(57)【特許請求の範囲】
【請求項１】
複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算方法であって、
それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、
前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、
前記始点ノードから前記終点ノードまでの冗長経路を計算し、その際、
前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、
前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該対応する前記ドメインを構成するノードから、このドメインに隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する抽出ステップと、
前記ドメイン境界ノードの集合から、２つのドメイン境界ノードを選択する選択ステップと、
前記選択した２つのドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける２つの前記ドメイン境界ノードまでの２つの経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算する計算ステップと、
予め設定された終了条件にしたがい、前記ドメイン境界ノードの集合から２つの前記ドメイン境界ノードを選ぶすべての組み合わせ、または、一部の組み合わせについて、前記選択ステップおよび前記計算ステップを繰り返すステップと、
前記２つの経路が冗長経路となるものの中から、１組以上の経路を経路計算結果として選択するステップと、
を実行することを特徴とする冗長経路計算方法。
【請求項２】
複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算方法であって、
それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、
前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、
前記始点ノードから前記終点ノードまでの冗長経路を計算し、その際、
前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、
前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインを構成するノードから、隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出するステップと、
それぞれの前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路について、冗長となる経路数を最大にするように経路を計算するステップと、
前記計算した経路の集合を経路計算結果とするステップと、
を実行することを特徴とする冗長経路計算方法。
【請求項３】
複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算方法であって、
それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、
前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、
前記始点ノードから前記終点ノードまでの冗長経路を計算し、その際、
前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、
前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインを構成するノードから、隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する抽出ステップと、
前記ドメイン境界ノードの集合から、１つのドメイン境界ノードを選択する選択ステップと、
前記選択した１つのドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路、および、他の前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路、の２つの経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算する計算ステップと、
予め設定された終了条件にしたがい、前記ドメイン境界ノードのうち、すべて、または、一部の前記ドメイン境界ノードについて、前記選択ステップおよび前記計算ステップを繰り返すステップと、
前記計算した冗長経路の中から、１組以上の経路を経路計算結果として選択するステップと、
を実行することを特徴とする冗長経路計算方法。
【請求項４】
前記始点ノードを含む前記ドメインに対応する前記経路計算装置において、前記処理部は、
隣接する前記経路計算装置から受信した前記経路計算結果、および、前記記憶部に記憶された対応する前記ドメインのネットワーク情報を用いて、前記始点ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの複数の経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算するステップと、
前記計算した冗長経路の中から、１組以上の経路を経路計算結果として選択し、この１組以上の経路、もしくは、この１組以上の経路から選択した１つ以上の経路を前記経路計算要求装置に送信するステップと、
を実行することを特徴とする請求項１から請求項３までのいずれか１項に記載の冗長経路計算方法。
【請求項５】
前記経路計算装置において、前記処理部は、
自身が前記終点ノードを含む前記ドメインに対応する前記経路計算装置であると判断した場合、当該ドメインにおける前記ドメイン境界ノードから前記終点ノードまでの冗長経路を計算して、その経路計算結果を、次に経路計算を行う前記経路計算装置に送信し、
自身が前記始点ノードおよび前記終点ノードのいずれも含まない前記ドメインに対応する前記経路計算装置であると判断した場合、隣接する前記経路計算装置から受信した経路計算結果を利用して自身の前記ドメインに対応する前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの冗長経路を計算して、その経路計算結果を、次に経路計算を行う前記経路計算装置に送信し、
自身が前記始点ノードを含む前記ドメインに対応する前記経路計算装置であると判断した場合、隣接する前記経路計算装置から受信した経路計算結果を利用して前記始点ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの冗長経路を計算して、その経路計算結果の中から冗長経路の全部または一部を経路計算結果として選択し前記経路計算要求装置に送信する
ことを特徴とする請求項１から請求項４までのいずれか１項に記載の冗長経路計算方法。
【請求項６】
前記経路計算装置において、前記処理部は、
前記経路計算要求装置による経路計算要求を受信したとき、それが前記冗長経路の計算要求であるか否かを判断し、前記冗長経路の計算要求であると判断した場合に、前記した冗長経路の計算を実行する
ことを特徴とする請求項１から請求項５までのいずれか１項に記載の冗長経路計算方法。
【請求項７】
前記経路計算装置において、前記処理部は、
隣接する前記経路計算装置から経路計算結果を受信した場合に、冗長経路を計算できなかったとき、当該隣接する前記経路計算装置に対して、前記受信した経路計算結果のうち、冗長経路を計算できなかった原因となっている、自身の前記ドメインにおける前記リンク、前記ノード、および、共有リスクリンクグループの少なくともいずれかの障害の影響を受ける前記ドメイン境界ノードを示す情報を経路除外制約条件として当該隣接する前記経路計算装置に送信し、
前記経路除外制約条件を受信した当該隣接する前記経路計算装置は、経路計算を再び行い、その経路計算結果を再び、次に経路計算を行う隣接する前記経路計算装置に送信する
ことを特徴とする請求項１から請求項６までのいずれか１項に記載の冗長経路計算方法。
【請求項８】
前記経路計算装置において、前記処理部は、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照して、当該経路計算装置に対応するドメインに関して複数の経路を計算する場合、
前記リンクを共有しない複数の経路、前記ノードを共有しない複数の経路、および、前記共有リスクリンクグループを共有しない複数の経路、の少なくともいずれかの選択入力を受け付け、
前記選択入力に基づき、前記複数の経路を計算する
ことを特徴とする請求項１から請求項７までのいずれか１項に記載の冗長経路計算方法。
【請求項９】
請求項１ないし請求項８のいずれか１項に記載の冗長経路計算方法をコンピュータに実行させるための冗長経路計算プログラム。
【請求項１０】
複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算システムにおける前記経路計算装置であって、
それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、
前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、
前記冗長経路計算システムは前記始点ノードから前記終点ノードまでの冗長経路を計算し、その際、
前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、
前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該対応する前記ドメインを構成するノードから、このドメインに隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する抽出処理と、
前記ドメイン境界ノードの集合から、２つのドメイン境界ノードを選択する選択処理と、
前記選択した２つのドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける２つの前記ドメイン境界ノードまでの２つの経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算する計算処理と、
予め設定された終了条件にしたがい、前記ドメイン境界ノードの集合から２つの前記ドメイン境界ノードを選ぶすべての組み合わせ、または、一部の組み合わせについて、前記選択処理および前記計算処理を繰り返す処理と、
前記２つの経路が冗長経路となるものの中から、１組以上の経路を経路計算結果として選択する処理と、を行う
ことを特徴とする経路計算装置。
【請求項１１】
複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算システムにおける前記経路計算装置であって、
それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、
前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、
前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、
前記冗長経路計算システムは前記始点ノードから前記終点ノードまでの冗長経路を計算し、その際、
前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、
前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインを構成するノードから、隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する処理と、
それぞれの前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路について、冗長となる経路数を最大にするように経路を計算する処理と、
前記計算した経路の集合を経路計算結果とする処理と、を行う
ことを特徴とする経路計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のドメインを有するネットワークにおいて、冗長経路を計算する技術に関する。
【背景技術】
【０００２】
ＩＰ（Internet Protocol）ネットワークなどの多くの（通信）ネットワークには、通常、複数のドメインが存在する。ドメインとは、ネットワークにおける所定の領域を指し、ノード、および、このノード間を接続するリンクをそれぞれ複数備えている。なお、ドメインの例としては、ＡＳ(Autonomous System)やＩＧＰ(Interior Gateway Protocol)のＡｒｅａが挙げられる。ノードとは、ルータなどの通信機器である。また、リンクとは、有線または無線による通信回線である。
【０００３】
ネットワークにおける（通信）経路計算のために、１つ以上のドメインに経路計算装置を対応させる手法、つまり、各経路計算装置が自身に対応する１つ以上のドメインをそれぞれ管理する手法がある。この手法では、各経路計算装置は、対応するドメインのネットワーク情報を把握する。そして、経路計算要求装置が、始点ノードと終点ノード含んだ経路計算要求を、経路計算装置に対して行う。経路計算要求装置の例としては管理システムやクライアントコンピュータが挙げられる。
【０００４】
そして、経路計算要求装置と経路計算装置、および、経路計算装置同士が、プロトコル通信を行うことで、同じもしくは異なるドメインに存在する始点ノードから終点ノードまでの経路計算を行うことができる。
【０００５】
経路計算に関しては、例えば、ＰＣＥＰ（ピーセップ：Path Computation Element communication Protocol）（非特許文献１参照）、ＢＲＰＣ（Backward Recursive PCE-based Computation）（非特許文献２参照）がある。
【０００６】
ＰＣＥＰは、ＭＰＬＳ（Multi Protocol Label Switching）／ＧＭＰＬＳ（Generalized ＭＰＬＳ）ネットワーク等において、帯域等を確保した経路を探すための通信プロトコルである。換言すれば、送信元のルータが、送信先までの通信路に必要な帯域を指定しながら経路の探索を行うための通信プロトコルである。
【０００７】
ＢＲＰＣは、ＩＥＴＦ（The Internet Engineering Task Force）で標準化が進められている、ドメイン間パスの最適経路を計算する手法である。
【０００８】
これらの方法では、ＰＣＥＰにより経路計算要求装置と経路計算装置、および経路計算装置同士が、プロトコル通信を行い、ＢＲＰＣにより複数の経路計算装置が連携した経路計算を行う。また、プロトコル通信を行う上で、ＰＣＥＰセッションが確立される。
【０００９】
ここで、ＰＣＥＰセッションにより通信を行う経路計算要求装置もしくは経路計算装置はＰＣＥＰピアと呼び、１つのＰＣＥＰセッションは２つのＰＣＥＰピアをもつ。２つのＰＣＥＰピアのうち、経路計算要求を行うＰＣＥＰピアをＰＣＣ（Path Computation Client）、経路計算要求を受け取って経路計算を行いＰＣＣに経路計算応答（経路計算結果送信）を行うＰＣＥＰピアをＰＣＥ（Path Computation Element）という。
【００１０】
ここで、従来技術の例について説明する。図１１は、従来技術の説明図である。図１１に示すように、ネットワークＮには、ドメイン３（３ａ，３ｂ，３ｃ）が存在する。各ドメイン３には、複数のノード１（Ａ〜Ｗ。以下「ノードＡ」、「Ａ」などという。）と、これらのノード１を接続する複数のリンク２とが存在する。各リンク２の近傍に添えられた数字（「１」〜「５」）は、それぞれのリンク２のコスト（例：ホップ数）を示す。
【００１１】
この例では、経路計算装置４ａ（４）がドメイン３ａ、経路計算装置４ｂ（４）がドメイン３ｂ、経路計算装置４ｃ（４）がドメイン３ｃのネットワーク情報をそれぞれ把握している。そして、クライアント装置５が、例えば、ノードＡを始点ノード、ノードＷを終点ノードとする経路計算要求を出す。
【００１２】
その場合、クライアント装置５と経路計算装置４ａ、経路計算装置４ａと経路計算装置４ｂ、経路計算装置４ｂと経路計算装置４ｃ、がＰＣＥＰによりプロトコル通信を行い、以下の処理（１）〜（９）に示すようにノードＡ（始点ノード）からノードＷ（終点ノード）の経路が計算される。
【００１３】
＜処理（１）＞クライアント装置５は、経路計算装置４ａに対して、ノードＡからノードＷまでの経路計算要求メッセージ（ＰＣＲｅｑ）を送信する。
＜処理（２）＞経路計算装置４ａは、ノードＡの情報がノードＷに到達するには、経路計算装置４ｂに対応するドメイン３ｂを経由することを判断し、経路計算装置４ｂに経路計算要求メッセージ（ＰＣＲｅｑ）を送信する。
【００１４】
＜処理（３）＞経路計算装置４ｂは、ノードＡの情報がノードＷに到達するには、経路計算装置４ｃに対応するドメイン３ｃを経由することを判断し、経路計算装置４ｃに経路計算要求メッセージ（ＰＣＲｅｑ）を送信する。
＜処理（４）＞経路計算装置４ｃは、ノードＷが自身の管理しているドメイン３ｃのノードであることを判断し、ドメイン３ｃのネットワーク情報を用い、経路計算要求メッセージ（ＰＣＲｅｑ）を送信してきた経路計算装置４ｂに対応するドメイン３ｂを構成するノード（例えばノードＮ，Ｏ，Ｐ）と１つ以上のリンクにより接続されるノード（例えばノードＱ，Ｒ，Ｓ）から、ノードＷへの経路を１つ以上計算し、経路および経路のコストを経路計算結果とする。なお、複数の経路からいくつかの経路に絞り込む基準は、例えばコストである。
【００１５】
＜処理（５）＞経路計算装置４ｃは、経路計算装置４ｂに、処理（４）で求めた経路計算結果を含む経路計算応答メッセージ（ＰＣＲｅｐ）を送信する。
＜処理（６）＞経路計算装置４ｂは、ドメイン３ｂのネットワーク情報と経路計算装置４ｃから受信した経路計算結果をつなぎあわせたものを用いて経路計算を行う。この経路計算で、経路計算装置４ｂは、経路計算要求メッセージ（ＰＣＲｅｑ）を送信してきた経路計算装置４ａが属するドメイン３ａを構成するノードと１つ以上のリンクにより接続されるノードから、ノードＷまでの経路を１つ以上計算し、経路および経路のコストを経路計算結果とする。
【００１６】
＜処理（７）＞経路計算装置４ｂが、経路計算装置４ａに、処理（６）で求めた経路計算結果を含む経路計算応答メッセージ（ＰＣＲｅｐ）を送信する。
＜処理（８）＞経路計算装置４ａが、ドメイン３ａのネットワーク情報と経路計算装置４ｂから受信した経路計算結果をつなぎあわせたものを用いて経路計算を行う。この経路計算で、経路計算装置４ａは、クライアント装置５から送信された経路計算要求メッセージ（ＰＣＲｅｑ）に含まれる始点ノードであるノードＡから、終点ノードであるノードＷへの経路を１つ以上計算し、経路および経路のコストを経路計算結果とする。
＜処理（９）＞経路計算装置４ａが、クライアント装置５に、処理（８）で求めた経路計算結果を含む経路計算応答メッセージ（ＰＣＲｅｐ）を送信する。
【００１７】
そして、処理（９）の経路計算応答メッセージ（ＰＣＲｅｐ）を受信したクライアント装置５は、例えば、ノードＡからノードＷまでの１つ以上の経路の中から、必要に応じて一番コストの小さい経路を選択することなどによって経路を決定する（図１１の例では経路１１１）。
【００１８】
ここで、冗長経路について説明する。なお、冗長経路とは、第一の経路、第二の経路、・・・、第Ｎの経路が、リンク、ノード、共有リスクリンクグループの少なくともいずれか１つのリソースをまったく共有しない、Ｎ個の経路の集合を指す。例えば、ある経路が障害によって１つの経路が影響を受けた場合でも、冗長経路中の他の経路に切り替えることで、その障害の影響を回避してサービスを継続することが可能となる。ここで、共有リスクリンクグループとは、例えば、同じ配線管に含まれるリンクの集合を意味し、１つの障害で同時に影響を受ける可能性のあるリンクの集合を意味する。
【００１９】
冗長経路を決定する場合、例えば、クライアント装置５が、最初に計算した経路を第一の経路とし、その第一の経路に含まれるノードなどを除外することを指示する制約条件（以下、経路除外制約条件という。）を付して第二の経路に関する経路計算要求を経路計算装置に送信すればよい。そうすれば、各経路計算装置４は経路除外制約条件を考慮して第二の経路を計算する。
【００２０】
しかし、図１１に示すように、各経路計算装置によって経路１１１が第一の経路として計算されると、ノード１を共有しない第二の経路を計算することはすでに不可能である。つまり、第一の経路の計算時に、第二の経路の計算要求が後から発生することを考慮していないため、実際には冗長経路を計算可能な場合であっても、冗長経路計算に失敗してしまう場合がある。
【００２１】
そこで、経路計算装置が第一の経路と第二の経路を同時に計算する方法もある（非特許文献３参照）。
【非特許文献１】“Path Computation Element (PCE) communication Protocol (PCEP)”、[online]、２００７年１１月、ＩＥＴＦ（The Internet Engineering Task Force）、[２００７年１２月検索]、インターネット＜http://www.ietf.org/internet-drafts/draft-ietf-pce-pcep-09.txt＞
【非特許文献２】“A Backward Recursive PCE-based Computation (BRPC) procedure to compute shortest inter-domain Traffic Engineering Label Switched Paths”、[online]、２００７年９月、ＩＥＴＦ（The Internet Engineering Task Force）、[２００７年１２月検索]、インターネット＜http://www.ietf.org/internet-drafts/draft-ietf-pce-brpc-06.txt＞
【非特許文献３】“Analysis of Inter-domain Label Switched Path (LSP) Recovery”、[online]、２００７年９月、ＩＥＴＦ（The Internet Engineering Task Force）、[２００７年１２月検索]、インターネット＜http://www.ietf.org/internet-drafts/draft-ietf-ccamp-inter-domain-recovery-analysis-02.txt＞
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかしながら、非特許文献３による方法は、複雑な処理を必要とする。つまり、この方法では、すべての可能性を探索する全探索手法を用いるため、計算量が多くなってしまうという問題がある。
【００２３】
そこで、本発明は、前記した問題を解決するためになされたものであり、複数のドメインを有するネットワークにおいて、冗長経路を効率よく計算することを課題とする。
【課題を解決するための手段】
【００２４】
前記課題を解決するために、本発明は、複数のノードと複数のリンクから構成されるドメインを複数有するネットワークがあり、１つ以上の前記ドメインに対応する経路計算装置が存在し、それぞれの前記経路計算装置が連携して、経路計算要求装置による経路計算要求において指定された始点ノードから終点ノードまでの複数の経路を計算する場合に、前記始点ノードと前記終点ノードが異なる前記ドメインに所属しているときに実行される冗長経路計算方法であって、それぞれの前記経路計算装置は、対応する前記ドメインのネットワーク情報を記憶する記憶部と、経路計算を行う処理部と、を備え、前記終点ノードを含む前記ドメインに対応する前記経路計算装置から、前記始点ノードを含む前記ドメインに対応する前記経路計算装置の順番に、それぞれの前記経路計算装置の処理部が、前記記憶部に記憶された自身のドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインに関して、前記リンク、前記ノード、および、共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算して、その経路計算結果を隣接する前記経路計算装置に送信することで、前記始点ノードから前記終点ノードまでの冗長経路を計算することを特徴とする。
【００２５】
かかる発明によれば、各経路計算装置が順番に、対応するドメインに関して、リンク、ノードおよび共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算することで、ドメインが異なる始点ノードから終点ノードまでの冗長経路を効率よく計算することができる。
【００２６】
また、本発明は、前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該対応する前記ドメインを構成するノードから、このドメインに隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する抽出ステップと、前記ドメイン境界ノードの集合から、２つのドメイン境界ノードを選択する選択ステップと、前記選択した２つのドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける２つの前記ドメイン境界ノードまでの２つの経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算する計算ステップと、予め設定された終了条件にしたがい、前記ドメイン境界ノードの集合から２つの前記ドメイン境界ノードを選ぶすべての組み合わせ、または、一部の組み合わせについて、前記選択ステップおよび前記計算ステップを繰り返すステップと、前記２つの経路が冗長経路となるものの中から、１組以上の経路を経路計算結果として選択するステップと、を実行することが望ましい。
【００２７】
かかる発明によれば、各経路計算装置が２つの経路から構成される冗長経路の中から１組以上の経路を経路計算結果として選択することにより、複数のドメインにまたがる冗長経路計算を行うことができる。
【００２８】
また、本発明は、前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインを構成するノードから、隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出するステップと、それぞれの前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路について、冗長となる経路数を最大にするように経路を計算するステップと、前記計算した経路の集合を経路計算結果とするステップと、を実行することが望ましい。
【００２９】
かかる発明によれば、各経路計算装置が冗長となる経路数を最大にするように経路を計算することにより、複数のドメインにまたがる冗長経路計算を行うことができる。
【００３０】
また、本発明は、前記始点ノードを含まない前記ドメインに対応する前記経路計算装置において、前記処理部は、前記記憶部に記憶された対応する前記ドメインのネットワーク情報を参照し、当該経路計算装置に対応するドメインを構成するノードから、隣接する前記ドメインのうち次に経路計算を行う対象となるドメインとの境界に位置するノードであるドメイン境界ノードの集合を抽出する抽出ステップと、前記ドメイン境界ノードの集合から、１つのドメイン境界ノードを選択する選択ステップと、前記選択した１つのドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路、および、他の前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの経路、の２つの経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算する計算ステップと、
予め設定された終了条件にしたがい、前記ドメイン境界ノードのうち、すべて、または、一部の前記ドメイン境界ノードについて、前記選択ステップおよび前記計算ステップを繰り返すステップと、前記計算した冗長経路の中から、１組以上の経路を経路計算結果として選択するステップと、を実行することが望ましい。
【００３１】
かかる発明によれば、各経路計算装置が１つのドメイン境界ノードを基準として冗長経路を計算することにより、複数のドメインにまたがる冗長経路計算を行うことができる。
【００３２】
また、本発明は、前記始点ノードを含む前記ドメインに対応する前記経路計算装置において、前記処理部は、隣接する前記経路計算装置から受信した前記経路計算結果、および、前記記憶部に記憶された対応する前記ドメインのネットワーク情報を用いて、前記始点ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの複数の経路が、前記リンク、前記ノード、および、前記共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない冗長経路となるように計算するステップと、前記計算した冗長経路の中から、１組以上の経路を経路計算結果として選択し、この１組以上の経路、もしくは、この１組以上の経路から選択した１つ以上の経路を前記経路計算要求装置に送信するステップと、を実行することが望ましい。
【００３３】
かかる発明によれば、始点ノードを含むドメインに対応する経路計算装置が最後に始点ノードから前記終点ノードまで、または、隣接ドメインのドメイン境界ノードまでの冗長経路を計算することにより、複数のドメインにまたがる冗長経路計算を行うことができる。
【００３４】
また、本発明は、前記経路計算装置において、前記処理部は、自身が前記終点ノードを含む前記ドメインに対応する前記経路計算装置であると判断した場合、当該ドメインにおける前記ドメイン境界ノードから前記終点ノードまでの冗長経路を計算して、その経路計算結果を、次に経路計算を行う前記経路計算装置に送信し、自身が前記始点ノードおよび前記終点ノードのいずれも含まない前記ドメインに対応する前記経路計算装置であると判断した場合、隣接する前記経路計算装置から受信した経路計算結果を利用して自身の前記ドメインに対応する前記ドメイン境界ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの冗長経路を計算して、その経路計算結果を、次に経路計算を行う前記経路計算装置に送信し、自身が前記始点ノードを含む前記ドメインに対応する前記経路計算装置であると判断した場合、隣接する前記経路計算装置から受信した経路計算結果を利用して前記始点ノードから、前記終点ノードまで、または、このドメインに隣接する前記ドメインのうち前に経路計算を行う対象であったドメインにおける前記ドメイン境界ノードまでの冗長経路を計算して、その経路計算結果の中から冗長経路の全部または一部を経路計算結果として選択し前記経路計算要求装置に送信することが望ましい。
【００３５】
かかる発明によれば、各経路計算装置が、自身を、終点ノードを含むドメインに対応する経路計算装置、始点ノードおよび終点ノードのいずれも含まないドメインに対応する経路計算装置、始点ノードを含むドメインに対応する経路計算装置、のいずれであるのかを判断し、その判断に応じた処理を行うことで、複数のドメインにまたがる冗長経路計算を行うことができる。
【００３６】
また、本発明は、前記経路計算装置において、前記処理部は、前記経路計算要求装置による経路計算要求を受信したとき、それが前記冗長経路の計算要求であるか否かを判断し、前記冗長経路の計算要求であると判断した場合に、前記した冗長経路の計算を実行することが望ましい。
【００３７】
かかる発明によれば、各経路計算装置が経路計算要求を冗長経路の計算要求か否か判断することで、要求品質に応じた経路計算が可能となる。
【００３８】
また、本発明は、前記経路計算装置において、前記処理部は、隣接する前記経路計算装置から経路計算結果を受信した場合に、冗長経路を計算できなかったとき、当該隣接する前記経路計算装置に対して、前記受信した経路計算結果のうち、冗長経路を計算できなかった原因となっている、自身の前記ドメインにおける前記リンク、前記ノード、および、共有リスクリンクグループの少なくともいずれかの障害の影響を受ける前記ドメイン境界ノードを示す情報を経路除外制約条件として当該隣接する前記経路計算装置に送信し、前記経路除外制約条件を受信した当該隣接する前記経路計算装置は、経路計算を再び行い、その経路計算結果を再び、次に経路計算を行う隣接する前記経路計算装置に送信することが望ましい。
【００３９】
かかる発明によれば、ある経路計算装置が冗長経路を計算できなかったときに、その前の経路計算装置が冗長経路計算をやり直すことで、冗長経路計算失敗の可能性を低減させることができる。
【００４０】
また、本発明は、前記経路計算装置において、前記処理部は、前記記憶部に記憶された自身のドメインのネットワーク情報を参照して、当該経路計算装置に対応するドメインに関して複数の経路を計算する場合、前記リンクを共有しない複数の経路、前記ノードを共有しない複数の経路、および、前記共有リスクリンクグループを共有しない複数の経路、の少なくともいずれかの選択入力を受け付け、前記選択入力に基づき、前記複数の経路を計算することが望ましい。
【００４１】
かかる発明によれば、複数の経路の計算の定義のうちユーザが選択した定義に基づいて、冗長経路を計算することができる。
【００４２】
また、本発明に係る冗長経路計算プログラムは、前記した経路計算装置を構成するコンピュータに実行させることを特徴とする。このような構成により、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００４３】
本発明によれば、複数のドメインを有するネットワークにおいて、冗長経路を効率よく計算することができる。
【発明を実施するための最良の形態】
【００４４】
以下、図面を参照（言及図以外の図も適宜参照）して、本発明を実施するための最良の形態（以下、「実施形態」という。）について詳細に説明する。なお、前記したように、冗長経路とは、第一の経路、第二の経路、・・・、第Ｎの経路が、リンク、ノード、共有リスクリンクグループの少なくともいずれか１つのリソースをまったく共有しない、Ｎ個の経路の集合を指すが、以下では、代表して、ノードを共有しない場合について説明する。
【００４５】
＜第１実施形態＞
図１は、第１実施形態のネットワークＮの全体構成図である。図１に示すように、ネットワークＮ（冗長経路計算システム）には、ドメイン３（３ａ，３ｂ，３ｃ）が存在する。各ドメイン３には、複数のノード１（Ａ〜Ｗ。以下「ノードＡ」、「Ａ」などという。）と複数のリンク２とが存在する。各リンク２の近傍に添えられた数字（「１」〜「５」）は、それぞれのリンク２のコスト（例:ホップ数）を示す。
【００４６】
なお、ノード１としては、例えば、伝送装置（ＳＯＮＥＴ（Synchronous Optical Network）／ＳＤＨ（Synchronous Digital Hierarchy）クロスコネクト、波長クロスコネクト）、ルータ、Ｌ２ＳＷ（レイヤ２スイッチ）などが相当する。
また、リンク２は、ノード１間に存在し、情報転送の媒体となるものであり、例えば、光ファイバなどが相当する。
【００４７】
ここでは、経路計算装置４ａ（４）がドメイン３ａ、経路計算装置４ｂ（４）がドメイン３ｂ、経路計算装置４ｃ（４）がドメイン３ｃのネットワーク情報をそれぞれ把握している。そして、クライアント装置５（経路計算要求装置）が、例えば、ノードＡを始点ノード、ノードＷを終点ノードとする経路計算要求を出す。
【００４８】
そして、クライアント装置５と経路計算装置４ａ、経路計算装置４ａと経路計算装置４ｂ、経路計算装置４ｂと経路計算装置４ｃ、がＰＣＥＰによりプロトコル通信を行い、ノードＡ（始点ノード）とノードＷ（終点ノード）の間の経路が計算される。なお、以下、始点ノード側を上流、終点ノード側を下流という。
【００４９】
次に、経路計算装置４の構成について説明する。図２は、経路計算装置の構成図である。経路計算装置４は、コンピュータ装置であり、入力部４１、通信部４２、出力部４３、記憶部４４および処理部４５を備えて構成される。なお、経路計算装置４における必須の構成は記憶部４４および処理部４５である。
【００５０】
入力部４１は、経路計算装置４のユーザが情報を入力する手段であり、例えばキーボードやマウスなどである。
【００５１】
通信部４２は、ネットワークＮにおける他の装置と通信するための通信インタフェースである。
【００５２】
出力部４３は、情報を出力するもので、例えばＣＲＴ（Cathode Ray Tube）などの表示装置である。
【００５３】
記憶部４４は、例えばＨＤＤ（Hard Disk Drive）などから構成され、ドメイン内ネットワークＤＢ（Data Base）４４１（ネットワーク情報）およびドメイン境界ノードＤＢ４４２（ネットワーク情報）を備える。
【００５４】
ドメイン内ネットワークＤＢ４４１は、自身の経路計算装置４に対応するドメイン３に関するネットワーク情報として、Ａ端装置ＩＤ（IDentification）、Ａ端ＩＦ＿ＩＤ、Ｚ端装置ＩＤ、Ｚ端ＩＦ＿ＩＤ、帯域、残余帯域、その他の情報を格納する。
【００５５】
Ａ端装置ＩＤとは、リンク２の一方の端となっているノード１のＩＤである。Ａ端ＩＦ＿ＩＤとは、Ａ端装置で、そのリンク２を一意に示す識別子である。Ｚ端装置ＩＤとは、リンク２の他方の端となっているノード１のＩＤである。Ｚ端ＩＦ＿ＩＤとは、Ｚ端装置で、そのリンク２を一意に示す識別子である。これらの４つのＩＤとしては、例えばＩＰアドレスを使用することができる。
【００５６】
帯域とは、各リンク２の最大利用可能帯域を示す情報である。残余帯域とは、各リンク２の残余帯域（最大利用可能帯域から現在利用されている帯域を差し引いた帯域）を示す情報である。その他の情報は、例えば、リンク２ごとのコストなどの情報を含んでいる。
【００５７】
なお、ドメイン内ネットワークＤＢ４４１では、リンク２を一意に識別するために、Ａ端装置ＩＤ、Ａ端ＩＦ＿ＩＤ、Ｚ端装置ＩＤおよびＺ端ＩＦ＿ＩＤの組み合わせを使用したが、その代わりに、リンク２に固有の識別子を使用してもかまわない。また、ドメイン内ネットワークＤＢ４４１に、リンク２の情報に加えてノード１の情報を保持してもかまわない。
【００５８】
ドメイン境界ノードＤＢ４４２は、自身の経路計算装置４に対応するドメイン３におけるドメイン境界ノードと、そのドメイン境界ノードの接続相手となる他のドメイン３におけるドメイン境界ノードおよびそのドメイン境界ノードに対応する経路計算装置４に関する情報などを格納する。
【００５９】
したがって、各経路計算装置４は、ドメイン境界ノードＤＢ４４２を参照することで、自身に対応するドメイン３における、他のドメイン３との境界に位置するドメイン境界ノードを特定することができる。また、隣接するドメイン３同士のお互いのドメイン境界ノードの接続関係もわかるので、一方のドメイン境界ノードがわかれば、その接続相手であるドメイン境界ノードを特定することができる。
【００６０】
なお、ドメイン境界ノードは、第１実施形態においては、１つのドメイン３に属するノード１を指すことになるが、これに限定されず、ドメインの形態や定義によっては、複数のドメイン３のいずれにも属する（あるいはいずれにも属さない）境界ノードを指してもよい。換言すれば、ドメイン境界ノードは、隣接するドメイン３におけるドメイン境界ノードと１つ以上のリンク２により接続しているノード１であってもよいし、あるいは、隣接するドメイン３におけるドメイン境界ノードと一致していても（それ自体を指していても）よい。
【００６１】
また、記憶部４４は、特に図示していないが、処理部４５が経路計算の処理を行う場合の終了条件などを予め記憶する（詳細は後記）。
【００６２】
なお、記憶部４４には、ドメイン内ネットワークＤＢ４４１およびドメイン境界ノードＤＢ４４２のほかに、ドメイン外ネットワークＤＢを備えていてもよい。ドメイン外ネットワークＤＢには、例えば、外部のドメイン３のノード１やリンク２のアドレスやそのドメイン３に対応する経路計算装置４のアドレスなどが格納される。このドメイン外ネットワークＤＢは、例えば、経路計算要求を受け取った経路計算装置４が、自身のドメイン内ネットワークＤＢ４４１に経路計算要求の終点ノードのない場合に、経路計算要求を転送すべき経路計算装置４のアドレスを特定するときなどに用いられる。
【００６３】
処理部４５は、例えばＣＰＵ（Central Processing Unit）とメモリから構成され、プロトコル手段４５１および経路計算手段４５２を有する。
【００６４】
プロトコル手段４５１は、ＰＣＥＰセッションを維持し、他の経路計算装置４（ＰＣＥＰピア）と通信を行う。具体的には、他の経路計算装置４と経路計算要求や経路計算結果などを送受信する。
【００６５】
経路計算手段４５２は、ドメイン内ネットワークＤＢ４４１及びドメイン境界ノードＤＢ４４２を利用して経路計算を行う。経路計算手段４５２は、複数のドメイン３にまたがる経路計算を行う場合、具体的には以下の３つのパターンに対応する。
【００６６】
[パターン１（終点ドメイン）]
経路計算要求の終点ノードが自身のドメイン内ネットワークＤＢ４４１に含まれている場合、それに対応した処理（図１における経路計算装置４ｃの処理）を行う。
【００６７】
[パターン２（中継ドメイン）]
経路計算要求の始点ノードも終点ノードも自身のドメイン内ネットワークＤＢ４４１に含まれていない場合、それに対応した処理（図１における経路計算装置４ｂの処理）を行う。
【００６８】
[パターン３（始点ドメイン）]
経路計算要求の始点ノードが自身のドメイン内ネットワークＤＢ４４１に含まれている場合、それに対応した処理（図１における経路計算装置４ａの処理）を行う。
【００６９】
そして、前記した終点ドメイン、中継ドメインおよび始点ドメインのいずれの場合も、具体的な計算アルゴリズムとしては、SuurballeアルゴリズムやＫ−shortestアルゴリズムなどの既存のアルゴリズムを活用できる。
【００７０】
Suurballeアルゴリズムは、始点ノードと終点ノードの間に、最短経路を計算し、その結果を用いてトポロジーを修正した後に、再度最短経路を計算することをＫ回繰り返すことで、経路に関するコストの和が最小となるＫ本の冗長な経路を計算するアルゴリズムである。
【００７１】
Ｋ−shortestアルゴリズムは、始点ノードと終点ノードの間に、最短経路を計算し、その経路を除外条件とした後に、再度最短経路を計算することをＫ回繰り返すことで、Ｋ本の冗長な経路を計算するアルゴリズムである。
【００７２】
なお、処理部４５は、ＰＣＥＰセッションの開始、終了、維持等を管理するＰＣＥＰセッション管理手段を備えていてもよい。
【００７３】
次に、ネットワークＮにおける経路計算の処理について説明する。図３は、クライアント装置５および各経路計算装置４の処理の流れを示すフローチャートである。なお、図３のフローチャートにおけるステップＳ１〜Ｓ９は、図１１で説明した処理（１）〜（９）に対応している。そして、図３のフローチャートの処理は、ステップＳ４，Ｓ６およびＳ８における具体的な計算手順が図１１の場合と異なっているが、それらの詳細については図４〜図６で説明する。
【００７４】
まず、クライアント装置５は、経路計算装置４ａに対して、ノードＡ（図１参照）からノードＷ（図１参照）までの経路計算要求（メッセージ）を送信する（ステップＳ１）。
【００７５】
クライアント装置５から経路計算要求を受信した経路計算装置４ａは、ドメイン境界ノードＤＢ４４２や前記したドメイン外ネットワークＤＢを参照して、ノードＡの情報がノードＷに到達するには、経路計算装置４ｂに対応するドメイン３ｂを経由することを判断し、経路計算装置４ｂに経路計算要求を送信する（ステップＳ２）。
【００７６】
経路計算装置４ａから経路計算要求を受信した経路計算装置４ｂは、ドメイン境界ノードＤＢ４４２や前記したドメイン外ネットワークＤＢを参照して、ノードＡの情報がノードＷに到達するには、経路計算装置４ｃに対応するドメイン３ｃを経由することを判断し、経路計算装置４ｃに経路計算要求を送信する（ステップＳ３）。
【００７７】
経路計算装置４ｂから経路計算要求を受信した経路計算装置４ｃは、ドメイン内ネットワークＤＢ４４１を参照して、ノードＷが自身の管理しているドメイン３ｃのノード１であることを判断する。そして、ドメイン３ｃのネットワーク情報を用い、経路計算要求を送信してきた経路計算装置４ｂに対応するドメイン３ｂを構成するノード（例えばノードＮ，Ｐ）と１つ以上のリンクにより接続されるノード（例えばノードＱ，Ｓ）から、ノードＷへの冗長経路を計算し、その経路および経路のコストを経路計算結果とする（ステップＳ４）。なお、複数の経路からいくつかの経路に絞り込む基準は、例えばコストである。
【００７８】
経路計算装置４ｃは、経路計算装置４ｂに、ステップＳ４で求めた経路計算結果を含む経路計算結果を送信する（ステップＳ５）。
【００７９】
経路計算装置４ｃから経路計算結果を受信した経路計算装置４ｂは、ドメイン３ｂのネットワーク情報と経路計算装置４ｃから受信した経路計算結果をつなぎあわせたものを用いて経路計算を行う（ステップＳ６）。この経路計算で、経路計算装置４ｂは、経路計算要求を送信してきた経路計算装置４ａに対応するドメイン３ａを構成するノード（例えばノードＦ，Ｇ）と１つ以上のリンクにより接続されるノード（例えばノードＩ，Ｊ）から、ノードＷへの冗長経路を計算し、その経路および経路のコストを経路計算結果とする。
【００８０】
経路計算装置４ｂは、経路計算装置４ａに、ステップＳ６で求めた経路計算結果を含む経路計算結果を送信する（ステップＳ７）。
【００８１】
経路計算装置４ｂから経路計算結果を受信した経路計算装置４ａは、ドメイン３ａのネットワーク情報と経路計算装置４ｂから受信した経路計算結果をつなぎあわせたものを用い、クライアント装置５から送信された経路計算要求に含まれる始点ノードであるノードＡから、終点ノードであるノードＷへの冗長経路を計算し、その経路および経路のコストを経路計算結果とする（ステップＳ８）。
【００８２】
経路計算装置４ａは、クライアント装置５に、ステップＳ８で求めた経路計算結果を含む経路計算結果を送信する（ステップＳ９）。ここでは、経路計算装置４ａは、ステップＳ８で計算した冗長経路の中から、１組以上の経路を経路計算結果として選択し、この１組以上の経路の全部（例えば１組の経路の全部（２つ以上の経路））または一部（例えば１組の経路の一部（１つの経路のみ））をクライアント装置５に送信する。
【００８３】
経路計算装置４ａから経路計算結果を受信したクライアント装置５は、経路計算結果を表示する（ステップＳ１０）。
【００８４】
このようにして、クライアント装置５は、経路計算要求に対する経路計算結果として冗長経路の情報の全部または一部を受信（および表示）することができる。
【００８５】
図４は、図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その１）を示すフローチャートである。ここでは、代表してステップＳ４の場合を例にとって説明する。
【００８６】
経路計算装置４ｃの処理部４５における経路計算手段４５２は、記憶部４４のドメイン境界ノードＤＢ４４２を参照して、ドメイン３ｃにおける上流側のドメイン境界ノードの集合を抽出する（ステップＳ４１）。例えば、図１のドメイン３ｃにおいて、ノードＱ，Ｒ，Ｓを抽出する。
【００８７】
経路計算手段４５２は、ドメイン境界ノードの集合から２つのドメイン境界ノードを選択する（ステップＳ４２）。この選択は、例えば、ランダムで行われる。例えば、図１のドメイン３ｃにおいて、ノードＱ，Ｒが選択される。
【００８８】
経路計算手段４５２は、ステップＳ４２で選択したドメイン境界ノードのうち、一方のドメイン境界ノードから終点ノードまでの経路と、他方のドメイン境界ノードから終点ノードまでの経路が、冗長となるように計算する（ステップＳ４３）。例えば、図１のドメイン３ｃにおいて、ノードＱからノードＷの経路と、ノードＲからノードＷの経路が冗長になるように計算する。ここでは、例えば、Ｑ→Ｔ→Ｗ、Ｒ→Ｕ→Ｗが計算される。具体的な計算アルゴリズムとしては、SuurballeアルゴリズムやＫ−shortestアルゴリズムなどの既存のアルゴリズムを活用できる。
【００８９】
経路計算手段４５２は、記憶部４４に予め設定された終了条件にしたがい、ドメイン境界ノードの集合から選択する２つのドメイン境界ノードの、すべての組み合わせ、または、一部の組み合わせについて経路計算を完了したか否か、確認する（ステップＳ４４）。
【００９０】
経路計算を完了していない場合（ステップＳ４４でＮｏ）、ステップＳ４２に戻る。経路計算を完了していた場合（ステップＳ４４でＹｅｓ）、ステップＳ４５に進む。例えば、図１のドメイン３ｃにおいて、すべての組み合わせとは、ノードＱとノードＲ、ノードＱとノードＳ、ノードＲとノードＳ、の３つの組み合わせのことである。
【００９１】
経路計算手段４５２は、一方のドメイン境界ノードから終点ノードまでの経路と、他方のドメイン境界ノードから終点ノードまでの経路が、冗長となるものの中から、１組以上を経路計算結果として選択する（ステップＳ４５）。この選択方法としては、例えば、ランダム、コストが最小、などがある。例えば、図１のドメイン３ｃにおいて、選択方法がコスト最小の場合、Ｑ→Ｔ→ＷとＳ→Ｖ→Ｗの経路の組が選択される。
【００９２】
図５は、図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その２）を示すフローチャートである。ここでは、代表してステップＳ４の場合を例にとって説明する。
【００９３】
経路計算装置４ｃの処理部４５における経路計算手段４５２は、記憶部４４のドメイン境界ノードＤＢ４４２を参照して、ドメイン３ｃにおける上流側のドメイン境界ノードの集合を抽出する（ステップＳ５１）。例えば、図１のドメイン３ｃにおいて、ノードＱ，Ｒ，Ｓを抽出する。
【００９４】
経路計算手段４５２は、各ドメイン境界ノードから終点ノードまでの経路について、冗長となる経路数が最大になるように経路を計算する（ステップＳ５２）。ここでは、Ｑ→Ｔ→Ｗ、Ｒ→Ｕ→Ｗ、Ｓ→Ｖ→Ｗが計算される。具体的な計算アルゴリズムとしては、SuurballeアルゴリズムやＫ−shortestアルゴリズムなどの既存のアルゴリズムを活用できる。
【００９５】
経路計算手段４５２は、前記した冗長となる経路の集合を経路計算結果とする（ステップＳ５３）。
【００９６】
図６は、図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その３）を示すフローチャートである。ここでは、代表してステップＳ４の場合を例にとって説明する。
【００９７】
経路計算装置４ｃの処理部４５における経路計算手段４５２は、記憶部４４のドメイン境界ノードＤＢ４４２を参照して、ドメイン３ｃにおける上流側のドメイン境界ノードの集合を抽出する（ステップＳ６１）。例えば、図１のドメイン３ｃにおいて、ノードＱ，Ｒ，Ｓを抽出する。
【００９８】
経路計算手段４５２は、上流側のドメイン境界ノードの集合から１つのドメイン境界ノードを選択する（ステップＳ６２）。この選択は、例えば、ランダムで行われる。例えば、図１のドメイン３ｃにおいて、ノードＱが選択される。
【００９９】
経路計算手段４５２は、選択したドメイン境界ノード（例えばノードＱ）から終点ノードまでの経路と、他のドメイン境界ノードから終点ノードまでの経路が、冗長となるように計算する（ステップＳ６３）。例えば、図１のドメイン３ｃにおいて、ノードＱからノードＷの経路と、ノードＲからノードＷの経路が冗長になるように計算する。その場合、例えば、Ｑ→Ｔ→Ｗ、Ｒ→Ｕ→Ｗが計算される。具体的な計算アルゴリズムとしては、SuurballeアルゴリズムやＫ−shortestアルゴリズムなどの既存のアルゴリズムを活用できる。冗長となるように計算できなかった場合は、他のドメイン境界ノードとして別のノード１を選択して、同様に計算を行う。
【０１００】
経路計算手段４５２は、記憶部４４に予め設定された終了条件にしたがい、ドメイン境界ノードの集合からそのすべてまたは一部を、ステップＳ６２における１つのドメイン境界ノードとして選択して経路計算を完了したか否か、確認する（ステップＳ６４）。例えば、図１のドメイン３ｃにおいて、ドメイン境界ノードのすべてとは、ノードＱ，Ｒ，Ｓのことである。
【０１０１】
経路計算を完了していない場合（ステップＳ６４でＮｏ）、ステップＳ６２に戻る。経路計算を完了していた場合（ステップＳ６４でＹｅｓ）、ステップＳ６５に進む。
【０１０２】
経路計算手段４５２は、冗長となる経路が存在する経路集合を経路計算結果とする（ステップＳ６５）。例えば、図１のドメイン３ｃにおいて、Ｑ→Ｔ→Ｗ、Ｒ→Ｕ→Ｗ、Ｓ→Ｖ→Ｗの組が経路計算結果となる。
【０１０３】
このように、図４〜図６のフローチャートの処理によって、図３のフローチャートのステップＳ４の処理を具体的に行うことができる。また、図３のステップＳ６においては、直前に受信した経路計算結果（ステップＳ５で送信された経路計算結果）を用いて、同様の処理を行うことができる。さらに、図３のステップＳ８については、直前に受信した経路計算結果（ステップＳ７で送信された経路計算結果）を用い、さらに、ドメイン境界ノードの代わりに始点ノードＡを用いて計算することで、同様の処理を行うことができる。
【０１０４】
次に、図３と図４のフローチャートに示す処理を行った場合の計算結果の例について説明する。図７は、図１のネットワークＮに対して、図３と図４のフローチャートに示す処理を行った場合の計算結果の例を示す図である。ここでは、クライアント装置５が、ノードＡを始点ノード、ノードＷを終点ノードとする経路計算要求を出したものとする。
【０１０５】
ステップＳ１〜Ｓ３の後、経路計算装置４ｃは、経路計算を行い（ステップＳ４）、経路計算装置４ｂに対し、経路計算結果＜１＞（Ｑ→Ｔ→Ｗ、Ｓ→Ｖ→Ｗ）を送信する（ステップＳ５）。
【０１０６】
経路計算装置４ｂは、経路計算結果＜１＞を用いて経路計算を行い（ステップＳ６）、経路計算装置４ａに対し、経路計算結果＜２＞（Ｉ→Ｌ→Ｋ→Ｎ→Ｑ、Ｊ→Ｍ→Ｐ→Ｓ）と経路計算結果＜１＞とを結合したものを送信する（ステップＳ７）。なお、ステップＳ６では、経路計算結果＜１＞にドメイン３ｃのドメイン境界ノードとしてノードＱとノードＳが含まれているので、経路計算結果＜２＞の最終ノード（下流側の端のノード）もノードＱとノードＳとなるように経路計算が行われる。
【０１０７】
なお、ステップＳ６の処理に関するプログラムを作成する場合、例えば図７の例では、ノードＨ，ＩおよびＪのいずれか２つから、ノードＱおよびノードＳまでの２つの経路を計算するようにしてもよい。また、ノードＱからノードＷまでの経路とその合計コスト（「２」）、および、ノードＳからノードＷまでの経路とその合計コスト（「４」）の情報を踏まえ、ノードＨ，ＩおよびＪのいずれか２つからノードＷまでの２つの経路を計算するようにしてもよい。
【０１０８】
経路計算装置４ａは、経路計算結果＜２＞を用いて経路計算を行い（ステップＳ８）、クライアント装置５に対し、経路計算結果＜３＞（Ａ→Ｃ→Ｆ→Ｉ、Ａ→Ｄ→Ｇ→Ｊ）と経路計算結果＜２＞と経路計算結果＜１＞とを結合したものを送信する（ステップＳ９）。なお、ステップＳ８では、経路計算結果＜２＞にドメイン３ｂのドメイン境界ノードとしてノードＩとノードＪが含まれているので、経路計算結果＜３＞の最終ノード（下流側の端のノード）もノードＩとノードＪとなるように経路計算が行われる。
【０１０９】
なお、ステップＳ９では、経路計算結果として冗長経路のうち１つの経路のみをクライアント装置５に送信するようにしてもよい。その場合、後で、クライアント装置５がその１つの経路を経路除外制約条件として指定して他の経路の計算要求を経路計算装置４に出せば、冗長経路の１つである他の経路を経路計算結果として得ることができる。
【０１１０】
また、ステップＳ８の処理に関するプログラムを作成する場合、例えば図７の例では、ノードＡから、ノードＩおよびノードＪまでの２つの経路を計算するようにしてもよい。また、ノードＩからノードＷまでの経路とその合計コスト（「８」）、および、ノードＪからノードＷまでの経路とその合計コスト（「８」）の情報を踏まえ、ノードＡからノードＷまでの２つの経路を計算するようにしてもよい。
【０１１１】
そして、クライアント装置５は、経路計算装置４ａから受信した経路計算結果＜１＞、＜２＞および＜３＞（経路７１と経路７２）を結合して表示する（ステップＳ１０）。
【０１１２】
このように、第１実施形態の経路計算装置４によれば、図７と図１１を比べればわかるように、従来技術では冗長経路を計算できなかった場合でも、冗長経路を計算することができる。また、各経路計算装置４が対応するドメイン３ごとに経路計算を行うので、効率よく経路計算することができる。また、図４のフローチャートの代わりに、図５や図６のフローチャートに示す処理を行った場合も、同様の作用や効果を得ることができる。
【０１１３】
＜第２実施形態＞
次に、第２実施形態について説明する。図８は、第２実施形態のネットワークＮ’の全体構成図である。図８の各構成について、図１と同様の構成については同じ符号を付し、説明を省略する。図８は、図１の場合と比べ、ドメイン３ｂ’（３）において、ノードＭとノードＰの間、および、ノードＯとノードＰの間のリンク２が、障害発生や帯域不足などの原因によって通信不能となっている点が相違している。
【０１１４】
このようなネットワークＮ’の場合、経路計算の方法によっては、冗長経路を計算できないことがありえる。例えば、経路計算装置４ｃが経路計算装置４ｂに経路計算結果として「Ｑ→Ｔ→Ｗ、Ｓ→Ｖ→Ｗ」を送信した場合である。その場合、ドメイン３ｂ’内ではノードＰが通信不能なので、経路計算装置４ｂが冗長経路を計算できない。
【０１１５】
図９は、第２実施形態における、クライアント装置５および各経路計算装置４の処理の流れを示すフローチャートである。なお、図３のフローチャートと比べて、同じ処理には同じステップ番号を付し、説明を省略する。
【０１１６】
ステップＳ１〜Ｓ４の後、経路計算装置４ｃは、経路計算装置４ｂに、ステップＳ４で求めた経路計算結果を含む経路計算結果を送信する（ステップＳ５）。ここで、例えば、経路計算装置４ｃが経路計算装置４ｂに、経路計算結果として「Ｑ→Ｔ→Ｗ、Ｓ→Ｖ→Ｗ」を送信したものとする。
【０１１７】
次に、経路計算装置４ｂは、経路計算に支障があるか否か判断する（ステップＳ５０１）。ここでは、経路計算装置４ｃから受信した経路計算結果のうち「Ｓ→Ｖ→Ｗ」が原因で経路計算に支障が生じている。つまり、ノードＭとノードＰをつなぐリンク２と、ノードＯとノードＰをつなぐリンク２と、が通信不能となっているので、ノードＰから「Ｓ→Ｖ→Ｗ」という経路接続する経路を計算することができない。
【０１１８】
経路計算装置４ｂは、経路計算結果にノードＳが含まれていることを理由として、経路計算に支障があると判断し（ステップＳ５０１でＹｅｓ）、経路計算時にノードＳを除外する旨の経路除外制約条件を経路計算装置４ｃに送信し（ステップＳ５０２）、ステップＳ５０１の前の待機状態に戻る。
【０１１９】
経路除外制約条件を受信した経路計算装置４ｃは、その経路除外制約条件を考慮して再び経路計算を行い（ステップＳ４）、経路計算結果を経路計算装置４ｂに送信する（ステップＳ５）。
【０１２０】
経路計算装置４ｂは、経路計算に支障がないと判断した場合（ステップＳ５０１でＮｏ）、ステップＳ６の処理に移る。ステップＳ６〜Ｓ１０は図３のフローチャートの場合と同様である。
【０１２１】
図１０は、図８のネットワークＮ’に対して、図９と図４のフローチャートに示す処理を行った場合の計算結果を示す図である。
【０１２２】
ステップＳ１〜Ｓ３の後、経路計算装置４ｃは、経路計算を行い（ステップＳ４）、経路計算装置４ｂに対し、経路計算結果＜１＞（Ｑ→Ｔ→Ｗ、Ｓ→Ｖ→Ｗ）を送信する（ステップＳ５）。
【０１２３】
経路計算装置４ｂは、経路計算に支障があると判断し（ステップＳ５０１でＹｅｓ）、経路計算時にノードＳを除外する旨の経路除外制約条件＜２＞を経路計算装置４ｃに送信し（ステップＳ５０２）、ステップＳ５０１の前の待機状態に戻る。
【０１２４】
経路除外制約条件＜２＞を受信した経路計算装置４ｃは、その経路除外制約条件＜２＞を考慮して再び経路計算を行い（ステップＳ４）、経路計算結果＜３＞（Ｑ→Ｔ→Ｗ、Ｒ→Ｕ→Ｗ）を経路計算装置４ｂに送信する（ステップＳ５）。
【０１２５】
このような経路計算結果＜３＞を受信した経路計算装置４ｂは、経路計算に支障がないと判断し（ステップＳ５０１でＮｏ）、経路計算結果＜３＞を用いて経路計算を行い（ステップＳ６）、経路計算装置４ａに対し、経路計算結果＜４＞（Ｈ→Ｋ→Ｎ→Ｑ、Ｊ→Ｍ→Ｌ→Ｏ→Ｒ）と経路計算結果＜３＞とを結合したものを送信する（ステップＳ７）。
【０１２６】
経路計算装置４ａは、経路計算結果＜４＞を用いて経路計算を行い（ステップＳ８）、クライアント装置５に対し、経路計算結果＜５＞（Ａ→Ｂ→Ｅ→Ｈ、Ａ→Ｄ→Ｇ→Ｊ）と経路計算結果＜４＞と経路計算結果＜３＞とを結合したものを送信する（ステップＳ９）。
【０１２７】
なお、第１実施形態の場合と同様、ステップＳ９では、経路計算結果として冗長経路のうち１つの経路のみをクライアント装置５に送信するようにしてもよい。
【０１２８】
そして、クライアント装置５は、経路計算装置４ａから受信した経路計算結果＜３＞、＜４＞および＜５＞（経路１０１と経路１０２）を結合して表示する（ステップＳ１０）。
【０１２９】
このように、第２実施形態の経路計算装置４によれば、経路計算の途中で冗長経路を計算できないと一旦判断してしまった場合でも、経路除外制約条件を考慮して再び経路計算を行うことで、冗長経路が存在するように、経路計算を行うことが可能となる。
【０１３０】
以上説明したように、本実施形態（第１実施形態および第２実施形態）の経路計算装置４によれば、各経路計算装置４が順番に、対応するドメイン３に関して、リンク、ノードおよび共有リスクリンクグループ、の少なくともいずれか１つのリソースを共有しない複数の経路を計算することで、ドメイン３が異なる始点ノードから終点ノードまでの冗長経路を計算することができる。つまり、複数のドメイン３を有するネットワークＮ（Ｎ’）において、冗長経路を効率よく計算することができる。
【０１３１】
また、各経路計算装置４が２つの経路から構成される冗長経路の中から１組以上の経路を経路計算結果として選択することにより、複数のドメイン３にまたがる冗長経路計算を行うことができる。
【０１３２】
さらに、各経路計算装置４が冗長となる経路数を最大にするように経路を計算することにより、複数のドメイン３にまたがる冗長経路計算を行うことができる。
【０１３３】
また、各経路計算装置４が１つのドメイン境界ノードを基準として冗長経路を計算することにより、複数のドメイン３にまたがる冗長経路計算を行うことができる。
【０１３４】
さらに、始点ノードを含むドメイン３に対応する経路計算装置４が最後に始点ノードから、終点ノードまで、または、下流に隣接するドメイン３のドメイン境界ノードまでの冗長経路を計算することにより、複数のドメイン３にまたがる冗長経路計算を行うことができる。
【０１３５】
また、各経路計算装置４が、自身を、終点ノードを含むドメイン３に対応する経路計算装置４、始点ノードおよび終点ノードのいずれも含まないドメイン３に対応する経路計算装置４、始点ノードを含むドメイン３に対応する経路計算装置４、のいずれであるのかを判断し、その判断に応じた処理を行うことで、複数のドメイン３にまたがる冗長経路計算を行うことができる。
【０１３６】
さらに、ある経路計算装置４が冗長経路を計算できなかったときに、その前の経路計算装置４が冗長経路計算をやり直すことで、冗長経路計算失敗の可能性を低減させることができる。
【０１３７】
なお、各経路計算装置４において、処理部４５は、リンク２を共有しない複数の経路、ノード１を共有しない複数の経路、および、共有リスクリンクグループを共有しない複数の経路、の少なくともいずれかの選択入力を、ユーザの操作によって入力部４１から受け付け、その選択入力に基づき、複数の経路を計算するようにしてもよい。
【０１３８】
また、経路計算装置４を構成するコンピュータに実行させる冗長経路計算プログラムを作成し、コンピュータにインストールすることにより、コンピュータは、その冗長経路計算プログラムに基づいた各機能を実現することができる。
【０１３９】
以上、本発明の実施形態について説明したが、本発明は、これに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
【０１４０】
例えば、各経路計算装置４が経路計算要求を冗長経路の計算要求か否か判断するようにしてもよい。つまり、本実施形態では、経路計算装置４が、経路計算時には冗長経路を計算するものとして説明したが、それではなく、経路計算要求ごとに、通常経路計算（冗長経路の計算が必須ではない経路計算）と冗長経路計算とのいずれかが指定され、冗長経路計算が指定された場合だけ経路計算装置４が冗長経路計算を行うようにしてもよい。そうすれば、要求品質に応じた経路計算が可能となる。
【０１４１】
また、複数の経路計算装置４や複数のドメイン３が構成するトポロジーは、バス型でなくても、リング型、メッシュ形、スター型、フルコネクト型、ツリー型、あるいはそれらの組み合わせなど、別のものであってもよい。
【０１４２】
さらに、本実施形態では、冗長経路はノード１を共有しないものとして経路計算を行ったが、冗長経路はリンク２または共有リスクリンクグループを共有しないものとして同様の経路計算を行うこともできる。
【０１４３】
また、冗長経路を計算する順番は、下流の経路計算装置４から上流の経路計算装置４の順番でなくても、その逆であってもよい。
【０１４４】
その他、ハードウェア、ソフトウェアの具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【０１４５】
【図１】第１実施形態のネットワークＮの全体構成図である。
【図２】経路計算装置４の構成図である。
【図３】クライアント装置５および各経路計算装置４の処理の流れを示すフローチャートである。
【図４】図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その１）を示すフローチャートである。
【図５】図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その２）を示すフローチャートである。
【図６】図３のステップＳ４，Ｓ６およびＳ８における具体的な計算手順（その３）を示すフローチャートである。
【図７】図１のネットワークＮに対して、図３と図４のフローチャートに示す処理を行った場合の計算結果の例を示す図である。
【図８】第２実施形態のネットワークＮ’の全体構成図である。
【図９】第２実施形態における、クライアント装置５および各経路計算装置４の処理の流れを示すフローチャートである。
【図１０】図８のネットワークＮ’に対して、図９と図４のフローチャートに示す処理を行った場合の計算結果を示す図である。
【図１１】従来技術の説明図である。
【符号の説明】
【０１４６】
１      ノード
２      リンク
３，３ａ，３ｂ，３ｃ  ドメイン
４，４ａ，４ｂ，４ｃ  経路計算装置
５      クライアント装置
４１    入力部
４２    通信部
４３    出力部
４４    記憶部
４５    処理部
４４１  ドメイン内ネットワークＤＢ
４４２  ドメイン境界ノードＤＢ
【図１】
0004806422.tif 000002
【図２】
0004806422.tif 000003
【図３】
0004806422.tif 000004
【図４】
0004806422.tif 000005
【図５】
0004806422.tif 000006
【図６】
0004806422.tif 000007
【図７】
0004806422.tif 000008
【図８】
0004806422.tif 000009
【図９】
0004806422.tif 000010
【図１０】
0004806422.tif 000011
【図１１】
0004806422.tif 000012