ISU Electrical and Computer Engineering Archives

Techniques for building a scalable and reliable distributed content-based publish/subscribe system

Shen, Zhenhui (2007) Techniques for building a scalable and reliable distributed content-based publish/subscribe system. PhD thesis, Iowa State University.

This is the latest version of this eprint.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Publish/subscribe is a generic paradigm for event dissemination, where events generated by publishers are delivered to subscribers, who express their interests in certain types of events via subscriptions. The strength of the publish/subscribe model lies in the anonymity between publishers and subscribers, which makes it well suited for building modern loosely coupled distributed applications. Among different variants of publish/subscribe, content-based publish/subscribe is especially expressive, since subscriptions consist of user defined predicates on the complete content of an event. A content-based system is usually constructed as a distributed network of routers, so that it can scale with the number of users, and avoid a single point of failure. However, the flexibility of content-based systems currently comes at a significant cost. Event forwarding is a complex task, since each forwarding decision is now based on the content of an event, rather than on a fixed destination address, as in IP routing, or on a fixed group name, as in traditional multicast. Meanwhile in order to receive events published at remote sites, it is necessary for each router to propagate locally registered subscriptions. But disseminating subscriptions in the network can also be expensive both space-wise and time-wise. Furthermore since it is built as a distributed network of multiple routers, the system needs to be tolerant of various faults such as link failure, message loss and data corruption. In this thesis, we develop techniques for building a scalable and reliable distributed content-based publish/subscribe system. Our contributions are as follows. First, we expedite distributed event forwarding through a strategy called ``lookup reuse'' which replaces a large fraction of expensive content-based event filtering operations with much cheaper hash-table lookups. Simulations show that lookup reuse decreases the event processing overhead on average by 40%. Next, we exploit an optimization called subscription covering to decrease the number of subscriptions forwarded in the system. To efficiently manage subscription covering, we build a framework decoupling the detection of covering from its maintenance. Simulations show that our modular structure is faster than previously known solutions. We also propose a new concept called approximate covering that provably obtains much of the benefits of exact covering at a fraction of its cost. Further, we design a scalable fault-tolerance scheme to fortify content-based systems through self-stabilization, where a corrupted component of the distributed system can automatically revert to a ``correct'' state through local corrections. This scheme has the advantage of addressing all the faults through a uniform mechanism.

EPrint Type:Thesis (PhD)
Uncontrolled Keywords:content-based publish/subscribe, scalability, reliability, event forwarding, subscription covering, space filling curve, self-stabilize
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
ID Code:338
Identification Number:Identification Number UNSPECIFIED
Deposited By:Mr. Zhenhui Shen
Deposited On:29 August 2007

Available Versions of this Item

  • Techniques for building a scalable and reliable distributed content-based publish/subscribe system (deposited 29 August 2007) [Currently Displayed]

Archive Staff Only: edit this record