EIGRPとベルマン–フォード法

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

EIGRPとベルマン–フォード法の違い

EIGRP vs. ベルマン–フォード法

EIGRP（Enhanced Interior Gateway Routing Protocol）は、シスコシステムズの独自ルーティングプロトコルで、IGRPに緩やかに基づいている。 自律システム (AS) 内のルーティングを行うInterior Gateway Protocol（IGP）の通信プロトコルである。 EIGRPは距離ベクトル型ルーティングプロトコルの拡張版であり、ネットワークトポロジーやルーターの帯域幅や処理能力を変更した後のルーティングの不安定さを最小にするよう最適化している。EIGRPをサポートするルーターは、32ビットのEIGRPメトリック（統計）情報を24ビットのIGRPメトリック情報に変換することで、隣接するIGRPルーター用の情報を自動的に再構築する。ルーティング最適化の多くはSRIの開発した Diffusing Update Algorithm (DUAL) に基づいており、ループフリー運用と高速コンバージェンス（収束）機構を提供している。. ベルマン–フォード法 (Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」。G を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、G における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。.

ルーティングプロトコル

ルーティングプロトコル（routing protocol）は、ルーター同士がネットワーク上の任意の2ノード間の経路を選択するための情報をやり取りする通信プロトコルである。.

EIGRPとルーティングプロトコル · ベルマン–フォード法とルーティングプロトコル · 続きを見る »

ダイクストラ法

ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。.

EIGRPとダイクストラ法 · ダイクストラ法とベルマン–フォード法 · 続きを見る »

グラフ理論

ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.

EIGRPとグラフ理論 · グラフ理論とベルマン–フォード法 · 続きを見る »

自律システム (インターネット)

インターネットにおける自律システム (autonomous system) （以下ASと略す）とは、インターネットに繋がるひとつ（時に複数）のルーティングポリシー配下にあるIPネットワークやルータの集合のことを言う。この新しい定義についての詳細はRFC 1930を参照のこと。.

EIGRPと自律システム (インターネット) · ベルマン–フォード法と自律システム (インターネット) · 続きを見る »