バックトラッキングを伴う構造化オーバレイネットワーク上のオブジェクト探索

摘要

本研究では，構造化オーバレイネットワークChordのルーティングプロトコルにバックトラッキングを追加した場合の耐故障性について考察する．ここでは，各ノードが後任ノードリストを持たない場合を仮定する．はじめに，Chordのルーティングプロトコルとバックトラッキングの概要について述べる．次に，ノード故障を考慮したChordのルーティングの基本的な特性を明らかにするため，代替リンクを用いない場合と，用いる場合それぞれの耐故障性と性能について解析的ならびに数値的に議論する．評価尺度として，探索成功確率と探索成功時·失敗時の累積ホップ数分布を用いる．最後に，バックトラッキングを伴うChordの耐故障性と性能をシミュレーションによって見積もり，オブジェクト探索における効果的な方策について論じる．