臺灣博碩士論文加值系統

隨著資訊傳輸技術的快速發展，點對點運算所提供的直接對端存取(direct access)鉅量資訊功能的架構，漸趨為大眾所重視和採用。而當前點對點運算相關探討中，有效的檔案搜尋和負載平衡可謂點對點環境中的重要研究議題，特別是應用在那些沒有主從式架構的網路之中。雖然已經有許多學者提出了相關的研究方法來解決這一類的問題，但是卻沒有辦法在提供有效的檔案搜尋之同時兼顧點對點網路的負載平衡，因此衍生嚴重的負載不平衡之缺失，從而增加使用者的反應時間和降低網路整體的效能。有鑑於此，本篇論文基於 Domain Name Server (DNS) 提出分散式服務搜尋之階層式架構以快速地搜尋到所需要的檔案，來減少使用者的搜尋次數和搜尋時所花費的時間，並兼顧使用者的反應時間和負載平衡的問題。同時以代理人 P2P Registry（P2PReg）的方式來當作DNS和使用者之間的仲介，讓使用者可以透過P2PReg來加入點對點網路和搜尋所需要的服務。為了避免搜尋時回傳的列表有過多與主題不相關的資訊，我們會先把使用者提供分享的資源依檔案的特性分門別類以利查詢。本篇論文所提出的架構，針對前述點對點運算的問題，不但能有效的減短使用者的搜尋時間，同時也能兼顧整個點對點網路的負載平衡，從而避免發生熱門點hotspot (指某一點瞬間有大量的使用者湧入) 的現象。顯而易見的，當檔案重複數越多，熱門點的情況也越能獲得改善，其傳輸品質也會更好。我們也經由實驗模擬來驗證本篇論文所提出的方法之可行性。經由實驗，我們發現區域性之檔案搜尋方式即能讓使用者快速且正確的搜尋到所需的檔案，同時整個系統的效能具有效的提升。

Peer-to-Peer (P2P) systems have attracted much current attention as a popular way to share huge volumes of resources directly within peers. Efficient content search and load balance are both important research issues in P2P environments, especially in those without centralized global indexes. Although a number of content search schemes are known to alleviate these problems, they cannot provide flexible object searches while balance the load for content demand in P2P networks, thereby resulting in severe load imbalance and consequently increased user response times. In this paper we tend to address these problems that take advantage of current Domain Name Server (DNS) architecture by harnessing all available resources in the P2P networks and balance the load without decreasing user response time. We proposed a novel decentralized service discovery mechanism by creating an agent call P2P Registry (P2PReg) as a middleware within DNS and peers. In our scheme, each peer is able to join in the P2P networks and discover desirable services through current DNS within a short duration in an efficient way with the help of P2PReg. In order to avoid in returning large unneeded peer lists in a request, we also capture the interests and resources being shared by peers as different services. The proposed method does not only perform least searching time and low bandwidth but also balances load in P2P systems in order to avoid hotspot (refers to a node which receives a large volume of requests in rapidly) problems naturally. It is obvious that the more replicas there are, the better the media delivery quality of the specific content object is. We also present the results of simulation work to validate the viability of our approach. Our simulation study showed that serving data discovery over local search is indeed effective in improving the system performance significantly.

中文摘要 (Abstract in Chinese) I
Abstract II
誌謝 (Acknowledgements) III
Contents IV
List of Tables VII
List of Figures VIII

Chapter 1 Introduction 1
1.1 Research Background 1
1.2 The Problems 7
1.3 Research Contributions 8
1.4 Chapters Outline 10

Chapter 2 Review of Related Work 11
2.1 Unstructured P2P Systems 11
2.1.1 Napster 12
2.1.2 Gnutella 14
2.1.3 Freenet 17
2.1.4 FastTrack / KaZaA 19
2.2 Structured P2P Systems 22
2.2.1 Chord 22
2.2.2 Content Addressable Network (CAN) 24
2.3.3 Tapestry 26
2.3.4 Pastry 28

Chapter 3 Service Discovery Mechanism 31
3.1 Design Description 31
3.1.1 DNS Overview 34
3.1.2 P2P Registry (P2PReg) 35
3.1.3 Group Classification 36
3.2 Self Organization 38
3.2.1 Peer Joins 39
3.2.2 Peer Departures / Failure 40
3.3 Routing 41

