BROAD-BAND PACKET SWITCHES BASED ON DILATED INTERCONNECTION NETWORKS

A theoretical foundation for evaluation and comparison of a very broad spectrum of fast packet-switching techniques is developed in this pap er. Based on this framework, we 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 conte ntion are dropped or queued. In a loss system, the packet loss probabi lity can be made arbitrary small by providing enough paths between inp uts and outputs. We focus on the question: How does the switch complex ity grow as a function of switch size for a given loss probability req uirement? A uniform approach to this problem is developed here. We sho w that for an N x N switch, the required number of switch elements for both the parallel-banyan network and the tandem-banyan network is of order N(logN)2, whereas the complexity of a dilated-banyan network is of order NlogN(loglogN). Within the class of waiting systems, we show that the parallel banyan networks in a Batcher-parallel-banyan network can be replaced by a dilated-banyan network without sacrificing the n onblocking property. Thus, as with parallelization, dilation can also be used to increase the throughput of a waiting system. In addition, w e also explore the application of dilation in a large modular switch d esign which is realized by an interconnection structure consisting of Batcher-dilated-banyan networks and statistical multiplexers.