  Acyclic overlays used for broker-based publish/subscribe systems provide
unique paths for content-based routing from a publisher to interested
subscribers. Cyclic overlays may provide multiple paths, however, the
subscription broadcast process generates one content-based routing path per
subscription. This poses serious challenges in offering dynamic routing of
notifications when congestion is detected because instantaneous updates in
routing tables are required to generate alternative routing paths. This paper
introduces the first subscription-based publish/subscribe system, OctopiS,
which offers inter-cluster dynamic routing when congestion in the output queues
is detected. OctopiS is based on a formally defined Structured Cyclic Overlay
Topology (SCOT). SCOT is divided into homogeneous clusters where each cluster
has equal number of brokers and connects to other clusters through multiple
inter-cluster overlay links. These links are used to provide parallel routing
paths between publishers and subscribers connected to brokers in different
clusters. While aiming at deployment at data center networks, OctopiS generates
subscription-trees of shortest lengths used by Static Notification Routing
(SNR) algorithm. Dynamic Notification Routing (DNR) algorithm uses a bit-vector
mechanism to exploit the structuredness of a clustered SCOT to offer
inter-cluster dynamic routing without making updates in routing tables and
minimizing load on overwhelmed brokers and congested links. Experiments on a
cluster testbed with real world data show that OctopiS is scalable and reduces
the number of inter-broker messages in subscription delivery by 89%,
subscription delay by 77%, end-to-end notification delay in static and dynamic
routing by 47% and 58% respectively, and the lengths of output queues of
brokers in dynamic routing paths by 59%.
