(57)【要約】【課題】ＢＧＰ(Border Gateway Protocol)に基づくUPDATEを通常シーケンスで監視し、少ない計算量で且つリアルタイムに障害リンクを検出する方法等を提供する。【解決手段】ノード装置は、UPDATE(Announce)のプレフィックス毎に、中継されたノード装置のＡＳ(Autonomous System)番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、ノード装置間のリンク毎に、パス数を記録するパス数記録テーブルとを有する。ノード装置は、UPDATE(Announce)を受信した際に、そのパスリストと、パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定する。一致しない場合、パスリスト記録テーブルを新しいパスリストで更新すると共に、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分する。パス数が０に変化したリンクが、障害リンクとなる。【選択図】図１０
2010161524.tif 000002
【特許請求の範囲】
【請求項１】
固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークにおける前記ノード装置の障害リンク検出方法において、
前記ノード装置は、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルとを有しており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する第１のステップと、
前記ノード装置が、前記経路更新メッセージを受信した際に、そのパスリストに更に当該ノード装置の固有識別番号を含めた当該経路更新メッセージを中継転送する第２のステップと、
前記ノード装置が、前記経路更新メッセージを受信した際に、そのパスリストと、前記パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定し、一致しない場合、前記パスリスト記録テーブルを新しいパスリストで更新すると共に、前記パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分する第３のステップと、
前記ノード装置が、前記パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する第４のステップと
を有することを特徴とするノード装置の障害リンク検出方法。
【請求項２】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項１に記載のノード装置の障害リンク検出方法。
【請求項３】
障害リンクを検出したノード装置が、経路取消メッセージをブロードキャストで送信するステップと、
前記ノード装置が、前記経路取消メッセージを受信した際に、その送信元アドレスと一致するパスリストを、前記パスリスト記録テーブルから検索し、前記パスリスト記録テーブルから当該パスリストを削除すると共に、前記パス数記録テーブルについて経路取消のリンクのパス数を減分するステップと
を更に有することを特徴とする請求項１又は２に記載のノード装置の障害リンク検出方法。
【請求項４】
前記経路取消メッセージは、ＢＧＰのUPDATE(Withdraw)であることを特徴とする請求項３に記載のノード装置の障害リンク検出方法。
【請求項５】
固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて障害リンクを検出するノード装置において、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、
ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルと、
前記経路更新メッセージを受信した際に、そのパスリストと、前記パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定するパスリスト判定手段と、
前記パスリスト判定手段によって一致しないと判定された場合、前記パスリスト記録テーブルを新しいパスリストで更新するパスリスト更新手段と、
前記パスリスト判定手段によって一致しないと判定された場合、前記パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分するパス数更新手段と、
前記パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する障害リンク検出手段と
を有することを特徴とするノード装置。
【請求項６】
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
前記経路更新メッセージを受信した際に、そのパスリストに更に当該ノード装置の固有識別番号を含めた当該経路更新メッセージを中継転送する中継転送手段と
を更に有することを特徴とするノード装置。
【請求項７】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項５又は６に記載のノード装置。
【請求項８】
障害リンクを検出した際に、経路取消メッセージをブロードキャストで送信する経路取消メッセージ送信手段を更に有し、
前記パスリスト判定手段は、前記経路取消メッセージを受信した際に、その送信元アドレスと一致するパスリストを、前記パスリスト記録テーブルから検索し、
前記パスリスト更新手段は、前記パスリスト記録テーブルから当該パスリストを削除し、
前記パス数更新手段は、前記パス数記録テーブルについて経路取消のリンクのパス数を減分する
ことを特徴とする請求項５から７のいずれか１項に記載のノード装置。
【請求項９】
前記経路取消メッセージは、ＢＧＰのUPDATE(Withdraw)であることを特徴とする請求項８に記載のノード装置。
【請求項１０】
固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて障害リンクを検出するノード装置に搭載されたコンピュータを機能させるプログラムにおいて、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、
ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルと、
前記経路更新メッセージを受信した際に、そのパスリストと、前記パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定するパスリスト判定手段と、
前記パスリスト判定手段によって一致しないと判定された場合、前記パスリスト記録テーブルを新しいパスリストで更新するパスリスト更新手段と、
前記パスリスト判定手段によって一致しないと判定された場合、前記パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分するパス数更新手段と、
前記パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する障害リンク検出手段と
してコンピュータを機能させることを特徴とするノード装置用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づく障害リンク検出方法、ノード装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットでは、ノード装置（例えばルータ）がパケットを適切に中継転送するために、経路制御プロトコルが用いられる。代表的な経路制御プロトコルとして、インターネット上で組織間の経路情報を交換する「ＢＧＰ(Border Gateway Protocol)」がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一の「ＡＳ(Autonomous System)番号」が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
ＢＧＰ対応のノード装置は、ＲＩＢ(Routing Information Base)と称される経路テーブルを保持する。経路テーブルは、リンク（２つのノード装置の間の経路）のリストによって構成される。経路テーブルのリンクには、少なくとも、送信元／宛先アドレスの集合を表す「プレフィックス」と、そのプレフィックスに到達するための中継ノード装置の「ＡＳ番号」とが含まれる。「プレフィックス」とは、ＩＰアドレスとサブネットマスクのビット数との組を表す。パケットの宛先アドレスを含むプレフィックスに対応したノード装置へ、そのパケットは中継転送される。経路テーブルは、ノード装置間で、「経路更新メッセージ(UPDATE)」を定期的に交換することによって更新される。
【０００４】
このような経路制御プロトコルに基づくネットワークについて、障害リンクを検出するために、従来、ネットワークにプローブ装置が設置されていた。そのプローブ装置が、多数のノード間を流れる経路更新メッセージを監視することによって、障害リンクを解析する。特に、経路更新メッセージを、大量に収集し且つクラスタリングすることによって、障害リンクを解析する技術がある（例えば特許文献１参照）。この技術によれば、障害発生の前後の経路更新メッセージに含まれるプレフィックス及びＡＳパスリストが用いられる。ここで、「パス」とは、２つのＡＳ間の接続関係を意味する。ＡＳパスリストの変化を解析することによって、同時間帯に変化した多数のプレフィックスをクラスタリングする。これによって、共通のＡＳパスのリンクを抽出し、障害リンクを検出する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３５７５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に記載された技術によれば、大量の経路更新メッセージをデータベースに収集した上で、クラスタリング（例えばデンドログラム）のための複雑なアルゴリズムを必要とする。そのために、ネットワークの規模に応じて、膨大な計算量を必要とし、リアルタイムに障害リンクを検出することはできなかった。また、複数の障害リンクが同一時間帯に発生した場合、クラスタリングによって特定の障害リンクを検出できないという課題も生じていた。そのために、短い時間帯に区切って、クラスタリングを実行し、障害リンクを検出していた。
【０００７】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、少ない計算量で且つリアルタイムに障害リンクを検出する方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明よれば、固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークにおけるノード装置の障害リンク検出方法において、
ノード装置は、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルとを有しており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する第１のステップと、
ノード装置が、経路更新メッセージを受信した際に、そのパスリストに更に当該ノード装置の固有識別番号を含めた当該経路更新メッセージを中継転送する第２のステップと、
ノード装置が、経路更新メッセージを受信した際に、そのパスリストと、パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定し、一致しない場合、パスリスト記録テーブルを新しいパスリストで更新すると共に、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分する第３のステップと、
ノード装置が、パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する第４のステップと
を有することを特徴とする。
【０００９】
本発明のノード装置の障害リンク検出方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれることも好ましい。
【００１０】
本発明のノード装置の障害リンク検出方法における他の実施形態によれば、
障害リンクを検出したノード装置が、経路取消メッセージをブロードキャストで送信するステップと、
ノード装置が、経路取消メッセージを受信した際に、その送信元アドレスと一致するパスリストを、パスリスト記録テーブルから検索し、パスリスト記録テーブルから当該パスリストを削除すると共に、パス数記録テーブルについて経路取消のリンクのパス数を減分するステップと
を更に有することも好ましい。
【００１１】
本発明のノード装置の障害リンク検出方法における他の実施形態によれば、経路取消メッセージは、ＢＧＰのUPDATE(Withdraw)であることも好ましい。
【００１２】
本発明によれば、固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて障害リンクを検出するノード装置において、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、
ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルと、
経路更新メッセージを受信した際に、そのパスリストと、パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定するパスリスト判定手段と、
パスリスト判定手段によって一致しないと判定された場合、パスリスト記録テーブルを新しいパスリストで更新するパスリスト更新手段と、
パスリスト判定手段によって一致しないと判定された場合、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分するパス数更新手段と、
パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する障害リンク検出手段と
を有することを特徴とする。
【００１３】
本発明のノード装置における他の実施形態によれば、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
経路更新メッセージを受信した際に、そのパスリストに更に当該ノード装置の固有識別番号を含めた当該経路更新メッセージを中継転送する中継転送手段と
を更に有することも好ましい。
【００１４】
本発明のノード装置における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれることも好ましい。
【００１５】
本発明のノード装置における他の実施形態によれば、
障害リンクを検出した際に、経路取消メッセージをブロードキャストで送信する経路取消メッセージ送信手段を更に有し、
パスリスト判定手段は、経路取消メッセージを受信した際に、その送信元アドレスと一致するパスリストを、パスリスト記録テーブルから検索し、
パスリスト更新手段は、パスリスト記録テーブルから当該パスリストを削除し、
パス数更新手段は、パス数記録テーブルについて経路取消のリンクのパス数を減分することも好ましい。
【００１６】
本発明のノード装置における他の実施形態によれば、経路取消メッセージは、ＢＧＰのUPDATE(Withdraw)であることも好ましい。
【００１７】
本発明によれば、固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて障害リンクを検出するノード装置に搭載されたコンピュータを機能させるプログラムにおいて、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなる直前のパスリストを記録するパスリスト記録テーブルと、
ノード装置間のリンク毎に、経路更新メッセージのパス数を記録するパス数記録テーブルと、
経路更新メッセージを受信した際に、そのパスリストと、パスリスト記録テーブルに記録された同一送信元アドレスにおける直前のパスリストとが一致するか否かを判定するパスリスト判定手段と、
パスリスト判定手段によって一致しないと判定された場合、パスリスト記録テーブルを新しいパスリストで更新するパスリスト更新手段と、
パスリスト判定手段によって一致しないと判定された場合、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分するパス数更新手段と、
パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する障害リンク検出手段と
してコンピュータを機能させることを特徴とするノード装置用のプログラム。
【発明の効果】
【００１８】
本発明の障害リンク検出方法、ノード装置及びプログラムによれば、プレフィックス毎の直前のパスリストを記憶するパスリスト記録テーブルと、リンク毎のパス数を増減させるパス数記録テーブルとを用いることにより、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、少ない計算量で且つリアルタイムに障害リンクを検出することができる。また、障害発生後の障害リンクを検出するだけでなく、迂回経路も検出することができる。
【図面の簡単な説明】
【００１９】
【図１】障害リンクが発生していない場合のネットワーク構成図である。
【図２】図１のネットワークについて、第１の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図３】図１のネットワークについて、第２の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図４】図１のネットワークについて、第３の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図５】図１のネットワークについて、第４の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図６】図１のネットワークについて、第５の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図７】図１のネットワークについて、第６の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図８】障害リンクが発生した場合のネットワーク構成図である。
【図９】図８のネットワークについて、第１、第２及び第４の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図１０】障害リンクが発生し、経路更新メッセージが迂回して転送された場合のネットワーク構成図である。
【図１１】図１０のネットワークについて、第３の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図１２】図１０のネットワークについて、第５の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図１３】図１０のネットワークについて、第６の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図１４】障害リンクが発生し、経路取消メッセージが迂回して転送された場合のネットワーク構成図である。
【図１５】図１４のネットワークについて、経路取消メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【図１６】障害発生前後におけるパス数の変化を表す説明図である。
【図１７】本発明における障害リンクを検出するフローチャートである。
【図１８】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２０】
以下では、本発明を実施するための形態について、図面を用いて詳細に説明する。
【００２１】
図１は、障害リンクが発生していない場合のネットワーク構成図である。
【００２２】
図１によれば、ＡＳ番号を有する複数のノード装置１（ＡＳ１０〜ＡＳ６０及び観測ＡＳ）がメッシュ状に接続されている。また、このネットワークシステムは、経路制御プロトコルであるＢＧＰによって構成されている。ここでは、観測ＡＳのノード装置によって受信される経路更新メッセージ又は経路取消メッセージに注目している。両メッセージは、ＢＧＰのUPDATEである。
【００２３】
UPDATEは、以下のパラメータを含む。
（１）プレフィックス（ＩＰアドレス及びサブネットマスクの組：xxx.xxx.xxx.xxx/xx）
（２）メッセージ種別（経路更新Announce／経路取消Withdraw）
（３）AS_PATH属性（パスリスト：プレフィックスへの到達経路を表すＡＳ番号の列）
（但し、Withdrawの場合、ＡＳパスリストは含まれない）
【００２４】
各ノード装置は、以下の経路更新メッセージを定期的にブロードキャストで送信している。
ＡＳ１０のノード装置  ：  第１の経路更新メッセージUPDATE1
ＡＳ２０のノード装置  ：  第２の経路更新メッセージUPDATE2
ＡＳ３０のノード装置  ：  第３の経路更新メッセージUPDATE3
ＡＳ４０のノード装置  ：  第４の経路更新メッセージUPDATE4
ＡＳ５０のノード装置  ：  第５の経路更新メッセージUPDATE5
ＡＳ６０のノード装置  ：  第６の経路更新メッセージUPDATE6
【００２５】
図１によれば、これら経路更新メッセージは、観測ＡＳのノード装置によって受信される。
UPDATE1  ：  プレフィックス[10.0.1.0/8]、パスリスト[20,10]
UPDATE2  ：  プレフィックス[11.0.1.0/8]、パスリスト[20]
UPDATE3  ：  プレフィックス[12.0.1.0/8]、パスリスト[20,30]
UPDATE4  ：  プレフィックス[13.0.1.0/8]、パスリスト[20,40]
UPDATE5  ：  プレフィックス[14.0.2.0/8]、パスリスト[20,30,50]
UPDATE6  ：  プレフィックス[15.0.2.0/8]、パスリスト[20,30,60]
【００２６】
図２は、図１のネットワークについて、第１の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第１の経路更新メッセージは、ノード装置ＡＳ１０から送信されたUPDATE(Announce)であって、プレフィックス[10.0.1.0/8]及びパスリスト[20,10]を含む。
【００２７】
パスリスト記録テーブルには、プレフィックス[10.0.1.0/8]が記録されていない。図２によれば、パスリスト記録テーブルに対して、プレフィックス[10.0.1.0/8]及びパスリスト[20,10]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20,10]に基づくリンク[AS10->AS20]及び[AS20->観測AS]のパス数を１増分する。
【００２８】
図３は、図１のネットワークについて、第２の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第２の経路更新メッセージは、ノード装置ＡＳ２０から送信されたUPDATE(Announce)であって、プレフィックス[11.0.1.0/8]及びパスリスト[20]を含む。
【００２９】
パスリスト記録テーブルには、プレフィックス[11.0.1.0/8]が記録されていない。図３によれば、パスリスト記録テーブルに対して、プレフィックス[11.0.1.0/8]及びパスリスト[20]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20]に基づくリンク[AS20->観測AS]のパス数を１増分する。
【００３０】
図４は、図１のネットワークについて、第３の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第３の経路更新メッセージは、ノード装置ＡＳ３０から送信されたUPDATE(Announce)であって、プレフィックス[12.0.1.0/8]及びパスリスト[20,30]を含む。
【００３１】
パスリスト記録テーブルには、プレフィックス[12.0.1.0/8]が記録されていない。図４によれば、パスリスト記録テーブルに対して、プレフィックス[12.0.1.0/8]及びパスリスト[20,30]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20,30]に基づくリンク[AS30->AS20]及び[AS20->観測AS]のパス数を１増分する。
【００３２】
図５は、図１のネットワークについて、第４の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第４の経路更新メッセージは、ノード装置ＡＳ４０から送信されたUPDATE(Announce)であって、プレフィックス[13.0.1.0/8]及びパスリスト[20,40]を含む。
【００３３】
パスリスト記録テーブルには、プレフィックス[13.0.1.0/8]が記録されていない。図５によれば、パスリスト記録テーブルに対して、プレフィックス[13.0.1.0/8]及びパスリスト[20,40]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20,40]に基づくリンク[AS40->AS20]及び[AS20->観測AS]のパス数を１増分する。
【００３４】
図６は、図１のネットワークについて、第５の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第５の経路更新メッセージは、ノード装置ＡＳ５０から送信されたUPDATE(Announce)であって、プレフィックス[14.0.2.0/8]及びパスリスト[20,30,50]を含む。
【００３５】
パスリスト記録テーブルには、プレフィックス[14.0.2.0/8]が記録されていない。図６によれば、パスリスト記録テーブルに対して、プレフィックス[14.0.2.0/8]及びパスリスト[20,30,50]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20,30,50]に基づくリンク[AS50->AS30]、[AS30->AS20]及び[AS20->観測AS]のパス数を１増分する。
【００３６】
図７は、図１のネットワークについて、第６の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。第６の経路更新メッセージは、ノード装置ＡＳ６０から送信されたUPDATE(Announce)であって、プレフィックス[15.0.2.0/8]及びパスリスト[20,30,60]を含む。
【００３７】
パスリスト記録テーブルには、プレフィックス[15.0.2.0/8]が記録されていない。図７によれば、パスリスト記録テーブルに対して、プレフィックス[15.0.2.0/8]及びパスリスト[20,30,60]が新たに記録される。また、パス数記録テーブルについて、パスリスト[20,30,60]に基づくリンク[AS60->AS30]、[AS30->AS20]及び[AS20->観測AS]のパス数を１増分する。
【００３８】
図８は、障害リンクが発生した場合のネットワーク構成図である。
【００３９】
図８によれば、ノード装置ＡＳ２０とＡＳ３０との間のリンクに、障害が発生している。このような場合であっても、第１、第２及び第４の経路更新メッセージは、経路を迂回することなく、転送される。
【００４０】
図９は、図８のネットワークについて、第１、第２及び第４の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【００４１】
ここで、パスリスト記録テーブルについて、第１の経路更新メッセージのプレフィックス[10.0.1.0/8]と、第２の経路更新メッセージのプレフィックス[11.0.1.0/8]と、第４の経路更新メッセージのプレフィックス[13.0.1.0/8]とが既に記録されている。また、パスリスト記録テーブルについて、プレフィックス[10.0.1.0/8]に対するパスリスト[20,10]と、プレフィックス[11.0.1.0/8]に対するパスリスト[20]と、プレフィックス[13.0.1.0/8]に対するパスリスト[20,40]とは、一致する。この場合、パスリスト記録テーブル及びパス数記録テーブルは、何ら更新されない。
【００４２】
図１０は、障害リンクが発生し、経路更新メッセージが迂回して転送される場合のネットワーク構成図である。
【００４３】
図１０によれば、図８と同様に、ノード装置ＡＳ２０とＡＳ３０との間のリンクに、障害が発生している。このような場合、ノード装置ＡＳ３０からＡＳ２０へ転送されるべき第３、第５及び第６の経路更新メッセージは、ノード装置ＡＳ４０を迂回して転送される。
【００４４】
図１１は、図１０のネットワークについて、第３の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【００４５】
ここで、パスリスト記録テーブルについて、第３の経路更新メッセージのプレフィックス[12.0.1.0/8]が既に記録されている。しかしながら、パスリスト記録テーブルについて、プレフィックス[12.0.1.0/8]に対するパスリスト[20,30]と、第３の経路更新メッセージのパスリスト[20,40,30]とは、一致しない。この場合、パスリスト記録テーブルにおけるプレフィックス[12.0.1.0/8]に対して、パスリスト[20,40,30]に更新する。
【００４６】
次に、パス数記録テーブルについて、パスリスト[20,40,30]に基づくリンク[AS30->AS40]、[AS40->AS20]及び[AS20->観測AS]のパス数を１増分する。また、過去のパスリスト[20,30]に基づくリンク[AS30->AS20]及び[AS20->観測AS]のパス数を１減分する。
【００４７】
図１２は、図１０のネットワークについて、第５の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【００４８】
ここで、パスリスト記録テーブルについて、第５の経路更新メッセージのプレフィックス[14.0.2.0/8]が既に記録されている。しかしながら、パスリスト記録テーブルについて、プレフィックス[14.0.2.0/8]に対するパスリスト[20,30,50]と、第３の経路更新メッセージのパスリスト[20,40,30,50]とは、一致しない。この場合、パスリスト記録テーブルにおけるプレフィックス[14.0.2.0/8]に対して、パスリスト[20,40,30,50]に更新する。
【００４９】
次に、パス数記録テーブルについて、パスリスト[20,40,30,50]に基づくリンク[AS50->AS30]、[AS30->AS40]、[AS40->AS20]及び[AS20->観測AS]のパス数を１増分する。また、過去のパスリスト[20,30,50]に基づくリンク[AS50->AS30]、[AS30->AS20]及び[AS20->観測AS]のパス数を１減分する。
【００５０】
図１３は、図１０のネットワークについて、第６の経路更新メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【００５１】
ここで、パスリスト記録テーブルについて、第６の経路更新メッセージのプレフィックス[15.0.2.0/8]が既に記録されている。しかしながら、パスリスト記録テーブルについて、プレフィックス[15.0.2.0/8]に対するパスリスト[20,30,60]と、第３の経路更新メッセージのパスリスト[20,40,30,60]とは、一致しない。この場合、パスリスト記録テーブルにおけるプレフィックス[15.0.2.0/8]に対して、パスリスト[20,40,30,60]に更新する。
【００５２】
次に、パス数記録テーブルについて、パスリスト[20,40,30,60]に基づくリンク[AS60->AS30]、[AS30->AS40]、[AS40->AS20]及び[AS20->観測AS]のパス数を１増分する。また、過去のパスリスト[20,30,60]に基づくリンク[AS60->AS30]、[AS30->AS20]及び[AS20->観測AS]のパス数を１減分する。
【００５３】
障害発生前の図７のパス数記録テーブルに対して、障害発生後の図１３のパス数記録テーブルは、[AS30->AS20]のパス数が０に変化している。これにより、[AS30->AS20]が、障害リンクとして検出される。逆に、[AS30->AS40]及び[AS30->AS40]のパス数が増加している。これにより、障害リンク[AS30->AS20]に対して、迂回経路が[AS30->AS40]及び[AS30->AS40]に設定されたが検出される。
【００５４】
図１４は、障害リンクが発生し、経路取消メッセージが迂回して転送された場合のネットワーク構成図である。
【００５５】
図１４によれば、ノード装置ＡＳ３０が、ノード装置ＡＳ２０との間のリンクに障害を検出したとする。この場合、ノード装置ＡＳ３０は、迂回経路を介して、ＢＧＰの経路取消メッセージUPDATE(Withdraw)を送信する。図１４によれば、UPDATE(Withdraw)は、ノード装置ＡＳ４０を迂回して、ノード装置ＡＳ２０へ転送される。尚、UPDATE(Withdraw)には、プレフィックスのみが含まれ、ＡＳパスリストは含まれない。
【００５６】
図１５は、図１４のネットワークについて、経路取消メッセージが受信された場合のパスリスト記録テーブル及びパス数記録テーブルである。
【００５７】
パスリスト記録テーブルについて、経路取消メッセージのプレフィックス[12.0.1.0/8]が既に記録されている。この場合、パスリスト記録テーブルから、プレフィックス[12.0.1.0/8]及びパスリスト[20,30]の記録を削除する。
【００５８】
次に、パス数記録テーブルについて、過去のパスリスト[20,30]に基づくリンク[AS30->AS20]及び[AS20->観測AS]のパス数を１減分する。
【００５９】
その後、図１２の第５の経路更新メッセージUPDATE5と、第１３の第６の経路更新メッセージUPDATE6とが迂回経路を転送されることによって、[AS30->AS20]のパス数が０となり、図１３と同様に、障害リンクを検出することができる。
【００６０】
図１６は、障害発生前後におけるパス数の変化を表す説明図である。
【００６１】
図１６によれば、リンク[AS30->AS20]に障害が発生した場合、パス数記録テーブルにおける当該リンクのパス数は、急激に０に変化する。一方で、迂回経路となるノード装置AS40を介するリンクのパス数は、急激に増加する。本発明のパス数記録テーブルによれば、パス数が急激に変動することによって、障害リンクを検出することができる。尚、他の実施形態として、観測用ノード装置が、障害リンク検出装置であってもよい。
【００６２】
図１７は、本発明における障害リンクを検出するフローチャートである。この処理に基づいて、ノード装置に搭載されるコンピュータが実行されるものであってもよい。
【００６３】
（Ｓ１）最初に、ＢＧＰの経路更新メッセージUPDATEを受信する。
（Ｓ２）UPDATEのメッセージ種別（経路更新Announce／経路取消Withdraw）を判定する。
（Ｓ３）経路更新メッセージであると判定された場合、UPDATEに含まれるパスリストと、パスリスト記録テーブルに記録された同一プレフィックスにおける直前のパスリストとが一致するか否かを判定する。一致すると判定された場合、そのまま処理を終了する。
（Ｓ４）一致しないと判定された場合、パスリスト記録テーブルを新しいパスリストで更新する。
（Ｓ５）そして、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分する。
（Ｓ６）経路取消メッセージであると判定された場合、そのプレフィックスと一致するパスリストを、パスリスト記録テーブルから検索し、パスリスト記録テーブルから当該パスリストを削除する。
（Ｓ７）そして、パス数記録テーブルについて経路取消のリンクのパス数を減分する。
（Ｓ８）パス数記録テーブルについて、パス数が０に変化したリンクがあるか否かを判定する。パス数が０に変化したリンクがない場合、そのまま処理を終了する。
（Ｓ９）パス数が０に変化したリンクがある場合、そのリンクを、障害リンクとして検出する。
【００６４】
図１８は、本発明におけるノード装置の機能構成図である。
【００６５】
図１８によれば、ノード装置１は、パスリスト記録テーブル１１１と、パス数記録テーブル１１２と、パスリスト判定部１２１と、パスリスト更新部１２２と、パス数更新部１２３と、障害リンク検出部１２４と、経路更新メッセージ送信部１０１と、経路取消メッセージ送信部１０２と、中継転送部１０３と、経路更新メッセージ受信監視部１０４とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、経路更新メッセージ受信監視部１０４は、中継転送部１０３から抽出したＢＧＰのUPDATEを、パスリスト判定部１２１へ出力する。
【００６６】
パスリスト記録テーブル１１１は、ＢＧＰのUPDATE(Announce)のプレフィックス（送信元アドレス）毎に、中継されたノード装置のＡＳ番号の連続からなる直前のパスリストを記録する。
【００６７】
パス数記録テーブル１１２は、ノード装置間のリンク毎に、UPDATE(Announce)のパス数を記録する。
【００６８】
パスリスト判定部１２１は、UPDATE(Announce)を受信した際に、そのパスリストと、パスリスト記録テーブルに記録された同一プレフィックスにおける直前のパスリストとが一致するか否かを判定する。また、パスリスト判定部１２１は、UPDATE(Withdraw)を受信した際に、そのプレフィックスと一致するパスリストを、パスリスト記録テーブル１１１から検索する。
【００６９】
パスリスト更新部１２２は、UPDATE(Announce)に基づいてパスリスト判定部１２１が一致しないと判定した場合、パスリスト記録テーブル１１１を新しいパスリストで更新する。また、パスリスト更新部１２２は、UPDATE(Withdraw)に基づいてパスリスト判定部１２１が検索したパスリストを、パスリスト記録テーブル１１１から削除する。
【００７０】
パス数更新部１２３は、UPDATE(Announce)に基づいてパスリスト判定部１２１が一致しないと判定した場合、パス数記録テーブルについて新しいリンクのパス数を増分し、且つ、古いリンクのパス数を減分する。また、パス数更新部１２３は、UPDATE(Withdraw)に基づいてパスリスト判定部１２１が検索したパスリストについて、パス数記録テーブルにおける経路取消のリンクのパス数を減分する。
【００７１】
障害リンク検出部１２４は、パス数記録テーブルについてパス数が０に変化したリンクを、障害リンクとして検出する。
【００７２】
経路更新メッセージ送信部１０１は、プレフィックス及びＡＳ番号を含むUPDATE(Announce)を定期的にブロードキャストで送信する。
【００７３】
経路取消メッセージ送信部１０２は、障害リンクを検出した際に、UPDATE(Withdraw)をブロードキャストで送信する。
【００７４】
中継転送部１０３は、UPDATE(Announce)を受信した際に、そのパスリストに更に当該ノード装置のＡＳ番号を含めた当該UPDATE(Announce)を中継転送する。
【００７５】
以上、詳細に説明したように、本発明の障害リンク検出方法、ノード装置及びプログラムによれば、プレフィックス毎の直前のパスリストを記憶するパスリスト記録テーブルと、リンク毎のパス数を増減させるパス数記録テーブルとを用いることにより、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、少ない計算量で且つリアルタイムに障害リンクを検出することができる。また、障害発生後の障害リンクを検出するだけでなく、迂回経路も検出することができる。
【００７６】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【産業上の利用可能性】
【００７７】
本発明は、固有識別番号を有する複数のノード装置がメッシュ状に接続され、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて、障害リンクを検出するために利用することができる。
【符号の説明】
【００７８】
１  ノード装置
１０１  経路更新メッセージ送信部
１０２  経路取消メッセージ送信部
１０３  中継転送部
１０４  経路更新メッセージ受信監視部
１１１  パスリスト記録テーブル
１１２  パス数記録テーブル
１２１  パスリスト判定部
１２２  パスリスト更新部
１２３  パス数更新部
１２４  障害リンク検出部
【図１】
2010161524.tif 000003
【図２】
2010161524.tif 000004
【図３】
2010161524.tif 000005
【図４】
2010161524.tif 000006
【図５】
2010161524.tif 000007
【図６】
2010161524.tif 000008
【図７】
2010161524.tif 000009
【図８】
2010161524.tif 000010
【図９】
2010161524.tif 000011
【図１０】
2010161524.tif 000012
【図１１】
2010161524.tif 000013
【図１２】
2010161524.tif 000014
【図１３】
2010161524.tif 000015
【図１４】
2010161524.tif 000016
【図１５】
2010161524.tif 000017
【図１６】
2010161524.tif 000018
【図１７】
2010161524.tif 000019
【図１８】
2010161524.tif 000020