4.1代 替 リ ン ク を 用 い な い 場 合....

修 士論 文

構 造 化P2Pネ ッ トワ ー クChordの 耐 故 障 性 評 価

EvaluationofFaultTolerance

forStructuredP2PNetwork .Chord

首都大 学東京大 学院 システムデザ イ ン研究科 情報通信 システム学域

10890507小 澤 一平 指導 教員 福本 聡 教授

近 年,P2P(Peer‑t(‑Peer)ネ ッ トワー クが イ ン ター ネ ッ ト通 信 に 広 く利 用 さ れ て い る.

p2Pネ ッ トワー ク は オー バ レイ ネ ッ トワー クの 一種 で,実 ネ ッ トワ ー クで 繋 が っ た多 数 の ピア(端 末,ノ ー ドと もい う)に よ る仮 想 的 なオ ー バ レイ ネ ッ トワ ー クで あ る.P2Pネ ッ

トワー ク は クラ イ ア ン ト ・サ ー バ 型 ネ ッ トワー ク と違 い,全 て の ノ ー ドが サー バ と して も ク ラ イ ア ン トと して も振 る舞 う.こ の ため,サ0バ へ の クエ リの集 中 に よ る高 負 荷 や,サ ー バ ダ ウ ン等 の シ ン グル ポ イ ン ト故 障 に高 い耐 性 を 持 つ.

構 造 化P2Pは オ ー バ レイ ネ ッ トワー ク を構 成 す る リン ク の持 ち方 が 構 造 的 に定 め られ て お り,探 索 メ ッセ ー ジ は この リ ン ク に よ る転 送 を 繰 り返 して 目 的 ノ ー ドま で到 達 す る こ と が 保 証 さ れ て い る.こ の オ ー バ レイ ネ ッ トワー クを 構 成 す る方 式 と して 分 散 ハ ッシ ュテ ー

ブル が よ く利 用 さ れ る.分 散 ハ ッ シ ュテ ー ブル を 用 い る こ とで,総 ノー ド数 が 増 大 して も 必 要 な メ ッセ ー ジ 量 が わ ず か しか 増 えな い ス ケ ー ラ ブル なネ ッ トワ ー クを 実 現 す る こ とが で き る.分 散 ハ ッ シ ュ テー ブル を利 用 したP2Pに は,Chord,Pastry,Symphony等 が あ る.

本 研 究 で は,代 表 的 な構 造 化P2Pネ ッ トワー クで あ るChordの ル ー テ ィ ン グ プ ロ トコ ル の 耐 故 障 性 を定 量 的 に議 論 す る.構 造 化P2Pで あ るChordは,ハ ッ シ ュ空 間上 に 分 散 配 置 さ れ たオ ブ ジ ェク トを 効 果 的 に探 索 す る こ とが可 能 で あ る.そ の 基 本 的 な 仕 組 み は,各

ノー ドがそ れ ぞれ に保 持 す る分 散 ハ ッシ ュテ ー ブ ル の リ ン ク情 報 に基 づ い て 最 適 な ホ ップ 先 を 順 次 決 定 す る とい う もの で あ る.こ の よ うな グ リー デ ィな ル ー テ ィ ン グ プ ロ トコル で は,ノ ー ドの 故 障 に対 す る 本 質 的 な 耐 性 を 備 え て い る.す な わ ち,最 適 な ホ ッ プ先 の ノ ー ドが 故 障 してい る場 合 で も,ハ ッシ ュテー ブル 上 の次 善 の リ ン ク先 ノー ドを ホ ッ プ先 に 選 択 す る こ とで オ ブ ジ ェ ク ト探 索 を 継 続 す る こ とが で き る.さ らに,Chordは 後 任 ノー ドリ ス トと呼 ば れ る追 加 的 な リン ク情報 を 用 い る こ とで,性 能 お よび 耐 故 障性 を 高 め る こ とが で き る.'

本 研 究 で は,ま ず,ノ ー ド故 障 を 考慮 したChordの ル ー テ ィ ン グの 基 本 的 な特 性 を明 ら か に す る た め,代 替 リン ク を用 い ない 場 合 と,用 い る場 合 そ れ ぞ れ の 耐 故 障性 と性 能 につ い て解 析 的 お よび 数 値 的 に議 論 す る.評 価 尺 度 と して,探 索 成 功 確 率 と探 索 成 功 時 ・失 敗 時 の累 積 ホ ップ 数 分 布 を 用 い る.つ ぎ に,バ ッ ク トラ ッキ ン グを 伴 うル ー テ ィ ン グの 耐 故 障性 を考 察 す る.バ ッ ク トラ ッ キ ン グを 伴 うル ー テ ィ ン グ とは,探 索 経 路 上 の ノ ー ドに お い てつ ぎ に選 ぶべ き ホ ップ先 ノー ドがす べ て 故 障 して い る場 合 に,探 索 経 路 を1ノ ー ドさ か の ぼ っ て ホ ップ先 を 選 択 し直 す こ とが 可 能 とす る もの で あ る.こ れ に よ っ て,失 敗 とな る探 索 経 路 を迂 回 して探 索 を 続 け る こ とが で き る.こ の ル ー テ ィ ング に つ い て耐 故 障 性 と 性 能 を シ ミ ュ レー シ ョ ンに よ っ て見 積 も り,オ ブ ジ ェ ク ト探 索 にお け る 効 果 的 な方 策 に つ い て 論 じる.

結果 と して,探 索 成 功 時 の ホ ップ数 分 布 に注 目 して探 索 ホ ッ プ数 の 許 容 値 を 制 限 し3バ ッ ク トラ ッキ ン グ に多 くの探 索 コス トを 費 や すべ き で は な い こ とな どを示 す.

目 次

1序 論

¹

2関 連研究

4

3Chordの 概 要 12

4Chordの 耐 故 障 性

4.1代 替 リ ン ク を 用 い な い 場 合....

4.2代 替 リ ン ク を 用 い る 場 合...

4.3バ ッ ク トラ ッ キ ン グ を 用 い る 場 合..

19 19 .24

.31

5結 論

³⁹

参考文献

⁴⁰

謝辞

⁴¹

図 目 次

2.1DistHashの 構 成...6

22Semiasの レ プ リ カ グ ル ー プ 管 理 の 例...6

2.3Semiasの レ プ リ カ グ ル ー プ 再 構 成 の 例... ...7

2.4Al‑Shishtawyら の 提 案 す る レ プ リ カ グ ル ー プ 管 理 手 法 の 夙...7

2.5Saturnの 構 造...8

2.6. のChordを 利 用 し た ネ ッ ト ワ ー ク の 例...̲..11

2.7CRPの ス パ ニ ン グ ツ リ ー の 例...。..11

3.1Chordの 構 造 の 例..。...。...12

32Chordの ル ー テ ィ ン グ の 例...。...13

3.3ブ イ ン ガ テ ー ブ ル の 例...,...16

3.4フ ィ ン ガ テ ー ブ ル を 用 い たChordの ル ー テ ィ ン グ 例...17

3.5ノ ー ド の 参 加 が な い 場 合 の 安 定 化 プ ロ ト コ ル の 例...17

3.6ノ ー ド の 参 加 が あ っ た 場 合 の 安 定 化 プ ロ ト コ ル の 例...18

3.7後 任 ノ ー ド を 更 新...,...18

4.1代 替 リ ン ク を 用 い な いChordの ル ー テ ィ ン グ 例...。...。...20

4.2代 替 リ ン ク を 用 い な いChordの 探 索 成 功 確 率...21

4.3代 替 リ ン ク を 用 い な いChordの 探 索 成 功 確 率 の 解 析 値 と シ ミ ュ レ ー シ ョ ン 結 果...9..,...22

4.4代 替 リ ン ク を 用 い な いChordの 探 索 成 功 お よ び 失 敗 ま で の ホ ッ プ 数 の 分 布.23 4.5代 替 リ ン ク を 用 い るChordの ル ー テ ィ ン グ 例...。..25

4.6ノ ー ド が 故 障 し て い る と き に 代 替 リ ン ク を 用 い るChordの 探 索 成 功 確 率.26 4.7定 理2の 証 明 で 想 定 し て い るChordの リ ン ク 構 造 の 具 体 例...27

4.8ノ ー ド が 故 障 し て い る と き に 代 替 リ ン ク を 用 い るChordの 総 期 待 ホ ッ プ 数29 4.9ノ ー ド が 故 障 し て い る と き に 代 替 リ ン ク を 用 い るChordの 探 索 成 功 ・失 敗 時 ホ ッ プ 数 分 布.̲...'30

4.10ノ ー ド が 故 障 し て い る と き に 代 替 リ ン ク を 用 い るChordの 探 索 成 功 ・失 敗 時 ホ ッ プ 数 累 積 分 布...,...,...31

4.11バ ッ ク ト ラ ッ キ ン グ を 用 い た ル ー テ ィ ン グ 例...32

4.12バ ッ ク ト ラ ッ キ ン グ に よ る 膨 大 な 探 索 時 間 増 加 の 例...33

4.13バ ッ ク ト ラ ッ キ ン グ を 伴 うChordと 伴 わ な いChordの 探 索 成 功 確 率...34

4.14バ ッ ク ト ラ ッ キ ン グ を 伴 うChordの 探 索 成 功 確 率 の シ ミ ュ レ ー シ ョ ン 結 果 と 上 限...35

4.15バ ッ ク ト ラ ッ キ ン グ を 伴 うChordと 伴 わ な いChordの 探 索 成 功 時 ホ ッ プ 数 分 布...。...36

4.16小 さ い ホ ッ プ 数 に 注 目 し た,バ ッ ク ト ラ ッ キ ン グ を 伴 うChordの 探 索 成 功 ・ 失 敗 時 ホ ッ プ 数 累 積 分 布...,...37

4.・7膨 ク ト ラ ッ キ ン グ を 伴 うCh・ ・dの 探 轍 功 ・失 敗 時 ホ ッ プ 数 累 積 分 布38'

表 目 次

2.1分 散 ハ ッ シ ュ テ ー ブ ル の 例...4

1序 論

近 年,P2P(Peer‑t(‑Peer)ネ ッ トワー ク に関 す る研 究 が多 く報 告 され て い る.P2Pネ ッ トワー クは オ ー バ レイ ネ ッ トワー クの 一種 で,実 ネ ッ トワー ク で繋 が っ た多 数 の ピ ア(端 末,ノ ー ドとも い う)で 構 成 さ れ る仮 想 的 なネ ッ トワー クで あ る.P2Pネ ッ トワー ク は ク ライ ア ン ト ・サ ー バ 型 ネ ッ トワー ク と違 い,全 て の ノ ー ドが サ ー バ と して も クラ イ ア ン ト

と して も振 る 舞 う.こ の た め,サ ー バ へ の要 求 の集 中 に よ る高 負 荷 や,サ ー バ ダ ウ ン等 の シ ン グル ポ イ ン ト故 障 に高 い耐 性 を持 つ.

P2Pネ ッ トワー ク で は全 て の ノー ドが サ ー バ と成 り得 る た め,ど の オ ブ ジ ェ ク トが どの ノー ドに存 在 す る か を示 す イ ンデ ック ス を管 理 す る手 法 が 極 め て 重 要 とな る.P2Pネ ッ ト ワー クは イ ンデ ッ クス 管理 の方 式 に よって 大 き く二 つ に分 類 す る こ とが で き る.一 つ は,イ ンデ ッ ク スを サ ー バ が一 括 して 管理 す るハ イ ブ リ ッ ドP2Pで あ る.ハ イ ブ リ ッ ドP2Pで は ノー ド同士 で オ ブ ジ ェ ク トの通 信 が お こな わ れ る た め,ク ライ ア ン ト ・サー バ 型 ネ ッ ト ワー ク と比 べ て 帯 域 負 荷 が 分 散 さ れ る点 が特 徴 で あ る.ま た,イ ン デ ッ ク ス を サ ー バ が 一 括 管 理 す る ため,管 理 者 が ネ ッ トワ ー クに存 在 す るオ ブ ジ ェ ク トを 管理 す る こ とが で き る.

しか しな が ら,サ ー バ にイ ン デ ック ス の要 求 負 荷 が集 中 す る た め,ス ケ ー ラ ビ リテ ィ はそ れ ほ ど高 くな く,サ ー バ を 必 要 と して い る点 で シ ン グル ポ イ ン ト故 障 へ の 耐 性 は良 くな い.

代 表 的 なハ イ ブ リ ッ ドP2Pに は,Napster,BitTorrent等 が 挙 げ られ る.

も う一 方 は,ノ ー ド同士 で イ ン デ ッ クス を分 散 して管 理 す る ピ ュ アP2Pで あ る.ピ ュア P2Pは サ ー バ レス ネ ッ トワー クで,シ ン グル ポ イ ン ト故 障 に 強 い 耐 性 を持 つ とさ れ る.イ ンデ ッ ク ス を各 ノ ー ドで 分 散 管 理 す る た め,ス ケー ラ ビ リテ ィが 高 く設 計 で き る こ とが 特 徴 で あ る.さ ら に ピ ュ アP2Pは,探 索 メ ッセ ー ジの 転 送 方 式 に よ って 非 構 造 化P2Pと 構 造 化P2Pに 分 け られ る.

非 構 造 化P2Pは,自 分 の 持 つ 全 て の リン ク 先 ノ ー ドに対 して 手 当 た り次 第 に メ ッセ ー ジ を 送 信 して い くフ ラ ッデ ィ ン グ方 式 で探 索 が 行 わ れ る.フ ラ ッデ ィ ン グ方 式 で は柔 軟 な 検 索 が 可 能 で あ る反 面,ネ ッ トワー ク の総 ノー ド数 の増 大 に伴 っ て転 送 さ れ る メ ッセ ー ジ の 量 が 多 くな り,ネ ッ トワー ク帯 域 の 負 荷 が 増 大 す る とい う特 徴 が あ る.過 負 荷 を 防 ぐた め に メ ッセ ー ジ数 を転 送 回 数 や 生 存 時 間 で 抑 え る と,メ ッセ ー ジが 目的 ノ ー ドま で到 達 し な い可 能 性 が あ る.フ ラ ッデ ィ ング方 式 を 利 用 したP2Pに,Gnutella,Ereenet,Winny

等 が あ る.

一方,構 造 化P2Pは オ ー バ レイ ネ ッ トワー クが 構 造 的 に定 め られ て お り,探 索 メ ッセ0 ジ は転 送 を 繰 り返 して 目的 ノー ドまで 到 達 され る こ とが 保 証 さ れ て い る.こ の オ ー バ レイ ネ ッ トワー クを構 成 す る方 式 と して 分散 ハ ッシ ュテ ー ブ ル が よ く利 用 され る.分 散 ハ ッ シ ュ テー ブ ル を 応 用 す る こ とで,総 ノ ー ド数 が増 大 して も必 要 な メ ッセ ー ジ量 が わ ず か しか増 え な い ス ケ ー ラ ブ ル な ネ ッ トワ ー クを 実 現 す る こ とが で き る.分 散 ハ ッ シ ュ テ ー ブル を利 用 したP2Pに は,Chord,Pastry,Symphony等 が あ る.

本 研 究 で は,代 表 的 な 構 造 化P2Pネ ッ トワー クで あ るChordの ル ー テ ィ ン グ プ ロ トコ ル の耐 故 障 性 を定 量 的 に 議 論 す る.構 造 化P2Pで あ るChordは 分 散 ハ ッシ ュテ ー ブル を

基 本 と し,ハ ッ シ ュ空 間 上 に ノー ド とオ ブ ジ ェ ク トをハ ッ シ ュ ・キ ー に よ って配 置 す る.各 ノー ドは それ ぞれ,経 路 表 と呼 ばれ る構造 的 に定 め られ る リ ン ク情 報 を 持 ってい る.各 ノー

ドは,経 路 表 の 内容 の一 つ で あ るハ ッシ ュ空 間上 で 隣接 す る ノー ドとの リン クを 用 い て,担 当 す べ きハ ッシ ュ空 間上 の 範 囲 を知 り,そ の 範 囲の ハ ッシ ュ ・キ ー を持 つ オ ブ ジ ェ ク トを 提 供 す る こ とに な る.

Chordで はハ ッ シ ュ空 間上 に 分散 配 置 さ れ たオ ブ ジ ェ ク トを 効 果 的 に探 索 す る こ とが 可 能 で あ る.そ の 基 本 的 な 仕 組 み は,各 ノ ー ドが そ れ ぞ れ に保 持 す る 経 路 表 に基 づ い て最 適 な ホ ッ プ先 を順 次 決 定 す る とい う もの で あ る.こ の よ うな グ リー デ ィな ル ー テ ィ ン グ プ ロ トコ ル で は,ノ ー ドの 故 障 に対 す る本 質 的 な耐 性 を備 え て い る.す な わ ち,最 適 な ホ ップ 先 の ノ ー ドが 故 障 して い る場 合 で も,ハ ッシ ュテ ー ブル 上 の 次 善 の リ ン ク先 ノー ドを ホ ッ プ先 に選 択 す る こ とで オ ブ ジ ェ ク ト探 索 を継 続 す る こ とが で き る.さ らに,Chordは 後 任 ノー ドリス トと呼 ば れ る追 加 的 な リン ク情 報 を用 い る こ とで,性 能 お よび 耐 故 障 性 を高 め る こ とが で き る.本 研 究 で は,Chordの フ ィ ン ガテ ー ブ ル に よ る耐 故 障 性 を 確 か め る た め に,後 任 ノ ー ドリス トを 持 た な い場 合 を対 象 と してい る.

本 研 究 で は,ま ず,ノ ー ド故 障 を考 慮 したChordの ル ー テ ィ ン グ の 基 本 的 な特 性 を 明 らか にす る た め,代 替 リ ン クを 用 い ない 場 合 と用 い る場 合 そ れ ぞれ の耐 故 障 性 と性 能 につ い て 解 析 的 お よ び数 値 的 に議 論 す る.そ れ ぞ れ につ い て,安 定 化 プ ロ トコル の 実 行 か ら次 の 実 行 ま で の 過 渡 的 な 状 態 を想 定 し,ノ ー ドの故 障率 を パ ラ メー タ と して解 析 及 び シ ミ ュ レー シ ョ ンに よ る評 価 を お こ な う.評 価 尺 度 と して,探 索 成 功 確 率 と平 均 ホ ッ プ数,探 索 成 功 時 ・失 敗 時 の ホ ップ 数 分 布 及 び累 積 分 布 を 用 い る.

つ ぎ に,バ ッ ク トラ ッキ ン グを 伴 うル ー テ ィ ン グの 耐 故 障 性 と性 能 を考 察 す る.バ ッ ク トラ ッ キ ン グを 伴 うル ー テ ィ ン グ とは,探 索 経 路 上 の ノ ー ドに お い てつ ぎ に選 ぶ べ き ホ ッ プ 先 ノー ドが す べ て 故 障 して い る場 合 に,探 索 経 路 を1ノ ー ドさか の ぼ って ホ ッ プ先 を 選 択 し直 す こ とが 可 能 とす る もの で あ る.こ れ に よ って,失 敗 とな る探 索 経 路 を迂 回 して 探 索 を 続 け る こ とが で き る.こ のル ー テ ィ ング プ ロ トコル につ い て 耐 故 障 性 と性 能 を シ ミ ュ レー シ ョン に よ って 見 積 も り,オ ブ ジ ェ ク ト探 索 に お け る効 果 的 な 方策 につ い て論 ず る.ま た,探 索 成 功 確 率 の解 析 的 導 出 につ い て 考 察 を す る.

結 果 と して,バ ッ ク トラ ッキ ン グを 伴 うル ー テ ィ ン グで は,探 索 成 功 時 の ホ ッ プ数 分 布 に 注 目 して探 索 ホ ッ プ数 の 許 容 値 を 制 限 し,バ ッ ク トラ ッキ ン グ に多 くの探 索 コス トを 費 や す べ き で は な い こ とな どを 示 す.

本 論 文 の 構 成 は以 下 の 通 りで あ る.1は 序論 であ り,本 研 究 の 背 景 や 目的等 に 関 して述 べ る.2は 関連 研 究 で あ る.ま ず,構 造 化P2Pネ ッ トワー ク につ いて 概 説 し,つ ぎに近 年 提 案 さ れ たP2Pネ ッ トワー ク に関 す る論 文 を耐 故 障 性 の観 点 か ら紹 介 す る.3で は,Chord

の ル ー テ ィ ン グ プ ロ トコル の概 要 に つ い て 述 べ る.4で は,ま ず,代 替 リン ク を 用 い な い 場 合 と用 い る 場 合 の そ れ ぞ れ の 耐 故 障 性 と性 能 に つ い て 解 析 な らび に シ ミュ レー シ ョ ン に よ って 議 論 す る.つ ぎ に,バ ッ ク トラ ッキ ン グを 伴 うル ー テ ィ ン グ の耐 故 障性 と性 能 を シ ミ ュ レー シ ョ ン に よ っ て 見 積 も り,オ ブ ジ ェ ク ト探 索 に お け る効 果 的 な方 策 につ い て 論 ず

る.5で は本 研 究 の結 論 を 述 べ,今 後 の 課 題 につ い て議 論 す る.

、

2関 連研究

こ こ で は,本 研 究 に 関 連 す る研 究 につ い て紹 介 す る.

構造化P2Pネ ッ トワー ク

構 造 化P2Pネ ッ トワー ク は各 ノー ドの 持 つ リン クが 構 造 的 に決 定 さ れ るオ ー バ レイ ネ ッ トワー ク で あ る.中 で も分 散 ハ ッシ ュテ ー ブル を 利 用 した も のが 多 く,様 々 な手 法 が 提 案 さ れ て い る.構 造 化P2Pネ ッ トワ ー クは拡 張 性 が 高 く,多 数 の ノー ドが 参 加 す る分 散 フ ァ イ ル 共 有 シ ス テ ム な どに 多 く利 用 され て い る.

分 散 ハ ッシ ュテ ー ブル は,多 数 の ノー ドで 分 散 して オ ブ ジ ェ ク トを 管 理 す る た め の 手 法 で あ る.分 散 ハ ッ シ ュテ ー ブ ル で は,ノ ー ドとオ ブ ジェ ク トは同 じハ ッシ ュ関 数 か ら 皿)が 与 え られ る.こ の ハ ッ シ ュ値 は 重 複 す る こ とは な い とさ れ,ノ ー ド とオ ブ ジ ェ ク トは 同 じ ハ ッ シ ュ値 空 間 に一 意 のIDを 持 つ こ とに な る.こ のIDを 利 用 した特 定 の 規 則 性 を も っ て ノ ー ド同士 が ハ ッ シ ュ空 間 を 分 担 し,担 当 空 間 に 配 置 さ れ るオ ブ ジ ェ ク トの提 供 者 とな る.担 当範 囲 を 定 め る手 法 に よ って さ まざ ま な 実装 が存 在 す る.例 え ば,オ ブ ジ ェ ク トは .そ の オ ブ ジ ェ ク トのIDに 一 番 近 いIDを 持 つ ノ ー ドが 管 理 す る と した とき,つ ぎ の表 の

よ うな 例 が 考 え られ る.

表2.1:分 散 ハ ッ シ ュ テ ー ブ ル の 例.

ノ ー ド名 ノ ー ドのID

ノ ー ドB 1 2 Data‑C 192.XX.XX.XXX

3 Data‑A 133.XXX.XX.XX

ノ ー ドG 6 8 Data‑F 111.XX.XXX.XX

ノ ー ド1 12 10 Data‑Y 98.XX.XX.XXX

15 Data‑J 155.XX.XX.XXX

ご の 例 で は,2と い うIDを 持 つ オ ブ ジ ェ ク トData‑Cと,3を 持 つData‑Aが,一 番 近 いID1を 持 つ ノー ドBに 配 置 され て い る.

ノー ド間 の 通 信 は,各 ノー ドが持 つ経 路 表 と呼 ばれ る リン ク集 合 を利 用 して お こ な われ る.数 千 か ら数 百 万 ノ ー ドに な る大 規 模 な分 散 ネ ッ トワー ク を考 慮 した とき,各 ノー ドが ネ ッ トワ ー一ク上 の 全 て の ノ ー ドのIPア ドレス を管 理 す る こ とは 現 実 的 で は な い.こ の た め,各 ノ ー ドの経 路 表 は必 要 最 低 限 の リ ン クで 構 成 され,複 数 の ノー ドの 経 路 表 を た どっ

てい く こ とで,ど の ノ ー ドか らで も 目的 の ノー ドと通 信 で き る よ うに設 計 さ れ る.

さ き ぼ どの例 で ノー ドGが ノー ドBの ア ドレス とそ れ に 伴 う担 当 範 囲 を経 路表 に持 っ て い て,ノ ー ド1は な か っ た場 合 を 考 え る.ノ ー ド1が オ ブ ジ ェ ク トData‑Aを 要 求 す る とき,ハ ッシ ュ関 数 か らData‑AのID3が わか る.し か し,ID3を 管 理 して い る ノー ド

を1は 知 らな い た め,1は 自分 の持 っ て い る リ ン クで 知 っ て い そ うな ノー ドに 対 して この 要 求 を転 送 す る.要 求 を受 け取 っ た ノー ドがGだ っ た と して,GはID3を 管 理 して い る ノー ドがBだ とわ か って い る の で,こ の要 求 を さ らにBぺ 転 送 す る.こ の よ うに複 数 の ノー ドを 経 由 す る こ とで,小 さ い経 路 表 で も要 求 を達 成 で き る よ うに さ れ て い る.

近年発表 ざれ た構 造化P2Pネ ッ トワークに関す る研究 構 造 化P2Pネ ッ トワー ク.の耐 故 障 性 に 関 す る 研 究 と して,

・ レ プ リ ケ ー シ ョ ン

・ 負 荷 分 散

・ 弾 力 性

等 に着 目 した もの が あ る.対 象 とす る ア プ リケ ー シ ョ ンに よ っ て;要 求 され る耐 故 障 性 が 変 わ っ て くる た め,シ ス テ ム設 計 者 は 明確 に耐 故 障性 の 基 準 を意 識 す る必 要 が あ る.

複数個の同じレプリカをグループで管理する手法

P2Pネ ッ トワー ク シ ス テ ムで は全 て の ノー ドが サー バ と して振 る舞 う こ とが で き る た め, ク ライ ア ン ト ・サー バ 型 ネ ッ トワー ク に見 られ るサ ーバ の故 障等 に よ る シ ン グル ポイ ン ト故 障 に対 す る 耐 性 を 備 え て い る.し か しな が ら,あ る オ ブ ジ ェ ク トを 管 理 す る ノ ー ドが た だ 一 つ だ った 場 合,ノ ー ド故 障 に よ る シ ス テ ム ダ ウ ンは起 こ らな い と して も,そ の ノー ドの 管 理 す る オ ブ ジ ェ ク トの取 得 は失 敗 して しま う こ とに な る.こ の とき,オ ブ ジ ェ ク トの レ プ リカ を 別 の ノ ー ドに配 置 して お け ば,レ プ リカ に よ って 要 求 を満 た せ る場 合 が あ る.ま た,レ プ リカ を 複 数 配 置 す れ ば,よ り高 い 耐故 障性 が 得 られ る.

多 くのP2Pネ ッ トワー ク で は,ノ ー ドの 参加 ・離 脱 は頻 繁 に発 生 す る と され て い る.こ う した状 況 で も安 定 して必 要 な数 の レプ リカ を保 持 す る た め に,複 数 の レ プ リカ を グル ー プ と して ま とめ て 管 理 す る手 法 が提 案 さ れ て い る.

Dobreら は,階 層 的 な グル ー プ構 造 を 持 つ オ ー バ レイ ネ ッ トワ ー ク構 造 を提 案 して い る [2].提 案 さ れ るDistHashと 呼 ば れ る オー バ レイ ネ ッ トワー ク は,分 散 ハ ッ シ ュテ ー ブル を基 本 と して い る.Dist且ashは 図2.1に 示 され る よ うに,エ ー ジ ェ ン トと呼 ば れ る ピ ァ とRエ ー ジ ェ ン トと呼 ば れ る ス ー パ ー ピ アか ら成 る階 層 的 ネ ッ トワ ー ク を 持 つ.各 工 一 ジ ェ ン トは そ れ ぞ れ 一 つ のRエ ー ジ ェ ン トを 中心 とす る ク ラ ス タ に属 して い る.Rエ ー ジ ェ ン トは 自 クラ ス タ 内の エ ー ジ ェ ン トの持 つ オ ブ ジ ェ ク トの 情 報 を 管 理 す る メ タデ ー タ カ タ ロ グ を所 持 して い る.各Rエ ー ジ ェ ン トは そ れ ぞ れ 全 て のRエ ー ジ ェ ン トとの リ ン クを 保 持 して お り,各 工 一 ジ ェン トはRエ ー ジ ェ ン トを 通 して全 て の エ ー ジ ェ ン トと通 信 出 来 る よ うにな って い る.DistHashで は 各 工一 ジ ェ ン トは それ ぞれ オ リジ ナ ル なオ ブ ジ ェ

嚢1

A

鰹 麟翻 躍'

RAgentslayer

た'

丈、 り

■1'

熱

ピ)ハ!

