(57)【特許請求の範囲】
【請求項１】
サーバによって実体を操作する際の制御を行なうスケジューラにおいて、
Ｎ個の実体であって、Ｎは１又は１よりも大きい整数であり、各実体は、サーバからサービスを受信するレートを有するＮ個の実体と、
Ｎ個の実体の終了時間ｆiを有するメモリーであって、ｆiは、ｉ番目の実体が、サーバによって操作される時間に対応するメモリーと、
仮想時間の経過を保持して、終了時間ｆiを確認する仮想クロックと、
仮想クロックとメモリーに接続されており、終了時間の関数としてサーバによって操作される実体を選択するコントローラと、
を具えており、
コントローラは、次式、
Ｖ(ｔ＋１)＝ｍｉｎ(Ｖ(ｔ)＋１，ｍｉｎＦ)
に応じて仮想時間を操作し、但し、ｍｉｎＦは、終了時間を有するすべての実体中の最も早い終了時間を示しているスケジューラ。
【請求項２】
各実体は、サーバからサービスを要求するレートを有しており、実体のレートの合計は、１よりも大きくできる、請求項１に記載のスケジューラ。
【請求項３】
コントローラは、仮想時間に等しい終了時間を有するすべての実体が、サーバからサービスを受信するまで、仮想時間を停止させる、請求項２に記載のスケジューラ。
【請求項４】
コントローラは、各実体のレートの関数として各実体にサービスを提供するものであり、レートの総計は、１よりも大きいものである、請求項３に記載のスケジューラ。
【請求項５】
メモリーは、Ｎ個の実体の開始時間ｓiを有しており、ｉは１≦ｉ＜Ｎである整数であり、ｓiは、ｉ番目の実体がサーバから次のサービスを要求できる最も早い時間に対応しており、メモリーは、Ｎ個の実体のレート制限時間ＴＩiを有する、請求項４に記載のスケジューラ。
【請求項６】
コントローラは、最も早い終了時間を有する実体にサービスを提供する、 請求項５に記載のスケジューラ。
【請求項７】
コントローラの階層を有しており、Ｎ個の実体のうちの少なくとも第１の実体は、第２層のコントローラ中の複数の実体を表しており、第２層の第２の実体は、第３層のコントローラ中の実体を表しており、
サービスを必要とするコネクションは、スケジューラ中にてコネクションが最初に接続するコントローラに関連づけられたメモリー中に、レート制限時間と開始時間を格納し、
下位層のコントローラに接続されたコントローラは、レート制限時間と開始時間を、下位層のコントローラに関連づけられたメモリー中に格納している、請求項６に記載のスケジューラ。
【請求項８】
第１層のコントローラは、第１の実体がスケジュールされるのに適正であり、サービスを待っている実体の最も早い終了時間を有しているとき、サービスを提供するために第１の実体を選択し、そのローカルメモリー中の実体の開始時間と終了時間を更新し、
第２のコントローラは、さらに、第２の実体がスケジュールされるのに適正であり、第２のコントローラでサービスを待っている実体の最も早い終了時間を有しているとき、サービスを提供するために第２の実体を選択し、そのローカルメモリ中で実体の開始時間と終了時間を更新する、請求項７に記載のスケジューラ。
【請求項９】
各コントローラは、異なる層又は同じ層の他のコントローラのすべての他のクロックから独立した仮想クロックを維持しており、すべての仮想クロックは、コントローラに接続されると共にスケジュールされるのに適正な実体の終了時間に基づいて更新される、請求項８に記載のスケジューラ。
【請求項１０】
すべての仮想クロックは、各サイクルタイムで増分され、クロックの正しい値を獲得するために、終了時間を有するすべての実体中の最も早い終了時間に関する上記の操作を仮想クロック上で行なって、コントローラがサービスを受信したときに、コントローラが次の層のクロックの正しい値を用いることを許容する、請求項９に記載のスケジューラ。
【請求項１１】
コントローラにおける実体のレートの合計は、１よりも大きくすることができ、従って、スケジューラにオーバーブッキングを許容する、請求項８に記載のスケジューラ。
【請求項１２】
オーバーブッキングのない場合に実体により受信されたレートは、その実体のレートに等しく、オーバーブッキングのある場合に実体により受信されたレートは、レートの最小値又はスケジュールされるのに適正な実体のレートの合計によってコントローラにて減じられたレートである、請求項１１に記載のスケジューラ。
【請求項１３】
少なくとも１の実体は、サービスを待っている実体の最も早い終了時間である終了時間を有しているとき、サーバからサービスを保証される、請求項１２に記載のスケジューラ。
【請求項１４】
コントローラがどの実体が次にサービスを受信するかを決定する場合、サービスを保証された実体がコントローラによって最初に調査されて、コントローラは、サービスを保証された実体が、サービスを待っている実体の最も早い終了時間を有しているかどうかを確認する、請求項１３に記載のスケジューラ。
【請求項１５】
サーバによって実体を操作する際の制御を行なうスケジューラにおいて、
Ｎ個の実体であって、Ｎは１又は１よりも大きい整数であり、各実体は、サーバからサービスを受信するレートを有しており、Ｎ個の実体の第１の実体は複数のコネクションを有しており、複数のコネクションのうち少なくとも１つが、サービスを待っており、サービスを待っている実体の中で最も早い終了時間である終了時間を有している場合、コントローラは、サービスを提供する第１の実体を選択するものであるＮ個の実体と、
Ｎ個の実体の終了時間ｆiを有するメモリーであって、ｆiは、ｉ番目の実体がサーバによって操作される時間に対応したメモリーと、
仮想時間の経過を保持して、終了時間ｆiを確認する仮想クロックと、
仮想クロックとメモリーに接続されており、終了時間の関数としてサーバによって操作される実体を選択するコントローラと、
を具えており、
コントローラは、次式、
Ｖ(ｔ＋１)＝ｍｉｎ(Ｖ(ｔ)＋１，ｍｉｎＦ)
に応じて仮想時間を操作し、但し、ｍｉｎＦは、終了時間を有するすべての実体中の最も早い終了時間を示しているスケジューラ。
【請求項１６】
サーバからのサービスをスケジュールするための方法において、
サービスについての第１のレートを有する第１の実体から第１の要求を、サーバから受信するステップと、
第１の実体がサーバからサービスを受信するときに、メモリーに終了時間を格納するステップと、
サービスについての第２のレートを有する第２の実体から第２の要求を、サーバから受信するステップと、
第１の実体にサービスを提供するステップと、
第２の実体の終了時間が、仮想時間と等しければ、仮想時間を停止するステップと、
第２の実体へ、サービスを提供するステップとを含んでいる方法。
【請求項１７】
実体のレートの合計は、１よりも大きい、請求項１６に記載の方法。
【請求項１８】
第１の実体にサービスを提供するステップは、第１の実体の第１のコネクションへサービスを提供し、次に、第１の実体の第２のコネクションへサービスを提供するステップである、請求項１７に記載の方法。
【請求項１９】
第１の実体にサービスを提供するステップの前に、第１の実体が、終了時間を有する実体の最も早い終了時間である終了時間を有しているかどうか決定するステップを含んでいる、請求項１８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はサーバが実体に対してサービスを提供する際のスケジューリングを行うためのスケジューラに関するものである。より具体的には、この発明はオーバーブッキングされた状態でのＡＴＭスケジューラの階層的な転送レート制限の実行方法に関するものである。
【０００２】
【従来の技術】
発明の背景
これまでにはパケットの公平な順序付けに基づく様々なスケジューリング法が提案されてきた。これらの方法は、典型的にはそれぞれのセッションに対して時計と時刻情報とを管理することを必要とした。セッションはそれらの時刻情報に基づいてソートされ、その順序に従い送出される。  この方法における提案された変形は、時計とセッションの時刻情報とを更新する方法において本質的な違いがある。同様にそれらは、サービスにおいて生成されるジッターにおいても異なる。J.C.R. Bennettと H.Zhang. Wf2q: Worst-case fair weighted weighted fair queuing. In INFOCOM'96, pages 120-128, Mar. 1996. を参照。
【０００３】
セッション間における調整に関連する2つの主なコストがある。仮想時間関数の計算、それはそれぞれのセッションが受け付けるべきサービスの標準化された公正な量を動的に測定するコスト、そして、log N のオーダーの複雑さとなる、異なるセッションからの転送要求の優先順序を管理するコストである。但しNはセッションの数。
【０００４】
J.C.R. Bennettと、D.C. Stephensと、H. Zhang. High Speed, Scalable, Accurate Implementation of Fair Queuing Algorithms in ATM Networks. ICNP'97 Mar. 1997,には、上記のコストを緩和する構造の一例が開示されている。J.C.R. BennettとD.C.StephensとH.Zhang. High Speed, Scalable and AccurateImplementation of Fair Queuing Algorithms in ATM Networksを参照。ICNP'97,Mar.1997, において、サーバは固定した数の転送レートをサポートするよう制約されている。そして同一のレートをもつセッションが互いにまとめられる。関連順序付けをすることなく、同一の転送レートを持つグループに属するセッションの間で優先度の関係が管理されていることが示されている。その問題は、すべてのセッションの間でスケジュールするといった問題から、グループのヘッドにて、すべてのセッションをスケジュールする問題へと簡単にされる。そのような実行においては、順序付けを管理し仮想時間を計算する複雑さは、セッションの数よりも、むしろ、サポートする離散したレートの数により増大する。
【０００５】
これまでの研究や特許において、パケットの公平な順序付けの実行（ＰＦＱ）が示されてきた。[J.C.R. Bennett と H. Zhang. Wf2q: Worst-case fair weighted weighted fair queuing. INFOCOM'96 pages 120-128, Mar. 1996; J.C.R. Bennettと H. Zhang. Hierarchical Packet Fair Queuing Algorithms.In ACM SIGCOMM'96 pages 143-156, Aug. 1996; J.L. Rexford と A.G. Greenberg と F.G. Bonomi. Hardware-efficient Fair Queuing Architectures for High Speed Networks. INFOCOM'96 Mar. 1996; J.C.R. Bennett と D.C. Stephensと and H. Zhang. High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks. ICNP'97 Mar.1997]これらはバンド幅を保証されたものにしようとしている。これまでの従来例として、そのようなパケットの公平な順序付けの実施例が示される。以下に示す手法は、いくつものセッションのそれぞれの転送レート要求の間でバンド幅を割り当てる。１つのセッションは、要求したレート以上のバンド幅を割り当てられることはない。
【０００６】
それぞれのセッションＣiは要求するサービスの転送レートｒi をもち、それは図１においてラインレートの一部分として示されている。基本的な考え方はそれぞれのセッションは、セルスロット時間の 1/ri 毎に1度割り当てられる。この間隔はセッション時間間隔(TIi)として引用される。最後のTIiのセル時間内に割り当てを受けていないセッションは、出来る限りはやい機会に割り当てを受けるべきである。各セッションについて開始時間(Si)はそれが適格としてスケジュールされるべき最も早い時間を示すために管理される。各セッションの終了時間 Fiもまた管理され、それは計算式 Fi=Si+TIiによって導出される。セッションはそれぞれの終了時間に基づき割り当てられる。そのアルゴリズムの詳細は以下に示されている:
・仮想時間は所定のポートに対し,ポートサイクルごとに以下のように更新される。
Ｖ（ｔ＋１）＝Ｖ（ｔ）＋１
【０００７】
これ以外にもより複雑な仮想時間関数が論文において提案されているが、その多くは上の式にあるものと同じような、単調に増加する関数を仮定する。
・セッションi は時間 tによってスケジュールされているものとする。もしセッションが残っているのなら、セルは送出され、残っていないのであればそのサイクルは何もしない。新たな開始時間と終了時間Si(t+)と Fi(t+) とは以下に従い更新される：
Si(t+)=Fi(t), and Fi(t+)=Si(t+)+L/ri
ただしLはセルの長さであり、riはセッションの転送速度である。新たなセッション iが時刻 tに追加された時、それに割り当てられる開始時間はSi(t)=V(t) and Fi(t)=Si(t)+L/rとなる。ポートスロット時刻 tにおいて、すべての活動している(セルが溜まっている）セッションのうちで、適格なものは次のように決定される。
Si(t)≦V(t)
すべての適格なセッションのうちで、もっとも小さい終了時間 Fi(t)をもつものが、次の送出の為に選択される。
【０００８】
上の手法において、セッションはセッション初期化の間にスケジュールに組み込まれることに注意したい。それはセッションが壊されるまでの間存続する。すべてのセッションの転送レートの合計が、回線速度（line rate）（LR)と同じかそれ以下であることが期待される。オーバーブッキングを実行するこの手法に関する問題のひとつは次のようなものである。活動していない（溜まっていない）セッションは、スケジュールされる可能性があるが、セルを持たないものは、サイクルを無駄にしてしまう。このことはハードウェアーが、アルゴリズムを繰り返し、空ではない接続を見つけ出すための時間がないという実際的な制約を仮定している。オーバーブッキングの状況において, 無駄になるサイクルは他の（セルが）溜まっているセッションに対して使われるべきであった。この問題は、たとえばスケジューラはセルを持っているセッションの間でのみスケジュールされるといった方法により、活動していないセッションをスケジューラから取り除くことにより解決できる。上記の手法には次のような修正が必要となる。
・（セルを）送出したあと、もしセッションに溜まっているものがなくなったのであれば、それはポートのバンド幅を調整するために活動しているセッションのリストからはずされる。
・活動していないセッション iは、時刻 tに活動を始め（セルが溜まり）、スケジューラ調整プロセスに書き戻される。それの新たな開始時間はつぎのように割り当てられる。
Si(t)=max(Si(t-),V(t)) and Fi(t)=Si(t)+L/r
【０００９】
上記の式におけるmaximum関数（最大値関数）は、セッションがSi(t-)よりも前には開始されないことを保証する。もし最後のサービスのあとセッションが空となり、そしてスケジュールされた次の開始時間よりも前に再び（セルが）溜まったら、その開始時間を仮想時間に対して再設定することにより、それは要求された転送レートよりも大きくなることが出来る。
【００１０】
しかしながら、修正された手法に従ったとしても, それをオーバーブッキングな状況で用いるには以下で議論するような更なる問題がある。PFQの実行可能性に関する一般的なコメントがここでは必要となる。セッションの間で、最短の終了時間を決定するために、すべての活動しているセッションの間で最小の計算を行う必要がある。もしセッションの数が大きくなった時、これはセルスロット時間の間に行うことはできない。これまでの手法では、この問題を解決するために時刻情報にもとづくセッションの順序付けされたヒープを管理することを提案してきた。同様に転送速度でまとめる手法は、[J.C.R. Bennett と H.Zhang. Wf2q: Worst-case fair weighted weighted fair queuing. INFOCOM'97，pages 120-128, Mar. 1996]で提案されている。この発明はすべてのセッションの間での最短の終了時間を決定するためにこれらの手法のいずれかを用いることもある。
【００１１】
これまで提案されてきたPFQ手法に関する実行では、目的とする転送レートにレート制限するようプログラムすることで、転送レート制限を実行することが可能である（上の箇条書きにおける最初の項目）。しかしながら、オーバーブッキングな状況においては,これらの実行において予想される振る舞いは、求められている振る舞いから大きく外れたものとなる。これまでに提案されてきたPFQ手法によるオーバーブッキングに対する能力により転送レート制限が可能なスケジューラを実行する際の問題について分析をする前に、理想的な実行による予想される振る舞いについて考慮するべきである。
・混雑していないポート（即ちポートに入力されるトラフィックの合計が回線転送レートに等しいか少ない状況）にとっては、溜まっているセッションはその転送速度の制限により受け取りを制限される。
・混雑している状況（溜まっているセッションに要求される転送レート制限の合計が回線転送レートよりも大きい状況）においては、この方法は、溜まったセッションの各々が、要求されたレートを、ラインレートがオーバーブッキングされてラインレートの時間が割算したものと等しいレートを確実に受けるようにする。
【００１２】
実施例
図2はこの動作を図示した例である。2つのセッションC0とC1とは同じポートをあて先としている。到着したセルはそれぞれの別個のキューに溜め込まれる。スケジューラはそれらを送出する。セッションC0とC1は、それぞれ転送レートが2/4と3/4とに制限されている。これはキューにC0だけがセルを持っていたとしたら、そのレートは2/4に制限されていることを意味する。同様にキューにC1だけがセルを持っているとしたら,それは3/4の転送レートに制限される。しかしながら、両方のセッションがセルを持っているとしたら、回線転送レートの5/4倍にオーバーブッキングしてしまう。セッションにより受け取られるサービスは、そのオーバーブッキング率により縮小される。この状況においては、C0とC1はそれぞれ回線転送レートの2/5と3/5を受け取る。
【００１３】
前の手法にもとづくオーバーブッキングレート制限による実行は考慮される。その手法はセッションの間でサービスの欠乏を発生させる。図は特定の実行にもとづくものであるが、オーバーブッキングされたシナリオのときに焦点が当てられる問題は、実行する際に単調に仮想時間関数が増加する様な、公平な順序付けアルゴリズムのすべての変形中に存在する。
【００１４】
図3は、それぞれが回線転送レートの1/2,1,1といった要求をする３つのセッションC0,C1,C2がオーバーブッキングしている状況を図示している。セッションC0とC1は時刻 t=0に活動的になり（セルを溜め）、セッションC2はそれより遅れてt=10000 において活動的になる。この表は、V(t+1) =  V(t) + 1に従い増加する仮想時間の実行に基づいたよる仮想時間の値をあらわしている。それは継続する列が、それぞれセッションC0,C1,C2の開始時間と終了時間を表してもいる。それぞれのスロット時間 tに対して、下線が引かれた開始時間と終了時間の対は、与えられたサイクルに送出されるセッションを表している。送出されるべきセッションは、適格なセッションの中から最短終了時間に基づいて選択される。適格セッションの中で最小終了時間について同じ適格性である場合は、最も早い開始時間のセッションが選ばれる。以下の観測が例から作成される:
・スケジューラーは、セッションC0とC1の要求レートによりオーバーブッキングしている。
・時刻が進むにつれ、これらのセッションの開始/終了時間は徐々にＶ（ｔ）からの遅れを溜めていく。例えばｔ＝10000の時、V(t)=10000はF0= 6670と F1 6669に対してかなり進んでしまっている。t=10000においてセッションC2が開始され、S2=V(t)=10000として開始時間が記載されている。
・最短終了時間によるセッション送出の基準によると、セッションC2とC1の終了時間がC2の終了時間に追いつくまでは、セッションＣ２は信号送出しない。セッションＣ２が信号送出を始めるのは、この時間が経過してからである。これは例においては t=15000で発生する。それゆえC2は5000スロット時間の間、送出がされないことになる。一般的に、セッションは活動的になってからも、他のセッションが仮想時間に対しての遅れがどの程度あるかに従い、任意の時間待たされることになる。
【００１５】
それゆえに活動しているセッションの時間記録のために使われている仮想時計が単調に増加することは、不公平と窮乏とにつながることになる。この問題は、セッションの終了時間を任意に進め変更できるような仮想時計関数によるいかなるPHQ手法によっても、オーバーブッキングな状況で発生する。
【００１６】
発明の概要
この発明は、実体がサーバーによって操作される時のスケジューラの制御に関するものである。スケジューラはN個の実体からなる。但しNは2に等しいかそれより大きい整数である。個々の実体はサーバーから受けるサービスの転送レートを有している。スケジューラは、 N個の実体の終了時間 fiを保持するメモリを含む。fiは i番目の実体がサーバーによって操作されるべき時間に対応する。スケジューラは、終了時間fiが判別できるように仮想時間のトラック(経過)を保持する仮想時計を含む。スケジューラは、終了時間の関数としてサーバーが作用するべき実体を選択する、コントローラを含む。コントローラは実体にサービスを提供するために仮想時間を遅らせる。コントローラは仮想時計とメモリーに接続されている。
【００１７】
この発明は、実体（entities）がサーバーに対して操作される、制御のためのスケジューラに関係する。スケジューラはN個の実体から構成される。但しNは2に等しいかそれよりも大きい整数である。個々の実体は、サーバーからサービスを受ける転送速度（rate）を持っている。N個の実体のうちの少なくとも最初の1つには、2つ以上の接続（connections）があり、2つの接続のうちの少なくとも1つがサービスを待っており、複数の接続の中、少なくとも１つがサービスを受けることを待っており、かつ終了時間がサービスを待っている実態の中で、もっとも早い終了時間を有している時に、コントローラは最初の実体を選択し、サービスを提供する。スケジューラは、N個の実体の終了時間fiを保持しているメモリーを持ちっている。但しfiはサーバーによって操作を行われるべきi 番目の実体の時間に対応する。スケジューラは仮想時計を持ち、その時計は終了時間 fiが判別できるように仮想時間のトラックを保持する。スケジューラは、終了時間の関数としてサーバによって操作されるべき実体を選択するコントローラを具えている。コントローラは実体に対してサービスを提供する仮想時計を遅らせる。コントローラは、仮想時計とメモリーとに接続されている。
【００１８】
この発明はサービスを提供するサーバーのスケジュールを行う方法に関係する。この手法は、サーバーからの第1の転送レートを持つ第1の実体から第1の要求を受け取るステップを含む。次に第1の実体が第1の実体からのサービスを受け取ろうとする時に、その終了時間をメモリーに蓄えるステップがある。次に、サーバーからサービスを受け取る2番目の転送レートを持つ第2の実体から第2の要求を受け取るステップがある。次に、第2の実体がメモリー中のサーバーからサービスを受け取る時に、その終了時間を蓄えるステップがある。第2の実体の終了時間は、第1の実体の終了時間と同じである。そして第1の実体に対してサービスを提供するステップがある。次に仮想時間を止めるステップがある。そして、第1の実体がサーバーからサービスを受け取るのと同じ仮想時間に、第2の実体に対してサーバーからサービスを提供するステップがある。
【００１９】
本発明のATMスケジューラに望まれる特徴は次のようなものである。
１．セッションに対して、保証されたバンド幅に見合うように供給出来ること。
VC毎のキューイングが出来ることが仮定される。
２．ジッターを最小に出来ること。
VCに対してセルを送出する際の大きなジッター（大きなセル配送の変化）が、下流の装置に対してセルの脱落を発生させるような破滅（burstiness）につながることは、よく知られている。このような問題を最小化するために、スケジューラはセルを円滑に送出する必要がある。
３．転送レート制限
異種のネットワーク機器の環境では、ATMスイッチは限られたバッファーとバンド幅を制御する能力を用いて末端やエンドユーザーの装置にまでトラフィックを供給する必要がある。それゆえ、そのような装置に向けた断続的なトラフィックによる激しいバーストは取りこぼされることとなる。このようなロスを最小化することは、本質的に興味のある問題である。この目標はネットワーク（もしくはATMスイッチ）がトラフィックを装置に対してそれが取り扱うことが可能な転送レートで供給することにより達成される。バーストは、目的に対して排出されるまでの間、ネットワークの内部に蓄積される。上のような目的を達成するために、ATMポートスケジューラはトラフィックを予め制限された転送レートに制限する能力を持つ必要がある。
４．階層的な転送レート制限
上記のような転送レート制限は、単一のセッション（外形を付ける形成法と同様)のレベルにおいては実現可能であるし、同じ目的地に向けたセッションの組み合わせのようなレベル、例えばT1やxDSLのパイプのようなスピードの遅いより下流へのポートにおいても実現可能である。この文書において、このようなセッションのグループは仮想回線として引用される。階層的な転送レート制限は、転送レートを仮想回線が寄せ集められたレベルにおいても制限される必要があるし、また個々のセッションの仮想回線のレベルにおいても制限される必要がある。
５．オーバーブッキング
ほとんどの場合において、転送レートの制限された仮想回線上の入力トラフィックは、その転送レートの制限と比較して非常に小さい。それゆえ仮想回線のためのバンド幅を、それらの転送レートの制限によって予約するすることは、ポートのバンド幅の非常な無駄遣いにつながる。この問題を解決するには、ポートにおいて転送レート制限をオーバーブッキングする機構が必要となる。それゆえ、あるポートに属するすべての仮想回線の転送レート制限の合計が、ポートのバンド幅（回線転送レート）より大きくなることがありうる。
これはバーストを起こしやすかったり、断続的なトラフィックにおいては特に有益である。もっとも良い場合においては、入力ソースのトラフィックは、個々のセッションが要求したレートで受信できるように分散して到着する。それゆえオーバーブッキングは、統計的な意味合いにおける多重化を利用することを可能にする。最も悪い場合においては、複数のセッションが同時に到着した際に、そのため集約されたトラフィックが回線転送レートを超えてしまったとき、このメカニズムはセッションに対するサービスの質を支障のない程度で低下させる。そのような機構は、本発明の一部を構成する。
６．セッション保証を満足しているオーバーブッキング
オーバーブッキングにおけるサービスの転送レート低下は、CBRやrt-VBRのような時間に影響を受けやすいセッションにとっては許容できないものがある。このようなセッションはサービスを受け取る上で、例えば彼らが要求する転送レートは常に維持されるといったように、より高い優先度を与えられるべきである。この問題は、このようなセッションが仮想回線の一部分であるような場合に、より興味深いものとなる。例えば仮想回線が10Mbpsといった転送レートを要求しているとする。仮想回線は二つのセッションC0とC1からなるとする。セッションC0は7Mbpsの転送レートを要求し、C1は８Mbpsの転送レートの保証を要求しているとする。両方のセッションが活動的になったとき、C1にとって期待される振る舞いは8Mbpsが保証されながら受信でき、C0は２Mbpsもしくはそれに等しくなり、このような集約により回線の転送レートである10Mbps以下になる。このような品質保証を確実としながら、オーバーブッキングにおける階層的な転送レート制限を達成するためのメカニズムは、この書類において提案される装置の一部を構成する。
ここで、仮想回線により受信される集約されたバンド幅が特定の転送レートに制限されることが必要であるが、仮想回線に属する個々のセッションのレベルにおける品質保証が要求を満たすことも重要である。上記のことを保証するために、スケジューラにおける転送レートの間で、二つの関係が含まれることが必須である。
・仮想リンクにおけるセッションの保証の合計は、仮想回線の転送レートの制限よりも少ない。
・すべてのセッションのすべての保証の合計が、回線の（ポートの）転送レートよりも小さい。
【００２０】
添付の図面に於いて、本発明の好ましい実施例及び本発明を実行する好ましい方法は、以下に記述される。
【００２１】
【詳細な記述】
図面中で同様な参照番号はいくつかの図を通じて同様な又は同一の部分に言及する。特に図９を参照する。該図には、サーバ(14)により実体(12)が作動しているときに、制御するスケジューラー(10)が示されている。スケジューラー(10)はＮ個の実体(12)を有し、ここでＮは１以上又は１に等しい整数である。各実体はレートを有し、該レートでサーバ(14)からサービスを受信する。スケジューラー(10)はＮ個の実体(12)の終了時間ｆiを有するメモリー(16)を具え、ｆiはｉ番目の実体がサーバ(14)により作動される仮想時間に対応している。スケジューラー(10)は、終了時間ｆiが識別されるように仮想時間のトラックを保つ仮想クロック(18)を有する。スケジューラー(10)は、終了時間の関数として、サーバ(14)により作動される実体(12)を選択するコントローラ(20)を有する。オーバーブッキングを容易にすべく、コントローラ(20)は仮想時間を遅らせて、実体(12)にサービスを供給する。コントローラ(20)は仮想クロック(18)及びメモリー(16)にコネクションされている。
【００２２】
各実体はサーバ(14)からサービスを要求するレートを有している。実体(12)は１よりも大きなレートの総和を有する。コントローラ(20)は好ましくは、各実体のレートの関数として各実体にサービスを供給し、レートの総和量は１より大きい。
【００２３】
好ましくは、オーバーブッキングを容易にする為に、コントローラ(20)は、仮想時間に等しい終了時間を有する全ての実体(12)がサーバ(14)からサービスを受信完了するまで仮想時間を停止させる。コントローラ(20)は好ましくは以下に対応した仮想時間を作動する。
Ｖ(ｔ＋１)＝ｍｉｎ(Ｖ(ｔ)＋１、ｍｉｎＦ)、
但し、ｍｉｎＦは終了時間を有する全ての実体の中で最も早い終了時間を示す。
【００２４】
好ましくは、メモリー(16)はＮ個の実体(12)の開始時間ｓiを有し、但しｉは１≦ｉ＜Ｎで、整数である。ｓiはｉ番目の実体がサーバ(14)から次のサービスを要求でき、メモリがＮ個の実体(12)のレート限界時間ＴＩiを有しているときの最も早い時間に対応している。コントローラ(20)は好ましくは、最も早い終了時間で実体にサービスを供給する。図１０に示すように、コントローラ(20)には階層があり、それによってＮ個の実体の少なくとも最初の実体が、第２層にてコントローラ(20)の複数の実体を表し、第２層の第２番目の実体が第３層にてコントローラ(20)の実体を表す。
サービスを要求しているコネクションは、スケジューラー中でコネクションが最初に接続するコントローラに繋がったメモリ中にて、時間間隔と開始時間を格納する。より低いレベルのコントローラに繋がったコントローラは、時間間隔、開始時間をより低い層のコントローラに繋がったメモリに格納する。第１層のコントローラは第１の実体を選択し、実体が適格で、サービスを待っている実体の中で最も早い終了時間を有しているときにサービスを供給し、またローカルメモリ内の実体の開始及び終了時間の更新もする。第１の実体は次段の中にもう１つのコントローラを含む。該もう１つのコントローラは更に第２の実体を選択し、第２の実体が適格で第２のコントローラでサービスを待っている実体の中で最も早い終了時間を有しているときにサービスを供給し、またローカルメモリ内の実体の開始及び終了時間の更新もする。
各コントローラは仮想クロックを維持し、該仮想クロックは異なる段又は同じ段の他のコントローラの他の全ての仮想クロックから独立し、全ての仮想クロックは、該クロックにコネクションされた適格な実体の終了時間に基づいて更新される。全ての仮想クロックは、各々のサイクル時間が増される。最小の動作が仮想クロックに実行され、コントローラがサービスを受信したときに、クロックの正確な値を得て、次のレベルでコントローラがクロックの正確な値を用いることを許容する。
コントローラに於ける実体のレートの総和は１より大きいことが可能であり、このようにしてスケジューラーがオーバーブックされることを許し、セッション密集中(congestion)にコントローラはオーバーブッキング動作を反映して、仮想時間の減速を確実にする。実体によりオーバーブッキングなしに受信されたレートは、実体のレートに等しい。しかし、オーバーブッキングとともに実体によって受信されたレートは、実体のレートの最小値か、又はコントローラにて適格な実体のレートの総和により縮小された実体のレートの最小値である。
【００２５】
好ましくは、少なくとも１つの実体(12)は、サービスを待っている実体(12)の中で最も早い終了時間である終了時間を有するときに、サーバ(14)からのサービスが保証される。サービスが保証された実体がサービスを待っている実体(12)の中で最も早い終了時間を有することを特定するため、コントローラ(20)がどの実体が次にサービスを受けるべきかを決めているときに、サービスが保証された実体がコントローラ(20)によって最先に吟味されることが望ましい。
【００２６】
本発明は、実体(12)がサーバ(14)上にて操作を受けているときに制御するためのスケジューラー(10)に関するものである。スケジューラー(10)はＮ個の実体(12)を有し、Ｎは１より大きい又は１に等しい整数である。各実体はサーバ(14)からのサービスを受けるべきレートを有する。Ｎ個の実体(12)中の少なくとも最初の実体(121)は複数のコネクションを有し、複数のコネクションの少なくとも１つがサービスを待っており、サービスを待っている実体(12)の中で最初の実体(121)が最も早い終了時間を有しているとき、コントローラ(20)は最初の実体(121)を選択して、サービスを供給する。
スケジューラー(10)は、Ｎ個の実体(12)の終了時間ｆiを有するメモリー(16)を有し、ｆiはｉ番目の実体がサーバ(14)により操作されるべき時間に対応する。スケジューラー(10)は終了時間ｆiが特定されるように仮想時間のトラックを保つ仮想クロック(18)を有する。スケジューラー(10)はコントローラ(20)を有し、該コントローラは、終了時間の関数としてサーバ(14)により操作されるべき実体(12)を選択する。コントローラ(20)は、仮想時間を遅らせて実体(12)にサービスを供給する。コントローラ(20)は、仮想クロック(18)とメモリー(16)にコネクションされる。
【００２７】
本発明は、図１２に示すように、サーバ(14)からサービスをスケデューリングする方法に関する。該方法は、サーバ(14)から受けるサービスへの最初のレートを有する最初の実体(121)からの最初の要求を受信する工程を有する。次に、最初の実体(121)がサーバ(14)からサービスを受けるべき時までに、終了時間をメモリー(16)に格納する工程がある。然る後、サーバ(14)から受けるサービスについて２番目のレートを有する２番目の実体から２番目の要求を受信する工程がある。次に、２番目の実体がサーバ(14)からサービスを受けるべき時に、終了時間をメモリー(16)に格納する工程がある。然る後、サービスを最初の実体(121)に供給する工程がある。次に、仮想時間を停止する工程がある。このとき、サーバ(14)から２番目の実体にサービスを供給する工程がある。
【００２８】
本発明は、実体(12)の１より大きなレートの総和を許すことにより、オーバーブッキングを許容する。最初の実体(121)にサービスを供給する工程は、好ましくは最初の実体(121)の最初のコネクションへサービスを供給し、最初の実体(121)の２番目のコネクションへサービスを供給する工程を含む。
好ましくは、最初の実体(121)にサービスを供給する工程の前に、終了時間を具える実体(12)の中で最初の実体(121)が有する終了時間が最も早い終了時間であるか否かを決定する工程があるのがよい。
【００２９】
好ましい実施例の動作にて、従来のスケジューラーのレート限定及びオーバーブッキングに関する主要な問題は、セッションの開始・終了時間の範囲を越えて仮想クロックが進む可能性があることである。新たな仮想クロック(18)関数がここに記載されており、それは実体(12)のコネクション又はセッションが、オーバーブッキングに関して適切に扱われることを確実にする。新たな仮想クロック(18)関数は、仮想クロックを遅らせ、オーバーブックされたセッションへの遅いサービスに歩調を合わせるとの概念に基づいている。このようにして、新たに到達したセッションは、クロックを用いて開始時間を時刻記録(timestamp)し、もはや不公平に有利にはならない。
【００３０】
最小限の関数と、他の動作しているセッションの中での最小の終了時間とを適用するように仮想クロック(18)の計算は増やされる。こうして、仮想クロック(18)関数は以下のようになる。
Ｖ(ｔ＋１)＝ｍｉｎ(Ｖ(ｔ)＋１、ｍｉｎＦ)、
ここで、ｍｉｎＦは全ての溜った(backlogged)セッションの中で最小の終了時間を示す。最小の終了時間に基づく仮想クロック(18)のスローダウンには、仮想クロックをセッションの終了時間の範囲内に保つことである。このようにして、動的になりつつあるセッションは、既に動的になったセッションの開始・終了時間よりも遙かに先の開始・終了時間は刻まれない。このことは、そのようなセッションの飢餓状態を回避する。動的セッションにより見られるサービスレートは、即時的なオーバーブッキング要素により分割され要求されたレートとして決定される。
【００３１】
上記の例は新たな仮想クロック(18)実行とともに図４に示される。
・Ｖ(ｔ)は動的セッションの中で最小終了時間を決して越えない。従ってｔ＝１０、０００にあってはＶ(ｔ)の値はセッションＣ１の６６６９という最小終了時間により限定される。
・ｔ＝１０、０００というそのようなより遅い時間のときに、動的になりつつあるセッションＣ２は、Ｖ(ｔ)＝６６６９に等しい開始時間が刻まれる。
・この実行に於いて、Ｃ２は１５、０００の代わりに時間１０、００２にてサービスされる。従って、セッションによっては、任意の飢餓状態は見られない。
【００３２】
前述したとおり、転送速度制限は単一セッションのレベル及び同一着信地に向けられた一組のセッションレベル、例えばＴ１又はｘＤＳＬパイプなどの、より低速の下流ポートのレベルでも実行されることが必要であるだろう。その様な１群のセッションは、仮想リンクと称する。階層的なレートリミティングでは、集合的仮想リンク（ＶＬ）のレベルにおいて及び、ＶＬ中の個々のセッションに於いてもレートリミティングを必要とする。ＲＬでは、ＶＬｓ間のオーバーブッキングが許される。オーバーブッキングした場合、ＲＬが利用できる帯域は、各帯域のレート配分に比例したＶＬｓに分けられる。同様にＶＬ中のセッション間でのオーバーブッキングも又許されている。オーバーブッキングがある場合、ＶＬが利用できる帯域は、各レート配分に比例してセッション間で分けられる。
【００３３】
実施例
図５は、レート制限されたＶＬをオーバーブッキングする様子を図面で示した１例である。２つのセッションＣ０とＣ１が、１つのポートの同一ＶＬに属している。到着したセルは別々の待ち列（queue）でバッファーされる。ＶＬは４／１０ラインレートにレートリミットされることになっている。セッションＣ０とＣ１は、ラインレートの２／１０と４／１０のレートに夫々リミットされる。これはＣ０だけがその待ち列にセルを有するときには、２／１０のレートにリミットされることを意味する。同じく、Ｃ１だけがその待ち列にセルを有するときは、それは４／１０のレートにリミットとされる。しかしながら両方のセッションがセルを有するときは、ＶＬレートは（２／１０＋４／１０）／（４／１０）＝１.５の率でオーバーブックされる。セッションによって受け取られるサービスは、オーバーブック要素で縮小される。この場合、Ｃ０とＣ１は、１.３３／１０と２.６６／１０のラインレートを夫々受取る。これらレートの合計は４／１０であることに注目すると、ＶＬのレートの限界は常に一定に維持されている。
【００３４】
仮想リンク（ＶＬ）レベルでのレートリミッター（ＲＬ）の実行は、前述した方式のセッションを仮想リンクに置き換えることによって得られる。ＶＬは、セッションがかつてそうであったように、正確にサービスされる。適格な仮想リンク間で、最小の終了時間の仮想リンクが選択されサービスされる。以前Ｖ（ｔ）として示したポートレベルでの基準仮想クロック(18)は、ＶP（ｔ）として示され、以下の議論に於いて仮想リンククロックとは区別できるようにする。以前説明したとおり、ＲＬ中ではＶＬｓ間のオーバーブッキングは許されている。オーバーブッキングの場合、ＲＬに利用可能な帯域幅は、夫々に配分されたＶＬ率に比例してＶＬｓの間で分けられる。
【００３５】
一旦ＶＬが決定されると、どのセッションがＶＬの下でサービスするかを決めるため、第２レベルの決定がなされる。望ましい実施例ではＶＬの下でセッション間で調整するために、同様な方式が複製される。各仮想リンクは夫々自身の基準仮想リンク(18)を有している。ＶＬｉの場合、これはＶLi（ｔ）と表示される。ＶＬｉ中のセッションはＶLi（ｔ）に基づいた時間スタンプがなされる。前述したとおり、ＶＬ中でセッション間のオーバーブッキングは許されている。オーバーブッキングの場合、ＶＬに利用できる帯域幅は、セッションに割り当てられた夫々のレートに比例してセッション間で分けられる。各仮想リンクのための個別の基準クロックは、セッションが異なったリンクの下で、個別に処理されることを許容する。このことは、異なった仮想リンクの下で、異なったレベルのオーバーブッキングを許す。全体の方式は図６に示す。望ましい実施例のための対応する疑似コードを附属書類に示した。
【００３６】
以下は最も重要な特徴である。
・活動しているセッションだけを維持し、スケジュールすることと同様にして、第１レベルに於いて調整しながら活動している仮想リンクは検討されるだけである。あるセッションが存在し、その下で仮想リンクが働らき、適正であるとき、仮想リンクは働らく。この定義の背景にあるモチベーションは、この仮想リンクがスケジュールされた時、その下でのセッションは第２レベルの調整によってそれも又スケジュールされることが出来、サイクルは無駄にはされないということである。ＶＬiが活動的であるかを決める工程は、次のようにして決めることが出来る。
−仮想リンクの下で、全セッションの中で最小開始時間のトラックを保持する。これをｍｉｍＳｖとして表す。（Ｓｖ≦ＶLi(ｔ))の比較が真であることは、ＶＬの下での少なくともあるセッションは適切であることを示している。
−リンクが空でない時、ＥＭＰＴＹ（ｉ）＝ＦＡＬＳＥ、すなわちその下で活動的セッションが存在するときトラックを維持する。パラメータｍｉｎＳｖは、ＥＭＰＴＹ（ｉ）＝ＦＡＬＳＥの場合にだけ真である。
−したがってＶＬは次の場合には活動的である。
ACTIVE(i)＝((EMPTY(i)＝FALSE)＆＆(minＳｖ≧ＶLi(t)))
・ポートシステムのクロックは、仮想リンクの適格さを計ることに屡々使用され、セル時間ごとに更新される。
ＶP（ｔ＋１）＝ｍｉｎ（ＶP（ｔ）＋１，ｍｉｎＦＴ）
ただしｍｉｎＦＴは、働いている仮想リンクのすべての中で最小の終了時間(finish time)を示す。
・前述したとおり、オーバーブッキングを許すために、各ＶＬのための個別の独立した仮想クロック（１８）が維持される。全てのＶＬクロックは次式に基づいた知識のサイクルごとに更新される。
ＶiL（ｔ＋１）＝ｍｉｎ（ＶiL（ｔ）＋１，ｍｉｎＦＶ）
ただし、ｍｉｎＦｖはＶＬｉの下で働いている全てのセッションの中で、最小終了時間である。多数の仮想リンクがあるので、ハードウェア中の制約された数の最少の比較器では上記操作は困難となる。賢い方式を用いることによってハードウェアの必要事項は減らすことが出来る。仮想クロック（１８）は、全ＶＬｓについてサイクルごとに盲目的に増分している。ある仮想リンクがサービスのために選ばれた時だけＭｉｎＦＶの最小の操作が実行され、ＶiL（ｔ＋１）の正しい値を得る。この操作は該正しい値をセッション間で第２レベルの調整に用いる以前に行われる。ＶＬの下でセッションがオーバーブックされた時、この方式はＶＬクロックが減速に対応できるようにし、所望するオーバーブック操作を確実に行わせる。
・ＶＬｓが一緒になってポートのオーバーブックをしない時。個別の各ＶＬは、その中のセッションに依っては依然としてオーバーブックされることが出来る。しかしながら、オーバーブックされたＶＬ中のセッションは、他のＶＬｓのセッションには影響を与えない。
【００３７】
オーバーブッキングによってサービスレートの品質が低下することは、例えばＣＢＲ，ｒｔ−ＶＢＲのごとき高感度のセッションには、時によっては許容できないことがある。その様なセッションは、サービスの受取りについてより高い優先順位が与えられ、それらのサービスレートが満足出来るようにせねばならない。その様なセッションが仮想リンクの一部であるときは、問題は一層難しくなる。図７は、レートが制限されているＶＬと、補償されたサービスを要求しているセッションをオーバーブッキングしたときの様子を描いている。
【００３８】
実施例
２つのセッションＣ０とＣ１は、１ポート上の同じＶＬに属している。到着するセルは、別々の待ち行列(queues)中でバッファリングされている。ＶＬのレートは、４／１０のラインレート以内に制限されている。セッションＣ０が２／１０のレート保証を要求し、セッションＣ１は、４／１０のラインレートのレート制限を要求する。これは、Ｃ０だけがその待ち行列中にセルを有するときに、Ｃ０は２／１０のレート以内に制限されることを意味している。同様に、Ｃ１だけが待ち行列中にセルを有するときに、Ｃ１は４／１０のレート以内に制限される。しかしながら、両方のセッションがセルを有しているときには、セッションＣ０は、２／１０のラインレートを受信し続ける。ＶＬレートの残りは、４／１０−２／１０＝２／１０であり、これをＣ１が受信する。これらレートの合計は４／１０であることに注目すると、ＶＬのレートの制限は、常に維持される。保証が確保されているときに、オーバーブッキングにより、そのような階層的レートの制限を達成させる機構は、以下のように説明される。
【００３９】
スケジューラー(10)におけるレート間に、２つの関係が必然的に含まれていることにも注意すべきである。
・仮想リンク中のセッション保証の総計は、仮想リンク上のレート制限よりも小さい。従って、上述の例では、セッションＣ０は、それのＶＬのレートである４／１０のラインレートより多くを要求することはできない。
・すべてのセッションについての全保証の総計は、ラインレートよりも小さい。
【００４０】
先の実施例は、ＲＬブロック(26)としてここで言及しているが、ＲＧブロック(24)は、個々のセッションの保証に応ずるための目的で加えられている。ＲＧブロック(24)は、オーバーブッキングされるべきではない。ＲＧブロック(24)は、前述の単調なスキーム(flat scheme)のように実行する。ＲＧブロックは、自己基準用の仮想クロック(18)を具える。全体のスキームは図８に示している。ＲＧブロック(24)についての次いで生ずる付加的な制約と、ＲＬブロック(26)との相互作用は、次のとおりである。
・所与のセルスロット中では、ＲＬを越えたＲＧを提供するために、より高い優先順位が与えられる。ＲＧに適正なセッションがない場合にのみ、ＲＬの下でセッションが検討される。
・ＲＧから提供されるセッションについて、ＶＬの対応する開始時間は、ＲＬ中で更新される。これが、ＶＬによってそのセッションを介し、ＲＧ中で受信されたバンド幅を決める。ＶＬがＲＬを介して獲得できる付加的なバンド幅は、バンド幅の合計が、そのレート制限よりも下方に保たれるように制限される。
【００４１】
図１０に示すように、スケジューラには、階層が存在する。この構成では、１つのポートについて、主コントローラ(20)は、コネクション(19)に代えて、１又は２以上の付加コントローラ(20)に接続でき、要望がある場合には、１又は２以上のこれら付加コントローラを、順にコントローラに接続することもできる。サービスを要求する各コネクションは、夫々、時間間隔、開始時間、終了時間を、メモリー(16)に格納しており、該メモリー(16)は、コネクションがスケジューラ(10)中で最初に接続されたコントローラ(20)に関連づけられる。コントローラ(20)は、コネクションの代わりに、下位レベルのコントローラ(20)に接続され、同様に、下位のコントローラ(20)に関連づけられたメモリー(16)の中に、時間間隔、開始時間及び終了時間を記憶している。
【００４２】
任意のコネクション(19)又は次の上位層(ポートから離れる側)にて、そこへ接続されたコントローラ(20)がサービスを受けるのに適しているときは、ある層のコントローラ(20)は、サービスを受けることに適しているか否かを決定する。サービス受信の適格を定めるコントローラ(20)は、次の下位層(ポートに近い側)で接続されているコントローラ(20)に、サービスを伝達する。
【００４３】
如何なる所与のスロットタイムにおいても、サービスを提供するための決定は、主コントローラ(20)から、中間コントローラを通って、コネクションで終わるところまで伝達する。主コントローラは、そのメモリー(16)中の適正な情報と最も早い終了時間に基づいており、次の上位層でコントローラに直接接続された実体のどれが、サービスを受信することを決定する。次に、そのローカルメモリ中の実体の開始と終了時間が更新される。選択された実体が、次の層中の他のコントローラ(20)である場合には、該コントローラは、そのメモリー(16)中の適格についての情報と最も早い終了時間に基づいて、次の上位層でコントローラ(20)に直接接続されたどの実体がサービスを受信することに関して、同様の決定を順に行なう。このように、決定プロセスは、階層を通じて伝達する。それは、コネクションをサービス対象に選択したときに終了する。従って、階層的な構造は、階層的手法によって、順応性(flexibility)が帯域幅を代表することを許容している。所与のコントローラ(20)の下でのコネクションの組は、あるレート以内に累積的に制限されており、これは、次の下位層における接続されたコントローラ(20)中でそのようなレートに対応する時間間隔をプログラミングすることによって行なわれる。
【００４４】
関連づけられたコントローラに対する仮想クロックは夫々、異なる層又は同じ層の他のコントローラの他のすべての仮想クロックとは独立して、仮想時間を維持することに注意すべきである。各々のスロット時間、すべての仮想クロックは、仮想ブロックに接続された適正な実体の終了時間に基づく等式(１)で記載したように更新される。等式(１)は、スケジューラ中で、各仮想クロック(18)に対して行なわれる増分(increment)と最小の操作を要求する。多数の仮想リンクを用いて、上述の操作をハードウェア中で実行するには非常に費用がかかる。ハードウェアの要件は、次のスキームを用いることによって減じることができる。すべての仮想クロック(18)は、各スロット時間で盲目的に増大する。コントローラ(20)がサービスを受信したときに、クロックの正確な値を得るために、最小の操作を仮想クロック(18)上で行なう。このことによって、コントローラは、次のレベルでの調整(next level of arbitration)によりクロックの正確な値を用いることができる。コントローラの下で実体がオーバーブッキングされているとき、スキームは、所望のオーバーブッキング操作を保証するために、仮想クロックがスローダウンを反映する(reflect)ことを保証する。
【００４５】
図８及び図１１を参照すると、保証されたサービスは、上述した階層的な構造で確立することができる。本実施例では、サービスの保証レートを要求するコネクションは、レート制限されたコントローラの主コントローラと下位層のコントローラから分離したレート保証コントローラ(20)に接続される。各スロット時間において、階層づけられた主レート制限コントローラ(10)が、コントローラの下で、如何なるコネクションとの手続を進める前に、レート保証コントローラ(20)は、まず、サービスを受信するレート保証コネクションが存在するかどうかを調べるための確認を行なう。もし存在するのであれば、他のレート制限されたコントローラのコネクションがサーバ(14)からサービスを受信する前に、これらコネクションは、まず、サーバ(14)からサービスを受信する。レート保証コネクションが、また、特殊なレート以内に制限されたレートであるコネクションの組に属するのであれば、そのようなコネクションによって受信されたレートを制御する階層に沿ってレートリミッター中のコントローラ(20)は、受信したサービスをアカウントするために、開始と終了時間を更新する。
【００４６】
本発明は、例示を目的とした上述の実施例で詳細に説明されているが、これら説明は、単にその目的のためのものであり、次の請求の範囲の記載された事項を除いて、本発明の精神と範囲から離れることなく、当業者が変形を加え得ることは理解されるべきである。
【００４７】
なお、図１３及び図１４に、オーバーブッキングをサポートするフラットレートリミッターの実施についての擬似コードを示す。
また、両レベルでのオーバーブッキングをサポートする階層レートリミッター手法についての擬似コードを、図１５及び図１６に示す。
【図面の簡単な説明】
【図１】典型的なＰＦＱスキーム内にて維持される従来の仮想クロック及びセッションの開始／終了時間を示す。
【図２】オーバーブッキングが存在するときの望ましい動作を示す例である。セッションＣ0及びＣ1は夫々２／４及び３／４のレート限界を要求する。このように、Ｃ0、Ｃ1が同時に動作しているときは、ラインはオーバーブックされる。そのような期間中、夫々２／５及び３／５のラインレートを受信する。それ以外の場合は、要求したレート限界のサービスを受信する。
【図３】オーバーブッキングが単純に増加する仮想クロック時間関数が与えられて、レート限界の実行に伴う飢餓状態(starvation)の問題を示す例である。行１は実時間(ｔ)の進行を示す。行２はこの例のｔのように、対応するＶ(ｔ)の値を示す。行３、４及び５は、セッションＣ0、Ｃ1及びＣ2の開始／終了時間を夫々示す。
【図４】オーバーブッキングを有するときのレートリミッターを新たに実行する際に伴うセッションの動作を示す例である。この実行に於ける仮想時間機能は、動的セッションの最小終了時間を越える(move ahead)ことは許されない。行１は、実時間(ｔ)の進行を示す。行２はこの例のｔのように、対応するＶ(ｔ)の値を示す。行３、４及び５は、セッションＣ0、Ｃ1及びＣ2の開始／終了時間を夫々示す。
【図５】限定されたレートＶＬの内部にてオーバーブッキングが存在するときの望ましい動作を示す例である。セッションＣ0及びＣ1はラインレート４／１０に限定されたレートＶＬの内部で、夫々ラインレートが２／１０及び４／１０のレート限界を夫々要求する。従って、Ｃ0、Ｃ1が同時に動作しているときは、ＶＬはオーバーブックされる。その期間中、夫々１.３３／１０及び２.６６／１０のラインレートを受信する。それ以外の場合は、要求したレート限界のサービスを受信する。
【図６】階層的レートリミッター(ＲＬ)の実行であり、ＶＬ間で、更にはＶＬ下にあるセッション間でのオーバーブッキングを支持する。ポート基準クロックはＶP(ｔ)である。各仮想リンクＶＬiは自身の基準クロックＶL i(ｔ)を有する。
【図７】限定されたレートＶＬの内部で、あるオーバーブッキングの存在下に於ける望ましい動作を示す例である。ラインレートが４／１０に限定されたレートＶＬの内部でセッションＣ0は２／１０のレートを保証することを要求し、セッションＣ1はラインレートが４／１０のレート限界を要求する。従って、Ｃ1とＣ0が同時に動的であるときは、ＶＬはオーバーブックされる。その期間中、Ｃ0は２／１０のラインレート保証を受信し続け、一方Ｃ１はラインレートの２／１０を受信するのみである。
【図８】階層的なレート限界及びオーバーブッキング、更に保証されたセッションのレート支持を許す例である。ＲＧブロック内のセッションは、ＲＬブロックよりもより上位の優先順位を得る。ＲＧから出力して供されるセッションがあって、それもまたＶＬに属するならば、ＶＬの対応する開始時間は、ＲＬ内で更新される。そのような演算は、ＶＬがＲＬを介して得ることができる更なる帯域幅を制限し、それによってそのレート限界内にて残るようにする。
【図９】本発明のスケジューラーの概略図である。
【図１０】階層的な構造を有するスケジューラーの概略図である。
【図１１】レート保証部とともに階層的な構造を有するスケジューラーの概略図である。
【図１２】本発明の方法のフローチャートである。
【図１３】オーバーブッキングをサポートするフラットレートリミッターの実施についての擬似コードを示す図である。
【図１４】図１３の続きを示す図である。
【図１５】両レベルでのオーバーブッキングをサポートする階層レートリミッター手法についての擬似コードを示す図である。
【図１６】図１５の続きを示す図である。
【符号の説明】
(10)  スケジューラー
(14)  サーバ
(16)  メモリー
(18)  仮想クロック
(20)  コントローラ
【図１】
0004327948.tif 000002
【図２】
0004327948.tif 000003
【図３】
0004327948.tif 000004
【図４】
0004327948.tif 000005
【図５】
0004327948.tif 000006
【図６】
0004327948.tif 000007
【図７】
0004327948.tif 000008
【図８】
0004327948.tif 000009
【図９】
0004327948.tif 000010
【図１０】
0004327948.tif 000011
【図１１】
0004327948.tif 000012
【図１２】
0004327948.tif 000013
【図１３】
0004327948.tif 000014
【図１４】
0004327948.tif 000015
【図１５】
0004327948.tif 000016
【図１６】
0004327948.tif 000017