Abstract
Recent developments in the area of peer-to-peer computing show that structured overlay networks implementing distributed hash tables scale well and can serve as infrastructures for Internet scale applications.
We are developing a family of infrastructures, \({{\cal D\!K\!S}}(N,k,f)\), for the construction of peer-to-peer applications. An instance of \({{\cal D\!K\!S}}(N,k,f)\) is an overlay network that implements a distributed hash table and which has a number of desirable properties: low cost of communication, scalability, logarithmic lookup length, fault-tolerance and strong guarantees of locating any data item that was inserted in the system.
In this paper, we show how multicast is achieved in \({{\cal D\!K\!S}}(N,k,f)\) overlay networks. The design presented here is attractive in three main respects. First, members of a multicast group self-organize in an instance of \({{\cal D\!K\!S}}(N,k,f)\) in a way that allows co-existence of groups of different sizes, degree of fault-tolerance, and maintenance cost, thereby, providing flexibility. Second, each member of a group can multicast, rather than having single source multicast. Third, within a group, dissemination of a multicast message is optimal under normal system operation in the sense that there are no redundant messages despite the presence of outdated routing information.
This work was funded by the European project IST-2001-32234, PEPITO and Vinnova PPC project in Sweden.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alima, L.O., El-Ansary, S., Brand, P., Haridi, S.: DKS(N, k, f): A Family of Low Communication, Scalable and Fault-Tolerant Infrastructures for P2P Applications. In: 3rd International Symposium on Cluster Computing and the Grid - CCGRID 2003, Tokyo, Japan (May 2003)
Banerjee, S., Bhattacharjee, B., Kommareddy, C.: Scalable application layer multicast. Technical Report UMIACS-TR 2002-53 and CS-TR 4373 (2002)
Castro, M., Druschel, P., Kermarrec, A.-M., Rowstron, A.: SCRIBE: A largescale and decentralised application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications (2002)
Ghodsi, A., Alima, L.O., El-Ansary, S., Brand, P., Haridi, S.: Self-Correcting Broadcast in Distributed Hash Tables. In: 15th IASTED International Conference, Parallel and Distributed Computing and Systems, Marina del Rey, CA, USA (November 2003)
Mozart Consortium (2003), http://www.mozart-oz.org
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A Scalable Content Addressable Network. Technical Report TR-00-010, Berkeley, CA (2000)
Ratnasamy, S., Handley, M., Karp, R., Shenker, S.: Application level Multicast using Content-Addressable Networks. In: Crowcroft, J., Hofmann, M. (eds.) NGC 2001. LNCS, vol. 2233, p. 14. Springer, Heidelberg (2001)
Rowstron, A., Druschel, P.: Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol. 2218, p. 329. Springer, Heidelberg (2001), citeseer.nj.nec.com/rowstron01pastry.html
Stoica, I., Morris, R., Karger, D., Kaashoek, M., Balakrishnan, H.: Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In: ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149–160 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alima, L.O., Ghodsi, A., Brand, P., Haridi, S. (2004). Multicast in \({{\cal D\!K\!S}}(N,k,f)\) Overlay Networks. In: Papatriantafilou, M., Hunel, P. (eds) Principles of Distributed Systems. OPODIS 2003. Lecture Notes in Computer Science, vol 3144. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27860-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-27860-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22667-3
Online ISBN: 978-3-540-27860-3
eBook Packages: Springer Book Archive