臺灣博碩士論文加值系統

早期對P2P檔案分享的研究大多專注在overlay topology、內容搜尋、對等點的探測、分享公平性等等的議題上，合作式檔案分享(Collaborative File sharing)的議題較少被人提及。在這篇論文中，我們針對於BT-like的P2P網路架構下，提出一個合作式檔案分享的演算法。我們假設Node的Lifetime為均勻分布(uniform distribution)，根據每個Peer的生命週期之機率分佈特性、每個檔案片段在網路中的稀有程度(Rarity)、與目前網路上每個Peer對於檔案的需求度(Demand)，來決定每一次排程演算法中發送端與接收端之優先順序，使得在有限及合理的時間裡，大多數的Peer都能取得完整的檔案。我們除了考慮BT所使用的RPF(Rarest Piece First)演算法外，也考慮了MDNF(Most Demanding Node First)演算法，以確保下載檔案的完整性以及如何在有限及合理的時間裡完成熱門檔案的下載。最後我們以模擬的方式來驗證此演算法的程序與系統效能。

Prior researches in P2P file sharing mostly focus on several topics such as the overlay topology, the content searching, the peer discovery, the sharing fairness, incentive mechanisms, except scheduling algorithms for peer-to-peer collaborative file distribution. The scheduling algorithm specifies how file pieces are distributed among peers. When a peer that has the rarest piece leaves, the other peers probably download the incomplete file in the network. Our algorithm is involved in the lifetime of peers in the P2P networks. We first use the distribution of peer’s lifetime and the demand of each peer to decide which peers send which pieces that are rarities, and then also consider the distribution of peer’s lifetime and the demand of each peer to decide which peers receive these pieces. Our goals are to maximize number of peers which have downloaded an entire file before it leaves, to increase the availability of different file pieces, and to minimize the transmission time of the latest completion. Lastly, we show the comparison of the performances of RPF, MDNF, Lifetime-based RPF, and Lifetime-based MDNF algorithms.

致謝 I
中文摘要 II
Abstract III
目錄 IV
圖目錄 VI
第一章 緒論 1
1.1 Peer-to-Peer 網路介紹 1
1.1.1 Napster 3
1.1.2 Gnutella 3
1.1.3 BitTorrent 4
1.2 研究動機與文獻探討 5
1.3 文章導讀 6
第二章 系統架構 7
2.1 模型架構 7
2.2 節點生命週期分佈 9
2.3 剩餘生命週期預測 11
第三章 檔案分享排程演算法 13
3.1 稀有片段優先下載排程演算法 15
3.2 高需求度節點優先排程演算法 16
3.3 以生命週期為基礎之排程演算法 17
3.3.1 以生命週期為基礎之稀有片段優先下載排程演算法 17
3.3.2 以生命週期為基礎之高需求度節點優先下載排程演算法 19
第四章 模擬結果與效能分析 21
4.1 模擬環境與參數 21
4.2 模擬結果 21
第五章 結論 32
參考文獻 33

[1] The official BitTorrent website, http://www.bittorrent.com/
[2] The official Gnutella website, http://www.gnutella.com/
[3] The official Kazaa website, http://www.kazaa.com/
[4] The official Napster website, http://www.napster.com/
[5] B. Cohen, “Incentive Build Robustness in BitTorrent” May 2003. [On-line]
[6] Jonathan S. K. Chan, Victor O. K. Li, and King-Shan Lui, ”Performance Comparison of scheduling Algorithms for Peer-to-Peer Collaborative File Distribution”, IEEE Journal on Selected Areas in Communications, Vol. 25, No. 1, January 2007, pp.146-154.
[7] J. S. K. Chan, V. O. K. Li, and K. S. Lui, “Scheduling algorithms for peer-to-peer collaborative file distribution,” in Proc. Int’l conf. on Collaborative Computing: Networking, Applications and Worksharing(CollaborativeCom), Dec. 2005, pp. Digital Object Identifier 10.1109/COLCOM.2005.1651215
[8] X. Yang and G. de Veciana, “Service capacity of peer to peer networks,” in Proc. IEEE INFOCOM, Mar. 2004. pp. 2242-2252
[9] A. Parker, “The true picture of peer-to-peer file-sharing,” CacheLogic Presentation, July 2004.
[10] E. W. Biersack, P. Rodriguez, and P. Felber, “Performance analysis of peer-to-peer networks for file distribution,” in Proc. 5th Int’l Workshop on Quality of Future Internet Service, Sep. 2004, pp. 1-10.
[11] S. Ratnasamy, P.Francis, M. Handley, R. Karp, and S. Shenker, “A scalable content-addressable network,” in ACM SIGCOMM, Aug. 2004, pp.161-172.
[12] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications,” IEEE/ACM Transactions on Networking, Vol. 11, No. 1, February 2003, pp. 17-32
[13] A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” in Proc. 18th IFIP/ACM Int. Conf. Distributed Systems Platforms (Middleware 2001), Nov. 2001, p.329-350.
[14] S. Saroiu, P. Gummadi, and S. Gribble, “A measurement study of peer-to-peer file sharing systems,” in MMCN, Jan. 2002, pp. 156-170.
[15] P. Golle, K. Leyton-Brown, I. Mironov, and M. Lillibridge, “Incentives for sharing in peer-to-peer networks,” in ACM Conference on Electronic Commerce, Oct. 2001, pp. 264-267.
[16] D. Liben-Nowell, H. Balakrishnan, and D. Karger, “Analysis of the evolution of peer-to-peer systems,” in ACM PODC, July 2002, pp. 233-242
[17] Derek Leonard, Zhongmei Yao, Vivek Rai, and Dmitri Loguinov, “On Lifetime-Based Node Failure and Stochastic Resilience of Decentralized Peer-to-Peer Networks”, IEEE/ACM Transactions on Networking, Vol. 15, No. 5, October 2007, pp. 644-656.

[18] F. Bustamante and Y. Qiao, “Friendships that last: Peer lifespan and its role in p2p protocols,” in IEEE WCW, Sept. 2003, pp. 233-246.
[19] Lei Gau, Songqing Chen, Zhen Xiao, Enhua Tan, Xiaoning Ding, Xiaodong Zhang, “A Performance study of BitTorrent-like Peer-to-Peer Systems,” IEEE Journal on Selected Areas in Communications, Vol. 25, No. 1, January 2007, pp. 155-169
[20] B. Bolloba’s, Random Graphs, Cambridge University Press, 2001.
[21] A. Ganesh and L. Massoulie, “Failure resilience in balanced overlay networks,” in Allerton Conference on Communication, Control and Computing, Oct. 2003.
[22] R. Cohen, K. Erez, D. ben Avraham, and S. Havlin, “Resilience of the internet to random breakdowns,” Physical Review Letters, vol. 85, no. 21, pp. 4626-4628, Nov.2000.