Packet caches on routers: the implications of universal redundant traffic elimination

ABSTRACT

Many past systems have explored how to eliminate redundant transfers from network links and improve network efficiency. Several of these systems operate at the application layer, while the more recent systems operate on individual packets. A common aspect of these systems is that they apply to localized settings, e.g. at stub network access links. In this paper, we explore the benefits of deploying packet-level redundant content elimination as a universal primitive on all Internet routers. Such a universal deployment would immediately reduce link loads everywhere. However, we argue that far more significant network-wide benefits can be derived by redesigning network routing protocols to leverage the universal deployment. We develop "redundancy-aware" intra- and inter-domain routing algorithms and show that they enable better traffic engineering, reduce link usage costs, and enhance ISPs' responsiveness to traffic variations. In particular, employing redundancy elimination approaches across redundancy-aware routes can lower intra and inter-domain link loads by 10-50%. We also address key challenges that may hinder implementation of redundancy elimination on fast routers. Our current software router implementation can run at OC48 speeds.

REFERENCES

• 1: Netequalizer Bandwidth Shaper. http://www.netequalizer.com/.
• 2: Packeteer WAN optimization solutions. http://www.packeteer.com/.
• 3: Peribit WAN Optimization. http://www.juniper.net/.
• 4: Riverbed Networks. http://www.riverbed.com.
• 5: A. Anand, A. Gupta, A. Akella, S. Seshan, and S. Shenker. Packet Caches on Routers: The Implications of Universal Redundant Traffic Elimination (Extended Version). Technical Report 1636, UW-Madison, June 2008.
• 6: B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights. In Infocom, 2000.
• 7: Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), ACM SIGCOMM Computer Communication Review, v.23 n.4, p.85-95, Oct. 1993
• 8: M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. van der Merwe. Design and implementation of RCP. In NSDI, 2005.
• 9: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 10: U. Erlingsson, M. Manasse, and F. McSherry. A cool and practical alternative to traditional hash tables. In WDAS, 2006.
• 11: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 12: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. In Infocom, 2002.
• 13: Albert Greenberg , Gisli Hjalmtysson , David A. Maltz , Andy Myers , Jennifer Rexford , Geoffrey Xie , Hong Yan , Jibin Zhan , Hui Zhang, A clean slate 4D approach to network control and management, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096541]
• 14: A. Gupta, A. Akella, S. Seshan, S. Shenker, and J. Wang. Understanding and Exploiting Network Traffic Redundancy. Technical Report 1592, UW-Madison, April 2007.
• 15: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 16: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 17: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 18: Robert Morris , Eddie Kohler , John Jannotti , M. Frans Kaashoek, The Click modular router, ACM SIGOPS Operating Systems Review, v.33 n.5, p.217-231, Dec. 1999
• 19: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 20: M. Rabin. Fingerprinting by Random Polynomials. Technical report, Harvard University, 1981. Technical Report, TR-15-81.
• 21: Matthew Roughan , Mikkel Thorup , Yin Zhang, Performance of estimated traffic matrices in traffic engineering, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 22: Sumeet Singh , Cristian Estan , George Varghese , Stefan Savage, Automated worm fingerprinting, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.4-4, December 06-08, 2004, San Francisco, CA
• 23: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 24: Neil T. Spring , David Wetherall, A protocol-independent technique for eliminating redundant network traffic, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.87-95, August 28-September 01, 2000, Stockholm, Sweden
• 25: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.16-31, December 12-15, 1999, Charleston, South Carolina, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Measurement

Keywords:
routing, traffic engineering, traffic redundancy