構造化オーバレイネットワークにおける故障耐性向上のための経路多重化法

摘要

オーバレイネノトワ一クとは実ネノトワ－ク上に構成される論理的ネノトワークである．特に，構造化オ、－バレイネットワークとはノ－ド間の隣接関係に規則性があるオーバレイネットワ－クであり，その代表例として分散ハブシユテーブル（DHT）がある．多くの構造化オーバレイネットワ－クでは，その規則的構造から任意のノ－ドへ効率的にメッセージを配送可能である．しかしメッセージを配送する経路上に故障ノードが存在する場合，メッセ、－ジを配送することができか－．この間題を解決する一手法として，マルチパス，ワイドパスなどの経路の多重化がある．マルチパスは低コストで実胡できるが故障耐性が十分でなく，ワイドパスは高い故障耐性を石する反面，高コストである．そこで本論文では，これらの手法を組み合わせた手法（マルチワイドパス）を提案する．更に，代表的なDHTであるChordに対し，マルチパス，ワイドパス，マルチワイドパスをそれぞれ適用し，各手法の故障耐性とコストを解析とシミュレーションにより評価する．．結果，提案手法は既存手法に比べて同程度の故障耐性を低コストで実現できることを示す．