陳銘憲臺灣大學：電信工程學研究所鄭伃璇Jheng, Yu-SyuanYu-SyuanJheng2007-11-272018-07-052007-11-272018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/58802從90年代後期以來，點對點(P2P)檔案分享已經逐漸成為互聯網上最普及的的網路應用；然而，現今互聯網上最大的問題同樣也來自於點對點檔案分享軟體消耗過多的網路資源，佔據了大量頻寬。因此在本篇論文中，我們提出若針對使用者的儲存資訊做傳輸編碼，能夠實施一個高頻寬效益的檔案分享網路。之前的網路編碼研究大都採用隨機編碼，這種編碼方式沒有考量使用者存取之間的異質性；而我們提出的編碼方式針對不同使用者不同存取檔案做動態編碼，能避開傳送某些不必要的訊息，造成使用者的負擔，也能達到較少傳輸頻寬的要求。 我們進一步地闡述了一個如何利用點對點傳輸編碼達到最少頻寬需求的問題(Minimum Bandwidth P2P Coding Problem, MES)，並且證明出這個問題屬於NP-Complete。接著，我們在文章中提出了Maximal Entropy Selection演算法，來幫助我們找出最好的傳送編碼。最後，從我們的實驗結果驗證，MES編碼確實能夠減少傳輸次數，並且有效的節省檔案分享軟體的傳輸頻寬。Peer-to-peer (P2P) file-sharing has become the leading growth application since its emergence in the late 90's. However, current approaches lead to high bandwidth consumption in Internet. In this thesis, we propose a bandwidth efficient file-sharing system using network coding which leverages P2P user storage in file transfer. Previous works on network coding mainly adopt random coding, and the coding decision thereby does not consider the heterogeneity of the data stored in users. In our approach, however, we avoid encoding unnecessary data by leveraging the variety of the caching files in the clients, and our approach thereby can effectively reduce the number of transmission in sender and result in minimal bandwidth consumption. We formulate the selection of coding data as Minimum Bandwidth P2P Coding Problem and prove that it is NP-complete. We also propose Maximal Entropy Selection (MES) algorithm in the thesis to find the solution of the problem. Finally, we demonstrate the algorithm performance through extensive simulations and show that MES is able to significantly reduce the bandwidth consumption.1 Introduction 6 2 Preliminaries 13 2.1 P2P Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Napster, Gnutella and KaZaA . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Linear Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Maximal Entropy Selection Algorithm 20 3.1 Problem Formulation of Minimum Bandwidth P2P Coding Problem . . . . 21 3.2 MES Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Protocol Design 31 4.1 Overview of MES Implementation . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Design of MES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 JOIN/LEAVE (On-line) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.4 Example of MES on KaZaA . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5 Experimental Evaluation 38 5.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2.1 Influence of Network Size . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2.2 Influence of Cache Size . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2.3 Influence of Download Behavior . . . . . . . . . . . . . . . . . . . . 43 5.2.4 Influence of Multicast Connectivity . . . . . . . . . . . . . . . . . . 44 6 Conclusion 481205440 bytesapplication/pdfen-US點對點檔案分享網路編碼P2Pfile-sharingnetwork codingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58802/1/ntu-95-R93942040-1.pdf