CNS Core: Small: Ultra-Low-Complexity Switching Algorithms for Scalable High Network Performance

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The volumes of network traffic across the Internet and in data-centers continue to grow relentlessly, thanks to existing and emerging data-intensive applications. To transport and "direct" this massive amount of traffic to its respective destinations, network switches capable of connecting a large number of input-output ports (these switches are called high-radix) and operating at very high speeds are badly needed. A switch has to compute, for each time slot (say 10 nanoseconds in duration), a matching that specifies the set of simultaneous connections through the switch between the input ports and the output ports, each of which allows for the transmission of a packet between the corresponding port pair and out the switch toward its destination. A major challenge in designing fast high-radix switches is to develop algorithms that can compute high-quality matchings within the duration of a time slot, even when the switch size (radix) N is large. However, existing matching (switching) algorithms are not computationally efficient nor scalable enough for future fast high-radix switches. This project will bridge this gap via investigating next-generation matching algorithms that run much faster yet have excellent throughput and delay performances. This project will also develop new mathematical techniques that are necessary for analyzing the throughput guarantees of such algorithms. This project will build on and extend three recent research breakthroughs made by the principal investigator and his students. The first breakthrough is an add-on algorithm called Queue-Proportional Sampling (QPS) that can be used to boost the performance of existing matching algorithms, such as SERENA and iSLIP, at virtually no additional computation cost. The second breakthrough is QPS-r, a distributed matching algorithm that runs a constant r rounds (iterations) of QPS to compute a matching. In just a single iteration (i.e., when r = 1), QPS-1 outputs a matching that is in general not even maximal, yet has exactly the same quality as maximal matchings, which are much more expensive to compute. The third breakthrough is SERENADE, which effectively parallelizes SERENA and has a low computational complexity of O(log N) per port. This project will develop among others Small Batch QPS (SB-QPS), a batch matching algorithm that builds on QPS and QPS-r and appears to have all the desired properties of next-generation matching algorithms. This project will also develop new mathematical techniques, within the framework of Lyapunov stability theory, for determining and proving the throughput guarantees of several existing or next-generation matching algorithms such as QPS-iSLIP, QPS-r, SB-QPS, and O-SERENADE. As an important educational component of this project, the PI is writing the second edition of a textbook on a topic that contains the design and analysis of such algorithms as a subtopic. The PI will work closely with leading networking solution providers, such as Cisco, to facilitate the transfer of technology. The PI will further broaden the participation of under-represented groups, such as women and minority, in research and higher education. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.