Route discovery for multistage fabrics in ATM switching nodes

This paper presents an intra-node Route Discovery Protocol (RDP) applicable to multistage switch fabrics in nodes of ATM Local Area Networks (LANs), as well as in transit nodes of future high-speed Metropolitan or Wide Area Networks (MANs or WANs). The proposed RDP automatically builds and periodically updates routing tables in each network adapter. These routing tables contain the mapping between the logical adapter addresses and the currently available physical routes through the multistage switch fabric to all other adapters attached to the node. In addition, functional entities located at specific adapters are detected and associated with physical routes in the routing tables. Detecting all routes during system startup is the basis for fast connection setup with low latency. By periodically monitoring all possible table entries, our protocol provides continuous supervision of the node's internal link status and can support possible higher-layer extensions to perform load balancing over alternative routes. Small control buffers in network adapters, which are typical for practical implementations, may lead to overflow conditions and, thus, to incompletely updated routing tables. An effective stochastic solution to this problem is presented and it will be shown through probabilistic analysis that reasonably small buffer sizes suffice for executing RDP with sufficient robustness.