(57)【特許請求の範囲】
【請求項１】
複数のキューから一つのキューを選択するキュー選択方法において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成工程と、
当該複数の第一のグループのうちの一つを選択する第一の選択工程と、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択工程と、
前記複数の第一のグループそれぞれに含まれるキューのパケット数を管理し、前記パケット数に応じて前記複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程とを備え、
パケットが存在しない第一のグループは選択されないことを特徴とするキュー選択方法。
【請求項２】
複数のキューから一つのキューを選択するキュー選択方法において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成工程と、
前記第一のグループをさらにグループ化し、複数の第二のグループを形成する第二の形成工程と、
当該複数の第一のグループのうちの一つを選択する第一の選択工程と、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択工程と、
当該第二のグループのうちの一つを選択する第三の選択工程とを備え、
前記複数の第二のグループそれぞれに属するキューのパケット数を管理し、特定の第二のグループを選択することにより、当該特定の第二のグループに属するキューのパケット数を減算更新し、当該特定の第二のグループに属する複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程とを備え、
前記複数の第一のグループは、選択された第二のグループに属する複数の第一のグループであって、
パケットが存在しない第一のグループ又は第二のグループは選択されないことを特徴とするキュー選択方法。
【請求項３】
請求項１において、
第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程とは同時並行的に実行されることを特徴とするキュー選択方法。
【請求項４】
請求項２において、
第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程と、第三のキューを選択するための第三の選択工程は同時並行的に実行されることを特徴とするキュー選択方法。
【請求項５】
請求項１において、
前記管理工程は、前記特定の第一のグループに含まれる特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするキュー選択方法。
【請求項６】
請求項２において、
前記管理工程は、前記特定の第二のグループに属する特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を、当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするキュー選択方法。
【請求項７】
複数のキューから一つのキューを選択するスケジューリング装置において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成手段と、
当該複数の第一のグループのうちの一つを選択する第一の選択手段と、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択手段と、
前記複数の第一のグループそれぞれに含まれるキューのパケット数を管理し、前記パケット数に応じて前記複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理手段とを備え、
パケットが存在しない第一のグループは選択されないことを特徴とするスケジューリング装置。
【請求項８】
複数のキューから一つのキューを選択するスケジューリング装置において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成手段と、
前記第一のグループをさらにグループ化し、複数の第二のグループを形成する第二の形成手段と、
当該複数の第一のグループのうちの一つを選択する第一の選択手段と、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択手段と、
当該第二のグループのうちの一つを選択する第三の選択手段と、
前記複数の第二のグループそれぞれに属するキューのパケット数を管理し、特定の第二のグループを選択することにより、当該特定の第二のグループに属するキューのパケット数を減算更新し、当該特定の第二のグループに属する複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理手段とを備え、
前記複数の第一のグループは、選択された第二のグループに属する複数の第一のグループであって、
パケットが存在しない第一のグループ又は第二のグループは選択されないことを特徴とするスケジューリング装置。
【請求項９】
請求項７において、
前記管理手段は、前記特定の第一のグループに含まれる特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするスケジューリング装置。
【請求項１０】
請求項８において、
前記管理手段は、前記特定の第二のグループに属する特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を、当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするスケジューリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット伝送を行う通信におけるキュー選択を制御するキュー選択方法及びそれを実行するスケジューリング装置に関し、特に、大量のキューのスケジューリングを実現するキュー選択方法及びスケジューリング装置に関する。
【背景技術】
【０００２】
近年、インターネットの普及などにより、通信ネットワークに膨大なパケットデータが流れている。このトラフィック量の膨張に対応すべく、通信ネットワークを構成するルータなどの中継装置に対しては、さらなる高速化、大容量化が要求されている。
【０００３】
また、通信データの増大とともに、特定コンテンツへのトラフィック集中が発生するようになり、その際、無関係なトラフィックへの影響を排除し、パケットの流れをスムーズにするQOS(Quality of Service)などによるトラフィック制御が必須となっている。
【０００４】
パケットのキュー選択制御を実行するスケジューリング装置であるルータなどの中継装置は、QOSなど伝送するパケットの要求品質、帯域を保証しながら、パケット転送を行う。
【０００５】
図１は、従来のキュー選択制御を示す図である。入力されるパケットは、複数のキュー１０にバッファリングされ、キュー制御部２０が、所定の順序で各キュー１０からパケットを読み出し、出力する。
【０００６】
従来のキュー制御の構成において、例えば、数百（例えば、１９２）のキューが並列に設けられ、各キューが均等に選択されるようにプライマリエンコーダとリングカウンタ用いて、複数のキューの中から１つを選択するキュー制御が実現されている。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
近年、通信トラフィックの増加に伴い、キュー制御の高速化及び大容量化が求められている。しかしながら、キュー数を単に増加させると、それに応じて回路規模が大きくなるという問題がある。例えば、キュー数を現在の数百から数万に増加させる場合、プライマリエンコーダとにエントリさせるためのキュー内のパケット有無を示すレジスタだけでも、その回路規模が膨大となり、現実的でない。
【０００８】
そこで、本発明の目的は、回路規模を増大させることなく、大量のキューを選択制御できるキュー選択方法及びそれを実行するスケジューリング装置を提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するための本発明の第一のキュー選択方法は、複数のキューから一つのキューを選択するキュー選択方法において、複数のキューをグループ化し、複数の第一のグループを形成する第一の形成工程と、当該複数の第一のグループのうちの一つを選択する第一の選択工程と、当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択工程と、前記複数の第一のグループそれぞれに含まれるキューのパケット数を管理し、前記パケット数に応じて前記複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程とを備え、パケットが存在しない第一のグループは選択されないことを特徴とする。
【００１０】
本発明の第二のキュー選択方法は、複数のキューから一つのキューを選択するキュー選択方法において、複数のキューをグループ化し、複数の第一のグループを形成する第一の形成工程と、前記第一のグループをさらにグループ化し、複数の第二のグループを形成する第二の形成工程と、当該複数の第一のグループのうちの一つを選択する第一の選択工程と、当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択工程と、当該第二のグループのうちの一つを選択する第三の選択工程とを備え、
前記複数の第二のグループそれぞれに属するキューのパケット数を管理し、特定の第二のグループを選択することにより、当該特定の第二のグループに属するキューのパケット数を減算更新し、当該特定の第二のグループに属する複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程とを備え、前記複数の第一のグループは、選択された第二のグループに属する複数の第一のグループであって、パケットが存在しない第一のグループ又は第二のグループは選択されないことを特徴とする。
【００１１】
本発明の第三のキュー選択方法は、上記第一のキュー選択方法において、第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程とは同時並行に実行されることを特徴とする。
【００１２】
本発明の第四のキュー選択方法は、上記第二のキュー選択方法において、第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程と、第三のキューを選択するための第三の選択工程は同時並行に実行されることを特徴とする。
【００１５】
本発明の第五のキュー選択方法は、上記第一のキュー選択方法において、前記管理工程は、前記特定の第一のグループに含まれる特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とする。
【００１６】
本発明の第六のキュー選択方法は、上記第二のキュー選択方法において、前記管理工程は、前記特定の第二のグループに属する特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を、当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とする。
【００１７】
さらに上記第一乃至第六のキュー選択方法のいずれか一つを実行するスケジューリング装置が提供される。
【発明の効果】
【００１８】
本発明によれば、各キューに蓄積されたパケットの有無を管理するレジスタを各キュー毎に設けることなく、キューの数よりもレジスタの数を大幅に削減することができ、キューの増大に対して、回路規模を抑えることができる。
【００１９】
パイプライン処理により、各段のグループ選択は同時並行的に行われるので、高速なキュー選択が可能となる。
【００２０】
各段の各グループにおいて、配下のキューに蓄積された合計パケット数を管理し、上位のグループのパケット数をフィードバックすることで、キューの選択が進行中での、上位グループにおけるキュー選択に誤りを防止することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照して本発明の実施の形態について説明する。しかしながら、かかる実施の形態例が、本発明の技術的範囲を限定するものではない。
【００２２】
本発明の実施の形態例では、キューをグループ化し、さらに、各グループを複数段のツリー構造とし、各段のグループを選択していくことで、キューを選択する方法を提供する。これにより、キュー数が膨大になっても、各段で選択されたグループの数だけパケットの有無を管理するためのレジスタを用意すればよく、キュー全てに対してレジスタを用意する必要がなくなるので、キュー数の増大に対して、レジスタの増大を抑えることができる。また、好ましくは、各段におけるグループ選択はパイプライン処理により独立して並行して行われ、高速動作を維持する。
【００２３】
図２は、本発明の実施の形態におけるスケジューリング装置のキュー選択方法の基本概念を説明する図である。従来のように、キューを１段並列で構成し、全キューの中から１つのキューを選択するのではなく、本発明では、図２に示すように、キューを複数段にツリー構造で構成し、各段の各グループを選択していくことで、キューが選択される。
【００２４】
図２に示すように、一例として、１９２のキューの選択を４段構成とする場合、最下位段の４段目において、１９２のキューを３個ごとにグループ化し、各グループ内において、例えば＃１、＃２、＃３というようにＩＤを付する。４段目の各グループは、上位の３段目で管理されるグループの配下に属し、３段目の各グループは、最下位段の４つのグループがグループ化され、例えば、＃１、＃２、＃３、＃４というようにＩＤが付される。３段目の各グループは、さらに上位の２段目で管理されるグループの配下に属し、２段目の各グループも、３段目の４つのグループが一つにグループ化され、例えば、＃１、＃２、＃３、＃４というようにＩＤが付される。そして、２段目の各グループは、最上位段である１段目で管理されるグループの配下に属し、１段目のグループも、２、３段目同様に、２段目の４つのグループが一つにグループ化され、例えば、＃１、＃２、＃３、＃４というようにＩＤ（番号）が付される。
【００２５】
そして、キュー選択時において、最上位段（１段目）から最下位段（４段目）に向かって、各段のグループのＩＤを選択していくことで、一つのキューを選択することができる。このとき、パケット有無フラグ（レジスタ）は、各段の各グループに含まれるサブグループ数分だけ用意すれば足り、図２の例では、１５（３＋４＋４＋４）個のレジスタで１９２のキューのパケット有無を識別することができるようになる。すなわち、各段で選択されたグループの数だけレジスタを用意すればよく、すべてのキューに対してレジスタを用意する必要がなくなるので、キューの数に対して、レジスタの数を大幅に削減することができ、キューの数が膨大になっても、レジスタの数の増大を抑えることができる。
【００２６】
また、上述のように、複数段によるキュー選択を行う場合、一サイクル（クロック）ごとに各段のグループが選択されるので、１つのキュー選択に、その段数分のサイクル（クロック）数が必要となる。そこで、本実施の形態例では、各段における選択動作を独立させ、段数分の並行動作を行うパイプライン処理を実施することで、１サイクル毎に１つのキュー選択を可能とする。
【００２７】
図３は、本発明の実施の形態におけるキュー選択の並行動作を説明する図である。図３（ａ）は、各処理のタイムチャートであり、図３（ｂ）は、各処理で選択されたグループを示す図である。図３（ｂ）において、斜線、網掛けのないグループは、配下のキューにパケットがないグループであり、パケット有無フラグにより、パケット無しと識別されているものとする。また、各段のグループ選択については、＃１から順番に（図では右方向に）、配下のキューにパケットがあるグループが選択されていくものとする。図３（ｂ）を参照しながら、図３（ａ）を説明する。
【００２８】
まず、最初のサイクルで実施される１−１処理では、１個目のキュー選択の１段目のＩＤ選択（例えば＃１）が行われる。
【００２９】
次のサイクルでは、１個目のキュー選択の２段目のグループ選択（例えば＃１）を行う１−２処理と、２個目のキュー選択の１段目のグループ選択（例えば＃２）を行う２−１処理が実施される。
【００３０】
その次のサイクルでは、１個目のキュー選択の３段目のグループ選択（例えば＃１）を行う１−３処理と、２個目のキュー選択の２段目のグループ（例えば、＃ｎ）選択を行う２−２処理と、３個目のキュー選択の１段目のグループ選択（例えば＃４）を行う３−１処理が実施される。
【００３１】
さらに次のサイクル（太枠表示）では、１個目のキュー選択の４段目のグループ選択（例えば＃１）を行う１−４処理と、２個目のキュー選択の３段目のグループ選択（例えば＃３）を行う２−３処理と、３個目のキュー選択の２段目のグループ選択（例えば＃ｎ）を行う３−２処理と、４個目のキュー選択の１段目のグループ選択（例えば＃ｎ−ｍ）を行う４−１処理が実施される。この段階で、１個目のキュー選択が完了する。なお、このサイクルで選択される各ＩＤは、図２（ｂ）においても、太枠表示されている。
【００３２】
そして、さらに続く次のサイクルでは、２個目のキュー選択の４段目のグループ選択を行う２−４処理と、３個目のキュー選択の３段目のグループ選択を行う３−３処理と、４個目のキュー選択の２段目のグループ選択を行う４−２処理と、５個目のキュー選択の１段目のグループ選択を行う５−１処理が実施される。この段階で、２個目のキュー選択が完了する。すなわち、１個目のキュー選択が完了したサイクルの次のサイクルで２個目のキュー選択が完了する。このように、各段におけるグループ選択処理を独立且つ並行に動作させることにより、１サイクル毎に１つのキュー選択が可能となる。
【００３３】
ところで、スケジューリングによるパケットのトラフィック制御では、各キュー毎の流量及び間隔を制御する必要があり、そのためには後続のキュー選択処理に対して、選択された結果（どのＩＤに対応するキューが選択されたかどうか、その結果、各キューにパケットが有るか無いか）をフィードバックしなければならない。パケットのないキューを選択しないようにするためである。しかしながら、上述したパイプライン処理により、複数のキュー選択処理が並行して動作し、前のキュー選択が完了する前（最下位段にて１つのキューが選択される前）に、順次次のキュー選択処理も進行するので、選択結果がフィードバックされる前に、次のキュー選択処理が開始されるという状態が生じる。
【００３４】
そこで、本発明の実施の形態例では、最下位段以外の各段のフィードバックをパケット数のみで行う。すなわち、各段の各グループにおいて、配下のキューに蓄積されているパケット数の合計を管理する。グループ配下のどのキューが選択されるか確定していないが、いずれかのキューが選択されることは判明しているので、各段のグループ単位でパケット数を管理することで、各グループの配下のキューにパケットが有るか無いかを判定することができる。この情報を中間段階でフィードバックすることで、最終的なキューの選択が行われる前に、パケットの有無のフィードバックが可能となる。以下、本発明の実施の形態例における具体例について説明する。
【００３５】
図４は、本発明の実施の形態におけるキュー選択処理の具体例を説明するための図である。図４では、４キュー３段スケジューリング構成によるキュー選択処理について説明する。すなわち、キューは各段毎に４つずつにグループ化され、計６４個のキューを識別する場合である。また、最上段（１段目）のグループをＧ１、２段目グループをＧ２、最下位段（３段目）グループをＧ３と称する。
【００３６】
最上段Ｇ１は、各グループ毎にパケット有無フラグを有し、さらに、前回選択されたグループＩＤ情報（前回選択ＩＤ）を有する。図４の例では、グループＩＤ＃１と＃４配下にパケットが存在し、前回選択されたグループは、＃４（太枠）であることが例示されている。本例のキュー選択では、パケット有無フラグに基づいて、パケットが存在するグループが順番に選択される。
【００３７】
図５は、グループＩＤの選択順序の例を示す例である。図５に示すように、グループＩＤ＃１から＃２、＃３の順に選択され、前回選択ＩＤが＃３であり、グループＩＤ＃４にパケットが存在しない場合は、＃１に戻って＃１が選択される。グループＩＤ＃４にパケットが存在すれば、もちろん＃４が選択される。このように、前回選択ＩＤを設け、次回は、前回選択されたＩＤの次のＩＤを選択するようにすることで、各グループ、すなわち、その配下のキューを順番に均等に読み出すことができる。
【００３８】
図４に戻って、２段目Ｇ２は、最上段Ｇ１同様に、各グループＩＤ毎にパケット有無フラグを有し、さらに、前回選択されたグループＩＤ情報（前回選択ＩＤ）を有することに加えて、配下のキューに蓄積されているパケット数情報（カウンタ）を有する。図４の例では、Ｇ１＃１配下のグループＧ１−１−Ｇ２と、Ｇ１＃４配下のグループＧ１−４−Ｇ２が例示されている。Ｇ１−１−Ｇ２は、グループＩＤ＃１と＃３配下にパケットが存在し、前回選択ＩＤは、＃３（太枠）である。さらに、配下のグループＧ１−１−Ｇ２−１−Ｇ３に２個のパケットが存在することから、カウンタ値＝２である。また、Ｇ１−４−Ｇ２は、グループＩＤ＃１配下にパケットが存在し、前回選択ＩＤは、＃４（太枠）である。さらに、配下のグループＧ１−１−Ｇ２−４−Ｇ３に１個のパケットが存在することから、カウンタ値＝１である。
【００３９】
最下位段Ｇ３は、２段目Ｇ２同様に、各グループＩＤ毎のパケット有無フラグ、前回選択されたグループＩＤ情報（前回選択ＩＤ）、パケット数情報（カウンタ）を有する。図４の例では、Ｇ２＃１配下のグループＧ１−２−Ｇ２−１−Ｇ３は、グループＩＤ＃３にパケットが存在し、前回選択ＩＤは、＃２（太枠）である。このグループ内には、パケットが１個だけなので、カウンタ値＝１である。なお、Ｇ３の別のグループ（Ｇ２＃３配下のグループ）Ｇ１−２−Ｇ２−３−Ｇ３内にも、パケットが１個存在する。
【００４０】
このような状態における今回サイクルのキュー選択処理を説明する。
【００４１】
＜１サイクル目＞
（１−１）１個目のキューに対するキュー選択処理として、最上段Ｇ１からグループＩＤ＃１（Ｇ１−１）を選択する（前回選択ＩＤが＃４のため）。
【００４２】
（１−２）（１−１）の選択により、Ｇ１−１−Ｇ２のカウンタ値を１減算する（カウンタ値＝２→１）。上述したように、次回サイクルで次のキュー選択処理が始まるので、カウンタ値の減算は１サイクル目期間内に行われる。
【００４３】
（１−３）（１−２）のカウンタ値減算により、カウンタ値＝０とならないため、Ｇ１−１のパケット有無フラグは、「パケット有り」を維持する。Ｇ１＃１配下のいずれかのキューが次サイクル以降で選択されても、まだ配下にパケットが残っているためである。パケット有無フラグの更新も１サイクル目期間内に行われる。
【００４４】
（１−４）前回選択ＩＤが＃１に更新される。これも、１サイクル目期間内に行われる。
【００４５】
＜２サイクル目＞
つづいて、今回サイクルに続く２サイクル目サイクルのキュー選択処理を説明する。
【００４６】
（１−５）１個目のキューに対するキュー選択処理として、２段目Ｇ１−１−Ｇ２からグループＩＤ＃１（Ｇ２−１）を選択する（Ｇ２の前回選択ＩＤが＃３であり、次のＩＤ＃４はパケットが存在せず、選択順序に沿って次にパケットが存在するグループＩＤが＃１のため）。
【００４７】
（１−６）（１−５）の選択により、Ｇ１−１−Ｇ２−１−Ｇ３のカウンタ値を１減算する（カウンタ値＝１→０）。
【００４８】
（１−７）（１−６）のカウンタ値減算により、カウンタ値＝０となるため、Ｇ１−１−Ｇ２−３のパケット有無フラグは、「パケット無し」に更新する。
【００４９】
（２−１）上記（１−５）乃至（１−７）の処理と並行して、２個目のキューに対するキュー選択処理として、最上段Ｇ１からグループＩＤ＃４（Ｇ１−４）を選択する。前回選択ＩＤが＃１に更新されており、グループＩＤ＃２、＃３配下にはパケットが存在しないためである。各グループ配下にパケットが存在するか否かは、パケット有無フラグで確認可能であり、この場合、グループＩＤ＃２、＃３のパケット有無フラグは、「パケット無し」の状態である。
【００５０】
（２−２）（２−１）の選択により、Ｇ１−４−Ｇ２のカウンタ値を１減算する（カウンタ値＝１→０）。
【００５１】
（２−３）（２−２）のカウンタ値減算により、カウンタ値＝０となるため、Ｇ１−４のパケット有無フラグは、「パケット無し」に更新する。
【００５２】
（２−４）前回選択ＩＤが＃４に更新される。
【００５３】
＜３サイクル目＞
（１−８）１個目のキューに対するキュー選択処理として、最下位段Ｇ１−１−Ｇ２−１−Ｇ３からグループＩＤ＃１（Ｇ３−３）を選択する（Ｇ３の前回選択ＩＤが＃２のため）。
【００５４】
（１−９）前回選択ＩＤが＃３に更新される。
【００５５】
（２−５）上記（１−８）、（１−９）の処理と並行して、２個目のキューに対するキュー選択処理として、２段目Ｇ１−４−Ｇ２からグループＩＤ＃１を選択する（前回選択ＩＤが＃４のため）。
【００５６】
（２−６）（２−５）の選択により、Ｇ１−４−Ｇ２−１−Ｇ３のカウンタ値を１減算する（カウンタ値＝１→０）。
【００５７】
（２−７）（２−６）のカウンタ値減算により、カウンタ値＝０となるため、Ｇ１−４−Ｇ２−１のパケット有無フラグは、「パケット無し」に更新する。
【００５８】
（３−１）上記（１−５）、（１−９）及び（２−５）乃至（２−７）の処理と並行して、３個目のキューに対するキュー選択処理として、最上段Ｇ１からグループＩＤ＃１（Ｇ１−１）を選択する（前回選択ＩＤが＃４に更新されているため）。
【００５９】
（３−２）（３−１）の選択により、Ｇ１−１−Ｇ２のカウンタ値を１減算する（カウンタ値＝１→０）。
【００６０】
（３−３）（３−２）のカウンタ値減算により、カウンタ値＝０となるため、Ｇ１−１のパケット有無フラグは、「パケット無し」に更新する。
【００６１】
（３−４）前回選択ＩＤが＃１に更新される。
【００６２】
以下、パケットが存在するキューがある限り、上述の処理が繰り返される。
【００６３】
上述したように、キューの選択は、パケット有無フラグの状態に従って、選択順序に従って、次にパケットが存在するキューが選択されるが、最上段以外の各段のグループ毎に、配下のキューの合計パケット数カウンタを設けることで、配下のキューにパケットが蓄積されているかどうかを中間段階で認識でき、パケット有無フラグの制御が可能となる。パケット数が０になると、配下のキューには１パケットも蓄積されていないことになるので、パケット有無フラグは、「パケット無し」状態となり、次回のサイクルからは、該当する段のグループは選択されないようにする。
【００６４】
なお、キューには、随時パケットが入力されるが、キューにパケットが入力されると、パケット数は１加算される。
【００６５】
また、上述の例では、前回選択ＩＤを用いて、配下にパケットが存在するキューを均等に選択する処理について説明したが、この場合は、パケットが存在する各キューからの読み出し量（読み出し速度）は同一である。しかし、各キューに設定された読み出し速度は、すべて同一とは限らず、キューごとに流量制限（読み出し速度制限）が設定されている場合は、その制限を超えないように、キュー選択制御を行う必要がある。
【００６６】
流量（読み出し速度）管理を実施する方法として、例えば、流量制限に達したキューに対応する最下位段のグループのカウンタ値を一時的にゼロにする。すなわち、キューに現在蓄積されているパケット数を現在のカウンタ値から減算する。これに応じて、当該グループが属する上位の各グループのカウンタ値も同数減算される。各段のグループ間のカウンタ値の整合性を保つためである。この場合、上記のグループのカウンタ値は、配下の他のキューのパケット数の合計をカウンタ値として持っているため、他のキューにパケットが蓄積されていれば、上位のグループのカウンタ値がゼロになるとは限らない。
【００６７】
制限を超えたキューに対応する最下位段のグループのカウンタ値がゼロなると、当該グループのパケット有無フラグは「パケット無し」状態となり、前回選択ＩＤを用いた順次選択において、当該グループは選択されなくなる。これにより、キューに設定された流量制限を超えたパケット読み出しが行われなくなり、キューに設定された流量制限が守られる。
【００６８】
例えば、流量制限が所定時間（例えば１秒）単位で設定されている場合に、所定時間単位で流量監視が行われ、所定時間経過中に、上述のように流量が制限されると、次の所定時間開始時に、流量制限が解除される。
【００６９】
すなわち、流量制限されていたキューに蓄積されている現在（読み出し開始時）のパケット数がカウンタ値に加算され、同時に、当該キューを収容する上位のグループのカウンタ値も同様に加算される。流量制限されていたキューのカウンタ値がゼロでなくなり、パケット有無フラグは「パケット有り」状態となる。これにより、当該キューの選択が可能となり、流量制限がかけられていない通常状態に戻る。
【００７０】
（付記１）
複数のキューから一つのキューを選択するキュー選択方法において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成工程と、
当該複数の第一のグループのうちの一つを選択する第一の選択工程と、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択工程とを備えることを特徴とするキュー選択方法。
【００７１】
（付記２）
付記１において、
前記第一のグループをさらにグループ化し、複数の第二のグループを形成する第二の形成工程と、
当該第二のグループのうちの一つを選択する第三の選択工程とを備え、
前記複数の第一のグループは、選択された第二のグループに属する複数の第一のグループであることを特徴とするキュー選択方法。
【００７２】
（付記３）
付記１において、
第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程とは同時並行的に実行されることを特徴とするキュー選択方法。
【００７３】
（付記４）
付記２において、
第一のキューを選択するための第二の選択工程と、第二のキューを選択するための第一の選択工程と、第三のキューを選択するための第三の選択工程は同時並行的に実行されることを特徴とするキュー選択方法。
【００７４】
（付記５）
付記１において、
前記複数の第一のグループそれぞれに含まれるキューのパケット数を管理し、特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程を備え、
パケットが存在しない第一のグループは選択されないことを特徴とするキュー選択方法。
【００７５】
（付記６）
（付記２）において、
前記複数の第二のグループそれぞれに属するキューのパケット数を管理し、特定の第二のグループを選択することにより、当該特定の第二のグループに属するキューのパケット数を減算更新し、
当該特定の第二のグループに属する複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理工程を備え、
パケットが存在しない第一のグループ又は第二のグループは選択されないことを特徴とするキュー選択方法。
【００７６】
（付記７）
付記５において、
前記管理工程は、前記特定の第一のグループに含まれる特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするキュー選択方法。
【００７７】
（付記８）
付記６において、
前記管理工程は、前記特定の第二のグループに属する特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を、当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数からを減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするキュー選択方法。
【００７８】
（付記９）
複数のキューから一つのキューを選択するスケジューリング装置において、
複数のキューをグループ化し、複数の第一のグループを形成する第一の形成手段と、
当該複数の第一のグループのうちの一つを選択する第一の選択手段とと、
当該選択された第一のグループに含まれる複数のキューのうちの一つを選択する第二の選択手段とを備えることを特徴とするスケジューリング装置。
【００７９】
（付記１０）
付記９において、
前記第一のグループをさらにグループ化し、複数の第二のグループを形成する第二の形成手段と、
当該第二のグループのうちの一つを選択する第三の選択手段とを備え、
前記複数の第一のグループは、選択された第二のグループに属する複数の第一のグループであることを特徴とするスケジューリング装置。
【００８０】
（付記１１）
付記９において、
第一のキューを選択するための前記第二の手段の処理と、第二のキューを選択するための前記第一の選択手段の処理とは同時並行的に実行されることを特徴とするスケジューリング装置。
【００８１】
（付記１２）
付記１０において、
第一のキューを選択するための前記第二の選択手段の処理と、第二のキューを選択するための前記第一の手段手段の処理と、第三のキューを選択するための前記第三の選択手段の処理とは同時並行的に実行されることを特徴とするスケジューリング装置。
【００８２】
（付記１３）
付記９において、
前記複数の第一のグループそれぞれに含まれるキューのパケット数を管理し、特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理手段を備え、
パケットが存在しない第一のグループは選択されないことを特徴とするスケジューリング装置。
【００８３】
（付記１４）
付記１０において、
前記複数の第二のグループそれぞれに属するキューのパケット数を管理し、特定の第二のグループを選択することにより、当該特定の第二のグループに属するキューのパケット数を減算更新し、
当該特定の第二のグループに属する複数の第一のグループから特定の第一のグループを選択することにより、当該特定の第一のグループに含まれるキューのパケット数を減算更新する管理手段を備え、
パケットが存在しない第一のグループ又は第二のグループは選択されないことを特徴とするスケジューリング装置。
【００８４】
（付記１５）
付記１３において、
前記管理手段は、前記特定の第一のグループに含まれる特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を当該特定の第一のグループに含まれるキューのパケット数から減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするスケジューリング装置。
【００８５】
（付記１６）
付記１４において、
前記管理手段は、前記特定の第二のグループに属する特定のキューからのパケット読み出しが設定速度を超えた場合、当該特定のキューのパケット数分を、当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数からを減算し、これにより、当該特定のキューにパケットが存在しないと判定され、当該特定のキューが選択されずに、当該特定のキューからのパケット読み出しが停止し、
読み出し再開時に、当該特定のキューに存在するパケット数を当該特定の第二のグループに属するキューのパケット数及び当該特定の第一のグループに含まれるキューのパケット数に加算し、これにより、当該特定のキューにパケットが存在すると判定され、当該特定のキューが選択可能となることを特徴とするスケジューリング装置。
【図面の簡単な説明】
【００８６】
【図１】従来のキュー選択制御を示す図である。
【図２】本発明の実施の形態におけるスケジューリング装置のキュー選択方法の基本概念を説明する図である。
【図３】本発明の実施の形態におけるキュー選択の並行動作を説明する図である。
【図４】本発明の実施の形態におけるキュー選択処理の具体例を説明するための図である。
【図５】キューＩＤの選択順序の例を示す例である。
【符号の説明】
【００８７】
１０：キュー、２０：キュー制御部
【図１】
0004440196.tif 000002
【図２】
0004440196.tif 000003
【図３】
0004440196.tif 000004
【図４】
0004440196.tif 000005
【図５】
0004440196.tif 000006