Basser Seminar Series

The Future of Network Algorithmics?

Speaker: Dr George Varghese
Microsoft Research

When: Friday 6 June, 2014, 12:00-1:00pm

Where: The University of Sydney, School of IT Building, SIT Lecture Theatre (Room 123), Level 1

Add seminar to my diary


I use the phrase "network algorithmics" to denote the study of network bottlenecks that must be implemented at high speeds using a multidisciplinary approach that involves algorithms, hardware design and attention to the overall system. Network algorithmics has successfully tackled issues such as IP lookup, packet classification, and simple QoS functions - to the extent that vendors regard these as "solved problems". In this talk I consider two new functions we have done some initial work on using the principles of network algorithmics.

First, I will describe our Kangaroo system for flexible, wire-speed packet parsing which introduces some new concepts such as lookahead parsing using CAMs and new measures of parsing speed. Second, I will describe an algorithm called the Lossy Difference Aggregator that provides an inexpensive technique for measuring the average and variance of packet latencies and loss on a link. I will also speculate that there are a number of future problems that can be tackled using the techniques of network algorithmics.

Speaker's biography

George Varghese obtained his Ph.D in 1992 from MIT. He joined Microsoft Research as a Principal Researcher after being a professor at UCSD for many years. He was elected as a Fellow of the ACM in 2002. Several algorithms he helped invent (Deficit Round Robin, IP lookups, Timing Wheels) are used in commercial products. His book "Network Algorithmics" was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift Inc. which was acquired by Cisco Systems in 2005. He was awarded the Kobayashi Award for Computers and Communication in 2014.