さて、今度はP2P技術（この場合オーバーレイネットワークと言ったほうが いいかもしれませんが）の肝の一つであるルーティングの話をしましょう。 ルーティングというとアドホックネットワークで非常に大きな役割を示しますが、 通常のP2Pにおいてもルーティングを考える事によって新たなシステムを提案 することができます。後述しますが、応用例として匿名性の高いインスタントメッセンジャーなどが考えられます。
Winnyのような数珠繋ぎ状ネットワークにおけるP2Pでのルーティングは主に2つに分かれます。１つはReactive Type,もう一つはProcative Typeです。（分散ハッシュ等での効率的なルーティング方法はこの後の章に書いてあります。）では、これらの違いを説明します。
Gnutellaではファイル情報を入手する際にブロードキャストをしますね。その際に GUIDという各ノードの各処理に応じたユニークな数もブロードキャストします。 今、AというノードがBというノードを介してCと通信したいとします。するとAはブロードキャストをして、BにGUID_Aを渡します。BはCにGUID_Aを渡します。Cは返答としてBにGUID_Cを渡します。BはAにGUID_Cを渡します。この時にBはGUID_AとGUID_Cがどこから来ているかわかるのでAとCに対するルーティングテーブルができあがります。その後はAとCは今度はブロードキャストせずに通信することができるのです。Gnutellaの仕組みはここまでですが、仮にこのせっかく作成されたルーティングテーブルを一定期間保持して他のノードも利用できれば便利ですよね。これがReactive Typeのイメージです。
Reactive Typeの場合、通信を行うためにまず経路の確保をしないので後述するProcative Typeよりも各ノードとの通信を行う際に遅延が生じると考えられます。また、Reactive Typeは定期的に経路情報を交換しないので、端末のリソース消費を最小限に抑えることができます。
Reactive Typeの代表例としてAODV,DSRなどが挙げられます。
Procative Typeの例としてOLSR、TBRFが挙げられます。
通常のルーティングと違い、自分のIPアドレスを他ノードに教えてもあまり上手くルーティングできません。これは例えばノードがプライベートアドレスであればなお更の事です。そこで、各ノードは自分のネットワーク参加時間とIPアドレスなどを基にハッシュ値を求めます。これは各ノードでユニークな値なのでGUIDと呼ぶことにしましょう。今回はGUIDを基にノードのルーティングをすることにします。
さて、どうやって経路情報を他ノードに知らせるでしょうか?ここではProcative Typeで考えて見ましょう。まず、各ノードはルーティングテーブルを交換します。このときに交換される内容として、GUIDとホップ数が挙げられます。またホップ数にはRIPのように上限を設定しておきますがこの上限をRとしましょう。ではなぜホップ数も交換する必要があるのでしょうか？これはループを避けるためです。ノードは各GUIDにおいて最小ホップ数に対するルーティングを覚えます。(これについての考察は「P2Pとルーティング【後編】」で行う予定です。）
一番やっかいなのはノードの参加と離脱です。ノードの変化に対してProcative Typeによって遠方のノードに教えるには非常に時間がかかることが考えられます。一つはルーティングテーブルの交換の間隔を短くする事ですが、それでは機器のリソースを消費します。そこで、ノードがネットワークに参加する場合にはホップ数Rまでブロードキャストをします。また、新たなノードは隣接ノードからルーティングテーブルの情報をもらいます。これによって新ノードは速やかに他ノードと通信できます。
では具体例で説明しましょう。下図をご覧になって下さい。今、Aというノードが新たなにBと接続します。今R=４とすればDやGまでブロードキャストされることになります。これによって、DやGでもAと言うノードがどのリンクからたどればルーティングできるかわかりますね。また、AはBからルーティングテーブルをもらうことになります。
今度はネットワークから離脱する場合です。隣接ノード間は定期的にノードが生きているかチェックしています。これが数回エラーを起こした時、隣接ノードは死んでいると想定します。その際にそれを確認したノードはホップ数R-1まで、そのノードが死んでいる事をブロードキャストします。
これも具体例で説明しましょう。下図を見て下さい。今、Aというノードが離脱しました。その時、隣接ノードのBは一定時間後、Aがネットワークから離脱した事を判断します。R=４なので、Bはホップ数R-1=3でブロードキャストします。このようにすれば、Aがネットワークに参加した時にブロードキャストした範囲のノードに対して、Aが離脱した事を知らせる事ができます。確かにDやGにもブロードキャストされていますね。
これによって、少なくとも経路情報が交換されるネットワーク内(ホップ数R）においてはノードの参加と離脱が速やかに周知されることになります。
さて、このモデルではノードの情報についてはホップ数Rまでしか伝わらない事がわかりました。そこでよりノードの情報を拡張できる方法を考えてみましょう。
たとえば、スタティックルーティングなどの場合自分のルーティングテーブルにないノードへの通信はデフォルトゲートウェイに飛ばします。これをオーバレイネットワークに応用してみましょう。
まず、ネットワークに参加したノードは先ほどのように自分自身の存在を知らせるためにブロードキャストします。このときに、デフォルトゲートウェイとなっているノードはこのブロードキャストを受け取ると、自分自身がデフォルトゲートウェイであること返答します。また、そのデフォルトゲートウェイに対する返答がない場合は参加したノードが自らデフォルトゲートウェイとなります。これで各ノードがデフォルトゲートウェイのルーティングテーブルを持つことになります。なお、デフォルトゲートウェイは定期的に自分の存在を周りのノードにホップ数Rでブロードキャストします。
さて、各ノードが自分自身のルーティングテーブルにないノードと通信する時にはデフォルトゲートウェイの方向へ通信を投げます。こうすれば、少なくともデフォルトゲートウェイになったノードとホップ数Rのノードとは通信ができることになります。ただし、デフォルトゲートウェイを設置したことによりデフォルトゲートウェイとなったノードや周辺のノードに対しては負荷がかかります。
これも具体例で見てみましょう。下図をご覧になって下さい。今Hがデフォルトゲートウェイだとします。R=4であれば、KもAもHの存在に気づいている事に注意してください。まず、KがAに対して通信を行おうとします。ところがKはAのルーティングテーブルを保持していないのでHの方向すなわちJに対して通信します。JもAのルーティングテーブルを保持してないのでよりHに近いGに通信します。GはAからホップ数４のところですから、Aに対するルーティングテーブルを保持しているのでGはAと通信ができます。これによってめでたくKはAと通信できることができました。
これで、最大ホップ数２R内のエリアにおける通信ができるようになりました。 次にデフォルトゲートウェイの扱いとさらにこの考え方を拡張してより広い範囲で通信ができる方法を説明します。