TUD Technische Universität Darmstadt
Hessische Landes-und Hochschulbibliothek
HLuHB

EPDA - Elektronische Publikationen Darmstadt


Autor: Mühl, Gero
Titel:Large-Scale Content-Based Publish-Subscribe Systems
Dissertation:TU Darmstadt, Fachbereich Informatik, 2002

Die Dokumente in PDF 1.3 (mit Adobe Acrobat Reader 4.0 zu lesen):

dissFinal.pdf (2323131 Byte)

Abstract auf Deutsch:


Heutzutage wird die Architektur verteilter Systeme von Client/Server-Plattformen dominiert, die auf dem synchronen Request/Reply Paradigma aufbauen. Diese Architektur ist jedoch nicht dafür geeignet, informationsgetriebene Applikationen (z.B. Nachrichtendienste, Aktienkursdienste, Flugüberwachungsdienste oder die Verbreitung von Auktionsgeboten) zu implementieren. Dies liegt daran, dass die Anforderungen dieser Applikationen und die Charakteristika von Client/Server Plattformen sich grundlegend voneinander unterscheiden. Im Gegensatz dazu bilden Publish/Subscribe Systeme die Eigenschaften von informationsgetriebenen Applikationen direkt ab, da in diesem Fall die Kommunikation indirekt ist und vom Produzenten der jeweiligen Informationen angestoßen wird: Produzenten veröffentlichen Benachrichtigungen und diese werden allen subskribierten Konsumenten durch einen zwischengeschalteten Benachrichtigungsdienst zugestellt. Daher bieten sich Publish/Subscribe-basierte Implementationen für die Umsetzung derartiger Applikationen an. Die Ausdrucksfähigkeit der von den Konsumenten benutzten Nachrichtenselektion ist entscheidend für die Flexibilität eines Benachrichtigungsdienstes. Inhaltsbasierte Nachrichtenselektion ist am ausdrucksstärksten, weil in diesem Fall Prädikate über dem gesamten Inhalt einer Nachricht ausgedrückt werden können. Diese im Vergleich zu kanalbasierter und themenbasierter Selektion erhöhte Ausdrucksfähigkeit vergrößert die Flexibilität und begünstigt somit die Erweiterbarkeit und Änderbarkeit. Andererseits ist ein skalierbarer inhaltsbasierter Benachrichtigungsdienst schwierig zu realisieren. In der Tat muss die Ausdrucksfähigkeit der Nachrichtenselektion in großen Systemen sorgfältig festgelegt werden, weil Ausdrucksfähigkeit und Skalierbarkeit voneinander abhängig sind. Daher ist das wohl grundlegendste Problem im Bereich der inhaltsbasierten Publish/Subscribe Systeme das skalierbare Routen von Nachrichten von den Produzenten zu den entsprechenden Konsumenten. Unglücklicherweise sind die heutigen Benachrichtigungsdienste nicht weit genug entwickelt, um in großen, weit verteilten Umgebungen genutzt werden zu können. Die meisten existierenden Benachrichtigungsdienste sind entweder zentralisiert, benutzen "Flooding" oder basieren auf einfachen Routing-Algorithmen, die annehmen, dass jeder Broker globales Wissen über alle im System aktiven Subskriptionen hat. Diese Ansätze haben allerdings ausgeprägte Skalierbarkeitsprobleme in großen Systemen. Diese Arbeit konzentriert sich auf Mechanismen, welche die Skalierbarkeit von inhaltsbasierten Routing-Algorithmen erhöhen und präsentiert verbesserte Algorithmen, die kein globales Wissen voraussetzen. Die Algorithmen basieren auf Tests, die bestimmte "Ähnlichkeiten" zwischen Subskriptionen erkennen können (Identitäts- und Überdeckungstests) und auf dem Konzept der Verschmelzung von Filtern. Darüber hinaus wird auch die Idee der "nicht perfekten" Routing-Algorithmen eingeführt. Im Einzelnen besteht die hier vorgestellte Arbeit aus einem theoretischen und einem praktischen Teil. Der theoretische Teil stellt eine formale Spezifikation von Publish/Subscribe Systemen, ein Routing-Framework und einige Routing-Algorithmen vor. Daneben wird auch diskutiert, wie die vorgeschlagenen Routing-Optimierungen auf das eigentliche Daten- und Filtermodell heruntergebrochen werden können. Der praktische Teil der Arbeit stellt die Implementierung des Benachrichtigungsdienstes Rebeca vor, der die diskutierten Routing-Algorithmen und zusätzlich zu Subskriptionen auch Ankündigungen von Produzenten unterstützt. Außerdem wird eine detaillierte praktische Evaluation der Routing-Algorithmen vorgestellt, die auf dem implementierten Prototypen basiert.


Abstract auf Englisch:

Today, the architecture of distributed computer systems is dominated by client/server platforms relying on synchronous request/reply. This architecture is not well suited to implement information-driven applications like news delivery, stock quoting, air traffic control, and dissemination of auction bids due to the inherent mismatch between the demands of these applications and the characteristics of those platforms. In contrast to that, publish/subscribe directly reflects the intrinsic behavior of information-driven applications because communication here is indirect and initiated by producers of information: Producers publish notifications and these are delivered to subscribed consumers by the help of a notification service that decouples the producers and the consumers. Therefore, publish/subscribe should be the first choice for implementing such applications. The expressiveness of the notification selection mechanism used by the consumers to describe the notifications they are interested in is crucial for the flexibility of a notification service. Content-based notification selection is most expressive because it allows to evaluate filter predicates over the whole content of a notification. The advantage in expressiveness compared to channel- or subject-based selection results in increased flexibility facilitating extensibility and change. On the other hand, scalable implementations of content-based notification services are difficult to realize. Indeed, the expressiveness of notification selection must be carefully chosen in large-scale systems, because expressiveness and scalability are interdependent. Hence, the most fundamental problem in the area of content-based publish/subscribe systems is probably the scalable routing of notifications from their producers to their respective consumers. Unfortunately, existing content-based notification services are not mature enough to be used in large-scale, widely-distributed environments. Most existing notification services are either centralized, use flooding, or use simple routing algorithms that assume that each event broker has global knowledge about all active subscriptions. All these approaches exhibit severe scalability problems in large-scale systems. In contrast to that, this thesis concentrates on mechanisms to improve the scalability of content-based routing algorithms and presents more advanced routing algorithms that do not rely on global knowledge. The algorithms presented here exploit similarities between subscriptions by using identity- and covering-tests, and by merging filters. While identity-based routing is a simplified version of covering-based routing, merging-based routing is more advanced because it exploits the concept of filter merging. Furthermore, the idea of imperfect routing algorithms is introduced. The thesis consists of a theoretical and a practical part. The theoretical part presents a formal specification of publish/subscribe systems, a routing framework and a set of routing algorithms, and discusses how the routing optimizations can be broken down to the actual data/filter model. The practical part presents the implementation of the Rebeca notification service which supports advertisements and all the routing algorithms mentioned above. A detailed practical evaluation of the implemented algorithms based upon the prototype is also presented.

Dokument aufgenommen :2002-11-22
URL:http://elib.tu-darmstadt.de/diss/000274