ルーティング

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

ルーティングは、ネットワーク内、または複数のネットワーク間または複数のネットワーク間のトラフィックのパスを選択するプロセスです。概して、ルーティングは公衆交換電話網(PSTN)などの回線交換ネットワークインターネットなどのコンピュータネットワークを含む、多くの種類のネットワークで実行されます

パケット交換ネットワークでは、ルーティングは、特定のパケット転送メカニズムによって中間ネットワークノードを介してネットワークパケットを送信元から宛先に向ける高レベルの意思決定ですパケット転送は、あるネットワークインターフェイスから別のネットワークインターフェイスのネットワークパケットの転送です。中間ノードは通常ルーターゲートウェイファイアウォールスイッチなどのネットワークハードウェアデバイスです。汎用コンピュータもパケットを転送してルーティングを実行しますが、タスク用に特別に最適化されたハードウェアはありません。

ルーティングプロセスは通常、ルーティングテーブルに基づいて転送を指示します。ルーティングテーブルは、さまざまなネットワーク宛先へのルートの記録を保持します。ルーティングテーブルは、管理者が指定したり、ネットワークトラフィックを監視して学習したり、ルーティングプロトコルを使用して作成したりできます

ルーティングは、狭義の意味で、IPルーティング指すことが多くブリッジングとは対照的です。IPルーティングは、ネットワークアドレスが構造化されており、同様のアドレスがネットワーク内の近接性を意味することを前提としています。構造化アドレスを使用すると、単一のルーティングテーブルエントリでデバイスのグループへのルートを表すことができます。大規模なネットワークでは、構造化アドレス指定(狭義のルーティング)は、非構造化アドレス指定(ブリッジング)よりも優れています。ルーティングは、インターネット上でのアドレス指定の主要な形式になっています。ブリッジングは、ローカルエリアネットワーク内でまだ広く使用されています

配信スキーム

ルーティングスキーム
ユニキャスト

Unicast.svg

ブロードキャスト

Broadcast.svg

マルチキャスト

Multicast.svg

Anycast

エニーキャスト-BM.svg

ルーティングスキームは、メッセージの配信方法が異なります。

  • ユニキャストは、送信者と宛先の間の1対1の関連付け使用して、単一の特定のノードにメッセージを配信します。各宛先アドレスは、単一の受信者エンドポイントを一意に識別します。
  • ブロードキャストは、1対すべての関連付け使用してネットワーク内のすべてのノードにメッセージを配信します。 1つの送信者からの単一のデータグラムは、ブロードキャストアドレスに関連付けられている可能性のある複数のエンドポイントすべてにルーティングされます。ネットワークは、必要に応じてデータグラムを自動的に複製し、ブロードキャストの範囲内のすべての受信者(通常はネットワークサブネット全体)に到達します。
  • マルチキャストは、使用してメッセージの受信に関心を表明しているノードのグループにメッセージを配信する、1対多の多または多対多の多の関連付けを、データグラムは、1回の送信で同時に多くの受信者にルーティングされます。マルチキャストは、宛先アドレスがアクセス可能なノードのサブセット(必ずしもすべてではない)を指定するという点でブロードキャストとは異なります。
  • エニーキャストは、ノードのグループのうちの任意の1つにメッセージを配信します。通常は、データグラムがすべての潜在的な受信者のグループの任意の1つのメンバーにルーティングされる1対1の関連付けを使用してソースに最も近いノードにメッセージを配信します。同じ宛先アドレスで識別されます。ルーティングアルゴリズムは、ある距離測定に従って最も近いものに基づいて、グループから単一の受信機を選択します。

ユニキャストは、インターネット上でのメッセージ配信の主要な形式です。この記事では、ユニキャストルーティングアルゴリズムに焦点を当てています。

トポロジー分布

スタティックルーティング、小規模ネットワークを手動で設定ルーティングテーブルを使用してもよいです。大規模なネットワークには複雑なトポロジがあり、急速に変化する可能性があるため、ルーティングテーブルを手動で作成することは不可能です。それにもかかわらず、ほとんどの公衆交換電話網(PSTN)は、事前に計算されたルーティングテーブルを使用し、最も直接的なルートがブロックされた場合のフォールバックルートを使用します(PSTNのルーティングを参照)。

