(57)【要約】【課題】  １つ以上のユーザーグループが存在するネットワークにおいて、トラフィック収容効率の改善を図りつつ、下位レイヤリンクに障害が起きた場合でも上位レイヤが確実に復旧できるようなネットワーク網を設計するための経路計算方法を提供する。【解決手段】  上位レイヤと下位レイヤが存在するネットワーク内にトラフィック転送等の機能を持ち、下位レイヤのスイッチと接続されるルーターが少なくとも２つ以上存在し、ユーザーグループが複数存在する場合の経路計算方法において、対象となるユーザーグループに属するユーザーのみの上位レイヤの所定の情報を考慮することで、その情報をもとに同じユーザーグループに属するユーザー間のみで、トラフィック収容効率がよく下位レイヤで障害が起きた場合にネットワーク内に存在する何れかのレイヤにおいて何らかの方法でその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする。【選択図】        図１
2005223522.tif 000002
【特許請求の範囲】
【請求項１】
自ネットワークより相対的に下位に位置するネットワークに収容されるコネクションレス型またはコネクション型ネットワークを上位レイヤ、自ネットワークより相対的に上位に位置するネットワークを収容するコネクション型ネットワークを下位レイヤとするとき、上位レイヤと下位レイヤが存在し、下位レイヤのスイッチと接続される上位レイヤのルーターが少なくとも２つ有するネットワークであって、当該ネットワーク内に同じグループに属するユーザーとのみトラフィックをやり取りして、他のグループに属するユーザーとはトラフィックのやり取りを行わないと定義されたユーザーグループが少なくとも１個存在するネットワークにおける、同じユーザーグループに属するユーザー間のみでパス設計を行う経路計算方法であって、
上位レイヤの所定の情報に基づき、どのノード間に下位レイヤのパスを確立するかを決定し、下位レイヤトポロジーを決定するステップ１と、
前記ステップ１で決定した下位レイヤパスに上位レイヤのパスを収容し、上位レイヤのトポロジーを決定するステップ２と、
任意の下位レイヤリンクに障害が起きた場合でも上位レイヤの接続が保たれるかどうかを下位レイヤリンクに対して調べるステップ３とを備えることを特徴とする経路計算方法。
【請求項２】
前記ユーザーグループがネットワーク内に１つのみ存在する場合に、前記ユーザーグループ内の全ユーザーにおける上位レイヤの所定の情報を収集しパス設定を行うことを特徴とする請求項１に記載の経路計算方法。
【請求項３】
前記下位レイヤは、波長やＴＤＭのコネクション型ネットワークを含み、
前記上位レイヤは、ＭＰＬＳのコネクション型ネットワークを含むことを特徴とする請求項１または請求項２に記載の経路計算方法。
【請求項４】
前記下位レイヤは、波長やＴＤＭのコネクション型ネットワークを含み、
前記上位レイヤは、パケットネットワークのコネクションレス型ネットワークを含むことを特徴とする請求項１または請求項２に記載の経路計算方法。
【請求項５】
下位レイヤで障害が起きた場合に、上位と下位の両方のレイヤにおいて、それぞれのレイヤで可能な復旧方法によってその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする請求項１ないし請求項４のいずれか１項に記載の経路計算方法。
【請求項６】
下位レイヤで障害が起きた場合に、上位レイヤのみで可能な復旧方法によってその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする請求項１ないし請求項４のいずれか１項に記載の経路計算方法。
【請求項７】
前記上位レイヤの情報は、トラフィックマトリクスであることを特徴とする請求項１ないし請求項６のいずれか１項に記載の経路計算方法。
【請求項８】
前記上位レイヤの情報は、将来のトラフィック需要予測であることを特徴とする請求項１ないし請求項６のいずれか１項に記載の経路計算方法。
【請求項９】
前記上位レイヤの情報は、リンクコストであり、
前記リンクコストの基準となる条件として、上位レイヤのパスが同じ下位レイヤリンクを用いないように考慮してパス設計を行うことを特徴とする請求項１ないし請求項６のいずれか１項に記載の経路計算方法。
【請求項１０】
前記ステップ３において、任意の下位レイヤリンクに障害が起きた場合でも上位レイヤの接続が保たれるかどうかを下位レイヤリンクに対して調べる際に、全ての下位レイヤ物理リンクに対して行うことを特徴とする請求項１ないし請求項９のいずれか１項に記載の経路計算方法。
【請求項１１】
前記ステップ３において、任意の下位レイヤリンクに障害が起きた場合でも上位レイヤの接続が保たれるかどうかを下位レイヤリンクに対して調べる際に、特定の物理リンクに対してのみ行うことを特徴とする請求項１ないし請求項９のいずれか１項に記載の経路計算方法。
【請求項１２】
前記ステップ３の後に、前記ステップ１ないし前記ステップ３により設定した下位レイヤパスを基にして、再度上位レイヤのパス設計を行い、遅延が最小化するようなパス設定を行うステップ４を有することを特徴とする請求項１ないし請求項１１のいずれか１項に記載の経路計算方法。
【請求項１３】
前記請求項１ないし請求項１２のいずれか１項に記載の経路計算方法を、コンピュータに実行させるための経路計算プログラム。
【請求項１４】
自ネットワークより相対的に下位に位置するネットワークに収容されるコネクションレス型またはコネクション型ネットワークを上位レイヤ、自ネットワークより相対的に上位に位置するネットワークを収容するコネクション型ネットワークを下位レイヤとするとき、上位レイヤと下位レイヤが存在し、下位レイヤのスイッチと接続される上位レイヤのルーターが少なくとも２つ有するネットワークであって、当該ネットワーク内に同じグループに属するユーザーとのみトラフィックをやり取りして、他のグループに属するユーザーとはトラフィックのやり取りを行わないと定義されたユーザーグループが少なくとも１個存在するネットワークにおける、同じユーザーグループに属するユーザー間のみでパス設計を行う経路計算制御装置であって、
ネットワークのパス計算を行う経路計算部と、
ユーザー毎の上位レイヤ情報を記憶する上位レイヤ情報記憶部とを有し、
前記経路計算部は、前記上位レイヤ情報記憶部に記憶された上位レイヤの所定の情報に基づき、どのノード間に下位レイヤのパスを確立するかを決定し、下位レイヤトポロジーを決定する手段１と、
前記手段１で決定した下位レイヤパスに上位レイヤのパスを収容し、上位レイヤのトポロジーを決定する手段２と、
任意の下位レイヤリンクに障害が起きた場合でも上位レイヤの接続が保たれるかどうかを下位レイヤリンクに対して調べる手段３とを備えることを特徴とする経路計算制御装置。
【請求項１５】
前記上位レイヤの情報は、トラフィックマトリクスであることを特徴とする請求項１４に記載の経路計算制御装置。
【請求項１６】
前記上位レイヤの情報は、将来のトラフィック需要予測であることを特徴とする請求項１４に記載の経路計算制御装置。
【請求項１７】
前記上位レイヤの情報は、リンクコストであり、
前記リンクコストの基準となる条件として、上位レイヤのパスが同じ下位レイヤリンクを用いないように考慮してパス設計を行うことを特徴とする請求項１４に記載の経路計算制御装置。
【請求項１８】
前記経路計算部は、前記手段１ないし前記手段３により設定した下位レイヤパスを基にして、再度上位レイヤのパス設計を行い、遅延が最小化するようなパス設定を行う手段４を有することを特徴とする請求項１４ないし請求項１７のいずれか１項に記載の経路計算制御装置。
【請求項１９】
前記経路計算制御装置は、ネットワーク内の各ルーターと接続され、ネットワーク内の各ノードを一括して集中的に管理・制御することを特徴とする請求項１４ないし請求項１８のいずれか１項に記載の経路計算制御装置。
【請求項２０】
前記経路計算制御装置は、ネットワーク内の各ルーター内に配置され、ネットワーク内の各ノードに付属してノードを管理・制御することを特徴とする請求項１４ないし請求項１８のいずれか１項に記載の経路計算制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計算方法、経路計算制御装置および経路計算プログラムに係わり、特に、ＭＰＬＳ（Multi Protocol Label Switchinｇ：マルチプロトコルラベルスイッチング）やＡＴＭ（Asynchronous Transfer Mode：非同期転送モード）などのパケットネットワークと、ＴＤＭ（Time Division Multiplexing：時分割多重）やＷＤＭ（Wavelength Division Multiplexing：波長分割多重）の光ネットワークの両方を考慮した経路計算方法に関する。
【背景技術】
【０００２】
近年、ＩＰトラフィックが爆発的に増大している。多数のルーターを経由してトラフィックを運ぶ従来のコネクションレス型の方式では、増大するＩＰトラフィックを転送するコアネットワークの設備コストが増加してしまうという問題がある。
その為、波長やＴＤＭといった、コネクション型のネットワークでＩＰ（レイヤ３）やＥｔｈｅｒｎｅｔ（レイヤ２）のトラフィックをパススルーすることで、トラフィックの収容効率を上げ、その結果ネットワークの経済化を実現する方法が登場した。
このような方法で、大容量ＩＰトラフィック・ネットワークサービス経済化を実現するコアネットワークも提案されている（例えば、非特許文献１参照）。
多数のルーターを経由してトラフィックを運ぶ従来のコネクションレス型のネットワークに対して、コネクションを張ってパススルーを行うコネクション型のネットワークでは、トラフィックを流すのに先立ってパスを確立する必要があり、そのための経路を事前に計算しなければならない。
限りある帯域を効率良く利用して膨大な情報に対処できるような経路を設定するために、ネットワーク内のサーバー又はルーターには、ＣＳＰＦ（Constrained Shortest Path First）機能が用意されている。
【０００３】
ＣＳＰＦ機能とは、シグナリング情報をやり取りするモジュールなど外部からの要求に基づいて、制約を満たすパスの経路を計算し、外部に対して経路を回答する機能、つまり制約付き最短経路計算機能である。
これまでに、非常に多くのＣＳＰＦアルゴリズムが提案されてきた。それぞれのＣＳＰＦアルゴリズムは機能・性能が異なるため、要求されている制約によって適切なものを選ぶ必要がある。
使用するＣＳＰＦアルゴリズムが異なると、例えば、ネットワークにかかるコストやトラフィック収容効率、エンドユーザーに対する信頼性など様々なものが影響を受ける。つまり、適切なＣＳＰＦアルゴリズムを用いることで、ネットワーク構築コストが下げられるなど、目的に叶ったパスの設計が可能となる。
ＣＳＰＦアルゴリズムは設定するパスの属性・制約によってアルゴリズムが異なり、ＩＰネットワーク、光ネットワークなど、レイヤが異なれば最適なアルゴリズムも異なる。
光ネットワークにおいては、経路計算アルゴリズムに加え、波長割り当てアルゴリズムも必要となる。
代表的な経路計算アルゴリズムとしては、k-shortest path heuristicや線形計画法、がある（例えば、非特許文献２参照）。
【０００４】
従来のＣＳＰＦアルゴリズムは、ＩＰネットワークのみ、光ネットワークのみといった１つのレイヤに閉じたものであり、１つのレイヤのみを考慮して経路計算を行っていた。
ところが、前述したようなパススルーを行って経済化を図るコアネットワークにおいては、上位レイヤと下位レイヤで別々のＣＳＰＦアルゴリズムを適用し、独立に経路計算を行っていては、帯域利用効率のいいパス切り替えを行うことが出来ず、効率的なネットワークが構築出来ない。
さらに、光ネットワーク網には複数本の光ファイバが束ねて敷設されているリンクがあり、このようなリンクばかりを経路に設定してしまうと、このリンクの障害時に非常に多くの通信が中断してしまう。
そのため、上位レイヤのパスが、下位（物理）レイヤの特定のリンクに集中せず互いに重ならない経路を通過するために、２つのレイヤを相互に考慮しながら経路計算する必要がある。
このような状況から、上位レイヤと下位レイヤの両方を考慮する必要性が認識され始め、最近になり、上位レイヤと下位レイヤの両方を考慮して経路計算を行うことができるマルチレイヤ用ＣＳＰＦアルゴリズムが注目され始めた。
ここでマルチレイヤとは、回線交換ネットワークのようなコネクション型ネットワークにパケットネットワークのようなコネクションレス型ネットワークが収容されているネットワークのことを言う。
【０００５】
マルチレイヤを考慮したＣＳＰＦで代表的なものとして２つ挙げる。
（１）ＢＸＣＱ（Branch eXchange with Quality-of-service Constraint）法
上位レイヤパスと下位レイヤのトラフィック量を考慮した動的な経路制御を行うことを目的としている。
上位レイヤのパスのトラフィック情報をノード間で交換し、その情報をもとに下位レイヤパスのトポロジーを設定し、また動的に変更することで、トラフィック需要の変動に適応的なネットワーク構築が可能になる。実際の経路計算にはＢＸＣＱ法が用いられている。
このＣＳＰＦアルゴリズムは、ネットワークのトラフィック収容効率を第１に優先してパスの設定を行いたい場合に適用すると有効である（例えば、非特許文献３参照）、
（２）ＳＬＡ（Survivable Layout Algorithm）法
下位レイヤの任意のリンクに障害が起きた場合でも、上位レイヤの各ノード同士は障害が起きたリンクから影響を受けない何らかの迂回経路を予め用意することでつながりを保ち、上位レイヤネットワークの接続は保障されるようなパス設計を行うことを目的としている。
下位レイヤのリンク１本１本に対して、障害が起きた場合の上位レイヤが受ける影響を調べ、必要があれば経路の再計算を行うことで、下位レイヤの障害に対して上位レイヤのみで復旧できるようなネットワークを構築することができる。実際の経路計算にはＳＬＡ法が用いられている。
このアルゴリズムは、ネットワークに障害が起きた場合でもノード間の接続は保障されるような信頼性の高さを第１に優先してパスの設定を行いたい場合に適用すると有効である（例えば、非特許文献４参照）。
【０００６】
【非特許文献１】栗本崇，宮村崇，青木道宏，井上一郎，松浦伸昭，小島久史，漆谷重雄，”マルチレイヤサービスネットワークアーキテクチャの提案”信学技法  TECHNICAL REPORT OF IEICE,PN2003-6(2003-09).
【非特許文献２】R.Bhandari,Survival Networks:Algorithms for Diverse Routing,Kluwer Academic Publishers,1999.
【非特許文献３】Kohei Shiomoto,Eiji Oki,Masaru Katayama,Wataru Imajuku and Naoaki Yamanaka,  ”Dynamic multi-layer traffic engineering in GMPLS networks”ISS2002.
【非特許文献４】Galen H.Sasaki and Ching-Fong SuInterface, ”Between IP and WDM and its Effect on the Cost of Survivability,”IEEE Communication Magazine,vol.41,no.1,pp.74-79,January,2003.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述のマルチレイヤを考慮したＣＳＰＦには、実際の網に適用する場合に問題となる要素もある。
例えば、ＢＸＣＱ法の場合、上位レイヤのトラフィック量を考慮してパスを確立するため、トラフィック収容効率が上がり経済的なネットワークが実現できる。
しかし、下位レイヤでリンク障害が起きた場合の復旧手段を全く考慮していないため、実際にネットワーク内で故障が起きた場合には多くの通信が中断してしまうか、専用のプロテクションパスを用意する必要があるためにコストがかかってしまうという問題がある。
もう１つのマルチレイヤ用ＣＳＰＦであるＳＬＡ法では、下位レイヤの任意のリンクに障害が起きた場合でも、上位レイヤの各ノード同士は障害が起きたリンクから影響を受けない何らかの迂回経路を予め用意してつながりを保つことで、上位レイヤネットワークの信頼性を提供できる。
しかし、ノード間のトラフィック量を考慮していないため、トラフィック収容効率のいいパスの張り方が出来ず、トラフィックを運ぶ際に遅延が生じる、パスを確立するためのコストが高くなるなどの問題が出てくる。
【０００８】
そして、両方のアルゴリズムに共通する問題として、ネットワーク内に複数のユーザーグループが存在する場合を想定していない事が挙げられる。
ネットワークの収容効率が上がり、多くのユーザーにサービスを提供できる環境がある場合、同一企業間や同一地域内といったグループが複数存在する状況が考えられる。
この場合、同じユーザーグループに属するユーザー同士は通信を行うが、異なるユーザーグループに属するユーザーとは通信を行わない。更に、グループ内のユーザー情報が別のユーザーグループに漏れないように保障しなければならない。
そのため、ネットワーク内のユーザー情報を把握し、同ユーザーグループに属するユーザー間でのみパスを確立するような方法が必要である。
先に挙げた従来型マルチレイヤＣＳＰＦは、このような複数ユーザーが存在するネットワークに対応していない。
【０００９】
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、１つ以上のユーザーグループが存在するネットワークにおいて、トラフィック収容効率の改善を図りつつ、下位レイヤリンクに障害が起きた場合でも何らかの方法で上位レイヤが確実に復旧できるようなネットワーク網を設計するための経路計算方法、経路計算制御装置を提供することにある。
また、本発明の他の目的は、前述の経路計算方法をコンピュータに実行させるための経路計算プログラムを提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【００１０】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
上述した問題点を解決するために、本発明では、上位レイヤと下位レイヤが存在するネットワーク内にトラフィック転送等の機能を持ち、下位レイヤのスイッチと接続されるルーターが少なくとも２つ以上存在し、ユーザーグループが複数存在する場合の経路計算方法において、対象となるユーザーグループに属するユーザーのみの上位レイヤの所定の情報を考慮することで、その情報をもとに同じユーザーグループに属するユーザー間のみで、トラフィック収容効率がよく下位レイヤで障害が起きた場合にネットワーク内に存在する何れかのレイヤにおいて何らかの方法でその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする。
また、本発明では、前記下位レイヤは、波長やＴＤＭのコネクション型ネットワークを含み、前記上位レイヤは、ＭＰＬＳのコネクション型ネットワークを含むことを特徴とする。
また、本発明では、前記下位レイヤは、波長やＴＤＭのコネクション型ネットワークを含み、前記上位レイヤは、パケットネットワークのコネクションレス型ネットワークを含むことを特徴とする。
【００１１】
また、本発明では、下位レイヤで障害が起きた場合に、上位と下位の両方のレイヤにおいて、それぞれのレイヤで可能な復旧方法によってその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする。
また、本発明では、下位レイヤで障害が起きた場合に、上位レイヤのみで可能な復旧方法によってその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行うことを特徴とする。
また、本発明では、上位レイヤの情報として、トラフィックマトリクスを用いてパス設定を行うことを特徴とする。
また、本発明では、上位レイヤの情報として、将来のトラフィック需要予測を用いてパス設定を行うことを特徴とする。
【００１２】
また、本発明では、前記上位レイヤの情報として、リンクコストを用い、前記リンクコストの基準となる条件として、上位レイヤのパスが同じ下位レイヤリンクを用いないように考慮してパス設定を行うことを特徴とする。
また、本発明では、上位レイヤの所定の情報を考慮することでトラフィック収容効率がよく、下位レイヤで障害が起きた場合にネットワーク内に存在する何れかのレイヤにおいて何らかの方法でその障害に対処し、上位レイヤが確実に復旧することができるようなパス設定を行った後で、この時点で設定した下位レイヤパスを基にして再度上位レイヤのパス設定を行い、遅延が最小化するようなパス設定を行うことを特徴とする。
また、本発明では、前述のパス設定方法を実行する経路計算制御装置が、ネットワーク内の各ノードを一括して集中的に管理・制御する目的で専用に使用される。
また、本発明では、前述のパス設定方法を実行する経路計算制御装置が、ネットワーク内の各ノードに付属してノードを管理・制御する。
また、本発明は、前述の経路計算方法をコンピュータに実行させるための経路計算プログラムである。
【発明の効果】
【００１３】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、上位レイヤのパスが下位レイヤのパスに収容され、上位レイヤと下位レイヤの連携を取るネットワークにおいて、帯域利用効率がよく、下位レイヤで障害が発生した場合に上位レイヤで再ルーティングを行うことで障害復旧を行うことができるという信頼性の高い経路設計が可能となる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［実施例１］
先ず、本発明の実施例１の経路計算制御装置が適用されるネットワーク構造について説明する。
図１は、本実施例の経路計算制御装置が適用されるネットワークの概念図であり、回線交換ネットワークにパケットネットワークが収容されているネットワークの概念図である。
図１に示すネットワークは、スイッチ（Ａ１，Ｂ１，Ｃ１，Ｄ１）と、ルーター（Ａ２，Ｂ２，Ｃ２，Ｄ２）と、経路計算制御装置１０から構成される。
各スイッチ（Ａ１，Ｂ１，Ｃ１，Ｄ１）は、波長やＴＤＭのデータを転送する役割を持つ。各スイッチ同士は物理リンクで接続され、回線交換ネットワークを構成する。
各ルーター（Ａ２，Ｂ２，Ｃ２，Ｄ２）は、スイッチ（Ａ１，Ｂ１，Ｃ１，Ｄ１）と接続していて、各スイッチ（Ａ１，Ｂ１，Ｃ１，Ｄ１）にデータを受け渡すことでパケットを転送する機能を持つ。各ルーター同士は下位レイヤのパスを設定することで提供される論理パスで接続され、パケットネットワークを構成する。
経路計算制御装置１０は、ネットワーク内にユーザーグループが複数存在する場合に、対象となるユーザーグループに属するユーザーのみの何らかの情報を収集し、その情報をもとに同じユーザーグループに属するユーザー間のみでパス設計を行うための経路計算を行う機能を持ち、各ルーターとパス設定に必要な情報をやり取りする。
【００１５】
図１に示すようなネットワークでは、上位レイヤが下位レイヤに収容され、下位レイヤが上位レイヤヘ仮想トポロジーを提供する。
なお、上位レイヤとは、自ネットワークより相対的に下位に位置するネットワークに収容されるコネクションレス型またはコネクション型ネットワークを意味し、下位レイヤとは、自ネットワークより相対的に上位に位置するネットワークを収容するコネクション型ネットワークを意味する。
上位レイヤとしては、ＩＰやＥｔｈｅｒｎｅｔ、又はＩＰのパケットにラベルをつけて転送するＭＰＬＳのネットワーク、下位レイヤとしてはＴＤＭやＷＤＭネットワークを対象とする。
次に、本実施形態で必要な情報について定義する。
（１）リンクコスト
トラフィックを運ぶのに必要な距離又はホップ数に基づき設定されるコスト。通常、距離やホップ数が大きくなるとリンクコストは高くなる。
（２）残余帯域
下位レイヤのリンク中で、残っている帯域の量。光パスの場合であれば、使用可能な波長数。
（３）トラフィックマトリクス
上位レイヤのノード同士で交換されるトラフィック量の情報。
【００１６】
図２は、図１に示す経路計算制御装置１０の概略構成を示すブロック図である。
図２に示すように、経路計算制御装置１０は、経路計算部１１と、パス情報記憶部１２と、ルーティング情報記憶部１３と、メンバーシップ情報記憶部１４と、上位レイヤ情報記憶部１５と、パス情報制御部１６と、外部装置との制御インターフェース１７と、ルーティング情報制御部１８とを備える。
各部の機能や、上述したアルゴリズムを実施するのに必要な情報が機能ブロックにどのように対応しているかを、図３の表に示す。
（１）経路計算部１１は、ネットワークのパス計算を行う。
（２）パス情報記憶部１２は、ネットワーク内の上位／下位レイヤのパス情報、上位レイヤのパスが使用している下位レイヤリンク情報、上位レイヤのパスのトラフィック情報を収集し、格納する。
（３）ルーティング情報記憶部１３は、上位／下位レイヤのトポロジー情報や、リンクコスト・残余帯域情報を格納する。
（４）メンバーシップ情報記憶部１４は、ユーザー情報を管理、格納する。
（５）上位レイヤ情報記憶部１５は、パス情報記憶部１２とメンバーシップ情報記憶部１４の情報から、ユーザー毎の上位レイヤ情報を作成し、内部のデータベース１５１に格納する。
（６）パス情報制御部１６は、上位レイヤ、下位レイヤのパス確立の流れを制御する。
（７）外部装置との制御インターフェース１７は、パス確立・解除の命令、それに伴う情報を外部装置（ここでは、ルーター）に送出する。
（８）ルーティング情報制御部１８は、ネットワーク内のリンクにコストをつけるための情報を収集し、経路計算に必要なリンクコスト情報をルーティング情報記憶部１３に伝える。
【００１７】
これまでのマルチレイヤ経路計算アルゴリズムでは、上位レイヤのトラフィックを考慮して下位レイヤのパスを確立するものや、下位レイヤの任意のリンクが切断された場合でも上位レイヤのネットワークは接続が保たれるようにパス設計を行うものがあった。
しかしながら、これらのアルゴリズムはトラフィック収容効率を考慮するか、又は障害時の上位レイヤ接続性を保障するかのどちらかに特化しており、この両方を満たすようなアルゴリズムが存在しないという問題があった。
本実施形態では、マルチレイヤを考慮して経路計算を行う際に、上位レイヤの所定の情報に基づき経路計算を行うことでトラフィック収容効率を上げると同時に、下位レイヤに障害が発生した場合でも上位レイヤの接続性を保障するように予めパス設計を行うことで、前述の問題を解決する。
図４は、本発明の実施例の経路計算方法を説明するためのフローチャートであり、マルチレイヤネットワークの経路決定の動作を説明するためのフローチャートである。
先ず、上位レイヤの所定の情報に基づき、どのノード間に下位レイヤのパスを確立するかを決め、下位レイヤトポロジーを決定する（ステップ１０１）。
ここで、上位レイヤの情報としては、トラフィックマトリクス、将来のトラフィック需要予測、ネットワークユーザーが支払う使用料金、又は何らかの条件で重み付けされたリンクコストなどを用いる。
次に、ステップ１０１で決定した下位レイヤパスに上位レイヤのパスを収容することで、上位レイヤのトポロジーを決定する（ステップ１０２）。
【００１８】
この時、制約付きDijkstraアルゴリズムを用いて経路を決定しても良いし、通るリンクを明示的に指定しても良い。また、各上位パスで使用されるリンクが重複しないように、リンクコストのつけ方を上手く工夫してもよい。
このようにリンクの付け方を工夫することで、上位レイヤのパスが下位レイヤの特定のリンクに集中することなく分散されるため、下位レイヤのリンクに障害が起きた場合でも通信の中断による被害範囲が抑えられる。
また、次ステップの接続性をチェックする段階で、追加すべきパス数を抑えることができる。このコストのつけ方に関する詳細は後述する。
更に、任意の下位レイヤリンクに障害が起きた場合でも上位レイヤの接続が保たれるかどうかを下位レイヤリンクに対して調べる（ステップ１０３）。
この時、全ての下位レイヤ物理リンクに対して調べてもよいし、特定の物理リンクに対してのみ調べてもよい。
このように、全ての、又は重要なものを選択した特定の物理リンクに対して障害が起こった場合を考慮することで、起こりうる下位レイヤ障害を最大限に考慮することになるため、下位レイヤに障害が起こった場合の上位レイヤ信頼性を向上させることができる。
最後に、必要があれば、上位レイヤパスに対する下位レイヤの経路を再計算するか、又は下位レイヤのパスを追加するなどして、上位レイヤの接続が常に保たれるような迂回経路を確保しておく（ステップ１０４）。
このような経路計算の結果、最終的にはトラフィック収容効率が良く、下位レイヤ障害時でも上位レイヤ接続性が保障されるようなトポロジーが完成する。
なお、ステップ１０４の後に、前述の各ステップにより設定した下位レイヤパスを基にして、再度上位レイヤのパス設計を行い、遅延が最小化するようなパス設定を行うようにしてもよい。
【００１９】
この経路計算アルゴリズムの詳細について次に述べる。
上位レイヤ、下位レイヤのトポロジーを決定するためには、上位レイヤの所定の情報を利用する。
図５は、本発明の実施例の経路計算方法において、上位レイヤの所定の情報を収集した後に、上位、下位各レイヤのパス経路を決定するアルゴリズムを説明するためのフローチャートである。
この時利用する上位レイヤの情報は、経路計算制御装置１０のメンバーシップ情報記憶部１４が記憶しているユーザーグループ情報を用いて、ネットワーク内に存在する複数ユーザーグループの中から、サービスを提供する対象となるグループに属するユーザーの情報のみを収集して利用する。
上位レイヤの情報としては、トラフィックマトリクス、将来のトラフィック需要予測、ネットワークユーザーが支払う使用料金、又は何らかの条件で重み付けされたリンクコストなどを用いる。
先ず、上位レイヤの所定の情報に基づき、どのノード間に下位レイヤのパスを確立するかを決め、下位レイヤトポロジーを決定する（ステップ１１１）。
この時、下位レイヤリンクにつけるコストを工夫することで、ある特定の物理リンクに下位レイヤパスが集中することを避けられ、その結果、上位レイヤパスが同じ下位レイヤリンクを通る可能性が低くなり、下位レイヤ障害時の上位レイヤ信頼性を向上させることができる。
【００２０】
このコストのつけ方の例として２つ挙げる。
（１）コスト例１
始めに、１本の下位レイヤのパスを張った時点で、そのパスの始終端ノードに直接接続している下位レイヤリンクに対してコストを付け加える。２本目の下位レイヤパスを張り終えた時点で再び同様なコストを付け加える。
これを繰り返すことで、次に張ろうとするパスの経路は、今まで張ったパスと重ならないような経路となる可能性が高くなる。そのため、ある特定の物理リンクに下位レイヤパスが集中することが避けられる。
（２）コスト例２
始めに、１本の下位レイヤのパスを張った時点で、このパスが経由した下位レイヤリンク全てにコストをつける。
２本目以降の下位レイヤパスにも、下位レイヤリンクに対して同様なコストの付け方をする。これを繰り返すことで、次に張ろうとするパスの経路は、今まで張ったパスと重ならないような経路となる可能性が高くなる。
そのため、ある特定の物理リンクに下位レイヤパスが集中することが避けられる。
【００２１】
次に、上位レイヤパスを下位レイヤパスに収容するために、各上位レイヤパスが通る下位レイヤパスの最短経路を計算する（ステップ１１２）。
この計算は、経路計算制御装置１０の経路計算部１１で行われる。
この時、下位レイヤ経路の計算は、上位レイヤパスで何らかの順番を決めて、順番が早い上位レイヤパスから順に計算される。順番としては、トラフィック量やユーザーが支払う使用料、などを元に決定する。最短経路の計算には、Dijkstra Algorithmなどが利用できる。
コストをつける場合には、経路計算制御装置１０のルーティング情報記憶部１３が格納している残余帯域や距離に関する情報や、上位レイヤパスがなるべく同じ下位レイヤパスを通らないなどを考慮しても良い。
この時、下位レイヤパスにつけるコストを工夫することで、ある特定の下位レイヤパスに上位レイヤパスが集中することを避けられ、その結果、上位レイヤパスが同じ下位レイヤパスを通る可能性が低くなり、下位レイヤ障害時の上位レイヤ信頼性を向上させることができる。
上位レイヤパスがなるべく同じ下位レイヤパスを通らないようなコストのつけ方としては、始めに１本上位レイヤパスを張った後に、その上位レイヤパスを収容している下位レイヤパスにコストを付け加える。２本目以降の上位レイヤパスにも、下位レイヤパスに対して同様なコストの付け方をする。
これを繰り返すことで、次に張ろうとするパスの経路は、今まで張ったパスと重ならないような経路となる可能性が高くなる。
そのため、ある特定の下位レイヤパスに上位レイヤパスが集中することが避けられる。
【００２２】
次に、探した最短経路にトラフィックを流せるだけの利用可能な帯域が存在するかどうかを判定する（ステップ１１３）。
利用可能な帯域としては、波長やタイムスロットがある。波長を割り当てる場合には、fixed-order法やMax-Sum法などの波長割り当てアルゴリズムを用いる。
ステップ１１３において、利用可能な帯域が存在しなければ、他にも上位レイヤパスが通る下位レイヤパスの経路があるかどうかを判定し（ステップ１１５）、ステップ１１５で上位レイヤパスが通る下位レイヤパスの他の経路がある場合には、次に最適な下位レイヤパスの最短経路を計算し（ステップ１１７）、ステップ１１３からの処理を繰り返す。
また、ステップ１１５で、上位レイヤパスが通る下位レイヤパス他の経路がない場合には、このノード間を直接つなぐパスは存在しないので、対象パスを張ることを断念し（ステップ１１６）、次の上位レイヤを選択し（ステップ１１８）、次の上位レイヤパスを対象にしてステップ１１２からの処理を繰り返す。
一方、ステップ１１３で、帯域が存在していれば、上位レイヤの全パスに対して下位レイヤの最短経路を計算したかどうかを判定し（ステップ１１４）、全ての上位レイヤパスに対して計算が終了していなければ、次の上位レイヤを選択し（ステップ１１８）、次の上位レイヤパスを対象にしてステップ１１２からの処理を繰り返す。
また、ステップ（１１４）において、全ての上位レイヤパスに対して下位レイヤパスの最短経路を計算したら、終了する。
以上が上位レイヤパスを提供する下位レイヤのコネクション経路を決定する方法の詳細である。この時、ＭＩＬＰ（Mixed Integer Linear Program）法を用いて同様な計算をしても良い。
【００２３】
次に、下位レイヤの任意のリンクが切断した場合でも、上位レイヤのルーターの接続が保障されるようなパス設計のアルゴリズムについて説明する。
図６は、このアルゴリズムを説明するためのフローチャートである。
先ず、図５で説明した方法で、上位、下位レイヤトポロジーが完成した後に、下位レイヤのリンクに順番をつける（ステップ１２１）。
この順番は、パスを確立する以前に予め手動で割り振っていても良い。
この順番に従って、該下位レイヤのリンクを使用している下位レイヤのパスを調べ、それらのパスを削除した下位レイヤトポロジーを作成する（ステップ１２２）。
この時、ネットワークから孤立するノードが存在するかどうかを判定し（ステップ１２３）、ステップ１２３でネットワークから孤立するノードが存在しない場合には、次の下位レイヤのリンクを選択し（ステップ１２９）、次の下位レイヤのリンクを対象としてステップ１２２からの処理を繰り返す。
ここで、ネットワークから孤立したノードとは、同じ上位レイヤネットワーク内にある他のノードと、トラフィックをやり取りするための上位レイヤパスを１本も持たないノードのことを言う。
【００２４】
ネットワークから孤立するノードが存在する場合には、該下位レイヤのリンクを除外した下位レイヤトポロジーを作成し、それを元に孤立しているノードとその他のノードを接続する下位レイヤパスが存在するかどうかを判定し（ステップ１２４）、ステップ１２４で孤立しているノードをネットワークに接続できるものが存在しない場合（即ち、適当なパスが発見できない場合）には、該物理リンクに対するネットワークの接続性は保障されないまま、次の下位レイヤのリンクを選択し（ステップ１２９）、次の下位レイヤのリンクを対象としてステップ１２２からの処理を繰り返す。
なお、このようなパスに対しては、計算の結果、ネットワークの接続性が保たれないことが分かった後に、新たに１＋１のプロテクションパスを用意することで対処してもよい。
ステップ１２４で、孤立しているノードとその他のノードを接続する下位レイヤパスが存在する場合には、下位レイヤパスとしては、一番コストの低いものでも良いし、一番初めに見つけたものでもよい。
ステップ１２４で、孤立しているノードとその他のノードを接続する下位レイヤパスが存在する場合には、その下位レイヤ経路（物理リンク）に利用可能な帯域が存在するかどうかを判定する（ステップ１２５）。
波長リソースがあるかどうか調べる場合には、fixed-order法やMax-Sum法などの波長割り当てアルゴリズムを用いる。
【００２５】
ステップ１２５で、当該下位レイヤ経路に利用可能な帯域が存在しない場合、他の下位レイヤ経路が存在するか否かを調べ（ステップ１３０）、ステップ１３０で他の下位レイヤ経路が存在する場合には、ステップ１２５に戻り、同様に利用可能な帯域が存在するかどうかを調べる。
ステップ１２５で、該下位レイヤ経路の帯域が存在せず、ステップ１３０で他には下位レイヤ経路がない場合は、該物理リンクに対するネットワークの接続性は保障されないまま、次の下位レイヤのリンクを選択し（ステップ１２９）、次の下位レイヤのリンクを対象としてステップ１２２からの処理を繰り返す。
このようなパスに対しては、計算の結果、ネットワークの接続性が保たれないことが分かった後に、新たに１＋１のプロテクションパスを用意することで対処してもよい。
ステップ１２５で、利用可能な帯域が存在する場合には、該上位レイヤパスの下位レイヤ経路を変更するか、もとの経路を残しておきながら新しい経路を１＋１プロテクションパスとして用意しておき、ステップ１２２のトポロジーに追加する（ステップ１２６）。
この時、経路変更の要因となった下位レイヤリンクを記憶しておき、以後同パスが経路変更の対象となった場合に該下位レイヤリンクを使用しないように計算しても良い。
ステップ１２２で作成した下位レイヤパストポロジーにステップ１２６で追加したパスを加えた下位レイヤパストポロジーを作成し、このトポロジーを元に、ネットワークから孤立するノードが存在するかどうか判定し（ステップ１２７）、まだ孤立するノードが存在する場合には、他の下位レイヤ経路が存在するか否かを調べる（ステップ１３０）。
ステップ１２７で、ネットワークから孤立するノードが存在しない場合には、下位レイヤの全リンク、又は調べるべき特定のリンクに対して上記の計算を行ったかどうかを判定し（ステップ１２８）、ステップ１２８でまだ考慮していない下位レイヤリンクが存在すれば、次の下位レイヤのリンクを対象としてステップ１２２からの処理を繰り返す。
また、ステップ１２８で全ての物理レイヤリンクを考慮していれば、終了する。
以上がアルゴリズムの詳細である。
【００２６】
なお、前述の経路計算方法は、コンピュータに実行させることも可能であり、その場合には、コンピュータ内のハードディスクなどに格納される経路計算プログラムを、コンピュータが実行することにより行われる。
この経路計算プログラムは、ＣＤ−ＲＯＭなどの記録媒体、あるいは、インターネット等のネットワークや電話回線等の通信回線のように情報を伝送する機能を有する伝送媒体により供給される。
また、この経路計算プログラムは、上述した処理の一部を実現するためのものであってもよい。さらに、上述した処理を別の装置に既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
このように、本実施例によれば、上位レイヤのパスが下位レイヤのパスに収容され、上位レイヤと下位レイヤの連携を取るネットワークにおいて、上位レイヤの所定の情報に基づき上位レイヤのパスを確立し、引き続き、任意の下位レイヤのリンクに障害が起きた場合でも上位レイヤの接続性が保たれるように必要があれば経路の再計算を行うため、帯域利用効率がよく、下位レイヤで障害が発生した場合に上位レイヤで再ルーティングを行うことで障害復旧を行うことができるという信頼性の高い経路設計が可能である。
なお、本実施例では、上位レイヤ、下位レイヤ共に障害復旧機能を持つものとする。この方法により、経済的かつエンドユーザーが障害を気にせず、ネットワークを使用し続けることができるようなネットワークが実現できる。
【００２７】
［実施例２］
前述の実施例１では、複数ユーザーが収容されているネットワークに対して、前述の経路計算方法、経路計算プログラムを適用していた。
この経路計算方法は、ネットワーク内のノードが全て同じグループに属する場合にも適用可能である。この場合に、経路計算制御装置１０は図７に示すような構成となる。
図７に示すように、本実施例の経路計算制御装置１０は、経路計算部１１と、パス情報記憶部１２と、ルーティング情報記憶部１３と、上位レイヤ情報記憶部１５と、パス情報制御部１６と、外部装置との制御インターフェース１７と、ルーティング情報制御部１８とを備える。
各部の機能や、上述したアルゴリズムを実施するのに必要な情報が機能ブロックにどのように対応しているかを、図８の表に示す。
【００２８】
（１）経路計算部１１は、ネットワークのパス計算を行う。
（２）パス情報記憶部１２は、ネットワーク内の上位／下位レイヤのパス情報、上位レイヤのパスが使用している下位レイヤリンク情報、上位レイヤのパスのトラフィック情報を収集し、格納する。
（３）ルーティング情報記憶部１３は、上位／下位レイヤのトポロジー情報や、リンクコスト・残余帯域情報を格納する。
（４）上位レイヤ情報記憶部１５は、パス情報記憶部とメンバーシップ情報記憶部の情報から、ユーザー毎の上位レイヤ情報を作成し、内部のデータベース１５１に格納する。
（５）パス情報制御部１６は、上位レイヤ、下位レイヤのパス確立の流れを制御する。
（６）外部装置との制御インターフェース１７は、パス確立・解除の命令、それに伴う情報を外部装置（ここでは、ルーター）に送出する。
（７）ルーティング情報制御部１８は、ネットワーク内のリンクにコストをつけるための情報を収集し、経路計算に必要なリンクコスト情報をルーティング情報記憶部１３に伝える。
本実施例のように、扱うユーザーグループを１つのみにすることで、前述の実施例１の経路計算制御装置１０のメンバーシップ情報記憶部１４が不要になり、また複数必要であった上位レイヤ情報記憶部１５のデータベース１５１が１つで済むので、実装を簡素化することが可能である。
【００２９】
［実施例３］
前述の実施例１、実施例２では、経路計算制御装置１０は、ネットワーク内の各ノードを一括して集中的に管理・制御する目的で専用に使用される。
本実施例では、経路計算制御装置１０は、各ルーターの内部に配置した実施例である。
図９は、本実施例のネットワークの概念図であり、同図に示すように、本実施例では、ルーター（Ａ２，Ｂ２，Ｃ２，Ｄ２）は経路計算機能付きのルーターとされる。
このように、本実施例では、経路計算制御装置は、各ルーター（Ａ２，Ｂ２，Ｃ２，Ｄ２）の内部に配置され、ネットワーク内の各ノードに付属してノードを管理・制御する。
本実施例において、経路計算方法、経路計算制御装置１０は、実施例１、実施例２と同様のものを使用することが可能であり、同様に、本実施例の経路計算方法は、経路計算プログラムにより、コンピュータに実行させることも可能である。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施例１の経路計算制御装置が適用されるネットワークの概念図である。
【図２】本発明の実施例１の経路計算制御装置の概略構成を示すブロック図である。
【図３】本発明の実施例１の経路計算制御装置における各部の扱う情報や、各部の機能を説明する図である。
【図４】本発明の実施例１の経路計算方法を説明するためのフローチャートである。
【図５】本発明の実施例１の経路計算方法において、上位レイヤの所定の情報を収集した後に、上位、下位各レイヤのパス経路を決定するアルゴリズムを説明するためのフローチャートである。
【図６】本発明の実施例１の経路計算方法において、下位レイヤの任意のリンクが切断した場合でも、上位レイヤのルーターの接続が保障されるようなパス設計のアルゴリズムを説明するためのフローチャートである。
【図７】本発明の実施例２の経路計算制御装置の概略構成を示すブロック図である。
【図８】本発明の実施例２の経路計算制御装置における各部の扱う情報や、各部の機能を説明する図である。
【図９】本発明の実施例３の経路計算制御装置が適用されるネットワークの概念図である。
【符号の説明】
【００３１】
１０  経路計算制御装置
１１  経路計算部
１２  パス情報記憶部
１３  ルーティング情報記憶部
１４  メンバーシップ情報記憶部
１５  上位レイヤ情報記憶部
１６  パス情報制御部
１７  外部装置との制御インターフェース
１８  ルーティング情報制御部１８
１５１  データベース
Ａ１，Ｂ１，Ｃ１，Ｄ１  スイッチ
Ａ２，Ｂ２，Ｃ２，Ｄ２  ルーター
【図１】
2005223522.tif 000003
【図２】
2005223522.tif 000004
【図３】
2005223522.tif 000005
【図４】
2005223522.tif 000006
【図５】
2005223522.tif 000007
【図６】
2005223522.tif 000008
【図７】
2005223522.tif 000009
【図８】
2005223522.tif 000010
【図９】
2005223522.tif 000011