本論文針對同儕式（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.

第一章　簡介
第二章　同儕式網路檔案分享系統－以BitTorrent為例
第三章　節點分享公平性議題與解決方法
第四章　檔案片段可得性議題與解決方法
第五章　結語
英文附錄

1. Napster [Online]. Available: http://www.napster.com/. The original Napster MP3-sharing systems was shut down in July 2001 and the current Napster services is provided by US electronics retailer.
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.
3. IPOQUE Report. “Internet Study 2008/2009”, 2009. Available: http://www.ipoque.com/resources/internet-studies/internet-study-2008_2009.
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/.
6. K. Savetz, N. Randall, and Y. Lepage, MBONE: Multicasting Tomorrow's Internet, IDG Publisher, 1996.
7. Y. H. Chu, S. G. Rao, and H. Zhang, “A Case for End System Multicast,” in Proc. ACM SIGMETRICS Int'l Conf. on Measurement and Modeling of Computer Systems, 2000.
8. EMS [Online]. Available: http://esm.cs.cmu.edu/.
9. Skype [Online]. Available: http://www.skype.com/.
10. X. Zhang, J. Liu, B. Li, and T. S. P. Yum, “Coolstreaming/DONet: A Data-Driven Overlay Network for Efficient Live Media Streaming,” in Proc. IEEE INFOCOM, 2005.
11. Coolstreaming [Online]. Available: http://www.coolstreaming.us/.
12. Akamai [Online]. Available: http://www.akamai.com/.
13. A. Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O'Reilly publisher, 2001.
14. D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, and Z. Xu, “Peer-to-Peer Computing,” Technical Report HPL-2002-57 (R.1), HP Laboratories Palo Alto, 2003.
15. S. Saroiu, P. K. Gummadi, and S. D. Gribble, “A Measurement Study of Peer-to-Peer File Sharing Systems,” in Proc. Multimedia Computing and Networking, 2002.
16. S. Sen and J. Wang, “Analyzing Peer-to-Peer Traffic Across Large Networks,” in IEEE/ACM Trans. Networking, vol. 12, no. 2, pp. 219-232, April 2004.
17. eDonkey, also known as eDonkey2000 or eD2k [Online]. Available: http://en.wikipedia.org/wiki/EDonkey_network.
18. eMule, one of the clients to connect the eDonkey network [Online]. Available: http://www.emule.com/.
19. LimeWire [Online]. Available: http://www.limewire.com/.
20. KaZaA [Online]. Available: http://www.kazaa.com/.
21. B. Cohen, “Incentives Build Robustness in BitTorrent,” in Proc. Workshop on Economics of Peer-to-Peer Systems, 2003.
22. BitTorrent [Online]. Available: http://www.bittorrent.com/.
23. P. Rodriguez and E. W. Biersack, “Dynamic Parallel Access to Replicated Content in the Internet,” in IEEE/ACM Trans. Networking, Vol. 10, No. 4, pp. 455-465. , Aug. 2002
24. J.W. Byers, J. Considine, M. Mitzenmacher, and S. Rost, “Informed Content Delivery Across Adaptive Overlay Networks,” in IEEE/ACM Trans. Networking, vol. 12, no. 5, pp. 767-780, Oct. 2004.
25. D. Qiu and R. Srikant, “Modeling and Performance Analysis of BitTorrent-like Peer-to-Peer Network,” in Proc. ACM SIGCOMM, 2004.
26. J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips, “The BitTorrent P2P File-Sharing System: Measurements and Analysis,” in Proc. Int'l Workshop on Peer-to-Peer Systems (IPTPS), 2005.
27. L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, and X. Zhang, “A Performance Study of BitTorrent-like Peer-to-Peer Systems,” in IEEE J. on Selected Areas in Communications, Vol. 25, No. 1, pp. 155-169, Jan. 2007.
28. A. Legout, “Rarest First and Choke Algorithms Are Enough,” Technical Report INRIA-00001111 (Ver. 1), INRIA, Feb. 2006.
29. Y. Tian, D. Wu, and K.W. Ng, “Modeling, Analysis and Improvement for BitTorrent-like File Sharing Networks,” in Proc. IEEE INFOCOM, 2006.
30. M. Izal, G. Urvoy-Keller, E. W. Biersack, P. A. Felber, A. A. Hamra, and L. Garces-Erice, “Dissecting BitTorrent: Five Months in a Torrent's Lifetime,” Passive and Active Measurements, 2004.
31. A. Legout, G. Urvoy-Keller, and P. Michiardi, “Understanding BitTorrent: An Experimental Perspective,” INRIA Technical Report INRIA-00000156 (Ver. 3), INRIA, Nov. 2005.
32. A. R. Bharambe, C. Herley, and V. N. Padmanabhan, “Analyzing and Improving a BitTorrent Network's Performance Mechanisms,” in Proc. IEEE INFOCOM, 2006.
33. D. Purandare and R. Guha, “Preferential and Strata Based P2P Model: Selfishness to Altruism and Fairness,” in Proc. 12th Int'l Conf. on Parallel and Distributed Systems (ICPADS 2006), 2006.
34. A. Nazareno, M. Miranda, L. Aliandro, W. Gustavo, and R. Matei, “Influences on Cooperation in BitTorrent Communities,” in Proc. ACM SIGCOMM Workshop on Economics of Peer-to-Peer Systems (P2PECON), 2005.
35. N. Liogkas, R. Nelson, E. Kohler, and L. Zhang, “Exploiting BitTorrent for Fun (But Not Profit),” in Proc. 5th Int'l Workshop on Peer-to-Peer Systems (IPTPS), 2006.
36. S. Jun and M. Ahamad, “Incentives in BitTorrent Induce Free Riding,” in Proc. ACM SIGCOMM workshop on Economics of Peer-to-Peer Systems (P2PECON), pp. 116-121, 2005.
37. Gnutella [Online]. Available: http://www.gnutellaforums.com/.
38. A. Rowstron1 and P. Druschel, “Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems”, in Proc. 18th IFIP/ACM Int'l Conf. on Distributed Systems Platforms, 2001.
39. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan,”Chord: A Scalable Peertopeer Lookup Service for Internet Applications”, in Proc. ACM SIGCOMM, 2001.
40. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network”, in Proc. ACM SIGCOMM, 2001.
41. D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin, “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,” in Proc. 29th Annual ACM Symposium on Theory of Computing, 1997.
42. E. Adar and B.A. Huberman, “Free Riding on Gnutella,” First Monday, Vol. 5, No. 10, Oct. 2000.
43. D. Hughes, G. Coulson, and J. Walkerdine, “Free Riding on Gnutella Revisited: The Bell Tolls?” in IEEE Distributed Systems Online, June 2005.
44. M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica, “Free-Riding and Whitewashing in Peer-to-Peer Systems,” in IEEE J. of Selected Areas in Communications, Vol. 24, Issue 5, pp. 1010-1019, 2006.
45. T. Locher, P. Moor, S. Schmid, and R. Wattenhofer, “Free Riding in BitTorrent is Cheap,” HotNets V, pp. 85-90, 2006.
46. J. Yu, M. Li, and J. Wu, “Modeling Analysis and Improvement for Free-Riding on BitTorrent-like File Sharing Systems,” in Proc. Int'l Conf. on Parallel Processing Workshops (ICPPW), 2007.
47. M. Sirivianos, J. H. Park, R. Chen, and X. Yang, “Free-riding in BitTorrent Networks with the Large View Exploit,” in Proc. 6th Int'l Workshop on Peer-to-Peer Systems (IPTPS), 2007.
48. M. Liu, J. Yu, and J. Wu, “Free-Riding on BitTorrent-like Peer-to-Peer File Sharing Systems: Modeling Analysis and Improvement,” in IEEE Trans. on Parallel and Distributed Systems, Vol. 19, Issue 7, pp. 954-966, July 2008.
49. B. Fan, J. C. S. Lui, and D.-M. Chiu, “The Design Trade-Offs of BitTorrent-like File Sharing Protocols,” in IEEE/ACM Transactions on Networking, Vol. 17, No. 2, pp. 365-376, April 2009.
50. D. Guan, J. Wang, Y. Zhang, and J. Dong, “Understanding BitTorrent Download Performance,” in Proc. 7th Int'l Conf. on Networking, 2008.
51. P. Zheng and C. Wang, “SODON: A High Availability Multi-Source Content Distribution Overlay,” in Proc. IEEE Int'l Conf. Computer Communications and Networks, 2004.
52. J.J. Cheng, X. Lv, K.F. Yu, and J. Ma, “A Study on the Pieces on Seed for Mobile Peer-to-Peer File Sharing Applications,” in Proc. IEEE Int'l Conf. Wireless Communications, Networking and Mobile Computing, 2005.
53. H. Chen, Z. Gong, and Z. Huang, “Parallel Downloading Algorithm for Large-volume File Distribution,” in Proc. IEEE Int'l Conf. Parallel and Distributed Computing, Applications and Technologies, 2005.
54. H. Park and M. V. D. Schaa, “Evolution of Resource Reciprocation Strategies in P2P Networks,” in IEEE Transactions on Signal Processing, Vol. 58, No. 3, pp. 1205-1217, March 2010.
55. R. Sherwood, R. Braud, and B. Bhattacharjee, “Slurpie: A Cooperative Bulk Data Transfer Protocol,” in Proc. IEEE INFOCOM, 2004.
56. R. Izhak-Ratzin, N. Liogkas, and R. Majumdar, “Team Incentives in BitTorrent Systems,” in Proc. 18th Int'l Conf. on Computer Communications and Networks (ICCCN), 2009.
57. F. Qiny, J. Liuy, and L. Zheng, “Improving Robustness and Fairness on BitTorrent-like P2P Systems,” in Proc. 4th Int'l Conf. On Communications and Networking in China, 2009.
58. X. Chen, X. Chu, and X, Chang, “Incentive Framework using Shapley Value for BitTorrentlike Systems,” in Proc. IEEE 7th Int'l Conf. on Information, Communications and Signal Processing (ICICS), 2009.
59. H. Schwetman, “CSIM18—The Simulation Engine,” in Proc. 28th IEEE Conf. Winter Simulation, 1996.
60. F. Esposito, I. Matta, P. Michiardiy, N. Mitsutake, and D. Carra, “Seed Scheduling for Peer-to-Peer Networks,” in Proc. 8th IEEE Int'l Symposium on Network Computing and Applications, 2009.
61. Bittorrent Protocol Specification v1.0 [Onilne]. Available: http://wiki.theory.org/BitTorrentSpecification.
62. P. Golle, K. Leyton-Brown, I. Mironov, and M. Lillibridge, “Incentives for Sharing in Peer-to-Peer Networks,” in Lecture Notes in Computer Science, Vol. 2232, pp. 75-87, 2001.
63. D. Levin, K. LaCurts, N. Spring, and B. Bhattacharjee, “BitTorrent is an Auction: Analyzing and Improving BitTorrent’s Incentives,” in Proc. ACM SIGCOMM, 2008.
64. S. K. Nair, E. Zentveld, B. Crispo, and A. S. Tanenbaum, “Floodgate: A Micropayment Incentivized P2P Content Delivery Network,” in Proc. 17th Int'l Conf. On Computer Communications and Networks (ICCCN), 2008.
65. G. Wei, M. Xie, Y. Mao, and A. V. Vasilakos, “A Budget-based Cost-effective Incentive Model,” in Proc. Int'l Conf. on Parallel Processing Workshops (ICPPW), 2009.
66. B. N. Chun, D. E. Culler, T. Roscoe, A. C. Bavier, L. L. Peterson, M. Wawrzoniak, and M. Bowman, “Planetlab: an overlay testbed for broad-coverage services,” in ACM SIGCOMM Computer Communication Review, Vol. 33, No. 3, pp. 3–12, July 2003.
67. PlanetLab [Online]. Available: http://www.planet-lab.org/.