臺灣博碩士論文加值系統

現今的網路，點對點網路的應用頗受眾人所關注，其中最熱門的應用即是檔案分享的技術。在點對點網路系統中，系統的效能取決於peers的行為。但是自私的peers使用了網路資源卻不願意貢獻資源給系統，影響其他peers的下載與系統效能。也因此有人引入了以牙還牙的策略來對抗自私的行為。在以牙還牙的策略中，為了不吃虧，各個peer的下載量等於它的上傳量。雖然以牙還牙的策略能夠有效的抑制自私行為，然而也因為限制條件過於嚴格反而減少peers之間的檔案傳遞的意願、降低系統效能、甚至可能會癱瘓整個系統。
本篇論文嘗試探討的是容忍型的以牙還牙策略。在此策略之下，下載量與上傳量的差異只有在容忍值之內既可。我們著重在點對點網路的效能界限分析，從參與下載的peers數、pieces數與檔案下載完成所需要時間以及Seed的負載來討論，推導分析出理論效能界限。比較推導結果與其他策略，證明在此策略機制能有效的下載檔案，減輕Seed負載並提升整體系統效益。

In current networks, the peer-to-peer network applications have received much attention. The most popular application is content distribution techniques. In peer-to-peer network, the system performance is depending on the behaviors of each peer. The selfish peers use resources but are willing to contribute, therefore impact the other peer’s download and hurt the whole network system. The peer-to-peer network attempts to reduce the number of selfish peers by employing the Tit-for-Tat strategy. To counterstrike the selfish peer, the upload amount is controlled so that it never exceeds the amount of download. It has been proved that this strategy can reduced the selfish behavior, but the constraint may be too strict to reduce the willingness of content delivering between peers, decrease the system performance, even the entire network might be crashed.
This paper studies a tolerable Tit-for-Tat strategy such that the difference between upload and download is only required to be less than a tolerance. We focus on the analysis of the download time and Seed workload, based on the number of participating peers and the number of pieces. We then derive some theoretical bounds on these performances. Compare the derivation of the results and the other strategies, proving that our strategy can efficiently download the file, reduce the Seed workload, and improve the whole system efficiency.

圖表目錄 6
第一章 序論 7
1.1 研究背景 7
1.2 研究動機 8
1.3 研究成果 8
1.4 論文架構 8
第二章 背景知識與相關研究 9
2.1 主從式（Client/Server）網路架構 9
2.2 點對點（Peer-to-Peer）網路架構 10
2.2.1 Tit-for-Tat策略機制 11
2.2.2 Fully Cooperative策略機制 12
2.3 其他研究 13
第三章 研究方法與設計 14
3.1 分析標準 14
3.2 主從式網路架構 15
3.2.1 系統模型. 15
3.2.2 系統假設 15
3.2.3主從式架構效能界限 15
3.2.4主從式架構效能分析 16
3.3 點對點網路架構 16
3.3.1 系統模型 16
3.3.2 Fully Cooperative 16
3.3.2.1 FC系統假設 16
3.3.2.2 FC策略效能界限 17
3.3.2.3 FC效能分析與比較 18
3.3.3 Tit-for-Tat 19
3.3.3.1 T4T系統假設 19
3.3.3.2 T4T策略效能界限 19
3.3.3.3 T4T策略效能分析 21
第四章 理論證明與分析 23
4.1 Fibonacci-T4T策略 23
4.2 Fibonacci-T4T運作方式 24
4.3 Order of download time 27
4.3.1 Theorem 1 27
4.3.2 Theorem 1證明 27
4.3.3 Theorem 1分析 29
4.4 Exact download time 30
4.4.1 Theorem 2 30
4.4.2 Theorem 2證明 31
4.4.3 Theorem 2分析 43
4.5 各種策略的比較 44
第五章 結論與未來展望 45
5.1 結論 45
5.2 未來展望 45
參考文獻 46

[1] http://www.emule-project.net/.
[2] http://www.bitcomet.com/.
[3] http://www.gnutella.com/.
[4] http://bittorrent.org/.
[5] B. Cohen, “Incentives build robustness in BitTorrent”. In Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, June 2003.
[6] Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose and D. Towsley, “Modeling Peer-Peer File Sharing Systems”. In Proceedings of IEEE INFOCOM, 2003.
[7] D. Qiu and R. Srikant, “Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks”. In Proceedings of ACM SIGCOMM, 2004.
[8] X. Yang and G. de Veciana, “Service Capacity of Peer to Peer Networks”. In Proceedings of IEEE INFOCOM, 2004.
[9] T. Locher, S. Schmid, and R. Wattenhofer. “Rescuing tit-for-tat with source coding”. In 7th IEEE International Conference on Peer-to-Peer Computing, 2007.
[10] D. do B. DeFigueiredo, B. Venkatachalam and S. Wu, “Bounds on the Performance of P2P Networks Using Tit-for-Tat Strategies”. In 7th IEEE International Conference on Peer-to-Peer Computing, 2007.
[11] A. Legout, G. Urvoy-Keller, and P. Michiardi. “Understanding BitTorrent: An Experimental Perspective”. Technical report, INRIA, 2005
[12] Tang Y., Wang, H., and Dou W. “Trust Based Incentive P2P Network”, Proceedings of the IEEE International Conference on E-Commerce Technology for Dynamic E-Business (CEC-East’04), 2004
[13] Richard T. B. Ma, Sam C. M. Lee, John C. S. Lui, David K. Y. Yau, “An Incentive Mechanism for P2P Networks”, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS’04), p. 516-523, 2004.
[14] David Hales, “Form Selfish Nodes to Cooperative Networks-Emergent Link-based incentives in Peer-to-Peer Networks”, Proceedings of the Fourth International Conference on Peer-to-Peer Computing (P2P’04), 2004.
[15] Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, “A Game Theoretic Framework for Incentives in P2P Systems”, Proceedings of the 3rd. International Conference on Peer-to-Peer Computing, p.48, September 01-03, 2003.
[16] Shih-Neng, Wu, “The Evaluation of Inquiry-based Learning with Incentive Mechanism on Peer-to-Peer Networks”, Master Thesis, Department of Information Management, National Sun Yat-sen University, Taiwan, R.O.C. 2003.
[17] Karl R. Lang and Roumen Vragov, “A Pricing Mechanism for Digital Content Distribution Over Peer-to-Peer Networks”, Proceedings of Hawaii International Conference on Systems Sciences, January, p. 211a-211a, 2005.
[18] Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble, “A measurement study of peer-to-peer file sharing systems,” in Proceedings of Multimedia Computing and Networking, San Jose, January 2002.
[19] T.S. Eugene Ng, Yang hua Chu, Sanjay G. Rao, Kunwadee Sripanidkulchai, and Hui Zhang, “Measurement-based optimization techniques for bandwidth-demanding peer-to-peer systems,” in proceedings of IEEE INFOCOM03, San Francisco, April 2003.
[20] A. R. Bharambe, C. Herley, and V. N. Padmanabhan, “Analysing and improving bittorrent performance,” Microsoft Research, Microsoft Corporation One Microsoft Way Redmond, WA 98052, USA, Tech. Rep. MSR-TR-2005-03, February 2005.