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.

Abstract

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.

Download



Sorry, can't prepare a list of recommended papers at the moment.