動的ルーティングは、ルーティングプロトコルによって伝送される情報に基づいてルーティングテーブルを自動的に構築することでこの問題を解決しようとします。これにより、ネットワークはほぼ自律的に動作して、ネットワークの障害やブロックを回避できます。動的ルーティングがインターネットを支配します。動的ルーティングプロトコルおよびアルゴリズムの例には、ルーティング情報プロトコル(RIP)、Open Shortest Path First(OSPF)、およびEnhanced Interior Gateway Routing Protocol(EIGRP)が含まれます。

距離ベクトルアルゴリズム

距離ベクトルアルゴリズムは、ベルマンフォードアルゴリズムを使用します。このアプローチでは、ネットワーク内の各ノード間の各リンクにコスト番号を割り当てます。ノードは、パスを介してポイントAからポイントBに情報を送信します。これにより、合計コスト(つまり、使用されるノード間のリンクのコストの合計)が最小になります。

ノードが最初に起動するとき、ノードはそのすぐ隣のノードとそれらに到達するために必要な直接コストのみを知っています。 (この情報(宛先のリスト、各宛先の合計コスト、およびそこに到達するためのデータを送信するためのネクストホップ)は、ルーティングテーブルまたは距離テーブルを構成します。)各ノードは、定期的に各隣接ノードに送信します。知っているすべての目的地に到達するための総コストの独自の現在の評価。隣接ノードはこの情報を調べて、すでに知っている情報と比較します。彼らがすでに持っているものの改善を表すものは何でも、彼らは彼ら自身のテーブルに挿入します。時間の経過とともに、ネットワーク内のすべてのノードが、すべての宛先に最適なネクストホップと合計コストを検出します。

ネットワークノードがダウンすると、それをネクストホップとして使用したノードはエントリを破棄し、更新されたルーティング情報をすべての隣接ノードに伝達します。隣接ノードはこのプロセスを繰り返します。最終的に、ネットワーク内のすべてのノードが更新を受信し、ダウンノードを含まないすべての宛先への新しいパスを検出します。

リンクステートアルゴリズム

リンクステートアルゴリズムを適用する場合、ネットワークのグラフィカルマップは、各ノードで使用される基本的なデータです。マップを作成するために、各ノードは、接続できる他のノードに関する情報でネットワーク全体を氾濫させます。次に、各ノードはこの情報を個別にマップにアセンブルします。このマップを使用して、各ルーターはダイクストラのアルゴリズムなどの標準の最短パスアルゴリズムを使用して、ルーターから他のすべてのノードへの最小コストパスを個別に決定します結果はツリーグラフですルートから他のノードへのツリーを通るパスがそのノードへの最小コストのパスになるように、現在のノードをルートとします。次に、このツリーは、現在のノードから他のノードに到達するための最適なネクストホップを指定するルーティングテーブルを構築するのに役立ちます。

最適化されたリンクステートルーティングアルゴリズム

モバイルアドホックネットワーク用に最適化されたリンクステートルーティングアルゴリズムは、最適化されたリンクステートルーティングプロトコル(OLSR)です。[1] OLSRは積極的です。Hello and Topology Control(TC)メッセージを使用して、モバイルアドホックネットワークを介してリンクステート情報を検出および配布します。Helloメッセージを使用して、各ノードは2ホップのネイバー情報を検出し、マルチポイントリレー(MPR)のセットを選択します。MPRは、OLSRを他のリンクステートルーティングプロトコルと区別します。

パスベクトルプロトコル

距離ベクトルとリンクステートルーティングは、どちらもドメイン内ルーティングプロトコルです。これらは自律システム内で使用されますが、自律システム間では使用されません。これらのルーティングプロトコルは両方とも、大規模なネットワークでは扱いにくくなり、ドメイン間ルーティングでは使用できなくなります。ドメイン内に数ホップを超える場合、距離ベクトルルーティングは不安定になる可能性があります。リンクステートルーティングは、ルーティングテーブルを計算するためにかなりのリソースを必要とします。また、洪水により交通量が多くなります。

