リンクステートルーティングプロトコル

リンクステートルーティングプロトコルは、コンピュータ通信用のパケット交換ネットワークで使用されるルーティングプロトコルの主要な2つのクラスの1つであり、もう1つは距離ベクトルルーティングプロトコルです。^{[ 1 ]}リンクステートルーティングプロトコルの例としては、Open Shortest Path First (OSPF) やIntermediate System to Intermediate System (IS-IS) などがあります。^{[ 2 ]}

リンクステートプロトコルは、ネットワーク内のすべてのスイッチングノード（つまり、パケットを転送する準備ができているノード。インターネットでは、これらはルータと呼ばれます）によって実行されます。^{[ 3 ]}リンクステートルーティングの基本概念は、各ノードが、どのノードが他のどのノードに接続されているかを示すグラフの形式で、ネットワークへの接続マップを構築することです。 ^{[ 4 ]}次に、各ノードは、ネットワーク内のすべての可能な宛先への次に最適な論理パスを個別に計算します。 ^{[ 5 ]}その後、各ノードのルーティングテーブルは、最適なパスの各コレクションで構成されます。^{[ 6 ]}

これは、各ノードがルーティングテーブルを近隣ノードと共有することで機能する距離ベクトルルーティングプロトコルとは対照的です。リンクステートプロトコルでは、ノード間で渡される情報は接続性に関する情報のみです。^{[ 7 ]}リンクステートアルゴリズムは、各ルータが「近隣ノードについて世界に伝える」と非公式に特徴付けられることがあります。^{[ 8 ]}

リンクステート型ルーティングプロトコルでは、各ルータはネットワーク全体のトポロジーに関する情報を保持しています。各ルータは、ローカルなトポロジー情報を用いて、ネットワーク内のすべての宛先に対して最適なネクストホップを独自に計算します。これらの最適なネクストホップの集合がルーティングテーブルを構成します。

これは、各ノードがルーティングテーブルを近隣ノードと共有する距離ベクトル型ルーティングプロトコルとは対照的です。リンクステート型プロトコルでは、ノード間でやり取りされる情報は、接続マップの構築に使用される情報のみです。

リンクステートルーティングを使用した、最初の適応型ルーティングネットワークと考えられているものは、1976年から1977年にかけて、バーナード・J・ハリス率いるプレッシーレーダーのチームによって設計および実装されました。このプロジェクトは、英国陸軍のコンピュータ指揮統制システムである「Wavell」のためのものでした。最初のリンクステートルーティングの概念は、1979年にジョン・M・マクキラン（当時ボルト、ベラネク、ニューマンに所属）によって、ネットワークの状態が変化するとより迅速に経路を計算し、より安定したルーティングにつながるメカニズムとして発表されました。^{[ 9 ] [ 10 ]} 

この技術は後に、現代のリンクステートルーティングプロトコルであるIS-ISとOSPFで使用するために採用されました。Ciscoの資料では、トポロジマップではなくルーティングテーブルを配布するにもかかわらず、Enhanced Interior Gateway Routing Protocol（EIGRP）を「ハイブリッド」プロトコルと呼んでいます^{[ 11 ]}。ただし、OSPFと同様に起動時にルーティングテーブルを同期し、トポロジの変更が発生した場合にのみ特定の更新を送信します。

2004年、ラディア・パールマンは、ルーティングブリッジ、またはRbridgeと呼ばれるデバイスを使用してレイヤ2フレーム転送にリンクステートルーティングを使用することを提案した。インターネット技術タスクフォースは、これを実現するためにTransparent Interconnection of Lots of Links （TRILL）プロトコルを標準化した。^{[ 12 ]}

近年では、この階層的な手法は、最適化リンク状態ルーティングプロトコル（OLSR）を用いた無線メッシュネットワークに適用されている。接続品質が変動する可能性がある場合でも、接続品質を利用してより良い接続を選択することができる。これは、無線周波数伝送を使用する一部のアドホックルーティングプロトコルで用いられている。

リンクステートアルゴリズムの最初の主要段階は、ネットワークのマップをすべてのノードに提供することです。これは、いくつかの補助的なステップを経て行われます。まず、各ノードは、完全に機能しているリンクを介して接続されている他のポートを特定する必要があります。これは、直接接続されている各隣接ノードと定期的に個別に実行される到達可能性プロトコルを使用して行われます。

各ノードは定期的に（および接続性の変化があった場合）短いメッセージであるリンク状態アドバタイズメントを送信します。このメッセージには以下の内容が含まれています。

• それを生成しているノードを識別します。
• 直接接続されている他のすべてのノード（ルーターまたはネットワーク）を識別します。
• これには「シーケンス番号」が含まれており、送信元ノードがメッセージの新しいバージョンを作成するたびに増加します。

