MS4 - A HIGH-PERFORMANCE OUTPUT BUFFERING ATM SWITCH

While pure output-buffered ATM switches achieve the best possible throughput-delay performance, most of them suffer from high complexity. In this paper, we describe a low-complexity output buffering deflection-routing based ATM switch, called the Multi Single-Stage-Shuffling Switch (MS4). Our work is motivated by the observation that cells which lose contention in any of the Tandem-Banyan switch networks do not contribute to the throughput of the switch until they reach the inputs of the following network. The MS4 is based on multi-layering of unbuffered single-stage interconnection networks. It preserves cell-sequencing while providing cells with multiple concurrent paths for each input-output pair. The switch is analysed under uniform traffic assuming arbitrary switch parameters. It is shown that a complexity of only O(N log(2)N) is required to achieve arbitrary small cell loss probabilities in the interconnection network, for a switch of size N. Simulation is used to assess the accuracy of the analysis and to examine the MS4 under a variety of traffic models. The MS4 is shown to be robust under non-uniform traffic. It is also shown to compare well to other known ATM switch architectures. Finally, a variation of the switch is described, analysed and compared to the original design.