Scalable Resilient Overlay Networks
The SRON project is a collaboration between researchers from MIT and
CMU to make Resilient Overlay Networks scale up to hundreds of nodes by applying a novel distributed algorithm for efficient (near-optimal) one-hop link-state routing in such full-mesh networks as RONs. Prior techniques for this setting scale poorly, as each node incurs quadratic communication overhead to broadcast its link state to all other nodes. In contrast, in our algorithm each node exchanges routing state with only a small subset of overlay nodes determined by using a quorum system. Using a two-round protocol, each node can find an optimal one-hop path to any other node using only n-root-n per-node communication. Our algorithm can also be used to find the optimal shortest-path of arbitrary length using n-root-n-log-n per-node communication. The algorithm is designed to be resilient to both node and link failures.
For more details, please refer to our paper, Scaling All-Pairs
Overlay Routing, which appears
in CoNext
2009. This codebase is the published system that was developed
to prototype and experimentally evaluate the algorithm
on PlanetLab. It also
contains simulation-driving code for operating the system in a
non-distributed setting.
Download code from
source repository
People
[PostScript
(1922KB)]
[Gzipped PostScript
(337KB)]
[PDF (378KB)]