(57)【要約】  この出願は、フォワーディング・テーブルを検査するための方法および装置、並びにデバイスを提供する。ネットワーク検査デバイスは、ネットワーク・トポロジー情報に従って、検査パケットを生成する。検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含む。ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数である。ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信し、検査されるべきネットワーク・ノードの次のホップであるフィードバック・ノードによって送信される通知メッセージを受信する。ネットワーク検査デバイスは、通知メッセージ内のフィードバック・ノードのIPアドレスおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定する。このようにして、故障が迅速に位置決めされることが可能である。
2019505142.tif 000002
【特許請求の範囲】
【請求項１】
フォワーディング・テーブルを検査するための方法であって、
ネットワーク検査デバイスにより、送信先インターネット・プロトコルIPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するステップであって、前記検査パケットは、ラベル・スタック、生存時間TTL、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、ステップと、
前記検査パケットが前記検査されるべきネットワーク・デバイスに送信されるように、前記ネットワーク検査デバイスにより、前記ラベル・スタックの一番上のリンク・ラベルに従って前記検査パケットを送信するステップと、
前記ネットワーク検査デバイスにより、フィードバック・ノードによって送信される通知メッセージを受信するステップであって、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードである、ステップと、
前記ネットワーク検査デバイスにより、前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するステップと、
を備える方法。
【請求項２】
ネットワーク検査デバイスにより、送信先IPアドレスおよびネットワーク・トポロジー情報に従って検査パケットを生成する前記ステップは、
前記ネットワーク検査デバイスにより、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記送信先IPアドレスまでのフォワーディング経路および前記フォワーディング経路上の前記検査されるべきネットワーク・ノードを決定するステップであって、前記ネットワーク・トポロジー情報は、前記フォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備える、ステップと、
前記ネットワーク検査デバイスにより、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するステップと、
を備える、請求項１に記載の方法。
【請求項３】
前記フィードバック・ノードにより、前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信するステップと、
前記フィードバック・ノードにより、TTLの前記値から1を減算し、TTLの前記値が0であると判定するとき前記通知メッセージを送信するステップと、  
請求項１または２に記載の方法。
【請求項４】
フォワーディング・テーブルを検査するための方法であって、
ネットワーク検査デバイスにより、送信先インターネット・プロトコルIPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するステップであって、前記検査パケットは、ラベル・スタック、生存時間TTL、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、ステップと、
前記ネットワーク検査デバイスにより、前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを送信するステップと、
前記検査されるべきネットワーク・ノードにより、前記検査パケットを受信し、前記ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの前記値から1を減算するステップと、
前記検査されるべきネットワーク・ノードにより、前記ラベル・スタックは空であると判定し、前記送信先IPアドレスおよび前記検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、前記検査パケットをフィードバック・ノードにフォワードするステップと、
前記フィードバック・ノードにより、前記検査パケットを受信し、TTLの前記値から1を減算するステップと、
前記フィードバック・ノードにより、TTLの前記値は0であると判定し、前記ネットワーク検査デバイスに通知メッセージを送信するステップと、
前記ネットワーク検査デバイスにより、前記通知メッセージを受信し、前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードの前記フォワーディング・テーブルが正しいかどうかを判定するステップと、
を備える方法。
【請求項５】
ネットワーク検査デバイスにより、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成する前記ステップは、
前記ネットワーク検査デバイスにより、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、ネットワーク経路および前記ネットワーク経路上の前記検査されるべきネットワーク・ノードを決定するステップであって、前記ネットワーク・トポロジー情報は、前記送信先IPアドレスへのフォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備え、前記フォワーディング経路は前記ネットワーク経路を備える、ステップと、
前記ネットワーク検査デバイスにより、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップの前記リンク・ラベルに従って、前記検査パケットを生成するステップと、
を備える、請求項４に記載の方法。
【請求項６】
前記検査されるべきネットワーク・ノードにより、前記検査パケットを受信する前に、前記方法は、
中間ネットワーク・ノードにより、前記検査パケットを受信し、前記ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの前記値から1を減算するステップと、
前記中間ネットワーク・ノードにより、前記ラベル・スタックは空でないと判定し、前記検査パケットが前記検査されるべきネットワーク・ノードに到着するまで、前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットをフォワードし続けるステップと、
をさらに備える、請求項４または５に記載の方法。
【請求項７】
フォワーディング・テーブルを検査するための装置であって、
送信先インターネット・プロトコルIPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成されたパケット生成モジュールであって、前記検査パケットは、ラベル・スタック、生存時間TTL、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、パケット生成モジュールと、
前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを送信するように構成された送信モジュールと、
フィードバック・ノードによって送信される通知メッセージを受信するように構成された受信モジュールであって、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードである、受信モジュールと、
前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成された判定モジュールと、
を備える装置。
【請求項８】
トポロジー取得モジュールをさらに備え、
前記トポロジー取得モジュールは、前記ネットワーク・トポロジー情報を取得するように構成され、前記ネットワーク・トポロジー情報は、前記送信先IPアドレスへのフォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備え、
前記パケット生成モジュールは、具体的には、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、ネットワーク経路および前記ネットワーク経路上の前記検査されるべきネットワーク・ノードを決定するように構成され、前記フォワーディング経路は前記ネットワーク経路を備え、前記パケット生成モジュールは、具体的には、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するように構成された、請求項７に記載の装置。
【請求項９】
前記通知メッセージは、前記検査パケット内のTTLの前記値が0であるとき、前記フィードバック・ノードによって送信される、請求項７または８に記載の装置。
【請求項１０】
ネットワーク検査デバイスであって、プロセッサとメモリとを備え、
前記メモリは、ネットワーク・トポロジー情報を記憶するように構成され、前記ネットワーク・トポロジー情報は、送信先インターネット・プロトコルIPアドレスへのフォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備え、
前記プロセッサは、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、前記検査パケットは、ラベル・スタック、生存時間TTL、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1であり、前記プロセッサは、前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを送信し、フィードバック・ノードによって送信される通知メッセージを受信するように構成され、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードであり、前記プロセッサは、前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成されたネットワーク検査デバイス。
【請求項１１】
前記プロセッサは、具体的には、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、ネットワーク経路および前記ネットワーク経路上の前記検査されるべきネットワーク・ノードを決定するように構成され、前記フォワーディング経路は前記ネットワーク経路を備え、前記プロセッサは、具体的には、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するように構成された、請求項１０に記載のネットワーク検査デバイス。
【請求項１２】
前記プロセッサは、前記ネットワーク・トポロジー情報を取得するようにさらに構成された、請求項１０または１１に記載のネットワーク検査デバイス。
【請求項１３】
前記通知メッセージは、前記検査パケット内のTTLの前記値が0であるとき、前記フィードバック・ノードによって送信される、請求項１０から１２のいずれか一項に記載のネットワーク検査デバイス。 
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信技術の分野、詳細には、フォワーディング・テーブルを検査するための方法および装置、並びにデバイスに関する。
【背景技術】
【０００２】
インターネット・プロトコル(Internet Protocol, 略してIP)ネットワークにおいて、１つのルートエントリは、ネットワーク・デバイスの制御プレーンにおけるルーティング・テーブル内の１つのIPアドレスに対応する。例えば、IPアドレス192.168.1.1は、ルートエントリ192.168.1.0/24に対応する。しかし、データパケットは、ネットワーク・デバイスのフォワーディング・プレーン(通常、フォワーディング・チップ)におけるフォワーディング・テーブル(forwarding table)によってフォワードされるように命令される。フォワーディング・テーブルは、フォワーディング情報ベース(forwarding information base, 略してFIB)とも呼ばれ得る。ネットワーク・デバイスのフォワーディング・テーブルは、通常、ルーティング・テーブル内の最適ルートに従って生成され、またはアドレス解決プロトコル(Address Resolution Protocol, 略してARP)に基づいて生成され得る。
【０００３】
IPネットワークは、高い信頼性を保証しない。ネットワークにおけるリンク故障によって、ネットワーク・デバイスにおいて生成されるべき対応するフォワーディング・エントリの欠如によって、生成されたフォワーディング・エントリ内のエラーによって、または他の理由によって、データパケット損失またはエラーのような異常が引き起こされ得る。
【発明の概要】
【課題を解決するための手段】
【０００４】
この出願の実施形態は、ネットワーク・デバイスにおけるフォワーディング・テーブルが誤っているかどうかを検査するために、フォワーディング・テーブルを検査するための方法および装置、並びにデバイスを提供する。
【０００５】
第１の態様は、ネットワーク検査デバイスにより、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するステップであって、検査パケットは、ラベル・スタック、生存時間(time to live, 略してTTL)、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値は、Nに1が加えられたもの、すなわち、N+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、Nは1以上の正の整数である(N≧1と表記され得る)、ステップと、検査パケットがラベル・スタックに従って検査されるべきネットワーク・ノードに送信されるように、ネットワーク検査デバイスにより、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信するステップと、を含む、フォワーディング・テーブルを検査するための方法を提供する。ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間に中間ネットワーク・ノードが存在し得る。ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを次のホップのノード、すなわち、中間ネットワーク・ノードにフォワードする。その代わりに、ネットワーク検査デバイスの次のホップのノードは、検査されるべきネットワーク・ノードであり得る。ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを検査されるべきネットワーク・ノードに送信する。ネットワーク検査デバイスは、通知メッセージを受信し、この通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用され、ネットワーク検査デバイスは、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定する。フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップのノードである。ネットワーク検査デバイスは、通常、フィードバック・ノードから通知メッセージを受信する。
【０００６】
このようにして、送信先IPアドレス行きのデータパケットが損失されるか、または誤ってフォワードされる、またはフォワーディング経路上の検査されるべきネットワーク・ノードの送信先IPアドレスへのフォワーディング・テーブルが、顧客要件または他の状況に従って、検査される必要があるとき、ネットワーク検査デバイスは、特定のラベル・スタックおよび特定のTTL値を含む検査パケットを生成し、ラベル・スタックを使用することによって、検査パケットのラベル・フォワーディング経路を特定し、それによって、検査パケットは、ラベル・スタックに従って、検査されるべきネットワーク・ノードに送信されることが可能である。TTLの値は、ホップ毎に1だけ減少される。検査されるべきネットワーク・ノードの次のホップ、すなわち、フィードバック・ノードによって処理された(1だけ減算された)後、検査パケット内のTTLの値が0であるとき、フィードバック・ノードは、通知メッセージをネットワーク検査デバイスに送信することを可能にされる。ネットワーク検査デバイスは、フィードバック・ノードによって送信される通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを迅速に判定することができる。従って、故障の位置決めの効率が増加される。
【０００７】
通知メッセージは、インターネット制御メッセージ・プロトコル(Internet Control Message Protocol, 略してICMP)パケットであり得る。
【０００８】
任意選択で、ネットワーク検査デバイスは、具体的には、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定し、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数(すなわち、N)および各ホップのリンク・ラベルを決定し、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルに従って、検査パケットを生成する。従って、検査パケットを生成するとき、ネットワーク検査デバイスは、検査されるべきネットワーク・ノードに従って、Nの値を決定する。これは、検査パケットが、ラベル・スタック内のN個のリンク・ラベルに従って、検査されるべきネットワーク・ノードにフォワードされることを保証し、検査されるべきネットワーク・ノードにおいてルート・フォワーディングが行われる。ネットワーク検査デバイスは、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを検査することができる。
【０００９】
ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路および各ホップのルート情報を含み得る。ルート情報はリンク・ラベルを含む。リンク・ラベルは、パケットのための単一ホップのフォワーディング経路を特定する。
【００１０】
任意選択で、フィードバック・ノードは、検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信し、TTLの値から1を減算し、検査パケット内のTTLの値が0であるとき、通知メッセージを送信する。
【００１１】
通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していると判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルは正しいと判定し得る。通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないと判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルは誤っていると判定し得る。
【００１２】
検査パケットが検査されるべきネットワーク・ノードの次のホップ(すなわち、フィードバック・ノード)によって処理されるとき、TTLの値は0であるので、通知メッセージがネットワーク検査デバイスに送信されることを保証するために、ネットワーク検査デバイスが検査パケットを生成するとき、ネットワーク検査デバイスは、TTLの値を特定の値に設定する。そして、ネットワーク検査デバイスは、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定し得る。
【００１３】
第２の態様は、ネットワーク検査デバイスにより、ネットワーク・トポロジー情報に従って、検査パケットを生成するステップであって、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、ステップと、検査パケットがラベル・スタックに従って検査されるべきネットワーク・ノードに送信されるように、ネットワーク検査デバイスにより、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信するステップと、含む、フォワーディング・テーブルを検査するための方法を提供する。検査されるべきネットワーク・ノードは、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であると判定し、送信先IPアドレスおよび検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードする。フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0であると判定し、ネットワーク検査デバイスに通知メッセージを送信する。ネットワーク検査デバイスは、通知メッセージを受信し、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定する。
【００１４】
ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間に１つ以上の中間ネットワーク・ノードが存在し得る。ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを次のホップのノード、すなわち、中間ネットワーク・ノードにフォワードする。検査されるべきネットワーク・ノードは、前のホップのノード(中間ネットワーク・ノード)によってフォワードされる検査パケットを受信する。その代わりに、ネットワーク検査デバイスの次のホップのノードは、検査されるべきネットワーク・ノードであり得る。すなわち、ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間に中間ネットワーク・ノードは存在しない。ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを検査されるべきネットワーク・ノードに送信する。検査されるべきネットワーク・ノードは、ネットワーク検査デバイスによって送信される検査パケットを受信する。
【００１５】
このようにして、ネットワーク検査デバイスは、特定のラベル・スタック(N個のリンク・ラベル)および特定のTTL値(値はN+1である)を含む検査パケットを生成し、ラベル・スタックを使用することによって、検査パケットのラベル・フォワーディング経路を特定し、それによって、ラベル・スタックに従って、検査パケットが検査されるべきネットワーク・ノードに送信されることが可能である。TTLの値は、ホップ毎に1だけ減少される。フィードバック・ノード(すなわち、検査されるべきネットワーク・ノードの次のホップ)によって処理された(1だけ減算された)後、検査パケット内のTTLの値が0であるとき、フィードバック・ノードは、通知メッセージをネットワーク検査デバイスに送信する。ネットワーク検査デバイスは、検査されるべきネットワーク・ノードのフォワーディング・テーブルを検査し、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを迅速に判定することができる。従って、故障の位置決めの効率が増加される。
【００１６】
通知メッセージは、ICMPパケットであり得る。
【００１７】
任意選択で、ネットワーク検査デバイスは、具体的には、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定し、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルを決定し、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルに従って、検査パケットを生成する。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路および各ホップのルート情報を含み得る。ルート情報はリンク・ラベルを含む。リンク・ラベルは、パケットのための単一ホップのフォワーディング経路を特定する。
【００１８】
このようにして、ネットワーク検査デバイスがフォワーディング経路上の異なる検査されるべきネットワーク・ノードを検査するならば、ネットワーク経路上の異なる検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを検査するために、ネットワーク検査デバイスは、Nを異なる値に設定し、Nの異なる値を有する検査パケットを生成し得る。
【００１９】
通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していると判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルは正しいと判定し得る。通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないと判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルは誤っていると判定し得る。
【００２０】
任意選択で、ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間に１つ以上の中間ネットワーク・ノードが存在することが可能であり、この方法は、中間ネットワーク・ノードにより、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算するステップと、中間ネットワーク・ノードにより、ラベル・スタックは空でないと判定し、検査されるべきネットワーク・ノードが検査パケットを受信するまで、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードし続けるステップをさらに含む。中間ネットワーク・ノードを制御して、リンク・ラベルのみに従って検査パケットをフォワードするために、検査パケット内の特定のラベル・スタックが使用される。検査パケットは、検査されるべきネットワーク・ノードがラベル・スタックは空であると判定するときのみ、フォワーディング・テーブルに従って、IPルート上でフォワードされる。
【００２１】
第３の態様は、ネットワーク検査デバイスを提供する。ネットワーク検査デバイスは、フォワーディング・テーブルを検査するための上記の方法を実現するネットワーク検査デバイスの機能を有する。機能は、フォワーディング・テーブルを検査するための装置を使用することによって実現され得る。フォワーディング・テーブルを検査するための装置は、ハードウェアによって実現されてもよく、または対応するソフトウェアを実行するハードウェアによって実現されてもよい。ハードウェアまたはソフトウェアは、上記で説明された機能に対応する１つまたは複数のモジュールを含み得る。
【００２２】
第３の態様の可能な実装において、装置は、パケット生成モジュール、送信モジュール、受信モジュール、および判定モジュールを含む。
【００２３】
パケット生成モジュールは、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、送信先IPアドレスは検査されるべきIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である。
【００２４】
送信モジュールは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信するように構成され、それによって、検査パケットは、ラベル・スタックに従って、検査されるべきネットワーク・ノードに送信されることが可能である。
【００２５】
受信モジュールは、通知メッセージを受信するように構成され、通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用され、フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。ネットワーク検査デバイスは、通常、フィードバック・ノードから通知メッセージを受信する。
【００２６】
判定モジュールは、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成される。
【００２７】
任意選択で、通知メッセージは、検査パケット内のTTLの値が0であるとき、フィードバック・ノードによって送信される。通知メッセージは、ICMPパケットであり得る。
【００２８】
任意選択で、パケット生成モジュールは、具体的には、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定し、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルを決定し、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルに従って、検査パケットを生成するように構成される。
【００２９】
任意選択で、装置は、ネットワーク・トポロジー情報を取得するように構成されたトポロジー取得モジュールをさらに含む。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路および各ホップのルート情報を含み得る。ルート情報はリンク・ラベルを含む。リンク・ラベルは、パケットのための単一ホップのフォワーディング経路を特定する。
【００３０】
第３の態様の他の可能な実装において、ネットワーク検査デバイスは、プロセッサおよびメモリを含み、通信インタフェースをさらに含む。プロセッサ、メモリ、および通信インタフェースは、バスを使用することによって互いに接続される。
【００３１】
メモリは、ネットワーク・トポロジー情報を記憶するように構成される。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路および各ホップのルート情報を含む。ルート情報はリンク・ラベルを含む。リンク・ラベルは、パケットのための単一ホップのフォワーディング経路を特定する。
【００３２】
プロセッサは、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1であり、プロセッサは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信し、通知メッセージを受信するように構成され、通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用され、プロセッサは、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成される。フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。ネットワーク検査デバイスは、通常、フィードバック・ノードから通知メッセージを受信する。
【００３３】
通知メッセージは、検査パケット内のTTLの値が0であるとき、フィードバック・ノードによって送信される。
【００３４】
任意選択で、プロセッサは、具体的には、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定し、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルを決定し、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルに従って、検査パケットを生成するように構成される。
【００３５】
任意選択で、プロセッサは、ネットワーク・トポロジー情報を取得するようにさらに構成される。
【００３６】
第４の態様は、ネットワーク・ノードを提供する。ネットワーク・ノードは、フォワーディング・テーブルを検査するための上記の方法を実現する(検査されるべきネットワーク・ノード、中間ネットワーク・ノード、および同様のものを含む)ネットワーク・ノードの機能を有する。機能は、ハードウェアによって実現されてもよく、または対応するソフトウェアを実行するハードウェアによって実現されてもよい。ハードウェアまたはソフトウェアは、上記で説明された機能に対応する１つまたは複数のモジュールを含み得る。
【００３７】
可能な実装において、ネットワーク・ノードは、受信モジュール、パケット処理モジュール、およびフォワーディング・モジュールを含む。
【００３８】
受信モジュールは、検査パケットを受信するように構成される。検査パケットは、ラベル・スタック、生存時間TTL、送信元インターネット・プロトコルIPアドレス、および送信先IPアドレスを含む。ラベル・スタックはN個のリンク・ラベルを含み、Nは1以上の正の整数であり(N≧1と表記され得る)、TTLの値はN+1である。
【００３９】
パケット処理モジュールは、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であるかどうかを判定するように構成される。
【００４０】
フォワーディング・モジュールは、パケット処理モジュールがラベル・スタックは空であると判定するとき、送信先IPアドレスおよびネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードするように構成される。この場合、ネットワーク・ノードは、検査されるべきネットワーク・ノードであり、フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップのノードである。
【００４１】
フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0であると判定するとき、ネットワーク検査デバイスがネットワーク・トポロジー情報および通知メッセージ内のフィードバック・ノードのIPアドレスに従ってネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように、通知メッセージをネットワーク検査デバイスに送信する。
【００４２】
フォワーディング・モジュールは、パケット処理モジュールがラベル・スタックは空でないと判定するとき、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードするようにさらに構成される。この場合、ネットワーク・ノードは、中間ネットワーク・ノードであり、検査パケットが検査されるべきネットワーク・ノードに送信されるように、ラベルに従って検査パケットをフォワードし続る。
【００４３】
他の可能な実装において、ネットワーク・ノードは、プロセッサおよびメモリを含み、通信インタフェースをさらに含む。プロセッサ、メモリ、および通信インタフェースは、バスを使用することによって互いに接続される。
【００４４】
メモリは、フォワーディング・テーブルを記憶するように構成される。プロセッサは、検査パケットを受信するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、N≧1であり、TTLの値はN+1であり、プロセッサは、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であるかどうかを判定するように構成される。ラベル・スタックは空であると判定するとき、プロセッサは、送信先IPアドレスおよびフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードする。この場合、ネットワーク・ノードは、検査されるべきネットワーク・ノードであり、フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップである。
【００４５】
フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0であると判定し、ネットワーク検査デバイスがネットワーク・トポロジー情報および通知メッセージ内のフィードバック・ノードのIPアドレスに従ってネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように、通知メッセージをネットワーク検査デバイスに送信する。
【００４６】
プロセッサは、ラベル・スタックは空でないと判定するとき、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードするようにさらに構成される。この場合、ネットワーク・ノードは、中間ネットワーク・ノードであり、検査パケットが検査されるべきネットワーク・ノードに送信されるように、ラベルに従って検査パケットをフォワードし続ける。
【００４７】
第５の態様は、コンピュータ記憶媒体を提供する。コンピュータ記憶媒体は、プログラムコードを記憶し、プログラムコードは、第１の態様における上記の方法を実現するための命令を含む。
【００４８】
第６の態様は、コンピュータ記憶媒体を提供する。コンピュータ記憶媒体は、プログラムコードを記憶し、プログラムコードは、第２の態様における上記の方法を実現するための命令を含む。
【００４９】
第７の態様は、フォワーディング・テーブルを検査するためのシステムを提供する。システムは、ネットワーク検査デバイス、検査されるべきネットワーク・ノード、およびフィードバック・ノードを含む。
【００５０】
ネットワーク検査デバイスは、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1であり、ネットワーク検査デバイスは、検査パケットが検査されるべきネットワーク・ノードに送信されるように、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信するように構成される。
【００５１】
検査されるべきネットワーク・ノードは、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であると判定するとき、送信先IPアドレスおよび検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードするように構成され、フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。
【００５２】
フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0であると判定するとき、ネットワーク検査デバイスに通知メッセージを送信するように構成される。
【００５３】
ネットワーク検査デバイスは、通知メッセージを受信し、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するようにさらに構成される。具体的には、通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していると判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルが正しいと判定し得る。通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないと判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルが誤っていると判定し得る。
【００５４】
任意選択で、フォワーディング・テーブルを検査するためのシステム内のネットワーク検査デバイスと検査されるべきネットワーク・ノードの間に、１つ以上の中間ネットワーク・ノードが存在し得る。検査されるべきネットワーク・ノードが検査パケットを受信する前に、中間ネットワーク・ノードは、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算する。中間ネットワーク・ノードは、ラベル・スタックは空でないと判定し、検査されるべきネットワーク・ノードが検査パケットを受信するまで、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードし続ける。このようにして、中間ネットワーク・ノードを制御して、リンク・ラベルのみに従って検査パケットをフォワードするために、検査パケット内の特定のラベル・スタックおよび特定のTTL値が使用され、それによって、検査パケットは、検査されるべきネットワーク・ノードに送信され、検査パケットは、検査されるべきネットワーク・ノードがラベル・スタックは空であると判定するときのみ、フォワーディング・テーブルに従って、IPルート上でフォワードされる。
【００５５】
この出願において提供される技術的解決策において、検査されるべきIPアドレス行きのデータパケットが損失されるか、または誤ってフォワードされるとき、検査されるべきネットワーク・ノードのフォワーディング・テーブルは検査される必要があり、ネットワーク検査デバイスは、特定のラベル・スタックおよび特定のTTL値を含む検査パケットを生成し、検査パケットのフォワーディング経路を特定する。TTLの値は、ホップ毎に1だけ減少される。TTLの値が0であるとき、検査されるべきネットワーク・ノードの次のホップ、すなわち、フィードバック・ノードは、通知メッセージ(ICMPパケット)をネットワーク検査デバイスに送信することを可能にされる。ネットワーク検査デバイスは、検査されるべきネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを迅速に判定することができる。従って、故障の位置決めの効率が増加される。
【図面の簡単な説明】
【００５６】
【図１】この出願の実施形態による、フォワーディング・テーブルを検査するためのシステムの構造の概略図である。
【図２】この出願の実施形態による、フォワーディング・テーブルを検査するための方法の概略フローチャートである。
【図３】この出願の実施形態による、フォワーディング・テーブルを検査するための方法における情報交換の概略図である。
【図４】この出願の実施形態による、フォワーディング・テーブルを検査するための装置の構造の概略図である。
【図５】この出願の実施形態による、フォワーディング・テーブルを検査するための他の装置の構造の概略図である。
【図６】この出願の実施形態による、ネットワーク検査デバイスの構造の概略図である。
【図７】この出願の実施形態による、ネットワーク・ノードの構造の概略図である。
【図８】この出願の実施形態による、他のネットワーク・ノードの構造の概略図である。
【発明を実施するための形態】
【００５７】
この出願において提供される技術的解決策において、ネットワーク検査デバイスは、TTLおよびリンク・ラベルを含む検査パケットを生成し、ラベル・スタックを使用することによって、検査パケットのラベル・フォワーディング経路を特定し、TTLを使用することによって、検査パケットが通過するホップ数を特定し、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上の検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを検査する。具体的には、ネットワーク検査デバイスは、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルを決定し、検査パケットを生成する。検査パケットは、ラベル・スタックおよびTTLを含み、ラベル・スタックはN個のリンク・ラベル(N個のホップの順次的なリンク・ラベル)を含み、TTLの値はMに1が加えられたもの、すなわち、N+1である。検査パケットがネットワーク検査デバイスから検査されるべきネットワーク・ノードまでフォワードされるプロセスにおいて、検査パケットは、ラベル・スタック内のリンク・ラベルに従ってフォワードされる。検査パケットが検査されるべきネットワーク・ノードに到着し、ラベル・スタックが空である後、検査パケットは、検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、フォワードされる。フィードバック・ノードとも呼ばれる、検査されるべきネットワーク・ノードの次のホップは、検査パケットを受信し、TTLの値から1を減算する。結果として、検査パケット内でTTLの値が0であるので、ICMPパケットのような通知メッセージがネットワーク検査デバイスに送信される。このようにして、ネットワーク検査デバイスは、受信されたICMPパケットおよびネットワーク・トポロジー情報に従って、フォワーディング・テーブル、すなわち、検査されるべきネットワーク・ノードのFIBが誤っているかどうかを判定する。
【００５８】
ICMPは、ホストとルータの間で、報告されるエラーおよび状態情報を含む制御情報を伝送するために使用される。異なる種類のICMPパケットが存在する。例えば、ICMPエラー報告パケットは、主に、データ通信の間にエラーを送信端に報告するために使用される。ICMPエラー報告パケットのデータ領域は、一般に、誤りのあるパケットのヘッダを含むことが可能であり、誤りのあるパケット内のデータの最初の64ビットをさらに含むことが可能である。データパケット内のTTLが0であるとき、ルータは、データパケットを廃棄し、データパケットの送信者(送信端)にタイムアウトタイプ(タイプ値は11であり、コードは0である)のICMPエラー報告パケットを送信する。この出願の実施形態において、通知メッセージは、ICMPパケット、すなわち、タイプ値が11であり、コードが0であるICMPエラー報告パケットであり得る。
【００５９】
異常が起きた、言い換えると、例えば、送信先IPアドレス行きのデータパケットが損失し、または誤っているが、ネットワークは正常であるか、または故障でない(例えば、リンク故障がない)とき、この出願の実施形態において提供される、フォワーディング・テーブルを検査するための方法が、送信先IPアドレスへのフォワーディング経路上のネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを検査するために使用される。もちろん、この方法は、いつでもユーザ要件に従って、送信先IPアドレス行きのフォワーディング経路上のネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを検査するためにも使用され得る。この出願の実施形態において、送信先IPアドレスは、検査されるべきIPアドレスとも呼ばれる。
【００６０】
通常、フォワーディング経路上に複数のネットワーク・ノードが存在し、ネットワーク検査デバイスは、どのネットワーク・ノードが誤っているフォワーディング・テーブルを有するかを知らない。この場合、ネットワーク検査デバイスは、TTLが0であるとき、ネットワーク経路上の複数のネットワーク・ノードがICMPパケットをフィードバックすることを可能にするために、検査されるべきネットワーク・ノードとしてフォワーディング経路の一部であるネットワーク経路上の複数のネットワーク・ノードを順次的に使用し、TTLの昇順または降順の値およびリンク・ラベルの昇順または降順の数を有する複数の検査パケットを送信し得る。このようにして、ネットワーク検査デバイスは、ネットワーク経路上のネットワーク・ノードの各ホップのフォワーディング・テーブルが正しいかどうかを検査することができる。この出願において提供される、フォワーディング・テーブルを検査するための方法は、ネットワーク経路上の複数のネットワーク・ノードを検査することによって、誤っているフォワーディング・テーブルを有するネットワーク・ノードを位置決めし得る。これは、故障の位置決めの効率を増加させる。
【００６１】
下記は、添付図面および特定の実装を参照して、この出願の技術的解決策を詳細に説明する。
【００６２】
図１は、この出願の実施形態による、フォワーディング・テーブルを検査するためのシステムの構造の概略図である。システム100は、ネットワーク検査デバイス110およびネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路の一部であるネットワーク経路120を含む。図１に表わされたネットワーク経路120は、３つのネットワーク・ノード:R1、R2、およびR3を含む。ネットワーク検査デバイス110は、ネットワーク経路120上のいずれかのネットワーク・ノードのフォワーディング・テーブルを検査してもよく、またはネットワーク経路120上の各ネットワーク・ノードのフォワーディング・テーブルを順次的に検査してもよい。システム100は、図１に表わされたネットワーク・ノードR0およびR4のような他のネットワーク・ノードをさらに含み得る。
【００６３】
この出願の実施形態において、ネットワーク検査デバイスが検査することを準備するネットワーク・ノードは、検査されるべきネットワーク・ノードと呼ばれ、検査されるべきネットワーク・ノードの次のホップは、フィードバック・ノードと呼ばれる。ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間のフォワーディング経路上のネットワーク・ノードは、中間ネットワーク・ノードと呼ばれる。図１に表わされたシステムを参照して、ネットワーク検査デバイス110がネットワーク・ノードR1のフォワーディング・テーブルを検査するとき、ネットワーク・ノードR1は、検査されるべきネットワーク・ノードである。ネットワーク・ノードR1のフォワーディング・テーブルが正しいならば、通知メッセージを送信するフィードバック・ノードは、ネットワーク・トポロジー情報内のルートと整合している。ネットワーク・ノードR1のフォワーディング・テーブルが誤っているならば、通知メッセージを送信するフィードバック・ノードは、ネットワーク・トポロジー情報と整合していない。例えば、ネットワーク・ノードR1の次のホップは、ネットワーク・トポロジー情報内のネットワーク・ノードR2である。ネットワーク検査デバイスがネットワーク・ノードR2によって送信される通知メッセージを受信したならば、フィードバック・ノードは、ネットワーク・トポロジー情報と整合せず、ネットワーク・ノードR1のフォワーディング・テーブルは正しいと判定され得る。ネットワーク検査デバイスがネットワーク・ノードR2以外のノードによって送信される通知メッセージを受信したならば、フィードバック・ノードは、ネットワーク・トポロジー情報と整合せず、R1のフォワーディング・テーブルは誤っていると判定され得る。
【００６４】
図２は、この出願の実施形態による、フォワーディング・テーブルを検査するための方法の概略フローチャートである。この方法は、ネットワーク経路上のいずれかのネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを検査するために使用され得る。この方法は、下記のステップを含む。
【００６５】
201.ネットワーク検査デバイスは、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成し、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である。
【００６６】
送信元IPアドレスはネットワーク検査デバイスのIPアドレス、例えば、1.1.1.1である。送信先IPアドレスは、通常、ホストのIPアドレス、例えば、192.168.1.1である。
【００６７】
具体的には、ネットワーク検査デバイスは、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定する。そして、ネットワーク検査デバイスは、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数および各ホップのリンク・ラベルを決定し、検査パケットを生成する。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の各ホップのルート情報を含む。ルート情報はリンク・ラベルを含む。リンク・ラベルは、パケットのための単一ホップのフォワーディング経路を特定する。
【００６８】
この出願の実施形態において、ネットワーク検査デバイスは、まず、ネットワーク・トポロジー管理装置を使用することによって、ネットワーク・トポロジー情報を取得し得る。ネットワーク・トポロジー管理装置は、ソフトウェア・デファインド・ネットワーキング(Software-Defined Networking, 略してSDN)コントローラであり得る。特定の実装の間、ネットワーク検査デバイスおよびネットワーク・トポロジー管理装置は、同じ物理的デバイスまたは異なる物理的デバイス上に実現され得る。
【００６９】
図１に表わされたシステムは、例として使用される。ネットワーク検査デバイス110は、ネットワーク上の送信先IPアドレス192.168.1.1行きのフォワーディング経路上のネットワーク・ノードR1のフォワーディング・テーブルが正しいかどうかを検査する。すなわち、検査されるべきネットワーク・ノードはR1である。ネットワーク検査デバイス110は、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイス110からネットワーク・ノードR1までのホップ数が2(すなわち、ネットワーク検査デバイス110からR0まで、およびR0からR1まで合計で2ホップ)であると判定する。リンク・ラベルは8801および8802である。ネットワーク検査デバイス110は、２つのリンク・ラベル8801および8802を含むラベル・スタックおよび3であるTTLの値を用いて、検査パケットを生成する。
【００７０】
202.ネットワーク検査デバイスは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信する。
【００７１】
ラベル・スタックの動作は、一般に、スタックの「後入れ先出し」動作と同じである。ラベルをスタックに押し込むことは、ラベルをパケットに追加すること、およびラベル・スタックの深さを1だけ増加させることを指す。ラベルをスタックから引き出すことは、ラベルをパケットから除去することを指す。言い換えると、ラベルは取り出され、ラベル・スタックの深さは1だけ減少される。パケット内のラベルは、内から外への順序でスタックの下から上までカプセル化される。パケット・フォワーディングの間に、ラベル・スタックの一番上のラベル、すなわち、パケットの最も外側のラベルは、常に、パケットをどのようにフォワードするかを決定する。
【００７２】
具体的には、ネットワーク検査デバイスは、(Multiprotocol Label Switching, 略してMPLS)において定義されたラベル・フォワーディング方式を使用して、この出願における、フォワーディング・テーブルを検査するための方法を実現し得る。検査パケットは、MPLSパケットであり得る。もちろん、セグメント・ルーティング(segment routing)をサポートする他のリンク・ラベル・フォワーディング方式が使用され得る。これは、この出願において限定されない。
【００７３】
具体的には、ネットワーク検査デバイスは、検査パケットが検査されるべきネットワーク・ノードに送信されるように、検査パケットを次のホップのノード(これは、中間ネットワーク・ノードまたは検査されるべきネットワーク・ノードであり得る)に送信する。ステップ201における例は、ここでも使用される。ネットワーク検査デバイス110によって生成される検査パケットにおいて、ラベル・スタックの下から上への(内から外への)リンク・ラベルは8802および8801であり、TTLの値は3である。ネットワーク検査デバイス110は、ラベル・スタックの一番上のリンク・ラベル8801に従って、検査パケットを次のホップのノード、すなわち、ネットワーク・ノードR0に送信する。
【００７４】
203.ネットワーク・ノードは、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算する。
【００７５】
204.ネットワーク・ノードは、ラベル・スタックは空であるかどうかを判定する。
【００７６】
ラベル・スタックの一番上のリンク・ラベルを取り出した後、ネットワーク・ノードは、ラベル・スタックは空であるかどうか、およびラベルに従って検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で検査パケットをフォワードするかを判定する必要がある。
【００７７】
ネットワーク・ノードがラベル・スタックは空でないと判定し、それがネットワーク・ノードは中間ネットワーク・ノードであることを示すとき、ネットワーク・ノードはステップ205に進む。ネットワーク・ノードがラベル・スタックは空であると判定し、それがネットワーク・ノードは検査されるべきネットワーク・ノードであることを示すとき、ネットワーク・ノードはステップ206に進む。
【００７８】
205.ラベル・スタックは空でないと判定するとき、ネットワーク・ノードは、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードする。
【００７９】
ネットワーク・ノードがラベル・スタックは空でないと判定し、すなわち、ネットワーク・ノードが中間ネットワーク・ノードであるとき、ネットワーク・ノードは、検査パケットが検査されるべきネットワーク・ノードに送信されるように、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを次のホップのノードにフォワードする。上記の例はここでも使用される。ネットワーク・ノードR0は、ラベルは空でないと判定し、ラベル・スタックの一番上のリンク・ラベル8802に従って、検査パケットを次のホップのノード、すなわち、ネットワーク・ノードR1にフォワードする。
【００８０】
206.ラベル・スタックは空であると判定するとき、ネットワーク・ノードは、送信先IPアドレスおよびネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードする。
【００８１】
ネットワーク・ノードがラベル・スタックは空であると判定するとき、ネットワーク・ノードは検査されるべきネットワーク・ノードである。この場合、検査パケット内のTTLの値は1であることが理解されるべきである。ネットワーク・ノードは、送信先IPアドレスおよびネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードする。フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。上記の例はここでも使用される。ネットワーク・ノードR1は、ラベルは空であると判定し、送信先IPアドレスおよびネットワーク・ノードR1のフォワーディング・テーブルに従って、検査パケットをフィードバック・ノード、すなわち、ネットワーク・ノードR2にフォワードする。
【００８２】
207.フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0であると判定するとき、ネットワーク検査デバイスに通知メッセージを送信する。
【００８３】
通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用される。通知メッセージは、フィードバック・ノードのIPアドレスを含む。
【００８４】
通知メッセージは、具体的には、ICMPパケットであり得る。もちろん、既存のメッセージが拡張されてもよく、または通知メッセージの機能が適用される限り、新しいメッセージが作り出されてもよい。これはこの出願において限定されない。
【００８５】
フィードバック・ノードは、検査パケットを受信し、TTLの値から1を減算し、TTLの値は0である。従って、フィードバック・ノードは、通知メッセージをネットワーク検査デバイスに送信して、フィードバック・ノードが検査パケットを受信したことをネットワーク検査デバイスに通知する。この出願の実施形態において、ラベル・スタックおよびTTLの値が設定されるので、ネットワーク検査デバイスによって生成される検査パケットは、リンク・ラベルに従って、ホップ毎に、検査されるべきネットワーク・ノードにフォワードされ、検査パケットが検査されるべきネットワーク・ノードによって処理された後、ラベル・スタックは空であり、TTLの値は1である。検査パケットがフィードバック・ノードによって処理され(TTLの値から1が減算され)、TTLの値が0である後、フィードバック・ノードは、通知メッセージをネットワーク検査デバイスに送信することを可能にされる。
【００８６】
208.ネットワーク検査デバイスは、通知メッセージを受信し、通知メッセージおよびネットワーク・トポロジー情報に従って、ネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定する。
【００８７】
具体的には、通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していると判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルが正しいと判定し得る。通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないと判定するとき、ネットワーク検査デバイスは、ネットワーク・ノードのフォワーディング・テーブルが誤っていると判定し得る。
【００８８】
この出願において提供される技術的解決策において、検査パケットは、ラベルに従って、フォワードされ、そして、検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、IPルート上でフォワードされる。検査パケットがホップを通過する毎にTTLの値は1だけ減少されるので、フィードバック・ノードによって処理された(TTLの値から1が減算された)後、TTLの値が0であり、フィードバック・ノードが、ICMPパケットをネットワーク検査デバイスに送信することを可能にされるように、TTLの適切な値が設定される。ICMPパケットを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合しているならば、検査されるべきネットワーク・ノードのフォワーディング・テーブルは正しいと判定され得る。ICMPパケットを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないならば、検査されるべきネットワーク・ノードのフォワーディング・テーブルは誤っていると判定され得る。
【００８９】
ICMPパケットは、検査パケットのヘッダを含み、従って、ネットワーク検査デバイスは、受信されたICMPパケットが、検査パケット・タイムアウト・エラー(TTLの値は0である)を報告するために、フィードバック・ノードによって使用されていると判定し得る。
【００９０】
ネットワーク検査デバイスがフォワーディング経路上の複数のネットワーク・ノードのフォワーディング・テーブルを検査する必要があるとき、ネットワーク検査デバイスは、TTLの昇順または降順の値およびリンク・ラベルの昇順または降順の数を有する複数の検査パケットを順次的に送信することが可能であり、図２に表わされた検査パケットのための方法を繰り返し実行して、フォワーディング経路上の複数のネットワーク・ノードのフォワーディング・テーブルを検査し、誤っているフォワーディング・テーブルを有するネットワーク・ノードを位置決めすることが可能である。
【００９１】
図１に表わされたシステムを参照して、この出願の実施形態は、ネットワーク検査デバイス110から送信先IPアドレスまでのフォワーディング経路の一部であるネットワーク経路120上の３つのネットワーク・ノードR1、R2、およびR3のフォワーディング・テーブルを順次的に検査するための方法を提供する。ネットワーク経路120は、顧客要件、ネットワーク配備状態(重み付け、帯域幅、または同様のもの)、またはデータパケット・フォワーディング例外に従って、分析により決定され得る。図３に表わされた、フォワーディング・テーブルを検査するための方法における情報交換の概略図を参照すると、この方法は、下記のステップを含む。
【００９２】
301-1.ネットワーク検査デバイス110は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、第１の検査パケットを生成し、第１の検査パケットのヘッダは、第１のラベル・スタック、第１のTTL、送信元IPアドレス、および送信先IPアドレスを含む。
【００９３】
具体的には、ネットワーク検査デバイス110は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路のネットワーク経路120を決定する。
【００９４】
ネットワーク検査デバイス110は、まず、ネットワーク経路120上のネットワーク・ノードR1のフォワーディング・テーブルが誤っているかどうかを検査する。すなわち、ネットワーク・ノードR1は、検査されるべきネットワーク・ノードである。
【００９５】
ネットワーク検査デバイス110は、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイス110からネットワーク・ノードR1までのホップ数が2(すなわち、ネットワーク検査デバイス110からネットワーク・ノードR0まで、およびネットワーク・ノードR0からネットワーク・ノードR1まで合計で2ホップ)であると判定する。リンク・ラベルは8801および8802である。ネットワーク検査デバイス110は、第１の検査パケットを生成し、Nは2である。図３に表わされているように、第１のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)２つのリンク・ラベル:第２のリンク・ラベル8802および第１のリンク・ラベル8801を含む。第１のTTLの値は3である。
【００９６】
送信先IPアドレス、すなわち、検査されるべきIPアドレスは、例えば192.168.1.1である。送信元IPアドレスは、ネットワーク検査デバイス110のIPアドレス、例えば、1.1.1.1である。
【００９７】
302-1.ネットワーク検査デバイス110は、第１のラベル・スタックの一番上の第１のリンク・ラベル(8801)に従って、第１の検査パケットを送信する。
【００９８】
具体的には、ネットワーク・ノードR0は、フォワーディング経路上のネットワーク検査デバイスの次のホップのノードである。ネットワーク検査デバイス110は、第１のラベル・スタックの一番上の第１のリンク・ラベル8801に従って、第１の検査パケットをネットワーク・ノードR0に送信する。
【００９９】
303-1.ネットワーク・ノードR0は、第１の検査パケットを受信し、第１のラベル・スタックの一番上の第１のリンク・ラベル(8801)を取り出し、第１のTTLの値から1を減算する。
【０１００】
第１の検査パケットがネットワーク・ノードR0によって処理された後、第１のラベル・スタックは、１つのリンク・ラベル、すなわち、第２のリンク・ラベル8802を含み、第１のTTLの値は2である。この場合、第１のラベル・スタックの一番上のラベルは、第２のリンク・ラベル8802である。
【０１０１】
そして、ネットワーク・ノードR0は、第１のラベル・スタックは空であるかどうかを判定して、ラベルに従って第１の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第１の検査パケットをフォワードするかを決定する必要がある。
【０１０２】
304-1.ネットワーク・ノードR0は、第１のラベル・スタックは空でないと判定し、第１のラベル・スタックの一番上の第２のリンク・ラベル(8802)に従って、第１の検査パケットをネットワーク・ノードR1に送信する。
【０１０３】
ネットワーク・ノードR0が第１のラベル・スタックは空でないと判定するならば、それは、ネットワーク・ノードR0が中間ネットワーク・ノードであることを示す。ネットワーク・ノードR0は、第１の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR1にフォワードし続ける。
【０１０４】
305-1.ネットワーク・ノードR1は、第１の検査パケットを受信し、第１のラベル・スタックの一番上の第２のリンク・ラベル(8802)を取り出し、第１のTTLの値から1を減算する。
【０１０５】
第１の検査パケットがネットワーク・ノードR1によって処理された後、第１のラベル・スタックは空であり(リンク・ラベルは存在しない)、第１のTTLの値は1である。
【０１０６】
そして、ネットワーク・ノードR1は、第１のラベル・スタックは空であるかどうかを判定して、ラベルに従って第１の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第１の検査パケットをフォワードするかを決定する必要がある。
【０１０７】
306-1.ネットワーク・ノードR1は、第１のラベル・スタックは空であると判定し、送信先IPアドレスおよびネットワーク・ノードR1のフォワーディング・テーブルに従って、第１の検査パケットをネットワーク・ノードR2にフォワードする。
【０１０８】
ネットワーク・ノードR1が第１のラベル・スタックは空であると判定するならば、それは、ネットワーク・ノードR1が検査されるべきネットワーク・ノードであることを示す。ネットワーク・ノードR1は、送信先IPアドレスおよびネットワーク・ノードR1のフォワーディング・テーブルに従って、IPルート上で第１の検査パケットをフォワードし、第１の検査パケットをネットワーク・ノードR1の次のホップ、すなわち、フィードバック・ノードにフォワードする。
【０１０９】
307-1.ネットワーク・ノードR2は、第１の検査パケットを受信し、第１のTTLの値から1を減算し、第１のTTLの値は0であると判定し、第１のICMPパケットをネットワーク検査デバイス110に送信する。
【０１１０】
ネットワーク・ノードR2が第１のTTLの値は0であると判定するならば、フィードバック・ノードとしてのネットワーク・ノードR2は、第１のICMPパケットを生成し、それをネットワーク検査デバイス110に送信する。第１のICMPパケットは、ネットワーク・ノードR2のIPアドレスを含む。第１のICMPパケットは、第１の検査パケットのヘッダ(送信元IPアドレスおよび送信先IPアドレス)を搬送する。従って、ネットワーク検査デバイスは、受信された第１のICMPパケットが、第１の検査パケット・タイムアウト・エラー(TTLの値は0である)を報告するために、ネットワーク・ノードR2によって使用されていると判定し得る。
【０１１１】
ネットワーク・トポロジー情報内のネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上のネットワーク・ノードR1の次のホップはネットワーク・ノードR2であると仮定する。ネットワーク・ノードR2が第１の検査パケットを受信し、第１のICMPパケットをネットワーク検査デバイスに送信する、すなわち、ネットワーク・ノードR2がフィードバック・ノードであるならば、それは、検査されるべきネットワーク・ノード、すなわち、ネットワーク・ノードR1のフォワーディング・テーブルは正しいことを示す。ネットワーク・ノードR2とは異なる他のノードが第１の検査パケットを受信するならば、他のノードは、第１のICMPパケットをネットワーク検査デバイスに送信し、すなわち、他のノードは、フィードバック・ノード(図３に表わされていない)であり、それは、ネットワーク・ノードR1のフォワーディング・テーブルは誤っていることを示す。
【０１１２】
308-1.ネットワーク検査デバイス110は、ネットワーク・ノードR2によって送信される第１のICMPパケットを受信し、第１のICMPパケットおよびネットワーク・トポロジー情報に従って、ネットワーク・ノードR1のフォワーディング・テーブルが正しいかどうかを判定する。
【０１１３】
具体的には、ネットワーク検査デバイスは、ネットワーク・トポロジー情報および第１のICMPパケット内のネットワーク・ノードR2のIPアドレスに従って、フォワーディング・テーブルが正しいかどうかを判定する。ネットワーク・トポロジー情報内のネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上のネットワーク・ノードR1(すなわち、検査されるべきネットワーク・ノード)の次のホップがネットワーク・ノードR2である、すなわち、第１のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR2)がネットワーク・トポロジー情報と整合していると判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR1のフォワーディング・テーブルは正しいと判定し得る。ネットワーク・トポロジー情報内のフォワーディング経路上のネットワーク・ノードR1の次のホップがネットワーク・ノードR2でない、すなわち、第１のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR2)がネットワーク・トポロジー情報と整合していないと判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR1のフォワーディング・テーブルは誤っていると判定し得る。
【０１１４】
そして、ネットワーク検査デバイス110は、ネットワーク経路120上のネットワーク・ノードR2のフォワーディング・テーブルが誤っているかどうかを検査し続ける必要がある。
【０１１５】
301-2.ネットワーク検査デバイス110は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、第２の検査パケットを生成し、第２の検査パケットは、第２のラベル・スタック、第２のTTL、送信元IPアドレス、および送信先IPアドレスを含む。
【０１１６】
具体的には、ネットワーク検査デバイス110は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイス110からネットワーク・ノードR2(検査されるべきネットワーク・ノード)までのホップ数は3(すなわち、ネットワーク検査デバイス110からネットワーク・ノードR0まで、ネットワーク・ノードR0からネットワーク・ノードR1まで、およびネットワーク・ノードR1からネットワーク・ノードR2まで合計で3ホップ)であると判定する。リンク・ラベルは8801、8802、および8803である。ネットワーク検査デバイス110は、第２の検査パケットを生成し、Nは3である。図３に表わされているように、第２のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)３つのリンク・ラベル:第３のリンク・ラベル8803、第２のリンク・ラベル8802、および第１のリンク・ラベル8801を含む。第２のTTLの値は4である。
【０１１７】
第２の検査パケットおよび第１の検査パケットは、同じ送信元IPアドレスおよび同じ送信先IPアドレスを有する。
【０１１８】
302-2.ネットワーク検査デバイス110は、第２のラベル・スタックの一番上の第１のリンク・ラベル(8801)に従って、第２の検査パケットを送信する。
【０１１９】
具体的には、ネットワーク検査デバイス110は、第２のラベル・スタックの一番上の第１のリンク・ラベル8801に従って、第２の検査パケットを次のホップのノード、すなわち、ネットワーク・ノードR0に送信する。
【０１２０】
303-2.ネットワーク・ノードR0は、第２の検査パケットを受信し、第２のラベル・スタックの一番上の第１のリンク・ラベル(8801)を取り出し、第２のTTLの値から1を減算する。
【０１２１】
第２の検査パケットがネットワーク・ノードR0によって処理された後、第２のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)２つのリンク・ラベル:第３のリンク・ラベル8803および第２のリンク・ラベル8802を含む。第２のTTLの値は3である。この場合、第２のラベル・スタックの一番上のラベルは、第２のリンク・ラベル8802である。
【０１２２】
そして、ネットワーク・ノードR0は、第２のラベル・スタックは空であるかどうかを判定して、ラベルに従って第２の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第２の検査パケットをフォワードするかを決定する必要がある。
【０１２３】
304-2.ネットワーク・ノードR0は、第２のラベル・スタックは空でないと判定し、第２のラベル・スタックの一番上の第２のリンク・ラベル(8802)に従って、第２の検査パケットをネットワーク・ノードR1に送信する。
【０１２４】
ネットワーク・ノードR0が第２のラベル・スタックは空でないと判定するならば、それは、ネットワーク・ノードR0は中間ネットワーク・ノードであることを示す。ネットワーク・ノードR0は、ラベル・スタックの一番上の第２のリンク・ラベル(8802)に従って、第２の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR1にフォワードし続ける。
【０１２５】
305-2.ネットワーク・ノードR1は、第２の検査パケットを受信し、第２のラベル・スタックの一番上の第２のリンク・ラベル(8802)を取り出し、第２のTTLの値から1を減算する。
【０１２６】
第２の検査パケットがネットワーク・ノードR1によって処理された後、第２のラベル・スタックは、１つのリンク・ラベル、すなわち、第３のリンク・ラベル8803を含み、第２のTTLの値は2である。この場合、第２のラベル・スタックの一番上のラベルは、第３のリンク・ラベル8803である。
【０１２７】
そして、ネットワーク・ノードR1は、第２のラベル・スタックは空であるかどうかを判定して、ラベルに従って第２の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第２の検査パケットをフォワードするかを決定する必要がある。
【０１２８】
306-2.ネットワーク・ノードR1は、第２のラベル・スタックは空でないと判定し、第２のラベル・スタックの一番上の第３のリンク・ラベル(8803)に従って、第２の検査パケットをネットワーク・ノードR2に送信する。
【０１２９】
ネットワーク・ノードR1が第２のラベル・スタックは空でないと判定するならば、それは、ネットワーク・ノードR1は、また、中間ネットワーク・ノードであることを示す。ネットワーク・ノードR1は、第２のラベル・スタックの一番上の第３のリンク・ラベル(8803)に従って、第２の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR2にフォワードし続ける。
【０１３０】
307-2.ネットワーク・ノードR2は、第２の検査パケットを受信し、第２のラベル・スタックの一番上の第３のリンク・ラベル(8803)を取り出し、第２のTTLの値から1を減算する。
【０１３１】
第２の検査パケットがネットワーク・ノードR2によって処理された後、第２のラベル・スタックは空であり、第２のTTLの値は1である。
【０１３２】
そして、ネットワーク・ノードR2は、第２のラベル・スタックは空であるかどうかを判定して、ラベルに従って第２の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第２の検査パケットをフォワードするかを決定する必要がある。
【０１３３】
308-2.ネットワーク・ノードR2は、第２のラベル・スタックは空であると判定し、送信先IPアドレスおよびネットワーク・ノードR2のフォワーディング・テーブルに従って、第２の検査パケットをネットワーク・ノードR3にフォワードする。
【０１３４】
ネットワーク・ノードR2が第２のラベル・スタックは空であると判定するならば、それは、ネットワーク・ノードR2は検査されるべきネットワーク・ノードであることを示す。ネットワーク・ノードR2は、そのフォワーディング・テーブルおよび送信先IPアドレスに従って、IPルート上で第２の検査パケットをフォワードし、第２の検査パケットをその次のホップ、すなわち、フィードバック・ノードにフォワードする。
【０１３５】
309-2.ネットワーク・ノードR3は、第２の検査パケットを受信し、第２のTTLの値から1を減算し、第２のTTLの値は0であると判定し、第２のICMPパケットをネットワーク検査デバイスに送信する。
【０１３６】
ネットワーク・ノードR3、すなわち、フィードバック・ノードは、第２の検査パケットを受信し、第２のTTLの値から1を減算する。ネットワーク・ノードR3が第２のTTLの値は0であると判定するならば、ネットワーク・ノードR3は、第２のICMPパケットを生成し、それをネットワーク検査デバイス110に送信する。第２のICMPパケットは、ネットワーク・ノードR3のIPアドレスを含む。第２のICMPパケットは、第２の検査パケットのヘッダ(送信元IPアドレスおよび送信先IPアドレス)をさらに搬送する。従って、ネットワーク検査デバイスは、受信された第２のICMPパケットが、第２の検査パケット・タイムアウト・エラー(TTLの値は0である)を報告するために、ネットワーク・ノードR3によって使用されていると判定し得る。
【０１３７】
310-2.ネットワーク検査デバイス110は、ネットワーク・ノードR3によって送信される第２のICMPパケットを受信し、第２のICMPパケットおよびネットワーク・トポロジー情報に従って、ネットワーク・ノードR2のフォワーディング・テーブルが正しいかどうかを判定する。
【０１３８】
具体的には、ネットワーク検査デバイスは、ネットワーク・トポロジー情報および第２のICMPパケット内のネットワーク・ノードR3のIPアドレスに従って、フォワーディング・テーブルが正しいかどうかを判定する。ネットワーク・トポロジー情報内のネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上のネットワーク・ノードR2(すなわち、検査されるべきネットワーク・ノード)の次のホップは、ネットワーク・ノードR3である、すなわち、第２のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR3)はネットワーク・トポロジー情報と整合していると判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR2のフォワーディング・テーブルは正しいと判定し得る。ネットワーク・トポロジー情報内のフォワーディング経路上のネットワーク・ノードR2の次のホップは、ネットワーク・ノードR3でない、すなわち、第２のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR3)はネットワーク・トポロジー情報と整合していないと判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR2のフォワーディング・テーブルは誤っていると判定し得る。
【０１３９】
そして、ネットワーク検査デバイス110は、ネットワーク経路120上のネットワーク・ノードR3のフォワーディング・テーブルが誤っているかどうかを検査し続ける。
【０１４０】
301-3.ネットワーク検査デバイス110は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、第３の検査パケットを生成し、第３の検査パケットは、第３のラベル・スタック、第３のTTL、送信元IPアドレス、および送信先IPアドレスを含む。
【０１４１】
具体的には、ネットワーク検査デバイス110は、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイス110からネットワーク・ノードR3(検査されるべきネットワーク・ノード)までのホップ数は4(すなわち、ネットワーク検査デバイス110からネットワーク・ノードR0まで、ネットワーク・ノードR0からネットワーク・ノードR1まで、ネットワーク・ノードR1からネットワーク・ノードR2まで、およびネットワーク・ノードR2からネットワーク・ノードR3まで合計で4ホップ)であると判定する。リンク・ラベルは8801、8802、8803、および8804である。ネットワーク検査デバイス110は、第３の検査パケットを生成し、Nは4である。図３に表わされているように、第３のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)４つのリンク・ラベル:第４のリンク・ラベル8804、第３のリンク・ラベル8803、第２のリンク・ラベル8802、および第１のリンク・ラベル8801を含む。第３のTTLの値は5である。
【０１４２】
第３の検査パケット、第１の検査パケット、および第２の検査パケットは、同じ送信元IPアドレス(すなわち、ネットワーク検査デバイスのIPアドレス)および同じ送信先IPアドレス(すなわち、検査されるべきIPアドレス)を有する。
【０１４３】
302-3.ネットワーク検査デバイス110は、第３のラベル・スタックの一番上の第１のリンク・ラベル(8801)に従って、第３の検査パケットをネットワーク・ノードR0に送信する。
【０１４４】
303-3.ネットワーク・ノードR0は、第３の検査パケットを受信し、第３のラベル・スタックの一番上の第１のリンク・ラベル(8801)を取り出し、第３のTTLの値から1を減算する。
【０１４５】
第３の検査パケットがネットワーク・ノードR0によって処理された後、第３のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)３つのリンク・ラベル:第４のリンク・ラベル8804、第３のリンク・ラベル8803、および第２のリンク・ラベル8802を含む。第３のTTLの値は4である。この場合、第３のラベル・スタックの一番上のラベルは、第２のリンク・ラベル8802である。
【０１４６】
そして、ネットワーク・ノードR0は、第３のラベル・スタックは空であるかどうかを判定して、ラベルに従って第３の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第３の検査パケットをフォワードするかを決定する必要がある。
【０１４７】
304-3.ネットワーク・ノードR0は、第３のラベル・スタックは空でないと判定し、第３のラベル・スタックの一番上の第２のリンク・ラベル(8802)に従って、第３の検査パケットをネットワーク・ノードR1に送信する。
【０１４８】
中間ネットワーク・ノードとしてのネットワーク・ノードR0は、第３の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR1にフォワードし続ける。
【０１４９】
305-3.ネットワーク・ノードR1は、第３の検査パケットを受信し、第３のラベル・スタックの一番上の第２のリンク・ラベル(8802)を取り出し、第３のTTLの値から1を減算する。
【０１５０】
第３の検査パケットがネットワーク・ノードR1によって処理された後、第３のラベル・スタックは、ラベル・スタックの下から上へ(内から外へ)２つのリンク・ラベル:第４のリンク・ラベル8804および第３のリンク・ラベル8803を含む。第３のTTLの値は3である。この場合、第３のラベル・スタックの一番上のラベルは、第３のリンク・ラベル8803である。
【０１５１】
そして、ネットワーク・ノードR1は、第３のラベル・スタックは空であるかどうかを判定して、ラベルに従って第３の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第３の検査パケットをフォワードするかを決定する必要がある。
【０１５２】
306-3.ネットワーク・ノードR1は、第３のラベル・スタックは空でないと判定し、第３のラベル・スタックの一番上の第３のリンク・ラベル(8803)に従って、第３の検査パケットをネットワーク・ノードR2に送信する。
【０１５３】
中間ネットワーク・ノードとしてのネットワーク・ノードR1は、第３の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR2にフォワードし続ける。
【０１５４】
307-3.ネットワーク・ノードR2は、第３の検査パケットを受信し、第３のラベル・スタックの一番上の第３のリンク・ラベル(8803)を取り出し、第３のTTLの値から1を減算する。
【０１５５】
第３の検査パケットがネットワーク・ノードR2によって処理された後、第３のラベル・スタックは、１つのリンク・ラベル、すなわち、第４のリンク・ラベル8804を含み、第３のTTLの値は2である。この場合、第３のラベル・スタックの一番上のラベルは、第４のリンク・ラベル8804である。
【０１５６】
そして、ネットワーク・ノードR2は、第３のラベル・スタックは空であるかどうかを判定して、ラベルに従って第３の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第３の検査パケットをフォワードするかを決定する必要がある。
【０１５７】
308-3.ネットワーク・ノードR2は、第３のラベル・スタックは空でないと判定し、第３のラベル・スタックの一番上の第４のリンク・ラベル(8804)に従って、第３の検査パケットをネットワーク・ノードR3に送信する。
【０１５８】
中間ネットワーク・ノードとしてネットワーク・ノードR2は、第３の検査パケットをその次のホップのノード、すなわち、ネットワーク・ノードR3にフォワードし続ける。
【０１５９】
309-3.ネットワーク・ノードR3は、第３の検査パケットを受信し、第３のラベル・スタックの一番上の第４のリンク・ラベル(8804)を取り出し、第３のTTLの値から1を減算する。
【０１６０】
第３の検査パケットがネットワーク・ノードR3によって処理された後、第３のラベル・スタックは空であり、第３のTTLの値は1である。
【０１６１】
そして、ネットワーク・ノードR3は、第３のラベル・スタックが空であるかどうかを判定して、ラベルに従って第３の検査パケットをフォワードし続けるか、またはフォワーディング・テーブルに従ってIPルート上で第３の検査パケットをフォワードするかを決定する必要がある。
【０１６２】
310-3.ネットワーク・ノードR3は、第３のラベル・スタックは空であると判定し、送信先IPアドレスおよびネットワーク・ノードR3のフォワーディング・テーブルに従って、第３の検査パケットをネットワーク・ノードR4にフォワードする。
【０１６３】
ネットワーク・ノードR3が第３のラベル・スタックは空であると判定するならば、それはネットワーク・ノードR3が検査されるべきネットワーク・ノードであることを示す。ネットワーク・ノードR3は、送信先IPアドレスおよびネットワーク・ノードR3のフォワーディング・テーブルに従って、IPルート上で第３の検査パケットをフォワードし、第３の検査パケットをネットワーク・ノードR3の次のホップ、すなわち、フィードバック・ノードにフォワードする。
【０１６４】
311-3.ネットワーク・ノードR4は、第３の検査パケットを受信し、第３のTTLの値から1を減算し、第３のTTLの値が0であると判定し、第３のICMPパケットをネットワーク検査デバイスに送信する。
【０１６５】
ネットワーク・ノードR4が第３のTTLの値は0であると判定するならば、検査されるべきネットワーク・ノードの次のホップのノード、すなわち、フィードバック・ノードとしてのネットワーク・ノードR4は、第３のICMPパケットを生成し、それをネットワーク検査デバイス110に送信する。第３のICMPパケットは、ネットワーク・ノードR4のIPアドレスを含む。第３のICMPパケットは、第３の検査パケットのヘッダをさらに含み、従って、ネットワーク検査デバイスは、受信された第３のICMPパケットが、第３の検査パケット・タイムアウト・エラー(TTLの値は0である)を報告するために、ネットワーク・ノードR2によって使用されていると判定し得る。
【０１６６】
ネットワーク・トポロジー情報内のフォワーディング経路上のネットワーク・ノードR3の次のホップがネットワーク・ノードR4であると仮定する。ネットワーク・ノードR4が第３の検査パケットを受信し、第３のICMPパケットをネットワーク検査デバイスに送信する、すなわち、ネットワーク・ノードR4がフィードバック・ノードであるならば、それは検査されるべきネットワーク・ノード、すなわち、ネットワーク・ノードR3のフォワーディング・テーブルが正しいことを示す。ネットワーク・ノードR4とは異なる他のノードが第３の検査パケットを受信するならば、他のノードは、第３のICMPパケットをネットワーク検査デバイスに送信し、すなわち、他のノードは、フィードバック・ノードであり(図３に表わされていない)、それはネットワーク・ノードR3のフォワーディング・テーブルが誤っていることを示す。
【０１６７】
312-3.ネットワーク検査デバイス110は、ネットワーク・ノードR4によって送信される第３のICMPパケットを受信し、第３のICMPパケットおよびネットワーク・トポロジー情報に従って、ネットワーク・ノードR3のフォワーディング・テーブルが正しいかどうかを判定する。
【０１６８】
具体的には、ネットワーク検査デバイスは、ネットワーク・トポロジー情報および第３のICMPパケット内のネットワーク・ノードR4のIPアドレスに従って、フォワーディング・テーブルが正しいかどうかを判定する。ネットワーク・トポロジー情報内のネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上のネットワーク・ノードR3(すなわち、検査されるべきネットワーク・ノード)のネットワーク経路上の次のホップがネットワーク・ノードR4である、すなわち、第３のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR4)がネットワーク・トポロジー情報と整合していると判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR3のフォワーディング・テーブルが正しいと判定し得る。ネットワーク・トポロジー情報内のフォワーディング経路上のネットワーク・ノードR3の次のホップがネットワーク・ノードR4でない、すなわち、第３のICMPパケットを送信するフィードバック・ノード(ネットワーク・ノードR4)がネットワーク・トポロジー情報と整合していないと判定するならば、ネットワーク検査デバイスは、ネットワーク・ノードR3のフォワーディング・テーブルが誤っている、すなわち、エラーを有すると判定し得る。
【０１６９】
この出願の実施形態における、フォワーディング・テーブルを検査するための方法において、ネットワーク検査デバイスは、検査パケットのフォワーディング経路を特定するために、ネットワーク・トポロジー情報に従って、特定のリンク・ラベルおよび特定のTTL値を含む検査パケットを生成する。TTLの値は、ホップ毎に1だけ減少される。TTLの値が0であるとき、検査されるべきノードの次のホップ、すなわち、フィードバック・ノードは、通知メッセージ(ICMPパケット)をネットワーク検査デバイスに送信することをトリガされる。この方法は、検査されるべきIPアドレス行きのネットワーク経路上のいずれか１つ以上のネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを検査し得る。従って、故障の位置決めの効率が増加される。
【０１７０】
図３に表わされた、フォワーディング・テーブルを検査するプロセスにおいて、各ノードのフォワーディング・テーブルが正しいかどうかは、フォワーディング経路のネットワーク経路120上のノードの順序に従って、順次的に検査されてもよく、または、もちろん、逆の順序で検査されてもよく、またはいずれか１つ以上のネットワーク・ノードが、フォワーディング・テーブルが正しいかどうかを検査するために選択されてもよい。これは、この出願において限定されない。
【０１７１】
この出願の図２および図３に表わされた実施形態において提供される、フォワーディング・テーブルを検査するための方法に基づいて、下記は、ネットワーク検査デバイスの機能を提供する、フォワーディング・テーブルを検査するための装置およびネットワーク検査デバイスを詳細に説明する。
【０１７２】
図４を参照すると、図４は、この出願の実施形態による、フォワーディング・テーブルを検査するための装置400を表わす。装置400は、ネットワーク検査デバイス上に配置されることが可能であり、この出願の図２および図３に表わされた実施形態における、フォワーディング・テーブルを検査するための方法を実現するように構成される。装置400は、
送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成されたパケット生成モジュール401であって、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、Nは1以上の正の整数である(N≧1と表記され得る)、パケット生成モジュール401と、
ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信する、具体的には、検査パケットをネットワーク検査デバイスの次のホップのノードに送信するように構成された送信モジュール402であって、ネットワーク検査デバイスの次のホップのノードは、中間ネットワーク・ノードまたは検査されるべきネットワーク・ノードであり得る、送信モジュール402と、
通知メッセージを受信するように構成された受信モジュール403であって、通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用され、フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである、受信モジュール403と、
通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成された判定モジュール404と、を含む。
【０１７３】
図５に表わされているように、装置400は、ネットワーク・トポロジー情報を取得するように構成されたトポロジー取得モジュール405をさらに含む。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の各ホップのルート情報を含む。ルート情報はリンク・ラベルを含む。
【０１７４】
トポロジー取得モジュール405は、まず、ネットワーク・トポロジー管理装置を使用することによって、ネットワーク・トポロジー情報を取得し得る。ネットワーク・トポロジー管理装置は、SDNコントローラであり得る。特定の実装の間、装置400およびネットワーク・トポロジー管理装置は、同じ物理的デバイスまたは異なる物理的デバイス上に実現され得る。
【０１７５】
パケット生成モジュール401は、具体的には、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の検査されるべきネットワーク・ノードを決定し、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルを決定し、ホップ数Nおよび各ホップのリンク・ラベルに従って、検査パケットを生成するように構成される。
【０１７６】
検査されるべきネットワーク・ノードは、検査パケットを受信し、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であると判定し、すなわち、検査パケット内のTTLの値は1であると理解されることが可能であり、送信先IPアドレスおよび検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、IPルート上で検査パケットをフィードバック・ノードにフォワードする。フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップである。
【０１７７】
通知メッセージは、フィードバック・ノードのIPアドレスを含み、検査パケット内のTTLの値が0であるとき、フィードバック・ノードによって送信される。具体的には、フィードバック・ノードは、検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信し、TTLの値から1を減算する。結果として、TTLの値は0であり、フィードバック・ノードは、通知メッセージ、例えば、ICMPパケットをネットワーク検査デバイスに送信することを可能にされる。
【０１７８】
判定モジュール404は、具体的には、ネットワーク・トポロジー情報および通知メッセージ内のフィードバック・ノードのIPアドレスに従って、通知メッセージを送信するフィードバック・ノードがネットワーク・トポロジー情報内のルートと整合しているかどうかを判定するように構成される。フィードバック・ノードがネットワーク・トポロジー情報内のルートと整合しているとき、判定モジュール404は、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいと判定する。フィードバック・ノードがネットワーク・トポロジー情報内のルートと整合していないとき、判定モジュール404は、検査されるべきネットワーク・ノードのフォワーディング・テーブルが誤っていると判定する。
【０１７９】
図６を参照すると、図６は、この出願の実施形態によって提供されるネットワーク検査デバイス600を表わす。ネットワーク検査デバイス600は、この出願の図２および図３に表わされた実施形態における、フォワーディング・テーブルを検査するための方法を実現するように構成される。ネットワーク検査デバイスは、プロセッサ601、メモリ602、および通信インタフェース603を含む。
【０１８０】
プロセッサ601、メモリ602、および通信インタフェース603は、バス604を使用することによって互いに接続される。バス604は、ペリフェラル・コンポーネント・インターコネクト(peripheral component interconnect, 略してPCI)バス、拡張業界標準アーキテクチャ(extended industry standard architecture, 略してEISA)バス、または同様のものであり得る。バスは、アドレスバス、データバス、制御バス、および同様のものに分類され得る。表現の容易さのために、図６においてバスを表現するために１つのみの太線が使用されているが、これは、１つのみのバスまたは１種類のみのバスが存在することを意味しない。
【０１８１】
メモリ602は、ネットワーク・トポロジー情報を記憶するように構成される。ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の各ホップのルート情報を含む。ルート情報はリンク・ラベルを含む。
【０１８２】
プロセッサ601は、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、TTLの値はN+1であり、送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nはネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1であり、プロセッサ601は、通信インタフェース603を使用することによって、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを送信し、通信インタフェース603を使用することによって、フィードバック・ノードによって送信される通知メッセージを受信するように構成され、通知メッセージは、フィードバック・ノードが検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことをネットワーク検査デバイスに通知するために使用され、プロセッサ601は、通知メッセージおよびネットワーク・トポロジー情報に従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成される。フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。
【０１８３】
プロセッサ601は、具体的には、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルを決定し、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルに従って、検査パケットを生成するように構成される。
【０１８４】
プロセッサ601は、ネットワーク・トポロジー情報を取得するようにさらに構成される。具体的には、プロセッサ601は、ネットワーク・トポロジー管理装置を使用することによって、ネットワーク・トポロジー情報を取得し得る。ネットワーク・トポロジー管理装置は、SDNコントローラであり得る。特定の実装の間、ネットワーク検査デバイスおよびネットワーク・トポロジー管理装置は、同じ物理的デバイスまたは異なる物理的デバイス上に実現され得る。
【０１８５】
メモリ602は、揮発性メモリ(英語: volatile memory)、例えば、ランダム・アクセス・メモリ(英語: random-access memory, 略してRAM)を含み得る。メモリ602は、不揮発性メモリ(英語: non-volatile memory)、例えば、フラッシュメモリ(英語: flash memory)、ハードディスク(英語: hard disk drive, 略してHDD)、またはソリッド・ステート・ドライブ(英語: solid-state drive, 略してSSD)を含み得る。メモリ602は、上記の種類のメモリの組み合わせを含み得る。
【０１８６】
この出願の実施形態において、通信インタフェース603は、ネットワーク検査デバイス600とネットワーク内の他のネットワーク・ノードの間の通信のためのインタフェースを表現し、１つ以上の通信インタフェースが存在し得る。説明の容易さのために、通信インタフェース603が、この出願において使用されるが、これは、この出願における技術的解決策を限定しない。
【０１８７】
プロセッサ601は、中央処理ユニット(英語: central processing unit, 略してCPU)、ネットワーク・プロセッサ(英語: network processor, 略してNP)、またはCPUとNPの組み合わせであり得る。プロセッサ601は、ハードウェア・チップをさらに含み得る。ハードウェア・チップは、特定用途向け集積回路(英語: application-specific integrated circuit, 略してASIC)、プログラマブル・ロジック・デバイス(英語: programmable logic device, 略してPLD)、またはそれらの組み合わせであり得る。PLDは、複雑プログラマブル・ロジック・デバイス(英語: complex programmable logic device, 略してCPLD)、フィールド・プログラマブル・ゲートアレイ(英語: field-programmable gate array, 略してFPGA)、ジェネリック・アレイ・ロジック(英語: generic array logic, 略してGAL)デバイス、またはそれらのいずれかの組み合わせであり得る。
【０１８８】
任意選択で、メモリ602は、プログラム命令を記憶するようにさらに構成される。プロセッサ601は、図２および図３に表わされた、フォワーディング・テーブルを検査するための方法を実現するために、メモリ602に記憶されたプログラム命令を呼び出し、図２および図３に表わされた実施形態における、ネットワーク検査デバイスの１つ以上のステップまたは任意選択の実装を実行し得る。
【０１８９】
この出願の実施形態において提供されるネットワーク検査デバイスは、送信先IPアドレス行きのフォワーディング経路上のいずれか１つ以上のネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを検査するために、送信先IPアドレスおよびネットワーク・トポロジー情報に従って、特定のリンク・ラベルおよび特定のTTL値を含む検査パケットを生成する。従って、故障の位置決めの効率が増加される。
【０１９０】
この出願の図２および図３に表わされた実施形態において提供される、フォワーディング・テーブルを検査するための方法に基づいて、下記は、この方法を実現するネットワーク・ノードを詳細に説明する。
【０１９１】
図７を参照すると、図７は、この出願の実施形態によって提供されるネットワーク・ノード700を表わす。ネットワーク・ノード700は、この出願の図２および図３に表わされた実施形態における、フォワーディング・テーブルを検査するための方法を実現するように構成される。ネットワーク・ノード700は、
検査パケットを受信するように構成された受信モジュール701であって、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、Nは1以上の正の整数であり、TTLの値はN+1である、受信モジュール701と、
ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であるかどうかを判定するように構成されたパケット処理モジュール702と、
パケット処理モジュール702がラベル・スタックは空であると判定するとき、送信先IPアドレスおよびネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードに転送するように構成されたフォワーディング・モジュール703と、を含む。この場合、ネットワーク・ノードは、検査されるべきネットワーク・ノードであり、フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップである。フィードバック・ノードは、検査パケット(この場合、検査パケットはリンク・ラベルを含まず、TTLの値は1である)を受信し、TTLの値から1を減算し、TTLの値は0であると判定するとき、ネットワーク検査デバイスが通知メッセージおよびネットワーク・トポロジー情報に従って、ネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように、通知メッセージ、例えば、ICMPパケットをネットワーク検査デバイスに送信する。
【０１９２】
フォワーディング・モジュール703は、パケット処理モジュール702がラベル・スタックは空でないと判定するとき、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードするようにさらに構成される。この場合、ネットワーク・ノードは、中間ネットワーク・ノードであり、検査パケットが検査されるべきネットワーク・ノードに送信されるまで、リンク・ラベルに従って、検査パケットをフォワードする。
【０１９３】
ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレスに対応するデバイスまでの各ホップのルート情報を含む。ネットワーク・トポロジー情報は、具体的には、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路およびフォワーディング経路上の各ホップのルート情報を含み得る。ルート情報はリンク・ラベルを含む。
【０１９４】
図８を参照すると、図８は、この出願の実施形態によって提供される他のネットワーク・ノード800を表わす。ネットワーク・ノード800は、この出願の図２および図３に表わされた実施形態における、フォワーディング・テーブルを検査するための方法を実現するように構成される。ネットワーク・ノード800は、プロセッサ801、メモリ802、および通信インタフェース803を含む。
【０１９５】
プロセッサ601、メモリ602、および通信インタフェース603は、バス604を使用することによって互いに接続される。バス604は、PCIバス、EISAバス、または同様のものであり得る。バスは、アドレスバス、データバス、制御バス、および同様のものに分類され得る。表現の容易さのために、図８においてバスを表現するために１つのみの太線が使用されているが、これは、１つのみのバスまたは１種類のみのバスが存在することを意味しない。
【０１９６】
メモリ802は、フォワーディング・テーブルを記憶するように構成される。フォワーディング・テーブルは、送信先IPアドレスおよび次のホップを含む。
【０１９７】
プロセッサ801は、検査パケットを受信するように構成され、検査パケットは、ラベル・スタック、TTL、送信元IPアドレス、および送信先IPアドレスを含み、ラベル・スタックはN個のリンク・ラベルを含み、Nは1以上の正の整数であり、TTLの値はN+1であり、プロセッサ801は、ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの値から1を減算し、ラベル・スタックは空であるかどうかを判定し、ラベル・スタックは空であると判定するとき、送信先IPアドレスおよびフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードするように構成される。この場合、ネットワーク・ノードは、検査されるべきネットワーク・ノードであり、フィードバック・ノードは、検査されるべきネットワーク・ノードの次のホップである。フィードバック・ノードは、検査パケット(この場合、検査パケットはリンク・ラベルを含まず、TTLの値は1である)を受信し、TTLの値から1を減算し、TTLの値は0であると判定するとき、ネットワーク検査デバイスが通知メッセージおよびネットワーク・トポロジー情報に従ってネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように、通知メッセージ、例えば、ICMPパケットをネットワーク検査デバイスに送信する。
【０１９８】
ネットワーク・トポロジー情報は、ネットワーク検査デバイスから送信先IPアドレス(検査されるべきIPアドレス)に対応するデバイスまでの各ホップのルート情報を含む。ネットワーク・トポロジー情報は、具体的には、ネットワーク検査デバイスから検査されるべきIPアドレスまでのフォワーディング経路およびフォワーディング経路上の各ホップのルート情報を含み得る。ルート情報はリンク・ラベルを含む。
【０１９９】
プロセッサ801は、ラベル・スタックは空でないと判定するとき、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードするようにさらに構成される。この場合、ネットワーク・ノードは、中間ネットワーク・ノードであり、検査パケットが検査されるべきネットワーク・ノードに送信されるまで、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットをフォワードする。
【０２００】
メモリ802は、揮発性メモリ、例えば、RAMを含み得る。メモリ802は、不揮発性メモリ、例えば、フラッシュメモリ、HDD、またはSSDを含み得る。メモリ802は、上記の種類のメモリの組み合わせを含み得る。
【０２０１】
この出願の実施形態において、通信インタフェース803は、ネットワーク・ノード800とネットワーク内の他のネットワーク・ノードの間の通信のためのインタフェースを表現し、１つ以上の通信インタフェースが存在し得る。説明の容易さのために、通信インタフェース803が、この出願において使用されるが、これは、この出願における技術的解決策を限定しない。
【０２０２】
プロセッサ801は、CPU、NP、またはCPUとNPの組み合わせであり得る。プロセッサ801は、ハードウェア・チップであり得る。ハードウェア・チップは、ASIC、PLD、またはそれらの組み合わせであり得る。PLDは、CPLD、FPGA、GALデバイス、またはそれらのいずれかの組み合わせであり得る。
【０２０３】
任意選択で、プロセッサ801は、フォワーディング・テーブルを取得するようにさらに構成される。具体的には、プロセッサ801は、ルーティング・テーブルに従って、フォワーディング・テーブルを生成する。メモリ802は、ルーティング・テーブルを記憶するようにさらに構成される。ネットワーク・ノードは、従来の方法を使用してルーティング・テーブルを取得し得る。詳細は、ここで説明されない。
【０２０４】
任意選択で、メモリ802は、プログラム命令を記憶するようにさらに構成される。プロセッサ601は、図２および図３に表わされた、フォワーディング・テーブルを検査するための方法を実現するために、メモリ802内に記憶されたプログラム命令を呼び出し、図２および図３に表わされた実施形態におけるネットワーク・ノードの１つ以上のステップまたは任意選択の実装を実行し得る。
【０２０５】
ネットワーク検査デバイスによって送信され、特定のリンク・ラベルおよび特定のTTLを含む検査パケットを受信した後、この出願の実施形態において提供されるネットワーク・ノードは、検査パケット内のTTLの値から1を減算し、ネットワーク・ノードが検査されるべきネットワーク・ノードであるならば、検査パケットをフィードバック・ノードにフォワードする。フィードバック・ノードは、検査パケットを受信し、また、TTLの値から1を減算する。結果として、TTLの値は0であり、フィードバック・ノードは、通知メッセージをネットワーク検査デバイスに送信することを可能にされる。このようにして、ネットワーク検査デバイスは、ネットワーク・トポロジー情報および通知メッセージ内のフィードバック・ノードのIPアドレスに従って、検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定し得る。
【０２０６】
上記の説明は、単に本発明の例示の実装であるが、本発明の保護範囲を限定することは意図されない。本発明において開示された技術的範囲内でこの技術分野の当業者によって容易に理解されるいずれの変形または置換も、本発明の保護範囲内にあるものである。従って、本発明の保護範囲は、請求項の保護範囲に従うものである。
【符号の説明】
【０２０７】
100  システム
110  ネットワーク検査デバイス
120  ネットワーク経路
400  装置
401  パケット生成モジュール
402  送信モジュール
403  受信モジュール
404  判定モジュール
405  トポロジー取得モジュール
600  ネットワーク検査デバイス
601  プロセッサ
602  メモリ
603  通信インタフェース
700  ネットワーク・ノード
701  受信モジュール
702  パケット処理モジュール
703  フォワーディング・モジュール
800  ネットワーク・ノード
801  プロセッサ
802  メモリ
803  通信インタフェース
【図１】
2019505142.tif 000003
【図２】
2019505142.tif 000004
【図３】
2019505142.tif 000005
【図４】
2019505142.tif 000006
【図５】
2019505142.tif 000007
【図６】
2019505142.tif 000008
【図７】
2019505142.tif 000009
【図８】
2019505142.tif 000010
【手続補正書】
【提出日】平成30年8月13日(2018.8.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
この出願において提供される技術的解決策において、ネットワーク検査デバイスは、TTLおよびリンク・ラベルを含む検査パケットを生成し、ラベル・スタックを使用することによって、検査パケットのラベル・フォワーディング経路を特定し、TTLを使用することによって、検査パケットが通過するホップ数を特定し、ネットワーク検査デバイスから送信先IPアドレスまでのフォワーディング経路上の検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを検査する。具体的には、ネットワーク検査デバイスは、ネットワーク・トポロジー情報に従って、ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数Nおよび各ホップのリンク・ラベルを決定し、検査パケットを生成する。検査パケットは、ラベル・スタックおよびTTLを含み、ラベル・スタックはN個のリンク・ラベル(N個のホップの順次的なリンク・ラベル)を含み、TTLの値はNに1が加えられたもの、すなわち、N+1である。検査パケットがネットワーク検査デバイスから検査されるべきネットワーク・ノードまでフォワードされるプロセスにおいて、検査パケットは、ラベル・スタック内のリンク・ラベルに従ってフォワードされる。検査パケットが検査されるべきネットワーク・ノードに到着し、ラベル・スタックが空である後、検査パケットは、検査されるべきネットワーク・ノードのフォワーディング・テーブルに従って、フォワードされる。フィードバック・ノードとも呼ばれる、検査されるべきネットワーク・ノードの次のホップは、検査パケットを受信し、TTLの値から1を減算する。結果として、検査パケット内でTTLの値が0であるので、ICMPパケットのような通知メッセージがネットワーク検査デバイスに送信される。このようにして、ネットワーク検査デバイスは、受信されたICMPパケットおよびネットワーク・トポロジー情報に従って、フォワーディング・テーブル、すなわち、検査されるべきネットワーク・ノードのFIBが誤っているかどうかを判定する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
この出願の実施形態において、ネットワーク検査デバイスが検査することを準備するネットワーク・ノードは、検査されるべきネットワーク・ノードと呼ばれ、検査されるべきネットワーク・ノードの次のホップは、フィードバック・ノードと呼ばれる。ネットワーク検査デバイスと検査されるべきネットワーク・ノードの間のフォワーディング経路上のネットワーク・ノードは、中間ネットワーク・ノードと呼ばれる。図１に表わされたシステムを参照して、ネットワーク検査デバイス110がネットワーク・ノードR1のフォワーディング・テーブルを検査するとき、ネットワーク・ノードR1は、検査されるべきネットワーク・ノードである。ネットワーク・ノードR1のフォワーディング・テーブルが正しいならば、通知メッセージを送信するフィードバック・ノードは、ネットワーク・トポロジー情報内のルートと整合している。ネットワーク・ノードR1のフォワーディング・テーブルが誤っているならば、通知メッセージを送信するフィードバック・ノードは、ネットワーク・トポロジー情報と整合していない。例えば、ネットワーク・ノードR1の次のホップは、ネットワーク・トポロジー情報内のネットワーク・ノードR2である。ネットワーク検査デバイスがネットワーク・ノードR2によって送信される通知メッセージを受信したならば、フィードバック・ノードは、ネットワーク・トポロジー情報と整合し、ネットワーク・ノードR1のフォワーディング・テーブルは正しいと判定され得る。ネットワーク検査デバイスがネットワーク・ノードR2以外のノードによって送信される通知メッセージを受信したならば、フィードバック・ノードは、ネットワーク・トポロジー情報と整合せず、R1のフォワーディング・テーブルは誤っていると判定され得る。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
具体的には、ネットワーク検査デバイスは、マルチプロトコル・ラベル・スイッチング(Multiprotocol Label Switching, 略してMPLS)において定義されたラベル・フォワーディング方式を使用して、この出願における、フォワーディング・テーブルを検査するための方法を実現し得る。検査パケットは、MPLSパケットであり得る。もちろん、セグメント・ルーティング(segment routing)をサポートする他のリンク・ラベル・フォワーディング方式が使用され得る。これは、この出願において限定されない。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
ネットワーク・ノードがラベル・スタックは空でないと判定し、すなわち、ネットワーク・ノードが中間ネットワーク・ノードであるとき、ネットワーク・ノードは、検査パケットが検査されるべきネットワーク・ノードに送信されるように、ラベル・スタックの一番上のリンク・ラベルに従って、検査パケットを次のホップのノードにフォワードする。上記の例はここでも使用される。ネットワーク・ノードR0は、ラベル・スタックは空でないと判定し、ラベル・スタックの一番上のリンク・ラベル8802に従って、検査パケットを次のホップのノード、すなわち、ネットワーク・ノードR1にフォワードする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
ネットワーク・ノードがラベル・スタックは空であると判定するとき、ネットワーク・ノードは検査されるべきネットワーク・ノードである。この場合、検査パケット内のTTLの値は1であることが理解されるべきである。ネットワーク・ノードは、送信先IPアドレスおよびネットワーク・ノードのフォワーディング・テーブルに従って、検査パケットをフィードバック・ノードにフォワードする。フィードバック・ノードは検査されるべきネットワーク・ノードの次のホップのノードである。上記の例はここでも使用される。ネットワーク・ノードR1は、ラベル・スタックは空であると判定し、送信先IPアドレスおよびネットワーク・ノードR1のフォワーディング・テーブルに従って、検査パケットをフィードバック・ノード、すなわち、ネットワーク・ノードR2にフォワードする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１６９
【補正方法】変更
【補正の内容】
【０１６９】
この出願の実施形態における、フォワーディング・テーブルを検査するための方法において、ネットワーク検査デバイスは、検査パケットのフォワーディング経路を特定するために、ネットワーク・トポロジー情報に従って、特定のリンク・ラベルおよび特定のTTL値を含む検査パケットを生成する。TTLの値は、ホップ毎に1だけ減少される。TTLの値が0であるとき、検査されるべきノードの次のホップ、すなわち、フィードバック・ノードは、通知メッセージ(ICMPパケット)をネットワーク検査デバイスに送信することをトリガされる(可能にされる)。この方法は、検査されるべきIPアドレス行きのネットワーク経路上のいずれか１つ以上のネットワーク・ノードのフォワーディング・テーブルが誤っているかどうかを検査し得る。従って、故障の位置決めの効率が増加される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１９５
【補正方法】変更
【補正の内容】
【０１９５】
プロセッサ801、メモリ802、および通信インタフェース803は、バス804を使用することによって互いに接続される。バス804は、PCIバス、EISAバス、または同様のものであり得る。バスは、アドレスバス、データバス、制御バス、および同様のものに分類され得る。表現の容易さのために、図８においてバスを表現するために１つのみの太線が使用されているが、これは、１つのみのバスまたは１種類のみのバスが存在することを意味しない。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０２０４
【補正方法】変更
【補正の内容】
【０２０４】
任意選択で、メモリ802は、プログラム命令を記憶するようにさらに構成される。プロセッサ801は、図２および図３に表わされた、フォワーディング・テーブルを検査するための方法を実現するために、メモリ802内に記憶されたプログラム命令を呼び出し、図２および図３に表わされた実施形態におけるネットワーク・ノードの１つ以上のステップまたは任意選択の実装を実行し得る。
【手続補正９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
フォワーディング・テーブルを検査するための方法であって、
ネットワーク検査デバイスにより、送信先インターネット・プロトコル(IP)アドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するステップであって、前記検査パケットは、ラベル・スタック、生存時間(TTL)、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、ステップと、
前記検査パケットが前記検査されるべきネットワーク・ノードに送信されるように、前記ネットワーク検査デバイスにより、前記ラベル・スタックの一番上のリンク・ラベルに従って前記検査パケットを送信するステップと、
前記ネットワーク検査デバイスにより、フィードバック・ノードによって送信される通知メッセージを受信するステップであって、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードである、ステップと、
前記ネットワーク検査デバイスにより、前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するステップと、
を備える方法。
【請求項２】
ネットワーク検査デバイスにより、送信先IPアドレスおよびネットワーク・トポロジー情報に従って検査パケットを生成する前記ステップは、
前記ネットワーク検査デバイスにより、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記送信先IPアドレスまでのフォワーディング経路および前記フォワーディング経路上の前記検査されるべきネットワーク・ノードを決定するステップであって、前記ネットワーク・トポロジー情報は、前記フォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備える、ステップと、
前記ネットワーク検査デバイスにより、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するステップと、
を備える、請求項１に記載の方法。
【請求項３】
前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定する前記ステップは、
前記ネットワーク検査デバイスにより、前記通知メッセージを送信するフィードバック・ノードが前記ネットワーク・トポロジー情報と整合しているとき、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいと判定するステップと、
前記ネットワーク検査デバイスにより、前記通知メッセージを送信するフィードバック・ノードが前記ネットワーク・トポロジー情報と整合していないとき、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが誤っていると判定するステップと、
を備える、請求項１または２に記載の方法。
【請求項４】
前記フィードバック・ノードによって送信される通知メッセージを受信する前に、前記方法は、
前記フィードバック・ノードにより、前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信するステップと、
前記フィードバック・ノードにより、TTLの前記値から1を減算し、TTLの前記値が0であると判定するとき前記通知メッセージを送信するステップと、  
を備える、請求項１から３のいずれか一項に記載の方法。
【請求項５】
前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信する前に、前記方法は、
前記フォワーディング経路内のネットワーク・ノードにより、前記検査パケットを受信するステップと、
前記ネットワーク・ノードにより、前記ラベル・スタックの一番上のリンク・ラベルを取り出し、TTLの前記値から1を減算するステップと、
前記ラベル・スタックが空でないとき、前記ネットワーク・ノードにより、前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを次のホップのノードにフォワードするステップと、
前記ラベル・スタックが空であるとき、前記ネットワーク・ノードにより、前記送信先IPアドレスおよび前記ネットワーク・ノードのフォワーディング・テーブルに従って、前記検査パケットを前記フィードバック・ノードにフォワードするステップと、
をさらに備える、請求項４に記載の方法。
【請求項６】
前記通知メッセージは、前記検査パケットのヘッダを備える、請求項１から５のいずれか一項に記載の方法。
【請求項７】
フォワーディング・テーブルを検査するための方法であって、
ネットワーク・ノードにより、第１の検査パケットを受信するステップであって、前記第１の検査パケットは、第１のラベル・スタック、第１の生存時間(TTL)、送信元インターネット・プロトコル(IP)アドレス、および送信先IPアドレスを備え、前記第１のラベル・スタックはN個のリンク・ラベルを備え、第１のTTLの値はN+1であり、前記送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、N≧1である、ステップと、
前記ネットワーク・ノードにより、前記第１のラベル・スタックの一番上のリンク・ラベルを取り出し、第１のTTLの前記値から1を減算するステップと、
前記ネットワーク・ノードにより、前記第１のラベル・スタックは空であるかどうかを判定するステップと、
前記ネットワーク・ノードが前記第１のラベル・スタックは空であると判定するならば、前記ネットワーク・ノードにより、第１のフィードバック・ノードが第１の通知メッセージを前記ネットワーク検査デバイスに送信して前記ネットワーク検査デバイスが前記フォワーディング・テーブルは正しいかどうかを判定するように、前記送信先IPアドレスおよび前記ネットワーク・ノードのフォワーディング・テーブルに従って、前記第１の検査パケットを前記第１のフィードバック・ノードにフォワードするステップであって、前記ネットワーク・ノードは第１の検査されるべきネットワーク・ノードであり、前記第１のフィードバック・ノードは前記第１の検査されるべきネットワーク・ノードの次のホップのノードである、ステップと、
を備える方法。
【請求項８】
前記ネットワーク・ノードが前記第１のラベル・スタックは空でないと判定するならば、前記ネットワーク・ノードにより、前記第１のラベル・スタックの一番上のリンク・ラベルに従って、前記第１の検査パケットをフォワードするステップをさらに備える、請求項７に記載の方法。
【請求項９】
前記ネットワーク・ノードにより、第２の検査パケットを受信するステップであって、前記第２の検査パケットは、第２の生存時間(TTL)、前記送信元IPアドレス、および送信先IPアドレスを備え、第２のTTLの値は1である、ステップと、
前記ネットワーク・ノードにより、第２のTTLの前記値から1を減算するステップと、
前記ネットワーク・ノードにより、第２のTTLの前記値は0であると判定するステップであって、前記ネットワーク・ノードは第２のフィードバック・ノードであり、前記第２のフィードバック・ノードは第２の検査されるべきネットワーク・ノードの次のホップのノードである、ステップと、
前記ネットワーク検査デバイスが前記第２の検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように、第２の通知メッセージを前記ネットワーク検査デバイスに送信するステップと、
をさらに備える、請求項７または８に記載の方法。
【請求項１０】
フォワーディング・テーブルを検査するための装置であって、
送信先インターネット・プロトコル(IP)アドレスおよびネットワーク・トポロジー情報に従って、検査パケットを生成するように構成されたパケット生成モジュールであって、前記検査パケットは、ラベル・スタック、生存時間(TTL)、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスはネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1である、パケット生成モジュールと、
前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを送信するように構成された送信モジュールと、
フィードバック・ノードによって送信される通知メッセージを受信するように構成された受信モジュールであって、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードである、受信モジュールと、
前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成された判定モジュールと、
を備える装置。
【請求項１１】
トポロジー取得モジュールをさらに備え、
前記トポロジー取得モジュールは、前記ネットワーク・トポロジー情報を取得するように構成され、前記ネットワーク・トポロジー情報は、前記ネットワーク検査デバイスから前記送信先IPアドレスまでのフォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備え、
前記パケット生成モジュールは、具体的には、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、ネットワーク経路および前記ネットワーク経路上の前記検査されるべきネットワーク・ノードを決定するように構成され、前記フォワーディング経路は前記ネットワーク経路を備え、前記パケット生成モジュールは、具体的には、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するように構成された、請求項１０に記載の装置。
【請求項１２】
前記通知メッセージは、前記検査パケット内のTTLの前記値が0であるとき、前記フィードバック・ノードによって送信される、請求項１０または１１に記載の装置。
【請求項１３】
ネットワーク検査デバイスであって、プロセッサとメモリとを備え、
前記メモリは、ネットワーク・トポロジー情報を記憶するように構成され、前記ネットワーク・トポロジー情報は、前記ネットワーク検査デバイスから送信先インターネット・プロトコル(IP)アドレスまでのフォワーディング経路および前記フォワーディング経路上の各ホップのルート情報を備え、
前記プロセッサは、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、検査パケットを生成するように構成され、前記検査パケットは、ラベル・スタック、生存時間(TTL)、送信元IPアドレス、および前記送信先IPアドレスを備え、前記ラベル・スタックはN個のリンク・ラベルを備え、TTLの値はN+1であり、前記送信元IPアドレスは前記ネットワーク検査デバイスのIPアドレスであり、Nは前記ネットワーク検査デバイスから検査されるべきネットワーク・ノードまでのホップ数であり、N≧1であり、前記プロセッサは、前記ラベル・スタックの一番上のリンク・ラベルに従って、前記検査パケットを送信し、フィードバック・ノードによって送信される通知メッセージを受信するように構成され、前記通知メッセージは、前記フィードバック・ノードが前記検査されるべきネットワーク・ノードによってフォワードされる検査パケットを受信したことを前記ネットワーク検査デバイスに通知するために使用され、前記フィードバック・ノードは前記検査されるべきネットワーク・ノードの次のホップのノードであり、前記プロセッサは、前記通知メッセージおよび前記ネットワーク・トポロジー情報に従って、前記検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定するように構成されたネットワーク検査デバイス。
【請求項１４】
前記プロセッサは、前記送信先IPアドレスおよび前記ネットワーク・トポロジー情報に従って、ネットワーク経路および前記ネットワーク経路上の前記検査されるべきネットワーク・ノードを決定するように構成され、前記フォワーディング経路は前記ネットワーク経路を備え、前記プロセッサは、前記ネットワーク・トポロジー情報に従って、前記ネットワーク検査デバイスから前記検査されるべきネットワーク・ノードまでの前記ホップ数および各ホップのリンク・ラベルを決定し、前記ホップ数および各ホップの前記リンク・ラベルに従って前記検査パケットを生成するように構成された、請求項１３に記載のネットワーク検査デバイス。
【請求項１５】
前記プロセッサは、ソフトウェア・デファインド・ネットワーキング(SDN)コントローラから前記ネットワーク・トポロジー情報を取得するようにさらに構成された、請求項１３または１４に記載のネットワーク検査デバイス。
【請求項１６】
前記通知メッセージは、前記検査パケット内のTTLの前記値が0であるとき、前記フィードバック・ノードによって送信される、請求項１３から１５のいずれか一項に記載のネットワーク検査デバイス。  
【請求項１７】
ネットワーク・ノードであって、プロセッサとメモリとを備え、
前記メモリは、フォワーディング・テーブルを記憶するように構成され、前記フォワーディング・テーブルは、送信先インターネット・プロトコル(IP)アドレスおよび次のホップを備え、
前記プロセッサは、第１の検査パケットを受信するように構成され、前記第１の検査パケットは、第１のラベル・スタック、第１のTTL、送信元IPアドレス、および送信先IPアドレスを備え、前記第１のラベル・スタックはN個のリンク・ラベルを備え、Nは１以上の正の整数であり、第１のTTLの値はN+1であり、
前記プロセッサは、前記第１のラベル・スタックの一番上のリンク・ラベルを取り出し、第１のTTLの前記値から1を減算し、
前記第１のラベル・スタックは空であるかどうかを判定し、
前記第１のラベル・スタックは空であると判定するとき、第１のフィードバック・ノードが第１の通知メッセージをネットワーク検査デバイスに送信することをトリガして前記ネットワーク検査デバイスが前記フォワーディング・テーブルは正しいかどうかを判定するように、前記送信先IPアドレスおよび前記フォワーディング・テーブルに従って、前記第１の検査パケットを前記第１のフィードバック・ノードにフォワードするように構成され、前記ネットワーク・ノードは第１の検査されるべきネットワーク・ノードであり、前記第１のフィードバック・ノードは前記第１の検査されるべきネットワーク・ノードの次のホップのノードであるネットワーク・ノード。
【請求項１８】
前記プロセッサは、前記第１のラベル・スタックは空でないと判定するとき、前記第１のラベル・スタックの一番上のリンク・ラベルに従って、前記第１の検査パケットをフォワードするようにさらに構成された、請求項１７に記載のネットワーク・ノード。
【請求項１９】
前記プロセッサは、
第２の検査パケットを受信するようにさらに構成され、前記第２の検査パケットは、第２の生存時間(TTL)、前記送信元IPアドレス、および送信先IPアドレスを備え、第２のTTLの値は1であり、
前記プロセッサは、第２のTTLの前記値から1を減算し、
第２のTTLの前記値は0であると判定するようにさらに構成され、前記ネットワーク・ノードは第２のフィードバック・ノードであり、前記第２のフィードバック・ノードは第２の検査されるべきネットワーク・ノードの次のホップのノードであり、
前記プロセッサは、前記ネットワーク検査デバイスに前記第２の検査されるべきネットワーク・ノードのフォワーディング・テーブルが正しいかどうかを判定させるために、第２の通知メッセージを前記ネットワーク検査デバイスに送信するようにさらに構成された、請求項１７に記載のネットワーク・ノード。
【請求項２０】
請求項１から６のいずれか一項に記載の方法を実行するための命令を備えるプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項２１】
請求項７から９のいずれか一項に記載の方法を実行するための命令を備えるプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2019505142.tif 000011
【国際調査報告】
2019505142.tif 000012
2019505142.tif 000013
2019505142.tif 000014
2019505142.tif 000015