research-article

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

Authors:

Fahad R. Dogar,

Amar Phanishayee,

Himabindu Pucha,

Olatunji Ruwase,

David G. AndersenAuthors Info & Claims

MobiCom '08: Proceedings of the 14th ACM international conference on Mobile computing and networking

Pages 279 - 290

https://doi.org/10.1145/1409944.1409977

Published: 14 September 2008 Publication History

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.

Digital Library

[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.

Digital Library

[4]

S. Biswas and R. Morris. ExOR: opportunistic multi-hop routing for wireless networks. In Proc. ACM SIGCOMM, Philadelphia, PA, Aug. 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[13]

C. Gkantsidis, T. Karagiannis, P. Rodriguez, and M. Vonjović. Planet scale software updates. In Proc. ACM SIGCOMM, Pisa, Italy, Aug. 2006.

Digital Library

[14]

K. Jamieson and H. Balakrishnan. PPR: Partial packet recovery for wireless networks. In Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[21]

N. T. Spring and D. Wetherall. A protocol-independent technique for eliminating redundant network traffic. In Proc. ACM SIGCOMM, Stockholm, Sweden, Sept. 2000.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Gong J(2021)RETRACTED ARTICLE: Redundant data high-efficiency compression based on distributed parallel algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-06141-125:20(13039-13051)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00500-021-06141-1
Ma NDiao M(2019)CoFi: Coding-Assisted File Distribution over a Wireless LANSymmetry10.3390/sym1101007111:1(71)Online publication date: 10-Jan-2019
https://doi.org/10.3390/sym11010071
Dogar F(2018)Towards Slack-Aware NetworkingACM SIGCOMM Computer Communication Review10.1145/3213232.321323648:2(24-30)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1145/3213232.3213236
Show More Cited By

Index Terms

Ditto: a system for opportunistic caching in multi-hop wireless networks
1. Networks
  1. Network components
  2. Network types

Recommendations

Inter-AP coordination for fair throughput in infrastructure-based IEEE 802.11 mesh networks
IWCMC '06: Proceedings of the 2006 international conference on Wireless communications and mobile computing

This paper studies throughput fairness among different basic service sets (BSSs) in infrastructure-based IEEE 802.11 mesh networks, where inter-BSS interference is unavoidable because of the difficulty in frequency and coverage planning and the limited ...
An analytical flow control scheme for real-time traffic in wireless mesh network: from theoretic model to practical mechanism
Mobility '07: Proceedings of the 4th international conference on mobile technology, applications, and systems and the 1st international symposium on Computer human interaction in mobile technology

The link interference and multi-hop characters make Wireless Mesh Network (WMN) performance can not be tuned well by local information. We propose an analytical flow control scheme (AFCS) based on the optimal bandwidth allocation model that is ...
An experimental study of small multi-hop wireless networks using chirp spread spectrum

Wireless mesh networks have emerged as a viable means of communicating between points that are not within wireless range of each other. There are still, however, a number of challenges involved in designing and implementing such wireless multi-hop ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiCom '08: Proceedings of the 14th ACM international conference on Mobile computing and networking

September 2008

374 pages

ISBN:9781605580968

DOI:10.1145/1409944

General Chair:
J. J. Garcia-Luna-Aceves
University of California, Santa Cruz, USA & Palo Alto Research Center, USA
,
Program Chairs:
Raghupathy Sivakumar
Georgia Institute of Technology, USA
,
Peter Steenkiste
Carnegie Mellon University, USA

Copyright © 2008 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiCom08

Sponsor:

MobiCom08: Annual International Conference on Mobile Computing and Networking

September 14 - 19, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
851
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gong J(2021)RETRACTED ARTICLE: Redundant data high-efficiency compression based on distributed parallel algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-06141-125:20(13039-13051)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00500-021-06141-1
Ma NDiao M(2019)CoFi: Coding-Assisted File Distribution over a Wireless LANSymmetry10.3390/sym1101007111:1(71)Online publication date: 10-Jan-2019
https://doi.org/10.3390/sym11010071
Dogar F(2018)Towards Slack-Aware NetworkingACM SIGCOMM Computer Communication Review10.1145/3213232.321323648:2(24-30)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1145/3213232.3213236
He SShen HSoundararaj VYu L(2018)Cloud Assisted Traffic Redundancy Elimination for Power Efficiency in Smartphones2018 IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)10.1109/MASS.2018.00060(371-379)Online publication date: Oct-2018
https://doi.org/10.1109/MASS.2018.00060
Haq ORaja MDogar FBarrett RCummings RAgichtein EGabrilovich E(2017)Measuring and Improving the Reliability of Wide-Area Cloud PathsProceedings of the 26th International Conference on World Wide Web10.1145/3038912.3052560(253-262)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3038912.3052560
Shen HHe SYu LSarker A(2017)Prediction-based redundant data elimination with content overhearing in wireless networks2017 IEEE International Conference on Pervasive Computing and Communications (PerCom)10.1109/PERCOM.2017.7917850(50-58)Online publication date: Mar-2017
https://doi.org/10.1109/PERCOM.2017.7917850
Bornholt JKaufmann ALi JKrishnamurthy ATorlak EWang X(2016)Specifying and Checking File System Crash-Consistency ModelsACM SIGARCH Computer Architecture News10.1145/2980024.287240644:2(83-98)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2980024.2872406
Prasad AGopinath K(2016)Prudent Memory Reclamation in Procrastination-Based SynchronizationACM SIGARCH Computer Architecture News10.1145/2980024.287240544:2(99-112)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2980024.2872405
Chen YChen YCao QYang X(2016)PacketCloud: A Cloudlet-Based Open Platform for In-Network ServicesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.242422227:4(1146-1159)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2424222
Ajayi AEdwards CRoedig U(2016)A Distributed Caching Approach for Improved Data Availability in Rural Wireless Mesh Networks2016 International Conference on Computational Science and Computational Intelligence (CSCI)10.1109/CSCI.2016.0175(904-910)Online publication date: Dec-2016
https://doi.org/10.1109/CSCI.2016.0175
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents