12:45 PM, January 25, 2001
Gates Building, Room 104

Internet Algorithmics

George Varghese,
Department of Computer Science,
University of California, San Diego

About the talk:

Internet Algorithmics is a term that I use to describe the emerging study of useful techniques to speed up Internet implementations. Algorithmics includes the use of new algorithms, operating system changes, hardware fixes, new system decompositions --- *whatever* it takes to speed up Internet bottlenecks. A key requirement is systems thinking: problems can often be eliminated by moving them from one part of a system to another.

After quickly showing two networking examples (timing wheels, Deficit Round Robin) of the way systems thinking differs from isolated algorithmic thinking, I provide two larger examples of bottlenecks based on current work. The first is the need for unconventional memory allocation techniques for allocating limited on-chip SRAM for applications such as lookups. Our new allocation schemes give much better worst-case bounds than say the buddy system, but are based on the fact that compaction is possible in our applications. This work was reported in SIGCOMM 2000. My second example is a new scalable packet classification scheme that has not been reported before; results on real databases seem very promising. The talk will not assume any familiarity with the Internet; the focus will be on patterns of algorithmic thinking as opposed to the results themselves.

About the speaker:

George Varghese has been a full professor of Computer Science at the University of California, San Diego since 1999. Before that he was a professor of Computer Science at the Washington University in St. Louis, since 1993. He received his PhD in Computer Science from MIT in 1993, and a MSc in Computer Studies from the North Carolina State University at Raleigh in 1983.