分散ハッシュテーブル（DHT)コミュのIterative (反復) / Recursive (再帰)

iterative / recurisve {routing, lookup} について。

コメント(9)

最初
全て
最新の40件

論文を書きました。

　首藤一幸, 加藤大志, 門林雄基, 土井祐介:
　"構造化オーバレイにおける反復探索と再帰探索の比較",
　情報処理学会研究報告, 2006-OS-103(-2),
　SWoPP高知2006 (並列/分散/協調処理に関するサマー・ワークショップ),
　2006年 7月 31日 (予定)

PDFファイル (181 KB):
http://www.shudo.net/publications/swopp2006/shudo-SWoPP2006-overlay.pdf

[2] mixiユーザー 07月13日 11:03

これは以前 Overlay Weaver のリリースの時に
仰っていた問題ですよね？関心は大有りなのですが、
今、２０日の横浜での研究会の準備で一杯一杯なので
それが終わったら読みます。

[3] mixiユーザー 07月13日 21:15

ルーティングのアルゴリズム (Chord とか) が同じでも、forwarding の仕方がいくつか iterative と recursive あって、それぞれ違う性質を持ってます。っていう話です。

世の中では iterative/recursive routing って言われることが多いのだけど、今回の論文では反復/再帰探索 (iterative/recursive lookup) と言ってます。

なぜかというと、門林先生に、iterativeかrecursiveか、なのは正しくは routing じゃなくて forwarding だよね、と御指摘を頂いたからです。
でも iterative/recursive forwarding という言い方には違和感があって、今回は lookup となりました。

[4] mixiユーザー 07月14日 23:56

勘違いしてたらすいません。

Ａ　　　　　Ｂ　　　　Ｃ　　　　Ｄ
｜--1->｜　　　　｜　　　　｜
｜　　　　｜--2->｜　　　　｜
｜　　　　｜　　　　｜--3->｜
｜　　　　｜　　　　｜<-4--｜
｜　　　　｜<-5--｜　　　　｜
｜<-6--｜　　　　｜　　　　｜

というふうに request/replyが流れるのはどう分類されるのでしょう？

[5] mixiユーザー 07月15日 00:03

あっ、論文を読んでから質問すべきでした。
再帰（slow）という分類ですね。

それより、この論文、筆者が面々がスゴイ。

[6] mixiユーザー 07月15日 01:40

反省してちゃんと論文読みました。(^^♪
iterativeかrecursiveかでどうして大きな話になるのかな？
と思ってたら、脆弱性にまで話が及んでいて大変勉強になりました。
＃それに意外な結末！

ちょっと気になったのは、ACKの扱い。
「TCPだと内部でACKの処理をしてて対等じゃないので、UDPで比較しよう」
というのは納得なんだけど、そうすると、replyで相手の不通を判断することになる再帰（slow）の場合は、タイムアウトを長めに取る必要が出て不利。
たぶん、UDPを前提にするなら、再帰（slow）でもACKは必要だろうなと思います。

それともう一点。
「転送を受けた次善のノードも故障ノードに対して転送を試みてしまう可能性が高い」というところは意外でした。
ルーティングの過程で故障ノードをまたいでしまえば、その故障ノードには２度と遭わなくてすむと思っていたんですが...

[7] mixiユーザー 07月21日 20:50

> 「転送を受けた次善のノードも故障ノードに対して転送を試みてしまう可能性が高い」というところは意外でした。
> ルーティングの過程で故障ノードをまたいでしまえば、その故障ノードには２度と遭わなくてすむと思っていたんですが...

ここも、もっと議論が要るところかと思います。
またげるのか故障ノードが次ホップ候補に現れ続けるのかは、
次の要因に依るのだろうと考えてます：

　・ルーティングの初めの段階なのか終わり頃なのか
　　終盤だと、故障ノードへの送信試みが繰り返されそう。
　・アルゴリズムの性質

僕自身は、Kademlia (のサブセット) での recursive lookup をしていて、故障ノードへの送信試みが複数ノードで起きてひどい目に遭った経験があります。

[8] mixiユーザー 07月22日 14:17

遅まきながら、大変興味深く拝読しました。

やはり、理論の重要さは言うに及ばず、実際にシミュレーションしてみるのが一番大切なんでしょうね。今度のDHT勉強会までに、一度Overlay Weaverをいじっておかないと（笑。

[9] mixiユーザー 08月01日 22:57

スライドをウェブページに貼りましたー。

　ウェブページ:
　http://www.shudo.net/publications/swopp2006/

　PDF ファイル:
　http://www.shudo.net/publications/swopp2006/shudo-SWoPP2006-slides-overlay-routing.pdf

ログインすると、みんなのコメントがもっと見れるよ