跳到主要內容

臺灣博碩士論文加值系統

(44.213.60.33) 您好!臺灣時間:2024/07/22 17:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林章汶
研究生(外文):Zhang-Wen Lin
論文名稱:Envoy:利用自我組織機制的混合式點對點網路系統
論文名稱(外文):Envoy: A Self-Organized Hybrid Peer-to-Peer System
指導教授:莊裕澤莊裕澤引用關係
指導教授(外文):Yuh-Jzer Joung
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:52
中文關鍵詞:點對點網路系統自我組織機制混合式系統
外文關鍵詞:Peer-to-PeerSelf-OrganizedHybrid System
相關次數:
  • 被引用被引用:0
  • 點閱點閱:227
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
近年來點對點網路系統已然在網際網路上廣為使用,也影響我們分享資訊與收集資源的方法。而基本上我們可以將現存的點對點網路系統分成四大類—非結構式、結構式、半集中式以及混合式。前三種點對點網路系統都存在其優點與缺點,因此混合式點對點網路系統透過結合不同種類的點對點網路以達到截長補短的功用。特別是結合非結構式與結構式的混合式點對點網路系統,能夠兼有兩者的彈性、穩固性、搜尋效率和較低的維護成本並且避免兩者的缺點。然而現有的混合式系統仍需要一些集中化的機制或者是事先選出一些網路結點來架構結構式的點對點網路。

因此為了解決以上的問題本研究提出了Envoy,Envoy可以緊密地結合非結構式與結構式點對點網路成為一個泛用的網路平臺,更重要的是Envoy是全分散式的並不需要任何集中化的機制。為了強化結構式點對點網路的穩固性,只有穩定且高頻寬的網路結點(稱作超結點)才有資格成為結構式點對點網路的一部份。超結點從非結構式點對點網路層中自動互選出來,並且將自我組成構結構式點對點網路層。Envoy的自我組成機制確保足夠以及合適的超結點被鄰選出來。在最後我們將透過數學分析以及模擬實驗來證明Envoy的延展性和低維護成本。
In recent years, P2P (Peer-to-Peer) systems have drastically changed the way we share resources and gather information. Existing P2P systems can be roughly classified into four families-decentralized unstructured, decentralized structured systems, partial-centralized, and hybrid systems. The first three families have their own strengths and weaknesses. Therefore, hybrid systems tends to simultaneously adopt various approaches in other families to complement drawbacks of others. Some hybrid systems tend to concord features of unstructured and structured ones, such as flexibility, robustness, low maintenance and efficiency. However, existing hybrid systems adopt centralized mechanisms or pre-select powerful peers.

