在過去二、三十年之間, 網際網路和WWW從一個小型研究計劃成長成為一個巨大的資訊貯藏庫和新的通信媒體。隨著現代電腦架構和網路的發展, 現在每個網路的參與者都可以一起合作以提供嶄新的服務。近年來最著名的故事是ICQ 和Napster。
ICQ 讓使用戶得以彼此即時通信﹐而Napster 讓使用者之間的數位式音樂交換成爲可能。他們兩個都具有兩個非常類似的特徵: 它的用戶都自發地形成網路且這個網路主要依靠所有的參與者來共同運作。這些系統現在被認為屬於所謂的 “Peer-to-Peer” (P2P) 網路。
然而, 隨著這些應用的大受歡迎, 更多問題慢慢地顯露出來。首先 , scalability 和performance對現今任一種網際網路應用都是根本的問題。例如, KaZaA 網路現在隨時都有超過一百五十萬個用戶而且他們之間分享了上千 terabytes的內容。第二, 隨著越來越多的內容在網際網路上散播, 用戶的隱私權, 言論自由和智財權之間的爭議越演越烈。第三, 因爲P2P網路倚賴所有的參與者來提供服務, Peer之間的信任和安全問題必須在系統設計就考慮進去。
在此計畫中我們提出MyP2P, 一個泛用的P2P軟體平臺, 作爲未來Internet service的基礎。MyP2P 不僅將提供各種基本的服務譬如name resolution and routing和資源分配 (resources allocation)﹐也將新題目譬如匿名性、 malicious peers、和網路攻擊納入考量。再者, 為了確認它的validity和viability, 我們將基於MyP2P開發一個檔案分享系統。

In the past decades, the Internet and World Wide Web have grown from a small research project into a huge information repository and a new media for communication. With the development of modern computer architectures and networks, it is now possible for every participant in the network to cooperate with one another to provide innovative new services. The most famous stories in recent years would be the rise of ICQ and Napster.
ICQ enables users to communicate with each other in real time, while Napster makes digital music exchange between users possible. Both of them share the very same characteristics: its users form the virtual network spontaneously, and the network relies mainly on the peers rather than on some centralized servers. These systems are now being known as Peer-to-Peer networks.
However, as the popularity of such applications grows, more issues are revealed. First, the scalability and performance issues are essential to any Internet-scale application nowadays. For example, Morpheus network now has more than one million concurrent users that share hundreds of terabytes of information. Secondly, as more and more contents are being digitalized and transported over the Internet, the struggle between user privacy, freedom of speech and intellectual property rights comes into the scene. Third, since the network functions are performed by the collaboration behaviors among its peers, trust and security issues needs to be reconsidered.
In this project we propose MyP2P, a general-purpose peer-to-peer computing platform, for future computation environment in the Internet. MyP2P will not only provide common services such as name resolution, routing, and resource allocation, but also address new topics such as anonymity, protection against malicious hosts and network attacks. Furthermore, to verify its validity and viability, we will develop file sharing application on top of MyP2P.

Acknowledgements ii
Abstract iii
摘要 iv
Table of Contents v
List of Figures vii
List of Tables viii
MyP2P: A Scalable Agent-Based Peer-to-Peer Network Platform 1
I. Introduction 1
Motivation 1
Research Goals 3
Research Method 5
Outline 6
II. Related work 7
Broadcasting and Distributed Hash Table Based Systems 7
Berkeley OceanStore and Tapestry 8
MIT Cooperative File System and CHORD 10
Content Delivery Network: Akamai 13
Freenet 16
Gnutella 16
III. System Architecture and Key Design Issues 18
System Overview 18
Application Service Layer 19
System Services Layer 20
Base Layer 21
Key Design Issue: Distributed Name Resolution and Fault-Tolerant Routing 22
Key Design Issue: Load Balancing 29
Key Design Issue: Replication Behavior and Resource Allocation 30
IV. System Design and Implementation 33
Base Layer 33
Comparison of MyP2P Base Layer 62
System Service Layer 64
Application Service Layer: A Simple File Sharing System 68
V. Future Work 71
P2P Systems over Wireless/Ad Hoc Networks 71
Key-word based Search, Meta-Data Attachment and Association for Arbitrary Objects 71
Online Replicating/Paging behavior 71
Online Service Composition 71
Distributed Security/Trust Chain or Domain 72
Recommendation and Reputation Mechanisms 72
Adaptation to Asymmetric Networks 72
Load-Balancing with Localized/Global Knowledge 72
References 73

