I - Technical Summary

The rapid growth of fiber line rates has meant that switches are potential bottlenecks to the growth of Internet traffic in the future. This has focused the attention of the switch designers on two switch architectures that are well-suited to this challenge: Virtual Output Queued (VOQ) switches and Load-Balanced Switches. However, a survey of switching literature reveals that most, but not all, switches have been optimized for cell switching, not packet switching. This may have been the right approach to designing ATM cell switches, but is clearly inappropriate for the variable sized packets seen in today's Internet. Internet switches are rapidly supplanting ATM switches, and as we shall demonstrate, this makes a significant difference to switch design. The optimal VOQ cell switch, using the high complexity maximum weight matching (MWM) algorithm, turns out to have higher delay than our proposed HE-iSLIP, a low complexity switch, when packet delay is measured. The reason is that the MWM algorithm leads to a high delay at the output of the switch, due to the time needed to reassemble the packets from its constituent cells. The matching algorithms we consider minimize this delay. We will therefore attempt to answer the following questions: Which matching algorithm delivers the lowest packet delay? How do we evaluate packet delay for such switches so that we can predict performance for switches too large to simulate? Can we design a switch whose packet delay grows less than linearly with switch size? The purpose of most of the previous work on VOQ switches has been to devise stable (100% throughput) matching algorithms. Only recently has the focus turned to algorithms of low complexity.

We will continue our ongoing research in devising switch matching algorithms, such as HE-iSLIP, which in addition to being provably stable, also have low complexity and low delay under all traffic patterns. Load balanced switches have recently emerged as an alternative switch architecture. They have the attractive feature of not requiring a centralized scheduler, unlike most VOQ switches, and are therefore more scalable. However, they do suffer from large worst case resequencing delay. We have designed a load balanced switch, called the Byte-Focal switch, which shows encouragingly low cell delay results. We intend to answer the following questions for this class of switches; How does one estimate the average delay, and possibly also the delay distribution, for such switches? This includes estimating resequencing delay. We will again consider the packet delay performance instead of just cell delay. This is challenging because the packet reassembly and resequencing operations overlap in time. Also, we will test a conjecture made on the basis of our previous research: For the long range dependent traffic characteristic of the Internet, load balanced switches may have inherent traffic shaping properties which lead to improved performance over competing switch architectures. After testing the validity of our conjecture using Internet traffic traces, we hope to uncover interesting switch design insights analogous to our above-mentioned work on the difference between packet delay and cell delay for packet switches. We hope this work will bring about important new results based on the demonstrable interplay between switch hardware design and performance, and Internet traffic engineering.

II - Broader Impacts

The research will be disseminated through publications, presentations and interactions with industry. The New York Center for Advanced Technology in Telecommunications, which has seed-funded the PI's research in this area, also facilitates interaction with switch equipment vendors such as Lucent Technologies and Fujitsu Network Communications. Jonathan Chao has a track record in writing texts in the area of switching and broadband communications. These books have helped present research in switching and networking in general through course texts at the graduate level. He has also developed courses where students design network subsystems such as buffer managers, schedulers and switch fabrics as projects using VLSI design tools. Shivendra Panwar and Yihan Li are co-authors of a textbook on a laboratory oriented course in networks at the senior/entering graduate level, a path breaking course which has been adopted by several universities. In addition to the PhD students supported by the grant, masters and undergraduate level students will also be involved in the research through project courses. The Departments of Electrical and Computer Engineering and Computer and Information Science have been jointly running a Undergraduate Summer Research Program for the past ten years, which has been funded by several past NSF Research Experience for Undergraduates (REU) grants and has attracted outstanding junior students nation wide, many of whom are women and from minority groups. A survey by the National Action Council for Minorities in Engineering ranked Polytechnic University among the top 20 schools graduating black engineers. We hope to support several students in this program using requested REU funding. Professor Panwar also supervised NY public high school students on a switch-related project which was an entry in the prestigious Intel Science Talent Search.