リンク可用率を用いた経路制御プロトコルに基づく経路制御方法、ノード装置及びプログラム
【課題】経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる経路制御方法等を提供する。
【解決手段】最初に、ノード装置が、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する。次に、ノード装置が、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出し、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する。そして、ノード装置が、優先的な経路を設定するルートマップ設定部に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する。
【解決手段】最初に、ノード装置が、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する。次に、ノード装置が、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出し、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する。そして、ノード装置が、優先的な経路を設定するルートマップ設定部に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づく経路制御方法、ノード装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットでは、ノード装置（例えばルータ）がパケットを適切に中継転送するために、経路制御プロトコルが用いられる。代表的な経路制御プロトコルとして、インターネット上で組織間の経路情報を交換するＢＧＰ(Border Gateway Protocol)がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一のＡＳ(Autonomous System)番号が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
図１は、従来技術におけるネットワーク構成図である。
【０００４】
複数のノード装置が相互に接続されており、送信元ノード装置と宛先ノード装置との間には、複数のパス（経路）が候補として存在する。ここで、「パス」とは、送信元ノード装置と宛先ノード装置との間の経路であって、中継ノード装置を介した接続を意味する。また、「リンク」とは、直接的に接続される隣接ノード装置間の接続を意味する。
【０００５】
図１によれば、送信元ノード装置AS40と宛先ノード装置AS80との間では、３つのパスが存在する。
パス１：AS40->AS10->AS80
パス２：AS40->AS30->AS20->AS80
パス３：AS40->AS70->AS60->AS50->AS80
【０００６】
ＢＧＰによれば、一般に、候補となる複数のパスの中で、宛先ネットワークまでの到達距離が最も短いものが選択される。即ち、複数のパスの中で、中継ノード装置の数が最も少ないものが選択される。図１によれば、３つのパスの中で、パス１の経路が選択される。
【０００７】
また、中継ノード装置の数に関係なく、オペレータ（ポリシ）によって経路が選択される場合もある。ノード装置は、ルートマップ設定部を備えており、オペレータがそのルートマップを書き換えることによって、経路を選択することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−２４３４８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＢＧＰの最適経路選択方式によれば、前述したように、複数のパスの中で、中継ノード装置の数が最も少ないパスか、又は、オペレータによって指定されたパスが、選択される。しかしながら、選択されたパスについて、いずれか１つのリンクの箇所に通信品質の劣化が生じた場合、通信自体に影響を及ぼすこととなる。即ち、ＢＧＰによれば、通信品質が劣化したリンクを含むパスであっても、最適経路として選択する場合がある。通常、ルータのようなノード装置における最適経路計算には、通信品質が考慮されていないからである。ノード装置自体が、通信品質に応じてパスを切り替える場合、別途、通信品質を計測する機能を備える必要がある。
【００１０】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる経路制御方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて、固有識別番号を有する複数のノード装置がメッシュ状に接続されており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
経路更新メッセージを受信したノード装置が、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送するノード装置の経路制御方法において、
ノード装置が、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する第１のステップと、
ノード装置が、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出する第２のステップと、
ノード装置が、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する第３のステップと、
ノード装置が、優先的な経路を設定するルートマップ設定部に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する第４のステップと
を有することを特徴とする。
【００１２】
本発明のノード装置の経路制御方法における他の実施形態によれば、
評価時間Ｔは、複数の単位時間ｔからなり、
第１のステップについて、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つの経路更新メッセージが通過した場合に１増分される数であり、可用時間は、リンク可用数をｔ倍することによって算出され、
第２のステップについて、リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出されることも好ましい。
【００１３】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００１４】
本発明のノード装置の経路制御方法における他の実施形態によれば、
ノード装置は、ルータであり、
第４のステップについて、ルートマップ設定部は、
経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することも好ましい。
【００１５】
本発明のノード装置の経路制御方法における他の実施形態によれば、
第２のステップについて、リンク可用率を算出する際に、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００１６】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
ルートマップ設定手段に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する優先値設定手段と
を有することを特徴とする。
【００１７】
本発明のノード装置の経路制御方法における他の実施形態によれば、
評価時間Ｔは、複数の単位時間ｔからなり、
リンク可用数計数手段について、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つの経路更新メッセージが通過した場合に１増分される数であり、可用時間は、リンク可用数をｔ倍することによって算出され、
リンク可用率算出手段について、リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出されることも好ましい。
【００１８】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００１９】
本発明のノード装置の経路制御方法における他の実施形態によれば、
ノード装置は、ルータであり、
ルートマップ設定手段は、
経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することも好ましい。
【００２０】
本発明のノード装置の経路制御方法における他の実施形態によれば、
リンク可用率算出手段は、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００２１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してコンピュータを機能させるノード装置用のプログラムにおいて、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
ルートマップ設定手段に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する優先値設定手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００２２】
本発明の経路制御方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる。
【図面の簡単な説明】
【００２３】
【図１】従来技術におけるネットワーク構成図である。
【図２】本発明におけるネットワーク構成図である。
【図３】本発明におけるリンク記録テーブル及びパス記録テーブルである。
【図４】本発明によって選択されたパスを表すネットワーク構成図である。
【図５】本発明におけるノード装置のフローチャートである。
【図６】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２４】
以下では、本発明を実施するための形態について、図面を用いて詳細に説明する。
【００２５】
図２は、本発明におけるネットワーク構成図である。
【００２６】
図２によれば、図１と同様に、ＡＳ(Autonomous System)番号を有する複数のノード装置１(AS10〜AS80)がメッシュ状に接続されている。また、このネットワークは、経路制御プロトコルであるＢＧＰ(Border Gateway Protocol)によって構成されている。
【００２７】
ノード装置１は、定期的に、ＢＧＰにおける経路更新メッセージ(UPDATE(Announce))をブロードキャストで送信する。図２によれば、送信元ノード装置AS40から送信されるUPDATEメッセージに注目している。ブロードキャストによって送信されたUPDATEメッセージは、３つのパスを別々に経由して、宛先ノード装置AS80によって受信される。
【００２８】
経路更新メッセージ(UPDATE)には、以下のパラメータが含まれる。
（１）プレフィックス
（２）メッセージ種別
（３）AS_PATH属性
「プレフィックス」は、ＩＰアドレス及びサブネットマスクの組(xxx.xxx.xxx.xxx/xx)であって、送信元ネットワークアドレス（又は送信元ノード装置のアドレス）を表す。
「メッセージ種別」は、経路更新(Announce)を表す。
「AS_PATH属性」は、プレフィックスからの到達経路のパスリスト（ＡＳ番号の列）を表す。
【００２９】
図２によれば、ノード装置AS80のパス記録テーブルが表されている。パス記録テーブルには、受信したUPDATEメッセージのプレフィックス毎に、１つ以上のＡＳパスリストが記録される。ノード装置AS80は、ノード装置AS40からのUPDATEメッセージを、３つのパス別々に経由して受信する。
【００３０】
ノード装置AS80のパス記録テーブルには、ノード装置AS40から送信されたUPDATEメッセージ（プレフィックス[40.0.0.1]）について、３つのパスリスト[10,40]、[20,30,40]及び[50,60,70,40]が記録されている。
【００３１】
図３は、本発明におけるリンク記録テーブル及びパス記録テーブルである。
【００３２】
リンク記録テーブルは、単位時間ｔの間に、リンク毎に、少なくとも１つのUPDATEメッセージが通過した場合に１増分されるリンク可用数を記録する。図３のリンク記録テーブルによれば、例えばリンク[AS40-AS10]に、５が記録されている。これは、少なくとも１つのUPDATEメッセージ（プレフィックス[40.0.0.1]）が通過した単位時間ｔが、５回発生したことを意味する。
【００３３】
図３のリンク記録テーブルについて、評価時間Ｔ(=ｔ×10)におけるリンク[AS40-AS10]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は５である。即ち、UPDATEメッセージが通過しなかった不用時間は５（＝１０−５）である。この場合、リンク[AS40-AS10]における可用率は、０．５（＝可用時間／評価時間＝５／１０）と算出される。
【００３４】
ここで、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。例えば、評価時間Ｔ（例えば１０）におけるリンク可用数が５であったとしても、可用時間／不用時間の変化回数が多い場合、リンク可用数を減らす。図３によれば、変化回数が５回もある場合、リンク可用数を３へ減らす。また、変化回数が２回である場合、リンク可用数を４へ減らす。
【００３５】
また、評価時間Ｔにおけるリンク[AS30-AS20]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は９である。即ち、UPDATEメッセージが通過しなかった不用時間は１である。この場合、リンク[AS30-AS20]における可用率は、０．９（＝９／１０）と算出される。
【００３６】
更に、評価時間Ｔにおけるリンク[AS70-AS60]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は１０である。即ち、UPDATEメッセージが通過しなかった不用時間は０である。この場合、リンク[AS70-AS60]における可用率は、１．０（＝１０／１０）と算出される。
【００３７】
図３のパス記録テーブルは、パスリスト毎に、全てのリンク可用率を乗算することによって算出された可用率を記録する。
【００３８】
パスリスト[10,40]によれば、リンク[AS40-AS10]及び[AS10-AS80]を経由している。ここで、リンク[AS40-AS10]可用率は０．５であり、リンク[AS10-AS80]可用率は１である。この場合、パスリスト[10,40]可用率は、リンク毎の可用率を乗算することによって、０．５（＝０．５×１）と算出される。
【００３９】
また、パスリスト[20,30,40]によれば、リンク[AS40-AS30]、[AS30-AS20]及び[AS20-AS80]を経由している。ここで、リンク[AS40-AS30]可用率は１であり、リンク[AS30-AS20]可用率は０．９であり、リンク[AS20->AS80]可用率は１である。この場合、パスリスト[20,30,40]可用率は、全てのリンク可用率を乗算することによって、０．９（＝１×０．９×１）と算出される。
【００４０】
更に、パスリスト[50,60,70,40]によれば、リンク[AS40-AS70]、[AS70-AS60]、[AS60-AS50]及び[AS50-AS80]を経由している。ここで、リンク[AS40-AS70]可用率は１であり、リンク[AS70-AS60]可用率は１であり、リンク[AS60-AS50]可用率は１であり、リンク[AS50-AS80]可用率は１である。この場合、パスリスト[50,60,70,40]可用率は、全てのリンク可用率を乗算することによって、１（＝１×１×１×１）と算出される。
【００４１】
図４は、本発明によって選択されたパスを表すネットワーク構成図である。
【００４２】
図４によれば、リンク毎にリンク可用率が表されている。また、３つのパスの中で、パス可用率が最も大きいパスは、パス３（１．０）である。本発明の経路制御によれば、中継ノード数が最も少ないパス１ではなく、可用率が最も大きいパス３が選択される。
【００４３】
また、図４によれば、ノード装置AS80に代えて、経路制御装置２を備えることも好ましい。経路制御装置２が、ＢＧＰのUPDATEメッセージをブロードキャストすることによって、ネットワーク全体における最適経路を導出することができる。
【００４４】
図５は、本発明におけるフローチャートである。
【００４５】
図５（ａ）は、UPDATEメッセージを受信した場合に実行されるフローチャートである。
（Ｓ５１１）ノード装置は、受信されたUPDATEメッセージから、パスリストを取得する。そのパスリストから複数のリンクを抽出する。
（Ｓ５１２）次に、ノード装置は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置のＡＳ番号の連続からなるパスリストをパス記録テーブルに記録する。また、隣接ノード装置間のリンク毎に、UPDATEメッセージが通過している可用時間を測定し、その可用時間に基づくリンク可用数をリンク記録テーブルに記録する。
【００４６】
評価時間Ｔが、複数の単位時間ｔからなるとする。リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分される数である。逆に、単位時間ｔの間に、１つのUPDATEメッセージも通過しなかったリンクにおけるそのリンク可用数は維持される。結果的に、評価時間Ｔが経過した際に、リンク記録テーブルには、リンク可用数（＝可用時間／単位時間ｔ）が記録される。即ち、可用時間は、リンク可用数をｔ倍することによって算出される。
【００４７】
図５（ｂ）は、評価時間Ｔ毎に実行されるフローチャートである。
（Ｓ５２１）ノード装置は、リンク記録テーブルを用いて、リンク毎に、評価時間Ｔにおけるリンク可用数（＝可用時間／単位時間ｔ）に基づいたリンク可用率を算出する。リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出される。
（Ｓ５２２）ノード装置は、リンク毎の可用率を乗算することによって、パスリスト毎に、パス可用率を算出する。
（Ｓ５２３）ノード装置のルートマップ設定部は、UPDATEメッセージの送信元アドレスのパケットに対する優先パラメータに、パスリスト毎のパス可用率の大きさに応じた値を設定する。
【００４８】
ここで、ルートマップ設定部における優先パラメータの設定について、具体的に説明する。
【００４９】
ＢＧＰによれば、オペレータが、そのポリシによって経路制御をすることができる優先パラメータとして、local-preference値を有する。local-preference値は、route-mapによって設定される。候補となる複数の経路の中で、local-preference値が最大となる経路が最適経路として計算される。
【００５０】
図４のネットワーク構成の場合、ノード装置ＡＳ８０におけるルートマップ設定部は、例えば以下のように設定する（Cisco（登録商標）社製ルータの場合）。
router bgp 80 （宛先ノード装置AS80）
neighbor 10.0.0.1 remote-as 10 （AS10と IPアドレス10.0.0.1で接続）
neighbor 20.0.0.1 remote-as 20 （AS20と IPアドレス20.0.0.1で接続）
neighbor 50.0.0.1 remote-as 50 （AS50と IPアドレス50.0.0.1で接続）
neighbor 10.0.0.1 route-map map10 in （10.0.0.1経由のパスにmap10を適用）
neighbor 20.0.0.1 route-map map20 in （20.0.0.1経由のパスにmap20を適用）
neighbor 50.0.0.1 route-map map50 in （50.0.0.1経由のパスにmap30を適用）
!
route-map map10 permit 10 （map10について）
match as-path 40 （AS40に対して）
set local-preference 1 （local-preference値を1とする）
!
route-map map20 permit 10 （map20について）
match as-path 40 （AS40に対して）
set local-preference 2 （local-preference値を2とする）
!
route-map map50 permit 10 （map50について）
match as-path 40 （AS40に対して）
set local-preference 3 （local-preference値を3とする）
!
【００５１】
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS10(10.0.0.1)を経由するパスにおけるlocal-preference値は１に設定する。
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS20(20.0.0.1)を経由するパスにおけるlocal-preference値は２に設定する。
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS50(20.0.0.1)を経由するパスにおけるlocal-preference値は３に設定する。
【００５２】
前述のルートマップによれば、local-preference値が最も大きいノード装置AS50(20.0.0.1)を経由するパスが選択される。local-preference値に設定される値は、例えば、算出されたパス毎の可用率を、所定倍数（例えば１０倍や１００倍）した整数値を設定するものであってもよい。また、前述のように、算出されたパス毎の可用率が小さいものから順に、１，２，３，・・・の順に設定するものであってもよい。
【００５３】
このようにルートマップを設定することによって、ＢＧＰのプロトコル使用を一切変更することなく、UPDATEメッセージを受信することによって算出された可用率を用いて、安定したパス（可用率が高いパス）を優先的に選択することができる。
【００５４】
尚、ＢＧＰによれば、ここで設定されたルートマップは、UPDATEメッセージによって、更に、ＡＳ内の全てのルータによって共有される。
【００５５】
図６は、本発明におけるノード装置の機能構成図である。
【００５６】
図６によれば、ノード装置１は、中継転送部１０と、ルートマップ設定部１１と、経路更新メッセージ送信部１２と、経路更新メッセージ受信監視部１３と、リンク可用数計数部１４と、リンク記録テーブル１５と、パス記録テーブル１６と、リンク可用率算出部１７と、パス可用率算出部１８と、優先値設定部１９とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００５７】
中継転送部１０は、UPDATE(Announce)メッセージを受信した際に、そのパスリストに更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。
【００５８】
ルートマップ設定部１１は、送信元アドレス毎の複数のパスリストの中から優先的な経路を選択し、その設定情報を中継転送部１０のルートマップへ設定する。
【００５９】
経路更新メッセージ送信部１２は、ＢＧＰに基づいて、プレフィックス（送信元アドレス）及びＡＳ番号（固有識別番号）を含むUPDATEメッセージを、定期的にブロードキャストで送信する。
【００６０】
経路更新メッセージ受信監視部１３は、中継転送部１０から抽出したＢＧＰのUPDATEメッセージを、リンク可用数計測部１４へ出力する。
【００６１】
リンク可用数計数部１４は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録する。また、隣接ノード装置間のリンク毎に、UPDATEメッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数を、リンク記録テーブルに記録する。ここで、評価時間Ｔは、複数の単位時間ｔからなるとした場合、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分される数である。
【００６２】
リンク記録テーブル１５は、隣接するノード装置間のリンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分されるリンク可用数を記録する。
【００６３】
パス記録テーブル１６は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストを記録する。
【００６４】
リンク可用率算出部１７は、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出する。ここで、評価時間Ｔは、複数の単位時間ｔからなるとした場合、可用時間は、リンク可用数をｔ倍することによって算出される。リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出される。算出されたリンク可用率は、パス可用率算出部１８及びパス記録テーブル１６へ出力される。尚、リンク可用率算出部１７は、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００６５】
パス可用率算出部１８は、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する。パスリスト毎のパス可用率は、パス記録テーブル１６へ出力される。
【００６６】
優先値設定部１９は、ルートマップ設定部１１に対して、UPDATEメッセージの送信元アドレスのパケットに対する優先パラメータに、パスリスト毎の可用率の大きさに応じた値を設定する。具体的には、UPDATEメッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定する。また、当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定する。
【００６７】
以上、詳細に説明したように、本発明の経路制御方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる。
【００６８】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６９】
１ ノード装置
１０ 中継転送部
１１ ルートマップ設定部
１２ 経路更新メッセージ送信部
１３ 経路更新メッセージ受信監視部
１４ リンク可用数計数部
１５ リンク記録テーブル
１６ パス記録テーブル
１７ リンク可用率算出部
１８ パス可用率算出部
１９ 優先値設定部
２ 経路制御装置
【技術分野】
【０００１】
本発明は、経路制御プロトコルに基づく経路制御方法、ノード装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットでは、ノード装置（例えばルータ）がパケットを適切に中継転送するために、経路制御プロトコルが用いられる。代表的な経路制御プロトコルとして、インターネット上で組織間の経路情報を交換するＢＧＰ(Border Gateway Protocol)がある。ＢＧＰ対応のノード装置には、インターネットにおける唯一のＡＳ(Autonomous System)番号が付与される。ＡＳ番号は、共通ポリシ及び同一管理運用下にあるノード装置の集合毎に付与される。ＡＳ番号は、原則として２バイト（現在は４バイト化）であって、ＩＡＮＡ(Internet Assigned Numbers Authority)によって管理されている。
【０００３】
図１は、従来技術におけるネットワーク構成図である。
【０００４】
複数のノード装置が相互に接続されており、送信元ノード装置と宛先ノード装置との間には、複数のパス（経路）が候補として存在する。ここで、「パス」とは、送信元ノード装置と宛先ノード装置との間の経路であって、中継ノード装置を介した接続を意味する。また、「リンク」とは、直接的に接続される隣接ノード装置間の接続を意味する。
【０００５】
図１によれば、送信元ノード装置AS40と宛先ノード装置AS80との間では、３つのパスが存在する。
パス１：AS40->AS10->AS80
パス２：AS40->AS30->AS20->AS80
パス３：AS40->AS70->AS60->AS50->AS80
【０００６】
ＢＧＰによれば、一般に、候補となる複数のパスの中で、宛先ネットワークまでの到達距離が最も短いものが選択される。即ち、複数のパスの中で、中継ノード装置の数が最も少ないものが選択される。図１によれば、３つのパスの中で、パス１の経路が選択される。
【０００７】
また、中継ノード装置の数に関係なく、オペレータ（ポリシ）によって経路が選択される場合もある。ノード装置は、ルートマップ設定部を備えており、オペレータがそのルートマップを書き換えることによって、経路を選択することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−２４３４８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＢＧＰの最適経路選択方式によれば、前述したように、複数のパスの中で、中継ノード装置の数が最も少ないパスか、又は、オペレータによって指定されたパスが、選択される。しかしながら、選択されたパスについて、いずれか１つのリンクの箇所に通信品質の劣化が生じた場合、通信自体に影響を及ぼすこととなる。即ち、ＢＧＰによれば、通信品質が劣化したリンクを含むパスであっても、最適経路として選択する場合がある。通常、ルータのようなノード装置における最適経路計算には、通信品質が考慮されていないからである。ノード装置自体が、通信品質に応じてパスを切り替える場合、別途、通信品質を計測する機能を備える必要がある。
【００１０】
そこで、本発明は、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる経路制御方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークについて、固有識別番号を有する複数のノード装置がメッシュ状に接続されており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
経路更新メッセージを受信したノード装置が、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送するノード装置の経路制御方法において、
ノード装置が、経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する第１のステップと、
ノード装置が、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出する第２のステップと、
ノード装置が、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する第３のステップと、
ノード装置が、優先的な経路を設定するルートマップ設定部に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する第４のステップと
を有することを特徴とする。
【００１２】
本発明のノード装置の経路制御方法における他の実施形態によれば、
評価時間Ｔは、複数の単位時間ｔからなり、
第１のステップについて、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つの経路更新メッセージが通過した場合に１増分される数であり、可用時間は、リンク可用数をｔ倍することによって算出され、
第２のステップについて、リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出されることも好ましい。
【００１３】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
固有識別番号は、ＡＳ(Autonomous System)番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００１４】
本発明のノード装置の経路制御方法における他の実施形態によれば、
ノード装置は、ルータであり、
第４のステップについて、ルートマップ設定部は、
経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することも好ましい。
【００１５】
本発明のノード装置の経路制御方法における他の実施形態によれば、
第２のステップについて、リンク可用率を算出する際に、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００１６】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
ルートマップ設定手段に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する優先値設定手段と
を有することを特徴とする。
【００１７】
本発明のノード装置の経路制御方法における他の実施形態によれば、
評価時間Ｔは、複数の単位時間ｔからなり、
リンク可用数計数手段について、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つの経路更新メッセージが通過した場合に１増分される数であり、可用時間は、リンク可用数をｔ倍することによって算出され、
リンク可用率算出手段について、リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出されることも好ましい。
【００１８】
本発明のノード装置の経路制御方法における他の実施形態によれば、
経路制御プロトコルは、ＢＧＰであり、
固有識別番号は、ＡＳ番号であり、
経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
経路更新メッセージの送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
経路更新メッセージのパスリストは、AS_PATH属性に含まれる
ことも好ましい。
【００１９】
本発明のノード装置の経路制御方法における他の実施形態によれば、
ノード装置は、ルータであり、
ルートマップ設定手段は、
経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することも好ましい。
【００２０】
本発明のノード装置の経路制御方法における他の実施形態によれば、
リンク可用率算出手段は、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００２１】
本発明によれば、経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してコンピュータを機能させるノード装置用のプログラムにおいて、
経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
ルートマップ設定手段に対して、送信元アドレスのパケットに対する優先パラメータに、パス可用率の大きさに応じた値を設定する優先値設定手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００２２】
本発明の経路制御方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる。
【図面の簡単な説明】
【００２３】
【図１】従来技術におけるネットワーク構成図である。
【図２】本発明におけるネットワーク構成図である。
【図３】本発明におけるリンク記録テーブル及びパス記録テーブルである。
【図４】本発明によって選択されたパスを表すネットワーク構成図である。
【図５】本発明におけるノード装置のフローチャートである。
【図６】本発明におけるノード装置の機能構成図である。
【発明を実施するための形態】
【００２４】
以下では、本発明を実施するための形態について、図面を用いて詳細に説明する。
【００２５】
図２は、本発明におけるネットワーク構成図である。
【００２６】
図２によれば、図１と同様に、ＡＳ(Autonomous System)番号を有する複数のノード装置１(AS10〜AS80)がメッシュ状に接続されている。また、このネットワークは、経路制御プロトコルであるＢＧＰ(Border Gateway Protocol)によって構成されている。
【００２７】
ノード装置１は、定期的に、ＢＧＰにおける経路更新メッセージ(UPDATE(Announce))をブロードキャストで送信する。図２によれば、送信元ノード装置AS40から送信されるUPDATEメッセージに注目している。ブロードキャストによって送信されたUPDATEメッセージは、３つのパスを別々に経由して、宛先ノード装置AS80によって受信される。
【００２８】
経路更新メッセージ(UPDATE)には、以下のパラメータが含まれる。
（１）プレフィックス
（２）メッセージ種別
（３）AS_PATH属性
「プレフィックス」は、ＩＰアドレス及びサブネットマスクの組(xxx.xxx.xxx.xxx/xx)であって、送信元ネットワークアドレス（又は送信元ノード装置のアドレス）を表す。
「メッセージ種別」は、経路更新(Announce)を表す。
「AS_PATH属性」は、プレフィックスからの到達経路のパスリスト（ＡＳ番号の列）を表す。
【００２９】
図２によれば、ノード装置AS80のパス記録テーブルが表されている。パス記録テーブルには、受信したUPDATEメッセージのプレフィックス毎に、１つ以上のＡＳパスリストが記録される。ノード装置AS80は、ノード装置AS40からのUPDATEメッセージを、３つのパス別々に経由して受信する。
【００３０】
ノード装置AS80のパス記録テーブルには、ノード装置AS40から送信されたUPDATEメッセージ（プレフィックス[40.0.0.1]）について、３つのパスリスト[10,40]、[20,30,40]及び[50,60,70,40]が記録されている。
【００３１】
図３は、本発明におけるリンク記録テーブル及びパス記録テーブルである。
【００３２】
リンク記録テーブルは、単位時間ｔの間に、リンク毎に、少なくとも１つのUPDATEメッセージが通過した場合に１増分されるリンク可用数を記録する。図３のリンク記録テーブルによれば、例えばリンク[AS40-AS10]に、５が記録されている。これは、少なくとも１つのUPDATEメッセージ（プレフィックス[40.0.0.1]）が通過した単位時間ｔが、５回発生したことを意味する。
【００３３】
図３のリンク記録テーブルについて、評価時間Ｔ(=ｔ×10)におけるリンク[AS40-AS10]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は５である。即ち、UPDATEメッセージが通過しなかった不用時間は５（＝１０−５）である。この場合、リンク[AS40-AS10]における可用率は、０．５（＝可用時間／評価時間＝５／１０）と算出される。
【００３４】
ここで、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。例えば、評価時間Ｔ（例えば１０）におけるリンク可用数が５であったとしても、可用時間／不用時間の変化回数が多い場合、リンク可用数を減らす。図３によれば、変化回数が５回もある場合、リンク可用数を３へ減らす。また、変化回数が２回である場合、リンク可用数を４へ減らす。
【００３５】
また、評価時間Ｔにおけるリンク[AS30-AS20]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は９である。即ち、UPDATEメッセージが通過しなかった不用時間は１である。この場合、リンク[AS30-AS20]における可用率は、０．９（＝９／１０）と算出される。
【００３６】
更に、評価時間Ｔにおけるリンク[AS70-AS60]に注目する。プレフィックス[40.0.0.1]のUPDATEメッセージが通過した可用時間（リンク可用数×単位時間ｔ）は１０である。即ち、UPDATEメッセージが通過しなかった不用時間は０である。この場合、リンク[AS70-AS60]における可用率は、１．０（＝１０／１０）と算出される。
【００３７】
図３のパス記録テーブルは、パスリスト毎に、全てのリンク可用率を乗算することによって算出された可用率を記録する。
【００３８】
パスリスト[10,40]によれば、リンク[AS40-AS10]及び[AS10-AS80]を経由している。ここで、リンク[AS40-AS10]可用率は０．５であり、リンク[AS10-AS80]可用率は１である。この場合、パスリスト[10,40]可用率は、リンク毎の可用率を乗算することによって、０．５（＝０．５×１）と算出される。
【００３９】
また、パスリスト[20,30,40]によれば、リンク[AS40-AS30]、[AS30-AS20]及び[AS20-AS80]を経由している。ここで、リンク[AS40-AS30]可用率は１であり、リンク[AS30-AS20]可用率は０．９であり、リンク[AS20->AS80]可用率は１である。この場合、パスリスト[20,30,40]可用率は、全てのリンク可用率を乗算することによって、０．９（＝１×０．９×１）と算出される。
【００４０】
更に、パスリスト[50,60,70,40]によれば、リンク[AS40-AS70]、[AS70-AS60]、[AS60-AS50]及び[AS50-AS80]を経由している。ここで、リンク[AS40-AS70]可用率は１であり、リンク[AS70-AS60]可用率は１であり、リンク[AS60-AS50]可用率は１であり、リンク[AS50-AS80]可用率は１である。この場合、パスリスト[50,60,70,40]可用率は、全てのリンク可用率を乗算することによって、１（＝１×１×１×１）と算出される。
【００４１】
図４は、本発明によって選択されたパスを表すネットワーク構成図である。
【００４２】
図４によれば、リンク毎にリンク可用率が表されている。また、３つのパスの中で、パス可用率が最も大きいパスは、パス３（１．０）である。本発明の経路制御によれば、中継ノード数が最も少ないパス１ではなく、可用率が最も大きいパス３が選択される。
【００４３】
また、図４によれば、ノード装置AS80に代えて、経路制御装置２を備えることも好ましい。経路制御装置２が、ＢＧＰのUPDATEメッセージをブロードキャストすることによって、ネットワーク全体における最適経路を導出することができる。
【００４４】
図５は、本発明におけるフローチャートである。
【００４５】
図５（ａ）は、UPDATEメッセージを受信した場合に実行されるフローチャートである。
（Ｓ５１１）ノード装置は、受信されたUPDATEメッセージから、パスリストを取得する。そのパスリストから複数のリンクを抽出する。
（Ｓ５１２）次に、ノード装置は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置のＡＳ番号の連続からなるパスリストをパス記録テーブルに記録する。また、隣接ノード装置間のリンク毎に、UPDATEメッセージが通過している可用時間を測定し、その可用時間に基づくリンク可用数をリンク記録テーブルに記録する。
【００４６】
評価時間Ｔが、複数の単位時間ｔからなるとする。リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分される数である。逆に、単位時間ｔの間に、１つのUPDATEメッセージも通過しなかったリンクにおけるそのリンク可用数は維持される。結果的に、評価時間Ｔが経過した際に、リンク記録テーブルには、リンク可用数（＝可用時間／単位時間ｔ）が記録される。即ち、可用時間は、リンク可用数をｔ倍することによって算出される。
【００４７】
図５（ｂ）は、評価時間Ｔ毎に実行されるフローチャートである。
（Ｓ５２１）ノード装置は、リンク記録テーブルを用いて、リンク毎に、評価時間Ｔにおけるリンク可用数（＝可用時間／単位時間ｔ）に基づいたリンク可用率を算出する。リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出される。
（Ｓ５２２）ノード装置は、リンク毎の可用率を乗算することによって、パスリスト毎に、パス可用率を算出する。
（Ｓ５２３）ノード装置のルートマップ設定部は、UPDATEメッセージの送信元アドレスのパケットに対する優先パラメータに、パスリスト毎のパス可用率の大きさに応じた値を設定する。
【００４８】
ここで、ルートマップ設定部における優先パラメータの設定について、具体的に説明する。
【００４９】
ＢＧＰによれば、オペレータが、そのポリシによって経路制御をすることができる優先パラメータとして、local-preference値を有する。local-preference値は、route-mapによって設定される。候補となる複数の経路の中で、local-preference値が最大となる経路が最適経路として計算される。
【００５０】
図４のネットワーク構成の場合、ノード装置ＡＳ８０におけるルートマップ設定部は、例えば以下のように設定する（Cisco（登録商標）社製ルータの場合）。
router bgp 80 （宛先ノード装置AS80）
neighbor 10.0.0.1 remote-as 10 （AS10と IPアドレス10.0.0.1で接続）
neighbor 20.0.0.1 remote-as 20 （AS20と IPアドレス20.0.0.1で接続）
neighbor 50.0.0.1 remote-as 50 （AS50と IPアドレス50.0.0.1で接続）
neighbor 10.0.0.1 route-map map10 in （10.0.0.1経由のパスにmap10を適用）
neighbor 20.0.0.1 route-map map20 in （20.0.0.1経由のパスにmap20を適用）
neighbor 50.0.0.1 route-map map50 in （50.0.0.1経由のパスにmap30を適用）
!
route-map map10 permit 10 （map10について）
match as-path 40 （AS40に対して）
set local-preference 1 （local-preference値を1とする）
!
route-map map20 permit 10 （map20について）
match as-path 40 （AS40に対して）
set local-preference 2 （local-preference値を2とする）
!
route-map map50 permit 10 （map50について）
match as-path 40 （AS40に対して）
set local-preference 3 （local-preference値を3とする）
!
【００５１】
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS10(10.0.0.1)を経由するパスにおけるlocal-preference値は１に設定する。
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS20(20.0.0.1)を経由するパスにおけるlocal-preference値は２に設定する。
ノード装置AS80は、ノード装置AS40に対して、ノード装置AS50(20.0.0.1)を経由するパスにおけるlocal-preference値は３に設定する。
【００５２】
前述のルートマップによれば、local-preference値が最も大きいノード装置AS50(20.0.0.1)を経由するパスが選択される。local-preference値に設定される値は、例えば、算出されたパス毎の可用率を、所定倍数（例えば１０倍や１００倍）した整数値を設定するものであってもよい。また、前述のように、算出されたパス毎の可用率が小さいものから順に、１，２，３，・・・の順に設定するものであってもよい。
【００５３】
このようにルートマップを設定することによって、ＢＧＰのプロトコル使用を一切変更することなく、UPDATEメッセージを受信することによって算出された可用率を用いて、安定したパス（可用率が高いパス）を優先的に選択することができる。
【００５４】
尚、ＢＧＰによれば、ここで設定されたルートマップは、UPDATEメッセージによって、更に、ＡＳ内の全てのルータによって共有される。
【００５５】
図６は、本発明におけるノード装置の機能構成図である。
【００５６】
図６によれば、ノード装置１は、中継転送部１０と、ルートマップ設定部１１と、経路更新メッセージ送信部１２と、経路更新メッセージ受信監視部１３と、リンク可用数計数部１４と、リンク記録テーブル１５と、パス記録テーブル１６と、リンク可用率算出部１７と、パス可用率算出部１８と、優先値設定部１９とを有する。これら機能構成部は、ノード装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００５７】
中継転送部１０は、UPDATE(Announce)メッセージを受信した際に、そのパスリストに更に当該ノード装置のＡＳ番号を含めて、そのUPDATEメッセージを中継転送する。
【００５８】
ルートマップ設定部１１は、送信元アドレス毎の複数のパスリストの中から優先的な経路を選択し、その設定情報を中継転送部１０のルートマップへ設定する。
【００５９】
経路更新メッセージ送信部１２は、ＢＧＰに基づいて、プレフィックス（送信元アドレス）及びＡＳ番号（固有識別番号）を含むUPDATEメッセージを、定期的にブロードキャストで送信する。
【００６０】
経路更新メッセージ受信監視部１３は、中継転送部１０から抽出したＢＧＰのUPDATEメッセージを、リンク可用数計測部１４へ出力する。
【００６１】
リンク可用数計数部１４は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録する。また、隣接ノード装置間のリンク毎に、UPDATEメッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数を、リンク記録テーブルに記録する。ここで、評価時間Ｔは、複数の単位時間ｔからなるとした場合、リンク記録テーブルのリンク可用数は、リンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分される数である。
【００６２】
リンク記録テーブル１５は、隣接するノード装置間のリンク毎に、単位時間ｔの間に、少なくとも１つのUPDATEメッセージが通過した場合に１増分されるリンク可用数を記録する。
【００６３】
パス記録テーブル１６は、UPDATEメッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストを記録する。
【００６４】
リンク可用率算出部１７は、評価時間Ｔについて、リンク可用数に基づいたリンク可用率を算出する。ここで、評価時間Ｔは、複数の単位時間ｔからなるとした場合、可用時間は、リンク可用数をｔ倍することによって算出される。リンク可用率は、評価時間Ｔに対する可用時間の割合によって算出される。算出されたリンク可用率は、パス可用率算出部１８及びパス記録テーブル１６へ出力される。尚、リンク可用率算出部１７は、評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、変化回数が多くなるほど、リンク可用率を減率することも好ましい。
【００６５】
パス可用率算出部１８は、パスリスト毎に、リンク可用率を乗算することによってパス可用率を算出する。パスリスト毎のパス可用率は、パス記録テーブル１６へ出力される。
【００６６】
優先値設定部１９は、ルートマップ設定部１１に対して、UPDATEメッセージの送信元アドレスのパケットに対する優先パラメータに、パスリスト毎の可用率の大きさに応じた値を設定する。具体的には、UPDATEメッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定する。また、当該ルータの優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定する。
【００６７】
以上、詳細に説明したように、本発明の経路制御方法、ノード装置及びプログラムによれば、経路制御プロトコルに基づく経路更新メッセージを通常シーケンスで監視し、安定した通信品質の経路を自動的に設定することができる。
【００６８】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６９】
１ ノード装置
１０ 中継転送部
１１ ルートマップ設定部
１２ 経路更新メッセージ送信部
１３ 経路更新メッセージ受信監視部
１４ リンク可用数計数部
１５ リンク記録テーブル
１６ パス記録テーブル
１７ リンク可用率算出部
１８ パス可用率算出部
１９ 優先値設定部
２ 経路制御装置
【特許請求の範囲】
【請求項１】
経路制御プロトコルの経路更新メッセージを送受信するネットワークについて、固有識別番号を有する複数のノード装置がメッシュ状に接続されており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
前記経路更新メッセージを受信したノード装置が、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送するノード装置の経路制御方法において、
前記ノード装置が、前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する第１のステップと、
前記ノード装置が、評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出する第２のステップと、
前記ノード装置が、パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出する第３のステップと、
前記ノード装置が、優先的な経路を設定するルートマップ設定部に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する第４のステップと
を有することを特徴とするノード装置の経路制御方法。
【請求項２】
前記評価時間Ｔは、複数の単位時間ｔからなり、
第１のステップについて、前記リンク記録テーブルの前記リンク可用数は、前記リンク毎に、単位時間ｔの間に、少なくとも１つの前記経路更新メッセージが通過した場合に１増分される数であり、前記可用時間は、前記リンク可用数をｔ倍することによって算出され、
第２のステップについて、前記リンク可用率は、前記評価時間Ｔに対する前記可用時間の割合によって算出される
ことを特徴とする請求項１に記載のノード装置の経路制御方法。
【請求項３】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項１又は２に記載のノード装置の経路制御方法。
【請求項４】
前記ノード装置は、ルータであり、
第４のステップについて、前記ルートマップ設定部は、
前記経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの前記優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することを特徴とする請求項１から３のいずれか１項に記載のノード装置の経路制御方法。
【請求項５】
第２のステップについて、前記リンク可用率を算出する際に、前記評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、前記変化回数が多くなるほど、前記リンク可用率を減率することを特徴とする請求項１から４のいずれか１項に記載のノード装置の経路制御方法。
【請求項６】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
前記経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
前記ルートマップ設定手段に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する優先値設定手段と
を有することを特徴とするノード装置。
【請求項７】
前記評価時間Ｔは、複数の単位時間ｔからなり、
前記リンク可用数計数手段について、前記リンク記録テーブルの前記リンク可用数は、前記リンク毎に、単位時間ｔの間に、少なくとも１つの前記経路更新メッセージが通過した場合に１増分される数であり、前記可用時間は、前記リンク可用数をｔ倍することによって算出され、
前記リンク可用率算出手段について、前記リンク可用率は、前記評価時間Ｔに対する前記可用時間の割合によって算出される
ことを特徴とする請求項６に記載のノード装置。
【請求項８】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項６又は７に記載のノード装置。
【請求項９】
前記ノード装置は、ルータであり、
前記ルートマップ設定手段は、
前記経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの前記優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することを特徴とする請求項６から８のいずれか１項に記載のノード装置。
【請求項１０】
前記リンク可用率算出手段は、前記評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、前記変化回数が多くなるほど、前記リンク可用率を減率することを特徴とする請求項６から９のいずれか１項に記載のノード装置。
【請求項１１】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
前記経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してコンピュータを機能させるノード装置用のプログラムにおいて、
前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
前記ルートマップ設定手段に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する優先値設定手段と
してコンピュータを機能させることを特徴とするノード装置用のプログラム。
【請求項１】
経路制御プロトコルの経路更新メッセージを送受信するネットワークについて、固有識別番号を有する複数のノード装置がメッシュ状に接続されており、
各ノード装置が、送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信し、
前記経路更新メッセージを受信したノード装置が、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送するノード装置の経路制御方法において、
前記ノード装置が、前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録する第１のステップと、
前記ノード装置が、評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出する第２のステップと、
前記ノード装置が、パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出する第３のステップと、
前記ノード装置が、優先的な経路を設定するルートマップ設定部に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する第４のステップと
を有することを特徴とするノード装置の経路制御方法。
【請求項２】
前記評価時間Ｔは、複数の単位時間ｔからなり、
第１のステップについて、前記リンク記録テーブルの前記リンク可用数は、前記リンク毎に、単位時間ｔの間に、少なくとも１つの前記経路更新メッセージが通過した場合に１増分される数であり、前記可用時間は、前記リンク可用数をｔ倍することによって算出され、
第２のステップについて、前記リンク可用率は、前記評価時間Ｔに対する前記可用時間の割合によって算出される
ことを特徴とする請求項１に記載のノード装置の経路制御方法。
【請求項３】
前記経路制御プロトコルは、ＢＧＰ(Border Gateway Protocol)であり、
前記固有識別番号は、ＡＳ(Autonomous System)番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項１又は２に記載のノード装置の経路制御方法。
【請求項４】
前記ノード装置は、ルータであり、
第４のステップについて、前記ルートマップ設定部は、
前記経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの前記優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することを特徴とする請求項１から３のいずれか１項に記載のノード装置の経路制御方法。
【請求項５】
第２のステップについて、前記リンク可用率を算出する際に、前記評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、前記変化回数が多くなるほど、前記リンク可用率を減率することを特徴とする請求項１から４のいずれか１項に記載のノード装置の経路制御方法。
【請求項６】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置であって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
前記経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
を有するノード装置において、
前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
前記ルートマップ設定手段に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する優先値設定手段と
を有することを特徴とするノード装置。
【請求項７】
前記評価時間Ｔは、複数の単位時間ｔからなり、
前記リンク可用数計数手段について、前記リンク記録テーブルの前記リンク可用数は、前記リンク毎に、単位時間ｔの間に、少なくとも１つの前記経路更新メッセージが通過した場合に１増分される数であり、前記可用時間は、前記リンク可用数をｔ倍することによって算出され、
前記リンク可用率算出手段について、前記リンク可用率は、前記評価時間Ｔに対する前記可用時間の割合によって算出される
ことを特徴とする請求項６に記載のノード装置。
【請求項８】
前記経路制御プロトコルは、ＢＧＰであり、
前記固有識別番号は、ＡＳ番号であり、
前記経路更新メッセージは、ＢＧＰのUPDATE(Announce)であり、
前記経路更新メッセージの前記送信元アドレスは、ＩＰアドレスとサブネットマスクのビット数との組からなるプレフィックスであり、
前記経路更新メッセージの前記パスリストは、AS_PATH属性に含まれる
ことを特徴とする請求項６又は７に記載のノード装置。
【請求項９】
前記ノード装置は、ルータであり、
前記ルートマップ設定手段は、
前記経路更新メッセージの送信元アドレスのノード装置を、route-mapにおけるmatchコマンドによって設定し、
当該ルータの前記優先パラメータを、route-mapにおけるsetコマンドによって、local-preference値に設定することを特徴とする請求項６から８のいずれか１項に記載のノード装置。
【請求項１０】
前記リンク可用率算出手段は、前記評価時間Ｔにおける可用時間／不用時間の変化回数を計数し、前記変化回数が多くなるほど、前記リンク可用率を減率することを特徴とする請求項６から９のいずれか１項に記載のノード装置。
【請求項１１】
経路制御プロトコルの経路更新メッセージを送受信するネットワークに接続された、固有識別番号を有するノード装置に搭載されたコンピュータを機能させるプログラムであって、
送信元アドレス及び固有識別番号を含む経路更新メッセージを定期的にブロードキャストで送信する経路更新メッセージ送信手段と、
前記経路更新メッセージを受信した際に、当該経路更新メッセージのパスリストに更に当該ノード装置の固有識別番号を含めて、当該経路更新メッセージを中継転送する中継転送手段と
してコンピュータを機能させるノード装置用のプログラムにおいて、
前記経路更新メッセージの送信元アドレス毎に、中継されたノード装置の固有識別番号の連続からなるパスリストをパス記録テーブルに記録し、隣接ノード装置間のリンク毎に、前記経路更新メッセージが通過している可用時間を測定し、該可用時間に基づくリンク可用数をリンク記録テーブルに記録するリンク可用数計数手段と、
評価時間Ｔについて、前記リンク可用数に基づいたリンク可用率を算出するリンク可用率算出手段と、
パスリスト毎に、前記リンク可用率を乗算することによってパス可用率を算出するパス可用率算出手段と、
前記ルートマップ設定手段に対して、前記送信元アドレスのパケットに対する優先パラメータに、前記パス可用率の大きさに応じた値を設定する優先値設定手段と
してコンピュータを機能させることを特徴とするノード装置用のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−１８３５２６（Ｐ２０１０−１８３５２６Ａ）
【公開日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願番号】特願２００９−２７７５０（Ｐ２００９−２７７５０）
【出願日】平成２１年２月９日（２００９．２．９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願日】平成２１年２月９日（２００９．２．９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]