(57)【特許請求の範囲】
【請求項１】
スイッチの入力のおけるセルのコンプライアンスを判定するための装置にして、所定の最大カウント範囲を有するタイム・カウント手段（２）を含み、該タイム・カウント手段（２）は、第１到着セル（１５）に対する第１到着時間（ｔa1）を決定するカウント値及び第１比較手段（４）により第２到着セル（１２）に対する理論的な到着時間（ＴＡＴ2）と比較される前記第２到着セル（１２）に対する第２到着時間（ｔa2）を決定するカウント値を持ち、前記理論的な到着時間（ＴＡＴ2）は、前記第１到着時間（ｔa1）と到着相互間の期間（Ｔ）の所定値とを使用して時間計算手段（６）において計算され、前記第１比較手段（４）において遂行された前記比較の結果に依存して、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかが判定されるという装置であって、
前記タイム・カウント手段（２）のラップの数をカウントするためのラップ・カウント手段（３）にして、前記第２到着時間（ｔa2）におけるカウント値及び前記理論的な到着時間（ＴＡＴ2）におけるカウント値が、前記理論的な到着時間（ＴＡＴ2）と前記第２到着時間（ｔa2）との間でラップが生じたかどうかを決定するために使用可能である、ラップ・カウント手段（３）を含み、
該決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第１比較手段（４）における前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用され、
前記ラップ・カウント手段（３）のカウント値が決定される人為的な第２到着時間（ｔa2）をもたらすバックグラウンド・プロセス（ｂｐ）を、所定の反復周期（ＴＲ）を持つ時間的に規則的な基準で開始させる状態決定手段（１４）を含み、
前記人為的な第２到着時間（ｔa2）における前記ラップ・カウント手段（３）のカウント値は、前記理論的な到着時間（ＴＡＴ2）における前記ラップ・カウント手段（３）のカウント値と共に、前記理論的な到着時間（ＴＡＴ2）と前記人為的な第２到着時間（ｔa2）との間でラップが生じたかどうかを決定するために使用され、該決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第１比較手段（４）における前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用され、
前記反復周期（ＴＲ）は、最大でも、前記タイム・カウント手段（２）の２つのラップの間の時間に前記ラップ・カウント手段（３）の最大のカウント値マイナス２を乗じたものであることを特徴とする装置。
【請求項２】
前記第１到着時間（ｔa1）における前記ラップ・カウント手段（３）のカウント値と前記第２到着時間（ｔa2）における前記ラップ・カウント手段（３）のカウント値とを比較するための第２比較手段（１０）を含むことを特徴とする、請求項１に記載の装置。
【請求項３】
前記理論的な到着時間（ＴＡＴ2）における前記ラップ・カウント手段（３）のカウント値を決定するための第１決定手段（７）を含むことを特徴とする、請求項１に記載の装置。
【請求項４】
前記第２到着時間（ｔa2）における前記ラップ・カウント手段（３）のカウント値を記憶するための第１メモリ手段（８）及び前記第１到着時間（ｔa1）における前記ラップ・カウント手段（３）のカウント値を記憶するための第２メモリ手段（９）を含むことを特徴とする、請求項１に記載の装置。
【請求項５】
前記理論的な到着時間（ＴＡＴ2）と前記人為的な第２到着時間（ｔa2）との間でラップが生じたかどうかの前記決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用される有効性フラッグをセットするために使用されることを特徴とする、請求項１に記載の装置。
【請求項６】
スイッチの入力におけるセルのコンプライアンスを判定するための方法にして、所定の最大カウント範囲を有するタイム・カウント手段（２）でもって時間がカウントされ、第１到着セル（１５）に対する前記タイム・カウンタ手段（２）のカウント値の使用の下に、前記第１到着セル（１５）に対する第１到着時間（ｔa1）が決定され、第２到着セル（１２）に対する前記タイム・カウント手段（２）のカウント値の使用の下に、第１比較手段（４）において前記第２到着セル（１２）に対する理論的な到着時間（ＴＡＴ2）と比較される前記第２到着セル（１２）に対する第２到着時間（ｔa2）が決定され、前記理論的な到着時間（ＴＡＴ2）は、前記第１到着時間（ｔa1）と到着相互間の期間（Ｔ）の所定値とを使用して計算され、前記比較の結果に従って、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかが判定されるという方法であって、
前記タイム・カウント手段（２）のラップの数がラップ・カウント手段（３）によってカウントされ、前記理論的な到着時間（ＴＡＴ2）と前記第２到着時間（ｔa2）との間でラップが生じたかどうかを決定するために前記第２到着時間（ｔa2）及び前記理論的な到着時間（ＴＡＴ2）における前記ラップ・カウント手段（３）のカウント値が使用され、該決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第１比較手段（４）における前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用され、
前記ラップ・カウント手段（３）のカウント値が決定される人為的な第２到着時間（ｔa2）をもたらすバックグラウンド・プロセス（ｂｐ）が、所定の反復周期（ＴＲ）を持つ時間的に規則的な基準で開始され、
前記人為的な第２到着時間（ｔa2）における前記ラップ・カウント手段（３）のカウント値は、前記理論的な到着時間（ＴＡＴ2）における前記ラップ・カウント手段（３）のカウント値と共に、前記理論的な到着時間（ＴＡＴ2）と前記人為的な第２到着時間（ｔa2）との間でラップが生じたかどうかを決定するために使用され、該決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第１比較手段（４）における前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用され、
前記反復周期（ＴＲ）は、最大でも、前記タイム・カウント手段（２）の２つのラップの間の時間に前記ラップ・カウント手段（３）の最大のカウント値マイナス２を乗じたものであることを特徴とする方法。
【請求項７】
前記第１到着時間（ｔa1）における前記ラップ・カウント手段（３）のカウント値が前記第２到着時間（ｔa2）における前記ラップ・カウント手段（３）のカウント値と比較されることを特徴とする、請求項６に記載の方法。
【請求項８】
前記第２到着時間（ｔa2）及び前記第１到着時間（ｔa1）における前記ラップ・カウント手段（３）のカウント値がそれぞれ記憶されることを特徴とする、請求項６に記載の方法。
【請求項９】
前記理論的な到着時間（ＴＡＴ2）と前記人為的な第２到着時間（ｔa2）との間でラップが生じたかどうかの前記決定の結果は、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記比較を使用すべきかどうかを判定するために使用され、或いは、前記比較を行うことなく、前記第２到着セル（１２）をコンプライアントであると見なすべきか又は非コンプライアントであると見なすべきかを判定するために使用される有効性フラッグをセットするために使用されることを特徴とする、請求項６に記載の方法。
【請求項１０】
前記人為的な第２到着時間（ｔa2）が前記第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の１ラップ事象後にある場合（ケースIII）、前記人為的な第２到着時間（ｔa2）が第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の少なくとも２ラップ事象後に又は前記第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の少なくとも１ラップ事象前にある場合（ケースＶ）、或いは、前記人為的な第２到着時間（ｔa2）が前記第１到着時間（ｔa1）の１ラップの事象後にある前記理論的な到着時間（ＴＡＴ2）の少なくとも１ラップ事象後にある場合（ケースVI）、前記有効性フラッグがリセットされることを特徴とする、請求項９に記載の装置。
【請求項１１】
前記第２到着セル（１２）の到着時に、前記有効性フラッグがリセットされている場合、前記第２到着セル（１２）がコンプライアントであると見なされることを特徴とする、請求項９に記載の方法。
【請求項１２】
前記第２到着セル（１２）の到着時に、前記理論的な到着時間（ＴＡＴ2）及び前記第２到着時間（ｔa2）の両方が前記第１到着時間（ｔa1）の後の１つのラップ事象後にある場合（ケースＩ）、或いは、前記第２到着時間（ｔa2）、前記第１到着時間（ｔa1）、及び前記理論的な到着時間（ＴＡＴ2）がすべてラップ事象によって分離されていない場合（ケースIV）、前記タイム・カウント手段（２）がラップを有する時にセットされるキャリー・フラッグのリセット状態を使用して、又は前記キャリー・フラッグを使用することなく、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第２到着時間（ｔa2）及び前記理論的な到着時間（ＴＡＴ2）が前記第１比較手段（４）において比較されることを特徴とする、請求項９に記載の方法。
【請求項１３】
前記第２到着セル（１２）の到着時に、前記理論的な到着時間（ＴＡＴ2）が前記第１到着時間（ｔa1）及び前記第２到着時間（ｔa2）の１ラップ事象後にある場合（ケースII）、前記タイム・カウント手段（２）がラップを有する時にセットされるキャリー・フラッグを使用して、前記第２到着セル（１２）がコンプライアントであると見なされるか又は非コンプライアントであると見なされるかを判定するために前記第２到着時間（ｔa2）及び前記理論的な到着時間（ＴＡＴ2）が前記第１比較手段（４）において比較されることを特徴とする、請求項９に記載の方法。
【請求項１４】
前記第２到着セル（１２）の到着時に、前記第２到着時間（ｔa2）が前記第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の１ラップ事象後にある場合（ケースIII）、前記人為的な第２到着時間（ｔa2）が前記第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の後の２つ又はそれ以上のラップ事象又は第１到着時間（ｔa1）及び前記理論的な到着時間（ＴＡＴ2）の前の少なくとも１つのラップ事象にある場合（ケースＶ）、或いは、前記第２到着時間（ｔa2）が前記第１到着時間（ｔa1）の後の１つのラップ事象にある前記理論的な到着時間（ＴＡＴ2）の後の１つのラップ事象にある場合（ケースVI）、前記第２到着セル（１２）はコンプライアントであると見なされることを特徴とする、請求項９に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
スイッチング・デバイスに到着したセルがコンプライアントであると見なすべきか或いは非コンプライアントであると見なすべきかを判定するために、スイッチの入力ポートにおけるセルのコンプライアンスを判定するための方法及び装置が使用される。その判定の結果は、そのセルが廃棄されるべきか或いは受け入れ可能であるかを判定するための基準として使用可能である。
【０００２】
【従来の技術】
固定長のセルを介して情報を搬送する分野では、複数の入力接続線を複数の出力接続線に接続するスイッチが使用される。それらのスイッチは入力接続線に到着したセルを、それらのセルが向かおうとしている出力接続線に送る。そのようなスイッチは、セルの喪失なしにセルを処理するようにそれらの容量を制限されるので、各入力接続線は、割振り帯域幅とも呼ばれる最大セル配送率を割り当てられる。すべてのセンダがそれぞれの割振り帯域幅によって定義された制限内に留まっている限り、スイッチは、情報の喪失という危険なしにセルを処理するように設計される。正しい機能のために、各接続線に関して現在使用されている帯域幅を決定するための機構が使用される。センダがそれの帯域幅の制限を超える場合、例えば、センダにそれの出力セル速度を絞らせるために、上流方向にそのセンダへ制御信号が送られることがある。従って、すべての接続線に対するサービスの質を保証するためには、現在使用されている帯域幅に関する正しい決定が重要である。既知の記号は、入力セルの到着時間を決定するための基準として使われるタイム・カウンタを使用している。先行のセルと同じ接続線を介して到着するものと期待される次のセルに対して、理論的な到着時間が計算される。そこで、このような次のセルの到着時間をそれの理論的な到着時間（ＴＡＴとも呼ばれる）と比較する汎用セル速度アルゴリズム、即ち、ＧＣＲＡが実行される。一般に、ＧＣＲＡは２つのアクションを遂行する。即ち、それは、セルの到着時に、到着したセルがコンプライアントであると見なすべきか非コンプライアントであると見なすべきかを決定し、しかる後、新たな理論的な到着時間を計算する。ＧＣＲＡの既知の原理は、１９９５年３月発行のＩＴＵ通信標準化部門のＩＴＵ勧告Ｉ．３７１１に記述されている。又、ＧＣＲＡは、種々の修正と共に存在する漏出性バケット・アルゴリズムとしても知られている。漏出性バケット・アルゴリズムの概要はインターネットを介して、アドレスhttp://www-kr.cisco.com/univercd/data/doc/lightstr/r2_2/sys_over/traffic.htmにおいて見ることができる。
【０００３】
米国特許第５４１８７７７号には、メッセージ・セル・ストリームが非同期的に伝送され、しかも複数の仮想接続線に向けてメッセージ・セルを搬送するというメッセージ伝送システムのための修正漏出性バケット方式が開示されている。すべての仮想接続線に対するメッセージ・セル速度が監視され、同じ仮想接続線に属する２つのメッセージ・セルの間の最も短い許容し得るタイミングが２つの数の商によって表される。
【０００４】
米国特許第５２２４０９２号には、複数の非同期時分割伝送チャネルへのデータ・セルのフローを、複数のカウント値の状態に関連してそれらのチャネルにおける伝送のための単一の許容スイッチでもって制御するための方法が開示されている。その米国特許では、多数の変数のインクリメント又はデクリメントが使用される。それらの変数は多数の評価信号を発生させるように処理され、それらの評価信号は、その後、更なる処理によって、データ・セルを受け入れるために又は受け入れないために使用される制御信号に変換される。もう１つのそれに関連した特許は、米国特許第５２２４０９１号である。その米国特許は、データ・フローを伝送することができる複数の仮想非同期時分割伝送チャネルを含む伝送システムを監視するための方法に関するものである。
【０００５】
米国特許第５５０９００１号には、ＡＴＭスイッチに入力されるべきセルを制御するための装置が開示されている。その装置は、種々のセルの各々に対するセルの番号を定期的に変更するための定期的計算回路、及びバッファ回路に記憶されたセルがＡＴＭスイッチに出力されるべきか又は廃棄されるべきかを決定するための制御部分を含んでいる。
【０００６】
米国特許第５６２３４０５号には、非同期転送モード・ネットワークのための課金システム及び方法が開示されている。
【０００７】
そのようなカウンタのカウント範囲が実際のハードウェアにおいていつも制限されるという事実のために問題が生じる。従って、カウンタは、それが最高の可能な読み（カウント値）に達する時、それの最低の読みにラップし、再びカウントを開始する。従って、カウンタ・ラップの後のカウンタの読みは前のカウンタの読みよりも低いことになる。これは、センダの誤操作及び誤処理を導く。もっと正確に云えば、タイム・カウンタのラップは、セルが非コンプライアントであってもそれらはコンプライアントであると見なされ、セルがコンプライアントであると見なされるべきであってもそれらは非コンプライアントであると見なされるという状況を導くことがあり得る。別の言葉で言えば、タイム・カウンタがセルを待っている間に又は次のＴＡＴの前にラップを持つ場合、ＧＣＲＡの結果は誤りとなることがある。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、セルが到着する接続線において実際に使用された帯域幅を正しく決定するように設計されることにより上記の問題点を回避する装置を提供することであり、本発明の他の目的は、上記の問題点を回避する方法を提供することである。これは、ラップが生じたかどうかを決定するためにタイム・カウント手段が監視されるということで達成され、その決定の結果は、理論的な到着時間が到着セルの到着時間と比較されるべき有効な値を有するかどうかを決定するために有用である。
【０００９】
【課題を解決するための手段】
第１到着時間におけるラップ・カウント手段の読みと第２到着時間におけるラップ・カウント手段の読みとを比較するための第２比較手段は、第１セルが到着したウインドウ及び第２セルが到着したウインドウの番号における差を見つけるための実用的且つ簡単な解決手段である。この差は、その接続線における使用された帯域幅を正しく決定するための重要な変数である。
【００１０】
理論的な到着時間が存在するウインドウの番号を容易に見つけるためには、理論的な到着時間におけるラップ・カウント手段の読みを使用することが可能である。
【００１１】
到着時間の記憶を保持するための実用的な解決方法は、第２到着時間におけるタイム・カウント手段の読み及び第１到着時間におけるタイム・カウント手段の読みを記憶することである。記憶位置がシフト・レジスタの形式で構成される時、新たなセルの到着時に、新しい到着時間の記憶は、その時まで第２到着時間であった前のセルの到着時間をその時の有効な第１到着時間に変換することを自動的に生じさせるであろう。この自動化は非常に簡単であり、従って多くの専用ロジックを必要としない。
【００１２】
ラップ・カウント手段の読みが決定される人為的な第２到着時間を生じさせるプロセスを、所定の反復周期をもって時間的に規則的な基準で開始させるために、状態決定手段が使用可能である。人為的な第２到着時間におけるラップ・カウント手段の読みは、理論的な到着時間におけるラップ・カウント手段の読みと共に、理論的な到着時間と人為的な第２到着時間との間でラップが生じたかどうかを決定するために使用可能である。これは、ラップ・カウント手段がそれ自体のラップを有する時に正しいセル処理を導くバックグラウンド・プロセスである。そのバックグラウンド・プロセスの結果は、理論的な到着時間が次の到着セルに対して有効であるか否かを表す有効性フラッグをセットするために使用可能である。
【００１３】
最高精度のセル速度決定プロセスを得るためには、バックグラウンド・プロセスの反復周期は、最大でも、タイム・カウント手段の２つのラップの間の時間とラップ・カウント手段の最大の読みマイナス２とを乗じた値を選択されなければならない。そこで、前のセルが到着したウインドウにおける１つの接続線に対して、又はそのウインドウの後のウインドウにおける１つの接続線に対してバックグラウンド・プロセスが適用された場合、同じ接続線に関して、バックグラウンド・プロセスは、遅くとも、ラップ・カウント手段がこれらのウインドウの番号の１つに再び到達する前に再び遂行されるということが保証される。従って、すべてのセル到着の状況が公平に扱われる。
【００１４】
人為的な第２到着時間が第１到着時間及び理論的な到着時間の１ラップ事象後にある場合、及び／又は、人為的な第２到着時間が第１到着時間及び理論的な到着時間の少なくとも２ラップ事象後に或いは第１到着時間及び理論的な到着時間の少なくとも１ラップ事象前にある場合、及び／又は、人為的な第２到着時間が第１到着時間の１ラップ事象後にある理論的な到着時間の少なくとも１ラップ事象後にある場合、ＴＡＴは最早有効ではないので次の到着セルの到着時間はそのＴＡＴと比較される必要がないというタイプの状況が生じている。従って、ＴＡＴは比較のために使用されないであろうということ、及び比較は遂行可能であるがそれの結果は使用されないであろうということを明瞭にするために、有効性フラッグがリセット可能である。第１到着時間、第２到着時間、及びＴＡＴの種々の状況の分類が、現在のケース・タイプを簡単に見つける単純なケース決定スキームに対する基礎を提供し、その結果は第２到着時間とＴＡＴとの比較が意味をなすか否かを判定するために使用可能である。上記のケースでは、比較は廃棄可能である。有効性フラッグはその結論に対する一種の１ビット・メモリとして働く。
【００１５】
第２到着セルの到着時に、有効性フラッグがそれの値に関してテスト可能である。それがリセットされている場合、第２到着セルはコンプライアントであると自動的に見なされる。この方法によって、第２到着セルのコンプライアンスは非常に容易に決定可能である。
【００１６】
第２到着セルの到着時に、理論的な到着時間及び第２到着時間の両方とも第１到着時間の１ラップ事象後にある場合、及び／又は、第２到着時間、第１到着時間、及び理論的な到着時間がすべて１つのラップ事象によって分離されていない場合、第２到着時間及び理論的な到着時間は、第２到着セルがコンプライアントであると見なされるか或いは非コンプライアントであると見なされるかを決定するために比較されるであろう。その比較は、リセット・キャリー・フラッグによって或いはキャリー・フラッグを使用することなく遂行される。キャリー・フラッグは、タイム・カウント手段がラップを有する時にセットされる。
【００１７】
第２到着セルの到着時に、理論的到着時間が第１到着時間及び第２到着時間の１ラップ事象後にある場合、第２到着時間及び理論的な到着時間は、第２到着セルがコンプライアントであると見なされるか或いは非コンプライアントであると見なされるかを判定するために比較されるであろう。従って、再び、キャリー・フラッグが使用されなければならない。このキャリー・フラッグは、セルが処理された時、即ち、それがそれのコンプライアンスを判定した時、いつもリセットされるであろう。
【００１８】
第２到着セルの到着時に、第２到着時間が第１到着時間及び理論的な到着時間の１ラップ事象後にある場合、及び／又は、第２到着時間が第１到着時間及び理論的な到着時間の少なくとも２ラップ事象後にあるか、又は第１到着時間及び理論的な到着時間の少なくとも１ラップ事象前にある場合、及び／又は、第２到着時間が第１到着時間の１ラップ事象後にある理論的な到着時間の少なくとも１ラップ事象後にある場合、第２到着セルをコンプライアントであると見なすことができる。再び、簡単なケース決定は、それが時間の状況を認識する場合におけるセル処理のプロセスを単純化する。このプロセスは、一方では、比較手順を使用するプロセスよりも速いし、もう一方では、誤処理の危険が減少するか又は全体的に回避されるので、公平である。
【００１９】
以下では、タイム・カウント手段と呼ばれるタイム・カウンタがラップを持つことなくカウントできる期間はウインドウと呼ばれる。
【００２０】
ラップの数をカウントするラップ・カウント手段（即ち、ウインドウ・カウント手段）が使用される。従って、実際のタイム・カウント手段の状態及びラップ・カウント手段の状態を使用することによって、現実の実時間が更に正確にモデル化可能である。しかし、ラップ・カウント手段も制限された範囲を有し、ラップはその結果として再び間違ったＧＣＲＡセル処理を生じさせるであろう。ラップ・カウント手段は、事実上、単なる延長されたタイム・カウント手段である。延長された時間は、次の期待されたセルに対する理論的な到着時間の有効性をテストすることでその状況を決定するバックグラウンド・プロセスを実行するために使用可能である。
【００２１】
これは、バックグラウンド・プロセスが各接続線に関するセルの到着を順次にシミュレートし、そしてＴＡＴの有効性を決定するが、実際のセルが到着した場合に遂行されるであろうＧＣＲＡプロセスを実行しないということによって達成される。
【００２２】
【発明の実施の形態】
以下では、本発明の種々の例示的な実施例が説明される。簡単にするために、以下の説明では、ＧＣＲＡの単純なケースが使用される。しかし、本発明の方法及び装置は完全なＧＣＲＡによっても機能する。
【００２３】
スイッチング・デバイスの入力には、幾つものセルが到着しつつある。セルは、本明細書においては、そのセルが向かっているターゲットに関する宛先情報及びターゲットに搬送されるべきペイロード情報を含む情報を持った固定長のパケットを意味する。スイッチング・デバイスは、到着するセルをそれらの宛先に送るためにそれの容量を制限されているので、単位時間当たりに入力において処理可能なセルの数も制限される。そのスイッチング・デバイスが処理し得る最大セル速度又はピーク・セル速度が定義される。最大セル速度はその入力、即ち、先行の接続線の割り当てられた帯域幅とも呼ばれる。到着するセルの数がその最大セル速度を超える場合、セルに関する情報を失う危険が存在する。従って、接続線に沿ってセルを送るユーザに、そのユーザが実際に使用した帯域幅がその割り当てられた帯域幅を超えること或いはそのセルが廃棄されることを信号するために使用可能な信号を作成するためには、入力におけるセル速度が監視される必要がある。監視機構として、２つの到着するセルの間の時間が測定され、到着相互間の最小期間であって、ピーク・セル速度から計算される期間に比較される。到着相互間の期間が最小期間よりも大きい場合、そのセルはコンプライアントであると見なされ、受け入れ可能である。そうでない場合、それは非コンプライアントであると見なされて廃棄されることがある。
【００２４】
セルが早く到着しすぎた場合、そのセルは、別の言葉で言えば、非コンプライアントであると見なされる。従って、第１セルが到着した時に開始されるタイム・フレームが設定される。このフレームは所定の長さ、即ち、到着相互間の期間Ｔという期間を有する。セルの到着時間はｔaである。第２セルのＴＡＴ（理論的な到着時間）は、コンプライアントであると見なされた第１セルの到着時間から、その第１セルの到着時間にＴＡＴを加えることによって計算される。即ち、
ＴＡＴ2＝ｔa1＋Ｔ
【００２５】
第２セルがこのタイム・フレーム［ｔa1，ＴＡＴ2］内に到着する場合、それは非コンプライアントであると見なされ、そうでない場合、それはコンプライアントであると見なされる。この判定プロセスは汎用セル速度アルゴリズム、即ち、ＧＣＲＡと呼ばれる。１つの接続線に対するセル処理プロセスの初期化のために、真の第１セルはいつもコンプライアントであると見なされる。それは、如何なる割り当てられた帯域幅も真の第１セルが超えることはないので、ある程度論理的である。
【００２６】
図１の（ａ）乃至（ｉ）には、スイッチの入力における種々の到着状況のタイム・スケジュールが示される。すべての状況に対して、次のパラメータは同じである。
【００２７】
時間は、制限されたカウント範囲を有するタイム・カウント手段によってカウントされる。各カウント・サイクルは０から開始し、そのタイム・カウント手段がラップを持つ時に終了する。カウント・サイクルはウインドウと呼ばれ、その後の順序ｋ、ｋ＋１、ｋ＋２等に番号付けられる。従って、すべてのウインドウが一定の等しい期間を有する。
【００２８】
第１セルは第１セル到着時間ｔa1に到着する。第２セルは第２セル到着時間ｔa2に到着する。
【００２９】
到着相互間の期間は、１ウインドウ期間よりも短いものとして定義される期間Ｔを有する。
【００３０】
第２セルに対する理論的な到着時間ＴＡＴ2は、第１セル到着時間ｔa1に到着相互間の期間Ｔを加えることによって計算される（ｔa1＋Ｔ＝ＴＡＴ2）。ここでは、及び以下の例では、第１セルはコンプライアントであると見なされるものと仮定する。従って、コンプライアンス判定後の第２セルに対する理論的な到着時間ＴＡＴ2の更新は、これらの例では、第１セル到着時間ｔa1に基づく。完全を期するためには、非コンプライアントの第１セルの場合、第２セルに対する理論的な到着時間ＴＡＴ2は上記の及び図２における式とは異なる式でもって計算されることを指摘しておく。図２の表を一般化するためには、ステップｔa1：＝ｔa2及びＴＡＴ2：＝ｔa1＋Ｔが汎用ステップ「ｕｐｄａｔｅ  ＴＡＴ  ｉｆ  ｃｃ」によって代用可能である。事実、第１セルがコンプライアントであると見なされなかった場合、それの先行セルの到着時間は、通常、理論的な到着時間ＴＡＴ2に対する基礎として働くであろう。ここで開示されるプロセスはこれらのケースに対しても機能する。
【００３１】
第１セル到着時間ｔa1は第２ウインドウｋ＋１の１ウインドウ前である第１ウインドウｋにあり、第２ウインドウｋ＋１は第３ウインドウｋ＋２の１ウインドウ前である。
【００３２】
図１の（ａ）において、第２セルに対する理論的な到着時間ＴＡＴ2は、第１ウインドウｋの１ラップ事象後にあるウインドウ、即ち、第２ウインドウｋ＋１内にある。第２セル到着時間ｔa2も第２ウインドウｋ＋１内にあり、しかも、第２セルに対する理論的な到着時間ＴＡＴ2よりも後でその第２ウインドウｋ＋１内にある。第２セルに対する理論的な到着時間ＴＡＴ2及び第２セル到着時間ｔa2は同じウインドウ内にあるので、タイム・カウント手段のラップはこれら２つの時点の間の比較を妨げるものではない。従って、ＧＣＲＡは正しい結果で終わる。第２セルに対する理論的な到着時間ＴＡＴ2は第２セル到着時間ｔa2よりも早いので、第２セルはコンプライアントであると見なされる。従って、第２セルは正しく処理される。この状況は、以下では、ケースＩａと呼ばれる。
【００３３】
図１の（ｂ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第２ウインドウｋ＋１内にある。第２セル到着時間ｔa2も第２ウインドウｋ＋１内にあり、第２セルに対する理論的な到着時間ＴＡＴ2よりも早い。第２セルに対する理論的な到着時間ＴＡＴ2及び第２到着時間ｔa2は同じウインドウ内にあるので、タイム・カウント手段のラップは比較されるべき両方の値に同じ程度に影響する。従って、これらの２つの時点の間の比較がラップ事象によって間違って扱われることはない。従って、ＧＣＲＡはいつも正しい結果で終わる。ここでは、第２セルに対する理論的な到着時間ＴＡＴ2は第２セル到着時間ｔa2よりも大きいので、第２セルは非コンプライアントであると見なされる。従って、第２セルは正しく処理される。この状況は、以下では、ケースＩｂと呼ばれる。
【００３４】
図１の（ｃ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第２ウインドウｋ＋１内にある。第２セル到着時間ｔa2は第１ウインドウｋ内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも早い。これは、第２セルが間違って扱われる代表的なケースである。第２セルに対する理論的な到着時間ＴＡＴ2の間、タイム・カウント手段はラップを持っていたので、第２セル到着時間ｔa2と第２セルに対するシフトした理論的な到着時間ＴＡＴ2′とが比較される。なお、そのシフトした理論的な到着時間ＴＡＴ2′は、１ウインドウ期間だけシフトバックした第２セルに対する理論的な到着時間ＴＡＴ2に対応する。このシフトは、第２セルに対する理論的な到着時間ＴＡＴ2が第２セル到着時間ｔa2よりも大きい、即ち、遅いけれども、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′が第２セル到着時間ｔa2よりも小さいということを生じさせる。ＧＣＲＡの結果、第２セルは、それが非コンプライアントであると見なされるべきであるけれども、コンプライアントであると見なされる。この状況は、以下では、ケースIIと呼ばれる。到着相互間の期間Ｔはいつも１ウインドウ期間よりも小さいので、シフトした理論的な到着時間ＴＡＴ2′が第２セル到着時間ｔa2よりも遅いというケースは起こり得ない。
【００３５】
図１の（ｄ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第１ウインドウｋ内にある。第２セル到着時間ｔa2は第２ウインドウｋ＋１内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。これは、第２セルが間違って扱われるもう１つのケースである。タイム・カウント手段は、第１セル到着時間ｔa1と第２セル到着時間ｔa2との間でラップを持っていたので、第２セル到着時間ｔa2と第２セルに対するシフトした理論的な到着時間ＴＡＴ2′とが比較される。なお、そのシフトした理論的な到着時間ＴＡＴ2′は、１ウインドウ期間だけ前方シフトした第２セルに対する理論的な到着時間ＴＡＴ2に対応する。このシフトは、第２セルに対する理論的な到着時間ＴＡＴ2が第２セル到着時間ｔa2よりも小さいけれども、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′が第２セル到着時間ｔa2よりも大きいということを生じさせる。ＧＣＲＡの結果、第２セルは、それがコンプライアントであると見なされなければならないけれども、非コンプライアントであると見なされる。この状況は、以下では、ケースIIIａと呼ばれる。
【００３６】
これと同様の状況が生ずるのは、第２セル到着時間ｔa2が第３ウインドウｋ＋２又はその後の任意のウインドウｋ＋ｎ（ｎ∈［３，∞］）内にあり、且つ、第２セル到着時間ｔa2が存在するウインドウへの第２セルに対する理論的な到着時間ＴＡＴ2のシフトが、第２セルに対する理論的な到着時間ＴＡＴ2は第２セル到着時間ｔa2よりも小さいけれども、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′は第２セル到着時間ｔa2よりも大きいということを生じさせる場合である。ＧＣＲＡの結果、第２セルは、それがコンプライアントであると見なされなければならないけれども、非コンプライアントであると見なされる。このケースは図１の（ｈ）に示される。
【００３７】
図１の（ｅ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第１ウインドウｋ内にある。第２セル到着時間ｔa2は第２ウインドウｋ＋１内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。第１セル到着時間ｔa1と第２セル到着時間ｔa2との間で、タイム・カウント手段がラップを持っていたので、第２セル到着時間ｔa2と第２セルに対するシフトした理論的な到着時間ＴＡＴ2′とが比較される。なお、そのシフトした理論的な到着時間は、１ウインドウ期間だけ前方シフトした第２セルに対する理論的な到着時間ＴＡＴ2に対応する。この特定なケースでは、第２セル到着時間ｔa2が第２セルに対する理論的な到着時間ＴＡＴ2よりも大きく、しかも、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′よりも大きい。第２セルは、それがコンプライアントでなければならないので、コンプライアントであると見なされる。従って、シフトはＧＣＲＡの結果に否定的な影響を与えるものではない。この状況は、以下では、ケースIIIｂと呼ばれる。
【００３８】
これと同様の状況が生ずるのは、第２セル到着時間ｔa2が第３ウインドウｋ＋２又はその後の任意のウインドウｋ＋ｎ（ｎ∈［３，∞］）内にあり、且つ、第２セル到着時間ｔa2が存在するウインドウへの第２セルに対する理論的な到着時間ＴＡＴ2のシフトが、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′が第２セル到着時間ｔa2よりも小さく、しかも、第２セルに対する理論的な到着時間ＴＡＴ2が第２セル到着時間ｔa2よりも小さいということを生じさせる場合である。ＧＣＲＡの結果、第２セルは間違いなくコンプライアントであると見なされる。本発明によるセルの扱いに関して、このケースはケースIIIｂとして分類可能である。
【００３９】
図１の（ｆ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第１ウインドウｋ内にある。第２セル到着時間ｔa2も第１ウインドウｋ内にあり、しかも第２セルに対する理論的な到着時間ＴＡＴ2よりも早い。第２セルに対する理論的な到着時間ＴＡＴ2及び第２セル到着時間ｔa2は同じウインドウ内にあるので、タイム・カウント手段のラップはこれらの２つの時点の間の比較を妨げるものではない。従って、ＧＣＲＡは正しい結果で終わる。第２セルに対する理論的な到着時間ＴＡＴ2は第２セル到着時間ｔa2よりも大きいので、第２セルは非コンプライアントであると見なされる。この状況は、以下では、ケースIVａと呼ばれる。
【００４０】
図１の（ｇ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第１ウインドウｋ内にある。第２セル到着時間ｔa2も第１ウインドウｋ内にあり、しかも第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。第２セルに対する理論的な到着時間ＴＡＴ2及び第２セル到着時間ｔa2は同じウインドウ内にあるので、タイム・カウント手段のラップはこれらの２つの時点の間の比較を妨げるものではない。従って、ＧＣＲＡは正しい結果で終わる。第２セルに対する理論的な到着時間ＴＡＴ2は第２セル到着時間ｔa2よりも小さいので、第２セルはコンプライアントであると見なされる。この状況は、以下では、ケースIVｂと呼ばれる。
【００４１】
図１の（ｈ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第１ウインドウｋ内にある。第２セル到着時間ｔa2は第３ウインドウｋ＋２内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。このケースは、図１の（ｄ）と関連して既に上述した。この状況は、以下では、ケースＶと呼ばれる。
【００４２】
図１の（ｉ）において、第２セルに対する理論的な到着時間ＴＡＴ2は第２ウインドウｋ＋１内にある。第２セル到着時間ｔa2は第３ウインドウｋ＋２内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。これは、第２セルが間違って処理されるもう１つのケースである。第１セル到着時間ｔa1及び第２セル到着時間ｔa2の間でタイム・カウント手段は２つのラップを持っていたので、第２セル到着時間ｔa2と第２セルに対するシフトした理論的な到着時間ＴＡＴ2′とが比較される。なお、そのシフトした理論的な到着時間ＴＡＴ2′は、１ウインドウ期間だけ前方シフトされた第２セルに対する理論的な到着時間ＴＡＴ2に対応する。このシフトは、第２セルに対する理論的な到着時間ＴＡＴ2が第２セル到着時間ｔa2よりも小さいけれども、シフトした理論的な到着時間ＴＡＴ2′が第２セル到着時間ｔa2よりも大きいということを生じさせる。ＧＣＲＡの結果、第２セルは、それがコンプライアントであると見なさなければならないけれども、非コンプライアントであると見なされる。この状況は、以下では、ケースVIと呼ばれる。
【００４３】
第２セルに対する理論的な到着時間ＴＡＴ2が第２ウインドウｋ＋１内にあり、且つ第２セル到着時間ｔa2がシフトした理論的な到着時間ＴＡＴ2′の後にあるという時のケースは示されない。このケースでは、第２セル到着時間ｔa2は第３ウインドウｋ＋２内にあり、従って、第２セルに対する理論的な到着時間ＴＡＴ2よりも遅い。第１セル到着時間ｔa1及び第２セル到着時間ｔa2の間でタイム・カウント手段は２つのラップを持っていたので、第２セル到着時間ｔa2と第２セルに対するシフトした理論的な到着時間ＴＡＴ2′とが比較される。なお、そのシフトした理論的な到着時間ＴＡＴ2′は、２ウインドウ期間だけ前方シフトされた第２セルに対する理論的な到着時間ＴＡＴ2に対応する。第２セル到着時間ｔa2は、第２セルに対するシフトした理論的な到着時間ＴＡＴ2′がその第２セル到着時間ｔa2よりも小さくなるように、及び理論的な到着時間ＴＡＴ2がその第２セル到着時間ｔa2よりも小さくなるように存在する。ＧＣＲＡの結果、第２セルは、それがコンプライアントであると見なされなければならない時にコンプライアントであると見なされる。本発明によるセルの処理に対して、このケースは、ケースIIIｂの下に分類可能である。
【００４４】
上記の概要からも明らかであるように、セルが誤処理されるケースが存在する。そのような誤処理は、これらのセルを送っているユーザへの間違った信号伝達及び正しくない廃棄／受入れ行為を導く。セルが廃棄されるべきであるけれども、受け入れられる場合、ユーザは、自分が持つべき及び支払う帯域幅よりも大きい帯域幅を許容される。これは、更に、他の正しく動作している接続線におけるセル喪失を導くことがあるスイッチ・エレメントの過負荷を導く。一方、セルが、受け入れられるべきであるけれども、廃棄される場合、正しく行動しているユーザからのセルが間違って廃棄され、そのユーザは、高すぎる帯域幅を使用したかのように処理され、割り振られた帯域幅を超えたために追加のコストを課せられることもある。
【００４５】
図２には、到着セルを処理するために実行されるべき主な機能を示すクロス・チャートが示される。その内容に関しては、図３の説明の後に説明する。
【００４６】
図３には、前述の原理に従って到着セルを処理するのに適した装置の構成が示される。
【００４７】
第１到着セル１５は接続線１８を介して到来し、第１判定手段１３を介してスイッチング・デバイス１の入力１７に向かう。それは第２到着セル１２によって後続されるべきものである。本明細書では、「第１」及び「第２」到着セル１２、１５は、専ら、接続線１８における真の第１到着セル１５及び第２到着セル１２を意味するものではなく、１つのセルが他のセルに後続する任意ペアのセルを意味する。
【００４８】
接続線１８は、タイム・カウント手段２、第１判定手段１３、及びラップ・カウント手段３に接続される。第１判定手段１３は、入力１７に接続された出力を有する。タイム・カウント手段２は、ラップ・カウント手段３及び第１比較手段４に第１出力を接続され、時間計算手段６並びに第１比較手段４及び第１決定手段７に並列に第２出力を接続され、状態決定手段１４から来る入力を有する。時間計算手段６は１つの出力を第１比較手段４に接続される。第１比較手段４は時間計算手段６の入力に接続された出力も有する。ラップ・カウント手段３は第１決定手段７への接続線を有し、第１決定手段７は第２決定手段５に接続される。第１比較手段４は第２決定手段５から１つの線を受け、一方、状態決定手段１４からもう１つの線を受ける。ラップ・カウント手段３と直列に、第１メモリ手段８及び第２メモリ手段９が配列され、それらの各々は第２比較手段１０に事前配列される。第２比較手段１０の唯一の出力が第２決定手段５に接続される。有効性フラッグ・メモリ手段１１及び第１比較手段４の間には、２つの反方向線が配列される。第１比較手段４は、第１判定手段１３に通じる出力線を有する。到着相互間の期間メモリ手段１６が第１決定手段７に、更に時間計算手段６にも接続される。
【００４９】
第１到着セル１５の到着は、その第１到着セル１５の到着時間ｔa1を読み取るタイム・カウント手段２における処理をトリガし、それの値を時間計算手段６及び第１比較手段４に配送する。到着相互間の期間メモリ手段１６には、到着相互間の期間Ｔに対する所定の値が記憶されており、時間計算手段６に配送される。時間計算手段６では、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が、到着相互間の期間メモリ手段１６からの到着相互間の期間Ｔを第１到着セル１５の到着時間ｔa1に加えることによって計算される。しかし、第２到着セルに対する計算された理論的な到着時間ＴＡＴ2は、第１比較手段４に接続された出力には未だ与えられない。
【００５０】
第１到着セル１５が第１比較手段４における前の到着時間ｔa0を持った前の到着セルのその後のセルであると仮定すると、前の到着セルの到着時間ｔa0から計算された第１到着セル１５の理論的な到着時間ＴＡＴ1が、そこで遂行されるべきアクション、即ち、第１到着セル１５の到着時間ｔa1と第１到着セル１５の理論的な到着時間ＴＡＴ1との比較のために使用される。同様に、第１比較手段４において、第２セル１２の理論的到着時間ＴＡＴ2が第２到着セル１２の到着時間ｔa2と比較されるであろう。接続線１８における真の第１セルに対して、理論的な到着時間ＴＡＴ値はゼロでもって初期化されるであろう。
【００５１】
ラップ・カウント手段３のカウンタは、タイム・カウント手段２の各ラップによってインクレメントされ、従って、ラップ・カウント手段３のカウンタ状態はタイム・カウント手段２のラップの数を反映する。タイム・カウント手段２がラップを有する度に、キャリー・フラッグｃは、それが未だセットされていなかった場合にセットされる。
【００５２】
ラップの数は現在のウインドウの番号を表しており、それが第１決定手段７に対する入力として使用されるラップ・カウント手段３の出力に現れる。ラップ・カウント手段３は、現在のカウンタ状態を第１メモリ手段８及び第１決定手段７に転送するように第１到着セル１５の到着によってトリガされる。従って、第１メモリ手段８の内容は、第１到着セル１５が到着したウインドウの番号を表す。次のセル、即ち、第２到着セルが到着しつつある時、第１メモリ手段８の内容は第２メモリ手段９にシフトされるので、それの内容は、前のセル、即ち、第１到着セル１５が到着したウインドウの番号を表す。ラップ・カウント手段３の現在のカウンタ状態は、第１到着セル１５の到着の際にも、第１決定手段７に転送される。従って、第１決定手段７も、第１到着セル１５が到着したウインドウの番号を得る。
【００５３】
第１到着セル１５の第１到着時間ｔa1及び到着相互間の期間Ｔは、第１決定手段７に対する入力として使用される。第１決定手段７では、これらの入力及びラップ・カウント手段３の転送されたカウンタ状態から、次のセル、即ち、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が存在するウインドウの番号が計算される。第１到着セル１５の到着時間ｔa1及び到着相互間の期間Ｔの和がタイム・カウント手段２の１カウンタ・サイクルよりも大きい場合、第２到着セルに対する理論的な到着時間ＴＡＴ2は、ラップ・カウント手段３の転送されたカウンタ状態によって表されたウインドウの後のウインドウ内にある。そうでない場合、それは、ラップ・カウント手段３の転送されたカウンタ状態によって表されたウインドウ内にある。
【００５４】
第２比較手段１０において、第１メモリ手段８の内容と第２メモリ手段９の内容との間の最終的な差が算定され、第１到着セル１５のウインドウに関連したどのウインドウに到着した次のセル、即ち、第２到着セルが存在するかということはそこから明らかである。
【００５５】
第２決定手段５において、図１の（ａ）乃至（ｉ）に示されたようなＩ、II、III、IV、Ｖ、又は、VIと呼ばれるケース・タイプを見つけるために、第１決定手段７からの情報及び第２比較手段１０からの情報が結合される。このテストの結果は、有効性フラッグ・メモリ手段１１からの有効性フラッグｖを更に使用する第１比較手段４に転送され、第１比較手段４によって遂行されるべきアクションのタイプを決定する。そこで、そのアクションはセルの受け入れ又はセルの廃棄を生じさせるであろう。真の第１セルの到着の場合、有効性フラッグｖは値１でもって初期化される。それは、真の第１セルに対して使用されるべき理論的な到着時間ＴＡＴが有効であること、及びその真の第１セルの到着時間ｔaとそのセルに対する理論的な到着時間ＴＡＴとの比較が正しいものと見なすことができることを意味する。第１比較手段４における比較プロセスの結果はフラッグとして第１判定手段１３に転送される。そのフラッグは、第１到着セル１５をスイッチング・デバイス１に送らせるか又はそのセルを削除するゲートとして働く。ケース・タイプ及び有効性フラッグｖ次第で、第１到着セル１５は、非コンプライアントであると見なされるか又はコンプライアントであると見なされる。
【００５６】
そのアクションの後、ケース・タイプに従って、有効性フラッグｖは第１比較手段４によってセット又はリセットされる。更に、第２到着セル１２に対する理論的な到着時間ＴＡＴ2の計算された値が時間計算手段６から第１比較手段４に転送される。この転送は、第１比較手段４から時間計算手段６に与えられるイネーブル信号を介して処理される。
【００５７】
上記のセル処理プロセスは第１到着セル１５を介して開始可能であるのみならず、実際にはセルは到着していないがセルの到着をシミュレートするという点でそのセル処理プロセスを時間的に規則的な基準で開始される状態決定手段１４を介しても開始可能である。状態決定手段１４によって開始したセル処理プロセスは、ここでは、バックグラウンド・プロセスと呼ばれる。バックグラウンド・プロセスは、セル処理は行われないがケース・タイプの評価及びそれに依存する有効性フラッグｖ又はキャリー・フラッグｃの更新が行われるという点で、非バックグラウンド・プロセス（真のセル処理プロセス）とは異なる。従って、バックグラウンド・プロセスは、人為的な第２到着時間ｔa2を作成するプロセスを開始させる。
【００５８】
状態決定手段１４は、現在実行中のプロセスが真のセル処理プロセスであるか又はバックグラウンド・プロセスであるかを決定する。そのプロセス・タイプは第１比較手段４に信号される。
【００５９】
そこで、第１比較手段４では、図２に示されたアクションが遂行される。
【００６０】
ここでは、再び、第１到着セル１５が到着したウインドウは第１ウインドウｋと呼ばれ、それに続くウインドウは第２ウインドウｋ＋１と呼ばれ、次のウインドウは第３ウインドウｋ＋２と呼ばれる等々である。
【００６１】
セル処理プロセスの説明に関して、有効性フラッグｖは最初に１にセットされるものと先ず仮定する。
【００６２】
ケースＩは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第２ウインドウｋ＋１内にあり、その第２到着セル１２の到着時間ｔa2も第２ウインドウｋ＋１内にある時のケースである。これは、キャリー・フラッグｃが比較のために使用される必要がないことを意味する。従って、それはここで最初に０にリセットされそして比較において使用されるが、１にセットされたままにされそして比較においては無視され、その後、０にリセットされることも可能である。セル到着（ｃａ）の時、有効性フラッグｖがテストされ、そして１にセットされていることがわかる。次に、ここでは０であるキャリー・フラッグｃを使用して、第２到着セル１２に対する理論的な到着時間ＴＡＴ2及びその第２到着セル１２の到着時間ｔa2の間の比較が行われる。第２到着セル１２の到着時間ｔa2が第２到着セル１２に対する理論的な到着時間ＴＡＴ2よりも遅い場合、サブケースＩａが存在し、第２到着セル１２はコンプライアント・セル（ｃｃ）であると見なされるであろう。その後、有効性フラッグは１にセットされ、第１比較手段４からのイネーブル信号は、第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。第２到着セル１２の到着時間ｔa2が第２到着セル１２に対する理論的な到着時間ＴＡＴ2よりも早い場合、サブケースＩｂが存在し、第２到着セル１２は非コンプライアント・セルであると見なされるであろう。有効性フラッグｖは任意のサブケースＩａ、Ｉｂにあり、その後、１にセットされるように更新され、第１比較手段４からのイネーブル信号は、第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ことを生じさせる。
【００６３】
ケースIIは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第２ウインドウｋ＋１内にあり、その第２到着セル１２の到着時間ｔa2は第１ウインドウｋ内にある時のケースである。このケースでは、第２到着セル１２がいつも非コンプライアントであることは明らかである。ここでは１にセットされているキャリー・フラッグｃを使用することは、その結果としてＴＡＴ2＞ｔa2という正しい比較を生じる。これは、キャリー・フラッグｃがその比較のために使用されなければならず、０にセットされないであろうということを意味する。セル到着（ｃａ）の時、有効性フラッグｖがテストされ、セットされていることがわかる。次に、ここでは１にセットされているキャリー・フラッグｃを使用して、第２到着セル１２に対する理論的な到着時間ＴＡＴ2及びその第２到着セル１２の到着時間ｔa2の間の比較が行われる。ここでは、第２到着セル１２の到着時間ｔa2が第２到着セル１２に対する理論的な到着時間ＴＡＴ2よりもいつも早く、第２到着セル１２は非コンプライアント・セルであると見なされるであろう。その後、有効性フラッグｖは１にセットされ、第１比較手段４からのイネーブル信号は、第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。更に、キャリー・フラッグｃは、最終的には０にリセットされる。
【００６４】
ケースIIIは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第１ウインドウｋ内にあり、その第２到着セルの到着時間ｔa2が第２ウインドウｋ＋１内にある時のケースである。このケースでは、第２到着セル１２がいつもコンプライアントであることは明らかである。比較が行われる必要はない。有効性フラッグｖ＝１又は有効性フラッグｖ＝０の何れの場合も、第２到着セル１２はコンプライアントであると見なされるので、有効性フラッグｖのステータスに関するテストが行われる必要はない。セル到着（ｃａ）時に、第２到着セル１２は直接にコンプライアント・セルであると見なされるであろう。その後、有効性フラッグｖは更新され、即ち、１にセットされ、第１比較手段４からのイネーブル信号は、その第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。
【００６５】
ケースIVは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第１ウインドウｋ内にあり且つその第２到着セルの到着時間ｔa2も第１ウインドウｋ内にある時のケースである。これは、ラップが生じなかったためにキャリー・フラッグｃがセットされていないことを意味する。キャリー・フラッグｃは比較のために使用可能であり、何の影響も生じない。セル到着（ｃａ）時に、有効性フラッグｖはテストされ、１にセットされていることがわかる。次に、ここでは０にセットされているキャリー・フラッグｃを使用して、第２到着セル１２に対する理論的な到着時間ＴＡＴ2とその第２到着セルの到着時間ｔa2との間の比較が行われる。第２到着セルの到着時間ｔa2が第２到着セル１２に対する理論的な到着時間ＴＡＴ2よりも遅い場合、サブケースIVｂが存在し、第２到着セル１２はコンプライアント・セル（ｃｃ）であると見なされるであろう。その後、有効性フラッグｖは１にセットされ、第１比較手段４からのイネーブル信号は、その第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。第２到着セルの到着時間ｔa2がその第２到着セル１２に対する理論的な到着時間ＴＡＴ2よりも早い場合、サブケースIVａが存在し、第２到着セル１２は非コンプライアント・セルであると見なされるであろう。その後、有効性フラッグｖは１にセットされ、第１比較手段４からのイネーブル信号は、その第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。
【００６６】
ケースＶは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第１ウインドウｋ内にあり、その第２到着セルの到着時間ｔa2が第３ウインドウｋ＋２内に又はその後のウインドウｋ＋３、４・・・内にある時のケースである。このケースでは、第２到着セル１２がいつもコンプライアントであることは明らかである。比較が行われる必要はない。有効性フラッグｖ＝１又は有効性フラッグｖ＝０の何れの場合も、第２到着セル１２はコンプライアントであると見なされるので、有効性フラッグｖのステータスに関するテストは行われる必要がない。セル到着（ｃａ）時に、第２到着セル１２は直接にコンプライアント・セルであると見なされるであろう。その後、有効性フラッグｖは１にセットされ、第１比較手段４からのイネーブル信号は、その第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。
【００６７】
ケースVIは、第２到着セル１２に対する理論的な到着時間ＴＡＴ2が第２ウインドウｋ＋１内にあり、その第２到着セルの到着時間ｔa2が第３ウインドウｋ＋２内に又はその後のウインドウｋ＋３、４・・・内にある時のケースである。このケースはケースＶと同じである。即ち、第２到着セル１２はいつもコンプライアントである。比較が行われる必要はない。有効性フラッグｖ＝１又は有効性フラッグｖ＝０の何れの場合も、第２到着セル１２はコンプライアントであると見なされるので、有効性フラッグｖのステータスに関するテストは行われる必要がない。セル到着（ｃａ）時に、第２到着セル１２は直接にコンプライアント・セルであると見なされるであろう。その後、有効性フラッグｖは１にセットされ、第１比較手段４からのイネーブル信号は、その第１比較手段４における比較のために使用される理論的な到着時間ＴＡＴ2が到着すべき次のセルのために更新される（ｔa1：＝ｔa2；ＴＡＴ2＝ｔa1＋Ｔ）ということを生じさせる。
【００６８】
従って、或るケースでは、比較のためにキャリー・フラッグｃが使用される。このフラッグは、理論的な到着時間ＴＡＴ2と第２到着セルの到着時間ｔa2との間の最終的なラップがそれらの比較において考慮され、従ってそれらの相互の位置の誤った解釈が排除されるということを生じさせる。
【００６９】
ラップ・カウント手段３のラップが生じない限り、上記のアクションは結果として正しいセル処理を生じる。それは、ラップ・カウント手段３の値が時間と共に増加するためである。しかし、ラップ・カウント手段３がラップを持つ場合、次のセルは時間的にずっと遅れて到着したけれども、前のセルが到着したウインドウの番号よりも小さい専用のウインドウの番号を有するウインドウ内に次のセルが到着するという状況が生じ得る。
【００７０】
従って、バックグラウンド・プロセスは最小の反復率で、即ち、最大の反復周期ＴＲで行われる。バックグラウンド・プロセスの２つの開始相互間の期間は、ラップ・カウント手段３のカウント周期の時間、即ち、ラップ・カウント手段３の２つのラップの間の時間よりも少なくとも２つのウインドウの期間だけ小さいものでなければならない。時間的な規則性は一定の周期性を持つ必要がないが、それが、ラップ・カウント手段３のラップなしにカウント可能であるウインドウの最大数よりも２つのウインドウだけ小さいという上記の制限を超えない限り、時間を変更することができることは明らかである。
【００７１】
バックグラウンド・プロセスが開始される時、次のようなアクションが遂行され、それによって、人為的な第２到着時間ｔa2が、恰も真の到着セルの第２到着時間ｔa2であるかのように使用される。
【００７２】
ケースIIIでは、有効性フラッグｖはゼロにリセットされる。これは、第２到着セル１２に関して、理論的な到着時間ＴＡＴ2がいつもそれの到着時間ｔa2よりも早いため、次のケースＩ−VIのいずれにおいても、第２到着セル１２は正しいコンプライアントであると見なされるであろうということを意味する。
【００７３】
ケースＶでは、有効性フラッグｖはゼロにリセットされる。これは、第２到着セル１２に関して、理論的な到着時間ＴＡＴ2がいつもそれの到着時間ｔa2よりも早いため、次のケースＩ−VIのいずれにおいても、第２到着セル１２は正しいコンプライアントであると見なされるであろうということを意味する。
【００７４】
ケースVIでは、有効性フラッグｖはゼロにリセットされる。これは、第２到着セル１２に関して、理論的な到着時間ＴＡＴ2はいつもそれの到着時間ｔa2よりも早いため、次のケースＩ−VIのいずれにおいても、第２到着セル１２は正しいコンプライアントであると見なされるであろうということを意味する。
【００７５】
ケースＩでは、キャリー・フラッグｃはゼロにリセットされる。理論的な到着時間ＴＡＴ2は同じウインドウ内にあり、そのウインドウにおいてバックグラウンド・プロセスが生じる。理論的な到着時間ＴＡＴ2の有効性は、バックグラウンド・プロセスが遂行される時点では陳腐化されない。第２到着セル１２は、依然として同じウインドウに到着することができ、従って、有効な理論的な到着時間ＴＡＴ2と比較されなければならない。第２到着セル１２に対する理論的な到着時間ＴＡＴ2の正しい評価のためには、その第２到着セル１２がラップ・カウント手段３のラップ後に、しかも、第１到着セル１５である前のセルが到着したウインドウが持っている番号と同じ番号を持っているウインドウに又はその後の１つのウインドウに到着する場合、もう一度バックグラウンド・プロセスが遂行されなければならない。従って、再び遂行されるべきバックグラウンド・プロセスに対する最新の時点は、第１到着セル１５が到着したウインドウが持っている番号と同じ番号を有するウインドウを先行するウインドウ内にある。第２到着セル１２が第２ウインドウｋ＋１よりも遅い又は第１ウインドウｋの前にある任意のウインドウにおいて到着する場合、それはコンプライアントであると見なされるであろう。従って、これはケースVIである。第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウにおいて又はその１つ後のウインドウにおいて第２到着セル１２が到着する場合、バックグラウンド・プロセスはケースVIに対して既に遂行されており、その結果、有効性フラッグｖ＝０のリセットを生じさせ、セル到着時にコンプライアントであると見なすという結果を生じさせるであろう。キャリー・フラッグｃは０にリセットされるので、理論的な到着時間ＴＡＴ2が存在する第２ウインドウｋ＋１に第２到着セル１２が到着する時のケースでは、正しいＧＣＲＡが遂行される。
【００７６】
ケースIIでは、バックグラウンド・プロセスによって何も行われない。理論的な到着時間ＴＡＴ2は、バックグラウンド・プロセスが生じるウインドウよりも１つ後のウインドウにある。理論的な到着時間ＴＡＴ2の有効性はその時点では陳腐化されない。次の第２到着セル１２は依然として同じウインドウ又は次のウインドウに到着できるであろうし、従って、有効な理論的な到着時間ＴＡＴ2と比較されなければならない。次の第２到着セル１２に対する理論的な到着時間ＴＡＴ2の有効性の正しい評価のために、その第２到着セル１２がラップ・カウント手段３のラップの後で且つ前のセルである第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウ又は１つ後のウインドウに到着した場合、その時には、遅くとも、第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウの前のウインドウ内である時間に、もう一度、バックグラウンド・プロセスが遂行されなければならない。一定のバックグラウンド・プロセスの周期性のために、最新のウインドウは、第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウの２つ前のウインドウとなるように選択されるであろう。第２ウインドウｋ＋１よりも遅いか又は第１ウインドウｋの前にある任意のウインドウに次の第２到着セル１２が到着する場合、それはコンプライアントであると見なされるであろう。従って、これは再びケースVIである。前の第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウ又はその１つ後のウインドウに次の第２到着セル１２が到着した場合、バックグラウンド・プロセスがケースVIに対して既に遂行されており、その結果、有効性フラッグｖ＝０のリセットを生じさせ、セル到着時にコンプライアントであると見なす結果を生じるであろう。ケースIIでは、キャリー・フラッグｃは依然として０であるので、次の第２到着セル１２が理論的な到着時間ＴＡＴ2に存在する第２ウインドウｋ＋１又は先行の第１ウインドウｋに到着する場合、正しいＧＣＲＡが遂行される。
【００７７】
ケースIVでは、バックグラウンド・プロセスによって何も行われない。理論的な到着時間ＴＡＴ2は、バックグラウンド・プロセスが生じるウインドウと同じウインドウにある。理論的な到着時間ＴＡＴ2の有効性はその時点では陳腐化されない。次の第２到着セル１２は依然として同じウインドウ又は次のウインドウに到着できるであろうし、従って、有効な理論的な到着時間ＴＡＴ2と比較されなければならない。次の第２到着セル１２に対する理論的な到着時間ＴＡＴ2の有効性に関する正しい評価のために、その第２到着セル１２がラップ・カウント手段３のラップの後に且つ前の第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウ又は１つ後のウインドウに到着した場合、遅くとも、第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウの前のウインドウにおける時間に、もう一度、バックグラウンド・プロセスが遂行されなければならない。一定のバックグラウンド・プロセスの周期性のために、第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウの２つ前のウインドウとなるように最新のウインドウが選択されるであろう。第２ウインドウｋ＋１よりも遅いか又は第１ウインドウｋの前にある任意のウインドウに次の第２セル１２が到着する場合、それはコンプライアントであると見なされるであろう。従って、これはケースＶである。前の第１到着セル１５が到着したウインドウが有する番号と同じ番号を有するウインドウ又は１つ後のウインドウに次の第２セル１２が到着した場合、バックグラウンド・プロセスがケースＶに対して既に遂行されており、その結果、有効性フラッグｖ＝０のリセットを生じさせ、セル到着時にコンプライアントであると見なす結果を生じるであろう。ケースIVでは、キャリー・フラッグｃは依然として０であるので、次の第２到着セル１２が、理論的な到着時間ＴＡＴ2にある第２ウインドウｋ＋１又は先行の第１ウインドウｋに到着する場合、正しいＧＣＲＡが遂行される。
【００７８】
ラップ・カウント手段（３）も制限されたカウント範囲を有するので、第１到着時間ｔa1が存在するウインドウよりも低い番号を有するウインドウ内に第２到着時間ｔa2が存在するというケースが起こり得る。図２において、このケースはケースＶ及びVIと一体化される。それは、その結果生じる手順が同じであるためである。ラップ・カウント手段３のラップが生じてこの状況を導いたに違いないことは明らかであるので、第２到着セル１２はコンプライアントであると見なされるであろう。従って、バックグラウンド・プロセスは、遅くとも、第１到着時間ｔa1が存在するウインドウの番号の直前の番号を有するウインドウにおいて生じることが可能である。
【００７９】
第１比較手段４における判定プロセスは、到着時間ｔaが第１比較手段４において更新される度に遂行される次のようなプログラム・ステップの形で実現可能である。
【００８０】
0003722376.tif 000002
【００８１】
ラップ・カウント手段３のサイズ、即ち、それの最大の読みは、状態決定手段１４がすべての現在の接続線に関してラップ・カウント手段３の１サイクルにおいて、少なくともそれの最小反復率で、即ち、最大反復周期でバックグラウンド・プロセスを遂行するのに十分な時間を有する時、理想的に選択される。そのサイズをできるだけ小さく選択することは、勿論、ラップ・カウント手段３のための必要なチップ・エリアをできるだけ小さく保つであろうし、従って、必要とされる総チップ・エリアを減少させ、それに伴いその装置の価格を減少させるであろう。
【００８２】
接続線におけるセル・トラフィックが或る最小値及び或る一様性の条件を満たす場合、バックグラウンド・プロセスがその接続線に関して廃棄可能であることは留意すべきことである。例えば、その接続線における２つのセルの間の最大の到着相互間時間がラップ・カウント手段３の半減した最大の読みを乗じたウインドウの期間よりも小さい場合、バックグラウンド・プロセスは陳腐なものになる。別の言葉で言えば、ラップ・カウント手段３の１つのラップ後の第３ウインドウｋ＋２の始めと第１ウインドウｋの始めとの間の時間に、少なくとも第２セル１２が到着しようとする時、バックグラウンド・プロセスは必要ない。
【００８３】
一般に、セルがコンプライアントであると見なれるか又は非コンプライアントであると見なされるかの結果次第で、非コンプライアント・セルを廃棄すること及びコンプライアント・セルを受け入れることが最も論理的なアクションである。この行為は前述の実施例において使用された。しかし、セル処理の判定に影響し得る更なる局面、並びに、或る非コンプライアント・セルが受け入れられる更に一般的なセル受け入れ、又は或るコンプライアント・セルが廃棄される更に制限的なセル受け入れを導き得る更なる局面が存在し得る。いずれの場合も、これらのセル処理ルーチンは正確なセル・コンプライアンス決定に大きく依存している。スイッチング・デバイスとしてＡＴＭスイッチが使用されることが望ましく、その場合、セルはＡＴＭセルである。
【図面の簡単な説明】
【図１】図１の（ａ）乃至（ｉ）は、スイッチの入力ポートにおけるセルの種々の到着状況のタイム・スケジュールである。
【図２】図２は、図１の（ａ）乃至（ｉ）の状況において実行されるべき種々のステップを持ったクロス・チャートである。
【図３】図３は、スイッチの入力ポートにおけるセルのコンプライアンスを判定するための装置のブロック図である。
【図１】
0003722376.tif 000003
【図２】
0003722376.tif 000004
【図３】
0003722376.tif 000005