Ditto: a system for opportunistic caching in multi-hop wireless networks

ABSTRACT

This paper presents the design, implementation, and evaluation of Ditto, a system that opportunistically caches overheard data to improve subsequent transfer throughput in wireless mesh networks. While mesh networks have been proposed as a way to provide cheap, easily deployable Internet access, they must maintain high transfer throughput to be able to compete with other last-mile technologies. Unfortunately, doing so is difficult because multi-hop wireless transmissions interfere with each other, reducing the available capacity on the network. This problem is particularly severe in common gateway-based scenarios in which nearly all transmissions go through one or a few gateways from the mesh network to the Internet.

Ditto exploits on-path as well as opportunistic caching based on overhearing to improve the throughput of data transfers and to reduce load on the gateways. It uses content-based naming to provide application independent caching at the granularity of small chunks, a feature that is key to being able to cache partially overheard data transfers. Our evaluation of Ditto shows that it can achieve significant performance gains for cached data, increasing throughput by up to 7x over simpler on-path caching schemes, and by up to an order of magnitude over no caching.

REFERENCES

• 1: MAP: Purdue University Wireless Mesh Network Testbed. https://engineering.purdue.edu/MESH.
• 2: Mikhail Afanasyev , David G. Andersen , Alex C. Snoeren, Efficiency through eavesdropping: link-layer packet caching, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.105-118, April 16-18, 2008, San Francisco, California
• 3: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 4: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 5: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In Proc. IEEE INFOCOM, pages 126--134, New York, NY, Mar. 1999.
• 6: Szymon Chachulski , Michael Jennings , Sachin Katti , Dina Katabi, Trading structure for randomness in wireless opportunistic routing, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 7: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060316]
• 8: Saumitra M. Das , Himabindu Pucha , Y. Charlie Hu, Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks, Ad Hoc Networks, v.5 n.6, p.680-703, August, 2007 [doi>10.1016/j.adhoc.2006.11.004]
• 9: T. E. Denehy and W. W. Hsu. Duplicate management for reference data. Research Report RJ10305, IBM, Oct. 2003.
• 10: John R. Douceur , Atul Adya , William J. Bolosky , Dan Simon , Marvin Theimer, Reclaiming Space from Duplicate Files in a Serverless Distributed File System, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.617, July 02-05, 2002
• 11: F. Douglis and A. Iyengar. Application-specific delta-encoding via resemblance detection. In Proceedings of the USENIX Annual Technical Conference, San Antonio, Texas, June 2003.
• 12: 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
• 13: Christos Gkantsidis , Thomas Karagiannis , Milan VojnoviC, Planet scale software updates, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 14: Kyle Jamieson , Hari Balakrishnan, PPR: partial packet recovery for wireless networks, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 15: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 16: Meraki Wireless Network. http://meraki.com/.
• 17: Allen Miu , Hari Balakrishnan , Can Emre Koksal, Improving loss resilience with multi-radio diversity in wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080832]
• 18: Jeffery C. Mogul , Yee Man Chan , Terence Kelly, Design, implementation, and evaluation of duplicate transfer detection in HTTP, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.4-4, March 29-31, 2004, San Francisco, California
• 19: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: 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.
• 21: 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
• 22: Squid Web Proxy Cache. http://www.squid-cache.org/.
• 23: Niraj Tolia , Michael Kaminsky , David G. Andersen , Swapnil Patil, An architecture for internet data transfer, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.19-19, May 08-10, 2006, San Jose, CA
• 24: N. Tolia, M. Kozuch, M. Satyanarayanan, B. Karp, A. Perrig, and T. Bressoud. Opportunistic use of content addressable storage for distributed file systems. In Proc. USENIX Annual Technical Conference, pages 127--140, San Antonio, TX, June 2003.
• 25: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060313]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Design, Experimentation, Performance

Keywords:
mesh networks, multi-hop wireless networks, opportunistic caching, performance, throughput