Load Balancing using Flame (2012) : With Terry Lam, Tom Edsall, Andy Fingerhut, and Rong Pan at Cisco, our Flame load balancing algorithm is being implemented in a chip at Cisco to go beyond the limitations of static hash ECMP.
Genomic Compression using SlimGene (Reccomb 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, our work on automated worm fingerprinting was commercialized by a company (that Sumeet and I founded) called NetSift which was sold to Cisco in 2005.
Measurement Algorithms (ACM TOCS 2000) : Our measurement algorithm, with Cristi Estan) using multistage filters and bitmap counters are being implemented at Gigabit speeds in Cisco and other routers.
IP Forwarding Engine: With John Holst, Tony Li, Bill Lynch and Sharad Merhotra and others, I designed the 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 last valuation by VCs (Feb 2001) was $1.55 billion, the highest valuation VCs have given any existing private company.
IP Route Lookups (SIGCOMM 97, SIGMETRICS 98) : 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. An algorithm called Tree BitMap (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): used in a number of systems including commercial systems due to DEC and SIEMENS and academic systems like the x-kernel. Our BSD implementation ported to FreeBSD by Justin Gibbs (Sept 97). Many important systems such as HotMail and Yahoo run (or at least ran) on FreeBSD. The timing wheel implementation reduced overhead from 10 % to less than a percent.
Deficit Round Robin (SIGCOMM 95): 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. While Deficit Round Robin is extremely simple it has become an industry standard because it showed that Fair Queuing was possible to implement at very high speeds.
Threaded Indices (SIGCOMM 95): The core idea in our paper is similar to and 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 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: algorithm (Fisk-Varghese) was ported to a prior version of the Snort open-source IDS tool by Mike Fisk. Snort currently uses a Wu-Manber variant. Snort is widely used in the IDS community to screen out worms and other exploits.
SRR Load Balancing (SIGCOMM 96): implemented in Cisco's IOS 11.3(1) (by Dana Blair) as part of Cisco's multilink PPP implementation. MultiLink PPP is often used to make multiple lower costs links have the same effective bandwidth as a higher cost link.
Packet Classification (SIGCOMM 98): Our Wash U algorithms were patented and licensed by Onex.
Compressed Tries: algorithms for OSI Lookups (Patent P6). 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, helped design new lookup and classification algorithms for SwitchOn (sold to PMC for $450 million); member of Technical Board for Jibe Networks (designing load distribution algorithms) and Sanera Systems (designing lookup and striping algorithms, Sanera was recently acquired by McData corporation. Also consulted for AOL, DEC, Intel, STMicroelectronics, Greenfield Networks, Chiaro Networks, and Fujitsu.