Diploma Thesis DIP-3151

BibliographyQuist, Tom: Underlay Aware Approach to Provide Reliable and Timely Dissemination of Events in a Publish Subscribe System.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3151 (2011).
89 pages, english.
CR-SchemaC.2.4 (Distributed Systems)
C.2.1 (Network Architecture and Design)
C.2.2 (Network Protocols)
KeywordsPublish-Subscribe; P2P; underlay-awareness; network-topology
Abstract

Publish-subscribe is a well-known paradigm for building distributed applications. Events produced by peers, called publishers, are disseminated to interested consumers, called subscribers. Usually publishers and subscribers are arranged in a peer-to-peer overlay network, which helps in dissemination of events in a decentralised manner. Recent research tries to provide Quality-of-Service like delay bounds or reliability in such a system. In order to provide reliability current distributed publish-subscribe systems mostly either rely on overlay level acknowledgement protocols or try to find multiple disjoint paths in the overlay to increase redundancy without taking into account the underlay topology. Acknowledgements induce high delays affecting timeliness of event delivery. Providing multiple paths without looking at the underlay does not take into account correlations between paths within the underlay. We address these drawbacks by designing a content-based publish-subscribe system which provides reliability by taking into account the underlay topology to reduce correlations within the underlay in overlay links. The system consists of three layers: The Topology-Discovery-Overlay (TDO) layer constructs an underlay topology aware overlay which reflects the underlay topology by using a path-matching algorithm. On top of the TDO the Maximum-Reliability-Spanning-Tree (MRST) layer constructs k overlay link disjoint trees which contain the most reliable overlay links. The MRSTs are used by the content-based publish-subscribe layer for subscription flooding and event forwarding. The system has been evaluated by simulations in PeerSim using Internet-like topologies. The results show that the TDO discovers most of the underlay topology and constructs overlay topologies reflecting the underlay topology. Simulations also show that the system converges towards a maximum event delivery probability.

Full text and
other links
PDF (677114 Bytes)
CopyrightTom Quist
Contacttom@quist.de
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)M. Sc. Muhammad Adnan Tariq
Entry dateOctober 9, 2011
   Publ. Department   Publ. Institute   Publ. Computer Science