臺灣博碩士論文加值系統

　　資源共享、協同運算、訊息通信為點對點網路系統相當便利且廣泛且之應用。其中尤以非結構化之點對點網路架構，因其具備：擁有較佳的並行處理能力、大幅提昇資料交換效能、不需建構伺服器等軟硬體裝置、維護容易等重要特性，使得該網路架構成為點對點網路通用且普及之系統型態。然而，非結構化點對點網路針對資源搜尋機制所採用之洪水搜尋演算法(Flooding)，雖然擁有實作容易且簡單快速之搜尋特性，但卻為網路頻寬帶來極大的負擔及浪費；另一方面，現存之相關改進演算法雖有其優點及特定範圍的改善，但仍無法兼顧充份節省頻寬與提昇搜尋效能之目標。因此，本研究之目的即針對非結構化點對點網路搜尋機制之問題，提昇一套改進機制作為解決方案，突破原有架構之瓶頸與限制，建立資源共享與網路溝通之便利管道。
　　本研究之架構，主要包含：1).非結構化點對點網路架構之觀察分析：根據不同大小規模之網路拓撲，從中分析觀察現存問題之狀況與其嚴重程度，並針對各規模之網路系統進行統計分析以建立改善指標。2).非結構化點對點網路搜尋機制之建立：針對現存之搜尋演算法提出一套改進機制，提昇搜尋效能與節省頻寬使用，以維持非結構化點對點網路系統之最佳狀態。3).數理效能分析：以數理模型針對特定相關搜尋演算法進行推測與評估，以利相關系統實測與效能評比進行預估之參考。4).系統實測與特定網路規模之效能評估。
　　實驗中，針對不同大小網路規模進行相關搜尋演算法之評比與觀察，於各項效能評比指標裏，本研究提出之搜尋機制皆有相當突出與顯著之效能改善；尤其與傳統洪水搜尋演算法相比，本研究成果將可改善80%之頻寬浪費。無論在理論以及實驗分析之結果，皆証明本研究所提出搜尋機制之有效性與實用性。

　　Peer-to-Peer (P2P) network systems are convenient and widely used because they enable data sharing, enable co-processing, and promote communication. This is especially true for unstructured P2P network systems that are easy to maintain, optimize parallel processing ability, and greatly increase data exchange all without requiring a customized server or specialized equipment. These qualities have made unstructured P2P networks common and widely used.
　　However, unstructured P2P network systems search data by using the “flooding” mechanism, and, even though the flooding mechanism is easy to use and fast, it requires a larger scale network, causes enormous traffic overhead, and wastes bandwidth. Recent improvements made to the flooding mechanism have provided limited advantages, but still cannot save bandwidth while maintaining good search performance.
　　The purpose of this study is to address these problems of the unstructured P2P network system search mechanism by providing an improved search mechanism which overcomes limitations, builds data sharing network convenience, and increases network communicating.
　　This dissertation is organized into 4 sections: (1) observation and analysis of the severity of current problems of unstructured P2P network systems with varying sizes of network topologies, (2) building an unstructured P2P network search mechanism focused on alleviating current search mechanism problems by providing increased search efficiency while saving bandwidth usage and keeping optimal performance, (3) evaluating efficiency by comparing mathematical models of the new search mechanism to various authentic network systems, and (4) performing a system simulation in various sizes of authentic networks to measure the efficiency improvements.
　　Our research indicates that our new search mechanism had significant improvements for various sizes of networks in every ranking compared to the traditional flooding search mechanism. In fact, our findings indicate our search mechanism reduced 80 percent of bandwidth waste. The findings give evidence that in both theoretical and actual testing results, our new search mechanism showed improvements in efficiency and practical application.

