Cyclic or general overlays may provide multiple paths between publishers and subscribers. However, an advertisement tree and a matching subscription activates only one path for notifications routing in publish subscribe systems. This poses serious challenges in handling network conditions like congestion, and link or broker failures. Further, content-based dynamic routing of notifications requires instantaneous updates in routing paths, which is not a scalable option. This paper introduces a clustering approach with a bit-vector technique for inter-cluster dynamic routing of notifications in a structured cyclic topology that provides multiple paths between publishers and interested subscribers. The advertisement forwarding process exploits the structured nature of the overlay topology to generate advertisement trees of length 1 without generating duplicate messages in the advertisement forwarding process. Issued subscriptions are divided into multiple disjoint subgropus, where each subscription is broadcast to a cluster, which is a limited part of the structured cyclic overlay network. We implemented novel static and intra-cluster dynamic routing algorithms in the proposed overlay topology for our advertisement-based publish subscribe system, called OctopiA. We also performed a pragmatic comparison of our two algorithms with the state-of-the-art. Experiments on a cluster testbed show that our approach generates fewer inter-broker messages, and is scalable.
This paper develops content-based publish subscribe algorithms to support general overlay topologies, as opposed to traditional acyclic or tree-based topologies. Among other benefits, publication routes can adapt to dynamic conditions by choosing among alternate routing paths, and composite events can be detected at optimal points in the network. The algorithms are implemented in the PADRES publish subscribe system and evaluated in a controlled local environment and a wide-area PlanetLab deployment. Atomic subscription notification delivery time improves by 20 in a well connected network, and composite subscriptions can be processed with 80 less network traffic and notifications delivered with about half the end to end delay.