ルーティングプロトコル

ルーティングプロトコルは各ルーターの次ホップ表を作ります。距離ベクトルは「C までのコストは X」という数値を交換し、古い通知が隣接ルーター間のループを起こすことがあります。リンクステートはトポロジーをフラッディングし、各ルーターが Dijkstra を実行します。本例の 3 ノードでは、リンク切断後の地図を適用するとパケットを破棄します。

道を知る方法に例えると、距離ベクトルは隣人に「パン屋まで何分か」を聞く方法、リンクステートは道路地図を交換する方法です。道が閉鎖されても古い所要時間を信じると、隣人同士で道を教え合うループになります。更新済みの地図なら経路がないと分かります。パケット自体は地図を持たず、その地点の次ホップに従います。

Dijkstra や Bellman–Ford は計算に必要な入力を前提とします。この教材では、入力をルーター間で伝える過程と、古い情報がループを作る仕組みを扱います。

ルーティングプロトコルの仕組み

転送表の仕事は「宛先 C をどの隣人へ渡すか」を答えることです。ルーティングが表を書き、転送が表を読みます。カードは dest C とだけ表示し、A—B—C という全経路は持ちません。

距離ベクトルは分散 Bellman–Ford です。隣人 nbr が nbr_cost を通知すると、cand = nbr_cost + link_cost を計算します。コストが改善した場合、または通知元が現在の次ホップである場合に更新します。後者では悪化した値も受け入れます。この条件を消すと古い低コストを保持し、ループしてもコストが増えません。条件があれば RIP の無限大 16 へ数え上げ、経路を無効にします。

RIP のスプリットホライズンとポイズンリバースはこの 2 ノードのループを防げますが、3 ノード以上のループすべてを防ぐ保証はありません。本例はそれらを使わない単純な方式です。クイズでは、この直線に導入すると何が変わるかを問います。

リンクステートは OSPF に似た方式です。各ルーターは「利用できる隣接リンク」を LSA で通知し、フラッディングします。C へのコストを交換するのではありません。LSDB に地図がそろうと table = dijkstra(lsdb, dest) を実行します。リンクが切れれば新しい LSA で辺を削除し、到達経路がなければ ∞。次の転送検索は破棄になります。

これは 3 ノードの直線で、新しい LSA を適用した後の結果です。実際のリンクステートも LSDB の不一致中に一時的なループを作り得ます。画面は共有地図でその過程を簡略化しています。

ルーティングプロトコルのステップ

初期設定は Distance Vector の Contrast。A —1— B —1— C、宛先 C です。空の表から収束して配送した後、B—C を切断し、距離ベクトルのループとリンクステートの破棄を比較します。

1. A は C 宛てのパケットを持つが次ホップがない。 A と B は ∞、C は 0 / local。dest C が待機し、有効なコスト表示はまだありません。
2. C が B に C: 0 を通知。 数値だけで、経路ではありません。
3. B が 1 via C を記録。 cand = 0 + 1 = 1 < ∞。
4. B が A に C: 1 を通知。 表の変更が通知を起こします。
5. A が 2 via B を記録。 cand = 1 + 1 = 2。上部に A = 2 via B を表示します。
6. 表が安定。 次ホップは A → B → C。単独の Converge では A が C: 2 を B に返し、B が無視する過程も示します。Contrast は省略します。
7. A にデータパケット。 dest C を見て、次ホップ B を得ます。
8. A から B へ。 forward は次ホップだけを読みます。
9. B から C へ。
10. C で配送。 宛先に一致します。パケットは全経路を保持していません。
11. B—C が切断。 最後のリンクに赤い × が付きます。
12. B が ∞ を記録。 次ホップが消え、on_link_down が advertise を予約します。
13. 通知順を表示。 1 A:C2 はすでに転送中、2 B: pending はその後です。B の更新は送信時に初めて自分の表を読みます。先に届く古い通知が競合を作ります。
14. A の定期通知 C: 2 が先着。 値は古いままです。
15. B が 3 via A を記録。 cand = 2 + 1 = 3 < ∞。しかし A の 2 自体が B 経由でした。
16. B が A に C: 3 を通知。
17. A が 4 via B を記録。 nbr == route.next なので、悪化した通知も受け入れます。
18. A に新しいパケット。 A は B、B は A を指します。
19. A から B へ。
20. B から A へ戻る。 これがループです。
21. カウントが増加。 3/4 → 5/6 → … → 15/16 をまとめて示し、表は B = 15 via A、A = ∞ へ移ります。RIP は 16 を到達不能とします。ループはすでに 3/4 で起きています。
22. リンクステートへ切り替え。 左側に距離ベクトルのループを固定表示し、表は地図に従います。宛先 C と B—C の切断は同じです。
23. B が LSA B {A:1} をフラッディング。 C へのコストではなく、隣人を示します。
24. LSDB から B—C を削除。 辺は 1 本だけになり、C への経路がありません。
25. Dijkstra が A、B に ∞ を記録。 数え上げは不要です。
26. A にパケット。 次ホップは None。
27. next is None → drop。 距離ベクトルでループしたのと同じ宛先 C です。
28. 両方の結果を残す。 DV は A=4 via B、B=3 via A のループ時点を固定表示。LS は両方 ∞ で、A が破棄します。

