# Automatic Alarm Correlation for Fault Identification > [!abstract] 概要 > 通信ネットワークには、ネットワークの異常な挙動を知らせるための多数のアラームが存在する。ネットワーク障害は典型的に多数のアラームを引き起こすため、これら異なるアラームを相関付けその発生源を特定することは障害管理における主要な問題である。アラーム相関問題は実務上大きな重要性を持つ。相関付けられなかったアラームは、不十分な情報に基づく重大な誤った対処を招くだけでなく、各アラートが独立に処理されることで複数の(場合によっては矛盾する)是正措置を引き起こしかねない。本論文は、アラーム相関問題を解くための一般的な枠組みを提案する。我々は確率的有限状態機械(probabilistic finite state machine)に基づく障害とアラームの新しいモデルを導入する。我々は2つのアルゴリズムを提案する。第1のアルゴリズムは、不完全かつ不正確な可能性のあるデータから出発して障害モデルを獲得する。第2のアルゴリズムは、複数障害とノイズを含む情報の存在下でアラームを相関付ける。両アルゴリズムとも多項式時間計算量を持ち、破損データを扱うためのVITERBIアルゴリズムの拡張を用い、ハードウェアで実装可能である。一例として、これらはANS(Advanced Network and Services, Inc.)/NSF T3ネットワークによって生成されたデータを解析するために適用される。 ## 論文情報 - 著者: Isabelle Rouvellou、George W. Hart(共に Columbia University 所属。George W. Hart は脚注で「現在は IBM T.J. Watson Research Center に所属」と明記) - 掲載: IEEE INFOCOM 1995(*Proceedings of INFOCOM '95*, セッション 5a.3, pp. 553-561) - 本論文の一部は ORSA/TIMS'93(Chicago)で発表済み - 原本: `.raw/papers/Automatic-Alarm-Correlation-for-Fault-Identification.pdf`(9ページ) ## 概要 大規模・複雑な通信ネットワークにおいて、障害(fault)は避けられないが、迅速な検知と識別はネットワークの信頼性を大きく向上させうる。ネットワーク障害は典型的に複数のアラームを発生させ、これらを相関付けて発生源を特定する問題(アラーム相関)は障害管理の主要課題である。従来はルールベースのエキスパートシステムが主なアプローチだったが、多くは人間の専門家の知識をアドホックに移植したものだった。本論文は、障害を確率的有限状態機械(PFSM)としてモデル化する新しい枠組みを提案し、ネットワークのトポロジーなど構造に関する知識を仮定せず、ノイズを含む環境で複数の同時障害を識別できる点を新規性とする。 ## 問題設定 - 障害は一般に、障害の発生源から影響が波及するにつれて一連のアラームの系列を生成する(単一のアラームや順序を問わないアラームの集合ではない)。 - 障害は単一の系列ではなく複数の可能な系列を生成しうる(発生時のネットワーク状態に依存して系列がわずかに変化する)。 - 各アラームは識別情報(デバイス名と症状)と発生時刻のみを持つと仮定する(理想的なアラームとは異なり、ネットワーク中の多くのシステムで成り立つ現実的な仮定)。 - 観測されるアラーム系列はデータ破損(ノイズ)を伴いうる。破損操作として、アラーム追加(Addition)・アラーム削除(Deletion)・アラーム変更(Change)・2つのアラームの順序変更(Order change)の4種を定義する。図1(Figure 1)は、この関係を「(a) 理想的なデータ(障害が生成する本来の出力)」と「(b) 観測データ(ノイズを経て観測される系列)」の対比として図示する。 - オンラインで観測されるデータは、一般に複数の障害から生成された系列がインターリーブ(shuffle)されたものであり、どの部分がどの障害由来かを決定する必要がある(p-coverage の概念で定式化)。 ## 提案手法 ### 障害モデル(PFSM) 障害を確率的有限状態機械(probabilistic finite state machine, PFSM)としてモデル化する。PFSM は有限状態集合・ラベル(アラームに対応する出力)集合・遷移(弧)集合・初期状態分布・終了状態分布・遷移確率テーブルの六つ組として定義される(Definition 1)。独立な2つの障害が同時発生する場合、対応する2つのPFSMの積が同時発生モデルとなる。 ### フェーズI: 学習(モデル獲得) 既知の障害に対応する履歴データ(複数のアラーム系列の連結)から、その障害のPFSMを推定する。推定問題は、PFSMの複雑度コスト(状態数・弧数・ラベル数の対数の和、Hartの1987年の博士論文に基づく記述長の考え方を利用)とデータへの適合コストの和を最小化するコスト最小化問題として定式化する(Problem 1)。アルゴリズムは非確率的FSM空間上の貪欲な局所探索であり、状態の分割・併合、弧の追加・削除・宛先変更という近傍操作を用いる。各候補構造に対してVITERBIアルゴリズムを拡張したfitルーチン(挿入・削除・複数記号にまたがる誤り(2記号の入れ替え等)を含むより広いクラスの誤りを訂正できる点で標準のVITERBIより強力)を適用し、コストを最小化するPFSMを生成する(FSM-to-PFSMルーチン)。このFSM-to-PFSMルーチンはEMアルゴリズムやBaum-Welchアルゴリズムに類似した反復構造を持つ。学習アルゴリズムの計算量は状態数・弧数に関して多項式時間であり、第2フェーズの計算量は O(K・N_c・Q^3) 程度である(K は次の探索ステップに保持する候補構造数、N_c は破損操作数、Q は状態数)。図2(Figure 2)は、この推論アルゴリズムの簡単な流れ(候補構造の生成とコスト評価の反復)を図示する。 ### フェーズII: オンライン相関 観測されたアラーム系列から、障害が発生したかどうか、発生した場合はどの障害(複数の同時障害を含む)かを判定する最大化問題として定式化する(Problem 2)。「無障害」状態を単一状態・遷移なしのPFSM F0として扱い、ノイズはF0による「アラーム追加」として解釈する。2つのアルゴリズムを提案する。 - **アルゴリズムI**: 障害の可能な組み合わせすべてに対して解釈ルーチンを適用し大域最適解を得るが、障害数 N に対して組み合わせ数が指数的(2^N)に増えるため計算量が指数的となる。 - **アルゴリズムII**: 貪欲な反復ヒューリスティックであり、各反復で残りのデータ系列に対し単一障害(+ノイズ)またはノイズのみの解釈を評価し、最も尤もらしい単一障害を確定させてから残りのデータに同じ操作を繰り返す。停止条件は残り全体がノイズと判定されるか、データが尽きるかのいずれか。計算量はfitルーチンと同程度の多項式時間であり、ハードウェア実装が可能である。 いずれのアルゴリズムも「解釈ルーチン」を基礎とする。解釈ルーチンは、与えられた障害集合の同時発生PFSM(各PFSMの積)に対しfitアルゴリズムを適用してデータの最良のp-coverage(データを各障害由来の部分系列に分割する組)を求め、尤度を割り当てる。図3(Figure 3)は、アルゴリズムIIによる相関アルゴリズムの簡単な流れ(単一障害候補の逐次的な当てはめとノイズの切り出し)を図示する。 ## 新規性 - ネットワークのトポロジーなど構造知識を一切仮定しない点(Bouloutas & Caloの先行研究[8]は障害箇所特定(fault localization)を扱うが、アラームの時間順序を考慮せず、トポロジー知識を前提とする「Mandatory Causation Assumption」を置き、信頼できないアラームの可能性を排除している。本論文はこの点で異なる)。 - アラームの時間的順序を明示的にモデル化する点(順序を無視する集合ベースのアプローチとは異なる)。 - ノイズ(不完全・不正確なデータ)を許容し、破損データからでも障害モデルを学習・相関付けできる適応的な枠組みである点。 - 両フェーズのアルゴリズムが多項式時間で動作し、VITERBIアルゴリズムの拡張に基づくためハードウェア実装が容易である点(高いアラームレートへの対応を想定)。 ## 実験設定 ANS(Advanced Network and Services, Inc.)/NSF T3ネットワーク(米国内の13のコアノードにまたがるT3ベースのネットワークで、全米科学財団(NSF)の拠点を結び818のネットワークを相互接続し、月あたり20億パケット超を運ぶ)から生成されたデータを用いる。学習データはANS/NSFのT3ネットワークを運用する専門家から提供された情報に基づきシミュレートされた。対象とする4つの障害は次のとおり。 - 障害(I): TCP fin-wait状態コードのバグ - 障害(II): インターフェースカードの故障 - 障害(III): T3回線の故障 - 障害(IV): ルートフラッピング(iBGPセッションの喪失) 表1(Table 1)は、CPU飢餓・iBGPセッション喪失・正常状態・パケットロス・ccstat異常・is-is隣接関係喪失・pingへの無応答・SNMP回線エラー・データパリティエラー・AS到達不能・断続的パケットロスなど11種類のアラーム症状とその記号(A〜Kに対応)を定義する。図4(Figure 4)は4つの障害それぞれについて獲得されたFSMモデル(遷移確率付き)を示す。 ## 実験結果 - アルゴリズムIIを単一障害のみが発生する単純なアラーム系列に適用したところ、いずれの場合も正しく障害を識別できた。 - 複数障害・ノイズを含む例を3件示す。すべて1秒未満でアラームの発生源を発見できた。 - **例1**: 障害I・II・IVが同時発生して生成したデータ ABEGCJDAD に対し、アルゴリズムは3つの障害すべてを正しく認識し、対応する3-coverage {C1=ABCD, C2=EGD, C3=JA} を得た(純粋ノイズへの帰属はゼロ)。図5(Figure 5)は本例における各FSM中の該当パス(太線)とアルゴリズムの各ステップを図示する。 - **例2**: 障害IIIとIVが同時発生して生成したデータ IHDDJ に対し、出力は F_probable={III, IV, f0} で、3-coverage {C1=IHD, C2=J, C3=D} が得られ、観測アラームの一部をノイズと判定した。追加操作の確率を他の破損操作より低く設定すると、出力は F_probable={III, IV} に変化し、C1=IHDD がFSMの許容系列 IHDF の破損版(最後のFがDと誤認)として解釈された。図6(Figure 6)は本例における該当パス(太線)を図示する。 - **例3**: 障害IIIが2回発生して生成したデータに対し、非破損データ(HIIDHFF)・破損データ(HIIDFF、Hアラームが1件欠落)いずれの場合も、アルゴリズムは同一障害の2回の発生を正しく識別した(F_probable={III, III})。図7(Figure 7)は本例(同一障害の2回発生)における該当パス(太線)を図示する。 ## 考察 - 本手法はエキスパートシステムを排除するものではなく、両立可能である(エキスパートシステムが初期学習データを提供しつつオンライン処理には遅すぎる、あるいは特定の障害種別にはエキスパートシステムが適し他はPFSMが適する、といった役割分担がありうる)。 - 障害モデルは新データの観測ごとに更新可能であり、システムは学習を継続して性能を向上させる。 - 監視対象の症状(シンボル)集合を拡張すればより精緻な識別が可能になるが、その分FSMが複雑化しオンライン処理の計算時間が増大するというトレードオフが生じる(結果の精度と手法の単純さのトレードオフ)。 - 本論文が扱うのはある1つの時間窓内のデータ処理のみであり、窓の選び方・重なりの扱いは今後の課題としている。ただしノイズ(追加・削除)への耐性から、窓や重なりの選択に対して頑健であると述べる。 ## 強み / 弱点・課題 - 強み: トポロジー知識を仮定しない、時間順序を明示的に扱う、ノイズを許容する適応的な学習、両アルゴリズムとも多項式時間かつハードウェア実装可能。 - 弱点・課題: アルゴリズムIは組み合わせ的爆発(2^N)により実用上の計算量が禁止的である。時間窓の選定・重なりの扱いはスコープ外として残されている。監視症状の粒度と精度・計算コストの間にトレードオフが存在する。評価は単一ネットワーク(ANS/NSF T3)のシミュレートデータに基づくものであり、大規模な実運用環境での検証は示されていない。