George Varghese
Encyclopedia
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 Kaufmann in 2004.
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.
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
).
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.
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.
(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.
University of California, San Diego
The University of California, San Diego, commonly known as UCSD or UC San Diego, is a public research university located in the La Jolla neighborhood of San Diego, California, United States...
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 Kaufmann in 2004.
Education
Varghese received his B.Tech in electrical engineeringElectrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
from IIT Bombay
Indian Institute of Technology Bombay
The Indian Institute of Technology Bombay , popularly known as IIT Bombay or IITB, is a public research university located in Powai, Mumbai...
in 1981, his M.S. in computer studies from NCSU
North Carolina State University
North Carolina State University at Raleigh is a public, coeducational, extensive research university located in Raleigh, North Carolina, United States. Commonly known as NC State, the university is part of the University of North Carolina system and is a land, sea, and space grant institution...
in 1983 and his Ph.D. in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
from MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in 1993. He is a Fellow of the ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
since 2002.
Transparent bridge architecture
Before his Ph.D., George spent several years as part of the network architecture and advanced development group at Digital Equipment CorporationDigital Equipment Corporation
Digital Equipment Corporation was a major American company in the computer industry and a leading vendor of computer systems, software and peripherals from the 1960s to the 1990s...
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
Gigabit Ethernet
Gigabit Ethernet is a term describing various technologies for transmitting Ethernet frames at a rate of a gigabit per second , as defined by the IEEE 802.3-2008 standard. It came into use beginning in 1999, gradually supplanting Fast Ethernet in wired local networks where it performed...
).
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
Deficit round robin
Deficit round robin , also deficit weighted round robin , is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size...
(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 SystemsCisco Systems
Cisco Systems, Inc. is an American multinational corporation headquartered in San Jose, California, United States, that designs and sells consumer electronics, networking, voice, and communications technology and services. Cisco has more than 70,000 employees and annual revenue of US$...
and Juniper Networks
Juniper Networks
Juniper Networks is an information technology and computer networking products multinational company, founded in 1996. It is head quartered in Sunnyvale, California, USA. The company designs and sells high-performance Internet Protocol network products and services...
on tag switching
Multiprotocol Label Switching
Multiprotocol Label Switching is a mechanism in high-performance telecommunications networks that directs data from one network node to the next based on short path labels rather than long network addresses, avoiding complex lookups in a routing table. The labels identify virtual links between...
. 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.
Self stabilization
George is also known for his contributions to the theoretical field of self-stabilizationSelf-stabilization
Self-stabilization is a concept of fault-tolerance in distributed computing. A distributed system that is self-stabilizing will end up in a correct state no matter what state it is initialized with...
(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 Cristian 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, Cristian Estan, George Varghese, and Stefan Savage, 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.
- Cristian Estan, David Moore, and George Varghese, Building a Better NetFlow, Proceedings of the ACM SIGCOMM Conference, Portland, OR, September 2004
- Fan Chung Graham, Ron Graham, and George Varghese, 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, Tree bitmap: Hardware Software IP Lookups with Incremental Updates (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, Summary of Ph.D. Thesis on Self-stabilization
External links
- George Varghese home page at UCSD
- List of online papers of George Varghese
- Internet Algorithms Lab
- Center for Network Systems
- Center for Internet Epidemiology
- ACM Fellows listing for Varghese
- Timing wheels
- Fast timers in Linux
- FreeBSD
- Threaded indexes
- Multibit tries
- Scalable IP packet lookup
- Tree BitMap IP lookup algorithm
- Hypercuts
- Cisco Systems acquires NetSift
- Transparent bridging