(57)【要約】  本発明の第１の構成に従えば、複数のパケット交換ドメインに渡るエンドツーエンドルーティング経路を構築する方法が提供される。この方法は、取り得るすべてのドメイン、これらドメインの境界エレメント群、及びインター−ドメインリンク群を識別するドメイントポロジーを生成する。第１のドメインの発信元エンティティから第２のドメインの宛先エンティティへの、経路の計算に対するリクエストが受信される場合、リクエストされる経路で特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群が、ドメイントポロジーから除去される。次に、残っているドメインそれぞれに対する候補イントラ−ドメイン経路群が計算され、候補イントラ−ドメイン経路群のそれぞれが、境界エレメントである一端と、境界エレメントあるいは発信元エンティティまたは宛先エンティティであるもう一端の２つによって定義される論理リンクにマッピングされる。論理リンクそれぞれに対する属性とともに、残っているインター−ドメインリンク群の属性が判定される。論理リンクとそれに関連する属性を、残っているインター−ドメインリンク群とそれに関連する属性とを組み合わせることによって、仮想ネットワークトポロジーが生成される。これは、仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定することを可能にする。【選択図】  なし
2011515974.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上のコネクション型技術をサポートする複数のパケット交換ドメインに渡るエンドツーエンドルーティング経路を構築する方法であって、
取り得るすべてのドメイン、前記ドメインの境界エレメント群、及びインター−ドメインリンク群を識別するドメイントポロジーを生成するステップと、
第１のドメインの発信元エンティティから第２のドメインの宛先エンティティへの、経路の計算に対するリクエストを受信するステップと、
リクエストされる経路で特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群を、前記ドメイントポロジーから除去するステップと、
前記ドメイントポロジーに残っているドメインそれぞれに対する候補イントラ−ドメイン経路群を計算するステップと、
境界エレメントである一端と、境界エレメントあるいは前記発信元エンティティまたは前記宛先エンティティであるもう一端の２つによって定義される論理リンクに、前記候補イントラ−ドメイン経路群のそれぞれをマッピングするステップと、
前記論理リンクそれぞれに対する属性を判定するステップと、
前記ドメイントポロジーに残っているインター−ドメインリンク群の属性を判定するステップと、
前記論理リンク群とそれらに関連する属性を、前記ドメイントポロジーに残っているインター−ドメインリンク群とそれらに関連する属性とを組み合わせることによって、仮想ネットワークトポロジーを生成するステップと、
前記仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定するステップと
を備えることを特徴とする方法。
【請求項２】
前記ドメイントポロジーを生成するステップは、更に、
ドメインそれぞれのイントラ−ドメイン経路計算において、前記ドメインの境界エレメント群とそれらのインター−ドメインリンク群との詳細情報を含む、インター−ドメインデータを生成し、前記インター−ドメインデータを、エンドツーエンド経路計算エンティティへ送信するステップと、
前記エンドツーエンド計算エンティティにおいて、前記インター−ドメインデータを使用して、前記ドメイントポロジーを生成するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のドメインの発信元エンティティから第２のドメインの宛先エンティティへの、経路の計算に対するリクエストを受信するステップは、更に、
前記経路の宛先の詳細情報とその経路に対して要求される属性とを含むエンドツーエンド経路リクエストを生成し、前記エンドツーエンド経路計算エンティティへ送信するステップと
を備えることを特徴とする請求項１または２に記載の方法。
【請求項４】
リクエストされる経路で特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群を、前記ドメイントポロジーから除去するステップは、前記エンドツーエンド経路リクエストの受信に応じて、前記エンドツーエンド経路計算エンティティにおいて実行される
ことを特徴とする請求項２または３に記載の方法。
【請求項５】
前記ドメイントポロジーに残っているドメインそれぞれに対する候補イントラ−ドメイン経路群を計算するステップは、更に、
前記エンドツーエンド経路計算エンティティにおいて、ドメインそれぞれに対して、かつ前記発信元エレメントを含む前記発信元ドメイン及び前記宛先エレメントを含む前記宛先ドメインに対する、前記エンドツーエンド経路で特徴となるドメインそれぞれの前記境界エレメント群それぞれと前記エンドツーエンド経路によって要求される属性とを含む仮想ドメイントポロジーリクエストを生成するステップと、かつ前記仮想ドメイントポロジーリクエストを、前記発信元ドメインと、前記宛先ドメインと、及びその宛先ドメインまでの取り得るすべての中継ドメインとの、イントラ−ドメイン経路計算エンティティに実質的に同時に送信するステップと、
イントラ−ドメイン経路計算エンティティそれぞれにおける仮想ドメイントポロジーリクエストの受信に応じて、前記仮想ドメイントポロジーリクエストに対する前記候補イントラ−ドメイン経路を計算するステップと
を備えることを特徴とする請求項２乃至４のいずれか１項に記載の方法。
【請求項６】
前記論理リンクそれぞれに対する属性を判定するステップは、更に、
前記ドメイン内で計算される他の論理リンク群に関して、前記論理リンクの可用性／適合性を表すコストパラメータを判定するステップを備える
ことを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
請求項５に従属する場合に、前記仮想ネットワークトポロジーを生成するステップは、更に、
イントラ−ドメイン経路計算エンティティにおいて、仮想ドメイントポロジーリプライとして、識別される論理リンク群、前記論理リンク群とそれに関連する属性群とを特徴付ける前記境界エレメントと、前記発信元ドメインに対する前記発信元エレメントと前記宛先ドメインに対する前記宛先エレメントとを含む仮想ドメイントポロジーリプライを、前記エンドツーエンド経路計算エンティティへ送信するステップと、
前記エンドツーエンド経路計算エンティティにおける前記仮想ドメイントポロジーリプライの受信に応じて、前記論理リンク群とそれに関連する属性群とを、前記残っているインター−ドメインリンク群とそれに関連する属性群とを組み合わせるステップと
を備えることを特徴とする請求項５または６に記載の方法。
【請求項８】
リンクに対する属性は、前記リンクに対する前記ドメイン内で利用可能な総ネットワークリソースのパーセンテージとして与えられる
ことを特徴とする請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
イントラ−ドメイン経路計算エンティティにおいて、自身のインター−ドメインデータを監視し、かつ前記インター−ドメインデータの更新を、前記エンドツーエンド経路計算エンティティへ送信するステップを更に備える
ことを特徴とする請求項２乃至８のいずれか１項に記載の方法。
【請求項１０】
前記インター−ドメインデータがいくつかの定義されている閾値（群）を越える場合、前記インター−ドメインデータの更新を、前記エンドツーエンド経路計算エンティティへ送信するステップを更に備える
ことを特徴とする請求項９に記載の方法。
【請求項１１】
請求項５に従属する場合に、前記仮想ドメイントポロジーリクエストを生成するステップは、更に、前記仮想ドメイントポロジーリクエスト内に、前記イントラ−ドメイン経路計算エンティティによって判定される属性（群）の識別情報を含めるステップを備える
ことを特徴とする請求項５乃至１０のいずれか１項に記載の方法。
【請求項１２】
請求項５に従属する場合に、前記仮想ドメイントポロジーリクエストを生成するステップは、更に、前記仮想ドメイントポロジーリクエスト内に、前記候補イントラ−ドメイン経路群を計算するために、前記イントラ−ドメイン経路計算エンティティによって使用されるルーティングストラテジーあるいはアルゴリズムの識別情報を含めるステップを備える
ことを特徴とする請求項５乃至１１のいずれか１項に記載の方法。
【請求項１３】
パケットベースのコネクション型技術群をサポートする複数のドメイン群に渡るエンドツーエンドルーティング経路の構築を容易にする方法であって、
前記ドメインの境界エレメントから、前記ドメインの各境界エレメントに関連する情報と、該ドメインの境界エレメント群と他のドメイン群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ドメインデータを受信するステップと、
前記インター−ドメインデータを、エンドツーエンド経路計算エンティティに送信するステップと、
前記エンドツーエンド経路計算エンティティから、エンドツーエンド経路と、該エンドツーエンド経路によって要求される属性群とを特徴付けるドメインの境界エレメント群を含む仮想ドメイントポロジーリクエストを受信するステップと、
候補イントラ−ドメイン経路群を計算し、その計算された候補イントラ−ドメイン経路群それぞれの属性を判定するステップと、
境界エレメントである一端と、境界エレメントあるいは前記発信元エンティティまたは前記宛先エンティティであるもう一端の２つによって定義される論理リンクに、前記候補イントラ−ドメイン経路群のそれぞれをマッピングするステップと、
前記論理リンク群とそれに関連する属性群を含む仮想ドメイントポロジーリプライを、前記エンドツーエンド経路計算エンティティに送信するステップと
を備えることを特徴とする方法。
【請求項１４】
請求項１３に記載の方法を実行するように構成されている装置。
【請求項１５】
パケットベースのコネクション型技術群をサポートする複数のドメイン群に渡るエンドツーエンドルーティング経路を構築する方法であって、
イントラ−ドメイン経路計算エンティティ群から、前記ドメインの各境界エレメントに関連する情報と、該ドメインの境界エレメント群と他のドメイン群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ドメインデータを受信するステップと、
取り得るすべてのドメインと、前記ドメインの前記境界エレメントと、及び前記インター−ドメインリンク群を識別するドメイントポロジーを生成するステップと、
発信元エンティティから、経路の発信元と宛先の詳細情報と、その経路に対して要求される属性とを含むエンドツーエンド経路リクエストを受信するステップと、
前記経路を特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群を、前記ドメイントポロジーから、除去するステップと、
前記経路と、該経路によって要求される属性群とを特徴付けるドメインの境界エレメント群それぞれを含む仮想ドメイントポロジーリクエストをドメインそれぞれに対して生成するステップと、
前記仮想ドメイントポロジーリクエストを、前記発信元ドメイン、前記宛先ドメイン及び取り得るすべての中継ドメイン群のイントラ−ドメイン経路計算エンティティへ送信するステップと、
前記ドメインのそれぞれから、候補イントラ−ドメイン経路それぞれを表す論理リンク群と、及びそれに関連する属性群とを含む仮想ドメイントポロジーリプライを受信するステップと、
残っているインター−ドメインリンク群それぞれの属性を判定するステップと、
前記論理リンク群とそれに関連する属性群とを、前記残っているインター−ドメインリンク群とそれに関連する属性群とを組み合わせることによって、仮想ネットワークトポロジーを生成するステップと、
前記仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定するステップと
を備えることを特徴とする方法。
【請求項１６】
請求項１５に記載の方法を実行するように構成されている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コネクション型パケットベースアーキテクチャ（connection-orientied packet based architectures）における、エンドツーエンドトラフィックエンジニア化マルチドメインルーティング（end-to-end traffic engineered multi-domain routing）に関するものである。本発明は、特に、限定するものではないが、マルチプロトコルラベルスイッチング（ＭＰＬＳ：Multi-Protocol Label Switching）とその拡張（即ち、ＧＭＰＬＳ、Ｔ−ＭＰＬＳ）と、トラフィックエンジニア化プロバイダバックボーンブリッジング（ＰＢＢ−ＴＥ：Traffic Engineered Provider Backbone Bridging）に適用可能である。
【背景技術】
【０００２】
インターネットは、自律システム（ＡＳ）群あるいはドメイン群の集合であり、これは、管理権限と、様々な組織のルーティングポリシーを定義している。これらのドメインは、インテリアゲートウェイプロトコル（ＩＧＰ：Interior Gateway Protocol）群を実行するルータ群を構成している。インテリアゲートウェイプロトコルは、例えば、ルーティング情報プロトコル（ＲＩＰ）、拡張インテリアゲートウェイルーティングプロトコル（ＥＩＧＲＰ）、オープンショーテストパスファースト（Open Shortest Path First）、及び自身の境界内の中間システム対中間システム（Intermediate System-to-Intermediate System）がある。近隣ドメイン群は、エクステリアゲートウェイプロトコル（ＥＧＰ：Exterior Gateway Protocol）を介して相互に接続され、現在のインターネット規格ＥＧＰは、ＲＦＣ４２７１で定義される、境界ゲートウェイプロトコルバージョン４（ＢＧＰ−４）である。
【０００３】
エクステリアルーティングプロトコルは、ルーティングテーブルの拡張を制御し、かつインターネットを、それぞれが独自のルーティングポリシーと固有のＩＧＰを有する別々の管理組織あるいはドメインに分離することによって、より構造化されたインターネットを提供するために作成されている。
【０００４】
これらのルーティングプロトコルは、どのようにして、ルータが自身のネットワークの「マップ」を判定するかを定義している。このネットワークのマップから、ルータは宛先への最小経路を計算することができ、これにより、大規模な自動処理となるルーティングを可能にする。しかしながら、最小経路は、必ずしも最速あるいは最適とは限らない。トラフィックエンジニアリング（ＴＥ：Traffic Engineering）は、リソースの可用性と現在かつ予測トラフィックに従って、データがネットワークをルーティングされる処理である。要求されるサービス品質（ＱｏＳ）は、この処理にも織り込まれ得る。
【０００５】
トラフィックエンジニアリングは、オペレータの制御下にあっても良い。これによって、オペレータは、ネットワークの状態を監視し、トラフィックのルーティング、あるいは追加のリソースを提供して、オペレータで生じる問題を補償する。選択的には、トラフィックエンジニアリングは、自動化されていても良い。トラフィックエンジニアリングは、ネットワークプロバイダに、利用可能なリソースを最適に利用させて、レイヤー２リンクに渡って負荷を分散し、そして、あるクラスのトラフィックに対してあるいは特定の顧客に対していくつかのリンクを予約することを許容することを支援する。
【０００６】
新規の技術、例えば、トラフィックエンジニア化プロバイダバックボーンブリッジング（ＰＢＢ−ＴＥ：Traffic Engineered Provider Backbone Bridging）と、より標準化された技術、例えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）とその拡張版（即ち、ＧＭＰＬＳ、Ｔ−ＭＰＬＳ）は、自身の接続指向性のおかげで、単一のドメイン（即ち、イントラ−ドメイン（intra-domain））内で、有効なＴＥソリューションを提供する。しかしながら、すべての利用可能なサービスをエンドツーエンドでサポートするためには、将来のパケット交換ネットワークアーキテクチャは、ネットワーク間での適切なＱｏＳと、効率的なリソースの使用の両方を保障する必要がある。これは、ドメイン内かつドメイン間の両方で、経路全体、つまり、エンドツーエンドに対してトラフィックエンジニアリングを適用することができるルーティングソリューションを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
インター−ドメイン（ドメイン間）ＴＥルーティングに対する従来の方法は、ＢＧＰ−−ＴＥ（ＩＥＴＦ  draft-fedyk-bgp-te-attribute-03  「トラフィックエンジニアリング属性」）に基づいている。しかしながら、この方法は、ＴＥの制約を、インター−ドメイン（ドメイン間）経路の計算と、発信元ドメインと宛先ドメインのイントラ−ドメイン（ドメイン内）経路にのみ適用することができる。ＢＧＰ−ＴＥは、宛先に到達するために通過しなければならない、任意の中継ドメイン内のイントラ−ドメインに関する詳細情報を考慮しない。加えて、ＢＧＰベースの方法では、複雑なポリシーの制約が構成設定され得るが、ほとんどが、対等な契約と、経済的あるいは管理上の選択に対して行われている。リンク上の最大過負荷と中継リンク上で発生する輻輳のようなＴＥの制約は、依然としてサポートされていない。
【０００８】
米国特許出願第０９／９８１１３８は、中継ノードが、従来よりのＢＧＰ−ＴＥに従って選択される状態で、発信元ドメインと宛先ドメイン内の詳細なネットワークリソース情報を考慮するエンドツーエンド経路計算用のシステムを開示している。ＢＧＰ−ＴＥは、ルートとＴＥの重み付けに関する集約情報をネットワークに流し、その結果によって生じる、中継ドメインにおける詳細情報の損失は、効率的なエンドツーエンドＴＥ経路計算を不可能にしている。
【０００９】
マルチドメイン環境でのいくつかの制約（例えば、ＱｏＳ、帯域幅、優先度、保護等）を考慮する、エンドツーエンド経路の計算は、かなり深刻な問題である。ＴＥを使用して有効な経路を計算するためには、各ドメインからの詳細情報が要求される。この情報が詳細であればあるほど、経路計算はよりＴＥ要件を満足することになる。これは、より多くのドメインを組み込むために拡張する場合におけるスケーラビリティについての自明な問題である。加えて、多くのイントラ−ドメイン情報（例えば、リンクの状態、トポロジー、管理ポリシー等）は、ドメインの所有者／管理者が、そのような詳細情報を、ドメイン外部の他のドメインあるいは管理エンティティ群と共有することを望まないような機密情報であることが好ましい。このような理由から、高度化されたイントラ−ドメインＴＥストラテジーの使用は、エンドツーエンドインター−ドメイン経路の計算に適用される場合には限界がある。
【００１０】
規格化団体、例えば、ＩＥＴＦは、マルチドメインネットワーク環境を取り扱うために、通信プロトコルと関連アーキテクチャの定義を策定中である。これらは、クライアント−サーバアーキテクチャに基づいていて、ここでは、経路計算クライアント（ＰＣＣ）と呼ばれる汎用エンティティが経路リクエストを実行するクライアントを表していて、一方、経路計算エレメント（ＰＣＥ）がその経路リクエストを受信し、かつ経路計算を実行するエンティティとなっている（ＩＥＴＦ  ＲＦＣ４６５５−「経路計算エレメント（ＰＣＥ）ベースのアーキテクチャ」参照）。この規格では、通信プロトコルと、満足すべき要件（例えば、保護タイプ、優先度、性質）を定義している、一方で、マルチドメイン環境においてそのような要件を満足するためのソリューションは、規格化作業の範囲外となっている。
【課題を解決するための手段】
【００１１】
本発明の第１の構成に従えば、１つ以上のコネクション型技術をサポートする複数のパケット交換ドメインに渡るエンドツーエンドルーティング経路を構築する方法が提供される。この方法は、取り得るすべてのドメイン、これらドメインの境界エレメント群、及びインター−ドメインリンク群を識別するドメイントポロジーを生成する。第１のドメインの発信元エンティティから第２のドメインの宛先エンティティへの、経路の計算に対するリクエストが受信される場合、リクエストされる経路で特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群が、ドメイントポロジーから除去される。
【００１２】
次に、残っているドメインそれぞれに対する候補イントラ−ドメイン経路群が計算され、候補イントラ−ドメイン経路群のそれぞれが、境界エレメントである一端と、境界エレメントあるいは発信元エンティティまたは宛先エンティティであるもう一端の２つによって定義される論理リンクにマッピングされる。論理リンクそれぞれに対する属性とともに、残っているインター−ドメインリンク群の属性が判定される。
【００１３】
論理リンクとそれに関連する属性を、残っているインター−ドメインリンク群とそれに関連する属性とを組み合わせることによって、仮想ネットワークトポロジーが生成される。これは、仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定することを可能にする。
【００１４】
特定の実装では、ドメイントポロジーを生成するステップは、更に、ドメインそれぞれのイントラ−ドメイン経路計算において、ドメインの境界エレメント群と、それらのインター−ドメインリンク群の詳細情報を含む、インター−ドメインデータを生成し、そのインター−ドメインデータを、エンドツーエンド経路計算エンティティへ送信することを含んでいる。エンドツーエンド計算エンティティにおいて、インター−ドメインデータが、ドメイントポロジーを生成するために使用される。
【００１５】
この方法は、エンドツーエンド経路計算エンティティにおいて、ドメインそれぞれに対して、かつ発信元エレメントを含む発信元ドメイン及び宛先エレメントを含む宛先ドメインに対する、エンドツーエンド経路で特徴となるドメインそれぞれの境界エレメント群それぞれとそのエンドツーエンド経路によって要求される属性とを含む仮想ドメイントポロジーリクエストを生成し、かつ仮想ドメイントポロジーリクエストを、発信元ドメインと、宛先ドメインと、及びその宛先ドメインまでの取り得るすべての中継ドメインと、のイントラ−ドメイン経路計算エンティティに実質的に同時に送信することを含むことができる。イントラ−ドメイン経路計算エンティティそれぞれにおける仮想ドメイントポロジーリクエストの受信に応じて、仮想ドメイントポロジーリクエストに対する候補イントラ−ドメイン経路が計算される。
【００１６】
論理リンクそれぞれに対する属性を判定するステップは、ドメイン内で計算される他の論理リンク群に関して、論理リンクの可用性／適合性を表すコストパラメータを判定することを含むことができる。
【００１７】
イントラ−ドメイン経路計算エンティティは、仮想ドメイントポロジーリプライをエンドツーエンド経路計算エンティティへ送信することができ、この仮想ドメイントポロジーリプライは、識別される論理リンク群、論理リンク群とそれに関連する属性群とを特徴付ける境界エレメントと、発信元ドメインに対する発信元エレメントと宛先ドメインに対する宛先エレメントとを含んでいる。エンドツーエンド経路計算エンティティにおける仮想ドメイントポロジーリプライの受信に応じて、論理リンク群とそれに関連する属性群とを、残っているインター−ドメインリンク群とそれに関連する属性群とに組み合わせることができる。リンクに対する属性は、そのリンクに対するドメイン内で利用可能な総ネットワークリソースのパーセンテージとして与えられる。
【００１８】
各ドメインに対して仮想ドメイントポロジーリクエストを生成するステップは、仮想ドメイントポロジーリクエスト内に、イントラ−ドメイン経路計算エンティティによって判定される属性（群）の識別情報を含めることを含むことができる。仮想ドメイントポロジーリクエストは、更に、候補イントラ−ドメイン経路群を計算するために、イントラ−ドメイン経路計算エンティティによって使用されるルーティングストラテジーあるいはアルゴリズムの識別情報を含んでいても良い。
【００１９】
システムを動的にするために、イントラ−ドメイン経路計算エンティティは、そのインター−ドメインデータを監視し、かつ該インター−ドメインデータの更新を、エンドツーエンド経路計算エンティティへ送信することができる。インター−ドメインデータがいくつかの定義されている閾値（群）を越える場合、インター−ドメインデータの更新は、エンドツーエンド経路計算エンティティへ送信されても良い。
【００２０】
本発明の第２の構成に従えば、パケットベースのコネクション型技術群をサポートする複数のドメイン群に渡るエンドツーエンドルーティング経路の構築を容易にする方法が提供される。この方法は、ドメインの境界エレメントから、ドメインの各境界エレメントに関連する情報と、該ドメインの境界エレメント群と他のドメイン群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ドメインデータを受信することを含んでいる。次に、このインター−ドメインデータは、エンドツーエンド経路計算エンティティに送信される。続いて、仮想ドメイントポロジーリクエストがエンドツーエンド経路計算エンティティから受信され、この仮想ドメイントポロジーリクエストは、エンドツーエンド経路と該エンドツーエンド経路によって要求される属性群とを特徴付けるドメインの境界エレメント群を含んでいる。候補イントラ−ドメイン経路群が計算され、その計算された候補イントラ−ドメイン経路群それぞれの属性が判定される。次に、候補イントラ−ドメイン経路群のそれぞれが、境界エレメントである一端と、境界エレメントあるいは発信元エンティティまたは宛先エンティティであるもう一端の２つによって定義される論理リンクにマッピングされる。そして、論理リンク群とそれに関連する属性群を含む仮想ドメイントポロジーリプライが、エンドツーエンド経路計算エンティティに送信される。
【００２１】
属性を判定する処理を考慮する際に、Ｅ２Ｅ−ＰＣＥの経路計算基準が最小ホップ（minimum hop）である例を検討する。それゆえ、候補経路に関連付けられているコストは、経路の先頭エレメントから末端エレメントへ向かうためのホップ数（例、１０）となる。それゆえ、この数は、対応する論理リンクに関連付けられるコストとなる（即ち、その論理リンクを使用するドメインを通過するコストは、１０ホップの経路を介在する論理リンクのコストと同一である）。
【００２２】
本発明の第３の構成に従えば、パケットベースのコネクション型技術群をサポートする複数のドメイン群に渡るエンドツーエンドルーティング経路を構築する方法が提供される。この方法は、イントラ−ドメイン経路計算エンティティ群から、ドメインの各境界エレメントに関連する情報と、該ドメインの境界エレメント群と他のドメイン群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ドメインデータを受信することを含んでいる。取り得るすべてのドメインと、ドメインの境界エレメントと、及びインター−ドメインリンク群を識別するドメイントポロジーが生成される。エンドツーエンド経路リクエストが発信元エンティティから受信され、このエンドツーエンド経路リクエストは、経路の発信元と宛先の詳細情報と、その経路に対して要求される属性とを含んでいる。
【００２３】
経路を特徴付けることができないあるいは特徴付ける可能性のない、すべてのドメインとインター−ドメインリンク群は、ドメイントポロジーから除去され、経路と該経路によって要求される属性群とを特徴付けるドメインの境界エレメント群それぞれを含む仮想ドメイントポロジーリクエスト（群）が生成される。この仮想ドメイントポロジーリクエスト（群）は、発信元ドメイン、宛先ドメイン及び取り得るすべての中継ドメイン群と、のイントラ−ドメイン経路計算エンティティへ送信される。
【００２４】
仮想ドメイントポロジーリプライがドメインのそれぞれから受信され、この仮想ドメイントポロジーリプライは、候補イントラ−ドメイン経路それぞれを表す論理リンク群と、及びそれに関連する属性群とを含んでいる。残っているインター−ドメインリンク群それぞれの属性が判定され、論理リンク群とそれに関連する属性群とを、残っているインター−ドメインリンク群とそれに関連する属性群とを組み合わせることによって、仮想ネットワークトポロジーが生成される。そして、その仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートが判定される。
【図面の簡単な説明】
【００２５】
【図１】ＰＣＥベースのネットワークトポロジーと、その仮想ネットワークトポロジーへの変換を示す図である。
【図２】７つのドメインからなるＰＣＥベースのネットワークを示す図である。
【図３】図２のネットワークのドメインＤ４とＤ５、それらのインターリンク群、ドメイントポロジー（ＤＴ）を生成するためにインターＰＣＥによって収集される情報のタイプを示す図である。
【図４】図２のネットワークのドメイントポロジーを示す図である。
【図５】表２の経路リクエストに従う図４のドメイントポロジーのプルーン処理と、その結果であるプルーン化ドメイントポロジー（ＰＤＴ）を示す図である。
【図６】図６ａは図２のネットワークのイントラドメインとインタードメイン内の候補経路を示す図であり、図６ｂは仮想ドメイントポロジーに組み合わせられている図２のネットワークの仮想リンクを示す図であり、図６ｃは図２のネットワークの仮想ネットワークトポロジーを示す図である。
【図７】ドメイントポロジーを生成し、かつ更新する処理を示すフロー図である。
【図８】エンドツーエンド最適経路を計算する処理を示すフロー図である。
【図９】本発明の実施形態に従う発信元エンティティを示す図である。
【図１０】本発明の実施形態に従うイントラ−ドメイン経路計算エンティティを示す図である。
【図１１】本発明の実施形態に従うエンドツーエンド経路計算エンティティを示す図である。
【発明を実施するための形態】
【００２６】
パケットベースのコネクション型技術に対するエンドツーエンドルート判定処理は、本明細書では、ルート上のイントラ−ドメイン（ドメイン内：intra-domain）エレメントとインター−ドメイン（ドメイン間：inter-domain）エレメントの両方からのすべての情報を含む、異種仮想トポロジーを使用する。ネットワークのトポロジーは、２つのレイヤー、つまり、イントラ−ドメインレイヤーとインター−ドメインレイヤーに分離される。インター−ドメインレイヤーは、実在（リアル）エレメントと仮想エレメントの両方から構成される異種仮想トポロジーに関連している。そのエレメントには、発信元ドメイン、宛先ドメイン及び任意の中継ドメイン群、の境界エレメント（ＢＥ）群と、異なるドメイン群を接続する物理インター−ドメインリンク（インターリンク）群と、発信元ドメインの発信元ノードと、宛先ドメインの宛先ノードと、各中継ドメインのすべてのＢＥ群を接続する論理リンク（ＬＬ）群と、及び発信元ドメイン／宛先ドメインのＢＥ群を発信元ノード／宛先ノードに接続する論理リンク群とがある。イントラ−ドメインレイヤーは、各ドメインの実（リアル）トポロジーに関連する。これは、発信元ドメインと、宛先ドメインと、及び中継ドメイン群のそれぞれからなる。各ドメインは、更に、相互に接続されているいくつかのイントラ−ドメインノードからなり、これは、発信元ドメインと宛先ドメイン内それぞれの発信元ノードと宛先ノード、及びドメインＢＥ群とを含んでいる。
【００２７】
以下の説明のために、ネットワークアーキテクチャは、ＰＣＥベースであり、各ドメインは、イントラ−ドメインルーティングの計算を担当する少なくとも１つのイントラ−ドメインＰＣＥ（イントラ−ＰＣＥ）を有し、また、イントラ−ドメインルーティングとインター−ドメインルーティングを組み合わせた、全体のエンドツーエンドルートの計算を担当する少なくとも１つのエンドツーエンドＰＣＥ（Ｅ２Ｅ−ＰＣＥ）が存在する。
【００２８】
図１は、ＰＣＥベースのネットワークトポロジーと、それを変換したものである仮想ネットワークトポロジーの簡略図を示している。ネットワークの完全なトポロジーは、下図の破線で示されていて、また、発信元ドメインＤ１の発信元と、宛先ドメインＤ３の宛先と、及び１つの中継ドメインＤ２を特徴付けている。ドメインのそれぞれは、いくつかの相互に接続されているノード群あるいは内部エレメント（ＩＥ）群と、境界エレメントと、及びイントラ−ＰＣＥとを含んでいる。ドメインＤ１の境界エレメント群は、中継ドメインＤ２の境界エレメントに接続されている。ドメインＤ２の他の境界エレメント群は、宛先ドメインＤ３の境界エレメント群に接続されている。
【００２９】
各イントラ−ＰＣＥは、自身のドメインネットワークのトポロジーを関知していて、かつ周知のＴＥルーティング方法に従ってドメイン内のＴＥルーティングを計算することができる（例えば、イントラ−ドメイン経路選択基準、メトリック、ポリシー、ルール及びターゲット機能群）。イントラ−ＰＣＥは、これらの方法を使用して、イントラ−ドメインノード群と境界エレメント群との間の「最適」候補経路群を判定し、あるいは、そのドメインが、通過されるべき中継ドメインである場合には、ドメインのそれぞれの境界エレメント群との間の「最適」候補経路群を判定する。異なるドメインによって計算される候補経路群は、異なる基準に従って「最適」であると定義され、そうすることで、異なるドメインそれぞれの各最適経路に関連付けられている局所的なコストパラメータは異なる意味を有することになる。
【００３０】
これらの候補経路は、論理リンク（ＬＬ）群に変換され、これは、その２つのエンドポイントによってドメインを通過する経路を定義する。これらの論理リンク群は、インター−ドメインリンク群と、また、ソースノードと宛先ノードと、更にまた、ＢＥ群とに接続されて、図１の破線で示されるように、仮想ネットワークトポロジー全体を形成している。
【００３１】
加えて、イントラ−ＰＣＥは、候補経路のコストを、論理リンク群のそれぞれに対して１つ以上のコストに変換する。これらのコストは、ＴＥルーティング方法（例えば、インター−ドメイン経路選択基準、メトリック、ルール及びターゲット機能群）に従って、エンドツーエンド最適経路（Ｅ２Ｅ−ＢＰ）を計算するために、Ｅ２Ｅ−ＰＣＥによって必要とされるパラメータ群（あるいはそららの抜粋）として選択される。これは、異なるドメイン内のＬＬ群のコストに制約を与えることを可能にし、また、それらに、インター−ドメインリンクコストの制約を与えることを可能にする。
【００３２】
挑戦的な問題である、トラフィックのバランシング（balancing：バランスを取ること）は、ドメイン内で計算される他のＬＬ群に関して、あるＬＬの可用性／適合性を表すＬＬコストパラメータを選択することによって達成することができる。これらのコストのパラメータは、所望のルーティング目的に従って判定される。例として、論理リンクの属性は、「等価可用リソース（ＥＡＲ：Equivalent Available Resources）」と呼ばれる、論理リンクに対応する候補経路に対して利用可能なドメイン内の全体ネットワークリソースのパーセンテージとして与えられ得る。このようなパラメータは、すべてのドメインに渡って容易に比較可能であろう。Ｅ２Ｅ−ＰＣＥは、複数のドメインに渡る適切なエンドツーエンド経路を計算するために、リンクに関連する属性を使用することができる。
【００３３】
一例として、図６ｂの仮想ドメイントポロジーＶＤＴ２を検討する。これは、４つのＬＬ（ＬＬ１、ＬＬ２、ＬＬ３、ＬＬ４）からなる。ここで、更に、ドメイン（Ｄ２）のイントラ−ＰＣＥが、以下の式に従って、ＥＡＲ値をＬＬ群に割り当てると仮定する。
【００３４】
ＥＡＲ＝［ＡＡＢＷ＋（１００−ＡＮＬ）］／２
ここで、ＡＡＢＷは、すべてのリンクの平均可用帯域幅であり、ＡＮＬは論理リンクに対応する候補経路に沿うすべてのノードの平均ノード負荷である。以下の表１は、４つのＬＬに対する、ＡＡＢＷのパーセンテージとＡＮＬを示している。このような状況では、すべての他の条件が等しい場合、Ｅ２Ｅ−ＰＣＥは、Ｄ２を通過するためにＬＬ１を選択することになる。これは、ＬＬ１は、より高いＥＡＲを有しているので、トラフィックは、そのＬＬを使用することでよりバランスが取れるからである。
【００３５】
このソリューションの適用は、２つのフェーズを要求する。ドメイントポロジー（ＤＴ）の作成と、エンドツーエンド最適経路（Ｅ２Ｅ−ＢＰ）の計算である。このドメイントポロジー（ＤＴ）の作成では、ドメイン群はノード群と見なされ、それらの境界エレメント群はノードポート群と見なされる。
【００３６】
フェーズ１：ドメイントポロジー生成
ドメイントポロジーの生成は、特定の経路リクエストから独立している。これは、その目的が、Ｅ２Ｅ−ＰＣＥに、ネットワークのグローバルなインター−ドメインビューを与えることであるからである。それゆえ、このフェーズは、オフラインで実行される。
【００３７】
図７のフロー図を参照すると、フェーズ１の処理は、ステップ１００で開始する。最初に、ステップ１０１で、各イントラ−ＰＣＥは、Ｅ２Ｅ−ＰＣＥに、自身のドメインに関する情報のセット（ドメイン情報）と、ドメインの境界エレメントと、それらのインター−ドメインリンク群（インターリンク情報）に関する情報のセットとを送信する。ドメイン情報は、あるドメインから別のドメインへ送られる管理属性のようなパラメータであり得る（サービスレベル契約及びサービスレベル仕様の少なくとも一方に従って）。このインターリンク情報は、例えば、リンク帯域幅あるいは境界エレメントの負荷のような、インターリンク群と境界エレメント群との両方に関するパラメータであり得る。ステップ１０２で、この情報を使用して、Ｅ２Ｅ−ＰＣＥは、ドメイントポロジーを作成する。
【００３８】
ステップ１０３で、各イントラ−ＰＣＥは、イントラ−ドメインネットワークリソース（ＩＧＰ−ＴＥ／ＥＧＰ−ＴＥ、例えば、ＯＳＰＦ−ＴＥ／ＢＧＰ−ＴＥ）を監視し、それに従って、自身のドメイン情報とインターリンク情報を更新する。ネットワーク上のトラフィックを削減するために、ステップ１０４及び１０５で、イントラ−ＰＣＥ群は、いくつかの閾値を越えることによって定義される、これらの変更が深刻である場合にのみＥ２Ｅ−ＰＣＥに通知する。次に、ＤＴは、Ｅ２Ｅ−ＰＣＥが新規のパラメータをイントラ−ＰＣＥから受信する場合に更新され得る。この処理は、ステップ１０６で終了する。
【００３９】
フェーズ２：エンドツーエンド最適経路計算
この処理は、図８のフロー図で示され、ステップ２００で、開始する。発信元ノードがデータを宛先ノードへ送信することを想定する。発信元ノードは、宛先の詳細情報と、経路に対する任意の制約とを含む、メッセージあるいは経路リクエストを生成する。この経路リクエストは、Ｅ２Ｅ−ＰＣＥへ直接送信される、あるいは発信元ドメインのイントラ−ＰＣＥを介して送信される。
【００４０】
発信元ノードからの経路リクエストの受信後、ステップ２０１で、Ｅ２Ｅ−ＰＣＥは、経路リクエスト内で特定される、ドメイントポロジー情報と任意の制約を使用して、経路内で特徴付けることができない、ドメイン群及びインターリンク群の少なくとも一方を「プルーン（prune：除去）」する。
【００４１】
次に、ステップ２０２で、Ｅ２Ｅ−ＰＣＥは、経路リクエスト群を残りのドメイン群のイントラ−ＰＣＥ群へ同時に送信する。この経路リクエストは、それらに、特定の経路リクエストに適切であるイントラ−ドメイン論理リンク群と、各リンクに関連する属性を提供することを要求する。
【００４２】
ステップ２０３で、各イントラ−ＰＣＥは、任意の適切なＴＥルーティング方法（群）を使用して、特定の経路リクエストに対する取り得る候補経路群を計算する。発信元ドメインのイントラ−ＰＣＥは、発信元とドメインの境界エレメント群とを接続する候補経路群を計算し、中継ドメインイントラ−ＰＣＥ群は、自身の境界エレメント群を相互に接続する候補経路群を計算し、宛先ドメインのイントラ−ＰＣＥは、自身の境界要素群と宛先とを接続する候補経路群を計算する。経路リクエストがある制約（例えば、ＲＦＣ２７０２で定義される性質、ディスジョイント性（disjointness）あるいは経路分離、保護等）を含んでいる場合、イントラ−ＰＣＥは、また、これらの要件を合致させるために、各経路の適切性を判定する。次に、ステップ２０４で、各経路は、適切な属性パラメータに従って、論理リンクに変換されて、Ｅ２Ｅ−ＰＣＥに提供される。次に、ステップ２０６で、Ｅ２Ｅ−ＰＣＥは、任意の適切なＴＥルーティング方法を、これらの論理リンク群とインターリンク群との組み合わせに適用し、すべてのリンク群に関連する属性を考慮する、最適なエンドツーエンド経路を選択する。
【００４３】
Ｅ２Ｅ−ＰＣＥによって提供されるエンドツーエンド経路は、イントラ−ＰＣＥとＥ２Ｅ−ＰＣＥの両方が同一のＴＥルーティングストラテジーを適用する場合に、そのＴＥルーティングストラテジーに従って最適となる。しかしながら、インター−ドメインとイントラ−ドメインそれぞれのルーティングストラテジーが異なる場合、イントラ−ＰＣＥは、Ｅ２Ｅ−ＰＣＥによって使用されるＴＥルーティングアルゴリズムで使用するために適切な属性パラメータを提供することができる。これは、リクエスト／リプライメカニズムの組込によって実現されることになる。このメカニズムでは、Ｅ２Ｅ−ＰＣＥからイントラ−ＰＣＥへ送信される経路リクエストは、イントラ−ＰＣＥによって使用されるべきルーティングストラテジーと、Ｅ２Ｅ−ＰＣＥによって要求される論理リンクの属性のパラメータ群との少なくとも一方を特定することができる。これは、本ソリューションを劇的に柔軟にして、２つのレイヤーに、独立のルーティングストラテジー群を使用することを可能にしながら、効率的なエンドツーエンドルーティングを維持する。
【００４４】
このソリューションは、図８のフロー図のステップ群を再度参照しながら、例示によって更に説明する。図２は、７つのドメインを備えるＰＣＥ−ベースのネットワークの簡略図を示している。以下の説明の目的のために、経路リクエスト（ＰａｔｈＲｅｑ）を送信するエンティティは、経路計算クライアント（ＰＣＣ）であると仮定する。この経路計算クライアント（ＰＣＣ）は、任意のドメインの任意のエレメントであり得るので、任意のドメインに属さないように表されている。ドメインＤ１からＤ７それぞれは、いくつかの内部エレメント群（簡略化のため不図示）、境界エレメント群及びイントラ−ＰＣＥを備えている。ここで再度、ドメイン群の境界エレメントは、いくつかのインターリンクによって相互に接続されている。
【００４５】
図３は、図２のドメインＤ４とＤ５と、それらのインターリンクＬｘとＬｙを示している。Ｄ４のＢＥとＤ５のＢＥは、それぞれＥ２とＦ１であり、これらは、インターリンクＬｘに関する情報を自身のイントラ−ＰＣＥ群に提供し、これらのイントラ−ＰＣＥ群は、この情報とドメイン情報とをＥ２Ｅ−ＰＣＥへ提供する。すべてのイントラ−ＰＣＥ群は、自身のドメイン情報とインターリンク情報パラメータとを、ＰＣＥ通信プロトコル（ＰＣＥＰ）を介して、必要であれば、その拡張版とともに、Ｅ２Ｅ−ＰＣＥへ送信する。この情報を使用して、Ｅ２Ｅ−ＰＣＥは、図４に示されるように、ドメイン群がノードとして見られ、かつそれらの境界エレメントがノードポート群として見られる、ドメイントポロジーを作成する。
【００４６】
次に、経路リクエストは、ＰＣＣ（これは、発信元ノードであり得る）によって生成され、かつＥ２Ｅ−ＰＣＥへ送信される。経路リクエストは、発信元ドメイン（ＳＤ）と宛先ドメイン（ＤＤ）とを発見するために使用される、発信元アドレス（ＳＡ）と宛先アドレス（ＤＡ）とを特定しなければならない。また、経路リクエストは、経路に対する制約を特定するための更なるフィールド群を含んでいる。以下のリストは、経路リクエスト内で特定され得るいくつかの制約の例である。
【００４７】
・サービスタイプ（例、ユニキャスト、マルチキャストあるいはブロードキャスト）
・ＬＳＰタイプ（例、一方向あるいは双方向、Ｅ−ＬＳＰあるいはＬ−ＬＳＰ）
・帯域幅アップストリーム
・帯域幅ダウンストリーム
・最大ノード負荷（Max_Node_Load）（即ち、Ｅ２Ｅ経路に沿うノードの最大許容負荷のパーセンテージ）
・ＱｏＳ（例、DiffServのクラス０から７）
・保護（例、１＋１、１：１、１：ｎ）
・Ｅ２Ｅ経路に従う、ストレートあるいはルーズリンクディスジョイント性（Straight or loose Link Disjointness along E2E path）
・Ｅ２Ｅ経路に従う、ストレートあるいはルーズノードディスジョイント性（Straight or loose Node Disjointness along E2E path）
・ストレートあるいはルーズドメインディスジョイント性
・ストレートあるいはルーズインター−ドメインリンクディスジョイント性
・オブジェクティブ機能（例、ノード負荷の最小化、Ｅ２Ｅ経路に沿う余剰帯域幅の最大化、トラフィックバランシングの実行等）
・ＤｏｍＥｘｃｌ（即ち、リクエストされる経路からの明示的なドメイン除外）
以下の表２は、計算された経路によって満足されるべき制約のセットを有する経路リクエストの一例を示している。表２の経路リクエストを図２のトポロジーに適用すると、プルーン化ドメイントポロジー（Pruned Domains Topology）の作成を導き、Ｅ２Ｅ−ＰＣＥは、以下のプルーン処理（pruning）を実行する：
・ＤｏｍＥｘｃｌフィールドは、Ｄ６を除外ドメインとして指定する。これにより、Ｄ６とその関連インターリンク群がプルーンされる。
【００４８】
・Ｄ７は、ＳＤでもＤＤでもない、リーフとして接続されているドメインである。そのため、このドメインを通過するＳＤからＤＤへの経路はないことになり、また、その関連インターリンク群がプルーンされる。
【００４９】
・インターリンクＬｘが輻輳していると仮定すると、インターリンクＬｘの帯域幅は十分でなくなっている、あるいはそのＢＥ群の一方あるいは両方は、経路リクエスト内で特定される負荷超過になっているので、Ｌｘもプルーンされる。
【００５０】
図５は、円で囲まれるドメイン群と、削除されたインターリンク群と、及び結果として得られるプルーン化ドメイントポロジーによって表されるように、表２の経路リクエストに従って、図２のネットワークトポロジーのプルーン処理を示している。
【００５１】
プルーン化ドメイントポロジーの作成に続いて、Ｅ２Ｅ−ＰＣＥは、仮想ドメイントポロジー計算リクエスト（ＶＤＴＣＲｅｑ）を、経路リクエストと同一の制約を伴って、発信元ドメイン、宛先ドメイン及び取り得るすべての中継ドメイン（ＴＤ）群、のイントラ−ＰＣＥ群へ送信する。様々なＶＤＴＣＲＲｅｑが、発信元ドメイン、宛先ドメイン及び取り得るすべての中継ドメインに送信される。これは、これらのドメイン群は、上述のように、様々な種類の仮想ドメイントポロジー（ＶＤＴ）群（即ち、異なるエレメントによって作成される）を提供しなければならないからである。
【００５２】
イントラ−ＰＣＥ群は、ローカルのイントラ−ドメイン経路選択基準、メトリック、ポリシー群、ルール及びターゲット機能群に従って、ＶＤＴＣＲｅｑに合致するすべての候補経路を計算する。上述のように、イントラ−ＰＣＥによって使用されるこれらの基準は、Ｅ２Ｅ−ＰＣＥによって適用されるものと異ならせることができる。このような環境では、一旦、経路リクエストを満足する候補経路群が計算されると、エンドツーエンド最適経路（Ｅ２Ｅ−ＢＰ）を計算するために、各経路に関連する属性が、Ｅ２Ｅ−ＰＣＥによって必要とされるこれらのパラメータに従って判定される。次に、イントラ−ＰＣＥは、取り得る各候補経路接続と、それらに関連する属性を表す論理リンク（ＬＬ）群のセットを含む、ドメインの仮想ドメイントポロジー（ＶＤＴ）を形成する。発信元ドメインに対する仮想ドメイントポロジーは、発信元エレメント（ＳＥ）を、ルート内で可能であれば特徴づけることができるドメインのこれらの境界エレメントのそれぞれとに接続する最適経路に対する論理リンクを提供する。中継ドメインに対する仮想ドメイントポロジーは、ルート内で可能であれば特徴づけることができるドメインのこれらの境界エレメント間の最適経路に対する論理リンクを提供する。宛先ドメインに対する仮想ドメイントポロジーは、ルート内で可能であれば特徴づけることができるドメインの境界エレメント群のそれぞれを宛先エレメント（ＤＥ）へ接続する最適経路に対する論理リンクを提供する。
【００５３】
図６ａは、図２のネットワークトポロジーのドメインプルーン処理後の、イントラドメインとインタードメイン内の候補経路群（即ち、同一の対のエレメント群を接続する、すべての取り得るエレメント群間の最適経路）を示している。各ドメインを通過する候補経路群は、図６ａの上部で別に示されている。これらの経路群のそれぞれは、論理リンクに変換され、これらのすべては、図６ｂの下部に示される仮想ドメイントポロジーに組み合わせられる。
【００５４】
仮想ドメイントポロジーが一旦作成されると、各イントラＰＣＥは、仮想ドメイントポロジーを搬送する仮想ドメイントポロジー計算リプライ（ＶＤＴＣＲｅｐ）を、Ｅ２Ｅ−ＰＣＥへ送信する。
【００５５】
リクエストされたドメイン群のすべてからのＶＤＴＣＲｅｐの受信に続いて、Ｅ２Ｅ−ＰＣＥは、仮想ネットワークトポロジー（ＶＮＴ）を作成することができる。ここでは、ノード群は、プルーン化ドメイントポロジーのすべてのドメインの、発信元エレメント、宛先エレメント及び境界エレメント群であり、リンク群は、図６ｃに示される、イントラ−ドメイン論理リンク群とインター−ドメインリンク群（それぞれは、自身の属性を有する）である。
【００５６】
仮想ネットワークトポロジーを使用して、Ｅ２Ｅ−ＰＣＥは、経路リクエストで特定される制約群とイントラ−ドメインネットワークリソースとインター−ドメインネットワークリソースの両方を考慮して、既知のＴＥルーティング方法を使用するエンドツーエンド最適経路（Ｅ２Ｅ−ＢＰ）を計算することができる。Ｅ２Ｅ−ＢＰは、インター−ドメインインターリンク群のセットと、最適経路セグメント（ＢＰＳ）群のセットを備え、それぞれの最適経路セグメントは、仮想ドメイントポロジー内の選択された論理リンクに対応する。
【００５７】
次に、ステップ２０７で、Ｅ２Ｅ−ＰＣＥは、最適経路セグメント通信（ＢＰＳＣｏｍ）を最適経路に関与するドメイン群のイントラ−ＰＣＥ群へ送信する。選択されるシグナリング技術に従って、最適経路セグメント通信は、最適経路セグメント（即ち、そのドメイン群ＶＤＴで提供されるものから選択されるＬＬ）と、インター−ドメインシグナリングプロトコル群によって必要とされるすべての情報を搬送する。ステップ２０８で、ＢＰＳＣｏｍを受信する各イントラ−ＰＣＥは、論理リンクを対応するイントラ−ドメイン経路へマッピングし、そして、自身のセットアップをトリガーする。
【００５８】
一旦、イントラ−ドメイン経路セットアップが完了すると、ステップ２０９で、各イントラ−ＰＣＥは、最適経路セグメントセットアップ確認応答（ＢＰＳＳｅｔ＿ＡＣＫ）をＥ２Ｅ−ＰＣＥへ送信する。経路内のすべてのドメイン群からのＢＰＳＳｅｔ＿ＡＣＫの受信に続いて、ステップ２１０で、Ｅ２Ｅ−ＰＣＥは、経路リプライ（ＰａｔｈＲｅｐ）をＰＣＣへ送信して、ＰＣＣに、エンドツーエンドインター−ドメイン経路計算の結果について通知する。
【００５９】
図９は、複数の別個のドメインを介して確立される通信セッションに対するエンドポイントであり得る、発信元（あるいは宛先）エンティティを示している。このエンティティは、プロセッサ１、送信機２及び受信機３を備えている。送信機と受信機の両方は、エンティティのアクセスドメインにインタフェースされている。このエンティティは、上述の経路リクエストを生成して送信するように構成されている。図１０は、プロセッサ４、送信機５及び受信機６を備えるイントラドメインＰＣＥを示している。プロセッサと受信機の両方は、ＰＣＥのローカルドメインにインタフェースされている。このＰＣＥは、特定のセッションに対する中継ドメインであり得り、または、発信元ドメインあるいは宛先ドメインであり得る。図１１は、プロセッサ７、送信機８及び受信機９を備えるＥ２Ｅ−ＰＣＥを示している。Ｅ２Ｅ−ＰＣＥは、スタンドアローンノードであり得る、あるいは所与のドメインに対するイントラドメインＰＣＥ機能を実現することができる。
【００６０】
当業者には、本発明の範囲から逸脱することなく、上述の実施形態に対して様々な変形を行うことができることが理解されるであろう。
【００６１】
【表１】
2011515974.tif 000003
【００６２】
【表２】
2011515974.tif 000004
【図１】
2011515974.tif 000005
【図２】
2011515974.tif 000006
【図３】
2011515974.tif 000007
【図４】
2011515974.tif 000008
【図５】
2011515974.tif 000009
【図６】
2011515974.tif 000010
【図７】
2011515974.tif 000011
【図８】
2011515974.tif 000012
【図９】
2011515974.tif 000013
【図１０】
2011515974.tif 000014
【図１１】
2011515974.tif 000015
【手続補正書】
【提出日】平成22年3月31日(2010.3.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つ以上のコネクション型技術をサポートする複数のパケット交換自律システムであるＡＳに渡るエンドツーエンドルーティング経路を構築する方法であって、
エンドツーエンド計算エンティティにおいて、
取り得るすべてのＡＳ、前記ＡＳの境界エレメント群、及びインター−ＡＳリンク群を識別するＡＳトポロジーを生成するステップと、
第１のＡＳの発信元エンティティから第２のＡＳの宛先エンティティへの、経路の計算に対するリクエストを受信するステップと、
リクエストされる経路で特徴付けることができないあるいは特徴付ける可能性のない、すべてのＡＳとインター−ＡＳリンク群を、前記ＡＳトポロジーから除去するステップと、
前記ＡＳトポロジーに残っているＡＳに対する、かつ前記発信元エレメントを含む前記第１のＡＳ及び前記宛先エレメントを含む前記第２のＡＳに対する、前記エンドツーエンド経路で特徴となるＡＳの前記境界エレメント群を含む仮想ＡＳトポロジーリクエストを生成するステップと、かつ前記仮想ＡＳトポロジーリクエストを、前記第１のＡＳと、前記第２のＡＳと、及びその第２のＡＳまでの取り得るすべての中継ＡＳとの、イントラ−ＡＳ経路計算エンティティに同時に送信するステップとを備え、
仮想ＡＳトポロジーリクエストの受信に応じて、前記ＡＳトポロジーに残っているＡＳ内の前記イントラ−ＡＳ経路計算エンティティそれぞれにおいて、
前記仮想ＡＳトポロジーリクエストに含まれる、前記境界エレメント群との間の、あるいは前記境界エレメントと前記発信元エンティティあるいは前記宛先エンティティとの間の、候補イントラ−ＡＳ経路群を計算するステップと、
境界エレメントである一端と、境界エレメントあるいは前記発信元エンティティまたは前記宛先エンティティであるもう一端の２つによって定義される論理リンクに、前記候補イントラ−ＡＳ経路群のそれぞれをマッピングするステップと、
前記論理リンクそれぞれに対する属性を判定するステップと、
前記論理リンク群とそれに関連する属性群とを含む仮想ＡＳトポロジーリプライを、前記エンドツーエンド経路計算エンティティへ送信するステップと、
前記仮想ＡＳトポロジーリプライの受信に応じて、前記エンドツーエンド経路計算エンティティにおいて、
前記ＡＳトポロジーに残っているインター−ＡＳリンク群の属性を判定するステップと、
前記論理リンク群とそれらに関連する属性を、前記ＡＳトポロジーに残っているインター−ＡＳリンク群とそれらに関連する属性とを組み合わせることによって、仮想ネットワークトポロジーを生成するステップと、
前記仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定するステップと
を備えることを特徴とする方法。
【請求項２】
前記ＡＳトポロジーを生成するステップは、更に、
ＡＳそれぞれのイントラ−ＡＳ経路計算において、前記ＡＳの境界エレメント群とそれらのインター−ＡＳリンク群との詳細情報を含む、インター−ＡＳデータを生成し、前記インター−ＡＳデータを、エンドツーエンド経路計算エンティティへ送信するステップと、
前記エンドツーエンド計算エンティティにおいて、前記インター−ＡＳデータを使用して、前記ＡＳトポロジーを生成するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のＡＳの発信元エンティティから第２のＡＳの宛先エンティティへの、経路の計算に対するリクエストを受信するステップは、更に、
前記経路の宛先の詳細情報とその経路に対して要求される属性とを含むエンドツーエンド経路リクエストを生成し、前記エンドツーエンド経路計算エンティティへ送信するステップと
を備えることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記候補イントラ−ＡＳ経路群を計算するステップは、更に、
前記エンドツーエンド経路計算エンティティにおいて、前記エンドツーエンド経路によって要求される属性を、ＡＳそれぞれに対する前記仮想ＡＳトポロジーリクエストに含めるステップと、
前記イントラ−ＡＳ経路計算エンティティそれぞれにおいて、前記仮想ＡＳトポロジーリクエストに含まれる前記エンドツーエンド経路によって要求される前記属性群に依存する論理リンクそれぞれに対する属性を判定するステップと
を備える
ことを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記論理リンクそれぞれに対する属性を判定するステップは、更に、
前記ＡＳ内で計算される他の論理リンク群に関して、前記論理リンクの可用性／適合性を表すコストパラメータを判定するステップを備える
ことを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
リンクに対する属性は、前記リンクに対する前記ＡＳ内で利用可能な総ネットワークリソースのパーセンテージとして与えられる
ことを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
イントラ−ＡＳ経路計算エンティティにおいて、自身のインター−ＡＳデータを監視し、かつ前記インター−ＡＳデータの更新を、前記エンドツーエンド経路計算エンティティへ送信するステップを更に備える
ことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
前記インター−ＡＳデータがいくつかの定義されている閾値（群）を越える場合、前記インター−ＡＳデータの更新を、前記エンドツーエンド経路計算エンティティへ送信するステップを更に備える
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記仮想ＡＳトポロジーリクエストを生成するステップは、更に、前記仮想ＡＳトポロジーリクエスト内に、前記イントラ−ＡＳ経路計算エンティティによって判定される属性（群）の識別情報を含めるステップを備える
ことを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記仮想ＡＳトポロジーリクエストを生成するステップは、更に、前記仮想ＡＳトポロジーリクエスト内に、前記候補イントラ−ＡＳ経路群を計算するために、前記イントラ−ＡＳ経路計算エンティティによって使用されるルーティングストラテジーあるいはアルゴリズムの識別情報を含めるステップを備える
ことを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
パケットベースのコネクション型技術群をサポートする複数のＡＳ群に渡るエンドツーエンドルーティング経路の構築を容易にする方法であって、
前記ＡＳの境界エレメントから、前記ＡＳの各境界エレメントに関連する情報と、該ＡＳの境界エレメント群と他のＡＳ群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ＡＳデータを受信するステップと、
前記インター−ＡＳデータを、エンドツーエンド経路計算エンティティに送信する  ステップと、
前記エンドツーエンド経路計算エンティティから、エンドツーエンド経路と、該エンドツーエンド経路によって要求される属性群とを特徴付けるＡＳの境界エレメント群を含む仮想ＡＳトポロジーリクエストを受信するステップと、
候補イントラ−ＡＳ経路群を計算し、その計算された候補イントラ−ＡＳ経路群それぞれの属性を判定するステップと、
境界エレメントである一端と、境界エレメントあるいは前記発信元エンティティまたは前記宛先エンティティであるもう一端の２つによって定義される論理リンクに、前記候補イントラ−ＡＳ経路群のそれぞれをマッピングするステップと、
前記論理リンク群とそれに関連する属性群を含む仮想ＡＳトポロジーリプライを、前記エンドツーエンド経路計算エンティティに送信するステップと
を備えることを特徴とする方法。
【請求項１２】
請求項１１に記載の方法を実行するように構成されている装置。
【請求項１３】
パケットベースのコネクション型技術群をサポートする複数のＡＳ群に渡るエンドツーエンドルーティング経路を構築する方法であって、
イントラ−ＡＳ経路計算エンティティ群から、前記ＡＳの各境界エレメントに関連する情報と、該ＡＳの境界エレメント群と他のＡＳ群の境界エレメント群との間のリンク群に関連する情報とを含むインター−ＡＳデータを受信するステップと、
取り得るすべてのＡＳと、前記ＡＳの前記境界エレメントと、及び前記インター−ＡＳリンク群を識別するＡＳトポロジーを生成するステップと、
発信元エンティティから、経路の発信元と宛先の詳細情報と、その経路に対して要求される属性とを含むエンドツーエンド経路リクエストを受信するステップと、
前記経路を特徴付けることができないあるいは特徴付ける可能性のない、すべてのＡＳとインター−ＡＳリンク群を、前記ＡＳトポロジーから、除去するステップと、
前記経路と、該経路によって要求される属性群とを特徴付けるＡＳの境界エレメント群それぞれを含む仮想ＡＳトポロジーリクエストをＡＳそれぞれに対して生成するステップと、
前記仮想ＡＳトポロジーリクエストを、前記発信元ＡＳ、前記宛先ＡＳ及び取り得るすべての中継ＡＳ群のイントラ−ＡＳ経路計算エンティティへ送信するステップと、
前記ＡＳのそれぞれから、候補イントラ−ＡＳ経路それぞれを表す論理リンク群と、及びそれに関連する属性群とを含む仮想ＡＳトポロジーリプライを受信するステップと、
残っているインター−ＡＳリンク群それぞれの属性を判定するステップと、
前記論理リンク群とそれに関連する属性群とを、前記残っているインター−ＡＳリンク群とそれに関連する属性群とを組み合わせることによって、仮想ネットワークトポロジーを生成するステップと、
前記仮想ネットワークトポロジーを解析することによって、最適エンドツーエンドルートを判定するステップと
を備えることを特徴とする方法。
【請求項１４】
請求項１３に記載の方法を実行するように構成されている装置。
【国際調査報告】
2011515974.tif 000016
2011515974.tif 000017
2011515974.tif 000018