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 paper. 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 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. We 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 here. We show 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 nonblocking property. Thus, as with parallelization, dilation can also be used to increase the throughput of a waiting system. In addition, we 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.