パスベクトルルーティングは、ドメイン間ルーティングに使用されます。これは、距離ベクトルルーティングに似ています。パスベクトルルーティングは、各自律システム内の1つのノード(多数存在する可能性があります)が自律システム全体に代わって動作することを前提としています。このノードはスピーカーノードと呼ばれます。スピーカーノードはルーティングテーブルを作成し、それを隣接する自律システム内の隣接するスピーカーノードにアドバタイズします。考え方は、各自律システムのスピーカーノードのみが相互に通信できることを除いて、距離ベクトルルーティングと同じです。スピーカーノードは、自律システムまたは他の自律システム内のノードのパスをアドバタイズします。メトリックではありません。

パスベクトルルーティングアルゴリズムは、各境界ルーターが隣接ルーターに到達できる宛先をアドバタイズするという意味で、距離ベクトルアルゴリズムに似ています。ただし、宛先とその宛先までの距離の観点からネットワークをアドバタイズする代わりに、ネットワークは、それらの宛先に到達するための宛先アドレスとパスの説明としてアドバタイズされます。これまでに通過したドメイン(またはコンフェデレーション)で表されるパスは、到達可能性情報が通過したルーティングドメインのシーケンスを記録する特別なパス属性で運ばれます。ルートは、宛先とその宛先へのパスの属性の間のペアとして定義されます。したがって、名前、パスベクトルルーティング。ルーターは、一連の宛先へのパスを含むベクトルを受け取ります。[2]

パス選択

パスの選択には、ルーティングメトリックを複数のルートに適用して、最適なルートを選択(または予測)することが含まれます。ほとんどのルーティングアルゴリズムは、一度に1つのネットワークパスのみを使用します。マルチパスルーティング、特に等コストのマルチパスルーティング技術により、複数の代替パスを使用できます。

コンピュータネットワークでは、メトリックはルーティングアルゴリズムによって計算され、帯域幅ネットワーク遅延ホップカウント、パスコスト、負荷、最大伝送ユニット、信頼性、通信コストなどの情報をカバーできます。[3]ルーティングテーブルには可能な限り最良のルートのみが格納されますがリンクステートデータベースまたはトポロジデータベースには他のすべての情報も格納される場合があります。

ルートが重複または等しい場合、アルゴリズムは次の要素を優先順に考慮して、ルーティングテーブルにインストールするルートを決定します。

  1. プレフィックス長:宛先をより正確に指定するため、サブネットマスクが長い一致するルートテーブルエントリが常に優先されます。
  2. メトリック:同じルーティングプロトコルを介して学習されたルートを比較する場合は、低いメトリックが優先されます。異なるルーティングプロトコルから学習したルート間でメトリックを比較することはできません。
  3. 管理距離:さまざまなルーティングプロトコルや静的構成など、さまざまなソースからのルートテーブルエントリを比較する場合、管理距離が小さいほど、ソースの信頼性が高く、したがって優先ルートであることを示します。

ルーティングメトリックは特定のルーティングプロトコルに固有であるため、マルチプロトコルルーターは、外部ヒューリスティック使用して、さまざまなルーティングプロトコルから学習したルートから選択する必要があります。たとえば、Ciscoルーターは、管理距離呼ばれる値を各ルートに割り当てます。管理距離が小さいほど、信頼性が高いと想定されるプロトコルから学習されたルートを示します。

ローカル管理者は、ネットワークの使用状況をより細かく制御し、テストを許可し、全体的なセキュリティを向上させるホスト固有のルートを設定できます。これは、ネットワーク接続またはルーティングテーブルのデバッグに役立ちます。

