(57)【要約】【課題】経路の持つプロテクションタイプに応じた経路選択基準を満たす経路を計算することができる経路計算方法を提供する。【解決手段】プロテクションタイプが１＋１である時は、二つの経路のメトリックの和が最小となる互いに排他な経路が計算されるため、現用経路と予備経路のメトリックの和の最適性を保証した経路計算をすることができる。また、プロテクションタイプが１：１や１：Ｎである時は、現用経路に対して排他な予備経路を確保できる経路の組であることを前提条件とし、これらの組のなかで、メトリックが最小の経路を有する組が計算されることにより、現用経路の最適性を保証した経路計算をすることができる。【選択図】　　　　図１
2004023179.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にメトリックまたはコストが定義されたネットワークにおいて、ソースノードから宛先ノードへの１つの現用経路と１つの予備経路を計算する経路計算方法であって、
前記ソースノードから宛先ノードへの経路を設定する際に、設定される経路が持つプロテクションタイプによって、採用する経路選択基準を切り替えることを特徴とする経路計算方法。
【請求項２】
前記経路の持つプロテクションタイプが、１：１、または１：Ｎであった場合に、現用経路の候補経路に排他な予備経路の候補経路が確保できる経路の組であることを前提条件として、該前提条件を満たす現用経路の候補経路と、予備経路の候補経路との組のなかで、現用経路の候補経路のメトリックが最小となる組を現用経路と予備経路として計算することを特徴とする請求項１記載の経路計算方法。
【請求項３】
前記経路の持つプロテクションタイプが、１＋１である場合に、２つの経路のメトリックの和が最小となる、互いに排他な経路を、前記現用経路と予備経路として算出することを特徴とする請求項１または２記載の経路計算方法。
【請求項４】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にメトリックまたはコストが定義されたネットワークにおいて、ソースノードから宛先ノードへの１つの現用経路と１つの予備経路を計算する経路計算プログラムであって、
前記ソースノードから宛先ノードへの経路を設定する際に、設定される経路が持つプロテクションタイプによって、採用する経路選択基準を切り替える処理を実行することを特徴とする経路計算プログラム。
【請求項５】
前記経路の持つプロテクションタイプが、１：１、または１：Ｎであった場合に、現用経路の候補経路に排他な予備経路の候補経路が確保できる経路の組であることを前提条件として、該前提条件を満たす現用経路の候補経路と、予備経路の候補経路との組のなかで、現用経路の候補経路のメトリックが最小となる組を現用経路と予備経路として計算する処理を実行することを特徴とする請求項４記載の経路計算プログラム。
【請求項６】
前記経路の持つプロテクションタイプが、１＋１である場合に、２つの経路のメトリックの和が最小となる、互いに排他な経路を、前記現用経路と予備経路として算出する処理を実行することを特徴とする請求項４または５記載の経路計算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はネットワークに経路を設定するときの経路計算方法、及び経路計算プログラムに関する。
【０００２】
【従来の技術】
ソースノードから宛先ノードへ、１つの現用経路とそれに対する１つの予備経路を設定するとき、それらのノードを結ぶ経路が複数あった場合、その中から現用経路、予備経路の組１つを選択する基準は、基本的なものとして２つを挙げることができる（この基準を、以降では経路選択基準、または選択基準と呼ぶ）。なお、予備経路には、現用経路に対して排他となる経路を選択することを前提としている。また、２つの経路が排他であるとは、それらの経路がソースノードと宛先ノードを除いて同じノード及び同じ伝送路を通過しないことである。
【０００３】
１つは、最小のメトリックを持つ経路を現用経路にする経路選択基準である。経路のメトリックとは、その経路が通過する伝送路のメトリックの和である。また、これは最小メトリック経路が複数存在した場合、それらの中の任意の経路を現用経路として選択する経路選択基準である。予備経路には、現用経路に対して排他な経路の中で、最小のメトリックを持つ経路が計算される（この選択基準を、以降では「経路選択基準１」と呼ぶ）。ただし、この選択基準では、それが現用経路に排他な予備経路が確保されることを保証するように現用経路を選択する基準ではないため、排他な経路の組が存在するにもかかわらず、予備経路を確保できなくなる場合がある。
【０００４】
もう一方は、Ｒａｍｅｓｈ　Ｂｈａｎｄａｒｉ、サバイバルネットワークスアルゴリズムズ“Ｓｕｒｖｉｖａｂｌｅ　Ｎｅｔｗｏｒｋｓ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｄｉｖｅｒｓｉｔｙ　Ｒｏｕｔｉｎｇ”，Ｋｌｕｗｅｒ　ａｃａｄｅｍｉｃ　ｐｕｂｌｉｓｈｅｒｓ，Ｊａｎｕａｒｙ　１９９９．（以下、文献１という）にあるように、二つの経路のメトリックの和が最小となる、互いに排他である経路を計算し、そのうちメトリックの小さい方を現用経路に、大きい方を予備経路にする経路選択基準である（この経路選択基準を、以降では「経路選択基準２」と呼ぶ）。また、計算された２つの経路が同じメトリックを持つ経路であれば、そのうちの任意の経路が現用経路に、残りの経路が予備経路に選択される。
【０００５】
ここでそれぞれの経路選択基準を、図２を参照しながら説明する。図２では、ソースノードをｓ、宛先ノードをｔ、それ以外のノードをａ，ｂ，ｃとする。また、伝送路はメトリックをもち、かつ、向きをもった伝送路であるとし、図中では数字と矢印で表されている。
【０００６】
表１は、図２のネットワークにおける、ノードｓからノードｔへ到達可能な経路をすべて列挙したものである。
【０００７】
【表１】
2004023179.tif 000003
【０００８】
経路選択基準１のもとでは、現用経路は最小メトリック経路であるため、この表１より、最小のメトリックをもつｓ→ａ→ｂ→ｔと通過する経路が現用経路になる。また、予備経路は、ｓ→ａ→ｂ→ｔの経路に排他な経路の中で、最小のメトリックを持つ経路であるため、この表１よりｓ→ｃ→ｔと通過する経路が予備経路となる。
【０００９】
表２は、図２のネットワークにおける、ノードｓからノードｔへ到達可能な経路のノード排他な組（表２中のパス１、パス２）をすべて、その二つの経路のメトリックの和（表２中のＳｕｍ）と、そのうちの経路のメトリックの小さい方の値（表２中のＭｉｎ）と共に列挙したものである。
【００１０】
【表２】
2004023179.tif 000004
【００１１】
経路選択基準２のもとでは、２つの経路のメトリックの和が最小となる、互いに排他な経路の組が計算される。そのうちの小さい方が現用経路になるため、ｓ→ａ→ｔと通過する経路が現用経路に、また、ｓ→ｂ→ｔと通過する経路が予備経路になる。
【００１２】
障害回復を考慮して光ネットワークに経路を設定する場合、設定する経路にプロテクションタイプをもたせるのが一般的である。インターネットドラフト“Ｇｅｎｅｒａｌｉｚｅｄ　Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ　Ｌａｂｅｌ　Ｓｗｉｔｃｈｉｎｇ（ＧＭＰＬＳ）Ａｒｃｈｉｔｅｃｔｕｒｅ”、Ｅｒｉｃ　Ｍａｎｎｉｅ，Ｐｅｔｅｒ　Ａｓｈｗｏｏｄ−Ｓｍｉｔｈ　ｅｔ　ａｌ．，Ｉｎｔｅｒｎｅｔ　Ｄｒａｆｔ，Ｗｏｒｋ　ｉｎ　Ｐｒｏｇｒｅｓｓ，ｄｒａｆｔ−ｉｅｔｆ−ｃｃａｍｐ−ｇｍｐｌｓ−ａｒｃｈｉｔｅｃｔｕｒｅ−０１．ｔｘｔ，Ｎｏｖｅｍｂｅｒ　２００１．（以下、文献２と呼ぶ）によれば、プロテクションタイプは、１＋１、１：１、１：Ｎ等に分類される。プロテクションタイプ１＋１では、一つの現用資源に対して一つの予備資源が用意され、障害発生前には現用資源と予備資源の双方にトラフィックが流される。プロテクションタイプ１：１では、一つの現用資源に対して一つの予備資源が用意されるが、障害発生前には現用資源だけにトラフィックが流される。プロテクションタイプ１：Ｎでは、一つの予備資源がＮ個の現用資源のために共有されるが、それ以外の点では１：１に等しい。
【００１３】
従来の技術では、プロテクションタイプをもった経路が設定される場合、それがもつプロテクションタイプを考慮しないで、同一の経路選択基準を採用した経路計算が行われる。
【００１４】
経路選択基準１のもとで経路計算した場合、排他な二つの経路が存在するにも関わらず、最小メトリック経路として計算された現用経路がどこを通過するかによっては、現用経路と予備経路を排他にできない場合がある。このことを図３を用いて説明する。表３は、図３のネットワークにおける、ｓからｔへ到達可能な経路をすべて列挙したものである。
【００１５】
【表３】
2004023179.tif 000005
【００１６】
経路選択基準１のもとでは、現用経路は最小メトリック経路になるため、表３より、ｓ→ａ→ｂ→ｃ→ｔと通過する経路が現用経路となる。この現用経路に対する予備経路の設定を試みた場合、ｓからｔへ到達可能な経路がどこを通過しようと、現用経路のどこかを共有する経路となり、それに排他な経路を予備経路とすることができない。なお、図３から明らかなように、排他な２つの経路は存在している。
【００１７】
経路選択基準２のもとで経路計算した場合、経路選択基準１のもとで現用経路を計算した場合に問題となった「予備経路を現用経路に対して排他にすることができない」ことは、互いに排他な２つの経路が存在する限り起こり得ない。これを、先と同じ図３を用いて説明する。
【００１８】
表４は、図３に示されたネットワークにおける、ｓからｔへ到達可能な経路の排他な組（表４中のｐａｔｈ１、ｐａｔｈ２）をすべて、その２つの経路のメトリックの和（表４中のＳｕｍ）、と、そのうちの経路のメトリックの小さい方の値（表４中のＭｉｎ）と共に列挙したものである。
【００１９】
【表４】
2004023179.tif 000006
【００２０】
この図のネットワークにおいて、経路選択基準１を採用して現用経路を計算した場合は、その現用経路と排他となる予備経路を計算することが出来なかった。これに対して経路選択基準２を採用して現用経路を計算した場合は、表４よりｓ→ａ→ｔと通過する経路と、ｓ→ｂ→ｔと通過する経路の組が、メトリックの和が最小となる排他な経路の組となり、ｓ→ａ→ｔと通過する経路が現用経路になり、ｓ→ｂ→ｃ→ｔと通過する経路が予備経路になる。
【００２１】
経路選択基準１では、現用経路の最適性が優先され、予備経路の現用経路に対する排他性はその次の優先となる。経路選択基準２では、現用経路と予備経路の排他性と、その二つの経路のメトリックの和の最適性が保証される。しかし、経路選択基準２では、個々の経路の最適性は保証されない。すなわち、経路選択基準２を採用して計算された現用経路のメトリックよりも小さいメトリックをもつ経路を現用経路とすることができ、かつその現用経路に対して排他となる経路が確保できるような経路選択基準を採用することができる。
【００２２】
【発明が解決しようとする課題】
しかしながら、従来の経路計算方法は、経路が持つプロテクションタイプを考慮しない、同一の経路選択基準を採用する経路計算方法であったため、プロテクションタイプに応じた経路計算ができないという問題があった。また、従来の経路選択基準を採用した経路計算方法では、１：１や１：Ｎなどのプロテクションタイプを持つ経路に、最適な経路を選択することができないという問題があった。
【００２３】
本発明は上記事情に鑑みてなされたものであり、経路の持つプロテクションタイプに応じた経路を計算することができる経路計算方法、及び経路計算プログラムを提供することを目的とする。
【００２４】
【課題を解決するための手段】
係る目的を達成するために請求項１記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にメトリックまたはコストが定義されたネットワークにおいて、ソースノードから宛先ノードへの１つの現用経路と１つの予備経路を計算する経路計算方法であって、ソースノードから宛先ノードへの経路を設定する際に、設定される経路が持つプロテクションタイプによって、採用する経路選択基準を切り替えることを特徴とする。
【００２５】
請求項２記載の発明は、請求項１記載の発明において、経路の持つプロテクションタイプが、１：１、または１：Ｎであった場合に、現用経路の候補経路に排他な予備経路の候補経路が確保できる経路の組であることを前提条件として、該前提条件を満たす現用経路の候補経路と、予備経路の候補経路との組のなかで、現用経路の候補経路のメトリックが最小となる組を現用経路と予備経路として計算することを特徴とする。
【００２６】
請求項３記載の発明は、請求項１または２記載の発明において、経路の持つプロテクションタイプが、１＋１である場合に、２つの経路のメトリックの和が最小となる、互いに排他な経路を、現用経路と予備経路として算出することを特徴とする。
【００２７】
請求項４記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にメトリックまたはコストが定義されたネットワークにおいて、ソースノードから宛先ノードへの１つの現用経路と１つの予備経路を計算する経路計算プログラムであって、ソースノードから宛先ノードへの経路を設定する際に、設定される経路が持つプロテクションタイプによって、採用する経路選択基準を切り替える処理を実行することを特徴とする。
【００２８】
請求項５記載の発明は、請求項４記載の発明において、経路の持つプロテクションタイプが、１：１、または１：Ｎであった場合に、現用経路の候補経路に排他な予備経路の候補経路が確保できる経路の組であることを前提条件として、該前提条件を満たす現用経路の候補経路と、予備経路の候補経路との組のなかで、現用経路の候補経路のメトリックが最小となる組を現用経路と予備経路として計算する処理を実行することを特徴とする。
【００２９】
請求項６記載の発明は、請求項４または５記載の発明において、経路の持つプロテクションタイプが、１＋１である場合に、２つの経路のメトリックの和が最小となる、互いに排他な経路を、現用経路と予備経路として算出する処理を実行することを特徴とする。
【００３０】
【発明の実施の形態】
次に添付図面を参照しながら本発明の経路計算方法、及び経路計算プログラムに係る実施の形態を詳細に説明する。
【００３１】
図１を用いて本実施形態の手順を説明する。本実施形態の経路計算方法、及び経路計算プログラムは、経路のプロテクションタイプを識別する工程と、識別したプロテクションタイプに応じて経路選択基準を選択する工程とからなる。
【００３２】
本経路計算方法では、経路計算要求に対して、その要求で指定される経路がもつプロテクションタイプに応じた経路選択基準が採用される。そして、その経路選択基準を満たす経路を探索するためのアルゴリズムが実行され、その計算結果が経路計算応答として要求元に返される。
【００３３】
本実施形態の経路計算方法を用いて、プロテクションタイプが１＋１である経路を設定する場合と、１：１や１：Ｎである経路を設定する場合を図３と表４を用いて説明する。
【００３４】
図３に示されたネットワークのもと、プロテクションタイプが１＋１である経路を設定する場合、現用経路と予備経路の双方に常時、トラフィックが流れるため、現用経路だけの最適性を考慮するより、双方を合わせた最適性を考慮した経路計算方式が適している。このため、本経路計算方法では、経路選択基準として経路選択基準２が採用される。その結果、二つの経路のメトリックの和が最小となる互いに排他な経路が計算されるため、表４より、ｓ→ａ→ｔと通過する経路が現用経路になり、ｓ→ｂ→ｃ→ｔと通過する経路が予備経路になる。
【００３５】
また、プロテクションタイプが１：１や１：Ｎの経路を設定する場合、障害時を除けば現用経路だけにトラフィックが流れるため、現用経路の最適性を考慮した経路計算方式が適している。このため、現用経路に対して排他な予備経路を確保できる経路の組であることを前提条件とし、これらの組のなかで、メトリックが最小の経路を有する組が計算される。従って、表４より、ｓ→ａ→ｂ→ｔと通過する経路が現用経路になり、ｓ→ｃ→ｔと通過する経路が予備経路になる。
【００３６】
このように本実施形態は、経路のプロテクションタイプごとに採用する経路選択基準を切り替えることで、従来のプロテクションタイプを考慮しない同一経路選択基準を採用する経路計算方法に比べて、より経路のプロテクションタイプに適した経路を計算することができる。
【００３７】
プロテクションタイプが１＋１である時は、二つの経路のメトリックの和が最小となる互いに排他な経路が計算されるため、現用経路と予備経路のメトリックの和の最適性を保証した経路計算をすることができる。また、プロテクションタイプが１：１や１：Ｎである時は、現用経路に対して排他な予備経路を確保できる経路の組であることを前提条件とし、これらの組のなかで、メトリックが最小の経路を有する組が計算されることにより、現用経路の最適性を保証した経路計算をすることができる。
【００３８】
なお、上述した実施形態は本発明の好適な実施の形態である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施が可能である。なお、本発明の経路計算プログラムに係る実施形態は、コンピュータに上述した手順で経路計算を行わせるプログラムを格納し、コンピュータがこのプログラムに従って経路計算を行うことで実現できる。
【００３９】
【発明の効果】
以上の説明より明らかなように本発明は、経路がもつプロテクションタイプによって、採用する経路選択基準を切り替えることにより、プロテクションタイプに応じた経路を計算することができる。
【００４０】
プロテクションタイプが１＋１である時は、二つの経路のメトリックの和が最小となる互いに排他な経路が計算されるため、現用経路と予備経路のメトリックの和の最適性を保証した経路計算をすることができる。
【００４１】
また、プロテクションタイプが１：１や１：Ｎである時は、現用経路に対して排他な予備経路を確保できる経路の組であることを前提条件とし、これらの組のなかで、メトリックが最小の経路を有する組が計算されることにより、現用経路の最適性を保証した経路計算をすることができる。
【図面の簡単な説明】
【図１】本発明に係る実施形態の手順を説明するための図である。
【図２】ネットワークの一例を示す図である。
【図３】ネットワークの一例を示す図である。
【図１】
2004023179.tif 000007
【図２】
2004023179.tif 000008
【図３】
2004023179.tif 000009