« [クラシック]「のだめカンタービレ」面白すぎ! | トップページ | [P2P]P2P型WEBプロキシのセキュリティ »

2004.06.10

[P2P]分散ハッシュシステムでのNAT越えの考察

分散ハッシュ(DHT)の論文などを見ていると、システムにおけるNAT越えの問題についてあまり取り組んでないように思える。分散ハッシュではある特定ノード間でルーティング情報を交換しないといけないので、NAT越えの問題はもっと注目されても良いはずだ。

ここ数日間,分散ハッシュと親和性の高いNAT越え技術について考察したのでここで説明したい。今回提唱するモデルを「2重分散ハッシュテーブルモデル」と呼ぶことにしよう。

まず、ノード集合(Node_A)にはグローバルアドレスを持つノード集合(Node_G)とプライベートアドレスを持つノード集合(Node_P)がある。つまりNode_A=Node_G+Node_Pである。今特に問題なのはNode_P⇔Node_Pの通信なので、これにフォーカスしてみよう。これができればNode_P⇔Node_Gの通信もほぼ同じ技術で解決する。

今、Node_Pに属するノードP1,P2がある。P1はP2と通信したいとしよう。hash_XはノードXのハッシュとし、Next(hash)は分散ハッシュテーブルにおいてハッシュ値hash以上の最初に実在するノードとする。

まず、ノード全体の集合Node_Aは分散ハッシュテーブルDHT_Aを持っている。ここで、グローバルアドレスの集合Node_Gはあらたに別の分散ハッシュテーブルDHT_Bを持つ事にしよう。ただし、ハッシュ関数はDHT_AもDHT_Bも全く同じであり、例えば、グローバルアドレスのノードGがDHT_Aでハッシュ値hash_Gを持つとすれば、DHT_Bでもハッシュ値hash_Gを持つ。つまり、DHT_Gではプライベートアドレスのノード分だけそっくりルーティングテーブルから落としたDHTと考えて欲しい。分散ハッシュのChordで言うと、同じハッシュ空間で全ノードを格納しているリングと、グローバルアドレスノードのみ格納しているリングがあって、グローバルアドレスのノードの位置(つまりハッシュ値)は全く同じになっている。

まず、P1は適当なグローバルアドレスノードと接続してDHT_GにおいてNext(hash_P1)となるグローバルアドレスノードを見つける。これをG1とする。一回P1がG1を見つければ、P1⇔G1は定期的に通信をすることにする。(理由は後述する。)次にP1はDHT_GにおいてNext(hash_P2)となるグローバルアドレスノードをみつける。これをG2とする。P2⇔G2は先ほどの説明より定期的に通信をしている。これで準備が整った。

ここからP1⇔P2の通信を行うために、(UDP Hole punching +STUN+Jxtaの原理)をミックスしたアプローチをとる。UDP Hole puchingやSTUNについては先日のBlogHPを見て欲しい。

1)P1はG2と通信することにより、P2と通信するためのポートとIPアドレスを知る。またP1はG1に対してP2と通信したいというメッセージをP2宛てに残す。

2)P1はP2に対してG2から教えてもらったIPアドレス、ポートにUDPで通信をする。まだP1⇔P2の通信は確立しない。

3)P2はG2と通信して、P1から接続要求があることを知る。また同時にP1のIPアドレスとポートを知る。これにより、P2はP1へそのアドレスとポートへUDPで通信をする。これにより、P1⇔P2の通信が確立する。(ただし、P1,P2がSymmetric NATでないとする。)

4)P1⇔P2の通信ができない場合、P1,P2のどちらかまたは両方がSymmetric NATであることがわかる。そのため、P1⇔G2⇔P2という通信をすることによりNAT越えを行う。

このようなステップを取れば、通信ノードの両方でNATがあっても通信ができる。すなわち、STUNサーバがグローバルアドレスのノードに分散していると考えてもらえば良い。これができれば、各ノードはルーティングテーブルを容易に交換できるから全ノードの分散ハッシュテーブルDHT_Aを構成することができる。

本考察では各ノードの通信を成立するためにグローバルアドレスのノードだけによる分散ハッシュテーブルを導入した。今回のモデルではグローバルアドレスのノードに対してほぼ均等に負荷が分散されるが、例外としてSymmetric NATを使用し且つ通信量の多いプライベートアドレスのノードXにおいて、DHT_GにおけるNext(hash_X)となるグローバルアドレスのノードに大きな負荷がかかるので、その辺の負荷分散を検討するともっと面白いモデルができるだろう。

(補足)分散ハッシュテーブルを1つにしても同様なことが実現できます。つまり、グローバルアドレスのノード間で通常のDHTでルーティングして、プライベートアドレスのノードはある規則によって特定のグローバルアドレスのノードとルーティングテーブルを回すという方法です。(つまり、プライベートアドレスのノードはグローバルアドレスのノードにぶらさがているというイメージです。)実装は本章の提案よりもやや面倒なことになるかもしれません。

|

« [クラシック]「のだめカンタービレ」面白すぎ! | トップページ | [P2P]P2P型WEBプロキシのセキュリティ »

パソコン・インターネット」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: [P2P]分散ハッシュシステムでのNAT越えの考察:

» 秋田 [PukiWiki/TrackBack 0.1]
Dev/ByMe/開発日記/2004-06-29 分散ハッシュでのnat越え、実装できれば楽になる。 http://toremoro.tea-nifty... [続きを読む]

受信: 2004.07.28 11:09

« [クラシック]「のだめカンタービレ」面白すぎ! | トップページ | [P2P]P2P型WEBプロキシのセキュリティ »