影響範囲
すべてのリンクとすべてのルーターを一度にテストする。そしてグラフ理論のおかげでそれが 13 ミリ秒で済む理由
Michel Wijnberg
「これを壊したらどうなる？」は、ひとつの対象についての問いです。アーキテクトが実際に答えを 必要としている問いはその逆で、しかもはるかに難しいものです。
このネットワークにあるすべてのうち、どの部分が重要なのか。
リンクを 1 本ずつクリックしていってもそこには到達できません。私のラボの AS 200 にはリンクが 275 本、ルーターが 64 台あります。障害を 1 つずつ手でテストすると 339 回の実験になり、トポロ ジーが変わるたびにやり直しです。
そこで Osprey は、それを全部まとめてやります。それで手に入るのは短いリストです。壊れうる 339 のもののうち、実際に何かを失わせるひと握り。 これは、来四半期に予定する冗長性レビューと、変更を承認する前に走らせるレビューとの差です。
すべてのリンク、すべてのルーター、13 ミリ秒
見出しを読んでください。“1 with impact in 13ms”。その下には何をテストしたかの説明があり ます。“Links whose failure causes device isolation. Redundant links omitted.”
このテナントのリンクはすべて評価されました。そのうちちょうど 1 本、
mia1-cr1 ↔ mia1-gw1 だけが何かを孤立させます。孤立するのはルーター 1 台、mia1-gw1 です。
トグルを Node Failures に切り替えると、答えは鏡像になります。64 台のルーターのうちちょうど
1 台（mia1-cr1）が、ちょうど 1 台を取り残します。
それがアーキテクトの欲しい結果です。読むべき 275 行のリストではなく、そのうち 274 行は証明可 能に退屈だ、という言明です。
同じ弱点を、3 つのプロトコル越しに 3 度見つける
同じ事実の構造的な見方は、専用のレポートに住んでいます。
64 デバイス、解析対象 275 リンク、関節点 1 つ（mia1-cr1、172.16.4.31）と橋リンク 1 本。
関節点とは、取り除くと連結成分の数が増える頂点のことで、「このルーターが死ぬとネットワークが割
れる」のグラフ理論での呼び名です。
ここからが、計画していなかったのにいちばん気に入っている部分です。同じレポートを他の 2 つのテナ ントに対しても走らせてみました。
| テナント | IGP | 関節点 | 橋リンク |
|---|---|---|---|
| Harrier-Broadband | OSPFv2 | mia1-cr1 | mia1-cr1 ↔ mia1-gw1 |
| Kestrel-Dynamics | EIGRP | e-mia1-cr1 | e-mia1-cr1 ↔ e-mia1-gw1 |
| Merlin-Carrier | IS-IS | i-mia1-cr1 | i-mia1-cr1 ↔ i-mia1-gw1 |
3 つのキャリア。3 つの異なる IGP。まったく別々の 3 つの発見経路。OSPF の LSDB ウォーク、
CISCO-EIGRP-MIB のネイバーテーブル、IS-IS の LSP。そのそれぞれに、同じ構造的弱点が、同じ場所
にありました。
正直な説明は、私がテンプレートからラボを作り、マイアミにシングルホームのゲートウェイを 3 回与え
たから、というものです。しかしまさにそれが、これを有用なチェックにしています。同一の物理的ミス
が、互いに無関係な 3 つのプロトコルモデルを通して Osprey に伝えられ、同じ 3 つの答えを生みまし
た。もし IS-IS のトポロジー抽出にバグがあったなら、食い違いが現れるのは i-mia1-cr1 だったはず
です。
ツールに言われるまで、それがラボにあることを私は知りませんでした。何週間もそこにあったのです。 何かを捕まえるために作ったはずのラボの中に。
そこはグラフ理論と切り分けておく価値があります。理論のほうは平凡な半分だからです。関節点も橋 も教科書に載っていて、どんなツールでもどんな図の上でも計算できます。答えに意味があるかどうか を決めるのは、頂点と辺が何であるかです。Osprey のグラフは誰かが保守した図面ではありません。 ルーター自身がフラッディングした内容から再構成されたものであり、だからそこにある橋は、絵につ いてではなく転送についての主張になります。同じアルゴリズムを古びた Visio ファイルに走らせれ ば、形はそっくり同じで、真実は何も残りません。
なぜ答えはマウスを離す前に返ってくるのか
275 の障害シナリオで 13 ミリ秒というのは、巧妙な並列化の成果ではありません。仕事をしないこと の成果です。
取り除くとグラフが分断されるリンクは橋です。どの閉路にも属さない辺のことです。Tarjan の 橋発見アルゴリズムは、深さ優先探索 1 回、O(V+E) で、グラフ全体の橋をまとめて特定します。そし て橋でないリンクは、何かを孤立させることがそもそも不可能です。定義上それは閉路の上にある ので、迂回路が必ず存在するからです。
そこで評価はまず橋を見つけ、それだけをシミュレートします。
// Precompute bridges in O(V+E). These are the only links that can
// cause unreachable devices when removed.
bridgeLinks := spf.FindBridges(baselineMerged)次に、もうひとつのクラスを取り除きます。2 台のルーターが複数の並列リンクで結ばれている場合、 そのどれも、意味のある形での橋にはなりえません。1 本落としても残りがあるからです。
// Parallel links: if a device pair has multiple links, failing any one
// cannot disconnect them. Remove such links from the bridge set.274 本のリンクは、到達性チェックではなく定理によって除外されます。シミュレートされるのは 1 本 だけです。仕掛けはそれだけであり、マウスから手を離す前に答えが返ってくる理由でもあります。この 100 倍の規模のネットワークでも、依然として探索 1 回にわずかなチェックが加わるだけです。
ここでのグラフ理論は飾りではありません。「実行するレポート」と「ちらりと見るレポート」の違いそ のものです。
何も致命的でないとき、「致命的」とは何を意味するか
Critical Pairs タブは、もう一歩外側の問いに答えます。どの 2 本のリンクが、どちらも単一障害点 ではないのに、同時に失われると致命的なのか。
これは本当に厄介な種類のリスクです。どちらのリンクも、どの SPOF レポートにも出てきません。どちら も単独では何も起こしません。両方を取り去ると（同じ管路、同じカード、同じメンテナンス作業）、ネッ トワークが割れます。
それを見つけるには、橋でない辺すべてについて、それを取り除いたうえで残りに対して橋検出を再実行し ます。O(L·(V+E)) であり、このレポートでいちばん高価な処理です。
3 つのテナントすべてで答えはゼロであり、パネルはそれを言葉で述べます。
No critical link pairs detected — your topology has good redundancy.
計算に実際の労力を要したゼロは、長いリストより価値があります。このゼロが言っているのは、このネッ トワークには同時に失われると分断を起こすリンクの組は存在せず、しかもそれは仮定ではなく網羅的に確 認された、ということです。
影響範囲はトポロジーだけではありません
構造は依存関係のひとつの形です。もうひとつの形は到達性であり、その単位はアドレス空間です。
| ピア AS | ピア数 | プレフィックス数 | IP 空間 | CIDR 換算 |
|---|---|---|---|---|
| 100 | 2 | 3 | 131,328 | /15 |
| 300 | 2 | 3 | 131,074 | /15 |
プレフィックス 3 つと聞くとたいしたことはなさそうですが、131,328 アドレス、/15 相当が AS 100 経由でしか到達できない、と表現すると話は変わります。プレフィックスの数は露出量の代理指標とし ては最悪です（/15 も /32 も同じ「1」です）。そこでレポートはアドレス空間に換算し、さらに CIDR 換 算に戻します。それがアーキテクトが実際に考えるときの単位だからです。
その隣で、レポートは各クリティカルペアを、そのメンバーが属する SRLG グループと突き合わせます。 地図の上では独立に見えても管路を共有している 2 本のリンクは、多重化ではなく相関ありとして報告され ます。
そこで、あなたに見つけられるより自分から述べておきたいギャップの話になります。
正直で、まだ完成していない部分
Osprey の SRLG サポートは、ひとつの方向を除いてすべての方向で完成しています。グループを定義し、リ ンクを紐づけ、グループ全体を単一のシミュレーション変異として落とし、依存関係レポートで共有リスクの 相関を見ることができます。できないのは、それを発見することです。
**SRLG テーブルに供給するものが何もありません。**すべてのグループは手入力です。Osprey は IS-IS で 見た RFC 5305 のトラフィックエンジニアリング sub-TLV を生バイトとして保存しますが、SRLG の sub-TLV はまだデコードしていません。したがって、共有リスクグループをすでに IGP で広告しているネットワーク でも、その恩恵は得られません。
供給元より先に消費者を作ってしまったのです。それは順序として間違っており、ロードマップに載っていま す。そしてそれが終わるまで、この機能の正直な説明は「SRLG の発見」ではなく「あなたが教えたグループ に基づく SRLG シミュレーション」です。
評価の途中で誰かに気づかれるくらいなら、私はこの一文を書きます。
私が最初に実行するレポートである理由
明日ネットワークを引き継ぐとしたら、最初に欲しいのは地図ではありません。3 つの問いへの答えです。
- どの単一障害が実際に何かを孤立させるのか。（リンク 1 本。ルーター 1 台。）
- 単一障害のレポートには現れないのに、そうなる障害の組はどれか。（なし。仮定ではなく検証済み。）
- 各外部依存の背後にはどれだけのアドレス空間があるのか。（ピア AS ごとに /15。）
3 つとも、すでに正しいモデルから、1 秒をはるかに下回る時間で、ルーターに触れずに計算できます。モデ ルを先に正しくするために 4 回分の記事を費やした理由は、まるごとそこにあります。正確なモデルは製品で はありません。有用な問いが走るための土台です。
次回は、この記事が静かに避けてきた数字です。そのリンクが落ちたとき実際にどれだけのトラフィックが 動くのか、そしてなぜ私のラボにはそれが分からないのか。 測れないものを推定する。