×

A peer-to-peer expressway over Chord. (English) Zbl 1134.68312

Summary: We introduce an auxiliary coarse-grained routing layer (an expressway) on Chord, a DHT based structured peer-to-peer system. With the assumption that nodes in the system have different resource capacities such as storages and bandwidths, powerful (high connectivity and bandwidth) nodes can join the expressway to perform fast routing. We design the logical structure of an expressway overlay.We focus on the design and analysis of the logical structure of the expressway overlay that is parameterized by a characteristic called the forwarding power \(p\). Expressway nodes maintain more routing entries that can forward requests with a longer per hop distance than the underlying system. The expressway defers the “last mile” fine-grained routing to the underlying system. We also propose an event-based notification for membership and routing entry management on the expressway. Our initial experimental results of an expressway with a forwarding power of 4 show that the average logical path length of the system when over 20% of nodes join the expressway is about the same as when every node joins the expressway. The theoretical analysis shows that the logical routing path lengths of the system improve up to \(1-2(\frac {p-1}{p})\log _p 2\). The system requires \(O(\log ^{2}r)\) messages to update all expressway routing entries when a node joins or leaves the system, where \(r\) is the number of expressway nodes.

MSC:

68M10 Network design and communication in computer systems

Software:

Pastry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, H. Balakrishman, Chord: A scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking 11 (1); I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, H. Balakrishman, Chord: A scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking 11 (1)
[2] Rowstron, A. I.T.; Druschel, P., 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 (2001), Springer-Verlag), 329-350 · Zbl 1051.68788
[3] B. Zhao, L. Huang, J. Stribling, S.C. Rhea, A.D. Joseph, J.D. Kubiatowicz, Tapestry: A resilient global-scale overlay for service deployment, IEEE Journal on Selected Areas in Communications 22 (1); B. Zhao, L. Huang, J. Stribling, S.C. Rhea, A.D. Joseph, J.D. Kubiatowicz, Tapestry: A resilient global-scale overlay for service deployment, IEEE Journal on Selected Areas in Communications 22 (1)
[4] S. Ratnasamy, P. Francis, M. Handley, R. Karp, A scalable content-addressable network, in: Proceedings of the ACM SIGCOMM, 2001, pp. 161-172; S. Ratnasamy, P. Francis, M. Handley, R. Karp, A scalable content-addressable network, in: Proceedings of the ACM SIGCOMM, 2001, pp. 161-172
[5] A. Gupta, B. Liskov, R. Rodrigues, One hop lookups for peer-to-peer overlays, in: Proceedings of HotOS IX: The 9th Workshop on Hot Topics in Operation Systems, 2003; A. Gupta, B. Liskov, R. Rodrigues, One hop lookups for peer-to-peer overlays, in: Proceedings of HotOS IX: The 9th Workshop on Hot Topics in Operation Systems, 2003
[6] J. Hu, M. Li, W. Zheng, D. Wang, N. Ning, H. Dong, Smart-Boa: Constructing p2p overlay network in the heterogeneous internet using irregular routing tables, in: Proceeding of the 3rd International Workshop on Peer-to-Peer System, IPTPS’04, 2004; J. Hu, M. Li, W. Zheng, D. Wang, N. Ning, H. Dong, Smart-Boa: Constructing p2p overlay network in the heterogeneous internet using irregular routing tables, in: Proceeding of the 3rd International Workshop on Peer-to-Peer System, IPTPS’04, 2004
[7] Z. Xu, Z. Zhang, Building low-maintenance expressways for P2P systems, Technical Report, Internet System and Storage Laboratory, HP Laboratories Palo Alto, 2002; Z. Xu, Z. Zhang, Building low-maintenance expressways for P2P systems, Technical Report, Internet System and Storage Laboratory, HP Laboratories Palo Alto, 2002
[8] Z. Xu, M. Mahalingam, M. Karlsson, Turning heterogeneity into an advantage in overlay routing, in: Proceeding of The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE INFOCOM, 2003; Z. Xu, M. Mahalingam, M. Karlsson, Turning heterogeneity into an advantage in overlay routing, in: Proceeding of The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE INFOCOM, 2003
[9] B. Zhao, Y. Duan, L. Huang, A. Joseph, J. Kubiatowicz, Brocade: Landmark routing on overlay networks, in: Proceedings of 1st International Workshop on Peer-to-Peer Systems, IPTPS, 2002; B. Zhao, Y. Duan, L. Huang, A. Joseph, J. Kubiatowicz, Brocade: Landmark routing on overlay networks, in: Proceedings of 1st International Workshop on Peer-to-Peer Systems, IPTPS, 2002 · Zbl 1014.68617
[10] B.Y. Zhao, J.D. Kubiatowicz, A.D. Joseph, Tapestry: An infrastructure for fault-tolerant wide-area location and routing, Technical Report, University of California at Berkeley, 2001; B.Y. Zhao, J.D. Kubiatowicz, A.D. Joseph, Tapestry: An infrastructure for fault-tolerant wide-area location and routing, Technical Report, University of California at Berkeley, 2001
[11] Loguinov, D.; Kumar, A.; Rai, V.; Ganesh, S., Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience, (SIGCOMM’03, Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (2003), ACM Press: ACM Press New York, NY, USA), 395-406
[12] D. Liben-Nowell, H. Balakrishnan, D. Karger, Analysis of the evolution of peer-to-peer systems, in: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, 2002; D. Liben-Nowell, H. Balakrishnan, D. Karger, Analysis of the evolution of peer-to-peer systems, in: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, 2002 · Zbl 1292.68014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.