JPH11340983A - スケジュ―リング回路及び方法 - Google Patents

Abstract

(57)【要約】 【課題】 スケジューリング回路に関し、特にＡＴＭネ
ットワークユニット内で効率のよいセル転送をスケジュ
ール可能なスケジューリング回路を提供する。 【解決手段】 マスタカレンダー１は所定のマスタカレ
ンダースケジューリング範囲（ＳＲ）内で発生するイベ
ントにそれぞれ対応したエントリを保持する。スレーブ
カレンダー１２は前記スケジューリング範囲外で発生す
るイベントにそれぞれ対応したエントリを保持する。イ
ベントがスケジュールされる時、カレンダ制御回路２４
は現時間とそのイベントの所望のスケジューリング時間
との間隔が前記スケジューリング範囲を超える場合に、
前記スレーブカレンダー１２にそれに対応したエントリ
を作成する。カレンダー制御回路２４は、さらに前記ス
レーブカレンダー１２のエントリをモニタし、前記エン
トリに対応するイベントが前記スケジューリング範囲内
にあるエントリをマスタカレンダ−１に転送する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はスケジューリング回
路及び使用方法に関し、例えば、非同期転送モード（Ａ
ＴＭ）通信ネトワークにおけるセル伝送動作のスケジュ
ーリングに関するものである。

【０００２】

【従来の技術】ＡＴＭ通信ネットワークにおいては、ユ
ーザデータや制御情報を異なるネットワークユニット間
で伝送するために、複数の“仮想チャネル（ＶＣ）”が
使われる。そのようなユーザデータ及び制御情報はＡＴ
Ｍセル形式で転送され、各セルはセル制御及びアドレス
情報を含むヘッダ部と、ユーザデータや他の制御情報を
含むペイロード部とからなる。

【０００３】所定のネットワークユニットは、それを１
つ又はより多くのネットワークユニットに接続する複数
の仮想チャネルを有する。従って、各ネットワークユニ
ットにはトラフィックマネジャが必要となり、それが関
連する異なった仮想チャネルへ与えられるセルの生成時
間を管理する。

【０００４】トラフィックマネジャのタスクは、異なる
形式のトラッフィクを伝送するのに異なる仮想チャネル
が使用され、それには異なる優先度を有するトラフィッ
ク形式が含まれるため複雑である。例えば、次のトラフ
ィック形式がＡＴＭネットワークにおいて使用される。

【０００５】i ）固定ビット速度（ＣＢＲ）トラッフィ
ク。これは、典型的には、ビデオ信号のような高優先度
データに使用される。 ii）可変ビット速度（ＶＢＲ）トラッフィック。この形
式のトラフィックもまた、比較的高い優先度を有する
（しかしながら、ＣＢＲトラッフィクよりは低い）。幾
つかの遅延許容度が利用可能なところ、例えば圧縮ビデ
オ（モーション・ピクチャ・エキスパート・グループ
ＭＰＥＧ２）トラフィックや音声トラフィック、で使わ
れる。

【０００６】iii ）利用可能ビット速度（ＡＢＲ）トラ
フィック。ＡＢＲトラフィックを転送するため使用する
仮想チャネルは、そのチャネルユーザとネットワークオ
ペレータの間で合意したトラフィックパラメータを有す
る。合意したパラメータにより課せられる制限の範囲内
において、ＡＢＲチャネルはネットワークの空き容量を
利用するためその伝送速度を可変とすることが許され
る。ＡＢＲトラフィックは低い優先度を有する（ＣＢＲ
及びＶＢＲトラフィックよりも低い）。ＡＢＲチャネル
は、例えばファイルやデータの伝送に使用される。 iv）未定義ビット速度（ＵＢＲ）トラフィック。例え
ば、Ｅメールや幾つかのファイル及びデータ伝送等で使
用される。

【０００７】図１は、ＡＴＭネットワークユニットから
のセルの伝送時間を管理するために先に提案された“カ
レンダー（calendar) ”スケジューリング方法を説明す
るためのものである。図１において、カレンダー１は各
々一連のタイムスロットに対応する記憶ロケーション２
のリストから成る。各タイムスロットの所要時間は、Ａ
ＴＭネットワークの最大要求データ速度で１つのＡＴＭ
セルを転送するのに要する時間に等しい。

【０００８】各記憶ロケーション２は１つ以上のエント
リを記憶することが可能であり、各エントリは特定の仮
想チャネルがその記憶ロケーションの対応するタイムス
ロットのトラフィックマネジャによって提供されるべき
ことを指示する。例えば、カレンダー１の記憶ロケーシ
ョン２_A は、仮想チャネルＶＣ_W が記憶ロケーション２
_A と対応するタイムスロットのトラフィックマネジャに
よって提供されるべきことを示す１つのエントリを有す
る。

【０００９】１つ以上のＶＣを同じ記憶ロケーションに
入力(enter) することが可能である。例えば、カレンダ
ー１の記憶ロケーション２_B はその中に入力された３つ
の仮想チャネルＶＣ_x 、ＶＣ_y 及びＶＣ_z を有し、これ
らの各チャネルが記憶ロケーション２_B に対応するタイ
ムスロットで提供されるべきことを指示する。記憶ロケ
ーション２_B の３つのエントリはリンクリスト形式で作
成され、タイムスロット当たり大容量のメモリをリザー
ブすることを回避し、特定の記憶ロケーションに入力可
能なＶＣ最大可能数を収容する。

【００１０】トラフィックマネジャは、カレンダー１を
処理するのに２つのポインタ３及び４を使用する。第１
のポインタ３はカレントタイムポインタ（Ｔ）であり、
実時間を表す。カレントタイムポインタＴは、各セル間
隔の後、常にインクリメントされる。第２のポインタ４
はアクティビティポインタ（Ａ）であり、Ｔポインタ３
を追い越すことなく、それに常に追いつこうとする。

【００１１】カレンダー１の各記憶ロケーションでは、
ＶＣが存在しなければＡポインタが次の記憶ロケーショ
ンへ単にインクリメントされる。この場合、Ａポインタ
はＴポインタにキャチアップしようとする。一方、もし
一つ以上のＶＣがＡポインタが示す記憶ロケーションに
存在する場合、全てのＶＣが処理されるまでこのポイン
タはインクリメントされない（この場合、全てのＶＣを
処理するのに必要な時間中、Ｔポインタは一回以上イン
クリメントされ、その結果ＡポインタはＴポインタより
かなり遅れることになる）。

【００１２】トラフィックマネジャはカレンダー内のエ
ントリに次のサービスを行う。第１に、エントリにおい
て指定されたＶＣのセルが転送される。第２に、もし必
要なら、このチャネルの新たなインターセル (inter-ce
ll) 間隔が計算される（ＣＢＲチャネルは常に同じイン
ターセル間隔を有するが、ＶＢＲ、ＡＢＲ及びＵＢＲに
ついてはセル間隔はチャネルの使用によって変化する。
そのため、時々計算し直す必要がある）。指定されたＶ
Ｃの次のセル伝送は、カレンダー１の異なる記憶ロケー
ション２内のＶＣに新たなエントリを作成することによ
って再スケジューリングされる。

【００１３】例えば、もしＶＣ_x が、関連するＡＴＭネ
ットワークユニットからの利用可能な伝送容量の３３％
を有するならば、ロケーション２_B でサービスされる時
に、カレントタイムポインタＴから３セルタイムスロッ
ト前方の記憶ロケーション２ _C で再スケージュリングさ
れることになる。

【００１４】ところで、本例において、現時間で記憶ロ
ケーション２_B を示しているＡポインタはＴポインタの
５つ後方の記憶ロケーションであることが分かる。２つ
のポインタ間の記憶ロケーションに空きがあるため、Ａ
ポインタはＴポインタに対して追いつくことも可能であ
る。しかしながら、Ａ及びＴポインタ間でサービスを行
うには３つの仮想チャネルＶＣ_y 、ＶＣ_z 、及びＶＣ_w
が存在する。このことは、実際にＶＣ_x が次の処理に再
び遭遇する前に３セル期間以上あることを意味する。

【００１５】

【発明が解決しようとする課題】図１に示したカレンダ
ースケージューリング方法の１つの問題は、大きく異な
る伝送速度を有するチャネル同士が協働可能なことを要
求される点である。最大データ速度１５５ＭｂｐｓのＡ
ＴＭネットワークにおける各セル期間は２．７２６μｓ
である。しかしながら、ある形式のＶＣは非常に遅いセ
ル速度を有する。例えば、ＡＢＲチャネルは制御のため
にリソース管理（ＲＭ）セルを使用するが、そのような
ＲＭセルのセル速度は１秒当たり１０セル程度である。
このことは、図１のカレンダー１が３５０００エントリ
（すなわち、３５０００×２．７２６μｓ＝０．１ｓ）
を備えることを要求する。これでは、カレンダー１が各
タイムスロットのための記憶ロケーション２を必要とす
ることから、非実用的である。

