GosSkip: a Gossip-based Structured Overlay Network for Efficient Content-based Filtering

It is appealing to implement publish/subscribe systems in a peer to peer (P2P) manner to circumvent the scalability issues of broker-based (semi-decentralized) systems and simplify the deployment. While existing P2P generic infrastructures provide a scalable support for topic-based publish-subscribe systems, they are not well adapted to content-based ones. In this paper, we advocate the need for dedicated overlay networks -where the overlay structure reflects the actual structure of the underlying application properties- to implement efficient content-based publish-subscribe infrastructures. We propose a new scalable P2P event filtering mechanism where filters are arranged according to a dictionary-based semantics. This structured overlay, which we call \textit{GosSkip}, relies on gossip messages to construct a structure eventually similar to a perfect Skip list, preserving the semantic locality of the items stored in the overlay. In GosSkip, events are delivered to matching subscriptions in O(log N) routing hops, N being the total number of subscriptions. The very same approach can be extended to support range queries. Preliminary implementation results based on a real P2P trace convey the scalability and the efficiency of the approach both in static and dynamic scenarios.