George Varghese (born 1960) is a Principal Researcher at

Microsoft Research Microsoft Research (MSR) is the research subsidiary of Microsoft. It was created in 1991 by Richard Rashid, Bill Gates and Nathan Myhrvold with the intent to advance state-of-the-art computing and solve difficult world problems through technologi ...

. Before joining MSR's lab in Silicon Valley in 2013, he was a Professor of Computer Science at the

University of California San Diego The University of California, San Diego (UC San Diego or colloquially, UCSD) is a public land-grant research university in San Diego, California. Established in 1960 near the pre-existing Scripps Institution of Oceanography, UC San Diego is t ...

, where he led the Internet Algorithms Lab and also worked 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 Morgan Kaufmann Publishers is a Burlington, Massachusetts (San Francisco, California until 2008) based publisher specializing in computer science and engineering content. Since 1984, Morgan Kaufmann has published content on information technology ...

in 2004.

Education

Varghese received his B.Tech in

electrical engineering Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems which use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...

from

IIT Bombay The Indian Institute of Technology Bombay (IIT Bombay or IITB) is a public research university and technical institute in Powai, Mumbai, Maharashtra, India. It is considered as one of the best engineering universities in India and is top ranked ...

in 1981, his M.S. in computer studies from

NCSU North Carolina State University (NC State) is a public land-grant research university in Raleigh, North Carolina. Founded in 1887 and part of the University of North Carolina system, it is the largest university in the Carolinas. The university ...

in 1983 and his Ph.D. in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

from

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...

in 1993, where his advisor was

Nancy Lynch Nancy Ann Lynch (born January 19, 1948) is a mathematician, a theorist, and a professor at the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the "Theory of D ...

. He is a Fellow of the ACM since 2002.

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 Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president unt ...

, 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 In computer networking, Gigabit Ethernet (GbE or 1 GigE) is the term applied to transmitting Ethernet frames at a rate of a gigabit per second. The most popular variant, 1000BASE-T, is defined by the IEEE 802.3ab standard. It came into use i ...

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. His contributions to network algorithmics include

Deficit Round Robin Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) poli ...

(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 Cisco Systems, Inc., commonly known as Cisco, is an American-based multinational corporation, multinational digital communications technology conglomerate (company), conglomerate corporation headquartered in San Jose, California. Cisco develo ...

and

Juniper Networks Juniper Networks, Inc. is an American multinational corporation headquartered in Sunnyvale, California. The company develops and markets networking products, including routers, switches, network management software, network security products, ...

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.

Self stabilization

George is also known for his contributions to the theoretical field of

self-stabilization Self-stabilization is a concept of fault-tolerance in distributed systems. Given any initial state, a self-stabilizing distributed system will end up in a correct state in a finite number of execution steps. At first glance, the guarantee of self ...

(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.

Awards and honors

* Elected as a member into the

National Academy of Engineering The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...

, 2017National Academy of Engineering Elects 84 Members and 22 Foreign Members
February 8, 2017, retrieved 2017-05-02. * 2014 Koji Kobayashi Award for Computers and Communications for "Contributions to the field of network algorithmics and its applications to high-speed packet networks" *

ACM Fellow ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia Computing ...

, 2002 * Best Teacher Award in Computer Science, UCSD, 2001, voted by graduating undergraduate students * Best Tutorial Award, SIGMETRICS 98. * Big Fish, Mentor of the Year Award, Association for Graduate Engineering Students (AGES),Washington University 1997. * ONR Young Investigator Award 1996 (34 awarded out of 416 applications across the sciences, among 2 computer scientists chosen in 1996) * Best Student Paper, PODC 96, for a paper jointly written with student Mahesh Jayaram. * Joint winner of the Sproull Prize for best MIT Thesis in Computer Science (1993) and nominated by MIT for ACM Thesis Prize. * DEC Graduate Education Program (GEEP) Scholar, 1989–1991.

Selected publications

* Sumeet Singh, Cristian Estan, George Varghese, and Stefan Savage
Automated Worm Fingerprinting
Proceedings of the 6th ACM/USENIX Symposium on Operating Systems 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