臺灣博碩士論文加值系統

點對點(P2P)網路主要分為集中式和非集中式。因數位版權上的問題，集中式P2P網路如Napster於2000年被控訴以及關閉, 也因此導致了集中式P2P網絡的沒落。而非集中式P2P網路主要集中在兩個種類：結構化和非結構化。
大多數結構化P2P網路使用分散式雜湊表(DHT)來尋求資源，雖然DHT可以有效的發布或尋求資源，但是節點更動會對結構化P2P網路有很大的衝擊。此外，當指派邏輯識別ID時，結構化P2P網路並不會考慮實體上網絡的距離，進而會造成大量的額外路由，資料探索的延遲，以及高平均路徑的延展。
混合式的P2P網絡如KaZaA雖然能夠有效的結合集中式與非集中式P2P網絡的優點，但是每一個由超級節點(Super Node)並無法得知除自己管理的普通節點(Ordinary Node)以外的資源信息，因此當探索的目標資源並不在自己的管轄節點裡，超級節點需要轉發給所有其他的超級節點，這會造成嚴重的網路流量增長。
在本論文裡，我們提出了將P2P網絡分成兩個階層，並且在第二階層裡把實際IP地址屬於同一個區域網絡的節點集合在一起形成一個群組，並指派第一個加入在這個群組裡的節點為超級節點(Super Node), 負責管理其餘加入的普通節點(Ordinary Node), 除此之外，在第二階層裡的每一個節點都會與第一個階層的其中一個節點進行連接，而該第一層節點負責判別新加入的節點是否屬於自己管理的群組，而該群組是否已經擁有超級節點的存在，除此之外，第一層的節點也負責轉發信息到其他第一層的節點。
而為了解決結構化P2P的額外路由，資料探索延遲等等的問題，我們提出了基於本地區域搜尋(local-based search)，因第二層的任何一個群組裡的所有節點都是屬於同一個區域網，因此本地區域搜尋能夠讓請求節點能夠在一個極短的時間內(基本為1個Hop) 找到同一個群組擁有的資源。除此之外，我們也提供了基於熱門資源索引搜尋(popular-index search)，讓屬於同一個第一階層節點的第二層群組能夠在不轉發信息到其他的第一階層的節點，以及再轉發到儲存該資源的信息節點情況下，能夠快速且有效率的找到曾經被探索過的熱門資源。

關鍵字：點對點網絡、IP地址、本地區域搜尋、熱門資源索引搜尋

A Peer-to-Peer (P2P) network can be classified as centralized, decentralized and Hybrid. Centralized P2P network such as Napster began to decline due to the digital copyright and load-balancing issue. Decentralized P2P network mainly focus on two categories: structure and unstructured. An unstructured P2P network such as Gnutella-based system cycle continues forwarding messages to node’s neighbors and causing a large number of flooding query message which may affect the network traffic.
Most of structure P2P network use DHT (Distributed-Hash-Table) to query resources, the node churn will be a huge impact to the structure P2P-network. In addition, extensive routing overhead, larger average file discovery delay, and high average path-stretch are the problems due structure P2P-network does not consider physical proximity of peers when assigning logical identifiers.
Hybrid P2P system such as KaZaA combine the advantages of centralized and decentralized. A super node (SN) act as server in a group. However, the burden of network traffic when a SN broadcast a request to other SNs due SNs did not exchange resources information.
In order to solve such problems on P2P networks, this thesis implements a novel P2P-network that separate two layers and grouping the nodes by the internet protocol address (IP-address). In addition, we provide local-based search and popular-index search to archive efficient discover resources and reduce the load-balancing, routing overhead and high average path-stretch issue.

Keywords— P2P network; IP-address; Local-based search; Popular-index search

摘要 i
Abstract ii
Table of Contents iii
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1. Research Motivations 1
1.2. Research Goals 2
1.3. Thesis Organization 3
Chapter 2 Literature Review 4
2.1. Peer-to-peer Networks 4
2.1.1. Centralized P2P System 5
2.1.1.1. Napster [1] 5
2.1.2. Decentralized P2P System 6
2.1.2.1. Gnutella-based search [7,24,25] 7
2.1.2.2. Chord [4, 16, 17, 18, 19] 8
2.1.2.3. Hypercube-based system[20, 21, 22] 9
2.1.2.4. Physical Distance Problem in logical network 10
2.1.3. Hybrid P2P System 12
2.1.3.1. KaZaA [10, 28] 13
2.2. Keyword Encoding 13
2.3. One-way Hash Function [30] 14
2.4. Distributed Hash Table (DHT) 14
Chapter 3 System Design 16
3.1. System Architecture 16
3.1.1. Notation Table 17
3.1.2. Split of IP-address 17
3.1.3. Entities description 18
3.1.4. Architecture description 20
3.2. Encoding Function 21
3.3. Node Joining 21
3.4. Resource distribution 27
3.5. Query Resource 32
3.5.1. Local-based search 33
3.5.2. Popular index search 36
3.5.3. Normal search 40
3.6. Maintenance 45
Chapter 4 Analysis and Comparison 47
4.1. Characteristic Comparison 47
4.2. Compare distance in physical routing 48
4.3. Reduce burden of index node 50
4.4. Avoid Query Flooding 50
Chapter 5 Conclusions and Future Works 52
5.1. Conclusion 52
5.2. Future Work 53
References 54

