4th International Workshop on Distributed Event-Based Systems (DEBS'05)

CHR: a Distributed Hash Table for Wireless Ad Hoc Networks
Filipe Araujo, Luis Rodrigues, Joerg Kaiser, Changling Liu, and Carlos Mitidieri
Universidade de Lisboa, Portugal and University of Ulm, Germany

Abstract: This paper focuses on the problem of implementing a distributed hash table (DHT) in wireless ad hoc networks. Scarceness of resources and node mobility turn routing into a challenging problem and therefore, we claim that building a DHT as an overlay network (like in wired environments) is not the best option. Hence, we present a proof-of-concept DHT, called Cell Hash Routing (CHR), designed from scratch to cope with problems like limited available energy, communication range or node mobility. CHR overcomes these problems, by using position information to organize a DHT of clusters instead of individual nodes. By using position-based routing on top of these clusters, CHR is very efficient. Furthermore, its localized routing and its load sharing schemes, make CHR very scalable in respect to network size and density. For these reasons, we believe that CHR is a simple and yet powerful adaptation of the DHT concept for wireless ad hoc environments.

Analysis and Algorithms for Content-based Event Matching
Elad Hazan, Satyen Kale, Fengyun Cao, and Jaswinder Pal Singh
Computer Science Department, Princeton University, Princeton, USA

Abstract: Content-based event matching is an important problem in large-scale event-based publish/subscribe systems. However, open questions remain in analysis of its difficulty and evaluation of its solutions. This paper makes a few contributions toward analysis, evaluation and development of matching algorithms. First, based on a simplified yet generic model, we give a formal proof of hardness of matching problem by showing its equivalence to the notoriously hard Partial Match problem. Second, we compare two major existing matching approaches and show that counting-based algorithms are likely to be more computationally expensive than tree-based algorithms. Third, we observe an important, prevalent characteristic of real-world publish/subscribe applications, and develop a new matching algorithm called RAPIDMatch to exploit it. Finally, we propose a new metric for evaluation of matching algorithms. We analyze and evaluate RAPIDMatch using both the traditional and new metrics proposed. Results show that RAPIDMatch achieves large performance improvement over tree-based algorithm under certain publish/subscribe scenarios.

MEDYM: Match-Early and Dynamic Multicast for Content-based Publish-Subscribe Service Networks
Fengyun Cao and Jaswinder Pal Singh
Princeton University, Princeton, USA

Abstract: Architecture design for content-based publishsubscribe service networks has been a challenging problem, because its communication paradigm cannot be directly supported by existing network primitives. In this paper, we propose a new architectural design called MEDYM Match Early with DYnamic Multicast. Unlike existing approaches, MEDYM does not rely on static overlay networks for event delivery. Instead, an event is matched against subscriptions early at the publishing server, to identify destinations with matching subscriptions, and then sent to destinations through a dynamically constructed multicast tree. This architecture achieves low computation cost in matching and high network efficiency in routing. We evaluate MEDYM through detailed simulations, and compare it with the two major existing design approaches: Content-based Forwarding and Channelization. Results show that MEDYM significantly improves event delivery efficiency and system scalability. We also examine closely overheads introduced in MEDYM, and found them to be well acceptable and more than outweighed by the benefits of the approach. We expect the MEDYM architecture to scale to pub-sub networks of thousands of servers, which we believe is adequate for many interesting applications in the foreseeable future.

Publish-Subscribe Tree-Maintenance over a DHT
Paolo Costa and Davide Frey
Politecnico di Milano, Italy

Abstract: Content-based publish-subscribe middleware is emerging as a promising answer to the demands of modern highly dynamic distributed computing by providing the necessary decoupling and flexibility. Nevertheless, currently available systems implement event dispatching by relying on an overlay network with unrooted tree topology but they do not provide any mechanism to maintain it in presence of reconfiguration, thus hampering their use in dynamic and unreliable scenarios. In this paper, we present a novel approach to accomplish this task by exploiting a Distributed Hash Table (DHT). Our algorithm supports arbitrary tree topologies and deals very well with the dynamicity of network scenarios by limiting the impact of reconfigurations induced by topology changes. These results are confirmed by simulations which validate the applicability of our approach in reconfigurable publishmiddleware.

On Introducing Location Awareness in Publish-Subscribe Middleware
Gianpaolo Cugola and Jose Enrique Munoz de Cote
Dip. di Elettronica e Informazione, Politecnico di Milano, Milan, Italy

Abstract: Having the possibility of routing messages only toward specific areas or subscribing to messages originating in specific locations seems natural when a publish-subscribe model of communication is adopted. Unfortunately, very few work have investigated such kind of services and none of the most widely adopted publish-subscribe middleware implements them. In this paper we first classify possible location-based publish-subscribe services, then we describe an algorithm to efficiently implement them in a distributed publish-subscribe middleware.

Publisher Mobility in Distributed Publish/Subscribe Systems
Vinod Muthusamy, Milenko Petrovic, Dapeng Gao, and Hans-Arno Jacobsen
Department of Electrical and Computer Engineering, University of Toronto, Canada

Abstract: The decoupling of producers and consumers in time and space in the publish/subscribe paradigm lends itself well to the support of mobile users who roam about the environment with intermittent network connectivity. This paper presents the first quantitative evaluation of the factors that affect performance when mobility is introduced to a publish/subscribe system. We formalize publisher mobility algorithms for a distributed publish/subscribe system supporting mobile publishers, and develop and evaluate optimizations for mobile publisher algorithms.

Policy-controlled Event Management for Distributed Intrusion Detection
Christian Kreibich and Robin Sommer
Computer Laboratory, University of Cambridge, UK and Computer Science Department, Technische Universitaet Muenchen, Germany

Abstract: A powerful strategy in intrusion detection is the separation of surveillance mechanisms from a site's policy for processing observed events. The Bro intrusion detection system has been using the notion of policy-neutral events as the basic building blocks for the formulation of a site's security policy since its conception. A recent addition to the system is the ability to exchange events with other Bro peers to allow distributed detection. In this paper we extend Bro's existing event model to ful ll the requirements of scalable policy-controlled distributed event management, including mechanisms for event publication, subscription, processing, propagation, and correlation.

Integrating Distributed Object Transactions with Wide-Area Content-Based Publish/Subscribe Systems
Anton Michlmayr and Pascal Fenkam
Vienna University of Technology, Distributed Systems Group, Wien, Austria

Abstract: Transactions are necessary for many distributed applications to deliver reasonable results. Typically, said transaction engines enhance systems dependability by providing atomicity, isolation, consistency, and durability. Yet, emerging paradigms in distributed systems seem to challenge these traditional concepts. This paper presents early results in integrating distributed object transactions with content-based publish/subscribe systems. Essentially, the paper illustrates a novel and generic integration framework that 1) supports application dependent message failure models and 2) exhibits a full messaging transaction mechanism. We discuss integration challenges, analyze middleware requirements, and position our attempt among existing approaches.

