"Efficient and Reliable Hop-by Flow Control" SIGCOMM 94, IEEE JSAC 95. Credit based flow control that is made reliable using a periodic snapshot and efficient by allowingc credits to be shared among flows in a safe manner. Credit based flow control is widely used in Storage Area Networks such as FiberChannel.
"Efficient Fair Queueing using Deficit Round Robin" SIGCOMM 95 and ACM/IEEE Trans Networking. An efficient O(1) substitute for the O(log(n) sorting bottleneck in Weighted Fair Queuing. Provides throughput fairness only and reasonable (but not optimal) delay bounds. universally deployed.
"Trading Packet Headers for Packet Processing" SIGCOMM 95. Shows how to add indices to packet headers to make lookups efficient. Predates and anticipates tag switching and MPLS.
"Reliable and Efficient Striping". SIGCOMM 96. Showed connections between fair queuing and load balancing protocols using a time-reversal argument. Uses this to develop load balancing protocols that ensure FIFO delivery. Implemented in Cisco IOS
"Leap Forward Virtual Clock: An O(log log N) Queuing Scheme with Guaranteed Delays and Throughput fairness". Infocom 97. Showed that Virtual Clock could be made fair and have the same complexity, delay bounds, and fairness as WFQ.
"Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility" IEEE Trans Networking, Dec 97. Revised from a 1984 SOSP paper; used in Linux and in many router OSes.
"Fast Scalable Routing Lookups". SIGCOMM 97 and ACM TOCS 2000. Describes bimary search on prefix lengths that is still useful for long addresses such as IPv6; has been patented and licensed by industry.
"Faster IP Lookups using Controlled Prefix Expansion". Proceedings of ACM Sigmetrics,Sep 98 and ACM TOCS 99. Another approach to solving the IP lookup problem problem that has been patented and licensed to industry.
"IP Lookups using Multiway and Multicolumn Search". IP Lookups using a Multicolumn Binary Search on addresses and not address lengths. Its main advantage is simplicity and the fact that it is not patented. IEEE/ACM Transactions on Networking.
" Packet Classification using Tuple Space Search". First algorithms for fast packet classification. A bit naive but hardware based tuple-space approaches are making a resurgence. SIGCOMM 99.
"Fast and Scalable Layer 4 Switching". Describes algorithms for fast packet classification. Most noteworthy for a simple algorithm for 2 dimensional packet classification called grid-of-tries.
Packet Classification Using Multidimensional Cutting, Fastest algorithmic classification algorithm we know of and the best alternative to CAMs, used in Cisco routers Proceedings ACM SIGCOMM 2003
Tree bitmap: Hardware Software IP Lookups with Incremental Updates, W. Eatherton, Z. Dittia, and George Varghese, Best compressed IP lookup algorithm we know of, used in Cisco CRS-1, ACM CCR, 2004.
Leaping Multiple Headers in a Single Bound: Wire Speed Parsing using the Kangaroo System, C. Kozanitis, J. Huber, S. Singh G. Varghese, Introduces the new problem of flexible parsing. While OpenFlow allows the control plane to change based on software control, flexible parsing allows part of the data plane to also change in particular to allow routers to process new protocols after deployment. INFOCOM 2010