ルーティングプロトコル分類の概要

RIP(Routing Information Protocol)、OSPF(Open Shortest Path First)、BGP(Border Gateway Protocol)などのルーティングプロトコルは、次の3つの観点から分類することができます。

  • ルーティングプロトコルの適用範囲による分類
  • ルーティングプロトコルのアルゴリズムによる分類
  • ネットワークアドレスの認識による分類

2つ目のルーティングプロトコルのアルゴリズムについてみてみましょう。

ルーティングアルゴリズムによる分類

ルーティングプロトコルのアルゴリズムとして、主に次の3つあります。

  • ディスタンスベクタ型
  • リンクステート型
  • ハイブリッド(拡張ディスタンスベクタ)型

そして、こうしたルーティングプロトコルのアルゴリズムのポイントは、次の3点です。

  • 「どのような情報」を交換するか
  • 「どのようなタイミング」で交換するか
  • 交換した情報から「どのように」最適ルートなルート情報を決定するか

以降、3つのルーティングプロトコルのアルゴリズムについて、それぞれ3つのポイントを考えましょう。

ディスタンスベクタ型

ディスタンスベクタ型ルーティングプロトコルでは、ルータ同士でネットワークアドレス/サブネットマスク+メトリックの情報を交換します。ディスタンスベクタ型のルーティングプロトコルは、「距離」と「方向」に基づいてルートを決定するというように説明されていることが多いです。具体的に、距離とはメトリックです。そして、方向はネクストホップとインタフェースです。ディスタンスベクタ型ルーティングプロトコルのルート情報の送信を簡単に示したものが次の図です。

図 「距離」と「方向」

R1は192.168.1.0/24のネットワークのルート情報をR2とR3から受信しています。R2から送信されたルート情報にはメトリック10が含まれていて、R1のインタフェース1で受信しています。R1から見ると、192.168.1.0/24のネットワークはインタフェース1のR2の方向で距離10だけ離れていることになります。同様にR3から送信された192.168.1.0/24のルート情報に含まれるメトリックは5で、R1はインタフェース2で受信します。つまり、R1から192.168.1.0/24のネットワークは、インタフェース2のR3の方向で距離5だけ離れています。

また、ディスタンスベクタ型ルーティングプロトコルではネットワーク構成に何も変更がなくても定期的にルート情報を交換します。定期的にルート情報を交換することで、他のルータがきちんと動作していることやリモートネットワークがダウンしていないことを確認しています。

そして、交換したルート情報から最適ルートを決定するために、ベルマンフォードアルゴリズムを採用しています。簡単に言えば、メトリックが最小のルート情報が最適ルートとしてルーティングテーブルに登録されるようになります。

具体的なディスタンスベクタ型ルーティングプロトコルは、RIPv1およびRIPv2です。

なお、RIPv1は後述するクラスフルルーティングプロトコルなので、交換するルート情報にサブネットマスクを含みません。

RIPについて以下の記事でより詳しく解説しています。


リンクステート型

リンクステート型ルーティングプロトコルでは、ルータは自分が持っているインタフェースの情報を交換します。インタフェースの情報をリンクステート情報(Link State Advertisement : LSA)と呼びます。LSAの中には、そのルータがどのようなインタフェースを持っていて、どのようなタイプのネットワークに接続されていて、IPアドレスや、帯域幅についてなどの情報が入っています。なお、LSAの交換は何らかの変更があったタイミングで行います。このLSAを集めて、リンクステートデータベース(Link State Data Base : LSDB)を作成します。

LSDBには、ネットワーク上のルータのLSAがすべて含まれています。つまり、LSDBを見れば、ネットワーク上にルータが何台存在していて、各ルータがどんなインタフェースをいくつ持っていて、他のルータとどのように接続されているか、というネットワーク構成を再現することができます。

LSAを交換して作成したLSDBから、最適ルートを決定するためにSPF(Shortest Path First)アルゴリズムを採用しています。LSDB内のルータ自身を起点として、リモートネットワークへの最小コストとなるルートを最適ルートとしてルーティングテーブルに登録します。

具体的なリンクステート型ルーティングプロトコルは、OSPFとIS-ISです。次の図は、OSPFの動作を簡単に表したものです。

図 OSPFの動作の概要

OSPFについて以下のリンクよりより詳しい解説をご覧いただけます。


ハイブリッド(拡張ディスタンスベクタ)型

ハイブリッド(拡張ディスタンスベクタ)型は、Ciscoが独自にディスタンスベクタ型を拡張したルーティングアルゴリズムです。ベースはディスタンスベクタなので、ルータ同士が交換する情報は、ネットワークアドレス/サブネットマスク+メトリックです。ただし、定期的ではなく、ネットワークに変更があったときのみ交換します。

交換したルート情報からDUAL(Diffusing Update ALgorithm)によって、最適ルートを決定します。簡単に言えば、DUALでもメトリックが最小のルート情報が最適ルートになり、ルーティングテーブルに登録されます。またDUALでは、最適ルートだけでなく利用可能なバックアップルートもあらかじめ決めておきます。利用可能なバックアップルートがあれば、障害発生時のコンバージェンスを非常に高速に行うことができます。

ハイブリッド型ルーティングプロトコルの具体的な例は、CiscoのEIGRPです。


Cisco EIGRPについて以下のリンクからより詳しい解説をご覧いただけます。


ルーティングアルゴリズムのまとめ

次の表にルーティングアルゴリズムの特徴をまとめています。

  ディスタンスベクタ リンクステート ハイブリッド
情報 ネットワークアドレス/サブネットマスク+メトリック リンクステート情報 ネットワークアドレス/サブネットマスク+メトリック
タイミング 定期的 変更時 変更時
決定 ベルマンフォード SPF DUAL
プロトコル例 RIPv1/v2 OSPF、IS-IS EIGRP

IPルーティングのキホン