In this paper we proposed Envoy, which organizes unstructured and structured P2P networks into a general-purpose hybrid P2P network without any kinds of centralized mechanism. To reinforce the structured overlay, only peers that meet several measures such as stability and bandwidth are eligible for serving on the overlay. Super-peers are automatically elected from the unstructured overlay and self-organized into the DHT overlay. Our self-organization mechanism ensures that elected peers are sufficient in number, stable and powerful enough. Through analysis and simulations, we prove that Envoy is scalable and low overhead even in the worst case.
1 Introduction - 1
2 Related Work - 4
2.1 Decentralized Unstructured P2P Systems - 4
2.1.1 Gnutella - 4
2.1.2 Freenet - 4
2.1.3 Brief Summary - 5
2.2 Decentralized Structured P2P Systems - 5
2.2.1 Chord - 5
2.2.2 Tapestry - 7
2.2.3 CAN - 8
2.2.4 Viceroy - 9
2.2.5 Hypercube - 9
2.2.6 Kademlia - 11
2.2.7 Brief Summary - 11
2.3 Partial Centralized P2P Systems - 11
2.4 Super-Peer-Based P2P Systems - 12
2.5 Hierarchical P2P systems - 13
2.6 Summary - 14
3 System Design 15
3.1 Overview - 15
3.2 Algorithm - 17
3.2.1 Peer Join - 17
3.2.2 Recommendation and Faction Discovery - 18
3.2.3 Update and Maintenance Within Factions - 19
3.2.4 Group Discovery - 20
3.2.5 Update within Alliances - 22
3.3 Peer Measurement - 24
3.4 Utilization - 26
3.5 Qualification of Super peers - 28
4 Simulation Results - 31
4.1 Simulation Methodology - 31
4.2 Quality of Super Peers - 32
4.3 Number of Unions Ever Created - 33
4.4 Size of Unions Ever Created - 36
4.5 Number of Joining Times - 39
4.6 Number of Discovery Times - 42
4.7 Coverage Rate of Super Peers - 46
5 Conclusion and Future Work - 48
Bibliography - 49
[1] MSN Messenger Version 7.0. http://messenger.msn.com/.
[2] Karl Aberer. P-Grid: A self-organizing access structure for P2P information systems. In
Proceedings of the Nineth International Conference on Cooperative Information Systems
(CoopIS 2001), volume 2172, pages 179-194, 2001.
[3] Artur Andrzejak and Zhichen Xu. Scalable, efficient range queries for grid information
services. In Proceedings of Second International Conference on Peer-to-Peer Computing
(P2P 2002), pages 33-40. IEEE Computer Scociety, September 2002.
[4] Baruch Awerbuch and Christian Scheideler. Peer-to-peer systems for prefix search. In Proceedings
of the Twenty-Second Annual Symposium on Principles of Distributed Computing
(PODC 2003), pages 123-132. ACM Press, July 2003.
[5] Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, Nick Lanham, and Scott Shenker. Making
gnutella-like P2P systems scalable. In Proceedings of the 2003 conference on Applications,
technologies, architectures, and protocols for computer communications, pages 407-418.
ACM Press, 2003.
[6] An-Hsun Cheng and Yuh-Jzer Joung. Probabilistic file indexing and searching. In Proceedings
of the Second Fourth IEEE/ACM International Symposium on Cluster Computing
and the Grid (CCGRID 2004), April 2004.
[7] Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Widearea
cooperative storage with cfs. In Proceedings of the eighteenth ACM symposium on
Operating systems principles, pages 202-215. ACM Press, 2001.
[8] KaZaA Media Desktop. http://www.kazaa.com.
[9] Freenet. http://freenet.sourceforge.com.
[10] Prasanna Ganesan, Qixiang Sun, and Hector Garcia-Molina. Yappers: A peer-to-peer
lookup service over arbitrary topology. In Proceedings of Twenty-Second Annual Joint
Conference of the IEEE Computer and Communications Societies (INFOCOM 2003),
March/April 2003.
[11] Luis Garces-Erice, Ernst W. Biersack, Keith W. Ross, Pascal A. Felber, and Guillaume
Urvoy-Keller. Hierarchical P2P systems. In Proceedings of ACM/IFIP International Conference
on Parallel and Distributed Computing (Euro-Par), Klagenfurt, Austria, 2003.
[12] Gnutella. http://www.gnutella.com.
[13] Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal hash table.
In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS--03),
February 2003.
[14] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel
Lewin. 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, pages 654-663. ACM Press, 1997.
[15] John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis
Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris
Wells, , and Ben 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 (ASPLOS 2000), pages 190-201. ACM Press,
2000.
[16] Xiaozhou Li and C. Greg Plaxton. On name resolution in peer-to-peer networks. In
Proceedings of the second ACM international workshop on Principles of mobile computing,
pages 82-89. ACM Press, 2002.
[17] David Liben-Nowell, Hari Balakrishnan, and David Karger. Analysis of the evolution of
peer-to-peer systems. In Proceedings of the Twenty-First Annual Symposium on Principles
of Distributed Computing, pages 233-242. ACM Press, 2002.
[18] Huaiyu Liu and Simon S. Lam. Neighbor table construction and update in a dynamic peerto-
peer network. In Proceedings of 23rd International Conference on Distributed Computing
Systems, pages 509-518, May 2002.
[19] Boon Thau Loo, Ryan Huebsch, Ion Stoica, and Joseph M. Hellerstein. The case for a
hybrid p2p search infrastructure. In Proceedings of the 3nd International Workshop on
Peer-to-Peer Systems (IPTPS--04), February 2004.
[20] Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker. Search and replication in
unstructured peer-to-peer networks. In ICS --02: Proceedings of the 16th international
conference on Supercomputing, pages 84-95. ACM Press, 2002.
[21] Dahlia Malkhi, Moni Naor, and David Ratajczak. Viceroy: A scalable and dynamic emulation
of the butterfly. In Proceedings of the twenty-first annual symposium on Principles
of distributed computing, pages 183-192. ACM Press, 2002.
[22] Petar Maymounkov and David Mazi`eres. Kademlia: A peer-to-peer information system
based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-
Peer Systems (IPTPS--02), March 2002.
[23] Yahoo! Messenger. http://messenger.yahoo.com/.
[24] Napster. http://www.napster.com.
[25] Overnet. http://www.edonkey2000.com/.
[26] C. Greg Plaxton, Rajmohan Rajaraman, and Andr--ea W. Richa. Accessing nearby copies
of replicated objects in a distributed environment. In Proceedings of the ninth annual
ACM symposium on Parallel algorithms and architectures, pages 311-320. ACM Press,
June 1997.
[27] JXTA Project. http://wwws.sun.com/software/jxta/.
[28] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Schenker. A scalable
content-addressable network. In Proceedings of the 2001 conference on applications,
technologies, architectures, and protocols for computer communications, pages 161-172.
ACM Pres, August 2001.
[29] Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-aware
overlay construction and server sselection. In Proceedings of IEEE INFOCOM--02, June
2002.
[30] Patrick Reynolds and Amin Vahdat. Efficient peer-to-peer keyword searching. In Proceedings
of the 2003 ACM/IFIP/USENIX International Middleware Conference (Middleware
2003), volume 2672, pages 21-40, 2003.
[31] Antony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and
routing for large-scale peer-to-peer systems. In Proceeding of IFIP/ACM International
Conference on Distributed Systems Platforms (Middleware), pages 329-350, November
2001.
[32] Mario Schlosser, Michael Sintek, Stefan Decker, and Wolfgang Nejdl. HyperCuP : Hypercubes,
ontologies and efficient search on P2P networks. In Proceedings of International
Conference on Autonomous Agents and MultiAgent Systems(AAMAS--02), July 2002.
[33] Emil Sit and Robert Morris. Security considerations for peer-to-peer distributed hash
tables. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems
(IPTPS--02), March 2002.
[34] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan.
Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of
the 2001 conference on applications, technologies, architectures, and protocols for computer
communications, pages 149-160. ACM Press, Auguest 2001.
[35] Chunqiang Tang, Zhichen Xu, and Sandhya Dwarkadas. Peer-to-peer information retrieval
using self-organizing semantic overlay networks. In Proceedings of the 2003 conference
on Applications, technologies, architectures, and protocols for computer communications,
pages 175-186. ACM Press, 2003.
[36] Skype Free Internet telephony that just works. http://www.skype.com/.
[37] Zhiyong Xu, Rui Min, and Yiming Hu. HIERAS: a DHT based hierarchical P2P routing
algorithm. In Proceedings of the 2003 International Conference on Parallel Processing(
ICPP--03), pages 187-, October 2003.
[38] Beverly Yang and Hector Garcia-Molina. Comparing hybrid peer-to-peer systems. In Proceedings
of the 21st International Conference on Very Large Databases(VLDB--01), pages
561-570, September 2001.
[39] Beverly Yang and Hector Garcia-Molina. Improving search in peer-to-peer systems. In Proceedings
of the 22nd International Conference on Distributed Computing Systems (ICDCS),
July 2002.
[40] Beverly Yang and Hector Garcia-Molina. Designing a super-peer network. In Proceedings
of the 19th International Conference on Data Engineering (ICDE), March 2003.
[41] Hui Zhang, Ashish Goel, and Ramesh Govindan. Incrementally improving lookup latency
in distributed hash table systems. In Proceedings of the 2003 ACM SIGMETRICS international
conference on Measurement and modeling of computer systems, pages 114-125.
ACM Press, 2003.
[42] Ben Y. Zhao, Yitao Duan, Ling Huang, Anthony D. Joseph, and John D. Kubiatowicz.
Brocade: Landmark routing on vverlay networks. In Proceedings of the 1st International
Workshop on Peer-to-Peer Systems (IPTPS--02), pages 34-44, March 2002.
[43] Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph. Tapestry: An infrastructure for
fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC
Berkeley, April 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文