(57)【特許請求の範囲】
【請求項１】
ネットワークドメイン・エッジノードに動的に結合し、様々なQoS制御管理機能を実行する帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法であって、
前記帯域幅ブローカに動的に結合したネットワークＱｏＳ状態データベースを設け、
前記帯域幅ブローカにより、前記ネットワークドメイン・エッジノードから前記パスに対するフローリクエストを受取り、
前記パスがクリティカルな状態になく、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、帯域幅ブローカによりその未使用の帯域幅を使ってフローリクエストに応じ、
前記パスがクリティカルな状態になく、前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記帯域幅ブローカにより前記パスに沿って各リンクにリンクにとって使用可能な帯域幅から帯域幅の割当て分を割当て、そして
前記パスがクリティカルな状態にある場合、前記帯域幅ブローカにより、１組のクリティカルリンクの各リンクに、リンクごとに別のパスから再請求された帯域幅からの未使用の帯域幅からの帯域幅を割当てる、
というステップを備え、
前記ネットワークＱｏＳ状態データベースは、
前記パスに割当てられた未使用の帯域幅と、
前記パスに沿った１組のクリティカルリンクと、
パス状態とを含む、前記ネットワークドメイン内のパスのためのパスレベルデータと、
前記パスに沿ったリンクのためのパス状態を含むネットワークドメイン内部のパスに関するパスレベルデータと、
リンクにとって使用可能な帯域幅の割当て分と、
リンク状態と
を含むことを特徴とする、帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、帯域ブローカによってネットワークドメイン内部で帯域を割り当てる方法に関する。
【０００２】
【従来の技術】
ネットワークドメインは、ネットワークドメイン全体を対象としてネットワークサービス品質（ＱｏＳ）状態を維持し、アドミッション制御、資源リザベーション、プロビジョニングなど様々なＱｏＳ制御管理機能を実行する責任を負う特殊なネットワークサーバ（ここでは帯域幅ブローカと呼ぶ）を持つことがある。ＱｏＳプロビジョニングの制御管理を行う集中型帯域幅ブローカは、ＱｏＳ制御面の複雑性を減じることがある。
【０００３】
ＱｏＳ制御管理を行う集中型帯域幅ブローカは、アピールするいくつかの特徴を有する。例えば、集中型帯域幅ブローカは、ＱｏＳ制御面をデータ面から切り離すことがある。特に、アドミッション制御やＱｏＳ状態維持などのＱｏＳ制御機能は、データ面内部に置かれたネットワークドメインのコアルータから除かれ、それで、コアルータの複雑性は減じられる。その結果、パスに沿ったリザベーション準備のためのホップバイホップ方式（バケツリレー方式）の信号伝送が無くされ、それにより、信号伝送オーバヘッドがコアルータから除かれることになる。その上、ネットワークＱｏＳ状態が帯域幅ブローカによって集中的に管理され得るので、制御状態が信頼できない、または一貫していないという問題は回避され得る。この点に関して、集中型帯域幅ブローカは、ＱｏＳ制御管理の代わりにスケーラビリティのある方式を提供し得る。
【０００４】
【発明が解決しようとする課題】
しかしながら、ＱｏＳ制御管理を行う集中型帯域幅ブローカはまた、それ自身のスケーラビリティの問題、特に、大量のフローをネットワークシステムのスケールとして扱うことができるか否かという問題も呈する。ゆっくりした時間スケール、静的資源プロビジョニングおよびトラフィックエンジニアリング（例えば、仮想私設網をセットアップすべく実行されるもの）しか実行されないネットワークでは、スケーラビリティの問題は深刻でないかもしれない。しかし、今日のインターネットの急速な発達に伴い、ボイス・オーバーＩＰ（ＶｏＩＰ）、オンデマンド・メディアストリーミング、リアルタイム・コンテンツデリバリ（例えばストック・クォーツやニュース）など、たくさんの新しいアプリケーションやサービスが、フロー到着／出発の時間スケールでアドミッション制御や資源プロビジョニングなど動的なＱｏＳ制御管理を要求するかもしれない。こうした環境の中で、集中度の不十分な帯域幅ブローカシステムが潜在的なネックとなり、そこで、ネットワークシステム自体の負荷容量にまだ余裕があるのに、このネットワークシステムに収容できるフローの数が制限されることになりかねない。
【０００５】
スケーラビリティのスケールのひとつは、帯域幅ブローカシステムがネットワークシステムのサイズ増大に応じて大量のフローリザベーションリクエストを処理できることである。例えば、ネットワークリンク容量が増大するにつれて、帯域幅ブローカシステムの呼出し処理能力（ここに、帯域幅ブローカシステムが単位時間当たり処理できるフローリクエストの数と定義する）はそれに比例して増え、これに伴い、ネットワークシステムに収容できるフローの数が増えることが望ましい。特に、帯域幅ブローカは、ネットワークが過負荷に至らないうちにネックにならないことが望ましい。
【０００６】
より大きい処理パワーを単純に追加し、またはメモリ／ディスクアクセス速度を上げることによって、帯域幅ブローカの呼出し処理能力を増強することは可能かもしれないが、このようなそれ自体の中でのアプローチでは、スケーラビリティのある帯域幅ブローカを提供できないかもしれない。帯域幅ブローカの呼出し処理能力に影響し得るファクターはたくさんある。なかでも、メモリ／ディスクアクセス速度は顕著な役割を演じる。フロー・リザベーション・セットアップ・リクエストを処理するとき、帯域幅ブローカはアドミッシビリティテストを実行し、リクエストが許諾できるものであれば、帯域幅ブローカは関連のＱｏＳ状態を更新する。同様に、フロー・リザベーション・ティアダウン・リクエストを処理するとき、帯域幅ブローカは関連のＱｏＳ状態を更新する。どちらのケースにおいても、ＱｏＳ状態へのアクセスおよび／または更新が含まれる。メモリ／ディスクアクセス速度は代表的に処理速度よりはるかに低いので、フローリクエストの処理時間は、大部分、メモリ／ディスクアクセスの数と更新の数によって決められる。
【０００７】
集中型帯域幅ブローカの全体の呼出し処理能力に影響し得る別のファクターが、集中型帯域幅ブローカと各種エッジルータの間の通信チャネルの容量（例えばネットワーク帯域幅または入出力帯域幅）である。フローの数が増すにつれて、この通信チャネルがネックになり、集中型帯域幅ブローカシステムに送られるフローリクエストを制限し、それによって、集中型帯域幅ブローカの全体の呼出し処理能力を低下させることがあり得る。ネットワークシステムのデマンドをもってスケールを決めるために、分散型多重帯域幅ブローカのアーキテクチャが要求されることもあり得る。
【０００８】
【課題を解決するための手段】
本発明の一態様では、ネットワークドメイン・エッジノードに動的に結合し、様々なQoS制御管理機能を実行する帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法であって、帯域幅ブローカに動的に結合したネットワークＱｏＳ状態データベースを設け、帯域幅ブローカにより、ネットワークドメイン・エッジノードからパスに対するフローリクエストを受取り、パスがクリティカルな状態になく、パスがフローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、帯域幅ブローカによりその未使用の帯域幅を使ってフローリクエストに応じ、パスがクリティカルな状態になく、フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、帯域幅ブローカによりパスに沿って各リンクにリンクにとって使用可能な帯域幅から帯域幅の割当て分を割当て、そしてパスがクリティカルな状態にある場合、帯域幅ブローカにより、１組のクリティカルリンクの各リンクに、リンクごとに別のパスから再請求された帯域幅からの未使用の帯域幅からの帯域幅を割当てる、というステップを備え、ネットワークＱｏＳ状態データベースは、パスに割当てられた未使用の帯域幅と、パスに沿った１組のクリティカルリンクと、パス状態とを含む、ネットワークドメイン内のパスのためのパスレベルデータと、パスに沿ったリンクのためのパス状態を含むネットワークドメイン内部のパスに関するパスレベルデータと、リンクにとって使用可能な帯域幅の割当て分と、リンク状態とを含むことを特徴とする、帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法が提供される。
【００１４】
【発明の実施の形態】
以下、本発明の諸々の特徴、態様および利点を添付図面に則して詳細に説明する。
【００１５】
図１は、ネットワークドメインのＱｏＳプロビジョニングの管理および制御のための集中型帯域幅ブローカの一実施例を示す。ネットワークドメイン1０は、コアノード1２によって例示されたような、複数の動的に結合したコアノードによって定義されている。それぞれのコアノードは、エッジノード1４によって例示されたようなエッジノードを介して他のドメインに動的に結合している。帯域幅ブローカデータ処理システム1６が、帯域幅ブローカホストと、帯域幅ブローカを実現させるプログラミング命令1８を含む。
【００１６】
図２は、帯域幅ブローカホストとして使用するのに適した汎用コンピュータのハードウェアアーキテクチャ図である。プロセッサ２００は、中央処理装置（ＣＰＵ）２1０、メモリキャッシュ２２０、およびバスインタフェース２３０を含み、システムバス２５０を介してメインメモリ２４０および入出力制御装置２４５に動的に結合している。入出力インタフェース制御装置は、入出力ローカルバス２５０を介してディスク記憶装置コントローラ２９５およびネットワークコントローラ２８０に動的に結合している。
【００１７】
ディスク記憶装置コントローラは、ディスク記憶装置２５５に動的に結合している。帯域幅ブローカを実現させるためのコンピュータプログラム命令２９７は、プロセッサがこのコンピュータプログラム命令を検索し、メインメモリに保存するまで、ディスク記憶装置に保存されている。プロセッサは、次に、帯域幅ブローカの特徴を実現させるべく、メインメモリに保存されたコンピュータプログラム命令を実行する。
【００１８】
ネットワークコントローラは、通信デバイス２９６に動的に結合している。通信デバイスは、汎用コンピュータをホストとした帯域幅ブローカを、インターネットなどのコンピュータネットワークを介してユーザクライアントなどの他のソフトウェア対象と通信できるようにするのに使用される。
【００１９】
再び図１について説明すると、帯域幅ブローカは、エッジノード1４によって例示されたようなネットワークドメインを定義する複数のエッジノードに動作可能な形で結合している。コアノードとエッジノードのネットワークは、データフローが通過するデータプレーン1０を定義する。帯域幅ブローカは、データプレーンを通過するデータフローの制御のためのシステムおよびデータを含む制御プレーン２２を占有する。帯域幅ブローカシステムは更に、ネットワーク・トポロジー・データベース（図示されていない）と、帯域幅ブローカに動作可能な形で結合したネットワークＱｏＳ状態データベース２６を含む。
【００２０】
ネットワーク・トポロジー・データベースとネットワークＱｏＳ状態データベースは共に、ネットワークドメインとその状態の論理的表現（ここではＱｏＳ抽象化と呼ぶ）を提供する。このネットワークドメインのＱｏＳ抽象化をもって、帯域幅ブローカは、これらデータベースの管理および更新によるＱｏＳ制御機能を実行する。これによって、ネットワークドメインのＱｏＳ制御プレーンは、ネットワークドメインのデータプレーンから切り離される。ネットワークドメインのコアルータは、ＱｏＳ制御プレーンから外される。なぜなら、コアルータは、パー・フローであろうと、ひとかたまりであろうと、ＱｏＳリザベーション状態を一切維持せず、アドミッション制御などのＱｏＳ制御機能を一切実行しないからである。
【００２１】
ネットワークＱｏＳ状態は、帯域幅ブローカによってネットワークＱｏＳ状態データベースにおける２つのレベルで表現される。すなわち、リンクレベル２８とパスレベル３０である。リンクレベルでは、帯域幅ブローカは、リンクのリザーブされた全帯域幅と使用可能な帯域幅を含めて、ネットワークドメインの各リンクのＱｏＳ状態に関する情報を維持する。パスレベルでは、帯域幅ブローカは、パスのリンクＱｏＳ状態から抽出され、“要約”されたネットワークドメインの各パスのＱｏＳ状態に関する情報を維持する。パスＱｏＳ状態の1つの例は、パスに沿った使用可能帯域幅で、これが、そのリンク全部の中の最小限使用可能な帯域幅である。別個のパスレベルＱｏＳ状態を維持することによって、帯域幅ブローカは、そのパスに沿ったルートを辿るフローについて高速アドミッシビリティテストを行うことができる。その上、要約されたパスＱｏＳ状態をベースにしてパス方式の資源最適化を行うこともできる。最終的に、リンクＱｏＳ状態とパスＱｏＳ状態の両方が、リンクとパスに関するひとかたまりのＱｏＳ状態となる。パー・フローＱｏＳ状態をネットワークＱｏＳ状態データベースの中で維持する必要はない。各フローに関するＱｏＳ状態情報および他の制御状態情報、例えばフローのＱｏＳ要求に関する情報、リザーブされた帯域幅に関する情報などは、帯域幅ブローカに動的に結合され且つ帯域幅ブローカによって管理される別個のフロー情報データベース（図示されていない）の中で維持される。
【００２２】
帯域幅ブローカは、アドミッション制御を実行するためにダイナミック帯域幅割当てメカニズム（ここでは、パス指向、割当て分ベースのダイナミック帯域幅割当て（ＰｏＱ）と呼ぶ）を使用する。ＰｏＱは、帯域幅ブローカによって使用されるネットワークＱｏＳ状態を２レベルで表現したもので、フロー・リザベーション・セットアップ・リクエストまたはフロー・リザベーション・ティアダウン・リクエストが処理されるたびにリンクＱｏＳ状態がアクセスされ、更新されるのを回避する。ＰｏＱのもとで、ネットワークの各リンクの全帯域幅は個々別々の帯域幅分（ここでは割当て分と呼ぶ）に分割される。1つの割当て分は、代表的なフローに要求される平均帯域幅より大きい。
【００２３】
パスに沿ったリンクが十分な割当て分を残さなかった場合、そのパスに関する割当て分の割当ては失敗することがある。この場合は、そのパスに関する帯域幅割当てが、ここでクリティカル状態と呼ぶところの状態に入る。もっと一般的には、リンクの使用可能な割当て分が閾値を下回るとき（例えば、割当て分がまったく残されなかったとき）、そのリンクは、ここでクリティカルリンクと呼ばれ、クリティカル状態にある。リンクがクリティカル状態にあるとき、そのリンクを横切る全部のパスがクリティカル状態に入る。ひとたびパスがクリティカル状態に入ると、帯域幅ブローカは、そのパスに沿って割当て分単位で帯域幅を割当てるのを止める。代わりに、パー・フローをベースにして帯域幅の割当てまたは割当て解除が行われる。特に、帯域幅ブローカは、クリティカルリンクごとに精確なリンクＱｏＳ状態を維持する（例えば、リンクにおいてリザーブされた精確な帯域幅分を）。これで、クリティカル状態にあるパスについてフロー・リザベーション・セットアップ・リクエストまたはフロー・リザベーション・ティアダウン・リクエストを処理するとき、帯域幅ブローカはそのクリティカルパスに沿ったクリティカルリンクのリンクＱｏＳ状態にアクセスし、これを更新する。この帯域幅ブローカによるリンク更新アドミッション制御スキームへの切替えにより、フロー・リザベーション・セットアップ・リクエストが無駄に拒絶されることは無くなる。
【００２４】
同様に、パスに対するフロー・リザベーション・ティアダウン・リクエストが到着すると、帯域幅ブローカは、そのパスのＱｏＳ状態を更新する（すなわち、そのパスのリザーブされた実際の帯域幅が、フローのためにリザーブされた分だけ減じられる）。
【００２５】
図８は、本発明による帯域幅ブローカの一実施例における割当てプロセスの一例を描いた図である。帯域幅ブローカが、ステップ８００においてパスに対するフローリクエストを受取る。ステップ８０２において、帯域幅ブローカは、パスレベルデータベース８０４を使ってフローリクエストに応じるのに十分な割当て分がパスに割当てられているかどうか判定する。十分であれば、帯域幅ブローカはフローを許可し、フローリクエストをパスに割当て、パスレベルデータベースを更新する。帯域幅ブローカは、ステップ８０２においてフローリクエストに応じるのに十分な割当て分がパスに割当てられていないと判定した場合、ステップ８０６においてリンクレベルデータベース８０８を使ってフローをパスに割当てる。帯域幅ブローカは、自ら、ステップ８1０においてフローをパスに割当てるのに成功したかどうか判定する。成功したのであれば、帯域幅ブローカは、ステップ８1２においてフローを許可する。フローをパスに割当てるのに成功しなかった場合、帯域幅ブローカは、ステップ８1４においてフローを拒絶する。
【００２６】
本発明による帯域幅ブローカの一実施例によって使用されたＰｏＱプロセスのより詳細な例を図３、図４および図５に示す。擬似コード内部で使用される記号を下記の表１にまとめる。
【００２７】
【表１】
0003987394.tif 000002
【００２８】
図３は、フロー・リザベーション・セットアップおよび割当て分割当て管理の目的でＰｏＱを使用する帯域幅ブローカのためのパス・レベル・アドミッション制御プロセスの一例についての記述である。ノーマルモードの間、帯域幅ブローカは、1つ時に1つの割当て分の単位で帯域幅の割当てと割当て解除を行う。パスのパスレベルＱｏＳ状態は、そのパスに沿ったルートを辿るフローについてリザーブされた実際の帯域幅に加えて、そのパスに割当てられた帯域幅の割当て分の数を維持する。パスに沿ったフローに対するフロー・リザベーション・セットアップ・リクエストが到着すると、帯域幅ブローカは、そのパスがノーマル状態にあるかどうか、また、そのパスに割当てられた未使用の帯域幅がステップ３００においてフローリクエストに応じるのに十分であるかどうか判定する。その通りであれば、フローリクエストは受入れられ、従って、当該のパスＱｏＳ状態はステップ３０２において更新される（すなわち、パスに沿った実際のリザーブされた帯域幅は、フローリクエストの分だけ増やされる）。
【００２９】
帯域幅ブローカは、ステップ３０４において、パスに割当てられた帯域幅がフローリクエストに応じるのに不十分であると判定すると、ステップ３０６においてフローリクエストを受入れるべく、新しい割当て分をパスに割当てようとする。そうするために、帯域幅ブローカは、後述のプロセスにおいてパスに沿った各リンクに対して新しい割当て分割当てをリクエストする。
【００３０】
帯域幅ブローカは、ステップ３０８において、パスがクリティカル状態にあると判定すると、ステップ３1０においてパスクリティカルリンクのリストの中の各リンクに対してより大きい帯域幅を割当てられるようリクエストする。ステップ３1２において帯域幅ブローカによって判定された通り、各リンクｌがパスクリティカルリンクのリストの中にないとき、帯域幅ブローカは、パスの割当てられた割当て分が十分であるかどうか判定し、そのパスの割当てられた割当て分が十分でない場合、後述のプロセスにおいてより多くの割当て分をリクエストする。
【００３１】
フローリクエストを処理した後、帯域幅ブローカは、帯域幅ブローカの帯域幅および割当て分のリクエストの全部がステップ３1６において承諾されたかどうか判定する。帯域幅ブローカの帯域幅および割当て分のリクエストの全部が承諾された場合、帯域幅ブローカは、パスに割当てられた割当て分を更新し、パスに沿ってリザーブされた合計レートの分を更新し、ステップ３２０においてフローリクエストを受入れる。ステップ３1６において、帯域幅ブローカの帯域幅および割当て分のリクエストの全部が承諾されたのでないと判定すると、帯域幅ブローカは、ステップ３２２においてフローリクエストを拒絶する。
【００３２】
図４は、本発明による帯域幅ブローカの一実施例において使用されるリンクレベル帯域幅割当て／割当て分割当て管理プロセスの一例についての記述である。このプロセスでは、リンク１に対してリクエストされたフローｒpを割当てる。可能な第１のケースの場合、ステップ４００において、帯域幅ブローカは、リンクがノーマル状態にあるかどうか、また、リクエストされたフローがリンクの使用可能な割当て分より大きいかどうか、判定する。その通りであれば、帯域幅ブローカは、ステップ４０２においてリンク1で全部のパスから未使用の帯域幅を再請求する。リンク1で全部のパスから未使用の帯域幅を再請求した後、帯域幅ブローカは、再請求された帯域幅の分がステップ４０４においてフローリクエストに応じるのに十分であるかどうか判定する。十分でなければ、フローリクエストは拒絶される。
【００３３】
可能な第２のケースの場合、ステップ４０６において、帯域幅ブローカは、リンクがクリティカル状態にあるかどうか、また、リンク1で全部のパスから再請求された未使用の帯域幅の分がリクエストされたフローより少ないかどうか、判定する。その通りであれば、帯域幅ブローカはリクエストを拒絶する。第1のケースにおいてフローリクエストに応じるのに十分な帯域幅を自ら再請求できるならば、帯域幅ブローカは、ステップ４０８においてリンクがノーマル状態にあるかどうか判定する。その通りであれば、帯域幅ブローカは、ステップ４1０においてリンクの状態をクリティカル状態にセットする。リンクの状態をクリティカル状態にセットしたならば、帯域幅ブローカは、ステップ４1２においてそのリンクがどのパスに属するか判定する。そのリンクが属する各パスについて、帯域幅ブローカは、パスのクリティカルリンクのリストにそのリンクを追加し、ステップ４1４においてパスのレベルを1つだけ上げる。
【００３４】
リンクの使用可能な割当て分がフローリクエストに応じるのに十分であったため、自らフローリクエストに応じることができた場合、帯域幅ブローカは、ステップ４1６においてリンクの使用可能な割当て分を減らす。クリティカル状態にあるリンクに対するフローリクエストに自ら応じることができた場合、帯域幅ブローカは、ステップ４1８において使用可能なリンク帯域幅をフローリクエストの分だけ減らす。
【００３５】
図５は、本発明による帯域幅ブローカによるフロー出発ハンドリングのためのリンクレベル帯域幅／割当て分管理プロセスの一例についての記述である。フローｆがパスｐを出発するとき、帯域幅ブローカは、ステップ５００において、そのパスに沿ってリザーブされた帯域幅の分を出発したフローに対して再請求する。帯域幅ブローカは、ステップ５０２においてパスがクリティカル状態にあるかどうか判定する。その通りであれば、ステップ５０４において帯域幅ブローカによって判定された通り、パスのクリティカルリンクのリストの中の各リンクｌに対して、帯域幅ブローカは、先に出発したフローに割当てられた帯域幅の分を再請求し、ステップ５０６においてリンクの割当てられた割当て分を再計算する。
【００３６】
再計算されたリンクの割当て分割当てが新しいフローリクエストを受入れるのに十分である、すなわち、リンクへの割当て分割当てがゼロより大きいと自ら判定した場合、帯域幅ブローカは、ステップ５1０においてリンクの状態をクリティカルからノーマルにリセットする。ステップ４1２において帯域幅ブローカによって判定された通り、そのリンクが属する各パスｐ’について、帯域幅ブローカは、ステップ５1４においてパスｐ’のクリティカルパスレベルを下げる。帯域幅ブローカは、次に、ステップ５1６においてパスｐ’のクリティカルリンクのリストからリンクを除去する。
【００３７】
ステップ５０２においてパスがクリティカル状態にあると自ら判定した場合、帯域幅ブローカは、ステップ５1８においてそのパスに過剰な割当て分が割当てられているかどうか判定する。その通りであれば、そのパスの過剰な割当て分は、ステップ５２０においてパスから除去される。ステップ５２２において帯域幅ブローカによって判定された通り、そのパスにおける各リンクｌについて、帯域幅ブローカは、リンクにおいて使用可能な割当て分の数を増やすことによって、パスに沿って各リンクに余分の割当て分を戻す。
【００３８】
本発明による帯域幅ブローカの別の実施例では、単一の帯域幅ブローカを使用する集中型帯域幅ブローカのアーキテクチャが、多重帯域幅ブローカ（ＭＢＢ）を使用する階層分散型帯域幅ブローカのアーキテクチャに拡張されている。ＭＢＢアーキテクチャは、ネットワークドメイン内部で帯域幅を割当てるのにＰｏＱを使用してよい。
【００３９】
図６は、本発明によるＭＢＢアーキテクチャの一例を描いた図である。階層分散型ＭＢＢアーキテクチャは、先に述べたネットワークＱｏＳ状態を２レベルで表現したＰｏＱアーキテクチャを含む。ＭＢＢアーキテクチャは、中央帯域幅ブローカ６００と、この中央帯域幅ブローカに動的に結合した、エッジ帯域幅ブローカ６０２によって例示された通りの複数のエッジ帯域幅ブローカから構成される。中央帯域幅ブローカは、先に述べたリンクＱｏＳ状態データベース６０４を維持し、複数のエッジ帯域幅ブローカの中の割当て分の割当てと割当て解除を管理する。複数のエッジ帯域幅ブローカの各々が、パスＱｏＳ状態のサブセットを管理し、例示的なエッジノード６０６のような動的に結合したエッジノードを通してパスに関するアドミッション制御を実行する。エッジ帯域幅ブローカの数は、ネットワークドメインのサイズに応じて変わり得る。例えば、図６に示す通り、エッジルータごとに1つのエッジ帯域幅ブローカを設けることができ、また、各エッジ帯域幅ブローカがエッジルータのところで場所を共有することもできる。
【００４０】
図７は、本発明による分散型帯域幅ブローカの一実施例における動作シーケンスの一例を描いた図である。一パスのための一フローがエッジノード６０６に到着すると、エッジノード６０６は、フローアドミッションリクエスト７００をエッジ帯域幅ブローカ６０２に伝送する。エッジ帯域幅ブローカは、パスレベルデータベース６０５からパスレベルデータ７０２を受取る。エッジ帯域幅ブローカ７０４は、先に述べた通りのパスデータに基づいてアドミッション制御決定を下す。フローリクエストを承諾した場合、エッジ帯域幅ブローカは、フローアドミッション７1８をエッジノードに伝送し、フローのパスＱｏＳ状態を更新７1６することによって、そのフローを許可する。
【００４１】
パスにおいて使用可能な帯域幅が十分でない場合、エッジ帯域幅ブローカは、中央帯域幅ブローカ６００からそのパスのための新しい割当て分を取得できるようリクエスト７０６を伝送する。割当て分リクエストが受入れられない場合（すなわち、使用可能な割当て分が中央帯域幅ブローカにもはや存在しない場合）中央帯域幅ブローカは、リンクレベルデータベース６０４からリンクレベルデータ７０８を取得し、先に述べたパー・フロー・リンク更新スキームを使ってアドミッション制御７1０を実行する。割当てに成功した場合、中央帯域幅ブローカは、リンクレベルデータ更新７1２をリンクレベルデータベースに伝送し、帯域幅割当て７1４をエッジ帯域幅ブローカに伝送する。
【００４２】
本発明によるＭＢＢアーキテクチャの一実施例では、ＭＢＢアーキテクチャは、ネットワークドメイン内部で帯域幅を割当てるために、改良されたＰｏＱ（ここでは、不可逆パスＰｏＱと呼ぶ）を使用する。不可逆パスＰｏＱスキームの内部で、割当て分リクエストが受入れられないとき、エッジ帯域幅ブローカは、先に述べたパー・フロー・リンク更新スキームを使って、リンクレベルアドミッションのために中央帯域幅ブローカにフローリクエストを通す代わりに、フローリザベーションリクエストを拒絶する。
【００４３】
以上、本発明をある特定の実施例に則して説明したが、なお多数の改良形態および変更形態のあることが当業者には明白であろう。よって、本発明は、ここに述べた以外の仕方で実施されてよいことを理解されたい。従って、ここに開示された本発明の実施例は、あらゆる点において例示的であり、本発明の範囲に制限を加えないものとみなされたい。本発明の範囲は、本文よりむしろ、本出願によって支持された請求項および請求項の均等物によって特定されるものとする。
【００４４】
（付記１）  ネットワークドメイン・エッジノードに動的に結合したネットワークサーバ帯域ブローカによってネットワークドメイン内部で帯域幅を割当てる方法であって、
前記ネットワークドメイン内部のパスのためのパスレベルデータおよびリンクレベルデータを含み、前記ネットワークサーバ帯域ブローカに動的に結合したデータベースを設け、
前記ネットワークサーバ帯域ブローカにより、前記ネットワークドメイン・エッジノードから前記パスのためのフローリクエストを受取り、そして
前記ネットワークサーバ帯域ブローカが前記パスレベルデータを使って前記フローリクエストに応じることができないと判定した場合、前記ネットワークサーバ帯域ブローカは前記リンクレベルデータを使ってフローリクエストに応じる、
ことを特徴とするパケットネットワークにおける帯域幅ブローカのための割り当て方法。
【００４５】
（付記２）  前記パスレベルデータが、前記パスおよびパス状態に割当てられた未使用の帯域幅を含み、更に、前記パスがクリティカルな状態になく、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、前記ネットワークサーバ帯域ブローカによりその未使用の帯域幅を使って前記フローリクエストに応じることを特徴とする、付記１に記載の方法。
【００４６】
（付記３）  前記リンクレベルデータは更に、リンクにとって使用可能な帯域の複数の割当て分を含み、更に、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記ネットワークサーバ帯域幅ブローカにより、前記パスに沿って各リンクに、前記リンクにとって使用可能な帯域幅の割当て分から帯域幅の一つの割当て分を割当てることを特徴とする、付記２に記載の方法。
【００４７】
（付記４）  前記リンクレベルデータは更にリンク状態を含み、前記パスレベルデータは更に前記パスに沿って１組のクリティカルリンクを含み、前記方法は更に、前記ネットワークサーバ帯域幅ブローカにより、前記１組のクリティカルリンクの中の各リンクに、未使用の帯域幅のうち、リンクごとに別のパスから再請求された帯域幅を割当てることを特徴とする付記３に記載の方法。
【００４８】
（付記５）  中央ネットワークサーバ帯域幅ブローカおよび複数のエッジネットワークサーバ帯域幅ブローカを含む分散型ネットワークサーバ帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法であって、
前記ネットワークドメイン内部のパスのためのパスレベルデータを含み、前記複数のエッジネットワークサーバ帯域幅ブローカに動的に結合した複数のパスレベルデータベースを設け、
前記ネットワークドメイン内部のパスに沿ったリンクのためのリンクレベルデータを含み、中央ネットワークサーバ帯域幅ブローカに動的に結合したリンクレベルデータベースを設け、
前記分散型ネットワークサーバ帯域幅ブローカによって、一つのエッジネットワークサーバ帯域幅ブローカに動的に結合した一つのネットワークドメイン・エッジノードから前記ネットワークドメイン内部のパスに対するフローリクエストを受取り、そして
前記ネットワークサーバ帯域幅ブローカが、前記パスレベルデータを使って前記フローリクエストに応じることができないと判定した場合、前記分散型ネットワークサーバ帯域幅ブローカによって、分散型ネットワークサーバ帯域幅ブローカが前記リンクレベルデータを使って前記フローリクエストに応じることを特徴とする、パケットネットワークにおける帯域幅ブローカのための割り当て方法。
【００４９】
（付記６）  前記パスレベルデータが、前記パスおよびパス状態に割当てられた未使用の帯域幅を含み、前記方法は更に、前記パスがクリティカルな状態になく、前記フローリクエストに応じるのに十分な未使用の帯域幅がある場合、前記エッジネットワークサーバ帯域幅ブローカによりその未使用の帯域幅を使ってフローリクエストに応じることを特徴とする、付記５に記載の方法。
【００５０】
（付記７）  前記リンクレベルデータは更に、一つのリンクにとって使用可能な帯域の複数の割当て分を含み、前記方法は更に、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記中央ネットワークサーバ帯域幅ブローカにより、前記パスに沿って各リンクに、前記リンクにとって使用可能な帯域幅の複数の割当て分から一つの割当て分を割当てることを特徴とする付記６に記載の方法。
【００５１】
（付記８）  前記リンクレベルデータは更にリンク状態を含み、前記パスレベルデータは更に、前記パスに沿う１組のクリティカルリンクを含み、前記方法は更に、前記中央ネットワークサーバ帯域幅ブローカにより、その１組のクリティカルリンクの各リンクに、各リンク上の別のパスから再請求された未使用の帯域幅から、帯域幅を割当てることを特徴とする付記７に記載の方法。
【００５２】
（付記９）  前記方法は更に、前記パスに沿ったリンクが、前記フローリクエストに応じるためにリンクにとって使用可能な帯域幅の割当て分を持たない場合、前記エッジネットワークサーバ帯域幅ブローカにより、前記フローリクエストを拒絶することを特徴とする付記７に記載の方法。
【００５３】
（付記１０）  ネットワークドメイン内部で帯域幅を割当てるのに使用されるデータ処理システムであって、
前記ネットワークドメイン内部のパスに関するパスレベルデータおよびリンクレベルデータを含むデータベース、
プロセッサ、および、
このプロセッサに動的に結合したメモリ
を含み、前記メモリの内部にプログラム命令が保存されており、前記プロセッサがこのプログラム命令を実行すべく動作できるようになっており、前記プログラム命令は、
ネットワークドメイン・エッジノードから前記パスに対するフローリクエストを受取り、そして
前記パスレベルデータを使ってこのフローリクエストに応じることができない場合、前記リンクレベルデータを使ってフローリクエストに応じる、
というステップを含むことを特徴とするデータ処理システム。
【００５４】
（付記１１）  前記パスレベルデータは、前記パスおよびパス状態に割当てられた未使用の帯域幅を含み、前記パスがクリティカルな状態になく、前記フローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、前記プログラム命令は更に、その未使用の帯域幅を使って前記フローリクエストに応じることを特徴とする付記１０に記載のデータ処理システム。
【００５５】
（付記１２）  前記リンクレベルデータは更に、一つのリンクにとって使用可能な帯域幅の割当て分を含み、前記プログラム命令は更に、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記パスに沿って各リンクに前記リンクにとって使用可能な帯域幅の割当て分から帯域幅の一つの割当て分を割り当てることを特徴とする付記１１に記載のデータ処理システム。
【００５６】
（付記１３）  前記リンクレベルデータは更にリンク状態を含み、前記パスレベルデータは更に、前記パスに沿って１組のクリティカルリンクを含み、前記プログラム命令は更に、その１組のクリティカルリンク内の各リンクに、リンクごとに別のパスから再請求された未使用の帯域幅から帯域幅を割当てることを含む特徴とする付記１２に記載のデータ処理システム。
【００５７】
（付記１４）  コンピュータにネットワークドメイン内部で帯域幅を割当てさせるプログラム命令をコンピュータが実行できるように具体化するコンピュータ読取り可能媒体であって、プログラム命令によって、
前記ネットワークドメイン内部のパスに関するパスレベルデータおよびリンクレベルデータを含むデータベースにアクセスし、
ネットワークドメイン・エッジノードからパスに対するフローリクエストを受取り、そして
前記パスレベルデータを使って前記フローリクエストに応じることができない場合、前記リンクレベルデータを使って前記フローリクエストに応じる、
ことを特徴とするコンピュータ読取り可能媒体。
【００５８】
（付記１５）  前記パスレベルデータは、前記パスおよびパス状態に割当てられた未使用の帯域幅を含み、前記プログラム命令は更に、前記パスがクリティカルな状態になく、前記フローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、プログラム命令によって更に、その未使用の帯域幅を使って前記フローリクエストに応じることを特徴とする付記１４に記載のコンピュータ読取り可能媒体。
【００５９】
（付記１６）  前記リンクレベルデータは更に、リンクにとって使用可能な帯域幅の割当分を含み、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記プログラム命令によって更に、前記パスに沿って各リンクに帯域幅全体のうちリンクにとって使用可能な帯域幅の割当分から帯域幅の一つの割当て分を割当てることを特徴とする、付記１５に記載のコンピュータ読取り可能媒体。
【００６０】
（付記１７）  前記リンクレベルデータは更にリンク状態を含み、前記パスレベルデータは更に、前記パスに沿って１組のクリティカルリンクを含み、更に、前記プログラム命令によって、その１組のクリティカルリンクの各リンクに、リンクごとに別のパスから再請求された未使用の帯域幅からの帯域幅を割当てることを特徴とする付記１６に記載のコンピュータ読取り可能媒体。
【００６１】
（付記１８）  ネットワークドメイン・エッジノードに動的に結合し、様々なQoS制御管理機能を実行する帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法であって、
前記帯域幅ブローカに動的に結合したネットワークＱｏＳ状態データベースを設け、
前記帯域幅ブローカにより、前記ネットワークドメイン・エッジノードから前記パスに対するフローリクエストを受取り、
前記パスがクリティカルな状態になく、前記パスが前記フローリクエストに応じるのに十分な未使用の帯域幅を持つ場合、帯域幅ブローカによりその未使用の帯域幅を使ってフローリクエストに応じ、
前記パスがクリティカルな状態になく、前記フローリクエストに応じるのに十分な未使用の帯域幅を持たない場合、前記帯域幅ブローカにより前記パスに沿って各リンクにリンクにとって使用可能な帯域幅から帯域幅の割当て分を割当て、そして
前記パスがクリティカルな状態にある場合、前記帯域幅ブローカにより、１組のクリティカルリンクの各リンクに、リンクごとに別のパスから再請求された帯域幅からの未使用の帯域幅からの帯域幅を割当てる、
というステップを備え、
前記ネットワークＱｏＳ状態データベースは、
前記パスに割当てられた未使用の帯域幅と、
前記パスに沿った１組のクリティカルリンクと、
パス状態とを含む、前記ネットワークドメイン内のパスのためのパスレベルデータと、
前記パスに沿ったリンクのためのパス状態を含むネットワークドメイン内部のパスに関するパスレベルデータと、
リンクにとって使用可能な帯域幅の割当て分と、
リンク状態と
を含むことを特徴とする、帯域幅ブローカによってネットワークドメイン内部で帯域幅を割当てる方法。
【図面の簡単な説明】
【図１】ネットワークドメインのＱｏＳプロビジョニングの管理および制御のための集中型帯域幅ブローカの一実施例を示す図である。
【図２】帯域幅ブローカホストとして使用するのに適した汎用コンピュータのハードウェアアーキテクチャ図である。
【図３】フロー・リザベーション・セットアップおよび割当て分割当て管理の目的でパス指向、割当て分ベースのダイナミック帯域幅割当て（ＰｏＱ）を使用する帯域幅ブローカのためのパス・レベル・アドミッション制御プロセスの一例についての記述である。
【図４】本発明による帯域幅ブローカの一実施例において使用されるリンクレベル帯域幅割当て／割当て分割当て管理プロセスの一例についての記述である。
【図５】本発明による帯域幅ブローカによるフロー出発ハンドリングのためのリンクレベル帯域幅／割当て分管理プロセスの一例についての記述である。
【図６】本発明による多重帯域幅ブローカのアーキテクチャの一例を描いた図である。
【図７】本発明による分散型帯域幅ブローカの一実施例における動作シーケンスの一例を描いた図である。
【図８】本発明による帯域幅ブローカの一実施例における割当てプロセスの一例を描いた図である。
【符号の説明】
１２…コアノード
１４…エッジノード
１６…帯域幅ブローカ
２０…データプレーン
２２…制御プレーン
２６…ＱｏＳデータベース
２８…リンクレベル
３０…パスレベル
【図１】
0003987394.tif 000003
【図２】
0003987394.tif 000004
【図３】
0003987394.tif 000005
【図４】
0003987394.tif 000006
【図５】
0003987394.tif 000007
【図６】
0003987394.tif 000008
【図７】
0003987394.tif 000009
【図８】
0003987394.tif 000010