Internet Scale String Attribute Publish/Subscribe Data Networks

Abstract

With this work we aim to make a threefold contribution. We first address the issue of supporting efficiently queries over string-attributes involving prefix, suffix, containment, and equality operators in large-scale data networks. Our first design decision is to employ distributed hash tables (DHTs) for the data network's topology, harnessing their desirable properties. Our next design decision is to derive DHT-independent solutions, treating DHT as a black box. Second, we exploit this infrastructure to develop efficient content based publish/subscribe systems. The main contribution here are algorithms for the efficient processing of queries (subscriptions) and events (publications). Specifically , we show that our subscription processing algorithms require O(logN) messages for a N-node network, and our event processing algorithms require O(l × logN) messages (with l being the average string length). Third, we develop algorithms for optimizing the processing of multi-dimensional events, involving several string attributes. Further to our analysis, we provide simulation-based experiments showing promising performance results in terms of number of messages, required bandwidth, load balancing, and response times.