(57)【要約】  経路計算方法は、第１ボトムレベルＰＣＥにより経路計算命令を受信し、それにより管理されるルーティングドメインに関する経路計算を実行し、第１ノードを有する経路セグメントセットを、その上位レベルＰＣＥに送信し；下位レベルＰＣＥにより送信された経路セグメントセットを受信する上位レベルＰＣＥにより、第１ノードと第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに経路計算命令を送信し、全ての下位レベルＰＣＥにより送信される経路セグメントセットを受信し、トップレベルＰＣＥが、その全ての下位レベルＰＣＥにより送信された経路セグメントを受信するまで、全ての受信された経路セグメントを結合して、その上位レベルＰＣＥに送信し；そして、トップレベルＰＣＥにより、受信された経路セグメントセットを結合して、第１ノードと第２ノードとの間の経路のセットを生成する。
2011509014.tif 000002
【特許請求の範囲】
【請求項１】
第１ボトムレベル経路計算エレメント（ＰＣＥ）により、経路計算命令を受信し、前記第１ボトムレベルＰＣＥにより管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する第１ノードを含む経路セグメントセットを取得し、そして、前記取得された経路セグメントセットを、前記ボトムレベルＰＣＥの上位レベルＰＣＥに送信し、
下位レベルＰＣＥによって送信された前記経路セグメントを受信する前記上位レベルＰＣＥにより、前記第１ノードと第２ノードとの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、全ての下位レベルＰＣＥにより送信される経路セグメントを受信し、そして、トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信するまで、前記受信された全ての経路セグメントセットを結合して前記上位レベルＰＣＥの上位レベルＰＣＥに送信し、
前記トップレベルＰＣＥにより、前記受信された全ての経路セグメントセットを結合して前記第１ノードと前記第２ノードとの間の経路のセットを生成することを含む経路計算方法。
【請求項２】
前記上位レベルＰＣＥが一つの下位レベルＰＣＥのみを有する場合、前記上位レベルＰＣＥにより、受信された経路セグメントセットを前記上位レベルＰＣＥの上位レベルＰＣＥに送信する請求項１記載の方法。
【請求項３】
前記上位レベルＰＣＥにより他の下位レベルＰＣＥに送信される前記経路計算命令は、計算されるべき前記他の下位レベルＰＣＥの経路セグメントセットのエッジノード情報を含む請求項１記載の方法。
【請求項４】
計算されるべき前記他の下位レベルＰＣＥの前記経路セグメントセットの前記エッジノード情報は、下位レベルＰＣＥによって返されるエッジ経路セグメントセット情報に従って前記上記レベルＰＣＥによって計算される請求項３記載の方法。
【請求項５】
前記第１ボトムレベルＰＣＥにより前記経路計算命令を受信することは、
前記トップレベルＰＣＥにより、前記経路計算命令を前記第１ボトムレベルＰＣＥに送信すること、または
前記トップレベルＰＣＥにより、前記経路計算命令を前記トップレベルＰＣＥの下位レベルＰＣＥに送信し、前記トップレベルＰＣＥの前記下位レベルＰＣＥにより、前記第１ボトムレベルＰＣＥが前記経路命令計算を受信するまで、前記経路計算命令を前記トップレベルＰＣＥの前記下位レベルＰＣＥの下位レベルＰＣＥに送信することを含む請求項１記載の方法。
【請求項６】
前記第１ノードは、確立されるべき前記経路の起点ノードであり、且つ、前記第２ノードは、確立されるべき前記経路の目標ノードであり、または
前記第２ノードは、確立されるべき前記経路の前記起点ノードであり、且つ、前記第１ノードは、確立されるべき前記経路の前記目標ノードである請求項１記載の方法。
【請求項７】
前記第１ボトムレベルＰＣＥにより受信される前記経路計算明細は、前記第１ノードと前記第２ノードとの間に確立されるべき前記経路が順次的に通る前記ルーティングドメインに関する情報を含む請求項１記載の方法。
【請求項８】
経路計算命令を受信するように構成された経路計算命令受信モジュールと、
前記経路計算命令受信モジュールが前記経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベルＰＣＥに前記経路計算命令を送信するように構成され、とりわけ、一つの下位レベルＰＣＥにより返される経路セグメントセットを受信し、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、前記経路計算命令を他の下位レベルＰＣＥに送信するように構成された経路セグメント情報受信モジュールと、
前記経路セグメント情報受信モジュールにより受信された前記経路セグメントセットを結合して、該結合された経路セグメントセットを送信するように構成された経路結合モジュールと、
前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように構成された経路セグメントセット送信モジュールと
を備えた経路計算エレメント（ＰＣＥ）。
【請求項９】
前記受信された経路計算命令に従って当該ＰＣＥにより管理されるルーティングドメインの経路セグメントセットを計算し、前記経路セグメントセット送信モジュールに計算結果を送信するように構成された経路計算モジュールを更に備えた請求項８記載のＰＣＥ。
【請求項１０】
前記経路計算明細受信モジュールにより受信された前記経路計算命令は、エッジノード情報を含み、前記エッジノード情報は、前の下位レベルＰＣＥにより返されたエッジ経路セグメントセット情報に従って前記上位レベルＰＣＥにより計算される請求項８記載のＰＣＥ。
【請求項１１】
前記経路計算命令を受信し、
確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信し、とりわけ、一つの下位レベルＰＣＥによって返される経路セグメントセットを受信し、そして全ての下位レベルＰＣＥにより返される経路セグメントセットが受信されるまで、前記経路計算命令を他の下位レベルＰＣＥに送信し、
前記受信された経路セグメントセットを結合して、前記結合された経路セグメントセットを送信し、
前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信する経路計算方法。
【請求項１２】
トップレベル経路計算エレメント（ＰＣＥ）と、
第１ボトムレベルＰＣＥと、
上位レベルＰＣＥと
を備え、
前記トップレベルＰＣＥは、経路計算リクエストを受信し、前記経路計算リクエストに含まれる第１ノードと第２ノードに関する情報に従って、前記第１ノードと前記第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインを計算し、そして、経路計算命令を前記第１ボトムレベルＰＣＥに直接的に送信し、またはレベルごとに前記経路計算命令を前記第１ボトムレベルＰＣＥに送信するように構成され、
前記ボトムレベルＰＣＥは、前記経路計算命令を受信した後に、前記第１ボトムレベルＰＣＥによって管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する前記第１ノードを含む経路セグメントセットを取得し、そして、前記取得された経路セグメントセットを前記第１ボトムレベルＰＣＥの上位レベルＰＣＥに送信するように構成され、
下位レベルＰＣＥにより送信された前記経路セグメントセットを受信する前記上位レベルＰＣＥは、前記第１ノードと前記第２ノードとの間に確立されるべき前記経路が順次的に通る前記ルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、全ての下位レベルＰＣＥによって送信される経路セグメントを受信し、前記受信された経路セグメントセットを結合して、前記トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントを受信するまで、前記下位レベルＰＣＥによって送信される前記経路セグメントセットを受信する前記上位レイヤＰＣＥの上位レベルＰＣＥに送信するように構成され、
ここで、前記トップレベルＰＣＥは、前記受信された全ての経路セグメントセットを結合して前記第１ノードと前記第２ノードとの間の経路のセットを生成する経路計算システム。
【請求項１３】
ネットワークエレメントによって実施されるコンピュータプログラムコードを含むコンピュータプログラムプロダクトであって、前記ネットワークエレメントは：経路計算命令を受信し；確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信し、とりわけ、一つの下位レベルＰＣＥによって返された経路セグメントセットを受信して、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、他の下位レベルＰＣＥに前記経路計算命令を送信し；前記受信された経路セグメントセットを結合し、そして、前記結合された経路セグメントセットを送信し；そして、前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように起動されるコンピュータプログラムプロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明、通信の分野に監視、さらに詳しくは、経路計算方法及びシステム並びに経路計算エレメント（ＰＣＥ；Path Computation Element）に関する。
【０００２】
本願は、“ROUTE COMPUTATIN METHOD, ELEMENT AND SYSTEM”と題された、２００７年１２月２９日出願の中国特許出願第２００７１０１２５７２４．９に対する優先権の利益を主張するものである。
【背景技術】
【０００３】
通信ネットワークは、地理的に分散配置されたノードのセットおよびデータ伝送用のノード間の通信リンクからなる。通信ネットワークにおける非隣接ノード間の通信は、中間ノードを通じて実現され、これは通信ネットワークの資源をセーブし、資源の利用を改善する。現在、例えばＳＤＨ／ＳＯＮＥＴ(synchronous digital hierarchy/synchronous optical network)ネットワークやＩＰネットワークのような、種々のタイプのネットワークが存在する。通信ネットワークにおけるノードは、通常、ネットワークを介してデータフレームまたはパケットを交換することにより相互に通信を行い、フレームまたはパケットは、ＴＣＰ／ＩＰ(Transmission Control Protocol/Internet Protocol)のような特定のプロトコルで定義される。ここで、プロトコルは、ＴＣＰ／ＩＰのようなルールのセットを意味し、ノード間のインタラクション(inter-node interaction)を規定する。
【０００４】
通信ネットワークの規模が大きくなると、管理や保守が困難になる。従って、管理を容易化するために、通信ネットワークは、複数のルーティングドメイン(routing domains)または自律システム(AS; Autonomous systems)に分割されるのが通例となっている。一般に、ＡＳ内のネットワークでは、ドメイン内ルーティングプロトコル(intra-domain routing protocols)を実行する従来のドメイン間ルーター(inter-domain routers)は一緒に結合され、共通のパワーにより管理される。経路の柔軟性を改善する目的で、ＡＳは、通常、複数の領域に分割される。一般に、ドメインは、アドレス管理または経路計算責務の共通階級(common sphere)内のネットワークエレメントの任意の集まり(collection)である。ドメインの例は、エリア、ＡＳ、および複数のＡＳを含む。説明の容易化のため、ルーティングドメイン、ＡＳ、およびエリアは、ここではまとめてドメインと称す。ドメインの特定の意味は、その内容に依存する。ノードがデータ交換のために付加される場合、ドメイン間ルーティングプロトコルを実行するドメイン間ルーターが、異なるドメインのノードを相互接続するために導入される。このようなドメイン間ルーターは、また、ボーダールーター(border routers)と称される。
【０００５】
ドメイン間ルーティングプロトコルの例として、ＢＧＰ(Border Gateway Protocol)バージョン４がある。ＢＧＰは、システムにおける隣接ドメイン間ルーターの間で到達可能な情報および経路を交換することにより、ドメイン間ルーティングを実施する。ＢＧＰは、通常、接続およびセッションを確立するために、ＴＶＰのような信頼性のある伝送プロトコルを採用する。ドメイン内ルーティングプロトコルまたはＩＰ(Interior Gateway Protocol)の例としては、ＯＳＰＦ(Open Shortest Path First)ルーティングプロトコルがある。ＯＳＰＦプロトコルは、リンクステート技術に基づいており、従って、リンクステート・ルーティングプロトコルでもある。リンクステート・ルーティングプロトコルは、例えばＯＳＰＦプロトコルにおけるドメイン内ルーティング情報およびネットワークトポロジー情報を交換処理するモードを規定し、この情報は、ＬＳＡ(Link State Advisement)を通じて交換される。
【０００６】
ＭＰＬＳ(Multi-Protocol Label Switching)技術の出現および開発は、保証され利用可能な帯域幅(bandwidth)および高速な復旧(restoration)のような、データネットワーク開発の新たな要件を満たす。ＭＰＬＳ技術は、ＬＳＲ(Label Switch Path)を有するＩＰ／ＭＰＬＳネットワークにおけるエンド・ツウ・エンド・トンネル(end-to-end tunnels)の確立を可能にする。このようなトンネルは、一般に、ＬＳＰ(Label Switch Paths)と称される。ＬＳＰの確立は、ネットワークにおけるＬＳＲの経路の計算を含み、それは、一般に経路計算(route computation)と称される。
【０００７】
また、ＭＰＬＳ技術は光伝送ネットワークの分野に導入され、それに基づいてＡＳＯＮ(Automatically Switched Optical Network)が開発された。ＡＳＯＮは、手動または半自動構成を通じてネットワーク接続サービスを提供する従来の光伝送ネットワークとは異なり、制御プレーンの自動確立を通じてネットワーク接続サービスを提供する。ＡＳＯＮは、ネットワークサービスを運ぶ伝送プレーンと、管理機能を実施する管理プレーンと、制御プロトコルを稼動させる制御プレーンに分割される。
【０００８】
ＡＳＯＮの制御プレーンによって使用される技術は、ＧＭＰＬＳ(Generalized Multi-Protocol Label Switching)と称され、それは、ＬＭＰ(Link Management Protocol)、ルーティングプロトコル、およびシグナリングプロトコルを含むように、ＭＰＬＳ技術を拡張する。ＬＭＰは、近隣関係(neighboring relation)の発見に基づいて交換されるパケットを通じて資源の数とリンクによって支援される接続タイプを取得する。このような情報は、ＴＥ(Traffic Engineering)情報と称され、ＴＥ情報を含むリンクは、ＴＥリンクと称される。ドメイン内では、ローカルリンクＴＥ情報は、ＯＳＰＦ−ＴＥのようなルーティングプロトコルを通じてドメインにおける他のノードに通知される。この情報に基づいて、ネットワーク管理システムまたはユーザーがネットワークにネットワーク接続の確立を要求すると、この接続の入口ノード(ingress node)は、この接続のリンクシーケンスを取得するために経路計算を実行することができ、そして、ＲＳＶＰ−ＴＥ(Resource Reservation Protocol-Traffic Engineering)のようなシグナリングプロトコルを通じて、資源割り当てのために経路上のノードにリクエストを送信し、そして横断接続(cross connection)を確立し、これにより、エンド・ツウ・エンド接続を確立する。
【０００９】
ＩＰ／ＭＰＬＳおよび光伝送ネットワークの両方について、ドメインの分割は懸案事項である。とりわけ、ＴＥ管理機能を有するネットワークが複数のドメインに分割される場合、各ノードは他のドメインの到達可能な情報とローカルドメインのＴＥ情報のみを格納し、それは、輻輳回復(congestion recovery)と新規なサービス展開に関するネットワークトポロジーにおける変化の影響を低減し、ネットワーク拡張性を強化する。しかしながら、各ノードは、他のドメインの到達可能な情報およびローカルドメインのＴＥ情報を格納するのみであり、他の情報の完全なＴＥ情報を把握しないので、帯域幅、スイッチング機能、経路分離、保護、および複数ドメインの場合におけるユーザポリシーに関し、全ての要件を満足するエンド・ツウ・エンド経路をどのように計算するかを解決することが問題となる。
【００１０】
複数のドメインのケースにおけるルート(route)計算またはパス(path)計算（以下では、まとめて、経路計算と称す。）を解決するために、ドメイン−ドメイン経路プロトコル(DDRP; Domain-Domain Routing Protocol)は階層ネットワークモデルを採用し、このモデルでは、下位レベル(lower-level)のドメインは上位レベル(upper-level)にあるエージェントノードにより表される。エージェントノードは、アブストラクト・トポロジー(abstract topology)、ドメイン間リンク、ドメインを表す到達可能なアドレスを通知することができる。従って、階層ネットワークは具体化する。複数のドメインを横切るエンド・ツウ・エンド経路が計算され、リクエストを発したノードのドメインにおける正確な経路(strict route)と、ボーダーノードの後続の大まかな経路(loose route)が最初に計算される。シグナリンングが中間ドメインの境界に流れると、この中間ドメインにおける正確な経路がドメインボーダー計算などを通じて計算される。このような処理は、シグナリングが目標ノードのドメインに到達するまで継続的に実行される。
【００１１】
図１に示されるように、ドメインが複数の場合における経路計算を解決する他の技術、即ちＰＣＥ技術においては、各ＰＣＥは、ＰＣＥが取り扱うドメインの全てのＴＥ情報を格納する（ここでは、説明の容易化のため、ＴＥ情報はネットワークトポロジー情報を含む）。経路計算をリクエストするノードは、経路計算クライアント(PCC; Path Computation Client)と称される。ＰＣＣは、ＰＣＥへ経路計算パラメータを含むリクエストを送信し、ＰＣＥは、そこに格納されているＴＥＤ(Traffic Engineering Database)に従って経路計算を実行し、その結果をＰＣＣにフィードバックする。ＰＣＥは、１または２以上のドメインのＴＥ情報を格納してもよい。複数のドメインを横切る経路が計算されると、この経路がローカルＰＣＥのサービスエリアを越えていれば、ＰＣＥは、最終経路を計算するために、ＰＣＥＣＰ(Path Computation Element Communication Protocol)を使用して他の関連ＰＣＥと協調動作(collaborate)する。
【００１２】
本発明実施中に、本発明者は、従来技術が少なくとも次の問題を抱えていることを見つけた。
第１の従来技術により提供される解法によれば、経路計算は直列的処理(Serial process)である。先頭ノード(head node)では、経路が通る幾つかのドメインの入口(ingress)および出口(egress)情報のみが利用可能である。関連ドメインにおける実際のＴＥ情報は利用できないので、シグナリングが対応のドメインボーダーに流れてドメインボーダー計算を起動するまで、経路計算が入口から出口まで成功するかどうかを判断することができない。従って、利用可能な経路がないこと、またはどの経路も関連の制限事項を満足しないことを、伝送中にシグナリングが発見することが頻繁に発生する。結果として、経路確立は、複数回にわたってロールバック(roll back)され、そして前に確立された横断接続は、再確立のために除去されなければならない。加えて、この技術解法について、エンド・ツウ・エンドの別の経路（起点ノード及び目標ノードを同一としたときの別の経路）を計算することは困難である。
【００１３】
第２の従来技術は、フラット単一レベル(flat single-level)モデルを採用し、即ち、全てのＰＣＥが等しく重要である。ネットワークが複雑または大規模である場合、ＰＣＥを管理することは困難である。加えて、階層アブストラクション(hierarchical abstraction)はネットワークに適用されず、ドメイン横断経路計算は、もっぱら、異なるＰＣＥ間の異なるドメインのＴＥ情報の交換に依存する。サービスが多数のドメインを通貨すると、関連ＰＣＥ間の通信が頻繁になりすぎて、交換される情報の量が膨大になり、そのことは、経路計算の効率と信頼性を低下させる。
【発明の概要】
【課題を解決するための手段】
【００１４】
従って、本発明は、経路計算方法およびシステム、並びにＰＣＥを対象とし、それは、エンド・ツウ・エンドのドメイン横断の経路計算を効率的に実行することを可能とする。
【００１５】
一実施形態において、本発明は経路計算方法を提供し、それは次のステップを含む。
【００１６】
第１ボトムレベルＰＣＥは、経路計算命令を受信し、前記第１ボトムレベルＰＣＥにより管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する第１ノードを含む経路セグメントセットを取得し、そして、前記取得された経路セグメントセットを前記第１ボトムレベルＰＣＥの上位レベルＰＣＥに送信する。
【００１７】
下位レベルＰＣＥによって送信された経路セグメントセットを受信する上位レベルＰＣＥは、第１ノードと第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信し、そして、前記受信された全ての経路セグメントセットを結合して、トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信するまで、前記上位レベルＰＣＥの上位レベルＰＣＥに送信する。
【００１８】
トップレベルＰＣＥは、受信された全ての経路セグメントセットを結合して第１ノードと第２ノードとの間の経路セグメントのセットを生成する。
【００１９】
一実施形態において、本発明は、更に、経路計算命令受信モジュールと、経路セグメント情報受信モジュールと、経路結合モジュールと、経路セグメントセット送信モジュールを備える。
【００２０】
前記経路計算命令受信モジュールは、経路計算命令を受信するように構成される。
【００２１】
前記経路セグメント情報受信モジュールは、経路計算命令受信モジュールが経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って、一つずつ経路計算命令を下位レベルＰＣＥに送信するように構成される。詳しくは、経路セグメント情報受信モジュールは、一つの下位レベルＰＣＥによって返された経路セグメントセットを受信し、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、他の下位レベルＰＣＥに前記経路計算命令を送信するように構成される。
【００２２】
前記経路結合モジュールは、経路セグメント情報受信モジュールによって受信された複数の経路セグメントセットを結合して、該結合された経路セグメントセットを送信するように構成される。
【００２３】
前記経路セグメントセット送信モジュールは、前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように構成される。
【００２４】
一実施形態において、本発明は、また、経路計算方法を提供し、この経路計算方法は、次のステップを含む。
【００２５】
経路計算命令が受信される。
【００２６】
前記経路計算命令は、確立されるべき経路が通る一連のルーティングドメインに従って、一つずつ下位レベルＰＣＥを送信され；具体的には一つの下位レベルＰＣＥによって返された経路セグメントセットが受信され、そして、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、前記経路計算命令が他の下位レベルＰＣＥに送信される。
【００２７】
前記受信された経路セグメントセットは結合され、そして、この結合された経路セグメントセットが送信される。
【００２８】
前記受信され結合された経路セグメントセットは、上位レベルＰＣＥに送信される。
【００２９】
一実施形態において、本発明は、更に、経路計算システムを提供し、本経路計算システムは、トップレベルＰＣＥ、第１ボトムレベルＰＣＥ、及び下位レベルＰＣＥによって送信された経路セグメントセットを受信する上位レベルＰＣＥを備える。
【００３０】
前記トップレベルＰＣＥは、経路計算リクエストを受信し、該経路計算リクエストで搬送される第１ノードおよび第２ノードに関する情報に従って、前記第１ノードと前記第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインを計算し、経路計算命令を前記第１ボトムレベルＰＣＥに直接的に送信し、または前記経路計算命令を前記第１ボトムレベルＰＣＥにレベルごとに送信する。
【００３１】
前記第１ボトムレベルＰＣＥは、前記経路計算命令を受信した後に第１ボトムレベルＰＣＥによって管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する前記第１ノードを含む経路セグメントセットを取得し、そして、この取得された経路セグメントセットを第１ボトムレベルＰＣＥの上位レベルＰＣＥに送信する。
【００３２】
前記下位レベルＰＣＥによって送信された前記経路セグメントセットを受信する前記上位レベルＰＣＥは、前記第１ノードと前記第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、そして、前記受信された全ての経路セグメントセットを結合し、トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信するまで、前記下位レベルＰＣＥによって送信された経路セグメントセットを受信する前記上位レベルＰＣＥの上位レベルＰＣＥに送信する。
【００３３】
ここで、トップレベルＰＣＥは、受信された全ての経路セグメントセットを結合して、第１ノードと第２ノードの間の経路のセットを生成する。
【００３４】
以上から、経路セグメントセットを順次的に計算するための階層的手法を採用する本発明の技術的解法を通じて、エンド・ツウ・エンド・ドメイン横断経路計算が効率的に実行されることが把握される。
【図面の簡単な説明】
【００３５】
【図１】従来技術によるドメイン横断経路計算を示すネットワーク構成の図である。
【図２】本発明の一実施形態による経路計算方法を適用するネットワーク構成を示す図である。
【図３】本発明の一実施形態によるＰＣＥの構成を示す図である。
【発明を実施するための形態】
【００３６】
本発明の経路計算方法及びシステム並びに経路計算エレメント(PCE; Path Computation Element)は、添付の図面と実施例を参照して以下に説明される。
【００３７】
本発明の実施形態による経路計算方法は、例えば図２に示されるネットワーク構成に適用される。図２に示されるように、ネットワークは複数のレベルに分割される。複数のドメインが相互に接続されると、各ボトムレベルルーティングドメイン(bottom-level routing domain)について、１または２以上のＰＣＥが、直接的に、ドメイン内ルーティングトポロジー(intra-domain routing topology)及び該ドメインの経路計算を担い；そして、複数のボトムレベルルーティングドメインが上位レベルＰＣＥ(higher-level PCE)によって直接的に管理され、そして、この上位レベルＰＣＥは、ボトムレベルルーティングドメインのドメイン間ルーティングトポロジー(inter-domain routing topology)を有し、前記ルーティングドメインのドメイン内経路がこれにより直接的に管理され、同様にポリシーに基づいて幾つかのドメインのドメイン内ルーティングトポロジーも直接的に管理される。これに基づいて、ネットワーク全体がＰＣＥに基づく階層的アブストラクションによって管理される。ネットワークのレベルの数は制限されず、ネットワークの規模(scale)またはポリシーによって決定されてもよい。各ＰＣＥが担う全てのルーティングトポロジー（各下位レベルＰＣＥが担うルーティングトポロジーのセット）は、ＰＣＥの計算ドメインと称される。
【００３８】
複数のドメインが、本発明の実施形態で提案されるような大規模ネットワークにおいて相互接続されると、各ボトムレベルルーティングドメインについて、１または２以上のＰＣＥは、ドメイン内ルーティングトポロジーおよび該ドメインの経路計算を担う；そして、複数のボトムレベルルーティングドメインのＰＣＥは、上位レベルＰＣＥとしてアブストラクト(abstract)され、そして、上位レベルＰＣＥは、ボトムレベルルーティングドメインのドメイン間ルーティングトポロジーを有し、ポリシーに基づく幾つかのドメインのドメイン内ルーティングトポロジーも同様である。これに基づいて、ネットワーク全体は、ＰＣＥに基づく階層化アブストラクションにより管理される。ＰＣＥのレベルの数は制限されず、ネットワークの規模またはポリシーによって決定されてもよい。
【００３９】
本発明は、実施形態を通じて更に詳細に説明される。
【００４０】
図２に示されるように、最低ボトムレベル(bottommost level)（即ちレベル０）は、複数の経路ドメイン、即ちドメイン１、ドメイン２、ドメイン３、ドメイン４から構成されている。もちろん、レベル０は、また、ドメイン１、ドメイン２、ドメイン３、ドメイン４の他に、説明の簡略のためにここでは述べられない複数のルーティングドメインを有してもよい。各ボトムレベルルーティングドメインは、ドメインの経路計算およびルーティングトポロジーを担う直接的に対応するＰＣＥを有する。レベル０にあるＰＣＥは、ＰＣＥ０１、ＰＣＥ０２、ＰＣＥ０３、ＰＣＥ０４である。
【００４１】
ボトムレベルにあるＰＣＥが担うトポロジーはアブストラクト(abstract)されて、第１レベル（即ちレベル１）のトポロジーを形成し、そして、レベル１にあるＰＣＥは、そのトポロジーを担う。図に示されるように、ＰＣＥ０１およびＰＣＥ０２が担う複数のドメイン１およびドメイン２はアブストラクトされ、それにより、上記ドメインは、同計算ドメインに配置される。この計算ドメインは、上記ＰＣＥに対応するボトムレベルルーティングドメイン間の経路を有し、ＰＣＥ１１は計算を担う。ＰＣＥ１１が担うドメインのアブストラクトトポロジーは、上記ドメインのドメイン間リンク情報を含んでいる。ＰＣＥ１２のアブストラクション方法は、ＰＣＥ１１の方法と同様であり、従って、その詳細は重ねて説明しない。
【００４２】
レベル１のトポロジーは、より上位レベルにアブストラクトされてもよい。例えば、階層的アブストラクションは、更に、レベル１にあるＰＣＥ１１、ＰＣＥ１２、…、ＰＣＥ１Ｘが担うルーティングトポロジーの計算ドメインに適用され、レベル２にあるＰＣＥ２１は上記ルーティングトポロジーを担う。ＰＣＥ２１のルーティングトポロジーは、ＰＣＥ１１とＰＣＥ１２との間の相互接続情報を含む。他の例では、ポリシーに基づいて、ＰＣＥ２１は、また、ＰＣＥ１１およびＰＣＥ１２の内部経路情報を含んでもよい。
【００４３】
その一方、図示しないが、当業者であれば、上記の説明から、ＰＣＥ１１、ＰＣＥ１２、ＰＣＥ２１がボトムレベルＰＣＥ(bottom-level PCE)ではなく、ルーティングドメインを直接的に管理してもよいことが分かるであろう。この場合、ＰＣＥ１１、ＰＣＥ１２、ＰＣＥ２１により直接的に管理されるルーティングドメインは、それぞれ、レベル１、レベル１、レベル２に配置される。ＰＣＥ１１、ＰＣＥ１２、ＰＣＥ２１は、直接的にそのドメイン内経路を計算し、同様に、同じレベルにある他のＰＣＥの計算ドメインとルーティングドメインとの間の経路を計算する。この場合の経路計算方法は、基本的に、ドメイン内経路がボトムレベルＰＣＥによって計算されないことを除いては、本発明の上記実施形態における方法と同じであり、従って以下では別個の説明を省く。
【００４４】
同一または異なるレベルにあるＰＣＥは、ルーティングプロトコルを通じて（例えばＩＧＰまたはＢＧＰに基づいて）対応のルーティングトポロジー情報を配信(diffuse)する。同一レベルまたは異なるレベルにあるＰＣＥは、ＰＣＥ発見プロトコル(PCE Discovery Protocol)を通じてＰＣＥの機能および位置情報を配信する。
【００４５】
この実施形態では、起点ノード(source node)が、そのドメインのＰＣＥへの経路計算リクエストを起動すると、このリクエストを受信したＰＣＥは、上記リクエストメッセージに含まれる起点アドレスおよび目標アドレス情報に従って決定をなす。もし、上記リクエストされた目標ノード(destination node)が起点ノードと同じルーティングドメインになければ、そのドメインのＰＣＥは、各レベルにあるＰＣＥの機能情報に従って共通の上位レベルＰＣＥ(upper-level)（トップレベルＰＣＥとしてマークされる）を見つけ出す。上位レベルＰＣＥの計算ドメインは、起点ノードと目標ノードの両方をカバーし、これにより上位レベルＰＣＥが目標ノードへの経路の計算を完了する。
【００４６】
別の実施形態によれば、起点ノードからトップレベルＰＣＥ(top-level PCE)によって受信される経路リクエストメッセージは、経路を通るドメインシーケンスに関する情報を含んでも良い。もし、起点ノードの経路計算リクエストが、経路が通るドメインシーケンスに関する情報を含めば、トップレベルＰＣＥは、ドメインシーケンスに従って対応の経路計算を完了する。そうでなければ、トップレベルＰＣＥは、そのアブストラクトドメイン間トポロジー情報に従って、並びに、或るポリシーに従って（例えば最短のシーケンス）、全体ドメイン横断経路のドメインシーケンスを決定する。
【００４７】
トップレベルＰＣＥは、目標ルーティングドメインに隣接する下位レベルＰＣＥ(a lower-level PCE)（トップレベルＰＣＥの右側にマークされたもの）への経路計算リクエストを起動する。上記処理は、経路計算リクエストが目標ノードのドメインの最低ボトムレベルＰＣＥに送信されるまで繰り返される。
【００４８】
最低ボトムレベルＰＣＥは、ローカルドメインにおける対応の最適経路セグメントを計算し、その経路セグメントセットを上位レベルＰＣＥに返す。
【００４９】
経路計算リクエストを受信した後、上記対応の上位レベルＰＣＥは、上記返された経路セグメントセット情報に従って、上記経路計算リクエストを、それにより管理される他のＰＣＥに送信する。上記処理は、経路計算リクエストが、経路セグメントのドメイン出口が属するノードの最低ボトムレベルＰＣＥに送信されるまで繰り返される。
【００５０】
上位レベルＰＣＥは、上記経路セグメントセットが上記トップレベルＰＣＥに返されるまで、その上位レベルＰＣＥに上記計算された経路セグメントセットを返す。
【００５１】
上位レベルＰＣＥは、トップレベルＰＣＥの右側にある上記収集された経路セグメントセットに従って、その左側の下位レベルＰＣＥへの経路計算リクエストを起動する。この処理は、上記処理３，４，５，６と同様である。
【００５２】
最後に、トップレベルＰＣＥは、下位レベルＰＣＥによって返された経路セグメントセットを受信し、この経路セグメントセットに従って最適なエンド・ツウ・エンドのドメイン横断経路を計算し、そして、この最適な経路を先頭ノード(head nod)のボトムレベルＰＣＥに返す。
【００５３】
トップレベルＰＣＥによって送信された経路計算リクエスト確認通知(path computation request acknowledgement)を受信した後、先頭ノードのボトムレベルＰＣＥは、対応の経路情報を上記経路計算リクエストの先頭ノードに返す。
【００５４】
上記計算された経路情報を受信した後、先頭ノードは、シグナリングを起動して対応経路を確立する。
【００５５】
上述の処理は、エンド・ツウ・エンドのドメイン横断経路の計算に関するものであり、実際には、エンド・ツウ・エンドのドメイン横断の別の経路を計算するための本方法は、上述の処理と同様であり、従って、その詳細は重ねて説明しない。
【００５６】
図２に示されるように、この実施形態では、起点ノードはＮ１０であり、起点ノードによってリクエストされる目標ノードはＮ４０である。理解の容易化のために、この実施形態による本方法は、図示のために２つのサブ処理に分割され：即ち、１）トップレベルＰＣＥの決定と、２）経路計算である。具体的な処理は次のように説明される。
【００５７】
１）トップレベルＰＣＥの決定
ステップＳ１１において、Ｎ１０は、ＰＣＥ０１に経路計算リクエストメッセージを送信する。このメッセージは、起点ノードＮ１０に関する情報と、目標ノードＮ４０に関する情報を含む。
【００５８】
ステップＳ１２において、Ｎ１０を直接的に管理するＰＣＥ０１は、Ｎ１０によって送信される上記経路計算リクエストを受信し、ＰＣＥ０１は、それにより管理される計算ドメインのトポロジー情報を格納する。ＰＣＥ０１は、上記経路計算メッセージに含まれる起点および目標アドレスに従って判定を行う。この判定の結果は、Ｎ１０およびＮ４０が、これによって管理される計算ドメインに配置されていないということであり、従って、ＰＣＥ０１は、その経路計算リクエストメッセージを報告する。
【００５９】
ステップＳ１３では、図２から理解されるように、ＰＣＥ０１に直接的に対応する上位レベルＰＣＥは、ＰＣＥ１１である。上記報告された経路計算リクエストメッセージを受信した後、ＰＣＥ１１は、ＰＣＥ０１と同じ判定を行う。この判定の結果は、Ｎ４０がそれにより管理される計算ドメインに配置されていないということであり、従ってＰＣＥ１１は、継続的に経路計算リクエストメッセージを報告する。
【００６０】
ステップＳ１４では、ＰＣＥ１１によって報告された経路計算リクエストメッセージを受信した後、ＰＣＥ１２はＰＣＥ０１およびＰＣＥ１１と同様に判定を行う。この判定の結果は、起点ノードおよび目標ノードがＰＣＥ２１の計算ドメインに属しているということである。従ってＰＣＥ２１はトップレベルＰＣＥである。
【００６１】
注目すべきことは、ステップＳ１１−Ｓ１４において、トップレベルＰＣＥが、レベルごとに報告することにより決定されということである。他の実施形態では、ＰＣＥ０１は、また、他のＰＣＥの計算機能情報を直接的に格納してもよく、それにより、ＰＣＥ０１は、ＰＣＥ２１がトップレベルＰＣＥであることを直接的に決定し、そして、上記経路計算リクエストメッセージをＰＣＥ２１に直接的に送信することができる。
【００６２】
２）経路計算
ステップＳ２１において、ＰＣＥは、最適なドメインシーケンスを決定する。上記最適なドメインシーケンスの決定は、ネットワーク状態または各ドメインの特定的に構成されたポリシーに従って、上記経路が通るべきドメインを決定することにより実施されてもよく、ここでは、その詳細を説明しない。この実施形態では、ドメインシーケンスは、ドメイン１−ドメイン２−ドメイン３−ドメイン４であるものとする。
【００６３】
ステップＳ２２では、ＰＣＥ２１の直接的な下位レベルＰＣＥにおいて、Ｎ４０のドメイン４は、ＰＣＥ１２の計算ドメインに属し、従ってＰＣＥ２１は経路計算命令をＰＣＥ１２に送信する。この実施形態では、経路計算命令は最適なドメインシーケンスを含み、それに従って、各ドメインについての後続のドメイン内経路計算が実施される。
【００６４】
ステップＳ２３では、ＰＣＥ１２の直接的な下位レベルＰＣＥにおいて、ドメイン４はＰＣＥ０４の計算ドメインに属し、従ってＰＣＥ１２はＰＣＥ０４に経路計算命令を送信する。
【００６５】
ステップＳ２４では、ＰＣＥ０４は、経路計算命令を受信した後、ドメイン内経路計算を実行し、そして、最適なドメイン内経路セグメントセットをＰＣＥ１２に返す。この実施形態では、ＰＣＥ０４は、また、それにより計算されたドメイン内経路セグメントセットに対応する入口ノードセットに関する情報をＰＣＥ１２に送信する。この入口ノードは、ちょうど、ドメイン０４のエッジノードである。入口ノードセットに関する上記情報は、別個に送信されてもよく、または、経路セグメントセットに関する情報からＰＣＥ１２により取得されてもよい。
【００６６】
ステップＳ２５では、ＰＣＥ１２は、ＰＣＥ０４によって返される情報を受信し、この返された情報に含まれる各経路セグメントの入口ノードセットに従ってドメイン０３の出口ノードセットを決定し、経路計算のために目標ノードとして上記出口ノードセットを使用し、そして、上記経路計算命令をＰＣＥ０３に送信する。
【００６７】
ステップＳ２６では、ＰＣＥ０３は、ドメイン３における特定の出口ノードに達する最適な経路セグメントセットを計算し、そして、計算結果をＰＣＥ１２に返す。
【００６８】
ステップＳ２７において、ＰＣＥ１２は、ＰＣＥ０３によって返された情報を受信した後、各経路のエッジノードに従ってドメイン０３およびドメイン０４の最適な経路セグメントセットを結合し、ドメイン０３およびドメイン０４を横断する経路セグメントセットを計算し、そして、この計算結果をトップレベルＰＣＥ２１に返す。この実施形態では、上記結合は、出口ノード情報に従って実施される。
【００６９】
ステップＳ２８では、ＰＣＥ２１は、経路計算命令をＰＣＥ１１に送信し、そして、ステップＳ２２−Ｓ２７と同様の処理を実行し：即ち、ＰＣＥ１１は、ＰＣＥ１２によってＰＣＥ２１に返されたドメイン０３およびドメイン０４を横断する経路セグメントの入口ノードセットに従ってドメイン０２の出口ノードセットを決定し、そして、その出口ノードセットをＰＣＥ０２に送信し；ＰＣＥ０２は、ドメイン内経路セグメントセットを計算し、そして、そのドメイン内経路セグメントセットをＰＣＥ１１に返し；そして、ＰＣＥ０１はドメイン内経路セグメントセットを計算し、このドメイン内経路セグメントセットをＰＣＥ１１に返し；そして、最後に、ＰＣＥ１１は、ドメイン１及びドメイン２を横断する経路セグメントを結合する。
【００７０】
ステップＳ２９では、ＰＣＥ２１は、ドメイン０１及びドメイン０２を横断する経路セグメントセットと同様に、ドメイン０３及びドメイン０４を横断する経路セグメントセットに従ってＮ１０からＮ４０までの最適なドメイン横断経路セットを計算し、そして経路情報をＰＣＥ０１に返し、そして、最後に、ＰＣＥ０１は、その受信した経路計算結果をＮ１０に返す。他の実施形態では、ＰＣＥ２１が、更に、ルーティングドメインであるドメイン５を直接的に管理するものとすれば、ＰＣＥ２１は、ドメイン５のドメイン内経路セグメントセットを計算し、そして、ドメイン５の経路セグメントセット、ドメイン０３及びドメイン０４の経路セグメントセット、ドメイン０１及びドメイン０２を横断する経路セグメントセットを結合し、Ｎ１０からＮ４０までの最適なドメイン横断経路を計算する。
【００７１】
注目すべきは次のことである。他の実施形態において、もし、レベル０にはないＰＣＥがドメインを直接的に管理するものとすれば、その実施形態は、ＰＣＥのドメイン内経路セグメントがボトムレベルＰＣＥによって計算されないことを除いては、基本的に、この実施形態と同じである。例えば、この実施形態におけるＰＣＥ１２が、更に、他のドメインを直接的に管理するものとすれば、ＰＣＥ１２は、そのドメインのドメイン内経路セグメントセットを直接的に計算し、そして、ドメイン０３およびドメイン０４の経路セグメントを受信した後に、そのドメインの経路セグメントとドメイン０３及びドメイン０４の経路セグメントを結合する。この実施形態は、単に、一例として３レベル構成をとることで説明される。しかしながら、当業者であれば、本発明は、また、１レベルまたはそれ以上のレベルの構成にも適用できることが理解されるであろう。
【００７２】
ステップＳ２２及びＳ２３では、ＰＣＥ２１は、経路計算命令をＰＣＥ０４にレベルごとに送信する。他の実施形態では、ＰＣＥ２１は、また、ＰＣＥ０４に経路計算命令を直接的に送信してもよい。他の実施形態では、ステップＳ２４及びＳ２５において、入口ノードセット及び出口ノードセットを計算または送信しなくてもよいが、その代わり、ＰＣＥ０３は、ステップＳ２６において、ドメイン内トポロジー情報のみに従って経路計算を実行する。
【００７３】
上述の実施形態では、ドメイン４が最初に計算され、そしてドメイン１が最後に計算される。しかしながら、当業者であれば、この実施形態におけるシーケンスとは逆のシーケンスも他の実施形態において使用し得ること、即ち、ドメイン１が最初に計算され、ドメイン４が最後に計算されることを理解するであろう。
【００７４】
図３を参照すると、一実施形態において、本発明は、ＰＣＥを更に備え、それは、経路計算命令受信モジュール３１０、経路セグメント情報受信モジュール３２０、経路結合モジュール３３０、経路セグメントセット送信モジュール３４０を備える。
【００７５】
経路計算命令受信モジュール３１０は、経路計算命令を受信するように構成される。この経路計算命令は、トップレベルＰＣＥによって直接的に送信され、またはトップレベルＰＣＥによってレベルごとに伝送される。
【００７６】
経路セグメント情報受信モジュール３２０は、経路計算命令受信モジュール３１０が経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って経路計算リクエストを送信するように構成される。もしＰＣＥが複数の下位レベルＰＣＥを有していれば、経路セグメント情報受信モジュール３２０は、最初に、経路計算リクエストを第１下位レベルＰＣＥに送信し、そして、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、第１下位レベルＰＣＥによって返される経路セグメントセットを受信した後に上記経路計算リクエストを他の下位レベルＰＣＥに送信する。もちろん、もしＰＣＥが一つの下位レベルＰＣＥしか有していなければ、経路セグメント情報受信モジュール３２０は、経路計算リクエストを下位レベルＰＣＥに直接的に送信する。この実施形態では、後続の経路セグメント結合処理を容易化するために、他の下位レベルＰＣＥに送信される経路計算リクエストは、前の下位レベルＰＣＥによって返される出口ノードセット情報を含み、これにより、経路計算中に、ボトムレベルＰＣＥは、出口ノードセット情報に従って入口ノードセットを取得し、そして、その入口ノードをドメイン内経路セグメントのエンドポイントとすることにより経路計算を実行する。
【００７７】
経路結合モジュール３３０は、もし、確立されるべき経路が順次的に通るルーティングドメインに複数の下位レベルＰＣＥが存在すれば、経路セグメント情報受信モジュールによって受信された経路セグメントセットを結合して、より長い経路セグメントセットを生成し、そして、このより長い経路セグメントセットを経路セグメントセット送信モジュールに送信するように構成される。
【００７８】
経路セグメント送信モジュール３４０は、上記受信された経路セグメントセットを上位レベルＰＣＥに送信するように構成される。
【００７９】
この実施形態のＰＣＥは、更に経路計算モジュールを備え、経路計算モジュールは、ＰＣＥがボトムレベルＰＣＥである場合に、それにより管理されるルーティングドメインの経路セグメントセットを計算し、または、ＰＣＥがボトムレベルＰＣＥではなく、ルーティングドメインを直接的に管理する場合に、それにより直接的に管理されるルーティングドメインの経路セグメントセットを計算し、そして、計算結果を経路セグメントセット送信モジュール３４０に送信するように構成され、それにより、経路セグメントセット送信モジュール３４０は、上記経路セグメントセットを上位レベルＰＣＥに送信する。
【００８０】
この実施形態において、もし、最初に、確立されるべき経路の起点ノードから経路確立が開始すれば、最初に経路計算を実行するＰＣＥに加えて、他のルーティングドメインが、計算されたルーティングドメインと同じレベルに存在する場合、他のルーティングドメインのＰＣＥの経路計算モジュールが出口ノードセットに関する情報を計算し、そして、その情報を上記レベルＰＣＥに送信する。或いは、情報を個別に計算しなくてもよく、その代わり、上位レベルＰＣＥは、経路セグメントセットから情報を取得する。上位レベルＰＣＥは、出口ノード情報に従って次のルーティングドメインの入口ノードセットを生成し、そして、その入口ノードセットを次のドメインのＰＣＥに送信し、それにより、ＰＣＥは、その入口ノードセットに収集されたノードを、経路セグメントセットを計算するための経路の入口ノードとして使用する。他の実施形態では、もし、最初に、確立されるべき経路の起点ノードから経路確立が開始すれば、出口ノードセットは入口ノードセットに従って取得され、それは上述の状況と反対である。
【００８１】
一実施形態において、本発明は、経路計算システムを更に提供し、本経路計算システムは、トップレベルＰＣＥと、第１ボトムレベルＰＣＥと、下位レベルＰＣＥによって送信される経路セグメントを受信する上位レベルＰＣＥを備える。
【００８２】
トップレベルＰＣＥは、経路計算リクエストを受信した後に、確立されるべき経路が順次的に通るルーティングドメインを決定し、経路計算命令を送信するように構成される。上記経路計算リクエストは、第１ノードおよび第２ノードに関する情報を含むものであり、第１ノードと第２ノードの間に直接的な経路を確立することをリクエストするように構成されている。
【００８３】
第１ボトムレベルＰＣＥは、経路計算命令を受信した後に、それにより管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する第１ノードを含む経路セグメントセットを取得し、そして、その取得された経路セグメントセットを、その上位レベルＰＣＥに送信するように構成される。経路計算命令は、第１ボトムレベルＰＣＥにトップレベルＰＣＥにより直接的に送信されてもよく、または、レベルごとに第１ボトムレベルＰＣＥにトップレベルＰＣＥにより送信されてもよい。
【００８４】
下位レベルＰＣＥによって送信された経路セグメントセットを受信する上位レベルＰＣＥは、第１ノードと第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに経路計算命令を送信し、全ての下位レベルＰＣＥにより送信される経路セグメントセットを受信し、そして、トップレベルＰＣＥが、その全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信するまで、その上位レベルＰＣＥに上記受信した経路セグメントセットを結合して送信するように構成される。
【００８５】
ここで、トップレベルＰＣＥは、全ての受信した経路セグメントセットを結合して、第１ノードと第２位ノードの間の経路のセットを生成する。
【００８６】
本システムにおける各ＰＣＥは、経路計算命令受信モジュール３１０と、経路セグメント情報受信モジュール３２０と、経路結合モジュール３３０と、経路セグメントセット送信モジュール３４０を備える。
【００８７】
経路計算命令受信モジュール３１０は、経路計算命令を受信するように構成される。経路計算命令は、トップレベルＰＣＥによって直接的に送信され、またはレベルごとにトップレベルＰＣＥによって伝送される。
【００８８】
経路セグメント情報受信モジュール３２０は、経路計算命令受信モジュールが経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って経路計算リクエストを送信するように構成される。もし、ＰＣＥが複数の下位レベルＰＣＥを有すれば、経路セグメント情報受信モジュール３２０は、最初に、経路計算リクエストを第１下位レベルＰＣＥに送信し、そして、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、第１下位レベルＰＣＥによって返される経路セグメントを受信した後に上記経路計算リクエストを他の下位レベルＰＣＥに送信する。もちろん、もしＰＣＥが一つの下位レベルＰＣＥのみを有すれば、経路セグメント情報受信モジュール３２０は、直接的に、経路計算リクエストを下位レベルＰＣＥに送信する。この実施形態では、後続の経路セグメント結合処理を容易化するために、他の下位レベルＰＣＥに送信される経路計算命令は、前の下位レベルＰＣＥによって返される出口ノードセット情報を含み、それにより、経路計算中に、ボトムレベルＰＣＥは、上記出口ノードセット情報に従って入口ノードセットを取得し、そして、その入口ノードをドメイン内経路セグメントのエンドポイントとすることにより経路計算を実行する。
【００８９】
経路結合モジュール３３０は、もし、確立されるべき経路が順次的に通るルーティングドメインに複数の下位レベルＰＣＥが存在すれば、受信された経路セグメントセットを結合して、この結合された経路セグメントセットを送信するように構成される。
【００９０】
経路セグメントセット送信モジュール３４０は、上記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように構成される。
【００９１】
この実施形態のＰＣＥは、経路計算モジュールを更に備えてもよく、この経路計算モジュールは、下位レベルＰＣＥがボトムレベルＰＣＥである場合に、それにより管理されるルーティングドメインの経路セグメントセットを計算し、または、下位レベルＰＣＥがボトムレベルＰＣＥではなく、ルーティングドメインを直接的に管理する場合に、それにより直接的に管理されるルーティングドメインの経路セグメントセットを計算し、そして、計算結果を経路セグメントセット送信モジュール３４０に送信するように構成され、それにより、経路セグメントセット送信モジュール３４０は、経路セグメントセットを上位レベルＰＣＥに送信する。
【００９２】
この実施形態において、もし、最初に、確立されるべき経路の起点ノードから経路確立が開始すれば、他のルーティングドメインが、計算されたルーティングドメインと同じレベルに存在する場合、最初に経路計算を実行するＰＣＥに加えて、他のルーティングドメインのＰＣＥの経路計算モジュールは、出口ノードセットに関する情報を計算し、そして、その情報を上位レベルＰＣＥに送信する。或いは、情報を個別に計算しなくてもよく、その代わり、上位レベルＰＣＥは、経路セグメントセットから情報を取得する。上位レベルＰＣＥは、出口ノード情報に従って次のルーティングドメインの入口ノードセットを生成し、そして、その入口ノードセットを次のドメインのＰＣＥに送信し、それにより、ＰＣＥは、この入口ノードに収集されたノードを経路の入口ノードとして使用して、経路セグメントセットを計算する。他の実施形態では、もし、最初に、確立されるべき経路の起点ノードから経路確立が開始すれば、出口ノードセットが、入口ノードセットに従って取得され、それは、上述の状況と反対である。
【００９３】
当業者であれば、明らかに、上述の技術的解法におけるステップの一部または全部が、ハードウェアを通じて実施されもよく、または、必要な一般的ハードウェアプラットフォームをソフトウェアに加えたものを通じて実施されてもよいことを理解するであろう。これに基づいて、本発明の技術的解法は、ソフトウェアプロダクトの観点から実現されてもよい。ソフトウェアプロダクトは、不揮発性記録媒体（例えば、ＣＤ−ＲＯＭ、ＵＳＢフラッシュドライブ、またはリムーバブルハードディスク）に格納してもよく、本発明の実施形態による方法を実施するためにコンピュータ機器（例えば、パーソナルコンピュータ、サーバー、またはネットワーク機器）に命令するように構成された多くの命令を含む。
【００９４】
最後に、上述の実施形態は、単に、本発明の技術的解法を説明するためのものであり、本発明を何ら制限するものではないことに注目すべきである。本発明は、好ましい実施形態を参照して詳細に説明されたが、当業者であれば、本発明の特定の実施形態に対して変形がなされることが可能であり、または、本発明の技術的解法の原理を逸脱することなく、幾つかの技術的特徴に対して均等な置換がなされ得ることを理解し、そして、このような変形または均等な置換は、本発明の保護範囲に含まれる。
【符号の説明】
【００９５】
０１，０２，０３，０４，１１，１２，２１；ＰＣＥ
【図３】
2011509014.tif 000003
【図１】
2011509014.tif 000004
【図２】
2011509014.tif 000005
【手続補正書】
【提出日】平成22年7月23日(2010.7.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１ボトムレベル経路計算エレメント（ＰＣＥ）により、経路計算命令を受信し、前記第１ボトムレベルＰＣＥにより管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する第１ノードを含む経路セグメントセットを取得し、そして、前記取得された経路セグメントセットを、前記ボトムレベルＰＣＥの上位レベルＰＣＥに送信し、
下位レベルＰＣＥによって送信された前記経路セグメントを受信する前記上位レベルＰＣＥにより、前記第１ノードと第２ノードとの間に確立されるべき経路が順次的に通るルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、全ての下位レベルＰＣＥにより送信される経路セグメントを受信し、そして、トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントセットを受信するまで、前記受信された全ての経路セグメントセットを結合して前記上位レベルＰＣＥの上位レベルＰＣＥに送信し、
前記トップレベルＰＣＥにより、前記受信された全ての経路セグメントセットを結合して前記第１ノードと前記第２ノードとの間の経路のセットを生成することを含む経路計算方法。
【請求項２】
前記上位レベルＰＣＥが一つの下位レベルＰＣＥのみを有する場合、前記上位レベルＰＣＥにより、受信された経路セグメントセットを前記上位レベルＰＣＥの上位レベルＰＣＥに送信する請求項１記載の方法。
【請求項３】
前記上位レベルＰＣＥにより他の下位レベルＰＣＥに送信される前記経路計算命令は、計算されるべき前記他の下位レベルＰＣＥの経路セグメントセットのエッジノード情報を含む請求項１記載の方法。
【請求項４】
計算されるべき前記他の下位レベルＰＣＥの前記経路セグメントセットの前記エッジノード情報は、下位レベルＰＣＥによって返されるエッジ経路セグメントセット情報に従って前記上記レベルＰＣＥによって計算される請求項３記載の方法。
【請求項５】
前記第１ボトムレベルＰＣＥにより前記経路計算命令を受信することは、
前記トップレベルＰＣＥにより、前記経路計算命令を前記第１ボトムレベルＰＣＥに送信すること、または
前記トップレベルＰＣＥにより、前記経路計算命令を前記トップレベルＰＣＥの下位レベルＰＣＥに送信し、前記トップレベルＰＣＥの前記下位レベルＰＣＥにより、前記第１ボトムレベルＰＣＥが前記経路命令計算を受信するまで、前記経路計算命令を前記トップレベルＰＣＥの前記下位レベルＰＣＥの下位レベルＰＣＥに送信することを含む請求項１記載の方法。
【請求項６】
前記第１ノードは、確立されるべき前記経路の起点ノードであり、且つ、前記第２ノードは、確立されるべき前記経路の目標ノードであり、または
前記第２ノードは、確立されるべき前記経路の前記起点ノードであり、且つ、前記第１ノードは、確立されるべき前記経路の前記目標ノードである請求項１記載の方法。
【請求項７】
前記第１ボトムレベルＰＣＥにより受信される前記経路計算明細は、前記第１ノードと前記第２ノードとの間に確立されるべき前記経路が順次的に通る前記ルーティングドメインに関する情報を含む請求項１記載の方法。
【請求項８】
経路計算命令を受信するように構成された経路計算命令受信モジュールと、
前記経路計算命令受信モジュールが前記経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベルＰＣＥに前記経路計算命令を送信するように構成され、ここで、前記経路計算命令受信モジュールが前記経路計算命令を受信した後に、確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベルＰＣＥに前記経路計算命令を送信するように構成されることは、一つの下位レベルＰＣＥにより返される経路セグメントセットを受信し、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、前記経路計算命令を他の下位レベルＰＣＥに送信するように構成されることである経路セグメント情報受信モジュールと、
前記経路セグメント情報受信モジュールにより受信された前記経路セグメントセットを結合して、該結合された経路セグメントセットを送信するように構成された経路結合モジュールと、
前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように構成された経路セグメントセット送信モジュールと
を備えた経路計算エレメント（ＰＣＥ）。
【請求項９】
前記受信された経路計算命令に従って当該ＰＣＥにより管理されるルーティングドメインの経路セグメントセットを計算し、前記経路セグメントセット送信モジュールに計算結果を送信するように構成された経路計算モジュールを更に備えた請求項８記載のＰＣＥ。
【請求項１０】
前記経路計算明細受信モジュールにより受信された前記経路計算命令は、エッジノード情報を含み、前記エッジノード情報は、前の下位レベルＰＣＥにより返されたエッジ経路セグメントセット情報に従って前記上位レベルＰＣＥにより計算される請求項８記載のＰＣＥ。
【請求項１１】
前記経路計算命令を受信し、
確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信し、ここで、確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信することは、一つの下位レベルＰＣＥによって返される経路セグメントセットを受信し、そして全ての下位レベルＰＣＥにより返される経路セグメントセットが受信されるまで、前記経路計算命令を他の下位レベルＰＣＥに送信することであり、
前記受信された経路セグメントセットを結合して、前記結合された経路セグメントセットを送信し、
前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信する経路計算方法。
【請求項１２】
トップレベル経路計算エレメント（ＰＣＥ）と、
第１ボトムレベルＰＣＥと、
上位レベルＰＣＥと
を備え、
前記トップレベルＰＣＥは、経路計算リクエストを受信し、前記経路計算リクエストに含まれる第１ノードと第２ノードに関する情報に従って、前記第１ノードと前記第２ノードの間に確立されるべき経路が順次的に通るルーティングドメインを計算し、そして、経路計算命令を前記第１ボトムレベルＰＣＥに直接的に送信し、またはレベルごとに前記経路計算命令を前記第１ボトムレベルＰＣＥに送信するように構成され、
前記ボトムレベルＰＣＥは、前記経路計算命令を受信した後に、前記第１ボトムレベルＰＣＥによって管理されるルーティングドメインに関する経路計算を実行し、エンドポイントとして機能する前記第１ノードを含む経路セグメントセットを取得し、そして、前記取得された経路セグメントセットを前記第１ボトムレベルＰＣＥの上位レベルＰＣＥに送信するように構成され、
下位レベルＰＣＥにより送信された前記経路セグメントセットを受信する前記上位レベルＰＣＥは、前記第１ノードと前記第２ノードとの間に確立されるべき前記経路が順次的に通る前記ルーティングドメインに従って他の下位レベルＰＣＥに前記経路計算命令を送信し、全ての下位レベルＰＣＥによって送信される経路セグメントを受信し、前記受信された経路セグメントセットを結合して、前記トップレベルＰＣＥが該トップレベルＰＣＥの全ての下位レベルＰＣＥによって送信される経路セグメントを受信するまで、前記下位レベルＰＣＥによって送信される前記経路セグメントセットを受信する前記上位レイヤＰＣＥの上位レベルＰＣＥに送信するように構成され、
ここで、前記トップレベルＰＣＥは、前記受信された全ての経路セグメントセットを結合して前記第１ノードと前記第２ノードとの間の経路のセットを生成する経路計算システム。
【請求項１３】
ネットワークエレメントによって実施されるコンピュータプログラムコードを含むコンピュータプログラムプロダクトであって、前記ネットワークエレメントは：経路計算命令を受信し；確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信するように起動され、ここで、前記ネットワークエレメントは：経路計算命令を受信し；確立されるべき経路が通る一連のルーティングドメインに従って一つずつ下位レベル経路計算エレメント（ＰＣＥ）に前記経路計算命令を送信するように起動されることは、前記ネットワークエレメントが、一つの下位レベルＰＣＥによって返された経路セグメントセットを受信して、全ての下位レベルＰＣＥによって返される経路セグメントセットが受信されるまで、他の下位レベルＰＣＥに前記経路計算命令を送信し；前記受信された経路セグメントセットを結合し、そして、前記結合された経路セグメントセットを送信し；そして、前記受信され結合された経路セグメントセットを上位レベルＰＣＥに送信するように起動されることであるコンピュータプログラムプロダクト。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】削除
【補正の内容】
【国際調査報告】
2011509014.tif 000006
2011509014.tif 000007
2011509014.tif 000008
2011509014.tif 000009