このメッセージは、ネットワーク上のすべてのノードに送信されます。その前段階として、ネットワーク内の各ノードは、隣接するノードごとに、そのノードから受信した最新のリンク状態メッセージのシーケンス番号を記憶しています。ノードがリンク状態アドバタイズメントを受信すると、そのノードは、そのリンク状態メッセージの送信元について保存されているシーケンス番号を検索します。このメッセージが新しい場合（つまり、シーケンス番号が大きい場合）、そのメッセージは保存され、シーケンス番号が更新され、そのコピーが順番にそのノードの隣接ノードに送信されます。この手順により、各ノードの最新バージョンのリンク状態アドバタイズメントのコピーが、ネットワーク内のすべてのノードに迅速に配信されます。

完全なデータセットによって、ネットワークマップのグラフが生成されます。ノードとその隣接ノード間の接続性に変化が生じた場合（例えば、リンクが切断された場合）、隣接ノードに関する情報を提供するリンク状態メッセージが再計算され、ネットワーク全体に送信されます。

リンクステートアルゴリズムの2番目の主要な段階は、マップを検査してルーティングテーブルを作成することです。各ノードは、マップ上でアルゴリズムを独立して実行し、自身からネットワーク内の他のすべてのノードへの最短パスを決定します。一般的には、ダイクストラ法の何らかの変種が使用されます。ノードは、2つのデータ構造を保持します。1つは「完了」したノードを含むツリーデータ構造ツリー、もう1つは候補のリストです。アルゴリズムは、両方の構造が空の状態から開始し、最初の構造にノード自身を追加します。貪欲アルゴリズムの変種は、その後、次のことを繰り返し実行します。

• ノードに直接接続されているすべての隣接ノードは、ツリーに追加されます（ただし、既にツリーまたは候補リストに含まれているノードは除きます）。残りのノードは、2番目の（候補）リストに追加されます。
• 候補リスト内の各ノードは、既にツリー内に存在する各ノードと比較されます。ツリー内に存在するいずれかのノードに最も近い候補ノードがツリー内に移動され、適切な隣接ノードに接続されます。ノードが候補リストからツリー内に移動すると、そのノードは候補リストから削除され、以降のアルゴリズムの反復処理では考慮されなくなります。

候補リストにノードが残っている限り、この2つの手順が繰り返されます。（候補リストにノードが残っていない場合、ネットワーク内のすべてのノードがツリーに追加されます。）この手順は、ネットワーク内のすべてのノードを含むツリーで終了します。任意の宛先ノードに対して、その宛先への最適なパスは、ルートノードから最短経路ツリーの目的の宛先ノードに向かう枝をたどった最初のステップとなるノードです。

接続マップに変更が生じるたびに、最短経路ツリーを再計算し、ルーティングテーブルを再構築する必要があります。BBN Technologiesは、マップの変更によって影響を受ける可能性のあるツリーの部分のみを計算する方法を発見しました。

すべてのノードが全く同じマップに基づいて動作していない場合、ルーティングループが発生する可能性があります。これは、最も単純な形では、隣接する2つのノードがそれぞれ相手ノードが特定の宛先への最適な経路であると考える状況です。その宛先に向かうパケットがどちらかのノードに到着すると、その2つのノード間をループするため、この名前が付けられています。2つ以上のノードが関与するルーティングループも発生する可能性があります。

これは、各ノードが他のノードと一切やり取りすることなく最短経路ツリーとルーティングテーブルを計算するため発生する可能性があります。2 つのノードが異なるマップから開始する場合、ルーティング ループが発生するシナリオが発生する可能性があります。特定の状況では、マルチ クラウド環境内で差分ループが有効になる場合があります。インターフェース プロトコルを介した可変アクセス ノードは、同時アクセス ノードの問題を回避することもできます。^{[ 15 ]}

最適化リンク状態ルーティングプロトコル（OLSR）は、モバイルアドホックネットワーク向けに最適化されたリンク状態ルーティングプロトコルです（他の無線アドホックネットワークでも使用できます）。^{[ 16 ]} OLSRはプロアクティブであり、helloメッセージとトポロジ制御メッセージを使用して、リンク状態情報をモバイルアドホックネットワークに配信します。helloメッセージを使用して、各ノードは2ホップのネイバー情報を検出し、マルチポイントリレー（MPR）のセットを選出します。MPRにより、OLSRは他のリンク状態ルーティングプロトコルと区別されます。個々のノードは、トポロジ情報を使用して、最短ホップ転送パスを使用して、ネットワーク内のすべてのノードに関するネクストホップパスを計算します。

• 802.1aq最短経路ブリッジング

• Ciscoの「インターネットワーキング技術ハンドブック」の「ルーティングの基本」の章にある「リンクステート方式と距離ベクトル方式」のセクションを参照してください。