George Varghese

George Varghese is a Professor of Computer Science at the University of California San Diego where he leads the Internet Algorithms Lab and also works with the Center for Network Systems and the Center for Internet Epidemiology. He is the author of the textbook "Network Algorithmics" published by Morgan-Kaufmancite web|url=http://books.elsevier.com/us/mk/us/subindex.asp?isbn=9780120884773&country=United+States&community=mk&ref=&mscssid=1561539SKMV19K39FWD7B3E7GX31F5QD|title=Network Algorithmics:An Interdisciplinary Approach to Designing Fast Networked Devices|accessdate=December 22|accessyear=2006|author= |last= |first= |authorlink= |coauthors= |date= |year= |month= |format= |work= |publisher=Elsevier: Morgan Kaufman|pages= |language= |archiveurl= |archivedate=] in 2004.

Education

Varghese received his B.Tech in electrical engineering from IIT Bombay in 1981, his M.S. in computer studies from NCSU in 1983 and his Ph.D. in computer science from MIT in 1993. He is a Fellow of the ACM since 2002 [ACM Fellows, V [http://fellows.acm.org/homepage.cfm?alpha=V&srt=alpha] ] .

Research

Transparent bridge architecture

Before his Ph.D., George spent several years as part of the network architecture and advanced development group at Digital Equipment Corporation where he wrote the first specification for the first transparent bridge architecture (based on the inventions of Mark Kempf and Radia Perlman). After several iterations and other authors, this became the IEEE 802 bridge specification, a widely implemented standard that is the basis of the billion dollar transparent bridging industry. He was also part of the DEC team that invented the Gigaswitch and the Giganet (a precursor to Gigabit Ethernet).

Network algorithmics

Varghese is best known for helping define network algorithmics, a field of study which resolves networking bottlenecks using interdisciplinary techniques that include changes to hardware and operating systems as well as efficient algorithms.

Among his contributions to network algorithmics are Deficit Round Robin (co-invented with M. Shreedhar), a scheduling algorithm that is widely used in routers, and timing wheels (with Tony Lauck), an algorithm for fast timers that is used as the basis of fast timers in Linux and FreeBSD.

IP lookup and packet classification

Varghese has also worked extensively on fast IP lookup and packet classification. His work with G. Chandranmenon on Threaded indexes predates the work done at Cisco Systems and Juniper Networks on tag switching. His work on multibit tries (with V. Srinivasan) has been used by a number of companies including Microsoft. His work on scalable IP packet lookup (with Waldvogel and Turner) for longer addresses such as IPv6 is being considered for use by Linux.

George also worked with Eatherton and Dittia on the Tree bitmap IP lookup algorithm that is used in Cisco’s CRS-1 router, which many believe to be the fastest router in the world. Tree bitmap and hypercuts (with Sumeet Singh and Florin Baboescu) appear to be among the best algorithms (excluding CAMs) for IP lookup and packet classification today.

elf stabilization

George is also known for his contributions to the theoretical field of self-stabilization (a form of fault-tolerance) where he has helped (with various colleagues) pioneer several general techniques such as local checking, local correction, and counter flushing.

NetSift

Varghese co-founded NetSift Inc. (with Sumeet Singh) in 2004, serving as President and CTO. NetSift helped pioneer the notion of automated signature extraction for security and helped to introduce the use of streaming algorithms for network measurement and security at speeds greater than 10 Gbit/s. His work with Christian Estan on multistage filters has been widely used in industry. NetSift was acquired in June 2005 by Cisco Systems as part of the Modular Switching Group.

Selected publications

* Sumeet Singh, Christian Estan, George Varghese, and Stefan Savage, [http://www.cs.ucsd.edu/~savage/papers/OSDI04.pdf Automated Worm Fingerprinting] , Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI). This paper was the basis of NetSift, which see above.
* Christian Estan, David Moore, and George Varghese, [http://www.cs.ucsd.edu/~varghese/PAPERS/sigcomm04.pdf Building a Better NetFlow] , Proceedings of the ACM SIGCOMM Conference, Portland, OR, September 2004
* Fan Chung Graham, Ron Graham, and George Varghese, [http://www.math.ucsd.edu/~fan/wp/george.pdf Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines]
* Proceedings of SPAA 2004 (invited and accepted to Theory of Computer Science journal as best of SPAA), Barcelona, Spain March 2004
* W. Eatherton, Z. Dittia, and George Varghese, [http://www.cisco.com/ Tree bit
] (no prior conference paper, IP lookup algorithm used in Cisco's most recent CRS-1 router) ACM Computer Communications Review, volume 34, April 2004
* George Varghese, [http://www-cse.ucsd.edu/users/varghese/PAPERS/thesissummary.ps.Z Summary of Ph.D. Thesis on Self-stabilization]

References

External links

* [http://www.cse.ucsd.edu/~varghese/ George Varghese home page at UCSD]
* [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/v/Varghese:George.html List of online papers of George Varghese]
* [http://ial.ucsd.edu/ Internet Algorithms Lab]
* [http://cns.ucsd.edu/ Center for Network Systems]
* [http://www.ccied.org/about.html Center for Intenet Epidemiology]
* [http://fellows.acm.org/fellow_citation.cfm?id=4302337&srt=alpha&alpha=V ACM Fellows listing for Varghese]
* [http://portal.acm.org/citation.cfm?id=37504 Timing wheels]
* [http://www.gelato.unsw.edu.au/lxr/source/Documentation/hrtimers.txt Fast timers in Linux]
* [http://fxr.watson.org/fxr/source/kern/kern_timeout.c FreeBSD]
* [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=217427 Threaded indexes]
* [http://citeseer.ist.psu.edu/srinivasan99fast.html Multibit tries]
* [http://lciteseer.ist.psu.edu/waldvogel97scalable.html Scalable IP packet lookup]
* [http://ccr.csail.mit.edu/issues/v34n2/AcademicPaper.2004-05-26.0836597984 Tree BitMap IP lookup algorithm]
* [http://portal.acm.org/citation.cfm?id=863980 Hypercuts]
* [http://newsroom.cisco.com/dlls/2005/corp_062705.html Cisco Systems acquires NetSift]
* [http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/transbdg.htm Transparent bridging]