(57)【要約】      （修正有）【課題】加入者間で通信資源を割り当てるネットワーク方針に従って効率的且つ公平に１つの通信網の加入者間で通信資源を割り当てるシステム及び方法の提供。【解決手段】通信システム内での許可制御のための方法及び装置。アクセスネットワーク（ＡＮ）要素は使用可能な資源を決定する。使用可能な資源が要求されたアプリケーションフローの要件を支持するのに十分であるとき、ＡＮは前記アプリケーションフローを許可する。ＡＮは周期的に、及びトリガイベント時に使用可能な資源のメトリックを更新する。許可制御は各フロータイプに補償係数を適用するスケジューラ、及び所与のユーザの集まった流れのための補償係数と協調して動作し得る。【選択図】図４
2010166582.tif 000002
【特許請求の範囲】
【請求項１】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおける許可制御のための方法であって、
前記通信システムにおいて使用可能な資源を決定することと、
第１のトラヒックプロファイル及び第１のＱｏＳプロファイルを有する第１のアプリケーションフローに対する要求を受け取ることと、
前記使用可能な資源が前記第１のアプリケーションフローに対する前記要求をサポートするかどうかを判断することと、
前記第１のアプリケーションフローが平均要求データレートを上回る対応するデータレートを有する場合に前記第１のアプリケーションフローを拒否することと、
前記対応するデータレートが前記平均要求データレートを上回らない場合に、及び前記使用可能な資源が前記第１のアプリケーションフローに対する前記要求をサポートする場合に前記第１のアプリケーションフローを許可することと、
を含む、方法。
【請求項２】
前記使用可能な資源が前記第１のアプリケーションフローをサポートするかどうかを判断することが、
前記通信システムにおいて予約された資源を決定することと、
前記予約された資源を前記通信システムの容量と比較することと、
前記使用可能な資源を前記容量と前記予約された資源の間の差異として決定することと、
を含む、請求項１に記載の方法。
【請求項３】
前記第１のアプリケーションフローについての適応加入係数を決定することをさらに含む、請求項２に記載の方法。
【請求項４】
前記第１のアプリケーションフローのサービスの質（ＱｏＳ）統計に基づいて前記適応加入係数を更新することをさらに含む、請求項３に記載の方法。
【請求項５】
前記第１のアプリケーションフローについてのＱｏＳ統計を決定することと、
前記第１アプリケーションフローについての前記ＱｏＳ統計を前記セクタ内の他の現在のフローと比較することと、
前記第１のアプリケーションフローについての前記ＱｏＳ統計と前記セクタ内の他の現在のフローとの比較に応じて、前記使用可能な資源および予約された資源を更新することと、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記無線通信システムのセクタ内に前記第１のアプリケーションフローのユーザが存在するかどうかを判断することと、
前記第１のアプリケーションフローについてのサンプル持続期間を決定することと、
をさらに含み、
前記第１のアプリケーションフローについてのＱｏＳ統計を決定することが、
前記サンプル持続期間中の前記第１のアプリケーションフローについてのＱｏＳ統計を決定することを含む、請求項５に記載の方法。
【請求項７】
第１のサンプル持続期間がレート違反と関連付けられ、第２のサンプル持続期間が遅延違反と関連付けられる、請求項６に記載の方法。
【請求項８】
前記第１のアプリケーションフローについての前記ＱｏＳ統計を前記セクタ内の他の現在のフローと比較することが、
前記サンプル持続期間中にＱｏＳ要件を有するフローによって使用されるスロットの第１の割合を計算することと、
前記サンプル期間中に前記第１のアプリケーションフローによって使用されるスロットの第２の割合を計算することと、
第１のＱｏＳ統計に対応するＱｏＳフローの第３の割合を計算することと、
前記第３の割合を対応する閾値と比較することと、
前記第３の割合と対応する閾値との比較に応じて、適応加入を評価することと、
を含む、請求項６に記載の方法。
【請求項９】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための方法であって、
適応加入を増加するために、第１のタイプのＱｏＳ違反を有する第１のフローを先処理することと、
第１のタイプのＱｏＳ違反について先処理最大値に達したことを判断することと、
第２のタイプのＱｏＳ違反を有する第２のフローを先処理することと、
を含む、方法。
【請求項１０】
第２のフローを先処理することが、
前記第２のフローの伝送のために使用されるスロットの数に基づいて前記第２のフローを選択することをさらに含む、請求項９に記載される方法。
【請求項１１】
パケットデータアプリケーションフローをサポートする無線通信システムにおいて資源をスケジュールするための方法であって、
第１のタイプのアプリケーションフローに関連付けられるサービスの質パラメータについて少なくとも１つの補償係数を選択することと、
サービスの質パラメータに基づいて前記少なくとも１つの補償係数を計算することと、
前記第１のタイプのアプリケーションフローについての重みを前記少なくとも１つの補償係数の関数として計算することと、
前記重みを使用してフロー単位のスケジューリング係数を計算することと、
前記スケジューリング係数に基づいて前記アプリケーションフローをスケジュールすることと、
を含む、方法。
【請求項１２】
第１のユーザが複数のアクティブなアプリケーションフローを有し、
前記複数のアプリケーションフローについての総計補償係数を計算することをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記複数のアクティブなアプリケーションフローは、前記第１のタイプの、及び第２のタイプのアプリケーションフローを含む、請求項１２に記載の方法。
【請求項１４】
第２のタイプのアプリケーションフローについての重みを計算することをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記複数のアクティブなアプリケーションフローの内の１つを伝送のために選択することをさらに含む、請求項１４に記載の方法。
【請求項１６】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおける許可制御のための装置であって、
前記通信システム内で使用可能な資源を決定するための手段と、
第１のトラヒックプロファイル及び第１のＱｏＳプロファイルを有する第１のアプリケーションフローに対する要求を受け取るための手段と、
前記使用可能な資源が前記第１のアプリケーションフローに対する前記要求をサポートするかどうかを判断するための手段と、
前記第１のアプリケーションフローが平均要求データレートを上回る対応するデータレートを有する場合に前記第１のアプリケーションフローを拒否するための手段と、
前記対応するデータレートが前記平均要求データレートを上回らない場合に、及び前記使用可能な資源が前記第１のアプリケーションフローに対する前記要求をサポートする場合に前記第１のアプリケーションフローを許可するための手段と、
を備える、装置。
【請求項１７】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための装置であって、
適応加入を増加するために、第１のタイプのＱｏＳ違反を有する第１のフローを先処理するための手段と、
前記第１のタイプのＱｏＳ違反について先処理最大値に達したこと判断するための手段と、
第２のタイプのＱｏＳ違反を有する第２のフローを先処理するための手段と、
を備える、装置。
【請求項１８】
パケットデータアプリケーションフローをサポートする無線通信システムにおいて資源をスケジュールするための装置であって、
第１のタイプのアプリケーションフローと関連付けられるサービスの質パラメータの少なくとも１つの補償係数を選択するための手段と、
サービスの質パラメータに基づいて前記少なくとも１つの補償係数を計算するための手段と、
前記第１のタイプのアプリケーションフローについての重みを前記少なくとも１つの補償係数の関数として計算するための手段と、
前記重みを使用してフロー単位のスケジューリング係数を計算するための手段と、
前記スケジューリング係数に基づいて前記アプリケーションフローをスケジュールするための手段と、
を備える、装置。
【請求項１９】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための装置であって、
アプリケーションフローを受け取り且つ前記アプリケーションフローの前記サービスの質（ＱｏＳ）要件を決定するように適応されたフロー分類装置と、
前記フロー分類装置に結合され、パケットデータ伝送をスケジュールするように適応されたスケジューラと、
前記フロー分類装置及びスケジューラに結合され、使用可能な資源が要求データレートをサポートするときにアプリケーションフローを許可するように適応された許可制御装置と、
前記フロー分類装置、前記スケジューラ、及び前記許可制御装置に結合され、前記アプリケーションフローについてのＱｏＳ違反を判断し、ＱｏＳ統計を維持するように適応されたＱｏＳモニタと、
前記許可制御装置に結合され、使用可能な資源を更新するように適応された適応装置と、
を備える、装置。
【請求項２０】
前記スケジューラは、要求データレートに応じてアプリケーションフローをスケジュールするように適応される、請求項１９に記載の装置。
【請求項２１】
前記スケジューラは、ＱｏＳ統計に応じてアプリケーションフローをス系ジュールするように適応される、請求項１９に記載の装置。
【請求項２２】
前記スケジューラは、ＱｏＳ要件に応じてアプリケーションフローをスケジュールするように適応される、請求項１９に記載の装置。
【請求項２３】
前記スケジューラは、加入情報に基づいてアプリケーションフローをスケジュールするように適応される、請求項１９に記載の装置。
【発明の詳細な説明】
【関連出願の表示】
【０００１】
本特許出願は、本譲受人に譲渡され、参照によって本明細書に明白に組み込まれる「通信システムにおいて資源を割り当てるためのシステム（System for Allocating Resources in a Communication System）」と題される2003年3月17日に出願された仮特許出願第60/455,906号の優先権を主張する。
【技術分野】
【０００２】
本願は通信システムに関する。特に、これらの実施形態は通信システムの複数の加入者の間で通信資源を割り当てることを目的とする。
【背景技術】
【０００３】
複数の加入者間で通信システム内の単一のノードにより提供される限られた通信資源を割り当てるという問題に対処するために複数の解決策が提示されてきた。コストを最小限に抑えながら、全加入者の要件を満たすために十分な資源を各ノードで提供することがこのようなシステムの目的である。したがって、このようなシステムは、通常、多様な加入者間での効率的な資源の割り当てを目的として設計される。
【０００４】
多様なシステムが、加入者のそれぞれに資源を同時に割り当てる周波数分割多元接続（ＦＤＭＡ）方式を実現してきた。このようなシステムの通信ノードは、通常、任意の時点でネットワーク内の各加入者に情報を送信するか、あるいは各加入者から情報を受信するかのどちらかのための限られた帯域幅を有している。この方式は、通常、個々の加入者に対して全体の帯域幅の別個の部分を割り当てることを含む。このような方式は、加入者が通信ノードとの中断されない通信を必要とするシステムにとっては効果的である可能性があるが、このような不断の（constant）、中断されない通信が必要とされないときには、全体的な帯域幅のさらに優れた活用が達成され得る。
【０００５】
複数の加入者の間で単一の通信ノードの通信資源を割り当てる他の方式には時分割多元接続（ＴＤＭＡ）方式がある。これらのＴＤＭＡ方式は、単一の通信ノードの限られた帯域幅資源を複数の加入者間で割り当てる際であって、ユーザが単一の通信ノードとの不断の、中断されない通信を必要としない際に特に有効である。ＴＤＭＡ方式は、通常、単一の通信ノードの帯域幅全体を指定された時間間隔で加入者のそれぞれに当てる（dedicate）。符号分割多元接続（ＣＤＭＡ）方式を利用する無線通信システムでは、これは時分割ベースで指定された時間間隔ですべての符号チャネルを加入者装置のそれぞれに割り当てることによって達成され得る。通信ノードは、加入者との排他的な（exclusive）通信を可能とするために、加入者に関連付けられる一意の搬送周波数またはチャネル符号を導入する。ＴＤＭＡ方式は、物理的接点リレー切り替えまたはパケット交換を使用して陸線システムで実現されてもよい。
【０００６】
ＴＤＭＡシステムは、通常、総当たり方式で各加入者に等しい時間間隔を割り当てる。このため、加入者によるある時間間隔の利用に無駄が生じる場合がある。同様に、他の加入者は、割り当てられた時間間隔を上回る通信資源要求を行い、この加入者が不十分なサービスを受けることになり得る。システムオペレータは、どの加入者も受けるサービスが不足していないことを確実にするためにノードの帯域幅を広げるコストを負担するか、あるいは不充分なサービスを受けている加入者が不充分なサービスを受け続けることを許容するかのどちらかを選び得る。
【０００７】
したがって、加入者間で通信資源を割り当てるネットワーク方針に従って効率的且つ公平に１つの通信網の加入者間で通信資源を割り当てるシステム及び方法を提供するニーズがある。それとともに、システムの特定の要件、制約及び／または目標に応じてフロー単位で、及び／または総計ベースでの資源割り当てを実行するための機構を提供することを含む（それに限定されない）システムによりサービスを受けるユーザ数を最大限にするニーズがある。さらに、資源割り当てを最適化する許可制御及び先処理(preemption)方法に対するニーズもある。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態による通信網を示す。
【図２Ａ】本発明の実施形態に従って構成された基地局コントローラ及び基地局装置のブロック図を示す。
【図２Ｂ】本発明の実施形態に従って構成された遠隔局装置のブロック図を示す。
【図３】図２Ａに示されるチャネルスケジューラの実施形態におけるスケジューリングアルゴリズムの実行を描く流れ図を示す。
【図４】各アプリケーション通信がアプリケーションフローにより表される、マルチメディアアプリケーションをサポートする通信システムである。
【図５】アプリケーションフローの待ち行列である。
【図６】アプリケーションフローの一部の信号タイミングを描くタイミング図である。
【図７Ａ】アプリケーションフローのジッタ測定を描くタイミング図である。
【図７Ｂ】アプリケーションフローを処理するためのタイムスロットの期間での連続するＩＰパケットの伝送を描くタイミング図である。
【図８】通信システム内のアプリケーションフローのスケジューリングを描く流れ図である。
【図９】さまざまなサービスの質（ＱｏＳ）要件を有するアプリケーションフローのスケジューリングを描く流れ図である。
【図１０】一実施形態によるスケジューリングアルゴリズムと一致した各アプリケーションフローの定義を描くアーキテクチャ図である。
【図１１】一実施形態に従ったクラスタイプを識別する表である。
【図１２Ａ】アプリケーションフローの初期化を含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１２Ｂ】クラスタイプの関数としてアプリケーションフローを処理することを含む、一実施形態によるスケジューリングアルゴリズムの一部を示す。
【図１２Ｃ】モードＩＩアプリケーションフローの処理、及びモードＩＩＩアプリケーションフローの処理を含む、一実施形態によるスケジューリングアルゴリズムの一部を示す。
【図１２Ｄ】モードＩアプリケーションフローの処理を含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１２Ｅ】適応加重及びそれに基づいたスケジューリングを含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１３】無線通信システムにおいて適応加重アルゴリズムを使用してアプリケーションフローをスケジュールするためのアルゴリズムを実現するための基地局トランシーバシステム（ＢＴＳ）を描く。
【図１４】時間の関数としてデータレート（ＬＭＡＸ）、予約済み資源（Ｒｅｓ（ｔ））、及び使用可能な資源（Ａｖａｉｌ（ｔ））などの割り当てのための最大資源を描くタイミング図である。
【図１５】高速パケットデータタイプシステム内でユーザから受信されるデータ要求、及び時刻ｔで予約するための時間の関数としての推測容量Ｌ（ｔ）を描くタイミング図である。
【図１６】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステムのためのスケジューラを描く情報流れ図であり、フローはフロー単位補償のアプリケーションによりスケジュールされる。
【図１７】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステムのためのスケジューラを示す情報流れ図であり、フローは総計補償のアプリケーションによりスケジュールされる。
【図１８Ａ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｂ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｃ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｄ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｅ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く  。
【図１９】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での先処理のためのアルゴリズムを描く。
【図２０】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内でのアクセスネットワーク（ＡＮ）要素のブロック図である。
【発明を実施するための形態】
【０００９】
本発明の実施形態は、単一の通信ノードによりサービスを提供される、１つの通信網の複数の加入者間で資源を割り当てるためのシステム及び装置を対象としている。個々の別々の伝送間隔、つまり「サービス間隔」で、個々の加入者は他のすべての加入者を除外して通信ノードの有限の資源を獲得する。個々の加入者は、個々の加入者に関連付けられる重みまたはスコアに基づいて有限資源を獲得するために選択される。個々の加入者に関連付けられる重みの変化は、当該個々の加入者が有限資源を消費できる瞬間の速度に基づいているのが好ましい。
【００１０】
図を参照すると、図１は例示的な可変速度通信システムを表す。１つのこのようなシステムはクアルコム社（Qualcomm, Inc.）に譲渡され、参照することにより本明細書に組み込まれる、1997年11月3日に出願された「高速パケットデータ伝送のための方法及び装置（Method and Apparatus for High Rate Packet Data Transmission）」と題される米国特許出願第08/963,386号に説明されている。可変速度通信システムは複数のセル２Ａから２Ｇを備える。各セル２は、対応する基地局４によりサービスを提供される。多様な遠隔局６が通信システム全体に分散されている。例示的な実施形態では、遠隔局６のそれぞれは任意のデータ伝送間隔で下りリンク（forward link）で多くても１つの基地局４と通信する。例えば、タイムスロットｎで、基地局４Ａはデータを遠隔局６Ａだけに送信し、基地局４Ｂは遠隔局６Ｂだけにデータを送信し、基地局４Ｃは下りリンクで遠隔局６Ｃだけにデータを送信する。図１に図示されるように、各基地局４はどの時点でも１つの遠隔局６にデータを送信するのが好ましい。他の実施形態では、基地局４は、基地局４に関連付けられる他のすべての遠隔局６を除いてある特定のデータ伝送間隔で２以上の遠隔局６と通信してよい。さらに、データレートは可変であり、一実施形態では受信側遠隔局６によって測定されるような搬送波対干渉比(carrier-to-interference ratio)（Ｃ／Ｉ）及び必要とされるビット当たりエネルギー対雑音比(energy-per-bit-to-noise)（Ｅｂ／ＮＯ）に依存している。簡略化のために、遠隔局６から基地局４への上りリンクは図１に図示されていない。一実施形態によれば、遠隔局６は無線データサービス加入者により操作される無線トランシーバ付きモバイルユニットである。
【００１１】
例示的な可変速度通信システムの基本サブシステムを描くブロック図は図２Ａから図２Ｂに示されている。基地局コントローラ１０はパケットネットワークインタフェース２４、公衆電話交換網（ＰＳＴＮ）３０、及び通信システム内のすべての基地局４（簡略化のために図２Ａではただ１つの基地局４が示されている）とインタフェースをとる。基地局コントローラ１０は、通信システム内の遠隔局６と、パケットネットワークインタフェース２４やＰＳＴＮ３０に接続される他のユーザの間との通信を調整する。ＰＳＴＮ３０は、標準的な電話網（図２Ａには図示されていない）を通してユーザとインタフェースをとる。
【００１２】
簡略化のために図２Ａにはただ１つしか示されていないが、基地局コントローラ１０は、多くのセレクタ要素１４を含む。各セレクタ要素１４は１つ以上の基地局４と１つの遠隔局６の間の通信を制御するために割り当てられる。セレクタ要素１４が遠隔局６に割り当てられていない場合、呼制御プロセッサ１６は、遠隔局６を呼び出す必要性を知らされる。呼制御プロセッサ１６は、次に基地局４に遠隔局６を呼び出すように命令する。
【００１３】
データソース２０は、遠隔局６に送信される予定の不定量のデータを含む。データソース２０はパケットネットワークインタフェース２４にデータを提供する。パケットネットワークインタフェース２４はデータを受信し、セレクタ要素１４にデータを送る。セレクタ要素１４は遠隔局６と通信している各基地局４にデータを送信する。例示的な実施形態では、各基地局１４は、遠隔局６に送信される予定のデータを記憶するデータ待ち行列（data queue）４０を保持する。
【００１４】
データはデータ待ち行列４０からチャネル要素４２へデータパケットで送信される。例示的な実施形態では、下りリンクでは、「データパケット」は、最大１０２４ビットである不定量のデータ、および「タイムスロット（例えば１．６６７ｍｓｅｃ）」内で宛て先遠隔局６に送信される予定の不定量のデータを指す。データパケットごとにチャネル要素４２は必要な制御フィールドを挿入する。例示的な実施形態では、チャネル要素４２はデータパケット及び制御フィールドをＣＲＣ符号化し、コードテールビットのセットを挿入する。データパケット、制御フィールド、ＣＲＣパリティビット及びコードテールビットはフォーマットされたパケットを備える。例示的な実施形態では、チャネル要素４２が、次いでフォーマットされたパケットを符号化し、符号化されたパケット内でのシンボルをインタリーブ（つまり再順序付け）する。例示的な実施形態では、インタリーブされたパケットはウォルシュ符号でカバーされ(covered)、ショートＰＮＩコードとＰＮＱコードで拡散される。拡散されたデータは、信号を直交変調し(quadrature modulates)、濾波し、増幅するＲＦ装置４４に供給される。下りリンク信号は下りリンク５０上でアンテナ４６を通して無線で送信される。
【００１５】
遠隔局６では、下りリンク信号はアンテナ６０により受信され、フロントエンド６２内の受信機に送られる。受信機は信号を濾波し、増幅し、直交変調し、量子化する。ディジタル化された信号は、復調器（ＤＥＭＯＤ）６４に供給され、そこで、ショートＰＮＩコードとＰＮＱコードで逆拡散され、ウォルシュカバーでデカバー(decover)される。復調されたデータは、基地局４で実行される信号処理機能、特にデインターリービング(de-interleaving)、復号、及びＣＲＣチェック機能の逆を実行するデコーダ６６に与えられる。復号されたデータはデータシンク６８に供給される。
【００１６】
前記に指摘されたように、ハードウェアは、下りリンク上でデータ、メッセージング、音声、ビデオ及び他の通信の可変速度伝送をサポートする。データ待ち行列４０から送信されるデータの速度は、遠隔局６での信号強度及び雑音環境の変化に適応するために変化する。遠隔局６のそれぞれは、各タイムスロットでデータレート制御（ＤＲＣ）信号を関連付けられた基地局４に送信するのが好ましい。ＤＲＣは、遠隔局が下りリンクについて所望されるデータレート、つまり遠隔局でデータを受信するためのデータレートを決定する制御機構を指す。遠隔局はＤＲＣメッセージを介して基地局にデータレート要求または命令として所望されるデータレートを送信する。ＤＲＣ信号は、遠隔局６のアイデンティティ、及び遠隔局６がその関連付けられるデータ待ち行列からデータを受信するべきレートを含む情報を基地局４に提供する。したがって、遠隔局６の回路は、信号強度を測定し、遠隔局６における雑音環境を推定して、ＤＲＣ信号で送信されるべきレート情報を決定する。
【００１７】
各遠隔局６によって送信されるＤＲＣ信号は、上りリンクチャネル５２を通して進み、アンテナ４６及びＲＦ装置４４を通して基地局４で受信される。例示的な実施形態では、ＤＲＣ情報はチャネル要素４２で復調され、基地局コントローラ１０内に位置するチャネルスケジューラ１２Ａに、あるいは基地局４内に位置するチャネルスケジューラ１２Ｂに供給される。第１の例示的な実施形態では、チャネルスケジューラ１２Ｂは基地局４に位置する。別の実施形態では、チャネルスケジューラ１２Ａは基地局コントローラ１０内に位置し、基地局コントローラ１０内のすべてのセレクタ要素１４と接続される。
【００１８】
一実施形態では、チャネルスケジューラ１２Ｂはデータ待ち行列４０から、待ち行列サイズとも呼ばれる遠隔局ごとに待ち行列に入れられるデータ量を示す情報を受け取る。チャネルスケジューラ１２Ｂは、次に、基地局４によりサービスを提供される遠隔局ごとにＤＲＣ情報及び待ち行列サイズに基づいてスケジューリングを実行する。待ち行列サイズが別の実施形態において使用されるスケジューリングアルゴリズムに必要とされる場合には、チャネルスケジューラ１２Ａはセレクタ要素１４から待ち行列サイズ情報を受信してよい。
【００１９】
本発明の実施形態は、可変速度伝送をサポートできる他のハードウェアアーキテクチャに適用可能である。本発明は上りリンクでの可変速度伝送をカバーするために容易に拡張されてよい。例えば、遠隔局６からのＤＲＣ信号に基づいて基地局４でデータを受信する速度を決定する代わりに、基地局４は遠隔局６から受信される信号の強度を測定し、雑音環境を推定して、遠隔局６からデータを受信する速度を決定する。基地局４は、次に、データが遠隔局６から上りリンクで送信される予定の速度を関連する遠隔局６の各々に送信する。次に基地局４は下りリンクについて本明細書に説明される方法と類似した方法で、上りリンクでの異なるデータレートに基づいて、上りリンクでの伝送スケジュールを行ってよい。
【００２０】
また、前述された実施形態の基地局４は、ＣＤＭＡ方式を使用して、基地局４と関連付けられる残りの遠隔局を除いて、遠隔局６の内の選択された１つまたは選択された複数の遠隔局に送信する。任意の特定のときに、基地局４は、受信側基地局（複数の場合がある）４に割り当てられる符号を使用することによって遠隔局６の内の選択された１つまたは選択された複数の遠隔局に送信する。しかしながら、本発明は、伝送資源を最適に割り当てるために、他の基地局４を除いて、基地局（複数の場合がある）４を選択するためのデータを提供するためのさまざまなＴＤＭＡ方法を利用する他のシステムにも適用可能である。
【００２１】
チャネルスケジューラ１２は、下りリンクでの可変速度伝送をスケジュールする。チャネルスケジューラ１２は遠隔局６に送信するためのデータ量を示す待ち行列サイズ、及びメッセージを、遠隔局６から受信する。チャネルスケジューラ１２は、公平性の制約に準拠しながら、最大データスループットというシステム目標を達成するためにデータ伝送をスケジュールするのが好ましい。
【００２２】
図１に図示されるように、遠隔局６は通信システム全体に分散され、下りリンクで基地局４と通信していないか、又は基地局４と通信しているかもしれない。例示的な実施形態では、チャネルスケジューラ１２は通信システム全体に亘って下りリンクデータ伝送を調整する。高速データ伝送のためのスケジューリングの方法及び装置は、本発明の譲受人に譲渡され、参照することにより本明細書に組み込まれる２００２年１月１日に発行された米国特許第６，３３５，９２２号に詳しく説明されている。
【００２３】
一実施形態によれば、チャネルスケジューラ１２は、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、及びプロセッサ（図示せず）により実行されるべき命令を記憶するためのプログラムメモリを含むコンピュータシステムで実現される。プロセッサ、ＲＡＭ及びプログラムメモリはチャネルスケジューラ１２の機能専用とされてよい。他の実施形態では、プロセッサ、ＲＡＭ、及びプログラムメモリは基地局コントローラ１０で付加的な機能を実行するための共用計算資源の一部であってよい。
【００２４】
図３は、基地局４から遠隔局６への伝送をスケジュールするためにチャネルスケジューラ１２を制御するスケジューリングアルゴリズムの実施形態を示す。前述されたように、データ待ち行列４０は各遠隔局６と関連付けられる。チャネルスケジューラ１２は、データ待ち行列４０のそれぞれを、「重み」と関連付ける。重みは、基地局４と関連付けられ且つその次のサービス間隔でデータを受信する特定の遠隔局６を選択するためにステップ１１０で評価される。チャネルスケジューラ１２は、別々のサービス間隔でデータ伝送を受信する個々の遠隔局６を選択する。ステップ１０２では、チャネルスケジューラは、基地局４と関連付けられている各待ち行列についての重みを初期化する。
【００２５】
チャネルスケジューラ１２は、伝送間隔またはサービス間隔でステップ１０４から１１２を周期的に繰り返す（cycles）。ステップ１０４では、チャネルスケジューラ１２は、先のサービス間隔で検出された基地局４との更なる遠隔局６との関連付けのために追加されるべき追加の待ち行列があるかどうかを判断する。チャネルスケジューラ１２はまた、ステップ１０４で新しい待ち行列と関連付けられた重みも初期化する。前述されたように、基地局４はタイムスロットなどの定期的な間隔で自身と関連付けられる各遠隔局６からＤＲＣ信号を受信する。
【００２６】
このＤＲＣ信号はまた、各待ち行列と関連付けられる遠隔局ごとに情報を消費する（つまり送信されたデータを受信する）ための瞬間速度を決定するためにチャネルスケジューラがステップ１０６で使用する情報も提供する。実施形態によれば、任意の遠隔局６から送信されるＤＲＣ信号は、前記遠隔局６が複数の有効なデータレートの内の任意の１つでデータを受信することができることを示す。
【００２７】
チャネルスケジューラ１２は、ステップ１０８で、データを受信するために遠隔局６に関連付けられた（最も近い過去に受信されたＤＲＣ信号に示されるような）瞬間速度に基づいてデータが任意の特定の遠隔局６に送信されるべきサービス間隔の長さを決定する。実施形態によれば、データＲｉを受信する瞬間速度は、ステップ１０６で特定のデータ待ち行列と関連付けられるサービス間隔長Ｌｉを決定する。
【００２８】
ステップ１１０でチャネルスケジューラ１２は伝送のための特定のデータ待ち行列を選択する。それから、関連付けされた量の送信データがデータ待ち行列４０から取り出され、次にデータ待ち行列４０と関連付けられる遠隔局６への伝送のためにチャネル要素４２に供給される。後述されるように、ステップ１１０でチャネルスケジューラ１２は、各待ち行列と関連付けられる各重みを含む情報を使用して次のサービス間隔で送信されるデータを提供するための待ち行列を選択する。送信された待ち行列と関連付けられる重みは、次にステップ１１２で更新される。
【００２９】
当業者は、チャネルスケジューラ１２が、本発明から逸脱することなく、多岐に渡るアプローチを使用して実現されてよいことを理解するであろう。例えば、チャネルスケジューラ１２は、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、及びプロセッサ（図示せず）によって実行される命令を記憶するためのプログラムメモリを含む、コンピュータシステムを使用して実現されてよい。他の実施形態では、チャネルスケジューラ１２の機能は、基地局４または基地局コントローラ１０で付加的な機能を実行するためにも使用される共用計算資源の中に組み込まれてもよい。さらに、チャネルスケジューラ機能を実行するために使用されるプロセッサは汎用マイクロプロセッサ、ディジタル信号プロセッサ（ＤＳＰ）、プログラマブルロジックデバイス、特定用途向け集積回路（ＡＳＩＣ）または、本発明から逸脱することなく、本明細書に説明されるアルゴリズムを実行できる他のデバイスであってよい。
【００３０】
図１の実施形態に示されるように、遠隔局６は、可動性であり、さまざまな基地局４の間で関連付けを変更することができる。例えば、遠隔局６Ｆは当初、基地局４Ｆからデータ伝送を受信している。次に、遠隔局６ｆは基地局４Ｆのセルから出て、基地局４Ｇのセルに入ってよい。遠隔局６Ｆは次に基地局４Ｆの代わりに基地局４Ｇに注意を喚起するためにＤＲＣ信号の送信を開始してよい。遠隔局６ＦからＤＲＣ信号を受信しないことにより、基地局４Ｆのロジックは、遠隔局６ｆが接続を解き、もはやデータ伝送を受信しないと推論する。遠隔局６Ｆに関連付けられるデータ待ち行列は、次に陸線またはＲＦ通信リンクを介して基地局４Ｇに送信されてもよい。
【００３１】
適応加重スケジューリングアルゴリズム
さらに、（以下にさらに説明される）「フロー（flows）」と呼ばれるマルチメディアサービス伝送がバースト的な（bursty）トラヒックをつくり出す１つの無線通信システムでマルチメディアサービス又は種々の伝送要件を有する他のサービスが送信されるときに問題が存在する。バースト的なトラヒックは、バースト性の測度（measure of burstiness）および平均データレートを含む複数の変数により特徴付けられる。さらに、システム内での多様なフローのそれぞれのサービスの質（ＱｏＳ）要件を満たすニーズがある。比例公平(Proportional Fair)（ＰＦ）アルゴリズムなどの現行のスケジューリング方法は、通常、「Ｔ」として識別されるスループットに対する、データレート制御データ要求つまり「ＤＲＣ」と呼ばれる要求されたデータレートの比率として示されるメトリックに基づいてサービスを提供するためのフローを選択する。このような計算はすべてのユーザの要求されるＱｏＳを保証しない可能性がある。したがって、純粋なＰＦアルゴリズムはマルチメディアまたは他のアプリケーションにアクセスするユーザのＱｏＳ要件を満足するほど十分な複雑さを提供しない可能性がある。これらの多様な要件を満たすことができるスケジューラに対するニーズがある。
【００３２】
以下の説明が、ＩＳ−８５６に説明されるような高速パケットデータ（ＨＲＰＤ）サービスをサポートするｃｄｍａ２０００システムを考慮していることに留意されたい。このシステムは例として使用される。本発明は、ユーザがスケジューリングアルゴリズムに従ってサービスのために選択される他のシステムに適用可能である。
【００３３】
ＨＲＰＤシステムでは、無線インタフェースは最高４つまでの平行なアプリケーションストリームをサポートし得る。第１のストリームはシグナリング情報を搬送し、他の３つは異なるサービスの質（ＱｏＳ）要件のアプリケーション、又は他のアプリケーションを搬送するために使用され得る。
【００３４】
以下の用語解説は、以下に提示される一実施形態を理解する上での明確さのために提供される。以下の用語解説は網羅的であることを意図していない。以下の用語解説は本発明をそれに制限することを意図しておらず、むしろ適応加重スケジューリングアルゴリズムをサポートする通信システムの一実施形態に関して明確にするため、及び理解するために提供される。
【００３５】
用語集
アクセスネットワーク（ＡＮ）：セルラーネットワークとパケット交換データネットワーク（通常はインターネット）とＡＴの間でのデータ接続性（data connectivity）を提供するネットワーク装置。ＨＲＰＤシステムにおけるＡＮは、セルラー通信システムにおける基地局に相当する。
【００３６】
アクセス端末（ＡＴ）：ユーザにデータ接続性を与えるデバイス。ＨＲＰＤシステムにおけるＡＴは、セルラー通信シムテムにおける携帯電話に対応する。ＡＴはラップトップパーソナルコンピュータなどのコンピューティング装置に接続されてよく、あるいは、ＡＴはパーソナルディジタルアシスタント（ＰＤＡ）のような自己完結した（self-contained）データデバイスであってよい。
【００３７】
アプリケーションフロー：あるアプリケーションストリームに関するソースからＡＴへの指定された伝送路（transmission path）。各アプリケーションフローはソース、宛て先、トラヒックプロファイル、及びサービスの質プロファイルによって識別される。
【００３８】
アプリケーションストリーム：アプリケーションに対応するデータ通信。大部分のアプリケーションストリームは指定されたサービスの質要件を有する。
【００３９】
自動反復要求（ＡＲＱ）−送信機がイベントの発生または非発生に基づいてデータの再送を開始する機構。
【００４０】
アベイル（ｔ）（Ａｖａｉｌ（ｔ））：下りリンク上での時刻ｔにおける予約されていない帯域幅。
【００４１】
平均データレート（ｒ）：あるアプリケーションフローに関する経時的な（over time）平均入力データレート。
【００４２】
平均遅延（ＡｖｇＤ）：ＡＮからＡＴへ複数のパケットまたはビットで生じる遅延の平均。
【００４３】
バースト性（σ）：バースト性、つまりアプリケーションフロー内のパケットの密度及び時間単位の関係指標。
【００４４】
データレート制御（ＤＲＣ）：それによりＡＴが要求データレートをＡＮに送信する機構。
【００４５】
不足パケット（ｄｅｆｐｋｔｓ）：スロットｎの始まりでのフローｋに関して定義される。不足パケットとは、フロー内のまだ送信されていないパケットであり、ｄｅｆｐｋｔｓは、特に、例えばフローｋの遅延閾値より長くＢＴＳに留まった媒体アクセス制御（ＭＡＣ）パケットなどの処理中(mid-processing)パケットなどの、等しいサイズのパケットの数として定義される。
【００４６】
不足ビット（ｄｅｆｂｉｔｓ）：不足パケットに対応するビット数。
【００４７】
遅延限度：ＡＮからＡＴへのデータのパケットの伝送に許容される指定時間。
【００４８】
遅延閾値：遅延限度またはジッタ限度の関数であり、ｄｅｆｐｋｔｓを計算するために使用される。
【００４９】
遅延補償係数（Φ）：遅延違反を補償するために使用される補償係数。
【００５０】
ＤＲＣ補償係数（β）：アプリケーションフローのユーザと関連付けられるデータ要求要件の主な原因となる補償係数。アプリケーションの優美な回復を行うために使用される。
【００５１】
拡張ジッタ閾値（ｄｖ）：フローの２つの連続するＩＰパケットの間のジッタ違反の検出時に拡張ジッタ補償関数を計算するために使用される。
【００５２】
フロー重み（ｗ）：適応加重スケジューリングアルゴリズムを使用した各アプリケーションフローに適用される初期重み値。適応加重（ａｗ）は、重みの適応値である。
【００５３】
下りリンク（ＦＬ）：ＡＮからＡＴへの伝送無線リンク。
【００５４】
行頭（ＨＯＬ）パケット：待ち行列内の第１のパケット。
【００５５】
高速パケットデータ（ＨＲＰＤ）：高データレートでパケットデータ通信を送信するデータサービス。高データレートとも呼ばれ、「ｃｄｍａ２０００高速パケットデータ無線インタフェース仕様書（cdma2000 High Rate Packet Data Air Interface Specification）」と題されるＩＳ−８５６規格に規定される。
【００５６】
ジッタ：受信された連続パケットの間の時間変動。
【００５７】
ジッタ限度（ｊ）：あるアプリケーションフローに関するジッタに対する制限。
【００５８】
ジッタ補償係数、機能拡張されている（δ）：フローについてジッタ違反を補償するための補償係数。
【００５９】
Ｌmax：ＢＴＳが下りリンクでデータを送信し得る最大速度（例えば、ｃｄｍａ２０００  １ｘＥＶ−ＤＯ型ネットワークでの２．４Ｍｂｐｓ）。
【００６０】
Ｌ（ｔ）：前回のＱｏＳ違反統計及びネットワーク負荷関連統計に基づいて時刻ｔにおいて確保すべき下りリンク容量の推定値。
【００６１】
正規化された不足パケット（ｎｄｅｆｐｋｔｓ）：不足パケット及びそのフローの要求速度を使用して計算された、正規化された不足パケット。
【００６２】
正規化された不足ビット（ｎｄｅｆｂｉｔｓ）：正規化された不足パケットに対応する、正規化された不足ビット。
【００６３】
エムペグ（ＭＰＥＧ）：マルチメディアデータの伝送のためのプロトコル。
【００６４】
未決パケット：ｐｅｎｄk,j［ｎ］：スロットｎのＢＴＳとＢＳＣでのフローｋのＩＰパケットｊの未決バイトの数。
【００６５】
比例公平（ＰＦ）アルゴリズム：データ通信が、スループットに対する要求データレートの比率としてＡＴごとに計算される選択係数に従ってスケジュールされるスケジューリングアルゴリズム。
【００６６】
サービスの質（ＱｏＳ）：遅延、所要レート及びジッタを含む（それらに限定されない）パケットデータ通信の伝送に関する要件。
【００６７】
ＱｏＳ及びネットワーク補償関数（Φ、γ、α、β、δ）：適応加重スケジューリングアルゴリズムで使用されるような補償関数。
【００６８】
サービスの質グループ（ＱＳＧ）：類似したＱｏＳ要件を有するアプリケーションタイプのグループ。
【００６９】
レート補償係数（α）：レート違反を補償するために計算される補償係数。
【００７０】
サービスのレート（Ｒ）または要求レート（ｒｅｑｕｉｒｅｄ＿ｒａｔｅ）：フローによって要求されるレート。
【００７１】
Ｒｅｓ（ｔ）：下りリンクでの時刻ｔにおいて確保されている帯域幅。
【００７２】
再送待ち行列（Ｒｘ）：再送を予定されているアプリケーションフローを記憶する再送待ち行列。
【００７３】
上りリンク（ＲＬ）：ＡＴからＡＮへの伝送無線リンク。
【００７４】
選択メトリック（Ｙ）：スケジュールを決定するためにアプリケーションフローの比較のために使用されるメトリック。
【００７５】
トラヒックプロファイル（σ、ｒ）：バースト性及びデータレートに関する指標。
【００７６】
伝送待ち行列（Ｔｘ）：所与のＢＴＳに関するアプリケーションフローを格納する伝送待ち行列。
【００７７】
待機時間パラメータ（γ）：ＡＮ内でＩＰパケットのＨＯＬに関する待機時間の値。
【００７８】
比例公平スケジューリングアルゴリズムへの適応重みの適用
メトリックＤＲＣ／Ｔに基づいてサービスを提供するためにフローを選択する比例公平（ＰＦ）スケジューリングアルゴリズムは、ｃｄｍａ２０００  １ｘＥＶ−ＤＯネットワークの下りリンクについて説明される。ＰＦアルゴリズムは、ほぼ同数の伝送スロットを各ユーザに提供するように設計される。このようなスケジューリングアルゴリズムを機能強化するために、異なるタイプのアプリケーションに対する多様なＱｏＳ要件を満たすためにＤＲＣ／Ｔアルゴリズムを拡張し、最適化する適応加重ＤＲＣ／Ｔアルゴリズムが本明細書において説明されている。各マルチメディアアプリケーションは、それぞれの特定のＱｏＳ要件を有する。スケジューリングアルゴリズムの目標は、多様なＱｏＳ要件を満たすことを含む。ここに提示されている、適応ｗ＊ＤＲＣ／Ｔアルゴリズムとも呼ばれている適応アルゴリズムは、アプリケーションフローがマルチメディアアプリケーションサービスを含む、ｃｄｍａ２０００  １ｘＥＶ−ＤＯネットワークの下りリンク用ＤＲＣ／Ｔアルゴリズムに優る種々の性能利点を提供する。ｃｄｍａ２０００  １ｘＥＶ−ＤＯネットワークの下りリンク上の遅延及びジッタに敏感なアプリケーションの遅延及びジッタ限度要件は、適応アルゴリズムを使用して満たされる。さらに、適応スケジューリングアルゴリズムによって、マルチメディアアプリケーションに関して、レート要件が満たされ、平均遅延が短縮されることが確実になる。マルチメディアアプリケーションは適応スケジューリングアルゴリズムの実現を説明するために一例として示されているが、ここに説明されている方法及び装置は、ＱｏＳ要件またはそれと関連付けられる他の定量化できる要件を有する他のアプリケーションに適用されてよい。
【００７９】
ウェブの閲覧及びゲームなどのレート要件及び待ち時間要件を有するアプリケーションの場合、適応スケジューリングアルゴリズムはレート保証を提供し、平均遅延を短縮する。レート要件だけを有する他のアプリケーションの場合、適応加重スケジューリングアルゴリズムはレート保証を満たすために使用されてよい。これらのＱｏＳ保証を提供する一方で、適応加重スケジューリングアルゴリズムはかなり高レベルで総スループットを維持するためにも機能し、純粋なＰＦスケジューリングアルゴリズムが使用されるときに達成される総スループットに近い総スループットを達成する。純粋なＰＦスケジューリングアルゴリズムとは、ＤＲＣ／Ｔ計算を利用するアルゴリズムを指す。ＱｏＳ違反のあるフローに特別な資源を与える一方で、適応加重スケジューリングアルゴリズムは公平に使用可能な資源を分散する。それと整合する多様な補償機構がここに示される。
【００８０】
図４は、マルチメディアアプリケーションをサポートするシステム８００を描いている。本発明が、フローがＱｏＳ要件を有する他のシステムにも適用可能であることに再び留意されたい。システム８００はパケットデータサービスノード（ＰＤＳＮ）８０６に結合されるマルチメディアソース８０２を含む。ＰＤＳＮ８０６は、基地局コントローラ（ＢＳＣ）８０４にも結合される。ＢＳＣ８０４は、複数であってもよい。ＢＳＣ８０４は基地局トランシーバシステム（ＢＴＳ）８０８、８１０を介して多様なＡＴ８１２、８１４、８１６、８１８等と通信する。システム８００は描かれているものより多いＢＴＳとＡＴを含んでよい。３つのフローが描かれている。つまり、ＰＤＳＮ８０６、ＢＳＣ８０４及びＢＴＳ８０８を介したマルチメディアソース８０２からＡＴ８１２への第１のフロー、ＰＤＳＮ８０６、ＢＳＣ８０４及びＢＴＳ８１０を介したマルチメディアソース８０２からＡＴ８１６への第２のフロー、及びＰＤＳＮ８０６、ＢＳＣ８０４、及びＢＴＳ８１０を介してマルチメディアソース８０２からＡＴ８１８への第３のフローである。１つのＡＴが複数のフローの宛て先となり得ることに留意されたい。ある例では、エムペグ（ＭＰＥＧ）タイプのアプリケーションの伝送は、音声とビデオを別々のフローに分離する。
【００８１】
システム８００で送信される各アプリケーションフローは、関連付けられたソースアドレス、宛て先アドレス及びＱｏＳ要件を有する。次にアプリケーションフローはソースから宛て先への伝送のためにスケジュールされる。アプリケーションフローは、図４に描かれているものと同様に経路を横切る。
【００８２】
各ＢＴＳ８０８、８１０は図５に描かれているようなフローの待ち行列を保持するように適応されている。各ＢＴＳが自身の下りリンク（ＦＬ）で各アプリケーションフローに対応する一組の待ち行列を保持することに留意されたい。１つのアプリケーションフローは１つのＡＴに向けられる。しかしながら、複数のフローが１つのＡＴに向けられてよいことに留意されたい。各フローは自身に関連付けられるサービスの質グループ（ＱＳＧ）タイプを有する。各ＱＳＧは、ＱｏＳパラメータの集合により定義される。あるＱＳＧの各フローは、集合の中のパラメータのそれぞれに対して特定の値を有する。例えば、１つのＱＳＧは遅延及びジッタを含む集合によって定義され得る。このようなＱＳＧのそれらのフローは、遅延及びジッタに関する要件を指定する。待ち行列内のフローのそれぞれについて、ＢＴＳは３つの独立の待ち行列を含んだ集合を保持する。つまり（１）オリジナルの伝送待ち行列（Ｔｘ）、（２）再送待ち行列（Ｒｘ）、及び（３）自動反復要求待ち行列（ＡＲＱ）である。一実施形態では、ＡＲＱ待ち行列は早期決定ＡＲＱなどのＢＴＳとＭＳ間で実行される任意のタイプの再送機構のためのフローを格納する待ち行列に対応し得る。マルチメディアアプリケーションは、遅延限度要件を有するテレビ会議などの遅延に敏感なアプリケーションを含み得る。遅延限度は、ＡＮからの伝送からＡＴによる受信までに許容される指定時間である。適応加重アルゴリズムは、遅延限度要件を満たすため、及びこのようなアプリケーションのＩＰパケットが経験した平均遅延を短縮するために機能する。レート要件と平均遅延要件の両方を有するアプリケーションの場合、適応加重スケジューリングアルゴリズムはレート要件を満たすため、及び平均遅延を短縮するために機能する。
【００８３】
マルチメディアビデオアプリケーションなどのいくつかのタイプのアプリケーションのための別の検討事項は、マルチメディア伝送における連続するパケット間が経る「ジッタ」である。ジッタは受信パケット間の時間の変動を指す。連続波形がわずかに早くまたはわずかに遅く受信機に到達するときにジッタは発生する。無線通信においては、このような波形は、通常、後に受信機で復号される論理１またはゼロを伝達する。ジッタとして定義されるタイミングの変動が、受信される伝送の視覚的な効果を歪ませる。適応加重スケジューリングアルゴリズムは、遅延に敏感なアプリケーションの場合の連続するパケット間の遅延変動だけではなく最悪のケースの遅延変動も削減する。
【００８４】
多様なユーザのＱｏＳ要件を満足する一方で、適応アルゴリズムは、それらのフローが「準拠しているとき」（conforming）のアプリケーションフローのレート要件を満たすようにも設計される。アプリケーションフローは、予め指定されたトラヒックプロファイルごとにデータを送信している場合に、準拠していると称される。レート要件のあるフローが準拠していない場合、つまりそれらが予め指定されたのより多くのデータをそのトラヒックプロファイルで送信する場合、アルゴリズムはより低いデータレートのフローに、より高い優先順位を与える。適応加重アルゴリズムはここではｃｄｍａ２０００  １ｘＥＶ−ＤＯネットワークとの関連において説明されているが、本概念及び方法は他のタイプの無線ネットワークにも適用され得る。
【００８５】
マルチメディアアプリケーションフローに関して、各フローは（１）トラヒックプロファイル、（２）ＱｏＳプロファイル、（３）インターネットプロトコル（ＩＰ）ソースアドレス及び（４）ＩＰ宛て先アドレスによって定義される。フローは、（５）Ｌ４プロトコルタイプ、（６）Ｌ４ポート番号、及び（７）Ｌ４宛て先ポート番号も含んでもよい。Ｌ４はプロトコルスタック内の転送制御プロトコル（ＴＣＰ）／低信頼（Ｕｎｒｅｌｉａｂｌｅ）データグラムプロトコル（ＵＤＰ）層を指す。例えば、ＭＰＥＧアプリケーションに対応するＭＰＥＧ音声フロー及びＭＰＥＧビデオフローは別々のフローとして処理されてよい。
【００８６】
各フローはトラヒックプロファイルによって指定され、それがそのトラヒックプロファイルに適応していることを確実にするために監視または変形される。トラヒックプロファイルは、σとして特定されるバースト性の測度及びｒとして特定されるフローの平均データレートを表す変数により定義される。したがって、各フローはトラヒックプロファイル（σ、ｒ）によって記述される。ＱｏＳプロファイルは、以下のパラメータの少なくとも１つにより定義される。つまり、（１）ＩＰパケットについて伝送から受信までに対して許容される時間を定義し、「Ｄ」として特定される遅延限度。マルチメディアアプリケーションフローの場合、システムは遅延限度を指定することができる。ウェブ閲覧などのいくつかの他のアプリケーションフローの場合、システムは遅延限度の代わりに、あるいは遅延限度に加えて平均遅延（ＡｖｇＤ）を指定することができる。（２）ＡＴでの受信パケット間の時間の最大許容変動を定義し、「ｊ」として特定されるジッタ限度。（３）「Ｒ」または「ｒｅｑ＿ｒａｔｅ」として特定されるサービスのレート（つまり要求レート）。
【００８７】
遅延限度Ｄを定義するために、多様なＡＮ要素及び１台のＡＴを含むタイミング図である図６を参照する。マルチメディアフローは、ＰＤＳＮ、ＢＳＣ及びＢＴＳを介してマルチメディアソース（図示せず）からＡＴに送信される。ＩＰパケットは時間ｔ0でＰＤＳＮから送信され、時間ｔ3でＡＴで受信される。パラメータＤは、時間ｔ0から時間ｔ3までの最大許容時間を定義する。つまりＤはｔ3−ｔ0の範囲（複数の場合がある）を指定する。
【００８８】
ジッタ限度ｊを定義するために、ＡＮ要素及び１台のＡＴを含むタイミング図である図７Ａを参照する。第１のパケットはＰＤＳＮから時間ｔ1で送信され、ＡＴで時間ｔ1’で受信される。第２のパケットはＰＤＳＮから時間ｔ2で送信され、ＡＴで時間ｔ2’で受信される。ジッタ限度ｊは、連続パケット間の最大許容変動を定義し、変数は（ｔ2’−ｔ1’）−（ｔ2−ｔ1）として与えられる。図７Ｂは複数のスロット上で送信される連続ＩＰパケットをさらに詳説する。
【００８９】
一実施形態では、ＱｏＳプロファイルは、ＱｏＳスケジューリンググループ（ＱＳＧ）と呼ばれるグループに分類される。表１は、カテゴリを一覧表示する。
【表１】
2010166582.tif 000003
【００９０】
図８は、適応加重スケジューリングアルゴリズムに従ったフローの処理を例示する。フロー９００、９０２、９０４及び９０６は、「Ｓ」が付されたスケジューリング装置９０８によって処理される。スケジューリング装置９０８は、適応加重スケジューリングアルゴリズムを適用する。適応加重スケジューリングアルゴリズムは、ＱＳＧプロファイルがフローのそれぞれに使用される。ＱＳＧプロファイルは、下記に詳述されるように、適応加重を計算するために使用される変数を特定する。スケジューリング装置９０８は、次に、選択されたＡＴにスケジュールされた伝送を出力する。
【００９１】
ＤＲＣ／Ｔアルゴリズムと呼ばれるＰＦスケジューリングアルゴリズムが説明される。アルゴリズムにおいて、パケットが、例えばＱ１、Ｑ２、．．．Ｑｍなどのｍ個の待ち行列へと分類される。ＤＲＣ［ｋ．ｎ］を、スロットｎについてフローｋに対応し、移動局によって要求されるＤＲＣとする。スケジューラは、選択メトリックＹ［．,．］の最高値の付いたフローを選択する。
【数１】
2010166582.tif 000004
【００９２】
Ｙ［ｋ，ｎ＋１］は、スロット（ｎ＋１）の中の待ち行列Ｑｋのための選択メトリックである。ここで、
【数２】
2010166582.tif 000005
【００９３】
及び
【数３】
2010166582.tif 000006
【００９４】
ここで使用されるｔcは時間定数であり、この時間定数で平均が計算される。
【００９５】
適応ｗ＊ＤＲＣ／Ｔアルゴリズム
一実施形態では、「適応ｗ＊ＤＲＣ／Ｔ」アルゴリズムと呼ばれる適応加重スケジューリングアルゴリズムは、初期の重みを各フローに割り当てる。フローｋに割り当てられる初期重みがｗkによって示され、スロットｎについてフローｋに対応し、ＡＴによって要求されるＤＲＣがＤＲＣ［ｋ，ｎ］であると仮定する。適応ｗ＊ＤＲＣ／Ｔアルゴリズムは、あらゆるスロットｎの中のフローｋごとに以下のメトリックを計算する。
【数４】
2010166582.tif 000007
【００９６】
ここではフローｋとスロットｎに関するスループット、Ｔk［ｎ］は、ＰＦアルゴリズムのＤＲＣ／Ｔについて定義されるとおりである。適応加重スケジューリングアルゴリズムで使用されるように、ａｗｋ［ｎ］はスロットｎのフローｋに関する適応重みである。適応ｗ＊ＤＲＣ／Ｔスケジューリングアルゴリズムは複数のモードで動作し、モードはＱＳＧによって定義される。スロットｎのフローｋに関する適応重み、ａｗｋ［ｎ］は、下記に詳説されるように、スケジューラモード及びさらに選択された方針または機構の組に基づいて計算される。式（４）がフローごとに計算され、適応重みが各フローに特定な公式化に従って計算されることに留意されたい。言い換えると、スケジューリングアルゴリズムはあるフローのＱｏＳプロファイルを考慮し、ＱｏＳを用いて、フローのための適応重みの計算を行う。このようにして、さまざまなＱｏＳ要件を有するさまざまなフローが、異なるように計算される適応重みを有し得る。スケジューリングアルゴリズムは、次にＹｋ［ｎ］という最高値のフローを選択して、スロットｎでサービスを提供する。
【００９７】
適応ｗ＊ＤＲＣ／Ｔスケジューラは次のモードで動作する。
【００９８】
モードＩ［ａｗ＊ＤＲＣ／Ｔ］（ｒ，ｄ，ｊ）：遅延及びジッタに敏感で、遅延限度及びジッタ限度に関する厳しい要件を有し、なんらかの最小レートを要求するアプリケーションに対して設計される。
【００９９】
モードＩＩ［ａｗ＊ＤＲＣ／Ｔ］（ｒ，ｄ）：平均遅延要件及びレート要件のあるアプリケーションに使用される。
【０１００】
モードＩＩＩ［ａｗ＊ＤＲＣ／Ｔ］（ｒ）：指定されるレート要件だけを有するアプリケーションに使用される。
【０１０１】
モードＩＶ［ＤＲＣ／Ｔ］：ＱｏＳ計画を指定しないが、ＤＲＣ／Ｔアルゴリズムによってサービスの提供を受けるフローのために使用される。
【０１０２】
ＱｏＳ要件に基づいて、あるフローに対して、適応ｗ＊ＤＲＣ／Ｔアルゴリズムの特定のモードが指定されてよい。モードＩＩは、スケジューラによってそのフローに指定されるスループットを増加するためにあるフローに対して使用されてよい。例えば、モードＩＩは対応するアプリケーションフローのためのスループットを潜在的に増加するためにＦＴＰアプリケーションのために使用されてよい。
【０１０３】
アプリケーションをグループ化する、つまりＱＳＧの一例が以下に示される。
【０１０４】
グループＩ：遅延限度及び遅延変動に関する厳しい要件のあるボイスオーバＩＰ（ＶｏＩＰ）のようなアプリケーション。多くの場合、このようなアプリケーションはレート要件（複数の場合がある）も有することに留意されたい。スケジューラモードＩを使用する。
【０１０５】
グループＩＩ：遅延限度及び遅延変動に関する厳しい要件のあるマルチメディア会議アプリケーション。これらのアプリケーションのいくつかは適応型であっても、一貫した高品質のためにサービスのレートを確実にすることが望ましい。スケジューラモードＩを使用する。
【０１０６】
グループＩＩＩ：遅延限度、レート及び遅延変動に関する要件のあるビデオストリーミングアプリケーション。スケジューラモードＩを使用する。
【０１０７】
グループＩＶ：レート及び（平均）遅延要件のあるウェブ閲覧アプリケーション、スケジューラモードＩＩを使用する。
【０１０８】
グループＶ：レートのあるＦＴＰアプリケーション、スケジューラモードＩＩＩを使用する。または、遅延制約が緩められたスケジューラモードＩＩを使用する。
【０１０９】
グループＶＩ：ベストエフォートアプリケーション、適応加重を使用することなく、ＰＦアルゴリズム、つまりＤＲＣ／Ｔアルゴリズムを使用する。
【０１１０】
データベーストランザクション、ゲーム及び他のアプリケーションが、それぞれのＱｏＳ要件に従って適切なグループに分類されてもよいことに留意されたい。
【０１１１】
図９は、レベルＩとレベルＩＩを含む（これらに限定されない）複数のレベルを有する適応加重スケジューラを描く。レベルＩスケジューラは複数のスケジューラＳ１、Ｓ２、Ｓ３，．．．Ｓｍを有し、ｍはグループの総数を指す。図９の各レベルＩスケジューラは適応ｗ＊ＤＲＣ／Ｔスケジューリングアルゴリズムのある特定の動作モードを実行し、そのグループから１つのフローを選択する。第１に、レベルＩスケジューラはＹの一部、特にスループットＴ及びレート補償係数αを計算する。次に、レベルＩＩスケジューラはフローを検討し、レベルＩスケジューラによる選択メトリックＹの完全な計算に十分な入力をレベルＩスケジューラに供給する。いったんＹがすべての未決フローに関して完全に計算されると、レベルＩスケジューラはＹ値を評価し、Ｙの値が最も高いフローを選択する。各レベルＩスケジューラは類似したＱｏＳ要件を有するフローのグループを評価する。各レベルＩスケジューラの選択されたフローは、次に他のグループからのフローとの比較のためにレベルＩＩスケジューラに供給される。レベルＩＩスケジューラはグループごとに１つ選択されたフローを検討し、メトリック（ａｗ＊ＤＲＣ／Ｔ）つまりＹが最も高いフローを選択する。このプロセスは、スケジューラがサービスを提供するフローを選択する必要があると、スロットごとに繰り返される。別の実施形態は１つのレベルスケジューラを使用してよい、あるいは図９に描かれているより多くのレベルを使用してよい。別の実施形態は別の数のレベルＩスケジューラを含んでよく、レベルＩスケジューラはフローの編成に応じる。
【０１１２】
包括的に、適応重み計算は複数のパラメータの関数として与えられ、以下として示される。
【数５】
2010166582.tif 000008
【０１１３】
遅延補償関数はΦとして特定される。待機時間パラメータはγとして特定される。レート補償関数はαとして特定される。ＤＲＣ補償関数はβとして特定される。機能拡張されたジッタ補償係数はδとして特定される。パラメータのすべてがすべてのマルチメディアサービスのための実質的な値を有するわけではないことに留意されたい。例えば、あるフローの唯一のＱｏＳ要件が、指定されたデータレートであるときには、変数αが指定され（レートパラメータは実質的な値を有し）、他のすべてのパラメータが値１に等しく設定される。このケースでは、適応重み計算にレートパラメータだけが含まれる。一実施形態では、適応重みは以下のように計算される。
【数６】
2010166582.tif 000009
【０１１４】
ここで、演算子は乗算である。以下の説明は、適応重み計算に含まれ得る多様な補償項の詳細を提供する。
【０１１５】
モードＩアプリケーションの場合、ＱｏＳプロファイルは式（６）に示されるパラメータのすべてを指定する。適応重み計算は、遅延閾値違反に起因する遅延補償、待機時間閾値違反に起因する遅延補償、レート違反に起因するレート補償、及び機能強化されたジッタ閾値違反に起因する機能強化ジッタ補償を考慮する。概念は、指定されたＱｏＳ要件を違反しているフローの重みを増やすことである。ＱｏＳ要件（複数の場合がある）の違反時にトリガされ、このようなフローにはクレジットが与えられる。クレジットは、遅延補償関数に適切な値でフローの重みを乗算することにより実現される。これは、さらにレート補償及び機能強化されたジッタ補償によって乗算される。
【０１１６】
対照的に、フローが過剰なサービスを享受していると考えられるときには、このようなフローがペナルティを課される可能性がある。フローは種々の方法のどれかでペナルティを課され得る。ある方法によれば、フローはフロー重みを減ずることによって直接的にペナルティを課され得る。別の方法によれば、フローは遅れをとっている他のユーザ（つまり必要とされるＱｏＳを達成していないフロー）の重みを増加する一方で、フロー重みを維持することによって間接的にペナルティを課され得る。
【０１１７】
遅延閾値の違反（複数の場合がある）の埋め合わせを行うために遅延補償を計算するための種々の機構がある。フローｋに関する遅延閾値がｄｔｈ＿φkによって示され、スロットｎのフローｋに関する遅延閾値違反に起因する遅延補償がφk［ｎ］によって示されると仮定する。遅延補償φk［ｎ］を計算するために、フローごとに３つすべての待ち行列（つまりＴｘ、ＲＴｘ及びＡＲＱ）内のパケットを考慮する。
【０１１８】
フローが複数のスロットを連続して消費したり、他のフローを飢えさせたり（starve）しないことを保証するために、φに対する最大閾値と最小閾値も、フローごとに指定される。これは、遅延閾値違反によるフローの遅延補償項が最小閾値と少なくとも同程度に有効であることを確実にするためにも設定される。φthres,min,k及びφthres,max,kをフローｋについて指定される最小閾値と最大閾値とする。この結果、（すべてのｋとすべてのｎについて）以下となる。
【数７】
2010166582.tif 000010
【０１１９】
以下の定義が使用されて、遅延補償の計算が進められる。
【０１２０】
Ｄ［ｎ］：スロットの始まりで遅延閾値違反を経験するフローの集合を定義する（つまり、このようなフローのそれぞれは、そのフローの遅延閾値を越えた、少なくとも１個のパケットを、スロットｎの始まりにおいて有する）。
【０１２１】
ｄｅｆｐｋｔｓk［ｎ］：スロットｎの始まりでのフローｋにについて「不足（deficit）」パケットを定義する。不足パケットとは、フローの中でまだ送信されていないパケットであり、ｄｅｆｐｋｔｓはフローｋに関して遅延閾値より長くＢＴＳに留まった、
等しいサイズの（ＭＡＣ）パケット数として特に定義される。
【０１２２】
ｒｅｑｕｉｒｅｄ＿ｒａｔｅk：フローｋの要求レートを定義する。
【０１２３】
ｎｄｅｆｐｋｔｓk：以下のように特に定義される、フローｋについて正規化された不足パケット数を定義する。
【数８】
2010166582.tif 000011
【０１２４】
ＢＴＳ、ＢＳＣ及びＰＤＳＮ内のパケットが等しくないサイズあるかも知れなく、したがってパケットの代わりにここで不足ビット数をカウントすることは有益であることに留意されたい。
【０１２５】
フローのＨＯＬパケットが事前に指定された閾値より長い時間期間の間ＢＴＳ待ち行列にある場合、フローは以下の機構を使用して補償され得る。この目的で使用される待機時間閾値は、φを計算するために使用される閾値以上でなければならない。フローｋに関する待機時間閾値はｄｔｈ＿γkによって示され、待機時間閾値はｄｔｈ＿γk≧ｄｔｈ＿φk、∀ｋによって制約される。フローのＨＯＬパケットを選択するために、最初にフローのＴｘ待ち行列、ＲＴｘ待ち行列及びＡＲＱ待ち行列からのＨＯＬパケットを検討し、ＢＴＳでの待ち時間に基づいて待ち行列を選択する。つまり最も長い期間ＢＴＳ内で待機している待ち行列を選択する。γk［ｎ］をスロットｎの始まりにあるフローｋに関する待機時間補償とし、Ｓｋ［ｎ］をスロットｎの始まりでフローｋのＨＯＬパケットがＢＴＳ待ち行列で費やした時間とする。フローｋごとに、また、最小閾値Ｓthres,min,k及び最大閾値Ｓthres,max,kが指定され、
【数９】
2010166582.tif 000012
【０１２６】
を満たす。
【０１２７】
一実施形態によれば、フローが遅延閾値違反または待機時間閾値違反を経験しているときに、遅延補償が適用される。この機構はＤＲＣデータレート要求を適応重みに適用する。βk［ｎ］をスロットｎでのフローｋについてのＤＲＣ調整関数とする。フローｋごとに、最小閾値βtmin,thres,k及び最大閾値βmax,thres,kが指定され、
【数１０】
2010166582.tif 000013
【０１２８】
を満たす。
【０１２９】
前述された補償機構が、映像／音声会議などのいくつかの用途のためのフローの遅延変動を削減するのに役立つ一方、遅延変動（ジッタ）制御をより効果的に含み、遅延変動をさらに削減することが望ましい場合がある。以下の機構は、フローの連続パケット間の遅延変動を削減することによって効果的な遅延変動制御を提供する。さらに大きなＩＰパケットサイズのフローはこの補償機構からより多くの利点を得る。
【０１３０】
ａｔ（ｋ，ｊ）がＢＳＣの進入時にフローｋのＩＰパケットｊの到着時間であると仮定する。ｄｔ（ｋ，ｊ）を、ＢＴＳからのこのＩＰパケットの出発時間とする。つまり、このときまでに、このＩＰパケットのすべての部分はＢＴＳにおける下りリンクスケジューラによって送信されている。ｐｅｎｄk,j［ｎ］をＢＴＳとＢＳＣでのフローｋのＩＰパケットｊのバイト単位での総長とする。また、ｄｖk,targetがフローｋについての連続ＩＰパケット間のターゲット遅延変動（ジッタ）であり、ｄｖk,thresがｄｖk,thres＜ｄｖk,targetとなるようにこのフローについて事前に指定された機能拡張ジッタ閾値である。一実施形態では、アルゴリズムは、連続ＩＰパケット間の遅延変動がｄｖk,thresを超えるときにフローｋの機能強化された変動補償機構をトリガする。
【０１３１】
図１０は一実施形態に対応するアーキテクチャ図を提供する。各アプリケーションフローは、トラヒックプロファイル、ＱｏＳプロファイル及びＤＲＣ要求、つまり要求データレートによって説明される。各トラヒックプロファイルはバースト性の測度及び平均データレートを含む。各ＱｏＳプロファイルは、クラスタイプ及びパラメータ限度を含む。クラスタイプはモードＩ、モードＩＩ、モードＩＩＩ、またはモードＩＶの内の１つであってよい。限度は遅延、ジッタ及び要求データレートの限度を指定する。ウェブ閲覧などのいくつかのアプリケーションは遅延限度の代わりに平均遅延を指定してよい。モードＩに関する遅延閾値はジッタ限度未満となるように選ばれ、モードＩＩの場合、遅延閾値は平均遅延未満となるように選ばれる。機能拡張されたジッタ閾値はジッタ限度未満となるように選ばれる。別の実施形態では、各アプリケーションフローにさらに多くのまたはさらに少ない情報を適用してよく、ＱｏＳ要件はネットワーク及び構成に固有であってよい。
【０１３２】
図１１は、クラスタイプごとのＱｏＳ要件及びＱｏＳパラメータを明記する表である。示されているように、モードＩＶが、ＱｏＳ要件が指定されないベストエフォートに対応する一方、モードＩは最も厳しい要件に対応する。別の実施形態は他のＱｏＳ要件、ＱｏＳパラメータ及び／またはモードを含んでよい。
【０１３３】
図１２Ａから図１２Ｅは、アプリケーションフローの処理及びアクティブなアプリケーションフローの一部としてのそのアプリケーションフローのスケジューリングを描いている。図１２Ａは、個々のアプリケーションフローのための初期化及びセットアップを描く流れ図である。プロセスは、ステップ１１００で開始して補償パラメータごとに使用される機構を選択する。補償パラメータは、遅延（Φ）、未決時間（γ）、ＤＲＣ（β）、ジッタ（δ）、及びレート（α）を含むが、これらに限定されない。ステップ１１０２では、適用可能な補償パラメータに関する閾値が選択される。補償パラメータがＡＮにとって重要なアプリケーションフローの任意のパラメータを含む場合があることに留意されたい。ステップ１１０２では、中間重みを計算するためのアルゴリズムが選択される。中間重みは、スケジューリングのために使用される適応重みを計算する上で使用される。ステップ１１０６では、適応重みを計算する上で使用されるスケーリングパラメータ（Ｃ）及び優先順位係数（Ｚ）の両方が設定される。ステップ１１０８では、このアプリケーションフローの初期重みが設定される。ステップ１１１０では、アプリケーションフローのＱｏＳ要件が評価される。ＤＲＣ要求により特定されるレート以外に指定されるＱｏＳ要件がない場合、デフォルト条件が使用される。デフォルト条件は前述されたように「ベストエフォート」と呼ばれる。この場合、デフォルト処理によって、このアプリケーションフローに使用される補償係数のすべては１に等しく設定される。本実施形態の場合、このケースでは、式（６）の計算で乗算演算子が使用され、したがって係数を１に設定すると、結果、それらの係数が無視される。つまりそれらの係数は加重に影響を及ぼさない。別の実施形態では、他の機構及び関数を実現してよく、したがって特殊な係数またはすべての補償係数を無視するために他の機構を使用してよいことに留意されたい。
【０１３４】
ステップ１１１２と１１１６でベストエフォート処理が続行する。結果として生じるスケジューリング係数の計算は、比例公平計算と一致している。アプリケーションフローがＱｏＳ要件を有する場合、処理はステップ１１１４に続行する。ステップ１１１４と１１１６は、以後の図で続行される処理を示す。
【０１３５】
図１２Ｂはステップ１１１４から図１２Ａの処理を続行する。ステップ１１２０で、現在のスロットの処理が開始する。ステップ１１２２では、アプリケーションフローのクラスタイプとしての決定が下される。モードＩはステップ１１２８で処理され、モードＩＩはステップ１１２６で処理され、モードＩＩＩはステップ１１２４で処理される。モードＩのＱｏＳパラメータはステップ１１２８で監視される。モードＩＩのＱｏＳパラメータはステップ１１２６で監視される。モードＩＩＩのＱｏＳパラメータはステップ１１２４で監視される。次にＱｏＳ違反チェックが、図１２Ｃ及び図１２Ｄにさらに詳説される、ステップ１１３０、１１４０及び１１５０で行われる。
【０１３６】
アプリケーションフローの処理は、モードＩ、ＩＩまたはＩＩＩアプリケーションに関しては、図１２Ｃのステップ１１３０に続行する。ステップ１１３２では、アルゴリズムはレート違反がないか周期的に監視する。レート補償計算が周期的に実行され、それ以後複数のスロットについて使用されることに留意されたい。レート違反がステップ１１３４で検出されると、処理はステップ１１３８に続行して補償係数（α）を計算する。さもなければ、レート補償係数（α）はステップ１１３６で１に等しく設定される。次に処理は図１２Ｅにさらに詳説されるステップ１１６０に続行する。
【０１３７】
アプリケーションフローの処理は、モードＩまたはＩＩアプリケーションに関しては、図１２Ｃのステップ１１４０に続行する。ステップ１１４２では、方法は各スロットで遅延違反及びジッタ違反がないか監視する。遅延及び／またはジッタ違反がステップ１１４４で検出されると、処理はステップ１１４８に続行し、初期化時に選択される機構に従って遅延補償係数（Φ）を計算する。機能拡張されたジッタ補償を要求したモードＩフローの場合には、機能拡張されたジッタ補償係数（δ）も次いで計算される。機能拡張されたジッタ補償を要求しなかったモードＩフローの場合、及びモードＩＩフローの場合、δは１に等しく設定される。または、遅延補償係数（Φ）はステップ１１４６で１に等しく設定され、δは１に等しく設定される。処理は、次に図１２Ｅにさらに詳説されるステップ１１６０に続行する。モードＩまたはＩＩアプリケーションフローの場合、違反チェックは直列または並行して行われてよい。言い換えると、レート違反及び遅延／ジッタ違反のチェックは時間的に連続して、または同時に実行されてよい。
【０１３８】
アプリケーションフローの処理は、モードＩアプリケーションに関しては、図１２Ｄのステップ１１５０に続行する。ステップ１１５２では、方法は待機時間違反がないか監視する。待機時間違反がステップ１１５４で検出されると、処理は、ステップ１１５８に続行して初期化時に選択された機構に従って待機時間補償係数（γ）を計算する。さもなければ、待機時間補償係数（γ）はステップ１１５６で１に等しく設定される。処理は、次に図１２Ｅにさらに詳説されるステップ１１６０に続行する。モードＩアプリケーションフローの場合、違反チェックが直列または並行して行われてよいことに留意されたい。言い換えると、レート違反、遅延／ジッタ違反及び待機時間のチェックは時間的に連続してまたは同時に実行されてよい。
【０１３９】
図１２Ｅは、ステップ１１６０及びステップ１１１６からの処理を描いている。ステップ１１６２は、以下に示されるように、ＱｏＳパラメータ及び補償係数の関数としてアプリケーションフローの適応重みを計算する。
【数１１】
2010166582.tif 000014
【０１４０】
ステップ１１６４では、スケジューリング係数またはスケジューリングメトリックが、以下のように計算される。
【０１４１】
スケジューリング係数＝ａｗ＊（ＤＲＣ／Ｔ）                              （10）
スケジューリングアルゴリズムは、次にアクティブなアプリケーションフローのそれぞれに関して計算されるスケジューリング係数に従ってアプリケーションフローをスケジュールする。
【０１４２】
図１３は、一実施形態によるスケジューリングアルゴリズムを適用するよう適応されたＢＴＳ１２００を描いている。ＢＴＳ１２００は、それぞれが通信バス１２１０に結合されるスケジューリング装置１２０２、アプリケーションフロー処理装置１２０６、ＱｏＳパラメータ評価１２０４、適応重み計算装置１２１２、及びＣＰＵ１２０８を含む。スケジューリング装置１２０２はアプリケーションフローごとにスケジューリング係数を作成し、次にスケジューリング係数に従って多様なアクティブなアプリケーションフローから選択することによりスケジューリングを実行する。所与のシステムの方針及び目標はスケジューリングアルゴリズムに組み込まれる。ＱｏＳパラメータ評価１２０４はＱｏＳ違反がないか監視し、情報をスケジューリング装置１２０２と重み計算装置１２１２に提供する。アプリケーションフロー処理は、パケットを宛て先ＡＴに向けることと、宛て先ＡＴからスケジューリングのために使用されるＱｏＳ情報を受け取ることと、ＱｏＳパラメータ評価１２０４にこのような情報を供給することとを含む（これらに限定されない）処理を実行する。ＢＴＳ１２００は、中間情報を記憶し、平均、フロー待ち行列等を計算するために使用されるデータを保持するためのメモリ１２１４も含む。違反チェックはＢＴＳで実行される。一実施形態は、フローごとに送出されるバイト数をカウントし続け、それをレート違反チェックに使用する。各パケットは、ＢＳＣに到達するとタイムスタンプを刻印される。パケットがＡＮ、ＢＳＣまたはＢＴＳに留まっている限り、時間は増分し続ける。ＢＴＳは閾値違反の検出のためにこの時間を使用し、次に、フローに従って遅延関数、待機時間関数、または機能強化されたジッタ補償関数を計算する。
【０１４３】
許可制御
許可制御とは、データサービスを要求するユーザにエントリを許可する際の決定プロセスを指す。新規ユーザがＱｏＳ要件を有するアプリケーションなどのデータサービスを要求すると、ＡＮはこのような使用をサポートするために使用可能な資源があるかどうかを判断する。許可プロセスは、ＱｏＳ統計とネットワーク統計だけではなく、要求されたアプリケーション、現在の使用量も考慮する。ＡＮが新規ユーザがサポートされてよいと判断すると、対応するアプリケーションフローが許可される。または、現在使用可能な資源がない場合には、アプリケーションフローは、拒絶されるか、待ち行列に入れられ、ステータスの変化を待つ。新規ユーザが実際には追加のサービス、つまり追加のアプリケーションフローを要求している現在アクティブなアプリケーションフローを有しているユーザであり得ることに留意されたい。
【０１４４】
許可制御に加えて、及び許可制御の一部として、アクティブアプリケーションフローを終了するために先処理のプロセスが実現されてよく、そこでは現在の動作状態が先処理決定を下すために評価される。この場合、現在のフローのそれぞれは、データレートだけではなくＱｏＳ違反についても評価される。
【０１４５】
本項は、適応セクタ単位許可制御アルゴリズムを提示する。このような許可制御アルゴリズムは、ある無線マルチメディアネットワークでフローを許可する（つまり先処理する）かどうかを決定する。したがって、あるネットワークで許可されてよい（各クラスの）フロー数を決定することが可能である。本明細書で提示されている許可制御アルゴリズムの実施形態は、ユーザ間、及びユーザ内のＱｏＳ監視を実行するための機構を含み、次にこの情報を許可及び／または先処理決定に利用する。このような実施形態は、フロー単位及びユーザ単位のＱｏＳ要件が許可されたフロー及びユーザについて満たされていることを確実にするように設計されている。このような機構は許可制御アルゴリズム及び階層スケジューリングアルゴリズムの調整を容易にする。
【０１４６】
スケジューリング及び許可制御は、無線ネットワークの下りリンク（ＦＬ）ＱｏＳ管理の一部であり、このような管理は複雑な課題である。ＱｏＳ管理は通信網の設計及び運用における重大な検討事項である。アプリケーションフローはシステムにより定義されるような基準に従って分類される。一実施形態では、この分類はＱｏＳ要件に従っている。第１に、許可制御は現在の動作状態の元で許可され得るフローの数を決定する。このフローの数は次にクラス単位のフロー数に分割される。システムは、次にそれぞれの許可されているフローについてＱｏＳ要件を満たすために動作する。フロー数が経時的に、及びアプリケーションのタイプにより動的に変化し得ることに留意されたい。例えば、第１の時点で、アクセスネットワーク（ＡＮ）は、特定数のフローが各タイプのアプリケーションに対して許可されている第１のシナリオをサポートしているかも知れない。第２の時点で、ＡＮは、異なる数のフローがアプリケーションのタイプの内の少なくとも１つに対して許可される第２のシナリオをサポートしているかも知れない。
【０１４７】
スケジューラ（つまりスケジューリングアルゴリズム）は、許可されたフローの間で公平を期す方策を実施する。スケジューラは、さらにＱｏＳ違反を有するフローの優美な回復を実行しようと努める。運営者の収益及び利益は、使用されるスケジューリングアルゴリズムの有効性に依存している。さらに効率的で機能豊富なアルゴリズムはこれらの利益を増加するための機会を与える。
【０１４８】
許可制御に関して、一実施形態では、加入係数に基づいた方法が実現される。加入係数に基づいた方法が多くの場合有線（wireline）ネットワークのための許可制御アルゴリズムで使用されることに留意されたい。無線ネットワークでは、各ユーザのチャネル状態は変化し続けるため、ＢＴＳスケジューラから見た下りリンク容量も変化し続ける。有線加入係数に基づいたアルゴリズムは不変のリンク容量を仮定しているため、無線ネットワークではそのまま適用できない。
【０１４９】
無線ネットワークの場合、一実施形態では、ＦＬ管理のための適応加入係数（ＡＳＦ）に基づいた許可制御アルゴリズムが提供され、そこではネットワークはＱｏＳ要件を有する複数のアプリケーションフローがサポートされる。無線ネットワークにおけるＡＳＦ許可制御により、ＱｏＳ統計及びネットワーク統計を監視することにより加入係数が動的に更新される。多様な機構が使用されて更新機能が実行される。したがって、適応加入係数を使用して補正処置を講じることが可能である。さらに、ＡＳＦは先処理法を実現するために使用される。
【０１５０】
ＡＳＦ、ＡＳ（ｔ）は毎時ｔに計算される。プロセスは、ＡＳ（ｔ）が１＜ＡＳmin_prespecified≦ＡＳ（ｔ）≦ＡＳmax_prespecified＜∞，∀ｔとなるように、ＡＳ（ｔ）についての最小閾値ＡＳmin_prespecifiedと最大閾値ＡＳmax_prespecifiedを求める。初め、値ＳinitialがＡＳＦに割り当てられ、その結果ＡＳ（０）＝Ｓinitialとなる。
【０１５１】
図１４は、最大データレート、予約帯域幅、及び使用可能な帯域幅を時間の関数としてプロットするタイミング図である。ＢＴＳが下りリンクでデータを送信し得る最大レート（Ｌmax）は、資源の割り当てのための上限となる。アクティブなアプリケーションフローが評価されて予約済み帯域幅Ｒｅｓ（ｔ）が決定される。ＱｏＳ違反及びネットワーク負荷関連の統計を使用して、時刻ｔで予約されることが所望される適応加入係数及び下りリンク容量の推定値Ｌ（ｔ）の計算が実行される。Ｌ（ｔ）≦Ｒｅｓ（ｔ）であり得ることに留意されたい。例えば、許可フローがそれらが許可されたときに非常に良好なチャネル状態を享受していたと仮定する。いま、複数のフローのチャネル状態が悪化し、いくつかのフローは関連付けられたＱｏＳ保証を達成していない。この場合、システムはさらに多くのフローを許可することに控えめになり、Ａｖａｉｌ（ｔ）＝０と設定することを所望し得る。他方、Ｌ（ｔ）＞Ｒｅｓ（ｔ）の場合、システムはＡｖａｉｌ（ｔ）＝Ｌ（ｔ）−Ｒｅｓ（ｔ）と設定し得る。したがって、値Ｌ（ｔ）は過去のＱｏＳ違反統計及びネットワーク負荷関連統計に基づいて時刻ｔにおいて予約されることが所望される下りリンク容量の推定値であり、ＬmaxとＡＳＦの関数として以下のように計算される。
【数１２】
2010166582.tif 000015
【０１５２】
制約が付き、
【数１３】
2010166582.tif 000016
【数１４】
2010166582.tif 000017
【０１５３】
である。使用可能な帯域幅Avail（ｔ）は以下のように計算される。
【０１５４】
Avail(t)=maximum (L(t) - Res(t), 0)                                    （14）
図１４に描かれているような資源の多様な測度は、ユーザから受信されるデータレート制御（ＤＲＣ）データ要求により決定される。各ユーザは、上りリンクでＤＲＣデータ要求を送信する。ｃｄｍａ２０００  １ｘＥＶ−ＤＯまたは他のＨＲＰＤタイプのシステムでは、ユーザはＲＬ伝送の各スロットでＤＲＣデータ要求を送信する。描かれているように、ユーザ１からのデータ要求（ＤＲＣ  １）及びユーザ２からのデータ要求（ＤＲＣ２）は経時的に変化する。データ要求及び所要のＱｏＳは予約帯域幅（Ｒｅｓ）を決定する。ＤＲＣ値とＲｅｓの関係が説明図として示されることに留意されたい。別の実施形態及びシナリオは別の関係を招き得る。
【０１５５】
各アプリケーションフローは、平均レート及びバースト性という点で特定されたトラヒックプロファイルを有し、フローｆkのトラヒックプロファイルは（σk，ｒk）で与えられる。ここでは、ｒkはフローｆkについての平均要求レートであり、σkはバースト性の測度であり、フローｆkについての要求レートはｒｅｑ＿ｒａｔｅ（ｆk）＝ｒkで与えられる。
【０１５６】
一実施形態によれば、許可制御は、許可のために、フローｆkを評価する。許可制御は、最初に、フローｆkに対応する、ユーザについての観察されたＤＲＣｕ（ｆk）を適用して要求レートを満足させる。観察されたＤＲＣは以下のように、そのユーザについての平均ＤＲＣデータ要求以下である。
【数１５】
2010166582.tif 000018
【０１５７】
ＡＳＦ、ＡＳ（ｔ）の計算が行われ、次にこれらを用いてＡｖａｉｌ（ｔ）が以下のように計算される。
【数１６】
2010166582.tif 000019
【０１５８】
最後に、時刻ｔでのフローｆkに対する許可の決定を検討する。
【数１７】
2010166582.tif 000020
【０１５９】
フローｆkが許可されると、図１４に描かれているような資源の測度は以下のように更新される。
【数１８】
2010166582.tif 000021
【数１９】
2010166582.tif 000022
【０１６０】
ＡＮは、すべての許可されたフローについてＱｏＳ統計を監視し続け、ネットワーク関連統計を監視し続ける。この監視は、加入係数を適応するためのフィードバックを供給する。
【０１６１】
ＡＳ（ｔ）についての適応方法：セクタ単位のＱｏＳ統計及びネットワーク統計
図１８Ａから図１８Ｅは、ＱｏＳ要件を有する複数のアプリケーションフローをサポートするシステムの許可制御のための方法３００の流れ図を提供する。図１８Ａでは、新しいフローのための要求が判断菱形３０２でＡＮによって受け取られると、許可制御手順がステップ３０４で稼動される。さもなければ、プロセスは新規フロー要求を待つ。この時間の間、ＡＮは、現在の動作状態を監視し続けて現在アクティブなフローに関するＱｏＳ統計及びフローについてのネットワーク統計を進展させることに留意されたい。許可制御手順は、新しいフローをサポートするために資源が使用可能であるかどうかを判断する。図１４に描かれているような資源の測度はステップ３０５で更新される。新しいフローが判断菱形３０６で許可された場合に、処理は適応スケジューリングプロセスの適用のためにステップ３０７に続行する。
【０１６２】
ステップ３０４の許可制御手順は図１８Ｂにさらに詳説される。判断菱形３０８で、フローｆkについての要求レートがフローｆkについての平均ＤＲＣデータ要求より大きい場合、処理はステップ３１２に続行してフローｆkのエントリを拒絶する。さもなければ、処理は、判断菱形３１０に戻ってｆkについての要求レートが時刻ｔでの使用可能な資源Ａｖａｉｌを上回っているかどうかを判断する。要求レートがＡｖａｉｌ未満である場合には、フローはステップ３１４で許可される。さもなければ、フローはステップ３１２で拒絶される。
【０１６３】
ステップ３０５の資源の測度の更新は、図１８Ｃにさらに詳説される。ステップ３２０では、資源の測度Ａｖａｉｌ及びＲｅｓが更新される。ＱｏＳ統計はステップ３２２で更新され、監視される。ＡＳＦはステップ３２０と３２２の結果に基づいてステップ３２４で更新される。推定された資源レベルＬはステップ３２６で計算し直される。新しいフローがステップ３２８で要求されると、処理は図１８Ａのステップ３０４で処理のために戻る。新しいフローがステップ３２８で要求されない場合には、セクタ内のユーザの存在がステップ３３０でユーザごとに決定される。ステップ３３２では、サンプル持続期間が決定される。
【０１６４】
図１８Ｄに続行して、ＱＳＧパラメータがフローごとに選択される。２つの平行な処理経路が考慮される。第１の経路はレートサンプル間隔でステップ３４２でレート違反を処理する。レートサンプル間隔はステップ３３２で計算されるサンプル持続期間を上回っていることに留意されたい。第２の経路はアクティブフローの処理を詳説する。あるフローに関して、プロセスはステップ３４４でサンプル持続期間中における遅延違反を有するＩＰパケットの割合を求める。ステップ３４６では、サンプル持続期間中におけるジッタ違反のあるＩＰパケットの割合が検討中のフローについて計算される。サンプル持続期間中にフローによって使用されるスロットの割合がステップ３４８で計算される。ステップ３５０では、プロセスはサンプル持続期間中にＱｏＳ要件を有するフローに与えられるスロットの割合を決定する。ステップ３５２では、プロセスはＱｏＳ違反がないかチェックし、ステップ３５４でＱｏＳグループＩＤを決定する。
【０１６５】
処理は、図１８Ｅに続行し、ここでステップ３６０がＱｏＳグループごとにフロー数を計算する。ステップ３６２では、プロセスは各ＱｏＳ統計に対応するＱｏＳフローの割合を計算する。ステップ３６０と３６２の結果は、ステップ３６４での所定閾値と比較される。閾値が演算中動的に更新され得ることに留意されたい。ステップ３６６ではＡＳＦは相応して調整される。
【０１６６】
図１８Ａから図１８Ｅは許可制御方法の一実施形態を示す。許可制御方法のさらなる詳細が以下に後述される。ＢＴＳなどのＡＮ要素は、フローごとのセクタ単位の統計を収集し、セクタ単位の許可制御及び先処理アルゴリズムのためにこの情報を使用する。セクタ単位の統計は、そのフローに対応するユーザがそのセクタ内にいる持続期間の間だけ収集される。ＢＴＳはＱｏＳ統計及びネットワーク関連統計を周期的に収集する。Ｔを、これらが収集された後の時間期間とする。Ｚはサンプル指数ｔ＝Ｚ＊Ｔである。
【０１６７】
セクタｓのフローｆkを考慮する。ｕ（ｆk）はフローｆkに対応するユーザである。ユーザは時刻ｔenterでセクタｓに入る。資源がセクタｓ内の持続期間［ｔreserve（ｆk，ｓ），ｔfree（ｆk，ｓ）］の間、このフローのために予約される。ここで、資源は時刻ｔreserveに予約される。ユーザがアプリケーションサービスを要求した時点で資源が予約される。ユーザｕ（ｆk）はｔenter,j（ｆk，ｓ）に持続期間内でｊ回目のセクタｓへの進入を行い、ｔleave,j（ｆk，ｓ）にｊ回目の退出を行う。したがって、ｔreserve（ｆk，ｓ）≦ｔenter,first（ｆk，ｓ）及びｔfree（ｆk，ｓ）≧ｔleave,last（ｆｋ，ｓ）となる。ＡＮが、ユーザが将来のなんらかの時点でこのセクタに移動する可能性があると予想して、ＱｏＳシグナリングプロトコルを介してフローのための資源を予約するように命じられることがあり得ることに留意されたい。ここでは、ｔenter,first（ｆk，ｓ）は、ユーザｕ（ｆk）がこのセクタｓに入る初めてのときであり、ｔleave,last（ｆk，ｓ）は、このユーザがフローｆkが有効な間にセクタｓを退出する最後のときである。
【０１６８】
アルゴリズムは、時刻ｔの時点で以下の条件が満たされる場合にだけ、時刻ｔにおいてＱｏＳ統計およびネットワーク関連性能統計を考慮に入れる。
【数２０】
2010166582.tif 000023
【数２１】
2010166582.tif 000024
【数２２】
2010166582.tif 000025
【０１６９】
ここではδ（ｆk）及びθ（ｆk）はフローｆkについて事前に指定され、ＩＮ＿ＩＰ＿ＰＫＴＳ（ｆk，ｔ，ｓ）は、セクタｓ内の期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）中のＢＴＳ下りリンクスケジューラによる伝送が予定されるフローｆkについての入力ＩＰパケットの数である。ＩＰパケットの最後のビットがセクタｓ内で伝送されると、そのビットはセクタについてのＩＮ＿ＩＰ＿ＰＫＴＳでカウントされる。変数δ（ｆk）は、その後セクタ内での存在が示唆される時間を指す。言い換えると、いったんユーザがδ秒セクタｓの中にいると、プロセスは資源の評価を開始する。いったん許可されると、ユーザは再許可を必要とせずにセクタを退出し、セクタに最進入することができる。
【０１７０】
ＱｏＳ統計及びネットワーク統計は、次に、アプリケーションサービスを要求するフローごとの許可基準を評価するために使用される。期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）でのセクタｓ内のフローｆkに対応する遅延したＩＰパケットの割合は以下のように計算される。
【数２３】
2010166582.tif 000026
【０１７１】
ここで、ＤＥＬＡＹＥＤ＿ＩＰ＿ＰＫＴＳ（ｆk，ｔ，ｓ）は時刻ｔまでにセクタｓについてＢＴＳでのフローｆkの対応する遅延限度を超えて遅延したＩＰパケットの数に相当する。セクタｓでのＩＰパケットについての遅延違反の検出時、そのセクタについての遅延違反のカウントが増分される。時刻ｔまでのフローｆkについてのジッタ限度違反を有するＩＰパケット組の割合は以下のように計算される。
【数２４】
2010166582.tif 000027
【０１７２】
ここで、ＪＴＲ＿ＶＩＯＬ＿ＰＫＴ＿ＰＡＩＲＳ（ｆk，ｔ）は、フローｆkについての、スロットｔによるジッタ限度違反のある（連続ＩＰパケットの）ＩＰパケット組の数に相当する。これは、あるセクタについて、あるフローに関する２個の連続ＩＰパケットがあるセクタで送信されるときにカウントされる。
【０１７３】
期間（ｔenter_latest（ｆk，ｓ））の間のフローｆkのレート違反は
【数２５】
2010166582.tif 000028
【０１７４】
であり、ｒｅｑ＿ｒａｔｅ（ｆk）＞ｓｅｒｖｅｄ＿ｒａｔｅ（ｆk，ｔ，ｓ）である。それ以外の場合、フローｆkに時刻ｔでのレート違反がないときには、期間（ｔenter_latest（ｆk，ｓ），ｔ）の間のセクタｓのフローｆkについてのｓｅｒｖｅｄ＿ｒａｔｅ（ｆk，ｔ，ｓ）が計算される。
【０１７５】
遅延及びジッタの違反の場合には、プロセスは期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）としてサンプル持続期間を適用するが、レート違反の場合、プロセスは期間（ｔenter_latest（ｆk，ｓ），ｔ）としてサンプル持続期間を適用することに留意されたい。
【０１７６】
期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）の間にフローｆkによって使用されるスロットの割合は、以下のように計算される。
【数２６】
2010166582.tif 000029
【０１７７】
ここで、ＳＥＲＶＥＤ＿ＳＬＯＴＳ（ｆk，ｔ，ｓ）は、フローｆkが（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）によって定義される期間中サービスを受けたスロット数であり、ＩＮ＿ＳＥＣＴＯＲ（ｆk，ｔ，ｓ）は期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）の間のスロットの総数である。期間（ｔ−Ｔ，ｔ）の間にセクタｓでＱｏＳ要件を有するフローに与えられるスロットの割合は、
【数２７】
2010166582.tif 000030
【０１７８】
のように示される。
【０１７９】
動的フロー分類
フローｆkごとに、以下の４つの閾値が事前に指定され、フロー単位のＱｏＳチェック及びチャネル状態関連チェックを実行するために使用される。
【０１８０】
Ｆｒａｃ＿ｄｅｌａｙｅｄ＿ＩＰ＿ｐｋｔｓ＿ｔｈｒｅｓ（ｆk）、
Ｆｒａｃ＿ｊｉｔｔｅｒ＿ｖｉｏｌ＿ＩＰ＿ｐｋｔｓ＿ｔｈｒｅｓ（ｆk）、
ｒａｔｅ＿ｖｉｏｌ＿ｔｈｒｅｓ（ｆk）、及び
Ｆｒａｃ＿ｓｌｏｔｓ＿ｖｉｏｌ＿ｔｈｒｅｓ（ｆk）
システムは期間Ｔの後ごとに周期的にＡＳＦを適応させる。Ｔは事前に指定された値である。Ｚ回目の適応チェックが実行されるある時刻ｔ（つまり、ｔ＝Ｚ＊Ｔ）で、プロセスはセクタｓで予約されたいくつかの資源を有するフロー、つまりｔreserve（ｆk，ｓ）≦ｔ≦ｔfree（ｆk，ｓ）であるそれらのフローを検討する。このフローの組からのフローｆkごとに、以下の「フロー単位閾値チェック」を評価するためにチェックが行われる。
【数２８】
2010166582.tif 000031
【数２９】
2010166582.tif 000032
【数３０】
2010166582.tif 000033
【数３１】
2010166582.tif 000034
【０１８１】
前記４つのチェックは、以下の２つの条件が満たされる場合にフローｆｋについて実行される。
【数３２】
2010166582.tif 000035
【数３３】
2010166582.tif 000036
【０１８２】
条件（３２）、（３３）の少なくとも１つがあるフローについて満たされないが、ｔｒｅｓｅｒｖｅ（ｆｋ，ｓ）≦ｔ≦ｔｆｒｅｅ（ｆｋ，ｓ）が真であるときには、このフローについての閾値チェックの結果がそのフローについてＮＡであると記される。
【０１８３】
プロセスはＱｏＳ、サンプル持続期間中、要件を有するフローについて使用されるスロットの割合を計算し、この割合の値についての閾値も計算する。Frac_slots_thres_quos_flows（ｓ）はセクタｓの期間ＴでＱｏＳ要件を有するフローに割り当てられるスロットの割合に対する上限閾値である。Frac_slots_thres_quos_flows（ｓ）の値は、
【数３４】
2010166582.tif 000037
【０１８４】
かどうかをチェックするために使用される。
【０１８５】
プロセスは、現在のフローを以下のＱｏＳスケジューリンググループ（ＱＳＧ）の１つに分類する。
【０１８６】
ＱＳＧ  ＩまたはＱ＿ＤＪＲ：遅延要件、ジッタ要件、及びレート要件を有するフロー
ＱＳＧ  ＩＩまたはＱ＿ＲａｖｇＤ：レート要件及び平均遅延要件を有するフロー
ＱＳＧ  ＩＩＩまたはＱ＿Ｒ：レート要件を有するフロー
Ｑ＿ＤＪＲクラスに属するフローの組を考えてみる。所与のフローｆｋがＮＡカテゴリの資格を有しておらず、
【数３５】
2010166582.tif 000038
【０１８７】
または
【数３６】
2010166582.tif 000039
【０１８８】
のどちらかを有する場合、このフローはdelay_or_jitter_viol（ｆk，ｔ，ｓ）＝Ｙを有するとして指定される。それ以外の場合、プロセスはこのフローについてdelay_or_jitter_viol（ｆk，ｔ，ｓ）＝Ｎを設定する。他方、このフローがＮＡの資格を有している場合、delay_or_jitter_viol（ｆk，ｔ，ｓ）＝ＮＡである。
【表２】
2010166582.tif 000040
【０１８９】
ＡＳ（ｔ）の適応チェックが実行される時刻ｔのたびに、プロセスはＱｏＳフロー、つまりＱｏＳ要件を有するフローを表２に示すように分類する。各フローはＱｏＳ  Ｓｔａｔ  ＧｒｏｕｐＩＤ（ＱＳ＿ＧＩＤ）を割り当てられる。
【０１９０】
ＱＳ＿ＧＩＤ＝１：レート及び遅延（またはジッタ）違反を有するＱ＿ＤＪＲクラスのフロー
ＱＳ＿ＧＩＤ＝２：レート違反のない遅延（またはジッタ）違反を有するＱ＿ＤＪＲクラスのフロー
ＱＳ＿ＧＩＤ＝３：遅延及びジッタ違反はないが、レート違反を有するＱ＿ＤＪＲクラスのフロー。このケースは適応アプリケーションについて発生する可能性がある。また、レート違反を有するＱ＿Ｒクラス及びＱ＿ＲａｖｇＤクラスに対応するフローがこのグループに割り当てられる。
【０１９１】
ＱＳ＿ＧＩＤ＝４：ＱｏＳ（レート、遅延、及びジッタ）違反がないフロー。ＮＡカテゴリ内のフローも、前述されたように、このグループに入れられる。
【０１９２】
加入係数の適応
Ｎk（ｔ，ｓ）を時刻ｔでのQSG kに対応するフローの数とし、Ｎ（ｔ，ｓ）を時刻ｔでの、セクタｓにおいていくつかの資源を予約されているフローの総数とする。
【数３７】
2010166582.tif 000041
【０１９３】
Ｍに、ＱｏＳ  ｓｔａｔグループｉｄ（ＱＳ＿ＧＩＤ）を示させ、その結果、
【数３８】
2010166582.tif 000042
【数３９】
2010166582.tif 000043
【数４０】
2010166582.tif 000044
【０１９４】
が生じる。
【０１９５】
（セクタｓ内の）時刻ｔにおけるＱｏＳ  ｓｔａｔグループＭにおける、フローｋのＱＳＧに対応するフローの割合、ＱＳＧ  ｋは、以下のように与えられる。
【数４１】
2010166582.tif 000045
【０１９６】
時刻ｔにおける、遅延（またはジッタ）及びレート違反のあるフローの割合は以下のように示される。
【数４２】
2010166582.tif 000046
【０１９７】
時刻ｔにおける、遅延（またはジッタ）違反はあるが、レート違反はないフローの割合は以下のように示される。
【数４３】
2010166582.tif 000047
【０１９８】
時刻ｔにおける、レート違反だけのあるフローの割合は以下のように示される。
【数４４】
2010166582.tif 000048
【０１９９】
ＱｏＳ違反の無い（またはＮＡカテゴリに入る）フローの割合は以下のように示される。
【数４５】
2010166582.tif 000049
【０２００】
Ｓ（ｔ）の適応は、事前に指定される期間Ｔの後に周期的に行われる。適応を行うために、上記グループは以下のように考えられてよい。
【表３】
2010166582.tif 000050
【０２０１】
以下の閾値は事前に指定され、以下に示される適応方法で使用される。
【０２０２】
Frac_flows_thres_DJR：遅延（またはジッタ）及びレート違反のあるフローの割合に対する閾値
Frac_flows_thres_DJ：遅延（またはジッタ）違反はあるが、レート違反はないフローの割合に対する閾値
Frac_flows_thres_R：レート違反がある（遅延違反またはジッタ違反はない）フローの割合に対する閾値
Frac_flows_thres_ok_qos：ＱｏＳ違反がないフローの割合に対する閾値
プロセスは、適応チェックがＡＳ（ｔ）について実行されるそれぞれの瞬間に以下の順序で続行する。
【０２０３】
ステップ１：Frac_flows_DJR_viol（ｔ，ｓ）≧Frac_flows_thres_DJRの場合：
ＡＳ（ｔ＋）＝ｆqos＊ＡＳ（ｔ）＋ｘqos、その結果ＡＳ（ｔ＋）≧ＡＳ（ｔ）である。ここでは、ｆqosとｘqosは事前に指定される。それ以外の場合。
【０２０４】
ステップ２：Frac_flows_DJ_viol(t,s)≧Frac_flows_thres_DJの場合：
ＡＳ（ｔ＋）＝ｆdelay_jitter＊ＡＳ（ｔ）＋ｘdelay_jitter、その結果ＡＳ（ｔ＋）≧ＡＳ（ｔ）である。ここでは、ｆdelay_jitterとｘdelay_jitterは事前に指定される。それ以外の場合、
ステップ３：Frac_flows_R_only_viol（ｔ，ｓ）≧Frac_flows_thres_Rの場合、ＡＳ（ｔ＋）＝ｆrate＊ＡＳ（ｔ）＋ｘrate、その結果ＡＳ（ｔ＋）≧ＡＳ（ｔ）である。ここでは、ｆrateとｘrateは事前に指定される。それ以外の場合、
ステップ４：Frac_flows_no_na_viol(t,s)＜Frac_flows_thres_ok_qosの場合、ＡＳ（ｔ＋）＝ｆall_qos_flows＊ＡＳ（ｔ）＋ｘall_qos_flows、その結果ＡＳ（ｔ＋）≧ＡＳ（ｔ）である。ここでは、ｆall_qos_flowsとｘall_qos_flowsは事前に指定される。それ以外の場合、
ステップ５：Frac_flows_no_na_viol（ｔ，ｓ）≧Frac_flows_thres_ok_qosの場合、及びfrac_slots_qos_flows（ｔ，ｓ）＜Frac_thres_slots_qos_flowsの場合：
ＡＳ（ｔ+）＝ｆok＊ＡＳ（ｔ）＋ｘok、その結果ＡＳ（ｔ＋）≧ＡＳ（ｔ）である。ここでは、ｆokとｘokは事前に指定される。それ以外の場合。
【０２０５】
ステップ６：Frac_flows_no_na_viol（ｔ，ｓ）≧Frac_flows_thres_ok_qosの場合、及びfrac_slots_qos_flows（ｔ，ｓ）≧Frac_thres_slots_qos_flowsの場合、ＡＳ（t＋）＝ＡＳ（ｔ）
先処理方式
図１９は、一実施形態による先処理方法４００を描いている。方法４００は、ＡＳＦが判断菱形４０２で増加したかどうかを判断することにより開始する。ＡＳＦの増加が検出されると、処理は、ステップ４０４に続行して最も多いレート違反数を有するフローを決定する。言い換えると、ＡＳＦが増加すると、先処理方法４００は先処理のために、それらのフローの特定を開始する。本実施形態では、レート違反のあるフローが先処理のための最善の候補として特定される。別の実施形態では、他のフローに優先順位が付けられてよく、優先順位方式を動的に変更されてよい。
【０２０６】
判断菱形４０６で先処理最大値、ＰMAX（以下に詳説される）に達すると、処理は最も多い遅延違反数を有するフローを先処理ためにステップ４０８に続行する。さもなければ処理は判断菱形４０２に戻る。ステップ４０８でフローを先処理後、処理は最も多い遅延違反数を有するフローが複数あるかどうかを判断するために判断菱形４１０に続行する。複数のフローの場合、処理はステップ４１２に続行して最も多いスロットを使用してフローを先処理する。通常、このフローは低データレートを有するため、ある期間中に最も多いスロットを消費する。次に処理は判断菱形４０２に戻る。
【０２０７】
一実施形態では、先処理方法４００が適用される。この方法において、Ｐ＿ｍａｘは、ある時点で先処理が可能なフローの最大数である。表３に示される２つの先処理グループの条件を満たすフローの部分集合を考える。特に、先処理グループＩは、ＱＳＧ＿ＲまたはＱＳＧ＿ＲａｖｇＤに属するフローから構成され、
【数４６】
2010166582.tif 000051
【０２０８】
及び
【数４７】
2010166582.tif 000052
【０２０９】
を有する。
【０２１０】
先処理グループ２は、Ｑ＿ＤＪＲ  ＱＳＧに属し、
【数４８】
2010166582.tif 000053
【０２１１】
及び
【数４９】
2010166582.tif 000054
【０２１２】
を有するフローから構成される。
【表４】
2010166582.tif 000055
【０２１３】
ステップ１：ＡＳ（ｔ）がある時点で（ＡＳ（ｔ）についての適応方法においてのように）増加すると、プロセスは、１つ以上のフローが先処理の資格を有するかどうかを確かめるためにチェックする。ＡＳ（ｔ）が増加していないときには、フローは先処理されないことに留意されたい。
【０２１４】
ステップ２：先処理グループ１に対応するフローの部分集合を考える。これらのフローの中から、ｒａｔｅ＿ｖｉｏｌという最高値を有するフローのＰ＿ｍａｘ数を選択する。これに該当するものが複数ある場合には、Ｆｒａｃ＿ｓｌｏｔｓ＿ｆｌｏｗ値がより高いものを先処理する。Ｐ＿ｍａｘフローが先処理されると、レート違反についてこれ以上のフローは先処理されない。
【０２１５】
ステップ３：先処理グループ２に対応するフローの部分集合を考える。これらのフローは遅延要件及びジッタ要件を有し、Ｆｒａｃ＿ｄｅｌａｙｅｄ＿ＩＰ＿Ｐｋｔｓ（ｆｋ，ｔ，ｓ）＞Ｆｒａｃ＿ｄｅｌａｙｅｄ＿ＩＰ＿ｐｋｔｓ＿ｔｈｒｅｓ（ｆｋ）及びＦｒａｃ＿ｓｌｏｔｓ＿ｆｌｏｗ（ｆｋ，ｔ，ｓ）＞ｆｒａｃ＿ｔｈｒｅｓ＿ｓｌｏｔｓ＿ｆｌｏｗ（ｆｋ）を有する。これらのフローの中から、Ｆｒａｃ＿ｄｅｌａｙｅｄ＿ＩＰ＿ｐｋｔｓという最高値を有する、ステップ２で先処理されたフローの数を差し引いたＰ＿ｍａｘを選択する。これに該当するものが複数ある場合には、Ｆｒａｃ＿ｓｌｏｔｓ＿ｆｌｏｗの値がより高いものを先処理する。
【０２１６】
ユーザ間及びユーザ内ＱｏＳ
携帯電話ユーザは複数のフロー、つまり複数のアプリケーションを同時に有することがある。ここに提示されるように、ユーザは以下を指定し得る。
【０２１７】
それが遅延及びジッタに敏感であるかどうかのフロー単位の表示。それが遅延及びジッタに敏感である場合は、遅延限度及びジッタ限度が指定されなければならない。
【０２１８】
各ユーザについての総計ターゲットレート（ＡＴＲ）。これは、下りリンク階層スケジューラがこのユーザに与えることを目指すであろうターゲットレートである。
【０２１９】
許可制御
時刻ｔにおける、Ｒ（ｔ）ユーザをＵ1，Ｕ2，．．．，ＵR(t)として示すとして、時刻ｔにおけるユーザＵｊのフロー数をｎｕｍ＿ｆｌｏｗｓ（Ｕj，ｔ）とする。ユーザＵｊが、時刻ｔで許可されている（ｋ−１）のフロー、つまりｎｕｍ＿ｆｌｏｗｓ（Ｕj，ｔ）＝ｋ−１であると仮定する。時刻ｔにおいてユーザＵｊについての新しいフローｆk,jを許可すると決定するために、プロセスはユーザＵｊについて観察されたＤＲＣを使用して以下をチェックする。
【数５０】
2010166582.tif 000056
【０２２０】
前述されたようにＡＳＦの適応を実行する間、フローにより用いられているスロット数及びその対応するＤＲＣも考慮に入れられる。プロセスはＡＳ（ｔ）を計算し、Ａｖａｉｌ（ｔ）を以下のように計算する。
【数５１】
2010166582.tif 000057
【０２２１】
プロセスは、
【数５２】
2010166582.tif 000058
【０２２２】
の場合、時刻ｔにおいてフローｆk,jを許可する。
【０２２３】
このフローが許可されると、更新は以下のとおりである。
【数５３】
2010166582.tif 000059
【数５４】
2010166582.tif 000060
【数５５】
2010166582.tif 000061
【０２２４】
プロセスは、すべての許可されたフロー及びユーザについてＱｏＳ統計の監視及びネットワーク関連統計の監視を続行する。加入係数の適応を続行するためにこれらを使用する。次に、ＡＳＦ、ＡＳ（ｔ）が計算され、利用される。
【０２２５】
階層スケジューラ
フロー単位及びユーザ単位の補償：
遅延及びジッタに敏感なフローのそれぞれには、ジッタ閾値が割り当てられる。ユーザＵkに関する、遅延及びジッタに敏感なフローｆｘごとに、プロセスは対応する遅延及びジッタ補償Φを計算する。フローが待ち行列内において遅延閾値を越えたパケットを有さない場合には、
【数５６】
2010166582.tif 000062
【０２２６】
となる。それ以外の場合、
【数５７】
2010166582.tif 000063
【０２２７】
を計算する。ここでは、
【数５８】
2010166582.tif 000064
【０２２８】
ユーザＵkについてのフローｆｘごとに、
ｎｄｅｆｐｋｔｓmin（ｎ）＝最小のｎｄｅｆｐｋｔｓ                        （59）
である。スロットｎでの（すべてのユーザ全体での）すべてのフローを考慮すると、
ｄｅｆｐｋｔｓ（ｆｘ（Ｕｋ，ｎ））＝スロットｎでそれらの遅延閾値に違反したユーザＵｋのフローｆｘの未決ＭＡＣパケットの数                                （60）
である。
【０２２９】
スロットｎでのユーザＵkのレート補償の場合、以下を定義する。
【数５９】
2010166582.tif 000065
【０２３０】
ここでは、
ＡＳＲ（Ｕk，ｎprev（ｎ））＝スロットｎprevの中のユーザＵkの総計供給レート  （62）
であり、
【数６０】
2010166582.tif 000066
【０２３１】
である。スロット数ｎprevは、スケジューリングアルゴリズムを目的としてレートが監視されたときのｎまたはｎより前の最後のスロットである。
【０２３２】
プロセスは任意のスロットｎにおけるユーザＵｋについての総計遅延補償を定義する。遅延要件を有するこのユーザのすべてのフローを考慮し、これらの遅延に敏感なフローのそれぞれについて行頭（ＨＯＬ）ＭＡＣパケットを観察する。その遅延閾値より長い期間システムに亘って（ＨＯＬ）ＭＡＣパケットが全くない場合には、
【数６１】
2010166582.tif 000067
【０２３３】
さもなければ、遅延閾値より長い期間に亘ってシステム内にＨＯＬパケットを有するこのユーザについてのフローの部分集合を考慮する。このユーザの場合、これらのフローの遅延閾値より大きい期間に亘ってシステム内にＨＯＬ  ＭＡＣパケットを有するユーザＵkについてのすべてのフローについて以下を計算する。
【数６２】
2010166582.tif 000068
【０２３４】
ここでは、ｗ（ｆｘ（Ｕk））はユーザＵkのフローｆｘに割り当てられる初期重みである。
【０２３５】
適応重み計算
このユーザについての適応重みを計算するため、プロセスは、遅延に敏感な少なくとも１つのフローを有するユーザそれぞれについて各スロットで遅延閾値違反チェックを行う。プロセスは、このようなユーザＵkのそれぞれについて以下を計算する。
【数６３】
2010166582.tif 000069
【０２３６】
ａｇｇ＿ｄｅｌａｙ＿ｃｏｍｐ（Ｕｋ，ｎ）＞１の場合、プロセスはユーザＵkについて以下のように適応重みを計算する。
【数６４】
2010166582.tif 000070
【０２３７】
一方、ａｇｇ＿ｄｅｌａｙ＿ｃｏｍｐ（Ｕk，ｎ）＝１の場合、プロセスは以下を計算する。
【数６５】
2010166582.tif 000071
【０２３８】
ここでｎprev,k（ｎ）は、ＡＳＲ（Ｕk，ｎprev（ｎ））が監視された（および、このようにＵk，ｎprev（ｎ））が計算された）ときのｎまたはｎより前の最後のスロットである。プロセスはこのユーザについて最終の適応重みの計算を、以下のように続ける。
【数６６】
2010166582.tif 000072
【０２３９】
ここで、ユーザＵkの遅延に敏感なフローについてＲＴｘまたはＤＡＲＱ待ち行列内にパケットがない場合、Ｚ（Ｕk，ｎ）＝１である。さもなければ、Ｚ（Ｕk，ｎ）＝Ｃ（Ｕk）である。ここで、Ｃ（Ｕk）は事前に指定される定数である。
【０２４０】
ユーザ及びフロー選択方法
プロセスがスロットｎでその待ち行列内に少なくとも１つのパケットを有するユーザごとに以下のメトリックを計算する。
【数６７】
2010166582.tif 000073
【０２４１】
ここでは、
【数６８】
2010166582.tif 000074
【０２４２】
はユーザＵk（つまりすべての対応するフローを含む）につての平均サービス供給レートである。プロセスは、Ｙ（Ｕk，ｎ）が最大値のユーザを選択する。いったんユーザがこのようなスケジューラを使用して選択されると、プロセスは、以下の方式に従ってそのユーザにサービス提供するためのフローを選択する。
【０２４３】
以下のグループに分類されるフローを考える。
【０２４４】
グループ１：ＱＳＧ＿ｄｅｌａｙ＿ｊｉｔｔｅｒ。ＶｏＩＰフロー。
【０２４５】
グループ２：ＱＳＧ＿ｄｅｌａｙ＿ｊｉｔｔｅｒ。テレビ会議フロー。
【０２４６】
グループ３：ＱＳＧ＿ｄｅｌａｙ＿ｊｉｔｔｅｒ。ビデオストリーミングフロー。
【０２４７】
グループ４：ＱＳＧ＿ｒａｔｅ＿ａｖｇ＿ｄｅｌａｙ。レート要件及び平均遅延要件のあるフロー。
【０２４８】
グループ５：ＱＳＧ＿ｒａｔｅ。レート要件だけがあるフロー。
【０２４９】
以下のステップが、本明細書において説明されているスケジューリングアルゴリズムを実行する際に、続き得る。
【０２５０】
ステップ１：そのスロット内の選択されたユーザのすべての保留されているフローを検討する。
【０２５１】
ステップ２：そのユーザについての、グループ１とグループ２に対応するフローを検討する。ＨＯＬパケットが自身の遅延閾値を違反し、且つそのフローの遅延限度に最も近いフローを選択する。フローが検出されると、このフローにサービス提供する。それ以外の場合、ステップ３に進む。
【０２５２】
ステップ３：ＨＯＬパケットが遅延閾値を越えたグループ３に対応するフローを検討し、ＨＯＬパケットが遅延限度に最も近いフローを選択する。フローが検出されたら、このフローにサービス提供する。それ以外の場合、次のステップに進む。
【０２５３】
ステップ４：ＨＯＬパケットが遅延閾値を越えたグループ４に対応するフローを検討し、ＨＯＬパケットが遅延限度に最も近いフローを選択する。フローが検出されたら、このフローにサービス提供する。それ以外の場合、次のステップに進む。
【０２５４】
ステップ５：サービス提供する保留フローをグループ１〜４から取り上げる。最も数の小さいグループのフローに優先順位を与える。フローが選択されたら、それにサービス提供する。それ以外の場合、次のステップに進む。
【０２５５】
ステップ６：そのユーザについての、グループ５に対応する保留フローを検討する。ｒｅｑｕｉｒｅｄ＿ｒａｔｅ／ｓｅｒｖｅｄ＿ｒａｔｅの最大値を有するものを選択する。このフローにサービス提供する。何も選択されない場合には、次のステップに進む。
【０２５６】
ステップ７：そのユーザについての、ベストエフォートフローにサービス提供する。複数ある場合には、サービス提供レートの最小値のものを取り上げる。
【０２５７】
図１６は、フロー単位の、及びユーザ単位の補償を行う２レベルスケジューラを描いている。図１６及び図１７に描かれているスケジューラは、ここに説明されているように、ＱｏＳ間、及びＱｏＳ内の補償のために使用される階層スケジューラである。図１６に描かれているように、レベルＩとして特定される第１のレベルは、複数のスケジューリング要素、つまりノードＳ１、Ｓ２、．．．ＳＭを含み、そこでは各ノードが異なるＱＳＧを処理する。この例では、Ｍは処理されるＱＳＧグループの数である。例えば、スケジューリングノードＳ１はボイスオーバＩＰ（ＶｏＩＰ）タイプのアプリケーションフローを処理する。ＶｏＩＰは例として示されているが、ＱＳＧ１として分類される任意のあらゆるアプリケーションフローがＳ１で処理される。このようなフローはＱｏＳ要件を評価するために指定される遅延限度及びジッタ限度を有する。複数のアプリケーションＶｏＩＰタイプのフローがスケジューリング要素Ｓ１で処理される。同様に、各スケジューリング要素は特定のＱＳＧのためのフローを処理する。別の実施形態では、１つのスケジューリング要素に複数のＱＳＧのためのアプリケーションフローが供給されてよいことに留意されたい。複数のスケジューリング要素が同じＱＳＧグループを処理するために使用されてよいことに留意されたい。
【０２５８】
図１６に描かれているスケジューラのレベルＩは、フロー単位の補償の一部を計算する。ユーザあたりの複数のアプリケーションフローが図１６に描かれている。レベルＩＩスケジューリング要素は、フロー単位の補償の計算を仕上げる。
【０２５９】
図１７は、スケジューリングノード、Ｓ１、Ｓ２、．．．Ｓｚを有するスケジューラを描いている。このステップでは、ｚはユーザ数である。ユーザ数が動的であるため、現在のスケジューリングノードの数が動的に変化し得ることに留意されたい。各スケジューリングノードＳ１、Ｓ２、．．．Ｓｚは所与のユーザから複数のフローを受け取るように適応されている。スケジューリングノードＳ１は、ユーザ１（Ｕ１）のためのＦｋを通してフローＦ１を受け取る。ここでｋは、ユーザ１について現在処理されているアプリケーションフローの総数である。図１６のレベルＩとレベルＩＩのスケジューラによってフローごとに計算されるフロー単位の補償を使用して、図１７のレベルＩＩスケジューラはユーザごとに総ユーザ補償を計算する。次に、レベルＩＩスケジューラは、ユーザを選択し、ユーザ選択方法について前述された適応加重ＤＲＣ／Ｔアルゴリズムに従ってスロットでこのユーザにサービス提供する。次にレベルＩＩスケジューラはレベルＩスケジューラから受信される加重値の中から選択する。示されているように、Ｗ（Ｕｋ）はユーザＵｋに割り当てられる初期重みであり、ＡＴＲ（Ｕｋ）はユーザＵｋについての総ターゲットレートである。いったんユーザが選択されると、そのユーザに対応するレベルＩスケジューラは前述されたフロー選択方法に従って、フローを選択してそのスロットでそのユーザにサービス提供する。
【０２６０】
下りリンクスケジューラは、スロット内のあるＤＲＣ値でのサービスのためのフローに対する自発的な（willing）価格を各ユーザが指定できるようにしてよい。いったん価格が指定されると、適応フレーム構造スケジューラは異なるタイプのアプリケーションのＱｏＳ要件を満たすべく動作する。対応するスケジューリング機構によって、サービスプロバイダは利益を高めるという目標と、アプリケーションのＱｏＳ要件を満たすという目標の間の良好な釣り合いを見つけることができる。このようなスケジューリング機構は、エンドユーザに動的コスト制御も提供し、レート要件及び／または平均遅延要件を有するアプリケーション、あるいはストリーミングアプリケーション等のために使用され得る。一実施形態では、各フローが、それがサービス提供されるときにスロットごとの価格を指定する価格決定オプションが提供される。この価格はそのスロット内のフローについてユーザが要求するＤＲＣ値に依存している。価格フローｊ（つまり、ユーザがアクセスするフローｊ）がスロットｍで喜んで支払うｃ［ｊ，ｍ，ＤＲＣ［ｊ，ｍ］として指定される。ここでは、ＤＲＣ［ｊ，ｍ］は、このユーザがスロットｍでサービス提供され得るレートを示す。ユーザは、ＤＲＣの値ごとに事前に指定された価格など、価格を静的に指定してよい。または、ユーザは、例えば、アプリケーションが有効な間に価格を変更する等のために、価格を動的に指定してよい。これにより、ユーザが、変化するチャネル状態に対応し、所望されるＱｏＳを達成するために価格に対してある程度の制御を有することができる。運用者は、ユーザ間及びユーザ内ＱｏＳのために存在しているスケジューラとともにこのようなスケジューラを使用してよい。これにより運用者は少なくとも２つのタイプの価格決定方式を指定できる。ユーザ間及びユーザ内ＱｏＳスケジューラの場合、運用者は、（静的サービス内容合意書に基づいて）静的な価格決定方式を指定してよく、と同時に適応フレーム構造に基づいたスケジューラについての動的価格決定方式が可能となる。ユーザはさまざまなフローのためにさまざまな方式を使用することを選び得る。
【０２６１】
一実施形態では、時間が複数のフレームに分割され、ＤＲＣ値、ＱｏＳ要件、ＱｏＳ違反統計、及び各ユーザによって指定される価格に応じてスロットごとにスケジューリング決定が下される。フレーム構造によって、基本的には、ユーザ待ち行列が１つの周回の間にサービス提供されるべき順序が決定される。ネットワークは、所望される目標を達成するために、スケジューリングの周回のそれぞれにおいて、各周回についてどのフロー／ユーザに、所与のスロットにおいてサービス提供するのかを決定する。フレーム構造、つまり各周回においてフローがサービス提供される順序は、変化しつづけ、ＡＦＳ依拠アルゴリズムと呼ばれる。
【０２６２】
以下の定義は、計算プロセスで使用されるいくつかの表記を説明する。Ｎ個の待ち行列（及びフローごとに１つの待ち行列）を前提として、フローｊについてのＱｏＳ要件はそれがレートｒ［ｊ］でサービス提供される場合に満たされると仮定する。初期重みｗ［ｊ］及びタイムスケールｔｓ［ｊ］も各フローｊに事前に指定される。プロセスは、フローｊにレート保証を与えることを目指す。このプロセスは、タイムスケールの整数倍であるスロットごとに（つまり、ｍを整数としてスロットｍ＊ｔｓ［ｊ］ごとに）監視されてよい。
【０２６３】
ｓｔａｒｔ［ｊ］を、フローｊが１周回のうちでサービス提供対象として最初に検討され始めたときのスロットとする。スロットｚの最後までに、システムはＳ［ｊ，ｚ］＝ｒ［ｊ］＊（ｚ−ｓｔａｒｔ［ｊ］）ビットにサービス提供することを所望する。ここで、なんらかの整数ｍについてｚ＝ｍ＊ｔｓ［ｊ］である。１つのスケジューリング機構を使用し、システムは、あるフローへの割り当てが望まれる（タイム）スロットの数とそのフローにサービス提供することを望まれるビット数の釣り合いをとることができる。
【０２６４】
さらに、ＡＦＳスケジューラのために使用される他のパラメータが以下のように示される。
【０２６５】
ｓｌｏｔｓ＿ａｌｌｏｃ［ｊ，ｎ］：周回ｎの間に待ち行列（フロー）ｊに割り当てられるスロットの数
ｓｌｏｔｓ＿ｓｅｒｖｅｄ［ｊ，ｎ］：待ち行列（フロー）ｊが周回ｎの内にサービス提供されたときのスロット数
Ｓ＿ｒ［ｊ，ｎ］：周回ｎの終了までにフローｆにサービス提供するビット数
ｒｏｕｎｄ＿ｌｅｎ［ｎ］：周回ｎ中のスロット数単位の長さ
ｒｏｕｎｄ＿ｌｅｎ＿ｔｈｒｅｓ：周回の長さはこの閾値により上限を設定される。
【０２６６】
Ｂ［ｎ］：スロットｎの始まりにある保留待ち行列のリスト
Ｒout_round［ｊ，ｎ］：スケジューラによって周回ｎ内で待ち行列ｊのためにサービス提供されるビット数
Ｒｏｕｔ［ｊ，ｎ，ｇ］：ｇ≧ｎの場合に時間間隔［ｎ，ｇ］の間に待ち行列ｊのためにサービス提供されるビット数
前記に与えられた説明を使用すると、周回ｎの始まりでの待ち行列ｊについてのビットの不足は、以下により与えられる。
【数６９】
2010166582.tif 000075
【０２６７】
ビットに不足がある場合、対応するフローはサービスで遅れをとっており、補償されなければならない。他方、フローが受け取る過剰なサービスは明示的にはペナルティを課されないが、サービスで遅れをとっている他のフローは補償されるであろう一方、このフローは補償されないであろうため、間接的にペナルティを課される。
【０２６８】
さらに、周回ｎの始まりでのフローｊについての正規化された不足ビットの計算は以下のように与えられる。
【数７０】
2010166582.tif 000076
【０２６９】
周回ｎの始まりでの待ち行列ｊについてのスロット内の不足は以下のように示される。
【数７１】
2010166582.tif 000077
【０２７０】
プロセスは、周回ｎの始まりでの待ち行列ｊについての正規化された不足スロットを以下のように定義する。
【数７２】
2010166582.tif 000078
【０２７１】
ｌｓｌｏｔ［ｎ］を周回ｎの最後のスロットとし、ｆｓｌｏｔ［ｎ］を周回ｎの最初のスロットとする。ａｗ［ｊ，ｎ］は周回ｎについてフローｊに割り当てられる（適応）重みを示すと仮定する。この重みは周回ｎ内のフローｊに割り当てられるスロット数を決定する。
【０２７２】
ユーザによって要求されるＤＲＣ値に、順列が与えられる。具体的には、ＤＲＣ1［Ｂ，Ｓ］がＤＲＣ2［Ｂ，Ｓ］より優れている場合には、（Ｂ／Ｓ）1＞（Ｂ／Ｓ）2である。ここでは、Ｂはパケット単位のビット数であり、Ｓはスロットの数である。
【０２７３】
ＡＦＳスケジューラのスケジューリング周回ごとに、プロセスは各周回についての前述される状態変数を計算し、次に各周回の始まりにおける各フローの重みを計算して、この周回についてこのフローに一定数のスロットを割り当てる。この目的のため、プロセスは適応重み計算機構を使用し、周回単位のサービス規律を使用して周回ごとにフレーム構造を計算する。
【０２７４】
（適応重み計算機構）
ｎｄｅｆ＿ｂｉｔｓ＿ｒthres,minをｎｄｅｆ＿ｂｉｔｓ＿ｒについての事前に指定される閾値とする。プロセスは、以下に示すように周回ｎの始まりで集合ｎｄｅｆｂｉｔｓ＿ｓｅｔ［ｎ］を定義する。
【数７３】
2010166582.tif 000079
【０２７５】
Ｓ＿Ｉ［ｎ］を周回ｎの始まりでの集合の中のフロー数とする。同様に、ｎｄｅｆ＿ｓｌｏｔｓ＿ｒｔｈｒｅｓ，ｍｉｎはｎｄｅｆ＿ｓｌｏｔｓ＿ｒについての事前に指定される閾値である。プロセスは、周回ｎの始まりでのｎｄｅｆｓｌｏｔｓ＿ｓｅｔ［ｎ］を以下のように定義する。
【数７４】
2010166582.tif 000080
【０２７６】
Ｓ＿ＩＩ［ｎ］を周回ｎの始まりでのこの集合の中のフロー数とする。
【０２７７】
任意のフローｊの場合、周回ｎの始まりで、対応するスロット補償関数を以下のように定義する。
【数７５】
2010166582.tif 000081
【数７６】
2010166582.tif 000082
【０２７８】
ここでは、
【数７７】
2010166582.tif 000083
【数７８】
2010166582.tif 000084
【数７９】
2010166582.tif 000085
【０２７９】
である。
【０２８０】
フローｊごとに、
【数８０】
2010166582.tif 000086
【０２８１】
となるように、２つの閾値、ｓｌｏｔｓ＿ｃｏｍｐ＿Ｉthres,min［ｊ］とｓｌｏｔｓ＿ｃｏｍｐ＿Ｉthres,max［ｊ］を定義する。
【０２８２】
本明細書に説明されている適応重み計算とともにこれらの閾値を使用することにより、あらゆるフローが周回ｎ内に不公平に多数のスロットを消費することが防止され、同時に指定限度を超えてそのフローにペナルティは課されない。
【数８１】
2010166582.tif 000087
【数８２】
2010166582.tif 000088
【０２８３】
フローｊごとに、
【数８３】
2010166582.tif 000089
【０２８４】
となるように、２つの閾値ｓｌｏｔｓ＿ｃｏｍｐ＿ＩＩthres,min［ｊ］とｓｌｏｔｓ＿ｃｏｍｐ＿ＩＩthres,max［ｊ］を定義する。
【０２８５】
各周回の始まりで、フローは表５に示されるように４つのグループに分けられる。
【表５】
2010166582.tif 000090
【０２８６】
任意の周回ｎの始まりで、グループＩＩまたはグループＩＶのどちらかに属するフローｊに対して、ｓｌｏｔ＿ｃｏｍｐ［ｊ，ｎ］＝１を使用する。周回ｎの始まりでグループＩに属するフローｊに対して、以下を適用する。
【数８４】
2010166582.tif 000091
【０２８７】
フローｊが周回ｎの始まりでグループＩＩＩに属する場合は、以下を適用する。
【数８５】
2010166582.tif 000092
【０２８８】
次に、プロセスはフローｊについての適応重みを計算し、そこでは周回ｎの空ではない待ち行列についての適応重みは以下のとおりである。
【数８６】
2010166582.tif 000093
【０２８９】
ここでは、
【数８７】
2010166582.tif 000094
【０２９０】
である。各フローｊについて、閾値ａｗｔｈｒｅｓ，ｍａｘ［ｊ］を定義し、以下を確実にするようこの閾値を使用する。
【数８８】
2010166582.tif 000095
【０２９１】
次に、これらの適応重みが利用されて、各フローに割り当てられるであろうスロットの数、及び各周回が
【数８９】
2010166582.tif 000096
【数９０】
2010166582.tif 000097
【０２９２】
となるように計算される。
【０２９３】
期間単位のスケジューリング規律
いったん各フローが割り当てられていれば、周回内のスロットの幾つか及び周回の長さは計算され終わっている。次のステップは、所与のスロットにサービス提供するためのフローを選択することである。周回ｎ内の所与の任意のスロットｍでは、直前のスロットの１つの中で選択されたパケットが依然としてサービス提供されている場合、サービス提供されなければならない新しいフローが選択される必要はない。他方、周回ｎ内のこのスロットｍ内でパケットがサービス提供されていない場合、サービス提供するためのフローは以下のように選択される。フローｊについて周回ｎのスロットｍについての以下の選択メトリックを、スケジューラがサービス提供するための新しいフローを選択する必要がある各スロットｍについて、及び
【数９１】
2010166582.tif 000098
【０２９４】
及び
【数９２】
2010166582.tif 000099
【０２９５】
となる各フローｊについて、
【数９３】
2010166582.tif 000100
【０２９６】
を計算する。ここでは、θ（ｊ）はフローｊごとに事前に指定され、ｗａｉｔ＿ｃｏｍｐはフローの遅延限度を改善するためにフローに与えられる待機補償である。ｗａｉｔ［ｊ，ｎ，ｍ］を周回ｎ内のスロットｍの始まりでのフローｊについての行頭パケットの待機時間とする。
【数９４】
2010166582.tif 000101
【０２９７】
また、フローｊは周回ｎ内のスロットｍの始まりで少なくとも１つの未決パケットを有する。次に、ｋ∈Ｂ［ｎ］であり、このようなフローの数がｗａｉｔ＿ｎｕｍ［ｎ，ｍ］となるようにすべてのフローｋについて、
【数９５】
2010166582.tif 000102
【０２９８】
を計算する。フローｊごとに、２つの閾値ｗａｉｔ＿ｃｏｍｐthres,min［ｊ］とｗａｉｔ＿ｃｏｍｐthres,max［ｊ］が、割り当てられ、
【数９６】
2010166582.tif 000103
【０２９９】
を確実にするために使用される。選択メトリックＹＹの値が最大のフローが選択されてこのＡＦＳスケジューラによって任意の所与のスロットでサービス提供される。
【０３００】
一実施形態によるＡＮ要素が図２０に描かれている。ＡＮ要素５００はアプリケーションフローデータを受け取り、ユーザへの伝送のためにこのデータを処理する。ＡＮ要素５００は複数の、それぞれがＱｏＳ要件を有するアプリケーションフローをスケジュールする。アプリケーションフローが、前述されたようにベストエフォートフローを含み得ることに留意されたい。ＡＮ要素５００は、トラヒックプロファイル、及び前記フローと関連付けられるＱｏＳプロファイルを特定し且つ前記フローをクラス、つまりＱＳＧに割り振るように適応されたフロー分類装置５０２を含む。フロー分類装置５０２はスケジューラ５０４、許可制御装置５１０、及びＱｏＳモニタ５０６に結合される。スケジューラ５０４は、比例公平（ＰＦ）アルゴリズム及び適応加重ＰＦアルゴリズム（これらに限定されない）を含む種々のスケジューリングアルゴリズムのどれかを実施してよい。許可制御装置５１０はＡＮ５００によって受け取られるアプリケーションフローに許可制御機構を適用する。許可制御装置５１０は、要求された各新規フローをＱｏＳ統計及びネットワーク統計に基づいて評価し、前記新規フローをサポートするために十分な資源が使用可能であるかどうかを判断する。適応装置は許可制御装置に結合され、そこではＡＳＦが更新される。適応装置５１２は現在アクティブなアプリケーションフローの先処理決定を実行するように適応されている。先処理は、データレート、使用されるスロット、及び他のＱｏＳ統計とネットワーク統計に関して所与のフローの性能を検討する。ＱｏＳモニタは受信されたアプリケーションフローのＱｏＳ要件を監視するように適応されている。ＡＮ要素５００は通常複数のフローを受け取り、ユーザへの伝送のためにそれらの中から選択することに留意されたい。スケジューラ５０４は、許可制御装置５１０から新規フローが許可されるかどうかに関する情報を受け取る。スケジューラ５０４はＱｏＳ統計及び他の情報をＱｏＳモニタ５０６から受け取り、そこでスケジューラ５０４はＱｏＳ情報を利用して伝送のためのフローを選択する。
【０３０１】
本明細書で提示されているのは、無線通信システムにおけるアプリケーションフローの許可制御、先処理、及びスケジューリングのための方法及び装置である。許可制御において、新しいフローの所要データレートが考慮され、これが使用可能な資源と比較される。いったん許可されると、フローは、スケジューラに提供される。スケジューラは、各スロットあるいは指定された期間での伝送のためにユーザを選択するためにフロー単位及びユーザ単位の分析を実行するように適応されている。
【０３０２】
当業者は、情報及び信号が種々の異なる技術及び技法のどれかを使用して表されてよいことを理解するであろう。例えば、前記説明を通して参照されて得るデータ、指示、コマンド、情報、信号、ビット、記号、及びチップは、電圧、電流、電磁波、磁場または磁性粒子、光学場または光学粒子、あるいはその任意の組み合わせで表され得る。
【０３０３】
当業者は、本明細書に開示されている実施形態に関連して説明される多様な例示的な論理ブロック、モジュール、回路、及びアルゴリズムステップが電子ハードウェア、コンピュータソフトウェア、または両方の組み合わせとして実現され得ることをさらに理解するであろう。ハードウェアとソフトウェアの互換性を明らかに示すために、多様な例示的な構成要素、ブロック、モジュール、回路、及びステップがその機能性という点で概して前述されている。このような機能性がハードウェアとして実現されるのか、あるいはソフトウェアとして実現されるのかは、システム全体に課される特定のアプリケーション及び設計制約に依存している。当業者は特定のアプリケーションごとにさまざまな方法で説明された機能性を実現してよいが、このような実現の決定は本発明の範囲からの逸脱を引き起こすとして解釈されるべきではない。
【０３０４】
本明細書に開示されている実施形態との関連において説明される多様な例示的な論理ブロック、モジュール、及び回路は、汎用プロセッサ、ディジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）または他のプログラマブルロジックデバイス、ディスクリートゲート、またはトランジスタロジック、ディスクリートハードウェア構成要素、あるいは本明細書に説明されている機能を実行するために設計されるその任意の組み合わせで実現または実行されてよい。汎用プロセッサはマイクロプロセッサであってよいが、或いはプロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラまたは状態機械であってよい。プロセッサは、例えばＤＳＰとマイクロプロセッサの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアととともに用いられる１台または複数台のマイクロプロセッサ、あるいは任意の他のこのような構成などのコンピューティング装置の組み合わせとして実現されてもよい。
【０３０５】
本明細書に開示されている実施形態との関連において説明される方法、アルゴリズムのステップはハードウェアで、プロセッサによって実行されるソフトウェアモジュールで、あるいはこれら２つの組み合わせで実現されてよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、あるいは既知の他の形式の記憶媒体に常駐してよい。例示的な記憶媒体は、プロセッサが情報を記憶媒体から読み取り、情報を記憶媒体に書き込むことができるようにプロセッサに結合される。または、記憶媒体はプロセッサに一体化されてよい。プロセッサ及び記憶媒体はＡＳＩＣに常駐してよい。ＡＳＩＣはユーザ端末に常駐してよい。または、プロセッサ及び記憶媒体はユーザ端末内のディスクリート構成要素として常駐してよい。
【０３０６】
開示された実施形態の説明は、当業者が本発明を製造または使用できるようにするために提供される。これらの実施形態に対する多様な変型は当業者に容易に明らかとなり、本明細書に定められる包括的な原則は本発明の思想または範囲から逸脱することなく他の実施形態に適用されてよい。したがって、本発明は、本明細書に示されている実施形態に制限されることを目的としないが、ここに開示されている原則及び新規特徴と一致した最も広い範囲を与えられるべきである。
【図１】
2010166582.tif 000104
【図２Ａ】
2010166582.tif 000105
【図２Ｂ】
2010166582.tif 000106
【図３】
2010166582.tif 000107
【図４】
2010166582.tif 000108
【図５】
2010166582.tif 000109
【図６】
2010166582.tif 000110
【図７Ａ】
2010166582.tif 000111
【図７Ｂ】
2010166582.tif 000112
【図８】
2010166582.tif 000113
【図９】
2010166582.tif 000114
【図１０】
2010166582.tif 000115
【図１１】
2010166582.tif 000116
【図１２Ａ】
2010166582.tif 000117
【図１２Ｂ】
2010166582.tif 000118
【図１２Ｃ】
2010166582.tif 000119
【図１２Ｄ】
2010166582.tif 000120
【図１２Ｅ】
2010166582.tif 000121
【図１３】
2010166582.tif 000122
【図１４】
2010166582.tif 000123
【図１５】
2010166582.tif 000124
【図１６】
2010166582.tif 000125
【図１７】
2010166582.tif 000126
【図１８Ａ】
2010166582.tif 000127
【図１８Ｂ】
2010166582.tif 000128
【図１８Ｃ】
2010166582.tif 000129
【図１８Ｄ】
2010166582.tif 000130
【図１８Ｅ】
2010166582.tif 000131
【図１９】
2010166582.tif 000132
【図２０】
2010166582.tif 000133
【手続補正書】
【提出日】平成22年3月19日(2010.3.19)
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
【図１】本発明の実施形態による通信網を示す。
【図２Ａ】本発明の実施形態に従って構成された基地局コントローラ及び基地局装置のブロック図を示す。
【図２Ｂ】本発明の実施形態に従って構成された遠隔局装置のブロック図を示す。
【図３】図２Ａに示されるチャネルスケジューラの実施形態におけるスケジューリングアルゴリズムの実行を描く流れ図を示す。
【図４】各アプリケーション通信がアプリケーションフローにより表される、マルチメディアアプリケーションをサポートする通信システムである。
【図５】アプリケーションフローの待ち行列である。
【図６】アプリケーションフローの一部の信号タイミングを描くタイミング図である。
【図７Ａ】アプリケーションフローのジッタ測定を描くタイミング図である。
【図７Ｂ】アプリケーションフローを処理するためのタイムスロットの期間での連続するＩＰパケットの伝送を描くタイミング図である。
【図８】通信システム内のアプリケーションフローのスケジューリングを描く流れ図である。
【図９】さまざまなサービスの質（ＱｏＳ）要件を有するアプリケーションフローのスケジューリングを描く流れ図である。
【図１０】一実施形態によるスケジューリングアルゴリズムと一致した各アプリケーションフローの定義を描くアーキテクチャ図である。
【図１１】一実施形態に従ったクラスタイプを識別する表である。
【図１２Ａ】アプリケーションフローの初期化を含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１２Ｂ】クラスタイプの関数としてアプリケーションフローを処理することを含む、一実施形態によるスケジューリングアルゴリズムの一部を示す。
【図１２Ｃ】モードＩアプリケーションフローの処理、モードＩＩアプリケーションフローの処理、及びモードＩＩＩアプリケーションフローの処理を含む、一実施形態によるスケジューリングアルゴリズムの一部を示す。
【図１２Ｄ】モードＩアプリケーションフローの処理を含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１２Ｅ】適応加重及びそれに基づいたスケジューリングを含む、一実施形態によるスケジューリングアルゴリズムの一部を描く。
【図１３】無線通信システムにおいて適応加重アルゴリズムを使用してアプリケーションフローをスケジュールするためのアルゴリズムを実現するための基地局トランシーバシステム（ＢＴＳ）を描く。
【図１４】時間の関数としてデータレート（ＬＭＡＸ）、予約済み資源（Ｒｅｓ（ｔ））、及び使用可能な資源（Ａｖａｉｌ（ｔ））などの割り当てのための最大資源を描くタイミング図である。
【図１５】高速パケットデータタイプシステム内でユーザから受信されるデータ要求、及び時刻ｔで予約するための時間の関数としての推測容量Ｌ（ｔ）を描くタイミング図である。
【図１６】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステムのためのスケジューラを描く情報流れ図であり、フローはフロー単位補償のアプリケーションによりスケジュールされる。
【図１７】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステムのためのスケジューラを示す情報流れ図であり、フローは総計補償のアプリケーションによりスケジュールされる。
【図１８Ａ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｂ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｃ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｄ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１８Ｅ】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での許可制御のためのアルゴリズムを描く。
【図１９】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内での先処理のためのアルゴリズムを描く。
【図２０】サービスの質（ＱｏＳ）要件を有する複数のアプリケーションフローをサポートする高速パケットデータタイプシステム内でのアクセスネットワーク（ＡＮ）要素のブロック図である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
図を参照すると、図１は例示的な可変速度通信システムを表す。１つのこのようなシステムはクアルコム社（Qualcomm, Inc.）に譲渡され、参照することにより本明細書に組み込まれる、2003年6月3日に発行された「高速パケットデータ伝送のための方法及び装置（Method and Apparatus for High Rate Packet Data Transmission）」と題される米国特許番号第6,574,211に説明されている。可変速度通信システムは複数のセル２Ａから２Ｇを備える。各セル２は、対応する基地局４によりサービスを提供される。多様な遠隔局６が通信システム全体に分散されている。例示的な実施形態では、遠隔局６のそれぞれは任意のデータ伝送間隔で下りリンク（forward link）で多くても１つの基地局４と通信する。例えば、タイムスロットｎで、基地局４Ａはデータを遠隔局６Ａだけに送信し、基地局４Ｂは遠隔局６Ｂだけにデータを送信し、基地局４Ｃは下りリンクで遠隔局６Ｃだけにデータを送信する。図１に図示されるように、各基地局４はどの時点でも１つの遠隔局６にデータを送信するのが好ましい。他の実施形態では、基地局４は、基地局４に関連付けられる他のすべての遠隔局６を除いてある特定のデータ伝送間隔で２以上の遠隔局６と通信してよい。さらに、データレートは可変であり、一実施形態では受信側遠隔局６によって測定されるような搬送波対干渉比(carrier-to-interference ratio)（Ｃ／Ｉ）及び必要とされるビット当たりエネルギー対雑音比(energy-per-bit-to-noise)（Ｅｂ／ＮＯ）に依存している。簡略化のために、遠隔局６から基地局４への上りリンクは図１に図示されていない。一実施形態によれば、遠隔局６は無線データサービス加入者により操作される無線トランシーバ付きモバイルユニットである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
図１の実施形態に示されるように、遠隔局６は、可動性であり、さまざまな基地局４の間で関連付けを変更することができる。例えば、遠隔局６Ｆは当初、基地局４Ｆからデータ伝送を受信している。次に、遠隔局６Ｆは基地局４Ｆのセルから出て、基地局４Ｇのセルに入ってよい。遠隔局６Ｆは次に基地局４Ｆの代わりに基地局４Ｇに注意を喚起するためにＤＲＣ信号の送信を開始してよい。遠隔局６ＦからＤＲＣ信号を受信しないことにより、基地局４Ｆのロジックは、遠隔局６Ｆが接続を解き、もはやデータ伝送を受信しないと推論する。遠隔局６Ｆに関連付けられるデータ待ち行列は、次に陸線またはＲＦ通信リンクを介して基地局４Ｇに送信されてもよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
各ＢＴＳ８０８、８１０は図５に描かれているようなフローの待ち行列を保持するように適応されている。各ＢＴＳが自身の下りリンク（ＦＬ）で各アプリケーションフローに対応する一組の待ち行列を保持することに留意されたい。１つのアプリケーションフローは１つのＡＴに向けられる。しかしながら、複数のフローが１つのＡＴに向けられてよいことに留意されたい。各フローは自身に関連付けられるサービスの質グループ（ＱＳＧ）タイプを有する。各ＱＳＧは、ＱｏＳパラメータの集合により定義される。あるＱＳＧの各フローは、集合の中のパラメータのそれぞれに対して特定の値を有する。例えば、１つのＱＳＧは遅延及びジッタを含む集合によって定義され得る。このようなＱＳＧのそれらのフローは、遅延及びジッタに関する要件を指定する。待ち行列内のフローのそれぞれについて、ＢＴＳは３つの独立の待ち行列を含んだ集合を保持する。つまり（１）オリジナルの伝送待ち行列（Ｔｘ）、（２）再送待ち行列（Ｒｘ）、及び（３）自動反復要求待ち行列（ＡＲＱ）である。一実施形態では、ＡＲＱ待ち行列は早期決定ＡＲＱなどのＢＴＳとＡＴ間で実行される任意のタイプの再送機構のためのフローを格納する待ち行列に対応し得る。マルチメディアアプリケーションは、遅延限度要件を有するテレビ会議などの遅延に敏感なアプリケーションを含み得る。遅延限度は、ＡＮからの伝送からＡＴによる受信までに許容される指定時間である。適応加重アルゴリズムは、遅延限度要件を満たすため、及びこのようなアプリケーションのＩＰパケットが経験した平均遅延を短縮するために機能する。レート要件と平均遅延要件の両方を有するアプリケーションの場合、適応加重スケジューリングアルゴリズムはレート要件を満たすため、及び平均遅延を短縮するために機能する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
一実施形態では、ＱｏＳプロファイルは、ＱｏＳスケジューリンググループ（ＱＳＧ）と呼ばれるグループに分類される。表１は、カテゴリを一覧表示する。
【表１】
2010166582.tif 000134
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
図８は、適応加重スケジューリングアルゴリズムに従ったフローの処理を例示する。フロー９００、９０２、９０４及び９０６は、「Ｓ」が付されたスケジューリング装置９０８によって処理される。スケジューリング装置９０８は、適応加重スケジューリングアルゴリズムを適用する。適応加重スケジューリングアルゴリズムは、ＱＳＧプロファイルがフローのそれぞれに使用される。ＱＳＧプロファイルは、下記に詳述されるように、適応加重を計算するために使用される変数を特定する。スケジューリング装置９０８は、次に、選択されたＡＴにスケジュールされた伝送９１０を出力する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１３３
【補正方法】変更
【補正の内容】
【０１３３】
図１２Ａから図１２Ｅは、アプリケーションフローの処理及びアクティブなアプリケーションフローの一部としてのそのアプリケーションフローのスケジューリングを描いている。図１２Ａは、個々のアプリケーションフローのための初期化及びセットアップを描く流れ図である。プロセスは、ステップ１１００で開始して補償パラメータごとに使用される機構を選択する。補償パラメータは、遅延（Φ）、未決時間（γ）、ＤＲＣ（β）、ジッタ（δ）、及びレート（α）を含むが、これらに限定されない。ステップ１１０２では、適用可能な補償パラメータに関する閾値が選択される。補償パラメータがＡＮにとって重要なアプリケーションフローの任意のパラメータを含む場合があることに留意されたい。ステップ１１０４では、中間重みを計算するためのアルゴリズムが選択される。中間重みは、スケジューリングのために使用される適応重みを計算する上で使用される。ステップ１１０６では、適応重みを計算する上で使用されるスケーリングパラメータ（Ｃ）及び優先順位係数（Ｚ）の両方が設定される。ステップ１１０８では、このアプリケーションフローの初期重みが設定される。ステップ１１１０では、アプリケーションフローのＱｏＳ要件が評価される。ＤＲＣ要求により特定されるレート以外に指定されるＱｏＳ要件がない場合、デフォルト条件が使用される。デフォルト条件は前述されたように「ベストエフォート」と呼ばれる。この場合、デフォルト処理によって、このアプリケーションフローに使用される補償係数のすべては１に等しく設定される。本実施形態の場合、このケースでは、式（６）の計算で乗算演算子が使用され、したがって係数を１に設定すると、結果、それらの係数が無視される。つまりそれらの係数は加重に影響を及ぼさない。別の実施形態では、他の機構及び関数を実現してよく、したがって特殊な係数またはすべての補償係数を無視するために他の機構を使用してよいことに留意されたい。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１３８
【補正方法】変更
【補正の内容】
【０１３８】
アプリケーションフローの処理は、モードＩアプリケーションに関しては、図１２Ｄのステップ１１５０に続行する。ステップ１１５２では、方法は待機時間違反がないか監視する。待機時間違反がステップ１１５４で検出されると、処理は、ステップ１１５８に続行して初期化時に選択された機構に従って待機時間補償係数（γ）を計算する。さもなければ、待機時間補償係数（γ）はステップ１１５６で１に等しく設定される。処理は、次に図１２Ｅにさらに詳説されるステップ１１６０に続行する。モードＩアプリケーションフローの場合、違反チェックが直列または並行して行われてよいことに留意されたい。言い換えると、ステップ１１７０、１１７２に示されるように、レート違反、遅延／ジッタ違反及び待機時間のチェックは時間的に連続してまたは同時に実行されてよい。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１４１
【補正方法】変更
【補正の内容】
【０１４１】
スケジューリング係数＝ａｗ＊（ＤＲＣ／Ｔ）                              （10）
スケジューリングアルゴリズムは、次に、ステップ１１６６において、アクティブなアプリケーションフローのそれぞれに関して計算されるスケジューリング係数に従ってアプリケーションフローをスケジュールする。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１５０
【補正方法】変更
【補正の内容】
【０１５０】
ＡＳＦ、ＡＳ（ｔ）は毎時ｔに計算される。プロセスは、ＡＳ（ｔ）が１≦ＡＳmin_prespecified≦ＡＳ（ｔ）≦ＡＳmax_prespecified＜∞，∀ｔとなるように、ＡＳ（ｔ）についての最小閾値ＡＳmin_prespecifiedと最大閾値ＡＳmax_prespecifiedを求める。初め、値ＳinitialがＡＳＦに割り当てられ、その結果ＡＳ（０）＝Ｓinitialとなる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１５４
【補正方法】変更
【補正の内容】
【０１５４】
Avail(t)=maximum (L(t) - Res(t), 0)                                    （14）
図１４に描かれているような資源の多様な測度は、ユーザから受信されるデータレート制御（ＤＲＣ）データ要求により決定される。各ユーザは、上りリンクでＤＲＣデータ要求を送信する。ｃｄｍａ２０００  １ｘＥＶ−ＤＯまたは他のＨＲＰＤタイプのシステムでは、ユーザはＲＬ伝送の各スロットでＤＲＣデータ要求を送信する。図１５に描かれているように、ユーザ１からのデータ要求（ＤＲＣ  １）及びユーザ２からのデータ要求（ＤＲＣ２）は経時的に変化する。データ要求及び所要のＱｏＳは予約帯域幅（Ｒｅｓ）を決定する。ＤＲＣ値とＲｅｓの関係が説明図として示されることに留意されたい。別の実施形態及びシナリオは別の関係を招き得る。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１５６
【補正方法】変更
【補正の内容】
【０１５６】
一実施形態によれば、許可制御は、許可のために、フローｆkを評価する。許可制御は、最初に、フローｆkに対応する、ユーザについての観察されたＤＲＣｕ（ｆk）を適用して要求レートを満足させる。観察されたＤＲＣは以下のように、そのユーザについての平均ＤＲＣデータ要求以下である。
【数１５】
2010166582.tif 000135
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１６４
【補正方法】変更
【補正の内容】
【０１６４】
図１８Ｄに続行して、ステップ３４０において、ＱＳＧパラメータがフローごとに選択される。２つの平行な処理経路が考慮される。第１の経路はレートサンプル間隔でステップ３４２でレート違反を処理する。レートサンプル間隔はステップ３３２で計算されるサンプル持続期間を上回っていることに留意されたい。第２の経路はアクティブフローの処理を詳説する。あるフローに関して、プロセスはステップ３４４でサンプル持続期間中における遅延違反を有するＩＰパケットの割合を求める。ステップ３４６では、サンプル持続期間中におけるジッタ違反のあるＩＰパケットの割合が検討中のフローについて計算される。サンプル持続期間中にフローによって使用されるスロットの割合がステップ３４８で計算される。ステップ３５０では、プロセスはサンプル持続期間中にＱｏＳ要件を有するフローに与えられるスロットの割合を決定する。ステップ３５２では、プロセスはＱｏＳ違反がないかチェックし、ステップ３５４でＱｏＳグループＩＤを決定する。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１７７
【補正方法】変更
【補正の内容】
【０１７７】
ここで、ＳＥＲＶＥＤ＿ＳＬＯＴＳ（ｆk，ｔ，ｓ）は、フローｆkが（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）によって定義される期間中サービスを受けたスロット数であり、ＩＮ＿ＳＥＣＴＯＲ（ｆk，ｔ，ｓ）は期間（max（ｔ−Ｔ，ｔenter_latest（ｆk，ｓ）），ｔ）の間のスロットの総数である。期間（ｔ−Ｔ，ｔ）の間にセクタｓでＱｏＳ要件を有するフローに与えられるスロットの割合は、
【数２７】
2010166582.tif 000136
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１８８
【補正方法】変更
【補正の内容】
【０１８８】
のどちらかを有する場合、このフローはdelay_or_jitter_viol（ｆk，ｔ，ｓ）＝Ｙを有するとして指定される。それ以外の場合、プロセスはこのフローについてdelay_or_jitter_viol（ｆk，ｔ，ｓ）＝Ｎを設定する。他方、このフローがＮＡの資格を有している場合、delay_or_jitter_viol（ｆk，ｔ，ｓ）＝ＮＡである。
【表２】
2010166582.tif 000137
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０２１２
【補正方法】変更
【補正の内容】
【０２１２】
を有するフローから構成される。
【表４】
2010166582.tif 000138
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０２１９
【補正方法】変更
【補正の内容】
【０２１９】
許可制御
時刻ｔにおける、Ｒ（ｔ）ユーザをＵ1，Ｕ2，．．．，ＵR(t)として示すとして、時刻ｔにおけるユーザＵｊのフロー数をｎｕｍ＿ｆｌｏｗｓ（Ｕj，ｔ）とする。ユーザＵｊが、時刻ｔで許可されている（ｋ−１）のフロー、つまりｎｕｍ＿ｆｌｏｗｓ（Ｕj，ｔ）＝ｋ−１であると仮定する。時刻ｔにおいてユーザＵｊについての新しいフローｆk,jを許可すると決定するために、プロセスはユーザＵｊについて観察されたＤＲＣを使用して以下をチェックする。
【数５０】
2010166582.tif 000139
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０２７８
【補正方法】変更
【補正の内容】
【０２７８】
ここでは、
【数７７】
2010166582.tif 000140
【数７８】
2010166582.tif 000141
【数７９】
2010166582.tif 000142
【手続補正２０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための方法であって、
適応加入を増加するために、第１のタイプのＱｏＳ違反を有する第１のフローを先処理することと、
第１のタイプのＱｏＳ違反について先処理最大値に達したことを判断することと、
第２のタイプのＱｏＳ違反を有する第２のフローを先処理することと、
を含む、方法。
【請求項２】
第２のフローを先処理することが、
前記第２のフローの伝送のために使用されるスロットの数に基づいて前記第２のフローを選択することをさらに含む、請求項１に記載される方法。
【請求項３】
パケットデータアプリケーションフローをサポートする無線通信システムにおいて資源をスケジュールするための方法であって、
第１のタイプのアプリケーションフローに関連付けられるサービスの質パラメータについて少なくとも１つの補償係数を選択することと、
サービスの質パラメータに基づいて前記少なくとも１つの補償係数を計算することと、
前記第１のタイプのアプリケーションフローについての重みを前記少なくとも１つの補償係数の関数として計算することと、
前記重みを使用してフロー単位のスケジューリング係数を計算することと、
前記スケジューリング係数に基づいて前記アプリケーションフローをスケジュールすることと、
を含む、方法。
【請求項４】
第１のユーザが複数のアクティブなアプリケーションフローを有し、
前記複数のアプリケーションフローについての総計補償係数を計算することをさらに含む、請求項３に記載の方法。
【請求項５】
前記複数のアクティブなアプリケーションフローは、前記第１のタイプの、及び第２のタイプのアプリケーションフローを含む、請求項４に記載の方法。
【請求項６】
第２のタイプのアプリケーションフローについての重みを計算することをさらに含む、請求項５に記載の方法。
【請求項７】
前記複数のアクティブなアプリケーションフローの内の１つを伝送のために選択することをさらに含む、請求項６に記載の方法。
【請求項８】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための装置であって、
適応加入を増加するために、第１のタイプのＱｏＳ違反を有する第１のフローを先処理するための手段と、
前記第１のタイプのＱｏＳ違反について先処理最大値に達したこと判断するための手段と、
第２のタイプのＱｏＳ違反を有する第２のフローを先処理するための手段と、
を備える、装置。
【請求項９】
パケットデータアプリケーションフローをサポートする無線通信システムにおいて資源をスケジュールするための装置であって、
第１のタイプのアプリケーションフローと関連付けられるサービスの質パラメータの少なくとも１つの補償係数を選択するための手段と、
サービスの質パラメータに基づいて前記少なくとも１つの補償係数を計算するための手段と、
前記第１のタイプのアプリケーションフローについての重みを前記少なくとも１つの補償係数の関数として計算するための手段と、
前記重みを使用してフロー単位のスケジューリング係数を計算するための手段と、
前記スケジューリング係数に基づいて前記アプリケーションフローをスケジュールするための手段と、
を備える、装置。
【請求項１０】
インターネットプロトコル（ＩＰ）アプリケーションをサポートし且つアクセスネットワーク（ＡＮ）及びそれぞれが要求データレートを前記ＡＮに送信する複数のアクセス端末（ＡＴ）を含み且つ前記ＡＴに対するＱｏＳ要件を有するアプリケーションフローをサポートする通信システムにおいて資源を割り当てるための装置であって、
アプリケーションフローを受け取り且つ前記アプリケーションフローの前記サービスの質（ＱｏＳ）要件を決定するように適応されたフロー分類装置と、
前記フロー分類装置に結合され、パケットデータ伝送をスケジュールするように適応されたスケジューラと、
前記フロー分類装置及びスケジューラに結合され、使用可能な資源が要求データレートをサポートするときにアプリケーションフローを許可するように適応された許可制御装置と、
前記フロー分類装置、前記スケジューラ、及び前記許可制御装置に結合され、前記アプリケーションフローについてのＱｏＳ違反を判断し、ＱｏＳ統計を維持するように適応されたＱｏＳモニタと、
前記許可制御装置に結合され、使用可能な資源を更新するように適応された適応装置と、
を備える、装置。
【請求項１１】
前記スケジューラは、要求データレートに応じてアプリケーションフローをスケジュールするように適応される、請求項１０に記載の装置。
【請求項１２】
前記スケジューラは、ＱｏＳ統計に応じてアプリケーションフローをス系ジュールするように適応される、請求項１０に記載の装置。
【請求項１３】
前記スケジューラは、ＱｏＳ要件に応じてアプリケーションフローをスケジュールするように適応される、請求項１０に記載の装置。
【請求項１４】
前記スケジューラは、加入情報に基づいてアプリケーションフローをスケジュールするように適応される、請求項１０に記載の装置。
【手続補正２１】
【補正対象書類名】図面
【補正対象項目名】図２Ａ
【補正方法】変更
【補正の内容】
【図２Ａ】
2010166582.tif 000143
【手続補正２２】
【補正対象書類名】図面
【補正対象項目名】図２Ｂ
【補正方法】変更
【補正の内容】
【図２Ｂ】
2010166582.tif 000144
【手続補正２３】
【補正対象書類名】図面
【補正対象項目名】図７Ａ
【補正方法】変更
【補正の内容】
【図７Ａ】
2010166582.tif 000145
【手続補正２４】
【補正対象書類名】図面
【補正対象項目名】図１２Ｄ
【補正方法】変更
【補正の内容】
【図１２Ｄ】
2010166582.tif 000146
【手続補正２５】
【補正対象書類名】図面
【補正対象項目名】図１２Ｅ
【補正方法】変更
【補正の内容】
【図１２Ｅ】
2010166582.tif 000147
【手続補正２６】
【補正対象書類名】図面
【補正対象項目名】図１６
【補正方法】変更
【補正の内容】
【図１６】
2010166582.tif 000148
【外国語明細書】
2010166582000001.pdf