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 to the thousands," 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.
The only requirement for this system is Java 6.
To build, run make. The main class is RonTest. make jar generates a
class jar for easy deployment.
To run the system in a non-distributed simulation mode, refer to the
runsim.bash and sim.rb scripts.
The tool to regenerate the message type source code is object-codegen and is
found here:
https://assorted.svn.sourceforge.net/svnroot/assorted/object-codegen/trunk/src
Instead of adopting a serialization framework such as Protocol Buffers, we chose to exercise greater control over a simpler serialization format.
More detailed documentation regarding system usage (invocation parameters) and simulation tooling are forthcoming, as is API documentation.
Eventually we will also release our PlanetLab-based experiment orchestration code to facilitate experiment re-creation.
The reactor framework has been refactored out of this codebase into a separate project, but this change has not yet been reflected in the current code.
- David Andersen (CMU)
- David Karger (MIT)
- Amar Phanishayee (CMU)
- David Sontag (MIT)
- Yang Zhang (MIT)