【００１６】この問題に対する１つの解決策は、先に提
案されており、各ＶＣにカウンタを持たせることであ
る。このカウンタはある正の値に初期設定され、トラフ
ィックマネジャによる各ＶＣエントリの検査時、カレン
ダーに関する各パス上でデクリメントされる。ＶＣはそ
のカウンタがゼロになった時だけサービスされる（すな
わち、１つのセルが転送され、次のセル転送がスケジュ
ールされる）。このように、ＶＣ当たり６ビットのカウ
ンタを使用して、カレンダーのサイズを（例えば）１０
００記憶ロケーションに低減可能である。セル速度が３
７０セル／秒（１５５Ｍｂｐｓで２. ７マイクロ秒のイ
ンターセル期間）より大きなＶＣは、常にカレンダーで
“ヒット (hit)”する。すなわち、各ＶＣのカウンタは
永久にゼロである。

【００１７】上述した解決策は、部分的にはカレンダー
サイズを低減するのに有効である。しかしながら、たと
え特定のＶＣはカレンダーを通した各パス (pass) 上で
遭遇しても、各遭遇に関してサービスされることを必ず
しも意味しない点でトラフィックマネジャのリソースを
浪費する。従って、しばしばエントリはカレンダーのこ
の特定パス上でのサービスを要求しないトラフィックマ
ネジャによって読み出される。

【００１８】別の欠点は、フォワードポインタと同様
に、カレンダーの各エントリに必要な（リンクリストの
先のエントリへの）バックワードポインタを備えること
と関連する。なぜなら、各ＶＣはそれ自身のカウンタを
持ち、リンクリストは初めから最後へと処理され、各カ
ウンタがゼロのＶＣはもはや必要とされないからであ
る。カウンタが非ゼロであるリンクリストの残りのＶＣ
は、次のカレンダーパスのリンクリストのため保持して
おく必要がある。カウンタがゼロになったＶＣを他のＶ
Ｃ（非ゼロカウンタ）を保持しながらリンクリストから
削除可能とするには、削除されるＶＣのバックワードポ
インタを使用してリンクリストにおける直前のＶＣを識
別し、それによってその直前のＶＣのフォワードポイン
タが、削除されるＶＣのフォワードポインタと等しくな
るようにすることが必要である。その結果、削除される
ＶＣに関するリンクリストは再構築される。ＶＣ毎のバ
ックワードポインタを提供する必要から、リンクリスト
の処理が複雑となり、トラフィックマネジャがたくわえ
なければならない情報量が大きく増大する。

【００１９】そこで本発明の目的は、上記種々の問題に
鑑み、特別な処理パワー及び／又は記憶容量を必要とせ
ず、異種速度のＶＣを効果的に制御可能な、改良したト
ラフィックマネジャ及び改良したトラフィック管理方法
を提供することにある。

【００２０】

【課題を解決するための手段】本発明の第１の態様によ
れば、所定のイベントをスケジュールするためのスケジ
ューリング回路は、所定のマスタカレンダースケジュー
リング範囲内で発生するイベントにそれぞれ対応したエ
ントリを保持するマスタカレンダー手段と、このスケジ
ューリング範囲外で発生するイベントにそれぞれ対応し
たエントリを保持するスレーブカレンダー手段と、イベ
ントがスケジュールされる時、現時間とそのイベントの
所望のスケジューリング時間との間隔がスケジューリン
グ範囲を超える場合に、スレーブカレンダー手段にそれ
に対応したエントリを作成するカレンダ制御手段とを有
し、カレンダー制御手段は、さらにスレーブカレンダー
手段のエントリをモニタし、エントリに対応するイベン
トがスケジューリング範囲内にあるエントリをマスタカ
レンダ−手段に転送することを特徴とするスケジューリ
ング回路が提供される。

【００２１】また本発明の第２の態様によれば、所定の
イベントをスケジュールするスケジューリング方法は、
イベントがスケジュールされる時、現時間とそのイベン
トの所望のスケジューリング時間との間隔が所定のマス
タカレンダースケジューリング範囲内の場合に、それに
対応したエントリがマスタカレンダー手段に作成される
こと、もしその間隔が所定のマスタカレンダースケジュ
ーリング範囲外の場合にはイベントに対応するエントリ
がマスタカレンダー手段とは独立にスレーブカレンダー
手段に作成されること、スレーブカレンダー手段におけ
るエントリはモニタされること、その対応するイベント
がマスタカレンダースケジューリング範囲内となったエ
ントリはマスタカレンダー手段へ転送されること、から
成るスケジューリング方法が提供される。

【００２２】

【発明の実施の形態】図２は、本発明を実施したスケジ
ューリング回路部分を示したものであり、その原理を説
明するためのものである。図１を参照して述べたこれま
でのスケジューリング回路に対し、図２のスケジューリ
ング回路は、それぞれ一連のタイムスロットに対応した
複数の記憶ロケーション２から成るマスタカレンダー１
を有する。各記憶ロケーション２は、１つ以上のエント
リを持つことが可能で、各エントリはその記憶ロケーシ
ョンに対応したタイムスロットでサービスされる仮想チ
ャネル（ＶＣ）を規定する。図１の回路のように、マス
タカレンダー１は、各セル期間でインクリメントされる
カレントタイムポインタ（Ｔ）３と、現在サービスされ
ている記憶ロケーション２（又は、それとは別に、サー
ビスされる次の記憶ロケーション）を規定するカレント
アクティビティポインタ（Ａ）４とを有する。Ａポイン
タは、常時Ｔポインタに追いつこうとする。特定の記憶
ロケーションにエントリが無い時には追いつく機会が生
じるが、１つ以上のＶＣが記憶ロケーション２に入力さ
れるとＴポインタの後方に遅れる。

【００２３】図２に示すスケジューリング回路では、
“スレーブ”と呼ばれるカレンダー６が与えられ、この
点で図１のスケジューリング回路と異なる。このスレー
ブカレンダー６は、複数の記憶ロケーション７と、現在
サービス中のスレーブカレンダー６の記憶ロケーション
７の１つを示すスレーブポインタ（Ｓ）８とを有する。
マスタ及びスレーブカレンダー及び関連するＡ、Ｔ及び
Ｓポインタはカレンダー制御回路９によって制御され
る。

【００２４】図２のスケジューリング回路は、以下のよ
うに動作する。マスタカレンダー１の記憶ロケーション
２は、現在サービス中の記憶ロケーションを識別するた
め、Ａポインタ４を使いカレンダー制御回路９によって
順次サービスされる。従来と同様に、Ａポインタによっ
て指示される記憶ロケーションの各エントリがサービス
されると、第１にそのエントリで指定されるＶＣのセル
が転送される。第２に、既存の技術を使って、指定され
たＶＣの次のセルが転送されるべき時間（以降では、
“次のスケジュール時間”又はＮＳＴという）が計算さ
れる。そして、図１の回路とは異なる再スケジューリン
グ動作が実行される。この異なる再スケジューリング動
作において、カレンダー制御回路は指定のＶＣのＮＳＴ
を調べ、マスタカレンダーのスケジューリング範囲ＳＲ
内か否かを判断する。本明細書において以降で詳細に説
明するように、このスケジューリング範囲ＳＲは記憶ロ
ケーションの現在の数未満でマスタカレンダーの記憶ロ
ケーション２の数に比例し、Ｔポインタがその記憶ロケ
ーション数を縦断するのにかかる時間を表す。

【００２５】もし、ＮＳＴがマスタカレンダー１のスケ
ジューリング範囲ＳＲ内ならば、図１のスケジューリン
グ回路のように、指定されたＶＣのための新たなエント
リがマスタカレンダーの適当な１つの記憶ロケーション
に作成される。一方、もしＮＳＴがマスタカレンダー１
のスケジューリング範囲ＳＲ外ならば、指定されたＶＣ
はマスタカレンダー１に入力されない。その代わり、ス
レーブカレンダー６の記憶ロケーション７の１つに入力
され、その記憶ロケーションはまた指定されたＶＣのＮ
ＳＴを記憶するのに使われる。

