(57)【特許請求の範囲】
【請求項１】
R S V P - T Eが動作するM P L S伝送装置で構成されたネットワークにおいて、L S P経路を計算するL S P経路計算方法であって、
要求取得手段が、各ノードの接続関係を表したトポロジ情報及び、送信ノードと受信ノード（ マルチキャストの場合は複数） 及び、L S P要求帯域を受け付け、該送信ノードを最初の探索ノードとして訪問済記憶手段に格納する要求取得ステップと、
最小残余帯域計算手段が、前記トポロジ情報に含まれる経路上のリンクから送信ノードに隣接する隣接ノードを探索し、該送信ノードから該隣接ノードまでの経路上のリンクにおける残余帯域の中で最小の残余帯域を第１ の最小残余帯域とする最小残余帯域計算ステップと、
ホップ数計算手段が、前記探索ノード経由の経路における第１ のホップ数を計算するホップ数計算ステップと、
判定手段が、記憶手段に前記隣接ノードに対して他の経路における第２ の最小残余帯域が計算されて格納されていない場合は、前記第１ の最小残余帯域と前記第１ のホップ数を記憶手段に格納し、記憶手段に前記隣接ノードに対して他の経路における第２ の最小残余帯域が計算されて格納されている場合は、前記第１ の最小残余帯域と比較し、該第１の最小残余帯域の方が大きい場合は、該第１ の最小残余帯域、前記第１ のホップ数、経路を該記憶手段に格納し、該最小残余帯域が等しい場合は、該隣接ノードに対する他の経路におけるホップ数と比較し、該第１ のホップ数の方が小さい場合、該第１ の最小残余帯域、該第１ のホップ数、経路を該記憶手段に格納する判定ステップと、
経路決定手段が、前記訪問済ノード記憶手段を参照して、まだ探索ノードとなっていないノードの中から前記記憶手段を参照して、経路上のリンクでホップ数が最小のノードを探索ノードとし、ホップ数が最小のノードが複数ある場合には、該記憶手段を参照して最小残余帯域が最大のノードを探索ノードとし、該探索ノードを訪問済ノード記憶手段に格納すると共に、該探索ノードを経路記憶手段に格納する経路決定ステップと、
前記訪問済ノード記憶手段を参照して、前記受信ノードが訪問済となるか、前記経路決定ステップにおいて新たな探索ノードが決定できなくなるまで、決定された探索ノードを用いて最小残余帯域計算ステップ以降の処理を繰り返し、
経路出力手段が、前記経路記憶手段に格納された経路を出力する経路出力ステップと、を行う
ことを特徴とするL S P経路計算方法。
【請求項２】
リンク削除手段が、前記要求取得ステップで取得した前記トポロジ情報から前記L S P要求帯域に満たない残余帯域を持つリンクを削除した経路を、リンク削除済記憶手段に格納するリンク削除ステップを更に行い、
前記最小残余帯域計算ステップは、前記リンク削除済記憶手段に格納された経路上のリンクから探索ノードと該探索ノードに隣接する隣接ノードを探索する、
請求項１記載のL S P経路計算方法。
【請求項３】
前記ホップ数計算ステップにおいて、
前記探索ノードが受信ノードである場合は、ホップ数を１ とする、
請求項１記載のL S P経路計算方法。
【請求項４】
R S V P - T Eが動作するM P L S伝送装置で構成されたネットワークにおいて、L S P経路を計算するL S P経路計算装置であって、
各ノードの接続関係を表したトポロジ情報及び、送信ノードと受信ノード（ マルチキャストの場合は複数）及び、L S P要求帯域を受け付け、該送信ノードを最初の探索ノードとして訪問済記憶手段に格納する要求取得手段と、
最小残余帯域計算手段が、前記トポロジ情報に含まれる経路上のリンクから送信ノードに隣接する隣接ノードを探索し、該送信ノードから該隣接ノードまでの経路上のリンクにおける残余帯域の中で最小の残余帯域を第１の最小残余帯域とする最小残余帯域計算手段と、
前記探索ノード経由の経路における第１のホップ数を計算するホップ数計算手段と、
記憶手段に前記隣接ノードに対して他の経路における第２の最小残余帯域が計算されて格納されていない場合は、前記第１の最小残余帯域と前記第１のホップ数を記憶手段に格納し、記憶手段に前記隣接ノードに対して他の経路における第２の最小残余帯域が計算されて格納されている場合は、前記第１の最小残余帯域と比較し、該第１の最小残余帯域の方が大きい場合は、該第１の最小残余帯域、前記第１のホップ数、経路を該記憶手段に格納し、該最小残余帯域が等しい場合は、該隣接ノードに対する他の経路におけるホップ数と比較し、該第１のホップ数の方が小さい場合、該第１の最小残余帯域、該第１のホップ数、経路を該記憶手段に格納する判定手段と、
前記訪問済ノード記憶手段を参照して、まだ探索ノードとなっていないノードの中から経路上のリンクで、前記記憶手段を参照してホップ数が最小のノードを探索ノードとし、ホップ数が最小のノードが複数ある場合には、該記憶手段を参照して最小残余帯域が最大のノードを探索ノードとし、該探索ノードを訪問済ノード記憶手段に格納すると共に、該探索ノードを経路記憶手段に格納する経路決定手段と、
前記訪問済ノード記憶手段を参照して、前記受信ノードが訪問済となるか、前記経路決定手段において新たな探索ノードが決定できなくなった時点で、前記経路記憶手段に格納された経路を出力する経路出力手段と、
を有することを特徴とするL S P経路計算装置。
【請求項５】
前記要求取得手段で取得した前記トポロジ情報から前記L S P要求帯域に満たない残余帯域を持つリンクを削除した経路を、リンク削除済記憶手段に格納するリンク削除手段を更に有し、
前記最小残余帯域計算手段は、
前記リンク削除済記憶手段に格納された経路上のリンクから探索ノードと該探索ノードに隣接する隣接ノードを探索する、
請求項４ 記載のL S P経路計算装置。
【請求項６】
前記ホップ数計算手段は、
前記探索ノードが受信ノードである場合は、ホップ数を１とする、
請求項４ 記載のL S P経路計算装置。
【請求項７】
コンピュータを、請求項４乃至６ 記載のL S P経路計算装置として機能させることを
特徴とするL S P経路計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、LSP（Label Switched Path）経路計算方法及び装置及びプログラムに係り、特に、RSVP-TE(Resource Reservation Signaling Protocol for Traffic Engineering)が動作するMPLS(Multi Protocol Label Switching)ネットワークにおいて、ホップ数を抑えつつ、より多くのLSPを収容するように経路を求めるために使用されるＬＳＰ経路計算方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
図９に示すように、RSVP-TEが動作しているMPLSネットワークにおいて、トポロジ情報収集機構によって集められたトポロジ情報と、送信伝送装置、受信伝送装置、必要帯域などのLSP要求を受け付けてLSP経路を計算し、その計算結果を経路設定機構に出力するLSP経路計算装置が用いられている。
【０００３】
このようなLSP経路計算装置において、従来技術であるダイクストラ経路計算方法が用いられている。
【０００４】
このダイクストラ経路計算方法は、少ない計算時間で、マルチキャスト経路とユニキャスト経路の区別なく、送信ノードから受信ノードまでのリンクに付与されたリンクコストの合計が最小になるような経路を計算することができる（例えば、非特許文献１参照）。
【０００５】
しかし、将来発生する予測不可能なLSP要求を、より多く収容することを考えると、既存のダイクストラ経路計算方法では、リンクコストが小さいリンクが優先的に使われてしまい、その回線がボトルネックリンクとなってしまう。それにより、それ以後、他のLSPの収容が困難になってしまう。
【非特許文献１】WIDE 2002年インターネットアーキテクチャ第６回講義資料  http://www.soi.wide.ad.jp/class/20020022/materials_for_student/06/na-06.pdf 10ページ、11ページ
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記の従来の技術では、入力されたトポロジ情報に対するLSP要求によって、少ない計算時間で、マルチキャスト経路とユニキャスト経路の区別なく、送信ノードから受信ノードまでのリンクコストを最小にするLSP経路を計算することができる。
【０００７】
しかし、リンクコストが小さいリンクを優先的に使用するため、ボトルネックリンクが発生しやすく、多くのLSPを収容することができないという問題がある。
【０００８】
本発明は、上記の点に鑑みなされたもので、上記の従来技術と同等の計算時間で、マルチキャスト経路とユニキャスト経路の区別なく、将来発生するLSP要求のために残余帯域をより多く残し、かつ、全体の仕様帯域を抑えたLSP経路計算が可能なＬＳＰ経路計算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１１】
本発明（ 請求項１） は、R S V P - T Eが動作するM P L S伝送装置で構成されたネットワークにおいて、L S P経路を計算するL S P経路計算方法であって、
要求取得手段が、各ノードの接続関係を表したトポロジ情報及び、送信ノードと受信ノード（マルチキャストの場合は複数） 及び、L S P要求帯域を受け付け、該送信ノードを最初の探索ノードとして訪問済記憶手段に格納する要求取得ステップと、
最小残余帯域計算手段が、トポロジ情報に含まれる経路上のリンクから送信ノードに隣接する隣接ノードを探索し、該送信ノードから隣接ノードまでの経路上のリンクにおける残余帯域の中で最小の残余帯域を第１の最小残余帯域とする最小残余帯域計算ステップと、
ホップ数計算手段が、探索ノード経由の経路における第１のホップ数を計算するホップ
数計算ステップと、
判定手段が、記憶手段に隣接ノードに対して他の経路における第２ の最小残余帯域が計算されて格納されていない場合は、第１の最小残余帯域と第１のホップ数を記憶手段に格納し、記憶手段に隣接ノードに対して他の経路における第２の最小残余帯域が計算されて
格納されている場合は、第１の最小残余帯域と比較し、該第１の最小残余帯域の方が大きい場合は、該第１の最小残余帯域、第１のホップ数、経路を該記憶手段に格納し、該最小残余帯域が等しい場合は、該隣接ノードに対する他の経路におけるホップ数と比較し、該第１のホップ数の方が小さい場合は、該第１の最小残余帯域、該第１のホップ数、経路を
該記憶手段に格納する判定ステップと、
経路決定手段が、訪問済ノード記憶手段を参照して、まだ探索ノードとなっていないノードの中から記憶手段を参照して、経路上のリンクでホップ数が最小のノードを探索ノードとし、ホップ数が最小のノードが複数ある場合には、最小残余帯域が最大のノードを探索ノードとし、該探索ノードを訪問済ノード記憶手段に格納すると共に、該探索ノードを経路記憶手段に格納する経路決定ステップと、
訪問済ノード記憶手段を参照して、受信ノードが訪問済となるか、経路決定ステップにおいて新たな探索ノードが決定できなくなるまで、決定された探索ノードを用いて最小残余帯域計算ステップ以降の処理を繰り返し、
経路出力手段が、経路記憶手段に格納された経路を出力する経路出力ステップと、を行う。
【００１２】
また、本発明（ 請求項２） は、請求項１において、リンク削除手段が、要求取得ステップで取得したトポロジ情報からL S P要求帯域に満たない残余帯域を持つリンクを削除した経路を、リンク削除済記憶手段に格納するリンク削除ステップを更に行い、
最小残余帯域計算ステップは、リンク削除済記憶手段に格納された経路上のリンクから探索ノードと該探索ノードに隣接する隣接ノードを探索する。
【００１３】
また、本発明（ 請求項３）は、請求項１のホップ数計算ステップにおいて、
探索ノードが受信ノードである場合は、ホップ数を１ とする。
【００１４】
図２は、本発明の原理構成図である。
【００１６】
本発明（ 請求項４） は、R S V P - T Eが動作するM P L S伝送装置で構成されたネットワークにおいて、L S P経路を計算するL S P経路計算装置であって、
各ノードの接続関係を表したトポロジ情報及び、送信ノードと受信ノード（ マルチキャストの場合は複数） 及び、L S P要求帯域を受け付け、該送信ノードを最初の探索ノードとして訪問済記憶手段に格納する要求取得手段と、
トポロジ情報に含まれる経路上のリンクから送信ノードに隣接する隣接ノードを探索し、該送信ノードから該隣接ノードまでの経路上のリンクにおける残余帯域の中で最小の残余帯域を第１の最小残余帯域とする最小残余帯域計算手段と、
探索ノード経由の経路における第１のホップ数を計算するホップ数計算手段と、
記憶手段に隣接ノードに対して他の経路における第２の最小残余帯域が計算されて格納されていない場合は、第１の最小残余帯域と第１のホップ数を記憶手段に格納し、記憶手段に隣接ノードに対して他の経路における第２の最小残余帯域が計算されて格納されている場合は、第１の最小残余帯域と比較し、該第１の最小残余帯域の方が大きい場合は、該第１の最小残余帯域、第１のホップ数、経路を該記憶手段に格納し、該最小残余帯域が等しい場合は、該隣接ノードに対する他の経路におけるホップ数と比較し、該第１のホップ数の方が小さい場合は、該第１の最小残余帯域、該第１のホップ数、経路を該記憶手段に格納する判定手段と、
訪問済ノード記憶手段を参照して、まだ探索ノードとなっていないノードの中から経路上のリンクで、記憶手段を参照してホップ数が最小のノードを探索ノードとし、ホップ数が最小のノードが複数ある場合には、記憶手段を参照して最小残余帯域が最大のノードを探索ノードとし、該探索ノードを訪問済ノード記憶手段に格納すると共に、該探索ノードを経路記憶手段に格納する経路決定手段と、
訪問済ノード記憶手段を参照して、受信ノードが訪問済となるか、経路決定手段において新たな探索ノードが決定できなくなった時点で、経路記憶手段に格納された経路を出力する経路出力手段と、を有する。
【００１７】
また、本発明（ 請求項５）は、請求項４ において、要求取得手段で取得したトポロジ情報からL S P要求帯域に満たない残余帯域を持つリンクを削除した経路を、リンク削除済記憶手段に格納するリンク削除手段を更に有し、
最小残余帯域計算手段は、
リンク削除済記憶手段に格納された経路上のリンクから探索ノードと該探索ノードに隣接する隣接ノードを探索する。
【００１８】
また、本発明（ 請求項６）は、請求項４のホップ数計算手段は、
探索ノードが受信ノードである場合は、ホップ数を１ とする。
【００１９】
本発明（ 請求項７）は、コンピュータを、請求項４乃至６記載のL S P経路計算装置として機能させるL S P経路計算プログラムである。
【発明の効果】
【００２０】
上記のように本発明では、最小残余帯域が最大になる経路を計算し、複数ある場合はホップ数が最小の経路を導出する。また、ホップ数が最小となるLSP経路と最小より１ホップ大きいLSP経路の中から、最小残余帯域が最大の経路を導出する。また、その計算時間は、既存のダイクストラ経路計算方法と同等の計算時間であり、マルチキャスト経路とユニキャスト経路を区別することがなく導出することができる。
【００２１】
これにより、将来発生する予測不可能なLSPのために多くの残余帯域を残すため、ホップ数と最小残余帯域を考慮した経路を計算することが可能となる。
【発明を実施するための最良の形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
［第１の実施の形態］
最初に本実施の形態におけるLSP経路計算装置について説明する。
【００２４】
図３は、本発明の第１の実施の形態における動作の概要を示すフローチャートである。
【００２５】
LSP経路計算装置は、経路の接続関係を表したトポロジ情報を取得し、次に、送信ノード、受信ノード、要求帯域を記載したLSP要求を受け付ける。
【００２６】
次に、各パラメータの初期化を行い、送信ノードを探索ノードとする。残余帯域が要求帯域に満たないリンクをトポロジ情報から削除し、LSPの設定により、オーバーフローが発生しないようにする。
【００２７】
探索ノードに隣接するノードを探索し（ステップ１０）、探索ノード経由の経路における最小残余帯域を計算する。ここで、最小残余帯域とは、送信ノードからあるノードまでの経路上のリンクにおける確保可能な帯域（残余帯域）が最小のものをいう。具体的には、
Ｒ（ｕ）＝min{R(v),ReBw(v,u)-bw}
により求める。ここでｕは隣接ノード、ｖは探索ノード、Ｒ（ｖ）はｖにおける最小残余帯域Ｒ（ｖ）（但し、ｖが送信ノードのときは十分大きな値とする）、bwはLSPの要求帯域、ReBw(v,u)はｖからuへのリンクの残余帯域であり、minは｛｝内の値の中で最も最小値を求める演算子を意味する。
【００２８】
次に、探索ノード経由の経路におけるホップ数を計算する。このとき、探索ノードが受信ノードのときは、ホップ数を“１”とすることで、マルチキャスト経路のときのトータルホップ数を小さくすることができる（A. Shaikh, K. Shin, “Destination-Driven Routing for Low-Cost Multicast”, IEEE Journal of Selected Areas in Communications, vol. 15, no.3, pp.373-381, 1997参照）。
【００２９】
その隣接ノードに対して、他の経路における最小残余帯域が計算されている場合は、先程計算した探索ノード経由の最小残余帯域と比較する。その結果、探索ノード経由の最小残余帯域の方が大きい場合、探索ノード経由の最小残余帯域、ホップ数、経路をその隣接ノードのために保存する。
【００３０】
ここで、最小残余帯域が等しい場合、ホップ数を比較し、探索ノード経由のホップ数の方が小さい場合、探索ノード経由の最小残余帯域、ホップ数、経路をその隣接ノードのために保存する。
【００３１】
次に、訪問済でないノード中からホップ数が最小ノードを探索ノードとして決定する。また、ホップ数が最小のノードが複数ある場合は、その中から最小残余帯域が最大のノードを探索ノードとして決定する（ステップ２ ０ ） 。
【００３２】
さらに、その探索ノードを訪問済ノードとする。
【００３３】
LSP経路が完成するか、探索ノードが更新されなくなるまで、ステップ１０まで戻り、上記の手順を繰り返し実行する。
【００４７】
図４ は、本発明の第１ の実施の形態における経路計算装置の構成を示す。
【００４８】
同図に示す経路計算装置は、トポロジ情報入力部１０１、トポロジ情報・残余帯域記憶部１０２、L S P要求入力部１０３、L S P要求記憶部１０４、初期設定部１１０、帯域不足リンク削除部１１１、ループ条件判定部１１２、未訪問ノード取得部１１３、隣接ノード判定部１１４、最小残余帯域算出部１１５、ホップ数算出部１１６、最大最小残余帯域−最小ホップ数判定部Ａ １１７、最小残余帯域・ホップ数・経路管理部１１８、最小ホップ数− 最大最小残余帯域判定部１１９、最大最小残余帯域−最小ホップ管理部１２０、訪問済ノード管理部１２１、リンク削除済みトポロジ情報記憶部１２２、訪問済ノード記憶部１２３、経路記憶部１２４、経路出力部１２５、最小残余帯域記憶部１２６、ホップ数記憶部１２７、最大最小残余帯域−最小ホップ数ノード記憶部１２８から構成される。
【００４９】
上記のうち、トポロジ情報入力部１０１、LSP要求入力部１０３を分けて記載しているが、これらは１つのキーボード装置やマウス等のポインティングデバイスとしてもよい。
【００５０】
また、トポロジ情報・残余帯域記憶部１０２、LSP要求記憶部１０４、リンク削除済みトポロジ情報記憶部１２２、訪問済ノード記憶部１２３、経路記憶部１２４、最小残余帯域記憶部１２６、ホップ数記憶部１２７、最大最小残余帯域−最小ホップ数ノード記憶部１２８は、ディスク装置等の記憶媒体である。
【００５１】
また、トポロジ情報入力部１０１、トポロジ情報・残余帯域記憶部１０２、LSP要求入力部１０３、LSP要求記憶部１０４については、当該経路計算装置本体に含めずに、外部に設けられていてもよい。
【００５２】
トポロジ情報入力部１０１は、ネットワークの接続関係、各リンクの残余帯域の入力を処理し、トポロジ情報・残余帯域記憶部１０２に保存する。
【００５３】
トポロジ情報・残余帯域記憶部１０２は、ネットワークの接続関係、各リンクの残余帯域を保存する。
【００５４】
LSP要求入力部１０３は、LSP要求の入力を処理し、LSP要求記憶部１０４に保存する。
【００５５】
LSP要求記憶部１０４は、送信ノード、受信ノード、要求帯域の情報を保存する。
【００５６】
初期設定部１１０は、トポロジ情報・残余帯域記憶部１０２、LSP要求記憶部１０４以外の各記憶部を初期化する。訪問済ノード記憶部１２３、経路記憶部１２４、ホップ数記憶部１２７は全てゼロに初期化し、最小残余帯域記憶部１２６は無限の値で初期化する。さらに、送信ノードを探索ノードとする。
【００５７】
帯域不足リンク削除部１１１は、トポロジ情報・残余帯域記憶部１０２からリンクを取り出し、要求帯域より大きいリンクをリンク削除済みトポロジ情報記憶部１２２に格納する。
【００５８】
ループ条件判定部１１２は、経路が完成しておらず、最大最小残余帯域−最小ホップ管理部１２０で探索ノードが更新されているかどうかを判定し、繰り返しの実行の終了判定を行う。具体的には、探索ノードが更新されなくなった時点、または、経路が完成した時点で繰り返し実行を終了する。
【００５９】
未訪問ノード取得部１１３は、リンク削除済みトポロジ情報記憶部１２２と訪問済ノード記憶部１２３に記憶されているノード情報を元に未訪問ノードを取得する。
【００６０】
隣接ノード判定部１１４は、未訪問ノード取得部１１３で取得されたノードが、探索ノードと隣接しているかどうかをリンク削除済みトポロジ情報記憶部１２２の接続関係情報を元に判定する。
【００６１】
最小残余帯域算出部１１５は、探索ノードと隣接しているノードについて、探索ノード経由の最小残余帯域を算出する。
【００６２】
ホップ数算出部１１６は、探索ノードと隣接しているノードについて、探索ノード経由のホップ数を算出する。
【００６３】
最大最小残余帯域−最小ホップ数判定部Ａ１１７は、最小残余帯域算出部１１５で算出された最小残余帯域と、最小残余帯域記憶部１２６に記憶されている値を比較し、算出された最小残余帯域が大きい場合、「真」を出力する。また、算出された最小残余帯域と、最小残余帯域記憶部１２６に記憶されている値が等しい場合に、ホップ数算出部１１６により算出されたホップ数とホップ数記憶部１２７に保存されているホップ数とを比較し、算出されたホップ数が小さい場合、「真」を出力する。
【００６４】
最小残余帯域・ホップ数・経路管理部１１８は、上記の最大最小残余帯域−最小ホップ数判定部Ａ１１７の判定で「真」である場合、探索ノード経由の経路を経路記憶部１２４へ、算出された最小残余帯域を最小残余帯域記憶部１２６へ、算出されたホップ数をホップ数記憶部１２７にそれぞれ保存する。
【００６５】
最小ホップ数−最大最小残余帯域判定部１１９は、上記の処理の後、未訪問ノード取得部１１３で取得されたノードの、ホップ数記憶部１２７に保存されているホップ数が最大最小残余帯域−最小ホップ数ノード記憶部１２８に保存されているホップ数より、小さいかどうかの判定を行い、小さい場合、「真」を出力する。また、ホップ数が等しい場合は、最小残余帯域を比較し、最小残余帯域が大きい場合「真」を出力する。
【００６６】
最大最小残余帯域−最小ホップ管理部１２０ は、上記の最小ホップ数−最大最小残余帯域判定部１１９における判定で、「真」である場合、判定したノードと、そのノードの最小残余帯域、ホップ数を、それぞれ最小残余帯域記憶部１２６、ホップ数記憶部１２７に保存する。
【００６７】
訪問済ノード管理部１２１は、最大最小残余帯域−最小ホップ数ノード記憶部１２８に保存されているノードを探索済みノードとして、最大最小残余帯域−最小ホップ数ノード記憶部１２８をリセットする。また、訪問済ノード記憶部１２３に保存する。
【００６８】
経路出力部１２５は、ループ条件判定部１１２によってループが終了したと判断された場合、経路記憶部１２４に保存されている経路から不要な経路を削除して、経路を出力する。
【００６９】
リンク削除済みトポロジ情報記憶部１２２は、残余帯域が要求帯域を満たさないリンクを削除したネットワークの接続関係、リンク、ノード一覧を記憶する。
【００７０】
訪問済ノード記憶部１２３は、探索過程で訪問済となったノードを記憶する。
【００７１】
経路記憶部１２４は、送信ノードから各ノードまでの経路を記憶する。
【００７２】
最小残余帯域記憶部１２６は、最大最小残余帯域−最小ホップ数管理部１２０で確定している経路における各ノードの最小残余帯域を記憶する。
【００７３】
ホップ数記憶部１２７は、最大最小残余帯域−最小ホップ数管理部１２０で確定している経路における各ノードのホップ数を記憶する。
【００７４】
最大最小残余帯域−最小ホップ数ノード記憶部１２８は、最大最小残余帯域−最小ホップ数判定部１１７，１１９によって選ばれたノードと、そのノードの最小帯域、ホップ数を一時的に保存する。
【０１０１】
これにより、既存技術と同等の計算時間で、マルチキャスト経路とユニキャスト経路の区別なく、将来発生するLSP要求のために残余帯域をより多く残しつつ、ホップ数を少なくして全体の使用帯域を押さえたLSP経路を計算することができる。
【０１０６】
図５、図６は、本発明の第１の実施の形態における動作例を説明するための図である。
【０１０７】
図５（ａ）にある接続関係と残余帯域があるネットワークに対して、Ａを送信ノード、Ｂを受信ノード、要求帯域を１とするL S P要求の入力を受け付けたとする。
【０１０８】
送信ノードＡを訪問済とし、探索ノードとする。次に、探索ノードの隣接ノードＢ，Ｃの最小残余帯域とホップ数を計算する。ノードＢの最小残余帯域は“５”、ホップ数は“１”、ノードＣの最小残余帯域は“０”、ホップ数は“１”となる。
【０１０９】
訪問済ノードでないノードの中からホップ数が最小で、最小残余帯域が最大となるノー
ドＢを訪問済とし探索ノードとする（ 図５（ｂ））。
【０１１０】
探索ノードの訪問済ノードを除く隣接ノードＤの最小残余帯域とホップ数を計算し、最小残余帯域を“５”、ホップ数“２”とする（図５（ｃ））。
【０１１１】
訪問済でないノード中から、ホップ数が最小となるノードＣ訪問済とし、訪問済ノード記憶部１２３に格納し、探索ノードとする。
【０１１２】
探索ノードの訪問済ノードを除く隣接ノードＤ，Ｅの最小残余帯域とホップ数を計算する。このとき、ノードＤの最小残余帯域とホップ数は既に計算されているため、計算されている値と探索ノード経由の値を比較する。最小残余帯域が“５”と“０”で、既に計算されている値の方が大きいため、ノードＤの最小残余帯域は“５”、ホップ数は“２”のままとする。ノードＥの最小残余帯域は“０”、ホップ数は“２”となる（図５（ ｄ ）） 。
【０１１３】
訪問済ノードでないノードの中から、ホップ数が最小となるノードＤを訪問済とし、探索ノードとする。
【０１１４】
探索ノードの訪問済ノードを除く隣接ノードＥの最小残余帯域とホップ数を計算する。ノードＥは既に計算されているが、探索ノード経由の最小残余帯域の方が大きいため、探索ノード経由の最小残余帯域とホップ数を保存する（図６（ｅ））。
【０１１５】
訪問済ノードでないノードの中から、ホップ数が少ないノードＥ を訪問済とし、探索ノードとする（ 図６（ｆ））。
【０１１６】
受信ノードが訪問済ノードとなるため、不要な経路を削除し、残余帯域を更新して、要求L S Pに対応する経路を出力する（ 図６（ｇ））。
【０１１７】
この動作により、最小ホップ数よりも１ホップ大きいが、最小残余帯域が最小ホップの経路（Ａ，Ｃ，Ｅを通る経路）よりも優れている経路（Ａ，Ｂ，Ｄ，Ｅを通る経路）が導き出されることとなる。
【０１２３】
図７、図８は、本発明の第１の実施の形態における動作のフローチャートである。
【０１２４】
ステップ２０１）  最初に初期化設定部１１０において、各記憶部について初期化を行う。
【０１２５】
訪問済ノード記憶部１２３の訪問済のノードの集合をＵとして、Ｕを空集合として初期化する。
【０１２６】
Eを、ネットワーク上の全リンク集合とし、経路記憶部１２４に全リンクを入れて初期化する。
【０１２７】
R(v)は、ノードｖにおける最小残余帯域を表し、全ノードの最小残余帯域を無限の値で初期化する（最小残余帯域記憶部１２６に無限の値を設定する）。
【０１２８】
H(v)をノードvにおけるホップ数を表し、全ノードのホップ数をゼロで初期化する（ホップ数記憶部１２７を０とする）。
【０１２９】
終了条件を表す変数Flagを定義し、ゼロで初期化する（ループ終了条件判定部１１２に０を設定する）。
【０１３０】
探索ノードをｖとし、送信ノード（ｓ）で初期化する。
【０１３１】
ステップ２０２）  帯域不足リンク削除部１１１において、上記のＥ(全リンク集合)から、トポロジ情報・残余帯域記憶部１０２及びLSP要求記憶部１０４から取得した要求LSPの要求帯域（ｂｗ）より残余帯域が小さいリンクを取り除き、E’というリンク集合をリンク削除済みトポロジ情報記憶部１２２に格納する。
【０１３２】
ステップ２０３）  ループ条件判定部１１２において、最大最小残余帯域−最小ホップ管理部１２０を参照して、受信ノードまでの経路が完成してなく（つまり、受信ノードが一つでも訪問済ノードとなっていない）、Flag==0の間、以下のステップを繰り返し実行する。
【０１３３】
ステップ２０４）  最小残余帯域記憶部１２６に対して、訪問済ノードでないノードを持つ最小残余帯域の中で最大となる値を保持するためにｄという変数を定義し、ゼロを代入する（ｄ＝０）。
【０１３４】
また、ホップ数記憶部１２７に対して、訪問済ノードでないホップ数の中で最小となる値を保持するためにｅという変数を定義し、無限値を代入する（ｅ＝∞）。また、ループ条件判定部１１２のFlagを１とする。
【０１３５】
ステップ２０５）  訪問済でない全てのuに対して以降の処理を実行する。
【０１３６】
ステップ２０６）  隣接ノード判定部１１４において、ｖとuがE’にあるリンクで接続されている（隣接している）かを判定する。隣接している場合は、ステップ２０７に移行し、隣接していない場合はステップ２１１に移行する。
【０１３７】
ステップ２０７）  隣接している場合は、最小残余帯域算出部１１５において、ｖからuへのリンクの残余帯域（ReBw(ｖ→ｕ)）から、bwを引いた値を求め、その値と最小残余帯域記憶部１２６のR(v)と比較し、小さい方をａとし、最大最小残余帯域−最小ホップ数ノード記憶部１２８に格納する。
【０１３８】
ステップ２０８）  ホップ数算出部１１６は、ｖが受信ノードの場合は、ホップ数を１として、ｂに代入する（ｂ＝１）。受信ノードではない場合は、探索ノードのホップ数b=H(v)+1として最大最小残余帯域−最小ホップ数ノード記憶部１２８に格納する。
【０１３９】
ステップ２０９）  最大最小残余帯域−最小ホップ数判定部Ａ１１７は、最小残余帯域記憶部１２６を参照して、ａが最小残余帯域記憶部１２６のノードｕの既に計算されている最小残余帯域より大きいか、ノードｕの最小残余帯域がまだ計算されていない（つまり、無限の値が入ったまま）、もしくは、ａとノードｕの最小残余帯域が等しく、かつ、ｂがホップ数記憶部１２７のｕのホップ数より小さいかの判定を行う。そうである場合はステップ２１０に移行し、そうでない場合は、ステップ２１１に移行する。
【０１４０】
ステップ２１０）  上記のステップ１０９において、Ｙｅｓ「真」である場合は、最小残余帯域・ホップ数・経路管理部１１８は、ｕの最小残余帯域をａとして最小残余帯域記憶部１２６に、ホップ数をｂとしてホップ数記憶部１２７に保存する。また、ｕまでの経路としてｖ経由の経路を経路記憶部１２４に保存する。
【０１４１】
ステップ２１１）最小ホップ数−最大最小残余帯域判定部１１９は、最大最小残余帯域−最小ホップ数ノード記憶部１２８を参照して、ｕのホップ数がｅよりも大きいか、も
しくは、ｕのホップ数が等しく、最小残余帯域がｄよりも大きいかの判定を行う。
【０１４２】
ステップ２１２）  最大最小残余帯域−最小ホップ管理部１２０は、上記のステップ２１１の判定がＹｅｓ「真」である場合は、最小残余帯域記憶部１２６のｄにｕの最小残余帯域、ホップ数記憶部１２７のｅにｕのホップ数、経路記憶部１２４のｆにｕを代入する。
【０１４３】
ステップ２１３）  上記の処理を全てのｕに対して実行する。
【０１４４】
ステップ２１４）  その後、訪問済ノード管理部１２１は、ｖにｆを代入し、ｖを訪問済ノードとし、訪問済ノード記憶部１２３に設定する（つまり、ｖをＵに代入する）。
【０１４５】
ステップ２１５）  ここまでの処理を、受信ノードまでの経路が完成しておらず、（未訪問ノード取得部１１３が、訪問済ノード記憶部１２３を参照して、受信ノードが当該訪問済ノード記憶部１２３に設定されていない場合），Flag==0の間、繰り返し実行する。
【０１４６】
ステップ２１６）  上記の繰り返し実行が終了後、経路出力部１２５は、経路記憶部１２４から不要な経路を削除し、送信ノードから受信ノードまでの経路を出力する。このとき、経路が完成していない場合は、「解なし」として出力する。
【０１４７】
上記の第２の実施の形態によれば、ホップ数が最小（ユニキャスト経路の場合は最小ホップ経路、マルチキャスト経路の場合は、最小ホップ木経路）となるLSP経路と最小より１ホップ大きいLSP経路の中から、最小残余帯域が最大の経路を導出することができる。
【０１４８】
なお、上記の第１・第２の実施の形態の動作をプログラムとして構築し、LSP経路計算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１４９】
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。
【０１５０】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１５１】
本発明は、RSVP-TEが動作するネットワークに適用可能である。
【図面の簡単な説明】
【０１５２】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態における概要動作のフローチャートである。
【図４】本発明の第１の実施の形態における装置構成図である。
【図５】本発明の第１の実施の形態における動作例を説明するための図（その１）である。
【図６】本発明の第１の実施の形態における動作例を説明するための図（その２）である。
【図７】本発明の第１の実施の形態における概要動作のフローチャート（その1）である。
【図８】本発明の第１の実施の形態における概要動作のフローチャート（その２）である。
【図９】L S P経路計算装置を説明するための図である。
【符号の説明】
【０１５３】
１ ０   要求取得手段
３ ０   経路決定手段
１ ０ １   トポロジ情報入力部
１ ０ ２   トポロジ情報・残余帯域記憶部
１ ０ ３   L S P要求入力部
１ ０ ４   L S P要求記憶部
１ １ ０   初期設定部
１ １ １   リンク削除手段、帯域不足リンク削除部
１ １ ２   ループ条件判定部
１ １ ３   未訪問ノード取得部
１ １ ４   隣接ノード判定部
１ １ ５   最小残余帯域算出部
１ １ ６   ホップ数算出部
１ １ ７   最大最小残余帯域− 最小ホップ数判定部Ａ
１ １ ８   最小残余帯域・ホップ数・経路管理部
１ １ ９   最小ホップ数− 最大最小残余帯域判定部
１ ２ ０   最大最小残余帯域−最小ホップ管理部
１ ２ １   訪問済ノード管理部
１ ２ ２   リンク削除済記憶手段、リンク削除済トポロジ情報記憶部
１ ２ ３   訪問済ノード記憶手段、訪問済ノード記憶部
１ ２ ４   経路記憶手段、経路記憶部
１ ２ ５   経路出力手段、経路出力部
１ ２ ６   最小残余帯域記憶部
１ ２ ７   ホップ数記憶部
１ ２ ８   最大最小残余帯域−最小ホップ数ノード記憶部
【図１】
0004436307.tif 000002
【図２】
0004436307.tif 000003
【図３】
0004436307.tif 000004
【図４】
0004436307.tif 000005
【図５】
0004436307.tif 000006
【図６】
0004436307.tif 000007
【図７】
0004436307.tif 000008
【図８】
0004436307.tif 000009
【図９】
0004436307.tif 000010