周承復臺灣大學：資訊工程學研究所張憶婷Chang, Yi-TingYi-TingChang2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53677隨著點對點網路系統的廣泛應用，多媒體物件的分享變得越來越有效率。點對點系統中的使用者會根據自己的喜好，搜尋及下載某特定類型的多媒體物件。然而，大多數的點對點系統只根據實體網路上的限制來建立疊代網路，並沒有考慮到系統中使用者對於物件的喜好。在這篇論文中，我們研究了一種以社群理論為基礎的疊代系統，能夠將點對點系統中有相同興趣的使用者聚集在一起，達成有效率的物件搜尋。為了要能夠建立以社群理論為基礎的疊代網路，我們提出了一個能夠計算使用者之間相似程度的量化方法，讓相似程度高的兩個使用者能夠在疊代網路上連結在一起。因此，使用者可以從與自己有相同興趣的鄰居中找到所感興趣的物件。此外，我們提出了一個讓使用者動態調整疊代網路上連結的分散式演算法，讓點對點網路系統能夠有效率地應付使用者的加入、離開，以及使用者興趣的變化。同時，我們提出了能夠處理多種物件類型的方法，及能夠增進物件搜尋效率的延伸方法，並且探討在限制TTL的情況下搜尋物件，應以多大的TTL值來做搜尋才能達到所希望的成功率。 我們利用名為Audioscrobbler網站上的使用者資料來做模擬實驗，以評估我們所提出的以社群理論為基礎的疊代網路系統。Audioscrobbler網站紀錄了使用者聆聽音樂的喜好，以及這些音樂的基本資料。實驗結果證實我們所提出的方法能夠讓使用者有效率地找尋到所想要的物件，即是能在造成系統較小的負擔下，達成很高的搜尋成功率。此外，我們也比較了傳統的非結構化點對點系統（以實體距離為基礎所建立的點對點疊代系統），實驗結果證實我們所提出的方法的確比傳統的點對點系統有較好的效能。The widespread use of Peer-to-Peer (P2P) systems has made multimedia content sharing more efficient. Users in a P2P network can query and download objects based on their preference for specific types of multimedia content. However, most P2P systems only construct the overlay architecture according to physical network constraints and do not take user preferences into account. In this thesis, we investigate a social-based overlay that can cluster peers that have similar preferences. To construct a semantic social-based overlay, we model a quantifiable measure of similarity between peers so that those with a higher degree of similarity can be connected by shorter paths. Hence, peers can locate objects of interest from their overlay neighbors, i.e., peers who have common interests. In addition, we propose an overlay adaptation algorithm that allows the overlay to adapt to P2P churn and preference changes in a distributed manner. Meanwhile, we introduce methods to handle multiple types of contents and extended methods to improve the performance of the content searching. We also analysis the number of TTL that is appropriate for the TTL-limited flooding. We use simulations and a real database called Audioscrobbler, which tracks users’ listening habits, to evaluate the proposed social-based overlay. The results show that social-based overlay adaptation enables users to locate content of interest with a higher success ratio and with less message overhead. Besides, we compare the performance between the proposed social-based p2p system with the Freenet-type p2p system.Abstract (in Chinese) . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract (in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem Formulation and Contribution . . . . . . . . . . . . . . . . . 2 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Decentralized P2P System . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 DHT-based P2P Systems . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Unstructured P2P Systems . . . . . . . . . . . . . . . . . . . . 7 2.2 Social-based P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Small World Theory . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Structured Social-based P2P Networks . . . . . . . . . . . . . 9 2.2.3 Unstructured Social-based P2P Networks . . . . . . . . . . . . 10 Chapter 3 Distributed Social-based Overlay Construction . . . . . 12 3.1 Overview of Social-based Overlay . . . . . . . . . . . . . . . . . . . . 12 3.2 Similar Peer Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.1 De‾nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.2 Similarity Computation . . . . . . . . . . . . . . . . . . . . . 14 3.2.3 Multiple Types of Contents . . . . . . . . . . . . . . . . . . . 15 3.3 Distributed Overlay Adaptation . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Distributed Buddy Selection . . . . . . . . . . . . . . . . . . . 18 3.3.2 Buddy List Update . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Keyword Search Using Social-based Graph . . . . . . . . . . . . . . . 20 3.4.1 Query TTL Analysis . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.2 Bu®er Replacement Schemes . . . . . . . . . . . . . . . . . . . 24 3.4.3 Enhanced Query Schemes . . . . . . . . . . . . . . . . . . . . 24 Chapter 4 Performance Evaluation and Discussion . . . . . . . . . 27 4.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Performance Comparison in Static Environments . . . . . . . . . . . 28 4.2.1 TTL-limited Flooding . . . . . . . . . . . . . . . . . . . . . . 30 4.2.2 Compare with Freenet-type P2P Networks . . . . . . . . . . . 33 4.3 Performance Comparison in Dynamic Environments . . . . . . . . . . 35 4.4 Multiple Types of Contents . . . . . . . . . . . . . . . . . . . . . . . 37 4.5 Enhanced Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.6 Query TTL Validation . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Chapter 5 Conclusions and Future Works . . . . . . . . . . . . . . 42 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44en-US非結構化點對點網路社群理論關鍵字搜尋多媒體存取系統Unstructured P2P NetworkSocial TheoryKeyword SearchMultimedia Access Systemthesis