(57)【要約】      （修正有）【課題】  運用するネットワーク・インフラの性能に重大な損害を与える複雑なネットワーク異常に対処するために、問題を即座に摘出することができる効果的な検出技術の開発。【解決手段】  ネットワークにおけるネットワーク異常を検出する方法は、時間間隔でネットワークから管理情報ベース（ＭＩＢ）データを収集する工程及び収集データの時系列を構築する工程を含む。該方法は更に、ウェーブレット領域において収集データの時系列を分解する工程、ウェーブレット領域において分解された時系列に基づいてエネルギ・プロットを構築する工程及びエネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程も含む。【選択図】  図３
2006067569.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおいてネットワーク異常を検出する方法であって：
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集する工程；
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を備えることを特徴とする方法。
【請求項２】
請求項1記載の方法であって：
該収集データの該時系列を分解する工程が、該収集データの該時系列をウェーブレット領域で分解する工程を備え；かつ
エネルギ・プロットを該分解時系列に基づいて構築する工程が、ウェーブレット領域で分解された該時系列に基づいてエネルギ・プロットを構築する工程を備えることを特徴とする方法。
【請求項３】
請求項2記載の方法であって、該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程が、該エネルギ・プロットを解析して線形特性からの偏差を判定する工程を備えることを特徴とする方法。
【請求項４】
請求項3記載の方法であって、線形特性からの該偏差が、該線形特性に対する、エネルギ値における異常な減少を備えることを特徴とする方法。
【請求項５】
請求項1記載の方法であって、更に、ネットワーク異常イベントの徴候を検出した場合に、警告を発生させる工程を備えることを特徴とする方法。
【請求項６】
請求項2記載の方法であって、更に：
該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
ネットワーク異常イベントの徴候が特定閾値の該特定回数、検出された場合に、ネットワーク異常イベントを示す警告を発生させる工程を備えることを特徴とする方法。
【請求項７】
請求項6記載の方法であって、更に：
ネットワーク異常イベントの徴候が該特定閾値の該特定回数検出されない場合に、健全なトラフィックの通知を生成する工程を備えることを特徴とする方法。
【請求項８】
ネットワーク装置を備えるネットワークにおいてネットワーク異常を検出するシステムであって：
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集するよう動作可能なメモリ；及び
該メモリに結合されるコントローラを備え、該コントローラは：
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を行うよう動作可能であることを特徴とするシステム。
【請求項９】
コンピュータ判読可能媒体において実施されるソフトウェアであって、該コンピュータ判読媒体は方法を行うよう動作可能なコードを備え、該方法は：
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集する工程；
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を備えることを特徴とするソフトウェア。
【請求項１０】
ネットワークにおいて誤構成を検出する方法であって：
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集する工程を備え、該データはパケット・カウント統計を備え；
更に、該収集データの時系列を構築する工程；
該収集データの該時系列をウェーブレット領域においてハール・ウェーブレット関数を用いて分解する工程；
エネルギ・プロットを該ウェーブレット領域において分解された該時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析して誤構成イベントの徴候を判定する工程を備え、誤構成イベントの徴候は該エネルギ・プロットにおける線形特性からの偏差を備え；
更に、該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
誤構成イベントの徴候が特定閾値の該特定回数、検出された場合に、誤構成イベントを示す警告を発生させる工程を備え；
該誤構成イベントは、ＩＰアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、通信ネットワークに関し、特に、ネットワークにおけるネットワーク異常を検出する方法及びシステムに関する。
【背景技術】
【０００２】
ネットワーク事業者は、運用するネットワーク・インフラの性能に重大な損害を与え、収益を減少させ得る、複雑なネットワーク異常、特に誤構成に日々、直面している。そのような異常に対処することは、そのような問題を即座に摘出することができる効果的な検出技術の開発を必要とし得る。大規模ネットワークに存在する誤構成の範囲は、広く、新たなプロトコルやアプリケーションが開発されるにつれて経時的に変わり続けている。通常、特定の検出アルゴリズムが、はっきり定義された誤構成を識別するよう企図されている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、従来の方法及びシステムに関連した欠点及び課題の少なくとも一部をかなり除去するか削減する、ネットワークにおけるネットワーク異常を検出する方法及びシステムを備える。
【課題を解決するための手段】
【０００４】
特定の実施例によれば、ネットワークにおけるネットワーク異常を検出する方法は、時間間隔でネットワークから管理情報ベース（MIB）データを収集する工程及び収集データの時系列を構築する工程を含む。該方法は、収集データの時系列を分解する工程、分解時系列に基づいてエネルギ・プロットを構築する工程及びエネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程も含む。
【０００５】
収集データの時系列を分解する工程は収集データの時系列をウェーブレット領域で分解する工程を備える場合があり、エネルギ・プロットを構築する工程はウェーブレット領域で分解される時系列に基づいてエネルギ・プロットを構築する工程を備え得る。エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程は、エネルギ・プロットを解析して線形特性からの偏差を判定する工程を備え得る。線形特性からの偏差は、線形特性に対する、エネルギ値における異常な減少を備え得る。該方法は、MIBデータを収集する工程、時系列を構築する工程、ウェーブレット領域において時系列を分解する工程、エネルギ・プロットを構築する工程及びエネルギ・プロットを解析する工程、を特定回数繰り返す工程、ネットワーク異常イベントが特定閾値の特定回数、検出された場合にネットワーク異常イベントを示す警告を発生させる工程を含み得る。ネットワーク異常イベントは、IPアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備え得る。ネットワークからMIBデータを収集する工程は、パケット・カウント統計を収集する工程を備え得る。
【０００６】
別の実施例によれば、ネットワークにおけるネットワーク異常を検出するシステムは、時間間隔でネットワークから管理情報ベース（MIB）データを収集するよう動作可能なメモリと、メモリに結合されたコントローラとを含むネットワーク装置を備える。コントローラは、収集データの時系列を構築し、ウェーブレット領域で収集データの時系列を分解し、ウェーブレット領域で分解された時系列に基づいてエネルギ・プロットを構築し、エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定するよう動作可能である。
【０００７】
特定の実施例の技術上の効果は、ループ、IPの重複アドレス、距離ベクトル（DV）ルーティング状態の誤り、最大伝送単位（MTU）の超過、ブラック・ホール及び誤構成パケット・フィルタリングを含む、ネットワークにおける複数の種類のネットワーク異常及び誤構成を検出することができる方法を含む。よって、特定の実施例は、MIBデータを検出処理に用い得るので、限定的なネットワーク再構成によって、将来の誤構成を含む、ネットワーク異常空間のかなりの部分を検出することが可能である。よって、ネットワーク異常検出機能を実施することに関する時間及び費用は、ネットワーク異常の種類毎の検出構成部分に対する必要性を削減し得るので、削減される。更に、特定の実施例はTCP特性と、ネットワーク装置メーカが首尾一貫して従う再送タイムアウト（RTO）イベントとを解析する。これによって、ネットワーク異常検出を実施する特定の実施例が種々のメーカによる幅広い製品群に適用可能であるようになる。
【発明を実施するための最良の形態】
【０００８】
本発明の他の技術上の効果は、添付図面、本明細書の記載及び本特許請求の範囲から当業者に容易に明らかとなる。更に、特定の効果を上記に記載したが、種々の実施例は、記載効果の全部又は一部を含む場合があり、記載効果を何ら含まない場合もある。
【０００９】
本発明やその効果が更に徹底的に分かるよう、次に、以下の記載を、添付図面とともに参照する。
【実施例】
【００１０】
図1は特定の実施例による通信システム10を示す。通信システム10は解析装置12、ネットワーク・セグメント14、ルータ16及びサーバ18を含み、何れかの適切な通信ネットワークを備え得る。通信システム10は、例えば、主要ティア1プロバイダ若しくは国内インターネット・サービス・プロバイダのネットワーク又は、公衆若しくは専用のローカル・エリア・ネットワーク（LAN）やワイド・エリア・ネットワーク（WAN）を備え得る。一般的に、解析装置12は、ネットワーク性能を悪化させ得る、システム10内の、誤構成などの、ネットワーク異常を診断するようネットワーク・トラフィックの解析を備える。特に、解析装置12は、通信システム10内のリンクされた装置間の誤構成及びネットワーク異常の検出を可能にし得る。特定の実施例によれば、解析装置12はトラフィック・データを収集し、収集トラフィック・データの特性を解析することによってネットワーク異常を検出することが可能である。解析装置12は種々のネットワーク種類の何れかにおけるネットワーク異常群を検出することが可能である。そのようなネットワーク異常は例えば、ループ、IPの重複アドレス、距離ベクトル（DV）ルーティング状態の誤り、最大伝送単位（MTU）の超過、ブラック・ホール及び誤構成パケット・フィルタリングなどの誤構成を含み得る。
【００１１】
解析装置12は、他の構成要素に結合し、パケット・ベースの標準を用いて通信することができる、適切な制御ロジックを含む、何れかの適切なネットワーク機器を表す。例えば、解析装置12は、汎用コンピュータ、ルータ、特別に設計された構成部分又は他の適切なネットワーク機器を備え得る。解析装置12は、ネットワーク異常を検出するようネットワーク・トラフィック・データの解析を行うようにしている。
【００１２】
解析装置12と同様に、各サーバ18は、他のネットワーク機器に結合し、パケット・ベースの通信プロトコルを用いて通信して、種々のサービスを備える、何れかの適切な制御ロジックを含むネットワーク機器を表す。サーバ18は、例えば、システム10内の他の構成要素にネットワーク・アクセス可能なサービスを備える。このサービスは、ウェブ・ホスティング、データ管理、処理又は他の適切なサービスなどの何れかの数の特徴を含み得る。特定の状況では、1つ又は複数のサーバ18が、解析装置12が備えるものと同様な診断機能又は解析装置12によって行われる診断と協調した診断機能をサポートし得る。
【００１３】
図示した実施例では、解析装置12及びサーバ18は、ネットワーク・セグメント14及びルータ16を含む通信機器によって相互接続されている。各ネットワーク・セグメント14は、パケット・ベースの伝送制御プロトコル（TCP）通信をサポートする構成部分及び伝送媒体の何れかの適切な集まり及び配置を表す。パケットの語を用いていることは、パケット、フレーム又はセルなどのデータの何れかの適切なセグメンテーションを想定しているものであることが分かる。特定のネットワーク・セグメント14は、何れかの数の相互接続されたスイッチ、ハブ又は中継器を含み得る。ルータ16は、ネットワーク・トラフィックがネットワーク・セグメント14間を流れることを可能にする。
【００１４】
解析装置12は、一般的な性能メトリックを含む共通の特性を共有するネットワーク異常群を診断するよう、ネットワーク・トラフィックを収集し、解析する。このネットワーク異常は、TCP接続の始めでのパケット喪失を検出することによって識別し得る。TCP接続の開始でのノードによって放出される第１パケットが喪失された場合、該ノードは宛て先ノードからの応答を待つことになる。（パケット喪失を示す、）応答が何ら受信されない場合、パケットはもう一度、再送される。よって、パケット喪失が起こる場合、再送タイムアウト（RTO）が起きる。例えば元の送信後3秒以内に応答が何ら受信されない場合、まさにそのパケットがもう一度送出される。ネットワークに異常が存在しているということを仮定すれば、再送されたパケットはもう一度喪失されることになる。6秒後応答が何ら得られない場合、第２の再送が行われる。12秒後応答が何ら得られない場合、第３の再送が行われる、などである。特定の実施例は、デフォールトのRTO値を利用する早期RTOイベント（ERE）を識別する。このデフォールトのRTO値はTCP/IPプロトコルにおいて標準化されており、首尾一貫して実施されている。よって、TCP接続の開始段階で招く再送イベントは、明確に定義された特性を備えており、モジュールの実施形態やエンド・ツー・エンド・パス特性に影響を受けにくい場合がある決定的パターンに従うネットワーク・トラフィックを生成する。
【００１５】
特定の実施例は、例えば解析装置12によって、集約されたトラフィックに埋め込まれた、誤構成された構成部分を摘出することができる、更に以下に記載する検出アルゴリズムを実施する。一部の実施例は、種々の分解レベルで入力信号のエネルギを分解するよう、パケット・カウント統計などの時系列管理情報ベース（MIB）データのウェーブレット解析を用いる。他の実施例は、ウィンドウイングされたフーリエ変換などの他のスペクトル解析手法を用い得る。多くの場合におけるEREは、正確な分解レベルでディップの存在をもたらす。特定の実施例は、このエネルギ・レベルのディップを解析し、認識して異常の存在を推論する手順を利用する。
【００１６】
動作上、トラフィック・データはルータ16などのネットワーク装置から解析装置12によって定期的に収集される。特定の実施例では、トラフィック・データは、毎秒、1つ又は複数のネットワーク装置から収集し得る。例えば、特定のルータに関しては、ルータのインタフェース経由で入ってくるパケットの数を示すデータを定期的に収集し得る。ルータの収集トラフィック・データから、ルータのインタフェースを通過するパケットの数を経時的に識別する時系列を構築する。この時系列のパケットは、健全なトラフィックからのパケットと、誤構成された、すなわち健全でないトラフィックからのパケットを含み得る。時系列は、構築されると、異常を含んでいるか否かを判定するよう解析される。特定の実施例では、そのような解析は、時系列のトラフィック・データのウェーブレット・スペクトル解析によって行い得る。
【００１７】
多くの種類のネットワーク異常は、収集データのスペクトル・エネルギ・プロットが健全なトラフィックの線形特性から逸脱することをもたらし得る。これらの種類のイベントによって、エネルギ・プロットが特定のエネルギ・レベルでディップを表すようになる。そのようなディップはよって、再送イベントの指紋であり、したがって、ネットワークにおける異常を示すパケット喪失の徴候であり得る。
【００１８】
TCP接続の開始の際でのパケットの喪失によって検出し得る特定の種類の異常又は誤構成は、IPアドレス空間の重複、パケット・フィルタリング誤構成、無限ルーティング・ループ及びTCP-SYNフラッド分散型サービス拒否（D-DoS）攻撃を含む。これらの標的異常の各々は、そのような検出を可能にする共通の特性を共有する。IPアドレス空間の重複は、中規模から大規模のネットワークにおいて頻繁にみられる。誤構成は、新たなサブネットワークS-N2が既存のネットワークN1に追加されるか、保守の理由でS-N2に割り当てられるアドレス空間が改変される場合にもたらされる。意図せずに、S-N2のアドレス空間はN1における別のサブネットワークS-N1のアドレス空間と重複する。この誤構成は、(a)同じネットワーキング・インフラの別個の部分を管理する種々の部門の間の連係の欠如又は(b)特定のネットワーク部分に対する最近の修正に関する最新情報の欠如（例えば、不完全なネットワーク図、失効した構成情報）によってもたらされているものとみられる。そのような誤構成は、ネットワークの内部ルーティング状態を妨害する。DVプロトコルが用いられる場合には、誤構成点S-N2に近いN1におけるノードは、そのルーティング状態を変えることになる。DV情報の交換は、特定のプレフィックス、すなわちS-N1のアドレス空間に対するより短いパスの存在を明らかにする。N1のルーティング状態が収束すると、M(S-N2)をN1におけるルータ群とし、その状態はそのような誤構成に応じて改変される。M(S-N2)におけるノードに達する、S-N1にアドレス指定されるパケットは、通常それが廃棄されるS-N2に向けてルーティングされることになる。逆に、M(S-N2)におけるノードに達しない、S-N1にアドレス指定されるパケットは、S-N1に適切に転送される。ネットワークN1内の特定の位置によって、問題は容易にみられるか、通常の監視活動に完全に透過的であり得る。このことは、完全な機能停止をもたらす誤構成と比較してトラブルシューティングの複雑度を増加させる。誤構成によって影響されるTCPフローは、新たに接続できるようになるのに必要な3ウェイ・ハンドシェークを完了することができない。ＩＰアドレス空間の重複を伴う他の誤構成の場合も可能であり得る。
【００１９】
パケット・フィルタリングの誤構成はもう１つの標的異常である。パケット・フィルタリングは、多くのネットワークにおいて一般的であり、安全性及び完全性を向上させることを目的としている。一般的には、パケット・フィルタリングの誤構成は：(a)フィルタが過剰に制限的な場合、望まれていないパケット欠落をもたらし得るものであり、(b)フィルタ構成が許容的過ぎる場合には望ましくないパケットの漏れをもたらし得る。過剰に制限的なフィルタリングの誤構成は通常、いくつかの要因に起因し得るものであり、それらの要因は；(a)最もサポートされているフィルタリング仕様形式が、その意味において非常に制限的であり、それによって管理者が複雑な規則を記述することを必要とするということ；(b)フィルタリング規則は通常パケット・ベースであるが、ビジネス中心のフィルタリング要件はフロー指向であるということ；及び(c)フィルタリング・ツールは、構成変更が行われる場合に頻繁に見逃される暗黙の規則処理順序を課すということである。特定のアドレス空間からのパケットとそのアドレス空間へのパケットとの全てを廃棄するフィルタリング誤構成はいくつか存在する。そのような状況は、標的誤構成の他の種類に同様な方法でTCP接続の設定に影響を及ぼす。この状況では、TCPハンドシェークは完了することが可能でなく、RTOベースの再送すなわちEREが行われる。
【００２０】
無限ルーティング・ループは、帯域利用やパケット喪失を高くするという理由で重大な問題をもたらす、別の種類の標的異常である。通常、レイヤ3ループはトランジェント又は無限として分類される。トランジェント・ループは当然、ルーティング変更の伝搬中に生じ、収束に達すると消える。一部の無限ルーティング・ループは、特定のプレフィックスに影響を及ぼすルートの間違った静的構成によって引き起こされる。他の無限ルーティング・ループはＤＶルーティング状態の誤りによる。1つの特定の異常は、パケット・フィルタリングの誤構成との組み合わせでのもっともらしい構成の選択の交互作用としてみられる。イベントの随伴性は、ルーティング情報がネットワークＮ1から隣接するネットワークＮ2に漏れるというようなものである。Ｎ2のルーティング状態は、Ｎ1からのパケットがＮ2によってもう一度Ｎ1に、通常、Ｎ1からのパケットがＮ2に当初入ったものとは別の相互接続点を経由してルーティングされるように改変される。そのような誤構成は、あまりない場合があるが、ネットワーク性能の点では非常に有害である。ループ関連の誤構成では、問題のループによって影響されるパケットは、ＴＴＬ値が失効することが理由で最終的には破棄される。この問題によって影響されるホストが起動するＴＣＰ接続はトランザクションを完了することができないことになり、ＥＲＥ再送が行われる。
【００２１】
別の種類の標的異常はD-Dos攻撃である。D-Dos攻撃の目的は、特定の標的を、その標的によって備えられるサービスが正当なユーザに利用可能でなくなるというように害するというものである。種々の機構を攻撃者は駆使し得る。TCP-SYNフラッド攻撃は極めて一般的であり、上記誤構成の他の種類のものとの重要な類推を表すネットワーク異常をもたらす。攻撃者は通常、スプーフされたTCP-SYNパケットが標的に向けて生成されるコンプロマイズド・ホスト群を用いる。標的は、当初のTCP-SYNのスプーフされたアドレス宛てのTCP-SYN-ACKパケットを生成する。標的からのTCP-SYN-ACKは、よって失われ、半開状態のTCP接続は入ってくる要求キューを飽和させる。更に、後から入ってくるTCP-SYNパケットは、正当なクライアントが標的と新たな接続ができるようにしようとする場合に廃棄される。その結果、サービスは拒否される。RTOベースの再送は、（スプーフされたパケットに応じた喪失TCP-SYN-ACKの場合）標的側から行われ、（標的に入ってくる要求のキューのオーバフローによる喪失TCP-SYNの場合）クライアント側から行われる。TCPフローの後者の群のほうが数値的により重要である。D-DoS攻撃が成功するほど、クライアントの早期RTO再送はより多く、ネットワークにおいて存在することになる。
【００２２】
上記のように、EREが存在していることは、特定の実施例が標的とする誤構成のうちで共有される異常な特性である。パケット喪失は新たなTCP接続の開始段階に影響を及ぼすので、RTOタイマはデフォールト値を用いる。このことは、指数バックオフRTO管理アルゴリズムが求める正確な時間軸での誤構成フローにおける明確に定義された相関関係をもたらす。よって、3ウェイ・ハンドシェークにおいてみられたパケットが後に喪失される場合、同じパケットはもう一度3・2k秒（k=0,1,2,..）後にみられるものである。原則的には、再送シーケンスが無限級数である場合、トラフィック・パターンは、擬似自己相似性として知られる、べき法則オンオフ特性をもたらすことになる。しかし、実際には、再送イベントのシーケンスは有限級数であり、再送試行の数は限定的である。
【００２３】
通常、TCP/IPモジュールの実施は、喪失パケットを限られた回数、再送しようとすることになる。最大試行数（kMAX）は種々の実施において変わってくる場合がある。更に、kMAXは、喪失が起きる場合のTCP接続の状態（例えば、接続できるようにした状態対データ交換状態）によって変わり得る。kMAXは通常、ハンドシェーク段階では低くなる。デフォールト構成におけるウィンドウズ・ベースのホストの場合、ハンドシェーク段階中のパケットの喪失についてはkMAX＝1である。リナックス（Linux）O/Sの場合、kMAX＝4である。更に、低応答性に対するエンド・ユーザの耐性は通常、約8乃至14秒に限定される。よって、TCPモジュールは、接続がアプリケーション層によって終結される前に少ない回数だけ喪失パケットを再送することができ得る。
【００２４】
通常、早期RTO再送パターン、すなわちEREは、誤構成によって影響されるTCPフロー全てにおいて一様に繰り返される。RTOイベントがTCP接続内部の後の点で起きた場合にはこのことは必ずしもあてはまらない。実際には、各フローにおけるRTOタイマは、別個に各接続が受けるRTTによって調節されることになる。RTT値は通常、特定のエンド・ツー・エンド接続の静的特性及び動的特性による高い分散を表す。ハンドシェーク段階におけるRTO再送は通常、RTT測定が何ら利用可能でないということなどの特徴に対して影響を受けにくい。更に、RTO管理アルゴリズムのデフォールトの初期化値が標準化されているので、特定のTCP/IPモジュールに対する依存は接続のこの段階ではあまり懸念すべきことではない。
【００２５】
特定の実施例は、下記のアルゴリズムを利用して、エネルギ・プロットの局所最小値によってネットワーク異常イベント又は誤構成イベントを検出し得る。{X0,r}(0≦r≦2M−1；M∈N)を、異常を検出するよう解析する離散入力信号とする。{X0,r}における最初の下付き文字は集約レベルを表す。第２の下付き文字は所定の時間及び集約レベルでの特定のサンプルを識別する。集約レベルの値が増加することは分解が粗くなることに相当する。信号サンプルは、時間的に一様に間隔があいている。ΔTは、利用可能な最も細かい分解での２つの連続したサンプルの間の時間間隔である。当該アルゴリズムは、信号のハール（Haar）・フィルタ・ベースの表現を利用している。２つのベクトル系列が生成される。これらは、集約信号{Xq,r}(1)及び詳細{dq,r}(2)（1≦q≦M）として知られている：
【００２６】
【数１】
2006067569.tif 000003
続いて、q番目の分解レベルのエネルギ含量Eqが計算される：
【００２７】
【数２】
2006067569.tif 000004
エネルギ・プロットは、分解レベルqと関数としてのlog2(Eq）の図である。検出アルゴリズムは、その基の時系列のスケーリング特性の一般的な特徴を判定するのにエネルギ・プロットを用いる。漸近的には、エネルギ関数の特性は、広範囲にわたるパケット交換ネットワークに及ぶ自己相似処理の場合、qが線形であることが想定される：
【００２８】
【数３】
2006067569.tif 000005
式(4)では、Hはハースト(Hurst)・パラメータであり、bは定数である。1/2＜H＜1であるので、式(4)における直線の傾きは、0＜（2H−1）＜1である。RTOイベントは、集約レベルの正確な範囲に及ぶエネルギ関数の線形特性を改変する。特定のモデリングでは、連続したRTOイベントは、（0≦k≦kMAXの場合）3・2k秒離れており、kMAXは、有限値であり、一般的には小さな値である。以下では、kMAXは2に等しいものとする。
【００２９】
（u≧0である場合）ΔT=3・2−u秒が信号サンプリング・レートである場合には、早期RTO再送の信号のエネルギ関数は、ウェーブレット集約レベル{u＋１、u+2、u＋3}にわたる局所のディップを表す。信号は、当初のパケットと、それに続く３つの後続再送からなる。信号{X0,r}は、δ0(t)+δ3・2k（0≦kMAX)であり、t=kである場合にδk(t)=１であり、さもなければδk(t)=0である2項関数によって表し得る。式(1)によって、集約レベルuでの信号は；
【００３０】
【数４】
2006067569.tif 000006
である。式(2)及び(3)によって、集約レベル{u＋１、u+2、u＋3}での詳細のエネルギ含量は：
【００３１】
【数５】
2006067569.tif 000007
である。集約レベル{u＋１、u+2、u＋3}付近でのエネルギ関数とその形状（局所最小値）とのプロットを以下に示す。この図は早期RTOベース信号エネルギ（実線）と式(4)によって予測される線形特性（点線）とを対比させている。
【００３２】
【表１】
2006067569.tif 000008
通常の展開シナリオでは、複数の健全なTCPフロー（雑音からの異常の検出）は（局所性の特性が当てはまる）誤構成フローと多重化されることになる。上記解析アルゴリズムは、区間〔u＋1,u+3〕を含む集約範囲にわたってエネルギ関数の形状を考慮することによって集約トラフィックに埋め込まれた誤構成された構成部分が存在することを検出する。当該集約レベルにおけるディップ（局所最小値）を位置特定するよう、エネルギ関数はy=β0+β1x+β2x2の最小２乗放物線によって近似化される。未知数{β0,β1,β2}は以下の条件を受ける：
【００３３】
【数６】
2006067569.tif 000009
【００３４】
【数７】
2006067569.tif 000010
を式群(8)の解とする。Vをyの頂点とする。
【００３５】
【数８】
2006067569.tif 000011
Vが関係(10)及び(11)を満たす場合、検出アルゴリズムはエネルギ・ディップを含むものとして時系列に印をつけ、したがって、異常の徴候が検出される。
【００３６】
【数９】
2006067569.tif 000012
関係(10)は、Vが局所最小値であるということを必要とする。関係(11)はVの横座標が当該エネルギ・レベルの範囲内に収まるということを示唆している。特定の実施例において実施される上記検出アルゴリズムはnの測定をサンプルSnに集約する。m(m≦n)を、関係(10)及び(11)によって異常なものとして印がされたSnにおける測定の数とする。閾値γは、(m/n)≧γである場合に警告をトリガするのに用い得る。
【００３７】
以上の記載は、ネットワーク異常を検出するうえで収集された時系列データを統計的に処理する詳細な数式を備える。しかし、上記のように、システム10は、誤構成を含む潜在的なネットワーク異常を検出する何れかの適切な手法及び計算を用いた解析装置12を想定している。用いられる手法にかかわらず、ネットワーク異常が検出されると、解析装置12は、ネットワーク異常の通知及び/又は追加検査の実行を行って、ネットワーク異常の位置を更に摘出し得る。
【００３８】
図２は、解析装置12の例示的な機能構成部分を示す構成図である。図示した実施例では、解析装置12は、ユーザ・インタフェース30、メモリ32、コントローラ34及びネットワーク・インタフェース36を含む。一般的には、上記のような解析装置12は、ネットワークにおける複数の種類のネットワーク異常を検出するようにしている。
【００３９】
ユーザ・インタフェース30は、解析装置12のユーザと相互作用するようにしている。例えば、ユーザ・インタフェース30は、ユーザに情報を提示し、ユーザから入力を受信する、ディスプレイ、キーボード、キーパッド、マウス及び/又は他の適切な構成要素を含み得る。メモリ32は、解析装置12が用いる情報を記憶するようにしている。図示した実施例では、メモリ32は、コード38及び構成情報40を含む。コード38は、解析装置12の構成要素によって用いる、ソフトウェア、ソース・コード及び/又は他の適切な制御ロジックを含む。例えば、コード38はデータ・パスを解析するうえでの動作の一部又は全部を実施するロジックを含み得る。構成情報40は、解析装置12が用いる、起動、動作、並びに他の適切な設定及び構成を含む。例えば、構成情報40は、動作中に用いる、遠隔標的のIPアドレス、ユーザ設定、閾値、及び/又は他の適切な情報を識別し得る。
【００４０】
ネットワーク・インタフェース36は他のネットワーク機器とのパケット・ベースの通信をサポートする。例えば、ネットワーク・インタフェース36は、何れかの適切な通信プロトコルを用いたパケットの送受信をサポートし得る。コントローラ34は解析装置12の管理及び動作を制御する。例えば、コントローラ34は、解析装置12の動作を制御する、1つ又は複数のマイクロプロセッサ、プログラムされたロジック装置又は他の適切な、コード38を実行する構成要素38を含み得る。
【００４１】
動作中、解析装置12の構成要素は、システム10の構成部分から収集されたデータを解析してネットワーク異常を識別するよう動作する。例えば、コントローラ34は、ネットワーク・インタフェース36の動作を制御するよう構成情報40に基づいてコード38を実行し得る。コントローラ34は更に、受信ネットワーク動作データを解析してネットワーク異常の徴候を検出し得る。ネットワーク異常の徴候を検出すると、コントローラ34はユーザ・インタフェース30を用いてユーザに警告してもよく、さもなければ、ネットワーク異常を示す警告を生成してもよい。他の場合には、閾値レベルの異常の徴候が検出されると、警告を発生させ得る。一部の場合には、ネットワーク異常の検出を表す解析の結果として警告を発生させることは、統計的推論、ニューラル・ネットワーク、空間的イベント及び/若しくは時間的イベント又は他の方法に基づくものであり得る。図示した特定の実施例は、解析装置12において概括的な機能を実施するモジュールの例を備える。
【００４２】
しかし、図示した実施例や上記記載は特定の構成要素を含む解析装置12の特定の実施例に焦点を当てている一方、システム10は、収集データの解析を備え、ネットワーク異常を検出する、構成要素の何れかの適切な組み合わせ及び配置を有する解析装置12を想定している。よって、上記モジュール及び機能は、何れかの適切な機能構成部分のうちで合成、分離又は別の方法での分散化を行い得る。更に、特定の機能構成要素を含むものとして示しているが、システム10は、ソフトウェア又はプログラムされたロジック装置などの媒体においてコード化されているロジックを用いてその機能の一部又は全部を実施する解析装置12を想定している。更に、専用解析装置12として示しているが、システム10は、システム10内の何れかの適切な構成部分によって実施される装置12の解析機能を想定している。よって、例えば、ルータ16又はサーバ18などの構成要素は、解析装置12に関して説明したように、ネットワーク異常検出などの種々のネットワーク解析関数を実施し得る。
【００４３】
図3は、特定の実施例による、ネットワークにおける、誤構成などのネットワーク異常を検出する方法を示す流れ図である。特定の実施例では、検出する標的であるネットワーク異常イベントは、ＩＰアドレス空間の重複、パケット・フィルタリングの誤構成、無限ルーティング・ループ及び分散型サービス拒否攻撃を含み得る。該方法は工程100から始まり、工程100では、ＭＩＢデータが1つ又は複数のネットワーク装置から収集される。ＭＩＢによって、ネットワーク装置を照会し、最後の照会から装置インタフェースを通過したパケットの数を取り出すことが可能になる。ＭＩＢデータは時間間隔で、例えば毎秒又は特定秒数毎に収集し得る。工程102では、ＭＩＢデータ測定の時系列が構築される。時系列は、例えば、経時的に装置インタフェースを通過するパケットの数を識別し得る。これらのパケットは、健全なトラフィックも健全でないトラフィックも含み得る。
【００４４】
工程１０４では、時系列は、ウェーブレット領域で分解される。そのような分解は、ハール・ウェーブレット関数を特定の実施例において用い得る。他の実施例は、ウィンドウイングされたフーリエ変換などの、ウェーブレット以外のスペクトル解析手法を用い得るということが分かる。工程106では、エネルギ・プロットが、ウェーブレット領域において時系列に基づいて構築される。工程108では、エネルギ・プロットは、解析されて、工程110で、ネットワーク異常イベントの徴候を含んでいるか否かを判定する。特定の実施例では、ネットワーク異常イベントの徴候は、プロットのエネルギ値におけるディップすなわち異常な減少を、健全なトラフィックが通常、エネルギ・プロット上での線形特性にマッピングされるので、備え得る。補間は特定の範囲の集約レベルにわたって行い得るものであり、放物線の最小値がその範囲内に収まる場合、当該範囲におけるエネルギ関数の減少があり得る。この減少はネットワーク異常イベントの徴候であり得る。
【００４５】
ネットワーク異常イベントの徴候が検出される場合、当該方法は工程112に進んでよく、工程112では、ネットワーク異常イベントの徴候の閾値レベルが検出されたか否かが判定される。この判定は、ネットワーク異常イベントを示し得る過去データを用いる。閾値レベルは、解析される4つの連続したエネルギ・プロットのうちのネットワーク異常イベントの徴候の少なくとも3つの検出などの何れかの適切なレベル又は割合を備え得る。閾値レベルが達成される場合、工程１１６で、ネットワーク異常イベントを示す警告を発生させ得る。達成する対象の閾値を、警告を発生させる前に必要とする余分な情報レイヤによって、例えば、エネルギ・プロットにおけるディップを発生させ得る雑音又は他の非ネットワーク異常イベントに基づき得るネットワーク異常イベントの偽警告がないようにしている。よって、測定の群が、より意義ある判定に達するよう解析される。特定の実施例は、別の閾値の判定を含まない場合があり、ネットワーク異常イベントの１つの徴候に基づいて警告を発生させるに過ぎない場合がある。他の実施例では、ネットワーク異常の検出を明らかにする解析の結果として警告を発生させることは、統計的推論、ニューラル・ネットワーク、空間的なイベント及び/若しくは時間的イベントの相関又は他の方法に基づくものであり得る。
【００４６】
ネットワーク異常イベントの徴候が何らないか、閾値レベルが用いられる場合、ネットワーク異常イベントの徴候はそのようなレベルに達せず、その場合、工程114で、健全なトラフィックの通知を生成し得る。特定の工程を連続して経時的に、特に、ネットワーク異常の表示子の閾値レベルを検出したか否かを判定するよう連続した測定を行おうとする場合に繰り返し得る。
【００４７】
図3に示す工程の一部は、適宜、合成、修正又は削除を行う場合があり、追加工程を流れ図に追加する場合もある。更に、本発明の範囲から逸脱することなく工程を何れかの適切な順序で行い得る。
【００４８】
特定の実施例の技術上の効果は、ループ、ＩＰアドレスの重複、ＤＶルーティング・テーブルの誤り、ＭＴＵの超過、ブラック・ホール及び誤構成パケット・フィルタリングを含む、ネットワークにおける複数種類のネットワーク異常を検出することができる方法を含む。よって、特定の実施例は、ＭＩＢデータを検出処理に用い得るので限定的なネットワーク再構成によって、将来の誤構成を含む、ネットワーク異常空間のかなりの部分を検出し得る。よって、ネットワーク異常検出機能を実施することに関連した時間及び費用は、ネットワーク異常の種類毎の検出構成部分に対する必要性を削減し得るので、削減される。更に、特定の実施例は、ＴＣＰ特性及び、ネットワーク装置メーカが首尾一貫して従うＲＴＯイベントを解析する。このことは、ネットワーク異常の検出を実施する特定の実施例が種々のメーカによる幅広い製品群に適用可能であるようにしている。
【００４９】
本発明は特定の実施例を参照しながら詳細に説明したが、種々の他の変更、置換及び改変をそれに対して、本発明の趣旨及び範囲から逸脱することなく行い得るということが分かる。例えば、本発明は図１及び２に示すいくつかの構成要素及び構成部分を参照しながら説明したが、そのような構成要素及び構成部分は合成、再配置又は配置させて、特定のルーティングのアーキテクチャ又はニーズに対応し得る。更に、これらの構成要素又は構成部分の何れかを、適宜、別個の外部の構成要素又は構成部分として備え得る。本発明は、これらの構成要素、更にはそれらの内部の構成部分の配置における高い柔軟性を想定している。
【００５０】
数多くの他の変更、置換、変形、改変及び修正を当業者によって見定め得るものであり、本発明が本特許請求の範囲記載の趣旨及び範囲の範囲内に収まるものとしてのそのような変更、置換、変形、改変及び修正を包含するということが意図されている。
（付記１）
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集する工程；
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を備えることを特徴とするネットワークにおいてネットワーク異常を検出する方法。
（付記2）
該収集データの該時系列を分解する工程が、該収集データの該時系列をウェーブレット領域で分解する工程を備え；かつ
エネルギ・プロットを該分解時系列に基づいて構築する工程が、ウェーブレット領域で分解された該時系列に基づいてエネルギ・プロットを構築する工程を備えることを特徴とする付記1記載の方法。
（付記3）
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程が、該エネルギ・プロットを解析して線形特性からの偏差を判定する工程を備えることを特徴とする付記2記載の方法。
（付記4）
線形特性からの該偏差が、該線形特性に対する、エネルギ値における異常な減少を備えることを特徴とする付記3記載の方法。
（付記5）
更に、ネットワーク異常イベントの徴候を検出した場合に、警告を発生させる工程を備えることを特徴とする付記1記載の方法。
（付記６）
更に：
該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
ネットワーク異常イベントの徴候が特定閾値の該特定回数、検出された場合に、ネットワーク異常イベントを示す警告を発生させる工程を備えることを特徴とする付記2記載の方法。
（付記７）
更に：
ネットワーク異常イベントの徴候が該特定閾値の該特定回数検出されない場合に、健全なトラフィックの通知を生成する工程を備えることを特徴とする付記6記載の方法。
（付記８）
時間間隔でネットワークから管理情報ベース（ＭＩＢ）データを収集するよう動作可能なメモリ；及び
該メモリに結合されるコントローラを備え、該コントローラは：
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を行うよう動作可能であることを特徴とするネットワーク装置を備えるネットワークにおいてネットワーク異常を検出するシステム。
（付記９）
コンピュータ判読媒体は方法を行うよう動作可能なコードを備え、該方法は：
時間間隔で該ネットワークから管理情報ベース（ＭＩＢ）データを収集する工程；
該収集データの時系列を構築する工程；
該収集データの該時系列を分解する工程；
エネルギ・プロットを該分解時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定する工程を備えることを特徴とするコンピュータ判読可能媒体において実施されるソフトウェア。
（付記１０）
時間間隔でネットワークから管理情報ベース（ＭＩＢ）データを収集する工程を備え、該データはパケット・カウント統計を備え；
更に、該収集データの時系列を構築する工程；
該収集データの該時系列をウェーブレット領域においてハール・ウェーブレット関数を用いて分解する工程；
エネルギ・プロットを該ウェーブレット領域において分解された該時系列に基づいて構築する工程；及び
該エネルギ・プロットを解析して誤構成イベントの徴候を判定する工程を備え、誤構成イベントの徴候は該エネルギ・プロットにおける線形特性からの偏差を備え；
更に、該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
誤構成イベントの徴候が特定閾値の該特定回数、検出された場合に、誤構成イベントを示す警告を発生させる工程を備え；
該誤構成イベントは、ＩＰアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備えることを特徴とする、ネットワークにおいて誤構成を検出する方法。
（付記11）
該収集データの該時系列をウェーブレット領域で分解する工程が、該収集データの該時系列を、ハール・ウェーブレット関数を用いて分解する工程を備えることを特徴とする付記2記載の方法。
（付記12）
該ネットワーク異常構成イベントは、ＩＰアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備えることを特徴とする付記1記載の方法。
（付記13）
該ネットワークからＭＩＢデータを収集する工程がパケット・カウント統計を収集することを特徴とする付記1記載の方法。
（付記14）
該収集データの該時系列を分解するよう動作可能なコントローラが、該収集データの該時系列をウェーブレット領域で分解するよう動作可能なコントローラを備え；かつ
エネルギ・プロットを該分解時系列に基づいて構築するよう動作可能なコントローラが、該ウェーブレット領域で分解された該時系列に基づいてエネルギ・プロットを構築するよう動作可能なコントローラを備えることを特徴とする付記8記載のシステム。
（付記15）
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定するよう動作可能なコントローラが、該エネルギ・プロットを解析して線形特性からの偏差を判定するよう動作可能なコントローラを備えることを特徴とする付記14記載のシステム。
（付記16）
線形特性からの該偏差が、該線形特性に対する、エネルギ値における異常な減少を備えることを特徴とする付記15記載のシステム。
（付記17）
該コントローラは、ネットワーク異常イベントの徴候が検出された場合に、警告を発生させるよう更に動作可能であることを特徴とする付記8記載のシステム。
（付記18）
該コントローラは更に：
該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
ネットワーク異常イベントの徴候が特定閾値の該特定回数、検出された場合に、ネットワーク異常イベントを示す警告を発生させる工程を行うよう動作可能であることを特徴とする付記14記載のシステム。
（付記19）
該コントローラは更に：
ネットワーク異常イベントの徴候が該特定閾値の該特定回数検出されない場合に、健全なトラフィックの通知を生成するよう動作可能であることを特徴とする付記18記載のシステム。
（付記20）
該収集データの該時系列をウェーブレット領域で分解するよう動作可能なコントローラが、該収集データの該時系列を、ハール・ウェーブレット関数を用いて分解するよう動作可能なコントローラを備えることを特徴とする付記14記載のシステム。
（付記21）
該ネットワーク異常構成イベントは、ＩＰアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備えることを特徴とする付記8記載のシステム。
（付記22）
該ネットワークからＭＩＢデータを収集するよう動作可能なメモリがパケット・カウント統計を収集するよう動作可能なメモリを備えることを特徴とする付記8記載のシステム。
（付記23）
該収集データの該時系列を分解するよう動作可能なコードが、該収集データの該時系列をウェーブレット領域で分解するよう動作可能なコードを備え；かつ
エネルギ・プロットを該分解時系列に基づいて構築するよう動作可能なコードが、該ウェーブレット領域で分解された該時系列に基づいてエネルギ・プロットを構築するよう動作可能なコードを備えることを特徴とする付記9記載の媒体。
（付記24）
該エネルギ・プロットを解析してネットワーク異常イベントの徴候を判定するよう動作可能なコードが、該エネルギ・プロットを解析して線形特性からの偏差を判定するよう動作可能なコードを備えることを特徴とする付記23記載の媒体。
（付記25）
線形特性からの該偏差が、該線形特性に対する、エネルギ値における異常な減少を備えることを特徴とする付記24記載の媒体。
（付記26）
該コードは、ネットワーク異常イベントの徴候が検出された場合に、警告を発生させるよう更に動作可能であることを特徴とする付記9記載の媒体。
（付記27）
該コードは更に：
該ＭＩＢデータの収集、時系列の構築、該ウェーブレット領域での該時系列の分解、エネルギ・プロットの構築及び該エネルギ・プロットの解析を特定回数繰り返す工程；及び
ネットワーク異常イベントの徴候が特定閾値の該特定回数、検出された場合に、ネットワーク異常イベントを示す警告を発生させる工程を行うよう動作可能であることを特徴とする付記23記載の媒体。
（付記28）
該コードは更に：
ネットワーク異常イベントの徴候が該特定閾値の該特定回数検出されない場合に、健全なトラフィックの通知を生成するよう動作可能であることを特徴とする付記27記載の媒体。
（付記29）
該収集データの該時系列をウェーブレット領域で分解するよう動作可能なコードが、該収集データの該時系列を、ハール・ウェーブレット関数を用いて分解するよう動作可能なコードを備えることを特徴とする付記23記載の媒体。
（付記30）
該ネットワーク異常構成イベントは、ＩＰアドレス空間の重複と、パケット・フィルタリングの誤構成と、無限ルーティング・ループと、分散型サービス拒否攻撃とのうちの少なくとも１つを備えることを特徴とする付記9記載の媒体。
（付記31）
該ネットワークからＭＩＢデータを収集するよう動作可能なコードがパケット・カウント統計を収集するよう動作可能なコードを備えることを特徴とする付記9記載の媒体。
【図面の簡単な説明】
【００５１】
【図１】特定の実施例による、ネットワークにおけるネットワーク異常を検出する通信システムを示す図である。
【図２】図１の解析装置の例示的な機能構成部分を示す構成図である。
【図３】特定の実施例による、ネットワークにおけるネットワーク異常を検出する方法を示す流れ図である。
【符号の説明】
【００５２】
10  通信システム
12  解析装置
14  ネットワーク・セグメント
16  ルータ
18  サーバ
30  ユーザ・インタフェース
32  メモリ
34  コントローラ
36  ネットワーク・インタフェース
38  コード
40  構成
100  工程
102  工程
104  工程
106  工程
108  工程
110  判定工程
112  判定工程
114  工程
116  工程
【図１】
2006067569.tif 000013
【図２】
2006067569.tif 000014
【図３】
2006067569.tif 000015