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

リンクステートルーティングプロトコルは、コンピュータ通信用のパケットスイッチングネットワークで使用されるルーティングプロトコルの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にも応用されました。シスコの文献では、Enhanced Interior Gateway Routing Protocol（EIGRP）はトポロジマップではなくルーティングテーブルを配布するにもかかわらず、「ハイブリッド」プロトコルと呼ばれています[ 11 ]。しかし、EIGRPはOSPFと同様に起動時にルーティングテーブルを同期し、トポロジの変化が発生した場合にのみ特定の更新を送信します。

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

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

地図の配布

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

各ノードは定期的に（および接続が変更された場合）、リンク状態アドバタイズメントと呼ばれる短いメッセージを送信します。

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

このメッセージはネットワーク上のすべてのノードに送信されます。必要な前提条件として、ネットワーク内の各ノードは、隣接するノードそれぞれについて、そのノードから受信した最後のリンクステートメッセージのシーケンス番号を記憶しています。あるノードがリンクステートアドバタイズメントを受信すると、そのノードは、そのリンクステートメッセージの送信元として保存されているシーケンス番号を参照します。このメッセージが新しい場合（つまり、シーケンス番号が大きい場合）、そのメッセージは保存され、シーケンス番号が更新され、そのコピーがそのノードの各隣接ノードに順に送信されます。この手順により、各ノードのリンクステートアドバタイズメントの最新バージョンのコピーが、ネットワーク内のすべてのノードに迅速に送信されます。

完全なセットは、ネットワークマップのグラフを生成します。隣接ノードに関する情報を提供するリンクステートメッセージは、ノードと隣接ノード間の接続性に変化が生じるたびに（例えばリンク障害など）、再計算され、ネットワーク全体にフラッディングされます。

ルーティングテーブルの計算

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

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

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

アルゴリズムの最適化

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

トポロジー削減

場合によっては、LSAメッセージを生成するノードの数を減らすことが合理的です。このため、ネットワークノードのサブセットのみがLSAメッセージを生成するトポロジ削減戦略を適用できます。トポロジ削減のために広く研究されている2つのアプローチは、最適化リンクステートルーティングプロトコル（OLSR）の基盤であり、OSPFでも提案されているマルチポイントリレー[ 13 ]と、同じくOSPFで提案された接続支配セット[ 14 ]です。

魚眼レンズステートルーティング

フィッシュアイステートルーティング（FSR）では、LSAに異なるTTL値を設定することで、LSAの拡散を制限し、制御メッセージによるオーバーヘッドを軽減します。同じ概念は、Hazy Sighted Link State Routing Protocolでも採用されています。

故障モード

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

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

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

参照

参考文献

  1. ^ 「ユニキャストルーティング - リンクステートルーティング」 . GeeksforGeeks . 2018年5月18日. 2024年5月9日閲覧。
  2. ^ lec10-lsrouting.pdf (princeton.edu) https://www.cs.princeton.edu/courses/archive/spring23/cos461/lectures/lec10-lsrouting.pdf
  3. ^講義6.pptx (umich.edu) https://www.eecs.umich.edu/courses/eecs489/w10/winter10/lectures/lecture6_2.pdf
  4. ^ 123sp15-lec14.pdf (ucsd.edu) https://cseweb.ucsd.edu/classes/sp15/cse123-a/lectures/123sp15-lec14.pdf
  5. ^リンクステートプロトコル.pdf (fauser.edu) http://nuovolabs.fauser.edu/~valeria/materiale-didattico/sistemi-quinta/link%20state%20protocol.pdf
  6. ^ 「9.6: リンクステートルーティング更新アルゴリズム」 . Engineering LibreTexts . 2019年8月12日. 2024年5月9日閲覧。
  7. ^ 5-routing-part2.pdf (washington.edu) https://courses.cs.washington.edu/courses/cse461/22sp/slides/5-routing-part2.pdf
  8. ^ライブラリ、ブロードバンド (2018年8月31日). 「ルーティングの詳細 |」 . 2024年5月9日閲覧。
  9. ^ John M. McQuillan、Isaac Richer、Eric C. Rosen、「ARPANet ルーティングアルゴリズムの改良」、BBN レポート No. 3803、ケンブリッジ、1978 年 4 月
  10. ^ John M. McQuillan、Isaac Richer、Eric C. Rosen、「ARPANetの新しいルーティングアルゴリズム」、 IEEE Trans. on Comm.、28(5)、pp. 711–719、1980
  11. ^ 「Cisco Firepower Threat Defense コンフィギュレーション ガイド（Firepower Device Manager バージョン 7.1 用） - Enhanced Interior Gateway Routing Protocol（EIGRP）[Cisco Secure Firewall Threat Defense]」。Cisco 。 2024年1月18日閲覧。
  12. ^ Eastlake 3Rd, Donald E.; Senevirathne, Tissa; Ghanwani, Anoop; Dutt, Dinesh; Banerjee, Ayan (2014年5月)、「Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS」、doi : 10.17487/RFC7176、RFC 7176 {{citation}}: CS1 maint: 数値名: 著者リスト (リンク)
  13. ^ Nguyen, Dang-Quan; Clausen, Thomas H.; Jacquet, Philippe; Baccelli, Emmanuel (2009年2月). 「アドホックネットワーク向けOSPFマルチポイントリレー（MPR）拡張」 . doi : 10.17487/RFC5449 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  14. ^ Ogier, Richard; Spagnolo, Phil (2009年8月). 「Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding」 . doi : 10.17487/RFC5614 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  15. ^ Wójcik, R (2016). 「ドメイン間マルチパス伝送を提供する方法に関する調査」.コンピュータネットワーク. 108 : 233–259 . doi : 10.1016/j.comnet.2016.08.028 .
  16. ^ RFC 3626

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Link-state_routing_protocol&oldid=1326428606」から取得