【００２６】カレンダ制御回路９は、スレーブポインタ
Ｓを使ってスレーブカレンダー６の記憶ロケーション７
を連続的に巡回し、現在処理されている記憶ロケーショ
ンを識別する。次に、スレーブカレンダー記憶ロケーシ
ョン７が特定のＶＣに対応するアクティブ（又は“ビジ
ー”）エントリを含むことを検出すると、そのＶＣに記
憶したＮＳＴを調べる。ＮＳＴはマスタカレンダーのカ
レントタイムポインタＴと比較される。もし、ＮＳＴと
現時間（Ｔポインタ）の間の時間間隔がマスタカレンダ
ーのスケジューリング範囲ＳＲより小さい場合、スレー
ブカレンダー記憶ロケーション７で指定されるＶＣはマ
スタカレンダーへ転送される。すなわち、そのＶＣに対
応する新たなエントリがマスタカレンダー記憶ロケーシ
ョン２の適当な１つに作成される。

【００２７】もし、調べたスレーブカレンダー記憶ロケ
ーション７の記憶したＮＳＴと現時間との間の時間間隔
がマスタカレンダーのスケジューリング範囲ＳＲより大
きければ、スレーブカレンダーの記憶ロケーションは変
更されず、スレーブポインタＳのスレーブカレンダー記
憶ロケーションによる次のパス完了が保留される。な
お、スレーブカレンダーからマスタカレンダーへの不要
なＶＣ転送を確実に防止するためには、スレーブポイン
タＳがスレーブカレンダー６の１つのパスを完了するの
にかかる時間をマスタカレンダーのスケジューリング範
囲ＳＲより小さいか又は等しくする必要がある。

【００２８】図２のスケジューリング回路において、マ
スタカレンダーのサイズは図１のスケジューリング回路
のカレンダー１よりもかなり小さくできる。例えば、マ
スタカレンダー１のサイズは設定済みの全ＶＣ数（いか
なる所定時間においても、設定チャネルの全てがアクテ
ィブというわけではない）と単純に等しくすることが可
能である。例えば、３０のそのような設定チャネルが存
在する場合、マスタカレンダーのサイズは図１の回路の
カレンダー１と比べて顕著に減少できる。図１の回路の
カレンダー１では、さらにＶＣあたりカウンタを伴い、
典型的には１０００個の記憶ロケーションを有する。実
際、異なるアプリケーションには設定すべき異なる数の
ＶＣが必要である。例えば、いくつかのアプリケーショ
ンでは１０００、４０００又は６４０００個のＶＣが存
在し得る。スレーブカレンダー６については、いかなる
時でも存在する設定ＶＣと同数の多くの記憶ロケーショ
ン７が必要となる。無論、再スケジューリングにおいス
レーブカレンダーへ転送されることのない非常に高い伝
送速度のＶＣが存在する。この場合には、スレーブカレ
ンダーにおける記憶ロケーション７の数を全てのアクテ
ィブなＶＣの数以上にまで減少させることが可能であ
る。

【００２９】また、図２のスケジューリング回路は、先
に述べた各ＶＣにそれ自身のカウンタを持たせることに
関する欠点を解消するのに有効である。第１に、ＶＣが
マスタカレンダーに入力される時はいつも次にサービス
される必要があることから、マスタカレンダーの全ての
エントリで“ヒット”が保証される。第２に、マスタカ
レンダー１の同じ記憶ロケーション内に複数のエントリ
がリンクリストを使って作成される場合、各エントリに
図１のカウンタベースの手法で用いる種類のバックワー
ドポインタを与える必要がない。なぜなら、その特定の
マスタカレンダー記憶ロケーション２がサービスされる
時に各リンクリストは一回だけ使用されるからである。
サービスの後、そのリンクリストに属する各エントリは
マスタカレンダーの異なる記憶ロケーションか又はスレ
ーブカレンダー６の適当な記憶ロケーションのいずれか
に再スケジュールされる（より多くのデータが送信可能
なように与えられる）。削除されたエントリに関するリ
ンクリストは再構築の必要がない。このことは、リンク
リストの操作を非常に簡潔且つ高速にする。

【００３０】次に、本発明の第１の実施例について図３
〜９を参照して説明する。先ず図３を参照して、第１の
実施例のスケジューリング回路は、マスタカレンダー
１、各Ｔ、Ａ及びＳポインタ３、４及び８、そしてカレ
ンダー制御回路２４からなる。Ｔポインタ３は、２．７
２６μｓ（１５５Ｍｂｐｓの伝送速度での１セル期間に
相当）の細分化を伴う１０．２３秒（ＡＢＲチャネルの
許可セル速度（ＡＣＲ）減少時間要素（ＡＤＴＦ）タイ
ムアウト値に相当）を測るのに必要な２２ビットのディ
ジタル値である。

【００３１】なお、可能な形態として、２．８３１μｓ
の異なるセル期間を使用してもよい。このセル期間は以
下のように実現される。先ず、セル／秒で１５５．５２
Ｍｂｐｓ（各セルは各々８ビトの５３バイトを有する）
―これは先に示したように２．７２６μｓに相当する―
のビット速度を表すことによって最大要求データ速度が
計算される。そして、このセル速度をＳＴＳ３ｃフレー
ム（すなわち、全体で２７０バイトの内の２６０データ
バイト―各ＳＴＳフレームは２６０データバイトと１０
オーバヘッドバイトを含む）のデータに比例して表され
る要素と乗算する。従って、セル期間は以下の式で表さ
れる。 （８×５３）／（１５５．５２×１０⁶ ）×（２７０／
２６０）＝２．８３１μｓ

【００３２】Ａポインタ４は１６ビットのパラメータで
ある。従って、Ａポインタの範囲は、２¹⁶×２．７２６
μｓ＝０．１７８７ｓまで対応する。これは略１０セル
／秒の最低セル速度（ＲＭセル速度）を扱うのに十分で
ある。Ａポインタのサイズは、マスタカレンダーの動的
な範囲（１０２４（＝２¹⁰）ＶＣに対し１０ビットで十
分であるが、１６ビットによりＮＳＴ（タイムスタン
プ）が２¹⁶セル期間の範囲で可能となる）を決定する。

【００３３】本実施例において、記憶ロケーション１４
の一組１２はマスタカレンダー及びスレーブカレンダー
でエントリを作成するのに使用される。これらの記憶ロ
ケーション１４は、関連するＡＴＭネットワークユニッ
トの異なるＶＣにそれぞれ対応する。この理由から、記
憶ロケーション１４はこれ以降においてＶＣ毎のパラメ
ータブロック（ｐｅｒ−ＶＣパラメータブロック）とし
て述べる。

【００３４】図４を参照すると、ＶＣ毎のパラメータブ
ロック１４は３つの異なる形式に分割される。第１は、
マスタカレンダー１にエントリを作成するブロックを有
する。図１を参照して先に説明したように、マスタカレ
ンダー１の記憶ロケーション２は、その中に１つ以上の
エントリを持つことが可能で、その記憶ロケーションに
対応したタイムスロットでサービスされるＶＣの数に依
存する。従って、各マスタカレンダー記憶ロケーション
２は各々の開始及び終了ポインタを有する。開始ポイン
タは関連する記憶ロケーション２の最初のエントリを構
成するＶＣ毎のパラメータブロック１４を指示し、そし
て終了ポインタは関連する記憶ロケーション２に入力さ
れた最後のＶＣ毎のパラメータブロックを指示する。も
し、記憶ロケーション２に入力されたＶＣが１つだけの
場合には、開始及び終了ポインタは同じ値であり、両者
とも１つのＶＣに対応するＶＣ毎のパラメータブロック
を指し示す。

【００３５】１つより多くのＶＣが特定のマスタカレン
ダー記憶ロケーション２に入力された時には、ＶＣ毎の
パラメータブロックは全てのエントリのリンクリストを
構成するのに使われる。この目的のために、各ＶＣ毎の
パラメータブロックは“ＮＥＸＴ＿ＶＣ”フィールドを
有し、そこにはマスタカレンダー記憶ロケーション２に
入力される次のＶＣのＶＣ毎のパラメータブロックのメ
モリロケーションを示すポインタ値が含まれる。リンク
リストにおける最後のＶＣ毎のパラメータブロックのＮ
ＥＸＴ＿ＶＣフィールドは“ｄｏｎ’ｔ ｃａｒｅ”状
態である。

【００３６】例えば、図４の例で示すように、記憶ロケ
ーション２_A は内部に入力された４つのＶＣ_s である。
ＶＣ２、ＶＣ５，ＶＣ８，及びＶＣ３をこの順序で有す
る。従って、開始ポインタはＶＣ２を指し示す。ＶＣ２
のＮＥＸＴ＿ＶＣフィールドはＶＣ５を指し示す。順
次、ＶＣ５のＮＥＸＴ＿ＶＣフィールドはＶＣ８を指示
する。ＶＣ８のＮＥＸＴ＿ＶＣフィールドはＶＣ３を指
示する。ＶＣ３のＮＥＸＴ＿ＶＣフィールドはそれが記
憶ロケーション２_A に入力された最後のＶＣであること
から、“ｄｏｎ’ｔ ｃａｒｅ”に設定される。マスタ
カレンダーの終了ポインタはまたＶＣ３を指示する。

