Algorithms Based on Divide and Conquer for Topic-Based Publish/Subscribe Overlay Design
Authors:
- 2 December 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 24 (1) , 422-436
Abstract
Overlay design for topic-based publish/subscribe (pub/sub) systems is of primary importance because the overlay forms the basis for the system and directly impacts its performance. This paper focuses on the MinAvg-TCO problem: Use the minimum number of edges to construct a topic-connected overlay (TCO) such that all nodes that are interested in the same topic are organized in a directly connected dissemination suboverlay. Existing algorithms for MinAvg-TCO suffer from three key drawbacks: 1) prohibitively high runtime cost; 2) reliance on global knowledge and centralized operation; and 3) nonincremental operation by reconstructing the TCO from scratch. From a practical point of view, these are all severe limitations. To address these concerns, we develop algorithms that dynamically join multiple TCOs. Inspired by the divide-and-conquer character of this idea, we derive a number of algorithms for the original MinAvg-TCO problem that accommodate a variety of practical pub/sub workloads. Both theoretical analysis and experimental evaluations demonstrate that our divide-and-conquer algorithms seek a balance between time efficiency and the number of edges required: Our algorithms cost a fraction (up to 1.67%) of the runtime cost of their greedy alternatives, which come at the expense of an empirically insignificant increase in the average node degree. Furthermore, in order to reduce the probability of poor partitioning at the divide phase, we develop a bulk-lightweight partitioning scheme on top of random partitioning. This more refined partitioning imposes a marginally higher runtime cost, but leads to improvements in the output TCOs, including average node degrees and topic diameters.Keywords
This publication has 30 references indexed in Scilit:
- Locality-Awareness in a Peer-to-Peer Publish/Subscribe Network2012
- PolderCast: Fast, Robust, and Scalable Architecture for P2P Topic-Based Pub/Sub2012
- Rappel: Exploiting interest and network locality to improve fairness in publish-subscribe systemsComputer Networks, 2009
- Efficient Publish/Subscribe Through a Self-Organizing Broker Overlay and its Application to SIENAThe Computer Journal, 2007
- PastryStrings: A Comprehensive Content-Based Publish/Subscribe DHT Network2006
- Topology-Aware Routing in Structured Peer-to-Peer Overlay Networks2003
- Scribe: a large-scale and decentralized application-level multicast infrastructureIEEE Journal on Selected Areas in Communications, 2002
- A scalable content-addressable networkACM SIGCOMM Computer Communication Review, 2001
- ChordACM SIGCOMM Computer Communication Review, 2001
- Parallel and serial heuristics for the minimum set cover problemThe Journal of Supercomputing, 1992