Loading article…
ヒューリスティック ルーティングは、ネットワーク トポロジで問題が発生した場合に配信を行う方法を説明するために使用されるシステムです。ヒューリスティックとは、学習、発見、または問題解決の方法に関連して使用される形容詞です。ルーティングは、特定の宛先へのパスを選択するプロセスです。ヒューリスティック ルーティングは、世界中の 通信ネットワークおよびトランスポート ネットワークのトラフィックに使用されます。
ヒューリスティック ルーティングは、特定のアルゴリズムを使用して、必ずしも最適ではないものの、よりよい宛先へのパスを決定することで実現されます。ネットワーク トポロジに中断が発生すると、ネットワーク エレクトロニクス上で実行されているソフトウェアは、利用可能な代替パスを経由して目的の宛先への別のルートを計算できます。
Shuster & Schur (1974, p. 1) によると:
問題解決に対するヒューリスティックなアプローチは、人間の知性、経験、常識、および特定の経験則 (またはヒューリスティックス) を適用して、問題に対する許容できる (ただし必ずしも最適ではない) 解決策を開発することです。もちろん、許容できる解決策を構成するものを決定することは、どのアプローチを使用するかを決定する作業の一部です。しかし、広義に定義すると、許容できる解決策とは、適度に良好 (最適に近い) であり、妥当な労力、時間、およびコストの制約内で導き出された解決策です。多くの場合、必要な労力 (人材、コンピューター、およびその他のリソース)、解決策が必要となる時間制限、および決定論的またはその他の複雑な手順に必要なすべてのデータのコンパイル、処理、および分析にかかるコストにより、それらの有用性が損なわれるか、より高速で単純なヒューリスティックなアプローチが有利になります。したがって、ヒューリスティックなアプローチは、決定論的な手法が利用できない、経済的でない、または実用的でない場合に一般的に使用されます。
ヒューリスティック ルーティングを使用すると、ネットワークの状態に関する最新の経験的知識に基づいて、通信ネットワークのルートを最適化することができます。時間 遅延などのデータは、指定された期間にさまざまなルートで受信メッセージから抽出され、ソースにデータを返信するための最適なルーティングを決定するために使用されます。
IPルーティング
現在使用されている IP ルーティング プロトコルは、距離ベクトルまたはリンク ステートの 2 つのアルゴリズムのいずれかに基づいています。距離ベクトルアルゴリズムは、ルーティング情報をすべての隣接ルータにブロードキャストします。リンク ステート ルーティング プロトコルは、隣接ルータからの更新に基づいてネットワーク全体の地形図を作成し、ダイクストラ アルゴリズムを使用して各宛先への最短パスを計算します。使用されるメトリックは、ホップ数、遅延、スループット、トラフィック、および信頼性に基づいています。
距離ベクトルアルゴリズム
- RIPはホップ数、つまり通過したゲートウェイの数を基準として用いる。
- IGRPは帯域幅、遅延、ホップ数、リンクの信頼性、負荷、MTUを使用します。
- EIGRPは（DUAL）拡散更新アルゴリズムを使用する
- BGPは距離ベクトルアルゴリズムを使用する
リンクステートアルゴリズム
- OSPF はDijkstra アルゴリズムを使用します。
参照
参考文献
- Campbell, Ann Melissa; Savelsbergh, Martin (2004). 「車両経路およびスケジュール問題に対する効率的な挿入ヒューリスティック」.交通科学. 38 (3): 369–378. CiteSeerX 10.1.1.499.8006 . doi :10.1287/trsc.1030.0046. JSTOR 25769207.
- Malhotra, Ravi (2002) 。IPルーティング。セバストポル、カリフォルニア州: O'Reilly。ISBN 0596002750. OCLC 49318657.
- Robertazzi, Thomas G. (2007)。ネットワークとグリッド: 技術と理論。情報技術: 伝送、処理、およびストレージ。ニューヨーク: Springer。doi : 10.1007 / 978-0-387-68235-8。ISBN 9780387367583. OCLC 76935739.
- Shuster, Kenneth A; Schur, Dennis A. (1974)。固形廃棄物収集車両のヒューリスティックルーティング。固形廃棄物管理シリーズの環境保護出版物 (SW-113)。ワシントン DC:米国環境保護庁。hdl :2027/ mdp.39015040701149。OCLC 3207134 。
この記事には、連邦規格 1037Cのパブリック ドメイン マテリアルが組み込まれています。一般調達局。2022 年 1 月 22 日にオリジナルからアーカイブされました。