Agent

臥( Agentslayer

図2.1:DistHashの 構 成.

ク トとい くつ か の レ プ リカ を保 持 す る と され る.故 障 を検 出 す る と,そ の エ ー ジ ェ ン トが 保 持 して い た オ ブ ジ ェ ク トと レプ リカ を補 完 す る よ うに クラ ス タ 内 で レプ リケ ー シ ョン が 行 わ れ る.こ れ に よ って,管 理 さ れ て い る レプ リ カ は常 に 一 定 の数 が存 在 す る こ とに な る.

P2Pネ ッ トワー ク シス テ ム は,特 に純 粋 なP2Pの 場 合,管 理 者 を必 要 と しな い.こ れ は裏 を 返 せ ば,シ ス テ ム は管 理 者 の介 入 な しに稼 働 し続 け る こ とを求 め られ て い る こ とに な る.こ の た め,要 求 され る性 能 と耐 故 障性 を備 え なが らも,ノ ー ドの 頻 繁 な 参 加 ・離 脱 に 自動 的 に対 応 す るた め の 仕 組 み が提 案 され て い る.

Costacheら は 自動 的 に レプ リカ グル ー プ内 の一 貫 性 低 下 を 検 出 し,グ ル ー プ の再 構 成 を お こな う シ ス テ ム を提 案 して い る[3】.Costacheら の提 案 す るSemiasは,全 て の 構 造 化 P2Pオ ー バ レイ に 適 用 で き る と さ れ る.Semiasの 想 定 す る分 散 オ ブ ジ ェ ク トは,ア プ リ ケ ー シ ョ ンの 一 つ の プ ロセ ス と して説 明 され て い る.図2.2の よ うに,一 つ の プ ロセ ス に 対 して複 数 個 の レプ リカ を 用 意 して グル ー プを 構 成 し,可 用 性 を高 め て い る.グ ル ー プ は

☆process

replicane

図2.2:Semiasの レ プ リ カ グ ル ー プ 管 理 の 例.

近 いIDを 持 つ も の で構 成 され てい る.P2Pネ ッ トワー クで は,/一 ドの参 加 ・離 脱 に よ っ て グル ー プ 内 の レプ リカ 数 が 変 動 す る.提 案 手 法 は,こ の レプ リカ 数 の 変 動 に対 して 自動 的 に グル ー プ 内の レプ リカ を 再 構 成 し,常 にあ る一 定 の レプ リ カを 保 持 す る こ とが で き る と して い る(図2.3).特 に,レ プ リ カ グル0プ の再 構 成 を 行 って い る間 で も一 貫性 を 維 持 しつ つ プ ロ セ ス の 実 行 が で き,ユ ー ザ が 再 構 成 を 意識 せ ず に 使 用 で き る事 が強 み で あ る と

detectfailure

図2。3:Semiasの レ プ リ カ グ ル ー プ 再 構 成 の 例.

して い る.ま た,レ プ リ カ グル0プ の 再 構 成 を 過 剰 に行 っ て は,通 信 コ ス トが か か りす ぎ る こ とが 問題 とさ れ る.Semiasで は再 構 成 を 必要 最 低 限 の 回 数 で 抑 え る た め,つ ぎ の よ う に工 夫 が な さ れ て い る.Costacheら は,オ ー バ レイ上 の ノ ー ドの 変 化 の 全 て に対 応 す る こ とは せ ず,セ ー フテ ィ コ ンデ ィシ ョ ン と呼 ば れ る 状 態 を 定 義 して お き,こ れ か ら外 れ る ほ どの 変 化 が あ っ た 時 の み,再 構 成 を 行 う と して い る.こ れ に よ って,コ ス トを 抑 え な が ら 一 定 数 の レ プ リカ を保 持 す る こ とが で き る とされ る.

また,Al‑Shishtawyら は,レ プ リカを 構 成 す る グル ー プが ハ ッ シ ュ空 間 上 に均 等 に分 布 ・ さ れ る手 法 を提 案 して い る[4].図2.4の よ うに,グ ル ー プ 内 の レプ リカ の 配 置 は コ ン フ ィ ギ ュ レー シ ョツ と呼 ば れ る情 報 に よ って 管 理 され,一 定 の ス レ ッ シ ョル ドを超 え る大 幅 な

グル ー プ 内 ノー ドの変 化 が 観 測 され る と,自 動 的 に 一 定 の レプ リ カ数 を保 つ よ うに再 構 成 さ れ る.対 称 レプ リケ ー シ ョ ン と呼 ば れ る手 法 に よ って,レ プ リ カ はハ ッシ ュ空 間上 に均

key:2

95 34

symmetricreplication

図2.4:Al‑Shishtawyら の 提 案 す る レ プ リ カ グ ル ー プ 管 理 手 法 の 例.

等 に配 置 され,ル ー テ ィ ン グ の 負 荷 が 分 散 さ れ る よ うに な っ て い る.

動的な負荷分散

レプ リ カを 用 い た 手 法 は,負 荷 分 散 に も利 用 され て い る.構 造 化P2Pネ ッ トワ ー ク は, オー バ レイ の 構 造 に よ っ て どの オ ブ ジ ェ ク トが どの ノー ドへ 配 置 さ れ るか が 定 め られ て い る.多 くの 場 合 に,一 度 定 め られ た オ ブ ジ ェ ク トは担 当 ノー ドが離 脱 す る まで 別 の ノー ド へ 配 置 さ れ る こ とは な い.こ の た め オ ブ ジ ェ ク トの人 気 に偏 りが生 じる と,特 定 の ノー ド

に負 荷 が 集 中 す る可 能 性 が あ る.

Pitouraら は,複 階 層 リ ン グ構 造 に よ る 負 荷 分 散 手 法 を 提 案 して い る 【5].提案 さ れ る Saturnは,全 て の 分 散 ハ ッシ ュテ ー ブ ル を用 い たオ ー バ レイ ネ ッ トワー ク に適 用 で き る と され て い る.Saturnは 一 つ の 基 本 リ ン グ と,複 数 の 仮 想 リ ング を持 ち,・最 下 層 の基 本 リ ン グ を リン グ1と す る と,リ ン グ1は そ の ま ま対 象 とな るオ0バ レイ で あ る.他 の層 は,基 本 リン グ と異 な るハ ッ シ ュ関 数 に よっ て形 成 さ れ る,Saturnの 構 造 を 図2.5に 示 す.同 じ

930 1030 1130 1230 1500 14720

ノ のt=83?ま きコホゆ ノノ く  ぐ まゑ む

尉 函 工

甲

・

147200L・ 盛頃o

,/認;;「i‑一 一一 一̲一 ＼ 一

冨 ト ㎞ 「 。 「 鎗 フ 召ea {蜘9㈱,

馴448＼ 、:郷 §7難y

＼ Ring2

コ    1930 2000 2330

X2416 侮 鵤4}＼ ,

iRingt

ご翻 弾 αノ

響!圏 4912

1230 150fl 1860

図2.5:Satumの 構 造

ノー ド集 合 に よ る別 種 の仮 想 ネ ッ トワー ク とされ る.リ ン グ上 の ピ ア の持 つ 値 へ の ア クセ ス 数 が 高 ま り,許 容 され る最 大 ア クセ ス数 を 上 回 る と,そ の値 は ホ ッ ト状 態 と見 な され る.

ホ ッ ト状 態 の値 は ア ク セ ス 負 荷 分 散 の ため に垂 直 レ プ リケ ー シ ョンが お こな わ れ る.垂 直 レ プ リケー シ ョ ン は,ホ ッ ト状 態 の 値 を 別 の リ ン グの ハ ッ シ ュ関 数 に よ っ て決 ま る ノー ド へ と複 製 す る.こ れ に よ って,レ プ リカが 配 置 さ れ る ノー ドが ラ ン ダ ム に決 定 され る た め, 効 果 的 に負 荷 分 散 が 行 え る と され て い る.

ノー ド故障によるリンクの欠損に対する弾力性

近 年 注 目 さ れ て い る耐 故 障 性 の指 標 に,弾 力 性(レ ジ リエ ン ス)が 挙 げ られ る.こ れ は, ノ ー ドの 持 つ リン クの 欠 損 に 対 して,柔 軟 に 回 復 す る こ とが で き る能 力 とさ れ る.弾 力 性 の 高 い シス テ ム で あ る ほ ど,致 命 的 な ネ ッ トワー クの 分 割 か ら リ ン ク の 回復 が お こ な え る

と され る.

Liら は,ノ ー ドの 参 加 ・離 脱 が 激 しい 状 態 に対 す る高 い 弾 力 性 を 備 え たP2Pデ ー タ散 布 プ ロ トコル を 提 案 してい る[6].通 常,非 構 造 化 オ ー バ レイ に よ るデ ー タ散 布 は,全 て の ノ ー ドヘ デ ー タ が到 達 す る保 証 が な され な い.こ れ は,非 構 造 化 オ ー バ レイ で は各 ノー ド の リ ン クの 持 ち方 が構 造 的 で な い ため,あ る ノー ドか らた ど り着 くこ とが で き な い ノー ド が 存 在 す る こ とが あ る ため で あ る.こ れ に対 して,提 案 さ れ るCRPは,構 造 化 オ ー バ レイ を 利 用 す る こ とで完 全 な デー タ散 布 をお こな う こ とが で き る とされ る.CRPで は,基 本 の ネ ッ トワー ク と して 図6(a)の よ うなChordを 用 い た ネ ッ トワー クを 構 築 す る.こ の ネ ッ

トワー ク は後 任 ノ ー ドリス ト と呼 ばれ る リ ン ク集 合 に よ っ て,高 い 確 率 で 多数 の ノー ドの 同 時 故 障 に よ るネ ッ トワー クの分 割 を 回 避 で き る とされ てい る.こ のChordネ ッ トワー ク に よ って得 られ る リン ク を用 い て,デ ー タ散 布 に 使 用 す る た め の 図7(a)の よ うな スパ ニ ン グ ツ リー を 構 成 して い る.こ れ に よ って,完 全 にデ ー タ散 布 を 行 う こ とが で き,ノ ー ドの 参 加 ・離 脱 に よ って ス パ ニ ン グ ツ リー を 再 構 成 す る必 要 が 生 じた場 合 で も,Chordネ ッ ト

ワー クを 活 用 す る こ とで 迅 速 に ス パ ニ ン グ ツ リー を 回 復 で き る と して い る.

Chordは 後 任 ノー ドリス トを用 い る こ とで,ノ ー ド故 障 に よ る ネ ッ トワ ー クの 分 割 に対 す る耐 故 障 性 を高 め て い る.す な わ ち,後 任 ノー ドリス トの うち 一 つ で もノ ー ドが 生 存 し て い れ ば,全 体 と して のChordリ ン グ は途 切 れ て お らず,ど の ノー ドか らで も全 て の ノー

ドと通 信 で き る とさ れ る.

このChordの 接 続 性 につ い て,Yaoら は後 任 ノー ドリス トと安 定 化 プ ロ トコ ル に着 目 した研 究 を報 告 して い る[7].Yaoら は,安 定 化 プ ロ トコル が 実 行 され る と,後 任 ノー ドリ ス ト内 の 故 障 ノー ドは全 て 生 存 ノー ドに 置 き 換 え られ る と仮 定 して,安 定 化 プ ロ トコル の 実行 間 隔 とChordの 接 続 性 保 持 の 関係 を 考察 してい る.Yaoら は ノー ド故 障 に つ い て,静 的 故 障 と動 的 故 障 を考 慮 して い る.静 的 故 障 で は シス テ ム の稼 働 時 間 に よ らず,各 ノー ド が 一 定 の 確 率 で故 障 した場 合 を考 え て い る.動 的 故 障 で は各 ノー ドに 確 率 的 な 生 存 時 間 を 設 定 し,故 障 状 態 が 稼 働 時 間 に よ って 変 化 す る.そ れ ぞ れ につ い て,各 ノー ドの 持 つ 後 任 ノー ドリス ト内の 全 て の ノ ー ドが 故 障 して い る場 合 を ノ ー ド孤 立 と定 義 し,ノ ー ド孤 立 が 発 生 す る確 率 を 解 析 的,実 験 的 に 求 め て い る.静 的故 障 を考 慮 した場 合 は,nを ノー ド数, pを 故 障 率,rを 後 任 ノ0ド リス トの 大 き さ と して,e‑n(1‑P)prの 確 率 で ノ ー ド孤 立 が 起 こ る と して い る.動 的 故 障 は マ ル コフ連 鎖 を 用 い て モ デ ル 化 し,解 析 と シ ミ ュ レー シ ョンを 行 っ てい る.結 果 と して,安 定 化 プ ロ トコル を な るべ く短 い 一 定 の 間 隔 で 実 行 す る こ とで, ネ ッ トワ ー クの 分 割 を 最 も効 率 的 に抑 制 で き る と して い る.

Yaoら は,Chordの フ ィ ン ガテ ー ブル は ル ー テ ィ ン グの効 率 化 に使 用 さ れ る も の で,耐 故 障 性 に つ い て は後 任 ノ ー ド リス トに注 目す れ ば よ い と して い る.し か しな が ら,Chord

の ル ー テ ィ ン グ に お い て,次 に ホ ッ プす るべ き ノー ドが 故 障 して い た場 合 に フ ィ ン ガテ ー ブ ル の 別 の ノ ー ドを代 替 リ ン ク と して使 う とき はそ の 限 りで ない.ネ ッ トワー クの 分 割 が 発 生 して後 任 ノー ドリス トに よる到 達 が 不 可能 とされ る場 合 で も,フ ィ ン ガテ ー ブル に よ っ て 分 割 さ れ た 空 間 を超 え て た ど り着 け る場 合 が あ る ため で あ る.

本 研 究 で は,こ の フ ィ ンガ テ ー ブル に よ る耐 故 障 性 に注 目 し,数 値 的,実 験 的 に 評 価 し て い く.

A(3)

1,"一 、、 、、」

{).3

IC(3)

G{3)

1、

σD(2)

F(3)＼ ＼

1、 、、̲̲,'4'監 E(4)

(a)

図2.6:CRPのChordを 利 用 し た ネ ッ トワ ー"の 例.

H

O,3 0.8/¥0.3

6ECB

O.70。5

D''''"AF

(a)

図2.7:CRPの ス パ ニ ン グ ツ リ ー の 例.

3Chordの 概 要

こ こ で は,Chordの 概 要 に つ い て 説 明 す る.

Chordの 基 本構造

Chord[1】 は 分 散 ハ ッ シ ュ テ ー ブ ル を 基 本 と し て い る.

ノ0ド と オ ブ ジ ェ ク トは そ れ ぞ れ,SHA‑1の よ う な ハ ッ シ ュ 関 数 に よ っ てIDが 与 え ら れ る.こ のIDに よ っ て ノ ー ドと オ ブ ジ ェ ク トは 同 じハ ッ シ ュ 空 間 上 に 位 置 づ け られ る.図 3.1の よ う に,Chordの ハ ッ シ ュ 空 間 は 閉 じ た リ ン グ 状 で あ り,ハ ッ シ ュ 関 数 がSHA‑1な らIDは0か ら2160‑1の 値 を 取 る.

O predeccessor

7

2m̲1./ ..,successor

responsible

図3.1:Chordの 構 造 の 例.

各 ノ ー ドは そ れ ぞ れ,自 身 のIDよ り大 き い 直 近 の ノ ー ド,"後 任 ノ ー ド(successor)"

と,小 さ いIDの 直 近 ノ ー ド,"前 任 ノ ー ド(predeccessor)"と の リ ン ク を 持 っ て い る.各 ノ ー ドは 前 任 ノ ー ドのIDか ら 自 身 のIDま で を 担 当 し,そ の 範 囲 のIDを 持 つ オ ブ ジ ェ ク

トを 管 理 す る.

ノ ー ド が オ ブ ジ ェ ク トを 要 求 す る こ とを ル ッ ク ア ッ プ と 呼 ぶ.ル ッ ク ア ッ プ を 行 う ノ ー

ドは 自 身 の 持 つ リ ン ク を 使 用 し て,自 身 のIDと 目 的 オ ブ ジ ェ ク トのIDを 記 し た ク エ リ

を 転 送 す る.ク エ リを 受 け 取 っ た ノ ー ドは 自 身 の 持 つ リ ン ク を 使 用 し,ク エ リ を さ ら に 目

的 ノ ー ドへ 向 け て 転 送 し て い く.こ う し て 転 送 が 繰 り返 さ れ る こ と で,オ ブ ジ ェ ク トを 管

理 す る ノー ドへ の リ ン クを持 た な くて も所 望 の オ ブ ジ ェ ク トを 要 求 す る こ とが で き る(図' 3.2).

responsible

1

0bject

object(address)

startlookup

routing

図3.2:Chordの ル ー テ ィ ン グ の 例.

始 点 ノー ドか ら目的 ノー ドま で クエ リを転 送 して い く流 れ をル ー テ ィ ン グ と呼 ぶ.Chord の ル ー テ ィ ン グ は時 計 回 りだ け で お こな わ れ る.

フ ィ ン ガ テ ー ブル

Chordで は ル ー テ ィ ン グを 効 率 化 す るた め に,そ れ ぞ れ の ノー ドが後 任 ノー一ドへ の リ ン クに加 えて フ ィン ガテ ー ブ ル と呼 ばれ る リ ンク集 合 を持 って い る.ノ ー ドnの フ ィ ンガ テ ー ブ ル の2(1≦2≦m)番 目 のエ ン トリは,nのIDか ら2i‑1先 のIDを 担 当 す る ノー ドへ の リ ン ク とな る(図3.3).

ノ ー ド数Nの ネ ッ トワー ク にお い て,各 ノー ドは お よそlogeN本 の リ ン クを持 つ こ とに な る.フ ィ ン ガテ ー ブル を 利 用 した ル ー テ ィ ン グで は,各 ノー ドは 自身 の持 つ リ ン ク の う ち 目的 のIDを 超 え な い 内 で最 大 の もの を使 用 して クエ リを転 送 して い く.再 帰 的 に転 送 を繰 り返 し,目 的IDを 担 当す る ノー ドの前 任 ノー ドへ と到 達 す る.目 的 ノー ドの前 任 ノ ー

ドは,目 的 ノー ドと後 任 ノー ドの リン ク で繋 が っ て い る ため 目 的 ノー ドの担 当す るID区 間 を知 って い る.そ の た め,目 的IDを 担 当す る ノー ドが 自身 の後 任 ノー ドで あ る 目的 ノ ー

ドで あ る とわ か る の で,目 的 ノ ー ドヘ クエ リを転 送 す る こ とが で き る.図3.4に,フ ィ ン ガ テー ブ ル を 利 用 した ル ー テ ィ ン グの例 を示 す.ノ ー ド3がID58の オ ブ ジ ェ ク トを 要 求 す る場 合 を 考 え て い る.ま ず,フ ィ ン ガ テー ブ ル に リン クの あ る ノー ドの 内で,目 的 のID

を 超 え な い 最 大 の ノー ド37ヘ ク エ リを 転 送 す る.ク エ リを 受 け取 っ た ノー一ド37は,同 様 に ノー ド53へ と クエ リを転 送 す る.さ らに ノー ド53か らノー ド55へ と転 送 さ れ る.

55は ノー一ド59が サ クセ ッサ で あ る こ とか ら,目 的 オ ブ ジ ェ ク トのIDを 管 理 す る の は59 で あ る こ とを把 握 して い る た め,ク エ リを59へ と転 送 す る.こ のル ー テ ィ ン グの 途 中 で, ノ ー ド53は59へ の リ ン クを 持 って い る が,目 的オ ブ ジ ェ ク トを 管理 す るノー ドか ど うか 判 断 で き な い た め59へ 転 送 され る こ とが な か った こ とに 注 意 す る必 要 が あ る.

フ ィ ン ガテ ー ブ ル を 利 用 して ル ー テ ィ ン グを行 う こ とで,Nノ ー ドのネ ッ トワー クに お け る クエ リの転 送 回 数,"ホ ップ 数"は0(logN)と な る.

参加と離脱 ・故障

Chordネ ッ トワー クへ の 参 加 は,す で に ネ ッ トワー クに 参 加 して い る ノー ドに何 らか の 方 法 で 通 信 を 行 い,自 身 のIDの ル ッ ク ア ップ を 依 頼 す る こ とで行 わ れ る.こ れ は,ア プ リケ ー シ ョン の提 供 者 が 常 に起 動 さ せ て お くコ ン タ ク トノー ドを用 意 す る こ と等 で実 現 さ れ る.

ノ ー ド ゴが ネ ッ トワ ー クへ 参 加 す る場 合 を例 に説 明 す る.参 加 ノ ー ド(ゴとす る)は 自身 のIDを ル ッ クア ッ プす る こ とで 後 任 ノー ドとな る ノー ド(sと す る)を 見 つ け て リ ン ク を 確 立 し,sか ら担 当 範 囲 の オ ブ ジ ェ ク トを 受 け取 っ て ネ ッ トワー クへ 参 加 す る.し か しそ の ま ま で は ゴの 前 任 ノ ー ド(pと す る)へ の リ ン ク は存 在 せ ず,pの 後 任 ノー ドへ の リ ン ク は ゴで はな く8の ま ま とな って い る.こ の ためChordに お け る ノー ドの参 加 は リン クの一 貫 性 を 低 下 さ せ る.

Chordで は離 脱 と故 障 は 同 等 に扱 わ れ る.こ こでい う故 障 とは永 久 故 障 で あ り,故 障 し た ノ ー ドは全 て の リ ン クを 失 い復 旧 しな い とす る.離 脱 ・故 障 ノー ドに 関 す る リ ン ク は有 効 で な くな り,担 当範 囲 は 他 の ノー ドが 代 わ りに 担 当 す る必 要 が あ る.

安定化プロ トコル

これ らの 問 題 に対 処 す る た め に,Chordで は安 定 化 プ ロ トコ ル が 定 期 的 に実 行 され て い る.安 定 化 プ ロ トコル に よ っ て,ネ ッ トワー ク上 の リン ク の一 貫 性 を 回 復 す る こ とが で き る.安 定 化 プ ロ トコル に は後 任 ノー ドの安 定 化 プ ロ トコル と,フ ィ ンガ テ ー ブ ル の安 定 化 プ ロ トコ ル が あ る.後 任 ノー ドの安 定 化 プロ トコル で は,図3.5の よ うに,安 定 化 を 行 う ノー ドが 自身 の後 任 ノー ドに対 して,後 任 ノー ドの前 任 ノー ドのIDを 尋 ね る.

後 任 ノ ー ドの前 任 ノー ドが 自身 のIDと 一 致 す れ ば,変 化 が な か っ た こ とが 確 認 さ れ る.

図3.6の よ うに,新 しいIDが 返 答 さ れ た場 合 は,そ のIDを 現 在 の 正 しい 後 任 ノー ドと して 更 新 す る(図3.7).

フ ィ ン ガテ ー ブル の安 定 化 プ ロ トコル で は,構 築 した 時 と同様 に ル ッ ク ア ップ を 行 う こ とで 正 しい リ ン クを 回復 してい る.Chordは これ らの安 定 化 プ ロ トコル を 定 期 的 に繰 り返 す こ とで,リ ン ク の一 貫 性 を 保 ち,ノ0ド の 参 加,離 脱 に対 応 して い る.

後 任 ノ ー ドリス ト

後 任 ノー ドが 故 障 して い る場 合,安 定 化 プ ロ トコル が行 え な くな っ て しま う.こ の 問題 に対 して,後 任 ノー ド方 向 へ の 連 続 す る複 数 個 の ノ ー ドヘ リン クを 持 つ こ とで 対 応 す る方 法 が 示 さ れ て い る.こ の リ ン ク集 合 を 後任 ノ ー ドリス トと呼 ぶ.後 任 ノー ドが 故 障 して い た場 合,故 障 して い な い ノ ー ドで 一 番 近 い 位 置 に あ る もの を後 任 ノー ドに置 き 換 え る こ と が で き る.

フ ィ ンガ テ ー ブル と同様 に,後 任 ノー ドリス トに 対 して も一 定 間 隔 で安 定 化 プ ロ トコ ル が実 行 され,リ ン ク の 一貫 性 回 復 が 行 わ れ る.

ま た,後 任 ノー ドリス トは通 常 のル ー テ ィ ン グ に も使 用 す る こ とが で き,追 加 的 な フ ィ ンガ テ ー ブ ル と して利 用 さ れ る.

本研 究の対 象 とす るChordの モデル

本 研 究 で は,安 定 化 プ ロ トコル に よ る リ ン クの 一 貫 性 回復 が完 全 で な い 過 渡 的 な 状 態 を 考 え る.ま た,参 加 ノ ー ドに よ る一 貫 性 の 低 下 は考 慮 せ ず,故 障 ノ ー ドに よ る 影 響 の み 考 慮 す る.故 障 は一 定 の確 率 で ラ ンダ ム に 発 生 す る こ と とす る.故 障 が 発 生 した ノ ー ドは 回 復 す る こ とはな く,少 な く とも全 ての 通信 機 能 を 失 い,そ の ノ ー ドが 管 理 して い た オ ブ ジ ェ

ク トは取 得 で きな くな る とす る.ル ー テ ィ ン グ中,故 障 は十 分 短 い 時 間 内 に検 出 で き る と す る.探 索 に か か る時 間対 して,安 定 化 や 故 障 が 発 生 す る間 隔 は 十 分 長 い と し,i探 索 開 始 時点 か ら終 了 ま で全 て の ノー ドの状 態 は変 化 しな い とす る.ま た,本 研 究 で はChordの 分 散 ハ ッシ ュテ ー ブル に よ る 複数 の リ ン クに 基 づ く耐 故 障 性 を 明 らか に す る た め,各 ノー ド が後 任 ノ ー ドリス トを持 た な い場 合 に つ い て考 え る.

FingerTableforN3

o

N37

q 35

ON3

45

・ 鋸7噂b§N9

噂、

嚇

、 馬

ら

i=1

3+2あ1=4

i=2 3+2洞=5 N9

i=3

3+2レ1=7

i=4 3+2i‑1=11 N14 z=5 3+2ム1ニ19 N23 t=6 3+2ム1=35 N37

.

1

N14

噺

＼

覧 覧

＼ /'亀19

∫

N23

図3.3:フ ィ ン ガ テ ー ブ ル の 例.

responsiblefor58 58N59

N55successor FingerTableforN53

團

lookup(58) ON3

Ng FingerTableforN3

N45

N42 N40 FingerTableforN37

N37N40 N40

N42 N45 N53 N9

図3.4:フ ィ ン ガ テ0ブ ル を 用 い たChordの ル ー テ ィ ン グ 例.

Aaskpredeccessor

AB

図3.5:ノ ー ドの 参 加 が な い 場 合 の 安 定 化 プ ロ ト コ ル の 例,

4 1 N 3 2 ‑ M 四

askpredeccessor joinnodeCB

図3.6:ノ ー ドの参 加 が あ っ た場 合 の 安 定 化 プ ロ トコル の例.

updatesuccessor C

B

図3.7:後 任 ノ ー ドを 更 新.

4Chordの 耐 故 障性

こ こで は,Chordの フ ィ ンガ テ ー ブ ル に よ る耐 故 障 性 に つ い て 定 量 的 に論 じる.4.1で は,ハ ッシ ュテ ー ブル の リ ンク先 の ノ ー ドが故 障 した場 合 に 代 替 リン クを 用 い な い 場合 に つ い て,探 索 成功 確 率 と探 索終 了 ま で のホ ップ数 を考 察 す る.4.2で は,ハ ッシ ュテ ー ブ ル の リ ン ク先 の ノ0ド が 故 障 した場 合 に 代替 リ ン クを 用 い る場 合 につ い て,探 索 成功 確 率 と 探 索 終 了 ま で の ホ ップ 数 を考 察 す る.4.3で は,ル ー テ ィ ン グ の最 中 に 自身 の 持 つ リ ン ク が全 て 有 効 で な くな った とき,1ホ ッ プ前 の ノー ドへ 戻 って 次 善 の リ ン ク を 使 用 す る こ と が で き る ル ー テ ィ ン グ につ い て考 察 す る.

こ こで い う探 索 の 成 功 とは,目 的 ノ ー ドの前 任 ノー ドに ホ ッ プ で き,尚 且 つ 目的 ノー ド の前 任 ノ ー ドと 目的 ノー ドが故 障 して い な い こ と とす る.

4.1代 替 リンクを用 いない場合

ま ず,ハ ッ シ ュ テ ー ブ ル の リ ン ク先 の ノー ドが故 障 した と き に代 替 リ ン ク を 用 い な い 場 合 に つ い て 考 察 す る.

代 替 リン ク を 用 い な い ル ー テ ィ ング で は,図4.1に 示 す よ うに,次 に選 ぶ べ き ホ ッ プ先 が故 障 して い た 場 合 に探 索 失 敗 とな る.

FingerTablefdrN3

58

responsiblefor58

N59

lookup(58)

N9 N9 N9 N14 N23 N37

N9 N55

N53

unsuccess

N14

N45

N42 N40

FingerTableforN37

N37N40 N40

N42 N45 'N9N53

図4.1:代 替 リ ン ク を 用 い な いChordの ル ー テ ィ ン グ 例.

図4.2は,総 ノ ー ド数N=100,1000,10000,100000に つ い て,ノ ー ド故 障 率P=0.0〜

0.9に 対 す る 探 索 成 功 確 率 を シ ミ ュ レ ー シ ョ ン に よ っ て 求 め た 結 果 を 示 し て い る.明 ら か

a 三 8 = 弓 8 り ∪ コ ご o ⊆ o 石 6 と

1

o.s

0.6

0.4

0.2

N=100‑+‑

N=1000‑一 一×一一一 N=10000

N=100000・ ・ ・ …f‑・・ 一 …

0

00.10.20.30.40.50.60.70.80.9

failurerate

図4.2:代 替 リ ン ク を 用 い な いChordのi探 索 成 功 確 率.

に,総 ノ ー ド数 が 増 加 す る ほ ど全 体 に 探 索 成 功 確 率 が 低 下 し て い る こ と が わ か る.

探 索 に 成 功 す る ま で の ホ ッ プ 数 をXoと し,そ れ が 確 率 関 数 ノ(勾=Pr{Xo=x}@=

0,1,2,…,「log22V1)に 従 う も の と す れ ば,Chordで はXoの 期 待 値 がE[Xo]=aIOg2N で あ る こ と か ら 国,探 索 成 功 確 率s。 は

flog2Nl

・・ 一 Σ(1‑p)x・ ノ(x)

‑o

N(1‑p)珂Xl‑(1‑P)log2N2

(1)

と 近 似 で き る.

図4.3は,総 ノ ー ド数1V=10000,100000の 場 合 の,解 析 値 と シ ミ ュ レ ー シ ョ ン 結 果 を 比 較 し た も の で あ る.

シ ミ ュ レ ー シ ョ ン結 果 は,こ の 解 析 と良 く一 致 し て い る こ と が 解 る.な お,本 研 究 の シ

ミ ュ レ ー シ ョ ン の 探 索 で は,232サ イ ズ に 相 当 す る ハ ッ シ ュ 空 間 を 模 擬 し て い る.

a 量 8 = 弓 娩8 当 ご ︒ ⊆ ︒ 旧七 認

o:s

0.6

0.4

0.2

N=100000simulation‑一 ←一 一

N=100000so‑一 一一一一一・

N=10000simulation

N=10000sa・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ …

0

00.10.20.30.40.50.60.70.80.9

failurerate

図4.3:代 替 リ ン ク を用 い な いChordの 探 索 成 功 確 率 の解 析 値 とシ ミ ュ レー シ ョン結 果.

次 に,図4.4は,探 索 が 成 功 す る ときの ホ ップ数 の分 布,な らび に失 敗 す る と きの ホ ッ プ数 の 分 布 を シ ミ ュ レー シ ョ ンに よ っ て求 め た結 果 を 示 して い る.

総 ノ ー ド数 はN=1000,各 ノー ドの故 障率 はp=0.2で あ る.探 索 が 成 功 す る とき の ホ ッ プ数 の平 均 は5.18ホ ッズ 失 敗 す る ときの ホ ップ数 の 平均 は1.75ホ ッズ 全 体 の ホ ッ プ数,す な わ ち探 索 が 成 功 また は失 敗 に よ っ て終 了 す るま で の ホ ップ数 の平 均 は2.73ホ ッ プ とな って い る.こ の よ うな分 布 の傾 向 は,他 の総 ノ0ド 数 や,ノ ー ド故 障 率 に お い て も 同様 で あ る.代 替 リ ン クを 用 い な いChordの 全 体 の ホ ップ数 の平 均 につ い て は,以 下 の 定 理 が 成 り立 つ.

定 理1.ハ ッシ ュ突 間 サ イ ズ2皿,総 ノー ド数N,ノ ー ド故 障 率PのChordで は,ノ ー ド 故 障 に つ い て の 代 替 リ ン ク を用 い な い場 合,高 い確 率 で,探 索 に要 す る平 均 ホ ッ プ数 が

1‑p

p{(・ 一 雪)m‐logeN̲(・ 一 弩)m}(2)

と な り,故 障 率Pが0の と き21092Nと な る.

証 明.サ イ ズ2mの ハ ッ シ ュ 空 間 を 探 索 す る と き,オ ブ ジ ェ ク トの ハ ッ シ ュ ・キ ー は 確 率 1

2で 始 点 ノ ー ドの キ ー か ら2m‑1未 満 の 距 離 に あ り,確 率12で2m‑1〜2m‑1の 距 離 に

の⊆O旧θコ﹄旧おいも 250

zoo

150

100

50

0 0

1屡lI failavg=1.75

total avg=2.73succ avg=5.18

一

、

一

一 一

failures

successes

'

一4‑一 一一 一 哺、

,'、

,'、 、

''

' 、

、

ノ 、

一 ノ!

''

!

、 一

、、

、

噂'_! 、

、

'' a‑' ' ''

'' ''

、、、 、

、、 、

、、

、、、

、 、

、、

書 書 聾 、、、囎

z 4 6 8 io

hopcount

図4.4:代 替 リ ン クを 用 い ないChordの 探 索 成功 お よび 失 敗 ま で の ホ ッ プ数 の 分 布.

あ る.2m‑1〜2m‑1の 距 離 に あ る キ ー を 探 索 す る た め の 次 の 起 点 と な る ノ ー ドは,ハ ッ シ ュ ・キ ー2m‑1の 後 任 ノ ー ド と な る.そ の ノ ー ドの ハ ッ シ ュ ・キ ー は 高 い 確 率 で2m‑1と 見 な す こ と が で き る.し た が っ て,ノ ー ドの 故 障 率 がpで あ る こ と に 注 意 す れ ば,2mの ハ ッ シ ュ 空 間 を 探 索 す る た め の 平 均 ホ ッ プ 数H(2m)は,

'

H(2m)‑1H2(2m‑1)+1(・‑p){・+H(2m‑・)}(3)

と再 帰 的 に 記 述 で き る.こ れ を 差 分 方 程 式 と して 解 け ば

p

とな る.こ こで,オ ブ ジ ェ ク トの ハ ッ シ ュ ・キ ー の前 任 ノ ー ド と後 任 ノ ー ドとで は さ まれ るハ ッシ ュ空 間 の サ イ ズ は,高 い 確 率 で,21=2m/Nで あ る こ とか ら,探 索 が ハ ッ シ ュ ・ キ ー の前 任 ノー ドに到 達 す る ま で の期 待 ホ ップ数 はH(2m)‑H(2り とな る.こ れ を整 理 し て式(2)を 得 る.ま た,故 障 率pが0に 近 づ く とき,べ き乗 関 数 の 微 係 数 の 意 味 か ら

H(2m)‑H(2り →1(m‑1)=21・92N(5)

となる.口

4.2代 替 リンクを用 いる場 合

続 い て,ハ ッシ ュテ ー ブ ル の リ ン ク先 の ノ ー ドが故 障 した と きに 代 替 リン クを用 い る場 合 に つ い て考 察 す る.

図4.5の よ うに,次 に 選 ぶ べ き ホ ップ先 が故 障 してい た 場 合,ル ー テ ィ ン グテー ブ ル の 次 善 の ホ ッ プ先 を 選 択 して探 索 を 続 行 す る こ とが で き る.

FingerTableforN3

responsiblefor58

lookupC58)

N55 N53

N45

N42

N59

N40

FingerTableforN37

N37N40 N40

N42fail N45 N53fail 'N9'

N14

図4.5:代 替 リ ン ク を 用 い るChordの ル ー テ ィ ン グ 例.