(57)【要約】【課題】ＢＧＰ(Border Gateway Protocol)に基づくプレフィックスの伝搬遅延を考慮して、実際に発生した障害リンクを検出する方法、ノード装置及びプログラムを提供する。【解決手段】各ＡＳ(Autonomous System)のプレフィックス毎に、正常状態パスのリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定し、監視プレフィックスを含む経路更新メッセージのみを計測する。監視プレフックス数が有値から零へ変化した零リンクを抽出し、検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割する。そして、クラスタに含まれる零リンクの中で、観測ＡＳに最も近いリンクを、障害箇所として決定する。【選択図】図４
2011166248.tif 000002
【特許請求の範囲】
【請求項１】
固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
前記ノード装置の障害リンク検出方法において、
観測ノード装置が、前記経路更新メッセージに含まれる前記パスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する第１のステップと、
前記観測ノード装置が、管理元ノード装置のプレフィックスに対する前記正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する第２のステップと、
前記観測ノード装置が、前記監視プレフィックスを含む経路更新メッセージのみを計測する第３のステップと、
前記観測ノード装置が、各検出時刻について、前記正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する第４のステップと、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割する第５のステップと、
前記クラスタに含まれる零リンクの中で、前記観測ノード装置に最も近いリンクを、障害箇所として決定する第６のステップと
を有することを特徴とする障害リンク検出方法。
【請求項２】
第４のステップについて、
前記正常状態パス上の各リンクの上流側ノード装置から広報される監視プレフックス毎に、パス列をパステーブルに記録し、
前記パステーブルの当該パス列が、前記正常状態パス上から外れた時の発生時刻を、前記零リンクに対応付けて記録し、
第６のステップについて、
前記クラスタに含まれる零リンクの中で、前記変動時刻が最も早い時点に、前記障害が発生したと決定する
ことを特徴とする請求項１に記載の障害リンク検出方法。
【請求項３】
第４のステップについて、
前記零リンクの上流側ノード装置から広報された監視プレフィックス毎に、当該パス列が、前記正常状態パス上へ戻った時の復旧時刻を、前記零リンクに対応付けて記録し、
第６のステップについて、
前記クラスタに含まれる零リンクの中で、前記復旧時刻が最も遅い時点に、前記障害が復旧したと決定する
ことを特徴とする請求項２に記載の障害リンク検出方法。
【請求項４】
第１のステップについて、前記観測ノード装置が、各ノード装置のプレフィックス毎に、受信した前記経路更新メッセージに含まれるパス毎の累積利用時間を収集し、所定時間範囲で、当該累積利用時間が最も長いパスを前記正常状態パスとして決定することを特徴とする請求項１から３のいずれか１項に記載の障害リンク検出方法。
【請求項５】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記プレフィックスとは、ＩＰアドレスとサブネットマスクのビット数との組からなる送信元アドレス又はその範囲であり、
前記経路更新メッセージの前記パスは、AS_PATH属性に含まれる
ことを特徴とする請求項１から４のいずれか１項に記載のノード装置の障害リンク検出方法。
【請求項６】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
前記経路更新メッセージに含まれる前記パスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する正常状態パス決定手段と、
管理元ノード装置のプレフィックスに対する前記正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する監視プレフィックス決定手段と、
前記観測ノード装置が、前記監視プレフィックスを含む経路更新メッセージのみを計測する監視対象抽出手段と、
各検出時刻について、前記正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する零リンク抽出手段と、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割するクラスタリング手段と、
前記クラスタに含まれる零リンクの中で、前記観測ノード装置に最も近いリンクを、障害箇所として決定する障害リンク検出手段と
を有することを特徴とするノード装置。
【請求項７】
前記零リンク抽出手段は、
前記正常状態パス上の各リンクの上流側ノード装置から広報される監視プレフックス毎に、パス列をパステーブルに記録し、
記録された当該パス列が、前記正常状態パス上から外れた時の発生時刻を、前記零リンクに対応付けて記録し、
前記障害リンク検出手段は、
前記クラスタに含まれる零リンクの中で、前記変動時刻が最も早い時点に、前記障害が発生したと決定する
ことを特徴とする請求項６に記載のノード装置。
【請求項８】
前記零リンク抽出手段は、
前記零リンクの上流側ノード装置から広報された監視プレフィックス毎に、当該パス列が、前記正常状態パス上へ戻った時の復旧時刻を、前記零リンクに対応付けて記録し、
前記障害リンク検出手段は、
前記クラスタに含まれる零リンクの中で、前記復旧時刻が最も遅い時点に、前記障害が復旧したと決定する
ことを特徴とする請求項７に記載のノード装置。
【請求項９】
前記正常状態パス決定手段は、各ノード装置のプレフィックス毎に、受信した前記経路更新メッセージに含まれるパス毎の累積利用時間を収集し、所定時間範囲で、当該累積利用時間が最も長いパスを前記正常状態パスとして決定することを特徴とする請求項６から８のいずれか１項に記載のノード装置。
【請求項１０】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記プレフィックスとは、ＩＰアドレスとサブネットマスクのビット数との組からなる送信元アドレス又はその範囲であり、
前記経路更新メッセージの前記パスは、AS_PATH属性に含まれる
ことを特徴とする請求項６から９のいずれか１項に記載のノード装置。
【請求項１１】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してノード装置に搭載されたコンピュータを機能させるプログラムにおいて、
前記経路更新メッセージに含まれる前記パスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する正常状態パス決定手段と、
管理元ノード装置のプレフィックスに対する前記正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する監視プレフィックス決定手段と、
前記観測ノード装置が、前記監視プレフィックスを含む経路更新メッセージのみを計測する監視対象抽出手段と、
各検出時刻について、前記正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する零リンク抽出手段と、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割するクラスタリング手段と、
前記クラスタに含まれる零リンクの中で、前記観測ノード装置に最も近いリンクを、障害箇所として決定する障害リンク検出手段と
してコンピュータを機能させることを特徴とするノード装置用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づいて障害リンクを検出する技術に関する。
【背景技術】
【０００２】
インターネットでは、経路制御プロトコルを用いて、ノード装置（例えばルータ）がパケットを適切に中継転送する。代表的な経路制御プロトコルとして、インターネット上で組織ネットワーク間の経路情報を交換する「ＢＧＰ(Border Gateway Protocol)」がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一の「ＡＳ(Autonomous System)番号」（固有識別番号）が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
図１は、ＢＧＰにおけるネットワーク構成図及びテーブルである。
【０００４】
図１によれば、ＢＧＰを用いて、ＡＳ番号を有するノード装置１が相互に接続されている。各ノード装置は、送信元プレフィックス（送信元ネットワークアドレス）及びＡＳ番号を含む経路更新メッセージ(UPDATE)を、定期的にブロードキャストで送信する。UPDATEメッセージには、以下のパラメータが含まれる。
（１）メッセージ種別
（２）プレフィックス
（３）AS_PATH属性
「メッセージ種別」は、経路更新メッセージのタイプ（通知Announce／削除Withdraw）を表す。
「プレフィックス」は、ＩＰアドレス及びサブネットマスクの組(xxx.xxx.xxx.xxx/xx)であって、送信元ネットワークアドレス（送信元アドレスの範囲）を表す。
「AS_PATH属性」は、プレフィックスからの到達経路のパス（ＡＳ番号の列）を表す。
【０００５】
UPDATEメッセージを受信した各ノード装置は、そのUPDATEメッセージのパスに当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。
【０００６】
観測ノード装置は、ＲＩＢ(Routing Information Base)と称されるパス（経路）テーブルを有する。ここで、「パス」とは、管理元ノード装置（送信元）と観測ノード装置との間の経路であって、中継ノード装置を介した接続を意味する。また、「リンク」とは、直接的に接続される隣接ノード装置間の接続を意味する。
【０００７】
パステーブルは、送信元ノード装置の「プレフィックス」と、そのプレフィックスに対応する「ＡＳ番号のパス」とを含む。パステーブルは、UPDATEメッセージを定期的に受信することによって更新される。
【０００８】
従来、本願発明者らは、各リンクで集計対象とするプレフィックスを、予め推定した最適経路上のプレフィックスのみに限定すると共に、最適経路上の各リンクＡＳj−ＡＳkにおける上流側ＡＳkが広報元で且つＡＳjを経由するプレフィックスに限定して、障害リンクを検出する技術を提案した（非特許文献１参照）。この技術によれば、小規模の経路障害に対しても、高精度に障害発生箇所を推定することができる。
【０００９】
尚、リンクの障害を検出する技術ではないが、所望のパスを導出することができる技術もある（例えば非特許文献２参照）。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】渡里雅史、立花篤男、阿野茂浩、「プレフィックス数の変動に基づくＢＧＰ障害リンク推定手法に関する一検討」、ＫＤＤＩ研究所、２００９年電子情報通信学会通信ソサエティ大会、Ｂ−７−６６、２００９年９月１５日
【非特許文献２】R. Oliveira, B. Zhang, D. Pei, L. Zhang,"Quantifying Path Exploration in the Internet", IEEE/ACM Transactionon Networking, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１に記載された技術によれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクをリアルタイムに特定することができる。しかしながら、ＢＧＰのノード装置におけるタイマ値や実装特性の影響によって、ネットワークが大規模になるほど、プレフィックス間の伝搬に時間差が生じる。これは、単一リンクで発生した障害により他のリンクを監視するプレフィックスに変動が発生した場合、プレフィックスの伝搬遅延によってそのプレフィックスの検出時刻が異なり、観測ノード装置から見て、障害箇所となるリンクを特定できないという課題を生じた。
【００１２】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視すると共に、プレフィックスの伝搬遅延を考慮して、実際に発生した障害リンクを検出することができる方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置の障害リンク検出方法において、
観測ノード装置が、経路更新メッセージに含まれるパスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する第１のステップと、
観測ノード装置が、管理元ノード装置のプレフィックスに対する正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する第２のステップと、
観測ノード装置が、監視プレフィックスを含む経路更新メッセージのみを計測する第３のステップと、
観測ノード装置が、各検出時刻について、正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する第４のステップと、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割する第５のステップと、
クラスタに含まれる零リンクの中で、観測ノード装置に最も近いリンクを、障害箇所として決定する第６のステップと
を有することを特徴とする。
【００１４】
本発明の障害リンク検出方法における他の実施形態によれば、
第４のステップについて、
正常状態パス上の各リンクの上流側ノード装置から広報される監視プレフックス毎に、パス列をパステーブルに記録し、
パステーブルの当該パス列が、正常状態パス上から外れた時の発生時刻を、零リンクに対応付けて記録し、
第６のステップについて、
クラスタに含まれる零リンクの中で、変動時刻が最も早い時点に、障害が発生したと決定することも好ましい。
【００１５】
本発明の障害リンク検出方法における他の実施形態によれば、
第４のステップについて、
零リンクの上流側ノード装置から広報された監視プレフィックス毎に、当該パス列が、正常状態パス上へ戻った時の復旧時刻を、零リンクに対応付けて記録し、
第６のステップについて、
クラスタに含まれる零リンクの中で、復旧時刻が最も遅い時点に、障害が復旧したと決定することも好ましい。
【００１６】
本発明の障害リンク検出方法における他の実施形態によれば、第１のステップについて、観測ノード装置が、各ノード装置のプレフィックス毎に、受信した経路更新メッセージに含まれるパス毎の累積利用時間を収集し、所定時間範囲で、当該累積利用時間が最も長いパスを正常状態パスとして決定することを特徴とすることも好ましい。
【００１７】
本発明の障害リンク検出方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
プレフィックスとは、ＩＰアドレスとサブネットマスクのビット数との組からなる送信元アドレス又はその範囲であり、
経路更新メッセージのパスは、AS_PATH属性に含まれることも好ましい。
【００１８】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
経路更新メッセージに含まれるパスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する正常状態パス決定手段と、
管理元ノード装置のプレフィックスに対する正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する監視プレフィックス決定手段と、
観測ノード装置が、監視プレフィックスを含む経路更新メッセージのみを計測する監視対象抽出手段と、
各検出時刻について、正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する零リンク抽出手段と、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割するクラスタリング手段と、
クラスタに含まれる零リンクの中で、観測ノード装置に最も近いリンクを、障害箇所として決定する障害リンク検出手段と
を有することを特徴とする。
【００１９】
本発明のノード装置における他の実施形態によれば、
零リンク抽出手段は、
正常状態パス上の各リンクの上流側ノード装置から広報される監視プレフックス毎に、パス列をパステーブルに記録し、
記録された当該パス列が、正常状態パス上から外れた時の発生時刻を、零リンクに対応付けて記録し、
障害リンク検出手段は、
クラスタに含まれる零リンクの中で、変動時刻が最も早い時点に、障害が発生したと決定することも好ましい。
【００２０】
本発明のノード装置における他の実施形態によれば、
零リンク抽出手段は、
零リンクの上流側ノード装置から広報された監視プレフィックス毎に、当該パス列が、正常状態パス上へ戻った時の復旧時刻を、零リンクに対応付けて記録し、
障害リンク検出手段は、
クラスタに含まれる零リンクの中で、復旧時刻が最も遅い時点に、障害が復旧したと決定することも好ましい。
【００２１】
本発明のノード装置における他の実施形態によれば、正常状態パス決定手段は、各ノード装置のプレフィックス毎に、受信した経路更新メッセージに含まれるパス毎の累積利用時間を収集し、所定時間範囲で、当該累積利用時間が最も長いパスを正常状態パスとして決定することも好ましい。
【００２２】
本発明のノード装置における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
プレフィックスとは、ＩＰアドレスとサブネットマスクのビット数との組からなる送信元アドレス又はその範囲であり、
経路更新メッセージのパスは、AS_PATH属性に含まれることも好ましい。
【００２３】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元のプレフィックス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してコンピュータを機能させるノード装置用のプログラムにおいて、
経路更新メッセージに含まれるパスを用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する正常状態パス決定手段と、
管理元ノード装置のプレフィックスに対する正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する監視プレフィックス決定手段と、
観測ノード装置が、監視プレフィックスを含む経路更新メッセージのみを計測する監視対象抽出手段と、
各検出時刻について、正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する零リンク抽出手段と、
検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割するクラスタリング手段と、
クラスタに含まれる零リンクの中で、観測ノード装置に最も近いリンクを、障害箇所として決定する障害リンク検出手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００２４】
本発明の障害リンク検出方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視すると共に、プレフィックスの伝搬遅延を考慮して、実際に発生した障害リンクを検出することができる。単一リンクで発生した障害により、他のリンクが異なる時刻で検出されたとしても、プレフィックスの伝搬に対する個々の影響を分類することができる。
【図面の簡単な説明】
【００２５】
【図１】ＢＧＰにおけるネットワーク構成図及びテーブルである。
【図２】本発明における観測ノード装置の第１のフローチャート及びテーブルである。
【図３】観測時刻における監視プレフィックスの計数を表す説明図である。
【図４】本発明における観測ノード装置の第２のフローチャート及びテーブルである。
【図５】図４のＳ４４〜Ｓ４６の監視プレフックス数に対する処理を表す説明図である。
【図６】観測時刻に対して、障害発生時刻及び障害復旧時刻の推定を表す説明図である。
【図７】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２６】
以下では、本発明を実施するための形態によれば、図面を用いて詳細に説明する。
【００２７】
図２は、本発明における観測ノード装置の第１のフローチャート及びテーブルである。図２によれば、図１と同一のネットワーク構成について説明している。
【００２８】
ＢＧＰを用いて、ＡＳ番号を有する８台のノード装置１(AS10〜AS80)が相互に接続されている。ここで、管理元ノード装置AS70から送信されたUPDATEメッセージが、観測ノード装置AS10へ到達するまでの流れを簡単に説明する。
【００２９】
ノード装置AS70は、自らが管理するプレフィックスp2及びＡＳ番号[70]を含むUPDATE(Announce)メッセージ[A|p7|70]を、定期的にブロードキャストで送信する。
ノード装置AS60は、AS70から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[60]を追加する。そして、ノード装置AS60は、そのUPDATE(Announce)メッセージ[A|p7|60 70]を、ノード装置AS50及びAS80へ送信する。
ノード装置AS80は、AS60から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[80]を追加する。そして、ノード装置AS80は、そのUPDATE(Announce)メッセージ[A|p7|80 60 70]を、ノード装置AS20へ送信する。
ノード装置AS50は、AS60から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[50]を追加する。そして、ノード装置AS50は、そのUPDATE(Announce)メッセージ[A|p7|50 60 70]を、ノード装置AS40へ送信する。
ノード装置AS40は、AS50から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[40]を追加する。そして、ノード装置AS40は、そのUPDATE(Announce)メッセージ[A|p7|40 50 60 70]を、ノード装置AS30及びAS20へ送信する。
ノード装置AS30は、AS40から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[30]を追加する。そして、ノード装置AS30は、そのUPDATE(Announce)メッセージ[A|p7|30 40 50 60 70]を、ノード装置AS20へ送信する。
ノード装置AS20は、AS30,AS40又はAS80から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[20]を追加する。そして、ノード装置AS20は、そのUPDATE(Announce)メッセージ[A|p7|20 30 40 50 60 70]、[A|p7|20 40 50 60 70]又は[A|p7|20 80 60 70]を、ノード装置AS10へ送信する。
ノード装置AS10は、AS20から受信したそのUPDATEメッセージのＡＳパスに、自らのＡＳ番号[10]を追加し、それをパステーブルに記録する。
【００３０】
前述したシーケンスと同様に、各ノード装置AS80,AS60,AS50,AS40,AS30,AS20から定期的にブロードキャストで送信されたUPDATEメッセージも、他のノード装置を中継して、観測ノード装置AS10によって受信される。
【００３１】
（Ｓ２１）最初に、観測ノード装置AS10は、所定時間、以下のＳ２２及びＳ２３を繰り返すことによって、障害発生前の正常状態パスを決定する。
【００３２】
（Ｓ２２）観測ノード装置AS10は、ＢＧＰのUPDATE(Announce)メッセージを受信する。そのUPDATEメッセージから、プレフィックス及びＡＳパスを取得する。
【００３３】
（Ｓ２３）観測ノード装置AS10は、送信元ノード装置のプレフィックス毎に、受信したUPDATEメッセージに含まれるＡＳパス毎の累積利用時間を収集する。図２によれば、管理元ノード装置として、ノード装置AS70が指定されており、管理元ノード装置AS70が広報するプレフィックスp7の累積利用時間が記録されている。
【００３４】
（Ｓ２４）観測ノード装置AS10は、UPDATEメッセージに含まれるパス(AS_PATH属性)を用いて、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する。ここでは、当該累積利用時間が最も長いパスを正常状態パスとして決定する。図２によれば、管理元ノード装置AS70について、累積利用時間「２４０時間」で最も長いＡＳパス[10 20 40 50 60 70]を、正常状態パスとして決定する。
【００３５】
（Ｓ２５）観測ノード装置AS10は、管理元ノード装置のプレフィックスに対する正常状態パスについて、ノード装置間のリンクを導出する。図２によれば、管理元ノード装置AS70のプレフィックスp7に対する正常状態パス[10 20 40 50 60 70]におけるノード装置間のリンクを導出する。ここでは、正常状態パス[10 20 40 50 60 70]について、リンク[10-20][20-40][40-50][50-60][60-70]が導出される。
【００３６】
次に、リンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する。
図２によれば、リンク[60-70]については、そのリンクの上流側ノード装置AS70から広報されるプレフィックスp7を監視プレフィックスとして決定する。
リンク[50-60]については、そのリンクの上流側ノード装置AS60から広報されるプレフィックスp61,p62,p63,p64,p65を監視プレフィックスとして決定する。
リンク[40-50]については、そのリンクの上流側ノード装置AS50から広報されるプレフィックスp5を監視プレフィックスとして決定する。
リンク[20-40]については、そのリンクの上流側ノード装置AS40から広報されるプレフィックスp4を監視プレフィックスとして決定する。
リンク[10-20]については、そのリンクの上流側ノード装置AS20から広報されるプレフィックスp2を監視プレフィックスとして決定する。
【００３７】
図３は、観測時刻における監視プレフィックスの計数を表す説明図である。
【００３８】
以下では、ノード装置AS50とノード装置AS40との間のリンク[AS40-AS50]に、障害が発生したものとして説明する。
【００３９】
図３（ａ）によれば、観測時刻Ta3について、監視プレフィックスp5,p61-p65が零に変化している。このとき、監視プレフィックスp5のリンク[40-50]と、監視プレフィックスp61-p65のリンク[50-60]とについて、観測ノード装置に最も近いリンク[40-50]に障害が発生したものと判断される。即ち、リンク[40-50]の障害によって、リンク[50-60]に基づく監視プレフィックスp61-p65にも、影響を与えたものと推定される。
【００４０】
一方で、図３（ｂ）は、図３（ａ）と比較して、１つのリンクに障害が発生した場合に、他のリンクに基づく監視プレフィックスの影響が、同一の観測時刻の中に現れない。これは、ＢＧＰのノード装置におけるタイマ値や実装特性の影響によって、ネットワークが大規模になるほど、プレフィックス間の伝搬に生じる時間差に基づく。例えば、同一リンク[40-50]について障害が複数回発生した場合、プレフィックスの伝搬遅延によって他のリンクの検出時刻が異なり、観測ノード装置から見て、障害箇所となるリンクを特定できない。
【００４１】
非特許文献１に記載された技術に基づく図３（ａ）は、１つのリンクに障害が発生した場合に、同一の観測時刻の中に、他のリンクに基づく監視プレフィックスの影響が現れる場合にのみ、リンク障害の推定が可能となる。しかしながら、図３（ｂ）のような場合、非特許文献１に記載された技術によれば、リンク障害の推定を誤る場合がある。
【００４２】
図４は、本発明における観測ノード装置の第２のフローチャート及びテーブルである。また、図５は、図４のＳ４４〜Ｓ４６の監視プレフックス数に対する処理を表す説明図である。
【００４３】
（Ｓ４１）観測ノード装置AS10は、UPDATE(Announce)メッセージを受信する毎に、以下のＳ４２〜Ｓ４５を繰り返すことによって、障害リンクを検出する。
【００４４】
（Ｓ４２）観測ノード装置AS10は、ＢＧＰのUPDATE(Announce)メッセージを受信する。そのUPDATEメッセージから、プレフィックス及びＡＳパスを取得する。
【００４５】
（Ｓ４３）観測ノード装置AS10は、受信したプレフィックスが監視プレフィックスであるか否かを判定する。ここで、監視プレフィックスでない場合、処理を終了し、再び次のUPDATE(Announce)メッセージの受信を待つ。これによって、観測ノード装置AS10は、監視プレフィックスについてのみ、以下のＳ４４〜Ｓ４６の処理を実行する。
【００４６】
（Ｓ４４）観測ノード装置AS10が、各検出時刻について、正常状態パス上のリンク毎に監視プレフックス数を計数し、その監視プレフックス数が有値から零へ変化した零リンクを抽出する。図５（ａ）によれば、以下の零リンクが抽出されている。
T3: p5 [40-50]
T4: p61-p65 [50-60]
T5: p7 [60-70]
T7: p5 [40-50]
T8: p61-p65 [50-60]
T9: p5 [40-50]
【００４７】
（Ｓ４５）検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割する。
【００４８】
図５（ｂ）によれば、所定分類時間範囲ｄが、例えばT×5に設定されているとする。例えば、観測時刻T3から見てT8までが、所定分類時間範囲ｄに含まれるとする。
T3: p5 [40-50]
T4: p61-p65 [50-60]
T5: p7 [60-70]
T7: p5 [40-50]
T8: p61-p65 [50-60]
ここで、零リンク[40-50]が、T3だけでなく、T7にも含まれる。そこで、T7以降を別の零リンク群に分割する。これによって、図５（ｂ）によれば、第１のクラスタは、以下のように表される。
T3: p5 [40-50]
T4: p61-p65 [50-60]
T5: p7 [60-70]
【００４９】
次に、例えば、観測時刻T7から見てT12までが、所定分類時間範囲ｄに含まれるとする。
T7: p5 [40-50]
T8: p61-p65 [50-60]
T9: p5 [40-50]
ここで、零リンク[40-50]が、T7だけでなく、T9にも含まれる。そこで、T9以降を別の零リンク群に分割する。これによって、図５（ｂ）によれば、第２のクラスタは、以下のように表される。
T7: p5 [40-50]
T8: p61-p65 [50-60]
更に、第３のクラスタは、以下のように表される。
T9: p5 [40-50]
【００５０】
（Ｓ４６）クラスタに含まれる零リンクの中で、観測ノード装置に最も近いリンクを、障害箇所として決定する。図５（ｃ）によれば、第１のクラスタは、零リンク[40-50][50-60][60-70]の中で、観測ノード装置AS10に最も近い[40-50]を、障害箇所として決定する。また、第２のクラスタは、零リンク[40-50][50-60]の中で、観測ノード装置AS10に最も近い[40-50]を、障害箇所として決定する。更に、第３のクラスタは、零リンク[40-50]を、障害箇所として決定する。これによって、リンク[40-50]に、３回の障害が発生したことが検出される。
【００５１】
図６は、観測時刻に対して、障害発生時刻及び障害復旧時刻の推定を表す説明図である。
【００５２】
前述した図５によれば、観測時刻に応じて零リンクが抽出され、障害発生箇所となる零リンクが検出されている。しかしながら、その零リンクに障害が現実に発生した時刻は、その観測時刻よりも過去の時刻となる。特に、インターネットを対象としたＢＧＰネットワークによれば、障害発生から障害検出まで例えば３〜４分程度を要するためである。
【００５３】
一方で、プレフィックス毎のＡＳパス列を観測した場合、リンク障害が発生した場合、何らかの経路変動（パス列の変動）が必ず発生している。図６によれば、パス列の変動が表されている。
【００５４】
（Ｓ６１）リンク障害を検出したノード装置AS40は、UPDATE(Withdraw)メッセージをノード装置AS20及びAS30へ送信する。
UPDATE(Withdraw):[W| p61,p62,p63,p64,p65,p7]
Withdrawは、経路が削除されたことを意味する。UPDATE(Withdraw)メッセージには、ノード装置AS40が過去に中継した経路更新(UPDATE)メッセージについて、リンク[AS40-AS50]を介したプレフィックスが含まれる。従って、そのUPDATE(Withdraw)メッセージには、プレフィックス[p5,p61,p62,p63,p64,p65,p7]が含まれる。
【００５５】
ノード装置AS20は、ノード装置AS40からUPDATE(Withdraw)メッセージ[w|p5,p61,p62,p63,p64,p65,p7]を受信する。これに対し、ノード装置AS20は、プレフィックス[p61,p62,p63,p64,p65,p7]について、他の経路を検索する。ここで、ノード装置AS20は、ノード装置AS30を経由して、プレフィックス[p5,p61,p62,p63,p64,p65,p7]に対応するノード装置へ到達できることを検索したとする。ノード装置AS20は、リンク[AS40-AS50]に障害が発生したことまで特定できていないからである。このとき、ノード装置AS20は、ノード装置AS10へ、プレフィックス[p5,p61,p62,p63,p64,p65,p7]に対する新たなUPDATE(Announce)メッセージを送信する。
UPDATE(Announce):[A|p5 |20 30 40 50]
UPDATE(Announce):[A|p61|20 30 40 50 60]
・・・・・・
UPDATE(Announce):[A|p7 |20 30 40 50 60 70]
これによって、ノード装置AS10は、プレフィックス[p5,p61,p62,p63,p64,p65,p7]に対応するノード装置に対して、ノード装置AS30の経路を確保できたと判断する。ここで、観測ノード装置AS10は、p5,p61-p65,p7についてＡＳパスの経路変動を記録する。
【００５６】
しかしながら、現実には、ノード装置AS30を経由する経路であっても、管理元ノード装置AS70と観測ノード装置AS10との間で、ノード装置間のリンク[AS40−AS50]の障害を回避することはできない。
【００５７】
（Ｓ６２）次に、ノード装置AS30が、UPDATE(Withdraw)メッセージをノード装置AS20へ送信する。ノード装置AS30は、ノード装置AS40からUPDATE(Withdraw)メッセージを受信した際に、プレフィックス[p5,p61,p62,p63,p64,p65,p7]について、他の経路を検索できない。そこで、ノード装置AS30は、UPDATE(Withdraw)メッセージを、ノード装置AS20へ転送する。
UPDATE(Withdraw):[W| p5,p61,p62,p63,p64,p65,p7]
【００５８】
（Ｓ６３）次に、ノード装置AS20は、ノード装置AS30からUPDATE(Withdraw)メッセージ[w|
p5,p61,p62,p63,p64,p65,p7]を受信した際に、ノード装置AS30を経由する経路でもリンク障害を回避できないことを知る。ここで、ノード装置AS20は、再度、プレフィックス[p61,p62,p63,p64,p65,p7]に対応するノード装置へ到達できる経路を検索し、ノード装置AS80を経由する経路を検索したとする。このとき、ノード装置AS20は、ノード装置AS10へ、プレフィックス[p61,p62,p63,p64,p65,p7]に対する新たなUPDATE(Announce)メッセージを送信する。
UPDATE(Announce):[A|p61|20 80 60 70]
・・・・・・
UPDATE(Announce):[A|p7 |20 80 60 70]
これによって、ノード装置AS10は、プレフィックス[p61,p62,p63,p64,p65,p7]に対応するノード装置に対して、ノード装置AS80の経路を確保できたと判断する。ここで、観測ノード装置AS10は、p61-p65,p7についてＡＳパスの経路変動を記録する。
【００５９】
図６（ａ）は、監視プレフックス毎にＡＳパス列が記録されたパステーブルを表す。ここで、監視プレフックス毎に、正常状態パスから外れた変動時刻を、障害発生時刻として記録し、その後、正常状態パスへ戻った変動時刻を、障害復旧時刻として記録する。
【００６０】
図６（ｂ）は、クラスタ毎の各零リンクに、障害発生時刻及び障害復旧時刻を更に記録する。
例えば、第１のクラスタにおける障害発生時刻について、t4'<t3'<t5'の場合、リンク[40-50]の障害が、遅くとも時刻t4'に発生したと推定できる。
例えば、第２のクラスタにおける障害発生時刻について、t7'<t8'の場合、リンク[40-50]の障害が、遅くとも時刻t7'に発生したと推定できる。
例えば、第３のクラスタにおける障害発生時刻について、リンク[40-50]の障害が、遅くとも時刻t9'に発生したと推定できる。
【００６１】
また、例えば、第１のクラスタにおける障害復旧時刻について、t4''<t3''<t5''の場合、リンク[40-50]の障害は、遅くとも時刻t5''に復旧したと推定できる。
例えば、第２のクラスタにおける障害復旧時刻について、t7''<t8''の場合、リンク[40-50]の障害は、遅くとも時刻t8''に復旧したと推定できる。
例えば、第３のクラスタにおける障害発生時刻について、リンク[40-50]の障害が、遅くとも時刻t9''に復旧したと推定できる。
【００６２】
図７は、本発明におけるノード装置の機能構成図である。
【００６３】
図７によれば、ノード装置１は、中継転送部１０と、経路更新メッセージ送信部１１と、経路更新メッセージ受信監視部１２と、正常状態パス決定部１３と、監視プレフィックス決定部１４と、監視対象抽出部１５と、零リンク抽出部１６と、クラスタリング部１７と、障害リンク決定部１８とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、中継転送部１０を除くこれらの機能は、経路更新メッセージの転送経過情報を予め蓄積した障害リンク検出装置２に搭載することもできる。
【００６４】
中継転送部１０は、UPDATE(Announce)メッセージを受信した際に、そのUPDATE(Announce)メッセージに含まれる、中継ノード装置のＡＳ番号の連続からなるパスに、更に当該ノード装置のＡＳ番号を含めて、当該UPDATEメッセージを中継転送する。
【００６５】
経路更新メッセージ送信部１１は、ＢＧＰに基づいて、プレフィックス及びＡＳ番号を含むUPDATEメッセージを、定期的にブロードキャストで送信する。
【００６６】
経路更新メッセージ受信監視部１２は、中継転送部１０から抽出したＢＧＰのUPDATEメッセージを、正常状態パス決定部１３及び監視対象抽出部１５へ出力する。
【００６７】
正常状態パス決定部１３は、UPDATE(Announce)メッセージに含まれるパス列をパステーブルに記録し、各ノード装置のプレフィックス毎に、正常状態時における１つの正常状態パスを決定する。具体的には、各ノード装置のプレフィックス毎に、受信したUPDATE(Announce)メッセージに含まれるパス毎の累積利用時間を収集し、所定時間範囲で、当該累積利用時間が最も長いパスを正常状態パスとして決定する。決定された正常状態パスは、監視プレフィックス決定部１４へ出力される。
【００６８】
パステーブルは、正常状態パス上の各リンクの上流側ノード装置から広報される監視プレフックス毎に、パス列を記録する。そして、当該パス列が、正常状態パス上から外れた時の発生時刻を記録する。また、当該パス列が、正常状態パス上へ戻った時の復旧時刻も記録する。
【００６９】
監視プレフィックス決定部１４は、管理元ノード装置のプレフィックスに対する正常状態パスにおけるノード装置間のリンク毎に、当該リンクの上流側ノード装置から広報されるプレフィックスを監視プレフィックスとして決定する。
【００７０】
監視対象抽出１５は、監視プレフィックスを含むUPDATEメッセージのみを、零リンク抽出部１６へ出力する。
【００７１】
零リンク抽出部１６は、各検出時刻について、正常状態パス上のリンク毎に監視プレフックス数を計数し、該監視プレフックス数が有値から零へ変化した零リンクを抽出する。ここで、正常状態パス決定部１３から出力されたパステーブルを参照し、発生時刻及び復旧時刻を、零リンクに対応付ける。
【００７２】
クラスタリング部１７は、検出時刻の先頭の零リンクから順に、当該零リンクの検出時刻から所定分類時間範囲ｄ以内の１つ以上の零リンク群であって、同一の零リンクが含まれる場合、後の検出時刻の零リンク以降を別の零リンク群として、クラスタに分割する。クラスタ毎に、障害リンク検出部１８へ出力される。
【００７３】
障害リンク検出部１８は、クラスタに含まれる零リンクの中で、観測ノード装置に最も近いリンクを、障害箇所として決定する。また、クラスタに含まれる零リンクの中で、発生時刻が最も早い時点に、障害が発生したと推定する。更に、クラスタに含まれる零リンクの中で、復旧時刻が最も遅い時点に、障害が復旧したと推定する。
【００７４】
以上、詳細に説明したように、本発明の障害リンク検出方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視すると共に、プレフィックスの伝搬遅延を考慮して、実際に発生した障害リンクを検出することができる。単一リンクで発生した障害により他のリンクが異なる時刻で検出されたとしても、プレフィックスの伝搬に対する個々の影響を分類することができる。
【００７５】
前述した本発明の種々の実施形態によれば、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７６】
１  ノード装置
１０  中継転送部
１１  経路更新メッセージ送信部
１２  経路更新メッセージ受信監視部
１３  正常状態パス決定部
１４  監視プレフィックス決定部
１５  監視対象抽出部
１６  零リンク抽出部
１７  クラスタリング部
１８  障害リンク検出部
２  障害リンク検出装置
【図１】
2011166248.tif 000003
【図２】
2011166248.tif 000004
【図３】
2011166248.tif 000005
【図４】
2011166248.tif 000006
【図５】
2011166248.tif 000007
【図６】
2011166248.tif 000008
【図７】
2011166248.tif 000009