(57)【要約】  複数の領域に広がる制約付きラベルスイッチパス（ＬＳＰ）を算出することが説明される。一実施形態において、複数の領域のうちの第１の領域中のルータは、１つ以上の制約のセットを満たし、宛先に到達するために必要なパス中に存在する第１の領域の少なくとも１つのボーダールータまでのパスセグメントを算出する。ルータは、複数の領域のうちの第２の領域中のパス算出エレメント（ＰＣＥ）に、パス算出要求メッセージを送信する。当該パス算出要求メッセージは、制約付きＬＳＰの宛先に向かう１つ以上のパスセグメントを算出するためにＰＣＥによって用いられる、算出されたパスセグメントの各々についての１つ以上の属性のセットを含む。ルータは、制約のセットを満たし、ルータから下流の１つ以上のＰＣＥによって算出された、１つ以上の算出されたパスセグメントのセットを特定するパス算出応答メッセージを、ＰＣＥから受信する。ルータは、パス算出応答メッセージにおいて特定される算出されたパスセグメントのセットのうちの少なくとも１つと、ルータによって算出されたパスセグメントとを連結して、制約付きＬＳＰの少なくとも一部を形成する。【選択図】図１
2013541290.tif 000002
【特許請求の範囲】
【請求項１】
複数の領域に広がって宛先に到達する制約付きラベルスイッチパス（ＬＳＰ）の算出に関与するための、ルータにおける方法であって、当該ルータは前記複数の領域のうちの第１の領域内に含まれ、当該方法は、
１つ以上の制約のセットを満たす、前記第１の領域の少なくとも１つのボーダールータまでのパスセグメントを算出するステップと、
前記少なくとも１つのボーダールータは、前記宛先に到達するために必要なパス中に存在することと、
前記複数の領域のうちの第２の領域中のパス算出エレメントに、パス算出要求メッセージを送信するステップと、
前記パス算出要求メッセージは、算出される各パスセグメントについての１つ以上の属性のセットを含み、当該１つ以上の属性は、前記制約付きＬＳＰの前記宛先に向かう１つ以上のパスセグメントを算出するために前記パス算出エレメントによって用いられることと、
前記制約のセットを満たす、前記ルータから下流の１つ以上のパス算出エレメントによって算出された、１つ以上の算出されたパスセグメントのセットを特定するパス算出応答メッセージを、前記パス算出エレメントから受信するステップと、
前記パス算出応答メッセージにおいて特定される前記算出されたパスセグメントのセットのうちの少なくとも１つと、前記ルータによって算出された前記パスセグメントとを連結して、前記制約付きＬＳＰの少なくとも一部を形成するステップと、
を含む、方法。
【請求項２】
前記制約のセットを満たす、前記第１の領域の少なくとも１つのボーダールータまでの前記パスセグメントを算出する前記ステップは、異なるルータによって算出される１つ以上のパスセグメントのセットについての１つ以上のパスセグメント属性のセットを含むパス算出要求メッセージを当該異なるルータから受信することに応じて行われる、請求項１に記載の方法。
【請求項３】
前記第２の領域中の前記パス算出エレメントに送信される前記パス算出要求メッセージは、前記異なるルータによって算出された前記パスセグメントのセットについての前記パスセグメント属性のセットを含む、請求項２に記載の方法。
【請求項４】
前記パスセグメント属性のセットは、コスト及びホップカウントを含む、請求項１に記載の方法。
【請求項５】
前記パスセグメントパラメータのセットは、帯域幅及び管理グループをさらに含む、請求項４に記載の方法。
【請求項６】
送信される前記パス算出要求メッセージに応答するパス算出応答メッセージを受信するためのタイマを開始するステップ、
をさらに含む、請求項１に記載の方法。
【請求項７】
前記第２の領域は、前記第１の領域とは異なる自律システム中にある、請求項１に記載の方法。
【請求項８】
複数の領域に広がって宛先に到達するための制約付きラベルスイッチパス（ＬＳＰ）の算出に関与するための、ルータにおける方法であって、当該ルータは、前記複数の領域のうちの第１の領域に存在し、前記宛先は、前記第１の領域中にあり、当該方法は、
前記複数の領域のうちの第２の領域に存在するルータから、パス算出要求メッセージを受信するステップと、
前記パス算出要求メッセージは、前記第２の領域中の前記ルータによって算出された、１つ以上のボーダールータのセットまでの１つ以上のパスセグメントのセットの各々についての１つ以上の属性のセットを含むことと、
前記第２の領域に存在する前記ルータによって算出された前記パスセグメントのセットの各々についての前記属性のセットを用いて前記宛先までの１つ以上のパスセグメントのセットを算出するステップと、
前記第２の領域に存在する前記ルータに、パス算出応答メッセージを送信するステップと、
前記パス算出応答メッセージは、前記宛先までの算出された前記パスセグメントのセット及び前記宛先までの算出された各パスセグメントについての１つ以上の属性のセットを特定することと、
を含む、方法。
【請求項９】
前記パス算出要求メッセージに含まれる前記属性のセットは、前記第２の領域中の前記ルータによって算出される前記パスセグメントのセットの各々についてのコスト及びホップカウントを含み、
前記パス算出応答メッセージに含まれる前記属性のセットは、前記第１の領域中の前記ルータによって算出される前記宛先までの前記パスセグメントのセットの各々についてのコスト及びホップカウントを含む、
請求項８に記載の方法。
【請求項１０】
前記第２の領域に存在する前記ルータは、前記第１の領域に存在する前記ルータと同じ自律システム中にある、請求項８に記載の方法。
【請求項１１】
前記第２の領域に存在する前記ルータは、前記第１の領域に存在する前記ルータとは異なる自律システム中にあり、
前記１つ以上のボーダールータのセットは、自律システムボーダールータ（ＡＳＢＲ）であり、
前記第１の領域に存在する前記ルータは、ＡＳＢＲである、
請求項８に記載の方法。
【請求項１２】
前記宛先までの前記１つ以上のパスセグメントのセットを算出する前記ステップは、各ボーダールータと前記第１の領域に存在する前記ルータとの間のリンクの１つ以上の特性のセットも算入する、請求項１１に記載の方法。
【請求項１３】
複数の領域に広がって宛先に到達する制約付きラベルスイッチパス（ＬＳＰ）の算出に関与するための装置であって、当該装置は、ルータを備え、
当該ルータは、
１つ以上の制約のセットを満たす、前記宛先に到達するために必要なパス中に存在する前記第１の領域の少なくとも１つのボーダールータまでのパスセグメントを算出し、
前記複数の領域のうちの第２の領域中のパス算出エレメントによって前記制約付きＬＳＰの前記宛先に向かう１つ以上のパスセグメントを算出するために用いられる算出された各パスセグメントについての１つ以上の属性のセットを含むパス算出要求メッセージを、当該パス算出エレメントに送信し、
前記パス算出エレメントから、前記制約のセットを満たし、前記ルータから下流の１つ以上のパス算出エレメントによって算出された、１つ以上の算出されたパスセグメントのセットを特定するパス算出応答メッセージを受信し、
前記パス算出応答メッセージにおいて特定される前記算出されたパスセグメントのセットのうちの少なくとも１つと、前記ルータによって算出された前記パスセグメントとを連結して、前記制約付きＬＳＰの少なくとも一部を形成する、
ように構成される、
装置。
【請求項１４】
前記ルータは、異なるルータによって算出される１つ以上のパスセグメントのセットについての１つ以上のパスセグメント属性のセットを含むパス算出要求メッセージを当該異なるルータから受信することに応じて、前記制約のセットを満たす、前記第１の領域の少なくとも１つのボーダールータまでの前記パスセグメントを算出する、請求項１３に記載の装置。
【請求項１５】
前記第２の領域中の前記パス算出エレメントに送信されるべき前記パス算出要求メッセージは、前記異なるルータによって算出された前記パスセグメントのセットについての前記パスセグメント属性のセットを含む、請求項１４に記載の装置。
【請求項１６】
前記パスセグメント属性のセットは、コスト及びホップカウントを含む、請求項１３に記載の装置。
【請求項１７】
前記パスセグメントパラメータのセットは、帯域幅及び管理グループをさらに含む、請求項１６に記載の装置。
【請求項１８】
前記ルータは、送信されるべき前記パス算出要求メッセージに応答するパス算出応答メッセージの受信のためのタイマを開始するようにさらに構成される、請求項１３に記載の装置。
【請求項１９】
前記第２の領域は、前記第１の領域とは異なる自律システム中にある、請求項１３に記載の装置。
【請求項２０】
複数の領域に広がって宛先に到達する制約付きラベルスイッチパス（ＬＳＰ）の算出に関与するための装置であって、当該装置は、ルータを備え、
当該ルータは、
前記複数の領域のうちの第２の領域に存在するルータから、当該第２の領域中の当該ルータによって算出された、１つ以上のボーダールータのセットまでの１つ以上のパスセグメントのセットの各々についての１つ以上の属性のセットを含むパス算出要求メッセージを受信し、
前記第２の領域に存在する前記ルータによって算出された前記パスセグメントのセットの各々についての前記属性のセットを用いて、前記宛先までの１つ以上のパスセグメントのセットを算出し、
前記第２の領域に存在する前記ルータに、前記宛先までの算出された前記パスセグメントのセット及び前記宛先までの算出された各パスセグメントについての１つ以上の属性のセットを特定するパス算出応答メッセージを送信する、
ように構成される、装置。
【請求項２１】
前記パス算出要求メッセージに含まれる前記属性のセットは、前記第２の領域中の前記ルータによって算出される前記パスセグメントのセットの各々についてのコスト及びホップカウントを含み、
前記パス算出応答メッセージに含まれる前記属性のセットは、前記第１の領域中の前記ルータによって算出される前記宛先までの前記パスセグメントのセットの各々についてのコスト及びホップカウントを含む、
請求項２０に記載の装置。
【請求項２２】
前記第２の領域に存在する前記ルータは、前記第１の領域に存在する前記ルータと同じ自律システム中にある、請求項２０に記載の装置。
【請求項２３】
前記第２の領域に存在する前記ルータは、前記第１の領域に存在する前記ルータとは異なる自律システム中にあり、
前記１つ以上のボーダールータのセットは、自律システムボーダールータ（ＡＳＢＲ）であり、
前記第１の領域に存在する前記ルータは、ＡＳＢＲである、
請求項２０に記載の装置。
【請求項２４】
前記ルータは、各ボーダールータと前記第１の領域に存在する前記ルータとの間のリンクの１つ以上の特性を算入して、前記宛先までの前記１つ以上のパスセグメントのセットを算出する、請求項２３に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本願は、２０１０年９月２１日に出願された、米国仮出願第６１／３８４，７７４号の利益を主張し、当該出願は参照により本明細書に包含される。
【０００２】
本発明の実施形態は、ネットワーキングの分野に関し、特に、複数の領域及び／又は複数の自律システムにわたって広がる制約付き（constraint-based）ラベルスイッチパス（ＬＰＳ：label  switched  path）を算出することに関する。
【背景技術】
【０００３】
複数の領域又は複数の自律システムにわたって広がるラベルスイッチパス（ＬＰＳ）を算出する能力への需要は、学術的議論からキャリアネットワークの機能要求へと発展してきた。複数の領域又は複数の自律システムにわたって広がる制約付きＬＳＰを算出するために提案されてきた解決法は少なかった。
【０００４】
提案された１つの解決法において、グローバルＴＥ（traffic  engineering）データベースが用いられる。グローバルＴＥデータベースは、複数の領域又は複数のＡＳにわたって広がるＬＳＰを算出するための単純な解決法である一方、法外に高くつく。なぜなら、グローバルＴＥデータベースはあまりに大きいことがあり、それ故に、複数の領域又は複数のＡＳを有することの目的の意味を失わせ、また、情報の秘匿及び機密性の要件に違反し、これはインターネットサービスプロバイダ（ＩＳＰ）によって受け入れがたいためである。
【０００５】
提案された別の解決法は、クランクバック法を用いる。クランクバック法は、全数検索に基づくメカニズムであり、ＬＳＰが存在する場合は当該ＬＳＰを見つけることとなるため、グローバルＴＥデータベースよりも現実的である。１つの欠点は、クランクバック法がスケーリングしないことである。なぜなら、クランクバック法は、要件を満たすＬＳＰを見つけるために２回以上のトライアウトをしばしば必要とし、それ故に当該トライアウトを浪費するためである。また、クランクバック法は、ＲＳＶＰ（Resource  Reservation  Protocol）シグナリングベースであり、これはその本質上、スケーリング性に乏しいためである。別の欠点は、クランクバック法において用いられる余分なシグナリングメッセージが既存のネットワークに負荷を追加することである。別の欠点は、パスが見つかる場合に、当該パスが最適である保証がないことである。別の欠点は、ボーダールータを特定するために多くの手動による設定を必要とする点において、クランクバック法が労働集約的であることである。最後に、別の欠点は、クランクバック法がプロトコル及びオペレーションの双方において実質的なＲＳＶＰの変更を必要とすることである。
【０００６】
提案された別の解決法は、２００９年４月のＲＦＣ（Request  For  Comments）５４４１、“A  Backward-Recursive  PCE-Based  Computation  (BRPC)  Procedure  to  Compute  Shortest  Constrained  Inter-Domain  Traffic  Engineering  Label  Switched  Paths”において説明される。ＲＦＣ５４４１において提案された解決法は、特定のドメイン及び領域において宛先が既知であると仮定する。ただし、この仮定は常に当てはまるとは限らない。また、宛先は、ＲＦＣ５４４１の方法が対処することができないマルチホームであることがある（様々なエリア及びドメインを介して到達可能であることを意味する）。さらに、ＲＦＣ５４４１において説明される方法は、ＶＳＰＴ（Virtual  Shortest  Path  Tree）を理解するＰＣＥＰ（Path  Computation  Element  Protocol）の拡張を要求し、これは当該方法をさらに複雑化する。また、ＶＳＰＴアプローチは、一度に１つの宛先しかアドレス指定しない。
【発明の概要】
【課題を解決するための手段】
【０００７】
複数の領域に広がって宛先に到達する制約付きラベルスイッチパス（ＬＳＰ）の算出に関与するための、ルータにおける方法であって、当該ルータは当該複数の領域のうちの第１の領域内に含まれる、方法が説明される。一実施形態において、ルータは、１つ以上の制約のセットを満たす、第１の領域の少なくとも１つのボーダールータまでのパスセグメントを算出する。当該少なくとも１つのボーダールータは、宛先に到達するために必要なパス中に存在する。ルータは、複数の領域のうちの第２の領域中のパス算出エレメントに、パス算出要求メッセージを送信する。当該パス算出要求メッセージは、算出される各パスセグメントについての１つ以上の属性のセットを含み、当該１つ以上の属性は、制約付きＬＳＰの宛先に向かう１つ以上のパスセグメントを算出するためにパス算出エレメントによって用いられる。ルータは、制約のセットを満たし、当該ルータから下流の１つ以上のパス算出エレメントによって算出された、１つ以上の算出されたパスセグメントのセットを特定するパス算出応答メッセージを、パス算出エレメントから受信する。ルータは、パス算出応答メッセージにおいて特定される算出されたパスセグメントのセットのうちの少なくとも１つと、ルータによって算出された前記パスセグメントとを連結（stitch）して、制約付きＬＳＰの少なくとも一部を形成する。
【０００８】
別の実施形態において、複数の領域のうちの第１の領域に存在するルータは、複数の領域に広がる制約付きＬＳＰの算出に関与する。宛先も、第１の領域にある。当該ルータは、複数の領域のうちの第２の領域に存在するルータから、パス算出要求メッセージを受信する。当該パス算出要求メッセージは、第２の領域中のルータによって算出された１つ以上のボーダールータのセットまでの１つ以上のパスセグメントのセットの各々についての１つ以上の属性のセットを含む。ルータは、第２の領域に存在するルータによって算出されたパスセグメントのセットの各々についての属性のセットを用いて、宛先までの１つ以上のパスセグメントのセットを算出する。ルータは、第２の領域に存在するルータに、パス算出応答メッセージを送信する。パス算出応答メッセージは、宛先までの算出された前記パスセグメントのセット及び宛先までの算出された各パスセグメントについての１つ以上の属性のセットを特定する。
【図面の簡単な説明】
【０００９】
本発明は、本発明の実施形態を例示するために用いられる下記の説明及び添付の図面を参照することによって、最もよく理解され得る。図面において：
【００１０】
【図１】一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出することを図示するデータフロー図である。
【図２】一実施形態に係る、パスセグメント算出のシード情報をエンコードするためのＰＣＥＰ（PCE  Communication  Protocol）の例示的な拡張を図示する。
【図３】一実施形態に係る、テールエンドルータＴに複数の領域を介して到達可能であるネットワークを図示する。
【図４】一実施形態に係る、ＳＰＦ（shortest  path  first）ヒープの最短パスツリー（ＳＰＴ：shortest  path  tree）等価特性を図示する。
【図５】一実施形態に係る、ＳＰＦヒープのシードデポジットタイミング特性を図示する。
【図６】一実施形態に係る、ＳＰＦヒープのシードセット低減特性を図示する。
【図７】一実施形態に係る、リレータイマロジックの例示的な疑似コードを図示する。
【図８】一実施形態に係る、制約付きＬＳＰが複数の自律システムにおける複数の領域にわたって広がる例示的なネットワークを図示する。
【図９】一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出するための例示的な動作を図示するフロー図である。
【図１０】一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出するために宛先領域中のＰＣＥによって実行される例示的な動作を図示するフロー図である。
【発明を実施するための形態】
【００１１】
下記の説明においては、多くの具体的な詳細が述べられる。ただし、本発明の実施形態はそれらの具体的な詳細無しに実施をされ得ることが理解される。他の場合において、周知の回路、構造及び技法は、この説明の理解を曖昧にしないように、詳細には示されていない。当業者は、本明細書に含まれる説明により、必要以上の実験無しに適当な機能性を実装することができるであろう。
【００１２】
本明細書における「一実施形態」、「ある実施形態」、「例示的な実施形態」等への言及は、説明される実施形態が特定の機能、構造、又は特性を含み得るが、全ての実施形態が必ずしも当該特定の機能、構造、又は特性を含まなくてもよいことを示す。また、そのような表現は、必ずしも同じ実施形態に言及しない。さらに、特定の機能、構造、又は特性が、ある実施形態に関連して説明される場合、明示的に説明されていてもいなくても、そのような機能、構造、又は特性を他の実施形態に関連して達成することは当業者の知識の範囲内であることが提示される。
【００１３】
下記の説明及び特許請求の範囲においては、「結合される（coupled）」及び「接続される（connected）」という用語がこれらの派生語と共に用いられ得る。これらの用語は互いに同義語として意図されないことが理解されるべきである。「結合される」は、互いに直接物理的に又は電気的に接触してもしなくてもよい２つ以上のエレメントが互いに協働し又は相互作用することを示すために用いられる。
【００１４】
複数の領域又は複数の自律システムにわたって広がる制約付きのラベルスイッチパス（ＬＳＰ）を算出するための方法及び装置が説明される。一実施形態において、複数の領域又は複数の自律システムにわたって広がるべきＬＳＰについて、当該複数の領域又は複数の自律システムにおけるパス算出エレメント（ＰＣＥ：path  computation  elements）は、（パスが存在する場合には）協働してパスを判定する。上流のＰＣＥは、当該ＰＣＥ自身のドメインの外部にあるＬＳＰの終端についてのパス算出を実行することは不可能である一方、その算出の履歴をその下流のＰＣＥに提供し、当該下流のＰＣＥは算出ジョブを引き継ぐ（assumes）。また、下流のＰＣＥは、パスが完全に算出されるまで、その履歴を別の下流のＰＣＥに送信し得る。
【００１５】
図１は、一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出することを図示するデータフロー図である。図１に図示される例示的なトポロジーは、破線によって分割される西領域１４０と東領域１４５とを含む。２つの領域のみが示されるが、本発明は２つの領域のみに限定されず、ＬＳＰが広がる２つより多くの領域が存在してもよい。ルータＨ１１０及びルータＢ１１５は、西領域１４０内に位置する。ルータＨ１１０は、ＬＳＰのヘッドエンドである。ルータＴ１４５は、東領域１４５内に位置する。ルータＴ１４５は、ＬＳＰのテールエンドである。ルータＡ１３０及びルータＣ１２０は、ボーダールータである。従って、ＬＳＰは、ヘッドエンドルータＨ１２０からテールエンドルータＴ１２５まで算出される。
【００１６】
西領域１４０は、ＰＣＥ１５０を含み、東領域は、ＰＣＥ１５５を含む。ＰＣＥ１５０は、ルータＨ１１０内、ルータＢ１１５内、ルータＡ１３０内、ルータＣ１２０内、又は西領域１４０内の別のネットワークデバイス中に含まれることができる。ＰＣＥ１５５は、ルータＡ１３０内、ルータＣ１２０内、ルータＴ１２５内、又は東領域１４５内の別のネットワークデバイス中に含まれることができる。ＰＣＥ１５０は、西領域１４０（ヘッドエンド領域）のＴＥデータベースにおける情報のみにアクセスできる。このため、及びＩＧＰ（Interior  Gateway  Protocol）（例えば、ＯＳＰＦ（Open  Shortest  Path  First）、ＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System））の性質に起因して、東領域１４５中のテールエンドルータＴ１２５は、西領域１４０中のＰＣＥ１５０からは可視ではない。
【００１７】
ルータＡ１３０及びルータＣ１２０は、（本明細書においてボーダーノード（ＢＮ））と呼ばれることもある）領域ボーダールータである。領域ボーダールータは、次の領域又はその先の領域中の宛先までの必要なパス内に存在する（ただし、領域ボーダーは宛先までのパス内に存在し得るが、当該パスは、より最適なルートが存在する場合、最終的に選択されるパスではないことがあることが理解されるべきである）。図１に図示されるように、ルータＡ１３０及びルータＣ１２０は、ルータＨ１１０からルータＴ１２５に到達するためのパスに存在する。具体的には、ルータＨ１１０からルータＡ１３０、ルータＴ１２５までのパスと、ルータＨ１１０からルータＢ１１５、ルータＣ１２０、ルータＴ１２５までの別のパスが存在する。
【００１８】
西領域１４０及び領域１４５にわたる制約付きＬＳＰを算出するために、ＰＣＥ１５０は、ヘッドエンドルータＨ１１０からボーダールータＡ１３０までのパス及びヘッドエンドルータＨ１１０からボーダールータＣ１２０までのパスを算出することによって、算出の一部を実行する（これらのパスは制約付きＬＳＰの制約を満たすと仮定する）。算出されるこれらのパスは、テールエンドルータ１２５までの完全なパスの一セグメントであるので、本明細書においてはパスセグメントと呼ばれる。ＰＣＥ１５０は、当該算出の結果をＰＣＥ１５５に提供する。ＰＣＥ１５５は、当該情報を用いて、テールエンドルータＴ１２５までのパスの算出を完了する。従って、パスの算出は、一方は西領域１４０において、他方は東領域１４５においてリレーされるＣＳＰＦ（Constrained  Shortest  Path  First）ジョブとして進む。本明細書において説明されるように、ＰＣＥは、パス算出要求（ＰＣＲｅｑ）メッセージを生成し及び送信し、ＰＣＲｅｑメッセージを受信し及び処理し、パス算出応答（ＰＣＲｅｐ）メッセージを生成し及び送信し、並びにＰＣＲｅｐメッセージを受信し及び処理するケイパビリティを有する。
【００１９】
ルータＡ１３０及びルータＣ１２０は東領域１４５へのボーダールータであるので、これらのルータは、ＣＳＰＦ算出についての最初のシードセットの選択肢として選択される。ＰＣＥ１５０は、領域ボーダールータの各々をそれに提供する情報を含む（ＩＧＰプロトコル及びそれらのＴＥ拡張によって提供されることができる）。ＣＳＰＦ、又はより一般的にはＳＰＦ（Shortest  Path  First）は、シードベースのアルゴリズムであり、西領域１４０についてのＳＰＴ（Shortest  Path  Tree）は、これらのシードに基づいて構築される。動作１．１において、ＰＣＥ１５０は、ＬＳＰについての制約のセットを満たす、ヘッドエンドルータＨ１１０からルータＡ１３０までのパスセグメントを算出し、及び、ＬＳＰについての制約のセットを満たす、ヘッドエンドルータＨ１１０からルータＣ１２０までのパスセグメントを算出する。
【００２０】
動作１．２において、ＰＣＥ１５０は、ＰＣＥ１５５がテールエンドルータＴ１２５までのパスの算出を継続することを可能にする、ルータＡ１３０までのパスセグメント及びルータＣ１２０までのパスセグメントの当該ＰＣＥ１５０による算出に関する情報と共に、パス算出要求（ＰＣＲｅｑ）メッセージをＰＣＥ１５５に送信する。この情報は、パス要求情報（例えば、制約のセット）、並びに、コスト、帯域幅、管理グループ、ホップカウント等といった、ルータＡ１３０及びルータＣ１２０までの算出されたセグメントのパス属性を含む。この情報を用いて、ＰＣＥ１５５は、制約のセットを満たす、テールエンドルータＴ１２５へ向けてのパスを算出する。
【００２１】
図１は、東領域１４５中に単一のＰＣＥ１５５を図示するが、ある状況においては、東領域１４５中に複数のＰＣＥが存在してもよい。そのような状況においては、算出リソースの浪費及びコンテンションを回避するために、ＰＣＥのうちの１つのみにＰＣＲｅｑメッセージが送信される必要がある。一実施形態において、ＰＣＥ１５０は、選択メカニズムを実行して、適格なＰＣＥのうちの１つを選択する。選択されるＰＣＥは、任意のルータとすることができ、又は専用のＰＣＥとすることができる（中継ルータである必要はない）。一実施形態において、選択を実行する（例えば、最上位のルータＩＤ又は最下位のルータＩＤを有するルータを選択する）ために、任意のタイブレーカーアルゴリズムが用いられることができる。
【００２２】
図２は、一実施形態に係る、パスセグメント算出のシード情報をエンコードするための２００９年３月のＲＦＣ５４４０“Path  Computation  Element  (PCE)  Communication  Protocol  (PCEP)”において説明されるＰＣＥＰ（PCE  Communication  Protocol）の例示的な拡張を図示する。図２に図示されるように、リレーコンテンツ拡張フォーマット２１０は、ＴＬＶ（type-length-value）フォーマットである。タイプフィールド２１５は、このメッセージがリレーされるＣＳＰＦ算出のためのものであることを示す１バイトの値である。長さフィールド２２０は、拡張の実際の長さを提供する１バイトの値である。ノードＩＤフィールド２２５は、ボーダールータのノード識別子を提供する４バイトの値である。リレーコンテンツ拡張２１０には、セグメント情報をエンコードする１つ以上のサブＴＶＬも含まれる。各サブＴＬＶは、当該サブＴＬＶがセグメント情報を含むことを示す値をエンコードする１バイトのフィールドであるサブタイプフィールド２３０、当該サブＴＬＶの長さの値（例えば、長さ６）をエンコードする１バイトのフィールドである長さフィールド２３５、セグメントについての識別子を提供する１バイトのフィールドであるセグメント識別子フィールド２４０（ボーダールータは当該ボーダールータまでの複数のセグメントパスを有することができるため、このセグメント識別子は、各セグメントが区別されることを可能にし、追加的な制約に順応する場合に用いられる）、セグメントのコストを提供するコストフィールド２４５、及びセグメント上のホップの数を提供するホップフィールド２５０を含む。一実施形態において、管理グループ及び帯域幅情報は、標準的なパス要求情報フィールドから知得されることができるため、リレーコンテンツ拡張２１０において搬送されない。
【００２３】
図１を再び参照すると、ＰＣＲｅｑメッセージ１６０を受信した後のあるときに、動作１．３において、東領域１４５のＰＣＥ１５５は、テールエンドルータＴまでのパスを算出する場合に、ＰＣＲｅｑメッセージ１６０中のルータＡ１３０及びルータＣ１２０までのパス情報を用いる。例えば、ＰＣＥ１５５は、パス情報を当該ＰＣＥ１５５のＳＰＦヒープにデポジットし、テールエンドルータＴ１２５までのパス算出を実行する。
【００２４】
パス算出を実行する場合、ＰＣＥ１５５は、ＳＰＦヒープに関連付けられる１つ以上の特性を利用し得る。ＳＰＦヒープの１つの特性は、最初のシードでのヒープが未到達の宛先についての任意のＳＰＦステージにおける複数の中間シードでのヒープと等価的であること（最短パスツリー（ＳＰＴ：shortest  path  tree）等価と呼ばれる）である。通常のＳＰＦサイクルの期間中に、ヒープは変化し、パスツリーは拡大するであろう。任意の特定のＳＰＦサイクルにおいて、パスツリーは、ある宛先への到達可能性を記録し、これは、ＩＧＰルーティングプロトコル（例えば、ＯＳＰＦ、ＩＳ−ＩＳ）などの一般的なＳＰＦアプリケーションにとって重要である。ＩＧＰにおいては、宛先がヒープから早く出てくるか又は遅くでてくるかに関わらず、全ての宛先が含まれなければならず、いずれも無視されることはできない。しかしながら、ＣＳＰＦにおいては、ターゲットとなる宛先のみが重要であるため、関連性のないレコードは算出期間中に破棄されることができる。従って、重要ではない早期のパスツリーのレコードは、破棄されることができる。それ故に、選択される宛先については、複数のシードを伴う拡大されたヒープは、最初の段階におけるヒープと等しい。図４は、この概念を図示する。通常のＳＰＦ算出によれば、ヘッドエンドノードルータＨ４１０は、ＳＰＦヒープの最初のシードとして用いられる。最後のＳＰＴは、ルータＡ４１５、ルータＢ４２０への到達可能性、及びテールエンドルータＴ４２５への到達可能性を提供する。算出がルータＡ４１５及びルータＢ４２０をデポジットシードとして用いる場合、算出はテールエンドルータＴ４２５への同じ到達可能性を伴うＳＰＴという結果になるであろう。２つのＳＰＴの間の相違点は、ヘッドエンドルータＨ４１０からルータＡ４１５及びルータＢ４２０への到達可能性である。
【００２５】
ＳＰＦヒープの別の特性は、シードがコスト及びネクストホップといった正確な属性を有する（carry）のであれば、まだ到達されていない宛先にシードのデポジット時間が影響を受けない（insensitive）ことである（シードデポジットタイミング特性と呼ばれる）。この特性は、まだ到達されていない宛先までのそのＳＰＴの寄与をシードデポジット時間が変化させないことを意味する。図５は、この概念を図示する。図５における例示的なネットワークは、ヘッドエンドルータＨ５１０、ルータＡ５１５、ルータＢ５２０、ルータＣ５２５、及びテールエンドルータＴ５３０を含む。ヘッドエンドルータＨ５１０は、ルータＡ５１５及びルータＢ５２０に直接結合される。ルータＢ５２０は、ルータＣ５２５にも直接結合され、当該ルータＣ５２５自体は、テールエンドルータＴ５３０に直接結合される。ルータＡ５１５も、テールエンドルータＴ５３０に直接結合される。この特性が理由で、テールエンドルータＴ５３０までのパスを算出する際、ルータＡ５１５及びルータＢ５２０のシードセットを用いる場合、又はルータＡ５１５及びルータＣ５２５のシードセットを用いる場合に同一の結果が提供される。
【００２６】
ＳＰＦヒープの別の特性は、ＳＰＴ等価特性における複数のシードが、それ無しでは宛先が有効で（viable）はないノードのセットを構成するノードにさらに低減されることができることである（シードセット低減特性と呼ばれる）。これは、パスに寄与しないであろうシードが除去されることを可能にする。図６は、この概念を図示する。図６における例示的なネットワークは、ヘッドエンドルータ６１０、ルータＡ６１５、ルータＢ６２０、ルータＣ６２５、ルータＤ６３５、ルータＥ６４０、及びテールエンドルータＴ６３０を含む。ヘッドエンドルータＨ６１０は、ルータＡ６１５及びルータＢ６２０に直接結合される。ルータＢ６２０は、ルータＣ６２５にも直接結合される。ルータＣ６２５は、ルータＤ６３５及びテールエンドルータＴ６３０にも直接結合される。ルータＤ６３５は、ルータＥ６４０にも直接結合され、ルータＡ６１５は、テールエンドルータＴ６３０にも直接結合される。テールエンドルータＴ６３０への到達可能性について、ヘッドエンドルータＨ６１０の最初のシードは、ＳＰＴ等価特性ごとにルータＡ６１５及びルータＢ６２０と置換されることができる。これらの２つのシードは、シードデポジットタイミング特性ごとにルータＡ６１５、ルータＣ６２５、及びルータＤ６３５のシードセットとさらに置換されることができる。ＤはテールエンドルータＴ６３０までのパスに寄与しないこととなるので、シードセットは、ルータＡ６１５及びルータＣ６２５のシードセットにさらに低減されることができる。
【００２７】
テールエンドルータＴ１２５までの算出を終了したことが分かった後のあるときに、動作１．４において、ＰＣＥ１５５は、パス算出応答（ＰＣＲｅｐ）メッセージ１６５をＰＣＥ１５０に送信する。ＰＣＲｅｐメッセージ１６５は、テールエンドルータＴ１２５までの算出されたパスについてのそのパスセグメント情報を含む。ＰＣＥ１５０は、動作１．５において、ＰＣＲｅｐメッセージ１６５中の情報を用いて、パスセグメントをルータＡ１３０及びルータＣ１２０のうちの１つにマッピングし、当該セグメントを西領域１４０におけるセグメントに連結して、テールエンドルータＴ１２５までの完全なパスを形成する。例えば、ＰＣＲｅｐメッセージ１６５がルータＡ１３０からテールエンドルータＴ１２５までのパスセグメント情報を含むと仮定すると、ＰＣＥ１５０は、当該セグメントをルータＡ１３０にマッピングし、完全なパスがヘッドエンドルータＨ１１０からルータＡ１３０、テールエンドルータＴ１２５までとなるように、複数のセグメントを互いに連結する。
【００２８】
図１に図示される例は２つの領域のみについてのものであるが、東領域１４５よりもさらに東の領域中に宛先が存在し得ることが理解されるべきである。そのような場合、ＰＣＥ１５５は、ＰＣＲｅｑをさらに下流のＰＣＥにリレーすることとなり、当該ＰＣＥは、ターゲットの宛先を見つけるか、又はジョブをリレーすることを継続することとなる。連結は、同様の手法で、ただし反対の順序で進む。
【００２９】
図１は、宛先が単一の領域中にあることを図示した。しかしながら、幾つかの状況において、宛先は、マルチホーミングされ、複数の領域を介して有効であってもよい。図３は、テールエンドルータＴ３５５に複数の領域（領域Ｂ３１５及び領域Ｃ３２０）を介して到達可能であるネットワークを図示する。領域Ａ３１０は、ヘッドエンドルータＨ３３０及びＰＣＥ３３２を含む。領域Ｂ３１５は、ＰＣＥ３３４を含む。領域Ｃは、ＰＣＥ３３６を含む。領域Ｄは、テールエンドルータＴ３５５及びＰＣＥ３３８を含む。領域Ａ３１０は、領域Ｂ３１５にボーダールータＡＢ３３５を介して接続され、領域ＣにボーダールータＡＣ３４０を介して接続される。領域Ｂ３１５は、領域Ｄ３２５にボーダールータＢＤ３４５を介して接続される。領域Ｃ３２０は、領域Ｄ３２５にボーダールータＣＤ３５０を介して接続される。
【００３０】
ルータＨ３３０からのパスの算出は、図１を参照しつつ説明されたのと同様の手法で実行されるが、パスの可用性及び最適性を最大化するために、一実施形態では、パス算出要求メッセージが各隣接領域及び各領域の選択されたＰＣＥに送信される。従って、ＰＣＥ３３２は、ＰＣＲｅｑメッセージ３６０をＰＣＥ３３４に送信し、ＰＣＲｅｑメッセージ３６２をＰＣＥ３３６に送信する。これらの２つのＰＣＲｅｑメッセージは異なる。ＰＣＥ３３４に送信されるＰＣＲｅｑメッセージ３６０は、ヘッドエンドルータＨ３３０とルータＡＢ３３５との間のルータのシードをエンコードし、ＰＣＥ３３６に送信されるＰＣＲｅｑメッセージ３６２は、ヘッドエンドルータＨ３３０とルータＡＣ３４０との間のルータのシードをエンコードする。ＰＣＥ３３４及びＰＣＥ３３６は、それぞれＰＣＲｅｑメッセージ３６０及び３６２中の情報に基づいて、テールエンドルータＴ３５５までのそれらの算出を実行する。ＰＣＥ３３４は、ＰＣＲｅｑメッセージ３６４をＰＣＥ３３８に送信し、ＰＣＥ３３６は、ＰＣＲｅｑメッセージ３６６をＰＣＥ３３８に送信する。ＰＣＥ３３８は、受信される複数のＰＣＲｅｑメッセージを別々に取扱い、テールエンドルータＴ３５５までのパスを別々に算出する。ＰＣＥ３３８は、ＰＣＲｅｐメッセージ３７０をＰＣＥ３３４に送信し、ＰＣＲｅｐメッセージ３７２をＰＣＥ３３６に送信する。ＰＣＥ３３４は、ＰＣＲｅｐメッセージ３７４をＰＣＥ３３２に送信し、ＰＣＥ３３６は、ＰＣＲｅｐメッセージ３７６をＰＣＥ３３２に送信する。複数のＰＣＲｅｑメッセージを送信することはヘッドエンドの領域中のＰＣＥに限定されないことが理解されるべきである。換言すれば、中間領域におけるＰＣＥは、複数の領域への複数のボーダールータを有する場合、複数のＰＣＲｅｑメッセージを送信することができる。
【００３１】
一実施形態において、ＰＣＥ３３２は、テールエンドルータＴ３５５までのパスをエンコードする複数の応答を受信し得るので、ＰＣＥ３３２は、宛先までの複数のパスについての競合状態の可能性に適応すべく、考えられる全てのＰＣＲｅｑメッセージを収集するために妥当な待機時間を許容するためのタイマを実装する。ＰＣＲｅｑメッセージを受信するＰＣＥは、当該ＰＣＥがパスを見つけるか否かを示すＰＣＲｅｐを要求側に送信するべきである。しかしながら、ＰＣＲｅｐメッセージは、生成するために時間を要することがあり、また、送信期間中に失われることがある。このため、幾つかの実施形態において、要求側ＰＣＥは、リレータイマを開始し、それにより、ＰＣＲｅｐメッセージが到達しない場合に当該ＰＣＥが無制限に待機しないようにする。
【００３２】
図７は、一実施形態に係る、タイマロジックのサンプル疑似コードを図示する。図７に図示されるように、疑似コードは、３つのセクション、即ち、ＰＣＲｅｑメッセージを送信すること、ＰＣＲｅｐメッセージを受信すること、及びリレータイマが満了することに分離される。ＰＣＲｅｑメッセージを送信する場合、要求側ＰＣＥは、各ボーダー領域の選択される各ＰＣＥについて、当該選択されるＰＣＥにＰＣＲｅｑメッセージを送信し、パス要求情報（例えば、制約のセット）及びボーダールータのシードを含む。要求側ＰＣＥは、選択されるＰＣＥをＰＣＲｅｑペンディングリストに追加し、当該ＰＣＥが存在しない場合にリレータイマを作成する。
【００３３】
ＰＣＲｅｐメッセージを受信すると、要求側ＰＣＥは、当該ＰＣＲｅｐのソースアドレスをルックアップし、当該ＰＣＲｅｐメッセージにおいてエンコードされるパスを判定する。ＰＣＥは、当該ＰＣＥが受信した、宛先までの過去のパスよりも当該パスが良好であるかを判定する（及び、当該良好なパスを最良のパスとして設定する）。ＰＣＥは、ＰＣＲｅｐメッセージを送信したＰＣＥを、ＰＣＲｅｑペンディングリストから除去する。それによってＰＣＲｅｑペンディングリストが空になる場合、リレータイマはキャンセルされ、要求側ＰＣＥがヘッドエンドである（又は、ヘッドエンド領域中にある）場合、処理は終了する。さもなければ、要求側ＰＣＥは、最良のパスを伴うＰＣＲｅｐを上流のＰＣＥに送信する。
【００３４】
リレータイマが満了すると、要求側ＰＣＥは、ＰＣＲｅｑペンディングリストをクリーンアップする。例えば、要求側ＰＣＥは、当該要求側ＰＣＥがＰＣＲｅｐメッセージを依然として待機しているエントリを削除する。ＰＣＲｅｑペンディングリストが空である場合、リレータイマはキャンセルされ、要求側ＰＣＥがヘッドエンドである（又は、ヘッドエンド領域中にある）場合、処理は終了する。さもなければ、要求側ＰＣＥは、最良のパスを伴うＰＣＲｅｐを上流のＰＣＥに送信する。
【００３５】
図１は、同じ自律システム中の複数の領域に広がるＬＳＰを説明したが、ＬＳＰは、複数の自律システムにわたって広がることもできる。複数の自律システムにわたって広がるＬＳＰの算出は、同じシステム中の複数の領域にわたって広がるＬＳＰの算出と同様であるが、少数の相違点がある。相違点の１つは、ＰＣＥがＰＣＲｅｐを異なる自律システム中にある要求側ＰＣＥに送信する場合、当該ＰＣＥは、明示的なホップごとのＥＲＯ（explicit  route  objects：明示的ルートオブジェクト）を送信しない点である。代わりに、ＰＣＥは、コストメトリックなどのパスレベルキャラクタを伴う疎な（loose）ＥＲＯを送信する。これは、エンドツーエンドのＬＳＰが依然として確立されることができる一方で、異なる自律システムから情報が隠されることを確保する。
【００３６】
別の相違点は、ＰＣＥの選択概念が複数の自律システムにわたって適用されないことである。換言すれば、ＰＣＥが異なる自律システム中にある場合、要求側ＰＣＥはＰＣＥ選択手続きを実行しない。また、自律システムの数をＴＥデータベースに保持する必要がない。一実施形態において、ＰＣＲｅｑメッセージ及び対応するシードは、有効な各自律システムのピアノードに送信される。
【００３７】
別の相違点は、ボーダールータが双方の領域上にある複数領域のトポロジーと異なり、２つの自律システムボーダールータがこれらを互いに接続するためのトランジットリンクを必要とすることである。自律システムボーダールータ（ＡＳＢＲ：autonomous  system  border  router）がＰＣＲｅｑメッセージを当該ルータのピアＡＳＢＲに送信しようとする際には、トランジットリンクがＡＳＢＲのために算入される必要がある。メトリック、ホップカウント、帯域幅といったトランジットリンクの特性もシード値に算入されなければならない。例えば、図８は、制約付きＬＳＰが複数の自律システムにおける複数の領域にわたって広がるネットワークを図示する。図８に図示されるように、自律システム８１０の西領域８１５は、ヘッドエンドルータ８５０、ルータＡ８１５、ルータＣ８３０、及びＰＣＥ８５０を含み、自律システム８２０の東領域８２５は、ルータＤ８４０、テールエンドルータＴ８４５、及びＰＣＥ８５５を含む。ルータＣ８３０及びルータＤ８４０は、自律システムボーダールータであり、トランジットリンク８３５によって接続される。ＰＣＥ８５０は、ＰＣＲｅｑメッセージ８６０をＰＣＥ８５５に送信し、当該ＰＣＥ８５５は、トランジットリンク８３５の特性を算入する。ＰＣＥ８５５は、テールエンドルータＴ８４５までのパスを算出し及びＰＣＥ８５０にＰＣＲｅｐメッセージ８６５により応答する際に、トランジットリンク８３５を算入する。
【００３８】
図９は、一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出するための例示的な動作を図示するフロー図である。動作９１０において、ＰＣＥは、制約のセットを満たす、１つ以上の領域の１つ以上のボーダールータまでのパスセグメントを算出する。ＰＣＥは、ヘッドエンド領域中にあってもよく、算出を開始し得る。ＰＣＥは、中間領域中にあっても、テールエンド領域中にあってもよい。中間領域又はテールエンド領域中にある場合、ＰＣＥは、異なる領域中の異なるＰＣＥからパス算出要求メッセージを受信することに応答して、パスセグメントを算出し得る。当該異なる領域は、異なる自律システム中にあってもよい。パス算出要求メッセージは、要求側ＰＣＥによって算出された１つ以上のパスセグメントについて１つ以上のパスセグメント属性を含み、ＰＣＥによって当該ＰＣＥのボーダールータまでのパスセグメントを算出する際に用いられる。フローは、動作９１０から動作９１５に移る。
【００３９】
随意的である動作９１５において、ＰＣＥは、領域の各々において２つ以上のＰＣＥがあるかを判定する。２つ以上のＰＣＥが無い場合、フローは動作９２５に移る。２つ以上のＰＣＥがある場合、フローは動作９２０に移り、２つ以上のＰＣＥを有する領域の各々について、当該ＰＣＥのうちの１つを要求側ＰＣＥが選択する（例えば、最上位のルータＩＤ又は最下位のルータＩＤを有するルータ内のＰＣＥを選択する）。フローは、動作９２０から動作９２５へ移る。複数の領域が異なる自律システム中にある場合、一実施形態において、９１５及び９２０の動作は実行されない。
【００４０】
動作９２５において、要求側ＰＣＥは、領域の各々におけるＰＣＥに、パス算出要求メッセージを送信する。パス算出要求メッセージは、当該領域についての算出された各パスセグメントについての属性を含む。パス算出要求メッセージは、パス要求情報（例えば、ＬＳＰについての制約のセット）も含む。一実施形態において、パス算出要求メッセージは、算出されたパスセグメントについての属性をエンコードするための、図２１０に図示されるＰＣＲｅｑリレーコンテキスト拡張を含む。フローは、動作９３５に移る。
【００４１】
動作９３５において、要求側ＰＣＥは、送信されたパス算出要求メッセージに応答するパス算出応答メッセージを受信する。パス算出応答メッセージは、下流のＰＣＥによって算出されるパスセグメント情報を含む。フローは、動作９４０に移る。
【００４２】
一実施形態において、同じ自律システム中にある下流のＰＣＥからパス算出応答メッセージが受信された場合、パス算出応答メッセージは、明示的ＥＲＯを含む。ただし、異なる自律システム中にある下流のＰＣＥからパス算出応答メッセージが受信された場合、パス算出応答メッセージは、疎なＥＲＯを含む。パス算出応答が疎なＥＲＯを含む場合、要求側ＰＣＥは、当該疎なＥＲＯによって表されるパスセグメントを回復させる。一実施形態において、ボーダールータは、パスセグメントのレコード（予め算出されるＥＲＯ）を記憶する。予約要求（例えば、ＲＳＶＰ要求）がボーダールータに到来する場合、当該要求は、ローカルに記憶されるＥＲＯを既に含んでいる。このアプローチは、迅速に機能するが、ＲＳＶＰ実装の変更を必要とする。別の実施形態において、ボーダールータは明示的パスセグメントを記憶せず、むしろ、ステートレスである。要求される場合、ボーダールータは、当該ボーダールータ自身のＰＣＥにＥＲＯを判定するように問い合わせるであろう。これは、トポロジーが変化していないと仮定すると、予め算出されるＥＲＯのアプローチと同じＥＲＯという結果になるであろう。
【００４３】
動作９４０において、要求側ＰＣＥは、パスセグメントをボーダールータのうちの１つにマッピングし、パス算出応答メッセージにおいて識別されるセグメントを当該ボーダールータまでのパスセグメントに連結する。要求側ＰＣＥがヘッドエンド領域にある場合、連結されたパスは、ヘッドエンドからテールエンドまでの完全なパスとなるであろう。要求側ＰＣＥが中間領域にある場合、連結されたパスは、完全なパスの一セグメントとなり、ＰＣＥは、その要求側ＰＣＥに送信するためにパスセグメント情報を用いてパス算出応答メッセージを生成するであろう。
【００４４】
図１０は、一実施形態に係る、複数の領域にわたって広がる制約付きＬＳＰを算出するために宛先領域においてＰＣＥによって実行される例示的な動作を図示するフロー図である。動作１０１０において、ＰＣＥは、上流のルータ上の異なるＰＣＥによって算出された１つ以上のパスセグメントについての属性を含むパス算出要求メッセージを受信する。一実施形態において、パス算出要求メッセージは、算出されたパスセグメントについての属性をエンコードするための、図２１０に図示されるＰＣＲｅｑリレーコンテンツ拡張を含む。フローは、動作１０１５に移り、ＰＣＥは、パス算出要求メッセージ中の情報を用いて、宛先までのパスセグメントを算出する。フローは、動作１０２０に移り、ＰＣＥは、算出されたパスセグメントについてのパスセグメント情報を含むＰＣＥ応答メッセージを送信する。
【００４５】
一実施形態において、既存のＬＳＰの知識を必要とするバックアップＬＳＰ、バイパスＬＳＰ、パスの再最適化、又は任意の他のパス算出は、ＰＣＲｅｑメッセージに含まれる当該ＬＳＰの情報及びそのパスセグメント情報を有する。ＬＳＰが複数の自律システムにまたがって広がる場合、上流のルータは、パスセグメントの詳細を、下流のルータから隠す。
【００４６】
一実施形態において、共有リスクリンクグループ（ＳＲＬＧ：shared  risk  link  group）ハンドリングは、単一の自律システムの単一領域のパス算出のそれと何ら変わりない。従って、（例えば、ＧＭＰＬＳ（Generalized  Multiprotocol  Label  Switching）を介して）ＳＲＬＧ情報が利用可能であれば、リレーされる各ＰＣＥは、正確なＰＣＥセグメントを算出することができ、エンドツーエンドのパスは、ＳＲＬＧ要件を満たすべきである。
【００４７】
本明細書において説明されるように、動作は、ある動作を実行するように構成され又は所定の機能性を有する特定用途向け集積回路（ＡＳＩＣ：application  specific  integrated  circuits）といったハードウェアの特定の設定、又は非一時的なコンピュータ読取可能な媒体において具現化されるメモリに記憶されるソフトウェア命令を指し得る。従って、図面に示される技法は、１つ以上の電子デバイス（例えば、ルータ）上に記憶され及び実行されるコード及びデータを用いて実装されることができる。そのような電子デバイスは、非一時的なコンピュータ読取可能な記憶媒体（例えば、磁気ディスク、光ディスク、ＲＡＭ、ＲＯＭ、フラッシュメモリデバイス、相変化メモリ）、及び一時的なコンピュータ読取可能な通信媒体（例えば、搬送波、赤外線信号、デジタル信号といった電気的、光学的、音響的、又は他の形態の伝搬信号）といったコンピュータ読取可能な媒体を用いて、コード及びデータを、記憶し並びに（内部的に、及び／又は、ネットワーク上で他の電子デバイスと）通信する。また、そのような電子デバイスは、典型的に、１つ以上のストレージデバイス（非一時的な機械読み取り可能なストレージ媒体）、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、及び／又はディスプレイ）、並びにネットワーク接続といった１つ以上の他のコンポーネントに結合される１つ以上のプロセッサを含む。プロセッサのセットと他のコンポーネントとの結合は、典型的に、１つ以上のバス及び（バスコントローラとも称される）ブリッジを介する。従って、所与の電子デバイスのストレージデバイスは、典型的に、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明の一実施形態の１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの異なる組み合わせを用いて実装され得る。
【００４８】
図面におけるフロー図は、本発明のある実施形態によって実行される動作の特定の順序を示すが、そのような順序は例示的である（例えば、別の実施形態は、当該動作を異なる順序で実行し、ある動作を組み合わせ、ある動作を重複させる等してもよい）ことが理解されるべきである。
【００４９】
本発明は幾つかの実施形態の観点から説明されたが、本発明が上記実施形態に限定されず、添付の特許請求の範囲の思想及び範囲内おいて変更され及び変形されて実施をされることができることを当業者は認識するであろう。従って、説明は、限定ではなく例示としてみなされるべきである。
【図１】
2013541290.tif 000003
【図２】
2013541290.tif 000004
【図３】
2013541290.tif 000005
【図４】
2013541290.tif 000006
【図５】
2013541290.tif 000007
【図６】
2013541290.tif 000008
【図７】
2013541290.tif 000009
【図８】
2013541290.tif 000010
【図９】
2013541290.tif 000011
【図１０】
2013541290.tif 000012
【国際調査報告】
2013541290.tif 000013
2013541290.tif 000014