【００３７】ＶＣ毎のパラメータブロック１４の第２の
形式は、スレーブカレンダーエントリである。このブロ
ックは図４において斜線で示してある。この本例では、
ＶＣ１、ＶＣ６、及びＶＣ７がスレーブカレンダーエン
トリとして現在使用中である。これらのパラメータブロ
ックは、関連するＶＣによって１つのセルを転送するた
めの次のスケジュール時間ＮＳＴを記憶するためＮＳＴ
フィールドを用いる。ＮＳＴフィールドは、１６ビット
パラメータとしてＮＳＴを記憶する。ＶＣ毎のパラメー
タブロックの第３の形式は未使用ブロックであり、図４
ではＶＣ４を例として示している。

【００３８】図４に示すように、ＶＣ毎のパラメータブ
ロック１４の第１及び第２の両形式ともそれぞれ“ＱＵ
ＥＵＥ＿ＳＴＡＲＴ”フィールドを含んでいる。スケジ
ューリング回路を含むＡＴＭネットワークユニットの動
作中、スケジューリング回路によって転送されるセルデ
ータはネットワークユニットの別の回路によって連続し
て生成される。セルデータは待ち行列（キュー）を作っ
てＶＣ毎の原則で記憶される。従って、ＶＣ毎のパラメ
ータブロック１４のＱＵＥＵＥ＿ＳＴＡＲＴフィールド
はそのセルデータキューの先頭を指し示す。セルが送出
された後、ＱＵＥＵＥ＿ＳＴＡＲＴフィールドは新たな
セルデータキューの先頭を指示するように更新される。
なお、スレーブカレンダーエントリを与えるのに使われ
るＶＣ毎のパラメータブロックは、スレーブカレンダー
のＶＣがリンクリスト中で互いにリンクされないよう
に、それらの各ＮＥＸＴ＿ＶＣフィールドを“ｄｏｎ’
ｔ ｃａｒｅ”状態にする。

【００３９】図３に戻って、第１の実施例のスケジュー
リング回路はさらにそれぞれスレーブ及びマスタのスヌ
ープ(snoop) メモリ１６及び２０を有する。まず、スレ
ーブスヌープメモリ１６の処理を取り扱うために、一組
１２のＶＣ毎のパラメータブロック１４はＮブロック
（本例ではＮ＝３２）のグループに分割される。スレー
ブスヌープメモリ１６はＮビット幅を有する。従って、
スレーブスヌープメモリ１６の各Ｎビットワード１８は
組１２のＮ連続したＶＣ毎のパラメータブロック１４の
１つのグループと対応し、Ｎビットワード１８の各ビッ
トはそのワード１８に対応するグループのパラメータブ
ロック１４の１つと個々に対応する。１つのビットが１
に設定された時、対応するＶＣ毎のパラメータブロック
１４がスレーブカレンダーエントリとして使用されるこ
とを意味する。そのビットがリセットされると、それと
は反対に、対応するパラメータブロック１４がマスタカ
レンダーに入力されるか又は全く未使用であることを意
味する。

【００４０】スレーブスヌープメモリ１６により、カレ
ンダー制御回路２４は各パラメータブロックを直接読み
出す必要もなしにスレーブカレンダーエントリを構成す
るこれらのパラメータブロック１４を識別することが可
能になる。スレーブポインタＳはマスタカレンダー１の
スケジューリング範囲ＳＲより決して大きくならない時
間でＶＣ毎のパラメータブロック１４の組１２のパス
(pass) を完了する必要がある。このことは、記憶に留
めるべき重要な点である。

【００４１】マスタスヌープメモリ２０は、マスタカレ
ンダー１に関して同様な目的で使用される。ここでも、
マスタカレンダーはＮ個の連続した記憶ロケーション２
（本例でもＮ＝３２）のグループに分割される。マスタ
スヌープメモリ２０はＮビット幅を有し、各Ｎビットワ
ード２２はＮ個の連続した記憶ロケーション２の１つの
グループに対応する。Ｎビットワード２２内の各ビット
は、個々にそのグループの１つの記憶ロケーション２に
対応する。この場合、ワード２２の１ビットが１にセッ
トされた時、対応する記憶ロケーション２はその中に入
力された少なくとも１つのＶＣを有することを意味す
る。もし、このビットがゼロならば、反対に、対応する
記憶ロケーション２は“空”、すなわち有効なエントリ
を含まない、ことになる。

【００４２】マスタスヌープメモリ２０は、カレンダー
制御回路２４によっていかなるＶＣエントリをも含まな
い記憶ロケーション２の検査を回避するために使用され
る。これは、Ａポインタ４がＴポインタ３に追いつくこ
とを可能とする点で有用である。マスタカレンダースヌ
ープ２０の具体的な使用例を図５及び６を参照して説明
する。

【００４３】図５には、マスタカレンダースヌープメモ
リ２０の特定のワード２２_A に対応した３２個のマスタ
カレンダー記憶ロケーション２のグループが示されてい
る。このグループの記憶ロケーションは、物理的な記憶
ロケーション００２０（１６進）〜００３Ｆ（１６進）
を有する。ワード２２_A において、最初の非ゼロビット
は最下位のビット（ＬＳＢ）の左側６番目に位置し、関
連グループの最初のカレンダーエントリは００２０＋６
＝００２６（１６進）の位置であることを意味する。

【００４４】その結果、カレンダー制御回路２４は、ワ
ード２２_A を読むことによって００２０〜００２５（１
６進）の記憶ロケーションをサービスする必要がないこ
とを知る。図６に示すように、処理すべき最初の記憶ロ
ケーションは００２６（１６進）である。なお、この記
憶ロケーション（本例では００２６）はカレントタイム
ポインタＴの前方であってもよい。この場合、カレンダ
ー制御回路２４は、Ｔポインタが記憶ロケーション００
２６のエントリにサービスを行う前、そのロケーション
に達するまで待つ。そのような待ちを要求できるのは、
さもなければ、Ｔポインタの前方の記憶ロケーションが
許可されていないのにサービスを受ける可能性がおきる
からである。

【００４５】先に述べたように、アクティビティポイン
タＡは、どんな特定のタイムスロットでもスケジュール
されたＶＣを超えてよいため、カレントタイムポインタ
Ｔの後方に遅れる可能性がある。マスタカレンダー１は
連続したループ中で処理がなされるため（すなわち、Ａ
及びＴポインタは、マスタカレンダーの最後の記憶ロケ
ーションに達した後、その最初の記憶ロケーション２へ
“ラップアラウンド (wrap around)”するか又は戻
る）、マスタカレンダーの範囲近傍にスケジュールされ
ているチャネルが、アクティビティポインタＡのまだサ
ービスされていない、従ってそのチャネルデータフロー
を破壊し得るマスタカレンダーの一部へ書き込まれない
ようにする保護機構が必要になる。

【００４６】そのような保護機構を与えるため、マスタ
カレンダーのスケジューリング範囲ＳＲは、記憶ロケー
ションのプリセット数によりマスタカレンダーの全記憶
ロケーションの数Ｌより少なく設定される。もし、マス
タカレンダーにおける記憶ロケーションの数が約１００
０ならば、一例として２５６記憶ロケーションが設定さ
れる。

【００４７】図７を参照して、アクティビティポインタ
Ａは、マスタカレンダーの記憶ロケーションのある数
（２５６以下）だけタイムポインタＴの後方に遅れて示
されている。先述したように、Ａポインタによって指し
示される記憶ロケーションの各エントリがサービスされ
る時、次のスケジュール時間（ＮＳＴ）がマスタカレン
ダー１のスケジューリング範囲（図７の斜線範囲）より
前方（すなわち、Ｔポインタによって測量されるような
現時間の前方）のさらに先にある場合、関連するＶＣを
スレーブカレンダーで再スケジュールすべきかを判断さ
れる。言いかえれば、ＮＳＴとカレントタイムポインタ
Ｔとの間の差がカレンダーのスケジューリングより大き
いか否かがチェックされる。この差は、Ｔポインタがマ
スタカレンダーを“ラップアラウンド”していても容易
に計算できる。なぜなら、ＮＳＴはＴに関して常に先方
にあると仮定し得るからである。

