The Grid Self-Organizing Protocol
グリッド、自己組織型プロトコル 原文はこちら

自己組織型マルチキャストネットワークのためのプロトコルプロポーザル
ベン・ヒューストン、Ben Houston ben@exocortex.org
月曜日、８月７日、２０００年
翻訳完了日：2000年8月10日
修正：2000年8月17日、「Ｆｒｅｅ」を無料と誤訳。「空いている」と訂正。
Special Thanks , bero-san!

この文書では、グリッドと呼ばれるプロトコルを提唱します。グリッドは自らでネットワークをマトリックスに似たものへと構造化します（今は平面的な２Ｄのグリッドですが、かなり簡単により大きな次元に拡大することが可能です）。グリッドは自身をマトリックスに似たものへと構造化します。これは、マルチキャストのメッセージを転送できるように効率的に改善するためです。プロトコルのこのタイプは、それを作り出すために、さらにアプリケーションよりの（例えばグヌーテラみたいなもの）マルチキャストの効率的な変化を考慮にいれるべきです。

グリッド・プロトコルとは？
グリッドは通常使われれるトポロジーを使ってネットワークを構築するためにデザインされたプロトコルです。これは、ネットワークを通じた大変効率的なマルチキャストのメッセージの転送を考慮に入れています。マルチキャストメッセージはグヌーテラのようなファイル共有システムにおいて基礎をなすものです。

グリッド・プロトコルを走らせているネットワークの構造はどうなるか？

構造は、もちろん長方形のグリッド、又はメッシュ型となります。長方形のグリッドは大変理解しやすく、実現もしやすいために、三角形のメッシュ又はペンタゴンの６角形のようなメッシュの代わりになるものとして選ばれました。

ノードは自分たちをグリッド構造へどのように組み入れるか？

お互いのクライアントは、ネットワークへ４つの接続を行うことを奨励されています。これらの接続に北（ＮＯＲＴＨ）、東（ＥＡＳＴ）、西（ＷＥＳＴ）とラベルをつけます。クライアントは、それが北の接続ならば一方のクライアントは南の接続であり、東の接続ならば一方のクライアントは西の接続とのみ接続できるというわけです。あなたが誰かの南の接続でネットワークにコ接続するとしたら、自分が接続しているクライアントが適切なクライアントに知らせ、自分の東と西のノードに接続することを要求するということが重要になります。ローカルの接続要求メッセージを送ることで、これが実現されます。

Click here for a diagram of the connection sequence
 

なぜグリッドはそのグヌーテラをより効率的にするのか？

メッセージをブロードキャストするというその方法において、グリッドはさらに効率的なものとなっています。グヌーテラはランダムなネットワークを持つという性格上、ネットワークで誰が誰に接続されているかは分かりません。グヌーテラはそのノードの隣は接続されていないメッセージの伝達の互いのノードにおいて、メッセージが現在どのノードにいようが、ともかく、そのように仮定しなくてはなりません。すべての隣へのノードへのメッセージのブロードキャストの結果は、このメッセージを送った１つのノードを除きます。グリッドは、それが通常の構造を持ち、その構造は隣のノードは接続されており、もっとも効率的でかつ余っていない方法でメッセージをフォワードできるということを意味していています。

この効率的なマルチキャストシステムはどのように動くか？

４つのルールがあります。ノードは以下のルールに従わなくてはなりません：

・東から受け取ったら、西へ送る
・西から受け取ったら、東へ送る
・北から受け取ったら、南、西、東へ送る
・南から受け取ったら、北、西、東に送る

もしこの４つのルールが同じ場所である場合には、ノードはもっとも効率的な方法として、メッセージを全体のネットワークにブロードキャストすることができます。これは単純にメッセージを彼らの４つの隣のノードに対してブロードキャストする場合においてのみです。

Click here to see a large diagram of a broadcast:

しかし、グリッドにも穴があったらどうしよう？

グリッドにはたくさんの穴があるだろうし、これは伝達アルゴリズム上で問題を引き起こすだろう。運良く本当にシンプルな解決法があります。ノードが、直接伝達するように設定されたメッセージを伝達することができないときに、それは単にメッセージを伝達しなくなります。もしメッセージを伝達しているノードが、直接伝達できない接続を失った場合には、ノードはそのメッセージにある情報でマークします。その情報には、前のノードにおいて接続が途切れているということが書かれています。こうして、次のノードはメッセージを受け取った際に、次のノードは途切れた接続を知るようになるわけです。前のノードのミッション接続の方向への接続を持つ場合には、意図された方向と、前に失われた接続の方向の両方にメッセージを伝達します。このノードはブロードキャストメッセージとして前のミッション接続に対して伝達したメッセージへのマークも行います。これは、メッセージが必要とされている場所すべてに対してそれを伝達することを確実にするためのものです。こういったことは、極端にシンプルに聞こえるが、現実的には、グリッドの構造の中で穴の周りを「ラッピングする」という効果を持つことになるでしょう。

Click here to see a large diagram of the algorithm in action:

ユーティリティ接続

北、南、東、西の接続に付け加えて、ユーティリティ接続もあります。このユーティリティ接続は、ネットワークへログインするために、クライアントによって使われることになるでしょう。クライアントはグリッド構造上で空いているロケーションを見つけなければならないために、クライアントは最初にノードに接続しなくてはならず、ノードに利用可能な経路を持つかどうかを尋ねなければなりません。もし、経路が利用不可能であった場合には、クライアントは二つの選択があります。１つはユーティリティ接続からユーティリティ接続へとジャンプするネットワークを横切るか、又はノードに対してネットワークで空いているところへの接続に対するクエリーを出すために接続されているかを尋ねるかです。どんな検索もユーティリティ接続によって導かれないこともありえます。この際のたった１つ、利用可能な選択は、隣のノードを決定し、空いているロケーションの検索を行うというものです。