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


[PostScript (1922KB)] [Gzipped PostScript (337KB)] [PDF (378KB)]