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. M. Afanasyev, D. G. Andersen, and A. C. Snoeren. Efficiency through eavesdropping: Link-layer packet caching. In Proc. 5th USENIX NSDI, San Francisco, CA, Apr. 2008.
3. J. Bicket, D. Aguayo, S. Biswas, and R. Morris. Architecture and evaluation of an unplanned 802.11b mesh network. In Proc. ACM Mobicom, Cologne, Germany, Sept. 2005.
4. S. Biswas and R. Morris. ExOR: opportunistic multi-hop routing for wireless networks. In Proc. ACM SIGCOMM, Philadelphia, PA, Aug. 2005.
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. S. Chachulski, M. Jennings, S. Katti, and D. Katabi. Trading structure for randomness in wireless opportunistic routing. In Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007.
7. L. P. Cox, C. D. Murray, and B. D. Noble. Pastiche: Making backup cheap and easy. In Proc. 5th USENIX OSDI, Boston, MA, Dec. 2002.
8. S. M. Das, H. Pucha, and C. Y. Hu. Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks. Ad Hoc Networks (Elsevier) Journal, Special Issue on Wireless Mesh Networks, 2007, 2007.
9. T. E. Denehy and W. W. Hsu. Duplicate management for reference data. Research Report RJ10305, IBM, Oct. 2003.
10. J. R. Douceur, A. Adya, W. J. Bolosky, D. Simon, and M. Theimer. Reclaiming space from duplicate files in a serverless distributed file system. In Proc. 22nd Intl. Conf on Distributed Computing Systems, Vienna, Austria, July 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. L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: A scalable wide-area Web cache sharing protocol. In Proc. ACM SIGCOMM, pages 254--265, Vancouver, British Columbia, Canada, Sept. 1998.
13. C. Gkantsidis, T. Karagiannis, P. Rodriguez, and M. Vonjović. Planet scale software updates. In Proc. ACM SIGCOMM, Pisa, Italy, Aug. 2006.
14. K. Jamieson and H. Balakrishnan. PPR: Partial packet recovery for wireless networks. In Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007.
15. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Mèdard, and J. Crowcroft. XORs in the air: practical wireless network coding. In Proc. ACM SIGCOMM, pages 243--254, Pisa, Italy, Aug. 2006.
16. Meraki Wireless Network. http://meraki.com/.
17. A. K. Miu, H. Balakrishnan, and C. E. Koksal. Improving loss resilience with multi-radio diversity in wireless networks. In Proc. ACM Mobicom, Cologne, Germany, Sept. 2005.
18. J. C. Mogul, Y. M. Chan, and T. Kelly. Design, implementation, and evaluation of duplicate transfer detection in HTTP. In Proc. First Symposium on Networked Systems Design and Implementation (NSDI), San Francisco, CA, Mar. 2004.
19. A. Muthitacharoen, B. Chen, and D. Mazieres. A low-bandwidth network file system. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP), Banff, Canada, Oct. 2001.
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. N. T. Spring and D. Wetherall. A protocol-independent technique for eliminating redundant network traffic. In Proc. ACM SIGCOMM, Stockholm, Sweden, Sept. 2000.
22. Squid Web Proxy Cache. http://www.squid-cache.org/.
23. N. Tolia, M. Kaminsky, D. G. Andersen, and S. Patil. An architecture for Internet data transfer. In Proc. 3rd Symposium on Networked Systems Design and Implementation (NSDI), San Jose, CA, May 2006.
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. B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In Proc. 5th USENIX OSDI, pages 255--270, Boston, MA, Dec. 2002.

Index Terms

• Networks

  • Network components

  • Network types

    • Mobile networks

    • Public Internet

    • Wireless access networks