Non-blocking and distributed routing principles in atm packet switching networks
P.P. To, Tony T. Lee · 1997
With the advent of high-speed electronics and optical transmission technology, link transmission speed has improved greatly over the last decade. It is envisioned that the typical transmission speed in future broadband integrated services digital networks (BISDN) will be at least 155 Mbps. A broadband packet switch operating under such a high-speed environment must be very efficient in order to give a high-throughput and a low delay. In addition, the switch must possess the non-blocking and distributed routing properties. Non-blocking and distributed routing (or self-routing) refer to the ability of the switch to route incoming packets with distinct outputs to their respective destinations without internal blocking, and that such routing can be performed in a distributed manner without requiring centralized coordinations between different switch modules. One of the most commonly used non-blocking and self-routing network architecture is the Batcher-banyan network. In this thesis, we generalize and consolidate the non-blocking and self-routing properties of a wide range of interconnection networks. In particular, we focus on the Clos network and show that by generalizing the address numbering scheme of the multistage interconnection network (MIN) to the Clos network, the Clos network is non-blocking given monotonic connection requests, and that self-routing can be performed by means of the Rank-based Assignment Algorithm. The results can be extended to the broadcast networks to build a broadcast Clos network, which can then be used in the construction of multicast packet switches. In view of the fact that the properties of an interconnection network are largely determined by the properties of the underlying graph, we next turn to study the topological properties of the de Bruijn graph and the hypercube, which are two well-known graphs in multiprocessor computer architectures. We consolidate the two graphs and propose a general Multi-dimensional Shuffle-exchange Network which inherits the properties of both de Bruijn graphs and the hypercube. The Multi-dimensional Shuffle-exchange Network can be used as recirculating networks as well as multistage networks. In this context, we study both cases and show that the Multi-dimensional Shuffle-exchange Network is a viable alternative to the widely used Banyan class of networks.