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

Tuesday, October 6, 2009 - 2:32pm


3:30 – 4:30
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Subhash Suri

Computer Science, UC San Diego

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


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 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 of millions of network addresses infected after
an attack using only a small amount of memory. In all three case the
talk will quantify the edge obtained over simple sampling.

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


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 won the
ONR Young Investigator Award in 1996, and 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.