(57)【特許請求の範囲】
【請求項１】
ネットワークデバイス（Ａ又はＦ）における、ＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）ベースのパス発見を実行するための方法であって、
他のネットワークデバイスの宛て先ＩＰ（Internet  Protocol）アドレスとのＴＷＡＭＰテストセッションについて、カレントホップカウントを１という初期値に設定するステップ（６００）と、
前記ＴＷＡＭＰテストセッションについて、前記ネットワークデバイスにより、ＴＷＡＭＰテストリクエストパケットを、前記宛て先ＩＰアドレスと共に、及び当該ＩＰパケット内の前記カレントホップカウントに設定されたホップカウントと共に送信するステップ（Ｓ３，Ｓ６，６１０）と、
前記送信するステップへの応答としてＩＣＭＰ（Internet  Control  Message  Protocol）時間超過メッセージ（Ｓ４）が前記ネットワークデバイスにより通過ノードから受信される（６２０）場合には、前記通過ノードは、発見されるＴＷＡＭＰエンドツーエンド（Ｅ２Ｅ）パス上で前記ネットワークデバイスから前記カレントホップカウント分離れており、前記ネットワークデバイスが、
前記ＩＣＭＰメッセージからのＩＰアドレスを、前記ＴＷＡＭＰ  Ｅ２Ｅパスについて記録されるＩＰアドレスのシーケンスへ追加すること（Ｓ５，６３０）と、
当該ＴＷＡＭＰテストセッションについての直前のＴＷＡＭＰテストリクエストパケットと比較して１つインクリメントされた前記カレントホップカウントと共に、前記送信するステップを反復すること（６４０）と、
を実行することと、
前記送信するステップへの応答としてＴＷＡＭＰテストリプライメッセージ（Ｓ８）が受信される（６２０）場合には、当該メッセージは前記他のネットワークデバイスから送信されたことになり、前記ネットワークデバイスが、
前記ＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットを送信し、当該ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信すること（６５０）と、
前記ＴＷＡＭＰテストリプライメッセージに応じて、前記ＴＷＡＭＰテストセッションにより横断される順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスの前記シーケンスに固有のＰＭを判定すること（６６０）と、
を実行することと、
を含む方法。
【請求項２】
前記送信することは、前記ネットワークデバイス（Ａ）が２つの他のノード（Ｃ及びＤ）の間で第１ホップについてルーティング決定を行うこと、を含み、前記ルーティング決定は、等コストマルチパス（ＥＣＭＰ）に基づく、請求項１の方法。
【請求項３】
ＩＰアドレスの前記シーケンスにおける１つのＩＰアドレスは、ＩＰベースのハッシングを使用して転送決定を行う等コストマルチパス（ＥＣＭＰ）ポイント（３１２）として動作するネットワークデバイスのものである、請求項１の方法。
【請求項４】
ＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）エンドツーエンド（Ｅ２Ｅ）パスを発見する装置であって、前記装置は、
ホップカウント１つ分よりも離れている他のネットワークデバイス（Ｂ）を返送部として有するＴＷＡＭＰ  Ｅ２Ｅパス（２１０又は３１０）の送信部として動作するネットワークデバイス（Ａ又はＦ）を含み、前記ネットワークデバイスは、
前記ＴＷＡＭＰ  Ｅ２Ｅパスの前記返送部として動作する前記他のネットワークデバイスからＴＷＡＭＰテストリプライメッセージ（Ｓ８）が受信されるまで、前記他のネットワークデバイスの宛て先ＩＰ（Internet  Protocol）アドレスへ、一連のＴＷＡＭＰテストリクエストパケットを、１から開始して増加していくホップカウントと共に送信し（Ｓ３，Ｓ６）、
前記他のネットワークデバイスへ到達するために必要とされるホップカウント数よりも少ないホップカウント数と共に送信された前記ＴＷＡＭＰテストリクエストパケットの各々に応じて、ネットワークインタフェースのＩＰ（Internet  Protocol）アドレスを各々が含むそれぞれのＩＣＭＰ（Internet  Control  Message  Protocol）時間超過メッセージ（Ｓ４）を受信し（Ｓ３，Ｓ６）、前記一連のＴＷＡＭＰテストリクエストパケットの順に配置された前記ＩＰアドレスは、前記ＴＷＡＭＰ  Ｅ２Ｅパスの順方向を表すＩＰアドレスのシーケンスを形成し（Ｓ５）、前記ネットワークデバイスはさらに、
前記ＴＷＡＭＰ  Ｅ２Ｅパスの返送部として動作する前記他のネットワークデバイスから、前記ＴＷＡＭＰテストリプライメッセージ（Ｓ８）を受信し、及び、
前記ＴＷＡＭＰテストリプライメッセージ（Ｓ８）に基づいて、前記ＩＣＭＰ時間超過メッセージから習得されるＩＰアドレスの前記シーケンスに固有の性能測定（ＰＭ）を開始する、
装置。
【請求項５】
前記ネットワークデバイスはさらに、
前記他のネットワークデバイスと、他のＴＷＡＭＰテストリクエストパケット及びＴＷＡＭＰテストリプライメッセージを送信及び受信し（６５０）、並びに、
前記他のＴＷＡＭＰテストリプライメッセージに基づいて性能測定（ＰＭ）を判定する（６６０）、
請求項４の装置。
【請求項６】
前記ネットワークデバイスは、
ＩＰ性能測定（ＰＭ）送信部コントローラモジュール（４１０）と、
ＴＷＡＭＰモジュール（４３０）と、を含み、前記ＴＷＡＭＰモジュールは、
前記ＴＷＡＭＰテストリクエストパケットを生成し及び送信させ（Ｓ３，Ｓ６）、それぞれの前記ＩＣＭＰ時間超過メッセージ（Ｓ４）及び第１のＴＷＡＭＰテストリプライメッセージ（Ｓ８）の提供を受け、前記ＩＣＭＰ時間超過メッセージ及び前記第１のＴＷＡＭＰテストリプライメッセージに応じて前記ＴＷＡＭＰ  Ｅ２Ｅパスの順方向に沿ってＩＰアドレスの前記シーケンスを記録し（Ｓ５）、及び、前記ＴＷＡＭＰ  Ｅ２ＥパスについてＴＷＡＭＰ性能測定（ＰＭ）を前記ＩＰ  ＰＭ送信部コントローラモジュール（４３０）へ提供する、ＴＷＡＭＰ通信モジュール（４５０）、を含む、
請求項４の装置。
【請求項７】
前記ＴＷＡＭＰ通信モジュールは、前記ＴＷＡＭＰ  Ｅ２Ｅパスについて発見される前記シーケンスと共にＴＷＡＭＰパステーブル（４６０）も記憶する、請求項６の装置。
【請求項８】
前記ＩＰ  ＰＭ送信部コントローラモジュール（４１０）は、前記ＴＷＡＭＰパス発見を再度行うために前記ＴＷＡＭＰ通信モジュールを始動するインターバルを追跡する、請求項６の装置。
【請求項９】
前記ネットワークデバイスは、他のＴＷＡＭＰテストセッションについて前記送信部として動作し、
前記ＴＷＡＭＰモジュール（４３０）は、異なるＴＷＡＭＰテストセッションについて、当該ＴＷＡＭＰテストセッション向けの前記ＴＷＡＭＰテストリクエストパケットに含むべき内容を判定するＴＷＡＭＰパケット内容選択モジュール（４４０）をさらに含み、
前記ＩＰ  ＰＭ送信部コントローラモジュール（４４０）は、前記ＴＷＡＭＰエンドツーエンド（Ｅ２Ｅ）パスについてＩＰアドレスの発見された前記シーケンス及びＰＭ情報を、ＴＷＡＭＰテストセッションごとにレポートし、別個のＴＷＡＭＰテストセッションが前記ネットワークデバイスと前記他のネットワークデバイスとの間の異なるＴＷＡＭＰ  Ｅ２Ｅ  ＩＰパスを反映する状況において、前記ＰＭ情報は、同じ送信部と返送部との間の当該異なるＴＷＡＭＰ  Ｅ２Ｅパスに固有になる、
請求項６の装置。
【請求項１０】
前記ネットワークデバイス（Ｆ）は、前記他のネットワークデバイスとの第２のＴＷＡＭＰ  Ｅ２Ｅパスの前記送信部としても動作し、
第１及び第２のＴＷＡＭＰ  Ｅ２ＥパスについてＩＰアドレスの異なるシーケンスを与える転送決定を生じさせるＥＣＭＰポイント（３１２）として動作するネットワークデバイスが前記第１及び第２のＴＷＡＭＰ  Ｅ２Ｅパス上に存在する状況において、前記ネットワークデバイスは、前記第１及び第２のＴＷＡＭＰ  Ｅ２ＥパスについてのＩＰアドレスの当該異なるシーケンスを発見することになる、
請求項４の装置。
【請求項１１】
ネットワークデバイスにおける、送信部及び返送部と同等よりも精細な粒度のレベルでＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）の性能測定（ＰＭ）を実行するための方法であって、
送信部と返送部との間の２つの異なるＴＷＡＭＰテストセッションにより横断されるべき順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスのシーケンスを判定する、ＴＷＡＭＰパス発見を実行すること（７１０）と、
前記異なるＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットを送信し、及び前記ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信すること（７２０）と、
前記ＴＷＡＭＰテストリプライメッセージに応じて、前記２つの異なるＴＷＡＭＰテストセッションにより横断される前記順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスの前記異なるシーケンスに固有のＰＭを判定すること（７３０）と、
を含む方法。
【請求項１２】
前記異なるＴＷＡＭＰテストセッションについてＩＰアドレスの異なるシーケンスを発見した（Ｓ５）結果として、ＴＷＡＭＰテストセッションごとに、当該異なるＴＷＡＭＰテストセッションに固有のＰＭ情報を提供すること、
をさらに含む、請求項１１の方法。
【請求項１３】
前記異なるＴＷＡＭＰテストセッションのＩＰアドレスの前記シーケンスは、前記２つのＴＷＡＭＰテストセッションについて異なる転送決定を行うＥＣＭＰポイント（３１２）として動作するノードのＩＰアドレスを含むため、異なる、請求項１１の方法。
【請求項１４】
ネットワークデバイス（Ａ又はＦ）における、ＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）エンドツーエンド（Ｅ２Ｅ）パスを発見するための方法であって、
ホップカウント１つ分よりも離れている同じ返送部の宛て先ＩＰ（Internet  Protocol）アドレスを各々が有する複数のＴＷＡＭＰテストセッションの各々について、送信部として動作する前記ネットワークデバイスにおいて、
ＴＷＡＭＰテストリプライメッセージ（Ｓ８）が受信されるまで、前記宛て先ＩＰアドレスへ、一連のＴＷＡＭＰテストリクエストパケットを、１から開始して増加していくホップカウントと共に送信すること（Ｓ３，Ｓ６）と、
前記返送部へ到達するために必要とされるホップカウント数よりも少ないホップカウント数と共に送信された前記ＴＷＡＭＰテストリクエストパケットの各々に応じて、それぞれのＩＣＭＰ（Internet  Control  Message  Protocol）時間超過メッセージ（Ｓ４）を受信すること（Ｓ３，Ｓ６）と、を実行し、前記ＩＣＭＰ時間超過メッセージの各々は、当該ＴＷＡＭＰテストセッションについての順方向ＴＷＡＭＰ  Ｅ２Ｅパス（２１０，３１０）に沿ったＩＰアドレスを識別し、さらに、
前記順方向ＴＷＡＭＰ  Ｅ２Ｅパス（２１０，３１０）の前記返送部として動作する他のネットワークデバイス（Ｂ）から、前記ＴＷＡＭＰテストリプライメッセージ（Ｓ８）を受信すること、
を実行するステップと、
前記送信部として動作する前記ネットワークデバイスと前記返送部として動作する前記他のネットワークデバイスとの間の２つの異なる順方向ＴＷＡＭＰ  Ｅ２Ｅパスを、当該順方向ＴＷＡＭＰ  Ｅ２Ｅパスに沿ったＩＰアドレスの前記異なるシーケンスによって区別するステップ（７３０）と、
を含む方法。
【請求項１５】
前記送信することは、前記ネットワークデバイス（Ａ）が２つの他のノード（Ｃ及びＤ）の間で第１ホップについてルーティング決定を行うこと、を含み、前記ルーティング決定は、等コストマルチパス（ＥＣＭＰ）に基づく、請求項１４の方法。
【請求項１６】
前記２つの異なる順方向ＴＷＡＭＰ  Ｅ２ＥパスについてのＩＰアドレスの前記シーケンスは、等コストマルチパス（ＥＣＭＰ）ポイント（３１２）として動作するネットワークデバイスのＩＰアドレスを含み、当該ＥＣＭＰポイントが前記２つの異なる順方向ＴＷＡＭＰ  Ｅ２Ｅパスについて異なる転送決定を行ったため、前記２つの異なる順方向ＴＷＡＭＰ  Ｅ２Ｅパスは、ＩＰアドレスの異なるシーケンスを有する、請求項１４の方法。
【請求項１７】
送信部及び返送部と同等よりも精細な粒度のレベルでＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）の性能測定（ＰＭ）を実行するための、ネットワークデバイス（４００）を含む装置であって、前記ネットワークデバイスは、
送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得されるＩＰアドレスのシーケンスによって区別するＩＰ（Internet  Protocol）性能測定（ＰＭ）送信部コントローラモジュール（４１０）と、
前記ＩＰ  ＰＭ送信部コントローラモジュールに連結されるＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）モジュール（４３０）と、を含み、前記ＴＷＡＭＰモジュールは、
各ＴＷＡＭＰテストセッションについて、ＴＷＡＭＰテストリクエストパケット内に含むべき内容を判定するＴＷＡＭＰパケット内容選択モジュール（４４０）と、
前記ＴＷＡＭＰパケット内容選択モジュールに連結され、ＴＷＡＭＰパス発見のために構成される前記ＴＷＡＭＰテストセッションについて、追加的なＴＷＡＭＰテストリクエストパケットを送信し及び前記ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信することにより前記ＴＷＡＭＰパス発見を実行し、及び前記ＴＷＡＭＰテストセッションの各々についてＴＷＡＭＰ  ＰＭを収集するＴＷＡＭＰ通信モジュール（４５０）と、を含む、
装置。
【請求項１８】
前記ＴＷＡＭＰ通信モジュール（４５０）は、各ＴＷＡＭＰテストセッションについての前記ＴＷＡＭＰテストリクエストパケットの生成と、各ＴＷＡＭＰテストセッションについての前記ＴＷＡＭＰテストリプライメッセージの受信と、前記ＰＭに関連する情報の判定と、を通じて、前記ＴＷＡＭＰ  ＰＭを収集する、請求項１７の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、２０１２年１２月１４日に提出された米国仮出願第６１／７３７，７３０号の利益を主張し、それは参照によりここに取り入れられる。
【０００２】
［分野］
本発明の実施形態は、ネットワーキングの分野に関し、より具体的には、性能を測定することに関する。
【背景技術】
【０００３】
図１は、従来技術に従って２つのＩＰ（Internet  Protocol）エンドポイントの間で使用されているＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）（ＩＥＴＦ（Internet  Engineering  Task  Force）により公表されたＲＦＣ（Request  for  Comments）５３５７及び４６５６）を例示するブロック図である。ＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）（ＲＦＣ５３５７及び４６５６）は、エンドツーエンド（Ｅ２Ｅ）のＩＰ性能測定（ＰＭ）のために使用され得る。言い換えれば、ＴＷＡＭＰは、２つのＩＰエンドポイント間の性能を測定する。具体的には、ＴＷＡＭＰは、送信部（sender）及び返送部（reflector）にて双方向及び一方向の双方の性能（遅延、ジッタ、パケットロス、接続性、並び替え）を測定することができる。
【発明の概要】
【０００４】
ＴＷＡＭＰを増強するための方法及び装置について説明する。本発明の１つの実施形態に従って、他のネットワークデバイスの宛て先ＩＰ（Internet  Protocol）アドレスとのＴＷＡＭＰテストセッションについて、カレントホップカウントが１という初期値に設定される。その後、ＴＷＡＭＰテストリクエストパケットが、宛て先ＩＰアドレスと共に、及び当該ＩＰパケット内のカレントホップカウントに設定されたホップカウントと共に送信される。送信の応答として、ＩＣＭＰ（Internet  Control  Message  Protocol）時間超過メッセージが通過ノードから受信される場合には、通過ノードは、発見されるＴＷＡＭＰエンドツーエンド（Ｅ２Ｅ）パス上でカレントホップカウント分離れており、ネットワークデバイス：１）ＩＣＭＰメッセージからのＩＰアドレスを、ＴＷＡＭＰ  Ｅ２Ｅパスについて記録されるＩＰアドレスのシーケンスへ追加し、当該ＴＷＡＭＰテストセッションについての直前のＴＷＡＭＰテストリクエストパケットと比較して１つインクリメントされたカレントホップカウントと共に、上記送信を反復する。送信の応答として、ＴＷＡＭＰテストリプライメッセージが受信される場合には、当該メッセージは上記他のネットワークデバイスから送信されたことになり、ネットワークデバイスは、ＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットを送信し、ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信し、２）ＴＷＡＭＰテストリプライメッセージに応じて、ＴＷＡＭＰテストセッションにより横断される順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスのシーケンスに固有のＰＭを判定する。
【０００５】
本発明の他の実施形態に従って、送信部と返送部との間の２つの異なるＴＷＡＭＰテストセッションにより横断されるべき順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスのシーケンスを判定するためにＴＷＡＭＰパス発見が実行される。その後、異なるＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットが送信され、ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージが受信される。ＴＷＡＭＰテストリプライメッセージに応じて、２つの異なるＴＷＡＭＰテストセッションにより横断される順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスの異なるシーケンスに固有のＰＭが判定される。
【０００６】
本発明の他の実施形態に従って、以下、ホップカウント１つ分よりも離れている同じ返送部の宛て先ＩＰ（Internet  Protocol）アドレスを各々が有する複数のＴＷＡＭＰテストセッションの各々について、送信部として動作するネットワークデバイスにおいて：１）ＴＷＡＭＰテストリプライメッセージが受信されるまで、宛て先ＩＰアドレスへ、一連のＴＷＡＭＰテストリクエストパケットを、１から開始して増加していくホップカウントと共に送信し；２）返送部へ到達するために必要とされるホップカウント数よりも少ないホップカウント数と共に送信されたＴＷＡＭＰテストリクエストパケットの各々に応じて、それぞれのＩＣＭＰ（Internet  Control  Message  Protocol）時間超過メッセージを受信し；及び３）順方向ＴＷＡＭＰ  Ｅ２Ｅパスの返送部として動作する他のネットワークデバイスから、ＴＷＡＭＰテストリプライメッセージを受信する。ＩＣＭＰ時間超過メッセージの各々は、そのＴＷＡＭＰテストセッションについての順方向ＴＷＡＭＰ  Ｅ２Ｅパスに沿ったＩＰアドレスを識別する。加えて、送信部として動作するネットワークデバイスと返送部として動作する他のネットワークデバイスとの間で、２つの異なる順方向ＴＷＡＭＰ  Ｅ２Ｅパスが、当該順方向ＴＷＡＭＰ  Ｅ２Ｅパスに沿ったＩＰアドレスの異なるシーケンスによって区別される。
【図面の簡単な説明】
【０００７】
本発明は、以下の記述及び本発明の実施形態を例示するために使用される添付の図面を参照することにより、最も良く理解され得る。
【０００８】
【図１】従来技術に従って２つのＩＰ（Internet  Protocol）エンドポイントの間で使用されるＴＷＡＭＰ（Two-Way  Active  Measurement  Protocol）（ＩＥＴＦ（Internet  Engineering  Task  Force）により公表されたＲＦＣ（Request  for  Comments）５３５７及び４６５６）を例示するブロック図である。
【図２Ａ】本発明の実施形態に従う、例示的なネットワークを示すブロック図である。
【図２Ｂ】本発明の実施形態に従う、ＴＷＡＭＰパス発見のために使用される、図２Ａからの例示的なネットワークの送信部と他のノードとの間のＴＷＡＭＰメッセージ群を示すトランザクション図である。
【図３Ａ】第３の例示的なネットワークを示すブロック図である。
【図３Ｂ】本発明の実施形態に従う、ＴＷＡＭＰパス発見のために使用される、図３Ａからの例示的なネットワークの送信部と他のノードとの間のＴＷＡＭＰメッセージ群を示すトランザクション図である。
【図４】本発明の特定の実施形態に従う、ネットワークデバイス内の様々なモジュールを示すブロック図である。
【図５】本発明の実施形態に従う、第４の例示的なネットワークを示す図である。
【図６】本発明の実施形態に従う、ＴＷＡＭＰパス発見を例示するフロー図である。
【図７】送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得されるＩＰアドレスのシーケンスによって区別することにより、より精細なレベルでＴＷＡＭＰ  ＰＭを提供するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下の説明において、数多くの具体的な詳細を示す。しかしながら、本発明の実施形態はこれらの具体的な詳細なしに実施され得ることを理解されたい。他の例では、この説明の理解を曖昧にすることのないよう、既知の回路、構造、及び技術は詳細には示されていない。
【００１０】
本明細書における、“１つの実施形態”、“一実施形態”、“例示的な実施形態”などへの言及は、説明される実施形態が特定の特徴、構造、又は特性を含み得るものの、あらゆる実施形態が当該特定の特徴、構造、又は特性を含むわけでは必ずしもないかもしれないことを示す。その上、そうしたフレーズは、必ずしも同じ実施形態を指しているわけではない。さらに、一実施形態との関係において特定の特徴、構造、又は特性が説明されている場合、明示的に記載されているか否かに関わらず、他の実施形態との関係においてそうした特徴、構造、又は特性を作用させることは、当業者の知識の範囲内であることが思量される。
【００１１】
以下の説明及び特許請求の範囲では、“連結される”及び“接続される”という用語が、それらの派生語と共に使用され得る。これら用語は互いに対して同義語として意図されないことを理解されるべきである。“連結される”は、互いに物理的に又は電気的に直接接触してもしなくておよい２つ以上の要素が互いに協働し又はインタラクションすることを示すために使用される。“接続される”は、互いに連結される２つ以上の要素間における通信の確立を示すために使用される。
【００１２】
電子デバイス（例えば、エンドステーション、ネットワークデバイス）は、非一時的なマシン読取可能な記憶媒体（例えば、磁気ディスク、光ディスク、読み出し専用メモリ、フラッシュメモリデバイス、相変化メモリといったマシン読取可能なストレージ）及び一時的なマシン読取可能な送信媒体（例えば、電気的、光学的、音響的、又は他の形式の伝播信号−例えば、搬送波、赤外線信号など）といったマシン読取可能な媒体を使用して、（ソフトウェア命令群からなる）コード及びデータを記憶し、コード及びデータを（内部的に、及び／又は、他の電子デバイスとの間でネットワーク上で）通信する。加えて、そうした電子デバイスは、典型的には、（コード及び／若しくはデータを記憶する）１つ以上の非一時的なマシン読取可能な媒体、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、及び／若しくはディスプレイ）、並びに（伝播信号を用いてコード及び／若しくはデータを送信するための）ネットワーク接続、といった１つ以上の他のコンポーネントと連結される１つ以上のプロセッサのセットを含む。プロセッサのセット及び他のコンポーネントの連結は、典型的には、１つ以上のバス及びブリッジ（バスコントローラとも呼称される）を通じて行われる。よって、所与の電子デバイスの非一時的なマシン読取可能な媒体は、典型的には、当該電子デバイスの１つ以上のプロセッサのセット上での実行のための命令群を記憶する。本発明の一実施形態の１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの様々な組み合わせを使用して実装されてよい。
【００１３】
ここで用いられるものとして、ネットワークデバイス（例えば、ルータ、スイッチ、ブリッジ）は、ネットワーク上の他の機器（例えば、他のネットワークデバイス、エンドステーション）と通信可能に相互接続するハードウェア及びソフトウェアを含む、ネットワーキング機器の一部である。いくつかのネットワークデバイスは、複数のネットワーキング機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２アグリゲーション、セッションボーダコントロール、ＱｏＳ（Quality  of  Service）、及び／又は加入者管理）についてのサポートを提供し、及び／又は複数のアプリケーションサービス（例えば、データ、音声、及び動画）についてのサポートを提供する、“マルチサービスネットワークデバイス”である。加入者エンドステーション（例えば、サーバ、ワークステーション、ラップトップ、ネットブック、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、ＶＯＩＰ（Voice  Over  Internet  Protocol）フォン、ユーザ機器、端末、ポータブルメディアプレイヤー、ＧＰＳユニット、ゲームシステム、セットトップボックス）は、インターネット上で提供されるコンテンツ／サービス、及び／又は、インターネット上にオーバレイした（例えば、インターネットを通じてトンネリングした）ＶＰＮ（virtual  private  networks）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的には、サービスプロバイダ又はコンテンツプロバイダに属する１以上のエンドステーション（例えば、サーバエンドステーション）、又はピアツーピアサービスに加入しているエンドステーションにより提供され、例えば、公共のウェブページ（例えば、フリーコンテンツ、ストアフロント、検索サービス）、個人用のウェブページ（例えば、ｅメールサービスを提供する、ユーザ名／パスワードでアクセスされるウェブページ）、及び／又はＶＰＮ上の企業ネットワークを含み得る。典型的には、加入者エンドステーションは、エッジネットワークデバイスに（例えば、アクセスネットワークに（有線又は無線で）連結される顧客構内機器を通じて）連結される。エッジネットワークデバイスは、他のエッジネットワークデバイスに（例えば、１以上のコアネットワークデバイスを通じて）連結され、他のエンドステーション（例えば、サーバエンドステーション）に連結される。
【００１４】
本明細書において、ノードは、ＩＰパケット内のＩＰヘッダ情報の一部に基づいてＩＰパケットを転送する。ＩＰヘッダ情報は、発信元ＩＰアドレス、宛て先ＩＰアドレス、発信元ポート、宛て先ポート（ここでは、“発信元ポート”及び“宛て先ポート”は、ネットワークデバイスの物理ポートとは対照的に、プロトコルポートをいう）、トランスポートプロトコル（例えば、ＵＤＰ（user  datagram  protocol）（ＲＦＣ７６８，２４６０，２６７５，４１１３，及び５４０５）、ＴＣＰ（Transmission  Control  Protocol）（ＲＦＣ７９３及び１１８０）、並びにＤＳＣＰ（differentiated  services）値（ＲＦＣ２４７４，２４７５，２５９７，２９８３，３０８６，３１４０，３２４６，３２４７，３２６０，４５９４，５８６５，３２８９，３２９０，及び３３１７）を含む。ノードは、ネットワークデバイスにおいて実装される。物理ノードは、ネットワークデバイス上に直接実装されるが、仮想ノードは、ネットワークデバイス上に実装されるソフトウェアの、及び場合によってはハードウェアの抽象化（abstraction）である。このため、複数の仮想ノードが単一のネットワークデバイス上に実装されてもよい。
【００１５】
ネットワークインタフェースは、物理的であっても仮想的であってもよく、インタフェースアドレスは、ネットワークインタフェースが物理ネットワークインタフェースであれ、仮想ネットワークインタフェースであれ、ネットワークインタフェースに割り当てられるＩＰアドレスである。物理ネットワークインタフェースは、ネットワーク接続がそれを通じて（例えば、無線ネットワークインタフェースコントローラ（ＷＮＩＣ）を通じて無線で、又はネットワークインタフェースコントローラ（ＮＩＣ）へ接続されているポートへのケーブルのプラグインを通じて）行われる、ネットワークデバイス内のハードウェアである。典型的に、１つのネットワークデバイスは、複数の物理ネットワークインタフェースを有している。仮想ネットワークインタフェースは、物理ネットワークインタフェースに関連付けられるか、他の仮想インタフェースに関連付けられるか、又は、単独で稼働し得る（例えば、ループバックインタフェース、ポイントツーポイントプロトコルインタフェース）。ネットワークインタフェースは（物理的であれ仮想的であれ）、番号が付されてもよいし（ＩＰアドレスありのネットワークインタフェース）、番号が付されなくてもよい（ＩＰアドレスなしのネットワークインタフェース）。ループバックインタフェース（及びそのループバックアドレス）は、管理の目的でしばしば使用される（物理的な又は仮想的な）ノードの特定のタイプの仮想ネットワークインタフェース（及びＩＰアドレス）であり、こうしたＩＰアドレスは、ノーダルループバックアドレスとして言及される。ネットワークデバイスの１つ以上のネットワークインタフェースに割り当てられる１つ以上のＩＰアドレスは、そのネットワークデバイスのＩＰアドレスとして言及される。より精細なレベルで、１つのネットワークデバイス上に実装される１つのノードに割り当てられる１つ以上のネットワークインタフェースに割り当てられる１つ以上のＩＰアドレスは、そのノードのＩＰアドレスとして言及されることができる。
【００１６】
ルーティングシステムによる所与の宛て先についてのネクストホップの選択は、１つのパスに帰着し得る（すなわち、ルーティングプロトコルは、最短パス上に１つのネクストホップを生成し得る）。ただし、複数の見込みのある（viable）ネクストホップが存在するとルーティングシステムが判断する（すなわち、ルーティングプロトコルにより生成される転送の解決策が、最短パス上に２つ以上のネクストホップ−複数の等コストのネクストホップ−を提案する）場合には、何らかの追加的な基準が使用される。例えば、コネクションレス型のネットワークでは、等コストマルチパス（又はパス化（pathing）−マルチパス転送もしくはＩＰマルチパスとしても知られる）（ＥＣＭＰ）（ＲＦＣ２９９１及び２９９２）が使用され得る。典型的な実装は、特定のヘッダフィールドを基準として使用することで、確実に、特定のパケットフローのパケット群がパケットフローの順序を守るために常に同じネクストホップ上で転送されるようにしている。マルチパス転送の目的で、パケットフローは、順序の制約を共有するパケットの組として定義される。一例として、特定のＴＣＰ移送シーケンスにおけるパケットの組は、順に到着する必要がある。さもなければ、ＴＣＰロジックは、異なる順序での到達を輻輳と解釈し、ＴＣＰ移送レートを減速するであろう。
【００１７】
［概要］
残念なことに、ＴＷＡＭＰのエンドポイント（送信部又は返送部）上で動作するＴＷＡＭＰプロトコルは、ＩＰルーティング型ネットワークにおける所与のパケットフローについて、送信部と返送部との間のパス上で横断されるリンク及び通過ノード（中間ノードとしても知られる）についての信頼できる知識を有しない。ポリシー、マルチエリア、ＥＣＭＰ、専用のルーティング実装などは、ノードがルーティングシステムから収集することのできる、パスについての先験的な（a  priori）知識を制限する。本発明の特定の実施形態は、こうしたパスに関する、例えば横断されるネットワークデバイスのネットワークインタフェースのＩＰアドレスのシーケンスといった追加的な粒度を発見するために、ＴＷＡＭＰパス発見を用いる。こうしたＴＷＡＭＰパス発見は、典型的には信頼できるものである。又、こうした情報を一元的に得てモデル化することができるとしても、パスを発見する方がやはり早く、性能の劣化に対する自動的なリアクションも可能となる。ＴＷＡＭＰパス発見に加えて、本発明の特定の実施形態は、送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得されるＩＰアドレスのシーケンスによって区別することにより、より精細なレベルでＴＷＡＭＰ  ＰＭを提供する。
【００１８】
所与のＴＷＡＭＰテストリクエストパケット（ＴＷＡＭＰリクエストセッションメッセージ又はＴＷＡＭＰ送信部プローブとしても言及される）がある特定のパスを横断するようにするために、送信部は、値（例えば、ＤＳＣＰ（differentiated  services）値（ＲＦＣ２４７４，２４７５，２５９７，２９８３，３０８６，３１４０，３２４６，３２４７，３２６０，４５９４，５８６５，３２８９，３２９０，及び３３１７）、送信部Ａの発信元ＩＰアドレス、宛て先ＩＰアドレス、発信元ポート（ここでは“発信元ポート”は、ネットワークデバイスの物理ポートとは対照的なものとして、プロトコルポートをいう）、宛て先ポート（ここでは“宛て先ポート”は、ネットワークデバイスの物理ポートとは対照的なものとして、プロトコルポートをいう）ＴＷＡＭＰであり、トランスポートプロトコル（例えば、ＵＤＰ（user  datagram  protocol）（ＲＦＣ７６８，２４６０，２６７５，４１１３，及び５４０５）、ＴＣＰ（Transmission  Control  Protocol）（ＲＦＣ７９３及び１１８０）といった）値をヘッダフィールド内に格納するが、それらは、特定の既知のパスを利用するために任意に選択される値であるか、又は、ＴＷＡＭＰテストリクエストパケットが顧客パケットフローによって辿られる（返送部への）パス上を横断する（ルーティングされる）ようにすることが期待される値、のいずれかであり、この状況において送信部は選択されるどの値がある特定の顧客パケットフローの転送挙動に対応する転送挙動を生み出すかを知るために十分なネットワークに関する情報を有する。
【００１９】
単一の送信部によって、複数のＴＷＡＭＰテストセッションが始動され得る。本発明の実施形態は、それら異なる複数のＴＷＡＭＰテストセッションが始動され及び／又はネットワークを通じて異なるマルチパスの置換（permutation）を辿ることを可能とする。
【００２０】
［ＴＷＡＭＰトレース（パス発見）］
図２Ａは、本発明の実施形態に従った例示的なネットワークを示すブロック図である。この例示的なネットワークは、Ａ、Ｂ、Ｃ、Ｅ、及びＧと表記されたノード（並びに、オプションでノードＤ及びＨ）を含み、それらの各々は、異なるネットワークデバイス上に実装されるノードである。図２Ａは、これらのノードのうちの異なるノードを相互に接続するリンク（ＡからＣ、ＣからＥ、ＥからＧ、及びＧからＢ；並びに、例示されているオプションでは、ＡからＤ、ＤからＨ、及びＨからＧ）を表す線、並びにしたがって、それらのノードが実装される複数のネットワークデバイス、も示している。
【００２１】
ノードＤ及びＨを含むオプションのネットワークでは、ノードＡは、ネクストホップＣとＤとの間で転送決定を行い得る。上に述べたように、ルーティングシステムによる所与の宛て先についてのこうしたネクストホップの選択は、１つのパスに帰着し得る（すなわち、ルーティングプロトコルは、最短パス上に１つのネクストホップを生成し得る）。ただし、複数の見込みのあるネクストホップが存在するとルーティングシステムが判断する（すなわち、ルーティングプロトコルにより生成される転送の解決策が、最短パス上に２つ以上のネクストホップ−複数の等コストのネクストホップ−を提案する）場合には、何らかの追加的な基準が使用される。例えば、コネクションレス型のネットワークでは、ＥＣＭＰが使用され得る。典型的な実装は、特定のヘッダフィールドを基準として使用することで、確実に、特定のパケットフローのパケット群がパケットフローの順序を守るために常に同じネクストホップ上で転送されるようにしている。
【００２２】
図２Ａでは、ノードＡ（発信元ノード）は、ＴＷＡＭＰプロトコルのために、エンドツーエンド（Ｅ２Ｅ）パス２１０の送信部として動作し、ノードＢは返送部（宛て先ノード）として動作する。送信部Ａは、ＴＷＡＭＰテストリクエストパケット（個々にＴＷＡＭＰテストリクエストパケット、ＴＷＡＭＰリクエストセッションメッセージ、又はＴＷＡＭＰ送信部プローブとしても言及される）を始動する。
【００２３】
本発明の実施形態は、ＴＷＡＭＰメッセージが順方向に（すなわち、送信部から返送部へと）横断するパスを発見（トレース）する、ＴＷＡＭＰパス発見を実行する。１つの実施形態では、以下のステップが実行される。
【００２４】
Ｓ１。（例えば、所与のパケットフローについて、送信部のＩＰアドレスと返送部のＩＰアドレスとの間で、）ＴＷＡＭＰ  ＰＭをオンにする指示を受信する。
【００２５】
Ｓ２。ＴＷＡＭＰテストリクエストパケットの内容を選択する（例えば、発信元ＩＰアドレス、発信元ポート、宛て先ＩＰアドレス、宛て先ポート、トランスポートプロトコル。具体例として、所与のパケットフローについてＴＷＡＭＰ  ＰＭをオンにする指示である場合、送信部は、上述のように、ＴＷＡＭＰテストリクエストパケットが、返送部への、所与のパケットフローと同じパスを横断するようにすることが期待される値を、ヘッダフィールド内に格納する。他の具体例として、送信部のＩＰアドレスと返送部のＩＰアドレスとの間でＴＷＡＭＰをオンにする指示である場合、宛て先ポートはＴＷＡＭＰであり、送信部は、ＤＳＣＰ、発信元ポート、及びトランスポートプロトコルを選び出す）。
【００２６】
Ｓ３。ＴＷＡＭＰテストリクエストパケットを、当該ＩＰパケット内のｔｔｌ（time  to  live）又はホップカウントを１にして送信する（setsockopt又は他のメソッドを設定してこの値を設定する）。一般的に、ＴＷＡＭＰテストリクエストパケットは、ネットワークデバイスにより、ＴＴＬをデクリメントするネットワークインタフェース上で受信される。
【００２７】
Ｓ４。宛て先がホップカウントよりも離れている場合、ＴＴＬは“通過ノード”において枯渇してしまい、結果として送信部は、ＩＣＭＰ（Internet  Control  Message  Protocol）（ＲＦＣ７９２及びＲＦＣ４４３）の“時間超過”メッセージを、パス内の‘通過ノード’から受信する（よって、“通過ノード”は、送信部と返送部との間のノードである）。このＩＣＭＰ時間超過メッセージは、その発信元ＩＰアドレスフィールド内に、次のいずれかを含む：１）ＴＷＡＭＰテストリクエストパケットが通過ノードによってその上で受信されたネットワークインタフェース（そのパケットについての到着ネットワークインタフェースとしても知られる）がＴＴＬを枯渇するまでデクリメントしてしまい及びそのネットワークインタフェースが番号を付されたインタフェースに接続されている場合には、そのネットワークインタフェースのＩＰアドレス；又は、２）ＴＷＡＭＰテストリクエストパケットが通過ノードによってその上で受信され及びＴＴＬを枯渇するまでデクリメントしてしまったネットワークインタフェースが番号を付されていないインタフェースに接続されている場合には、その通過ノードのノーダル（nodal）ループバックアドレス。言い換えれば、こうしたＴＴＬ枯渇イベントについては、入手可能な最も具体的なＩＰアドレスが、ＩＣＭＰ時間超過メッセージの発信元ＩＰアドレスのために使用される。
【００２８】
Ｓ５。送信部は、ＩＣＭＰ時間超過メッセージからの発信元ＩＰアドレスを、ＴＷＡＭＰパステーブル内のＴＷＡＭＰ  Ｅ２ＥパスについてのＩＰアドレスのシーケンス内に記録する。
【００２９】
Ｓ６。送信部は、再度、ＴＷＡＭＰテストリクエストパケットを宛て先（返送部）へ送信する。ただし、このＴＷＡＭＰテストセッションについての直前のＴＷＡＭＰテストリクエストパケットと比較して、そのホップカウントは１つインクリメントされる。
【００３０】
Ｓ７。返送部から戻されるＴＷＡＭＰリプライを受信するまで、ステップ４〜６を繰り返す。そのＴＷＡＭＰリプライは、返送部のＩＰアドレスを含むであろう。
【００３１】
Ｓ８。送信部は、ＴＷＡＭＰパステーブルにおけるＴＷＡＭＰ  Ｅ２Ｅパスについてのシーケンスについて、そのＩＰアドレスを記録し（例えば、ＴＷＡＭＰリプライからの返送部のＩＰアドレスを、ＩＰアドレスのシーケンスに追加する。宛て先によってインデックス付けされるＴＷＡＭＰパステーブルを使用する実施形態においては、ＴＷＡＭＰ  Ｅ２ＥパスについてのエントリがＴＷＡＭＰパステーブルにおいて作成されたときに、これは既に実行されているかも知れない。発見中にＩＰアドレスのシーケンスを一時的な場所に記憶する実施形態においては、ＴＷＡＭＰパステーブルにおけるＴＷＡＭＰ  Ｅ２Ｅパスについてのエントリがこの時点で作成され、及びそうした情報がそこに記憶され得る）、パスの性能特性の測定を開始して、ＰＭを判定する。よって、ＴＷＡＭＰパス発見により、順方向（送信部から返送部へ）のＴＷＡＭＰ  Ｅ２Ｅパスに沿ったＩＰアドレスのシーケンスが与えられる。各ＩＰアドレスは、１）ＴＷＡＭＰテストリクエストパケットがその上で受信され、ＴＴＬを満了／枯渇するまでデクリメントし、及び、番号を付されたインタフェースに接続されているネットワークインタフェースのＩＰアドレスであるか、２）ＴＷＡＭＰテストリクエストパケットがその上で受信され、及びＴＴＬを満了／枯渇するまでデクリメントしたネットワークインタフェースが、番号を付されたインタフェースに接続されているので、通過ノードのノーダルループバックアドレスであるか、又は、３）（ホップカウントが満了せずに、宛て先ＩＰアドレスによって識別されるノード又はネットワークインタフェースでフレームが終端された場合には）宛て先のＩＰアドレスである。よって、ＩＰアドレスのシーケンスにおけるＩＰアドレスの各々は、１つのネットワークデバイスを直接的に又は推論的に（inferentially）識別するが、物理ノードのループバックアドレスの場合には直接的に識別し、そのＩＰアドレスが仮想ノードのループバックアドレスであるか、又はＴＷＡＭＰテストリクエストメッセージがその上で受信されたネットワークインタフェースを割り当てられている場合には、（物理ネットワークインタフェースを割り当てられているにせよ、そのネットワークデバイス上に実装されている物理又は仮想ノードに割り当てられた仮想ネットワークインタフェースを割り当てられているにせよ、）推論的に識別する。ＩＰアドレスのシーケンスはネットワークインタフェースのシーケンスを識別し、そうしたネットワークインタフェースは横断されるリンクを識別するので、ＩＰアドレスのシーケンスは、それらのＩＰアドレスに割り当てられるネットワークインタフェース間のリンク（及びしたがって、それらのネットワークインタフェースがその上で実装されているネットワークデバイス間で横断されるリンクのシーケンス）を間接的に識別する。ＩＰ  ＴＴＬをデクリメントしない、もしくはＩＣＭＰメッセージを生成しないように管理上構成されている、及び／又はＴＷＡＭＰの返送部の機能をサポートしないネットワークインタフェースのＩＰアドレスを、上記ＩＰアドレスのシーケンスが含むことはない。
【００３２】
Ｓ９。送信部は、引き続き、ＴＷＡＭＰテストリクエストパケットを送信し、ＴＷＡＭＰテストリプライパケットを受信し、ＴＷＡＭＰ  Ｅ２Ｅパスの要求されたＰＭを完了する。
【００３３】
図６は、本発明の実施形態に従ったＴＷＡＭＰパス発見を例示するフロー図であり、上述のステップを表したものである。フロー図は、ネットワークデバイスが、他のネットワークデバイスの宛て先ＩＰ（Internet  Protocol）アドレスとのＴＷＡＭＰテストセッションについて、カレントホップカウントを１という初期値に設定することで始まる（ブロック６００、これは上記Ｓ３の一部である）。次に、フロー図は、ＴＷＡＭＰテストセッションについて、ネットワークデバイスにより、ＴＷＡＭＰテストリクエストパケットを、宛て先ＩＰアドレスと共に、及びＩＰパケット内のカレントホップカウントに設定されたホップカウントと共に、送信することを示す（ブロック６１０、これは上記Ｓ３の一部である）。これに続いて、ＴＷＡＭＰテストリクエストパケットへの応答として、ＩＣＭＰ時間超過メッセージ又はＴＷＡＭＰテストリプライが受信されるかを判定する（ブロック６２０）。ＩＣＭＰ時間超過メッセージが受信される場合（上記Ｓ４）、フローは、ＩＣＭＰメッセージからのＩＰアドレスを、ＴＷＡＭＰ  Ｅ２Ｅパスについて記録されるＩＰアドレスのシーケンスへ追加し（ブロック６３０、これは上記Ｓ５である）、及びこのＴＷＡＭＰテストセッションについての直前のＴＷＡＭＰテストリクエストパケットと比較して、カレントホップカウントを１つインクリメントし（ブロック６４０、これは上記Ｓ６の一部である）、その後ブロック６１０に戻ること（これはＳ６の残りである）を含む。代わりにＴＷＡＭＰテストリプライが受信される場合には、送信部は転送パス情報を獲得したことになり、フロー図は、以下（これらは上記Ｓ９である）を含む：１）ＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットを送信し、当該ＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信すること（６５０）、及び２）ＴＷＡＭＰテストリプライメッセージに応じて、ＴＷＡＭＰテストセッションにより横断される順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスのシーケンスに固有のＰＭを判定すること（６６０）。
【００３４】
図２Ｂは、本発明の実施形態に従う、ＴＷＡＭＰパス発見のための上述のステップに関連して、図２Ａからの例示的なネットワークの送信部と他のノードとの間のＴＷＡＭＰメッセージ群を示すトランザクション図である。図２Ｂは、図２ＡからのノードＡ、Ｃ、Ｅ、Ｇ、及びＢをこの順序で、図２Ｂの上部に沿って示す。ノードＡは送信部であり、ノードＢは返送部である。上述の方法がステップ３（Ｓ３）に到達すると、ノードＡはノードＢへ、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝１と共に送信する。宛て先ノードＢは、ホップカウントＴＴＬ＝１よりも離れているので、このパケットはノードＣに到達するにすぎず、ステップ４（Ｓ４）で、ノードＣはノードＡへ、ＩＣＭＰ“時間超過”メッセージを送り返す。これら２つのメッセージは、図２Ｂにおいて２１５と表記されている。これを受けて、ステップ５（Ｓ５）で、ノードＡは、ノードＡによって保持されているＴＷＡＭＰパステーブルにおけるこのパスについてのシーケンスに、ノードＣのＩＰアドレスを追加する。
【００３５】
その後、ステップ６（Ｓ６）で、ノードＡはノードＢへ、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝２と共に送信する。宛て先ノードＢは、ホップカウントＴＴＬ＝２よりも離れているので、このパケットはノードＥに到達するにすぎず、ノードＥは返送部（ノードＢ）ではない。よって、ステップ７（Ｓ７）の結果、フローはステップ４（Ｓ４）へ戻り、ノードＥはノードＡへ、ＩＣＭＰ“時間超過”メッセージを送り返す。これら２つのメッセージは、図２Ｂにおいて２２０と表記されている。Ｓ５の結果、ノードＥのＩＰアドレスが、このパスについてのシーケンスに追加される（Ａ−＞Ｃ−＞Ｅ）。
【００３６】
このプロセスは、ノードＡからＧについて繰り返され、一対のメッセージは２３０と表記されている。その後、ノードＡは、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝５と共にノードＢへ送信することによって、Ｓ６を再度実行する。ノードＢはホップカウントＴＴＬ＝５だけ離れているので、今回は、メッセージはノードＢに到達する。よって、ステップ７（Ｓ７）で、返送部として動作するノードＢは、ＴＷＡＭＰテストリプライメッセージをノードＡへ送り返す。これら２つのメッセージは、図２Ｂにおいて２５０と表記されている。ステップ８（Ｓ８）の結果、ノードＢがこのパスについてのシーケンスに追加される（Ａ−＞Ｃ−＞Ｅ−＞Ｇ−＞Ｂ）。
【００３７】
このパス情報は、様々な目的に使用され得る。例えば、ネットワーク管理システムにレポートされ得る。次に、他の例について説明する。
【００３８】
図３Ａは、第３の例示的なネットワークを示すブロック図である。この例示的なネットワークは、図２Ａに示されているものと同様であるが、次の点で異なる：１）ノードＦがノードＡの前に、ノードＡへのリンクと共に追加されている；２）ノードＡではなく、ノードＦが送信部である；３）前と同様に、ノードＦはパケットフローを始動し、及び／又は、他のノード（図示せず）からパケットフローを受信することができる）：４）ノードＦ（発信元ノード）は、ＴＷＡＭＰプロトコルのために、エンドツーエンド（Ｅ２Ｅ）パス３１０の送信部として動作し、ノードＢは返送部（宛て先ノード）として動作する；及び、５）ノードＡは、ＥＣＭＰポイント３１２として動作する。
【００３９】
図３Ｂは、本発明の実施形態に従う、ＴＷＡＭＰパス発見のための上述のステップに関連して、図３Ａからの例示的なネットワークの送信部と他のノードとの間のＴＷＡＭＰメッセージ群を示すトランザクション図である。図３Ｂは、図３ＡからのノードＦ、Ａ、Ｃ、Ｅ、Ｇ、及びＢをこの順序で、図３Ｂの上部に沿って示す。ノードＦは送信部であり、ノードＢは返送部である。上述の方法がステップ３（Ｓ３）に到達すると、ノードＦはノードＢへ、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝１と共に送信する。宛て先ノードＢはホップカウントＴＴＬ＝１よりも離れているので、このパケットはノードＡに到達するにすぎず、ステップ４（Ｓ４）で、ノードＡはノードＦへ、ＩＣＭＰ“時間超過”メッセージを送り返す。これら２つのメッセージは、図３Ｂにおいて３１５と表記されている。これを受けて、ステップ５（Ｓ５）で、ノードＦは、ノードＦによって保持されているＴＷＡＭＰパステーブルにおけるこのパスについてのシーケンスに、ノードＡのＩＰアドレスを追加する。
【００４０】
その後、ステップ６（Ｓ６）で、ノードＦはノードＢへ、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝２と共に送信する。宛て先ノードＢは、ホップカウントＴＴＬ＝２よりも離れているので、このパケットはノードＣに到達するにすぎず、ノードＣは返送部（ノードＢ）ではない。よって、ステップ７（Ｓ７）の結果、フローはステップ４（Ｓ４）に戻り、ノードＣはノードＦへ、ＩＣＭＰ“時間超過”メッセージを送り返す。これら２つのメッセージは、図３Ｂにおいて３２０と表記されている。Ｓ５の結果、ノードＣのＩＰアドレスが、このパスについてのシーケンスに追加される（Ｆ−＞Ａ−＞Ｃ）。
【００４１】
このプロセスは、ノードＦからＥ及びノードＦからＧについて繰り返され、それぞれの対のメッセージは３３０及び３４０と表記されている。その後、ノードＦは、ＴＷＡＭＰテストリクエストパケットをＴＴＬ＝５と共にノードＢへ送信することによって、Ｓ６を再度実行する。ノードＢはホップカウントＴＴＬ＝５だけ離れているので、今回は、メッセージはノードＢに到達する。よって、ステップ７（Ｓ７）で、返送部として動作するノードＢは、ＴＷＡＭＰテストリプライメッセージをノードＦへ送り返す。これら２つのメッセージは、図３Ｂにおいて３５０と表記されている。ステップ８（Ｓ８）の結果、ノードＢが、このパスについてのシーケンスに追加される（Ｆ−＞Ａ−＞Ｃ−＞Ｅ−＞Ｇ−＞Ｂ）。
【００４２】
図２〜図３は数例のネットワークを示しているが、本発明は任意のトポロジーのネットワーク（例えば、より多くのリンク、より多くのノード、及びより多くのパスを有するもの、並びに、パスがノードＧに収束するのではなく、ノードＢへの最終ホップの起点となることのできる複数のノードが存在するもの、を含む）に適用可能であることを理解されたい。
【００４３】
［ＴＷＡＭＰパス発見及び／又はＴＷＡＭＰ  ＰＭをより精細なレベルで実行する例示的なネットワークデバイス］
同じ送信部と返送部との間の２つの異なるＴＷＡＭＰテストセッションについてのパス発見であって、（例えば、ＴＷＡＭＰパス発見が２つのＴＷＡＭＰテストセッションについてほぼ同時に行われるか、ＴＷＡＭＰテストセッションのうち１つ目のセッションについてＴＷＡＭＰパス発見が完了し性能測定が進行中に２つ目のＴＷＡＭＰテストセッションについてのＴＷＡＭＰパス発見が始まる等、）時間的に重複し、及び、（該当するネットワークトポロジに変化をもたらす障害がない）安定したネットワークにおいて行われているパス発見は、ＩＰアドレスの２つの異なるシーケンス、及びしたがって２つの異なる順方向ＴＷＡＭＰ  Ｅ２Ｅパスを与え得る。これが発生する可能性があるのは、２つの異なるＴＷＡＭＰ  Ｅ２Ｅパスに沿った１つのノードがルータであって２つのＴＷＡＭＰテストセッションについて異なるネクストホップ決定を行っているからであり、異なるネクストホップ決定は、それらのＴＷＡＭＰテストセッションについて発見される異なるＴＷＡＭＰ  Ｅ２ＥパスにおいてＩＰアドレスの異なるシーケンスを与える。これは、ＥＣＭＰ転送によっても発生する可能性がある。この場合、ＥＣＭＰポイントとして動作するノードが、２つのＴＷＡＭＰテストセッションについて異なるネクストホップ決定を行い、その結果、ＩＰアドレスの２つの異なるシーケンスが発見される。これは、レイヤ３（Ｌ３）リンク統合（ＬＡＧ）リンクによっても発生する可能性がある。Ｌ３−ＬＡＧリンクは、（各リンクパスに異なるＩＰアドレスが割り当てられた）複数のＩＰアドレス指定されたリンクパスによって複数のネットワークデバイスへ直接接続しているリンクであり、それらの異なるリンクパスにわたる負荷分散決定は、データ転送プレーンにおいて実行される。この場合、２つのＴＷＡＭＰテストセッションについての異なる負荷分散決定の結果、ＩＰアドレスの２つの異なるシーケンスが発見される。上述の例示的なタイプの発生（ルータ、ＥＣＭＰ転送、Ｌ３−ＬＡＧリンク）は、ここでは一般的に、“ＩＰアドレスベースのパケットフロー決定”として言及され、結果として得られるＴＷＡＭＰ  Ｅ２Ｅパスは、ここでは一般的に、“ＩＰアドレスベースのパケットフローパス”として言及される。上に示したように、本発明の特定の実施形態は、送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得されるＩＰアドレスのシーケンスによって区別することにより、より精細なレベルでＴＷＡＭＰ  ＰＭを提供し得る。
【００４４】
図４は、本発明の特定の実施形態に従った、ネットワークデバイス内の様々なモジュールを示すブロック図である。本発明の１つの実施形態では、ネットワークデバイスは、特定の宛て先（返送部）のＩＰアドレスに基づいてＰＭの粒度を測定するＴＷＡＭＰのための構成オプションを有している（１つの実施形態では、このオプションは、ネットワークデバイス４００内の構成４２０の一部としてのＩＰ  ＰＭ送信部コントローラモジュール４１０へ通信される。また、先に述べたように、本発明の実施形態は、ＴＷＡＭＰをオンにして、例えば１）プロキシＴＷＡＭＰフローが必要とされる所与の顧客パケットフロー、又は２）発信元ＩＰアドレス及び宛て先ＩＰアドレス、を構成において識別することによってＰＭの粒度を測定すること、をサポートする。１つの実施形態では、各ＴＷＡＭＰテストセッションについて、ＴＷＡＭＰテストリクエストパケットに含むべき内容（例えば、ＤＳＣＰ値、発信元ＩＰアドレス、発信元ポート、宛て先ＩＰアドレス、宛て先ポート、トランスポートプロトコル）が、ＴＷＡＭＰパケット内容選択モジュール４４０によって判定され、その内容が、ＴＷＡＭＰ通信モジュール４５０へ提供される。各ＴＷＡＭＰテストセッションについて、ＴＷＡＭＰ通信モジュール４５０は、ＴＷＡＭＰテストリクエストパケットを生成しそれらを送信させ、及び、ＴＷＡＭＰテストリプライメッセージの提供を受ける。ＴＷＡＭＰ通信モジュール４５０は、ＰＭに関連する情報をＩＰ  ＰＭ送信部コントローラモジュール４１０へ提供し、モジュール４１０はその情報を用いて様々なアクションを実行し得る。
【００４５】
送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得された横断されるＩＰアドレスのシーケンスによって区別する１つの実施形態では、（ＩＣＭＰ時間超過メッセージを含む上述のメッセージを送信／受信し、及び各パスについて発見されたシーケンスを記憶しているＴＷＡＭＰパステーブル４６０を保持する）上述のＴＷＡＭＰパス発見方法を、ＴＷＡＭＰ通信モジュール４５０が実行した。１つの実施形態では、ＴＷＡＭＰパス発見は、構成／実装によって決められる特定の構成されたインターバルで、再実行され得る（１つの実施形態では、こうしたインターバルは、構成４２０の一部であり、ＩＰ  ＰＭ送信部コントローラモジュール４１０は、このインターバルを追跡し、及びＴＷＡＭＰ通信モジュール４３０を始動して、所与のＴＷＡＭＰテストセッションについてＴＷＡＭＰパス発見を再び行う）。１つの実施形態では、所与のＴＷＡＭＰテストセッションについて、ＴＷＡＭＰパステーブル４６０は、最初に、ＴＷＡＭＰパケットの内容（例えば、発信元ＩＰアドレス、発信元ポート、宛て先ＩＰアドレス、宛て先ポート、トランスポートプロトコル）を記憶する。その後、発見されたＩＰアドレスのシーケンスが追加される。ＴＷＡＭＰテストセッションのＴＷＡＭＰ  Ｅ２Ｅパスへのこのマッピング／追跡は、この追加されたレベルのネットワークの粒度でＰＭ情報がマッピング／追跡され及び提供されること可能とする。ＰＭ情報はＴＷＡＭＰテストセッションごとに提供されるので、ＩＰ  ＰＭ送信部コントローラモジュール４１０へ送信されるＰＭ情報は、ＴＷＡＭＰテストセッションごとのものである。また、ＩＰ  ＰＭコントローラモジュール４１０は、発見されたＴＷＡＭＰ  Ｅ２Ｅパス及びＰＭ情報にアクセスすることができ、及びＴＷＡＭＰテストセッションごとにそれらをレポートすることができる。別個のＴＷＡＭＰテストセッションが同じ送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２Ｅパスを反映する状況では、ＰＭ情報は、同じ送信部と返送部との間のそれらの異なるＴＷＡＭＰ  Ｅ２Ｅパスに固有となる。それは、部分的に重複するパスルーティングを有する異なるテストセッションからの結果を相互に関連付けて、リンクレベルまでの測定の粒度を達成することもできる（すなわち、いくつかのパス測定は、他の測定と共通のリンクを有するであろうし、いくつかの実施形態は、組み合わせ解析を用いて、共通の及び個別のパス構成要素を分類整理し得る）。
【００４６】
本発明の様々な実施形態は、上記したＴＷＡＭＰ  Ｅ２Ｅパスをキー（例えば、ＴＷＡＭＰテストセッションＩＤ及び／又はＴＷＡＭＰテストセッションキー）ごとに記憶し得る。ＴＷＡＭＰテストセッションＩＤは、例えば、ＴＷＡＭＰテストリクエストパケットの発信元ＩＰアドレス、宛て先ＩＰアドレス、発信元ポート、宛て先ポート、トランスポートプロトコル、及びＤＳＣＰ（differentiated  services）（ＲＦＣ２４７４，２４７５，２５９７，２９８３，３０８６，３１４０，３２４６，３２４７，３２６０，４５９４，５８６５，３２８９，３２９０，及び３３１７））に基づいてよい。
【００４７】
図５は、本発明の実施形態に従った第４の例示的なネットワークを示す。２つのリンクパス（リンクパス５３０Ａ及びリンクパス５３０Ｂ）を統合するＬ３−ＬＡＧリンク５３０によってＡとＣとが接続されていることを除けば、図５は、図２Ａと同じである。上述の技術は、２つの異なるＴＷＡＭＰ  Ｅ２Ｅパスのうち、一方がノードＡからノードＣへ到達するリンクパス５３０Ａを取り（及びしたがって、ノードのそのシーケンスが、リンクパス５３０Ａに関連付けられたネットワークインタフェースのＩＰアドレスを含み）、他方がリンクパス５３０Ｂを取る（及びしたがって、ノードのそのシーケンスが、リンクパス５３０Ｂに関連付けられた、リンクパス５３０Ａについてのそれとは異なるネットワークインタフェースのＩＰアドレスを含む）、２つの異なるＴＷＡＭＰ  Ｅ２Ｅパスを区別することができる。すなわち、２つのＴＷＡＭＰテストセッションについての異なる負荷分散決定の結果、ＩＰアドレスの２つの異なるシーケンスが発見される。図５は、送信部ＡとノードＣとを直接接続する単一のＬ３−ＬＡＧを示しているが、本発明は任意のトポロジーのネットワーク（例えば、より多くのリンクパス、より多くのＬ３−ＬＡＧリンク、より多くのノード、及びより多くのパスを有するもの、並びに、Ｌ３−ＬＡＧリンクが送信部に直接接続されているのではなく、２つの通過ノードの間、又は通過ノードと返送部との間、等にあるもの、を含む）に適用可能であることを理解されたい。
【００４８】
図７は、送信部と返送部との間の異なるＴＷＡＭＰ  Ｅ２ＥパスをＴＷＡＭＰパス発見から習得されるＩＰアドレスのシーケンスによって区別することにより、より精細なレベルでＴＷＡＭＰ  ＰＭを提供するためのフロー図である。ブロック７００において、フロー図は、送信部と返送部との間の２つの異なるＴＷＡＭＰテストセッションにより横断されるべき順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスのシーケンスを判定する、ＴＷＡＭＰパス発見を実行すること（ブロック７００）を含む。これに続いて、異なるＴＷＡＭＰテストセッションについて追加的なＴＷＡＭＰテストリクエストパケットを送信し、及びＴＷＡＭＰテストリクエストパケットのうちのそれぞれ１つに応じてＴＷＡＭＰテストリプライメッセージを受信する（ブロック７１０）。その後、フロー図は、ＴＷＡＭＰテストリプライメッセージに応じて、２つの異なるＴＷＡＭＰテストセッションにより横断される順方向ＴＷＡＭＰ  Ｅ２ＥパスのＩＰアドレスの異なるシーケンスに固有のＰＭを判定すること（ブロック７２０）を示している。
【００４９】
このため、従来技術では、ＴＷＡＭＰは、例えばＥ２ＥパスにおけるＬＡＧ／ＥＣＭＰに気付かないので、ＴＷＡＭＰは、互いに異なるＩＰアドレスベースのパケットフローパスについてＰＭを測定することができない。本発明の実施形態は、ＥＣＭＰ及びＬ３−ＬＡＧにわたるものを含んで、ＩＰ性能の測定のより精細な粒度を提供する。様々な実施形態は、このより精細な粒度の情報を使用して、性能認識型（performance-aware）ルーティング及び／又はトラフィックエンジニアリングを向上し得る（例えば、所与のパスに関する測定に基づいて、トリガを送信して、パスのサービス品質（ＱｏＳ）を変更し、より広い帯域幅を割り当て、及び／又は負荷バランシングのためにより多くのＬ３−ＬＡＧパス又はＥＣＭＰパスを追加することができる）。例えば、ネットワークデバイスは、１）発見されるＴＷＡＭＰ  Ｅ２ＥパスごとにＴＷＡＭＰ測定をレポートし、２）測定値に対するパスポリシー／重みのマッピングをレポートし、３）様々なパス上の測定値に基づいて、各々の又は任意の測定済みパスにかかる負荷を調整することをシステムが決定してよく、及び／又は４）各ルートパス内のノード群をレポートしてよい。
【００５０】
［共通的なネットワークデバイスの構成要素］
ネットワークデバイスは、一般的に、制御プレーンとデータプレーン（転送プレーン又は媒体プレーンとして言及されることもある）とに分けられる。ネットワークデバイスがルータである（又は、ルーティング機能を実装している）場合、制御プレーンは、典型的に、データ（例えばパケット）がどのようにルーティングされるべきか（例えば、データについてのネクストホップ及びそのデータについてのアウトゴーイングポート）を判定し、データプレーンは、そのデータの転送を担う。例えば、他のネットワークデバイスと通信してルートを交換し及び１つ以上のルーティングメトリックに基づいてそれらのルートを選択する、１つ以上のルーティングプロトコル（例えば、ＢＧＰ（Border  Gateway  Protocol）、ＩＧＰ（Interior  Gateway  Protocol）（例えば、ＯＳＰＦ（Open  Shortest  Path  First）、ＲＩＰ（Routing  Information  Protocol）、ＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System））、ＬＤＰ（Label  Distribution  Protocol）、ＲＳＶＰ（Resource  Reservation  Protocol））を、制御プレーンは典型的に含む。
【００５１】
ルート及び近隣情報（adjacency）が制御プレーン上の１つ以上のルーティング構造（例えば、ＲＩＢ（Routing  Information  Base）、ＬＩＢ（Label  Information  Base）、１つ以上の近隣構造）において記憶される。制御プレーンは、ルーティング構造に基づく情報（例えば、近隣及びルート情報）でデータプレーンをプログラムする。例えば、制御プレーンは、近隣及びルート情報を、データプレーン上の１つ以上の転送構造（例えば、ＦＩＢ（Forwarding  Information  Base）、ＬＦＩＢ（Label  Forwarding  Information  Base）、及び１つ以上の近隣構造）にプログラムする。データプレーンは、トラフィックを転送する際にそれら転送構造及び近隣構造を使用する。
【００５２】
ルーティングプロトコルの各々は、何らかのルートメトリックに基づいて、ルートエントリをメインＲＩＢへダウンロードする（メトリックは、異なるルーティングプロトコルについて異なることができる）。ルーティングプロトコルの各々は、メインＲＩＢへダウンロードされないルートエントリを含むルートエントリを、ローカルＲＩＢ（例えば、ＯＳＰＦのローカルＲＩＢ）内に記憶することができる。メインＲＩＢを管理するＲＩＢモジュールは、（メトリックの組に基づいて）ルーティングプロトコルによってダウンロードされたルートからルートを選択し、それら選択されたルート（アクティブルートエントリとして言及されることもある）をデータプレーンへダウンロードする。ＲＩＢモジュールは、ルーティングプロトコル間にルートが再分配されるようにすることもできる。
【００５３】
レイヤ２転送について、ネットワークデバイスは、１つ以上のブリッジングテーブルを記憶することができ、それらを使用して、データを、そのデータにおけるレイヤ２情報に基づいて転送する。
【００５４】
典型的に、ネットワークデバイスは、１つ以上のラインカードの組と、１つ以上の制御カードの組と、オプションとして１つ以上のサービスカード（リソースカードとして言及されることがある）の組と、を含む。これらのカードは、１つ以上のメカニズム（例えば、ラインカードを連結する第１のフルメッシュ及び全てのカードを連結する第２のフルメッシュ）を通じて、互いに連結される。ラインカードの組はデータプレーンを構成し、制御カードの組は、制御プレーンを提供し及びラインカードを通じて外部のネットワークデバイスとパケットを交換する。サービスカードの組は、特化された処理（例えば、レイヤ４からレイヤ７のサービス（例えば、ファイアウォール、ＩＰｓｅｃ、ＩＤＳ、Ｐ２Ｐ）、ＶｏＩＰセッションボーダーコントローラ、移動無線ゲートウェイ（ＧＧＳＮ、ＥＰＳ（Evolved  Packet  System）ゲートウェイ））を提供することができる。例として、サービスカードを使用して、ＩＰｓｅｃのトンネルを終端し、並びに受付認証（attendant  authentication）及び暗号化アルゴリズムを実行し得る。
【００５５】
こうしたネットワークデバイス上に実装されているノードは、（例えば、制御プレーン上で）ＴＷＡＭＰを実行し得る。ＥＣＭＰ（これは例えば、データプレーン上でソフトウェア及び／又はハードウェア（例えば、ＡＳＩＣ）において実装され得る）は、こうしたネットワークデバイスのデータプレーンが、最短パス上に２つ以上のネクストホップを提案する、ルーティングプロトコルにより生成される転送解決策に対処することのできる手法である。
【００５６】
［代替的な実施形態］
例えば、複数の図は、本発明の特定の実施形態によって実行される操作の具体的な順序を示しているが、そうした順序は例示的なものであると理解されたい（例えば、代替的な実施形態は、操作を異なる順序で実行したり、特定の操作を組み合わせたり、特定の操作を一部重複させたりしてよい）。
【００５７】
本発明をいくつかの実施形態に関して説明してきたが、本発明が上述の実施形態に限定されるものではなく、添付の特許請求の範囲の請求項の思想及び範囲内で変形及び変更を加えて実施されることができることは、当業者には理解されるであろう。したがって、上記の説明は、限定ではなく例示と捉えられるべきである。
【図１】
0006017702.tif 000002
【図２Ａ】
0006017702.tif 000003
【図２Ｂ】
0006017702.tif 000004
【図３Ａ】
0006017702.tif 000005
【図３Ｂ】
0006017702.tif 000006
【図４】
0006017702.tif 000007
【図５】
0006017702.tif 000008
【図６】
0006017702.tif 000009
【図７】
0006017702.tif 000010