[1]“Napster” Available online at http://www.napster.com/
[2]“Publius” Available online at http://publius.cdt.org/
[3]Yang, B., & Garcia-Molina, H. (2002). Improving search in peer-to-peer networks. In Distributed Computing Systems, 2002. Proceedings. 22nd International Conference on (pp. 5-14). IEEE.
[4]Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001). Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 31(4), 149-160.
[5]Manku, G. S., Bawa, M., & Raghavan, P. (2003, March). Symphony: Distributed Hashing in a Small World. In USENIX Symposium on Internet Technologies and Systems (p. 10).
[6]Milojicic, D. S., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., ... & Xu, Z. (2002). Peer-to-peer computing.
[7]Ripeanu, M. (2001, August). Peer-to-peer architecture case study: Gnutella network. In Peer-to-Peer Computing, 2001. Proceedings. First International Conference on (pp. 99-100). IEEE.
[8]Rowstron, A., & Druschel, P. (2001, January). Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware 2001 (pp. 329-350). Springer Berlin Heidelberg.
[9]Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.
[10]Liang, J., Kumar, R., & Ross, K. W. (2004). Understanding kazaa. Manuscript, Polytechnic Univ, 17.
[11]Sheng, L., Song, J., Dong, X., & Zhou, L. (2010, April). Emule simulator: A practical way to study the emule system. In Networks (ICN), 2010 Ninth International Conference on (pp. 83-88). IEEE.
[12]Joung, Y. J., & Yang, L. W. (2007). Wildcard search in structured peer-to-peer networks. Knowledge and Data Engineering, IEEE Transactions on, 19(11), 1524-1540.
[13]Joung, Y. J., & Yang, L. W. (2014). On character-based index schemes for complex wildcard search in peer-to-peer networks. Information Sciences, 272, 209-222.
[14]Naor, M., & Wieder, U. (2007). Novel architectures for P2P applications: the continuous-discrete approach. ACM Transactions on Algorithms (TALG), 3(3), 34.
[15]Manku, G. S. (2004). Dipsea: a modular distributed hash table (Doctoral dissertation, stanford university).
[16]Chang, C., Lu, E. J. L., Huang, S. Y., & Chen, Y. H. (2014). An RDF-based P2P overlay network supporting range and wildcard queries. Journal of Network and Computer Applications, 46, 124-138.
[17]Taheri, J., & Akbari, M. K. TAC: A Topology-Aware Chord-based Peer-to-Peer Network.
[18]Forestiero, A., & Mastroianni, C. (2011, July). Description of the Self-Chord P2P Application. In WOA (pp. 175-177).
[19]Wang, Y., Li, X., Jin, Q., & Ma, J. (2012, September). AB-Chord: an efficient approach for resource location in structured P2P networks. In Ubiquitous Intelligence & Computing and 9th International Conference on Autonomic & Trusted Computing (UIC/ATC), 2012 9th International Conference on (pp. 278-284). IEEE.
[20]Schlosser, M., Sintek, M., Decker, S., & Nejdl, W. (2003). HyperCuP—hypercubes, ontologies, and efficient search on peer-to-peer networks. InAgents and Peer-to-Peer Computing (pp. 112-124). Springer Berlin Heidelberg.
[21]Li, X., & Yu, J. (2008, October). A Novel P2P Overlay Network Based on Cycloid and Folded Hypercube. In Grid and Cooperative Computing, 2008. GCC''08. Seventh International Conference on (pp. 374-379). IEEE.
[22]Ali, H., & Ahmed, M. (2012, October). HPRDG: A scalable framework hypercube-P2P-based for resource discovery in computational Grid. InComputer Theory and Applications (ICCTA), 2012 22nd International Conference on (pp. 2-8). IEEE.
[23]Kamoun, F., Werghi, N., & Al Blushi, M. (2010). On the appropriateness of incident management systems in developing countries: a case from the UAE.Journal of technology management & innovation, 5(4), 57-69.
[24]Ertel, S. (2014). Unstructured P2P networks by example: Gnutella 0.4, Gnutella 0.6. proceeding of Dresden University of Technology.
[25]Zink, T., & Waldvogel, M. Distributed System Laboratory Analysis and Efficient Classification of P2P File Sharing Traffic.
[26]Barriquello, C. H., Denardin, G. W., & Campos, A. (2015). A geographic routing approach for IPv6 in large-scale low-power and lossy networks. Computers & Electrical Engineering.
[27]Dagang, G., Mingqin, Z., & Jirong, Z. (2014). Research of Resources Search Mechanism on Hybrid Stream Media System. Telecommunications Science,30(2), 33-39.
[28]Ye, W., & Cho, K. (2014). Hybrid P2P traffic classification with heuristic rules and machine learning. Soft Computing, 18(9), 1815-1827.
[29]Fournier, R., Cholez, T., Latapy, M., Chrisment, I., Magnien, C., Festor, O., & Daniloff, I. (2014). Comparing pedophile activity in different P2P systems.Social Sciences, 3(3), 314-325.
[30]Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., & Yogev, E. (2014, October). One-way functions and (im) perfect obfuscation. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on (pp. 374-383). IEEE.
[31]Tseng, Y. H. (2014). Research and Development on Automatic Information Organization and Subject Analysis in Recent Decades. Journal of Educational Media & Library Sciences, 51.
[32]Antoine, M., Pellegrino, L., Huet, F., & Baude, F. (2014). Towards a generic API for data load balancing in structured P2P systems.
[33]Abid, S. A., Othman, M., & Shah, N. (2014). 3D P2P overlay over MANETs.Computer Networks, 64, 89-111.
[34]Sharifkhani, F., & Pakravan, M. R. (2013, August). A review of new advances in resource discovery approaches in unstructured P2P networks. In Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on (pp. 828-833). IEEE.
[35]Lu, S. H., Li, K. C., Lai, K. C., & Chung, Y. C. (2014). A scalable P2P overlay based on arrangement graph with minimized overhead. Peer-to-Peer Networking and Applications, 7(4), 497-510.