(57)【要約】【課題】  本発明は、送信スケジューラーのキューからアイテムを除去するシステム及び方法を提供する。【解決手段】  送信スケジューラーのキューからアイテムを除去するシステム及び方法であって、各アイテムに待ち時間、つまり当該アイテムが送信される前にシステム内に残留している時間を示す待ち時間カウントを割り当て、現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算し、前記現行の待ち時間カウントを予め定められるか又はスケジューラーの実行の度に再計算されて良い除去期間と比較し、及び前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する。【選択図】  図４
2008125073.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにある局のスケジューラーであって、前記スケジューラーは、アイテムのキュー及び除去期間を有し、各アイテムはスケジューラーを実行する度に更新される待ち時間カウントを有し、アイテムは、前記アイテムに関連付けられた現行の待ち時間カウントが前記除去期間を超えた場合、前記キューから除去される、スケジューラー。
【請求項２】
前記キューに入るアイテムの待ち時間カウントは、前記アイテムの許容待ち時間値と等しい大きさを有する負数に設定される、請求項１記載のスケジューラー。
【請求項３】
前記キューに入るアイテムの待ち時間カウントは、サービス品質の待ち時間パラメータ又はジッター・パラメータから計算される、請求項１記載のスケジューラー。
【請求項４】
前記キューに入るアイテムの待ち時間カウントはゼロに設定される、請求項１記載のスケジューラー。
【請求項５】
前記アイテムの待ち時間カウントは、前回のスケジューラーの実行から経過したフレーム数を前記待ち時間カウントに加算することにより、前記スケジューラーの実行の開始時に更新される、請求項１記載のスケジューラー。
【請求項６】
前記除去期間は、前記キューの長さと現行のトラフィック・レートとの比に等しい、請求項１記載のスケジューラー。
【請求項７】
前記除去期間は、前記キューの長さと最大維持トラフィック・レートとの比に等しい、請求項１記載のスケジューラー。
【請求項８】
スケジューラーのキューからアイテムを除去する方法であって、
アイテムの許容待ち時間に等しい大きさを有する負数に等しい待ち時間カウントを前記アイテムに割り当てる段階、
現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する段階、
前記現行の待ち時間カウントを除去期間と比較する段階、及び
前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する段階、を有する方法。
【請求項９】
スケジューラーのキューからアイテムを除去するシステムであって、
前記アイテムの許容待ち時間に等しい大きさを有する負数を待ち時間カウントに割り当てる手段、
現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する手段、
前記現行の待ち時間カウントを除去期間と比較する手段、及び
前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する手段、を有するシステム。
【請求項１０】
局のスケジュール・システムであって、
１又は複数の入力キュー内のユーザー・データ及び管理メッセージの複数のアイテムを処理するスケジューラー、を有し、前記アイテムのそれぞれは待ち時間カウントを有し、
前記入力キューは所定の大きさ及びアイテムが前記入力キューに到着する計算された又は所定のレートを有し、
前記待ち時間カウントは、スケジューラーの実行の度に、前記アイテムが前記入力キューに置かれてから前記スケジューラーを経過したフレーム数だけインクリメントされ、及び
アイテムの待ち時間カウントが前記所定の大きさと前記所定のレートとの比を超えた場合、前記アイテムは前記入力キューから除去される、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＷｉＭＡＸスケジューラーの待ち時間カウントを使用した無効データ除去に関する。
【０００２】
本願は、名称「Ｓｔａｌｅ  Ｄａｔａ  Ｒｅｍｏｖａｌ  Ｂｙ  Ｕｓｉｎｇ  Ｌａｔｅｎｃｙ  Ｃｏｕｎｔ  Ｉｎ  Ａ  Ｗｉｍａｘ  Ｓｃｈｅｄｕｌｅｒ」、番号６０／８６５,４６３、２００６年１１月１３日出願、発明者Ａｎｔｏｎｉ  Ｏｌｅｓｚｃｓｕｋ、代理人管理番号１９７４．１０１８Ｐである仮出願の優先権を主張する。当該仮出願は、参照されることにより本願明細書に組み込まれる。
【背景技術】
【０００３】
無線通信ネットワークは、益々普及してきている。通信ネットワークの一形態である所謂ＷｉＭＡＸシステムは、電気電子技術者協会（ＩＥＥＥ）８０２．１６のような規格により定められて良い。本願明細書は、利便性のためＩＥＥＥ８０２．１６規格によっても使用される略語を含む用語を使用するが、それにより本発明が限定されることを意味しない。
【０００４】
図１は、通信ネットワーク１００の例を示す。通信ネットワーク１００は、基地局（ＢＳ）１０２の周囲に位置するセル領域にサービスを提供する基地局を（ＢＳ）１０２有して良い。１又は複数の加入者局（ＳＳ）１０８は、移動局（ＭＳ）、携帯電話、ラップトップコンピューターなどであって良く、移動局が基地局１０２のサービス領域１１０内にある場合に基地局１０２と通信可能であって良い。通信ネットワークはまた、１又は複数の中継局（ＲＳ）１０４を有し、例えば基地局１０２のブロードキャスト範囲が加入者局１０６又は移動局に届くために不十分である場合に、基地局１０２のサービス領域を拡張して良い。
【０００５】
ユーザー・データ・パケットは、基地局１０２と加入者局１０８との間で通信経路１１４を介し送信されて良い。ユーザー・データ・パケットはまた、通信経路１１６を介して加入者局１０６へ再送されるため、基地局１０２と中継局１０４との間で通信経路１１２を介し送信されて良い。ユーザー・データ・パケットは、ユーザー・データ・パケットの分配の種々の優先度を有するアイテムを有して良い。基地局１０２と加入者局１０６及び１０８はスケジューラーを有し、当該優先度に従いアイテムの送信をスケジュールして良い。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、キューから無効データを除去するスケジューラー、システム及び方法を提供する。
【課題を解決するための手段】
【０００７】
本発明の種々の実施例は、無線ネットワークの基地局、加入者局、中継局等のような局のスケジューラーを提供する。スケジューラーは、アイテムの１又は複数のキュー及び除去期間を有する。各アイテムはスケジューラーを実行する度に更新される待ち時間カウントを有する。アイテムは、当該アイテムに関連付けられた現行の待ち時間カウントが除去期間を超えた場合、キューから除去される。
【０００８】
本発明の種々の実施例は、方法を提供する。前記方法は、スケジューラーのキューからアイテムを除去し、初期にゼロに等しい待ち時間カウントをアイテムに割り当てる段階、現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する段階、前記現行の待ち時間カウントを除去期間と比較する段階、及び前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する段階、を有する。
【０００９】
本発明の種々の実施例は、システムを提供する。前記システムは、スケジューラーのキューからアイテムを除去し、フレーム単位の時間で表されるアイテムの許容待ち時間値に等しい大きさを有する負数のような初期にゼロでない待ち時間カウントをアイテムに割り当てる手段、現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する手段、前記現行の待ち時間カウントを除去期間と比較する手段、及び前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する手段、を有し、除去期間は待ち時間カウントに初期に設定された値に対応する値により調整され得る。
【００１０】
本発明の種々の実施例は、局のスケジュール・システムを提供する。前記システムは、１又は複数の入力キュー内のユーザー・データの複数のアイテム及び管理メッセージを処理するスケジューラーを有する。前記アイテムのそれぞれは待ち時間カウントを有する。前記入力キューは所定の大きさ及びアイテムが前記入力キューに到着するレートを有する。前記レートは計算されるか又は予め定められる。前記待ち時間カウントは、前記アイテムが前記スケジューラーの入力キューに置かれてから経過しているフレーム数を示す。またアイテムの待ち時間カウントが前記所定の大きさと前記入力レートとの比を超えた場合、前記アイテムは前記入力キューから除去される。前記比は除去期間である。前記比は、前記スケジューラーの実行の度に動的に計算されるか、又は初期に予め定められて良い。
【００１１】
本発明の以上の実施例は単なる例であり、本発明の全ての実施例はこれらの特徴に限定されない。
【発明を実施するための最良の形態】
【００１２】
本発明の実施例の詳細を参照する。当該例は添付の図面に図示され、図を通じて同様の要素に同様の参照符号が付される。
【００１３】
本発明の種々の実施例は基地局又は加入者局の観点から記載されるが、本発明がそれにより限定されることを意味しない。むしろ本願明細書の記載は、本発明の精神から逸脱することなく実質的に移動局、基地局、又は中継局に等しく適用されて良い。
【００１４】
図２は、本発明の実施例による、相互に通信する基地局及び加入者局のアーキテクチャの例を示す。通信は、基地局２０２、及び基地局２０２と通信する加入者局２０８を有する。しかしながら本発明は加入者局と通信する基地局に限定されない。基地局２０２は、例えば、サービス・フロー２１２に属するデータ・パケットを基地局２０２と通信している加入者局２０８へ送信して良い。ここで受信データ・パケットは、加入者局の対応するサービス・フロー２２２に属する。加入者局２０８は、一方で、サービス・フロー２２４に属する加入者局２０８自身のデータ・パケットを基地局２０２へ送信して良い。ここで受信データ・パケットは、基地局の対応するサービス・フロー２２６に属する。
【００１５】
基地局から加入者局への無線送信２２８は、ユーザー・データ・パケット２１８又は管理メッセージ２２０を伝達するフレームを有して良い。同様に、加入者局から基地局への無線送信２３０は、ユーザー・データ・パケット２３２又は管理メッセージ２３４を伝達するフレームを有して良い。しかしながら本発明は、ユーザー・データ・パケット又は管理メッセージを伝達するフレームに限定されない。
【００１６】
基地局２０２は、媒体アクセス制御（ＭＡＣ）層２１４及びスケジューラー２０４を有し、サービス・フロー２１２に属するデータ・パケット２１８及びＭＡＣ層により生成された管理メッセージ２２０の両方を送信するためにスケジュールする。しかしながら本発明は、媒体アクセス制御及びスケジューラーを有する基地局に限定されない。媒体アクセス制御２１４層は、複数のノード間のネットワークへの物理接続の共有に関連して良い。加入者局２０８は、媒体アクセス制御（ＭＡＣ）２１０層及びスケジューラー２０６を有し、サービス・フロー２２４に属するデータ・パケット２３２及びＭＡＣ層により生成された管理メッセージ２３４の両方を送信するためにスケジュールする。しかしながら本発明は、媒体アクセス制御及びスケジューラーを有する加入者局に限定されない。
【００１７】
基地局２０２のスケジューラー２０４及び加入者局２０８のスケジューラー２０６は、ユーザー・データ・パケット２１８又は２３２及び管理メッセージ２２０又は２３４を処理するための入力キューを有して良い。しかしながら本発明は、ユーザー・データ・パケット及び管理メッセージを処理するための入力キューを有する基地局又は加入者局のスケジューラーに限定されない。ユーザー・データ２１８又は２３２及び管理メッセージ２２０又は２３４は、スケジューラーの入力キューに到着して良く、スケジューラーが他の局への再送のためにスケジュールするまで待つ。ユーザー・データ２１８又は２３２及び管理メッセージ２２０又は２３４は、スケジューラーで異なるキューに置かれて良い。
【００１８】
図３は、基地局又は加入者局の入力キュー３００の例を示す。ユーザー・データ・パケット又は管理メッセージのような入力アイテムは、基地局又は加入者局のスケジューラーに到着し、送信をスケジュールするために入力キュー３００に置かれて良い。しかしながら本発明は、送信をスケジュールするために入力キューに置かれるデータ・パケット又は管理メッセージに限定されない。アイテムは、入力端３０２で入力キュー３００に入って良い。入力キュー３００内のアイテムは、当該アイテムが属するサービス・フローのサービス品質（ＱｏＳ）パラメータにより、又は管理クラス（管理メッセージの場合）により、要求に応じて当該アイテムの優先度に従い順位付けられて良い。例えば図３は、アイテムの待ち時間カウントに従い順位付けられたアイテムを示す。カウントが高いほど、出力端３０４に近い。しかしながら本発明は、アイテムの待ち時間カウントに従い順位付けられる入力アイテムに限定されない。
【００１９】
入力アイテム３１６のような、いくつかの低優先度の入力アイテムは、送信される前に比較的長時間の間、入力キュー３００に残留して良い。入力アイテム３１６が入力キュー３００内で分配前に過ごす時間長が特定の時間長を超えた場合、分配の遅延は、入力アイテム３１６の損失を生じ得る。従って、入力アイテム３１６の分配は、もはや必要ない。更に、入力アイテム３１６のような、より低い優先度のアイテムの分配の遅延は、入力キュー３００を待機アイテムで一杯にし、新たなアイテムが入力キュー３００に入るのを妨げ得る。従って、入力アイテム３１６のような分配が大きく遅れているアイテムを入力キュー３００に保持するより、入力キュー３００から除去することが望ましい。この処理は無効データ除去と称される。
【００２０】
本発明の種々の実施例は、方法を提供する。前記方法では、入力キュー３００に到着するアイテム毎にフレームのカウントが保持される。しかしながら本発明は、入力キューに到着するアイテム毎にフレームのカウントを保持する方法に限定されない。このようなカウントは、待ち時間カウントと称され、無効データ除去を容易にするために使用されて良い。スケジューラーの入力キュー３００に到着するサービス・フローの各アイテムは、待ち時間カウントを割り当てられて良い。待ち時間カウントの単位は、例えば１個のＷｉＭＡＸフレームであって良い。待ち時間カウントの単位は、しかしながら、特定の種類又は単位量に限定されない。
【００２１】
アイテムに割り当てられる待ち時間カウントは、アイテムが入力キューに残っている間、定期的にインクリメントされて良い。ある実施例では、待ち時間カウントは、アイテムが入力キューに残っている間に通過したフレーム数だけインクリメントされて良い。アイテムが分配される前に待ち時間カウントが特定の値に達した場合、当該アイテムは除去されて良い。従って、非常に多くのフレームが通過する間、入力キューに残っているアイテムは、入力キューから除去されて良い。
【００２２】
入力アイテム３０６及び３０８は、例えば、入力キュー３００にごく最近到着しており、それぞれ待ち時間カウント０及び１を割り当てられて良い。アイテム３１０、３１２、３１４及び３１６は、他方で、入力キュー３００でより長く待っており、それぞれ現行の待ち時間カウント３、５、１６及び２０を割り当てられて良い。ある実施例では、アイテムはアイテムの待ち時間カウントを定める構造に包まれる。当該実施例では、待ち時間カウントを定める当該構造は、入力キュー３００に常駐して良く、及びアイテムが分配された後には当該構造に従わなくて良い。
【００２３】
入力キュー３００内の各アイテムの待ち時間カウントは、スケジューラーの実行毎に開始時に更新されて良い。しかしながら本発明は、スケジューラーの実行毎に開始時に更新される入力キュー内のアイテムの待ち時間カウントに限定されない。待ち時間カウントは、アイテムに割り当てられた待ち時間カウントを、前回のスケジューラーの実行から経過したフレーム数だけインクリメントすることにより更新されて良い。
【００２４】
スケジューラーが基地局にある場合、スケジューラーはフレーム毎に実行されて良い。一方で、加入者局はデータを送信する前に、基地局が当該加入者局に帯域を割り当てるのを待たなければならないので、加入者局にあるスケジューラーは、フレーム毎にアイテムを送信しなくて良い。従って、加入者局にあるスケジューラーは、当該局が基地局により当該局に割り当てられた任意の帯域を受信した時のみ実行して良い。
【００２５】
入力キュー３００内の入力アイテムは、それぞれアイテム３１６及び３１８内に、０のような小さい数から２０及び２１のような比較的大きい数までの範囲の異なる値の待ち時間カウントを有する。如何なる大きい数の待ち時間カウントも、アイテムが送信されることなく入力キュー内に長時間の間残留していることを示す。３１８のようなアイテムは、もはや当該アイテムを受信すべき次の局に適さなくて良い。つまり、入力アイテム３１８は「無効」になっており、分配されたとしてももはや適切でないだろう。
【００２６】
本発明の種々の実施例は、方法を提供する。前記方法は、入力アイテム３１８のような無効データを入力キュー３００から除去し、新たなデータのための余地を生成する。しかしながら本発明は、無効データを入力キュー３００から除去し新たなデータのための余地を生成する方法に限定されない。アイテムが再送されずに入力キュー３００内に残り得る時間長は、除去期間Ｔｒｅｍとして定められて良い。入力アイテムの待ち時間カウントが除去期間を超えた場合、入力アイテムは入力キュー３００から除去されて良い。除去期間Ｔｒｅｍは、特定のハードウェア構成要素に対し設定可能、つまり予め定められて良い。他の実施例では、除去期間Ｔｒｅｍは計算されて良い。異なる除去期間が異なるサービス・フローに割り当てられて良い。
【００２７】
入力キュー３００は、例えば、２０の除去期間Ｔｒｅｍを有して良い。しかしながら本発明は、２０の除去期間Ｔｒｅｍを有する入力キューに限定されない。入力アイテム３１８は、入力キュー３００内の他のアイテムより低い優先度で開始し、及び入力キュー３００内の他のアイテムが分配される間、待機しており、もはや関連を有さず、及び従って廃棄され得る。従って、入力アイテム３１８は、２０の除去期間Ｔｒｅｍを超える待ち時間カウント２１を有し、入力キュー３００から除去される。
【００２８】
除去期間Ｔｒｅｍは、現行のトラフィック・レート及びサービス・フローのデータ・パケットがスケジューラーで処理されるスケジューラーの入力キュー３００の残りの大きさからサービス・フローに対し計算されて良い。しかしながら本発明は、現行のトラフィック・レート及び入力キューの残りの大きさから計算される除去期間に限定されない。データ接続が入力キュー３００の一部にのみ割り当てられた場合、除去期間は、現行のトラフィック・レート及びデータ接続に割り当てられたキューの部分の大きさから計算されて良い。特に、
Ｔｒｅｍ＝（キューの残りの大きさ）／（現行のトラフィック・レート）    （１）
ある実施例では、現行のトラフィック・レートはデータ接続の最大維持トラフィック・レート（ＱｏＳパラメータである）により置き換えられて良い。最大維持トラフィック・レートがサービス・フローに対し定められない場合、当該データ接続で可能な最大レート、又は推定最大レートが代わりに使用されて良い。
【００２９】
例えば最大維持トラフィック・レート１０メガビット毎秒（Ｍｂｉｔ／ｓ）のキューに対し１フレームが５ミリ秒（ｍｓ）であり、且つ当該キュー内に３００キロバイト（ＫＢ）残っている場合、除去期間は次の通りである。
［（３０００００バイト）（８ビット／バイト）／（１０００００００ビット／ｓ）］（１０００ｍｓ／ｓ）／（５ｍｓ／フレーム）＝４８フレーム
本発明の種々の実施例は、入力キュー内のアイテムの待ち時間カウントを計算する方法を提供する。入力キュー内のアイテムが属するサービス・フローのサービス品質（ＱｏＳ）パラメータは、当該アイテムの待ち時間カウントを導出するために使用される。ある実施例では、ジッターのようなタイミング要件を課すサービス品質パラメータ、及び最大待ち時間は、入力アイテムがスケジューラーのキューに到着した時に、待ち時間カウントを当該入力アイテムの初期値に設定するために使用される。この場合、待ち時間カウントは初期に、フレーム単位の時間で許容待ち時間に等しい大きさを有する負数に設定される。これは、サービス・フローに属する入力アイテムが、ユーザーの容認可能性を失わずにどれだけ多くのフレーム遅延を生じて良いかを意味する。待ち時間カウントは、どれだけ多くのフレームが更新と更新の間で経過したかを示す数を加算することにより、通常の方法で更新される。初期の負の値の使用は、（単に待ち時間カウントが依然として負であるかどうかを検査することにより）アイテムが依然として許容待ち時間の範囲内にあるかどうかを検査するのに便利である。しかしながら本発明は、待ち時間カウントに負の初期値を使用することに依存しない。除去期間が入力アイテムの待ち時間カウントと比較される時に初期値を考慮に入れるならば、如何なる初期値が使用されても良い。
【００３０】
待ち時間又はジッターを使用しないデータ接続では、待ち時間カウントは初期にゼロに設定されて良い。待ち時間カウントは、待ち時間カウントに前回のスケジューラーの実行から経過したフレーム数を加算することにより、スケジューラーの実行毎に開始時に更新されて良い。
【００３１】
キューに入るアイテムが既に発生したある待ち時間を有する場合、待ち時間カウントは、発生した待ち時間に等しい正数を待ち時間カウントに加算することにより、調整されて良い。これは、例えばパケットを生成してから送信のためにスケジューラーへパケットを委託するまでの間にある遅延が存在する場合である。
【００３２】
待ち時間カウント又はジッターを使用するデータ接続では、（初期値はゼロでないので）除去期間は待ち時間カウントの初期値で調整されて良い。除去期間に、待ち時間カウントの初期値に等しい数を加算して良い（これは、初期値が負である場合、除去期間値が減少することを意味する）。しかしながらこの調整は、許容待ち時間が式（１）から計算される除去期間の値より非常に小さいので必要不可欠ではない。
【００３３】
図４は、スケジューラーの入力キュー内にある各入力アイテムの待ち時間カウントを更新し、任意的に除去期間を更新し、待ち時間カウントを除去期間と比較し、及びスケジューラーのキューからアイテムを除去する手順を説明するフローチャートである。これら全ての動作は、スケジューラーの実行毎に開始時に実行される。図４を参照する。動作４０２で、入力アイテムの待ち時間カウントは、前回のスケジューラーの実行から経過したフレーム数を加算することにより更新される。このフレーム数の情報は、全ての送信フレームをＭＡＣ層で番号付けすることにより、及び動作４０４に示されるようにスケジューラーの実行毎に現行のフレームを記憶し、次に動作４０２で記憶したフレームを次のスケジューラーの実行時に現行のフレーム番号と比較することにより、得られて良い。
【００３４】
処理は動作４０４から動作４０６へ進む。動作４０６では、除去期間は使用されるサービス・フローに対し再計算される。この動作は任意であり、システム設計及びシステム構成の間に実行されるよう設定されて良い。上述の式（１）に示された除去期間Ｔｒｅｍの式は、待ち時間カウントの初期値Ｔａによる調整を有する。Ｔａはサービス・フローの許容待ち時間であって良い（サービス・フローに如何なるタイミング要件も存在しない場合、当該許容待ち時間の値はゼロであって良い）。
【００３５】
処理は動作４０６から動作４０８へ進む。動作４０８で比較が現行の待ち時間カウントは除去期間Ｔｒｅｍを超えたと示す場合、動作４１０でアイテムはキューから除去される。
【００３６】
図４は単なる例である処理を示す。また本発明の実施例は、図４に示される全ての動作を有する処理に限定されない。代わりに、いくつかの動作は、本発明の精神から逸脱することなく削除されるか、又は再配置されて良い。
【００３７】
図５は、キューに入るアイテムの待ち時間カウントを設定する手順を説明するフローチャートである。図５を参照する。動作５０２で、新たな入力アイテムが属するサービス・フローが最大待ち時間パラメータを満たさなければならないかどうかが検査される（最大待ち時間パラメータはＱｏＳ待ち時間パラメータから直接に得るか、又はジッター等から計算されて良い）。当該検査の結果が肯定的である場合、動作５０４で、キューに入るアイテムの待ち時間カウントは、許容待ち時間値と等しい大きさを有する負数に設定される。当該検査の結果が否定的である場合、動作５０６で、キューに入るアイテムの待ち時間カウントは、ゼロに設定される。
【００３８】
処理は動作５０４又は５０６から動作５０８へ進む。動作５０８では、アイテムの待ち時間カウントは、入力アイテムの既に発生している待ち時間に等しい正数Ｔａｃｃｒｕｅｄを加算することにより、調整される。
【００３９】
処理は動作５０８から動作５１０へ進む。動作５１０では、除去期間は入力アイテムのサービス・フローに対し決定される（当該サービス・フローは全ての入力アイテムに適用可能である）。この動作は、新たに開かれたサービス・フローの最初のアイテムにのみ必要である。除去期間がスケジューラーの実行毎に動的に再計算されて良いので、この動作は任意であり、システム設計及びシステム構成の間に実行されるよう設定されて良い。除去期間Ｔｒｅｍの式は、式（１）に示され、待ち時間カウントの初期値Ｔａによる調整を有する。Ｔａはサービス・フローの許容待ち時間（サービス・フローに如何なるタイミング要件も存在しない場合、この値はゼロであって良い）であって良い。
【００４０】
図５は単なる例である処理を示す。また本発明の実施例は、図５に示される全ての動作を有する処理に限定されない。代わりに、いくつかの動作は、本発明の精神から逸脱することなく削除されるか、又は再配置されて良い。
【００４１】
本発明の実施例は、改正又は拡張を含むＩＥＥＥ８０２．１６規格に従い動作する局に適用可能である。しかしながら、本発明の実施例は当該規格に限定されない。むしろ、他の規格に従い動作する局、又は如何なる規格にも従わない局は、本発明の精神から逸脱することなく実施され得る。更にＩＥＥＥ８０２．１６規格の全体は参照されることにより本願明細書に組み込まれる。
【００４２】
本発明のいくつかの好適な実施例が示され及び記載されたが、当業者は、請求項に範囲を定められた本発明及び本発明の等価物の原理及び精神から逸脱することなく、これら実施例に変更がなされ得ることを理解するだろう。
【００４３】
（付記）
（付記１）  無線ネットワークにある局のスケジューラーであって、前記スケジューラーは、アイテムのキュー及び除去期間を有し、各アイテムはスケジューラーを実行する度に更新される待ち時間カウントを有し、アイテムは、前記アイテムに関連付けられた現行の待ち時間カウントが前記除去期間を超えた場合、前記キューから除去される、スケジューラー。
（付記２）  前記キューに入るアイテムの待ち時間カウントは、前記アイテムの許容待ち時間値と等しい大きさを有する負数に設定される、付記１記載のスケジューラー。
（付記３）  前記キューに入るアイテムの待ち時間カウントは、サービス品質の待ち時間パラメータ又はジッター・パラメータから計算される、付記１記載のスケジューラー。
（付記４）  前記キューに入るアイテムの待ち時間カウントはゼロに設定される、付記１記載のスケジューラー。
（付記５）  前記アイテムの待ち時間カウントは、前回のスケジューラーの実行から経過したフレーム数を前記待ち時間カウントに加算することにより、前記スケジューラーの実行の開始時に更新される、付記１記載のスケジューラー。
（付記６）  前記除去期間は、前記キューの長さと現行のトラフィック・レートとの比に等しい、付記１記載のスケジューラー。
（付記７）  前記除去期間は、前記キューの長さと最大維持トラフィック・レートとの比に等しい、付記１記載のスケジューラー。
（付記８）  スケジューラーのキューからアイテムを除去する方法であって、
アイテムの許容待ち時間に等しい大きさを有する負数に等しい待ち時間カウントを前記アイテムに割り当てる段階、
現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する段階、
前記現行の待ち時間カウントを除去期間と比較する段階、及び
前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する段階、を有する方法。
（付記９）  前記待ち時間カウントは、サービス品質の待ち時間パラメータ又はジッター・パラメータから計算される、付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１０）  前記キューに入るアイテムの待ち時間カウントを、前記アイテムの許容待ち時間値と等しい大きさを有する負数に設定する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１１）  前記キューに入るアイテムの待ち時間カウントを、サービス品質の待ち時間パラメータ又はジッター・パラメータから計算する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１２）  前記キューに入るアイテムの待ち時間カウントを、ゼロに設定する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１３）  前回のスケジューラーの実行から経過したフレーム数を前記待ち時間カウントに加算することにより、前記スケジューラーの実行の開始時に前記アイテムの待ち時間カウントを更新する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１４）  前記除去期間を、前記キューの長さと現行のトラフィック・レートとの比に等しく設定する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１５）  前記除去期間を、前記キューの長さと最大維持トラフィック・レートとの比に等しく設定する段階、を更に有する付記８記載のスケジューラーのキューからアイテムを除去する方法。
（付記１６）  スケジューラーのキューからアイテムを除去するシステムであって、
前記アイテムの許容待ち時間に等しい大きさを有する負数を待ち時間カウントに割り当てる手段、
現行の待ち時間カウントを得るため、前回のスケジューラーの実行から経過しているフレーム数を前記スケジューラーの実行の度に前記待ち時間カウントに加算する手段、
前記現行の待ち時間カウントを除去期間と比較する手段、及び
前記比較が前記現行の待ち時間カウントは前記除去期間を超えていると示す場合、前記アイテムが前記キューから出力される前に前記アイテムを除去する手段、を有するシステム。
（付記１７）  局のスケジュール・システムであって、
１又は複数の入力キュー内のユーザー・データ及び管理メッセージの複数のアイテムを処理するスケジューラー、を有し、前記アイテムのそれぞれは待ち時間カウントを有し、
前記入力キューは所定の大きさ及びアイテムが前記入力キューに到着する計算された又は所定のレートを有し、
前記待ち時間カウントは、スケジューラーの実行の度に、前記アイテムが前記入力キューに置かれてから前記スケジューラーを経過したフレーム数だけインクリメントされ、及び
アイテムの待ち時間カウントが前記所定の大きさと前記所定のレートとの比を超えた場合、前記アイテムは前記入力キューから除去される、システム。
【図面の簡単な説明】
【００４４】
【図１】従来技術による通信ネットワークのセルの例を示す。
【図２】本発明の実施例による、通信ネットワーク内の基地局及び加入者局のアーキテクチャの例を示す。
【図３】本発明の実施例による、基地局又は加入者局の入力キューの例を示す。
【図４】本発明の実施例による、スケジューラーの実行時にスケジューラーの入力キューからアイテムを除去する手順を説明するフローチャートである。
【図５】本発明の実施例による、キューに入るアイテムの待ち時間カウントを設定する手順を説明するフローチャートである。
【符号の説明】
【００４５】
１００  通信ネットワーク
１０２、２０２  基地局
１０４  中継局
１０６、１０８、２０８  加入者局
１１０  サービス領域
１１２、１１４、１１６  通信経路
２０４、２０６  スケジューラー
２１０、２１４  媒体アクセス制御（ＭＡＣ）層
２１２、２２２、２２４、２２６  サービス・フロー
２１８、２３２  ユーザー・データ・パケット
２２０、２３４  管理メッセージ
２２８、２３０  無線送信
３００  入力キュー
３０２  入力端
３０４  出力端
３０６、３０８、３１０、３１２、３１４、３１６、３１８  アイテム
【図１】
2008125073.tif 000003
【図２】
2008125073.tif 000004
【図３】
2008125073.tif 000005
【図４】
2008125073.tif 000006
【図５】
2008125073.tif 000007