- 學位論文
點對點檔案分享系統的建模與分析
The Modeling and Analysis of P2P File-sharing Systems
摘要
點對點（peer-to-peer，簡稱 P2P）連線軟體，為當今網際網路上最重要的使用者應用之一。在技術面上，點對點連線利用「使用端」對「使用端」（client to client）的通訊技術，讓網路上的主機不必經過中央伺服器即能有效散佈資料，此項技術的特色是，系統的建置成本低廉，而且效能會隨著使用者的數量而提高，所以特別適合於擁有大量使用者的網路應用。常見的P2P應用包括音樂下載服務（例如 Napster、Kazaa） 、線上影音串流（例如PPStream、TVAnts）、以及檔案分享社群（如 BitTorrent、Emule）等等。在此篇論文中，我們針對了BitTorrent-like的檔案分享系統提出一個數學模型。基於此模型，我們建立出應用層的網路拓墣，並在此拓墣上研究檔案分享系統的校能。對於下載端，我們估計出平均檔案下載時間，也提出幾個因地制宜（ad hoc）的最佳化作法，幫助使用者在最快的時間內下載完檔案。對於檔案分享端，我們則提出一個頻寬分配策略，此策略可以最大化檔案在網路上的分配亂度。我們證明：將資料的分配亂度最大化，有助於增進整體系統效能。最後，我們研究了數種使用者行為之下的檔案散佈模式，並在兩種特殊情境中，給出使用者社群壽命與服務達成率的機率估計。
並列摘要
Peer-to-peer (P2P) file-sharing system is becoming a critical application on today's Internet. It features remarkable efficiency and effectiveness in disseminating contents to a large number of users. In this thesis, we present an application of basic concepts of the stochastic process theory to devise a analytical model describing the dynamics of large peer-to-peer networks. The model we propose is quite general and highly modular, and allows to represent several effects related to content distribution among peers, user behavior, resource allocation algorithms and dynamic structure of the overlay network topology. Based on our model, we propose several client side strategies aiming at optimizing user level performance metrics. For system level metrics, we develop an uploader bandwidth allocation policy and prove it to achieve efficient total completion time. Finally, we examine the dynamic of content distribution, and discuss how it is affected by environmental factors such as peer flows and uploader policies. In particular, we study the evolution of P2P community in terms of its survivability, and give distributional results in the some special cases.