A Peer-to-Peer Approach toContent-Based Publish/SubscribeWesley W. Terpstra Stefan Behnel Ludger FiegeAndreas Zeidler Alejandro P. BuchmannDepartment of Computer ScienceDarmstadt University of TechnologyD-64283 Darmstadt, [email protected],behnel,fiege@gkec.tu-darmstadt.de,az,buchmann@informatik.tu-darmstadt.deABSTRACTPublish/subscribe systems are successfully used to decoupledistributed applications. However, their efficiency is closelytied to the topology of the underlying network, the design ofwhich has been neglected. Peer-to-peer network topologiescan offer inherently bounded delivery depth, load sharing,and self-organisation. In this paper, we present a content-based publish/subscribe system routed over a peer-to-peertopology graph. The implications of combining these ap-proaches are explored and a particular implementation usingelements from Rebeca and Chord is proven correct.KeywordsPublish/subscribe, content-based routing, peer-to-peer net-works, graph topology1. INTRODUCTIONPublish/subscribe is a scalable and flexible communica-tion paradigm which suits the needs of modern applications.A publish/subscribe service conveys published notificationsfrom any producer to all interested consumers with a match-ing subscription set. In this manner clients do not usesource/destination identifiers or addresses. This inherentloose coupling of producers and consumers is the primaryadvantage of these systems.To achieve this loose coupling, consumers subscribe tospecific kinds of event notifications. The most flexible se-lection criteria for notifications is realized by content-basedselection. In this particular publish/subscribe model, no-tification messages are filtered according to their content.Event notifications propagate from a producer to interestedconsumers through a network of filters.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.DEBS’03 2003, San Diego/CA, USACopyright 2003 ACM /06/03 ...$5.00.However, state of the art content-based publish/subscribesystems have static networks. While subscriptions changedynamically with the interests of the current clients, therouting network used to publish the notifications remainsrather unchanged. Furthermore, the network is often cho-sen to be a tree in order to simplify the routing algorithms.This approach introduces single points of failure and bot-tlenecks. However, since the network topology significantlyinfluences the performance of the overall system, it shouldbe carefully selected to reduce network congestion, minimiserouting depth, and preserve these properties in face of chang-ing network nodes and failures. These properties are missingin current systems.On the other hand, peer-to-peer (P2P) networks often ad-dress precisely these issues. They self-coordinate a very largenetwork to achieve a common goal. The assumption madefor the design of peer-to-peer networks is frequent node fail-ure and changing participation. The networks typically haveexcellent routing depth guarantees. Also, as most peers areequal, traffic is often evenly distributed, reducing conges-tion. All peer-to-peer systems maintain their guaranteesunder the assumption of frequent failures.Modern peer-to-peer networks have been used to great ef-fect in implementing a form of multicast [17]. Topic-basedpublish/subscribe—a primitive addressing model—can beimplemented on peer-to-peer multicast. The routing deci-sions of peer-to-peer networks are generally simplistic. Ourpublish/subscribe routing policy allows for decisions with se-lection criteria as flexible as content-based publish/subscribe.To provide more reliable and scalable topologies for content-based filtering, more general graphs than a tree must bemaintained. Our contribution in this paper is to take thegraph topology and management of a peer-to-peer networkand couple it with the highly flexible routing of a pub-lish/subscribe system. Of particular interest, our networkpreserves the use of fully general filters, yet guarantees alogarithmic bound on delivery depth with evenly distributedcongestion, even in the face of dynamic participation andfailures.The remainder of this paper is structured as follows. Insection 2 we briefly outline Chord [18], a P2P overlay routingscheme, and Rebeca [11], a content-based publish/subscribesystem, both of which we borrow ideas from. After section 3Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full cit ation on the first page. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2003 ACM - 1-58113-843-1…$500. 1motivates the design of our system, we outline its formalproperties. Section 4 proceeds to present and prove cor-rect the publish and subscribe algorithms. We then discussthroughout section 5 how to preserve the required networkand filter structure in the face of node and edge failures andjoins. Finally, in section 6 and 7, we compare our systemto existing work and outline the direction of our further re-search.2. COMMUNICATION PARADIGMSThe communication architecture envisioned in this paperintegrates content-based filtering strategies directly on topof a P2P network topology. To manage the filters, we reuseRebeca’s algorithms for filter covering and merging [8, 10,11]. The topology of our network is directly borrowed fromthe Chord P2P network [18]. However, the generalised rout-ing algorithm used to implement the publish/subscribe in-terface is the focus of this paper. The maintenance of thegraph is implemented using this generalised routing algo-rithm rather than Chord’s native algorithm which we omit.2.1 RebecaProcesses in pub/sub systems (also known as event-basedsystems [8]) are clients of an underlying notification serviceand can act both as producers and consumers of messages,called event notifications or notifications for short. A notifi-cation is a message that describes an
View Full Document
Unlocking...