ノード装置、最適パス決定方法及びプログラム
【課題】メッシュ型ネットワークにおいて、ノード装置間の最適パスを決定するための処理負荷を軽減する。
【解決手段】不通リンク決定部１３のネットワーク経路情報取得手段１３１は、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムの実行結果から、リンクのＲＴＴ及び経由ルータ台数を取得し、ＢＧＰまたはＯＳＰＦの経路制御プロトコルの分析結果から、リンクのＡＳ経由数／ルータ経由数及びコストを取得する。不通リンク決定手段１３２は、リンクのＲＴＴ等に基づいて、伝送性能が劣ると予想される候補リンクを計測対象から除外し、最適パスの決定に際してその候補リンクを不通リンクとして扱う。これにより、計測対象となる候補リンク数を削減でき、プローブパケットの送出総量を削減できる。また、最適パスを決定するための計算量も削減できる。
【解決手段】不通リンク決定部１３のネットワーク経路情報取得手段１３１は、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムの実行結果から、リンクのＲＴＴ及び経由ルータ台数を取得し、ＢＧＰまたはＯＳＰＦの経路制御プロトコルの分析結果から、リンクのＡＳ経由数／ルータ経由数及びコストを取得する。不通リンク決定手段１３２は、リンクのＲＴＴ等に基づいて、伝送性能が劣ると予想される候補リンクを計測対象から除外し、最適パスの決定に際してその候補リンクを不通リンクとして扱う。これにより、計測対象となる候補リンク数を削減でき、プローブパケットの送出総量を削減できる。また、最適パスを決定するための計算量も削減できる。
【発明の詳細な説明】
【技術分野】
【０００１】
メッシュ型ネットワークにおいて、ノード間のリンクの利用可能帯域を計測し、この計測結果から最適な伝送パス（最適パス）を動的に決定するノード装置、最適パス決定方法及びプログラムに関する。
【背景技術】
【０００２】
メッシュ型ネットワークは、３つ以上のノードがそれぞれ相互に接続され、網目状に構成された伝送路をいう。メッシュ型ネットワークでは、２つのノード間の伝送経路は、その２つのノードを直接繋ぐ最短パスの経路だけではなく、他のノードを経由して繋ぐ迂回パスの経路も存在する。このため、２つのノード間の伝送経路に障害が発生した場合であっても、他のノードを経由する迂回パスによって、伝送を継続することができる。このメッシュ型ネットワークにおいては、ノード間のリンクが局所的に混雑することによって、最短パスよりも迂回パスの利用可能帯域の方が広くなる場合がある。
【０００３】
以下、「リンク」は、２つの（オーバーレイ）ノードを直接結ぶ経路をいい、「パス」は、２つの（オーバーレイ）ノードを結ぶ経路一般（途中に他のノードを経由する経路を含む）をいう。また、事業者により素材映像伝送を実現するメッシュ型ネットワークのシステムにおいて、メッシュ型ネットワークを構成するノードは、全て管理者によって管理されており（アドレスが既知であり）、ノードが頻繁に参加または離脱することはないものとする。
【０００４】
従来、ネットワークにおけるノード間の最適パスを決定する手法が知られている（例えば、特許文献１を参照）。この特許文献１の手法は、ネットワーク全体の処理負荷の低減を考慮して、ノード間伝送路の負荷情報に基づいてノードのグルーピングを行い、受信するデータに基づいてトラフィック情報（利用可能帯域）を計測し、トラフィック情報に基づいて最適パスを決定するものである。
【０００５】
この利用可能帯域を計測する手法として、例えば、パケットペア法が知られている。図１４は、パケットペア法による利用可能帯域の計測手法について説明する図である。図１４を用いて、ノード１０１からノード１０２までの間のリンク１−２の帯域（利用可能帯域）１−２を計測する手法について簡単に説明する。ノード１０１からノード１０２までの間のリンクに、帯域Ｗのボトルネックが存在するものとする。起点のノード１０１は、充分に短い時間間隔Ｔで、パケット長Ｌのプローブパケットを連続的に終点のノード１０２へ送信する。リンク１−２におけるいずれかのパス上で他のトラフィックの影響を受けない場合には、終点のノード１０２は、ノード１０１から送信されたプローブパケットを、時間間隔Ｔ’＝Ｌ／Ｗで受信する。したがって、ノード１０２は、受信するプローブパケットの時間間隔を算出することにより、ボトルネックの帯域（利用可能帯域）Ｗを計測することができる。実際には、計測を繰り返した結果を統計的に処理することにより、他のトラフィックの影響を排除した利用可能帯域が推定される。
【０００６】
図１３は、図１４に示したパケットペア法に用いるプローブパケットの構成を示す図である。図１３に示すように、プローブパケットは、Ｖｅｒｓｉｏｎ（バージョン）、Ｈｅａｄｅｒ Ｌｅｎｇｔｈ（ヘッダ長）等のヘッダと、ダミーデータが格納されたペイロードとにより構成される。パケットペア法においては、プローブパケット長が長い場合は計測精度が向上するから、プローブパケット長を、ＩＰネットワークのＭＴＵ（Ｍａｘｉｍｕｍ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｕｎｉｔ：最大転送単位）として一般的な１５００バイトに固定することが多い。このため、プローブパケットは、先頭のＩＰヘッダ部分を除いて、ダミーデータにより構成される。
【０００７】
図１５は、従来のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、相互に接続された複数のノード１０１〜１０４等により、網目状に構成されている。ノード１０１は、プローブパケットをノード１０２〜１０４へ送信し、ノード１０２〜１０４もプローブパケットを他のノード１０１〜１０４へ送信する。ノード１０１は、プローブパケットをノード１０２〜１０４からそれぞれ受信すると、隣接リンクの利用可能帯域（ノード１０２からノード１０１までの間のリンク２−１の帯域２−１、ノード１０３からノード１０１までの間のリンク３−１の帯域３−１、ノード１０４からノード１０１までの間のリンク４−１の帯域４−１）を、前述のパケットペア法によりそれぞれ計測し、結果パケットに格納してノード１０２〜１０４へ送信する。ノード１０２〜１０４も、プローブパケットを受信すると、隣接リンクの利用可能帯域をそれぞれ計測し、結果パケットに格納して他のノード１０１〜１０４へ送信する。
【０００８】
そして、ノード１０１〜１０４は、他のノード１０１〜１０４において計測された隣接リンクの利用可能帯域が格納された結果パケットを受信し、全てのリンクの利用可能帯域を取得する。そして、取得した全リンクの利用可能帯域に基づいて最適パスを決定する。図１５に示すように、ノード１０３は、全リンクの利用可能帯域に基づいて、ノード１０１からノード１０３までの間の最適パスを決定する際に、ノード１０１からノード１０３までの間のパスを構成するリンクの組み合わせを求め、その組み合わせ毎にリンクの帯域の最小値が最も大きいリンクの組み合わせを最適パスとして決定する。例えば、パスを構成するリンクの組み合わせとしてリンク１−３、リンク１−２，２−３、リンク１−４，４−３、リンク１−４，４−２，２−３、及びリンク１−２，２−４，４−３が存在し、それぞれのリンクの帯域が、（帯域１−２＜帯域２−３、帯域２−４、帯域４−３）、（帯域１−４＜帯域２−３、帯域４−２、帯域４−３）、（帯域１−２＜帯域１−４＜帯域１−３）の関係にある場合、リンク１−３を最適パスとして決定する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−１５３９７８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、図１５に示した従来のノード１０１〜１０４を含むメッシュ型ネットワーク１００では、以下の問題があった（課題（１）（２））。
【００１１】
〔課題（１）〕
従来のメッシュ型ネットワーク１００では、ノードがｎ台の場合、利用可能帯域を計測する計測対象となるリンク（以下、候補リンクという。）の総数がｎ（ｎ−１）であり、ｎの増加に従って、ｎ２のオーダーで増大する。候補リンク数の増加は、プローブパケットの送出量と計測結果を交換する結果パケットの送出量の増大につながり、メッシュ型ネットワーク１００への負荷を増加させる。また、候補リンクが多数存在すると、候補リンクから最適パスを決定する処理（例えば、総当たり法による全リンクの利用可能帯域の計算及び比較処理、並びにダイクストラ法による最適パスの決定処理）の計算量も増大する。
【００１２】
〔課題（２）／付加的な課題〕
また、従来のメッシュ型ネットワーク１００では、隣接リンクの利用可能帯域を計測する帯域計測が行われ、そして、計測結果を交換するために、それぞれ別のパケット（帯域計測のときはプローブパケット、計測結果を交換するときは結果パケット）が送受信されるため、メッシュ型ネットワーク１００へのデータ送信量が増大する。また、前述のとおり、プローブパケットは、計測精度の向上を図るために、ＭＴＵとほぼ等しい固定長に設定されることが多く、メッシュ型ネットワーク１００に与える負荷が大きいにも関わらず、そのペイロード部分はダミーデータのみで構成され、有効に使用されていない。
【００１３】
そこで、本発明は前記課題を解決するためになされたものであり、その目的は、メッシュ型ネットワークにおいて、ノード装置間の最適パスを決定するための処理負荷を軽減可能なノード装置、最適パス決定方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明者らは、上記目的を達成すべく鋭意検討を行った。その結果、各ノード装置において、メッシュ型ネットワークの経路情報を分析し、分析結果（例えば、ｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムの実行により得られるＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ：ラウンドトリップ時間）または経由ルータ台数、ＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）またはＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）等の経路制御プロトコルにて送受信されるメッセージの分析により得られる経由ＡＳ数／経由ルータ台数またはコスト）に基づいて、伝送性能が劣ると予想される候補リンクを計測対象から除外し、最適パスの決定に際してその候補リンクを不通リンクとして扱う、いわゆる候補リンクの足切りを行うことを見出した。
【００１５】
これにより、伝送性能が劣ると予想される候補リンクは、最適パスに含まれるリンクにはなり得ないから、利用可能帯域の計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができる。
【００１６】
また、本発明者らは、各ノード装置において、計測した隣接リンクの利用可能帯域を、帯域計測に用いるプローブパケットに格納して送信することを見出した。
【００１７】
これにより、各ノード装置は、プローブパケットとは別に、計測結果の利用可能帯域を送信する必要がなく、帯域計測と計測結果の交換とをプローブパケットによって同時に実現することができる。最適パスを決定するノード装置は、他のノード装置から送られてくるプローブパケットを受信することにより、隣接リンクの利用可能帯域を計測することができ、同時に、プローブパケットに格納された利用可能帯域を取得することができる。つまり、プローブパケットを受信し、自ノード装置における隣接リンクの利用可能帯域の計測と、他のノード装置における隣接リンクの利用可能帯域の取得とを同時に行うことにより、メッシュ型ネットワークにおいて送受信されるパケットの量を減らし、ネットワーク負荷を一層低減することができる。したがって、前記課題（２）を解決することができる。
【００１８】
すなわち、本発明によるノード装置は、複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定するノード装置において、当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するネットワーク経路情報取得手段、及び、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断し、前記リンクを不通リンクとして決定する不通リンク決定手段を有する不通リンク決定部と、当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測する帯域計測部と、前記帯域計測部により計測された、前記不通リンクを除外した候補リンクの利用可能帯域を結果パケットに格納し、他のノード装置へ送信し、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得する結果パケット処理部と、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、前記結果パケット処理部により取得された他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定する最適パス決定部と、を備えたことを特徴とする。
【００１９】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークを管理するために用いるｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムを実行し、この実行結果に基づいて、当該ノード装置と他のノード装置との間のルータ台数またはＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２０】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークの経路を制御するためのＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）に用いるＢＧＰメッセージのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、他のノード装置を内包するＡＳを始点として送信され、当該ノード装置を内包するＡＳへ送信されたＢＧＰメッセージを選定し、前記選定したＢＧＰメッセージのＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号から、当該ノードと他のノードとの間のＡＳ数をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２１】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークの経路を制御するためのＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）に用いる広告メッセージに基づいて、当該メッセージが送信されたルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得し、前記ネットワークアドレス及びコスト情報から、当該ノード装置と他のノード装置との間のルータ台数またはコスト情報をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２２】
また、本発明によるノード装置は、前記結果パケット処理部の代わりにプローブパケット処理部を備え、前記プローブパケット処理部が、当該ノード装置における隣接リンクの利用可能帯域を計測するためのプローブパケットを他のノード装置から受信し、他のノード装置において隣接リンクの利用可能帯域を計測させるためのプローブパケットに、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を格納し、前記プローブパケットを他のノード装置へ送信することを特徴とする。
【００２３】
さらに、本発明による最適パス決定方法は、複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定する方法において、当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するステップと、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断するステップと、前記伝送性能が劣ると判断したリンクを不通リンクとして決定するステップと、当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測するステップと、前記計測した、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を、結果パケットに格納し、他のノード装置へ送信するステップと、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得するステップと、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定するステップと、を有することを特徴とする。
【００２４】
また、本発明による最適パス決定プログラムは、コンピュータを、前記ノード装置として機能させることを特徴とする。
【発明の効果】
【００２５】
以上のように、本発明によれば、メッシュ型ネットワークにおいて、ノード装置間の最適パスを決定するための処理負荷を軽減することが可能となる。
【図面の簡単な説明】
【００２６】
【図１】実施例１のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【図２】実施例１におけるノードの処理概要を示すフローチャートである。
【図３】実施例１におけるノードの構成を示すブロック図である。
【図４】ｐｉｎｇプログラムの実行結果例を示す図である。
【図５】ｔｒａｃｅｒｏｕｔｅプログラムの実行結果例を示す図である。
【図６】ＢＧＰメッセージの例を示す図である。
【図７】ＢＧＰメッセージに基づいて作成された経路マップ（ＡＳマップ）例を示す図である。
【図８】ＯＳＰＦのＬＳＡに基づいて作成されたルータマップ情報例を示す図である。
【図９】実施例４のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【図１０】実施例４におけるノードの処理概要を示すフローチャートである。
【図１１】実施例４におけるノードの構成を示すブロック図である。
【図１２】実施例４，５におけるプローブパケットの構成例を示す図である。
【図１３】従来のプローブパケットの構成を示す図である。
【図１４】パケットペア法による利用可能帯域の計測手法について説明する図である。
【図１５】従来のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための形態について、図面を参照して説明する。本発明は、メッシュ型ネットワークにおいて、ノード（ノード装置）間の最適パスを決定する際の候補リンクを削減することを特徴とする。実施例１は、ＩＰネットワーク管理用のｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムの実行結果を用いてネットワーク経路情報を取得し、候補リンクを削減する例である。実施例２は、経路制御用のＢＧＰに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例３は、経路制御用のＯＳＰＦに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例４は、実施例１〜３のいずれかの例に加え、隣接リンクの利用可能帯域をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。実施例５は、実施例４の拡張例であり、隣接リンクの利用可能帯域の属性もプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。実施例１〜３により、前記課題（１）を解決することができる。また、実施例４，５により、前記課題（１）に加え、課題（２）を解決することができる。ここで、ネットワーク経路情報は、経路の伝送性能を判定する際に用いる情報である。
【実施例１】
【００２８】
まず、実施例１について説明する。実施例１は、前述のとおり、ＩＰネットワーク管理用のｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムの実行結果を用いてネットワーク経路情報を取得し、候補リンクを削減する例である。実施例１は、ＩＰネットワーク上でオーバーレイ伝送網を構築する場合に適用がある。
【００２９】
図１は、実施例１のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、例えばインターネットであり、相互に接続された複数のノード１〜４等により、網目状に構成されている。後述する実施例２，３においても同様である。
【００３０】
〔ノードの処理概要／実施例１〕
図２は、図１に示したノード１の処理概要を示すフローチャートである。ノード２〜４もノード１と同じ処理を行う。この処理は、例えば、ノード１〜４間で映像データを送受信する際に、利用可能帯域を計測し、最適パスを決定し、決定した最適パスにて映像データを送受信するものである。後述する実施例２，３においても同様である。
【００３１】
ノード１は、プローブパケットの送信タイミングを判定すると（ステップＳ２１：Ｙ）、ノード２〜４において利用可能帯域を計測するためのプローブパケットをノード２〜４へ送信する（ステップＳ２０１）。送信タイミングは、例えば所定の時間間隔であり、プローブパケットは、メッシュ型ネットワーク１００の状態変化に対応するために、定期的に送信される。
【００３２】
ノード１は、ノード２〜４からプローブパケットをそれぞれ受信した場合（ステップＳ２２：Ｙ）、図１４に示したように、プローブパケットの受信間隔を算出することにより、隣接リンクの利用可能帯域（ノード２からノード１までの間のリンク２−１の帯域２−１、ノード３からノード１までの間のリンク３−１の帯域３−１、ノード４からノード１までの間のリンク４−１の帯域４−１）をそれぞれ計測する（ステップＳ２０２）。利用可能帯域を計測した隣接リンクが候補リンクとなる。この場合、ノード１は、ノード２〜４から送信されるプローブパケットを定期的に受信する。
【００３３】
ノード１は、不通リンクの更新タイミングを判定すると（ステップＳ２３：Ｙ）、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを実行し、実行結果から、自ノード１と相手ノード２〜４との間のルータ台数及び自ノード１から相手ノード２〜４までのＲＴＴを示すネットワーク経路情報を取得する（ステップＳ２０３）。更新タイミングは、例えば所定の時間間隔とする。そして、ノード１は、ネットワーク経路情報に基づいて不通リンクを決定し（ステップＳ２０４）、候補リンク（リンク２−１，３−１，４−１）から不通リンクを除外する（ステップＳ２０５）。図１に示すように、例えば、ノード１は、ネットワーク経路情報に基づいて、リンク２−１が不通リンクであると決定し、候補リンクから不通リンク２−１を除外する。
【００３４】
ノード１は、結果パケットの送信タイミングを判定すると（ステップＳ２４：Ｙ）、前述の例では、不通リンク２−１を除外した候補リンク３−１，４−１の利用可能帯域（帯域３−１，４−１）を結果パケットに格納し、結果パケットをノード２〜４へ送信する（ステップＳ２０６）。送信タイミングは、例えば所定の時間間隔とする。これにより、ノード２〜４は、結果パケットを受信し、結果パケットから、ノード１における不通リンクを除外した候補リンクの利用可能帯域を取得することができる。
【００３５】
ノード１は、結果パケットをノード２〜４からそれぞれ受信した場合（ステップＳ２５：Ｙ）、受信した結果パケットから、他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を取得する（ステップＳ２０７）。
【００３６】
ノード１は、最適パスを決定するタイミングを判定すると（ステップＳ２６：Ｙ）、自ノード１において不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４において不通リンクを除外した候補リンクの利用可能帯域に基づいて、例えば前述した手法により、最適パスを決定する（ステップＳ２０８）。
【００３７】
図１に示すように、ノード２は、リンク１−２が不通リンクであると決定し、ノード４は、リンク３−４が不通リンクであると決定する。この場合、例えばノード３は、ノード１，２，４から、不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、不通リンクを除外した候補リンクの利用可能帯域を取得する。そして、ノード３は、全リンクのうちの不通リンク２−１，１−２，１−４，２−４，３−４を除外した候補リンク１−３，２−３，４−３，３−１，４−１，４−２，３−２に基づいて、最適パスを決定する。
【００３８】
〔ノードの構成／実施例１〕
次に、図１に示したノード１の構成について説明する。図３は、ノード１の構成を示すブロック図である。このノード１は、通信部１１、プローブパケット処理部１２、不通リンク決定部１３、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７を備えている。
【００３９】
ノード１の通信部１１は、メッシュ型ネットワーク１００に対してプローブパケット及び結果パケットの送受信を行う。また、後述するｐｉｎｇプログラム及びｔｒａｃｅｒｏｕｔｅプログラムの実行に伴って、各種メッセージの送受信を行う。
【００４０】
プローブパケット処理部１２は、プローブパケットの送信タイミングにおいて、ノード２〜４において利用可能帯域を計測するためのプローブパケットを生成し、このプローブパケットを、通信部１１を介してノード２〜４へ送信する。また、プローブパケット処理部１２は、ノード２〜４から通信部１１を介して、プローブパケットを受信し、プローブパケットの受信間隔を算出し、受信間隔等の情報をプローブパケット受信情報として帯域計測部１４に出力する。また、プローブパケット処理部１２は、不通リンク決定部１３から不通リンク情報を入力し、不通リンクの相手ノードに対するプローブパケットの送信を停止する。尚、プローブパケット処理部１２は、後述する記憶部１７から、不通リンクを除外した候補リンクの利用可能帯域である自ノード帯域情報を読み出し、この自ノード帯域情報に基づいて不通リンクを特定し、不通リンクの相手ノードに対するプローブパケットの送信を停止するようにしてもよい。この場合、不通リンクの利用可能帯域にはデータが格納されていない。
【００４１】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、メモリ（図示せず）からｐｉｎｇプログラムを読み出して実行し、通信部１１を介してメッセージの送受信を行い、プログラム実行結果として、相手ノード２〜４までの間に存在するルータの台数及び相手ノード２〜４までのＲＴＴを取得する。または、ネットワーク経路情報取得手段１３１は、メモリからｔｒａｃｅｒｏｕｔｅプログラムを読み出して実行し、通信部１１を介してメッセージの送受信を行い、プログラム実行結果として、相手ノード２〜４までの間に存在するルータのＩＰアドレス及びルータ（相手ノード２〜４を含む）までのＲＴＴを取得し、ルータのＩＰアドレスの数からルータ台数を算出し、相手ノード２〜４までのＲＴＴを取得する。ネットワーク経路情報取得手段１３１は、ルータ台数及びＲＴＴをネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００４２】
ｐｉｎｇプログラムは、ＩＰネットワークの管理のために一般的に用いられ、インターネット、イントラネット等のＴＣＰ／ＩＰネットワークを診断するプログラムである。相手ノードのＩＰアドレスを指定することにより、ＩＣＭＰ（Ｉｎｔｅｒｎｅｔ Ｃｏｎｔｒｏｌ Ｍｅｓｓａｇｅ Ｐｒｏｔｏｃｏｌ）を使って所定量のデータを送信し、相手ノードから返信があるか否か、返信がある場合はその返信時間等によって、ネットワークを診断する。このプログラムにより、自ノードと相手ノードとの間のルータ台数及び自ノードから相手ノードまでのＲＴＴを取得することができる。ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレスを指定してｐｉｎｇプログラムを実行し、実行結果として、ルータ台数及びＲＴＴを取得する。
【００４３】
図４は、ｐｉｎｇプログラムの実行結果例を示す図である。（尚、図４では実際には使われていないＩＰアドレスを記載している。）図４に示すように、ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレス「１９２．１６８．０．１」を指定してｐｉｎｇプログラムを実行した結果、１回目のシーケンス（ｉｃｍｐ＿ｓｅｑ＝０）の結果が、ルータ台数が１８（ｔｔｌ（ｔｉｍｅ ｔｏ ｌｉｖｅ）＝２３７であるから、２５５−２３７＝１８）、ＲＴＴが９．９５４ｍｓ（ｔｉｍｅ＝９．９５４ｍｓ）であり、２〜１１回目のシーケンスの結果を合わせて、ＲＴＴの最小値、平均値、最大値及び平均偏差値（７．３６９／８．７０７／・・・ｍｓ）を取得する。このように、ネットワーク経路情報取得手段１３１は、自ノードと相手ノードとの間のルータ台数（図４の場合、１７台）、及び自ノードから相手ノードまでのＲＴＴ（図４の場合、平均値８．７０７ｍｓ）を取得する。
【００４４】
一方、ｔｒａｃｅｒｏｕｔｅプログラムも、ＩＰネットワークの管理のために一般的に用いられ、目的のホストまでの経由ルータを一覧するためのプログラムである。このプログラムにより、自ノードと相手ノードとの間に存在するルータのＩＰアドレス及び自ノードから各ルータ（相手ノードを含む）までのＲＴＴを取得することができる。ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレスを指定してｔｒａｃｅｒｏｕｔｅプログラムを実行し、実行結果として、ルータのＩＰアドレス及び各ルータ（相手ノードを含む）までのＲＴＴを取得する。
【００４５】
図５は、ｔｒａｃｅｒｏｕｔｅプログラムの実行結果例を示す図である。（尚、図５では実際には使われていないＩＰアドレスを記載している。）図５に示すように、ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレス「１９２．１６８．０．１」を指定してｔｒａｃｅｒｏｕｔｅプログラムを実行した結果、相手ノードとの間に存在する各ルータの番号（２〜１８）、各ルータのＩＰアドレス（１７２．３１．２５４．２５４，・・・）、各ルータ（相手ノードを含む）までのＲＴＴ（０．５０８ｍｓ，・・・，７．２８４ｍｓ）を取得する。図５において、左端の「２」から「１８」までの各行の情報が各ルータに関する情報であり、「１」の情報が自ノードに関する情報であり、「１９」の情報が相手ノードに関する情報である。このように、ネットワーク経路情報取得手段１３１は、自ノードと相手ノードとの間に存在するルータのＩＰアドレス（１７台のルータのＩＰアドレス１７２．３１．２５４．２５４，・・・）、及び自ノードから各ルータ（相手ノードを含む）までのＲＴＴ（０．５０８ｍｓ，・・・，７．２８４ｍｓ）を取得する。そして、ネットワーク経路情報取得手段１３１は、ルータのＩＰアドレスの数から、自ノードと相手ノードとの間のルータ台数（図５の場合、１７台）を算出し、相手ノードまでのＲＴＴ（例えば、「１９」の情報における７．６５７ｍｓ，７．４６３ｍｓ，７．２８４ｍｓの平均値）を算出する。
【００４６】
尚、ｐｉｎｇプログラム及びｔｒａｃｅｒｏｕｔｅプログラムにより取得されるルータ台数及びＲＴＴ等は、長期的に変化する。そこで、ネットワーク経路情報取得手段１３１は、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを、所定周期にて適宜繰り返して実行する。
【００４７】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４までの間のルータ台数、及び自ノード１から相手ノード２〜４までのＲＴＴ）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００４８】
例えば、不通リンク決定手段１３２は、相手ノードまでの間のルータ台数と所定のしきい値とを比較し、ルータ台数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。または、相手ノードまでのＲＴＴと所定のしきい値とを比較し、ＲＴＴが所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。これは、多数のルータを経由するリンク及びＲＴＴの大きいリンクは、利用可能帯域が狭く伝送性能が劣る傾向にあるからである。尚、不通リンク決定手段１３２は、他のリンクのルータ台数またはＲＴＴも含めて平均的なルータ台数またはＲＴＴを算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ルータ台数またはＲＴＴのばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００４９】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、ネットワークの負荷、及び最適パスを決定するための処理負荷を軽減することができる。
【００５０】
帯域計測部１４は、プローブパケット処理部１２からプローブパケット受信情報（ノード２〜４から送信されたプローブパケットの受信間隔等）を入力すると共に、不通リンク決定部１３から不通リンク情報を入力する。帯域計測部１４は、前述したとおり、プローブパケット受信情報における受信間隔等の情報に基づいて、ノード２〜４との間の隣接リンク（候補リンク２−１，３−１，４−１）の利用可能帯域を計測する。また、帯域計測部１４は、候補リンク２−１，３−１，４−１から不通リンクを除外し、不通リンクを除外した候補リンクの利用可能帯域を自ノード帯域情報として記憶部１７に格納する。尚、帯域計測部１４は、計測した隣接リンク（候補リンク）の利用可能帯域を記憶部１７に格納し、入力した不通リンク情報の示す不通リンクの利用可能帯域を記憶部１７から削除するようにしてもよい。
【００５１】
結果パケット処理部１５は、記憶部１７から自ノード帯域情報（自ノード１における不通リンクを除外した候補リンクの利用可能帯域）を読み出して結果パケットに格納し、この結果パケットを、通信部１１を介してノード２〜４へ送信する。また、結果パケット処理部１５は、ノード２〜４から通信部１１を介して、結果パケットを受信し、結果パケットから、ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を取得する。そして、結果パケット処理部１５は、ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を他ノード帯域情報として記憶部１７に格納する。これにより、記憶部１７には、自ノード１における不通リンクを除外した候補リンクの利用可能帯域である自ノード帯域情報、及びノード２〜４における不通リンクを除外した候補リンクの利用可能帯域である他ノード帯域情報が格納される。
【００５２】
最適パス決定部１６は、記憶部１７から自ノード帯域情報及び他ノード帯域情報（自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及びノード２〜４における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、前述したとおり、最適パスを決定する。
【００５３】
以上のように、実施例１のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを実行して、自ノード１から相手ノード２〜４までの間のルータ台数、及び自ノード１から相手ノード２〜４までのＲＴＴを示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ルータ台数の多いリンクまたはＲＴＴの大きいリンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンク２−１，３−１，４−１から不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００５４】
これにより、不通リンクを除外した候補リンクから最適パスが決定されるから、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワーク１００において、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【実施例２】
【００５５】
次に、実施例２について説明する。実施例２は、前述のとおり、経路制御用のＢＧＰに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例２は、インターネット上に配置したノード間でオーバーレイ伝送網を構築する場合に適用がある。
【００５６】
〔ノードの処理概要／実施例２〕
実施例２のノードを含むメッシュ型ネットワークの構成は、図１に示した構成と同様である。また、実施例２のノード１は、図２に示した実施例１のステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８と同じ処理を行い、ステップＳ２０３とは異なる処理を行う。ステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８の説明については省略する。
【００５７】
ノード１は、図２に示した実施例１のステップＳ２０３の代わりに、ＢＧＰに用いるメッセージを受信して分析し、分析結果から、自ノード１と相手ノード２〜４との間に存在するＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ：自律システム）の数を示すネットワーク経路情報を取得する（ステップＳ２０３）。
【００５８】
〔ノードの構成／実施例２〕
次に、実施例２におけるノード１の構成について説明する。実施例２におけるノード１の構成は、図３に示した実施例１の構成と同じであるが、実施例２におけるノード１の不通リンク決定部１３が、実施例１の不通リンク決定部１３とは異なる処理を行う点で相違する。通信部１１、プローブパケット処理部１２、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の説明については省略する。
【００５９】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、ＢＧＰに用いるメッセージを、通信部１１を介して受信し、受信したメッセージを分析し、分析結果として、相手ノード２〜４までの間のＡＳ数を取得する。ネットワーク経路情報取得手段１３１は、ＡＳ数をネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００６０】
ＢＧＰは、インターネットを構成するＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）ネットワーク間において、経路制御のためのメッセージをＢＧＰルータ間で交換する経路制御プロトコルである。ＢＧＰでは、各ＩＳＰネットワークをＡＳといい、それぞれのＡＳにユニークな番号（ＡＳ番号）が付与されている。各ＡＳのＢＧＰルータは、自ＡＳの内部に含むネットワークアドレスと自らのＡＳ番号とを含むＢＧＰメッセージを接続先ＡＳのＢＧＰルータへ送信する。接続先のＢＧＰルータは、このＢＧＰメッセージを受信すると、受信したＢＧＰメッセージの先頭に自らのＡＳ番号を追記し（これをＡＳ−ＰＡＴＨ属性という。）、他の接続先ＡＳのＢＧＰルータへ送信する。尚、ＢＧＰの詳細については「Ｒ．Ｈａｌｈｏｔｒａ著、清水奨訳、入門ＩＰルーティング、オライリージャパン、２００２／８」の第７章を参照されたい。
【００６１】
ここで、ノード１は、ＡＳ−ＰＡＴＨ属性を含むＢＧＰメッセージを、ノード１を内包するＡＳのＢＧＰルータから受信することにより、取得することができる。また、一般に、インターネット上に存在するオーバーレイ伝送網を構成するノードのＩＰアドレスが既知であれば、後述するプログラムにより、そのノードを内包するＡＳ番号も取得することができる。つまり、ノード１は、自ノードを内包するＡＳのＡＳ番号と、相手ノードを内包するＡＳのＡＳ番号を取得できる。
【００６２】
そこで、ネットワーク経路情報取得手段１３１は、自ノード１及び相手ノード２〜４のＩＰアドレスを指定して所定のプログラムを実行し、実行結果としてそのノード１〜４を含むそれぞれのＡＳのＡＳ番号を取得する。例えば、所定のプログラムとして「ＲＡＤｄ、ＭＥＲＩＴ ＮＥＴＷＯＲＫ ＩＮＣ．、ＲＯＵＴＩＮＧ ＡＳＳＥＴＳ ＤＡＴＡＢＡＳＥ、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ：http://www.radb.net/＞」のサービスを利用することができる。そして、ネットワーク経路情報取得手段１３１は、自ノード１を内包するＡＳに到着するＢＧＰメッセージを受信し、ＢＧＰメッセージからＡＳ−ＰＡＴＨ属性を取得し、そのＡＳ−ＰＡＴＨ属性が、相手ノードを内包するＡＳ番号で始まると判断した場合、そのＢＧＰメッセージから取得したＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、自ノード１と相手ノードとの間に存在するＡＳを特定し、そのＡＳ数を取得する。
【００６３】
図６は、ＢＧＰメッセージの例を示す図である。ＢＧＰメッセージは、当該メッセージを生成した日時（ＤＡＴＥ＆ＴＩＭＥ）、当該メッセージのタイプ（ＴＹＰＥ）、自ノードの隣のＡＳ番号（ＳＯＵＲＣＥ＿ＡＳ）、ＡＳのネットワークアドレス（ＰＲＥＦＩＸ）及びＡＳ−ＰＡＴＨ属性（ＡＳ＿ＰＡＴＨ）により構成される。タイプにおいて、Ｂはある時刻における経路一覧、Ａは経路の追加・更新、Ｗは経路の削除を示している。（尚、実際のＢＧＰメッセージではＡＳ番号として０〜６５５３５の数が記述されるが、ここではＡＳ番号を＃Ｘのように記述している。）図６に示すＢＧＰメッセージは、ＡＳ−＃Ｒに内包される自ノードからＡＳ−＃Ｓに内包される相手ノード（ネットワークアドレスｗｗ．ｘｘ．ｙ．ｚ／１６）との間に存在するＡＳ数を取得することを目的として、ＡＳ−＃Ｒにおいて観測されたＢＧＰメッセージから、ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージを抜き出した一覧である。すなわち、図６に示すＢＧＰメッセージは、ノード１の不通リンク決定部１３におけるネットワーク経路情報取得手段１３１が、通信部１１を介して受信したＢＧＰメッセージのうち、ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージを抜き出した一覧である。
【００６４】
図７は、図６に示したＡＳ−ＰＡＴＨ属性から生成された経路マップ（ＡＳマップ）を示す図である。ネットワーク経路情報取得手段１３１は、図６に示したＢＧＰメッセージ（ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージ）を分析し、ＡＳ−＃Ｒに内包される自ノード１とＡＳ−＃Ｓに内包される相手ノードとの間に存在するＡＳのマップ（ＡＳマップ）を、図７に示すように生成する。図７に示すように、自ノード１と相手ノードとの間には、ＡＳ−＃Ｂ，＃Ｃ，＃Ｄ経由の第１の経路、ＡＳ−＃Ｔ，＃Ａ経由の第２の経路、ＡＳ−＃Ｅ，＃Ｔ，＃Ａ経由の第３の経路、及びＡＳ−＃Ｆ，＃Ｇ，＃Ｈ経由の第４の経路の合計４つの経路が存在している。ネットワーク経路情報取得手段１３１は、ＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性から生成したＡＳマップに基づいて、第１の経路の経由ＡＳ数３、第２の経路の経由ＡＳ数２、第３の経路の経由ＡＳ数３、及び第４の経路の経由ＡＳ数３を取得し、このうち最小のＡＳ数をネットワーク経路情報として不通リンク決定手段１３２に出力する。なぜなら、ＢＧＰによる経路制御においては通常、経由ＡＳ数の最も少ない経路をパケットの実際の転送経路として採用するからである。
【００６５】
尚、ＡＳマップは、ＩＳＰ間の接続の変更により変わることがあり得る。そこで、ネットワーク経路情報取得手段１３１は、所定周期にて適宜繰り返して、受信したＢＧＰメッセージを分析しＡＳマップを作成する。また、ＢＧＰメッセージの分析により生成されるＡＳマップは、必ずしも実際のメッシュ型ネットワーク１００の経路を反映していない場合もあり得る。そこで、ＡＳマップの分析により一旦計測対象から外れた候補リンクに対しても、適宜計測を行い、その正当性を検証する。
【００６６】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４との間の各リンクにおけるＡＳ数）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００６７】
例えば、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるＡＳ数と所定のしきい値とを比較し、ＡＳ数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。これは、多数のＡＳを経由するリンクは、経由するルータ台数も多くて利用可能帯域が狭く、伝送性能が劣る傾向にあるからである。尚、不通リンク決定手段１３２は、他のリンクのＡＳ数も含めて平均的なＡＳ数を算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ＡＳ数のばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００６８】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、最適パスを決定するための処理負荷を軽減することができる。
【００６９】
以上のように、実施例２のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ＢＧＰメッセージを受信し、ＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性から、相手ノードを含むＡＳの番号から始まるＢＧＰメッセージを特定し、このＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性を分析することにより、自ノード１と相手ノード２〜４との間のＡＳマップを生成し、ＡＳマップに基づいて、自ノード１と相手ノード２〜４との間の各リンクにおけるＡＳ数を示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ＡＳ数の多いリンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンクから不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００７０】
これにより、実施例１と同様に、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワークにおいて、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【００７１】
尚、実施例２において、以下に示す他の手法を用いることができる。例えば、図１に示したメッシュ型ネットワーク１００及び図７に示したＡＳマップにおいて、前述の「ＲＡＤｄ」のプログラムを実行することにより、ノード１がＡＳ−＃Ｒに、ノード２がＡＳ−＃Ｃに、ノード３がＡＳ−＃Ｓに、ノード４がＡＳ−＃Ｔに内包されることがわかったとする。このとき、ノード１→３への直接伝送のパスとノード１→４→３への迂回伝送のパスは、ＡＳマップ上では同一の経路（ＡＳ−＃Ｒ→＃Ｔ→＃Ａ→＃Ｓ）となる。このため、両パスの利用可能帯域の計測結果は似通った結果になると予測される。
【００７２】
そこで、不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からＡＳマップの情報を入力し、ＡＳマップの情報に基づいて、同一または類似した経路を通る候補リンクが複数存在することを判定した場合、それらの複数の候補リンクのうちの一部のリンクを不通リンクに決定する。前記例の場合、不通リンク決定手段１３２は、ノード１→３への直接伝送のパス及びノード１→４→３の迂回伝送のパスのうちの例えば後者のパスを不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。
【００７３】
また、例えば、図１に示したメッシュ型ネットワーク１００及び図７に示したＡＳマップにおいて、前述と同様に、ノード１がＡＳ−＃Ｒに、ノード２がＡＳ−＃Ｃに、ノード３がＡＳ−＃Ｓに、ノード４がＡＳ−＃Ｔに内包されるものとする。この場合、ノード１→３への直接伝送のパス（ＡＳ−＃Ｒ→＃Ｔ→＃Ａ→＃Ｓ）と、ノード１→２→３の迂回伝送のパス（ＡＳ−＃Ｒ→＃Ｂ→＃Ｃ→＃Ｄ→＃Ｓ）とは、ＡＳマップ上で経路を共有しないから、ノード１→３への直接伝送とノード１→２→３の迂回伝送とは相互の干渉が少ないことが予想される。
【００７４】
そこで、不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からＡＳマップの情報を入力し、ＡＳマップの情報に基づいて、経路を共通しないパスの構成リンクだけを候補リンクとし、それ以外のリンクを伝送性能が劣ると判断して不通リンクに決定する。前記例の場合、両パスの構成リンク（この場合はリンク１−３とリンク１−２とリンク２−３の３つ）以外のリンクは全て伝送性能が劣ると判断して不通リンクに決定し、伝送に利用するパスをこの２パスに限定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、ノード１において実行される伝送アプリケーションに対し、ノード１→３とノード１→２→３の両パスを最適パスとして提示し、伝送アプリケーションには同時に両パスを使って伝送させることにより、両パスの利用可能帯域を合わせて伝送性能を向上させることができる。
【００７５】
前記実施例２では、ノード１〜４は、当該ノード１〜４をそれぞれ内包するＡＳのＢＧＰルータからＢＧＰメッセージを受信するものとして説明した。ノード１〜４は、ＢＧＰルータからＢＧＰメッセージを受信する代わりに、他のＡＳで観測したＢＧＰメッセージから、ＡＳ−ＰＡＴＨ属性に自ノードと相手ノードのＡＳ番号を含むＢＧＰメッセージを抽出し（受信し）、それらのメッセージからＡＳマップを作成するようにしてもよい。図７に示した例では、ＡＳ−＃Ｔに内包されるノードとＡＳ−＃Ｓに内包されるノードとを結ぶリンクのネットワーク経路情報を取得する際に、ＡＳ−＃Ｒで観測したＢＧＰメッセージからＡＳ−ＰＡＴＨ属性に自ノードと相手ノードのＡＳ番号を含むＢＧＰメッセージを抽出し、ＡＳマップを作成してもよい。この場合、ノード１〜４は、ＢＧＰメッセージの観測データを、所定のプログラムを実行することにより取得する。例えば、所定のプログラムとして「routeviewsプロジェクト、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ： http://www.routeviews.org/＞」「routing information serviceプロジェクト、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ：http://www.ripe.net/projects/ris/index.html」のサービスを利用し、インターネットの各所で観測したＢＧＰメッセージを蓄積して公開しているサイトから、ＢＧＰメッセージの観測データを取得することができる。
【実施例３】
【００７６】
次に、実施例３について説明する。実施例３は、前述のとおり、経路制御用のＯＳＰＦに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例３は、ＩＳＰの内部ネットワーク、企業等の専用ネットワーク等において、オーバーレイ伝送網を構築する場合に適用がある。
【００７７】
〔ノードの処理概要／実施例３〕
実施例３のノードを含むメッシュ型ネットワークの構成は、図１に示した構成と同様である。また、実施例３のノード１は、図２に示した実施例１のステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８と同じ処理を行い、ステップＳ２０３とは異なる処理を行う。ステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８の説明については省略する。
【００７８】
ノード１は、図２に示した実施例１のステップＳ２０３の代わりに、ＯＳＰＦに用いるメッセージを受信して分析し、分析結果から、自ノード１と相手ノード２〜４との間のルータ台数またはコスト（例えば、回線の速度）を示すネットワーク経路情報を取得する（ステップＳ２０３）。
【００７９】
〔ノードの構成／実施例３〕
次に、実施例３におけるノード１の構成について説明する。実施例３におけるノード１の構成は、図３に示した実施例１の構成と同じであるが、実施例３におけるノード１の不通リンク決定部１３が、実施例１の不通リンク決定部１３とは異なる処理を行う点で相違する。通信部１１、プローブパケット処理部１２、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の説明については省略する。
【００８０】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、ＯＳＰＦに用いるメッセージを、通信部１１を介して受信し、受信したメッセージを分析し、分析結果として、相手ノード２〜４までの間のルータ台数またはコストを算出する。ネットワーク経路情報取得手段１３１は、ルータ台数またはコストをネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００８１】
ＯＳＰＦは、小規模のＩＰネットワークを構成するルータ間において、経路制御のためのメッセージを交換する経路制御プロトコルである。ＯＳＰＦでは、各ルータにユニークな番号（ルータＩＤ）が付与されている。各ルータは、自らのインターフェースに付与されたネットワークアドレス、コスト情報及び自らのルータＩＤを含む広告メッセージ（ＬＳＡ：Ｌｉｎｋ Ｓｔａｔｅ Ａｄｖｅｒｔｉｓｅｍｅｎｔ）を、全てのネットワークインターフェースから同報送信する。また、ＬＳＡを受信したルータは、ＬＳＡを受信したネットワークインターフェースを除いた全てのネットワークインターフェースから、受信したＬＳＡを再び同報送信する。各ルータは、他のルータが同報送信したＬＳＡを受信することにより、ネットワーク上に存在するルータの配置、ルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報（例えば回線速度）を取得し、これらを反映したルータマップ情報を生成し、生成されたルータマップ情報に基づき実際のパケット転送経路を決定している。
【００８２】
図８は、ＯＳＰＦのＬＳＡに基づいて生成されたルータマップ情報例を示す図である。ルータマップ情報から、例えば、ネットワーク１７２．１６．１０．０／２４からネットワーク１７２．１６．３０．０／２４に至る経路にはルータ１→３（ＩＤ１→ＩＤ３）を経由する経路（そのコストはコスト１−３）とルータ１→２→３（ＩＤ１→ＩＤ２→ＩＤ３）を経由する経路（そのコストはコスト１−２とコスト２−３の和）との二つの経路が存在すること、がわかる。ノードのＩＰアドレスが既知なのでノードを内包するネットワークアドレスもわかるから、ルータマップ情報から２台のノードの間にあるルータの台数及びコストを知ることができる。尚、ＯＳＰＦの詳細については「Ｒ．Ｈａｌｈｏｔｒａ著、清水奨訳、入門ＩＰルーティング、オライリージャパン、２００２／８」の第６章を参照されたい。
【００８３】
ノード１における不通リンク決定部１３のネットワーク経路情報取得手段１３１は、通信部１１を介して、ルータが同報送信するＬＳＡを受信することにより、ルータの配置、ネットワークアドレス及びコスト情報を取得し、ＯＳＰＦ対応ルータと同等のルータマップ情報を生成することができる。この場合、ＯＳＰＦ対応ルータに、生成したルータマップ情報をノードへ送信する機能を持たせることにより、ノード１のネットワーク経路情報取得手段１３１がルータマップ情報を取得してもよい。
【００８４】
このルータマップ情報は、図７に示した実施例２のＡＳマップに対応し、実施例３のルータは実施例２のＡＳに対応する。つまり、実施例３のネットワーク経路情報取得手段１３１は、実施例２のネットワーク経路情報取得手段１３１と同様の処理を行う。
【００８５】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４との間のルータ台数及びコスト）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００８６】
例えば、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるルータ台数と所定のしきい値とを比較し、ルータ台数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。また、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるコストである回線の速度と所定のしきい値とを比較し、回線の速度が所定のしきい値よりも小さいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。尚、不通リンク決定手段１３２は、他のリンクのルータ台数またはコストも含めて平均的なルータ台数またはコストを算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ルータ台数またはコストのばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００８７】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、最適パスを決定するための処理負荷を軽減することができる。
【００８８】
以上のように、実施例３のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ＯＳＰＦに用いるＬＳＡに基づいて、ルータの配置、ルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得してルータマップ情報を生成し、または、ルータからルータマップ情報を取得してそのルータマップ情報を分析することにより、自ノード１と相手ノード２〜４との間のルータ台数またはコストを示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ルータ台数の多いリンクまたはコストの高い（回線速度の遅い）リンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンクから不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００８９】
これにより、実施例１，２と同様に、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの付加を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワークにおいて、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【００９０】
尚、実施例３においても、実施例２にて説明した他の手法を用いることができる。ノード１の不通リンク決定部１３における不通リンク決定手段１３２は、実施例２の他の手法と同様に、ルータマップ情報に基づいて、同一または類似した経路を通る候補リンクが複数存在することを判定した場合、複数の候補リンクのうちの一部のリンクを不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、不通リンク決定手段１３２は、実施例２の他の手法と同様に、ルータマップ情報に基づいて、経路を共通しないパスの構成リンクだけを候補リンクとし、それ以外のリンクを伝送性能が劣ると判断して不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、伝送アプリケーションに対し、例えば、ノード１→３とノード１→２→３の両パスを最適パスとして提示し、伝送アプリケーションには同時に両パスを使って伝送させることにより、両パスの利用可能帯域を合わせて伝送性能を向上させることができる。
【００９１】
前述の実施例１〜３では、メッシュ型ネットワーク１００の全ノード１〜４が、不通リンクを除外した候補リンクの利用可能帯域を計測し、結果パケットに格納して他のノード１〜４へ送信することにより、その計測結果をお互いに交換し、それぞれ最適パスを決定するようにした。これに対し、全てのノード１〜４がそれぞれ最適パスを決定するのではなく、所定の１台の経路計算ノードに、最適パスを決定させるようにしてもよい。例えば、各ノード１〜４は、隣接リンクの利用可能帯域を計測し、その計測結果を結果パケットに格納し、経路計算ノードへ送信する。経路計算ノードは、結果パケットを受信し、実施例１〜３の不通リンク決定部１３と同様の処理を行って不通リンクを決定し、最適パス決定部１６と同様の処理を行って最適パスを決定する。各ノード１〜４は、経路計算ノードに対し、不通リンク及び最適パスの問い合わせを行う。
【実施例４】
【００９２】
次に、実施例４について説明する。実施例４は、前述のとおり、実施例１〜３のいずれかの例に加え、隣接リンクの利用可能帯域をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。
【００９３】
図９は、実施例４のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、相互に接続された複数のノード２１〜２４等により、網目状に構成されている。実施例５も同様である。
【００９４】
〔ノードの処理概要／実施例４〕
図１０は、図９に示したノード２１の処理概要を示すフローチャートである。ノード２２〜２４もノード２１と同じ処理を行う。実施例５も同様である。
【００９５】
ノード２１は、ノード２２〜２４からプローブパケットをそれぞれ受信した場合（ステップＳ９１：Ｙ）、隣接リンクの利用可能帯域（帯域２−１，３−１，４−１）をそれぞれ計測する（ステップＳ９０１）。利用可能帯域を計測した隣接リンクが候補リンクとなる。
【００９６】
ノード２１は、不通リンクの更新タイミングを判定すると（ステップＳ９２：Ｙ）、実施例１〜３のうちのいずれかにより、ネットワーク経路情報を取得する（ステップＳ９０２）。更新タイミングは、例えば所定の時間間隔とする。そして、ノード２１は、ネットワーク経路情報に基づいて不通リンクを決定し（ステップＳ９０３）、不通リンクを候補リンク（リンク２−１，３−１，４−１）から除外する（ステップＳ９０４）。図９の例は、不通リンクが存在しない場合を示している。
【００９７】
ノード２１は、プローブパケットの送信タイミングを判定すると（ステップＳ９３：Ｙ）、ノード２２〜２４において利用可能帯域を計測するためのプローブパケットに、不通リンクを除外した候補リンクの利用可能帯域をプローブパケットに格納し（ステップＳ９０５）、このプローブパケットをノード２２〜２４へ送信する（ステップＳ９０６）。送信タイミングは、例えば所定の時間間隔とする。
【００９８】
ノード２１は、最適パスを決定するタイミングを判定すると（ステップＳ９４：Ｙ）、自ノード２１において不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２２〜２４において不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定する（ステップＳ９０７）。
【００９９】
〔ノードの構成／実施例４〕
次に、図９に示したノード２１の構成について説明する。図１１は、ノード２１の構成を示すブロック図である。このノード２１は、通信部１１、プローブパケット処理部３１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７を備えている。図１１において、図３に示したノード１の構成と共通する部分には図３と同一の符号を付し、その詳しい説明は省略する。図３に示したノード１とこのノード２１とを比較すると、ノード１，２１は、通信部１１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７を備えている点で同一であるが、ノード２１は、結果パケット処理部１５を備えておらず、ノード１のプローブパケット処理部１２とは異なるプローブパケット処理部３１を備えている点で相違する。
【０１００】
プローブパケット処理部３１は、プローブパケットの送信タイミングにおいて、ノード２２〜２４において利用可能帯域を計測するためのプローブパケットを生成すると共に、記憶部１７から自ノード帯域情報（自ノード２１における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、この自ノード帯域情報をプローブパケットに格納し、このプローブパケットを、通信部１１を介してノード２２〜２４へ送信する。また、プローブパケット処理部３１は、ノード２２〜２４から通信部１１を介して、プローブパケットを受信し、プローブパケットの受信間隔を算出し、受信間隔等の情報をプローブパケット受信情報として帯域計測部１４に出力する。そして、受信したプローブパケットから、他ノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域を取得し、他ノード帯域情報として記憶部１７に格納する。また、プローブパケット処理部３１は、不通リンク決定部１３から不通リンク情報を入力し、不通リンクの相手ノードに対するプローブパケットの送信を停止する。
【０１０１】
以上のように、実施例４のノード２１によれば、プローブパケット処理部３１が、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域を格納したプローブパケットを送信し、他ノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域が格納されたプローブパケットを受信するようにした。
【０１０２】
これにより、隣接リンクの利用可能帯域を計測するためのプローブパケットと、不通リンクを除外した候補リンクの利用可能帯域を含む結果パケットとを別々に送受信することなく、帯域計測を行い、かつ計測結果を交換するためのプローブパケットのみを送受信する。したがって、帯域計測及び計測結果交換を同時に行いながら、ネットワークへのパケット送出総量を削減することができる。したがって、実施例１の効果に加え、前記課題（２）を解決することができる。
【０１０３】
尚、ノード２１のプローブパケット処理部３１は、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域（具体的には、リンクの識別子（例えば、事前に各リンクに付与したユニークな識別子、リンクの両端のノードのＩＰアドレスを組にした識別子）及びそのリンクの利用可能帯域の計測結果）をプローブパケットに格納するようにしたが、その格納形式は限定されない。
【実施例５】
【０１０４】
次に、実施例５について説明する。実施例５は、前述のとおり、実施例４の拡張例であり、隣接リンクの利用可能帯域の属性をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。
【０１０５】
〔ノードの処理概要／実施例５〕
実施例５のノードを含むメッシュ型ネットワークの構成は、図９に示した構成と同様である。また、実施例５のノード２１は、図１０に示した実施例４の処理、すなわち、ステップＳ９１〜ステップＳ９４及びステップＳ９０１〜ステップＳ９０７の処理に加え、ステップＳ９０５とステップＳ９０６との間に、隣接リンクの利用可能帯域の属性を生成し、この属性をプローブパケットに格納する処理を行う。ステップＳ９１〜ステップＳ９４及びステップＳ９０１〜ステップＳ９０７の説明については省略する。
【０１０６】
〔ノードの構成／実施例５〕
次に、実施例５におけるノード２１の構成について説明する。実施例５におけるノード２１の構成は、図１１に示した実施例４の構成と同じであるが、実施例５におけるノード２１のプローブパケット処理部３１及び最適パス決定部１６が、実施例４のプローブパケット処理部３１及び最適パス決定部１６とは異なる処理を行う点で相違する。通信部１１、不通リンク決定部１３、帯域計測部１４及び記憶部１７の説明については省略する。
【０１０７】
プローブパケット処理部３１は、実施例４に示した処理に加え、記憶部１７から自ノード帯域情報を読み出し、利用可能帯域を計測する計測結果である自ノード帯域情報に対し、読み出す毎に統計処理し、計測結果の信頼性（例えば、しきい値と比較することにより得られる、計測結果のばらつきが大きいか小さいかを示す情報）または安定性（例えば、しきい値と比較することにより得られる、計測結果が長期的にほぼ同一の値を示しているかを示す情報）を属性として生成する。そして、プローブパケット処理部３１は、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域に加え、生成した属性をプローブパケットに格納し、ノード２２〜２４へ送信する。また、プローブパケット処理部３１は、ノード２２〜２４により送信されたプローブパケットを受信し、このプローブパケットから属性を取得し、最適パス決定部１６に出力する。
【０１０８】
最適パス決定部１６は、記憶部１７から自ノード帯域情報及び他ノード帯域情報（ノード２１における不通リンクを除外した候補リンクの利用可能帯域、及びノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、プローブパケット処理部３１から属性（計測結果の信頼性または安定性）を入力し、不通リンクを除外した候補リンクの利用可能帯域及び属性に基づいて、最適パスを決定する。すなわち、信頼性または安定性が高いリンクを優先的に扱い、最適パスを決定する。例えば、同じ利用可能帯域のリンクが複数存在する場合、信頼性または安定性が高い方のリンクを、最適パスのリンクとなるように扱う。
【０１０９】
尚、属性には、計測結果が得られた時刻（計測時刻）を含むようにしてもよい。この場合、最適パス決定部１６は、計測時刻が新しいリンクを優先的に扱い、最適パスを決定する。例えば、同じ利用可能帯域のリンクが複数存在する場合、計測時刻が新しい方のリンクを、最適パスのリンクとなるように扱う。また、属性には、伝送遅延等の情報を含むようにしてもよく、これらの情報は、最適パスの決定の際に用いられる。
【０１１０】
図１２は、実施例４，５におけるプローブパケットの構成例を示す図である。図１３に示したように、従来のプローブパケットは、先頭のヘッダ部分を除いて、ダミーデータにて構成されている。これに対し、図１２に示す実施例４，５におけるプローブパケットは、従来のプローブパケットと同じヘッダと、当該プローブパケットを送信するノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、帯域計測結果である利用可能帯域、及び属性を含むペイロードとにより構成される。残りのペイロード部にはダミーデータが格納される。図１２では、１つの隣接リンク毎に、リンクの識別子としてのリンクの相手ノードのＩＰアドレス（ＩＰヘッダのＳｏｕｒｃｅ Ａｄｄｒｅｓｓと併せてリンクを一意に識別可能なＩＰアドレス）、リンクの帯域計測結果である利用可能帯域、及びリンクの属性を組としている。ここではリンクの帯域計測結果である利用可能帯域、リンクの属性のデータ長は８バイトとした。尚、隣接リンクの数が少ない場合は、残りの部分にダミーデータが格納され、隣接リンクの数が多い場合は、ペイロード部の情報が複数のプローブパケットに分けて格納される。尚、実施例４では、図１２に示したプローブパケットのペイロード部に、ノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、及び帯域計測結果である利用可能帯域が格納され、実施例５では、ノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、帯域計測結果である利用可能帯域、及び属性が格納される。
【０１１１】
以上のように、実施例５のノード２１によれば、プローブパケット処理部３１が、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域に加えて、その属性（例えば、計測した利用可能帯域の信頼性または安定性を数値化した情報）もプローブパケットに格納して送信し、他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域及び属性が格納されたプローブパケットを受信するようにした。そして、最適パス決定部１６が、属性を参照して最適パスを決定するようにした。
【０１１２】
これにより、リンクの信頼性または安定性の高いリンクを有するパスが最適パスに決定される可能性が高くなる。したがって、実施例４の効果に加え、決定される最適パスの精度が高くなる。
【０１１３】
以上、実施例１〜５を挙げて本発明を説明したが、本発明は前記実施例１〜５に限定されるものではなく、その技術思想を逸脱しない範囲で種々変形可能である。例えば、前記実施例１〜５では、メッシュ型ネットワーク１００を前提として説明したが、メッシュ型ネットワーク１００には、オーバーレイ技術による論理ネットワークも含まれる。また、前記実施例１〜５では、パケットペア法を用いて利用可能帯域を計測することを想定して説明したが、本発明は、プローブパケットを用いる計測手法一般に適用可能であり、計測手法を限定するものではない。
【０１１４】
尚、本発明の実施例１〜５によるノード１〜４，２１〜２４のハード構成としては、通常のコンピュータを使用することができる。ノード１〜４，２１〜２４は、ＣＰＵ、ＲＡＭ等の揮発性の記憶媒体、ＲＯＭ等の不揮発性の記憶媒体、及びインターフェース等を備えたコンピュータによって構成される。実施例１〜３のノード１〜４に備えた通信部１１、プローブパケット処理部１２、不通リンク決定部１３、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の各機能は、これらの機能を記述したプログラムをＣＰＵに実行させることによりそれぞれ実現される。また、実施例４，５のノード２１〜２４に備えた通信部１１、プローブパケット処理部３１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７の各機能も、これらの機能を記述したプログラムをＣＰＵに実行させることによりそれぞれ実現される。これらのプログラムは、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリ等の記憶媒体に格納して頒布することもできる。
【符号の説明】
【０１１５】
１〜４，２１〜２４，１０１〜１０４ ノード
１１ 通信部
１２ プローブパケット処理部
１３ 不通リンク決定部
１４ 帯域計測部
１５ 結果パケット処理部
１６ 最適パス決定部
１７ 記憶部
３１ プローブパケット処理部
１００ メッシュ型ネットワーク
１３１ ネットワーク経路情報取得手段
１３２ 不通リンク決定手段
【技術分野】
【０００１】
メッシュ型ネットワークにおいて、ノード間のリンクの利用可能帯域を計測し、この計測結果から最適な伝送パス（最適パス）を動的に決定するノード装置、最適パス決定方法及びプログラムに関する。
【背景技術】
【０００２】
メッシュ型ネットワークは、３つ以上のノードがそれぞれ相互に接続され、網目状に構成された伝送路をいう。メッシュ型ネットワークでは、２つのノード間の伝送経路は、その２つのノードを直接繋ぐ最短パスの経路だけではなく、他のノードを経由して繋ぐ迂回パスの経路も存在する。このため、２つのノード間の伝送経路に障害が発生した場合であっても、他のノードを経由する迂回パスによって、伝送を継続することができる。このメッシュ型ネットワークにおいては、ノード間のリンクが局所的に混雑することによって、最短パスよりも迂回パスの利用可能帯域の方が広くなる場合がある。
【０００３】
以下、「リンク」は、２つの（オーバーレイ）ノードを直接結ぶ経路をいい、「パス」は、２つの（オーバーレイ）ノードを結ぶ経路一般（途中に他のノードを経由する経路を含む）をいう。また、事業者により素材映像伝送を実現するメッシュ型ネットワークのシステムにおいて、メッシュ型ネットワークを構成するノードは、全て管理者によって管理されており（アドレスが既知であり）、ノードが頻繁に参加または離脱することはないものとする。
【０００４】
従来、ネットワークにおけるノード間の最適パスを決定する手法が知られている（例えば、特許文献１を参照）。この特許文献１の手法は、ネットワーク全体の処理負荷の低減を考慮して、ノード間伝送路の負荷情報に基づいてノードのグルーピングを行い、受信するデータに基づいてトラフィック情報（利用可能帯域）を計測し、トラフィック情報に基づいて最適パスを決定するものである。
【０００５】
この利用可能帯域を計測する手法として、例えば、パケットペア法が知られている。図１４は、パケットペア法による利用可能帯域の計測手法について説明する図である。図１４を用いて、ノード１０１からノード１０２までの間のリンク１−２の帯域（利用可能帯域）１−２を計測する手法について簡単に説明する。ノード１０１からノード１０２までの間のリンクに、帯域Ｗのボトルネックが存在するものとする。起点のノード１０１は、充分に短い時間間隔Ｔで、パケット長Ｌのプローブパケットを連続的に終点のノード１０２へ送信する。リンク１−２におけるいずれかのパス上で他のトラフィックの影響を受けない場合には、終点のノード１０２は、ノード１０１から送信されたプローブパケットを、時間間隔Ｔ’＝Ｌ／Ｗで受信する。したがって、ノード１０２は、受信するプローブパケットの時間間隔を算出することにより、ボトルネックの帯域（利用可能帯域）Ｗを計測することができる。実際には、計測を繰り返した結果を統計的に処理することにより、他のトラフィックの影響を排除した利用可能帯域が推定される。
【０００６】
図１３は、図１４に示したパケットペア法に用いるプローブパケットの構成を示す図である。図１３に示すように、プローブパケットは、Ｖｅｒｓｉｏｎ（バージョン）、Ｈｅａｄｅｒ Ｌｅｎｇｔｈ（ヘッダ長）等のヘッダと、ダミーデータが格納されたペイロードとにより構成される。パケットペア法においては、プローブパケット長が長い場合は計測精度が向上するから、プローブパケット長を、ＩＰネットワークのＭＴＵ（Ｍａｘｉｍｕｍ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｕｎｉｔ：最大転送単位）として一般的な１５００バイトに固定することが多い。このため、プローブパケットは、先頭のＩＰヘッダ部分を除いて、ダミーデータにより構成される。
【０００７】
図１５は、従来のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、相互に接続された複数のノード１０１〜１０４等により、網目状に構成されている。ノード１０１は、プローブパケットをノード１０２〜１０４へ送信し、ノード１０２〜１０４もプローブパケットを他のノード１０１〜１０４へ送信する。ノード１０１は、プローブパケットをノード１０２〜１０４からそれぞれ受信すると、隣接リンクの利用可能帯域（ノード１０２からノード１０１までの間のリンク２−１の帯域２−１、ノード１０３からノード１０１までの間のリンク３−１の帯域３−１、ノード１０４からノード１０１までの間のリンク４−１の帯域４−１）を、前述のパケットペア法によりそれぞれ計測し、結果パケットに格納してノード１０２〜１０４へ送信する。ノード１０２〜１０４も、プローブパケットを受信すると、隣接リンクの利用可能帯域をそれぞれ計測し、結果パケットに格納して他のノード１０１〜１０４へ送信する。
【０００８】
そして、ノード１０１〜１０４は、他のノード１０１〜１０４において計測された隣接リンクの利用可能帯域が格納された結果パケットを受信し、全てのリンクの利用可能帯域を取得する。そして、取得した全リンクの利用可能帯域に基づいて最適パスを決定する。図１５に示すように、ノード１０３は、全リンクの利用可能帯域に基づいて、ノード１０１からノード１０３までの間の最適パスを決定する際に、ノード１０１からノード１０３までの間のパスを構成するリンクの組み合わせを求め、その組み合わせ毎にリンクの帯域の最小値が最も大きいリンクの組み合わせを最適パスとして決定する。例えば、パスを構成するリンクの組み合わせとしてリンク１−３、リンク１−２，２−３、リンク１−４，４−３、リンク１−４，４−２，２−３、及びリンク１−２，２−４，４−３が存在し、それぞれのリンクの帯域が、（帯域１−２＜帯域２−３、帯域２−４、帯域４−３）、（帯域１−４＜帯域２−３、帯域４−２、帯域４−３）、（帯域１−２＜帯域１−４＜帯域１−３）の関係にある場合、リンク１−３を最適パスとして決定する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−１５３９７８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、図１５に示した従来のノード１０１〜１０４を含むメッシュ型ネットワーク１００では、以下の問題があった（課題（１）（２））。
【００１１】
〔課題（１）〕
従来のメッシュ型ネットワーク１００では、ノードがｎ台の場合、利用可能帯域を計測する計測対象となるリンク（以下、候補リンクという。）の総数がｎ（ｎ−１）であり、ｎの増加に従って、ｎ２のオーダーで増大する。候補リンク数の増加は、プローブパケットの送出量と計測結果を交換する結果パケットの送出量の増大につながり、メッシュ型ネットワーク１００への負荷を増加させる。また、候補リンクが多数存在すると、候補リンクから最適パスを決定する処理（例えば、総当たり法による全リンクの利用可能帯域の計算及び比較処理、並びにダイクストラ法による最適パスの決定処理）の計算量も増大する。
【００１２】
〔課題（２）／付加的な課題〕
また、従来のメッシュ型ネットワーク１００では、隣接リンクの利用可能帯域を計測する帯域計測が行われ、そして、計測結果を交換するために、それぞれ別のパケット（帯域計測のときはプローブパケット、計測結果を交換するときは結果パケット）が送受信されるため、メッシュ型ネットワーク１００へのデータ送信量が増大する。また、前述のとおり、プローブパケットは、計測精度の向上を図るために、ＭＴＵとほぼ等しい固定長に設定されることが多く、メッシュ型ネットワーク１００に与える負荷が大きいにも関わらず、そのペイロード部分はダミーデータのみで構成され、有効に使用されていない。
【００１３】
そこで、本発明は前記課題を解決するためになされたものであり、その目的は、メッシュ型ネットワークにおいて、ノード装置間の最適パスを決定するための処理負荷を軽減可能なノード装置、最適パス決定方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明者らは、上記目的を達成すべく鋭意検討を行った。その結果、各ノード装置において、メッシュ型ネットワークの経路情報を分析し、分析結果（例えば、ｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムの実行により得られるＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ：ラウンドトリップ時間）または経由ルータ台数、ＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）またはＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）等の経路制御プロトコルにて送受信されるメッセージの分析により得られる経由ＡＳ数／経由ルータ台数またはコスト）に基づいて、伝送性能が劣ると予想される候補リンクを計測対象から除外し、最適パスの決定に際してその候補リンクを不通リンクとして扱う、いわゆる候補リンクの足切りを行うことを見出した。
【００１５】
これにより、伝送性能が劣ると予想される候補リンクは、最適パスに含まれるリンクにはなり得ないから、利用可能帯域の計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができる。
【００１６】
また、本発明者らは、各ノード装置において、計測した隣接リンクの利用可能帯域を、帯域計測に用いるプローブパケットに格納して送信することを見出した。
【００１７】
これにより、各ノード装置は、プローブパケットとは別に、計測結果の利用可能帯域を送信する必要がなく、帯域計測と計測結果の交換とをプローブパケットによって同時に実現することができる。最適パスを決定するノード装置は、他のノード装置から送られてくるプローブパケットを受信することにより、隣接リンクの利用可能帯域を計測することができ、同時に、プローブパケットに格納された利用可能帯域を取得することができる。つまり、プローブパケットを受信し、自ノード装置における隣接リンクの利用可能帯域の計測と、他のノード装置における隣接リンクの利用可能帯域の取得とを同時に行うことにより、メッシュ型ネットワークにおいて送受信されるパケットの量を減らし、ネットワーク負荷を一層低減することができる。したがって、前記課題（２）を解決することができる。
【００１８】
すなわち、本発明によるノード装置は、複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定するノード装置において、当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するネットワーク経路情報取得手段、及び、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断し、前記リンクを不通リンクとして決定する不通リンク決定手段を有する不通リンク決定部と、当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測する帯域計測部と、前記帯域計測部により計測された、前記不通リンクを除外した候補リンクの利用可能帯域を結果パケットに格納し、他のノード装置へ送信し、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得する結果パケット処理部と、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、前記結果パケット処理部により取得された他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定する最適パス決定部と、を備えたことを特徴とする。
【００１９】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークを管理するために用いるｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムを実行し、この実行結果に基づいて、当該ノード装置と他のノード装置との間のルータ台数またはＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２０】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークの経路を制御するためのＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）に用いるＢＧＰメッセージのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、他のノード装置を内包するＡＳを始点として送信され、当該ノード装置を内包するＡＳへ送信されたＢＧＰメッセージを選定し、前記選定したＢＧＰメッセージのＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号から、当該ノードと他のノードとの間のＡＳ数をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２１】
また、本発明によるノード装置は、前記不通リンク決定部のネットワーク経路情報取得手段が、ネットワークの経路を制御するためのＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）に用いる広告メッセージに基づいて、当該メッセージが送信されたルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得し、前記ネットワークアドレス及びコスト情報から、当該ノード装置と他のノード装置との間のルータ台数またはコスト情報をネットワーク経路情報として取得し、前記不通リンク決定手段が、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とする。
【００２２】
また、本発明によるノード装置は、前記結果パケット処理部の代わりにプローブパケット処理部を備え、前記プローブパケット処理部が、当該ノード装置における隣接リンクの利用可能帯域を計測するためのプローブパケットを他のノード装置から受信し、他のノード装置において隣接リンクの利用可能帯域を計測させるためのプローブパケットに、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を格納し、前記プローブパケットを他のノード装置へ送信することを特徴とする。
【００２３】
さらに、本発明による最適パス決定方法は、複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定する方法において、当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するステップと、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断するステップと、前記伝送性能が劣ると判断したリンクを不通リンクとして決定するステップと、当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測するステップと、前記計測した、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を、結果パケットに格納し、他のノード装置へ送信するステップと、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得するステップと、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定するステップと、を有することを特徴とする。
【００２４】
また、本発明による最適パス決定プログラムは、コンピュータを、前記ノード装置として機能させることを特徴とする。
【発明の効果】
【００２５】
以上のように、本発明によれば、メッシュ型ネットワークにおいて、ノード装置間の最適パスを決定するための処理負荷を軽減することが可能となる。
【図面の簡単な説明】
【００２６】
【図１】実施例１のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【図２】実施例１におけるノードの処理概要を示すフローチャートである。
【図３】実施例１におけるノードの構成を示すブロック図である。
【図４】ｐｉｎｇプログラムの実行結果例を示す図である。
【図５】ｔｒａｃｅｒｏｕｔｅプログラムの実行結果例を示す図である。
【図６】ＢＧＰメッセージの例を示す図である。
【図７】ＢＧＰメッセージに基づいて作成された経路マップ（ＡＳマップ）例を示す図である。
【図８】ＯＳＰＦのＬＳＡに基づいて作成されたルータマップ情報例を示す図である。
【図９】実施例４のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【図１０】実施例４におけるノードの処理概要を示すフローチャートである。
【図１１】実施例４におけるノードの構成を示すブロック図である。
【図１２】実施例４，５におけるプローブパケットの構成例を示す図である。
【図１３】従来のプローブパケットの構成を示す図である。
【図１４】パケットペア法による利用可能帯域の計測手法について説明する図である。
【図１５】従来のノードを含むメッシュ型ネットワークの構成を示す概略図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための形態について、図面を参照して説明する。本発明は、メッシュ型ネットワークにおいて、ノード（ノード装置）間の最適パスを決定する際の候補リンクを削減することを特徴とする。実施例１は、ＩＰネットワーク管理用のｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムの実行結果を用いてネットワーク経路情報を取得し、候補リンクを削減する例である。実施例２は、経路制御用のＢＧＰに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例３は、経路制御用のＯＳＰＦに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例４は、実施例１〜３のいずれかの例に加え、隣接リンクの利用可能帯域をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。実施例５は、実施例４の拡張例であり、隣接リンクの利用可能帯域の属性もプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。実施例１〜３により、前記課題（１）を解決することができる。また、実施例４，５により、前記課題（１）に加え、課題（２）を解決することができる。ここで、ネットワーク経路情報は、経路の伝送性能を判定する際に用いる情報である。
【実施例１】
【００２８】
まず、実施例１について説明する。実施例１は、前述のとおり、ＩＰネットワーク管理用のｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムの実行結果を用いてネットワーク経路情報を取得し、候補リンクを削減する例である。実施例１は、ＩＰネットワーク上でオーバーレイ伝送網を構築する場合に適用がある。
【００２９】
図１は、実施例１のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、例えばインターネットであり、相互に接続された複数のノード１〜４等により、網目状に構成されている。後述する実施例２，３においても同様である。
【００３０】
〔ノードの処理概要／実施例１〕
図２は、図１に示したノード１の処理概要を示すフローチャートである。ノード２〜４もノード１と同じ処理を行う。この処理は、例えば、ノード１〜４間で映像データを送受信する際に、利用可能帯域を計測し、最適パスを決定し、決定した最適パスにて映像データを送受信するものである。後述する実施例２，３においても同様である。
【００３１】
ノード１は、プローブパケットの送信タイミングを判定すると（ステップＳ２１：Ｙ）、ノード２〜４において利用可能帯域を計測するためのプローブパケットをノード２〜４へ送信する（ステップＳ２０１）。送信タイミングは、例えば所定の時間間隔であり、プローブパケットは、メッシュ型ネットワーク１００の状態変化に対応するために、定期的に送信される。
【００３２】
ノード１は、ノード２〜４からプローブパケットをそれぞれ受信した場合（ステップＳ２２：Ｙ）、図１４に示したように、プローブパケットの受信間隔を算出することにより、隣接リンクの利用可能帯域（ノード２からノード１までの間のリンク２−１の帯域２−１、ノード３からノード１までの間のリンク３−１の帯域３−１、ノード４からノード１までの間のリンク４−１の帯域４−１）をそれぞれ計測する（ステップＳ２０２）。利用可能帯域を計測した隣接リンクが候補リンクとなる。この場合、ノード１は、ノード２〜４から送信されるプローブパケットを定期的に受信する。
【００３３】
ノード１は、不通リンクの更新タイミングを判定すると（ステップＳ２３：Ｙ）、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを実行し、実行結果から、自ノード１と相手ノード２〜４との間のルータ台数及び自ノード１から相手ノード２〜４までのＲＴＴを示すネットワーク経路情報を取得する（ステップＳ２０３）。更新タイミングは、例えば所定の時間間隔とする。そして、ノード１は、ネットワーク経路情報に基づいて不通リンクを決定し（ステップＳ２０４）、候補リンク（リンク２−１，３−１，４−１）から不通リンクを除外する（ステップＳ２０５）。図１に示すように、例えば、ノード１は、ネットワーク経路情報に基づいて、リンク２−１が不通リンクであると決定し、候補リンクから不通リンク２−１を除外する。
【００３４】
ノード１は、結果パケットの送信タイミングを判定すると（ステップＳ２４：Ｙ）、前述の例では、不通リンク２−１を除外した候補リンク３−１，４−１の利用可能帯域（帯域３−１，４−１）を結果パケットに格納し、結果パケットをノード２〜４へ送信する（ステップＳ２０６）。送信タイミングは、例えば所定の時間間隔とする。これにより、ノード２〜４は、結果パケットを受信し、結果パケットから、ノード１における不通リンクを除外した候補リンクの利用可能帯域を取得することができる。
【００３５】
ノード１は、結果パケットをノード２〜４からそれぞれ受信した場合（ステップＳ２５：Ｙ）、受信した結果パケットから、他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を取得する（ステップＳ２０７）。
【００３６】
ノード１は、最適パスを決定するタイミングを判定すると（ステップＳ２６：Ｙ）、自ノード１において不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４において不通リンクを除外した候補リンクの利用可能帯域に基づいて、例えば前述した手法により、最適パスを決定する（ステップＳ２０８）。
【００３７】
図１に示すように、ノード２は、リンク１−２が不通リンクであると決定し、ノード４は、リンク３−４が不通リンクであると決定する。この場合、例えばノード３は、ノード１，２，４から、不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、不通リンクを除外した候補リンクの利用可能帯域を取得する。そして、ノード３は、全リンクのうちの不通リンク２−１，１−２，１−４，２−４，３−４を除外した候補リンク１−３，２−３，４−３，３−１，４−１，４−２，３−２に基づいて、最適パスを決定する。
【００３８】
〔ノードの構成／実施例１〕
次に、図１に示したノード１の構成について説明する。図３は、ノード１の構成を示すブロック図である。このノード１は、通信部１１、プローブパケット処理部１２、不通リンク決定部１３、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７を備えている。
【００３９】
ノード１の通信部１１は、メッシュ型ネットワーク１００に対してプローブパケット及び結果パケットの送受信を行う。また、後述するｐｉｎｇプログラム及びｔｒａｃｅｒｏｕｔｅプログラムの実行に伴って、各種メッセージの送受信を行う。
【００４０】
プローブパケット処理部１２は、プローブパケットの送信タイミングにおいて、ノード２〜４において利用可能帯域を計測するためのプローブパケットを生成し、このプローブパケットを、通信部１１を介してノード２〜４へ送信する。また、プローブパケット処理部１２は、ノード２〜４から通信部１１を介して、プローブパケットを受信し、プローブパケットの受信間隔を算出し、受信間隔等の情報をプローブパケット受信情報として帯域計測部１４に出力する。また、プローブパケット処理部１２は、不通リンク決定部１３から不通リンク情報を入力し、不通リンクの相手ノードに対するプローブパケットの送信を停止する。尚、プローブパケット処理部１２は、後述する記憶部１７から、不通リンクを除外した候補リンクの利用可能帯域である自ノード帯域情報を読み出し、この自ノード帯域情報に基づいて不通リンクを特定し、不通リンクの相手ノードに対するプローブパケットの送信を停止するようにしてもよい。この場合、不通リンクの利用可能帯域にはデータが格納されていない。
【００４１】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、メモリ（図示せず）からｐｉｎｇプログラムを読み出して実行し、通信部１１を介してメッセージの送受信を行い、プログラム実行結果として、相手ノード２〜４までの間に存在するルータの台数及び相手ノード２〜４までのＲＴＴを取得する。または、ネットワーク経路情報取得手段１３１は、メモリからｔｒａｃｅｒｏｕｔｅプログラムを読み出して実行し、通信部１１を介してメッセージの送受信を行い、プログラム実行結果として、相手ノード２〜４までの間に存在するルータのＩＰアドレス及びルータ（相手ノード２〜４を含む）までのＲＴＴを取得し、ルータのＩＰアドレスの数からルータ台数を算出し、相手ノード２〜４までのＲＴＴを取得する。ネットワーク経路情報取得手段１３１は、ルータ台数及びＲＴＴをネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００４２】
ｐｉｎｇプログラムは、ＩＰネットワークの管理のために一般的に用いられ、インターネット、イントラネット等のＴＣＰ／ＩＰネットワークを診断するプログラムである。相手ノードのＩＰアドレスを指定することにより、ＩＣＭＰ（Ｉｎｔｅｒｎｅｔ Ｃｏｎｔｒｏｌ Ｍｅｓｓａｇｅ Ｐｒｏｔｏｃｏｌ）を使って所定量のデータを送信し、相手ノードから返信があるか否か、返信がある場合はその返信時間等によって、ネットワークを診断する。このプログラムにより、自ノードと相手ノードとの間のルータ台数及び自ノードから相手ノードまでのＲＴＴを取得することができる。ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレスを指定してｐｉｎｇプログラムを実行し、実行結果として、ルータ台数及びＲＴＴを取得する。
【００４３】
図４は、ｐｉｎｇプログラムの実行結果例を示す図である。（尚、図４では実際には使われていないＩＰアドレスを記載している。）図４に示すように、ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレス「１９２．１６８．０．１」を指定してｐｉｎｇプログラムを実行した結果、１回目のシーケンス（ｉｃｍｐ＿ｓｅｑ＝０）の結果が、ルータ台数が１８（ｔｔｌ（ｔｉｍｅ ｔｏ ｌｉｖｅ）＝２３７であるから、２５５−２３７＝１８）、ＲＴＴが９．９５４ｍｓ（ｔｉｍｅ＝９．９５４ｍｓ）であり、２〜１１回目のシーケンスの結果を合わせて、ＲＴＴの最小値、平均値、最大値及び平均偏差値（７．３６９／８．７０７／・・・ｍｓ）を取得する。このように、ネットワーク経路情報取得手段１３１は、自ノードと相手ノードとの間のルータ台数（図４の場合、１７台）、及び自ノードから相手ノードまでのＲＴＴ（図４の場合、平均値８．７０７ｍｓ）を取得する。
【００４４】
一方、ｔｒａｃｅｒｏｕｔｅプログラムも、ＩＰネットワークの管理のために一般的に用いられ、目的のホストまでの経由ルータを一覧するためのプログラムである。このプログラムにより、自ノードと相手ノードとの間に存在するルータのＩＰアドレス及び自ノードから各ルータ（相手ノードを含む）までのＲＴＴを取得することができる。ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレスを指定してｔｒａｃｅｒｏｕｔｅプログラムを実行し、実行結果として、ルータのＩＰアドレス及び各ルータ（相手ノードを含む）までのＲＴＴを取得する。
【００４５】
図５は、ｔｒａｃｅｒｏｕｔｅプログラムの実行結果例を示す図である。（尚、図５では実際には使われていないＩＰアドレスを記載している。）図５に示すように、ネットワーク経路情報取得手段１３１は、相手ノードのＩＰアドレス「１９２．１６８．０．１」を指定してｔｒａｃｅｒｏｕｔｅプログラムを実行した結果、相手ノードとの間に存在する各ルータの番号（２〜１８）、各ルータのＩＰアドレス（１７２．３１．２５４．２５４，・・・）、各ルータ（相手ノードを含む）までのＲＴＴ（０．５０８ｍｓ，・・・，７．２８４ｍｓ）を取得する。図５において、左端の「２」から「１８」までの各行の情報が各ルータに関する情報であり、「１」の情報が自ノードに関する情報であり、「１９」の情報が相手ノードに関する情報である。このように、ネットワーク経路情報取得手段１３１は、自ノードと相手ノードとの間に存在するルータのＩＰアドレス（１７台のルータのＩＰアドレス１７２．３１．２５４．２５４，・・・）、及び自ノードから各ルータ（相手ノードを含む）までのＲＴＴ（０．５０８ｍｓ，・・・，７．２８４ｍｓ）を取得する。そして、ネットワーク経路情報取得手段１３１は、ルータのＩＰアドレスの数から、自ノードと相手ノードとの間のルータ台数（図５の場合、１７台）を算出し、相手ノードまでのＲＴＴ（例えば、「１９」の情報における７．６５７ｍｓ，７．４６３ｍｓ，７．２８４ｍｓの平均値）を算出する。
【００４６】
尚、ｐｉｎｇプログラム及びｔｒａｃｅｒｏｕｔｅプログラムにより取得されるルータ台数及びＲＴＴ等は、長期的に変化する。そこで、ネットワーク経路情報取得手段１３１は、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを、所定周期にて適宜繰り返して実行する。
【００４７】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４までの間のルータ台数、及び自ノード１から相手ノード２〜４までのＲＴＴ）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００４８】
例えば、不通リンク決定手段１３２は、相手ノードまでの間のルータ台数と所定のしきい値とを比較し、ルータ台数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。または、相手ノードまでのＲＴＴと所定のしきい値とを比較し、ＲＴＴが所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。これは、多数のルータを経由するリンク及びＲＴＴの大きいリンクは、利用可能帯域が狭く伝送性能が劣る傾向にあるからである。尚、不通リンク決定手段１３２は、他のリンクのルータ台数またはＲＴＴも含めて平均的なルータ台数またはＲＴＴを算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ルータ台数またはＲＴＴのばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００４９】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、ネットワークの負荷、及び最適パスを決定するための処理負荷を軽減することができる。
【００５０】
帯域計測部１４は、プローブパケット処理部１２からプローブパケット受信情報（ノード２〜４から送信されたプローブパケットの受信間隔等）を入力すると共に、不通リンク決定部１３から不通リンク情報を入力する。帯域計測部１４は、前述したとおり、プローブパケット受信情報における受信間隔等の情報に基づいて、ノード２〜４との間の隣接リンク（候補リンク２−１，３−１，４−１）の利用可能帯域を計測する。また、帯域計測部１４は、候補リンク２−１，３−１，４−１から不通リンクを除外し、不通リンクを除外した候補リンクの利用可能帯域を自ノード帯域情報として記憶部１７に格納する。尚、帯域計測部１４は、計測した隣接リンク（候補リンク）の利用可能帯域を記憶部１７に格納し、入力した不通リンク情報の示す不通リンクの利用可能帯域を記憶部１７から削除するようにしてもよい。
【００５１】
結果パケット処理部１５は、記憶部１７から自ノード帯域情報（自ノード１における不通リンクを除外した候補リンクの利用可能帯域）を読み出して結果パケットに格納し、この結果パケットを、通信部１１を介してノード２〜４へ送信する。また、結果パケット処理部１５は、ノード２〜４から通信部１１を介して、結果パケットを受信し、結果パケットから、ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を取得する。そして、結果パケット処理部１５は、ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域を他ノード帯域情報として記憶部１７に格納する。これにより、記憶部１７には、自ノード１における不通リンクを除外した候補リンクの利用可能帯域である自ノード帯域情報、及びノード２〜４における不通リンクを除外した候補リンクの利用可能帯域である他ノード帯域情報が格納される。
【００５２】
最適パス決定部１６は、記憶部１７から自ノード帯域情報及び他ノード帯域情報（自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及びノード２〜４における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、前述したとおり、最適パスを決定する。
【００５３】
以上のように、実施例１のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ｐｉｎｇプログラムまたはｔｒａｃｅｒｏｕｔｅプログラムを実行して、自ノード１から相手ノード２〜４までの間のルータ台数、及び自ノード１から相手ノード２〜４までのＲＴＴを示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ルータ台数の多いリンクまたはＲＴＴの大きいリンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンク２−１，３−１，４−１から不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００５４】
これにより、不通リンクを除外した候補リンクから最適パスが決定されるから、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワーク１００において、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【実施例２】
【００５５】
次に、実施例２について説明する。実施例２は、前述のとおり、経路制御用のＢＧＰに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例２は、インターネット上に配置したノード間でオーバーレイ伝送網を構築する場合に適用がある。
【００５６】
〔ノードの処理概要／実施例２〕
実施例２のノードを含むメッシュ型ネットワークの構成は、図１に示した構成と同様である。また、実施例２のノード１は、図２に示した実施例１のステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８と同じ処理を行い、ステップＳ２０３とは異なる処理を行う。ステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８の説明については省略する。
【００５７】
ノード１は、図２に示した実施例１のステップＳ２０３の代わりに、ＢＧＰに用いるメッセージを受信して分析し、分析結果から、自ノード１と相手ノード２〜４との間に存在するＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ：自律システム）の数を示すネットワーク経路情報を取得する（ステップＳ２０３）。
【００５８】
〔ノードの構成／実施例２〕
次に、実施例２におけるノード１の構成について説明する。実施例２におけるノード１の構成は、図３に示した実施例１の構成と同じであるが、実施例２におけるノード１の不通リンク決定部１３が、実施例１の不通リンク決定部１３とは異なる処理を行う点で相違する。通信部１１、プローブパケット処理部１２、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の説明については省略する。
【００５９】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、ＢＧＰに用いるメッセージを、通信部１１を介して受信し、受信したメッセージを分析し、分析結果として、相手ノード２〜４までの間のＡＳ数を取得する。ネットワーク経路情報取得手段１３１は、ＡＳ数をネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００６０】
ＢＧＰは、インターネットを構成するＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）ネットワーク間において、経路制御のためのメッセージをＢＧＰルータ間で交換する経路制御プロトコルである。ＢＧＰでは、各ＩＳＰネットワークをＡＳといい、それぞれのＡＳにユニークな番号（ＡＳ番号）が付与されている。各ＡＳのＢＧＰルータは、自ＡＳの内部に含むネットワークアドレスと自らのＡＳ番号とを含むＢＧＰメッセージを接続先ＡＳのＢＧＰルータへ送信する。接続先のＢＧＰルータは、このＢＧＰメッセージを受信すると、受信したＢＧＰメッセージの先頭に自らのＡＳ番号を追記し（これをＡＳ−ＰＡＴＨ属性という。）、他の接続先ＡＳのＢＧＰルータへ送信する。尚、ＢＧＰの詳細については「Ｒ．Ｈａｌｈｏｔｒａ著、清水奨訳、入門ＩＰルーティング、オライリージャパン、２００２／８」の第７章を参照されたい。
【００６１】
ここで、ノード１は、ＡＳ−ＰＡＴＨ属性を含むＢＧＰメッセージを、ノード１を内包するＡＳのＢＧＰルータから受信することにより、取得することができる。また、一般に、インターネット上に存在するオーバーレイ伝送網を構成するノードのＩＰアドレスが既知であれば、後述するプログラムにより、そのノードを内包するＡＳ番号も取得することができる。つまり、ノード１は、自ノードを内包するＡＳのＡＳ番号と、相手ノードを内包するＡＳのＡＳ番号を取得できる。
【００６２】
そこで、ネットワーク経路情報取得手段１３１は、自ノード１及び相手ノード２〜４のＩＰアドレスを指定して所定のプログラムを実行し、実行結果としてそのノード１〜４を含むそれぞれのＡＳのＡＳ番号を取得する。例えば、所定のプログラムとして「ＲＡＤｄ、ＭＥＲＩＴ ＮＥＴＷＯＲＫ ＩＮＣ．、ＲＯＵＴＩＮＧ ＡＳＳＥＴＳ ＤＡＴＡＢＡＳＥ、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ：http://www.radb.net/＞」のサービスを利用することができる。そして、ネットワーク経路情報取得手段１３１は、自ノード１を内包するＡＳに到着するＢＧＰメッセージを受信し、ＢＧＰメッセージからＡＳ−ＰＡＴＨ属性を取得し、そのＡＳ−ＰＡＴＨ属性が、相手ノードを内包するＡＳ番号で始まると判断した場合、そのＢＧＰメッセージから取得したＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、自ノード１と相手ノードとの間に存在するＡＳを特定し、そのＡＳ数を取得する。
【００６３】
図６は、ＢＧＰメッセージの例を示す図である。ＢＧＰメッセージは、当該メッセージを生成した日時（ＤＡＴＥ＆ＴＩＭＥ）、当該メッセージのタイプ（ＴＹＰＥ）、自ノードの隣のＡＳ番号（ＳＯＵＲＣＥ＿ＡＳ）、ＡＳのネットワークアドレス（ＰＲＥＦＩＸ）及びＡＳ−ＰＡＴＨ属性（ＡＳ＿ＰＡＴＨ）により構成される。タイプにおいて、Ｂはある時刻における経路一覧、Ａは経路の追加・更新、Ｗは経路の削除を示している。（尚、実際のＢＧＰメッセージではＡＳ番号として０〜６５５３５の数が記述されるが、ここではＡＳ番号を＃Ｘのように記述している。）図６に示すＢＧＰメッセージは、ＡＳ−＃Ｒに内包される自ノードからＡＳ−＃Ｓに内包される相手ノード（ネットワークアドレスｗｗ．ｘｘ．ｙ．ｚ／１６）との間に存在するＡＳ数を取得することを目的として、ＡＳ−＃Ｒにおいて観測されたＢＧＰメッセージから、ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージを抜き出した一覧である。すなわち、図６に示すＢＧＰメッセージは、ノード１の不通リンク決定部１３におけるネットワーク経路情報取得手段１３１が、通信部１１を介して受信したＢＧＰメッセージのうち、ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージを抜き出した一覧である。
【００６４】
図７は、図６に示したＡＳ−ＰＡＴＨ属性から生成された経路マップ（ＡＳマップ）を示す図である。ネットワーク経路情報取得手段１３１は、図６に示したＢＧＰメッセージ（ＡＳ−ＰＡＴＨ属性がＡＳ−＃Ｓから始まるＢＧＰメッセージ）を分析し、ＡＳ−＃Ｒに内包される自ノード１とＡＳ−＃Ｓに内包される相手ノードとの間に存在するＡＳのマップ（ＡＳマップ）を、図７に示すように生成する。図７に示すように、自ノード１と相手ノードとの間には、ＡＳ−＃Ｂ，＃Ｃ，＃Ｄ経由の第１の経路、ＡＳ−＃Ｔ，＃Ａ経由の第２の経路、ＡＳ−＃Ｅ，＃Ｔ，＃Ａ経由の第３の経路、及びＡＳ−＃Ｆ，＃Ｇ，＃Ｈ経由の第４の経路の合計４つの経路が存在している。ネットワーク経路情報取得手段１３１は、ＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性から生成したＡＳマップに基づいて、第１の経路の経由ＡＳ数３、第２の経路の経由ＡＳ数２、第３の経路の経由ＡＳ数３、及び第４の経路の経由ＡＳ数３を取得し、このうち最小のＡＳ数をネットワーク経路情報として不通リンク決定手段１３２に出力する。なぜなら、ＢＧＰによる経路制御においては通常、経由ＡＳ数の最も少ない経路をパケットの実際の転送経路として採用するからである。
【００６５】
尚、ＡＳマップは、ＩＳＰ間の接続の変更により変わることがあり得る。そこで、ネットワーク経路情報取得手段１３１は、所定周期にて適宜繰り返して、受信したＢＧＰメッセージを分析しＡＳマップを作成する。また、ＢＧＰメッセージの分析により生成されるＡＳマップは、必ずしも実際のメッシュ型ネットワーク１００の経路を反映していない場合もあり得る。そこで、ＡＳマップの分析により一旦計測対象から外れた候補リンクに対しても、適宜計測を行い、その正当性を検証する。
【００６６】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４との間の各リンクにおけるＡＳ数）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００６７】
例えば、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるＡＳ数と所定のしきい値とを比較し、ＡＳ数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。これは、多数のＡＳを経由するリンクは、経由するルータ台数も多くて利用可能帯域が狭く、伝送性能が劣る傾向にあるからである。尚、不通リンク決定手段１３２は、他のリンクのＡＳ数も含めて平均的なＡＳ数を算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ＡＳ数のばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００６８】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、最適パスを決定するための処理負荷を軽減することができる。
【００６９】
以上のように、実施例２のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ＢＧＰメッセージを受信し、ＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性から、相手ノードを含むＡＳの番号から始まるＢＧＰメッセージを特定し、このＢＧＰメッセージに含まれるＡＳ−ＰＡＴＨ属性を分析することにより、自ノード１と相手ノード２〜４との間のＡＳマップを生成し、ＡＳマップに基づいて、自ノード１と相手ノード２〜４との間の各リンクにおけるＡＳ数を示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ＡＳ数の多いリンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンクから不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００７０】
これにより、実施例１と同様に、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの負荷を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワークにおいて、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【００７１】
尚、実施例２において、以下に示す他の手法を用いることができる。例えば、図１に示したメッシュ型ネットワーク１００及び図７に示したＡＳマップにおいて、前述の「ＲＡＤｄ」のプログラムを実行することにより、ノード１がＡＳ−＃Ｒに、ノード２がＡＳ−＃Ｃに、ノード３がＡＳ−＃Ｓに、ノード４がＡＳ−＃Ｔに内包されることがわかったとする。このとき、ノード１→３への直接伝送のパスとノード１→４→３への迂回伝送のパスは、ＡＳマップ上では同一の経路（ＡＳ−＃Ｒ→＃Ｔ→＃Ａ→＃Ｓ）となる。このため、両パスの利用可能帯域の計測結果は似通った結果になると予測される。
【００７２】
そこで、不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からＡＳマップの情報を入力し、ＡＳマップの情報に基づいて、同一または類似した経路を通る候補リンクが複数存在することを判定した場合、それらの複数の候補リンクのうちの一部のリンクを不通リンクに決定する。前記例の場合、不通リンク決定手段１３２は、ノード１→３への直接伝送のパス及びノード１→４→３の迂回伝送のパスのうちの例えば後者のパスを不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。
【００７３】
また、例えば、図１に示したメッシュ型ネットワーク１００及び図７に示したＡＳマップにおいて、前述と同様に、ノード１がＡＳ−＃Ｒに、ノード２がＡＳ−＃Ｃに、ノード３がＡＳ−＃Ｓに、ノード４がＡＳ−＃Ｔに内包されるものとする。この場合、ノード１→３への直接伝送のパス（ＡＳ−＃Ｒ→＃Ｔ→＃Ａ→＃Ｓ）と、ノード１→２→３の迂回伝送のパス（ＡＳ−＃Ｒ→＃Ｂ→＃Ｃ→＃Ｄ→＃Ｓ）とは、ＡＳマップ上で経路を共有しないから、ノード１→３への直接伝送とノード１→２→３の迂回伝送とは相互の干渉が少ないことが予想される。
【００７４】
そこで、不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からＡＳマップの情報を入力し、ＡＳマップの情報に基づいて、経路を共通しないパスの構成リンクだけを候補リンクとし、それ以外のリンクを伝送性能が劣ると判断して不通リンクに決定する。前記例の場合、両パスの構成リンク（この場合はリンク１−３とリンク１−２とリンク２−３の３つ）以外のリンクは全て伝送性能が劣ると判断して不通リンクに決定し、伝送に利用するパスをこの２パスに限定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、ノード１において実行される伝送アプリケーションに対し、ノード１→３とノード１→２→３の両パスを最適パスとして提示し、伝送アプリケーションには同時に両パスを使って伝送させることにより、両パスの利用可能帯域を合わせて伝送性能を向上させることができる。
【００７５】
前記実施例２では、ノード１〜４は、当該ノード１〜４をそれぞれ内包するＡＳのＢＧＰルータからＢＧＰメッセージを受信するものとして説明した。ノード１〜４は、ＢＧＰルータからＢＧＰメッセージを受信する代わりに、他のＡＳで観測したＢＧＰメッセージから、ＡＳ−ＰＡＴＨ属性に自ノードと相手ノードのＡＳ番号を含むＢＧＰメッセージを抽出し（受信し）、それらのメッセージからＡＳマップを作成するようにしてもよい。図７に示した例では、ＡＳ−＃Ｔに内包されるノードとＡＳ−＃Ｓに内包されるノードとを結ぶリンクのネットワーク経路情報を取得する際に、ＡＳ−＃Ｒで観測したＢＧＰメッセージからＡＳ−ＰＡＴＨ属性に自ノードと相手ノードのＡＳ番号を含むＢＧＰメッセージを抽出し、ＡＳマップを作成してもよい。この場合、ノード１〜４は、ＢＧＰメッセージの観測データを、所定のプログラムを実行することにより取得する。例えば、所定のプログラムとして「routeviewsプロジェクト、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ： http://www.routeviews.org/＞」「routing information serviceプロジェクト、［平成２２年４月２２日検索］、インターネット＜ＵＲＬ：http://www.ripe.net/projects/ris/index.html」のサービスを利用し、インターネットの各所で観測したＢＧＰメッセージを蓄積して公開しているサイトから、ＢＧＰメッセージの観測データを取得することができる。
【実施例３】
【００７６】
次に、実施例３について説明する。実施例３は、前述のとおり、経路制御用のＯＳＰＦに用いるメッセージを分析してネットワーク経路情報を取得し、候補リンクを削減する例である。実施例３は、ＩＳＰの内部ネットワーク、企業等の専用ネットワーク等において、オーバーレイ伝送網を構築する場合に適用がある。
【００７７】
〔ノードの処理概要／実施例３〕
実施例３のノードを含むメッシュ型ネットワークの構成は、図１に示した構成と同様である。また、実施例３のノード１は、図２に示した実施例１のステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８と同じ処理を行い、ステップＳ２０３とは異なる処理を行う。ステップＳ２１〜ステップＳ２６、ステップＳ２０１、ステップＳ２０２、ステップＳ２０４〜ステップＳ２０８の説明については省略する。
【００７８】
ノード１は、図２に示した実施例１のステップＳ２０３の代わりに、ＯＳＰＦに用いるメッセージを受信して分析し、分析結果から、自ノード１と相手ノード２〜４との間のルータ台数またはコスト（例えば、回線の速度）を示すネットワーク経路情報を取得する（ステップＳ２０３）。
【００７９】
〔ノードの構成／実施例３〕
次に、実施例３におけるノード１の構成について説明する。実施例３におけるノード１の構成は、図３に示した実施例１の構成と同じであるが、実施例３におけるノード１の不通リンク決定部１３が、実施例１の不通リンク決定部１３とは異なる処理を行う点で相違する。通信部１１、プローブパケット処理部１２、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の説明については省略する。
【００８０】
不通リンク決定部１３は、ネットワーク経路情報取得手段１３１及び不通リンク決定手段１３２を備えている。ネットワーク経路情報取得手段１３１は、ＯＳＰＦに用いるメッセージを、通信部１１を介して受信し、受信したメッセージを分析し、分析結果として、相手ノード２〜４までの間のルータ台数またはコストを算出する。ネットワーク経路情報取得手段１３１は、ルータ台数またはコストをネットワーク経路情報として不通リンク決定手段１３２に出力する。
【００８１】
ＯＳＰＦは、小規模のＩＰネットワークを構成するルータ間において、経路制御のためのメッセージを交換する経路制御プロトコルである。ＯＳＰＦでは、各ルータにユニークな番号（ルータＩＤ）が付与されている。各ルータは、自らのインターフェースに付与されたネットワークアドレス、コスト情報及び自らのルータＩＤを含む広告メッセージ（ＬＳＡ：Ｌｉｎｋ Ｓｔａｔｅ Ａｄｖｅｒｔｉｓｅｍｅｎｔ）を、全てのネットワークインターフェースから同報送信する。また、ＬＳＡを受信したルータは、ＬＳＡを受信したネットワークインターフェースを除いた全てのネットワークインターフェースから、受信したＬＳＡを再び同報送信する。各ルータは、他のルータが同報送信したＬＳＡを受信することにより、ネットワーク上に存在するルータの配置、ルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報（例えば回線速度）を取得し、これらを反映したルータマップ情報を生成し、生成されたルータマップ情報に基づき実際のパケット転送経路を決定している。
【００８２】
図８は、ＯＳＰＦのＬＳＡに基づいて生成されたルータマップ情報例を示す図である。ルータマップ情報から、例えば、ネットワーク１７２．１６．１０．０／２４からネットワーク１７２．１６．３０．０／２４に至る経路にはルータ１→３（ＩＤ１→ＩＤ３）を経由する経路（そのコストはコスト１−３）とルータ１→２→３（ＩＤ１→ＩＤ２→ＩＤ３）を経由する経路（そのコストはコスト１−２とコスト２−３の和）との二つの経路が存在すること、がわかる。ノードのＩＰアドレスが既知なのでノードを内包するネットワークアドレスもわかるから、ルータマップ情報から２台のノードの間にあるルータの台数及びコストを知ることができる。尚、ＯＳＰＦの詳細については「Ｒ．Ｈａｌｈｏｔｒａ著、清水奨訳、入門ＩＰルーティング、オライリージャパン、２００２／８」の第６章を参照されたい。
【００８３】
ノード１における不通リンク決定部１３のネットワーク経路情報取得手段１３１は、通信部１１を介して、ルータが同報送信するＬＳＡを受信することにより、ルータの配置、ネットワークアドレス及びコスト情報を取得し、ＯＳＰＦ対応ルータと同等のルータマップ情報を生成することができる。この場合、ＯＳＰＦ対応ルータに、生成したルータマップ情報をノードへ送信する機能を持たせることにより、ノード１のネットワーク経路情報取得手段１３１がルータマップ情報を取得してもよい。
【００８４】
このルータマップ情報は、図７に示した実施例２のＡＳマップに対応し、実施例３のルータは実施例２のＡＳに対応する。つまり、実施例３のネットワーク経路情報取得手段１３１は、実施例２のネットワーク経路情報取得手段１３１と同様の処理を行う。
【００８５】
不通リンク決定手段１３２は、ネットワーク経路情報取得手段１３１からネットワーク経路情報（自ノード１と相手ノード２〜４との間のルータ台数及びコスト）を入力し、ネットワーク経路情報に基づいて、所定のしきい値との比較演算等により、伝送性能が劣る候補リンクを判定し、判定した候補リンクを不通リンクとして特定する。
【００８６】
例えば、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるルータ台数と所定のしきい値とを比較し、ルータ台数が所定のしきい値よりも大きいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。また、不通リンク決定手段１３２は、相手ノードとの間のリンクにおけるコストである回線の速度と所定のしきい値とを比較し、回線の速度が所定のしきい値よりも小さいと判断した場合、その相手ノードとの間のリンクは伝送性能が劣る候補リンクであると判定する。尚、不通リンク決定手段１３２は、他のリンクのルータ台数またはコストも含めて平均的なルータ台数またはコストを算出し、その大小関係により判断してもよいし、ネットワーク経路情報取得手段１３１により定期的に取得されたネットワーク経路情報を逐次入力し、ルータ台数またはコストのばらつきと所定のしきい値と比較し、ばらつきが大きいリンクは不安定であるとし、伝送性能が劣る候補リンクであると判定するようにしてもよい。
【００８７】
そして、不通リンク決定手段１３２は、不通リンクに関する情報（不通リンク情報）をプローブパケット処理部１２及び帯域計測部１４に出力する。これにより、プローブパケット処理部１２に、不通リンクの相手ノードに対するプローブパケットの送信を停止させることができ、その相手ノードに対し、隣接リンクの利用可能帯域の計測を行わせないようにすることができるから、最適パスを決定するための処理負荷を軽減することができる。
【００８８】
以上のように、実施例３のノード１によれば、不通リンク決定部１３のネットワーク経路情報取得手段１３１が、ＯＳＰＦに用いるＬＳＡに基づいて、ルータの配置、ルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得してルータマップ情報を生成し、または、ルータからルータマップ情報を取得してそのルータマップ情報を分析することにより、自ノード１と相手ノード２〜４との間のルータ台数またはコストを示すネットワーク経路情報を取得し、不通リンク決定手段１３２が、ネットワーク経路情報に基づいて、ルータ台数の多いリンクまたはコストの高い（回線速度の遅い）リンクを伝送性能が劣る不通リンクと判定するようにした。そして、帯域計測部１４が、候補リンクから不通リンクを除外し、プローブパケット処理部１２が、不通リンクの相手ノードに対するプローブパケットの送信を停止し、最適パス決定部１６が、自ノード１における不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定するようにした。
【００８９】
これにより、実施例１，２と同様に、計測対象となる候補リンク数を削減することができる。そして、利用可能帯域を計測するために用いるプローブパケットの送出総量を削減し、ネットワークの付加を低減することができる。また、最適パスを決定するための計算量を削減することができる。したがって、前記課題（１）を解決することができ、メッシュ型ネットワークにおいて、ノード間の最適パスを決定するための処理負荷を軽減することが可能となる。
【００９０】
尚、実施例３においても、実施例２にて説明した他の手法を用いることができる。ノード１の不通リンク決定部１３における不通リンク決定手段１３２は、実施例２の他の手法と同様に、ルータマップ情報に基づいて、同一または類似した経路を通る候補リンクが複数存在することを判定した場合、複数の候補リンクのうちの一部のリンクを不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、不通リンク決定手段１３２は、実施例２の他の手法と同様に、ルータマップ情報に基づいて、経路を共通しないパスの構成リンクだけを候補リンクとし、それ以外のリンクを伝送性能が劣ると判断して不通リンクに決定する。これにより、ノード１の処理負荷及びメッシュ型ネットワーク１００の負荷を軽減することができる。また、伝送アプリケーションに対し、例えば、ノード１→３とノード１→２→３の両パスを最適パスとして提示し、伝送アプリケーションには同時に両パスを使って伝送させることにより、両パスの利用可能帯域を合わせて伝送性能を向上させることができる。
【００９１】
前述の実施例１〜３では、メッシュ型ネットワーク１００の全ノード１〜４が、不通リンクを除外した候補リンクの利用可能帯域を計測し、結果パケットに格納して他のノード１〜４へ送信することにより、その計測結果をお互いに交換し、それぞれ最適パスを決定するようにした。これに対し、全てのノード１〜４がそれぞれ最適パスを決定するのではなく、所定の１台の経路計算ノードに、最適パスを決定させるようにしてもよい。例えば、各ノード１〜４は、隣接リンクの利用可能帯域を計測し、その計測結果を結果パケットに格納し、経路計算ノードへ送信する。経路計算ノードは、結果パケットを受信し、実施例１〜３の不通リンク決定部１３と同様の処理を行って不通リンクを決定し、最適パス決定部１６と同様の処理を行って最適パスを決定する。各ノード１〜４は、経路計算ノードに対し、不通リンク及び最適パスの問い合わせを行う。
【実施例４】
【００９２】
次に、実施例４について説明する。実施例４は、前述のとおり、実施例１〜３のいずれかの例に加え、隣接リンクの利用可能帯域をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。
【００９３】
図９は、実施例４のノードを含むメッシュ型ネットワークの構成を示す概略図である。このメッシュ型ネットワーク１００は、相互に接続された複数のノード２１〜２４等により、網目状に構成されている。実施例５も同様である。
【００９４】
〔ノードの処理概要／実施例４〕
図１０は、図９に示したノード２１の処理概要を示すフローチャートである。ノード２２〜２４もノード２１と同じ処理を行う。実施例５も同様である。
【００９５】
ノード２１は、ノード２２〜２４からプローブパケットをそれぞれ受信した場合（ステップＳ９１：Ｙ）、隣接リンクの利用可能帯域（帯域２−１，３−１，４−１）をそれぞれ計測する（ステップＳ９０１）。利用可能帯域を計測した隣接リンクが候補リンクとなる。
【００９６】
ノード２１は、不通リンクの更新タイミングを判定すると（ステップＳ９２：Ｙ）、実施例１〜３のうちのいずれかにより、ネットワーク経路情報を取得する（ステップＳ９０２）。更新タイミングは、例えば所定の時間間隔とする。そして、ノード２１は、ネットワーク経路情報に基づいて不通リンクを決定し（ステップＳ９０３）、不通リンクを候補リンク（リンク２−１，３−１，４−１）から除外する（ステップＳ９０４）。図９の例は、不通リンクが存在しない場合を示している。
【００９７】
ノード２１は、プローブパケットの送信タイミングを判定すると（ステップＳ９３：Ｙ）、ノード２２〜２４において利用可能帯域を計測するためのプローブパケットに、不通リンクを除外した候補リンクの利用可能帯域をプローブパケットに格納し（ステップＳ９０５）、このプローブパケットをノード２２〜２４へ送信する（ステップＳ９０６）。送信タイミングは、例えば所定の時間間隔とする。
【００９８】
ノード２１は、最適パスを決定するタイミングを判定すると（ステップＳ９４：Ｙ）、自ノード２１において不通リンクを除外した候補リンクの利用可能帯域、及び他ノード２２〜２４において不通リンクを除外した候補リンクの利用可能帯域に基づいて、最適パスを決定する（ステップＳ９０７）。
【００９９】
〔ノードの構成／実施例４〕
次に、図９に示したノード２１の構成について説明する。図１１は、ノード２１の構成を示すブロック図である。このノード２１は、通信部１１、プローブパケット処理部３１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７を備えている。図１１において、図３に示したノード１の構成と共通する部分には図３と同一の符号を付し、その詳しい説明は省略する。図３に示したノード１とこのノード２１とを比較すると、ノード１，２１は、通信部１１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７を備えている点で同一であるが、ノード２１は、結果パケット処理部１５を備えておらず、ノード１のプローブパケット処理部１２とは異なるプローブパケット処理部３１を備えている点で相違する。
【０１００】
プローブパケット処理部３１は、プローブパケットの送信タイミングにおいて、ノード２２〜２４において利用可能帯域を計測するためのプローブパケットを生成すると共に、記憶部１７から自ノード帯域情報（自ノード２１における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、この自ノード帯域情報をプローブパケットに格納し、このプローブパケットを、通信部１１を介してノード２２〜２４へ送信する。また、プローブパケット処理部３１は、ノード２２〜２４から通信部１１を介して、プローブパケットを受信し、プローブパケットの受信間隔を算出し、受信間隔等の情報をプローブパケット受信情報として帯域計測部１４に出力する。そして、受信したプローブパケットから、他ノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域を取得し、他ノード帯域情報として記憶部１７に格納する。また、プローブパケット処理部３１は、不通リンク決定部１３から不通リンク情報を入力し、不通リンクの相手ノードに対するプローブパケットの送信を停止する。
【０１０１】
以上のように、実施例４のノード２１によれば、プローブパケット処理部３１が、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域を格納したプローブパケットを送信し、他ノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域が格納されたプローブパケットを受信するようにした。
【０１０２】
これにより、隣接リンクの利用可能帯域を計測するためのプローブパケットと、不通リンクを除外した候補リンクの利用可能帯域を含む結果パケットとを別々に送受信することなく、帯域計測を行い、かつ計測結果を交換するためのプローブパケットのみを送受信する。したがって、帯域計測及び計測結果交換を同時に行いながら、ネットワークへのパケット送出総量を削減することができる。したがって、実施例１の効果に加え、前記課題（２）を解決することができる。
【０１０３】
尚、ノード２１のプローブパケット処理部３１は、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域（具体的には、リンクの識別子（例えば、事前に各リンクに付与したユニークな識別子、リンクの両端のノードのＩＰアドレスを組にした識別子）及びそのリンクの利用可能帯域の計測結果）をプローブパケットに格納するようにしたが、その格納形式は限定されない。
【実施例５】
【０１０４】
次に、実施例５について説明する。実施例５は、前述のとおり、実施例４の拡張例であり、隣接リンクの利用可能帯域の属性をプローブパケットに格納して送信し、ネットワークのパケット送出総量を削減する例である。
【０１０５】
〔ノードの処理概要／実施例５〕
実施例５のノードを含むメッシュ型ネットワークの構成は、図９に示した構成と同様である。また、実施例５のノード２１は、図１０に示した実施例４の処理、すなわち、ステップＳ９１〜ステップＳ９４及びステップＳ９０１〜ステップＳ９０７の処理に加え、ステップＳ９０５とステップＳ９０６との間に、隣接リンクの利用可能帯域の属性を生成し、この属性をプローブパケットに格納する処理を行う。ステップＳ９１〜ステップＳ９４及びステップＳ９０１〜ステップＳ９０７の説明については省略する。
【０１０６】
〔ノードの構成／実施例５〕
次に、実施例５におけるノード２１の構成について説明する。実施例５におけるノード２１の構成は、図１１に示した実施例４の構成と同じであるが、実施例５におけるノード２１のプローブパケット処理部３１及び最適パス決定部１６が、実施例４のプローブパケット処理部３１及び最適パス決定部１６とは異なる処理を行う点で相違する。通信部１１、不通リンク決定部１３、帯域計測部１４及び記憶部１７の説明については省略する。
【０１０７】
プローブパケット処理部３１は、実施例４に示した処理に加え、記憶部１７から自ノード帯域情報を読み出し、利用可能帯域を計測する計測結果である自ノード帯域情報に対し、読み出す毎に統計処理し、計測結果の信頼性（例えば、しきい値と比較することにより得られる、計測結果のばらつきが大きいか小さいかを示す情報）または安定性（例えば、しきい値と比較することにより得られる、計測結果が長期的にほぼ同一の値を示しているかを示す情報）を属性として生成する。そして、プローブパケット処理部３１は、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域に加え、生成した属性をプローブパケットに格納し、ノード２２〜２４へ送信する。また、プローブパケット処理部３１は、ノード２２〜２４により送信されたプローブパケットを受信し、このプローブパケットから属性を取得し、最適パス決定部１６に出力する。
【０１０８】
最適パス決定部１６は、記憶部１７から自ノード帯域情報及び他ノード帯域情報（ノード２１における不通リンクを除外した候補リンクの利用可能帯域、及びノード２２〜２４における不通リンクを除外した候補リンクの利用可能帯域）を読み出し、プローブパケット処理部３１から属性（計測結果の信頼性または安定性）を入力し、不通リンクを除外した候補リンクの利用可能帯域及び属性に基づいて、最適パスを決定する。すなわち、信頼性または安定性が高いリンクを優先的に扱い、最適パスを決定する。例えば、同じ利用可能帯域のリンクが複数存在する場合、信頼性または安定性が高い方のリンクを、最適パスのリンクとなるように扱う。
【０１０９】
尚、属性には、計測結果が得られた時刻（計測時刻）を含むようにしてもよい。この場合、最適パス決定部１６は、計測時刻が新しいリンクを優先的に扱い、最適パスを決定する。例えば、同じ利用可能帯域のリンクが複数存在する場合、計測時刻が新しい方のリンクを、最適パスのリンクとなるように扱う。また、属性には、伝送遅延等の情報を含むようにしてもよく、これらの情報は、最適パスの決定の際に用いられる。
【０１１０】
図１２は、実施例４，５におけるプローブパケットの構成例を示す図である。図１３に示したように、従来のプローブパケットは、先頭のヘッダ部分を除いて、ダミーデータにて構成されている。これに対し、図１２に示す実施例４，５におけるプローブパケットは、従来のプローブパケットと同じヘッダと、当該プローブパケットを送信するノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、帯域計測結果である利用可能帯域、及び属性を含むペイロードとにより構成される。残りのペイロード部にはダミーデータが格納される。図１２では、１つの隣接リンク毎に、リンクの識別子としてのリンクの相手ノードのＩＰアドレス（ＩＰヘッダのＳｏｕｒｃｅ Ａｄｄｒｅｓｓと併せてリンクを一意に識別可能なＩＰアドレス）、リンクの帯域計測結果である利用可能帯域、及びリンクの属性を組としている。ここではリンクの帯域計測結果である利用可能帯域、リンクの属性のデータ長は８バイトとした。尚、隣接リンクの数が少ない場合は、残りの部分にダミーデータが格納され、隣接リンクの数が多い場合は、ペイロード部の情報が複数のプローブパケットに分けて格納される。尚、実施例４では、図１２に示したプローブパケットのペイロード部に、ノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、及び帯域計測結果である利用可能帯域が格納され、実施例５では、ノード２１が保持する隣接リンクの相手ノードのＩＰアドレス、帯域計測結果である利用可能帯域、及び属性が格納される。
【０１１１】
以上のように、実施例５のノード２１によれば、プローブパケット処理部３１が、自ノード２１における不通リンクを除外した候補リンクの利用可能帯域に加えて、その属性（例えば、計測した利用可能帯域の信頼性または安定性を数値化した情報）もプローブパケットに格納して送信し、他ノード２〜４における不通リンクを除外した候補リンクの利用可能帯域及び属性が格納されたプローブパケットを受信するようにした。そして、最適パス決定部１６が、属性を参照して最適パスを決定するようにした。
【０１１２】
これにより、リンクの信頼性または安定性の高いリンクを有するパスが最適パスに決定される可能性が高くなる。したがって、実施例４の効果に加え、決定される最適パスの精度が高くなる。
【０１１３】
以上、実施例１〜５を挙げて本発明を説明したが、本発明は前記実施例１〜５に限定されるものではなく、その技術思想を逸脱しない範囲で種々変形可能である。例えば、前記実施例１〜５では、メッシュ型ネットワーク１００を前提として説明したが、メッシュ型ネットワーク１００には、オーバーレイ技術による論理ネットワークも含まれる。また、前記実施例１〜５では、パケットペア法を用いて利用可能帯域を計測することを想定して説明したが、本発明は、プローブパケットを用いる計測手法一般に適用可能であり、計測手法を限定するものではない。
【０１１４】
尚、本発明の実施例１〜５によるノード１〜４，２１〜２４のハード構成としては、通常のコンピュータを使用することができる。ノード１〜４，２１〜２４は、ＣＰＵ、ＲＡＭ等の揮発性の記憶媒体、ＲＯＭ等の不揮発性の記憶媒体、及びインターフェース等を備えたコンピュータによって構成される。実施例１〜３のノード１〜４に備えた通信部１１、プローブパケット処理部１２、不通リンク決定部１３、帯域計測部１４、結果パケット処理部１５、最適パス決定部１６及び記憶部１７の各機能は、これらの機能を記述したプログラムをＣＰＵに実行させることによりそれぞれ実現される。また、実施例４，５のノード２１〜２４に備えた通信部１１、プローブパケット処理部３１、不通リンク決定部１３、帯域計測部１４、最適パス決定部１６及び記憶部１７の各機能も、これらの機能を記述したプログラムをＣＰＵに実行させることによりそれぞれ実現される。これらのプログラムは、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリ等の記憶媒体に格納して頒布することもできる。
【符号の説明】
【０１１５】
１〜４，２１〜２４，１０１〜１０４ ノード
１１ 通信部
１２ プローブパケット処理部
１３ 不通リンク決定部
１４ 帯域計測部
１５ 結果パケット処理部
１６ 最適パス決定部
１７ 記憶部
３１ プローブパケット処理部
１００ メッシュ型ネットワーク
１３１ ネットワーク経路情報取得手段
１３２ 不通リンク決定手段
【特許請求の範囲】
【請求項１】
複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定するノード装置において、
当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するネットワーク経路情報取得手段、及び、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断し、前記リンクを不通リンクとして決定する不通リンク決定手段を有する不通リンク決定部と、
当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測する帯域計測部と、
前記帯域計測部により計測された、前記不通リンクを除外した候補リンクの利用可能帯域を結果パケットに格納し、他のノード装置へ送信し、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得する結果パケット処理部と、
前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、前記結果パケット処理部により取得された他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定する最適パス決定部と、
を備えたことを特徴とするノード装置。
【請求項２】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークを管理するために用いるｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムを実行し、この実行結果に基づいて、当該ノード装置と他のノード装置との間のルータ台数またはＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項３】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークの経路を制御するためのＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）に用いるＢＧＰメッセージのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、他のノード装置を内包するＡＳを始点として送信され、当該ノード装置を内包するＡＳへ送信されたＢＧＰメッセージを選定し、前記選定したＢＧＰメッセージのＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号から、当該ノードと他のノードとの間のＡＳ数をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項４】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークの経路を制御するためのＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）に用いる広告メッセージに基づいて、当該メッセージが送信されたルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得し、前記ネットワークアドレス及びコスト情報から、当該ノード装置と他のノード装置との間のルータ台数またはコスト情報をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項５】
請求項１から４までのいずれか一項に記載のノード装置において、
前記結果パケット処理部の代わりにプローブパケット処理部を備え、
前記プローブパケット処理部は、当該ノード装置における隣接リンクの利用可能帯域を計測するためのプローブパケットを他のノード装置から受信し、他のノード装置において隣接リンクの利用可能帯域を計測させるためのプローブパケットに、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を格納し、前記プローブパケットを他のノード装置へ送信することを特徴とするノード装置。
【請求項６】
複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定する方法において、
当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するステップと、
前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断するステップと、
前記伝送性能が劣ると判断したリンクを不通リンクとして決定するステップと、
当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測するステップと、
前記計測した、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を、結果パケットに格納し、他のノード装置へ送信するステップと、
他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得するステップと、
当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定するステップと、
を有することを特徴とする最適パス決定方法。
【請求項７】
コンピュータを、請求項１から５までのいずれか一項に記載のノード装置として機能させるための最適パス決定プログラム。
【請求項１】
複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定するノード装置において、
当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するネットワーク経路情報取得手段、及び、前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断し、前記リンクを不通リンクとして決定する不通リンク決定手段を有する不通リンク決定部と、
当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測する帯域計測部と、
前記帯域計測部により計測された、前記不通リンクを除外した候補リンクの利用可能帯域を結果パケットに格納し、他のノード装置へ送信し、他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得する結果パケット処理部と、
前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、前記結果パケット処理部により取得された他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定する最適パス決定部と、
を備えたことを特徴とするノード装置。
【請求項２】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークを管理するために用いるｐｉｎｇ（ピング）プログラムまたはｔｒａｃｅｒｏｕｔｅ（トレースルート）プログラムを実行し、この実行結果に基づいて、当該ノード装置と他のノード装置との間のルータ台数またはＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項３】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークの経路を制御するためのＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）に用いるＢＧＰメッセージのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）−ＰＡＴＨ属性に含まれるＡＳ番号に基づいて、他のノード装置を内包するＡＳを始点として送信され、当該ノード装置を内包するＡＳへ送信されたＢＧＰメッセージを選定し、前記選定したＢＧＰメッセージのＡＳ−ＰＡＴＨ属性に含まれるＡＳ番号から、当該ノードと他のノードとの間のＡＳ数をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項４】
請求項１に記載のノード装置において、
前記不通リンク決定部のネットワーク経路情報取得手段は、ネットワークの経路を制御するためのＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）に用いる広告メッセージに基づいて、当該メッセージが送信されたルータのインターフェースに付与されたネットワークアドレス、及びルータ間リンクのコスト情報を取得し、前記ネットワークアドレス及びコスト情報から、当該ノード装置と他のノード装置との間のルータ台数またはコスト情報をネットワーク経路情報として取得し、
前記不通リンク決定手段は、前記ネットワーク経路情報取得手段により取得されたネットワーク経路情報と所定のしきい値とを比較し、前記ネットワーク経路情報についての当該ノード装置と他のノード装置との間のリンクを不通リンクとして決定することを特徴とするノード装置。
【請求項５】
請求項１から４までのいずれか一項に記載のノード装置において、
前記結果パケット処理部の代わりにプローブパケット処理部を備え、
前記プローブパケット処理部は、当該ノード装置における隣接リンクの利用可能帯域を計測するためのプローブパケットを他のノード装置から受信し、他のノード装置において隣接リンクの利用可能帯域を計測させるためのプローブパケットに、前記帯域計測部により計測された当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を格納し、前記プローブパケットを他のノード装置へ送信することを特徴とするノード装置。
【請求項６】
複数のノード装置により構成されるメッシュ型ネットワークの下で、隣接リンクの利用可能帯域に基づいて、ノード装置間の最適パスを決定する方法において、
当該ノード装置と他のノード装置との間の伝送性能の判定に用いるネットワーク経路情報を取得するステップと、
前記ネットワーク経路情報に基づいて、伝送性能が劣るリンクを判断するステップと、
前記伝送性能が劣ると判断したリンクを不通リンクとして決定するステップと、
当該ノード装置と他のノード装置との間の経路を示す複数の候補リンクから、前記不通リンクを除外し、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を計測するステップと、
前記計測した、当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域を、結果パケットに格納し、他のノード装置へ送信するステップと、
他のノード装置から、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域が格納された結果パケットを受信し、前記結果パケットから、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域を取得するステップと、
当該ノード装置における不通リンクを除外した候補リンクの利用可能帯域と、他のノード装置における不通リンクを除外した候補リンクの利用可能帯域とに基づいて、前記最適パスを決定するステップと、
を有することを特徴とする最適パス決定方法。
【請求項７】
コンピュータを、請求項１から５までのいずれか一項に記載のノード装置として機能させるための最適パス決定プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１１−２４４３１２（Ｐ２０１１−２４４３１２Ａ）
【公開日】平成２３年１２月１日（２０１１．１２．１）
【国際特許分類】
【出願番号】特願２０１０−１１６１５３（Ｐ２０１０−１１６１５３）
【出願日】平成２２年５月２０日（２０１０．５．２０）
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
【公開日】平成２３年１２月１日（２０１１．１２．１）
【国際特許分類】
【出願日】平成２２年５月２０日（２０１０．５．２０）
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
[ Back to top ]