Cost-performance trade-offs in large scale banyan-based ATM switches
Creators: name: Mohammad, Alimuddin.
Publisher: name: University of British Columbia
Year: 2009

description: Much research effort has been directed into the design and performance analysis of ATM switches to date. However, less work has been done in efficiently utilizing the switch resources (e.g. buffers and links) to achieve the required performance. The current techniques for designing and evaluating ATM switches focus mainly on achieving a specified global cell loss probability within a given maximum cell delay. While useful and necessary to ensure that the switch can provide an acceptable QoS, this approach cannot effectively measure other important qualities of an ATM switch such as resource utilization and implementation complexity. Further, as the use of the Internet increases and new multimedia applications emerge there is need for substantial improvement in capacity on Internet backbone links. The need for ever increasing packet delivery bandwidth makes it inevitable that switches will have to scale to handle larger aggregate bandwidth (quiet possibly in terabit-per-second) range and more importantly to maintain QoS delivery. This thesis proposes a unifying framework for the design and analysis of large scale ATM switches based on enhanced banyan topologies. The banyan architecture has been chosen as the target architecture for developing the framework, since it is a logiV depth network and is optimal in the use of switching elements. However, the standard banyan network suffers from internal blocking. In order to overcome blocking in the banyan network we have proposed the fat-banyan (FAB) architecture which employs gradual increase in dilation from the input stage to the output stage of the network. Gradually incrementing dilation has dramatic impact on the implementation and architectural scalability of the FAB switch. Further, the FAB switch is highly optimized in the utilization of the internal bandwidth by appropriate setting of the dilation parameter per stage. The FAB switch can scale to the terabit-per-sec range with reasonable increase in chip count. Also, there is minimal interaction between the different streams (VCs/VPs) traversing the switch, thus minimizing any effect on the QoS of a stream from other streams. The performance of the FAB is analyzed by analytical methods and by extensive computer simulations. It should be noted that the technique of optimizing internal bandwidth can be applied in general to other ATM switching fabrics like the Benes network and the Fat-tree. An important resource of an ATM switch is its buffers. The proliferation of besteffort services implies that ATM switches must contain large buffers to effectively manage congestion. Shared-memory switching uses smaller amount of buffering to achieve the same loss probability as that of dedicated buffering. However, shared memory architectures do not scale due to limitations of memory cycle time. A novel approach to scale shared-memory switches is proposed using small depth (truncated) self-routing fabrics. This approach provides an efficient realization of the growable switches concept which was proposed by other researchers. Three buffering schemes have been considered for the FAB switch: output buffering, shared output buffering and combined input with output buffering (dedicated as well as shared). The performance under these buffering schemes has been analyzed by extensive simulation. Pure output buffering is considered as it has been shown to provide optimal delay and throughput performance. Shared output buffering has been combined with the use of the memoryless truncated FAB network to design highly scalable shared-memory switch architectures. Input-output buffering with backpressure is shown to provide a cost-effective way of designing a lossless switching fabric. This thesis also examines multicasting on the FAB switch. We have proposed a scheme to efficiently handle the replication of multicast packets in the FAB switch. It is shown that this technique can achieve very low cell loss even at very high offered loads and can also handle the case where the number of packet copies exceeds the switch size. The various aspects of design and performance optimization developed in this thesis can serve as a general approach for designing and evaluating Terabit-per-second ATM switches.