Warning: session_start() [function.session-start]: open(/var/lib/php/sessions/sigcomm/sess_2509fc8d586e2f43c67345f6fdada0c3, O_RDWR) failed: Permission denied (13) in /acminfo/2/sigs/sigcomm/conferences/sigcomm/2006/discussion/functions.php on line 2

Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /acminfo/2/sigs/sigcomm/conferences/sigcomm/2006/discussion/functions.php:2) in /acminfo/2/sigs/sigcomm/conferences/sigcomm/2006/discussion/functions.php on line 2

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /acminfo/2/sigs/sigcomm/conferences/sigcomm/2006/discussion/functions.php:2) in /acminfo/2/sigs/sigcomm/conferences/sigcomm/2006/discussion/functions.php on line 2
Sigcomm 2006 Form >> Virtual Ring Routing: Network Routing Inspired by DHTs ;

Virtual Ring Routing: Network Routing Inspired by DHTs

View PaperPublic Review (by Brad Karp)

Matthew Caesar, University of California, Berkeley
Miguel Castro, Microsoft Research
Edmund B. Nightingale, University of Michigan, Ann Arbor
Gerg O, Microsoft Research
Antony Rowstron, Microsoft Research

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 traditional 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 translation between fixed identifiers and location-dependent addresses.


  1. Posted by Paul Tarjan on Friday August 18, 12:23pm
    Posted by vg96:

    You are not as unique or innovative as you’ve been led to think. Your key to independent routing is the combination of local links and a “global” ring. A ring allows efficient insertion/deletion like doubly-linked lists, but yields only a flat address space. To scale, you need to link up these elements in a hierarchy of some sort, turning it into a hierarchical address space. The hierarchy of rings would be a routing structure like each of your rings, and would again depend on the combination of local links to lower level rings and its (hierarchy’s) “global” structure. However, the hierarchy can be at least equally efficiently extended down to the leaf nodes, and provides hierarchical addressing of its own with almost no coordination compared to IP again because of the locality of each link, i.e. just like in your ring’s flat address space, but more scalably.

    [This larger scheme was anticipated 7 years earlier by one person working only in spare time from regular mundane work, with almost no funding and no resources, and hence has remained below the Sigcomm radar… See US Patent 6802068 filed 1999, best paper at IEEE ECUMN 2000, and thesis “Canonical simplification of networking and the Internet”, Columbia Univ 2005. Yes, it’s self-glorification, but someone has to do it :) ]
  2. Posted by Muneeb Ali on Monday August 28, 7:06pm
    Well i would not be as aggressive as the above comment (I think VRR is a nice paper and I have been a supporter of using DHT in sensor-nets for quite some time) but I do have my reservations against the novelty of the idea. At the very least there should have been more literature search done. If you type in DHT and "sensor networks" the FIRST hit on google is my conference talk of this paper http://dx.doi.org/10.1109/DNSR.2004.1344725

    which is the paper on CSN - "Chord for Sensor Networks" and the paper goes deep into the arguments mentioned above in the comment about "hierarchy of rings" and how to form topolgy-dependant DHT rings in a way that it makes sense for energy-constraint sensor nodes

  3. Posted by Jon Crowcroft on Friday September 15, 3:18am
    Lots of people have thought of p2p+manet (and p2p+dtn) - the trick is to think of a scalable routing system - this paper does a nice job because it imports the idea from landmark hierarchy (paul francis of cornell did this when at bellcore and in part in his thesis in 1988) - but combining _that_ with DHT and then applying it is definitely new....

    btw, unstructured techniques for ad hoc routing goes back to arpa packet radio work in late 1970s, but noone had structured techniques (although they did have hierarchies) - \

    anyhow, this is a cool paper and has nice evaluation (and a major first for Microsoft, as far as I am aware) in that the researchers were allowed (and annouced this at the end of their presentation) to release the code!!! so now they can behave more "like us"

    [truth in advertising: I am a member of their technical advisory board]

Login to post a comment

Warning: Unknown(): open(/var/lib/php/sessions/sigcomm/sess_2509fc8d586e2f43c67345f6fdada0c3, O_RDWR) failed: Permission denied (13) in Unknown on line 0

Warning: Unknown(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php/sessions/sigcomm) in Unknown on line 0