臺灣博碩士論文加值系統

　　隨著網路頻寬和計算機速度的快速成長，計算設備之間的聯繫變得快速而容易。點對點計算的發展正成為無所不在運算的啟動技術之一。近年來在點對點計算領域中，資源搜尋機制的研究趨勢可分為三大類，集中式控制、分散式控制、分散式雜湊表控制，各有各的優缺點。在學術研究上越來越多的學者針對分散式雜湊表控制類型進行研究。分散式雜湊表控制類型中，每個點都必須紀錄一些拓墣的資訊，行動運算裝置；如手持式設備，筆記型電腦，隨著無線網路的進步而越來越普及，這些行動裝置的特性迥異於傳統的固定式設備，網路的連結可能經常的變動，導致這些裝置會在短期間內多次加入或離開點對點網路，造成整個拓墣的不穩定，對於分散式雜湊表控制類型的機制來說，解決這樣的問題是首要任務，本文修改Chord 協定，提出一個基於分散式並且以群組群環狀(Group-Ring)拓樸為基礎，適用於行動與無線網路環境的網路資源搜尋協定、稱之Crown。Crown將Chord原本的環狀拓墣擴充為群組群環狀(Group-Ring)拓樸，並在協定內設計複本與回復機制加強整個拓墣的穩定與資源的可用性(availability)及可靠性(reliability)。透過群組群環(Group-Ring)的觀念，使的整個拓墣更加穩定，並可以降低個別資源頻繁的加入與離開網路時的負擔。

With increasing network bandwidth and computer speed, communications between computing devices become easy and fast. P2P computing is emerging as one of the Ubiquitous computing enabling technologies. People can share their computer resources via a P2P network. In recent years, the trends in developing resource discovery mechanisms of P2P systems could be classified into three categories- the centralized controlled, the decentralized controlled and the distributed hash-table-based controlled respectively, each with superiority as well as drawbacks. Recently, more and more researches are focusing on distributed hash-table-based controlled mechanism. In this mechanism, each peer must maintain some topologic information. As mobile devices, such as PDA, notebook etc, becoming popular with the perfection of wireless network technology, many people may begin to have the demand on using such devices in a P2P system. However, the characteristic of mobile devices are quite different from those of the traditional stationary devices; their connection status may change frequently. That is, these devices may join to or leave from a P2P network at short intervals. As these mobile peers move frequently, the overall topology will become unstable. To use the distributed hash–table -based controlled mechanism in a P2P system containing wireless sub-network, the unstable topology problem must be solved first. This paper modifies the Chord protocol and results in a new resource lookup protocol, the Crown protocol, which is suitable for mobile and wireless network environment. In Chord, all peers are connected to form a single ring topology, while Crown protocol adds concept of group and expands the ring to a group-ring. Besides, Crown adds a replica mechanism and a fault-recovery mechanism to strengthen the group-ring topology, and enhances the availability and reliability of resources. The group-ring concept makes the whole topology more stable when peers join or leave frequently.

Contents

Abstract in Chinese I
Abstract in English II
Acknowledgements III
Contents IV
List of Figures VI
List of Tables VIII
Chapter 1 Introduction 1
1.1. Research Background and Motivation 1
1.2. Research Goals 3
1.3. Research Contributions 3
1.4. Chapters Outline 4
Chapter 2 Related Works 5
2.1. Centralized controlled 5
2.2. Decentralized controlled 7
2.3. Distributed hash-table-based controlled 8
CAN (Content-Addressable Networks) 9
Chord 11
Chapter 3 System Model 16
3.1. The Crown Topology 16
3.2. Group ID and Peer ID 18
3.3. Super Peer Election Mechanism (SPEM) 19
3.4. Resource Distribution Mechanism 20
3.5. Resource Lookup 21
3.6. How a Node Joins to Crown 24
3.7. How a Node Leaves from Crown 27
3.8. Crown Protocol Message Data Structure 28
3.9. Crown Protocol Resource Description and Resource Keys 31
3.10. Crown Protocol keyList Data Structures 33
3.11. Crown Protocol spList Data Structures 34
Chapter 4 Recovery in Crown 35
4.1. Recovery in a Group 35
4.2. Recovery among Groups 38
Chapter 5 Performance Evaluation and Comparison 39
5.1. Formula deduction 39
5.2. Simulation 41
5.2.1. POEMS ( P2P Overlay Event-driven fraMework Simulator) 41
5.2.3. Topologic Model Setting 46
5.2.4. Join/Leave Cost Comparison 47
5.2.5. Search Cost Comparison 50
Chapter 6 Conclusion and Further Work 52
6.1. Conclusion 52
6.2. Contributions 52
6.3. Further Work 53
Reference 54

