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.
Dario Floreano, Bixio Rimoldi, Stefano Rosati, Grégoire Hilaire Marie Heitz, Karol Jacek Kruzelecki