Redundancy in network traffic: findings and implications

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/.
• 2: Computerworld -- WAN optimization continues growth. www.computerworld.com.au/index.php/id;1174462047;fp;16;fpid;0/.
• 3: F5 Networks: WAN Delivery Products. http://www.f5.com/.
• 4: Netequalizer Bandwidth Shaper. http://www.netequalizer.com/.
• 5: Packeteer WAN optimization solutions. http://www.packeteer.com/.
• 6: PeerApp: P2P and Media Caching. http://www.peerapp.com.
• 7: Peribit Networks (Acquired by Juniper in 2005): WAN Optimization Solution. http://www.juniper.net/.
• 8: Riverbed Networks: WAN Optimization. http://www.riverbed.com/solutions/optimize/.
• 9: WAN optimization revenues grow 16% -- IT Facts. www.itfacts.biz/wan-optimization--market-to-grow-16/1205/.
• 10: WAN Optimization: Wikipedia entry. http://en.wikipedia.org/wiki/WAN_Optimization.
• 11: P. Abry and D. Veitch.Wavelet analysis of long-range dependent traffic. IEEE Transactions on Information Theory, 44(1):2--15, Jan 1998.
• 12: Ashok Anand , Archit Gupta , Aditya Akella , Srinivasan Seshan , Scott Shenker, Packet caches on routers: the implications of universal redundant traffic elimination, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 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.
• 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.
• 15: M. Burrows and D. J.Wheeler. A block-sorting lossless data compression algorithm. Technical report, Digital SRC Research Report, 1994.
• 16: Fahad R. Dogar , Amar Phanishayee , Himabindu Pucha , Olatunji Ruwase , David G. Andersen, Ditto: a system for opportunistic caching in multi-hop wireless networks, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409977]
• 17: 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
• 18: David K. Goldenberg , Lili Qiuy , Haiyong Xie , Yang Richard Yang , Yin Zhang, Optimizing cost and performance for multihoming, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 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.
• 20: 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
• 21: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 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.
• 23: M. Rabin. Fingerprinting by random polynomials. Technical report, Harvard University, 1981. Technical Report, TR-15-81.
• 24: RouteScience Technologies, Inc. Routescience PathControl. http://www.routescience.com/products.
• 25: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 26: 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
• 27: Squid Web Proxy Cache. http://www.squid--cache.org/.
• 28: 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
• 29: Alec Wolman , Geoff Voelker , Nitin Sharma , Neal Cardwell , Molly Brown , Tashana Landray , Denise Pinnel , Anna Karlin , Henry Levy, Organization-based analysis of web-object sharing and caching, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.3-3, October 11-14, 1999, Boulder, Colorado
• 30: J. Ziv and A. Lempel. A universal algorithm for sequential data compression. Information Theory, IEEE Transactions on, 23(3):337--343, 1977.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

General Terms:
Algorithms, Measurement

Keywords:
traffic engineering, traffic redundancy