【００４８】それとは異なる再スケジューリングの可能
性を以下で説明する。もし、計算したＮＳＴが現時刻よ
りも前ならば（ＣＢＲチャネルで可能なように）、図７
のＴポインタの前方の記憶ロケーションＢはＮＳＴに対
応し、カレントタイムポインタＴによって指示される記
憶ロケーションの後の次の記憶ロケーション（Ｔ＋１）
でスケジュールされるよう、カレンダー制御回路２４は
ＮＳＴを切り上げる。

【００４９】なお、ＣＢＲトラフィックはＡポインタと
の関連でスケジュールされるが、もしＮＳＴがＴポイン
タ（それ以下）の前方にあるなら、Ｔポインタの後（Ｔ
＋１）に置かれなければならない。他の全てのトラフィ
ックはＴポインタとの関連でスケジュールされる。マス
タスヌープメモリはＡポインタの前方ロケーションの読
み出しを許容できるため、ＡポインタはＴポインタの前
を走行可能である。しかしながら、この場合、そのよう
なロケーションへのいかなるサービスもＴポインタがそ
れらに追いつくまでは実行されない。

【００５０】ＮＳＴがスケジューリング範囲ＳＲ内なら
ば、図７の記憶ロケーションＣはＮＳＴに対応し、カレ
ンダー制御回路２４はスケジューリング範囲内で記憶ロ
ケーションＣにＶＣを入力する。もし、記憶ロケーショ
ンが先に空であった場合には、そのロケーションの開始
及び終了ポインタは再スケジュールされるＶＣに対応し
たＶＣ毎のパラメータブロックを指し示すように更新さ
れる。しかしながら、もし関連する記憶ロケーションに
すでに１つ以上のエントリが存在していた場合、カレン
ダー制御回路２４は記憶ロケーションＣにおける既存リ
ンクリストの最後に再スケジュールされるＶＣに対応し
たＶＣ毎のパラメータブロック１４を付加する。このこ
とは、そのリストに付加されるＶＣ毎のパラメータブロ
ック１４のメモリロケーションを指し示すように既存リ
ンクリストにおける最終ＶＣ毎のパラメータブロック１
４のＮＥＸＴ＿ＶＣフィールドの更新と、そして次にこ
の付加されたＶＣ毎のパラメータブロック１４を指し示
すようマスタカレンダー記憶ロケーション２の終了ポイ
ンタの更新とを伴う。

【００５１】もし、ＮＳＴがスケジューリング範囲（例
えば、図７の記憶ロケーションＤ）を超えてＶＣを再ス
ケジュールすべきことを指示していた場合、カレンダー
制御回路はマスタカレンダーにエントリを作成すること
を許可せずに、代わりにスレーブカレンダーにＶＣを入
力する。これは、再スケジュールされるＶＣに対応した
スレーブスヌープメモリ１６のビットを１に設定し、そ
して計算したＮＳＴを反映すべくこのＶＣに対応したＶ
Ｃ毎のパラメータブロック１４のＮＳＴフィールドを更
新することによって単純に達成される。

【００５２】次に図８を参照して、マスタカレンダーエ
ントリをサービスするのにカレンダー制御回路２４が実
行するステップを説明する。初めに、ステップＳ１にお
いて、カレンダー制御回路２４はＡポインタで指し示さ
れた記憶ロケーションで処理すべき次のエントリを決定
する。このエントリは（関連する記憶ロケーションで処
理すべき２番目の又は引き続くエントリであっても）、
記憶ロケーションの開始ポインタを使って識別される。
ポインタは、関連するＶＣのＶＣ毎のパラメータブロッ
ク１４のメモリロケーションを指し示す。一旦、処理す
べきＶＣのＶＣ毎のパラメータブロック１４が識別され
ると、そのパラメータブロックのＱＵＥＵＥ＿ＳＴＡＲ
Ｔフィールドが調べられ、送信すべきセルの位置を決定
する。このセルは次に送信され、ＱＵＥＵＥ＿ＳＴＡＲ
ＴフィールドはこのＶＣの次のサービスの準備のため更
新される。

【００５３】記憶ロケーションの開始ポインタもまた、
その記憶ロケーションにおける次のエントリ（もしある
なら）を指し示すため更新される。すなわち、開始ポイ
ンタは現在処理中のエントリのＮＥＸＴ＿ＶＣフィール
ドに保持された位置に設定される。そのようなエントリ
が存在しなければ、すなわちその時点で開始ポインタが
終了ポインタと同じ値を持つなら、マスタスヌープメモ
リ２０がマスタカレンダーからその記憶ロケーションを
とり除くべく更新される。

【００５４】ステップＳ２では、処理されるＶＣのＮＳ
Ｔを決定するのに従来の処理が適用される。なお、ＮＳ
Ｔを計算する時、その計算は好適には１つのフルレート
(full-rate) セル期間よりも高い精度で、すなわちセル
期間の端数 (fraction) を用いて、実行される。この端
数は（例えば、ＮＳＴフィールドに付加された端数フィ
ールドを使って関連するＶＣのＶＣ毎のパラメータブロ
ックに）保持され、ＮＳＴが計算される各時間毎に使用
される。これにより、マスタカレンダーにおけるスケジ
ューリングスロットの各々が１つのフルレートセル期間
に対応していたとしても、ＶＣはインターセル間隔がフ
ルレートセル期間の整数に等しくない平均転送速度を実
現することができる。ステップＳ３では、計算したＮＳ
Ｔがマスタカレンダーのスケジューリング範囲内か否か
が決定される。

【００５５】もし、ＮＳＴがスケジューリング範囲内な
らば、処理はステップＳ４へ進み、そこでＮＳＴがＴポ
インタと比較される。ＮＳＴがＴポインタの後方ならば
（ステップＳ４で“ｙｅｓ”）、処理はステップＳ５へ
進み、そこでカレンダー制御回路はＮＳＴを切り上げて
Ｔポインタに１を加算した値（Ｔ＋１）に等しくする。
反対に、ステップＳ４で結果が“ｎｏ”なら、処理はス
テップＳ６へ直接進む。

【００５６】ステップＳ６では、ＶＣはマスタカレンダ
ーで再スケジュールされる。ＶＣが再スケジュールされ
るマスタカレンダー記憶ロケーションは、ＮＳＴに基づ
いて決定される。その記憶ロケーションが初め空きなら
ば、その開始及び終了ポインタが更新され、処理される
ＶＣに対するＶＣ毎のパラメータブロック１４を指し示
す。さもなければ、先述したように、ＶＣ毎のパラメー
タブロックが関連する記憶ロケーションの位置で既存の
リンクリストに付加される。

【００５７】もし、ステップＳ３の結果が“ｎｏ”な
ら、すなわち計算したＮＳＴがマスタカレンダーのスケ
ジューリング範囲ＳＲ外なら、処理はステップＳ７へ進
む。ステップＳ７では、処理されるＶＣがスレーブカレ
ンダーで再スケジュールされる。初めに、計算されたＮ
ＳＴがそのＶＣに対応するＶＣ毎のパラメータブロック
１４のＮＳＴフィールドに記憶される。次に、そのＶＣ
に対応したスレーブスヌープメモリ１６のビットが１に
セットされる。そして、処理はステップＳ８へ進む。

【００５８】最後に、ステップＳ８で、ちょうど処理し
たＶＣがその記憶ロケーション（その記憶ロケーション
をマスタカレンダーから削除するためステップＳ１で更
新されたマスタスヌープメモリ２０）で処理すべき最後
のＶＣであったか否かが決定される。もし、そうなら、
次のビジーロケーションを判断して、次のサービス動作
の準備のためにマスタスヌープメモリ２０を使ってＡポ
インタが更新され、そして処理は終了する。

【００５９】ここでは、スレーブカレンダーの処理を図
９を参照して説明する。スレーブカレンダーの処理は、
マスタカレンダーの処理と並行して実行される。最初の
ステップＳ１０では、カレンダー制御回路２４は、スレ
ーブスヌープメモリ１６を使って、スレーブカレンダー
におけるＳポインタ８の前方の最初のビジーロケーショ
ンを決定する。そして、ステップＳ１１で、そのビジー
ロケーションでＶＣ毎のパラメータブロックのＮＳＴフ
ィールドを読み出す。ステップＳ１２では、ＮＳＴフィ
ールド中の記憶されたＮＳＴをカレントタイムポインタ
Ｔと比較する。記憶したＮＳＴとＴとの間の差がマスタ
カレンダーのスケジューリング範囲ＳＲ内である場合
は、処理がＳ１３へ進む。

