パケットスケジューリング装置
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、ＡＴＭ網のようなパケット網においてバッファリングされたパケットを選択出力するためのパケットスケジューリング装置に関する。
【０００２】
【従来の技術】ＡＴＭ（Asynchronous Transfer Mode：非同期転送モード）方式を用いたパケット網では、セルと呼ばれる５３オクテットの固定長のパケットが伝送される。ＡＴＭ方式においては、セルのヘッダ部に書かれたＶＣＩ（Virtual Channel Identifier：バーチャルチャネル識別子）、ＶＰＩ（Virtual Path Identifier ：バーチャルパス識別子）と呼ばれる識別子によりコネクションが識別される。
【０００３】また、ＡＴＭ方式ではコネクションが属するサービスクラスが定義される。サービスクラスには、ＣＢＲ（Constant Bit Rate ：固定ビットレート）、実時間ＶＢＲ（Variable Bit Rate ：可変レート）、非実時間ＶＢＲ、ＡＢＲ（Available Bit Rate：アベイラブル・ビットレート）、ＵＢＲ（Unspecified Bit Rate：アンスペシファイド・ビットレート）がある。そして、これらの各サービスクラスに対して、必要なセル廃棄率やセル遅延に関するＱＯＳ（Quality of Service：サービス品質）が規定される。すなわち、ＣＢＲ、実時間ＶＢＲおよび非実時間ＶＢＲでは、セル廃棄率、セル遅延の両方に関する要求値が規定される。ＡＢＲではセル廃棄率に関する要求値のみ規定され、ＵＢＲではＱＯＳは規定されない。
【０００４】ユーザは、コネクション設定時にコネクションのトラヒック特性に関するパラメータを網に申告する。網はこの申告パラメータを守ってセルを送出するコネクションに対して、要求するＱＯＳを保証できる場合にコネクションを設定する。申告パラメータとしては、ＣＢＲに関してはピークセルレートが、実時間ＶＢＲおよび非実時間ＶＢＲに関してはピークセルレート、平均セルレートや最大バースト長がそれぞれ用いられる。
【０００５】網は、これらの申告パラメータ通りにセルを送出しているコネクションに対しては、たとえパラメータに違反して送出するコネクションがあっても、その影響を受けずにＱＯＳを保証する必要がある。このための制御として、網の入口でコネクションの送出レートを監視し、パラメータに違反してセルを送出するコネクションに対しては入力規制を行なうＵＰＣ（Usage Parameter Control ：使用量パラメータ制御）がある。ＵＰＣを適切に行なえば、ＡＴＭ交換機は複数のコネクションのセルを単一もしくはクラス別のＦＩＦＯ（First-In First-Out：先入れ先出し）キューにより管理することで、申告パラメータ通りにセルを送出しているコネクションに対して、他のコネクションの影響を受けずにＱＯＳを保証することができる。
【０００６】しかし、ＡＢＲのように端末が送出可能なセルレートがコネクション接続中に網の状態によって動的に変動する場合には、正確なＵＰＣは難しいため、他のコネクションの影響を受けやすくなる。また、ＵＢＲに対してはＵＰＣを行なうことを想定していないが、ＵＢＲクラス内のコネクション間で、できるだけ公平に帯域を使用するような制御を行なうことが望ましい。このため、ＡＢＲ／ＵＢＲに対しては、単一もしくはクラス別のＦＩＦＯキューによる管理よりも、コネクション毎にキューを設けて、複数のキューの間でパケットのスケジューリングを行なうことが必要となる。
【０００７】このパケットスケジューリング方式として、あるクラスのコネクション間で全て等しい割合で公平にサービスを行なうＦＱ（Fair Queueing ）と呼ばれる方式が文献１：John B.Nagle, "On Packet Switches with Infinite Storage", IEEETransactions on Communications, Vol. COM-35, No.4,pp.435-438,April 1987. で提案されている。ＦＱ方式は、アクティブな（空でない）キューをラウンドロビンでサービスすることにより実現されるものであるが、コネクション毎に要求される帯域が異なる場合には適当でない。また、パケットが可変長である場合にはパケット長を考慮する必要がある。
【０００８】そこで、コネクション毎に各々の使用帯域に関する重みを与え、重みに応じた割合でパケット長を考慮して公平にキューのサービスを行なうことでパケットのスケジューリングを行なうＷＦＱ（Weighted Fair Queueing）と呼ばれるスケジューリング方式に関する検討がなされている。ＷＦＱのアルゴリズムについては、ＳＣＦＱ（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 '90pp. 19-29, 1990. で提案されている。
【０００９】今、パケットスケジューリング装置がコネクション毎にキューを持ち、コネクションは識別子により識別されるものとすると、ＳＣＦＱではコネクションｉ毎に使用帯域に比例した重みｗｉと変数Ｆｉを持ち、パケットがパケットスケジューリング装置に到着すると変数Ｆｉの値の更新を行ない、更新した変数Ｆｉを到着パケットと一緒にキューに格納する。パケット出力時には、アクティブなキューの先頭のパケットの変数Ｆｉの中から最小のＦｉを持つコネクションのパケットをサービスする。変数Ｆｉの更新は、Ｆｉ ＝Ｌ／ｗｉ＋ｍａｘ（Ｆｉ，ｖ（ｔａ））
に従って行なわれる。但し、Ｌは到着パケットのパケット長、ｔａはパケットの到着時刻、ｖ（ｔａ）は時刻ｔａにおいてサービス中またはサービス直後のコネクションｊのパケットの変数Ｆｊの値を返す関数である。
【００１０】
【発明が解決しようとする課題】しかしながら、上述したＳＣＦＱやバーチャルクロックのようなアルゴリズムによるパケットのスケジューリング方式では、２つの問題点がある。第１の問題点は、重みの差が大きいコネクションのパケット同士がスケジューリングされる場合に、小さい時間スケールで公平になりにくいことである。例えば、重み１のコネクション１００本と、重み１００のコネクション１本のパケットがぞれぞれ１個ずつ合計１０１個、各コネクション対応のキューに存在し、その状態で重み１００のコネクションのパケットが連続して到着するものとする。このとき公平を期するとすると、理想的には重み１の１００本のコネクションのパケットと重み１００の１本のコネクションのパケットは交互にスケジューリングされるべきにもかかわらず、ＳＣＦＱやバーチャルクロックでは、重み１００のコネクションから先に最大１００個のパケットが出力された後で、重み１のコネクションのパケットが出力される。すなわち、重みの大きいコネクション群と重みの小さいコネクション群があって、それぞれのコネクション群の重みの和が等しい場合には、常に重みの大きい方のコネクション群のパケットが小さい時間スケールで優位に扱われてしまうという不都合がある。
【００１１】第２の問題点は、ＳＣＦＱやバーチャルクロックでは前述したようにパケットのスケジューリング時に変数Ｆｉの最小値を計算で求める必要があるが、このための計算時間がコネクション数とともに増大することである。今、変数Ｆｉを常にソートしておくものとすると、コネクション数がｎのときに最小値を求めるのに必要な計算時間は、ソートされたＦｉの系列に新しいＦｉを挿入する時間、すなわちｏ（ｌｏｇ2 ｎ）のオーダとなる。ＡＴＭの場合、ｌ物理リンクあたりの最大のバーチャルコネクション（ＶＣ）数ｎ＝４０９６をサポートするには、変数Ｆｉの最小値を計算するとき最大ｌｏｇ2 ４０９６＝１２回のサーチが必要となる。このような計算時間の増大から、パケットのみでなくクラスおよびバーチャルパス（ＶＰ）のスケジューリングも行なう場合や、リンク速度が大きい場合を考慮すると、ＳＣＦＱやバーチャルクロックは実装が困難である。従って、スケジューリングに必要な処理時間がコネクション数に関係なく小さい値であることが望まれる。
【００１２】一方、米国特許第５，３７９，２９７号明細書"Concurrent Multi-Channel Segmentation and Reassmbly Processors for Asynchronous Transfer Mode" には、ピークレート毎にキューを構成することにより、コネクション数に関係ない処理時間で複数のキューの間でＷＦＱを行なう方式が開示されているが、この方式では任意のピークレート（重み）の組み合わせをサポートできない。
【００１３】本発明は、上記のような従来技術の問題点を解決し、コネクションの重みによらず公平なスケジューリングを可能としたパケットスケジューリング装置を提供することを目的とする。
【００１４】また、本発明は受信パケットが固定長パケットの場合に、スケジューリングに必要な処理時間がコネクション数に関係なく一定値となるようなパケットスケジューリング装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】上記の課題を解決するため、本発明は入力されるパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積部と、パケット受信時に複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力部と、複数のパケット蓄積部にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積部のパケット蓄積量と該パケット蓄積部に設定された重みとに基づいて管理するスケジューリング情報管理部と、パケット送信時にスケジューリング情報管理部が管理するスケジューリング情報を基に所望のパケット蓄積部から所望のパケットを出力するパケット出力部とを有することを基本的な特徴とする。
【００１６】このように本発明では、スケジューリング情報管理部において、パケット蓄積部からパケットを読み出す際に用いるスケジューリング情報をパケット蓄積量とそのパケット蓄積部に設定された重みと基づいて管理するため、アクティブなパケット蓄積部に対応する重みの値だけでなく、アクティブなパケット蓄積部のパケット蓄積量も考慮してパケットのスケジューリングが行なわれる。
【００１７】ここで、それぞれのパケット蓄積部に設定される重みとして、例えばパケット蓄積部に対応したコネクションに設定されている帯域の重みを用いた場合、パケット蓄積量に比例した評価値が重み以下のコネクションは、重みに相当する分の帯域をフルに使用せず、他のコネクションに帯域を与えることができるため、コネクションの重みによらず公平なスケジューリングが可能となる。すなわち、重みの大きいコネクション群と重みの小さいコネクション群が存在し、それぞれのコネクション群の重みの和が等しい場合においても、重みの大きいコネクション群が小さい時間スケールで優位に扱われることが抑制される。また、任意の重みの組合せをサポートできる。
【００１８】また、本発明は特に固定長パケットをスケジューリングする際、パケット蓄積量が蓄積されたパケットの数に比例することから、スケジューリング情報管理部において複数のパケット蓄積部にそれぞれ対応したスケジューリング情報を該パケット蓄積部スケジューリング情報をパケット蓄積部のパケット蓄積量とそのパケット蓄積部に設定された重みのうちの小さい方の値に等しい個数だけ常に保持することを特徴とする。
【００１９】この場合、スケジューリング情報管理部へのスケジューリング情報の入力はパケットの受信時と送信時に行ない、その際に必要な処理としては基本的にそのパケットを蓄積しているパケット蓄積部のパケット蓄積数と設定された重みを比較して小さい方を調べるのみでよい。このようにすることにより、パケットが固定長であることを利用してスケジューリングに必要な処理時間がコネクション数に依存せず一定のパケットスケジューリングを実現できる。また、このようにスケジューリング情報管理部が保持するスケジューリング情報の個数をパケット蓄積数と重みのうちの小さい方の値を上限とすることにより、パケット蓄積量と重みの両方を考慮したパケットスケジューリングが上記と同様に可能になるため、重みによらず公平なスケジューリングを行なうことができる。さらに、スケジューリング情報管理部から読み出すスケジューリング情報の選び方を変えれば、様々なポリシーに基づいたパケットスケジューリングが可能となる。
【００２０】また、本発明では複数クラスおよび仮想パスのスケジューリングをサポートするパケットスケジューリング装置を実現する場合、スケジューリング情報管理部において、パケットが属するクラス別または仮想パス別にスケジューリング情報を管理することを特徴とする。さらに、クラス別または仮想パス別に重みを設定し、これを各クラスまたは仮想パス内のコネクション別のキュー長が０から正の値に変化したときまたは、正の値から０に変化したときに変更することにより、クラス間または仮想パス間でのパケットスケジューリングと同一クラスまたは同一仮想パス内のパケットスケジューリングの両方において、上述と同様の作用が得られる。
【００２１】スケジューリング情報管理部は、少なくとも一つのＦＩＦＯキューあるいはランダムアウトキューで構成される。スケジューリング情報管理部をＦＩＦＯキューで構成した場合は、スケジューリング情報管理部がパケットをスケジューリングするために必要な処理時間がコネクション数に関係なく一定となり、かつスケジューリング情報管理部のハードウエア構成も簡単になる。また、スケジューリング情報管理部をランダムアウトキューで構成した場合は、スケジューリング情報管理部がパケットをスケジューリングするために必要な処理時間がコネクション数に関係なく一定となる上、入力トラヒックにほとんど依存せず確率的に公平なスケジューリングが可能となる。
【００２２】
【発明の実施の形態】
（第１の実施の形態）図１に、本発明の第１の実施形態に係わるパケットスケジューリング装置の構成を示す。
【００２３】本実施形態におけるパケットスケジューリング装置１１は、パケット蓄積部である複数のパケットキュー１２，１３，１４と、パケット受信時にパケットキュー１２，１３，１４にパケットを入力するためのパケット入力部１５と、パケットキュー１２，１３，１４に蓄積されたパケット１８を読み出す順序を指定するためのスケジューリング情報を管理するスケジューリング情報管理部１６と、パケット送信時にスケジューリング情報管理１６が管理するスケジューリング情報に基づきパケットキュー１２，１３，１４から所望のパケットを読み出して出力するパケット出力部１７と、受信パケットをパケットスケジューリング装置１１に入力するためのパケット入力線１９と、送信パケットをパケットスケジューリング装置１１から出力するためのパケット出力線２０を有する。
【００２４】次に、パケットスケジューリング装置１１の動作を説明する。パケットスケジューリング装置１１で受信されたパケットは、パケット入力線１９からパケット入力部１５に入力される。パケット入力線１９は一般に複数本存在する。パケット入力部１５は、パケット入力線１９から入力されたパケットを該パケットのヘッダ情報を基にパケットキュー１２，１３，１４のうちの所望の一つに入力する。ここで、受信パケットがユニキャストパケットの場合には、いずれか１つのパケットキューにパケットが入力されるが、パケットスケジューリング装置１１でマルチキャストをサポートする場合には、マルチキャストすべき複数のパケットキューにパケットが入力される。
【００２５】パケットキュー１２，１３，１４は、ＶＣ（バーチャルチャネル）コネクション毎、トラヒッククラス毎、出力リンク毎、あるいはこれら２つ以上の組み合わせ等、種々の単位で設けることができるが、本実施形態ではＶＣコネクション毎にパケットキュー１２，１３，１４が設けられているものとする。これらのＶＣコネクションには、それぞれ要求された帯域が設定されている。
【００２６】スケジューリング情報管理部１６は、パケットキュー１２，１３，１４に蓄積されているパケットを読み出す順序を指定するためのスケジューリング情報であるＶＣＩ（バーチャルチャネル識別子）をパケット入力部１５から入力し、パケット出力部１７へ出力する。この際、スケジューリング情報管理部１６は各パケットキュー１２，１３，１４に対して、そのパケットキューのパケット蓄積量（以下、キュー長という）と、そのパケットキューに対応した重みとに基づいてスケジューリング情報であるＶＣＩを管理し、これらキュー長と重みに従ってパケット出力部１７へのスケジューリング情報の出力順序を決定する。
【００２７】本実施形態では、各パケットキューに対応したＶＣコネクションに設定された帯域の比に等しい重みを各パケットキューに割り当てる。ここで、ＶＣＩ＝ｉで識別されるパケットキューに対応するＶＣコネクションに設定された帯域の重みをｗｉ、同パケットキューのキュー長をバイト数で表わしてｑｉとする。スケジューリング情報管理部１６は、ＶＣＩ＝ｉのパケットがパケット入力部１５に到着したとき、あるいはＶＣＩ＝ｉのパケットがパケット出力部１７から出力されるときに式（１）で表される変数Ｆｉを更新し、次に出力すべきパケットのＶＣＩを決定する。
【００２８】Ｆｉ＝ｆ（ｑｉ，ｗｉ）
ここで、関数ｆはスケジューリングのポリシーに依存して決定される。例えば関数ｆを式（２）とすれば、キュー長ｑｉが重みｗｉ以下の場合には、重みｗｉに応じた帯域はＶＣコネクションｉに与えられず、他のコネクションに帯域を与えることが可能となる。
【００２９】
【数１】
なお、関数ｆを式（３）とすれば、スケジューリングがキュー長ｑｉに依存しない従来のＳＣＦＱ方式となる。
【００３０】
【数２】
【００３１】但し、式（２）（３）においてＬは到着パケットのパケット長、Ｌｍｉｎはパケットスケジューリング装置１１で扱う最小パケット長、ｔａはパケットの到着時刻、ｖ（ｔａ）は時刻ｔａにおいてサービス中またはサービス直後のＶＣコネクションｊのパケットの変数Ｆｊの値を返す関数である。
【００３２】パケット出力部１７は、パケット送信時にスケジューリング情報管理部１６からＶＣＩを１つ取り出した後、そのＶＣＩに対応するパケットキューからパケットを取り出してパケット出力線２０へ出力する。
【００３３】このように本実施形態によれば、スケジューリング情報管理部１６において、スケジューリング情報であるＶＣＩをパケットキュー１２，１３，１４のキュー長と設定された重みとに基づいて管理するため、アクティブなパケットキューに設定されている重みの値だけでなく、そのパケットキューのキュー長も考慮したきめ細かなパケットスケジューリングを行なうことができる。
【００３４】従って、各パケットキュー１２，１３，１４に対応するＶＣコネクションに設定されている帯域の重みを各パケットキュー１２，１３，１４に設定すれば、キュー長に比例した評価値が重み以下のＶＣコネクションが重みに相当する分の帯域をフルに使用せず、他のコネクションに帯域を与えることができるため、重みの大きいコネクション群と重みの小さいコネクション群が存在し、それぞれのコネクション群の重みの和が等しい場合においても、重みの大きいコネクション群が小さい時間スケールで優位に扱われることが抑制され、コネクションの重みによらず公平なパケットスケジューリングが実現されるという効果が得られる。
【００３５】（第２の実施形態）次に、第１実施形態をより具体化した第２の実施形態に係わるパケットスケジューリング装置について図２を用いて説明する。本実施形態はＡＴＭセルのような固定長パケットのスケジューリングを行なう例であり、Ｍ個のパケットキューを有し、またスケジューリング情報としては第１の実施形態と同様にＶＣＩを用いるものとする。図２において、図１R>１と相対応する部分には同一符号を付して第１の実施形態との相違点を中心に説明する。
【００３６】本実施形態においては、スケジューリング情報管理部１６はＭ個のパケットキュー１２，１３，１４に対応したＶＣＩ２１を各パケットキューに対してキュー長と設定された重みのうち小さい方の値に等しい個数だけ常に保持する。
【００３７】また、本実施形態では各パケットキュー１２，１３，１４に対応するコネクションにそれぞれ設定された帯域の比に等しい重みｗ１，ｗ２，ｗＭを各パケットキュー１２，１３，１４に設定する。ここで、ＶＣＩ＝ｉで識別されるパケットキューに対応するコネクションに設定された帯域の重みをｗｉとし、該パケットキューのキュー長をｑｉとする。
【００３８】スケジューリング情報管理部１６は、保持されているスケジューリング情報であるＶＣＩ＝ｉの個数をｎｉとすると、以下の関係式が常に成立するように制御される。
【００３９】
ｎｉ＝ｍｉｎ（ｑｉ，ｗｉ） …（４）
このとき、ｆ（ｑｉ，ｗｉ）＝ｍｉｎ（ｑｉ，ｗｉ）となる。ここで、パケットキュー１２，１３，１４に対して設定される重みをｗ１＝ｗ２＝ｗＭ＝１とおけば、文献４：John B.Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Vol. COM-35, No.4,April 1987. と同様のFair Queueing が実現できる。
【００４０】また、ｗ１＝２，ｗ２＝１，ｗＭ＝３とすると、図２においてはパケットキュー１２，１３，１４のキュー長はｑ１＝３，ｑ２＝２，ｑＭ＝０であるため、ｎ１＝２，ｎ２＝１，ｎＭ＝０となる。なお、図２においてパケットキュー１２，１３，１４の中に記された○印がパケットを表わし、この○印の数がキュー長を評価している。
【００４１】パケット出力部１７は、パケット送信時にスケジューリング情報管理部１６からＶＣＩを１つ取り出した後、そのＶＣＩに対応するパケットキューからパケットを取り出してパケット出力線３０からパケットを出力する。
【００４２】図３に、本実施形態におけるスケジューリング情報としてＶＣＩを用いるスケジューリング情報管理部１６の構成例を示す。このスケジューリング情報管理部１６は、プロセッサ（ＭＰＵ）３１、ＲＯＭ３２、ＶＣＩメモリ３３、キュー長メモリ３４、重みメモリ３５、状態レジスタ３６、入力ＶＣＩレジスタ３７、出力ＶＣＩレジスタ３８、データバス３９および制御バス４０を有する。これら各部の機能は、次の通りである。
【００４３】ＭＰＵ３１は、ＲＯＭ３２にプログラムされた命令を逐次実行する。ＶＣＩメモリ３３は、スケジューリング情報であるＶＣＩを格納するためのキューであり、ＲＡＭによって構成される。スケジューリング情報管理部１６がＦＩＦＯキューで構成されている場合には、ＶＣＩメモリ３３はリンクドリストまたはリングバッファのいずれの方式で実装してもよい。
【００４４】キュー長メモリ３４は、パケットキュー１２，１３，１４毎の現在のキュー長を記憶するメモリであり、ＲＡＭによって構成される。重みメモリ３５は、パケットキュー１２，１３，１４毎に設定されている重みを記憶するメモリであり、ＲＡＭによって構成される。
【００４５】状態レジスタ３６は、スケジューリング情報管理部１６の動作状態を示す情報を格納するためのレジスタであり、図示しない外部装置により書き込みがなされ、ＭＰＵ３１が該レジスタ３６の値を参照する。なお、各セルスロットにおいて、入力セルがある場合には状態レジスタ３６の値は１となり、セル入力処理終了後状態レジスタ３６の値は２となる。
【００４６】入力ＶＣＩレジスタ３７は、スケジューリングされるパケットのＶＣＩを格納するためのレジスタであり、外部装置により書き込みがなされ、ＭＰＵ３１が該レジスタ３７の値を参照する。
【００４７】出力ＶＣＩレジスタ３８は、出力されるパケットのＶＣＩを格納するためのレジスタであり、ＭＰＵ３１から書き込みがなされ、図示しない外部装置が該レジスタ３８の値を参照する。出力ＶＣＩレジスタ３８に負の値が書き込まれる場合は、パケットは出力されないものとする。
【００４８】ＭＰＵ３１と、各メモリ３３，３４，３５および各レジスタ３６，３７，３８との間でやりとりされるデータは、データバス３９上を流れる。また、制御バス４０を用いて、アドレス指定等のデータアクセスのための制御情報のやりとりを行なう。
【００４９】次に、図４に示すフローチャートを用いて図３のスケジューリング情報管理部１６内で実行されるスケジューリングアルゴリズムを説明する。図４において、Ｅｎｑｕｅｕｅ（ｉ）はＶＣＩ＝ｉをＶＣＩメモリ３３に書き込む操作を表し、ＤｅｑｕｅｕｅはＶＣＩメモリ３３からＶＣＩを読み出す操作を表す。なお、図４のスケジューリングアルゴリズムはコード化されて図３のＲＯＭ３２内に格納される。
【００５０】まず、状態レジスタ３６の値ｓをＭＰＵ３１で参照し（ステップＳ１０１）、ｓが１，２のいずれか、またはｓが１、２のいずれでもないかどうかを調べる（ステップＳ１０２）。ｓ＝１であれば、ＶＣＩ入力レジスタ３７の値ｉを参照し（ステップＳ１０３）、ＶＣＩ＝ｉのパケットキューのキュー長＋１をｑとし（ステップＳ１０４）、またＶＣＩ＝ｉのパケットキューに設定された重みをｗとして（ステップＳ１０５）、ｑ、ｗの大小関係を調べる（ステップＳ１０６）。ここで、ｑ≦ｗの場合にはステップＳ１０７においてＥｎｑｕｅｕｅ（ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込み、その後にステップＳ１０８に移り、またｑ＞ｗの場合には直接ステップＳ１０８に移る。ステップＳ１０８では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとする。
【００５１】一方、ステップＳ１０２においてｓ＝２であれば、ステップＳ１０９においてｉ：＝Ｄｅｑｕｅｕｅ、つまりＶＣＩメモリ３３からＶＣＩを読み出した後、ＶＣＩ＝ｉのパケットキューのキュー長−１，０のうち大きい方をｑとし（Ｓ１１０）、さらにＶＣＩ＝ｉのパケットキューに設定された重みをｗとして（Ｓ１１１）、ｑ，ｗの大小関係を調べる（Ｓ１１２）。ここで、ｑ≧ｗの場合にはステップＳ１１３においてＥｎｑｕｅｕｅ（ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込み、その後にステップＳ１１４に移り、またｑ＜ｗの場合には直接ステップＳ１１４に移る。ステップＳ１１４では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとし、さらに次のステップＳ１１５でＶＣＩ出力レジスタ３８の値をｉとする。
【００５２】そして、ステップＳ１０２においてｓが１、２のいずれでもない場合と、ステップＳ１０８，Ｓ１１５の処理の終了後、ステップＳ１１６で状態レジスタ３６の値を０としてステップＳ１０１に戻り、以上の処理を繰り返す。
【００５３】このようなアルゴリズムにより、ＶＣＩメモリ３３内の各ＶＣＩ＝ｉの個数について常に式（４）が成立する。このように本実施形態では、スケジューリング情報管理部１６においてＶＣＩメモリ３３に各パケットキュー１２，１３，１４毎にキュー長と設定されている重みとを比較して、これらのうち小さい方の値同じ個数のＶＣＩ２１をスケジューリング情報として保持するため、第１の実施形態の効果に加えて、スケジューリングに必要な処理時間がＶＣコネクション数に依存せず一定のパケットスケジューリングを実現できるという効果がある。
【００５４】（第３の実施形態）次に、第２の実施形態においてスケジューリング情報管理部１６をＦＩＦＯキューで構成した場合の第３の実施形態に係わるパケットスケジューリング装置の構成と動作を図５を用いて説明する。図５において、ＣＶＩ＝１，１，２の順番でパケットキュー１２，１３，１４からパケットが出力される。ここで、スケジューリング情報管理部１６がリングドリストを用いたＦＩＦＯキュー構成の場合には、図３に示したフローチャート中のＥｎｑｕｅｕｅ（ｉ）はリストの最後尾にｉを追加する操作を表わし、Ｄｅｑｕｅｕｅはリストの先頭から値を取り出すとともに、リストの先頭を更新する操作を表す。リストが空の場合は、Ｄｅｑｕｅｕｅは負の値とする。
【００５５】まず、パケットがパケット入力部５から入力された場合の動作例を述べる。図５（ａ）の状態でＶＣＩ＝Ｍがパケット入力部１５から入力された場合、パケット入力直後はＶＣＩ＝Ｍに対応するパケットキュー１４のキュー長ｑＭと、このパケットキュー１４に設定された重みｗＭの大小関係はｑＭ＝１＜ｗＭ＝３であるため、ＶＣＩ＝Ｍがスケジューリング情報管理部１６の最後尾に追加される。また、図５（ａ）の状態でＶＣＩ＝１のパケットがパケット入力部１５から入力された場合、パケット入力直後はＶＣＩ＝１に対応するパケットキュー１１のキュー長ｑ１と、このパケットキュー１１に設定された重みｗ１の大小関係はｑ１＝４＞ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６の最後尾に追加されない。
【００５６】次に、パケットがパケット出力部１７から出力された場合の動作例を述べる。ここで、ｗ１＝１，ｗＭ＝３に設定されているものとする。図５（ａ）の状態でＶＣＩ＝１のパケットがパケット出力部１７から出力された直後はｑ１＝ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６に再度入力される。このとき、ＶＣＩ＝１はスケジューリング情報管理部１６の最後尾に追加され、図５（ｂ）の状態になる。次に、図５（ｂ）の状態でＶＣＩ＝１のパケットがパケット出力部１７から出力されるが、パケット出力直後はｑ１＝１＜ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６に再入力されない。
【００５７】このように本実施形態によれば、スケジューリング情報管理部１６をＦＩＦＯキューで構成したことにより、スケジューリング情報管理部１６がパケットをスケジューリングするために必要な処理時間がＶＣコネクション数に関係なく一定となり、かつスケジューリング情報管理部１６のハードウエア構成が簡単になるという効果がある。
【００５８】（第４の実施形態）図６に、本発明の第４の実施形態におけるスケジューリング情報管理部１６の構成例を示す。なお、スケジューリング情報管理部１６はクラス毎にスケジューリング情報を管理するものとする。ここでのクラスは速度クラス、サービスクラス、それらの組合せのいずれでもよい。また仮想パス別にスケジューリング情報を管理する場合についても同様の構成となる。図６において、図３と同一部分に同一符号を付して説明すると、本実施形態においては図３の構成に加えてクラスレジスタ６１が新たに設けられる。
【００５９】このクラスレジスタ６１は、パケットが属するクラスの番号を格納するためのレジスタであり、図示しない外部装置から書き込みがなされ、ＭＰＵ３１が該レジスタ６１の値を参照する。また、入力ＶＣＩレジスタ３７はＶＣＩをクラス別に格納するためのキューであり、ＲＡＭにより構成される。入力ＶＣＩレジスタ３７から読み込まれた入力ＶＣＩは、クラスレジスタ６１から読み込んだクラス番号のクラスに対応したＶＣＩメモリ３３内のキューに書き込まれる。
【００６０】次に、図７に示すフローチャートを用いて図６のスケジューリング情報管理部１６内で実行されるスケジューリングアルゴリズムを説明する。図７において、Enqueue （ｃ，ｉ）はＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込む操作を表し、Dequeue （ｃ）はＶＣＩメモリ３３のクラスｃに対応するクラス別キューからＶＣＩを取り出す操作を表す。Select ClassはＶＣＩを出力すべきクラスの番号を返す関数である。但し、クラス別キューが空であれば、クラス番号として負の値を返す。
【００６１】まず、状態レジスタ３６の値ｓをＭＰＵ３１で参照し（ステップＳ２０１）、ｓが１，２のいずれか、またはｓが１、２のいずれでもないかどうかを調べる（ステップＳ２０２）。ｓ＝１であれば、クラスレジスタ６１の値ｃと、ＶＣＩ入力レジスタ３７の値ｉを順次参照し（ステップＳ２０３，Ｓ２０４）、ＶＣＩ＝ｉのパケットキューのキュー長＋１をｑとし（ステップＳ２０５）、またＶＣＩ＝ｉのパケットキューの重みをｗとして（ステップＳ２０６）、ｑ，ｗの大小関係を調べる（ステップＳ２０７）。ここで、ｑ≦ｗの場合にはステップＳ２０８においてＥｎｑｕｅｕｅ （ｃ，ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込み、その後にステップＳ２０９に移り、またｑ＞ｗの場合には直接ステップＳ２０９に移る。ステップＳ２０９では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとする。
【００６２】一方、ステップＳ２０２においてｓ＝２であれば、ステップＳ２１１においてｉ：＝Dequeue （ｃ）、つまりＶＣＩメモリ３３のクラス別キューからＶＣＩを取り出した後、ＶＣＩ＝ｉのパケットキューのキュー長−１，０をｑとし（Ｓ２１２）、またＶＣＩ＝ｉのパケットキューの重みをｗとして（Ｓ２１３）、ｑ，ｗの大小関係を調べる（Ｓ２１４）。ここで、ｑ≧ｗの場合にはステップＳ２１５においてＥｎｑｕｅｕｅ（ｃ，ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込んだ後にステップＳ２１６に移り、またｑ＜ｗの場合には直接ステップＳ２１６に移る。ステップＳ２１６では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとし、さらにＶＣＩ出力レジスタ３８の値をｉとする（Ｓ２１７）。
【００６３】そして、ステップＳ２０２においてｓが１、２のいずれでもない場合と、ステップＳ２０９，Ｓ２１７の処理の終了後、状態レジスタ３６の値を０とし（ステップＳ２１８）、ステップＳ２０１に戻り、以上の動作を繰り返す。
【００６４】Ｓｅｌｅｃｔ Ｃｌａｓｓが予め定められた順番で周期的にクラスを選択すれば、時分割多重（ＴＤＭ）的なクラスのスケジューリングとなる。また、クラスに対してもキュー長と重みのうちの小さい方の値に基づいたＷＦＱを行なう場合には、クラスをスケジューリングするためのクラススケジューリングキューとクラス別セル数カウンタとクラス別の重みとを用意し、Ｓｅｌｅｃｔ Ｃｌａｓｓはクラスｃのセル数カウンタの値が１以上であれば、クラススケジューリングキューからクラス番号を１個出力するとともに、クラスｃのセル数カウンタをデクリメントする。一方、クラスｃのセル数カウンタの値が０であれば、負の値を出力する。
【００６５】ここで、Ｅｎｑｕｅｕｅ（ｃ，ｉ）は、ＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込む操作に加え、クラスｃのセル数カウンタをインクリメントし、状態レジスタ３１の値がｓ＝１、かつクラスｃのセル数が重み以下であるか、またはｓ＝２、かつクラスｃのセル数が重み以上である場合にクラス番号ｃをクラススケジューリングキューに書き込む操作を行なうようにする。
【００６６】また、クラスのスケジューリングには、ＳＣＦＱやＶｉｒｔｕａｌ Ｃｌｏｃｋなどの従来方式を用いることも可能である。また、１個以上蓄積されているクラスの中で最も優先度の高いクラスをサービスするような完全優先のクラススケジューリングを行なう場合には、クラス別の重みは必要ない。
【００６７】このゆうなアルゴリズムにより、常にＶＣＩメモリ３３内のＶＣＩ＝ｉの個数について式（４）が成立し、かつクラス毎に独立したスケジューリングが可能となる。
【００６８】なお、図７のスケジューリングアルゴリズムは、コード化されて図６のＲＯＭ３２内に格納されているものとする。このように本実施形態によれば、パケットが属するクラス別にスケジューリング情報管理部１６でスケジューリング情報であるＶＣＩを管理することにより、クラス間でのパケットスケジューリングと同一クラス内のコネクション間のパケットスケジューリングの両方において、第１〜第３の実施形態と同様の効果を得ることができる。
【００６９】（第５の実施形態）次に、本発明の第５の実施形態に係るパケットスケジューリング装置の構成と動作を図８を用いて説明する。
【００７０】図８において、図２および図５と同一部分に同一符号を付して説明すると、本実施形態ではスケジューリング情報管理部１６内にランダムアウトキュー８１，８２およびキュー選択部８３，８４が設けられている。
【００７１】キュー選択部８３は、スケジューリング情報をランダムアウトキュー８１，８２のいずれに格納するかを選択する。また、キュー選択部８４はランダムアウトキュー８１，８２のいずれからスケジューリング情報を取り出すかを選択する。ここで、キュー選択部８３がランダムアウトキュー８１を選択している場合は、キュー選択部８４はランダムアウトキュー８２を選択し、反対にキュー選択部８３がランダムアウトキュー８２を選択している場合は、キュー選択部８４はランダムアウトキュー８１を選択する。このようにキュー選択部８３，８４は、常に互いに異なるランダムアウトキューを選択するように制御される。なお、ここではランダムアウトキューが２個であるが、さらに多数のランダムキューを設けてもよい。
【００７２】ランダムアウトキュー８１，８２はキュー選択部８４によって選択されている場合に、格納しているスケジューリング情報をランダムに出力する。ここで、キュー選択部８４によって選択されているランダムアウトキューからスケジューリング情報が全て取り出された場合、キュー選択部８３，８４はそれぞれ、現在選択されていないランダムアウトキューを選択する。
【００７３】スケジューリング情報管理部１６の基本動作は、図４に示したフローチャートで表されるが、Ｅｎｑｕｅｕｅ（ｉ）、Ｄｅｑｕｅｕｅの意味が先の第２の実施形態の場合と異なる。
【００７４】図８において、パケットキュー１２，１３，１４はＶＣＩ＝１，２，ＭのＶＣコネクションにそれぞれ対応しており、それらのコネクションの持つ重みをそれぞれｗ１＝２，ｗ２＝１，ｗＭ＝１とする。また、図８（ａ）の状態でパケットキュー１２，１３，１４にパケットが格納されており、それらのスケジューリング情報がスケジューリング情報管理部１６内のランダムアウトキュー８１に格納されているものとする。すなわち、キュー選択部８３はランダムアウトキュー８１を選択し、キュー選択部８４はランダムアウトキュー８２を選択している。
【００７５】パケット出力時点で現在キュー選択部８４が選択しているランダムアウトキュー８２は空であるため、キュー選択部８３はランダムアウトキュー８２へ選択を切り替え、キュー選択部８４はランダムアウトキュー８１へ選択を切り替える。ここで、ランダムアウトキュー８１からランダムにＶＣＩを選択した結果、ＶＣＩ＝２が出力されたものとすると、ｑ２＝０＜ｗ２＝１となって、ＶＣＩ＝２はスケジューリング情報管理部１６に再入力されないため、パケットスケジューリング装置１１は図８（ａ）の状態から図８（ｂ）の状態に遷移する。
【００７６】図８（ｂ）の状態において、ＶＣＩ＝１のパケットキューへ１個パケットが到着した場合、ｑ１とｗ１の関係から、ＶＣＩ＝１が１個新たにランダムアウトキュー８２へ入力され、パケットスケジューリング装置１１は図８（ｂ）の状態から図８（ｃ）の状態に遷移する。
【００７７】さらに、図８（ｃ）の状態委からＶＣＩ＝２に対応するパケットキュー１３にパケットが１個到着した後、ランダムアウトキュー８１から２個の識別子１，Ｍがランダムに選択された場合には、パケットスケジューリング装置１１は図８（ｃ）の状態から図８（ｄ）の状態に遷移する。この際、ランダムアウトキュー８１が空になるため、キュー選択部８３，８４が選択するランダムアウトキューの切替えが起こる。
【００７８】このような制御により、例えばｗ１＝１００，ｗ２＝１００のように大きい値を持つ重みに対しては、スケジューリング情報管理部１６が第３の実施形態で述べたようなＦＩＦＯ構成の場合には、短い時間スケールではｗｅｉｇｈｔｅｄｆａｉｒとはなりにくいという欠点が解消され、どのような重みに対しても常に確率的にｗｅｉｇｈｔｅｄ ｆａｉｒなスケジューリングが可能となる。また、あるランダムアウトキューからスケジューリング情報を出力中は、別のランダムアウトキューへスケジューリング情報が入力されるため、空でない全てのパケットキューの先頭のパケットを一定時間内に出力することが保証される。
【００７９】ランダムアウトキュー８１，８２は図９のようなアルゴリズムで実現可能である。図９において、ｒは配列、ｐは配列の終りを示すポインタである。まず、初期化処理として、ポインタｐに−１をセットする。Ｅｎｑｕｅｕｅ（ｉ）操作は、ポインタｐを１だけインクリメントした後でｒ［ｐ］：＝ｉとすることにより実現される。次に、Ｄｅｑｕｅｕｅ操作について述べる。まず、ポインタｐが−１であればキューが空であるため返り値−１を変数ｉに記憶する。そうでなければ、０以上ｐ以下の疑似ランダム整数（Ｒａｎｄｏｍ（Ｏ，Ｐ））をｋとし、ｉ：＝ｒ［ｋ］によりＤｅｑｕｅｕｅの返り値を変数ｉに記憶した後、ｒ［ｋ］：＝ｒ［ｐ］とすることによりキューの最後尾の値を位置ｋに移し、ポインタｐを１だけデクリメントする。最後に、変数ｉの値を返す。このようなアルゴリズムにより、簡単な構成によりランダムアウトキューの管理ができる。
【００８０】（第６の実施形態）図１０に、本発明によるパケットスケジューリング装置を出力バッファ型ＡＴＭスイッチに適用した実施形態を示す。なお、本発明によるパケットスケジューリング装置は入力バッファ型や共通バッファ型のスイッチアーキテクチャにも適用可能である。
【００８１】図１０において、セル入力線１０１−１〜１０１−Ｎに到着した固定長パケットであるＡＴＭセルは、ＡＴＭセルのヘッダ情報を基にスイッチ１０２で交換出力され、パケット入力線１９−１〜１９−Ｎを介して上述したパケットスケジューリング装置１１−１〜１１−Ｎに入力される。パケットスケジューリング装置１１−１〜１１−Ｎは、パケット蓄積部としてＶＣコネクション単位のキューを持っており、入力されたセルはそのセルのヘッダに書かれているＶＣＩに対応するキューに格納される。パケットスケジューリング装置１１−１〜１１−Ｎは、各セルサイクルにおいて、キューにバッファリングされたセルのうち、１つを選択出力する。
【００８２】（第７の実施形態）図１１に、本発明において重みが動的に変化する場合のスケジューラのフローチャートを示す。なお、ハード構成は図３のようになる。
【００８３】重みが動的に変化する場合には、スケジューリング情報管理手段内のＶＣＩ＝ｉの個数は一時的に式（４）を満たさない場合がある。したがって、スケジューリング情報管理手段内のＶＣＩ＝ｉの個数ｎｉをカウントしておく必要がある。ｎｉの変更は、スケジューリング情報管理手段へのスケジューリング情報入力および出力時い行なう。
【００８４】また、セル出力時にＶＣＩ＝ｉをスケジューリングキューに入れるかどうかを判定する場合には、重みとキュー長を比較せずに、重いとスケジューリングキュー内のＶＣＩ＝ｉの個数および、キュー長とスケジューリングキュー内のＶＣＩ＝ｉの個数の比較を行ない、ｗｉ≧ｎｊかつｑｉ≧ｎｊのときに、ＶＣＩ＝ｉがスケジューリングキューに入れられる。これにより、重みが増加した結果、ｗｉ＞ｑｉとなった場合でもＶＣＩ＝ｉはスケジューリングキューに入れられるようになる。
【００８５】また、ｗｉ，＜ｑｉであるときにｗｉが増加した場合には、重みの増加分だけスケジューリング情報管理手段内のＶＣＩ＝ｉの個数も増加させる必要がある。この処理が図１１の重み対応処理である。図１１においては、重み変更対応処理はセル出力時に行なう例を示しているが、重み変更対応処理をセル入力時に行なうことも、セル入力時および出力時の両方で行なうことも、また、毎セル時間行なうことも可能である。
【００８６】重み変更対応処理においては、必要な回数だけEnqueue （ｉ）を実行するとともにｎｉをインクリメントする。ただし、重みの変更幅が大きいほどループの回数も増えるため、１回の処理に対するループの最大回数Ｃmax を決めておき、Ｃmax を越える分のループは次以降のセル時間に実行するようにする。
【００８７】（第８の実施形態）図１２に、本発明において重みが実数値をとり得る場合のスケジューラのフローチャートを示す。なお、ハード構成は図３のようになる。図１２においては、重みｗｉは１以上の実数値をとるものとする。重みとキュー長の比較の際には、ｗinowが使用される。ｗinowの値は、ｆｌｏｏｒ（ｗinow）の値がｆｌｏｏｒ（ｗi ）またはｆｌｏｏｒ（ｗi ）＋１のいずれかの値をとるように、かつｗinowの平均値がｗi と等しくなるように制御する。ここで、ｆｌｏｏｒ（ｘ）は、ｘ以下の最大の整数値を返す関数である。ｗinowの値は動的に変更されるため、第７の実施形態と同様に、スケジューリング情報管理部内のＶＣＩ＝ｉの個数ｎiをカウントしておく必要がある。
【００８８】ＶＣ設定時に、ｗinowの値はｗi に初期化され、また、変数ｆi がｗi の小数部分の値に設定される。図１２の例では、ｗinowの値の更新はセル出力時に行なわれる。すなわち、ｗinowの値はｆi ずつインクリメントされ、その結果、ｆｌｏｏｒ（ｗi ）＋１以上となった場合には１だけデクリメントされる。この処理が図１２の小数点処理である。また、ｗinowの動的な変更に伴い、第７の実施形態と同様に重み変更対応処理が必要となる。図１２では、重み変更対応処理の中でｗi の代わりにｗinowが用いられる。なお、ｗinowの値は小数点処理によって変更されるだけでなく、第７の実施形態のようにｗi の動的な変更に伴って変更される場合もあるが、本実施例はそのような変更も許容するような構成となっている。
【００８９】なお、小数点処理、および重み変更対応処理はセル出力時だけでなく、セル入力時に行なうことも、セル入力時および出力時の両方で行なうことも、また、毎セル時間行なうことも可能である。このように重みが実数値をとれるようにすることにより、重みの値が大きくならないようにできるためスケジューラの性能劣化を抑えることができる。
【００９０】（第９の実施形態）図１３に、本発明においてスケジューリング情報管理手段が、パケットが所属するクラス別に設定される重みに基づいてクラスのスケジューリングを行ない、かつ、クラス別の重みをそのクラス内のコネクションのキューの状態に応じて変更する場合の実施形態を示す。
【００９１】クラス別スケジューラは速度クラス、ＱＯＳクラス、仮想パス、またはそれらの組合せ毎に用意される。クラス別スケジューラは重みとキュー長とを用いたスケジューリングを行なう。クラススケジューラは従来方式のスケジューラでもよい。
【００９２】クラススケジューラは各クラスｉ毎に重みφi を管理する。クラス重みφi は、
となるように制御する。ただし、Ｂi はクラスｉのＶＣの中でＶＣキューが空でないＶＣＩの集合である。また、Ｗi はクラスｉに接続中のＶＣに関するｗjの和である。したがって、パケットキューが空のＶＣ数が多いほどφi は小さくなる。これにより、スケジューラを階層化した場合でもクラススケジューラはクラス内のＶＣの状態を考慮したスケジューリングが可能になる。
【００９３】ただし、φi の値が変わった場合には、それに合わせてクラススケジューラ内の状態も更新する必要がある。例えば、クラススケジューラがＳＣＦＱのようにバーチャルタイムを用いたスケジューラである場合、スケジューリング情報の再ソーティングが行なわれる。この場合のフローチャートを図１４に示す。ハード構成は図６のようになる。
【００９４】図１４では重みが実数値をとることができ、また、動的な重みの変更も可能である。まず、初期化処理ですべてのクラスｉ重みの和Ｗi およびキュー長が０にリセットされる。
【００９５】次に、クラスｉのＶＣＩ＝ｊのＶＣの接続要求があった場合には、ｑi 、ｎiを０にリセットし、重みの小数部分をｆj に設定し、重みの初期値ｗjnowをｗjに設定する。また、クラスｉの重みをｗj だけインクリメントする。また、クラスｉのＶＣＩ＝ｊのＶＣの切断要求があった場合には、クラスｉの重みをｗj だけデクリメントする。
【００９６】セル入力時には、クラスｉのＶＣＩ＝ｊのＶＣのキュー長ｑj が０である場合には、クラスｉの重み現在のφ1 の値を変数φ´1 に記憶するとともに、φ1 をｗj ／Ｗi だけインクリメントする。次に、φ1 の変更に伴いクラスｉに対する評価値Ｆi の値の更新を行なう。更新される値は現在のＦi の値に対して１／φ´i −１φi だけ小さくなるが、現在ソートされている評価値の中での最小値Ｆよりも小さい値に更新されてしまうような場合には、Ｆi の値をＦから１φi だけ大きい値に設定する。また、クラスｉのキュー長Ｑi が０である場合も同様にＦi の値をＦから１φ／1 だけ大きい値に設定する。その後、ｑj 、Ｑi の値をインクリメントし、ｑi ≦ｗjnowの場合にはスケジューリングキューにＶＣＩ＝ｊを入れ、ｎi の値をインクリメントする。
【００９７】セル出力時には、ソートされている中で最も小さい評価値をもつクラス（ｉ）からＶＣＩ（＝ｊ）を取り出すとともに、ｑj 、Ｑi をデクリメントする。次に図１２と同様の小数点処理を行なう。ｑj ＝０であればクラスｉの重みφi をｗj ／Ｗi だけデクリメントする。次に、Ｑi ＞０であればクラスｉの評価値Ｆiを１／φi だけインクリメントする。次に、ｗjnow≧ｎj であれば、ＶＣＩ＝ｊをクラスｉのスケジューリングキューに再入力（Ｅｎｑｕｅｕｅ（ｉ，ｊ））し、そうでなければｎj を１だけデクリメントする。最後に、ｗjnowの更新に伴って図１２と同様の重み変更対応処理を行ない、ＶＣＩ＝ｊのＶＣキューの先頭からセルを出力するためにＶＣＩレジスタにｊを設定する。
【００９８】このような構成により、重みが大きいコネクションと重みが小さいコネクションを別のクラスに分けて管理することができるため、重みが大きいコネクションの重みの絶対値が小さくなり、階層化しない場合に比べてスケジューラの性能劣化を抑えることができる。
【００９９】
【発明の効果】以上説明したように、本発明のスケジューリング装置によれば、重みのみでなくパケット蓄積料も用いたきめ細かなパケットスケジューリングが可能となる。従って、例えば重みの大きいコネクション群と重みの小さいコネクション群があって、それぞれのコネクション群の重みの和が等しい場合にも、重みの大きいコネクション群が小さい時間スケールで優位に扱われるという不都合を抑制することができ、コネクションの重みによらず公平なパケットスケジューリングが可能となる。
【０１００】また、特に固定長パケットを扱う場合には、スケジューリング情報管理部において各パケットキュー（パケット蓄積部）に対応した重みとキュー長（パケット蓄積量）のうちの小さい方の値に等しい個数のスケジューリング情報を常に保持することにより、スケジューリング情報管理部がパケットのスケジューリングに必要な処理時間をコネクション数に関係なく一定値にすることができ、入力トラヒックにほとんど依存せずに確率的に公平なＷＦＱも実現可能となる。
【０１０１】さらに、スケジューリング情報管理部においてクラス別にキューを設ければ、各クラス内あるいはクラス間のパケットスケジューリングに対して上記と同様の効果が期待できる。
【図面の簡単な説明】
【図１】 本発明の一実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図２】 本発明の他の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図３】 本発明におけるスケジューリング情報管理部の実現例をしめすブロック図。
【図４】 図３のスケジューリング情報管理部の動作を示すフローチャート。
【図５】 本発明の別の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図６】 本発明におけるスケジューリング情報管理部の他の実現例を示すブロック図。
【図７】 図６のスケジューリング情報管理部の動作を示すフローチャート。
【図８】 本発明のさらに別の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図９】 ランダムアウトキューの実現例。
【図１０】 重みが動的に変化する場合のスケジューリングアルゴリズム。
【図１１】 重みが動的に変化する場合のスケジューリングアルゴリズム。
【図１２】 重みが実数値をとり得る場合のスケジューリングアルゴリズム。
【図１３】 スケジューラの階層化構成。
【図１４】 クラススケジューラがクラス内のコネクションのキューの状態によってクラスの重みを変更する場合のスケジューリングアルゴリズム。
【符号の説明】
１１，１１−１〜１１−Ｎ…パケットスケジューリング装置
１２，１３，１４…パケットキュー（パケット蓄積部）
１５…パケット入力部
１６…スケジューリング情報管理部
１７…パケット出力部
１８…パケット
１９，１９−１〜１９−ｎ…パケット入力線
２０，２０−１〜２０−Ｎ…パケット出力線
２１…ＶＣＩ（スケジューリング情報）
３１…プロセッサ
３２…ＲＯＭ
３３…ＶＣＩメモリ
３４…キュー長メモリ
３５…重みメモリ
３６…状態レジスタ
３７…ＶＣＩ出力レジスタ
３８…ＶＣＩ出力レジスタ
３９…データバス
４０…制御バス
６１…クラスレジスタ
８１，８２…ランダムアウトキュー
８３，８４…キュー選択部
９１…レジスタ
９２…シフト信号生成回路
９３…セレクト信号生成回路
９４…セレクタ信号線
９５…シフト信号線
９６…アドレス入力線
９７…データ入力線
９８…読み出し可能信号線
９９…書き込み可能信号線
９１０…データ出力線
９１１…シフト信号生成可能信号線
９１２…データシフト線
１０１−１〜１０１−Ｎ…セル入力線
１０２…ＡＴＭスイッチ
【０００１】
【発明の属する技術分野】本発明は、ＡＴＭ網のようなパケット網においてバッファリングされたパケットを選択出力するためのパケットスケジューリング装置に関する。
【０００２】
【従来の技術】ＡＴＭ（Asynchronous Transfer Mode：非同期転送モード）方式を用いたパケット網では、セルと呼ばれる５３オクテットの固定長のパケットが伝送される。ＡＴＭ方式においては、セルのヘッダ部に書かれたＶＣＩ（Virtual Channel Identifier：バーチャルチャネル識別子）、ＶＰＩ（Virtual Path Identifier ：バーチャルパス識別子）と呼ばれる識別子によりコネクションが識別される。
【０００３】また、ＡＴＭ方式ではコネクションが属するサービスクラスが定義される。サービスクラスには、ＣＢＲ（Constant Bit Rate ：固定ビットレート）、実時間ＶＢＲ（Variable Bit Rate ：可変レート）、非実時間ＶＢＲ、ＡＢＲ（Available Bit Rate：アベイラブル・ビットレート）、ＵＢＲ（Unspecified Bit Rate：アンスペシファイド・ビットレート）がある。そして、これらの各サービスクラスに対して、必要なセル廃棄率やセル遅延に関するＱＯＳ（Quality of Service：サービス品質）が規定される。すなわち、ＣＢＲ、実時間ＶＢＲおよび非実時間ＶＢＲでは、セル廃棄率、セル遅延の両方に関する要求値が規定される。ＡＢＲではセル廃棄率に関する要求値のみ規定され、ＵＢＲではＱＯＳは規定されない。
【０００４】ユーザは、コネクション設定時にコネクションのトラヒック特性に関するパラメータを網に申告する。網はこの申告パラメータを守ってセルを送出するコネクションに対して、要求するＱＯＳを保証できる場合にコネクションを設定する。申告パラメータとしては、ＣＢＲに関してはピークセルレートが、実時間ＶＢＲおよび非実時間ＶＢＲに関してはピークセルレート、平均セルレートや最大バースト長がそれぞれ用いられる。
【０００５】網は、これらの申告パラメータ通りにセルを送出しているコネクションに対しては、たとえパラメータに違反して送出するコネクションがあっても、その影響を受けずにＱＯＳを保証する必要がある。このための制御として、網の入口でコネクションの送出レートを監視し、パラメータに違反してセルを送出するコネクションに対しては入力規制を行なうＵＰＣ（Usage Parameter Control ：使用量パラメータ制御）がある。ＵＰＣを適切に行なえば、ＡＴＭ交換機は複数のコネクションのセルを単一もしくはクラス別のＦＩＦＯ（First-In First-Out：先入れ先出し）キューにより管理することで、申告パラメータ通りにセルを送出しているコネクションに対して、他のコネクションの影響を受けずにＱＯＳを保証することができる。
【０００６】しかし、ＡＢＲのように端末が送出可能なセルレートがコネクション接続中に網の状態によって動的に変動する場合には、正確なＵＰＣは難しいため、他のコネクションの影響を受けやすくなる。また、ＵＢＲに対してはＵＰＣを行なうことを想定していないが、ＵＢＲクラス内のコネクション間で、できるだけ公平に帯域を使用するような制御を行なうことが望ましい。このため、ＡＢＲ／ＵＢＲに対しては、単一もしくはクラス別のＦＩＦＯキューによる管理よりも、コネクション毎にキューを設けて、複数のキューの間でパケットのスケジューリングを行なうことが必要となる。
【０００７】このパケットスケジューリング方式として、あるクラスのコネクション間で全て等しい割合で公平にサービスを行なうＦＱ（Fair Queueing ）と呼ばれる方式が文献１：John B.Nagle, "On Packet Switches with Infinite Storage", IEEETransactions on Communications, Vol. COM-35, No.4,pp.435-438,April 1987. で提案されている。ＦＱ方式は、アクティブな（空でない）キューをラウンドロビンでサービスすることにより実現されるものであるが、コネクション毎に要求される帯域が異なる場合には適当でない。また、パケットが可変長である場合にはパケット長を考慮する必要がある。
【０００８】そこで、コネクション毎に各々の使用帯域に関する重みを与え、重みに応じた割合でパケット長を考慮して公平にキューのサービスを行なうことでパケットのスケジューリングを行なうＷＦＱ（Weighted Fair Queueing）と呼ばれるスケジューリング方式に関する検討がなされている。ＷＦＱのアルゴリズムについては、ＳＣＦＱ（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 '90pp. 19-29, 1990. で提案されている。
【０００９】今、パケットスケジューリング装置がコネクション毎にキューを持ち、コネクションは識別子により識別されるものとすると、ＳＣＦＱではコネクションｉ毎に使用帯域に比例した重みｗｉと変数Ｆｉを持ち、パケットがパケットスケジューリング装置に到着すると変数Ｆｉの値の更新を行ない、更新した変数Ｆｉを到着パケットと一緒にキューに格納する。パケット出力時には、アクティブなキューの先頭のパケットの変数Ｆｉの中から最小のＦｉを持つコネクションのパケットをサービスする。変数Ｆｉの更新は、Ｆｉ ＝Ｌ／ｗｉ＋ｍａｘ（Ｆｉ，ｖ（ｔａ））
に従って行なわれる。但し、Ｌは到着パケットのパケット長、ｔａはパケットの到着時刻、ｖ（ｔａ）は時刻ｔａにおいてサービス中またはサービス直後のコネクションｊのパケットの変数Ｆｊの値を返す関数である。
【００１０】
【発明が解決しようとする課題】しかしながら、上述したＳＣＦＱやバーチャルクロックのようなアルゴリズムによるパケットのスケジューリング方式では、２つの問題点がある。第１の問題点は、重みの差が大きいコネクションのパケット同士がスケジューリングされる場合に、小さい時間スケールで公平になりにくいことである。例えば、重み１のコネクション１００本と、重み１００のコネクション１本のパケットがぞれぞれ１個ずつ合計１０１個、各コネクション対応のキューに存在し、その状態で重み１００のコネクションのパケットが連続して到着するものとする。このとき公平を期するとすると、理想的には重み１の１００本のコネクションのパケットと重み１００の１本のコネクションのパケットは交互にスケジューリングされるべきにもかかわらず、ＳＣＦＱやバーチャルクロックでは、重み１００のコネクションから先に最大１００個のパケットが出力された後で、重み１のコネクションのパケットが出力される。すなわち、重みの大きいコネクション群と重みの小さいコネクション群があって、それぞれのコネクション群の重みの和が等しい場合には、常に重みの大きい方のコネクション群のパケットが小さい時間スケールで優位に扱われてしまうという不都合がある。
【００１１】第２の問題点は、ＳＣＦＱやバーチャルクロックでは前述したようにパケットのスケジューリング時に変数Ｆｉの最小値を計算で求める必要があるが、このための計算時間がコネクション数とともに増大することである。今、変数Ｆｉを常にソートしておくものとすると、コネクション数がｎのときに最小値を求めるのに必要な計算時間は、ソートされたＦｉの系列に新しいＦｉを挿入する時間、すなわちｏ（ｌｏｇ2 ｎ）のオーダとなる。ＡＴＭの場合、ｌ物理リンクあたりの最大のバーチャルコネクション（ＶＣ）数ｎ＝４０９６をサポートするには、変数Ｆｉの最小値を計算するとき最大ｌｏｇ2 ４０９６＝１２回のサーチが必要となる。このような計算時間の増大から、パケットのみでなくクラスおよびバーチャルパス（ＶＰ）のスケジューリングも行なう場合や、リンク速度が大きい場合を考慮すると、ＳＣＦＱやバーチャルクロックは実装が困難である。従って、スケジューリングに必要な処理時間がコネクション数に関係なく小さい値であることが望まれる。
【００１２】一方、米国特許第５，３７９，２９７号明細書"Concurrent Multi-Channel Segmentation and Reassmbly Processors for Asynchronous Transfer Mode" には、ピークレート毎にキューを構成することにより、コネクション数に関係ない処理時間で複数のキューの間でＷＦＱを行なう方式が開示されているが、この方式では任意のピークレート（重み）の組み合わせをサポートできない。
【００１３】本発明は、上記のような従来技術の問題点を解決し、コネクションの重みによらず公平なスケジューリングを可能としたパケットスケジューリング装置を提供することを目的とする。
【００１４】また、本発明は受信パケットが固定長パケットの場合に、スケジューリングに必要な処理時間がコネクション数に関係なく一定値となるようなパケットスケジューリング装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】上記の課題を解決するため、本発明は入力されるパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積部と、パケット受信時に複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力部と、複数のパケット蓄積部にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積部のパケット蓄積量と該パケット蓄積部に設定された重みとに基づいて管理するスケジューリング情報管理部と、パケット送信時にスケジューリング情報管理部が管理するスケジューリング情報を基に所望のパケット蓄積部から所望のパケットを出力するパケット出力部とを有することを基本的な特徴とする。
【００１６】このように本発明では、スケジューリング情報管理部において、パケット蓄積部からパケットを読み出す際に用いるスケジューリング情報をパケット蓄積量とそのパケット蓄積部に設定された重みと基づいて管理するため、アクティブなパケット蓄積部に対応する重みの値だけでなく、アクティブなパケット蓄積部のパケット蓄積量も考慮してパケットのスケジューリングが行なわれる。
【００１７】ここで、それぞれのパケット蓄積部に設定される重みとして、例えばパケット蓄積部に対応したコネクションに設定されている帯域の重みを用いた場合、パケット蓄積量に比例した評価値が重み以下のコネクションは、重みに相当する分の帯域をフルに使用せず、他のコネクションに帯域を与えることができるため、コネクションの重みによらず公平なスケジューリングが可能となる。すなわち、重みの大きいコネクション群と重みの小さいコネクション群が存在し、それぞれのコネクション群の重みの和が等しい場合においても、重みの大きいコネクション群が小さい時間スケールで優位に扱われることが抑制される。また、任意の重みの組合せをサポートできる。
【００１８】また、本発明は特に固定長パケットをスケジューリングする際、パケット蓄積量が蓄積されたパケットの数に比例することから、スケジューリング情報管理部において複数のパケット蓄積部にそれぞれ対応したスケジューリング情報を該パケット蓄積部スケジューリング情報をパケット蓄積部のパケット蓄積量とそのパケット蓄積部に設定された重みのうちの小さい方の値に等しい個数だけ常に保持することを特徴とする。
【００１９】この場合、スケジューリング情報管理部へのスケジューリング情報の入力はパケットの受信時と送信時に行ない、その際に必要な処理としては基本的にそのパケットを蓄積しているパケット蓄積部のパケット蓄積数と設定された重みを比較して小さい方を調べるのみでよい。このようにすることにより、パケットが固定長であることを利用してスケジューリングに必要な処理時間がコネクション数に依存せず一定のパケットスケジューリングを実現できる。また、このようにスケジューリング情報管理部が保持するスケジューリング情報の個数をパケット蓄積数と重みのうちの小さい方の値を上限とすることにより、パケット蓄積量と重みの両方を考慮したパケットスケジューリングが上記と同様に可能になるため、重みによらず公平なスケジューリングを行なうことができる。さらに、スケジューリング情報管理部から読み出すスケジューリング情報の選び方を変えれば、様々なポリシーに基づいたパケットスケジューリングが可能となる。
【００２０】また、本発明では複数クラスおよび仮想パスのスケジューリングをサポートするパケットスケジューリング装置を実現する場合、スケジューリング情報管理部において、パケットが属するクラス別または仮想パス別にスケジューリング情報を管理することを特徴とする。さらに、クラス別または仮想パス別に重みを設定し、これを各クラスまたは仮想パス内のコネクション別のキュー長が０から正の値に変化したときまたは、正の値から０に変化したときに変更することにより、クラス間または仮想パス間でのパケットスケジューリングと同一クラスまたは同一仮想パス内のパケットスケジューリングの両方において、上述と同様の作用が得られる。
【００２１】スケジューリング情報管理部は、少なくとも一つのＦＩＦＯキューあるいはランダムアウトキューで構成される。スケジューリング情報管理部をＦＩＦＯキューで構成した場合は、スケジューリング情報管理部がパケットをスケジューリングするために必要な処理時間がコネクション数に関係なく一定となり、かつスケジューリング情報管理部のハードウエア構成も簡単になる。また、スケジューリング情報管理部をランダムアウトキューで構成した場合は、スケジューリング情報管理部がパケットをスケジューリングするために必要な処理時間がコネクション数に関係なく一定となる上、入力トラヒックにほとんど依存せず確率的に公平なスケジューリングが可能となる。
【００２２】
【発明の実施の形態】
（第１の実施の形態）図１に、本発明の第１の実施形態に係わるパケットスケジューリング装置の構成を示す。
【００２３】本実施形態におけるパケットスケジューリング装置１１は、パケット蓄積部である複数のパケットキュー１２，１３，１４と、パケット受信時にパケットキュー１２，１３，１４にパケットを入力するためのパケット入力部１５と、パケットキュー１２，１３，１４に蓄積されたパケット１８を読み出す順序を指定するためのスケジューリング情報を管理するスケジューリング情報管理部１６と、パケット送信時にスケジューリング情報管理１６が管理するスケジューリング情報に基づきパケットキュー１２，１３，１４から所望のパケットを読み出して出力するパケット出力部１７と、受信パケットをパケットスケジューリング装置１１に入力するためのパケット入力線１９と、送信パケットをパケットスケジューリング装置１１から出力するためのパケット出力線２０を有する。
【００２４】次に、パケットスケジューリング装置１１の動作を説明する。パケットスケジューリング装置１１で受信されたパケットは、パケット入力線１９からパケット入力部１５に入力される。パケット入力線１９は一般に複数本存在する。パケット入力部１５は、パケット入力線１９から入力されたパケットを該パケットのヘッダ情報を基にパケットキュー１２，１３，１４のうちの所望の一つに入力する。ここで、受信パケットがユニキャストパケットの場合には、いずれか１つのパケットキューにパケットが入力されるが、パケットスケジューリング装置１１でマルチキャストをサポートする場合には、マルチキャストすべき複数のパケットキューにパケットが入力される。
【００２５】パケットキュー１２，１３，１４は、ＶＣ（バーチャルチャネル）コネクション毎、トラヒッククラス毎、出力リンク毎、あるいはこれら２つ以上の組み合わせ等、種々の単位で設けることができるが、本実施形態ではＶＣコネクション毎にパケットキュー１２，１３，１４が設けられているものとする。これらのＶＣコネクションには、それぞれ要求された帯域が設定されている。
【００２６】スケジューリング情報管理部１６は、パケットキュー１２，１３，１４に蓄積されているパケットを読み出す順序を指定するためのスケジューリング情報であるＶＣＩ（バーチャルチャネル識別子）をパケット入力部１５から入力し、パケット出力部１７へ出力する。この際、スケジューリング情報管理部１６は各パケットキュー１２，１３，１４に対して、そのパケットキューのパケット蓄積量（以下、キュー長という）と、そのパケットキューに対応した重みとに基づいてスケジューリング情報であるＶＣＩを管理し、これらキュー長と重みに従ってパケット出力部１７へのスケジューリング情報の出力順序を決定する。
【００２７】本実施形態では、各パケットキューに対応したＶＣコネクションに設定された帯域の比に等しい重みを各パケットキューに割り当てる。ここで、ＶＣＩ＝ｉで識別されるパケットキューに対応するＶＣコネクションに設定された帯域の重みをｗｉ、同パケットキューのキュー長をバイト数で表わしてｑｉとする。スケジューリング情報管理部１６は、ＶＣＩ＝ｉのパケットがパケット入力部１５に到着したとき、あるいはＶＣＩ＝ｉのパケットがパケット出力部１７から出力されるときに式（１）で表される変数Ｆｉを更新し、次に出力すべきパケットのＶＣＩを決定する。
【００２８】Ｆｉ＝ｆ（ｑｉ，ｗｉ）
ここで、関数ｆはスケジューリングのポリシーに依存して決定される。例えば関数ｆを式（２）とすれば、キュー長ｑｉが重みｗｉ以下の場合には、重みｗｉに応じた帯域はＶＣコネクションｉに与えられず、他のコネクションに帯域を与えることが可能となる。
【００２９】
【数１】
なお、関数ｆを式（３）とすれば、スケジューリングがキュー長ｑｉに依存しない従来のＳＣＦＱ方式となる。
【００３０】
【数２】
【００３１】但し、式（２）（３）においてＬは到着パケットのパケット長、Ｌｍｉｎはパケットスケジューリング装置１１で扱う最小パケット長、ｔａはパケットの到着時刻、ｖ（ｔａ）は時刻ｔａにおいてサービス中またはサービス直後のＶＣコネクションｊのパケットの変数Ｆｊの値を返す関数である。
【００３２】パケット出力部１７は、パケット送信時にスケジューリング情報管理部１６からＶＣＩを１つ取り出した後、そのＶＣＩに対応するパケットキューからパケットを取り出してパケット出力線２０へ出力する。
【００３３】このように本実施形態によれば、スケジューリング情報管理部１６において、スケジューリング情報であるＶＣＩをパケットキュー１２，１３，１４のキュー長と設定された重みとに基づいて管理するため、アクティブなパケットキューに設定されている重みの値だけでなく、そのパケットキューのキュー長も考慮したきめ細かなパケットスケジューリングを行なうことができる。
【００３４】従って、各パケットキュー１２，１３，１４に対応するＶＣコネクションに設定されている帯域の重みを各パケットキュー１２，１３，１４に設定すれば、キュー長に比例した評価値が重み以下のＶＣコネクションが重みに相当する分の帯域をフルに使用せず、他のコネクションに帯域を与えることができるため、重みの大きいコネクション群と重みの小さいコネクション群が存在し、それぞれのコネクション群の重みの和が等しい場合においても、重みの大きいコネクション群が小さい時間スケールで優位に扱われることが抑制され、コネクションの重みによらず公平なパケットスケジューリングが実現されるという効果が得られる。
【００３５】（第２の実施形態）次に、第１実施形態をより具体化した第２の実施形態に係わるパケットスケジューリング装置について図２を用いて説明する。本実施形態はＡＴＭセルのような固定長パケットのスケジューリングを行なう例であり、Ｍ個のパケットキューを有し、またスケジューリング情報としては第１の実施形態と同様にＶＣＩを用いるものとする。図２において、図１R>１と相対応する部分には同一符号を付して第１の実施形態との相違点を中心に説明する。
【００３６】本実施形態においては、スケジューリング情報管理部１６はＭ個のパケットキュー１２，１３，１４に対応したＶＣＩ２１を各パケットキューに対してキュー長と設定された重みのうち小さい方の値に等しい個数だけ常に保持する。
【００３７】また、本実施形態では各パケットキュー１２，１３，１４に対応するコネクションにそれぞれ設定された帯域の比に等しい重みｗ１，ｗ２，ｗＭを各パケットキュー１２，１３，１４に設定する。ここで、ＶＣＩ＝ｉで識別されるパケットキューに対応するコネクションに設定された帯域の重みをｗｉとし、該パケットキューのキュー長をｑｉとする。
【００３８】スケジューリング情報管理部１６は、保持されているスケジューリング情報であるＶＣＩ＝ｉの個数をｎｉとすると、以下の関係式が常に成立するように制御される。
【００３９】
ｎｉ＝ｍｉｎ（ｑｉ，ｗｉ） …（４）
このとき、ｆ（ｑｉ，ｗｉ）＝ｍｉｎ（ｑｉ，ｗｉ）となる。ここで、パケットキュー１２，１３，１４に対して設定される重みをｗ１＝ｗ２＝ｗＭ＝１とおけば、文献４：John B.Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Vol. COM-35, No.4,April 1987. と同様のFair Queueing が実現できる。
【００４０】また、ｗ１＝２，ｗ２＝１，ｗＭ＝３とすると、図２においてはパケットキュー１２，１３，１４のキュー長はｑ１＝３，ｑ２＝２，ｑＭ＝０であるため、ｎ１＝２，ｎ２＝１，ｎＭ＝０となる。なお、図２においてパケットキュー１２，１３，１４の中に記された○印がパケットを表わし、この○印の数がキュー長を評価している。
【００４１】パケット出力部１７は、パケット送信時にスケジューリング情報管理部１６からＶＣＩを１つ取り出した後、そのＶＣＩに対応するパケットキューからパケットを取り出してパケット出力線３０からパケットを出力する。
【００４２】図３に、本実施形態におけるスケジューリング情報としてＶＣＩを用いるスケジューリング情報管理部１６の構成例を示す。このスケジューリング情報管理部１６は、プロセッサ（ＭＰＵ）３１、ＲＯＭ３２、ＶＣＩメモリ３３、キュー長メモリ３４、重みメモリ３５、状態レジスタ３６、入力ＶＣＩレジスタ３７、出力ＶＣＩレジスタ３８、データバス３９および制御バス４０を有する。これら各部の機能は、次の通りである。
【００４３】ＭＰＵ３１は、ＲＯＭ３２にプログラムされた命令を逐次実行する。ＶＣＩメモリ３３は、スケジューリング情報であるＶＣＩを格納するためのキューであり、ＲＡＭによって構成される。スケジューリング情報管理部１６がＦＩＦＯキューで構成されている場合には、ＶＣＩメモリ３３はリンクドリストまたはリングバッファのいずれの方式で実装してもよい。
【００４４】キュー長メモリ３４は、パケットキュー１２，１３，１４毎の現在のキュー長を記憶するメモリであり、ＲＡＭによって構成される。重みメモリ３５は、パケットキュー１２，１３，１４毎に設定されている重みを記憶するメモリであり、ＲＡＭによって構成される。
【００４５】状態レジスタ３６は、スケジューリング情報管理部１６の動作状態を示す情報を格納するためのレジスタであり、図示しない外部装置により書き込みがなされ、ＭＰＵ３１が該レジスタ３６の値を参照する。なお、各セルスロットにおいて、入力セルがある場合には状態レジスタ３６の値は１となり、セル入力処理終了後状態レジスタ３６の値は２となる。
【００４６】入力ＶＣＩレジスタ３７は、スケジューリングされるパケットのＶＣＩを格納するためのレジスタであり、外部装置により書き込みがなされ、ＭＰＵ３１が該レジスタ３７の値を参照する。
【００４７】出力ＶＣＩレジスタ３８は、出力されるパケットのＶＣＩを格納するためのレジスタであり、ＭＰＵ３１から書き込みがなされ、図示しない外部装置が該レジスタ３８の値を参照する。出力ＶＣＩレジスタ３８に負の値が書き込まれる場合は、パケットは出力されないものとする。
【００４８】ＭＰＵ３１と、各メモリ３３，３４，３５および各レジスタ３６，３７，３８との間でやりとりされるデータは、データバス３９上を流れる。また、制御バス４０を用いて、アドレス指定等のデータアクセスのための制御情報のやりとりを行なう。
【００４９】次に、図４に示すフローチャートを用いて図３のスケジューリング情報管理部１６内で実行されるスケジューリングアルゴリズムを説明する。図４において、Ｅｎｑｕｅｕｅ（ｉ）はＶＣＩ＝ｉをＶＣＩメモリ３３に書き込む操作を表し、ＤｅｑｕｅｕｅはＶＣＩメモリ３３からＶＣＩを読み出す操作を表す。なお、図４のスケジューリングアルゴリズムはコード化されて図３のＲＯＭ３２内に格納される。
【００５０】まず、状態レジスタ３６の値ｓをＭＰＵ３１で参照し（ステップＳ１０１）、ｓが１，２のいずれか、またはｓが１、２のいずれでもないかどうかを調べる（ステップＳ１０２）。ｓ＝１であれば、ＶＣＩ入力レジスタ３７の値ｉを参照し（ステップＳ１０３）、ＶＣＩ＝ｉのパケットキューのキュー長＋１をｑとし（ステップＳ１０４）、またＶＣＩ＝ｉのパケットキューに設定された重みをｗとして（ステップＳ１０５）、ｑ、ｗの大小関係を調べる（ステップＳ１０６）。ここで、ｑ≦ｗの場合にはステップＳ１０７においてＥｎｑｕｅｕｅ（ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込み、その後にステップＳ１０８に移り、またｑ＞ｗの場合には直接ステップＳ１０８に移る。ステップＳ１０８では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとする。
【００５１】一方、ステップＳ１０２においてｓ＝２であれば、ステップＳ１０９においてｉ：＝Ｄｅｑｕｅｕｅ、つまりＶＣＩメモリ３３からＶＣＩを読み出した後、ＶＣＩ＝ｉのパケットキューのキュー長−１，０のうち大きい方をｑとし（Ｓ１１０）、さらにＶＣＩ＝ｉのパケットキューに設定された重みをｗとして（Ｓ１１１）、ｑ，ｗの大小関係を調べる（Ｓ１１２）。ここで、ｑ≧ｗの場合にはステップＳ１１３においてＥｎｑｕｅｕｅ（ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込み、その後にステップＳ１１４に移り、またｑ＜ｗの場合には直接ステップＳ１１４に移る。ステップＳ１１４では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとし、さらに次のステップＳ１１５でＶＣＩ出力レジスタ３８の値をｉとする。
【００５２】そして、ステップＳ１０２においてｓが１、２のいずれでもない場合と、ステップＳ１０８，Ｓ１１５の処理の終了後、ステップＳ１１６で状態レジスタ３６の値を０としてステップＳ１０１に戻り、以上の処理を繰り返す。
【００５３】このようなアルゴリズムにより、ＶＣＩメモリ３３内の各ＶＣＩ＝ｉの個数について常に式（４）が成立する。このように本実施形態では、スケジューリング情報管理部１６においてＶＣＩメモリ３３に各パケットキュー１２，１３，１４毎にキュー長と設定されている重みとを比較して、これらのうち小さい方の値同じ個数のＶＣＩ２１をスケジューリング情報として保持するため、第１の実施形態の効果に加えて、スケジューリングに必要な処理時間がＶＣコネクション数に依存せず一定のパケットスケジューリングを実現できるという効果がある。
【００５４】（第３の実施形態）次に、第２の実施形態においてスケジューリング情報管理部１６をＦＩＦＯキューで構成した場合の第３の実施形態に係わるパケットスケジューリング装置の構成と動作を図５を用いて説明する。図５において、ＣＶＩ＝１，１，２の順番でパケットキュー１２，１３，１４からパケットが出力される。ここで、スケジューリング情報管理部１６がリングドリストを用いたＦＩＦＯキュー構成の場合には、図３に示したフローチャート中のＥｎｑｕｅｕｅ（ｉ）はリストの最後尾にｉを追加する操作を表わし、Ｄｅｑｕｅｕｅはリストの先頭から値を取り出すとともに、リストの先頭を更新する操作を表す。リストが空の場合は、Ｄｅｑｕｅｕｅは負の値とする。
【００５５】まず、パケットがパケット入力部５から入力された場合の動作例を述べる。図５（ａ）の状態でＶＣＩ＝Ｍがパケット入力部１５から入力された場合、パケット入力直後はＶＣＩ＝Ｍに対応するパケットキュー１４のキュー長ｑＭと、このパケットキュー１４に設定された重みｗＭの大小関係はｑＭ＝１＜ｗＭ＝３であるため、ＶＣＩ＝Ｍがスケジューリング情報管理部１６の最後尾に追加される。また、図５（ａ）の状態でＶＣＩ＝１のパケットがパケット入力部１５から入力された場合、パケット入力直後はＶＣＩ＝１に対応するパケットキュー１１のキュー長ｑ１と、このパケットキュー１１に設定された重みｗ１の大小関係はｑ１＝４＞ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６の最後尾に追加されない。
【００５６】次に、パケットがパケット出力部１７から出力された場合の動作例を述べる。ここで、ｗ１＝１，ｗＭ＝３に設定されているものとする。図５（ａ）の状態でＶＣＩ＝１のパケットがパケット出力部１７から出力された直後はｑ１＝ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６に再度入力される。このとき、ＶＣＩ＝１はスケジューリング情報管理部１６の最後尾に追加され、図５（ｂ）の状態になる。次に、図５（ｂ）の状態でＶＣＩ＝１のパケットがパケット出力部１７から出力されるが、パケット出力直後はｑ１＝１＜ｗ１＝２であるため、ＶＣＩ＝１はスケジューリング情報管理部１６に再入力されない。
【００５７】このように本実施形態によれば、スケジューリング情報管理部１６をＦＩＦＯキューで構成したことにより、スケジューリング情報管理部１６がパケットをスケジューリングするために必要な処理時間がＶＣコネクション数に関係なく一定となり、かつスケジューリング情報管理部１６のハードウエア構成が簡単になるという効果がある。
【００５８】（第４の実施形態）図６に、本発明の第４の実施形態におけるスケジューリング情報管理部１６の構成例を示す。なお、スケジューリング情報管理部１６はクラス毎にスケジューリング情報を管理するものとする。ここでのクラスは速度クラス、サービスクラス、それらの組合せのいずれでもよい。また仮想パス別にスケジューリング情報を管理する場合についても同様の構成となる。図６において、図３と同一部分に同一符号を付して説明すると、本実施形態においては図３の構成に加えてクラスレジスタ６１が新たに設けられる。
【００５９】このクラスレジスタ６１は、パケットが属するクラスの番号を格納するためのレジスタであり、図示しない外部装置から書き込みがなされ、ＭＰＵ３１が該レジスタ６１の値を参照する。また、入力ＶＣＩレジスタ３７はＶＣＩをクラス別に格納するためのキューであり、ＲＡＭにより構成される。入力ＶＣＩレジスタ３７から読み込まれた入力ＶＣＩは、クラスレジスタ６１から読み込んだクラス番号のクラスに対応したＶＣＩメモリ３３内のキューに書き込まれる。
【００６０】次に、図７に示すフローチャートを用いて図６のスケジューリング情報管理部１６内で実行されるスケジューリングアルゴリズムを説明する。図７において、Enqueue （ｃ，ｉ）はＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込む操作を表し、Dequeue （ｃ）はＶＣＩメモリ３３のクラスｃに対応するクラス別キューからＶＣＩを取り出す操作を表す。Select ClassはＶＣＩを出力すべきクラスの番号を返す関数である。但し、クラス別キューが空であれば、クラス番号として負の値を返す。
【００６１】まず、状態レジスタ３６の値ｓをＭＰＵ３１で参照し（ステップＳ２０１）、ｓが１，２のいずれか、またはｓが１、２のいずれでもないかどうかを調べる（ステップＳ２０２）。ｓ＝１であれば、クラスレジスタ６１の値ｃと、ＶＣＩ入力レジスタ３７の値ｉを順次参照し（ステップＳ２０３，Ｓ２０４）、ＶＣＩ＝ｉのパケットキューのキュー長＋１をｑとし（ステップＳ２０５）、またＶＣＩ＝ｉのパケットキューの重みをｗとして（ステップＳ２０６）、ｑ，ｗの大小関係を調べる（ステップＳ２０７）。ここで、ｑ≦ｗの場合にはステップＳ２０８においてＥｎｑｕｅｕｅ （ｃ，ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込み、その後にステップＳ２０９に移り、またｑ＞ｗの場合には直接ステップＳ２０９に移る。ステップＳ２０９では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとする。
【００６２】一方、ステップＳ２０２においてｓ＝２であれば、ステップＳ２１１においてｉ：＝Dequeue （ｃ）、つまりＶＣＩメモリ３３のクラス別キューからＶＣＩを取り出した後、ＶＣＩ＝ｉのパケットキューのキュー長−１，０をｑとし（Ｓ２１２）、またＶＣＩ＝ｉのパケットキューの重みをｗとして（Ｓ２１３）、ｑ，ｗの大小関係を調べる（Ｓ２１４）。ここで、ｑ≧ｗの場合にはステップＳ２１５においてＥｎｑｕｅｕｅ（ｃ，ｉ）、つまりＶＣＩ＝ｉをＶＣＩメモリ３３に書き込んだ後にステップＳ２１６に移り、またｑ＜ｗの場合には直接ステップＳ２１６に移る。ステップＳ２１６では、ＶＣＩ＝ｉのパケットキューのキュー長をｑとし、さらにＶＣＩ出力レジスタ３８の値をｉとする（Ｓ２１７）。
【００６３】そして、ステップＳ２０２においてｓが１、２のいずれでもない場合と、ステップＳ２０９，Ｓ２１７の処理の終了後、状態レジスタ３６の値を０とし（ステップＳ２１８）、ステップＳ２０１に戻り、以上の動作を繰り返す。
【００６４】Ｓｅｌｅｃｔ Ｃｌａｓｓが予め定められた順番で周期的にクラスを選択すれば、時分割多重（ＴＤＭ）的なクラスのスケジューリングとなる。また、クラスに対してもキュー長と重みのうちの小さい方の値に基づいたＷＦＱを行なう場合には、クラスをスケジューリングするためのクラススケジューリングキューとクラス別セル数カウンタとクラス別の重みとを用意し、Ｓｅｌｅｃｔ Ｃｌａｓｓはクラスｃのセル数カウンタの値が１以上であれば、クラススケジューリングキューからクラス番号を１個出力するとともに、クラスｃのセル数カウンタをデクリメントする。一方、クラスｃのセル数カウンタの値が０であれば、負の値を出力する。
【００６５】ここで、Ｅｎｑｕｅｕｅ（ｃ，ｉ）は、ＶＣＩ＝ｉをＶＣＩメモリ３３のクラスｃに対応するクラス別キューに書き込む操作に加え、クラスｃのセル数カウンタをインクリメントし、状態レジスタ３１の値がｓ＝１、かつクラスｃのセル数が重み以下であるか、またはｓ＝２、かつクラスｃのセル数が重み以上である場合にクラス番号ｃをクラススケジューリングキューに書き込む操作を行なうようにする。
【００６６】また、クラスのスケジューリングには、ＳＣＦＱやＶｉｒｔｕａｌ Ｃｌｏｃｋなどの従来方式を用いることも可能である。また、１個以上蓄積されているクラスの中で最も優先度の高いクラスをサービスするような完全優先のクラススケジューリングを行なう場合には、クラス別の重みは必要ない。
【００６７】このゆうなアルゴリズムにより、常にＶＣＩメモリ３３内のＶＣＩ＝ｉの個数について式（４）が成立し、かつクラス毎に独立したスケジューリングが可能となる。
【００６８】なお、図７のスケジューリングアルゴリズムは、コード化されて図６のＲＯＭ３２内に格納されているものとする。このように本実施形態によれば、パケットが属するクラス別にスケジューリング情報管理部１６でスケジューリング情報であるＶＣＩを管理することにより、クラス間でのパケットスケジューリングと同一クラス内のコネクション間のパケットスケジューリングの両方において、第１〜第３の実施形態と同様の効果を得ることができる。
【００６９】（第５の実施形態）次に、本発明の第５の実施形態に係るパケットスケジューリング装置の構成と動作を図８を用いて説明する。
【００７０】図８において、図２および図５と同一部分に同一符号を付して説明すると、本実施形態ではスケジューリング情報管理部１６内にランダムアウトキュー８１，８２およびキュー選択部８３，８４が設けられている。
【００７１】キュー選択部８３は、スケジューリング情報をランダムアウトキュー８１，８２のいずれに格納するかを選択する。また、キュー選択部８４はランダムアウトキュー８１，８２のいずれからスケジューリング情報を取り出すかを選択する。ここで、キュー選択部８３がランダムアウトキュー８１を選択している場合は、キュー選択部８４はランダムアウトキュー８２を選択し、反対にキュー選択部８３がランダムアウトキュー８２を選択している場合は、キュー選択部８４はランダムアウトキュー８１を選択する。このようにキュー選択部８３，８４は、常に互いに異なるランダムアウトキューを選択するように制御される。なお、ここではランダムアウトキューが２個であるが、さらに多数のランダムキューを設けてもよい。
【００７２】ランダムアウトキュー８１，８２はキュー選択部８４によって選択されている場合に、格納しているスケジューリング情報をランダムに出力する。ここで、キュー選択部８４によって選択されているランダムアウトキューからスケジューリング情報が全て取り出された場合、キュー選択部８３，８４はそれぞれ、現在選択されていないランダムアウトキューを選択する。
【００７３】スケジューリング情報管理部１６の基本動作は、図４に示したフローチャートで表されるが、Ｅｎｑｕｅｕｅ（ｉ）、Ｄｅｑｕｅｕｅの意味が先の第２の実施形態の場合と異なる。
【００７４】図８において、パケットキュー１２，１３，１４はＶＣＩ＝１，２，ＭのＶＣコネクションにそれぞれ対応しており、それらのコネクションの持つ重みをそれぞれｗ１＝２，ｗ２＝１，ｗＭ＝１とする。また、図８（ａ）の状態でパケットキュー１２，１３，１４にパケットが格納されており、それらのスケジューリング情報がスケジューリング情報管理部１６内のランダムアウトキュー８１に格納されているものとする。すなわち、キュー選択部８３はランダムアウトキュー８１を選択し、キュー選択部８４はランダムアウトキュー８２を選択している。
【００７５】パケット出力時点で現在キュー選択部８４が選択しているランダムアウトキュー８２は空であるため、キュー選択部８３はランダムアウトキュー８２へ選択を切り替え、キュー選択部８４はランダムアウトキュー８１へ選択を切り替える。ここで、ランダムアウトキュー８１からランダムにＶＣＩを選択した結果、ＶＣＩ＝２が出力されたものとすると、ｑ２＝０＜ｗ２＝１となって、ＶＣＩ＝２はスケジューリング情報管理部１６に再入力されないため、パケットスケジューリング装置１１は図８（ａ）の状態から図８（ｂ）の状態に遷移する。
【００７６】図８（ｂ）の状態において、ＶＣＩ＝１のパケットキューへ１個パケットが到着した場合、ｑ１とｗ１の関係から、ＶＣＩ＝１が１個新たにランダムアウトキュー８２へ入力され、パケットスケジューリング装置１１は図８（ｂ）の状態から図８（ｃ）の状態に遷移する。
【００７７】さらに、図８（ｃ）の状態委からＶＣＩ＝２に対応するパケットキュー１３にパケットが１個到着した後、ランダムアウトキュー８１から２個の識別子１，Ｍがランダムに選択された場合には、パケットスケジューリング装置１１は図８（ｃ）の状態から図８（ｄ）の状態に遷移する。この際、ランダムアウトキュー８１が空になるため、キュー選択部８３，８４が選択するランダムアウトキューの切替えが起こる。
【００７８】このような制御により、例えばｗ１＝１００，ｗ２＝１００のように大きい値を持つ重みに対しては、スケジューリング情報管理部１６が第３の実施形態で述べたようなＦＩＦＯ構成の場合には、短い時間スケールではｗｅｉｇｈｔｅｄｆａｉｒとはなりにくいという欠点が解消され、どのような重みに対しても常に確率的にｗｅｉｇｈｔｅｄ ｆａｉｒなスケジューリングが可能となる。また、あるランダムアウトキューからスケジューリング情報を出力中は、別のランダムアウトキューへスケジューリング情報が入力されるため、空でない全てのパケットキューの先頭のパケットを一定時間内に出力することが保証される。
【００７９】ランダムアウトキュー８１，８２は図９のようなアルゴリズムで実現可能である。図９において、ｒは配列、ｐは配列の終りを示すポインタである。まず、初期化処理として、ポインタｐに−１をセットする。Ｅｎｑｕｅｕｅ（ｉ）操作は、ポインタｐを１だけインクリメントした後でｒ［ｐ］：＝ｉとすることにより実現される。次に、Ｄｅｑｕｅｕｅ操作について述べる。まず、ポインタｐが−１であればキューが空であるため返り値−１を変数ｉに記憶する。そうでなければ、０以上ｐ以下の疑似ランダム整数（Ｒａｎｄｏｍ（Ｏ，Ｐ））をｋとし、ｉ：＝ｒ［ｋ］によりＤｅｑｕｅｕｅの返り値を変数ｉに記憶した後、ｒ［ｋ］：＝ｒ［ｐ］とすることによりキューの最後尾の値を位置ｋに移し、ポインタｐを１だけデクリメントする。最後に、変数ｉの値を返す。このようなアルゴリズムにより、簡単な構成によりランダムアウトキューの管理ができる。
【００８０】（第６の実施形態）図１０に、本発明によるパケットスケジューリング装置を出力バッファ型ＡＴＭスイッチに適用した実施形態を示す。なお、本発明によるパケットスケジューリング装置は入力バッファ型や共通バッファ型のスイッチアーキテクチャにも適用可能である。
【００８１】図１０において、セル入力線１０１−１〜１０１−Ｎに到着した固定長パケットであるＡＴＭセルは、ＡＴＭセルのヘッダ情報を基にスイッチ１０２で交換出力され、パケット入力線１９−１〜１９−Ｎを介して上述したパケットスケジューリング装置１１−１〜１１−Ｎに入力される。パケットスケジューリング装置１１−１〜１１−Ｎは、パケット蓄積部としてＶＣコネクション単位のキューを持っており、入力されたセルはそのセルのヘッダに書かれているＶＣＩに対応するキューに格納される。パケットスケジューリング装置１１−１〜１１−Ｎは、各セルサイクルにおいて、キューにバッファリングされたセルのうち、１つを選択出力する。
【００８２】（第７の実施形態）図１１に、本発明において重みが動的に変化する場合のスケジューラのフローチャートを示す。なお、ハード構成は図３のようになる。
【００８３】重みが動的に変化する場合には、スケジューリング情報管理手段内のＶＣＩ＝ｉの個数は一時的に式（４）を満たさない場合がある。したがって、スケジューリング情報管理手段内のＶＣＩ＝ｉの個数ｎｉをカウントしておく必要がある。ｎｉの変更は、スケジューリング情報管理手段へのスケジューリング情報入力および出力時い行なう。
【００８４】また、セル出力時にＶＣＩ＝ｉをスケジューリングキューに入れるかどうかを判定する場合には、重みとキュー長を比較せずに、重いとスケジューリングキュー内のＶＣＩ＝ｉの個数および、キュー長とスケジューリングキュー内のＶＣＩ＝ｉの個数の比較を行ない、ｗｉ≧ｎｊかつｑｉ≧ｎｊのときに、ＶＣＩ＝ｉがスケジューリングキューに入れられる。これにより、重みが増加した結果、ｗｉ＞ｑｉとなった場合でもＶＣＩ＝ｉはスケジューリングキューに入れられるようになる。
【００８５】また、ｗｉ，＜ｑｉであるときにｗｉが増加した場合には、重みの増加分だけスケジューリング情報管理手段内のＶＣＩ＝ｉの個数も増加させる必要がある。この処理が図１１の重み対応処理である。図１１においては、重み変更対応処理はセル出力時に行なう例を示しているが、重み変更対応処理をセル入力時に行なうことも、セル入力時および出力時の両方で行なうことも、また、毎セル時間行なうことも可能である。
【００８６】重み変更対応処理においては、必要な回数だけEnqueue （ｉ）を実行するとともにｎｉをインクリメントする。ただし、重みの変更幅が大きいほどループの回数も増えるため、１回の処理に対するループの最大回数Ｃmax を決めておき、Ｃmax を越える分のループは次以降のセル時間に実行するようにする。
【００８７】（第８の実施形態）図１２に、本発明において重みが実数値をとり得る場合のスケジューラのフローチャートを示す。なお、ハード構成は図３のようになる。図１２においては、重みｗｉは１以上の実数値をとるものとする。重みとキュー長の比較の際には、ｗinowが使用される。ｗinowの値は、ｆｌｏｏｒ（ｗinow）の値がｆｌｏｏｒ（ｗi ）またはｆｌｏｏｒ（ｗi ）＋１のいずれかの値をとるように、かつｗinowの平均値がｗi と等しくなるように制御する。ここで、ｆｌｏｏｒ（ｘ）は、ｘ以下の最大の整数値を返す関数である。ｗinowの値は動的に変更されるため、第７の実施形態と同様に、スケジューリング情報管理部内のＶＣＩ＝ｉの個数ｎiをカウントしておく必要がある。
【００８８】ＶＣ設定時に、ｗinowの値はｗi に初期化され、また、変数ｆi がｗi の小数部分の値に設定される。図１２の例では、ｗinowの値の更新はセル出力時に行なわれる。すなわち、ｗinowの値はｆi ずつインクリメントされ、その結果、ｆｌｏｏｒ（ｗi ）＋１以上となった場合には１だけデクリメントされる。この処理が図１２の小数点処理である。また、ｗinowの動的な変更に伴い、第７の実施形態と同様に重み変更対応処理が必要となる。図１２では、重み変更対応処理の中でｗi の代わりにｗinowが用いられる。なお、ｗinowの値は小数点処理によって変更されるだけでなく、第７の実施形態のようにｗi の動的な変更に伴って変更される場合もあるが、本実施例はそのような変更も許容するような構成となっている。
【００８９】なお、小数点処理、および重み変更対応処理はセル出力時だけでなく、セル入力時に行なうことも、セル入力時および出力時の両方で行なうことも、また、毎セル時間行なうことも可能である。このように重みが実数値をとれるようにすることにより、重みの値が大きくならないようにできるためスケジューラの性能劣化を抑えることができる。
【００９０】（第９の実施形態）図１３に、本発明においてスケジューリング情報管理手段が、パケットが所属するクラス別に設定される重みに基づいてクラスのスケジューリングを行ない、かつ、クラス別の重みをそのクラス内のコネクションのキューの状態に応じて変更する場合の実施形態を示す。
【００９１】クラス別スケジューラは速度クラス、ＱＯＳクラス、仮想パス、またはそれらの組合せ毎に用意される。クラス別スケジューラは重みとキュー長とを用いたスケジューリングを行なう。クラススケジューラは従来方式のスケジューラでもよい。
【００９２】クラススケジューラは各クラスｉ毎に重みφi を管理する。クラス重みφi は、
となるように制御する。ただし、Ｂi はクラスｉのＶＣの中でＶＣキューが空でないＶＣＩの集合である。また、Ｗi はクラスｉに接続中のＶＣに関するｗjの和である。したがって、パケットキューが空のＶＣ数が多いほどφi は小さくなる。これにより、スケジューラを階層化した場合でもクラススケジューラはクラス内のＶＣの状態を考慮したスケジューリングが可能になる。
【００９３】ただし、φi の値が変わった場合には、それに合わせてクラススケジューラ内の状態も更新する必要がある。例えば、クラススケジューラがＳＣＦＱのようにバーチャルタイムを用いたスケジューラである場合、スケジューリング情報の再ソーティングが行なわれる。この場合のフローチャートを図１４に示す。ハード構成は図６のようになる。
【００９４】図１４では重みが実数値をとることができ、また、動的な重みの変更も可能である。まず、初期化処理ですべてのクラスｉ重みの和Ｗi およびキュー長が０にリセットされる。
【００９５】次に、クラスｉのＶＣＩ＝ｊのＶＣの接続要求があった場合には、ｑi 、ｎiを０にリセットし、重みの小数部分をｆj に設定し、重みの初期値ｗjnowをｗjに設定する。また、クラスｉの重みをｗj だけインクリメントする。また、クラスｉのＶＣＩ＝ｊのＶＣの切断要求があった場合には、クラスｉの重みをｗj だけデクリメントする。
【００９６】セル入力時には、クラスｉのＶＣＩ＝ｊのＶＣのキュー長ｑj が０である場合には、クラスｉの重み現在のφ1 の値を変数φ´1 に記憶するとともに、φ1 をｗj ／Ｗi だけインクリメントする。次に、φ1 の変更に伴いクラスｉに対する評価値Ｆi の値の更新を行なう。更新される値は現在のＦi の値に対して１／φ´i −１φi だけ小さくなるが、現在ソートされている評価値の中での最小値Ｆよりも小さい値に更新されてしまうような場合には、Ｆi の値をＦから１φi だけ大きい値に設定する。また、クラスｉのキュー長Ｑi が０である場合も同様にＦi の値をＦから１φ／1 だけ大きい値に設定する。その後、ｑj 、Ｑi の値をインクリメントし、ｑi ≦ｗjnowの場合にはスケジューリングキューにＶＣＩ＝ｊを入れ、ｎi の値をインクリメントする。
【００９７】セル出力時には、ソートされている中で最も小さい評価値をもつクラス（ｉ）からＶＣＩ（＝ｊ）を取り出すとともに、ｑj 、Ｑi をデクリメントする。次に図１２と同様の小数点処理を行なう。ｑj ＝０であればクラスｉの重みφi をｗj ／Ｗi だけデクリメントする。次に、Ｑi ＞０であればクラスｉの評価値Ｆiを１／φi だけインクリメントする。次に、ｗjnow≧ｎj であれば、ＶＣＩ＝ｊをクラスｉのスケジューリングキューに再入力（Ｅｎｑｕｅｕｅ（ｉ，ｊ））し、そうでなければｎj を１だけデクリメントする。最後に、ｗjnowの更新に伴って図１２と同様の重み変更対応処理を行ない、ＶＣＩ＝ｊのＶＣキューの先頭からセルを出力するためにＶＣＩレジスタにｊを設定する。
【００９８】このような構成により、重みが大きいコネクションと重みが小さいコネクションを別のクラスに分けて管理することができるため、重みが大きいコネクションの重みの絶対値が小さくなり、階層化しない場合に比べてスケジューラの性能劣化を抑えることができる。
【００９９】
【発明の効果】以上説明したように、本発明のスケジューリング装置によれば、重みのみでなくパケット蓄積料も用いたきめ細かなパケットスケジューリングが可能となる。従って、例えば重みの大きいコネクション群と重みの小さいコネクション群があって、それぞれのコネクション群の重みの和が等しい場合にも、重みの大きいコネクション群が小さい時間スケールで優位に扱われるという不都合を抑制することができ、コネクションの重みによらず公平なパケットスケジューリングが可能となる。
【０１００】また、特に固定長パケットを扱う場合には、スケジューリング情報管理部において各パケットキュー（パケット蓄積部）に対応した重みとキュー長（パケット蓄積量）のうちの小さい方の値に等しい個数のスケジューリング情報を常に保持することにより、スケジューリング情報管理部がパケットのスケジューリングに必要な処理時間をコネクション数に関係なく一定値にすることができ、入力トラヒックにほとんど依存せずに確率的に公平なＷＦＱも実現可能となる。
【０１０１】さらに、スケジューリング情報管理部においてクラス別にキューを設ければ、各クラス内あるいはクラス間のパケットスケジューリングに対して上記と同様の効果が期待できる。
【図面の簡単な説明】
【図１】 本発明の一実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図２】 本発明の他の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図３】 本発明におけるスケジューリング情報管理部の実現例をしめすブロック図。
【図４】 図３のスケジューリング情報管理部の動作を示すフローチャート。
【図５】 本発明の別の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図６】 本発明におけるスケジューリング情報管理部の他の実現例を示すブロック図。
【図７】 図６のスケジューリング情報管理部の動作を示すフローチャート。
【図８】 本発明のさらに別の実施形態に係るパケットスケジューリング装置の構成を示すブロック図。
【図９】 ランダムアウトキューの実現例。
【図１０】 重みが動的に変化する場合のスケジューリングアルゴリズム。
【図１１】 重みが動的に変化する場合のスケジューリングアルゴリズム。
【図１２】 重みが実数値をとり得る場合のスケジューリングアルゴリズム。
【図１３】 スケジューラの階層化構成。
【図１４】 クラススケジューラがクラス内のコネクションのキューの状態によってクラスの重みを変更する場合のスケジューリングアルゴリズム。
【符号の説明】
１１，１１−１〜１１−Ｎ…パケットスケジューリング装置
１２，１３，１４…パケットキュー（パケット蓄積部）
１５…パケット入力部
１６…スケジューリング情報管理部
１７…パケット出力部
１８…パケット
１９，１９−１〜１９−ｎ…パケット入力線
２０，２０−１〜２０−Ｎ…パケット出力線
２１…ＶＣＩ（スケジューリング情報）
３１…プロセッサ
３２…ＲＯＭ
３３…ＶＣＩメモリ
３４…キュー長メモリ
３５…重みメモリ
３６…状態レジスタ
３７…ＶＣＩ出力レジスタ
３８…ＶＣＩ出力レジスタ
３９…データバス
４０…制御バス
６１…クラスレジスタ
８１，８２…ランダムアウトキュー
８３，８４…キュー選択部
９１…レジスタ
９２…シフト信号生成回路
９３…セレクト信号生成回路
９４…セレクタ信号線
９５…シフト信号線
９６…アドレス入力線
９７…データ入力線
９８…読み出し可能信号線
９９…書き込み可能信号線
９１０…データ出力線
９１１…シフト信号生成可能信号線
９１２…データシフト線
１０１−１〜１０１−Ｎ…セル入力線
１０２…ＡＴＭスイッチ
【特許請求の範囲】
【請求項１】入力されるパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積手段と、パケット受信時に前記複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力手段と、前記複数のパケット蓄積手段にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積手段のパケット蓄積量と該パケット蓄積手段に設定された前記重みとに基づいて管理するスケジューリング情報管理手段と、パケット送信時に前記スケジューリング情報管理手段が管理するスケジューリング情報を基に所望の前記パケット蓄積手段から所望のパケットを読み出して出力するパケット出力手段とを有し、前記スケジューリング情報管理手段は、前記パケットが所属するクラス別または仮想パス別に設定される動的に変更可能な重みに基づいてクラスまたは仮想パスのスケジューリングを行ない、前記クラス別または仮想パス別の重みを前記クラスまたは仮想パス内に収容されるコネクションのパケット蓄積手段内のパケット蓄積数が、０から正の値に変化したときあるいは正の値から０に変化したときに変更することを特徴とすることを特徴とするパケットスケジューリング装置。
【請求項２】入力される固定長のパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積手段と、パケット受信時に前記複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力手段と、前記複数のパケット蓄積手段にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積手段のパケット蓄積数と該パケット蓄積手段に設定された前記重みとに基づいて管理するスケジューリング情報管理手段と、パケット送信時に前記スケジューリング情報管理手段が管理するスケジューリング情報を基に所望の前記パケット蓄積手段から所望のパケットを読み出して出力するパケット出力手段とを有し、前記スケジューリング情報管理手段は、前記複数のパケット蓄積手段にそれぞれ対応したスケジューリング情報の個数を該パケット蓄積手段のパケット蓄積数と該パケット蓄積手段に設定された前記重みのうちの小さい方の値に等しい個数だけ常に保持することを特徴とするパケットスケジューリング装置。
【請求項３】前記スケジューリング情報管理手段は、前記パケットが属するクラス別又は仮想パス別に前記スケジューリング情報を管理することを特徴とする請求項２に記載のパケットスケジューリング装置。
【請求項４】前記スケジューリング情報管理手段は、前記パケットが所属するクラス別または仮想パス別に設定される動的に変更可能な重みに基づいてクラスまたは仮想パスのスケジューリングを行ない、前記クラス別または仮想パス別の重みを前記クラスまたは仮想パス内に収容されるコネクションのパケット蓄積手段内のパケット蓄積数が、０から正の値に変化したときあるいは正の値から０に変化したときに変更することを特徴とする請求項３に記載のパケットスケジューリング装置。
【請求項５】前記スケジューリング情報管理手段は、少なくとも一つのＦＩＦＯキューで構成されることを特徴とする請求項１乃至３のいずれか１項に記載のパケットスケジューリング装置。
【請求項６】前記スケジューリング情報管理手段は、少なくとも一つのランダムアウトキューで構成されることを特徴とする請求項１乃至３のいずれか１項に記載のパケットスケジューリング装置。
【請求項１】入力されるパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積手段と、パケット受信時に前記複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力手段と、前記複数のパケット蓄積手段にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積手段のパケット蓄積量と該パケット蓄積手段に設定された前記重みとに基づいて管理するスケジューリング情報管理手段と、パケット送信時に前記スケジューリング情報管理手段が管理するスケジューリング情報を基に所望の前記パケット蓄積手段から所望のパケットを読み出して出力するパケット出力手段とを有し、前記スケジューリング情報管理手段は、前記パケットが所属するクラス別または仮想パス別に設定される動的に変更可能な重みに基づいてクラスまたは仮想パスのスケジューリングを行ない、前記クラス別または仮想パス別の重みを前記クラスまたは仮想パス内に収容されるコネクションのパケット蓄積手段内のパケット蓄積数が、０から正の値に変化したときあるいは正の値から０に変化したときに変更することを特徴とすることを特徴とするパケットスケジューリング装置。
【請求項２】入力される固定長のパケットを一時的に蓄積するための動的に変更可能な重みがそれぞれ設定された複数のパケット蓄積手段と、パケット受信時に前記複数のパケット蓄積手段の少なくとも一つにパケットを入力するパケット入力手段と、前記複数のパケット蓄積手段にそれぞれ蓄積されたパケットを読み出す順序を指定するためのスケジューリング情報を該パケット蓄積手段のパケット蓄積数と該パケット蓄積手段に設定された前記重みとに基づいて管理するスケジューリング情報管理手段と、パケット送信時に前記スケジューリング情報管理手段が管理するスケジューリング情報を基に所望の前記パケット蓄積手段から所望のパケットを読み出して出力するパケット出力手段とを有し、前記スケジューリング情報管理手段は、前記複数のパケット蓄積手段にそれぞれ対応したスケジューリング情報の個数を該パケット蓄積手段のパケット蓄積数と該パケット蓄積手段に設定された前記重みのうちの小さい方の値に等しい個数だけ常に保持することを特徴とするパケットスケジューリング装置。
【請求項３】前記スケジューリング情報管理手段は、前記パケットが属するクラス別又は仮想パス別に前記スケジューリング情報を管理することを特徴とする請求項２に記載のパケットスケジューリング装置。
【請求項４】前記スケジューリング情報管理手段は、前記パケットが所属するクラス別または仮想パス別に設定される動的に変更可能な重みに基づいてクラスまたは仮想パスのスケジューリングを行ない、前記クラス別または仮想パス別の重みを前記クラスまたは仮想パス内に収容されるコネクションのパケット蓄積手段内のパケット蓄積数が、０から正の値に変化したときあるいは正の値から０に変化したときに変更することを特徴とする請求項３に記載のパケットスケジューリング装置。
【請求項５】前記スケジューリング情報管理手段は、少なくとも一つのＦＩＦＯキューで構成されることを特徴とする請求項１乃至３のいずれか１項に記載のパケットスケジューリング装置。
【請求項６】前記スケジューリング情報管理手段は、少なくとも一つのランダムアウトキューで構成されることを特徴とする請求項１乃至３のいずれか１項に記載のパケットスケジューリング装置。
【図１】
【図９】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１０】
【図７】
【図８】
【図１４】
【図１１】
【図１２】
【図９】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１０】
【図７】
【図８】
【図１４】
【図１１】
【図１２】
【特許番号】特許第３４３４６４２号（Ｐ３４３４６４２）
【登録日】平成１５年５月３０日（２００３．５．３０）
【発行日】平成１５年８月１１日（２００３．８．１１）
【国際特許分類】
【出願番号】特願平８−５２８１３
【出願日】平成８年３月１１日（１９９６．３．１１）
【公開番号】特開平９−８３５４７
【公開日】平成９年３月２８日（１９９７．３．２８）
【審査請求日】平成１２年１２月１３日（２０００．１２．１３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【参考文献】
【文献】特開 平２−８７７４７（ＪＰ，Ａ）
【文献】特開 平４−２０７５４３（ＪＰ，Ａ）
【文献】特開 平７−２４０７５２（ＪＰ，Ａ）
【文献】特開 平８−１３０５４３（ＪＰ，Ａ）
【文献】特開 平５−２２７１９４（ＪＰ，Ａ）
【文献】特開 平４−３３６８３２（ＪＰ，Ａ）
【文献】特開 平６−３３８９０５（ＪＰ，Ａ）
【登録日】平成１５年５月３０日（２００３．５．３０）
【発行日】平成１５年８月１１日（２００３．８．１１）
【国際特許分類】
【出願日】平成８年３月１１日（１９９６．３．１１）
【公開番号】特開平９−８３５４７
【公開日】平成９年３月２８日（１９９７．３．２８）
【審査請求日】平成１２年１２月１３日（２０００．１２．１３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【参考文献】
【文献】特開 平２−８７７４７（ＪＰ，Ａ）
【文献】特開 平４−２０７５４３（ＪＰ，Ａ）
【文献】特開 平７−２４０７５２（ＪＰ，Ａ）
【文献】特開 平８−１３０５４３（ＪＰ，Ａ）
【文献】特開 平５−２２７１９４（ＪＰ，Ａ）
【文献】特開 平４−３３６８３２（ＪＰ，Ａ）
【文献】特開 平６−３３８９０５（ＪＰ，Ａ）
[ Back to top ]