(57)【特許請求の範囲】
【請求項１】
ワイヤレス通信ネットワークの資源を、前記ネットワークのチャネルを介してユーザ機器に送信すべき、複数のパケットを含むトラヒックに割り当てる方法であって、
被選択キューに格納すべきパケットを受信すること、
前記被選択キューの最大遅延を求めること、
開始時間、終了時間、およびキューイング順を求めること、
前記開始時間、前記終了時間、および前記キューイング順に従って前記被選択キューに前記パケットを挿入すること、
前記被選択キューの重みを更新すること、
前記被選択キューからデキューすべき次のパケットをスケジュールすること、
前記チャネルを介して前記次のパケットを前記ユーザ機器に送信すること、
前記ユーザ機器から前記トラヒックについての要求を受信すること、
前記要求を受け入れること、
前記ネットワークの物理層資源および前記ネットワーク上の既存のトラヒックから利用可能な資源を推定すること、
前記トラヒックおよび前記既存のトラヒックの送信に十分な資源が利用可能である場合のみ、前記要求を受け入れること
を含み、
前記推定することは、前記ユーザ機器からのチャネル状態のフィードバックに基づくものであり、
前記パケットは、前記チャネル状態に応じる複数の変調符号化レベルの１つに従ってサブクラスにさらに分類され、
Ｎ個のレベルがあり、レベルｎのデータレートＲｎはＲｎ（１≦ｎ≦Ｎ）であり、前記パケットの送信に使用される前記チャネルγの信号対雑音比のフレームエラーレートはＦＥＲ（γ，ｎ）であり、実効伝送レートがＲｎ×（１−ＦＥＲ（γ，ｎ））に等しいようにレベルｎが使用される、ワイヤレス通信ネットワークの資源を、前記ネットワークのチャネルを介してユーザ機器に送信すべきトラヒックに割り当てる方法。
【請求項２】
複数のキューがあり、該方法は、
前記受信パケットをｉ個のクラスの１つに分類することであって、各クラスに１つのキューがあること、
前記ｉ番目のキューを前記被選択キューとして選択すること
をさらに含む、請求項１記載の方法。
【請求項３】
複数のクラスは、従来型音声トラヒッククラス、オーディオ・ビデオストリーミングトラヒッククラス、インタラクティブトラヒッククラス、およびベストエフォートトラヒッククラスを含む、請求項２記載の方法。
【請求項４】
各キューには再送信キューが関連付けられ、該方法は、
前記パケットを再送信すべき場合は前記再送信キューを選択すること
をさらに含む、請求項２記載の方法。
【請求項５】
前記トラヒックは、サービスパラメータの品質に従って分類され、該方法は、
前記サービスパラメータの品質に基づいて前記被選択キューの前記重みを求めること、
前記サービスパラメータの品質に基づいて前記被選択キューの長さを求めること
をさらに含む、請求項２記載の方法。
【請求項６】
ハイブリッド自動繰り返し要求（Ｈ−ＡＲＱ）が許可される
請求項４記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはワイヤレスパケットネットワークに関し、より詳細には、ワイヤレスネットワークのダウンリンクチャネルでの資源の制御に関する。
【背景技術】
【０００２】
セルラネットワーク等のワイヤレス通信ネットワークは、様々なサービス品質（ＱｏＳ）要件を有する統合マルチメディアアプリケーションをサポートする必要がある。異なる高速サービスのＱｏＳを差別化することにより、基地局がサービス提供するセル内の様々なユーザ機器（ＵＥ）のマルチメディア需要をサポートすることが可能になる。ＵＥとしてはセルラ電話、携帯計算装置、および他のエンドユーザ端末を含むことができる。
【０００３】
データパケットサービスと従来の回線交換式音声サービスのトラヒック特徴の相違により、専用チャネルが多くのシステムのデータサービスに割り当られ、高速データ通信（ＨＤＲ）システム等、多くの標準仕様が知られている。Bender他、「CDMA / HDR: A bandwidth efficient high speed data service for nomadic users」、IEEE Commun. Mag.,  Vol. 38, No. 7, pp. 70-77, July 2000、1xTREME of 3rd Generation Partnership Project 2 (3GPP2), Motorola and Nokia, 「3GPP2 1xTREME Presentation」、C00-20000327-003, March 2000, およびthe High Speed Downlink Packet Access (HSDPA) of 3rd Generation Partnership Project (3GPP), Motorola, 「Feasibility study of advanced technique for High Speed Downlink Packet Access」、TSG-R WG1 document, R1-556, April, 2000を参照のこと。
【０００４】
ワイヤレスパケットネットワークでは、高速ダウンリンクデータチャネルが同じセル内の複数のＵＥによって共有される。標準化機構により共有ダウンリンクチャネルに関する多くの新技術が開発された。たとえば、３ＧＰＰのＨＳＤＰＡでは、方策に、適応変調符号化（ＡＭＣ：adaptive modulation and coding）、ハイブリッド自動繰り返し要求（Ｈ−ＡＲＱ：hybrid automatic repeat request）、高速セル選択（ＦＣＳ:fast cell selection）、および多重入力多重出力（ＭＩＭＯ）システムが含まれる。
【０００５】
ＡＭＣは、変調符号化方式を各ユーザのチャネルの状態に合わせるリンク適応方法を提供する。ＡＭＣを使用するシステムでは、基地局に近いＵＥには通常、Ｒ＝３／４ターボコードを有する６４ＱＡＭ等、符号化率のより高いより高次の変調が割り当てられる。変調の次元および／または符号化率は、ＵＥと基地局の間の距離が増大するにつれて低くなる。
【０００６】
Ｈ−ＡＲＱは、失われたまたはエラーのあるパケットの再送信機構を提供する。追跡組み合わせ（chase combining）、レートコンパチブルパンクチャードターボコード、および増分冗長性等、Ｈ−ＡＲＱを実施する多くの方式がある。
【０００７】
ＦＣＳの場合、ＵＥは、アップリンクシグナリングを通してダウンリンクチャネルに使用すべき「最良」セルを選択する。したがって、複数のセルがアクティブセットのメンバであることができるが、一度に１つのセルのみが送信し、潜在的に干渉を低減するとともにシステムの能力を増大させる。
【０００８】
多重入力多重出力（ＭＩＭＯ）システムは、基地局の送信器およびＵＥの受信器の両方に複数のアンテナを採用する。これは、従来の単一アンテナシステムおよび送信器に複数のアンテナを有する送信ダイバーシティ技法よりも優れたいくつかの利点を提供する。
【０００９】
重要な問題は、資源の制御および管理をこれら新技術とどのように統合するかである。たとえば、基地局におけるデータ伝送能力はＡＭＣ方式の動的変化に従って変わる。同量のコードおよび時間空間の場合、通常、高い変調方式を使用するＵＥほど、低い変調方式を使用するＵＥよりも高いデータレートを得ることができる。
【００１０】
本発明に特に関係するのは、ＡＭＣおよびＨ−ＡＲＱシステムに適合された高速ダウンリンク共有チャネルにＱｏＳ制御を使用する資源の割り当てである。
【００１１】
パケットスケジューリングは、ワイヤレスマルチメディアネットワークの最も重要なＱｏＳ制御手法の１つである。ワイヤレスネットワークの多数のパケットスケジューリング技法が既知であり、たとえば、チャネル状態依存パケットスケジューリング（ＣＳＤＰＳ）、Fragouli他、「Controlled multimedia wireless link sharing via enhanced class-based queuing with channel-state dependent packet scheduling」、Proc. IN-FOCOM'98, vol. 2, pp. 572-580, March 1998、理想ワイヤレスフェアキューイングプロセス（ＩＷＦＱ：idealized wireless fair queuing process）、Lu他、「Fair scheduling in wireless packet net-works」、IEEE/ACM Trans. Networking, Vol. 7, No. 4, pp. 473-489, 1999参照、チャネル状態独立フェアキューイング（ＣＩＦ−Ｑ:channel-condition independent fair queuing）、Ng他、「Packet fair queuing algorithms for wireless networks with location-dependent errors」、Proc. INFOCOM98, pp. 1103-1111, March 1998、サーバベースの公平性（ＳＢＦＡ：server based fairness）、Ramanathan他、「Adapting packet fair queuing algorithms to wireless network」、Proc. ACM MOBICOM'98, October 1998、改良版チャネル状態状態依存パケットスケジューリング（Ｉ−ＣＳＤＰＳ）、Gomez他、「The Havana frame-work for supporting application and channel dependent QoS in wireless networks」、Proc. ICNP'99, pp. 235-244, November 1999、チャネル適応フェアキューイング（ＣＡＦＱ:channel adaptive fair queuing）、Wang他、「Channel Capacity Fair Queuing in Wireless Networks: Issues and A New Algorithm」、ICC 2002, April 2002、変形版最大加重遅延先（Ｍ−ＬＷＤＦ:modified largest weighted delay first）、Andrews他、「Providing quality of service over a shared wireless link」、IEEE Communications Magazine, Vol. 39, No. 2, pp. 150-154, February 2001、および符号分割汎用プロセッサ共有（ＣＤＧＰＳ）、Xu他、「Dynamic bandwidth allocation with fair scheduling for WCDMA systems」、IEEE Wireless Communications, April 2002である。
【００１２】
Wang、Andrews、およびXuを除き、大半の従来技術による手法は、２状態マルコフモデル等の単純なワイヤレスモデルを想定している。スケジューラは、セッションが「良好な」チャネル状態を有するとき、すなわち実効スループットが最大にあるとき、ワイヤレスパケットスケジューリングプロセスを実行するエラーのないシステムをシミュレートする。データを送信するようにスケジュールされたセッションが「不良」チャネル状態になると、セッションは送信機会をあきらめ、良好なチャネル状態を有するセッション等、他のエラーのないセッションに渡す。次に、これらエラーのないセッションは埋め合わせとして、チャネル状態が再び良好になったときにそれぞれの送信権をエラーセッションに戻す。これらプロセスは主に、公平性および「弱い」ＱｏＳ保証を提供する。
【００１３】
Wangは、公平性の新しい定義、およびいくつかのチャネル状態に適合されたスケジューリングプロセスについて述べている。しかし、明示的なＱｏＳ保証は提供されていない。Andrewsは、遅延とスループットのトレードオフに基づいてユーザスケジューリングプロセスについて述べている。その手法は、各ＵＥが一度に１つのＱｏＳトラヒッククラスのみをサポートすることができると想定する。Xuは、汎用プロセッサ共有（ＧＰＳ）方式を、異なるＵＥのタイムスロットではなく分散コードに動的に適用する。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
高速ダウンリンクチャネルにおいて資源を動的に制御する方法およびシステムを提供することが望まれる。方法およびシステムは、ＡＭＣおよびＨ−ＡＲＱ等の他のＨＳＤＰＡ技術と密接に統合されるべきである。ＡＭＣはチャネル状態に従って動的に変化するため、スケジューラ機構は、単純な従来技術による「オン／オフ」ワイヤレスチャネルモデルに基づくべきではない。
【００１５】
さらにＨ−ＡＲＱは、過剰なトラヒック負荷をワイヤレスネットワークに持ち込む。従来技術によるスケジューリング技法は増大した負荷を考慮しない。
【００１６】
さらに、元のパケットと再送信されるパケットを区別することが重要であり、ＵＥは異なるＱｏＳ要件を有する複数のストリームを同時に受信することが可能であるべきである。
【００１７】
たとえば、ユーザは、ＦＴＰサーバからテキストファイルをダウンロードしながら、ビデオサーバからストリーミングビデオを見ることが可能であるべきである。したがって、基地局のスケジューラは、ＱｏＳトラヒッククラスおよび同じダウンリンクＨＳＤＰＡチャネルの容量を共有する異なるＵＥを同時に処理する必要がある。
【００１８】
通常、従来技術による方策は、トラヒッククラスの異なる資源およびＱｏＳ要件を考慮することなく、異なるＵＥ端末に対して資源を個々にスケジュールするだけである。
【００１９】
したがって、ネットワーク全体のスループットが最適化されるようにすべてのネットワークトラヒックを考慮する動的資源制御システムおよび方法が必要である。
【課題を解決するための手段】
【００２０】
本発明は、ＡＭＣおよびＨ−ＡＲＱ等の既知のＨＳＤＰＡ技術と統合される動的資源制御方法を提供する。各ユーザのＡＭＣ方式はチャネル状態に従って動的に変化するため、本発明によるスケジューラは、各ユーザ機器のチャネル状態情報を動的に得る。したがってスケジューラは、従来技術によるワイヤレスチャネルモデルの単純な「オン／オフ」制御を使用する必要がある。
【００２１】
本発明は、Ｈ−ＡＲＱによるワイヤレスネットワークに持ち込まれる負荷の増大を考慮する。本発明は、元のパケットと再送信されたパケットを別のキューに配置することによって区別し、したがってＵＥが異なるＱｏＳ要件を有する複数のストリームを同時に受信することができる。
【００２２】
本発明は、従来技術でのように異なるＵＥにではなく、基地局における異なるトラヒッククラスに、異なるＱｏＳ要件を有するＵＥを割り当てる。
【００２３】
キューの長さおよび重み等、キューパラメータが、遅延およびパケット損失要件に従って指定される。本発明は、トラヒックの動的負荷およびキューの状態に従ってキューの重みを動的に調整する遅延敏感ＷＦＱ（ＤＳＷＦＱ）スケジューリング方式を用いる。
【００２４】
したがって、本発明は各クラスのユーザに明示的なＱｏＳを提供することができる。ユーザはそれぞれの現在のＡＭＣ方式に従って分類され、クラスはサブクラスにさらに分割される。ＡＭＣ方式から得られるように、「良好」なチャネル状態を有するユーザには、「不良」チャネル状態を有するユーザよりも高いスケジューリング優先度が与えられる。
【００２５】
これは、異なるＡＭＣ方式に異なるランダム初期検出（ＲＥＤ：random early detection、ランダム早期検出）を設定することによって実現される。本発明によるユーザの分類により、不良なチャネル状態を有するユーザを制限することによってネットワーク全体のスループットを最適化することができる。
【００２６】
サービス品質（ＱｏＳ）制御を共有高速ダウンリンクパケットアクセスワイヤレスチャネルに提供するために、本発明は、変調符号化（ＡＭＣ）およびハイブリッド自動繰り返し要求（Ｈ−ＡＲＱ）に統合されてクラスベースのアプリケーションをサポートする新規の動的資源制御の枠組みを用いる。
【００２７】
本発明はまた、遅延敏感動的フェアキューイング（ＤＳＤＦＱ：delaysensitive dynamic fair queuing）と呼ばれる新規のワイヤレススケジューリングプロセスも用いて、マルチメディアアプリケーションの遅延要件を満たすとともに、高いネットワーク効率も維持する。
【００２８】
本発明は、異なるトラヒッククラスからの負荷変動およびユーザの移動性、フェージング、およびシャドーイングにより影響を受けて動的に変化するワイヤレスチャネル状態に適合することができる。
【００２９】
より具体的には、方法は、ワイヤレス通信ネットワークの資源を、ネットワークのチャネルを介してユーザ機器に送信されるトラヒックに割り当てる。被選択キューに格納すべきトラヒックのパケットが受信される。被選択キューの最大遅延が、開始時間、終了時間、およびキューイング順とともに求められる。パケットは、開始時間、終了時間、およびキューイング順に従って被選択キューに挿入され、次に、被選択キューの重みが更新される。次に、被選択キューからデキューすべき次のパケットがスケジュールされ、次のパケットがチャネルを介してユーザ機器に送信される。
【発明の効果】
【００３０】
従来技術によるＷＦＱおよびＦＩＦＯ（非ＱｏＳ）方式と比較して、本発明のＤＳＤＦＱ方法は、可変ビットレートおよび固定ビットレート（ＣＢＲ−ＶＢＲ）両方のストリーミングビデオでより少ない遅延を受ける。ＣＢＲの場合、本発明の方法は遅延を２０ｍｓに制御することができる一方で、ＷＦＱの場合、遅延は本発明の方式の略２０倍の長さである。ＶＢＲの場合、本発明の方法は遅延を約半分に低減する。他のトラヒッククラスの場合でも、本発明の方法はＷＦＱおよびＦＩＦＯ両方よりも良好なパフォーマンスを得る。
【発明を実施するための最良の形態】
【００３１】
システムの構造
図１は、本発明によるシステムおよび方法１００を示す。システムおよび方法は、ワイヤレス通信ネットワーク、たとえばセルラネットワークの高速ダウンリンクパケットアクセス（ＨＳＤＰＡ）チャネルにおける資源を動的に制御する。このようなネットワークでは、基地局は通常、チャネル１８０を介してセル内のユーザ機器（ＵＥ）１０３の複数のインスタンスにサービスを提供する。ＵＥ１０３は静止していても、また移動していてもよい。
【００３２】
システム１００は、分類器・トラヒックシェーパ１２０に接続されたアドミッションコントローラ１１０を備える。変調符号化方式（ＭＣＳ）セレクタ１３０が、コントローラ１１０および分類器／シェーパ１２０に入力を供給する。資源推定器１４０が、コントローラ１１０、セレクタ１３０、およびスケジューラ１５０に入力を供給する。スケジューラは送信器１６０に接続される。分類器／シェーパ１２０からの出力は、送信器１６０に転送される前にキュー対１７０に格納される。送信器は、チャネル１８０を介してデータパケットをＵＥ１０３に送信する。
【００３３】
システムの動作
動作中、システム１００は、ネットワーク中のワイヤレスユーザ機器（ＵＥ）１０３、たとえばセルラ電話、モバイルプロセッサ、およびエンドユーザ端末からトラヒック１０２に対する要求１０１を受け取る。トラヒックは、当分野において既知のようにパケットの形で送信される。要求１０１はアドミッションコントローラ１１０に渡される。トラヒック１０２は、サーバ１９０から発信してもよく、またネットワーク内の他の任意の場所にあるＵＥから発信してもよい。
【００３４】
セレクタ１３０および推定器１４０の出力に応じて要求が受け入れられる場合、対応するトラヒック１０２が分類されて整形され（１２０）、パケットが適切なキュー１７０に転送される。スケジューラ１５０は、キューイングされたトラヒックが送信器１６０に解放されて、以下さらに詳述するようにワイヤレスチャネル１８０を介してユーザ機器１０３に送信される順序を決定する。
【００３５】
動的資源制御
本発明の目的は、アドミッションコントローラ１１０、分類器・トラヒックシェーパ１２０、ＭＣＳセレクタ１３０、送信器１６０、キュー１７０、チャネル１８０、およびユーザ機器１０３を備えた基地局への動的資源割り当てを実現することにある。基地局がサービス提供する各セル内に複数の移動または固定のＵＥ１０３があり、各ＵＥが複数の異なるトラヒッククラスを同時にサポートすることができるものと想定した。
【００３６】
トラヒッククラスは、従来の音声トラヒック、ストリーミングオーディオ・ビデオトラヒック、閲覧等のインタラクティブトラヒック、および電子メール等のバックグラウンドベストエフォートトラヒックであることができる。さらなるクラスも定義することが可能であることを理解されたい。
【００３７】
従来技術と比較して、本発明のシステムおよび方法は、異なるＵＥ１０３にパケットをどのようにスケジュールするかを考慮するのみならず、おそらく異なるチャネル状態を有する複数のＵＥ環境における異なるトラヒッククラスもスケジュールする。
【００３８】
したがって、トラヒック１０２に対する伝送要求１０１はアドミッションコントローラ１１０に送られる。コントローラは、物理層資源測定および既存のトラヒックから利用可能な資源を推定する（１４０）ことによって、ネットワークへの新しい伝送トラヒックを受け入れるか否かを判定することができる。
【００３９】
要求が受け入れられた後、トラヒックのパケットをキューイングする前に、対応するトラヒックストリームが分類され、整形される（１２０）。
【００４０】
トラヒックストリームは、サービス品質（ＱｏＳ）パラメータ、たとえば遅延およびパケット損失に従って分類される（１２０）。ＱｏＳパラメータにより、各キューの長さおよびワイヤレスフェアキューイング（ＷＦＱ）の重み、および重み付きランダム初期検出（ＲＥＤ）が決まる。
【００４１】
ハイブリッド自動繰り返し要求（Ｈ−ＡＲＱ）が許可されると、ワイヤレスチャネル１８０の状態が不良状態の場合は再送信を大量の追加トラヒックに導入することができる。したがって、２つのキュー１７０、すなわち元の送信キュー１７０’および再送信キー１７０’’をあらゆるクラスに割り当てる。
【００４２】
各クラス毎に、サブクラス（異なるパターン）が、チャネル状態に応じてＭＣＳセレクタ１３０に従って指定される。拡散コード１６１および時間フレーム１６２が両方ともスケジュールされ、ＵＥ１０３のトラヒック１０２に割り当てられる。３ＧＰＰ  ＨＳＤＰＡでは、時間フレームの長さ、すなわち伝送時間間隔（ＴＴＩ）は一定であり、２ｍｓに等しく、拡散コード１０１は直交コードである。拡散率（ＳＦ）は固定であり、１６に等しい。同じＴＴＩ内の複数の拡散コードを各ＵＥ１０３に割り当てることができるものと想定する。ＷＦＱの重みは、各キューの状態に従って動的に調整される。
【００４３】
図１に示すように、ＵＥ１０３はチャネル１８０の状態を監視し、搬送波対干渉（Ｃ／Ｉ）情報１９１をフィードバックする。チャネル状態１９１を使用して、利用可能な資源が推定される（１４０）とともに、各ＵＥ１０３のトラヒック１０２に変調符号化方式（ＭＣＳ）が選択される（１３０）。
【００４４】
Ｎ個のＭＣＳレベルがある場合、ＭＣＳレベルｎのデータレートはＲｎ（１≦ｎ≦Ｎ）である。値ＦＥＲ（γ，ｎ）は、チャネルγおよびＭＣＳレベルｎの所与の信号対雑音比のフレームエラーレート（ＥＦＲ）を表す。
【００４５】
すると、実効データ伝送レートはＲｎ×（１−ＦＥＲ（γ，ｎ））に等しい。チャネルγの測定状態の実効データレートを最大化するように、特定のＭＣＳレベルｊが選択される（１３０）。すなわち、
【００４６】
【数１】
0004397928.tif 000002
【００４７】
である。
【００４８】
ワイヤレスインタフェースにおけるプロトコルデータ単位（ＰＤＵ）は、フレームまたはＴＴＩ中に搬送されるデータトラヒックである。データレートはＭＣＳレベルに伴って変化するため、ＰＤＵサイズも変化する。したがって、トラヒックは可変ＰＤＵサイズに従ってセグメント化される。ＵＥはＰＤＵの受信を承認する。ＰＵＤの誤った伝送が検知される場合、ＰＤＵは最大でＭ回再送信される。
【００４９】
再送信中、ＭＣＳレベルは元の送信のものと同じままである。リンクの利用を向上させ、本発明のスケジューリングプロセス１５０に適合させるために、本発明では、異なるＭＣＳレベルを有するＰＤＵに異なる最大再送信回数（Ｍ）を用いる。ＭＣＳレベルが高いほど、Ｍの値は大きい。
【００５０】
スケジューリング
本発明では、ＨＳＤＰＡワイヤレスマルチメディアトラヒックに新規の遅延敏感動的フェアキューイング（ＤＳＤＦＱ）スケジューリングを用いる。スケジューラ１５０は、適切な拡散コード１６１とともにフレームまたはＴＴＩ中のＰＤＵをスケジュールするＭＡＣ層にある。便宜上、本発明ではＰＤＵを「パケット」と呼ぶ。
【００５１】
本発明では、キューの現在遅延に従って各キューの重みを動的に調整し、それに従ってパケットの送信をスケジュールする。本発明では、異なるトークンを使用して、１つのクラス内の異なるＭＣＳレベルを有するパケットを区別する。さらに本発明では、重みの付いたＲＥＤを使用して、どのパケットを落とすべきかを判定する。本発明のＤＳＤＦＱは、あらゆるキューの遅延状態に従って動的な公平性を保つ。従来技術によるフェアキューイング方式とは異なり、本発明のキューイングは、汎用プロセッサ共有（ＧＰＳ）への近似手法ではない。
【００５２】
仮想クロック、ＷＦＱ、およびＷＦ２Ｑに一般に使用される優先度ソートキューイング手順が、Zhangにより「Service Discipline For Guaranteed Performance Service in PacketSwitching Networks」、Proceedings of IEEE, 83 (10), October 1995に説明されている。本発明では、その技法を本発明のＤＳＤＦＱに適合させる。
【００５３】
ＷＦＱでは、仮想終了時間である状態変数Ｆが各チャネルに関連付けられて、トラヒックを監視し実施する。ＷＦＱでは、パケットの仮想終了時間Ｆは、
【００５４】
【数２】
0004397928.tif 000003
【００５５】
として定義される。但し、Ｆｋｉは、クラスｉのｋ番目のパケットの仮想終了時間であり、Ｖ（ｔ）は、ｋ番目のパケットを受信した仮想時間であり、φｉはクラスｉの重みであり、Ｌｋｉは、バイト単位で測定されたｋ番目のパケットのパケットサイズである。
【００５６】
従来技術によるＷＦＱでは、重みφｉは固定であり、現在のチャネルの状態を反映しない。これとは対照的に、本発明のＤＳＤＦＱの場合、各キューの重みφｉは可変である。パケットキューイングイベントに応答して、現在のパケットの遅延（遅延）が求められ、これを使用して、
【００５７】
【数３】
0004397928.tif 000004
【００５８】
に従って重みφｉを変更する。但し、φ０ｉはクラスｉの基本の重みであり、φｍａｘｉはクラスｉの最大の重みであり、ｄｅｌａｙｋｉはクラスｉ中のｋ番目のパケットのキューイング遅延であり、ｋｉは調整パラメータである。
【００５９】
値Ｓｋｉはクラスｉ中のパケットｋの供給が開始する仮想時間を表し、Ｆｋｉはクラスｉ中のパケットｋの供給を終了する仮想時間を表す。
【００６０】
パケットのエンキューおよびデキュー
図２は、上に説明した変数および式を用いる、本発明によりパケットをエンキュー、またデキューする方法２００を示す。
【００６１】
キューイングすべきトラヒックの新しいパケット２０１の受信に応答して、ステップ２１０が、対応するキュー１７０の最大遅延２０２を求める。
【００６２】
ステップ２２０が、仮想開始時間Ｓｋｉおよび仮想終了時間Ｆｋｉ、ならびにデキュー順２０３を求める。
【００６３】
これら２つのステップは、
【００６４】
【数４】
0004397928.tif 000005
【００６５】
によりそれぞれ表現することができる。但し、Ｌｋ−１ｉはクラスｉ中のｋ番目のパケットの長さであり、Ｂｗはチャネルの帯域幅であり、ｔｌａｓｔは仮想時間がキューの重みを最後に更新した実際の時間である。
【００６６】
次に、パケット２０１の番号を、仮想終了時間の順序に従って出力制御キュー２６０に挿入する（２３０）。
【００６７】
ステップ２４０は、以下のように、
【００６８】
【数５】
0004397928.tif 000006
【００６９】
に従って新しい遅延値に従ってキューの重みを更新する。但し、φｋｉはクラスｉの基本の重みであり、ｇ（ｄｅｌａｙｋｉ）は重み曲線を表す。
【００７０】
ステップ２５０が、次のパケット２０４を送信すべき実際の時間ｔを求め、パケットの送信器１６０へのデキューをスケジュールする。送信器は、選択されたＭＣＳ１３０に従ってパケットを、正しい拡散コード１６１および時間フレーム１６２とともに送信する。
【００７１】
次にスケジュールされたパケットの実際の時間がＮｅｘｔ（ｔ）である場合、時間Ｎｅｘｔ（ｔ）において、各クラスの重みおよび遅延が以下のように、
【００７２】
【数６】
0004397928.tif 000007
【００７３】
更新される（２４０）。
【００７４】
したがって、次のパケットＰｋｉが受け取られると、まず遅延を求め（２１０）、新しい遅延が前の遅延よりも大きく、したがってクラスｉの保証ビットレートが一時的に増大する場合は重みφｉを増大する。
【００７５】
各クラスのパケットは独立して受け取られ、重みは、パケットを受け取る都度更新されるため、動的バランスは保たれ、帯域幅が、従来技術による静的スケジューリング方法を用いる場合に可能なよりも公平に割り当てられる。
【００７６】
解析
ｇｉ（ｄｅｌａｙ）が非ゼロの場合について、本発明のＤＳＤＦＱプロセスを解析する。トラヒックが「穴あきバケツ整形（leaky bucket shaping）」により課されるものと同様の制約を有するものと想定する。「穴あきバケツ」からのトークンが使用される場合、ネットワークに入るトラヒックは、以下のように、
【００７７】
【数７】
0004397928.tif 000008
【００７８】
整形される。但し、Ａｉ（τ，ｔ）は、時間間隔［τ，ｔ］中にネットワークに入るクラスｉのトラヒック量である。
【００７９】
トークンは固定レートρｉで生成され、パケットは、必要な数のトークンを穴あきバケツから取得した後でのみネットワーク中に解放される。穴あきバケツは最大でρｉ個のトークンを収容する。
【００８０】
本発明の方式では、クラスｉ中のパケットｋ２０１の遅延２０２の計算が鍵となる問題である。上に述べたように本発明では、パケット２０１を受け取ったときに遅延２０２を求め（２１０）、パケット２０４がデキューされる（２５０）ときは常に重みが更新される（２４０）。したがって、計算された遅延は実際の遅延よりも、範囲［１，Ｌ／Ｂｗ］内の値だけ少ない場合がある。但し、Ｌはパケット長であり、Ｂｗはチャネルの帯域幅である。
【００８１】
システム１００が時間０において動作を開始する場合、
【００８２】
【数８】
0004397928.tif 000009
【００８３】
が、クラスｉのパケットｋの時間０からの総遅延である。クラスｉのパケットｋの実際の遅延は、
【００８４】
【数９】
0004397928.tif 000010
【００８５】
により表すことができる。但し、ｔはクラスｉのパケットｋを受け取った実際の時間である。
【００８６】
さらに、スケジューラ１５０が「欲張り」であり、したがって次のパケットの開始時間が前のパケットの終了時間と同じであるものと想定する。したがって、
【００８７】
【数１０】
0004397928.tif 000011
【００８８】
が得られる。
【００８９】
上記式から、
【００９０】
【数１１】
0004397928.tif 000012
【００９１】
が得られる。
【００９２】
セットＢ（ｉ，ｋ）中の要素の数はＮｉ，ｋＢと解釈することができ、これは、
【００９３】
【数１２】
0004397928.tif 000013
【００９４】
を満たす。但し、ρｉはクラスｊの平均レートであり、Ｌｍｉｎはパケットの最小サイズであり、φｍａｘｊはクラスｊの最大の重みである。
【００９５】
ここで、
【００９６】
【数１３】
0004397928.tif 000014
【００９７】
ということが分かる。
【００９８】
結果として、以下：
【００９９】
【数１４】
0004397928.tif 000015
【０１００】
のように遅延を導き出すことができる。
【０１０１】
クラスｉ中のパケットｋの遅延はｄｅｌａｙｋｉ＝Ｄｋｉ−ｔｋｉである。
【０１０２】
クラスｉのキューの最大サイズがｑｌｉｍｉである場合、パケットは、キューサイズＱｌｅｎｉｋがｑｌｉｍｉに等しいときに落とされる。但し、Ｑｌｅｎｉｋは、
【０１０３】
【数１５】
0004397928.tif 000016
【０１０４】
により制限される。
【０１０５】
本発明を好ましい実施の形態の例により説明したが、他の様々な適合および変更を本発明の精神および範囲内で行うことができることを理解されたい。したがって、添付の特許請求項の目的は、本発明の真の精神および範囲内にあるこのような変形および変更をすべて包含することにある。
【図面の簡単な説明】
【０１０６】
【図１】本発明によるネットワーク資源を制御するシステムおよび方法のブロック図である。
【図２】本発明によるキューイング方法のブロック図である。
【図１】
0004397928.tif 000017
【図２】
0004397928.tif 000018