(57)【特許請求の範囲】
【請求項１】
通信ネットワーク内でマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定するための方法であって、
サービスインスタンスの第１のサブセットをサポートするネットワーク内の複数のノードの各々において、サービスインスタンスの第１のサブセットに関連する共通に合意済みのメカニズムに従って、指定ノード（ＤＮ）を確定するステップを含み、前記共通に合意済みのメカニズムは、サービスインスタンスの前記第１のサブセットをサポートするネットワーク内の前記複数のノード内から単一の指定ノード（ＤＮ）を確定するように構成され、更に前記方法は、
複数のノードの各々において、ＤＮと複数のノードの各々との間の最短経路を確定するステップ、および
複数のノードの各々において、それぞれのノードを横断するＤＮからのそれらの確定された最短経路のみを、マルチキャストのためのそれぞれの転送ツリー内に含めるように選択するステップ
を含む、方法。
【請求項２】
マルチキャストのためのそれぞれの転送ツリーが＊，Ｇツリーである、請求項１に記載の方法。
【請求項３】
選択するステップが、ＤＮと複数のノードの各々との間の最短経路を含む転送ツリーをプルーニングするステップを含む、請求項１に記載の方法。
【請求項４】
共通に合意済みのメカニズムが、システム識別フィールドおよびブリッジ優先フィールドのうちのいずれかを含む、請求項１に記載の方法。
【請求項５】
共通に合意済みのメカニズムが、最短経路ブリッジングプロトコルに関連するタイプ長さ値（ＴＬＶ）を含む、請求項１に記載の方法。
【請求項６】
通信ネットワークが、追加のサービスインスタンスサブセットをサポートし、方法が、対応するそのそれぞれの複数のサポートノードを使用して、追加のサービスインスタンスサブセットの各々について繰り返される、請求項１に記載の方法。
【請求項７】
各サービスインスタンスサブセットが、それぞれの共通に合意済みのメカニズムを使用する、請求項６に記載の方法。
【請求項８】
プロバイダバックボーン（ＰＢＢ）マルチキャストが、組織的一意識別子（ＯＵＩ）を含む第１のフィールド、およびＰＢＢサービス識別子Ｉ−ＳＩＤを含む第２のフィールドを備える構造を使用してエンコードされる、請求項６に記載の方法。
【請求項９】
コンピュータによって実行されると、通信ネットワーク内のマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定するための方法をコンピュータに実施させるソフトウェアプログラムを記憶したコンピュータ可読記憶媒体であって、方法が、
サービスインスタンスの第１のサブセットをサポートするネットワーク内の複数のノードの各々において、サービスインスタンスの第１のサブセットに関連する共通に合意済みのメカニズムに従って、指定ノード（ＤＮ）を確定するステップを含み、前記共通に合意済みのメカニズムは、サービスインスタンスの前記第１のサブセットをサポートするネットワーク内の前記複数のノード内から単一の指定ノード（ＤＮ）を確定するように構成され、更に前記方法が、
複数のノードの各々において、ＤＮと複数のノードの各々との間の最短経路を確定するステップ、および
複数のノードの各々において、それぞれのノードを横断するＤＮからのそれらの確定された最短経路のみを、マルチキャストのためのそれぞれの転送ツリー内に含めるように選択するステップ
を含む、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トランスポートネットワークの分野に関し、より詳細には、それに限定するものではないが、トランスポートネットワークにおけるマルチキャストトラフィックの最短経路ブリッジングを実現することに関する。
【背景技術】
【０００２】
最短経路ブリッジング（ＳＰＢ）は、ユニキャストトラフィックおよびマルチキャストトラフィックの最短経路ベースの転送を使用することによって、イーサネット（登録商標）方式のネットワークにおける従来の非効率性を克服するための方法を規定した新たな規格である。マルチキャストについては、ＳＰＢには、送信元ノードごとに及び等コストツリーアルゴリズムごとにマルチキャストツリーを構築することが必要な送信元／グループツリーと称されるメカニズムが規定されている。これには２つの主な問題がある：すなわち、計算資源の消費と、マルチキャストアドレスまたは最短経路仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子などの他のデータ資源の消費である。具体的には、各ノードで消費される計算資源は、ネットワークにおけるノードの数に対応する。さらには、各ノードで消費されるマルチキャスト転送またはフィルタのエントリは、それぞれのノードがトラフィックをそれに向けて送信または通過させなくてはならないネットワークにおけるノードの数に比例する。
【０００３】
「Ｌｏｃａｌ  ａｎｄ  Ｍｅｔｒｏｐｏｌｉｔａｎ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ−Ｖｉｒｔｕａｌ  Ｂｒｉｄｇｅｄ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ−Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｂｒｉｄｇｉｎｇ」という名称のＩＥＥＥ規格草案Ｐ８０２．１ａｑは、習得済みの局情報を共有することができる複数のアクティブトポロジーを計算するプロトコルを含めた、ユニキャストフレームおよびマルチキャストフレームの最短経路ブリッジングおよびトポロジーごとの複数のＶＬＡＮ識別子（ＶＩＤ）によるＶＬＡＮのサポートを規定している。ＩＥＥＥ規格草案Ｐ８０２．１ａｑは、引用によりその全体が本明細書に組み込まれている。
【０００４】
各サービスインスタンス（Ｉ−ＳＩＤ）に対して送信元固有のツリーのオーバーヘッドを抑えるのに知られているいくつかの技法がある。１つの技法によれば、ヘッドエンドレプリケーションがユニキャスト経路とともに使用される。この技法は、ネットワーク全体にわたって帯域幅を浪費するため残念である。別の技法によれば、グルーピングがサービス固有のアドレスの数の抑えるために使用される。この技法は、非効率的であり、多数のツリーを使用するため残念である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】ＩＥＥＥ規格草案Ｐ８０２．１ａｑ
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術における様々な不備点は、計算資源の消費および各ノードにおいて消費されるマルチキャスト転送またはフィルタのエントリ数を最小限に抑える様態で、通信ネットワーク内でマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定するための方法、システムおよび装置によって対処される。
【課題を解決するための手段】
【０００７】
通信ネットワーク内でマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定するための方法の１つの実施形態は、ネットワーク内の複数のノードの各々において、共通に合意済みのメカニズムに従って、指定ノード（ＤＮ）を確定するステップ、複数のノードの各々において、ＤＮと複数のノードの各々との間の最短経路を確定するステップ、および複数のノードの各々において、それぞれのノードを横断するＤＮからのそれらの確定された最短経路のみを、マルチキャストのためのそれぞれの転送ツリー内に含めるように選択するステップを含む。
【０００８】
本発明の教示は、添付の図面と合わせて以下の詳細な説明を考慮することによって容易に理解することができる。
【図面の簡単な説明】
【０００９】
【図１】通信ネットワークを示す高レベルのブロック図である。
【図２】１つの実施形態による方法の流れ図である。
【図３】図１の通信ネットワークを示す高レベルのブロック図であり、ここでは、指定ノードにより計算される＊，Ｇツリーが示されている。
【図４】本明細書に説明される機能を実行する際に使用するのに適している汎用コンピュータの高レベルのブロック図である。
【発明を実施するための形態】
【００１０】
理解し易くするために、図に共通する同一の要素を指定するために、可能であれば、同一の参照符号が使用されている。
【００１１】
本発明の様々な実施形態は、計算資源の消費、および各ノードにおいて消費されるマルチキャスト転送およびフィルタのエントリ数を最小限に抑える様態で、通信ネットワーク内でユニキャストフレームおよびマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定することを対象とする。
【００１２】
様々な実施形態では、複数の異なる経路は、ユニキャストおよびマルチキャストのトラフィックをサポートすることが許容される。様々な実施形態では、重み付けに関する様々なコスト要因は、ユニキャスト経路もしくはマルチキャスト経路、または経路要素に関連付けられる。様々な実施形態では、（「スターカンマグループツリー」すなわち「＊，Ｇツリー」とも称される１つまたは複数のツリーは、マルチキャスト経路を定めるために通信ノード（ＣＮ）ごとに１回計算され、ただし、＊，Ｇツリーは、ノード全体、ノード全体の一部分、およびサービスインスタンスのサブセットなどの中でそれぞれのノードの各々が、指定ノード（複数可）の共通の確定へと収束することになるように、共通に合意済みのメカニズムに従って計算される。
【００１３】
ユニキャストフレームおよびマルチキャストフレームのＳＰＢの確定は、主として、イーサネット方式のトランスポートネットワーク内でユニキャストトラフィックおよびマルチキャストトラフィックを伝搬する環境の範囲内で示され説明されるが、本明細書に示され説明されるトラフィック伝搬性能は、他のタイプのネットワークにおけるユニキャストトラフィックおよびマルチキャストトラフィックのトランスポートを実現するために使用され得ることが当業者には認識されるであろうし、また本明細書における教示によって知らされるであろう。
【００１４】
図１は、通信ネットワークの高レベルのブロック図を示している。図１に示すように、通信ネットワーク１００は、通信ネットワーク（ＣＮ）１１０、および管理システム（ＭＳ）１２０を含む。ＣＮ１１０は、複数の通信ノード（ＣＮ）１１２Ａ−１１２Ｊ（まとめて、ＣＮ１１２）を含むネットワークである。ＣＮ１１２は、複数の通信経路（ＣＰ）１１４を使用して通信する。通信ネットワーク１１０が、より多くのまたはより少ない通信ノード１１２を含んでもよいことは当業者には認識されよう。
【００１５】
ＣＮ１１０のＣＮ１１２は、トランスポートノードである。１つの実施形態では、ここでは、ＣＮ１１０は、イーサネット方式のトランスポートネットワークであるが、ＣＮ１１２は、イーサネットトランスポートノードである。この実施形態では、ＣＮ１１２各々は、転送およびブリッジング性能、ならびにイーサネット方式のトランスポートノードによってサポート可能な任意の他の性能など、イーサネット性能をサポートする。ＣＮ１１２は、他のトランスポート技術に関連するノードであってもよい。
【００１６】
ＣＮ１１０のＣＰ１１４は、ＣＮ１１２間の直接接続および／または他のノード（図示せず）を横断し得る接続など、ＣＮ１１２間の間接接続を含み得る通信経路である。ＣＰ１１４は、ＣＮ１１２のトラフィックをサポートするようになされている任意のタイプの通信経路とすることができる。ＣＰ１１４は、トラフィックの伝搬をサポートするのに適している任意の基礎技術を使用してトラフィックの伝搬をサポートすることができる。
【００１７】
特定のタイプ、数、およびトポロジーの通信ノードおよび通信経路（例示として、ＣＮ１１０のＣＮ１１２およびＣＰ１１４）に関して本明細書には示され説明されているが、本明細書に示され説明されている耐障害性のトラフィック伝搬性能は、他のタイプ、数、およびトポロジーの通信ノードおよび通信経路を有するトランスポートネットワークにおいて用いてもよいことが当業者には認識されるであろうし、また本明細書における教示によって知らされるであろう。
【００１８】
ＭＳ１２０は、ＣＮ１１０の管理機能を提供する管理システムである。ＭＳ１２０によって提供され得る管理機能は、本明細書において詳細に後述される。ＭＳ１２０は、通信経路（ＣＰ）１２１を介してＣＮ１１０と通信する。ＭＳ１２０は、ＣＮ１１０のＣＰ１２１およびＣＰ１１４を介して、ＣＮ１１０のＣＮ１１２の各々と通信する。ＭＳ１２０は、任意の他の適切な様態でＣＮ１１２と通信することが可能である。
【００１９】
図１を参照すると、通信ノード１１２Ａ（Ａ）は、通信ノードＢ、Ｄ、Ｆ、ＧおよびＨに結合され、通信ノード１１２Ｂは、通信ノードＡ、Ｃ、Ｆ、ＧおよびＨに結合され、通信ノード１１２Ｃは、通信ノードＢ、Ｄ、Ｅ、ＩおよびＪに結合され、通信ノード１１２Ｄは、通信ノードＡ、Ｃ、Ｅ、ＩおよびＪに結合され、通信ノード１１２Ｅは、通信ノードＣおよびＤに結合され、通信ノード１１２Ｆは、通信ノードＡおよびＢに結合され、通信ノード１１２Ｇは、通信ノードＡおよびＢに結合され、通信ノード１１２Ｈは、通信ノードＡおよびＢに結合され、通信ノード１１２Ｉは、通信ノードＣおよびＤに結合され、通信ノード１１２Ｊは、通信ノードＣおよびＤに結合されている。
【００２０】
本発明の様々な実施形態は、合意済みのアルゴリズムまたはメカニズムに基づいて計算される（スター，グループツリー）（または＊，Ｇツリー）とも称される単一のツリーを用いる。イーサネットネットワークで＊，Ｇツリーを使用するのと異なり（この場合、ユニキャストトラフィックとマルチキャストトラフィックの両方が、同じツリーを使用しなくてはならない）、様々な実施形態は、ユニキャストトラフィックおよびマルチキャストトラフィックについて、各々についての転送を維持しながら、別々のツリーを企図する。
【００２１】
概して言えば、様々な実施形態の環境の範囲内で、１つのノードが、指定ノードであるように選択され、＊，Ｇツリーの指定ノードになる。これにより、マルチキャスト転送経路について、マルチキャストツリーごとの単一の計算へと計算が縮小される。ネットワーク内のあらゆるノードは、同じデータベースまたは他の基準に基づいて同じ計算を行う。ネットワーク内のあらゆるノードは、指定ノードを選択し、集中したトポロジーで、ノードのすべては、指定ノードと同じノードを選択する。この利点は、２要素ある：すなわち、マルチキャストエントリの数は、サービスインスタンスごとに１に抑えられ、単一のマルチキャスト計算は、ネットワーク内の指定ノードごとにしか実行されない。
【００２２】
様々な実施形態の環境の範囲内で、結果的に生じたマルチキャストトラフィックは、必ずしも、ユニキャストトラフィックと一致する（すなわち、それと同じ経路をとる）とは限らないことが分かる。一致しないことの１つの帰結として、接続性チェックおよび経路トレースなどの運用管理保守機能（ＯＡＭ）は、ユニキャスト経路についてはユニキャスト転送機構を使用するように修正される。同様に、マルチキャスト経路についてのＯＡＭは、マルチキャスト転送機構を使用する。別の帰結として、フレーム送信元が有効であるかどうかをチェックするイングレスチェック時などに、ユニキャストトラフィックについての転送ルールが、ユニキャスト転送経路に対して行われ、一方、マルチキャストトラフィックについての転送ルールは、マルチキャスト経路に対して行われる。
【００２３】
様々な実施形態は、例えば組織的一意識別子（ＯＵＩ）を含む第１のフィールドと、２４ビットのＰＢＢサービス識別子Ｉ−ＳＩＤを含む第２のフィールドとを備えるデータ構造を使用することによって、ＰＢＢマルチキャストの現在のエンコーディングを可能にする。１つの実施形態では、データ構造は、最大２０ビットの予約済みＩＥＥＥ８０２．１Ｑバックボーンサービスインスタンスグループのアドレスの組織的一意識別子（ＯＵＩ）を含む第１のフィールドと、２４ビットのＰＢＢサービス識別子（Ｉ−ＳＩＤ）を含む第２のフィールドとを備える４８ビットデータ構造を備える。このデータ構造は、一意送信元識別子に２４ビットＩ−ＳＩＤを加えて使用する送信元固有のマルチキャストデータ構造よりもより効率的であることが本発明者らによって見出された。
【００２４】
図２は、１つの実施形態による方法の流れ図を示している。具体的には、図２の方法２００は、計算資源の消費、および各ノードにおいて消費されるマルチキャスト転送またはフィルタのエントリ数を最小限に抑える様態で、通信ネットワーク内でユニキャストフレームおよびマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を確定するようになされている。
【００２５】
ステップ２１０で、各ノードは、それ自体と、通信ネットワーク内の対象の複数の他のノードの各々またはその関連部分との間の最短経路を確定する。確定された最短経路は、典型的には、ユニキャスト経路である。ボックス２１５を参照すると、この確定に使用される複数の他のノードは、通信ネットワーク内の他のノードのすべて、他のノードのサブセット、特定のタイプの他のノード、特定のオーナーに関連付けられるノード、特定のサービスに関連付けられるノード、特定のサービスプロバイダに関連付けられるノード、および特定のサービスインスタンスまたはサービスインスタンスのサブセットに関連付けられるノードなどを含み得る。
【００２６】
ステップ２２０で、各ノードは、（必要に応じて）指定ノードを確定するための共通に合意済みのメカニズムを識別する。様々な実施形態では、共通に合意済みのメカニズムは、決して変わらない。他の実施形態では、共通に合意済みのメカニズムは、例えばネットワーク管理システムを介して変わることもある。具体的には、共通に合意済みのメカニズムは、後述するように、どのノードが、指定ノード（ＤＮ）、バックアップＤＮ、およびバックアップＤＮシーケンスなどとして働くべきかを確定するためのメカニズムである。
【００２７】
共通に合意済みのメカニズムは、ノード全体、ノード全体の一部分、ノードのサブセット、特定のタイプの他のノード、特定のオーナーに関連付けられるノード、特定のサービスに関連付けられるノード、特定のサービスプロバイダに関連付けられるノード、および特定のサービスインスタンスまたはサービスインスタンスのサブセットに関連付けられるノードなどの中で各それぞれのノードが、指定ノードをそれぞれ共通して確定することへと収束することを可能にする任意のメカニズムを含み得る。
【００２８】
さらには、様々な実施形態は、各ノードが、潜在的な指定ノードの共通のシーケンスへと収束することができるようにする共通に合意済みのメカニズムを用いる。これらの実施形態では、共通に合意済みのメカニズムを使用して確定される指定ノードが、指定ノードの仕事を行うことができない場合、指定ノードの仕事を行うことができる確定されるノードのシーケンスの中で次の確定されるノードが、指定ノードとして選択される。
【００２９】
ボックス２２５を参照すると、共通に合意済みのメカニズムは、最も重要なブリッジまたはノードを識別し、そのノードを指定ノードとして選択するためのブリッジ優先度フィールドデータを備える。他の実施形態では、システム識別子に関連付けられる１つまたは複数の他のフィールドが使用されてもよい。他の実施形態では様々なノードに関連付けられる他のシステム識別情報、または他のデータベースのエントリもしくはフィールドが使用されてもよい。
【００３０】
他の実施形態では、プロトコルに関連付けられる、またはプロトコルに導入される既存の、修正済みまたは新規のタイプ長さ値（ＴＬＶ）が、共通に合意済みのメカニズムを実現するために使用される。概して言えば、様々な実施形態の各々は、１つまたは複数のマルチキャストルート優先度パラメータ（ＭＲＰＰ）を用い、ここでは、特定の共通に合意済みのメカニズムを忠実に守るノードのセット内で各ノードが、同じＭＲＰＰを使用して、指定ノードまたは指定ノードのシーケンスを計算する。概して言えば、各指定ノードは、管理上の名前および／または管理上の優先度などのデータに従って選択される。名前および／または優先度は、共通に合意済みのメカニズム内で複数の異なる「タイブレーカ」メカニズムを提供するために様々な実施形態で修正され得、それにより、対応する異なる転送ツリーが提供されることになる。様々な実施形態では、既存の、修正済みかつ／または新規のｔｌｖが、異なる管理上の重み因子を提供し、それにより、異なる転送ツリーが提供される。
【００３１】
１つの実施形態では、例えば、少数のツリーにわたってマルチキャストトラフィックの負荷が広がるのを可能にするために、１つまたは複数の後続の指定ノードの優先度が配分され、そのことにより、第１の指定ノードの優先度を受けた複数の異なるマルチキャストツリーの指定ノードを選択することになる。１つの実施形態では、ＴＬＶは、第２の優先度か、またはマルチキャストツリーを使用するための指示のいずれかを有し、この場合、第２の優先度の指定ノードもまた、いくつかのサービスについてのアクティブツリーである。追加のデータは、ツリーの数、およびサービスの識別情報を含み得る。１つの実施形態では、マルチキャストツリーの指定優先度についての現在のアルゴリズム指標が使用される。例えば、第１のアルゴリズムは、第１の指定ノード優先度を使用し、第２のアルゴリズムは、第２の指定ノード優先度を使用するといった具合である。任意選択で、この論理は、独自のアルゴリズムによって、またはアルゴリズム番号を使用して次の指定ノードの優先度によって使用されるべきそれらのサービスを識別する新規のＴＬＶを加えることによって、信号で伝えられる。
【００３２】
様々な実施形態では、ボックス２１５に関して上述したように、共通に合意済みのメカニズムは、通信ネットワーク内でのサービスインスタンスの複数のサブセットの各々についてわずかに修正される。特定のサービスインスタンスをサポートするネットワーク全体を通じてノードのすべては、同じ指定ノードを選択しなくてはならない。例えば、サービスインスタンスの第１のサブセットをサポートするネットワーク全体を通じてノードの各々は、それぞれ指定ノードとして機能する第１のノードを確定するように、第１の共通に合意済みのメカニズムに従って動作し、一方、サービスインスタンスの第２のサブセットをサポートするネットワーク全体を通じてノードの各々は、それぞれ指定ノードとして機能する第２のノードを確定するように、第２の共通に合意済みのメカニズムに従って動作する。サービスインスタンスの１つのサブセットの共通に合意済みのメカニズムは、サービスインスタンスの別のサブセットの共通に合意済みのメカニズムと同じであっても、またはそれとは異なっていてもよい。さらには、共通に合意済みのメカニズムがサービスインスタンスのサブセット間で異なっている場合でさえも、サービスインスタンスの１つのサブセットの確定された指定ノードまたはそのシーケンスは、サービスインスタンスの別のサブセットの確定された指定ノードまたはそのシーケンスと同じであっても、またはそれとは異なっていてもよい。
【００３３】
ステップ２３０で、各ノードは、それぞれどのノードが指定ノード（ＤＮ）として機能すべきであるかを確定するように、共通に合意済みのメカニズムに従って動作する。ボックス２３５を参照すると、ノードは、単一のＤＮに、または潜在的なＤＮのシーケンスへと収束するように動作することができる。例えば、ＤＮであると確定された第１のノードが、ＤＮとして機能できない場合には（例えば、閾値レベルを上回って輻輳した、資源が不十分である、など）、潜在的なＤＮのシーケンスにおける次の潜在的なＤＮが選択される。この処理は、選択されたＤＮがＤＮの機能として実行することができるまで、繰り返される。
【００３４】
ステップ２４０で、各ノードは、通信ネットワークまたはその関連する部分の中で、確定された指定ノードと、複数の他のノードの各々との間の最短経路を確定するように動作する。すなわち、各ＤＮについて、ＤＮから発出する経路を表す転送ツリーは、各ノードによって計算される。
【００３５】
ステップ２５０で、ステップ２４０で確定された経路の各々について、確定された経路内に含まれる各ノードは、例えば、それぞれのノードを横断するＤＮからのそれらの確定された最短経路のみを、マルチキャストのためのそれぞれの転送ツリー内に含めるように選択することによって、それぞれのマルチキャスト転送アドレスデータを経路に加える。すなわち、ＤＮから発出する経路を表す転送ツリーは、各それぞれのノードからの追加の転送アドレスデータにより拡大されるが、ただし転送ツリーが、マルチキャストサービスについてノードによって使用されるべき＊，Ｇツリーに達するようにそれぞれのノードを横断する経路を含むことができる場合のみである。
【００３６】
動作に際して、様々な実施形態は、通信ネットワーク内でマルチキャストフレームの最短経路ブリッジング（ＳＰＢ）を、ネットワーク内の複数のノードの各々で、またはサービスインスタンスのサブセットをサポートする複数のノードの各々で、以下のステップを行うことによって確定する：（１）共通に合意済みのメカニズムに従って、指定ノード（ＤＮ）を確定するステップ、（２）ＤＮと複数のノードの各々との間の最短経路を確定するステップ、および（３）それぞれのノードを横断するＤＮからのそれらの確定された最短経路のみを、マルチキャストのためのそれぞれの転送ツリー内に含めるように選択するステップ。
【００３７】
図２の方法は、ＤＮから発出する最短経路を備え、さらには、それぞれのノードに関連付けられるそれらのマルチキャスト経路のみを有する、そのそれぞれのＤＮに基づいて、＊，Ｇツリーをその中に格納した、ネットワークまたはその一部分の中で各ノードについて提供される。
【００３８】
様々な実施形態では、ノードは、必要なメモリ資源の量を抑えるために、その中に格納されている＊，Ｇツリーにプルーニング（ｐｒｕｎｉｎｇ）動作をさらに適用する。
【００３９】
図３は、図１の通信ネットワークの高レベルのブロック図を示しており、ここでは、指定ノードを用いて計算された＊，Ｇツリーが示されている。具体的には、図３は、通信ネットワーク１１０を示し、ここでは、ノード１１２の各々は、ノード１１２Ａが以下の経路：ＡＨ、ＡＢ、ＡＦ、ＡＧ、ＡＤ、ＢＣ、ＤＥ、ＤＩ、およびＤＪを使用して、最短経路＊，Ｇツリーを形成するための指定ノード（ＤＮ）であることを確定済みである。
【００４０】
具体的には、表１−表４（下記）とともに図３は、様々な実施形態に従って、相対的な節約を示している。図３を参照すると、ノードＥ、Ｉ、およびＨの各々は、Ｉ−ＳＩＤ２００と示されるサービスインスタンスに関連付けられていることが分かる。
【００４１】
表１および表２は、それぞれ従来の技法を使用してノードＣおよびＤにおけるマルチキャストフィルタ／転送エントリ情報ベース（ＭＦＩＢ）の使用を示しており、ここでは、本明細書で論じている指定ノードおよび関連技法は使用されていない。具体的には、１つのＭＦＩＢエントリは、マルチキャストの通過ごとに必要であり、一方、１つのツリー計算は、ユニキャストおよび現在のノードのマルチキャストに必要である。したがって、ＣにおけるＭＦＩＢの使用は、１２個のエントリと１０個のツリー計算を含み（表１）、一方、表２に示されるように、ＤにおけるＭＦＩＢの使用には、１３個のエントリと１０個のツリー計算が必要である（表２）。
【００４２】
これらの表に使用される術語の一例として、表１を参照すると、
行１は、ノードＡＣからのノードＣに対するサービスＩＳＩＤデフォルト（すなわち、あらゆるところに及ぶサービスであり、決してプルーニングされない）が、マルチキャスト転送情報データベース（ＭＦＩＢ）内のＣにおいて終端するＡの送信元固有のアドレスをサポートするはずであることを指示している。
【００４３】
行２は、ノードＢＣからのノードＣに対するサービスＩＳＩＤデフォルトが、Ｄ、Ｅ、Ｉ、およびＪに及ぶリンクに対するＢの送信元固有のアドレス、ならびにＣにおける終端サービスをサポートするはずであることを指示している。
【００４４】
行１１は、ノードＥからのノードＣに対するサービスＩＳＩＤ２００について、ＣがノードＩへと通過するＥの送信元固有のアドレスをサポートするはずであることを指示している。これは、行５と比較することによって分かるプルーニング済みリストであり、この場合、デフォルトＩ−ＳＩＤについて、３つのリンクが存在し、ノードＣがサポートされるが、ＩＳＩＳ２００は、Ｃ、Ｉ、またはＪにおいて存在しないため、３つのリンクがプルーニングされる。
【００４５】
網掛けおよびＣ＊は、特定のアドレスエントリが、ノードＣに対してサポートされるが、ノードＣからは決して転送されないこと（リンクは存在しない）を意味する。これらのエントリは、まさに同じくメモリをとり、別の内部表ルックアップに移されることになる。この検討のために、エントリが、送信元ごとに資源を必要とすることに注目するのが適切である。
【００４６】
概して言えば、表１は、Ｉ−ＳＩＤをサポートするために必要なマルチキャストアドレスを示している。表の縮小およびプルーニングの特性が示されている。表１−表４は、実質的にすべてのノードに及ぶサービスを含むデフォルトＩ−ＳＩＤを使用する。表３とともに表１は、広範に配分されるサービスについての表縮小の特性を示すのに役立つ。デフォルトＩ−ＳＩＤは、すべてのノードに達するデータ経路に使用される。
【００４７】
【表１】
0005851040.tif 000002
【００４８】
【表２】
0005851040.tif 000003
【００４９】
表３および表４は、本明細書に説明されている実施形態を使用して、それぞれノードＣおよびＤにおけるＭＦＩＢの使用を示しており、ここでは、ノードＡが指定ノードとして選択される。具体的には、（表１および表２のマルチキャストの通過ごとに１つのＭＦＩＢエントリが必要なのと異なり）Ｉ−ＳＩＤごとに１つのエントリのみ、Ｉ−ＳＩＤがツリーのノードを通過する際に必要であるにすぎない。したがって、ＣにおけるＭＦＩＢの使用は、１つのエントリと２つのツリー計算を含み（表３）、一方、ＤにおけるＭＦＩＢの使用は、２つのエントリと２つのツリー計算が必要である（表４）。これにより、様々な実施形態を使用して達成される計算の著しい縮小（例えば、１つのマルチキャストツリーに１つのユニキャストを加える）が強調される。
【００５０】
これらの表に使用される術語の一例として、表３を参照すると、行１は、いずれかのノードからノードＣに対するサービスＩＳＩＤデフォルトについて、Ｃは、Ｂに至るおよびＣにおいて終端する２つのリンクの＊，Ｇアドレスをサポートするはずであることを指示している。Ｃは、デフォルトＩ−ＳＩＤに対して単一のエントリしか必要でなく、そのため、所要の表資源における削減がもたらされる。Ｃは、ＩＳＩＤ２００に対する最短経路上になく、したがって、ＩＳＩＤ２００が全く必要でない（すなわち、表資源およびノードＣについての先の表に対するさらなるプルーニングの削減）。
【００５１】
表４は、デフォルトおよびＩＳＩＤ２００に対する最短経路上にあるノードＤからの視点を示している。Ｄは、ＩＳＩＤ２００のマルチキャストツリーについての経路上にあり、したがって、プルーニング不可能である。デフォルトＩ−ＳＩＤも示されている。
【００５２】
【表３】
0005851040.tif 000004
【００５３】
【表４】
0005851040.tif 000005
【００５４】
表１、表２と表３、表４との間に示されている表サイズの縮小は、１つのエントリとポートのリストが存在する＊，Ｇアドレス指定を使用することに起因する。ユニキャスト転送およびマルチキャスト転送は、宛先アドレスによってインデックスされるルックアップ表を使用することに留意されたい。様々な実施形態は、マルチキャスト転送表にフレームをルックアップおよび反復することができるようにする。任意選択のハードウェアアシストを使用する諸実施形態では、マルチキャストのスケーリングは、そのようなハードウェア資源の使用を受ける。様々な実施形態は、マルチキャストツリーの一部としてプルーニングを行い、そのようなプルーニングは、記載の実施形態ならびにＳＰＢ仕様の範囲で説明されている他の構成の両方に適用可能である。プルーニングは、マージポイントを越える転送ツリーのリーフが、それぞれのマルチキャストエントリを必要としない際に行われる（Ｉ−ＳＩＤに関連付けられるサービスが存在しないため）。
【００５５】
様々な実施形態は、概して、非常に効率的な単一のツリーの実施形態の環境の範囲内で説明されている。しかしながら、様々な他の実施形態は、負荷バランス、冗長サービス経路、および特殊目的の経路などを可能にする複数のツリーを用いる。
【００５６】
具体的には、経路識別子法に基づく単一のツリー計算が使用され、ここでは、すべての動作可能ノードのうちノード優先度が最も低い動作可能ノードが、指定ノードであると確定される。単一のツリーは、リンクメトリックおよびこのノードについての低い経路識別子タイブレーカに基づいて構築される。例えば、図２の方法２００の様々なステップは、指定ノードとして、すべての動作可能ノードのうちノード優先度が最も低い動作可能ノードを選択するようになされている。様々な実施形態の利点は、様々な計算を行うこと、および転送ツリーデータを格納することなどに対する資源要件の削減に見出される。時には、ユニキャストのための最短経路は、いくつかの実施形態を使用して計算される経路でないこともある。例えば、図３を参照すると、スイッチＡは、優先度が最も高いノードであり、マルチキャスト指定ノードであることが分かる。しかしながら、スイッチＩの場合、その差はわずかであるものの、マルチキャストにおけるスイッチＡからスイッチＣへの経路は、ユニキャストについての直接的な１ホップ（ＩＣ）の最短経路に対して３ホップ（ＩＤ、ＤＡ、ＡＢ、ＢＣ）である。
【００５７】
図４は、本明細書に説明されている機能を行う際に使用するのに適している汎用コンピュータの高レベルのブロック図を示している。図４に示されているように、システム４００は、プロセッサ要素４０２（例えば、ＣＰＵ）、例えばランダムアクセスメモリ（ＲＡＭ）および／または読取り専用メモリ（ＲＯＭ）のメモリ４０４、ＲＭＴ管理モジュール４０５、ならびに様々な入力／出力デバイス４０６（例えば、テープドライブ、フロッピドライブ、ハードディスクドライブ、またはコンパクトディスクドライブ、受信器、送信器、スピーカ、ディスプレイ、出力ポート、およびユーザ入力デバイス（キーボード、キーパッド、およびマウスなど）を含むが、これらに限定されない記憶デバイス）を備える。
【００５８】
本発明は、例えば、特定用途向け集積回路（ＡＳＩＣ）、汎用コンピュータ、または任意の他のハードウェアの均等物を使用して、ソフトウェアおよび／またはソフトウェアとハードウェアとの組合せで実施され得ることに留意されたい。１つの実施形態では、方法２００およびその修正形態は、上記に論じた機能を実施するために、メモリ４０４内にロードされ、プロセッサ４０２によって実行され得る。したがって、本発明の（関連するデータ構造を含む）方法２００は、例えば、ＲＡＭメモリ、および磁気または光ドライブもしくはディスケットなど、コンピュータ可読媒体またはキャリアにおいて格納され得る。様々な実施形態は、ネットワークのサイズが大きくなるにつれて容易に拡大するので有利である。概して、諸実施形態は、現在のマルチキャストスケーリングの性能を維持しつつ、ユニキャストについてのリンク状態および最短経路転送を可能にする。諸実施形態は、最短経路と一致しない単一のツリーを使用することができるとともに、現在のプロバイダバックボーン（ＰＢＢ）ネットワーク転送が元のままの形を保つことを可能にする。
【００５９】
ソフトウェア方法として本明細書に論じられたステップのうちのいくつかは、例えば、様々な方法ステップを行うようにプロセッサと協働する回路構成要素として、ハードウェア内で実施可能であることが企図される。本明細書に説明されている機能／要素の一部分は、コンピュータプログラム製品として実施され得、ここでは、コンピュータ命令は、コンピュータによって処理されると、本明細書に説明されている方法および／または技法が呼び出される、あるいは別の形で実行されるように、コンピュータの動作を適合させる。本発明の方法を読み出すための命令は、固定または取外し可能な媒体に格納され、ブロードキャストでもしくは他の信号担持媒体でデータストリームを介して伝送され、かつ／またはこれらの命令に従って動作する計算デバイス内のメモリ内に格納され得る。
【００６０】
本発明の教示を組み込んだ様々な実施形態が本明細書に詳細に示され説明されてきたが、当業者は、これらの教示をさらに組み込んだ他の多数の多様な実施形態を容易に考案することができる。
【図１】
0005851040.tif 000006
【図２】
0005851040.tif 000007
【図３】
0005851040.tif 000008
【図４】
0005851040.tif 000009