(57)【要約】【課題】  待ち行列設計及び待ち行列内のアイテムの管理が改善された、無線ネットワーク内の局からのアイテムの送信をスケジューリングする装置及び方法を提供する。【解決手段】  スケジューラは、無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングする。加入者局によって送信されるべきアイテムは待ち行列に格納される。この待ち行列は、基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する。スケジューラは、アイテムが待ち行列の何れの区画にあるかに従って、加入者局による送信のために待ち行列内のアイテムをスケジューリングする。【選択図】図１
2008125071.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングするスケジューラ；及び
前記加入者局によって送信されるべきアイテムが格納される待ち行列であり、前記基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、前記基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する待ち行列；
を有する装置であって：
前記スケジューラは、前記待ち行列の第２区画内のアイテムを送信のためにスケジューリングする前に、前記待ち行列の第１区画内のアイテムを前記加入者局による送信のためにスケジューリングする、装置。
【請求項２】
前記待ち行列の第２区画内のアイテムは、当該待ち行列の第２区画内のアイテムに関する帯域幅割当て要求が前記基地局に対して為されたとき、前記待ち行列の第１区画に動的に移動される、請求項１に記載の装置。
【請求項３】
前記待ち行列の第１区画、前記待ち行列の第２区画、又は前記待ち行列の第１区画と前記待ち行列の第２区画との双方、の何れかはいつでもエンプティになり得る、請求項１に記載の装置。
【請求項４】
当該装置は加入者局によって送信されるべきアイテムが格納される複数の待ち行列を有し、所定クラスのサービスフローのアイテムは自動的に、前記複数の待ち行列のうちの同一の待ち行列に格納される、請求項１に記載の装置。
【請求項５】
無線ネットワーク内の加入者局によって送信されるべきアイテムを、基地局からの帯域幅の割当てに従ってスケジューリングするスケジューラ；及び
前記加入者局によって送信されるべきアイテムが格納される待ち行列であり、帯域幅の割当てが為されたアイテムが格納される、当該待ち行列の先頭に位置する第１区画と、帯域幅の割当てが未だ為されていないアイテムが格納される第２区画とを有する待ち行列；
を有する装置。
【請求項６】
送信されるべくスケジューリングされる前に帯域幅が割当てられる必要がないアイテムは、前記待ち行列の第１区画に格納される、請求項５に記載の装置。
【請求項７】
無線ネットワーク内の加入者局のスケジューラの待ち行列の第１区画に、基地局に対して帯域幅割当て要求が為されたアイテムを格納する段階；
前記待ち行列の第２区画に、前記基地局に対して帯域幅割当て要求が未だ為されていないアイテムを格納する段階；及び
前記待ち行列内のアイテムを、前記基地局に対して為された帯域幅割当て要求に応じて前記基地局により該アイテムに割り当てられた帯域幅に従って加入者局によって送信されるようにスケジューリングする段階；
を有する方法であって：
前記待ち行列の第１区画内のアイテムは、前記待ち行列の第２区画内のアイテムが前記加入者局によって送信されるべくスケジューリングされる前に、前記加入者局によって送信されるべくスケジュールされる、方法。
【請求項８】
前記待ち行列の第２区画内のアイテムを、該待ち行列の第２区画内のアイテムに関する帯域幅割当て要求が前記基地局に対して為されたとき、前記待ち行列の第１区画に動的に移動させる段階、を更に有する請求項７に記載の方法。
【請求項９】
前記待ち行列がジッターキュー又はレイテンシキューである請求項７に記載の方法であって：
前記基地局に対して帯域幅割当て要求が為された競合アイテムを前記待ち行列の第１区画の競合区画に格納する段階；
前記基地局に対して帯域幅割当て要求が為された非競合アイテムを前記待ち行列の第１区画の非競合区画に格納する段階；
前記基地局に対して帯域幅割当て要求が未だ為されていない競合アイテムを前記待ち行列の第２区画の競合区画に格納する段階；及び
前記基地局に対して帯域幅割当て要求が未だ為されていない非競合アイテムを前記待ち行列の第２区画の非競合区画に格納する段階；
を更に有する方法。
【請求項１０】
無線ネットワーク内の加入者局によって処理されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられたサービスに従ってスケジューリングする段階；
前記基地局によるサービスの割当てが未だ要求されていないアイテムをまとめて、待ち行列の未要求区画内にグループ化する段階；及び
前記待ち行列の未要求区画内のアイテムを処理する前に、前記待ち行列の要求済み区画内の如何なるアイテムをも処理する段階；
を有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アイテムの送信をスケジューリングする装置及び方法に関し、より具体的には、無線ネットワーク内の局からのアイテムの送信をスケジューリングする装置及び方法に関する。
【背景技術】
【０００２】
無線ネットワークは通信においてますます普及してきており、一般に、ある一定エリア内に通信を行う多数の局を含んでいる。一部の種類の無線ネットワークにおいては、１つの局から別の局に送信されるアイテムは、送信のためにスケジューラによってスケジューリングされる。このように送信のためにアイテムをスケジューリングすることは、伝送のための帯域幅の割当てを必要とする。
【０００３】
例えば、しばしば“WiMAX”と呼ばれる電気電子技術者協会（IEEE）802.16規格に基づく無線ネットワークにおいては、加入者局（subscriber  station；ＳＳ）がそれら同士で相互に、及び基地局（Base  station；ＢＳ）と通信を行う。加入者局は、例えば、移動局（mobile  station；ＭＳ）又は中継局（relay  station；ＲＳ）であり得る。加入者局が別の加入者局又は基地局にアイテムを送信するとき、送信側の加入者局は先ず、これを行う伝送のための帯域幅の割当てを基地局から得なければならず、加入者局は基地局に帯域幅の要求を行う。この要求に応答し、基地局は帯域幅の割当てを行う。そして、加入者局のスケジューラは基地局による帯域幅の割当てに従って送信アイテムを適切に処理しなければならない。
【０００４】
従って、加入者局による送信のためにアイテムをスケジューリングするスケジューラは周知である。また、このような加入者局による基地局への帯域幅要求と、該要求に応答しての基地局による帯域幅割当てとに従ったスケジューリングは周知である。
【０００５】
さらに、加入者局のスケジューラは、しばしば、加入者局による送信のために多数のアイテムを、該アイテムのための帯域幅要求及び帯域幅割当てに従ってスケジューリングしなければならない。送信アイテムは典型的に待ち行列（キュー）内に置かれ、帯域幅要求及び帯域幅割当てに従って送信のために待ち行列から取り出される。結果として、待ち行列内のアイテムを管理することは複雑且つ非効率になっている。
【０００６】
故に、改善された待ち行列設計、待ち行列内のアイテムの改善された管理、及びそれらによるシステム性能の向上が望まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、待ち行列設計及び待ち行列内のアイテムの管理が改善され、それにより性能が向上された、無線ネットワーク内の局からのアイテムの送信をスケジューリングする装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様に従って提供される装置は、（ａ）無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングするスケジューラ、及び（ｂ）加入者局によって送信されるべきアイテムが格納される待ち行列を含んでいる。この待ち行列は、基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する。スケジューラは、待ち行列の第２区画内のアイテムを送信のためにスケジューリングする前に、待ち行列の第１区画内のアイテムを加入者局による送信のためにスケジューリングする。
【０００９】
本発明の一態様に従って提供される装置は、（ａ）無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングする手段、及び（ｂ）加入者局によって送信されるべきアイテムが格納される待ち行列を含んでいる。この待ち行列は、基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する。スケジューリングする手段は、待ち行列の第２区画内のアイテムを送信のためにスケジューリングする前に、待ち行列の第１区画内のアイテムを加入者局による送信のためにスケジューリングする。
【００１０】
本発明の一態様に従って提供される装置は、（ａ）無線ネットワーク内の加入者局によって送信されるべきアイテムを、基地局からの帯域幅の割当てに従ってスケジューリングするスケジューラ、及び（ｂ）加入者局によって送信されるべきアイテムが格納される待ち行列を含んでいる。この待ち行列は、帯域幅の割当て要求が為されたアイテムが格納される、当該待ち行列の先頭に位置する第１区画と、帯域幅の割当てが未だ為されていないアイテムが格納される第２区画とを有する。
【００１１】
本発明の一態様に従って提供される方法は、（ａ）無線ネットワーク内の加入者局のスケジューラの待ち行列の第１区画に、基地局に対して帯域幅割当て要求が為されたアイテムを格納する段階、（ｂ）待ち行列の第２区画に、基地局に対して帯域幅割当て要求が未だ為されていないアイテムを格納する段階、及び（ｃ）待ち行列内のアイテムを、基地局に対して為された帯域幅割当て要求に応じて基地局により該アイテムに割り当てられた帯域幅に従って加入者局によって送信されるようにスケジューリングする段階を含む。待ち行列の第１区画内のアイテムは、待ち行列の第２区画内のアイテムが加入者局によって送信されるべくスケジューリングされる前に、加入者局によって送信されるべくスケジュールされる。
【００１２】
本発明の一態様に従って提供される方法は、（ａ）無線ネットワーク内の加入者局によって処理されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられたサービスに従ってスケジューリングする段階、（ｂ）基地局によるサービスの割当てが未だ要求されていないアイテムをまとめて、待ち行列の未要求区画内にグループ化する段階、及び（ｃ）待ち行列の未要求区画内のアイテムを処理する前に、待ち行列の要求済み区画内の如何なるアイテムをも処理する段階を含む。
【００１３】
本発明の上記態様は単なる例であり、本発明の全ての実施形態がこれらの例、又はこれらの例に含まれる特徴に限定されるわけではない。
【００１４】
本発明の更なる態様は、部分的に以下の記載にて説明され、部分的に該記載から明らかになり、あるいは本発明の実施により教示される。
【発明を実施するための最良の形態】
【００１５】
ここでは添付の図面に示された実施例を参照し、本発明の実施形態を詳細に説明する。図面においては全体を通じて、似通った参照符号は似通った要素を参照するものとする。
【００１６】
図１は、無線ネットワーク内にある、スケジューラ105を含む加入者局100の一例を示している。無線ネットワークは、例えば、しばしば“WiMAX”ネットワークと呼ばれるIEEE802.16ネットワークとし得る。しかしながら、本発明はIEEE802.16ネットワークに限定されるものではなく、むしろ、数多くのその他の種類のネットワークにも適用可能なものである。また、本発明は移動ネットワーク若しくは固定ネットワーク、又は移動局若しくは固定局に限定されるものではない。
【００１７】
加入者局100は、例えば、移動局（ＭＳ）又は中継局（ＲＳ）とし得る。しかしながら、加入者局は如何なる特定種類の局にも限定されるものではない。一例として、加入者局は或る種の固定位置局とし得る。加入者局（ＳＳ）は、一般に、基地局（ＢＳ）と交信する如何なる種類の局であってもよい。スケジューラ105は無線ネットワーク170内で加入者局100によって送信されるアイテムをスケジューリングする。本発明は如何なる特定位置にあるスケジューラ105にも限定されるものではない。
【００１８】
加入者局100によるアイテムの送信のスケジューリングは、ネットワーク170内の基地局150による該アイテムへの帯域幅の割当て162に従ってスケジューラ105によって行われる。
【００１９】
スケジューラは、図１に示されるように、加入者局により送信されるアイテムが格納される待ち行列（キュー）110を含んでいる。図１に更に示されるように、本発明の一実施形態によれば、待ち行列110は第１区画120及び第２区画130を含んでいる。待ち行列に格納されるアイテムは、例えば、ユーザ層から供給されるデータパケット、又はシステム層から供給される管理メッセージである。例えば、ネットワークが802.16ネットワークである場合、これらアイテムは例えばネットワークのメディアアクセス制御（ＭＡＣ）層にて生成される管理メッセージであってもよい。しかしながら、本発明は如何なる特定種類の情報若しくはフォーマットのアイテム、又はネットワークの如何なる特定レベルにて生成されるアイテムにも限定されるものではない。これらアイテムは、むしろ、スケジューラ105によるスケジューリングを必要とするような、加入者局により送信される如何なるものであってもよい。
【００２０】
待ち行列110の第１区画120は、基地局150に対して帯域幅割当て要求161が既に為されたアイテムが格納される区画である。待ち行列110の第２区画130は、基地局150に対して帯域幅割当て要求161が未だ為されていないアイテムが格納される区画である。スケジューラ105は、待ち行列110の第２区画130内のアイテムが送信のためにスケジューリングされる前に、待ち行列110の第１区画内のアイテムを加入者局による送信のためにスケジューリングする。
【００２１】
図１は、点線140により表される第１区画120と第２区画130との間での待ち行列110の分割の一例を示している。この分割は動的であると考えられる。何故なら、例えば、待ち行列の第２区画内の或るアイテムに関する帯域幅割当て要求が基地局150に対して為された後には、待ち行列110内の第２区画130内の該アイテムは待ち行列110の第１区画120へと動的に移動させられるからである。
【００２２】
本発明の実施形態は、基地局150からの“帯域幅”割当てに従った送信のためのアイテムのスケジューリングに限定されるものではない。故に、帯域幅の割当ては基地局150によるサービスの割当てであると考えることができる。本発明の様々な実施形態においては、アイテムは送信のための基地局による帯域幅割当て以外の別のサービスに従って、送信のためにスケジューリングされてもよい。故に、ここで説明される基地局によって帯域幅が割り当てられることに関する様々な実施形態は、帯域幅以外の異なるサービスが基地局によって割り当てられる状況にも適用可能である。
【００２３】
図１は、無線ネットワーク内で作動するスケジューラ及び待ち行列を含む加入者局、及び単一の基地局の単なる一例である。例えば、本発明の実施形態は単一の待ち行列を有するスケジューラに限定されるものではなく、スケジューラは加入者局により送信されるアイテムが格納される複数の待ち行列を有することができる。さらに、所定クラスのサービスフローに属するアイテムは、複数の待ち行列のうちの同一の待ち行列に自動的に格納されることが可能である。サービスフローは論理結合であり、例えば待ち時間（レイテンシ）及びジッター等の既定のパラメータを有し得る。
【００２４】
図２は、区画分けされた待ち行列の一例を示している。図２に示されるように、待ち行列110は、例えば“要求済み区画”とでも呼び得る第１区画120と、例えば“未要求区画”とでも呼び得る第２区画130とに分割されることが可能である。帯域幅割当てが既に要求されたアイテム、すなわち、アイテム121、アイテム122、・・・等は待ち行列110の第１区画120に格納されている。第１区画120は、例えば、待ち行列の先頭210に近い側にある。帯域幅割当てが未だ要求されていないアイテム、すなわち、アイテム131、アイテム132、アイテム133、アイテム134、・・・等は待ち行列110の第２区画130に格納されている。第２区画130は、例えば、待ち行列の末尾220に近い側にある。しかしながら、本発明は第１区画120が待ち行列の先頭210の近くにあり且つ第２区画130が待ち行列の末尾220の近くにあることに限定されるものではない。
【００２５】
本発明の一実施形態によれば、待ち行列110内のアイテムは、待ち行列の先頭210から待ち行列の末尾220への規則的な待ち行列順序を有しているとしてもよい。すなわち、アイテムは規則的な待ち行列順序で待ち行列の入口230に入り、待ち行列の出口240を出てもよい。待ち行列110の第１区画120にあるアイテムには自動的に、より高い優先度が与えられ得る。これは待ち行列内でのこれら区画の配置、すなわち、要求済み区画は未要求区画の前方にあることに従うものである。また、第１区画120又は第２区画130の何れかは所与の時点で空（エンプティ）であってもよい。
【００２６】
このような分割は、例えば、ネットワーク内でのスケジューラを有する加入者局の実施を実現させるものであり、帯域幅が要求されなければならないアイテムを含む入力待ち行列に適用可能である。このような入力待ち行列は、ユーザデータ待ち行列、及び例えばＭＡＣ管理待ち行列である管理待ち行列を含む。本発明の一実施形態によれば、帯域幅の割当てが不要なアイテムは待ち行列110の第１区画120に格納されることができる。
【００２７】
図２は、２つの区画に分割され、第１区画が２アイテムを有し、第２区画が４アイテムを有する待ち行列の単なる一例である。本発明の様々な実施形態はこのように限定されるものではなく、これら区画内に如何なる数のアイテムが格納されたものをも含むことができる。
【００２８】
図３は、本発明の一実施形態に従った、スケジューラの待ち行列の特定の区画にアイテムを格納する処理を示している。操作300にて、送信されるべきアイテムがスケジューラ105に入力される。この処理は操作300から操作305へと進み、帯域幅割当て要求が基地局に対して為されたかに関して決定が為される。
【００２９】
帯域幅割当て要求が基地局に対して為されたと決定されると、処理は操作305から操作310へと進み、帯域幅割当て要求が基地局に対して為されたアイテムは、無線ネットワーク内の加入者局のスケジューラに含まれる待ち行列の第１区画に格納される。
【００３０】
帯域幅割当て要求が基地局に対して為されたと決定されない場合には、処理は操作305から操作320へと進み、帯域幅割当て要求が基地局に対して未だ為されていないアイテムは、上記の待ち行列の第２区画に格納される。
【００３１】
図３に示されるように、処理は操作310から操作330へと進み、待ち行列内のアイテムは、基地局に対して為された帯域幅割当て要求に応じて基地局により該アイテムに割り当てられた帯域幅に従って加入者局によって送信されるようにスケジューリングされる。
【００３２】
本発明の一実施形態によれば、待ち行列の第１区画内のアイテムは、待ち行列の第２区画内のアイテムが加入者局によって送信されるようにスケジューリングされる前に、加入者局によって送信されるようにスケジューリングされる。基地局により割り当てられた帯域幅が、待ち行列の第１区画内のアイテムのスケジューリングによって使い尽くされない場合、待ち行列の第２区画内のアイテムもまた送信されるようにスケジューリングされる。図３に示されるように、処理は操作330から操作340へと進み、アイテムが待ち行列から出力される。本発明の実施形態は、例えば、２つの区画の一方にアイテムを格納することのみに限定されるものではなく、更に細分化された区画にアイテムを格納することを含み得る。
【００３３】
操作300、305、310、320及び330は、例えば、スケジューラ105のようなスケジューラによって実行される。操作340は、例えば、加入者局によって実行される。しかしながら、本発明は、図３の具体的な操作がスケジューラ又は加入者局によって実行されることに限定されるものではない。
【００３４】
操作の一例として、新たに到来したアイテムは、加入者局のスケジューラに含まれる待ち行列の未要求区画に格納されることが可能である。加入者局は１つの入力アイテムのための帯域幅要求を個々に発してもよいし、複数のアイテムのための帯域幅要求をまとめて発してもよい。１つ又は複数のアイテムのために帯域幅が要求されると、それぞれのアイテム又はアイテム群は、同一の待ち行列の他方の区画すなわち要求済み区画に移動される。帯域幅が割り当てられると、加入者局は、基地局により送信された例えばマップ等のその他の特徴から、送信するアイテムの量を決定することができ、また、待ち行列の先頭から可能な限り多くのアイテムを効率良く送出することができる。
【００３５】
従って、この送信処理が行われるとき、アイテムが実際に待ち行列の未要求区画又は要求済み区画の何れにあるかは、スケジューラがアイテムの優先順序を守りながら可能な限り多くのアイテムを待ち行列から送出することが可能なこの効率的な処理には影響を及ぼさない。
【００３６】
例えばアンソリシッティド・グラント・サービス（Unsolicited  Grant  Service；ＵＧＳ）フローに属するアイテムといった一部の種類のアイテムは帯域幅割当て要求なしで送信されることができる。例えば、携帯電話は帯域幅が要求されないＵＧＳのようなサービスを使用することが可能である。例えばこれらサービスフロー用に加入者局によって帯域幅要求が発せられないクラスに属するデータパケット等のアイテムは、入力待ち行列の第１区画に直ちに格納されることができる。
【００３７】
一部の場合、加入者局は要求した帯域幅より大きい帯域幅を割り当てられてもよい。本発明の一実施形態によれば、加入者局は該加入者局が未だ帯域幅を要求していないデータアイテムさえも送信することができる。従って、本発明の様々な実施形態の利点は、待ち行列の区画にグループ化されたアイテム群を有することにより、アイテムが効率的に処理され得る、すなわち、待ち行列の先頭から送信され得ることである。
【００３８】
図４は本発明の一実施形態に従った処理を例示しており、操作400にて基地局からの帯域幅割当てを要求している。処理は操作400から操作405へと進み、帯域幅の割当てが基地局から要求されたかが決定される。
【００３９】
帯域幅要求が基地局に対して為されたと決定されると、処理は操作410へと進み、待ち行列の第２区画内のアイテムが待ち行列の第１区画に動的に移動される。
【００４０】
処理は操作410から430へと進み、待ち行列内のアイテムは基地局に対して為された帯域幅割当て要求に応じて基地局により該アイテムに割り当てられた帯域幅に従って加入者局によって送信されるようにスケジューリングされる。処理は操作430から操作440へと進み、アイテムが出力される。
【００４１】
本発明の実施形態は、アイテムを第２区画から第１区画へと移動させる処理のみに限定されるものではなく、区画内の部分区画へのアイテムの移動といったその他の移動を含み得る。本発明の一実施形態によれば、待ち行列の第１区画、待ち行列の第２区画、又はこれら双方はいつでもエンプティになり得る。
【００４２】
操作405、410及び430は、例えば、スケジューラ105のようなスケジューラによって実行される。操作400及び440は、例えば、加入者局によって実行される。しかしながら、本発明は、図４の具体的な操作がスケジューラ又は加入者局によって実行されることに限定されるものではない。
【００４３】
本発明の一実施形態に従って、待ち行列はジッターキュー又はレイテンシキューとし得る。図５は、第１区画501すなわち要求済み部分、及び第２区画502すなわち未要求部分を有する待ち行列500を示している。さらに、待ち行列の第１区画501は、アイテム551及び552を有する競合区画510と、アイテム553、554、555及び556を有する非競合区画520とを有している。同様に、待ち行列の第２区画502は、アイテム557、558及び559を有する競合区画511と、アイテム560、561及び562を有する非競合区画521とを有している。本発明の一実施形態によれば、待ち行列500内のアイテムは、待ち行列の末尾542の待ち行列の入口530と待ち行列の先頭541の待ち行列の出口540とを有する規則的な待ち行列順序を有しているとしてもよい。本発明の実施形態はこのように限定されるものではなく、複数の待ち行列の複数の区画に如何なる数のアイテムを含んでいてもよい。
【００４４】
図６は、待ち行列がジッターキュー又はレイテンシキューであり得る本発明の一実施形態に従った処理を示している。本発明の一実施形態によれば、一部のアイテムは優先度に関して互いに競合していると考えられ、これらは“競合（contention）”アイテムと呼ばれ得る。優先度に関して互いに競合していないアイテムは“非競合（non-contention）”アイテムと呼ばれ得る。
【００４５】
図６を参照するに、操作600にて、アイテムが待ち行列500に入力される。処理は操作600から操作605へと進み、基地局に対して帯域幅割当て要求が為されたかが決定される。基地局に対して帯域幅割当て要求が為されたと決定されると、処理は、基地局に対して帯域幅割当て要求が為された競合アイテムが待ち行列の第１区画501の競合区画510に格納される操作610と、基地局に対して帯域幅割当て要求が為された非競合アイテムが待ち行列の第１区画501の非競合区画520に格納される操作620とに進む。
【００４６】
逆に、基地局に対して帯域幅割当て要求が為されていないと決定されると、処理は、基地局に対して帯域幅割当て要求が未だ為されていない競合アイテムが待ち行列の第２区画502の競合区画511に格納される操作630と、基地局に対して帯域幅割当て要求が未だ為されていない非競合アイテムが待ち行列の第２区画502の非競合区画521に格納される操作640とに進む。
【００４７】
言い換えると、未要求部分及び要求済み部分の各々が非競合／競合の対を形成する。本発明の一実施形態によれば、待ち行列の要求済み部分及び未要求部分でもある、これら２つの非競合／競合の対のみが待ち行列に作り出される。本発明の実施形態は、例えば、第１区画及び第２区画のみにアイテムを格納することに限定されるものではなく、その他の分割配置を含み得る。
【００４８】
操作600、605、610、620、630及び640は、例えば、スケジューラ105のようなスケジューラによって実行される。しかしながら、本発明は、図６の具体的な操作がスケジューラによって実行されることに限定されるものではない。
【００４９】
本発明の一実施形態に従って、処理はサービス（例えば帯域幅割当て等）が未だ要求されていないアイテムを一緒にグループ化することを含む。図７に例示されるように、この処理はアイテムが入力される操作700を含んでいる。操作705にて、無線ネットワーク内の加入者局によって処理されるべきアイテムは、該ネットワーク内の基地局によって該アイテムに割り当てられたサービスに従ってスケジューリングされる。処理は操作705から操作710へと進み、基地局によるサービスの割当てが未だ要求されていないアイテムは一緒に、待ち行列の未要求区画内にグループ化される。
【００５０】
処理は操作710から操作720へと進み、待ち行列の要求済み区画内の如何なるアイテムも、待ち行列の未要求区画内のアイテムが処理される前に処理される。本発明の一実施形態によれば、サービスは基地局によるアイテムへの帯域幅割当てである。
【００５１】
操作700、705、710及び720は、例えば、スケジューラ105のようなスケジューラによって実行される。しかしながら、本発明は、図７の具体的な操作がスケジューラ又は加入者局によって実行されることに限定されるものではない。
【００５２】
本発明の実施形態は、例えば、アイテムを待ち行列の未要求区画内にグループ化することのみに限定されるものではなく、その他のグループ化を含むことができ、また、待ち行列の要求済み区画、待ち行列の未要求区画、又はこれら双方は、いつでもエンプティになり得る。
【００５３】
本発明の一実施形態に従って、待ち行列がジッターキュー又はレイテンシキューであるとき、競合アイテム及び非競合アイテムは、それぞれ、まとめて待ち行列の相異なる区画にグループ分けされることが可能である。例えば、処理は、図８に例示されるように、帯域幅要求が基地局に対して為されたかが決定される操作805を含んでいる。帯域幅要求が基地局に対して為されたと決定されると、処理は、基地局に対して帯域幅割当て要求が為された競合アイテムが待ち行列の要求済み区画の競合区画内にグループ化される操作810と、基地局に対して帯域幅割当て要求が為された非競合アイテムが待ち行列の要求済み区画の非競合区画内にグループ化される操作820とに進む。
【００５４】
逆に、基地局に対して帯域幅要求が為されていないと決定されると、処理は、基地局に対して帯域幅割当て要求が未だ為されていない競合アイテムが待ち行列の未要求区画の競合区画内にグループ化される操作830と、基地局に対して帯域幅割当て要求が未だ為されていない非競合アイテムが待ち行列の未要求区画の非競合区画内にグループ化される操作840とに進む。本発明の実施形態は、例えば、待ち行列の２つの区画の一方にアイテムをグループ化することのみに限定されるものではなく、更に細分化された区画内にアイテムを格納することを含み得る。
【００５５】
操作805、810、820、830及び840は、例えば、スケジューラ105のようなスケジューラによって実行される。しかしながら、本発明は、図８の具体的な操作がスケジューラによって実行されることに限定されるものではない。
【００５６】
時限サービスフローに付随する加入者局のスケジューラの入力待ち行列、すなわち、ジッター及びレイテンシキューの詳細は、２００６年１１月１３日出願の「WiMAXスケジューラのジッター及びレイテンシキューの競合部分及び非競合部分への分割（Division  of  Jitter  and  Latency  Queues  of  a  WIMAX  Scheduler  into  Contention  and  Non-contention  Parts）」という発明名称の米国仮出願６０／８６５４５４号に記載されている。なお、その内容は参照することにより、ここに取り込まれる。
【００５７】
本発明の実施形態によれば、帯域幅要求を発するためのアイテムの処理が容易になる。何故なら、要求済みアイテムと未要求アイテムとの分割により、スケジューラは割当てを必要とするアイテムの量を効率的に決定することができるからである。すなわち、“未要求”アイテムをまとめてグループ化しておくことにより、例えば、これらアイテムに関する帯域幅要求を発するためのアイテムの処理が容易になる。
【００５８】
本発明の一実施形態に従った装置及び処理の効果は、より高い優先度が“要求済み”アイテムに自動的に与えられ得るものの、規則的な待ち行列順序でアイテムを処理することが可能になることである。
【００５９】
本発明の実施形態は“帯域幅”が割り当てられることに関する。“帯域幅”の概念は既知である。例えば、“WiMAX”ネットワークと呼ばれることも多いIEEE802.16規格に基づく無線ネットワークにおいては、帯域幅はアイテムが加入者局により送信され得るWiMAXフレーム内の空間である。
【００６０】
本発明の実施形態は、IEEE802.16規格に基づく無線ネットワークに適用可能である。しかしながら、本発明はそのようなネットワークに限定されるものではなく、むしろ、数多くのその他の種類のネットワークにも適用可能なものである。さらに、本発明は移動ネットワーク若しくは固定ネットワーク、又は移動局若しくは固定局に限定されるものではない。
【００６１】
上述のように、本発明の実施形態は、“帯域幅”割当てに従った送信のためのアイテムのスケジューリングに限定されるものではない。むしろ、本発明の様々な実施形態においては、アイテムは送信のための基地局による帯域幅割当て以外の別のサービスの割当てに従って、送信のためにスケジューリングされてもよい。故に、ここで説明された基地局によって帯域幅が割り当てられることに関する様々な実施形態は、帯域幅以外の異なるサービスが基地局によって割り当てられる状況にも適用可能である。
【００６２】
本発明について幾つかの好適な実施形態を用いて説明してきた。しかしながら、当業者に認識されるように、これらの実施形態は、本発明の原理及び意図を逸脱することなく変更され得るものである。本発明の範囲は添付の特許請求の範囲により定められる。
【００６３】
（付記１）無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングするスケジューラ；及び
前記加入者局によって送信されるべきアイテムが格納される待ち行列であり、前記基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、前記基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する待ち行列；
を有する装置であって：
前記スケジューラは、前記待ち行列の第２区画内のアイテムを送信のためにスケジューリングする前に、前記待ち行列の第１区画内のアイテムを前記加入者局による送信のためにスケジューリングする、装置。
【００６４】
（付記２）前記待ち行列の第２区画内のアイテムは、当該待ち行列の第２区画内のアイテムに関する帯域幅割当て要求が前記基地局に対して為されたとき、前記待ち行列の第１区画に動的に移動される、付記１に記載の装置。
【００６５】
（付記３）前記待ち行列の第１区画、前記待ち行列の第２区画、又は前記待ち行列の第１区画と前記待ち行列の第２区画との双方、の何れかはいつでもエンプティになり得る、付記１に記載の装置。
【００６６】
（付記４）当該装置は加入者局によって送信されるべきアイテムが格納される複数の待ち行列を有し、所定クラスのサービスフローのアイテムは自動的に、前記複数の待ち行列のうちの同一の待ち行列に格納される、付記１に記載の装置。
【００６７】
（付記５）無線ネットワーク内の加入者局によって送信されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられた帯域幅に従ってスケジューリングする手段；及び
前記加入者局によって送信されるべきアイテムが格納される待ち行列であり、前記基地局に対して帯域幅割当て要求が為されたアイテムが格納される第１区画と、前記基地局に対して帯域幅割当て要求が未だ為されていないアイテムが格納される第２区画とを有する待ち行列；
を有する装置であって：
前記スケジューリングする手段は、前記待ち行列の第２区画内のアイテムを送信のためにスケジューリングする前に、前記待ち行列の第１区画内のアイテムを前記加入者局による送信のためにスケジューリングする、装置。
【００６８】
（付記６）前記待ち行列の第２区画内のアイテムは、当該待ち行列の第２区画内のアイテムに関する帯域幅割当て要求が前記基地局に対して為されたとき、前記待ち行列の第１区画に動的に移動される、付記５に記載の装置。
【００６９】
（付記７）前記加入者局によって送信されるべきアイテムは、ユーザデータパケット又は管理メッセージである、付記５に記載の装置。
【００７０】
（付記８）無線ネットワーク内の加入者局によって送信されるべきアイテムを、基地局からの帯域幅の割当てに従ってスケジューリングするスケジューラ；及び
前記加入者局によって送信されるべきアイテムが格納される待ち行列であり、帯域幅の割当てが為されたアイテムが格納される、当該待ち行列の先頭に位置する第１区画と、帯域幅の割当てが未だ為されていないアイテムが格納される第２区画とを有する待ち行列；
を有する装置。
【００７１】
（付記９）送信されるべくスケジューリングされる前に帯域幅が割当てられる必要がないアイテムは、前記待ち行列の第１区画に格納される、付記８に記載の装置。
【００７２】
（付記１０）前記待ち行列の第１区画、前記待ち行列の第２区画、又は前記待ち行列の第１区画と前記待ち行列の第２区画との双方、の何れかは、いつでもエンプティになり得る、付記８に記載の装置。
【００７３】
（付記１１）無線ネットワーク内の加入者局のスケジューラの待ち行列の第１区画に、基地局に対して帯域幅割当て要求が為されたアイテムを格納する段階；
前記待ち行列の第２区画に、前記基地局に対して帯域幅割当て要求が未だ為されていないアイテムを格納する段階；及び
前記待ち行列内のアイテムを、前記基地局に対して為された帯域幅割当て要求に応じて前記基地局により該アイテムに割り当てられた帯域幅に従って加入者局によって送信されるようにスケジューリングする段階；
を有する方法であって：
前記待ち行列の第１区画内のアイテムは、前記待ち行列の第２区画内のアイテムが前記加入者局によって送信されるべくスケジューリングされる前に、前記加入者局によって送信されるべくスケジュールされる、方法。
【００７４】
（付記１２）前記待ち行列の第２区画内のアイテムを、該待ち行列の第２区画内のアイテムに関する帯域幅割当て要求が前記基地局に対して為されたとき、前記待ち行列の第１区画に動的に移動させる段階、を更に有する付記１１に記載の方法。
【００７５】
（付記１３）アンソリシッティド・グラント・サービス（ＵＧＳ）フローに属するアイテムは直ちに前記待ち行列の第１区画に格納される、付記１１に記載の方法。
【００７６】
（付記１４）前記待ち行列の第１区画、前記待ち行列の第２区画、又は前記待ち行列の第１区画と前記待ち行列の第２区画との双方、の何れかはいつでもエンプティになり得る、付記１１に記載の方法。
【００７７】
（付記１５）前記待ち行列がジッターキュー又はレイテンシキューである付記１１に記載の方法であって：
前記基地局に対して帯域幅割当て要求が為された競合アイテムを前記待ち行列の第１区画の競合区画に格納する段階；
前記基地局に対して帯域幅割当て要求が為された非競合アイテムを前記待ち行列の第１区画の非競合区画に格納する段階；
前記基地局に対して帯域幅割当て要求が未だ為されていない競合アイテムを前記待ち行列の第２区画の競合区画に格納する段階；及び
前記基地局に対して帯域幅割当て要求が未だ為されていない非競合アイテムを前記待ち行列の第２区画の非競合区画に格納する段階；
を更に有する方法。
【００７８】
（付記１６）無線ネットワーク内の加入者局によって処理されるべきアイテムを、該ネットワーク内の基地局によって該アイテムに割り当てられたサービスに従ってスケジューリングする段階；
前記基地局によるサービスの割当てが未だ要求されていないアイテムをまとめて、待ち行列の未要求区画内にグループ化する段階；及び
前記待ち行列の未要求区画内のアイテムを処理する前に、前記待ち行列の要求済み区画内の如何なるアイテムをも処理する段階；
を有する方法。
【００７９】
（付記１７）前記サービスは前記基地局によるアイテムへの帯域幅の割当てである、付記１６に記載の方法。
【００８０】
（付記１８）前記待ち行列の要求済み区画、前記待ち行列の未要求区画、又は前記待ち行列の要求済み区画と前記待ち行列の未要求区画との双方、の何れかはいつでもエンプティになり得る、付記１６に記載の方法。
【００８１】
（付記１９）前記待ち行列はジッターキュー又はレイテンシキューであり、当該方法は更に、競合アイテムをまとめてグループ化する段階、及び非競合アイテムをまとめてグループ化する段階を有する、付記１６に記載の方法。
【００８２】
（付記２０）前記競合アイテムをまとめてグループ化する段階、及び前記非競合アイテムをまとめてグループ化する段階は更に：
前記基地局に対して帯域幅割当て要求が為された競合アイテムを前記待ち行列の要求済み区画の競合区画内にグループ化する段階；
前記基地局に対して帯域幅割当て要求が為された非競合アイテムを前記待ち行列の要求済み区画の非競合区画内にグループ化する段階；
前記基地局に対して帯域幅割当て要求が未だ為されていない競合アイテムを前記待ち行列の未要求区画の競合区画内にグループ化する段階；及び
前記基地局に対して帯域幅割当て要求が未だ為されていない非競合アイテムを前記待ち行列の未要求区画の非競合区画内にグループ化する段階；
を有する、付記１９に記載の方法。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態に従った装置を例示する図である。
【図２】加入者局により送信されるアイテムが格納される、本発明の一実施形態に従った待ち行列を例示する図である。
【図３】加入者局のスケジューラの待ち行列の第１区画にアイテムを格納することを含む、本発明の一実施形態に従った処理を例示するフローチャートである。
【図４】待ち行列の第２区画内のアイテムを待ち行列の第１区画に動的に移動させることを含む、本発明の一実施形態に従った処理を例示するフローチャートである。
【図５】本発明の一実施形態に従ったジッターキュー又はレイテンシキューを例示する図である。
【図６】基地局に対して帯域幅割当て要求が為された競合アイテムを待ち行列の第１区画の競合区画に格納することを含む、本発明の一実施形態に従った処理を例示するフローチャートである。
【図７】加入者局により送信される待ち行列内のアイテムを、基地局に対して為された帯域幅割当て要求に応じて基地局により該アイテムに割り当てられた帯域幅に従ってスケジューリングすることを含む、本発明の一実施形態に従った処理を例示するフローチャートである。
【図８】基地局に対して帯域幅割当て要求が為された競合アイテムを待ち行列の第１区画の競合区画に格納することを含む、本発明の一実施形態に従った処理を例示するフローチャートである。
【符号の説明】
【００８４】
100  …  加入者局
105  …  スケジューラ
150  …  基地局
161  …  割当て要求
162  …  割当て
170  …  無線ネットワーク
110、500  …  待ち行列
120、501  …  第１区画（要求済み区画）
130、502  …  第２区画（未要求区画）
510  …  第１区画の競合区画
520  …  第１区画の非競合区画
530  …  第２区画の競合区画
540  …  第２区画の非競合区画
210、541  …  待ち行列の先頭
230、542  …  待ち行列の末尾
121−122、131−134  …  アイテム
551−552、557−559  …  競合アイテム
553−556、560−562  …  非競合アイテム
【図１】
2008125071.tif 000003
【図２】
2008125071.tif 000004
【図３】
2008125071.tif 000005
【図４】
2008125071.tif 000006
【図５】
2008125071.tif 000007
【図６】
2008125071.tif 000008
【図７】
2008125071.tif 000009
【図８】
2008125071.tif 000010