請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40151
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chih-Duo Hong | en |
dc.contributor.author | 洪智鐸 | zh_TW |
dc.date.accessioned | 2021-06-14T16:41:51Z | - |
dc.date.available | 2008-08-04 | |
dc.date.copyright | 2008-08-04 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-08-01 | |
dc.identifier.citation | [ECRS03] T.S. Eugene, Y. H. Chu, S. G. Rao, K. Sripanidkulchai, and H. Zhang,
“Measurement-Based Optimization Techniques for Bandwidth-Demanding Peer-to-Peer Systems,” Proceedings of IEEE INFOCOM, 2003. [QS04] D. Qiu and R. Srikant, “Modeling and Performance Evaluation of BT-Like Peer-to- Peer Networks,” Proceedings of ACM SIGCOMM, 2004. [Rip01] M. Ripeanu, “Peer-to-Peer Architecture Case Study: Gnutella network,” Proceedings of First International Conference on Peer-to-Peer Computing, 2001. [RFI02] M. Ripeanu, I. Foster, and A. Iamnitchi, “Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design,” IEEE Internet Computing, 2002. [GFJK03] Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose, and D. Towsley, “Modeling Peer- to-Peer File-sharing Systems,” Proceedings of IEEE INFORCOM, 2003. [RDA06] R. Kumar, D. D. Yao, A. Bagchi, K. W. Ross, Dan Rubenstein, “Fluid Modeling of pollution proliferation in P2P networks,” ACM SIGMETRICS Performance Evaluation Review, Vol.34(1), 2006. [GDS03] K. P. Gummadi, R. J. Dunn, and S. Saroiu, “Measurement, Modeling, and Analysis of a Peer-to-Peer File Sharing Workload,” Proceedings of ACM Symposium of Operating Systems Principles, 2003. [RS04] K. Ramachandran and B. Sikdar, “An Analytic Framework for Modeling Peer to Peer Networks,” Proceedings of IEEE INFOCOM, 2005. [YV04] X. Yang, and G. de Veciana, “Service Capacity of Peer-to-Peer Networks,” Proceed- ings of IEEE INFOCOM, 2004. [Her94] H. S. Wilf, generatingfunctionology, 2nd ed. Academic Press, New York, 1994. [LYW08] M. Li, J. Yu and J. Wu, “Free-Riding on BitTorrent-like Peer-to-Peer File Sharing Systems: Modeling Analysis and Improvement,” IEEE Trans. on Parallel and Distributed Systems, Vol.19, No.4, 2008. [Kel01] F. P. Kelly. “Mathematically Modeling of the Internet,” Mathematics Unlimited — 2001 and Beyond, Springer, pp.685-702, 2001. [TK98] H.M. Taylor and S. Karlin, An Introduction to StochasticModeling, 3rd ed. Academic Press, New York, 1998. [CGGG06] G. Carofiglio, R. Gaeta, M. Garetto, P. Giaccone, E. Leonardi, M. Sereno, “A Fluid-Diffusive Approach for Modeling P2P Systems,” Proceedings of IEEE International Symposium on Modeling, Analysis, and Simulation, 2006. [IG60] I. Reed, G. Solomon, “Polynomial Codes Over Certain Finite Fields,” Journal of the Society of Industrial and Applied Mathematics, 1960. [ST06] A. Srinivasan, J. Teitelbaum, and J. Wu. “DRBTS: Distributed Reputation-Based Beacon Trust System, Proceedings of of the 2nd IEEE International Symposium on Dependable, Autonomic and Secure Computing (DASC), 2006. [KSH03] S. D. Kamvar, M. T. Schlosser, and H. G. Molina, “The EigenTrust Algorithm for Reputation Management in P2P networks,” Proceedings of the Twelfth International World Wide Web Conference, 2003. [MV05] L. Massoulie and M. Vojnovic. “Coupon Replication Systems,” ACM Sigmetrics 05, 2005. [All03] L. J. S. Allen, An Introduction to Stochastic Processes with Applications to Biology, Pearson Education Upper Saddle River, NJ, 2003. [Bai90] N. T. J. Bailey, The Elements of Stochastic Processes with Applications to the Natural Sciences, books.google.com, 1990. [Fel71] W. Feller, An Introduction to Probability Theory and its Applications, Volume I, Wiley, New York, 1971. [GPK89] R.L. Graham, O. Patashnik, D.E. Knuth, Concrete mathematics, Addison-Wesley Reading, Mass, 1989. [Por94] S.C. Port, Theoretical Probability for Applications, Wiley New York, 1994. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40151 | - |
dc.description.abstract | 點對點(peer-to-peer,簡稱 P2P)連線軟體,為當今網際網路上最重要的使用者應用之一。在技術面上,點對點連線利用「使用端」對「使用端」(client to client)的通訊技術,讓網路上的主機不必經過中央伺服器即能有效散佈資料,此項技術的特色是,系統的建置成本低廉,而且效能會隨著使用者的數量而提高,所以特別適合於擁有大量使用者的網路應用。常見的P2P應用包括音樂下載服務(例如 Napster、Kazaa) 、線上影音串流(例如PPStream、TVAnts)、以及檔案分享社群(如 BitTorrent、Emule)等等。在此篇論文中,我們針對了BitTorrent-like的檔案分享系統提出一個數學模型。基於此模型,我們建立出應用層的網路拓墣,並在此拓墣上研究檔案分享系統的校能。對於下載端,我們估計出平均檔案下載時間,也提出幾個因地制宜(ad hoc)的最佳化作法,幫助使用者在最快的時間內下載完檔案。對於檔案分享端,我們則提出一個頻寬分配策略,此策略可以最大化檔案在網路上的分配亂度。我們證明:將資料的分配亂度最大化,有助於增進整體系統效能。最後,我們研究了數種使用者行為之下的檔案散佈模式,並在兩種特殊情境中,給出使用者社群壽命與服務達成率的機率估計。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-14T16:41:51Z (GMT). No. of bitstreams: 1 ntu-97-R95922079-1.pdf: 512900 bytes, checksum: 9005bd1c1c94b6514b013a46af9648d0 (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Our contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 The coupon collecting process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Homogeneous coupon probabilities . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Heterogeneous coupon probabilities . . . . . . . . . . . . . . . . . . . . . 7 2.2 The file downloading process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Modeling the content availability . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Modeling the download time . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 Mean download time — unlimited downlink capacity . . . . . . . . . . . . . . . 17 3.2 Mean download time — limited downlink capacity . . . . . . . . . . . . . . . . 20 3.3 Optimal downloader requesting strategies . . . . . . . . . . . . . . . . . . . . . 21 3.3.1 Download time estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Uploader bandwidth allocation mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1 The water-filling method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1.1 Some Elaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Modeling the system performance . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2.1 The simplest case: closed systems . . . . . . . . . . . . . . . . . . . . . 36 4.2.2 Closed systems with peer outflow . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Stationary age structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Impact of the free-riders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Survivability of P2P communities . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2 The simplest case: torrents without peer influx . . . . . . . . . . . . . . . . . . 46 5.3 Permanent seeds and selfish leechers . . . . . . . . . . . . . . . . . . . . . . . . 50 6 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Bibliography . . . . . . . . . . . . . . . . . . . . . . 55 | |
dc.language.iso | en | |
dc.title | 點對點檔案分享系統的建模與分析 | zh_TW |
dc.title | The Modeling and Analysis of P2P File-sharing Systems | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐熊健(Shyong-Jian Shyu),吳邦一(Bang-Ye Wu) | |
dc.subject.keyword | 點對點,網路最佳化,數學模型,非線性系統, | zh_TW |
dc.subject.keyword | peer to peer,networks,modeling,BitTorrent,optimization, | en |
dc.relation.page | 57 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-08-01 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 500.88 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。