How UPDATE Changes State

Session Goal

このセッションで終わらせたいこと

Session 02 のゴールは、UPDATE を「パケット形式」としてではなく、「routing table を書き換える操作の列」として説明できるようになることです。

• `NLRI` と `Withdrawn Routes` の役割の違いを言える
• route disappearance と session failure を言い分けられる
• `path_attributes` が announcement に付いてくる理由を言える
• 1 つの UPDATE が removal と addition を両方含めうると説明できる

Core Idea

RoutingTable に対する mutation として UPDATE を読む

update.py では、BGP の route table を RoutingTable として表し、その上で apply_update() と withdraw() を呼びます。だから UPDATE を読むときは、パケットフォーマットを暗記するより先に、「この message は table に何をするのか」を見ます。

Read Order

この順番で読むと迷いにくい

1. PathAttributes を読んで、announcement に何が載るか掴む
2. BGPUpdate を読んで、message が何を持てるか見る
3. RoutingTable.apply_update() と withdraw() を読んで、table 側の mutation を理解する
4. apply_update_message() を読んで、処理順序を追う
5. walkthrough script を実行して、table の変化を目で確認する

Read The Source

UPDATE 1 個を 2 種類の操作へ分解する

@dataclass
class RoutingTable:
    paths_by_prefix: dict[str, list[PathAttributes]] = field(default_factory=dict)

    def apply_update(self, prefix: str, attributes: PathAttributes) -> None:
        self.paths_by_prefix.setdefault(prefix, []).append(attributes)

    def withdraw(self, prefix: str) -> None:
        self.paths_by_prefix.pop(prefix, None)

同じ UPDATE message の中に Withdrawn Routes と NLRI があるとき、実際には「消す操作」と「足す操作」が同居しています。source 上でもそれぞれ別メソッドになっているので、読み分けやすくなります。

Toy Model Boundary

ここでは prefix-wide simplification を使っています

この lesson の RoutingTable.withdraw() は、prefix 全体を table から消す最初の toy model です。後続の Session 06 と Session 09 では、同じ prefix でも peer ごとに別 path が残りうるように、Adj-RIB-In の per-peer state へ refine します。

Message Flow

apply_update_message() が実際の順番を示す

def apply_update_message(table: RoutingTable, update: BGPUpdate) -> RoutingTable:
    for prefix in update.withdrawn_routes:
        table.withdraw(prefix)

    if update.path_attributes is None:
        return table

    for prefix in update.nlri:
        table.apply_update(prefix, update.path_attributes)

    return table

この関数を見ると、route は「現れる」「消える」「戻る」と説明できます。Lab 02 で見える route の出現、消失、再出現も、この mutation の列として読むと整理しやすくなります。Lab 02 は optional context で、この session 自体は GitHub source reading だけで完結します。

Attributes

PathAttributes が一緒に運ばれる

announcement が起きるとき、ただ prefix が届くのではなく、ORIGIN、AS_PATH、NEXT_HOP が一緒に届きます。つまり apply_update() の引数は prefix だけでは足りません。

@dataclass(frozen=True)
class PathAttributes:
    next_hop: str
    as_path: tuple[int, ...]
    origin: str
    local_pref: int = 100

Walkthrough

手元で table mutation を順番に流す

GitHub repo 側には Session 02 用の walkthrough script を置いてあります。announcement、second path、withdrawal、複数 prefix、同一 UPDATE 内の remove + add を順番に流し、table がどう変わるかを見ます。

cd protocol-in-code
PYTHONPATH=src python3 examples/bgp/session_02_walkthrough.py

Done Check

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

• withdrawal は prefix を table から消す操作で、session down そのものではないと説明できる
• announcement には prefix だけでなく path attributes が必要だと説明できる
• apply_update_message() が withdrawals を先に処理する理由を説明できる
• 1 つの UPDATE が remove と add を同時に含めても不思議ではないと説明できる

Next

次は best path を条件分岐として読む

UPDATE によって複数の path が table に入ったあと、どれが best になるかを決めるのが Session 03 です。次は GitHub 上の best_path.py を開いて、優先順位表をそのまま覚えるのではなく、if ... else if ... として読みます。