【００６０】なお、図９に示すように、記憶したＮＳＴ
は、実際には、Ｔポインタに所定のオフセット時間ΔＴ
を加算したものと比較される。記憶したＮＳＴと（Ｔ＋
ΔＴ）との間の差がマスタカレンダーのスケジューリン
グ範囲ＳＲ内である場合は、処理はＳ１３へ進む。オフ
セット時間ΔＴはマスタカレンダーへのＶＣ転送に伴う
メモリ書き込み動作の時間を許容するのに必要であるた
め比較で用いる。オフセット時間はゼロに設定してもよ
い。

【００６１】ステップＳ１３では、カレンダー制御回路
２４が、ＮＳＴからマスタカレンダーに入力すべきＶＣ
の位置（記憶ロケーション２）を決定する。そして、ス
テップＳ１４で、ＶＣがその記憶ロケーション入力され
る。このステップＳ１４は、基本的に図８と関連して先
述したステップＳ６と同様である。次に、ステップＳ１
５で、このＶＣに対応するスレーブスヌープメモリ１６
のビットがリセットされ、ＶＣに対応するマスタスヌー
プメモリ２０のビットがセットされる。それによりスレ
ーブカレンダーからマスタカレンダーへのＶＣ転送が反
映され（ステップＳ１６）、処理が終了する。ステップ
Ｓ１２では、記憶したＮＳＴとＴ（又はＴ＋ΔＴ）との
間の差がマスタカレンダーのスケジューリング範囲ＳＲ
を超えることが判明した場合に、アクションなしに処理
が終了する。

【００６２】図１０は、本発明の第２の実施例によるス
ケジューリング回路部分を示している。本実施例は異な
る優先度のセルを効果的に制御可能とすることを意図し
ている。図１０の回路は、４つのマスタカレンダー１−
１〜１−４と、有効な４つのスレーブカレンダー６−１
〜６−４とを有する。各マスタカレンダー１−１〜１−
４は第１の実施例のマスタカレンダー１と同じ構成を有
する。第２の実施例のスレーブカレンダー６−１〜６−
４もまた第１の実施例のスレーブカレンダー６と基本的
な構成を同じくする。

【００６３】各マスタカレンダーは、それ自身のＴポイ
ンタ３及びＡポインタ４を有する。例えば、マスタカレ
ンダー１−１はＴポインタ３−１（Ｔ１）及びＡポイン
タ４−１（Ａ１）を有する。各スレーブカレンダー６
は、それ自身のＳポインタ８を有する。例えば、スレー
ブカレンダー６−１はそれ自身のＳポインタ８−１（Ｓ
１）を有する。カレンダー制御回路３４は、全てのマス
タ及びスレーブカレンダー１及び６に接続され、そして
スケジューリング回路の制御動作のために全てのポイン
タ３、４及び８に接続される。

【００６４】図１０の回路において、各マスタカレンダ
ー１−１〜１−４はＡＴＭネットワークユニット内で異
なる優先レベルのセルトラフィックに対応する。例え
ば、マスタカレンダー１−１は最高の優先度を有し、そ
してマスタカレンダー１−２は次の高い優先度を有す
る、等である。本明細書の最初の部分で指摘したよう
に、ＡＴＭネットワークの異なる仮想チャネルは、異な
る優先度を有する異なる形式のセルトラフィックを伝送
する。高優先度の仮想チャネルは一定ビット速度（ＣＢ
Ｒ）チャネルを含む。図１０の回路において、従って、
そのようなチャネルは最高優先度のマスタカレンダー１
−１でスケジュールされる。可変ビット速度（ＶＢＲ）
チャネルもまた高い優先度を有し（しかしながら、ＣＢ
Ｒチャネルよりは低い）、マスタカレンダー１−２でス
ケジュールされる。利用可能ビット速度（ＡＢＲ）チャ
ネルは低い優先度を有し、マスタカレンダー１−３でス
ケジュールされる。最後に、不特定ビット（ＵＢＲ）速
度チャネルは最低優先度のマスタカレンダー１−４でス
ケジュール可能である。

【００６５】各マスタカレンダー１は、それ自身個々に
対応したスレーブカレンダー６を有する。例えば、スレ
ーブカレンダー６−１は、図１０のマスタカレンダー１
−１に対応する。各マスタカレンダー１及びそれに個々
に対応したスレーブチャネルは、基本的には上述した第
１の実施例と同様に動作する。特に、マスタカレンダー
はそれぞれのＶＣに対応したエントリを記憶するように
与えられる記憶ロケーション（図１０には示していな
い）を有する。これらの記憶ロケーションは、関連する
マスタカレンダーのＡポインタが進む時に、カレンダー
制御回路３４によって連続してサービスされる。関連す
るマスタカレンダーのＴポインタは各セル期間ごとに進
み、Ａポインタは典型的にはＴポインタの項方に遅れる
ことになる（しかしながら、常時追いつこうとする）。

【００６６】Ａポインタによって指し示された記憶ロケ
ーションのエントリがサービスされる時、そのエントリ
で特定されるＶＣセルが転送され、そのＶＣは再スケジ
ュールされる。そのような再スケジューリングでは、も
しＶＣの次のスケジュール時間ＮＳＴがマスタカレンダ
ーのスケジューリング範囲ＳＲ内の場合には、ＶＣはマ
スタカレンダーの適当に引き続くエントリにおいて再ス
ケジュールされる。一方、ＮＳＴがマスタカレンダーの
スケジューリング範囲ＳＲを超える場合には、ＶＣは関
連するマスタカレンダーに対応するスレーブカレンダー
６に入力される。第１の実施例と関連して先に述べたよ
うに、ＮＳＴもまたスレーブカレンダーのエントリに含
まれる。

【００６７】各スレーブカレンダー６は、関連するＳポ
インタによって連続的にスキャンされる。Ｓポインタに
より関連するスレーブカレンダー６を通したパスの完了
にかかる全体の時間は、それが対応するマスタカレンダ
ーのスケジューリング範囲ＳＲより少なく与えられる。
Ｓポインタにより指し示される記憶ロケーションでＶＣ
がスレーブカレンダーにおいて発見されると、先に述べ
たようにＶＣの記憶したＮＳＴは関連するスレーブカレ
ンダーが対応するマスタカレンダーのカレントタイムポ
インタＴと比較される。もし、ＶＣが現在マスタカレン
ダーのスケジュール範囲内にあるならば、そのＶＣはス
レーブカレンダーからマスタカレンダーへ転送される。
反対に、ＶＣがいまだにスケジューリング範囲外なら
ば、そのＶＣはＳポインタによってスレーブカレンダー
を通った次のパスのために残される。

【００６８】図１０には示されていないが簡易化のた
め、第２の実施例におけるスケジューリング回路が、オ
プションとして各マスタカレンダー１のマスタスヌープ
メモリ及び／又は各スレーブカレンダー６のスレーブス
ヌープメモリに与えられる。実際、セル優先度が認識さ
れるＡＴＭネットワークユニットにおける異なるチャネ
ルの競合する要求のため、第２の実施例におけるそのよ
うなマスタ及びスレーブスヌープメモリの使用は好まし
いものである。

【００６９】次に、第２の実施例（そのようなマスタ及
びスレーブスヌープメモリを含む）の動作を図１１を参
照して説明する。図１１は、マスタカレンダー１−１〜
１−４と関連する動作を示している。各スレーブカレン
ダー６−１〜６−４は、図９で参照したこれより前に述
べたフローチャートと自動的に一致して動作する。図１
１に示すステップシーケンスは各セル期間で実行され
る。セル期間の開始で、ステップＳ２０では、処理され
るマスタカレンダーの優先レベルを表すパラメータＰＲ
Ｌは１（最高優先度）にセットされる。そして、ステッ
プＳ２１では、優先レベルＰＲＬを持つマスタカレンダ
ー１のＴ及びＡポインタの間のギャップがある所定の閾
値ＴＨＲ（例えば、２５６）より大きいか否かがチェッ
クされる。大きくなければ、関連するマスタカレンダー
のＴポインタはステップＳ２２で１インクリメントされ
る。さもなければ、Ｔポインタはインクリメントされ
ず、関連するマスタカレンダーは実質的には停止され、
ＡポインタにＴポインタに追いつく機会を与える。

【００７０】ステップＳ２３で、カレンダー制御回路３
４は優先レベルＰＲＬ（初期１）に対するマスタスヌー
プメモリを読み出す。ステップＳ２４では、ステップＳ
２３で読み出されたマスタスヌープメモリの結果が分析
され、Ａポインタに即近の範囲に如何なる“ビジー”マ
スタカレンダー記憶ロケーション、すなわち少なくとも
１つのエントリを含む記憶ロケーション、があるか否か
が判断される。もしあるなら、カレンダー制御回路３４
は、ステップＳ２５でこのビジーロケーションがＴポイ
ンタの前方であるか否かを判断する。ビジーロケーショ
ンがＴポインタの前方にない場合には、カレンダー制御
回路３４は処理すべき次のエントリが現在の優先レベル
マスタカレンダーのビジーロケーションにおけるエント
リ（又は２以上のエントリなら次のエントリ）かを判断
する。

