講演抄録/キーワード |
講演名 |
2011-12-16 16:10
バックトラッキングを伴う構造化オーバレイネットワーク上のオブジェクト探索 ○福本 聡・小澤一平・新井雅之(首都大東京) DC2011-73 |
抄録 |
(和) |
本研究では,構造化オーバレイネットワーク Chord のルーティングプロトコルにバックトラッキングを追加した場合の耐故障性について考察する.ここでは,各ノードが後任ノードリストを持たない場合を仮定する.はじめに,Chord のルーティングプロトコルとバックトラッキングの概要について述べる.次に,ノード故障を考慮した Chord のルーティングの基本的な特性を明らかにするため,代替リンクを用いない場合と,用いる場合それぞれの耐故障性と性能について解析的ならびに数値的に議論する.評価尺度として,探索成功確率と探索成功時・失敗時の累積ホップ数分布を用いる.最後に,バックトラッキングを伴う Chord の耐故障性と性能をシミュレーションによって見積もり,オブジェクト探索における効果的な方策について論じる. |
(英) |
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 / 分散ハッシュテーブル / 耐故障性 / / / / |
(英) |
overlay network / Chord / distributed hash table / fault tolerance / / / / |
文献情報 |
信学技報, vol. 111, no. 362, DC2011-73, pp. 27-32, 2011年12月. |
資料番号 |
DC2011-73 |
発行日 |
2011-12-09 (DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
DC2011-73 |