Three Hops Overlay Routing

Patrick Lee and Hans-Arno Jacobsen.

MSRG, University of Toronto, July 2010.


Improvement in datacenter networks will enable architects to built larger distributed systems. However, standard distributed system architectures and their resulting communication patterns are incapable of supporting systems much larger than the current limits. This paper describes the design and evaluation of an overlay topology and messaging infrastructure that can be used for creating datacenter-scale distributed systems. The topology provides sufficient scalability to accommodate future datacenter growth. Theoretical analysis suggests its fault resiliency and network capability are unmatched by other common network topologies. The messaging infrastructure build on top of this topology supports incremental scaling, node failure recovery and flexible routing. Properties of the topology ensure that the overlay has constant bounded delay and bandwidth usage, which are useful for planning incremental deployment while guaranteeing performance. Finally, evaluation of our overlay prototype reveals usage trends that best matches the characteristics of our overlay


Related Projects

Tags: overlay, routing

Readers who enjoyed the above work, may also like the following:

  • OMen: Overlay Mending for Topic-based Publish/Subscribe Systems Under Churn.
    Chen Chen, Roman Vitenberg , and Hans-Arno Jacobsen.
    In Proceedings of the 10th ACM International Conference on Distributed and Event-Based Systems (DEBS 2016), June 2016.
    Best Paper Award.
    Tags: pub/sub, overlay
  • Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints.
    Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.
    In Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS), Nara, Japan, June 2016.
    Acceptance rate: 17.6%. 68 papers accepted out of 386 submissions.
    Tags: icdcs16, overlay, pub/sub
  • Weighted Overlay Design for Topic-based Publish/Subscribe on Geo-Distributed Data Centers.
    Chen Chen, Yoav Tock, Hans-Arno Jacobsen, and Roman Vitenberg.
    In Proceedings of the 35th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 474-485, July 2015.
    Acceptance rate: 13%. 70 papers accepted out of 543 submissions..
    Tags: icdcs15, overlay, pub/sub