| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | August 5, 2019 |
| Latest Amendment Date: | August 5, 2019 |
| Award Number: | 1909048 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Darleen Fisher
CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2019 |
| End Date: | September 30, 2022 (Estimated) |
| Total Intended Award Amount: | $432,691.00 |
| Total Awarded Amount to Date: | $432,691.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
926 DALNEY ST NW ATLANTA GA US 30318-6395 (404)894-4819 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
225 North Avenue Atlanta GA US 30332-0002 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Networking Technology and Syst |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Intellectual Merit: The research team, referred to as "the team" in the sequel, consist of PI Xu, his Ph.D. and undergraduate students, and a few collaborators. Over the past three years, the team have worked on and solved close to a dozen research problems related to the two major goals of this project: (1) to investigate next-generation matching algorithms that have both low time complexity and excellent throughput and delay performances; (2) to develop novel mathematical techniques that are necessary for analyzing the throughput guarantees of such algorithms.
Towards the first goal, the team have designed or fully developed several such matching algorithms. The first such algorithm is QPS-r. QPS-r is a distributed matching algorithm that runs a constant r rounds (iterations) of QPS to compute a matching. The team show that, 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 team have also demonstrated that QPS-3 (running r=3 iterations) has comparable empirical throughput and delay performances as iSLIP (running O(log N) iterations).
The second such algorithm is SERENADE (SERENA, the Distributed Edition). SERENADE effectively parallelizes SERENA, a centralized switching algorithm that guarantees 100% throughput. SERENADE has a low computational complexity of O(log N) per port, whereas SERENA has O(N) computational complexity.
The third such algorithm is Small Batch QPS (SB-QPS), a parallel batch switching algorithm the sketchy ideas of which were laid out in the proposal. SB-QPS achieves a high throughput of near or over 90% under all typical traffic patterns. It also achieves the lowest possible time complexity of O(1) per matching computation per port, via parallelization.
As a significant extension of SB-QPS, the team have also developed another parallel switching algorithm called Sliding-Window QPS (SW-QPS). SW-QPS retains and enhances all benefits of SB-QPS, and reduces the batching delay to zero via a novel switching framework called sliding-window switching. The team have also applied the sliding window switching framework to a classic yet still widely used switching algorithm called iSLIP.
Towards the second goal, the team have proved, using Lyapunov stability theory, that QPS-1 can achieve the same lower bound (of 50%) on throughput and the same upper bound on average delay under i.i.d. traffic arrivals, as maximal matching algorithms. The team also extended both bounds for QPS-1 under Markovian arrivals, which is a much more general and widely applicable traffic model. The team have also made good progress in proving Conjecture 1 in the proposal which states that the throughput lower bound of QPS-1 is actually 63.2% (more precisely 1 - 1/e), not just 50%, under i.i.d. traffic arrivals. The team have proved this conjecture when the traffic matrix is uniform. Proving this special case is a significant result for two reasons. First, no one has proved any throughput lower bound larger than 50% for maximal matching algorithms or similar algorithms, so this proof is a fundamental breakthrough. Second, the idea of the proof suggests a new solution approach in the fluid analysis.
Broader Impact: The first broader impact agenda item of the proposal is for the PI to finish drafting the second edition of the legendary textbook "Network Algorithmics", which contains a chapter devoted to (single) crossbar and data center switching. The book is now published. The webpage advertising this book can be found at:
https://www.elsevier.com/books/network-algorithmics/varghese/978-0-12-809927-8
The second broader impact agenda item is to broaden the participation of under-represented groups in research and higher education. Toward that end, the PI has actively recruited female and minority Ph.D. and undergraduate students. This recruiting effort was successful in 2022. A female Georgia Tech graduating senior (to graduate in Fall 2022) with 3.84 GPA joined the team in early August 2022. She does not plan to pursue a Ph.D., but is committed to being a part of the team until she graduates with an MSCS degree at Georgia Tech in summer 2024. She has been working, under the guidance of the PI and his Ph.D. students, on the two research problems related to the project.
The third broader impact agenda item is possible technology transfer. Toward that end, Georgia Tech filed an international patent application in August 2021 for SB-QPS, SW- QPS, and SW-iSLIP under a unified framework of small-batch switching and sliding-window switching. This is a significant achievement, since Georgia Tech (GT) files a patent (and pays tens of thousands of dollars) for only a tiny percentage of inventions. Out of two dozens or so GT-owned inventions by the PI during his 22-year career at GT, this is the first one that Georgia Tech decides to file a patent for.
Last Modified: 03/31/2023
Modified by: Jun Xu
Please report errors in award information by writing to: awardsearch@nsf.gov.
