技術知識⑪ ディスタンスベクターとリンクステート --- 「ディスタンスベクターとは、噂話が好きな奥様達による伝言ゲームである」 「リンクステートとは、同じカーナビをつけた走り屋の集団である」 ...私の先輩の格言より。 ＊ ＊ ＊ ルーティングプロトコルの仕組みには、大別して「ディスタンスベクター型」と「リンク ステート型」の2 種類がある、というようなことが、ネットワークの教科書には必ず書い てあると思います。 本コラムでは、今回から4 話連続で OSPF に関連したテーマを予定しており、第 1 回目の 今日は、ディスタンスベクターとリンクステートの違いの本質を暴いてしまいます。 ■ディスタンスベクター ディスタンスベクターはRIP や BGP などで使われている方式であり、以下のような特徴が あります。 ①経路表そのものを交換 ②局所的に情報を交換 ③経路表を比較して選択
出展：WIDE University, School of Internet
ネットワークアーキテクチャ 第 06 回(2002/11/18) 「経路制御」 http://www.soi.wide.ad.jp/class/20020022/slides/06/index_23.html
一つずつ、見ていくと ①経路表そのものを交換 経路情報（ルーティングテーブル）そのものを交換します。 ルーティングプロトコルがルーティングテーブルを交換するのは当たり前のように思われ るかもしれませんが、逆の言い方をすると、リンクステート型の場合にはルーティングテ ーブルそのものは交換しません。 後述するリンクステート型の仕組みを理解しないと、言っている意味がピンと来ないかも しれませんが、ここでは流してください。 ②局所的に情報を交換 基本的に隣接するルータとのみ情報（ルーティングテーブル）を交換します。 伝言ゲームのように、隣のルーターから仕入れた経路情報を、逆側のルーターへと伝えて いきます。 奥様達のコミュニティに流れた噂話が数日で町中に広まるのと同じで、伝言を何度か繰り 返すことによって、ネットワーク内の全てのルーターに同じ経路情報が行き渡ります。 リンクダウンなどのトポロジー変化があった場合には、伝言ゲームをやり直す必要がある ので、情報が行き渡るまでに多少の時間が必要です。 また、隣のルーターから伝言された経路情報は無条件に信じる、という特徴もあります。 逆の言い方をすれば、情報にフィルターをかけたり書き換えたりして、隣のルーターを「だ ます」のは簡単です。
だから、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 点 があげられています。 ①接続情報を交換 ②全域的に情報を交換 ③接続情報からトポロジを再構成
こちらも、一つずつ説明します。 ①接続情報を交換
接続情報（リンクステート）を交換するから、リンクステート型と呼ばれています。 接続情報と言われても意味不明だと思いますが、さきほどのクイズの「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)をフ ラッディングし、ダイクストラの再計算を行えば、即座に代替ルートが算出できるので、 伝言ゲームのやり直しが必要なディスタンスベクターよりも、高速に収束することが期待 できます。 なお、ディスタンスベクターは小規模ネットワーク用で、大中規模にはリンクステートが
良いというような記述をたまに見かけますが、正しい理解ではありません。 この点については、過去のコラムをご参照ください。
●大規模ネットワークでRIP を使っちゃ、いけませんか？ http://nw-expert.jp/column/cat10/127.html
Written by Keiichi Takagi. as of Mar 17,2010