[1]. http://www.akamai.com
[2]. http://www.icq.com
[3]. http://www.napster.com
[4]. Jeff Schneider. “Convergence of Peer and Web Services”, O’reilly OpenP2P.com. 2001 http://www.openp2p.com/pub/a/p2p/2001/07/20/convergence.html
[5]. http://www.isc.org
[6]. Wired News 2001 Oct. 6. SETI@Home Expands its Back Yard. http://www.wired.com/news/technology/0%2C1282%2C47365%2C00.html
[7]. IBM Research 1997. Kasparov vs. Deep Blue: The Rematch. http://www.research.ibm.com/deepblue/home/html/b.html
[8]. Microsoft .NET Passport service. http://www.microsoft.com/myservices/passport/default.asp
[9]. W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lilley. The design and implementation of an intentional naming system. In Proceedings of the 17th Symposium on Operating Systems Principles, pages 186--201, Kiawah Island, SC, USA, Dec. 1999. ACM
[10]. Fred S. Annexstein, Kenneth A. Berman, and Mihajlo A. Jovanovi. Latency effects on reachability in large-scale peer-to-peer networks. In Proceedings of the 13th annual Symposium on Parallel algorithms and architectures, pages 84 —92, Crete Island, Greece, 2001. ACM
[11]. B. Awerbuch, Y. Azar, and Y. Bartal. On-line Generalized Steiner Problem. In Proc. 7th Ann. ACMSIAM Symp. on Discrete Algorithms. pp. 68--74, 1996
[12]. B. Awerbuch, Y. Bartal, and A. Fiat, Distributed Paging for General Networks, in Journal of Algorithms, July 1998. vol.28, no.1, p. 67-104.
[13]. B. Awerbuch, B. Patt, D. Peleg, and M. Saks. Adapting to asynchronous dynamic networks with polylogarithmic overhead. In Proceedings of 24th ACM Symposium on Theory of Computing, pages 557--570, 1992
[14]. B. Awerbuch and D. Peleg 1990. Sparse Partitions. In Proceedings of IEEE Symposium on Foundations of Computer Science, pages 503─513, 1990
[15]. B. Awerbuch and D. Peleg. Concurrent on-line tracking of mobile users. In sigcomm, pages 221--233, Zurich, Switzerland, September 1991. ACM;. also in Computer Communication Review 21 (4), Sep. 1991.
[16]. Awerbuch and D. Peleg. Online Tracking of Mobile Users. Journal of the Association for Computing Machinery, vol. 42, no. 5, pp. 1021-1058, September 1995
[17]. Y. Bartal, A. Fiat, and Y. Rabani. Competitive algorithms for distributed data management. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 39-- 50, May 1992.
[18]. B. Bloom. Space/time trade-offs in hash coding with allowable errors. In Communications of the ACM, July 1970, vol. 13(7), pp. 422--426.
[19]. A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrel. A Hierarchical Internet Object Cache. In Proceedings of the USENIX Annual Technical Conference, pages 153--163, January 1996.
[20]. Pierluigi Crescenzi and Viggo Kann. A Compendium of NP Optimization Problems. http://www.nada.kth.se/~viggo/problemlist/compendium.html
[21]. Ian Clarke, Oscar Sandberg, Brandon Wiley, and Theodore Hong. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability, pages 46--66, July 2000.
[22]. Lenore J. Cowen and Christopher G. Wagner 2000. Compact Roundtrip Routing in Directed Networks. In Proceedings of ACM Symposium on Principles of Distributed Computing, pages 51─59, 2000
[23]. F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), Chateau Lake Louise, Banff, Canada, October 2001
[24]. S. Dolev and T. Herman. SuperStabilizing Protocols for Dynamic Distributed Systems. Chicago Journal of Theoritical Computer Science, Vol. 1997, Art. 4, The MIT Press, December 19, 1997
[25]. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth ACM Symposium on Principles of Distributed Computing, pages 1--12, Vancouver, British Columbia, August 1987.
[26]. P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. IDMaps: a global internet host distance estimation service. IEEE/ACM Transactions on Networking, October 2001.
[27]. B. Gavish, O. R. Liu Sheng, "Dynamic File Migration in Distributed Computer Systems", Communications of the ACM, Vol. 33, pages 177--189, Feb. 1990.
[28]. M. X Goemans, A V. Goldberg, S. Plotkin, D.B. Shmoys,E. Tardos, and D.B. Williamson. Improved Approximation algorithms for Network Design Problems. In Proceedings of 5th ACM Symposium on Discrete Algorithms, pages 223─232, 1994
[29]. B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman. Tight analyses of two local load balancing algorithms. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 548--558, May 1995.
[30]. Mor Harchol-Balter, T. Leighton, and D. Lewin. Resource discovery in distributed networks. In 8th Annual ACM-SIGACT/SIGOPS Symposium on Principles of Distributed Computing, Atlanta, May 1999.
[31]. Kris Hildrum, John D. Kubatowicz, Satish Rao, and Ben Y. Zhao 2002. Distributed Object Location in a Dynamic Network. In Proceedings of ACM Symposium of Parallel Architectures and Algorithms, 2002
[32]. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pages 654--663, El Paso, Texas, May 1997.
[33]. D. Kempe, J. Kleinberg, and A. Demers. Spatial Gossip and Resource Location Protocols. In Proceedings of the Thirty Third Annual ACM Symposium on Theory of Computing (STOC), Crete, Greece, July 2001.
[34]. J. Kubiatowicz, D. Bindel, P. Eaton, Y. Chen, D. Geels, R. Gummadi, S. Rhea, W. Weimer, C. Wells, H. Weatherspoon, and B. Zhao. OceanStore: An architecture for global-scale persistent storage. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, volume 35, pages 190-201, Nov. 2000.
[35]. Shay Kutten and David Peleg. Deterministic distributed resource discovery. In Nineteenth Annual ACM SIGACT/SIGOPS Symposium on Principles of Distributed Computing, pages 16 — 19. Portland, Oregon, July 2000.
[36]. Shay Kutten, David Peleg, and Uzi Vishkin. Deterministic Resource Discovery in Distributed Networks. In Proceedings of ACM Symposium on Parallel Architectures and Algorithms, pages 77─83, 2001
[37]. Adam Langley 2001. The FreeNET Protocol. http://freenet.sourceforge.net/index.php?page=protocol
[38]. F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays•Trees•Hyper Cubes. Morgan Kaufmann 1992
[39]. Nancy Lynch 1996, Distributed Algorithms, Morgan Kaufmann 1997
[40]. Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algo- rithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 322-333, Chicago, Illinois, 2-4 May 1988.
[41]. S. Muthukrishnan and R. Rajaraman. An Adversarial Model for Distributed Dynamic Load Balancing. In Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 47--54, June 1998.
[42]. K. Petersen, M. Spreitzer, D. Terry, and M. Theimer. Bayou: Replicated Database Services for Worldwide Applications. In Proceedings 7th SIGOPS European Workshop, pages 275--280, Connemara, Ireland, Sept. 1996. ACM.
[43]. C.G. Plaxton, R. Rajaraman, and A.W Richa. Accessing nearby copies of replicated objects in a distributed environment. Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, Newport, Rhode Island, pages 311--320, June 1997.
[44]. C. G. Plaxton and R. Rajaraman. Fast fault-tolerant concurrent access to shared objects. In Proc. of the 37th IEEE Symposium on Foundations of Computer Science (FOCS), pages 570--579, 1996.
[45]. R. Rajaraman, A. W. Richa, B. Vöcking, G. Vuppuluri. A Data Tracking Scheme for General Networks. In Proceedings of Thirteen ACM Symposium on Parallel Algorithms and Architectures, pages 247 —254, 2001.
[46]. S. Raman and S. McCanne. A model, analysis, and protocol framework for soft state-based communication. In ACM SIGCOMM, (Cambridge, Massachusetts, USA), pages 15 —25, September 1999.
[47]. A. Rowstron, P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms, 2001
[48]. T. Sander and C. Tschudin. Towards mobile cryptography. In Proceedings of the 1998 IEEE Symposium on Security and Privacy, pages 215 — 224, Oakland, California, May 1998
[49]. T. Sander and C. Tschudin. Protecting Mobile Agents Against Malicious Hosts. In G. Vigna, editor, Mobile agents and security, volume 1419 of Lecture Notes in Computer Science, pages 44--60. Springer-Verlag, New York, NY, 1998.
[50]. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, Chord: A scalable peerto -peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM Symposium on Communication, Architecture, and Protocols (San Diego, CA, U.S.A., Aug. 2001), ACM SIGCOMM, pp. 149--160.
[51]. E. Ukkonen. On-Line Construction of Suffix Trees, Algorithmica 14, pages 246-260,1995.
[52]. B. Y. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley, 2001