(57)【特許請求の範囲】
【請求項１】
ネットワーク内の複数の他のネットワークデバイス（１０２〜１０７）へ通信可能に連結される第１のネットワークデバイス（１０１）における方法であって、前記ネットワークデバイスの各々はビット転送ルータ（ＢＦＲ）であり、前記方法は、
指定ＢＦＲ（Ｄ−ＢＦＲ）を決定するための選択プロセスに参加することと、
前記第１のネットワークデバイスを前記Ｄ−ＢＦＲ（１０１）として選択するという決定に応じて、
共通的なツリータイプをサポートするＢＦＲの範囲内で、前記ネットワーク内の他のＢＦＲ（１０２〜１０７）により広告される当該他のＢＦＲによりサポートされる最大ＢＭ長のうちの最小のＢＭ長に基づいて、ビットマスク（ＢＭ）の選択ＢＭ長を決定すること（６３５，６４０）、前記ＢＭの各ビットがビット転送出口ルータ（ＢＦＥＲ）（１０５〜１０７）に対応することになること、及び、
決定された前記選択ＢＭ長を前記他のＢＦＲへ広告すること（６４５）、
を含むＤ−ＢＦＲ動作を実行することと、
を含む方法。
【請求項２】
Ｄ−ＢＦＲ動作を実行することは、
前記ネットワーク内の他のＢＦＲにより広告される当該他のＢＦＲによりサポートされるツリータイプに基づいて、選択ツリータイプを決定すること（７２０，７２５，７３０）、及び、
決定された前記選択ツリータイプを前記他のＢＦＲへ広告すること（７３５）、
をさらに含み、
前記共通的なツリータイプとしての前記選択ツリータイプをサポートするＢＦＲの範囲内で前記選択ＢＭ長が決定される、
請求項１の方法。
【請求項３】
Ｄ−ＢＦＲ動作を実行することは、
１つ以上のＢＭ位置（ＢＭＰ）を割り当てること（８１０）、前記１つ以上のＢＭＰの各々が異なるＢＦＥＲへ割り当てられること、及び、
割り当てられた前記１つ以上のＢＭＰを前記他のＢＦＲへ広告すること（８２０）、
をさらに含む、請求項１の方法。
【請求項４】
前記選択ＢＭ長を決定することは、
前記他のＢＦＲのうちの１つ以上からメッセージを受信すること（６０５）、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含むこと、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短くないと判定することに応じて、前記選択ＢＭ長を決定された前記最小のＢＭ長に等しくなるように設定すること（６３５）、
を含む、請求項１の方法。
【請求項５】
前記選択ＢＭ長を決定することは、
前記他のＢＦＲのうちの１つ以上からメッセージを受信すること（６０５）、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含むこと、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短いと判定することに応じて、前記選択ＢＭ長を前記前回の選択ＢＭ長に等しくなるように設定すること（６４０）、
を含む、請求項１の方法。
【請求項６】
前記選択ツリータイプを決定することは、
前記他のＢＦＲのうちの１つ以上からメッセージを受信すること（７０５）、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる１つ以上のツリータイプの標識を含むこと、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示されたツリータイプを判定すること、及び、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示された判定された前記ツリータイプへと、前記選択ツリータイプを設定すること（７２０，７２５，７３５）、
を含む、請求項２の方法。
【請求項７】
１つ以上のＢＭＰを割り当てることは、
ＢＦＥＲから、ＢＭＰを当該ＢＦＥＲへ割り当てるための要求を示すメッセージを受信すること（５０５）、
ＢＭＰを前記ＢＦＥＲへ割り当てること（８１０）、及び、
前記ＢＭＰが割り当て済みであることを示すようにＢＭＰ情報を更新すること（８１５）により、前記ＢＭＰが他のＢＦＥＲへ割り当てられないようにすること、
を含む、請求項３の方法。
【請求項８】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する特定のＢＭＰをさらに示す、請求項７の方法。
【請求項９】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する前記特定のＢＭＰ以外のＢＭＰを受け入れる用意が前記ＢＦＥＲにあることをさらに示す、請求項８の方法。
【請求項１０】
ネットワーク内の複数の他のネットワークデバイス（１０２〜１０７）へ通信可能に連結される第１のネットワークデバイス（１０１）であって、前記ネットワークデバイスの各々はビット転送ルータ（ＢＦＲ）であり、前記第１のネットワークデバイスは、
１つ以上のプロセッサのセットと、
コードを収容する非一時的なマシン読取可能な記憶媒体と、
を備え、
前記コードは、前記１つ以上のプロセッサのセットにより実行された場合に、前記第１のネットワークデバイスに、
指定ＢＦＲ（Ｄ−ＢＦＲ）を決定するための選択プロセスに参加させ、
前記第１のネットワークデバイスを前記Ｄ−ＢＦＲとして選択するという決定に応じて、
共通的なツリータイプをサポートするＢＦＲの範囲内で、前記ネットワーク内の他のＢＦＲ（１０２〜１０７）により広告される当該他のＢＦＲによりサポートされる最大ＢＭ長のうちの最小のＢＭ長に基づいて、ビットマスク（ＢＭ）の選択ＢＭ長を決定すること（６３５，６４０）、前記ＢＭの各ビットがビット転送出口ルータ（ＢＦＥＲ）（１０５〜１０７）に対応することになること、及び、
決定された前記選択ＢＭ長を前記他のＢＦＲへ広告すること（６４５）、
を含むＤ−ＢＦＲ動作を実行させる、
第１のネットワークデバイス。
【請求項１１】
Ｄ−ＢＦＲ動作を実行することは、前記第１のネットワークデバイスが、
前記ネットワーク内の他のＢＦＲにより広告される当該他のＢＦＲによりサポートされるツリータイプに基づいて、選択ツリータイプを決定すること（７２０，７２５，７３０）、及び、
決定された前記選択ツリータイプを前記他のＢＦＲへ広告すること（７３５）、
をさらに含み、
前記共通的なツリータイプとしての前記選択ツリータイプをサポートするＢＦＲの範囲内で前記選択ＢＭ長が決定される、
請求項１０の第１のネットワークデバイス。
【請求項１２】
Ｄ−ＢＦＲ動作を実行することは、前記第１のネットワークデバイスが、
１つ以上のＢＭ位置（ＢＭＰ）を各々異なるＢＦＥＲへ割り当てること（８１０）、及び、
割り当てられた前記１つ以上のＢＭＰを前記他のＢＦＲへ広告すること（８２０）、
をさらに含む、請求項１０の第１のネットワークデバイス。
【請求項１３】
前記選択ＢＭ長を決定することは、前記第１のネットワークデバイスが、
各メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（６０５）、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短くないと判定することに応じて、前記選択ＢＭ長を決定された前記最小のＢＭ長に等しくなるように設定すること（６３５）、
を含む、請求項１０の第１のネットワークデバイス。
【請求項１４】
前記選択ＢＭ長を決定することは、前記第１のネットワークデバイスが、
各メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（６０５）、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短いと判定することに応じて、前記選択ＢＭ長を前記前回の選択ＢＭ長に等しくなるように設定すること（６４０）、
を含む、請求項１０の第１のネットワークデバイス。
【請求項１５】
前記選択ツリータイプを決定することは、前記第１のネットワークデバイスが、
各メッセージを送信したＢＦＲによりサポートされる１つ以上のツリータイプの標識を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（７０５）、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示されたツリータイプを判定すること、及び、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示された判定された前記ツリータイプへと、前記選択ツリータイプを設定すること（７２０，７２５，７３５）、
を含む、請求項１１の第１のネットワークデバイス。
【請求項１６】
１つ以上のＢＭＰを割り当てることは、前記第１のネットワークデバイスが、
ＢＦＥＲから、ＢＭＰを当該ＢＦＥＲへ割り当てるための要求を示すメッセージを受信すること（５０５）、
ＢＭＰを前記ＢＦＥＲへ割り当てること（８１０）、及び、
前記ＢＭＰが割り当て済みであることを示すようにＢＭＰ情報を更新すること（８１５）により、前記ＢＭＰが他のＢＦＥＲへ割り当てられないようにすること、
を含む、請求項１２の第１のネットワークデバイス。
【請求項１７】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する特定のＢＭＰをさらに示す、請求項１６の第１のネットワークデバイス。
【請求項１８】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する前記ＢＭＰ以外のＢＭＰを受け入れる用意が前記ＢＦＥＲにあることをさらに示す、請求項１７の第１のネットワークデバイス。
【請求項１９】
非一時的なコンピュータ読取可能な記憶媒体であって、当該記憶媒体に記憶されたコンピュータコードを有し、前記コンピュータコードは、ネットワークデバイスの各々がビット転送ルータ（ＢＦＲ）であるものとして、ネットワーク内の複数の他のネットワークデバイス（１０２〜１０７）へ通信可能に連結される第１のネットワークデバイスのプロセッサにより実行された場合に、前記第１のネットワークデバイスに、
指定ＢＦＲ（Ｄ−ＢＦＲ）を決定するための選択プロセスに参加する動作と、
前記第１のネットワークデバイスを前記Ｄ−ＢＦＲとして選択するという決定に応じて、
共通的なツリータイプをサポートするＢＦＲの範囲内で、前記ネットワーク内の他のＢＦＲ（１０２〜１０７）により広告される当該他のＢＦＲによりサポートされる最大ＢＭ長のうちの最小のＢＭ長に基づいて、ビットマスク（ＢＭ）の選択ＢＭ長を決定すること（６３５，６４０）、前記ＢＭの各ビットがビット転送出口ルータ（ＢＦＥＲ）（１０５〜１０７）に対応することになること、及び、
決定された前記選択ＢＭ長を前記他のＢＦＲへ広告すること（６４５）、
を含むＤ−ＢＦＲ動作を実行する動作と、
を行わせる、非一時的なコンピュータ読取可能な記憶媒体。
【請求項２０】
Ｄ−ＢＦＲ動作を実行することは、
前記ネットワーク内の他のＢＦＲにより広告される当該他のＢＦＲによりサポートされるツリータイプに基づいて、選択ツリータイプを決定すること（７２０，７２５，７３０）、及び、
決定された前記選択ツリータイプを前記他のＢＦＲへ広告すること（７３５）、
をさらに含み、
前記共通的なツリータイプとしての前記選択ツリータイプをサポートするＢＦＲの範囲内で前記選択ＢＭ長が決定される、
請求項１９の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２１】
Ｄ−ＢＦＲ動作を実行することは、
１つ以上のＢＭ位置（ＢＭＰ）を各々異なるＢＦＥＲへ割り当てること（８１０）、及び、
割り当てられた前記１つ以上のＢＭＰを前記他のＢＦＲへ広告すること（８２０）、
をさらに含む、請求項１９の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２２】
前記選択ＢＭ長を決定することは、
各メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（６０５）、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短くないと判定することに応じて、前記選択ＢＭ長を決定された前記最小のＢＭ長に等しくなるように設定すること（６３５）、
を含む、請求項１９の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２３】
前記選択ＢＭ長を決定することは、
各メッセージを送信したＢＦＲによりサポートされる前記最大ＢＭ長を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（６０５）、
受信されるメッセージ内に含まれる全ての前記最大ＢＭ長のうちの前記最小のＢＭ長を決定すること（６２０）、及び、
前記最小のＢＭ長が前回の選択ＢＭ長よりも短いと判定することに応じて、前記選択ＢＭ長を前記前回の選択ＢＭ長に等しくなるように設定すること（６４０）、
を含む、請求項１９の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２４】
前記選択ツリータイプを決定することは、
各メッセージを送信したＢＦＲによりサポートされる１つ以上のツリータイプの標識を含む当該メッセージを、前記他のＢＦＲのうちの１つ以上から受信すること（７０５）、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示されたツリータイプを判定すること、及び、
メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示された判定された前記ツリータイプへと、前記選択ツリータイプを設定すること（７２０，７２５，７３５）、
を含む、請求項２０の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２５】
１つ以上のＢＭＰを割り当てることは、
ＢＦＥＲから、ＢＭＰを当該ＢＦＥＲへ割り当てるための要求を示すメッセージを受信すること（５０５）、
ＢＭＰを前記ＢＦＥＲへ割り当てること（８１０）、及び、
前記ＢＭＰが割り当て済みであることを示すようにＢＭＰ情報を更新すること（８１５）により、前記ＢＭＰが他のＢＦＥＲへ割り当てられないようにすること、
を含む、請求項２１の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２６】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する特定のＢＭＰをさらに示す、請求項２５の非一時的なコンピュータ読取可能な記憶媒体。
【請求項２７】
前記ＢＦＥＲからの前記メッセージは、前記ＢＦＥＲが選好する前記特定のＢＭＰ以外のＢＭＰを受け入れる用意が前記ＢＦＥＲにあることをさらに示す、請求項２６の非一時的なコンピュータ読取可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、２０１４年９月１９日に提出された米国仮出願第６２／０５３，０６７号の利益を主張し、同仮出願は参照によりここに取り入れられる。
【０００２】
［分野］
本発明の実施形態は、パケットネットワークの分野に関し、より具体的には、ビットマスク（ＢＭ）長、ＢＭ位置及びツリータイプ情報の自動化された選択と分配とに関する。
【背景技術】
【０００３】
ＩＥＴＦ（Internet  Engineering  Task  Force）のインターネットドラフト（Ｉ−Ｄ）draft-wijnands-bier-architecture-00（参照によりここに取り入れられる）は、全ての目的とするマルチキャスト受信機がビットマスク（ＢＭ）内のビットとして符号化されるアーキテクチャとしてＢＩＥＲ（Bit  Index  Explicit  Replication）を記述しており、同アーキテクチャでは、即ち、各受信機がＢＭ内の一意なビットにより表現される。ヘッダ内にカプセル化されるビットマスクを伴うパケットを受信するルータは、ＢＭ内のビットの各々についての予め計算されるツリーに従って、受信機へ向けてＢＭの設定に基づいてパケットを転送することになる。
【０００４】
ヘッダにより搬送可能なビット数の制限及びそれにより生じる拡張可能性の懸念に起因して、ＢＩＥＲは、受信機セットという概念をサポートする。各パケットは、一意なセット識別子により各々が識別されるＢＩＥＲセットを搬送する。それらセットの複数の用法は、全てのＢＩＥＲセット内の全ての受信機を包含する単一のＢＩＥＲツリーを展開すること（単一の分配トランスポートの線形的な拡張）であるか、又は、ＢＩＥＲセットの複数の独立したセット（その各々が独立マルチキャスト分配トランスポートである）であるかのいずれかとして理解され得る。
【０００５】
一旦受信機の数が大規模になり（即ち、多くのセットが存在）又は受信機が多くの独立したＢＩＥＲツリーに参加する（即ち、受信機は多くのセット内の多くの独立したビットを割り当てられることができる）と、受信機への一意なＢＭ位置（ＢＭＰ）の割り当ては些細な問題ではなくなり、自動化された解決策を要する。通常のトレードオフは、集中型（サーバ型）のアプローチであるか又は分散型のアプローチであるかであって、分散型のアプローチは、追加的なプロトコルの複雑さを犠牲にして、より高い拡張可能性を提供する。追加的に、保証を要することとして、セットを共有する全ての受信機がパケットを分配するために使用されるツリーのタイプと各セットのＢＭ長とをサポートできなければならない。
【発明の概要】
【課題を解決するための手段】
【０００６】
ネットワーク内の複数の他のネットワークデバイスへ通信可能に連結される第１のネットワークデバイスにより実行される方法において、上記ネットワークデバイスの各々はビット転送ルータ（ＢＦＲ）であり、上記方法は、指定ＢＦＲ（Ｄ−ＢＦＲ）を決定するための選択プロセスに参加すること、を含む。上記方法は、上記第１のネットワークデバイスを上記Ｄ−ＢＦＲとして選択するという決定に応じてＤ−ＢＦＲ動作を実行すること、をさらに含み、Ｄ−ＢＦＲ動作は、上記ネットワーク内の他のＢＦＲにより広告される最大ローカルＢＭ長に基づいて、ＢＭの選択ＢＭ長を決定すること、上記ＢＭの各ビットがビット転送出口ルータ（ＢＦＥＲ）に対応することになること、及び、決定された上記選択ＢＭ長を上記他のＢＦＲへ広告すること、を含む。
【０００７】
１つの実施形態によれば、Ｄ−ＢＦＲ動作を実行することは、上記ネットワーク内の他のＢＦＲにより広告されるサポートされるツリータイプに基づいて、選択ツリータイプを決定すること、及び、決定された上記選択ツリータイプを上記他のＢＦＲへ広告すること、をさらに含む。１つの実施形態において、Ｄ−ＢＦＲ動作を実行することは、１つ以上のＢＭ位置（ＢＭＰ）を割り当てること、上記１つ以上のＢＭＰの各々が異なるＢＦＥＲへ割り当てられること、及び、割り当てられた上記１つ以上のＢＭＰを上記他のＢＦＲへ広告すること、をさらに含む。
【０００８】
１つの実施形態において、上記選択ＢＭ長を決定することは、上記他のＢＦＲのうちの１つ以上からメッセージを受信すること、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる最大ＢＭ長を含むこと、受信されるメッセージ内に含まれる全ての最大ＢＭ長のうちの最小のＢＭ長を決定すること、及び、上記最小のＢＭ長が前回の選択ＢＭ長よりも短くないと判定することに応じて、上記選択ＢＭ長を決定された上記最小のＢＭ長に等しくなるように設定すること、を含む。
【０００９】
１つの実施形態において、上記選択ＢＭ長を決定することは、上記他のＢＦＲのうちの１つ以上からメッセージを受信すること、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる最大ＢＭ長を含むこと、受信されるメッセージ内に含まれる全ての最大ＢＭ長のうちの最小のＢＭ長を決定すること、及び、上記最小のＢＭ長が前回の選択ＢＭ長よりも短いと判定することに応じて、上記選択ＢＭ長を上記前回の選択ＢＭ長に等しくなるように設定すること、を含む。
【００１０】
１つの実施形態によれば、上記選択ツリータイプを決定することは、上記他のＢＦＲのうちの１つ以上からメッセージを受信すること、各メッセージは当該メッセージを送信したＢＦＲによりサポートされる１つ以上のツリータイプの標識を含むこと、メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示されたツリータイプを判定すること、及び、メッセージを送信した１つ以上のＢＦＲによりサポートされるものとして示された判定された上記ツリータイプへと、上記選択ツリータイプを設定すること、を含む。
【００１１】
１つの実施形態において、１つ以上のＢＭＰを割り当てることは、ＢＦＥＲから、ＢＭＰを当該ＢＦＥＲへ割り当てるための要求を示すメッセージを受信すること、ＢＭＰを上記ＢＦＥＲへ割り当てること、及び、上記ＢＭＰが割り当て済みであることを示すようにＢＭＰ情報を更新することにより、上記ＢＭＰが他のＢＦＥＲへ割り当てられないようにすること、を含む。１つの実施形態において、上記ＢＦＥＲからの上記メッセージは、上記ＢＦＥＲが選好する特定のＢＭＰをさらに示す。１つの実施形態において、上記ＢＦＥＲからの上記メッセージは、上記ＢＦＥＲが選好する上記特定のＢＭＰ以外のＢＭＰを受け入れる用意が上記ＢＦＥＲにあることをさらに示す。
【図面の簡単な説明】
【００１２】
本発明は、以下の説明及び本発明の実施形態を例示するために用いられる添付図面を参照することにより最も良好に理解され得る。図面は次の通りである：
【００１３】
【図１】１つの実施形態に係るＢＩＥＲをサポートするためのネットワークを例示するブロック図である。
【図２】１つの実施形態に係るＢＩＥＲをサポートするためのネットワークデバイスを例示するブロック図である。
【図３】１つの実施形態に係るＢＩＥＲプロトコル選択（ＢＩＥＲ−ＰＥ）パケットを例示するブロック図である。
【図４】１つの実施形態に係るＢＩＥＲプレフィクス情報タイプレングス値（ＢＩＥＲ−ＰＩ  ＴＬＶ）を例示するブロック図である。
【図５】１つの実施形態に係るＢＩＥＲプロトコル選択ＭＢ位置（ＢＩＥＲ−ＰＥ−ＢＭＰ）パケットを例示するブロック図である。
【図６】１つの実施形態に係るＢＭ長を選択するための方法を例示するフロー図である。
【図７】１つの実施形態に係るツリータイプを選択するための方法を例示するフロー図である。
【図８】１つの実施形態に係るＢＭＰを割り当てるための方法を例示するフロー図である。
【図９Ａ】本発明のいくつかの実施形態に従って、例示的なネットワーク内のネットワークデバイス（ＮＤ）の間の接続性と共に、ＮＤの３つの例示的な実装例を示している。
【図９Ｂ】本発明のいくつかの実施形態に係る、特殊目的のネットワークデバイス９０２を実装する例示的な手法を示している。
【発明を実施するための形態】
【００１４】
以下の説明は、ＢＩＥＲ情報を分配するための方法及び装置を説明する。以下の説明において、ロジック実装、オプコード、オペランドを特定するための手段、リソース分割／共有／複製の実装、システムコンポーネントのタイプ及び相互関係、並びにロジック分割／統合の選択などの多くの具体的な詳細が、本発明のより充分な理解を提供する目的で呈示される。しかしながら、本発明がそうした具体的な詳細が無くとも実践され得ることが、当業者により理解されるであろう。他の例において、制御構造、ゲートレベル回路及びソフトウェア命令シーケンスの全体は、発明を曖昧にしないために詳細には示されていない。当業者は、包含される説明によって、過度な実験をせずとも適切な機能性を実装することができるであろう。
【００１５】
本明細書における、“１つの実施形態”、“一実施形態”、“例示的な実施形態”などへの言及は、記載される実施形態が特定の特徴、構造、又は特性を含み得るものの、あらゆる実施形態が当該特定の特徴、構造、又は特性を含むわけでは必ずしもないかもしれないことを示す。その上、そうしたフレーズは、必ずしも同じ実施形態を指しているわけではない。さらに、一実施形態との関係において特定の特徴、構造、又は特性が説明されている場合、明示的に記載されているか否かに関わらず、他の実施形態との関係においてそうした特徴、構造、又は特性を作用させることは、当業者の知識の範囲内であることが思量される。
【００１６】
ここでは、括弧書きのテキスト及び破線境界（例えば、ラージダッシュ、スモールダッシュ、ドットダッシュ及びドット）を伴うブロックが、本発明の実施形態に追加的な特徴を加えるオプション的な動作を例示するために使用されているかもしれない。但し、そうした表記は、それらがオプション若しくはオプション的な動作に過ぎないこと、及び／又は、実線境界を伴うブロックが本発明のある実施形態においてオプション的ではないことを意味するものとして受け取られるべきではない。
【００１７】
以下の説明及び特許請求の範囲では、“連結される”及び“接続される”という用語が、その派生語と共に使用され得る。これら用語は互いに対して同義語として意図されないことを理解されるべきである。“連結される”は、互いに物理的に又は電気的に直接接触してもしなくておよい２つ以上の要素が互いに協働し又はインタラクションすることを示すために使用される。“接続される”は、互いに連結される２つ以上の要素間における通信の確立を示すために使用される。
【００１８】
電子デバイス又はコンピューティングデバイスは、マシン読取可能な記憶媒体（例えば、磁気ディスク、光ディスク、読み出し専用メモリ（ＲＯＭ）、フラッシュメモリデバイス、相変化メモリ）及びマシン読取可能な（担体ともいう）伝送媒体（例えば、電気的、光学的、無線、音響的、又は他の形式の伝播信号−例えば、搬送波、赤外線信号など）といったマシン読取可能な媒体（コンピュータ読取可能な媒体ともいう）を使用して、（ソフトウェア命令から構成され、コンピュータプログラムコード若しくはコンピュータプログラムとして言及されることもある）コード及び／又はデータを記憶し、コード及び／又はデータを（内部的に、及び／又は、他の電子デバイスとの間でネットワーク上で）伝送する。よって、電子デバイス（例えば、コンピュータ）は、１つ以上のマシン読取可能な記憶媒体へ連結される１つ以上のプロセッサのセットなどのハードウェア及びソフトウェアを含み、それらマシン読取可能な記憶媒体は、プロセッサのセット上での実行のためのコードを記憶し及び／又はデータを記憶する。例えば、電子デバイスは、不揮発性のメモリであれば電子デバイスがターンオフされた場合（電力が除去された場合）であってもコード／データを維持することができることから、コードを収容する不揮発性メモリを含んでよく、一方で、電子デバイスがターンオンされている間、電子デバイスのプロセッサにより実行されるべきコードの部分は、典型的には、より低速の不揮発性メモリから、電子デバイスの揮発性メモリ（例えば、ＤＲＡＭ（dynamic  random  access  memory）、ＳＲＡＭ（static  random  access  memory））へコピーされる。典型的な電子デバイスは、（伝播信号を用いてコード及び／又はデータを送信し及び／又は受信するために）他の電子デバイスとのネットワーク接続を確立するための１つ以上の物理的なネットワークインタフェースのセットをも含む。本発明の一実施形態の１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの様々な組み合わせを使用して実装されてよい。
【００１９】
ネットワークデバイス（ＮＤ）は、ネットワーク上の他の電子デバイス（例えば、他のネットワークデバイス、エンドユーザデバイス）を通信可能に相互接続する電子デバイスである。いくつかのネットワークデバイスは、複数のネットワーキング機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２統合、セッションボーダ制御、ＱｏＳ（Quality  of  Service）、及び／若しくは加入者管理）についてのサポートを提供し、並びに／又は複数のアプリケーションサービス（例えば、データ、音声及び映像）についてのサポートを提供する、“マルチサービスネットワークエレメント”である。
【００２０】
図１は、あるトポロジーにおいてＢＩＥＲプロトコルをサポートするためのネットワーク１００を例示するブロック図である。ここで使用されるところによれば、トポロジーとは、ネットワークの多様なネットワークエレメント（例えば、リンク、ノードなど）の配置をいう。トポロジーは、１つ以上のツリーを含む。ここで使用されるところによれば、ツリーとは、ループの無い形での、即ち、同一のノードで開始し且つ終了するパスの無い形での複数のネットワークエレメントの配置をいう。ここで、パスとは、複数のネットワークデバイスを連結するリンクのセットをいう。
【００２１】
図示した例において、ネットワーク１００は、ネットワークデバイス１０５〜１０６へ通信可能に連結されるネットワークデバイス１０１〜１０２を含む。ネットワークデバイス１０２は、さらに、ネットワークデバイス１０４へ通信可能に連結される。ネットワークデバイス１０３は、ネットワークデバイス１０４及び１０７へ通信可能に連結される。この例において、ネットワークデバイス１０２及び１０４〜１０６は、図１において実線で示されているリンクを通じて、ツリーＴ１により通信可能に連結される。さらに、ネットワークデバイス１０３〜１０４及び１０７は、図１において破線で示されているリンクを通じて、ツリーＴ２により通信可能に連結される。
【００２２】
図示したネットワークデバイスの各々は、ビット転送ルータ（ＢＦＲ）である。ここで使用されるところによれば、ＢＦＲは、ＢＩＥＲプロトコルをサポートするネットワークデバイス（即ち、ＢＩＥＲ対応ネットワークデバイス）である。ＢＦＲは、ビット転送入口ルータ（ＢＦＩＲ）であるかもしれない。ここで使用されるところによれば、ＢＦＩＲは、目的受信機へ向けて次のＢＦＲへパケットを送信する前に、当該パケットへＢＭを挿入／カプセル化する入口ルータである。ＢＦＲは、ビット転送出口ルータであるかもしれない。ここで使用されるところによれば、ＢＦＥＲは、ＢＭＰが割り当てられており、ＢＭＰセットを伴うＢＩＥＲパケットを受信するように構成される出口ルータである。この例において、ネットワークデバイス１０４はＢＦＩＲであり、ネットワークデバイス１０５〜１０７はＢＦＥＲである。
【００２３】
ＢＦＲは、あるセットのための指定ＢＦＲ（Ｄ−ＢＦＲ）として及び／又はバックアップＤ−ＢＦＲ（ＢＤ−ＢＦＲ）として選択されることができる。１つのネットワークデバイスが１つ以上のセットのためのＤ−ＢＦＲ又はＢＤ−ＢＦＲとして供されてもよい。図示した例では、セットＳ１のためのＤ−ＢＦＲとしてネットワークデバイス１０１が選択されており、セットＳ２のためのＤ−ＢＦＲとしてネットワークデバイス１０３が選択されている。本発明を曖昧にすることを避ける目的で、ＢＤ−ＢＦＲは図から省略されている。１つの実施形態によれば、Ｄ−ＢＦＲは、各ＢＭ（即ち、セット）についてのＢＭ長を決定する、ように構成される。この例において、セットＳ１は３ビットという長さを有し、セットＳ２は２ビットという長さを有する。本説明を通じて、右端のビットを“第１ビット”、右から２番目のビットを“第２ビット”などというものとする。
【００２４】
１つの実施形態によれば、Ｄ−ＢＦＲは、ＢＭセット内で一意なＢＭＰを各ＢＦＥＲへ割り当てる、ように構成される。この例において、ネットワークデバイス１０５〜１０６は、それぞれＢＭセットＳ１のＢＭＰ００１及び０１０を割り当てられている。さらに、ネットワークデバイス１０７は、ＢＭセットＳ２のＢＭＰ０１を割り当てられている。よって、マルチキャストパケットを受信するＢＦＲは、ＢＭ設定に基づいて当該パケットの宛て先を判定することができる。例として、ネットワークデバイス１０４（即ち、ＢＦＩＲ）がネットワークデバイス１０７（即ち、ＢＦＥＲ）へパケット１５０を送信する必要があることを想定されたい。そうしたケースにおいて、ネットワークデバイス１０４は、パケット（Ｓ２，０１）１５０をネットワークへ投入することになる。本説明を通じて、ＢＩＥＲパケットを“パケット（Ｂ，Ｃ）”として記述するものとし、“Ｂ”はセットＩＤを、“Ｃ”はＢＭを表す。“Ｂ，Ｃ”は、ＢＦＲ同士で交渉され合意されたカプセル化プロトコル（例えば、ＭＰＬＳ）を用いてパケットへカプセル化されるものと理解されるべきである。図示されていないものの、当業者は、パケットの一部として他の情報（例えば、ペイロード、チェックサムなど）を含めることができることを認識するはずである。
【００２５】
上の例について続けると、ネットワークデバイス１０３によりパケット（Ｓ２，０１）１５０が受信される。ネットワークデバイス１０３は、カプセル化されたＢＭの第１ビットが設定されており、ネットワークデバイス１０７が０１というＢＭＰ（即ち、１番目のビット位置）を有すると判定する。そうした判定に応じて、ネットワークデバイス１０３は、ツリーＴ２を介してネットワークデバイス１０７へパケット（Ｓ２，０１）１５０を向かわせる。本説明を通じて、“１”に設定されたＢＭビットは、対応するＢＭＰを伴うＢＦＥＲへパケットが転送されるべきであることを示す。但し、他の用法を用いてもよいことが理解されるべきである。
【００２６】
さらなる例として、ネットワークデバイス１０４がネットワークデバイス１０５及び１０６の双方へパケット１５１を送信する必要があることを想定されたい。そうした例において、ネットワークデバイス１０４は、パケット（Ｓ１，０１１）１５１をネットワークへ投入することになる。パケット（Ｓ１，０１１）１５１は、ネットワークデバイス１０２により受信される。ネットワークデバイス１０２は、カプセル化されたＢＭの第１ビットが設定されており、ネットワークデバイス１０５が００１というＢＭＰ（即ち、１番目のビット位置）を有すると判定する。そうした判定に応じて、ネットワークデバイス１０２は、ＢＭを修正し、ツリーＴ１を介してネットワークデバイス１０５へ当該パケットを向かわせる。例えば、ネットワークデバイス１０２は、パケット（Ｓ１，０１１）１５１をパケット（Ｓ１，００１）１５１Ａとしてネットワークデバイス１０５へ送信する。
【００２７】
ネットワークデバイス１０２は、さらに、カプセル化されたＢＭの第２ビットが設定されており、ネットワークデバイス１０６が０１０というＢＭＰ（即ち、２番目のビット位置）を有すると判定する。そうした判定に応じて、ネットワークデバイス１０２は、パケット（Ｓ１，０１１）１５１を複製し、そのＢＭを修正し、ネットワークデバイス１０６へ向かわせる。例えば、ネットワークデバイス１０２は、パケット（Ｓ１，０１１）１５１をパケット（Ｓ１，０１０）１５１Ｂとしてネットワークデバイス１０６へ送信する。
【００２８】
１つの実施形態によれば、Ｄ−ＢＦＲは、参加する全てのＢＦＲがＢＩＥＲパケットを送信するために計算し及び使用しなければならないツリータイプを選択する、ように構成される。１つの実施形態において、Ｄ−ＢＦＲは、以下にさらに詳細に説明するように、複数のＢＦＲによりサポートされるツリータイプに基づいて、及び／又は、管理上の構成に基づいて、ツリータイプを選択する。
【００２９】
図２は、１つの実施形態に係るネットワークデバイス２０１を例示するブロック図である。１つの実施形態によれば、ネットワークデバイス２０１は、Ｄ−ＢＦＲ及びＢＤ−ＢＦＲを選択するための選択アルゴリズム／プロセスを実行する責任を有する選択コントローラ２１０を含む。選択コントローラ２１０は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせとして実装されてよい。１つの実施形態によれば、トポロジーＴ内の所与のセットＳ（＜Ｔ，Ｓ＞として表記する）は、そのトポロジー内へと広告されるセットＳを含む第１ＢＩＥＲ−ＰＥパケット又はＢＩＥＲ−ＰＩ  ＴＬＶパケットによりトリガされない限り、選択を目的として有効化されない。但し、理解されるべきこととして、＜Ｔ，Ｓ＞は、限定ではないものの、管理者による構成を含む他のいかなる仕組みを用いて有効化されてもよい。ここで使用されるところによれば、ＢＩＥＲ−ＰＥパケットは、ＢＩＥＲについてのプロトコル選択情報を搬送するプロトコルパケットユニット（ＰＰＵ）である。例えば、ＯＳＰＦｖ２（Open  Shortest  Path  First,  Version  2）のケースでは、ＢＩＥＲ−ＰＥパケットはＯｐａｑｕｅ  ＬＳＡ（Link  State  Advertisement）であり、これはＩＥＴＦ  ＲＦＣ（Request  For  Comments）５２５０（参照によりここに取り入れられる）に記述されている。ここで使用されるところによれば、ＢＩＥＲ−ＰＩ  ＴＬＶパケットは、ＢＦＥＲのＢＩＥＲプレフィクス情報を搬送するＰＰＵである。例えば、ＯＳＰＦｖ２のケースでは、ＢＩＥＲ−ＰＩ  ＴＬＶパケットは、拡張プレフィクスＯｐａｑｕｅ  ＬＳＡであり、これはＩＥＴＦ  Ｉ−Ｄ  draft-ietf-ospf-prefix-link-attr-00（参照によりここに取り入れられる）に記述されている。最初のＢＩＥＲ−ＰＥ又はＢＩＥＲ−ＰＩ  ＴＬＶは、多様なイベントのうちのどれによってトリガされてもよく、それらイベントは、限定ではないものの、ＶＰＮ（Virtual  Private  Network）によるＰ２ＭＰ（Point-to-Multipoint）ツリーの開始の希望、又はＢＦＥＲへの管理上のＢＭＰの割り当て及びエリア内へのＢＩＥＲ−ＰＩ  ＴＬＶを介する広告を含む。
【００３０】
一旦セットＳが有効化されると、選択コントローラ２１０は、＜Ｔ，Ｓ＞のためのＤ−ＢＦＲ（ここでは、Ｄ−ＢＦＲ＜Ｔ，Ｓ＞として表記される）を選択するための選択プロセスに参加する、ように構成される。ここで、選択アルゴリズムについて説明する。
【００３１】
［選択の初期化］
選択コントローラ２１０は、＜Ｔ，Ｓ＞に参加するＢＦＲのリストを生成する。留意すべきこととして、ネットワークデバイス２０１自身がリストに含まれなければならない。リストは、ネットワークデバイス２０１によって到達可能なＢＦＲのみを含まなければならず、Ｄ−ＢＦＲになる資格を有しないＢＦＲ（例えば、＜Ｔ，Ｓ＞について０というルータ優先度を有するＢＦＲ）を含んではならない。例えば、リストは、ＢＩＥＲ−ＰＥパケットを送信することにより、ネットワークデバイス２０１によって受信されるＢＩＥＲ選択情報を広告したＢＦＲを含んでもよい。
【００３２】
図３は、１つの実施形態に係るＢＩＥＲ−ＰＥパケット３００を例示するブロック図である。ＢＩＥＲ−ＰＥパケット３００の一部として示している情報／エレメントは例示のためのものであり、本発明の限定を意図したものではない。
【００３３】
１つの実施形態によれば、ＢＩＥＲ−ＰＥパケット３００は、ＯＳＰＦｖ２  ｏｐａｑｕｅ  ＬＳＡとして実装され、これはＩＥＴＦ  ＲＦＣ５２５０に記述されている。ＢＩＥＲ−ＰＥパケット３００は、ＢＩＥＲに参加する各ＢＦＲにより広告／分配され、図３に例示したセット情報ブロックの１つ以上を含む。セット情報ブロックは、送信元のＢＦＲが参加する各セットについて繰り返される。ＢＩＥＲ−ＰＥパケット３００は、限定ではないものの、次のフィールドを含む：
【００３４】
［フィールド］  …  ［定義］
“タイプ（Type）”  …  パケットをＢＩＥＲ−ＰＥとして識別する、予め定義される値
“レングス（Length）”  …  パケットの合計長
“ＭＴ−ＩＤ”  …  マルチトポロジー識別子，ＩＥＴＦ  ＲＦＣ４９１５に記述されている（参照によりここに取り入れられる）
“セット選択数（#  Of  Set  Elections）”  …  本パケット内で繰り返されるセット情報ブロックの数
“セットＩＤ（Set  ID）”  …  セット識別子
“Ｄ−ＢＦＲ優先度（D-BFR  Priority）”  …  本パケットの送信元のＢＦＲの＜MT-ID,  Set  ID＞についての優先度（Ｄ−ＢＦＲ及びＢＤ−ＢＦＲ選択の目的のために使用される）
“サポートツリータイプ（Supported  Tree  Types）”  …  本パケットの送信元のＢＦＲによりサポートされるオプションとしてのツリータイプのマスク
“最大ローカルＢＭ長（Maximum  Local  BM  Length）”  …  本パケットの送信元のＢＦＲによりサポートされる最大ＢＭ長
“Ｄ−ＢＦＲ  ＩＤ”  …  Ｄ−ＢＦＲとして選択されたＢＦＲのルータＩＤ。送信元ＢＦＲは自身をＤ−ＢＦＲとして選択した場合には本フィールドを自身のルータＩＤに設定しなければならない
“ＢＤ−ＢＦＲ  ＩＤ”  …  ＢＤ−ＢＦＲとして選択されたＢＦＲのルータＩＤ。送信元ＢＦＲは自身をＢＤ−ＢＦＲとして選択した場合には本フィールドを自身のルータＩＤに設定しなければならない
【００３５】
［ＢＤ−ＢＦＲ選択アルゴリズム］
ここで再び図２を参照すると、選択コントローラ２１０は、ＢＤ−ＢＦＲ＜Ｔ，Ｓ＞を選択するために、以下の動作を実行する。選択コントローラ２１０は、生成したＢＦＲのリストから、自らをＤ−ＢＦＲ＜Ｔ，Ｓ＞として広告した全てのＢＦＲを除外する。除外後の生成されたリスト上に残るＢＦＲから、選択コントローラ２１０は、１つ以上のＢＦＲが自らをＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として広告したかを判定する。そうである場合、選択コントローラ２１０は、＜Ｔ，Ｓ＞について最も高いルータ優先度を有するＢＦＲをＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択する。
【００３６】
ＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として広告した２つ以上のＢＦＲのルータ優先度が等しい場合、Ｓ（例えば、セットＩＤ）でＸＯＲ演算したルータＩＤの最も高いＢＦＲがＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択される（ビッグエンディアンの順序とし、双方の値を右寄せして、短い方の値の全てのビットを長い方の値の長さになるまでゼロでパディングすることを想定）。ルータＩＤを分配するための仕組みは当分野においてよく知られており、簡明さのためにここでは説明されない。
【００３７】
＜Ｔ，Ｓ＞についてのＢＤ−ＢＦＲとして自身を広告した／宣言したＢＦＲが存在しない場合、選択コントローラ２１０は、＜Ｔ，Ｓ＞について最も高いルータ優先度を有するＢＦＲをＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択する。２つ以上のＢＦＲのルータ優先度が等しい場合、ＳでＸＯＲ演算したルータＩＤの最も高いＢＦＲがＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択される。
【００３８】
［Ｄ−ＢＦＲ選択アルゴリズム］
選択コントローラ２１０は、Ｄ−ＢＦＲ＜Ｔ，Ｓ＞を選択するために、以下の動作を実行する。選択コントローラ２１０は、初期化プロセスの一部として生成したリスト上の１つ以上のＢＦＲが自らをＤ−ＢＦＲ＜Ｔ，Ｓ＞として（例えば、ＢＩＥＲ−ＰＥパケットを送信することにより）広告したかを判定する。そうである場合、＜Ｔ，Ｓ＞について最も高いルータ優先度を有する１つがＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択される。上記ＢＦＲのうちの２つ以上のルータ優先度が等しい場合、ＳでＸＯＲ演算したルータＩＤの最も高い１つが選択される。自身がＤ−ＢＦＲ＜Ｔ，Ｓ＞であると宣言したＢＦＲが存在しない場合、選択コントローラ２１０は、新たに選択されたＢＤ−ＢＦＲ＜Ｔ，Ｓ＞をＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択する。
【００３９】
ネットワークデバイス２０１が（ｉ）新たに選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞であり、（ｉｉ）新たに選択されたＢＤ−ＢＦＲ＜Ｔ，Ｓ＞であり、（ｉｉｉ）もはやＤ−ＢＦＲ＜Ｔ，Ｓ＞ではなく、又は（ｉｖ）もはやＢＤ−ＢＦＲ＜Ｔ，Ｓ＞ではないと判定することに応じて、選択コントローラ２１０は、ＢＤ−ＢＦＲ選択アルゴリズム及びＤ−ＢＦＲ選択アルゴリズムを再実行する。例えば、ＢＤ−ＢＦＲ選択アルゴリズムが再実行される際にネットワークデバイス２０１が新たに選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞である場合、ネットワークデバイス２０１は、もはやＢＤ−ＢＦＲ＜Ｔ，Ｓ＞選択について資格を有しない。とりわけ、これは自身がＢＤ−ＢＦＲ＜Ｔ，Ｓ＞及びＤ−ＢＦＲ＜Ｔ，Ｓ＞の双方であると宣言するＢＦＲが存在しないことを補償することになる。
【００４０】
選択アルゴリズムの複雑さの裏にある理由は、その時点のＤ−ＢＦＲ＜Ｔ，Ｓ＞に障害が起きた場合のＢＤ−ＢＦＲ＜Ｔ，Ｓ＞からＤ−ＢＦＲ＜Ｔ，Ｓ＞への混乱の無い移行が望まれることである。この混乱の無い移行は、古いＢＤ−ＢＦＲ＜Ｔ，Ｓ＞が新たにＤ−ＢＦＲ＜Ｔ，Ｓ＞の責任を受け入れるまで、新たなＢＤ−ＢＦＲ＜Ｔ，Ｓ＞を選択することが不可であるというヒステリシスの導入を通じて保証される。
【００４１】
上の手続は、同一のＢＦＲをＤ−ＢＦＲ＜Ｔ，Ｓ＞及びＢＤ−ＢＦＲ＜Ｔ，Ｓ＞の双方として選択するかもしれない。例えば、ネットワークデバイス２０１は、自身をＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択し得るが、ＢＩＥＲ−ＰＥが他のＢＦＲにより受信されるタイミングに起因して、それら他のＢＦＲがネットワークデバイス２０１をＢＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択するかもしれない。さらに留意すべきこととして、選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞は、＜Ｔ，Ｓ＞について最高のルータ優先度を有するＢＦＲではないかもしれず、（やはりＢＩＥＲ−ＰＥがＢＦＲにより受信されるタイミングに起因して）ＢＤ−ＢＦＲ＜Ｔ，Ｓ＞も必ずしも２番目に高いルータ優先度を有しないかもしれない。また、留意すべきこととして、ネットワークデバイス２０１がＤ−ＢＦＲ＜Ｔ，Ｓ＞となる資格を有するただ１つのＢＦＲである場合、ネットワークデバイス２０１は、自身をＤ−ＢＦＲ＜Ｔ，Ｓ＞として選択し、そのネットワークについてＢＤ−ＢＦＲ＜Ｔ，Ｓ＞は存在しないことになる。
【００４２】
１つの実施形態によれば、ネットワークデバイス２０１が選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞であるという判定に応じて、選択コントローラ２１０は、Ｄ−ＢＦＲコントローラ２１１によるＤ−ＢＦＲ責任の遂行を有効化する。Ｄ−ＢＦＲコントローラ２１１は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせとして実装されてよい。１つの実施形態において、Ｄ−ＢＦＲコントローラ２１１は、＜Ｔ，Ｓ＞についてのＢＭ長（ここでは、ＢＭ長＜Ｔ，Ｓ＞という）を選択するためのＢＭ長選択部２２０を含む。ＢＭ長＜Ｔ，Ｓ＞を選択するために、ＢＭ長選択部２２０は、ＢＩＥＲ−ＰＥパケットを介して全てのＢＦＲ＜Ｔ，Ｓ＞により広告された全ての最大ＢＭ長のうちの最小値を計算する。この計算された最小値が、決定される最小ＢＭ長である。
【００４３】
１つの実施形態によれば、ＢＭ長選択部２２０は、決定済みの最小ＢＭ長以下のＢＭ長を＜Ｔ，Ｓ＞内の参加中の全てのＢＦＲ（Ｄ−ＢＦＲは例外であり得る）が広告しない限り、前回選択したＢＭ長よりも短い新たなＢＭ長を選択しない。この要件は、十分なＢＭＰが無いことを理由としてＢＩＥＲネットワークから排除されるＢＦＲが存在しないことを保証する。
【００４４】
しかしながら、ＢＭ長選択部２２０は、結果としてツリーが細分化される場合であって、より短いＢＭ長を伴うＢＦＲが選択に含められない限り割り当て済みのＢＭＰを伴う全てのＢＦＲが到達可能にならない場合には、より短いＢＭ長を選択してもよい。言い換えれば、全てのＢＦＲを到達可能にする目的でより短いＢＭ長を伴うＢＦＲ（即ち、決定される最小ＢＭ長を前回選択されたＢＭ長よりも短くさせたＢＦＲ）が必要である場合、ＢＭ長選択部２２０は、より短いそのＢＭ長に等しい新たなＢＭ長を選択してよい。１つの実施形態において、新たに選択されるＢＭ長が前回選択されたＢＭ長よりも短いと判定することに応じて、ＢＭ長選択部２２０は、ＢＭＰ割り当て部２２１にＢＭＰを再割り当てさせる。そして、１つの実施形態において、ＢＭ長選択部２２０は、以下にさらに詳細に説明するように、ネットワークデバイス２０１に、新たに選択されたＢＭ長をＢＩＥＲ−ＰＥ−ＢＭＰパケット内で広告させる。
【００４５】
１つの実施形態によれば、Ｄ−ＢＦＲコントローラ２１１は、ＢＩＥＲパケットを送信するためにＢＦＲが使用することを要するツリータイプを選択するためのツリー選択部２２２、をさらに含む。１つの実施形態によれば、参加中の各ＢＦＲは、ＢＩＥＲ−ＰＥパケットを送信することにより、自身がサポートするツリータイプを広告する。１つの実施形態において、各ＢＦＲは、少なくともＳＰＦ（Shortest  Path  First）ツリータイプ及び／又はＳＳＴ（Shortest  Spanning  Tree）タイプをサポートすることを要する。加えて、各ＢＦＲは、１つ以上のオプション的なツリータイプをサポートしてよい。そうした広告を受信することに応じて、ツリー選択部２２２は、例えばネットワークデバイス２０１によりアクセス可能なストレージデバイスなど、ストレージデバイス内に、サポートツリータイプに関する情報を記憶し又は記憶させる。１つの実施形態によれば、ツリー選択部２２２は、選択ツリータイプを、全てのＢＦＲによりサポートされるツリータイプに設定する。１つの実施形態において、全てのＢＦＲによりサポート可能な複数のツリータイプが存在すると判定することに応じて、ツリー選択部２２２は、選択ツリータイプを、全てのＢＦＲによりサポートされる既定のツリータイプ（例えば、管理上で構成されたツリータイプ）に設定する。１つの実施形態において、ツリー選択部２２２は、選択ツリータイプを管理上で構成されるツリータイプに設定し、選択ツリータイプをサポートしないＢＦＲを除外する。例えば、この実施形態では、オプションとしてのツリータイプを全てのＢＦＲがサポートするわけではないと判定することに応じて、ツリー選択部２２２は、その選択の結果としていくつかのＢＦＲがＢＩＥＲネットワークから除外されることになるとしても、オプションとしての当該ツリータイプを選択してよい。ここで説明したツリータイプ選択アルゴリズムは、例示の目的のためのものである。理解されるべきこととして、ツリー選択部２２２は、管理上の構成及び／又はＢＦＲによりどのツリータイプがサポートされるかに関する情報に基づいて、いかなるツリータイプを選択してもよい。１つの実施形態によれば、ツリー選択部２２２は、次いで、ネットワークデバイス２０１に、以下にさらに詳細に説明されるＢＩＥＲ−ＰＥ−ＢＭＰパケット内で選択ツリータイプを広告させる。
【００４６】
１つの実施形態において、Ｄ−ＢＦＲコントローラ２１１は、ＢＦＥＲ＜Ｔ，Ｓ＞へＢＭＰを割り当てるように構成されるＢＭＰ割り当て部２２１、をさらに含む。ＢＭＰの割り当ては、多様なイベントのうちのいかなるイベントによって開始されてもよく、それらイベントは、限定ではないものの、ＢＩＥＲ−ＰＩ  ＴＬＶパケットを送信することによるＢＦＥＲからのＢＭＰを求めるリクエストを含む。
【００４７】
図４は、１つの実施形態に係るＢＩＥＲ−ＰＩ  ＴＬＶパケット４００を例示するブロック図である。ＢＩＥＲ−ＰＩ  ＴＬＶパケット４００の一部として示した情報／エレメントは、説明の目的のためのものであって、本発明の限定を意図していない。
【００４８】
１つの実施形態によれば、ＢＩＥＲ−ＰＩ  ＴＬＶパケット４００は、拡張プレフィクスＯｐａｑｕｅ  ＬＳＡとして実装され、これはＩＥＴＦ  Ｉ−Ｄ  draft-ietf-ospf-prefix-link-attr-00に記述されている。ＢＩＥＲ−ＰＩ−ＢＭＰパケット４００は、参加中のＢＦＥＲにより広告／分配される。ＢＩＥＲ−ＰＩ  ＴＬＶパケット４００は、限定ではないものの、次のフィールドを含む：
【００４９】
［フィールド］  …  ［定義］
“タイプ（Type）”  …  パケットをＢＩＥＲ−ＰＩ  ＴＬＶとして識別する、予め定義される値
“レングス（Length）”  …  パケットの合計長
“カプセル化タイプ（Encapsulation  Type）”  …  ＢＩＥＲカプセル化タイプ
“ＭＴ−ＩＤ”  …  マルチトポロジー識別子，ＩＥＴＦ  ＲＦＣ４９１５に記述されている（参照によりここに取り入れられる）
“セットＩＤ（Set  ID）”  …  セット識別子
“ラベル（Label）”  …  本セットについてカプセル化に関し使用されるラベル（２０ビット）。ＢＦＲにより割り当てられた有効なラベルでなければならない
“管理ＢＭＰ（Admin  BMP）”  …  無効なＢＭＰ（例えば、全て１）又は管理上要するＢＭＰに設定される
“Ａ”  …  本ビットが設定される場合、ＢＦＥＲは管理ＢＭＰフィールドに示される値が管理上の構成について選好される位置であることを広告する
“Ｒ”  …  本ビットが設定される場合、ＢＦＥＲは管理ＢＭＰフィールドに管理上で設定されたもの以外のＢＭＰを受け入れる用意があることを示す
【００５０】
ここで再び図２を参照すると、１つの実施形態において、ＢＭＰ割り当て部２２１は、割り当て済みのＢＭＰを含むＢＭＰ情報を維持する（例えば、ＢＭＰデータベースが当該情報を収容する）。ＢＭＰ割り当て部２２１は、受信したＢＩＥＲ−ＰＩ  ＴＬＶが選好されるＢＭＰを示しているかを（例えば、受信したＢＩＥＲ−ＰＩ  ＴＬＶにおいてフィールド“Ａ”が設定されているかをチェックすることにより）判定する。そうである場合、ＢＭＰ割り当て部２２１は、選好される当該ＢＭＰが割り当て用に利用可能である（即ち、未だＢＦＥＲに割り当てられていない）ことをＢＭＰ情報が示しているかを判定する。選好されるＢＭＰが利用可能であると判定することに応じて、ＢＭＰ割り当て部２２１は、選好される当該ＢＭＰを要求元のＢＦＥＲへ割り当てる。選好されるＢＭＰが利用可能ではない場合、ＢＭＰ割り当て部２２１は、要求元のＢＦＲが選好される当該ＢＭＰとは異なるＢＭＰを受け入れる用意があるかを（例えば、受信したＢＩＥＲ−ＰＩ  ＴＬＶにおいてフィールド“Ｒ”が設定されているかをチェックすることにより）判定する。そうである場合、ＢＭＰ割り当て部２２１は、選好される当該ＢＭＰとは異なる利用可能な（即ち、未割り当ての）ＢＭＰを要求元のＢＦＥＲへ割り当てる。要求元のＢＦＥＲが選好されるＢＭＰを示していて、かつ利用可能な（即ち、未割り当ての）異なるＢＭＰを受け入れる用意が無いことを示している（例えば、フィールド“Ａ”が設定されているがフィールド“Ｒ”が設定されていない）場合、ＢＭＰ割り当て部２２１は、要求元のＢＦＥＲに、ＢＭＰの衝突を示すエラーを返信する。
【００５１】
１つの実施形態によれば、ＢＩＥＲ−ＰＩ  ＴＬＶが選好されるＢＭＰを示さないと判定することに応じて、ＢＭＰ割り当て部２２１は、単純に、例えばＢＭＰデータベースから取得される任意の利用可能なＢＭＰを要求元のＢＦＥＲへ割り当てる。全てのケースにおいて、利用可能なＢＭＰが無いことをＢＭＰ情報が示している場合、ＢＭＰ割り当て部２２１は、利用可能なＢＭＰが無いことを示すエラーを要求元のＢＦＥＲへ返信する。ＢＭＰ割り当て部２２１は、複数のＢＦＥＲへ同一のＢＭＰを割り当てることを回避する目的で、各ＢＭＰ割り当ての後にＢＭＰ情報を更新する。１つの実施形態によれば、ＢＭＰ割り当て部２２１は、次いで、ネットワークデバイス２０１に、割り当てられたＢＭＰをＢＩＥＲ−ＰＥ−ＢＭＰパケット内で広告させる。
【００５２】
新たなＢＭ長の選択、ツリータイプの選択及び／又は１つ以上のＢＭＰの割り当てに応じて、ネットワークデバイス２０１は、ＢＩＥＲ−ＰＥ−ＢＭＰパケットを送信することによりその情報を広告する。
【００５３】
図５は、１つの実施形態に係るＢＩＥＲ−ＰＥ−ＢＭＰパケット５００を例示するブロック図である。ＢＩＥＲ−ＰＥ−ＢＭＰパケット５００の一部として示した情報／エレメントは、説明の目的のためのものであって、本発明の限定を意図していない。
【００５４】
１つの実施形態によれば、ＢＩＥＲ−ＰＥ−ＢＭＰパケット５００は、ＯＳＰＦｖ２  ｏｐａｑｕｅ  ＬＳＡとして実装され、これはＩＥＴＦ  ＲＦＣ５２５０に記述されている。ＢＩＥＲ−ＰＥ−ＢＭＰパケット５００は、選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞により広告／分配され、図５に例示したＢＭＰ割り当てブロックの１つ以上を含む。ＢＭＰ割り当てブロックは、各ＢＭＰ割り当てについて反復される。ＢＩＥＲ−ＰＥ−ＢＭＰパケット５００は、限定ではないものの、次のフィールドを含む：
【００５５】
［フィールド］  …  ［定義］
“タイプ（Type）”  …  パケットをＢＩＥＲ−ＰＥ−ＢＭＰとして識別する、予め定義される値
“レングス（Length）”  …  パケットの合計長
“ＭＴ−ＩＤ”  …  マルチトポロジー識別子，ＩＥＴＦ  ＲＦＣ４９１５に記述されている（参照によりここに取り入れられる）
“セットＩＤ（Set  ID）”  …  セット識別子
“ツリーＩＤ(Tree  ID）”  …  選択ツリータイプ識別子
０：ＳＰＦ（Shortest  Path  First）−全てのＢＦＲによりサポートされる
あらゆるＢＦＲが自身をルートとしてＳＰＦを計算し、そのツリーを用いてビットインデックス転送テーブル（ＢＩＦＴ）を構築する
１：ＳＳＴ（Shortest  Spanning  Tree）−全てのＢＦＲによりサポートされる
あらゆるＢＦＲがセット（即ち、有効なＢＭＰ割り当てを伴うＢＦＲ）内の全てのＢＦＥＲに行きわたるシュタイナーツリーを計算する
２〜６：オプションとしてのツリータイプ１〜５
７：予約済み
“選択ＢＭ長（Elected  BM  Length）”  …  ＢＭの選択された長さ
“ＢＭＰ割り当て数（#  BMP  Assignments）”  …  本パケット内で反復されるＢＭＰ割り当てブロックの数
“経路タイプ／ＡＦ／プレフィクス長（Route  Type/AF/Prefix  Length）”  …  ＢＭＰが割り当てられた対象のプレフィクスについての一意な識別子
“ステータス（status）”  …  ０：ＢＭＰ割り当ては有効、１：エラー：ＢＭＰ衝突、２：エラー：ＢＭＰ不足
“ＢＭＰ割り当て（BMP  Assignment）”  …  ＢＦＥＲ  ＩＤにより識別されるＢＦＥＲへ割り当てられたＢＭＰ。割り当てエラーがある場合、本フィールドは無効なＢＭＰ（例えば、全て１）に設定される。
“アドレスプレフィクス（Address  Prefix）”  …  ＢＦＥＲに関連付けられるプレフィクス
“ＢＦＥＲ  ＩＤ”  …  ＢＭＰが割り当てられた対象のＢＦＥＲのルータＩＤ
【００５６】
ここで再び図２を参照すると、１つの実施形態によれば、ネットワークデバイス２０１が選択されたＢＤ−ＢＦＲ＜Ｔ，Ｓ＞であると判定することに応じて、選択コントローラ２１０は、ＢＤ−ＢＦＲコントローラ２１２によるＢＤ−ＢＦＲ責任の遂行を有効化する。ＢＤ−ＢＦＲコントローラ２１２は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせとして実装されてよい。１つの実施形態において、ＢＤ−ＢＦＲコントローラ２１２は、選択されたＤ−ＢＦＲ＜Ｔ，Ｓ＞の正確な状態、及び受信される各広告上の正確な状態を自身の広告内でミラーリングし、ネットワークデバイス２０１がＤ−ＢＦＲ＜Ｔ，Ｓ＞への接続性を喪失した場合に備えて全てのＤ−ＢＦＲ＜Ｔ，Ｓ＞手続の開始点として使用すべき自身の内部状態を維持する。
【００５７】
ＢＩＥＲ−ＰＥを広告することによりセット＜Ｔ，Ｓ＞へ参加することを望む新たなＢＦＲは、次の場合には、＜Ｔ，Ｓ＞について全てのメンバーによりツリータイプ計算において無視されなければならない：
・選択ＢＭ長よりも自身の最大サポートＢＭ長が短い場合、
・選択ツリータイプを計算可能でない場合、又は、
・＜Ｔ，Ｓ＞上でのＢＩＥＲトラフィックの転送をサポートするために有効なカプセル化ラベルを（少なくとも一時的に）割り当て可能でない場合。
【００５８】
よって、Ｄ−ＢＦＲが既に選択済みである場合、＜Ｔ，Ｓ＞について上の条件を満たさないルータは、自身のＢＩＥＲ−ＰＥを広告すべきでない。但し、当該ルータは、全ての受信機に行きわたるツリーの細分化を防止するためにＤ−ＢＦＲがより短いＢＭを選択することを可能とするために、そうしたＢＩＥＲ−ＰＥを広告してもよい。
【００５９】
各ＢＦＲ＜Ｔ，Ｓ＞は、自身のＢＩＥＲ−ＰＩ  ＴＬＶにおいて、ＢＭＰを求めるリクエストを搬送する。ＢＦＲ＜Ｔ，Ｓ＞がＢＦＥＲ＜Ｔ，Ｓ＞でもあるケースでは、ＢＩＥＲ−ＰＩ  ＴＬＶは、ＢＩＥＲトラフィックを転送する際にセットＳのカプセル化のために割り当てられたラベルをも含む。最適化、リソース制約又は他の基準に起因して、ルータは、そうしたラベルを＜Ｔ，Ｓ＞において割り当てることができないかもしれない。その場合、ルータは、＜Ｔ，Ｓ＞について自身のＢＩＥＲ−ＰＩ  ＴＬＶを広告してはならなない。従って、＜Ｔ，Ｓ＞についてツリータイプを計算する全てのルータは、それを計算から除外する。ルータが＜Ｔ，Ｓ＞についてラベルを広告する場合、＜Ｔ，Ｓ＞についてツリータイプを計算する全てのルータは、＜Ｔ，Ｓ＞についてビットインデックス転送テーブル（ＢＩＦＴ）を再計算しなければならない。
【００６０】
特殊な検討の観点として、ルータは、転送されるトラフィックが無いためにラベル空間を節約できると判定した場合、意図的に＜Ｔ，Ｓ＞についてラベルを広告せず又は自身のＢＩＥＲ−ＰＩ  ＴＬＶを削除（purge）してもよいということが考察されるべきである。
【００６１】
図６は、ＢＭ長を選択するための方法６００を例示するフロー図である。例えば、方法６００は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせで実装されることができる。このフロー図及び他のフロー図における動作は、他の図面の例示的な実施形態を参照しながら説明されるであろう。しかしながら、理解されるべきこととして、他の図面を参照して議論したものとは別の本発明の実施形態によりフロー図の動作を実行することが可能であり、また、それら他の図面を参照して議論した本発明の実施形態がフロー図を参照して議論されるものとは異なる動作を実行することが可能である。
【００６２】
ここで図６を参照すると、ブロック６０５において、ＢＭ長選択部は、ＢＦＲにより広告される最大ＢＭ長を（例えば、ＢＩＥＲ−ＰＥパケット内で）受信する。ブロック６１０において、ＢＭ長選択部は、受信した最大ＢＭ長をストレージデバイス内に記憶する。ブロック６１５において、ＢＭ長選択部は、新たなＢＭ長を選択するためのトリガを受信する。例えば、そのトリガは、ＢＩＥＲ−ＰＥパケットの受信、管理者により設定されるリクエストなどであってよい。ブロック６２０において、ＢＭ長選択部は、受信した全ての最大ＢＭ長のうち最小のＢＭ長を判定する。
【００６３】
ブロック６２５において、ＢＭ長選択部は、判定した最小のＢＭ長が前回選択されたＢＭ長（即ち、その時点のＢＭ長）よりも短いかを判定する。短くない場合、ＢＭ長選択部は、ブロック６３５へ遷移し、新たに選択されるＢＭ長を、判定した最小のＢＭ長に設定する。ブロック６４５において、ＢＭ長選択部は、新たに選択したＢＭ長を（例えば、ＢＩＥＲ−ＰＥ−ＢＭＰパケットを送信することにより）広告する。
【００６４】
次に、ブロック６２５へ戻る。判定した最小のＢＭ長が前回選択されたＢＭ長よりも短いと判定することに応じて、ＢＭ長選択部は、ブロック６３０へ遷移する。ブロック６３０において、ＢＭ長選択部は、受信した全ての最大ＢＭ長が判定した最小ＢＭ長以下であるかを判定する。そうである場合、ＢＭ長選択部は、ブロック６３５へ遷移する。一方、受信した全ての最大ＢＭ長が判定した最小ＢＭ長以下であるというわけではない場合、ＢＭ長選択部は、ブロック６４０へ遷移し、新たに選択されるＢＭ長を前回選択したＢＭ長に設定する（即ち、その時点のＢＭ長を維持する）。留意すべきこととして、ＢＭ長選択部は、結果としてツリーが細分化される場合であって、より短いＢＭ長を伴うＢＦＲが選択に含められない限り割り当て済みのＢＭＰを伴う全てのＢＦＥＲが到達可能にならないと判定する場合には、前回選択したＢＭ長よりも短いかに関わらず、新たなＢＭ長を選択してもよい。例えば、より短い最大ＢＭ長を伴うＢＦＲが選択に含められない場合に割り当て済みのＢＭＰを伴う全てのＢＦＥＲが到達可能にはならないと判定することに応じて、ＢＭ長選択部は、１つの実施形態において、より短い最大ＢＭ長を伴うＢＦＲを選択に含め、（例えば、ブロック６３５の動作を実行することにより）新たに選択されるＢＭ長をより短いその最大ＢＭ長に設定する。これは、新たな最小のＢＭ長を判定するためのブロック６２０の動作の実行の前でも後でも行われることができる。
【００６５】
図７は、ツリータイプを選択するための方法７００を例示するフロー図である。例えば、方法７００は、ツリー選択部２２２により実行されることができる。方法７００は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせで実装されることができる。ここで図７を参照する。ブロック７０５において、ツリー選択部は、ＢＦＲによりどのツリータイプがサポートされるかの情報を（例えば、受信されるＢＩＥＲ−ＰＥパケットの一部として）受信する。ブロック７１０において、ツリー選択部は、受信したサポートツリータイプの情報をストレージデバイス内に記憶する。ブロック７１５において、ツリー選択部は、ツリータイプを選択するためのトリガを受信する。例えば、そのトリガは、ＢＩＥＲ−ＰＥパケットの受信、管理者により開始されるリクエストなどであってよい。
【００６６】
ブロック７２０において、ツリー選択部は、選択ツリータイプを、全てのＢＦＲによりサポートされるツリータイプに設定する。ブロック７２５において、ツリー選択部は、全てのＢＦＲによりサポート可能な複数のツリータイプが存在すると判定することに応じて、選択ツリータイプを、全てのＢＦＲによりサポートされる管理上で構成されるツリータイプに設定する。ブロック７３０において、ツリー選択部は、選択ツリータイプを、管理上で構成されるツリータイプに設定し、及び当該選択ツリータイプをサポートしないＢＦＲを除外する。ブロック７３０は、例えば、あるオプションとしてのツリータイプを全てのＢＦＲがサポートしているわけではなく、いくつかのＢＦＲがＢＩＥＲネットワークから除外される結果となるとしても、それでもツリータイプを選択する必要があるとツリー選択部が判定することに応じて、実行されてよい。ブロック７３５において、ツリー選択部は、選択ツリータイプを（例えば、ＢＩＥＲ−ＰＥ−ＢＭＰパケットを送信することにより）広告する。
【００６７】
図８は、ＢＭＰを割り当てるための方法８００を例示するフロー図である。例えば、方法８００は、ＢＭＰ割り当て部２２１により実行されることができる。方法８００は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの任意の組み合わせで実装されることができる。ここで図８を参照する。ブロック８０５において、ＢＭＰ割り当て部は、ＢＭＰを割り当てるためのトリガを受信する。そのトリガは、ＢＩＥＲ−ＰＥパケット、ＢＩＥＲ−ＰＩ  ＴＬＶパケットの受信、管理者により開始されるリクエストなどであってよい。
【００６８】
ブロック８１０において、ＢＭＰ割り当て部は、未割り当ての（即ち、利用可能な）ＢＭＰをＢＦＥＲへ割り当てる。割り当てられるＢＭＰは、要求元のＢＦＥＲがそのＢＩＥＲ−ＰＩ  ＴＬＶにおいて選好されるＢＭＰを示したか、選好されるＢＭＰが利用可能ではない場合に他のＢＭＰを受け入れる用意があるか、などに依存する。例えば、要求元のＢＦＥＲが選好されるＢＭＰを示さない場合、ＢＭＰ割り当て部は、任意の利用可能な／未割り当てのＢＭＰを選択し、それをＢＦＥＲへ割り当てる。要求元のＢＦＥＲが選好されるＢＭＰを示す場合であって当該ＢＭＰが利用可能である場合、ＢＭＰ割り当て部は、その選好されるＢＭＰを要求元のＢＦＥＲへ割り当てる。しかしながら、選好されるＢＭＰが利用可能ではない場合であって要求元のＢＦＥＲが他のＢＭＰを受け入れる用意があることを示す場合、ＢＭＰ割り当て部は、ＢＦＥＲに他の利用可能を割り当てる。一方、選好されるＢＭＰが利用可能ではない場合であって要求元のＢＦＥＲが他のＢＭＰを受け入れる用意が無いことを示す場合、ＢＭＰ割り当て部は、衝突を示すエラーステータスをＢＦＥＲへ返信する。全てのケースにおいて、利用可能なＢＭＰが存在しない場合、ＢＭＰ割り当て部は、利用可能なＢＭＰ無し、を示すエラーをＢＦＥＲへ返信する。
【００６９】
ブロック８１５において、ＢＭＰ割り当て部は、同じＢＭＰが他のＢＦＥＲへ割り当てられることのないよう、上記ＢＭＰが割り当てられたことを示すように（例えば、データベース内に記憶されている）ＢＭＰ情報を更新する。ブロック８２０において、ＢＭＰ割り当て部は、割り当てたＢＭＰを（例えば、ＢＩＥＲ−ＰＥ−ＢＭＰパケットを送信することにより）広告する。
【００７０】
図９Ａは、本発明のいくつかの実施形態に従って、例示的なネットワーク内のネットワークデバイス（ＮＤ）間の接続性と共に、ＮＤの３つの例示的な実装を示している。図９Ａは、ＮＤ９００Ａ〜Ｈ、及びそれらの接続性を、Ａ−Ｂ、Ｂ−Ｃ、Ｃ−Ｄ、Ｄ−Ｅ、Ｅ−Ｆ、Ｆ−Ｇ及びＡ−Ｇの間の線、並びに、ＨとＡ、Ｃ、Ｄ及びＧの各々との間の線の手段により示している。これらＮＤは物理的デバイスであり、これらＮＤの間の接続性は、無線又は有線であり得る（しばしばリンクという）。ＮＤ９００Ａ、Ｅ及びＦから伸びる追加的な線は、これらＮＤが本ネットワークについての入口及び出口ポイントとして動作することを示している（よって、これらＮＤをエッジＮＤということがあり、一方で他のＮＤはコアＮＤと呼ばれ得る）。
【００７１】
図９Ａにおける例示的なＮＤ実装の２つは次の通りである：１）カスタムＡＳＩＣ（application-specific  integrated  circuits）及びプロプライエタリなＯＳ（operating  system）を使用する特殊目的のネットワークデバイス９０２、並びに、２）ＣＯＴＳ（common  off-the-shelf）プロセッサ及び標準のＯＳを使用する汎用目的のネットワークデバイス９０４。
【００７２】
特殊目的のネットワークデバイス９０２は、（典型的には１つ以上のプロセッサのセットを含む）計算リソース９１２と、（典型的には１つ以上のＡＳＩＣ及び／又はネットワークプロセッサを含む）転送リソース９１４と、（物理ポートと呼ばれることもある）物理ネットワークインタフェース（ＮＩ）９１６と、ネットワーキングソフトウェア９２０を記憶している非一時的なマシン読取可能な記憶媒体９１８と、を含むネットワークハードウェア９１０を含む。物理ＮＩは、ＮＤ９００Ａ〜Ｈの間の接続性により示されているようなネットワーク接続を（例えば、ワイヤレスネットワークインタフェースコントローラ（ＷＮＩＣ）を通じて無線で、又は、ネットワークインタフェースコントローラ（ＮＩＣ）へ接続された物理ポートへケーブルを繋げることを通じて）仲介するＮＤ内のハードウェアである。動作の期間中、ネットワーキングソフトウェア９２０は、１つ以上のネットワーキングソフトウェアインスタンス９２２のセットをインスタンス化するためにネットワーキングハードウェア９１０により実行され得る。ネットワーキングソフトウェアインスタンス９２２の各々、及びネットワーキングハードウェア９１０のネットワークソフトウェアインスタンスを実行する部分（当該ネットワーキングソフトウェアインスタンスに専用のハードウェア及び／又は当該ネットワーキングソフトウェアインスタンスによりネットワークソフトウェアイスタンス９２２のうちの他のインスタンスと時間的に共用されるハードウェアの時間スライスである）は別々の仮想ネットワークエレメント９３０Ａ〜Ｒを形成する。仮想ネットワークエレメント（ＶＮＥ）９３０Ａ〜Ｒの各々は、（ローカル制御モジュール又は制御通信モジュールということもある）制御通信及び構成モジュール９３２Ａ〜Ｒ及び転送テーブル９３４Ａ〜Ｒを含み、そのため、所与の仮想ネットワークエレメント（例えば、９３０Ａ）は、制御通信及び構成モジュール（例えば、９３２Ａ）、１つ以上の転送テーブルのセット（例えば、９３４Ａ）、及びネットワーキングハードウェア９１０の仮想ネットワークエレメント（例えば、９３０Ａ）を実行する部分を含む。
【００７３】
ソフトウェア９２０は、ネットワーキングハードウェア９１０により実行されるコードであって、ネットワーキングハードウェア９１０にネットワーキングソフトウェアインスタンス９２２の部分として本発明の１つ以上の実施形態の動作を実行させる当該コード、を含むことができる。
【００７４】
特殊目的のネットワークデバイス９０２は、多くの場合、物理的に及び／又は論理的に、次を含むものと考えられる：１）制御通信及び構成モジュール９３２Ａ〜Ｒを実行する計算リソース９１２を含む（制御プレーンということもある）ＮＤ制御プレーン９２４、２）転送テーブル９３４Ａ〜Ｒ及び物理ＮＩ９１６を利用する転送リソース９１４を含む（転送プレーン、データプレーン又はメディアプレーンということもある）ＮＤ転送プレーン９２６。ＮＤがルータである（又はルータの機能性を実装している）例として、ＮＤ制御プレーン９２４（制御通信及び構成モジュール９２３Ａ〜Ｒを実行する計算リソース９１２）は、典型的には、データ（例えば、パケット）がどのようにルーティングされるべきか（例えば、当該データについてのネクストホップ及び当該データについてのアウトゴーイング物理ＮＩ）の制御と、転送テーブル９３４Ａ〜Ｒ内のルーティング情報の記憶とに関与する責任を有し、ＮＤ転送プレーンは、転送テーブル９３４Ａ〜Ｒに基づいて、物理ＮＩ９１６上でデータを受信し及び当該データを物理ＮＩ９１６のうちの適切なＮＩから外へ転送する責任を有する。
【００７５】
図９Ｂは、本発明のいくつかの実施形態に係る特殊目的のネットワークデバイス９０２を実装する例示的な手段を示している。図９Ｂは、（典型的には、ホットプラグ可能な）カード９３８を含む特殊目的のネットワークデバイスを示している。いくつかの実施形態では、それらカード９３８は２つのタイプ（（ラインカードと呼ばれることもある）ＮＤ転送プレーン９２６として動作する１つ以上、及び、（制御カードと呼ばれることもある）ＮＤ制御プレーン９２４を実装するように動作する１つ以上）からなる一方、代替的な実施形態は、単一のカードへ機能性を結合してもよく、及び／又は、追加的なカードタイプ（例えば、ある追加的なカードのタイプは、サービスカード、リソースカード、又はマルチアプリケーションカードと呼ばれる）を含んでもよい。サービスカードは、特殊化された処理（例えば、レイヤ４からレイヤ７のサービス（例えば、ファイアウォール、ＩＰｓｅｃ（Internet  Protocol  Security）、ＳＳＬ（Secure  Sockets  Layer）／ＴＬＳ（Transport  Layer  Security）、ＩＤＳ（Intrusion  Detection  System）、Ｐ２Ｐ（peer-to-peer）、ＶｏＩＰ（Voice  over  IP）、セッションボーダコントローラ、モバイルワイヤレスゲートウェイ（ゲートウェイＧＰＲＳ（General  Packet  Radio  Service）サポートノード（ＧＧＳＮ））、ＥＰＣ（Evolved  Packet  Core）ゲートウェイ））を提供することができる。例として、サービスカードは、ＩＰｓｅｃトンネルを終端させ、並びに付随する認証及び暗号化アルゴリズムを実行するために使用されてもよい。これらカードは、バックプレーン９３６として図示されている１つ以上の相互接続メカニズムを通じて互いに連結される（例えば、それらラインカードを連結する第１のフルメッシュ、及びカードの全てを連結する第２のフルメッシュ）。
【００７６】
図９Ａに戻ると、汎用目的のネットワークデバイス９０４は、（しばしばＣＯＴＳプロセッサである）１つ以上のプロセッサ９４２のセット及び（ネットワークインタフェースカードとしても知られる）ネットワークインタフェースコントローラ９４４（ＮＩＣ）、並びに、ソフトウェア９５０を記憶している非一時的なマシン読取可能な記憶媒体９４８、を備えるハードウェア９４０を含む。動作の期間中、プロセッサ９４２は、ソフトウェア９５０を実行して、（仮想マシンモニタ（ＶＭＭ）ということもある）ハイパーバイザ９５４とハイパーバイザ９５４により動作させられる１つ以上の仮想マシン９６２Ａ〜Ｒとをインスタンス化し、これらをまとめてソフトウェアインスタンス９５２という。仮想マシンは、仮想化されていない物理的なマシン上で稼働しているかのようにプログラムを実行する物理マシンのソフトウェア実装であり、アプリケーションは一般に、“そのままの（bare  metal）”ホスト電子デバイス上で稼働する場合とは対照的に、それらが仮想マシン上で稼働していることを知らない。但し、いくつかのシステムは、最適化の目的のためにオペレーティングシステム又はアプリケーションが仮想化の存在を認識することを可能とする準仮想化（para-virtualization）を提供する。仮想マシン９６２Ａ〜Ｒの各々及びハードウェア９４０の仮想マシンを実行する部分（当該仮想マシンに専用のハードウェア及び／又は当該仮想マシンにより他の仮想マシン９６２Ａ〜Ｒと時間的に共用されるハードウェアの時間スライスである）は別々の仮想ネットワークエレメント９６０Ａ〜Ｒを形成する。
【００７７】
仮想ネットワークエレメント９６０Ａ〜Ｒは、仮想ネットワークエレメント９３０Ａ〜Ｒと同等の機能性を実行する。例えば、ハイパーバイザ９５４は、仮想マシン９６２Ａにとってネットワーキングハードウェア９１０と同様に見える仮想オペレーティングプラットフォームを呈示し、仮想マシン９６２Ａは、制御通信及び構成モジュール９３２Ａ及び転送テーブル９３４Ａと同様の機能性を実装するために使用され得る（ハードウェア９４０のこの仮想化は、ネットワーク機能仮想化（ＮＦＶ）ということもある）。このように、ＮＦＶは、データセンタ、ＮＤ及び顧客構内機器（ＣＰＥ）内に位置することができる産業標準の大容量サーバハードウェア、物理スイッチ及び物理ストレージへと、多くのネットワーク機器タイプを集約するために使用されてよい。但し、本発明の様々な実施形態は、仮想マシン９６２Ａ〜Ｒの１つ以上を多様に実装してよい。例えば、本発明の実施形態は、各仮想マシン９６２Ａ〜Ｒが１つのＶＮＥ９６０Ａ〜Ｒに対応する形で図示されているが、代替的な実施形態は、より精細なレベルの粒度でこの対応関係を実装してもよく（例えば、ラインカード仮想マシンがラインカードを仮想化し、制御カード仮想マシンが制御カードを仮想化する、など）、理解されるべきこととして、ＶＮＥに対する仮想マシンの対応関係を参照しながらここで説明した技法は、より精細なレベルのそうした粒度が使用される実施形態にも当てはまる。
【００７８】
ある実施形態において、ハイパーバイザ９５４は、物理イーサネットスイッチと同様の転送サービスを提供する仮想スイッチを含む。具体的には、仮想スイッチは、仮想マシンとＮＩＣ９４４との間、及びオプションとして仮想マシン９６２Ａ〜Ｒの間でトラフィックを転送し、加えて、この仮想スイッチは、（例えば、仮想ローカルエリアネットワーク（ＶＬＡＮ）を履行することにより）互いに通信することをポリシー上許可されないＶＮＥ９６０Ａ〜Ｒの間のネットワーク分離を実施してもよい。
【００７９】
ソフトウェア９５０は、プロセッサ９４２により実行された場合にプロセッサ９４２に仮想マシン９６２Ａ〜Ｒの一部として本発明の１つ以上の実施形態の動作を実行させるコード、を含むことができる。
【００８０】
図９Ａにおける第３の例示的なＮＤ実装は、単一のＮＤ又はＮＤ内の単一のカードに、カスタムＡＳＩＣ／プロプライエタリＯＳ及びＣＯＴＳプロセッサ／標準ＯＳの双方を含む、ハイブリッドネットワークデバイス９０６である。そうしたハイブリッドネットワークデバイスのある実施形態において、プラットフォームＶＭ（即ち、特殊目的のネットワークデバイス９０２の機能性を実装するＶＭ）は、ハイブリッドネットワークデバイス９０６内に存在するネットワーキングハードウェアへ準仮想化を提供し得る。
【００８１】
ＮＤの上述した例示的な実装に関わらず、ＮＤにより実装される複数のＶＮＥのうちの単一のＶＮＥが考慮される（例えば、ＶＮＥのうちの１つのみが所与の仮想ネットワークの一部である）場合、又は、ＮＤにより単一のＶＮＥのみがその時点で実装されている場合、ＶＮＥへ言及するために短縮された用語であるネットワークエレメント（ＮＥ）が使用されることもある。また、上述した例示的な実装の全てにおいて、ＶＮＥ（例えば、ＶＮＥ９３０Ａ〜Ｒ、ＶＮＥ９６０Ａ〜Ｒ、及びハイブリッドネットワークデバイス９０６内のＶＮＥ）の各々は、物理ＮＩ（例えば、９１６、９４６）上でデータを受信し、当該データを物理ＮＩ（例えば、９１６、９４６）のうちの適切な１つから外へ転送する。例えば、ＩＰルータの機能性を実装するＶＮＥは、ＩＰパケット内のＩＰヘッダ情報のいくつかに基づいてＩＰパケットを転送する。ＩＰヘッダ情報は、ソースＩＰアドレス、宛て先ＩＰアドレス、ソースポート、宛て先ポート（ここで、“ソースポート”及び“宛て先ポート”は、ＮＤの物理ポートとは異なり、プロトコルポートを指す）、トランスポートプロトコル（例えば、ＵＤＰ（user  datagram  protocol）、ＴＣＰ（Transmission  Control  Protocol）及びＤＳＣＰ（differentiated  service）、を含む。
【００８２】
ネットワークインタフェース（ＮＩ）は、物理的であっても又は仮想的であってもよく、ＩＰの文脈では、物理ＮＩか仮想ＮＩかに関わらず、インタフェースアドレスはＮＩへ割り当てられるＩＰアドレスである。仮想ＮＩは、物理ＮＩ若しくは他の仮想インタフェースに関連付けられてもよく、又は単独で存在してもよい（例えば、ループバックインタフェース、ポイントツーポイントプロトコルインタフェース）。ＮＩ（物理又は仮想）は、番号を付与され（ＩＰアドレス有りのＮＩ）又は付与されない（ＩＰアドレス無しのＮＩ）。ループバックインタフェース（及びそのループバックアドレス）は、管理目的でしばしば使用される、ＮＥ／ＶＮＥ（物理又は仮想）の特定のタイプの仮想ＮＩ（及びＩＰアドレス）であり、そうしたＩＰアドレスをノーダルループバックアドレスという。ＮＤのＮＩへ割り当てられたＩＰアドレスをそのＮＤのＩＰアドレスといい、より粒度の高いレベルでは、ＮＤ上に実装されるＮＥ／ＶＮＥへ割り当てられたＩＰアドレスを当該ＮＥ／ＶＮＥのＩＰアドレスということができる。
【００８３】
これまでの詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビットに対するトランザクションのアルゴリズム的でシンボリックな表現の観点で呈示されている。それらアルゴリズム的な説明及び表現は、当業者がその作業の実体を他の当業者へ最も効率よく伝達するためにデータ処理分野において用いられている手法である。ここで、及び一般に、アルゴリズムは、所望の結果を導くトランザクションの首尾一貫したシーケンスとして想起される。トランザクションは、物理的な量の物理的な操作を要するものである。通常、必須ではないものの、それら量は、記憶し、移送し、結合し、比較し、及びさもなければ操作することの可能な電気的又は磁気的な信号の形態をとる。時には、共通的な用途を理由として、それら信号を、ビット、値、エレメント、シンボル、文字、用語又は数などとして言及することが簡便であることが分かっている。
【００８４】
しかしながら、念頭に置くべきこととして、それら及び同様の用語の全ては、適切な物理的な量に関連付けられるべきであり、それら量に適用される単に便宜上のラベルに過ぎない。上の議論から明白な別段の記述がなければ、本説明を通じて、“処理（processing）”、“計算（computing若しくはcalculating）”、“判定若しくは決定（determining）”又は“表示（displaying）”などの用語を利用した議論は、コンピュータシステム又は同様の電子コンピューティングデバイスのアクション及びプロセスであって、コンピュータシステムのレジスタ及びメモリ内の物理的な（電子的な）量として表現されるデータをコンピュータシステムのメモリ、レジスタ、又はそうした情報記憶、伝送若しくは表示デバイス内の物理量として同様に表現される他のデータへ操作変換する当該アクション及びプロセスへの言及である。
【００８５】
ここで呈示されたアルゴリズム及びディスプレイは、いかなる具体的なコンピュータ又は他の装置にも本質的には関連しない。ここでの教示に従うプログラムと共に多様な汎用目的のシステムを使用してもよく、又は、所要の方法のトランザクションを実行するための、より専門化された装置を構築することが便利であることが分かるかもしれない。多様なこれらシステムのための所要の構造は、上の説明から明白であろう。加えて、本発明の実施形態は、どういった具体的なプログラミング言語を基準として説明されてもいない。理解されるであろうこととして、多様なプログラミング言語がここで説明した通りの本発明の実施形態の教示を実装するために使用されてよい。
【００８６】
ここまでの明細書において、本発明の実施形態を、具体的で例示的な実施形態を参照しながら説明した。以下の特許請求の範囲に示されている通りの本発明のより広範な思想及びスコープから逸脱することなく、それらに対し多様な修正をなし得ることが明らかであろう。従って、本明細書及び図面は、限定的な意味ではなくむしろ例示的な意味で受け取られるべきである。
【００８７】
本説明を通し、本発明の実施形態がフロー図を通じて呈示されている。理解されるであろうこととして、それらフロー図に記述されているトランザクションの順序及びトランザクションは、単に例示の目的を意図しており、本発明の限定を意図してはいない。当業者は、以下の特許請求の範囲に示されている通りの本発明のより広範な思想及びスコープから逸脱することなく、フロー図について派生を導くことができることを認識するであろう。
【図１】
0006479169.tif 000002
【図２】
0006479169.tif 000003
【図３】
0006479169.tif 000004
【図４】
0006479169.tif 000005
【図５】
0006479169.tif 000006
【図６】
0006479169.tif 000007
【図７】
0006479169.tif 000008
【図８】
0006479169.tif 000009
【図９Ａ】
0006479169.tif 000010
【図９Ｂ】
0006479169.tif 000011