# ネットワークトモグラフィー(Network Tomography) 協調的なエンドツーエンドプローブの観測結果からネットワーク内部(リンクやノード)の性能特性を推定する手法群。binary tomography はその一種で、各エンドツーエンドパスの到達性(up/down)を並べた reachability matrix(到達性行列)とネットワークトポロジを入力に、どのリンクが故障しているかを推定する。モニタが宛先へ定期的にプローブを送り、コーディネータが全モニタの観測を集約してトモグラフィーアルゴリズムを実行する、という3段構成(監視 → 集約 → 推定)を取る。(Source: [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]]) ## binary tomography が実運用で直面する課題 - **入力の質がボトルネックになる**: binary tomography 自体は理論・シミュレーション・オフライン解析で広く検討されてきたが、実運用の監視システムから収集した測定を素朴に適用すると、reachability matrix の不整合により大量の誤警報(false alarm)が発生する。 - 根拠: PlanetLab の実測にそのまま binary tomography を適用すると約1分に1回、企業ネットワークでは約3分に1回の頻度で警報が発生し、実運用に耐えない頻度になる。(Source: [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]]) - **不整合の原因は検知誤りと非同期測定の2つに整理できる**: (1) 一時的でバースト性の高い損失を持続的障害と誤検知する検知誤り(detection error)、(2) 異なるモニタが異なる時刻にプローブを送るため同一リンクの故障を全モニタが同時に捉えられない同期の欠如(lack of synchronization)。 - 根拠: 障害確認(failure confirmation)プロービングで検知誤りを、多サイクル集約(aggregation)戦略で同期の欠如を、それぞれ切り分けて対処すると誤警報を2桁削減できる。(Source: [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]]) ## 未解決の問い - 障害確認・集約の枠組みは binary tomography アルゴリズム自体とどこまで統合して実運用リアルタイム監視システムに組み込めるか(著者ら自身が将来課題として挙げている)。 - マイクロサービス時代のトレースベース RCA(グラフベース・因果推論ベース)と、パスレベルの binary tomography との関係は整理されているか(対象ネットワーク層が異なるが、いずれも「観測から到達不能な内部要因を逆推定する」という構造は共通する)。 ## 未編纂の観察 - [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]] は binary tomography の実用化を阻んできた2つの障害(検知誤りと同期の欠如)を、障害確認と集約戦略という2つの独立した測定手法で切り分けて対処し、Kompella et al. の absolute フィルタリング手法より高い識別率・低い誤警報率を達成したと報告する。 - [識別可能性の形式化] エンドツーエンド経路の二値状態(正常/故障)からノード故障を局所化する能力を、集合レベルの最大識別可能指数 Ω(S) = min_{v∈S} Ω(v) という per-node 特性の関数として厳密に定式化できる(Source: [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]])。プロービング機構(任意経路制御可能/制御可能かつ非巡回/制御不能)ごとに、多項式時間で検証可能な必要十分条件が存在し、制御可能性が高いほど故障局所化能力が大きく向上する(特にスパースな実ネットワークで顕著)。 ## 関連 - [[Fault Localization]] — より広い障害箇所特定の枠組み。ネットワークトモグラフィーはエンドツーエンド能動測定に基づく手法として位置づく。 - [[ネットワークブラックホール]] — binary tomography が検知対象とする代表的な障害クラス。 - [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]] - ソース: [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]] ## 出典 - [[@2009__IMC__Measurement Methods for Fast and Accurate Blackhole Identification with Binary Tomography]] - [[@2017__TON__Network Capability in Localizing Node Failures via End-to-End Path Measurements]](ノード故障局所化の識別可能性を per-node 特性へ還元し、3種のプロービング機構ごとに多項式時間条件を導出)