(57)【要約】  経路を取得するための方法、経路計算要素、および経路計算システムが提供され、この方法は、経路計算開始ドメインと経路計算終了ドメインの間の少なくとも２つの経路計算ドメインが、２つのエンドノードの間の経路を取得するために対話的計算を実行するステップを含み、少なくとも１つの経路計算ドメインが、第１の経路の経路情報を取得し、取得された第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、経路情報を次の経路計算ドメインに送信する。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路の経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
2011505092.tif 000002
【特許請求の範囲】
【請求項１】
経路計算開始ドメインと経路計算終了ドメインの間の少なくとも２つの経路計算ドメインによって、２つのエンドノードの間の経路を取得するために対話的計算を実行するステップを含み、
前記経路計算ドメインの少なくとも１つが、第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、前記生成された経路情報を次の経路計算ドメインに送信し、前記第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードである、経路を取得するための方法。
【請求項２】
前記２つのエンドノードが隣接する経路計算ドメインに属するとき、前記方法は、
前記経路計算開始ドメインによって、前記第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報に従って、前記第２の経路を計算するための経路情報を計算および生成し、前記生成された経路情報を前記経路計算終了ドメインに送信するステップをさらに含み、前記経路計算終了ドメインにおける前記第２の経路を計算するための経路情報は前記２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードであり、
前記経路計算終了ドメインによって、前記第１の経路についての経路情報を取得し、前記経路計算開始ドメインからの経路情報と、前記取得された第１の経路の経路情報とに従って、前記２つのエンドノードの間の第２の経路を取得するために計算を行うステップと、さらに含む請求項１に記載の経路を取得するための方法。
【請求項３】
前記２つのエンドノードが隣接しない経路計算ドメインに属し、前記対話的計算に参加する経路計算ドメインが、前記２つのエンドノードの間の経路を再帰的方式で取得するとき、前記方法は、
前記再帰的計算に参加する、経路計算終了ドメインでない経路計算ドメインによって、前記第１の経路についての経路情報を取得し、前記経路計算終了ドメインでない経路計算ドメインから前記経路計算開始ドメインまでの経路を計算し、前記取得された第１の経路についての経路情報に従って、前記次の経路計算ドメインの第２の経路を計算するための経路情報を生成し、前記生成された経路情報を前記次の経路計算ドメインに送信するステップと、
前記再帰的計算に参加する経路計算終了ドメインによって、前の経路計算ドメインからの経路情報に従って、前記２つのエンドノードの間の経路を計算するステップと、をさらに含み、
前記少なくとも１つの経路計算終了ドメインでない経路計算ドメインによって前記次の経路計算ドメインに送信される第２の経路を計算するための経路情報は前記２つの境界ノードの間の経路についての経路情報を含み、前記２つの境界ノードは前記経路計算終了ドメインに結び付けられ、前記境界ノードの一方は前記第１の経路が通過するノードである、請求項１に記載の経路を取得するための方法。
【請求項４】
前記２つのエンドノードが隣接しない経路計算ドメインに属し、前記対話的計算に参加する経路計算ドメインの１つが前記２つのエンドノードの間の経路を取得するために集中化された計算を実行するとき、前記方法は、
前記集中化された計算を担当する経路計算ドメインによって、前記第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とに従って、前記２つのエンドノードの間の第２の経路を計算するステップをさらに含み、前記他の経路計算ドメインによって前記集中化された計算を担当する経路計算ドメインに送信される経路情報は、
前記２つの境界ノードの間の経路についての経路情報を含み、前記２つの境界ノードは前記集中化された計算を担当する経路計算ドメインに結び付けられ、前記境界ノードの一方は前記第１の経路が通過するノードである、請求項１に記載の経路を取得するための方法。
【請求項５】
前記対話的計算を通して前記第１の経路および前記第２の経路を取得した後、前記方法は、
前記第１の経路と前記第２の経路が重なり合う部分を有するか否かを決定するステップと、
前記第１の経路と前記第２の経路が重なり合う部分を有するならば、２つの分離された経路または分離されるべき経路を取得するために、前記第１の経路と前記第２の経路の重なり合う部分を調整するステップと、をさらに含む請求項１から４のいずれか一項に記載の経路を取得するための方法。
【請求項６】
前記第１の経路は最短経路であり、前記第２の経路は前記第１の経路を除いて最短経路である、請求項１から４のいずれか一項に記載の経路を取得するための方法。
【請求項７】
前記対話的計算に参加する経路計算要素PCEからの対話的情報は、
前記第１の経路に対して、ノード分離された、リンク分離された、ノード分離されるべき、リンク分離されるべき、のいずれであるかを示す情報をさらに含む、請求項１に記載の方法。
【請求項８】
前記対話的計算に参加するPCEからの対話的情報が、前記第１の経路に対して、リンク分離された、または、リンク分離されるべき、であることを示すとき、前記第２の経路を計算するステップは、
前記第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にするステップ、または、前記第１の経路が通過する前記リンクの順方向の重みを増加させ、前記第１の経路が通過するリンクの逆方向の重みを負にするステップ、をさらに含む請求項７に記載の経路を取得するための方法。
【請求項９】
前記対話的計算に参加するPCEからの対話的情報は、前記第１の経路に対して、ノード分離された、または、ノード分離されるべき、であることを示すとき、前記第２の経路を計算するステップは、
前記第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にし、前記第１の経路内の３より大きい度数を有するノードを分割するステップ、または、前記第１の経路が通過するリンクの順方向の重みを増加させ、前記第１の経路が通過するリンクの逆方向の重みを負にし、前記第１の経路内の３より大きい度数を有するノードを分割するステップ、をさらに含む請求項７に記載の経路を取得するための方法。
【請求項１０】
前記対話的計算に参加する経路計算ドメインによって取得された第１の経路についての経路情報は、
前記経路計算ドメインが経路計算終了ドメインでないならば、前記経路計算終了ドメインは、前記２つのエンドノードの間の第１の経路を計算し、その後、前記第１の経路についての経路情報を他の経路計算ドメインに通知し、または、前記第２の経路の計算を開始する経路計算ドメインは、他の経路計算ドメインに送信される経路要求メッセージで前記第１の経路についての経路情報を伝達し、または、前記経路計算ドメインは、前記次の経路計算ドメインに送信される第２の経路を計算するための経路情報において前記第１の経路についての経路情報を伝達すること、および、
前記経路計算ドメインが経路計算終了ドメインであるならば、前記経路計算ドメインは自らの計算によって前記情報を取得すること、
のうち少なくとも１つを通して実現される請求項１に記載の経路を取得するための方法。
【請求項１１】
前記取得された第１の経路についての経路情報に従って、前記第２の経路を計算するための経路情報を計算し、生成し、送信するステップは、
第１の経路計算ドメインによって、前記取得された第１の経路についての経路情報に従って、前記第１の経路に対して、分離された、または、分離されるべき第２の経路に関する経路を計算し、前記計算が失敗したならば、前記第２の経路を計算するための経路情報を生成し、前記次の経路計算ドメインに送信するステップをさらに含み、前記第２の経路を計算するための経路情報は前記２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードである、請求項１に記載の経路を取得するための方法。
【請求項１２】
第１の経路についての経路情報を取得するように構成された情報取得サブユニットと、
経路計算の機能を実行し、前記第１の経路についての経路情報に従って第２の経路を計算するための経路情報を生成するように構成された経路計算サブユニットと、を備え、前記生成された第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードであり、
前記生成された第２の経路を計算するための経路情報を送出するように構成された情報送信サブユニットをさらに備える経路計算要素PCE。
【請求項１３】
第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成された情報取得サブユニットを備え、前記第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードであり、
前記取得された第１の経路についての経路情報と、前記取得された第２の経路を計算するための経路情報とに従って、前記第２の経路を計算するための経路情報をさらに計算するように構成された経路計算サブユニットと、
前記経路計算サブユニットによる計算を通して取得された経路情報を他の経路計算ドメインに送信するように構成された情報送信サブユニットと、
をさらに備える経路計算要素PCE。
【請求項１４】
第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成された情報取得サブユニットを備え、前記第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードであり、
前記取得された第１の経路についての経路情報と、前記取得された第２の経路を計算するための経路情報とに従って、前記第２の経路を計算するように構成された経路計算サブユニットと、
を備える経路計算要素PCE。
【請求項１５】
２つのノードの間の経路を取得するために対話的計算を実行するように構成された少なくとも２つの経路計算要素PCEを備える経路計算システムであって、
第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、前記生成された経路情報を第２のPCEに送信するように構成された第１のPCEを備え、前記第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記２つの境界ノードは前記第２のPCEが属するノードドメインに結び付けられ、前記境界ノードの一方は前記第１の経路が通過するノードであり、
前記第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報と、前記第１のPCEによって送信された経路情報とに従って、計算するように構成された前記第２のPCEと、
を少なくとも備える経路計算システム。
【請求項１６】
経路を取得するように構成されたコンピュータのためのプログラムを保存するコンピュータ読み取り可能な記憶媒体であって、前記プログラムの実行は、
他の経路計算要素PCEとの経路情報対話を実行し、第１の経路についての経路情報を取得し、前記取得された第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、前記生成された経路情報を他のPCEに送信するステップを含み、前記第２の経路を計算するための経路情報は２つの境界ノードの間の経路についての経路情報を含み、前記境界ノードの一方は前記第１の経路が通過するノードである、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００８年１月７日に出願された、発明の名称を“METHOD FOR OBTAINING PATH, PATH COMPUTATION ELEMENT, AND PATH COMPUTATION SYSTEM”とする中国特許出願第200810002521.5号の優先権の利益を主張し、同出願は、参照によりその全体が本明細書に組み込まれる。
【０００２】
本発明は、通信技術の分野に関し、より詳細には、経路を取得するための方法、経路計算要素(PCE: path computation element)、および経路計算システムに関する。
【背景技術】
【０００３】
マルチプロトコルラベルスイッチング-トラフィックエンジニアリング(MPLS-TE: multi-protocol label switching-traffic engineering)ネットワークおよび光ネットワークなどのコネクション指向ネットワークでは、クライアント信号はすべて、ネットワーク内の事前確立されたコネクションを通して宛先に伝送される。コネクションを確立するために、様々な方法を利用することができる。例えば、光ネットワークでは、経路内の各ノードの相互接続は、ネットワーク管理者によって構成することができ、またはシグナリングプロトコルにより自動的に構成することができる。そのようなコネクションは通常、ラベルスイッチングパス(LSP: label switching path)と呼ばれる。
【０００４】
ネットワーク障害下におけるクライアント信号の正常な伝送を保証するため、各クライアント信号に対して、通常２つのLSPが確立され、一方は、通常状態下における伝送に適用されて、ワーキングLSPと呼ぶことができ、他方は、ネットワーク障害下における伝送用であり、ワーキングLSPに代わってクライアント信号を伝送し、バックアップLSPと呼ぶことができる。上述の機能を実現するため、２つのLSPは、ノード分離(node-separation)およびリンク分離(link-separation)など、ある分離条件を満たすことが必要とされる。こうすることで、ネットワーク内のあるノードまたはリンクの障害下において、２つのLSPが同時に無効になることはなく、それによって、クライアント信号の伝送を保証することができる。
【０００５】
小規模ネットワークでは、各ノードは、オープンショーテストパスファースト-トラフィックエンジニアリング(OSPF-TE: Open Shortest Path First for Traffic Engineering)機器を用いて全体的なネットワークトポロジを収集し、収集したトポロジを自らのトラフィックエンジニアリングデータベース(TED: Traffic Engineering Database)に保存することができ、その後、分離経路アルゴリズムを使用することによって、２つの分離された経路を取得するための計算を行うことができる。
【０００６】
しかし、ネットワーク規模の拡大に伴い、各ノードがOSPF-TE機器を用いて全体的なネットワークトポロジを収集することは非現実的となっており、その理由は、この方法では、大量の制御帯域幅リソースが消費され、各ノードは、TEDを実現するための大容量メモリと、経路計算を実行するための高性能プロセッサとを有するように構成される必要があるからである。従来技術において利用される一般的な対策は、大規模ネットワークを複数のドメインに分割し、各ドメインごとにPCEを構成し、対応するドメインの経路計算の責任をPCEに割り当てることである。こうすることで、LSPを確立する際には、最初にノードが、経路計算要素プロトコル(PCEP: Path Computation Element Protocol)を用いて、ノードが属するドメインのPCEに経路計算を要求し、PCEは、経路を計算し、その後、経路をノードに返し、ノードは、返された経路情報を使用することによって、LSPを確立する。複数のドメインを横断する経路を取得したい場合は、これらのドメインに対応するPCEにおいて、PCEPを用いて、対話的計算を実行する必要がある。
【０００７】
従来技術では、２つの分離されたドメイン横断経路を取得するため、PCEの対話を通して、最初に最短経路が計算され、次にその経路上のリソースがTEDから除外され、別の経路が再計算される。計算が成功した場合、分離制約を満たす２つの経路が取得される。例えば、２つのノード分離された経路を計算したい場合、経路が通過するノードが除外され、２つのリンク分離された経路を計算したい場合、経路が通過するリンクが除外される。
【０００８】
しかし、従来技術の研究および実施の最中に、発明者らは、上述の技術的解決策が、実際には２つの分離された経路が存在するのに、第２の経路の計算に失敗する場合があることを見出した。図１は、従来技術に従って２つのドメインに分割されたネットワークの概略図である。図１を参照すると、１つのネットワークが２つのドメイン、すなわちドメイン1とドメイン2に分割され、R10およびR15は、ドメイン1の境界ノードであり、R21およびR23は、ドメイン2の境界ノードであり、R15は、ドメイン1のPCEであり、R21は、ドメイン2のPCEであり、それぞれPCE1およびPCE2によって表される。各々の２つのノード間の接続線は、１つのトラフィックエンジニアリング(TE: traffic engineering)リンクであり、その重みは1である。
【０００９】
これ以降、図１を参照して、従来技術においてノードR11からノードR22への２つのリンク分離された経路を取得するための方法が紹介される。
【００１０】
最初に、以下のステップを含む、PCE1およびPCE2の間の対話を通して、第１の最短経路が取得される。
【００１１】
11. PCE1が、R11->R22の経路を計算するよう求める経路計算要求メッセージを受信する。
【００１２】
12. PCE1は、宛先ノードがドメイン1内に存在しないことを見出し、PCEPを用いて経路計算要求メッセージをPCE2に送信する。
【００１３】
13. PCE2は、宛先ノードがドメイン2内に存在することを見出し、その後、ドメイン2内の境界ノードから宛先ノードまでの経路を計算し、その結果、２つの経路、すなわち(R21, R22)および(R23, R24, R22)を取得し、PCEPを使用することによって、２つの経路についての経路情報をPCE1に返す。
【００１４】
14.  返された経路情報と、PCE1のTED内に保存されたドメイン1についてのトポロジ情報とに従って、制約付きショーテストパスファースト(CSPF: constrained shortest path first)アルゴリズムを用いてPCE1によって取得されるR11->R22の最短経路は、(R11, R12, R13, R14, R15, R21, R22)である。
【００１５】
第１の最短経路が取得された後、PCE1は、以下のステップを含む、別の経路の計算を開始する。
【００１６】
15. PCE1は、PCEPを用いて、第１の経路についての情報を保有する経路計算要求メッセージをPCE2に送信する。
【００１７】
16. PCE2は、ドメイン2の境界ノードから宛先ノードR22までの経路を計算し、第１の経路が通過するリンク、すなわちリンクR21->R22を除外し、その結果、ただ１つの経路が要件を満たし、それは(R23, R24, R22)であり、PCE2は、PCEPを用いて、経路(R23, R24, R22)についての経路情報をPCE1に返す。
【００１８】
17. PCE2によって返された経路情報を受信した後、PCE1は、送信元ノードR11から宛先ノードR22までの第２の経路を計算する。送信元ノードR11から同じドメイン内の境界ノードまでの経路は、(R11, R12, R13, R14, R15)、(R11, R12, R18, R19, R10)、(R11, R12, R18, R19, R14, R15)、(R11, R16, R17, R13, R14, R15)、および(R11, R16, R17, R13, R14, R19, R10)を含み、それらはすべて、第１の経路(R11, R12, R13, R14, R15, R21, R22)が通過するリンクを通過するので、第２の経路を取得することができず、すなわち、２つのリンク分離された経路の計算は失敗する。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかし、R11->R22が２つのリンク分離された経路、すなわち(R11, R12, R18, R19, R10, R23, R24, R22)および(R11, R16, R17, R13, R14, R15, R21, R22)を含むことは、図１から直ちに見て取ることができる。
【課題を解決するための手段】
【００２０】
上記の技術的課題を解決するため、本発明は、各PCEが全体的なネットワークトポロジを有さない環境下で、ドメイン横断の分離された経路の計算の成功率を高めることが可能な、経路を取得するための方法、PCE、および経路計算システムに関する。
【００２１】
したがって、本発明の実施形態は、以下の技術的解決策を用いて実現される。
【００２２】
一実施形態では、本発明は、以下のステップを含む、経路を取得するための方法を提供する。
【００２３】
経路計算開始ドメインと経路計算終了ドメインの間の少なくとも２つの経路計算ドメインが、２つのエンドノードの間の経路を取得するために、対話的計算を実行する。
【００２４】
経路計算ドメインの少なくとも１つが、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、生成された経路情報を次の経路計算ドメインに送信する。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
【００２５】
一実施形態では、本発明は、PCEを提供し、PCEは、情報取得サブユニットと、経路計算サブユニットと、情報送信サブユニットとを含む。
【００２６】
情報取得サブユニットは、第１の経路についての経路情報を取得するように構成される。
【００２７】
経路計算サブユニットは、経路計算の機能を実行するように構成され、第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を生成する。第２の経路を計算するための生成された経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
【００２８】
情報送信サブユニットは、第２の経路を計算するための生成された経路情報を送出するように構成される。
【００２９】
一実施形態では、本発明は、PCEをさらに提供し、PCEは、情報取得サブユニットと、経路計算サブユニットと、情報送信サブユニットとを含む。
【００３０】
情報取得サブユニットは、第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
【００３１】
経路計算サブユニットは、第１の経路についての取得された経路情報と、第２の経路を計算するための取得された経路情報とに従って、第２の経路を計算するための経路情報をさらに計算するように構成される。
【００３２】
情報送信サブユニットは、経路計算サブユニットによる計算を通して取得された経路情報を、他の経路計算ドメインに送出するように構成される。
【００３３】
一実施形態では、本発明は、PCEをさらに提供し、PCEは、情報取得サブユニットと、経路計算サブユニットとを含む。
【００３４】
情報取得サブユニットは、第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
【００３５】
経路計算サブユニットは、第１の経路についての取得された経路情報と、第２の経路を計算するための経路情報とに従って、第２の経路を計算するように構成される。
【００３６】
一実施形態では、本発明は、経路計算システムをさらに提供し、経路計算システムは、２つのノードの間の経路を取得するために対話的計算を実行するように構成された少なくとも２つのPCEを含む。システムは、第１のPCEおよび第２のPCEを少なくとも含む。
【００３７】
第１のPCEは、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、生成された経路情報を第２のPCEに送信するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、２つの境界ノードは、第２のPCEが属するノードドメインに結び付けられ、境界ノードの一方は、第１の経路が通過するノードである。
【００３８】
第２のPCEは、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報と、第１のPCEに送信された経路情報と従って、計算を行うように構成される。
【００３９】
上記に基づいて、上述の技術的解決策では、２つのエンドノードの間の経路は、ノードドメインに対応する少なくとも２つのPCE上で対話的計算を実行することによって取得される。対話的計算に参加するPCEのうちの第１のPCEは、第１の経路についての取得された情報に従って、第２の経路を計算するための経路情報を計算および生成することができ、第２の経路を計算するための経路情報は、第１のPCEが属するノードドメインの境界ノードと、その境界ノード側で第１の経路が通過するノードドメインの境界ノードとについての経路情報を含むので、第１の経路が通過する経路を除外することによって起こる、実際には存在する分離された経路の計算に失敗する問題を回避することができる。そのような落とし穴回避アルゴリズム(pitfall avoiding algorithm)を使用することによって、ドメイン横断の分離された経路の計算の成功率が上昇し、その結果、ユーザはドメイン横断の分離された経路をより的確に取得できるようになり、システムの信頼性が向上する。
【図面の簡単な説明】
【００４０】
【図１】従来技術による、２つのドメインに分割されたネットワークの概略図である。
【図２】本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法のフローチャートである。
【図３】本発明の一実施形態による、ノード分離されるべき経路の概略図である。
【図４】本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第１の好ましい実施形態におけるネットワークの概略図である。
【図５】本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第２の好ましい実施形態におけるネットワークの概略図である。
【図６】本発明の一実施形態による、拡張RPオブジェクトデータフォーマットの概略図である。
【図７Ａ】本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第３の好ましい実施形態におけるネットワークの概略図である。
【図７Ｂ】本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第３の好ましい実施形態におけるTED調整後のネットワークの概略図である。
【図８】本発明の一実施形態による、PCEの第１の好ましい実施形態の概略構造図である。
【図９】本発明の一実施形態による、PCEの第２の好ましい実施形態の概略構造図である。
【発明を実施するための形態】
【００４１】
以下の実施形態では、本発明は、各PCEが全体的なネットワークトポロジを有さない環境下で、PCEの対話を通して、実際に存在するドメイン横断の分離された経路を取得することができ、その結果、ドメイン横断の分離された経路の計算の成功率を高めることができる、経路を取得するための方法、PCE、および経路計算システムを提供する。
【００４２】
本発明の実施形態は、複数の経路計算ドメインを通して実現され、すなわち、経路計算開始ドメインと経路計算終了ドメインの間の少なくとも２つの経路計算ドメインが、２つのエンドノードの間の経路を取得するために、対話的計算を実行する。経路計算ドメインの少なくとも１つが、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、生成された経路情報を次の経路計算ドメインに送信する。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。こうすることで、第１のPCEは、第２のPCEに十分な経路リソースを提供し、その結果、第１の経路が通過する経路を除外することによって起こる、実際には存在する分離された経路の計算に失敗する問題が回避され、ドメイン横断の分離された経路の計算の成功率は上昇し、それによって、ユーザはドメイン横断の分離された経路をより的確に取得できるようになり、システムの信頼性が向上し、経路落とし穴問題が除去される。本明細書では、そのような方法は、落とし穴回避アルゴリズムと呼ばれる。本発明の実施形態における用語のうち、経路計算ドメインとノードドメインは、同じ意味を表す。
【００４３】
本明細書の文脈において、経路計算開始ドメインは、最初に計算を実行する経路計算ドメインを表し、それは、送信元ノードが属する経路計算ドメイン、または宛先ノードが属する経路計算ドメインとすることができる。経路計算終了ドメインは、最後に計算される経路計算ドメインを表す。経路計算開始ドメインが、送信元ノードが属する経路計算ドメインである場合、経路計算終了ドメインは、宛先ノードが属する経路計算ドメインであり、経路計算開始ドメインが、宛先ノードが属する経路計算ドメインである場合、経路計算終了ドメインは、送信元ノードが属する経路計算ドメインである。２つのエンドノード間を横切る中間ドメインが必要とされる場合、中間ドメインは、経路計算中間ドメインと呼ばれる。
【００４４】
２つのエンドノードの間の経路を計算するプロセスにおいて、２つの状況が存在し得る。一方は、経路計算開始ドメインが経路計算終了ドメインに隣接する状況であり、他方は、経路計算開始ドメインが経路計算終了ドメインに隣接しない状況である。経路計算開始ドメインが経路計算終了ドメインに隣接しない場合、再帰的方式(recursive manner)または集中化された方式(centralized manner)で、対話的計算を実行することができる。
【００４５】
再帰的方式での計算は、以下のステップを含む。再帰的計算に参加する各経路計算ドメインは、計算を通して経路計算終了ドメインが２つのエンドノードの間の経路を取得するまで、経路計算ドメインが属するノードドメインと経路計算開始ドメインの間の経路を計算し、次の経路計算ドメインの計算のための経路情報を生成し、生成経路情報を次の経路計算ドメインに送信する。
【００４６】
集中化された方式での計算は、以下のステップを含む。対話的計算に参加する各PCEは、PCEが属する経路計算ドメインにおいて計算される経路に関連する経路を計算し、集中化された計算を担当する経路計算ドメインの計算のための経路情報を生成し、生成された経路情報を集中化された計算を担当する経路計算ドメインに直接的または間接的に送信する。集中化された計算を担当する経路計算ドメインは、１つまたは複数の経路計算ドメインからの経路情報に従った計算を通して、２つのエンドノードの間の経路情報を取得する。
【００４７】
上述の再帰的方式および集中化された方式は、任意の経路を計算するように構成され、すなわち、両方式は、第１の経路を計算するように構成され得るばかりでなく、第１の経路に関連する第２の経路を計算するようにも構成され得る。
【００４８】
上述の経路計算ドメインの各々について、計算処理機能は、対応するPCEによって、または専用ノードもしくは経路計算ドメイン毎に指定されるノードによって実行することができる。
【００４９】
各経路計算ドメインは、サービス優先順位およびサービス品質(QoS)保証などのサービス要件を満たすために、計算される経路と第１の経路の間の関係情報に従って、対応する計算方式を構成することができる。関係情報は、ノード分離された(node-separated)、リンク分離された(link-separated)、ノード分離されるべき(to-be-node-separated)、およびリンク分離されるべき(to-be-link-separated)、といった状況のうちの少なくとも１つを含むことができる。詳細は、以下の具体的な適用シナリオにおいて説明される。
【００５０】
第２の経路を計算する場合、上述の経路計算ドメインの各々は、第１の経路についての経路情報を取得する必要がある。経路計算ドメインが経路計算終了ドメインである場合、経路計算ドメインは自らの計算を通して経路情報を取得し、経路計算ドメインが、第１の経路を計算するための経路計算終了ドメインではなく、第１の経路を計算するための経路計算開始ドメインもしくは経路計算中間ドメインである場合、第１の経路を計算するための経路計算終了ドメインは、２つのエンドノードの間の第１の経路を計算し、その後、第１の経路についての経路情報を他の経路計算ドメインに通知し、または第２の経路の計算を開始する経路計算ドメインは、経路要求メッセージを介して第１の経路についての経路情報を他の経路計算ドメインに送信し、または経路計算ドメインは、次の経路計算ドメインに送信される第２の経路を計算するための経路情報に第１の経路についての経路情報を保有する。第１の経路を計算するための経路計算開始ドメインは、第２の経路を計算するための経路計算開始ドメインと同じでも、または異なってもよいことに留意されたい。例えば、第１の経路を計算するための経路計算開始ドメインは、送信元ノードが属する経路計算ドメインであり、第２の経路を計算するための経路計算開始ドメインは、宛先ノードが属する経路計算ドメインである。
【００５１】
本発明の実施形態の目的、技術的解決策、および利点をより理解しやすくするため、本発明の実施形態のうちの再帰的計算方式を利用する実施形態が、添付の図面を用いて以下で詳細に説明される。
【００５２】
図２は、本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法のフローチャートである。方法の詳細な説明が、具体的なステップを通して以下で与えられる。
【００５３】
21.  経路計算開始ドメインは、第１の経路についての経路情報を取得し、第１の経路についての取得された情報と、計算される経路と第１の経路の間の分離関係情報とに従って、経路計算開始ドメインのエンドノードから経路計算開始ドメインの境界ノードまでの経路を計算する。上述の境界ノードは、経路計算終了ドメインに結び付けられる。
【００５４】
計算される経路は、第１の経路に関連し、関係は、ノード分離された、リンク分離された、ノード分離されるべき、およびリンク分離されるべき、であるかどうかを含む。
【００５５】
ノード分離されるべき関係は、送信元ノードから宛先ノードまでの複数の経路が通過するノードの中で、分離できるノードは分離され、分離できないノードは最大限分離される(すなわち、分離されていないノードの部分を有することが許容される)関係を表す。図３は、本発明の一実施形態による、ノード分離されるべき経路の概略図である。ノードR1-R15は、完全なノード分離された経路を有さないが、計算を通して、共にノードR6を通過する２つのノード分離されるべき経路が、すなわち、R1-R7-R8-R3-R9-R10-R5-R6-R15およびR1-R2-R11-R12-R4-R13-R14-R6-R15が取得できる。
【００５６】
リンク分離されるべき関係は、送信元ノードから宛先ノードまでの複数の経路が通過するリンクの中で、分離できるリンクは分離され、分離できないリンクは最大限分離される(すなわち、分離されていないリンクの部分を有することが許容される)関係を表す。
【００５７】
本明細書の文脈では、計算される経路と第１の経路の間の分離関係情報は、必要ではないこともあり、例えば、システムがそのような方式をデフォルトでサポートする場合、またはシステムによって構成されるパラメータに従って決定できる場合などがそうである。ノード分離されるべき経路またはリンク分離されるべき経路は、可能な限りユーザの要件を満たすように計算され、経路伝送の信頼性を改善する。
【００５８】
22.  計算が失敗した場合、経路計算開始ドメインは、２つの境界ノードの間の経路を計算する。２つの境界ノードは、経路計算終了ドメインに結び付けられ、境界ノードの一方は、第１の経路が通過する境界ノードである。複数の経路が、第１の経路が通過する境界ノードを通過する場合、２つの境界ノードの間の複数の経路が生成される。
【００５９】
第１の経路内の第１のノードドメインを通過する経路が完全に除外された場合、実際に存在する経路が除外されることがあり、計算が失敗した場合、第１のエンドノードドメインは、第１のエンドノードドメインの境界ノードから第１の経路が通過する第１のエンドノードドメインの境界ノードまでの経路を計算する。実際に存在する経路の計算を確実なものにし、計算の成功率を上昇させるために、そのような落とし穴回避アルゴリズムを利用することができる。
【００６０】
本明細書の文脈では、帯域幅を節約できるように、伝送は、障害中にも実行される。実際には、システムは、計算が失敗したかどうかに関わりなく、強制的に伝送を実行することができる。こうすることで、計算の信頼性が改善され、より多くの要件を満たすことができる。
【００６１】
23.  経路計算開始ドメインは、計算された経路情報および第１の経路についての情報の他に、計算される経路と第１の経路の間の分離関係情報も、隣接する経路計算中間ドメインに伝送する。経路計算開始ドメインが経路計算終了ドメインに隣接する場合、経路情報は、経路計算終了ドメインに直接的に伝送される。
【００６２】
24.  経路計算中間ドメインは、第１の経路についての情報、計算される経路と第１の経路の間の分離関係情報、および経路計算開始ドメインによって計算された経路情報を取得し、２つの境界ノードの間の経路を計算する。２つの境界ノードはそれぞれ、経路計算開始ドメインおよび経路計算終了ドメインに結び付けられる。上述の境界ノードの間の複数の経路が、経路計算開始ドメインおよび経路計算終了ドメインに結び付けられる場合、２つの境界ノードの間の複数の経路が生成される。
【００６３】
25.  計算が失敗した場合、経路計算中間ドメインは、２つの境界ノードの間の経路を計算する。２つの境界ノードは、経路計算終了ドメインに結び付けられ、境界ノードの一方は、第１の経路が通過するノードである。２つの境界ノードは、経路計算終了ドメインに結び付けられる。
【００６４】
26.  経路計算中間ドメインは、計算された経路情報および第１の経路についての情報の他に、計算される経路と第１の経路の間の分離関係情報も、次の経路計算中間ドメインに伝送する。次の経路計算ドメインが経路計算終了ドメインである場合、ステップ28まで直接スキップされ、すなわち、経路計算終了ドメインが、２つのエンドノードの間の経路を計算する。
【００６５】
27.  次の経路計算中間ドメインの処理プロセスは、ステップ25および26と同様であり、本明細書では、その詳細を再び繰り返すことはしない。
【００６６】
28.  経路計算終了ドメインは、第１の経路についての経路情報を取得し、前の経路計算ドメインによって送信された経路情報に従って、２つのエンドノードの間の経路を計算する。
【００６７】
２つのエンドノードの間の新しい経路を計算する上述のプロセスにおいて、経路での伝送が効率的であることを保証するため、第１の経路は、最短経路とすることができ、新しい経路は、第１の経路に次ぐ最短経路である。
【００６８】
各ドメインは、異なる分離関係情報に従って、異なる計算方法によって、経路を計算することができる。例えば、リンク分離された、または、リンク分離されるべき、であるドメイン横断の分離された経路の計算は、このドメイン内の第１の経路が通過するリンクの順方向(positive direction)を除外し、逆方向(negative direction)の重みを負にする(negate)こと、またはこのドメイン内の第１の経路が通過するリンクの順方向の重みを増加させ、逆方向の重みを負にすることを含む。さらに、ノード分離されたドメイン横断の分離された経路を取得するため、上述の方法は、第１の経路内で3よりも大きい度数(degree)を有するノードを分割することをさらに含む。
【００６９】
これ以降、本発明の実施形態が、具体的な適用シナリオにおいて説明される。
【００７０】
図４は、本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第１の好ましい実施形態におけるネットワークの概略図である。ネットワークは、３つのドメイン、すなわち、ドメイン1と、ドメイン2と、ドメイン3とによって構成されている。計算を容易にするため、各々の２つのリンク間のリンクの重みは、1に設定され、３つのドメインのPCEはそれぞれ、PCE1、PCE2、およびPCE3であり、それらはそれぞれ、R12、R22、およびR31に対応している。R31が経路計算要求メッセージを受信し、R11->R34の２つのリンク分離された経路が計算されるよう要求されると仮定する。これ以降、本発明の実施形態に従ってドメイン横断の分離された経路を実現する方法が、具体的なステップを通して説明される。
【００７１】
41.  第１の経路が計算される。
【００７２】
本発明の実施形態では、送信元ノードから宛先ノードまでの第１のドメイン横断経路を計算するための様々な方法が提供される。例えば、宛先ノードドメイン内のPCEは、宛先ノードドメインにおいて境界ノードから宛先ノードまでの経路を計算し、中間ドメイン内のPCEはそれぞれ、PCEが属するドメインの宛先ノード側の境界ノードとPCEが属するドメインの送信元ノード側の境界ノードの間の経路を計算し、その経路を送信元ノードドメイン内のPCEに返す。送信元ノードドメイン内のPCEは、返された計算結果に従って、送信元ノードから宛先ノードまでの経路を計算する。代替的に、宛先ノードドメイン内のPCEは、宛先ノードドメインにおいて境界ノードから宛先ノードまでの経路を計算し、その経路を送信元ノード側の隣接ドメイン内のPCEに返すこともできる。一方、中間ドメイン内のPCEは、中間ドメイン内の送信元ノード側の境界ノードから宛先ノードまでの経路を計算し、計算結果を送信元ノード側の隣接ドメイン内のPCEに順次返す。結果が送信元ノードドメイン内のPCEに返されると、送信元ノードドメイン内のPCEは、返された結果に従って、送信元ノードから宛先ノードまでの経路を取得するための計算を行う。
【００７３】
好ましくは、BRPC(backward recursive PCE-based computation(後方再帰PCEベース計算))方法を利用することができ、この方法は、経路が通過するリンクの重みの合計が最小である経路、すなわち最短経路を計算するために、多数のPCEの対話を通して１つのドメイン横断経路を取得する。
【００７４】
図４を参照すると、ドメイン系列は、ドメイン1->ドメイン2->ドメイン3と指定されており、３つのPCEが、第１の経路に関して対話的計算を実行し、その主なプロセスは、以下で与えられる。
【００７５】
411) PCE1は、R11->R34の経路を計算するため、経路計算要求メッセージをPCE2に送信する。
【００７６】
412) PCE2は、宛先ノードがドメイン3内に存在することを見出し、経路計算要求メッセージをドメイン3内のPCEであるR31、すなわちPCE3に転送する。
【００７７】
413) PCE3は、宛先ノードが自らが管理するドメイン内に存在することを見出し、ドメイン3のTED内のトポロジ情報に従って、前のドメインに接続された境界ノードから宛先ノードまでの経路を、すなわち、R31->R34およびR35->R34の経路を計算する。計算結果は、(R31, R32, R33, R34)および(R35, R36, R33, R34)であり、２つの経路の重みは共に3である。PCE3は、２つの経路についての上述の情報を保有する経路計算応答メッセージをR22に送信し、この場合、R22は、前のドメイン内のPCEである。
【００７８】
414) PCE2は、経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン2内に存在しないことを見出す。そのため、PCE2は、前のドメインに接続された境界ノードから宛先ノードまでの経路を計算し、ドメイン2のTED内のトポロジ情報と、PCE3によって返された経路情報とに従って、R21->R34、R23->R34、およびR26->R34の経路をそれぞれ計算する。計算結果は、(R21, R22, R31, R32, R33, R34)、(R23, R21, R22, R31, R32, R33, R34)、および、(R26, R27, R28, R35, R36, R33, R34)であり、それぞれ5、6、および6の重みを有する。PCE2は、３つの経路についての上述の情報を保有する経路計算応答メッセージをR12に送信し、この場合、R12は、前のドメイン内のPCEである。
【００７９】
415) PCE1は、経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン1内に存在することを見出す。そのため、PCE1は、ドメイン1のTED内のトポロジ情報と、PCE2によって返された経路情報とに従って、R11->R34の経路を計算し、計算された経路は、(R11, R12, R21, R22, R31, R32, R33, R34)であり、7の重みを有する。
【００８０】
42.  第１の経路の計算の後、第２の経路が計算され始め、それは以下のステップを含む。
【００８１】
421) PCE1は、R11->R34の経路を計算するため、経路計算要求メッセージをPCE2に送信し、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とを要求メッセージに保有する。
【００８２】
要求メッセージ内の計算される経路と第１の経路の間の分離関係情報は、例えば、リンク分離された、ノード分離された、リンク分離されるべき、または、ノード分離されるべき、であることを示すことができる。この実施形態では、分離関係は、リンク分離された、であると指定される。
【００８３】
422) PCE2は、宛先ノードがドメイン3内に存在することを見出し、経路計算要求メッセージをドメイン3内のPCEであるR31に転送する。
【００８４】
423) PCE3は、宛先ノードが自らが管理するドメイン内に存在することを見出し、前のドメインに接続された境界ノードから宛先ノードまでの経路を計算し、経路応答メッセージを前のドメインのPCEに返す。
【００８５】
この実施形態では、R31->R34およびR35->R34の経路がそれぞれ計算されるが、計算の前に、このドメインのTEDが調整され、第１の経路についての取得された情報の他に、計算される経路と第１の経路情報の間の分離関係情報にも従って、別の経路が計算される。例えば、第１のドメイン横断経路が通過するリンクの順方向は除外され、逆方向の重みは負にされ、このドメインのTEDが調整され、TED内のトポロジ情報が調整され、前のドメインに接続された境界ノードから宛先ノードまでの経路が、調整されたトポロジ情報に従って計算され、計算が失敗した場合、境界ノードから、第１の経路が通過し、前のドメインに接続される境界ノードまでの経路が計算される。図４に示されるように、R32->R33の方向のリンクは除外され、R33->R32の方向のリンクの重みは-1となる。R32->R33の方向のリンクが除外されたので、R31->R34の経路の計算は失敗する。さらに、境界ノードR31は第１の経路上に存在するので、その境界ノードから第１の経路が通過するこのドメイン内の境界ノードまでの経路を計算する必要はない。R35->R34の経路の計算結果は、(R35, R36, R32, R37, R38, R34)であり、4の重みを有する。前のドメインに経路計算応答メッセージを返すPCEであるR22は、R35->R34についての経路情報をメッセージに保有する。
【００８６】
424) PCE2は、経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン2内に存在しないことを見出す。そのため、PCE2は、前のドメインに接続された境界ノードから宛先ノードまでの経路を計算し、経路計算応答メッセージを前のドメインのPCEであるR12に送信する。
【００８７】
第１の経路についての取得情報と、計算される経路と第１の経路の間の分離関係情報とに従って、第１の経路が通過するリンクの順方向は除外され、逆方向の重みは負にされ、ドメイン2のTEDが調整され、ドメイン1に接続された境界ノードから宛先ノードまでの経路が、ドメイン2の調整されたTEDと、PCE3によって返された経路情報とに従って計算される。計算結果はそれぞれ、8の重みを有する(R21, R23, R24, R25, R35, R36, R33, R32, R37, R38, R34)、共に7の重みを有する(R23, R24, R25, R35, R36, R32, R37, R38, R34)、および(R26, R27, R28, R25, R35, R36, R33, R32, R37, R38, R34)である。３つの経路についての上述の情報を伝達する経路計算応答メッセージが、R12に送信され、この場合、R12は、前のドメイン内のPCEである。
【００８８】
425) PCE1は、経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン1内に存在することを見出す。そのため、PCE1は、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にし、ドメイン1のTEDを調整し、ドメイン1の調整されたTEDに従って、境界ノードからドメイン1の送信元ノードまでの経路を計算し、計算が失敗した場合、境界ノードから第１の経路が通過するドメイン1の境界ノードまでの経路を計算し、その結果、実際にはR11->R14の経路、すなわち(R11, R13, R14)を計算する。その後、PCE1は、PCE2によって返された経路情報に従って、R11->R34の経路、すなわち(R11, R13, R14, R23, R24, R25, R35, R36, R33, R32, R37, R38, R34)を計算する。
【００８９】
43.  任意選択的に、送信元ノードから宛先ノードまでの新しい経路が、第１の経路と重なり合う部分を有するかどうかが決定され、有する場合、分離された経路を取得するために、送信元ノードから宛先ノードまでの新しい経路と第１の経路の間の重なり合う部分が調整される。
【００９０】
２つの経路が重なり合うリンク、すなわちR32<->R33を有することが見つかった場合、２つのリンク分離された経路、すなわち(R11, R13, R14, R23, R24, R25, R35, R36, R33, R34)および(R11, R12, R21, R22, R31, R32, R37, R38, R34)を取得するために、２つの経路がそれぞれ調整される。
【００９１】
この実施形態から、第２の経路が計算される場合、第１の経路が通過するリンクは完全には除外されず、代わりに、第１の経路についての情報と、計算される経路と第１の経路の間のリンク分離関係情報とに従って、第１の経路と重なり合うリンクの順方向が除外され、逆方向の重みは負にされることが分かる。さらに、あるドメインの計算が失敗した場合、このドメイン内の送信元ノード側の境界ノードから、第１の経路が通過するこのドメイン内の送信元ノード側の境界ノードまでの経路が計算され、その結果、新しい経路が計算され、２つのリンク分離された経路が取得される。したがって、第１の経路と重なり合うリンクを完全に除外する解決策と比較した場合、この実施形態では、ドメイン横断の分離された経路の計算の成功率が上昇する。
【００９２】
２つ以上の中間ドメインが提供される状況は、１つの中間ドメインが提供される状況と実質的に同じであり、本明細書では、その詳細を再び繰り返すことはしない。
【００９３】
これ以降、第２の経路の計算中に、あるドメインの境界ノードから第１の経路の宛先ノードまでの経路の計算が失敗した場合、このドメインの側の境界ノードから、第１の経路が通過するこのドメインの同じ側の境界ノードまでの経路を計算する方法が利用できることを説明するために、具体的な適用例が採用され、ドメイン横断の分離された経路を計算する状況が、以下の実施形態を用いて説明される。
【００９４】
図５は、本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第２の好ましい実施形態におけるネットワークの概略図である。ネットワークは、２つのドメイン、すなわち、ドメイン1と、ドメイン2とによって構成されている。計算を容易にするため、各ノードリンクの重みは、1に設定され、２つのドメインのPCEはそれぞれ、R12 (PCE1)およびR21 (PCE2)である。PCE1が、R11->R23の２つのリンク分離された経路を計算するよう求める要求メッセージを受信すると仮定され、それが具体的なステップを用いて以下で説明される。
【００９５】
51.  第１の経路が計算される。先の実施形態と同様に、BRPCアルゴリズムが利用され、ドメイン系列は、ドメイン1->ドメイン2と指定され、２つのPCEが、第１の最短経路を、すなわち5の重みを有する(R11, R12, R13, R21, R22, R23)を取得するために、第１の経路に関して対話的計算を実行する。
【００９６】
52.  第２の経路が計算される。
【００９７】
各PCEは、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、それが所属するドメイン内のTEDを調整し、ある境界ノードから宛先ノードまでの経路の計算が失敗した状況下において、境界ノードから、第１の経路が通過するこのドメインの同じ側の境界ノードまでの経路を計算する。詳細なプロセスが以下で提示される。
【００９８】
521) PCE1は、R11->R23の経路を計算するため、経路計算要求メッセージをPCE2に送信し、第１の経路についての情報と、例えば、リンク分離された関係、ノード分離された関係、リンク分離されるべき関係、またはノード分離されるべき関係など、計算される経路と第１の経路の間の分離関係情報とを、経路計算要求メッセージに保有する。この実施形態では、分離関係は、リンク分離された、であると指定される。
【００９９】
具体的な実装では、現行のPCEPプロトコルの要求パラメータ(RP: request parameters)オブジェクトが、３つのフラグビットを追加することによって拡張される。図６は、本発明の一実施形態による、拡張RPオブジェクトデータフォーマットの概略図であり、フォーマットは、以下を含む。
Nフラグビット: 1は、ノード分離された、であることを表し、0は、ノード分離された、である必要はないことを表す。
Lフラグビット: 1は、リンク分離された、であることを表し、0は、リンク分離された、である必要はないことを表す。
Eフラグビット: 1は、分離されるべき経路を許容することを表し、0は、分離されるべき経路を許容しないことを表す。
【０１００】
分離されるべき経路を許容する場合の具体的な動作は、以下のようであり、分離条件を満たす経路が存在する場合は、分離された経路が返され、それ以外の場合は、最も分離に近い経路が返される。分離されるべき経路を許容しない場合の具体的な動作は、以下のようであり、分離条件を満たす経路が存在する場合は、分離された経路が返され、それ以外の場合は、計算失敗メッセージが返される。
【０１０１】
こうすることで、第２の経路が計算される場合、経路計算要求メッセージ内のルート記録オブジェクト(RRO: record route object)が、第１の経路についての情報を伝達し、ノード分離された関係またはリンク分離された関係など、計算される第２の経路と第１の経路の間の関係を表すように上述のフラグビットが構成される。そのため、各ドメインのPCEは、第１の経路についての情報に従って、それぞれのTEDをしかるべく調整することができ、経路を計算する。
【０１０２】
522) PCE2は、宛先ノードが自らが管理するドメイン内に存在することを見出し、前のドメインに接続された境界ノードから宛先ノードまでの経路を計算し、経路計算応答メッセージを前のドメインのPCEに返す。
【０１０３】
この実施形態では、R27->R23、R21->R23、およびR24->R23の経路がそれぞれ計算される。
【０１０４】
計算の前に、第１の経路についての情報に従って、このドメインのTEDを調整する必要があるが、それは具体的には、第１のリンクが通過する順方向を除外し、逆方向の重みを負にすることを含む。例えば、R21->R22の方向のリンクは除外され、R22->R21の方向のリンクの重みは-1となる。R24->R23の経路の計算結果は、(R24, R25, R26, R23)であり、3の重みを有する。R21->R22の方向のリンクが除外されるので、R21->R23の経路の計算は失敗し、境界ノードR21自体が第１の経路上に存在するので、境界ノードから第１の経路内の境界ノードまでの経路を計算する必要はない。さらに、R22->R23のリンクが除外されるので、R27->R23の経路の計算は失敗し、境界ノードから第１の経路が通過するこのドメイン内の境界ノードまでの経路、すなわちR27->R21の経路を計算する必要があり、その結果は、(R27, R22, R21)であり、0の重みを有する。
【０１０５】
前のドメインに経路計算応答メッセージを送信するPCEであるR13は、計算に成功した２つの経路についての経路情報、すなわち(R24, R25, R26, R23)および(R27, R22, R21)をメッセージに保有する。
【０１０６】
523) PCE1は、経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン1内に存在することを見出す。そのため、PCE1は、ドメイン1の調整されたTEDと、PCE2によって返された経路情報とに従って、R11->R23の経路を、すなわち7の重みを有する(R11, R14, R15, R16, R27, R22, R21, R13, R12, R17, R24, R25, R26, R23)を計算する。
【０１０７】
53.  任意選択的に、第２の送信元ノードから宛先ノードまでの経路が、第１の経路と重なり合う部分を有するかどうかが決定され、有する場合、分離ドメイン横断経路を取得するために、第２の送信元ノードから宛先ノードまでの経路と第１の経路の間の重なり合う部分が調整される。
【０１０８】
２つの経路が重なり合うリンク、すなわちR12<->R22を有することが見つかった場合、２つのリンク分離された経路、すなわち(R11, R12, R17, R24, R25, R26, R23)および(R11, R14, R15, R16, R27, R22, R23)を取得するために、２つの経路がそれぞれ調整される。
【０１０９】
境界ノードからあるドメインの宛先ノードまでの経路の計算が失敗した状況下において、実際に存在するドメイン横断の分離された経路を取得するために、境界ノードから、第１の経路が通過するこのドメインの同じ側の境界ノードまでの経路が計算されることが分かる。したがって、各ドメインのPCEが全体的なネットワークトポロジを有さない状況下において、ドメイン横断の分離された経路の計算の成功率が上昇する。
【０１１０】
エンドノードドメインの境界ノードからエンドノードまでの経路の計算、およびエンドノードドメインの境界ノードから第１の経路が通過するエンドノードドメインの境界ノードまでの経路の計算は、送信元ノードまたは宛先ノードが所在するエンドノードドメインのPCEによって同時に行うことができることが理解できる。中間ドメインの送信元ノード側の境界ノードから宛先ノード側の境界ノードまでの経路の計算、および各ドメインの送信元ノード側の境界ノードから第１の経路が通過する対応するドメインの送信元ノード側の境界ノードまでの経路の計算も、計算を通して別の経路を取得し、ドメイン横断の分離された経路を取得するために、中間ドメインのPCEによって同時に行うことができる。本明細書では、詳細な説明を再び繰り返すことはしない。
【０１１１】
上記の実施形態は、ドメイン横断のリンク分離された経路を実現する方法を一例として利用することによって説明されたが、ドメイン横断のノード分離された経路も実現することができ、それは具体的な実施形態を通して以下で説明される。
【０１１２】
図７Ａは、本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第３の好ましい実施形態におけるネットワークの概略図である。ネットワークは、２つのドメイン、すなわち、ドメイン1と、ドメイン2とによって構成されている。計算を容易にするため、各々の２つのノード間のリンクの重みは、1に設定され、２つのドメインのPCEはそれぞれ、PCE1およびPCE2であり、それらはそれぞれ、R13およびR202に対応している。PCE1が経路計算要求メッセージを受信し、R11->R25の２つのリンク分離された経路が計算されるよう要求されると仮定する。これ以降、本発明の実施形態に従ってドメイン横断の分離された経路を実現する方法が、具体的なステップを用いて説明される。
【０１１３】
71.  第１の経路が計算される。
【０１１４】
第１の経路を計算するために、様々な方法を利用することができる。例えば、BRPC方法が利用され、その場合、ドメイン系列は、ドメイン1->ドメイン2と指定され、２つのPCEが、最短経路を、すなわち6の重みを有する(R11, R12, R21, R22, R23, R24, R25)を取得するために、対話的計算を実行する。具体的なステップは、リンク分離された経路を計算するプロセスにおいて第１の経路を計算するステップと同様であり、そのため、本明細書では、詳細を再び繰り返すことはしない。
【０１１５】
72.  第１の経路が計算された後、第２の経路が計算され始める。各PCEは、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、そのドメインのTEDを調整し、ある境界ノードから宛先ノードまでの経路の計算が失敗した状況下において、その境界ノードから、第１の経路が通過するこのドメインの同じ側の境界ノードまでの経路を計算する。詳細なプロセスが以下で提示される。
【０１１６】
721) PCE1は、R11->R25の経路を計算するため、経路計算要求メッセージをPCE2に送信し、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とを要求メッセージに保有する。
【０１１７】
計算される経路と第１の経路の間の分離関係情報は、リンク分離された、ノード分離された、リンク分離されるべき、または、ノード分離されるべき、とすることができる。この実施形態では、分離関係は、ノード分離された、であると指定される。
【０１１８】
722) PCE2は、宛先ノードが自らが管理するドメイン内に存在することを見出し、前のドメインに接続された境界ノードから宛先ノードまでの経路を計算し、経路応答メッセージを前のドメインのPCEに返す。
【０１１９】
この実施形態では、R21->R25およびR26->R25の経路がそれぞれ計算される。計算の前に、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報と従って、このドメインのTEDを調整することができる。具体的には、第１のリンクが通過するリンクの順方向が除外され、逆方向の重みが負にされ、経路内で3よりも大きい度数を有するノードが２つのノードに分割される。図７Ｂは、本発明の一実施形態による、ドメイン横断の分離された経路を取得するための方法の第３の好ましい実施形態におけるTED調整後のネットワークの概略図である。例えば、R21->R22の方向のリンクは除外され、R22->R21の方向のリンクの重みは-1となり、ノードR23はR23とR23'に分割される。R21->R25の経路の計算結果は、(R21, R26, R27, R23, R22, R28, R29, R24, R23', R201, R202, R25)であり、8の重みを有する。R26->R25の経路の計算結果は、(R26, R27, R23, R22, R28, R29, R24, R23', R201, R202, R25)であり、7の重みを有する。
【０１２０】
PCE2は、計算に成功した２つの経路についての情報を保有する経路応答メッセージを前のドメインのPCEに返し、この場合、前のドメインのPCEはR13である。
【０１２１】
723) PCE1は、上述の経路計算応答メッセージを受信し、計算される経路の送信元ノードがドメイン1内に存在することを見出す。そのため、PCE1は、ドメイン1の調整されたTEDと、PCE2によって返された経路情報とに従って、R11->R25の経路を、すなわち10の重みを有する(R11, R13, R14, R26, R27, R23, R22, R28, R29, R24, R23', R201, R202, R25)を計算する。
【０１２２】
73.  任意選択的に、ステップ72の計算を通して取得された第２の送信元ノードから宛先ノードまでの経路が、第１の経路と重なり合う部分を有するかどうかが決定され、有する場合、分離された経路を取得するために、ステップ72で取得された送信元ノードから宛先ノードまでの経路と第１の経路の間の重なり合う部分が調整される。
【０１２３】
731) PCE1は、以下の２つの経路
(R11, R12, R21, R22, R23, R24, R25)と、
(R11, R13, R14, R26, R27, R23, R22, R28, R29, R24, R23', R201, R202, R25)
を取得する。
【０１２４】
732) ２つの経路は、重なり合うリンクR22<->R23を有し、２つの経路はそれぞれ、２つの経路
(R11, R12, R21, R22, R28, R29, R24, R23, R201, R202, R25)と、
(R11, R13, R14, R26, R27, R23, R24, R25)
を取得するように調整される。
【０１２５】
733) ２つの調整された経路は、重なり合うリンク部分R24<->R23をさらに有し、２つの経路は、２つの経路
(R11, R12, R21, R22, R28, R29, R24, R25)と、
(R11, R13, R14, R26, R27, R23, R201, R202, R25)
を取得するように引き続き調整される。
【０１２６】
２つの経路が重なり合うリンク部分を有さない場合、２つのノード分離されたドメイン横断経路が取得されるように、２つの経路を調整する必要はない。
【０１２７】
各ドメインのTEDは、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にする方式で、上で言及されたように、第１の経路についての情報に従って調整される。他の実施方式も利用できることが理解できる。例えば、第１の経路が通過するリンクの順方向の重みを増加させることができ、好ましくは、リンクの順方向の重みを、リンクの順方向において実際値の重みよりもはるかに大きく設定することができ、例えば、他のリンクの重みがすべて100よりも小さい場合に、リンクの順方向の重みを10000に設定することができる。具体的な構成は、実際の戦略に従って設定することができる。
【０１２８】
上述の実施形態の各々では、２つのドメイン横断の分離された経路が取得される。実際に存在するドメイン横断の分離された経路がすべて取得でき、取得された３つ以上の経路は、第１の経路から分離されてさえいればよいこと、または計算される経路は、先に取得された経路の各々から分離されることが理解できる。具体的な選択は、経路の安全性および信頼性についてのシステムの要件に従って行うことができる。
【０１２９】
加えて、本発明の実施形態に従ってドメイン横断の分離された経路を取得するための方法を実現する能力を、すなわち分離関係情報を公表する能力をPCEが有するかどうかを、自動発見メッセージを通して、PCEについての自動発見情報で公表することができる。こうすることで、ドメイン横断の分離された経路を取得するために、そのような計算能力を有するPCEが選択され得る。
【０１３０】
第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、異なる経路が計算される場合、再帰的計算方式による上述の方法に加えて、各ドメインのPCEの計算を通して取得されたすべての結果をPCEのうちの１つに返す方式による方法を採用することもできる。PCEのうちのエンドノードドメイン内の１つに返す方式は、具体的には以下のステップを含む。
【０１３１】
第１の経路についての取得された情報と、計算される経路と第１の経路の間の分離関係情報とに従って、第１のエンドノードドメインのPCEは、第１のエンドノードから第１のエンドノードドメインの境界ノードまでの経路と、第１のエンドノードドメインの境界ノードから第１の経路が通過する第１のエンドノードドメインの境界ノードまでの経路とを計算し、計算された経路情報および第１の経路についての情報の他に、計算される経路と第１の経路の間の分離関係情報も、第２のエンドノードドメインのPCEに送信する。
【０１３２】
第２のエンドノードドメインのPCEは、第１のエンドノードドメインのPCEによって送信された第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、第２のエンドノードから第２のエンドノードドメインの境界ノードまでの経路を計算し、第２のエンドノードドメインの境界ノードから第１の経路が通過する第２のエンドノードドメインの境界ノードまでの経路を計算し、第１のエンドノードドメインによって計算された経路情報に従って、第１のエンドノードから第２のエンドノードまでの新しい経路を計算する。
【０１３３】
第１のエンドノードが送信元ノードである場合、第２のエンドノードは宛先ノードであり、第１のエンドノードが宛先ノードである場合、第２のエンドノードは送信元ノードである。
【０１３４】
第１のエンドノードから第２のエンドノードまでの経路が、少なくとも２つのドメインを横断する場合、中間ドメインのうちの各ドメインのPCEは、第１のエンドノード側の隣接ドメインによって送信された第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、中間ドメインの第１のエンドノード側の境界ノードと中間ドメインの第２のエンドノード側の境界ノードの間の経路を計算し、この中間ドメインの第１のエンドノード側の境界ノードから第１の経路が通過するこの中間ドメインの第１のエンドノード側の境界ノードまでの経路を計算し、計算された経路情報を第２のエンドノードドメインに送信する。一方、第２のエンドノードドメインのPCEは、中間ドメインのうちの各ドメインのPCEによって送信された経路情報と、第１のエンドノードドメインによって送信された、第１のエンドノードドメインのPCEによって計算された経路情報と、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、第１のエンドノードから第２のエンドノードまでの新しい経路を計算する。
【０１３５】
計算される経路と第１の経路の間の分離関係情報は、ノード分離された、リンク分離された、ノード分離されるべき、またはリンク分離されるべき、のいずれであるかを示す情報とすることができる。
【０１３６】
異なる分離関係情報に従って、異なる計算方法を利用することができる。例えば、第１のエンドノードから第２のエンドノードまでのリンク分離された経路の計算は、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にすること、または第１の経路が通過するリンクの順方向の重みを増加させ、逆方向の重みを負にすることを含むことができる。さらに、ドメイン横断のノード分離された経路を取得するため、上述の方法は、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にし、第１の経路内で3よりも大きい度数を有するノードを分割すること、または第１の経路が通過するリンクの順方向の重みを増加させ、逆方向の重みを負にし、第１の経路内で3よりも大きい度数を有するノードを分割することを含むことができる。
【０１３７】
加えて、第１のエンドノードから第２のエンドノードまでの新しい経路の計算が失敗した場合、計算に失敗したドメインのPCEは、そのPCEが属するドメインの境界ノードと、そのPCEが属し、第１の経路が通過するドメインの同じ側の境界ノードの間の経路を計算し、その経路を第２のエンドノードに返す。一方、第２のエンドノードドメインのPCEは、計算に失敗したドメインのPCEについての経路情報と、第１の経路についての情報と、計算される経路と第１の経路の間の分離関係情報とに従って、第１のエンドノードから第２のエンドノードまでの新しい経路を取得するために計算を行う。
【０１３８】
好ましくは、最大限分離された経路を取得するため、別の第１のエンドノードから第２のエンドノードまでの経路が第１の経路と重なり合う部分を有すると決定された場合、別の第１のエンドノードから第２のエンドノードまでの経路と第１の経路の間の重なり合う部分は、経路の信頼性を最大限高めるように調整することができる。
【０１３９】
上で説明されたように、本発明の実施形態で提供されるドメイン横断の分離された経路を取得するための方法が、添付の図面を用いて詳細に紹介された。当業者が本発明をより良く理解し、実施できるように、本発明の実施形態で提供されるPCEが、添付の図面を用いて以下で詳細に説明される。
【０１４０】
図８は、本発明の一実施形態による、PCEの第１の好ましい実施形態の概略構造図である。PCEは、情報取得サブユニット81と、経路計算サブユニット82と、情報送信サブユニット83とを含む。
【０１４１】
情報取得サブユニット81は、第１の経路についての経路情報を取得するように構成される。
【０１４２】
情報は、PCEから取得することができ、または情報は、他のPCEによって送信することができる。
【０１４３】
情報取得サブユニット81によって取得される情報は、第２の経路と第１の経路の間の分離関係情報をさらに含む。分離関係情報は、第１の経路から分離されているか、それとも分離されるべきかを示す情報を含み、具体的には、ノード分離された関係、リンク分離された関係、ノード分離されるべき関係、またはリンク分離されるべき関係を含む。そのような機能は、PCEが、分離された経路または分離されるべき経路の計算をサポートすることを可能にする。
【０１４４】
ノード分離されるべき関係は、送信元ノードから宛先ノードまでの異なる経路が通過するノードの中で、分離できるノードは分離され、分離できないノードは最大限分離される(すなわち、分離されていないノードの部分を有することが許容される)関係を表す。
【０１４５】
リンク分離されるべき関係は、送信元ノードから宛先ノードまでの異なる経路が通過するリンクの中で、分離できるリンクは分離され、分離できないリンクは最大限分離される(すなわち、分離されていないリンクの部分を有することが許容される)関係を表す。
【０１４６】
経路計算サブユニット82は、経路計算の機能を実行し、第１の経路についての経路情報に従って、第２の経路を計算するための経路情報を生成するように構成される。第２の経路を計算するための生成経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。２つの境界ノードは、経路計算終了ドメインに結び付けることができる。
【０１４７】
情報送信サブユニット83は、第２の経路を計算するための生成された経路情報を送出するように構成される。
【０１４８】
情報送信サブユニット83によって送信される情報は、第１の経路についての経路情報、および/または第２の経路と第１の経路の間の分離関係情報をさらに含む。
【０１４９】
PCEは、第１の経路についての取得された情報に従って、PCEが属するノードドメインの境界ノードと、PCEが属し、第１の経路が通過するノードドメインの境界ノードの間の経路についての経路情報を計算するために、他のPCEと連携して対話的計算を実行することができ、ノード分離されるべき経路またはリンク分離されるべき経路を計算することによって、実際に存在する分離された経路を計算し、その結果、分離された経路の計算の成功率が上昇し、それによって、ユーザの要件は可能な限り満たされ、経路伝送の信頼性が改善する。
【０１５０】
PCEの計算において、リンク分離された、または、リンク分離されるべきドメイン横断の分離された経路の計算は、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にすること、または第１の経路が通過するリンクの順方向の重みを増加させ、逆方向の重みを負にすることを含むことができる。
【０１５１】
ノード分離された、または、ノード分離されるべき経路の場合、PCEは、第１の経路が通過するリンクの順方向を除外し、逆方向の重みを負にし、同時に、第１の経路内で3よりも大きい度数を有するノードを分割することができ、または第１の経路が通過するリンクの順方向の重みを増加させ、逆方向の重みを負にし、同時に、第１の経路内で3よりも大きい度数を有するノードを分割することを含むことができる。
【０１５２】
上述のPCEは、自動発見情報を送信するように構成された自動発見情報送信サブユニットをさらに含む。自動発見情報では、情報取得サブユニット81によって取得された第１の経路に対する分離関係情報に従って、ドメイン横断の分離された経路を取得する機能をPCEがサポートするかどうかが識別され、その結果、システムは、自動発見情報に従って、本発明の実施形態で紹介されたようなドメイン横断の分離された経路を取得するための方法をサポートするPCEを見出し、そのPCEを用いて上述の計算を実行することができる。PCEは、集中化された計算または再帰的計算をサポートする。
【０１５３】
図９は、本発明の一実施形態による、PCEの第２の好ましい実施形態の概略構造図である。PCEは、情報取得サブユニット91と、経路計算サブユニット92と、情報送信サブユニット93とを含む。
【０１５４】
情報取得サブユニット91は、第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、２つの境界ノードは、経路計算終了ドメインに結び付けられ、境界ノードの一方は、第１の経路が通過するノードである。
【０１５５】
経路計算サブユニット92は、第１の経路についての取得された経路情報と、第２の経路を計算するための取得された経路情報とに従って、第２の経路を計算するための経路情報をさらに計算するように構成される。
【０１５６】
情報送信サブユニット93は、経路計算サブユニット92による計算を通して取得された経路情報を、他の経路計算ドメインに送信するように構成される。
【０１５７】
中間ドメイン内のPCEは、第１の経路についての情報に従って、PCEが属するドメインの境界ノードと、第１の経路が通過する境界ノード側のPCEが属するドメインの境界ノードの間の経路を計算するように構成される。PCEは、集中化された計算または再帰的計算をサポートする。PCEは、他のPCEと連携して対話的計算を実行し、その結果、実際に存在する分離された経路を計算し、分離された経路の計算の成功率を上昇させるために利用される。
【０１５８】
本発明の実施形態によれば、経路計算終了ドメイン内のPCEは、情報取得サブユニットと、経路計算サブユニットと、調整サブユニットとを含む。
【０１５９】
情報取得サブユニットは、第１の経路についての経路情報と、他の経路計算ドメインからの第２の経路を計算するための経路情報とを取得するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードであり、２つの境界ノードは、経路計算終了ドメインに結び付けられる。
【０１６０】
経路計算サブユニットは、第１の経路についての取得された経路情報と、第２の経路を計算するための経路情報とに従って、第２の経路を計算するように構成される。
【０１６１】
調整サブユニットは、２つの分離された経路または分離されるべき経路を取得するために、第１の経路および第２の経路についての経路情報を調整するように構成される。
【０１６２】
経路計算終了ドメイン内のPCEは、オプションのユニットを有する。PCEは、集中化された計算または再帰的計算をサポートする。PCEは、他のPCEと連携して対話的計算を実行し、その結果、実際に存在する分離された経路を計算し、分離された経路の計算の成功率を上昇させるために利用される。
【０１６３】
当業者が本発明の実施形態をより良く理解し、実施できるように、本発明の実施形態によって提供される経路計算システムについての詳細な説明が、以下で別の態様から与えられる。
【０１６４】
本発明の実施形態で提供される方法に対応して、本発明によって提供される経路計算システムは、対話的計算を実行して、２つのノードの間の経路を取得するように構成された少なくとも２つのPCEを含む。システムは、第１のPCEおよび第２のPCEを少なくとも含む。
【０１６５】
第１のPCEは、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、生成された経路情報を第２のPCEに送信するように構成される。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、２つの境界ノードは、第２のPCEが属するノードドメインに結び付けられ、境界ノードの一方は、第１の経路が通過するノードである。
【０１６６】
第２のPCEは、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報と、第１のPCEによって送信された経路情報とに従って、計算を行うように構成される。
【０１６７】
第２のPCEが経路計算終了ドメイン内のPCEである場合、第２のPCEは、計算を通して、２つのエンドノードの間の経路を取得する。
【０１６８】
第２のPCEが経路計算中間ドメイン内のPCEである場合、第２のPCEは、計算をさらに行い、計算結果を次のPCEに送信する。
【０１６９】
２つのエンドノードが隣接していない経路計算ドメインに属する場合、対話的計算に参加するPCEは、再帰的方式または集中化された方式で計算を実行する。システムによって実行される異なるアルゴリズムに対応するPCEが、以下のように説明される。
【０１７０】
PCEが再帰的計算を実行する場合、PCEのうちの再帰的計算に参加する、経路計算終了ドメインでない経路計算ドメインのPCEは、第１の経路についての取得された経路情報に従って、再帰的計算に参加する次のPCEが属するドメインに接続された、PCEが属するドメイン内の境界ノードと、経路計算開始ドメインのエンドノードの間の経路を計算し、計算を通して取得された経路情報を、再帰的計算に参加する次の経路計算ドメインに送信する。PCEのうちの再帰的計算に参加する経路計算終了ドメインのPCEは、前のPCEによって送信された経路情報に従って、２つのエンドノードの間の経路を計算する。必要であれば、経路計算終了ドメインのPCEは、２つの分離された経路または分離されるべき経路を取得するために、計算を通して取得された２つの経路についての経路情報を調整する。
【０１７１】
経路計算システムが集中化された計算を実行する場合、PCEのうちの集中化された計算を担当する１つは、他のPCEによって送信された経路情報を受信し、２つのエンドノードの間の経路を計算する。
【０１７２】
他のPCEによって送信された経路情報は、以下の内容を含む。
【０１７３】
PCEがエンドノードドメイン内に存在する場合、経路情報は、エンドノードドメインの境界ノードからエンドノードまでの経路についての経路情報である。
【０１７４】
PCEが中間ドメイン内に存在する場合、経路情報は、２つのエンドノードドメインにそれぞれ結び付けられる、中間ドメインの第１の境界ノードと第２の境界ノードの間の経路についての経路情報である。
【０１７５】
上述のPCEは、実際の要件に従ってさらに最適化できることが理解できる。例えば、自動発見情報を送信するために、自動発見情報送信サブユニットをPCEに提供することができる。自動発見情報では、メッセージ受信サブユニット81によって受信された情報に保有された第１の経路に対する分離関係情報に従って、ドメイン横断の分離された経路を取得する機能をPCEがサポートするかどうかが識別される。
【０１７６】
上述の実施形態における方法を実現するためのステップの全部または一部は、プログラムによって命令される関連ハードウェアによって達成できることを当業者であれば理解できよう。プログラムは、コンピュータ読み取り可能な媒体内に保存することができ、実行された場合に以下のステップを実施する。
【０１７７】
プログラムは、他のPCEと経路情報対話を実行し、第１の経路についての経路情報を取得し、第１の経路についての取得された経路情報に従って、第２の経路を計算するための経路情報を計算および生成し、生成された経路情報を他のPCEに送信する。第２の経路を計算するための経路情報は、２つの境界ノードの間の経路についての経路情報を含み、境界ノードの一方は、第１の経路が通過するノードである。
【０１７８】
上述の記憶媒体は、ROM(Read Only Memory)、磁気ディスク、または光ディスクとすることができる。
【０１７９】
本発明におけるドメイン横断の分離された経路を取得するための方法、PCE、および経路計算システムについての詳細な説明が上で提供された。当業者であれば、本発明のアイデアに従って、具体的な実施および適用範囲に関して、本発明に変形および変更を施すことができる。したがって、本明細書は、本発明に対する限定と解釈されるべきではない。
【符号の説明】
【０１８０】
81、91  ・・・  情報取得サブユニット
82、92  ・・・  経路計算サブユニット
83、93  ・・・  情報送信サブユニット
R1〜R19、R21〜R28、R23’、R31〜R38、R201、R202  ・・・  ノード
【図１】
2011505092.tif 000003
【図２】
2011505092.tif 000004
【図３】
2011505092.tif 000005
【図４】
2011505092.tif 000006
【図５】
2011505092.tif 000007
【図６】
2011505092.tif 000008
【図７Ａ】
2011505092.tif 000009
【図７Ｂ】
2011505092.tif 000010
【図８】
2011505092.tif 000011
【図９】
2011505092.tif 000012
【国際調査報告】
2011505092.tif 000013
2011505092.tif 000014
2011505092.tif 000015
2011505092.tif 000016