(57)【特許請求の範囲】
【請求項１】
それぞれ予約した帯域が保証されている複数の帯域保証キューと、それぞれ予め優先順序が設定されていて優先制御の対象となる複数の優先キューを有する優先キュークラスの各キューにそれぞれ格納されているパケットのうち最先に出力すべきパケットを選定するパケットスケジューリング方法であって、
各前記帯域保証キューに付与された重みと、前記優先キュークラス全体に付与された重みとを記憶し、
記憶した前記重みを参照し、前記帯域保証キューについてはバックログ状態のキューがあるときはそのキューの重みを、前記優先キュークラスについてはバックログ状態の前記優先キューがあるときは該優先キュークラスの重みを合計して合計値を計算し、
少なくとも、前記重みと、前記合計値と、前記優先順序の高いパケットであって前記優先キュークラスに最初に到着したパケットの最小到着時刻と、をパラメータとして、バックログ状態の各前記キューについてサービス時刻を計算し、
各前記サービス時刻相互間の大小比較により最小のサービス時刻を有する１のパケットを、前記の最先に出力すべきパケットとして、選定する、
ことを特徴とするパケットスケジューリング方法。
【請求項２】
前記サービス時刻の計算を、実時刻に代えて、仮想時刻を用いて行う請求項１に記載の方法。
【請求項３】
前記優先順序に従い選択されなかった前記優先キューについては、前記サービス時刻の計算の対象から除外する請求項１に記載の方法。
【請求項４】
それぞれ予約した帯域が保証されている複数の帯域保証キューと、それぞれ予め優先順序が設定されていて優先制御の対象となる優先キュークラスをなす複数の優先キューと、にそれぞれ格納されているパケットのうち最先に出力すべきパケットを選定するパケットスケジューリング装置であって、
入力された複数の所定のパラメータに基づき、バックログ状態の各前記帯域保証キューと、バックログ状態にあり、かつ、最も高い前記優先順序を有する前記優先キューとについて、それぞれのサービス時刻を計算するサービス時刻計算部と、
計算された各前記サービス時刻相互の大小比較をして、最小のサービス時刻を有するパケットを、前記の最先に出力すべきパケットとして、選定するサービス時刻比較部と、
前記帯域保証と、前記優先制御とを両立させるように計算された前記パラメータを生成するパラメータ生成部と、からなることを特徴とするパケットスケジューリング装置。
【請求項５】
前記パラメータ生成部は、
各前記帯域保証キューに付与された重みと、前記優先キュークラス全体に付与された重みとを、前記所定のパラメータとして、記憶する重み記憶手段を有する請求項４に記載の装置。
【請求項６】
前記パラメータ生成部は、
バックログ状態にある前記帯域保証キューおよび前記優先キューと、前記優先順序と、に関する各情報をもとに、１の優先キューを選択する優先キュー選択手段を有する請求項５に記載の装置。
【請求項７】
前記パラメータ生成部は、
前記優先キュー選択手段により選択された前記１の優先キューおよびバックログ状態にある前記帯域保証キューと、前記重み記憶手段から提供される当該バックログ状態にある前記キューについての各前記重みと、に関する各情報を入力として、各該キューの重みを合計してその合計値を計算する重み合計値計算手段を有する請求項６に記載の装置。
【請求項８】
前記パラメータ生成部は、
前記優先キュークラスに最初に到着したパケットの最小到着時刻を記憶する最小到着時刻記憶手段を有する請求項７に記載の装置。
【請求項９】
前記パラメータ生成部は、
前記サービス時刻計算部にて計算された前記サービス時刻に関連する計算時刻を、各前記パケット毎のサービス状況に応じて記憶し、かつ、該計算時刻を、次のパケットに対する計算のために該サービス時刻計算部にフィードバックするサービス時刻記憶手段を有する請求項８に記載の装置。
【請求項１０】
前記重み合計値計算手段は、
前記帯域保証キューについては、バックログ状態にある前記キューの前記重みを加算し、
前記複数の優先キューについては、いずれか１つがバックログ状態にあれば、前記優先キュークラスの前記重みを加算して前記合計値を計算する請求項７に記載の装置。
【請求項１１】
サービス時刻記憶手段は、
同一の前記キューから直前に出力されたパケットのサービス終了時刻を記憶し、
前記優先キュークラスの中で、最後に出力したパケットのサービス終了時刻を記憶する請求項９に記載の装置。
【請求項１２】
前記サービス時刻計算部は、
前記優先キュー選択手段により選択された前記優先キューについては、前記最小到着時刻と、サービス終了時刻と、前記優先キュークラスの重みによって、前記サービス時刻を計算する請求項８に記載の装置。
【請求項１３】
前記サービス時刻比較部は、前記優先キュー選択手段によって選択されなかった前記優先キューについては、前記の大小比較の対象から除外するために、前記サービス時刻として、該サービス時刻が通常取りうる最大値よりも大きい値を設定する請求項６に記載の装置。
【請求項１４】
前記優先キュー選択手段は、
各前記キューに前記パケットが格納されているか否かの情報を記憶するキュー状態記憶手段と、
各前記キューが前記優先キューか否かの情報を記憶する優先制御対象キュー記憶手段と、
前記優先順序に関する情報を記憶する優先順序記憶手段と、
前記の各情報をもとに、バックログ状態にある高優先のパケットを選択し、その選択情報を出力する請求項６に記載の装置。
【請求項１５】
各前記帯域保証キューに付与される前記重みの合計と、前記の最先に出力すべきパケットを送出する出力リンクの速度との差分により、前記優先キュークラス全体に付与される前記重みを設定する請求項５に記載の装置。
【請求項１６】
前記重み合計値計算手段からの出力をもとに仮想時刻を計算する仮想時刻計算手段をさらに設け、
前記最小到着時刻記憶手段は、計算された前記仮想時刻をもとに、前記優先キュークラスに最初に到着したパケットの到着時刻における該仮想時刻を記憶し、
前記サービス時刻計算部は、記憶した前記仮想時刻に基づいて、各前記帯域保証キューに対しおよび前記優先キュー選択手段により選択された前記優先キューに対し、それぞれ、前記サービス時刻を計算する請求項８に記載の装置。
【請求項１７】
入力された複数の所定のパラメータに基づき、各帯域保証キューと、高い優先順序を有する優先キューとについて、それぞれのサービス時刻を計算するサービス時刻計算部と、
計算された各サービス時刻相互の大小比較をして、最先に出力すべきパケットを選定するサービス時刻比較部と、
帯域保証と、優先制御とを両立させるように計算されたパラメータを生成するパラメータ生成部と、から構成される
ことを特徴とするパケットスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク内の中継装置に格納された複数のパケットを読み出す際の読出し順序を決定するためのパケットスケジューリング方法および装置に関する。
近年、ネットワークを利用するマルチメディアやリアルタイム・アプリケーション等の普及に伴い、そのネットワークが提供する通信品質（ＱｏＳ）の保証が求められている。このネットワーク内の、例えばルーターやスイッチ等の中継装置においては、トラヒックの種別に応じて、各パケットを複数のキューに分類し、それぞれのキューに要求された通信品質（ＱｏＳ）を保証しながら該パケットの転送制御を行うための手段が必要となる。この手段がパケットスケジューリング装置である。
【０００２】
【従来の技術】
上記のパケットスケジューリング、すなわち通信品質を保証した、パケット読出し順序、を決定するための要因にはいくつか考えられるが、特に効果的な決定要因として、〈１〉帯域保証と、〈２〉優先制御とが知られている。
ここに帯域保証とは、ユーザからの予約に基づき、当該トラヒックに対して許容すべき帯域、例えば１００Mbps、を保証することを意味する。
【０００３】
一方優先制御とは、帯域が予約されていないときに、いわゆるBest-effort の転送ではなく、ユーザからの指定に基づいて複数のトラヒックに対して、高優先のトラヒックから低優先のトラヒックまで各々に優先順序を付与しておき、転送すべきパケットが発生したときは、そのパケットが属するトラヒックの優先順序がより高いものから、パケットの読出しを行う、ことを意味する。
【０００４】
したがって、パケットスケジューリング装置においては、予約された帯域を保証しつつ、かつ、優先順序の高いトラヒックを優先順序の低いトラヒックに優先させて、パケットの読出しを行うことが必要である。
従来より、パケットスケジューリング方法として、パケットフェアキューイング（Packet Fair Queueing）が用いられてきた。このパケットフェアキューイングは、前述した各キュー毎に予約された帯域に基づいて、重み（weight）を設定する。そして、パケット転送に使われていない余剰帯域があればその余剰帯域を、各キュー毎の重みに従って公平に再配分して有効利用する。以下、このパケットフェアキューイングをもとにして詳しく説明する。
【０００５】
パケットフェアキューイングを実現する公知の方法は、文献１（A.K.Parekh and R.G.Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case", IEEE/ACM Trans. on Networking, vol.1, pp.344-357, June 1993 ）に記載されているＧＰＳ規則（Generalized Processor Sharing Discipline）と呼ばれる方法に準拠している。
【０００６】
このＧＰＳ規則は、パケットフェアキューイングの理想的な流体モデルとして知られている。この流体モデルでは、サービス対象を無限に分割することができ、したがってすべてのフロー（例えばファイル転送等のアプリケーションレベルでのフロー）を並行してサービスできることを仮定している。ところがパケットは分割することができないので、複数のパケットを同時にサービスすることができない。このため、実際のパケットスケジューリングにおいては、上記ＧＰＳ規則を近似する方法を用いている。なお、本発明においては、該ＧＰＳ規則を近似するパケットスケジューリング方法の総称として、パケットフェアキューイングの語を用いる。
【０００７】
パケットフェアキューイングの１つとして、ＷＦＱ（Weighted Fair Queueing）と呼ばれるパケットスケジューリング方法がよく知られている。これは、ＧＰＳ規則で規定する「サービス終了時刻」を計算して用いるものである。このＷＦＱについては、上記の文献１に詳しく記載されているが、ここで、これについて簡単に説明しておく。
【０００８】
各フローをなすパケットは、それぞれに対応するキューに格納される。これらのキューの１つ１つをキューｉ（ｉ＝１，２，３…）と表すと、キューｉには、キューｉについて予約した帯域に比例した重みφｉが設定されているものとする。また、バックログ状態のキューの重みの合計をφｂとする。ここでは、送信すべきパケットがキューに格納されているとき、そのキューは「バックログ状態」であると呼ぶ。もしくは「アクティブ」であると呼ぶ。
【０００９】
これらφｉとφｂを用いると、各キューの変数Ｆｉは、次式（１）のｒ ｉ（Ｑｉのパケットの再配分後の出力速度）によって、次式（２）のように計算される。Ｆｉ（ｆｉｎｉｓｈ ｉ）は、上記のサービス終了時刻である。
ｒ ｉ＝φｉ×Ｒ／φｂ                      …（１）
Ｆｉ＝ｍａｘ（ｔ ｉ，Ｆ′ｉ）＋Ｌｉ／ｒｉ  …（２）
なお上記式（１）および（２）において、Ｒは出力リンクの速度、ｔ ｉはキューｉの先頭パケットの到着時刻、Ｌｉはキューｉの先頭パケットのパケット長、Ｆ′ｉはこれから出力すべきパケットの直前のパケットのサービス終了時刻であり、また、ｍａｘ（ｔ ｉ，Ｆ′ｉ）はｔ ｉとＦ′ｉのうち大きい方を表す。
【００１０】
ＷＦＱにおいては、上記式（２）によって計算されたＦｉのうち、最小のＦｉを持つキューｉに格納されている先頭パケットを、次に出力すべきパケットとして選択する。
上述のようにして、複数のキューｉの中から次に出力すべきパケットを選択する、従来のパケットフェアキューイングによるパケットスケジューリング方法では、パケットフェアキューイングの重みφｉを次のように設定する。
【００１１】
まず、帯域保証を要求するトラヒックに対しては、各トラヒック毎に予約した帯域の相互の比に基づいて、各々の重みφｉを設定する。
一方、優先制御を要求するトラヒックに対しては、低優先トラヒックの重みφｉを、高優先トラヒックの重みφｉより小さく設定する。このように重みを設定することにより、帯域保証を要求するトラヒックに対しては予約帯域を保証することができる。一方、高優先トラヒックは、低優先トラヒックよりも大きい帯域（φｉ）が割当てられて、優先的に出力される。
【００１２】
なお、その他従来のパケットフェアキューイングとして、仮想時刻（virtual clock ）を用いることによって上記のＷＦＱを変形し計算量を抑えることのできる、ＳＣＦＱ（Self Clocked Fair Queueing）と呼ばれるパケットスケジューリング方法が、文献２：S.Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications", In Proc. of INFOCOM '94, pp.636-646, 1994. で提案されており、また、バーチャルクロック（Virtual Clock ）と呼ばれる同様の方法が、文献３：L.Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet Switcing Networking", In Proc. of SIGCOMM '90, pp.19-29, 1990.で提案されている。この仮想時刻を用いたアルゴリズムも本発明において適用可能であるが、これについては、第２実施例として、後述する。
【００１３】
【発明が解決しようとする課題】
上述した従来のパケットフェアキューイングによるパケットスケジューリング方法では、トラヒックのパケットは、このトラヒックに対して予め設定した帯域（φｉ）のみに従って出力される。したがって、低優先トラヒックのパケットは、その予約帯域に従い、高優先トラヒックのパケットがキューに格納されているかどうかに拘わらず、その低優先トラヒックのパケットが出力される。このため、本来、先に出力されるべき高優先トラヒックのパケットが、低優先トラヒックのパケットの後に出力されてしまう場合がある。この結果、高優先パケットと低優先パケットの出力順序が逆転してしまい、パケット単位で見た場合、高優先トラヒックが低優先トラヒックに対して優先的にサービスを受けられない場合がある、という問題があった。
【００１４】
したがって本発明は、上述の問題点に鑑み、上記〈１〉帯域保証のもとでは予約された帯域を保証しつつ、かつ上記〈２〉優先制御のもとでは、高優先トラヒックのパケットが必ず低優先トラヒックのパケットに対して優先することを保証する、パケットスケジューリング方法および装置を提供することを目的とするものである。
【００１５】
すなわち本発明は、上記〈１〉帯域保証と、上記〈２〉優先制御とを、常に、両立させることを目的とするものである。
【００１６】
【課題を解決するための手段】
図１は本発明に基づくパケットスケジューリング方法の基本ステップを示すフローチャートである。
図２は本発明に基づくパケットスケジューリング装置の基本構成を示す図である。
【００１７】
本発明に係る方法は、それぞれ予約した帯域が保証されている複数の帯域保証キュー（１３）と、それぞれ予め優先順序が設定されていて優先制御の対象となる複数の優先キューを有する優先キュークラス（１４）の各キューにそれぞれ格納されているパケットのうち最先に出力すべきパケットを選定するパケットスケジューリング方法であって、図１に示すステップＳ１〜Ｓ４を有する。これらのステップは次のとおりである。
【００１８】
ステップＳ１：各帯域保証キューに付与された重みと、優先キュークラス全体に付与された重み（φｉ、φｐ）とを記憶する。
ステップＳ２：記憶した重みを参照し、帯域保証キューについてはバックログ状態のキューがあるときはそのキューの重みを、優先キュークラスについてはバックログ状態の優先キューがあるときはこの優先キュークラスの重みを合計して合計値（φｂ）を計算する。
【００１９】
ステップＳ３：少なくとも、重みと、合計値と、優先順序の高いパケットであって優先キュークラスに最初に到着したパケットの最小到着時刻（ｔ ｍｉｎ）と、をパラメータとして、バックログ状態の各キューについてサービス時刻を計算する。
ステップＳ４：各サービス時刻相互間の大小比較により最小のサービス時刻を有する１のパケットを、最先に出力すべきパケットとして、選定する。
【００２０】
なお前記サービス時刻の計算は、実時刻に代えて、仮想時刻ｖ（Ｔ）を用いて行うこともできる。
本発明に係る装置は、上述したパケットスケジューリング方法を実施可能な装置であって、図２に示す基本構成を有する。
図２を参照すると、本発明のパケットスケジューリング装置１１は、基本的に、本図に示すブロック１〜３からなる。
【００２１】
サービス時刻計算部２は、入力された複数の所定のパラメータに基づき、バックログ状態の各帯域保証キュー（１３）と、バックログ状態にあり、かつ、最も高い優先順序を有する前記優先キュー（１４）とについて、それぞれのサービス時刻を計算する。
サービス時刻比較部３は、計算された各サービス時刻相互の大小比較をして、最小のサービス時刻を有するパケットを、最先に出力すべきパケットとして、選定する。
【００２２】
パラメータ生成部１は、帯域保証と、優先制御とを両立させるように計算されたパラメータを生成する。
【００２３】
【発明の実施の形態】
図３は本発明に基づくパケットスケジューリング装置を適用したパケット転送システムの一例を示す図である。なお全図を通じて、同様の構成要素には同一の参照番号または記号を付して示す。
本図において、参照番号１０はパケット転送システムであり、既述した例えばルーターやスイッチ等の中継装置内に形成される。
【００２４】
このパケット転送システム１０の中で、本発明の主たる構成要素となるのがパケットスケジューリング装置１１である。いわゆるスケジューラである。
パケットスケジューリング装置１１は、その入力側に複数のキューからなるキューセット１２を備え、またその出力側は出力リンク１５に接続する。
キューセット１２は、図示するように、帯域保証キュー１３と、優先キュークラス１４とに分類される。帯域保証キュー１３に属するキューは一例としてＱ１，Ｑ２…Ｑ（ｎ−５）のように示され、優先キュークラス１４に属するキューは一例として優先キュー（優先制御対象キュー）Ｑ（ｎ−４），Ｑ（ｎ−２）…Ｑｎのように示されている。なお、キューの割当ての仕方は、この例に限らず、任意でよい。
【００２５】
キューセット１２内のパケット群のうちの１つが、パケット転送装置１１において、パケットフェアキューイングに基づき選択される。選択されたその１つのパケットは出力リンク１５に送出され、相手方装置（図示せず）に送信される。上記出力リンク１５の速度、すなわち出力リンク速度は図中、Ｒとして示されている。出力リンク速度Ｒは、実際には、回線速度、回線容量あるいは出力帯域等である。
【００２６】
この出力リンク速度Ｒを占有する帯域の比率、すなわち重み（ｗ）を、図示するように割り振る。これは本発明の特徴の１つでもある。すなわちＲを、ｗ１〜ｗ（ｎ−５）と、ｗｐと、に割り振る。ここに、ｗｉ（ｉ＝１，２…（ｎ−５））を、帯域保証キュー１３の各キュー（Ｑ１，Ｑ２…Ｑ（ｎ−５））の予約帯域とすると、優先キュークラス１４（Ｑ（ｎ−４）〜Ｑｎ）の予約帯域ｗｐを、
ｗｐ＝Ｒ−ｗ ａｌｌ                        …（３）
のように設定する。ｗ ａｌｌは、帯域保証キュー１３の各予約帯域の合計である。
【００２７】
このように帯域の割振りをすると、帯域保証キュー１３の各キューの重みφｉ（ｉ＝１，２…（ｎ−５））と、優先キュークラス１４全体の重みφｐは、
φｉ＝ｗ ｉ／Ｒ                            …（４）
φｐ＝（Ｒ−ｗ ａｌｌ）／Ｒ                …（５）
と表すことができる。
【００２８】
上記式（４）および（５）のように、帯域保証キュー１３の各々の重みφｉと、優先キュークラス１４全体の重みφｐを設定しておくことにより、本発明の目的である、〈１〉帯域保証と〈２〉優先制御との両立が実現しやすくなる。
図４は本発明の第１実施例に基づく構成を表す図である。
図２のサービス時刻計算部２は図４においてサービス時刻計算手段２５として示され、図２のサービス時刻比較部３は図４においてサービス時刻比較手段２７として示される。そして図２のパラメータ生成部１は、図４において、優先キュー選択手段２１、重み記憶手段２２、重み合計値計算手段２３、最小到着時刻記憶手段２４、サービス時刻計算手段２５およびサービス時刻記憶手段２６として示される。
【００２９】
本図において、各ブロック２１〜２７の機能は次のとおりである。
優先キュー選択手段２１は、キューセット１２の中で、優先キュークラス１４に属する優先キュー（優先制御対象キュー）が該クラスの中のどのキューであるか、キューセット１２の各キューにパケットが格納されているか否か（キュー状態）、優先キュークラス１４内の各優先キューの優先順序がどのように設定されているか、の各情報を記憶しておいて、該情報と所定のアルゴリズムに基づき、パケットを出力すべき１つの優先キューを選択する。
【００３０】
重み記憶手段２２は、帯域保証キュー１３の各々の重みφｉ（上記の式（４））と、優先キュークラス１４の重みφｐ（上記の式（５））とを記憶する。
重み合計値計算手段２３は、キューセット１２内の各キューのバックログ状態に基づいて、パケットを格納している各キュー（１３，１４）が有する重みの合計値を計算する。優先キュー選択手段２１により優先キュー１４が選択されており、かつ、いずれかの帯域保証キュー１３がバックログ状態であれば、重み記憶手段２２を参照して、各φｉとφｐとを合計する。その合計値はφｂである。
【００３１】
最小到着時刻記憶手段２４は、優先キュークラス１４内の優先キューに格納されている各パケットのうち、優先キュークラス１４に最初に到着したパケットの到着時刻を記憶する。
サービス時刻計算手段２５は、パケットのサービス時刻を計算する。サービス時刻とは、直前に出力されたパケットのサービス終了時刻か、今サービス中であれば、そのサービス終了予定時刻である。
【００３２】
サービス時刻記憶手段２６は、サービス時刻をパケットと関連づけて記憶する。そのパケットが帯域保証キュー１３のパケットであれば、直前に同じキューから出力されたパケットについてのサービス時刻であり、あるいは、そのパケットが優先キュークラス１４のパケットであれば、優先順序に従って直前に選択されたキューから出力されたパケットのサービス時刻である。
【００３３】
サービス時刻比較手段２７は、最小到着時刻記憶手段２４と、サービス時刻記憶手段２６と協働してサービス時刻計算手段２５において計算された各キュー（１３，１４）についてのサービス時刻を相互に大小比較し、そのうち最小となるサービス時刻を判定して、当該最小サービス時刻に相当する１つのキューを選択する。これにより、図３のパケットスケジューリング装置１１から、１つの選択されたパケットが、出力リンク１５に送出される。
【００３４】
図５は図４に表す優先キュー選択手段２１の具体的構成例を示す図である。
本図において、優先キュー選択手段２１は、４つの手段３１，３２，３３および３４からなる。
キュー状態記憶手段３１は、キューセット１２内にパケットが格納されているか否かを記憶する。
【００３５】
優先制御対象キュー記憶手段３２は、キューセット１２の中で優先キュークラス１４に属する優先制御対象キュー（優先キュー）を記憶する。
優先順序記憶手段３３は、優先キュークラス１４に属する各優先キューの優先順序を記憶する。
選択手段３４は、上記手段３１，３２および３３からの、“キュー状態”情報と、“優先順序”情報と、“優先キュー”情報とに基づいて、次に重み合計値計算手段２３等に与えるべきパケット情報を出力する。
【００３６】
以下、図４および図５を参照して、パケットスケジューリング装置１１の動作を詳しく説明する。
１）優先キュー選択手段２１は、パケットを格納している優先キューのうち、最も高優先（優先順序の高い）なキューを選択する。この選択されたキューの情報を、重み合計値計算手段２３、サービス時刻計算手段２５およびサービス時刻比較手段２７に通知する（図４の〔１〕）。
【００３７】
図５に示すとおり、優先キュー選択手段２１は次のようにして、優先キューを選択する。
ａ）キュー状態記憶手段３１、優先制御対象キュー記憶手段３２および優先順序記憶手段３３は、それぞれ、着目した１つのキューが、バックログ状態であるか否か、優先制御対象か否か、優先キューであればその優先順序を、選択手段３４に通知する。
ｂ）選択手段３４では、バックログ状態でかつ、優先制御対象キューの中で、最も優先順序の高いキューを選択する。
２）図４の重み記憶手段２２は、帯域保証キュー１３の各キューの重みφｉと、優先キュークラス１４の重みφｐとを記憶している。記憶しているこれらの重みφｉ，φｐは、重み合計値計算手段２３と、サービス時刻計算手段２５とにそれぞれ通知される（図４の〔２〕と〔２〕′）。
【００３８】
なお、各帯域保証キューｉの重みφｉと、優先キュークラスの重みφｐは、既述の式（４）および（５）に従い、
φｐ＝（Ｒ−ｗ ａｌｌ）／Ｒおよび
φｉ＝ｗ ｉ／Ｒ
によってそれぞれ求まる。前述のとおり、Ｒは出力リンク速度、ｗ ｉは各帯域保証キューｉの予約帯域、ｗ ａｌｌは帯域保証するトラヒックの予約帯域の合計である。
３）図４の重み合計値計算手段２３では、パケットを格納するキューすなわちアクティブなキューの全ての重みの合計値φｂを、下記ａ）およびｂ）のように計算し、サービス時刻計算手段２５に通知する（図２の〔３〕）。
ａ）優先キュークラス１４の中の少なくとも１つの優先キューがバックログ状態の場合
φｂ＝（バックログ状態の帯域保証キューφｉの重みの合計値Σφｉ）＋φｐｂ）優先キュークラス１４の優先キューの全てが空の場合
φｂ＝（バックログ状態の帯域保証キューφｉの重みの合計値Σφｉ）
なお、上記φｂの計算手順の具体例については、後に図６を参照して説明する。
４）図４の最小到着時刻記憶手段２４は、優先キュークラス１４の優先キューに格納されているパケットの中で、その到着時刻が最小のパケットの時刻、すなわち最先に到着した最小到着時刻をｔ ｍｉｎとして、サービス時刻計算手段２５に通知する（図４の〔４〕）。
５）図４のサービス時刻記憶手段２６は、サービス時刻計算手段２５で計算されたサービス時刻を、パケットと関連付けて記憶する。ここに記憶したサービス時刻は、サービス時刻計算手段２５に通知される（図４の〔５〕）。
６）図４のサービス時刻計算手段２５はキューｉのサービス時刻Ｆｉを計算し、この計算後のＦｉを再び記憶手段２６に格納すると共に（図４の〔６〕）、サービス時刻比較手段２７に通知する（図４の〔６〕′）。
【００３９】
上記のサービス時刻を計算する方法および対象となるパケットは、適用するパケットフェアキューイングにより異なる。例えば、パケットフェアキューイングとして既述のパケットスケジューリング方法ＷＦＱを用いる場合には、各キューの先頭パケットの、ＧＰＳ規則におけるサービス終了時刻を、上記のサービス時刻として計算する。またパケットフェアキューイングとしてＳＦＱ（Start-time Fair Queueing）と呼ばれるパケットスケジューリング方法を用いる場合には、該ＧＰＳ規則におけるサービス開始時刻を、上記サービス時刻として計算する。
【００４０】
なお、上記のＷＦＱを用いる場合も、ＳＦＱを用いる場合も、従来の考え方によれば、キューｉのパケットのサービス時刻Ｆｉを計算するときに用いるパラメータとして、次の３つのパラメータ、すなわちｔ ｉ：パケットの到着時間、Ｆ′ｉ：キューｉで直前に格納されていたパケットのサービス時刻、φ ｉ：キューｉの重みを用いることになる。
【００４１】
ところが本発明の考え方によると、上記の考え方に加えて、さらに、特に優先キューに関して、変形したｔ ｉと、Ｆ′ｉと、φ ｉとを用いる。
すなわち選択された優先キューｐに格納されているパケットのサービス時刻の計算については、以下のように変形したｔ ｍｉｎ，Ｆ′ｐ，φ ｐを、上記のパラメータとして用いる。
【００４２】
ｔ ｉ  →  ｔ ｍｉｎ
Ｆ′ｉ  →  Ｆ′ｐ
φ ｉ  →  φ ｐ
ここで、
ｔ ｍｉｎ：最小到着時刻記憶手段２４に記憶している値、
Ｆ′ｐ：ａ）もしサービス時刻Ｆｉがキューの先頭パケットのサービス時刻であれば、優先キュークラス１４のパケットで、サービス中のパケットのサービス時刻、または、直前にサービスされたパケットのサービス時刻、
ｂ）もしキューの先頭のパケットでなければ、そのキューで直前に格納されていたパケットのサービス時刻、
φ ｐ：優先キュークラス１４に対して設定された重み、である。
【００４３】
なお、選択された優先キューの先頭パケットのサービス時刻Ｆ′ｐは、その優先キューが選択され続けている間に再計算されるものとする。
また、従来のパケットフェアキューイングのもとでは、サービス時刻の計算に、そのキューに格納されているパケット長の和を用いており、従来法のもとでは、選択された優先キューについてはそのパケット長の和を用いることになる。ところが本発明によれば、そのような、選択された優先キューのパケット長の和に代えて、優先キュークラス１４のパケットのパケット長の和を用いる。
【００４４】
この場合、選択されていない優先キューのサービス時刻Ｆ′ｐとしては、サービス時刻として取り得る値の最大値より大きい値を設定する。これにより、下記の７）において、全てのキューのサービス時刻の大小を比較したときに、当該非選択の優先キューが選出されることはなく、当該非選択の優先キューを比較対象から容易に除外することができる。
７）図４のサービス時刻比較手段２７は、上記非選択の優先キューを除く全てのアクティブなキュー（１３，１４）の各先頭パケットについて、これら相互間のサービス時刻の大小比較を行う。この比較の結果、最小のサービス時刻を有するいずれか１つのキューの先頭パケットを選出し、出力リンク１５に送出する。
【００４５】
前述の説明の中で、φｂの計算手順については後述する、としていたので、これをここで説明しておく。
図６は重み合計値計算手段２３によるφｂの計算手順の具体例を示すフローチャートである。
ステップＳ１１：全てのキューの重みの合計値であるφｂの初期値として０を設定する。
【００４６】
ステップＳ１２：各キューｉについてそれぞれ本フローチャートのステップを繰り返し実行する。
ステップＳ１３：今着目しているキューｉが、優先制御対象キュー（優先キュー）か否か判定する。例えば図３の左端に示す例では、Ｑ（ｎ−４）〜Ｑｎのいずれか１つに該当すれば、その判定はＹｅｓであり、Ｑ１〜Ｑ（ｎ−５）のいずれか１つに該当すれば、その判定はＮｏである。
【００４７】
ステップＳ１４：今着目している優先キューｉが、優先順序に鑑み、選択されているか（Ｙｅｓ）、否か（Ｎｏ）を判定する。
ステップＳ１５：今着目しているキューｉが、選択優先キューであるので、合計値φｂに、φｉ＝φｐを加算する。φｐは優先キュークラス１４の重みである。
【００４８】
ステップＳ１６：今着目しているキューｉが、非選択優先キューであるので、上述のように、サービス時刻比較手段２７（図４）による比較対象から除外されており、合計値φｂには何も加算されない。
ステップＳ１７：上記ステップＳ１３での判定がＮｏのとき、すなわち今着目しているキューｉが優先制御対象キュー（１４）でないとき（帯域保証キュー１３のとき）、そのキューｉがアクティブか否か、すなわちパケットを格納しているか否か判定する。
【００４９】
ステップＳ１８：今着目しているキューｉがアクティブであるから、当該キューｉの重みφｉを合計値φｂに加算する。
ステップＳ１９：今着目しているキューｉがアクティブでないので、その重みφｉを合計値φｂに加算する必要はなく、φｂはそのままである。
なお、上述したステップＳ１３，Ｓ１４およびＳ１７の判定には、既述した図５の優先キュー選択手段２１からの情報が用いられる。
【００５０】
図３〜図６を用いて説明した本発明のパケットスケジューリング装置１１の概要をさらに分かりやすく図解して説明する。
図７は本発明に係るパケットスケジューリング装置１１の動作概要を図解的に表す図である。なお、本図は同装置１１内の主として優先キュー選択手段２１とサービス時刻比較手段２７に着目した図である。
【００５１】
本図の左端のキューセット１２は、図３の左端に示したとおりである。
本図の上欄に示す
ｔｙｐｅ ｉは、優先制御対象フラグであり、上述した図６のステップＳ１３での判断により定まる。
ｓ ｉは、キュー状態フラグであり、図６のステップＳ１７（およびＳ１４）での判断により定まる。
【００５２】
ｓｅｌｅｃｔ ｉは、優先キュー選択フラグであり、図６のステップＳ１４での判断により定まる。
フラグｔｙｐｅ ｉについて見ると、帯域保証キュー１３は全て０、優先キュークラス１４は全て１である。
フラグｓ ｉについて見ると、図７の左端に示す各キュー（Ｑ１〜Ｑｎ）の中でパケットＰＴを格納しているアクティブなキューについては、全て１、その他は０である。
【００５３】
フラグｓｅｌｅｃｔ ｉについて見ると、図７の例では、優先キュークラス１４の中で、かつ、アクティブなキューＱ（ｎ−２）〜Ｑｎの中で、最も優先順序が高いキューはＱ（ｎ−２）であるから、キューＱ（ｎ−２）について、ｓｅｌｅｃｔ ｉは１となり、他は０である。
サービス時刻比較手段２７は、図４に示すサービス時刻計算手段２５からのサービス時刻（Ｆ ｉ）情報に基づき、Ｆ１〜Ｆ（ｎ−５），Ｆ（ｎ−２）のうち、最小のもの（本図の例では、Ｆ（ｎ−２））を選択し、当該パケットを出力リンク１５へ送出する。なお、既に述べたように、非選択の優先キューに対しては、サービス時刻として取り得る最大値より大きい値（ａｌｌ  １）が設定され、これらのサービス時刻は比較対象から容易に除外されている。このサービス時刻の比較については後にさらに詳しく説明する。
【００５４】
図８は図４に示す第１実施例に係る装置１１のさらに具体的な構成例を示す図であり、
図９は図５に示す第１実施例に係る選択手段２１のさらに具体的な構成例を示す図である。
主として図８および図９を参照しながら、パケットフェアキューイングとしてＷＦＱを適用した場合の動作例について以下説明する。
【００５５】
まず、パケット転送システム１０に到着するパケットは、フロー毎に各キュー（Ｑ１〜Ｑｎ）に格納されているとする（図３参照）。図３の例では、Ｑ１〜Ｑ（ｎ−５）が帯域保証キューでありＱ（ｎ−４）〜Ｑｎが優先キューである。なお、既述のとおり、帯域保証キューと優先キューの各キューへの割当ては、ユーザからの指定により自由に変更でき、この例の組み合わせに限定されるものではない。
１）重み記憶手段２２は、その中に記憶している各帯域保証キューの重みφｉと、優先キュークラス１４の重みφｐとを、重み合計値計算手段２３とサービス時刻計算手段２５とにそれぞれ通知する〔１〕，〔１〕′。
【００５６】
ここで、帯域保証キューｉの重みφｉは、
φｉ＝ｗ ｉ／Ｒ、
優先キュークラスの重みφｐは、
φｐ＝（Ｒ−ｗ ａｌｌ）／Ｒ
がそれぞれ設定されているものとする。前述したようにｗ ｉは帯域保証キューｉの予約帯域、Ｒは出力リンク速度、ｗ ａｌｌは帯域保証するトラヒックの予約帯域の合計、をそれぞれ表す。
２）キュー状態記憶手段３１は、キュー状態フラグ（図７のｓ ｉ）として１ビットの変数ｓ １〜ｓ ｎをもち、キューｉから出力すべきパケットが格納されていればｓ ｉ＝１、格納されていなければｓ ｉ＝０を設定する。キュー状態フラグｓ ｉは、選択手段３４（図９）と、サービス時刻計算手段２５と、重み合計値計算手段２３とにそれぞれ通知される〔２〕。
３）優先制御対象キュー記憶手段３２（図９）は、優先制御対象フラグ（図７のｔｙｐｅ ｉ）として１ビットの変数ｔｙｐｅ １〜ｔｙｐｅ ｎをもち、優先制御を行うフローが、キューｉに割当てられる場合はｔｙｐｅ ｉ＝１、帯域保証を行うフローが、キューｉに割当てられる場合はｔｙｐｅ ｉ＝０を、それぞれ設定する。図３の例では、ｔｙｐｅ １からｔｙｐｅ （ｎ−５）は０、ｔｙｐｅ （ｎ−４）からｔｙｐｅ ｎは１が設定される。
【００５７】
この優先制御対象フラグｔｙｐｅ ｉは、選択手段３４と、サービス時刻計算手段２５と、重み合計値計算手段２３とに、それぞれ通知される〔３〕。
４）優先順序記憶手段３３（図９）は、優先順序テーブルとして、変数ｐｒｉ １〜ｐｒｉ ｎをもち、キューｉの優先順序をｐｒｉ ｉとして設定する。なお優先順序は、高優先なものから１〜ｎの値で表す。図３の例では、ｐｒｉ （ｎ−４）からｐｒｉ ｎに、１から５の値が、それぞれ設定される。上記優先順序テーブルの内容は、選択手段３４と、サービス時刻計算手段２３とに、それぞれ通知される〔４〕。
５）選択手段３４は、所定の手順に従って、パケットＰＴが格納されている最も高優先なキューを選択し、そのキュー番号をｓｅｌｅｃｔ ｉとして出力する〔５〕。この所定の手順は、後に図１０および図１１に示す。
６）重み合計値計算手段２３では、φ ｉ，φ ｐ，ｓ ｉ，ｔｙｐｅ ｉおよびｓｅｌｅｃｔ ｉから、所定の手順に従って、アクティブなキューの重みの合計値φｂを計算し、サービス時刻計算手段２５に通知する〔６〕。この所定の手順は、後に図１２に示す。
７）最小到着時刻記憶手段２４は、優先キュー（１４）に格納されているパケットＰＴの到着時刻で最小の値を、ｔ ｍｉｎとして、サービス時刻計算手段２５に通知する〔７〕。
８）サービス時刻記憶手段２６は、キューｉから直前に出力されたパケットＰＴのサービス終了時刻Ｆ′ｉを記憶する。また、優先キュークラス１４についてはその中で最後に出力したパケットＰＴのサービス終了時刻をＦ′ｐとして記憶する。このように記憶したサービス終了時刻は、サービス時刻計算手段２５に通知する〔８〕。
９）サービス時刻計算手段２５は、キューｉのサービス終了時刻を、以下に示すように計算する。計算したＦｉの値は、サービス時刻比較手段２７と、サービス時刻記憶手段２６とに、それぞれ通知する〔９〕，〔９〕′。
【００５８】
ａ）キューｉが帯域保証キュー１３の場合：
ｒ ｉ＝φ ｉ×Ｒ／φ ｂ
Ｆｉ＝ｍａｘ｛ｔ ｉ，Ｆ′ｉ｝＋Ｌ ｉ／ｒ ｉ
ｂ）キューｉが、選択された優先キューの場合（ｓｅｌｅｃｔ ｉ＝１）：
ｒ ｉ＝φ ｐ×Ｒ／φ ｂ
Ｆｉ＝ｍａｘ｛ｔ ｍｉｎ，Ｆ′ｐ｝＋Ｌ ｉ／ｒ ｉ
ｃ）キューｉが、選択されていない優先キュー（ｓｅｌｅｃｔ ｉ＝０）、
またはアクティブでない帯域保証キュー１３の場合：
Ｆｉ＝（ａｌｌ  １）
（ａｌｌ  １）は、図７の右端参照。
【００５９】
ここで上記の記号の意味を再確認しておくと、以下のとおりである。
Ｒ：出力リンク１５の速度
ｔ ｉ：先頭パケットの到着時間
ｔ ｍｉｎ：優先キュークラス１４に最初に到着したパケットＰＴの到着時間
Ｆ′ｉ：キューｉから直前に出力したパケットＰＴのサービス時刻
Ｌ ｉ：キーｉの先頭パケットＰＴのパケット長
φ ｐ：優先キュークラス１４の重み
Ｆ′ｐ：優先キュークラス１４から直前に出力したパケットＰＴのサービス時刻
ａｌｌ  １：２進数表記で全てのビットが１の数であり、最大値を示す。
１０）サービス時刻比較手段２７は、サービス終了時刻Ｆ１〜Ｆｎ（図７の右端参照）の大小比較を行う。この場合、帯域保証キュー１３のサービス時刻と選択されている優先キューのサービス時刻は共に（ａｌｌ  １）、より小さい値をとるので、選択されていない優先キューが大小比較で選ばれることはない。
【００６０】
もし、この（ａｌｌ  １）の設定がなければ、優先キュー選択手段２１から各優先キューが選択されているか否かが、ｓｅｌｅｃｔ ｉとして通知され、ｓｅｌｅｃｔ ｉ＝０となるキューｉのサービス時刻Ｆｉを大小比較から除外する処理が行われる。
かくして最小のＦｉの値を示すキューｉを、出力手段３５に通知する〔１０〕。
１１）出力手段３５は、サービス時刻比較手段２７から通知されたキューｉの先頭パケットを読み出し、出力リンク１５に送出する〔１１〕。
【００６１】
前述の説明の中で、所定の手順については、図１０，１１および図１２において後述するとしていたので、これをここで説明する。
図１０は最も高優先なキューを選択し、そのキュー番号をｓｅｌｅｃｔ ｉとして出力する手順の一例を示すフローチャート（その１）、
図１１は同フローチャート（その２）である。
【００６２】
図１０および図１１を参照して各ステップを説明する。
ステップＳ２１：ｓｅｌｅｃｔ，ｐｒｉｏｒｉｔｙ（ｐｒｉ）およびｉ（キューｉ）について、初期値を設定する。なお、ｐｒｉｏｒｉｔｙとしては、選択不能な値を設定する。
ステップＳ２２：キューｉを１つずつインクリメントする。
【００６３】
ステップＳ２３：この判定でＹｅｓのときは、未処理のキューｉが残っている。
ステップＳ２４：今着目しているキューのキュー状態がアクティブ（パケットあり）で、かつ、優先キュークラス１４のキューであるか判定し、Ｎｏならば、再び元に戻る。
【００６４】
ステップＳ２５：今着目しているキューの優先順序（ｐｒｉｏｒｉｔｙ）が現在選択されているキューのｐｒｉ ｉよりも大ならば、元に戻る。ｐｒｉ ｉは小さいほど高優先である。
ステップＳ２６：今着目しているキューのｐｒｉ ｉが、現在既に選択されているキューのｐｒｉ ｉよりも小ならば、優先キュー選択手段２１でのｓｅｌｅｃｔ ｉとｐｒｉ ｉとが一旦記憶される。
【００６５】
ステップＳ２７：再びキューｉをｉ＝０に戻す。
ステップＳ２８：再びキューｉを１ずつインクリメントする。
ステップＳ２９：全てのキューｉが処理されたか判定し、未処理のキューｉがあれば（Ｙｅｓ）、ステップＳ３０へ移る。
ステップＳ３０：今着目しているキューｉが選択（ｓｅｌｅｃｔ）されているものと同じか否か判定する。
【００６６】
ステップＳ３１：同じならば、このキューｉが選択されて、ｓｅｌｅｃｔ＝１を選択手段３４より出力する。
ステップＳ３２：同じでなければ、このキューｉについては非選択とし、ｓｅｌｅｃｔ＝０を選択手段３４より出力する。
図１２は重みの合計値φｂを求める手順の一例を示すフローチャートである。
【００６７】
本図のフローチャートは、図６のフローチャートを具体的にプログラミングしたときのステップに相当する。したがって本図のステップＳ４１〜Ｓ４９の殆んどは、図６のステップＳ１１〜Ｓ１９と対応している。例えば、本図のステップと図６のステップとが、Ｓ４４＝Ｓ１３，Ｓ４５＝Ｓ１４，Ｓ４６＝Ｓ１５，Ｓ４７＝Ｓ１７，Ｓ４８＝Ｓ１８のように対応している。
【００６８】
以上本発明に係る第１実施例について説明したので、次に本発明に係る第２実施例について説明する。
図１３は本発明の第２実施例に基づく構成を表す図である。
本図（第２実施例）と図４（第１実施例）とを対比すると、仮想時刻計算手段２８を追加した点が相違する。なお、本図の構成は、パケットフェアキューイングとして、前述したＳＣＦＱ（Self Clocked Fair Queueing）を適用した場合の構成を示す。
【００６９】
上記第２実施例に固有の仮想時刻計算手段２８は、重み合計値計算手段２３で計算された重み合計値をもとに、仮想時刻を計算する機能を有するものである。
この重み合計値計算手段２３は、パケットを格納するキューすなわちアクティブなキューの重みの合計値φｂを、第１実施例で詳述したように計算し、仮想時刻計算手段２８とサービス時刻計算手段２５とに通知する（図１３の〔３〕′および〔３〕）。
【００７０】
第１実施例では、実時刻を用いて計算したのに対し、第２実施例では、仮想時刻計算手段２８を導入して、該手段２８により、実時刻をパラメータとする仮想時刻ｖ（Ｔ）を用いて計算する。ここで仮想時刻ｖ（Ｔ）は、実時刻に対する変化率が、重み合計値φｂの変化率にほぼ反比例するように計算される。φｂを１つのパイプに例えれば、φｂが大きいときはパイプが太くそこを流れるパケットは時間的に早く進み、φｂが小さければパイプは細いのでそこを流れるパケットは時間的に遅く進む。このような時間の変化を考慮したのが仮想時刻ｖ（Ｔ）であり、このｖ（Ｔ）を用いると計算の高速化が図れる。かくして計算した仮想時刻ｖ（Ｔ）は、サービス時刻計算手段２５に通知される〔３〕′。
【００７１】
このように仮想時刻ｖ（Ｔ）を用いる場合、選択された優先キューの先頭パケットのサービス時刻は、既述した諸パラメータに加え、ｔ ｍｉｎにおける仮想時刻ｖ（ｔ ｍｉｎ）によって計算されることになる。
かくして第２実施例は、重み合計値計算手段２３からの出力をもとに、仮想時刻を計算する仮想時刻計算手段２８を有し、最小到着時刻記憶手段２４はその仮想時刻をもとに優先キュークラスに最初に到着したパケットの到着時刻における仮想時刻を記憶し、サービス時刻計算手段２５はその仮想時刻をもとにサービス時刻を計算し、優先キュー選択手段２１により選択された優先キューのサービス時刻の計算には、最小到着時刻記憶手段２４に記憶された仮想時刻を用いるように構成されている。
【００７２】
図１４は図１３に示す第２実施例に係る装置１１のさらに具体的な構成例を示す図である。
本図に示す構成における動作は、図８を用いて説明した第１実施例の構成のもとでの動作１）〜１１）と大半は同様であるので、以下に、相違する部分を詳しく説明する。
【００７３】
なお前記のパケットフェアキューイングとして、仮想時刻を用いたＳＣＦＱを適用した場合の動作例である。
１）図８を参照して既に説明した第１実施例（以下、実施例１と呼ぶ）の動作１）と同様である。すなわち、φｉとφｐを、重み合計値計算手段２３に通知する（図１４の〔１〕と〔１〕′）。
２）実施例１の２）と同様（キュー状態フラグｓ ｉを手段２３に通知）〔２〕。
３）実施例１の３）と同様（優先制御対象フラグｔｙｐｅ ｉを手段２３に通知）〔３〕。
４）実施例１の４）と同様（優先順序フラグｐｒｉ ｉを手段２３に通知）〔４〕。
５）実施例１の５）と同様（優先キュー選択フラグｓｅｌｅｃｔ ｉを手段２３に通知）〔５〕。
６）実施例１の６）と同様（合計値φｂを転送するが、第２実施例では、仮想時刻計算手段２８にφｂを転送する（図１４の〔６〕））。
７）仮想時刻計算手段２８では、実時刻Ｔでの仮想時刻ｖ（Ｔ）を、次のように計算する。
【００７４】
ｖ（０）＝０、
ｖ（Ｔ ２）−ｖ（Ｔ １）＝φ ａｌｌ／φｂ
ここで、Ｔ ２＞Ｔ １であり、φ ａｌｌ＝（帯域保証キュー１３の重みφ ｉの合計）＋（優先キュークラス１４の重みφ ｐ）である。
このように計算された仮想時刻ｖ（Ｔ）は、サービス時刻計算手段２５に通知される（図１４の〔７〕）。
８）最小到着時刻記憶手段２４は、優先キュー１４に格納されているパケットＰＴの到着時刻で最小の値ｔ ｍｉｎおよび仮想時刻ｖ（ｔ ｍｉｎ）を記憶し、サービス時刻計算手段２５に通知する（図１４の〔８〕）。
９）サービス時刻記憶手段２６は、キューｉに格納されているパケットおよび、サービス中またはサービス直後のパケットのサービス終了時刻Ｆｉをパケットと関連付けて記憶している。また、優先キュークラス１４から最後に出力したパケットのサービス終了時刻を、Ｆ′ｐとして、記憶する。記憶したサービス終了時刻は、サービス時刻計算手段２５に通知する（図１４の〔９〕）。
１０）サービス時刻計算手段２５は、キューｉに到着したパケットＰＴに対して、サービス終了時刻を次のように計算する。
【００７５】
ａ）キューｉが帯域保証キュー１３の場合：
Ｆｉ＝ｍａｘ｛Ｆ′ｉ，ｖ（ｔ）｝＋Ｌ ｉ／ｒ ｉ
ｂ）キューｉが、選択された優先キューの場合（ｓｅｌｅｃｔ ｉ＝１）：
Ｆｉ＝ｍａｘ｛Ｆ′ｐ，ｖ（ｔ ｍｉｎ）｝＋Ｌ ｉ／ｒ ｉ
ｃ）キューｉが選択されていない優先キュー（ｓｅｌｅｃｔ ｉ＝０）、
またはアクティブでない帯域保証キュー１３の場合：
Ｆｉ＝（ａｌｌ  １）
ここで上記の記号の意味を再確認しておくと、以下のとおりである。
【００７６】
ｖ（Ｔ）：時刻Ｔでの仮想時刻
ｔ：パケットが到着したときの時刻
ｔ ｍｉｎ：優先キュークラス１４に最初に到着したパケットＰＴの到着時刻
Ｌ ｉ：キューｉの先頭パケットＰＴのパケット長
φ ｐ：優先キュークラス１４の重み
Ｆ′ｐ：優先キュークラス１４から直前に出力したパケットＰＴのサービス時刻
ａｌｌ  １：２進数表記で全てのビットが１の数であり、最大値を示す。ただし、選択された優先キューの先頭パケットは、パケットがキューの先頭になるか、または出力すべき優先キューとして選択された時点で、サービス時刻を再計算するものとする。
【００７７】
計算したＦｉの値は、サービス時刻比較手段２７とサービス時刻記憶手段２６に通知される（図１４の〔１０〕と〔１０〕′）。
１１）実施例１の１０）と同様（Ｆｉを出力段３５に通知）〔１１〕。
１２）実施例１の１１）と同様（パケットＰＴを出力リンク１５へ送出）〔１２〕。
【００７８】
【発明の効果】
以上説明したように、本発明のパケットスケジューリング方法によれば、パケットフェアキューイングと同様の帯域保証と公平な帯域割当てを可能としつつ、なおかつ、高優先のパケットは、常に、より低優先なパケットより先に出力リンクへ送出することができる。したがって、帯域が予約されたトラヒックに対しては、帯域保証と公平な余剰帯域の割当てとを行い、帯域が予約されていないトラヒック間においては、パケット単位での確実な優先制御を行って、高い通信品質を保証することができる。
【００７９】
また本発明は、仮想時刻を使って計算の手間を削減するパケットフェアキューイングも容易に適用することができ、この場合は、処理のより一層の高速化を可能とするパケットスケジューリング装置が実現できる。
さらにまた本発明は、パケットスケジューリング装置内のキューに対し、帯域保証キューと優先キューの割当てを自由に変更することができ、したがって帯域保証を要求するトラヒックが多い場合にはその帯域保証キューの割合を自由に増やすことができる。このため装置内のキューを有効に利用することが可能となる。
【００８０】
また本発明は、サービス時刻の大小比較において、選択されていない優先キューについては、これらのサービス時刻として単にａｌｌ  １を与えるだけで、その比較対象から排除することができる。したがってそのような排除のための処理が不要となるため、高速にサービス時刻の比較を行い、出力すべきパケットを決定することができる。
【００８１】
さらにまた本発明においては、既述した式（３）により、優先キュークラスの予約帯域φｐを定めているので、優先度の高いトラヒックは、予約されていない、出力リンクの帯域があれば、これを優先して利用することが可能となり、優先制御がより円滑に実行される。
【図面の簡単な説明】
【図１】本発明に基づくパケットスケジューリング方式の基本ステップを示すフローチャートである。
【図２】本発明に基づくパケットスケジューリング装置の基本構成を示す図である。
【図３】本発明に基づくパケットスケジューリング装置を適用したパケット転送システムの一例を示す図である。
【図４】本発明の第１実施例に基づく構成を表す図である。
【図５】図４に表す優先キュー選択手段２１の具体的構成例を示す図である。
【図６】重み合計値計算手段２３によるφｂの計算手順の具体例を示すフローチャートである。
【図７】本発明に係るパケットスケジューリング装置１１の動作を図解的に表す図である。
【図８】図４に示す第１実施例に係る装置１１のさらに具体的な構成例を示す図である。
【図９】図５に示す第１実施例に係る選択手段２１のさらに具体的な構成例を示す図である。
【図１０】最も高優先なキューを選択し、そのキュー番号をｓｅｌｅｃｔ ｉとして出力する手順の一例を示すフローチャート（その１）である。
【図１１】最も高優先なキューを選択し、そのキュー番号をｓｅｌｅｃｔ ｉとして出力する手順の一例を示すフローチャート（その２）である。
【図１２】重みの合計値φｂを求める手順の一例を示すフローチャートである。
【図１３】本発明の第２実施例に基づく構成を表す図である。
【図１４】図１３に示す第２実施例に係る装置１１のさらに具体的な構成例を示す図である。
【符号の説明】
１…パラメータ生成部
２…サービス時刻計算部
３…サービス時刻比較部
１０…パケット転送システム
１１…パケットスケジューリング装置
１２…キューセット
１３…帯域保証キュー
１４…優先キュークラス
１５…出力リンク
２１…優先キュー選択手段
２２…重み記憶手段
２３…重み合計値計算手段
２４…最小到着時刻記憶手段
２５…サービス時刻計算手段
２６…サービス時刻記憶手段
２７…サービス時刻比較手段
２８…仮想時刻計算手段
３１…キュー状態記憶手段
３２…優先制御対象キュー記憶手段
３３…優先順序記憶手段
３４…選択手段
３５…出力手段
【図１】
0004338285.tif 000002
【図２】
0004338285.tif 000003
【図３】
0004338285.tif 000004
【図４】
0004338285.tif 000005
【図５】
0004338285.tif 000006
【図６】
0004338285.tif 000007
【図７】
0004338285.tif 000008
【図８】
0004338285.tif 000009
【図９】
0004338285.tif 000010
【図１０】
0004338285.tif 000011
【図１１】
0004338285.tif 000012
【図１２】
0004338285.tif 000013
【図１３】
0004338285.tif 000014
【図１４】
0004338285.tif 000015