議論:距離とアルゴリズムの不整合
出典: P2P SIP
目次 |
目的
ID空間を元に作られる位相的な話にプラスして、ID間の距離という概念の持ち込んだ場合の不整合を検証する
言うならば、位相と距離の定義にある乖離の問題。または、ルーティングアルゴリズムと距離の定義との間の不整合ともいってよいかも。
きっかけ
- 構造化オーバレイの routing / forwarding を実装するためには、距離云々よりも、手順を記述できることが第一。
- しかし、Pastryは、Plaxtonの方法にプラスして、近傍（IDの距離の近いもの）のノードを集めた表（leaf set）を持つ、いわばハイブリッドなものにおいて、実装時に問題が発見された。
⇒こちら、[首藤さん]による指摘があった。
対象
greedy forwarding （最も近い距離のノードを選ぶ）の罠
- 終点のノードへ到達するパスがあるのにもかかわらず到達できないということが起こること。
- local maximum/minimum 問題ともいう。
具体例
- [首藤さん]が、[OverLay weaver]を実装中に発見された問題点。
- 下記は、首藤さんより頂いた説明メールを添付したものである。
(PC 1台上で) 10,000 ノードの動作試験をしていて、Pastry, iterative routing で、経路がループしてることに気づきました:
ログの内容 警告: TTL expired: (略) emu5960 emu8052 emu5960 emu8052 ... (emu◯◯ ってのは、仮想的なホスト名です。)
19fd... という ID に向けてのルーティングの際に、emu5960 と emu8052 の間で、ピンポンが起きてます。
で、emu5960 の経路表を調べました。Pastry のパラメータとして、基数は 16 (4 bit 単位), ID の bit 数 128 です。
ID and address: 1a238153561985cb517f7bcf2ab3bcf7:emu5960 Routing table: [ 0 0:emu7017 2:emu5957 3:emu5886 4:emu5943 5:emu1 6:emu5951 7:emu5909 8:emu5956 9:emu5941 a:emu5954 b:emu5901 c:emu5936 d:emu5959 e:emu5953 f:emu5923 1 0:emu6959 1:emu7472 2:emu6822 3:emu7584 4:emu7112 5:emu5719 6:emu5860 7:emu7082 8:emu7241 『9:emu8052』 b:emu6868 c:emu6502 d:emu5836 e:emu7680 f:emu6225 2 0:emu2785 1:emu1250 3:emu1121 4:emu836 7:emu9450 8:emu1716 a:emu563 b:emu2410 e:emu5935 f:emu9361 ] leaf set: [ emu2785 emu1767 emu4743 emu1250 | emu1121 emu3421 emu5060 emu836]
この emu5960 のノード ID は 1a23... です。
この emu5960 が 19fd... を宛先として、Pastry のルーティングアルゴリズムに従って next hop を算出すると、経路表中の『』内の emu8052 が next hop となります。 (この場合 leaf set は 19fd... をカバーしていないので、Plaxton et al. 方式の表に従います。)
でも、emu8052 の ID は実は 1a0a... でして、emu5960 から emu8052 にまわしてしまうと、宛先の 19fd... より遠くなってしまうんです:
emu8052 のノードID: 1986... ← 宛先への距離、およそ 0077...。遠い。 ルーティングの宛先: 19fd... emu5960 のノードID: 1a23... ← 宛先への距離、およそ 0025...。近い。
Pastry は、ID 間の距離を、ID 間の差分の絶対値と定義しており、この距離を縮める方向にルーティング (正確には forwarding) していく、というのが基本的な方針です。
詳細な解説
- kibayosさんより、詳細な解説が届きました。
- この首藤さんのメール（修正済み）を前提にピンポンの現象を書きますと、たいだい図の通りになります。
Leaf Setに不整合（emu5960側に欠け）があったために、ピンポンするノード同士で異なるの距離判断をしていることが原因
となります。 Plaxtonの手法を適応させる際に、
整数距離を考慮すれば、停止できること
も確認しました。 こう考えると、
Bamboo で、digitの桁を1bitにして停止させる（停止させるために、1bitにしているのではないかという首藤さんの予想）
というのはあまり賢い方法ではないなあ、と感じました。 Pastryは、このように、2種類の距離空間が混在しているのですが、片方の距離空間からルーティングの振る舞いを見ますと、「バンカーからボールを出せないで、限りなく打っている」という風に見えます。 以前話題に出ていた、local max/min 問題と捉えることも可能です。 （どっちの距離を主にするかは議論のあるところ）
まとめ
- 上記において、この距離を縮める方向にルーティング (正確には forwarding) していく、というのが基本的な方針(アルゴリズム)に従うと、宛先へ (距離が) 近付くとは限らない、という不整合があるということになる。
- Kademlia というアルゴリズムは、この種の不整合を持たず、きれいです。
- 方式としてもシンプルなので、世間で一番採用されている構造化オーバレイのアルゴリズムは Kademlia です。
距離の概念とは？
- Plaxton et al. ベースの Tapestry (という構造化オーバレイ) は、背景として ID 間距離という考え方を前提とはしているものの、routing / forwarding の手順においては ID 間距離は要りません。(同じく Plaxton ベースの Pastry は、leaf set を参照する → 距離を扱う)
「手順」が与えられれば routing / forwarding を実装できる、一方、「ID 間距離」という概念は構造化オーバレイに必須ではない (?)とすると、この「ID 間距離」という概念は一体何なのだろう?
というお話。
- 一つの解として、最低限、
ID 間距離は、forwarding の収束性 (ループせずに特定ノードに辿り着く) を保証するための強力な道具である
と言えるのでは？ しかし、それ以上の意味は、あるのかないのかは、不明である。
議論の発展
- 実は、この考察に基づいて、構造化オーバレイを設計する上での方法論を整理できるのかもしれません。
- 例えば、Kademlia (という構造化オーバレイ) は、「ID 間距離」を 1st class のものとして、その上で、距離と矛盾することのない routing / forwarding 「手順」を定義しています。(Tapestry とは違うわけです。)
⇒上記、[首藤さん]からの提案
問題点の再定義
- ただ、単純に、(1つの) 距離空間 (≒ ポテンシャル空間) での local minimum 問題というだけではなく、こういうことかな? と:
Pastry では、minimum (maximum) を探すために、 対象とする元の距離空間を近似し、かつ、効率よい (O(log n)) 探索が可能であるような別の距離空間 (e.g. Plaxton メッシュ) を定義した。 その近似空間における minimum は、元の空間での minimum と、実は一致しない。
- 現象は違いますが、これも、距離が定義された空間内での局所探索の際に起こる local mininum/maximum 問題（極小または極大値、どっち使ってもいいです、に引っかかってしまう問題）の一種だと思います。
- 感覚的に言えば、greedy forwarding の場合は、知らず知らずのうちに、目的場所から違ったところに誘導されてしまうのに対して、こちら（Pastryの場合）は、打っても打っても、バンカーから抜けれない状態です。
⇒上記、キバヨシさんからの提案
新しい筋道
確認事項
問題点の可視化