一部の小規模なシステムでは、単一の中央デバイスがすべてのパケットの完全なパスを事前に決定します。他のいくつかの小さなシステムでは、どちらのエッジデバイスがネットワークにパケットを注入するかによって、その特定のパケットの完全なパスが事前に決定されます。いずれの場合も、ルートプランニングデバイスは、ネットワークに接続されているデバイスと、それらが相互に接続されている方法に関する多くの情報を知っている必要があります。この情報を取得すると、A *検索アルゴリズムなどのアルゴリズムを使用して最適なパスを見つけることができます。

高速システムでは、毎秒送信されるパケットが非常に多いため、単一のデバイスですべてのパケットの完全なパスを計算することは不可能です。初期の高速システムは、ある送信元とある宛先の間の最初のパケットに1回パスを設定することにより回線交換でこれに対処していました。同じ送信元と同じ宛先の間のそれ以降のパケットは、回線が切断されるまで再計算せずに同じパスをたどり続けます。その後の高速システムは、1つのデバイスがパケットの完全なパスを計算することなく、ネットワークにパケットを注入します。

大規模なシステムでは、デバイス間に非常に多くの接続があり、それらの接続は頻繁に変更されるため、すべてのデバイスがどのように相互に接続されているかを1つのデバイスで知ることは不可能であり、デバイスを通る完全なパスを計算することはできません。このようなシステムは通常、ネクストホップルーティングを使用します。

ほとんどのシステムは、決定論的な動的ルーティングアルゴリズムを使用します。デバイスが特定の最終宛先へのパスを選択すると、そのデバイスは、他のパスの方が優れていると思わせる情報を受信するまで、常にその宛先への同じパスを選択します。

一部のルーティングアルゴリズムは、決定論的アルゴリズムを使用して、パケットが元の送信元から最終的な宛先に到達するための最適なリンクを見つけません。代わりに、パケットシステムの輻輳ホットスポットを回避するために、いくつかのアルゴリズムは、ランダムに選択された中間宛先にパスをルーティングし、そこから真の最終宛先にパスをルーティングするランダム化アルゴリズム(Valiantのパラダイム)を使用します。[4] [5]多くの初期の電話交換機では、多段スイッチングファブリックを通るパスの開始を選択するためにランダマイザーがよく使用されていました

パス選択が実行されるアプリケーションに応じて、さまざまなメトリックを使用できます。たとえば、Webリクエストの場合、最小遅延パスを使用してWebページの読み込み時間を最小限に抑えることができます。または、バルクデータ転送の場合、最も使用率の低いパスを選択して、ネットワーク全体の負荷を分散し、スループットを向上させることができます。一般的なパス選択の目的は、トラフィックフローの平均完了時間とネットワーク帯域幅の総消費量を削減することです。最近、パスごとにエッジでスケジュールされた合計バイト数を選択メトリックとして計算するパス選択メトリックが提案されました。[6]この新しい提案を含む、いくつかのパス選択メトリックの経験的分析が利用可能になりました。[7]

複数のエージェント

一部のネットワークでは、パスの選択を担当するエンティティが1つもないため、ルーティングが複雑になります。代わりに、複数のエンティティがパスまたは単一のパスの一部の選択に関与します。これらのエンティティが自分の目的を最適化するためのパスを選択すると、複雑化や非効率が生じる可能性があり、他の参加者の目的と競合する可能性があります。

典型的な例は、各ドライバーが移動時間を最小化するパスを選択する道路システムの交通を含みます。このようなルーティングでは、平衡ルートがすべてのドライバーにとって最適なルートよりも長くなる可能性があります。特に、ブライスのパラドックスは、新しい道路を追加すると、すべてのドライバーの移動時間長くなる可能性があることを示しています。

たとえば、ターミナルで無人搬送車(AGV)をルーティングするために使用されるシングルエージェントモデルでは、インフラストラクチャの同じ部分が同時に使用されないように、車両ごとに予約が行われます。このアプローチは、コンテキストアウェアルーティングとも呼ばれます。[8]

