| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Near-Optimal Algorithm Attacking the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks
July 2010 (vol. 21 no. 7)
pp. 983-997
Hao Liao, National Cheng-Kung University, Tainan
In an unstructured peer-to-peer (P2P) network (e.g., Gnutella), participating peers choose their neighbors randomly such that the resultant P2P network mismatches its underlying physical network, resulting in the lengthy communication between the peers and redundant network traffics generated in the underlying network. Previous solutions to the topology mismatch problem in the literature either have no performance guarantees or are far from the optimum. In this paper, we propose a novel topology matching algorithm based on the Metropolis-Hastings method. Our proposal is guided by our insight analytical model and is close to the optimal design. Specifically, we show that our proposal constructs an unstructured P2P network in which a broadcast message, originated by any node v, reaches any other node u by taking approximately the only physical end-to-end delay between v and u. In addition, our design guarantees the exponential broadcast scope. We verify our solution through extensive simulations and show that our proposal considerably outperforms state-of-the-art solutions.
[1] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A Scalable Content-Addressable Network," Proc. ACM SIGCOMM '01, pp. 161-172, Aug. 2001.
[2] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications," Proc. ACM SIGCOMM '01, pp. 149-160, Aug. 2001.
[3] A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems," Lecture Notes in Computer Science, pp. 161-172, Springer, Nov. 2001.
[4] 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. 2004.
[5] X. Liao, H. Jin, Y. Liu, L.M. Ni, and D. Deng, "Scalable Live Streaming Service Based on Interoverlay Optimization," IEEE Trans. Parallel and Distributed Systems, vol. 18, no. 12, pp. 1663-1674, Dec. 2007.
[6] M. Ripeanu, I. Foster, and A. Iamnitchi, "Mapping the Gnutella Network," IEEE Internet Computing, vol. 6, no. 1, pp. 50-57, Jan./Feb. 2002.
[7] S. Sen and J. Wang, "Analyzing Peer-to-Peer Traffic Across Large Networks," IEEE/ACM Trans. Networking, vol. 12, no. 2, pp. 219-232, Apr. 2004.
[8] Gnutella, http:/rfc-gnutella.sourceforge.net/, 2010.
[9] Y. Liu, L. Xiao, X. Liu, L.M. Ni, and X. Zhang, "Location Awareness in Unstructured Peer-to-Peer Systems," IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 2, pp. 163-174, Feb. 2005.
[10] Y. Liu, "A Two-Hop Solution to Solving Topology Mismatch," IEEE Trans. Parallel and Distributed Systems, vol. 19, no. 11, pp. 1591-1600, Nov. 2008.
[11] Y. Liu, L. Xiao, and L.M. Ni, "Building a Scalable Bipartite P2P Overlay Network," IEEE Trans. Parallel and Distributed Systems, vol. 18, no. 9, pp. 1296-1306, Sept. 2007.
[12] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, "Equations of State Calculations by Fast Computing Machines," J. Chemical Physics, vol. 21, no. 6, pp. 1087-1092, June 1953.
[13] W.K. Hastings, "Monte Carlo Sampling Methods Using Markov Chains and Their Applications," Biometrika, vol. 57, no. 1, pp. 97-109, Apr. 1970.
[14] H.-C. Hsiao, H. Liao, and C.-C. Huang, "Resolving the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks," IEEE Trans. Parallel and Distributed Systems, vol. 20, no. 11, pp. 1668-1681, http://doi.ieeecomputersociety.org/10.1109 TPDS.2009.24, Nov. 2009.
[15] J.M. Kleinberg, "Navigation in a Small World," Nature, vol. 406, p. 845, Aug. 2000.
[16] S. Milgram, "The Small-World Problem," Psychology Today, vol. 2, pp. 60-67, 1967.
[17] D.J. Watts and S.H. Strogatz, "Collective Dynamics of Small-World Networks," Nature, vol. 393, pp. 440-442, June 1998.
[18] S. Merugu, S. Srinivasan, and E. Zegura, "Adding Structure to Unstructured Peer-to-Peer Networks: The Use of Small-World Graphs," J. Parallel and Distributed Computing, vol. 65, no. 2, pp. 142-153, Feb. 2005.
[19] J.M. Kleinberg, "The Small-World Phenomenon: An Algorithm Perspective," Proc. 32nd ACM Ann. Symp. Theory Computing (STOC '00), pp. 163-170, May 2000.
[20] V.N. Padmanabhan and L. Subramanian, "An Investigation of Geographic Mapping Techniques for Internet Hosts," Proc. ACM SIGCOMM '01, pp. 173-185, Aug. 2001.
[21] T.S.E. Ng and H. Zhang, "Predicting Internet Network Distance with Coordinates-Based Approaches," Proc. IEEE INFOCOM '02, pp. 170-179, June 2002.
[22] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topologically-Aware Overlay Construction and Server Selection," Proc. IEEE INFOCOM '02, pp. 1190-1199, June 2002.
[23] T. Qiu, G. Chen, M. Ye, E. Chan, and B.Y. Zhao, "Towards Location-Aware Topology in Both Unstructured and Structured P2P Systems," Proc. 36th Int'l Conf. Parallel Processing (ICPP '07), Sept. 2007.
[24] H. Zhang, A. Goel, and R. Govindan, "An Empirical Evaluation of Internet Latency Expansion," ACM SIGCOMM Computer Comm. Rev., vol. 35, no. 1, pp. 93-97, Jan. 2004.
[25] H. Zhang, A. Goel, and R. Govindan, "Improving Lookup Latency in Distributed Hash Table Systems Using Random Sampling," IEEE/ACM Trans. Networking, vol. 13, no. 5, pp. 1121-1134, Oct. 2005.
[26] G. Phillips, S. Shenker, and H. Tangmunarunkit, "Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law," ACM SIGCOMM Computer Comm. Rev., vol. 29, no. 4, pp. 41-51, Oct. 1999.
[27] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Network Topology Generators: Degree-Based vs. Structural," Proc. ACM SIGCOMM '02, pp. 147-159, Aug. 2002.
[28] C.G. Plaxton, R. Rajaraman, and A.W. Richa, "Accessing Nearby Copies of Replicated Objects in a Distributed Environment," Proc. Ninth ACM Symp. Parallel Algorithms and Architectures (SPAA '97), pp. 311-320, June 1997.
[29] D.R. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted Metrics," Proc. 34th ACM Ann. Symp. Theory Computing (STOC '02), pp. 741-750, May 2002.
[30] S.M. Ross, "Markov Chains," Introduction to Probability Models, ninth ed., pp. 185-280, Academic Press, 2007.
[31] M. Mitzenmacher and E. Upfal, "Coupling of Markov Chains," Probability and Computing: Randomized Algorithms and Probabilistic Analysis, pp. 271-294, Cambridge Univ. Press, 2005.
[32] P. Diaconis and D. Stroock, "Geometric Bounds for Eigenvalues of Markov Chains," Annals of Applied Probability, vol. 1, no. 1, pp. 36-61, Feb. 1991.
[33] A. Sinclair, "Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow," Combinatorics, Probability and Computing, vol. 1, no. 4, pp. 351-370, Dec. 1992.
[34] B. Bollobás, Random Graphs, second ed. Cambridge Univ. Press, 2001.
[35] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[36] S. Saroiu, P.K. Gummadi, and S.D. Gribble, "Measurement Study of Peer-to-Peer File Sharing Systems," Proc. Ninth SPIE/ACM Multimedia Computing Networking (MMCN '02), Jan. 2002.
[37] K.P. Gummadi, R.J. Dunn, S. Saroiu, S.D. Gribble, H.M. Levy, and J. Zahorjan, "Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload," Proc. 19th ACM Symp. Operating Systems Principles (SOSP '03), pp. 314-329, Oct. 2003.
[38] G. Pandurangan, P. Raghavan, and E. Upfal, "Building Low-Diameter Peer-to-Peer Networks," IEEE J. Selected Areas in Comm., vol. 21, no. 6, pp. 995-1002, Aug. 2003.
[39] S. Jin and H. Jiang, "Novel Approaches to Efficient Flooding Search in Peer-to-Peer Networks," Computer Networks, vol. 51, no. 10, pp. 2818-2832, July 2007.
[40] A. Medina, A. Lakhina, I. Matta, and J. Byers, "BRITE: An Approach to Universal Topology Generation," Proc. Ninth Int'l Workshop Modeling, Analysis, and Simulation of Computer and Telecomm. Systems (MASCOTS '01), pp. 346-353, Aug. 2001.
[41] PlanetLab, http:/www.planet-lab.org/, 2010.
[42] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, "Search and Replication in Unstructured Peer-to-Peer Networks," Proc. ACM Int'l Conf. Supercomputing (ICS '02), pp. 84-95, June 2002.
[43] K. Sripanidkulchai, "The Popularity of Gnutella Queries and Its Implications on Scalability," O'REILLY P2P openp2p.com, http://www.oreillynet.com/topics/p2pgnutella , 2010.
[44] E. Cohen and S. Shenker, "Replication Strategies in Unstructured Peer-to-Peer Networks," Proc. ACM SIGCOMM '02, pp. 177-190, Aug. 2002.
Index Terms:
Unstructured peer-to-peer systems, topology mismatch, location awareness, broadcast.
Citation:
Hung-Chang Hsiao, Hao Liao, Po-Shen Yeh, "A Near-Optimal Algorithm Attacking the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 7, pp. 983-997, July 2010, doi:10.1109/TPDS.2009.160