Abstract in Chinese i
Abstract ii
Acknowledgement iii
Contents iv
List of Tables vi
List of Figures vii
1 Introduction 1
1.1 Research Background and Motivation 1
1.2 Technique and Literature Review 2
1.3 Research Purpose 7
1.4 Method 8
1.5 Organization 8
2 Observation and Discussion of Variant Previous Techniques in Simulation 10
2.1 Traffic Cost 10
2.2 Response Time 12
2.3 Success Rate 13
2.4 Average Number of Search Hops 15
3 The Search Mechanism Based on the Statistical Matrix Form 17
3.1 Feature Matrix 18
3.1.1 Feature Collection Scope 18
3.1.2 Processing Ability 19
3.1.2.1 Query Frequency 19
3.1.2.2 Response Frequency 23
3.1.3 Effective Sharing 26
3.1.3.1 Sharing Count 27
3.1.3.2 Quality of Sharing 30
3.1.4 Index Power 33
3.1.4.1 Index Count 34
3.1.4.2 Quality of the Index 37
3.1.5 Transmission Efficiency 40
3.2 Weight Matrix 47
3.3 Scoring Matrix 49
4 Performance Evaluation 51
4.1 Simulation Environment and System 51
4.2 Parameter Settings 57
4.3 Experiments in Static Environments 58
4.4 Experiments in Dynamic Environments 61
4.5 Analysis of SMF 64
4.5.1 Matrix Construction Overhead 64
4.5.2 Setting Proper Values for the Feature Collection Scope 66
4.5.3 The Number of Queried Neighbors 68
4.5.4 Proper Weight Setting 70
4.5.5 Search Performance in Different Sized Networks 71
5 Mathematical Analysis of Performance 73
5.1 Success Rate 74
5.2 Traffic Cost 79
5.3 Response Time 82
6 Discussion and Conclusion 86
Bibliography 87

