Algorithms based on Divide and Conquer for Topic-based Publish/Subscribe Overlay Design

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

ACM/IEEE Transactions on Networking, 2014.
Accepted for publication, September, 2014..

Abstract

Overlay design for topic-based publish/subscribe (pub/sub) systems is of primary importance because the overlay forms the basis for the system and directly impacts its performance. This paper focuses on the MinAvg-TCO problem: Use the minimum number of edges to construct a topic-connected overlay (TCO) such that all nodes that are interested in the same topic are organized in a directly connected dissemination sub-overlay.

Existing algorithms for MinAvg-TCO suffer from three key drawbacks: 1) prohibitively high runtime cost; 2) reliance on global knowledge and centralized operation; and 3) nonincremental operation by reconstructing the TCO from scratch.

From a practical point of view, these are all severe limitations. To address these concerns, we develop algorithms that dynamically join multiple TCOs. Inspired by the divide-and-conquer character of this idea, we derive a number of algorithms for the original MinAvg-TCO problem that accommodate a variety of practical pub/sub workloads. Both theoretical analysis and experimental evaluations demonstrate that our divide-and-conquer algorithms seek a balance between time efficiency and the number of edges required: Our algorithms cost a fraction (up to 1.67%) of the runtime cost of their greedy alternatives, which come at the expense of an empirically insignificant increase in the average node degree. Furthermore, in order to reduce the probability of poor partitioning at the divide phase, we develop a bulk-lightweight partitioning scheme on top of random partitioning. This more refined partitioning imposes a marginally higher runtime cost, but leads to improvements in the output TCOs, including average node degrees and topic diameters.

Download



Tags: algorithms, publish/subscribe, pub/sub, topic-based pub/sub


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
  • 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%.
    Tags: overlay design, algorithms, 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