Even commercial router vendors have adopted randomized algorithms in a few cases because of their simplicity, speed, and memory-efficiency. Further, because of the opportunity to see every member of the population (i.e., 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 three algorithms. First, I will describe a simple algorithm for finding sources that send a large proportion of traffic, and its application in a worm detection chip. Second, 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. If time permits, I will describe a third algorithm which allows scalable logging, say of millions of network addresses infected after an attack, using only a small amount of memory. In all three case I will quantify the edge obtained over simple sampling.

Joint work with Cristi Estan, Ramana Kompella, Kirill Levchenko, Terry Lam and Alex Snoeren.

[slides]

George Varghese worked at DEC for several years designing DECNET protocols and products (bridge architecture, Gigaswitch) before obtaining his Ph.D in 1992 from MIT. He worked from 1993-1999 at Washington University. He joined UCSD in 1999, where he currently is a professor of computer science. He won the ONR Young Investigator Award in 1996, and was elected to be a Fellow of the Association for Computing Machinery (ACM) in 2002. Together with colleagues, he has 16 patents awarded in the general field of Network Algorithmics. Several of the algorithms he has helped develop have found their way into commercial systems including Linux (timing wheels), the Cisco GSR (DRR), and Microsoft Windows (IP lookups). He also helped design the lookup engine for Procket's 40 Gbps forwarding engine. 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., where he was the President and CTO. NetSift was acquired by Cisco Systems in 2005. From Aug 2005 to Aug 2006, he worked at Cisco Systems to help equip future routers and switches to detect traffic patterns for measurement and security.