Optimizing content-based routers: posets and forests

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous one-to-many and many-to-many information dissemination. Event systems are widely used because asynchronous messaging provides a flexible alternative to RPC. They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. This paper addresses the optimization of content-based routing tables organized using the covering relation and presents novel configurations for improving local and distributed operation. We present the poset-derived forest data structure and variants that perform considerably better under frequent filter additions and removals than existing data structures. The results offer a significant performance increase to currently known covering-based routing mechanisms. Sasu Tarkoma received his M.Sc. and Ph.Lic degrees in Computer Science from the University of Helsinki, Department of Computer Science. He has over 20 scientific publications and has also contributed to several books on mobile middleware. His research interests include distributed computing and middleware. Jaakko Kangasharju is a PhD student at the University of Helsinki and working as a researcher at the Helsinki Institute for Information Technology. His research is concentrated on XML messaging and processing in the mobile wireless environment. He has participated in related standardization efforts at the Object Management Group and the World Wide Web Consortium.