Design of routing protocols and overlay topologies for topic-based publish/subscribe on small-world networks

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., smallworld 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 topicbased 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 show 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.