TERA: topic-based event routing for peer-to-peer architectures

ABSTRACT

The completely decoupled interaction model offered by the publish/subscribe communication paradigm perfectly suits the interoperability needs of todays large-scale, dynamic, peer-to-peer applications. The unmanaged environments, where these applications are expected to work, pose a series of problems (potentially wide number of partipants, low-reliability of nodes, absence of a centralized authority, etc.) that severely limit the scalability of existing approaches which were originally thought for supporting distributed applications built on the top of static and managed environments. In this paper we propose an architecture for implementing the topic-based publish/subscribe paradigm in large scale peer-to-peer systems. The architecture is based on clustering peers subscribed to the same topic. The major novelty of this architecture lies in the mechanism employed to bring events from the publisher to the cluster (namely outer-cluster routing). The evaluation shows that this mechanism for outer-cluster routing has a probability to bring events to the destination cluster very close to 1 while keeping small the involved number of out-of-cluster peers. Finally, the overall architecture is shown to be scalable along several fundamental dimensions like number of participants, subscriptions, and to exhibit a fair load distribution (load distribution closely follows the distribution of subscriptions on nodes).

REFERENCES

• 1: Ioannis Aekaterinidis , Peter Triantafillou, PastryStrings: A Comprehensive Content-Based Publish/Subscribe DHT Network, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.23, July 04-07, 2006 [doi>10.1109/ICDCS.2006.63]
• 2: 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]
• 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: Roberto Baldoni, Roberto Beraldi, Vivien Quéma, Leonardo Querzoni, and Sara Tucci-Piergiovanni, TERA: Topic-based event routing for peer-to-peer architectures, Tech. Report 2/07, Dipartimento Informatica e Sistemistica "A. Ruberti" - Sapienza, Università di Roma, 2007.
• 6: An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.262, May 31-June 04, 1999
• 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: Fengyun Cao and J. Pal Singh, Efficient event routing in content-based publish-subscribe service networks, Proceedings of the 23rd IEEE Conference on Computer Communications (INFOCOM) (Hong Kong, China), vol. 2, IEEE, Washington, 7--11 March 2004, pp. 929--940.
• 9: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 10: A. Carzaniga and A. L. Wolf, A benchmark suite for distributed publish/subscribe systems, Tech. Report CU-CS-927-02, Software Engineering Research Laboratory, Department of Computer Science, University of Colorado at Boulder, 2002.
• 11: M. Castro, P. Druschel, A. Kermarrec, and A. Rowston, Scribe: A large-scale and decentralized application-level multicast infrastructure, IEEE Journal on Selected Areas in Communications <b>20</b> (October 2002), no. 8.
• 12: 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]
• 13: Patrick Th. Eugster , Pascal A. Felber , Rachid Guerraoui , Anne-Marie Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys (CSUR), v.35 n.2, p.114-131, June 2003 [doi>10.1145/857076.857078]
• 14: I. Gupta, K. Birman, and R. van Renesse, Fighting fire with fire: using randomized gossip to combat stochastic scalability limits, Journal of Quality and Reliability Engineering International (2002).
• 15: Márk Jelasity, Gian Paolo Jesi, Alberto Montresor, and Spyros Voulgaris, Peersim, http://peersim.sourceforge.net/.
• 16: Márk Jelasity , Alberto Montresor, Epidemic-Style Proactive Aggregation in Large Overlay Networks, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.102-109, March 24-26, 2004
• 17: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 18: Dionysios Kostoulas , Dimitrios Psaltoulis , Indranil Gupta , Ken Birman , Al Demers, Decentralized Schemes for Size Estimation in Large and Dynamic Groups, Proceedings of the Fourth IEEE International Symposium on Network Computing and Applications, p.41-48, July 27-29, 2005 [doi>10.1109/NCA.2005.15]
• 19: Laurent Massoulié , Erwan Le Merrer , Anne-Marie Kermarrec , Ayalvadi Ganesh, Peer counting and sampling in overlay networks: random walk methods, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146402]
• 20: E. Le Merrer, A-M. Kermarrec, and L. Massoulie, Peer to peer size estimation in large and dynamic networks: A comparative study, Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, 2006, pp. 7--17.
• 21: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 22: D. Psaltoulis, D. Kostoulas, I. Gupta, K. Birman, and A. Demers, Practical algorithms for size estimation in large and dynamic groups, Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2005.
• 23: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 24: Anton Riabov , Zhen Liu , Joel L. Wolf , Philip S. Yu , Li Zhang, Clustering Algorithms for Content-Based Publication-Subscription Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.133, July 02-05, 2002
• 25: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 26: S. Voulgaris, D. Gavidia, and M. van Steen, CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays, Journal of Network and Systems Management <b>13</b> (2005), no. 2.
• 27: Spyros Voulgaris, Etienne Rivière, Anne-Marie Kermarrec, and Maarten van Steen, Sub-2-sub: Self-organizing content-based publish and subscribe for dynamic and large scale collaborative networks, Research Report RR5772, INRIA, Rennes, France, December 2005.
• 28: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. Kubiatowicz, Tapestry: A Resilient Global-scale Overlay for Service Deployment, IEEE Journal on Selected Areas in Communications <b>22</b> (2003), no. 1, 41--53.
• 29: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

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

Keywords:
data distribution, gossip-based algorithms, publish-subscribe