Login |
Scaling Construction of Low Fan-out Overlays for Topic-based Publish/Subscribe Systems
Roman Vitenberg, Chen Chen, and Hans-Arno Jacobsen.
University of Toronto, University of Oslo, December 2010.
Pages 1-20.
Abstract
It is a key challenge and fundamental problem in the design of
distributed publish/subscribe systems to construct the underlying
dissemination overlay. In this paper, we focus on effective practical
solution for the MinMax-TCO problem: Create a topic-connected pub/sub
overlay in which all nodes interested in the same topic are organized
in a directly connected dissemination sub-overlay while keeping the
maximum node degree to the minimum.
Previously known solutions provided an extensive analysis of the problem
and an algorithm that achieves a logarithmic approximation for
MinMax-TCO. Yet, they did not focus on efficiency of the solution or
feasibility of decentralized operation that would not require full
knowledge of the system. Compared to these solutions, our proposed
algorithm produces an overlay with marginally higher degrees. At the
same time, it has drastically reduced runtime cost, which is
corroborated by both theoretical analysis and empirical evaluation.
The latter shows a speedup by a factor of more than 25 on average for
typical pub/sub workloads.
Download