インターネットはインターネットサービスプロバイダー(ISP)などの自律システム(AS)に分割されており、それぞれがネットワークに関連するルートを制御します。ルーティングは複数のレベルで発生します。まず、ASレベルのパスは、パケットが流れるASのシーケンスを生成するBGPプロトコルを介して選択されます。各ASには、隣接するASによって提供される複数のパスがあり、そこから選択できます。これらのルーティングの決定は、多くの場合、これらの隣接するASとのビジネス関係と相関しています[9]。これは、パスの品質や遅延とは関係がない場合があります。次に、ASレベルのパスが選択されると、対応するルーターレベルのパスが複数存在することがよくあります。これは、2つのISPが複数の接続を介して接続されている可能性があるためです。単一のルーターレベルのパスを選択する場合、各ISPはホットポテトルーティングを採用するのが一般的です。つまり、パスが宛先までの合計距離を長くする場合でも、ISP自体のネットワークを介した距離を最小化するパスに沿ってトラフィックを送信します。

2つのISP、ABについて考えてみます。それぞれの中に存在があるニューヨークの待ち時間5との高速リンクで接続され、MSはそれぞれの中に存在している-とロンドンは5ミリ秒のリンクで接続します。両方のISPに2つのネットワークを接続する大西洋横断リンクがあるが、Aのリンクの遅延は100ミリ秒、Bのリンクの遅延は120ミリ秒であるとします。Aのロンドンネットワークの送信元からBのニューヨークネットワークの宛先にメッセージをルーティングする場合AはメッセージをロンドンのBすぐに送信することを選択できます。これはAを節約します 高価な大西洋横断リンクに沿って送信する作業ですが、他のルートの方が20ミリ秒高速だった場合、メッセージの遅延は125ミリ秒になります。

インターネットルートの2003年の測定調査では、隣接するISPのペア間で、パスの30%以上がホットポテトルーティングのために遅延が増大し、パスの5%が少なくとも12ミリ秒遅延していることがわかりました。ASレベルのパス選択によるインフレは、実質的ではありますが、主に、利己的なルーティングポリシーではなく、遅延を直接最適化するメカニズムがないことに起因していました。また、適切なメカニズムが整っていれば、ISPは、ホットポテトルーティングを使用するのではなく、協力して遅延を削減することをいとわないことも示唆されました。[10]

このようなメカニズムは、最初に2つのISP [11]の場合、次にグローバルな場合について、同じ著者によって後で公開されました[12]

ルート分析

インターネットとIPネットワークがミッションクリティカルなビジネスツールになるにつれて、ネットワークのルーティング姿勢を監視するための技術と方法への関心が高まっています。誤ったルーティングまたはルーティングの問題は、望ましくないパフォーマンスの低下、フラッピング、および/またはダウンタイムを引き起こします。ネットワーク内のルーティングの監視は、ルート分析ツールと手法を使用して実現されます。[13]

一元化されたルーティング

たとえば、ソフトウェア定義ネットワークを使用して、転送状態を論理的に集中管理できるネットワークでは、グローバルおよびネットワーク全体のパフォーマンスメトリックを最適化することを目的としたルーティング技術を使用できます。これは、MicrosoftのグローバルWAN、[14] FacebookのExpressBackbone、[15]、GoogleのB4などのプライベート光リンクを使用して接続されたさまざまな地理的場所で多くのデータセンターを運営する大規模なインターネット企業によって使用されています[16]最適化するグローバルパフォーマンスメトリックには、ネットワーク使用率の最大化、トラフィックフローの完了時間の最小化、特定の期限より前に配信されるトラフィックの最大化が含まれます。特に、プライベートWANでのフロー完了時間を最小限に抑えることは、研究コミュニティからあまり注目されていません。ただし、プライベートデータセンター間ネットワークを使用して接続されたグローバルに分散したデータセンターを運営する企業の数が増えるにつれ、この分野での研究努力が増える可能性があります。[17]プライベートWANを介したフローの完了時間を短縮する最近の研究では、すべてのキューイングをエンドポイントにプッシュすることにより、グラフ最適化問題としてルーティングをモデル化することが説明されています。著者はまた、無視できるパフォーマンスを犠牲にしながら問題を効率的に解決するためのヒューリスティックを提案しています。[18]

