(57)【特許請求の範囲】
【請求項１】
予め定められたセル伝送時間間隔で仮想チャネルエントリの非同期タイムモード転送のためセルスケジューラを動作させる方法であって、セルスケジューラは、第１の型の複数のキューと、第２の型の少なくとも１つのキューと、第１のキューおよび第２のキューの間で仮想チャネルエントリを転送するための手段とを含み、
前記方法は各間隔において、
第１の型のキューの１つを反復して選択する工程と、
もし選択されたキューが少なくとも１つのエントリを有していれば、選択されたキューから第１の型のすべてのエントリを第２の型のキューへ転送する工程と、
第２の型のキューが少なくとも１つのエントリを有していれば、第２の型のキューのヘッドにあるエントリをエントリＥ１として選択して、そのエントリＥ１を伝送する工程と、
現在時間が、そのエントリＥ１が次に伝送される時間よりも早ければ、前記エントリＥ１を、第１の型のキューの１つのテールに付け加える工程と、
現在時間が、そのエントリＥ１が次に伝送される時間よりも早くなければ、前記エントリＥ１を、第２の型のキューのテールに付け加える工程とを含む、セルスケジューラを動作させる方法。
【請求項２】
現在時間が、そのエントリＥ１が次に伝送される時間よりも早いか否かを決定する工程は、エントリＥ１が最後に伝送されてからエントリＥ１が次に伝送される時間までの時間間隔を表すステップを決定する工程を含み、前記ステップは整数であり、
前記ステップを決定する工程は、
ステップサイズを累算された値に加算する工程を含み、前記ステップサイズはエントリＥ１の連続した伝送間の所望の時間間隔を表す予め規定された値であり、累算された値はエントリＥ１の連続した伝送にわたって累算されたステップサイズの累算された端数部分を表し、前記ステップを決定する工程はさらに、
累算された値の整数部分を抽出する工程を含み、整数部分は前記ステップであり、前記ステップを決定する工程はさらに、
累算された値から整数部分を減算する工程を含む、請求項１に記載のセルスケジューラを動作させる方法。
【請求項３】
エントリＥ１が次に伝送される前記時間を示すタイムスタンプ値を更新する工程をさらに含み、タイムスタンプ値を更新する工程は前記ステップをタイムスタンプ値に加算する工程を含む、請求項２に記載のセルスケジューラを動作させる方法。
【請求項４】
現在時間を更新する工程をさらに含む、請求項１〜３のいずれかに記載のセルスケジューラを動作させる方法。
【請求項５】
予め定められたセル伝送時間間隔での仮想チャネルエントリの非同期タイムモード転送のためのセルスケジューラであって、セルスケジューラは、
第１の型の複数のキューと、
第２の型の少なくとも１つのキューと、
以下の処理を実行する第１の手段とを含み、
前記第１の手段は、
第１の型のキューの１つを反復して選択する処理と、
もし選択されたキューが少なくとも１つのエントリを有していれば、選択されたキューから第１の型のすべてのエントリを第２の型のキューへ転送する処理と、
第２の型のキューが少なくとも１つのエントリを有していれば、第２の型のキューのヘッドにあるエントリをエントリＥ１として選択して、そのエントリＥ１を伝送する処理と、
現在時間が、そのエントリＥ１が次に伝送される時間よりも早ければ、前記エントリＥ１を、第１の型のキューの１つのテールに付け加える処理と、
現在時間が、そのエントリＥ１が次に伝送される時間よりも早くなければ、前記エントリＥ１を第２の型のキューのテールに付け加える処理とを実行する、セルスケジューラ。
【請求項６】
第１の手段は、エントリＥ１のためのステップを決定する手段をさらに含み、そのステップは、エントリＥ１が最後に伝送されてからエントリＥ１が次に伝送される時間までの時間間隔を示し、
ステップを決定する手段は、
ステップサイズとともに累算された値の合計の整数部分を計算する手段を含み、前記ステップサイズはエントリＥ１の連続した伝送間の所望の時間間隔を表す予め規定された値であり、累算された値はエントリＥ１の連続した伝送にわたって累算されたステップサイズの累算された端数部分を表し、整数部分は前記ステップであり、前記ステップを決定する手段はさらに、
累算された値を更新する手段を含む、請求項５に記載のセルスケジューラ。
【請求項７】
第１の手段は、そのエントリＥ１が次に伝送される時間を示すタイムスタンプ値を保持する手段を含む、請求項５または６に記載のセルスケジューラ。
【請求項８】
仮想チャネルエントリの非同期タイムモード転送で使用されるスケジューリングシステムであって、前記システムは第１および第２のセルスケジューラを含み、第１のセルスケジューラは第１の優先順位を有し、第２のセルスケジューラは第１の優先順位よりも低い第２の優先順位を有し、第１のセルスケジューラおよび第２のセルスケジューラの少なくとも１つは請求項５または６の構成を有する、スケジューリングシステム。
【請求項９】
第１のセルスケジューラおよび第２のセルスケジューラのそれぞれは、請求項５または６の構成を有する、請求項８に記載のスケジューリングシステム。
【請求項１０】
仮想チャネルエントリの非同期タイムモード転送で使用されるスケジューリングシステムであって、前記システムは第１および第２のセルスケジューラを含み、第１のセルスケジューラの出力ラインは第２のセルスケジューラの入力ラインと結合され、第１のセルス
ケジューラおよび第２のセルスケジューラの少なくとも１つは請求項５または６の構成を有する、スケジューリングシステム。
【請求項１１】
第１のセルスケジューラおよび第２のセルスケジューラの一方は、第１のセルスケジューラおよび第２のセルスケジューラの他方よりも低い優先順位を有する、請求項１０に記載のスケジューリングシステム。
【発明の詳細な説明】
【０００１】
【発明の分野】
この発明は一般に、非同期転送モード（ＡＴＭ）ネットワークにおけるセルのスケジューリングに関し、より特定的にはＡＴＭネットワークにおけるタイムホイールセルスケジューリングに関する。
【０００２】
【発明の背景】
次に簡単な先行技術のタイムホイールスケジューラを図示する図１を参照する。いくつかのキュー１０がラウンドキュー１２に組織される。各キュー１０は、ゼロまたは１以上の伝送されるべき仮想チャネル（ＶＣ）エントリ１４を含む。スケジューラの動作を制御するため２つのタイムポインタが用いられる。すなわち、タイムポインタ１６と伝送ポインタ１８とである。タイムポインタ１６はセルタイムごとに１つのキュー１０から次のキュー１０へ時計回り方向に進み、それの後ろのキュー１０内のすべてのＶＣエントリ１４ができる限り早く伝送されねばならないことを指示する。伝送ポインタ１８はタイムポインタ１６に遅れていくかまたはそれとともに進み、どのキュー１０が現在サービスされているかを指示する。典型的には、スケジューリングは、キュー１０内にＶＣエントリ１４を置く役割を持つ外部マネージャ（図示せず）により行なわれる。
【０００３】
図１に示すような簡単なタイムホイールセルスケジューラは、いくつかの限界を有する。第１に、伝送ポインタ１８が新しいキューに到達するたびに、たとえそのキューが空であったとしても、複雑な計算が必要である。計算が必要である結果、実現できるキューの総数も限られる。さらに、キューの数の制限によって、ＶＣに割当てることができる最小帯域幅および帯域幅の分解能が限定される。ＶＣの数または属性のいかなる変更のためにも、キュー内の固定エントリを決定するため複雑な計算を再び行なう必要がある。
【０００４】
帯域幅の分解能が高く、多数のＶＣをサポートする能力を備える定ビット速度（ＣＢＲ）および可変ビット速度（ＶＢＲ）セルスケジューリングのための容易に実現される方法が必要である。
【０００５】
【発明の概要】
したがって、この発明は、帯域幅の分解能が高く多数のＶＣをサポートすることができるＣＢＲおよびＶＢＲセルスケジューリングのための容易に実現される方法を提供する。
【０００６】
この発明はさらに、伝送ポインタが新しいキューに到達するたびにそのキューが空であったとしても複雑な計算をせねばならないという必要性を取除く。
【０００７】
さらに、この発明は、ＶＣの数または属性が変更される場合に複雑な計算を行なう必要性を取除く。
【０００８】
上述のおよび他の目的を達成するため、そしてこの発明の目的により、帯域幅の高分解能および多数のＶＣを可能にする、複雑な再計算の必要性を除去する自動再スケジューリング機構を備えた、タイムホイールＡＴＭセルスケジューラが提供される。
【０００９】
スケジューラは、いくつかの回転キューと、１つまたは２つ以上の静止キューと、回転キューと静止キューとの間でＶＣエントリを転送するための手段とを含む。スケジューラは、各回転キューと静止キューとを漸進的に接触させることによって動作する。回転キュー内のすべてのＶＣエントリは静止キューに転送され、（もしエントリが存在すれば）セルタイムごとに物理チャネル上で１エントリが伝送される。
【００１０】
伝送の直後に、ＶＣの［ｍ，ｉ］属性（ｉセルタイムにおけるｍ個のセル）により決定されるステップにより、近づいてくる回転キューにエントリが再スケジュールされる。もしｍ／ｉが整数でなければ、その端数部分が累算器レジスタ内に記憶される。次の回転キューは静止キューと接触させられ、そのエントリが静止キューに付加される。次に、別のエントリが伝送され近づいてくるキューに再スケジュールされる。累算器レジスタがオーバーフローするとき、ちょうど伝送されたセルを再スケジュールするステップが、１だけ増分される。
【００１１】
結果として、新しいＶＣが付加されるとしても、または、既存のＶＣの特性が変更されるとしても、大域的な計算は必要ない。加えて、ｍ／ｉがキューの数に等しいかまたはキューの数よりも小さい限り、スケジューラは任意の数のＶＣを扱うことができる。
【００１２】
キューが次第に申込み過剰になってくると、セルはそれらの所望のステップよりも長い間静止キュー内に待機することになってしまうだろう。この課題を解決するため、各ＶＣエントリが近づいてくる適切な回転キュー内に位置づけられるとき、各ＶＣエントリにタイムスタンプが付加される。セルが再スケジュールされるとき、そのタイムスタンプと現在時間とが比較され、もしその差がその計算されるステップよりも大きければ、そのセルは静止キューへと再スケジュールされる。
【００１３】
結果的に、チャネルのさらなる申込み過剰に伴い、異なったＶＣの帯域幅が調節される。より高帯域幅のＶＣはより頻繁に静止キューへ再スケジュールされ、したがって、それらの帯域幅が減じられ、一方、より低帯域幅のＶＣはより稀に静止キューへ再スケジュールされ、したがってそれらに割当てられる帯域幅が維持される。したがって、スケジューラは再計算の必要なく、ＶＣの数および特性の両方における変化に対処することができる。
【００１４】
本明細書に組み込まれその一部をなす添付する図面は、この発明のいくつかの局面を示しており、本明細書とともにこの発明の原理を説明する役割を果たす。
【００１５】
【詳細な説明】
図２は、図１の簡単な先行技術のスケジューラよりも優れた改良例を図示しており、キュー内の固定エントリを有するのではなく、自動再スケジューリング機構を用いている。このスケジューラの動作は、ＶＣがサービスされるとき、その現在のキュー１０から取除かれ何らかの予め定められた固定ステップにより近づいてくるキュー１０内に位置づけられるという点を除いては、簡単な図１のスケジューラの動作といくらか類似的なものである。ステップはＶＣに割当てられる帯域幅を決定する。同一のキュー上に２つのＶＣが位置づけられるのでない限り、他のＶＣの数または特性の変化はそのＶＣの帯域幅に全く影響しない。しかし、サポートされる最小帯域幅は依然として、キューの数でチャネルの帯域幅を除したものに等しく、サポートされる別個の帯域幅はステップサイズで乗じた最小帯域幅に等しい。やはり、伝送ポインタが新しいキューに到達するたびごとにたとえそのキューが空であったとしても、計算が必要である。
【００１６】
次にこの発明の好ましい実施例を図示する図３を参照する。図１に図示した背景技術におけると同様、キュー１０のラウンドロビンキューからなるタイムホイール１２が構築される。伝送がスケジュールされるＶＣエントリ１４が、キュー１０内に置かれる。タイムホイール１２は、ＡＴＭセルタイムごとに１ステップずつ、時計回り方向に回転する。静止キュー２０が、タイムホイール１２の上の位置０に取付けられる。回転キュー１０がタイムホイール１２上の位置０に到達するごとに、そのエントリ１４が静止キュー２０に付加される。各セルタイムごとに１回、静止キュー２０内のＶＣエントリ１４が伝送のために取出され、近づいてくるキュー１０内に置かれることによってすぐに再スケジュールされる。
【００１７】
ＶＣエントリを近づくキュー内に位置づけるために使用されるステップが、２つの尺度によって計算される。すなわち、（１）チャネルに割当てられる帯域幅および（２）他のＶＣに対する影響である。
【００１８】
ＶＣに割当てられる帯域幅は、たとえばｍセルタイムにおけるｉ個のセルとして２つのパラメータｉおよびｍにより定義される。したがって、ＶＣに割当てられる帯域幅は、ＶＣを定義するパラメータであるｉ／ｍで乗じた全物理チャネルの帯域幅に等しい。理想的には、仮想チャネルからのセルは物理チャネル内に均一に拡散されねばならず、セルはｍ／ｉセルタイムごとに放出されねばならない。したがって、もしｍ／ｉが整数であれば、このステップは単にｍ／ｉとなるであろう。しかし、もしｍ／ｉが整数でなければ、図６に示すように、その整数部分は初期ステップにおいてとられ、その端数部分が累算器レジスタ２２に付加される。図６においては、タイムホイール１２は、回転キュー１０により形成される円筒状の形で図示される。各回転キューは、ＶＣエントリ１４のキューのヘッドおよびテールを指し示すヘッドポインタ２５およびテールポインタ２７を含む。各ＶＣエントリ１４は、ｍ／ｉに等しい実数であるステップ２１と、累算器レジスタ２２と、回転キュー１０内の次のＶＣエントリ１４へのポインタ２９とを含む。累算器レジスタ２２がオーバーフローするとき、ステップサイズが増やされる。このステップ生成を表１に、より正式に示すが、Ａは累算器レジスタ２２内に記憶される値であり、Ｓはステップ２１に記憶される値すなわちｍ／ｉである。
【００１９】
【表１】
0003609255.tif 000002
【００２０】
静止キュー２０内に２つ以上のＶＣエントリ１４が存在するときは、各セルタイムごとに１つのＶＣがサービスされる。したがって、ステップサイズの計算においては、各ＶＣエントリが静止キュー内で待機していた時間を考慮せねばならない。これは図６に示すように、ＶＣエントリ１４にタイムスタンプ２３を付加することによって行なわれる。ＶＣがサービスされるとき、そのタイムスタンプは現在時間と比較され、その差がステップサイズから減算される。もしその差がステップサイズよりも大きいかまたはステップサイズに等しければ、図５に図示するようにＶＣエントリ１４は元の静止キュー２０に置かれ、そうでなければ、図４に図示するようにそのステップサイズにより、近づいてくる回転キュー１０に位置づけられる。
【００２１】
このプロセスは表２に、より正式に示す。
【００２２】
【表２】
0003609255.tif 000003
【００２３】
図４１は、表２のプロセスをさらに説明するフローチャートである。ステップ６０において、静止キューにスケジュールされるＶＣエントリがあるか否かが判断される。もしあれば、これらのＶＣエントリの第１のものがステップ６２において伝送される。次にステップ６４において、その間にＶＣエントリが再スケジュールされるべき間隔が生成される。ステップ６６において、ＶＣエントリが再スケジュールされる。最後に、ステップ６８においてキューが回転させられプロセスが繰返される。
【００２４】
次に連続した時点におけるＶＣの帯域幅の割当のグラフを示す図７を参照する。物理チャネルが過剰に申し込まれるため、すなわち、全ＶＣの帯域幅の合計が物理チャネルの帯域幅を超えるので、最も高い帯域幅２４のＶＣのエントリは絶えず静止キューに戻され、その帯域幅を効率的に減じる。次にこのプロセスが２番目に高い帯域幅２６を有するＶＣに対して繰返される。もし過剰な申込みが継続すれば、最終的にすべてのＶＣが同一の有効帯域幅を共有することになるだろう。
【００２５】
図８から図１１は、異なったＶＣ構成に対するこの発明の機能の例を示す。
図８は、それぞれ３および１に等しいパラメータｍおよびｉを備えるタイムホイール１２上の単一のＶＣエントリ１４という単純な場合を図示する。タイム＝０において、ＶＣエントリ１４は静止キュー２０から１つ位置が離れた回転キュー１０内にある。タイム＝１において、回転キュー１０は静止キュー２０に到達し、その内容が静止キュー２０に転送され、ＶＣエントリ１４は伝送ライン３０上で伝送され、静止キューから３つ位置が離れた回転キュー１０へと再スケジュールされる。タイム＝２において、タイムホイール１２が回転し、ＶＣエントリ１４がその上に位置づけられる回転キュー１０を静止キュー２０から２つ位置が離れたところにもっていく。
【００２６】
図９は、それぞれ３および２に等しいパラメータｍおよびｉを備える、タイムホイール１２上の単一のＶＣエントリ１４を図示する。タイム＝０において、ＶＣエントリ１４は、静止キュー２０から１つ位置が離れた回転キュー１０内にある。タイム＝１において、回転キュー１０は静止キュー２０に到達し、その内容が静止キュー２０へ転送され、ＶＣエントリ１４が伝送ライン３０上で伝送され、静止キュー２０から１つ位置が離れた回転キュー１０へと再スケジュールされる。ｍ／ｉ＝３／２に対するステップは１．５であろうから、０．５が累算器レジスタ２２内に記憶される。タイム＝２において、回転キュー１０は静止キュー２０に到達し、その内容が静止キュー２０へと転送され、ＶＣエントリ１４が伝送ライン３０上で伝送され、静止キュー２０から２つ位置が離れた回転キュー１０へと再スケジュールされ、累算器レジスタ２２内に記憶される０．５がステップｍ／ｉ＝１．５に加算される。
【００２７】
図１０は、それぞれ２および１ならびに３および２に等しいパラメータｍおよびｉを備える、２つのＶＣエントリを備えるより複雑な例を示す。タイム＝０において、静止キュー２０上にあるｍ／ｉ項＝３／２のＶＣエントリ１４が伝送ライン３０上で伝送され、静止キュー２０から１つ位置が離れた回転キュー１０へと再スケジュールされる。ｍ／ｉ＝３／２に対するステップは１．５であろうから、累算器レジスタ２２内に０．５が記憶される。タイム＝１において、回転キュー１０は静止キュー２０に到達し、その内容が静止キュー２０へ転送される。静止キュー２０上のｍ／ｉ項＝２／１のＶＣエントリ１４は伝送ライン３０上で伝送され、タイムスタンプ２３がステップｍ／ｉ＝２に等しいため、静止キュー２０の末尾に再スケジュールされる。タイム＝２において、ｍ／ｉ項＝３／２のＶＣエントリ１４は伝送ライン３０上で伝送され、現在時間とタイムスタンプ２３との間の差は、累算器レジスタ２２へと記憶された値０．５をｍ／ｉ＝１．５に加算して計算されたステップサイズよりも大きいので、静止キュー２０の末尾へと再スケジュールされる。タイム＝３において、静止キュー２０上のｍ／ｉ項＝２／１のＶＣエントリ１４は伝送ライン３０上で伝送され、現在時間とタイムスタンプ２３との間の差がステップサイズｍ／ｉ＝２に等しいので、静止キュー２０の末尾に再スケジュールされる。
【００２８】
図１１は、それぞれ３および２ならびに４および３に等しいパラメータｍおよびｉの２つのＶＣエントリ１４を備えるより複雑な例を示す。タイム＝０において、静止キュー２０上のｍ／ｉ＝４／３のＶＣエントリ１４は伝送ライン３０上で伝送され、静止キュー２０から１つ位置が離れた回転キュー１０へと再スケジュールされる。ｍ／ｉ＝４／３に対するステップは１．３４であろうから、０．３４が累算器レジスタ２２内に記憶される。タイム＝１において、回転キュー１０は静止キュー２０に到達し、その内容が静止キュー２０へと転送される。静止キュー２０上のｍ／ｉ＝３／２のＶＣエントリ１４は伝送ライン３０上で伝送され、静止キュー２０から１つ位置が離れた回転キュー１０へと再スケジュールされる。ｍ／ｉ＝３／２に対するステップは１．５であろうから、０．５が累算器レジスタ２２内に記憶される。タイム＝２において、ｍ／ｉ＝４／３のＶＣエントリ１４は伝送ライン３０上で伝送され、現在時間とタイムスタンプ２３との差が、累算器レジスタ２２に記憶された値０．３４をｍ／ｉ＝１．３４に加算して計算されたステップサイズに等しいので、静止キュー２０の末尾へと再スケジュールされる。タイム＝３において、静止キュー２０上のｍ／ｉ＝３／２のＶＣエントリ１４は伝送ライン３０上で伝送され、現在時間とタイムスタンプ２３との差がステップサイズ２に等しいので、静止キュー２０の末尾に再スケジュールされる。タイム＝４において、ｍ／ｉ項＝４／３のＶＣエントリ１４は伝送ライン３０上で伝送され、現在時間とタイムスタンプ２３との差が、累算器レジスタ２２へ記憶された値０．６８をｍ／ｉ＝１．３４に加算して計算されたステップサイズよりも大きいので、静止キュー２０の末尾へと再スケジュールされる。タイム＝５において、静止キュー２０上のｍ／ｉ項＝１．５のＶＣエントリ１４は伝送ライン３０へと伝送され、現在時間とタイムスタンプ２３との間の差がステップサイズ２よりも大きいので、静止キュー２０の末尾へと再スケジュールされる。
【００２９】
図１２−図１９は、ｍ＝３およびｉ＝２での単一のスケジューラの動作をステップごとに絵的に示すものである。タイム＝０（図１２）において、単一のＶＣエントリ１４はタイムホイール３５上の位置３２において回転キュー３１へ入れられ、一方、静止キュー３３は空であり、伝送ライン３０上にはエントリは存在しない。タイム＝１（図１３）においては、ＶＣエントリ１４が静止キュー３３に動かされ、伝送ライン３０上で伝送され、そしてタイムホイール３５上の位置３２で回転キュー３１へと再スケジュールされる。タイム＝２（図１４）において、ＶＣエントリ１４は再び静止キュー３３へ動かされ、伝送されそして累積レジスタ２２がオーバフローしてしまっているためタイムホイール３５上の位置３２ではなく位置３４の回転キュー３１へと再スケジュールされる。タイム＝３（図１５）において、キューがタイム＝０における状態と同じ状態にあり、タイム０、１および２でのステップと同一のステップがそれぞれタイム３、４および５において繰返されることがわかる。したがって、タイム＝７（図１９）における伝送ライン３０は、予想されるように、３セルタイムごとに２つのＶＣエントリが伝送されるパターンを示す。
【００３０】
図２０から図３５は、それぞれ３および２ならびに９および２に等しいｍおよびｉ項の２つのＶＣエントリ１４を備える単一のスケジューラの動作をステップごとに絵的に示したものである。タイム＝０（図２０）において、２つのＶＣエントリ３６および３８が、タイムホイール３５上の位置３２の回転キュー３１に入れられ、一方、静止キュー３３は空であり伝送ライン３０上にはエントリは存在しない。タイム＝１（図２１）において、ＶＣエントリ３６は静止キュー３３へ動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。タイム＝２（図２２）において、ＶＣエントリ３６は静止キュー３３へ動かされ、ＶＣエントリ３８は伝送ライン３０上で伝送されタイムホイール３５上の位置４２の回転キュー３１へと再スケジュールされる。タイム＝３（図２３）において、ＶＣエントリ３６は伝送ライン３０上で伝送され、タイムホイール３５上の位置３２において回転キュー３１へと再スケジュールされる。タイム＝４（図２４）において、ＶＣエントリ３６は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。タイム＝５（図２５）において、ＶＣエントリ３６は静止キュー３３へと動かされ、ＶＣエントリ３８は静止キュー３３へと動かされ、伝送ライン３０上で伝送されタイムホイール３５上の位置４４の回転キュー３１へと再スケジュールされる。タイム＝６（図２６）において、ＶＣエントリ３６は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。タイム＝７（図２７）において、ＶＣエントリ３６は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。タイム＝８（図２８）において、ＶＣエントリ３６は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３４の回転キュー３１へと再スケジュールされる。タイム＝９（図２９）において、ＶＣエントリ３８および３６はともにタイムホイール３５上の位置３２の回転キュー３１へと動かされる。タイム＝１０（図３０）において、ＶＣエントリ３６は静止キュー３３へ動かされ、ＶＣエントリ３８は静止キュー３３へと動かされ、伝送ライン３０上で伝送されタイムホイール３５上の位置４０の回転キュー３１へと再スケジュールされる。タイム＝１１（図３１）において、ＶＣエントリ３６は伝送ライン３０上で伝送され、これが最後にサービスされてから経過した時間がそのステップに等しいため、静止キュー３３へと再スケジュールされる。タイム＝１２（図３２）において、ＶＣエントリ３６は伝送ライン３０上で伝送され、タイムホイール３５上の位置３４の回転キュー３１へと再スケジュールされる。タイム＝１３（図３３）において、ＶＣエントリ３６は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。タイム＝１４（図３４）において、ＶＣエントリ３６は静止キュー３３へと動かされ、ＶＣエントリ３８は静止キュー３３へと動かされ、伝送ライン３０上で伝送され、タイムホイール３５上の位置４４の回転キュー３１へと再スケジュールされる。タイム＝１５（図３５）において、ＶＣエントリ３６は伝送ライン３０上で伝送され、タイムホイール３５上の位置３２の回転キュー３１へと再スケジュールされる。
【００３１】
最後に、特定の調停／優先順位機構を実現するため多数のスケジューラを並行して使用してもよい。たとえば、ある仮想チャネルに保証される最低帯域幅を割当てるが、同時に、このＶＣが取ることができる最大帯域幅をいかなる特定の時点においても限定したいと所望するかも知れない。図３６は、保証される最低帯域幅５０と可能な最大帯域幅５２との関係を示す。この機能は並行して作業する２つのスケジューラにより達成できる。図３７は、図３の好ましい実施例による２つのスケジューラを図示する。すなわち、保証される最低帯域幅５０に等しい属性ｍおよびｉを備えるスケジューラ５４と、可能な最大帯域幅５２と保証される最低帯域幅５０との差に等しいｍ項およびｉ項を備えるスケジューラ５６である。スケジューラ５６にスケジューラ５８より高い優先順位を与えることによって、所望の帯域幅割当が達成される。
【００３２】
この機構のもう１つの説明が、図３８の「二重漏れバケツ」により与えられる。バケツ７０は液体７２で満たされる。蛇口７４および７６が、異なった速度での液体７２の漏斗７８への排出を可能にする。もし、蛇口７４が保証される最低帯域幅５０に対応する速度に設定され、蛇口７６が可能な最大帯域幅５２と保証される最低帯域幅５０との差に対応する速度に設定されるならば、液体７２は、図３７のスケジューラ５６および５８によりＶＣエントリがプロセシングされる態様と類比的な態様で漏斗７８へと排出されるであろう。
【００３３】
さらに、多数のスケジューラを使用して、いくつかのより低い帯域幅のチャネルが単一のより高い帯域幅のチャネルへと多重化されてもよい。図３９においては、いくつかの低帯域幅チャネル間で帯域幅を分割するためスケジューラ８０が使用され、各チャネルのＶＣに適切な帯域幅を割当てるためにスケジューラ８２が使用される。
【００３４】
さらに、単一の仮想パス（ＶＰ）上でいくつかのＶＣが搬送されてよい。図４０において、いくつかのＶＰへ適切な帯域幅を提供するためスケジューラ８４が使用され、一方、ＶＰの１つの中のＶＣへ適切な帯域幅を提供するためスケジューラ８６が使用される。
【００３５】
この発明の一実施例によるＡＴＭセルスケジューリングのための集積回路のブロック図が図４２に示される。ＡＴＭセルスケジューラ９０は、タイムホイールスケジューラ９２および重み付ラウンドロビン／厳密優先順位スケジューラ９４を含む。重み付ラウンドロビンスケジューラは、同時係属中の共通の譲受人に譲渡されたアレクサンダー・ヨッフェ（Alexander Joffe ）による「ＡＴＭセルスケジューリングのための重み付けされた公平なキューイングのための方法（METHOD FOR WEIGHTED FAIR QUEUEING FOR ATM CELL SCHEDULING ）」と題された、代理人書類番号Ｎｏ．Ｍ−４０７９ ＵＳの米国特許出願連続番号第０８／８４３，１０８号に記載されており、これはここにその全体として引用により援用される。
【００３６】
ＡＴＭセルスケジューラ９０はさらに、サブポートスケジューリングインターフェイスモジュール９５、キュー速度記述子メモリインターフェイスモジュール９６、ＯＶＣ記述子メモリインターフェイス９７およびキューイングコントローラインターフェイス９８を含む。ＡＴＭセルスケジューラ９０およびそれと対応するピンによって受送信される信号のリストを、付録Ａ（表３から表７）に提供する。
【００３７】
ＡＴＭセルスケジューラ９０は、ＯＶＣ記述子メモリインターフェイス９７を通してＶＣごと回路１００とインターフェイスする。ＶＣごと回路１００はＶＣセルを表わすデータ構造に対する記憶装置を含む。予め定められたプロトコルによりＶＣごと回路１００と信号を交換することによって、ＡＴＭセルスケジューラ９０は、図４３のＡＴＭスイッチにおいてキューに入れられたＡＴＭセルのスケジューリングを制御する。図４３は、この発明によるＡＴＭスイッチの構造を図示する。スイッチコントローラ１２０はスイッチインターフェイス１１０を通してＶＣごと回路１００とインターフェイスする。ＶＣごと回路１００はスケジューラ９０と信号を交換し、伝送のためのＡＴＭセルのスケジューリングを行なう。図４３のＡＴＭスイッチは、アレクサンダー・ヨッフェ、アリ・バーガー（Ａｒｉ  Ｂｉｒｇｅｒ）およびプラバット・ミシュラ（Ｐｒａｖａｔ  Ｍｉｓｈｒａ  ）による「ＡＴＭスイッチにおけるセルキューイング（ＣＥＬＬ  ＱＵＥＵＩＮＧ  ＩＮ  ＡＴＭ  ＳＷＩＴＣＨＥＳ）」と題された代理人書類番号Ｎｏ．Ｍ−４１７７  ＵＳの、米国特許出願連続番号第０８／７０６，１０４号に記載されており、これはここにその全体として引用により援用される。
【００３８】
【表３】
0003609255.tif 000004
【００３９】
【表４】
0003609255.tif 000005
【００４０】
【表５】
0003609255.tif 000006
【００４１】
【表６】
0003609255.tif 000007
【００４２】
【表７】
0003609255.tif 000008
【図面の簡単な説明】
【図１】簡単な先行技術のタイムホイールセルスケジューラの斜視図である。
【図２】この発明の一実施例による自動再スケジューリング機構を用いるタイムホイールセルスケジューラの斜視図である。
【図３】この発明の他実施例の斜視図である。
【図４】図３の静止キュー構成要素の部分図である。
【図５】図３の静止キュー構成要素の部分図である。
【図６】この発明の一実施例のブロック図である。
【図７】仮想チャネルの帯域幅の過剰申込の影響を表わす２次元グラフである。
【図８】この発明の動作における連続的な時点での図３の好ましい実施例の斜視図に示す、この発明の動作の例の図である。
【図９】この発明の動作における連続的な時点での図３の好ましい実施例の斜視図に示す、この発明の動作の例の図である。
【図１０】この発明の動作における連続的な時点での図３の好ましい実施例の斜視図に示す、この発明の動作の例の図である。
【図１１】この発明の動作における連続的な時点での図３の好ましい実施例の斜視図に示す、この発明の動作の例の図である。
【図１２】この発明の動作を絵的に表わした図である。
【図１３】この発明の動作を絵的に表わした図である。
【図１４】この発明の動作を絵的に表わした図である。
【図１５】この発明の動作を絵的に表わした図である。
【図１６】この発明の動作を絵的に表わした図である。
【図１７】この発明の動作を絵的に表わした図である。
【図１８】この発明の動作を絵的に表わした図である。
【図１９】この発明の動作を絵的に表わした図である。
【図２０】この発明の動作を絵的に表わした図である。
【図２１】この発明の動作を絵的に表わした図である。
【図２２】この発明の動作を絵的に表わした図である。
【図２３】この発明の動作を絵的に表わした図である。
【図２４】この発明の動作を絵的に表わした図である。
【図２５】この発明の動作を絵的に表わした図である。
【図２６】この発明の動作を絵的に表わした図である。
【図２７】この発明の動作を絵的に表わした図である。
【図２８】この発明の動作を絵的に表わした図である。
【図２９】この発明の動作を絵的に表わした図である。
【図３０】この発明の動作を絵的に表わした図である。
【図３１】この発明の動作を絵的に表わした図である。
【図３２】この発明の動作を絵的に表わした図である。
【図３３】この発明の動作を絵的に表わした図である。
【図３４】この発明の動作を絵的に表わした図である。
【図３５】この発明の動作を絵的に表わした図である。
【図３６】この発明の多スケジューラ実施例において保証される最低帯域幅と可能な最大帯域幅との関係を表わす２次元グラフである。
【図３７】この発明の多スケジューラ実施例の斜視図である。
【図３８】「二重漏れバケツ」を絵的に示す図である。
【図３９】この発明の多スケジューラ実施例を絵的に表わす図である。
【図４０】この発明の多スケジューラ実施例を絵的に表わす図である。
【図４１】ＶＣエントリのプロセシングのフローチャートである。
【図４２】この発明の一実施例による、ＡＴＭセルのスケジューリングのための集積回路のブロック図である。
【図４３】この発明の一実施例による、ＡＴＭスイッチのブロック図である。
【符号の説明】
１０  キュー
１２  タイムホイール
１４  ＶＣエントリ
２０  静止キュー
【図１】
0003609255.tif 000009
【図２】
0003609255.tif 000010
【図３】
0003609255.tif 000011
【図４】
0003609255.tif 000012
【図５】
0003609255.tif 000013
【図６】
0003609255.tif 000014
【図７】
0003609255.tif 000015
【図８】
0003609255.tif 000016
【図９】
0003609255.tif 000017
【図１０】
0003609255.tif 000018
【図１１】
0003609255.tif 000019
【図１２】
0003609255.tif 000020
【図１３】
0003609255.tif 000021
【図１４】
0003609255.tif 000022
【図１５】
0003609255.tif 000023
【図１６】
0003609255.tif 000024
【図１７】
0003609255.tif 000025
【図１８】
0003609255.tif 000026
【図１９】
0003609255.tif 000027
【図２０】
0003609255.tif 000028
【図２１】
0003609255.tif 000029
【図２２】
0003609255.tif 000030
【図２３】
0003609255.tif 000031
【図２４】
0003609255.tif 000032
【図２５】
0003609255.tif 000033
【図２６】
0003609255.tif 000034
【図２７】
0003609255.tif 000035
【図２８】
0003609255.tif 000036
【図２９】
0003609255.tif 000037
【図３０】
0003609255.tif 000038
【図３１】
0003609255.tif 000039
【図３２】
0003609255.tif 000040
【図３３】
0003609255.tif 000041
【図３４】
0003609255.tif 000042
【図３５】
0003609255.tif 000043
【図３６】
0003609255.tif 000044
【図３７】
0003609255.tif 000045
【図３８】
0003609255.tif 000046
【図３９】
0003609255.tif 000047
【図４０】
0003609255.tif 000048
【図４１】
0003609255.tif 000049
【図４２】
0003609255.tif 000050
【図４３】
0003609255.tif 000051