臺灣博碩士論文加值系統

在非結構疊蓋式網路(unstructured peer-to-peer network)上，由於節點(peer)之間彼此隨機連接使得此非結構疊蓋式網路連線跟實體網路上的連線路徑不匹配，導致節點間較長的溝通路徑(communication path)以及實體網路上多餘的網路流量(network traffics)，對此稱之為拓蹼不匹配(topology mismatch)，而先前對於解決拓蹼不匹配問題的研究沒有提出保證效能的結果或者說離最佳解有段不小的差距。
這裡我們提出一個基於抽樣方法(Metropolis-Hastings method)來解決拓蹼匹配的演算法，且藉由觀察我們的分析模型我們所提出的演算法近似最佳解。在我們的演算法中所建立的非結構疊蓋式網路上，任一節點v發佈一個廣播到達其他任一節點u所花的時間近乎於實體網路上這兩節點間連線路徑，而且也同時保証每個節點的廣播範圍(broadcast scope)是以指數成長。經由大量實驗模擬結果顯示，我們的演算法優於當前的各種方法。

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 thesis, 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 Introduction . . . . . . . . . . . . . . . . . . . 1
1.1 Our contributions . . . . . . . . . . . . . . . . 3
1.2 Roadmap . . . . . . . . . . . . . . . . . . . . . 4
2 Related Work . . . . . . . . . . . . . . . . . . . 5
3 Preliminaries . . . . . . . . . . . . . . . . . . . 8
3.1 Broadcast in the Power-Law Delay Model . . . . . 8
3.2 Discussions . . . . . . . . . . . . . . . . . . 13
4 Our Proposal and Implementation . . . . . . . . . 15
4.1 Constructing Wv . . . . . . . . . . . . . . . . 15
4.2 Constructing Bv(1) . . . . . . . . . . . . . . . 19
4.3 Discussions . . . . . . . . . . . . . . . . . . 21
5 Simulations . . . . . . . . . . . . . . . . . . . 23
5.1 Simulation Setting . . . . . . . . . . . . . . . 23
5.1.1 Topology Matching Algorithms . . . . . . . . . 24
5.2 Comparative Study . . . . . . . . . . . . . . . 26
5.2.1 Broadcasting Delay and Scope . . . . . . . . . 26
5.2.2 Effects of Varying the Number of Neighbors . . . . . . . . 29
5.2.3 Effects of Varying the Number of Participating Peers . . . . . . . . . . . . . . . . . . 31
5.3 System Dynamics . . . . . . . . . . . . . . . . 32
5.3.1 Broadcast Delay and Scope . . . . . . . . . . 32
5.3.2 Message Overhead . . . . . . . . . . . . . . . 32
5.4 Impact of Wv and Bv(1) on Our Proposal . . . . . 35
5.4.1 Building Wv and Bv(1) in Parallel . . . . . . 35
5.4.2 Effects of Varying T . . . . . . . . . . . . . 37
6 Summary and Future Work . . . . . . . . . . . . . 40

