CSAIL Event Calendar

Scalable Petabit Router Architectures

Abstract: Several current and emerging trends continue to drive exponential growth in traffic demand on the Internet. First, over the last few years, there has been a ten-fold increase in the number of broadband subscribers, with currently over 100 million subscribers. Second, there is growing deployment of Fiber-to-the-Homes (FTTH) with access speeds upwards to 2.4 Gbps. In Japan, there are plans to provide FTTH access to over 30 million homes in the next seven years. Though targets have not been set in the US and Europe, similar ambitions are expected eventually. Finally, traffic is becoming increasingly global, which will further increase traffic demand across the Internet. In addition to growing traffic demand, there is an ongoing trend to consolidate smaller routers into high capacity routers to improve manageability and ease of service integration. To accommodate increasing traffic demand and router consolidation, I will describe in this talk two closely related scalable router architectures that we have been developing that can scale to petabit routing capacities.

The first router architecture is called a Concurrent Matching Switch (CMS). Like previously proposed load-balanced routers, the CMS architecture is also based on two identical stages of fixed configuration meshes that do not require dynamic reconfigurations. These fixed configuration meshes can be efficiently scaled to petabit switching capacities using optics. To ensure 100% throughput, packet ordering, and low average packet delay, the CMS architecture uses a novel fully distributed contention-resolution scheme. This distributed contention-resolution scheme can be implemented independently on each linecard with O(1) time complexity on sequential hardware, which makes the method independent of switch size. In comparison with previously proposed load-balanced router architectures that can ensure packet ordering, the CMS architecture can achieve much lower average packet delay.

The second router architecture is called an Interleaved Matching Switch (IMS), and it is also based on two identical stages of fixed configuration meshes. In the case where the traffic pattern is fixed and known apriori, contention-resolution can be performed offline by means of Birkhoff-von Neumann decomposition. Packets can then be scheduled online independently at each input linecard in a fully distributed manner to achieve both 100% throughput and Quality-of-Service guarantees.

In addition to showing the practicality of these architectures, it is also interesting to note that these architectures also provide a link between the large body of existing work on scheduling algorithms and recently proposed load-balanced router architectures.

Biography:

Bill Lin received his Ph.D in Electrical Engineering and Computer Sciences from the University of California at Berkeley in 1991. He is currently on the faculty of Electrical and Computer Engineering at UCSD where he is actively involved with the Center for Networked Systems, the Center for Wireless Communications, and the California Institute for Telecommunicatons and Information Technology in industry-driven research efforts. Prior to joining UCSD, he was the head of the System Control and Communications Group at IMEC, Belgium, the largest independent microelectronics and information technology research center in Europe. His research has led to over 100 journal and conference publications, including several conference best paper citations and a best paper award at the IEEE Transaction on VLSI Systems. He also holds 2 awarded patents.

See other events happening in October 2006