Chord<sup>＃</sup>における経路表の維持管理コスト削減手法の提案とその評価

情報処理学会 Web Site

書誌事項

タイトル別名
  • A Method for Reducing Maintenance Cost of Routing Table in Chord<sup>＃</sup> and Its Evaluation
  • Chord#ニ オケル ケイロヒョウ ノ イジ カンリ コスト サクゲン シュホウ ノ テイアン ト ソノ ヒョウカ

この論文をさがす

説明

Chord#は範囲検索が可能な構造化P2P（Peer-to-Peer）ネットワークの一種である．Chord#ではショートカットリンク（finger table）を用いることでノード数nに対して，O(log n)ホップで検索が可能である．Chord# のfinger tableは，ノードの挿入や削除，障害に対応するために定期的に更新する必要があるが，本稿ではこの更新処理のコストを削減する方式を提案する．提案手法では，finger tableを2次元配列に拡張したうえで，隣接するノードのfinger tableが類似していることを利用して更新処理に必要なメッセージ数を数分の1に削減する．さらに，リモートノード離脱時のfinger table更新処理の高速化，およびネットワーク近接性を利用したルーティングも実現した．提案方式の有効性はシミュレーションにより確認した．

Chord# is a kind of structured Peer-to-Peer (P2P) network that supports range queries. Chord# achieves O(log n) search hops, where n denotes the number of nodes, by using a finger table, a collection of short cut links. A finger table of Chord# must be periodically updated to catch up node insertion, deletion and failure. In this paper, we propose a method to reduce the cost of updating finger tables. Finger tables are extended to two-dimensional arrays and the cost of updating finger tables is reduced by using the similarity of finger tables of adjacent nodes. The method avoids delay in updating finger tables caused by node leaving and also supports proximity routing. The effectiveness of the proposed method is experimentally confirmed by computer simulations.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