Thursday, January30th, 2003
Room 104, Gates Computer Science Building

Practical Algorithms for Performance Guarantees in Internet
Routers

Sundar Iyer
Stanford University

About the talk:

Most Internet core routers are designed using a crossbar switching fabric. While crossbars can provide delay, fairness, bandwidth and quality of service guarantees, the algorithms suggested by existing theoretical results are not practical at high speed because of the complexity of switching algorithms. So most core routers use heuristic switching algorithms, and as a result their performance is unpredictable and the worst case is not known.

In this talk I will show how the addition of a fixed number of buffers to a crossbar can simplify switching algorithms. I will present a suite of distributed switching algorithms and derive analytically using Lyapunov functions and combinatorial arguments the conditions under which they can provide delay, fairness, bandwidth and quality of service guarantees. Since these algorithms operate in parallel on each input and output port of the router, and do not require communication with each other, they can be readily implemented. We believe that Internet core routers can be upgraded in a practical manner using these distributed algorithms to support the above performance guarantees.

Note: This is joint work with Da Chuang and Nick McKeown. This talk will be distinct from my orals talk which is scheduled for next month.

About the speaker:

Sundar Iyer is a doctoral candidate in the Computer Science department in Prof. Nick McKeown's High-Performance Networking Group. He holds a Masters degree in Computer Science from Stanford (June 2000) and a Bachelors degree in Computer Science and Engg. from I. I. T. Bombay (April 1998). From 1999-2001 he worked as a Senior Systems Architect in SwitchOn Networks, which is now part of PMC-Sierra. His research interests belong in the area of Network Architecture, and include network algorithms, system architecture and the theory and architecture of scalable load balancing systems. He can be currently reached at sundaes@cs.stanford.edu.