請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/28688
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 莊裕澤(Yuh-Jzer Joung) | |
dc.contributor.author | Wing-Tat Wong | en |
dc.contributor.author | 黃榮達 | zh_TW |
dc.date.accessioned | 2021-06-13T00:17:32Z | - |
dc.date.available | 2007-07-30 | |
dc.date.copyright | 2007-07-30 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2007-07-27 | |
dc.identifier.citation | [1] I. Antony, T. Rowstron, and P. Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), 2001.
[2] J. Aspnes, J. Kirsch, and A. Krishnamurthy. Load balancing and locality in range-queriable data structures. In Proceedings of the 23th Symposium on Principles of Distributed Computing (PODC 2004), 2004. [3] J. Aspnes and G. Shah. Skip graphs. In Proceedings of Symposium on Discrete Algorithms, 2003. [4] R. Bhagwan, K. Tati, Y. C. Cheng, S. Savage, and G. M. Voelker. Total Recall: System support for automated availability management. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI 2004), 2004. [5] P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (ITS'97), 1997. [6] M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. Technical Report MSR-TR-2003-52, Microsoft Research, September 2003. [7] M. Castro, P. Druschel, Y.C. Hu, and A. Rowstron. Exploiting network proximity in distributed hash tables. In Proceedings of the International Workshop on Future Directions in Distributed Computing (FuDiCo 2002), 2002. [8] J. C. Chu, K. S. Labonte, and B. N. Levine. Availability and locality measurements of peer-to-peer file systems. In Proceedings of SPIE (SPIE 2002), volume 4868, page 310. SPIE, 2002. [9] B. G. Chun, F. Dabek, A. Haeberlen, E. Sit, H. Weatherspoon, H. F. Kaashoek, J. Kubiatowicz, and R. Morris. Effcient replica maintenance for distributed storage systems. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI'06), 2006. [10] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the International Workshop on Design Issues in Anonymity and Unobservability (DIAU 2000), pages 311{320, 2000. [11] 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, 2001. [12] F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for low latency and high throughput. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI'04), 2004. [13] C. Damgaard and J. Weiner. Describing inequality in plant size or fecundity. Ecology, 81(4):1139{1142, 2000. [14] B. M. Duska, D. Marwood, and M. J. Feeley. The measured access characteristics of World-Wide-Web client proxy caches. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (ITS'97), 1997. [15] L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary Cache: A scalable wide-area Web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3):281{293, 2000. [16] P. Ganesan, M. Bawa, and H. Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Mario A. Nascimento, M. Tamer Ozsu, Donald Kossmann, Renee J. Miller, Jose A. Blakeley, and K. Bernhard Schiefer, editors, Proceedings of Conference on Very Large Data Bases (VLDB'04), pages 444{455. Morgan Kaufmann, 2004. [17] P. K. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of DHT routing geometry on resilience and proximity. In Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2003), 2003. [18] A. Haeberlen, A. Mislove, and P. Druschel. Glacier: Highly durable, decentralized storage despite massive correlated failures. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), 2005. [19] N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. SkipNet: A scalable overlay network with practical locality properties. In Proceedings of the Fourth USENIX Symposium on Internet Technologies and Systems, 2003. [20] S. Iyer, A. I. T. Rowstron, and P. Druschel. Squirrel: A decentralized peer-to-peer web cache. In Proceedings of the 21th Symposium on Principles of Distributed Computing (PODC 2002), pages 213{222, 2002. [21] M. Kacimi and K. Yetongnon. Evaluation study of a distributed caching based on query similarity in a P2P network. In Proceedings of The 2nd International Conference on Scalable Information Systems (INFOSCALE 2007), 2007. [22] D. Karger, E. Lehman, F. L. 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 29th ACM Symposium on Theory of Computing, 1997. [23] D. R. Karger and M. Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In Phillip B. Gibbons and Micah Adler, editors, Proceedings of Symposium on Parallelism in Algorithms and Architectures, pages 36{43. ACM, 2004. [24] J. Kubiatowicz, D. Bindel, Y. Chen, S. E. Czerwinski, P. R. Eaton, D. Geels, R. Gummadi, S. C. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Y. Zhao. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, 2000. [25] P. Linga, I. Gupta, and K. Birman. A churn-resistant peer-to-peer web caching system. In Proceedings of the Workshop on Survivable and Self-Regenerative Systems, 2003. [26] E. P. Markatos. Tracing a large-scale peer to peer system: An hour in the life of gnutella. In Proceedings of the 2nd IEEE/ACM International Symposium Cluster Computing and the GRID (CCGRID 2002), pages 65{74. IEEE Computer Society, 2002. [27] A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An approach to universal topology generation. In Proceedings of the 9th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS 2001), 2001. [28] S. Patro and Y. C. Hu. Transparent query caching in peer-to-peer overlay networks. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPD 2003), 2003. [29] C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241{280, 1999. [30] W. Pugh. Skip Lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33:668{676, 1990. [31] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2001). ACM Press, 2001. [32] S. C. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, and H. Yu. OpenDHT: A public DHT service and its uses. In Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2005), 2005. [33] M. Ripeanu. Peer-to-peer architecture case study: Gnutella Network. In Ross Lee Graham and Nahid Shahmehri, editors, Proceedings of the 1st International Conference on Peer-to-Peer Computing (P2P 2001), pages 99{100. IEEE Computer Society, 2001. [34] R. Rodrigues and C. Blake. When multi-hop peer-to-peer lookup matters. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS'04), 2004. [35] R. Rodrigues and B. Liskov. High availability in DHTs: Erasure coding vs. replication. In Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS 20005), 2005. [36] M. Roussopoulos and M. Baker. CUP: Controlled update propagation in peer-to-peer networks. In Proceedings of USENIX Annual Technical Conference, 2003. [37] A. I. T. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP 2001), 2001. [38] S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the 2002 Multimedia Computing and Networking (MMCN 2002), 2002. [39] E. Sit, A. Haeberlen, F. Dabek, B. G. Chun, H. Weatherspoon, F. Kaashoek, R. Morris, and J. Kubiatowicz. Proactive replication for data durability. In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS 2006), 2006. [40] K. Sripanidkulchai. The popularity of Gnutella queries and its implications on scalability, February 2001. Available in http://www.cs.cmu.edu/~kunwadee/research/p2p/gnutella.html. [41] I. Stoica, R. Morris, D. R. Karger, M. F. Kaashoek, and H. 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 (SIGCOMM 2001). ACM Press, 2001. [42] K. Tati and G. M. Voelker. On object maintenance in peer-to-peer systems. In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS 2006), 2006. [43] M. Waldvogel and R. Rinaldi. Efficient topology-aware overlay network. ACM SIGCOMM Computer Communication Review, 33(1):101{106, 2003. [44] C. Wang, L. Xiao, Y. Liu, and P. Zheng. Distributed caching and adaptive search in multilayer P2P networks. In Proceedings of the 24th International Conference on Distributed Computing Systems (IDCS 2004), 2004. [45] H. Weatherspoon and J. D. Kubiatowicz. Erasure coding vs. replications: A quantitative comparison. In Proceedings of the 1st International Workshop of Peer-to-Peer Systems (IPTPS 2002), 2002. [46] R. P. Wooster and M. Abrams. Proxy caching that estimates page load delays. Computer Networks, 29(8-13):977{986, 1997. [47] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical report, University of California, Berkeley, April 04 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/28688 | - |
dc.description.abstract | 在過去的幾年裡,點對點系統為大規模的分散式資訊系統形成一個強大的平台。在這種平台裡,搜尋系統裡的資源是十分重要的一種功能,並且已經有不少的研究提出方法來改善系統中搜尋的效能;然而,點對點平台並不是對於任何類型的查詢都能有效的支援,例如對於範圍查詢的支援仍然有限。要在點對點平台上有效的支援範圍查詢,首先我們必須解決影響效能的相關問題﹕系統內部的高通訊成本、點與點之間的負載不平衡以及維持系統裡物件的有效性。在過去的研究中雖然有針對單一問題提出不錯的解決方法;不過,因為這些問題之間存在著衝突性,所以尚未有一個系統可以同時有效地解決這些問題。在這篇論文裡,我們提出了一個可靠的點對點系統,它可以維持物件的有效性及有效地支援範圍查詢。我們的系統會考慮地域鄰近性及利用合作式的cache機制來處利高通訊成本的問題。同時,我們也會利用群組化的概念來解決地域鄰近性與負載平衡之間的衝突。在一個群組化的系統裡,每一個節點會被分派到不同的群組以提昇地域鄰近性的彈性,這樣可以增加實行負載平衡的可行性,因為物件會被均等地分配到不同的群組當中。
我們的實驗結果證明了我們的平台可以在一個高度不穏定的環境下維持正常的操作,而考慮地域鄰近性的機制也可以有系統化地降低通訊的成本;在另一方面,合作式的cache機制會經由降低系統裡搜尋的範圍以及貯藏物件的重複性來增加系統搜尋的效能。最後,我們所提出的負載平衡機制亦能夠以低成本在一個具有物件順序的限制情況下快速地平衡點與點之負載。 | zh_TW |
dc.description.abstract | Peer-to-peer (P2P) systems have emerged promptly as a powerful platform for large-scale distributed information systems in recent years; important functionalities, such as searching, have been added to improve the system's lookup capability. In particular, range query is exceptionally demanded when a user does not know exactly what he/she is looking for, however, the efficient support of range queries in a P2P system is still a challenging problem. To resolve
this problem, some other related issues must first be addressed, such as high communication overheads, load imbalance among peers and preservation of object availability. Several techniques have been proposed in each aspect, but it is difficult to incorporate all of them in a single range queries system due to the conflict among these techniques. In this thesis, we propose a fault-tolerable P2P system which guarantees object availability and supports range queries effectively. The system exploits proximity and cooperative caching to tackle the high communication overhead. By introducing the concept of grouping, the conflict between proximity and load balance can be resolved. Within a grouping environment, peers are divided into several groups to provide the flexibility of proximity and feasibility of load balance in a range queries system. Therefore, objects are evenly distributed among groups. Our results show that our platform is fault-tolerable in a highly dynamic environment. The impact of proximity is effective in reducing the communication overhead. Moreover, the cooperative cache scheme can improve search performance, decrease the query scope significantly and avoid redundancy. The load balance mechanism can quickly balance the load among peers under object ordering constraint environment with a low cost. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T00:17:32Z (GMT). No. of bitstreams: 1 ntu-96-R94725007-1.pdf: 2812427 bytes, checksum: 369c64c41cbaa4c57afcfbd2a7ce6bfe (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Research Objectives . . . . . . . . . . . . . . . . . 4 1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . 5 2 Related Work . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Peer-to-Peer Overlays. . . . . . . . . . . . . . . . . 6 2.1.1 CAN . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2 Chord . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Pastry . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.4 SkipGraph . . . . . . . . . . . . . . . . . . . . . 10 2.2 Techniques to Improve Search Performance . . . . . . . 11 2.2.1 Consideration of Proximity . . . . . . . . . . . . . 12 2.2.2 Caching . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Load Balancing . . . . . . . . . . . . . . . . . . . . 17 2.4 Object Maintenance Strategy . . . . . . . . . . . . . 18 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . 19 3 System Model . . . . . . . . . . . . . . . . . . . . . . 21 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 The Chordal Ring Overlay . . . . . . . . . . . . . . . 23 3.2.1 Approaching Proximity . . . . . . . . . . . . . . . 25 3.3 Fault Tolerance and Object Availability . . . . . . . 29 3.3.1 Fault tolerance mechanism . . . . . . . . . . . . . 29 3.3.2 Object Availability . . . . . . . . . . . . . . . . 32 3.4 Load Balancing . . . . . . . . . . . . . . . . . . . . 34 3.5 Cooperative Cache . . . . . . . . . . . . . . . . . . 36 3.5.1 Enabling Search with Cooperative Caching . . . . . . 39 4 Experimental Results . . . . . . . . . . . . . . . . . . 41 4.1 Simulation Methodology . . . . . . . . . . . . . . . . 41 4.2 Notations . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Overlay Proximity and Grouping . . . . . . . . . . . . 45 4.3.1 The Impact of Grouping on Overlay Proximity . . . . 46 4.3.2 The Impact of Grouping on Proximity Table . . . . . 48 4.3.3 The Scalability of Our Joining Algorithm . . . . . . 48 4.4 Load Balancing . . . . . . . . . . . . . . . . . . . . 50 4.4.1 Basic Effect of Neighbor Balance . . . . . . . . . . 51 4.4.2 Basic Effect of Peer Reorder . . . . . . . . . . . . 52 4.4.3 Combine Effect of Load Balance Schemes . . . . . . . 53 4.5 Search and Cache Performance . . . . . . . . . . . . . 57 4.5.1 Effect of Cache . . . . . . . . . . . . . . . . . . 60 4.5.2 Effect of Cache Size . . . . . . . . . . . . . . . . 60 4.5.3 Effect of Cache Union Size . . . . . . . . . . . . . 63 5 Conclusion and Future Work . . . . . . . . . . . . . . . 65 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . 66 Bibliography . . . . . . . . . . . . . . . . . . . . . . . 67 | |
dc.language.iso | en | |
dc.title | 考慮地域鄰近性且群組化的點對點範圍查詢系統 | zh_TW |
dc.title | A Proximity-Aware and Group-Based Peer-to-Peer System for Range Queries | en |
dc.type | Thesis | |
dc.date.schoolyear | 95-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林宗男(Tsung-Nan Lin),蔡益坤(Yih-Kuen Tsay) | |
dc.subject.keyword | 點對點網路,範圍查詢,鄰近性,群組化,負載平衡, | zh_TW |
dc.subject.keyword | Peer-to-Peer,Range Queries,Proximity,Grouping,Load Balance, | en |
dc.relation.page | 71 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2007-07-27 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 2.75 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。