RCAN : A Multi-ring Content Addressable Network

• Item type: SIG Technical Reports(1)
• 公開日: 2008-09-14
• タイトル: RCAN : A Multi-ring Content Addressable Network
• タイトル / 言語: en
• タイトル: RCAN : A Multi-ring Content Addressable Network
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻
• 著者所属: 筑波大学計算科学研究センター
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba / Center for Computational Sciences, University of Tsukuba
• 著者名: ブーケレフジェッルール; 北川, 博之
• 著者名(英): Djelloul, Boukhelef; Hiroyuki, Kitagawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We present in this paper RCAN a novel topological structure to improve the routing performance of CAN overlays while minimizing the maintenance overhead during nodes churn in large size networks. The key idea for our design is to equip each node with few long-links towards some distant nodes. Long-links are clockwise directed and wrap around to form small rings along each dimension. The number of rings and their sizes self-adjust as nodes join and leave the systems. RCAN is a pure P2P design where all nodes assume the same responsibility. Unlike other concurent P2P overlays RCAN is self-organizing and does not assume any \emph{a-priori} fixed limits for the network size or the routing state per node. Each node auto-adapts its routing state to cope with network changes. RCAN maintains $O(\log n)$ routing state per node and achieves $O(\log n)$ routing performance by following a simple greedy routing algorithm. Arguably the amount of routing state is not a big issue if the associated maintenance cost is reasonable. From this viewpoint we proposed an efficient mechanism to establish/maintain long links that increases nodes' connectivity to offer more routing flexibility and robustness while reducing the total cost of join operation to $O(\log n)$ messages instead of $O(\log^2 n)$ in some other existing protocols such as: Chord pastry SCAN etc. Through simulation we have demonstrated the full scalability and efficiency of our design and its advantages over other existing methods.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present in this paper RCAN, a novel topological structure to improve the routing performance of CAN overlays while minimizing the maintenance overhead during nodes churn in large size networks. The key idea for our design is to equip each node with few long-links towards some distant nodes. Long-links are clockwise directed and wrap around to form small rings along each dimension. The number of rings and their sizes self-adjust as nodes join and leave the systems. RCAN is a pure P2P design, where all nodes assume the same responsibility. Unlike other concurent P2P overlays, RCAN is self-organizing and does not assume any \emph{a-priori} fixed limits for the network size or the routing state per node. Each node auto-adapts its routing state to cope with network changes. RCAN maintains $O(\log n)$ routing state per node, and achieves $O(\log n)$ routing performance by following a simple greedy routing algorithm. Arguably, the amount of routing state is not a big issue if the associated maintenance cost is reasonable. From this viewpoint, we proposed an efficient mechanism to establish/maintain long links that increases nodes' connectivity, to offer more routing flexibility and robustness, while reducing the total cost of join operation to $O(\log n)$ messages, instead of $O(\log^2 n)$ in some other existing protocols, such as: Chord, pastry, SCAN, etc. Through simulation we have demonstrated the full scalability and efficiency of our design and its advantages over other existing methods.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2008, 号 88(2008-DBS-146), p. 91-96, 発行日 2008-09-14
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会