Protocol in Code: OSPF Session 07

Bridge

LSDB をそのままではなく router-only graph に変換する

Session 06 までで stable LSDB ができました。Session 07 では、その LSDB を `build_graph()` で adjacency map に変換し、`shortest_path_tree()` で root からの tree に落とします。ここでは最初の teaching model として router-only graph を使い、Network-LSA と transit network vertex は意図的に省きます。

Read The Source

cost, parent, order が SPF の出力になる

if candidate_cost < costs.get(neighbor_router_id, 10**9):
    costs[neighbor_router_id] = candidate_cost
    parents[neighbor_router_id] = router_id

この session のポイントは、SPF の出力が単なる route list ではなく、cost と parent を持つ tree object だということです。Session 08 ではこの tree から route が作られます。

Walkthrough

LSDB に入れた LSA 群から tree を作る

cd protocol-in-code
PYTHONPATH=src python3 examples/ospf/session_07_walkthrough.py

walkthrough では Router-LSA を先に LSDB に install してから、order, `cost_to_2`, `cost_to_3`, `parent_of_3` を見ます。Session 06 の store がそのまま SPF の入力になっていることを確認します。

Done Check

Session 07 を終えたと言える条件

LSDB が graph に変換されてから SPF が走ると説明できる
`costs`, `parents`, `order` の意味を説明できる
次ホップはまだ route に変換していないと説明できる

Next Session

次は tree を route に変えます

Session 08 では `parents` から first hop を戻し、stub network を actual route に変換します。

Back to Session 06 Open Session 08