ルーティングテーブルデバイスに関する記事と、QuaggaでのBGPプロトコルの実装に関する記事の続きで、この記事ではOSPFプロトコルがどのように機能するかを分析します。 他のルーティングプロトコルからのルートを再配布せずに、1つのOSPFゾーンの場合に限定します。



いつものように、OSPFプロトコルの動作と構成については詳細に説明せず、OSPFプロトコルの詳細についてはどこで参照できるかについて言及しません。 この記事をさらに理解するために、最も重要な情報に限定しています。



異なるネイバーからの着信ルートを比較し、いくつかの基準に従って最適なものを選択するRIPまたはBGPプロトコルとは異なり、OSPFプロトコルはネットワークのトポロジマップを構築し、対応するipネットワークへの最短ルートを描画します。 ネットワークトポロジに関する情報を収集するために、ルーターは直接接続されたネットワークとそのOSPFネイバーに関する情報をルーター間で交換します。 これらのトポロジ情報はLSA（Link State Advertisement）と呼ばれ、パズルのように、ネットワークの完全なトポロジマップを組み立てることができます。 LSAがどのように配置されるかについては少し後で見ていきます。次に、最短パスを見つけるためのアルゴリズムに進みます。

最短経路アルゴリズム

最短経路を見つけるために、ダイクストラアルゴリズムが使用されます。その動作は、次の例で考慮されます。 図に示すように、リンクで接続された5つのルーターがあります。









R1は、最短パスアルゴリズムを実行するルートルーターです。 リンク上の数字は、このリンクのコストを示しています。 タスクは、ルーターR1から他の各ルーターへの最短パスを見つけることです。 リンクの総コストが最小になる方法。



その結果、各ルーターについて、2つのことを計算する必要があります。

1. R1からこのルーターへのパスのコスト。
2. このネクストホップは、R1を使用してこのルーターに到達します。

この情報は、R1がルーティングテーブルを正しく作成できるようにするために必要です。 各ルーター内で、その前の現在の値を示します。 次に、R1がこのルーターに到達するために使用する現在のネクストホップを示します。 緑色で、最短パスが計算されるルーターをマークします。



したがって、初期段階では、ルータR1自体への最短パスは0になります。残りのルータのコストは無限であり、ネクストホップは不明です。



次に、一連の手順を実行します。各手順は、ルーターへのパスのコストを改善し、最終的にはすべてのルーターへの最短パスを計算します。

手順1.ルートルータのネイバーを調べます。

ルートルータR1のネイバーは、ルータR2とR3です。 これらのそれぞれについて、図のように、対応するリンクのコストに等しいパスのコストとルーターR2またはR3自体に等しいネクストホップを設定します。

ステップ2.残りの最良のものを選択します。

このステップでは、残りのすべてのルーター、つまり 最短パスがまだ検出されていないルーター（白）から、パスコストが最小のルーターを選択します。 私たちの場合、これはコストが1のR2ルーターです。このルーターを安全に緑に塗り替えることができます。短い経路はありません。









図では、このルーターはステップ3で役立つので、濃い緑色に塗られています。

ステップ3.選択したルーターの近隣を調べます。

この手順は手順1と似ていますが、ルーターR1の代わりに、前の手順で選択した濃い緑色のルーターの近隣を確認します。 各ネイバーについて、選択したルーターを通るパスのコストを計算します。 そのようなパスのコストが現在の値よりも小さい場合、新しい値をネイバーに割り当て、ネクストホップは選択されたルーターからそれをコピーするだけです。 次の図が判明します。









すべてのルーターが緑色に変わるまで、手順2と3を繰り返します。 ステージ2では、緑色に変わるルーターが1つあるため、このプロセスは遅かれ早かれ終了します。



そのため、残りの最適なものを選択し、緑色（R5ルーター）で塗り直します。









選択したルーターの近隣を調べ、コストを改善し、ネクストホップをコピーします。









R3に置き換えられたネクストホップがR5からコピーされたことがわかります。 最高の選択：