【００７１】このエントリは、ステップＳ２６で処理さ
れる。ステップＳ２６で実行される処理ステップは、実
行的には図８のステップＳ１〜Ｓ９に対応する。ステッ
プＳ２４でビジーロケーションがなければ、又はステッ
プＳ２５でＴポインタの前方に次のビジーロケーション
が発見された場合には、カレンダー制御回路３４は、こ
の場合、現在の優先レベルＰＲＬ（初期１）でマスタカ
レンダーをサービスする必要なしと判断し、そしてステ
ップＳ２７で次の最低優先レベルへ移動するために優先
レベルパラメータＰＲＬをインクリメントする。ステッ
プＳ２８で、可能な全ての優先レベルがサービスされた
か否かを判断する。そうでなければ、処理はステップＳ
２１へ戻り、次の優先レベルに対するマスタカレンダー
をサービスする。４つの全ての優先レベルが処理された
ならば、処理はステップＳ２８の後に終了する。

【００７２】このように、図１１で示したように、もし
ある優先レベルに対しマスタスヌープメモリにより指示
されるビジーロケーションがなければ、カレンダー制御
回路は次の最低優先レベルへ移動し、そのレベルのマス
タスヌープメモリを読み出す。同様に、ある優先レベル
でマスタカレンダーの次のビジーロケーションがそのレ
ベルのカレントタイムポインタＴの前方にある場合に
は、カレンダー制御回路３４は次の最低優先レベルへ移
動し、より低い優先度のマスタカレンダーから送信する
のに適任のロケーションを探査する。

【００７３】第２の実施例において、４つのスレーブカ
レンダー６−１〜６−４が１つのスレーブメモリによっ
て与えられることが可能である。すなわち、メモリの共
通エリア内には４つの論理スレーブカレンダーが存在す
る。この場合、１つのスレーブメモリの各エントリは適
当な方法によって４つの論理スレーブカレンダー６−１
〜６−４の１つに割り当てられる。例えば、各エントリ
に４つの優先レベルの１つを識別可能な２ビットの優先
レベルフィールドが与えられる。この場合、各スレーブ
カレンダーは（上述したような）そのスレーブポインタ
を持つことが可能であり、又はシングルスレーブポイン
タが優先順位により４つの論理スレーブカレンダーの全
てをサービスするのに使用可能である。ステップＳ２１
をクロックサイクル毎に全ての優先レベルで並列に実行
させることで、図１１のフローチャートに示す処理がち
ょうど１クロックサイクルを表すことも可能である。

【００７４】図１２は本発明によるスケジューリング回
路の第３の実施例部分を示す。本実施例では、（第１の
実施例におけるような）マスタカレンダー１が存在する
が、第１の実施例における１つのスレーブカレンダー６
に代えて、それぞれ第１順位及び第２順位のスレーブカ
レンダー３６及び４６が存在する。第１順位のスレーブ
カレンダー３６はＳポインタ３８（１Ｓ）を有し、そし
て第２順位のスレーブカレンダー４６はＳポインタ４８
（２Ｓ）を有する。マスタカレンダー１は通常のＴ及び
Ａポインタ（図１２には示されていない）を有する。

【００７５】第３の実施例は、次の見地から与えられ
る。第１の実施例では、スレーブカレンダーの各エント
リがマスタカレンダーのスケジューリング範囲より小さ
いか又は等しい間隔でサービスされる必要がある。しか
しながら、スレーブカレンダーで読み出すべきロケーシ
ョンが多ければそれだけカレンダー制御回路が全てのス
レーブカレンダーエントリをスケジューリング範囲より
少ないか又は等しい時間で処理するのが困難となる。こ
の困難を緩和するために、第３の実施例ではスレーブカ
レンダーの“階層化(hierarchy) ”を行う。この場合、
階層における２つのスレーブカレンダー３６及び４６は
時間の大きさの異なる順位を表す。例えば、マスタカレ
ンダーのスケジューリング範囲ＳＲが１ミリ秒なら、第
１順位のスレーブカレンダー３６は次の１０ミリ秒で送
出が必要なセルを有するＶＣを処理するのに使われ、そ
して第２順位のスレーブカレンダーは次の１００ミリ秒
で送出が必要なセルを有するＶＣを処理するのに使われ
る。従って、マスタカレンダー１に入力されたＶＣが処
理され次に再スケジュールされる時、もし計算したＮＳ
Ｔが１０ミリ秒より大きければ、そのＶＣは第２順位の
スレーブカレンダー４６で再スケジュールされる。しか
しながら、その計算したＮＳＴがマスタカレンダーのス
ケジューリング範囲（１ミリ秒）より大きく且つ１０ミ
リ秒より小さい場合、それは第１順位のスレーブカレン
ダー３６で再スケジュールされる。先の実施例と同様
に、そのＮＳＴがスケジューリング範囲内の場合は、Ｖ
Ｃはマスタカレンダーで直接再スケジュールされる。

【００７６】スレーブカレンダーエントリの処理に関す
る限り、第２順位のスレーブカレンダー４６の場合に
は、その中の各エントリは１０ミリ秒毎に少なくとも一
度サービスされる必要があり、その結果ＶＣはそのＮＳ
Ｔが１０ミリ秒離れていない時に第１順位のスレーブカ
レンダーへ転送される。第１順位のスレーブカレンダー
３６の場合には、各エントリが１ミリ秒毎に少なくとも
一度サービスされる必要があり、その結果ＶＣはそのＮ
ＳＴがマスタカレンダーのスケジューリング範囲内の時
に第１順位のスレーブカレンダーからマスタカレンダー
へ転送される。

【００７７】従って、セル転送の間隔が１０ミリ秒より
大きいいかなるＶＣも、第２順位のスレーブカレンダー
でその時間部分を費やし、それによって第１順位のスレ
ーブカレンダー上の負荷を軽減する。１００ミリ秒のセ
ル転送間隔を有するＶＣは、第２順位のスレーブカレン
ダー４６に入力された時間の略９０％を、第１順位のス
レーブカレンダー４６に入力された時間の略９％を費や
し、そしてマスタカレンダーに入力された時間に費やす
時間は単に１％である。スレーブのカレンダーの順位数
は幾つでもよく、カレンダーのサイズ（利用可能なメモ
リ量）及びトラフィック速度の相違等に基づく。

【００７８】本発明の第３の実施例は、特に、大きく異
なる範囲のトラフィック速度、すなわち非常に低速なＶ
Ｃや他の非常に高速なＶＣ等、が存在するＡＴＭネット
ワークユニットで使用するのに適している。そのような
状況において、第３の実施例はスレーブカレンダーを通
したサーチ時間の短縮に顕著な有効性を示す。

【００７９】第１順位及び第２順位のスレーブカレンダ
ーのエントリは、マスタカレンダーと同様に、先述した
ような１組のＶＣ毎のパラメータブロックを使って作成
される。この場合、各スレーブカレンダーは、それ自体
個々に対応するスレーブスヌープメモリが与えられ、各
パラメータブロックが対応するスレーブカレンダーのエ
ントリとして現在使用されいるか否かを示す。これによ
り、スレーブカレンダー間のＶＣ転送を各スレーブスヌ
ープメモリの１ビットを変えることで簡易且つ素早く実
行することが可能となる。

【００８０】

【発明の効果】以上、本発明をＡＴＭセル転送のスケジ
ューリングに関して説明してきた。本発明は、他の実施
例において、例えばあるイベント（事象）をスケジュー
リングする必要がある状況下で提供可能なことは容易に
理解されるところである。このように本発明によれば、
特別な処理パワー及び／又は記憶容量を必要とせず、異
種速度のＶＣを効果的に制御可能な、改良したトラフィ
ックマネジャ及び改良したトラフィック管理方法が提供
可能となる。

【図面の簡単な説明】

【図１】ＡＴＭネットワークで用いられる従来のカレン
ダースケジューリング方法の図式的な説明図である。

【図２】本発明によるスケジューリング回路の基本構成
を図式的に示した図である。

【図３】本発明による第１の実施例のスケジューリング
回路部分を示した図である。

【図４】第１の実施例である図３の詳細図である。

【図５】第１の実施例におけるマスタスヌープメモリの
動作の説明図である。

【図６】マスタスヌープメモリの使用を説明した図であ
る。

【図７】第１の実施例の再スケジューリング動作の説明
図である。

