Weighted Overlay Design for Topic-based Publish/Subscribe on Geo-Distributed Data Centers

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

In 35th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 474-485, July 2015.
Acceptance rate: 13%. 70 papers accepted out of 543 submissions..


We incorporate underlay information into overlay design for topic-based publish/subscribe (pub/sub) systems on geo-distributed data centers. We propose the MinAvg-WTCO problem that optimizes the weighted average node degree while constructing a topic-connected overlay (TCO), i.e., each topic induces a connected sub-overlay among all nodes interested in this topic. Most existing TCO designs are oblivious to the low-level network infrastructure and assume edge equivalence.

We prove that MinAvg-WTCO is NP-complete and difficult to approximate within a logarithmic factor with regard to the number of nodes. We devise several approximation algorithms for MinAvg-WTCO using different design techniques. Both theoretical analysis and empirical evaluation show that our designed algorithms tread the balance between overlay quality and runtime cost. Our algorithms significantly outperform the state of the art for TCO design that ignores edge differences.


Tags: icdcs15, overlay, pub/sub

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 10th ACM International Conference on Distributed and Event-Based Systems (DEBS), June 2016.
    Tags: overlay, pub/sub, churn handling, topic-connected overlay, t-man
  • Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints.
    Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.
    In 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