[1]I. Foster, C. Kesselman, J. Nick, S. Tuecke , “The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration”. Open Grid Service Infrastructure WG, Global Grid Forum, June 22, 2002.
[2]http://www.w3.org/2002/ws/
[3]UDDI Version 3 Specification http://uddi.org/pubs/uddi-v3.00-published-20020719.htm
[4]Germn Goldszmidt, Yechiam Yemini. “Evaluating Management Decisions via Delegation”. IFIP International Symposium on Network Management, April 1993.
[5]M. Ripeanu, I. Foster , “A Decentralized, Adaptive, Replica Location Service”. 11th IEEE International Symposium on High Performance Distributed Computing (HPDC-11) Edinburgh, Scotland, July 24-16, 2002.
[6]D. R. Karger, E. Lehman, F. Leighton, M. Levine, D. Lewin, and R. Panigrahy, “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on theWorldWideWeb,” in Proc. 29th Annu. ACM Symp. Theory of Computing, El Paso, TX, May 1997, pp. 654–663.
[7]Napster. http://www.napster.com/
[8]RFC 3174 US Secure Hash Algorithm 1 (SHA1)
[9]The Gnutella Protocol Specification v0.4 Revision 1.2.
[10]Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D.R.; Kaashoek, M.F.; Dabek, F.; Balakrishnan,H . “Chord: a scalable peer-to-peer lookup protocol for Internet applications“, Networking, IEEE/ACM Transactions on , Volume: 11 Issue: 1 , Feb. 2003 Page(s): 17 -32.
[11]Dabek, F. Brunskill, E. Kaashoek, M.F. Karger, D. Morris, R. Stoica, I. Balakrishnan, H. Lab. for Comput. Sci., MIT, USA , “Building peer-to-peer systems with chord, a distributed lookup service”,This paper appears in Hot Topics in Operating Systems, 2001. Proceedings of the Eighth Workshop on Publication Date: 20-22 May 2001 On page(s): 81 – 86.
[12]Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker,”A Scalable Content-Addressable Network”, Proceedings of ACM SIGCOMM 2001
[13]A. Rowstron and P. Druschel, "Pastry: Scalable, distributed object location and routing for largescale peer-to-peer systems," in Proc. 18th IFIP/ACM Int'l. Conf. Distributed Systems Platforms (Middleware), 2001.
[14]B. Y. Zhao, J. Kubiatowicz, and A. Joseph, "Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing". Tech. Rep. UCB/CSD-01-1141, University of California at Berkeley, 2001.
[15]C. Greg Plaxton, Rajmohan Rajaraman, and Andrea W. Richa. “Accessing nearby copies of replicated objects in a distributed environment”. In Proceedings of ACM SPAA. ACM, June 1997.
[16]Kavitha Ranganathan, Adriana Iamnitchi, and Ian Foster,” Improving Data Availability through Dynamic Model-Driven Replication in Large Peer-to-Peer Communities”, Global and Peer-to-Peer Computing on Large Scale Distributed Systems Workshop, Berlin, Germany, May 2002.
[17]A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In Proceedings of MASCOTS 2001, Cincinnati, OH, August 2001.
[18]H. Tangmunarunkit, R. Govindan, S. Jamin, and S. S. W. Willinger. "Network Topology Generators: Degree-Based vs. Structural". Technical report, Computer Science Department, University of Southern California, 2002. Technical Report 02-760.
[19]Oliver Heckmann, Michael Piringer, Jens Schmitt, and Ralf Steinmetz. "How to use Topology Generators to create realistic Topologies". Technical Report TR-KOM-2002-07, Multimedia Communications (KOM), Darmstadt University of Technology, December 2002.
[20]Menasce, D.A.; “Scalable P2P search”, Internet Computing, IEEE , Volume: 7 , Issue: 2 , March-April 2003 , Pages:83 – 87
[21]Kikuma, K.; Morita, Y.; Sunaga, H.; Tamura, H.; Hidaka, T.; Mizuno, M.;”A study of a P2P community on a P2P communication platform”, Communication Technology Proceedings, 2003. ICCT 2003. International Conference on , Volume: 1 , 9-11 April 2003, Pages:153 - 156 vol.1
[22]Talia, D.; Trunflo, P., “Toward a synergy between P2P and grids”, Internet Computing, IEEE , Volume: 7 , Issue: 4 , July-Aug. 2003 , Pages:96, 94 – 95
[23]Zupeng Li; Daoying Huang; Zinrang Liu; Jianhua Huang; “Research of peer-to-peer network architecture”, Communication Technology Proceedings, 2003. ICCT 2003. International Conference on , Volume: 1 , 9-11 April 2003, Pages:312 - 315 vol.1.
[24]Parameswaran, M.; Susarla, A.; Whinston, A.B.; “P2P networking: an information sharing alternative” Computer , Volume: 34 , Issue: 7 , July 2001 , Pages:31 – 38
[25]Tsungnan Lin; Hsinping Wang; , ”Search performance analysis in peer-to-peer networks”, Peer-to-Peer Computing, 2003. (P2P 2003). Proceedings. Third International Conference on , 1-3 Sept. 2003. Pages:204 – 205.
[26]Chia-Feng Li, Chia-Jen Cheng, Chi-Jen Wu, De-Kai Liu, Ren-Hung Hwang, "Location-Aware Peer-to-Peer Information Sharing System in Mobile Ad Hoc Network," Active Networking Workshop (ANW 2003), Taiwan, September, 2003.
[27]Yunhao Liu, Xiaomei Liu, Li Xiao, Lionel Ni, Xiaodong Zhang, "Location-Aware Topology Matching in P2P Systems," IEEE INFOCOM 2004, Hong Kong, China, March, 2004.
[28]H.C. Hsiao and C.T. King, ``Similarity Discovery in Structured P2P Overlays,' Int'l Conf. on Parallel Processing (ICPP 2003), Oct. 2003.
[29]H. T. Kung and Chun-Hsin Wu, "Differentiated Admission for Peer-to-Peer Systems: Incentivize Peers to Contribute Their Resources," presented at the Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, June 2003.