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

乾　広二  鈴木　朋子  大下　福仁  角川　裕次  増澤　利光 

誌名
電子情報通信学会論文誌 D  Vol.J91-D  No.5  pp.1261-1274
発行日: 2008/05/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 論文
専門分野: ディペンダブルコンピューティング
キーワード: 
構造化オーバレイネットワーク,  分散ハッシュテーブル,  Chord,  故障耐性,  経路の多重化, 

本文: PDF(1MB)

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