残りの隣人を見ます：









そして、最終結果が得られます。









これで、各ルーターへのパスのコストと、それらを達成するためにルートルーターで使用するネクストホップがわかりました。 つまり ルーティングテーブルを作成する準備がほぼ整いました。 ただし、ネットワークに直接適用する場合は、上記のアルゴリズムを近代化する必要があります。

最短経路を見つけるためのアルゴリズムの近代化

上記のアルゴリズムは、各リンクが2つのルーターを接続している場合、ポイントツーポイントリンクでのみ機能します。 ただし、実際のルーターは、イーサネットネットワークを介して相互に接続できます。これにより、図に示すように、2つ以上のルーターを1つのセグメントに接続できます。









OSPFでは、このようなネットワークは中継ネットワークと呼ばれます。 OSPFでこの問題を解決するために、各中継ネットワークはグラフ内の個別のノードとして表されます。 つまり 最短パスを計算すると、トポロジは次のようになります。









ノードN1は、中継ネットワークを指定するだけです。 これで、各リンクは2つのノードのみを接続し、最短パスを見つけるためのアルゴリズムを適用できます。 パスのコストを計算するとき、ルーターから中継ネットワークへのリンクのコストのみが考慮され、中継ネットワークからルーターへのリンクのコストは0に等しいと見なされます。



中継ネットワークは論理エンティティであるため、ルーターの1つが中継ネットワークを説明する必要なトポロジ情報を作成する責任を負う必要があります。 このため、各中継ネットワークのOSPFでDesignated Router（DR）が選択されます。DRは、それ自体に関する情報に加えて、中継ネットワークに関する情報を通知する義務もあります。



さらに、ルーティングテーブルには、ルーターへのルートではなく、IPネットワークへのルートが含まれています。 中継ネットワークの問題は簡単に解決されます。 トランジットネットワークはグラフ内の頂点で表されるため、トランジットネットワークへのルートのコストは、最短パス検索アルゴリズムを実行するプロセスで計算されます。 他のネットワーク、たとえば1つのOSPFルーターのみが接続されているネットワークは、スタブネットワークと見なされ、接続先のルーターによってアナウンスされます。 各ルーターへの最短パスのコストがわかれば、接続されているすべてのエンドネットワークへのルートのコストを簡単に計算できます。

リンクステートアドバタイズメント（LSA）

既に述べたように、各ルーターがネットワークトポロジを作成し、最短経路検索アルゴリズムを適用するために、ルーターはLink State Advertisement LSAと呼ばれる小さな情報を相互に交換します。 LSAには多くの種類があり、さまざまな種類の情報を送信します。 単一ゾーンの場合、LSAタイプ1とLSAタイプ2の2つのLSAタイプが重要です。各LSAタイプ1はルーターを記述します。 LSAタイプ2はトランジットネットワークを記述します。 さまざまなオーバーヘッド情報を省略すると、これらのLSAは次のように概略的に表すことができます。









以下は、LSAフィールドの簡単な説明です。

LSAタイプ1（ルーターLSA）。

LSAヘッダーの3つのフィールドは重要です。

• 種類 LSAのタイプを示します。 私たちの場合、これはタイプ1、またはルーターLSAです。
• LSID LSA識別子。 この場合、LSIDは、LSAを作成するルーターのルーターIDと同じです。
• Advルーター LSAを作成したルーターの識別子。 この場合、LSAを作成するルーターのルーターIDと同じです。 LSIDと一致します。

以下は、ルーターのリンクに関する情報です。 リンクについて送信される情報は、リンクのタイプによっても異なります。 ルーターには、次の3種類のリンクを設定できます。



トランジットネットワーク。 このタイプのリンクについては、次の情報が送信されます。

• リンクID-中継ネットワークに接続された指定ルーターインターフェイスのIPアドレス。
• リンクデータ-中継ネットワークに接続されているルーター自体のインターフェイスのIPアドレス。
• メトリック-リンクコスト。

