Pruning subscriptions in distributed publish/subscribe systems
Sven Bittner, Annika Hinze · 2006
Publish/subscribe systems utilize filter algorithms to determine all subscriptions matching incoming event messages. To distribute such services, subscriptions are forwarded to several filter components. This approach allows for an application of routing algo-rithms that selectively forward event messages to only a subset of filter components. Beneficial effects of this scheme include decreasing network and compu-tational load in single filter components. So far, we can find routing optimizations that ex-ploit coverings among subscriptions or utilize sub-scription merging strategies. Generally, such opti-mizations aim at reducing the amount of subscrip-tions forwarded to filter components, which decreases their computational load. This might in turn result in an increasing number of event messages routed through the network. However, current optimization strategies only work on restrictive conjunctive subscriptions and can-not be extended to efficiently support arbitrary sub-scriptions. Furthermore, it is not possible to apply covering and perfect merging strategies in all appli-cation scenarios due to the strong dependency of these approaches on actually registered subscriptions. In this paper, we present a novel optimization ap-proach, subscription generalization, to decrease the filtering overhead in publish/subscribe systems. Our approach is based on selectivities of subscriptions and can be utilized for all kinds of subscriptions includ-ing arbitrary Boolean and conjunctive subscriptions. We propose a simple subscription generalization al-gorithm and show an evaluation of the results of a first series of experiments proving the usefulness of our approach.