Broadband packet switches based on dilated interconnection networks

A theoretical foundation for the evaluation and comparison of a very broad spectrum of fast packet-switching techniques is developed. Based on this framework, the authors investigate the complexity of various packet switch designs, and demonstrate the advantage of dilation as a switch-design technique. Packet switches are classified either as loss systems or waiting systems, according to whether packets losing contention are dropped or queued. In a loss system, the packet loss probability can be made arbitrary small by providing enough paths between inputs and outputs. The authors focus on the question: how does the switch complexity grow as a function of switch size for a given loss probability requirement? A uniform approach to this problem is developed. It is shown that for an N/spl times/N switch, the required number of switch elements for both the parallel-banyan network and the tandem-banyan network is of order N(log N)/sup 2/, whereas the complexity of a dilated-banyan network is of order N log N(log log N). Within the class of waiting systems, it is shown that the parallel banyan networks in a Batcher-parallel-banyan network can be replaced by a dilated-banyan network without sacrificing the nonblocking property. Thus, as with parallelization, dilation can also be used to increase the throughput of a waiting system. In addition, the authors also explore the application of dilation in a large modular switch design which is realized by an interconnection structure consisting of Batcher-dilated-banyan networks and statistical multiplexers.>