# Network Tomography of Binary Network Performance Characteristics > [!abstract] 概要 > ネットワーク性能トモグラフィでは、リンク損失やパケット遅延といったネットワーク内部の特性を、相関のあるエンドツーエンド測定から推定する。これまでの研究の大半は、マルチキャストパケットまたはそのユニキャストによる模倣といった、パケットレベルの相関を利用することに基づいている。しかし、これらの手法はしばしば適用範囲が限られる――マルチキャストは広く展開されていない――か、追加のハードウェアまたはソフトウェアインフラストラクチャの展開を必要とする。 > 最近のいくつかの研究は、より詳細度の低い目標、すなわち相関のないエンドツーエンド測定のみを用いて最も損失の多いネットワークリンクを識別するという目標の達成に成功している。本論文では、これを可能にするネットワーク性能の性質を抽象化し、高い確度で最悪の性能のリンクを識別する、迅速かつ単純な推論アルゴリズムでそれらを活用する。この必要な性質を示す実際のネットワーク性能指標の例をいくつか示す。さらに、このアルゴリズムは十分に単純であるため、その性能を明示的に解析できる。 ## 論文情報 - 著者: Nick Duffield([[Nick Duffield]]、[[AT&T Labs–Research]]) - 媒体: AT&T Labs–Research テックレポート(D06、PDF 内部メタデータの作成日は 2006-08-22) - 会議発表版の先行報告は ACM SIGCOMM Internet Measurement Conference 2003 の [11](本文参照。強い分離可能ケースの解析結果を証明なしで報告)。本テックレポートはその証明を補い、Section 5(網羅検査)と Section 6(弱分離可能ケース)を新規に追加したもの。 - 入力: `.raw/papers/D06-binary.pdf`(32 ページ)、`.raw/papers/D06-binary.txt` - 埋め込みラスター画像: 0 件(`images_count=0`)。図表 12 件はすべてベクター描画のため PyMuPDF の座標クロップで取得した。 ## 概要 ネットワークトモグラフィ(network tomography)は、リンク単位のパケット損失や遅延といったネットワーク内部の特性を、エンドツーエンドの測定値から推定する分野である。従来手法の主流はマルチキャストパケット、またはそれを模倣する「ストライプ」状のユニキャストパケット群のパケットレベル相関を利用してきたが、マルチキャストは広く展開されておらず、相関ユニキャストの実現にも専用の測定インフラが要る。 本論文は、パケットレベルの相関を一切使わない設定を扱う。すなわち、各 source-to-leaf パス(経路)について「良好(good)」か「不良(bad)」かという 1 ビットの性能測定だけを入力とし、木トポロジ上の bad リンクの位置を推定する。この設定は Padmanabhan・Qiu・Wang(以下 [18])が提案した、Web サーバー側で TCP 再送を観測して損失統計を得る手法に由来するが、[18] の最も精度の高い推定手法は計算コストが非常に高い。本論文は、この設定を成立させる構造的性質(separability、分離可能性)を抽象化し、それを満たす限りにおいて解析的に性能保証できる単純な推論アルゴリズム SCFS(Smallest Consistent Failure Set)を提案する。 ## 問題設定 - ネットワークトポロジは既知の有向木 T = (V, L) として与えられる。根ノード 0 にパケット送信元(サーバー等)、葉ノード集合 R に宛先(クライアント等)が位置する。 - 各リンク k を通過するパケットは、パラメータ φ_k に従って性能劣化(損失・遅延)を受ける。劣化はリンク間・パケット間で独立とする。 - リンクまたはパスの期待統計量 ψ を閾値で「good」「bad」の 2 値に分割する。**分離可能(separable)** とは「パスが bad であることと、そのパス上の少なくとも 1 つのリンクが bad であることが同値」となる性質(A2 は「パスが bad ⇒ 少なくとも 1 リンクが bad」のみを要求する **弱分離可能(weakly separable)** の緩和版)。 - 分離可能な性能モデルは、マルチキャスト木上のパケット損失モデルと構造的に等価であり(badness=パケット損失)、マルチキャスト損失推定で確立された手法群をそのまま転用できる。 - 相関のないエンドツーエンド測定だけでは、木のリンクレベルパラメータ φ は一般に統計的識別不可能(identifiable でない)。図1 が示す 2 葉の木の反例では、2 つの独立測定(葉 2・3 への到達確率)では 3 つのリンクパラメータ φ₁, φ₂, φ₃ を一意に決定できない。 ![[fig01-identifiability-example.png]] *図1: 2 葉の木において、リンク遷移確率 φ₁, φ₂, φ₃ を φ₁x, φ₂x⁻¹, φ₃x⁻¹ に置き換えても(x は max{φ₂,φ₃} と 1/φ₁ の間の任意の倍率)、葉 2・3 へのエンドツーエンド遷移確率は不変である。相関のない測定だけではリンクパラメータが識別不可能であることを示す反例。* ### 分離可能な性能モデルの例 論文は 2.3 節で、分離可能性(または弱分離可能性)を満たす実際の性能指標の例を複数示す。 - **Connectivity**: リンクまたはパスが good なら全パケットを転送し、bad なら 1 つも転送しない。定義から厳密に分離可能。 - **High-Low Loss Model**: 各リンクを独立確率 φ_k で通過するとし、good リンクは φ_k > x、bad リンクは φ_k < y(y < x^ℓ、ℓ は木の深さ)と損失域が離れている場合、パス遷移確率の積に適切な閾値 z を選べば厳密に分離可能になる。[18] の LM1 モデル(good: 損失率 0–1%、bad: 損失率 5–10%)は木の深さが 5 以下なら分離可能。 - **General Loss Model**: 閾値 t を挟んで good/bad を分けると弱分離可能になる。[18] の LM2 モデル(bad リンクの損失率が 1–100% に一様分布)は good/bad の損失域が連続しているため厳密には分離可能でないが、弱分離可能で近似精度を式 (1) で評価できる。 - **General Additive High-Low Model**: リンク性能が独立で統計量 ψ がリンクごとに加法的な(式 (2))モデル一般に拡張できる。損失率の対数、遅延の平均・分散などが該当する。 - **Delay Spike Model**: インターネットの RTT 測定で観測される「遅延スパイク」(中央値で平均 RTT より 16.9 標準偏差高い、中央持続時間 150ms、平均到着間隔 10 秒〜数百秒のポアソン過程)を各リンク上の独立事象としてモデル化すると、[25] の実測データに整合する仮定(A1: 1 パスに複数スパイクが同時発生する確率は小さい、A2: 十分な頻度のプローブがあれば bad リンクのスパイクは少なくとも 1 つのプローブに捕捉される)の下で分離可能になる。 ## 提案手法 ### SCFS(Smallest Consistent Failure Set)アルゴリズム 木の各リンク k に指標変数 Z_k(good なら 1、bad なら 0、根 0 は Z_0=1)を、各ノード k への根からのパス X_k(good なら 1)を定義すると、分離可能性の下で X_k = Π_{j⪯k} Z_j(k とその祖先すべての積)が成り立つ。 葉集合 R_k を k の子孫の葉集合とし、Y_k = max_{j∈R_k} X_j と定義すると、Y_k=1 は「k を通る source-destination パスの少なくとも 1 本が good」を意味する。Y_k=0 かつ親 Y_{f(k)}=1 のとき、k を根とする部分木を **極大な bad 部分木(maximal bad subtree)** と呼ぶ。 SCFS アルゴリズムは、この極大 bad 部分木の根 k だけを bad と判定し、その子孫リンクはすべて good と判定する(最も保守的に「部分木全体を bad」とみなす方式の対極にある、最小限の帰責)。形式的には W′ = {k ∈ U | max_{j∈R_k} X_j = 0}(bad である可能性のある全ノード)から、W = {k ∈ W′ | f(k) ∉ W′}(その中で親が W′ に属さない、すなわち極大なもの)を出力する。木上の再帰で線形時間に実装できる(図2)。 ![[fig02-scfs-pseudocode.png]] *図2: SCFS アルゴリズムの再帰実装。ノード 1 は根 0 の唯一の子。* ![[fig03-scfs-operation-example.png]] *図3: SCFS の動作例。左は各ノードの Y_k の値(bad パスを通るリンク a, b とその部分木の状態は不確定)、右は SCFS が a, b を bad と判定し残りを good とする様子。* ### 網羅検査(Exhaustive Inspection)アルゴリズム SCFS 単発適用では検知率(全 bad リンクのうち正しく bad と判定される割合)が 1 未満にとどまる。これを補うため、SCFS の判定結果を候補として点検・修理し、bad リンクが尽きるまで測定→SCFS→点検を繰り返す反復アルゴリズムを提案する(図6)。各反復で点検されたリンク k は good であることが確定する(点検で good と判明したか、修理されて good になったか)ため、次の反復ではその祖先も good として扱ってよく、探索範囲は単調に絞られる。 ![[fig06-exhaustive-inspection-algorithm.png]] *図6: SCFS の下での網羅検査アルゴリズム。候補 bad リンクが尽きるまで測定・SCFS 適用・点検/修理を繰り返す。* ## 新規性 - パケットレベル相関を必要としない設定([18] が開拓した「サーバー側 TCP 再送観測」の枠組み)において、[18] の最も高精度な手法(Gibbs サンプリング等)より計算量が大幅に小さく、かつ性能を**明示的に解析できる**アルゴリズムを初めて提示した。 - separability(分離可能性)という構造的性質を導入し、多様な実ネットワーク性能指標(接続性・損失率・遅延スパイク)がこの性質を満たす(または弱く満たす)ことを具体例で示した。分離可能な性能モデルはマルチキャスト損失推定モデルと構造的に等価であることも指摘し、マルチキャスト向けに確立された解析手法群を binary 性能推定へ転用する道を開いた。 - 偽陽性率(FPR)と検知率(detection rate)の**閉形式の理論限界**を導出した(Theorem 1〜7)。特に bad リンクが稀(α → 1)な極限での漸近挙動(Theorem 4, 6)を明示的に与えた。 - 弱分離可能ケースへの一般化として **critical link(臨界リンク)** の概念を導入し、厳密な分離可能性からの逸脱の影響を臨界確率 K_k で定量化した(Theorem 7)。 - SCFS に反復点検を組み合わせた網羅検査アルゴリズムの検査オーバーヘッド(bad リンク数に対する超過検査数の割合)も式 (22)–(39) の再帰で解析し、深い木でも小さいことを示した。 - 会議報告版 [11] の解析結果(厳密分離可能ケースの証明なし結果)に証明を与え、Section 5(網羅検査)・Section 6(弱分離可能ケース)を新規に追加した。 ## 実験設定 本論文は主に理論解析(定理と証明)であり、実験は次の 3 種類に限られる。 1. **モデルベースの数値計算**: 均一分岐比・均一 α のモデル木 T_α(r₁,...,r_n) に対し Mathematica でシンボリック計算した検知率 C・偽陽性率 FPR を、分岐比 r=2,3,10、木の深さ 2〜5、および一定パス障害率スケーリング(α^{1/d})の下でプロットした(図4図5図7図10、表1)。 2. **実測損失率データへの適用**: [25](Zhang, Duffield, Paxson, Shenker, ACM SIGCOMM IMW 2001)が測定した 3,779 本のインターネットパスの 1 時間平均損失率の累積分布(図8)を用いて、損失閾値ごとの臨界確率 K と FPR 増分 Θ を木の深さ 5, 15, 50 で評価した(図9)。 3. **他手法との比較**: [18](random / linear programming / Gibbs sampling)の LM1 モデル(1,000 ノード、最大分岐比 10、深さ 3〜10 の 10 トポロジ)に対する自モデル計算との比較(表2)、および [3](Batsakis, Malik, Terzis, PAM 2005)による ns-2 シミュレーション(BRITE 生成の 800 ノード・1,400 リンク、100 クライアントのファイルダウンロードトラフィック、SCFS・random・Gibbs・COBALT の比較)の結果を引用した比較。 ## 実験結果 ![[fig04-fpr-bounds.png]] *図4: bad リンク識別の FPR_k 上界(worst case・best case)を good リンク割合 α の関数として、分岐比 r=2,3,10 についてプロット。α が 1 に近づくほど平坦化し、FPR は小さい α への感度が低い。* ![[fig05-detection-rate.png]] *図5: 検知率 C を α の関数として、左は分岐比への非感度、中央は木の深さ増加による低下、右は一定パス障害率スケーリング下での深さへの非感度を示す。* ![[table01-detection-rate-comparison.png]] *表1: 検知率 C の厳密値と、Theorem 6 による近似 1−C′(1)ᾱ・下界 1−ℓᾱ の比較(均一木 T_α(2,2) 等)。α=0.95 で近似誤差は数 % 以内。* ![[fig07-inspection-overhead.png]] *図7: 均一木における検査オーバーヘッド(%)。左は分岐比の関数、右は木の深さの関数。深さ 6・α=0.8 の最悪ケースでもオーバーヘッドは 10% 未満。* ![[fig08-path-loss-cdf.png]] *図8: [25] の実測パス損失率(3,779 パス、1 時間平均)の累積分布関数。横軸は対数スケール。* ![[fig09-critical-probability-and-fpr-increase.png]] *図9: 図8 の損失率分布を仮定した臨界確率 K(左)と FPR 増分 Θ(右)を損失閾値の関数として、深さ 5, 15, 50 についてプロット。臨界確率は損失率 0.01〜0.03 付近で最小の U 字型を示す。* ![[table02-1000-node-tree-summary.png]] *表2: 約 1,000 ノードの木での FPR F・検知率 C・一定パス障害率スケーリング下の検知率 C⁰ を α=0.95, 0.9, 0.8 について要約。* ![[fig10-fixed-point-iteration.png]] *図10: B_{α,r}(x)=α(1−(1−x)^r) の不動点反復の図示(r=3, α=1/2)。恒等関数との交点が β*(α,r)。* 主要な数値結果: - 二分木(分岐比 2)・深さ 5・α=0.95(損失閾値 1%)の厳密分離可能ケースで FPR_k ≈ 0.0025、最悪ケースの検知率 C_k ≈ 0.7。 - 約 1,000 ノードの木・α=0.95 で FPR は 0.0%〜0.08%、検知率は 59%〜81%(一定パス障害率スケーリング下の検知率 C⁰ は 95%)。 - [18] の LM1 モデルとの比較(表2 vs. [18] 図3・4)で、α=0.95 では SCFS の FPR が [18] のどの手法よりも小さく、検知率も linear programming・Gibbs と同等。ただし α が小さくなると検知率は [18] の他手法より急速に低下する。 - [3] のシミュレーション比較では、SCFS の FPR は次点手法の約 3 分の 1。検知率は bad リンクが稀(5%)な条件では他手法と同等だが、bad リンクが多い(20%)条件では低下する。他手法も α=0.95, 0.9, 0.8 の範囲で検知率は約 65% にとどまり、完璧ではない。 - 弱分離可能ケース([18] LM2 型、α 小・閾値 t≈1 の極限)では、二分木・深さ 5・α=0.95・t=0.99 で FPR_k ≈ 0.015(厳密分離可能ケースの 0.0025 と比較)、C_k ≈ 0.65(同 0.7 と比較)。実測損失率分布(図8)を用いた解析では、損失閾値 1% で Θ ≈ 0.19(対応する厳密分離可能ケースの FPR 上界は約 0.06)。 ## 考察 - SCFS の低い FPR と、[18] の高精度手法(Gibbs サンプリング)に対する 1 桁少ない計算量([3] の報告)は、ネットワーク管理の実務では「誤って良好なリンクを点検・修理するコスト」が高いという前提と整合する。著者はこのトレードオフ(FPR と検知率)の選好は文脈依存であるとしつつ、ネットワーク運用では FPR を抑える設計を支持すると論じる。 - SCFS 単発適用の検知率不足は、相関測定を用いる従来のトモグラフィ手法(推定量が漸近的に不偏)と対照的な「不確定性のコスト」だが、反復網羅検査により検知率を実質 1 まで引き上げられ、そのオーバーヘッドは小さい。 - 弱分離可能ケースへの拡張(critical link・臨界確率 K_k)は、分離可能性という理想化された仮定からの逸脱の影響を定量化する枠組みを与える。LM2 型モデルでは損失分布が閾値付近に偏っている(power law の指数 p>1)ほど臨界確率が下がり、分離可能近似の精度が悪化することを示した。 - Section 8 では、状態空間の拡張(good/bad の 2 値を超える分類)、木以外の一般トポロジへの拡張([5] の木被覆アプローチの応用)、時系列測定からのリンク確率推定(Gilbert モデル、[6] のマルチキャスト損失推定法への還元)を将来課題として挙げている。 ## 強み / 弱点・課題 **強み** - separability という単純な構造的仮定のもとで、FPR・検知率の閉形式の理論限界を導出し、実験(モデルベース数値計算・実測損失率データ)で検証している。 - アルゴリズム自体は木上の 1 回の再帰で計算でき、[18] の高精度手法に比べ計算量が大幅に小さい。 - 弱分離可能ケースへの拡張により、厳密な分離可能性が成り立たない実務的な状況への適用可能性も定量的に評価している。 **弱点・課題** - SCFS 単発適用の検知率は α が小さくなると急速に低下し、[18] の他手法(linear programming・Gibbs)に劣る場面がある(著者自身が認める限界)。 - 前提となるトポロジ(木構造)は既知として扱われ、一般トポロジへの拡張は [5] の木被覆アプローチへの言及にとどまり本論文では未実施。 - good/bad の閾値(ambient failure probability)は事前に既知として扱われ、閾値を測定データから適応的に決める方法は将来課題として残されている(著者は単純なクラスタリングでは閾値決定が失敗しうる反例を挙げている)。 - 実測データへの適用は 図8/9 の 1 データセット([25])に限られ、動的(時変)な bad/good 状態への拡張(Gilbert モデル)は概念のみで実装・評価されていない。