Chord#における経路表の維持管理コスト削減手法の提案とその評価
書誌情報
呉承彦, 安倍広多, 石橋勇人, 松浦敏雄, Chord#における経路表の維持管理コスト削減手法の提案とその評価, 情報処理学会論文誌, Vol. 53, No. 12, pp. 2752-2761, (2012-12).
Abstract
Chord#は範囲検索が可能な構造化P2P（Peer-to-Peer）ネットワークの一種である．Chord#ではショートカットリンク（finger table）を用いることでノード数nに対して，O(log n)ホップで検索が可能である．Chord# のfinger tableは，ノードの挿入や削除，障害に対応するために定期的に更新する必要があるが，本稿ではこの更新処理のコストを削減する方式を提案する．提案手法では，finger tableを2次元配列に拡張したうえで，隣接するノードのfinger tableが類似していることを利用して更新処理に必要なメッセージ数を数分の1に削減する．さらに，リモートノード離脱時のfinger table更新処理の高速化，およびネットワーク近接性を利用したルーティングも実現した．提案方式の有効性はシミュレーションにより確認した．