Integrating Databases with Publish/Subscribe
Luis Vargas, Jean Bacon, and Ken Moody
Computer Laboratory, University of Cambridge, Cambridge, UK

Abstract: Publish/subscribe is emerging as an appropriate communication paradigm for large-scale, widely-distributed systems. In this paper, we describe our work on integrating active databases with publish/subscribe, using PostgreSQL and Hermes as the experimental context. In the proposed architecture, each database manager defines and advertises change events, in contrast with a continuous query model. Advertised events, which may span a number of physical relations, correspond to the virtual relations of a security view. Clients subscribe to events of interest, and can refine their subscriptions through content-based filter expressions. An event is published whenever a database change, detected via a dynamic triggering layer, matches some active subscription. Security and routing of database events are handled in the same way as for conventional Hermes events.

A Two-way Publish-Subscribe System (Position Paper)
Ingar Mæhlum Arntzen and Dag Johansen
Dept. Computer Science University of Tromsø, Norway

Abstract: Anonymity between publishers and subscribers is an implicit assumption for many publish-subscribe systems. By restructuring a popular pull-based Web application, the online marketplace, to fit the publish-subscribe paradigm, we discovered that absolute anonymity is not always an attractive property. We present a publish-subscribe system that allows providers to access limited information on consumers, and vice-versa. Especially, consumers may subscribe to provider-information (product publications), and providers may subscribe to consumer-information (consumer-subscriptions). We call this structure a Two-way Publish-Subscribe System.

Low Latency Optimisation of Content Based Publish Subscribe for Real-Time Mobile Gaming Applications
Duncan McCaffery and Joe Finney
Computing Department, Lancaster University, Lancaster, United Kingdom

Abstract: In recent years real-time multiplayer networked gaming has grown in popularity due to exciting challenges posed by competing with human opponents. It is therefore very likely that the introduction of more powerful portable wireless hand held devices will motivate a similar demand for fast action collaborative multiplayer gaming capabilities on those platforms also. In this paper we argue that the commonly used communication architectures for today s multiplayer gaming applications will not work in the mobile wireless domain. We address this argument by introducing our own architecture based on publish subscribe and structured peer to peer that offers a novel interest managed, spatially partitioned solution. Finally we evaluate this approach and suggest that an optimal solution also requires knowledge of both the network interface in use and of the underlying network topology.

A Distributed Alerting Service for Open Digital Library Software
Annika Hinze and George Buchanan
Department of Computer Science, University of Waikato, New Zealand and UCL Interaction Centre, University College London, United Kingdom

Abstract: Alerting for Digital Libraries is an important and useful feature for the library users. To date, two independent services and a few publisher-hosted proprietary services have been developed. Here, we address the problem of integrating alerting as functionality into open source software for distributed digital libraries. For this application existing solutions are insufficient; new ways have to be found for supporting a fragmented network of distributed digital library servers. We propose the design and usage of a distributed Directory Service. This paper also introduces our hybrid approach using two networks and a combination of different distributed routing strategies for event filtering.

On the Benefits of Non-Canonical Filtering in Publish/Subscribe Systems
Sven Bittner and Annika Hinze
University of Waikato, Hamilton, New Zealand

Abstract: Current matching approaches in pub/sub systems only allow conjunctive subscriptions. Arbitrary subscriptions are transformed to canonical expressions, e.g., DNFs, and are treated as several conjunctive subscriptions. This technique is known from database systems and allows us to apply more efficient filtering algorithms. Since pub/sub systems are the contrary to traditional database systems, it is questionable if filtering several canonical subscriptions is the most efficient and scalable way of dealing with arbitrary subscriptions. In this paper we show that our filtering approach supporting arbitrary boolean subscriptions is more scalable and efficient than current matching algorithms using transformations of subscriptions to DNFs.