も参照してください

参考文献

  1. ^ RFC 3626
  2. ^ RFC  1322
  3. ^ ルーティングメトリックに関する調査(PDF)、2007年2月10日、2020年5月4日取得
  4. ^ マイケル・ミッツェンマッハー; アンドレア・W・リチャ; Ramesh Sitaraman、「回路ルーティングのためのランダム化プロトコル」、2つのランダムな選択の力:技術と結果の調査(PDF)、p。34
  5. ^ Stefan Haas(1998)、IEEE 1355 Standard:Developments、Performance and Application in High Energy Physics(PDF)、p。15、ネットワークのホットスポットを排除するために、... 2フェーズルーティングアルゴリズム。これには、ランダムに選択された中間宛先に最初に送信されるすべてのパケットが含まれます。中間宛先から最終宛先に転送されます。ユニバーサルルーティングと呼ばれるこのアルゴリズムは、高負荷の条件下で容量を最大化し、遅延を最小化するように設計されています。
  6. ^ M. Noormohammadpour; CSラガヴェンドラ。(2018)。「ポスターの要約:データセンター間ワイドエリアネットワーク上での適応ルーティングを使用したフロー完了時間の最小化」CS1 maint: multiple names: authors list (link)
  7. ^ M. Noormohammadpour; CSラガヴェンドラ。(2018)。「データセンター間ワイドエリアネットワーク上でのアダプティブルーティングを使用したフロー完了時間の最小化」CS1 maint: multiple names: authors list (link)
  8. ^ Jonne Zutt、Arjan JC van Gemund、Mathijs M. de Weerdt、およびCees Witteveen(2010)。運用輸送計画における不確実性への対処RR Negenborn、Z。Lukszo、H。Hellendoorn(編)、Intelligent Infrastructures、Ch。14、pp。355–382。スプリンガー。
  9. ^ マシューシーザーとジェニファーレックスフォードISPネットワークのBGPルーティングポリシーIEEE Network Magazine、ドメイン間ルーティングの特集号、2005年11月/ 12月。
  10. ^ ニール・スプリング、ラトゥル・マハジャン、トーマス・アンダーソン。パスインフレの原因の定量化手順 SIGCOMM2003
  11. ^ ラトゥル・マハジャン、デイヴィッド・ウェザラル、トーマス・アンダーソン。隣接するISP間のネゴシエーションベースのルーティング手順 NSDI2005
  12. ^ ラトゥル・マハジャン、デイヴィッド・ウェザラル、トーマス・アンダーソン。独立したISPとの相互制御ルーティング手順 NSDI2007
  13. ^ Santhi、P。; Ahmed、Md Shakeel; Mehertaj、Sk; マノハール、T。バーラス。ワイヤレスセンサーネットワークにおけるモバイルシンクを使用した認証とペアワイズキー配布の効率的なセキュリティ方法CiteSeerX 10.1.1.392.151 
  14. ^ Khalidi、Yousef(2017年3月15日)。「マイクロソフトが高速で信頼性の高いグローバルネットワークを構築する方法」
  15. ^ 「エクスプレスバックボーンの構築:Facebookの新しい長距離ネットワーク」2017年5月1日。
  16. ^ 「Googleのソフトウェア定義ネットワークの内部」2017年5月14日。
  17. ^ Noormohammadpour、Mohammad; Raghavendra、Cauligi(2018年7月16日)。「データセンターのトラフィック制御:技術とトレードオフを理解する」。IEEE通信の調査とチュートリアル20(2):1492–1525。arXiv1712.03530土井10.1109 /COMST.2017.2782753S2CID 28143006 
  18. ^ Noormohammadpour、Mohammad; Srivastava、Ajitesh; Raghavendra、Cauligi(2018)。「データセンター間WANを介した長いフローの完了時間の最小化について」IEEEコミュニケーションレター22(12):2475–2478。arXiv1810.00169Bibcode2018arXiv181000169N土井10.1109 /LCOMM.2018.2872980S2CID 52898719 

さらに読む

外部リンク