(57)【要約】  マルチキャストネットワークのネットワーク出口ノード上で、プライマリマルチキャストツリーとスタンバイマルチキャストツリーの間で切り換えるための機能が提供される。ネットワーク出口ノードは、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコードと、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコードと、複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードとを含む。ＭＰＬＳラベルレコードは、それぞれパラメータを含み、パラメータの値は、パケットを受け入れるか、それとも破棄するかを判定するために適用される各パケット処理ルールを示している。ＭＰＬＳラベルレコードのパラメータが第１の値に設定されたとき、関連付けられたマルチキャストツリーを介して受信されたパケットを受け入れるか、それとも破棄するかに関する判定は、ＭＰＬＳラベルレコードのツリー識別子を、マルチキャストレコードのプライマリツリー識別子とだけ比較することにより行われる。ＭＰＬＳラベルレコードのパラメータが、第２の値に設定されたとき、関連付けられたマルチキャストツリーを介して受信されたパケットを受け入れるか、それとも破棄するかに関する判定は、ＭＰＬＳラベルレコードのツリー識別子を、マルチキャストレコードのプライマリツリー識別子、またはマルチキャストレコードのスタンバイツリー識別子と比較することにより行われる。
2013535911.tif 000002
【特許請求の範囲】
【請求項１】
ノードで、第１のマルチキャストツリーから第２のマルチキャストツリーに切り換えることを可能にする方法であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、方法が、
第１のマルチキャストツリーの障害が検出されたとき、第２のＭＰＬＳラベルレコードのパラメータを第１の値から第２の値に切り換えるステップであり、第１の値および第２の値が、第２のマルチキャストツリーを介してノードで受信したパケットを受け入れるか、それとも破棄するかを判定するために適用される第１および第２の処理ルールをそれぞれ示している、方法。
【請求項２】
第１の処理ルールが、
パケットが、第２のマルチキャストツリーを介して受信されたとき、パケットを受け入れるか、それとも破棄するかを判定するために、第２のＭＰＬＳラベルレコードからの第２のツリー識別子を、マルチキャストレコードのプライマリツリー識別子とだけ比較するステップを含む、請求項１に記載の方法。
【請求項３】
第２の処理ルールが、
パケットが、第２のマルチキャストツリーを介して受信されたとき、パケットを受け入れるか、それとも破棄するかを判定するために、第２のＭＰＬＳラベルレコードからの第２のツリー識別子を、マルチキャストレコードのプライマリツリー識別子、またはスタンバイツリー識別子と比較するステップを含む、請求項１に記載の方法。
【請求項４】
第１の値が、パケットを第２のマルチキャストツリーを介して受信すると、パケットは、第２のＭＰＬＳラベルレコードの第２のツリー識別子が、マルチキャストレコードのプライマリツリー識別子の１つと一致する場合に限って受け入れられることを示しており、かつ
第２の値が、パケットを第２のマルチキャストツリーを介して受信すると、パケットは、第２のＭＰＬＳラベルレコードの第２のツリー識別子が、マルチキャストレコードのプライマリツリー識別子の１つ、またはスタンバイツリー識別子の１つと一致する場合に受け入れられることを示している、請求項１に記載の方法。
【請求項５】
第２のマルチキャストツリーを介してパケットを受信するステップと、
第２のＭＰＬＳラベルレコードから第２のマルチキャストツリーの第２のツリー識別子を求めるステップと、
第２のＭＰＬＳラベルレコードからパラメータの値を求めるステップと、
第２のＭＰＬＳラベルレコードからのパラメータの値に基づいて第１または第２の処理ルールを適用するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
第１のＭＰＬＳラベルレコードのツリー識別子を、第１のツリー識別子から無効値に変更するステップをさらに含む、請求項１に記載の方法。
【請求項７】
第１のマルチキャストツリーを介してパケットを受信するステップと、
第１のＭＰＬＳラベルレコードから第１のマルチキャストツリーの第１のツリー識別子を求めるステップと、
第１のＭＰＬＳラベルレコードからパラメータの値を求めるステップと、
パケット処理ルールの結果に基づき受信したパケットを破棄するステップであり、適用されるパケット処理ルールは、第１のＭＰＬＳラベルレコードからのパラメータの値に基づいて選択される、ステップと
をさらに含む、請求項１に記載の方法。
【請求項８】
プライマリツリー識別子のそれぞれを、第２のマルチキャストツリーの第２のツリー識別子を指し示すように切り換えることにより、かつスタンバイツリー識別子のそれぞれを、第１のマルチキャストツリーの第１のツリー識別子を指し示すように切り換えることにより、マルチキャストレコードを変更するステップをさらに含む、請求項１に記載の方法。
【請求項９】
ノードで、第１のマルチキャストツリーから第２のマルチキャストツリーに切り換えることを可能にする装置であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、装置が、
第１のマルチキャストツリーの障害が検出されたとき、第２のＭＰＬＳラベルレコードのパラメータを第１の値から第２の値に切り換えるように構成されたプロセッサであり、第１の値および第２の値が、第２のマルチキャストツリーを介してノードで受信したパケットを受け入れるか、それとも破棄するかを判定するために適用される第１および第２の処理ルールをそれぞれ示している、プロセッサ
を備える、装置。
【請求項１０】
第１のマルチキャストツリーおよび第２のマルチキャストツリーをサポートするノードでパケットを受信するための方法であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、方法が、
マルチキャストツリーの一つを介してパケットを受信するステップと、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのパラメータの値を求めるステップと、
パラメータの値に基づいて、パケットに適用すべきパケット処理ルールを決めるステップと
を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、通信ネットワークに関し、またより詳細には、これだけに限らないが、マルチキャスト通信ネットワークにおけるマルチキャストツリー間の切換えに関する。
【背景技術】
【０００２】
マルチキャストサービスを求める要求が増加し続けているのに伴い、サービスプロバイダは、マルチキャストサービスをサポートするための低コストで、帯域幅効率がよく、耐障害性のあるマルチキャスト移送機能を絶えず求めている。マルチプロトコルラベルスイッチング（ＭＰＬＳ）は、ラベルスイッチトパス（ＬＳＰ）を用いて、広範囲な差別化されたエンドツーエンドサービスの効率的な配信を可能にする。多くのＭＰＬＳネットワークでは、ポイントツーマルチポイント（Ｐ２ＭＰ）ツリーが、様々なサービスを移送するマルチキャストストリームをサポートするために使用される。このようなネットワークでは、マルチキャストストリームがＭＰＬＳネットワークから出る位置にあるネットワーク出口ノードは、２つのＰ２ＭＰ  ＬＳＰツリー、すなわち、プライマリＰ２ＭＰ  ＬＳＰツリーおよびスタンバイＰ２ＭＰ  ＬＳＰツリーを介してパケットを受け取る。ネットワーク出口ノードは、障害が起きるまで、プライマリＰ２ＭＰ  ＬＳＰツリーからパケットを受け取るが、障害が起きたとき、ネットワーク出口ノードは、プライマリＰ２ＭＰ  ＬＳＰツリーが回復するまで、スタンバイＰ２ＭＰ  ＬＳＰツリーからパケットを受け入れるように切り換える。
【０００３】
しかし、ネットワーク出口ノードにおける既存のマルチキャストツリー切換え機構は、十分に高速ではないという欠点がある。既存のネットワーク出口ノードでは、ネットワーク出口ノードの転送エンジンが、ＭＰＬＳラベルレコードおよびマルチキャストレコードを含み、また既存のネットワーク出口ノード上の既存のマルチキャストツリー切換え機構は、プライマリＰ２ＭＰ  ＬＳＰツリーの障害が起きた後、トラフィックがスタンバイＰ２ＭＰ  ＬＳＰツリーを介して受け入れることができる前に、ネットワーク出口ノードのマルチキャストレコードのチャネルレコードのすべてを再プログラミングするように要求する。その結果、ｎ個のチャネルレコードを有するマルチキャストレコードの場合、マルチキャストレコードを再プログラミングすることは、オーダーＯ（ｎ）の演算になり、それは、完了するまでにかなりの量のトラフィック損失を生ずる可能性がある。したがって、既存のネットワーク出口ノードでは、トラフィックは、ネットワーク出口ノードが、プライマリマルチキャストツリーとスタンバイマルチキャストツリーの間を切り換えるときに失われるが、それは、ＳＬＡ（サービスレベルに関する合意）の下に、または加入者が感ずる品質の点で受け入れられない可能性がある。
【発明の概要】
【課題を解決するための手段】
【０００４】
マルチキャストネットワークのネットワーク出口ノードで、プライマリマルチキャストツリーとスタンバイマルチキャストツリーの間で切り換えるための機能が提供される。ネットワーク出口ノードは、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコードと、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコードと、複数のプライマリツリー識別子、および複数のスタンバイツリー識別子を含むマルチキャストレコードとを含む。ＭＰＬＳラベルレコードは、それぞれパラメータを含み、パラメータの値は、パケットを受け入れるか、それとも破棄するかを判定するために適用される各パケット処理ルールを示している。ＭＰＬＳラベルレコードのパラメータが第１の値に設定されたとき、関連付けられたマルチキャストツリーを介して受信されたパケットを受け入れるか、それとも破棄するかに関する判定が、ＭＰＬＳラベルレコードのツリー識別子を、マルチキャストレコードのプライマリツリー識別子とだけ比較することにより行われる。ＭＰＬＳラベルレコードのパラメータが、第２の値に設定されたとき、関連付けられたマルチキャストツリーを介して受信したパケットを受け入れるか、それとも破棄するかに関する判定が、ＭＰＬＳラベルレコードのツリー識別子を、マルチキャストレコードのプライマリツリー識別子、またはマルチキャストレコードのスタンバイツリー識別子と比較することにより行われる。
【０００５】
本明細書の教示は、添付の図面と共に、以下の詳細な記述を検討することにより容易に理解することができる。
【図面の簡単な説明】
【０００６】
【図１】マルチキャストツリー間で切り換えるように構成されたネットワーク出口ノードを含む例示的なビデオ配信システムの高水準のブロック図である。
【図２】図１の例示的なビデオ配信システムのネットワーク出口ノードの例示的なデータ構造を示す図である。
【図３】ネットワーク出口ノードの一実施形態の高水準のブロック図である。
【図４】プライマリマルチキャストツリーからスタンバイマルチキャストツリーに切り換えるようにネットワーク出口ノードを構成する方法の一実施形態を示す図である。
【図５】プライマリマルチキャストツリーに障害が起きた後、スタンバイマルチキャストツリーからパケットを受け入れる方法の一実施形態を示す図である。
【図６】本明細書で述べる機能を実施するために使用するのに適したコンピュータの高水準ブロック図である。
【発明を実施するための形態】
【０００７】
容易に理解できるように、可能な限り、諸図に共通の同一の要素を指定するために同一の参照数字を使用している。
【０００８】
マルチキャストツリー間で切り換えるためのマルチキャストツリー切換え機能が、本明細書で示され、かつ述べられる。本マルチキャストツリー切換え機能は、マルチキャストツリー間で切り換えるための機構を改良し、マルチキャストツリー間で切り換える既存の機構を用いて可能な速度よりも高速にストリームからストリームへの移行を実行することができる。マルチキャストツリー切換え機能は、マルチキャストツリーのマルチキャストストリーム間を切り換える高速な機構を提供することにより、例えば、負荷の共有、保守などのための障害（例えば、コンポーネント、リンクなどの）に応じて、切換えが行われたとき、エンドユーザに対する影響を最小化する。マルチキャストツリー切換え機能は、高速なストリーム切換え機構を提供することによりパケット損失を低減し、したがって、エンドユーザが感ずる品質を高める。
【０００９】
マルチキャストツリー切換え機能は、ビデオトラフィックが、２つのマルチキャストツリーを用いて、冗長的にネットワークを介して移送されるというネットワーク環境で有用になりうるが、その場合には、２つのマルチキャストツリーが、同じまたは異なる入口ネットワークノードでネットワークに入り、また２つのマルチキャストツリーは、ネットワーク出口ノードを介して（例えば、ビデオトラフィックを可能性のある下流の受信者に転送するために）ネットワークを出る。この環境において、マルチキャストツリー切換え機能は、２つのマルチキャストツリーを介してビデオトラフィックを受け取るネットワーク出口ノードが、（ビデオトラフィックを可能性のある下流の受信者に転送するために）マルチキャストツリーの一つを介して受信するビデオトラフィックにアクセスできるが、他のマルチキャストツリーを介して受信するビデオトラフィックを拒否することのできる機構を提供する。
【００１０】
主として、同報通信／マルチキャストビデオ配信システムの環境内で（すなわち、ＩＰ（インターネットプロトコル）／ＭＰＬＳ（マルチプロトコルラベルスイッチング）ネットワークを介するビデオトラフィックをマルチキャスト移送する環境内で）示され、かつ述べられているが、マルチキャストツリー切換え機能は、マルチキャストストリーム間の切換えが必要な、または望ましい任意の他のタイプのシステム内で実施することができる（例えば、別タイプの基本ネットワークおよび／またはプロトコルを用いる他のタイプのビデオ配信システム、他のタイプのトラフィックの移送をサポートするネットワークなどで、ならびにそれらの様々な組合せで実施することができる）。
【００１１】
図１は、マルチキャストツリー間で切り換えるように構成されたネットワーク出口ノードを含む例示的なビデオ配信システムの高水準のブロック図を示す。
【００１２】
例示的なビデオ配信システム１００は、ソースノード１１０、マルチキャストネットワーク１２０、および受信ノード１３０を含む。マルチキャストネットワーク１２０は、複数のルータ１２２１−１２２５（総称して、ルータ１２２）を含む。ソースノード１１０、ルータ１２２、および受信ノード１３０は結合されており、したがって、通信リンクを介して通信する。図１で示すように、ソースノード１１０、ルータ１２２、および受信ノード１３０は、以下のように結合される：（ａ）ソースノード１１０はルータ１２２１および１２２２に結合される、（ｂ）ルータ１２２１、１２２２、１２２３、および１２２４はフルメッシュで結合される、（ｃ）ルータ１２２３および１２２４は共にルータ１２２５に結合される、（ｄ）ルータ１２２５は受信ノード１３０に結合される。
【００１３】
ソースノード１１０は、ビデオトラフィックをビデオストリームとして（ビデオチャネルと呼ぶこともできる）配信する。ソースノード１１０は、ビデオトラフィックを受信ノード１３０にマルチキャストするために、ビデオトラフィックをマルチキャストネットワーク１２０に配信する。図１で示すように、ソースノード１１０は、ビデオトラフィックをルータ１２２１と１２２２の両方に配信する。ソースノード１１０は、ビデオトラフィックを任意の適切な方法で配信することができる。一実施形態では、例えば、ソースノード１１０は、ビデオトラフィックのビデオストリームに対して一意のＩＰマルチキャストアドレスを使用し、ＩＰマルチキャストパケットとしてビデオトラフィックを配信する。ソースノード１１０は、任意の適切なソース（例えば、ビデオトラフィックがソースノード１１０に記憶されている場所からローカルに、１つまたは複数の他のネットワーク要素から、および同様のものなど）からビデオトラフィックを得ることができる。
【００１４】
マルチキャストネットワーク１２０は、ソースノード１１０からビデオトラフィックを受信し、受信ノード１３０へ配信するためにビデオトラフィックをマルチキャストする。マルチキャストネットワーク１２０は、任意の適切なマルチキャスト機能を利用する任意の適切なタイプのネットワークとすることができる。一実施形態では、例えば、マルチキャストネットワーク１２０は、ポイントツーマルチポイント（Ｐ２ＭＰ）ラベルスイッチトパス（ＬＳＰ）を用いたビデオトラフィックのマルチキャストをサポートするように構成されたＩＰ／ＭＰＬＳネットワークである。Ｐ２ＭＰ  ＬＳＰの特性は、当業者であれば理解されよう。
【００１５】
図１で示すように、ルータ１２２１および１２２２は、ソースノード１１０からビデオトラフィックを受信し、そのトラフィックをルータ１２２５へマルチキャストする。ルータ１２２１は、ルータ１２２１とルータ１２２５の間で構成されたプライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して、ビデオトラフィックをルータ１２２５にマルチキャストするが、そのツリーは、ルータ１２２１からルータ１２２３、ルータ１２２５への経路を横断している（本明細書では、Ｂｌｕｅ  Ｐ２ＭＰ  ＬＳＰまたはＰ２ＭＰ−ＢＬＵＥとも呼ぶ）。ルータ１２２２は、ルータ１２２２とルータ１２２５の間で構成されたスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して、ビデオトラフィックをルータ１２２５にマルチキャストするが、そのツリーは、ルータ１２２２からルータ１２２４、ルータ１２２５への経路を横断している（本明細書では、Ｒｅｄ  Ｐ２ＭＰ  ＬＳＰまたはＰ２ＭＰ−ＲＥＤとも呼ぶ）。プライマリＰ２ＭＰ  ＬＳＰツリー１２５１およびスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２は、本明細書で、総称的にＰ２ＭＰ  ＬＳＰツリー１２５と呼ぶ。Ｐ２ＭＰ  ＬＳＰツリー１２５は、任意の適切な方法で（例えば、ＲＳＶＰ−ＴＥ（リソース予約プロトコル−トラフィックエンジニアリング）ベースの制御プレーンシグナリングを用いて、かつ／または任意の他の適切な方法で）マルチキャストネットワーク１２０内で構成することができる。ルータ１２２１および１２２２は、ネットワーク入口ノードとして動作する。概して、この環境では、ネットワーク入口ノードは、（１）Ｐ２ＭＰ  ＬＳＰツリーが開始するノードであり、かつ（２）ＩＰマルチキャストパケットでソースノードから受信したトラフィックが、そこでＭＰＬＳを用いてＭＰＬＳラベルでカプセル化され、Ｐ２ＭＰ  ＬＳＰツリーを介して伝達されるノードである。
【００１６】
図１でさらに示すように、ルータ１２２５は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１とスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を共に経由してビデオソース１１０からビデオトラフィックを受け取る。ルータ１２２５は、Ｐ２ＭＰ  ＬＳＰツリー１２５の一つからビデオトラフィックを受け入れ、Ｐ２ＭＰ  ＬＳＰツリー１２５の他のものからのビデオトラフィックを（このようなビデオトラフィックはルータ１２２５にとって冗長なものであるため）破棄するように構成される。すなわち、ルータ１２２５は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１がアクティブである限り、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からのビデオトラフィックを受け入れ、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２からのビデオトラフィックを破棄するように構成され、またさらに、ビデオトラフィックが、（例えば、障害に応じて）プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からこれ以上利用できない場合、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２からビデオトラフィックを受け入れるべく切り換えるように構成される。本明細書で述べるように、マルチキャストツリー切換え機能は、ルータ１２２５が、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からビデオトラフィックを受け取ることを、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２からビデオトラフィックを受け取るように切り換える処理を改良するように構成される。ルータ１２２５は、ネットワーク出口ノードとして動作し、したがって、本明細書では、ネットワーク出口ノード１２２５と呼ぶこともできる。概して、この環境では、ネットワーク出口ノードは、（１）Ｐ２ＭＰ  ＬＳＰツリーが終了するノードであり、（２）そのノードで、ＭＰＬＳラベルカプセル化が除かれ、ＩＰマルチキャストとしてトラフィックが、１つまたは複数のローカルの出力インターフェース上で伝達されてトラフィックチャネルの可能性のある受信者（例として、受信ノード１３０）へと送られる。
【００１７】
例示的なビデオ配信システム１００の前述の説明から、マルチキャストツリー切換え機能は、ビデオトラフィックが、ネットワーク入口ノードによりＭＰＬＳカプセル化が行われ、かつマルチキャストＰ２ＭＰ  ＬＳＰツリーを介してネットワーク出口ノードに伝達される、ＩＰ／ＭＰＬＳネットワーククラウドを介して、複数のチャネルをサポートする任意の同報通信／マルチキャストビデオ配信システムの環境において少なくとも利用できることが理解されよう。多くのこのようなアプリケーションでは、ネットワーク出口ノードは、ネットワーク入口ノードから始まるＰ２ＭＰ  ＬＳＰツリーを介して、２つの異なるネットワーク入口ノードからビデオトラフィックをそれぞれ受け取る。同様に、多くのこのようなアプリケーションでは、各ネットワーク出口ノードは、ネットワーク出口ノードに利用可能なＰ２ＭＰ  ＬＳＰツリーのいずれかから異なるチャネルを受け取るように選択することができる。このタイプの冗長性は、通常、プライマリＰ２ＭＰ  ＬＳＰツリーで障害が生じたとき、損失を最小にするために（すなわち、プライマリＰ２ＭＰ  ＬＳＰツリーに関連付けられたスタンバイＰ２ＭＰ  ＬＳＰツリーに迅速に切り換えることにより）使用される。多くのこのようなアプリケーション（例えば、ビデオトラフィックの配信）では、このようなＰ２ＭＰ  ＬＳＰツリーの障害が生じたとき、トラフィック損失を１秒未満にすることが望ましい。
【００１８】
ネットワーク出口ノード１２２５は、Ｐ２ＭＰ  ＬＳＰツリー１２５により移送されるマルチキャストストリームの間を切り換えるためのマルチキャストツリー切換えを行うように構成される。すなわち、ネットワーク出口ノード１２２５は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害検出に応じて、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からスタンバイＰ２ＭＰツリー１２５２に切り換えるように構成され、同様に、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の回復を検出したことに応じて、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２からプライマリＰ２ＭＰ  ＬＳＰツリー１２５１に切り換えて戻るように構成することができる。
【００１９】
ネットワーク出口ノード１２２５は、Ｐ２ＭＰ  ＬＳＰツリー１２５間で切り換えるための、したがって、Ｐ２ＭＰ  ＬＳＰツリー１２５により移送されるマルチキャストストリーム間を切り換えるためのマルチキャストツリー切換えを可能にするように構成された転送エンジンを含む。転送エンジンは、Ｐ２ＭＰ  ＬＳＰツリー１２５により移送されるマルチキャストストリーム間を切り換えるためのマルチキャストツリー切換えを可能にするのに使用されるように構成されたデータ構造を管理する。Ｐ２ＭＰ  ＬＳＰツリー１２５により移送されるマルチキャストストリーム間を切り換えるためにデータ構造を使用することは、図２を参照することにより、よく理解することができる。
【００２０】
図２は、図１の例示的なビデオ配信システムのネットワーク出口ノードの例示的なデータ構造を示している。図２は、（１）プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害が、ネットワーク出口ノード１２２５で検出される前のデータ構造の第１の状態２０１Ｂ、および（２）プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害が、ネットワーク出口ノード１２２５で検出された後のデータ構造の第２の状態２０１Ａを示す。
【００２１】
図２で示すように、データ構造は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のための第１のＭＰＬＳラベルレコード２１０Ｐと、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のための第２のＭＰＬＳラベルレコード２１０Ｓ（総称的に、ＭＰＬＳラベルレコード２１０）と、マルチキャストレコード２２０とを含む。
【００２２】
ＭＰＬＳラベルレコード２１０Ｐおよび２１０Ｓ（ＩＬＭ（Ｉｎｃｏｍｉｎｇ  Ｌａｂｅｌ  Ｍａｐ）テーブルと呼ぶこともできる）は、それぞれ、プライマリおよびスタンバイＰ２ＭＰ  ＬＳＰツリー１２５１、１２５２を介して受信されたＭＰＬＳラベルでカプセル化されたパケットに使用するためのルックアップテーブルである。ＭＰＬＳラベルレコード２１０は、各Ｐ２ＭＰ  ＬＳＰツリー１２５に対して一意のものである。ＭＰＬＳラベルレコード２１０はそれぞれ、ツリー識別子（ＭＰＬＳラベルレコード２１０のＰ２ＭＰ  ＬＳＰツリー１２５を識別する）を含む。ＭＰＬＳラベルレコード２１０はまたそれぞれ、本明細書で状態ビットと呼ぶ新しいパラメータを含み、パラメータは、マルチキャストツリー切換え機能に従って、マルチキャストツリー切換えを可能にする。本明細書で述べるように、一実施形態では、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に障害が起きると、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２への高速の切換えが、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード２１０Ｓを再プログラミングすることにより（また任意選択で、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード２１０Ｐを再プログラミングすることにより）達成される。
【００２３】
マルチキャストレコード２２０（ＳＧテーブルと呼ぶこともできる）は、Ｐ２ＭＰ  ＬＳＰツリー１２５により受信されたＭＰＬＳラベルでカプセル化されたパケットに使用されるルックアップテーブルである。マルチキャストレコード２２０は、各マルチキャストチャネルに対して、プライマリツリー識別子（現在、アクティブなツリーとして設定されたＰ２ＭＰ  ＬＳＰツリー１２５のツリー識別子を示す）、およびスタンバイツリー識別子（現在、スタンバイツリーとして設定されたＰ２ＭＰ  ＬＳＰツリー１２５のツリー識別子を示す）を含むマルチキャストチャネルレコードを含む。マルチキャストレコード２２０は、ソースおよびマルチキャストアドレスに基づき、Ｐ２ＭＰ  ＬＳＰツリー１２５を介して受け取られるパケットに対してルックアップを行うために使用される。
【００２４】
ＭＰＬＳラベルレコード２１０およびマルチキャストレコード２２０は、受信したパケットを処理するために、例えば、受信したパケットを受け入れるか、それとも破棄するかを判定するために使用される。概して、マルチキャストパケットがネットワーク出口ノード１２２５で受け取られたとき、回線から到来したパケットは、ＩＰパケット内に移送すべき情報（例えば、ビデオ）を含み、それは、ＭＰＬＳヘッダ（ＭＰＬＳラベルを含む）でカプセル化されており、イーサネット（登録商標）ヘッダでさらにカプセル化される。マルチキャストパケットが受信されたとき、イーサネットヘッダは除去され、またパケットのＭＰＬＳヘッダからのＭＰＬＳラベルが使用されて、パケットを処理するためにＭＰＬＳラベルレコード２１０のどれを使用すべきかが識別される（例えば、検索動作、または任意の他の適切な方法を用いる）。識別されたＭＰＬＳラベルレコードのツリー識別子は、次いで、パケットを受け入れるべきか、それとも破棄すべきかを判定するために、マルチキャストレコード中の情報と比較するためのツリー識別子として使用される。
【００２５】
図２で示すように、第１の状態２０１Ｂで、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐは、ＢＬＵＥのツリー識別子および０に設定された状態ビットを有し、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２に関連付けられたＭＰＬＳラベルレコード２１０Ｓは、ＲＥＤのツリー識別子および０に設定された状態ビットを有し、またマルチキャストレコード２２０は、各エントリが、ＢＬＵＥに設定されたプライマリツリー識別子、およびＲＥＤに設定されたスタンバイツリー識別子を有するＮ個のエントリを含む。言い換えると、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に障害が起きる前は、ＭＰＬＳラベルレコード２２０のそれぞれの状態ビットのデフォルト値は０である。ネットワーク出口ノード１２２５の転送エンジンは、ＭＰＬＳラベルレコード２１０のいずれも状態ビットの値が０に設定され、パケットがＰ２ＭＰ  ＬＳＰツリー１２５の一つを介して受信されたとき、転送エンジンは、マルチキャストレコード２２０のプライマリツリー識別子だけを、パケットが介して受信されたＰ２ＭＰ  ＬＳＰツリー１２５のＭＰＬＳラベルレコード２１０から取得されたツリー識別子と比較するように構成される。その結果、図２の状態２０１Ｂで示されるように、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害が起きる前は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して受信したパケットだけが受け入れられて転送されるが、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信されたパケットは破棄されることになる。
【００２６】
第１の状態２０１Ｂでは、パケットが、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して受信されたとき、ツリー識別子ＢＬＵＥが、ライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐから取得され、状態ビット値が０であることにより、マルチキャストレコード２２０のプライマリツリー識別子とだけ比較される。この場合、マルチキャストレコード２２０中のプライマリツリー識別子のすべてが、ＢＬＵＥの値を有しているので、一致が見出され、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して受信したパケットが受け入れられて、転送される。
【００２７】
第１の状態２０１Ｂで、パケットが、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信されたとき、ツリー識別子ＲＥＤが、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐから取得され、状態ビット値が０であることにより、マルチキャストレコード２２０中のプライマリツリー識別子とだけ比較される。この場合、マルチキャストレコード２２０のプライマリツリー識別子のすべてがＢＬＵＥの値を有しているので、一致が見出されることはなく、したがって、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信されたパケットは破棄される。
【００２８】
図２で示すように第２の状態２０１Ａで、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害を検出すると：（１）スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード２１０Ｓの状態ビットが０から１に切り換えられる、かつ（２）障害を起こしたプライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード２１０Ｐのツリー識別子の値が、ネットワーク出口ノード１２２５によるパケットの複製を阻止するために（すなわちネットワーク出口ノード１２２５が、両方のＰ２ＭＰ  ＬＳＰツリー１２５からのパケットを受け入れる状況を阻止するために）、無効の値に設定される。その結果、第２の状態２０１Ａで、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐは、ＩＮＶのツリー識別子と０に設定された状態ビットとを有し、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２に関連付けられたＭＰＬＳラベルレコード２１０Ｓは、ＲＥＤのツリー識別子と１に設定された状態ビットとを有し、さらにマルチキャストレコード２２０は、各エントリが、ＢＬＵＥに設定されたプライマリツリー識別子と、ＲＥＤに設定されたスタンバイツリー識別子を有するＮ個のエントリを含む（すなわち、既存のマルチキャストツリー切換えを行うには、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介してトラフィックを受け入れることが可能になる前に必要となるはずのマルチキャストレコード２２０の変更がまだ行われていない）。ネットワーク出口ノード１２２５の転送エンジンは、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード２１０Ｓの状態ビットが１に設定されたとき、マルチキャストレコード２２０のプライマリおよびスタンバイツリー識別子の両方と、パケットが介して受信されたＰ２ＭＰ  ＬＳＰツリー１２５のＭＰＬＳラベルレコード２１０から取得されたツリー識別子との突合わせを検討し、比較した値のいずれかが一致する場合、パケットが受け入れられて、転送されるように構成される。
【００２９】
第２の状態２０１Ａで、パケットが、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して受信されたとき、ツリー識別子ＩＮＶがプライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐから取得され、マルチキャストレコード２２０中のプライマリツリー識別子と比較される。マルチキャストレコード２２０におけるすべてのプライマリツリー識別子は、ＢＬＵＥの値を有しているので、一致を見出すことができず、したがって、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介して受信されたパケットは破棄されることになる。このことは、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１が障害状態にある場合は問題になる可能性はないが、これは、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１が回復する時間と、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を用いる状態に戻るために、切換え動作が行われる時間との間にパケットが複製されるのを阻止することが理解されよう。
【００３０】
第２の状態２０１Ａでは、パケットが、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信されたとき、ツリー識別子ＲＥＤが、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に関連付けられたＭＰＬＳラベルレコード２１０Ｐから取得され、また状態ビット値が１であることにより、マルチキャストレコード２２０におけるプライマリツリー識別子、およびマルチキャストレコード２２０におけるスタンバイツリー識別子の両方と比較される。この場合、マルチキャストレコード２２０中のすべてのプライマリツリー識別子はＢＬＵＥであるが（マルチキャストレコード２２０が再プログラムされていないため）、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信されたパケットはなお、転送エンジンにより受け入れられ、転送されるが、それは、マルチキャストレコード２２０におけるすべてのスタンバイツリー識別子がＲＥＤである（すなわち、マルチキャストレコード２２０のスタンバイツリー識別子に対して一致が見出される）からである。
【００３１】
このように、ＭＰＬＳラベルレコード２１０内に状態ビットを含めることにより、ネットワーク出口ノード１２２５の転送エンジンは、マルチキャストレコード２２０の再プログラミングが行われる前に、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害を検出したことに応じて、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２からのトラフィックの受入れを開始することが可能になる。
【００３２】
ツリーの障害に応じてＭＰＬＳラベルレコード２１０を再プログラミングする動作は決定性のもの（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）であり、かつオーダーＯ（１）であるので、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に障害が起きたときにプライマリＰ２ＭＰ  ＬＳＰツリー１２５１からスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２へと高速に切り換えることは、トラフィック損失がほとんどない、または全くない状態で達成できることが理解されよう。これは、スタンバイＰ２ＭＰ  ＬＳＰツリーで受信されたパケットが、ネットワーク出口ノードにより受け入れられて転送できる前に、マルチキャストレコードの全部でＮ個あるチャネルレコードを再プログラムすることが必要であるため、オーダーＯ（Ｎ）である既存のマルチキャストツリー切換えの実施に対して、実質的に改善されている。
【００３３】
マルチキャストツリー切換えを可能にするための転送エンジンのデータ構造の再プログラミングを含むマルチキャストツリー切換えを実施するネットワーク出口ノードの動作は、任意の適切な方法で実施することができる。マルチキャストツリー切換えを実施するネットワーク出口ノードの動作は、図３で示されたネットワーク出口ノードの例示的な実施形態を参照することにより、よく理解することができる。
【００３４】
図３は、ネットワーク出口ノードの一実施形態の高水準のブロック図を示している。例えば、図３のネットワーク出口ノード３００は、図１のルータ１２２５として使用することができ、それは、図１のＰ２ＭＰ  ＬＳＰツリー１２５に関するネットワーク出口ノードとして機能する。
【００３５】
図３で示すように、ネットワーク出口ノード３００は、本明細書で示され述べられるマルチキャストツリー切換え機能に従ってマルチキャストツリー切換えを行うように協動するいくつかのコンポーネントを含む。すなわち、ネットワーク出口ノード３００は、障害検出コンポーネント３１０、ＭＰＬＳコンポーネント３２０、マルチキャストコンポーネント３３０、ラインカードプログラミングコンポーネント３４０、および転送エンジンコンポーネント３５０を含む。図３で示されるように、転送エンジンコンポーネント３５０は：プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐ、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード３５１Ｓ、およびマルチキャストレコード３５２のそれぞれを維持する。
【００３６】
マルチキャストツリー切換え機能を提供するようにネットワーク出口ノード３００のコンポーネントを使用することに関する説明は、ステップ３６１−３６６（障害を起こしたプライマリＰ２ＭＰ  ＬＳＰツリー１２５１からスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２へ切り換えるためのもの）、およびステップ３７１−３７８（スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２から回復したプライマリＰ２ＭＰ  ＬＳＰツリー１２５１へと戻るためのもの）を参照することにより行われる。
【００３７】
本明細書で述べるように、ネットワーク出口ノード３００は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害が検出されたとき、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１からスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２へ切り換えるように構成される。これは、ステップ３６１−３６６に関して示され、述べられる。
【００３８】
ステップ３６１で、障害検出コンポーネント３１０は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害を検出する。プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害は、任意の適切な方法で検出することができる。
【００３９】
ステップ３６２で、障害検出コンポーネント３１０は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の検出された障害をＭＰＬＳコンポーネント３２０に通知する。
【００４０】
ステップ３６３で、ＭＰＬＳコンポーネント３２０は、２つのアクションを行う、すなわち、それは、（１）ラインカードプログラミングコンポーネント３４０にメッセージを送り、ラインカードプログラミングコンポーネント３４０に、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード３５１Ｓの状態ビットを変更する（例えば、状態ビットの値を０から１に変更する）ように命令し、かつラインカードプログラミングコンポーネント３４０に、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐのツリー識別子を変更する（例えば、ツリー識別子の値を無効値に変更する）ように命令する、かつ（２）マルチキャストコンポーネント３３０にメッセージを送り、マルチキャストコンポーネント３３０にプライマリＰ２ＭＰ  ＬＳＰツリー１２５１の検出された障害を知らせる。
【００４１】
ステップ３６４で、ラインカードプログラミングコンポーネント３４０は、転送エンジンコンポーネント３５０上で、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード３５１Ｓの状態ビットを変更し、かつ転送エンジンコンポーネント３５０上で、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐのツリー識別子を変更する。
【００４２】
ステップ３６５で（任意の適切な時間に行うことができる）、マルチキャストコンポーネント３３０は、２つのアクションを行う、すなわち、それは：（１）ラインカードプログラミングコンポーネント３４０に再プログラミングメッセージを送り、ラインカードプログラミングコンポーネント３４０に、マルチキャストレコード３５２におけるすべてのチャネルレコードに対して、プライマリツリー識別子およびスタンバイツリー識別子を切り換えることによりマルチキャストレコード３５２を変更するように命令し、それにより、すべてのチャネルレコードに対して、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のツリー識別子を、プライマリツリー識別子にし、かつすべてのチャネルレコードに対して、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のツリー識別子を、スタンバイツリー識別子にする、かつ（２）肯定応答メッセージ（ＡＣＫ）をＭＰＬＳコンポーネント３２０に送り、ラインカードプログラミングコンポーネント３４０により処理するための再プログラミングメッセージが待ち行列に入ったことを示す。
【００４３】
ステップ３６６で、ラインカードプログラミングコンポーネント３４０は、転送エンジンコンポーネント３５０のマルチキャストレコード３５２のツリー識別子の要求された再プログラミングを実施する。
【００４４】
このように、マルチキャストレコード３５２のすべてのツリー識別子をネットワーク出口ノードが再プログラミングする間に、Ｐ２ＭＰ  ＬＳＰツリー１２５のＭＰＬＳラベルレコード３５１の状態ビットによりマルチキャストの適正な経路指定が可能であるが、既存のマルチキャストツリー切換え解決策ではそれとは反対に、マルチキャストレコード３５２のツリー識別子の再プログラミングを、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の障害が起きた後、パケットをスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受け入れることが可能になる前に完了している必要があるはずである（それは、大幅なパケット損失が生じ、エンドユーザに顕著な影響を生ずる可能性がある）。
【００４５】
本明細書で述べるように、ネットワーク出口ノード３００はまた、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１が回復したことを検出したとき、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２から、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１に切り換えて戻るように構成される。これは、ステップ３７１−３７８に関して示され、かつ述べられる。
【００４６】
ステップ３７１で、ＭＰＬＳコンポーネント３２０は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１が回復したことを検出する。プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の回復は、任意の適切な方法で検出することができる。一実施形態では、例えば、障害が起きたプライマリＰ２ＭＰ  ＬＳＰツリー１２５１は、ＭＰＬＳ／ＲＳＶＰ−ＴＥプロトコル機構により回復される。一実施形態では、ネットワーク出口ノードは、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の使用へと戻る何らかのアクションをとる前に、所定長さの時間だけ待機することができる。
【００４７】
ステップ３７２で、ＭＰＬＳコンポーネント３２０は、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の検出された回復をマルチキャストコンポーネント３３０に知らせるために、マルチキャストコンポーネント３３０にメッセージを送る。
【００４８】
ステップ３７３で、マルチキャストコンポーネント３３０は、２つのアクションを行う、すなわち、それは：（１）ラインカードプログラミングコンポーネント３４０に再プログラミングメッセージを送り、ラインカードプログラミングコンポーネント３４０に、マルチキャストレコード３５２におけるすべてのチャネルレコードに対して、プライマリツリー識別子およびスタンバイツリー識別子を切り換えることにより、マルチキャストレコード３５２を変更するように命令し、それにより、すべてのチャネルレコードに対して、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のツリー識別子をプライマリツリー識別子に変え、かつすべてのチャネルレコードに対して、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のツリー識別子をスタンバイツリー識別子にする、かつ（２）肯定応答メッセージ（ＡＣＫ）をＭＰＬＳコンポーネント３２０に送り、ラインカードプログラミングコンポーネント３４０により処理するための再プログラミングメッセージが待ち行列に入ったことを示す。
【００４９】
ステップ３７４で、ラインカードプログラミングコンポーネント３４０は、転送エンジンコンポーネント３５０のマルチキャストレコード３５２のツリー識別子の要求された再プログラミングを実施する。
【００５０】
ステップ３７５で、転送エンジンコンポーネント３５０のマルチキャストレコード３５２のツリー識別子の要求された再プログラミングの完了に続いて、ラインカードプログラミングコンポーネント３４０は、肯定応答メッセージをマルチキャストコンポーネント３３０に送り、転送エンジンコンポーネント３５０のマルチキャストレコード３５２の再プログラミングが完了したことを示す。代替の実施形態では、ラインカードプログラミングコンポーネント３４０は、ＭＰＬＳコンポーネント３２０に肯定応答メッセージを直接送ることもできる。
【００５１】
ステップ３７６で、マルチキャストコンポーネント３３０は、肯定応答メッセージをＭＰＬＳコンポーネント３２０に送り、転送エンジンコンポーネント３５０のマルチキャストレコード３５２の再プログラミングが完了したことを示す。
【００５２】
ステップ３７７で、ＭＰＬＳコンポーネント３２０は、プログラミングメッセージをラインカードプログラミングコンポーネント３４０に送り、ラインカードプログラミングコンポーネント３４０に、（１）プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐのツリー識別子を（例えば、無効値から、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１の正しいツリー識別子に）訂正するように、かつ（２）スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード３５１Ｓの状態ビットをリセットする（例えば、状態ビットの値を１から変更して０に戻す）ように命令する。
【００５３】
ステップ３７８で、ラインカードプログラミングコンポーネント３４０は、転送エンジンコンポーネント３５０上でプライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐのツリー識別子を変更し、かつ転送エンジンコンポーネント３５０上でスタンバイＰ２ＭＰ  ＬＳＰツリー１２５２のＭＰＬＳラベルレコード３５１Ｓの状態ビットを変更する。
【００５４】
このように、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介してトラフィックを受信することから、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１を介してトラフィックを受信することへと円滑に、損失なく復帰することが達成されうる。プライマリＰ２ＭＰ  ＬＳＰツリー１２５１への復帰中に、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２がアクティブである場合、マルチキャストレコード３５２の再プログラミングが行われている間に、トラフィックを、スタンバイＰ２ＭＰ  ＬＳＰツリー１２５２を介して受信できるので、プライマリＰ２ＭＰ  ＬＳＰツリー１２５１のＭＰＬＳラベルレコード３５１Ｐの状態ビットを０から１に変更する必要のないことが理解されよう。
【００５５】
別々のコンポーネントとして示され、述べられているが、ネットワーク出口ノード３００の様々なコンポーネントを、任意の適切な方法で（例えば、別々の物理的なコンポーネント、１つまたは複数の物理的なコンポーネントの１つまたは複数の論理部分などとして、ならびにその様々な組合せで）実施できることが理解されよう。
【００５６】
図４は、ネットワーク出口ノードを、プライマリマルチキャストツリーからスタンバイマルチキャストツリーに切り換えるように構成するための方法の一実施形態を示す。
【００５７】
ステップ４０２で、方法４００が開始する。
【００５８】
ステップ４０４で、プライマリマルチキャストツリーの障害が検出される。
【００５９】
ステップ４０６で、スタンバイマルチキャストツリーのＭＰＬＳラベルレコードが変更される。すなわち、ＭＰＬＳラベルレコードの状態ビットが、第１の値（パケットを受け入れる／転送するか、それともパケットを破棄するかを判定する場合に、スタンバイマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子が、ネットワーク出口ノードのマルチキャストレコードのプライマリツリー識別子とだけ比較すべきであることをネットワーク出口ノードに示す値）から、第２の値（パケットを受け入れる／転送するか、それともパケットを破棄するかを判定する場合に、スタンバイマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子を、ネットワーク出口ノードのマルチキャストレコードのプライマリツリー識別子およびスタンバイツリー識別子の両方と比較できることをネットワーク出口ノードに示す値）に変更される。
【００６０】
ステップ４０８で、プライマリマルチキャストツリーのＭＰＬＳラベルレコードが変更される。すなわち、ＭＰＬＳラベルレコードのツリー識別子は、第１の値（プライマリマルチキャストツリーのツリー識別子）から第２の値（無効値）に変更される。
【００６１】
ステップ４１０で、方法４００は終了する。終了と示され、述べられているが（この方法を実行することは、スタンバイマルチキャストツリーを介してトラフィックを受信できるようにするには十分であるため）、さらなるステップ（例えば、マルチキャストレコードのプライマリおよびスタンバイツリー識別子の再プログラミング）をネットワーク出口ノードで実施できることが理解されよう。
【００６２】
図５は、プライマリマルチキャストツリーに障害が起きた後に、スタンバイマルチキャストツリーからパケットを受け入れる方法の一実施形態を示す。方法５００は、プライマリマルチキャストツリー、またはスタンバイマルチキャストツリーで受信されるパケットに関して実行することができる。
【００６３】
ステップ５０２で、方法５００が開始する。
【００６４】
ステップ５０４で、パケットは、マルチキャストツリーを介して受け取られる。
【００６５】
ステップ５０６で、マルチキャストツリーに関連付けられたＭＰＬＳラベルレコードが識別される。例えば、ＭＰＬＳラベルレコードは、パケットのＭＰＬＳヘッダ中のＭＰＬＳラベルを用いて識別することができる。
【００６６】
ステップ５０８で、ツリー識別子が、ＭＰＬＳラベルレコードから求められる。
【００６７】
ステップ５１０で、状態ビットが、ＭＰＬＳラベルレコードから求められる。
【００６８】
ステップ５１２で、ＭＰＬＳラベルレコードの状態ビットがゼロ（０）であるか、それとも１であるかに関して判定が行われる。状態ビットがゼロである場合、方法５００はステップ５１４０に進む。状態ビットが１である場合、方法５００はステップ５１４１に進む。
【００６９】
ステップ５１４０で、第１のパケット処理ルールが、受信したパケットの処理を決めるために適用される。すなわち、パケットを受け入れるか、それとも破棄するかを判定するために、ＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子とだけ比較される。
【００７０】
ステップ５１４１で、第２のパケット処理ルールが、受信したパケットの処理を決めるために適用される。すなわち、パケットを受け入れるか、それとも破棄するかを判定するために、ＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子およびスタンバイツリー識別子の両方と比較することができる。
【００７１】
ステップ５１６で、パケットは、その比較に基づいて処理される、すなわち、パケットは、（一致が見出された場合）転送のために受け入れられる、または（一致が見出されない場合）破棄される。
【００７２】
ステップ５１８で、方法５００は終了する。
【００７３】
ＭＰＬＳラベルレコードの状態ビットのデフォルト値が「０」であり、またプライマリＰ２ＭＰ  ＬＳＰツリーの障害を検出すると、スタンバイＰ２ＭＰ  ＬＳＰツリーのＭＰＬＳラベルレコードの状態ビットが「１」に設定される実施形態に関して本明細書で示され、述べられているが、他の実施形態では、ＭＰＬＳラベルレコードの状態ビットのデフォルト値が「１」であり、またプライマリＰ２ＭＰ  ＬＳＰツリーの障害が検出されると、スタンバイＰ２ＭＰ  ＬＳＰツリーのＭＰＬＳラベルレコードの状態ビットが「０」に設定されることが理解されよう。
【００７４】
主として、マルチキャストツリー切換え機能が、状態ビットと呼ばれる１ビット値を有するパラメータを用いて行われる実施形態に関して本明細書で示され、かつ述べられているが、任意の適切なパラメータ、またはパラメータの組合せを、マルチキャストツリー切換え機能を行うために使用できることが理解されよう（例えば、異なるパラメータ名を有する単一ビット値を用いること、マルチビット値を用いること、他の任意の適切な値を用いること、および同様のもの、ならびにそれらの様々な組合せなど）。言い換えると、任意の適切なパラメータ、および関連するパラメータ値を、本明細書で示され、述べられた状態ビットにより可能な様々な機能を提供するために使用することができる。
【００７５】
主として、マルチキャストツリー切換え機能が、Ｐ２ＭＰ  ＬＳＰツリー間で切り換えるために使用される実施形態に関して本明細書で示され、述べられているが、マルチキャストツリー切換え機能は、マルチキャストツリーの様々な他のタイプの間で切り換えるために使用することができる。
【００７６】
主として、マルチキャストツリー切換え機能が、ＭＰＬＳネットワークにおけるマルチキャストツリーの間で切り換えるために使用される実施形態に関して本明細書で示され、述べられているが、マルチキャストツリー切換え機能は、他のタイプのマルチキャストネットワークのマルチキャストツリー間で切り換えるために使用することもできる。
【００７７】
図６は、本明細書で述べる機能を実施するために使用するのに適したコンピュータの高水準ブロック図を示す。
【００７８】
図６で示すように、コンピュータ６００は、プロセッサ要素６０２（例えば、ＣＰＵ（中央処理装置）および／または他の適切なプロセッサ）、メモリ６０４（例えば、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読出し専用メモリ）など）、協動するモジュール／処理６０５、および様々な入力／出力装置６０６（例えば、ユーザ入力装置（キーボード、キーパッド、マウスなど）、ユーザ出力装置（ディスプレイ、スピーカなど）、入力ポート、出力ポート、受信器、送信器、および記憶装置（例えば、テープドライブ、フロッピー（登録商標）ドライブ、ハードディスクドライブ、コンパクトディスクドライブなど））を含む。
【００７９】
本明細書で示され、述べられた機能は、ソフトウェアおよび／またはハードウェアで、例えば、汎用コンピュータ、１つまたは複数のＡＳＩＣ（特定用途向けＩＣ）、および／または任意の他のハードウェアの等価物を用いて実施できることが理解されよう。一実施形態では、協動する処理６０５は、本明細書で論ずる機能を実施するために、メモリ６０４にロードされ、プロセッサ６０２により実行することができる。したがって、協動する処理６０５（関連するデータ構造を含む）は、例えば、ＲＡＭメモリ、磁気または光ドライブもしくはディスケット、および同様のものなど、コンピュータ可読記憶媒体に記憶することができる。
【００８０】
本明細書でソフトウェアの方法として論じられたステップのいくつかは、例えば、様々な方法ステップを行うためにプロセッサと協動する回路としてなど、ハードウェア内で実施できることが企図される。本明細書で述べた機能／要素のいくつかの部分は、コンピュータプログラム製品として実施することができ、その場合、コンピュータ命令は、コンピュータにより処理されたとき、本明細書で述べた方法および／または技法が呼び出される、またはその他の形で提供されるように、コンピュータの動作を適合させる。本発明の方法を呼び出すための命令は、固定された、または取外し可能な媒体に記憶する、同報通信または他の信号搬送媒体におけるデータストリームにより送信する、かつ／または命令に従って動作するコンピューティング装置内のメモリに記憶することができる。
【００８１】
様々な実施形態の諸態様は、特許請求の範囲で指定される。様々な実施形態のこれらの、および他の態様は、以下の番号を付した節で具体的に述べる：
１．ノードで、第１のマルチキャストツリーから第２のマルチキャストツリーに切り換えることを可能にする方法であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、方法が、
第１のマルチキャストツリーの障害が検出されたとき、第２のＭＰＬＳラベルレコードのパラメータを第１の値から第２の値に切り換えるステップであり、第１の値および第２の値が、第２のマルチキャストツリーを介してノードで受信したパケットを受け入れるか、それとも破棄するかを判定するために適用される第１および第２の処理ルールをそれぞれ示している、方法。
【００８２】
２．第１の処理ルールが、
パケットが、第２のマルチキャストツリーを介して受信されたとき、パケットを受け入れるか、それとも破棄するかを判定するために、第２のＭＰＬＳラベルレコードからの第２のツリー識別子を、マルチキャストレコードのプライマリツリー識別子とだけ比較するステップを含む、節１の方法。
【００８３】
３．第２の処理ルールが、
パケットが、第２のマルチキャストツリーを介して受信されたとき、パケットを受け入れるか、それとも破棄するかを判定するために、第２のＭＰＬＳラベルレコードからの第２のツリー識別子を、マルチキャストレコードのプライマリツリー識別子、またはスタンバイツリー識別子と比較するステップを含む、節１の方法。
【００８４】
４．第１の値が、パケットを第２のマルチキャストツリーを介して受信すると、パケットは、第２のＭＰＬＳラベルレコードの第２のツリー識別子が、マルチキャストレコードのプライマリツリー識別子のうちの１つと一致する場合に限って受け入れられることを示している、節１の方法。
【００８５】
５．第２の値が、パケットを第２のマルチキャストツリーを介して受信すると、パケットは、第２のＭＰＬＳラベルレコードの第２のツリー識別子が、マルチキャストレコードのプライマリツリー識別子の１つ、またはスタンバイツリー識別子の１つと一致する場合に受け入れられることを示している、節１の方法。
【００８６】
６．第２のマルチキャストツリーを介してパケットを受信するステップと、
第２のＭＰＬＳラベルレコードから第２のマルチキャストツリーの第２のツリー識別子を求めるステップと、
第２のＭＰＬＳラベルレコードからパラメータの値を求めるステップと、
第２のＭＰＬＳラベルレコードからのパラメータの値に基づいて第１または第２の処理ルールを適用するステップと
をさらに含む、節１の方法。
【００８７】
７．第１のＭＰＬＳラベルレコードのツリー識別子を第１のツリー識別子から無効値に変更するステップをさらに含む、節１の方法。
【００８８】
８．第１のマルチキャストツリーが回復したとき、
第１のマルチキャストツリーを介してパケットを受信するステップと、
受信したパケットを受け入れるか、それとも破棄するかを判定するステップと
をさらに含み、
第１のマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子の無効値が、マルチキャストレコードのプライマリツリー識別子のいずれとも一致するのに失敗した場合、パケットは破棄される、節７の方法。
【００８９】
９．第１のマルチキャストツリーを介してパケットを受信するステップと、
第１のＭＰＬＳラベルレコードから第１のマルチキャストツリーの第１のツリー識別子を求めるステップと、
第１のＭＰＬＳラベルレコードからパラメータの値を求めるステップと、
パケット処理ルールの結果に基づき受信したパケットを破棄するステップであり、適用されるパケット処理ルールは、第１のＭＰＬＳラベルレコードからのパラメータの値に基づいて選択される、ステップと
をさらに含む、節１の方法。
【００９０】
１０．プライマリツリー識別子のそれぞれを、第２のマルチキャストツリーの第２のツリー識別子を指し示すように切り換えることにより、かつスタンバイツリー識別子のそれぞれを、第１のマルチキャストツリーの第１のツリー識別子を指し示すように切り換えることにより、マルチキャストレコードを変更するステップをさらに含む、節１の方法。
【００９１】
１１．第１のマルチキャストツリーの回復が検出されたとき、
プライマリツリー識別子のそれぞれを、第１のマルチキャストツリーの第１のツリー識別子を指し示すように切り換えることにより、かつスタンバイツリー識別子のそれぞれを、第２のマルチキャストツリーの第２のツリー識別子を指し示すように切り換えることにより、マルチキャストレコードを変更するステップと、
第２のＭＰＬＳラベルレコードのパラメータを、第２の値から第１の値に切り換えるステップと
をさらに含む、節１０の方法。
【００９２】
１２．第１のおよび第２のマルチキャストツリーが、ポイントツーマルチポイント（Ｐ２ＭＰ）ラベルスイッチトパス（ＬＳＰ）ツリーである、節１の方法。
【００９３】
１３．ノードで、第１のマルチキャストツリーから第２のマルチキャストツリーに切り換えることを可能にする装置であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、装置が、
第１のマルチキャストツリーの障害が検出されたとき、第２のＭＰＬＳラベルレコードのパラメータを第１の値から第２の値に切り換えるように構成されたプロセッサであり、第１の値および第２の値が、第２のマルチキャストツリーを介してノードで受信したパケットを受け入れるか、それとも破棄するかを判定するために適用される第１および第２の処理ルールをそれぞれ示している、プロセッサ
を備える、装置。
【００９４】
１４．第１のマルチキャストツリーおよび第２のマルチキャストツリーをサポートするノードでパケットを受信するための方法であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、方法が、
マルチキャストツリーの一つを介してパケットを受信するステップと、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのパラメータの値を求めるステップと、
パラメータの値に基づいて、パケットに適用すべきパケット処理ルールを決定するステップと
を含む、方法。
【００９５】
１５．パラメータの値が第１の値であるとき、パケットを受け入れるか、それとも破棄するかを判定するために第１のパケット処理ルールを適用するステップと、
パラメータの値が第２の値であるとき、パケットを受け入れるか、それとも破棄するかを判定するための第２のパケット処理ルールを適用するステップと
をさらに含む、節１４の方法。
【００９６】
１６．パラメータの値が第１の値であるとき、パケット処理ルールが、パケットを受け入れるか、それとも破棄するかを判定するために、（ａ）パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子を、（ｂ）マルチキャストレコードのプライマリツリー識別子とだけ比較するステップを含む、節１４の方法。
【００９７】
１７．パケットを受け入れるか、それとも破棄するかを判定するために、パケット処理ルールを適用するステップをさらに含み、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子のうちの１つと一致したとき、パケットを受け入れ、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子と一致しないとき、パケットを破棄する、節１６の方法。
【００９８】
１８．パラメータの値が第２の値であるとき、パケットを受け入れるか、それとも破棄するかを判定するために、パケット処理ルールが、（ａ）パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子を、（ｂ）マルチキャストレコードのプライマリツリー識別子またはスタンバイツリー識別子と比較するステップを含む、節１４の方法。
【００９９】
１９．パケットを受け入れるか、それとも破棄するかを判定するために、パケット処理ルールを適用するステップをさらに含み、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子の１つと一致したとき、またはマルチキャストレコードのスタンバイツリー識別子の１つと一致したとき、パケットを受け入れ、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのツリー識別子が、マルチキャストレコードのプライマリツリー識別子またはスタンバイツリー識別子と一致しないとき、パケットを破棄する、節１８の方法。
【０１００】
２０．第１のマルチキャストツリーおよび第２のマルチキャストツリーをサポートするノードで、パケットを受信するための装置であって、ノードが、第１のマルチキャストツリーの第１のツリー識別子を含む第１のＭＰＬＳラベルレコード、第２のマルチキャストツリーの第２のツリー識別子を含む第２のＭＰＬＳラベルレコード、ならびに複数のプライマリツリー識別子および複数のスタンバイツリー識別子を含むマルチキャストレコードを含み、装置が
マルチキャストツリーの一つを介してパケットを受信し、
パケットが介して受信されたマルチキャストツリーのＭＰＬＳラベルレコードのパラメータの値を求め、
パラメータの値に基づいて、パケットに適用すべきパケット処理ルールを決定する
ように構成されたプロセッサ
を備える、装置。
【０１０１】
本発明の教示を組み込む様々な実施形態が、本明細書で詳細に示され、かつ述べられてきたが、当業者であれば、これらの教示をなお組み込む多くの他の様々な実施形態を容易に考案することができる。
【図１】
2013535911.tif 000003
【図２】
2013535911.tif 000004
【図３】
2013535911.tif 000005
【図４】
2013535911.tif 000006
【図５】
2013535911.tif 000007
【図６】
2013535911.tif 000008
【国際調査報告】
2013535911.tif 000009
2013535911.tif 000010
2013535911.tif 000011