Chapter 4 Load Balance 46
4.1 Finding Nearby Peers 47
4.2 Replicas 47

Chapter 5 Simulation Result 51
5.1 Evaluating Service Discovery Performance 52
5.1.1 Discussion 56
5.2 Balanced Load Distribution 57
5.2.1 Discussion 60

Chapter 6 Conclusions 66

Publication List of Phui-Si Gan 72

[1] Napster Inc., in http://www.napster.com.
[2] KaZaA, in http://www.kazaa.com, 2002.
[3] Gnutella, in http://www.gnutella.wego.com, 2001.
[4] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, “Freenet: A Distributed Anonymous Information Storage and Retrieval System”, in work on Design Issues in Anonymity and Unobservability, July 2000, pp. 311-320.
[5] Peer-to-Peer Working Group, in http://www.peer-to-peerwg.org/.
[6] Open P2P, in http://www.openp2p.com.
[7] G. Moro, A. M. Ouksel and C. Sartori, “Agents and Peer-to-Peer Computing: A Promising Combination of Paradigms”, in Proceedings of the International Workshop on Agents and Peer-to-Peer Computing (AP2PC 2002), LNAI 2530, 2003, pp. 1-14.
[8] M. Roussopoulos, M. Baker, D. Rosenthal, T. Guili, P. Maniatis and J. Mogul, “2 P2P or Not 2 P2P?”, in Proceedings of the 3rd International Workshop on Peer-to-Peer Systems, San Diego, CA, USA, February 26-27, 2004.
[9] D. Tsoumakos and N. Roussopoulos, “A Comparison of Peer-to-Peer Search Methods”, in Proceedings of the International Workshop on the Web and Databases (WebDB), June 12-13, 2003.
[10] K. Young, “Look no Server”, Network, March 1993, pp.21, 22 & 26.
[11] S. Simon, “Peer-to-Peer Network Management in an IBM SNA Network”, IEEE Network Magazine, Vol. 5, March 1991, pp. 30-34.
[12] P. S. Munindar, “Peering at Peer-to-Peer Computing”, IEEE Internet Computing 2001, January/February 2001.
[13] Athens University of Economics and Business, “White Paper: A Survey of Peer-to-Peer File Sharing Technologies”, The eBusiness Centre.
[14] R. Schollmeier, “A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications”, in Proceedings of the IEEE Conference Peer-to-Peer 2001, August 2001, pp. 27-39.
[15] K. L. Eng, J. Crowcroft, M. Pias, R. Sharma and S. Lim, “A Survey and Comparison of Peer-to-Peer Overlay Network Schemes”, IEEE Communications Survey and Tutorial, March 2004, pp.1-22.
[16] Q. Lv, S. Ratnasamy, and S. Shenker, “Can Heterogeneity Make Gnutella Scalable?”, in Proceedings of the 1st Internationla Workshop on Peer-to-Peer Systems (IPTPS’02), MIT Faculty Club, Cambridge, MA, USA, March 2002.
[17] I. Stocia, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications”, in Proceedings of the ACM SIGCOMM, August 2001, pp.149-160.
[18] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network”, in Proceedings of the ACM SIGCOMM, August 2001, pp.161-172.
[19] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph, “Tapestry: An Infrastructrure for Fault-Tolerant Wide-Area Location and Routing”, Technical Report UCB/CSD-01-1141, April 2000, pp.41-53.
[20] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems”, IFIP/ACM Middleware, 2001.
[21] P. Maymounkov and D. Mazières, “Kademlia: A Peer-to-Peer Information System Based On the Xor Metric”, in Proceedings of the IPTPS, Cambridge, MA, USA, February 2002, pp. 53-65.
[22] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, and S. Shenker and I. Stoica, “The Impact of Dht Routig Geometry on Resilience and Proximity”, in Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocol for Computer Communications, August 2003, pp. 381-394.


