請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38155
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 莊裕澤(Yuh-Jzer Joung) | |
dc.contributor.author | Yi-Fang Chou | en |
dc.contributor.author | 周亦方 | zh_TW |
dc.date.accessioned | 2021-06-13T16:27:09Z | - |
dc.date.available | 2005-07-19 | |
dc.date.copyright | 2005-07-19 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-14 | |
dc.identifier.citation | Bibliography
[1] James Aspnes, Jonathan Kirsch, and Arvind Krishnamurthy. Load balancing and locality in range-queriable data structures. In Proceedings of the twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC 2004), pages 115~124. ACM Press, July 2004. [2] James Aspnes and Gauri Shah. Skip graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pages 384~393. Society for Industrial and Applied Mathematics, January 2003. [3] 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. [4] Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury: Supporting scalable multi-attribute range queries. In Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2004), pages 353~366. ACM Press, August 2004. [5] Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron. Exploiting network proximity in distributed hash tables. In Proceedings of the 2002 International Workshop on Future Directions in Distributed Computing (FuDiCo 2002), June 2002. [6] Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Technical Report MSR/TR-2002-82, Microsoft Research, May 2002. [7] Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. Technical Report MSR/TR-2003-52, Microsoft Research, June 2003. [8] Prasanna Ganesan, Mayank Bawa, and Hector Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the Thirtieth Conference on Very Large Databases (VLDB 2004), August 2004. [9] Prasanna Ganesan, Qixiang Sun, and Hector Garcia-Molina. Apocrypha: Making p2p overlays network-aware. Technical report, Stanford University, November 2003. [10] Krishna Gummadi, Ramakrishna Gummadi, Sylvia Ratnasamy, Steve Gribble, Scott Shenker, and Ion Stoica. The impact of dht routing geometry on resilience and proximity. In Proceedings of ACM conference on Special Interest Group on Data Communications (SIGCOMM), Aug 2003. [11] Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman. SkipNet: A scalable overlay network with practical locality properties. In Proceedings of the Fourth USENIX Symposium on Internet Technologies and Systems (USITS 2002), March 2003. [12] Yuh-Jzer Joung and Chih-Ho Kang. Approaching proximate prefix search and load balancing in p2p networks. Technical report, National Taiwan University, March 2004. [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 (STOC 1997), pages 654~663. ACM Press, May 1997. [15] David R. Karger and Matthias Ruhl. Simple e±cient load balancing algorithms for peer-to-peer systems. In Proceedings of the sixteenth annual ACM symposium on Parallel algorithms and architectures, June 2004. [16] 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. [17] 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), pages 53~65, March 2002. [18] Freenet Home Page. http://freenet.sourceforge.com. [19] Gnutella.com Home Page. http://www.gnutella.com. [20] Napster.com Home Page. http://www.napster.com. [21] C. Greg Plaxton, Rajmohan Rajaraman, and Andrea 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 (SPAA 1997), pages 311~320.ACM Press, June 1997. [22] William Pugh. Skip lists: A probabilistic alternative to balanced trees. In Proceedings of the First Workshop on Algorithms and Data Structures (WADS 1989), volume 382, pages 437~449, 1989. [23] 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. [24] Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-aware overlay construction and server selection. In Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), volume 3, pages 1190~1199, June 2002. [25] Sylvia Ratnasamy, Joseph M. Hellerstein, and Scott Shenker. Range queries over dhts. Technical Report IRB/TR-03-009, Intel Research Berkeley, June 2003. [26] 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. [27] 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. [28] Marcel Waldvogel and Roberto Rinaldi. E±cient topology-aware overlay network. In Proceedings of HotNets-I, October 2002. [29] Zhichen Xu and Zheng Zhang. Building low-maintenance expressways for p2p systems. Technical Report HPL-2002-41, Hewlett-Packard Laboratories Palo Alto, March 2002. [30] 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 (SIGMETRICS 2003), pages 114~125. ACM Press, June 2003. [31] 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, University of California, Berkeley, April 2001. [32] Shuheng Zhou, Gregory R. Ganger, and Peter Steenkiste. Location-based node ids: Enabling explicit locality in dhts. Technical Report CMU/CS-03-171, Carnegie Mellon University, September 2003. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38155 | - |
dc.description.abstract | DHT(Distributed Hash Table) 是非常受歡迎的P2P結構,它提供了有效率的繞送(routing)和保證有結果的搜尋。然而,它有兩個主要的缺點:上層邏輯網路和下層實體網路的不一致性,以及混亂編碼(hashing)導致珍貴的資訊遺失。前者使得在上層邏輯網路的繞送變得成本高昂,後者則限制了DHT支援複雜搜尋方法的能力。因此,儘管DHT保證了在邏輯網路上有效率的關鍵字搜尋,真正在實體網路上所發生的成本可能很高。此外,簡單的關鍵字搜尋無法滿足各式各樣搜尋的需求。
在這篇論文中,我們提出了Donuts。這個系統利用了鄰近性,且負載平衡,並同時可以支援範圍查詢。我們建立了考慮鄰近性的繞送表格來減少繞送成本,並且使點(Peer)加入系統時考慮鄰近性來建立和實體網路類似的邏輯網路。為了要保存資訊以支援範圍查詢,Donuts使用一個機率性的架構來代替DHT。另外,我們介紹了“Group”的概念來將實體網路中靠近的點群聚在數個邏輯網路的區域。這個概念不但解決了鄰近性、負載平衡和範圍查詢間的衝突,同時更明顯的利用緩衝儲存(cache)增進了搜尋的效率。透過模擬實驗,我們證明了Donuts是一個成功結合鄰近性,負載平衡以及範圍查詢的系統,它也具備了能容錯和能支援大量使用者等P2P網路的特性。 | zh_TW |
dc.description.abstract | Distributed Hash Table (DHT) is a popular P2P structure because of efficient routing and guaranteed search. However, it has two main drawbacks: incongruence between overlay and IP-network, and the lost of information due to hashing. The first makes overlay routing become expensive due to high routing stretch while the second restricts DHTs to support complex query. Therefore, even though DHT guarantees efficient keyword search in overlay, the actual cost might still be high and the limited keyword search is not enough to fulfill different needs.
In this paper, we propose Donuts, which exploits proximity, achieves load balance, and supports range query. We build proximity routing table to reduce routing stretch, and adopt proximity join to exploit overlay proximity. A probabilistic structure is used instead of DHT so Donuts is able to support range query. Moreover, we introduce the 'Group' concept which clusters physically nearby nodes into several overlay sections. It not only solves the conflict among proximity, load balance, and range query, but also improves search efficiency by cache. Through simulations, we prove that Donuts is a scalable and fault-tolerant system which successfully achieves proximity, load balance, and range query simultaneously. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T16:27:09Z (GMT). No. of bitstreams: 1 ntu-94-R92725016-1.pdf: 974749 bytes, checksum: 59731981f0878fc35932825e23604447 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Background 1 1.2 Motivation 3 1.3 Research Objectives 4 2 Related Work 5 2.1 Structured Peer-to-Peer Overlay 5 2.1.1 Hash Function Based Overlay 5 2.1.2 Non Hash Function Based Overlay 9 2.1.3 Brief Summary 12 2.2 Proximity Approach 14 2.2.1 Proximity Join 14 2.2.2 Proximity Routing Table Construction 16 2.2.3 Proximity Routing 17 2.2.4 Adaptive Proximity 17 2.2.5 Brief Summary 18 2.3 Hybrid Systems 19 2.3.1 Network-aware and Load-balanced System 19 2.3.2 Load-balanced System for Range Query 19 2.3.3 Network-aware System for Range Query 20 2.3.4 Network-aware and Load-balanced System for Range Query 20 2.4 Summary 21 3 System Model 22 3.1 Query Model 22 3.2 Basic Donuts Structure 22 3.2.1 Approaching Proximity 24 3.2.2 Load Balance 25 3.3 Enhancement 25 3.3.1 The Affinity of Proximity Table 27 3.3.2 Link Pattern and Cache 27 3.3.3 Fault-tolerance 29 3.4 Donuts 29 3.4.1 The Features of Donuts 29 3.4.2 System Algorithm 29 4 Experimental Results 38 4.1 Simulation Methodology 38 4.2 Proximity Join Performance 39 4.2.1 Locating a physically nearby node 39 4.2.2 Deciding the overlay position 42 4.2.3 Overlay Proximity 43 4.3 Proximity and Group 44 4.3.1 The Impact of Group on Overlay Proximity 44 4.3.2 The Impact of Group on Proximity Table 45 4.4 Load Balance 48 4.5 Cache, Group, and Search Performance 50 5 Conclusion and Future Work 58 5.1 Conclusion 58 5.2 Future Work 59 Bibliography 60 | |
dc.language.iso | en | |
dc.title | Donuts:考慮地域鄰近性且負載平衡的點對點範圍查詢系統 | zh_TW |
dc.title | Donuts: A Network-Aware and Load-Balanced
System for Range Query | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 劉邦鋒(Pang-Feng Liu),林宗男(Tsung-Nan Lin) | |
dc.subject.keyword | 點對點網路,鄰近性,負載平衡,範圍查詢, | zh_TW |
dc.subject.keyword | Peer-to-Peer,Proximity,Load Balance,Range Query, | en |
dc.relation.page | 62 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-15 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 951.9 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。