skip to main content
10.1145/1159913.1159954acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
Article
Free access

Virtual ring routing: network routing inspired by DHTs

Published: 11 August 2006 Publication History

Abstract

This paper presents Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer. VRR provides both raditional point-to-point network routing and DHT routing to the node responsible for a hash table key.VRR can be used with any link layer technology but this paper describes a design and several implementations of VRR that are tuned for wireless networks. We evaluate the performance of VRR using simulations and measurements from a sensor network and an 802.11a testbed. The experimental results show that VRR provides robust performance across a wide range of environments and workloads. It performs comparably to, or better than, the best wireless routing protocol in each experiment. VRR performs well because of its unique features: it does not require network flooding or trans-lation between fixed identifiers and location-dependent addresses.

References

[1]
ns-2 network simulator. http://www.isi.edu/nsnam/ns/.
[2]
J.-Y. Le Boudec and M. Vojnovic. Perfect simulation and stationarity of a class of mobility models. In Infocom, 2005.
[3]
J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Mobicom, October 1998.
[4]
M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. Wallach. Secure routing for structured peer-to-peer overlay networks. In OSDI, December 2002.
[5]
B. Chen and R. Morris. L+: scalable landmark routing and address lookup for multi-hop wireless networks. In Technical Report 837, MIT LCS, March 2002.
[6]
T. Clausen and P. Jacquet. OLSR RFC3626, October 2003. http://ietf.org/rfc/rfc3626.txt.
[7]
D. De Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In Mobicom, 2003.
[8]
F. Delmastro. From Pastry to CrossROAD: Cross-layer ring overlay for ad hoc networks. In PerCom Workshops, 2005.
[9]
J. Douceur. The sybil attack. In IPTPS, March 2002.
[10]
R. Draves, J. Padhye, and B. Zill. Comparison of routing metrics for static multi-hop wireless networks. In SIGCOMM, August 2004.
[11]
R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In Mobicom, September 2004.
[12]
J. Dunagan, N. Harvey, M. Jones, D. Kostic, M. Theimer, and A. Wolman. Fuse: Lightweight guaranteed distributed failure notification. In OSDI, December 2004.
[13]
J. Eriksson, M. Faloutsos, and S. Krishnamurthy. Peernet: Pushing peer-to-peer down the stack. In IPTPS, February 2003.
[14]
R. Fonseca. Personal communication.
[15]
R. Fonseca, S. Ratnasamy, J. Zhao, C. Ee, D. Culler, S. Shenker, and I. Stoica. Beacon vector routing: Scalable point-to-point in wireless sensornets. In NSDI, May 2005.
[16]
B. Ford. Unmanaged Internet Protocol: Taming the edge network management crisis. In HotNets II, November 2003.
[17]
D. Gay, P. Levis, R. vonBehren, M. Welsh, E. Brewer, and D. Culler. The nesC Language: A Holistic Approach to Networked Embedded Systems. In PLDI, June 2003.
[18]
Z. J. Haas and M. R. Pearlman. The zone routing protocol (ZRP) for ad hoc networks. July 2002. Internet-draft, draft-ietf-manet-zone-zrp-04.txt.
[19]
A. Haeberlen, J. Hoye, A. Mislove, and P. Druschel. Consistent Key Mapping in Structured Overlays. In Technical Report TR05-456, Rice CS department, August 2005.
[20]
J. Hill and D. Culler. Mica: A wireless platform for deeply embedded networks. IEEE Micro, 2002.
[21]
Y. Hu, H. Pucha, and S. Das. Exploiting the synergy between peer- to-peer and mobile ad-hoc networks. In Hot-OS IX, May 2003.
[22]
D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In Ad Hoc Networking, 2001.
[23]
D.B. Johnson and D.A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353, 1996.
[24]
B. Karp and H. Kung. Greedy perimeter stateless routing for wireless networks. In Mobicom, August 2000.
[25]
P. Key and G. Cope. Distributed Dynamic Routing Schemes. IEEE Communications Magazine, October 1990.
[26]
Y-J Kim, R. Govindan, B. Karp, and S. Shenker. Geographic routing made practical. In NSDI, May 2005.
[27]
P. Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer, and D. Culler. The Emergence of Networking Abstractions and Techniques in TinyOS. In NSDI, March 2004.
[28]
J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris. A scalable location service for geographic ad-hoc routing. In Mobicom, August 2000.
[29]
P. Maymounkov and D. Mazères. Kademlia: A Peer-to-peer Information System. In IPTPS, 2002.
[30]
R. Moskowitz, P. Nikander, P. Jokela, and T. Henderson. Host identity protocol (HIP), 2004. draft-moskowitz-hip-08.txt.
[31]
S. Murthy and J.J. Garcia-Luna-Aceves. An efficient routing protocol for wireless networks. In Mobile Networks and Applications, 1996.
[32]
V. Park and M. Corson. Temporally-ordered routing algorithm (TORA) version 1: Functional specification. July 2001. Internet-draft, draft- etf-manet-tora-spec-04.txt.
[33]
G. Pei, M. Gerla, and X. Hong. LANMAR: Landmark routing for large scale wireless ad hoc networks with group mobility. In MobiHoc, 2000.
[34]
C. Perkins and P. Bhagwat. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In Sigcomm, August 1994.
[35]
C. Perkins and E. Royer. Ad hoc on-demand distance vector routing. In Mobile Computing Systems and Applications, February 1999.
[36]
H. Pucha, S. M. Das, and Y. C. Hu. Imposed route reuse in ad hoc network routing protocols using structured peer-to-peer overlay routing. IEEE Transactions on Parallel and Distributed Systems (to appear), 2006.
[37]
V. Ramasubramanian, Z. Haas, and E. Sirer. SHARP: A hybrid adaptive routing protocol for mobile ad hoc networks. In Mobihoc, June 2003.
[38]
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Sigcomm, August 2001.
[39]
A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Middleware, November 2001.
[40]
I. Stoica, R. Morris, D. Karger, M. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Sigcomm, August 2001.
[41]
A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. In SenSys, November 2003.
[42]
J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Infocom, 2003.
[43]
T. Zahn and J. Schiller. MADPastry: A DHT substrate for practicably sized MANETs. In ASWN, June 2005.
[44]
B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: an infrastructure for fault-resilient wide-area location and routing. In Technical report UCB//CSD-01-1141, U.C. Berkeley, April 2001.

