(57)【特許請求の範囲】
【請求項１】
出力保証帯域に基づく重み係数がそれぞれ設定された複数のキューにより送出待ちのパケットを管理するとともに、各キューに格納された先頭パケットの送出順序を決定するパケットスケジューラであって、
各キューにおける送出待ちパケットの管理情報と前記重み係数とを用いた計算により得られた送出予定時刻情報に基づき、最優先に送出すべきパケットを格納するキューを選択制御するキュー制御手段と、
現在時刻情報に基づいて、該キュー制御手段における処理を補正する補正手段と、をそなえ、
該キュー制御手段が、バックログ状態の各キューにおける送出待ちパケットの管理情報と重み係数とを用いて前記バックログ状態の各キューに格納されたパケットの送出予定時刻を計算する送出予定時刻計算手段と、該送出予定時刻計算手段にて計算された各送出予定時刻情報に基づいてパケットを最優先に送出すべきキューを選択する選択手段とをそなえて構成されるとともに、
該補正手段は、該送出予定時刻計算手段にて計算された該送出予定時刻情報が、該現在時刻情報よりも所定の許容値を超えて大きい場合には、該送出予定時刻計算手段による計算に前記現在時刻情報を反映させることにより、該選択手段における選択処理を補正することを特徴とする、パケットスケジューラ。
【請求項２】
該補正手段が、該キュー制御手段にて選択制御されたキューについて計算された前記の送出予定時刻情報と現在時刻情報との乖離量を検出する乖離量検出手段と、該乖離量検出手段にて検出された乖離量に基づいて該選択手段による選択処理を補正すべく指示する指示手段とをそなえて構成されたことを
特徴とする、請求項１記載のパケットスケジューラ。
【請求項３】
該指示手段が、該乖離量検出手段にて検出された乖離量に基づいて、該選択手段による選択の基準となる各キューの送出予定時刻情報を補正すべく指示するように構成されたことを特徴とする、請求項２記載のパケットスケジューラ。
【請求項４】
各キューにおける送出待ちパケットの管理情報を前記現在時刻情報を含んで入力され前記の管理情報から現在時刻情報を取得する時刻情報取得手段をそなえ、該補正手段が、該時刻情報取得手段にて取得された現在時刻情報に基づいて、該キュー制御手段における処理を補正するように構成されたことを特徴とする、請求項1記載のパケットスケジューラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットスケジューラに関し、特に、いわゆるルータなどのパケット転送装置においてＷＦＱ(Weighted Fair Queuing)を用いたパケットスケジューリングを行なう際に用いて好適な、パケットスケジューラに関する。
【０００２】
【従来の技術】
近年、ネットワークを利用するマルチメディア情報通信や、リアルタイムで通信を行なうアプリケーションの普及が進行している。このようなネットワークの利用態様の普及に伴って、ネットワークが提供する通信品質の保証の強化、向上が求められている。
【０００３】
ＩＰ(Internet Protocol)や、ＡＴＭ(Asynchronous Transfer Mode)などの技術は、上述のごときアプリケーションの普及を支えているものであるが、これらＩＰやＡＴＭにおけるネットワーク中継装置(パケット転送装置)としてのルータにおいては、トラヒックに応じてパケットを複数のキューに分類し、要求された通信品質を保証しながら転送制御を行なうパケットスケジューリングが必要となる。
【０００４】
また、ネットワークに要求される通信品質として、トラヒックに保証すべき帯域を予約する場合がある。このため、パケット転送装置では、それぞれのトラヒックに対して帯域を予約し、その予約帯域を保証するようにパケットの送信を行なう必要がある。
このようなパケット転送装置では、トラヒックごとに独立に、先入れ先出しメモリ(FIFO；First-In  First-Out)方式のメモリ等で構成されるキューをそなえ、各トラヒックに予約された帯域を保証しつつ、各トラヒックのキューに保持されたパケットの送出順序を決定するパケットスケジューリング方式が必要となる。このようなパケットスケジューリング方式として、ＷＦＱ(Weighted  Fair  Queuing)によるアルゴリズムがよく知られている。ＷＦＱについては、例えば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に記載されている。
【０００５】
図１９は、上述のネットワーク上のパケット転送装置における従来のＷＦＱアルゴリズムによるパケット転送技術を説明するための図であり、この図１９において、１０１−１〜１０１−ｎはキュー、１０２は各キュー１０１−１〜１０１−ｎに保持されているパケットの送出順序を決定するパケットスケジューラである。
【０００６】
この図１９において、各トラヒックｔｒ１〜ｔｒｎのパケットはそれぞれのキュー１０１−１〜１０１−ｎに格納され、各キュー１０１−１〜１０１−ｎに保持されたパケットはＦＩＦＯ方式で出力される。また、キュー１０１−ｉ（ｉ；1〜ｎ）には予約帯域に比例した重み係数φｉが設定され、送信すべきパケットがキューに格納されているとき、そのキューはバックログ状態もしくはアクティブであると定義する。バックログ状態のキューの重みを合計したものをφｂとする。
【０００７】
この図１９に示すパケットスケジューラ１０２では、非アクティブ状態のキューの余剰帯域を公平に配分することも考慮して、各キューの先頭パケット（最初に出力されるべきパケット）の送出予定時刻(例えばキュー１０１−ｉの値Ｆｉ)を以下の式（１）及び式（２）により計算し、得られた各キュー１０１−１〜１０１−ｎの先頭パケットの送出予定時刻に基づいて、最優先で出力すべきパケットを保持するキューを選択するようになっている。
【０００８】
ここで、ｒｉはキュー１０１−ｉのトラヒックｔｒｉに予約された帯域に余剰帯域が配分された値、ｔｉはキュー１０１−ｉに保持されている先頭パケットのキュー１０１−ｉへの到着時刻データ、Ｌｉは当該先頭パケットのパケット長、Ｒは出力リンクの速度、Ｆ′ｉはキュー１０１−ｉにおいて前回パケットを送出した際に計算された送出予定時刻データである。なお、全てのキューの予約帯域を保証するためにはＲ≧Σφｉとなる必要がある。
【０００９】
ｒｉ＝φｉ×Ｒ／φｂ                                   …（１）
Ｆｉ＝ｍａｘ{Ｆ′ｉ，ｔｉ}＋Ｌｉ／ｒｉ                 …（２）
すなわち、図２０に示すように、式（２）の第1項ｍａｘ{Ｆ′ｉ，ｔｉ}は、直前に出力したキュー１０１−ｉの先頭パケットの送出予定時刻Ｆ′ｉと、その先頭パケットに続く同じキュー１０１−ｉのパケットの到着時刻ｔｉとのうちで値の大きい（時刻の遅れた）方を計算基準として採ることを表すもので、第２項Ｌｉ／ｒｉは、予約帯域ｒｉでパケット長Ｌｉのパケットを送出したときに要する転送時間を示すものである。
【００１０】
換言すれば、第１項ｍａｘ{Ｆ′ｉ，ｔｉ}は、先頭パケットの送出予定時刻Ｆｉの計算基準となる時刻情報を、Ｆ′ｉまたはｔｉのいずれかに揃えることを意味している。例えば、直前のパケット出力後に次のパケットが当該キュー１０１−ｉに到着するという状況では、ｔｉの方がＦ′ｉよりも遅れた時刻を刻むことになるので、ｔｉの値を計算基準とする。逆に、図２０に示すように、直前のパケットが出力される前に次のパケットが到着するという状況では、Ｆ′ｉの方がｔｉよりも遅れた時刻を刻むことになるので、Ｆ′ｉの値を計算基準とする。
【００１１】
前述したように、パケットスケジューラ１０２では、このようにして計算されたＦｉに基づいて、出力すべきパケットとして、最小のＦｉを持つアクティブ状態のキュー１０１−ｉを選択して、当該キュー１０１−ｉに対して先頭パケットの送出指示を行なう。
なお、選出されたキュー１０１−ｉの先頭パケットの送出予定時刻Ｆｉは、Ｆ′ｉとして後続パケットのＦｉ計算に用いられる。このように、パケットスケジューラ１０２では、パケット選出のたびにＦｉの値をインクリメント処理する。換言すれば、一つのパケットが選出されて回線に出力されるたびに、新しいキューの条件によるＦｉ計算（式（１）及び式（２）参照）とともにパケット選出処理が行なわれることになる。
【００１２】
上述のごときＷＦＱアルゴリズムを適用したパケット転送装置では、通常、上記式（１）及び式（２）の計算において用いられる各変数は有限のビット長で表現され、タイマなどで計測されるパケット到着時刻においても、有限のビット長で表現される値が用いられる。
【００１３】
【発明が解決しようとする課題】
しかしながら、このような従来のＷＦＱアルゴリズムにおいては、上述の送出予定時刻Ｆｉと実際の時刻（実時刻）とが一定値以上乖離した場合には、以下に示すような要因により、Ｆｉの計算値を示すビットデータが一定値以上になり、桁あふれ(オーバフロー)を起こす可能性がある。オーバフローした場合、上述の計算方式における大小比較（ｍａｘ｛Ｆ′ｉ，ｔｉ｝、Ｆｉの最小値選択）を正確に行なうことができなくなるという課題がある。
【００１４】
また、ラップアラウンド方式で時刻を扱っていた場合でも、２(ビット長-1)以上値が異なる場合には、大小判定を正確に行なうことができなくなるという課題がある。
上記のような送出予定時刻Ｆｉと実時刻との乖離により、以下のような誤動作が発生する。すなわち、ＷＦＱアルゴリズムによる送出予定時刻Ｆｉが最小値のキューを選択するにあたり、オーバフローを起こしたキューのＦｉの値は他のキューに比べ極端に小さいことから、当該オーバフローを起こしたキューが優先的に選択され続けることになる。
【００１５】
このため、他のキューの利用帯域を圧迫し、予約帯域を保証できないキューが発生する。また、送出予定時刻Ｆｉの比較が公平に行なわれないことから、余剰帯域の公平な割り当てが行なわれない。したがって、ＷＦＱが本来意図していたような、予約帯域の保証、公平な余剰帯域配分を行なうことができないという課題があるのである。
【００１６】
以下では、前述の式（２）に示すＷＦＱ計算におけるオーバフロー要因である、送出予定時刻Ｆｉと実時刻の乖離について説明する。
送出予定時刻Ｆｉと実時刻とが乖離する第1の要因として、ＷＦＱアルゴリズムによる送出予定時刻Ｆｉの計算に関して、ビット長の制限による丸め誤差などがある。例えば、式（２）の第2項において、予約帯域ｒｉが逆数として用いられることから、除算による丸め誤差が発生する。
【００１７】
前述のように、Ｆｉの計算は前回送出パケットの送出予定時刻Ｆ′ｉの値から算出するため、ビット長の制限による丸め誤差がパケットを送出するたびに積算される。従って、送出予定時刻計算上のビット長の制限による丸め誤差は、実時刻からの乖離を引き起こす要因となるのである。
送出予定時刻Ｆｉと実時刻とが乖離する第2の要因として、ＷＦＱアルゴリズムによる計算上の出力リンク速度Ｒと実際の回線速度とが、主として以下に示す3つの要因により一致しないことである。
【００１８】
すなわち、出力リンク速度Ｒと実際の回線速度とが一致しない第1の要因として、ＷＦＱアルゴリズムによる計算において用いられるパケット長の値には、ＩＰレイヤやＡＴＭレイヤよりも下位のレイヤにて付加されるようなヘッダ長は計算に組み込まれていない場合があることが挙げられる。
つまり、ネットワークで転送するパケットには、レイヤ毎にヘッダ（ＩＰヘッダ、ＭＡＣヘッダなど）、プリアンプルなどの識別情報が付加されており、これらのヘッダ情報を含めたデータ転送量から転送速度が求まる。一方、ネットワークのユーザが指定する予約帯域は、あるレイヤ以下のヘッダのデータ量を含まないデータ転送量である場合がある。
【００１９】
このため、ＷＦＱの計算上のパケット長としては、あるレイヤ以下のヘッダ長を含めない場合がある。このように、帯域指定時にパケット情報のどの部分までを含めるか、およびＷＦＱ計算上で実パケットのどの部分までをパケット長Ｌｉに含めるかにより、計算上のデータ転送量と実転送量の不一致が発生する。
また、パケット転送装置内で必要に応じてヘッダの付加削除処理（転送メディア変換処理、ＥｔｈｅｒｎｅｔのＶＬＡＮｔａｇ処理、ＩＰｖ６のオプションヘッダ処理）などを行なう場合があり、このようなヘッダ付加削除処理を見越して予約帯域が示すレイヤでの実転送速度及びパケット長を計測することが考えられるが、これは処理負荷の増大を引き起こし、特にパケット転送の高速化を図る際には支障をきたす。このため、計算上の帯域と実効帯域とを完全に一致させることは困難である。
【００２０】
出力リンク速度Ｒと実際の回線速度とが一致しない第２の要因としては、パケット転送装置の運用上、予約帯域を保証するために、ＷＦＱ計算上のＲの値を実際の回線速度よりも小さく設定する場合があることにある。
つまり、ＷＦＱの運用では、ネットワーク回線の混み具合により、実際の出力リンク速度が計算上のＲの値よりも小さくなることが考えられる。この場合、実際の出力リンク速度がΣφｉの値よりも小さくなれば、ネットワーク回線の輻輳などに起因したスループットの低下が発生し、予約帯域を保証できないキューが発生する。
【００２１】
そこで、上述のネットワーク回線の輻輳や計算誤差なども考慮し、Ｒの値を、ネットワーク回線の混み具合によらずに（ＷＦＱ計算上のＲ）＜(実際の最大転送速度)となるような安全値に設定する必要があるのである。
さらに、出力リンク速度Ｒと実際の回線速度とが一致しない第３の要因としては、同一回線上でＷＦＱアルゴリズム以外のパケット転送アルゴリズムを帯域分割して併用している場合に、他の方式が利用されている帯域から未使用帯域が発生したとき、ＷＦＱアルゴリズムが適用されるキューからは計算上のＲの値よりも多くの帯域を利用した転送が行なわれることであり、この場合にも、出力リンク速度Ｒと実際の回線速度とは一致しない。
【００２２】
ここで、上述した第２の要因によって、ＷＦＱアルゴリズムによる計算上の出力リンク速度Ｒと実際の回線速度とが一致しないと、送出予定時刻Ｆｉと実時刻が乖離することの具体例について、以下に説明する。
まず、既にいくつかのパケットがキューに溜まっており、新たなパケットが連続的に到着している状況があると仮定する。この場合には、式（２）における計算上の第1項ｍａｘ｛Ｆ′ｉ，ｔｉ｝ではＦ′ｉの値が選択される。このとき、計算上の出力リンク速度Ｒは、実際の回線速度（転送速度）よりも小さく設定されているものとする。
【００２３】
実際の回線速度が計算上の値Ｒよりも速いため、図２１（ａ）及び図２１（ｂ）に示すように、実際の回線速度の値がＲである場合よりも多くのデータ量が送出可能となり、パケット送出(選択)回数も急速に増加する。従って、Ｆｉの値は、パケット送出回数の増加に比例して急速に増加する。即ち、実際の転送速度が計算上の値Ｒを上回る状態が続いた場合には、実際の時刻の経過に比し送出予定時刻Ｆｉの値が急速に増加することになるのである。
【００２４】
実際の転送速度が計算上の値Ｒを上回る状態が続いた場合には、このようなＦｉの急速な増加が継続するので、Ｆｉに関するｂｉｔ数の制限から桁あふれを引き起こすことになる。オーバフローしたキューのＦｉは、他のキューのＦｉとの比較において、極端に小さな値とみなされる。
このような送出予定時刻Ｆｉと実時刻との乖離により、以下のような誤動作が発生する。即ち、パケットスケジューラ１０２では、オーバフローを起こしたキューのＦｉの値が他のキューに比べ極端に小さいことから、出力すべきパケットとして優先的に選択され続けることになる。
【００２５】
このため、他のキューの利用帯域を圧迫し、予約帯域を保証できないキューが発生する。また、送出予定時刻Ｆｉの比較が公平に行なわれないことから、余剰帯域の公平な割り当てが行なわれない。したがって、ＷＦＱアルゴリズムが本来意図していたような、予約帯域の保証、公平な余剰帯域の配分を行なうことが困難となるのである。
【００２６】
本発明は、このような課題に鑑み創案されたもので、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できるようにした、パケットスケジューラを提供することを目的とする。
【００２７】
【課題を解決するための手段】
上記の目的を達成するため、本発明のパケットスケジューラは、出力保証帯域に基づく重み係数がそれぞれ設定された複数のキューにより送出待ちのパケットを管理し且つ各キューに格納された先頭パケットの送出順序を決定するとともに、各キューにおける送出待ちパケットの管理情報と前記重み係数とを用いた計算により得られた送出予定時刻情報に基づき、最優先に送出すべきパケットを格納するキューを選択制御するキュー制御手段と、現在時刻情報に基づいて、該キュー制御手段における処理を補正する補正手段と、をそなえ、該キュー制御手段が、バックログ状態の各キューにおける送出待ちパケットの管理情報と重み係数とを用いて前記バックログ状態の各キューに格納されたパケットの送出予定時刻を計算する送出予定時刻計算手段と、該送出予定時刻計算手段にて計算された各送出予定時刻情報に基づいてパケットを最優先に送出すべきキューを選択する選択手段とをそなえて構成されるとともに、該補正手段は、該送出予定時刻計算手段にて計算された該送出予定時刻情報が、該現在時刻情報よりも所定の許容値を超えて大きい場合には、該送出予定時刻計算手段による計算に前記現在時刻情報を反映させることにより、該選択手段における選択処理を補正することを特徴としており、このような構成によって、出力保証帯域を保証したパケットスケジューリングを行なう際の誤動作を減少させている。
【００２９】
さらに、補正手段を、該選択手段にて選択制御されたキューについて計算された前記の送出予定時刻情報と現在時刻情報との乖離量を検出する乖離量検出手段と、該乖離量検出手段にて検出された乖離量に基づいて該選択手段による選択処理を補正すべく指示する指示手段とをそなえて構成することもでき、さらに、指示手段を、乖離量検出手段にて検出された乖離量に基づいて、該選択手段による選択の基準となる各キューの送出予定時刻情報を補正すべく指示するように構成してもよい。
【００３０】
また、上述の本発明においては、各キューにおける送出待ちパケットの管理情報を前記現在時刻情報を含んで入力され前記の管理情報から現在時刻情報を取得する時刻情報取得手段をそなえ、補正手段を、時刻情報取得手段にて取得された現在時刻情報に基づいて、該キュー制御手段における処理を補正するように構成してもよい。
【００３１】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ１）第１実施形態の説明
図１は本発明の第１実施形態にかかるパケットスケジューラを示すブロック図であり、この図１に示すパケットスケジューラは、図２に示すパケット転送装置に適用しうるものである。ここで、図2に示すパケット転送装置は、パケット受信部１，キュー構成部２，パケットスケジューラ３及びパケット送出部４をそなえて構成され、例えば図示しないＩＰ(Internet Protocol)ネットワークや、ＡＴＭ(Asynchronous Transfer Mode)ネットワークにおけるルータとして用いることができる。
【００３２】
パケット受信部１は、ネットワークから受信したパケットの書き込みをキュー構成部２に要求するもので、キュー構成部２は、詳細には図３に示すように書き込み／読み出し制御部２１，ＦＩＦＯメモリ部２２およびキュー情報通知２３をそなえて構成される。
また、ＦＩＦＯメモリ部２２は更に、トラヒックに応じて分別してパケットを格納するためのキュー２２−１〜２２−ｎをそなえて構成されている。このキュー２２−１〜２２−ｎについても、前述の図１９に示すキュー１０２−１〜１０２−ｎと同様に、また、キュー情報通知部２３は、各キューの情報（パケットの有無、パケット到着時刻、先頭パケット長など）をパケットスケジューラ１に随時通知するものである。
【００３３】
さらに、書き込み／読み出し制御部２１は、パケット受信部１からの受信パケットをトラヒックに応じたキュー２２−ｉ（ｉ；１〜ｎのいずれかの整数）に書き込み制御するとともに、パケットスケジューラ３から受けた読み出し指示に従って、指示に対応したキュー２２−ｉの読み出し制御を行なうようになっている。また、パケットスケジューラ３は、ＩＰパケットやＡＴＭパケットなどのパケットデータについて、ＷＦＱアルゴリズムによるパケットスケジューリングを行ないうるものである。具体的には、バックログ状態にあるキュー２２−１〜２２−ｎのうちのいずれか一つのキューを選択し、選択したキューの先頭パケットの読み出しをキュー構成部２に要求するもので、詳細には後述の図１に示すように構成されている。
【００３４】
なお、上述のキュー２２−１〜２２−ｎのうちで、ＷＦＱのアルゴリズムを適用しないキューを設定することもできる。この場合においては、当該キューについては後述するＷＦＱアルゴリズムによるパケットスケジューリング処理の対象からは除外される。
パケット送出部４は、ネットワーク回線の空き状態に応じて、キュー構成部３から読み出したパケットをネットワーク回線に送出するとともに、ネットワーク回線にパケットを送出可能な場合には次に出力すべきパケットの決定(パケットスケジューリング処理)をパケットスケジューラ３に要求するものである。
【００３５】
続いて、パケットスケジューラ３の詳細な構成について、図１を用いて以下に説明する。この図1に示すパケットスケジューラ３は、キュー選択制御部（キュー制御手段）３１と乖離補正部(補正手段)３３とをそなえて構成されている。
キュー選択制御部３１は、各キュー２２−１〜２２−ｎにおける送出待ちパケットデータの管理情報と前記重み係数とを用いた計算により得られた送出予定時刻情報に基づき、パケットデータを最優先に送出すべきキューを選択するもので、例えば図１に示す送出予定時刻計算部３１−１と送出予定時刻比較部３１−２とによりその機能を実現することができる。
【００３６】
ここで、送出予定時刻計算部（送出予定時刻計算手段）３１−１は、前述の各キュー２２−１〜２２−ｎにおける送出待ちパケットデータの管理情報と重み係数とを用いて各キューに格納されたパケットデータの送出順序を決定するための基準となる送出予定時刻を計算するもので、計算結果はビットデータとして送出予定時刻比較部３１−２に出力されるようになっている。
【００３７】
具体的には、送出予定時刻計算部３１−１は、上述の管理情報としての各キュー２２−１〜２２−ｎの情報（送出待ちパケットの有無、パケット到着時刻データ、先頭パケット長データ等）をキュー情報通知部２３から入力され、これらのデータとバックログ状態のキューのトラヒックに予約された帯域に比例した重み係数とに基づいて、前述の式(１)及び式（２）に示す計算を行なうものである。すなわち、送出予定時刻計算部３１−１では、バックログ状態のキュー２２−ｉのトラヒックに予約された帯域に比例する重み係数をφｉ、先頭パケットのキュー２２−ｉへの到着時刻データをｔｉ、先頭パケット長データをＬｉ、および全てのバックログ状態のキューにおける重み係数φｉの総和をφｂとして、上述の式（１）及び式（２）の計算を行ない、バックログ状態のキューについての各送出予定時刻Ｆｉを算出できるようになっている。
【００３８】
なお、上述の各キュー２２−１〜２２−ｎのトラヒックに予約された帯域に比例した重み係数φｉの値については、パケットスケジューラ３内部の図示しないメモリ機能により記憶しておき、必要に応じて設定を変更することも可能である。また、各キュー２２−ｉについての前回送出予定時刻データＦ′ｉの値についても、パケットスケジューラ３内部のメモリ機能に記憶しておき、送出予定時刻計算部３１−１における次回の送出予定時刻計算の際には、前回送出予定時刻データＦ′ｉの値を当該メモリ機能から呼び出すことができる。
【００３９】
さらに、送出予定時刻比較部（選択手段）３１−２は、送出予定時刻計算部３１−１からの計算結果を入力され、送出予定時刻計算部３１−１にて計算された各送出予定時刻情報に基づいてパケットデータを最優先に送出すべきキューを選択するものである。
具体的には、送出予定時刻計算部３１−１にて計算されたバックログ状態のキューのパケットについての送出予定時刻データのうちで、最小の送出予定時刻データに対応するキューを、最優先にパケットデータを送出すべきキューとして選択し、選択したキューに付された(例えばビットデータで構成される)キュー番号を、選択結果としてキュー構成部２に通知するようになっている。
【００４０】
また、時刻情報生成部３２は、例えばパケットスケジューラ３の外部にそなえられ、現在時刻情報としてのカウントデータを生成するものであり、例えばパケット転送装置が有するクロック生成機能からのクロック信号に同期してカウントアップするようなカウントデータを生成するカウンタなどにより構成される。なお、この時刻情報生成部３２としては、例えばパケットスケジューラ３内部において、クロック信号からカウントデータを生成するカウンタにより構成してもよい。
【００４１】
さらに、乖離補正部３３は、現在時刻情報に基づいて、キュー選択制御部３１における処理を補正するもので、例えば図１に示す乖離検出部（乖離量検出手段）３３−１と補正指示部(指示手段)３３−２とによりその機能を実現することができる。
ここで、乖離検出部３３−１は、送出予定時刻計算部３１−１にて計算された各送出予定時刻情報と時刻情報生成部３２からの現在時刻情報との乖離量をそれぞれ検出するものである。具体的には、送出予定時刻計算部３１−１にて計算された各送出予定時刻データＦｉの、時刻情報生成部３２からの現在時刻データＴｉｍｅに乖離許容値ｋを加えた値（Ｔｉｍｅ+ｋ）に対する大小比較を行なうもので、比較判定結果を補正指示部３３−２に出力するようになっている。
【００４２】
すなわち、乖離検出部３３−１では、バックログ状態のキュー２２−ｉについてのデータＦｉと現在時刻データとの比較結果を、以下に示す式（３）を満たすか否かの判定情報として比較判定結果について補正指示部３３−２に出力するようになっている。
Ｆｉ≦Ｔｉｍｅ＋ｋ                                    …（３）
上述の式（３）に示すＴｉｍｅは、現在時刻情報としてのデータであって、ｋは、送信予定時刻データＦｉと現在時刻データとの比較において乖離が許容される上限の値を示す許容値である。従って、送信予定時刻Ｆｉが、この式（３）を満たす範囲内であれば、現在時刻データとの乖離は許容されるのである。
【００４３】
補正指示部３３−２は、乖離検出部３３−１にて検出された各乖離量に基づいて送出予定時刻比較部３１−２による選択処理を補正すべく指示するものである。具体的には、乖離検出部３３−１にて上述の式（３）を満たさないキューがあると判定された場合（即ちＴｉｍｅ＋ｋの値を超えるＦｉの値を持つキュー２２−ｉがあると判定された場合）には、当該Ｆｉの値をＴｉｍｅ＋ｋに書き換えるように、送出予定時刻計算部３１−１に指示するようになっている。
【００４４】
換言すれば、補正指示部３３−２では、送出予定時刻計算部３１−１にて計算された送出予定時刻を補正指示して、次回に計算されるＦｉが適正な値となるようにすることを通じて、送出予定時刻比較部３１−２による選択処理を間接的に補正できるようになっている。
上述の乖離補正部３３による補正処理を通じて、Ｆｉの計算値を示すビットデータが一定値以上になって桁あふれ(オーバフロー)を起こすことを防止し、後段の送出予定時刻比較部３１−２における最小値選択処理の信頼度を常に適正に保っている。
【００４５】
なお、上述の時刻情報生成部３２からの現在時刻情報は、現在時刻を判断するための一つの指標であって、比較対象のキュー２２−ｉから現実にパケットが送信される時刻とは乖離することが考えられる。しかしながら、送出予定時刻Ｆｉとの比較において、許容値としてのｋを加算した値を用いることにより、そのような乖離を吸収するだけでなく、乖離検出部３１−１では明らかにオーバフローの原因となるようなＦｉの乖離幅のみを検出することができる。
【００４６】
上述の構成による、本発明の第１実施形態にかかるパケットスケジューラが適用されたパケット転送装置の動作について、以下に詳述する。
まず、パケット転送装置のパケット受信部１では、ネットワークからパケットを受信するとともに、受信パケットについて更にネットワーク上に転送すべきパケットについての書き込み制御を、キュー構成部２の書き込み／読み出し制御部２１に対して要求する。キュー構成部２の書き込み／読み出し制御部２１では、パケットデータのＦＩＦＯメモリ部２２への書き込みを制御する際、転送すべきパケットにおけるトラヒックの予約帯域に応じて書き込むべきキュー２２−ｉを選択している。これにより、転送すべきパケットデータについては、トラヒックの予約帯域に応じたキュー２２−ｉに保持される。
【００４７】
また、パケットスケジューラ３では、上述のキュー２２−ｉに保持されているパケットデータの送出パケットとしての送出順序を、後述のＷＦＱアルゴリズムによるパケットスケジューリング処理により決定している。パケット送出部４では、パケットスケジューラ３により送出順序が決定されたパケットについて、回線の空き状態に応じて転送パケットとしてネットワークへ送出する。
【００４８】
ここで、パケット送出部４では、ネットワークへのパケットの送出ができる状態となった場合に、パケットスケジューラ３に対してスケジューリングを要求する。パケットスケジューラ３では、パケット送出部４からの要求を受けると、図４のフローチャートに示すようなＷＦＱアルゴリズムを適用したスケジューリング処理を行なって、最優先に送出すべきパケットを格納するキューを選択する。
【００４９】
まず、パケットスケジューラ３の送出予定時刻計算部３１−１において、バックログ状態にある各キュー２２−ｉについての送出予定時刻を、前述の式（１）および式（２）を用いることにより計算している（ステップＡ１，ステップＡ２〜ステップＡ５，ステップＡ７）。なお、図４中のステップＡ４，ステップＡ５における変数ｔｅｍｐは、前述の式（１）および式（２）の計算過程において用いられる一時記憶用の補助変数である。
【００５０】
また、乖離補正部３３の乖離検出部３３−１では、送出予定時刻として計算されたキュー２２−ｉ（ｉ＝１〜ｎ）ごとの送出予定時刻Ｆｉについて(ステップＡ５)、前述の式（３）による現在時刻情報との比較を行なって、計算された送出予定時刻データが許容範囲を超えて現在時刻に乖離しているか否かを判定する（ステップＡ６）。この比較判定結果は、乖離検出部３３−１から補正指示部３３−２に通知される。
【００５１】
ここで、乖離検出部３３−１では、送出予定時刻Ｆｉの値が前述の式（３）を満たしていれば、計算された送出予定時刻Ｆｉは許容範囲内にあると判定し、判定結果を補正指示部３３−２に出力する。この場合は、補正指示部３３−２では、送出予定時刻計算部３１−１にて計算されたＦｉの値を、後段の送出予定時刻比較部３１−２の処理で用いる送出予定時刻データとしてそのまま出力する(ステップＡ６のＹＥＳルート)。
【００５２】
一方、乖離検出部３３−１では、前述の式（３）を満たさないならば、計算された送出予定時刻Ｆｉは許容範囲を超えて現在時刻に乖離していると判定し、判定結果を補正指示部３３−２に通知する。補正指示部３３−２では、乖離検出部３３−１からの判定結果に基づいて、当該Ｆｉの値を乖離許容範囲内のＴｉｍｅ＋ｋに書き換えることで補正する（ステップＡ６のＮＯルートからステップＡ８）。
【００５３】
このような処理により、キュー２２−１〜２２−ｎのうちで、バックログ状態にあるものについては、順次計算された送出予定時刻データが現在時刻データに基づいて許容値の範囲に収まるように補正され、後段の送出予定時刻比較部３１−２に出力される（ステップＡ２のＮＯルートからステップＡ３〜ステップＡ７）。
【００５４】
送出予定時刻比較部３１−２は、送出予定時刻計算部３１−１からの、バックログ状態の各キューについての必要な補正が施された送出予定時刻データを入力され、各送出予定時刻データのうちで最小値の送出予定時刻データを持つキューを選択する（ステップＡ９〜ステップＡ１３）。
送出予定時刻比較部３１−２では、最小値の送出予定時刻データ（例えばキュー２２−ｉにおけるＦｉ）が選択されると、当該Ｆｉの値をキュー２２−ｉの前回送出予定時刻Ｆ′ｉとして次回の送信予定時刻計算のために図示しないメモリ機能に記憶して（ステップＡ１４）、キュー構成部２の書き込み／読み出し制御部２１に対して、選択されたＦｉに対応するキュー２２−ｉの番号を通知する。これにより、書き込み／読み出し制御部２１におけるキュー２２−ｉの読み出し制御を指示している（ステップＡ１５）。
【００５５】
このようにして、パケットスケジューラ３によるスケジューリング処理により送出すべきパケットの読み出し指示が出力されると、選択されたキュー２２−ｉの先頭パケットが読み出されて、パケット送出部４を通じて回線に出力される。
このように、本発明の第１実施形態にかかるパケットスケジューラ３によれば、乖離補正部３３により、現在時刻情報に基づきキュー選択制御部３１における処理を補正することができるので、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点がある。
【００５６】
また、乖離補正部３３が、送出予定時刻計算部３１−１による計算結果としての各送出予定時刻情報と現在時刻情報との乖離を許容範囲内に収める補正を行なうことを通じて送出予定時刻計算部３１−１の計算に現在時刻情報を反映させることにより、送出予定時刻比較部３１−２における選択処理を補正することで、ＷＦＱ計算上の演算誤差を確実に補正された値を用いて送出予定時刻比較部３１−２における選択処理を行なうことができるので、送出予定時刻の計算値を示すビットデータを桁あふれ(オーバフロー)させることを防止して、送出予定時刻比較部３１−２における選択処理の信頼度、ひいてはパケットスケジューラやパケット転送装置の性能ないし信頼度を向上させることができる利点がある。
【００５７】
（ａ２）第１実施形態の第１変形例の説明
上述の第１実施形態においては、乖離補正部３３の乖離検出部３３−１において送出予定時刻データの現在時刻との乖離幅を判定するに際しては、時刻情報生成部３２にて生成された現在時刻情報としてのカウントデータを用いているが、これに限定されず、例えば図５に示すパケットスケジューラ３−１のように、キュー情報通知部２３からのキュー管理情報から抽出された現在時刻情報を用いるように構成してもよい。
【００５８】
ここで、この図５に示すパケットスケジューラ３−１は、前述の図１に示すもの(符号３参照)に比して、時刻情報生成部３２の代わりに、キュー情報通知部２３からのキュー管理情報から現在時刻情報を抽出し取得する時刻情報取得部３２Ａをそなえている点が異なり、その他の構成については、図１に示すパケットスケジューラ３と基本的に同様である。なお、図５中で図１と同一の符号は、ほぼ同様の部分を示している。
【００５９】
すなわち、時刻情報取得部３２Ａは、キュー情報通知部２３から通知されるキュー管理情報からパケット到着時刻に関する情報を抽出し取得するもので、取得したパケット到着時刻情報を現在時刻情報として乖離検出部３３−１に出力するようになっている。
例えば、キュー情報通知部２３からキュー２２−ｉについての管理情報が通知された場合には、この管理情報からパケット到着時刻情報ｔｉ（キュー２２−ｉに最新パケットが到着した時刻情報）を抽出し取得して、この到着時刻情報ｔｉを現在時刻情報として乖離検出部３３−１へ出力するようになっている。即ち、乖離検出部３３−１では、時刻情報取得部３２Ａからの到着時刻情報ｔｉを、キュー２２−ｉについて計算された送出予定時刻について乖離幅を判定する際の基準となる現在時刻情報として用いることができるようになっている。
【００６０】
具体的には、乖離検出部３３−１では、送出予定時刻計算部３１−１にて計算された送出予定時刻データ(例えばキュー２２−ｉについて計算されたデータＦｉ)と、時刻情報取得部３２Ａからの現在時刻データとしての到着時刻データｔｉとを入力されて、このＦｉとｔｉ＋ｋ（ｔｉに対して乖離が許容される値で、予め設定されたもの）との大小を比較して、比較判定結果を補正指示部３３−２に出力するようになっている。
【００６１】
換言すれば、乖離検出部３３−１では、キュー２２−ｉについての前回送出予定時刻データＦ′ｉと現在時刻データＴｉｍｅ+ｋとの比較結果を、以下に示す式（３−１）を満たすか否かの判定情報として比較判定結果について補正指示部３３−２に出力するようになっている。
Ｆｉ≦ｔｉ＋ｋ                                          …（３−１）
補正指示部３３−２は、乖離検出部３３−１にて検出された各乖離量に基づいてキュー選択制御部３１による選択処理を補正すべく指示するものである。具体的には、乖離検出部３３−１にて上述の式（３−１）を満たさないキューがあると判定された場合（即ちＴｉｍｅ＋ｋの値を超えるＦ′ｉの値を持つキュー２２−ｉがあると判定された場合）には、当該Ｆ′ｉの値をＴｉｍｅ＋ｋに書き換えるように、送出予定時刻計算部３１−１に指示するようになっている。
【００６２】
なお、上述の時刻情報抽出部３２Ａからの現在時刻情報についても、前述の第１実施形態における時刻情報生成部３２と同様に、現在時刻を判断するための一つの指標であって、通常、比較対象のキュー２２−ｉから現実にパケットが送信される時刻とは乖離する。しかしながら、送出予定時刻Ｆｉとの比較において、許容値としてのｋを加算した値を用いることにより、そのような乖離を吸収するだけでなく、乖離検出部３１−１では明らかにオーバフローの原因となるようなＦｉの乖離幅のみを検出することができるのである。
【００６３】
上述の構成により、本発明の第１実施形態の第１変形例にかかるパケットスケジューラ３−１では、図６のフローチャートに示すように、乖離補正部３３−１における乖離補正処理を行なう際に、現在時刻取得部３２Ａにて取得された到着時刻データを現在時刻データとして用いている点以外は、基本的に前述の第１実施形態の場合と同様に動作する。なお、図６中で図４と同一の符号が付された処理ステップでは、ほぼ同様の動作が行なわれる。以下においては、前述の図４の場合と異なる点に着目して動作を説明する。
【００６４】
すなわち、乖離補正部３３−１の乖離検出部３３−１では、キュー２２−１〜２２−ｎのうちで、バックログ状態にあるキューについて算出された送出予定時刻データ（例えばキュー２２−ｉにおけるデータＦｉ）が、時刻情報取得部３２Ａにて取得された現在時刻情報から許容された乖離幅にあるか否かを検出する(ステップＡ６−１)。
【００６５】
具体的には、乖離検出部３３−１では、Ｆｉの値とｔｉ＋ｋとの大小比較を行なって、前述の式（３−１）を満たす場合には許容された乖離幅にあることを検出する一方、式（３−１）を満たさない場合には許容された乖離幅に無いことを検出する。なお、検出結果については補正指示部３３−２に通知される。
補正指示部３３−２では、Ｆｉの値とｔｉ＋ｋとの大小比較を行なった結果、前述の式（３−１）を満たす場合には当該Ｆｉの値を補正せずに後段の送出予定時刻比較部３１−２へ出力する旨を送出予定時刻計算部３１−１へ指示する一方（ステップＡ６−１のＹＥＳルート）、式（３−１）を満たさない場合には当該Ｆｉの値を乖離許容範囲内の値ｔｉ＋ｋに書き換えるべく、送出予定時刻計算部３１−１へ補正指示する（ステップＡ６−１のＮＯルートからステップＡ８−１）。
【００６６】
送出予定時刻比較部３１−２では、補正指示部３３−２からの補正指示に基づいて必要な補正が施された送出予定時刻データについて比較することを通じ、パケットを送出すべきキューを選択しているので、送出予定時刻が実時刻に乖離することを抑制し、オ−バフローの原因を解消している。
したがって、第１実施形態の第１変形例にかかるパケットスケジューラ３−１においても、乖離補正部３３により、現在時刻情報に基づきキュー選択制御部３１における処理を補正することができるので、前述の第１実施形態の場合と同様の利点があるほか、現在時刻取得部３２Ａにより、送出待ちパケットデータからの管理情報を、現在時刻情報を取得するために流用することができるので、時刻情報生成のための専用の機能部を持つ必要がなくなり、装置構成の簡素化を図ることもできる。
【００６７】
（ａ３）第１実施形態の第２変形例の説明
上述の第１実施形態においては、乖離補正部３３が、送出予定時刻計算部３１−１からの計算結果としての各送出予定時刻データ（例えばキュー２２−ｉにおけるデータＦｉ）を用いて現在時刻との乖離幅を判定しているが、これに限定されず、例えば図７に示すパケットスケジューラ３−２のように、各送出予定時刻データを算出する際の中間パラメータを用いて現在時刻との乖離幅を検出するように構成することもできる。
【００６８】
すなわち、この図７に示すパケットスケジューラ３−２は、前述の図１に示すパケットスケジューラ(符号３参照)に比して、乖離補正部３３Ａが、送出予定時刻計算部３１Ａ−１による計算結果ではなく計算過程の中間パラメータの値に、時刻情報生成部３２からの現在時刻情報を反映させることにより、キュー選択制御部３１Ａの送出予定時刻比較部３１−２における選択処理を補正するようになっている点が異なり、その他の構成についてはほぼ共通する。
【００６９】
すなわち、乖離補正部３３Ａの乖離検出部３３Ａ−１は、送出予定時刻計算部３１Ａ−１における計算で用いられる中間パラメータとしての前回パケット送出時に計算された送出予定時刻情報と、時刻情報生成部３２からの現在時刻情報との乖離量をそれぞれ検出するものである。
具体的には、乖離検出部３３Ａ−１は、キュー２２−ｉにおいて前回パケットを送出した際に計算された送出予定時刻データＦ′ｉと、時刻情報生成部３２からの現在時刻データＴｉｍｅに乖離許容値ｋを加えた値（Ｔｉｍｅ+ｋ）との大小比較を行なって、比較判定結果を乖離補正部３３Ａの補正指示部３３Ａ−２に出力するようになっている。
【００７０】
換言すれば、乖離検出部３３Ａ−１では、キュー２２−ｉについての前回送出予定時刻データＦ′ｉと現在時刻データＴｉｍｅ+ｋとの比較結果を、以下に示す式（３−２）を満たすか否かの判定情報として比較判定結果について補正指示部３３Ａ−２に出力するようになっている。
Ｆ′ｉ≦Ｔｉｍｅ＋ｋ                                  …（３−２）
これにより、補正指示部３３Ａ−２は、乖離検出部３３Ａ−１にて上述の式（３−１）を満たさないキューがあると判定された場合（即ちＴｉｍｅ＋ｋの値を超えるＦ′ｉの値を持つキュー２２−ｉがあると判定された場合）には、当該Ｆ′ｉの値をＴｉｍｅ＋ｋに書き換えるように、送出予定時刻計算部３１Ａ−１に指示するようになっている。
【００７１】
上述の構成による、本発明の第１実施形態の第２変形例にかかるパケットスケジューラ３−２においても、乖離補正部３３Ａにおける乖離補正処理以外については、基本的に前述の第１実施形態の場合と同様に動作する。
すなわち、図８のフローチャートに示すように、乖離補正部３３Ａ−１の乖離検出部３３Ａ−１において、キュー２２−１〜２２−ｎのうちでバックログ状態にあるキューについて送出予定時刻データ（例えばキュー２２−ｉにおけるデータＦｉ）を算出する前段において、この送出予定時刻データを算出するための中間パラメータＦ′ｉの値の現在時刻データに対する乖離幅が許容範囲内にあるか否かを判定する。
【００７２】
換言すれば、乖離補正部３３Ａの乖離検出部３３Ａ−１では、中間パラメータとしての前回パケット送出時の送出予定時刻データを送出予定時刻計算部３１Ａ−１から入力され、この中間パラメータの値の現在時刻データに対する乖離幅が許容範囲内にあるか否かを判定する。
例えば、乖離検出部３３Ａ−１では、キュー２２−ｉの送出予定時刻データを計算する前段において、前回パケット送出時に計算された送出予定時刻データＦ′ｉとＴｉｍｅ＋ｋとの大小比較を行なって、Ｆ′ｉの値が許容範囲を超えて現在時刻に乖離しているか否かを判定し（ステップＡ６−２）、判定結果を補正指示部３３Ａ−２に通知する。
【００７３】
ここで、補正指示部３３Ａ−２では、Ｆ′ｉの値とＴｉｍｅ＋ｋとの大小比較の結果、前述の式（３−２）を満たす場合には、当該Ｆ′ｉの値をキュー２２−ｉの送出予定時刻の計算に用いるパラメータとして用いる旨を送出予定時刻計算部３１Ａ−１に通知し、補正指示は行なわない（ステップＡ６−２のＹＥＳルートからステップＡ４）。
【００７４】
一方、補正指示部３３Ａ−２では、Ｆ′ｉの値とＴｉｍｅ＋ｋとの大小比較の結果、前述の式（３−２）を満たさない場合には、当該Ｆ′ｉの値を乖離許容範囲内の値Ｔｉｍｅ＋ｋに書き換えるように、送信予定時刻計算部３１Ａ−１に対して補正指示を行なう（ステップＡ６−２のＮＯルートからステップＡ８−２）。
【００７５】
送出予定時刻計算部３１Ａ−１では、補正指示部３３Ａ−２からの補正指示により必要な補正が施されたＦ′ｉの値をパラメータとして、送信予定時刻Ｆｉを計算することにより、オ−バフローの原因を解消している。
したがって、第１実施形態の第２変形例にかかるパケットスケジューラ３−２においても、乖離補正部３３Ａにより、現在時刻情報に基づきキュー選択制御部３１Ａにおける処理を補正することができるので、前述の第１実施形態の場合と同様の利点がある。
【００７６】
また、乖離補正部３３Ａが、送出予定時刻計算部３１Ａ−１における各計算過程の中間パラメータと現在時刻情報との乖離を許容範囲内に収める補正を行なうことを通じて送出予定時刻計算部３１Ａ−１の計算に現在時刻情報を反映させることにより、送出予定時刻比較部３１−２における選択処理を補正して、ＷＦＱ計算上の演算誤差を確実に補正された値を用いて送出予定時刻比較部３１−２における選択処理を行なうことができるので、送出予定時刻の計算値を示すビットデータの桁あふれ(オーバフロー)を防止して、送出予定時刻比較部３１−２における選択処理の信頼度、ひいてはパケットスケジューラの性能ないし信頼度を向上させることができる利点がある。
【００７７】
（ａ４）第１実施形態の第３変形例の説明
図９は本発明の第１実施形態の第３変形例にかかるパケットスケジューラ３−３を示すブロック図であり、この図９に示すパケットスケジューラ３−３は、前述の第１実施形態の第１変形例におけるもの(符号３−１参照)と第１実施形態の第２変形例におけるもの（符号３−２参照）とを組み合わせたものである。
【００７８】
すなわち、第１実施形態の第３変形例にかかるパケットスケジューラ３−３は、前述の第１実施形態におけるもの（符号３参照）に比して、時刻情報生成部３２の代わりに、キュー情報通知部２３からのキュー管理情報から現在時刻情報を抽出し取得する時刻情報取得部３２Ａをそなえる点が異なるほか、乖離補正部３３Ａが、送出予定時刻計算部３１Ａ−１からの計算結果ではなく計算過程の中間パラメータの値に時刻情報生成部３２からの現在時刻情報を反映させることにより、選択手段としての送出予定時刻比較部３１−２における選択処理を補正するようになっている点が異なり、その他の構成についてはほぼ共通する。
【００７９】
具体的には、乖離検出部３３Ａ−１は、キュー２２−ｉにおいて前回パケットを送出した際に計算された送出予定時刻データＦ′ｉと、時刻情報取得部３２Ａからの現在時刻データｔｉに乖離許容値ｋを加えた値（ｔｉ+ｋ）との大小比較を行なって、比較判定結果を乖離補正部３３Ａの補正指示部３３Ａ−２に出力するようになっている。
【００８０】
換言すれば、乖離検出部３３Ａ−１では、キュー２２−ｉについての前回送出予定時刻データＦ′ｉと現在時刻データｔｉ+ｋとについて、以下に示す式（３−３）を満たすか否かを判定することで比較し、比較判定結果については補正指示部３３Ａ−２に出力するようになっている。
Ｆ′ｉ≦ｔｉ＋ｋ                                    …（３−３）
なお、図９中で、図５および図７と同一の符号は、ほぼ同様のものを示す。
【００８１】
このような構成による、本発明の第１実施形態の第３変形例にかかるパケットスケジューラ３−３においても、乖離検出部３３Ａ−１における乖離補正処理を行なう際に、現在時刻取得部３２Ａにて取得された到着時刻データを現在時刻データとして用いている点と、乖離検出部３３Ａにおける現在時刻データとの比較対象として、送出予定時刻の計算過程の中間パラメータを用いる点以外については、基本的に前述の第１実施形態の場合と同様に動作する。
【００８２】
すなわち、図１０のフローチャートに示すように、乖離補正部３３Ａ−１の乖離検出部３３Ａ−１において、キュー２２−１〜２２−ｎのうちでバックログ状態にあるキューについて送出予定時刻データ（例えばキュー２２−ｉにおけるデータＦｉ）を算出する前段において、この送出予定時刻データを算出するための中間パラメータＦ′ｉの値の現在時刻データに対する乖離幅が許容範囲内にあるか否かを判定する(ステップＡ６−３)。
【００８３】
換言すれば、乖離補正部３３Ａの乖離検出部３３Ａ−１では、中間パラメータとしての前回パケット送出時の送出予定時刻データを送出予定時刻計算部３１Ａ−１から入力される一方、時刻情報取得部３２Ａから現在時刻データとしてのパケット到着時刻データを入力され、この中間パラメータの値の現在時刻データに対する乖離幅が許容範囲内にあるか否かを判定する。
【００８４】
例えば、乖離検出部３３Ａ−１では、キュー２２−ｉの送出予定時刻データを計算する前段において、前回パケット送出時に計算された送出予定時刻データＦ′ｉとｔｉ＋ｋとの大小比較を行なって、Ｆ′ｉの値が許容範囲を超えて現在時刻に乖離しているか否かを判定し（ステップＡ６−３）、判定結果を補正指示部３３Ａ−２に通知する。
【００８５】
ここで、補正指示部３３Ａ−２では、Ｆ′ｉの値とｔｉ＋ｋとの大小比較の結果、前述の式（３−３）を満たす場合には、当該Ｆ′ｉの値をキュー２２−ｉの送出予定時刻の計算に用いるパラメータとして用いる旨を送出予定時刻計算部３１Ａ−１に通知し、補正指示は行なわない（ステップＡ６−３のＹＥＳルートからステップＡ４）。
【００８６】
一方、補正指示部３３Ａ−２では、Ｆ′ｉの値とｔｉ＋ｋとの大小比較の結果、前述の式（３−３）を満たさない場合には、当該Ｆ′ｉの値を乖離許容範囲内の値ｔｉ＋ｋに書き換えるように、送信予定時刻計算部３１Ａ−１に対して補正指示を行なう（ステップＡ６−３のＮＯルートからステップＡ８−３）。
送出予定時刻計算部３１Ａ−１では、補正指示部３３Ａ−２からの補正指示により必要な補正が施されたＦ′ｉの値をパラメータとして、送信予定時刻Ｆｉを計算することにより、オ−バフローの原因を解消している。
【００８７】
したがって、第１実施形態の第３変形例にかかるパケットスケジューラ３−３においても、乖離補正部３３Ａにより、現在時刻情報に基づきキュー選択制御部３１Ａにおける処理を補正することができるので、前述の第１実施形態の場合と同様の利点があるほか、現在時刻取得部３２Ａにより、回路構成の簡素化を図ることもできる。
【００８８】
また、乖離補正部３３Ａが、送出予定時刻計算部３１Ａ−１による計算結果としての各送出予定時刻情報と現在時刻情報との乖離を許容範囲内に収める補正を行なうことを通じて送出予定時刻計算部３１Ａ−１の計算に現在時刻情報を反映させることにより、送出予定時刻比較部３１−２における選択処理を補正することで、ＷＦＱ計算上の演算誤差を確実に補正された値を用いて送出予定時刻比較部３１−２における選択処理を行なうことができるので、前述の第１実施形態の第２変形例の場合と同様の効果を得ることもできる。
【００８９】
（ｂ１）第２実施形態の説明
図１１は本発明の第2実施形態にかかるパケットスケジューラ３Ｂを示すブロック図であり、この図１１に示すパケットスケジューラ３Ｂにおいても、前述の第1実施形態におけるもの(符号3参照)と同様に、図２に示すパケット転送装置に適用されて、キュー２２−１〜２２−ｎにて保持されているパケットデータをＷＦＱアルゴリズムに基づいてスケジューリングを行なうことができるようになっている。
【００９０】
なお、第２実施形態の場合においても、上述のキュー２２−１〜２２−ｎのうちで、ＷＦＱのアルゴリズムを適用しないキューを設定することもできる。この場合においては、当該キューについては後述するＷＦＱアルゴリズムによるパケットスケジューリング処理の対象からは除外される。
さて、第２実施形態にかかるパケットスケジューラ３Ｂにおいても、前述の第１実施形態におけるパケットスケジューラ３に比して、乖離補正部３３Ｂにおいて現在時刻情報との乖離を補正する対象となる送出予定時刻情報が異なっており、その他の構成についてはほぼ共通している。なお、図１１中で図１と同一の符号は、ほぼ同様の部分を示している。
【００９１】
すなわち、乖離補正部（補正手段）３３Ｂは、乖離検出部（乖離検出手段）３３Ｂ−１と補正指示部（指示手段）３３Ｂ−２とをそなえて構成され、キュー選択制御部(キュー選択手段)３１Ｂは、送出予定時刻計算部（送出予定時刻計算手段）３１Ｂ−１と送出予定時刻比較部（選択手段）３１Ｂ−２とをそなえて構成されている。
【００９２】
ここで、乖離検出部３３Ｂ−１は、キュー選択制御部３１Ｂにて選択制御されたキューについて計算された送出予定時刻情報と現在時刻情報との乖離量を検出するものであり、補正指示部３３Ｂ−２は、乖離検出部３３Ｂ−１にて検出された乖離量に基づいて送出予定時刻比較部３１Ｂ−１による選択処理を補正すべく指示するものである。
【００９３】
この点、前述の第１実施形態にかかるパケットスケジューラ３(図１参照)の乖離補正部３１では、送出予定時刻計算部３１−１にて計算されたバックログ状態の各キューの送出予定時刻情報の全てについて必要な補正を施すための処理を行なっているのに対し、第２実施形態にかかるパケットスケジューラ３Ｂでは、キュー選択制御部３１Ｂにて選択制御されたキューについて計算された送出予定時刻情報のみについて必要な補正を施すための処理を行なっている。
【００９４】
例えば、送出予定時刻比較部３１Ｂ−２において、送出予定時刻計算部３１Ｂ−１からの、バックログ状態のキューごとに計算された送出予定時刻データを比較した結果、最小値の送出予定時刻データを有するキュー２２−ｉが選択された場合には、乖離検出部３３Ｂ−１では、このキュー２２−ｉについて計算された送出予定時刻データＦｉの現在時刻データに対する乖離を検出するようになっている。
【００９５】
具体的には、最小値の送出予定時刻データＭｉｎＦと、時刻情報生成部３２からの現在時刻データＴｉｍｅに乖離許容値ｋを加えた値（Ｔｉｍｅ+ｋ）との大小比較を行なって、比較判定結果を乖離補正部３３Ｂの補正指示部３３Ｂ−２に出力するようになっている。
換言すれば、乖離検出部３３Ｂ−１では、最小値の送出予定時刻データＭｉｎＦ（選択されたキュー２２−ｉについての送出予定時刻データＦｉ）と現在時刻データＴｉｍｅ+ｋとの比較結果を、以下に示す式（３Ｂ）を満たすか否かを判定し、比較判定結果について補正指示部３３Ａ−２に出力するようになっている。
【００９６】
ＭｉｎＦ≦Ｔｉｍｅ＋ｋ                                …（３Ｂ）
乖離検出部３３Ｂ−１にて上述の式（３Ｂ）を満たさないキューがあると判定された場合（即ちＴｉｍｅ＋ｋの値を超えると判定された場合）には、補正指示部３３Ｂ−２からの指示に基づいて、送出予定時刻比較部３１Ｂ−２では、ＷＦＱアルゴリズムによるキューからのパケットの読み出し指示を行なわず、他のアルゴリズムによるパケット転送制御がなされるキューがあれば、当該キューからのパケットの読み出し指示を行なう。
【００９７】
換言すれば、補正指示部３３−２では、送出予定時刻比較部３１Ｂ−２にて選択される最小値の送出予定時刻データが、現在時刻情報に対して許容範囲ｋの範囲内に乖離が収まるまで、ＷＦＱアルゴリズムが適用されるキューからのパケットの読み出しの停止を指示することを通じて、送出予定時刻比較部３１−２による選択処理を間接的に補正できるようになっている。
【００９８】
上述の乖離補正部３３による補正処理を通じて、Ｆｉの計算値を示すビットデータが一定値以上になって桁あふれ(オーバフロー)を起こすことを防止し、後段の送出予定時刻比較部３１−２における最小値選択処理の信頼度を常に適正に保っている。
上述の構成により、本発明の第２実施形態にかかるパケットスケジューラ３Ｂを前述の図２に示すパケット転送装置に適用した場合にも、基本的に第１実施形態の場合と同様にＷＦＱアルゴリズムによるパケット転送処理が行なわれる。そこで、第２実施形態のパケットスケジューラ３Ｂ特有の送出予定時刻データの補正手法に着目した動作について、図１２のフローチャートを用いて以下に説明する。
【００９９】
すなわち、図１２のフローチャートに示すように、パケットスケジューラ３の送出予定時刻計算部３１Ｂ−１では、バックログ状態にある各キュー２２−ｉ（ｉ＝１〜ｎ）についての送出予定時刻を、前述の式（１）および式（２）を用いることにより計算している（ステップＢ１〜ステップＢ６）。なお、図４中のステップＢ４、ステップＢ５における変数ｔｅｍｐは、前述の式（１）および式（２）の計算過程において用いられる一時記憶用の補助変数である。
【０１００】
送出予定時刻比較部３１−２では、バックログ状態の各キューについての送出予定時刻データを、送出予定時刻計算部３１−１から入力され、各送出予定時刻データのうちで最小値の送出予定時刻データＭｉｎＦを持つキュー（例えばキュー２２−ｉの送出予定時刻データＦｉ）を選択する（ステップＢ７〜ステップＢ１１）。
【０１０１】
また、乖離補正部３３Ｂの乖離検出部３３Ｂ−１では、送出予定時刻比較部３１−２にて最小値が選択された送出予定時刻データＭｉｎＦについて、前述の式（３Ｂ）による現在時刻情報との比較を行なって、計算された送出予定時刻データが許容範囲を超えて現在時刻に乖離しているか否かを判定する（ステップＢ１２）。この比較判定結果は、乖離検出部３３Ｂ−１から補正指示部３３−２に通知される。
【０１０２】
ここで、乖離検出部３３Ｂ−１では、ＭｉｎＦの値が前述の式（３Ｂ）を満たしていれば(ステップＢ１２のＹＥＳルート)、当該送出予定時刻データＭｉｎＦは許容範囲内にあると判定し、判定結果を補正指示部３３Ｂ−２に出力する。この場合は、補正指示部３３Ｂ−２では、送出予定時刻比較部３１Ｂ−２に対して補正を行なわない旨を指示する。
【０１０３】
補正指示部３３Ｂ′−２から上述の指示を受けると、送出予定時刻比較部３１Ｂ−２では、補正指示部３３Ｂ−２からの指示に基づいて、当該ＭｉｎＦ（＝Ｆｉ）の値をキュー２２−ｉの前回送出予定時刻Ｆ′ｉとして次回の送信予定時刻計算のために図示しないメモリ機能に記憶させる（ステップＢ１３）。
その後、選択されたキュー２２−ｉの識別番号をキュー構成部２に通知することにより、当該キュー２２−ｉに格納されているパケットデータを読み出し指示をキュー構成部２の書き込み／読み出し制御部２１(図３参照)に対して出力する(ステップＢ１４)。
【０１０４】
このようにして、パケットスケジューラ３Ｂによるスケジューリング処理により送出すべきパケットの読み出し指示が出力されると、選択されたキュー２２−ｉの先頭パケットが読み出されて、パケット送出部４を通じて回線に出力されることになる。
一方、乖離検出部３３−１において、前述の式（３Ｂ）を満たさないならば(ステップＢ１２のＮＯルート)、計算された送出予定時刻Ｆｉは許容範囲を超えて現在時刻に乖離していると判定し、判定結果を補正指示部３３−２に通知する。補正指示部３３−２では、乖離検出部３３−１からの判定結果に基づいて、ＷＦＱアルゴリズムが適用されたキュー以外のキューがバックログ状態にあれば、当該キューからパケットデータを読み出すべき旨を送出予定時刻比較部３３Ｂ−２に指示する(ステップＢ１５)。
【０１０５】
これにより、送出予定時刻比較部３３Ｂ−２では、ＷＦＱアルゴリズム以外のアルゴリズムで読み出し制御がなされるキューからのパケットデータの読み出し指示を、書き込み／読み出し制御部２１に対して出力する。従って、選択された送出予定時刻データが現在時刻に許容範囲を超えて乖離している場合には、当該キューからのパケット送出を停止して、ＷＦＱアルゴリズムによるキューで確保された空き帯域を他のアルゴリズムにより転送制御されるパケットに振り分けている。
【０１０６】
すなわち、ＷＦＱアルゴリズムが適用されるキューからのパケットの読み出しを停止することで、式(１),(２)により計算される送出予定時刻データが増加(インクリメント)することもなくなるので、現在時刻データとの乖離幅を狭めることができるのである。
このように、本発明の第２実施形態にかかるパケットスケジューラ３Ｂによれば、乖離補正部３３Ｂにより、現在時刻情報に基づきキュー選択制御部３１Ｂにおける選択処理を停止することを通じて補正することができるので、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点がある。
【０１０７】
すなわち、補正指示部３３Ｂ−２が、乖離検出部３３Ｂ−１にて検出された乖離量に基づいて、キュー選択制御部３１Ｂの送出予定時刻比較部３１Ｂ−２による選択処理を停止することにより、最小値の送出予定時刻データの現在時刻データに対する乖離が許容範囲ｋ内に収まるまでＷＦＱアルゴリズムが適用されたキューからのパケットの読み出しの停止、すなわち計算される送出予定時刻データの増加を停止させることができるので、送出予定時刻が実時刻と乖離することを防止することができる。
【０１０８】
(ｂ２)第２実施形態の第１変形例の説明
図１３は本発明の第２実施形態の第１変形例にかかるパケットスケジューラ３Ｂ′を示すブロック図であり、この図１３に示すパケットスケジューラ３Ｂ′は、上述のごとき第２実施形態のパケットスケジューラ３Ｂとは異なり、選択されなかったキューを含むＷＦＱアルゴリズムが適用される全てのキューについての送出予定時刻データを補正するとともに、送出予定時刻比較部３１Ｂ′−２にて選択されたキューに格納されているパケットデータの読み出し指示を行なうようになっている。
【０１０９】
すなわち、乖離補正部３３Ｂ′の補正指示部３３Ｂ′−２は、乖離検出部３３Ｂ−１にて検出された乖離量に基づいて、送出予定時刻比較部３１Ｂ′−２による選択の基準となる各キューの送出予定時刻情報を補正すべく指示するように構成されている。
具体的には、乖離検出部３３Ｂ−１において、最小値の送出予定時刻データＦｉが時刻情報生成部３２からの現在時刻データＴｉｍｅに対して許容範囲ｋを超えて乖離していると判定された場合には、補正指示部３３Ｂ′−２では、送出予定時刻比較部３１Ｂ′−２に対して補正指示を出力する。この補正指示により、送出予定比較部３１Ｂ′−２では、ＷＦＱアルゴリズムが適用された全てのキューについての送出予定時刻データを乖離上限値のＴｉｍｅ＋ｋに書き換える。
なお、送出予定時刻比較部３１Ｂ′−２では、先行して選択された最小値の送出予定時刻データを有するキューの識別番号をキュー構成部２に通知することにより、当該キューに格納されている先頭パケットデータの読み出し指示を行なうようになっている。
【０１１０】
上述の構成により、第２実施形態の第１変形例にかかるパケットスケジューラ３Ｂ′では、補正指示部３３Ｂ′−２において、選択されなかったキューを含むＷＦＱアルゴリズムが適用される全てのキューについての送出予定時刻データを補正すべく指示するとともに、送出予定時刻比較部３１Ｂ′−２では、先行して選択されたキューに格納されているパケットデータの読み出し指示を行なう点が前述の第２実施形態の場合と異なり、その他の動作についてはほぼ共通する。
【０１１１】
すなわち、図１４のフローチャートに示すように、乖離検出部３３Ｂ−１では、送出予定時刻比較部３３Ｂ′−２にて先行して選択されているＭｉｎＦの値が前述の式（３Ｂ）を満たしていると判定された場合には(ステップＢ１２のＹＥＳルート)、補正指示部３３Ｂ′−２では、送出予定時刻比較部３１Ｂ−２に対して補正を行なわない旨を指示する。
【０１１２】
補正指示部３３Ｂ′−２から上述の指示を受けると、送出予定時刻比較部３１Ｂ′−２では、補正指示部３３Ｂ−２からの指示に基づいて、当該ＭｉｎＦ（＝Ｆｉ）の値をキュー２２−ｉの前回送出予定時刻Ｆ′ｉとして次回の送信予定時刻計算のために図示しないメモリ機能に記憶させる（ステップＢ１３）。その後、選択されたキュー２２−ｉの識別番号をキュー構成部２に通知することにより、当該キュー２２−ｉに格納されているパケットデータの読み出し指示をキュー構成部２の書き込み／読み出し制御部２１(図３参照)に出力する(ステップＢ１４)。
【０１１３】
一方、乖離検出部３３Ｂ−１において、前述の式（３Ｂ）を満たさないと判定されたならば(ステップＢ１２のＮＯルート)、補正指示部３３−２では、選択されなかったキューを含むＷＦＱアルゴリズムが適用される全てのキューについての送出予定時刻データを乖離上限値のＴｉｍｅ＋ｋに補正すべく指示する (ステップＢ１６〜Ｂ１９)。
【０１１４】
上述の補正指示に基づいて、送出予定時刻比較部３１Ｂ′−２にて送出予定時刻が補正され、補正された各送出予定時刻データが例えば図示しないメモリ機能に格納された後は、送出予定時刻比較部３１Ｂ′−２では、補正指示部３３Ｂ−２からの指示に基づいて、当該ＭｉｎＦ（＝Ｆｉ）の値をキュー２２−ｉの前回送出予定時刻Ｆ′ｉとして次回の送信予定時刻計算のために図示しないメモリ機能に記憶させる（ステップＢ１３）。
【０１１５】
その後、送出予定時刻比較部３１Ｂ′−２にて先行して選択されたキュー２２−ｉの識別番号をキュー構成部２に通知することにより、当該キュー２２−ｉに格納されている先頭パケットデータの読み出し指示をキュー構成部２の書き込み／読み出し制御部２１(図３参照)に出力する(ステップＢ１４)。
このように、第２実施形態の第１変形例にかかるパケットスケジューラ３Ｂ′においても、乖離補正部３３Ｂ′により、現在時刻情報に基づき全てのＷＦＱアルゴリズムが適用されたキューの送出予定時刻について補正することができるので、前述の第１実施形態の場合と同様、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点がある。
【０１１６】
(ｂ３)第２実施形態の第２変形例の説明
図１５は本発明の第２実施形態の第２変形例にかかるパケットスケジューラ３Ｃが適用されたパケット転送装置６を示すブロック図であり、この図１５に示すパケット転送装置６は、前述の図２に示すパケット転送装置におけるパケットスケジューラ(符号３参照)として、図１１に示すパケットスケジューラ３Ｂまたは図１３に示すパケットスケジューラ３Ｂ′のいずれかの態様で動作しうるパケットスケジューラ３Ｃを適用したものである。
【０１１７】
また、このパケット転送装置６には、このパケット転送装置６の動作環境をオペレータが確認したり設定したりするための動作環境設定監視装置としてのワークステーション５が接続されている。このワークステーション５は、制御部５−１,ディスプレイ５−２及びキーボード,マウス等の入力装置５−３をそなえて構成されている。
【０１１８】
ここで、制御部５−１は、データやプログラム等を記憶しうる図示しない記憶機能と記憶機能にて記憶されているコンピュータプログラムを実行しうる制御機能とを少なくとも有してなるもので、動作環境設定部５１及び表示制御部５２をそなえて構成されている。
ここで、動作環境設定部５１は、パケット転送装置６の動作環境、具体的にはパケットスケジューラ３Ｃにおける乖離補正部による乖離補正処理の有効／無効を設定しうるものであり、表示制御部５２は、ワークステーション５の動作状態、具体的にはパケットスケジューラ３Ｃによる乖離補正状況をディスプレイ５−２にて表示するための制御を行なうものである。
【０１１９】
また、制御部５−１の動作環境設定部５−２は、例えば前述の図１３に示すパケットスケジューラ３Ｂ′で行なっていた乖離補正動作を行なうか否かの環境を設定する機能（乖離補正環境設定機能）と、乖離検出部３３Ｂ′−１における送出予定時刻データの現在時刻に対する乖離を検出する際の許容値ｋを設定する機能（乖離上限値設定機能）とをそなえている。さらに、表示制御部５２は、乖離検出部３３Ｂ′−１にて検出される現在時刻データとの乖離幅を表示制御する機能（乖離幅表示機能）をそなえている。
【０１２０】
ところで、上述の制御部５−１による各機能の動作により、ディスプレイ５−２では、例えば図１６に示すような表示を行なうことができるようになっている。
すなわち、パケットスケジューラ３Ｃの動作環境を設定する機能を動作させる際には、表示制御部５２の制御により、その動作状態に応じて例えば設定画面５Ａ〜５Ｆに示すような画面をディスプレイ５にて表示することができる。
【０１２１】
この設定画面５Ａ〜５Ｆに示すように、パケットスケジューラ３Ｃの動作環境を設定するための画面としては、４行により構成され、上から１行目には、この表示・設定画面のタイトルが表示される。また、２行目は上述の乖離補正環境設定機能による設定を行なうための表示であって、現在の乖離補正環境について表示されている。３行目には乖離上限値設定機能による設定を行なうための表示であって、現在乖離上限値が表示されている。さらに、４行目には乖離幅表示機能による乖離幅（乖離値）が表示される。
【０１２２】
また、設定画面５Ａ〜５Ｆにおける上から２行目または３行目の設定値を変更する際には、キーボード５−３における図示しない矢印キーを操作することによって、該当する設定を指定することができるようになっている。なお、指定された設定部分については反転表示がなされる。例えば設定画面５Ａでは「乖離補正機能」が反転表示され、乖離補正環境設定機能による設定ができ、設定画面５Ｄでは「乖離上限値」が反転表示され、乖離上限値設定機能による設定ができるような状態となっている。
【０１２３】
ここで、乖離補正環境設定機能を選択した状態で（画面５Ａ参照）、キーボード５−３におけるリターンキー(図示せず)を押下すると、画面５Ｂに示すように、乖離補正機能の有効（“ｏｎ”）かまたは無効（“ｏｆｆ”）を設定する画面表示となる。この状態においてキーボード５−３の矢印キーで“ｏｎ”かまたは“ｏｆｆ”の反転表示部分を選択したのち、リターンキーを押下することにより、乖離補正環境を設定することができる。なお、画面５Ｃでは、乖離補正機能を有効（“ｏｎ”）から無効（“ｏｆｆ”）に設定を変更している。
【０１２４】
同様に、乖離上限値設定機能を選択した状態で（画面５Ｄ参照）、キーボード５−３におけるリターンキー(図示せず)を押下すると、画面５Ｅに示すように、乖離上限値が入力できる画面表示となる。この状態においてキーボード５−３の数字キーで所望の乖離上限値を入力したのち、リターンキーを押下することにより、乖離上限値ｋとして入力した値を確定させることができる。なお、画面５Ｆでは、乖離上限値ｋを２００ｍｓ（ミリ秒）１５０ｍｓ(ミリ秒)に設定を変更している。
【０１２５】
また、上述のごときワークステーション５によるパケット転送装置６の動作環境の設定が変更されると、パケット転送装置６では、変更された設定に従って動作環境が更新されて、パケット転送処理を行なうことになる。
なお、乖離幅表示機能により画面５Ａ〜５Ｆ上の４行目に表示される乖離幅については、パケットスケジューラ３Ｃの機能により乖離幅が補正された場合には、補正直後の乖離値について通常と異なる色で表示することにより、乖離補正機能が動作したことを強調的に表示することができるようになっている。
【０１２６】
上述の構成による、本発明の第２実施形態の第２変形例の動作について、図１７及び図１８のフローチャートを用いて以下に説明する。
第２実施形態の第２変形例にかかるパケットスケジューラ３Ｃが適用されたパケット転送装置６では、動作環境設定監視装置としてのワークステーション５の乖離補正環境設定機能による設定により、前述の第２実施形態の第１変形例(図１３及び図１４参照)にて詳述したような乖離補正動作を行なう環境か、または前述の第２実施形態（図１１及び図１２参照）にて詳述したような乖離補正動作を行なわない環境かのいずれかの動作環境で動作する。
【０１２７】
なお、乖離補正を行なう前段までの処理、即ち図１３に示す送出予定時刻計算部３１Ｂ−１による送出予定時刻データの計算処理や、送出予定時刻比較部３１Ｂ′−１による送出予定時刻データのうちの最小値を選択する処理については、図１３に示すパケットスケジューラ３Ｂ′と同様である(図１７のステップＢ１〜Ｂ１１)。
【０１２８】
換言すれば、パケットスケジューラ３Ｃにおいても、送出予定時刻計算部において、バックログ状態のキューについて送出予定時刻を計算した後に、送出予定時刻比較部では計算された送出予定時刻から最小値の送出予定時刻を選択する処理までは、前述の図１１または図１３に示すパケットスケジューラ３Ｂ,３Ｂ′と共通する。
【０１２９】
上述の送出予定時刻比較部において最小値の送出予定時刻が選択されると、ワークステーション５では、表示制御部５２の乖離幅表示機能により、選択された送出予定時刻の最小値と時刻情報生成部３２からの現在時刻データＴｉｍｅとの差分値Ｄｉｆｆ（＝ＭｉｎＦ−Ｔｉｍｅ）をディスプレイ５−２において表示する(ステップＢ２０)。
【０１３０】
続いて、動作環境設定部５１の乖離補正環境設定機能による設定に基づいて、乖離補正機能が有効である場合には（Ａｃｔ＝１）、前述の図１３のパケットスケジューラ３Ｂ′と同様の乖離補正処理を行なう(ステップＢ２１のＹＥＳルートから図１８のステップＢ２２〜Ｂ２８)。換言すれば、乖離補正機能が有効である場合には、パケットスケジューラ３Ｃは前述の図１３に示すパケットスケジューラ３Ｂ′と同様に動作する。
【０１３１】
ここで、パケットスケジューラ３Ｃの乖離検出部３３Ｂ−１で、最小値の送出予定時刻データＭｉｎＦが時刻情報生成部３２からの現在時刻データＴｉｍｅに対して許容範囲ｋを超えて乖離していることを検出した場合(ステップＢ２２のＮＯルート)、補正指示部３３Ｂ′−２では、選択されなかったキューを含むＷＦＱアルゴリズムが適用される全てのキューについての送出予定時刻データを乖離上限値のＴｉｍｅ＋ｋに補正すべく指示する (ステップＢ２３〜Ｂ２５,Ｂ２８)。なお、上述の許容範囲ｋは、動作環境設定部５２の乖離上限値設定機能により設定されている。
【０１３２】
上述のごとくＷＦＱアルゴリズムが適用されるすべてのキューについての送出予定時刻データが補正される過程において、最小値として選択された送出予定時刻データについても補正されることによって、乖離幅表示機能によりディスプレイ５−２にて表示されていた乖離幅Ｄｉｆｆの値も乖離上限値ｋの値に更新される(ステップＢ２６)。この場合には、補正直後の乖離値Ｄｉｆｆ（＝ｋ）について通常と異なる色で表示することにより、乖離補正機能が動作したことを強調的に表示する(ステップＢ２７)。
【０１３３】
このようにして、すべての送出予定時刻データが補正されると、送出予定時刻比較部３１Ｂ′−２では、補正指示部３３Ｂ−２からの指示に基づいて、当該ＭｉｎＦ（＝Ｆｉ）の値をキュー２２−ｉの前回送出予定時刻Ｆ′ｉとして次回の送信予定時刻計算のために図示しないメモリ機能に記憶させる（ステップＢ２９）。その後、選択されたキュー２２−ｉの識別番号をキュー構成部２に通知することにより、当該キュー２２−ｉに格納されているパケットデータの読み出し指示をキュー構成部２の書き込み／読み出し制御部２１(図３参照)に出力する(ステップＢ３０)。
【０１３４】
また、上述の乖離補正機能が有効である状態において、最小値の送出予定時刻データＭｉｎＦの値が前述の式（３Ｂ）を満たしていると判定された場合には(ステップＢ２２のＹＥＳルート)、補正指示部３３Ｂ′−２では、送出予定時刻比較部３１Ｂ′−２に対して上述のごとき補正指示はせずに、当該送出予定時刻データＭｉｎＦを持つキューに保持される先頭パケットの送出処理のための指示を行なう（ステップＢ２９，Ｂ３０）。
【０１３５】
また、乖離補正機能が無効に設定されている場合には、パケットスケジューラ３Ｃは前述の図１１のパケットスケジューラ３Ｂと同様に動作する。即ち、補正指示部３３−２では、ＷＦＱアルゴリズムが適用されたキュー以外のキューがバックログ状態にあれば、当該キューからパケットデータを読み出すべき旨を送出予定時刻比較部３３Ｂ−２に指示し(ステップＢ３１)、上述のごとき乖離補正処理は行なわない。
【０１３６】
このように、本発明の第２実施形態の第２変形例においても、前述の第１実施形態の場合と同様、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点があるほか、動作環境設定監視装置としてのワークステーション５の動作環境設定部５１により、装置運用に際しての乖離補正処理の必要性に応じて、乖離補正処理の有効／無効を設定することができるので、運用に最適な環境で装置を動作させることができるので、装置運用者の便宜に資するという利点がある。
【０１３７】
なお、上述の第２実施形態の第２変形例にかかる動作環境設定装置としてのワークステーション５の各機能を動作させるためのコンピュータプログラムを、ＣＤ−ＲＯＭ等の記憶媒体に記憶しておき、パケット転送装置６の運用の際に、この記憶媒体に記憶されたプログラムをワークステーション５にて読取処理を行なって実施することも可能である。
【０１３８】
（ｃ）その他
上述の各実施形態にかかるパケットスケジューラの各機能としては、ハードウェア、ファームウェア、ソフトウェアまたはこれらの組み合わせなどのいずれにおいても実現可能である。
また、上述の各実施形態における実施態様のほか、本発明の趣旨を逸脱しない範囲の他の態様で実施することも可能である。
【０１３９】
（ｄ）付記
（付記１)  出力保証帯域に基づく重み係数がそれぞれ設定された複数のキューにより送出待ちのパケットを管理するとともに、各キューに格納された先頭パケットの送出順序を決定するパケットスケジューラであって、
各キューにおける送出待ちパケットの管理情報と前記重み係数とを用いた計算により得られた送出予定時刻情報に基づき、最優先に送出すべきパケットを格納するキューを選択制御するキュー制御手段と、
現在時刻情報に基づいて、該キュー制御手段における処理を補正する補正手段とをそなえて構成されたことを
特徴とする、パケットスケジューラ。
【０１４０】
（付記２)  該キュー制御手段が、バックログ状態の各キューにおける送出待ちパケットの管理情報と重み係数とを用いて前記バックログ状態の各キューに格納されたパケットの送出予定時刻を計算する送出予定時刻計算手段と、該送出予定時刻計算手段にて計算された各送出予定時刻情報に基づいてパケットを最優先に送出すべきキューを選択する選択手段とをそなえて構成されるとともに、
該補正手段が、該送出予定時刻計算手段による計算に前記現在時刻情報を反映させることにより、該選択手段における選択処理を補正すべく構成されたことを特徴とする、付記1記載のパケットスケジューラ。
【０１４１】
（付記３)  該補正手段が、該キュー制御手段にて選択制御されたキューについて計算された前記の送出予定時刻情報と現在時刻情報との乖離量を検出する乖離量検出手段と、該乖離量検出手段にて検出された乖離量に基づいて該選択手段による選択処理を補正すべく指示する指示手段とをそなえて構成されたことを
特徴とする、付記２記載のパケットスケジューラ。
【０１４２】
（付記４）  該指示手段が、該乖離量検出手段にて検出された乖離量に基づいて、該選択手段による選択の基準となる各キューの送出予定時刻情報を補正すべく指示するように構成されたことを特徴とする、付記３記載のパケットスケジューラ。
（付記５）  各キューにおける送出待ちパケットの管理情報を前記現在時刻情報を含んで入力され前記の管理情報から現在時刻情報を取得する時刻情報取得手段をそなえ、該補正手段が、該時刻情報取得手段にて取得された現在時刻情報に基づいて、該キュー制御手段における処理を補正するように構成されたことを特徴とする、付記1記載のパケットスケジューラ。
【０１４３】
（付記６)  該補正手段が、該送出予定時刻計算手段にて計算された前記の各送出予定時刻情報と現在時刻情報との乖離量をそれぞれ検出する乖離量検出手段と、該乖離量検出手段にて検出された各乖離量に基づいて該選択手段による選択処理を補正すべく指示する指示手段とをそなえて構成されたことを特徴とする、付記２記載のパケットスケジューラ。
【０１４４】
（付記７)  該補正手段が、該送出予定時刻計算手段における各計算過程の中間パラメータの値と前記現在時刻情報との乖離量をそれぞれ検出する乖離量検出手段と、該乖離量検出手段にて検出された各乖離量に基づいて該選択手段による選択処理を補正すべく指示する指示手段とをそなえて構成されたことを特徴とする、付記２記載のパケットスケジューラ。
【０１４５】
（付記８)  該指示手段が、該乖離量検出手段にて検出された乖離量に基づいて、該選択手段による選択処理を停止することを特徴とする、付記３記載のパケットスケジューラ。
（付記９)  付記１記載のパケットスケジューラの補正手段の補正処理動作についての有効／無効の環境を設定しうる動作環境設定部と、
該パケットスケジューラによる乖離補正状況動作を表示制御する表示制御部とをそなえて構成されたことを
特徴とする、動作環境設定監視装置。
【０１４６】
【発明の効果】
以上詳述したように、本発明のパケットスケジューラによれば、補正手段により、現在時刻情報に基づきキュー制御手段における処理を補正することができるので、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点がある。
【０１４７】
また、本発明によれば、補正手段が、送出予定時刻計算手段の計算に現在時刻情報を反映させることにより、選択手段における選択処理を補正することで、ＷＦＱ計算上の演算誤差を確実に補正された値を用いて選択手段における選択処理を行なうことができるので、送出予定時刻の計算値を示すビットデータを桁あふれ(オーバフロー)させることを防止して、選択手段における選択処理の信頼度、ひいてはパケットスケジューラやパケット転送装置の性能ないし信頼度を向上させることができる利点がある。
【０１４８】
さらに、本発明によれば、時刻情報取得手段をそなえたことにより、送出待ちパケットからの管理情報を、現在時刻情報を取得するために流用することができるので、時刻情報生成のための専用の機能部を持つ必要がなくなり、装置構成の簡素化を図ることもできる。
また、補正手段により、現在時刻情報に基づきキュー制御手段における選択処理を停止することを通じて補正することができるので、ＷＦＱ計算上の演算誤差に起因するパケット送出予定時刻と実時刻の乖離による誤動作を防ぎながら、帯域保証及び公平な余剰帯域配分を実現できる利点がある。
【０１４９】
すなわち、指示手段が、乖離量検出手段にて検出された乖離量に基づいて、キュー制御手段の選択手段による選択処理を停止することにより、最小値の送出予定時刻データの現在時刻データに対する乖離が許容範囲内に収まるまでＷＦＱアルゴリズムが適用されたキューからのパケットの読み出しの停止、すなわち計算される送出予定時刻データの増加を停止させることができるので、送出予定時刻が実時刻と乖離することを防止することができる。
【０１５０】
また、動作環境設定監視装置の動作環境設定部により、装置運用に際しての乖離補正処理の必要性に応じて、乖離補正処理の有効／無効を設定することができるので、運用に最適な環境で装置を動作させることができるので、装置運用者の便宜に資するという利点がある。
【図面の簡単な説明】
【図１】本発明の第１実施形態にかかるパケットスケジューラを示すブロック図である。
【図２】本実施形態にかかるパケットスケジューラが適用されるパケット転送装置を示すブロック図である。
【図３】本実施形態にかかるパケットスケジューラが適用されるパケット転送装置の要部を示すブロック図である。
【図４】本発明の第１実施形態の動作を説明するためのフローチャートである。
【図５】本発明の第１実施形態の第１変形例にかかるパケットスケジューラを示すブロック図である。
【図６】本発明の第１実施形態の第１変形例の動作を説明するためのフローチャートである。
【図７】本発明の第１実施形態の第２変形例にかかるパケットスケジューラを示すブロック図である。
【図８】本発明の第１実施形態の第２変形例の動作を説明するためのフローチャートである。
【図９】本発明の第１実施形態の第３変形例にかかるパケットスケジューラを示すブロック図である。
【図１０】本発明の第１実施形態の第３変形例の動作を説明するためのフローチャートである。
【図１１】本発明の第２実施形態にかかるパケットスケジューラを示すブロック図である。
【図１２】本発明の第２実施形態の動作を説明するためのフローチャートである。
【図１３】本発明の第２実施形態の第１変形例にかかるパケットスケジューラを示すブロック図である。
【図１４】本発明の第２実施形態の第１変形例の動作を説明するためのフローチャートである。
【図１５】本発明の第２実施形態の第２変形例を示すブロック図である。
【図１６】本発明の第２実施形態の第２変形例におけるワークステーションの画面表示例を示す図である。
【図１７】本発明の第２実施形態の第２変形例の動作を説明するためのフローチャートである。
【図１８】本発明の第２実施形態の第２変形例の動作を説明するためのフローチャートである。
【図１９】ネットワーク上のパケット転送装置における従来のＷＦＱアルゴリズムによるパケット転送技術を説明するための図である。
【図２０】ＷＦＱアルゴリズムによるパケット転送処理について説明するための図である。
【図２１】（ａ），（ｂ）はいずれもネットワーク上のパケット転送装置における従来のＷＦＱアルゴリズムによるパケット転送技術を説明するための図である。
【符号の説明】
１  パケット受信部
２  キュー構成部
３,３−１〜３−３，３Ｂ，３Ｂ′，３Ｃ  パケットスケジューラ
４  パケット送出部
５  ワークステーション
５Ａ〜５Ｆ  画面
５−１  制御部
５−２  ディスプレイ
５−３  入力装置
６  パケット転送装置
２１  書き込み／読み出し制御部
２２  ＦＩＦＯメモリ部
２２−１〜２２−ｎ  キュー
２３  キュー情報通知部
３１，３１Ａ，３１Ｂ，３１Ｂ′  キュー選択制御部(キュー制御手段)
３１−１，３１Ａ−１，３１Ｂ−１  送出予定時刻計算部(送出予定時刻計算手段)
３１−２，３１Ｂ−２，３１Ｂ′−２  送出予定時刻比較部（送出予定時刻比較手段）
３２  時刻情報生成部
３２Ａ  時刻情報所得部(時刻情報取得手段)
３３，３３Ａ，３３Ｂ，３３Ｂ′  乖離補正部(補正手段)
３３−１，３３Ａ−１，３３Ｂ−１  乖離検出部（乖離量検出手段）
３３−２，３３Ａ−２，３３Ｂ−２，３３Ｂ′−２  補正指示部（指示手段）
５１  動作環境制御部
５２  表示制御部
１０１−１〜１０１−ｎ  キュー
１０２  パケットスケジューラ
【図１】
0003790429.tif 000002
【図２】
0003790429.tif 000003
【図３】
0003790429.tif 000004
【図４】
0003790429.tif 000005
【図５】
0003790429.tif 000006
【図６】
0003790429.tif 000007
【図７】
0003790429.tif 000008
【図８】
0003790429.tif 000009
【図９】
0003790429.tif 000010
【図１０】
0003790429.tif 000011
【図１１】
0003790429.tif 000012
【図１２】
0003790429.tif 000013
【図１３】
0003790429.tif 000014
【図１４】
0003790429.tif 000015
【図１５】
0003790429.tif 000016
【図１６】
0003790429.tif 000017
【図１７】
0003790429.tif 000018
【図１８】
0003790429.tif 000019
【図１９】
0003790429.tif 000020
【図２０】
0003790429.tif 000021
【図２１】
0003790429.tif 000022