[1] B. Bollobas. Random Graphs. Cambridge University Press, 2nd edition, 2001.
[2] P. Diaconis and D. Stroock. Geometric Bounds for Eigenvalues of Markov Chains. Ann. Appl. Probab., 1(1):36–61, Feb. 1991.
[3] Gnutella. [online] http://rfc-gnutella.sourceforge.net/.
[4] 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. In Proc. 19th ACM Symp. Operating Systems Principles (SOSP'03), pages 314–329, Oct. 2003.
[5] W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57(1):97–109, Apr. 1970.
[6] H.-C. Hsiao, H. Liao, and C.-C. Huang. Resolving the TopologyMismatch Problem in Unstructured Peer-to-Peer Networks. IEEE Trans. Parallel Distrib. Syst., Feb. 2009. [online] http://doi.ieeecomputersociety.org/10.1109/TPDS.2009.24.
[7] S. Jin and H. Jiang. Novel Approaches to Efficient Flooding Search in Peer-to-Peer Networks. Computer Networks, 51(10):2818–2832, July 2007.
[8] D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-Restricted Metrics. In Proc. 34th ACM Annual Symp. Theory Computing (STOC'02), pages 741–750, May 2002.
[9] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671–680, May 1983.
[10] J. M. Kleinberg. Navigation in a Small World. Nature, 406:845, Aug. 2000.
[11] J. M. Kleinberg. The Small-World Phenomenon: An Algorithm Perspective. In Proc. 32nd ACM Annual Symp. Theory Computing (STOC'00), pages 163–170, May 2000.
[12] X. Liao, H. Jin, Y. Liu, L. M. Ni, and D. Deng. Scalable Live Streaming Service Based on Interoverlay Optimization. IEEE Trans. Parallel Distrib. Syst., 18(12):1663–1674, Dec. 2007.
[13] Y. Liu. A Two-hop Solution to Solving Topology Mismatch. IEEE Trans. Parallel Distrib. Syst., 19(11):1591–1600, Nov. 2008.
[14] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang. Location Awareness in Unstructured Peer-to-Peer Systems. IEEE Trans. Parallel Distrib. Syst., 12(2):163–174, Feb. 2005.
[15] Y. Liu, L. Xiao, and L. M. Ni. Building a Scalable Bipartite P2P Overlay Network. IEEE Trans. Parallel Distrib. Syst., 18(9):1296–1306, Sept. 2007.
[16] A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In Proc. 9th Int'l Workshop Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS'01), pages 346–353, Aug. 2001.
[17] S. Merugu, S. Srinivasan, and E. Zegura. Adding Structure to Unstructured Peer-to-Peer Networks: the Use of Small-World Graphs. J. Parallel Distrib. Comput., 65(2):142–153, Feb. 2005.
[18] 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, 21(6):1087–1092, June 1953.
[19] S. Milgram. The Small-World Problem. Psychology Today, 2:60–67, 1967.
[20] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis, chapter Coupling of Markov Chains, pages 271–294. Cambridge University, 2005.
[21] T. S. Eugene Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-Based Approaches. In Proc. IEEE INFOCOM'02, pages 170–179, June 2002.
[22] V. N. Padmanabhan and L. Subramanian. An Investigation of Geographic Mapping Techniques for Internet Hosts. In Proc. ACM SIGCOMM'01, pages 173–185, Aug. 2001.
[23] G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks. IEEE J. Selected Areas in Comm., 21(6):995–1002, Aug. 2003.
[24] G. Phillips, S. Shenker, and H. Tangmunarunkit. Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law. ACM SIGCOMM Comp. Comm. Review, 29(4):41–51, Oct. 1999.
[25] PlanetLab. http://www.planet-lab.org/.
[26] C. G. Plaxton, R. Rajaraman, and A.W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In Proc. 9th ACM Symp. Parallel Algorithms and Architectures (SPAA'97), pages 311–320, June 1997.
[27] T. Qiu, G. Chen, M. Ye, E. Chan, and B. Y. Zhao. Towards Location-Aware Topology in both Unstructured and Structured P2P Systems. In Proc. 36th Int'l Conf. Parallel Processing (ICPP'07), Sept. 2007.
[28] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. In Proc. ACM SIGCOMM'01, pages 161–172, Aug. 2001.
[29] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-Aware Overlay Construction and Server Selection. In Proc. IEEE INFOCOM'02, pages 1190–1199, June 2002.
[30] M. Ripeanu, I. Foster, and A. Iamnitchi. Mapping the Gnutella Network. IEEE Internet Computing, 6(1):50–57, Jan./Feb. 2002.
[31] S. M. Ross. Introduction to Probability Models, chapter Markov Chains, pages 185–280. Academic Press, 9th edition, 2007.
[32] A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. LNCS 2218, pages 161–172, Nov. 2001.
[33] S. Saroiu, P. K. Gummadi, and S. D. Gribble. Measurement Study of Peer-to-Peer File Sharing Systems. In Proc. Ninth SPIE/ACM Multimedia Computing Networking (MMCN'02). Jan., 2002.
[34] S. Sen and J. Wang. Analyzing Peer-to-Peer Traffic Across Large Networks. IEEE/ACM Trans. Netw., 12(2):219–232, Apr. 2004.
[35] A. Sinclair. Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow. Combin. Probab. Comput., 1(4):351–370, Dec. 1992.
[36] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proc. ACM SIGCOMM'01, pages 149–160, Aug. 2001.
[37] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network Topology Generators: Degree-Based vs. Structural. In Proc. ACM SIGCOMM'02, pages 147–159, Aug. 2002.
[38] D. J. Watts and S. H. Strogatz. Collective Dynamics of Small-World Networks. Nature, 393:440–442, June 1998.
[39] H. Zhang, A. Goel, and R. Govindan. An Empirical Evaluation of Internet Latency Expansion. ACM SIGCOMM Comp. Comm. Review, 35(1):93–97, Jan. 2004.
[40] H. Zhang, A. Goel, and R. Govindan. Improving Lookup Latency in Distributed Hash Table Systems Using Random Sampling. IEEE/ACM Trans. Netw., 13(5):1121–1134, Oct. 2005.
[41] 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., 22(1):41–53, Jan. 2004.