王勝德臺灣大學：電機工程學研究所莊永裕Zhuang, Yung-YuYung-YuZhuang2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/52946以分散雜湊表（Distributed hash table）為基礎的點對點系統諸如CAN、Chord、Pastry、Tapestry提供了相當有效率且可保證的平台。但既然DHT以一致的雜湊函數均勻地將節點及物件分佈到虛擬空間，同時也破壞了原本節點之間的區域性（Locality）。而以分散雜湊表為基礎的階層式架構如HIERAS、Canon以地理位置將節點分群，大幅地提昇區域性，但它們仍然無法充分地利用階層結構的優點。此外，因為它們不具有可適應性，效能會因系統狀況而有所差異。在這篇論文中，我們提出一個具可適應性並能動態分群的架構—Pharos 。它將階層式架構應用在DHT，並以區域性為準則來均勻地分群。利用Super-peer的特性，它能有效地管理群組，同時仍保留了DHT的特性。由於動態的分群方式，使得Pharos具有可適應性而總是能保持它的區域性與效率。Distributed hash tables (DHT) based P2P systems such as CAN, Chord, Pastry, and Tapestry, provide efficient platforms with the guaranteed searching performance. But the locality is destroyed since DHTs use a uniform hash function to distribute nodes and objects in the virtual space evenly. The hierarchical architecture based on DHTs like HIERAS and Canon, significantly improves locality by grouping nodes geographically, but they still cannot take full advantage of hierarchy. Furthermore their performances vary with the system status because they are not adaptive. In this thesis, we propose an adaptive architecture with dynamic grouping, called Pharos. It applies hierarchical overlays on DHTs and groups nodes with locality evenly. Pharos manages groups effectively by taking advantage of the super-peer architecture but reserves the load balance guarantee of DHTs. Because of dynamic grouping, Pharos is adaptive and always keeps its locality and efficiency.中文摘要 i 英文摘要 ii 致謝 iii 1. Introduction 1 2. Related Work 3 2.1. Locality 3 2.2. Efficiency 5 3. The Design of Pharos 5 3.1. Architecture and Searching 5 3.2. Lighthouse 7 3.3. Node Join Algorithm 9 3.3.1. Hierarchical Join Procedure 9 3.3.2. Dynamic Grouping Scheme 10 3.4. Deploy on DHTs 11 3.4.1. Pharos-CAN 11 3.4.2. Pharos-Chord 13 3.5. Caching 15 3.6. Costs and Properties 15 3.6.1. Node Joining 15 3.6.2. Disbanding 16 3.6.3. Group Area 18 3.7. Lighthouse Recovery 18 3.7.1. Lighthouse Exiting 19 3.7.2. Lighthouse Failure 19 4. Performance 20 4.1. Locality 20 4.2. Efficiency 24 4.3. Adaptability 28 4.4. Search Method 31 4.5. Group Accepting Range 34 4.6. Number of Groups 36 4.7. Cache Policy 38 4.8. Group Management 40 4.9. Memory Cost 41 5. Conclusion 41 Reference 42398535 bytesapplication/pdfen-US點對點虛擬空間分散雜湊表覆遞h區域性peer-to-peeroverlayDHTvirtual spacelocalitythesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/52946/1/ntu-93-R91921072-1.pdf