今回は、第3回『地味な重要技術「パケット」』でちょっとだけ紹介したルーティングのお話です。
インターネットはパケットを転送していくルータが連携しながら巨大なネットワークを構成していますが、各ルータは「このパケットはどっちに転送すればいいか」を確認できる「ルーティングテーブル」を持っています。このルーティングテーブルは、次のような道路標識に似ています。
ルーティングテーブルは、「○○に行くにはあっちだよ」とか「××に行くにはこっちだよ」という情報を持っています。
図1
このルーティングテーブルの概念は非常にわかりやすいのですが、今回はもう一歩踏み込んで「じゃあ、どうやってルーティングテーブルを作ってるの？」という話をしようと思います。
まずは単純な例
まず、最初に非常に単純なネットワークを例に考えてみましょう。以下の例では3台の機器が数珠つなぎにつながっています。
図2
このようなトポロジのネットワークでは、複雑なルーティングは必要ありません。末端にいるAとCはBへとパケット転送を依頼する以外に方法がありません。また、間にいる機器がパケットを相互に転送するだけで済みます。
これは、間にある機器が「自分のつながっているネットワークを知っている」から可能となっています。
直接わからない例
では、次に4台の機器が数珠つなぎになっているネットワークを考えてみましょう。3台の例から1台増えただけですが、急に問題が複雑になってしまいます。
3台から4台に機器が増えて問題が複雑になるのは、全てを知れる立場にある機器が1台もなくなってしまうためです。AとDは当然、隣以外は直接知りませんし、間にいるBもCも互いの1つ向こうにいる機器は知りません。
図3
このような場合、どうにかして自分が直接知らない相手に関しての情報を入手しなければなりません。このような問題の解決を自動的に行うのがダイナミックルーティング（動的ルーティング）ですが、このルーティングにもいくつかの種類があります。
ネットワーク内のルーティング、ネットワーク間のルーティング
まず、ルーティングにはネットワーク内とネットワーク間の2種類があります。
インターネット上に接続された機器が3台、4台だけということはありません。数えきれないほどの大量の機器がインターネットに接続されています。それらの機器が、何らかの方法で、それぞれ独自にルーティングを考えて成り立っているのがインターネットです。
では、どうやってそんな巨大なものが動いているのでしょうか？ 「インターネット」という名前そのものが、その答えへの鍵になります。
インターネットは「ネットワークの集合体」です。ということは、ネットワークとネットワークが接続しているということになります。そして、相互接続している「ネットワーク内」と「ネットワーク間」で行われているルーティングの仕組みは、それぞれ別です。
ネットワーク間で行われるルーティングをEGP（Exterior Gateway Protocol）、ネットワーク内で行われるルーティングはIGP（Interior Gateway Protocol）と呼ばれます（EGPという単語には2つの意味があり、BGPの前身プロトコルとしてのEGPもありますが、それは今回は割愛します）。
特定の組織がコントロール可能な「ネットワーク内」と違い、「ネットワーク間」の接続は「全ての隣接ネットワークを全てに伝える」ような事はできません。そのような方法では規模性が実現できないためです。そのため、EGPはIGPとは異なる仕組みになっています。
リンクステート型
ネットワーク内で行われるルーティング手法であるIGPにはさまざまなものがあります。日本国内ではOSPF（Open Shortest Path First）と呼ばれる手法が多く利用されています。OSPFはリンクステート型のルーティングプロトコルです。
リンクステート型プロトコルでは、各ルータは「自分の隣にいる人」をネットワーク内の全てのルータに伝えます。なお、この自己申告される情報は、リンクステート情報と呼ばれ、224.0.0.5や224.0.0.6が利用されます。224.0.0.5や224.0.0.6はリンクローカルなマルチキャストアドレスであり、ルータを超えないマルチキャストです。
すべてのルータがすべての隣接ルータを自己申告していけば、ネットワーク内の地図を作るための部品が集まったことになります。そして、その情報から各自が「完全な地図」が構築できます。その「地図」を元にルーティングテーブルが構築されていきます。
図4
ルーティングテーブルはダイクストラ（Dijkstra）法を利用して作られて行きます。簡単に言うと、自分を中心とした木構造を作ってしまうという方法です。その木構造を見ることによってわかる、最も短い経路をルーティングテーブルに掲載していきます（コストの話はややこしくなるので、ここでは割愛します）。
ディスタンスベクター型
ディスタンスベクター型プロトコルもあります。これは、隣の人の情報を隣の人に聞いて、さらに隣の人の情報は、さらに隣からの伝聞情報として聞くという方法です。いわば、伝言ゲームを繰り返すという方法です。
伝言ゲームで「私は●●まで届けることができますよ」という経路情報を交換していくと、「●●まで届ける経路」として複数の経路が登場する可能性があります。各ルータは、「最も間にルータが入らずに●●まで届ける経路」を最適な経路としてルーティングテーブルに登録します。
このディスタンスベクター型を採用したプロトコルとしてはRIP（Routing Information Protocol）が挙げられます。RIPは、収束時間、ホップ数、エリア分けなど様々な課題があるため、主に大きさの限られた小規模ネットワークでの利用しか行われていません。
最後に
ルーティングまわりの話はいろいろと調べ始めると非常に面白いです。興味がある方は、RIPやOSPFなどの具体的なプロトコルの仕組みを調べてみることをお勧めします。
今回は、独立したネットワーク内でのルーティングに関する話でしたが、次はネットワーク間でのルーティングの話をします。インターネットはAS（Autonomous System）という単位で運営されていますが、次回はAS間を接続するBGP（Border Gateway Protocol）に関する説明です。
なお、ここでは主にルータが自動的に計算を行うダイナミックルーティング（動的なルーティング）の話をしました。人間が手動でルーティングテーブルを設定するスタティックルーティング（静的なルーティング）というものもあります。
