A distributed architecture and crossbar scheduling algorithm for high performance switch fabrics
Wayne H. Wolf, Yuanlong Wang · 2002
High-performance high-capacity switch fabrics are of critical importance in the design of modern networking and computing systems. In the near future, the switch capacity of such systems will be in the multi-terabit range. Distributed switch architectures allow the partition of a switch into smaller and independent switch elements such that each of them can be built with currently available semiconductor and high-speed serial link technologies, a key advantage for building high-capacity switch systems. Two critical components of a distributed switch architecture are the queueing structure and the load-balancing algorithm. They determine the performance as well as the implementation feasibility of the switch system. In addition, the scheduling algorithm used in the switch elements can also impact the performance although it is not normally considered part of the distributed switch architecture. In this thesis, we present a new distributed switch architecture consisting of simple yet efficient queueing structure and load-balancing algorithm. Unlike some other distributed architectures, our proposed architecture introduces little internal communication overhead and has no throughput degradation. The queueing structure of the architecture is based on distributed non-buffered crossbars with request-only virtual output queues. The distributed load-balancing algorithm dynamically balances workloads among the parallel switch elements by trying to equalize the RVOQ lengths. The architecture achieves non-blocking switching without internal speed-up. The load-balancing algorithm can perform one load-balancing action in less than 10ns, which is suitable for OC-768 line rates of 40Gbps. We also present a practical yet accurate approach for analyzing the performance of our proposed switch architecture. By using a combination of analytical and simulation approaches, we show that our proposed architecture can be approximated as discrete-time Geom/G/P queues. We then apply the Allen-Cunneen approximation formula to derive the mean cell delay of the architecture as a function of the underlying crossbar scheduling algorithm, the number of parallel switch elements and the number of ports in the system. Finally, we present a new crossbar scheduling algorithm that can be used in the switch elements of our proposed switch architecture. The algorithm is fair and efficient in a benign environment and remains fair and starvation-free in other environments with ingress congestion and egress flow control, two working conditions commonly found in real systems. In contrast, other commonly deployed crossbar scheduling algorithms lose fairness and may even cause starvation under such conditions. The new algorithm can also be used in other systems using crossbar in their switch networks.