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

摘要

This paper discusses the fault tolerance of routing protocol by the structured overlay network "Chord" with backtrackings. We here suppose that each node in network does not have the successor list. First, routing protocol and backtracking in Chord are briefly described. Secondly, fault tolerance and performance are considered numerically and analytically for the cases with/without alternate links, in order to check up on the fundamental property of Chord's routing on the assumption of node faults. Fraction of successful lookups and distributions of hop counts for successful and unsuccessful lookups are employed for evaluation measures. We finally estimate the fault tolerance and performance of Chord with backtrackings by simulations and discuss the effective strategy in object search.%本研究では，構造化オーバレイネットワークChord のルーティングプロトコルにバックトラッキングを追加した場合の耐故障性について考察する．ここでは，各ノードが後任ノードリストを持たない場合を仮定する．はじめに，Chord のルーティングプロトコルとバックトラッキングの概要について述べる．次に，ノード故障を考慮したChord のルーティングの基本的な特性を明らかにするため，代替リンクを用いない場合と，用いる場合それぞれの耐故障性と性能について解析的ならびに数値的に議論する．評価尺度として，探索成功確率と探索成功時・失敗時の累積ホップ数分布を用いる．最後に，バックトラッキングを伴うChord の耐故障性と性能をシミュレーションによって見積もり，オブジェクト探索における効果的な方策について論じる．