Load Balancing (2014) : With Mohammed Alizadeh, Terry Lam, Tom Edsall, Andy Fingerhut, and Rong Pan at Cisco, CONGA algorithmn implemented in Cisco/Enseme switch to go beyond the limitations of static hash ECMP.
Net Sonar (2014) : With J. Zheng, R. Mahajan, M. Zhang, and N. Mckeown. NetSonar algorithm implemented in Microsft's Autopilot that runs on all our data centers.
Genomic Compression using SlimGene (Recomb 2010) : With Christos Kozanitis and Vineet Bafna, SlimGene is being used at Illumina.
Automated Worm Fingerprinting (OSDI 2004) : With Sumeet Singh, Stefan Savage, and Cristi Estan, work on automated worm fingerprinting was commercialized by a company called NetSift. NetSift was sold to Cisco in 2005.
Measurement Algorithms (ACM TOCS 2000) : With ith Cristi Estan), measurement algorithms using multistage filters and bitmap counters implemented at Gigabit speeds in Cisco and other routers.
IP Forwarding Engine: With John Holst, Tony Li, Bill Lynch and Sharad Merhotra and others, IP lookup architecture for Procket Networks, as part of of the first 5 people to join the company. In 2003, when Procket went public it was the fastest forwarding engine in the world running all day at 40 Gbps for minimum size packets, faster than Juniper and Cisco routers. While Procket was eventually sold to Cisco, Procket's promise at the time was hinted at by a SiliconValley.com article (Jan 2002) which reported that Procket's valuation in Feb 2001 was $1.55 billion, the highest valuation given to any existing private company till then.
IP Route Lookups (SIGCOMM 97, SIGMETRICS 98) : With V. Srinivasan, M. Waldvogel, J, Turner, licensed to Microsoft, NEC, BBN, Ascend, Quarry, Onex, and Chiaro in the period 1998-2001. Together with the work at Lulea University, the Washington University algorithms and patents helped changed the perception that IP lookups were inherently slow. The Tree BitMap Algorithm (ACM CCR April 2004, with Eatherton and Dittia) is currently used in Cisco's highest end CRS-1 router. CRS-1 overview, See Slide 32.
Timing wheels (SOSP 87): With Tony Lauck and Adam Costello, used in a number of systems including commercial systems due to DEC and SIEMENS and academic systems like the x-kernel. BSD implementation ported to FreeBSD by Justin Gibbs (Sept 97) and then to Linux. Many important systems such as HotMail and Yahoo run (or at least ran) on FreeBSD.
Deficit Round Robin (SIGCOMM 95): With M, Shreedhar, fair queuing algorithm implemented by Cisco in the GSR (with a small modification to add 1 priority queue for voice and called MDRR), Microsoft in Windows NT, Motorola, and several other companies. QoS Tests in Internet 2 say (qbone.internet2.edu/presentations/teitelbaum-terenaAntalya-5.01.pdf) that MDRR "seems to work". Similarly, router tests show that Cisco routers using MDRR drop no high priority packets while Juniper's M160 (that uses weighted round robin does (see newsroom.cisco.com/dlls). MDRR continues to be an important QoS mechanism as part of Cisco's Voice over IP, VPN, and DiffServ strategies. Deficit Round Robin showed that Fair Queuing was possible to implement at very high speeds.
Threaded Indices (SIGCOMM 95): With G. Chandranmenon. Predates Cisco's tag switching and MPLS architecture. For example, the Cisco Tag Switching Architecture Overview on the Cisco web page says that "Chandranmemon and Varghese [SIGCOMM 95] have described a scheme that is essentially equivalent to the destination-based unicast routing module of tag switching". Tag switching and MPLS have been major forces that are widely deployed in the Internet today. An early NSF proposal we submitted in Dec 1993 that described this idea has been cited as "prior art" for MPLS in two lawsuits.
Update Process for OSI Routing: (Patent P3 with Radia Perlman) used by many OSI routers. OSPF routers in the Internet use an almost identical protocol, and OSPF is the most widely used interior routing protocol used by most ISPs precisely because of its reliable routing protocol.
Bridge architecture specification: Wrote the first bridge architecture specification at DEC (based on inventions by Radia Perlman and Mark Kempf) that became the 802.1 Spanning Tree Bridge Specification, and the basis for commercial Ethernet and FDDI bridges. Since we introduced bridging at DEC in 1983, bridging has become a huge growth area; commercial Ethernet "switches" are really multiport bridges with a crosbar fabric.
Fast string matching for Intrusion Detection: With Mike Fisk, was ported to a prior version of the Snort open-source IDS tool by Mike Fisk.
SRR Load Balancing (SIGCOMM 96): With Hari Adiseshu, implemented in Cisco's IOS 11.3(1) (by Dana Blair) as part of Cisco's multilink PPP implementation.
Packet Classification (SIGCOMM 98): With V. Srinivasan and S. Suri, patented and licensed by Onex.
Compressed Tries: With H. Wilkinson, algorithms for OSI Lookups. Implemented in DEC's DECnis and other Routers.
Source Hashing: (SIGCOMM 95) used in IPv6 flow Ids (independently invented by Dave Clark).
Other Consulting : With colleagues, consulted on memory design for Memoir (acquired by Cisco), lookup and classification algorithms for SwitchOn (acquired by PMC), load distribution algorithms for Jibe Networks (acquired by Citrix), lookup and striping algorithms for Sanera Systems (acquired by McData). Also consulted for AOL, DEC, Intel, STMicroelectronics, Greenfield Networks, Chiaro Networks, and Fujitsu.