Ashok Anand
Scott Shenker
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.
- Netequalizer Bandwidth Shaper. http://www.netequalizer.com/.Google Scholar
- Packeteer WAN optimization solutions. http://www.packeteer.com/.Google Scholar
- Peribit WAN Optimization. http://www.juniper.net/.Google Scholar
- Riverbed Networks. http://www.riverbed.com.Google Scholar
- 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.Google Scholar
- B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights. In Infocom, 2000.Google ScholarCross Ref
- T. Ballardie, P. Francis, and J. Crowcroft. Core based trees (CBT). SIGCOMM Comput. Commun. Rev., 23(4):85--95, 1993. Google ScholarDigital Library
- M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. van der Merwe. Design and implementation of RCP. In NSDI, 2005.Google Scholar
- B. Davie and Y. Rekhter. MPLS: technology and applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2000. Google ScholarDigital Library
- U. Erlingsson, M. Manasse, and F. McSherry. A cool and practical alternative to traditional hash tables. In WDAS, 2006.Google Scholar
- L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: a scalable wide-area Web cache sharing protocol. In ACM SIGCOMM, 1998. Google ScholarDigital Library
- B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. In Infocom, 2002.Google ScholarDigital Library
- A. Greenberg, G. Hjalmtysson, D. A. Maltz, A. Myers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang. A clean slate 4D approach to network control and management. SIGCOMM Comput. Commun. Rev., 35(5):41--54, 2005. Google ScholarDigital Library
- A. Gupta, A. Akella, S. Seshan, S. Shenker, and J. Wang. Understanding and Exploiting Network Traffic Redundancy. Technical Report 1592, UW-Madison, April 2007.Google Scholar
- S. Kandula, D. Katabi, B. Davie, and A. Charny. Walking the tightrope: responsive yet stable traffic engineering. In ACM SIGCOMM, 2005. Google ScholarDigital Library
- U. Manber. Finding similar files in a large file system. In USENIX Winter Technical Conference, 1994. Google ScholarDigital Library
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic matrix estimation: existing techniques and new directions. In ACM SIGCOMM, 2002. Google ScholarDigital Library
- R. Morris, E. Kohler, J. Jannotti, and M. F. Kaashoek. The Click modular router. SIGOPS Oper. Syst. Rev., 33(5):217--231, 1999. Google ScholarDigital Library
- A. Muthitacharoen, B. Chen, and D. Mazières. A low-bandwidth network file system. SIGOPS Oper. Syst. Rev., 35(5), 2001. Google ScholarDigital Library
- M. Rabin. Fingerprinting by Random Polynomials. Technical report, Harvard University, 1981. Technical Report, TR-15-81.Google Scholar
- M. Roughan, M. Thorup, and Y. Zhang. Performance of estimated traffic matrices in traffic engineering. In ACM SIGMETRICS, 2003. Google ScholarDigital Library
- S. Singh, C. Estan, G. Varghese, and S. Savage. Automated worm fingerprinting. In OSDI, 2004. Google ScholarDigital Library
- N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP Topologies with Rocketfuel. In ACM SIGCOMM, 2002. Google ScholarDigital Library
- N. Spring and D. Wetherall. A protocol-independent technique for eliminating redundant network traffic. In ACM SIGCOMM, 2000. Google ScholarDigital Library
- A. Wolman et al. On the scale and performance of cooperative Web proxy caching. In ACM Symposium on Operating Systems Principles, 1999. Google ScholarDigital Library
Index Terms
- Packet caches on routers: the implications of universal redundant traffic elimination
Recommendations
Redundancy in network traffic: findings and implications
SIGMETRICS '09: Proceedings of the eleventh international joint conference on Measurement and modeling of computer systemsA large amount of popular content is transferred repeatedly across network links in the Internet. In recent years, protocol-independent redundancy elimination, which can remove duplicate strings from within arbitrary network flows, has emerged as a ...
Packet caches on routers: the implications of universal redundant traffic elimination
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 ...
Redundancy in network traffic: findings and implications
SIGMETRICS '09A large amount of popular content is transferred repeatedly across network links in the Internet. In recent years, protocol-independent redundancy elimination, which can remove duplicate strings from within arbitrary network flows, has emerged as a ...
Comments