BeaConvey: Co-design of overlay and routing for topic-based publish/subscribe on small-world networks

Abstract

Distributed pub/sub must make principal design choices with regards to overlay topologies and routing protocols. It is challenging to tackle both aspects together, and most existing work merely considers one. We argue the necessity to address both problems simultaneously, since only the right combination of the two can deliver an ecient internet-scale pub/sub. Traditional design space spans from structured data-oblivious overlays employing greedy routing strategies all the way to unstructured data-driven overlays using naive broadcast-based routing. The two ends of the spectra come with unacceptable prices: the former often exerts considerable overhead on each node for forwarding irrelevant messages, while the latter is dicult to scale due to prohibitive latencies stemming from unbounded node degrees and network diameters. To achieve the best of both worlds, we propose BeaConvey, a distributed pub/sub system for federated environments. First, we dene the small-world and interest-close overlay (SWICO) that embraces both small-world properties and pub/sub semantics. To construct a SWCIO, we devise a greedy heuristic to assign small-world identiers and ngers in a centralized manner. Second, we develop a family of peer-to-peer pub/sub routing protocols that leverages such SWICOs. Empirical evaluation shows that BeaConvey achieves substantial improvement in routing overhead and propagation delays. For instance, the routing overhead of BeaConvey is only 20% to 40% of the state of the art. This acceleration is consistent across a variety of pub/sub workloads, and BeaConvey obtains such adaptability by optimizing both overlay and routing, which complement each other in dierent situations. Under one Facebook workload with a skewed distribution, 78% of the improvement is accredited to a better overlay. Under another non-skewed workload, more advanced routing contributes 95% of cost reduction.