General overlay networks

Most distributed publish/subscribe systems assume an acyclic overlay network, or use message flooding techniques to define a spanning tree in the network. The PADRES system, however, supports general cyclic overlay topologies. The benefits of this include greater flexibility to accommodate changing network conditions, improved robustness due to presence of redundant paths, and simplicity in network provisioning. Furthermore, a general overlay simplifies the development of other protocols, such as failure recovery. For example, since only one path exists between any pair of nodes in an acyclic overlay, it is not possible to route around congested, overloaded, or failed brokers. Furthermore, solutions for failure recovery and topology reconfiguration in an acyclic broker overlay can be very complex as they must maintain the acyclic property of the overlay.

PADRES brokers incorporate extensions to the standard content-based routing protocol that enable message routing in general overlay topologies. The design preserves the simple publish and subscribe interface to clients, and does not require changes to a broker's internal message matching algorithm allowing so it can be easily integrated into existing publish/subscribe systems. In addition, the algorithm exploits redundant routing paths to achieve dynamic optimal path routing of publications. Experiments demonstrate that by routing around congestion, this algorithm reduces message delivery delay by up to 51.67%. As well, when the network is not congested, the algorithm introduces little overhead, with observed delivery delays and broker CPU and memory consumption similar to the case without dynamic routing enabled.