経路制御プロトコルに基づいて障害リンクを検出する方法、ノード装置及びプログラム
【課題】経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、少ない計算量で且つリアルタイムに障害リンクを検出する方法等を提供する。
【解決手段】最初に、パスリストを用いて障害候補リンクを選択する。次に、障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する。次に、最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。そして、他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとしてステップを繰り返し、検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【解決手段】最初に、パスリストを用いて障害候補リンクを選択する。次に、障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する。次に、最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。そして、他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとしてステップを繰り返し、検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づいて障害リンクを検出する方法、ノード装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットでは、経路制御プロトコルを用いて、ノード装置（例えばルータ）がパケットを適切に中継転送する。代表的な経路制御プロトコルとして、インターネット上で組織間の経路情報を交換する「ＢＧＰ(Border Gateway Protocol)」がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一の「ＡＳ(Autonomous System)番号」が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
このような経路制御プロトコルに基づくネットワークについて、障害リンクを検出するために、従来、ネットワークにプローブ装置が設置されていた。そのプローブ装置が、多数のノード間を流れる経路更新メッセージを監視することによって、障害リンクを解析する。特に、経路更新メッセージを、大量に収集し且つクラスタリングすることによって、障害リンクを解析する技術がある（例えば特許文献１参照）。この技術によれば、障害発生の前後の経路更新メッセージに含まれるプレフィックス及びＡＳパスリストが用いられる。ＡＳパスリストの変化を解析することによって、同時間帯に変化した多数のプレフィックスをクラスタリングする。これによって、共通のＡＳパスのリンクを抽出し、障害リンクを検出する。
【０００４】
図１は、従来技術におけるネットワーク構成図及びテーブルである。
【０００５】
図１によれば、ＢＧＰを用いて、ＡＳ番号を有する９台のノード装置１(AS10〜AS90)が相互に接続されている。各ノード装置は、送信元アドレス（送信元ネットワークプレフィックス）及びＡＳ番号を含むUPDATEメッセージを、定期的にブロードキャストで送信する。UPDATEメッセージには、以下のパラメータが含まれる。
（１）プレフィックス
（２）メッセージ種別
（３）AS_PATH属性
「プレフィックス」は、ＩＰアドレス及びサブネットマスクの組(xxx.xxx.xxx.xxx/xx)であって、送信元ネットワークアドレス（又は送信元ノード装置のアドレス）を表す。
「メッセージ種別」は、経路更新(Announce)を表す。
「AS_PATH属性」は、プレフィックスからの到達経路のパスリスト（ＡＳ番号の列）を表す。
【０００６】
各ノード装置は、UPDATEメッセージを受信した際に、そのUPDATEメッセージのパスリストに、更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。これらUPDATEメッセージは、観測ノード装置AS10によって受信される。
【０００７】
観測ノード装置は、ＲＩＢ(Routing Information Base)と称されるパス（経路）テーブルと、リンクテーブルとを有する。ここで、「パス」とは、送信元ノード装置と宛先ノード装置との間の経路であって、中継ノード装置を介した接続を意味する。また、「リンク」とは、直接的に接続される隣接ノード装置間の接続を意味する。
【０００８】
パステーブルは、１つのパスを、複数のリンクのリストによって構成する。パステーブルは、少なくとも、送信元アドレスの集合を表す「プレフィックス」と、そのプレフィックスに到達するための中継ノード装置の「ＡＳ番号のパスリスト」とが含まれる。「プレフィックス」とは、ＩＰアドレスとサブネットマスクのビット数との組を表す。
【０００９】
パステーブルは、ノード装置間で、「経路更新メッセージ(UPDATE)」を定期的に交換することによって更新される。図１によれば、パステーブルには、受信したUPDATEメッセージのプレフィックス毎に、ＡＳパスリストが記録される。
【００１０】
また、リンクテーブルには、リンク毎に、評価時間Ｔにおける、UPDATEメッセージを受信したプレフィックスの数が表されている。ここで、リンクのプレフィックス数が０になった場合、障害リンクと判定される。図１によれば、リンク(AS20,AS30)は、プレフィックス数３である。また、リンク(AS30,AS40)、リンク(AS30,AS50)及びリンク(AS30,AS60)は、プレフィックス数１である。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００６−１３５７５６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、特許文献１に記載された技術によれば、大量の経路更新メッセージをデータベースに収集した上で、クラスタリング（例えばデンドログラム）のための複雑なアルゴリズムを必要とする。そのために、ネットワークの規模に応じて、膨大な計算量を必要とし、リアルタイムに障害リンクを検出することはできなかった。また、複数の障害リンクが同一時間帯に発生した場合、クラスタリングによって特定の障害リンクを検出できないという課題も生じていた。そのために、短い時間帯に区切って、クラスタリングを実行し、障害リンクを検出していた。
【００１３】
図２は、従来技術における障害リンクを含むネットワーク構成図及びテーブルである。
【００１４】
図２によれば、リンク(AS20,AS30)のみに、実際に障害が発生している。この場合、ノード装置AS40,AS50,AS60からのUPDATEメッセージが受信できなくなる。最初に、ノード装置AS40からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS40)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が２に減分される。次に、ノード装置AS50からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS50)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が１に減分される。更に、ノード装置AS60からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS60)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が０に減分される。プレフィックス数が０となったリンクは、障害リンクとして検出される。
【００１５】
図２からも明らかなとおり、リンク(AS20,AS30)にしか障害が発生していないにも関わらず、リンク(AS30,AS40)、リンク(AS30,AS50)及びリンク(AS30,AS60)も、障害リンクとして検出される。即ち、観測ノード装置から見て、実際の障害リンクよりも上流のリンクも障害リンクとして検出してしまう。
【００１６】
また、図２によれば、リンクテーブルに記録されるプレフィックス数は、観測ノード装置から見て、遠いリンクから順に０となっていく。
【００１７】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明によれば、固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置の障害リンク検出方法において、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する第４のステップと
を有することを特徴とする。
【００１９】
本発明の障害リンク検出方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００２０】
本発明の障害リンク検出方法における他の実施形態によれば、
第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、経路更新メッセージの送信時間間隔に応じて制御されることも好ましい。
【００２１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する障害候補リンク選択手段と、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する上流障害リンク検出手段と、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する下流障害リンク検出手段と、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして上流障害リンク検出手段へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する障害リンク確定手段と
を有することを特徴とする。
【００２２】
本発明のノード装置における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００２３】
本発明のノード装置における他の実施形態によれば、第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、経路更新メッセージの送信時間間隔に応じて制御する判定時間制御手段を更に有することも好ましい。
【００２４】
本発明によれば、固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置に搭載されたコンピュータを実行させる障害リンク検出プログラムであって、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する第４のステップと
してコンピュータを実行させることを特徴とする。
【発明の効果】
【００２５】
本発明の障害リンク検出方法、ノード装置及びプログラムによれば、上流障害リンクと下流障害リンクとを別々に検出することによって、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる。
【図面の簡単な説明】
【００２６】
【図１】従来技術におけるネットワーク構成図及びテーブルである。
【図２】従来技術における障害リンクを含むネットワーク構成図及びテーブルである。
【図３】本発明におけるノード装置のフローチャートである。
【図４】図３のＳ３１における時刻T1のネットワーク構成図である。
【図５】図３のＳ３２における時刻T1＋αのネットワーク構成図である。
【図６】図３のＳ３３における時刻T2＋βのネットワーク構成図である。
【図７】本発明における障害リンクを含むネットワーク構成図である。
【図８】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２７】
以下では、本発明を実施するための形態について、図面を用いて詳細に説明する。
【００２８】
本発明によれば、観測ノード装置から見て、遠いリンクを「上流リンク」と定義し、近いリンク「下流リンク」と定義する。また、「リンク(X,Y)」記載した場合、Xを下流ノード装置と定義し、Yを上流ノード装置と定義する。
【００２９】
図２からも明らかなとおり、リンクテーブルに記録されるプレフィックス数は、観測ノード装置から見て、遠いリンクから順に０となっていく。本発明によれば、上流障害リンクと下流障害リンクとを別々に検出することによって、実際に発生した障害リンクを特定する。
【００３０】
図３は、本発明におけるノード装置のフローチャートである。
【００３１】
（Ｓ３１）送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを「障害候補リンク」として選択する。
【００３２】
図４は、図３のＳ３１における時刻T1のネットワーク構成図である。
【００３３】
図４によれば、リンク(AS20,AS30)は、リンク(AS30,AS40)に対して、下流リンクとなる。観測ノード装置は、当初、ノード装置AS40,AS50,AS60からのUPDATEメッセージを受信し続けていたとする。これによって、パステーブルには、ノード装置AS40からのプレフィックス数が記録されている。
【００３４】
その後、観測ノード装置は、ノード装置AS40からのUPDATEメッセージを受信できなくなったとする。このとき、パステーブルについて、ノード装置AS40のプレフィックス（送信元アドレス）に対応するＡＳパスリストは、「不用」に設定される。また、リンクテーブルについて、リンク(AS30,AS40)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が２に減分される。リンク(AS30,AS40)には、障害が発生したものとして、障害検出時刻T1が記録される。そして、リンク(AS30,AS40)は、「障害候補リンク」として選択される。
【００３５】
（Ｓ３２）障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出する。また、検出された他の障害リンクの中で、最新障害検出時刻を検出する。
【００３６】
図５は、図３のＳ３２における時刻T1＋αのネットワーク構成図である。
【００３７】
図５によれば、観測ノード装置は、リンク(AS30,AS40)（障害候補リンク）の障害検出時刻T1から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置AS30を、下流ノード装置とする他の障害リンクを検出する。
【００３８】
図５によれば、時刻T1〜時刻T1＋αに、ノード装置AS50からのUPDATEメッセージと、ノード装置AS60からのUPDATEメッセージとが、受信できなくなったとする。このとき、パステーブルについて、ノード装置AS50及びノード装置AS60のプレフィックスに対応するＡＳパスリストは、「不用」に設定される。また、リンクテーブルについて、(AS30,AS50)のプレフィックス数が０に減分され、リンク(AS30,AS60)のプレフィックス数が０になり、リンク(AS20,AS30)のプレフィックス数が０に減分される。これによって、リンク(AS30,AS50)、リンク(AS30,AS60)及びリンク(AS20,AS30)が、障害リンクとして検出される。
【００３９】
その中で、ノード装置AS30を、下流ノード装置とするリンクとしては、リンク(AS30,50)及びリンク(AS30,60)がある。結局、リンク(AS30,AS50)及びリンク(AS30,AS60)が検出される。
【００４０】
次に、検出された他の障害リンクの中で、最新障害検出時刻を検出する。図４によれば、リンク(AS30,60)の障害を検出した時刻T2が、最新障害検出時刻であるとする。
【００４１】
（Ｓ３３）最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。
【００４２】
図６は、図３のＳ３３における時刻T2＋βのネットワーク構成図である。
【００４３】
図６によれば、最新障害検出時刻T2から第２の所定時間β内に発生した他の障害リンクであって、且つ、リンク(AS30,AS40)（障害候補リンク）の下流ノード装置AS30を、上流ノード装置とする他の障害リンク(AS20,AS30)を検出する。ここで、図６によれば、最新障害検出時刻T2と、障害リンク(AS20,AS30)の障害検出時刻とは、同じである。
【００４４】
（Ｓ３４）他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとしてＳ３２へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【００４５】
図７は、図３のＳ３４によって確定した障害リンクを含むネットワーク構成図である。
【００４６】
図７によれば、リンク(AS20,AS30)を、障害候補として、Ｓ３２〜Ｓ３３の処理を実行するが、リンク(AS20,AS30)以外に、他の障害リンクは検出されない。これによって、リンク(AS20,AS30)が最も下流にあり、当該リンク(AS20,AS30)に障害が発生したことを特定することができる。
【００４７】
図４〜図６について、以下のような時刻の関係が成立する。
最初の障害候補リンクの障害発生時刻：T1
上流障害リンクの最新障害発生時刻： T2
下流障害リンクの障害発生時刻： T3
T1≦T3、T2≦T3
【００４８】
仮に、T1＝T2＝T3の場合、本発明によって確定される障害リンクは、同様に、リンク(20,30)である。
また、仮に、以下のような時刻関係であっても、本発明によって確定される障害リンクは、同様に、リンク(20,30)である。
T1＜T3、T2＜T3、T1＜T2
T2≦T1＋α、T3≦T2＋α＋β
尚、図４〜図６は、T1＜T2＝T3の関係にある。
【００４９】
ここで、第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、UPDATEメッセージの送信時間間隔に応じて制御されるものであってもよい。例えば、障害リンクの発生頻度が相対的に多い場合、及び／又は、UPDATEメッセージの送信時間間隔が相対的に短い場合、α及びβは相対的に短く設定される。
【００５０】
図８は、本発明におけるノード装置の機能構成図である。
【００５１】
図８によれば、ノード装置１は、中継転送部１０と、経路更新メッセージ送信部１１と、経路更新メッセージ受信監視部１２と、パステーブル１３と、リンクテーブル１４と、障害候補リンク選択部１５と、上流障害リンク検出部１６と、下流障害リンク検出部１７と、障害リンク確定部１８と、判定時間制御部１９とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、中継転送部１０を除くこれらの機能を、パステーブル１３及びリンクテーブル１４を予め蓄積した障害リンク検出装置２に搭載することもできる。これによって、予め蓄積されたログファイルを用いて、障害リンクを特定することもできる。
【００５２】
中継転送部１０は、UPDATE(Announce)メッセージを受信した際に、そのパスリストに更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。
【００５３】
経路更新メッセージ送信部１１は、ＢＧＰに基づいて、プレフィックス（送信元アドレス）及びＡＳ番号（固有識別番号）を含むUPDATEメッセージを、定期的にブロードキャストで送信する。
【００５４】
経路更新メッセージ受信監視部１２は、中継転送部１０から抽出したＢＧＰのUPDATEメッセージを、パステーブル１３へ出力する。
【００５５】
パステーブル１３は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストを記録する。
【００５６】
リンクテーブル１４は、隣接するノード装置間のリンク毎に、パステーブル１３に記録されたパスリストが通過するプレフィックス数を記録する。
【００５７】
障害候補リンク選択部１５は、送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する。
【００５８】
上流障害リンク検出部１６は、障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出する。そして、検出された他の障害リンクの中で、最新障害検出時刻を検出する。
【００５９】
下流障害リンク検出部１７は、最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。
【００６０】
障害リンク確定部１８は、他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして上流障害リンク検出部１６へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【００６１】
判定時間制御部１９は、第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御する。
【００６２】
以上、詳細に説明したように、本発明の障害リンク検出方法、ノード装置及びプログラムによれば、上流障害リンクと下流障害リンクとを別々に検出することによって、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる。
【００６３】
本発明によれば、観測ノード装置で計測したＢＧＰのUPFATEメッセージを用いて、リンクを通過するプレフィックス数を監視し、上流障害リンクと下流障害リンクとの時刻差から、下流に生じた障害リンクを特定することができる。
【００６４】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６５】
１ ノード装置
１０ 中継転送部
１１ 経路更新メッセージ送信部
１２ 経路更新メッセージ受信監視部
１３ パステーブル
１４ リンクテーブル
１５ 障害候補リンク選択部
１６ 上流障害リンク検出部
１７ 下流障害リンク検出部
１８ 障害リンク確定部
１９ 判定時間制御部
２ 障害リンク検出装置
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づいて障害リンクを検出する方法、ノード装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットでは、経路制御プロトコルを用いて、ノード装置（例えばルータ）がパケットを適切に中継転送する。代表的な経路制御プロトコルとして、インターネット上で組織間の経路情報を交換する「ＢＧＰ(Border Gateway Protocol)」がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一の「ＡＳ(Autonomous System)番号」が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
このような経路制御プロトコルに基づくネットワークについて、障害リンクを検出するために、従来、ネットワークにプローブ装置が設置されていた。そのプローブ装置が、多数のノード間を流れる経路更新メッセージを監視することによって、障害リンクを解析する。特に、経路更新メッセージを、大量に収集し且つクラスタリングすることによって、障害リンクを解析する技術がある（例えば特許文献１参照）。この技術によれば、障害発生の前後の経路更新メッセージに含まれるプレフィックス及びＡＳパスリストが用いられる。ＡＳパスリストの変化を解析することによって、同時間帯に変化した多数のプレフィックスをクラスタリングする。これによって、共通のＡＳパスのリンクを抽出し、障害リンクを検出する。
【０００４】
図１は、従来技術におけるネットワーク構成図及びテーブルである。
【０００５】
図１によれば、ＢＧＰを用いて、ＡＳ番号を有する９台のノード装置１(AS10〜AS90)が相互に接続されている。各ノード装置は、送信元アドレス（送信元ネットワークプレフィックス）及びＡＳ番号を含むUPDATEメッセージを、定期的にブロードキャストで送信する。UPDATEメッセージには、以下のパラメータが含まれる。
（１）プレフィックス
（２）メッセージ種別
（３）AS_PATH属性
「プレフィックス」は、ＩＰアドレス及びサブネットマスクの組(xxx.xxx.xxx.xxx/xx)であって、送信元ネットワークアドレス（又は送信元ノード装置のアドレス）を表す。
「メッセージ種別」は、経路更新(Announce)を表す。
「AS_PATH属性」は、プレフィックスからの到達経路のパスリスト（ＡＳ番号の列）を表す。
【０００６】
各ノード装置は、UPDATEメッセージを受信した際に、そのUPDATEメッセージのパスリストに、更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。これらUPDATEメッセージは、観測ノード装置AS10によって受信される。
【０００７】
観測ノード装置は、ＲＩＢ(Routing Information Base)と称されるパス（経路）テーブルと、リンクテーブルとを有する。ここで、「パス」とは、送信元ノード装置と宛先ノード装置との間の経路であって、中継ノード装置を介した接続を意味する。また、「リンク」とは、直接的に接続される隣接ノード装置間の接続を意味する。
【０００８】
パステーブルは、１つのパスを、複数のリンクのリストによって構成する。パステーブルは、少なくとも、送信元アドレスの集合を表す「プレフィックス」と、そのプレフィックスに到達するための中継ノード装置の「ＡＳ番号のパスリスト」とが含まれる。「プレフィックス」とは、ＩＰアドレスとサブネットマスクのビット数との組を表す。
【０００９】
パステーブルは、ノード装置間で、「経路更新メッセージ(UPDATE)」を定期的に交換することによって更新される。図１によれば、パステーブルには、受信したUPDATEメッセージのプレフィックス毎に、ＡＳパスリストが記録される。
【００１０】
また、リンクテーブルには、リンク毎に、評価時間Ｔにおける、UPDATEメッセージを受信したプレフィックスの数が表されている。ここで、リンクのプレフィックス数が０になった場合、障害リンクと判定される。図１によれば、リンク(AS20,AS30)は、プレフィックス数３である。また、リンク(AS30,AS40)、リンク(AS30,AS50)及びリンク(AS30,AS60)は、プレフィックス数１である。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００６−１３５７５６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、特許文献１に記載された技術によれば、大量の経路更新メッセージをデータベースに収集した上で、クラスタリング（例えばデンドログラム）のための複雑なアルゴリズムを必要とする。そのために、ネットワークの規模に応じて、膨大な計算量を必要とし、リアルタイムに障害リンクを検出することはできなかった。また、複数の障害リンクが同一時間帯に発生した場合、クラスタリングによって特定の障害リンクを検出できないという課題も生じていた。そのために、短い時間帯に区切って、クラスタリングを実行し、障害リンクを検出していた。
【００１３】
図２は、従来技術における障害リンクを含むネットワーク構成図及びテーブルである。
【００１４】
図２によれば、リンク(AS20,AS30)のみに、実際に障害が発生している。この場合、ノード装置AS40,AS50,AS60からのUPDATEメッセージが受信できなくなる。最初に、ノード装置AS40からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS40)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が２に減分される。次に、ノード装置AS50からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS50)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が１に減分される。更に、ノード装置AS60からのUPDATEメッセージが受信できなくなった場合、リンク(AS30,AS60)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が０に減分される。プレフィックス数が０となったリンクは、障害リンクとして検出される。
【００１５】
図２からも明らかなとおり、リンク(AS20,AS30)にしか障害が発生していないにも関わらず、リンク(AS30,AS40)、リンク(AS30,AS50)及びリンク(AS30,AS60)も、障害リンクとして検出される。即ち、観測ノード装置から見て、実際の障害リンクよりも上流のリンクも障害リンクとして検出してしまう。
【００１６】
また、図２によれば、リンクテーブルに記録されるプレフィックス数は、観測ノード装置から見て、遠いリンクから順に０となっていく。
【００１７】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明によれば、固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置の障害リンク検出方法において、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する第４のステップと
を有することを特徴とする。
【００１９】
本発明の障害リンク検出方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００２０】
本発明の障害リンク検出方法における他の実施形態によれば、
第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、経路更新メッセージの送信時間間隔に応じて制御されることも好ましい。
【００２１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する障害候補リンク選択手段と、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する上流障害リンク検出手段と、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する下流障害リンク検出手段と、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして上流障害リンク検出手段へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する障害リンク確定手段と
を有することを特徴とする。
【００２２】
本発明のノード装置における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００２３】
本発明のノード装置における他の実施形態によれば、第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、経路更新メッセージの送信時間間隔に応じて制御する判定時間制御手段を更に有することも好ましい。
【００２４】
本発明によれば、固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置に搭載されたコンピュータを実行させる障害リンク検出プログラムであって、
送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する第４のステップと
してコンピュータを実行させることを特徴とする。
【発明の効果】
【００２５】
本発明の障害リンク検出方法、ノード装置及びプログラムによれば、上流障害リンクと下流障害リンクとを別々に検出することによって、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる。
【図面の簡単な説明】
【００２６】
【図１】従来技術におけるネットワーク構成図及びテーブルである。
【図２】従来技術における障害リンクを含むネットワーク構成図及びテーブルである。
【図３】本発明におけるノード装置のフローチャートである。
【図４】図３のＳ３１における時刻T1のネットワーク構成図である。
【図５】図３のＳ３２における時刻T1＋αのネットワーク構成図である。
【図６】図３のＳ３３における時刻T2＋βのネットワーク構成図である。
【図７】本発明における障害リンクを含むネットワーク構成図である。
【図８】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２７】
以下では、本発明を実施するための形態について、図面を用いて詳細に説明する。
【００２８】
本発明によれば、観測ノード装置から見て、遠いリンクを「上流リンク」と定義し、近いリンク「下流リンク」と定義する。また、「リンク(X,Y)」記載した場合、Xを下流ノード装置と定義し、Yを上流ノード装置と定義する。
【００２９】
図２からも明らかなとおり、リンクテーブルに記録されるプレフィックス数は、観測ノード装置から見て、遠いリンクから順に０となっていく。本発明によれば、上流障害リンクと下流障害リンクとを別々に検出することによって、実際に発生した障害リンクを特定する。
【００３０】
図３は、本発明におけるノード装置のフローチャートである。
【００３１】
（Ｓ３１）送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを「障害候補リンク」として選択する。
【００３２】
図４は、図３のＳ３１における時刻T1のネットワーク構成図である。
【００３３】
図４によれば、リンク(AS20,AS30)は、リンク(AS30,AS40)に対して、下流リンクとなる。観測ノード装置は、当初、ノード装置AS40,AS50,AS60からのUPDATEメッセージを受信し続けていたとする。これによって、パステーブルには、ノード装置AS40からのプレフィックス数が記録されている。
【００３４】
その後、観測ノード装置は、ノード装置AS40からのUPDATEメッセージを受信できなくなったとする。このとき、パステーブルについて、ノード装置AS40のプレフィックス（送信元アドレス）に対応するＡＳパスリストは、「不用」に設定される。また、リンクテーブルについて、リンク(AS30,AS40)のプレフィックス数が０に減分され、リンク(AS20,AS30)のプレフィックス数が２に減分される。リンク(AS30,AS40)には、障害が発生したものとして、障害検出時刻T1が記録される。そして、リンク(AS30,AS40)は、「障害候補リンク」として選択される。
【００３５】
（Ｓ３２）障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出する。また、検出された他の障害リンクの中で、最新障害検出時刻を検出する。
【００３６】
図５は、図３のＳ３２における時刻T1＋αのネットワーク構成図である。
【００３７】
図５によれば、観測ノード装置は、リンク(AS30,AS40)（障害候補リンク）の障害検出時刻T1から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置AS30を、下流ノード装置とする他の障害リンクを検出する。
【００３８】
図５によれば、時刻T1〜時刻T1＋αに、ノード装置AS50からのUPDATEメッセージと、ノード装置AS60からのUPDATEメッセージとが、受信できなくなったとする。このとき、パステーブルについて、ノード装置AS50及びノード装置AS60のプレフィックスに対応するＡＳパスリストは、「不用」に設定される。また、リンクテーブルについて、(AS30,AS50)のプレフィックス数が０に減分され、リンク(AS30,AS60)のプレフィックス数が０になり、リンク(AS20,AS30)のプレフィックス数が０に減分される。これによって、リンク(AS30,AS50)、リンク(AS30,AS60)及びリンク(AS20,AS30)が、障害リンクとして検出される。
【００３９】
その中で、ノード装置AS30を、下流ノード装置とするリンクとしては、リンク(AS30,50)及びリンク(AS30,60)がある。結局、リンク(AS30,AS50)及びリンク(AS30,AS60)が検出される。
【００４０】
次に、検出された他の障害リンクの中で、最新障害検出時刻を検出する。図４によれば、リンク(AS30,60)の障害を検出した時刻T2が、最新障害検出時刻であるとする。
【００４１】
（Ｓ３３）最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。
【００４２】
図６は、図３のＳ３３における時刻T2＋βのネットワーク構成図である。
【００４３】
図６によれば、最新障害検出時刻T2から第２の所定時間β内に発生した他の障害リンクであって、且つ、リンク(AS30,AS40)（障害候補リンク）の下流ノード装置AS30を、上流ノード装置とする他の障害リンク(AS20,AS30)を検出する。ここで、図６によれば、最新障害検出時刻T2と、障害リンク(AS20,AS30)の障害検出時刻とは、同じである。
【００４４】
（Ｓ３４）他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとしてＳ３２へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【００４５】
図７は、図３のＳ３４によって確定した障害リンクを含むネットワーク構成図である。
【００４６】
図７によれば、リンク(AS20,AS30)を、障害候補として、Ｓ３２〜Ｓ３３の処理を実行するが、リンク(AS20,AS30)以外に、他の障害リンクは検出されない。これによって、リンク(AS20,AS30)が最も下流にあり、当該リンク(AS20,AS30)に障害が発生したことを特定することができる。
【００４７】
図４〜図６について、以下のような時刻の関係が成立する。
最初の障害候補リンクの障害発生時刻：T1
上流障害リンクの最新障害発生時刻： T2
下流障害リンクの障害発生時刻： T3
T1≦T3、T2≦T3
【００４８】
仮に、T1＝T2＝T3の場合、本発明によって確定される障害リンクは、同様に、リンク(20,30)である。
また、仮に、以下のような時刻関係であっても、本発明によって確定される障害リンクは、同様に、リンク(20,30)である。
T1＜T3、T2＜T3、T1＜T2
T2≦T1＋α、T3≦T2＋α＋β
尚、図４〜図６は、T1＜T2＝T3の関係にある。
【００４９】
ここで、第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、UPDATEメッセージの送信時間間隔に応じて制御されるものであってもよい。例えば、障害リンクの発生頻度が相対的に多い場合、及び／又は、UPDATEメッセージの送信時間間隔が相対的に短い場合、α及びβは相対的に短く設定される。
【００５０】
図８は、本発明におけるノード装置の機能構成図である。
【００５１】
図８によれば、ノード装置１は、中継転送部１０と、経路更新メッセージ送信部１１と、経路更新メッセージ受信監視部１２と、パステーブル１３と、リンクテーブル１４と、障害候補リンク選択部１５と、上流障害リンク検出部１６と、下流障害リンク検出部１７と、障害リンク確定部１８と、判定時間制御部１９とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、中継転送部１０を除くこれらの機能を、パステーブル１３及びリンクテーブル１４を予め蓄積した障害リンク検出装置２に搭載することもできる。これによって、予め蓄積されたログファイルを用いて、障害リンクを特定することもできる。
【００５２】
中継転送部１０は、UPDATE(Announce)メッセージを受信した際に、そのパスリストに更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。
【００５３】
経路更新メッセージ送信部１１は、ＢＧＰに基づいて、プレフィックス（送信元アドレス）及びＡＳ番号（固有識別番号）を含むUPDATEメッセージを、定期的にブロードキャストで送信する。
【００５４】
経路更新メッセージ受信監視部１２は、中継転送部１０から抽出したＢＧＰのUPDATEメッセージを、パステーブル１３へ出力する。
【００５５】
パステーブル１３は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストを記録する。
【００５６】
リンクテーブル１４は、隣接するノード装置間のリンク毎に、パステーブル１３に記録されたパスリストが通過するプレフィックス数を記録する。
【００５７】
障害候補リンク選択部１５は、送信元アドレス毎のパスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する。
【００５８】
上流障害リンク検出部１６は、障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出する。そして、検出された他の障害リンクの中で、最新障害検出時刻を検出する。
【００５９】
下流障害リンク検出部１７は、最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する。
【００６０】
障害リンク確定部１８は、他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして上流障害リンク検出部１６へ移行し、他の障害リンクが検出されなかった場合、障害候補リンクを障害リンクとして確定する。
【００６１】
判定時間制御部１９は、第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御する。
【００６２】
以上、詳細に説明したように、本発明の障害リンク検出方法、ノード装置及びプログラムによれば、上流障害リンクと下流障害リンクとを別々に検出することによって、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、実際に発生した障害リンクを特定することができる。
【００６３】
本発明によれば、観測ノード装置で計測したＢＧＰのUPFATEメッセージを用いて、リンクを通過するプレフィックス数を監視し、上流障害リンクと下流障害リンクとの時刻差から、下流に生じた障害リンクを特定することができる。
【００６４】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６５】
１ ノード装置
１０ 中継転送部
１１ 経路更新メッセージ送信部
１２ 経路更新メッセージ受信監視部
１３ パステーブル
１４ リンクテーブル
１５ 障害候補リンク選択部
１６ 上流障害リンク検出部
１７ 下流障害リンク検出部
１８ 障害リンク確定部
１９ 判定時間制御部
２ 障害リンク検出装置
【特許請求の範囲】
【請求項１】
固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
前記ノード装置の障害リンク検出方法において、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する第４のステップと
を有することを特徴とする障害リンク検出方法。
【請求項２】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項１に記載のノード装置の障害リンク検出方法。
【請求項３】
第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御されることを特徴とする請求項１又は２に記載の障害リンク検出方法。
【請求項４】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する障害候補リンク選択手段と、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する上流障害リンク検出手段と、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する下流障害リンク検出手段と、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして前記上流障害リンク検出手段へ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する障害リンク確定手段と
を有することを特徴とするノード装置。
【請求項５】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項４に記載のノード装置。
【請求項６】
第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御する判定時間制御手段を更に有することを特徴とする請求項４又は５に記載のノード装置。
【請求項７】
固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置に搭載されたコンピュータを実行させる障害リンク検出プログラムであって、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する第４のステップと
してコンピュータを実行させることを特徴とするノード装置の障害リンク検出プログラム。
【請求項１】
固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
前記ノード装置の障害リンク検出方法において、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する第４のステップと
を有することを特徴とする障害リンク検出方法。
【請求項２】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項１に記載のノード装置の障害リンク検出方法。
【請求項３】
第１の所定時間α及び第２の所定時間βは、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御されることを特徴とする請求項１又は２に記載の障害リンク検出方法。
【請求項４】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する障害候補リンク選択手段と、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する上流障害リンク検出手段と、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する下流障害リンク検出手段と、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして前記上流障害リンク検出手段へ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する障害リンク確定手段と
を有することを特徴とするノード装置。
【請求項５】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項４に記載のノード装置。
【請求項６】
第１の所定時間α及び第２の所定時間βを、障害リンクの発生頻度に応じて、及び／又は、前記経路更新メッセージの送信時間間隔に応じて制御する判定時間制御手段を更に有することを特徴とする請求項４又は５に記載のノード装置。
【請求項７】
固有識別番号を有する複数のノード装置が相互に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークであって、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
各ノード装置が、受信した前記経路更新メッセージに含まれる、中継ノード装置の固有識別番号の連続からなるパスリストに、更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する
ノード装置に搭載されたコンピュータを実行させる障害リンク検出プログラムであって、
送信元アドレス毎の前記パスリストを用いて障害リンク及び障害検出時刻を検出し、その障害リンクを障害候補リンクとして選択する第１のステップと、
前記障害候補リンクの障害検出時刻から第１の所定時間α内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、下流ノード装置とする他の障害リンクを検出し、検出された他の障害リンクの中で、最新障害検出時刻を検出する第２のステップと、
前記最新障害検出時刻から第２の所定時間β内に発生した他の障害リンクであって、且つ、前記障害候補リンクの下流ノード装置を、上流ノード装置とする他の障害リンクを検出する第３のステップと、
他の障害リンクが検出された場合、当該他の障害リンクを障害候補リンクとして第２のステップへ移行し、他の障害リンクが検出されなかった場合、前記障害候補リンクを障害リンクとして確定する第４のステップと
してコンピュータを実行させることを特徴とするノード装置の障害リンク検出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−２１３０１８（Ｐ２０１０−２１３０１８Ａ）
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願番号】特願２００９−５７２７０（Ｐ２００９−５７２７０）
【出願日】平成２１年３月１１日（２００９．３．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願日】平成２１年３月１１日（２００９．３．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]