同儕式網路檔案分享系統下載效能改良之研究

On Improving the Performance of Peer-to-Peer File Sharing Systems

江政龍(Jeng-Long Chiang)

指導教授 ： 陳文村

國立清華大學/電機資訊學院/資訊工程學系/博士(2010年)

摘要

本論文針對同儕式（Peer-to-Peer, P2P）網路應用中最重要的系統－BitTorrent，提出針對節點分享公平性（peer fairness）及檔案片段可得性（piece availability）兩方面效能的改善方法。BitTorrent在近幾年領先HTTP協定保有網際網路流量的第一佔有率，然而，最近的研究皆指出其在效能上的一些潛在問題，包含使用者分享量不公平問題（unfairness problem）以及俗稱的斷頭/斷種問題（the last piece/block problem）。分享不公平的問題使得部份使用者付出超出數倍以上的上傳量，卻和其他少量付出甚至完全不付出的使用者得到同樣下載量；而斷頭現象為在種子（seed）離開系統後，工作中的節點容易因為少量的稀有檔案片段（rare piece）遺失而造成下載失敗的問題。
在本研究中，針對不公平問題我們提出Adaptive Optimistic Unchoking（AOU）方法，透過更有效地使用BitTorrent內建的optimistic unchoking機制，能在維持與原始BitTorrent下載效能相當的條件下，由常見六倍的不平衡量下降至兩倍以下的相對平衡，並在整體達到60%以上的公平性改善。在針對斷頭問題方面，我們分別提出一個主動式與一個內嵌式的改進方法。主動式Explicitly Acquiring Rare Piece （EARP）方法提出一個新的訊息格式讓使用者可以主動搜尋及快速下載與分散即將遺失的檔案片斷，儘管在使用者高速變動的環境下，仍較原始BitTorrent 減少約70%的斷頭現象。而內嵌式Interest-Intended Piece Selection （IIPS）方法除了較原始BitTorrent的rarest-first演算法減少28%~60%斷頭問題外，其較廣域之檔案片斷觀點（piece rareness）及使用者互傳的穩定性，亦使IIPS能達成較佳的佈種（seeding）效率。

關鍵字

同儕式網路 ； 檔案分享 ； 公平性 ； 服務可得性

並列摘要

Peer-to-peer (P2P) networking is emerging as an important communication model which brings advantages of low deployment cost, high scalability, and high throughput for network applications. Unlike the conventional client-server model, P2P model allows services to be offered by all participating peers in a distributed and cooperative manner. The major application in P2P networking model is file sharing. Napster, eDonkey, LimeWire, and BitTorrent are famous and popular P2P-based file sharing systems where all peers share their files directly among themselves without the need of a vulnerable file repository.
Retrieving a target file in the P2P file sharing system has two major phases: the target file is located during the discovery phase while it is transmitted during the delivery phase. In this thesis, we study the performance of file distribution in the delivery phase and focus on the BitTorrent system, which is designed for fast and efficient distribution of large files. The two issues concerned are the unfairness problem and the last piece problem. The former refers to the unbalance of data volume each peer serves, while the latter addresses download failures due to missing pieces. The unfairness problem discourages users from sharing their resources in most P2P-based systems while the last piece problem, which is prone to occur when the last seed leaves, degrades service availability and download speed.
In this thesis, three schemes are proposed to resolve the two aforementioned problems in BitTorrent. One deal with peer fairness and the other two with the last piece problem. First, in order to enforce better peer fairness, Adaptive Optimistic Unchoking (AOU) suggests to maintain cooperation between similar peers and to restrict the use of optimistic unchoking. Second, Explicitly Acquiring Rare Piece (EARP) allows peers to explicitly acquire designated rare pieces outside its current peer set so as to rapidly distribute those rare pieces over the network. Finally, Interest-Intended Piece Selection (IIPS) tends to maintain piece diversity in a wider view of piece rareness as well as keep stable cooperation between peers for alleviating the last piece problem and improving overall download performance respectively.
Simulation results show that the three proposed schemes successfully enhance the performance of BitTorrent. In one aspect, AOU achieves about 60% improvement on peer fairness while maintaining equivalent performance as original BitTorrent. In the other aspect, EARP outperforms BitTorrent's local-rarest-first (LRF) algorithm in terms of higher robustness as well as fewer occurrences of piece loss. Even under high peer dynamics, EARP still shows 69% less piece losses with comparison to LRF. Finally, IIPS successfully results in 28%-60% fewer occurrences of the last piece problem than LRF even under controlled tough environments.

並列關鍵字

peer-to-peer network ； file sharing ； fairness ； availability

參考文獻

2. C. Bengt and G. Rune, “The Rise and Fall of Napster – An Evolutionary Approach,” in Proc. of the 6th Int'l Computer Science Conf. On Active Media Technology, 2001.

4. D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, R. Morris, “Resilient Overlay Networks,” in Proc. 18th ACM Symposium on Operating Systems Principles, 2001.

5. RON [Online]. Available: http://nms.csail.mit.edu/ron/.

8. EMS [Online]. Available: http://esm.cs.cmu.edu/.

9. Skype [Online]. Available: http://www.skype.com/.