algorithm - ベルマンフォードアルゴリズムで無限に数える原因となる可能性があるもの

Question

私が理解できることから、無限にカウントすることは、あるルーターが別の古い情報をフィードするときに発生し、それはネットワークを介して無限に向かって伝播し続けます。私が読んだところによると、これはリンクが削除されたときに間違いなく発生する可能性があります。

したがって、この例では、ベルマンフォードアルゴリズムがルーターごとに収束し、ルーターごとにエントリがあります。R2は、1のコストでR3に到達できることを認識し、R1は、2のコストでR2を介してR3に到達できることを認識します。

R2とR3の間のリンクが切断されている場合、R2は、そのリンクを介してR3に到達できなくなったことを認識し、テーブルから削除します。更新を送信する前に、R1から更新を受信する可能性があります。これは、2のコストでR3に到達できることをアドバタイズします。R2は1のコストでR1に到達できるため、次のルートを更新します。 R3はR1を介して3のコストでR1を経由します。R1は後でR2から更新を受け取り、そのコストを4に更新します。その後、彼らはお互いに悪い情報を無限に送り続けます。

私がいくつかの場所で言及したことの1つは、リンクのコストを変更するなど、リンクがオフラインになるだけでなく、無限にカウントする他の原因が存在する可能性があることです。私はこれについて考えるようになりました、そして私が言うことができることから、おそらくリンクのコストが増加することが問題を引き起こす可能性があるように思われます。しかし、コストを下げることで問題が発生する可能性はないと思います。

たとえば、上記の例で、アルゴリズムが収束し、R2に1のコストでR3へのルートがあり、R1に2のコストでR2を経由してR3へのルートがある場合、R2とR3の間のコストが5.次に、これにより同じ問題が発生します。R2はR1から更新を取得してコスト2をアドバタイズし、R1を介してコストを3に変更し、次にR2を介してルートを4に変更します。ただし、コンバージドルートでコストが下がれば、変化はありません。これは正しいです？問題を引き起こす可能性があるのはリンク間のコストの増加であり、コストの減少ではありませんか？他に考えられる原因はありますか？ルーターをオフラインにすることは、リンクが切れることと同じでしょうか？

Answer 1

この例を見てください：

ルーティング テーブルは次のようになります。

    R1   R2    R3
R1  0    1     2
R2  1    0     1
R3  2    1     0

ここで、R2 と R3 の間の接続が失われたとします (回線が切断されたか、それらの間の中間ルーターが落ちた可能性があります)。

情報の送信を 1 回繰り返すと、次のルーティング テーブルが得られます。

    R1   R2    R3
R1  0    1     2
R2  1    0     3
R3  2    3     0

これは、R2、R3 が接続されなくなったため、R2 がパッケージを R1 経由で R3 にリダイレクトできると「考え」、パスが 2 であるため、重み 3 のパスを取得するために発生します。

追加の反復の後、R1 は R2 が以前よりも高価であることを「認識する」ため、ルーティング テーブルを変更します。

    R1   R2    R3
R1  0    1     4
R2  1    0     3
R3  4    3     0

など、正しい値に収束するまで続けますが、特に (R1,R3) が高価な場合は、長い時間がかかる可能性があります。
これは「無限にカウントする」と呼ばれます (w(R1,R3)=infinityと が唯一のパスである場合、無限にカウントし続けます)。

---

2 つのルーター間のコストが上昇すると、同じ問題が発生することに注意してください (w(R2,R3)上記の例では 50 まで上昇すると想定しています)。同じことが起こります -も依存することを「認識」せずにviaR2にルーティングしようとし、正しいコストを見つけたら同じ最初のステップを取得して収束します。ただし、コストが下がった場合 (新しいコストは現在のコストよりも優れているため発生しません)、ルーターはコストが下がった同じルーティングに固執し、 を経由しようとしません。R3R1(R2,R3)
R2R1

Answer 2

ウィキペディアによると：

RIP は、ポイズン リバース技術を使用したスプリット ホライズンを使用して、ループが形成される可能性を減らし、最大ホップ数を使用して「無限カウント」の問題に対処します。これらの対策により、すべてではありませんが、一部のケースでルーティング ループの形成が回避されます。ホールド タイムを追加すると (ルートの撤回後に数分間ルートの更新を拒否する)、事実上すべてのケースでループの形成が回避されますが、収束時間が大幅に増加します。

最近では、多くのループフリー距離ベクトル プロトコルが開発されました。注目すべき例は、EIGRP、DSDV、および Babel です。これらはすべてのケースでループの形成を回避しますが、複雑さが増すという問題があり、OSPF などのリンクステート ルーティング プロトコルの成功により展開が遅くなりました。

http://en.wikipedia.org/wiki/Distance-vector_routing_protocol#Workarounds_and_solutions

Answer 3

これは、質問のベルマンフォードアルゴリズムの部分を認めていませんが、これは単純化された回答です。ここに行きます。

元のポスターの画像に注目してください。R1、R2、R3 があります。それぞれルーター 1、2、および 3 を表します。

各リンクには 1 のコストがかかり、各ホップには 1 のコストがかかります。2 つのルーター (例: R1 から R3) をホップするには、2 のコストが必要です。

各ルーターはコストを追跡し、情報を更新します。ただし、値が欠落している場合 (ルーター間のリンクが欠落している場合など) は、ホップ カウントが削除され、ルーティング テーブルが更新されたときに別のルーターによって埋められます。

例：

ルーター 3 からルーター 2 へのリンクがダウンすると、ルーター 2 はそのルートをテーブルから削除します。ルーター 1 は、ルーター 3 に到達するには 2 ホップかかるとまだ考えています。これはルーター 2 に複製され、両方のルーターがルーター 3 に到達するには 2 ホップかかると考えています。

ルーター 1 は簡単な計算を行います。「ルーター 2 に到達するのに 1 ホップかかり、ルーター 2 がルーター 3 に到達するのに 2 ホップかかるとすると、ルーター 3 に到達するのに 3 ホップかかるはずです。すばらしい!」ルーター 2 は同様の計算を行い、そのルートに 1 つのホップを追加します。

これがループの仕組みです。