skip to main content
10.1145/1555349.1555355acmconferencesArticle/Chapter ViewAbstractPublication PagesmetricsConference Proceedingsconference-collections
research-article

Redundancy in network traffic: findings and implications

Published:15 June 2009Publication History

ABSTRACT

A 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 powerful technique to improve the efficiency of network links in the face of repeated data. Many vendors offer such redundancy elimination middleboxes to improve the effective bandwidth of enterprise, data center and ISP links alike.

In this paper, we conduct a large scale trace-driven study of protocol independent redundancy elimination mechanisms, driven by several terabytes of packet payload traces collected at 12 distinct network locations, including the access link of a large US-based university and of 11 enterprise networks of different sizes. Based on extensive analysis, we present a number of findings on the benefits and fundamental design issues in redundancy elimination systems. Two of our key findings are (1) A new redundancy elimination algorithm based on Winnowing that outperforms the widely-used Rabin fingerprint-based algorithm by 5-10% on most traces and by as much as 35% in some traces. (2) A surprising finding that 75-90% of middlebox's bandwidth savings in our enterprise traces is due to redundant byte-strings from within each client's traffic, implying that pushing redundancy elimination capability to the end hosts, i.e. an end-to-end redundancy elimination solution, could obtain most of the middlebox's bandwidth savings.

References

  1. Citrix, application delivery infrastructure. http://www.citrix.com/.Google ScholarGoogle Scholar
  2. Computerworld -- WAN optimization continues growth. www.computerworld.com.au/index.php/id;1174462047;fp;16;fpid;0/.Google ScholarGoogle Scholar
  3. F5 Networks: WAN Delivery Products. http://www.f5.com/.Google ScholarGoogle Scholar
  4. Netequalizer Bandwidth Shaper. http://www.netequalizer.com/.Google ScholarGoogle Scholar
  5. Packeteer WAN optimization solutions. http://www.packeteer.com/.Google ScholarGoogle Scholar
  6. PeerApp: P2P and Media Caching. http://www.peerapp.com.Google ScholarGoogle Scholar
  7. Peribit Networks (Acquired by Juniper in 2005): WAN Optimization Solution. http://www.juniper.net/.Google ScholarGoogle Scholar
  8. Riverbed Networks: WAN Optimization. http://www.riverbed.com/solutions/optimize/.Google ScholarGoogle Scholar
  9. WAN optimization revenues grow 16% -- IT Facts. www.itfacts.biz/wan-optimization--market-to-grow-16/1205/.Google ScholarGoogle Scholar
  10. WAN Optimization: Wikipedia entry. http://en.wikipedia.org/wiki/WAN_Optimization.Google ScholarGoogle Scholar
  11. P. Abry and D. Veitch.Wavelet analysis of long-range dependent traffic. IEEE Transactions on Information Theory, 44(1):2--15, Jan 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. A. Anand, A. Gupta, A. Akella, S. Seshan, and S. Shenker. Packet Caches on Routers: The Implications of Universal Redundant Traffic Elimination. In ACM SIGCOMM, Seattle, WA, Aug. 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. N. Bjorner, A. Blass, and Y. Gurevich. Content-Dependent Chunking for Differential Compression, the Local Maximum Approach. Technical Report 109, Microsoft Research, July 2007.Google ScholarGoogle Scholar
  14. L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In IEEE Infocom, 1999.Google ScholarGoogle ScholarCross RefCross Ref
  15. M. Burrows and D. J.Wheeler. A block-sorting lossless data compression algorithm. Technical report, Digital SRC Research Report, 1994.Google ScholarGoogle Scholar
  16. F. Dogar, A. Phanishayee, H. Pucha, O. Ruwase, and D. Andersen. Ditto -- A System for Opportunistic Caching in Multi-hop Wireless Mesh Networks. In Proc. ACM Mobicom, San Francisco, CA, Sept. 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: a scalable wide-area web cache sharing protocol. In SIGCOMM '98, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. D. Goldenberg, L. Qiu, H. Xie, Y. Yang, and Y. Zhang. Optimizing cost and performance for multihoming. In ACM SIGCOMM, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. X. Li, D. Salyers, and A. Striegel. Improving packet caching scalability through the concept of an explicit end of data marker. In HotWeb, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  20. U. Manber. Finding similar files in a large file system. In USENIX Winter Technical Conference, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. A. Muthitacharoen, B. Chen, and D. Mazières. A low-bandwidth network file system. SIGOPS Oper. Syst. Rev., 35(5), 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. H. Pucha, D. G. Andersen, and M. Kaminsky. Exploiting similarity for multi-source downloads using file handprints. In Proc. 4th USENIX NSDI, Cambridge, MA, Apr. 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. M. Rabin. Fingerprinting by random polynomials. Technical report, Harvard University, 1981. Technical Report, TR-15-81.Google ScholarGoogle Scholar
  24. RouteScience Technologies, Inc. Routescience PathControl. http://www.routescience.com/products.Google ScholarGoogle Scholar
  25. S. Schleimer, D. Wilkerson, and A. Aiken. Winnowing: Local algorithms for document fingerprinting. In SIGMOD, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. N. T. Spring and D. Wetherall. A protocol-independent technique for eliminating redundant network traffic. In SIGCOMM, pages 87--95, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Squid Web Proxy Cache. http://www.squid--cache.org/.Google ScholarGoogle Scholar
  28. A. Wolman et al. On the scale and performance of cooperative Web proxy caching. In ACM Symposium on Operating Systems Principles, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. A. Wolman et al. Organization-based Analysis of Web-Object Sharing and Caching. In Proceedings of the 2nd USITS, Oct 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. J. Ziv and A. Lempel. A universal algorithm for sequential data compression. Information Theory, IEEE Transactions on, 23(3):337--343, 1977.Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Redundancy in network traffic: findings and implications

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        SIGMETRICS '09: Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems
        June 2009
        336 pages
        ISBN:9781605585116
        DOI:10.1145/1555349
        • cover image ACM SIGMETRICS Performance Evaluation Review
          ACM SIGMETRICS Performance Evaluation Review  Volume 37, Issue 1
          SIGMETRICS '09
          June 2009
          320 pages
          ISSN:0163-5999
          DOI:10.1145/2492101
          Issue’s Table of Contents

        Copyright © 2009 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 15 June 2009

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate459of2,691submissions,17%

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader