Best Path Selection As If Statements

Session Goal

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

Session 03 のゴールは、best path selection を「BGP がなんとなく選んだ」ではなく、「どの if 文が最初に勝敗を決めたか」で説明できるようになることです。

• 複数 path がないと best path logic は動かないと説明できる
• comparison order が結果を変えると説明できる
• 最初に差がついた field を言える
• `best` と `authorized` を混同しないと説明できる

Core Idea

select_best_path() は「最初に勝った条件」で決まる

同じ prefix に対して複数 path が table に入ってきたとき、router は 1 本を best に選びます。ここで大事なのは、比較は一気に行われるのではなく、順番に条件を見ていくことです。

Read Order

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

1. PathCandidate を読んで、比較材料が何か先に掴む
2. _is_better() を読んで、比較順序を上から追う
3. select_best_path() を読んで、複数 candidate が 1 本に潰れる流れを見る
4. walkthrough script を実行して、各 scenario の「最初の勝因」を確認する

Read The Source

優先順位表ではなく実際の if 文で読む

def _is_better(candidate: PathCandidate, current: PathCandidate) -> bool:
    if candidate.weight != current.weight:
        return candidate.weight > current.weight
    if candidate.local_pref != current.local_pref:
        return candidate.local_pref > current.local_pref
    if len(candidate.as_path) != len(current.as_path):
        return len(candidate.as_path) < len(current.as_path)
    if candidate.origin_type != current.origin_type:
        return candidate.origin_type < current.origin_type
    return candidate.next_hop < current.next_hop

実装やベンダーごとの差はありますが、学ぶときの骨格としてはこの読み方が役に立ちます。「全部の条件を同時に眺める」のではなく、「どこで差がついたか」を探すのです。

What To Compare

PathCandidate の field が比較材料になる

best path selection は path が 1 本しかないなら動きません。だからこのロジックを読むときは、最初に same prefix, multiple paths という前提が必要です。

Competing Paths

select_best_path() は 2 本以上を順番に潰していく

Lab 03 のように 1 つの prefix に 2 本の path が見えると、best path logic を読む練習になります。重要なのは「2 本見えている」という事実と、「どの条件で 1 本に決まったか」を分けて考えることです。Lab 03 は optional context で、この session 自体は GitHub source reading だけで完結します。

def select_best_path(paths: list[PathCandidate]) -> PathCandidate:
    if not paths:
        raise ValueError("at least one path is required")

    best = paths[0]
    for candidate in paths[1:]:
        if candidate.prefix != best.prefix:
            raise ValueError("all compared paths must be for the same prefix")
        if _is_better(candidate, best):
            best = candidate
    return best

Why This Matters

「best だから正しい」とは限らない

best path selection は、あくまで router が 1 本を選ぶためのロジックです。authorized かどうか、leak かどうか、policy 的に正しいかどうかは別の問いです。ここを混ぜないことが中級での大事なポイントです。

Walkthrough

比較順序がどう勝敗を決めるかを見る

GitHub repo 側には Session 03 用の walkthrough script を置いてあります。weight、local_pref、AS_PATH length、origin_type がそれぞれ最初の勝因になる scenario を流し、なぜその path が選ばれたかを見ます。

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

Done Check

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

• 最初の differing condition が勝者を決めると説明できる
• AS_PATH が短くても earlier branch で負けることがあると説明できる
• select_best_path() が pairwise comparison で 1 本に潰していくと説明できる
• best path selection と route authorization は別の問いだと説明できる

Next

次は best path の外側で authorization を見る

ここまでで router が 1 本の path をどう選ぶかは読めました。ただし、その path が authorize されているかは別問題です。次は GitHub 上の validation.py を開いて、best path と origin authorization を分けて読みます。