(57)【要約】本発明は、孤立した異常の検出に関し、大規模な異常が発生する場合に異常管理システムがオーバーロードする結果とならずに、ユーザ介入に依存しない自動的なやり方で動作する。
2015529036.tif 000002
【特許請求の範囲】
【請求項１】
サービスをレンダリングするデータ処理デバイスにおいて孤立した異常検出を行う方法であって、前記方法は、前記データ処理装置によって実装され、
前記データ処理デバイスによってレンダリングされた少なくとも１つのサービスのサービス品質に応じてソース品質バケットに前記データ処理デバイスを挿入する第１の挿入ステップ（６１）であって、品質バケットは前記少なくとも１つのサービスに関するサービス品質の予め定められた範囲を有するデータ処理デバイスのグループを表す、第１の挿入ステップと、
前記データ処理デバイスによってレンダリングされた前記サービス品質が前記第１の品質バケットの前記予め定められた範囲を超えて展開する場合、宛先品質バケットに前記データ処理デバイスを挿入する第２の挿入ステップ（６３）と、
ソース品質バケットが前記データ処理デバイスの前記品質バケットと同一である前記宛先品質バケットにおけるデータ処理デバイスの総数を表すカウンタが閾値（６４）を下回るとき、孤立した異常検出を表すメッセージを送信するステップ（６５）と、
を含む、前記方法。
【請求項２】
前記方法は、前記ソースバケット上及び前記第２の挿入ステップのタイムスタンプ上で動作されるハッシュ関数に従って前記カウンタを格納することを担当する前記宛先品質バケットにおけるデータ処理デバイスのアドレスを判定するステップであって、前記タイムスタンプは、前記データ処理デバイス間で共有された共有クロックから得られるタイムスロットを表す、ステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記データ処理デバイスは、品質バケットに関するエントリポイントを表すルートデータ処理デバイスを備えるデータ処理デバイスのネットワークにおいて組織化され、前記第２の挿入ステップは、その宛先品質バケットの宛先ルートデータ処理デバイスのアドレスを得るためのそのソース品質バケットの第１のルートデータ処理デバイスに第１の要求を送信するステップをさらに含む、請求項１又は２に記載の方法。
【請求項４】
前記方法は、前記宛先品質バケットに前記データ処理デバイスを挿入するためのその宛先品質バケットの前記宛先ルートデータ処理デバイスに第２の要求を送信するステップをさらに含む、請求項３に記載の方法。
【請求項５】
前記データ処理デバイスのネットワークは、２つのレベルのオーバーレイ構造に従って組織化され、前記オーバーレイ構造は、前記ルートデータ処理デバイス間のネットワーク接続を組織化する１つの上部オーバーレイと、同一の品質バケットのデータ処理デバイス間のネットワーク接続を組織化する多数の底部オーバーレイとを備える、請求項３又は４に記載の方法。
【請求項６】
前記データ処理デバイスによってレンダリングされる前記サービスは、データストレージサービスである、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記データ処理デバイスによってレンダリングされる前記サービスは、音響映像レンダリングサービスである、請求項１乃至５のいずれかに記載の方法。
【請求項８】
サービスをレンダリングするデータ処理デバイスのための孤立した異常検出配置であって、
前記データ処理デバイスによってレンダリングされた少なくとも１つのサービスのサービス品質に応じてソース品質バケットに前記データ処理デバイスを挿入する第１の挿入手段であって、品質バケットは前記少なくとも１つのサービスに関するサービス品質の予め定められた範囲を有するデータ処理デバイスのグループを表す、第１の挿入ステップと、
前記データ処理デバイスによってレンダリングされた前記サービス品質が前記第１の品質バケットの前記予め定められた範囲を超えて展開する場合、宛先品質バケットに前記データ処理デバイスを挿入する第２の挿入手段と、
ソース品質バケットが前記データ処理デバイスの前記品質バケットと同一である前記宛先品質バケットにおけるデータ処理デバイスの総数を表すカウンタが閾値を下回るとき、孤立した異常検出を表すメッセージを送信する手段と、
を備えた、前記配置。
【請求項９】
前記ソースバケット上及び前記第２の挿入のタイムスタンプ上で動作されるハッシュ関数に従って前記カウンタを格納することを担当する前記宛先品質バケットにおけるデータ処理デバイスのアドレスを判定する手段であって、前記タイムスタンプは、前記データ処理デバイス間で共有された共有クロックから得られるタイムスロットを表す、手段をさらに備えた、請求項８に記載の配置。
【請求項１０】
前記データ処理デバイスは、品質バケットに関するエントリポイントを表すルートデータ処理デバイスを備えるデータ処理デバイスのネットワークにおいて組織化され、前記第２の挿入は、その宛先品質バケットの宛先ルートデータ処理デバイスのアドレスを得るためのそのソース品質バケットの第１のルートデータ処理デバイスに第１の要求を送信する手段をさらに備えた、請求項８又は９に記載の配置。
【請求項１１】
前記宛先品質バケットに前記データ処理デバイスを挿入するためのその宛先品質バケットの前記宛先ルートデータ処理デバイスに第２の要求を送信する手段をさらに含む、請求項１０に記載の配置。
【請求項１２】
前記データ処理デバイスのネットワークは、２つのレベルのオーバーレイ構造に従って組織化され、前記オーバーレイ構造は、前記ルートデータ処理デバイス間のネットワーク接続を組織化する１つの上部オーバーレイと、同一の品質バケットのデータ処理デバイス間のネットワーク接続を組織化する多数の底部オーバーレイとを備える、請求項１０又は１１に記載の配置。
【請求項１３】
前記データ処理デバイスによってレンダリングされる前記サービスは、データストレージサービスである、請求項８乃至１２のいずれかに記載の配置。
【請求項１４】
前記データ処理デバイスによってレンダリングされる前記サービスは、音響映像レンダリングサービスである、請求項８乃至１２のいずれかに記載の配置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、多くの（例えば、何千、何百万もの）デバイス処理データがデータ処理サービスに提供される大規模データ処理システムに関する。具体的には、本発明の技術分野は、このような大規模データ処理システムにおいて孤立した異常の検出に関する。
【背景技術】
【０００２】
本発明のコンテキストにおける大規模データ処理システムの例は、テレビ、インターネット、およびテレフォニーサービスが何百万もの加入者に提供されるトリプルプレイオーディオビジュアルサービス提供システムである（ここでは、オーディオビジュアルサービスの受信およびレンダリングがデータ処理である）。大規模データ処理システムの別の例は、何千ものストレージノードがストレージサービスを提供する（分散）データストレージシステムである（ここでは、ストレージサービスのレンダリングがデータ処理である）。オペレータの何百万ものクライアントによって享受されるトリプルプレイサービスのサービス品質（ＱｏＳ）における異常を検出するために、または分散データストレージシステムにおけるストレージデバイスの機能時の異常を検出するために、異常検出システムの一部である集中型エラー検出サーバは、データ処理デバイスをモニタする。ここでは、孤立した異常の検出が問題である。これは、異常管理システムが、そのシステムに接続されている何百万ものデータ処理デバイスが原因で、異常管理システムによってデータ処理デバイスから異常管理システムに個々のメッセージ送信が可能となる時に発生する可能性があるオーバーロードをそのシステム自体で防がなければならない理由による。例えば、通信パスが何らかの理由でダウンすると、この通信パスを介して少なくとも部分的に（トリプルプレイの例として）用いられるか又は（分散データストレージの例として）相互通信する何千または何百万ものデータ処理デバイスは、（トリプルプレイの例として）ＱｏＳ（サービス品質）の突然の低下、又は（分散ストレージの例として）接続の突然の喪失を経験し、エラーメッセージを異常管理システムに大量に送信するであろう。異常管理システムは、その後、非常に短い時間期間で到着する大量のメッセージに対処することができないであろう。これらの大規模データ処理システムのために、オペレータは、従って、個々のデバイスに関する可能性を制限してエラーメッセージを異常管理システムに送信する傾向がある。遠隔管理技術はＴＲ−０６９又はＳＮＭＰ（Simple network management protocol）などである。これらのプロトコルは、サーバ・クライアント指向であり、すなわちサーバが複数のデータ処理デバイスを遠隔管理する。本質により、この中央遠隔管理アーキテクチャは、単一のサーバがそのような大規模なデバイスセットを効果的に監視できないときに、何百万ものデータ処理デバイスにスケーリング（scale）しない。従来技術によると、異なる監視アーキテクチャは、従って、これらのデータ処理デバイスが正しく機能し続けることかどうかを検証するために、監視システムがサービス分散ネットワークトポロジーの分散パスにおけるいくつかのデータ処理デバイスを頻繁に監視する場所を設置する。明らかに、異常管理システムのオーバーロードに対するこの保護バリアは、如何なる細粒異常検出も不可能にする。次に、個別基準の異常検出は不可能になる。
【０００３】
異常が発生した時、その異常は、非常に多くのデータ処理デバイスが同一の異常を経験することになる場合におけるネットワーク関連問題によるか、又は局所的問題によるかのいずれかになる場合があり、単一のデータ処理デバイス又は非常に制限された数のデータ処理デバイスに影響を与えるだけである。トリプルプレイサービス提供システムである大規模データ処理システムの第１の例をとると、ＱｏＳの孤立した低下を経験するサービスユーザのために、サービスオペレータは論理的に、多くのデータ処理デバイスに影響を与える異常の検出を優先する傾向があるにもかかわらず、これは非常に満足のいかない状況である。そのユーザは、サービスオペレータに連絡をとろうとする他には選択肢がない。これは、時間がかかり且つ面倒であり、ユーザはしばしばサービスオペレータのコールセンタに話さなければならない。トラブルが起こったユーザがコールセンタの電話オペレータとついに連絡をとると、コールセンタの電話オペレータはユーザに初期設定に戻すことやデバイス再起動などの異なる操作を試みることを指示するだろう。複数の試行の後にユーザのサービス受信が未だエラーである場合、最後の手段としてメンテナンス技術者がユーザの建物に現れることができる。そのような手続は、ユーザにとって非常にイライラするものであり、生じた問題を解決することを補助することになる動作を彼自身が取らなければならない。サービスオペレータは不満足なユーザを十分に理解しない。個々の問題が技術的な観点から些細なものと考えられるにもかかわらず、個々の問題は大規模な次元を有する。サービスオペレータのクライアント又は潜在的クライアントである他の個人の不満足な経験を伝えることが人間性であるため、不満足でイライラがたまったユーザはオペレータの評価を駄目にする。大規模データ処理システムの第２の例を分散データストレージシステムとすると、ストレージ「ノード」またはデバイスは、ストレージ媒体の不具合、電力サージ、ＣＰＵサーチャージによって引き起こされるローカル問題に遭遇する可能性がある。これは、ストレージ「ノード」もしくはデバイスの性能、または言い換えれば、ストレージ「ノード」またはデバイスが配信するサービスのサービス品質（ＱｏＳ）を低下させる。ストレージデバイスによって配信されるサービスは、ストレージサービスである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
大規模データ処理システムでは、従って、大規模な異常が発生する場合に異常管理システムがオーバーロードする結果とならずに、ユーザ介入に依存しない自動的なやり方で動作する、孤立した異常の検出のためのより良いソリューションが必要である。
【課題を解決するための手段】
【０００５】
本発明は、従来技術のいくつかの不都合を軽減することを目的とする。
【０００６】
本発明は、サービスをレンダリングするデータ処理デバイスにおいて孤立した異常検出を行う方法であって、前記データ処理デバイスによってレンダリングされた少なくとも１つのサービスのサービス品質に応じてソース品質バケットに前記データ処理デバイスを挿入する第１の挿入するステップであって、前記データ処理装置によって実装され、品質バケットは前記少なくとも１つのサービスに関するサービス品質の予め定められた範囲を有するデータ処理デバイスのグループを表す、第１の挿入ステップと、前記データ処理デバイスによってレンダリングされた前記サービス品質が前記第１の品質バケットの前記予め定められた範囲を超えて展開する場合、宛先品質バケットに前記データ処理デバイスを挿入する第２の挿入ステップと、ソース品質バケットが前記データ処理デバイスの前記品質バケットと同一である前記宛先品質バケットにおけるデータ処理デバイスの総数を表すカウンタが閾値を下回るとき、孤立した異常検出を表すメッセージを送信するステップと、を含む、前記方法を提供することを目的とする。
【０００７】
本発明の方法の特定の実施形態によると、前記方法は、前記ソースバケット上及び前記第２の挿入ステップのタイムスタンプ上で動作されるハッシュ関数に従って前記カウンタを格納することを担当する前記宛先品質バケットにおけるデータ処理デバイスのアドレスを判定するステップであって、前記タイムスタンプは、前記データ処理デバイス間で共有された共有クロックから得られるタイムスロットを表す、ステップをさらに含む。
【０００８】
本発明の方法の特定の実施形態によると、前記データ処理デバイスは、品質バケットに関するエントリポイントを表すルートデータ処理デバイスを備えるデータ処理デバイスのネットワークにおいて組織化され、前記第２の挿入ステップは、その宛先品質バケットの宛先ルートデータ処理デバイスのアドレスを得るためのそのソース品質バケットの第１のルートデータ処理デバイスに第１の要求を送信するステップをさらに含む。
【０００９】
本発明の方法の特定の実施形態によると、前記方法は、前記宛先品質バケットに前記データ処理デバイスを挿入するためのその宛先品質バケットの前記宛先ルートデータ処理デバイスに第２の要求を送信するステップをさらに含む。
【００１０】
本発明の方法の特定の実施形態によると、前記データ処理デバイスのネットワークは、２つのレベルのオーバーレイ構造に従って組織化され、前記オーバーレイ構造は、前記ルートデータ処理デバイス間のネットワーク接続を組織化する１つの上部オーバーレイと、同一の品質バケットのデータ処理デバイス間のネットワーク接続を組織化する多数の底部オーバーレイとを備える。
【００１１】
本発明の方法の特定の実施形態によると、前記データ処理デバイスによってレンダリングされる前記サービスは、データストレージサービスである。
【００１２】
本発明の方法の特定の実施形態によると、前記データ処理デバイスによってレンダリングされる前記サービスは、音響映像レンダリングサービスである。
【００１３】
本発明はまた、サービスをレンダリングするデータ処理デバイスのための孤立した異常検出配置であって、前記データ処理デバイスによってレンダリングされた少なくとも１つのサービスのサービス品質に応じてソース品質バケットに前記データ処理デバイスを挿入する第１の挿入手段であって、品質バケットは前記少なくとも１つのサービスに関するサービス品質の予め定められた範囲を有するデータ処理デバイスのグループを表す、第１の挿入ステップと、前記データ処理デバイスによってレンダリングされた前記サービス品質が前記第１の品質バケットの前記予め定められた範囲を超えて展開する場合、宛先品質バケットに前記データ処理デバイスを挿入する第２の挿入手段と、ソース品質バケットが前記データ処理デバイスの前記品質バケットと同一である前記宛先品質バケットにおけるデータ処理デバイスの総数を表すカウンタが閾値を下回るとき、孤立した異常検出を表すメッセージを送信する手段と、を備えた、前記配置に関する。
【００１４】
本発明の配置の特定の実施形態によると、前記ソースバケット上及び前記第２の挿入のタイムスタンプ上で動作されるハッシュ関数に従って前記カウンタを格納することを担当する前記宛先品質バケットにおけるデータ処理デバイスのアドレスを判定する手段であって、前記タイムスタンプは、前記データ処理デバイス間で共有された共有クロックから得られるタイムスロットを表す、手段をさらに備える。
【００１５】
本発明の配置の特定の実施形態によると、前記データ処理デバイスは、品質バケットに関するエントリポイントを表すルートデータ処理デバイスを備えるデータ処理デバイスのネットワークにおいて組織化され、前記第２の挿入は、その宛先品質バケットの宛先ルートデータ処理デバイスのアドレスを得るためのそのソース品質バケットの第１のルートデータ処理デバイスに第１の要求を送信する手段をさらに備える。
【００１６】
本発明の配置の特定の実施形態によると、前記宛先品質バケットに前記データ処理デバイスを挿入するためのその宛先品質バケットの前記宛先ルートデータ処理デバイスに第２の要求を送信する手段をさらに含む。
【００１７】
本発明の配置の特定の実施形態によると、前記データ処理デバイスのネットワークは、２つのレベルのオーバーレイ構造に従って組織化され、前記オーバーレイ構造は、前記ルートデータ処理デバイス間のネットワーク接続を組織化する１つの上部オーバーレイと、同一の品質バケットのデータ処理デバイス間のネットワーク接続を組織化する多数の底部オーバーレイとを備える。
【００１８】
本発明の配置の特定の実施形態によると、前記データ処理デバイスによってレンダリングされる前記サービスは、データストレージサービスである。
【００１９】
本発明の配置の特定の実施形態によると、前記データ処理デバイスによってレンダリングされる前記サービスは、音響映像レンダリングサービスである。
【図面の簡単な説明】
【００２０】
本発明のより多くの利点は、本発明の特定の、限定されない実施形態の説明を通じて現れる。
【００２１】
本実施形態は、以下の図面を参照して説明される。
【図１】大規模データ処理システムの例示的なネットワークトポロジーを示し、および孤立した異常が検出されるか否かの異なる事例を例示する図である。
【図２】本発明の方法を例示する図である。
【図３】２つのサービスのサービス品質をモニタするために本発明において使用することができる２次元上部オーバーレイ構造の例を例示する図である。
【図４】提供されたソリューションのスケーラビリティを拡大するために本発明において使用することができる構造であって、ノードまたはデータ処理デバイスがある品質バケットから別の品質バケットに移動する時に効率的にナビゲートすることを可能にする構造である、上部オーバーレイ構造と底部オーバーレイ構造との間の階層を例示する図である。
【図５】本発明の方法を実装するシステムにおいて使用することができる配置およびデバイスを示す図である。
【図６】フローチャートの形式において特定の実施形態による本発明の方法を図示した図である。
【発明を実施するための形態】
【００２２】
本明細書において、用語「異常検出」は、「エラー検出」よりもむしろ使用される。これは、意図的に行われる。実際には、異常は、ＱｏＳにおける「非正常的(abnormal)」変更と見なされる。このような異常は、肯定的（より良いＱｏＳ）または否定的（より悪いＱｏＳ）のいずれかとすることができ、従って、「エラー」またはエラーでないかが区別されなければならない。異常モニタリングの目的で、エラー検出に加えて、ノードが、例えば、トラブルシューティングの目的で、より良いＱｏＳを有することを検出することも興味深い。
【００２３】
データ処理システムでは、異常管理システムに対する通信複雑度がスケーラビリティの鍵である。本明細書の先行技術の項において論じたように、大規模データ処理システムにおいて微細な異常検出は、グループ化された異常検出のためにトレードオフされる。なぜならば、異常モニタリングシステムは、多数のデバイスからの異常メッセージを同時に処理することができないからである。本発明は、従って、何千あるいはさらに何百万ものデバイスが１または複数のデータ処理サービスを提供する大規模データ処理システムにおいて使用するために特によくスケーリングする孤立した異常検出のソリューションを定義する。スケーラビリティに関する本発明の重要な特徴は、デバイスが、それらのデバイスが提供するデータ処理サービスのＱｏＳにおける著しい劣化、または反対に、著しい改善に遭遇する際の異常の検出の後、アラームによる報知を最小限にする能力である。現在の発明の目的は、ＱｏＳの劣化／改善がデバイス、またはデバイスの限定されたセットに特有なものであると評価される事例に対するアラーム報告を減らすことである。このため、本発明は、大規模または超大規模を含む、任意の規模のデータ処理システムに適している異常検出の自己組織化方法を提案する。
【００２４】
図１は、大規模データ処理システムの例示的なネットワークトポロジーを示し、および孤立した異常が検出されるか否かの異なる事例を図示している。１つのみのサービス（例えば、１つのテレビ受信サービス）がデータ処理システムノード（以下「ノード」とする）によりモニタされる場合、可能なＱｏＳは、「品質バケット」を有するラインとして表すことができ、多数の事前定義された（ここでは１０個）品質バケットは、ＱｏＳを０（最小品質）から１（最大品質）までに分類して表される。参照番号１０は、このような分類を２つのノード、Ａ（１００）とＢ（１０１）として表す。参照番号１２−１５は、ノードのＱｏＳの展開の異なるシナリオを表す。開始において、参照番号１０によれば、ノードＡとＢは、全く同じＱｏＳを有していないが、同じ品質バケット内である。ｔ＋１（参照番号１１）において、ＱｏＳの異なる変更は（後に論じられるようなｘ＋ｄ）、これらのノードのうちの少なくとも１つとして発生する。シナリオ１２によれば、ノードＡは、ノードＡがノードＢと同じＱｏＳを有するようにＱｏＳのわずかな変更を経験する。しかしながら、その変更は、ノードＡを別の品質バケットに変更させるのに十分ではない。その変更は、バケット境界の内側に留まり、さらなるアクションが起こされない。即ち、何の異常も検出されない。しかしながら、シナリオ１３から１５までによれば、ノードＡは、ノードＡが別の品質バケットに展開するのに十分なＱｏＳの変更を経験する。しかしながら、本発明によれば、異常を検出する条件のうちの１つは、展開が十分に重要でなければならないことであり、その条件は、シナリオ１４および１５の事例が当てはまり、シナリオ１３は当てはまらない。シナリオ１３によれば、従って何の異常も検出されない。シナリオ１４および１５では、展開は十分に重要であるが、孤立した異常は該当するノードの展開が孤立した事例の場合にのみ検出されなければならない。あるいは、多数のノードが同じ展開を経験するのであれば、その展開は孤立しておらず、むしろネットワークにおいて発生する変更が原因か、または例えばバグの多いソフトウェアの更新のような大量のシステムエラーが原因である。その場合、十分なデバイスは、同じ異常を経験していると仮定することができるので、ネットワークオペレータが他の手段を用いて問題にアクセスすることができ、我々がここで説明する微細な機構は必要ない。シナリオ１４によれば、ノードＡの展開は、ノードＢが同じ展開に遭遇した理由により孤立した事例ではない。シナリオ１４では、所定の数より多い（ここでは、例のように２個）ノードが同じ展開に遭遇したので、異常が孤立していると見なされない理由により、従って何の異常も検出されない。しかしながら、シナリオ１５によれば、ノードＡのみがＱｏＳの十分に重要な展開に遭遇した。従って、異常が検出される。「十分に重要」という概念は、特定の実施形態により、事前定義された閾値として実装され、図２を用いて提供される説明を見られたい。変形実施形態によれば、Ｈｏｌｔ−Ｗｉｎｔｅｒｓ予想方法が使用される。Ｈｏｌｔ−Ｗｉｎｔｅｒｓ方法が使用される場合、ＱｏＳの最終値ｋのリストは、１ノードごとに記憶される。このリストを使用して、次の値が予測される。実際の値が予測された値から大きく離れている場合、異常が検出される。さらに別の変形実施形態によれば、Ｃｕｓｕｍ（累積和）方法が使用される。Ｈｏｌｔ−Ｗｉｎｔｅｒｓと同様に、最終のＱｏＳ値ｋのリストが１ノードごとに記憶されるが、Ｈｏｌｔ−Ｗｉｎｔｅｒｓがこのリストを使用して次の値を予測する場合、Ｃｕｓｕｍは、これらの値の傾向を検出して、傾向がすでに論じたノードＡと同様のＱｏＳの値を有する事前定義された数のＱｏＳ値があることを示していれば、異常が検出されるようにする。Ｃｕｓｕｍは、傾向に基づき、一方、Ｈｏｌｔ−Ｗｉｎｔｅｒｓは、定時(punctual)の変更を検出する。これらは、オペレータの希望に従って定義することができる、例示的な変形実施形態である。
【００２５】
図２は、本発明の方法の特定の実施形態を図示している。ノードがその品質バケットから離れて（２１）、ｔ（または後に論じられるようなｘ）におけるＱｏＳとｔ＋１（またはｘ＋ｄ）におけるＱｏＳとの間の距離の展開が所定の閾値よりも上回る（２２）場合、および所定の数よりも少ないノードが同じ展開に遭遇した（２３）場合に異常が検出される（２４）。あるいは、テストステップ２１と２２は、ＱｏＳ変更が所定の閾値よりも上回る場合、単一の判定のテストステップに統合される。
【００２６】
デジタルデータ処理技術は、データ処理がもはや不可能である閾値の遭遇に対して特殊性を有する。テレビ技術の類推において、アナログＴＶ受信機のユーザは、大量のノイズを含むアナログ信号からなおもテレビ番組を見続けることができるであろうが、デジタルＴＶの受信機は、デジタル信号のノイズの量が重要であれば、画像をレンダリングする能力がなく、デジタル信号の受信がもはや不可能である閾値以下が存在する。このような要因は、ＱｏＳの展開が重要であるか否かを判定して異常を検出する時に考慮に入れることができる。例えば、ＱｏＳの展開が０．６から０．４までであれば、たとえ０．４のＱｏＳであっても受信機が、デジタル信号を読み取る時に発生するエラーを（例えば、エラー修正方法のアプリケーションを介して）修正する能力がなおもある理由により受容可能であり、０．４から０．３までの展開は、受信機が、ＱｏＳが０．４以下のデジタル信号を利用する能力がもはやない理由により受容不可能であろう。この知識はさらに、品質バケットの分散を定義するために使用することもできる。上記の例によれば、単一の品質バケットは、ＱｏＳ範囲が０から０．４までに対して、別の単一の品質バケットは、ＱｏＳ範囲が０．４から０．６までに対して定義することができる。品質バケットの分散は、従って、必ずしも規則的ではない。変形実施形態によれば、方法は、従って、付加的ＯＲ条件が付加されるように適応される。ノードがその品質バケットから離れて、ｔ（若しくはｘ）におけるＱｏＳとｔ＋１（若しくはｘ＋ｄ）におけるＱｏＳとの間の距離の展開が所定の閾値よりも上回るか、または所定の閾値以下であるＱｏＳの値を表す品質バケットに展開する場合、および所定の数よりも少ないノードが同じ展開に遭遇した場合に異常が検出される。所定の閾値は、エラーがない受信がもはや不可能である値以下、または受信がもはや不可能である値以下に設定することができる。
【００２７】
図１の例によれば、１つのみのサービスがモニタされる。実際には、２以上のサービス（例えば、２以上のテレビ受信サービス、テレビ受信サービスおよびテレフォニーサービス）をモニタすることができる。結果的に情報の損失になるであろう、複数のサービスのモニタリングを（例えば、平均を計算するための平均関数を使用して）共通の結果にコンパイルすることよりも、現在の発明は、多次元品質バケットを用いて機能できるようにさせる。方法の演算の原理は、変更されない一方、Ｄ次元の品質バケットは、複数の（Ｄ）サービスのモニタリングを単に要求するだけである。
【００２８】
データ処理システムの集中型異常検出サーバのオーバーロードを回避するために、本発明によるデータ処理デバイスまたはノードは、それら自体をモニタし、ローカルには、それらのＱｏＳをモニタする。ノードは、ノード自体で、同様のＱｏＳを有するノードのグループに組織化する。ノードが品質バケットを変更させるＱｏＳの変更を観察して、その変更が十分に重要であると判定されれば、ノードは、そのノードの現在のＱｏＳグループから別のＱｏＳグループに変更する。異常が孤立しているか否かを確認するために、ノードは、「新しい」ＱｏＳグループ内の他のノードに他のノードの以前のＱｏＳでコンタクトする。同じＱｏＳを有していた新しいＱｏＳグループのノードの数が所定の閾値以下であれば、そのノードは、そのノードが遭遇した異常がノードにローカルである、即ち、孤立していると見なすことができ、その時初めてそのノードは、アラームメッセージを集中型異常検出サーバに送信する。アラームメッセージの送信まで、集中型異常検出サーバは、従って、コンタクトされず、孤立した異常によりメッセージ送信のオーバーロードがない。さらに、異常検出は、ユーザ介入が無く、自動的に機能する。
【００２９】
上記で示されているように、本発明の方法によれば、ノードは、集中型コントローラまたはサーバの介入無しで、１つのノードにおいて発生する異常が孤立しているか否かを判断するために協働する。有利な実施形態によれば、ノードは、ピアツーピア（Ｐ２Ｐ）方式で組織化される。Ｐ２Ｐネットワークトポロジーは、ノードが互いのアドレスを見つけて、互いに通信するために集中型コントローラまたはサーバのサービスを使用せずに、互いの間で直接通信することができるような、通信ボトルネックを削減する利点を付加する。これは、本発明のスケーラブルな特徴にさらに付加される。このＰ２Ｐネットワークトポロジーに対して、本発明は、２つのタイプのオーバーレイを付加する。ノード間のグローバル通信を可能にさせる、１つの上部レベルのオーバーレイ（ノードがＤ多次元空間に配置される）と、１または多数の底部オーバーレイであるが、同様のＱｏＳを有するノードへの接続を担当する底部オーバーレイは、１品質バケット当たり多くても１つである。
【００３０】
言及してきたように、品質バケットを変更するノードは、別の品質バケットに移動していることになり、その後、その移動が孤立した事例であるかどうかを判定するために、どのくらいの数の他のノードも同じ移動を行ったかを判定しなければならず、孤立した場合、アラームが報知される。ノードは、従って、どのノードグループ（宛先グループ）にノード自体を挿入しなければならないかについての情報を取得するために周囲のノードと通信しなければならず、その後、どのくらいの数の他のノードも同じ移動を行ったかを知るために、宛先グループ内のあるロケーション（ノード）に問い合わせる。これは、一部の組織化を必要とする。直接的な実施形態は、各ノードがコンタクトすることができ、そして必要な情報を集める集中型サーバである。しかしながら、このようなソリューションは、大規模データ処理システムにとってあまりスケーラブルでない。より良いソリューションは、一部のノードが、ノードを他のノードのセットにリンクする役割を果たすオーバーレイアーキテクチャを使用することである。ノードが集中型サーバの使用を必要とせずにノードアドレスを容易に見つけるために、ＤＨＴ（分散ハッシュテーブル:Distributed Hash Table）が使用される。ＤＨＴは、ハッシュテーブルと同様の検索サービスを提供する非集中型分散システムのクラスであり、（キー、値）ペアは、ＤＨＴに格納され、そして任意の参加ノードは、所与のキーと関連付けられた値を効率的に読み出すことができる。キーから値へのマッピングを維持する責任は、参加者のセットの変更が必要最低限量の中断を引き起こすようなやり方で、ノードに分散される。これによって、ＤＨＴが極めて多数のノードをスケーリングして、連続的なノードの到着および出発を処理することが可能となる。このようなＤＨＴは、参加するノードに分散されるやり方で、基本的なＰＵＴ演算およびＧＥＴ演算を提供し、それぞれ、アイテムの格納およびアイテムの読出しを行う。ＤＨＴを使用する本発明の特定の実施形態によれば、分散されたハッシュテーブルは、ＰＵＴおよびＧＥＴ演算を提供する基本インタフェースをエクスポートして、（キー、値）ペアがシステムに参加しているノードにマップできるようにさせる。ノードは、その後、ＰＵＴ演算を用いて値をＤＨＴに挿入し、そしてキーと関連付けられたＧＥＴを使用して値を読み出すことができる。キーは、ＤＨＴのアドレス空間上でランダムアドレスを取得するために、オブジェクトのコンテンツ（またはネーム）をハッシュすることによって取得される。ノード自体は、キーがＤＨＴのキーの位置に基づいて（同じ空間のキーのＩＤに応じて）ＤＨＴのアドレス空間のキーのサブセットの範囲内である、オブジェクトを格納する責任を負う。
【００３１】
ノードが大規模データ処理システムにおいて効率的に通信できるようにさせる本発明による特に効率的なオーバーレイアーキテクチャは、言及した２レベルのＰ２Ｐネットワークトポロジー、即ち、１または多数の「底部」と、ちょうど１つの「上部」のオーバーレイ構造を使用する。底部オーバーレイレイヤにおける特定のオーバーレイ構造は、近いＱｏＳ値を有するノードがスケーラブルなやり方で近くに接続されるようにさせて、通信がすべてのノードに伝搬されないように、各ノードは、そのノードの所与のグループ内の他のノードのサブセットのみを知っている。本発明の特定の実施形態によれば、底部オーバーレイは、ハイパーキューブとして実装される。変形実施形態によれば、底部オーバーレイは、ＣｈｏｒｄまたはＰａｓｔｒｙを用いるようなＰｌａｘｔｏｎツリー実装として実装される。上部オーバーレイは、ノードグループ間の高速通信を可能にさせる。上部オーバーレイにおいて、ノードは、ノードのＱｏＳ値に従ってノード自体を品質バケットに自己組織化する。底部オーバーレイを使用して、各ノードが他のすべてのノードに通信することを回避する。底部オーバーレイにおいて、ノードは、ＱｏＳ値とは独立にノード自体で自己組織化する。１品質バケット当たり１つのオーバーレイがあり、品質バケットは、上部オーバーレイ経由で相互接続され、底部オーバーレイは、ハイパーキューブ、Ｐｌａｘｔｏｎツリー、またはその他である。底部オーバーレイでは、サービスバケットが同じ品質であるノードがハッシュ関数に基づいて互いのアドレスを見つけ、そして多数のノードを介して渡されることなく効率的に通信できるようにさせる古典的ＤＨＴ機能が使用される。しかしながら、効率的な「標準の」ＤＨＴは、底部オーバーレイを構築するためのものであり、上部レベルのオーバーレイでは、ＤＨＴの特定のバージョンが本発明の目的により適している。Ｄ次元メトリックを処理できるようにするために、本発明の方法は、Ｄサービスを同時にモニタすることができる。「標準の」ＤＨＴと、上部オーバーレイに使用される本発明による特定のＤＨＴ変形との間の主な違いは、「標準の」ＤＨＴに従って、ハッシュ値がオーバーレイの位置に関連付けられることである。しかし、ハッシング演算は、ノードを空間に均一に分散する結果となり、これは、ノードがそのノードのＱｏＳに従って空間に分散されることを要求する情報を損失する結果となるであろう。本発明によれば、ノードは、従って、それらのノードのそれぞれのＱｏＳ値に関して近いノードに相互接続される。システムは、その後、上部レベルのオーバーレイのノードの近接を考慮する時、オリジナルＱｏＳ分散に配慮する。例えば、ノードが別の品質バケットに移動しなければならない時点で変更するノードのＱｏＳ値をノードが観察する時、ノードは、ノードにモニタされたサービスのＤ値に従ってルーティングされるメッセージを送信する。このメッセージは、最終的には、このＤ値の座標が属する品質バケットに届き、その後、そのノードは、その距離にあるノードとメッセージが最後に到着する新しい品質バケットのノードとインタラクトすることによってオーバーレイにおいてそのノードの過去の（ソース）位置からこの新しい（宛先）位置への移動を実行できるようになる。
【００３２】
上部オーバーレイは、従って、ノードグループ間の効率的で短いパスナビゲーション（「ルーティング」）を可能にし、これは、ノードが品質バケットを変更する時に望ましく、従って、正確な新しい品質バケットにルーティングしなければならず、そこでノードがそのノードの新しいＱｏＳに近い値を有するノードのグループ（即ち、底部オーバーレイ）を見つける。従って、上部オーバーレイにおいて、言及したように、ノードは、そのノードのハッシュ値に従う代わりにそのノードの品質バケットに従って組織化される。図３および図４によって、このような異なる概念をより良く理解することができる。図３は、Ｄモニタサービス（図３および図４においてＤ＝２）に対応するＤ次元空間を処理する、ＣＡＮのようなＤＨＴ（コンテンツアドレス可能ネットワーク(Content Addressable Network)）を表す。ＣＡＮは、インターネットのような規模でハッシュテーブルの機能性を提供する分散、非集中型Ｐ２Ｐインフラストラクチャである。
【００３３】
２次元上部オーバーレイ構造（Ｄ＝２）の例は、図３によって図示される。Ｄは、ＱｏＳを確立するためにモニタされる予定のサービスの数である。水平方向に、サービスｘのＱｏＳ（参照番号３５）があり、垂直方向に、サービスｙのＱｏＳ（３４）がある。Ｄ次元空間は、品質バケットに分割される。品質バケットは、ＱｏＳの固有の範囲を用いて品質バケットをグループ化するセル（ここでは、１から４までのセル、参照番号３０−３３）にグループ化される。各セルは、多くても１つのシード（ここでは、黒い品質バケット３８）を有する。ノード（黒い点、参照番号３９）は、それらのノードのＱｏＳに従ってグリッド内に配置される。シード（３８）は、所定の閾値以上であるいくつかのノード（品質バケット内の個々のノードを図示した、３９）を包含する品質バケットである。この閾値は、異常が孤立しているか否かを判定するために説明された本発明の特定の実施形態において使用されるすでに論じた所定の閾値と関係ない。
【００３４】
図４は、上部オーバーレイ４０と、１または多数の底部オーバーレイ４１（ここでは、限定されない例として４つの底部オーバーレイが図示されている）との間の階層を図示している。上部オーバーレイにおいて、ノードは、グリッド内のそれらのノードの座標に従って品質バケットに組織化される。底部オーバーレイにおいて、同じまたは同様のサービス品質を有するノードのグループは、ＤＨＴによって組織化される。説明を明確にするために、４つの底部レベルのオーバーレイのそれぞれに対して単純なツリー構造が描かれている。上部オーバーレイと底部オーバーレイとの間のリンクは、底部オーバーレイと上部オーバーレイとの間のブリッジ(bridge)である「ルート（root）」ノードで示しているライン４３によって表され、ルートノードは、品質バケットの底部オーバーレイへのエントリポイントを表す。
【００３５】
ノードが品質バケットを変更する時、即ち、ノードが別の品質バケットに「移動する」時、ノードは、ＤＨＴを使用して、そのノードの底部オーバーレイにおいてルートノード（参照番号４２）の検索を行う。（「移動する」ノードは、例えば、ＤＨＴのＩＤ０の責任を負うＤＨＴノードにルーティングすることができる。変形実施形態によれば、ロードバランシング機構が使用される）。ルートノード（４２）が見つかったので、移動するノードは、上部オーバーレイの検索演算を経てそのノードの宛先品質バケットの品質バケット座標に従って、上部オーバーレイのルートノードのアドレスを見つけるようにルートノードに要求する。移動するノードは、その後、ルートノードを、宛先底部オーバーレイのトポロジーに挿入されるブートストラップノードとして使用する。ひとたび宛先底部オーバーレイに挿入されると、新しく加入したノードは、古典的ＤＨＴプリミティブを介して目的底部オーバーレイのノードと通信することができる。警告メッセージをセントラルサーバに送信するか否かを判定するために、新しく加入したノードは、同じ移動を行ったノードの数を知る必要がある。そうするために、移動するノードは、そのノードの底部オーバーレイにおいて同じ移動を行ったノードの数のカウンタを増加する。このカウンタを使用して、同じ品質バケット（ソースバケット）から来て現在の品質バケット（宛先バケット）に入るノードの数をほぼ同じ時間にカウントする。ノードは、共通のタイムクロックｔを共有し、それによって所定の期間ｄを有する共通のクロックから導出されたタイムスロットを定義するタイムスタンプが生成される。ここで、ｄは、本発明を実装するデータ処理システムに対して定義されるパラメータである。タイムスロットｘにおける品質バケットの変更を判定したノードは、このカウンタの値である、時間ｘ＋ｄ（ｘ＋ｄは、次のタイムスロットを意味する）においてチェックする。カウンタが所定の閾値以下または未満であれば、警告が報知される。そうでなければ、ノードは、サイレント状態のままである。共通のタイムラインは、例えば、ノード間で共有される共通のクロックによって共有されることができ、タイムスロットの所定の期間は、後で論じられるハッシュ演算hash(previous_location:time_of_move_relative_to_time_slot)を計算するのに重要である、オペレーションが１タイムスロットごとのタイムラインで同期されることを保証する。
【００３６】
各底部オーバーレイのカウンタのロケーション（即ち、カウンタ値のホスティングを担当する特定のノード）は、移動するノードの以前のロケーションと、移動するノードが移動する時の時間（例えば、事前定義されたタイムスロット期間ｄを数分と見なす）とのＤＨＴハッシングによって判定されるように定義される。言い換えれば、文字ハッシュ(previous_location:time_of_move_relative_to_time_slot)の演算は、判定性値(deterministic value)、即ち、所与のＤＨＴのカウンタのロケーションを一意に特定するために移動するノードによって使用される、タイムスタンプを提供する。このようにして、新しいロケーションは、底部オーバーレイの構成要素となるノードにわたってロードバランシングを提供する、各底部オーバーレイにおける移動タイムスロットの過去のロケーション／タイムスタンプの各一対に対して定義される。
【００３７】
図５は、本発明の方法を実装するシステムにおいて使用することができるデバイス５００を示す。デバイスは、デジタルデータおよびアドレスバス５０によって相互接続された以下のコンポーネント、
−処理ユニット５３（または中央処理装置であるＣＰＵ）と、
−メモリ５５と、
−接続５１を介してネットワークに接続される他のデバイスに対するデバイス５００の相互接続のためのネットワークインタフェース５４と、
を備える。
【００３８】
処理ユニット５３は、マイクロプロセッサ、カスタムチップ、専用（マイクロ）コントローラなどとして実装することができる。メモリ５５は、ＲＡＭ（Random Access Memory）、ハードディスクドライブ、不揮発性ランダムアクセスメモリ、ＥＰＲＯＭ（Erasable Programmable ROM）などのような、任意の形式の揮発性および／または不揮発性メモリに実装することができる。デバイス５００は、本発明の方法によるデータ処理デバイスを実装するのに適している。データ処理デバイス５００は、データ処理デバイスによって提供される少なくとも１つのサービスに関連する同一の第１のサービス品質値を有するデータ処理デバイスの第１のグループに挿入するための手段（５３、５４）と、データ処理デバイスのサービス品質値が所定の閾値を超えている第２のサービス品質値に展開するかどうかを判定するためのサービス品質展開判定手段（５２）と、同一のサービス品質を有するデータ処理デバイスの第２のグループに挿入するための手段（５３、５４）と、データ処理デバイスの第２のグループが第１の値と等しい以前のサービス品質値を有していた多数のデータ処理デバイスを含むかどうか、及びその数が所定の値以下であるかどうかを判定するための計算手段（５３）と、孤立した異常検出を示すメッセージを送信するための手段（５４）とを有する。
【００３９】
特定の実施形態によれば、本発明は、例えば、専用コンポーネントのような（例えば、ＡＳＩＣ、ＦＰＧＡまたはＶＬＳＩのような）（それぞれ、≪Application Specific Integrated Circuit≫、≪Field-Programmable Gate Array≫および≪Very Large Scale Integration≫）ハードウェアに完全に実装されるか、または別の変形実施形態によれば、デバイスに統合される別個の電子コンポーネントとしてまたは、さらに別の実施形態によれば、ハードウェアとソフトウェアを組み合わせた形式において完全に実装される。
【００４０】
図６は、フローチャートの形式において特定の実施形態による本発明の方法を図示している。初期化する第１のステップ６０において、本発明の実行に必要である変数は、メモリ、例えば、デバイス５００のメモリ５５において初期化される。次のステップ６１において、デバイスは、データ処理デバイスによってレンダリングされる少なくとも１つのサービス品質に応じてデバイス自体を品質バケット（「ソース」品質バケット）に挿入する。品質バケットは、少なくとも１つのサービスに関するサービス品質の事前定義された範囲を有するデータ処理デバイスのグループを表す。言い換えれば、デバイスは、データ処理デバイスによってレンダリングされる少なくとも１つのサービス品質を含むサービス品質の範囲を有する品質バケットにデバイス自体を挿入する。品質バケットへの「挿入」は、デバイスが品質バケットを表すグループのメンバになることを意味する。特定の実施形態によれば、このような挿入は、デバイスを表す識別子を、品質バケットを表すデバイスのグループのリストに付加することによって行われる。変形実施形態によれば、挿入は、品質バケットを表すデバイスのセットへのネットワーク接続を作ることによって行われ、その品質バケットは、品質バケット内にあるデバイス間のネットワーク接続によって特徴付けられる。判定ステップ６２において、データ処理デバイスによってレンダリングされるサービス品質が、挿入された（メンバである）品質バケットの事前定義された範囲を超えて展開するかどうかが判定される。これは、その品質バケットの範囲に含まれていた所与の瞬時でのサービス品質と、後の瞬時でのサービス品質との間で、後者がその品質バケットの範囲内にもはや入らない、即ち、ＱｏＳの展開が品質バケットの変更、即ち、「ソース」から「宛先」品質バケットに変更する結果となるのに十分重要であることを意味する。デバイスは、従って、データ処理デバイスによってレンダリングされるサービス品質が第１の品質バケットの事前定義された範囲を超えて展開した場合、データ処理デバイスを宛先品質バケットに挿入する第２の挿入するステップ（６３）において別の品質バケットに挿入されることになる。その後、品質バケットの変更が孤立した事例であったかどうかがステップ６４において判定される。このために、ソース品質バケットがデータ処理デバイスの品質バケットと同一である宛先品質バケットにおけるデータ処理デバイスの総数が所定の値以下であることをカウンタが表しているかどうかが判定される。そうである場合、孤立した異常が検出され、デバイスは、孤立した異常検出の発生を表すメッセージを送信／送出する。特定の実施形態によれば、メッセージは、デバイスの識別子を含む。変形実施形態によれば、メッセージは、オペレータがデバイスに異常の理由を問い合わせることなく介入することができるように、異常検出の理由を含む。
【図１】
2015529036.tif 000003
【図２】
2015529036.tif 000004
【図３】
2015529036.tif 000005
【図４】
2015529036.tif 000006
【図５】
2015529036.tif 000007
【図６】
2015529036.tif 000008
【国際調査報告】
2015529036.tif 000009
2015529036.tif 000010