(57)【特許請求の範囲】
【請求項１】
ＩＰネットワークにおけるＭＰＬＳによる経路設定に当り、ネットワークの入口のノードからネットワークの出口のノードまでをダイキストラアルゴリズム計算による最小メトリックのＭＰＬＳ経路を１本張り、該１本目の通過ノードの位置情報をラベルマッピングメッセージに書き込み、該位置情報を入口ノードに通知し、前記１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算し、必要帯域が取れないリンクを通過することを避け、且つ前記１本目の経路と重複をしないように２本目以降の経路を自律的に設定することを特徴とする複数経路設定方法。
【請求項２】
ＩＰネットワークにおけるＭＰＬＳによる経路設定に当り、ネットワークの入口のノードからネットワークの出口のノードまでをダイキストラアルゴリズム計算による最小メトリックのＭＰＬＳ経路を１本張り、該１本目の通過ノードの位置情報をラベルマッピングメッセージに書き込み、該位置情報を入口ノードに通知し、前記１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算し、前記１本目の経路のリンク及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書込み、各ノードに１本目の通過ノード及び必要帯域が取れないリンクの位置情報を通知し、各通過ノードでは、１本目の経路のリンク及び必要帯域が取れないリンクの位置情報を、回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算することにより、必要帯域が取れないリンクを通過することを避け、かつ、前記１本目の経路と重複をしないように２本目以降の経路を自律的に設定することを特徴とする複数経路設定方法。
【請求項３】
入口ノードと通過ノードと出口ノードからなるＩＰネットワークにおけるＭＰＬＳによる複数経路設定システムであって、
前記入口ノードは、
ネットワークの入口ノードからネットワークの出口ノードまでに張られたダイキストラアルゴリズム計算による最小メトリックの１本のＭＰＬＳ経路の通過ノードの位置情報が書き込まれたラベルマッピングメッセージを読み込んで、前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクのメトリックを、回避リンク情報を保持するデータベースに通知する手段と、
前記データベースにて、前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を算出する計算手段と、
出口ノードまでの経路情報をラベルリクエストメッセージに書き込む手段を備え、
前記通過ノードは、
到着するラベルリクエストメッセージ内にある経路情報を読み取り、この情報により次ノードを決定する手段と、
到着するラベルマッピングメッセージに自ノード位置情報を書き込んで出力する手段を備え、
必要帯域が取れないリンク通過することを避け、かつ前記１本目のＭＰＬＳ経路と重複をしないように２本目以降のＭＰＬＳ経路を自律的に設定するようにしたことを特徴とする複数経路設定システム。
【請求項４】
入口ノードと通過ノードと出口ノードからなるＩＰネットワークにおけるＭＰＬＳによる複数経路設定システムであって、
前記入口ノードは、
ネットワークの入口ノードからネットワークの出口ノードまでに張られたダイキストラアルゴリズム計算による最小メトリックの１本のＭＰＬＳ経路の通過ノードの位置情報が書き込まれたラベルマッピングメッセージを読み込んで、前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクのメトリックを、回避リンク情報を保持するデータベースに通知する手段と、
前記データベースにて、前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を算出する計算手段と、
前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書き込む手段を備え、
前記通過ノードは、
到着するラベルリクエストメッセージ内にある前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクの位置情報を読み取り、この情報を回避リンク情報を保持するデータベースに通知する手段と、
前記データベースにて、前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を算出する計算手段と、
前記１本目のＭＰＬＳ経路のリンク及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書き込む手段と、
到着するラベルマッピングメッセージに自ノード位置情報を書き込んで出力する手段を備え、
必要帯域が取れないリンク通過することを避け、かつ前記１本目のＭＰＬＳ経路と重複をしないように２本目以降のＭＰＬＳ経路を自律的に設定するようにしたことを特徴とする複数経路設定システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、IPネットワークにおけるMPLS（ multiprotocol label switching ）による経路設定に際し、分散型障害回復機能及び負荷分散のためのロードバランス機能を実現するために、事前に複数の経路を重複することなく設定する方法及びシステムに関するものである。
【０００２】
【従来の技術】
IPネットワークの信頼性向上のために、パケットの転送経路をシステムの障害時や、ネットワークの管理上の要求から、例えば輻輳時のトラヒック分散のために代替経路に切り替える必要がある。こうした場合に、代替経路を事前に設定する方式と、切り替え要求が発生したときに代替経路を選択する方式とがある。MPLSは、ノード間で終端されたコネクションをネットワーク層の経路情報に従って関連付け、この関連付けられたコネクションは、「ラベル」を付けて識別できるようにして、パケット中のルーティング情報にラベルを対応付け、これらのラベルに従って高速にル−ティング処理を行なうようにする。
【０００３】
このようなMPLSネットワークにおいて、分散型障害回復機能を実現する際には、障害発生を検知したノードがオンデマンドで経路の設定を行うリルーティング型復旧方式と、障害発生以前に予備経路を確立しておくプロテクション型復旧方式とが採られている。前者のリルーティング型復旧方式では、障害リンクが発生した場合に同時に大量の復旧用経路設定要求が起こり、復旧用の代替経路同士の衝突を避ける必要がある。そこで、このような衝突を回避するために、ノード毎に復旧用経路設定の計算を行う時間をずらす策が採られるが、現実的にはトポロジー情報の更新を待つことができず、復旧用経路の早期確立が困難である。また、後者のプロテクション型復旧方式では、障害リンク通知を受け取った保守者がネットワーク全体のトポロジー情報を考慮することにより代替経路を指定して、手動で通過ノードの経路テーブルを書き換えるようにしていた。
【０００４】
【発明が解決しようとする課題】
本発明の目的は、前記プロテクション型の復旧方式を改善し、事前に複数の経路を重複せずに自律的に設定する方法及びシステムを提供することにある。
【０００５】
【課題を解決するための手段】
本発明によれば、IPネットワークにおけるMPLSによる経路設定に当り、ネットワークの入口のノードからネットワークの出口のノードまでをダイキストラアルゴリズム計算による最小メトリックのMPLS経路を１本張り、該１本目の通過ノードの位置情報をラベルマッピングメッセージに書き込み、該位置情報を入口ノードに通知し、前記１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算し、必要帯域が取れないリンクを通過することを避け、且つ前記１本目の経路と重複をしないように２本目以降の経路を自律的に設定するようにする。
【０００６】
さらに本発明の他の例では、IPネットワークにおけるMPLSによる経路設定に当り、ネットワークの入口のノードからネットワークの出口のノードまでをダイキストラアルゴリズム計算による最小メトリックのMPLS経路を１本張り、該１本目の通過ノードの位置情報をラベルマッピングメッセージに書き込み、該位置情報を入口ノードに通知し、前記１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算し、前記１本目の経路のリンク及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書込み、各ノードに１本目の通過ノード及び必要帯域が取れないリンクの位置情報を通知し、各通過ノードでは、１本目の経路のリンク及び必要帯域が取れないリンクの位置情報を、回避リンク情報を保持するデータベースに通知し、該データベースでは１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、前記回避リンク情報を保持するデータベースを用いてダイキストラアルゴリズムによる最小メトリック経路を計算することにより、必要帯域が取れないリンクを通過することを避け、かつ、前記１本目の経路と重複をしないように２本目以降の経路を自律的に設定する
【０００７】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態をシステムの装置例及び方法の例につき説明する。
【０００８】
（装置例）
（１）第１実施例：明示的経路設定法
図１は、IPネットワークの入口ノードでの本装置例の概略を示す概略構成ブロック図であり、図２は、通過ノードでの本装置例の概略を示す概略構成ブロック図である。
【０００９】
図１に示す入口ノードにおける本例装置Aは、インタフェース部１０とプロセッサ部２０とから成り、インタフェース部１０は回避リンク位置情報読取部１１、転送経路テーブル１２、LSP（label  switched  path）対応テーブル１３及び明示的経路情報書込み部１４を具えており、プロセッサ部２０はOSPF（open  shortest  path  first）データベース２１、回避リンク情報を保持するデータベース２２及びダイキストラ（Dijkstra）アルゴリズム計算による最小メトリックの経路計算部２３を具えている。
【００１０】
IPネットワークにおけるMPLSによる明示的経路設定に際し、先ず、入口ノードの本装置Aでは、回避リンク位置情報読取部１１が、この装置Ａに到着して、LSP(label  switching  path)対応テーブル１３にてLSPのIDを基に検索したラベルマッピングメッセージ（label  mapping  message）及びノウティフィケーションメッセージ（notification  message）内にある回避リンク位置情報を読み取り、この情報をプロセッサ部２０における回避リンク情報を保持しているデータベース２２に送信する。次いで、このデータベース２２はOSPF（open  shortest  path  first）データベース２１を複製し、回避リンク位置情報読取部１１から受け取った情報を１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または他のどのメトリックよりも大きくした値に置き換える。次いで、ダイキストラ最小メトリック経路計算部２３にて、回避リンク情報を保持するデータベース２２からの情報を基にネットワーク状態に対応した最適な経路を算出して転送経路テーブル１２を作成する。
【００１１】
明示的経路情報書込み部１４では、ラベルリクエストメッセージ（label  request  message）に出口ノードまでの経路情報を書き込む。ラベルリクエストメッセージは転送経路テーブル１２で出口ポート番号を引き、LSP対応テーブル１３にLSPのIDと出口ポート番号を書込み、このラベルリクエストメッセージのパケットを出口ポートに出力して、次ぎのノードに転送する。
【００１２】
図２に示す通過ノードにおける本例装置Bのインターフェース部３０は、次ノードアドレス情報読取部３１と、転送経路テーブル３２と、LSP対応テーブル３３と、自ノード位置情報書込み部３４とを具えている。
【００１３】
通過ノードの本装置Bでは、通過ノードに到着するラベルリクエストメッセージ内にある明示的経路情報を次ノードアドレス情報読取部３１で読み取り、これにて次ノードを決定して、転送経路テーブル３２を作成する。ラベルマッピングメッセージはLSP対応テーブル３３でLSPのIDを認識した後、転送経路テーブル３２にラベルと出口ポートを書込む。自ノード位置情報書込み部３４ではラベルマッピングメッセージに自ノード位置情報を書込んで出口ポートに出力する。
【００１４】
（２）第２実施例：ホップ・バイ・ホップ（hop  by  hop）経路設定法
図３は、入口ノードでの本装置例を示す概略構成ブロック図であり、図４は、通過ノードでの本装置例を示す概略構成ブロック図である。これらの図において、前記図１及び図２における各構成要素と同じか、同様の機能をする部分には同じ参照番号を付して示してある。
【００１５】
ホップ・バイ・ホップ経路設定法の場合における図３に示す入口ノードにおける本例装置Aの構成は、ホップ・バイ・ホップ経路設定法の場合における図３に示す図１の場合の入口ノードの装置Aとは、インタフェース部１０の明示的経路情報書込み部１４の代わりに、回避リンク位置情報書込み部１５を用いている点が相違しているだけである。
【００１６】
IPネットワークにおけるMPLSによるホップ・バイ・ホップ経路設定に際し、先ず、この図3の入口ノードの本装置Aでは、回避リンク位置情報読取部１１が、この装置Ａに到着して、LSP対応テーブル１３にてLSPのIDを基に検索したラベルマッピングメッセージ及びノウティフィケーションメッセージの回避リンク位置情報を読み取り、この情報をプロセッサ部２０における回避リンク情報を保持しているデータベース２２に送信する。次いで、このデータベース２２はOSPFデータベース２１を複製し、回避リンク位置情報読取部１１から受け取った情報を置き換える。回避リンク情報を保持するデータベース２２からの情報を基にダイキストラ最小メトリック経路計算部２３では、ネットワーク状態に対応した最適な経路を算出して転送経路テーブル１２を作成する。
【００１７】
回避リンク位置情報書込み部１５では、先に設定した１本目の経路及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書き込む。ラベルリクエストメッセージは転送経路テーブル１２で出口ポート番号を引き、LSP対応テーブル１３にLSPのIDと出口ポート番号を書込み、メッセージパケットを出口ポートに出力する。
【００１８】
ホップ・バイ・ホップ経路設定法の場合における図４に示す通過ノードの本装置Bは、図１の入口ノードの装置Aにおけるものと同じプロセッサ部２０を具え、且つ回避リンク位置情報読取部１１、回避リンク位置情報書込み部１５、転送経路テーブル３２、LSP対応テーブル３３及び自ノード位置情報書込み部３４を含むインタフェース部３０も具えている。
【００１９】
図４の通過ノードにおける装置Bでは、この通過ノードに到着するラベルリクエストメッセージ及びノウティフィケーションメッセージ内にある回避リンク位置情報を回避リンク位置情報読取部１１で読み取り、回避リンク情報を保持するデータベース２２に転送する。回避リンク情報を保持するデータベース２２はOSPFデータベース２１を複製し、回避リンク位置情報読み取り部１１から受け取った情報を置き換える。回避リンク情報を保持するデータベース２２からの情報を基にダイキストラ最小メトリック経路計算部２３では、ネットワーク状態に対応した最適な経路を算出して転送経路テーブル１２を作成する。
【００２０】
回避リンク位置情報書込み部１５では、１本目の経路及び必要帯域が取れないリンクの位置情報をラベルリクエストメッセージに書き込む。ラベルリクエストメッセージは転送経路テーブル３２で出口ポート番号を引き、ＬＳＰ対応テーブル３３にＬＳＰのＩＤと出口ポート番号を書込み、メッセージパケットを出口ポートに出力する。ラベルマッピングメッセージはLSP対応テーブル３３でLSPのIDを認識した後、転送経路テーブル３２にラベルと出口ポートを書込む。自ノード位置情報書込み部３４ではラベルマッピングメッセージに自ノード位置情報を書込んで出口ポートに出力する。
【００２１】
（方法例）
次ぎに、本発明による複数経路設定方法の明示的経路設定法及びホップ・バイ・ホップ経路設定法の各実施例につき説明する。
【００２２】
（１）第１実施例：明示的経路設定法
図５は、この明示的経路設定例の入口ノードでの実行手順を示すフローチャートであり、図６は、通過ノードでの実行手順を示すフローチャートである。
【００２３】
図７に示すネットワークのように、ネットワーク入口のノードでは、先ず図１の装置Aにつき述べたように、ネットワーク出口ノードまでの最小メトリック経路をダイキストラアルゴリズムにより計算し、通過ノードアドレスを明示的に指定してCR-LDPのストリクト（strict）指定でラベルリクエストメッセージにその情報を付加する。図８のようにメッセージを各通過ノードへ通知していき、途中で必要帯域を取れないリンクがある場合には、ノウティフィケーションメッセージにそのリンクの位置情報を付加してネットワークの入口ノードに通知する。入口ノードではこのように収集した必要帯域が取れないリンクメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、ダイキストラアルゴリズムによる最小メトリック経路を計算し、通過ノードアドレスを明示的に指定してラベルリクエストメッセージにその情報を付加する。メッセージを各通過ノードヘ通知していき、出口ノードまでラベルリクエストメッセージが通知できた場合には、同じ経路をラベルマッピングメッセージとして戻り、各通過ノードではIPフローとMPLSラベルの関連付けを行い、同時に通過ノードのアドレスをそのメッセージに付加して入口ノードに通知する。
【００２４】
図９のように、２本目以降の経路を設定する際は、１本目の経路のリンクと必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、ダイキストラアルゴリズムによる最小メトリック経路を計算し、１本目の経路と重複しない経路を設定する。
【００２５】
（２）第２実施例：ホップ・バイ・ホップ経路設定法
図１０は、このホップ・バイ・ホップ経路設定例の各ノードでの実行手順を示すフローチャートである。
【００２６】
図７に示すネットワークのように各ノードでは、CR-LDPのルーズ（loose）指定で隣接ノードにラベルリクエストメッセージを通知し、ホップ・バイ・ホップでダイキストラアルゴリズムによる最小メトリック経路計算を行う。メッセージを各通過ノードに通知していき、途中で必要帯域を取れないリンクがある場合には、ノウティフィケーションメッセージにそのリンクの位置情報を付加して、一つ前のノードに通知する。通知されたリンクでは必要帯域が取れないリンクメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、ダイキストラアルゴリズムによる最小メトリック経路を計算し、隣接ノードに必要帯域が取れないリンク情報を持ったラベルリクエストメッセージを通知する。図８のように出口ノードまでラベルリクエストメッセージが通知できた場合には、同じ経路をラベルマッピングメッセージとしてIPフローとMPLSラベルの関連付けを行いながら戻り、必要帯域が取れないリンク情報と通過ノードの位置情報をそのメッセージに付加して入口ノードに通知する。
【００２７】
図９のように、２本日以降の経路を設定する際は、ラベルリクエストメッセージに１本目の経路のリンクと必要帯域が取れないリンクの位置情報を付加し、隣接ノードに通知する。各ノードではラベルリクエストメッセージに付加されている、１本目の経路のリンク及び必要帯域が取れないリンクのメトリックを無限大、または、他のどのリンクメトリックよりも大きくした値に一時的に置き換えて、ダイキストラアルゴリズムによる最小メトリック経路を計算し、１本目の経路と重複しない経路を設定する。
【００２８】
【発明の効果】
以上詳述したように、本発明によれば、保守者を介すことなく自律的に複数の経路を重複することなく設定することが可能であり、特にネットワーク全体のトポロジーを把握していなくても、経路設計が可能になる。
【図面の簡単な説明】
【図１】  本発明の第１実施形態であるシステムの入口ノードの概略構成ブロック図である。
【図２】  本発明の第１実施形態であるシステムの通過ノードの概略構成ブロック図である。
【図３】  本発明の第２実施形態であるシステムの入口ノードの概略構成ブロアク図である。
【図４】  本発明の第２実施形態であるシステムの通過ノードの概略構成ブロック図である。
【図５】  本発明の第１実施形態の方法の入口ノードでの実行手順を示すフローチャートである。
【図６】  本発明の第１実施形態の方法の通過ノードでの実行手順を示すフローチャートである。
【図７】  本発明の経路設定シグナリングを説明する図である。
【図８】  本発明の経路設定シグナリングを説明する図である。
【図９】  本発明の経路設定シグナリングを説明する図である。
【図１０】  本発明の第２実施形態の方法の各ノードでの実行手順を示すフローチャートである。
【符号の説明】
Ａ  入口ノード装置
Ｂ  通過ノード装置
１０  インターフェイス部
１１  回避リンク位置情報読取部
１２  転送経路テーブル
１３  ＬＳＰ対応テーブル
１４  明示的経路情報書込み部
１５  回避リンク位置情報書込み部
２０  プロセッサ部
２１  OSPFデータベース
２２  回避リンク情報を保持するデータベース
２３  ダイキストラ最小メトリック経路計算部
３０  インタフェース部
３１  次ノードアドレス情報読取部
３２  転送経路テーブル
３３  LSP対応テーブル
３４  自ノード位置情報書込み部
【図１】
0003682237.tif 000002
【図２】
0003682237.tif 000003
【図３】
0003682237.tif 000004
【図４】
0003682237.tif 000005
【図５】
0003682237.tif 000006
【図６】
0003682237.tif 000007
【図７】
0003682237.tif 000008
【図８】
0003682237.tif 000009
【図９】
0003682237.tif 000010
【図１０】
0003682237.tif 000011