| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
SCALLOP: A Scalable and Load-Balanced Peer-to-Peer Lookup Protocol
May 2006 (vol. 17 no. 5)
pp. 419-433
Abstract—A number of structured peer-to-peer (P2P) lookup protocols have been proposed recently. A P2P lookup protocol routes a lookup request to its target node in a P2P distributed system. Existing protocols achieve balanced routing traffic among nodes by assuming that lookup requests are evenly targeted at every node. However, when lookup requests concentrate on a few nodes simultaneously, these nodes become hot spots. Due to uneven routing patterns in existing protocols, hot spots cause unbalanced routing traffic which leads to routing bottlenecks. In this paper, we present a novel structured P2P lookup protocol called SCALLOP that delivers balanced routing and avoids routing bottlenecks at occurrences of hot spots. Among existing protocols, SCALLOP is the first one to accomplish this goal at the fundamental nature of a routing protocol. SCALLOP achieves balanced routing by uniquely constructing a balanced lookup tree for each node. The balanced tree evenly distributes routing traffic among sibling nodes and, therefore, avoids or reduces routing bottlenecks. In addition, as a load-balanced protocol, SCALLOP delivers asymptotically optimal lookup performance at the tradeoff between routing path and routing table size. We conducted a set of simulations to demonstrate the effectiveness of SCALLOP. The results show that, compared with a most-referenced and representative structured P2P lookup protocol and a graph-based extension of this protocol, SCALLOP significantly reduces routing bottlenecks while all three protocols deliver comparable lookup performance.
[1] W.J. Bolosky, J.R. Douceur, D. Ely, and M. Theimer, “Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs,” Proc. ACM SIGMETRICS, pp. 34-43, June 2000.
[2] J.W. Byers, J. Considine, and M. Mitzenmacher, “Simple Load Balancing for Distributed Hash Tables,” Proc. Second Int'l Workshop Peer-to-Peer Systems (IPTPS), pp. 80-87, 2003.
[3] M. Cai, A. Chervenak, and M. Frank, “A Peer-to-Peer Replica Location Service Based on A Distributed Hash Table,” Proc. ACM/IEEE SC 2004 Conf., 2004.
[4] J.C.Y. Chou, T.-Y. Huang, and K.-L. Huang, “SCALLOP: A Scalable and Load-Balanced Peer-to-Peer Lookup Protocol for High-Performance Distributed System,” Proc. Fourth IEEE/ACM Int'l Symp. Cluster Computing and the Grid (CCGrid), Apr. 2004.
[5] I. Clarke, O. Sandberg, B. Wiley, and T.W. Hong, “Freenet: A Distributed Anonymous Information Storage and Retrieval System,” Lecture Notes in Computer Science, vol. 2009, pp. 46-66, 2001.
[6] A. Fiat and J. Saia, “Censorship Resistant Peer-to-Peer Content Addressable Networks,” Proc. Symp. Discrete Algorithms, pp. 94-103, 2002.
[7] P. Fraigniaud and P. Gauron, “An Overview of the Content-Addressable Network D2B,” Proc. 23rd Ann. ACM Symp. Principles of Distributed Computing (PODC), July 2003.
[8] F. Dabek, M. Frans Kaashoek, D. Karger, R. Morris, and I. Stoica, “Wide-Area Cooperative Storage with CFS,” Proc. 18th ACM Symp. Operating Systems Principles (SOSP), pp. 202-215, Oct. 2001.
[9] Gnutella, http:/gnutella.wego.com/, 2006.
[10] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, “Load Balancing in Dynamic Structured P2P Systems,” Proc. IEEE INFOCOM, 2004.
[11] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, “Load Balancing in Dynamic Structured P2P Systems,” Proc. IEEE INFOCOMM, 2004.
[12] A. Gupta, B. Liskov, and R. Rodrigues, “Efficient Routing for Peer-to-Peer Overlays,” Proc. First Symp. Networked Systems Design and Implementation, 2004.
[13] S. Hazel and B. Wiley, “AChord: A Variant of the Chord Lookup Service for Use in Censorship Resistant Peer-to-Peer Publishing Systems,” Proc. Int'l Workshop Peer-to-Peer Systems (IPTPS), Mar. 2002.
[14] M. Frans Kaashoek and D.R. Karger, “Koorde: A Simple Degree-Optimal Distributed Hash Table,” Proc. Int'l Workshop Peer-to-Peer Systems (IPTPS), Feb. 2003.
[15] D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,” Proc. ACM Symp. Theory of Computing, pp. 654-663, May 1997.
[16] KaZaA, KaZaA file sharing network, http:/www.kazaa.com/, 2002.
[17] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, “OceanStore: An Architecture for Global-Scale Persistent Storage,” Proc. Ninth Int'l Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 190-201, Nov. 2000.
[18] A. Kumar, S. Merugu, J. Xu, and X. Yu, “Ulysses: A Robust, Low-Dimeter, Low-Latency Peer-to-Peer Network,” Proc. 11th IEEE Int'l Conf. Network Protocols, pp. 258-267, Nov. 2003.
[19] K. Laskshminaraynan, A.R. Rao, S. Surana, R. Karp, and I. Stoica, “Hyperchord: A Peer-to-Peer Data Location Architecture,” Technical Report CS-021208, UC Berkeley, Dec. 2001.
[20] D. Loguinov, A. Kumar, V. Rai, and S. Ganesh, “Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience,” Proc. ACM SIGCOMM, pp. 395-406, Aug. 2003.
[21] D. Malkhi, M. Naor, and D. Ratajczak, “Viceroy: A Scalable and Dynamic Emulation of the Butterfly,” Proc. 21st Ann. ACM Symp. Principles of Distributed Computing (PODC), pp. 183-192, July 2002.
[22] Morpheus, Morpheus file sharing network, 2002, http:/www.musiccity.com/.
[23] M. Naor and U. Wieder, “A Simple Fault Tolerant Distributed Hash Table,” Proc. Int'l Workshop Peer-to-Peer Systems (IPTPS), Feb. 2003.
[24] Napster, http:/www.napster.com/, 2006.
[25] G. Pandurangan, “Building Low-Diameter P2P Networks,” Proc. 42nd IEEE Symp. Foundations of Computer Science, pp. 492-499, 2001.
[26] C.G. Plaxton, R. Rajaraman, and A.W. Richa, “Accessing Nearby Copies of Replicated Objects in a Distributed Environment,” Proc. ACM Symp. Parallel Algorithms and Architectures, pp. 311-320, 1997.
[27] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, “Load Balancing in Structured P2P Systems,” Proc. Second Int'l Workshop Peer-to-Peer Systems (IPTPS), 2003.
[28] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content Addressable Network,” Proc. ACM SIGCOMM Conf., pp. 161-172, Aug. 2001.
[29] A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems,” Lecture Notes in Computer Science, vol. 2218, pp. 329-340, 2001.
[30] J. Saia, A. Fiat, S.D. Gribble, A.R. Karlin, and S. Saroiu, “Dynamically Fault-Tolerant Content Addressable Networks,” Proc. Int'l Workshop Peer-to-Peer Systems (IPTPS), Mar. 2002.
[31] I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,” Proc. ACM SIGCOMM Conf., pp. 149-160, Sept. 2001.
[32] I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,” Technical Report TR-819, MIT LCS, Mar. 2001.
[33] J. Xu, “On the Fundamental of Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks,” Proc. IEEE Infocom Conf., pp. 151-163, Jan. 2003.
[34] B.Y. Zhao, L. Huang, J. Stribling, S.C. Rhea, A.D. Joseph, and J.D. Kubiatowicz, “Tapestry: A Resilient Global-scale Overlay for Service Deployment,” IEEE J. Selected Areas in Comm., vol. 22, no. 1, pp. 41-53, Jan. 2003.
[35] B.Y. Zhao, J.D. Kubiatowicz, and A.D. Joseph, “Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing,” Technical Report UCB/CSD-01-1141, UC Berkeley, Apr. 2001.
Index Terms:
Peer-to-peer distributed systems, lookup protocols, routing bottlenecks, balanced routing.
Citation:
Jerry C.-Y. Chou, Tai-Yi Huang, Kuang-Li Huang, Tsung-Yen Chen, "SCALLOP: A Scalable and Load-Balanced Peer-to-Peer Lookup Protocol," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 5, pp. 419-433, May 2006, doi:10.1109/TPDS.2006.66
