SpiderCast: a scalable interest-aware overlay for topic-based pub/sub communication

ABSTRACT

We introduce SpiderCast, a distributed protocol for constructing scalable churn-resistant overlay topologies for supporting decentralized topic-based pub/sub communication. SpiderCast is designed to effectively tread the balance between average overlay degree and communication cost of event dissemination. It employs a novel coverage-optimizing heuristic in which the nodes utilize partial subscription views (provided by a decentralized membership service) to reduce the average node degree while guaranteeing (with high probability) that the events posted on each topic can be routed solely through the nodes interested in this topic (in other words, the overlay is topic-connected). SpiderCast is unique in maintaining an overlay topology that scales well with the average number of topics a node is subscribed to, assuming the subscriptions are correlated insofar as found in most typical workloads. Furthermore, the degree grows logarithmically in the total number of topics, and slowly decreases as the number of nodes increases.

We show experimentally that, for many practical work-loads, the SpiderCast overlays are both topic-connected and have a low per-topic diameter while requiring each node to maintain a low average number of connections. These properties are satisfied even in very large settings involving up to 10,000 nodes, 1,000 topics, and 70 subscriptions per-node, and under high churn rates. In addition, our results demonstrate that, in a large setting, the average node degree in SpiderCast is at least 45% smaller than in other overlays typically used to support decentralized pub/sub communication (such as e.g., similarity-based, rings-based, and random overlays).

REFERENCES

• 1: André Allavena , Alan Demers , John E. Hopcroft, Correctness of a gossip based membership protocol, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073871]
• 2: E. Anceaume , M. Gradinariu , A. K. Datta , G. Simon , A. Virgillito, A Semantic Overlay for Self- Peer-to-Peer Publish/Subscribe, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.22, July 04-07, 2006 [doi>10.1109/ICDCS.2006.12]
• 3: Sebastien Baehni , Patrick Th. Eugster , Rachid Guerraoui, Data-Aware Multicast, Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04), p.233, June 28-July 01, 2004
• 4: Roberto Baldoni , Carlo Marchetti , Antonino Virgillito , Roman Vitenberg, Content-Based Publish-Subscribe over Structured Overlay Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.437-446, June 06-10, 2005 [doi>10.1109/ICDCS.2005.19]
• 5: Sumeer Bhola , Robert E. Strom , Saurabh Bagchi , Yuanyuan Zhao , Joshua S. Auerbach, Exactly-once Delivery in a Content-based Publish-Subscribe System, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.7-16, June 23-26, 2002
• 6: Kenneth P. Birman, Building Secure and Reliable Network Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1996
• 7: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 8: M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE: a large-scale and decentralized application-level multicast infrastructure. IEEE J. Sel. Areas in Comm., 20(8):1489--1499, 2002.
• 9: R. Chand and P. Felber. Semantic peer-to-peer overlays for publish/subscribe networks. In Euro-Par 2005 Parallel Processing, LNCS, volume 3648, pages 1194--1204. Springer Verlag, 2005.
• 10: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 11: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 12: R. Guerraoui, S. Handurukande, and A.-M. Kermarrec. Gosskip: a gossip-based structured overlay network for efficient content-based filtering. Technical Report IC/2004/95, EPFL, Lausanne, 2004.
• 13: John Jannotti , David K. Gifford , Kirk L. Johnson , M. Frans Kaashoek , James W. O'Toole, Jr., Overcast: reliable multicasting with on overlay network, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.14-14, October 22-25, 2000, San Diego, California
• 14: Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Amin Vahdat, Bullet: high bandwidth data dissemination using an overlay mesh, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 15: Hongzhou Liu , Venugopalan Ramasubramanian , Emin Gün Sirer, Client behavior and feed characteristics of RSS, a publish-subscribe system for web micronews, Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, p.3-3, October 19-21, 2005, Berkeley, CA
• 16: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium on (NCA'04), p.5-14, August 30-September 01, 2004
• 17: Venugopalan Ramasubramanian , Ryan Peterson , Emin Gün Sirer, Corona: a high performance publish-subscribe system for the world wide web, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.2-2, May 08-10, 2006, San Jose, CA
• 18: D. Sandler, A. Mislove, A. Post, and P. Druschel. Feedtree: Sharing web micronews with peer-to-peer event notification. In IPTPS, 2005.
• 19: Chunqiang Tang , Christopher Ward, GoCast: Gossip-Enhanced Overlay Multicast for Fast and Dependable Group Communication, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.140-149, June 28-July 01, 2005 [doi>10.1109/DSN.2005.52]
• 20: Wesley W. Terpstra , Stefan Behnel , Ludger Fiege , Andreas Zeidler , Alejandro P. Buchmann, A peer-to-peer approach to content-based publish/subscribe, Proceedings of the 2nd international workshop on Distributed event-based systems, June 08-08, 2003, San Diego, California [doi>10.1145/966618.966627]
• 21: Y. Tock, N. Naaman, A. Harpaz, and G. Gershinsky. Hierarchical clustering of message flows in a multicast data dissemination system. In 17th IASTED Int'l Conf. Parallel and Distributed Computing and Systems, 2005.
• 22: S. Voulgaris, E. Riviere, A.-M. Kermarrec, and M. van Steen. Sub-2-sub: Self-organizing content-based publish subscribe for dynamic large scale collaborative networks. In IPTPS, 2006.
• 23: N. Wormald. Models of random regular graphs. Surveys in Combinatorics, 276:239--298, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Keywords:
overlay networks, peer-to-peer, pub/sub systems, scalability