Loading article…
ルーティングとは、ネットワーク内、あるいは複数のネットワーク間におけるトラフィックの経路を選択するプロセスです。ルーティングは、公衆交換電話網（PSTN）などの回線交換ネットワークや、インターネットなどのコンピュータネットワークなど、多くの種類のネットワークで広く行われています。
パケット交換ネットワークにおいて、ルーティングとは、特定のパケット転送メカニズムによって、ネットワークパケットを送信元から宛先へと、中間ネットワークノードを経由して誘導する上位レベルの意思決定プロセスです。パケット転送とは、ネットワークパケットをあるネットワークインターフェースから別のネットワークインターフェースへと転送することです。中間ノードは通常、ルーター、ゲートウェイ、ファイアウォール、スイッチなどのネットワークハードウェアデバイスです。汎用コンピュータもパケット転送とルーティングを実行しますが、このタスクに特化した最適化されたハードウェアは備えていません。
ルーティング処理は通常、ルーティングテーブルに基づいて転送を指示します。ルーティングテーブルは、さまざまなネットワーク宛先への経路を記録します。ルーティングテーブルは、管理者が指定することも、ネットワークトラフィックを観測して学習することも、ルーティングプロトコルの支援を受けて構築することもできます。
狭義のルーティングは、多くの場合IPルーティングを指し、ブリッジングとは対照的です。IPルーティングは、ネットワークアドレスが構造化されており、類似のアドレスはネットワーク内での近接性を意味することを前提としています。構造化されたアドレスにより、単一のルーティングテーブルエントリでデバイスグループへの経路を表すことができます。大規模ネットワークでは、構造化されたアドレス指定（狭義のルーティング）は、非構造化アドレス指定（ブリッジング）よりも優れた性能を発揮します。ルーティングは、インターネットにおけるアドレス指定の主流となっています。ブリッジングは、ローカルエリアネットワーク（LAN ）内では依然として広く使用されています。
ルーティング方式は、メッセージの配信方法においてそれぞれ異なる。
ユニキャストは、インターネットにおけるメッセージ配信の主流方式です。この記事では、ユニキャストルーティングアルゴリズムに焦点を当てます。
静的ルーティングでは、小規模ネットワークでは手動で設定したルーティングテーブルを使用できます。大規模ネットワークは複雑なトポロジーを持ち、急速に変化する可能性があるため、ルーティングテーブルを手動で構築することは現実的ではありません。しかしながら、公衆交換電話網（PSTN）の大部分は、事前に計算されたルーティングテーブルを使用しており、最短経路がブロックされた場合はフォールバック経路が用意されています（PSTNにおけるルーティングを参照）。
動的ルーティングは、ルーティングプロトコルによって伝達される情報に基づいてルーティングテーブルを自動的に構築することでこの問題を解決しようとします。これにより、ネットワークはほぼ自律的に動作し、ネットワーク障害やブロックを回避できます。インターネットでは動的ルーティングが主流となっています。動的ルーティングプロトコルとアルゴリズムの例としては、Routing Information Protocol (RIP)、Open Shortest Path First (OSPF)、Enhanced Interior Gateway Routing Protocol (EIGRP) などがあります。
距離ベクトルアルゴリズムは、ベルマン・フォードアルゴリズムを使用します。この手法では、ネットワーク内の各ノード間の各リンクにコスト値を割り当てます。ノードは、総コスト（つまり、使用されるノード間のリンクのコストの合計）が最小となる経路を経由して、ポイントAからポイントBへ情報を送信します。
ノードが最初に起動したとき、そのノードはすぐ隣のノードと、そこへ到達するのにかかる直接的なコストしか知りません。（この情報、つまり宛先のリスト、それぞれの宛先までの総コスト、そしてそこへデータを送るための次のホップは、ルーティングテーブル、または距離テーブルを構成します。）各ノードは定期的に、自分が知っているすべての宛先までの総コストに関する現在の評価を、各隣のノードに送信します。隣のノードはこの情報を調べ、既に知っている情報と比較します。既に持っている情報よりも改善されているものがあれば、自分のテーブルに追加します。時間が経つにつれて、ネットワーク内のすべてのノードが、すべての宛先に対する最適な次のホップと総コストを発見します。
ネットワークノードがダウンすると、そのノードを次のホップとして使用していたノードは、そのエントリを破棄し、更新されたルーティング情報をすべての隣接ノードに伝達します。隣接ノードも同様にこのプロセスを繰り返します。最終的に、ネットワーク内のすべてのノードが更新情報を受信し、ダウンしたノードを経由しないすべての宛先への新しいパスを発見します。
リンクステートアルゴリズムを適用する場合、ネットワークのグラフィカルマップが各ノードの基本データとして使用されます。各ノードは、マップを作成するために、接続可能な他のノードに関する情報をネットワーク全体に送信します。その後、各ノードはこの情報を独自にマップにまとめます。このマップを使用して、各ルータは、ダイクストラ法などの標準的な最短経路アルゴリズムを用いて、自身から他のすべてのノードへの最小コストパスを独自に決定します。その結果、現在のノードを根とするツリーグラフが作成され、そのツリーの根から他の任意のノードへのパスが、そのノードへの最小コストパスとなります。このツリーは、ルーティングテーブルの構築に使用され、ルーティングテーブルは、現在のノードから他の任意のノードへの最適なネクストホップを指定します。
モバイルアドホックネットワーク向けに最適化されたリンクステートルーティングアルゴリズムは、最適化リンクステートルーティングプロトコル（OLSR）です。[ 2 ] OLSRはプロアクティブであり、Helloメッセージとトポロジ制御（TC）メッセージを使用して、モバイルアドホックネットワーク全体にリンクステート情報を検出して配信します。Helloメッセージを使用して、各ノードは2ホップのネイバー情報を検出し、マルチポイントリレー（MPR）のセットを選出します。MPRは、OLSRを他のリンクステートルーティングプロトコルと区別するものです。
距離ベクトルルーティングとリンクステートルーティングは、いずれもドメイン内ルーティングプロトコルです。これらは自律システム内部で使用されますが、自律システム間では使用されません。これらのルーティングプロトコルは、大規模ネットワークでは処理が困難になり、ドメイン間ルーティングには使用できません。距離ベクトルルーティングは、ドメイン内のホップ数が数個を超えると不安定になります。リンクステートルーティングは、ルーティングテーブルの計算に多大なリソースを必要とします。また、フラッディングによって大量のトラフィックが発生します。
パスベクトルルーティングは、ドメイン間ルーティングに使用されます。これは距離ベクトルルーティングに似ています。パスベクトルルーティングでは、各自律システム内の1つのノード（複数存在する場合もあります）が、自律システム全体を代表して動作することを前提としています。このノードはスピーカーノードと呼ばれます。スピーカーノードはルーティングテーブルを作成し、それを隣接する自律システムの近隣スピーカーノードに通知します。基本的な考え方は距離ベクトルルーティングと同じですが、各自律システム内のスピーカーノード同士のみが通信できる点が異なります。スピーカーノードは、自身の自律システムまたは他の自律システムのノードのメトリックではなく、パスを通知します。
パスベクトルルーティングアルゴリズムは、各境界ルータが到達可能な宛先を隣接ルータに通知するという点で、距離ベクトルアルゴリズムと似ています。ただし、宛先とその宛先までの距離でネットワークを通知する代わりに、宛先アドレスとそれらの宛先に到達するためのパス記述でネットワークを通知します。これまでに通過したドメイン（またはコンフェデレーション）で表現されるパスは、到達可能性情報が通過したルーティングドメインのシーケンスを記録する特別なパス属性に格納されます。ルートは、宛先とその宛先へのパスの属性とのペアとして定義されるため、パスベクトルルーティングと呼ばれます。ルータは、一連の宛先へのパスを含むベクトルを受け取ります。[ 3 ]
経路選択とは、複数の経路にルーティングメトリックを適用して最適な経路を選択（または予測）することです。ほとんどのルーティングアルゴリズムは、一度に1つのネットワーク経路しか使用しません。マルチパスルーティング、特に等コストマルチパスルーティング技術では、複数の代替経路を使用できます。
コンピュータネットワークでは、メトリックはルーティングアルゴリズムによって計算され、帯域幅、ネットワーク遅延、ホップ数、パスコスト、負荷、最大伝送単位、信頼性、通信コストなどの情報を網羅することができます。[ 4 ]ルーティングテーブルには可能な限り最良のルートのみが格納されますが、リンクステートデータベースやトポロジデータベースには他のすべての情報も格納される場合があります。
重複する経路や同一の経路が存在する場合、アルゴリズムは優先順位に従って以下の要素を考慮し、どの経路をルーティングテーブルにインストールするかを決定します。
ルーティングメトリックは特定のルーティングプロトコルに固有のものであるため、マルチプロトコルルータは、異なるルーティングプロトコルから学習したルートを選択するために、何らかの外部ヒューリスティックを使用する必要があります。たとえば、 Ciscoルータは、各ルートに管理距離と呼ばれる値を割り当てます。管理距離が小さいほど、そのプロトコルから学習したルートは信頼性が高いとみなされます。
ローカル管理者は、ホスト固有のルートを設定することで、ネットワーク使用状況をより詳細に制御し、テストを可能にし、全体的なセキュリティを向上させることができます。これは、ネットワーク接続やルーティングテーブルのデバッグに役立ちます。
小規模なシステムでは、単一の中央デバイスが事前にすべてのパケットの完全な経路を決定します。また、別の小規模なシステムでは、ネットワークにパケットを挿入するエッジデバイスが、その特定のパケットの完全な経路を事前に決定します。いずれの場合も、経路計画デバイスは、ネットワークに接続されているデバイスとその相互接続に関する多くの情報を把握する必要があります。この情報を入手すれば、A*探索アルゴリズムなどのアルゴリズムを使用して最適な経路を見つけることができます。
高速システムでは、毎秒送信されるパケット数が非常に多いため、単一のデバイスがすべてのパケットの完全な経路を計算することは現実的ではありません。初期の高速システムでは、回線交換によってこの問題に対処していました。回線交換では、送信元と宛先間の最初のパケットに対して一度経路を設定し、同じ送信元と宛先間の後続のパケットは、回線が切断されるまで経路を再計算することなく同じ経路をたどります。後期の高速システムでは、どのデバイスもパケットの完全な経路を計算することなく、ネットワークにパケットを注入します。
大規模システムでは、デバイス間の接続が非常に多く、しかもそれらの接続が頻繁に変化するため、どのデバイスもすべてのデバイスがどのように接続されているかを把握することすら不可能であり、ましてやそれらを通過する完全な経路を計算することは到底できません。このようなシステムでは、一般的にネクストホップルーティングが使用されます。
ほとんどのシステムは、決定論的な動的ルーティングアルゴリズムを使用しています。デバイスが特定の最終宛先への経路を選択すると、そのデバイスは、別の経路の方が良いと判断する情報を受け取るまで、常に同じ経路を選択してその宛先に向かいます。
一部のルーティング アルゴリズムは、パケットが元の送信元から最終宛先に到達するための最適なリンクを見つけるために決定論的アルゴリズムを使用しません。代わりに、パケット システム内の輻輳ホット スポットを回避するために、一部のアルゴリズムはランダム化アルゴリズム (Valiant のパラダイム) を使用して、ランダムに選択された中間宛先へのパスをルーティングし、そこから真の最終宛先にルーティングします。[ 5 ] [ 6 ]多くの初期の電話交換機では、多段階交換ファブリックを通るパスの開始を選択するためにランダム化がよく使用されていました。
パス選択を実行するアプリケーションに応じて、異なるメトリックを使用できます。たとえば、Web リクエストの場合は、Web ページの読み込み時間を最小限に抑えるために最小遅延パスを使用できます。また、大量データ転送の場合は、ネットワーク全体に負荷を分散してスループットを向上させるために、最も使用率の低いパスを選択できます。一般的なパス選択の目的は、トラフィック フローの平均完了時間とネットワーク帯域幅の総消費を削減することです。最近、パスごとにエッジでスケジュールされたバイトの総数を選択するメトリックとして計算するパス選択メトリックが提案されました。[ 7 ]この新しい提案を含むいくつかのパス選択メトリックの経験的分析が公開されています。[ 8 ]
ネットワークによっては、経路選択を単一の主体が担うのではなく、複数の主体が経路、あるいは単一経路の一部を選択するため、ルーティングが複雑になる場合があります。これらの主体が自身の目的を最適化するために経路を選択すると、他の参加者の目的と矛盾する可能性があり、複雑さや非効率性が生じる可能性があります。
典型的な例として、道路網における交通状況が挙げられます。各ドライバーは、移動時間を最小化する経路を選択します。このような経路選択では、均衡経路はすべてのドライバーにとって最適経路よりも長くなる可能性があります。特に、ブレースのパラドックスは、新しい道路を追加すると、すべてのドライバーの移動時間が長くなる可能性があることを示しています。
例えば、ターミナル上で自動搬送車（AGV）の経路設定に使用されるシングルエージェントモデルでは、インフラストラクチャの同じ部分が同時に使用されるのを防ぐために、各車両に予約が行われます。このアプローチは、コンテキスト認識ルーティングとも呼ばれます。[ 9 ]
インターネットは、インターネットサービスプロバイダ（ISP）などの自律システム（AS）に分割されており、各ASは自社のネットワークに関わる経路を制御しています。ルーティングは複数のレベルで行われます。まず、ASレベルのパスは、パケットが流れるASのシーケンスを生成するBGPプロトコルによって選択されます。各ASは、隣接するASから提供される複数のパスから選択できます。これらのルーティング決定は、多くの場合、これらの隣接するASとのビジネス関係と関連しており[ 10 ]、パスの品質や遅延とは無関係である可能性があります。次に、ASレベルのパスが選択されると、多くの場合、対応するルータレベルのパスが複数選択できます。これは、2つのISPが複数の接続を介して接続されている可能性があるためです。単一のルータレベルのパスを選択する際、各ISPはホットポテトルーティングを採用するのが一般的です。つまり、宛先までの総距離が長くなる場合でも、ISP自身のネットワークを通る距離を最小限に抑えるパスに沿ってトラフィックを送信します。
例えば、2つのISP、AとBを考えてみましょう。それぞれがニューヨークに拠点を持ち、低遅延の高速リンクで接続されています。5 ms —そしてそれぞれがロンドンに拠点を持ち、5 ms リンクで接続されている。両方の ISP が、2 つのネットワークを接続する大西洋横断リンクを持っていると仮定するが、Aのリンクの遅延は100ms で、Bの遅延は 120 ms です。Aの ソースからメッセージをルーティングする場合ロンドンのネットワークからBの目的地へAは、ニューヨークのネットワークを利用して、メッセージをロンドンのBに即座に送信することを選択する場合があります。これにより、Aは高価な大西洋横断回線を経由してメッセージを送信する手間を省くことができますが、メッセージの遅延は125 ミリ秒となり、他の経路であれば20 ミリ秒速かったはずです。
さらに、セルラーネットワークでも同様のルーティングの課題が見られます。セルラーネットワークでは、異なるパケットがさまざまなエンドポイントに送られ、各リンクのスペクトル効率が異なります。このような状況では、最適なパスの選択には遅延とパケットエラー率を考慮する必要があります。これに対処するために、各基地局ごとに1つずつ、複数の独立したエンティティがパス選択において重要な役割を果たし、ネットワーク全体のパフォーマンスの最適化を目指します。[ 11 ]
2003年のインターネット経路の測定調査では、隣接するISPのペア間では、ホットポテトルーティングにより30%以上の経路で遅延が増大しており、5%の経路で少なくとも12msの遅延が発生していること が判明しました。ASレベルの経路選択による遅延増大は相当なものでしたが、これは主に利己的なルーティングポリシーではなく、BGPに遅延を直接最適化するメカニズムがないことに起因するとされました。また、適切なメカニズムがあれば、ISPはホットポテトルーティングを使用するよりも遅延を削減するために協力するだろうとも示唆されました。[ 12 ]このようなメカニズムは後に同じ著者によって発表され、最初は2つのISPの場合[ 13 ]、次にグローバルな場合[ 14 ]について発表されました。
インターネットとIPネットワークがミッションクリティカルなビジネスツールとなるにつれて、ネットワークのルーティング状態を監視する技術と方法への関心が高まっています。ルーティングの誤りやルーティングの問題は、望ましくないパフォーマンスの低下、フラッピング、ダウンタイムを引き起こします。ネットワークのルーティングの監視は、ルート分析ツールと技術を使用して実現されます。[ 15 ]
転送状態を論理的に一元的に制御できるネットワーク（例えば、ソフトウェア定義ネットワーク）では、グローバルおよびネットワーク全体のパフォーマンス指標を最適化することを目的としたルーティング技術を使用できます。これは、プライベート光リンクを使用して接続されたさまざまな地理的場所に多数のデータセンターを運用する大手インターネット企業によって使用されており、その例としては、Microsoftの Global WAN [ 16 ] 、 Facebookの Express Backbone [ 17 ]、Googleの B4 [ 18 ]などがあります。
最適化するグローバルなパフォーマンス指標には、ネットワーク利用率の最大化、トラフィックフロー完了時間の最小化、特定の期限前に配信されるトラフィックの最大化、フローの完了時間の短縮が含まれます。[ 19 ]プライベートWAN上の後者に関する研究では、すべてのキューイングをエンドポイントにプッシュすることで、ルーティングをグラフ最適化問題としてモデル化することを議論しています。著者らはまた、わずかなパフォーマンスを犠牲にしながら効率的に問題を解決するためのヒューリスティックを提案しています。[ 20 ]
ネットワークのホットスポットを解消するために、... 2 段階のルーティング アルゴリズムを使用します。これは、すべてのパケットが最初にランダムに選択された中間宛先に送信され、中間宛先から最終宛先に転送されるというものです。ユニバーサル ルーティングと呼ばれるこのアルゴリズムは、負荷が高い状況下で容量を最大化し、遅延を最小化するように設計されています。