Design of Routing Protocols and Overlay Topologies for Topic-based Publish/Subscribe on Small-World Networks

Chen Chen and Yoav Tock.

In Proceedings of the Industry Track of the 16th ACM/IFIP/USENIX Middleware conference (Middleware Industry 2015), Dec 2015.
Acceptance rate: 20%. Only 4 papers accepted out of 20 submissions in Industry Track.


It is primarily important and challenging to develop a distributed publish/subscribe (pub/sub) system for large-scale workloads. On the one hand, structured overlays (e.g., small-world networks) scale logarithmically in terms of node degrees, propagation delay, and so on, but pub/sub routing on these structured overlays often exerts considerable overhead on each node for forwarding irrelevant messages. On the other hand, the unstructured topic connected overlay (TCO) can eliminate unnecessary pure forwarders, since each topic induces a connected sub-overlay among all nodes interested in this topic; however, the node degrees and diameters are unbounded in a constructed TCO.

To achieve the best of both worlds, we design a practical pub/sub system in peer-to-peer settings, including both routing protocols and overlay topologies. First, based on small-world overlays, we propose the Nearest Subscribers and Matched Fingers (NSMF) routing protocol for topic-based pub/sub. Second, to reduce the routing overhead of NSMF, we construct small-world overlays that aim to maximize interest closeness, where each node strives to point its small-world fingers to nodes with common interests.

We validate our design with empirical evaluation and demonstrate the advantages, in both routing efficiency and overlay quality. As compared to regular small-world networks, our system reduces over 30% of the costs in both pure forwarding messages and the average path length.


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