【図８】第１の実施例のマスタカレンダーにおけるエン
トリ処理のフロー図である。

【図９】第１の実施例のスレーブカレンダーにおけるエ
ントリ処理のフロー図である。

【図１０】本発明による第２の実施例であって、異なる
形式のセルトラフィック処理を可能としたスケジューリ
ング回路部分を示した図である。

【図１１】第２の実施例の動作フロー図である。

【図１２】本発明による第３の実施例のスケジューリン
グ回路部分を示した図である。

【符号の説明】

１、１−１〜１−４…マスタカレンダー ２、７、１４…記憶ロケーション ３、３−１〜３−４…カレントタイムポインタ ４、４−１〜４−４…カレントアクティビティポインタ ６、６−１〜６−４…スレーブカレンダー ８、８−１〜８−４、３８、４８…スレーブポインタ ９、２４、３４…カレンダー制御回路 １２…一組の記憶ロケーション １４…ＶＣ毎のパラメータブロック １６…スレーブスヌープメモリ １８、２２…Ｎビットワード ２０…マスタスヌープメモリ ３６…第１順位のスレーブカレンダー ４６…第２順位のスレーブカレンダー

───────────────────────────────────────────────────── フロントページの続き (72)発明者 サイモン ティモシー スミス イギリス国，マンチェスター エム21 ０ ティーキュー，コールトン，リズバーン アベニュ １

Claims (13)

【特許請求の範囲】
1. 【請求項１】 所定のイベントをスケジュールするため
   のスケジューリング回路は、 所定のマスタカレンダースケジューリング範囲内で発生
   するイベントにそれぞれ対応したエントリを保持するマ
   スタカレンダー手段と、 前記スケジューリング範囲外で発生するイベントにそれ
   ぞれ対応したエントリを保持するスレーブカレンダー手
   段と、 イベントがスケジュールされる時、現時間とそのイベン
   トの所望のスケジューリング時間との間隔が前記スケジ
   ューリング範囲を超える場合に、前記スレーブカレンダ
   ー手段にそれに対応した前記所望のスケジューリング時
   間を示すタイミング情報を含むエントリを作成するカレ
   ンダ制御手段とを有し、 前記カレンダー制御手段は、さらに前記スレーブカレン
   ダー手段のエントリをモニタし、前記エントリに対応す
   るイベントが前記スケジューリング範囲内にあるエント
   リを前記マスタカレンダ−手段に転送することを特徴と
   するスケジューリング回路。
2. 【請求項２】 前記カレンダー制御手段は、前記イベン
   トのスケジューリング中に、前記間隔がスケジューリン
   グ範囲を超えない場合には、前記マスタカレンダー手段
   においてスケジュールされるイベントに対応したイベン
   トを作成する請求項１記載のスケジューリング回路。
3. 【請求項３】 前記スレーブカレンダー手段の各エント
   リに含まれるタイミング情報の細分性は前記現時間を測
   定した細分性に等しく、 前記カレンダー制御手段は、前記スレーブカレンダー手
   段におけるエントリのモニタの間に、そのエントリに含
   まれるタイミング情報によって示される所望のスケジュ
   ーリング時間と前記現時間とを比較し、その比較結果に
   より前記転送を実行するか否かを判断する請求項１又は
   ２に記載のスケジューリング回路。
4. 【請求項４】 前記転送は、前記エントリのタイミング
   情報によって示される所望のスケジューリング時間の差
   が、前記スケジューリング範囲及び所定のオフセット時
   間の合計より小さいか等しい量だけ前記現時間と異なる
   時に実行される請求項３記載のスケジューリング回路。
5. 【請求項５】 前記所定のイベントは、複数の異なるユ
   ニットの各々に対する一連のイベントを含み、前記マス
   タカレンダ−手段又はスレーブカレンダー手段における
   エントリの各々は、前記ユニットの１つに対する一連の
   イベントの次のイベントに対応する請求項１〜４のいず
   れか一つに記載のスケジューリング回路。
6. 【請求項６】 前記カレンダー制御手段は、前記マスタ
   カレンダー手段におけるエントリをシーケンシャルに処
   理し、そして処理される各エントリに対し、対応するイ
   ベントを生成し、処理したエントリを削除し、そしてマ
   スタカレンダー手段又はスレーブカレンダー手段の１つ
   に前記関連するユニットの一連の次のイベントに対応す
   る新たなエントリを作成する請求項５記載のスケジュー
   リング回路。
7. 【請求項７】 前記カレンダー制御回路によって現在処
   理中の前記マスタカレンダー手段の記憶ロケーションの
   １つを識別するアクティビティポインタを有し、そして
   対応するタイムスロットが前記現時間であるマスタカレ
   ンダー手段の記憶ロケーションの１つを識別するタイム
   ポインタを有する請求項６記載のスケジューリング回
   路。
8. 【請求項８】 前記アクティビティポインタは現在処理
   中の記憶ロケーションで、前記エントリの処理、もし１
   つ以上の場合は前記エントリの全ての処理の終了時に更
   新され、そして前記タイムポインタは前記現在時間に従
   って更新される請求項７記載のスケジューリング回路。
9. 【請求項９】 前記複数のエントリの前記ユニットはそ
   れ自身個々に対応するパラメータブロックを有し、前記
   パラメータブロックは選択的に前記マスタカレンダー手
   段におけるエントリ又は前記スレーブカレンダー手段に
   おけるエントリを構成する請求項５〜８のいずれか一つ
   に記載のスケジューリング回路。
10. 【請求項１０】 さらに、前記マスタ及びスレーブカレ
    ンダー手段におけるエントリとは独立に、前記カレンダ
    ー制御手段によってアクセスされるエントリ形式のスヌ
    ープメモリを有し、前記スヌープメモリは前記ユニット
    の１つに対応するパラメータブロックが前記マスタカレ
    ンダー手段におけるエントリ又は前記スレーブカレンダ
    ー手段におけるエントリを現在構成しているか否かを指
    示する請求項９記載のスケジューリング回路。
11. 【請求項１１】 前記イベントの複数の異なる優先レベ
    ルの各々に対する前記マスタカレンダー手段及びスレー
    ブカレンダー手段を有し、 各優先レベルは他の優先レベルの現在時間とは独立した
    それ自身の現在時間を有し、もし前記所望のスケジュー
    リング時間がその優先レベルに対する現在時間の後方又
    はそれに等しいイベントに対応したエントリをより高い
    優先レベルのマスタカレンダー手段が有する場合、前記
    カレンダー制御手段は特定の優先レベルに対するマスタ
    カレンダー手段でのエントリ処理を停止する請求項１〜
    １０のいずれか一つに記載のスケジューリング回路。
12. 【請求項１２】 前記スレーブカレンダー手段は、各第
    １順位及び第２順位のスレーブカレンダーを有し、 前記カレンダー制御手段は、前記イベントスケジューリ
    ング中に、もし前記現在時間とそのイベントの所望のス
    ケジューリング時間との間隔が前記マスタカレンダース
    ケジューリング範囲よりも大きな閾値を越えた場合に、
    第２順位スレーブカレンダーのイベントに対応したエン
    トリを作成し、そして前記間隔が前記マスタカレンダー
    スケジューリング範囲外であるが前記閾値を越えない場
    合には、第１順位スレーブカレンダーのイベントに対応
    したエントリを作成し、 前記カレンダー制御手段は、また第１順位及び第２順位
    のスレーブカレンダーをモニタし、その対応イベントが
    前記閾値よりも近くなった時点で第２順位スレーブカレ
    ンダーのエントリを第１順位のスレーブカレンダーへ転
    送し、そしてその対応イベントがマスタカレンダースケ
    ジューリング範囲内となった時点で第１順位スレーブカ
    レンダーのエントリを前記マスタカレンダー手段へ転送
    する請求項１〜１１のいずれか一つに記載のスケジュー
    リング回路。
13. 【請求項１３】 所定のイベントをスケジュールするス
    ケジューリング方法は、 イベントがスケジュールされる時、現時間とそのイベン
    トの所望のスケジューリング時間との間隔が所定のマス
    タカレンダースケジューリング範囲内の場合にはそれに
    対応したエントリがマスタカレンダー手段に作成される
    こと、 もし前記間隔が前記所定のマスタカレンダースケジュー
    リング範囲外の場合には前記イベントに対応するエント
    リが前記マスタカレンダー手段とは独立にスレーブカレ
    ンダー手段に作成されること、 前記スレーブカレンダー手段におけるエントリはモニタ
    されること、 その対応するイベントが前記マスタカレンダースケジュ
    ーリング範囲内になったエントリは前記マスタカレンダ
    ー手段へ転送されること、を特徴とするスケジューリン
    グ方法。