Cited By

View all
  • (2023)A Novel Data Placement and Retrieval Service for Cooperative Edge CloudsIEEE Transactions on Cloud Computing10.1109/TCC.2021.307622911:1(71-84)Online publication date: 1-Jan-2023
  • (2022)Intelligent Water Drops Algorithm-Based Aggregation in Heterogeneous Wireless Sensor NetworkJournal of Sensors10.1155/2022/60993302022(1-12)Online publication date: 28-Sep-2022
  • (2020)On Virtual Id Assignment in Networks for High Resilience Routing: A Theoretical FrameworkGLOBECOM 2020 - 2020 IEEE Global Communications Conference10.1109/GLOBECOM42002.2020.9322538(1-6)Online publication date: 7-Dec-2020
  • Show More Cited By

Index Terms

  1. Virtual ring routing: network routing inspired by DHTs

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications
    September 2006
    458 pages
    ISBN:1595933085
    DOI:10.1145/1159913
    • cover image ACM SIGCOMM Computer Communication Review
      ACM SIGCOMM Computer Communication Review  Volume 36, Issue 4
      Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications
      October 2006
      445 pages
      ISSN:0146-4833
      DOI:10.1145/1151659
      Issue’s Table of Contents
    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: 11 August 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. distributed hash table
    2. network routing
    3. wireless

    Qualifiers

    • Article

    Conference

    SIGCOMM06
    Sponsor:
    SIGCOMM06: ACM SIGCOMM 2006 Conference
    September 11 - 15, 2006
    Pisa, Italy

    Acceptance Rates

    Overall Acceptance Rate 462 of 3,389 submissions, 14%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)86
    • Downloads (Last 6 weeks)13
    Reflects downloads up to 12 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A Novel Data Placement and Retrieval Service for Cooperative Edge CloudsIEEE Transactions on Cloud Computing10.1109/TCC.2021.307622911:1(71-84)Online publication date: 1-Jan-2023
    • (2022)Intelligent Water Drops Algorithm-Based Aggregation in Heterogeneous Wireless Sensor NetworkJournal of Sensors10.1155/2022/60993302022(1-12)Online publication date: 28-Sep-2022
    • (2020)On Virtual Id Assignment in Networks for High Resilience Routing: A Theoretical FrameworkGLOBECOM 2020 - 2020 IEEE Global Communications Conference10.1109/GLOBECOM42002.2020.9322538(1-6)Online publication date: 7-Dec-2020
    • (2020)Implementation of Multipath-Based Multicast Routing Protocol in Hierarchical Wireless Sensor NetworkAdvances in Data Science and Management10.1007/978-981-15-0978-0_34(345-354)Online publication date: 14-Jan-2020
    • (2019)Dynamic and Scalable Control as a Foundation for Future NetworksEmerging Automation Techniques for the Future Internet10.4018/978-1-5225-7146-9.ch008(208-230)Online publication date: 2019
    • (2019)BPIIoT: A Light-Weighted Blockchain-Based Platform for Industrial IoTIEEE Access10.1109/ACCESS.2019.29142237(58381-58393)Online publication date: 2019
    • (2018)P2P Over MANET: A Review and Its Conceptual Framework2018 Fifth International Conference on Parallel, Distributed and Grid Computing (PDGC)10.1109/PDGC.2018.8745856(48-53)Online publication date: Dec-2018
    • (2018)Autonomous Edge Resource Organization with Smallcell Integration in 5G2018 IEEE International Conference on Communications Workshops (ICC Workshops)10.1109/ICCW.2018.8403593(1-6)Online publication date: May-2018
    • (2018)Challenges and Protocols for P2P applications in Multi-hop Wireless Networks2018 Second International Conference on Computing Methodologies and Communication (ICCMC)10.1109/ICCMC.2018.8487911(310-316)Online publication date: Feb-2018
    • (2018)Some Improvements in VCP for Data Traffic Reduction in WSNAdvances in Internet, Data & Web Technologies10.1007/978-3-319-75928-9_63(711-722)Online publication date: 24-Feb-2018
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media