(57)【要約】【課題】ＬＡＮ空間からＷＡＮ又はプロバイダ・ネットワーク空間にイーサネットを拡大するには、効率的なループ・フリーのイーサネットを生成することが必要とされる。【解決手段】ブリッジへのユニキャスト転送用に少なくとも１つのＭＡＣアドレスが、またブリッジからのマルチキャスト転送用に少なくとも１つのＭＡＣアドレスが割り当てられる。ブリッジは、ネットワークの同期の取れた構成された見取図がノード間で共有されるように、リンク状態ブリッジング・プロトコルによって状態情報を交換する。各ノードは、同位ブリッジング・ノード間を接続する最短パスを計算し、それを適切な転送テーブルに入力する。逆方向パス転送チェックが、ループ抑制を提供するため、着信パケット上で実行される。ネットワークが不安定な間、宛先ＭＡＣアドレスによって識別されるユニキャスト・パケットについてのループ抑制は使用不能にされる。【選択図】図５
2009510953.tif 000002
【特許請求の範囲】
【請求項１】
プロバイダ・リンク状態ブリッジング・イーサネット・ノードであって、
少なくとも１つの関連するユニキャストＭＡＣアドレスと、
少なくとも１つの関連するマルチキャストＭＡＣアドレスと、
それぞれのユニキャストＭＡＣアドレスと同位ノードの複数のマルチキャストＭＡＣアドレスとに基づいてノード間でリンク状態ルーティング情報を交換するため、および同位ノード間の最短パス接続性を決定するためのルーティング・モジュールであって、多数の等コスト・パスが利用可能である場合、選択された最短パスが、前記ルーティング情報の交換に関係するすべてのブリッジに対して整合性のあるものとなるように決められる、ルーティング・モジュールと、
前記ノードから同位ブリッジ・ノードへの接続性を識別するための、前記ルーティング・モジュールから受け取った転送情報が入力される転送情報ベース（ＦＩＢ）であって、前記ユニキャストＭＡＣアドレスは同位ノードを指し示し、前記マルチキャスト・アドレスは同位ノードから指し示すものである、転送情報ベース（ＦＩＢ）と、
着信パケットを検査し、前記パケットが、送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するために、前記ＦＩＢによって決定された出口ポートとして使用されるポートと同じ入口ポートに到着したかどうかを判定するための逆方向パス転送チェック（ＲＰＦＣ）モジュールと、
前記ノードの出口ポートが同位ブリッジの宛先ＭＡＣアドレスに関連付けられているかどうかを前記ＦＩＢから決定し、前記パケットを転送するための転送モジュールと、
を含むイーサネット・ノード。
【請求項２】
前記パケットが正しい入口ポートに到着しなかったと決定された場合、前記ＲＰＦＣモジュールが、前記パケットを廃棄する、請求項１に記載のイーサネット・ノード。
【請求項３】
ネットワーク・トポロジおよび前記ルーティング・モジュールが収束していない場合、前記ＲＰＦＣモジュールが、ユニキャスト・トラフィックについて使用不能にされる、請求項１に記載のイーサネット・ノード。
【請求項４】
パケットの前記廃棄を検出することによって永続的なループが存在するかどうかをチェックするために、前記ＲＰＦＣモジュールが、ユニキャスト・パケットについて定期的に使用可能にされる、請求項３に記載のイーサネット・ノード。
【請求項５】
前記パケットの宛先ＭＡＣアドレス用の出口ポートが前記ＦＩＢ内で識別されない場合、前記転送モジュールが、前記パケットを廃棄する、請求項１に記載のイーサネット・ノード。
【請求項６】
前記少なくとも１つのユニキャストＭＡＣアドレスが、ライン・カード、仮想スイッチ・インスタンス（ＶＳＩ）、もしくはＵＮＩポート、またはブリッジにおける終端のその他の任意の命名の１つに割り当てられ、あるいは前記ブリッジの背後のＭＡＣ終端を表す、請求項１に記載のイーサネット・ノード。
【請求項７】
前記ルーティング・モジュールが、フロイドのアルゴリズムまたはダイクストラのアルゴリズムによって前記最短パスを決定する、請求項１に記載のイーサネット・ノード。
【請求項８】
前記ＦＩＢモジュールが、前記最短パス内のノードにのみ関係する情報に基づいてデータ入力される、請求項１に記載のイーサネット・ノード。
【請求項９】
各ブリッジが、２つのノード間の前記最短パス上にある場合、前記２つのノードが関心に基づくコミュニティの共通部分を有するかどうかを決定することができ、前記ブリッジが、転送テーブル内に入力されるデータをしかるべく変更するように、前記リンク状態情報が、ルーティング公示内に関心に基づくコミュニティ情報を含む、請求項１に記載のイーサネット・ノード。
【請求項１０】
前記リンク状態情報が、複数の仮想ＬＡＮ（ＶＬＡＮ）識別子を含むことをさらに含み、各識別子が、コントロール・プレーンでメッシュの１つのインスタンスを定義するために使用される、請求項１に記載のイーサネット・ノード。
【請求項１１】
前記複数のＶＬＡＮ識別子が、多数の等コスト・パスが利用され得るように、ネットワークを区分化して、前記メッシュ内におけるトラフィックの拡散を容易にするために使用される、請求項１０に記載のイーサネット・ノード。
【請求項１２】
前記ルーティング・モジュールが、多数の等コスト・パス間の均衡を破り、ＶＬＡＮの集まりの間で負荷分散をもたらすために、異なるランク付けアルゴリズムを各ＶＬＡＮに割り当てながら、各ＶＬＡＮについての前記最短パスを決定する、請求項１１に記載のイーサネット・ノード。
【請求項１３】
前記リンク状態情報が、一意のマルチキャスト・グループを識別するために、前記リンク状態ルーティング公示内に含まれる拡張サービスＩＤ（Ｉ−ＳＩＤ）を含み、２つのブリッジ間の前記最短パス上にあるブリッジが、各ブリッジに関連付けられた前記ユニキャストＭＡＣアドレスと、前記２つのブリッジに共通なすべてのＩ−ＳＩＤに関する前記マルチキャストＭＡＣアドレスとをインストールする、請求項１に記載のイーサネット・ノード。
【請求項１４】
メッシュ・ネットワーク内でプロバイダ・リンク状態ブリッジング・イーサネット・ノードを構成し、動作させる方法であって、
リンク状態情報を同位ノードと交換するステップであって、各ノードが、少なくとも１つの関連するユニキャストＭＡＣアドレスと、少なくとも１つの関連するマルチキャストＭＡＣアドレスとを有するステップと、
前記交換されたリンク状態情報に基づいて、同位ノードに到る最短パスを最短パス・アルゴリズムによって決定するステップであって、多数の等コスト・パスが利用可能である場合、選択された最短パスが、前記ルーティング情報の交換に関係するすべてのブリッジに対して整合性のあるものとなるように決められるステップと、
同位ノードを指し示す関連するユニキャストＭＡＣアドレスと、同位ノードから指し示すマルチキャストＭＡＣアドレスとを利用する前記決定された最短パスを転送情報ベース（ＦＩＢ）に入力するステップと、
着信パケットの送信元ＭＡＣアドレスを検査し、前記パケットが、送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するために、前記ノードの出口ポートとして使用されるポートと同じ、前記ノードの入口ポートに到着したかどうかを判定することによって逆方向パス転送チェック（ＲＰＦＣ）を実行するステップであって、前記ＲＰＦＣが失敗した場合、前記パケットが廃棄されるステップと、
前記ＲＰＦＣが成功した場合、前記ＦＩＢ内で識別される前記パケットの宛先ＭＡＣに関連付けられた前記ノードの出口ポートを介して、前記パケットを同位ブリッジに転送するステップと、
を含む方法。
【請求項１５】
ネットワーク・トポロジ、したがって、ルーティング・モジュールが収束していない場合、前記ＲＰＦＣを実行する前記ステップが、ユニキャスト・トラフィックについて選択的にバイパスされる、請求項１４に記載の方法。
【請求項１６】
最短パスを決定する前記ステップが、フロイドのアルゴリズムまたはダイクストラのアルゴリズムを利用する、請求項１４に記載の方法。
【請求項１７】
前記最短パス・アルゴリズムが、前記ネットワークを使用するその他のアプリケーションの、キャパシティ、速度、使用量、および正味アベイラビリティを含む群から選択されるコストの尺度をさらに含む、請求項１６に記載の方法。
【請求項１８】
前記ルーティング・モジュールが、どちらのタイプのパケットの間にも転送の合同性が存在するように、ユニキャストおよびマルチキャスト接続性のための共通メトリックを利用する、請求項１４に記載の方法。
【請求項１９】
前記ＦＩＢに入力する前記ステップが、前記最短パス内のノードにのみ関係する情報にのみ基づく、請求項１４に記載の方法。
【請求項２０】
前記パケットが、８０２．１ａｈに従ったＭＡＣ−ｉｎ−ＭＡＣカプセル化である、請求項１４に記載の方法。
【請求項２１】
各ブリッジが、２つのノード間の前記最短パス上にある場合、前記２つのノードが関心に基づくコミュニティの共通部分を有するかどうかを決定することができ、前記ブリッジが、転送テーブル内に入力されるデータをしかるべく変更するように、リンク状態情報を交換する前記ステップが、ルーティング公示内に関心に基づくコミュニティ情報を含むステップをさらに含む、請求項１４に記載の方法。
【請求項２２】
リンク状態情報を交換する前記ステップが、複数の仮想ＬＡＮ（ＶＬＡＮ）識別子を含むステップをさらに含み、各識別子が、コントロール・プレーンでメッシュの１つのインスタンスを定義するために使用される、請求項１４に記載の方法。
【請求項２３】
前記複数のＶＬＡＮ識別子が、多数の等コスト・パスが利用され得るように、前記ネットワークを区分化して、前記メッシュ内におけるトラフィックの拡散を容易にするために使用される、請求項２２に記載の方法。
【請求項２４】
前記最短パスを決定する前記ステップが、多数の等コスト・パス間の均衡を破り、ＶＬＡＮの集まりの間で負荷分散をもたらすために、異なるランク付けアルゴリズムを各ＶＬＡＮに割り当てながら、各ＶＬＡＮについて繰り返される、請求項２３に記載の方法。
【請求項２５】
リンク状態情報を交換する前記ステップが、一意のマルチキャスト・グループを識別するために、前記リンク状態ルーティング公示内に含まれる拡張サービスＩＤ（Ｉ−ＳＩＤ）を含むステップをさらに含み、２つのブリッジ間の前記最短パス上にあるブリッジが、各ブリッジに関連付けられた前記ユニキャストＭＡＣアドレスと、前記２つのブリッジに共通なすべてのＩ−ＳＩＤに関する前記マルチキャストＭＡＣアドレスとをインストールする、請求項１４に記載の方法。
【請求項２６】
リンク状態情報を交換する前記ステップが、与えられたマルチキャスト・グループの送信元、送信先、または送信元と送信先の両方のどれであることを前記ブリッジが望むかを示すアトリビュートを前記リンク状態公示に追加することによって、非対称ＶＰＮ接続性を提供するステップをさらに含み、２つの他のブリッジ間の前記最短パス上にあることを確定した前記ブリッジが、前記送信元／送信先アトリビュートを使用して、どのマルチキャスト・グループ・アドレスがインストールされるべきかを決定する、請求項１４に記載の方法。
【請求項２７】
イーサネット・ブリッジング・ネットワークであって、
前記ネットワーク内の同位ブリッジに関する転送情報を含む転送情報ベース（ＦＩＢ）を各ブリッジが有する複数のブリッジであって、着信パケットが、前記着信パケットの送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するための前記ブリッジの出口ポートとして使用されるポートと同じ、前記ブリッジの入口ポートに到着したかどうかを判定するために、逆方向パス転送チェック（ＲＰＦＣ）を各ブリッジが実行することが可能な、複数のブリッジと、
前記ブリッジを相互接続し、メッシュ・ネットワークを形成する複数のパスとを含み、
前記ＦＩＢが、前記複数のブリッジ間で交換されたリンク状態情報に基づいてデータ入力され、同位ブリッジ間の最短パスを決定するために使用され、選択されるパスの決定は、多数の等コスト・パスが利用可能である場合、同位ブリッジに対して整合性のあるものとなるように決められる、イーサネット・ブリッジング・ネットワーク。
【請求項２８】
１つまたは複数のブリッジが、同位ブリッジを前記ＦＩＢに入力する際に利用される、少なくとも１つの関連するユニキャスト媒体アクセス制御（ＭＡＣ）アドレスと、少なくとも１つの関連するマルチキャストＭＡＣアドレスとを有する、請求項２７に記載のブリッジング・ネットワーク。
【請求項２９】
ネットワーク・トポロジがブリッジ間で収束していない場合、前記ＲＰＦＣが、前記パケットの宛先アドレスによって識別されるユニキャスト・パケットについては選択的に使用不能にされ、マルチキャスト・パケットについては使用可能にされる、請求項２７に記載のブリッジング・ネットワーク。
【請求項３０】
ブリッジのサブセットが、同位ＰＬＳＢドメインを識別するＭＡＣを介して相互接続され得る、個々のプロバイダ・リンク状態ブリッジング（ＰＬＳＢ）ドメインを形成する、請求項２７に記載のブリッジング・ネットワーク。
【請求項３１】
プロバイダ・バックボーン・トランスポート（ＰＢＴ）ネットワークが、ＰＢＴ  ＭＡＣ識別子によって、前記ブリッジング・ネットワークのエッジ・ブリッジを用いて相互接続され得る、請求項２７に記載のブリッジング・ネットワーク。
【請求項３２】
８０２．１ａｈプロバイダ・バックボーン・ブリッジが、前記ブリッジング・ネットワーク上にオーバーレイされる、請求項２７に記載のブリッジング・ネットワーク。
【請求項３３】
接続性方針メカニズムが、各同位ブリッジへのマルチポイント・ツー・ポイント（ｍｐ２ｐ）ユニキャスト・ツリーのリーフとして、および各関心に基づくコミュニティに関する同位ノードの組への（Ｓ，Ｇ）ポイント・ツー・マルチポイント（ｐ２ｍｐ）マルチキャスト・ツリーのルートとして、前記複数のブリッジの１つを利用することによって構成される、請求項２７に記載のブリッジング・ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、イーサネット・トラフィック・ルーティング・プロトコルに関し、詳細には、メッシュ型イーサネット・ネットワークにおける接続性の構成に関する。
【背景技術】
【０００２】
イーサネット・ネットワーク・アーキテクチャでは、ネットワークに接続された装置は、常時、共用遠隔通信パスを使用するための能力を求めて競合する。ネットワーク・セグメントを相互接続するために多数のブリッジまたはノードが使用される場合、メッシュ型ネットワーク・アーキテクチャでは、同じ宛先に到る多数の潜在的なパスが存在する。このアーキテクチャの利点は、それがブリッジ間にパス冗長性を提供し、追加リンクの形態でネットワークにキャパシティが追加されることを可能にすることである。しかし、フラッディングおよび学習（ｆｌｏｏｄｉｎｇ  ａｎｄ  ｌｅａｒｎｉｎｇ）というイーサネットのパラダイムは、折り返しパス（ｒｅｐｌｉｃａｔｉｎｇ  ｐａｔｈ）がループしないことを保証する要件のために、メッシュ型ネットワーク内に存在する接続性の広さを、一般には任意の瞬間に利用しないことを意味する。ブリッジは、単純なリンクによって、または共用ＬＡＮセグメントもしくは共用仮想ＬＡＮセグメントによって相互接続され得ることに留意されたい。本文書の観点からは、セグメント、仮想セグメント、およびリンクは、実際上交換可能である。
【０００３】
イーサネット・ネットワーク内の各ブリッジ・ノードは、与えられた装置からのパケットがどのセグメント上で到着したかを観察することによって、どの局所イーサネット・セグメントを経由してどの装置またはステーションに到達し得るかを学習する。未知の装置（転送情報ベース（ＦＩＢ：ｆｏｒｗａｒｄｉｎｇ  ｉｎｆｏｒｍａｔｉｏｎ  ｂａｓｅ）内に転送情報が存在しない装置）に送信する場合、ブリッジは、すべての接続セグメント上にメッセージを複製する（これはフラッディングとして知られている）。これは２つの効果を有し、すなわち、フラッディングされたパケットを観察したブリッジは、発信装置に到るための到達可能性情報を学習し、また将来のある時点に、意図された宛先装置からの、メッセージによって求められた応答またはその後の求められたものではないメッセージが観察され、それから、どのセグメントを経由して装置がメッセージに応答したかが分かることが期待される。次第にブリッジは、ネットワーク内の特定の装置に到達するための次のセグメントとしてどのセグメントが適切であるかについての独自の絵図を作り上げる。その後にメッセージが送信されて来た場合、ブリッジは、そのＦＩＢを使用して、どの局所接続セグメントにメッセージを転送するかを決定することができる。ブリッジが経験を通してネットワークを学習することを可能にする手法は、透過ブリッジング（ｔｒａｎｓｐａｒｅｎｔ  ｂｒｉｄｇｉｎｇ）として知られている。この技法の１つの主要な利点は、ブリッジングが管理者によるセットアップを必要としないことである。
【０００４】
メッシュでは、パケットが同位装置間で転送される場合、パケットは、複数のパスにより、多数のブリッジを通過して横断することが可能であり得る。しかし、パケットが多数の経路上で同時に送信された場合、ネットワーク輻輳が増大し、可能なループ形成条件が生じることがある。このシナリオは、メッシュにおいて、マルチキャストおよび／またはフラッディングされたトラフィックに関して生じるが、それは、与えられたパケットのコピーの数が、抑制されなければ指数関数的に増加するためである。参加ノードの組を論理的に接続するスパニング・ツリーを反復的に選出することによって、パケット重複を除去するために、スパニング・ツリー・プロトコル（ＳＴＰ：Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ）アルゴリズムが利用される。このアルゴリズムは、特にブリッジ・ループ（１つのセグメントを別のセグメントにリンクして無限ループ状況を引き起こす多数のパス）を回避するように構成される。このアルゴリズムは一般に、すべてのセグメントから選出ルート・ブリッジ（ｒｏｏｔ  ｂｒｉｄｇｅ）への最短パスを計算する。最も良いパスが障害を起こした場合、アルゴリズムは、ネットワークを再計算し、次に良い経路を見つける。ルートが障害を起こした場合、新しいルートが選出され、アルゴリズムが再実行される。同時に、装置到達可能性に関するすべての学習されたＭＡＣ情報は廃棄され、新しいスパニング・ツリーが確立されると、ＦＩＢには、フラッディングおよび学習を通して、徐々にデータが再入力されていく。
【０００５】
ＳＴＰは、接続性を提供する一方で、ノードまたは装置間に多数のアクティブ・パスがある場合に存在するネットワーク内の望ましくないループを防止する。ループが形成を許された場合、ループに入ったパケットは、ノードがそのパケットを削除するアクションを取るまで、またはループが壊されるまで、巡回し続ける。ループ内のブリッジがフラッディングを行った場合、またはパケットがマルチキャスト・パケットである場合、ループを巡るたびにパケットの追加コピーが生成され、これは非常に望ましくない結果である。ループ・フリー（ｌｏｏｐ−ｆｒｅｅ）な接続性を確立するため、ＳＴＰは、展開されたネットワーク内のすべてのブリッジに枝を伸ばすツリーを作成し、冗長パスを強制的にスタンバイまたはブロック状態にする。ＳＴＰは、ネットワーク内の任意の２点間に、１度に１つのアクティブ・パスのみを許可し、これがループを防止するが、物理メッシュ接続性に関連する追加のキャパシティは利用されない。ＳＴＰは、ブリッジの簡潔性のために状態メモリを持たないノード用に設計された。しかし、ループ・フリーな接続性に対する単純過ぎる手法は、物理トポロジを刈り込んで単一のループ・フリーなスパニング・ツリーにする要件のため、過大な未使用ネットワーク・キャパシティをもたらし得る。
【０００６】
ＳＴＰ収束（ＳＴＰ  ｃｏｎｖｅｒｇｅｎｃｅ）の最中のルート選出は、どのブリッジが最低ＩＤを有するかをブリッジの組が決定すること、その後、最低ＩＤを有するブリッジ、すなわち「ルート」に到る最低コストのパス上にあるネクスト・ホップ（ｎｅｘｔ  ｈｏｐ）を各ブリッジが決定することによって決定される。ブリッジは最初、スパニング・ツリー・プロトコル交換において、自らのＩＤとヌル・コストとを公示する。より低いＩＤを有する公示を受信した場合、ブリッジは、自らのＩＤを公示することを止め、そのより低いＩＤとコストとを公示する。同様に、現在の最低ＩＤに到るより低いコストを有するセグメントに遭遇した場合、ブリッジは、その再放出される公示と内部状態とをしかるべく修正する。最終的に、ネットワークは、最低ＩＤの共通見解に収束し、各ブリッジは、ルートに到る最低コスト・パス上の次のセグメントを知る。コストが変化した場合、またはスパニング・ツリー内の１つのネットワーク・セグメントが到達不能になった場合、ＳＴＰアルゴリズムは、セグメントの変更された組を利用する接続性を提供するために、反復的に新しいスパニング・ツリー・トポロジを計算する。ネットワークのブリッジが収束していない間、ループ形成および複製を防止するために、ポートがブロックされて、ネットワーク・トラフィックを停止させる。
【０００７】
図１は、メッシュ・ネットワークにおけるスパニング・ツリー・プロトコル・アルゴリズムが、ネットワークを介したパケットの転送にどのように影響するかについての一例を示している。送信元装置Ａから、ＳＴＰアルゴリズムは、（マルチキャスト経路として示された）最低コストを達成する各ノード間のリンクを決定することによって、ネットワークを介したパスを緻密に計画している。この経路は、ネットワークを横断するすべてのトラフィックが利用可能なパスを決定する。ブリッジ１１０に接続された装置Ａが、ネットワーク上において新しい装置Ｂにパケットを送信する。ネットワークのブリッジは、この装置用のデータが入力された転送テーブルを有していない。パケットがネットワーク内にフラッディングされ、スパニング・ツリーによって定義されたパスによって各ブリッジ・ノードに転送される。スパニング・ツリーに従って、パケットは、ブリッジ１１０からブリッジ１１２まで転送される。ブリッジ１１０から隣接ブリッジ１１６、１２０へのリンクは、使用不能またはブロックされており、スパニング・ツリーの一部ではないので、利用されない。ブリッジ１１２から、パケットは、ネットワークのその他のノードであるブリッジ１２０、１２２、１２４、１１４に転送される。ブリッジ１１４は、パケットをさらにブリッジ１１６、１１８に転送する。装置Ｂは、パケットのフラッディングされたコピーをブリッジ１２２を介して受信する。すべての中間ブリッジは、送信元「Ａ」に到達するためのセグメントを知り、ＦＩＢをしかるべく更新する。その後、装置Ｂによって送信される応答は、戻り経路がネットワーク内の中間ブリッジに知られているので、フラッディングされることなく、ネットワークを横断して装置Ａに直接転送される。基本的に、パケットのフラッディングがネットワークに入り、装置Ｂから装置Ａに１つの応答が戻され、初期メッセージを観察して「Ａ」への最適転送を学習した中間ブリッジは、それと同様にして、応答を観察して「Ｂ」への最適転送を学習する。
【０００８】
イーサネット・ネットワークにおけるＳＴＰの使用は、ネットワーク内のリンクまたはＬＡＮセグメントの利用効率を制限する。ＳＴＰアルゴリズムによって選択されなかったセグメントおよびリンクは、使用不能であり、ネットワークの物理トポロジに何らかの変化が生じて、そのリンクが結果のスパニング・ツリーの一部になるまで、基本的にアクティブ・ネットワーク・トポロジの一部ではない。これは、これらのリンクのキャパシティを阻害する。小規模ＬＡＮ環境では、これは問題にならないかもしれないが、ＷＡＮまたはプロバイダ・ネットワークでは、未使用キャパシティは、スケーリングに影響を与え、活用が不十分な投資に相当する。加えて、障害が発生した場合、ＳＴＰを再収束させ、ネットワーク内のすべてのブリッジを安定させるのに要する時間の間、ネットワーク全体のパフォーマンスが影響を受ける。現在のスパニング・ツリーのルートは、必ずしも物理最短パス上にあるとは限らないので、スパニング・ツリーを利用する与えられたパケットによって取られるパスは一般に、送信元と宛先の間の最短パスではない。例えば、装置Ｃが隣接ブリッジ１１６に接続された場合、装置Ａからのパケットは、必ずしもブリッジ１１６への最短パスを提供しない現在のスパニング・ツリーに基づいて、依然としてブリッジ１１２、１１４を横断しなければならない。最後に、プロバイダ・ネットワークでは、仮想プライベート・ネットワーク（ｖｉｒｔｕａｌ  ｐｒｉｖａｔｅ  ｎｅｔｗｏｒｋ）の形態をとる多くの小規模な関心に基づくコミュニティ（ｃｏｍｍｕｎｉｔｙ  ｏｆ  ｉｎｔｅｒｅｓｔ）が存在することができ、情報のフラッディングをそれらの関心に基づくコミュニティ内に制限するには、一般にコミュニティ毎に異なるスパニング・ツリーを必要とする。
【０００９】
ＳＴＰパフォーマンスを改善し、メッシュ型イーサネット・ネットワーク内でのループ形成を緩和するために、様々な方法が提案された。現在の提案のいくつかは、ループ形成の影響を制限するため、ＭＰＬＳに類似したラベル、またはイーサネット・パケットへの有効期間（ＴＴＬ：ｔｉｍｅ−ｔｏ−ｌｉｖｅ）フィールドの追加を必要とする。しかし、これらの解決策を実施するには、基本的なデータ・プレーン（ｄａｔａ  ｐｌａｎｅ）の修正が必要とされ、それがこれらの解決策の有用性を制限する。加えて、パケットが複製され得る回数を制限するだけでは、ループ形成問題に対する明らかに不完全な解決策にしかならない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ＬＡＮ空間からＷＡＮまたはプロバイダ・ネットワーク空間にイーサネットを拡大するには、効率的なループ・フリーのイーサネットを生成するための改善されたメカニズムが必要とされる。これは、メッシュ接続性をより良く利用するメカニズム、障害またはトポロジ変更の影響を制限する（例えば、接続性を中断しない、または接続性の中断を最低限に抑える）メカニズム、ループを抑制する、またはループ形成の影響を緩和するメカニズムである。したがって、ネットワーク利用率を改善しながらも、一時的または永続的ループの落とし穴を回避するイーサネット・ネットワークが必要とされている。
【課題を解決するための手段】
【００１１】
本発明は、プロバイダ・リンク状態ブリッジング（ＰＬＳＢ：Ｐｒｏｖｉｄｅｒ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｂｒｉｄｇｉｎｇ）を利用することによって、ループ・フリーなイーサネット・ネットワークを生成するためのシステムおよび方法を提供する。ＰＬＳＢは、コントロール・プレーン（ｃｏｎｔｒｏｌ  ｐｌａｎｅ）によってイーサネットＭＡＣ転送テーブルの静的構成を拡張し、リンク状態ルーティング・システム（ｌｉｎｋ  ｓｔａｔｅ  ｒｏｕｔｉｎｇ  ｓｙｓｔｅｍ）によるイーサネット転送の直接操作を利用する。少なくとも２つのＭＡＣアドレスが、各ブリッジに関連付けられ、１つはブリッジへのユニキャスト転送用、１つはブリッジからのマルチキャスト転送用である。ユニキャストＭＡＣは、ブリッジにパケットを送信する場合に、パケットの宛先アドレスとして、同位ブリッジによって使用され、ブリッジからその同位ブリッジへのユニキャストまたはマルチキャスト・トラフィックの送信元としてブリッジを識別する。マルチキャスト・アドレスは、多数の同位ブリッジに同時にトラフィックを送信する場合に、ブリッジによって使用され、ルーティング・システムによって構成された特定のマルチキャスト・ツリーを識別する。
【００１２】
ブリッジは、リンク状態プロトコル（ｌｉｎｋ  ｓｔａｔｅ  ｐｒｏｔｏｃｏｌ）によって状態情報を交換し、最短パス・アルゴリズムによって同位ブリッジ間の最短パスを決定するのに利用される状態データベース（ｓｔａｔｅ  ｄａｔａｂａｓｅ）を維持する。任意の２つのブリッジ間の等コスト複数パス（Ｅｑｕａｌ  Ｃｏｓｔ  Ｍｕｌｔｉｐｌｅ  Ｐａｔｈｓ）の条件下では、「行き（ｇｏ）」および「戻り（ｒｅｔｕｒｎ）」ユニキャスト・パス、ならびに２つのマルチキャスト・ツリーの関連するセグメントが、同様にルーティング（ｃｏ−ｒｏｕｔｅ）されるように、一貫したパス選択が、すべてのブリッジによって行われる。その後、転送テーブルまたは転送情報ベース（ＦＩＢ）には、適切なユニキャストおよびマルチキャスト・アドレスが入力される。その後、一意のユニキャストおよびマルチキャスト配送ツリーが、各ブリッジで生成され、より効率的なリンク利用を提供する。
【００１３】
ループ抑制は、各ブリッジにおいて受信パケット上で実行される逆方向パス転送チェック（ｒｅｖｅｒｓｅ  ｐａｔｈ  ｆｏｒｗａｒｄｉｎｇ  ｃｈｅｃｋ、ＲＰＦＣ）によって提供される。ＲＰＦＣは、パケットがＦＩＢ内で識別される正しいポートまたはインターフェースに到着したかどうかを決定し、正しいポートに到着しなかったパケットは廃棄される。これは、（上記のような）任意の２点間のすべてのパスの同ルーティング特性（ｃｏ−ｒｏｕｔｅｄ  ｐｒｏｐｅｒｔｙ）のために可能になる。ループ形成が潜在的に発生し、ネットワーク・トポロジが収束しない、ブリッジまたはリンク障害の間など、ネットワークが不安定な時間の間、ＲＰＦＣは、トラフィックへの影響を最低限に抑えるため、ユニキャスト・パケットに対しては使用不能にされることができる。各ブリッジにおいてトポロジが再収束した時、ＲＰＦＣは、再び使用可能にされることができる。マルチキャスト・トラフィックの場合、ＲＰＦＣは、無制限な複製の可能性を低減するため、決して使用不能にされることはない。
【００１４】
仮想プライベート・ネットワーク（ＶＰＮ）は、ＰＬＳＢネットワーク上にマッピングされることができ、トラフィックが特定の一意の関心に基づくコミュニティにのみ送られるように、一意のマルチキャスト・ツリーが、エッジ・ブリッジ（ｅｄｇｅ  ｂｒｉｄｇｅ）毎のＶＰＮ毎にマッピングされることを可能にする。マルチキャストＶＰＮトラフィックは、共通であるパスに対してインストールされるＶＰＮグループ・マルチキャスト・アドレスによって、ＶＰＮに参加しているブリッジにのみ配送される。
【００１５】
ネットワークは、（本発明の譲受人に譲渡された出願ＵＳ２００５０２２００９６で説明されるような）プロバイダ・バックボーン・トランスポート（Ｐｒｏｖｉｄｅｒ  Ｂａｃｋｂｏｎｅ  Ｔｒａｎｓｐｏｒｔ）、およびＰＬＳＢと組み合わされた８０２．１ａｈプロバイダ・バックボーン・ブリッジ（Ｐｒｏｖｉｄｅｒ  Ｂａｃｋｂｏｎｅ  Ｂｒｉｄｇｅ）などのその他の技術を利用することによって、拡大されることができる。ＰＢＢは、ＰＬＳＢ  ＷＡＮドメインおよびＰＬＳＢメトロ・ドメインなどのＰＬＳＢ領域を互いに結び付けるため、またはＰＢＴを使用して接続性を拡張するために使用されることができる。
【００１６】
したがって、本発明の一態様は、プロバイダ・リンク状態ブリッジング・イーサネット・ノードを提供し、そのノードは、少なくとも１つの関連するユニキャストＭＡＣアドレスと、少なくとも１つの関連するマルチキャストＭＡＣアドレスと、それぞれのユニキャストＭＡＣアドレスと同位ノードの複数のマルチキャストＭＡＣアドレスとに基づいてノード間でリンク状態ルーティング情報を交換するため、および同位ノード間の最短パス接続性を決定するためのルーティング・モジュールであって、多数の等コスト・パスが利用可能である場合、選択された最短パスが、ルーティング情報の交換に関係するすべてのブリッジに対して整合性のあるものとなるように決められる、ルーティング・モジュールと、ノードから同位ブリッジ・ノードへの接続性を識別するための、ルーティング・モジュールから受け取った転送情報が入力される転送情報ベース（ＦＩＢ）であって、ユニキャストＭＡＣアドレスは同位ノードを指し示し、マルチキャスト・アドレスは同位ノードから指し示すものである、転送情報ベース（ＦＩＢ）と、着信パケットを検査し、そのパケットが、送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するために、ＦＩＢによって決定された出口ポートとして使用されるポートと同じ入口ポートに到着したかどうかを判定するための逆方向パス転送チェック（ＲＰＦＣ）モジュールと、ノードの出口ポートが同位ブリッジの宛先ＭＡＣアドレスに関連付けられているかどうかをＦＩＢから決定し、パケットを転送するための転送モジュールとを含む。
【００１７】
本発明のさらなる態様は、メッシュ・ネットワーク内でプロバイダ・リンク状態ブリッジング・イーサネット・ノードを構成し、動作させる方法を提供し、その方法は、リンク状態情報を同位ノードと交換するステップであって、各ノードが、少なくとも１つの関連するユニキャストＭＡＣアドレスと、少なくとも１つのマルチキャストＭＡＣアドレスとを有するステップと、交換されたリンク状態情報に基づいて、同位ノードに到る最短パスを最短パス・アルゴリズムによって決定するステップであって、多数の等コスト・パスが利用可能である場合、選択された最短パスが、ルーティング情報交換に関係するすべてのブリッジに対して整合性のあるものとなるように決められるステップと、同位ノードを指し示す関連するユニキャストＭＡＣアドレスと、同位ノードから指し示すマルチキャストＭＡＣアドレスとを利用する決定された最短パスを転送情報ベース（ＦＩＢ）に入力するステップと、着信パケットの送信元ＭＡＣアドレスを検査し、そのパケットが、送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するために、ノードの出口ポートとして使用されるポートと同じ、ノードの入口ポートに到着したかどうかを判定することによって逆方向パス転送チェック（ＲＰＦＣ）を実行するステップであって、ＲＰＦＣが失敗した場合、パケットが廃棄されるステップと、ＲＰＦＣが成功した場合、ＦＩＢ内で識別されるパケットの宛先ＭＡＣに関連付けられたノードの出口ポートを介して、パケットを同位ブリッジに転送するステップとを含む。
【００１８】
また、本発明のさらなる態様は、イーサネット・ブリッジング・ネットワークを提供し、イーサネット・ブリッジング・ネットワークは、ネットワーク内の同位ブリッジに関する転送情報を含む転送情報ベース（ＦＩＢ）を各ブリッジが有する複数のブリッジであって、着信パケットが、着信パケットの送信元ＭＡＣアドレスと等しい宛先ＭＡＣアドレスをもつパケットを転送するためのブリッジの出口ポートとして使用されるポートと同じ、ブリッジの入口ポートに到着したかどうかを判定するために、逆方向パス転送チェック（ＲＰＦＣ）を各ブリッジが実行することが可能な、複数のブリッジと、ブリッジを相互接続し、メッシュ・ネットワークを形成する複数のパスとを含み、ＦＩＢは、複数のブリッジ間で交換されたリンク状態情報に基づいてデータ入力され、同位ブリッジ間の最短パスを決定するために使用され、選択されるパスの決定は、多数の等コスト・パスが利用可能である場合、同位ブリッジに対して整合性のあるものとなるように決められる。
【００１９】
本発明のその他の態様および特徴は、本発明の特定の実施形態についての以下の説明を添付の図面と併せて検討することで、当業者に明らかになるであろう。
【００２０】
本発明のさらなる特徴および利点は、以下の詳細な説明を添付の図面と併せて理解することから明らかとなるであろう。
【発明を実施するための最良の形態】
【００２１】
添付の図面の全体で、同様の特徴は同様の参照番号によって識別されることに留意されたい。
【００２２】
本発明の実施形態が、図２〜図９を参照しながら、以下で例としてのみ説明される。本発明は、ループ・フリーなイーサネット・ネットワーキングのためのシステム、方法、および装置を提供する。
【００２３】
プロバイダ・リンク状態ブリッジング（ＰＬＳＢ）は、ループ・フリーな最短パス転送とともに、ネットワーク・キャパシティのより効率的な使用を提供することによって、イーサネット・ネットワークが、ＬＡＮ空間からからＷＡＮまたはプロバイダ・ネットワーク空間に拡大されることを可能にする。透過ブリッジングと組み合わされたスパニング・ツリー・プロトコル（ＳＴＰ）を使用することによって各ノードにおいて学習されたネットワーク図を利用する代わりに、ＰＬＳＢベースのネットワークでは、メッシュ・ネットワークを形成するブリッジは、ネットワーク・トポロジの同期が取られた見取図を有する。これは、リンク状態ルーティング・システムのよく理解されたメカニズムを通して達成される。ネットワーク内のブリッジは、ネットワーク・トポロジの同期が取られた見取図を有し、必要なユニキャストおよびマルチキャスト接続性の知識を有し、ネットワーク内の任意の１対のブリッジ間の最短パス接続性を計算することができ、ネットワークの計算された見取図に従って個別に転送情報ベース（ＦＩＢ）にデータを入力することができる。すべてのノードが、同期が取られた見取図におけるその役割を計算し、そのＦＩＢにデータを入力した場合、ネットワークは、１組の同位ブリッジからある任意のブリッジに到るループ・フリーなユニキャスト・ツリーと、ある任意のブリッジから同じ１組の同位ブリッジに到る合同かつループ・フリーなポイント・ツー・マルチポイント（ｐ２ｍｐ）マルチキャスト・ツリーとを有する。その結果、あるブリッジ対の間のパスは、スパニング・ツリーのルート・ブリッジの移動に制約されず、全体的な結果は、メッシュの接続性の広さをより良く利用することができる。
【００２４】
ＰＬＳＢは、イーサネット・ブリッジ接続性の同等物を提供するが、これをフラッディングおよび学習の代わりにＦＩＢの構成によって達成する。そのようなものとして、ＰＬＳＢは、Ｂ−ＭＡＣ（バックボーンＭＡＣ）の転送を構成し、ＰＢＢアダプテーション機能をごくわずか変更した、プロバイダ・バックボーン・ブリッジ（ＰＢＢ）またはＭＡＣ−ｉｎ−ＭＡＣと呼ばれるＩＥＥＥ（電気電子技術者協会）８０２．１ａｈドラフト規格など、新たに出現した規格によって使用されることができ、クライアント・イーサネットがＰＬＳＢネットワークによって提供される接続性を変更なく利用し得るように、クライアント・ブロードキャスト挙動をＰＬＳＢマルチキャストにマッピングする。
【００２５】
ＰＬＳＢ動作は、仮想ＬＡＮ（ＶＬＡＮ）の使用によるネットワークのパーティショニングを介して、その他のコントロール・プレーンまたは透過ブリッジングと組み合わされることができる。ＶＬＡＮ  ＩＤが、コントロール・プレーン・レベルでメッシュの１つのインスタンスを定義するために使用されることができ、ＰＬＳＢの場合、これは、分散リンク状態ルーティング・システムによって駆動される。ネットワーク機能のＶＬＡＮパーティショニングが使用される場合、ＰＬＳＢは、本発明の譲受人に譲渡された２００４年４月４日に出願された米国特許出願第２００５０２２００９６号で開示されたようなプロバイダ・バックボーン・トランスポート（ＰＢＴ）など、その他のイーサネット・ネットワーク技術とサイド・バイ・サイド（ｓｉｄｅ−ｂｙ−ｓｉｄｅ）な互換性がある。
【００２６】
ＰＬＳＢは、任意の２つのブリッジ間の接続性が双方向で同じパスをたどるように、対称なメトリックを使用し、マルチキャストされるパケットとユニキャストされるパケットの間に転送の合同性が存在するように、ユニキャストおよびマルチキャスト接続性に対して共通のメトリックを使用する。イーサネット・クライアントをトランスポートするためにＰＬＳＢが使用される場合、これが望ましい以下のような多くの理由が存在する。
【００２７】
初期パケットがマルチキャスト・パス上でフラッディングされるフロー内ではパケットの並べ替えが可能でなく、ユニキャスト・パス上で転送を可能にするために、フローの最中に転送情報が学習される。
【００２８】
非対称な障害がループを引き起こし得る場合、スパニング・ツリーを利用するクライアントに関する知られた問題に対処するために、はるかに高い確率の障害が対称的である。
【００２９】
クライアントＩＥＥＥ８０２．１ａｇマルチキャスト接続性障害管理（ＣＦＭ：Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｆａｕｌｔ  Ｍａｎａｇｅｍｅｎｔ）パケットの転送とＰＬＳＢネットワークを介した対応するユニキャスト・パスの合同性。
【００３０】
ＰＬＳＢレイヤＣＦＭパケットの同様の合同性。
【００３１】
対称なメトリックは、等しい「行き」および「戻り」トランスポート遅延をもたらし、それが、ネットワーク内でタイミング情報を広めるためのレイヤ２クロック分配方式の有効性および堅牢性を大幅に改善する。
【００３２】
以下の説明でより詳細に説明されるように、イーサネット・クライアントのサービス要件とは独立に、対称なメトリックは、ループ抑制も容易にする。
【００３３】
ＰＬＳＢは、透過ＬＡＮサービスを使用することができるＣ−ＭＡＣ（カスタマＭＡＣ）レイヤまたはその他のレイヤ・ネットワークに透過ＬＡＮサービスを提供するために、ＭＡＣ構成を使用して、１組の（わずかに変更された）８０２．１ａｈプロバイダ・バックボーン・ブリッジの間の最短パスのループ・フリーな（ユニキャストおよびマルチキャスト双方の目的のため）接続性を構成する。これは、関連するＶＬＡＮ、およびルーティング・システム公示上でのＭＡＣ情報のピギーバッキングのため、ＳＴＰの代わりに、プロバイダ・バックボーン・ブリッジ・ネットワーク内でリンク状態ルーティング・プロトコルの動作を必要とする。
【００３４】
トランジット・ブリッジは、ユニキャストまたはマルチキャスト接続性を終了させる必要がない場合、ＭＡＣ情報を提供せず、その他のブリッジからのＭＡＣアドレス公示を処理することを選択することができる。８０２．１ａｈの場合、プロバイダ・バックボーン・ブリッジ（ＰＢＢ）として知られるエッジ・ブリッジは、ほぼ常にＭＡＣ情報を提供するが、純粋にトランジット・ブリッジは提供しない。
【００３５】
少なくとも２つのＭＡＣアドレスが、各ブリッジに関連付けられ、１つはブリッジへのユニキャスト転送用、少なくとも１つはブリッジからのマルチキャスト転送用である。ユニキャストＭＡＣは、ブリッジにパケットを送信する場合に、パケットの宛先アドレスとして、同位ブリッジによって使用され、ブリッジからその同位ブリッジへのユニキャストまたはマルチキャスト・トラフィックの送信元としてブリッジを識別する。マルチキャスト・アドレスは、多数の同位ブリッジに同時にトラフィックを送信する場合に、ブリッジによって使用され、ルーティング・システムによって構成された特定のマルチキャスト・ツリーを識別する。マルチキャスト・ツリーは、ＰＬＳＢドメイン内のすべてのブリッジにパケットを配送するように構成されることができ、したがって、特定の送信元ブリッジのためのブロードキャスト機能を実施する。マルチキャスト・ツリーは、特定の関心に基づくコミュニティ、一般にクライアント・レイヤＶＰＮに属するブリッジにのみ配送を制限するために、任意選択的にブロードキャスト・ツリーの限定的なサブセットを識別することができる。
【００３６】
ＰＬＳＢは、構成された情報を利用し、与えられたメッシュ・ネットワーク内のすべてのセグメントを使用可能にするので、透過ブリッジングに関連するフラッディングは、必要とされず、望ましくない。したがって、ＰＬＳＢ挙動に割り当てられたＶＬＡＮパーティションはどれも、透過ブリッジングのためのものとは異なる「未知の」宛先ＭＡＣアドレスを有するパケットを扱うために変更された転送挙動も持たなければならない。ＰＬＳＢの場合、未知の宛先アドレスを有するパケットは、黙って廃棄される。
【００３７】
図２ａは、ＰＬＳＢを利用するネットワークの概略図である。共用ネットワーク・トポロジから、各ノードは、最短パス・アルゴリズムを使用して、ネットワーク内のその他のプロバイダ・バックボーン・ブリッジ（ＰＢＢ）またはノードに到る最適最短パスを計算する。ネットワーク全体に対する最短パスの適用の結果、およびブリッジ内のＦＩＢへの対応するデータ入力が、各ブリッジからネットワークのメンバ・ブリッジに到るメッシュ経由の一意のツリーを提供する。例えば、図２ａの装置Ａからの最短パスを使用して計算されたマルチキャスト・ツリーは、特にＳＴＰのようにルート・スイッチ選出が存在しない点で、図１に示されたスパニング・ツリーとは異なる。図２ａに示されるように、最短パス・アルゴリズムの利用は、装置Ａから発信されたパケットが、隣接ブリッジ１２０、１１６へのより直接的な経路を進むことを可能にするが、ＳＴＰを使用すると、最短パス経路は、図１に示されたように、使用不能にされることがある。
【００３８】
フラッディングおよび学習の透過ブリッジング動作は、ＰＬＳＢを実施する８０２．１ａｈ  ＰＢＢによって、ＰＬＳＢ上にマッピングされることができる。例えば、クライアント装置Ｂのロケーションが、ＰＬＳＢネットワークのブリッジ１１０に知られていない場合、ＡからＢに宛てたパケットは、そのブリッジに割り当てられたグループ・アドレスを使用するブリッジ１１０によって、マルチキャスト・パケット内にＭＡＣ−ｉｎ−ＭＡＣカプセル化され、ブリッジ１１０の送信元アドレスを有する。マルチキャスト・メッセージは、ＰＬＳＢを介してネットワークを横断し、コピーは最終的にノード１２２に到着し、そこでＭＡＣ−ｉｎ−ＭＡＣカプセル化が解除され、コピーが装置Ｂに転送される。ブリッジ１２２のＭＡＣ−ｉｎ−ＭＡＣ透過ブリッジング機能は、ＭＡＣ−ｉｎ−ＭＡＣカプセル化内の送信元Ｂ−ＭＡＣアドレスを観察し、Ａに到達するには、ブリッジ１１０を経由すべきであることを連想する。装置Ｂは、その後、メッセージに応答するとき、「Ａ」に宛てたメッセージをブリッジ１２２に送信する。ブリッジ１２２は、ＡのＭＡＣ−ｉｎ−ＭＡＣ宛先がブリッジ１１０であることに気づき、ブリッジ１１０に宛てたユニキャスト・パケット内にメッセージをラップする。パケットは、ブリッジ１１２を介してブリッジ１１０に送信され、その後、ブリッジ１１０は、ＭＡＣ−ｉｎ−ＭＡＣカプセル化を解除し、装置Ａに到達するための正しいポート上にパケットを転送する。同様に、ブリッジ１１０は、ＰＬＳＢネットワーク内でＢに到達するには、ブリッジ１２２を経由することを観察する。装置Ａから装置Ｂおよび装置Ｂから装置Ａに送信される将来のメッセージはどれも、ＰＬＳＢネットワークを介した学習されたユニキャスト転送を今では使用することができる。
【００３９】
各ブリッジのユニキャストおよびマルチキャスト・ツリーは、合同であることが必要とされ、これは、対称リンク・メトリックの使用の直接の結果である。等コストの多数のパスに遭遇した場合、パスの共通ランク付けを達成する分散手段が必要とされ、これは多くの潜在的な解決策を有するよく理解された問題である。１つの典型的な解決策は、等コストのパスが分かれ、合流する２つのブリッジを識別し、最高のブリッジ番号を選択し、等コスト・パス・セグメント上に最高の番号の隣接ブリッジを有するそのブリッジからの／へのパスを選択することである。その他の方法は、当業者には明らかであろう。任意の２つのブリッジ間のランク付けされた最短パスは対称であり、そのため、任意の２つのブリッジ間のユニキャストおよびマルチキャスト転送の合同性が達成される。
【００４０】
与えられたブリッジについて、それが与えられたブリッジ対の間の最短パス上にあるかどうかを決定する場合、様々な最短パス・アルゴリズムが、最適パスを計算するために使用されることができる。フロイドのアルゴリズム［Ｒ．Ｆｌｏｙｄ：Ａｌｇｏｒｉｔｈｍ  ９７（ｓｈｏｒｔｅｓｔ  ｐａｔｈ）、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、７：３４５、１９６２］、またはダイクストラのアルゴリズム［Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ：Ａ  ｎｏｔｅ  ｏｎ  ｔｗｏ  ｐｒｏｂｌｅｍｓ  ｉｎ  ｃｏｎｎｅｘｉｏｎ  ｗｉｔｈ  ｇｒａｐｈｓ、Ｎｕｍｅｒｉｃａｌ  Ｍａｔｈｅｍａｔｉｃｓ、１：２６９−２７１、１９５９］など、グラフ・ベースのアルゴリズムが、同位ノード間の最短パスを計算するために、ＰＬＳＢブリッジ内で実施されることができる。任意の適切な最短パス・アルゴリズムも利用され得ることを理解されたい。フロイドのアルゴリズムは、コスト行列から距離行列を計算し、一方、ダイクストラのアルゴリズムは、頂点から他のすべての頂点までの最短距離を計算する。ツリーの数は基本的なフロイドのアルゴリズムの計算量に影響を与えないことに留意されたい。アルゴリズムは、パスがルート・ブリッジ・パスから延びる必要がない点で、ＳＴＰアルゴリズムとは異なるパス図を生成する。ＳＴＰは、すべての可能なパスについて使用されるより制約的な「ツリー」構造を生成し、一方、最短パス法は、同様に経路選択によって制限されない。
【００４１】
最短パス・アルゴリズムは、トラフィック工学情報を考慮するように変更されることができる。例えば、最短パスは、キャパシティ、速度、使用量、およびアベイラビリティなどのコストの尺度を含むことができる。ブリッジ間での送信元ＭＡＣの保存は、実際のトラフィック行列が観察され、ルーティング・システムへの入力として使用され、リンク負荷当たりの標準偏差を最小化し、負荷バランシングを容易にし得ること意味する。最短パス・アルゴリズムの副作用は、現在ノードよりも宛先に近いことが知られているネクスト・ホップに対する一般に認められた業界用語である、「ループ・フリーな代替（ｌｏｏｐ−ｆｒｅｅ  ａｌｔｅｒｎａｔｅ）」が、コネクションレス高速経路変更のために、ネットワーク接続性を計算する一部として計算され得ることであることも留意されたい。
【００４２】
図２ｂに示されるように、装置Ｂからブリッジ１２２を見る場合、最短パス・アルゴリズムから得られるツリーは、図２ａに示された装置Ａからブリッジ１１０を見た場合のツリーとは異なる。装置Ｂからのトラフィックは、接続ブリッジ１２２からの最短パスによってその宛先に到着することができ、生成されたツリーは、ブリッジから見て一意であることができる。各ブリッジから一意のツリーは、ネットワーク・リンクの効果的な利用を可能にする。しかし、２つの装置（ＡおよびＢ）の間のパスまたは関連するブリッジは対称であり、したがって、各方向で同じである。
【００４３】
再び図２ａを参照すると、いずれかの地点でネットワーク上にリンクの障害が存在する場合、例えば、ブリッジ１１６とブリッジ１１８の間のリンクが障害を起こした場合、唯一の影響は、そのリンクを通過するトラフィックに対するものである。障害はルーティング・システムによって公示され、最短パス・アルゴリズムが実行される。この時点で、唯一の変更は、障害リンクを通過していたパスに対するものであり、影響のない最短パスは変化しない。正味の結果は、新しいＦＩＢが旧いＦＩＢと大部分は同じであることであり、影響のないパス上でのパケットの転送には実質的な影響がないことを暗示している。図２ｂを参照すると、ブリッジ１１６とブリッジ１１８の間のリンクにおける障害は、最短パスの一部ではないので、ルーティング・ツリーに影響を与えない。本発明の範囲外にある、障害シナリオにおいて実行される計算を最小化する技法が存在することは、当業者であれば理解されよう。上記の説明は、トポロジ変更の通知の受信、新しい転送テーブルの計算、およびＦＩＢへのデータ入力など、ルーティング・システムのアクションを説明する場合の最も単純なケースを解説したに過ぎない。
【００４４】
ブリッジに関連付けられたＭＡＣアドレス（ユニキャストおよびマルチキャスト）は、リンク状態制御イーサネット・サブネットワークに対してグローバルであり、宛先ベースの転送用に使用される。これは、ルーティング・システム公示において、それらが単純にフラッディングされ得ること、ルーティング・システムの局所収束時に、それらがルーティング・システムによって指示されたように局所ブリッジ転送データベース（またはＦＩＢ）内でインスタンス化され得ることを意味する。このように、レイヤ２接続性の分散計算は、接続性をトポロジと関連付けために異なるシグナリング・システムを必要とせずに、イーサネット・ブリッジに適用されることができる。その最も単純な形態では、ブリッジは、それが２つの与えられたブリッジ・ノード間の最短パス上にあることを計算した場合、それらのブリッジに関連付けられたＭＡＣアドレスをＦＩＢ内に単にインストールし、ユニキャストＭＡＣアドレスは、対象ブリッジの各々を指し示し、マルチキャストＭＡＣアドレスは、対象ブリッジから指し示す。さらなる改良は、ブリッジが２つのノード間の最短パス上にある場合、それらが関心に基づくコミュニティの共通部分を有するならば、ブリッジが転送テーブルに入力されるデータをしかるべく変更し得ることをブリッジが決定するように、関心に基づくコミュニティ情報をルーティング公示に追加することを含むことができる。
【００４５】
一意のメッシュが、ＰＬＳＢメカニズムを使用して、ＶＬＡＮ毎に構成されることができる。通常は単一のメッシュで十分であるが、等しいパスの場合、等コスト・パスが利用され得るようにトラフィックを拡散することが望ましいことがある。接続性の多数の置換が必要とされる場合（例えば、等コスト・パスの効率的な利用）、これは、依然として単一のルーティング・プロトコル・インスタンスを使用しながら、２つ以上のＶＬＡＮをＰＬＳＢ動作に委任することによって達成されることができる。最短パスを計算する場合、各ＶＬＡＮについて動作が繰り返されながら、均衡を破るために異なるランク付けアルゴリズムを各ＶＬＡＮに割り当て、このモードの動作に委任されたＶＬＡＮの集まりの間でエッジにおける負荷分散を行う。追加のＭＡＣアドレスは、それらの機能はエンド・ポイントを明白に識別することなので、必要とされず、ＶＬＡＮは、経路選択のためのランク付けアルゴリズムを決定する。
【００４６】
ブリッジ毎に単一のユニキャストＭＡＣアドレスが説明されたが、何ものもより細かい粒度の使用を排除せず、ユニキャストＭＡＣアドレスは、ライン・カード、仮想スイッチ・インスタンス（ＶＳＩ）、またはＵＮＩポートに関係し得ることを理解されたい。これは、宛先ブリッジにおけるフローのデマルチプレキシングを簡単にするために望ましいことがある。
【００４７】
（トポロジ変更から、ルーティング・システムによるネットワーク内のすべてのブリッジへのトポロジ変更の公示、新しいトポロジの共通見取図への再収束および転送情報の対応する更新までの期間である）不安定な期間の間、（潜在的に悪化した形態であっても）接続性を維持するために、ループ抑制が、ネットワークにおいて必要とされる。分散システムの不安定性はしばしば、少なくとも一時的にネットワークの全体的な見取図が同期していないことを意味する。
【００４８】
イーサネット・アドレシングは、フラットおよび非アグリゲータブル（ｎｏｎ−ａｇｇｒｅｇａｔｅａｂｌｅ）であり、これは単一のルーティング・ドメインを暗示し、そのため、一時的なユニキャスト・ループは局所的で、相対的に無害であり、永続的なユニキャスト・ループおよびすべてのマルチキャスト・ループのみが対処される必要がある。メトリックは、ユニキャストおよびマルチキャスト転送用とも対称的で共通であるので、その場合、各方向における最短パスは、ユニキャストおよびマルチキャスト・パスとも任意の２つの装置間で同じである。それが同じである場合、収束したネットワークでは、各ブリッジは、与えられた送信元ＭＡＣを予期すべきインターフェースを知っており、それは、ＦＩＢでは、それを指し示すようにＭＡＣが構成されるポートは、戻りパスだからである。パケットの送信元アドレスは、ユニキャストおよびマルチキャスト・パケットで共通であり、それは、送信者のユニキャスト送信元アドレスであることにさらに留意されたい。
【００４９】
どの分散システムでも、トポロジ変更に関連して、一時的なループが発生する。まれに、実装エラーまたはハードウェア問題の結果として、永続的なループも発生し得る。これは、構成または方針問題のために多数のルーティング・ドメインを含むネットワークの場合にも当てはまるが、ＰＬＳＢでは、（ルーティング・ドメインの同位メッシュに対して）単一のドメインまたは限定的な階層のみが考えられる。いくつかのノードはネットワークについての情報を知っており、他のノードは知らない場合に、ループが形成される。これは、必ずしもすべてのノードが同時に収束していないことをしばしば意味する、ネットワーク情報の伝播遅延のために発生する。分散ルーティングが機能するためには、最終的にすべての健全なノードが同期が取られた見取図を有し、共通の結果を計算するという仮定が存在する。
【００５０】
先に言及されたように、任意の２つのノード間の最短パスが双方向で同じになるように、対称メトリックが使用される。リンク状態ルーティングによって転送データベースの構成と組み合わされた場合、逆方向パス転送チェック（ＲＰＦＣ）と呼ばれるものを実行することによって、パケットが予期されたインターフェース上で受信されたかどうか（与えられた送信元からの到着のセグメントがその送信元への最短パス上のセグメントに一致するかどうか）の検査となるように、従来のＭＡＣ学習手順が変更されることを可能にする、十分な情報が転送データベース内に存在する。これは、ポートをブロックする必要なく、または他にネットワーク接続性を大幅に妨げる必要なく、ループ・フリー性のパケット毎の検査を可能にする。これは、ＳＴＰを使用せずに、ループ・フリーな任意対任意（ａｎｙ−ｔｏ−ａｎｙ）のイーサネット接続性を生成する。
【００５１】
ブリッジは、パケットに含まれる送信元ＭＡＣアドレスおよびパケットが到着したセグメントと、転送データベース内で宛先としてのその同じＭＡＣアドレスのために構成されたものとの比較に基づいて、パケット上で健全性チェックを実行する。ＲＰＦＣ監視（ＲＰＦＣ  ｐｏｌｉｃｉｎｇ）が使用可能にされている場合、送信元ＭＡＣアドレスの学習されたセグメントが静的エントリを変更するならば、または静的エントリが存在しないならば、パケットは廃棄される。例えば、図２ａを参照すると、ブリッジ１１０の送信元ＭＡＣを有するパケットが、ブリッジ１１４、１１８、１２０、１２２、または１２４へのその他の接続リンクに関連付けられたポートを介してブリッジ１１２に到着した場合、ポートはブリッジ１１０の送信元ＭＡＣに関連付けられたエントリを持たないので、パケットは廃棄される。ＲＰＦＣは、サブネットワーク内におけるリンク状態ルーティング・システムのバグのない一貫した実施を想定する。
【００５２】
先に言及されたように、正しく収束したネットワークは、ネットワーク内の任意のブリッジ対の間に１つの双方向最短パスを有する。ＰＬＳＢルーティングは、定義によって、リンクの両方向に「等しい重み」を割り当てる。使用可能にされたＲＰＦＣを用いると、ブリッジＡからブリッジＢに到達するパケットは、両方向についてのすべての中間ノードの正しい収束の論理「ＡＮＤ」である。正しくないまたは収束しないパスに遭遇したパケットはどれも、ループする可能性を取るのではなく、廃棄される。
【００５３】
図３は、ネットワーク内でループ形成がどのように生じ得るかについての概略図である。例は、ステップ３０１において、作業システムが装置Ｂから装置Ａおよび装置Ａから装置Ｂに転送を行うことから開始する。ステップ３０２に示されるように、可能な一時的ループを開始するには、例えば、ノードＹから装置Ａへのリンクが障害を起こしていなければならず、かつ装置Ａがループ上でデュアル・ホーム（ｄｕａｌ−ｈｏｍｅｄ）でなければならず、そのため、ノードＹは、第２のリンクを介してパケットを配送しようとし続ける。ＰＬＳＢネットワーク内でのループの生成は、ループ抑制メカニズムが何らかの障害を起こしたことを仮定する。
【００５４】
ステップ３０３に示されるように、ブリッジＺにおいてループを進め続けるには、ブリッジＺが、ブリッジＹに到る最短パスは、ブリッジＺからブリッジＹ、またはブリッジＺから装置Ａとだけ矛盾のない、ブリッジＹからブリッジＺに直接進むことを決定した、ブリッジＹへの向きとは正反対の、ブリッジＸを経由する時計回りであると信じなければならない。
【００５５】
ブリッジＸにおいてループを進め続けるには、ステップ３０４に示されるように、第２の障害が存在しなければならない。しかし、ＲＰＦＣが利用される場合、順方向および逆方向におけるループが同時に必要とされる。順方向におけるループを概念的に想像することは容易であるが、両方向での発生を想像することはあまり容易ではない。ループは、２つの装置間の最短パスに固有である。そのため、特定のＭＡＣアドレスに対するループは、そのアドレスへのすべてのトラフィックがループすることを意味せず、戻りパスも合同なループ内に存在するトラフィックのみがループすることを意味する。
【００５６】
保証されるループ・フリー性は、直観的な略式の証明によって確証されることができる。ループ上で２つの逆循環方向は、同時に存在することができず、そのような転送構成を生成する条件は、１つの方向でループを生成する条件がミラーされた場合、本質的に自己矛盾を有する。ＲＰＦＣは、ループが順方向および逆方向の両方で合同であることを要求する。直観的な証明の核心は、健全なシステムでは、これが両方向について同時に成り立たないことである。パス上の与えられたノード対の間に現在の作動パスよりも短いパスが存在するためには、リンクまたはリソースが追加される必要があり、それの知識は、実際に形成されたループの単一の方向に制限される必要がある。追加されるリソースについての知識は、ＲＰＦＣが本質的に自己矛盾となることを覆すためには、同時に（両方向で）対称であることが必要とされる。
【００５７】
障害の組合せまたは不健全な実施が実際にループを形成した場合、ひとたび形成されると、さらなるトラフィックはそのループに入ることができず、その結果、パケットは複製地点に到着しなければ出ることができないという特性を、ループが有することにも留意されたい。図４に例示的に示されるように、ループ４０２が多数のブリッジ間で形成された場合、ＲＰＦＣのため、ループ内のパケットの唯一の有効な送信元は、ループ自体である。ループするパケットは、ループ内にすでに捕らえられたパケットに制限される。ループの外部のブリッジであるノード４０４、４０６、４０８、４１０からのトラフィックは、ループに入ることができない。これは、形成されるとしても、単純なループのみが形成され得ることを意味する。ループは与えられた送信元アドレスの有効な送信元として２つ以上のインターフェースを受け入れることは不可能であるので、重複パケットは元のフローに再合流することができない。
【００５８】
したがって、ＲＰＦＣは、（ＴＴＬまたはポート・ブロッキングに対して）ループ・フリー性のパケット毎の監視を実行するループ防止メカニズムとして利用されることができる。ループは送信元／宛先の対に対して存在しなければならないので、ループの粒度が著しく制限されることに留意することも重要である。
【００５９】
ＲＰＦＣは、イーサネット・パケットには変更を必要とせず、ブリッジの実装には最低限の変更しか必要としないという利点を有する。予期せぬインターフェースに到着するパケットにはその他の原因も存在し得るので、ＲＰＦＣは積極的な監視であり、したがって、それを選択的な状況において利用しなくてもよい能力が望ましい。ＰＬＳＢマルチキャストは、（例えば、ＶＬＡＮにおけるフラッディングとは反対に）もっぱらイーサネットＭＡＣアドレスに基づいている。イーサネット・マルチキャストＭＡＣアドレスは、独特な監視処理がユニキャストまたはマルチキャスト・パケットに適用されることを可能にする、明示的なマルチキャスト表示を宛先ＭＡＣアドレス上に含む（ＰＢＴと同様に、未知パケットのフラッディングは禁止されることに留意されたい）。構成されたユニキャスト転送の場合、ループが解消する時まで、またはバッファリング容量が限界を超え、受信された追加のトラフィックが廃棄されるようになる時まで、ネットワークはループ内のパケットを単にバッファリングするので、一時的なループは破局的ではない。これは、一時的なループは害がなく、複製を行わないので（ネットワークはループが解消されるまで単にバッファリングする）、ネットワーク収束の間、ループ抑制はオフにされることができ、ネットワークが安定したとき、どのような永続的なループも即座に抑制するために、ユニキャスト抑制が再びオンにされることを意味する。
【００６０】
（トラフィックの廃棄によって検出される）永続的なループ状態が存在するかどうかをチェックするために、単にユニキャスト用のＲＰＦＣを定期的に使用可能にし、存在しない場合、再びオフにするなど、その他の戦略も考えられ得る。ループ形成の結果は、マルチキャスト・トラフィックの場合は著しく異なり、一時的なループは、無制限な複製をもたらすことができ、したがって、マルチキャスト宛先ＭＡＣアドレスを有するパケットに対しては、ＲＰＦＣは決して使用不能にされない。マルチキャストの場合、非収束マルチキャスト転送がパケットを積極的に廃棄し、ループを防止するように、ループ抑制は常にオンにしておくべきである。
【００６１】
トポロジ変更によって影響されないツリーは、ＦＩＢに対する変更がなく、またはトポロジ変更に関連しないそれらの関連パスには不安定性がないので、正常に機能し続けるが、変更によって影響されるツリーは、ＲＰＦＣが非収束マルチキャスト・パスに関するパケットを廃棄するので、接続性の中断を経験することがある。ネットワーク全体に関して、これは、サービスの一時的な「低下（ｂｒｏｗｎ  ｏｕｔ）」に似ている。学習されたエントリは、構成されたエントリに取って代わることはなく、そのため、監視の使用可能／使用不能が、ルーティング・システムによってインスタンス化された構成の改悪をもたらすことはない。
【００６２】
図５は、ＰＬＳＢを実施するためのブリッジ・ノード５００の可能な実装の概略図である。ルーティング・システム・モジュール５０２は、リンク状態プロトコル・ルーティングを使用して、ネットワーク・トポロジに関する情報を、ネットワーク内の同位ブリッジと交換する。先に説明されたように、情報の交換は、ブリッジが、ネットワーク・トポロジの同期の取れた見取図を生成することを可能にし、その後、同期の取れた見取図は、ルーティング・システム５０２モジュールが、収束の最中に（上で説明されたアルゴリズムを使用して）最短パス・ツリーを計算することを可能にする。ＦＩＢ５０４は、決定されたパスに基づいてネットワークを介してトラフィックを送るのに適切なエントリを入力される。ＲＰＦＣ送信元チェック・モジュール５０６は、着信パケットを処理し、受信ポートが特定の送信元ＭＡＣ用のＦＩＢ５０４内で識別されたポートと一致するかどうかを決定するために、ＦＩＢ５０４内で検索を実行する。受信ポート／送信元ＭＡＣが、予想ポート／送信元ＭＡＣと一致しない場合、パケットは廃棄される。同様に、ルーティング・システム５０２が、送信元チェック５０６に対して、ネットワークが収束プロセス中であることを識別した場合、ユニキャストに関するループ抑制は使用不能にされる。ネットワークが収束した場合、ユニキャスト・パケットに関するループ抑制は再び使用可能にされる。マルチキャスト宛先アドレスによって識別されるマルチキャスト・パケットの場合、収束の最中、ＲＰＦＣ送信元チェック５０６は決して使用不能にされない。パケットがＲＰＦＣ送信元チェック５０６モジュールに合格した場合、またはチェックが使用不能にされている場合、宛先検索５０８モジュールは、どのポートからパケットが宛先ユニキャストまたはマルチキャストＭＡＣアドレスに転送されるべきかを、ＦＩＢ５０４から決定する。有効なエントリが存在しない場合、パケットは廃棄される。ブリッジがネットワークのエッジにある場合、発信パケットの転送の前に、パケットのＭＡＣ−ｉｎ−ＭＡＣカプセル化が、一意ユニキャストおよびマルチキャスト・アドレスを利用して行われることがある（図示されず）。説明されたモジュールは、例示的な目的のものに過ぎず、当業者であれば理解されるように、ブリッジ・ノードのモジュールの間で機能を結合または分散することによって実施されてよいことも理解されたい。
【００６３】
図６は、動作のためにＰＬＳＢブリッジ５００を構成する方法の一実施形態を示している。ステップ６０２において、ブリッジまたはリンク障害などのネットワーク・トポロジ変更が発生した場合、ステップ６０４において、状態情報が、ルーティング・システム・モジュール５０２によって、ネットワーク内のブリッジ間で交換される。ルーティング・システム・モジュール５０２は、トポロジ情報をブリッジ内蔵のデータベース内に保存することによって、ネットワーク構成の同期の取れた見取図を作り上げる。その後、ステップ６０６において、ブリッジは、先に説明されたような最短パス・アルゴリズムを使用して、同位ブリッジ間の最短パスを決定することができる。その後、ステップ６０８において、ＦＩＢ５０４は、接続性を可能にする適切なルーティング・エントリを入力される。その後、パケットは、ブリッジによって処理されることができる。ネットワーク・トポロジ変更が発生した場合、プロセスが再び開始される。
【００６４】
図７は、受信パケットを処理するブリッジ・ノード５００の一実施形態を示している。ステップ７０２において、パケットがブリッジのポートで受信される。ステップ７０４において、パケットがマルチキャスト・パケットか、それともユニキャスト・パケットかを決定するために、宛先アドレスが使用される。パケットがユニキャストであり（ステップ７０４においてＹＥＳ）、ルーティング・システムが収束している場合、したがって、ＲＰＦＣが使用可能であり（ステップ７０６においてＹＥＳ）、ステップ７０８において、ＲＰＦＣが実行される。ＲＰＦＣが成功した場合（ステップ７０８においてＹＥＳ）、すなわち、パケットが関連送信元ＭＡＣアドレスの予想ポートに到着した場合、ステップ７１０において、宛先ＭＡＣ用の発信ポートのＦＩＢ内における検索が行われる。ＲＰＦＣが使用可能でない場合（ステップ７０６においてＮＯ）、すなわち、ループ状態が存在し、ネットワークが収束していない場合、ＲＰＦＣはバイパスされ、ステップ７１０において、パケットを転送するための検索が直接行われる。関連ＭＡＣアドレス用のエントリが存在する場合（ステップ７１０においてＹＥＳ）、ステップ７１４において、パケットはその宛先に転送される。ＲＰＦＣが成功しなかった場合（ステップ７０８においてＮＯ）、すなわち、パケットが送信元アドレスに基づいた予想ポートに到着しなかった場合、ステップ７１２において、パケットは廃棄される。同様に、パケットが適切なエントリを持たない場合（ステップ７１０においてＮＯ）、ステップ７１２において、パケットは廃棄される。
【００６５】
パケットがマルチキャスト・パケットである場合（ステップ７０４においてＮＯ）、ＲＰＦＣは常に使用可能であり、ステップ７０８において、ＲＰＦＣが実行される。ＲＰＦＣが成功した場合（ステップ７０８においてＹＥＳ）、すなわち、パケットが関連ＭＡＣアドレスの予想ポートに到着した場合、ステップ７１０において、宛先ＭＡＣ用の発信ポートのＦＩＢ内における検索が行われる。関連ＭＡＣアドレス用のエントリが存在する場合（ステップ７１０においてＹＥＳ）、ステップ７１４において、パケットはその宛先に転送される。ＲＰＦＣが成功しなかった場合（ステップ７０８においてＮＯ）、すなわち、パケットが送信元アドレスに基づいた予想ポートに到着しなかった場合、ステップ７１２において、パケットは廃棄される。同様に、パケットが適切なエントリを持たない場合（ステップ７１０においてＮＯ）、ステップ７１２において、パケットは廃棄される。先に言及されたように、（トラフィックの廃棄によって検出される）永続的なループ状態が存在するかどうかをチェックするために、ユニキャスト用のＲＰＦＣは、定期的に使用可能にされることができ、存在しない場合、再びオフにされる。
【００６６】
これまで、単一の関心に基づくコミュニティをサポートするプロバイダ・リンク状態ブリッジ・ネットワークが説明されたが、ポートのサブセット、したがってＰＬＳＢネットワーク内のブリッジのサブセットに対する接続性のみを個々の関心に基づくコミュニティが必要とする、多数の関心に基づくコミュニティをサポートすることも可能である。必要とされるのは、関心に基づくコミュニティに関係するブリッジの組に制約されたマルチキャスト接続性および共有のユニキャスト接続性と、与えられたパケットを関心に基づくコミュニティに関連付けるためのメカニズムである。ＩＥＥＥ８０２．１ａｈのＩ−ＳＩＤ（拡張サービスＩＤ）フィールドは、パケットを関心に基づくコミュニティに関連付けるメカニズムの一例である。関心に基づくコミュニティ識別子（例えばＩ−ＳＩＤ）は、ノードがＩ−ＳＩＤで識別される関心に基づくコミュニティの関心事を識別することができ、最終的に、各ブリッジが一意グループ・マルチキャスト・アドレスを公示された各Ｉ−ＳＩＤに関連付けるように、ルーティング・システム公示内に含まれることもできる。２つのブリッジ間の最短パス上に自らを見出したブリッジは、各ブリッジに関連付けられたユニキャストＭＡＣアドレスと、２つのブリッジに共通するすべてのＩ−ＳＩＤに関するマルチキャストＭＡＣアドレスとをインストールする。これの結果は、与えられたエッジ・ブリッジが、すべての同位ブリッジへのユニキャスト接続性と、Ｉ−ＳＩＤで識別される各関心に基づくコミュニティに特有のマルチキャスト接続性とを有することである。これは、各同位ノードへのマルチポイント・ツー・ポイント（ｍｐ２ｐ）ユニキャスト・ツリーのリーフである形態、および（Ｓ，Ｇ）ポイント・ツー・マルチポイント（ｐ２ｍｐ）マルチキャスト・ツリーのルートである形態をとり、ここで、Ｓは送信元のアドレスであり、Ｇは各関心に基づくコミュニティの１組の同位ノードに対するマルチキャスト・グループ・アドレスである。ブリッジ対が共通のＩ−ＳＩＤを持たない場合、さらなる改良は、ユニットＭＡＣアドレスがインストールされないこととすることができる。同様に、ブリッジ対は、トランジット・ブリッジとすることができ、ノードによって終了または開始されるフローにどのようなＭＡＣアドレスも提供しないことを選択することができる。このように、マルチキャスト接続性は、特定の関心事グループに限定されるばかりでなく、この手法は、ユニキャスト接続性のための転送テーブル空間の消費も節約する。
【００６７】
図８は、仮想プライベート・ネットワーク（ＶＰＮ）がＰＬＳＢネットワーク上にどのようにマッピングされることができ、エッジ・ブリッジ毎のＶＰＮ毎に一意のマルチキャスト・ツリーがマッピングされることを可能にするかを示している。マルチキャストＶＰＮシナリオでは、マルチキャスト・トラフィックは、ＶＰＮに参加するブリッジにのみ配送される。ＶＰＮグループ・マルチキャスト・アドレスが、共通なパスについてインストールされる。４つのＶＰＮネットワークが、Ｖ１、Ｖ２、Ｖ３、Ｖ４として識別されている。多数のＶＰＮが、ブリッジ１１０などのブリッジからホストされることができ、個々のＶＰＮエンド装置とすることができる。例えばＶ１およびＶ３などの各ＶＰＮについて、一意のユニキャスト・ツリーが生成される。対応するＶＰＮの端点を含むブリッジへの唯一の経路が識別される。例えば、Ｖ１に関するルーティング・ツリーの場合、ブリッジ１１６へのパスと、ブリッジ１１２を介するブリッジ１２２およびブリッジ１２４へのパスが必要とされる。同様に、Ｖ３に関するルーティング・ツリーの場合、ブリッジ１１２へのパスと、その先のブリッジ１１８およびブリッジ１２４へのパスが必要とされる。これは、Ｖ１からのＶＰＮトラフィックが、ＶＰＮ  Ｖ１およびＶＰＮ  Ｖ３エンド装置をホストしないブリッジに配送される可能性を排除する。各ＶＰＮは、最短パス・アルゴリズムに基づいて、ＶＰＮに特有のエッジ・ブリッジ毎のツリーを有することができる。
【００６８】
ＶＰＮを定義する能力と同様に、非対称接続性が構成されることができる。通常、ＰＬＳＢは、（＊，Ｇ）マルチキャスト接続性を生成し、Ｓがグループ「Ｇ」内の送信元を示す（Ｓ，Ｇ）マルチキャスト・ツリーの完全メッシュのように、＊はすべての送信元を意味し、Ｇはマルチキャスト・グループを表す。与えられたサービス・インスタンスが（Ｓ，Ｇ）への接続性に制限されることが望ましいこともある。これは、与えられたマルチキャスト・グループの送信元、送信先、または送信元と送信先の両方のどれであることを望むかを示すアトリビュートを公示に追加することによって、マルチキャストについて容易に達成されることができる。２つの他のブリッジ間の最短パス上にあることを確定したブリッジは、送信元／送信先アトリビュートを使用して、どのマルチキャスト・グループ・アドレスがインストールされるべきかを決定する。より複雑な接続性は、異なるアトリビュート構成を用いてこの例を繰り返すことによって構成されることができる。例えば、ともに２つのＶＰＮに参加する、ネットワーク内の装置の２つの組を想定することができる。方針の問題として、接続性は、組間（ｉｎｔｅｒ−ｓｅｔ）でのみ許可され、組内（ｉｎｔｒａ−ｓｅｔ）では許可されない（実際の具体例は、本社オフィス／支社オフィス接続性である）。そのため、第１のＶＰＮは、組Ａのための送信元アトリビュートと、組Ｂのための送信先アトリビュートとを有する。第２のＶＰＮは、組Ａのための送信先アトリビュートと、組Ｂのための送信元アトリビュートとを有する。透過ブリッジング・オーバーレイが考えられる場合、そのような制限を課すことは、組Ａからの未知のフラッディングが組Ｂに、組Ｂからの未知のフラッディングが組Ａに制限されることを意味する。したがって、２つの組は、決して組内接続性を学習することはできず、組Ａの装置は、組Ｂとのみ通信を行い、組Ｂの装置は、組Ａとのみ通信を行う。
【００６９】
図９に示されるように、ネットワークは、（本発明の譲受人に譲渡された出願ＵＳ２００５０２２００９６で説明されるような）ＰＢＴ、および８０２．１ａｈ  ＰＢＢなどのその他の技術を利用して拡大されることができる。ＰＢＢ９０４は、ＰＬＳＢ  ＷＡＮドメイン９０２およびＰＬＳＢメトロ・ドメイン９０６などのＰＬＳＢエリアを互いに結びつけるため、またはＰＢＴ９０８を使用して接続性を拡張するために、エリア境界ルータ（ＡＢＲ：Ａｒｅａ  Ｂｏｒｄｅｒ  Ｒｏｕｔｅｒ）の緩やかな同等物として使用されることができる。エリア境界におけるクライアント情報の検査は、同位エリアが、隣接エリアのルーティング・システムにおいて単一のＭＡＣアドレスとして単純にモデル化されること、または同位エリアには単一のＢ−ＭＡＣとして見えるＰＢＴファンイン・ドメイン（ｆａｎ−ｉｎ  ｄｏｍａｉｎ）と相互動作することを可能にし、これらの技術のどちらかが、要約を提供する。ドメイン間のループ・フリー性を保証するため、ネットワークは、ドメインの厳格な階層であり、ルーティング・ドメインのメッシュは、サポートされることができない。
【００７０】
ネットワークの遠端において、送信元学習が、ポートＩＤのための送信元Ｂ−ＭＡＣダブリング（ｓｏｕｒｃｅ  Ｂ−ＭＡＣ  ｄｏｕｂｌｉｎｇ）を用いて動作する仕方と同じようにして、与えられたＣ−ＭＡＣのための送信元Ｂ−ＭＡＣが知られる。この手順は、リンク状態ブリッジングを用いて動作するようにわずかに変更される。Ｃ−ＭＡＣとＢ−ＭＡＣの対応を学習する手順は、変更されない。Ｃ−ＭＡＣに対するＢ−ＭＡＣが学習されていない場合、関心に基づくコミュニティ（典型的にはクライアントＶＰＮ）に適したブリッジのマルチキャスト・アドレスが使用され、これが、Ｃ−ＭＡＣブロードキャストのＰＬＳＢ空間において必要とされるエミュレーションを提供する。
【００７１】
ＰＬＳＢは、スパニング・ツリー・プロトコルの不利な側面の大部分が除去された、ＭＡＣ−ｉｎ−ＭＡＣブリッジ・ネットワークを提供する。これは、メッシュ接続性のはるかに良い利用をもたらし、各装置がリンク状態データベースを有するので、はるかに速い収束をもたらす。ユニキャスト接続性は、ネットワークの再収束の最中に中断されない。加えて、ＰＬＳＢは、（異なるＶＩＤ範囲を使用して）ＰＢＴと並列して動作する能力、または（ハブ実装において）ＰＢＴと連結されて動作する能力を提供し、イーサネット・アトリビュートは完全に保存されて、クライアント・レイヤに完璧なエミュレーションを提供する。
【００７２】
上で説明された本発明の実施形態は、単に説明的であることが意図されている。したがって、本発明の範囲は、添付の特許請求の範囲によってのみ限定されることが意図されている。
【図面の簡単な説明】
【００７３】
【図１】スパニング・ツリー・プロトコル（ＳＴＰ）を使用するメッシュ・ネットワークの概略図である。
【図２ａ】装置Ａから示されたＰＬＳＢを実施するメッシュ・ネットワークの概略図である。
【図２ｂ】装置Ｂから示されたＰＬＳＢを実施するメッシュ・ネットワークの概略図である。
【図３】パケット・ループ・シナリオの概略図である。
【図４】収束中のポート・ブロッキングの概略図である。
【図５】ＰＬＳＢブリッジの概略図である。
【図６】ＰＬＳＢブリッジを構成するための方法のフローチャートである。
【図７】ＰＬＳＢブリッジを動作させるための方法のフローチャートである。
【図８】ＰＬＳＢを使用するＶＰＮオーバーレイの概略図である。
【図９】ハイブリッドＰＢＢおよびＰＢＴネットワークと組み合わされたＰＬＳＢのネットワーク図である。
【図１】
2009510953.tif 000003
【図２ａ】
2009510953.tif 000004
【図２ｂ】
2009510953.tif 000005
【図３】
2009510953.tif 000006
【図４】
2009510953.tif 000007
【図５】
2009510953.tif 000008
【図６】
2009510953.tif 000009
【図７】
2009510953.tif 000010
【図８】
2009510953.tif 000011
【図９】
2009510953.tif 000012
【国際調査報告】
2009510953.tif 000013
2009510953.tif 000014
2009510953.tif 000015