Research Summary: George Varghese

The networking group at UCSD includes:

-- Joe Pasquale, Stefan Savage, Geoff Voelker and George Varghese in Computer Science doing Internet systems, security, and Mobile Code.

-- Rene Cruz, Ramesh Rao and Tony Acompora in Electrical Engineering doing wireless research.

-- Kim Claffy and David Moore at CAIDA building Internet tools for Internet measurement.

It has broad strengths in wireless, security, quality of service, optical networks, Internet protocols, Internet measurements and the relation between OS and networking. UCSD has a strong Wireless Center and a newly awarded California Institute for Technology (CALIT2) that aims to solve problems in genomics, traffic engineering and oceanography using wireless networking as a substrate.

Within the networking group at UCSD, my group conducts research that aims to make the Internet into something as fast and reliable as other utilities such as electricity and telephones. Our two particular research thrusts are: designing efficient techniques for removing networking bottlenecks; and second, designing provably robust network protocols. We build and measure real prototypes to validate the usefulness of our ideas in real networks.

If much of the work in the last 5 years can be characterized as detecting patterns within single packets (e.g., does a packet match one of a set of prefixes, or a set of fields in a classifer), much of my current and future work is on detecting patterns across a sequence of packets, still at high speed. Such multi-packet patterns are interesting for accounting and security. For example, many Denial-of-Service attacks have a characteristic attack signature which is a multi-packet pattern. Similarly, in a recent ACM Workshop on measurement we proposed detecting all flows that use more than a specified percentage of the link bandwidth. I'm interested in algorithms for this purpose, and the design of radically new network processors designs that can help detect such patterns at even OC-48 speeds.

We work with commercial vendors through consulting or patent licensing. Our group has been supported by a recent 900,000 NIST grant, 2.5 million in NSF grants and a 310,000 dollar ONR Young Investigator Award in the past 7 years. We have received roughly 3/4 of a million dollars in revenue from our router lookup inventions from 8 companies.

Efficient Protocol Implementations

My colleagues and I have invented some of the most efficient known algorithms for timer implementations (timing wheels), IP address lookup (expanded tries, compressed tries, binary search on lengths, binary search on prefix ranges, full tree bitmap), and fast filter matching (grid-of-tries, cross-producting). I have also helped invent efficient techniques for many other networking bottlenecks such as sequence number bookkeeping, fair queuing, link striping, packet reassembly, and circumventing lookups. Click here for some pointers to real products based on our ideas. I am writing a book called "Streamlining Network Protocol Implementations" due to be published by Addison-Wesley in 2002. 

Robust Protocol Design

My doctoral work at MIT was on the design of extremely robust network protocols (self-stabilizing protocols) that begin to work correctly regardless of initial states. With colleagues at MIT, I initiated several general and efficient approaches to designing self-stabilizing protocols including local correction, global correction and by compiling synchronous protocols. With colleagues from U.Texas I showed that local checking could be used to understand existing protocols. With students at Washington University, I developed two more techniques (counter flushing and window washing) for designing robust protocols, and characterized the power of crash faults. The crash faults result provides a justification for self-stabilization by showing that crashes can drive asynchronous systems into arbitrary states.

Research Directions

Current work includes the design of fast measurement techniques to support Accounting and fast techniques for Intrusion Detection and other security problems. I also kibbitz on a number of areas that are strictly none of my business: some examples are randomized memory interleaving (architecture), approximate string matching (computational biology), and some new proposals for content caching (distributed systems).