(57)【要約】【課題】多搬送波通信システムに関する分散型順方向リンクスケジューラ【解決手段】本明細書において開示される実施形態は、多搬送波通信システムにおけるパケット送信をスケジューリングすることに関するものである。一実施形態においては、少なくとも１つのプロセッサ及び前記少なくとも１つのプロセッサに動作可能な形で結合された少なくとも１つのメモリを有するマスタースケジューラは、前記少なくとも１つのメモリに格納された命令を実行するように適合化され、前記命令は、複数の搬送波のうちの1つの搬送波からの候補パケットのうちで最高のパケットメトリックを有するパケットを選択することを具備し、優先転送フローは、他の搬送波においてより高いメトリックを有さない。【選択図】        図１０
2009528793.tif 000002
【特許請求の範囲】
【請求項１】
複数の搬送波を用いたパケット送信をスケジューリングするのに適した装置であって、
前記複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択するための手段であって、多搬送波割り当てを有する優先転送フローは前記複数の搬送波のうちの他の搬送波においてより高いパケットメトリックを有しない手段、を具備するパケットをスケジューリングするための手段を具備する、装置。
【請求項２】
パケットをスケジューリングするための前記手段は、
待ち行列内の前記優先転送フローのデータをバッファリングするための手段であって、前記待ち行列内には前記複数の搬送波のうちの他の搬送波が搬送（serve）すべきデータが存在しない手段、をさらに具備する請求項１に記載の装置。
【請求項３】
パケットをスケジューリングするための前記手段は、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新するための手段をさらに具備する請求項１に記載の装置。
【請求項４】
パケットをスケジューリングするための前記手段は、
前記最高のメトリックを有する前記パケットを選択するための手段をさらに具備し、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している請求項１に記載の装置。
【請求項５】
パケットをスケジューリングするための前記手段は、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新するための手段をさらに具備する請求項１に記載の装置。
【請求項６】
パケットをスケジューリングするための前記手段は、
待ち行列内の前記優先転送フローのデータをバッファリングするための手段であって、前記待ち行列内には前記複数の搬送波のうちの他の搬送波が搬送すべきデータが存在しない手段と、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新するための手段と、
前記最高のメトリックを有する前記パケットを選択するための手段であって、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している手段と、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新するための手段と、をさらに具備する請求項１に記載の装置。
【請求項７】
候補パケット送信インスタンスをスケジューリングするための手段をさらに具備し、候補パケット送信インスタンスをスケジューリングするための前記手段は、
一組の前記候補パケット送信インスタンスを生成するための手段と、
１つの候補パケットを組の中から選択するための手段と、
パッキング効率を最高にするための手段と、を具備する請求項１に記載の装置。
【請求項８】
パケットをスケジューリングするための前記手段のシャドールーチンを実行するための手段をさらに具備する請求項７に記載の装置。
【請求項９】
エアインタフェースを通じてパケットを送信するため手段と、
パケットをスケジューリングするための前記手段によって提供されたパケットフォーマットに基づいてパケットを生成するための手段と、をさらに具備する請求項８に記載の装置。
【請求項１０】
分散型アーキテクチャを用いて複数の搬送波を用いたパケット送信をスケジューリングするのに適した装置であって、
前記複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択するための少なくとも１つの手段であって、多搬送波割り当てを有する優先転送フローは前記複数の搬送波のうちの他の搬送波においてより高いパケットメトリックを有さない少なくとも１つの手段、を具備する、順方向リンクを処理するための複数の手段であって、複数のセクターに対応する順方向リンクを処理するための複数の手段と、
データを変調するための手段と、
逆方向リンクを処理するための少なくとも１つの手段と、を具備する、装置。
【請求項１１】
パケットを選択するための前記少なくとも１つの手段は、
待ち行列内の前記優先転送フローのデータをバッファリングするための手段であって、前記待ち行列内には前記複数の搬送波のうちの他の搬送波が搬送すべきデータが存在しない手段と、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新するための手段と、
前記最高のメトリックを有する前記パケットを選択するための手段であって、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している手段と、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新するための手段と、をさらに具備する請求項１０に記載の装置。
【請求項１２】
候補パケット送信インスタンスをスケジューリングするための手段をさらに具備し、候補パケット送信インスタンスをスケジューリングするための前記手段は、
一組の前記候補パケット送信インスタンスを生成するための手段と、
１つの候補パケットを組の中から選択するための手段と、
パッキング効率を最高にするための手段と、を具備する請求項１０に記載の装置。
【請求項１３】
パケットをスケジューリングするための前記手段のシャドールーチンを実行するための手段をさらに具備する請求項１２に記載の装置。
【請求項１４】
エアインタフェースを通じてパケットを送信するため手段と、
パケットをスケジューリングするための前記手段によって提供されたパケットフォーマットに基づいてパケットを生成するための手段と、をさらに具備する請求項１３に記載の装置。
【請求項１５】
順方向リンクスケジューラであって、
少なくとも１つのプロセッサであって、少なくとも１つのセクターに対応する少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに動作可能な形で接続される少なくとも１つのメモリと、を具備するマスタースケジューラであって、前記少なくとも１つのメモリに格納された命令を実行するように適合化されたマスタースケジューラを具備し、前記命令は、複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択することであって、多搬送波割り当てを有する優先転送フローは他の前記搬送波においてより高いパケットメトリックを有さないことを具備する、順方向リンクスケジューラ。
【請求項１６】
前記命令は、待ち行列内の前記優先転送フローのデータをバッファリングすることであって、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しないこと、をさらに具備する請求項１５に記載の順方向リンクスケジューラ。
【請求項１７】
前記命令は、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新することをさらに具備する請求項１５に記載の順方向リンクスケジューラ。
【請求項１８】
前記命令は、
前記最高のメトリックを有する前記パケットを選択することをさらに具備し、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している請求項１５に記載の順方向リンクスケジューラ。
【請求項１９】
前記命令は、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新することをさらに具備する請求項１５に記載の順方向リンクスケジューラ。
【請求項２０】
前記命令は、
待ち行列内の前記優先転送フローのデータをバッファリングすることであって、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しないことと、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新することと、
前記最高のメトリックを有する前記パケットを選択するための手段であって、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している手段と、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新すること、とをさらに具備する請求項１５に記載の順方向リンクスケジューラ。
【請求項２１】
前記マスタースケジューラに結合された少なくとも１つの候補パケット生成器をさらに具備し、前記少なくとも１つの候補パケット生成器は、メモリを具備し、前記少なくとも１つの候補パケット生成器は、一組の前記候補パケット送信インスタンスを生成することと、１つの候補パケットを組から選択することと、パッキング効率を最高にすること、とを具備する前記メモリ内に格納された命令を実行するように適合化される請求項１５に記載の順方向リンクスケジューラ。
【請求項２２】
前記マスタースケジューラに結合されたスレーブスケジューラをさらに具備し、前記スレーブスケジューラは、メモリを具備し、前記スレーブスケジューラは、前記マスタースケジューラのシャドールーチンを実行することを具備する前記メモリ内に格納された命令を実行するように適合化される請求項２１に記載の順方向リンクスケジューラ。
【請求項２３】
前記マスタースケジューラに結合されたメモリを有する少なくとも１つのマスタープロセッサと、前記マスタースケジューラに結合されたメモリを有する少なくとも１つのパケットビルダーと、をさらに具備し、前記少なくとも１つのマスタープロセッサは、エアインタフェースを通じてパケットを送信することを具備する前記メモリ内に格納された命令を実行するように適合化され、前記少なくとも１つのパケットビルダーは、前記マスタースケジューラによって提供されたパケットに基づいてパケットを生成することを具備する前記メモリ内に格納された命令を実行するように適合化される請求項２２に記載の順方向リンクスケジューラ。
【請求項２４】
分散型順方向リンクスケジューラであって、
複数の順方向リンクプロセッサと、
前記複数の順方向リンクプロセッサのうちの少なくとも１つに動作可能な形で接続された少なくとも１つのメモリと、
前記複数の順方向リンクプロセッサのうちの少なくとも１つに動作可能な形で接続されたセルサイトモデムと、
前記セルサイトモデムに動作可能な形で接続された逆方向リンクデジタル信号プロセッサであって、前記マスタースケジューラは、分散型アーキテクチャを有する逆方向リンクデジタル信号プロセッサと、を具備し、前記複数の順方向リンクプロセッサは、複数のセクターに対応し、前記複数の順方向リンクプロセッサのうちの少なくとも１つは、前記少なくとも１つのメモリ内に格納された命令を実行するように適合化されており、
前記命令は、
複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択することであって、多搬送波割り当てを有する優先転送フローは他の前記搬送波においてより高いパケットメトリックを有さないことを具備する、分散型順方向リンクスケジューラ。
【請求項２５】
前記命令は、
待ち行列内の前記優先転送フローのデータをバッファリングすることであって、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しないことと、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新することと、
前記最高のメトリックを有する前記パケットを選択することであって、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達していることと、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新すること、とをさらに具備する請求項２４に記載の分散型順方向リンクスケジューラ。
【請求項２６】
前記複数の順方向リンクプロセッサに結合された少なくとも１つの候補パケット生成器をさらに具備し、前記少なくとも１つの候補パケット生成器は、メモリを具備し、前記少なくとも１つの候補パケット生成器は、一組の前記候補パケット送信インスタンスを生成することと、１つの候補パケットを組から選択することと、パッキング効率を最高にすること、とを具備する前記メモリ内に格納された命令を実行するように適合化される請求項２４に記載の分散型順方向リンクスケジューラ。
【請求項２７】
前記複数の順方向リンクプロセッサに結合されたスレーブスケジューラをさらに具備し、前記スレーブスケジューラは、メモリを具備し、前記スレーブスケジューラは、前記マスタースケジューラのシャドールーチンを実行することを具備する前記メモリ内に格納された命令を実行するように適合化される請求項２６に記載の分散型順方向リンクスケジューラ。
【請求項２８】
前記複数の順方向リンクプロセッサに結合されたメモリを有する少なくとも１つのマスタープロセッサと、前記複数の順方向リンクプロセッサに結合されたメモリを有する少なくとも１つのパケットビルダーと、をさらに具備し、前記少なくとも１つのマスタープロセッサは、エアインタフェースを通じてパケットを送信することを具備する前記メモリ内に格納された命令を実行するように適合化され、前記少なくとも１つのパケットビルダーは、前記マスタースケジューラによって提供されたパケットフォーマットに基づいてパケットを生成することを具備する前記メモリ内に格納された命令を実行するように適合化される請求項２７に記載の分散型順方向リンクスケジューラ。
【請求項２９】
コンピュータによって読み取り可能な媒体であって、
複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択するためのプロセッサによって実行可能な命令を具体化し、多搬送波割り当てを有する優先転送フローは、他の前記搬送波においてより高いパケットメトリックを有さない、コンピュータによって読み取り可能な媒体。
【請求項３０】
待ち行列内の前記優先転送フローのデータをバッファリングするための命令をさらに具備し、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しない請求項２９に記載のコンピュータによって読み取り可能な媒体。
【請求項３１】
前記搬送波によって搬送されたフローに関する待ち行列状態を更新するための命令をさらに具備する請求項２９に記載のコンピュータによって読み取り可能な媒体。
【請求項３２】
前記最高のメトリックを有する前記パケットを選択するための命令をさらに具備し、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している請求項２９に記載のコンピュータによって読み取り可能な媒体。
【請求項３３】
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新するための命令をさらに具備する請求項２９に記載のコンピュータによって読み取り可能な媒体。
【請求項３４】
待ち行列内の前記優先転送フローのデータをバッファリングし、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新し、
前記最高のメトリックを有する前記パケットを選択し、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新するための命令をさらに具備し、前記待ち行列内には前記他の搬送波が搬送すべきデータが存在せず、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している請求項２９に記載のコンピュータによって読み取り可能な媒体。
【請求項３５】
多搬送波通信システムにおけるパケット送信をスケジューリングするのに適した方法であって、
複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択することであって、多搬送波割り当てを有する優先転送フローは、他の前記搬送波においてより高いパケットメトリックを有さないことを具備する、方法。
【請求項３６】
待ち行列内の前記優先転送フローのデータをバッファリングするための命令をさらに具備し、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しない請求項３５に記載の方法。
【請求項３７】
前記搬送波によって搬送されたフローに関する待ち行列状態を更新することをさらに具備する請求項３５に記載の方法。
【請求項３８】
前記最高のメトリックを有する前記パケットを選択することをさらに具備し、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達している請求項３５に記載の方法。
【請求項３９】
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新することをさらに具備する請求項３５に記載の方法。
【請求項４０】
待ち行列内の前記優先転送フローのデータをバッファリングすることであって、前記待ち行列内には他の前記搬送波が搬送すべきデータが存在しないことと、
前記搬送波によって搬送されたフローに関する待ち行列状態を更新することと、
前記最高のメトリックを有する前記パケットを選択することであって、ユーザーは十分なデータを有するか又は前記ユーザーの遅延限度に達していることと、
前記複数の搬送波のうちのその他の搬送波に関する候補パケット送信に関するパケットメトリックを更新すること、とをさらに具備する請求項３５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
３５Ｕ．Ｓ．Ｃ．§１１９及び§１２０に基づく優先権の主張
本特許出願は、"ADAPTIVE DELAY MANAGEMENT"（適応型遅延管理）という題名を有する仮特許出願番号６０／５６８，６５０（出願日：２００４年５月５日）、及び"ADAPTIVE DELAY MANAGEMENT"（適応型遅延管理）という題名を有する仮特許出願番号６０／６２５，６６０（出願日：２００４年１１月４日）に対する優先権を主張する、"METHOD AND APPARATUS FOR ADAPTIVE DELAY MANAGEMENT"（適応型遅延管理に関する方法及び装置）という題名を有する米国特許出願一連番号１１／１２３，４７９（出願日：２００５年５月５日）の一部継続（ＣＩＰ）出願である。
【０００２】
本発明は、一般的には、通信に関するものである。本発明は、より具体的には、適応型遅延管理を用いる無線通信システムにおける送信のスケジューリングに関するものである。
【背景技術】
【０００３】
無線通信システムは、回線交換（又は固定資源割り当て）型技術を用いるシステム処理通信と、パケット交換（又は動的資源割り当て）型技術を用いるシステム処理通信と、を含む。回線交換及びパケット交換は両方とも、高容量能力を有するネットワークにおいて用いることができる。回線交換型通信システムにおいては、送信機と受信機との間に専用通信経路が構築され、送信機と受信機との間のネットワーク資源は、転送開始前は静的であり、従って「回線」を構築しているとみなされる。資源は、転送全体を通じて回線専用の状態であり、メッセージ全体が同じ経路をたどる。パケット交換通信システムにおいては、メッセージはパケットに分割され、各々のパケットは、パケットの到着先であることが意図される行先まで異なるルートをとることができる。パケットは、受信された時点で再コンパイルされて原メッセージが取り出される。パケット交換システムにおいては、メッセージ又はメッセージの断片を表すパケットは、ノード間で個々にルーティングされる。パケットは、適切なルートを通じて行先にルーティングされる。換言すると、同じ２つのホスト間を移動するパケットは、該パケットが単一のメッセージの一部であるときでも同じルートをたどらないことがある。
【０００４】
パケット交換システム（又は共有パケットデータシステム）においては、ボイス・オーバー・インターネット・プロトコル（ＶｏＩＰ）サービスを用いて回線交換音声通信をエミュレートすることができる。ＶｏＩＰは、典型的には、遅延の影響を受けやすいアプリケーション又はサービスであり、従って、パケット引き渡しに対する遅延上の制約を満たすためにサービスの質（ＱｏＳ）メカニズムが用いられる。その他のサービス及び送信の型も、ＱｏＳを保証する上での様々な遅延に関する要求事項又は目標を有する。従って、通信システムにおける送信のスケジューリングに関する適応型遅延管理が必要である。有効なスケジューリングは、通信システムにおける資源の効率的な使用を考慮する。
【発明の開示】
【発明の概要】
【０００５】
本明細書において開示される実施形態は、多搬送波通信システムにおけるパケット送信のスケジューリングに関するものである。
【０００６】
一実施形態においては、順方向リンクスケジューラは、少なくとも１つの入力及び少なくとも１つの出力を有する少なくとも１つの候補パケット生成器と、少なくとも１つの入力及び少なくとも１つの出力を有するマスタースケジューラと、少なくとも１つの出力及び前記マスタースケジューラの前記少なくとも１つの出力に動作可能な形で接続された少なくとも１つの入力を有する少なくとも１つのパケットビルダーと、少なくとも１つの出力及び前記少なくとも１つのパケットビルダーの前記出力に動作可能形で接続された少なくとも１つの入力を有するマスタースプロセッサと、を具備する。
【０００７】
一実施形態においては、マスタースケジューラは、少なくとも１つのプロセッサと、前記少なくとも１つのプロセッサに動作可能な形で接続された少なくとも１つのメモリと、を具備し、前記マスタースケジューラは、前記少なくとも１つのメモリに格納された命令を実行するように適合化され、前記命令は、複数の搬送波のうちの１つの搬送波からの候補パケットの中から最高のパケットメトリックを有するパケットを選択することを具備し、優先転送フローは、他の搬送波においてより高いメトリックを有さない。
【０００８】
本発明のさらなる適用可能範囲が、以下の発明を実施するための最良の形態、請求項、及び図面から明確になるであろう。しかしながら、前記発明を実施するための最良の形態及び具体例は、本発明の好まれる実施形態を示す一方で、本発明の精神及び適用範囲内にある様々な変更及び修正が当業者にとって明確になるため、例示することのみを目的とすることが理解されるべきである。
【０００９】
本発明は、以下に示される発明を実施するための最良の形態、添付された請求項、及び添付図面からより完全に理解されることになるであろう。
【発明を実施するための最良の形態】
【００１０】
本明細書における「例示的」という表現は、「１つの例、事例、又は実例」であることを意味する。本明細書において「例示的」として記述されるいずれの実施形態も、その他の実施形態よりも優先されるか又は有利であるとは必ずしも解釈すべきでない。
【００１１】
サービスの質（ＱｏＳ）に関して異なる要求事項を有するサービス及びアプリケーションをサポートする通信システムの動作は、最適でなくさらに非効率的なことがある。例えば、ＶｏＩＰアプリケーションは、遅延上の要求事項を有する。一方法は、負荷及びカバレッジとは無関係な複数のユーザーに関して等しい遅延上の制約を提供することによって音声をエミュレートする。該手法は、等しい遅延を保証するために資源を割り当て、システム容量を増大させることが可能な最適化を回避するため最適ではない。一実施形態においては、システム容量は、様々なユーザーに関して等しくない遅延を提供することによって増大させることができ、資源は、負荷及びカバレッジの関数として割り当てられる。
【００１２】
以下の説明は、例えば、“ｃｄｍａ２０００高レートパケットデータエアインタフェース仕様”３ＧＰＰ２  Ｃ．Ｓ００２４−Ａ、Ｖｅｒｓｉｏｎ  ２．０、Ｊｕｌｙ  ２００５（本明細書においては“１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様”又は“ＩＳ−８５６Ｒｅｖ．Ａ仕様”と呼ばれる）、“ｃｄｍａ２０００高レートパケットデータエアインタフェース仕様”３ＧＰＰ２  Ｃ．Ｓ００２４−０、Ｖｅｒｓｉｏｎ  ４．０、Ｏｃｔｏｂｅｒ  ２００２（本明細書においては“１ｘＥＶ−ＤＯ Ｒｅｌ．０仕様”又は“ＩＳ−８５６ Ｒｅｌ．０仕様”と呼ばれる）、及び／又はその他の関連仕様における規定に従い、１ｘＥＶ−ＤＯ動作をサポートするシステムの順方向リンク（ＦＬ）に関するスケジューリング方法に関するものである。一実施形態においては、スケジューリング方法は、ＦＬ容量を最大化することを試みる一方で様々なアプリケーションのＱｏＳに関する要求を満たすために様々なマルチユーザーパケット及び短いパケットを利用する。スケジューリング方法は、様々なアプリケーションの優先順位を設定するためのメカニズムも提供する。該優先順位設定は、アプリケーションフローの型、特定のＱｏＳ要求、又は該フローのその他の特徴に基づくことができる。一実施形態においては、フローは、アプリケーションの遅延影響度に基づいてＦＬにおける送信に関してスケジューリングされる。一側面においては、フローは、スループット影響度と均衡化された遅延影響度に基づいて区別される。以下の説明は、１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様に関して実装されるスケジューリング手段及び方法を考慮する一方で、前記スケジューリング手段及び方法は、代替システムに対しても適用可能であり、特に、概念は、ユーザーが例えば１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様において規定されるように所定の部分組の副型と適合可能なシステムに対して適用可能である。
【００１３】
以下の説明においては、“Ｒｅｖ−Ａユーザー”又は“Ｒｅｖ−Ａと適合可能なユーザー”等の用語は、例えば１ｘＥＶ−ＤＯ  Ｒｅｖ．  Ａ仕様において定義されるメディアアクセスチャネル（ＭＡＣ）層及び物理層プロトコル副型をサポートするアクセス端末（ＡＴ）を指すために用いられる。特に、Ｒｅｖ−Ａユーザーは、拡張順方向トラフィックチャネルＭＡＣプロトコルをサポートする。“Ｒｅｌ−０ユーザー”等の用語は、１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様において定義されるＭＡＣ層及び物理層プロトコル副型をサポートするＡＴを指すために用いられるが、例えば１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様において定義されるより新しい副型はサポートすることができない。
【００１４】
符号分割多元接続、ＣＤＭＡ、方式を採用する無線通信システムにおいては、一スケジューリング方法は、時間多重化に基づいて、指定された時間間隔ですべての符号チャネルを各アクセス端末（ＡＴ）に割り当てる。中央通信ノード、例えば基地局（ＢＳ）は、加入者との排他的通信を可能にするために加入者と関連づけられた一意の搬送波周波数又はチャネル符号を実装する。時分割多元接続（ＴＤＭＡ）方式は、物理的接点リレー交換又はパケット交換を用いるランドラインシステムにおいても実装することができる。ＣＤＭＡシステムは、１つ以上の基準、例えば、（１）本明細書においてはＩＳ−９５基準と呼ばれる“デュアルモード広帯域拡散スペクトルセルラーシステムに関するＴＩＡ／ＥＩＡ／ＩＳ−９５−Ｂ移動局−基地局適合性基準”、（２）本明細書においては３ＧＰＰと呼ばれる“第三世代パートナーシッププロジェクト”という名称のコンソーシアムによって提供され、本明細書においてはＷＴ−ＣＤＭＡ基準と呼ばれる文書番号３Ｇ  ＴＳ  ２５．２１１，３Ｇ  ＴＳ  ２５．２１２，３Ｇ  ＴＳ  ２５．２１３，３Ｇ  ＴＳ  ２５．２１４、及び３Ｇ  ＴＳ  ２５．３０２を含む一組の文書において具体化されている基準、（３）本明細書においては３ＧＰＰ２と呼ばれる“第三世代パートナーシッププロジェクト２”という名称のコンソーシアムによって提供された基準、及び以前はＩＳ−２０００ＭＣと呼ばれ、本明細書においてはｃｄｍａ２０００基準と呼ばれるＴＲ−４５．５、（４）その他の幾つかの無線基準、及び／又はその組合せ、をサポートするように設計することができる。
【００１５】
ＣＤＭＡシステムは、地上リンクを通じてのユーザー間における音声通信及びデータ通信を考慮する。ＣＤＭＡシステムにおいては、ユーザー間通信は、１つ以上のＢＳを通じて行われる。無線通信システムにおいては、順方向リンクは、信号がＢＳからＡＴに移動するチャネルを意味し、逆方向リンクは、信号がＡＴからＢＳに移動するチャネルを意味する。逆方向リンクにおいてＢＳにデータを送信することによって、１つのＡＴにおける第１のユーザーは、第２のＡＴにおける第２のユーザーと通信する。ＢＳは、第１のＡＴからデータを受信し、第２のＡＴと交信するＢＳにデータをルーティングする。いずれの場合においても、第２のＡＴと交信するＢＳは、順方向リンクにおいてデータを送信する。ＡＴは、第２のＡＴと通信する代わりに、交信ＢＳとの接続を通じて地上インターネットと通信することもできる。例えばＩＳ−９５基準に準拠する無線通信においては、順方向リンク信号及び逆方向リンク信号は、独立（ｄｉｓｊｏｉｎｔ）周波数帯域内において送信される。
【００１６】
図１Ａは、幾つかのユーザーをサポートする通信システム１００の実施形態を示し、本明細書において開示される少なくとも幾つか側面及び実施形態を実装することができる。様々なアルゴリズム及び方法のうちのいずれかを、システム１００における送信をスケジューリングするために用いることができる。システム１００は、幾つかのセル１０２        Ａ乃至１０２Ｇに関する通信を提供し、前記セルの各々は、対応するＢＳ１０４Ａ乃至１０４Ｇによってそれぞれサービスが提供される。無線データ送信要求の増大及び無線通信技術を介して利用可能なサービスの拡大によって特定のデータサービスが開発されるようになっている。１つの該サービスは、高データレート（ＨＤＲ）と呼ばれる。“ＨＤＲ仕様”と呼ばれる“ＥＩＡ／ＴＩＡ−ＩＳ８５６ｃｄｍａ２０００高レートパケットデータエアインタフェース仕様”において典型的ＨＤＲサービスが提案されている。ＨＤＲサービスは、一般的には、無線通信システムにおいてデータパケットを送信する効率的な方法を提供する音声通信システムへのオーバーレイである。送信されるデータ量が増大し、送信数が増加するのに応じて、無線送信に関して利用可能な限られた帯域幅が不足資源になってきている。
【００１７】
図１Ｂは、エアインタフェース１２４を介してＡＴ  １２６と通信するアクセスネットワーク（ＡＮ）１２２を有する通信システム１２０に関するアーキテクチャ基準モデルを示す。一実施形態においては、システム１０は、例えばＨＤＲ基準、ＩＳ−８５６  Ｒｅｌ．０又はＩＳ−８５６  Ｒｅｖ．  Ａ仕様において規定されるようなＨＤＲオーバーレイシステムを有するＣＤＭＡシステムである。ＡＮ  １２２は、エアインタフェース１２４を通じて、ＡＴ１２６、及びシステム１２０内のその他のＡＴ（明示されない）と通信する。
【００１８】
ＡＮ  １２２は、複数のセクターを含み、各セクターは、少なくとも１つのチャネルを提供する。チャネルは、所定の周波数割り当て内におけるＡＮ１２２とＡＴとの間での送信に関する通信リンクの組であると定義される。チャネルは、ＡＮ１２２からＡＴ１２６への送信に関する順方向リンク（ＦＬ）と、ＡＴ１２６からＡＮ１２２への送信に関する逆方向リンク（ＲＬ）と、を含むことができる。
【００１９】
データ送信に関して、ＡＮ１２２は、ＡＴ１２６からデータ要求を受信する。データ要求は、データが送信されるべきデータレート、送信されるデータパケットの長さ、及びデータの送信元になるセクターを指定する。ＡＴ１２６は、ＡＮ１２２とＡＴ１２６との間のチャネルの品質に基づいてデータレートを決定する。一実施形態においては、チャネルの品質は、搬送波対干渉比（Ｃ／Ｉ）によって決定される。代替実施形態は、チャネルの品質に対応するその他のメトリックを用いることができる。ＡＴ１２６は、ＤＲＣチャネルと呼ばれる特定のチャネルを介してデータレート制御（ＤＲＣ）メッセージを送信することによってデータ送信要求を提供する。ＤＲＣメッセージは、データレート部分と、セクター部分と、を含む。データレート部分は、ＡＮ１２２がデータを送信するための要求されるデータレートを示し、セクター部分は、ＡＮ１２２がデータを送信するときの送信セクターを示す。データレート及びセクター情報の両方とも、データ送信を処理するために典型的に要求される。データレート部分は、ＤＲＣ値と呼ばれ、セクター部分は、ＤＲＣカバーと呼ばれる。ＤＲＣ値は、エアインタフェース１２４を介してＡＮ１２２に送信されるメッセージである。一実施形態においては、各ＤＲＣ値は、予め決められたＤＲＣ値割り当てに従った関連するパケット長を有するデータレート（例えば、単位がキロビット／秒）に対応する。割り当ては、ヌルデータレートを指定するＤＲＣ値を含む。実際には、ヌルデータレートは、ＡＴ１２６がデータを受信できないことをＡＮ１２２に示す。例えば、一状況においては、チャネルの品質は、ＡＴ１２６がデータを正確に受信する上では不十分である。
【００２０】
動作中において、ＡＴ１２６は、チャネルの品質を連続的にモニタリングし、ＡＴ１２６が次のデータパケット送信を受信できるデータレートを計算する。次に、ＡＴ１２６は、対応するＤＲＣ値を生成し、ＤＲＣ値は、データ送信を要求するためにＡＮ１２２に送信される。典型的には、データ送信はパケットに分割されることに注目すること。１つのデータパケットを送信するために要する時間は、適用されるデータレートの関数である。
【００２１】
ＤＲＣ信号は、各待ち行列と関連づけられたＡＴの各々に関する情報を消費する（又は送信されたデータを受信する）ための瞬間レートを決定するためにチャネルスケジューラが用いる情報も提供する。一実施形態により、ＡＴから送信されたＤＲＣ信号は、ＡＴが複数の有効なデータレートのうちのいずれか１つにおいてデータを受信できることを示す。
【００２２】
ＨＤＲ送信をサポートし、複数のユーザーへの送信をスケジューリングするのに適した通信システムの一例が図２に示される。図２は、以下において詳述されており、具体的には、ＢＳ８２０及び基地局コントローラ（ＢＳＣ）８１０は、パケットネットワークインタフェース８０６とインタフェースする。ＢＳＣ８１０は、システム８００における送信に関するスケジューリング方法を実装するためのチャネルスケジューラ８１２を含む。チャネルスケジューラ８１２は、（直近において受信されたＤＲＣ信号において示された）ＡＴの関連づけられた瞬間的データ受信レートに基づいて特定のＡＴにデータが送信されるサービス間隔の長さを決定する。サービス間隔は、時間的に隣接することができないが、ｎスロットごとに１回生じることができる。一実施形態により、パケットの第１の部分は、第１のスロット中に第１の時間において送信され、第２の部分は、４スロット後に後続時間において送信される。さらに、パケットの後続部分は、同様の４スロットの広がりを有する、例えば互いに４スロット離れている、複数のスロットにおいて送信される。一実施形態により、瞬間的データ受信レートＲｉは、特定のデータ待ち行列と関連づけられたサービス間隔長さＬｉを決定する。
【００２３】
さらに、チャネルスケジューラ８１２は、送信に関する特定のデータ待ち行列を選択する。次に、送信されるべき関連データ量がデータ待ち行列８３０から取り出され、データ待ち行列８３０と関連づけられたＡＴへの送信のためにチャネル素子８２６に提供される。後述されるように、チャネルスケジューラ８１２は、データを提供するための待ち行列を選択し、データは、各々の待ち行列と関連づけられた重みを含む情報を用いて次のサービス間隔で送信される。次に、送信された待ち行列と関連づけられた重みが更新される。
【００２４】
ＢＳＣ８１０は、パケットネットワークインタフェース８０６、公衆交換電話網（ＰＳＴＮ）８０８、及び通信システム内のＢＳとインタフェースする（図２においては、説明を単純化するために１つのＢＳ８２０のみが示される）。ＢＳＣ８１０は、通信システム内のＡＴとパケットネットワークインタフェース８０６及びＰＳＴＮ８０８に接続されたその他のユーザーとの間における通信を調整する。ＰＳＴＮ８０８は、標準電話網（図２においては明示されていない）を通じてユーザーとインタフェースする。
【００２５】
ＢＳＣ８１０は、多くのセレクタ素子８１６を含むことができるが、図２においては単純化のために１つだけが示される。各セレクタ素子８１６は、１つ以上のＢＳ８２０と１つのＡＴ（示されていない）との間における通信を制御するために割り当てられる。セレクタ送信８１６が所定のＡＴに割り当てられていない場合は、ＡＴをページングする必要があることが呼制御プロセッサ８１８に連絡される。呼制御プロセッサ８１８は、ＡＴをページングするようにＢＳ８２０に指示する。
【００２６】
データソース８０２は、所定のＡＴに送信されるべきある量のデータを含む。データソース８０２は、パケットネットワークインタフェース８０６にデータを提供する。パケットネットワークインタフェース８０６は、データを受信してセレクタ素子８１６にデータをルーティングする。次に、セレクタ素子８１６は、目標ＡＴと通信中の各ＢＳ８２０にデータを送信する。典型的実施形態においては、各ＢＳ８２０は、ＡＴに送信されるべきデータを格納するデータ待ち行列８３０を維持する。
【００２７】
データは、データパケットにおいてデータ待ち行列８３０からチャネル素子８２６に送信される。典型的実施形態においては、順方向リンクにおける“データパケット”は、例えば最大の１０２４ビット及び予め決められた“タイムスロット”（例えば、約１．６６７ミリ秒）内において行先ＡＴに送信されるべきある量のデータであることができるある量のデータを意味する。各データパケットに関して、チャネル素子８２６は、幾つかの制御フィールドを挿入する。典型的実施形態においては、チャネル素子８２６は、データパケット及び制御フィールドの巡回冗長検査（ＣＲＣ）符号化を行い、一組の符号テールビットを挿入する。データパケット、制御フィールド、ＣＲＣパリティビット、及び符号テールビットは、フォーマット化されたパケットを具備する。典型的実施形態においては、チャネル素子８２６は、フォーマット化されたパケットを符号化し、符号化されたパケット内のシンボルをインターリービング（又は順序を再設定）する。典型的実施形態においては、インターリービングされたパケットは、ウォルシュ符号でカバーされ、短いＰＮＩ及びＰＮＱ符号で拡散される。拡散されたデータは、ＲＦユニット８２８に提供され、ＲＦユニット８２８は、信号を直交変調、フィルタリング、及び増幅する。順方向リンク信号は、アンテナを通じてオーバーザエアで順方向リンクに送信される。
【００２８】
ＡＴにおいて、順方向リンク信号がアンテナによって受信されて受信機にルーティングされる。受信機は、信号をフィルタリング、増幅、直交復調、及び量子化する。デジタル化された信号は、復調器（ＤＥＭＯＤ）に提供され、復調器（ＤＥＭＯＤ）において、短いＰＮ１符号及びＰＮＱ符号によって逆拡散され、ウォルシュカバーでデカバーされる。復調されたデータは、ＢＳ８２０において実施された信号処理関数の逆、具体的には、デインターリービング、復号、及びＣＲＣ検査関数、を実施する復号器に提供される。復号されたデータは、データシンク８０４に提供される。
【００２９】
ハードウェアは、上述されるように、順方向リンクを通じてのデータ、メッセージ、音声、映像、及びその他の通信の可変レート送信をサポートする。データ待ち行列８３０から送信されるデータのレートは、信号強度及びＡＴにおける雑音環境の変化に対処するために変動する。各ＡＴは、好ましいことに、各タイムスロットにおいてＤＲＣ信号を関連づけられたＢＳ８２０に送信する。ＤＲＣ信号は、ＡＴのアイデンティティ及びＡＴがその関連づけられたデータ待ち行列からデータを受信するレートを含む情報をＢＳ８２０に提供する。従って、ＡＴにおける回路は、ＤＲＣ信号において送信されるレート情報を決定するために信号強度を測定し、ＡＴにおける雑音環境を推定する。
【００３０】
各ＡＴによって送信されたＤＲＣ信号は、逆方向リンクチャネルを通じて移動し、ＲＦユニット８２８に結合された受信アンテナを通じてＢＳ８２０において受信される。典型的実施形態においては、ＤＲＣ情報がチャネル素子８２６において復調され、ＢＳＣ８１０内に配置されたチャネルスケジューラ８１２又はＢＳ８２０内に配置されたチャネルスケジューラ８３２に提供される。一実施形態においては、チャネルスケジューラ８３２は、ＢＳ８２０内に配置することができる。代替実施形態においては、チャネルスケジューラ８１２は、ＢＳＣ８１０内に配置することができ、ＢＳＣコントローラ８１０内のセレク素子８１６に接続する。
【００３１】
回線交換システムにおける送信スケジューリングは、比例的公平アルゴリズムを含むことができ、優先度関数が各ユーザーに関して定義される。比例的公平アルゴリズムの一例が以下において示される。優先度関数は、所定のユーザーに関する要求されたデータレート、典型的にはユーザーに対する順方向リンクチャネル品質の関数、及びユーザーに関するスループットを考慮に入れることができる。容量は、スループットと比較して高い要求データレートを有するユーザーに最初にサービングすることによって均衡化される。
【００３２】
一実施形態による、パケット交換システムにおける送信スケジューリングは、容量とユーザー遅延を均衡化させる。アプリケーションフローは、ネットワークを通じて送信される独立した内蔵メッセージであるデータグラムとして送信される。データグラムの到着、到着時間、及びコンテンツは、一般的には保証されない。同じアプリケーションフローと関連づけられたデータグラムを、異なるルートで同じユーザーに送信することができる。データグラムは、受信機において再アセンブルされる。パケット交換システムにおけるエンドツーエンド遅延は固定されておらず、従って、スケジューラは、この遅延差を用いること及び様々なユーザーに関する遅延を調整して容量を増大させることができる。例えば、スケジューラは、低い遅延限度及び／又は遅延変動限度を有するデータを要求中のユーザーによって経験される遅延を短くすることができる。該アプリケーションは、（限定されることなしに）ＶｏＩＰ、映像、等を含む。送信は、ＱｏＳに関する特定の要求を有することができる。例えば、ＶｏＩＰ型通信は、定義されたレーテンシーを有する状態で、又は許容される遅延期間内にパケットが到着することを要求する。従って、より低いレーテンシーが要求されるか又はその他のサービス等級（ＧｏＳ）仕様を有する通信又はアプリケーションの優先順位を設定することが望ましい。マルチメディア会議、映像ストリーミング、ウェブブラウジング、及びファイル転送プロトコル（ＦＴＰ）は、各々が、特定のＧｏＳ要求を有する。
【００３３】
優先度分類方式を実装するために、各フローに優先度関数が割り当てられる。一実施形態においては、パケット交換スケジューラに関する優先度関数（ＰＦ）を次のように与えることができる。
【００３４】
ＰＦ＝ｆ（ｄｅｌａｙ）                          （１）
ここで、ｆ（  ）は関数であり、ＰＦは、所定のユーザー又はユーザーに関する所定のアプリケーションの遅延上の要求事項に基づいて決定される。ＰＦは、各待ち行列内の各データグラムに関して計算される。様々なＰＦが比較され、より高い優先度のフローインスタンスが識別される。パケット交換通信は、所定の通信のエンドツーエンド遅延が固定されないため、適応型遅延管理をスケジューリングが組み入れることを可能にする。このことは、エンドツーエンド遅延が固定される回線交換通信と対照的である。
【００３５】
以下の説明では、例えばＩＳ−８５６仕様において説明される高レートパケットデータ（ＨＲＰＤ）サービスをサポートするｃｄｍａ２０００システムを考慮する。このシステムは、例として用いられる。本明細書において開示される実施形態は、ユーザーがスケジューリング方法に従ってサービスに関して選択されるその他のシステムに対して適用可能である。
【００３６】
ＨＲＰＤシステムにおいては、エアインタフェースは、最大で４つの並行するアプリケーションストリームをサポートすることができる。第１のストリームは、シグナリング情報を搬送し、その他の３つは、異なるＱｏＳ要求を有するアプリケーション又はその他のアプリケーションを搬送するために用いることができる。
【００３７】
上述されるように、ＣＤＭＡ２０００（又はｃｄｍａ２０００）は、ＩＴＵによって承認された、ＩＭＴ−２０００（３Ｇ）基準系統を表し、ＣＤＭＡ２０００  １Ｘ及びＣＤＭＡ２０００  １ｘＥＶ−ＤＯ技術を含む。これらの基準は、無線サービス及び高速データサービスの増大する需要を満たすための増大されたネットワーク容量を提供する。ＣＤＭＡ２０００  １Ｘは、世界で初めて商業導入された３Ｇ技術であった（２０００年１０月）。ＣＤＭＡ２０００  １ｘＥＶ−ＤＯは、２００１年にストックホルム会議においてＩＭＴ−２０００技術として認められた。パケットデータサービス用に最適化されたＣＤＭＡ２０００  １ｘＥＶ−ＤＯは、１つの１．２５ＭＨｚＣＤＭＡ搬送波内において２．４Ｍｂｐｓのピークデータレートを提供する。このことは、既存の一揃えのインターネットプロトコル（ＩＰ）を活用し、従って、すべての人気のあるオペレーティングシステム及びソフトウェアアプリケーションをサポートする。１ｘＥＶ−ＤＯは、「常にオンの」ユーザー経験を提供し、このため、ユーザーはあらゆる時間に、あらゆる場所において、インターネット及びコーポレートイントラネットから自由に情報を送信及び受信することができる。さらに、１ｘＥＶ−ＤＯは、バースト性のデータアプリケーションがあらゆるデバイスにおいて実行するのを可能にするソリューションである。
【００３８】
単一ユーザーの場合は、サービング時間のうちの１００％を１人のユーザー専用にすることができる。複数のユーザーにサービングすることによってパケットスケジューリングを通じてマルチユーザーダイバーシティ利得が達成される。１ｘＥＶ−ＤＯ順方向リンクの１つの特長は、マルチユーザーダイバーシティを利用するスケジューリング方法の使用がデータスループットの向上を可能にすることである。マルチユーザーダイバーシティの下で、スケジューラは、モバイル（又はＡＴ）が高い信号レベルを経験しているときにタイムスロット中及び／又は特定の周波数搬送波を用いたこれらのモバイルへの送信をスケジューリングすることによってチャネル状態の変動を利用することができる。
【００３９】
しかしながら、先行技術において存在するスケジューリング方式のうちの多くを用いることについては問題が存在する。非常に多くのユーザーが存在する状態で非常に多くの副搬送波に関して最適なスケジューリングを行うことは計算上非実際的である。先行技術においては、順方向リンクスケジューラは、単一のエンティティに常駐する単一の搬送波スケジューラであった。本方法及び装置は、分散型ＦＬスケジューラを用いてパケットを送信する。さらに、ＥＶ−ＤＯ  Ｒｅｖ．Ａ単搬送波を多搬送波アプリケーションに拡大する。
【００４０】
以下の用語集は、後述される一実施形態について理解する際に明確化することを目的とするものである。以下の用語集は、包括的であることを意図するものではなく、さらに本発明を以下の用語集に限定することを意図するものでもなく、適応型重み付きスケジューリングアルゴリズムをサポートする通信システムの一実施形態に関して明確化すること及び理解することを目的として提供されるものである。
【００４１】
用語集
アクセスネットワーク（ＡＮ）−セルラーネットワーク及びパケット交換データネットワーク（典型的にはインターネット）とＡＴとの間におけるデータ接続性を提供するネットワーク装置。ＨＲＰＤシステム内のＡＴは、セルラー通信システムにおける基地局に相当する。
【００４２】
アクセス端末（ＡＴ）−データ接続性をユーザーに提供するデバイス。ＨＲＰＤシステム内のＡＴは、セルラー通信システムにおける移動局に対応する。ＡＴは、ラップトップパソコン等の計算デバイスに接続することができ、又はパーソナルデジタルアシスタント（ＰＤＡ）等の内蔵デーデバイスであることができる。ＡＴは、様々な名称、例えば、アクセスユニット、アクセスノード、加入者ユニット、移動局、モバイルデバイス、モバイルユニット、携帯電話、モバイル、遠隔局、遠隔端末、遠隔ユニット、ユーザーデバイス、ユーザー装置、ハンドヘルドデバイス等、を有することができる。
【００４３】
アプリケーションフロー−所定のアプリケーションストリームに関するソースからＡＴまでの指定された送信経路。各アプリケーションフローは、ソース、行先、トラフィックプロフィール及びサービス質プロフィールによって識別される。
【００４４】
アプリケーションストリーム−アプリケーションに対応するデータ通信。ほとんどのアプリケーションストリームは、指定されたサービスの質に関する要求事項を有する。
【００４５】
自動再送要求（ＡＲＱ）−送信機がイベントの発生又は非発生に基づいてデータの再送信を開始するメカニズム。
【００４６】
平均データレート−所定のアプリケーションフローに関する経時での平均入力データレート。
【００４７】
バースト性（σ）−アプリケーションフロー内のパケットのバースト性又は密度及び時間的関係の尺度。
【００４８】
ベストエフォート（ＢＥ）−一般的にオーバーザエアで受信すべき相対的に大量のデータを有するアプリケーションフローであるが、トラフィックの性質上、相対的に大きな遅延を許容可能であるが、データ損失率を極端に小さくすべきである。
【００４９】
データレート制御（ＤＲＣ）−ＡＴが要求されるデータレートをＡＮに送信するためのメカニズム。
【００５０】
欠陥ビット（ｄｅｆｂｉｔｓ）−欠陥パケットに対応するビット数。
【００５１】
遅延限度−ＡＮからＡＴへのデータパケットの送信に関して許容される規定時間（遅延限度）。
【００５２】
優先転送（ＥＦ）−典型的にはインターネットからＡＮに到着する少量のトラフィックを有するが、前記トラフィックの性質上合理的なデータ損失率で一定の相対的に小さい遅延限度内においてデータパケットがユーザーに引き渡されるべきであるアプリケーションフロー。
【００５３】
順方向リンク（ＦＬ）−ＡＮからＡＴへの送信エアリンク。
【００５４】
ヘッドオブライン（ＨＯＬ）パケット−待ち行列内の最初のパケット。
【００５５】
高レートパケットデータ（ＨＲＰＤ）−高データレートでパケットデータ通信を送信するデータサービス。高データレート（ＨＤＲ）とも呼ばれ、ＩＳ−８５６仕様において規定される。
【００５６】
ジッター−受信された連続するパケット間における時間的ゆらぎ。
【００５７】
ジッター限度−所定のアプリケーションフローに関するジッターの限度
モーション・ピクチャーズ・エキスパーツ・グループ（ＭＰＥＧ）−マルチメディア素材送信用プロトコル。
【００５８】
比例的公平（ＰＦ）アルゴリズム−各ＡＴに関して要求されるデータレートとスループットの比として計算される選択係数に従ってデータ通信がスケジューリングされるスケジューリングアルゴリズム。
【００５９】
サービス質（ＱｏＳ）−パケットデータ通信の送信に関連する要求事項であり、限定されることなしに、遅延、要求レート、及びジッターを含む。
【００６０】
逆方向リンク（ＲＬ）−ＡＴからＡＮへの送信エアリンク。
【００６１】
送信待ち行列−所定のＢＴＳに関するアプリケーションフローを格納する送信待ち行列。
【００６２】
多くの無線通信では、異なるホップ単位転送動作（ＰＨＢ）及び異なるルーティングをパケットデータの処理に関して利用するためにＩＰを用いる。一般的には、インターネットは、相互に動作するためにＩＰに依存する様々なリンク層技術によって構築された多数のネットワークから成る。ＩＰは、ネットワーク負荷の増大に伴って増大するパケット損失及び遅延が生じる無接続ネットワーク層サービスを提供する。基本的なＩＰ引き渡しモデルは、ＢＥと呼ばれる。しかしながら、幾つかのアプリケーションは、単純なＢＥサービスよりも優れたサービスを要求することがある。例えば、マルチメディアアプリケーションは、固定された帯域幅、低遅延及びジッターがほとんどないことを規定することができる。他の優先度型は、スループットレベルを保証する保証転送（ＡＦ）と呼ばれる転送動作である。
【００６３】
ＱｏＳ管理には様々な側面が存在する。ＱｏＳ管理に関する幾つかの考慮事項は、帯域幅の割り当て、及び、ブロードキャストネットワークとも呼ばれる共有メディア、例えばイーサネット（登録商標）ネットワーク又は無線ローカルエリアネットワーク（ＬＡＮ）等、を通じての保証された帯域幅である。ラップトップコンピュータ及びその他の計算デバイス内に無線能力を含める要求がますます強くなってきている一方で、無線ネットワークは、帯域幅が限られており、従って容量の保全及び最適化が１つの考慮事項になる。
【００６４】
図３は、ＧｏＳ及びＱｏＳに関する要求事項に基づいて送信の優先順位を設定するスケジューリング方法を示す。ＡＮにおいて、送信用データが、着信アプリケーションフローに対応するデータ待ち行列を格納するように適合化されたメモリ記憶ユニットに格納される。待ち行列は、アプリケーションフローの各インスタンスに関して格納される。
【００６５】
フロー及び待ち行列
フローは、ユーザーに向けられたデータストリームを意味する。フローのソースは、１つ以上のユーザーアプリケーション、例えば、限定されることなしに、ファイルダウンロード（ｆｔｐ）、ウェブサーフィン（ｈｔｔｐ）、オンラインゲームプレイ、ＶｏＩＰ、又は１ｘＥＶ−ＤＯシステムを試験するために用いられる試験アプリケーションによって生成されたデータストリーム、であることができる。フロー、例えばシグナリングフローは、１ｘＥＶ−ＤＯシステムの稼働を維持し、ユーザーセッションが適切に維持されるようにするために、１ｘＥＶ−ＤＯシステム自体によって生成することもできる。各フローは、一組の品質保証（ＱｏＳ）要求事項、例えば目標スループット及び遅延限度、を有することができる。
【００６６】
ユーザーは、異なるＱｏＳ要求事項を有する複数の同時並行フローを有することができる。各フローは、１つのアプリケーション、例えばＶｏＩＰ、ｆｔｐ、シグナリング、によって生成することができるか、又はＢＳＣによって単一のフローに統合される複数のアプリケーションによって生成することができる。ＢＳＣがこのようにしてフローを１つに統合する場合は、統合されたフローは、スケジューラにとっては、明確に定義されたＱｏＳ要求事項を有する単一のフローのようにみえる。スケジューラは、統合されたフロー内の異なるアプリケーションによって生成されたデータを区別することができない。
【００６７】
各フローは、最初の送信に関してデータを保持する少なくとも１つの待ち行列（前記フローのＦＴｘ待ち行列と呼ばれる）を有し、再送信のための追加待ち行列、例えば無線リンクプロトコル（ＲＬＰ）再送信待ち行列（フローのＲＴｘ待ち行列）、及び／又はＭＡＣ層再送信待ち行列（遅延されたＡＲＱ待ち行列又はＤＡＲＱ待ち行列）等、を有することができる。
【００６８】
一実施形態においては、アプリケーションフローは、インスタンスに分割することができ、各インスタンスは、１オクテットのデータである。各待ち行列内のすべてのオクテットは、明確に定義されたタイムスタンプを有し、前記タイムスタンプによって、スケジューラは、オクテットによって被った現在の遅延を決定することができる。さらに、タイムスタンプは、（カプセル化された）データグラム等のデータのバーストに割り当てられ、データバーストの各オクテットは同じタイムスタンプを有することを示す。個々のデータグラムは、複数のアプリケーションレベルフレームを搬送することができ、前記複数のアプリケーションレベルフレームは、異なる時点においてアプリケーションによって生成しておくことができる。アプリケーションフレームタイムスタンプはスケジューラに知られていないと仮定される。データグラムによって搬送されるアプリケーションフレームのうちのいずれかを受信端アプリケーションによって構文解析できるようになる前に完全なデータグラムがユーザーによって成功裏に受信される必要があるため、上記の仮定は適切である。
【００６９】
従って、アプリケーションフローは、関連づけられた複数の待ち行列を有することができ、しばしば有することになる。各待ち行列は、関連づけられたＱｏＳ及び／又はＧｏＳの優先度型によって定義された送信及び受信に関する要求事項を有する。例えば、優先度型は、エンドツーエンド遅延要求事項又はその他の何らかの品質判定基準に基づくことができる。所定の送信は、複数のＧｏＳ優先度型のうちの１つに属することができる点に注目すること。例えば、幾つかのサービスは、データパケットを個々に送信し、のちに連続性を失うことなしに受信機において再結合することを可能にし、例えばＢＥ優先型である。対照的に、リアルタイムの経験をユーザーに与えるように設計されたアプリケーション、例えばＶｏＩＰ、は、より高い優先度型を有しており、ＥＦ優先度型と呼ばれる。ＥＦ優先度型は、遅延限度及び遅延変動に関する限度を有するアプリケーションを含む。現在の例においては、スケジューラは、ＥＦ通信の優先順位を設定する。ＱｏＳ又はＧｏＳ優先度型は、ＱｏＳクラスと呼ぶこともできる。さらに、各待ち行列は、関連づけられた影響度を有する。例えば、ＥＦアプリケーションフローは、典型的には遅延の影響を受けやすく、ＥＦアプリケーションフローの送信は満たすべき遅延上の要求を有することを意味する。多くの場合において、遅延上の要求が満たされない場合は、データが捨てられて送信されない。対照的に、ＢＥアプリケーションフローは、典型的にスループットの影響を受けやすく、ＢＥアプリケーションフローの送信は目標スループット上の要求事項を有するがＥＦアプリケーションフローの厳しい遅延上の要求事項は必ずしも有さないことを意味する。
【００７０】
図３は、一実施形態による適応型遅延管理を実装するスケジューリング方法２００を示す。ＡＮ内において、スケジューラは、高レートパケットデータ送信を複数のユーザーに提供するスケジューリング方法を実装する。スケジューラは、データ待ち行列を検査してデータに関するＧｏＳ型を決定する。判断ステップ２０２において、いずれかのデータが所定のＧｏＳ優先度型、例えばＢＥよりも具体的な要求事項を定義する優先度型、である場合は、プロセスはステップ２０４に進み、待ち行列内において優先度が最高の型の最も古いデータを見つけ出す。本明細書において用いられるより高い優先度とは、より厳しい仕様によって定義されるＧｏＳ優先度型を意味する。例えば、１つの優先度型は、遅延限度を指定することができ、他の優先度型は、ジッター限度を指定することができる。この場合は、遅延限度を指定する優先度型は、より高い優先度とみなされ、従って最初に考慮される。
【００７１】
本実施形態により、スケジューラは、最初に、遅延上の要求事項に基づいて送信のためにビットの順序を設定してパケットに入れる。高優先度データがスケジューリングされた時点で、残りのパケットをスケジューリングするために他の方法を適用することができる。
【００７２】
例えば、ＥＦデータが待ち行列内に存在するときは、スケジューラは、ＥＦデータを用いて送信のためにパケットを形成することを開始する。ＥＦデータは、ステップ２０４において、待ち行列内のデータが古い順に選択される。一実施形態においては、データが待ち行列に入れられるのに応じて前記データはタイムスタンプを受信する。スケジューラは、最も早いタイムスタンプを有するＥＦデータを見つけ出し、該ＥＦデータを最初にパケットに入れる。次に、スケジューラは、ステップ２０６において、待ち行列における古い順にＥＦデータをパケットに入れ続ける。すべてのＥＦデータが送信のためにパケット内に入れられた時点で、スケジューラは、残りのデータに関して他の方法を適用する。本実施形態においては、スケジューラは、ステップ２０８において、ＢＥデータであることができる残りのデータに対して比例的公平方法を適用する。次に、ステップ２１０において、比例的公平方法に従ってＢＥデータがパケットに入れられる。
【００７３】
チャネル状態が向上するのに応じて、ユーザーはより高いレートでデータを要求し、遅延限度を引き下げる効果を有する。従って、スケジューラがＥＦデータの優先順位を設定するときでさえも、遅延限度は、チャネル状態の関数であることができる。
【００７４】
ＢＥデータを送信するため、スケジューラは、スループットが最高になるようにパケットを選択する。スループットは、一般的には以下のように計算される。
【００７５】
スループット＝（パケット当たりのビット数）／（パケット当たりのスロット数）                                          （２）
一実施形態により、ＰＦは、以下のように与えることができる。
【００７６】
ＰＦ＝ｆ（パケットの古さ）＊ｇ（チャネル状態）＊ｈ（セルローディング）                                                （３）
上式は、送信をスケジューリングする際に、パケットの古さに加えてチャネル状態及びセルのローディングを考慮する。該計算は、ＥＦデータ又はＢＥデータのスケジューリングに関して用いることができる。
【００７７】
再度図２に関して、一実施形態においては、チャネルスケジューラ８３２は、待ち行列の大きさとも呼ばれる、各ＡＴに関する待ち行列内のデータ量を示す情報をデータ待ち行列８３０から受信する。次に、チャネルスケジューラ８３２は、ＢＳ８２０によってサービスが提供された各々のＡＴに関するＤＲＣ情報及び待ち行列の大きさに基づいてスケジューリングを行う。代替実施形態において用いられるスケジューリング方法に関して待ち行列の大きさが要求される場合は、チャネルスケジューラ８１２は、待ち行列大きさ情報をセレクタ素子８１６から受信することができる。
【００７８】
１つ以上のユーザーへのパケット送信中においては、ユーザーは、送信されたパケットの一部分を含むＡＣＫ信号を各タイムスロット後に送信する。各ユーザーによって送信されたＡＣＫ信号は、逆方向リンクチャネルを通じて移動し、ＲＦユニット８２８に結合された受信アンテナを通じてＢＳ８２０において受信される。典型的実施形態においては、ＡＣＫ情報は、チャネル素子８２６において復調され、ＢＳＣ８１０に配置されたチャネルスケジューラ８１２に対して又はＢＳ８２０に配置されたチャネルスケジューラ８３２に対して提供される。一実施形態においては、チャネルスケジューラ８３２は、ＢＳ８２０内に配置される。代替実施形態においては、チャネルスケジューラ８１２は、ＢＳ８１０内に配置され、ＢＳＣ８１０内のセレクタ素子８１６に接続する。
【００７９】
本発明の実施形態は、可変レート送信をサポートすることができるその他のハードウェアアーキテクチャに対して適用可能である。例えば、本発明の実施形態は、逆方向リンクにおける可変レート送信を網羅するように容易に拡大することができる。一実施形態においては、ＢＳ８２０においてＡＴからのＤＲＣ信号に基づいてデータを受信するレートを決定する代わりに、ＢＳ８２０は、ＡＴから受信された信号の強度を測定し、雑音環境を推定してＡＴからデータを受信するレートを決定する。次に、ＢＳ８２０は、ＡＴから逆方向リンクでデータを送信すべきレートを各々の関連ＡＴに送信する。次に、ＢＳ８２０は、本明細書において順方向リンクに関して説明されるのと同様の方法で、逆方向リンクでの異なるデータレートに基づいて逆方向リンクにおける送信をスケジューリングすることができる。
【００８０】
さらに、上述される実施形態のＢＳ８２０は、ＡＴのうちの選択された１つのＡＴ又は選択された複数のＡＴに送信し、ＣＤＭＡ方式を用いるＢＳ８２０と関連づけられた残りのＡＴを除外する。いずれかの特定の時点において、ＢＳ８２０は、受信側ＢＳ８２０に割り当てられた符号を用いてＡＴのうちの選択された１つのＡＴ又は選択された複数のＡＴに送信する。しかしながら、本発明は、送信資源を最適に割り当てるために、選択されたＢＳ８２０にデータを提供してその他のＢＳ８２０を除外する異なるＴＤＭＡ方法を採用するその他のシステムに対しても適用可能である。
【００８１】
チャネルスケジューラ８１２は、順方向リンクにおける可変レート送信をスケジューリングする。チャネルスケジューラ８１２は、ＡＴに送信すべきデータ量を示す待ち行列の大きさ、及びＡＴからのメッセージを受信する。チャネルスケジューラ８１２は、好ましいことに、公平性に関する制約を順守しつつ最高データスループットというシステム目標を達成させるようにデータ送信をスケジューリングする。
【００８２】
図１Ａに示されるように、ＡＴは、通信システム全体にわたって分散されており、順方向リンクにおいてゼロ又は１つのＢＳと通信中の場合がある。典型的実施形態においては、チャネルスケジューラ８１２は、通信システム全体を通じての順方向リンクデータ送信を調整する。
【００８３】
一実施形態においては、図２のチャネルスケジューラ８１２は、プロセッサと、ランダムアクセスメモリ（ＲＡＭ）と、プロセッサによって実行される命令を格納するためのプログラムメモリ（示されていない）と、を含むコンピュータシステムにおいて実装される。プロセッサ、ＲＡＭ及びプログラムメモリは、チャネルスケジューラ８１２の関数専用であることができる。その他の実施形態においては、プロセッサ、ＲＡＭ及びプログラムメモリは、ＢＳＣ８１０において追加関数を実行するための共有計算資源の一部であることができる。典型的実施形態においては、図２に示されるシステム８００には一般化されたスケジューラが適用され、以下において詳述される。一般化されたスケジューラの詳細を確立した後に、データ送信をスケジューリングするために優先度関数を実装するために用いられるＢＳＣ８１０及びＢＳ８２０内のモジュールが説明される。
【００８４】
増大してきている無線データアプリケーション需要を考慮して、非常に効率的な無線データ通信システムの必要性も大幅に増大してきている。ＩＳ−９５基準は、順方向リンク及び逆方向リンクを通じてトラフィックデータ及び音声データを送信することができる。ＩＳ−９５基準により、トラフィックデータ又は音声データは、幅が２０ミリ秒で１４．４Ｋｂｐｓという高いデータレートを有する符号チャネルフレームにパーティショニングされる。ＩＳ−９５システムにおいては、各加入者局は、限られた数の直交順方向リンクチャネルのうちの少なくとも１つが割り当てられる。ＢＳと加入者局との間の通信が継続中である間は、順方向リンクチャネルは加入者局に割り当てられた状態である。ＩＳ−９５システムにおいてデータサービスが提供されるときには、加入者局に送信されるべき順方向リンクデータが存在しない間においても順方向リンクチャネルは加入者局に割り当てられた状態である。
【００８５】
音声サービスとデータサービスとの間における重要な相違点は、前者は厳しい固定された遅延上の要求を課すことである。典型的には、スピーチフレームに関する全体的な一方向の遅延は、１００ミリ秒未満であることが規定される。対照的に、データ遅延は、データ通信システムの効率を最適化するために用いられる可変パラメータであることができる。
【００８６】
音声サービスとデータサービスとの間における他の重要な相違点は、前者は全ユーザーに関して固定された共通のＧｏＳを要求することである。典型的には、音声サービスを提供するデジタルシステムに関しては、全ユーザーに関して固定された等しい送信レートになり、スピーチフレームの誤り率に関して最大許容値になる。対照的に、データサービスに関しては、ＧｏＳは、各々のユーザーごとに異なることが可能であり、データ通信システムの全体的効率を向上させるために最適化されたパラメータであることができる。データ通信システムのＧｏＳは、典型的には、以下においてはデータパケットと呼ばれる予め決められたデータ量の転送において生じる総遅延であると定義される。
【００８７】
音声サービスとデータサービスとの間におけるさらに他の重要な相違点は、前者は、典型的ＣＤＭＡ通信システムにおいてはソフトハンドオフによって提供される信頼できる通信リンクを要求することである。ソフトハンドオフの結果、信頼性を向上させるために２つ以上のＢＳからの冗長な送信が行われることになる。しかしながら、誤った状態で受信されたデータパケットは再送信することができるため、このさらなる信頼性は、データ送信に関しては要求されない。データサービスに関しては、ソフトハンドオフをサポートするために用いられる送信電力は、追加データを送信するためにより効率的に用いることができる。
【００８８】
データパケットを転送するために要求される送信遅延及び平均スループット率が、データ通信システムの品質及び有効性を定義するために用いられる２つの属性である。送信遅延は、データ送信においては、音声送信における場合と同じ影響を及ぼさないが、データ通信システムの品質を測定するための１つのメトリックである。平均スループット率は、通信システムのデータ送信能力の効率の尺度である。当業においては、無線チャネルを通じて提供中のサービスの型に適したＧｏＳを同時に提供する一方で向上されたデータスループットを提供する通信システムが必要である。
【００８９】
一般化スケジューラの必要性は、無線システムにおけるデータ送信の要求事項及び目標に基づく。データ送信の場合は、スループットは、個々のビット又はバイトに関してではなくデータパケットの送信において生じる遅延に関して定義される。ほとんどの場合は、パケットの一部分のみを受信してもユーザーがパケット全体を復号して使用する上で十分な情報を含んでいないため、データパケット、例えばＩＰデータグラム、は分割不能な単位である。エンドユーザーは、データパケットを受信し、データパケットに関するＣＲＣを実施し、データを処理する。従って、ユーザーは、パケットの最後のビットの到着時間に最も関心があり、データパケット内の個々のビットの遅延に関しては同じ関心を有さない。このことは、データパケットの送信時間よりも小さいタイムスケールにおける異なるユーザーへのレート割り当てにおいて相当の柔軟性を可能にする。さらに、送信制御プロトコル（ＴＣＰ）型接続においては、パケット遅延の変動が予測できないためＴＣＰ再送信を不必要に生じさせることになる限りにおいてある程度のパケット遅延の変動が許容可能である。
【００９０】
無線チャネルの他の特長は、チャネル自体の可変性である。ＨＤＲ型システムにおいては、この可変性の結果、ある期間における要求レートの変動が生じることになる。チャネルの利用を最大化するために、スケジューラは、高レートユーザー、すなわち最高データレートを要求するユーザー、にサービング（ｓｅｒｖｅ）するように設計される。このことは、ユーザーの要求レートがより低い期間中はユーザーにサービングできない場合があることを意味する。全体的スループットは、スケジューラが低レートユーザーに長時間サービングしないときに最高化することができる。しかしながら、上述されるように、スケジューラは、この点を、パケット遅延と遅延変動を相対的に一定にする希望とを均衡化させる必要がある。
【００９１】
他の側面は、システム内の複数のユーザーに対する公平性を考慮する。公平なスケジューリング方法を完遂させるために、スケジューラは、異なるユーザー間で全体的スループットを分配する。個々のシステムのニーズおよび希望に対処するために、異なるシステムによって異なる公平性の基礎(又は許容可能な不公平性)が用いられる。公平性概念は、多くのスケジューリングアルゴリズムにおける重要概念である。公平性は、異なるユーザーにサービングする際に異なる柔軟性を提供し、従ってセクターの全体的なスループットに対して影響を有する。
【００９２】
一実施形態により、複数のクラスのユーザーを対象として通信システムにおける送信をスケジューリングするための方法及び装置は、一般化スケジューラを組み込む。一般化スケジューラは、様々な異なるスケジューリング優先度を受け入れる。各々が特定の送信上の要求事項を有する異なるクラスのユーザーが、全ユーザーにわたって高いスループットを維持する一般化スケジューラによってサービングされる。
【００９３】
順方向リンクスケジューラの設計においては、以下の３つの主要なＱｏＳクラスが考慮される。
【００９４】
ＢＥ−このクラスは、典型的には相対的に高いエンドツーエンド遅延の余裕があるが非常に低いビット誤り率（ＢＥＲ）を用いるフローが対象になる。最低スループット要求は存在しないが、送信されるデータのサイズが大きくなる可能性がある。ＢＥとみなすことができるフロー例は、ファイルダウンロード（ｆｔｐ）と、ウェブサーフィン（ｈｔｔｐ）と、を含む。
【００９５】
ＡＦ−このクラスは、一般的には、多少大きい遅延の余裕があるという点でＢＥフローと類似するフローを含む。しかしながら、典型的にはＡＦフローに関して最低の平均スループットが要求される点でＢＥフローと異なる。ＡＦフローであるとみなすことができるアプリケーション例は、テレビ会議アプリケーションによって生成される映像ストリームである。
【００９６】
ＥＦ−このクラスは、典型的には低いスループット要求を有する（ただし必ずしもではない）が、エンドツーエンド遅延に関して厳しい要求を有するフローが対象になる。信頼性に関する要求は、ＢＥフローに関するほどは厳しくなく、アプリケーションデータの小さい割合（例えば１％乃至２％）を失うことが許容可能である。該フローの例は、ＶｏＩＰおよびオンラインゲームプレイである。
【００９７】
順方向リンクスケジューラに関する限りは、ＢＥフローとＡＦフローとの間における相違点は、最低スループットに関する要求であり、最低スループットは、ＢＥフローの場合がゼロ、ＡＦフローの場合が非ゼロである。それ以外に関しては、これらの２つのＱｏＳクラス間には相違点はない。
【００９８】
ＥＦクラス内においては、異なる優先度を有するフローが存在することができる。一例として、ＶｏＩＰ及びテレビ会議アプリケーションの音声部分等のアプリケーションは、テレビ会議アプリケーションの映像部分よりも高い優先度を有するとみなすことができる。オンラインゲームプレイは、音声及び映像の両アプリケーションよりも低い優先度を有するとみなすことができる。
【００９９】
ユーザーアプリケーションによって生成されるフローに加えて、１ｘＥＶ−ＤＯシステムは、フロー、例えば、１ｘＥＶ−ＤＯを稼働状態にしておくために要求されるシグナリングフロー、及び１ｘＥＶ−ＤＯシステムの試験に用いられる試験アプリケーションによって生成されるフロー、を内部において生成しておくことができる。
【０１００】
一実施形態においては、一般化スケジューラの動作は、チャネル状態メトリック及び公平性判定基準の優先度関数を実装し、前記優先度関数は、以下のように定義される。
【０１０１】
ｆ（Ａｉ（ｔ），Ｕｉ（ｔ））                        （４）
ここで、Ａｉ（ｔ）は、チャネル状態メトリックと呼ばれ、Ｕｉ（ｔ）は、ユーザー公平性メトリックと呼ばれる。関数Ａｉ（ｔ）は、時間ｔにおいてユーザーｉにサービングする希望度を受信されたサービスの過去の履歴に基づいて指定する。優先度関数ｆ（  ）は、２つの希望度メトリックＡｉ（ｔ）及びＵｉ（ｔ）を組み合わせて各ユーザーに関する優先度レベルを決定する。
【０１０２】
一実施形態により、一般化スケジューラは、所定のユーザークラス又はユーザー型内において最高優先度関数ｆ（Ａｉ（ｔ），Ｕｉ（ｔ））を有するユーザーをサービングする。典型的実施形態においては、優先度関数ｆ（Ａｉ（ｔ），Ｕｉ（ｔ））によってとられる値は、チャネル状態関数Ａｉ（ｔ）が大きくなるに従って大きくなり、公平性関数Ｕｉ（ｔ）が大きくなるに従って小さくなる。関数Ａｉ（ｔ）及びＵｉ（ｔ）は、適宜決定される。さらに、優先度関数ｆ（  ）は、チャネル状態メトリック及びユーザー公平性メトリックが測定される少なくとも１つの期間の関数である。代替実施形態においては、優先度関数ｆ（  ）は、時間に依存する１つのユーザー当たりの関数である。しかしながら、説明を単純化するため、スケジューラは、全ユーザーに共通するコンバイナ関数を使用し、ユーザーによる要求を反映させるようにユーザー公平性メトリックを修正することができる。
【０１０３】
ＱｏＳに関する要求事項
典型的なＱｏＳに関する要求事項は、次の変数を用いて記述することができる。
【０１０４】
ＤｅｌａｙＢｏｕｎｄ（遅延限度）は、各フローに関してスケジューラに指定されるパラメータであり、データグラム（又はオクテット）が成功裏にユーザーに引き渡されなければならない該データグラムのタイムスタンプに関する最大遅延を表す。この遅延限度は、１ｘＥＶ−ＤＯシステムにおける順方向リンク遅延以外の遅延−バジェット成分が関わることになるエンドツーエンド遅延限度とは異なることに注目すること。データグラムのＤｅｌａｙＢｏｕｎｄに達した時点で、データグラムが待ち行列から取り出される。
【０１０５】
ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔは、スケジューラに対して指定することができる他のＱｏＳパラメータであり、フローに関する最低限の要求される平均スループットを意味する。スループットの平均を求めることは、適切な時定数（例えば１秒）を有する一次無限インパルス応答（ＩＩＲ）フィルタを介して定義することができる。
【０１０６】
第３のＱｏＳに関する要求事項は、信頼性であることができる。典型的には、１ｘＥＶ−ＤＯシステムの物理層は、例外的に低い誤り率を要求するアプリケーション、例えばファイルのダウンロード、に関しては十分でない可能性がある１％のパケット誤り率（ＰＥＲ）を提供する。従って、オーバーザエアでの損失をさらに低減させるために、再送信メカニズムを利用することができる。典型的再送信メカニズムは、（前述されるように、ＲＴｘ及びＤＡＲＱ待ち行列にそれぞれ対応する）ＲＬＰ再送信及びＭＡＣ層再送信である。さらに、アプリケーションがさらなる信頼性を提供するためのトランスポート層プロトコルとしてＴＣＰを用いることができる。
【０１０７】
容量及び公平性
順方向リンクスケジューラ、例えばチャネルスケジューラ８１２、は、諸フロー間における公平性を提供し、該フローの優先度及びＱｏＳに関する一定の要求を満たす一方でシステム容量を最大化することの均衡を図る。容量及び公平性の概念は、個々のフローのＱｏＳに関する要求事項に依存する。ＢＥフローに関しては、容量は、セクターによって送信される総ＢＥスループットであると定義することができる。特定の型（例えばＶｏＩＰ）のＥＦフローに関しては、容量は、ＱｏＳに関する要求を満たしつつサポートできるユーザー数であると定義することができる。一例として、ＶｏＩＰ容量は、平均して全ユーザーの９５％がアプリケーションデータフレーム（又はオクテット）の９８％を成功裏に（指定されたＤｅｌａｙＢｏｕｎｄ内において及び送信誤りがない状態で）受信するようなＶｏＩＰユーザー数であると定義することができる。
【０１０８】
諸フロー間における公平性の課題は、ＢＥクラス及びＥＦクラスに関して次のように処理することができる。すなわち、システム負荷が増大するのに応じてＢＥフローが一様に劣化するような形でＢＥフロー間において比例的公平性を用いる。ＥＦフローに関しては、システム負荷が増大する（又は混雑が生じる）のに応じてユーザー間で一様でない劣化を有することが望ましい。劣化は、最も低い優先度を有するとみなされるＥＦフローから開始する。同様のＱｏＳ要求事項及び同じレベルの優先度に対応するフロー間において、劣化は、最悪のチャネル状態を有するユーザーのフローから開始する。この手法により、システムが混雑するのに従い、最大限可能な数のＥＦフローがそれぞれのＱｏＳ要求を満たすことができる。この手法の結果は、通常は、ユーザーのチャネル状態とＥＦフローの遅延統計との間がほぼ反比例の関係になる。この性質は、“遅延公平性”と呼ばれる。
【０１０９】
一般的クラスのマルチユーザースケジューラは、ＡＮからサービスを受信するユーザーを少なくとも２つの大きなカテゴリであるＢＥ及びＥＦに分類する。その他の送信カテゴリ、例えばＡＦ等、も同様に実装することができる。上述されるように、ＢＥアプリケーション全般は、オーバーザエアで受信するデータ量が相対的に大量であり、トラフィックの性質上相対的に大きな遅延を許容可能であるが、データ損失率を極端に小さくすべきである。ＥＦアプリケーションのフローは、典型的には、インターネットからＡＮに到着するトラフィック量が少量であるが、トラフィックの性質上、データパケットは一定の相対的に小さいＤｅｌａｙＢｏｕｎｄ内において合理的なデータ損失率でユーザーに引き渡されるべきである。
【０１１０】
１ｘＥＶ−ＤＯ等のパケットデータシステムにおいては、スケジューラは、容量を最大にするために個々のユーザーへの可変遅延性能を許容する柔軟性を有する。ここでは、容量は、ＶｏＩＰ（ＥＦユーザー）等の遅延の影響を受けやすいトラフィックの場合におけるＢＥユーザーに関するスループット及び許容可能な性能を有するサービングされたユーザー数を指す。
【０１１１】
１ｘＥＶ−ＤＯにおいては、一般的には、ユーザーのＤｅｌａｙＢｏｕｎｄを大きくするとＦＬの利用が向上し、従ってシステムのＢＥ及びＥＦ容量を増大させる。この容量増大は、限定されることなしに、より高いパッキング効率及びローカルなチャネル状態及びマルチユーザーダイバーシティ利得を利用する能力を含む様々な要因によるものである。
【０１１２】
ＢＥ専用トラフィックの場合は、典型的スケジューラは、比例的公平（ＰＦ）スケジューラである。このスケジューラは、個々のユーザーに提供されるスループットがユーザーのジオメトリ（ｇｅｏｍｅｔｒｙ）、すなわち平均的チャネル状態、にほぼ比例することになるという意味で比例的に公平である。ＰＦスケジューラは、スループットの利益と公平性の利益の相反性に起因してＢＥ専用トラフィックに関して選択されるスケジューラとなっている。さらに、ＰＦアルゴリズムは、マルチユーザーダイバーシティ利得を提供しつつローカルチャネルピークを利用するように設計される。本明細書においては、該ＰＦスケジューラは、“比例的公平スループットスケジューラ”と呼ばれる。
【０１１３】
ＢＥ専用トラフィックの場合は、他のクラスのスケジューラ、すなわち“等しいサービス等級”スケジューラが存在することに注目すること。このスケジューラは、等しいスループットを全ユーザーに提供することを目的とする。この理由により、システム容量は、最も弱いユーザーによって決定される。等しいサービス等級スケジューラは、一定のアプリケーションにおいて望ましいが、該スケジューラは、典型的には、エアリンクを効率的に利用しない。これらのスケジューラは、本明細書においては、“等スループットスケジューラ”と呼ばれる。
【０１１４】
上述される比例的公平スループットスケジューラ及び等スループットスケジューラは、ＢＥ専用トラフィックに関して有用である。遅延の影響を受けやすいＥＦトラフィックに関しては、これらのスケジューラは、遅延制御メカニズムがないことに起因してＢＥ専用トラフィックほどは有効でない場合がある。次に、ＢＥ専用トラフィックに関する２つの手法、すなわち、比例的公平スループットスケジューラ及び等スループットスケジューラ、と並行して動作する遅延の影響を受けやすいスケジューリング手段及び方法が示される。遅延の影響を受けやすいトラフィックの場合は、“比例的”及び“等しい”公平性は、個々のユーザーに提供されるスループットに対してだけでなく、個々のユーザーに提供される“遅延”性能に対しても適用される。遅延性能は、平均遅延、遅延テール重み等に関して定量化することができる。代替実施形態は、スループット及び遅延の影響度に関する要求をそれぞれ満たしつつＢＥ及びＥＦスケジューリングを１つの共通する方法に組み入れることができる点に注目すること。
【０１１５】
一実施形態においては、ほぼ等しい遅延性能を各ユーザーに提供することができる。この手法は、等しいスループットと類似しており、用語の対称性上、“等遅延スケジューラ”と呼ばれる。等スループットスケジューラは、等しいスループットを全ユーザーに提供することを試み、従って、システム容量は、最も弱いカバレッジを有するユーザーによって決定することができる。等遅延スケジューラは、等遅延性能、例えば、等しい平均遅延又は等しい遅延テール重み、を全ユーザーに提供することを試み、従って、システム容量は、同様に最も弱いカバレッジを有するユーザーによって決定される。
【０１１６】
他の実施形態においては、ユーザーに提供される遅延性能は、該ユーザーの平均ジオメトリに比例する。この手法は、比例的公平スループットスケジューラと類似しており、“比例的公平遅延スケジューラ”と呼ばれる。比例的公平スループットスケジューラは、各々の平均ジオメトリに比例するスループットを個々のユーザーに提供することを試み、それによって、等スループットスケジューラと比較してシステム容量を大幅に向上させる。同様に、比例的公平遅延スケジューラは、ユーザーの平均ジオメトリに比例する遅延性能を個々のユーザーに提供し、それによってＥＦ容量を最大化する。
【０１１７】
これらの４つのパケットスケジューリングカテゴリは、図４に示される。各カテゴリは、ＱｏＳに関する考慮事項が均衡化された状態が示されている。具体的には、ＰＦスループットスケジューラは、スループット制御を比例的公平性と均衡化する。等スループットスケジューラは、スループット制御を等しい公平性と均衡化する。ＰＦ遅延スケジューラは、遅延制御を比例的公平性と均衡化する。等遅延スケジューラは、遅延制御を等しい公平性と均衡化する。
【０１１８】
幾つかのスケジューリング方法は回線交換システムにおいて有用である一方で、その他のスケジューリング方法は、１ｘＥＶ−ＤＯ等のパケットデータシステムに関してより適用可能である。本明細書において提示される比例的公平遅延スケジューリング手段及び方法は、回線交換システムに対するパケット交換システムの優位性を提供することができる。
【０１１９】
比例的公平遅延スケジューラは、システム容量を向上させることに加えて、ユーザーの経験を高めることもできる。例えば、ＢＳに非常に近接するユーザーは、ＢＳからより離れているユーザーよりも良い遅延性能を受信する可能性がより高い。このことは、ＢＳへのユーザーの近接性に依存しない遅延性能と対照的である。さらに、ＢＳに非常に近接する高ジオメトリのユーザーの場合は、高い信頼度レベルで性能を予測可能である。他方、等遅延スケジューラに関しては、性能は、システムに対する現在の負荷に依存して予測不能である。従って、スケジューラが個々のユーザーのジオメトリの増大に応じてサービスの質を向上させることが望ましい。
【０１２０】
ＢＥ及びＥＦの両ユーザーにサービングするスケジューラは、比例的公平スループット及び遅延スケジューリングの適切な組合せを利用することができる。該スケジューラは、“比例的公平スループット／遅延スケジューラ”と呼ばれる。一実施形態においては、比例的公平スループット／遅延スケジューリングは、単一のセクターに関してサービングされるユーザーの相対的ジオメトリに暗黙に基づくことに注目すること。このことは、“セクター内公平性”と呼ばれる。スケジューラ設計における他の考慮すべき課題は、異なるセクターによってサービングされるユーザーに対してこれらの異なるセクターによって提供される“セル間”公平性であり、“セル間”公平性とは、平均レベルのサービスであると説明することができ、ＢＥユーザーに対して提供されるスループット及びＥＦユーザーに対して提供される平均遅延、等に関して定量化することができる。
【０１２１】
比例的公平スループットスケジューラと比例的公平遅延スケジューラとの間の類似点を続けると、比例的公平スループットスケジューラを利用するセクターによって個々のＢＥユーザーに提供されるスループットは、そのセクターによってサービングされるユーザー数が減少するのに応じて低下することに注目すること。しかしながら、セクター内公平性は維持される。同様に、比例的公平遅延スケジューラを利用するセクターによって個々のＥＦユーザーに提供される遅延性能は、セクターによってサービングされるユーザー数が増加するのに応じて向上することが許容される。
【０１２２】
比例的公平スループット／遅延スケジューラは、いずれかのスケジューリング決定においてサービングすべきユーザーを選択するために以下の形の決定メトリックを利用する。  
ＤｅｃｉｓｉｏｎＭｅｔｒｉｃ＝ｆ（ＰａｃｋｅｔＡｇｅ，ＣｈａｎｎｅｌＣｏｎｄｉｔｉｏｎ，ＳｅｃｔｏｒＬｏａｄ）                                                     
（５）
ここで、ＰａｃｋｅｔＡｇｅは、現在の時間とＢＳ待ち行列において待機中の各パケットに関して定義された適切なタイムスタンプとの間の違いを表し、ＣｈａｎｎｅｌＣｏｎｄｉｔｉｏｎは、ＢＳとＡＴとの間における無線リンクの品質を表し、ＳｅｃｔｏｒＬｏａｄは、現在の時間の近くにおける短い時間間隔においてセクターによってサービング中の総トラフィックの量及び状況を表す。関数ｆ（）は、スケジューラの特定の実装に依存する。さらに、ＤｅｃｉｓｉｏｎＭｅｔｒｉｃは、ビットメトリック、パケットメトリック、データグラムメトリック、又は送信インスタンス選択方法をスケジューラに提供するその他の手段を表すことができる。
【０１２３】
ＣｈａｎｎｅｌＣｏｎｄｉｔｉｏｎ情報は、様々な形でスケジューラ内に組み入れることができる。例えば、比例的公平スループットスケジューラは、ローカルチャネルピーク中にピークに達する傾向があるＤＲＣ／ＡｖｇＴｈｒｏｕｇｈｐｕｔを用いる。他の手法は、ＤＲＣ／ＡｖｇＤＲＣを用いることができるが、アプリケーション上は、より大きいチャネル変動を有するユーザーを優先することができる。他の可能性は、チャネルピークの一定の割合を示すためにフィードバックループを用いることである。１つの該ループ３００が図５に示される。
【０１２４】
図５に示されるように、一実施形態は、しきい値に関して受け入れ可能なチャネル品質を決定するように設計されたループ３００である。入力ＩＤＲＣは、ＤＲＣ値の関数又はインデックス、例えば、ＤＲＣと関連づけられたデータレートの逓増関数であり、ＩＤＲＣは、要求されたデータレートが上昇するのに応じて大きくなる。ＩＤＲＣは、比較ユニット３０２及びＩＩＲフィルタ３０６に提供される。一例においては、時定数は、１秒に設定される。しかしながら、代替時定数を実装することができる。ＩＩＲフィルタ３０６のフィルタリングされた出力が加算ユニット３１２に提供され、加算ユニット３１２は、しきい値を比較ユニット３０２に提供する。比較ユニット３０２は、ＩＤＲＣをしきい値と比較する。比較結果は、現在のチャネル品質が受け入れ可能であるかどうかを示す。システムは、チャネル品質が受け入れ可能であるときに目標とする時間の割合を決定する。本例においては、目標は３０％に設定される。目標は、可変であり、動作中に調整することができる。代替システムは、その他の目標値又は方式を実装することができる。比較ユニット３０２の出力は、バイナリ｛１，０｝であり、“１”は、受け入れ可能なチャネル品質を示し、“０”は、受け入れ不能（例えばしきい値未満）であることを示す。
【０１２５】
図５を続けると、比較ユニット３０２の出力は、他のＩＩＲフィルタ３０４に提供され、本例においては、時定数は０．５秒に設定される。代替時定数を実装可能である。ＩＩＲフィルタ３０４から、フィルタリングされた出力が、入力値と比較するために比較ユニット３１０に提供される。本例においては、入力値は０．３である。比較結果が入力値よりも大きい場合は、チャネル品質を決定するためのしきい値を大きくするためにアップ／ダウン累積器３０８に信号が提供される。これは、比較ユニット３０２からのチャネル品質インジケータが３０％超であることを示す。他方、比較結果が入力値よりも小さい場合は、アップ／ダウン累積器３０８に提供された信号は、しきい値を小さくするように指示する。アップ／ダウン累積器３０８の出力が加算ユニット３１２に提供される。加算ユニット３１２は、アップ／ダウン累積器３０８及びＩＩＲフィルタ３０６の出力を合計し、ＩＩＲフィルタ３０６からの入力は、しきい値に関する一般的バイアスを比較ユニット３０２に提供する。加算結果は、比較ユニット３０２に提供される。チャネル推定インジケータが比較ユニット３０２の出力から取り出される。この方法により、スケジューラは、チャネル状態が良好であるときの良好な時間（例えば、チャネルピーク）の割合を識別するためにチャネル推定インジケータ又はＣｈａｎｎｅｌＣｏｎｄｉｔｉｏｎ情報を維持する。
【０１２６】
ＢＥフロー及びＥＦフローの量を測定することによってＳｅｃｔｏｒＬｏａｄをスケジューラ内に組み入れることができる。最後に、スケジューラによって用いられる実際の決定メトリックは、ＣｈａｎｎｅｌＣｏｎｄｉｔｉｏｎ測定値及びＳｅｃｔｏｒＬｏａｄ測定値を明示で含むことができない。１つのユーザー当たりの要求されるＤｅｌａｙＢｏｕｎｄは、送信されたＩＰパケットの一定の割合に関して遅延限度を満たすことができないＥＦユーザーの割合を測定することによって適応的に選択することができる。
【０１２７】
幾つかのスケジューラによって用いられるパラメータは、フローの“ＱｏＳクラスインデックス”と呼ばれ、そのフローの相対的優先度を定義する。ＱｏＳクラスを決定することができる様々な方法が存在する。所定のＱｏＳクラス内において、異なるフローは、非常に異なるトラフィック型を有することができる。ＱｏＳクラスインデックスは、フローによる要求された優先度レベルの指標であり、トラフィックの統計的挙動を示す指標であることができない。
【０１２８】
一実施形態においては、ＱｏＳクラスインデックスは、スケジューラがより高いＱｏＳクラスインデックスを有するフローにより高い優先度を提供するために選択される負でない整数値である。ここでは、０のＱｏＳクラスインデックスは、ＢＥ／ＡＦフローに対応し、ＢＥフローは、要求される最低スループット値がゼロに設定されるＡＦフローの特殊事例である。１よりも高いＱｏＳクラスインデックスは、ＥＦフローに対応する。
【０１２９】
より高いＱｏＳクラスにより高い優先度が与えられるが、ＢＥデータは、待ち行列において待機中の全ＥＦデータが送信された後に送信に関してスケジューリングすることが必ずしもできるわけではないことに注目すること。一例として、スケジューラは、期限が近づいている幾つかのＥＦビットを送信するようにマルチユーザーパケットをスケジューリングすることができる。同じ送信インスタンスにおいて、スケジューラは、適合可能なＤＲＣ、例えば送信フォーマット、を有するユーザーからのＢＥデータを含み、その一方で適合不能なＤＲＣを有するユーザーからのＥＦビットを含めないようにすることもできる。
【０１３０】
ＱｏＳフローは、３つのパラメータ、すなわち、（１）ＩＰデータグラムのサイズの分布、（２）ＩＰデータグラム間における到着間の時間の分布、及び（３）超えた場合はＩＰデータグラムの内容が役に立たなくなるＩＰデータグラムのタイムスタンプに関する遅延限度、によってほぼ特徴づけることができる。
【０１３１】
ＢＥ／ＡＦフローに関して、遅延限度は、厳しさがＥＦフローよりもはるかに弱く、従って、ＢＥ／ＡＦフローに関しては考慮することができない。同じ遅延限度を有するがＩＰデータグラムのサイズの分布及び到着間時間が異なるＥＦフローに関しては、スケジューラは、ほとんど線形で挙動するように設計される。例えば、ＶｏＩＰフローと同じ遅延限度及びパケットサイズ分布を有するが、１／２の到着間時間分布を有する所定のフローは、２つのＶｏＩＰフローとほぼ同じように挙動することができる。同様に、ＶｏＩＰフローと同じ遅延限度及び到着間時間分布を有するが、２倍のデータグラムサイズ分布を有するフローは、スケジューラに対する２つのＶｏＩＰフローとしてほぼ挙動することができる。パケットサイズ及び到着間時間の非整数倍数は、基本“単位”フロー型の集合であると容易に想像することができる。
【０１３２】
しかしながら、遅延限度は、データグラムサイズ分布及び到着間時間分布とは異なる影響をスケジューラに対して有する。スケジューラは、より低い遅延限度を有するフローをより高い優先度で取り扱う。ある意味においては、フローの遅延限度をより低い値に設定することは、ＱｏＳクラスインデックスを大きくするソフトな方法である。
【０１３３】
上述されるように、送信のスケジューリングは、受付制御（ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ）に関連し、受付制御は、ユーザー又はフローが処理及びスケジューリングに関していつ受け入れられるかを決定し、次に、該フローがいつどのようにして送信されるかを決定する。換言すると、受付制御は、いずれのデータが送信インスタンスに含める資格を有することになるかを決定し、次に、スケジューリングは、送信インスタンスの特定のデータ、フォーマット及び順序を決定する。従って、スケジューラ動作は、所定のシステムにおいて用いられる受付制御方式に影響を与えることができる。
【０１３４】
一実施形態により、システム負荷が増大するのに従い、典型的には、ＢＥ／ＡＦフローは、各々のフローが公平に劣化するような形でスケジューリングされる。しかしながら、ＥＦフローに関しては、劣化は典型的には一様でない。より具体的には、より高いＱｏＳクラスが適切に機能するのを維持することを試みるためより低いＱｏＳクラスが最初に劣化される。所定のＥＦ  ＱｏＳクラス内において、さらに遅延限度設定の違いを無視した場合、可能な限り多くのユーザーが希望される性能を受信するように維持するためにより低いジオメトリを有するユーザーが最初に劣化される。この手法は、サポートされるＥＦユーザー数を最大にするために採用される。均質なＥＦフローに関しては、ＥＦユーザーは、最初に最低のジオメトリを有するユーザーが不均一に劣化され、より高いジオメトリのユーザーに進む。この手法は、スケジューラの外部において、より具体的には受付制御処理によって処理される幾つかの結果を有する。これらの結果の一部が以下の例において示される。
【０１３５】
スケジューラのこの機能は、図６に示され、フローは、ジオメトリに従ってソートされた順序で示されており、右に進むほどジオメトリが高くなる。現在のシステム負荷を考慮した場合、スケジューラは、希望されるＱｏＳを受信するＱｏＳフロー数を最大にするためにより低いジオメトリのユーザーにより低い優先度を与える。低いジオメトリのユーザーのレベルは右に進み、右に進むほど混雑度が増大する。スケジューラは、該ユーザーにより低い優先度を与えることによってこれらのユーザーよって受信されたサービスを劣化させる。しかしながら、スケジューラは、フローを完全に取り出す責任を有しておらず、このことは、典型的には、受付制御及びその他の性能モニタリングブロックの機能になる。
【０１３６】
全ユーザーが単一のフロー及び同じＱｏＳクラス、例えばＶｏＩＰフローを有し、最高のジオメトリのユーザーが非常に高いスループットのＥＦフローを要求する状況について検討する。スケジューラは、その他のユーザーへの送信が行われないことを意味する場合においても、最高のジオメトリのユーザーにすべてのＦＬスロットを割り当てることができる。一般的には、フローに関する受付決定は、システムの現在のローディングを考慮する受付制御処理によって処理される。受付制御がフローを受け付けたときには、スケジューラは、あらゆる基本機能を実行し、すべてのＦＬスロットをそのユーザーに割り当てる。より低いジオメトリのユーザーを最初に劣化させることは、スケジューラが受け入れ可能な受信性能を有するＥＦユーザー数を最大にすることを必ずしも意味しないことに注目すること。スケジューラは、全ユーザーが同じＱｏＳパラメータ及び同じトラフィック型（例えばＶｏＩＰのみ）を有する場合に該ＥＦユーザー数を最大にすることができる。
【０１３７】
混雑が激しくないことに起因してスケジューラによってサービスが劣化される低ジオメトリユーザーが非常に低いスループット（例えば毎秒１バイト）を要求している場合は、スケジューラは、ＦＬの性能に影響を与えない場合であっても要求された又は希望される性能をこのユーザーに与えることができない。繰り返すと、現在のシステム負荷を考慮した場合にこのユーザーに関するスケジューラの動作を予想するのは受付制御の責任である。この場合は、受付制御は、ＱｏＳクラスインデックスを増やすことによってこのユーザーにサービスを提供するようにスケジューラに強制することができる。
【０１３８】
以下の説明のために、全ユーザーが同じトラフィックモデルを有するＥＦユーザーであるシナリオとして均質なＥＦトラフィックを考慮する。スケジューラは最初に、一組の単一ユーザー及びマルチユーザー送信フォーマットに関する候補送信インスタンスのリストを作成する。単一ユーザーフォーマットには、対応するユーザーの待ち行列からのビットがスタッフィングされる。マルチユーザーフォーマットには、適合可能なＤＲＣを有するユーザーの待ち行列からのビットがスタッフィングされる。
【０１３９】
次に、スケジューラは、パケットメトリックを候補インスタンスの各々に割り当て、最大のパケットメトリックに対応する候補送信インスタンスを選択する。パケットメトリックは、“スループット多項式”であることができ、比較動作は、適切に定義された最大化を提供する“辞書方式の”比較であると定義される。
【０１４０】
全ユーザーがＥＦユーザーであり、各々のユーザーが同じ型（例えば、ＶｏＩＰ専用システム）及びマルチユーザー送信フォーマットの１つのＥＦフローを有し、このフォーマットに関するマルチユーザー送信インスタンスを生成するために適合可能ＤＲＣを有するユーザーの待ち行列からビットがスタッフィングされる特殊ケースに関するパケットメトリックについて考慮する。これらのユーザーの間で、対応するＩＰデータグラムのタイムスタンプに基づいて先入れ先出し方式でビットが選択される。この例では、遅延限度は同じであると仮定される。同じタイムスタンプを有するビット間においては、選択は、ＩＰパケット内の順序に従い、異なるユーザー間においては、選択は、パケット内においてデータを有するユーザー数を最少にするように行われる。
【０１４１】
送信インスタンスのペイロード多項式は、以下のように与えることができる。
【０１４２】
ｐ（ｚ）＝ＢＤｚ−Ｄ＋ＢＤ−１ｚ−Ｄ＋１＋・・・Ｂ１ｚ−１＋Ｂ０                                （６）
ここで、ＢＤは、ｎのスロットの遅延を被る候補送信インスタンスに含まれるビット数を表す。ビットが遅延限度を超える期間にわたって待ち行列内に存在しており、従ってＤのスロットを超える遅延を被るときに該ビットを待ち行列から取り出すことができるため、Ｄの値は、遅延限度と等しくすることができる。
【０１４３】
スループット多項式は、ペイロード多項式をフィルタリング及びサブサンプリングすることによって得られる。１つの方法は、ペイロード多項式の係数ベクトルをＮのグループにセグメンテーションし、各グループ内の係数を合計してペイロード多項式の簡略化された表現を得ることである。これで、スループット多項式は、簡略化されたペイロード多項式を対象となる全ユーザーによって復号されるべき候補送信インスタンスに関する予想スロット数によって割ることによって得られる。この手順は、図７に示され、最上行がペイロード多項式ｐ（ｘ）であり、最下行は、ペイロード多項式の簡略化された表現であるｃ（ｚ）である。変数ｚは、送信インスタンスインデックスである。
【０１４４】
スループット多項式は以下のように与えられる。
【０１４５】
Ｔ（ｚ）＝ｃ（ｚ）／Ｎｇ                  （７）
ここで、Ｎｇは、考慮中の送信フォーマットに関する“一般的”スパンであり、その計算方法が以下において説明される。その結果得られたスループット多項式は、各々が同様に入手される一組の様々なその他の代替の中から候補送信インスタンス３５を選択する際のパケットメトリックとして用いられる。
【０１４６】
上述されるパケットメトリックは、レーテンシーの強制とスループットとの間における相反性を暗に示していることに注目すること。Ｎ−１がＤと等しくなるように選択された場合、すなわち、ｃ（ｘ）＝ｐ（ｘ）である場合は、パケットメトリックは、最初に最大の遅延を被っているビットの送信を強制する。引き続き、候補送信インスタンスの選択の際に次に大きい遅延を被っているビットが考慮される。この考慮は、パケットメトリック（すなわち、スループット多項式）を比較する際に用いられる“辞書方式の”比較の結果である。この方法により、比較は、各多項式の最高次数を識別することから始まる。１つの多項式がより高い次数を有する場合は、その多項式はより大きい多項式として定義される。両方の多項式が同じ次数を有する場合は、最初に最も高い次数から係数が比較され、１つの多項式においてより高い係数が見つかったときに、その多項式はより大きい多項式であると定義される。
【０１４７】
ｐ（ｘ）の係数をセグメンテーションしてｃ（ｘ）を入手することは、各セグメント内のビットに対応する被った遅延の相違を暗黙に無視する。その代わりに、現在より大きい柔軟性を有するスループットを最高にすることが存在する。ｐ（ｘ）の全係数が単一のセグメント（例えば次数ゼロのｃ（ｚ））内に結合された場合にスループットを最高にする上で最大の柔軟性が得られる。
【０１４８】
一例においては、２つのセグメント（例えば次数１のｃ（ｚ））は、妥協を提供する。最大次数の項が最大の影響力を有する。様々な候補インスタンス間において引き分け（ｔｉｅ）が存在するときには、ｃ（ｚ）の項が考慮される。従って、ｐ（ｚ）の係数をセグメンテーションして３つ以上のセグメントにする必要がない場合がある。その結果、最適化すべきパラメータは１つになり、該パラメータは、αによって表されて“遅延部分”と呼ばれる。要約すると、２つのセグメントの場合は、ｃ（ｚ）＝（ｈｉ２）ｚ−１＋（ｈｉ）であり、ここで、“ｈｉ２”及び“ｈｉ”は、それぞれ、各セグメント内のビット数である。より具体的には、ｈｉ２は、遅延限度のα倍よりも大きい遅延を被っている候補送信インスタンスに含まれているビット数であり、“ｈｉ”は、より小さい遅延を被っているビット数である。
【０１４９】
すべてのＥＦトラフィックを有するが異なるトラフィックモデル（例えば、異なる遅延限度）を有するユーザーの場合は、引数が修正される。より小さい遅延限度を有するビットは、より大きい遅延限度を有するビットよりも速くｈｉ２の一部になる。このことを達成させる自然な方法は、候補送信インスタンス内にビットをシフトさせる際に及びビットがいつｈｉ２ギアの一部になるかを決定する際に、“遅延”単独とは対照的に遅延のβ倍を用いることである。
【０１５０】
一般的には、βは、遅延限度＋１に比例するように設計される。その結果、より低い遅延限度を有するＥＦビットがより大きい遅延限度を有するＥＦビットよりも優先される傾向がある。
【０１５１】
図８は、一実施形態によるスケジューラを示す。スケジューラ６００は、待ち行列情報を格納及び維持するのに適したメモリ記憶ユニット６０４に結合された適応型遅延制御ユニット６０２を含む。メモリ記憶ユニット６０４は、遅延及び／又はスループット影響度、優先度クラス、例えば、ＥＦ、ＢＥ、等を含む情報、及び設計によってスケジューラ内に組み込むことができるその他の情報、例えばその他のＱｏＳ情報、も格納する。メモリ記憶ユニット６０４に格納された待ち行列データ及び情報は、ビットメトリック計算ユニット６０８及びビットスタッフィングメトリック計算ユニット６０６に提供される。これらのユニットは、ビットメトリック及びビットスタッフィングメトリックをそれぞれ生成する。計算されたビットメトリックは、ビットメトリック計算ユニット６０８、パケットメトリック計算ユニット６１６、及び待ち行列選択ユニット６１０に提供される。ビットスタッフィングメトリック及び選択された待ち行列は、候補送信インスタンス生成器６１２に提供される。パケットメトリック計算ユニット６１６からのパケットメトリック及び生成器６１２によって生成された候補送信インスタンス３５の組は、送信インスタンス選択ユニット６１４に提供される。一実施形態においては、送信インスタンス選択ユニット６１４は、候補パケット生成器２５であることができる。
【０１５２】
図９は、送信待ち状態のデータを有する複数の待ち行列を格納中のメモリ記憶ユニット６０４の詳細を示す。待ち行列データは、待ち行列データ６２０として各々のフローごとに格納される。各待ち行列６２０に関して、対応するＱｏＳクラス又は優先度クラス６２２及び影響度指定子６２４が存在する。
【０１５３】
図１０は、単一搬送波スケジューラ２３が用いられる一実施形態によるスケジューリング方法を示す流れ図である。方法５００は、最初に、判断ブロック５０２において、ＦＬがビジーであるかどうか、すなわち、新たなパケット送信に関してタイムスロットを利用可能であるかどうかを決定する。新たなパケット送信に関してスロットが利用可能である場合は、単一搬送波スケジューラ２３は、ステップ５０４において、部分組の定義されて導き出された送信フォーマットに基づいて候補送信インスタンス３５のリストを生成する。ステップ５０６において、各候補送信インスタンス３５に対応するパケットメトリックが計算される。ステップ５０８において、単一搬送波スケジューラ２３は、パケットメトリックに関する最大値を有する送信インスタンス３５を選択する。ステップ５１０において、送信インスタンス３５が送信のためにフォーマット化される。
【０１５４】
図１１は、一組の候補送信インスタンス３５を生成して方法５００におけるステップ５０４を実装するための一実施形態を示す。ステップ５２０において、単一搬送波スケジューラ２３は、各待ち行列エントリに関するビットメトリックを計算する。ステップ５２２において、単一搬送波スケジューラ２３は、各待ち行列に関するビットスタッフィングメトリックを計算する。ステップ５２４において、送信インスタンスに関する一組の待ち行列を選択するためにビットメトリック値が比較される。ステップ５２６において、ビットスタッフィングメトリックを用いて、待ち行列の組を用いて候補送信インスタンス３５が生成される。該計算及び比較に関する方法及び手段の例が以下において提供される。
【０１５５】
一実施形態においては、送信待ち状態のデータを有する各ユーザーに関して単一ユーザーフォーマットを有する候補送信インスタンス３５が生成されることに注目すること。送信フォーマットは、そのユーザーのＤＲＣに対応するカノニカルフォーマットに設定される。受信されているＮＵＬＬ  ＤＲＣを送信したユーザーに関して、候補送信インスタンス３５は、ユーザーが送信待ち状態の“ＥＦ”データを有する場合のみに作成される。ＢＥ／ＡＦユーザーに関しては、これらのユーザーはＲＬＰ層において低ドロップ率を維持することを試みるため、ＮＵＬＬ  ＤＲＣはサービングされない。
【０１５６】
マルチユーザーフォーマットを有する候補送信インスタンス３５は、各々の定義されて導き出された“カノニカル”マルチユーザーフォーマットに関して生成される。導き出されたフォーマットをこの段階において許容するためにフラグを用いることができる。
【０１５７】
ステップ５０６において生成された候補送信インスタンス３５の組は“カノニカル”フォーマットに基づくことに注目すること。すなわち、このステップには短いパケットは含まれない。その目的は、ジオメトリがより高いユーザーの方に単一搬送波スケジューラ２３を偏らせやすくすること及び低ジオメトリユーザーが短いパケットを乱用するのを回避しそれによってＦＬスループットを低下させることである。短いパケットは、選択された候補送信インスタンス３５が短いパケットに適合するペイロードを有するときに（図１２において示されるような）パッキング効率最高化ステップにおいて用いられる。
【０１５８】
パッキング効率最高化ステップ５３０は、図１２と一致する形で実行することができる。このステップにおいては、選択された候補送信インスタンス３５は、以下の規則に従って送信フォーマットの変更を行うことができる。
【０１５９】
（１） 選択された候補送信インスタンス３５が単一ユーザーのデータを含む場合は、再選択されたフォーマットは、ユーザーのＤＲＣと適合する単一ユーザーフォーマット又はマルチユーザーフォーマットのいずれかであることが許容される。
【０１６０】
（２） 選択された候補送信フォーマットが２つ以上のユーザーのデータを含む場合は、再選択されたフォーマットは、他のマルチユーザーフォーマットでしかあることができない。いずれの場合においても、ペイロードを搬送できる最小フォーマットが選択される。この後変換は、幾つかのマルチユーザーフォーマットへの変換を回避することができるフラグによってさらに制御される。
【０１６１】
一実施形態においては、送信インスタンス３５をフォーマット化するステップ５１０は、単一搬送波スケジューラ２３が送信インスタンス３５のパッキング効率を最高にするステップ５３０と、単一搬送波スケジューラ２３が事前ＡＣＫ計算を行うステップ５３２と、をさらに含む。図１２参照。さらに、ステップ５３０は、図１３に示される方法を含むことができる。判断ブロック５４０において、送信インスタンス３５が最初に評価され、単一ユーザーフォーマットが用いられるかどうかが決定される。単一ユーザーフォーマットが用いられる場合は、５４２において、利用可能な最低レートの非カノニカル単一ユーザーフォーマットに変換する。その他の場合は、選択された送信インスタンス５４４に関して利用可能な最低レートマルチユーザーフォーマットを用いる。
【０１６２】
一実施形態においては、単一搬送波スケジューラ２３は、選択された送信インスタンス３５がデータビットを搬送することになる対象となるユーザーのＤＲＣに対応する最大スパンを決定する。単一搬送波スケジューラ２３は、指定された数の送信スロットをカウントする。送信された情報の正確な受信の確認応答をまだしていない、すなわちＡＣＫメッセージをまだ送信していないユーザーが存在する場合で、いずれかの待ち行列内に送信待ち状態のデータが存在する場合は、ＡＮは、送信を終了させる。
【０１６３】
代替実施形態は、図１０に示される方法５００を完了させるための特定の手段及び方法を含み、限定されることなしに、各候補送信インスタンス３５を生成するためのビットスタッフィングと、パケットメトリックの計算と、を含む。
【０１６４】
ステップ５０８においてパケットメトリック計算が実行され、ビットスタッフィングは、ステップ５０８の送信インスタンス３５をフォーマット化する一部である。一般的には、単一ユーザー送信インスタンスは、同じユーザーの１つ以上のフローからのビットをスタッフィングすることができる。“定義された”フォーマットを有するマルチユーザーインスタンス、例えば表１において定義されるマルチユーザーインスタンス、は、１つ以上のユーザーからのビットをスタッフィングすることができ、この場合は、該ユーザーは、マルチユーザーフォーマットと適合可能なＤＲＣを送信している。“導き出された”フォーマットを有するマルチユーザーインスタンスは、マルチユーザーフォーマットと適合可能なＤＲＣを送信し、“ソフト適合性”という追加要求を満たす１つ以上のユーザーからのビットをスタッフィングすることができる。ＤＲＣは、対応する“定義された”フォーマットを復号するための予想スロット数が導き出されたフォーマットのスパンよりも小さいか又は等しい場合に導き出されたマルチユーザーフォーマットにソフト適合可能であるとみなされる。予想スロット数は、（例えば平均白色ガウス雑音（ＡＷＧＮ）状態下において）受信されたＤＲＣに関して要求される信号対干渉雑音比（ＳＩＮＲ）を、導き出されたフォーマットを成功裏に復号するために要求されるＳＩＮＲと比較することによって得ることができる。代替として、予想スロット数は、要求されたレートを導き出されたフォーマットの有効データレートと比較することによって決定することができる。
【０１６５】
以下の説明では、ｉ）ＢＥ／ＡＦ、及び１つのＥＦクラスを含むＱｏＳクラスを仮定する。方法は、複数のＥＦクラスへの拡大を許容する。本実施形態により、待ち行列において待機中の各ビットは、以下の形の多項式として与えられるビットメトリックが割り当てられる。
【０１６６】
ｂｉ（ｚ）＝［ｈｉ２］ｚ−２＋［ｈｉ］ｚ−１＋［ｌｏ］                      （８）
ここで、ｉは、ビットのインデックスであり、３つの係数｛ｈｉ２，ｈｉ，ｌｏ｝のうちの１つのみがゼロ以外であることを許容される。この説明はビットレベルに関するものであるが、典型的には、ＩＰデータグラム内の全ビットが同じメトリックを有しており、パケットメトリック計算はビットレベルの累積を必ずしも含まないことに注目すること。
【０１６７】
ＥＦフローからのビットと関連づけられた現在の遅延をδとする。ｈｉ２及びｈｉに関して以下の定義を設定する。
【０１６８】
ｈｉ２＝βδ＋μ、  δ＞αＤｅｌａｙＢｏｕｎｄの場合                                （９）
及び
ｈｉ＝βδ＋μ、  δ≦αＤｅｌａｙＢｏｕｎｄの場合                                （１０）
ここで、βは、ＥＦフローと関連づけられたパラメータであり、遅延限度と反比例の関係であり、μは、大きい数であり、αは、固定されたスカラー（例えば０．２５）であり、ＥＦフロー型から独立している。
【０１６９】
ＢＥ／ＡＦフローに関して、ｌｏを以下のように設定する。
【数１】
2009528793.tif 000003
【０１７０】
ここで、ＡｖｇＴｈｒｏｕｇｈｐｕｔは、対応するユーザーの平均スループットであり、ＴｒｇｔＴｈｒｏｕｇｈｐｕｔは、そのユーザーに関する最低の希望されるスループットである。ＢＥユーザーに関しては、ＴｒｇｔＴｈｒｏｕｇｈｐｕｔはゼロに設定される。次に、パケットメトリック（例えば、スループット多項式）が以下のように得られる。
【０１７１】
ＰａｃｋｅｔＭｅｔｒｉｃ＝ＡｃｃｕｍｕｌａｔｅｄＢｉｔＭｅｔｒｉｃ／Ｎｇ
（１２）
ここで、Ｎｇは、考慮中の定義された又は導き出された候補送信インスタンス３５の一般的スパンであり、累積されたビットメトリック（ＡｃｃｕｍｕｌａｔｅｄＢｉｔＭｅｔｒｉｃ）は、候補インスタンス内に含まれている（又はスタッフィングされている）全ビットに対応するビットメトリックの合計である。値Ｎｇは、定義又は導き出された型の公称スパンに設定することができる。代替として、値Ｎｇは、１に設定することができ、その場合は、パケットメトリックは、累積されたビットメトリックに等しくなる。この場合は、スケジューラは、送信インスタンス当たりのスループットではなく送信インスタンス当たりのペイロードを最大化するように機能する。このことは、ＤＲＣの影響を受けなくなるという望ましくない影響を及ぼし、それによって劣化された性能を生じさせる可能性があり、該劣化は、図６に示される挙動に従わない場合がある。他の手法は、Ｎｇを“疑似スパン”に設定することであり、該“疑似スパン”は、１又は２スロット高レートパケットに関しては１に設定し、４スロットパケットに関しては４に設定し、以下同様であり、それによって、ペイロードに基づく高レートパケットを区別し、その一方でＮｇをより大きい値に設定することによって低レートフォーマットが断念されるようにすることができる。
【０１７２】
以下の特性は、高ジオメトリユーザーの方への偏りをスケジューラに提供する。
【０１７３】
（１） ＤＲＣがマルチユーザーフォーマットと適合する場合は、より低い公称データレートの全マルチユーザーフォーマットとも適合可能である。
【０１７４】
（２） スケジューラは、“スループット”多項式を選択デバイスとして使用する。
【０１７５】
１つの設計は、ビットメトリックに関するｈｉ及びｈｉ２係数を定義する際に大きい値μ項を用いる。μは全ビットに共通するため、ビットはβδの値に従って順にスタッフィングされる。パケットメトリックは、あたかもビットメトリックの対応するエントリが１つに変更されるかのように計算され、その結果スループット多項式に比例するパケットメトリックが得られる。この方法は、パケットメトリックの計算に関するパケットメトリック内におけるβδの影響を排除する。
【０１７６】
上述されるように、スケジューラは、固定されたＤｅｌａｙＢｏｕｎｄを全ユーザーに適用することに注目すること。典型的には、良好なカバレッジを経験中のユーザーは、ＤｅｌａｙＢｏｕｎｄのうちのわずかな部分のみを要求する。ユーザー数が増加するのに応じて、劣化は、最初に最も弱いユーザーから始まり、高いジオメトリにあるユーザーは、負荷による影響を強く受けない。
【０１７７】
一実施形態は、良好なＥＦユーザーの割合を測定することによって遅延限度及び関連パラメータ（例えば、α）を適応的に設定する。スケジューラによって用いられるＤｅｌａｙＢｏｕｎｄは、良好なユーザーの割合を希望されるレベルに維持するために繰り返し引き上げること又は引き下げることができる。一実施形態においては、ＤｅｌａｙＢｏｕｎｄに関するより低い限度を有する単純な一次ループが実装される。
【０１７８】
上述されるスケジューラにおいては、ＢＥ／ＡＦユーザーに関するビットメトリックを定義する方法は、以下の計算を用いる。
【０１７９】
ビットメトリック＝１／［ＡｖｇＴｈｒｏｕｇｈｐｕｔ−ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ］                        （１３）
異なるシステム、動作目標、及び設計に関してはその他のビットメトリック定義を実装することができる。
【０１８０】
送信フォーマット及びインスタンス
表１では、１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様及びＲｅｖ  Ａ．仕様においてそれぞれ定義される２組のプロトコル副型に関して、各ＤＲＣインデックスと適合するＦＬ送信フォーマットが記載されており、０ｘ０、０ｘ０、０ｘ１、及び０ｘ２のＤＲＣインデックスに関する適合可能マルチユーザーフォーマットを定義するＲｅｖ  Ａ．への最近の寄稿の変更案を含む。送信フォーマットは、Ｒｅｖ．Ａ仕様におけるように、３つ一組（ＰａｃｋｅｔＳｉｚｅ、Ｓｐａｎ、ＰｒｅａｍｂｌｅＬｅｎｇｔｈ）によって表される。“ＰａｃｋｅｔＳｉｚｅ”（パケットサイズ）は、送信フォーマットが搬送するビット数であり、ＣＲＣ及びテールを含む。パケットサイズは、単位がビットの物理層ペイロードサイズである。“Ｓｐａｎ”（スパン）は、送信インスタンスが順方向リンクにおいて採用する公称（例えば最大の）ビット数である。スパンは、そのフォーマットのパケットに関して送信することができる最大スロット数である。“ＰｒｅａｍｂｌｅＬｅｎｇｔｈ”（プリアンブル長） は、プリアンブルチップ総数である。プリアンブルチップ総数は、単位がチップのプリアンブル継続時間である。
【０１８１】
１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様におけるように、各ＤＲＣに関する“カノニカル”送信フォーマットは、ボールド体で示される。１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様は、単一ユーザー送信フォーマットのみを定義し、１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様内の一定の副型は、単一ユーザーフォーマット及びマルチユーザーフォーマットの両方を定義する。さらに、１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ内の各ＤＲＣインデックスに関して複数の送信フォーマットを定義することができる。ＡＴは、これらのフォーマットの各々においてパケットを受信することを試みる。マルチユーザーフォーマットは、その一意のＭＡＣインデックスによって識別される。すなわち、各マルチユーザーフォーマットに関するプリアンブルは、個別のウォルシュカバーを用いる。単一ユーザーフォーマットはすべて、ユーザーに割り当てられたＭＡＣインデックスを用いる。
【表１】
2009528793.tif 000004
【０１８２】
2009528793.tif 000005
【０１８３】
2009528793.tif 000006
【０１８４】
2009528793.tif 000007
【０１８５】
繰り返すと、送信インスタンスは、転送するために選択された１つ以上の待ち行列からの特定の組のビットを有する送信フォーマットを指す。候補送信インスタンス３５は、送信可能であるかどうかがスケジューラアルゴリズムによって評価される送信インスタンスである。マルチユーザー送信フォーマット（１０２４，４，２５６）、（２０４８，４，１２８）、（３０７２，２，６４）、（４０９６，２，６４）、及び（５１２０，２，６４）は、カノニカルマルチユーザー送信フォーマットと呼ばれる。マルチユーザー送信フォーマット（１２８，４，２５６）、（２５６，４，２５６）、及び（５１２，４，２５６）は、“非カノニカルマルチユーザーフォーマット”と呼ばれる。導き出された送信フォーマットは、あたかも早期終了によって定義されたフォーマットから得られたものとして、対応する定義されたフォーマットのスパンを公称値よりも小さい値に単純に設定することによって得られる。要約すると、送信フォーマット及びインスタンスは、カノニカル又は非カノニカルであること、単一ユーザー又はマルチユーザーであること、及び定義された又は導き出されたものであることができる。“公称スロット数”という用語は、定義された送信フォーマットに関する最大スロット数及び導き出された送信フォーマットに関する再定義された最大スロット数を指すために用いられる。
【０１８６】
スケジューリング手段及び方法に関する以下の説明は、様々な待ち行列において送信待ち状態のオクテットをあらゆる量（オクテット単位）だけサービングすることができる、オクテットに基づくスケジューリングを考慮する。典型的には、各フローは、少なくとも１つのデータ待ち行列として格納される。従って、各待ち行列は、関連づけられた特定のＱｏＳに関する要求事項を有する。データは、各待ち行列においてオクテットで格納される。ＦＬでの送信のために全オクテット未満のデータが送信インスタンス又は物理層パケット内に入れられるスケジューリングを行うことができる。
【０１８７】
一定のアプリケーションは、フレームに基づくスケジューリングを要求することができ、フレームに基づくスケジューリングにおいては、フローの（カプセル化された）データグラムが物理層パケット内においてフラグメンテーションなしでサービングされることに注目すること。オクテットに基づくスケジューリング手段及び方法は、フレームに基づくスケジューリングに拡張することも可能である。
【０１８８】
さらに、受付制御は、スケジューリングと密接に関連しており、受付制御は、現在のシステム負荷に基づいて及び既に受け付けられているフローに許容不能な劣化を生じさせずに着信フローに成功裏にサービングする（例えば、ＱｏＳ目標を達成させる）ことができるかどうかを予測することによって着信フローを受け付ける／拒否する働きをする。
【０１８９】
ＩＳ−８５６をサポートするシステムにおいては、各ユーザーに関するＦＬ送信データレートを決定するためにリンク適応化が用いられる。各ＡＴは、ＡＴがデータを受信できる最高データレートを示すデータ要求を送信する。データ要求は、ＤＲＣメッセージと呼ばれる。ＤＲＣメッセージフォーマットは、各々が送信フォーマットを指定する様々なＤＲＣインデックスを用いる。ＡＴは、ＤＲＣチャネルでＤＲＣメッセージを送信する。各々の有効なＤＲＣインデックスに関して、ＩＳ−８５６  Ｒｅｌ−０におけるＮＵＬＬ  ＤＲＣを除き、ユーザーにデータを搬送するためにＦＬでサービングすることができる１つ以上の単一ユーザー及びゼロ以上のマルチユーザー送信フォーマットが存在する。表１は、ＩＳ−８５６において定義されるＤＲＣインデックスの詳細を示す。さらに、表１は、各ＤＲＣインデックスに関する適合可能な送信フォーマットをさらに含む。
【０１９０】
１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様においては、各ＤＲＣインデックスに関して、適合可能な単一ユーザー送信フォーマットのうちの１つがそのＤＲＣに関するカノニカルフォーマットとして定義される。本明細書において用いられるように、ＤＲＣは、ＡＴによって要求されてＤＲＣインデックスによって識別される特定のフォーマットに対応することに注目すること。一般的には、ＡＴが所定のＤＲＣに対応するカノニカルフォーマットを用いて送信されたパケットを成功裏に復号した場合は、該ＡＴは、適合可能な非カノニカル単一ユーザーフォーマットのうちのいずれか又は適合可能なマルチユーザーフォーマットのうちのいずれかによって送信されたパケットも成功裏に復号する可能性が高い。ただし、ＤＲＣインデックス：０ｘ０、０ｘ１、及び０ｘ２は例外である。所定のＤＲＣと適合可能な幾つかのマルチユーザーフォーマットは、カノニカルフォーマットと比較してより大きいプリアンブル長を有することができるため、これらは結果的には必ずしもデータ処理利得にはならないことがある。
【０１９１】
いずれかのＤＲＣに関して、ＤＲＣインデックス０ｘ０と適合可能な全フォーマット及び０ｘ１及び０ｘ２のＤＲＣインデックスと適合可能なマルチユーザーフォーマットを除き、非カノニカルフォーマットのペイロードサイズは、典型的には、カノニカルフォーマットのペイロードサイズよりも小さいか又は等しい。さらに、非カノニカルフォーマットのスパンは、典型的には、カノニカルフォーマットのスパンよりも大きいか又は等しい。受信されている０ｘ０のＤＲＣインデックス（例えば、ＮＵＬＬレート要求）を送信したユーザーがいずれかのフォーマットでサービングされる場合は、一般的には、パケットが信頼できる形で受信される保証はない。さらに、０ｘ１及び０ｘ２のＤＲＣインデックスに関しては、適合可能マルチユーザー送信フォーマットのペイロードサイズ及びスパンはこの特性を満たさないため、これらのフォーマットは、十分に信頼できる受信を満たすことができない。
【０１９２】
さらに、受信されるＮＵＬＬ  ＤＲＣ（０ｘ０）を送信したユーザーへのサービスは、一定の条件に制限することができる。これらの条件は、設計によってシステム内に組み入れることができる。
【０１９３】
マルチユーザー送信フォーマットに関するＤＲＣ適合性規則の有用な特性は、所定のＤＲＣが所定のマルチユーザーフォーマットと適合可能である場合は、同じＤＲＣはより低いデータレートの全マルチユーザーフォーマットと適合可能であることである。
【０１９４】
送信インスタンスは、送信フォーマットとそのフォーマットのパケットによって搬送可能なデータオクテットのアイデンティティの組合せを指す（例えば、パケットがデータオクテットを搬送する先であるユーザーのＭＡＣインデックスの組及び正確にいずれのオクテットをパケットにおいて搬送すべきかを示す一組の対応待ち行列ポインタ）。
【０１９５】
候補パケット生成器２５（後述）は、一組の仮説的送信インスタンス３５を生成し、次に、ＦＬにおいて送信するためにこれらのインスタンスのうちの１つを選択する。このように、幾つかの候補パケットの中から１つが送信のために選択される。これらの仮説的送信インスタンスのうちのいずれかを指すために本明細書において用いられる用語は、“候補送信インスタンス３５”である。
【０１９６】
スケジューラメトリック
以下は、順方向リンクスケジューラによって用いられる３つの型のメトリックの定義である（そのうちの一実施形態が以下の図１６において示される）。これらのメトリック型は、ｉ）ビットスタッフィング、ｉｉ）ビット及びｉｉｉ）パケットである。これらのメトリック型は、現在の送信インスタンス内に組み入れる資格を有する待ち行列を選択するために用いられる。簡単に要約すると、ビットスタッフィングメトリックは、様々な待ち行列内において送信待ちの状態であるオクテット（ビット）が所定の候補送信インスタンス３５内に含められる順序を決定する。
【０１９７】
パケットメトリックに関しては、候補送信インスタンス３５が生成された時点で、その候補３５に関するパケットメトリックが計算され、一組の同様に生成された候補送信インスタンス３５の中で勝利した候補送信インスタンスを選択するために用いられる。すなわち、候補パケット生成器２５は、一組の同様に生成された候補送信インスタンス３５の中から、マスタースケジューラ１０に提示すべきパケットとして選択する。候補送信インスタンス３５のパケットメトリックは、候補送信インスタンス３５に含まれているすべてのオクテットのビットメトリックを単純に合計し、候補送信インスタンス３５の送信フォーマットのスパンで前記合計を割ることによって決定される。
【数２】
2009528793.tif 000008
【０１９８】
ここで、ｋは、一組の代替候補送信インスタンスのうちの特定の候補送信インスタンス３５に関するインデックスを表し、Ｓｐａｎ［ｋ］は、対応する送信フォーマットに関して定義されたスパンを表し、Ｐ［ｋ］は、候補送信インスタンス３５に含まれているオクテットの組を表し、ＢｉｔＭｅｔｒｉｃ［ｉ］は、候補インスタンス３５に含まれているｉ番目のオクテットのビットメトリックを表す。
【０１９９】
従って、パケットメトリックは、候補送信インスタンス３５がＦＬにおいて実際にサービングされた場合における“ビットメトリックの瞬間的スループット”の推定値であると解釈することができる。
【０２００】
一般的には、オクテットテックｉのビットスタッフィングメトリックが他のオクテットｊのビットスタッフィングメトリックよりも大きい場合は（オクテットは、異なる待ち行列からのオクテットであることができる）、オクテットｉのビットメトリックは、オクテットｊのビットメトリックよりも大きいか又は等しく設定することができる。同様に、オクテットｉのビットメトリックが他のオクテットｊのビットメトリックよりも大きい場合は、オクテットｉのビットスタッフィングメトリックは、オクテットｊのスタッフィングメトリックよりも大きいか又は等しく設定すべきである。すなわち、
BitMetric[i] > BitMetric[j] ⇒BitStuffingMetric[i]≧BitStuffingMetric[j]
BitStuffingMetric[i] > BitStuffingMetric[j] ⇒BitMetric[i]≧BitMetric[j]
この一般的方法は、候補送信インスタンス３５内にスタッフィングされるオクテットがのちにスタッフィングされる他のオクテットと少なくとも同じ量だけパケットメトリックに寄与することを保証する。
【０２０１】
一般的メトリック構造
前節において説明されるすべての３つの型のメトリックは、以下のように多項式の形で表すことができる。
【０２０２】
メトリック＝［ＭＣ０］＋［ＭＣ１］ｘ＋［ＭＣ２］ｘ２＋［ＭＣ３］ｘ３＋［ＭＣ４］ｘ４＋［ＭＣ５］ｘ５＋［ＭＣ６］ｘ６＋［ＭＣ７］ｘ７            （１５）
ここで、メトリックは、３つのメトリック型のうちのいずれかであることができ、ＭＣ０，．．．ＭＣ７は、後述されるメトリック係数を表す。
【０２０３】
２つのメトリックの加算及びスカラーによるメトリックの乗算（又は除算）の各演算は、通常の多項式代数におけるように定義され、２つのメトリックが合計されるときに、２つの多項式の対応する係数が合計される。メトリックがスカラーによって乗算（除算）されるときに、係数の各々が同じスカラーによって乗算（又は除算）される。この演算は、方程式（１３）を介してビットメトリックを用いてパケットメトリックを計算することを可能にする。
【０２０４】
比較演算子“＞，≧，＝＝，≦，＜”は、辞書方式で定義され、例えば、２つのメトリックが比較されるときには、最初に最高次の項の係数が比較される。等しい場合は、次の最高次の項の係数が比較され、以下同様である。２つの多項式表現のすべての対応する係数が等しい場合は、２つのメトリックは等しい。これらの比較演算は、パケットメトリックを比較するのと同様にビットスタッフィングメトリックを比較するために用いられる。
【０２０５】
ビットメトリック及びビットスタッフィングメトリック
本節においては、ビットメトリック及びビットスタッフィングメトリックの意味、用法及び実装が説明される。ビットメトリック及びビットスタッフィングメトリックに関して、対応する多項式表現の１つの項のみがいずれかの所定の時点においてゼロ以外になることが許容される。非ゼロ項の次数は、所定のオクテットに関するビットメトリック及びビットスタッフィングメトリックに関して同じである。通常は対応する係数の名前及びＭＣ０，．．．ＭＣ７で呼ばれるこの非ゼロ項の次数は、ビット（スタッフィング）メトリック（又は対応するオクテット）の優先度状態と呼ばれる。比較演算の定義は、ＭＣ０項が最低優先度のオクテットに対応し、ＭＣ７項は最高優先度のオクテットに対応することを意味する。
【０２０６】
オクテットｉに関するビット（スタッフィング）メトリックの優先度状態は、与えられたオクテットによって被る現在の遅延によって及びオクテットが属するフローに関して定義された優先度しきい値と呼ばれる順序が設定されたしきい値の組を用いて以下のように決定される。
【０２０７】
ＣｕｒｒｅｎｔＤｅｌａｙ［ｉ］＝ＣｕｒｒｅｎｔＴｉｍｅ−ＴｉｍｅＳｔａｍｐ［ｉ］
（１６）
方程式（１６）において、ＴｉｍｅＳｔａｍｐ［ｉ］は、オクテットｉに関する適切に定義されたタイムスタンプである。優先度しきい値によって定義された各間隔は、優先度状態にマッピングされる。優先度しきい値及びこのようにして定義された間隔の優先度状態へのマッピングは、各フローに関して別々に候補パケット生成器２５に対して指定することができる。オクテットｉのＣｕｒｒｅｎｔＤｅｌａｙ［ｉ］がこれらの順序が設定されたしきい値の組と比較されて該当する間隔が決定される。この決定は、逆に、ビット（スタッフィング）メトリックの優先度状態を定義する。
【０２０８】
上記動作は、各フローに関するＭの優先度しきい値及びＭ＋１の優先度状態を定義する。Ｍの値は、ソフトウェア実施形態においては２に設定される。従って、各フローに関して、２つの優先度しきい値及び３つの優先度状態が定義される。これらのしきい値及び状態は、典型的には、フローの寿命中は不変である（ただし、該当するＤＳＰ−Ｄｒｉｖｅｒコマンドによって動作中に変更することができる）。
【０２０９】
スループットの影響を受けやすいトラフィックフローに関しては、ビットメトリックは以下に設定される。
【数３】
2009528793.tif 000009
【０２１０】
及び、ビットスタッフィングメトリックは以下に設定される。
【数４】
2009528793.tif 000010
【０２１１】
ここで、ＧｏＳＦａｃｔｏｒは、複数のフロー間において様々なレベルのサービス等級を提供するために用いられる、１つのフローに基づく定義されたパラメータである。
【０２１２】
ＡｖｇＴｈｒｏｕｇｈｐｕｔは、フローのフィルタリングされた（平均された）総スループットであり、フローのＦＴｘ、ＲＴｘ、及びＤＡＲＱ待ち行列を含む。６００スロット（１秒）等の時定数を有する一次ＩＩＲフィルタが平均を求めるために用いられる。ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔは、１つのフローに基づく定義されたパラメータである。Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭは、１つのフローに基づく定義されたパラメータである。Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭは、１つのフローに基づく定義されたパラメータである。εは、非常に小さい正数を表す。
【０２１３】
スループットの影響を受けやすいトラフィックフローに関しては、ビットメトリックは以下に説明されるように計算される。
【０２１４】
遅延の影響を受けやすいフローのビットスタッフィングメトリックに関しては、優先度状態に関する多項式係数は、以下のように設定される。
【０２１５】
ＤＳＢＳＭ＝ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒ＊ＣｕｒｒｅｎｔＤｅｌａｙ＋ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔ    （１９）
ここで、ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒは、１つのフローに基づく定義されたパラメータである。該パラメータの主目的は、異なるフローに関して異なる可能性があるＤｅｌａｙＢｏｕｎｄを正規化することである。一例として、２つの異なるオンラインゲームを考慮する。これらの２つのアプリケーションの特徴が異なることに起因して、これらの２つのアプリケーションは、異なるＤｅｌａｙＢｏｕｎｄ設定値がスケジューラに指定されることがあるが、このことは、一方のゲームが他方のゲームよりも高い優先度を有することは意味しない。単一搬送波スケジューラ２３が両方のアプリケーションを同等の優先度で取り扱うことが望ましいことがある。第１のゲームが３００ｍｓの遅延限度を有し、第２のゲームが１５０ｍｓの遅延限度を有すると仮定する。これで、いずれの時間においても、１５０ｍｓよりも古い第２のゲームに属するオクテットは（スケジューラが捨てるため）存在しない。しかしながら、１５０ｍｓよりも古い第１のゲームに属するオクテットが存在する可能性がある。ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒがない場合は、結果的に第１のゲームのオクテットが第２のゲームのオクテットよりも優先されることになる。各アプリケーションのＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒを各々のＤｅｌａｙＢｏｕｎｄ設定値に反比例するように設定することによって、この希望されない影響を正規化することができる。
【０２１６】
ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒは、１つのフローに基づく定義されたパラメータである。その値は、方程式（７）の右辺の第１の項がとることを許容された最大値の整数倍数に設定することができる（この最大値は、フローから独立しており、ソフトウェア実装によって決定される）。このことは、フローのソフト優先順位設定のための手段を提供することができる。一例として、２つのフロー、ゼロのＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔを有するフロー及び正のＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔを有する他方のフローのうちで、（両フローが所定の候補インスタンス３５の送信フォーマットとＤＲＣ適合可能であると仮定して）後者のフローのオクテットが、前者のフローのオクテット前に候補送信インスタンス３５内に含められる。
【０２１７】
上記のソフトな優先順位設定概念は、２つのフローのビットスタッフィングメトリックの優先度状態を別々に設定することによって達成させることができる厳しい優先順位設定と対照的である。ビットメトリックに関して、優先度状態に関する多項式係数は、以下のように一定値に設定される。
【０２１８】
ＤＳＢＳＭ＝ＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅ    （２０）
ここで、ＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅは、１つのフローに基づく定義されたパラメータである。その目的は、次の２つである。第１に及び最も重要なことに、前記パラメータは、ソフトな優先順位設定に関して用いることができる。第２に、優先度が等しいとみなされる２つのアプリケーションが（インターネットから待ち行列への）異なる平均着信スループットを有する場合は、各フローに関するＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅは、より高いスループットを有するアプリケーションがＦＬパケットを効率的に満たすためのより多くのデータを単に有することによって優先されるのを回避するために、フローの典型的スループットと反比例関係になるように設定することができる。
【０２１９】
各トラフィックフローは、ＦｌｏｗＣｌａｓｓパラメータに基づいてスループットの影響を受けやすいクラス又は遅延の影響を受けやすいクラスに分類される。次に、ビットメトリックＭＣＸ（ここで、Ｘは、｛０，．．．，７｝）の要素である）は以下のように定義される。
【数５】
2009528793.tif 000011
【０２２０】
同様に、ビットスタッフィングメトリックは以下のように定義される。
【数６】
2009528793.tif 000012
【０２２１】
継続中のソフトウェア実施形態において、ビットスタッフィングメトリックは、［Ｂ１５．．．Ｂ０］で表すことができる１６ビット量によって表される。３つの最上位ビットは、優先度状態を決定する（例えば、“０００”はＭＣ０にマッピングし、“１１１”はＭＣ７にマッピングする）。残りの１３の最下位ビットは、係数値自体を保持する。この表現により、ビットスタッフィングメトリック間の比較演算は、これらの１６のビット量間において直接行うことができる。
【０２２２】
ビットメトリックは、ソフトウェア実装においては明示されない、その理由は、すべての必要情報をビットスタッフィングメトリックから導き出すことができるためである。ビットメトリックの優先度状態は、ビットスタッフィングメトリックの優先度状態と同じである。
【０２２３】
パケットメトリック
候補送信インスタンス３５のパケットメトリックは、方程式（１）を用いて計算される。オクテットのビットメトリックの１つの項のみがゼロ以外であることができる場合でも、一般的にはその結果得られるパケットメトリックの全係数がゼロ以外であることができる点に注目すること。
【０２２４】
実装単純化
ビット（スタッフィング）メトリックに関する上記の説明は、各待ち行列内の各オクテットにはスロットごとに再計算される個々のビット（スタッフィング）メトリックが割り当てられる一般的事例を考慮した。代替実施形態は、該計算の複雑さを引き下げる。その他のメカニズムのおかげでタイムスタンプによって待ち行列の順序が設定されると仮定すると、フローの全待ち行列の待ち行列先頭オクテットの間で最も古いタイムスタンプに基づいてフロー当たり１つのビット（スタッフィング）メトリックを計算するのは合理的なことである。このビット（スタッフィング）メトリックは、フローの現在待機状態のオクテットに関して用いることができる。この単純化は、ビット（スタッフィング）メトリックがオクテットのＣｕｒｒｅｎｔＤｅｌａｙの単調増加関数であると仮定している。そうでない場合は、待ち行列先頭オクテットは連続するオクテットがサービングされるのを妨げるリスクが存在する。この単純化により、ビットスタッフィングメトリックは、フローメトリックと呼ぶこともできる。
【０２２５】
さらに、フローのＲＸｘ待ち行列において送信待ち状態の待ち行列先頭オクテットは、ＦＴｘ待ち行列及びＤＡＲＱ待ち行列において送信待ち状態である待ち行列先頭オクテットよりも古い可能性がある。同様に、ＤＡＲＱ待ち行列において送信待ち状態の待ち行列先頭オクテットは、ＦＴｘ待ち行列の待ち行列先頭オクテットよりも古い可能性がある。この理由により、これらの３つの待ち行列の中で最も古いタイムスタンプを見つけ出すのではなく、ＲＴｘ、ＤＡＲＱ、次にＦＴｘ待ち行列の固定された順序を用いて、フローに関するビット（スタッフィング）メトリック計算において用いられるタイムスタンプを決定するための第１の空でない待ち行列を見つけ出すことが可能である。フローの待ち行列も、ＲＴｘ、ＤＡＲＱ、次にＦＴｘの順にサービングすべきである。
【０２２６】
単一搬送波スケジューラ
単一搬送波スケジューラ２３は、ＦＬが新たな送信に関して利用可能であるときに常に実行される。しかしながら、幾つかの実装上の課題は、利用可能でないスロットを含むすべてのスロットにおいて計算の一部が実行されるようにすることができる。この理由は、ＦＬを新たな送信に関して利用可能であるとＡＮが決定するときまでに、通常は送信インスタンス３５を決定するために単一搬送波スケジューラ２３に関わる全計算を行うための多くの時間が残されていないためである。
【０２２７】
図１５の流れ図９００に示される以下のステップは、単一搬送波スケジューラ２３によって実行することができ、単一搬送波スケジューラ２３は、順方向リンクスケジューラ２０の論理的ブロック図を例示する図１６Ａに示される候補パケット生成器２５において（例えば、メモリ２７に格納されたソフトウェア命令２９の形で）常駐することができる。ステップ９１０は、一組の候補パケット送信インスタンスを生成する。ステップ９２０は、前記組内の中から１つの候補パケットを選択する。ステップ９３０は、パッキング効率を最高にする。ステップ９４０は、事前確率を計算する（例えば、パケット９２０を成功裏に復号しているＡＴの事前確率を計算する）。上記ステップの各々が以下の４つの節においてそれぞれ説明される。
【０２２８】
一組の候補パケット送信インスタンスの生成（９１０）
単一搬送波スケジューラ方法を実行時に候補パケット生成器２５によって実行される第１のステップは、候補パケット送信インスタンス（３５）のリストを生成することである９１０（図１０及び１１においてはステップ５０４として示される）。より具体的には、次の候補送信インスタンス３５が生成される。すなわち、単一ユーザーフォーマットを有する候補の単一ユーザー送信インスタンス３５が、送信待ち状態のデータを有している（何らかの理由で、例えば継続問題を理由として、プロトコル副型によってサービスが現在禁止されていない）各ユーザーに関して生成される。さらに、ユーザーからの受信されたＤＲＣは、非ＮＵＬＬである。その他の場合は、ユーザーは、１つ以上の送信フォーマットがＮＵＬＬ  ＤＲＣに基づいてサービングされることを可能にするＭＡＣ層プロトコルを交渉済みである。受信されているＮＵＬＬ  ＤＲＣを送信したユーザーに関して候補パケット送信インスタンス３５が生成される場合は、候補送信インスタンス３５は、有限ＤｅｌａｙＢｏｕｎｄを有するフローに属しさらに該フローのＦＴｘ待ち行列からのデータを搬送する。候補送信インスタンス３５の送信フォーマットは、表１において詳細に示されるようにユーザーのＤＲＣに対応するカノニカルフォーマットである。
【０２２９】
一実施形態においては、マルチユーザー候補送信インスタンス３５は、５つのマルチユーザー送信フォーマット、（１０２４，４，２５６）、（２０４８，４，１２８）、（３０７２，２，６４）、（４０９６，２，６４）、及び（５１２０，２，６４）の各々に関して生成することができる。１５３．６Ｋｂｐｓ以上を要求したユーザーのみが、マルチユーザーフォーマットでサービングされる。さらに、ユーザーのＤＲＣは、候補パケット送信インスタンス３５のフォーマットと適合可能である。さらに、マルチユーザー候補送信インスタンス３５は、次の条件のうちの１つ又は両方を満たし、その他の場合は捨てられてさらなる考慮が行われず、２つ以上のユーザーのデータ、又はＤＲＣが消去された少なくとも１つのユーザーのデータ、を搬送する。上記の２つのグループのうちのいずれかのグループにおける候補パケット送信インスタンス３５は、１つ以上のフローからのビットをスタッフィングすることによって生成され、
１）   単一ユーザーフォーマットには、同じユーザーのフローからのビットがスタッフィングされる。
【０２３０】
２）   マルチユーザーフォーマットには、適合可能なＤＲＣを有するユーザーのフローからのビットがスタッフィングされる。
【０２３１】
ビットスタッフィングは、ビットスタッフィングメトリックの降順で行われる。上述されるように、計算上の要求に起因して、１つのフロー当たり１つだけのビットスタッフィングメトリックが計算され、次に、フローの全待ち行列内におけるすべての現在送信待ち状態のオクテットに関して用いられる。この場合は、ビットスタッフィングメトリックは、最初にいずれのフローにサービングするかを決定するのに役立つが、所定のフローのオクテットにどのようにサービングするかは決定することができない。ここでは、フローの待ち行列（特に、初めて送信された（ＦＴｘ）待ち行列であるが必ずしもＲＴｘ／ＤＡＲＱ待ち行列ではない）内において送信待ち状態のオクテットはタイムスタンプ順に現れ、フローのオクテットは待ち行列内において現れる順序でサービングされると仮定される。
【０２３２】
上述されるように、各フローは、複数の待ち行列を有することができ、最初に送信されたデータ（ＦＴｘ）に関する１つの待ち行列、及び再送信に関するその他の待ち行列（ＲＬＰ再送信に関するＲＴｘ待ち行列及び／又はＭＡＣ層再送信に関するＤＡＲＱ待ち行列）である。フローが空でない再送信（ＲＴｘ）及び／又はＤＡＲＱ待ち行列を有する場合は、フローに関するビットスタッフィングメトリックは、いずれかの空でないＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列のうちで待ち行列先頭のタイムスタンプのうちの最も古いタイムスタンプに基づいて計算することができる。フローの全待ち行列に関して１つのビットスタッフィングメトリックのみが計算される。所定のフローからのビットスタッフィングは、ＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列のうちで待ち行列先頭のタイムスタンプの昇順に基づいて行うこともできる。
【０２３３】
フローの待ち行列に関する上述されるタイムスタンプに基づく順序設定は、ＲＴｘ／ＤＡＲＱ／ＦＴｘ待ち行列の固定順序として概算することができる。
【０２３４】
候補パケット送信インスタンス３５を生成する際には、非カノニカル単一ユーザーフォーマット及び１０２４未満のビットを搬送する短いマルチユーザーフォーマットは考慮されない。これらのフォーマットは、スケジューラ２３のパッキング効率最高化ステップ９３０において考慮される。考慮されない理由の一部は、次の通りである。すなわち、ｉ）複雑さを低減させる、ｉｉ）１つのパケット当たり可能なかぎり多くのデータをパッキングする、ｉｉｉ）弱いチャネル状態を有するユーザーを避ける、及びｉｖ）短いパケットを効率的に充填することによって数多くのデータが相対的優先度を得る。
【０２３５】
この段階において非カノニカルパケット及び短いパケットを考慮しない他の理由は、フレームに基づくスケジューリングにおいて生じる可能性がある一定の量子化の影響を回避することが関わる。
【０２３６】
マルチユーザー候補送信インスタンス３５を生成する際には、連続性問題の潜在的な悪影響を軽減するためにさらなる予防措置を講じることが可能である。１つの該方法は、第１のマルチユーザーパケットの開始後の（所定のインターレースにおいてカウントされた）一定のスロット数の間、前に開始されて終了されたマルチユーザーパケットを有する同じインターレースにおいてマルチユーザーパケットをサービングするのを回避することである。このスロット数は、２つのマルチユーザーパケットのスパンのうちの最も小さいスパン又は第１のマルチユーザーパケットのスパンに設定することが可能である。この手法は、ユーザーが新たなマルチユーザーパケットにおいてサービングされる資格を素早く得るのを可能にし、それによって無資格状態が長時間続くのを回避するのに役立つ。
【０２３７】
組内において１つの候補パケットを選択する（９２０）
単一ユーザー及びマルチユーザー候補パケット送信インスタンス３５のリストが上述されるように生成された後、次のステップは、ステップ９１０（図１０ではステップ５０８として示される）において（上記の生成されたリストには少なくとも１つの候補送信インスタンス３５が含まれると仮定して）これらの候補パケット３５のうちの少なくとも１つを選択することである。この選択は、リスト内の各々の候補３５に関するパケットメトリックを計算し、最大のパケットメトリックを有する候補パケット３５を勝利候補３５として選択することによって行われる。引き分けになった場合は、マルチユーザーフォーマットよりも単一ユーザーフォーマットを優先させることが望ましい。さらに、より低いレートのマルチユーザーフォーマットよりもより高いレートのマルチユーザーフォーマットを選択するのが望ましい。
【０２３８】
パッキング効率を最高にする（９３０）
このステップにおいては、搬送するために選択されたデータオクテットの組を変更せずにパッキング効率を最高にし（それによってＡＲＱ利得を提供する）ために、勝利した候補送信インスタンス３５の送信フォーマットが再考されて（可能なことに変更される）、ステップ９３０（図１０においてはステップ５１０として示される）。このステップの完了は、ＡＲＱ利得を提供することができる。
【０２３９】
勝利した候補送信インスタンス３５が単一ユーザーフォーマットである場合は、フォーマットは、選択されたデータオクテットを搬送することができるサービングされたユーザーのＤＲＣと適合可能な最低レート非カノニカル単一ユーザーフォーマットに変換することができる。（図１３においてはステップ５４２として示される）。単一ユーザー送信インスタンス３５のフォーマットをマルチユーザーフォーマットに変換することも可能である。スケジューラの選択ステップにおける勝利した候補送信インスタンスがマルチユーザーフォーマットである場合は、（１０２４，４，２５６）フォーマットをこれらの３つのフォーマット（｛１２８，２５６，５１２｝，４，２５６）のうちのいずれかに変換する（選択されたデータオクテットを搬送できる最低レートフォーマットが用いられる）。ＡＴ内部の適応型レート制御メカニズムは、単一ユーザーパケットをサポートするように適合化させることができる点が注目される。
【０２４０】
事前確率を計算する（９４０）
このステップ（図１２においてはステップ５３２として示される）においては、単一搬送波スケジューラ２３は、送信インスタンス３５においてサービングされた全ユーザーからのＡＣＫを検出できない場合でも、送信インスタンス３５を送信する際の上限となる最大スロット数（選択された送信インスタンス３５の公称スパンよりも小さい）を決定することができる。このステップは、オプションである。このステップは、ＡＮがパケットにおいてサービングされた全ユーザーからのＡＣＫを検出後に、又はパケットの全スパンを送信後にパケット送信を終了するようにオフにすることができる。このステップを実装する一方法は、送信インスタンスの最大スロット数を以下のように設定することである。
【数７】
2009528793.tif 000013
【０２４１】
ここで、ＳｃｈｅｄｕｌｅｄＴｘＦｏｒｍａｔＳｐａｎは、スケジューリングされた送信フォーマットのスパンであり、ＤＲＣＳｐａｎ［ｉ］は、パケット内のｉ番目のサービングされたユーザーからの復号されたＤＲＣに対応するカノニカル送信フォーマットのスパンである。
【０２４２】
上記では、スケジューラによって利用されるパラメータのうちの一部が説明されている。ここでは、ＤＳＰ−Ｄｒｉｖｅｒインタフェースにおいてスケジューラに提供されるパラメータが提示される。グローバルパラメータは、全フローに適用されるパラメータを指し、フローパラメータは、各フロー関して別々に指定されたパラメータを指す。
【０２４３】
１．   グローバルパラメータ
ａ．ＦｌｏｗＴＰｕｔＦｉｌｔｅｒＴｉｍｅＣｏｎｓｔ−各フローに関して保持される変数である平均スループット、ＡｖｇＴｈｒｏｕｇｈｐｕｔ、を生成するために用いられる一次ＩＩＲフィルタの時定数を定義する。フィルタは、各スロットごとに１回繰り返される。フィルタへの入力は、そのスロットにおいて開始するパケット内の所定のフローの待ち行列からサービングされるオクテット数である。フィルタは、新たなパケット送信が開始しないゼロがスロットに入力されて更新される。
【０２４４】
ｂ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭ−ビットメトリックの計算を目的としてスループットの影響を受けやすいメトリックから遅延の影響を受けやすいメトリックに変換するための変換係数。
【０２４５】
ｃ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭ−ビットスタッフィングメトリックの計算を目的としてスループットの影響を受けやすいメトリックから遅延の影響を受けやすいメトリックに変換するための変換係数。
【０２４６】
ｄ．ＦｌｏｗＣｌａｓｓ−フローがスループットの影響を受けやすい型か又は遅延の影響を受けやすい型かを説明する。
【０２４７】
ｅ．ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓｕｒｅＭａｐｐｉｎｇ−ＤＲＣ消去マッピング方法によって用いられる。
【０２４８】
ｆ．ＥｒａｓｕｒｅＭａｐｐｉｎｇＴｈｒｅｓｈｏｌｄ−ＤＲＣ消去マッピング方法によって用いられる。
【０２４９】
２．フローパラメータ
ａ．ＵｓｅｒＩｄ，ＦｌｏｗＩｄ−各フローのオーナーをインデキシング及び決定するための手段を提供する。
【０２５０】
ｂ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ，ＰｒｉｏｒｉｔｙＴｈｏｌｄ［２］−これらのパラメータは、ビット（スタッフィング）メトリックの優先度状態を現在の遅延の関数として説明する。ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］配列の要素は、変数ＤｅｌａｙＴｈｏｌｄ及びＱｏＳＭｅｔｒｉｃＳｔａｔｅを含む構造である。フローのＣｕｒｒｅｎｔＤｅｌａｙがＰｒｉｏｒｉｔｙＴｈｏｌｄ［０］．ＤｅｌａｙＴｈｏｌｄよりも小さい場合は、優先度状態はＱｏＳＭｅｔｒｉｃＳｔａｔｅに設定される。ＣｕｒｒｅｎｔＤｅｌａｙがＰｒｉｏｒｉｔｙＴｈｏｌｄ［０］．ＤｅｌａｙＴｈｏｌｄよりも大きいがＰｒｉｏｒｉｔｙＴｈｏｌｄ［１］．ＤｅｌａｙＴｈｏｌｄより小さい場合は、優先度状態はＰｒｉｏｒｉｔｙＴｈｏｌｄ［０］．ＱｏＳＭｅｔｒｉｃＳｔａｔｅに設定される。ＣｕｒｒｅｎｔＤｅｌａｙがＰｒｉｏｒｉｔｙＴｈｏｌｄ［１］．ＤｅｌａｙＴｈｏｌｄよりも大きい場合は、優先度状態はＰｒｉｏｒｉｔｙＴｈｏｌｄ［１］．ＱｏＳＭｅｔｒｉｃＳｔａｔｅに設定される。ＱｏＳＭｅｔｒｉｃＳｔａｔｅ変数は、｛ＭＣ０，．．．，ＭＣ７｝の優先度状態に対応する値｛０，．．．，７｝をとる。
【０２５１】
ｃ．ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒ
ｄ．ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔ
ｅ．ＤｅｌａｙＢｏｕｎｄ−０は、無限大を表す（オクテットをサービングする前に該オクテットを捨てない）。その他の場合は、経過後は所定のオクテットが待ち行列から捨てられるオクテットのタイムスタンプに関する遅延量を表す。
【０２５２】
ｆ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ−スループットの影響を受けやすいフローのビット（スタッフィング）メトリックにおいて用いられるパラメータ。
【０２５３】
ｇ．ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘ−ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘが０に設定されたフローは、スケジューラによって統合されない。その他の場合は、ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘの値が同じ（非ゼロ）であるフローがスケジューラにおいて統合される。ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘの適用範囲は、ユーザーに限定され、例えば同じインデックスを混乱なく他のユーザーのフローに関して再度用いることができる。
【０２５４】
ｈ．ＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙ−（スケジューラによって）統合されたフロー内の寄与フロー（ｃｏｎｔｒｉｂｕｔｉｎｇ  ｆｌｏｗ）がＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙの順序でサービングされる。同じＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙを有する寄与フローの間では、寄与フローのタイムスタンプによって順序が決定される。
【０２５５】
ｉ．ＧｏＳＦａｃｔｏｒ−フロー間におけるサービス等級レベルを提供するために用いられる。
【０２５６】
ｊ．ＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅ−ＭＣＸ内の優先度状態におけるビットメトリック係数値。
【０２５７】
ＤＳＰ−Ｄｒｉｖｅｒインタフェースにおいては、フローは、ＢＥ、ＡＦ、ＥＦとして指定できず、さらにいずれのその他の高レベル記述子によっても指定できないことに注目すること。むしろ、ＤＳＰ−Ｄｒｉｖｅｒインタフェースは、全フローに関して一様な低レベル記述を用いる。より高いレベル、例えばＢＳＣ、においては、フローの特定の高レベル記述子、例えばＱｏＳ要求事項及びＢＥ／ＥＦ／ＡＦカテゴリ分類等、が各フローに関するＤＳＰ−Ｄｒｉｖｅｒインタフェースにおいて定義される基本パラメータにマッピングされる。該マッピングテーブルは、構想可能なフロー型に関して十分なシミュレーション及び試験によって生成される。
【０２５８】
以下は、様々なパラメータの使用を示す例である。ＢＥフローに関しては、以下のパラメータを用いることができる。
【０２５９】
ａ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝０（ＭＣ０）
ｂ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝｛ａｎｙ，ａｎｙ｝
ｃ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＤｅｌａｙＴｈｏｌｄ＝｛０，０｝（無限大）
ｄ．ＤｅｌａｙＢｏｕｎｄ＝０（無限大）
ｅ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ＝０
ｆ．ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘ＝１（ユーザーの全ＢＥフローを統合する）
ｇ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭ＝１６
ｈ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭ＝１２８
ｉ．ＦｌｏｗＣｌａｓｓ＝ＴｈｒｐｕｔＳｅｎｓｉｔｉｖｅ
ｊ．ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓｕｒｅＭａｐｐｉｎｇ＝０
ｋ．ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｏｌｄ＝０｛無限大｝
ＡＦフローに関しては、以下のパラメータを用いることができる。
【０２６０】
ａ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝０（ＭＣ０）
ｂ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝｛ａｎｙ、ａｎｙ｝
ｃ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＤｅｌａｙＴｈｏｌｄ＝｛０，０｝（無限大）
ｄ．ＤｅｌａｙＢｏｕｎｄ＝０（無限大）
ｅ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ＝正値
ｆ．ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘ＝０（統合なし）
ｇ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭ＝１６
ｈ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭ＝１２８
ｉ．ＦｌｏｗＣｌａｓｓ＝ＴｈｒｐｕｔＳｅｎｓｉｔｉｖｅ
ｊ．ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓｕｒｅＭａｐｐｉｎｇ＝０
ｋ．ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｈｏｌｄ＝０｛無限大｝
ＥＦフローに関しては、以下のパラメータを用いることができる。
【０２６１】
ａ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝０（ＭＣ０）
ｂ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＱＯＳＭｅｔｒｉｃＳｔａｔｅ＝｛２，３｝
ｃ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＤｅｌａｙＴｈｏｌｄ＝｛０．２５＊ＤｅｌａｙＢｏｕｎｄ，０．５＊ＤｅｌａｙＢｏｕｎｄ｝
ｄ．ＤｅｌａｙＢｏｕｎｄ＝アプリケーションに依存
ｅ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ＝０
ｆ．ＦｌｏｗＡｇｇｒｅｇａｔｅＩｎｄｅｘ＝０（統合なし）
ｇ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭ＝１
ｈ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭ＝１
ｉ．ＦｌｏｗＣｌａｓｓ＝ＤｅｌａｙＳｅｎｓｉｔｉｖｅ
ｊ．ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓｕｒｅＭａｐｐｉｎｇ＝１
ｋ．ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｏｌｄ＝０．２５＊ＤｅｌａｙＢｏｕｎｄ
シグナリングフローは以下のように提供される。
【０２６２】
ａ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ＝７（ＭＣ７、最高優先度）
ｂ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＱＯＳＭｅｔｒｉｃＳｔａｔｅ＝｛７，７｝
ｃ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［］．ＤｅｌａｙＴｈｏｌｄ＝｛０，０｝（無限大）
ｄ．ＤｅｌａｙＢｏｕｎｄ＝０（無限大）
ｅ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ＝０
ｆ．ＡｇｇｒｅｇａｔｅＩｎｄｅｘ＝０（統合なし）
ｇ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＭ＝１
ｈ．Ｔｈｒｇｈｐｔ２ＤｅｌａｙＣｏｎｖＦａｃｔｏｒＢＳＭ＝１
ｉ．ＦｌｏｗＣｌａｓｓ＝ＤｅｌａｙＳｅｎｓｉｔｉｖｅ
ｊ．ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓｕｒｅＭａｐｐｉｎｇ＝１
ｋ．ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｏｌｄ＝０．２５＊ＤｅｌａｙＢｏｕｎｄ
ＢＥ／ＡＦフローは、以下のパラメータの適切な組合せを用いることによって優先順位を設定することができる。
【０２６３】
１．   ＭＣ０，．．．，ＭＣ７状態は、厳しい優先順位設定を許容する。
【０２６４】
２．   ソフト優先順位設定用ＧｏＳＦａｃｔｏｒ
３．   典型的には、何らかの最低スループットを要求するＡＦフローに関するＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ
ＥＦフローは、以下のパラメータの適切な組合せを用いることによってさらに優先順位を設定することができる。
【０２６５】
１．   ＭＣ０，．．．，ＭＣ７状態は、厳しい優先順位設定を許容する。
【０２６６】
２．   ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔは、同じ優先度状態のオクテット間でのビットスタッフィング中における優先順位設定を提供するが、最終的なパケット選択には対しては直接的な影響を与えない（その理由は、この後者のステップは、ビットメトリックを用いてパケットメトリックを計算し、ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔに依存しないためである）。同じユーザー又は２つの異なるユーザーに属する２つのフローが同じ候補送信インスタンス内に含められるために競争中であるときには、より大きいＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔを有するフローが優先される。
【０２６７】
３．   ＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅは、ビットメトリックに対して影響を与え、このためパケットメトリックに対して直接的な影響を有する。このパラメータは、ソフト優先順位設定に関しても用いることができる。現在は、このパラメータは実装されない。
【０２６８】
ＤＳＰ−Ｄｒｉｖｅｒインタフェースは、スケジューラにおいてフローを統合する柔軟な方法を提供する。スケジューラによって行われる統合は、ＢＳＣによって行うことができる統合とは異なることに注目すること。ＢＳＣが一組のフローを統合するときには、この統合フローは、スケジューラへの単一のフローであるようにみえ、スケジューラは、フローに関する単一の組のパラメータを受け取る。スケジューラは、寄与フローを区別することができない。統合がスケジューラにおいて行われるときには、スケジューラは、当然のことであるが、寄与フローを知ることになる。
【０２６９】
ＡｖｇＴｈｒｏｕｇｈｐｕｔ変数は、統合フローの総スループットを含む。統合フローの寄与フローに関して規定された一定のパラメータ、例えばＤｅｌａｙＢｏｕｎｄ、は、ＤＳＰ−Ｄｒｉｖｅｒインタフェースにおいて同じ値に設定される。全寄与フローに関して等しく設定される変数一覧は以下のとおりである。
【０２７０】
ａ．ＵｓｅｒＩＤ
ｂ．ＡｇｇｒｅｇａｔｅＩｎｄｅｘ
ｃ．ＱｏＳＭｅｔｒｉｃＳｔａｔｅ
ｄ．ＰｒｉｏｒｉｔｙＴｈｏｌｄ［２］
ｅ．ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒ
ｆ．ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔ
ｇ．ＤｅｌａｙＢｏｕｎｄ
ｈ．ＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ
ｉ．ＧｏＳＦａｃｔｏｒ
ｊ．ＤＳＢｉｔＭｅｔｒｉｃＶａｌｕｅ
異なる設定ができるパラメータは、ＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙであり、異なる設定をすべきパラメータは、ＦｌｏｗＩＤである。
【０２７１】
一実施形態においては、統合フローは、単一のビット（スタッフィング）メトリックが割り当てられる。このメトリックは、統合フローの寄与フロー間において最も古いタイムスタンプに基づく。寄与フローのタイムスタンプは、ＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列の待ち行列先頭タイムスタンプに基づいて計算される。しかしながら、ビットスタッフィングに関してフローが選択されるときには、寄与フローにサービングする順序は、第１に、寄与フローの各々に割り当てられたＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙパラメータによって決定され、２次的には、寄与フローのタイムスタンプによって決定される。ＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙパラメータを同じ値に設定することによって、寄与フローの選択順は、それぞれのタイムスタンプに厳格に基づいて設定することができる。ＩｎｔｒａＦｌｏｗＰｒｉｏｒｉｔｙパラメータは、ほとんどの場合ＢＥフローを対象とする。
【０２７２】
上述されるように、各フローは、ＦＴｘ待ち行列を有し、ＲＸｘ及び／又はＤＡＲＱ待ち行列を有することができる。ソフトウェア実装においては、各フローに関して単一のビットスタッフィングメトリックが計算される。このメトリックは、ＦＴｘ待ち行列内のオクテット、及びＲＴｘ及びＤＡＲＱ待ち行列内のオクテットに適用される。サービングされるべきフローが選択された場合は、個々の待ち行列も決定された順序でサービングされる。
【０２７３】
一ソフトウェア実装は、ＲＴｘ及び／又はＤＡＲＱ待ち行列が空でない場合にフローの優先度を高くする能力を提供する。この提供は、方程式（２１）内のＭｅｔｒｉｃＴＳ値を以下のように単純に修正することによって完遂される。
【数８】
2009528793.tif 000014
【０２７４】
係数ＲｅｔｒａｎｓｍｉｓｓｉｏｎＰｒｉｏｒｉｔｙＦａｃｔｏｒは、ＲＴｘ及びＤＡＲＱの両待ち行列が空である場合に１の値をとる。ＲＴｘ待ち行列は空であるがＤＡＲＱ待ち行列はデータを含む場合は他の値をとる。さらに、ＲＴｘ待ち行列が空でない場合はさらに他の値である。
【０２７５】
１ｘＥＶ−ＤＯ  Ｒｅｖ．  Ａ仕様においては、一定のプロトコル副型は、一組の単一ユーザー及びマルチユーザー送信フォーマットと適合可能なようにＮＵＬＬ  ＤＲＣを定義する。さらに、１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様においては、（１０２４，１６，１０２４）単一ユーザー送信フォーマットを持って受信されたＮＵＬＬ  ＤＲＣを送信したユーザーにＡＮがサービングできるようにする一定のプロトコル副型に関して構成属性が定義される。
【０２７６】
いずれの場合も、スケジューラは、受信されたＮＵＬＬ  ＤＲＣを送信したユーザーに関するデータを含む候補送信インスタンスを生成することができる。この生成は、ＮＵＬＬ−レート変換と呼ばれる。スケジューラは、以下の条件をＮＵＬＬ−レート変換に課す。
【０２７７】
ａ．有限ＤｅｌａｙＢｏｕｎｄを有するフローにサービングする。
【０２７８】
ｂ．ＲＴｘ／ＤＡＲＱ待ち行列にサービングすることができない。
【０２７９】
これらの条件以外では、スケジューラは、ユーザーからの受信されたＤＲＣが、１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様において一定のプロトコル副型内の同じ送信フォーマットと適合可能であることが両方とも定義される０ｘ０、（すなわち、ＮＵＬＬ  ＤＲＣ）、又は０ｘ１、（すなわち、３８．４Ｋｂｐｓ）であったかを区別しない。表１の特定のプロトコル副型に関する定義を再度参照すること。
【０２８０】
ＮＵＬＬ  ＤＲＣがユーザーから受信されるときに、サービングされたパケットがそのユーザーによって成功裏に復号される保証はない。一改良点は、ＮＵＬＬ  ＤＲＣを送信しておりパケットにおいてサービングされたユーザーが成功裏に復号したかどうかをモニタリングすることを含む。変換は、成功に関する統計に依存して、フローに関してオン／オフにすることができる。一実施形態は、０ｘ１のＤＲＣを送信したユーザーに関して生成された候補送信インスタンス３５よりも小さいＮＵＬＬ  ＤＲＣを送信したユーザーに関して生成された候補送信インスタンス３５の順位を決める。
【０２８１】
ソフトウェア実装において、スループットの影響を受けやすいフローに関するデータを含む候補マルチユーザーインスタンスの生成を容易にするために一定の概算を行うことができる。
【０２８２】
スケジューラタイミングに関して、スロット内のタイムラインが２つの部分に分割され、第１の部分は、重要でないセグメントであり、後者の部分は、重要セグメントである。ユーザーのＤＲＣ値は、重要セグメント中に利用可能になる。しかしながら、重要セグメントは、最悪時のローディング下にあるスケジューラに関わる計算を行う上で十分なプロセッササイクルを提供することができない。従って、これらの計算の一部は非重要セグメントに委託される。幾つかのユーザーのＤＲＣ値は、非重要セグメント中には知ることができないため、ソフトウェア実装は、前スロットのＤＲＣ値を用いて候補送信インスタンス３５を構築し、勝利候補を選択する。幾つかのユーザーのＤＲＣ値は変化することがあり、重要セグメント中に勝利候補が無効になる場合がある。この問題を克服するために、非重要セグメント中には２つ以上の強力な候補が選択される。実際のＤＲＣ値が重要セグメントにおいて受信されると、この縮小された組の候補が再評価される。縮小された候補インタフェースの組は、以下の候補を含むことができる。
【０２８３】
ａ．少数（例えば５つ）の単一ユーザー候補
ｂ．マルチユーザー候補（生成された場合）内のサービングされたユーザーの一部が適合不能になった場合に該候補においてサービングできる幾つかの予備のユーザーを有する１つのマルチユーザー候補
１ｘＥＶ−ＤＯ  Ｒｅｌ．０仕様においては、ＡＮは、ＤＲＣ情報が消去されたときにはＡＴへのパケットをスケジューリングしない。ＡＮが遅延の影響を受けにくいアプリケーション、例えばＢＥトラフィック、を有する複数のＡＴにサービング中であるときは、（例えば、マルチユーザーダイバーシティに起因するときに）システム容量を失わずに相対的に大きいＤＲＣ消去レートに耐えることができる。ＤＲＣ消去レートが過度に高いときには、ＤＲＣロックビットがＡＮによってゼロに設定され、ＡＴは、他のセクターにハンドオフすること又は固定レートモードに切り換わることを選択することができる。しかしながら、ＤＲＣロックビット生成方法は、不要なハンドオフを防止するための組み込まれた遅延を有し、該遅延は、少なくとも一部はフィルタリングに起因する。従って、相対的に長い実行長のＤＲＣ消去が逆方向リンクにおいて生じる可能性が依然として存在する。遅延の影響を受けやすいアプリケーション、例えばＥＦトラフィック、に関しては、これらの消去の結果、受け入れ不能な量のサービス停止になる可能性がある。ＤＲＣ消去マッピング方法は、ＦＬにおけるサービス停止を最小にすることを追究する。
【０２８４】
基準方法が２つのステップで説明される。第１のステップは、ＤＲＣ消去マッピングに関する決定について説明する。第２のステップは、１ｘＥＶ−ＤＯ  Ｒｅｖ．ＡのＦＬスケジューラの修正について説明する。図１４は、可変レートモードにある各ＡＴに関するすべてのタイムスロット間隔においてＡＮによって実行することができるＤＲＣ消去マッピング方法の実施形態を示す。各ＡＴに関して、方法は、そのユーザーに関してＢＳＣによってセットアップされるアクティブ待ち行列を有するセルの各セクターにおいて実行される。説明を単純化するため、方法は、各スロット間隔で実行されることが説明されるが、パラメータは、すべてのＤＲＣ＿Ｌｅｎｇｔｈ間隔のみにおいて更新することができる。
【０２８５】
方法の主出力は、Ｅｒａｓｕｒｅ＿Ｍａｐｐｅｄ＿ｆｌａｇであり、ＤＲＣ消去マッピングが実施されて制限されたＦＬスケジューリングをＡＴに関して行うことができることをスケジューラに示す。
【０２８６】
ＤＲＣ＿ｉｎｄｅｘ＿ｓｔｏｒｅは、最新の有効な、例えば成功裏に復号されたＤＲＣインデックスを格納するために用いられる。Ｅｒａｓ＿Ｃｏｕｎｔは、ＤＲＣ消去の実行長を計算するために用いられる。ＤＲＣ消去マッピングは、消去実行長がＭａｘ＿Ｅｒｓ＿Ｌｅｎよりも大きい場合のみに実施される。このしきい値は、サービス停止確率が相対的に高いときのみにＤＲＣ消去マッピングが実施されるように保証する。しかしながら、パケットは、対応するＦＬパケット遅延が大きいときにＡＴに対してスケジューリングすることができる。従って、Ｍａｘ＿Ｅｒｓ＿Ｌｅｎは高くしすぎることができない。ＥＦフロー（例えば、ＶｏＩＰ）に関しては、Ｍａｘ＿Ｅｒｓ＿Ｌｅｎに関する合理的な設定値は、０乃至１６スロットの範囲であることができる。
【０２８７】
図１４に示されるように、方法７００は、最初に、判断ブロック７０２においてＤＲＣが消去されるかどうかを検査する。ＤＲＣが消去される場合は、ステップ７０４においてＥｒａｓ＿Ｃｎｔが増やされる。次に、ステップ７０６において、Ｅｒａｓ＿Ｃｎｔが最大値Ｍａｘ＿Ｅｒｓ＿Ｌｅｎと比較される。Ｅｒａｓ＿ＣｎｔがＭａｘ＿Ｅｒｓ＿Ｌｅｎよりも大きい場合は、Ｅｒａｓｕｒｅ＿Ｍａｐｐｅｄ＿ｆｌａｇが１に設定され、その他の場合は、ステップ７１２において、Ｅｒａｓｕｒｅ＿Ｍａｐｐｅｄ＿ｆｌａｇがクリアされ、例えば０に設定される。判断ブロック７０２においてＤＲＣが消去されない場合は、ステップ７０８において、Ｅｒａｓｕｒｅ＿Ｍａｐｐｅｄ＿ｆｌａｇが０に設定され、Ｅｒａｓ＿Ｃｎｔが０に設定され、ＤＲＣ＿Ｉｎｄｅｘ＿ＳｔｏｒｅがＤＲＣ＿Ｉｎｄｅｘに設定される。処理はステップ７１２に続き、ステップ７１２において、Ｅｒａｓｕｒｅ＿Ｍａｐｐｅｄ＿ｆｌａｇが０に設定される。
【０２８８】
上述されるＦＬスケジューラは、ＤＲＣ消去マッピング方法とともに機能するように修正することができる。各ＡＴの各々の個別のデータフローに関して、フローは、以下の場合に限定ＦＬスケジューリングの資格を有する。
【０２８９】
（ＥｒａｓｕｒｅＭａｐｐｅｄＦｌａｇ＝＝１＆＆  ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓＭａｐｐｉｎｇ＝＝１  ＆＆  ＨｅａｄｏｆＱｕｅｕｅＤｅｌａｙ≧ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｈｏｌｄ）                                （２３）
ここで、ＦｌｏｗＥｌｉｇｉｂｌｅＦｏｒＤＲＣＥｒａｓＭａｐｐｉｎｇは、ＤＲＣ消去マッピングに関する各トラフィックフローの有資格性を示すパラメータである。デフォルトとして、ＥＦフローはマッピング資格を有し、ＢＥ及びＡＦは資格を有さないと仮定される。
【０２９０】
ＨｅａｄｏｆＱｕｅｕｅＤｅｌａｙは、ＦＬ待ち行列の先頭にあるパケット（例えば、ＦＴｘ、ＲＴｘ又はＤＡＲＱ待ち行列内の最も古いパケット）に関する“Ｃｕｒｒｅｎｔ＿Ｄｅｌａｙ”値を示す。ＥｒａｓｕｒｅＭａｐＤｅｌａｙＴｈｒｅｓｈｏｌｄは、（“ＰｒｉｏｒｉｔｙＴｈｏｌｄ［ｉ］．ＤｅｌａｙＨｏｌｄ”と同様の効果を有する）消去マッピングに関する特定のフローに関する最低限の要求される遅延である。フローが限定ＦＬスケジューリングの資格を有する場合は、以下の修正がＦＬスケジューラに関して行われる。
【０２９１】
ａ．フローは、単一ユーザー送信インスタンス候補としての資格がない。
【０２９２】
ｂ．フローは、要求されたＤＲＣインデックス，ＤＲＣ＿ｉｎｄｅｘ＿ｍａｐｐｅｄを有するマルチユーザー送信インスタンスの資格を有する。
【０２９３】
ＤＲＣ＿ｉｎｄｅｘ＿ｍａｐｐｅｄを消去長の関数として動的に変更することが可能である。この変更は、ＤＲＣ＿ｉｎｄｅｘ＿ｓｔｏｒｅ及びＥｒａｓ＿Ｃｏｕｎｔを用いて達成させることができる。ＤＲＣ＿ｉｎｄｅｘに関するデフォルト設定値は、０ｘ３にマッピングすることができる。ＦＬスケジューラに関しては、ＤＲＣインデックス０ｘ３は、フォーマット（｛１２８，２５６，５１２｝，４，２５６）に変換可能なマルチユーザー送信フォーマット（１０２４，４，２５６）に対応することになる。これらのすべてのマルチユーザーフォーマットは、全ＤＲＣインデックスと適合可能であり、このため、ＡＴは、（実際の要求されるＤＲＣインデックスから独立した）十分なＳＩＮＲを有するかぎりにおいてマッピングされたＤＲＣを復号することができるはずである。代替アルゴリズムは、より控えめにし、Ｅｒａｓ＿Ｃｏｕｎｔが増加するのに応じて利用可能なマルチユーザー送信フォーマットをより低いデータレートに制限することができる。
【０２９４】
ＤＡＲＱオプションは、ＶｏＩＰに関してオンにできることに注目すること。従って、ＡＴが送信されたマルチユーザーパケットを第１の送信試みにおいて復号していない場合は、ＤＡＲＱは、第２の送信試みを可能にし、残留パケット誤り率を引き下げる。しかしながら、ＤＡＲＱ性能は、ＤＲＣが消去中にはあまり信頼できない可能性があるＡＣＫチャネル性能と結びつけられている。ＡＣＫ／ＮＡＫ決定しきい値は、可能なことにＤＲＣインデックス又はＤＲＣマッピング状態に依存してＤＡＲＱに関して最適化することができる。他の実施形態は、ＤＲＣ消去マッピングの場合は、ＤＡＲＱ送信試みをより低レートのマルチユーザーパケットフォーマット、例えば（５１２，４，１０２４）、又は（２５６，４，１０２４）、のみと適合できるようにする。
【０２９５】
代替実施形態は、本明細書に示されるスケジューラに対して追加のステップ及び手段を提供することができる。例えば、ＢＥ／ＡＦフローは、ＥＦ優先度状態よりも低い優先度を有する優先度状態を利用することができる。この結果、より高い優先度状態を用いる可能性が非常に高いＥＦユーザーが存在する場合にＢＥ／ＡＦスループットが劣化する可能性がある。ＢＥ／ＡＦスループットは、一定の条件下においてＢＥ／ＡＦフローの優先度をより高い状態に上げることによって上昇させることができる。
【０２９６】
一実施形態により、ＡｖｇＲｅｑｕｅｓｔｅｄＲａｔｅは、ユーザーのフィルタリングされた要求レートであり、システム内においてＫのユーザーがＢＥユーザーとして構成される。ＢＥフローに関するユーザーのスループットＡｖｇＴｈｒｏｕｇｈｐｕｔが以下を満たす場合は、ＢＥフローに関するユーザーの優先度状態をより高い優先度状態に上昇させることができる。αの値は、システムのＥＦ負荷に依存して選択することができ、例えばより高い負荷に関してより小さいαである。さらに、この促進のために、最低限の要求レートに関する要求事項をユーザーに課すことができる。ＢＥ／ＡＦ容量を向上させるためのその他の方法が可能である。
【数９】
2009528793.tif 000015
【０２９７】
上記の方法は、フローのビット（スタッフィング）メトリックの優先度状態が待ち行列先頭の遅延の関数になることができるだけでなく、フローのスループットの関数であることもできることも示唆する。
【０２９８】
遅延の影響を受けやすい状態においては、ビットスタッフィングメトリックは、遅延の関数であり、ユーザーのローカルチャネルピークを利用するためのメカニズムを有さないことに注目すること。ここでは、遅延の影響を受けやすい状態におけるビットスタッフィングメトリック値を以下のように修正することができる。
【０２９９】
ＭＢＳＤＳ＝ＡｃｃｅｌｅｒａｔｉｏｎＦａｃｔｏｒ＊［ＣｕｒｒｅｎｔＤｅｌａｙ＋ｋＣＣＩ］＋ＡｃｃｅｌｅｒａｔｉｏｎＯｆｆｓｅｔ            （２５）
ここで、チャネル状態インジケータ（ＣＣＩ）は、別々に生成することができる組｛０，１｝又は間隔［０，１］からの値をとることができ、このため、より高い値をとるときには、ユーザーの長期的なチャネル状態と比較して相対的に良好なチャネル状態を示す。さらに、ｋは、ＣＣＩ−遅延変換係数である。ｋは、ユーザーのチャネル状態が自己のチャネル統計に関して良好であるときにフローが遅延に関してどの程度向上するかを示す。
【０３００】
バイナリ｛０，１｝に関するＣＣＩを生成するための１つの単純な方法は、次のように与えられる。ＲａｔｅＩｎｄｅｘを、レートの昇順でＤＲＣ値に割り当てられた整数であるとする。ここで、ＤＲＣ値は、データレートとともに単調に増加していないため用いられない。ＡｖｇＲａｔｅＩｎｄｅｘをユーザーの平均（フィルタリングされた）ＲａｔｅＩｎｄｅｘとする。ＣＣＩＴｈｒｅｓｈｏｌｄをパラメータ（例えば、１．２）とする。次に、ＲａｔｅＩｎｄｅｘ＞ＣＣＩＴｈｒｅｓｈｏｌｄ＊ＡｖｇＲａｔｅＩｎｄｅｘである場合は、ＣＣＩの値は１に設定することができる。その他の場合は、ゼロに設定される。この例においては、ＣＣＩは、受信されたＤＲＣに対応する現在のＲａｔｅＩｎｄｅｘが平均品質よりも１２０％以上高い場合に相対的に良好なチャネル状態を示す。
【０３０１】
プリエンプション（ｐｒｅｅｍｐｔｉｏｎ）は、ＦＬ送信が行先のユーザーによって復号される前に打ち切られることを意味する。プリエンプションは、ＦＬにおける４つの全インターレースが相対的に低レートのユーザーによって占められている間に非常に高い優先度のデータが現れる場合に用いることができる。ここで採用される手法は、プリエンプションを要求する可能性がある事情を回避することである。１つの該状態は、上述されるように、４つの全インターレースが低レートユーザーによって占有されている状態である。これを回避するために、単純な方法を利用することができる。１つの該方法は、１６スロット及び８スロットのスパンを有するフォーマットの定められた同時送信回数を超えるのを許可しないことである。一例として、この回数は、２又は３に設定することができる。
【０３０２】
一実施形態は、ＮＵＬＬ  ＤＲＣを送信し、パケット内においてサービングされるユーザーの復号性能をモニタリングする。これらのＮＵＬＬ−レート事例に関して測定されたＰＥＲに依存して、各ユーザーに関するＮＵＬＬ−レート変換をオン／オフにすることが可能である。同様に、ＡＴがこれらのパケットを十分に信頼できる形で復号中であることを収集された統計が示す場合に、ＲＴｘ／ＤＡＲＱ待ち行列及びＮＵＬＬ−レートインスタンスにおいて無限のＤｅｌａｙＢｏｕｎｄを有するフローの待ち行列にサービングすることに関する制限をオン／オフにすることも可能である。
【０３０３】
スループットの影響を受けやすいフローに関するビット及びビットスタッフィングメトリック係数は、ユーザーが受信すべきデータを大量に有するＢＥ専用システムにおいて比例的公平性を提供する（例えば、全フローに関してＴａｒｇｅｔＴｈｒｏｕｇｈｐｕｔ＝０及びＧｏＳＦａｃｔｏｒ＝１）。メトリック係数の形態は、その他のスケジューラにも同様の形で適用することができる。この目的のため、スループットの影響を受けやすいフローに関するメトリック係数は、以下のように表すことができる。
【数１０】
2009528793.tif 000016
【０３０４】
ここで、ｆ（．）及びｈ（．）は、総称関数であり、ＡｖｇＲｅｑｕｅｓｔｅｄＲａｔｅは、ユーザーの平均要求レートである。ｆ（ｘ）＝ｘ及びｈ（ｘ）＝ｘに設定することは、ほぼ等しいＧｏＳのスケジューラを生み出す。
【０３０５】
１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様において定義される拡張順方向トラフィックチャネルＭＡＣプロトコルは、以下において要約されるようにマルチユーザーパケットに従ってユーザーにサービングすることに制約を課す。１ｘＥＶ−ＤＯ  Ｒｅｖ．Ａ仕様では、以下の条件が満たされる場合はスロットｔはより早いスロットｓの連続であると定義されると述べている。
【０３０６】
ｃ．アクセス端末は、送信がスロットｓにおいて開始するパケットの潜在的目標である。
【０３０７】
ｄ．スロットｔは、スロットｓと同じＦＬインターレース内にある。すなわち、ｔ−ｓ＝０（ｍｏｄ４）である。
【０３０８】
ｅ．ｓ＜ｔ＜ｓ＋４×ｍｉｎ［Ｎ１，Ｎ２，ＭｉｎｉｍｕｍＣｏｎｔｉｎｕａｔｉｏｎＳｐａｎ］であり、ここで、Ｎ１は、受信がスロットｓにおいて開始したパケットの公称送信継続時間を表し、Ｎ２は、スロットｓ中に有効であるＤＲＣ値に対応するＤＲＣインデックスのスパンを表す。
【０３０９】
ｆ．スロットｔの前において、ＡＮは、スロットｓにおいて送信が開始したパケットに関する肯定応答を受信していない。
【０３１０】
ＡＴがスロットｓにおいて開始するセクターによって送信されたパケットの潜在的目標である場合は、ＡＮは、スロットｓの連続であるいずれのスロットｔにおいても同じＦＬデータソースからの新しいパケットをＡＴに送信することができない。
【０３１１】
上記の制限は、マルチユーザーパケットに従っていずれのユーザーにサービングできるかに対して制約を課す。一例として、ＡＮが、早期に終了する一組のユーザーにマルチユーザーパケットをサービングする場合は、ＡＮは、サービングされたパケットの連続中には、前パケットにおいてサービングされなかったがフォーマットと適合可能であったユーザーに対しては（単一ユーザー又はマルチユーザーであるかにかかわらず）どのようなパケットもサービングすることができない。１つの状況においては、ＡＮは、１５３．６Ｋｂｐｓマルチユーザーパケットをサービングし、該パケットによって搬送されたデータを有するユーザーは、４スロット未満でパケットを復号する。ＡＮが同じインターレースにおいて他の１５３．６Ｋｂｐｓマルチユーザーパケットを直ちにサービングする場合は、１５３．６Ｋｂｐｓ又は４スロットのスパンを有するＤＲＣを実際に要求したが前パケットにおいてサービングされなかったユーザーは、新たな送信においてサービングすることができない。従って、４スロット未満のスパンを有するＤＲＣを要求したユーザー、例えば、典型的にはより良いチャネル状態にあるユーザー、のみが新たな送信においてサービングすることができる。しかしながら、このことは、新たなパケットが早期に復号する可能性をさらに高くする。この連鎖は、より高いジオメトリのユーザーの待ち行列が空になるまで続く。他方、４スロットのスパンを有するＤＲＣを要求中のより低いジオメトリのユーザーは、サービングすることができない。その結果、より低いジオメトリのユーザーに関して過度の遅延及びより高いジオメトリのユーザーに関して遅延上の小さい利得が生じる可能性がある。
【０３１２】
上記の説明において提供される実施形態、側面及び例は、高レートパケットデータプロトコルをサポートするシステムに関するものであることに注目すること。該システムは、説明を明確化すること及び例示することを目的として提示されている。代替システムは、本明細書において提示される適応型遅延管理及びスケジューリングに関する方法及び手段を実装することができる。
【０３１３】
順方向リンクスケジューラ２０
図１６Ａは、順方向リンクスケジューラの実施形態２０を示す。図１７Ａは、順方向リンクスケジューラによって実行されるプロセスの流れ図を示す。
【０３１４】
候補パケット生成器２５
図１６Ａにおいて示されるように、各セクター内の各搬送波は、同じ（又は異なる）順方向リンクデジタル信号プロセッサにおいて実行される候補単一ユーザーパケット及びマルチユーザーパケットを生成する候補パケット生成器２５を有する。各候補パケット生成器２５搬送波は、特定の周波数及び特定のセクターと関連づけられる。例えば、３つの搬送波及び３つのセクターが存在する場合は、搬送波とセクターの各組合せに関して１つずつ合計９の候補パケット生成器２５が存在することになる。候補パケット生成器２５は、信号プロセッサ又はいずれかの形態の処理手段であることができる。さらに、候補パケット生成器２５は、ハードウェア内に実装することもできる。候補パケット生成器２５は、上述される単一搬送波スケジューラ２３において開示されるスケジューリング方法を用いてユーザーからのパケットを送信のために選択することができる。このように、各セクター／搬送波の組合せに割り当てられた各々の候補パケット生成器２５は、送信のためのパケットを選択することができる。図１６Ａは、第１の候補パケット生成器２５への２つの入力、すなわち、搬送波９２及びセクター９０に割り当てられた全フローに関するフロー当たりのＱ状態及びこのサービングセクターとのＡＴの全ＤＲＣ及びこの搬送波９２に割り当てられた全ＤＲＣ。しかしながら、すべての候補パケット生成器２５がこれらの入力を受信する。
【０３１５】
個々の候補パケット生成器２５は、互いに独立して働くため、複数の候補パケット生成器２５が送信のために同じユーザーからのパケットを選択することが可能である。しかしながら、マスタースケジューラ１０は、２つ以上の候補パケット生成器２５が同じユーザーからのパケットを選択することを妨げることができる。
【０３１６】
マスタースケジューラ１０
マスタースケジューラ１０は、各候補パケット生成器２５から入力される各搬送波に関する最良のパケット送信を決定する。一実施形態においては、マスタースケジューラ１０は、順方向リンクデジタル信号プロセッサに常駐する。マスタースケジューラ１０は、１つ以上の単一ユーザーパケット及び／又はマルチユーザーパケット（バックアップオプション付き）９３を候補パケット生成器２５から入力として受信する。マスタースケジューラ１０は、システム９４内の全フローに関するＱ状態（又はバッファ状態情報）も入力として受信する。マスタースケジューラ１０は、図１７Ａの流れ図に示されていてさらに図１６Ａのメモリ１２に格納されたソフトウェア命令１４の形態でマスタースケジューラ１０に常駐する順方向リンクスケジューラ方法の次のステップを実行することによって各候補パケット生成器２５から入力される各搬送波に関する最良のパケット送信を決定する。さらに、マスタースケジューラ１０は、セクター及び搬送波９８当たりのＱ状態更新９６及び最終的パケット情報を出力する。
【０３１７】
各セクターｓに関して、１≦ｓ≦ｎであり、ここで、ｎ＝総セクター数であり、マスタースケジューラ１０は、各候補パケット生成器２５から出力された全パケットを入力として有する（図１７Ａにおけるステップ３１５）。候補パケット生成器は、対応する搬送波において送信することができる候補パケットを生成する。パケット自体は、単一ユーザーに関する又は例えばマルチユーザーパケット内の複数のユーザーに関するデータを含むことができる。
【０３１８】
各搬送波ｉに関して、１≦ｉ≦ｋであり、ここで、ｋ＝総搬送数であり、マスタースケジューラ１０は、候補単一ユーザーパケット（ＳＵＰ）及び複数のユーザーパケット、又はマルチユーザーパケット（ＭＵＰ）のうちで最高のメトリックを有するパケットを選択し（図１７Ａのステップ３２０）、このため、
ｉ）計算されたパケットメトリックを達成させる上で十分なデータがバッファＱ内に存在する。
【０３１９】
ｉｉ）多搬送波割り当てを有するＥＦフローは、他の搬送波又は副搬送波においてより高いパケットメトリックを有さない。ＥＦフローは、この搬送波によって搬送された場合に他の搬送波が搬送すべきデータがＱ内に存在しないようなフローである。（この最高のメトリックは、ユーザーが十分なデータを有すること又はユーザーの遅延限度に達していることを暗黙に示す）。
【０３２０】
上述されるように、ユーザーは、データ送信のために２つ以上のパケット生成器２５によって選択することができる。事実、ユーザーは、最大でＮの搬送波を受信することができ、各パケット生成器２５は１つの搬送波を有する。ユーザーのデータがマスタースケジューラ１０によって第１の搬送波を通じて既に送信されている場合は、マスタースケジューラ１０は、後続する候補パケット生成器２５から選択するパケットがこの同じユーザーからのものでないことを保証する。各候補パケット生成器２５が２つ以上のユーザーからパケットを選択するのはこの理由による。搬送波当たり１つのユーザーを用いる理由は、ＥＦフローは、１つの搬送波によって搬送された場合は他の搬送波が搬送すべきデータがＱ内に存在しないようなフローであるためである。（ＥＦフロー、例えばＶｏＩＰ、は、非常に厳しい遅延上の制約を有しているため大量のデータがバッファリングされない。）
マスタースケジューラ１０は、複数の候補パケット生成器２５によって選択されているユーザーからのパケットが提示されたときには、最良の状態を有する搬送波を有する候補パケット生成器２５を選択する（図１７Ａにおけるステップ３２５）。
【０３２１】
次に、マスタースケジューラ１０は、搬送波ｉによって搬送されるデータフローに関してＱ状態、例えばバッファ、を更新する（図１７Ａにおけるステップ３３０）。この更新は、マスタースケジューラ１０がパケットを選択することによってユーザーにサービング後に、同じユーザーパケットを搬送中の後続するバッファがマスタースケジューラ１０によってサービングされないようにする。
【０３２２】
次に、マスタースケジューラ１０は、すべての残りの搬送波ｊからの候補パケット送信に関するパケットメトリックを更新し、ここで、ｉ＜ｊ≦ｋである（図１７Ａにおけるステップ３３５）。すなわち、ユーザーが１つの搬送波において１つの候補パケット生成器２５によってサービングされた時点で、該ユーザーがパケット切れである場合はその他の搬送波における候補にならない。従って、すべての残りの搬送波からの候補パケット送信に関するパケットメトリックが更新され、それによって、ユーザーは、２つ以上の候補パケット生成器２５によってサービングされない。例えば、搬送波１において搬送されたユーザーに関する候補送信インスタンス３５に関するメトリックに対して、搬送波２、３及び４に関する候補パケット生成器２５がそのユーザーにサービングしないようにするための小さい値を割り当てることができる。このことは、搬送波１において行われたことを考慮して搬送波２、３及び４がどのように用いられるかを決定する。その他の場合においては、搬送波１においてサービングされたユーザーは、そのユーザーに関する全データが搬送波１において搬送されているため、その他の搬送波においてサービスを受けるための候補になることができない。
【０３２３】
図１７Ｂは、マスタースケジューラ１０の実施形態をブロック図形で示し、複数の搬送波におけるパケット送信をスケジューリングするための装置３５０を具備する。各セクターに関して及び各搬送波ｉ、１≦ｉ≦ｋ（ｋ＝総搬送波数）に関して、装置３５０は、最高のメトリックを有するパケットを選択するためのパケット選択ユニット（又はモジュール）３５５と、現在の搬送波ｉによって搬送されたＱ状態を更新するためのＱ更新ユニット３６０と、すべての残りの搬送波ｊ、ｊ＞ｉ，ｊ≦ｋからの候補パケット送信に関するパケットメトリックを更新するためのパケットメトリック更新３６５と、を具備し、ｉ）メトリックを達成させる上での十分なデータが待ち行列内に存在し、ｉｉ）多搬送波割り当てを有するＥＦフローは、他の副搬送波においてより高いパケットメトリックを有さず、ｉｉｉ）ＥＦフローは、現在の搬送波によって搬送された場合に他の搬送波が搬送すべきデータがＱ内に存在しないようなＥＦフローである。
【０３２４】
パケットビルダー４０
再度図１６Ａにおいて、パケットビルダー４０は、マスタースケジューラ１０によって提供されたパケットフォーマットに基づいてパケットを生成する。一実施形態においては、パケットビルダー４０は、マスタースケジューラ１０によって選択されたパケットのフォーマットをＥＶ−ＤＯにおいて用いられるフォーマットに変換する。各セクターは、マスタースケジューラ１０によって提供されたパケットフォーマットに基づいてパケットを生成するパケットビルダー４０を有する。パケットビルダー４０は、チャネルカード上の変調器によって受け入れ可能なフォーマットを用いる。次に、パケットは、変調器を含むマスタープロセッサ６０によってＥＶ−ＤＯエアインタフェースを通じて送信される。
【０３２５】
スレーブスケジューラ５０
スレーブスケジューラ５０は、マスタースケジューラ１０が実施することをコピーする。マスタースケジューラ１０が故障した場合は、シャドールーチンがマスタースケジューラ１０を引き継ぐ。
【０３２６】
図１６Ｂは、図１６Ａの分散型アーキテクチャの実施形態１３０をブロック形で示し、複数の搬送波におけるスケジューリングのための装置１３０を具備する。装置１３０は、候補パケット送信インスタンスをスケジューリングするための第１のスケジューリングユニット１３５と、パケットをスケジューリングするための第２のスケジューリングユニット１４０と、第２のスケジューリングユニット１４０によって提供されるパケットフォーマットに基づいてパケットを生成するためのパケット生成ユニット１４５と、エアインタフェースを通じてパケットを送信するための送信ユニット１５０と、を具備する。装置１３０は、スケジューリングユニット１３５、１４０のシャドールーチンを実行するための処理ユニット１５５を含むこともできる。
【０３２７】
分散型アーキテクチャ
図１８Ａは、マスタースケジューラ１０と関連づけられた分散型アーキテクチャの実施形態を示す。マスタースケジューラ１０の構成要素は、異なるエンティティ（例えば、異なるデジタル信号プロセッサ（ＤＳＰ）又はネットワークプロセッサのマイクロエンジン）に常駐することができる。これらの構成要素は、セルサイトモデム（ＣＳＭ）６０と、ＲＬデジタル信号プロセッサ７０と、セクター＃１に関するＦＬデジタル信号プロセッサ８０と、セクター＃２に関するＦＬデジタル信号プロセッサ８２と、セクター＃３に関するＦＬデジタル信号プロセッサ８４と、セクター＃４に関するＦＬデジタル信号プロセッサ８６と、セクター＃５に関するＦＬデジタル信号プロセッサ８８と、等を含むことができる。このように、マスタースケジューラ１０は、選択された構成に依存して複数の順方向リンクＤＳＰにわたって機能的に分散される。分散型アーキテクチャに関する理由の１つは、１つのプロセッサがすべてのユーザー、セクター及び搬送波を取り扱うことができる可能性が低いためである。第２の理由は、分散型アーキテクチャは、非常にスケーラブルな設計を生み出すためである。選択されるプロセッサ数は、ユーザー数及び搬送波数に応じて異なる。すべてのプロセッサが１つのプロセッサにおいて適合するわけではないため、マスタースケジューラ１０は、すべての処理が１つのプロセッサ上に配置される場合は、該１つのプロセッサはすべてのユーザー及び搬送波に関して最適化ルーチンを実行するため、選択されたユーザーは最良のタイムスロット及び最良の周波数を送信のために常に入手するという意味で、周波数領域において“最適でない”マルチユーザーダイバーシティを達成させる。
【０３２８】
本方法及び装置の分散型アーキテクチャを用いることで、各候補パケット生成器２５は、１つの搬送波周波数及びセクターにおいて全ユーザーに関する最適化ルーチンを実行する。候補パケット生成器２５は、その他の搬送波又はセクターを考慮に入れない。マスタースケジューラ１０は、候補パケット生成器２５によって選択されたユーザーを見るだけである。次に、マスタースケジューラ１０は、全候補パケット生成器２５によって選択されたユーザーを評価し、各ユーザーに関する最良の搬送波及びセクターを用いることを試みる。
【０３２９】
図１８Ｂは、図１８Ａの分散型アーキテクチャの実施形態をブロック図形で開示し、パケットをスケジューリングするための装置１１０を具備する。装置１１０は、順方向リンクを処理するための複数のユニット（又はモジュール）（“ＦＬ処理ユニット”）を具備し、複数のセクターに対応するＦＬ処理ユニット１８０、１８２、１８４、１８６及び１８８と、データを変調及び復調するための変調ユニット１６０と、逆方向リンクを処理するためのユニット（又は“ＲＬ処理ユニット”）１７０と、を含む。
【０３３０】
情報及び信号は様々な技術及び技法のうちのいずれかを用いて表すことができることを当業者は理解するであろう。例えば、上記の説明全体を通じて参照されることがあるデータ、命令、コマンド、情報、信号、ビット、シンボル、及びチップは、電圧、電流、電磁波、磁場、磁粒子、光学場、光学粒子、又はその組合せによって表すことができる。
【０３３１】
本明細書において開示される実施形態に関連して説明されている様々な例示的論理ブロック、モジュール、回路、及びアルゴリズム上のステップは、電子ハードウェアとして、コンピュータソフトウェアとして、又は両方の組合せとして実装できることを当業者はさらに理解するであろう。ハードウェアとソフトウェアのこの互換性を明確に例示するため、上記においては、様々な例示的構成要素、ブロック、モジュール、回路、及びステップが、各々の機能の観点で一般的に説明されている。これらの機能がハードウェアとして又はソフトウェアとして実装されるかは、全体的システムに対する特定のアプリケーション上の及び設計上の制約事項に依存する。当業者は、説明されている機能を各々の特定のアプリケーションに合わせて様々な形で実装することができるが、これらの実装決定は、本発明の適用範囲からの逸脱を生じさせるものであるとは解釈すべきではない。  
本明細書において開示される実施形態に関連して説明されている様々な例示的な論理ブロック、モジュール、及び回路は、本明細書において説明されている機能を果たすように設計された汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、その他のプログラミング可能な論理デバイス、ディスクリートゲートロジック、ディスクリートトランジスタロジック、ディスクリートハードウェア構成品、又はそのあらゆる組合せ、とともに実装又は実行することができる。汎用プロセッサはマイクロプロセッサであることができるが、代替として、従来のどのようなプロセッサ、コントローラ、マイクロコントローラ、又はステートマシンであってもよい。さらに、プロセッサは、計算装置の組合せ、例えば、ＤＳＰと、１つのマイクロプロセッサとの組合せ、複数のマイクロプロセッサの組合せ、ＤＳＰコアと関連する1つ以上のマイクロプロセッサの組合せ、又はその他のあらゆる該コンフィギュレーションとの組合せ、として実装することもできる。
【０３３２】
本明細書において開示される実施形態に関連して説明されている方法又はアルゴリズムのステップは、ハードウェア内において直接具体化させること、プロセッサによって実行されるソフトウェアモジュール内において具体化させること、又はこれらの２つの組合せ内において具体化させることができる。ソフトウェアモジュールは、ランダムアクセスメモリ（ＲＡＭ）、フラッシュメモリ、読取専用メモリ（ＲＯＭ）、電気的にプログラマブルなＲＯＭ（ＥＲＰＯＭ）、電気的に消去可能なプログラマブルなＲＯＭ（ＥＥＲＰＯＭ）、レジスタ、ハードディスク、取り外し可能ディスク、ＣＤ−ＲＯＭ、又は当業において知られるその他のあらゆる形態の記憶媒体に常駐することが可能である。例示的記憶媒体は、プロセッサが記憶媒体から情報を読み出すことができるように及び記憶媒体に情報を書き込むことができるようにプロセッサに結合される。代替として、記憶媒体は、プロセッサと一体化させることができる。プロセッサ及び記憶媒体は、ＡＳＩＣ内に常駐することができる。ＡＳＩＣは、ユーザー端末内に常駐することができる。代替として、プロセッサ及び記憶媒体は、ユーザー端末において個別構成要素として常駐することができる。
【０３３３】
開示されている実施形態に関する上記の説明は、当業者が本発明を製造又は使用できるようにすることを目的とするものである。これらの実施形態に対する様々な修正は、当業者にとっては容易に明確になるであろう。本明細書において定められている一般原理は、本発明の精神及び適用範囲を逸脱しない形でその他の実施形態に対しても適用することができる。以上のように、本発明は、本明細書において示されている実施形態に限定されることを意図するものではなく、本明細書において開示されている原理及び斬新な特長に一致する限りにおいて最も広範な適用範囲が認められるべきである。
【図面の簡単な説明】
【０３３４】
【図１Ａ】無線通信システムである。
【図１Ｂ】高データレート送信をサポートする無線通信システムである。
【図２】無線通信システムにおける送信に関するスケジューリングアルゴリズムのブロック図である。
【図３】無線通信システムにおけるアクセスネットワーク（ＡＮ）の流れ図である。
【図４】パケットデータスケジューラのカテゴリ分類を示した図である。
【図５】ユーザーからの受信されたデータ要求に基づいてチャネル強度を決定するためのフィードバックループを示した図である。
【図６】単一のトラフィック型を有する優先転送（ＥＦ）専用ユーザーが存在する状態におけるスケジューラの挙動を示した図である。
【図７】ペイロード多項式ｐ（ｚ）からの簡略化されたペイロード多項式ｃ（ｚ）の計算を示した図である。
【図８】一実施形態によるスケジューラを示した図である。
【図９】一実施形態による図８のスケジューラの一部分を示した図である。
【図１０】送信の適応型遅延管理を実装するためのスケジューリングアルゴリズムを示した図である。
【図１１】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１２】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１３】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１４】データレート制御（ＤＲＣ）消去マッピング方法の流れ図である。
【図１５】単一搬送波スケジューラによって実行されるプロセスの流れ図を示した図である。
【図１６Ａ】順方向リンクスケジューラの実施形態を示した図である。
【図１６Ｂ】図１６Ａの分散型アーキテクチャの実施形態を示した図である。
【図１７Ａ】順方向リンクスケジューラによって実行されるプロセスの流れ図である。
【図１７Ｂ】マスタースケジューラの実施形態を示した図である。
【図１８Ａ】マスタースケジューラと関連づけられた分散型アーキテクチャの実施形態を示した図である。
【図１８Ｂ】図１８Ａの分散型アーキテクチャのブロック図を示した図である。
【図１Ａ】
2009528793.tif 000017
【図１Ｂ】
2009528793.tif 000018
【図２】
2009528793.tif 000019
【図３】
2009528793.tif 000020
【図４】
2009528793.tif 000021
【図５】
2009528793.tif 000022
【図６】
2009528793.tif 000023
【図７】
2009528793.tif 000024
【図８】
2009528793.tif 000025
【図９】
2009528793.tif 000026
【図１０】
2009528793.tif 000027
【図１１】
2009528793.tif 000028
【図１２】
2009528793.tif 000029
【図１３】
2009528793.tif 000030
【図１４】
2009528793.tif 000031
【図１５】
2009528793.tif 000032
【図１６Ａ】
2009528793.tif 000033
【図１６Ｂ】
2009528793.tif 000034
【図１７Ａ】
2009528793.tif 000035
【図１７Ｂ】
2009528793.tif 000036
【図１８Ａ】
2009528793.tif 000037
【図１８Ｂ】
2009528793.tif 000038
【国際調査報告】
2009528793.tif 000039
2009528793.tif 000040
2009528793.tif 000041