Content-based publish/subscribe systems: architectures and algorithms

Publish/subscribe communication paradigm is an interaction paradigm suitable for a variety of large scale dynamic applications, requiring selective events diffusion or data notification: news delivery, stock quoting, on-line games, dissemination of multimedia contents, services and resources discovery, remote control of critical infrastructures and management of large scale systems are examples of systems requiring such reactive communication paradigm. Content-based publish/subscribe is the most promising version of publish/subscribe system: in such systems, users subscribe to content-based conditions, and will be notified about the published events that satisfy their expressed conditions. Content-based style subscriptions are highly expressive and flexible, permitting the users to specify complex filtering criteria along multiple dimensions of the events content. In contrast to their flexibility and expressiveness, scalable content-based publish/subscribe systems are difficult to implement and the proposed solutions are not always mature. In other words, one of the most fundamental requirement in the area of content-based pub/sub systems is to design scalable and efficient event dissemination mechanisms maintaining the expressiveness in the subscription language and the flexibility in the structures defining the events. In addition, most of existing pub/sub systems assume that actors involved in the subscriptions management have global knowledge about active subscriptions. This assumption limits the scalability of the existing approaches when they are dealing with large scale and dynamical systems. In this thesis, we research for algorithms and techniques that permit to build content-based pub/sub systems over efficient data dissemination structures. The thesis consists on different kind of contributions. First of all, a global and systematic analysis of the functionalities of the event service has been produced, critically describing the current solutions, the strengths and the weaknesses of the existing approaches. In the second part, we propose innovative algorithms and architectures for pub/sub systems. We introduce novel approaches for content-based pub/sub systems, guaranteeing the expressiveness for any application domain and maintaining the scalability with respect to the number of participants and to the number subscriptions. The clustering functionality is designed to match application-level multicast techniques with content-based routing of events. We introduce clustering mechanisms (hierarchical and not hierarchical algorithms) in the event service to dynamically identify groups of users with similar preferences and to adapt these groups in the context of content-based publish/subscribe systems. One of the main feature of the proposed mechanism is the use of the system state knowledge sharing by system nodes, with the goal of limiting the system overhead in terms of computing, bandwidth and storage resources. Gossiping and probabilistic techniques represent a potential and open research field that has been analyzed and described within this work. In high dynamical large scale systems, the dynamic and unpredictable behavior of the nodes can cause problems to be resolved with approaches more adaptive and robust to the fast and frequent system changes. An innovative solution for pub/sub systems is proposed relying on an unstructured overlay network where a variant of subscriptions flooding-based algorithm is adopted to face with highly dynamical environments. Last contribution consists of examples of real applications that exploit the potentialities of the publish-subscribe paradigm model. We provide architectures based on the pub/sub models in the field of the infrastructures for monitoring critical systems and of the infrastructures for context-aware applications. Keywords: clustering, multicast dissemination, broadcast dissemination, collaborative p2p approaches, structured and unstructured overlay networks, distributed systems evaluation, architectures based on pub/sub models