Stanford Networking Seminar

12:15PM, Thursday October 14, 2010
Gates 104

Getting an Edge at High Speeds: Randomized Algorithms and Networking Hardware

George Varghese
University of California - San Diego

About the talk:
Even commercial router vendors have adopted randomized algorithms in a few cases because they are simple, fast, and memory-efficient. Further, because of the opportunity to see every arriving packet and preserve summary information about the entire population, such randomized algorithms can obtain an "edge" over standard algorithms that merely sample the population. I illustrate this thesis by two algorithms. First, I will describe an algorithm that provides an inexpensive technique for measuring the average and variance of packet latencies and loss on a link. By contrast, the majority of routers have no support for fine-grained latency measurement; managers must instead rely on approximate methods such as sending probe packets or using "tomographic" techniques. Second, I will describe an algorithm which allows scalable logging of millions of network addresses infected after an attack using only a small amount of memory. In both cases the talk will quantify the edge obtained over simple sampling. Joint work with Ramana Kompella, Kirill Levchenko, Terry Lam and Alex Snoeren.

About the speaker:
George Varghese obtained his Ph.D in 1992 from MIT. He joined UCSD in 1999, where he currently is a professor of computer science. He was elected to be a Fellow of the Association for Computing Machinery (ACM) in 2002. He has written a book on building fast router and endnode implementations called "Network Algorithmics", which was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift Inc. which was acquired by Cisco Systems in 2005.