(57)【要約】  高周波のグローバルおよびローカルなトレースルートデータにおけるリアルタイムの情報伝送異常を識別し、特徴付けるために、警告システムおよび方法が提供される。システムは、アクティブなネットワークセンサおよび／またはコレクタデバイスを含み、それらは、コンピュータネットワークにおける異なる地点への伝送に関連付けられたトレースルートデータを収集し、そのトレースルートデータをマスターサーバに提供する。トレースルートデータは、ターゲットデバイスに対してローカルに、および／またはグローバルに位置する多くのコンピューティングターゲットデバイスへ探索用データパケットを送信することにより、アクティブネットワークセンサによって取得される。マスターサーバは、受信されたトレースルートデータから１つ以上の異常を判断し、タイプ、重症度、位置、影響を受けたドメイン名システム（ＤＮＳ）サーバおよび／またはインターネット・サービス・プロバイダ（ＩＳＰ）の観点から異常を特徴付ける。
2018521611.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークを監視する方法であって、前記方法は、
前記コンピュータネットワークにおける第１の地点と前記コンピュータネットワークにおける第２の地点との間の情報の伝送に関連付けられたベースライン待ち時間状態を推定するステップを含み、前記ベースライン待ち時間状態は、ベースラインリザーバに格納された離散的待ち時間値の分布を表わし、前記方法はさらに、
前記コンピュータネットワークにおける前記第１の地点と前記コンピュータネットワークにおける前記第２の地点との間の情報の伝送に関連付けられた現在の待ち時間状態を推定するステップを含み、前記現在の待ち時間状態は、最近のサンプルキューに格納された離散的待ち時間値の分布を表わし、前記方法はさらに、
前記ベースライン待ち時間状態と前記現在の待ち時間状態との比較を行なうステップと、
前記ベースライン待ち時間状態と前記現在の待ち時間状態との前記比較に基づいて、前記コンピュータネットワークにおける前記第１の地点と前記コンピュータネットワークにおける前記第２の地点との間の情報の伝送に関連付けられた異常の存在を識別するステップとを含む、方法。
【請求項２】
前記コンピュータネットワークに動作可能に結合された複数のセンサを用いて、前記離散的待ち時間値をある取得レートで取得するステップをさらに含み、前記複数のセンサにおける各センサは、異なる地理的位置にあり、前記方法はさらに、
前記離散的待ち時間値を前記最近のサンプルキューに格納するステップを含む、請求項１に記載の方法。
【請求項３】
待ち時間値の前記分布を測定するステップは、
前記複数のセンサにおける第１のセンサで、前記コンピュータネットワークにおけるインターネットプロトコル（ＩＰ）アドレスと前記第１のセンサとの間の通信に関連付けられた複数の待ち時間値を示す複数のトレースルートデータパケットを受信するステップを含む、請求項２に記載の方法。
【請求項４】
前記複数のトレースルートデータパケットにおける各トレースルートデータパケットは、前記トレースルートデータパケットがいつ受信されたかを示すそれぞれのタイムスタンプを有し、
前記現在の待ち時間状態または前記ベースライン待ち時間状態のうちの少なくとも１つを推定するステップは、予め定められた時間範囲内でそれぞれのタイムスタンプを有する前記複数のトレースルートデータパケットのうちの選択されたグループに対して、中心傾向または分散度のうちの少なくとも１つを計算するステップを含む、請求項３に記載の方法。
【請求項５】
前記取得レートが、前記ベースラインリザーバまたは前記最近のサンプルキューのうちの少なくとも１つのサイズに基づくしきい値より上である場合、前記離散的待ち時間値を前記最近のサンプルキューに格納する前に、前記離散的な待ち時間値を間引くステップをさらに含む、請求項３に記載の方法。
【請求項６】
前記離散的待ち時間値の取得レートに基づいて、前記ベースラインリザーバまたは前記最近のサンプルキューのうちの少なくとも１つのサイズを設定するステップをさらに含む、請求項３に記載の方法。
【請求項７】
前記ベースライン待ち時間状態と前記現在の待ち時間状態との前記比較を行なうステップは、
第１のしきい値より上の、または第２のしきい値より下の離散的待ち時間値を却下するステップ、
前記ベースライン待ち時間状態のカーネル密度推定値を構築するステップ、
前記現在の待ち時間状態のカーネル密度推定値を構築するステップ、または、
前記ベースライン待ち時間状態および前記現在の待ち時間状態を計算するステップ、
のうちの少なくとも１つを含む、請求項１に記載の方法。
【請求項８】
前記最近のサンプルキューにおける最も古い離散的待ち時間値を前記ベースラインリザーバへ移動させるステップをさらに含む、請求項１に記載の方法。
【請求項９】
前記ベースラインリザーバから第１の離散的待ち時間値をランダムに除去するステップと、
前記第１の離散的待ち時間値を置換するために、第２の離散的待ち時間値を前記最近のサンプルキューから前記ベースラインリザーバへ移動させるステップとをさらに含む、請求項１に記載の方法。
【請求項１０】
前記ベースライン待ち時間状態と前記現在の待ち時間状態との前記比較に基づいて、前記異常のタイプを識別するステップをさらに含む、請求項１に記載の方法。
【請求項１１】
前記異常の影響を受けたインターネットプロトコル（ＩＰ）アドレスをユーザに通知するステップをさらに含む、請求項１に記載の方法。
【請求項１２】
前記異常に基づいて、前記コンピュータネットワークにおける前記第１の地点と前記コンピュータネットワークにおける前記第２の地点との間の通信をルーティングするステップをさらに含む、請求項１に記載の方法。
【請求項１３】
前記コンピュータネットワークにおける、または前記コンピュータネットワークに結合されたドメイン名システム（ＤＮＳ）サーバで、ＤＮＳ要求を受信するステップと、
前記異常に基づいて、前記ＤＮＳ要求への応答を発行するステップとをさらに含む、請求項１に記載の方法。
【請求項１４】
コンピュータネットワークを監視する方法であって、前記方法は、
前記コンピュータネットワーク中に分散された複数のコレクタデバイスから複数の伝送待ち時間値を受信するステップを含み、前記複数の伝送待ち時間値における伝送待ち時間値は、前記複数のコレクタデバイスにおけるそれぞれのコレクタデバイスと前記コンピュータネットワークにおけるそれぞれのターゲットコンピューティングデバイスとの間のそれぞれの伝送待ち時間を示し、前記方法はさらに、
前記複数のコレクタデバイスにおける各コレクタデバイスについて、前記複数の伝送待ち時間値の第１のサブセットに少なくとも部分的に基づいて、複数のターゲットコンピューティングデバイスにおける第１のターゲットコンピューティングデバイスへの伝送についての予期される伝送待ち時間状態を計算するステップと、
前記複数のコレクタデバイスにおける各コレクタデバイスについて、前記複数の伝送待ち時間値の第２のサブセットに少なくとも部分的に基づいて、前記第１のターゲットコンピューティングデバイスへの前記伝送についての現在の伝送待ち時間状態を計算するステップと、
複数のコレクタデバイスにおける各コレクタデバイスについて、前記現在の伝送待ち時間状態と前記予期される伝送待ち時間状態との比較を行なうステップと、
前記現在の伝送待ち時間状態と前記予期される伝送待ち時間状態との前記比較に少なくとも部分的に基づいて、前記第１のターゲットコンピューティングデバイスに関連付けられた異常を推測するステップとを含む、方法。
【請求項１５】
前記第１のターゲットコンピューティングデバイスのインターネットプロトコル（ＩＰ）アドレスに基づいて、前記異常の影響を受けた前記コンピュータネットワークの一部を識別するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記異常に基づいて、トラフィックを、代替インターネットサービスプロバイダを介して、前記複数のターゲットコンピューティングデバイスにおける第２のターゲットコンピューティングデバイスへルーティングするステップをさらに含む、請求項１５に記載の方法。
【請求項１７】
異常通知をユーザへ送信するステップをさらに含み、前記異常通知は、前記異常の重症度、または前記異常の影響を受けた前記コンピュータネットワークの前記一部、のうちの少なくとも１つを表わす、請求項１５に記載の方法。
【請求項１８】
コンピュータネットワークにおけるパフォーマンス異常を検出する方法であって、前記方法は、
第１のネットワークセンサによって収集された複数のトレースルートデータパケットを、プロセッサで受信するステップを含み、前記複数のトレースルートデータパケットにおける各トレースルートデータパケットは、前記第１のネットワークセンサとターゲットデバイスとの間のそれぞれの通信に関連付けられた待ち時間値を示し、前記方法はさらに、
前記複数のトレースルートデータパケットによって表わされる待ち時間状態を、前記プロセッサを介して計算するステップと、
前記待ち時間状態と予期される待ち時間状態との比較を行なうステップと、
前記比較に少なくとも部分的に基づいて、パフォーマンス異常の存在を推測するステップとを含む、方法。
【請求項１９】
前記比較を行なうステップは、
前記第１のネットワークセンサによって収集されたデータの信頼性の関数としての第１のネットワークセンサ予想を、前記プロセッサを介して判断するステップと、
前記第１のネットワークセンサ予想と、少なくとも、第２のネットワークセンサによって収集されたデータに基づく第２のネットワークセンサ予想とに少なくとも部分的に基づいて、コヒーレンス値を計算するステップとを含み、
前記第２のネットワークセンサによって収集された前記データは、前記第２のネットワークセンサと前記ターゲットデバイスとの間の待ち時間値を表わす、請求項１８に記載の方法。
【請求項２０】
前記パフォーマンス異常の影響を受けたインターネットプロトコル（ＩＰ）アドレスを判断するステップをさらに含む、請求項１８に記載の方法。
【請求項２１】
前記異常の影響を受けた前記ＩＰアドレスに基づいて、トラフィックを、代替インターネットサービスプロバイダを介して、前記ターゲットデバイスへルーティングするステップをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記コンピュータネットワークにおける、または前記コンピュータネットワークに結合されたドメイン名システム（ＤＮＳ）サーバで、ＤＮＳ要求を受信するステップと、
前記異常の影響を受けた前記ＩＰアドレスに基づいて、前記ＤＮＳ要求への応答を発行するステップとをさらに含む、請求項２０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願との相互参照
本願は、「情報伝送パフォーマンス警告を生成するための方法、システム、および装置」（Methods, Systems, and Apparatus to Generate Information Transmission Performance Alerts）と題された、２０１５年７月２２日に出願された米国出願第６２／１９５，４７８号の米国特許法第１１９条（ｅ）の優先権利益を主張する。上に引用された出願は、その全体がここに引用により援用される。
【背景技術】
【０００２】
背景
インターネットとは、パケット交換プロトコルのインターネットプロトコル（Internet Protocol：ＩＰ）ファミリーを使用して通信する相互接続されたコンピュータネットワークのグローバルなシステムである。インターネットに接続されたデバイス同士は、典型的には複数のビット数（たとえば、ＩＰｖ４については３２ビット、ＩＰｖ６については１２８ビット）として表わされる特定のＩＰアドレスにアドレス指定された情報のパケットを交換することによって、互いに通信する。
【０００３】
ルータ、スイッチ、ブリッジ、および他のデバイスは、各パケットを、当該パケットのＩＰアドレスに基づいて、その宛先へ転送する。ルータなどのいくつかのデバイスは、たとえば輻輳を避けるために、または利用可能な経路間でトラフィック負荷を分散させるために、パケットを、当該パケットの宛先への異なる経路上のトラフィックに基づいてルーティングすることができる。ルータも、パケットを、当該パケットによって搬送されるデータのタイプに基づいてルーティングしてもよい。たとえば、ルータは、待ち時間を不必要に増加させないようにするために、音声または映像データといった待ち時間に影響されやすいデータを搬送するパケットを、他のパケットに先立って伝送してもよい。
【０００４】
インターネットに接続された各ルータは、それ自体のＩＰアドレスを１つ以上有しており、インターネット上の多くのノードのうちの１つを形成する。インターネットはパケット交換を使用し、多くのノードを有しているため、それは、影響を受けたエリアを迂回するようにトラフィックを動的にルーティングすることによって、機器故障、自然災害、政治事件などによる重大なノードの損失に耐えることができる。にもかかわらず、あるノードの一時的損失でさえ、接続性を減少させるかまたは待ち時間を増加させることによってインターネットサービスを混乱させるおそれがある。インターネットサービスが混乱すると、影響を受けたエリアにおいておよびおそらくは当該エリアを超えてコンテンツプロバイダがコンテンツを消費者に確実に配信するためにより費用がかかるおそれがある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
概要
発明者らは、ノード故障などによって生じたインターネットサービスでの混乱は通常のネットワークパフォーマンスパターンからのずれをもたらす場合がある、ということを認識してきた。異常とも呼ばれるこれらのずれは、グローバルに分散されたトレースルートデータコレクタシステムによって取得されたトレースルートデータを使用して検出され得る。当該システムが異常を検出すると、それは、その異常についてのパフォーマンス警告を発行してもよい。場合によっては、当該システムは異常を特徴付け、異常の特性に基づいて、異常を引き起こす原因となったインターネットサービス混乱の存在、位置、および／またはタイプを判断してもよい。
【課題を解決するための手段】
【０００６】
いくつかの実現化例では、マスターサーバは、第１のネットワークセンサまたはトレースルートデータコレクタから、当該ネットワークセンサとターゲットコンピューティングデバイスとの間の伝送待ち時間を示すトレースルートデータを受信する。マスターサーバは、ターゲットコンピューティングデバイスに対する予期される待ち時間と現在の待ち時間との差異が著しいか、および／または予め規定されたしきい値を越えているかどうかを判断することによって、異常表示を識別することができる。同様に、マスターサーバは、第２のネットワークセンサまたはトレースルートデータコレクタによって送信されたトレースルートデータパケットを受信することができる。マスターサーバは、ターゲットコンピューティングデバイスに対する予期される待ち時間と現在の待ち時間との差異が著しいか、および／または予め規定されたしきい値を越えているかどうかを判断することによって、異常表示を識別することができる。
【０００７】
マスターサーバは、トレースルートデータコレクタから収集されたデータに由来した１つ以上の異常表示を利用してコヒーレンス値または信頼値を計算し、さらに、第１および第２のトレースルートデータコレクタから計算された異常表示に少なくとも基づいてネットワークパフォーマンス異常推測を行なうことができる。
【０００８】
いくつかの実現化例では、マスターサーバは、コンピュータネットワークにおける第１の地点とコンピュータネットワークにおける第２の地点との間の情報の伝送に関連付けられたベースライン待ち時間状態を推定することができる。そのようなベースライン待ち時間状態は、ベースラインリザーバに格納された離散的待ち時間値の分布を表わす。さらに、マスターサーバは、コンピュータネットワークにおける第１の地点とコンピュータネットワークにおける第２の地点との間の情報の伝送に関連付けられた現在の待ち時間状態を推定することができる。そのような現在の待ち時間状態は、最近のサンプルキューに格納された離散的待ち時間値の分布を表わす。続いて、マスターサーバは、推定されたベースライン待ち時間状態と推定された現在の待ち時間状態との比較を行なうことによって、第１の地点と第２の地点との間の異常の存在を識別することができる。
【０００９】
いくつかの実現化例では、マスターサーバは、多くのネットワークセンサまたはトレースルートデータコレクタからトレースルートデータを受信する。トレースルートデータパケットは、多くのトレースルートデータコレクタの各々と１組のターゲットコンピューティングデバイスとの間の伝送待ち時間データを含む。伝送待ち時間データは、異なる期間で観察される伝送待ち時間を表わし得る。たとえば、第１の１組のトレースルートデータは、時間Ｔｌから時間Ｔ２まで観察された伝送待ち時間を表わし、一方、第２の１組のトレースルートデータは、後の（およびおそらくは重複する）期間、たとえば時間Ｔ３から時間Ｔ４まで観察された伝送待ち時間を表わし得る。
【００１０】
マスターサーバは、第１の１組のトレースルートデータに基づいて、トレースルートデータコレクタの各々とターゲットコンピューティングデバイスとの間の予期される待ち時間値を計算することができる。加えて、マスターサーバは、第２の１組のトレースルートデータに基づいて、トレースルートデータコレクタの各々とターゲットコンピューティングデバイスとの間の現在の待ち時間値を計算することができる。マスターサーバはさらに、各トレースルートデータコレクタについて、コンピューティングターゲットデバイスまたはコンピューティングターゲットデバイスのグループに対する現在の待ち時間値と予期される待ち時間値との差異を計算することができる。その後、マスターサーバは、１つ以上のトレースルートデータコレクタと、１つのターゲットコンピューティングデバイスおよび／または１組のターゲットコンピューティングデバイスとに関連付けられた異常を推測することができる。
【００１１】
異常についての情報は、コンピュータネットワークの性能を向上させるために、さまざまな異なるやり方で使用され得る。たとえば、マスターサーバは、異常のタイプ、重症度、位置などについての自動通知を発行してもよい。ユーザ、ルータ、およびサーバを含む、この通知の受信者は、異常についてのこの情報を使用して、トラフィックを適切にルーティングすること、たとえば、輻輳を減少させること、接続性問題の影響を受けたエリアを避けること、負荷を分散させること、待ち時間を減少させることなどができる。たとえば、ドメイン名システム（domain name system：ＤＮＳ）サーバが異常通知を受信した場合、ＤＮＳサーバは異常に基づいてＤＮＳ要求に応答してもよい。同様に、異常が第１のインターネット・サービス・プロバイダ（Internet Service Provider：ＩＳＰ）に影響を与えるものの、第２のＩＳＰには影響を与えないことを異常通知が示す場合、ルータが、異常を避けるために、第２のＩＳＰを介してトラフィックをルーティングしてもよい。
【００１２】
以下により詳細に説明される前述の概念および追加の概念のすべての組合せが（そのような概念が互いに矛盾しない場合）ここに開示されるこの発明の主題の一部として考えられる、ということが理解されるべきである。特に、この開示の最後に現われる、請求される主題のすべての組合せは、ここに開示されるこの発明の主題の一部として考えられる。引用により援用される任意の開示にも現われ得る、ここに明示的に採用された用語は、ここに開示される特定の概念と最も一致する意味を与えられるべきである、ということも理解されるべきである。
【００１３】
図面の簡単な説明
当業者であれば、図面は主として例示を目的とするものであり、ここに説明されるこの発明の主題の範囲を限定するよう意図されてはいない、ということを理解するであろう。図面は必ずしも縮尺通りではなく、場合によっては、ここに開示されるこの発明の主題のさまざまな局面は、異なる特徴の理解を容易にするために、図面において誇張または拡大して示される場合がある。図面では、同じ参照符号は概して、同じ特徴（たとえば、機能的に同様の、および／または構造上同様の要素）を指す。
【図面の簡単な説明】
【００１４】
【図１】マスターサーバと、ルーティングデバイスと、トレースルートコレクタデバイスと、ターゲットコンピューティングデバイスとを含む、パフォーマンス警告システムの一例を示す図である。
【図２】ハードウェアモジュールとソフトウェアモジュールとを含むマスターサーバの一例のブロック図である。
【図３】ハードウェアモジュールとソフトウェアモジュールとを含むトレースルートコレクタデバイスの一例のブロック図である。
【図４】ＴＴＬをインクリメントすることによって（図１上に暗い矢印で示された）特定のトレースルートを判断するためのプロセスを示す図である。
【図５Ａ】ターゲットコンピューティングデバイスに対してコレクタによって取得されたトレースルートデータの一例を示す図である。
【図５Ｂ】データ平滑化または正規化プロセスの一例を示す図である。
【図５Ｃ】データ平滑化または正規化プロセスの一例を示す図である。
【図５Ｄ】データ平滑化または正規化プロセスの一例を示す図である。
【図６Ａ】新しいトレースルートデータと、最近のトレースルートデータの集合と、ベースライントレースルートデータの集合とを含む、トレースルートデータ置換ポリシーを示す図である。
【図６Ｂ】新しいトレースルートデータと、最近のトレースルートデータの集合と、ベースライントレースルートデータの集合とを含む、トレースルートデータ置換ポリシーを示す図である。
【図６Ｃ】新しいトレースルートデータと、最近のトレースルートデータの集合と、ベースライントレースルートデータの集合とを含む、トレースルートデータ置換ポリシーを示す図である。
【図７】ターゲットコンピューティングデバイスと、コレクタと、ルーティングデバイスとを含む、グローバルに分散されたシステムのサブセットを示す図である。
【図８】本発明の一実施形態に従った、コンピュータネットワークにおけるパフォーマンス異常の検出のための方法を示す図である。
【図９】本発明の追加の一実施形態に従った、コンピュータネットワークにおける異常を検出するための方法を示す図である。
【図１０】本発明のさらに別の実施形態に従った、複数のコレクタを含むコンピュータネットワークにおけるパフォーマンス異常を検出するための方法を示す図である。
【図１１Ａ】１組の３つの別個の（しかし地理的に近い）トレースルートコレクタから、イラクのスコープスカイ・コミュニケーション・アンド・インターネット社（ScopeSky Communication and Internet Ltd）（ＡＳ５０５９７）によって制御されるＩＰアドレスのグループまで測定されるような、往復待ち時間のプロットである。
【図１１Ｂ】１組の３つの同様のコレクタから、中国のパックネット（Pacnet）によって制御される特定のネットワークプレフィックス（２２２．１２６．１２８．０／２３）におけるＩＰアドレスまで測定されるような、往復待ち時間のプロットである。
【図１１Ｃ】１組の３つの同様のコレクタから、南アフリカのテネット（TENET）（ＡＳ２０１８）によって制御されるアドレスまで測定されるような、往復待ち時間のプロットである。
【図１１Ｄ】１組の３つの同様のコレクタから、ルーマニアのブカレストのＲＣＳ＆ＲＤＳによって制御される特定のネットワークプレフィックス（２１３．１５４．１００．０／２３）におけるＩＰアドレスまで測定されるような、往復待ち時間のプロットである。
【図１２】警告システムによって生成された警告メッセージ内に含まれるコンテンツの一例を示す図である。
【発明を実施するための形態】
【００１５】
本技術の特徴および利点は、以下に述べる詳細な説明を図面とともに解釈すれば、より明らかになるであろう。
【００１６】
詳細な説明
以下は、情報伝送パフォーマンス警告をローカルおよびグローバルなスケールで生成するためのこの発明のシステム、方法、および装置に関する、ならびにそれらの実施形態の、さまざまな概念のより詳細な説明である。開示される概念はどの特定の態様の実現化例にも限定されないため、上に紹介された、および以下により詳細に説明されるさまざまな概念は、多くのやり方のうちのいずれでも実現され得る、ということが理解されるべきである。具体的な実現化例および用途の例は、主として例示を目的として提供される。
【００１７】
はじめに
インターネットパフォーマンスの１つの尺度は、インターネット上の２つの地点間でパケットを伝送することに関連付けられた時間遅延、すなわち待ち時間である。総待ち時間は、パケットがその送信元と宛先との間を伝搬するのにかかる時間に依存する。待ち時間は、２つの地点を隔てる物理的距離と光速との積によって与えられる下限を有する。実際には、総待ち時間は、パケットが光ファイバーなどに沿って２つの地点間を伝搬するのにかかる時間に依存する。総待ち時間はまた、ルータ、スイッチ、およびブリッジといった中間デバイスが、パケットをその送信元と宛先との間でルーティングするのにかかる時間にも依存する。場合によっては、特定の１対の地点間には多くの経路があるかもしれず、各経路は異なる待ち時間を有するかもしれない。各経路についての待ち時間はまた、トラフィック輻輳、機器故障などによって変動するかもしれない。ある場合には、これらの変動は、インターネット使用時の周期的変動（たとえば、夜のストリーミングビデオに関連付けられた日内変動）によって生じるかもしれない。他の場合には、これらの変動は、機器故障などによって生じる、インターネットトラフィックパターンにおける異常なまたは不規則なずれを表わすかもしれない。
【００１８】
インターネットトラフィックにおける変動は、グローバルに分散されたコレクタのネットワーク、すなわち、略してコレクタネットワークにおける各コレクタからの待ち時間を測定するためにトレースルートユーティリティを使用して識別され、追跡され得る。当業者によって理解され、以下により詳細に説明されるように、トレースルートとは、インターネットを通る、送信元コンピュータ（たとえばコレクタ）と特定された宛先コンピュータとの間のルートを記録するユーティリティである。トレースルートデータは、宛先へのルートに沿ったルータおよび他のデバイスのアドレス双方と、宛先へのルートに沿った各ホップに関連付けられた待ち時間とを含む。
【００１９】
グローバルに分散されたコレクタのネットワークは、インターネットに接続されたネットワークおよびデバイスの少なくとも一部について、トレースルートデータを収集する。全体として、コレクタネットワークは、典型的な１日に、およそ２，０００，０００個の固有アドレスを監視する場合がある。コレクタネットワークは、高トラフィックのノードに位置するルータといったいくつかのデバイスについては、他のデバイスよりも頻繁にトレースルートデータを収集する場合がある。加えて、コレクタネットワークにおける異なるコレクタは、同じ宛先、異なる宛先、同じ宛先への異なるルート、および／またはいくつかのルートに共通のホップについて、トレースルートデータを収集する場合がある。
【００２０】
トレースルートデータは、ほぼ毎日１回収集されるインターネット上のいくつかの地点までの測定値と、毎秒何回も測定されるインターネット上の他の（より一般的には横断される）地点までの測定値とを含むデータのストリームとして考えられ得る。さらに説明すると、各トレースルートは、１組の［コレクタ、レスポンダ、待ち時間］タプルへ分解され得る。ホップＷ、Ｘ、Ｙ、およびＺから順調なホップ応答を引き出すコレクタＡからのトレース（たとえば、Ａ→Ｗ（１０ｍｓ）→Ｘ（３０ｍｓ）→Ｙ（４５ｍｓ）→Ｚ（５５ｍｓ））は、以下のようになる：
［Ａ、Ｗ、１０ｍｓ］
［Ａ、Ｘ、３０ｍｓ］
［Ａ、Ｙ、４５ｍｓ］
［Ａ、Ｚ、５５ｍｓ］
これらのタプルはトレース分解ステップから出現するため、それらはもはや、それらの内部に含まれる経路情報を有していない。さらに、異なる［コレクタ、レスポンダ］対が異なるレートでデータストリームに現われるかもしれない。なぜなら、一般的には横断されるルータ（Ｗ、Ｘ、およびＹなど）は繰り返し観察／測定されがちである一方、終点（Ｚ）はたまにしか（たとえば１日に１回しか）見られないかもしれないためである。各［コレクタ、レスポンダ］対は、それ自体の最近のサンプルキューおよびベースラインリザーバを有する。キューおよびリザーバのサイズは、対ごとに固有である観察頻度に基づいて調整され得る。
【００２１】
コレクタネットワークは、トレースルートデータから、インターネット上のＩＰアドレスの多くについて待ち時間データを計算し、当該待ち時間データをベースライン待ち時間データとして蓄積する（トレースルートデータは、場合によってはこのシステムによって無視され得る経路情報を含む）。このベースライン待ち時間データは、コレクタネットワークにおける各コレクタによって監視された各ＩＰアドレスに関連付けられた待ち時間の分布、すなわち待ち時間状態を含んでいてもよい。コレクタネットワークはトレースルートデータを継続的に収集するため、それは、インターネット上のノードおよび接続部の数および配置の変化による待ち時間の変化も検出する。言い換えれば、トレースされているルートに沿った各ホップ応答は、トレースルートコレクタと、応答する特定のホップに関連付けられたノードとの間の新たな待ち時間測定値として処理され得る。その結果、コレクタネットワークによって収集された最も最近のトレースルートデータは、インターネットの現在の状態（または、より正確には、データが収集されたときのインターネットの状態）を表わす。コレクタネットワークが更新された最近のトレースルートデータを収集する際、それは、以前に収集されたトレースルートデータをベースライン待ち時間データに追加し、そのため、ベースライン待ち時間データは、インターネット接続の進展を時間とともに追跡する。その結果、ベースライン待ち時間状態は、地理的領域、ターゲットコンピューティングデバイス、相互接続された１組のルーティングデバイス、および／または１つ以上のターゲットコンピューティングデバイスに関するインターネットの正規／通常順序を記述することができる。
【００２２】
コレクタネットワークの一部である、またはコレクタネットワークに動作可能に結合された警告システムは、ベースライン待ち時間データとより最近に収集された待ち時間データとの類似性を計算する。たとえば、警告システムは、インターネット上の特定の１対の地点間のパケット伝送についての現在の待ち時間状態（離散的待ち時間値の最近測定された分布）を、同じ１対の地点間のベースライン待ち時間状態（離散的待ち時間値のベースライン分布）と比較してもよい。警告システムは、現在の待ち時間状態がインターネット異常を表わすかどうかを判断するために１つ以上の類似性メトリックを計算することによって、この比較を行なってもよい。警告システムはまた、影響を受けた地理的エリア、影響を受けていない代替トラフィックルート、および異常の分類を含むもののそれらに限定されない、異常に固有の情報を判断してもよい。
【００２３】
現在の待ち時間状態が異常であることを比較が示す場合、警告システムは、異常、影響を受けたルート、影響を受けていない代替ルート、異常のタイプなどを示すパフォーマンス警告を発行してもよい。パフォーマンス警告は、１組のコレクタ（１組の関連するＩＰ／コレクタタプルとしても公知）から見られるような、特定の位置における特定のネットワークに属するＩＰアドレスのグループ上で異常を観察した後に生成され得る。これは、単一のネットワークノードの誤動作または単一のコレクタでのネットワークパフォーマンス問題による誤検出を防止するのに役立つ。警告がいったん生成されると、それは、影響を受けたネットワークまたは地理的エリアに関心を示した顧客へ、もしくは、詳細調査のためにアナリストへ送信されてもよい。
【００２４】
現在の待ち時間状態とベースライン待ち時間状態との適切な比較を保証するために、コレクタシステムは、同じ取得プロセス（または同じ組のプロセス）を使用して、待ち時間状態および根底的な離散的待ち時間値を収集し、判断してもよい。一貫した待ち時間収集および判断プロセスを使用することは、測定ノイズの変化による誤検出が比較に現われることを減少させ、または防止する。加えて、現在の待ち時間状態およびベースライン待ち時間状態における待ち時間値分布は、ダイナミクスを取込むのに十分大きいものの、異常なルーティング挙動による待ち時間の変化を呈するのに十分小さくなるように選択されてもよい。
【００２５】
コンピュータネットワークトラフィック異常を検出するためのシステム
図１は、インターネットなどのコンピュータネットワークにおけるパフォーマンス異常を検出するパフォーマンス警告システムの一例を示す。図１に示すパフォーマンス警告システムは、パフォーマンス警告サーバ１１０（マスターサーバ１１０としても公知）を含み、それは、パフォーマンス警告データベース１１２と、１つ以上のクライアント１１４と、トレースルートコレクタ１２０のネットワークとに結合される。明確にするために、図１はたった１つのパフォーマンス警告サーバ１１０およびデータベース１１２を示しているが、システム１００は、同期された複数のマスターサーバ１１０およびデータベース１１２を含んでいてもよく、および／または使用してもよい。複数のマスターサーバ１１０が使用される場合、マスターサーバ１１０は、複数のデータベース１１２上に分散され得るデータを処理するために同期され得る。したがって、データベース１１２同士は同期可能であり、このため、有線および／または無線通信プロトコルおよび／または手法を使用して通信可能である。
【００２６】
トレースルートコレクタ１２０は、自律システム（Autonomous System；ＡＳ）１３０またはルーティングドメインに各々属する、それらのそれぞれのプロバイダのデータセンター内に存在する実在マシンまたは仮想マシンである。動作時、トレースルートコレクタ１２０は、それら自体のＡＳ１３０内および他のＡＳ１３０内のルータ１４０、ターゲットコンピューティングデバイス１５０、および境界ゲートウェイプロトコル（Border Gateway Protocol：ＢＧＰ）ルータ１６０（境界ルータ１６０としても公知）へのルートに関連付けられた待ち時間を測定する。
【００２７】
ＡＳ１３０は、コンピューティングデバイス１５０の郵便番号と考えられ得る。すなわち、各ＡＳ１３０は、あるＩＳＰに基づくとともに範囲が必ずしも地理的ではない、インターネットの近隣区域（neighborhood）として描写され得る。各ＡＳ１３０内には、境界ゲートウェイプロトコル（ＢＧＰ）ルータ１６０（境界ルータ１６０としても公知）と、ＡＳ１３０のルーティングポリシーを実現し、隣り合うＡＳ１３０内のＢＧＰルータ１６０への物理的接続を維持する他のルータ１４０とがある。出願時点では、グローバルなインターネット上のＡＳの数は、５１，０００以上である。
【００２８】
より正式には、ＡＳ１３０は、単一の管理エンティティ（大学、企業、事業部など）のために共通ネットワークアドミニストレータ（またはアドミニストレータのグループ）によって制御される明確に定義された単一のルーティングポリシーを有する、ＩＰネットワークの接続されたグループである。ＡＳ１３０における所与のＩＰネットワーク内のノードは同じネットワークプレフィックスを共有し、そのプレフィックス内の個々のＩＰアドレスをインターネット接続性のために採用する。たいていの自律システム１３０は、複数のネットワークプレフィックスを含む。ＡＳ１３０は、ＴＣＰ／ＩＰネットワークにおいてドメイン間ルーティングを行なうために使用される外部ゲートウェイプロトコル（exterior gateway protocol：ＥＧＰ）であるＢＧＰを使用して、他のＡＳ１３０とルーティング情報を共有することができる。
【００２９】
ルーティング情報は、ＢＧＰ更新を交換するために境界ルータ１６０からそのＢＧＰピアのうちの１つへの接続を確立することによって、ＡＳ１３０内で、またはＡＳ１３０間で共有され得る。当業者には理解されるように、境界ルータ１６０間でデータを交換するプロセスは、「ピアリング」と呼ばれる。ピアリングセッションでは、２つのネットワークが直接接続してデータを交換する。内部ＢＧＰピアリングセッションは、単一のＡＳ１３０内で境界ルータ１６０同士を直接接続することを伴う。外部ＢＧＰピアリングセッションは、隣り合うＡＳ１３０における境界ルータ１６０同士を互いに直接接続することを伴う。
【００３０】
トレースルートコレクタデバイス１２０は、（インターネットに接続された任意のデバイスであり得る）特定のターゲットへの道に沿って、ルータ１４０および境界ルータ１６０中のルートを探索し、トレースルートデータを伝送する。トレースルートコレクタデバイス１２０は、収集されたメッセージデータを、図１に示すような１つ以上のデータベース１１２にデータを格納またはアーカイブするマスターサーバ１１０へ転送することができる。マスターサーバ１１０はデータベース１１２からのトレースルートデータを処理して、処理されたデータにアクセスし、当該データを操作し、および／または他の態様で表示するためのツールをクライアント１１４に提供する。それは、ネットワーク経路を監視し、パフォーマンス異常を検出し、ネットワーク異常に基づいてルーティング決定を行なうために使用され得る。当該データは、クライアント１１４が複数の有利な地点（コレクタデバイス１２０）からネットワーク経路を監視することを可能にする。
【００３１】
データベース１１２はまた、グローバルなルーティング状態、ルーティングレジストリデータ、ドメイン名システム（ＤＮＳ）データ、インターネットネットワークデータ、および／または、トレースルートデータに関するかまたは由来する他のデータといった、他のデータを含み得る。これらのデータは、観察された待ち時間異常を集約し、相関させ、クラスタ化するために、および、データを理解しようとする人間のオペレータまたはアナリストをサポートするために使用され得る。
【００３２】
マスターサーバおよびトレースルートコレクタデバイス
図２は、ユーザインターフェイス２１２に結合されたプロセッサ２１８と、通信インターフェイス２１９と、実行可能命令２１６を格納するメモリ２１４とを含むマスターサーバ１１０の一例のブロック図を示す。これらの実行可能命令２１６はアナリストエンジン２１７を規定し、それは、プロセッサ２１８によって実現される場合、インターネットトラフィックにおけるパフォーマンス異常を識別するためにトレースルートデータを分析する。
【００３３】
プロセッサ２１８は、ユーザおよび／またはシステムが生成した要求を実行するためのプログラムコンポーネントを実行するための１つ以上の高速データ処理ユニットを含み得る。これらの高速データ処理ユニットは、集積システム（バス）コントローラ、メモリ管理制御ユニット、浮動小数点ユニット、さらには、グラフィック処理ユニット、デジタル信号処理ユニットなどのような特殊処理サブユニットなどを含むもののそれらに限定されない、さまざまな特殊処理ユニットを取り入れることが多い。加えて、プロセッサ２１８は、内部高速アクセスアドレス指定可能メモリを含んでいてもよく、プロセッサ自体を越えてメモリをマッピングし、アドレス指定することが可能であってもよい。内部メモリは、高速レジスタ、さまざまなレベルのキャッシュメモリ（たとえば、レベル１、２、３など）、ＲＡＭ、ＲＯＭなどを含んでいてもよいが、それらに限定されない。プロセッサ２１８は、命令アドレスを介してアクセス可能なメモリアドレス空間の使用を通して、メモリ２１４および実行可能命令２１６にアクセスしてもよく、その命令アドレスをプロセッサ２１８は構築し復号することができ、それが、メモリ状態および／または実行可能命令を有する特定のメモリアドレス空間への回路経路にアクセスすることを可能にする。
【００３４】
通信インターフェイス２１９は、入出力（Ｉ／Ｏ）インターフェイス、ストレージインターフェイス、ネットワークインターフェイスなどを含むもののそれらに限定されない、従来（必ずというわけではないが）アダプタカードの形をした多くのインターフェイスアダプタを受入れ、接続し、および／または当該インターフェイスアダプタに通信する。たとえば、通信インターフェイス２１９に含まれるネットワークインターフェイスは、図３のトレースルートコレクタデバイス１２０との間で情報を送受信するために利用され得る。
【００３５】
ユーザインターフェイスディスプレイ２１２は、ビデオインターフェイスからの信号を受入れるインターフェイス（たとえば、ＤＶＩ回路およびケーブル）を有する、陰極線管（Cathode Ray Tube：ＣＲＴ）または液晶ディスプレイ（Liquid Crystal Display：ＬＣＤ）ベースのモニタを含み得る。これに代えて、ユーザインターフェイスディスプレイ２１２は、タッチスクリーンおよび／または他のコンテンツ表示デバイスを含み得る。ビデオインターフェイスは、メモリ２１４に格納されプロセッサ２１８によって実行される実行可能命令２１６によって生成された情報を合成する。実行可能命令２１７は、１つ以上のトレースルートコレクタデバイス１２０から取得されたデータを処理し分析する１組の命令を有するアナリストエンジンモジュール２１７を含む。ユーザインターフェイスディスプレイ２１２は、アップルＯＳ、Ｗｉｎｄｏｗｓ（登録商標）ＯＳ、Ｌｉｎｕｘ（登録商標）、Ｕｎｉｘ（登録商標）ベースのＯＳなどといったオペレーティングシステムおよび／または動作環境によって、当該オペレーティングシステムおよび／または動作環境を用いて、ならびに／もしくは、当該オペレーティングシステムおよび／または動作環境上に提供されるような、従来のグラフィックユーザインターフェイスを含んでいてもよい。ユーザインターフェイスディスプレイ２１２は、テキスト機能および／またはグラフィック機能を通した、プログラムコンポーネントおよび／またはシステム機能の表示、実行、対話、操作、および／または動作を可能にしてもよい。ユーザインターフェイスディスプレイ２１２は、ユーザがコンピュータシステムに影響を与え、コンピュータシステムと対話し、および／またはコンピュータシステムを動作させ得る機能を提供する。ユーザインターフェイスディスプレイ２１２は、それ自体を含むコンポーネントの集合における他のコンポーネント、および／または機能などと通信してもよい。ユーザインターフェイスディスプレイ２１２は、プログラムコンポーネント、システム、ユーザ、および／またはデータ通信、要求、および／または応答を含み、通信し、生成し、取得し、および／または提供してもよい。
【００３６】
図３は、ハードウェアモジュールとソフトウェアモジュールとを含むトレースルートコレクタデバイス１２０の一例のブロック図を示す。トレースルートコレクタデバイス１２０は、前述の通信インターフェイス２１９の特性と同様の特性を有する通信インターフェイス３２２を含む。プロセッサ３２４も、前述のプロセッサ２１８の特性に類似した特性を有し得る。メモリ３２６は、実行可能命令３２８と、１つ以上のターゲットコンピューティングデバイス（たとえば、図１のターゲットコンピューティングデバイス１５０ａ、１５０ｂ、および１５０ｃ）からトレースルートデータを収集する命令を有するトレース探索モジュール３２９とを含む。
【００３７】
トレースルートデータおよびデータ収集
図１および図４は、トレースルートデータシステムの動作原理を示す。トレースルートを行なうために、トレースルートコレクタ１２０ａは、インターネット・コントロール・メッセージ・プロトコル（Internet Control Message Protocol：ＩＣＭＰ）を使用して、第１のパケットを宛先コンピュータ（１５０ａ）へ送信する。トレースルートコレクタ１２０ａはまた、第１のパケットについてのホップリミット値を特定する。それは、「有効時間」（time to live：ＴＴＬ）として公知であり、１に等しい。第１のルータ１４０ａが第１のパケットを受信すると、それはＴＴＬを（１から０へ）デクリメントする。ＴＴＬ＝０のパケットを処理すると、第１のルータは、宛先コンピュータ１５０ａへの経路に沿った次のルータへ第１のパケットを転送する代わりに、「超過時間」メッセージ４０１ａをトレースルートコレクタ１２０ａへ返す。これにより、トレースルートコレクタ１２０ａは、ターゲットコンピュータ１５０ａへの経路上の第１のルータ１４０ａへのホップに関連付けられた待ち時間を判断することができる。トレースルートコレクタ１２０ａは次に、ＴＴＬ＝２の第２のパケットをターゲットコンピュータ１５０ａへ送信する。第２のルータ１６０ａは別の超過時間メッセージを返す、などとなっている。（ＴＴＬ＝３からＴＴＬ＝７を含む）その後のパケットは、ルータ１６０ｂ、１６０ｃ、１４０ｂ、１６０ｄ、および１６０ｅから超過時間メッセージを引き出す。宛先コンピュータ１５０ａがＴＴＬ＝８の最終パケットを受信すると、それは「エコー返答」メッセージ４０２をトレースルートコレクタ１２０ａへ返し、トレースルートコレクタ１２０ａが最終ホップの待ち時間を測定することを可能にする。
【００３８】
トレースルートコレクタデバイス１２０ａは、それがパケットを送信するたびにＴＴＬを増加させ、中間ルータからの「超過ＴＴＬ」応答４０１ａ、４０１ｂ、４０１ｃなどを監視することによって、宛先コンピュータ１５０ａへの経路上の連続ホップを発見する。収集された「超過ＴＴＬ」応答および「ＩＣＭＰエコー返答」４０２の順序およびタイミングは、ターゲットデバイス１５０ａに向かう途中でＩＣＭＰパケットによって横断されるルータのリストを構築するために、トレースルートコレクタデバイス１２０ａによって使用される。経路に沿った各ホップは、応答（超過ＴＴＬまたはエコー返答）の到着時間からＩＣＭＰエコー要求の送信時間を減算することによって計算された往復待ち時間を有する。
【００３９】
図５Ａは、図１のトレースルートコレクタ１２０によって取得されたトレースルートデータの一例を示す。図５Ａのトレースルートデータは、データパケットが、センサまたはトレースルートコレクタデバイスからターゲットコンピューティングデバイスまで通る経路を示す。トレースルートデータは、トレースルートコレクタデバイス１２０についての識別子および／またはＩＰアドレス５０１を含む、トレースルートにおける各デバイスについての識別子を含む。５０２ａおよび５０２ｂに含まれるＩＰアドレスは、グローバルまたはローカルなコンピュータネットワークの一部であるルータを表わし得る。トレースルートデータはまた、トレースルートコレクタデバイス５０１がルータ５０２ａおよび５０２ｂから応答を取得するのにそれぞれかかった、往復時間を表わす時間５０３ａおよび５０３ｂを含む。同様に、時間５０３ｃは、トレースルートコレクタデバイス１２０が、識別子５０４によって識別されたターゲットコンピューティングデバイスからＩＣＭＰエコー返答を取得するのにかかった時間を表わす。
【００４０】
場合によっては、１つ以上のトレースルートコレクタデバイスによって取得されたトレースルートデータは、以下に示すようなデータ構造の、中間の人間可読フォーマットを生成するために、マスターサーバ１１０によって処理され得る。
【００４１】
【数１】
2018521611.tif 000003
【００４２】
データ構造tr_base_fieldsは、現在の内部データフォーマット（たとえば、ＴｌまたはＴ５）を表わすデータバージョンdcvフィールドと、トレースルートが開始した時間を特定するtsフィールドと、たとえばインターネット・コントロール・メッセージ・プロトコル（ＩＣＭＰ）、ユーザ・データグラム・プロトコル（User Datagram Protocol：ＨＤＰ）、伝送制御プロトコル（Transmission Control Protocol：ＴＣＰ）、および同様のプロトコルといった１つ以上のインターネットプロトコルを特定するprotocolフィールドと、トレースルートデータの伝送に関連付けられたポート番号または識別子を特定するportフィールドと、トレースルートコレクタデバイスのＩＰアドレスを特定するcollector_ipフィールドと、コレクタデバイスの外部ＩＰアドレスを特定するcollector_external_ipフィールドと、コレクタデバイス名を特定するcollector_nameと、ターゲットデバイスのＩＰアドレスを特定するtarget_ipフィールドと、たとえば成功、ループ、到達不能、またはギャップといった停止原因を特定するhalt_reasonフィールドと、トレースルートデータ伝送中に記録されたホップを表わすhoprecordsリストとを含み得る。
【００４３】
hoprecordsリストは、１つ以上の要素を有し得る。各要素は、トレースルートコレクタおよびターゲットデバイスからのトレースルートにおけるターゲットデバイスまたはタイプルーティングデバイスを表わす。ルーティングデバイスは、ＩＰネットワーク間のデータトラフィックを調整するゲートウェイルータであり得る。加えて、ルーティングデバイスは、パケットがどのようにターゲットデバイスに到達できるかを指示する静的または動的な１組のルールを有するＩＰネットワーク内のあるインターフェイスから別のインターフェイスへデータパケットを向けることができる。hoprecordsリストの要素を表わすデータ構造は、以下のように提供される。
【００４４】
【数２】
2018521611.tif 000004
【００４５】
データ構造exは、ルーティングデバイスまたはターゲットデバイスを表わすＩＰアドレスh.ipと、トレースルートコレクタデバイス（たとえば、図４の１２０ｃ）によって送信されたトレースルート伝送に応答して、受容器デバイスからの受領確認伝送（たとえば、図４の４０１ａ〜４０１ｃおよび４０２）を受信するためにかかる時間を表わす往復遅延時間h.rttと、伝送失敗とみなされる前にトレースルート伝送パケットが通り得るホップの制限を特定する有効時間（ＴＴＬ）距離h.distと、伝送失敗とみなされる前にトレースルート伝送への受領確認が通り得る多くのホップを特定するＴＴＬ距離h.replyttlと、私的および／または公的ネットワーク内で通るルートを事前に判断するためにたとえばラベル交換経路を特定する１つ以上のマルチプロトコル・ラベル・スイッチング（Multiprotocol Label Switching：ＭＰＬＳ）タグmpls_tagsとを含み得る。
【００４６】
tr_base_fieldsおよびexデータ構造において示されるように編成された、収集されたトレースルートデータの一例を、以下に提供する。
【００４７】
【数３】
2018521611.tif 000005
【００４８】
図５Ｂ〜５Ｄは、待ち時間値を含むトレースルートデータを図５Ａに示すデータとして分布させることに適用され得るデータ平滑化または正規化プロセスの一例を示す。いくつかの実現化例では、マスターサーバ１１０は、１つ以上のコレクタによって受信されたトレースルートデータを、処理されるように準備することができる。データの準備は、トレースルートデータ内のノイズと考えられる外れ値および／または他の値の却下を含み得る。たとえば、ある百分位数（たとえば、１０番目、１５番目、２０番目、または第２５番目の百分位数）より上および／または下の待ち時間データが、分布から省略され得る。加えて、マスターサーバ１１０は、トレースルートデータから取得された離散的待ち時間値の分布（図５Ｃ）から、カーネル密度グラフ（図５Ｂ）を導き出すことができる。カーネル密度グラフは、たとえばσ２のカーネル幅でガウス合計手法（sum-of-Gaussians technique）を適用することによって、マスターサーバによって受信された各分布について推定され得る。その後、マスターサーバ１１０は、たとえば母集団サイズごとに１つ以上のカーネル分布推定値の高さを測定することによって、または、カーネル分布推定値から新たな分布を再度サンプリングすることによって、各分布を共有ベースで、等しい母集団サイズで計算することができる。カーネルの帯域幅は、ケースバイケースで構成され得る自由なパラメータである。同様に、サブ間隔、ビン、またはバケットは、それに応じて構成され得るある範囲のデータをカバーする自由なパラメータである、図５Ｄは、図の背景に示された柱状図上の離散的データに対応する、重複されたカーネル密度推定値を示す。
【００４９】
ベースライン待ち時間状態の蓄積および更新
図６Ａ〜６Ｃは、新しいトレースルートデータ、最近のトレースルートデータ、およびベースライントレースルートデータに基づいて、待ち時間状態を取得し、蓄積し、更新するためのトレースルートデータ置換ポリシーを示す。マスターサーバ１１０は、１つ以上のトレースルートコレクタデバイス１２０によって収集されたトレースルート記録を含むデータストリームを受信する。トレースルート記録の各々は、所与のトレースルートコレクタデバイス１２０とコンピュータネットワークにおける別のノードとの間の１つ以上のホップを表わす。上に示されたように、各ホップ記録は、ホップの往復時間（待ち時間）を含む。各ホップ記録はまた、hop_recordデータ構造において示されたようなタイムスタンプ、ホップ距離、および返答ＴＴＬを含んでいてもよい。
【００５０】
マスターサーバ１０１は、tr_base_fieldsデータ構造におけるタイムスタンプtsに基づいて、データストリームにおけるトレースルート記録をソートする。それはまた、タイムスタンプでソートされたトレースルート記録のホップ記録を、１組の時間順データサブストリームへと分解し、各サブストリーム６０４は、単一のコレクタと単一の受容器ＩＰアドレスとの間にサンプルを含む。これらのサンプルは、tr_base_fieldsデータ構造において記述されたコレクタと、測定値の各hop_recordのh.ipフィールドにおける受容器ＩＰアドレスとに基づいて、サブストリーム６０４へ向けられる。
【００５１】
サンプルは、図６Ａに示されるような最近のサンプルキュー（Recent Sample Queue：ＲＳＱ）６０１におけるメモリ１１４に一時的に保持され得る。マスターサーバ１１０のいくつかの場合では、受信されたサンプルは、ＲＳＱ６０１の末尾に押し付けられ得る。ＲＳＱ６０１は、予め構成された保持能力を含み得る。図６Ｂは、ＲＳＱ６０１の保持能力が消耗した場合はいつでも、マスターサーバ１１０は最も古いサンプルをＲＳＱ６０１の先頭からベースラインリザーバ（baseline reservoir：ＢＲ）６０２内へ移動させることができる、ということを示す。
【００５２】
所望すれば、ＲＳＱ６０１の保持能力は調整され得る。一般に、より小さいＲＳＱ保持能力は、システムがより迅速に異常に応答することを可能にするものの、システムを誤検出により敏感にする傾向がある。場合によっては、各［コレクタ、レスポンダ］対は、コレクタがレスポンダからサンプルを受信する観察された頻度に基づいたＲＳＱ保持能力を有する。（たとえば、レスポンダがインターネットの難所にあるルータであるために）コレクタがレスポンダからサンプルを頻繁に受信する場合、システムは、比較的短時間の間、受信されたサンプルを保持するように、ＲＳＱ保持能力を設定してもよい。また、それは、受信されたサンプルの一部（たとえば、１０番目ごとのサンプル）のみを保持してもよい。そして、それは、より多い数のサンプルを保持してもよい。しかし、（たとえば、レスポンダがインターネットの行き止まりにあるクライアントデバイスであるために）コレクタがレスポンダからサンプルを比較的たまにしか受信しない場合、システムは、比較的長時間の間、受信されたサンプルを保持するように、および／または、ＲＳＱ６０１において全体でより少数のサンプルを保持するように、ＲＳＱ保持能力を設定してもよい。たとえば、１０個未満のサンプルを保持するＲＳＱ６０１は、ほんの数個の逸脱したサンプルで多くの誤検出を生成するおそれがあり、一方、２００個を上回るサンプルを保持するＲＳＱ６０１は、最も頻繁に観察される［コレクタ、レスポンダ］対のみを除き、ゆっくり反応するかもしれない。
【００５３】
ＲＳＱ６０１の保持能力と同様に、ＢＲ６０２の保持能力は、予め定められた数のサンプルを保持するように予め構成され得る。ＲＳＱ保持能力が調整され得るのと同様に、ＢＲ保持能力は、コレクタがレスポンダからサンプルを受信する観察された頻度に基づいて、各［コレクタ、レスポンダ］対について設定されてもよい。典型的には、ＢＲ６０２は、対応するＲＳＱ６０１のおよそ５〜１０倍のサンプルを保持すべきである。
【００５４】
図６Ｃに示すように、ＢＲ６０２がその保持能力にいったん到達すると、１個以上のサンプル６０３をＢＲ６０２から除去し、それらを、１つ以上の置換ポリシー、たとえばターンテーブル置換ポリシーなどに従って、ＲＳＱ６０１から得られたサンプルと置換することにより、対応する数のサンプルをＢＲ６０２に追加することができる。
【００５５】
場合によっては、立退きポリシーとしても公知である置換ポリシーが、永続的な立退きのためにサンプルをＢＲ６０２からランダムに選択することを特定できる。そのような場合、各サンプルは、同じ立退き確率を有していてもよい。さらに、各サンプルは、関数［１−（ｌ／ｓ）］ｍによって定義されたＢＲ６０２同等物にとどまる確率を有していてもよく、式中、ｓは、ＢＲ６０２に保持されたサンプルの数であり、ｍは、ＢＲ６０２に配置された追加のサンプルの数である。
【００５６】
マスターサーバ１１０は、ＢＲ６０２に格納された離散的待ち時間値に基づいて、２つ以上のデバイス間の情報の伝送に関連付けられた伝送ベースライン待ち時間状態を判断することができる。ベースライン待ち時間状態は、ＢＲ６０２に保持されたサンプルに対して、たとえば離散的待ち時間値の代表値および／または分布の分散度といった１つ以上の記述統計を計算することによって、判断され得る。同様に、マスターサーバ１１０は、ＲＳＱ６０１に格納された離散的待ち時間値に基づいて、２つ以上のデバイス間の情報の伝送に関連付けられた現在の待ち時間状態を判断することができる。現在の待ち時間状態も同様に、ＲＳＱ６０１に保持されたサンプルに対して、代表値および／または分散度を含むもののそれらに限定されない１つ以上の記述統計を計算することによって、判断され得る。
【００５７】
場合によっては、ＢＲ６０２およびＲＳＱ６０１に含まれる分布は、マスターサーバ１１０によって実行される１つ以上のサンプリングポリシーおよび／または正規化ポリシーに従い得る。たとえば、マスターサーバ１１０は、待ち時間値分布から推測を引き出す際に、あるしきい値より下または上のサンプルを考慮に入れるべきでないと特定することによって、外れ値サンプルを省略するポリシーを適用してもよい。加えて、ＢＲ６０２およびＲＳＱ６０１における分布は、任意の統計的分析および／またはテストを行なう前に、任意の好適な動作によって平滑化および／または正規化され得る。好適な平滑化動作は、各分布についてカーネル密度を判断すること、分布の各々を共有ベースで、等しい母集団サイズで計算することなどを含むものの、それらに限定されない。
【００５８】
マスターサーバ１１０は、ベースライン待ち時間状態と現在の待ち時間状態との差異を分析することによって、１つ以上の情報伝送異常を識別することができる（以下に説明される図１１Ａ〜１１Ｄは、ベースラインリザーバおよび現在の待ち時間状態の双方からのサンプルを表示する）。そのような分析は、たとえば、対数尤度分析、ピアソンのカイ二乗検定、および同様の離散的な比較分析といった、ベース待ち時間状態および現在の待ち時間状態が同じ母集団から引き出された可能性を判断するための離散的な比較を含み得る。他の場合では、分析は、たとえば、２つの分布中の２つ以上の差異に敏感であるコルモゴロフ−スミルノフ分析および同様の統計的分析に基づいた連続的な比較を含み得る。
【００５９】
図７は、ターゲットコンピューティングデバイス１５０ａおよび１５０ｙと、トレースルートコレクタ１２０ａ〜１２０ｃと、ＡＳ境界ルーティングデバイス１６０ａ〜１６０ｆと、内部ルータ１４０ａ〜１４０ｃとを含む、図１に示すデバイスのサブセットを示す。それは、マスターサーバ１１０が２つ以上のデバイス間で判断された異常に基づいてどのように代替情報伝送ルートを判断できるかを示す。たとえば、コンピュータデバイス１５０ｙは、ターゲットデバイス１５０ａへ情報を伝送するための経路を２つ有する。第１の経路は、境界ルータ１６０ｃと、内部ルータ１４０ｂとを含む。第２の経路は、内部ルータ１４０ｃと、境界ルータ１６０ｆとを含む。双方の経路は、境界ルータ１６０ａ、１６０ｂ、および１６０ｄを含む。コレクタデバイス／ネットワークセンサ１２０はマスターサーバ１１０に接続されて、予め構成された間隔でトレースルートデータをマスターサーバ１１０へ送信することができる。
【００６０】
マスターサーバ１１０は、コレクタデバイス１２０ａによって提供されるトレースルートデータに基づいて、異なる予想を推測することができる。たとえば、第１の経路１４０ａ−１６０ａ−１６０ｂ−１６０ｃ−１４０ｂ−１６０ｄ−１６０ｅを通る、ターゲットデバイス１５０ａへのトレースルートデータの伝送については、コレクタデバイス１２０ａから受信されたデータに対して、異常を識別する予想が前述のように判断され得る。並行して、マスターサーバ１１０は、第２の経路１４０ａ−１６０ａ−１６０ｂ−１４０ｃ−１６０ｆ−１６０ｄ−１６０ｅを通る、ターゲットデバイス１５０ａへのトレースルートデータの伝送については、コレクタデバイス１２０ｂから受信されたデータに対して、異常はないと判断することができる。そのような場合、マスターサーバ１１０は、異常について、および、異常に機能していない第２の経路（すなわち、１４０ａ−１６０ａ−１６０ｂ−１４０ｃ−１６０ｆ−１６０ｄ−１６０ｅ）を介して情報をターゲットデバイス１５０ａへ伝送する可能性について、デバイス１５０ｘに警告することができる。場合によっては、たとえば追加の伝送情報の検討、第１の経路がうまくいかない際の第１および第２の経路の待ち時間の比較、第１の経路への伝送が経路内のある地点で到達不能であるとみなされたかどうかについての判断、および同様の条件の後で、代替経路が推薦される。
【００６１】
場合によっては、マスターサーバ１１０は、トレースルートデータに基づいて、異常を特定のリンクおよび／または地理的エリアまで絞り込むことができる。たとえば、第１の経路で異常が識別されたという条件で、第３の経路１６０ｃ−１６０ｂ−１６０ａ−１４０ａ−１５０ｙを通るコレクタデバイス１２０ｃとターゲットデバイス１５０ｙとの間で検出される異常がない場合、マスターサーバ１１０は、異常が、影響を受けたルートから１６０ａ―１６０ｂおよび１６０ｄ−１６０ｅを接続するリンクを除く、部分経路１６０ｃ−１４０ｂ−１６０ｄのどこかに存在すると推測することができる。この予想は、部分的に重複する経路を通して他のコレクタデバイスから受信されたトレースルートデータを分析することによって、再確認され、無視され、ならびに／もしくは、特定のリンクまたは地理的エリアまでさらに絞り込まれ得る。デバイス１２０から引き出された推測が矛盾しているかまたは合わない場合、マスターサーバ１１０は、トレースルートデータコレクタデバイス１２０によって受信されたデータにコヒーレンス値を割り当てることによって、推測を調和させてもよい。場合によっては、コヒーレンス値は、コレクタの各々に対応する信頼性重みの関数、および／または他の信頼性尺度であり得る。
【００６２】
パフォーマンス異常の検出
図８は、インターネットなどのコンピュータネットワークにおけるパフォーマンス異常を検出するための方法８００を示す。ステップ８０１で、プロセッサ（たとえばマスターサーバ１１０）は、コンピュータネットワーク上のコンピュータまたはルータなどのターゲットデバイスと、コンピュータネットワークにおける、またはコンピュータネットワークに結合された１つ以上のコレクタ（たとえばコレクタ１２０ａ）との間の伝送待ち時間を表わす、トレースルートデータまたはpingデータなどの待ち時間データを受信する。待ち時間データは、tr_base_fieldsデータ構造に関して上述されたフィールドを含むように各々編成され得る１つ以上のトレースルートデータパケットからの測定値を含み得る。たとえば、フィールドは、コンピュータネットワーク内の異なる宛先（ノード）への１つのホップまたは多くのホップに関連付けられた待ち時間を示してもよい。上述のように、別のターゲットに向かう途中で各ホップに遭遇するかもしれない。
【００６３】
待ち時間データはまた、所与のＩＰアドレスを直接ターゲットとし得る１つ以上のpingパケット（またはping）によって引き出された待ち時間測定値を含み得る。各pingパケットは、コンピュータネットワーク内の個々のコレクタと特定のターゲット宛先との間で収集される。各pingパケットは、ある瞬間に、コレクタと宛先との間の単一の往復時間（待ち時間）を測定する。
【００６４】
ステップ８０２で、待ち時間データは時間順ストリームへと編成されるかまたは配置され、各ストリームは、単一のコレクタと単一のターゲットデバイスとの間で観察されたサンプルのみを表わす。トレースルートデータの場合、これらのストリームは、トレースルート測定値を順序付け、分解することによって取得される。トレースルート測定値の各ホップ記録は、トレースルートを発生させたコレクタとホップＩＰアドレスとの間の新たな往復時間（待ち時間）測定値として理解され得る。pingデータの場合、これらのストリームは、コレクタとターゲットとの間の別個のping測定値を順序付け、照合するだけで取得される。
【００６５】
場合によっては、プロセッサは、コンピュータネットワーク内のターゲットデバイスの位置と、ターゲットデバイスへの、ターゲットデバイスからの、またはターゲットデバイスを通過するトラフィックの量とに基づいて、待ち時間収集パラメータを調節してもよい（８０４）。たとえば、プロセッサは、待ち時間データをバッファ（図６の最近のサンプルキュー６０１）に格納する前に、収集レートを減少させる（８０４ａ）か、または待ち時間データを間引いてもよい（８０４ｃ）。たとえば、プロセッサは、待ち時間における高周波変動をフィルタリングするために、および、バッファが現在の待ち時間状態およびベースライン待ち時間状態の意味のある推定を行なうのに十分な待ち時間データを保持することを保証するために、頻繁に通過されるルータとの行き来に関連付けられた待ち時間データを間引いてもよい。プロセッサはまた、待ち時間データを保持するために使用されるバッファ（最近のサンプルキュー６０１およびベースラインリザーバ６０２）のサイズを調節してもよい。典型的なターゲットについては、最近のサンプルキューは２５個のサンプルを保持し、ベースラインリザーバは１７５個のサンプルを保持する。これらの数は、ターゲットへの待ち時間がコレクタによって測定される頻度に依存して増減してもよい（なお、ステップ８０４は、図８に示すプロセスフロー内の異なる地点で行なわれ得る）。
【００６６】
プロセッサは、到着する待ち時間データを最近のサンプルキューに格納する（８０６）。プロセッサはまた、より古い待ち時間データを最近のサンプルキューからベースラインリザーバへ移動させる（８０８）。たとえば、プロセッサは、測定間隔ごとに、ベースラインリザーバにおける最も古い待ち時間サンプルを、最近のサンプルキューからの最も古い待ち時間サンプルと置換してもよい。これに代えて、プロセッサは、測定間隔ごとに１回、ベースラインリザーバにおけるランダムな待ち時間サンプルを、最近のサンプルキューからの待ち時間サンプルと置換してもよい。
【００６７】
プロセッサは、ベースラインリザーバにおける待ち時間サンプルからベースライン待ち時間状態を推定し（８１０）、最近のサンプルキューにおける待ち時間サンプルから現在の待ち時間状態を推定する（８１２）。それは、現在の待ち時間状態とベースライン待ち時間状態とを比較し（８１４）、比較が異常なネットワーク挙動を示す場合、異常の存在を識別する（８１６）。プロセッサはまた、たとえば経路変更、輻輳、接続性故障など、ならびに、ネットワークおよび／または特定の地理的エリア内のその位置といった、異常のタイプを識別しようとしてもよい（８１８）。たとえば、プロセッサは、異常に関連付けられた、および／または異常によって影響を受けた、１つ以上のＩＰアドレス、地理的領域、もしくは、ＩＰアドレスおよび地理的領域の双方を識別してもよい。
【００６８】
プロセッサは、現在の待ち時間状態およびベースライン待ち時間状態を推定し、任意の好適な比較手法を使用して比較してもよい。たとえば、プロセッサは、現在の待ち時間分布およびベースライン待ち時間分布を生成して正規化し、次に、正規化された分布同士を比較して、現在の待ち時間パフォーマンスがこれまでの待ち時間パフォーマンスに対して異常である確率を判断してもよい。プロセッサはまた、たとえば離散的待ち時間値の代表値および／または分布の分散度を含む１つ以上の記述統計８０５を計算してもよい。その後、マスターサーバ１１０は、現在の待ち時間値と予期される待ち時間値とのずれがネットワークパフォーマンス異常８０７に対応する確率を示す値を計算することができる。ずれが統計的に有意である場合、それは異常の徴候かもしれない。実際には、ｐ≦０．００００１が、単一のコレクタ／レスポンダ対が異常であると考えるのに十分である。これらのコレクタ／レスポンダ対は、混乱に遭遇しているネットワークまたは地理を見つけるためにクラスタ化され得る。
【００６９】
プロセッサはまた、異常のタイプ、影響を受けたエリアのＩＰアドレス、影響を受けた地理的位置、およびタイミング；以前に判断された応答ポリシー；ユーザからの命令などに基づいて、異常に応答してもよい（８２０）。たとえば、プロセッサは、異常警告を、異常のタイプ、位置、およびタイミングについての情報とともに、１人以上のユーザまたは他のデバイスに自動的に送信してもよい（８２０ａ）。これらのデバイスは、ＤＮＳサーバ、ルータ、負荷分散装置、ネットワーク最適化機器、および構成管理システムを含むものの、それらに限定されない。
【００７０】
たとえば、プロセッサは、コンピュータネットワークにおいて異常が存在するかどうかに部分的に依存してＤＮＳクエリを解決するＤＮＳサーバへ異常警告を送信してもよい。当業者には容易に理解されるように、ＤＮＳサーバとは、ドメイン名を、コンピュータネットワークを通してパケットをルーティングするために使用され得るＩＰアドレスへ変換するサーバである。ＤＮＳサーバは、権威あるＤＮＳサーバ、キャッシングＤＮＳサーバ、および転送ＤＮＳサーバを含む、さまざまなタイプで提供される。異常がない状況下では、ＤＮＳサーバは第１の予め定められたポリシーに従ってＤＮＳクエリを解決してもよく、当該ポリシーは、たとえば所望の待ち時間を達成し、負荷を分散し、コストを減少させ、特定のインターネット・サービス・プロバイダ（ＩＳＰ）を介したトラフィックのルーティングを避けるかまたは好むように設定されてもよい。ＤＮＳサーバは、プロセッサからの異常警告に応答して、ＤＮＳクエリに答えるための別の予め定められたポリシーに切り替えてもよい。場合によっては、ＤＮＳサーバは、異常の異なるタイプ、位置、および重症度について、異なるポリシーを有していてもよい。各ポリシーは、異常に応答して予め定められ、または設定され、または修正されてもよい。
【００７１】
別の表現で言うと、異常が、第１の予め定められたポリシーに従って特定のドメイン名についてのＤＮＳクエリを解決するＤＮＳサーバの能力に影響を与える場合、ＤＮＳサーバは、その特定のドメイン名についてのクエリを違ったやり方で扱う第２の予め定められたポリシーに切り替えてもよい。たとえば、ＤＮＳサーバが第１の予め定められたポリシーの下で所与のクエリに応答してトラフィックを第１のＩＰアドレスへ導き、異常がそのＩＰアドレスとの間のインターネットトラフィックに影響を与える場合、ＤＮＳサーバは、第２の予め定められたポリシーの下で同じクエリに応答してトラフィックを第２のＩＰアドレスへ導いてもよい。同様に、ＤＮＳサーバは、宛先の地理的位置、ＤＮＳクエリ送信元、および異常の影響を受けたエリアに基づいて、ならびに、対応するＩＰアドレス間でルーティングされるトラフィックに関連付けられた待ち時間に基づいて、トラフィックを導いてもよい。
【００７２】
プロセッサはまた、異常を勘案するルーティングポリシーを実施する（たとえば顧客サイトにある）構成可能ネットワークルータに異常警告を自動的に送信してもよい。ルータが（たとえば異なるＩＳＰを介した）インターネットへの利用可能な経路を複数有する場合、それは、予め定められたポリシー（負荷分散、最低コスト、または最高性能を含む）に基づいて、外部送信トラフィックを対応するインターフェイスを通して経路（ＩＳＰ）へ向けることができる。ポリシーはまた、１つ以上の異常の存在を、および異なるタイプの異常を勘案してもよい。その結果、所与のＩＳＰを介したトラフィックがより多い待ち時間または他の問題を経験する可能性があることを示す異常警告をルータが受信した場合、ルータは、異常が解決されるまで、代替ＩＳＰを介してトラフィックを送信してもよい。ルータがコレクタ１２０（図１）のうちの１つ以上とともに配置される場合、コレクタは、各ＩＳＰインターフェイスを通して同じターゲットをサンプリングし、異常を識別し、構成可能ネットワークルータ上のポリシーエンジンにプログラム提案を行なうことによって、各ＩＳＰインターフェイスを通してルータの観点からインターネットを見てもよい。
【００７３】
図９は、コンピュータネットワークにおける異常を検出するための別の方法９００を示す。ステップ９０２で、マスターサーバ１１０または他のプロセッサは、複数のコレクタから待ち時間データを収集する。この待ち時間データは、より詳細に上述されたように、各コレクタから、コンピュータネットワーク全体に分散された１つ以上の他のデバイスへのトレースルートパケットを含んでいてもよい。
【００７４】
ステップ９０４で、マスターサーバ１１０は、利用可能なデータに基づいて、コンピュータネットワークにおけるコレクタと各ターゲットとの間の伝送に関連付けられた待ち時間状態を判断する。待ち時間状態は、待ち時間分布を含むか表わしてもよく、図８のステップ８１０および８１２に関して上述された手法を使用して推定され得る。たとえば、マスターサーバ１１０は、現在の待ち時間状態によって表わされる待ち時間値の移動平均、中央値、または最頻値を計算してもよく、もしくは、現在の待ち時間状態によって表わされる待ち時間値の分布にピークを合わせてもよい。現在の待ち時間状態は、各コレクタ／ターゲット対間の最近のほぼリアルタイムの伝送状態を説明できる。マスターサーバ１１０は、あらゆる可能な組合せが計算されるまで、これらの計算を対ごとに、たとえば、各コレクタと第１のターゲット、第２のターゲット、などとの間で行なってもよい（場合によっては、データがない、または接続がないコレクタおよびターゲットについて待ち時間状態を推定することは、実用的または可能でないかもしれない）。
【００７５】
マスターサーバ１１０はまた、各コレクタ／ターゲット対について予期される待ち時間状態を判断する。ある場合では、マスターサーバ１１０は、図８のステップ８１０に関して上述されたように、これまでの待ち時間データから予期される待ち時間状態を計算してもよい。他の場合では、マスターサーバ１１０は、ユーザによって特定されたデータから予期される待ち時間状態を判断してもよい。すなわち、ユーザは所望の待ち時間または待ち時間状態を設定してもよく、マスターサーバ１１０は、ユーザによって供給されたこの情報を使用して、予期される待ち時間状態を判断してもよい。マスターサーバ１１０はまた、ユーザによって提供された情報に基づいて、予測される、または所望の待ち時間状態を生成してもよい。
【００７６】
ステップ９０８で、マスターサーバ１１０は、予期される待ち時間状態と現在の待ち時間状態とを比較する。比較の一環として、マスターサーバ１１０は、第１のしきい値より上の、または第２のしきい値より下の離散的待ち時間値を却下し、予期される待ち時間状態のカーネル密度推定値を構築し、および／または、現在の待ち時間状態のカーネル密度推定値を構築してもよい。比較は、ターゲットデバイスのうちの１つ以上との通信に影響を与えるネットワーク伝送異常の存在を推測する（ステップ９１０）のに十分な情報を提供することができる。そのような場合、マスターサーバ１１０は、たとえばＩＰアドレス、地理的位置、または他の識別子によって、異常の影響を受けたターゲットデバイスを識別してもよく（ステップ９１２）、コンピュータネットワークのうちの影響を受けていない部分を識別してもよい（ステップ９１４）。マスターサーバは、図８に関して上述したものと同様の警告メッセージを生成し、送信する（ステップ９１６）。この警告メッセージを受信するＤＮＳサーバ、ルータ、およびユーザは、異常についての情報を使用して、上述のように異常の有害な影響を緩和する態様でＤＮＳクエリを解決する、ＩＳＰを選択する、などしてもよい。
【００７７】
図１０は、コンピュータネットワーク（たとえば、図１に示すネットワーク１００）におけるパフォーマンス異常を検出するためのさらに別の方法１０００を示す。ステップ１００２で、コレクタはトレースルートデータパケットを受信し、トレースルートデータパケットにおいて符号化された待ち時間情報をマスターサーバ１１０へ提供する。ステップ１００４および１００６で、マスターサーバ１１０は、たとえば上述のようなこれまでの待ち時間情報および／またはユーザ入力を使用して、収集された待ち時間情報に基づいた実際の待ち時間状態と、予期される待ち時間状態とを判断する。
【００７８】
いくつかの実現化例では、マスターサーバ１００は、たとえば、パケットが特定の経路を所与の待ち時間で通過する確率を生成することによって、実際の待ち時間状態と予期される待ち時間状態とを比較する。それはこの確率を、コレクタデバイスに関連付けられた信頼性値、待ち時間データの質といった他の要因とともに使用して、パフォーマンスネットワーク異常予想を判断する（１００４ａ）。この予想は、ネットワークパフォーマンス異常のタイプに関して完全な推測を生成するのにともに十分である多くのまたは少なくとも２つの前例のうちの１つとして解釈され得る。マスターサーバ１１０は、他のコレクタから受信されたトレースルートデータに由来した予想間の不一致を調和させるために、コヒーレンス値を計算する（１００４ｂ）。コヒーレンス値が予め定められた異常しきい値より上である場合、マスターサーバ１１０は、ネットワークパフォーマンス異常を示す推測を生成することができる（１０１０）。マスターサーバ１１０は、異常のタイプを診断または分類する（１０１２ａ）ために、１つ以上の人工知能手法を使用してトレースルートデータを分析することによって異常に応答してもよい（ステップ１０１２）。それはまた、異常警告を送信し（１０１２ｂ）、異常に基づいてパケットをルーティングし（１０１２ｃ）、および／または、上述のように異常に基づいてＤＮＳクエリを解決してもよい（１０１２ｄ）。
【００７９】
パフォーマンス異常警告
場合によっては、マスターサーバは、異なるタイプの異常を検出し、マスターサーバのユーザインターフェイスディスプレイ２１２を通してグラフィック出力および／またはテキスト出力を提供することができる。図１１Ａ〜１１Ｄは、異なる記号が異なるコレクタによる測定値を表わす、警告システムによって検出された１組の現実世界異常を示す。図１１Ａ〜１１Ｃは異常な経路変更であるように見え、図１１Ｄは異常な輻輳事象であるように見える。
【００８０】
より具体的には、図１１Ａは、１組の３つの別個の（しかし地理的に近い）トレースルートコレクタから、イラクのスコープスカイ・コミュニケーション・アンド・インターネット社（ＡＳ５０５９７）によって制御されるＩＰアドレスのグループまで測定されるような、往復待ち時間のプロットである。このプロットは、典型的な双峰分布（およそ８０ｍｓおよび１３０ｍｓでピークを有する）と、劣化したより遅い単峰分布（１６０〜１７０ｍｓ前後で若干変化するピークを有する）との間の遷移を示す。
【００８１】
図１１Ｂは、（異なる色で表示された）１組の３つの同様のコレクタから、中国のパックネットによって制御される特定のネットワークプレフィックス（２２２．１２６．１２８．０／２３）におけるＩＰアドレスまで測定されるような、往復待ち時間のプロットである。このプロットは、各々およそ８０ｍｓずつ離れた（３１０ｍｓ、３９０ｍｓ、および４７０ｍｓでの）３つの別々のモードを示す。６月１３日に、上方のモードが低下し、最も速い結果から１０〜２０ｍｓしか離れていないため、パフォーマンスが向上する。
【００８２】
図１１Ｃは、（異なる色で表示された）１組の３つの同様のコレクタから、南アフリカのテネット（ＡＳ２０１８）によって制御されるアドレスまで測定されるような、往復待ち時間のプロットである。このプロットは、（大部分が）漸進的に向上する待ち時間を示しているが、４０ｍｓ速くなる際に独立したままである（およそ２０ｍｓ離れた）２つのモードがある。
【００８３】
図１１Ｄは、（異なる色で表示された）１組の３つの同様のコレクタから、ルーマニアのブカレストのＲＣＳ＆ＲＤＳによって制御される特定のネットワークプレフィックス（２１３．１５４．１００．０／２３）におけるＩＰアドレスまで測定されるような、往復待ち時間のプロットである。このプロットは、３つのコレクタすべてからのおよそ３５ｍｓの一貫した待ち時間を示す。６月１２日より、測定されたアドレスの部分母集団が日ごとの待ち時間増加を呈し始めた。６月１８日までに、部分母集団は、ベースラインから３００ｍｓもの日ごとの待ち時間変動を呈する。
【００８４】
マスターサーバ１１０は、トレースルートデータサンプルの観察から、情報伝送システムおよび／またはネットワーク１００の自動モデル化を可能にする１つ以上の人工知能手法によって、時間とともにトレースルートデータパターンを認識するように訓練され得る。人工知能手法は、タイミングを合わせた自動化、リアルタイム自動化、および同様の人工知能手法を含み得るものの、それらに限定されない。システム１００がいったんモデル化されると、マスターサーバ１１０は、異常のタイプを識別するために、トレースルートデータの分類子として動作することができる。マスターサーバ１１０によって識別され得る異常のうちのいくつかは、モード変更１１０２、モード統合１１０４、マルチモードシフト１１０６、悪化する日ごとの輻輳１１０８、および同様の異常を含み得る。さらに、マスターサーバはまた、異常の影響を受けた国１１１０、影響を受けた国の地域インターネットレジストリ１１１２、異常の影響を受けたＤＮＳ識別子１１１１、および／または、異常の影響を受けたＩＳＰ１１０９を判断することができる。
【００８５】
パフォーマンス異常警告
マスターサーバ１１０が、たとえば待ち時間データにおけるパターンの認識、または現在の待ち時間状態とベースライン待ち時間状態との比較によって、パフォーマンス異常を認識した場合、それは、図１２に示す警告メッセージ１２０１のような警告を生成し、発行してもよい。場合によっては、マスターサーバ１１０は、識別された異常について、１つ以上のクライアント１１４に警告することができる。異常警告は、警告の影響を受ける地理的エリアを示すことができる。たとえば、警告メッセージは、影響を受けた地理的エリアがワシントンＤ．Ｃ．北西部であることを示すことができる。地理的エリアに加えて、警告メッセージは、影響を受けた経路１２０５を示すことができる。この例において影響を受けた経路は、図７に示すデバイス（１４０ａ−１６０ａ−１６０ｂ−１６０ｃ−１４０ｂ−１６０ｄ−１６０ｅ）を含む。
【００８６】
さらに、警告メッセージは、影響を受けていない地理的エリア１００３、たとえば、ワシントンＤ．Ｃ．南西部を示すことができる。場合によっては、警告メッセージは、提案された代替経路を含んでいてもよい。たとえば、代替経路は、図７に示すデバイス１４０ａ−１６０ａ−１６０ｂ−１４０ｃ−１６０ｆ−１６０ｄ−１６０ｅを含み得る。提案された代替経路を通してデータパケットを伝送するための推定時間を示す、代替経路に対応する推定された待ち時間伝送時間１００７を、警告メッセージにおいて提供することができる。
【００８７】
結論
この発明のさまざまな実施形態をここに説明し図示してきたが、当業者であれば、ここに説明された機能を行なうための、および／または結果、および／または利点のうちの１つ以上を得るためのさまざまな他の手段および／または構造を容易に構想するであろう。そのような変更および／または修正の各々は、ここに説明されたこの発明の実施形態の範囲内にあると考えられる。より一般的には、当業者であれば、ここに説明されたすべてのパラメータ、寸法、材料、および構成は例示的であるよう意図されていること、ならびに、実際のパラメータ、寸法、材料、および／または構成は、この発明の教示が使用される特定の用途に依存することを容易に理解するであろう。当業者であれば、ここに説明されたこの発明の特定の実施形態との多くの同等物を認識し、または単なる定型実験を使用して確かめることができるであろう。したがって、前述の実施形態は例としてのみ提示されること、ならびに、添付された請求項およびそれとの同等物の範囲内で、この発明の実施形態が、具体的に記載され請求されたもの以外の態様で実践され得ることが理解されるべきである。本開示の発明の実施形態は、ここに説明された各個々の特徴、システム、物品、材料、キット、および／または方法に向けられる。加えて、２つ以上のそのような特徴、システム、物品、材料、キット、および／または方法の任意の組合せは、そのような特徴、システム、物品、材料、キット、および／または方法が互いに矛盾しない場合、本開示の発明の範囲内に含まれる。
【００８８】
この発明の上述の実施形態は、多くの方法のうちのいずれかで実現され得る。たとえば、いくつかの実施形態は、ハードウェア、ソフトウェア、またはそれらの組合せを使用して実現されてもよい。実施形態の任意の局面がソフトウェアで少なくとも部分的に実現される場合、単一のコンピュータに提供されるか複数のコンピュータ中に分散されるかにかかわらず、ソフトウェアコードが任意の好適なプロセッサまたはプロセッサの集合上で実行され得る。
【００８９】
この点において、この発明のさまざまな局面は、１つ以上のコンピュータまたは他のプロセッサ上で実行されると上述の技術のさまざまな実施形態を実現する方法を行なう１つ以上のプログラムで符号化された、コンピュータ読取可能記憶媒体（または複数のコンピュータ読取可能記憶媒体）（たとえば、コンピュータメモリ、１つ以上のフロッピー（登録商標）ディスク、コンパクトディスク、光ディスク、磁気テープ、フラッシュメモリ、フィールドプログラマブルゲートアレイまたは他の半導体装置における回路構成、もしくは他の有形のコンピュータ記憶媒体または非一時的な媒体）として少なくとも部分的に具現化されてもよい。コンピュータ読取可能媒体は、その上に格納されたプログラムが上述のような本技術のさまざまな局面を実現するように１つ以上の異なるコンピュータまたは他のプロセッサにロードされ得るように、可搬型であってもよい。
【００９０】
「プログラム」、「ソフトウェア」という用語は、上述のような本技術のさまざまな局面を実現するようにコンピュータまたは他のプロセッサをプログラムするために採用され得る任意のタイプのコンピュータコードまたは１組のコンピュータ実行可能命令を指すために、一般的な意味でここに使用される。加えて、この実施形態の１つの局面によれば、実行されると本技術の方法を行なう１つ以上のコンピュータプログラムは、本技術のさまざまな局面を実現するために、単一のコンピュータまたはプロセッサ上に存在する必要はなく、多くの異なるコンピュータまたはプロセッサ中にモジュール方式で分散されてもよい、ということが理解されるべきである。
【００９１】
コンピュータ実行可能命令は、１つ以上のコンピュータまたは他のデバイスによって実行されるプログラムモジュールといった、多くの形態を取ってもよい。一般に、プログラムモジュールは、特定のタスクを行なう、または特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。典型的には、プログラムモジュールの機能性は、さまざまな実施形態において所望されるように組合され、または分散されてもよい。
【００９２】
また、ここに説明された技術は、方法として具現化されてもよく、その少なくとも１つの例が提供されてきた。方法の一環として行なわれる行為は、任意の好適なやり方で順序付けられてもよい。したがって、例示されたものとは異なる順序で行為が行なわれる実施形態が構築されてもよく、例示された実施形態では順次の行為として示されたものであっても、それはいくつかの行為を同時に行なうことを含んでいてもよい。
【００９３】
ここに定義され使用されたようなすべての定義は、辞書の定義、引用により援用される文献における定義、および／または定義された用語の通常の意味を統括していると理解されるべきである。
【００９４】
明細書および請求項においてここに使用されるような不定冠詞「ａ」および「ａｎ」は、そうでないことが明らかに示されない限り、「少なくとも１つ」を意味すると理解されるべきである。
【００９５】
明細書および請求項においてここに使用されるような「および／または」という句は、そのように結合された要素、すなわち、ある場合には結合的に存在し、他の場合には分離的に存在する要素の「いずれかまたは双方」を意味すると理解されるべきである。「および／または」を用いて列挙された複数の要素は同じ態様で、すなわち、そのように結合された要素のうちの「１つ以上」と解釈されるべきである。「および／または」という句によって具体的に識別された要素以外に、他の要素が、それらの具体的に識別された要素に関連していようとなかろうと、オプションで存在してもよい。このため、非限定的な例として、「Ａおよび／またはＢ」への言及は、「…を備える」などのオープンエンドの文言とともに使用される場合、ある実施形態ではＡのみ（オプションでＢ以外の要素を含む）；別の実施形態ではＢのみ（オプションでＡ以外の要素を含む）；さらに別の実施形態ではＡとＢの双方（オプションで他の要素を含む）；などを指すことができる。
【００９６】
明細書および請求項においてここに使用されるように、「または」は、上で定義されたような「および／または」と同じ意味を有すると理解されるべきである。たとえば、リストにおける項目を分ける場合、「または」あるいは「および／または」は、包括的であると解釈されるものとする。すなわち、多くの要素またはリストの要素のうちの少なくとも１つ（しかしながら２つ以上も含む）、およびオプションでリストにない追加の項目を含むと解釈されるものとする。「…のうちの１つのみ」あるいは「…のうちのまさしく１つ」、もしくは請求項で使用される場合には「…からなる」といった、そうでないことが明らかに示された用語だけが、多くの要素またはリストの要素のうちのまさしく１つの要素を含むことを指すであろう。一般に、ここに使用されるような「または」という用語は、「いずれか」、「…のうちの１つ」、「…のうちの１つのみ」あるいは「…のうちのまさしく１つ」といった排他性の用語が後続する場合、単に排他的な代替物を示すと解釈されるものとする（すなわち「一方または他方、しかしながら双方でない」）。「本質的に…からなる」は、請求項で使用される場合、特許法の分野で使用されるようなその通常の意味を有するものとする。
【００９７】
明細書および請求項においてここに使用されるように、１つ以上の要素のリストに関する「少なくとも１つ」という句は、要素のリストにおける要素のいずれか１つ以上から選択されるものの、要素のリスト内に具体的に列挙されたすべての各要素のうちの少なくとも１つを必ずしも含まず、要素のリストにおける要素のいかなる組合せも除外しない、少なくとも１つの要素を意味すると理解されるべきである。この定義はまた、「少なくとも１つ」という句が指す要素のリスト内で具体的に識別された要素以外に、要素が、それらの具体的に識別された要素に関連していようとなかろうと、オプションで存在してもよい、ということを可能にする。このため、非限定的な例として、「ＡおよびＢのうちの少なくとも１つ」（あるいは同等に「ＡまたはＢのうちの少なくとも１つ」、あるいは同等に「Ａおよび／またはＢのうちの少なくとも１つ」）は、ある実施形態では、Ａが少なくとも１つ（オプションで２つ以上を含む）、Ｂは存在せず（およびオプションでＢ以外の要素を含む）；別の実施形態では、Ｂが少なくとも１つ（オプションで２つ以上を含む）、Ａは存在せず（およびオプションでＡ以外の要素を含む）；さらに別の実施形態では、Ａが少なくとも１つ（オプションで２つ以上を含む）、およびＢが少なくとも１つ（オプションで２つ以上を含む）（およびオプションで他の要素を含む）；などを指すことができる。
【００９８】
上述の明細書だけでなく、請求項においても、「…を備える」、「…を含む」、「…を搬送する」、「…を有する」、「…を含有する」「…を伴う」、「…を保持する」、「…から構成された」などといった移行句はすべて、オープンエンドである、すなわち、「…を含むもののそれらに限定されない」という意味であると理解されるべきである。米国特許庁特許審査便覧のセクション２１１１．０３に規定されるように、「…からなる」および「本質的に…からなる」という移行句のみが、それぞれクローズドまたはセミクローズドの移行句であるものとする。
【図１】
2018521611.tif 000006
【図２】
2018521611.tif 000007
【図３】
2018521611.tif 000008
【図４】
2018521611.tif 000009
【図５Ａ】
2018521611.tif 000010
【図５Ｂ】
2018521611.tif 000011
【図５Ｃ】
2018521611.tif 000012
【図５Ｄ】
2018521611.tif 000013
【図６Ａ】
2018521611.tif 000014
【図６Ｂ】
2018521611.tif 000015
【図６Ｃ】
2018521611.tif 000016
【図７】
2018521611.tif 000017
【図８】
2018521611.tif 000018
【図９】
2018521611.tif 000019
【図１０】
2018521611.tif 000020
【図１１Ａ】
2018521611.tif 000021
【図１１Ｂ】
2018521611.tif 000022
【図１１Ｃ】
2018521611.tif 000023
【図１１Ｄ】
2018521611.tif 000024
【図１２】
2018521611.tif 000025
【国際調査報告】
2018521611.tif 000026
2018521611.tif 000027
2018521611.tif 000028