Contrast で Protocol を Link State にすると、2 個の LSA、1 回の Dijkstra、配送、切断後の破棄を先に示し、DV のループを静止画で比較します。Converge と Link down は各方式を単独で再生します。

障害時に何を見るか

最終リンクが切れても RIP 型の表に有限コストが残る場合、次ホップを確認してください。相互に相手を指していれば、制御側が数え上げている間にパケットは循環し、TTL が尽きます。

OSPF の LSA 撤回後に経路が消えた場合は、LSDB と隣接関係のログを見ます。地図に道がなければ破棄は正しい結果です。ルーター間で地図が違うなら、フラッディングの遅延、SPF の実行待ち、未反映の表など、教材が省いた過渡状態を調べます。

ルーティングは表を書き、転送は表を読みます。有限のコストがあるだけではループを否定できず、空の次ホップによる破棄も必ずしも転送処理の故障ではありません。

数値と地図の違い

Dijkstra にはグラフが必要です。ルーティングプロトコルがグラフや距離情報を集めます。距離ベクトルはコストの作り方を知らせません。A の古い 2 が B に依存していても、B は通知からそれを見抜けません。

LSA は隣接関係を伝えます。各関係が LSDB に集まって初めて、各ルーターが最短路計算を行えます。新しい仕組みはフラッディングです。

転送は A で next = B を読むだけです。各表の検索が有効でも、組み合わせると A ↔ B のループになります。

境界条件

• 収束時の悪い候補。 Converge では A の C: 2 を B が受け取ります。B は直接 C へコスト 1 で届くので、< 条件で候補を拒否します。
• 宛先自身の経路。 C の 0 / local は通知で上書きされません。
• リンク切断時の競合。 B は更新を予約しますが、A の定期通知はすでに移動中で先に届きます。raceOrder が順番を示し、B の更新は送信時に表を読むため ∞ ではなく 3 を通知します。
• 16 まで数える。 3/4 → … → 15/16 は後続交換の圧縮表示。A は 16 で次ホップを消しますが、パケットはコスト 4 の時点でループ済みです。
• 代替経路なし。 A—C の予備リンクはありません。B—C 切断後は C に到達できず、途中で別経路が勝つ展開にはなりません。
• 空の次ホップ。 LSDB 更新後は forward の nxt is None で破棄します。
• スプリットホライズンは省略。 A が B 経由の経路を B に戻さなければこの 2 ノードのカウントは防げますが、長いループは残り得ます。

よくある間違い

• ルーティングを Dijkstra と同一視する。 DV は全体地図を作りません。LS は地図を作ってから Dijkstra を呼びます。
• パケットが経路を持つと思う。 最初の fwdHop で止めると dest C しかありません。次ホップは A の表から得ます。
• nbr == route.next を消す。 B が 3 を知らせても A は 2 via B のまま。ループは消えず、カウントだけが止まります。
• スプリットホライズンで全ループを防げると思う。 この直線の 2 ノードには効きますが、3 ノードのループをなくす保証はありません。
• リンクステートは決してループしないと思う。 本例は LSA 適用後の 3 ノード直線です。地図の不一致中は一時的なループが起こり得ます。
• ∞ を利用可能なコストと読む。 コードは RIP の整数 16 を到達不能に使い、表は最短路の記号と合わせて ∞ と描きます。

モデルの簡略化

DV は単純な Bellman–Ford で、スプリットホライズン、ポイズンリバース、ホールドダウン、RIP の invalid/flush タイマーはありません。無限大は 16 です。LS は OSPF に似たフラッディングと 1 回の Dijkstra だけで、エリア、指定ルーター、LSA タイプ、hello/dead 間隔を省略します。

宛先は 1 つ。画面は共有 LSDB ですが、コードはルーターごとの lsdb[node] を持ち、フラッディングで一致させます。C の LSA は新しい無向辺を増やさないので省略します。BGP、ポリシー、最長プレフィックス一致は別の範囲です。