利用異質性降低Chord點對點系統之維護成本

Abstract

隨著網際網路的擴張以及個人電腦效能的成長，點對點系統打破了傳統主從式網路架構的限制，讓使用者可以彼此分享資源、也使得點對點系統越來越受歡迎及注目。為了解決點對點網路在延展性以及搜尋效率上的問題，已有許多以分散式雜湊表(Distributed Hash Table)為基礎的點對點系統研究相繼被提出，例如：Chord、Tapestry、CAN、Pastry。在這些系統中，每個節點必須要維護部份的路由資訊以合作完成資訊傳遞及搜尋的功能。因此，如何有效率的維護這些路由資訊將影響這些DHT系統的效能以及正確性。雖然DHT點對點系統有許多的優點，但目前大多數的系統仍採用非結構化的點對對模式，原因即在於以DHT為基礎的方式耗費了太多的頻寬在維護路由資訊上。 多數的點對點系統將每個節點的能力以及負擔都視為是平等的；然而真實的網路觀察結果卻發現異質性是普遍存在的—每個節點的能力以及頻寬不盡相同，甚至有相當的差距。在論文中，我們賦予不同能力的節點不同的工作負擔；修改Chord點對點系統的演算法以降低維護成本。實驗模擬的結果證明我們的系統能有效的減少不必要的頻寬消耗，使得系統能更具可實用性。

As Internet grows and the capability of PC improves, peer-to-peer (P2P) systems become increasingly popular due to the potential for overcoming several limitations of client/server systems with respect to scalability, content availability and computing power. To tackle the challenges in scalability and the issues of search, various schemes have been proposed in the literature, such as Chord, CAN, Tapestry, and Pastry. These are distributed hash tables (DHTs). In order to make DHT based search e±cient, nodes use local information as routing guides to forward requests to appropriate intermediary nodes. The efficiency and correctness for all DHT overlays depends on the consistent maintenance of routing tables at each peers even under highly dynamical network conditions. Although DHT based P2P systems are praised for their e±cient routing performance, most released P2P systems do not adopt DHT algorithms and are still using unstructured P2P manners. The main problem in DHT algorithm implementation is the high traffic load for maintaining DHT structures. The primitive DHT designs tend to involve the participating nodes equally, but the empirical studies have demonstrated the diversity between system nodes. Considering such diversity, we design to collect more resources from capable participants rather than treat all participants equally. In this thesis, we propose a super-peer based approach to reduce maintenance overhead in Chord P2P algorithm. Our design takes advantage of the heterogeneity of network peers. The experimental results show that our approach saves the meaningless maintenance overhead and makes Chord P2P system more practical.