Virtual Ring Routing: Network Routing Inspired by DHTs

Caesar et al

distributed hashtable network routing

@inproceedings{caesar:sigcomm-2006,
  title={Virtual Ring Routing: Network Routing Inspired by {DHTs}},
  author={Caesar, M. and Castro, M. and Nightingale, E.B. and
          O'Shea, G. and Rowstron, A.},
  booktitle={{ACM} {SIGCOMM} Computer Communication Review},
  volume={36},
  number={4},
  pages={351--362},
  year={2006},
  publisher={{ACM}}
}

Virtual Ring Routing: Network Routing Inspired by DHTs. Caesar, Castro, Nightingale, O'Shea, Rowstron. SIGCOMM 2006.

• VRR is a combination ad hoc routing protocol and distributed hash table overlay.
• It routes and forwards over location independent addresses; it does not require an underlying IP layer (for either addressing or forwarding).
• Nodes periodically send out beacons to determine local neighborhood.
• Nodes maintain a list of physical neighbors, as well as a small set of nearby virtual neighbors in the ID space.
• Forwarding is along the physical neighbors toward the known node w/ID closest to the target ID. Notably, this is down in greedy fashion. That's not so rare for some DHTs, notably CAN seems similar, but now the underlying multihop network layer routing as also being done in the same fashion.
• Despite this, the comprehensive-sounding testing in the paper indicates it's a winner.
• Possible lesson from this is that more often than not, by the time you establish the best route, you could have already delivered the message along any rout.
• It's not clear how this fares under links w/ high latency, packet loss, or heterogeneity.
• Also not clear how brittle the protocol is and what the bounds are on node state, among other things.