- 「ディスタンスベクターとは，噂話が好きな奥様たちによる伝言ゲームである」
- 「リンクステートとは，同じカーナビをつけた走り屋の集団である」
（私の先輩の格言より）
ルーティングプロトコルの仕組みには，大別して「ディスタンスベクター型」と「リンクステート型」の2種類がある，というようなことが，ネットワークの教科書には必ず書いてあると思います。
本コラムでは今回から4話連続でOSPFに関連したテーマを予定しており，初回となる今回は，ディスタンスベクターとリンクステートの違いの本質を暴いてしまいます。
ディスタンスベクター
ディスタンスベクターはRIPやBGPなどで使われている方式であり，以下のような特徴があります。
- 経路表そのものを交換
- 局所的に情報を交換
- 経路表を比較して選択
これらの特徴を1つずつ見ていきましょう。
①経路表そのものを交換
経路情報（ルーティングテーブル）そのものを交換します。ルーティングプロトコルがルーティングテーブルを交換するのは当たり前のように思われるかもしれませんが，逆の言い方をすると，リンクステート型の場合にはルーティングテーブルそのものは交換しません。後述するリンクステート型の仕組みを理解しないと，言っている意味がピンと来ないかもしれませんが，ここでは流してください。
②局所的に情報を交換
基本的に隣接するルータとのみ情報（ルーティングテーブル）を交換します。伝言ゲームのように，隣のルータから仕入れた経路情報を逆側のルータへと伝えていきます。奥様たちのコミュニティに流れた噂話が数日で町中に広まるのと同じで，伝言を何度か繰り返すことによって，ネットワーク内の全てのルータに同じ経路情報が行き渡ります。
リンクダウンなどのトポロジ変化があった場合には，伝言ゲームをやり直す必要があるので，情報が行き渡るまでに多少の時間が必要です。また，隣のルータから伝言された経路情報は無条件に信じる，という特徴もあります。逆の言い方をすれば，情報にフィルタをかけたり書き換えたりして，隣のルータを「だます」のは簡単です。だから，RIPやBGPでは，distribute-listやroute-mapなどのコマンドを使って，簡単に経路情報を操作できますね。
この方法では，同じ情報がグルグルと廻り続ける，いわゆるルーティングループに陥る恐れがあるので，ルートポイズニング，スプリットホライズンなどの対策が施されます。この点については，皆さんもよくご存知でしょう。
③経路表を比較して選択
隣接するルータが複数あれば，それぞれからルーティングテーブルが「伝言」されてきますので，自分以外の各ルータへの最適なパスを一定のルール（ホップ数が最も少ない方向など）で選択して，自分のルーティングテーブルを作ります。
リンクステート
まず，以下のクイズを考えてみてください。
- 【問題】以下の情報に従い，A駅からD駅への最短ルートと距離を算出しなさい。
- A駅は，B駅とC駅に接続している。B駅との距離は10km，C駅との距離は5kmである。
- B駅は，A駅とD駅に接続している。A駅との距離は10km，D駅との距離は15kmである。
- C駅は，A駅とE駅に接続している。A駅との距離は5km，E駅との距離は15kmである。
- D駅は，B駅とE駅に接続している。B駅との距離は15km，E駅との距離は10kmである。
- E駅は，C駅とD駅に接続している。C駅との距離は15km，D駅との距離は10kmである。
- 【答え】
- 最短ルートはA駅→B駅→D駅
- 距離は25km
どうでしたか？絵を描いてみれば簡単にわかったと思います。
実は，これがリンクステートの基本的な考え方なのです。
先ほどと同様のWIDE Universityの資料では，リンクステートの特徴として以下の3点があげられています。
- 接続情報を交換
- 全域的に情報を交換
- 接続情報からトポロジを再構成
こちらも1つずつ説明しましょう。
①接続情報を交換
接続情報（リンクステート）を交換するから，リンクステート型と呼ばれています。接続情報と言われても意味不明だと思いますが，さきほどのクイズの「A駅は，B駅とC駅に接続している。B駅との距離は…」というのが接続情報に相当します。OSPFの場合はLSA（Link-State Advertisement）というやつですね。
②全域的に情報を交換
全てのルータと接続情報（LSA）を交換する，という意味です。
先ほどのクイズの場合でも，A駅からE駅までの全ての接続情報が揃っているから最短ルートが算出できるのであって，断片的な情報では正しいルートを判定できません。したがって，リンクステート型プロトコルでは，全てのルータから，全てのルータに対して，接続情報（LSA）を配信する必要があり，これがいわゆる「フラッディング」というやつです。
ディスタンスベクターの場合は，隣のルータから受け取った情報で，まず自分のルーティングテーブルを更新し，それを別の隣接ルータへ伝えていく，という「伝言ゲーム」だったわけですが，リンクステートでは隣のルータから接続情報を受け取ったら，中身を読む前に隣接する全てのルータへ情報をコピーして配信（フラッディング）する，というようなイメージになります。
リンクステートは，全てのルータが同じ接続情報を持っている，という前提で動作しますので，フラッディングの途中で情報をフィルタリングしたり書き換えたりすることは，原則としてできません。だからOSPFでは，RIPやBGPと比べて，（エリア内での）経路情報の操作が難しいですね。なお，OSPFのマルチエリア構成の場合は，同じエリア内のみでリンクステートが使われています。
逆に言えば，異なるエリアとはリンクステート型ではない方法で経路情報を交換している，ということです。この点については，後の回で説明できると思います。
③接続情報からトポロジを再構成
最初にクイズをやっていただいたので，この項目は説明不要でしょう。全ての接続情報，OSPFで言うところのLSDB（Link-State Data Base），に基づいて「地図」を作るということです。全てのルータが同じLSDBを持っていれば，完全に同じ地図が作れるはずです。
Wideの資料には③までしか書かれていませんでしたが，次のステップがあります。
④各ネットワークへの最短経路を探索し，経路情報を作成する
先ほど作った地図に基づいて，ルータごとにルーティングテーブルを作成します。
ここで「ダイクストラ・アルゴリズム」と呼ばれる手法が使われますが，これは実際にカーナビでも使われている，地図情報から最短経路を探索する方法です。全てのルータが完全に同じ地図を持っていて，同じアルゴリズムで経路を計算する，ということがポイントです。これにより，全てのルータが宛先への正しい「方向」を知っているので，ディスタンスベクターの弱点であった，「ルーティングループ」は起こりえないのです。
また，リンクダウンなどのトポロジー変化が発生した場合でも，新しい接続情報（LSA）をフラッディングし，ダイクストラの再計算を行えば，即座に代替ルートが算出できるので，伝言ゲームのやり直しが必要なディスタンスベクターよりも，高速に収束することが期待できます。
なお，ディスタンスベクターは小規模ネットワーク用で，大中規模にはリンクステートが良いというような記述をたまに見かけますが，正しい理解ではありません。
この点については，過去のこの連載をご参照ください。
第4回 大規模ネットワークでRIPを使っちゃ，いけませんか？
