Scaling Construction of Low Fan-out Overlays for Topic-based Publish/Subscribe Systems

Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen.

In Proceedings of The 31th IEEE International Conference on Distributed Computing Systems (ICDCS 2011), pages 225-236, June 2011. IEEE Computer Society.
Acceptance rate: 15%.

Share

Abstract

It is a key challenge and fundamental problem in the design of distributed publish/subscribe systems to construct the underlying dissemination overlay. In this paper, we focus on effective practical solution for the MinMax-TCO problem: Create a topic-connected pub/sub overlay in which all nodes interested in the same topic are organized in a directly connected dissemination sub-overlay while keeping the maximum node degree to the minimum.

Previously known solutions provided an extensive analysis of the problem and an algorithm that achieves a logarithmic approximation for MinMax-TCO. Yet, they did not focus on efficiency of the solution or feasibility of decentralized operation that would not require full knowledge of the system. Compared to these solutions, our proposed algorithm produces an overlay with marginally higher degrees. At the same time, it has drastically reduced runtime cost, which is corroborated by both theoretical analysis and empirical evaluation. The latter shows a speedup by a factor of more than 25 on average for typical pub/sub workloads.

Download




Tags: overlay design, algorithms, publish/subscribe


Readers who enjoyed the above work, may also like the following:
  • A Generalized Algorithm for Publish/Subscribe Overlay Design and its Fast Implementation.
    Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen.
    In Proceedings of The 26th International Symposium on Distributed Computing (DISC 2012), pages 76-90, October 2012. Springer.
    Acceptance rate: 24%.
    Tags: algorithms, overlay design, overlay networks, publish/subscribe
  • Divide and Conquer Algorithms for Publish/Subscribe Overlay Design.
    Chen Chen, Hans-Arno Jacobsen, and Roman Vitenberg.
    In Proceedings of The 30th IEEE International Conference on Distributed Computing Systems (ICDCS 2010), pages 622-633, June 2010. IEEE Computer Society.
    Acceptance rate: 14%.
    Tags: overlay design, algorithms, publish/subscribe