[23] H. C. Hsiao and C. T. King, “Similarity Discovery in Structured P2P Overlays”, in Proceedings of the 2003 International Conference on Parallel Processing (ICPP’03), 2003.
[24] R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker and I. Stoica, “Querying the Internet with PIER”, in Proceedings of the 29th International Conference on Very Large Databases (VLDB ‘03), Berlin, Germany, September 2003.
[25] A. Crespo, H. Garcia-Molina, “Routing Indices for Peer-to-Peer systems”, in Proceedings of the International Conference of Distributed Computing Systems, (ICDCS’02), IEEE Computer Society July 2002, pp. 23-32.
[26] F. M. Cuenca-Acuna and T. D. Nguyen, “Text-based Content Search and Retrieval in Ad hoc P2P Communities”, Lecture Notes in Computer Science, May 2002, pp.220-234.
[27] M. K. Ramanathan, V. Kalogeraki, and J. Pruyne, “Finding Good Peers in Peer-to-Peer Networks”, in Proceedings of the International Parallel and Distributed Processing Symposium, IEEE Computer Society, April 2002.
[28] FastTrack, in http://www.fasttrack.nu, 2003.
[29] MA. Jovanovich, FS. Annexstein, and KA. Berman. “Scalability Issues in Large Peer-to-Peer Networks - A Case Study of Gnutella”, Technical report, ECECS Department, University of Cincinnati, Cincinnati, OH 45221, 2001.
[30] J. Ritter. “Why Gnutella Can’t Scale. No, Really”,
in http://www.darkridge.com/jpr5/gnutella.html/, February 2001.
[31] Gnutella Ultrapeers,
in http://rfc-gnutella.sourceforge.net/Proposals/Ultrapeer/Ultrapeers.htm/,2002
[32] I. Clarke, S. G. Miller, T. W. Hong, O. Sandberg, and B. Wiley, “Protecting Free Expression Online with Freenet”, IEEE Internet Computing, January/February 2002.
[33] Morpheus, in http://www.musiccity.com, 2002.
[34] Grokster, in http://www.grokster.com
[35] iMesh, in www.imesh.com
[36] D. Karger, E. Lehman, T. Leighton, R. Panigraphy, M. Levine, and D. Lewein, “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 Theory of computing, May 1997, pp. 654-663.
[37] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, “Wide-area Cooperative Storage with CFS”, in Proceedings of the eighteenth ACM Symposium on Operating Systems Principles, 2001, pp. 202-215.
[38] “Secure Hash Standard”, Federal Information Processing Standards 180-1, National Institute of Standard and Technology, U.S. Department of Commerce, April 1995.
[39] C. Plaxton, R. Rajaraman, and A. Richa, “Accessing Nearby Copies of Replicated Objects in A Distributed Environment”, in Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, 1997.
[40] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, S. Gummadi, H. Weatherspoon, W. Weimer, C. Wells and B. Zhao, “Oceanstore: An Architecture for Global-Scale Persistent Storage”, in Proceedings of the ACM ASPLOS, 2000.
[41] S. Hand and T. Roscoe, “Mnemosyne: Peer-to-Peer Steganographic Storage”, in Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS’02), MIT Faculty Club, Cambridge, MA, 2002.
[42] Y. Chen, R. Katz and J. Kubiatowicz, “Scan: A Dynamic, Scalable and Efficient Content Distribution Network, in Proceedings of the International Conference on Pervasive Computing, 2000.
[43] Y. Rekhter and T. Li, “An architecture for IP address allocation with CIDR”, http://www.isi.edu/in-notes/rfc1518.txt, 1993
[44] A. Rowstron and P. Druschel, “Storage Management and Caching in PAST, A Large-Scale, Persistent Peer-to-Peer Storage Utility”, in Proceedings of the ACM Symposium on Operating Systems Principles, October 2001.
[45] P. Mockapetris, “Domain Names—Concepts and Facilities”, Internet Request for Comments (RFC 1034), February 1987.

[46] P. Mockapetris, “Domain Names—Implementation and Specification”, Internet Request for Comments (RFC 1035), February 1987.
[47] A. Kumar, J. Postel, C. Neuman, P, Danzig, and S. Miller, “Common DNS implementation error and suggested fixes”, Internet Request for Comments (RFC 1536), October 1993.