[1] “BitTorrent Website, http://www.bittorrent.com/, 2011.
[2] “Chord Website, http://www.pdos.lcs.mit.edu/chord/, 2013.
[3] “eDonkey Website, http://www.emule-project.net/, 2011.
[4] “FrostWire Website, http://www.frostwire.com/, 2015.
[5] “Gnutella Website, http://rfc-gnutella.sourceforge.net/, 2008.
[6] “KaZaa Website, http://www.kazaa.com/, 2011.
[7] “LimeWire Website, http://www.limewire.com/, 2010.
[8] “Pastry Website, http://www.freepastry.org/, 2009.
[9] E. Adar and B. Huberman, “Free Riding on Gnutella, First Monday, vol. 5, no. 10–2, pp. 1–22, 2000.
[10] R. Ahmed and R. Boutaba, “Plexus: A Scalable Peer-to-Peer Protocol Enabling Efficient Subset Search, IEEE/ACM Transactions on Networking, vol. 17, no. 1 pp. 130–143, 2009.
[11] S. Bianchi, P. Felber, and M. G. Potop-Butucaru, “Stabilizing Distributed R-Trees for Peer-to-Peer Content Routing, IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1175–1187, 2010.
[12] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, “Making Gnutella-like P2P Systems Scalable, in Proceedings of ACM SIGCOMM, pp. 407–418, 2003.
[13] E. Chavez, M. Graff, G. Navarro, and E. S. Tellez, “Near neighbor searching with K nearest references, Journal of Information Systems, vol. 51, pp. 43–61, 2015.
[14] K. Chen, D. R. Choffnes, R. Potharaju, Y. Chen, F. E. Bustamante, D. Pei, and Y. Zhao, “Where the Sidewalk Ends: Extending the Internet AS Graph Using Traceroutes from P2P Users, IEEE Transactions on Computers, vol. 63, no. 4, pp. 1021–1036, 2014.
[15] G. Chen, C. P. Low, and Z. Yang, “Enhancing Search Performance in Unstructured P2P Networks Based on Users’ Common Interest, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 6, pp. 821–836, 2008.
[16] W. M. Chen and K. C. Liu, “Randomized Search Strategy for Unstructured P2P Networks, IEICE Transactions on Communications, vol. E95–B, no. 1, pp. 289–292, 2012.
[17] Y. M. Chiu, and D. Y. Eun, “On the Performance of Content Delivery under Competition in a Stochastic Unstructured Peer-to-Peer Network, IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 10, pp. 1487–1500, 2010.
[18] S. Datta, C. R. Giannella, and H. Kargupta, “Approximate Distributed K-Means Clustering over a Peer-to-Peer Network, IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 10, pp. 1372–1388, 2009.
[19] S. S. Dhillon and P. V. Mieghem, “Searching with Multiple Random Walk Queries, in Proceedings of IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, pp. 1–5, 2007.
[20] P. Fonseca, R. Rodrigues, A. Gupta, and B. Liskov, “Full-Information Lookups for Peer-to-Peer Overlays, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 9 pp. 1339–1351, 2009.
[21] R. Gaeta and M. Sereno, “Generalized Probabilistic Flooding in Unstructured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 12, pp. 2055–2062, 2011.
[22] C. Gkantsidis, M. Mihail, and A. Saberi, “Random Walks in Peer-to-Peer Networks, in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications, pp. 1–12, 2004.
[23] H. Guclu, and M. Yuksel, “Limited Scale-Free Overlay Topologies for Unstructured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 5 pp. 667–679, 2009.
[24] K. M. Hammouda and M. S. Kamel, “Hierarchically Distributed Peer-to-Peer Document Clustering and Cluster Summarization, IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 5 pp. 681–698, 2009.
[25] M. Hefeeda, and B. Noorizadeh, “On the Benefits of Cooperative Proxy Caching for Peer-to-Peer Traffic, IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 7, pp. 998–1010, 2010.
[26] M. Hefeeda, C. H. Hsu, and K. Mokhtarian, “Design and Evaluation of a Proxy Cache for Peer-to-Peer Traffic, IEEE Transactions on Computers, vol. 60, no. 7, pp. 964–977, 2011.
[27] P. Hieungmany, T. Souma, and S. Shioda, “Directional-Random-Walk-Based Contents Search for Unstructured P2P Systems, IEICE Transactions on Communications, vol. J98–B, no. 2, pp. 132–140, 2015.
[28] H. Hoang-Van, Y. Shinozaki, T. Miyoshi, and O. Fourmaux, “A Router-Aided Hierarchical P2P Traffic Localization Based on Variable Additional Delay Insertion, IEICE Transactions on Communications, vol. E97–B, no. 1, pp. 29–39, 2014.
[29] D. Hughes, G. Coulson, and J. Walkerdine, “Free Riding on Gnutella Revisited: The Bell Tolls? IEEE Distributed. System. Online, vol. 6, no. 6, pp. 1–18, 2005.
[30] H. C. Hsiao and C. H. He, “A Tree-Based Peer-to-Peer Network with Quality Guarantees, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 8, pp. 1099–1110, 2008.
[31] H. C. Hsiao, H. Liao, and C. C. Hung, “Resolving the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 11, pp. 1668–1681, 2009.
[32] H. C. Hsiao, H. Liao, and P. S. 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, 2010.
[33] H. C. Hsiao, Y. C. Lin, and H. Liao, “Building Small-World Peer-to-Peer Networks Based on Hierarchical Structures, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 7 pp. 1023–1037, 2009.
[34] S. Jiang, L. Guo, X. Zhang, and H. Wang, “LightFlood: Minimizing Redundant Messages and Maximizing the Scope of Peer-to-Peer Search, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 5, pp. 601–614, 2008.
[35] M. Karakaya, I. Korpeoglu, and O. Ulusoy, “Free Riding in Peer-to-Peer Networks, IEEE Internet Computing, vol. 13, no. 2, pp. 92–98, 2009.
[36] A. Kumar, J. Jim, X. Ellen, andW. Zegura, “Efficient and Scalable Query Routing for Unstructured Peer-to-Peer Networks, in Proceedings of the 24th IEEE International Conference on Computer Communications, vol. 2, pp. 1162–1173, 2005.
[37] H. Lee and A. Nakao, “A Feasibility Study of P2P Traffic Localization through Network Delay Insertion, IEICE Transactions on Communications, vol. E95–B, no. 11, pp. 3464–3471, 2012.
[38] Y. Li, D. Gruenbacher, and C. Scoglio, “Evaluating stranger policies in P2P file-sharing systems with reciprocity mechanisms, Journal of Computer Networks, vol. 56, pp. 1470–1485, 2012.
[39] Z. Li, J. Wu, J. Xie, T. Zhang, G. Chen, and Y. Dai, “Stability-Optimal Grouping Strategy of Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 12, pp. 2079–2087, 2011.
[40] T. Lin, P. Lin, H. Wang, and C. Chen, “Dynamic Search Algorithm in Unstructured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 5 pp. 654–666, 2009.
[41] Y. Liu, J. Han, and J. Wang, “Rumor Riding: Anonymizing Unstructured Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 3, pp. 464–475, 2011.
[42] X. Liu, Y. Liu, and L. Xiao, “Improving Query Response Delivery Quality in Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 11, pp. 1335–1347, 2006.
[43] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang, “Location Awareness in Unstructured Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 2, pp. 163-174, 2005.
[44] Y. Liu, L. Xiao, and L. M. Ni, “Building a Scalable Bipartite P2P Overlay Network, IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 9, pp. 1296–1306, 2007.
[45] Y. Liu, Z. Zhuang, L. Xiao, and L. M. Ni, “AOTO: Adaptive Overlay Topology Optimization in Unstructured P2P Systems, in Proceedings of IEEE GLOBECOM, vol. 7, pp. 4186–4190, 2003.
[46] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, “Search and Replication in Unstructured Peer-to-Peer Networks, in Proceedings of the 16th International Conference on Supercomputing, pp. 84–95, 2002.
[47] T. Nakashima and S. Fujita, “Tree-Based Consistency Maintenance Scheme for Peer-to-Peer File Sharing of Editable Contents, IEICE Transactions on Information and Systems, vol. E97–D, no. 12, pp. 3033–3040, 2014.
[48] S. Patro and Y. C. Hu, “Transparent Query Caching in Peer-to-Peer Overlay Networks, in Proceedings of the 17th International Parallel and Distributed Processing Symposium, pp. 1–10, 2003.
[49] K. K. Ramachandran and B. Sikdar, “A Queuing Model for Evaluating the Transfer Latency of Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 3, pp. 367–378, 2010.
[50] S. C. Rhea and J. Kubiatowicz, “Probabilistic Location and Routing, in Proceedings of IEEE International Conference on Computer Communications, vol. 3, pp. 1248–1257, 2002.
[51] M. Ripeanu, I. Foster, and A. Iamnitchi, “Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design, IEEE Internet Computing, vol. 6, no. 1, pp. 50–57, 2002.
[52] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems, in Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms, pp. 1–22, 2001.
[53] K. Saito and Y. Takano, “Distributed Hash Tables Adapting to the Conditions of the Real World, IEICE Transactions on Information and Systems, vol. J96–D, no. 6, pp. 1433–1446, 2013.
[54] S. Saroiu, P. Gummadi, and S. Gribble, “A Measurement Study of Peer-to-Peer File Sharing Systems, in Processing of Multimedia Computing and Networking, pp. 1–15, 2002.
[55] K. Scipanidkulchai, B. Maggs, and H. Zhang, “Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems, in Processing of the 22nd Annual Joint Conference of the IEEE Computer and Communications, vol. 3, pp. 2166–2176, 2003.
[56] H. Stark and J. G. Brankov, “Estimating the Standard Deviation From Extreme Gaussian Values, IEEE Signal Processing Letters, vol. 11, no. 3, pp. 320–322, 2004.
[57] R. M. Stoica, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications, in Proceedings of ACM SIGCOMM, pp. 149–160, 2001.
[58] D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, and W. Willinger, “On Unbiased Sampling for Unstructured Peer-to-Peer Networks, IEEE/ACM Transactions on Networking, vol. 17, no. 2 pp. 377–390, 2009.
[59] Y. Takahasi, T. Izumi, H. Kakugawa, and T. Masuzawa, “An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks, IEICE Transactions on Information and Systems, vol. E91–D, no. 7, pp. 1971–1981, 2008.
[60] S. Tewari and L. Kleinrock, “Optimal Search Performance in Unstructured Peer-to-Peer Networks With Clustered Demands, IEEE Journal On Selected Areas In Communications, vol. 25, no. 1, pp. 84–95, 2007.
[61] C. Theoharatos, G. Economou, and S. Fotopoulos, “Color Edge Detection Using the Minimal Spanning Tree, Pattern Recognition, vol. 38, pp. 603–606, 2005.
[62] C. Tian, H. Jiang, X. Liu, and W. Liu, “Revisiting Dynamic Query Protocols in Unstructured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 160–167, 2012.
[63] D. Tsoumakos and N. Roussopoulos, “Analysis and Comparison of P2P Search Methods, in Processing of ACM 1st International Conference on Scalable Information Systems, vol. 152, no. 25, pp. 847–872, 2006.
[64] C. Wang, L. Xiao, Y. Liu, and P. Zheng, “DiCAS: An Efficient Distributed Caching Mechanism for P2P Systems, IEEE Transactions Parallel and Distributed Systems, vol. 17, no. 10, pp. 1097–1109, 2006.
[65] C. Wang and L. Xiao, “An Effective P2P Search Scheme to Exploit File Sharing Heterogeneity, IEEE Transactions Parallel and Distributed Systems, vol. 18, no. 2, pp. 145–157, 2007.
[66] H. Wang and T. Lin, “On Efficiency in Searching Networks, in Processing of IEEE International Conference on Computer Communications, vol. 2, no. 2, pp. 1490–1501, 2005.
[67] L. Xiao, Y. Liu, and L. M. Ni, “Improving Unstructured Peer-to-Peer Systems by Adaptive Connection Establishment, IEEE Transactions on Computers, vol. 54, no. 9, pp. 1091–1103, 2005..
[68] X. Xiao, Q. Zhang, Y. Shi, and Y. Gao, “How Much to Share: A Repeated Game Model for Peer-to-Peer Streaming under Service Differentiation Incentives, IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 2, pp. 288–295, 2012.
[69] B. Yang and H. Garcia-Molina, “Efficient Search in Peer-to-Peer Networks, in Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures, no. 271–272, 2004.
[70] Z. Yang, J. Tian, B. Y. Zhao, W. Chen, and Y. Dai, “Protector: A Probabilistic Failure Detector for Cost-Effective Peer-to-Peer Storage, IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 9, pp. 1514–1527, 2011.
[71] M. Yang, and Y. Yang. “An Efficient Hybrid Peer-to-Peer System for Distributed Data Sharing, IEEE Transactions on Computers, vol. 59, no. 9, pp. 1158–1171, 2010.
[72] K. Yokota, T. Nakagawa, T. Isogai, T. Asaka, and T. Takahashi, “Clustering for Distributing Cached Contents in P2P File Sharing Application, IEICE Transactions on Communications, vol. J95–B, no. 2, pp. 178–187, 2012.
[73] Y. B. Zhao, J. D. Kubiatowicz, and A. D. Joseph, “Tapestry: An Infrastructure for Fault-Resilient Wide-Area Location and Routing, Technical Report CSD-01-1141, University of California Berkeley, pp. 1–27, 2001.
[74] B. Q. Zhao, J. C. Lui, and D. M. Chiu, “A Mathematical Framework for Analyzing Adaptive Incentive Protocols in P2P Networks, IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 367–380, 2012.
[75] Z. Zhu, P. Kalnis, and S. Bakiras, “DCMP: A Distributed Cycle Minimization Protocol for Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 3, pp. 363–377, 2008.