Computer Networks & Packet Switch Design

The Internet is a challenging environment to design algorithms for: there is a lot of work to do and not enough time to do it in. For example, the time available to switch packets at a router in the Internet core is roughly 50 ns. It is very challenging to design good scheduling algorithms that operate at this speed. Thus, Internet algorithms need to be simple enough to be implementable, but sophisticated enough to perform well.

Randomized algorithms are particularly well-suited for this task because they base decisions on a small random sample of the state rather than the whole state. This considerably simplifies the implementation.

In this talk I will illustrate the use of randomization in devising simple, high-performance network algorithms; specifically for switch scheduling, web caching, and bandwidth partitioning.

Presenter(s)

Balaji Prabhakar is with the Departments of Electrical Engineering and Computer Science at Stanford University. He is currently interested in network algorithms, scalable network performance prediction, wireless networks and information theory. He is a Fellow of the Alfred P. Sloan Foundation, and has received the NSF CAREER award, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize from the University of Cambridge. He is a co-recipient of two best paper awards: at Hot Interconnects 2002 and at Infocom 2004.