(57)【要約】  コンピュータネットワーク障害の発生源を検出するための、コンピュータ記憶媒体上に符号化されたコンピュータプログラムを含む、方法、システム、および装置。方法のうちの1つは、送信元と宛先との間のコンピュータネットワーク内のネットワークフローを識別するステップと、送信元と宛先との間にエンドツーエンド接続性があるかどうかを判定するための第1のプローブを実行するステップと、送信元と宛先との間にエンドツーエンド接続性がないとの判定に応答して、送信元がネットワークフローのパスにおける各ホップにそれぞれの第1のトレース診断パケットを伝送することを要求することを含む、送信元と宛先との間のネットワークフローのパスにおける各ホップが動作可能であるかどうかを判定するための第2のプローブを含む、1つまたは複数の追加のプローブを実行するステップと、結果に基づいて、ネットワークフローのパスの一部であるコンピュータネットワークの少なくとも1つのリンクが障害を起こしたかどうかを判定するステップとを含む。
2021502788.tif 000002
【特許請求の範囲】
【請求項１】
送信元と宛先との間のコンピュータネットワーク内のネットワークフローを識別するステップと、
前記送信元が前記宛先にエンドツーエンド診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間にエンドツーエンド接続性があるかどうかを判定するための第1のプローブを実行するステップであって、前記エンドツーエンド診断パケットが、前記コンピュータネットワーク内の1つまたは複数のネットワークデバイスに、前記ネットワークフローのパス上で前記エンドツーエンド診断パケットを転送させる情報を含む、ステップと、
前記送信元と前記宛先との間にエンドツーエンド接続性がないとの判定に応答して、前記送信元が前記ネットワークフローの前記パスにおける各ホップにそれぞれの第1のトレース診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間の前記ネットワークフローの前記パスにおける各ホップが動作可能であるかどうかを判定するための第2のプローブを含む1つまたは複数の追加のプローブを実行するステップであって、各トレース診断パケットが、それぞれのホップに、前記送信元に対して前記第1のトレース診断パケットに応答する第1のトレース応答パケットを送信させる情報を有する、ステップと、
前記第1のプローブおよび前記1つまたは複数の追加のプローブの結果に基づいて、前記ネットワークフローの前記パスの一部である前記コンピュータネットワークの少なくとも1つのリンクが障害を起こしたかどうかを判定するステップと
を含む、方法。
【請求項２】
前記1つまたは複数の追加のプローブを実行するステップが、前記宛先が前記宛先と前記送信元との間のパスにおける各ホップにそれぞれの第2のトレース診断パケットを伝送することを要求することを含む、前記宛先と前記送信元との間の前記パスにおける各ホップが動作可能であるかどうかを判定するための第3のプローブを実行するステップであって、各トレース診断パケットが、前記それぞれのホップに、前記送信元に対して前記第2のトレース診断パケットに応答する第2のトレース応答パケットを送信させる情報を有する、ステップを含む、請求項1に記載の方法。
【請求項３】
それぞれのホストに関連付けられた前記第2のトレース診断パケットが、前記ホップに前記第2のトレース診断パケットに応答して、前記ホストに時間超過メッセージを送信させる、前記第2のトレース診断パケットの有効期限フィールドにおける特定の値を有する、請求項2に記載の方法。
【請求項４】
前記エンドツーエンド診断パケットが、前記送信元の識別子および前記宛先の識別子をそれぞれ含む、送信元識別子フィールドおよび宛先識別子フィールドを有する、請求項1に記載の方法。
【請求項５】
前記エンドツーエンド診断パケットが、前記エンドツーエンド診断パケットが診断パケットであることを示すために、1つまたは複数の特定のフィールドにおいて指定された値を有する、請求項1に記載の方法。
【請求項６】
前記診断パケットがトランスポート制御プロトコルパケットであり、前記指定された値がフラグフィールドのためのゼロ値を備える、請求項5に記載の方法。
【請求項７】
それぞれのホップに関連付けられた前記第1のトレース診断パケットが、前記ホップに前記第1のトレース診断パケットに応答して、前記送信元に時間超過メッセージを送信させる、前記第1のトレース診断パケットの有効期限フィールドにおける特定の値を有する、請求項1に記載の方法。
【請求項８】
前記第1のプローブを実行するステップが、
前記送信元が前記エンドツーエンド診断パケットに応答するエンドツーエンド応答パケットを受信したかどうかを判定するステップと、
前記送信元が前記エンドツーエンド応答パケットを受信したとの判定に応答して、前記送信元と前記宛先との間にエンドツーエンド接続性があると判定するステップと、
前記送信元が前記エンドツーエンド応答パケットを受信していないとの判定に応答して、前記送信元と前記宛先との間にエンドツーエンド接続性がないと判定するステップと
をさらに含む、請求項1に記載の方法。
【請求項９】
前記送信元が特定のホップから前記第1のトレース応答パケットを受信したかどうかを判定するステップと、
前記送信元が特定のホップから前記第1のトレース応答パケットを受信したとの判定に応答して、前記特定のホップが動作可能であると判定するステップと、
前記送信元が特定のホップから前記第1のトレース応答パケットを受信していないとの判定に応答して、前記特定のホップが動作可能ではないと判定するステップと
をさらに含む、請求項1に記載の方法。
【請求項１０】
前記ネットワークフローを識別するステップが、
前記コンピュータネットワーク内の1つまたは複数のホストから再伝送情報を取得するステップと、
1つまたは複数のネットワークフローを検出するために、前記再伝送情報を解析するステップと、
前記1つまたは複数のネットワークフローの各ネットワークフローについて、前記再伝送情報から再伝送カウントを決定するステップと、
再伝送カウントがしきい値を超える前記1つまたは複数のネットワークフローのグループを識別するステップと、
前記グループから前記ネットワークフローを選択するステップと
を含む、請求項1に記載の方法。
【請求項１１】
前記ネットワークフローを識別するステップが、
前記グループ内の各ネットワークフローについて、前記ネットワークフローの宛先が障害を起こしたかどうかを検出するステップと
対応する宛先が障害を起こしたいかなるネットワークフローも除外するために、前記グループを更新するステップと
をさらに含む、請求項4に記載の方法。
【請求項１２】
前記第1のプローブ、前記第2のプローブ、および前記第3のプローブの結果を含むプローブ結果情報を生成するステップと、
前記ネットワーク内の各リンクについての訪問カウントおよび障害カウントを決定するために前記プローブ結果を解析するステップであって、対応するリンクについての前記訪問カウントが、パケットが前記リンクに移動した回数を示し、対応するリンクについての前記障害カウントが、前記リンクが障害の兆候を示した回数を示す、ステップと、
前記コンピュータネットワークのグラフを生成するステップであって、前記グラフが、前記コンピュータネットワーク内のそれぞれのリンクに各々対応するエッジと、前記エッジに対応する前記リンクについての前記訪問カウントおよび前記障害カウントのうちの少なくとも1つに基づいて決定される各エッジのための重みとを含む、ステップと
をさらに含む、請求項1に記載の方法。
【請求項１３】
障害を起こした可能性が高い、前記コンピュータネットワーク内の少なくとも1つのリンクを検出するために前記グラフを解析するステップをさらに含む、請求項6に記載の方法。
【請求項１４】
コンピュータネットワーク内の1つまたは複数のホストから再伝送情報を取得するステップと、
1つまたは複数のネットワークフローを検出するために、前記再伝送情報を解析するステップと、
前記1つまたは複数のネットワークフローの各ネットワークフローについて、前記再伝送情報から再伝送カウントを決定するステップと、
再伝送カウントがしきい値を超える前記1つまたは複数のネットワークフローのグループを識別するステップと、
前記識別されたグループについての1つまたは複数のネットワーク診断結論を生成するステップと
を含む、方法。
【請求項１５】
システムであって、
1つまたは複数のコンピュータと、命令が記憶された1つまたは複数の記憶デバイスとを備え、前記命令が、前記1つまたは複数のコンピュータによって実行されると、前記1つまたは複数のコンピュータに、
送信元と宛先との間のコンピュータネットワーク内のネットワークフローを識別することと、
前記送信元が前記宛先にエンドツーエンド診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間にエンドツーエンド接続性があるかどうかを判定するための第1のプローブを実行することであって、前記エンドツーエンド診断パケットが、前記コンピュータネットワーク内の1つまたは複数のネットワークデバイスに、前記ネットワークフローのパス上で前記エンドツーエンド診断パケットを転送させる情報を含む、実行することと、
前記送信元と前記宛先との間にエンドツーエンド接続性がないとの判定に応答して、前記送信元が前記ネットワークフローの前記パスにおける各ホップにそれぞれの第1のトレース診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間の前記ネットワークフローの前記パスにおける各ホップが動作可能であるかどうかを判定するための第2のプローブを含む1つまたは複数の追加のプローブを実行することであって、各トレース診断パケットが、それぞれのホップに前記送信元に対して前記第1のトレース診断パケットに応答する第1のトレース応答パケットを送信させる情報を有する、実行することと、
前記第1のプローブおよび前記1つまたは複数の追加のプローブの結果に基づいて、前記ネットワークフローの前記パスの一部である前記コンピュータネットワークの少なくとも1つのリンクが障害を起こしたかどうかを判定することと
を含む動作を実行させるように動作可能である、システム。
【請求項１６】
前記1つまたは複数の追加のプローブを実行することが、前記宛先が前記宛先と前記送信元との間のパスにおける各ホップにそれぞれの第2のトレース診断パケットを伝送することを要求することを含む、前記宛先と前記送信元との間の前記パスにおける各ホップが動作可能であるかどうかを判定するための第3のプローブを実行することであって、各トレース診断パケットが、前記それぞれのホップに前記送信元に対して前記第2のトレース診断パケットに応答する第2のトレース応答パケットを送信させる情報を有する、第3のプローブを実行することを含む、請求項15に記載のシステム。
【請求項１７】
それぞれのホストに関連付けられた前記第2のトレース診断パケットが、前記ホップに前記第2のトレース診断パケットに応答して、前記ホストに時間超過メッセージを送信させる、前記第2のトレース診断パケットの有効期限フィールドにおける特定の値を有する、請求項16に記載のシステム。
【請求項１８】
それぞれのホップに関連付けられた前記第1のトレース診断パケットが、前記ホップに前記第1のトレース診断パケットに応答して、前記送信元に時間超過メッセージを送信させる、前記第1のトレース診断パケットの有効期限フィールドにおける特定の値を有する、請求項15に記載のシステム。
【請求項１９】
前記第1のプローブを実行することが、
前記送信元が前記エンドツーエンド診断パケットに応答するエンドツーエンド応答パケットを受信したかどうかを判定することと、
前記送信元が前記エンドツーエンド応答パケットを受信したとの判定に応答して、前記送信元と前記宛先との間にエンドツーエンド接続性があると判定することと、
前記送信元が前記エンドツーエンド応答パケットを受信していないとの判定に応答して、前記送信元と前記宛先との間にエンドツーエンド接続性がないと判定することと
をさらに含む、請求項15に記載のシステム。
【請求項２０】
命令とともに符号化された1つまたは複数のコンピュータ可読記憶媒体であって、前記命令が、1つまたは複数のコンピュータによって実行されると、前記1つまたは複数のコンピュータに、
送信元と宛先との間のコンピュータネットワーク内のネットワークフローを識別することと、
前記送信元が前記宛先にエンドツーエンド診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間にエンドツーエンド接続性があるかどうかを判定するための第1のプローブを実行することであって、前記エンドツーエンド診断パケットが、前記コンピュータネットワーク内の1つまたは複数のネットワークデバイスに、前記ネットワークフローのパス上で前記エンドツーエンド診断パケットを転送させる情報を含む、実行することと、
前記送信元と前記宛先との間にエンドツーエンド接続性がないとの判定に応答して、前記送信元が前記ネットワークフローの前記パスにおける各ホップにそれぞれの第1のトレース診断パケットを伝送することを要求することを含む、前記送信元と前記宛先との間の前記ネットワークフローの前記パスにおける各ホップが動作可能であるかどうかを判定するための第2のプローブを含む1つまたは複数の追加のプローブを実行することであって、各トレース診断パケットが、それぞれのホップに前記送信元に対して前記第1のトレース診断パケットに応答する第1のトレース応答パケットを送信させる情報を有する、実行することと、
前記第1のプローブおよび前記1つまたは複数の追加のプローブの結果に基づいて、前記ネットワークフローの前記パスの一部である前記コンピュータネットワークの少なくとも1つのリンクが障害を起こしたかどうかを判定することと
を含む動作を実行させる、1つまたは複数のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、コンピュータネットワーク障害の発生源の検出に関する。
【背景技術】
【０００２】
典型的なコンピュータネットワークは、1つまたは複数のリンク、および1つまたは複数のネットワークデバイス、たとえばスイッチまたはルータを通して、共に接続された複数のコンピュータを含む。コンピュータネットワークは、コンピュータネットワークの1つまたは複数の構成要素の障害を含む、多数の理由のために、部分的または全体的な障害を経験する可能性がある。たとえば、コンピュータネットワーク内のいくつかのリンクの障害は、一定のネットワークフローの伝送において問題を引き起こす可能性がある。ネットワーク内のネットワークデバイスの診断論理は、そのようなリンク障害を検出することができない場合があり、それによって次にコンピュータネットワークが、障害が発生したリンクをパケット転送のために使用し続ける状況を引き起こす可能性がある。コンピュータネットワーク障害の発生源の検出は、コンピュータネットワークのあらゆる構成要素を調査することが実行可能または実現可能ではない場合があるので、困難である場合がある。これは特に、多数のホスト、リンク、およびスイッチを有するより大規模なネットワークの場合に当てはまる。
【発明の概要】
【課題を解決するための手段】
【０００３】
概して、本明細書は、ネットワーク障害の発生源を検出するための技法について説明する。具体的には、本明細書は、スイッチに特定のネットワークフローのパケットの同じパスに沿って診断パケットを転送させる方法でフォーマットされた診断パケットとともに、エンドツーエンドプロービングを使用する技法について説明する。本明細書は、それらのパス上のホップに、診断パケットに対する応答を送信元ホストへ送信させる方法でフォーマットされた診断パケットとともに、トレースプロービングを使用する技法についてさらに説明する。
【０００４】
概して、本明細書で説明する主題の1つの発明的態様は、方法において具現化可能であり、本方法は、送信元と宛先との間のコンピュータネットワーク内のネットワークフローを識別するアクションと、送信元が宛先にエンドツーエンド診断パケットを伝送することを要求することを含む、送信元と宛先との間にエンドツーエンド接続性があるかどうかを判定するための第1のプローブを実行するアクションであって、エンドツーエンド診断パケットが、コンピュータネットワーク内の1つまたは複数のネットワークデバイスに、ネットワークフローのパス上でエンドツーエンド診断パケットを転送させる情報を含む、アクションと、送信元と宛先との間にエンドツーエンド接続性がないとの判定に応答して、送信元がネットワークフローのパスにおける各ホップにそれぞれの第1のトレース診断パケットを伝送することを要求することを含む、送信元と宛先との間のネットワークフローのパスにおける各ホップが動作可能であるかどうかを判定するための第2のプローブを含む、1つまたは複数の追加のプローブを実行するアクションであって、各トレース診断パケットが、それぞれのホップに送信元に対して第1のトレース診断パケットに応答する第1のトレース応答パケットを送信させる情報を有する、アクションと、第1のプローブおよび1つまたは複数の追加のプローブの結果に基づいて、ネットワークフローのパスの一部であるコンピュータネットワークの少なくとも1つのリンクが障害を起こしたかどうかを判定するアクションとを含む。この態様の他の実施形態は、方法のアクションを実行するように各々構成された、対応するコンピュータシステム、装置、および1つまたは複数のコンピュータ記憶デバイス上に記録されたコンピュータプログラムを含む。
【０００５】
本明細書は、システム、装置、およびコンピュータプログラム構成要素に関連して、「構成される」という用語を使用する。1つまたは複数のコンピュータのシステムが特定の動作またはアクションを実行するように構成されることは、システムが、動作中に動作またはアクションをシステムに実行させるソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せをインストールしていることを意味する。1つまたは複数のコンピュータプログラムが特定の動作またはアクションを実行するように構成されることは、1つまたは複数のプログラムが、データ処理装置によって実行されると、動作またはアクションを装置に実行させる命令を含むことを意味する。専用論理回路が特定の動作またはアクションを実行するように構成されることは、回路が、動作またはアクションを実行する電子論理を有することを意味する。
【０００６】
上記および他の実施形態は、各々、場合によっては、以下の特徴のうちの1つまたは複数を単独で、または組み合わせて含むことができる。具体的には、一実施形態は、以下の特徴のすべてを組み合わせて含む。1つまたは複数の追加のプローブを実行するステップは、宛先が宛先と送信元との間のパスにおける各ホップにそれぞれの第2のトレース診断パケットを伝送することを要求することを含む、宛先と送信元との間のパスにおける各ホップが動作可能であるかどうかを判定するための第3のプローブを実行するステップであって、各トレース診断パケットが、それぞれのホップに送信元に対して第2のトレース診断パケットに応答する第2のトレース応答パケットを送信させる情報を有する、ステップを含む。それぞれのホストに関連付けられた第2のトレース診断パケットは、ホップに第2のトレース診断パケットに応答して、ホストに時間超過メッセージを送信させる、第2のトレース診断パケットの有効期限フィールドにおける特定の値を有する。エンドツーエンド診断パケットは、送信元の識別子および宛先の識別子をそれぞれ含む、送信元識別子フィールドおよび宛先識別子フィールドを有する。エンドツーエンド診断パケットは、エンドツーエンド診断パケットが診断パケットであることを示すために、1つまたは複数の特定のフィールドにおいて指定された値を有する。診断パケットは、トランスポート制御プロトコルパケットであり、指定された値は、フラグフィールドのためのゼロ値を備える。それぞれのホップに関連付けられた第1のトレース診断パケットは、ホップが第1のトレース診断パケットに応答して、送信元に時間超過メッセージを送信させる、第1のトレース診断パケットの有効期限フィールドにおける特定の値を有する。
【０００７】
第1のプローブを実行するステップは、送信元がエンドツーエンド診断パケットに応答するエンドツーエンド応答パケットを受信したかどうかを判定するステップと、送信元がエンドツーエンド応答パケットを受信したとの判定に応答して、送信元と宛先との間にエンドツーエンド接続性があると判定するステップと、送信元がエンドツーエンド応答パケットを受信していないとの判定に応答して、送信元と宛先との間にエンドツーエンド接続性がないと判定するステップとをさらに含む。
【０００８】
本方法は、送信元が特定のホップから第1のトレース応答パケットを受信したかどうかを判定するステップと、送信元が特定のホップから第1のトレース応答パケットを受信したとの判定に応答して、特定のホップが動作可能であると判定するステップと、送信元が特定のホップから第1のトレース応答パケットを受信していないとの判定に応答して、特定のホップが動作可能ではないと判定するステップとをさらに含む。
【０００９】
ネットワークフローを識別するステップは、コンピュータネットワーク内の1つまたは複数のホストから再伝送情報を取得するステップと、1つまたは複数のネットワークフローを検出するために、再伝送情報を解析するステップと、1つまたは複数のネットワークフローの各ネットワークフローについて、再伝送情報から再伝送カウントを決定するステップと、その再伝送カウントがしきい値を超える1つまたは複数のネットワークフローのグループを識別するステップと、グループからネットワークフローを選択するステップとを含む。ネットワークフローを識別するステップは、グループ内の各ネットワークフローについて、ネットワークフローの宛先が障害を起こしたかどうかを検出するステップと、その対応する宛先が障害を起こしたいかなるネットワークフローも除外するために、グループを更新するステップとをさらに含む。
【００１０】
本方法は、第1のプローブ、第2のプローブ、および第3のプローブの結果を含む、プローブ結果情報を生成するステップと、ネットワーク内の各リンクについての訪問カウントおよび障害カウントを決定するために、プローブ結果を解析するステップであって、対応するリンクについての訪問カウントが、パケットがリンクに移動した回数を示し、対応するリンクについての障害カウントが、リンクが障害の兆候を示した回数を示す、ステップと、コンピュータネットワークのグラフを生成するステップであって、グラフが、コンピュータネットワーク内のそれぞれのリンクに各々対応するエッジと、エッジに対応するリンクについての訪問カウントおよび障害カウントのうちの少なくとも1つに基づいて決定される、各エッジのための重みとを含む、ステップとをさらに含む。方法は、障害を起こした可能性が高い、コンピュータネットワーク内の少なくとも1つのリンクを検出するために、グラフを解析するステップをさらに含む。
【００１１】
概して、本明細書で説明する主題の1つの発明的態様は、方法において具現化可能であり、本方法は、コンピュータネットワーク内の1つまたは複数のホストから再伝送情報を取得するアクションと、1つまたは複数のネットワークフローを検出するために、再伝送情報を解析するアクションと、1つまたは複数のネットワークフローの各ネットワークフローについて、再伝送情報から再伝送カウントを決定するアクションと、その再伝送カウントがしきい値を超える1つまたは複数のネットワークフローのグループを識別するアクションと、識別されたグループについての1つまたは複数のネットワーク診断結論を生成するアクションとを含む。この態様の他の実施形態は、方法のアクションを実行するように各々構成された、対応するコンピュータシステム、装置、および1つまたは複数のコンピュータ記憶デバイス上に記録されたコンピュータプログラムを含む。
【００１２】
本明細書で説明する主題の特定の実施形態は、以下の利点のうちの1つまたは複数を実現するように実装可能である。コンピュータネットワークは、特定のネットワークフローに関連付けられた障害についてプローブ可能である。ネットワーク診断結果の精度は、実行される必要があるアクティブプロービングの量を制限しながら、アクティブプロービングによって改善可能である。ネットワーク診断からのデータは、グラフベースの推論および計算を可能にする方法で処理可能である。それらのタスクがより計算集約的ではないプロービング方法、およびネットワークをプローブしない受動的な方法を使用して実行されることになる、ネットワークフローを選択することによって、より計算集約的なプロービングタスクの実行を制限することができ、したがってネットワーク診断を実行する全体的なコストが削減される。
【００１３】
本明細書の主題の1つまたは複数の実施形態の詳細が、添付の図面および以下の説明において記載される。主題の他の特徴、態様、および利点は、説明、図面、および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１４】
【図１】ネットワーク診断エンジンを含む、例示的なコンピュータネットワークのブロック図である。
【図２】例示的なネットワーク診断エンジンのブロック図である。
【図３】エンドツーエンドプローブと、その後に続くトレースプローブとを実行するための例示的なプロセスのフロー図である。
【図４Ａ】エンドツーエンドプローブのためのデータフロー図である。
【図４Ｂ】トレースプローブのためのデータフロー図である。
【図５Ａ】診断パケットの例示的な表現の図である。
【図５Ｂ】診断パケットの例示的な表現の図である。
【図５Ｃ】診断パケットの例示的な表現の図である。
【図５Ｄ】診断パケットの例示的な表現の図である。
【図６】再伝送カウントに基づいて、ネットワークフローを分類するための例示的なプロセスのフロー図である。
【図７】ホスト障害を検出するための例示的なプロセスのフロー図である。
【図８】ネットワークリンク信頼性情報を用いて、グラフを生成するための例示的なプロセスのフロー図である。
【発明を実施するための形態】
【００１５】
様々な図面における同様の参照番号および名称は、同様の要素を示す。
【００１６】
図1は、ネットワーク診断エンジン101を含む、例示的なコンピュータネットワーク100のブロック図である。ネットワーク診断エンジン101は、本明細書で説明する技法が実装可能である、1つまたは複数のコンピュータのシステムである。コンピュータネットワーク100は、たとえば分散データセンターにおける複数のデータサーバホストを接続するために使用されるネットワークでもよい。
【００１７】
ネットワーク診断エンジン101は、コンピュータネットワーク100の1つまたは複数の構成要素、たとえばスイッチ、ホストコンピュータ、および/またはリンクの利用可能性および信頼性を監視する。ネットワーク診断エンジン101は、コンピュータネットワーク100内のホストコンピュータがいくつかの機能を実行することを要求し、コンピュータネットワーク100の状態について、ホストコンピュータから情報を取得することができる。ネットワーク診断エンジン101は、ホストコンピュータから取得された情報を使用して、困難を経験している場合があるコンピュータネットワーク100の1つまたは複数の構成要素を検出することができる。いくつかの実装形態では、ネットワーク診断エンジン101は、その情報を使用して、コンピュータネットワーク100の1つまたは複数の構成要素の使用および/または信頼性についての情報の表現、たとえばグラフを生成することができる。例示的なネットワーク診断エンジン101については、図2を参照しながら以下でより詳細に説明する。
【００１８】
コンピュータネットワーク100は、複数のホストコンピュータ、すなわちホストA 111、ホストB 112、ホストC 113、およびホストD 114を含む。ホストコンピュータは、複数のスイッチ、すなわちスイッチA 141、スイッチB 142、スイッチC 143、スイッチD 144、スイッチE 145、スイッチF 146、スイッチG 147、およびスイッチH 148を通して互いに接続される。2つのスイッチ、またはスイッチおよびホストが、コンピュータネットワーク100内のリンクを通して互いに接続される。リンクは、スイッチ内のインターフェースに対応してもよい物理接続である。
【００１９】
各ホストは、通信モジュール、詳細には、ホストA 111内の通信モジュールA 121、ホストB 112内の通信モジュールB 122、ホストC 113内の通信モジュールC 123、およびホストD 114内の通信モジュールD 124を有する。所与のホスト内の通信モジュールは、ホストからスイッチに通信パケット、たとえばトランスポート制御プロトコル(TCP)パケットまたはユーザデータグラムプロトコル(UDP)パケットを送信し、スイッチからホストへの通信パケットを受信する。
【００２０】
スイッチは、コンピュータネットワーク内で通信パケットを受信、処理、および転送する例示的なコンピュータネットワーキングデバイスである。本明細書はスイッチに言及するが、本明細書で説明する技法は、ルータおよびイーサネットハブなどのコンピュータネットワーク内で通信パケットを受信、処理、および転送可能な他のタイプのコンピュータネットワーキングデバイスを使用するコンピュータネットワークに適用されてもよい。
【００２１】
各スイッチは、1つもしくは複数のホストコンピュータ、および/または1つもしくは複数の他のスイッチから、通信パケットを受信することができる。スイッチが通信パケットを受信するとき、スイッチは、パケットを転送するための実現可能なパスを選択し、パケットのために選択されたパスに基づいて、パケットを転送する先の次のホップ、すなわちホストまたはスイッチを決定する。たとえば、スイッチA 141が、ホストD 114に宛てられたホストA 111からのパケットを受信する場合、スイッチAは、パケットのために、スイッチA 141→スイッチE 145→スイッチD 144→ホストD 114というパスを選び、選択されたルートにおける次のホップであるスイッチE 145に、パケットを転送することができる。
【００２２】
いくつかの状況では、スイッチは、送信元ホストと宛先ホストとの間に複数の実現可能なパスがあると判定してもよい。たとえば、スイッチA 141が、ホストD 114に宛てられたホストA 111からのパケットを受信する場合、スイッチA 141は、送信元ホストA 111から宛先ホストD 114にパケットを転送するために、スイッチA 141→スイッチE 145→スイッチD 144→ホストD 114というパス、スイッチA 141→スイッチF 146→スイッチD 144というパス、および多数の他のパスが実現可能なパスであると判定することができる。
【００２３】
スイッチは、パケットの送信元と宛先との間に複数の利用可能なパスがあるとき、パケットを転送するためのパスを選択するために、転送アルゴリズムを使用することができる。転送アルゴリズムは、パケットのための送信元と宛先との間の任意のパスを選択することができるが、いくつかの転送アルゴリズムは、同じパスに沿ってネットワークフローに関連付けられたパケットをルーティングすることを目指す。ネットワークフローは、特定の時間フレーム内の送信元ホストと宛先ホストとの間の通信を特徴とすることができる。
【００２４】
いくつかの実装形態では、転送アルゴリズムは、ルートを選択するために、パケットヘッダからの情報を使用する。たとえば、転送アルゴリズムは、ルートを選択するために、通信パケットの送信元および宛先の識別子、たとえばインターネットプロトコル(IP)アドレスと、通信パケットの送信元および宛先ポートの識別子(送信元TCPポートおよび宛先TCPポートなど)と、通信のトランスポートプロトコル識別子とを使用することができる。たとえば、スイッチは、通信パケットの送信元および宛先のIPアドレスと、送信元および宛先TCPポートと、トランスポートプロトコル識別子とにスイッチ固有のハッシング関数を適用して、パケットのためのハッシュ値を生成し、ハッシュ値を使用して、複数の実現可能なパスの間でパケットの送信元と宛先との間のパスを選択してもよい。結果として、転送アルゴリズムは、同じパスに沿って送信元ホストと宛先ホストとの間の所与のネットワークフローのすべてのパケットをルーティングすることになる。
【００２５】
パケットを転送するためのパスを選択するために、通信パケットの送信元および宛先の識別子を使用するいくつかの転送アルゴリズムはまた、等価コストマルチパス転送(ECMP)と呼ばれる転送方式に依拠する。ECMPを使用するスイッチは、たとえばパケットが宛先に到達するために通過しなければならないことになるホップ間のリンクの数、および各リンクに関連付けられた(たとえば、リンクの長さおよび/または速度に基づいて決定された)推定コストに基づいて、通信パケットの送信元と宛先との間の各実現可能なパスに関連付けられたコストの推定値を取得し、パケットを転送するためのコストの最低推定値を有するパスを選択してもよい。送信元と宛先ホストとの間で利用可能な複数の最低コストのパスがある場合、スイッチは、通信パケットの送信元および宛先の識別子、通信パケットのための送信元ポートおよび宛先ポートの識別子、ならびにトランスポートプロトコル識別子などの1つまたは複数の追加のファクタに基づいて、最低コストのパスを選んでもよい。たとえば、スイッチは、送信元通信パケットの識別子、宛先通信パケットの識別子、送信元ポートの識別子、宛先ポートの識別子、およびトランスポートプロトコルの識別子をハッシングしてもよい。スイッチは、得られたハッシュ値を使用して、複数の最低コストのパスの間で、パケットの送信元と宛先との間のパスを選択してもよい。この転送技法は、コンピュータネットワーク100が等しいコストの複数のパスの間でパケットを配信することを引き起こし、特定のパスに過負荷をかける可能性を低減することができる。この転送技法はまた、コンピュータネットワーク100に、少なくともある時間期間の間、同じパスに沿って特定のネットワークフローに属する通信パケットを転送させることもできる。
【００２６】
各ホストは、診断モジュール、すなわちホストA 111内の診断モジュールA 131、ホストB 112内の診断モジュールB 132、ホストC 113内の診断モジュールC 133、およびホストD 114内の診断モジュールD 134を含む。ホスト内の診断モジュールは、ネットワーク診断エンジン101によって要求された機能を実行し、コンピュータネットワーク100の状態について、ネットワーク診断エンジン101に情報を提供する。
【００２７】
たとえば、ネットワーク診断エンジン101は、ホスト上の診断モジュールが、たとえばホストの通信モジュールを使用して、ホストから特定の宛先に診断パケットを送信することを要求することができる。診断モジュールは、たとえばパケットに応答して受信された通信パケットに基づいて、コンピュータネットワーク100内の診断パケットの伝送についての情報を取得し、ネットワーク診断エンジン101に、取得された情報を提供することができる。診断パケットの伝送および受信については、以下でより詳細に説明する。
【００２８】
図2は、例示的なネットワーク診断エンジン101のブロック図である。ネットワーク診断エンジン101は、初期検出サブエンジン211と、プローブサブエンジン212と、データ解析サブエンジン213とを含む。
【００２９】
初期検出サブエンジン211は、プローブサブエンジン212がプローブすることができる1つまたは複数のネットワークフロー251を検出する。ネットワークフローは、送信元と宛先との間の通信パケットのフローである。コンピュータネットワーク100は、多数のネットワークフローに関係するパケットを伝送する場合がある。プローブサブエンジン212を使用するネットワークフローのプロービングは、計算集約的タスクとなる可能性がある。プローブサブエンジン212がプローブする必要があるネットワークフローの数を低減することによって、初期検出サブエンジン211は、ネットワーク診断エンジン101の効率を高めることができる。
【００３０】
初期検出サブエンジンは、高再伝送検出器221と、ホスト障害検出器231とを含むことができる。高再伝送検出器221は、1つまたは複数のホストから、ネットワークフローのためのパケット再伝送についての情報を受信し、その再伝送カウントがしきい値を超える1つまたは複数のネットワークフローを決定するために、取得された情報を処理する。高再伝送検出器221は、そのような高再伝送ネットワークフローが潜在的な問題についてのさらなる調査を必要とすると決定してもよく、ホスト障害検出器231に、またはプローブサブエンジン212に、それらのネットワークフローの識別子を伝送することができる。高い再伝送カウントを有するネットワークフローの検出については、図6を参照しながら以下でより詳細に説明する。
【００３１】
ホスト障害検出器231は、たとえば高再伝送検出器221によって検出された高い再伝送を伴うネットワークフロー、および/または1つもしくは複数の検出技法によって検出された他の特定の性質を有するネットワークフローなどのネットワークフローの伝送または受信に関連する特定のホストが障害を起こしたかどうかを判定する。ホスト障害検出器231は、ホスト、たとえば送信元ホストが特定のホストに状態問合せパケットを送信することを要求し、送信元ホストが状態問合せパケットに対する応答を受信したかどうかについて、送信元ホストから情報を取得することができる。ホストは、送信元ホストと宛先ホストとの間のネットワークフローに関連付けられたパスとは異なるパスを含む、コンピュータネットワーク100内の1つまたは複数の可能なパスを介して、状態問合せパケットを送信することができる。転送アルゴリズムによって使用された情報のために状態問合せパケットを伝送するためのパスは、送信元ホストと宛先ホストとの間のネットワークフローに関連付けられたパスとは異なるパスを含む可能性が最も高い。ホスト障害検出器231は、特定のホストが障害を起こしたかどうかを判定するために、取得された情報を処理することができる。ホスト障害の検出については、図7を参照しながら以下でより詳細に説明する。
【００３２】
ホスト障害検出器231が、ネットワークフローに関連付けられたホストが障害を起こしたと判定するとき、ネットワーク診断エンジン101は、(スイッチおよび/またはリンクの障害などの他のネットワーク障害とは対照的に)ホスト障害が、ネットワークフローに関連付けられた問題のある性能のいずれかの兆候、たとえば高い再伝送カウントの可能性の高い理由であると判定することができる。したがって、ネットワーク診断エンジン101は、ホスト障害の影響を受けたネットワークフローを、プローブサブエンジン212によってプローブされているネットワークフローのグループから除外することができる。これによって、プローブサブエンジン212によってプローブされる必要があるネットワークフローのグループをさらに制限し、したがってネットワーク診断エンジン101の効率を高めることができる。
【００３３】
プローブサブエンジン212は、「エンドツーエンドプロービング」および「トレースプロービング」という、2つのタイプのプロービングのうちの少なくとも1つをネットワークフロー251上で実行する。エンドツーエンドプロービングは、プローブサブエンジン212のエンドツーエンドプローバ222によって実行される。トレースプロービングは、プローブサブエンジン212のトレースプローバ232によって実行される。プローブサブエンジンは、データ解析サブエンジン213に、プローブの結果252を伝送する。
【００３４】
エンドツーエンドプローバ222は、送信元ホストが宛先ホストにエンドツーエンド診断パケットを送信することを要求し、宛先ホストがエンドツーエンド診断パケットを受信したと、送信元ホストが決定したかどうかについての情報を取得する。ネットワーク診断エンジン101は、診断パケットと同じパスに沿って伝送されたネットワークフローが、ネットワークフローの送信元と宛先との間のエンドツーエンド接続性を有するかどうかを判定するために、取得された情報を処理することができる。ネットワーク診断エンジン101が、ネットワークフローがそのようなエンドツーエンド接続性を有していないと判定する場合、エンドツーエンドプローバ222は、トレースプローバ232がトレースプロービングを使用して、ネットワークフローによって取られたパスをさらにプローブすることを要求することができる。
【００３５】
トレースプローバ232は、ホストが、ネットワークフローに対応するパスにおけるあらゆる予想されるホップのためにトレース診断パケットを送信することを要求し、各予想されるホップが対応するトレース診断パケットを受信したかどうかについての情報を取得する。ネットワーク診断エンジン101は、パスにおけるいずれかのリンクが障害を起こしたかどうかを判定するために、取得された情報を処理することができる。エンドツーエンドプロービングおよびトレースプロービングについては、図3を参照しながら以下でより詳細に説明する。
【００３６】
データ解析サブエンジン213は、プローブサブエンジン212からプローブ結果252を受信し、プローブ結果252を解析することができる。解析は、特定の出力結果を提供すること、またはコンピュータネットワーク100の構成要素の利用可能性および信頼性の表現を生成することを含み、困難を経験している場合があるコンピュータネットワーク100の1つまたは複数の構成要素を検出することができる。
【００３７】
データ解析サブエンジン213は、グラフコンストラクタ223と、フォルスポジティブ訂正器233と、ネットワーク障害検出器243とを含むことができる。グラフコンストラクタ223は、グラフを生成するためにプローブ結果252を処理する。グラフは、コンピュータネットワーク100内のリンクに対応するエッジと、コンピュータネットワーク100内のスイッチおよび場合によってはホストに対応するノードと、リンクの信頼性の推定値に対応するエッジ重みとを含む。グラフの生成については、図8を参照しながら以下でより詳細に説明する。
【００３８】
グラフコンストラクタ223は、リンクに移動したことが観測された診断パケットのカウント、すなわちリンクについての訪問カウント、およびリンク上で失われたことが観測されたパケットのカウント、すなわちリンクのための障害検出器に基づいて、リンクについての信頼性の推定値を決定することができる。これは、グラフコンストラクタ223が、リンクが低い訪問カウンタを有するので、リンクが低い信頼性の推定値を有すると決定する状況につながる場合がある。しかしながら、いくつかの状況では、リンクのための低い訪問カウンタは、リンクの障害からではなくネットワーク100アクティビティの標準の過程におけるリンクの低利用から生じる可能性がある。そのようなフォルスポジティブ検出を訂正するために、フォルスポジティブ訂正器233は、たとえばその訪問カウントがしきい値を下回るリンクを検出することによって、低利用リンクを検出することができる。次いで、フォルスポジティブ訂正器233は、それらのリンク上のネットワーク100アクティビティを増加させ、プローブ結果252の精度を高めるために、プローブサブエンジン212のトレースプローバ232が、その対応するパスが低利用リンクを含むネットワークフローのためのトレース診断パケットを生成することを要求することができる。
【００３９】
ネットワーク障害検出器243は、グラフコンストラクタ223によって生成されたグラフを取得し、障害を起こした可能性が高いリンクを検出するために、グラフにおけるリンクについての信頼性の推定値を解析する。いくつかの実装形態では、ネットワーク障害検出器243は、その信頼性の推定値がしきい値を下回るリンクが障害を起こした可能性が高いと決定する。
【００４０】
図3は、エンドツーエンドプローブと、その後に続くトレースプローブとを実行するための例示的なプロセスのフロー図である。プロセスは、1つまたは複数のコンピュータのシステム、たとえば図1のネットワーク診断エンジン101によって実行可能である。
【００４１】
システムは、ネットワークフローを識別し(302)、ネットワークフローに関連付けられた送信元ホストが、ネットワークフローに関連付けられた宛先ホストに、ネットワークフローに対応するエンドツーエンド診断パケットを伝送することを要求する(304)。たとえば、ネットワークフローは、さらなる調査のための候補フローを識別するために、1つまたは複数のホストから取得された再伝送情報の解析に基づいて識別可能である。
【００４２】
エンドツーエンド診断パケットは、スイッチに、監視されたネットワークフローに対応するパスと同じパスに沿ってパケットを転送させる特定のフォーマットを有するべきである。たとえば、スイッチが、フローのパケットを転送するためのパスを選択するために、パケットの送信元および宛先の識別子を使用する場合、エンドツーエンド診断パケットは、特定のネットワークフローを特徴づける送信元識別子および宛先識別子と同じ送信元識別子および宛先識別子を有するように構成される。これによって、診断パケットが、対応するネットワークフローと同じパスに沿って転送されることを引き起こす。パケットがフローのパケットと同じパスに従うことになることを保証しなければ、診断パケットは、送信元ホストから宛先ホストへの異なるパスに沿って送信される可能性がある。したがって、そうでなければフローの特定のパスに沿って問題があったかどうかを判定することが困難になる。ネットワークフローのためのエンドツーエンド診断パケットのフォーマットはまた、宛先ホスト上のプログラム、たとえば宛先ホスト上の診断エンジンが、パケットが診断パケットである(フロー内の標準のパケットではない)と決定すること、およびしたがって、応答において対応する診断パケットを送信することを可能にする方法で、ネットワークフローの通常のパケットのフォーマットとは別個であるように構成される。たとえば、エンドツーエンド診断パケットは、いくつかのフィールドにおいて指定された値、たとえばゼロ値を有することができる。これによって、パケットが宛先ホストの通信モジュールによって無視され、したがってネットワークフローの標準のパケットの伝送に干渉させないことが可能である。例示的なエンドツーエンド診断TCPパケットのフォーマットについては、図5Aを参照しながら以下でより詳細に説明する。
【００４３】
システムは、送信元ホストがエンドツーエンド応答パケットを受信したかどうかを判定する(306)。エンドツーエンド応答パケットは、宛先ホスト、たとえば宛先ホスト内の診断モジュールがエンドツーエンド診断パケットを受信したという指示である。エンドツーエンド応答パケットは、それが(1)(たとえば、いくつかのフィールドにおいて指定された値を有することによって)診断パケットであり、標準のネットワークフローパケットではないこと、および(2)(たとえば、エンドツーエンド診断パケットの宛先識別子および送信元識別子にそれぞれ対応する、送信元識別子および宛先識別子を有することによって)エンドツーエンド診断パケットに応答するものであることを示すフォーマットを有するように構成される。例示的なエンドツーエンド診断TCPパケットのフォーマットについては、図5Bを参照しながら以下でより詳細に説明する。
【００４４】
システムが、送信元ホストがエンドツーエンド応答パケットを受信したと判定する場合、システムは、ステップ304および306で実行されたエンドツーエンドプローブの結果に基づいて、プローブ結果を生成する(312)。しかしながら、システムが、送信元ホストがエンドツーエンド応答パケットを受信していないと判定する場合、システムは、ネットワークフローが、エンドツーエンド診断パケットのパスに沿って、送信元ホストによるトレースプローブの形態におけるさらなるプロービング(ステップ308および310)を必要とすると判断する。トレースプローブを実行した後、システムは、エンドツーエンドプローブおよびトレースプローブの結果に基づいて、プローブ結果を生成する(312)。
【００４５】
トレースプローブを実行するために、システムは、送信元ホストが、送信元ホストと宛先ホストとの間のパスにおける各予想されるホップ、たとえばホストおよびスイッチに対応するトレース診断パケットを伝送することを要求し(308)、送信元ホストが各トレース診断パケットに対応するトレース応答パケットを受信したかどうかを判定する(310)。トレース診断パケットに対応するトレース応答パケットは、トレース診断パケットに対応する予想されるホップがトレース応答パケットを受信したという指示である。
【００４６】
特定のホップに対応する各トレース診断パケットは、(1)特定のホップにトレース診断パケットに対応するトレース応答パケットを送信させることができ、(2)応答されているトレース診断パケットを識別するために、対応するホップがトレース応答パケット中に入れることができる識別情報を有する、特定のフォーマットを有するように構成される。各トレース応答パケットは次に、対応するトレース診断パケットの識別情報を含む特定のフォーマットを有する。
【００４７】
たとえば、ホップに対応するトレース診断パケットは、ホップにおいて満了し、ホップが時間超過メッセージの形式においてトレース診断応答を送信させることになるように、その有効期限(TTL)フィールドが送信元ホストによって設定されている、TCPまたはUDPパケットとすることができる。時間超過メッセージは、時間超過メッセージ、すなわち対応するトレース診断パケットをトリガしたパケットのバイトの集合、たとえば最初の64バイトを含むことができるインターネット制御メッセージプロトコル(ICMP)メッセージの一例である。したがって、トレース診断パケットの識別情報は、システムが時間超過メッセージの一部分として含めるトレース診断パケットの一部分におけるものとすることができる。たとえば、時間超過メッセージが、時間超過メッセージをトリガしたパケットの最初の64バイトを含む場合、トレース診断パケットの識別情報は、トレース診断パケットの最初の64バイトにおける、たとえばTCPパケットのシーケンス番号またはUDPパケットの長さフィールドにおけるものとすることができるので、システムは、時間超過メッセージ内にそれらの識別情報を含めることになる。本明細書で言及するIPヘッダフィールドのための長さの値のいくつかは、IPプロトコルのバージョン4(IPv4)に従う通信パケットのフォーマットを指す。他のバージョンのIPプロトコルは、他のフォーマットを使用する場合がある。
【００４８】
例示的なTCPトレース診断パケットについては、図5Cを参照しながら以下でより詳細に説明する。例示的なICMPトレース応答パケットについては、図5Dを参照しながら以下でより詳細に説明する。
【００４９】
図4Aおよび図4Bは、それぞれ、エンドツーエンドプローブおよびトレースプローブのためのデータフロー図である。図4Aは、送信元ホスト401から宛先ホスト402に送信されたエンドツーエンド診断パケット411と、宛先ホスト402から送信元ホスト401に送信された、対応するエンドツーエンド応答パケットとを示す。送信元ホスト401は、パケットのシーケンスの一部として、したがってシーケンス番号とともに、エンドツーエンド診断パケット411を送信することができる。宛先ホスト402は、エンドツーエンド診断パケット411のシーケンス番号に対応する確認応答番号とともに、シーケンスの単一のパケットとして、エンドツーエンド応答パケット412を送信することができる。
【００５０】
図4Bは、送信元ホスト401から送信された2つのトレース診断パケットを示す。第1のトレース診断パケットであるトレース診断パケット1 421は1のTTL値を有し、したがってそのルート上の第1のホップ、すなわちスイッチ403において、デクリメントおよび満了する。第2のトレース診断パケット、すなわちトレース診断パケット422は2のTTL値を有し、したがってスイッチ403によって、宛先ホスト402に伝送される。次いで、第2のトレース診断パケット422は、宛先ホスト402において満了する。
【００５１】
図4Bはまた、2つのトレース応答パケットを示す。第1のトレース診断パケット421に応答して、スイッチ403は、送信元ホスト401に、任意のTTL値、たとえば64とともに第1のトレース応答パケット、すなわちトレース応答パケット1 431を送信する。第2のトレース診断パケット422に応答して、宛先ホスト402は、送信元ホスト401に、任意のTTL値とともに第2のトレース応答パケット、すなわちトレース応答パケット2 432を送信する。スイッチ403は、第2のトレース応答パケット432を受信し、送信元ホスト401に伝送する。
【００５２】
図5A〜図5Dは、診断パケットの例示的な表現である。図示されたすべての診断パケットは、32ビットの送信元アドレスフィールド521と、32ビットの宛先アドレスフィールド523と、8ビットのTTLフィールド518とを含むIPヘッダ501を有する。送信元アドレスフィールド521はパケットの送信元の識別子を含み、宛先アドレスフィールド523はパケットの宛先の識別子を含む。TTLフィールド518は、各ホップにおいてデクリメントされ、宛先より前のホップにおいてゼロに到達するとき、ホップにパケットの送信元へ時間超過メッセージを送信させる。
【００５３】
図5A〜図5Cは、TCPペイロード502を含む、例示的なTCPパケットである。TCPペイロードは、32ビットのシーケンス番号534と、32ビットの確認応答番号535と、4ビットのオフセット値536と、6ビットの予約値537と、フラグを含む6ビット値538と、16ビットのウィンドウサイズ値539とを含む。シーケンス番号534は、パケットのシーケンスにおける特定のパケットの位置を示し、確認応答番号535は、その受信が特定のパケットによって確認応答されている元のパケットのシーケンス番号534を示す。
【００５４】
図5Aは、例示的なTCPエンドツーエンド診断パケットを示す。パケットの送信元アドレスフィールド521は、監視されたネットワークフローに関連付けられた送信元ホストのIPアドレスであるが、パケットの宛先アドレスフィールド523は、監視されたネットワークフローに関連付けられた宛先ホストのIPアドレスである。パケットのシーケンス番号534は、パケットのグループにおいてパケットを区別することができ、パケットの確認応答番号は、パケットがエンドツーエンド応答パケットではないことを示すためにゼロである。パケットのオフセット値536、予約値537、フラグビット538、およびウィンドウサイズ539は、パケットが診断パケットであることを示すために、ゼロに設定される。
【００５５】
図5Bは、例示的なTCPエンドツーエンド応答パケットを示す。パケットの送信元アドレスフィールド521は、監視されたネットワークフローに関連付けられた宛先ホストのIPアドレスであるが、パケットの宛先アドレスフィールド523は、監視されたネットワークフローに関連付けられた送信元ホストのIPアドレスである。パケットがエンドツーエンド診断パケットではないので、パケットのシーケンス番号534はゼロであり、パケットの確認応答番号535は、エンドツーエンド応答パケットが確認応答するエンドツーエンド診断パケットのシーケンス番号534に設定される。パケットのオフセット値536、予約値537、フラグビット538、およびウィンドウサイズ539は、パケットが診断パケットであることを示すためにゼロに設定される。
【００５６】
図5Cは、例示的なTCPトレース診断パケットを示す。パケットの送信元アドレスフィールド521は、監視されたネットワークフローに関連付けられた送信元ホストのIPアドレスであるが、パケットの宛先アドレスフィールド523は、監視されたネットワークフローに関連付けられた宛先ホストのIPアドレスである。パケットのTTLフィールド518は、各ホップにおいてデクリメントされる場合、パケットがトレースすることを求める特定のホップにおいてゼロに到達することになる値である。パケットのシーケンス番号534は、パケットのための識別値を含む。パケットのオフセット値536、予約値537、フラグビット538、およびウィンドウサイズ539は、パケットが診断パケットであることを示すためにゼロとすることができる。いくつかの異なるTCPトレース診断パケットが、フローのパスにおいて連続するホップを取り込むために、異なるTTL値とともに送信可能である。
【００５７】
図5Dは、ICMP時間超過メッセージの形式における、例示的なトレース応答パケットを示す。パケットのICMPペイロード503は、ICMPヘッダ551とICMP本文554とを含む。ICMPヘッダ551は、ICMPメッセージが時間超過メッセージであることを示すために、それぞれ11およびゼロに設定された、8ビットのタイプフィールド552および8ビットのコードフィールド553と、16ビットのチェックサムフィールド556と、他のヘッダ情報をもつ32ビットフィールド555とを含む。ICMP本文554は、ICMPメッセージをトリガしたパケットの一部分、たとえば最初の32バイトを含むことができる。トリガリングパケットが、図5Cに示すようなTCPトレース診断パケットである場合、トリガリングパケットのシーケンス番号フィールド534における識別番号もまた、トレース応答パケットのICMP本文554において現れることになる。結果として、各受信されたICMP時間超過メッセージの起点は、パケットの返される部分における識別情報から決定可能である。
【００５８】
図6は、再伝送カウントに基づいて、ネットワークフローを分類するための例示的なプロセス600のフロー図である。プロセス600について、プロセス600を実行することができるシステム、たとえば図1のネットワーク診断エンジン101に関して説明する。
【００５９】
システムは、1つまたは複数のネットワークフローを識別し(602)、1つまたは複数のホストから、ネットワークフローに関連付けられたパケットの再伝送についての情報を取得する(604)。
【００６０】
いくつかの実装形態では、システムは、1つまたは複数のホストの各ホストにおいて、パケット再伝送のために使用されるカーネル関数の呼出しをトレースすること、および次いで、ネットワークプロトコルに従って、各呼出しを対応する識別情報にマッピングすることによって、ネットワークフローに関連付けられたパケットの再伝送についての情報を生成する。たとえば、システムは、Linux(登録商標)においてTCPパケット再伝送のために使用されるtcp_retransmit_skb()関数の呼出しをトレースすることができる。続いて、Linuxのトレーサ機能ftraceを使用して、システムトレースが、tcp_retransmit_skb()関数によって使用される1つまたは複数のデータ構造、たとえばstruct sockおよびstruct sk_buffデータ構造に渡される。次いで、システムは、擬似ファイルprocfs:/proc/net/tcpによって与えられたマップを使用して、各呼出しを対応するTCP-IPフロー情報にマッピングする。
【００６１】
いくつかの実装形態では、システムは、LinuxにおけるKprobe機構に基づいて開発されたトレーサ機能を使用して、tcp_retransmit_skb()関数の呼出しをトレースする。このトレーサ機能は、tcp_retransmit_skb()関数の呼出しに関連付けられたTCP-IPフロー情報を直接返し、したがってprocfs:/proc/net/tcpを使用する必要をなくすことができる。
【００６２】
システムは、1つまたは複数のネットワークフローの、たとえば指定された時間ウィンドウにわたる、各ネットワークフローのための総再伝送カウントを計算し(606)、そのカウントがしきい値を超えるかどうかを判定する(608)。しきい値は、1などの任意の好適な値とすることができる。
【００６３】
次いで、システムは、ネットワークフローのための総再伝送カウントがしきい値を超えるかどうかに基づいて、各ネットワークフローを分類する(610)。たとえば、システムが、ネットワークフローのための総再伝送カウントがしきい値を超えると決定する場合、システムは、ネットワークフローを、高い再伝送カウントを有するものとして分類することができる。システムが、ネットワークフローのための総再伝送カウントがしきい値を超えないと判定する場合、システムは、ネットワークフローを、高い再伝送カウントを有していないものとして分類することができる。
【００６４】
図7は、ホスト障害を検出するための例示的なプロセス700のフロー図である。プロセス700について、プロセスを実行することができるシステム、たとえば図1のネットワーク診断エンジン101に関して説明する。
【００６５】
システムは、送信元ホストが宛先ホストに状態問合せパケットを送信することを要求する(702)。いくつかの実装形態では、状態問合せパケットは、慣例により、ホスト上のいかなるアプリケーションによってもリッスンされない宛先ホストのポート、たとえば33434以上のポート番号をもつポートへのパケット、たとえばUDPパケットである。送信元ホストは、送信元ホストから宛先ホストにネットワークフローのパケットを伝送するためのパス以外のパスを介して、宛先ホストに状態問合せパケットを送信してもよい。
【００６６】
システムは、送信元ホストが宛先ホストから状態問合せ応答パケットを受信したかどうかを判定する(704)。状態問合せ応答パケットは、宛先ホストが状態問合せパケットを受信したことを示す。いくつかの実装形態では、状態問合せパケットが、慣例により、ホスト上のいかなるアプリケーションによってもリッスンされない宛先ホストのポートへのパケットであるとき、状態問合せ応答パケットは、ICMPポート到達不可能パケットである。ICMPポート到達不可能パケットは、状態問合せパケットについての識別情報が状態問合せパケットの一部分、たとえば最初の64バイトにおいて供給される場合、そのような識別情報をそのICMP本文においてコピーすることができる。
【００６７】
システムは、送信元ホストが状態問合せ応答パケットを受信したかどうかに基づいて、宛先ホストが障害を起こしたかどうかを判定する(706)。システムが、送信元ホストが状態問合せ応答パケットを受信していないと判定する場合、システムは、宛先ホストが障害を起こしたと判定する。システムが、送信元ホストが状態問合せ応答パケットを受信したと判定する場合、システムは、宛先ホストが障害を起こしていないと判定する。
【００６８】
図8は、ネットワークリンク信頼性情報を用いて、グラフを生成するための例示的なプロセスのフロー図である。プロセスは、1つまたは複数のコンピュータのシステム、たとえば図1のネットワーク診断エンジン101によって実行可能である。
【００６９】
システムは、たとえばネットワークデバイスについての情報を含むデータベースから、コンピュータネットワークのマップを取得し(802)、ネットワークマップに基づいて、グラフを構築する(804)。グラフは、コンピュータネットワーク内のリンクに対応するエッジと、コンピュータネットワーク内のスイッチおよび場合によってはホストに対応するノードと、リンクの信頼性の推定値に対応するエッジ重みとを含む。
【００７０】
システムは、コンピュータネットワーク内のスイッチからプローブ結果を取得し(806)、グラフ内の各リンクについての訪問カウントおよび障害カウントを決定するために、プローブ結果を処理する(808)。
【００７１】
いくつかの実装形態では、システムは、たとえばエンドツーエンドプロービング、トレースプロービング、または両方を使用して、監視されたネットワークの各プロービングタスクに対応するプローブ記録を生成するために、プローブ結果を処理する。各プロービングタスクのためのプローブ記録は、プロービングタスクの間に診断パケットが到達に成功したホップを示す。次いで、システムは、コンピュータネットワーク内のリンクについての訪問カウントおよび障害カウントを決定するために、プローブ記録を処理する。プローブ記録が、診断パケットがリンクを通してスイッチまたはホストに到達したことを示すたびに、システムは、リンクについての訪問カウントをインクリメントする。プローブ記録が、診断パケットがその最後のホップとしての特定のスイッチに到達したが、その宛てられた宛先に到達していないことを示すたびに、システムは、最後のホップと宛てられた宛先との間のあらゆるリンクについての障害カウントをインクリメントする。
【００７２】
システムは、各リンクについての信頼性の推定値を決定するために、各リンクについての訪問カウントおよび障害カウントを使用する(810)。システムは、リンクについての障害カウントに基づいて、リンクの信頼性の推定値を減少させることになる。しかしながら、システムは、リンクが低い障害カウントを有するときでも、たとえばリンクがしきい値よりも高い訪問カウントを有し、リンクの輻輳の可能性が高いことを示す場合、および/またはリンクがしきい値よりも低い訪問カウントを有し、リンクの到達不可能性の可能性が高いことを示す場合、低い信頼性の推定値をリンクに割り当てることができる。リンクが低い障害カウントを有するときでも、低い信頼性の推定値をリンクに割り当てるための例示的な技法については、図2におけるフォルスポジティブ訂正器233を参照しながら上記で説明している。
【００７３】
次いで、システムは、各リンクについての信頼性の推定値に基づいて、グラフにマークを付ける(812)。いくつかの実装形態では、システムは、リンクの確率の推定値に基づいて、リンクに対応するグラフ内のエッジに重みまたはラベルを割り当てる。たとえば、システムは、リンクがより低い確率の推定値を有することを示すために、リンクに対応するエッジにより低い重みを割り当てる。
【００７４】
本明細書では、「エンジン」という用語は、1つまたは複数の特定の機能を実行することができるソフトウェアベースのシステムまたはサブシステムを指すために広く使用される。一般に、エンジンは、1つまたは複数のロケーションにおける1つまたは複数のコンピュータ上にインストールされた、1つまたは複数のソフトウェアモジュールまたは構成要素として実装されることになる。場合によっては、1つまたは複数のコンピュータが特定のエンジン専用となり、他の場合には、複数のエンジンを同じ1つまたは複数のコンピュータ上にインストールして実行することができる。
【００７５】
本明細書で説明する主題および機能的動作の実施形態は、本明細書で開示する構造およびそれらの構造的均等物を含む、デジタル電子回路において、有形に実施されたコンピュータソフトウェアもしくはファームウェアにおいて、コンピュータハードウェアにおいて、またはそれらのうちの1つもしくは複数の組合せにおいて実装可能である。本明細書で説明する主題の実施形態は、1つまたは複数のコンピュータプログラム、すなわちデータ処理装置による実行のための、またはデータ処理装置の動作を制御するために、有形の非一時的プログラムキャリア上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして実装可能である。代替的にまたは追加として、プログラム命令は、データ処理装置による実行のために、好適な宛先装置への伝送のために情報を符号化するために生成される、人工的に生成された伝搬信号、たとえば機械により生成された電気信号、光信号、または電磁信号上で符号化可能である。コンピュータ記憶媒体は、機械可読記憶デバイス、機械可読記憶基板、ランダムもしくは順次アクセスメモリデバイス、またはそれらのうちの1つもしくは複数の組合せとすることができる。
【００７６】
「データ処理装置」という用語は、例として、プログラマブルプロセッサ、コンピュータ、または複数のプロセッサもしくはコンピュータを含む、データを処理するためのすべての種類の装置、デバイス、および機械を包含する。装置は、専用論理回路、たとえばFPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)を含むことができる。装置はまた、ハードウェアに加えて、問題のコンピュータプログラムのための実行環境を作成するコード、たとえばプロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの1つもしくは複数の組合せを構成するコードを含むこともできる。
【００７７】
コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、モジュール、ソフトウェアモジュール、スクリプト、またはコードと呼ばれるか、またはそのように説明される場合もある)は、コンパイラ型言語もしくはインタープリタ型言語、または宣言型言語もしくは手続き型言語を含む、任意の形式のプログラミング言語において記述可能であり、スタンドアロンプログラムとして、またはモジュール、構成要素、サブルーチン、もしくはコンピューティング環境において使用するのに好適な他のユニットとしてを含む、任意の形態において展開可能である。コンピュータプログラムは、ファイルシステムにおけるファイルに対応する場合があるが、そうである必要はない。プログラムは、他のプログラムもしくはデータ、たとえばマークアップ言語ドキュメント中に記憶された1つもしくは複数のスクリプトを保持するファイルの一部分において、問題のプログラム専用の単一のファイルにおいて、または、複数の協調されたファイル、たとえば1つもしくは複数のモジュール、サブプログラム、もしくはコードの部分を記憶するファイルにおいて記憶可能である。コンピュータプログラムは、1つのコンピュータ上で、または1つのサイトに位置するか、もしくは複数のサイトにわたって分散され、通信ネットワークによって相互接続された、複数のコンピュータ上で実行されるように展開可能である。
【００７８】
本明細書で説明するプロセスおよび論理フローは、入力データにおいて動作すること、および出力を生成することによって、機能を実行するために、1つまたは複数のコンピュータプログラムを実行する1つまたは複数のプログラマブルコンピュータによって実行可能である。プロセスおよび論理フローはまた、専用論理回路、たとえばFPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)によって実行可能であり、装置もまた、専用論理回路、たとえばFPGAまたはASICとして実装可能である。
【００７９】
コンピュータプログラムの実行に好適なコンピュータは、汎用もしくは専用マイクロプロセッサまたは両方、あるいは任意の他の種類の中央処理ユニットを含み、例として、それに基づくことができる。一般に、中央処理ユニットは、読取り専用メモリもしくはランダムアクセスメモリ、または両方から、命令およびデータを受信することになる。コンピュータの本質的な要素は、命令を実施または実行するための中央処理ユニット、ならびに、命令およびデータを記憶するための1つまたは複数のメモリデバイスである。一般に、コンピュータはまた、データを記憶するための1つまたは複数の大容量記憶デバイス、たとえば磁気ディスク、光磁気ディスク、または光ディスクを含むか、あるいはそれからデータを受信するため、またはそれにデータを転送するため、またはその両方のために動作可能に結合されることになる。ただし、コンピュータは、そのようなデバイスを有する必要はない。その上、コンピュータは、別のデバイス、たとえばほんのいくつかの例を挙げれば、モバイル電話、携帯情報端末(PDA)、モバイルオーディオもしくはビデオプレーヤ、ゲームコンソール、全地球測位システム(GPS)宛先、またはポータブル記憶デバイス、たとえばユニバーサルシリアルバス(USB)フラッシュドライブ中に埋め込み可能である。
【００８０】
コンピュータプログラム命令およびデータを記憶するのに好適なコンピュータ可読媒体は、例として、半導体メモリデバイス、たとえばEPROM、EEPROM、およびフラッシュメモリデバイス、磁気ディスク、たとえば内蔵ハードディスクまたはリムーバブルディスク、光磁気ディスク、ならびにCD ROMおよびDVD-ROMディスクを含む、すべての形態の不揮発性メモリ、媒体、およびメモリデバイスを含む。プロセッサおよびメモリを、専用論理回路によって補うか、または専用論理回路に組み込むことができる。
【００８１】
ユーザとの対話のために送信するために、本明細書で説明する主題の実施形態は、情報をユーザに表示するためのディスプレイデバイス、たとえばCRT(陰極線管)またはLCD(液晶ディスプレイ)モニタと、それによってユーザがコンピュータに入力を送信することができるキーボードおよびポインティングデバイス、たとえばマウスまたはトラックボールとを有する、コンピュータ上で実装可能である。他の種類のデバイスを、ユーザとの対話のために送信するために同様に使用することができ、たとえばユーザに与えられるフィードバックは、任意の形態の感覚フィードバック、たとえば視覚フィードバック、聴覚フィードバック、または触覚フィードバックとすることができ、ユーザからの入力は、音響入力、音声入力、または触覚入力を含む、任意の形態で受信可能である。追加として、コンピュータは、ユーザによって使用されるデバイスにドキュメントを送信し、そのデバイスからドキュメントを受信することによって、たとえばユーザのクライアントデバイス上のウェブブラウザから受信された要求に応答して、そのウェブブラウザにウェブページを送信することによって、ユーザと対話することができる。
【００８２】
本明細書で説明する主題の実施形態は、バックエンド構成要素を、たとえばデータサーバとして含むか、あるいは、ミドルウェア構成要素、たとえばアプリケーションサーバを含むか、あるいは、フロントエンド構成要素、たとえばそれを通してユーザが本明細書で説明する主題の実装形態と対話することができる、グラフィカルユーザインターフェースもしくはウェブブラウザを有するクライアントコンピュータ、または、1つもしくは複数のそのようなバックエンド構成要素、ミドルウェア構成要素、もしくはフロントエンド構成要素の任意の組合せを含む、コンピューティングシステムにおいて実装可能である。システムの構成要素は、任意の形態または任意の媒体のデジタルデータ通信、たとえば通信ネットワークによって相互接続可能である。通信ネットワークの例には、ローカルエリアネットワーク("LAN")、およびワイドエリアネットワーク("WAN")、たとえばインターネットが含まれる。
【００８３】
コンピューティングシステムはクライアントおよびサーバを含むことができる。クライアントおよびサーバは、一般に互いから遠隔であり、典型的には通信ネットワークを通して対話する。クライアントおよびサーバの関係は、それぞれのコンピュータ上で実行しており、互いとクライアントサーバ関係を有するコンピュータプログラムによって生じる。
【００８４】
本明細書は、多数の特定の実装詳細を含むが、これらは、いかなる発明の範囲の限定、または特許請求される場合があるものの範囲の限定としても解釈されるべきではなく、むしろ、特定の発明の特定の実施形態に固有である場合がある特徴の説明として解釈されるべきである。別個の実施形態との関連で本明細書において説明するいくつかの特徴はまた、単一の実施形態において組み合わせて実装可能である。逆に、単一の実施形態との関連で説明する様々な特徴もまた、複数の実施形態において別個に、または任意の好適な部分組合せにおいて実装可能である。その上、特徴は、いくつかの組合せにおいて作用するとして上記で説明される場合があり、最初にそのようなものとして特許請求される場合さえあるが、特許請求される組合せからの1つまたは複数の特徴は、場合によっては、その組合せから削除可能であり、特許請求される組合せは、部分組合せ、または部分組合せの変形形態を対象とする場合がある。
【００８５】
同様に、動作は、特定の順序で図面において図示されるが、これは、望ましい結果を達成するために、そのような動作が図示された特定の順序で、もしくは順番に実行されること、またはすべての図示された動作が実行されることを必要とするものとして理解されるべきではない。いくつかの状況では、マルチタスキングおよび並列処理が有利である場合がある。その上、上記で説明した実施形態における様々なシステムモジュールおよび構成要素の分離は、すべての実施形態においてそのような分離を必要とするものとして理解されるべきではなく、説明したプログラム構成要素およびシステムは、一般に単一のソフトウェア製品にともに統合可能であるか、または複数のソフトウェア製品にパッケージ化可能であることを理解されたい。
【００８６】
主題の特定の実施形態について説明した。他の実施形態は、以下の特許請求の範囲の範囲内である。たとえば、特許請求の範囲に記載されているアクションは、異なる順序で実行され、なお、望ましい結果を達成することが可能である。一例として、添付の図面に図示されたプロセスは、望ましい結果を達成するために、必ずしも図示された特定の順序、または順番を必要とするとは限らない。いくつかの実装形態では、マルチタスキングおよび並列処理が有利である場合がある。
【符号の説明】
【００８７】
100  コンピュータネットワーク、ネットワーク
101  ネットワーク診断エンジン
111  ホストA、送信元ホストA
112  ホストB
113  ホストC
114  ホストD、宛先ホストD
121  通信モジュールA
122  通信モジュールB
123  通信モジュールC
124  通信モジュールD
131  診断モジュールA
132  診断モジュールB
133  診断モジュールC
134  診断モジュールD
141  スイッチA
142  スイッチB
143  スイッチC
144  スイッチD
145  スイッチE
146  スイッチF
147  スイッチG
148  スイッチH
211  初期検出サブエンジン
212  プローブサブエンジン
213  データ解析サブエンジン
221  高再伝送検出器
222  エンドツーエンドプローバ
223  グラフコンストラクタ
231  ホスト障害検出器
232  トレースプローバ
233  フォルスポジティブ訂正器
243  ネットワーク障害検出器
251  ネットワークフロー
252  プローブの結果、プローブ結果
401  送信元ホスト
402  宛先ホスト
403  スイッチ
411  エンドツーエンド診断パケット
412  エンドツーエンド応答パケット
421  トレース診断パケット1、第1のトレース診断パケット
422  トレース診断パケット、第2のトレース診断パケット
431  トレース応答パケット1
432  トレース応答パケット2、第2のトレース応答パケット
501  IPヘッダ
502  TCPペイロード
503  ICMPペイロード
518  8ビットのTTLフィールド、TTLフィールド
521  32ビットの送信元アドレスフィールド、送信元アドレスフィールド
523  32ビットの宛先アドレスフィールド、宛先アドレスフィールド
534  32ビットのシーケンス番号、シーケンス番号、シーケンス番号フィールド
535  32ビットの確認応答番号、確認応答番号
536  4ビットのオフセット値、オフセット値
537  6ビットの予約値、予約値
538  フラグを含む6ビット値、フラグビット
539  16ビットのウィンドウサイズ値、ウィンドウサイズ
551  ICMPヘッダ
552  8ビットのタイプフィールド
553  8ビットのコードフィールド
554  ICMP本文
555  他のヘッダ情報をもつ32ビットフィールド
556  16ビットのチェックサムフィールド
【図１】
2021502788.tif 000003
【図２】
2021502788.tif 000004
【図３】
2021502788.tif 000005
【図４Ａ】
2021502788.tif 000006
【図４Ｂ】
2021502788.tif 000007
【図５Ａ】
2021502788.tif 000008
【図５Ｂ】
2021502788.tif 000009
【図５Ｃ】
2021502788.tif 000010
【図５Ｄ】
2021502788.tif 000011
【図６】
2021502788.tif 000012
【図７】
2021502788.tif 000013
【図８】
2021502788.tif 000014
【国際調査報告】
2021502788.tif 000015
2021502788.tif 000016
2021502788.tif 000017