(57)【特許請求の範囲】
【請求項１】
最短パスブリッジングを利用するデータパケットネットワークバックボーンにおいて負荷のバランシングを容易にするための方法であって、
前記ネットワークバックボーンの入口ノードにおいて、１つ以上のクライアントフレームを受信することと、
各クライアントフレームについてのフローオフセット値を、当該クライアントフレームの内容の関数として計算することと、
前記フローオフセット値は、Ｎ個の所定の値の１つであることと、Ｎは、当該クライアントフレームについての前記入口ノードからバックボーン宛て先ＭＡＣアドレスへの候補パスの最大の数を定義することと、
各クライアントフレームに、バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、を付加することと、
当該Ｂ−ＶＩＤは、所定のＢ−ＶＩＤ基礎値及び当該クライアントフレームについての前記フローオフセット値の関数であることと、
各クライアントフレームを、当該クライアントフレームについての前記Ｂ−ＶＩＤ及び前記バックボーン宛て先ＭＡＣアドレスに従って転送することと、
を含む方法。
【請求項２】
前記フローオフセット値を計算することは、前記クライアントフレーム内のインターネットプロトコルヘッダの関数として前記フローオフセット値を生成することを含む、請求項１の方法。
【請求項３】
前記インターネットプロトコルヘッダの関数として前記フローオフセット値を生成することは、前記インターネットプロトコルヘッダのハッシュを計算することと、計算された前記ハッシュを前記Ｎ個の所定の値の１つへマッピングすることと、を含む、請求項２の方法。
【請求項４】
計算された前記ハッシュを前記Ｎ個の所定の値の１つへマッピングすることは、前記ハッシュをＮで割ったモジュロ剰余として前記フローオフセット値を計算することを含み、前記Ｂ−ＶＩＤは、前記所定のＢ−ＶＩＤ基礎値と前記フローオフセット値との和である、請求項３の方法。
【請求項５】
前記フローオフセット値を計算することは、前記クライアントフレームについてのソースＭＡＣアドレスと、前記クライアントフレームについてのバックボーン宛て先ＭＡＣアドレス又はクライアント宛て先ＭＡＣアドレスのいずれかとの関数として、前記フローオフセット値を生成すること、を含む、請求項１の方法。
【請求項６】
前記入口ノードにおいて受信される２つ以上のクライアントフレームの各々について、
当該クライアントフレーム内にインターネットプロトコルヘッダが存在するかを判定することと、
前記インターネットプロトコルヘッダが存在するという判定に応じて、当該インターネットプロトコルヘッダの関数としてフローオフセット値を生成することと、
そうではなくインターネットプロトコルヘッダが存在しないという判定に応じて、当該クライアントフレームについてのソースＭＡＣアドレスと、当該クライアントフレームについてのバックボーン宛て先ＭＡＣアドレス又はクライアント宛て先ＭＡＣアドレスのいずれかとの関数として、前記フローオフセット値を生成することと、
をさらに含む、請求項１の方法。
【請求項７】
最短パスブリッジングネットワークにおける使用のためのネットワークノードであって、
１つ以上のクライアントネットワーク又はデバイス及び前記最短パスブリッジングネットワーク内の１つ以上の他のノードへ前記ネットワークノードを接続するように構成されるネットワークインタフェースユニットと、
前記ネットワークインタフェースユニットを介して１つ以上のクライアントフレームを受信し、
各クライアントフレームについてのフローオフセット値を、当該クライアントフレームの内容の関数として計算し、
各クライアントフレームに、バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、を付加し、
各クライアントフレームを、前記ネットワークインタフェースユニットを介して、当該クライアントフレームについての前記Ｂ−ＶＩＤ及びバックボーン宛て先ＭＡＣアドレスに従って転送する、
ように構成される処理回路と、
を備え、
前記フローオフセット値は、Ｎ個の所定の値の１つであり、
Ｎは、当該クライアントフレームについての入口ノードから前記バックボーン宛て先ＭＡＣアドレスへの候補パスの最大の数を定義し、
前記Ｂ−ＶＩＤは、所定のＢ−ＶＩＤ基礎値及び当該クライアントフレームについての前記フローオフセット値の関数である、
ネットワークノード。
【請求項８】
前記処理回路は、前記クライアントフレーム内のインターネットプロトコルヘッダの関数として、前記フローオフセット値を計算するように構成される、請求項７のネットワークノード。
【請求項９】
前記処理回路は、前記インターネットプロトコルヘッダのハッシュを計算し、計算された前記ハッシュを前記Ｎ個の所定の値の１つへマッピングすることにより、前記インターネットプロトコルヘッダの関数として前記フローオフセット値を計算するように構成される、請求項８のネットワークノード。
【請求項１０】
前記処理回路は、前記ハッシュをＮで割ったモジュロ剰余として前記フローオフセット値を計算することにより、計算された前記ハッシュを前記Ｎ個の所定の値の１つへマッピングするように構成され、前記Ｂ−ＶＩＤは、前記所定のＢ−ＶＩＤ基礎値と前記フローオフセット値との和である、請求項９のネットワークノード。
【請求項１１】
前記処理回路は、前記クライアントフレームについてのソースＭＡＣアドレスと、前記クライアントフレームについてのバックボーン宛て先ＭＡＣアドレス又はクライアント宛て先ＭＡＣアドレスのいずれかとの関数として、前記フローオフセット値を生成することにより、前記フローオフセット値を計算するように構成される、請求項７のネットワークノード。
【請求項１２】
前記処理回路は、前記入口ノードにおいて受信される２つ以上のクライアントフレームの各々について、
当該クライアントフレーム内にインターネットプロトコルヘッダが存在するかを判定し、
前記インターネットプロトコルヘッダが存在するという判定に応じて、当該インターネットプロトコルヘッダの関数としてフローオフセット値を生成し、
そうではなくインターネットプロトコルヘッダが存在しないという判定に応じて、当該クライアントフレームについてのソースＭＡＣアドレスと、当該クライアントフレームについてのバックボーン宛て先ＭＡＣアドレス又はクライアント宛て先ＭＡＣアドレスのいずれかとの関数として、前記フローオフセット値を生成する、
ようにさらに構成される、請求項７のネットワークノード。
【請求項１３】
最短パスブリッジングを利用するデータパケットネットワークバックボーンにおいて負荷のバランシングを容易にするための、ネットワークノードにおける方法であって、
複数のバックボーン宛て先ＭＡＣアドレスの各々について、
当該バックボーン宛て先ＭＡＣアドレスに対応する等コストのネクストホップの数を判定することと、
バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、の所定のセットからの各Ｂ−ＶＩＤを、当該Ｂ−ＶＩＤ及び前記等コストのネクストホップの数の関数として、ネクストホップインタフェースへマッピングすることと、
前記所定のセット内のＢ−ＶＩＤの数は、前記等コストのネクストホップの数を上回ることと、
バックボーン宛て先ＭＡＣアドレスとＢ−ＶＩＤとの各組合せに対応するエントリであって、前記Ｂ−ＶＩＤへマッピングされた前記ネクストホップインタフェースについての識別子を含む当該エントリで、転送データベースを形成することと、
を含む方法。
【請求項１４】
Ｂ−ＶＩＤの前記所定のセットは、所定の範囲のＢ−ＶＩＤを含み、
各Ｂ−ＶＩＤをネクストホップインタフェースへマッピングすることは、
当該Ｂ−ＶＩＤから所定のＢ−ＶＩＤ基礎値を減算して、フローオフセット値を取得することと、
インタフェースオフセット値を、前記等コストのネクストホップの数を法とする前記フローオフセット値の剰余として計算することと、
前記インタフェースオフセット値に対応する前記ネクストホップインタフェースへ当該Ｂ−ＶＩＤをマッピングすることと、
を含む、請求項１３の方法。
【請求項１５】
Ｂ−ＶＩＤの前記所定のセットは、複数の範囲のＢ−ＶＩＤを含み、
Ｂ−ＶＩＤの各範囲は、前記ネクストホップインタフェースの１つへマッピングされる、
請求項１３の方法。
【請求項１６】
最短パスブリッジングネットワークにおける使用のためのネットワークノードであって、
前記最短パスブリッジングネットワーク内の１つ以上の他のノードへ前記ネットワークノードを接続するように構成されるネットワークインタフェースユニットと、
複数のバックボーン宛て先ＭＡＣアドレスの各々について、
当該バックボーン宛て先ＭＡＣアドレスに対応する等コストのネクストホップの数を判定し、
バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、の所定のセットからの各Ｂ−ＶＩＤを、当該Ｂ−ＶＩＤ及び前記等コストのネクストホップの数の関数として、ネクストホップインタフェースへマッピングし、
バックボーン宛て先ＭＡＣアドレスとＢ−ＶＩＤとの各組合せに対応するエントリであって、前記Ｂ−ＶＩＤへマッピングされた前記ネクストホップインタフェースについての識別子を含む当該エントリで、転送データベースを形成する、
ように構成される処理回路と、
を備え、
前記所定のセット内のＢ−ＶＩＤの数は、前記等コストのネクストホップの数を上回る、
ネットワークノード。
【請求項１７】
Ｂ−ＶＩＤの前記所定のセットは、所定の範囲のＢ−ＶＩＤを含み、
前記処理回路は、各Ｂ−ＶＩＤを、
当該Ｂ−ＶＩＤから所定のＢ−ＶＩＤ基礎値を減算して、フローオフセット値を取得し、
インタフェースオフセット値を、前記等コストのネクストホップの数を法とする前記フローオフセット値の剰余として計算し、
前記インタフェースオフセット値に対応する前記ネクストホップインタフェースへ当該Ｂ−ＶＩＤをマッピングする、
ことにより、ネクストホップインタフェースへマッピングする、
請求項１６のネットワークノード。
【請求項１８】
Ｂ−ＶＩＤの前記所定のセットは、複数の範囲のＢ−ＶＩＤを含み、
前記処理回路は、Ｂ−ＶＩＤの各範囲を、前記ネクストホップインタフェースの１つへマッピングするように構成される、
請求項１６のネットワークノード。
【請求項１９】
データパケットネットワークにおいてデータフレームを転送するための方法であって、
バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、及びバックボーン宛て先ＭＡＣアドレスでラベリングされたデータフレームを受信することと、
前記バックボーン宛て先ＭＡＣアドレスに関連付けて記憶されている等コストのネクストホップの識別子のセットから、前記Ｂ−ＶＩＤの関数として、ネクストホップの識別子を選択することと、
選択された前記ネクストホップの識別子に対応するネクストホップインタフェースを介して、前記データフレームを転送することと、
を含む方法。
【請求項２０】
前記ネクストホップの識別子を選択することは、前記Ｂ−ＶＩＤ及びノード固有のシード値の関数として、疑似ランダム数を計算することと、前記疑似ランダム数の関数として、等コストのネクストホップの識別子の前記セットから前記ネクストホップの識別子を選択することと、を含む、請求項１９の方法。
【請求項２１】
最短パスブリッジングネットワークにおける使用のためのネットワークノードであって、
前記最短パスブリッジングネットワーク内の１つ以上の他のノードへ前記ネットワークノードを接続するように構成されるネットワークインタフェースユニットと、
バックボーン仮想ＬＡＮ識別子、Ｂ−ＶＩＤ、及びバックボーン宛て先ＭＡＣアドレスでラベリングされたデータフレームを、前記ネットワークインタフェースユニットを介して受信し、
前記バックボーン宛て先ＭＡＣアドレスに関連付けて記憶されている等コストのネクストホップの識別子のセットから、前記Ｂ−ＶＩＤの関数として、ネクストホップの識別子を選択し、
選択された前記ネクストホップの識別子に対応するネクストホップインタフェースを介して、前記データフレームを転送する、
ように構成される処理回路と、
を備えるネットワークノード。
【請求項２２】
前記処理回路は、前記Ｂ−ＶＩＤ及びノード固有のシード値の関数として、疑似ランダム数を計算し、前記疑似ランダム数の関数として、等コストのネクストホップの識別子の前記セットから前記ネクストホップの識別子を選択する、ことにより前記ネクストホップの識別子を選択するように構成される、請求項２１のネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
本出願は、米国特許法第１１９条（ｅ）の下で、２０１０年１０月２９日に提出された仮特許出願第６１／４０８，０３７号の優先権を主張し、また、米国特許法第１１９条（ｅ）の下で、２０１１年１月６日に提出された仮特許出願第６１／４３０，２８１号の優先権を主張する。上述した仮出願の各々の全ての内容は、参照によりここに取り入れられる。
【０００２】
本発明は、一般に、データ通信ネットワークに関し、具体的には、最短パスブリッジングを利用するデータパケットネットワークバックボーンにおける負荷バランシングを容易にするための技術に関する。
【背景技術】
【０００３】
負荷の分配（distribution）又は負荷の分散（spreading）は、データ通信の帯域幅をより効率的に利用し及びネットワーク内で全体としての性能を改善するための方法である。より具体的には、等コストマルチパス（ＥＣＭＰ：equal-cost  multi-path）は、ルーティングされるネットワークにおいてユニキャストトラフィックの負荷分散のための１つのありがちな戦略である。ＥＣＭＰを利用することができるのは、所与の宛て先へパケットをいかに転送するかに関する決定を、ネットワーク横断的な計算を実行する際に最短（又は最小コスト）となるパスとそれぞれ同点である複数の“等コストな”パスの任意のものについて解決することのできる状況である。ＥＣＭＰは、単一のルータにとってローカルであるホップ別の決定に依拠しており、中間ノードごとの完全な転送テーブルを前提としているため、ほとんどのユニキャストルーティングプロトコル及びサポートすることを要求されるデータプレーンのハードウェアを備えるノードと併せて、使用されることができる。ネットワーク内の所与のノードにおいてＥＣＭＰが使用される際、当該ノードからのトラフィックは、等コストのネクストホップのセットにわたって疑似均等的に分割される。このプロセスは、ネットワークの各ホップにおいて独立的に実装され、所与の宛て先に対して１つより多くのパスが存在する。
【０００４】
多くの実装において、複数の等コストなネクストホップの存在に遭遇する地点ごとに、各パケットは例えばＩＰ（Internet  Protocol）ヘッダなどの一様化のソース（source  of  entropy）について検査され、ヘッダ情報のハッシュを使用して特定のパケットについてネクストホップが選択される。高度に統合されたトラフィックについては、この方法は、平均すると、規則的なトポロジー（即ち、対称的なトポロジー）において負荷を均等的に分配し、規則性の少ないトポロジーにおいていくらかの改善をもたらす。
【０００５】
最短パスブリッジング（ＳＰＢ）についてのＩＥＥＥ（Institute  of  Electrical  and  Electronics  Engineers）８０２．１ａｑ標準は、イーサネットネットワークのアーキテクチャにおけるフルメッシュの最短パスの接続性の構築を可能とするために開発されてきた。ＳＰＢは、複数の制御プロトコルを、ＩＳ−ＩＳ（intermediate  system  to  intermediate  system）プロトコルによってサポートされる単一のリンクステートルーティングシステムに集約する。このシステムを統合的かつ合同的な（congruent）ユニキャスト及びマルチキャスト転送の計算のために使用して、基本的なイーサネットＬＡＮの接続性が構築される。
【０００６】
８０２．１ａｑをサポートするものを含むイーサネットネットワークのアーキテクチャは、上で議論したホップ別のマルチパス転送のアプローチをサポートしない。このサポートの欠落は、ユニキャスト及びマルチキャストのトラフィックの間の合同性のニーズの結果であり、マルチキャストが一般的にＥＣＭＰに適合しないことを理由とする。従って、ＳＰＢをサポートするイーサネットネットワークにおいて負荷をバランシングするための改善された技術が必要とされる。
【発明の概要】
【０００７】
本発明の複数の実施形態において、最短パスブリッジングネットワークのエッジにおいて、当該ネットワークに入るクライアントフレームに付加するためのフローラベルを決定するために、フロー分類プロセスが使用される。特定の出口ノードへネットワークを横断するクライアントフレームに、複数のフローラベルのいずれかを割り当てることができるため、当該フローラベルは、複数の等コストパスの中の選択のために転送ノードにより使用され得る。複数の実施形態において、フローラベルは、当該フローラベルの選択をランダム化するための一様化のソースを提供するクライアントフレームの内容の関数として計算される。この一様化ソースは、いくつかの実施形態において、当該クライアントフレーム内のＩＰ（Internet  Protocol）ヘッダを含み、但し、他のケースでは、例えば当該フレームの宛て先ＭＡＣアドレス及びソースＭＡＣアドレスなどの他のクライアントフレームの内容を含んでよい。いくつかの実施形態において、利用可能であればＩＰヘッダが一様化のソースとして使用され、そうでなければ宛て先ＭＡＣアドレス／ソースＭＡＣアドレスのペアが使用される。
【０００８】
ここで開示される技法のいくつかの実施形態において、転送プロセスは、従来型のイーサネットルーティングと類似しており、宛て先アドレス及びフローラベルでインデックス付けされた転送データベース内のネクストホップインタフェースをルックアップすることを含む。このアプローチの変形例において、転送データベースは、対応するネクストホップインタフェースのセットにペアリングされる宛て先アドレスを含み、転送プロセスは、フローラベルに基づく計算を用いてネクストホップインタフェースの１つを選択することを含み、いくつかの実施形態では、さらにノード固有のシード値にも基づく。
【０００９】
最短パスブリッジングを利用するデータパケットネットワークバックボーンにおいて負荷のバランシングを容易にするための１つの例示的な方法は、上記ネットワークバックボーンの入口ノードにおける１つ以上のクライアントフレームの受信で開始される。各クライアントフレームについて、フローオフセット値が、当該クライアントフレームの内容の関数として計算される；このフローオフセット値は、Ｎ個の所定の値の１つであり、Ｎは、当該クライアントフレームについての入口ノードから宛て先ＭＡＣアドレスへの候補パス（possible  paths）の最大の数を定義する。上記方法は、各クライアントフレームに、バックボーン仮想ＬＡＮ識別子（Ｂ−ＶＩＤ）を付加することに続き、当該Ｂ−ＶＩＤは、所定のＢ−ＶＩＤ基礎値及び当該クライアントフレームについての上記フローオフセット値の関数である。そして、クライアントフレームは、当該クライアントフレームについての上記Ｂ−ＶＩＤ及びバックボーン宛て先ＭＡＣアドレスに従って転送される。
【００１０】
いくつかのケースにおいて、上記フローオフセット値は、クライアントフレーム内のインターネットプロトコルヘッダの関数として生成される。例えば、上記フローオフセット値は、上記インターネットプロトコルヘッダのハッシュを計算し、計算された上記ハッシュをＮ個の所定の値の１つへマッピングすることによって生成され得る。いくつかの実施形態において、このマッピングは、上記ハッシュをＮで割ったモジュロ剰余（modulo  remainder）として上記フローオフセット値を計算することを含んでよく、上記Ｂ−ＶＩＤは、所定のＢ−ＶＩＤ基礎値と上記フローオフセット値との和である。
【００１１】
いくつかのケースにおいて、上記フローオフセット値は、クライアントフレームについてのソースＭＡＣアドレスと、当該クライアントフレームについてのクライアント宛て先ＭＡＣアドレス又はバックボーン宛て先ＭＡＣアドレスのいずれかと、の関数として生成され得る。また別のケースでは、上記方法は、まずクライアントフレーム内にインターネットプロトコルヘッダが存在するかを判定し、存在するならば当該インターネットプロトコルヘッダの関数としてフローオフセット値を生成し、そうではなくＩＰヘッダが存在しなければ、当該クライアントフレームについての宛て先ＭＡＣアドレス及びソースＭＡＣアドレスの関数として上記フローオフセット値を生成する、ことを含み得る。
【００１２】
他の例示的な方法は、ネットワークノードにおいて転送データベースを形成する（populate）ための技法を対象とする。当該方法によれば、バックボーン宛て先ＭＡＣアドレスに対応する等コストのネクストホップの数が判定される。バックボーン仮想ＬＡＮ識別子（Ｂ−ＶＩＤ）の所定のセットからの各Ｂ−ＶＩＤは、当該Ｂ−ＶＩＤ及び上記等コストのネクストホップの数の関数として、ネクストホップインタフェースへマッピングされる。最後に、転送データベースは、バックボーン宛て先ＭＡＣアドレスとＢ−ＶＩＤとの各組合せに対応するエントリであって、上記Ｂ−ＶＩＤへマッピングされたネクストホップインタフェースについての識別子を含む当該エントリで形成される。このプロセスは、ネットワークノードにとって既知のバックボーンの宛て先アドレスの各々について繰り返されてよい。
【００１３】
いくつかの実施形態において、Ｂ−ＶＩＤの所定のセットは、所定の範囲のＢ−ＶＩＤである。それら実施形態において、各Ｂ−ＶＩＤは、当該Ｂ−ＶＩＤから所定のＢ−ＶＩＤ基礎値を減算して、フローオフセット値を取得し、インタフェースオフセット値を、等コストのネクストホップの数を法とする上記フローオフセット値の剰余（modulo）として計算し、上記インタフェースオフセット値に対応するネクストホップインタフェースへ当該Ｂ−ＶＩＤをマッピングすることにより、ネクストホップインタフェースへマッピングされ得る。他の実施形態において、Ｂ−ＶＩＤの所定のセットは、複数の範囲のＢ−ＶＩＤを含み、Ｂ−ＶＩＤの各範囲は、上記ネクストホップインタフェースの１つへマッピングされる。
【００１４】
ネットワークノードにおいて転送データベースを形成するための上で要約した方法の他の変形例において、各宛て先ＭＡＣアドレスについて、等コストのネクストホップのセットが判定され、当該バックボーン宛て先ＭＡＣアドレスを対応する上記セット内の等コストのネクストホップの各々についての識別子へマッピングするエントリで転送データベースが形成される。転送データベースを形成するためのこの技法が使用される場合、転送ノードは、フレームを転送するための修正された技法を使用する。より具体的には、転送ノードは、バックボーン仮想ＬＡＮ識別子（Ｂ−ＶＩＤ）及びバックボーン宛て先ＭＡＣアドレスでラベリングされたデータフレームを受信し、当該宛て先ＭＡＣアドレスに関連付けて転送データベース内に記憶されている等コストのネクストホップの識別子のセットから、上記Ｂ−ＶＩＤの関数としてネクストホップの識別子を選択する。そして、当該ノードは、選択されたネクストホップの識別子に対応するネクストホップインタフェースを介して、データフレームを転送する。これら実施形態のいくつかにおいて、当該ノードは、上記Ｂ−ＶＩＤ及びノード固有のシード値の関数として、疑似ランダム数（pseudorandom  number）を計算し、この疑似ランダム数の関数として、等コストのネクストホップの識別子の上記セットからネクストホップの識別子を選択することにより、上記ネクストホップの識別子を選択する。
【００１５】
下で要約する方法に加えて、以下の詳細な説明におけるさらなる詳細において、複数の変形例が開示され及び説明される。それら方法の１つ以上を実行するように構成されるネットワークノードもまた説明される。よって、本発明は、上述した特徴及び利点に限定されない。実際、当業者は、以下の詳細な説明を読み、添付図面を見れば、追加的な特徴及び利点を認識するであろう。
【図面の簡単な説明】
【００１６】
【図１】ループを回避するためにスパニングツリーを使用するネットワークを示している。
【図２】最短パスブリッジングを使用するネットワークを示している。
【図３】クライアントフレームにフロー識別子を付加して最短パスブリッジングネットワーク内でそれらを転送するための一例としての方法を示すプロセスフロー図である。
【図４】フローラベルの一例としての計算の詳細を示すプロセスフロー図である。
【図５】クライアントフレームにフロー識別子を付加して最短パスブリッジングネットワーク内でそれらを転送するための他の例としての方法を示すプロセスフロー図である。。
【図６】ネットワークノードにおいて転送データベースを形成するための方法を示すプロセスフロー図である。
【図７】ネットワークノードにおいて転送データベースを形成するための他の方法を示すプロセスフロー図である。
【図８】最短パスブリッジングネットワーク内でデータパケットを転送するための方法を示すプロセスフロー図である。
【図９】本発明のいくつかの実施形態に従って構成される一例としてのネットワークノードのコンポーネントを示している。
【発明を実施するための形態】
【００１７】
以下の説明は、本発明のいくつかの実施形態を示しているものの、単に例示のやり方で与えられていることが理解されるべきである。以下の説明を読み添付図面を見ることで、当業者には、請求される本発明の範囲内の様々な変更及び修正が明らかとなるであろう。
【００１８】
ＩＥＥＥは、ネイティブなイーサネット基盤上の論理的なイーサネットネットワークを提供するために、最短パスブリッジングのための８０２．１ａｑ標準を開発した。８０２．１ａｑが有効化されたノード（ＳＰＢ機能を有するブリッジ）は、ＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）リンクステートプロトコルを用いて、ネットワークトポロジーと論理ネットワーク内のメンバーシップとを広告する。このよく理解されているルーティングプロトコルは、ネットワーク内のノードがノード間の最短パスを自動的に判定することを可能とする。実質的に、各ブリッジは、自身が知っているノードを他の全てのノードへ広告し、それによりネットワーク内の全てのブリッジが最終的にネットワークの同等のビューを有するようになる。そして、各ノードは、対象ノードまでの最短の（コストの最も小さい）ルートを計算し、当該最短パスにおけるネクストホップへ、フレームを転送することができる。
【００１９】
８０２．１ａｑ標準は、ＳＰＢの２つの変異形を記述している。ＳＰＢＶ（Shortest  Path  Bridging  -  VID）は、スパニングツリープロトコル（ＳＴＰ）と後方互換であり、マルチスパニングツリープロトコル（ＭＳＴＰ）の“リジョン（region）”の概念を使用し、概して、百個よりも少ないブリッジを有する小規模なＶＬＡＮ（Virtual  Local-Area  Networks）に適している。ＳＰＢＭ（Shortest  Path  Bridging  -  MAC）として知られる他の変異形は、千個程度のブリッジを有する大規模なプロバイダバックボーンブリッジを含む、キャリア級（carrier-grade）のアプリケーションのために設計されている。
【００２０】
ＳＰＢＭネットワークにおいて、接続されるイーサネットデバイスからネットワークのエッジにおいて受信されるユニキャストフレームは、ＭＡＣインＭＡＣというＩＥＥＥ８０２．１ａｈヘッダにカプセル化され、このヘッダを用いて、当該フレームがネットワークにわたってコアブリッジにより転送される。当該フレームが反対側でＳＰＢＭネットワークから退出する際、ＩＥＥＥ８０２．１ａｈヘッダは、取り外される。ネットワークのエッジにおいて、論理ネットワーク内のクライアントＭＡＣ（Ｃ−ＭＡＣ）アドレスのソースの学習が実行され、それにより、宛て先のクライアントへ最も近い出口ノード（egress  node）に向けて、バックボーンＭＡＣ（Ｂ−ＭＡＣ）アドレスへフレームが転送されるようになる。ＳＰＢブリッジについてのＢ−ＭＡＣアドレスは、制御プレーンによって配信され及び／又はアルゴリズムで構築され、Ｂ−ＭＡＣの学習の必要性は排除される。ＳＰＢＭは、対称的な最短パス上での全てのルーティングについてユニキャスト及びマルチキャストをサポートし、そのサポートは多くの等コスト最短パスについて提供される。
【００２１】
図１及び図２は、ＳＰＢの重要な利点の１つを示している。図１は、ネットワーク内のループを回避するためにＳＰＴに依存する、簡略的な３層（three-tier）のネットワーク１００を描いている。クライアント１１０によりサーバ１２０へ送信されるフレームは、入口ノード（ingress  node）１３０においてネットワークへ入り、コアネットワークノード１５０を介して出口ノード１４０へと、実線のリンクを通ってネットワークを横断する。実線のリンクは、クライアント１１０からサーバ１２０への、及びコアネットワークノード１５０を通ってアクセス可能な任意の他のクライアントノードへのただ１つのパスが存在するように、ネットワークノードの全てを横断する単一のパスを定義している。図１において破線で示されているネットワークノード間の代替的なリンクは、故障したリンクとの置換えが必要でなければ、無効化される。
【００２２】
対照的に、図２は、最短パスブリッジングを利用するネットワーク２００を示している。ここでは、クライアント１１０によりサーバ１２０へ送信されるフレームは、入口（エッジ）ノード２３０においてネットワークへ入るものの、ネットワーク１００において要する５つのホップよりもむしろ、出口（エッジ）ノード２４０へただ２つのホップでネットワークを横断することができる。このネットワークは、コアネットワークノード２５０の間のリンクの全てを利用することができ、フレームは最短パスの（コストの最も小さい）ルートを辿ることになる。これによって、ネットワーク内の輻輳が軽減され、ネットワークの性能及びキャパシティが改善される。
【００２３】
最短パスブリッジングの１つの利点は、閉塞点（choke  point）を排除することができるために、ネットワークトポロジーにわたってより均等に負荷が分配されるように、メッシュネットワークを形成することができることである。冗長的なリンクは、障害時まで待機しているのではなく、実際に使用される。改善された効率は、ネットワークの性能を維持し又は改善すらしつつ、１つ以上の層を取り除くことにより既存のネットワークをフラット化する可能性を提供する。
【００２４】
一方で、ＳＰＢネットワークは、トラフィック管理及びネットワークのトラブルシューティングを複雑化させる従来型のイーサネットネットワークよりも、ダイナミックである。さらに言えば、実際のネットワークにおける負荷バランシングは、非常に複雑であり得る。図２に示したネットワーク２００は、非常にシンプルである。より複雑なネットワークでは、より多くのブリッジが存在し、得られるリンクの全てが使用可能であるため、入口ノード２３０と出口ノード２４０との間にいくつもの（又は多数の）等コストなパスが存在し得る。よって、それら複数のパス上のネットワークトラフィックをバランシングするための効率的かつ柔軟な技術が必要とされる。
【００２５】
１つのアプローチの候補は、ＥＣＭＰ技術をＳＰＢＭに適合させることである。これは、利用可能な等コストのパスの間での選択について一様化のいくつかのソースのいずれかを使用して、多くの異なるやり方で行われることができる。１つの可能性は、等コストのパスの間の選択についての一様化のソースを提供するために、８０２．１１ａｈヘッダ内に含まれるＢ−ＭＡＣアドレス（ソースアドレス、Ｂ−ＳＡ、及び宛て先アドレス、Ｂ−ＤＡ）の組合せをハッシュ化することである。しかしながら、これは比較的劣悪な一様化のソースである。ある種のより良好な一様化のソースはＩ−ＳＩＤであり、さらに良い選択肢はＣ−ＭＡＣ  ＳＡ／ＤＡ情報をハッシュ化することだが、恐らく最良の選択肢は、存在するとすればＩＰ（Internet  Protocol）の５タプルをハッシュ化することである。一様化ソースのハッシュ化に基づくホップ選択は、ホップ別の原理で、即ち各転送ノードにおいて実行されることができ、又はブリッジングネットワークのエッジにおいて実行されることができる。後者のケースでは、結果として導かれる何らかの情報のトークンが、ハッシュを要約するためにデータパケット内で搬送される。
【００２６】
複数の等コストな転送インタフェースにわたってデータフローをランダム化するためのより高度な一様化ソースは、より良好な性能を提供する。よって、特にルーターがイーサネットで接続される場合、単一のソース／宛て先ルータＭＡＣアドレスのペアが非常に多用なＩＰ５タプルでパケットを送出するため、ＩＰペイロードのハッシュ化が最良の一様性を提供する。但し、ＩＰペイロードのホップごとのハッシュ化には、いくつかの理由で問題がある。第一に、このアプローチはレイヤ違反（layer  violation）である。第二に、このアプローチは、既存のイーサネットの技術のベースとの互換性がない。最後に、これは、ＯＡＭ（Operations  Administration  and  Management）プロトコルにとってネットワーク性能のデータを収集するためにＩＰパケットを擬装することを要するために、イーサネットのＯＡＭを不可能ではないとしても非常に困難にする。
【００２７】
ホップごとのハッシュ化に伴うこれら問題があるため、イーサネットのレイヤ固有のラベルにフローをエッジベースで割り当てることが、より良いアプローチである。このアプローチでは、既存のＯＡＭプロトコルを機能させることができ、レイヤ違反がエッジの適応化機能に限られ、全体的な技術ベースに要する変更は最小となる。
【００２８】
８０２．１ａｑにおいて現在文書化されているような、Ｂ−ＶＩＤで識別されるＥＣＴの複数のセットの使用は、フローラベルの１つのバリエーションであると見なすことができる。しかしながら、この技術には、リンクの利用効率の観点で制限がある。ＥＣＴセットの生成についての提案されている拡張は、パス選択の効率を改善するために計算的な技法を適用するが、ユニキャスト及びマルチキャストの対称的合同性（symmetric  congruence）の要件がパス選択の高い計算上の複雑性をもたらす。ＩＥＴＦ（Internet  Engineering  Task  Force）のＴＲＩＬＬ仕様は、ユニキャスト及びマルチキャストの技法の区別を含んでおり、その設計の一部としてユニキャストのＥＣＭＰを許容する。ＴＲＩＬＬは、計算上の複雑性を低減するために、マルチキャストについてはスパニングツリーを使用する。ＩＥＴＦのＰＷＥ仕様は、ＩＰｖ６標準においてもそうであるように、フローラベルとして見なすことのできる一様化ラベル（entropy  label）の概念を含んでいる。
【００２９】
ここで開示される本発明の技法は、対称合同性が緩和される場合にユニキャストの負荷分散のためにイーサネット技術で行い得ることの吟味に基づいている。この従来型の合同性の要件の緩和の下では、“行き”と“帰り”のパスは同じでなくてよい。さらに、ユニキャスト及びフラッディングされるフレームは、同じルーティングに追随しなくてもよい。下記から理解されるように、このアプローチは、ルーティング計算についての簡略化された計算及び簡略化されたタイブレーキング（tie-breaking）ルールの可能性の余地をもたらす。
【００３０】
既存のイーサネットデバイスへの全体的な変更を最小化するために、及びマルチキャストのためにＶＩＤを用いることも見据えて、ここで概説される技法は、バックボーン仮想ＬＡＮ識別子（Ｂ−ＶＩＤ）をユニキャストのフローラベルとして使用するであろう。より詳細には、ＳＰＢネットワークのエッジにおいてパケットに適用されるＢ−ＶＩＤフローラベルは、一様化ラベルに類似しているが、但しホップごとのハッシュ化のために使用されるわけではない。むしろ、エッジノードが、適切な一様化ソースをハッシュ化して、ユニキャストパケットのためのＢ−ＶＩＤフローラベルを生成する。ＳＰＢネットワークのコアノードは、Ｂ−ＶＩＤフローラベル及び宛て先Ｂ−ＭＡＣに基づいて、従来型の転送データベース（ＦＤＢ）を用いて簡単にパケットを転送することができる。
【００３１】
このアプローチを用いて、単一の論理ネットワークは、いくつかのＢ−ＶＩＤフローラベル値を使用するであろう。従って、このアプローチを実装するために、論理ネットワークのためのＢ−ＶＩＤベースのフローラベルの値の数と範囲とを合わせる手段が必要とされる。同様に、マルチキャストの動作にどのＢ−ＶＩＤが割り当てられるかを決定するための仕組みも必要である。８０２．１ａｑのために定義されたＩＳ−ＩＳ  Ｈｅｌｌｏについての既存のアルゴリズム交渉フレームワークは、この仕組みの基礎として供されることができる。留意すべき点として、この仕組みは、ＭＳＴＰ／ＳＶＬ（Multiple  Spanning  Tree  Protocol/Shared  VLAN  Learning）において行われるように、Ｂ−ＶＩＤの複数の範囲を使用することもできる。
【００３２】
この技法を採用するネットワークにおける通常のデータプレーンの構成は、８０２．１ａｑ又は８０２．１Ｑａｙにおいて仕様化されており、フローラベルとして使用される全てのＢ−ＶＩＤは全てのインタフェース上でブロックされない。ノードは、アルゴリズム及びトポロジーの情報を、既存の８０２．１ａｑ及びＩＳ−ＩＳの手続の通りに交換する。
【００３３】
ノードは、最短パスを計算している時、各ＤＡ−ＭＡＣ／Ｂ−ＶＩＤタプルについて一意なエントリが存在するように、転送データベース（ＦＤＢ）を形成（populate）する。一例としてのアルゴリズムは、予め定義される基礎値から始まるＢ−ＶＩＤの値の連続的な範囲の前提と共に開始される。ランダムプロセスとなるためにサポートされるものと不必要に相関付られることを回避するために、ノードは、インタフェースの選択に先立って、フローラベルにノード別のランダム値を組合せることを選択してもよい。ユニキャストのフローラベルのＢ−ＶＩＤの各々について、ノードは、等コストのネクストホップの数での、Ｂ−ＶＩＤの値（及び、可能であればノード別のランダム値）のモジュロ演算を実行する。その結果は、（等コストのインタフェースのうちの）ＦＤＢ内で宛て先ＭＡＣ／Ｂ−ＶＩＤタプルが指し示すことになるインタフェースを識別する。それに従ってＦＤＢが形成される。マルチキャストパケットは、このアプローチの下で別個にハンドリングされる。よって、ネットワークは、１つ以上のマルチキャスト配信ツリーを計算してそれらの各々をマルチキャストＢ−ＶＩＤに割り当ててもよく、それらはユニキャストについて使用されるＢ−ＶＩＤから区別される。
【００３４】
エッジノードでの振る舞いは、ある意味でより複雑である。クライアントフレームが受信されると、エッジノードは、当該フレームの内容を検査してある形式の“フロー分類（flow  classification）を実行し、これはフローラベルの数及び加算される基礎値でのモジュロの値をもたらし、ＳＰＢＭ適応の一部として当該パケットに適用されるべきフローラベルが選択される。ラベリングされたフレームを受信するコアノードは、単純にＦＤＢ内のＢ−ＤＡをルックアップし、Ｂ−ＶＩＤフローラベル及び当該Ｂ−ＤＡ転送エントリに関連付けられるネクストホップの数の関数として、ネクストホップインタフェースを選択することになる。
【００３５】
当業者は、ブロードキャストセグメントがユニキャストパケットの複製を引き起こさないことを保証するための技法が必要とされることを理解するであろう。転送ノードの振る舞いが修正されなければ、ブロードキャストセグメントに接続される送信者が当該セグメント上でブロードキャストされるフレームを受け取ることになる。わずかだがこれをハンドリングすることのできるやり方がある。第一に、重要な要件は、Ｂ−ＶＩＤ／ＤＡタプルについてブロードキャストセグメントからの出口がただ１つ存在するということである。１つの解決策は、ブロードキャストセグメント／疑似ノードに隣接するいずれかのノードが、ルーティングシステム内のブロードキャストセグメントを表現する疑似ノードのためのＳＰＦ（Shortest  Path  First）ツリーをも計算しなければならない、ということである。このアプローチによって、当該ノードは、上流のノードからのＤＡ／Ｂ−ＶＩＤタプルについての最短パス上に自身がいるかを判定し、それに応じて入口フィルタリングをセットアップすることができる。なお、ノードがローカルなランダム値をフロー選択に組合せる場合、共有されるセグメントに接続される全てのノードは、疑似ノードのために使用されるランダム値の一貫したビューを必要とするであろう。これを達成することのできるよく理解された多くの技法が存在し、それは本開示の中心ではない。
【００３６】
図３は、本発明のいくつかの実施形態に従って、ＳＰＢネットワークのエッジノードにおいて受信されるクライアントフレームをハンドリングするためのプロセスフローを示している。プロセスフロー３００は、ブロック３１０に示されているように、クライアントノード又はエッジに接続するノードからのフレームの受信で始まる。ブロック３２０に示されているように、エッジノードは、フローオフセット値及びフロー識別子を計算し、そして、ブロック３３０に示されているように、フロー識別子は、クライアントフレームに付加され、ブロック３４０に示されているように、転送される。
【００３７】
上で提案されているように、フロー識別子の計算は、好適には、ＳＰＢネットワーク内の複数の等コストなパスにわたってパケットの分配が最もよくランダム化されるように、良好な一様化のソースに基づく。フロー識別子は、その一様性を効果的に取り込み、そして一様化ラベルを形成する。しかしながら、フロー識別子は既に一様化ソースのランダム性を反映しているため、コアノードは、パケットを転送するために複雑な計算を実行しなくてよく、むしろ、バックボーン宛て先アドレス及びフロー識別子に従って形成されるＦＤＢを用いてパケットを転送することができる。
【００３８】
図４は上で議論したプロセス３００のいくつかの実施形態における使用のための、フロー識別子を計算するためのプロセスフロー４００を示している。既に述べたように、クライアントフレーム内のＩＰヘッダは、良好な一様化のソースである。よって、本発明のいくつかの実施形態において、フローオフセット値は、ＩＰヘッダの関数として生成される。ブロック４１０に示されているように、エッジノードは、ＩＰヘッダ（例えば、ＩＰ５タプル）のハッシュを計算し、その結果は図４においてＨで表される。そして、ハッシュ値Ｈは、フロー識別子の値のためのＮ個の所定の値の１つへマッピングされ、ここでＮはエッジノード（入口ノード）からＳＰＢの宛て先ノード（出口ノード）への候補パスの最大の数を定義する（Ｎを任意の大きい値とすることができることに留意すべきである）。ブロック４２０にこのマッピングの１つのアプローチが示されており、オフセット値（ＯＦＦＳＥＴ）は、ネットワークを通じた等コストな候補パスの数（Ｎ）での上記ハッシュ値のモジュロとして計算される。よって、
【００３９】
【数１】
0005857058.tif 000002
【００４０】
このアプローチによって、ハッシュ値は、ＯＦＦＳＥＴについてＮ個の候補値（ゼロからＮ−１）の間で均等に分けられる。最後に、ブロック４３０に示されているように、オフセット値に所定のフロー識別子の基礎値（ＢＡＳＥ）を加算することにより、フロー識別子（Ｂ−ＶＩＤ）が計算される。
【００４１】
【数２】
0005857058.tif 000003
【００４２】
図４に示したアプローチは、所与の論理ネットワークのために、Ｂ−ＶＩＤの連続的なセットを設定することができるという前提に基づく直接的なアプローチである。イーサネット標準内では、ある範囲のＢ−ＶＩＤ値をアクティブなトポロジーに割り当て、最大で６４までの複数のアクティブなトポロジーを有することが可能である。例えば、論理ネットワークは、（ユニキャストの目的のために）６４個の連続的なグループ内のＢ−ＶＩＤの範囲を割り当てられてよく、既存のイーサネット技術の限度において、ＳＰＢネットワーク内の入口／出口ノードの任意の所与のペアについて６４個までの等コストパス（６４×６４＝４０９６）をサポートすることが可能となる。当然ながら、サイズの異なるグループが使用されてもよく、あるグループについての連続的なＢ−ＶＩＤ識別子の使用は、厳密には必須ではないが、Ｂ−ＶＩＤ値の計算を簡単にする。こうしたアプローチに価値があるのは、既存の技術に基づくノードを、既存の実装により課される６４個のパスの制限を超えることのできるノードとシームレスに組み合わせることができる点である。既存のノードは、６４個のパスに制限されないノードほど良好なフローのランダム化のジョブを行わないが、依然として後方互換性を有する形でネットワークに組み込まれることができる。
【００４３】
いくつかのケースにおいて、フローラベルを生成するために使用される一様化のソースは、どういったタイプのパケットが処理されるかに依存して変化し得る。図５は、そのアプローチに従って動作するプロセス５００を示している。ブロック５１０に示されているように、まず、エッジノードにおいてクライアントフレームが受信される。エッジノードは、まず、クライアントＭＡＣからバックボーンＭＡＣへのバインディングが存在するか、即ち宛て先Ｂ−ＭＡＣアドレスが当該クライアントＭＡＣ宛て先アドレスについて学習されているかを確認する。これはブロック５２０に示されている。宛て先Ｂ−ＭＡＣアドレスが未知であれば、Ｂ−ＭＡＣアドレスを学習することができるように、ブロック５２５に示されているように、マルチキャストプロセスが開始される。
【００４４】
一方、クライアントＭＡＣからＢ−ＭＡＣへのバインディングが既に存在する場合、エッジノードは、ブロック５３０に示されているように、パケットがＩＰヘッダを有するかを確認する。ＩＰヘッダを有する場合、ブロック５４０に示されているように、当該ＩＰヘッダがハッシュ化され、ブロック５５０に示されているように、その結果がＢ−ＶＩＤを計算するために使用される。それに対し、ＩＰヘッダが存在しない場合には、エッジノードは、ブロック５３５に示されているように、Ｂ−ＭＡＣソースアドレス及びＢ−ＭＡＣ宛て先アドレスを代わりにハッシュ化し、ブロック５５０において、その結果がＢ−ＶＩＤを計算するために使用される。Ｂ−ＶＩＤは、いくつかの実施形態において、図４のブロック４２０及び４３０に示したのと同じやり方で計算されてもよく、又は、いくつかの他のやり方では、ハッシュ関数から導かれるフローオフセットがＮ個の所定のＢ−ＶＩＤ値（又は値の範囲）の１つにマッピングされてもよい。いずれのケースでも、Ｂ−ＶＩＤは、クライアントフレームへ付加され、ブロック５６０に示されているように転送される。
【００４５】
図６は、本発明のいくつかの実施形態に従って、最短パスブリッジングを利用するデータパケットネットワークバックボーン内のネットワークノードにおいて転送データベースを形成するためのプロセス６００を示している。図示されたプロセスは、ブロック６１０において示されているように、所与の論理ネットワークについての第１の（Ｂ−ＭＡＣ）宛て先アドレスで始まる。次に、ブロック６２０において示されているように、当該宛て先アドレスへの等コストのパスに対応する異なるネクストホップの数が計算される。等コストのパスは、任意の適切なルーティングメトリックの計算を用いて識別されることができる。
【００４６】
論理ネットワークに割り当てられたＢ−ＶＩＤのセットのうちの第１のＢ−ＶＩＤで開始されると（ブロック６３０）、当該Ｂ−ＶＩＤは、ブロック６４０において示されているように、当該Ｂ−ＶＩＤ及びネクストホップの数に基づいて、等コストパスについてのネクストホップインタフェースのうちの１つへマッピングされる。セット内のＢ−ＶＩＤが連続的な値であれば、各Ｂ−ＶＩＤ値をネクストホップインタフェースへマッピングする１つの簡易な手法は、当該Ｂ−ＶＩＤ値からＢ−ＶＩＤ基礎値を減算してフローオフセット値を取得し、等コストネクストホップ数での当該フローオフセット値のモジュロとしてインタフェースオフセット値を計算し、宛て先アドレスに向けた等コストパスに対応するネクストホップインタフェース群のうちのネクストホップインタフェースへのインデックスとして当該インタフェースオフセット値を使用することである。数学的な観点では：
【００４７】
【数３】
0005857058.tif 000004
【００４８】
ここで、ｎは、宛て先アドレスへのある等コストパスに対応するノードにおけるネクストホップインタフェースの数であり、対応するネクストホップインタフェースは、ｎｅｘｔ＿ｈｏｐ（０）からｎｅｘｔ＿ｈｏｐ（ｎ）としてインデックス付けされる。フローのハンドリングの間の相関度を低減するためにフローオフセットにローカルなランダム性が追加される場合、１つの例は次の通りである：
【００４９】
【数４】
0005857058.tif 000005
【００５０】
ブロック６５０に示されているように、転送データベースは、Ｂ−ＭＡＣ宛て先アドレス（ＤＡ−ＭＡＣ）、Ｂ−ＶＩＤ及びネクストホップインタフェースのための識別子で形成される。現在の宛て先アドレスについてＢ−ＶＩＤのセット内にさらなる未処理のＢ−ＶＩＤが存在する場合、ブロック６６０及び６６５に示されているように、処理は繰り返される。そして、ブロック６７０及び６７５に示されているように、ネットワークノードに知られている残りの宛て先アドレスの各々について、処理は繰り返される。プロセスが完了すると、所与の論理ネットワークについてのＦＤＢは、各宛て先アドレスについて複数のエントリを含み、各エントリは当該論理ネットワーク内のユニキャスト転送に割り当てられたＢ−ＶＩＤの１つに対応する。
【００５１】
表１は、ＦＤＢの一部分に相当する一例を示しており、Ｉ＿０〜Ｉ＿３が付番されたルータ上の４つのインタフェースが存在し、Ｂ−ＶＩＤ＿０〜Ｂ−ＶＩＤ＿８の範囲で、所与の論理ネットワークについてユニキャスト転送に８個のＢ−ＶＩＤが割り当てられている。
【００５２】
【表１】
0005857058.tif 000006
【００５３】
この（極端に単純化した）例において、各宛て先アドレスについて２つのネクストホップインタフェースが存在することがあるが、ネクストホップインタフェースのペアは、例示された３つの宛て先アドレスごとに異なる。よって、Ｉ＿０及びＩ＿３は、宛て先アドレスＢ−ＭＡＣ−ＤＡ−ａへの等コストパスについてのネクストホップのための識別子であって、宛て先アドレスＢ−ＭＡＣ−ＤＡ−ｂへの等コストパスについてのネクストホップのための識別子は、Ｉ＿１及びＩ＿２である。各宛て先アドレスについて、利用可能な８個のＢ−ＶＩＤは、２つの等コストなネクストホップの間で分けられる。
【００５４】
上述した技術の変形例において、個々のＢ−ＶＩＤの１つ以上を、ある範囲のＢ−ＶＩＤと置換えることができる。このアプローチは、サポートされる等コストパスの最大数と比較して所与の論理ネットワークのために利用可能なフローラベルが多数存在する場合に適している。例えば、４０９６個のフローラベル（Ｂ−ＶＩＤ）が利用可能であって、しかし候補としての等コストパスが６４個だけ存在する場合、Ｂ−ＶＩＤを６４個の“チャンク（chunk）”内のネクストホップ識別子へマッピングすることができる。よって、表１におけるＢＶＩＤ０は例えばＢＶＩＤ０〜ＢＶＩＤ６３という範囲に置き換えられてもよく、ＢＶＩＤ１は例えばＢＶＩＤ６４〜ＢＶＩＤ１２７という第２の範囲に置き換えられる。
【００５５】
上で説明し及び図６と表１とに例示した技術に従って形成されるＦＤＢが与えられると、Ｂ−ＶＩＤでラベリングされたパケットを転送することは、平凡な動作である。パケットを受信するネットワークノードは、Ｂ−ＶＩＤ及びＢ−ＭＡＣ−ＤＡをパケットから単純に読み取り、データベース内で対応するネクストホップをルックアップし、その方向へパケットを送信する。
【００５６】
バックボーンネットワークノードにおいてＦＤＢを形成するための上述した技法は、概して、パケット処理が単純なルックアップ及び転送のアプローチに基づいているという点で、既存のイーサネット技術と互換的である。図７及び図８において、ネットワークノードのハードウェアへより大規模な修正を要し得る、ＦＤＢ及びパケット転送に対する他のアプローチが示されている。
【００５７】
図７は、フローラベルの動的な処理を要する、このより高度なアプローチのいくつかの実施形態に係るプロセスフロー７００を示している。プロセスフロー７００は、ブロック７１０に示されているように、第１の宛て先アドレスで開始し、ブロック７４０及び７４５に示されているように、ノードにとって既知の宛て先アドレスの各々について繰り返される。各宛て先アドレスについて、ノードは、ブロック７２０に示されているように、当該宛て先アドレスに向かう等コストパスに対応するネクストホップのセットを判定する。あらためて言うと、従来型のルーティングメトリックの計算を用いて、等コストパス及びそれらに対応するインタフェースを識別することができる。
【００５８】
ブロック７３０に示されているように、ＦＤＢは、宛て先アドレス及び対応するネクストホップ識別子のセットで形成される。表１に示したものと同じ状況に対応する、この異なるタイプのＦＤＢの一例が、表２に示されている。
【００５９】
【表１】
0005857058.tif 000007
【００６０】
このアプローチに係るＦＤＢは、上で説明したアプローチに従って形成されるＦＤＢよりもメモリをあまり消費しない(即ち、より少ない状態情報を表現する）ことが、直ちに理解されるであろう。
【００６１】
図８には、このタイプのＦＤＢに対応する転送プロセス８００が示されている。ブロック８１０に示されているように、転送ノードは、Ｂ−ＶＩＤ及び宛て先アドレスでラベリングされたデータフレームを受信する。そして、ブロック８２０に示されているように、当該ノードは、Ｂ−ＶＩＤの数学的関数を用いて、当該宛て先アドレスに関連付けられるセットからネクストホップ識別子を選択する。そして、ブロック８３０に示されているように、選択されたネクストホップ識別子に対応するインタフェースを用いて、フレームが転送される。
【００６２】
いくつかの実施形態において、ＢＶＩＤに基づくネクストホップ識別子の選択は、ＦＤＢの形成について上述したものと同様の数学的アプローチを使用する。よって、例えば、ネクストホップインタフェースの数でのＢＶＩＤ値のモジュロ除算を用いて、インデックスを計算することができる。例えば、
【００６３】
【数５】
0005857058.tif 000008
【００６４】
ここで、ｎは、宛て先アドレスに対応するセット内のネクストホップインタフェースの数である。但し、フローラベルのこの動的処理の１つの利点は、ネットワークを通じたパケットフローのランダム化を、例えばノード固有のシード値などのシード値を、ネクストホップ識別処理に加えることにより、改善することができる点である。よって、例えば、ネクストホップインタフェースを、次のような公式を用いて選択することができる。
【００６５】
【数６】
0005857058.tif 000009
【００６６】
ここで、ｓｅｅｄの値は、ノードごとに若しくは時間ごとに又はその双方で変化する。
【００６７】
上の検討は、エッジノード、即ち、クライアントネットワーク及び／又はクライアントコンピュータに接続されるエッジノードにおいて、及びＳＰＢネットワークのコア内のノードを含む転送ノードにおいて実行される何らかの処理を説明したが、当然ながら、エッジノードは、いくつかの例では転送ノードでもあってよく、上記技法の１つ又は複数が所与のノードにおいて実装されてもよい。図９は、上で説明したエッジ処理、転送データベースの形成及び転送の技法のいずれか又は全てを実行するように構成されることができる例示的なネットワークノードの基本的な特徴を示している。より具体的には、ネットワークノード９００は、クライアント／ネットワークインタフェース９１０を含み、当該インタフェースユニットは、ＳＰＢネットワークへの及びからの接続点、並びに／又は１つ以上のクライアントネットワーク若しくはデバイスへの及びからの接続点を備え、具体的には、イーサネットネットワークへの接続のために適合された従来型のインタフェースハードウェアを備え得る。ネットワークノード９００は、さらに、処理回路９２０を備え、処理回路９２０は、１つ以上のマイクロプロセッサ９３０とメモリ９４０とを含み、メモリ９４０は、プログラムコード９４２、プログラムデータ９４４、及び転送データベース９４６を含む。いくつかの実施形態において、プログラムコード９４２は、最短パスブリッジングを利用するデータパケットネットワークバックボーンにおいて負荷のバランシングを容易にするための上述した技法の１つ又は複数を実行するためのプログラム命令を含み、それら技法は、クライアントフレームへフローラベルを付加し、転送データベース９４６を形成し、及びフレームについての付加されたフローラベル及び宛て先ＭＡＣアドレスに従って当該フレームを転送することについて説明した技法を含む。
【００６８】
より概して言えば、これらコンピュータプログラム命令は、汎用コンピュータのプロセッサ、特殊目的用のコンピュータ、又はマシンを生み出すための他のプログラマブルデータ処理装置に提供されて、コンピュータ又は他のプログラマブルデータ処理装置のプロセッサを介して実行される際に、ここで説明し添付のブロック図及びフロー図に例示した機能を実装するための手段を生成する。また、これらコンピュータプログラム命令は、コンピュータにより使用可能な又はコンピュータにより読取可能なメモリ内に記憶されてよく、それらは、コンピュータ又は他のプログラマブルデータ処理装置を特定の形で機能させるように指示し、それにより、コンピュータにより使用可能な又はコンピュータにより読取可能なメモリ内に記憶された当該命令は、ここで開示された機能を実装する命令を含む製品を生み出す。ここで説明された機能エンティティのいくつかは、単一のプロセッサ又はコンピュータ上に実装されてもよく、又は別個のプロセッサ又はコンピュータ上にそれぞれ実装されてもよい。当業者は、ここで説明した機能をグルーピングし又は分配する利点及び欠点を認識するであろう。
【００６９】
当然ながら、上述した負荷バランシングの技法は一例にすぎず、これら手続の様々な修正及び拡張が可能であることを当業者は理解するであろう。また、当業者は、ここで説明したネットワークノード９００の機能的な側面が、ネットワーク構造、事業者のビジネスモデル及び他の要因に依存して、複数の様々な構成で配備されてもよいことを認識するであろう。
【００７０】
これら及び他のバリエーション及び拡張を念頭におき、当業者は、上述した説明及び添付図面が、データパケットネットワーク内の負荷のバランシングを容易にするためにここで教示されたシステム及び装置の非限定的な例を表現していることを理解するであろう。そのため、本発明は、上述した説明及び添付図面によって限定されない。その代わりに、本発明は、以下の特許請求の範囲及びそれらの法的な均等物によってのみ限定される。
【図１】
0005857058.tif 000010
【図２】
0005857058.tif 000011
【図３】
0005857058.tif 000012
【図４】
0005857058.tif 000013
【図５】
0005857058.tif 000014
【図６】
0005857058.tif 000015
【図７】
0005857058.tif 000016
【図８】
0005857058.tif 000017
【図９】
0005857058.tif 000018