分離的なパス計算アルゴリズム
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成するようにマルチプロトコルラベルスイッチングを実装するネットワークエレメントである。当該ネットワークエレメントは、ＬＳＰの生成についての要求を受信し、前記ＬＳＰの前記生成についての前記要求が前記バックアップＬＳＰを対象とすることを判定し、トラフィックエンジニアリングデータベース内で前記プライマリＬＳＰの各リンクの位置を特定し、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、実際のリンクコストよりも大幅に大きいリンクコストを有するように、前記プライマリＬＳＰの各リンクを修正し、ＣＳＰＦアルゴリズムを実行して、前記プライマリＬＳＰの各リンクの修正されたコストに起因して前記プライマリＬＳＰからの最大の分離度を有する前記バックアップＬＳＰを取得し、そして前記バックアップＬＳＰを返却する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ネットワーク上のマルチプロトコルラベルスイッチングを管理するためのシステムに関する。具体的には、本発明の実施形態は、プライマリラベルスイッチパスについての最適なバックアップパスを決定するための方法及びシステムに関する。
【背景技術】
【０００２】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）は、ネットワーク上のトラフィックを管理するために利用される技術である。ＭＰＬＳは、ネットワークをまたがるトラフィックをルーティングするために、トラフィックのストリームに割当てられる。ネットワークの各ノードは、ネットワーク上で受信されるインカミングのトラフィックを検査し、そのラベルに基づいて当該トラフィックを転送することにより、ＭＰＬＳをサポートする。
【０００３】
トラフィックエンジニアリングのケイパビリティを有するＭＰＬＳネットワークは、カスタマイズされるトラフィックサービスのために、トラフィックエンジニアリングのリソース割当てを最適化することができる。トラフィックエンジニアリングを伴うＭＰＬＳネットワークにおいて、プライマリラベルスイッチパス（ＬＳＰ）は、カスタマイズされるトラフィックサービスごとにセットアップされる。プライマリＬＳＰは、制約付きの最短経路優先（ＣＳＰＦ：Constrained Shortest Path First）アルゴリズムを用いて計算される。プライマリＬＳＰは、通常、パスの起点となるノードであるヘッドエンドノードにおいて計算される。プライマリＬＳＰの確立は、自動化され得る。ＬＳＰの自動的な生成は、ヘッドエンドノード又は別個のパス計算エレメント（ＰＣＥ）により行われ得る。
【０００４】
カスタマイズされるトラフィックサービスごとのバックアップＬＳＰは、プライマリＬＳＰの障害の場合に利用され、手動で構成されなければならない。バックアップＬＳＰ内のリンクの各々は、プライマリＬＳＰが障害の状態にある時に頼ることのできる分離した（disjointed）パスを生成するという目標をもって、バックアップＬＳＰを構築するように手動で選択される。バックアップＬＳＰの手動構成のための技術は、リンクのカラーリング（coloring）及びノードの排除（exclusion）を含む。
【０００５】
しかしながら、これら技術は、管理者によるバックアップＬＳＰの手動での構成に強く依存している。結果として、バックアップＬＳＰの構成は、ヒューマンエラーを引き起こし易い。バックアップＬＳＰを確立しようとする管理者は、バックアップＬＳＰがカスタマイズされるトラフィックサービスの全ての制約又は要件を充足しているかを検証しなければならない。彼らは、考え得る最良の保護をバックアップＬＳＰが提供し、又はバックアップＬＳＰがプライマリＬＳＰからの最大の分離度（disjointness）を有することを、手動で判定しなければならない。
【発明の概要】
【課題を解決するための手段】
【０００６】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するネットワークエレメント上で実行される、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成して、プライマリＬＳＰに信頼できるバックアップを提供する方法であって、前記ネットワークエレメントにより、シグナリングプロトコルを通じて、ＬＳＰの生成についての要求を受信するステップと、前記ＬＳＰの前記生成についての前記要求が前記バックアップＬＳＰを対象とすることを判定するステップと、前記要求が前記バックアップＬＳＰを対象とするという判定に応じて、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するステップと、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、実際のリンクコスト以外のリンクコストを有するように、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを修正するステップと、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するステップと、前記バックアップＬＳＰは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、前記シグナリングプロトコルを通じて、前記バックアップＬＳＰを返却することと、を含む方法である。
【０００７】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのシステムであって、ＬＳＰの生成についての要求を受信するように適合され、及び、パス計算エレメントを呼び出して前記ＬＳＰを取得し、前記ＬＳＰを要求側へ返却するように適合されるラベルスイッチルータと、前記ラベルスイッチルータに連結される前記パス計算エレメント（ＰＣＥ）と、前記ＰＣＥは、前記ＬＳＰの前記生成についての前記要求がバックアップＬＳＰを対象とするかを判定するように適合されることと、前記ＰＣＥは、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するように適合されることと、前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、修正されたコストを有するように修正するように適合されることと、前記修正されたコストは、前記バックアップＬＳＰ内での前記プライマリＬＳＰのリンクの使用を抑制することと、前記ＰＣＥは、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するように適合されることと、前記バックアップＬＳＰは、前記バックアップＬＳＰの計算において使用される前記プライマリＬＳＰの各リンクの前記修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、前記ＰＣＥは、前記第１のラベルスイッチルータへ前記バックアップＬＳＰを返却するように適合されることと、を含むシステムである。
【０００８】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのネットワークエレメントあって、プライマリＬＳＰについてのリンク状態情報を含むネットワークトポロジーについてのリンク状態情報を記憶するように適合されるトラフィックエンジニアリングデータベースと、前記トラフィックエンジニアリングデータベースに連結され、前記バックアップＬＳＰについての要求を処理するように適合されるバックアップパス計算モジュールと、前記バックアップパス計算モジュールは、トラフィックエンジニアリングデータベース内で前記プライマリＬＳＰの各リンクの位置を特定し、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、実際のコスト以外のコストを有するように修正するするように適合されることと、前記バックアップパス計算モジュールに連結され、前記トラフィックエンジニアリングデータベースからの前記リンク状態情報を用いて、宛て先ノードへの最適なパスを判定するための最適パス判定モジュールと、を含むネットワークエレメントである。
【図面の簡単な説明】
【０００９】
本発明は、添付図面の図において限定の形ではなく例示の形で示されており、同等の参照は同様のエレメントを指し示す。なお、本開示における“一”実施形態又は“１つの”実施形態という異なる参照は、必ずしも同じ実施形態へのものではなく、そうした参照は、少なくとも１つを意味する。さらに、特定の特性、構造又は特徴が一実施形態との関連で説明される場合に、明示的に説明されているかによらず、そうした特性、構造又は特徴が他の実施形態との関連でも効果を有することは、当業者の知識の範囲内である。
【００１０】
【図１】マルチプロトコルラベルスイッチングを実装するネットワークの１つの実施形態の図である。
【図２】ヘッドエンドノード又はパス計算エレメントの１つの実施形態の図である。
【図３】バックアップラベルスイッチングパスを生成するための処理の１つの実施形態のフローチャートである。
【発明を実施するための形態】
【００１１】
以下の説明において、多くの具体的な詳細が例示される。しかしながら、本発明の実施形態がこれら具体的な詳細がなくとも実践され得ることが理解される。他の例において、よく知られた回路、構造及び技術は、本説明の理解を曖昧にしないために、詳細には示されていない。しかしながら、当業者であれば、そうした具体的な詳細がなくとも本発明を実践し得ることを理解するであろう。ここに含められる説明によって、当業者は、必要以上の実験を行わなくても、適切な機能性を実装することができるであろう。
【００１２】
図１及び図２の例示的な実施形態を参照しながら、フロー図の作用について説明する。しかしながら、理解されるべき点として、フロー図の作用は、図１及び図２を参照しながら議論されるもの以外の本発明の実施形態によって奏されてもよく、図１及び図２を参照しながら議論される実施形態は、図３のフロー図を参照しながら議論されるものとは異なる作用を奏することもできる。
【００１３】
図に示される技術を、１つ以上の電子デバイス（例えば、エンドステーション、ネットワークエレメントなど）上で記憶され実行されるコード及びデータを用いて実行することができる。そうした電子デバイスは、例えばマシン読取可能な又はコンピュータ読取可能な記憶媒体（例えば、磁気ディスク、光学ディスク、ランダムアクセスメモリ、リードオンリメモリ、フラッシュメモリデバイス及び相変化メモリ）などの、マシン読取可能な又はコンピュータ読取可能な媒体を用いて、コード及びデータを記憶し及び（内部的に及び／又はネットワーク上で他の電子デバイスと）通信する。加えて、そうした電子デバイスは、典型的には、１つ以上のプロセッサのセットを含み、１つ以上のプロセッサのセットは、例えば１つ以上の記憶デバイス、ユーザ入出力デバイス（例えば、キーボード、タッチスクリーン及び／又はディスプレイ）及びネットワーク接続などの、１つ以上の他のコンポーネントと連結される。プロセッサのセットと他のコンポーネントとの連結（coupling）は、典型的には、１つ以上のバス及びブリッジ（バスコントローラともいう）を介する。記憶デバイス及びネットワークトラフィックを搬送する信号は、それぞれ、１つ以上のマシン読取可能な又はコンピュータ読取可能な記憶媒体、及び、マシン読取可能な又はコンピュータ読取可能な通信媒体を表す。よって、所与の電子デバイスの記憶デバイスは、典型的には、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明の実施形態の１つ以上の部分は、ソフトウェア、ファームウェア及び／又はハードウェアの様々な組合せを用いて実装されてよい。
【００１４】
ここで使用されるような、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジなど）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、エンドステーションなど）と通信可能に相互接続する、ハードウェア及びソフトウェアを含む１つのネットワーク機器である。いくつかのネットワークエレメントは、複数のネットワーク機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２集約、セッションボーダ制御、マルチキャスティング及び／又は加入者管理）についてのサポートを提供し、及び／又は複数のアプリケーションサービス（例えば、データ、音声及び映像）についてのサポートを提供する“マルチサービスネットワークエレメント”である。加入者エンドステーション（例えば、サーバ、ワークステーション、ラップトップ、パームトップ、モバイルフォン、スマートフォン、マルチメディアフォン、ＶｏＩＰ（Voice over Internet Protocol）、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲームシステム、セットトップボックス（ＳＩＢ）など）は、インターネット上で提供されるコンテンツ／サービス、及び／又は、インターネット上に重畳されるＶＰＮ（Virtual Private Network）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的には、サービス又はコンテンツプロバイダに属する１つ以上のエンドステーション（例えば、サーバエンドステーション）、又はピアツーピアサービスに参加しているエンドステーションにより提供され、パブリックウェブページ（フリーコンテンツ、ストアフロント、検索サービスなど）、プライベートウェブページ（例えば、ユーザネーム／パスワードでアクセスされる、電子メールサービスを提供するウェブページなど）、ＶＰＮ上の企業ネットワーク、ＩＰＴＶなどを含み得る。典型的には、加入者エンドステーションは、エッジネットワークエレメントに（例えば、（有線で又は無線で）アクセスネットワークに連結される顧客設備機器を通じて）連結され、エッジネットワークエレメントは、他のエンドステーション（例えば、サーバエンドステーション）に（例えば、他のエッジネットワークエレメントへの１つ以上のコアネットワークエレメントを通じて）連結される。
【００１５】
本発明の実施形態は、ヒューマンエラー、非最適なラベルスイッチパス（ＬＳＰ）、最大限分離していないプライマリ及びバックアップＬＳＰ、バックアップＬＳＰの決定論的な生成、並びに、バックアップＬＳＰを手動でセットアップするための管理者の時間及びリソースの莫大な使用、を含む従来技術の欠点を回避するためのシステム、ネットワーク及び方法を提供する。
【００１６】
本発明の実施形態は、バックアップＬＳＰを生成する際に、プライマリＬＳＰのリンクの使用を禁止はしないものの抑制するように、各リンクに高い又は最大のコストを与えることで、トラフィックエンジニアリングデータベース内のプライマリＬＳＰのパスを“ポイズニング”して、これら欠点を克服する。プライマリＬＳＰのリンクが一度このように修正されると、制約付きの最短経路優先（ＣＳＰＦ）アルゴリズムなどのパス発見アルゴリズムが、自動的に、プライマリＬＳＰから最も分離した最適なバックアップＬＳＰを決定論的に判定するために使用され得る。
【００１７】
図１は、ＭＰＬＳを実装するネットワークの１つの実施形態の図である。例としてのネットワーク１００は、ノードＡ〜Ｆを含む。他の実施形態において、ネットワーク内にいかなる数のノードが存在してもよい。ノードの各々は、コンピュータ又はネットワークエレメントを含むいかなる種類のコンピューティングデバイスであってもよい。コンピューティングデバイスは、デスクトップコンピュータ、ラップトップコンピュータ、ネットワーキングエレメント、ルータ、サーバ又は同様のコンピューティングデバイスを含み得る。ノードの各々は、どういったネットワーク媒体上で接続されてもよく、ネットワークのサイズ又は構成も問わない。ネットワークは、ローカリエリアネットワーク（ＬＡＮ）、インターネット又は同様の通信システムなどのワイドエリアネットワーク（ＷＡＮ）であってよい。ネットワーク１００内のノードの各々は、ラベルスイッチパス（ＬＳＰ）に従ってネットワーク１００にわたるトラフィックを管理するための、ＭＰＬＳ又は同様の技術をサポートする。ネットワーク媒体は、いかなる有線又は無線ネットワーキング技術であってもよい。ネットワーク１００は、ヘッドエンドノード１０１及び宛て先ノード１１１を含み得る。ＬＳＰは、ヘッドエンドノード１０１を起点とし、宛て先ノード１１１を終点とする。別個のＬＳＰについて、ネットワーク１００内のいかなる数のノードが、ヘッドエンドノード又は宛て先ノードとして記憶されてもよい。
【００１８】
ヘッドエンドノード１０１は、トラフィックサービス要求に応じて、プライマリＬＳＰ１０７を確立する。ヘッドエンドノード１０１は、ネットワーク１００上のトラフィックサービスごとにプライマリＬＳＰ１０７を確立することもできる。ヘッドエンドノード１０１は、プライマリＬＳＰ１０７を計算するパス計算エレメント（ＰＣＥ）１０３を含み得る。他の実施形態において、ＰＣＥ１０３は、別個のデバイス又はそうでなければヘッドエンドノード１０１とは別々である。本実施形態では、ヘッドエンドノード１０１は、パス計算クライアント（ＰＣＣ）を介してＰＣＥと通信する。
【００１９】
ヘッドエンドノード１０１は、バックアップＬＳＰ１０９を確立するための責任をも有する。バックアップＬＳＰ１０９は、理想的には、プライマリ１０７から最大限の分離度を有する一方で、ヘッドエンドノード１０１から宛て先ノードＣ１１１へ最良の、最も効率的な又は最適なルートを依然として有するＬＳＰである。ＰＣＥ１０３がバックアップＬＳＰ１０９を計算することもできる。バックアップＬＳＰ１０９は、プライマリＬＳＰ１０７が生成される都度、又は、バックアップＬＳＰを計算すべきことを示すトラフィックサービス要求に応じて、計算されてよい。
【００２０】
ネットワーク１００の例において、ノードＡ〜Ｆ間のリンクの各々は、例えば毎秒１ギガビットなどの同等の帯域幅を有する。但し、ノードＣ及びＦの間のリンクを除く。このリンクは、毎秒０．５ギガビットの帯域幅を有する。ヘッドエンドノードにより処理される、ヘッドエンドノード１０１から宛て先ノードＣへのトラフィックサービス要求が、毎秒１ギガビットの帯域幅の要件を有するものとする。プライマリＬＳＰ１０７は、最少のホップを有する最も近道のルートとして、ノードＡ、Ｂ及びＣを通過する。同じ制約付きの最短経路優先（ＣＳＰＦ）アルゴリズム又は同等のアルゴリズムを単純に用いてバックアップＬＳＰ１０９を生成すると、プライマリＬＳＰ１０７と同じルートが生成されるであろう。プライマリＬＳＰ１０７の各リンクが除外されると、バックアップＬＳＰ１０９は、トラフィックサービス要求の制約を満たさないノードＦ及びＣの間のリンクを含まざるを得ないであろう。以下にさらに詳細に説明するＰＣＥは、プライマリＬＳＰ１０７のリンクの各々を最大のコストで重み付けすることによりバックアップＬＳＰ１０９を生成し、それにより、それらリンクの使用を抑制し、但しそれらを禁止しない。この改変された重み又はコストでＣＳＰＦ又は同等のパス発見アルゴリズムが実行され、それにより、修正されたトポロジーについてのコストに基づく最良のパスが生み出される。結果として生じるバックアップＬＳＰ１０９は、プライマリＬＳＰ１０７から最大限の分離度を提供しつつ、一方で要求されたトラフィックサービスの制約を維持する。バックアップＬＳＰ１０９は、依然として、プライマリＬＳＰ１０７との間で共有されるノードＢ及びＣの間のリンクを含み、これは必要であればプライマリＬＳＰ１０７のリンクを使用するという柔軟さの実例である。
【００２１】
図２は、ヘッドエンドノード又はＰＣＥの１つの実施形態の図である。バックアップＬＳＰを計算する機能性は、ヘッドエンドノード、又はヘッドエンドノード内のＰＣＣを介してヘッドエンドノードと通信する別個のＰＣＥのいずれにおいて実装されてもよい。１つの実施形態において、ヘッドエンドノードがその機能性を実装し、当該機能性は、ヘッドエンドノード内に組み込まれる個別のＰＣＥ内にやはりセグメント化されてよい。当業者であれば、バックアップＬＳＰの計算に直接的に関係するヘッドエンドノードのコンポーネント又はＰＣＥのみが示されていることを理解するであろう。ヘッドエンドノード又はＰＣＥは、プライマリＬＳＰを計算するために必要な標準的な機能性及びコンポーネント、並びに他の同様の機能の全てを有することができる。１つの実施形態において、ヘッドエンドノード又はＰＣＥは、バックアップＬＳＰモジュール２０１、トラフィックエンジニアリングデータベース２０３、及び制約付きの最短経路優先（ＣＳＰＦ）モジュール２０５を含む。１つの実施形態において、上記機能性はヘッドエンドノード内に実装され、トラフィックサービス要求にサービスを提供し及び隣接ノードへトラフィックを転送するシグナリングエンジン２０７が存在する。
【００２２】
バックアップＬＳＰモジュール２０１は、バックアップＬＳＰを生成しヘッドエンドノードと宛て先ノードとの間にバックアップＬＳＰを確立する責任を有する。バックアップＬＳＰモジュール２０１は、プライマリＬＳＰのリンクの各々を“ポイズニング”し又は最大のコストを与えるように、トラフィックエンジニアリングデータベース２０３を修正する。すると、バックアップＬＳＰモジュール２０１は、ＣＳＰＦモジュール２０５が修正されたトラフィックエンジニアリングデータベース２０３に基づいてバックアップＬＳＰを計算するように要求する。ＣＳＰＦモジュール２０５は、トラフィックエンジニアリングデータベース２０３の修正された属性には気づかず、最適なＬＳＰの通常の計算を行う。ＣＳＰＦモジュール２０５によりバックアップＬＳＰがバックアップＬＳＰモジュール２０１へ返却された後、バックアップＬＳＰモジュール２０１は、トラフィックエンジニアリングデータベースを再び修正して、プライマリＬＳＰ内のリンクの各々についての実際のコストを示す元の値を復元する。プライマリＬＳＰの障害の後、シグナリングエンジンにより、バックアップＬＳＰを利用して、ネットワーク上で関連するトラフィックを転送することができる。
【００２３】
図３は、バックアップＬＳＰを計算するための処理の１つの実施形態のフローチャートである。１つの実施形態において、当該プロセスは、ラベルスイッチパス生成要求又はトラフィックサービシング要求に応じて開始される（ブロック３０１）。この要求は、ネットワーク上のヘッドエンドノード又はＰＣＥと通信状態にあるいかなるノードにより生成されてもよい。１つの実施形態において、当該要求は、ヘッドエンドノードにより受信され、又はヘッドエンドノードによりＰＣＥへ転送される。受信後に、当該要求がプライマリＬＳＰを対象としているか又はバックアップＬＳＰを対象としているかを判定するために、当該要求は分析されなければならない（ブロック３０３）。他の実施形態において、プライマリＬＳＰを対象とする要求は、プライマリＬＳＰの完了後に、バックアップＬＳＰの生成を自動的に開始する。プライマリＬＳＰの計算が完了するまで、バックアップＬＳＰを計算することはできない。受信された要求がバックアップＬＳＰを生成しようとするものである場合、プライマリＬＳＰ内の各リンクの位置が、トラフィックエンジニアリングデータベース内で特定されなければならない（ブロック３０７）。リンクの位置を、ラベル又はプライマリＬＳＰと関連付けられる同様の識別子によって特定することができる。トラフィックエンジニアリングデータベース内で識別されるプライマリＬＳＰの各リンクは、修正される（ブロック３０９）。その修正は、そのコストを定義するいかなる値をリンクに与えてもよい。１つの実施形態において、当該コストは、バックアップＬＳＰの計算においてプライマリＬＳＰのリンクの使用が強く抑制されるような、最大のコスト、又はネットワークトポロジーの他のリンクよりも大幅に大きい任意の値である。
【００２４】
リンクの各々が修正された後、ＣＳＰＦ又はプライマリＬＳＰを計算するために使用されたものと同じ同様のパス発見アルゴリズムを用いて、最良のパスが計算される（ブロック３０５）。ＣＳＰＦアルゴリズムは、修正されたリンク情報に依存し、結果として、最大限の分離度を有し、但しトラフィックサービス要求の制約を充足する点で最適なバックアップパスを生成する。バックアップＬＳＰが計算された後、修正されたリンクの各々の元の値が復元される（ブロック３１１）。そして、バックアップＬＳＰは、トラフィックの転送及びＭＰＬＳネットワーク上でのＬＳＰの確立における使用のために、要求側へ供給される（ブロック３１３）。
【００２５】
受信された要求がバックアップＬＳＰを対象としないケースでは、処理は、既存のトラフィックエンジニアリングデータを用いて、単純に最良のパスを計算する（ブロック３０５）。このプライマリＬＳＰは、要求側への応答において、ＭＰＬＳネットワーク上のプライマリＬＳＰを確立するために返却される。
【００２６】
よって、ＭＰＬＳを実装するネットワーク内でバックアップＬＳＰを計算するための方法、システム及び装置が説明された。上述した説明が例示を目的としており、限定的ではないことは、理解されるべきである。上述した説明を読んで理解した後、当業者には、他の多くの実施形態が明らかであろう。本発明の範囲は、従って、添付の特許請求の範囲を参照することにより決定されるべきであり、それに伴う均等の範囲の全体が特許請求の範囲に与えられる。
【技術分野】
【０００１】
本発明の実施形態は、ネットワーク上のマルチプロトコルラベルスイッチングを管理するためのシステムに関する。具体的には、本発明の実施形態は、プライマリラベルスイッチパスについての最適なバックアップパスを決定するための方法及びシステムに関する。
【背景技術】
【０００２】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）は、ネットワーク上のトラフィックを管理するために利用される技術である。ＭＰＬＳは、ネットワークをまたがるトラフィックをルーティングするために、トラフィックのストリームに割当てられる。ネットワークの各ノードは、ネットワーク上で受信されるインカミングのトラフィックを検査し、そのラベルに基づいて当該トラフィックを転送することにより、ＭＰＬＳをサポートする。
【０００３】
トラフィックエンジニアリングのケイパビリティを有するＭＰＬＳネットワークは、カスタマイズされるトラフィックサービスのために、トラフィックエンジニアリングのリソース割当てを最適化することができる。トラフィックエンジニアリングを伴うＭＰＬＳネットワークにおいて、プライマリラベルスイッチパス（ＬＳＰ）は、カスタマイズされるトラフィックサービスごとにセットアップされる。プライマリＬＳＰは、制約付きの最短経路優先（ＣＳＰＦ：Constrained Shortest Path First）アルゴリズムを用いて計算される。プライマリＬＳＰは、通常、パスの起点となるノードであるヘッドエンドノードにおいて計算される。プライマリＬＳＰの確立は、自動化され得る。ＬＳＰの自動的な生成は、ヘッドエンドノード又は別個のパス計算エレメント（ＰＣＥ）により行われ得る。
【０００４】
カスタマイズされるトラフィックサービスごとのバックアップＬＳＰは、プライマリＬＳＰの障害の場合に利用され、手動で構成されなければならない。バックアップＬＳＰ内のリンクの各々は、プライマリＬＳＰが障害の状態にある時に頼ることのできる分離した（disjointed）パスを生成するという目標をもって、バックアップＬＳＰを構築するように手動で選択される。バックアップＬＳＰの手動構成のための技術は、リンクのカラーリング（coloring）及びノードの排除（exclusion）を含む。
【０００５】
しかしながら、これら技術は、管理者によるバックアップＬＳＰの手動での構成に強く依存している。結果として、バックアップＬＳＰの構成は、ヒューマンエラーを引き起こし易い。バックアップＬＳＰを確立しようとする管理者は、バックアップＬＳＰがカスタマイズされるトラフィックサービスの全ての制約又は要件を充足しているかを検証しなければならない。彼らは、考え得る最良の保護をバックアップＬＳＰが提供し、又はバックアップＬＳＰがプライマリＬＳＰからの最大の分離度（disjointness）を有することを、手動で判定しなければならない。
【発明の概要】
【課題を解決するための手段】
【０００６】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するネットワークエレメント上で実行される、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成して、プライマリＬＳＰに信頼できるバックアップを提供する方法であって、前記ネットワークエレメントにより、シグナリングプロトコルを通じて、ＬＳＰの生成についての要求を受信するステップと、前記ＬＳＰの前記生成についての前記要求が前記バックアップＬＳＰを対象とすることを判定するステップと、前記要求が前記バックアップＬＳＰを対象とするという判定に応じて、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するステップと、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、実際のリンクコスト以外のリンクコストを有するように、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを修正するステップと、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するステップと、前記バックアップＬＳＰは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、前記シグナリングプロトコルを通じて、前記バックアップＬＳＰを返却することと、を含む方法である。
【０００７】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのシステムであって、ＬＳＰの生成についての要求を受信するように適合され、及び、パス計算エレメントを呼び出して前記ＬＳＰを取得し、前記ＬＳＰを要求側へ返却するように適合されるラベルスイッチルータと、前記ラベルスイッチルータに連結される前記パス計算エレメント（ＰＣＥ）と、前記ＰＣＥは、前記ＬＳＰの前記生成についての前記要求がバックアップＬＳＰを対象とするかを判定するように適合されることと、前記ＰＣＥは、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するように適合されることと、前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、修正されたコストを有するように修正するように適合されることと、前記修正されたコストは、前記バックアップＬＳＰ内での前記プライマリＬＳＰのリンクの使用を抑制することと、前記ＰＣＥは、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するように適合されることと、前記バックアップＬＳＰは、前記バックアップＬＳＰの計算において使用される前記プライマリＬＳＰの各リンクの前記修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、前記ＰＣＥは、前記第１のラベルスイッチルータへ前記バックアップＬＳＰを返却するように適合されることと、を含むシステムである。
【０００８】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのネットワークエレメントあって、プライマリＬＳＰについてのリンク状態情報を含むネットワークトポロジーについてのリンク状態情報を記憶するように適合されるトラフィックエンジニアリングデータベースと、前記トラフィックエンジニアリングデータベースに連結され、前記バックアップＬＳＰについての要求を処理するように適合されるバックアップパス計算モジュールと、前記バックアップパス計算モジュールは、トラフィックエンジニアリングデータベース内で前記プライマリＬＳＰの各リンクの位置を特定し、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、実際のコスト以外のコストを有するように修正するするように適合されることと、前記バックアップパス計算モジュールに連結され、前記トラフィックエンジニアリングデータベースからの前記リンク状態情報を用いて、宛て先ノードへの最適なパスを判定するための最適パス判定モジュールと、を含むネットワークエレメントである。
【図面の簡単な説明】
【０００９】
本発明は、添付図面の図において限定の形ではなく例示の形で示されており、同等の参照は同様のエレメントを指し示す。なお、本開示における“一”実施形態又は“１つの”実施形態という異なる参照は、必ずしも同じ実施形態へのものではなく、そうした参照は、少なくとも１つを意味する。さらに、特定の特性、構造又は特徴が一実施形態との関連で説明される場合に、明示的に説明されているかによらず、そうした特性、構造又は特徴が他の実施形態との関連でも効果を有することは、当業者の知識の範囲内である。
【００１０】
【図１】マルチプロトコルラベルスイッチングを実装するネットワークの１つの実施形態の図である。
【図２】ヘッドエンドノード又はパス計算エレメントの１つの実施形態の図である。
【図３】バックアップラベルスイッチングパスを生成するための処理の１つの実施形態のフローチャートである。
【発明を実施するための形態】
【００１１】
以下の説明において、多くの具体的な詳細が例示される。しかしながら、本発明の実施形態がこれら具体的な詳細がなくとも実践され得ることが理解される。他の例において、よく知られた回路、構造及び技術は、本説明の理解を曖昧にしないために、詳細には示されていない。しかしながら、当業者であれば、そうした具体的な詳細がなくとも本発明を実践し得ることを理解するであろう。ここに含められる説明によって、当業者は、必要以上の実験を行わなくても、適切な機能性を実装することができるであろう。
【００１２】
図１及び図２の例示的な実施形態を参照しながら、フロー図の作用について説明する。しかしながら、理解されるべき点として、フロー図の作用は、図１及び図２を参照しながら議論されるもの以外の本発明の実施形態によって奏されてもよく、図１及び図２を参照しながら議論される実施形態は、図３のフロー図を参照しながら議論されるものとは異なる作用を奏することもできる。
【００１３】
図に示される技術を、１つ以上の電子デバイス（例えば、エンドステーション、ネットワークエレメントなど）上で記憶され実行されるコード及びデータを用いて実行することができる。そうした電子デバイスは、例えばマシン読取可能な又はコンピュータ読取可能な記憶媒体（例えば、磁気ディスク、光学ディスク、ランダムアクセスメモリ、リードオンリメモリ、フラッシュメモリデバイス及び相変化メモリ）などの、マシン読取可能な又はコンピュータ読取可能な媒体を用いて、コード及びデータを記憶し及び（内部的に及び／又はネットワーク上で他の電子デバイスと）通信する。加えて、そうした電子デバイスは、典型的には、１つ以上のプロセッサのセットを含み、１つ以上のプロセッサのセットは、例えば１つ以上の記憶デバイス、ユーザ入出力デバイス（例えば、キーボード、タッチスクリーン及び／又はディスプレイ）及びネットワーク接続などの、１つ以上の他のコンポーネントと連結される。プロセッサのセットと他のコンポーネントとの連結（coupling）は、典型的には、１つ以上のバス及びブリッジ（バスコントローラともいう）を介する。記憶デバイス及びネットワークトラフィックを搬送する信号は、それぞれ、１つ以上のマシン読取可能な又はコンピュータ読取可能な記憶媒体、及び、マシン読取可能な又はコンピュータ読取可能な通信媒体を表す。よって、所与の電子デバイスの記憶デバイスは、典型的には、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明の実施形態の１つ以上の部分は、ソフトウェア、ファームウェア及び／又はハードウェアの様々な組合せを用いて実装されてよい。
【００１４】
ここで使用されるような、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジなど）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、エンドステーションなど）と通信可能に相互接続する、ハードウェア及びソフトウェアを含む１つのネットワーク機器である。いくつかのネットワークエレメントは、複数のネットワーク機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２集約、セッションボーダ制御、マルチキャスティング及び／又は加入者管理）についてのサポートを提供し、及び／又は複数のアプリケーションサービス（例えば、データ、音声及び映像）についてのサポートを提供する“マルチサービスネットワークエレメント”である。加入者エンドステーション（例えば、サーバ、ワークステーション、ラップトップ、パームトップ、モバイルフォン、スマートフォン、マルチメディアフォン、ＶｏＩＰ（Voice over Internet Protocol）、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲームシステム、セットトップボックス（ＳＩＢ）など）は、インターネット上で提供されるコンテンツ／サービス、及び／又は、インターネット上に重畳されるＶＰＮ（Virtual Private Network）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的には、サービス又はコンテンツプロバイダに属する１つ以上のエンドステーション（例えば、サーバエンドステーション）、又はピアツーピアサービスに参加しているエンドステーションにより提供され、パブリックウェブページ（フリーコンテンツ、ストアフロント、検索サービスなど）、プライベートウェブページ（例えば、ユーザネーム／パスワードでアクセスされる、電子メールサービスを提供するウェブページなど）、ＶＰＮ上の企業ネットワーク、ＩＰＴＶなどを含み得る。典型的には、加入者エンドステーションは、エッジネットワークエレメントに（例えば、（有線で又は無線で）アクセスネットワークに連結される顧客設備機器を通じて）連結され、エッジネットワークエレメントは、他のエンドステーション（例えば、サーバエンドステーション）に（例えば、他のエッジネットワークエレメントへの１つ以上のコアネットワークエレメントを通じて）連結される。
【００１５】
本発明の実施形態は、ヒューマンエラー、非最適なラベルスイッチパス（ＬＳＰ）、最大限分離していないプライマリ及びバックアップＬＳＰ、バックアップＬＳＰの決定論的な生成、並びに、バックアップＬＳＰを手動でセットアップするための管理者の時間及びリソースの莫大な使用、を含む従来技術の欠点を回避するためのシステム、ネットワーク及び方法を提供する。
【００１６】
本発明の実施形態は、バックアップＬＳＰを生成する際に、プライマリＬＳＰのリンクの使用を禁止はしないものの抑制するように、各リンクに高い又は最大のコストを与えることで、トラフィックエンジニアリングデータベース内のプライマリＬＳＰのパスを“ポイズニング”して、これら欠点を克服する。プライマリＬＳＰのリンクが一度このように修正されると、制約付きの最短経路優先（ＣＳＰＦ）アルゴリズムなどのパス発見アルゴリズムが、自動的に、プライマリＬＳＰから最も分離した最適なバックアップＬＳＰを決定論的に判定するために使用され得る。
【００１７】
図１は、ＭＰＬＳを実装するネットワークの１つの実施形態の図である。例としてのネットワーク１００は、ノードＡ〜Ｆを含む。他の実施形態において、ネットワーク内にいかなる数のノードが存在してもよい。ノードの各々は、コンピュータ又はネットワークエレメントを含むいかなる種類のコンピューティングデバイスであってもよい。コンピューティングデバイスは、デスクトップコンピュータ、ラップトップコンピュータ、ネットワーキングエレメント、ルータ、サーバ又は同様のコンピューティングデバイスを含み得る。ノードの各々は、どういったネットワーク媒体上で接続されてもよく、ネットワークのサイズ又は構成も問わない。ネットワークは、ローカリエリアネットワーク（ＬＡＮ）、インターネット又は同様の通信システムなどのワイドエリアネットワーク（ＷＡＮ）であってよい。ネットワーク１００内のノードの各々は、ラベルスイッチパス（ＬＳＰ）に従ってネットワーク１００にわたるトラフィックを管理するための、ＭＰＬＳ又は同様の技術をサポートする。ネットワーク媒体は、いかなる有線又は無線ネットワーキング技術であってもよい。ネットワーク１００は、ヘッドエンドノード１０１及び宛て先ノード１１１を含み得る。ＬＳＰは、ヘッドエンドノード１０１を起点とし、宛て先ノード１１１を終点とする。別個のＬＳＰについて、ネットワーク１００内のいかなる数のノードが、ヘッドエンドノード又は宛て先ノードとして記憶されてもよい。
【００１８】
ヘッドエンドノード１０１は、トラフィックサービス要求に応じて、プライマリＬＳＰ１０７を確立する。ヘッドエンドノード１０１は、ネットワーク１００上のトラフィックサービスごとにプライマリＬＳＰ１０７を確立することもできる。ヘッドエンドノード１０１は、プライマリＬＳＰ１０７を計算するパス計算エレメント（ＰＣＥ）１０３を含み得る。他の実施形態において、ＰＣＥ１０３は、別個のデバイス又はそうでなければヘッドエンドノード１０１とは別々である。本実施形態では、ヘッドエンドノード１０１は、パス計算クライアント（ＰＣＣ）を介してＰＣＥと通信する。
【００１９】
ヘッドエンドノード１０１は、バックアップＬＳＰ１０９を確立するための責任をも有する。バックアップＬＳＰ１０９は、理想的には、プライマリ１０７から最大限の分離度を有する一方で、ヘッドエンドノード１０１から宛て先ノードＣ１１１へ最良の、最も効率的な又は最適なルートを依然として有するＬＳＰである。ＰＣＥ１０３がバックアップＬＳＰ１０９を計算することもできる。バックアップＬＳＰ１０９は、プライマリＬＳＰ１０７が生成される都度、又は、バックアップＬＳＰを計算すべきことを示すトラフィックサービス要求に応じて、計算されてよい。
【００２０】
ネットワーク１００の例において、ノードＡ〜Ｆ間のリンクの各々は、例えば毎秒１ギガビットなどの同等の帯域幅を有する。但し、ノードＣ及びＦの間のリンクを除く。このリンクは、毎秒０．５ギガビットの帯域幅を有する。ヘッドエンドノードにより処理される、ヘッドエンドノード１０１から宛て先ノードＣへのトラフィックサービス要求が、毎秒１ギガビットの帯域幅の要件を有するものとする。プライマリＬＳＰ１０７は、最少のホップを有する最も近道のルートとして、ノードＡ、Ｂ及びＣを通過する。同じ制約付きの最短経路優先（ＣＳＰＦ）アルゴリズム又は同等のアルゴリズムを単純に用いてバックアップＬＳＰ１０９を生成すると、プライマリＬＳＰ１０７と同じルートが生成されるであろう。プライマリＬＳＰ１０７の各リンクが除外されると、バックアップＬＳＰ１０９は、トラフィックサービス要求の制約を満たさないノードＦ及びＣの間のリンクを含まざるを得ないであろう。以下にさらに詳細に説明するＰＣＥは、プライマリＬＳＰ１０７のリンクの各々を最大のコストで重み付けすることによりバックアップＬＳＰ１０９を生成し、それにより、それらリンクの使用を抑制し、但しそれらを禁止しない。この改変された重み又はコストでＣＳＰＦ又は同等のパス発見アルゴリズムが実行され、それにより、修正されたトポロジーについてのコストに基づく最良のパスが生み出される。結果として生じるバックアップＬＳＰ１０９は、プライマリＬＳＰ１０７から最大限の分離度を提供しつつ、一方で要求されたトラフィックサービスの制約を維持する。バックアップＬＳＰ１０９は、依然として、プライマリＬＳＰ１０７との間で共有されるノードＢ及びＣの間のリンクを含み、これは必要であればプライマリＬＳＰ１０７のリンクを使用するという柔軟さの実例である。
【００２１】
図２は、ヘッドエンドノード又はＰＣＥの１つの実施形態の図である。バックアップＬＳＰを計算する機能性は、ヘッドエンドノード、又はヘッドエンドノード内のＰＣＣを介してヘッドエンドノードと通信する別個のＰＣＥのいずれにおいて実装されてもよい。１つの実施形態において、ヘッドエンドノードがその機能性を実装し、当該機能性は、ヘッドエンドノード内に組み込まれる個別のＰＣＥ内にやはりセグメント化されてよい。当業者であれば、バックアップＬＳＰの計算に直接的に関係するヘッドエンドノードのコンポーネント又はＰＣＥのみが示されていることを理解するであろう。ヘッドエンドノード又はＰＣＥは、プライマリＬＳＰを計算するために必要な標準的な機能性及びコンポーネント、並びに他の同様の機能の全てを有することができる。１つの実施形態において、ヘッドエンドノード又はＰＣＥは、バックアップＬＳＰモジュール２０１、トラフィックエンジニアリングデータベース２０３、及び制約付きの最短経路優先（ＣＳＰＦ）モジュール２０５を含む。１つの実施形態において、上記機能性はヘッドエンドノード内に実装され、トラフィックサービス要求にサービスを提供し及び隣接ノードへトラフィックを転送するシグナリングエンジン２０７が存在する。
【００２２】
バックアップＬＳＰモジュール２０１は、バックアップＬＳＰを生成しヘッドエンドノードと宛て先ノードとの間にバックアップＬＳＰを確立する責任を有する。バックアップＬＳＰモジュール２０１は、プライマリＬＳＰのリンクの各々を“ポイズニング”し又は最大のコストを与えるように、トラフィックエンジニアリングデータベース２０３を修正する。すると、バックアップＬＳＰモジュール２０１は、ＣＳＰＦモジュール２０５が修正されたトラフィックエンジニアリングデータベース２０３に基づいてバックアップＬＳＰを計算するように要求する。ＣＳＰＦモジュール２０５は、トラフィックエンジニアリングデータベース２０３の修正された属性には気づかず、最適なＬＳＰの通常の計算を行う。ＣＳＰＦモジュール２０５によりバックアップＬＳＰがバックアップＬＳＰモジュール２０１へ返却された後、バックアップＬＳＰモジュール２０１は、トラフィックエンジニアリングデータベースを再び修正して、プライマリＬＳＰ内のリンクの各々についての実際のコストを示す元の値を復元する。プライマリＬＳＰの障害の後、シグナリングエンジンにより、バックアップＬＳＰを利用して、ネットワーク上で関連するトラフィックを転送することができる。
【００２３】
図３は、バックアップＬＳＰを計算するための処理の１つの実施形態のフローチャートである。１つの実施形態において、当該プロセスは、ラベルスイッチパス生成要求又はトラフィックサービシング要求に応じて開始される（ブロック３０１）。この要求は、ネットワーク上のヘッドエンドノード又はＰＣＥと通信状態にあるいかなるノードにより生成されてもよい。１つの実施形態において、当該要求は、ヘッドエンドノードにより受信され、又はヘッドエンドノードによりＰＣＥへ転送される。受信後に、当該要求がプライマリＬＳＰを対象としているか又はバックアップＬＳＰを対象としているかを判定するために、当該要求は分析されなければならない（ブロック３０３）。他の実施形態において、プライマリＬＳＰを対象とする要求は、プライマリＬＳＰの完了後に、バックアップＬＳＰの生成を自動的に開始する。プライマリＬＳＰの計算が完了するまで、バックアップＬＳＰを計算することはできない。受信された要求がバックアップＬＳＰを生成しようとするものである場合、プライマリＬＳＰ内の各リンクの位置が、トラフィックエンジニアリングデータベース内で特定されなければならない（ブロック３０７）。リンクの位置を、ラベル又はプライマリＬＳＰと関連付けられる同様の識別子によって特定することができる。トラフィックエンジニアリングデータベース内で識別されるプライマリＬＳＰの各リンクは、修正される（ブロック３０９）。その修正は、そのコストを定義するいかなる値をリンクに与えてもよい。１つの実施形態において、当該コストは、バックアップＬＳＰの計算においてプライマリＬＳＰのリンクの使用が強く抑制されるような、最大のコスト、又はネットワークトポロジーの他のリンクよりも大幅に大きい任意の値である。
【００２４】
リンクの各々が修正された後、ＣＳＰＦ又はプライマリＬＳＰを計算するために使用されたものと同じ同様のパス発見アルゴリズムを用いて、最良のパスが計算される（ブロック３０５）。ＣＳＰＦアルゴリズムは、修正されたリンク情報に依存し、結果として、最大限の分離度を有し、但しトラフィックサービス要求の制約を充足する点で最適なバックアップパスを生成する。バックアップＬＳＰが計算された後、修正されたリンクの各々の元の値が復元される（ブロック３１１）。そして、バックアップＬＳＰは、トラフィックの転送及びＭＰＬＳネットワーク上でのＬＳＰの確立における使用のために、要求側へ供給される（ブロック３１３）。
【００２５】
受信された要求がバックアップＬＳＰを対象としないケースでは、処理は、既存のトラフィックエンジニアリングデータを用いて、単純に最良のパスを計算する（ブロック３０５）。このプライマリＬＳＰは、要求側への応答において、ＭＰＬＳネットワーク上のプライマリＬＳＰを確立するために返却される。
【００２６】
よって、ＭＰＬＳを実装するネットワーク内でバックアップＬＳＰを計算するための方法、システム及び装置が説明された。上述した説明が例示を目的としており、限定的ではないことは、理解されるべきである。上述した説明を読んで理解した後、当業者には、他の多くの実施形態が明らかであろう。本発明の範囲は、従って、添付の特許請求の範囲を参照することにより決定されるべきであり、それに伴う均等の範囲の全体が特許請求の範囲に与えられる。
【特許請求の範囲】
【請求項１】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するネットワークエレメント上で実行される、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成して、プライマリＬＳＰに信頼できるバックアップを提供する方法であって、
前記ネットワークエレメントにより、シグナリングプロトコルを通じて、ＬＳＰの生成についての要求を受信するステップと、
前記ＬＳＰの前記生成についての前記要求が前記バックアップＬＳＰを対象とすることを判定するステップと、
前記要求が前記バックアップＬＳＰを対象とするという判定に応じて、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するステップと、
前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、実際のリンクコスト以外のリンクコストを有するように、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを修正するステップと、
前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するステップと、前記バックアップＬＳＰは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、
前記シグナリングプロトコルを通じて、前記バックアップＬＳＰを返却することと、
を含む方法。
【請求項２】
前記バックアップＬＳＰが決定された後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、元のコストを有するようにコスト値を復元するステップ、
をさらに含む、請求項１の方法。
【請求項３】
前記プライマリＬＳＰ内の障害の検出に応じて、前記バックアップＬＳＰに切り替えるステップ、
をさらに含む、請求項１の方法。
【請求項４】
前記要求は、パス通信クライアントから受信される、請求項１の方法。
【請求項５】
前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの位置を特定する前記ステップは、ＭＰＬＳラベルを用いる、請求項１の方法。
【請求項６】
前記バックアップＬＳＰは、前記プライマリＬＳＰの少なくとも１つのリンクを含む、請求項１の方法。
【請求項７】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのシステムであって、
ＬＳＰの生成についての要求を受信するように適合され、及び、パス計算エレメントを呼び出して前記ＬＳＰを取得し、前記ＬＳＰを要求側へ返却するように適合されるラベルスイッチルータと、
前記ラベルスイッチルータに連結される前記パス計算エレメント（ＰＣＥ）と、
前記ＰＣＥは、前記ＬＳＰの前記生成についての前記要求がバックアップＬＳＰを対象とするかを判定するように適合されることと、
前記ＰＣＥは、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するように適合されることと、
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、修正されたコストを有するように修正するように適合されることと、前記修正されたコストは、前記バックアップＬＳＰ内での前記プライマリＬＳＰのリンクの使用を抑制することと、
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するように適合されることと、前記バックアップＬＳＰは、前記バックアップＬＳＰの計算において使用される前記プライマリＬＳＰの各リンクの前記修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、
前記ＰＣＥは、前記第１のラベルスイッチルータへ前記バックアップＬＳＰを返却するように適合されることと、
を含むシステム。
【請求項８】
前記ＰＣＥは、前記バックアップＬＳＰを取得した後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、元のコストを有するようにコスト値を復元するように適合される、請求項７のシステム。
【請求項９】
前記ラベルスイッチルータは、前記プライマリＬＳＰ内の障害の検出に応じて、前記バックアップＬＳＰに切り替えるように適合される、請求項７のシステム。
【請求項１０】
前記ラベルスイッチルータは、前記要求を前記ＰＣＥへ送信するパス通信クライアントを含む、請求項７のシステム。
【請求項１１】
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、ＭＰＬＳラベルによって識別するように適合される、請求項７のシステム。
【請求項１２】
前記ＰＣＥは、ラベルスイッチルータとは別個のデバイスのコンポーネントである、請求項７のシステム。
【請求項１３】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのネットワークエレメントあって、
プライマリＬＳＰについてのリンク状態情報を含むネットワークトポロジーについてのリンク状態情報を記憶するように適合されるトラフィックエンジニアリングデータベースと、
前記トラフィックエンジニアリングデータベースに連結され、前記バックアップＬＳＰについての要求を処理するように適合されるバックアップパス計算モジュールと、
前記バックアップパス計算モジュールは、トラフィックエンジニアリングデータベース内で前記プライマリＬＳＰの各リンクの位置を特定し、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、実際のコスト以外のコストを有するように修正するするように適合されることと、
前記バックアップパス計算モジュールに連結され、前記トラフィックエンジニアリングデータベースからの前記リンク状態情報を用いて、宛て先ノードへの最適なパスを判定するための最適パス判定モジュールと、
を含むネットワークエレメント。
【請求項１４】
前記バックアップパス計算モジュールは、前記バックアップＬＳＰを取得した後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、前記実際のコストを有するようにコスト値を復元するように適合される、請求項１３のネットワークエレメント。
【請求項１５】
前記バックアップパス計算モジュールは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの位置を、ＭＰＬＳラベルによって特定するように適合される、請求項１３のネットワークエレメント。
【請求項１６】
前記要求は、パス通信クライアントから受信される、請求項１３のネットワークエレメント。
【請求項１７】
前記バックアップＬＳＰは、前記プライマリＬＳＰの少なくとも１つのリンクを含む、請求項１３のネットワークエレメント。
【請求項１８】
前記最適パス判定モジュールは、ＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実装する、請求項１３のネットワークエレメント。
【請求項１】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するネットワークエレメント上で実行される、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成して、プライマリＬＳＰに信頼できるバックアップを提供する方法であって、
前記ネットワークエレメントにより、シグナリングプロトコルを通じて、ＬＳＰの生成についての要求を受信するステップと、
前記ＬＳＰの前記生成についての前記要求が前記バックアップＬＳＰを対象とすることを判定するステップと、
前記要求が前記バックアップＬＳＰを対象とするという判定に応じて、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するステップと、
前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、実際のリンクコスト以外のリンクコストを有するように、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを修正するステップと、
前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するステップと、前記バックアップＬＳＰは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、
前記シグナリングプロトコルを通じて、前記バックアップＬＳＰを返却することと、
を含む方法。
【請求項２】
前記バックアップＬＳＰが決定された後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、元のコストを有するようにコスト値を復元するステップ、
をさらに含む、請求項１の方法。
【請求項３】
前記プライマリＬＳＰ内の障害の検出に応じて、前記バックアップＬＳＰに切り替えるステップ、
をさらに含む、請求項１の方法。
【請求項４】
前記要求は、パス通信クライアントから受信される、請求項１の方法。
【請求項５】
前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの位置を特定する前記ステップは、ＭＰＬＳラベルを用いる、請求項１の方法。
【請求項６】
前記バックアップＬＳＰは、前記プライマリＬＳＰの少なくとも１つのリンクを含む、請求項１の方法。
【請求項７】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を自動的に生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのシステムであって、
ＬＳＰの生成についての要求を受信するように適合され、及び、パス計算エレメントを呼び出して前記ＬＳＰを取得し、前記ＬＳＰを要求側へ返却するように適合されるラベルスイッチルータと、
前記ラベルスイッチルータに連結される前記パス計算エレメント（ＰＣＥ）と、
前記ＰＣＥは、前記ＬＳＰの前記生成についての前記要求がバックアップＬＳＰを対象とするかを判定するように適合されることと、
前記ＰＣＥは、トラフィックエンジニアリングデータベース内で、前記プライマリＬＳＰの各リンクの位置を特定するように適合されることと、
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、修正されたコストを有するように修正するように適合されることと、前記修正されたコストは、前記バックアップＬＳＰ内での前記プライマリＬＳＰのリンクの使用を抑制することと、
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース上でＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実行して、前記バックアップＬＳＰを取得するように適合されることと、前記バックアップＬＳＰは、前記バックアップＬＳＰの計算において使用される前記プライマリＬＳＰの各リンクの前記修正されたコストに起因して、前記プライマリＬＳＰからの最大の分離度を有することと、
前記ＰＣＥは、前記第１のラベルスイッチルータへ前記バックアップＬＳＰを返却するように適合されることと、
を含むシステム。
【請求項８】
前記ＰＣＥは、前記バックアップＬＳＰを取得した後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、元のコストを有するようにコスト値を復元するように適合される、請求項７のシステム。
【請求項９】
前記ラベルスイッチルータは、前記プライマリＬＳＰ内の障害の検出に応じて、前記バックアップＬＳＰに切り替えるように適合される、請求項７のシステム。
【請求項１０】
前記ラベルスイッチルータは、前記要求を前記ＰＣＥへ送信するパス通信クライアントを含む、請求項７のシステム。
【請求項１１】
前記ＰＣＥは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、ＭＰＬＳラベルによって識別するように適合される、請求項７のシステム。
【請求項１２】
前記ＰＣＥは、ラベルスイッチルータとは別個のデバイスのコンポーネントである、請求項７のシステム。
【請求項１３】
プライマリＬＳＰに信頼できるバックアップを提供するために、プライマリＬＳＰから最も分離した最適で決定論的なバックアップラベルスイッチパス（ＬＳＰ）を生成するようにマルチプロトコルラベルスイッチング（ＭＰＬＳ）を実装するためのネットワークエレメントあって、
プライマリＬＳＰについてのリンク状態情報を含むネットワークトポロジーについてのリンク状態情報を記憶するように適合されるトラフィックエンジニアリングデータベースと、
前記トラフィックエンジニアリングデータベースに連結され、前記バックアップＬＳＰについての要求を処理するように適合されるバックアップパス計算モジュールと、
前記バックアップパス計算モジュールは、トラフィックエンジニアリングデータベース内で前記プライマリＬＳＰの各リンクの位置を特定し、前記バックアップＬＳＰ内での前記プライマリＬＳＰの各リンクの使用を抑制するために、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクを、実際のコスト以外のコストを有するように修正するするように適合されることと、
前記バックアップパス計算モジュールに連結され、前記トラフィックエンジニアリングデータベースからの前記リンク状態情報を用いて、宛て先ノードへの最適なパスを判定するための最適パス判定モジュールと、
を含むネットワークエレメント。
【請求項１４】
前記バックアップパス計算モジュールは、前記バックアップＬＳＰを取得した後に、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクについて、前記実際のコストを有するようにコスト値を復元するように適合される、請求項１３のネットワークエレメント。
【請求項１５】
前記バックアップパス計算モジュールは、前記トラフィックエンジニアリングデータベース内の前記プライマリＬＳＰの各リンクの位置を、ＭＰＬＳラベルによって特定するように適合される、請求項１３のネットワークエレメント。
【請求項１６】
前記要求は、パス通信クライアントから受信される、請求項１３のネットワークエレメント。
【請求項１７】
前記バックアップＬＳＰは、前記プライマリＬＳＰの少なくとも１つのリンクを含む、請求項１３のネットワークエレメント。
【請求項１８】
前記最適パス判定モジュールは、ＣＳＰＦ（Constrained Shortest Path First）アルゴリズムを実装する、請求項１３のネットワークエレメント。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２０１３−５１０４５９（Ｐ２０１３−５１０４５９Ａ）
【公表日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願番号】特願２０１２−５３５９９２（Ｐ２０１２−５３５９９２）
【出願日】平成２２年１０月２６日（２０１０．１０．２６）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５４８５２
【国際公開番号】ＷＯ２０１１／０５５２７３
【国際公開日】平成２３年５月１２日（２０１１．５．１２）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【Ｆターム（参考）】
【公表日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願日】平成２２年１０月２６日（２０１０．１０．２６）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５４８５２
【国際公開番号】ＷＯ２０１１／０５５２７３
【国際公開日】平成２３年５月１２日（２０１１．５．１２）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【Ｆターム（参考）】
[ Back to top ]