ポイントツーポイント。 ポイントツーポイントリンクの場合、以下が送信されます。

• リンクID-近隣のインターフェースのIPアドレス。
• リンクデータ-ルーター自体のインターフェイスのIPアドレス。
• メトリック-リンクコスト。

究極の（スタブ）ネットワーク。 彼女のために送信されます：

• リンクID-ネットワークの実際のIPアドレス。
• リンクデータ-ネットワークマスク。
• メトリック-リンクコスト。

LSAタイプ2（ネットワークLSA）

LSAタイプ2は中継ネットワーク情報を送信し、各中継ネットワーク用に特別に選択された指定ルーターとしてアナウンスされます。



LSAヘッダーには、4つの重要なフィールドが含まれています。

• 種類 私たちの場合、これはタイプ2、またはネットワークLSAです。
• LSID LSA識別子。 この場合、LSIDは、中継ネットワークに接続された指定ルーターインターフェイスのIPアドレスと同じです。
• Advルーター LSAを作成したルーターの識別子。 この例では、指定ルーターIDと同じです。
• マスク。 ネットマスク

次に、中継ネットワークに接続されているルーターに関する情報があります。 そのようなルーターごとに、そのルーターIDが示されます。



各LSAはグラフノードに対応し、タイプに応じて、ルーターまたは中継ネットワークのいずれかを表します。 すべてのLSAを使用して、ネットワークトポロジを簡単に作成できるようになりました。 これを行うには、ルーターの中継リンクのリンクIDが中継ネットワークのLSIDに対応し、逆に、中継ネットワークの接続ルーターIDが中継ネットワークに接続されたルーターのLSIDに対応することに注意するだけで十分です。



たとえば、図は小規模なネットワークを示しています。









対応するLSA：









およびトポロジー：









作成および受け入れられたすべてのLSAは、LSDB（LSAデータベース）と呼ばれるデータベースに保存されます。 このデータベースに必要な主なことは、LSAを追加し、特定のタイプのすべてのLSAを反復処理し、LSAヘッダーのキーフィールドでLSAを検索できるようにすることです。



LSDBのすべてのLSAとそのフィールドのリストを表示するには、 show ip ospf databaseコマンド （すべてのLSAのヘッダーを表示）、 show ip ospf database route （LSAタイプのルーターに関する完全な情報を表示）、 show ip ospf database network （LSAに関する完全な情報を表示）タイプNetwork）。

Quaggaの実装

Quaggaでは、LSAストレージベース（LSDB）全体が、図に示すように、LSAのタイプごとに別々の複数のデータベースに分割されます。











特定のタイプのLSAを格納するための各ベースは構造が同様であり、前の記事で説明されたプレフィックスツリーの形でそれに含まれたLSAを格納します 。 LSIDとAdv Routerの組み合わせがプレフィックスとして使用されます。 これらのフィールドの組み合わせは、ゾーン内の特定のタイプの各LSAに固有です。



新しいLSAを受信すると、このLSAがLSDBに追加され、最短ルートの計算プロセスが開始されます。 プロセスは、ルーター自体に対応するLSAから始まります。 含まれている情報に基づいて、トポロジ内のルートノードに対応するメモリ内に新しいノードが作成されます。 さらに、最短パスアルゴリズムで説明されているように、トポロジ内の隣接ノードに対応するLSAがLSDBから順次取得され、新しいノードが作成され、それらへの最短パスと次ホップが計算されます。 並行して、処理されたノードについて、中継ネットワークへのルートがOSPFルーティングテーブルに追加されます。



トポロジの構築と最短パスの計算が完了すると、ルーターに対応するすべてのノードがスキャンされ、すべての最終（スタブ）ネットワークがOSPFルーティングテーブルに追加されます。 中継ネットワークへのルートは既にルーティングテーブルに既に追加されています。



最後の段階で、トポロジ内のすべてのノードがメモリから削除され、OSPFルーティングテーブルからのルートがzebraデーモンに渡されます。 このプロセスの図を図に示します。