JPH0720124B2 - データチャンネルのスケジューリング装置及び方法 - Google Patents
データチャンネルのスケジューリング装置及び方法Info
- Publication number
- JPH0720124B2 JPH0720124B2 JP3351198A JP35119891A JPH0720124B2 JP H0720124 B2 JPH0720124 B2 JP H0720124B2 JP 3351198 A JP3351198 A JP 3351198A JP 35119891 A JP35119891 A JP 35119891A JP H0720124 B2 JPH0720124 B2 JP H0720124B2
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- cycle
- data
- channel
- packet
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
- H04L49/901—Buffering arrangements using storage descriptor, e.g. read or write pointers
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/62—Queue scheduling characterised by scheduling criteria
- H04L47/6215—Individual queue per QOS, rate or priority
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/62—Queue scheduling characterised by scheduling criteria
- H04L47/622—Queue service order
- H04L47/6225—Fixed service order, e.g. Round Robin
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
- H04L49/9036—Common buffer combined with individual queues
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
- H04L49/9057—Arrangements for supporting packet reassembly or resequencing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
- H04L49/9063—Intermediate storage in different physical parts of a node or terminal
- H04L49/9078—Intermediate storage in different physical parts of a node or terminal using an external memory or storage device
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Small-Scale Networks (AREA)
- Mobile Radio Communication Systems (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、スロット化されたパケ
ットデータシステムへのデータデバイスのアクセスを行
うためのスケジューリング装置及び方法に関する。
ットデータシステムへのデータデバイスのアクセスを行
うためのスケジューリング装置及び方法に関する。
【０００２】
【従来の技術】複数のデータデバイス（端末、計算機、
データ幹線など）がデータ資源（ネットワーク、バス、
データ幹線など）へのアクセス要求をする場合、アクセ
ス競合を解決するためにスケジューリング法が必要であ
る。そのような資源を分配して良いサービスを行うこと
は、適切なスケジューリング法と密に関係している。
データ幹線など）がデータ資源（ネットワーク、バス、
データ幹線など）へのアクセス要求をする場合、アクセ
ス競合を解決するためにスケジューリング法が必要であ
る。そのような資源を分配して良いサービスを行うこと
は、適切なスケジューリング法と密に関係している。
【０００３】ファーストカム・ファーストサービスと呼
ばれるスケジューリング法の一つのタイプは、受け取っ
た順にアクセス要求を行列に入れて競合解消をする。ヘ
ッドオブザライン・ラウンドロビンと呼ばれる他のタイ
プのスケジューリング法は、各チャンネルに行列を用意
し、チャンネルへ到着した未処理のデータサービス要求
を行列に入れながら、一つ以上のサービスを時分割でこ
なしていく。
ばれるスケジューリング法の一つのタイプは、受け取っ
た順にアクセス要求を行列に入れて競合解消をする。ヘ
ッドオブザライン・ラウンドロビンと呼ばれる他のタイ
プのスケジューリング法は、各チャンネルに行列を用意
し、チャンネルへ到着した未処理のデータサービス要求
を行列に入れながら、一つ以上のサービスを時分割でこ
なしていく。
【０００４】
【発明が解決しようとする課題】各データサービスに同
等の優先度が与えられる均等ネットワークにおいては、
スケジューリング法はこれらのデータサービスを公正に
扱うべきである。各データサービスが異なる優先度を持
つ非均等ネットワークにおいては、スケジューリング法
の公正さの達成はより難しくなる。スケジューリング法
が適切であるためには、資源に関するデータサービスの
優先度のクラスに従って異なった扱いをするとともに、
各優先度クラス内の全てのデータサービスを公正に扱う
ことが要求される。
等の優先度が与えられる均等ネットワークにおいては、
スケジューリング法はこれらのデータサービスを公正に
扱うべきである。各データサービスが異なる優先度を持
つ非均等ネットワークにおいては、スケジューリング法
の公正さの達成はより難しくなる。スケジューリング法
が適切であるためには、資源に関するデータサービスの
優先度のクラスに従って異なった扱いをするとともに、
各優先度クラス内の全てのデータサービスを公正に扱う
ことが要求される。
【０００５】このような要求があるため、従来のファー
ストカム・ファーストサービスのスケジューリング法に
は公正なオペレーションをしないという欠点があり、一
方ラウンドロビンスケジューリング法は複雑かつ大容量
メモリの使用を必要とするという欠点がある。
ストカム・ファーストサービスのスケジューリング法に
は公正なオペレーションをしないという欠点があり、一
方ラウンドロビンスケジューリング法は複雑かつ大容量
メモリの使用を必要とするという欠点がある。
【０００６】本発明は、データサービスの優先度による
公正なオペレーションを行い、かつ大規模な計算資源を
必要としないスケジューリング装置及び方法の提供を目
的とする。
公正なオペレーションを行い、かつ大規模な計算資源を
必要としないスケジューリング装置及び方法の提供を目
的とする。
【０００７】
【課題を解決するための手段】本発明では、各データバ
ッチの一つまたは二つ以上のデータパケットを認識する
情報が、複数（Ｎ個）のサイクル行列のうちの一つまた
は二つ以上のサイクル行列中へソートされる。このソー
トは、各データバッチについて、特定のチャンネルから
の予め決められた数（Ｐ）以上のデータパケットを認識
する情報が各サイクル行列に入力されないように行われ
る。認識されたデータパケットを通信施設線へ出力する
ことによって、各サイクル行列は空にするように周期的
にサービスされる。
ッチの一つまたは二つ以上のデータパケットを認識する
情報が、複数（Ｎ個）のサイクル行列のうちの一つまた
は二つ以上のサイクル行列中へソートされる。このソー
トは、各データバッチについて、特定のチャンネルから
の予め決められた数（Ｐ）以上のデータパケットを認識
する情報が各サイクル行列に入力されないように行われ
る。認識されたデータパケットを通信施設線へ出力する
ことによって、各サイクル行列は空にするように周期的
にサービスされる。
【０００８】各サイクル行列が飽和した後（すなわち、
全てのサイクル行列が満杯になった後、あるいは各サイ
クル行列が特定のチャンネルからのＰ個のデータパケッ
トを認識する情報を含んだ後）、情報はオーバーフロー
行列へソートされる。その後、特定のチャンネルからの
Ｐ個以上のデータパケットを認識する情報が各サイクル
行列に入力されないように、オーバーフロー行列中の情
報をサイクル行列へソートする。第１のサイクル行列が
空になるようにサービスされた後、オーバーフロー行列
は少なくとも第１のサイクル行列にソートされる。
全てのサイクル行列が満杯になった後、あるいは各サイ
クル行列が特定のチャンネルからのＰ個のデータパケッ
トを認識する情報を含んだ後）、情報はオーバーフロー
行列へソートされる。その後、特定のチャンネルからの
Ｐ個以上のデータパケットを認識する情報が各サイクル
行列に入力されないように、オーバーフロー行列中の情
報をサイクル行列へソートする。第１のサイクル行列が
空になるようにサービスされた後、オーバーフロー行列
は少なくとも第１のサイクル行列にソートされる。
【０００９】本発明の一実施例では、認識情報はデータ
パケットがストアされるメモリ位置を示すポインタであ
る。他の実施例では、認識情報はデータパケット自体で
ある。
パケットがストアされるメモリ位置を示すポインタであ
る。他の実施例では、認識情報はデータパケット自体で
ある。
【００１０】本発明は、ヘッドオブザライン・ラウンド
ロビンのスケジューリング法で達成される機能をほぼ達
成するが、その一方で必要とする複雑さとメモリサイズ
はかなり軽減される。サイクル行列へ入力データをソー
トすることによって、全チャンネルの間及び全優先度レ
ベルの間でのメモリ資源完全共有を可能にする。また、
ヘッドオブライン・ラウンドロビン法の実施に必要とさ
れる処理やポインタオーバーヘッドを、各チャンネルに
対して別々のキューを使用しながら軽減する。さらに、
各チャンネルに関連した優先度レベル指標によって、各
サイクル中のチャンネルからのパケット数Ｐをユーザが
指定できるようになる。
ロビンのスケジューリング法で達成される機能をほぼ達
成するが、その一方で必要とする複雑さとメモリサイズ
はかなり軽減される。サイクル行列へ入力データをソー
トすることによって、全チャンネルの間及び全優先度レ
ベルの間でのメモリ資源完全共有を可能にする。また、
ヘッドオブライン・ラウンドロビン法の実施に必要とさ
れる処理やポインタオーバーヘッドを、各チャンネルに
対して別々のキューを使用しながら軽減する。さらに、
各チャンネルに関連した優先度レベル指標によって、各
サイクル中のチャンネルからのパケット数Ｐをユーザが
指定できるようになる。
【００１１】
【実施例】本発明の一実施例によるデータネットワーク
システムを図１を参照して説明する。図１において、１
０１はアクセス装置すなわちアクセスステーション、１
０３はデータ幹線、１１０ー１１５は交換ノードであ
る。交換ノード１１０は、アクセスインターフェイス１
２０ー１２３、データ幹線インターフェイス１３０、１
３１、及びバックプレーン１４０から成る。
システムを図１を参照して説明する。図１において、１
０１はアクセス装置すなわちアクセスステーション、１
０３はデータ幹線、１１０ー１１５は交換ノードであ
る。交換ノード１１０は、アクセスインターフェイス１
２０ー１２３、データ幹線インターフェイス１３０、１
３１、及びバックプレーン１４０から成る。
【００１２】アクセスステーション１０１としては、Ｐ
Ｃ、ワークステーション、ホスト、スーパーコンピュー
タ、ブリッジ、ルーター、ゲートウェイ、ＰＢＸ、デジ
タルビデオカメラ、ビデオモニタ、リアルタイムモニタ
リングデバイスなどが考えられる。実際、アクセスステ
ーション１０１はデジタル情報を生成するものなら何で
も良い。アクセスステーション１０１とアクセスインタ
ーフェイス１２０との間の通信に使われるアクセス技術
は、点対間リンク、複数点間リンク、ＬＡＮ、無線ネッ
トワーク、切り換えサービスなどである。
Ｃ、ワークステーション、ホスト、スーパーコンピュー
タ、ブリッジ、ルーター、ゲートウェイ、ＰＢＸ、デジ
タルビデオカメラ、ビデオモニタ、リアルタイムモニタ
リングデバイスなどが考えられる。実際、アクセスステ
ーション１０１はデジタル情報を生成するものなら何で
も良い。アクセスステーション１０１とアクセスインタ
ーフェイス１２０との間の通信に使われるアクセス技術
は、点対間リンク、複数点間リンク、ＬＡＮ、無線ネッ
トワーク、切り換えサービスなどである。
【００１３】通常、アクセスインターフェイスは、アク
セスステーションからデータを受け取るステップ、適切
なスケジューリング法を使ってそのデータをバックプレ
ーンへ配送するステップ及びバックプレーンからデータ
を受け取ってアクセスステーションへ適切に配送するス
テップからなる必要なステップを実行する。これら必要
なステップは、パケットの分割と再組立、アドレス解
釈、プロトコル終了、バッファリング、スケジューリン
グなどを含み得る。
セスステーションからデータを受け取るステップ、適切
なスケジューリング法を使ってそのデータをバックプレ
ーンへ配送するステップ及びバックプレーンからデータ
を受け取ってアクセスステーションへ適切に配送するス
テップからなる必要なステップを実行する。これら必要
なステップは、パケットの分割と再組立、アドレス解
釈、プロトコル終了、バッファリング、スケジューリン
グなどを含み得る。
【００１４】データ幹線インターフェイス１３０、１３
２は、データ幹線からのデータを受け取るステップ、適
切なスケジューリング法を使ってそのデータをバックプ
レーン１４０、１４１へ配送するステップ及びバックプ
レーンからデータを受け取ってデータ幹線へ配送するス
テップからなる必要なステップを実行する。これら必要
なステップは、パケットの分割と再組立、バッファリン
グ、スケジューリング、などを含み得る。データ幹線
は、種々の時分割多重化（ＴＤＭ）フォーマットを利用
する。データ幹線は、点対間あるいは複数点間のデータ
幹線である。複数点間データ幹線は、双方向バス、無方
向ループバス、リングバスなどがあり得る。あらゆるタ
イプのデータ幹線が、色々な転送設備を使って、適当な
データ転送スピードと符号化スキームを使って、通信媒
体として光ファイバーや銅線や無線を使って実装され
る。データ幹線のタイプは同じである必要はない。それ
らは各々別の符号化スキームを使った異なる伝送メディ
アを利用し得る。さらに、異なるデータ幹線があって良
いことと同様に、共通複数点間データ幹線内のそれぞれ
の部分が全く同じである必要はない。
２は、データ幹線からのデータを受け取るステップ、適
切なスケジューリング法を使ってそのデータをバックプ
レーン１４０、１４１へ配送するステップ及びバックプ
レーンからデータを受け取ってデータ幹線へ配送するス
テップからなる必要なステップを実行する。これら必要
なステップは、パケットの分割と再組立、バッファリン
グ、スケジューリング、などを含み得る。データ幹線
は、種々の時分割多重化（ＴＤＭ）フォーマットを利用
する。データ幹線は、点対間あるいは複数点間のデータ
幹線である。複数点間データ幹線は、双方向バス、無方
向ループバス、リングバスなどがあり得る。あらゆるタ
イプのデータ幹線が、色々な転送設備を使って、適当な
データ転送スピードと符号化スキームを使って、通信媒
体として光ファイバーや銅線や無線を使って実装され
る。データ幹線のタイプは同じである必要はない。それ
らは各々別の符号化スキームを使った異なる伝送メディ
アを利用し得る。さらに、異なるデータ幹線があって良
いことと同様に、共通複数点間データ幹線内のそれぞれ
の部分が全く同じである必要はない。
【００１５】バックプレーン１４０は、例えばスロット
化されたバスやＡＴＭ交換装置などのパケットの交換や
伝送を実行できるデバイスならなんでもよい。バックプ
レーン１４０は、一つのアクセスインターフェイスある
いは一つのデータ幹線インターフェイスからのデータを
受け、それを他のアクセスインターフェイスやデータ幹
線インターフェイスに配送する。
化されたバスやＡＴＭ交換装置などのパケットの交換や
伝送を実行できるデバイスならなんでもよい。バックプ
レーン１４０は、一つのアクセスインターフェイスある
いは一つのデータ幹線インターフェイスからのデータを
受け、それを他のアクセスインターフェイスやデータ幹
線インターフェイスに配送する。
【００１６】図１に例示したシステムは、例えば、ロー
カルエリアネットワーク（ＬＡＮ）、メトロポリタンエ
リアネットワーク（ＭＡＮ）、ワイドエリアネットワー
ク（ＷＡＮ）などを含む一般的なデータネットワークを
表している。これらの全てのシステムは、以前から挙げ
られていた問題、すなわち過剰な複雑さの増加を招くこ
となしに共有資源の使用効率を上げる問題を提示する。
カルエリアネットワーク（ＬＡＮ）、メトロポリタンエ
リアネットワーク（ＭＡＮ）、ワイドエリアネットワー
ク（ＷＡＮ）などを含む一般的なデータネットワークを
表している。これらの全てのシステムは、以前から挙げ
られていた問題、すなわち過剰な複雑さの増加を招くこ
となしに共有資源の使用効率を上げる問題を提示する。
【００１７】以下、このシステムの動作を説明する。ア
クセスステーション１０１から受け取ったデータパケッ
トはバックプレーン１４０に到着する。データパケット
は、一つまたは複数（Ｎ個）のサイクル行列にソートさ
れるが、ある特定のアクセスステーションから来たデー
タパケットがどの特定のサイクルキューにも事前に決め
られた数Ｐ個を越えてソートされることのないようにソ
ートされる。Ｎ個のサイクル行列全てが満杯あるいは飽
和した（つまり、特定のアクセスステーションからのＰ
個のデータパケットを持っている）時、新たに到着した
データパケットはオーバーフロー行列にストアされる。
サイクル行列はサービスを受け、データパケットを排出
（空にする）する。各サイクル行列がサービスされた
後、ライン先頭データパケットがオーバーフロー行列か
ら各サイクル行列に、上述した新たに到着したデータパ
ケットと同様の方法でソートされる。
クセスステーション１０１から受け取ったデータパケッ
トはバックプレーン１４０に到着する。データパケット
は、一つまたは複数（Ｎ個）のサイクル行列にソートさ
れるが、ある特定のアクセスステーションから来たデー
タパケットがどの特定のサイクルキューにも事前に決め
られた数Ｐ個を越えてソートされることのないようにソ
ートされる。Ｎ個のサイクル行列全てが満杯あるいは飽
和した（つまり、特定のアクセスステーションからのＰ
個のデータパケットを持っている）時、新たに到着した
データパケットはオーバーフロー行列にストアされる。
サイクル行列はサービスを受け、データパケットを排出
（空にする）する。各サイクル行列がサービスされた
後、ライン先頭データパケットがオーバーフロー行列か
ら各サイクル行列に、上述した新たに到着したデータパ
ケットと同様の方法でソートされる。
【００１８】このような動作をすることにより、本実施
例はアクセスインターフェイス及びデータ幹線インター
フェイス内のメモリバッファの効率的な使用に特に適し
ている。全データが固定された大きさのデータセル（典
型的には、ＴＤＭデータ幹線のタイムスロットに等し
い）にアクセスインターフェイスにおいて分割されて、
データセルの交換またはデータ幹線スケジューリングが
各データセルベースで行われる場合に大きく関連する。
以下の説明では、「セル」という用語と「パケット」と
いう用語を同じ意味で使用する。
例はアクセスインターフェイス及びデータ幹線インター
フェイス内のメモリバッファの効率的な使用に特に適し
ている。全データが固定された大きさのデータセル（典
型的には、ＴＤＭデータ幹線のタイムスロットに等し
い）にアクセスインターフェイスにおいて分割されて、
データセルの交換またはデータ幹線スケジューリングが
各データセルベースで行われる場合に大きく関連する。
以下の説明では、「セル」という用語と「パケット」と
いう用語を同じ意味で使用する。
【００１９】次に、データ幹線１０３を介した二つの交
換ノード１１０、１１１間の結合の一例を図２を参照し
て説明する。図２において、説明を簡単にするためにデ
ータ幹線１０３は、無方向バス２１０、２２０からなる
双方向バスであると仮定する。データ幹線１０３の各端
に一つずつデータ幹線インターフェイス１３０、１３２
がある。各データ幹線インターフェイス（例えば１３
０）は、バックプレーン１４０からデータ幹線２１０へ
のデータ転送点２０１及びデータ幹線２２０からバック
プレーン１４０へのデータ転送点２０２、すなわち双方
向のデータ結合点にある受信部（ＲＸ）・送信部（Ｔ
Ｘ）対を含む。このようにして、交換ノード１１０から
の信号は、バックプレーン１４０、受信部・送信部対２
０１、データ幹線１０３、受信部・送信部対２０３を経
て交換ノード１１１のバックプレーン１４１に到達す
る。交換ノード１１１からの信号は、バックプレーン１
４１、受信部・送信部対２０４、データ幹線１０３、受
信部・送信部対２０２を経て交換ノード１１０のバック
プレーン１４０に到達する。
換ノード１１０、１１１間の結合の一例を図２を参照し
て説明する。図２において、説明を簡単にするためにデ
ータ幹線１０３は、無方向バス２１０、２２０からなる
双方向バスであると仮定する。データ幹線１０３の各端
に一つずつデータ幹線インターフェイス１３０、１３２
がある。各データ幹線インターフェイス（例えば１３
０）は、バックプレーン１４０からデータ幹線２１０へ
のデータ転送点２０１及びデータ幹線２２０からバック
プレーン１４０へのデータ転送点２０２、すなわち双方
向のデータ結合点にある受信部（ＲＸ）・送信部（Ｔ
Ｘ）対を含む。このようにして、交換ノード１１０から
の信号は、バックプレーン１４０、受信部・送信部対２
０１、データ幹線１０３、受信部・送信部対２０３を経
て交換ノード１１１のバックプレーン１４１に到達す
る。交換ノード１１１からの信号は、バックプレーン１
４１、受信部・送信部対２０４、データ幹線１０３、受
信部・送信部対２０２を経て交換ノード１１０のバック
プレーン１４０に到達する。
【００２０】図１に示したデータネットワークにおける
データ幹線１０３上でのデータ転送に使用されるスロッ
ト化パケット信号のスロットの一例を図３を参照して説
明する。スロット化パケット信号は、例えば、時分割多
重化（ＴＤＭ）信号でもよい。そのフォーマットは、例
えば、ＩＥＥＥ８０２．６プロトコルでもよい。タイム
スロット３０１（ＴＳ１）は、ヘッダー３０２、ペイロ
ード部３０３、トレーラー３０４を含む。ヘッダー３０
２は（時には、さらに分割されてヘッダーと適合層にな
る）、マルチユーザのアクセス情報（例えば、アクセス
制御フィールド）、アドレス情報（例えば、仮想回線Ｉ
Ｄ）、メッセージＩＤ、優先度情報などを運ぶ。トレー
ラー３０４は、エラー検出／訂正の情報（例えば、サイ
クリックな冗長コードーＣＲＣ）などを運ぶ。ペイロー
ド部３０３は、種々のメッセージサイズの幾つかのタイ
プのデータを運ぶために使用できる。種々のサイズのメ
ッセージ３０５（通常、スロットよりもずっと大きい）
が、幾つかのパケット３１１ー３１３に分割され、幾つ
かの連続したタイムスロットＴＳ１−ＴＳ３のペイロー
ド部分の中へ移される。通常、回線無指向型メッセージ
は、メッセージのルーティングやスケジューリングの決
定に使うための完全なソース／宛先アドレス情報を持
つ。回線指向型メッセージは、ルーティングやスケジュ
ーリングの決定を、回線の所在（例えば、仮想回線Ｉ
Ｄ）に依存することになる。チャンネルＩＤは適切な方
法により定義され得る。例えば、異なる仮想回線からの
回線指向型パケット（すなわちタイムスロット）及び異
なるソースアドレスからの回線無指向型パケットは全て
異なるチャンネルへ割付られる。
データ幹線１０３上でのデータ転送に使用されるスロッ
ト化パケット信号のスロットの一例を図３を参照して説
明する。スロット化パケット信号は、例えば、時分割多
重化（ＴＤＭ）信号でもよい。そのフォーマットは、例
えば、ＩＥＥＥ８０２．６プロトコルでもよい。タイム
スロット３０１（ＴＳ１）は、ヘッダー３０２、ペイロ
ード部３０３、トレーラー３０４を含む。ヘッダー３０
２は（時には、さらに分割されてヘッダーと適合層にな
る）、マルチユーザのアクセス情報（例えば、アクセス
制御フィールド）、アドレス情報（例えば、仮想回線Ｉ
Ｄ）、メッセージＩＤ、優先度情報などを運ぶ。トレー
ラー３０４は、エラー検出／訂正の情報（例えば、サイ
クリックな冗長コードーＣＲＣ）などを運ぶ。ペイロー
ド部３０３は、種々のメッセージサイズの幾つかのタイ
プのデータを運ぶために使用できる。種々のサイズのメ
ッセージ３０５（通常、スロットよりもずっと大きい）
が、幾つかのパケット３１１ー３１３に分割され、幾つ
かの連続したタイムスロットＴＳ１−ＴＳ３のペイロー
ド部分の中へ移される。通常、回線無指向型メッセージ
は、メッセージのルーティングやスケジューリングの決
定に使うための完全なソース／宛先アドレス情報を持
つ。回線指向型メッセージは、ルーティングやスケジュ
ーリングの決定を、回線の所在（例えば、仮想回線Ｉ
Ｄ）に依存することになる。チャンネルＩＤは適切な方
法により定義され得る。例えば、異なる仮想回線からの
回線指向型パケット（すなわちタイムスロット）及び異
なるソースアドレスからの回線無指向型パケットは全て
異なるチャンネルへ割付られる。
【００２１】バス２１０に沿った一方向のデータフロー
について説明するが、逆方向のデータフローも同様にし
て起きている。以下、回線無指向型のデータ流を運ぶた
めのデータ幹線インターフェイスの動作についてのみ説
明する。
について説明するが、逆方向のデータフローも同様にし
て起きている。以下、回線無指向型のデータ流を運ぶた
めのデータ幹線インターフェイスの動作についてのみ説
明する。
【００２２】回線無指向型メッセージにおいて、一つか
それ以上のデータパケットから成るデータバッチは一つ
あるいは複数のメッセージ３０５の部分を含み得る。さ
らに、データパケットは固定のサイズ（データのビット
数が固定）、または変動サイズ（データのビット数が可
変）である。回線無指向型ネットワーク以外のネットワ
ークに対する適用においては、データバッチ及びデータ
パケットは、音声情報や映像情報のデジタル表現である
データビットから形成され得る。
それ以上のデータパケットから成るデータバッチは一つ
あるいは複数のメッセージ３０５の部分を含み得る。さ
らに、データパケットは固定のサイズ（データのビット
数が固定）、または変動サイズ（データのビット数が可
変）である。回線無指向型ネットワーク以外のネットワ
ークに対する適用においては、データバッチ及びデータ
パケットは、音声情報や映像情報のデジタル表現である
データビットから形成され得る。
【００２３】図４を参照して、図２に示したデータ幹線
インターフェイス１３０内の受信部／送信部対２０１の
構成を説明する。データの移動は交換ノード１１０から
データ幹線１０３への方向に起きる。図４において、バ
ックプレーン１４０からデータ幹線インターフェイス１
３０への入力があると、その受け取られたデータは受信
部バッファ４０１へストアされる。入力パケット３１１
のヘッダが到着した時点で、受信制御部４０２は、その
入力セルがメッセージの開始（ＢＯＭ）、メッセージの
継続（ＣＯＭ）、メッセージの終了（ＥＯＭ）のどれな
のかを特定する。入力パケットがＢＯＭと分かったら、
受信制御部４０２は適合層内のメッセージＩＤ（ＭＩ
Ｄ）とデータフィールド内の宛先アドレスが到着するの
を待つ。それから、受信制御部４０２は、このデータ幹
線を使ってその宛先アドレスへ到達できるかどうかを決
定するためにルーティングテーブル４０３をチェックす
る。その特定の宛先アドレスがルーティングテーブル４
０３内で見つかった場合、対応するチャンネルＩＤ（Ｃ
ＩＤ）が計算されて、テーブル４０４内のパケットのＭ
ＩＤに割付られる。見つからなかった場合、受け取った
パケットは無視される。入力パケットがＣＯＭまたはＥ
ＯＭと分かった場合は、それに対応するチャンネルＩＤ
がテーブル４０４から検索される。検索されたチャンネ
ルＩＤが無効である場合（例えば ＦＦＦＦ ｈｅｘに
等しい場合）、そのパケットは無視される。入力パケッ
トがＥＯＭでありかつチャンネルＩＤが有効と分かった
場合、無効なチャンネルＩＤがテーブル４０４内のパケ
ットのＭＩＤへ割り付けられる。
インターフェイス１３０内の受信部／送信部対２０１の
構成を説明する。データの移動は交換ノード１１０から
データ幹線１０３への方向に起きる。図４において、バ
ックプレーン１４０からデータ幹線インターフェイス１
３０への入力があると、その受け取られたデータは受信
部バッファ４０１へストアされる。入力パケット３１１
のヘッダが到着した時点で、受信制御部４０２は、その
入力セルがメッセージの開始（ＢＯＭ）、メッセージの
継続（ＣＯＭ）、メッセージの終了（ＥＯＭ）のどれな
のかを特定する。入力パケットがＢＯＭと分かったら、
受信制御部４０２は適合層内のメッセージＩＤ（ＭＩ
Ｄ）とデータフィールド内の宛先アドレスが到着するの
を待つ。それから、受信制御部４０２は、このデータ幹
線を使ってその宛先アドレスへ到達できるかどうかを決
定するためにルーティングテーブル４０３をチェックす
る。その特定の宛先アドレスがルーティングテーブル４
０３内で見つかった場合、対応するチャンネルＩＤ（Ｃ
ＩＤ）が計算されて、テーブル４０４内のパケットのＭ
ＩＤに割付られる。見つからなかった場合、受け取った
パケットは無視される。入力パケットがＣＯＭまたはＥ
ＯＭと分かった場合は、それに対応するチャンネルＩＤ
がテーブル４０４から検索される。検索されたチャンネ
ルＩＤが無効である場合（例えば ＦＦＦＦ ｈｅｘに
等しい場合）、そのパケットは無視される。入力パケッ
トがＥＯＭでありかつチャンネルＩＤが有効と分かった
場合、無効なチャンネルＩＤがテーブル４０４内のパケ
ットのＭＩＤへ割り付けられる。
【００２４】パケットに関するチャンネルＩＤが見つか
ると、受信制御部４０２はそのパケットの送信をスケジ
ュールする用意をする。受信制御部４０２は、チャンネ
ルＩＤに関する全状態情報（レジスタ４０５、４０６、
４０７、４０８、４０９、４１０）を検索、更新し、そ
のＩＤ情報（そのパケットがストアされるべきメモリ位
置を指すポインター）を決定する。そのＩＤ情報は受信
部のダイレクトメモリアクセス（ＤＭＡ）デバイス４１
１へ送られ、パケットがメモリ４１２内にあるＮ個のサ
イクル行列５０７ー５０９の内の一つまたはオーバーフ
ロー行列５１０に適切にストアされる。
ると、受信制御部４０２はそのパケットの送信をスケジ
ュールする用意をする。受信制御部４０２は、チャンネ
ルＩＤに関する全状態情報（レジスタ４０５、４０６、
４０７、４０８、４０９、４１０）を検索、更新し、そ
のＩＤ情報（そのパケットがストアされるべきメモリ位
置を指すポインター）を決定する。そのＩＤ情報は受信
部のダイレクトメモリアクセス（ＤＭＡ）デバイス４１
１へ送られ、パケットがメモリ４１２内にあるＮ個のサ
イクル行列５０７ー５０９の内の一つまたはオーバーフ
ロー行列５１０に適切にストアされる。
【００２５】パケット送信の時、送信制御部４１３は転
送されるパケットに関する全状態情報を検索、更新す
る。送信制御部４１３は、ＩＤ情報（一つあるいはそれ
以上のデータパケットへのポインタ）を送信部のＤＭＡ
デバイス４１４へ送り、適切なパケットが送信部バッフ
ァ４１５へ送られる。そして、パケットはデータ幹線２
１０へ送出される。
送されるパケットに関する全状態情報を検索、更新す
る。送信制御部４１３は、ＩＤ情報（一つあるいはそれ
以上のデータパケットへのポインタ）を送信部のＤＭＡ
デバイス４１４へ送り、適切なパケットが送信部バッフ
ァ４１５へ送られる。そして、パケットはデータ幹線２
１０へ送出される。
【００２６】この様な方法で、送信制御部４１３は全て
のサイクル行列５０７ー５０９の各々を空にするまで連
続的にサービスを行う。送信制御部４１３がサイクル行
列を空にした時点で、オーバーフロー行列のソーターが
活性化され、受信制御部４０２が到着したパケットを取
り扱う場合と同様の方法で、オーバーフロー行列のライ
ン先頭に対して繰り返しサービスし、サイクル行列に導
く。オーバーフロー行列のライン先頭にあったパケット
が通ってきたチャンネルと同じチャンネルからのパケッ
トで全てのサイクル行列が飽和した時、もしくは他の所
定の事態が起きた時、送信制御部４１３は次のサイクル
行列へのサービスを始める。この所定の事態というの
は、例えば送信部バッファ４１５が空になった時であ
る。その時には、送信制御部４１３は直ちにパケットを
送信部バッファ４１５に送り、データ幹線２１０を使用
状態に保つ。
のサイクル行列５０７ー５０９の各々を空にするまで連
続的にサービスを行う。送信制御部４１３がサイクル行
列を空にした時点で、オーバーフロー行列のソーターが
活性化され、受信制御部４０２が到着したパケットを取
り扱う場合と同様の方法で、オーバーフロー行列のライ
ン先頭に対して繰り返しサービスし、サイクル行列に導
く。オーバーフロー行列のライン先頭にあったパケット
が通ってきたチャンネルと同じチャンネルからのパケッ
トで全てのサイクル行列が飽和した時、もしくは他の所
定の事態が起きた時、送信制御部４１３は次のサイクル
行列へのサービスを始める。この所定の事態というの
は、例えば送信部バッファ４１５が空になった時であ
る。その時には、送信制御部４１３は直ちにパケットを
送信部バッファ４１５に送り、データ幹線２１０を使用
状態に保つ。
【００２７】図４に示された構成は、ＣＭＯＳ、ＶＬＳ
Ｉ、ＥＣＬ、またはハイブリッド回路技術による集積回
路チップを一つかそれ以上使用することによって実現可
能である。なお、いかなる周知の半導体技術を使った他
の実施例によっても実現できる。受信部バッファ４０１
へのインターフェイスは、光インテグレーター、調和型
ファイバーまたはその他のバックプレーンの物理的メデ
ィアと変調の組合せに適切なデバイスを使用できる。受
信部バッファ４０１は、シフトレジスタまたは非常に高
速なランダムアクセスメモリＲＡＭを使用できる。受信
制御部４０２と送信制御部４１３は、ＶＬＳＩ回路によ
って実現される有限状態マシン、縮小命令セットコント
ローラ（ＲＩＳＣ）をベースにしたマイクロプロセッ
サ、あるいは他の通常のマイクロプロセッサを使って組
み立てられ得る。レジスタ４０５、４０６、４０７、４
０８、４０９、４１０及びデータメモリ４１２は非常に
高速なＲＡＭを用いて作られ得る。
Ｉ、ＥＣＬ、またはハイブリッド回路技術による集積回
路チップを一つかそれ以上使用することによって実現可
能である。なお、いかなる周知の半導体技術を使った他
の実施例によっても実現できる。受信部バッファ４０１
へのインターフェイスは、光インテグレーター、調和型
ファイバーまたはその他のバックプレーンの物理的メデ
ィアと変調の組合せに適切なデバイスを使用できる。受
信部バッファ４０１は、シフトレジスタまたは非常に高
速なランダムアクセスメモリＲＡＭを使用できる。受信
制御部４０２と送信制御部４１３は、ＶＬＳＩ回路によ
って実現される有限状態マシン、縮小命令セットコント
ローラ（ＲＩＳＣ）をベースにしたマイクロプロセッ
サ、あるいは他の通常のマイクロプロセッサを使って組
み立てられ得る。レジスタ４０５、４０６、４０７、４
０８、４０９、４１０及びデータメモリ４１２は非常に
高速なＲＡＭを用いて作られ得る。
【００２８】図５において、本実施例によって用いられ
るアルゴリズムは、受信部サーバー（ソーター）５１
１、送信部サーバー５１２、Ｎ個のサイクル行列（Ｃ
Ｑ）５０７ー５０９、一個のオーバーフロー行列（Ｏ
Ｑ）５１０を必要とし、さらに受信ポインター（ＲＰ）
５０１、サイクルカウンタ（ＣＣ）５０２、オーバーフ
ローカウンタ（ＯＣ）５０３、優先度レジスタ（ＰＲ）
５０４、サイクルレジスタ（ＣＲ）５０５、送信ポイン
タ（ＴＰ）５０６から成るチャンネルに対するポインタ
群を必要とする。
るアルゴリズムは、受信部サーバー（ソーター）５１
１、送信部サーバー５１２、Ｎ個のサイクル行列（Ｃ
Ｑ）５０７ー５０９、一個のオーバーフロー行列（Ｏ
Ｑ）５１０を必要とし、さらに受信ポインター（ＲＰ）
５０１、サイクルカウンタ（ＣＣ）５０２、オーバーフ
ローカウンタ（ＯＣ）５０３、優先度レジスタ（ＰＲ）
５０４、サイクルレジスタ（ＣＲ）５０５、送信ポイン
タ（ＴＰ）５０６から成るチャンネルに対するポインタ
群を必要とする。
【００２９】受信ポインター（ＲＰ）５０１は、特定の
チャンネルから来たパケット（タイムスロット）をサイ
クル行列５０７ー５０９の内のどれに入れるかを受信部
サーバー５１１内のオーバーフロー行列ソーターが決め
るために使われる。サイクルカウンタ（ＣＣ）に対応す
るポインター５０２は、サイクル行列５０７ー５０９全
体に渡ってストアされている各チャンネルからのパケッ
トの数をカウントするために使われる。オーバーフロー
カウンタ（ＯＣ）に対応するポインター５０３は、オー
バーフロー行列にストアされている各チャンネルからの
パケットの数をカウントするために使われる。優先度レ
ジスタ（ＰＲ）に対応するポインター５０４は、各チャ
ンネルに対して優先度に比例して事前に割付られた値を
ストアするために使われる。サイクルレジスタ（ＣＲ）
に対応するポインター５０５は、現在ＲＰによって認識
されているサイクル行列の中に各チャンネルのパケット
が各々幾つストアされているかをカウントするために使
われる。送信ポインター（ＴＰ）に対応するポインター
５０６は、Ｎ個のサイクル行列５０７ー５０９のうちの
どれからパケットを取り出して送信するかを送信部５１
２内のセレクタが決めるために使われる。
チャンネルから来たパケット（タイムスロット）をサイ
クル行列５０７ー５０９の内のどれに入れるかを受信部
サーバー５１１内のオーバーフロー行列ソーターが決め
るために使われる。サイクルカウンタ（ＣＣ）に対応す
るポインター５０２は、サイクル行列５０７ー５０９全
体に渡ってストアされている各チャンネルからのパケッ
トの数をカウントするために使われる。オーバーフロー
カウンタ（ＯＣ）に対応するポインター５０３は、オー
バーフロー行列にストアされている各チャンネルからの
パケットの数をカウントするために使われる。優先度レ
ジスタ（ＰＲ）に対応するポインター５０４は、各チャ
ンネルに対して優先度に比例して事前に割付られた値を
ストアするために使われる。サイクルレジスタ（ＣＲ）
に対応するポインター５０５は、現在ＲＰによって認識
されているサイクル行列の中に各チャンネルのパケット
が各々幾つストアされているかをカウントするために使
われる。送信ポインター（ＴＰ）に対応するポインター
５０６は、Ｎ個のサイクル行列５０７ー５０９のうちの
どれからパケットを取り出して送信するかを送信部５１
２内のセレクタが決めるために使われる。
【００３０】受信部５１１は、一つかそれ以上の施設線
５１１上の複数の通信チャンネルを受ける。受信部５１
１は、与えられたチャンネルからのタイムスロットデー
タをＮ個のサイクル行列５０７ー５０９の内の適当な一
つかオーバーフロー行列５１０へ分配あるいはソートす
る。送信部５１２はＮ個のサイクル行列５０７ー５０９
からタイムスロットデータを集める。受信部５１１、送
信部５１２または独立したプロセッサは、オーバーフロ
ー行列５１０からＮ個のサイクル行列５０７ー５０９へ
タイムスロットデータをソートする。送信部５１２は、
一つかそれ以上の施設線５１４上の各チャンネルへその
タイムスロットを送信する。なお、Ｎ個のサイクル行列
５０７ー５０９及びオーバーフロー行列５１０が、実際
に受信したデータまたはシステムメモリ内のデータの実
際の位置に対するポインターを持っていても良い。
５１１上の複数の通信チャンネルを受ける。受信部５１
１は、与えられたチャンネルからのタイムスロットデー
タをＮ個のサイクル行列５０７ー５０９の内の適当な一
つかオーバーフロー行列５１０へ分配あるいはソートす
る。送信部５１２はＮ個のサイクル行列５０７ー５０９
からタイムスロットデータを集める。受信部５１１、送
信部５１２または独立したプロセッサは、オーバーフロ
ー行列５１０からＮ個のサイクル行列５０７ー５０９へ
タイムスロットデータをソートする。送信部５１２は、
一つかそれ以上の施設線５１４上の各チャンネルへその
タイムスロットを送信する。なお、Ｎ個のサイクル行列
５０７ー５０９及びオーバーフロー行列５１０が、実際
に受信したデータまたはシステムメモリ内のデータの実
際の位置に対するポインターを持っていても良い。
【００３１】実際には、全ての行列（Ｎ個のサイクル行
列５０７ー５０９とオーバーフロー行列５１０）はその
大きさが有限である。選択されたサイクル行列が満杯で
あった場合にデータロスを最小にするために、情報認識
データやデータパケットを他の使用可能なサイクル行列
またはオーバーフロー行列の中に入れることを可能にし
て、データの放棄や欠落が起きないようにしている。さ
らに、システムメモリがほとんど満杯だった場合、すな
わち事前に決められているデータ許容しきい値に達して
いる場合、システムが受け取った新しいメッセージを放
棄して、すでにシステムが受け取っているメッセージを
放棄することを防止している。
列５０７ー５０９とオーバーフロー行列５１０）はその
大きさが有限である。選択されたサイクル行列が満杯で
あった場合にデータロスを最小にするために、情報認識
データやデータパケットを他の使用可能なサイクル行列
またはオーバーフロー行列の中に入れることを可能にし
て、データの放棄や欠落が起きないようにしている。さ
らに、システムメモリがほとんど満杯だった場合、すな
わち事前に決められているデータ許容しきい値に達して
いる場合、システムが受け取った新しいメッセージを放
棄して、すでにシステムが受け取っているメッセージを
放棄することを防止している。
【００３２】図６、図７及び図８を参照して、それぞれ
受信部５１１、送信部５１２、オーバーフロー行列ソー
ター５１０の動作を説明する。以下の説明において、チ
ャンネルｎに対して、ＲＰ（ｎ）は受信ポインターの
値、ＣＣ（ｎ）はサイクルカウンタの値、ＯＣ（ｎ）は
オーバーフローカウンタの値、ＰＲ（ｎ）は優先度レジ
スタの値、ＣＲ（ｎ）はサイクルレジスタの値を指す。
受信部５１１、送信部５１２、オーバーフロー行列ソー
ター５１０の動作を説明する。以下の説明において、チ
ャンネルｎに対して、ＲＰ（ｎ）は受信ポインターの
値、ＣＣ（ｎ）はサイクルカウンタの値、ＯＣ（ｎ）は
オーバーフローカウンタの値、ＰＲ（ｎ）は優先度レジ
スタの値、ＣＲ（ｎ）はサイクルレジスタの値を指す。
【００３３】図５に示したアルゴリズムを使うと、特定
のデータチャンネルからのＰ個以上のデータパケットを
一つのサイクル行列中へ入れようとするような事態が起
こり得る。このような事態を避けるために、図６に示す
手順が実行される。例えば、システムに特定のチャンネ
ルからのデータパケットが一つも無い場合、そのチャン
ネルからのデータパケットの現サイクルにおける送信は
無かったとシステムはみなす。しかし、次のようなシー
ケンスが起きる可能性もある。すなわち、チャンネルｉ
からのデータパケットが到着し、チャンネルｊからのデ
ータパケットが到着し、そしてそのチャンネルｉからの
最初のデータパケットが既にサービスされたり送信され
た後にチャンネルｉから第二のデータパケットが到着す
るというシーケンスである。このようなことが起きた場
合、チャンネルｉに対する送信ポインターと受信ポイン
ターが同じ値を持つことになる。そのため、チャンネル
ｉからのデータパケットが到着して、そのチャンネルか
らのデータパケットがシステムに一つも無いということ
がステップ６０４において分かった場合、及び受信ポイ
ンター５０１の値が送信ポインター５０６の値に等しい
場合、上述した事態が起きていると考えられる。そのよ
うな場合には、データパケットはステップ６０５、６０
７、６０９により次のサイクル行列に入れられる。
のデータチャンネルからのＰ個以上のデータパケットを
一つのサイクル行列中へ入れようとするような事態が起
こり得る。このような事態を避けるために、図６に示す
手順が実行される。例えば、システムに特定のチャンネ
ルからのデータパケットが一つも無い場合、そのチャン
ネルからのデータパケットの現サイクルにおける送信は
無かったとシステムはみなす。しかし、次のようなシー
ケンスが起きる可能性もある。すなわち、チャンネルｉ
からのデータパケットが到着し、チャンネルｊからのデ
ータパケットが到着し、そしてそのチャンネルｉからの
最初のデータパケットが既にサービスされたり送信され
た後にチャンネルｉから第二のデータパケットが到着す
るというシーケンスである。このようなことが起きた場
合、チャンネルｉに対する送信ポインターと受信ポイン
ターが同じ値を持つことになる。そのため、チャンネル
ｉからのデータパケットが到着して、そのチャンネルか
らのデータパケットがシステムに一つも無いということ
がステップ６０４において分かった場合、及び受信ポイ
ンター５０１の値が送信ポインター５０６の値に等しい
場合、上述した事態が起きていると考えられる。そのよ
うな場合には、データパケットはステップ６０５、６０
７、６０９により次のサイクル行列に入れられる。
【００３４】しかし、このようにすると別の問題が生じ
る。受信ポインターの値と送信ポインターの値が偶然に
等しいかもしれないという問題である。この場合、その
ような「偶然」の事態が起きる可能性を、状態空間（送
信ポインターと受信ポインターのとり得る値の数）をサ
イクル行列の数Ｎよりも非常に大きくすることによって
減らすことができる。これは、送信ポインターと受信ポ
インターのとり得る値の数をＮの整数倍の数Ｍに等しく
することにより達成できる。このため、送信ポインター
と受信ポインターは本質的に、基本サイズＭのカウンタ
になる。このようにして、データパケット誤配置の確率
は１／Ｍになり、それはＭを大きくすることによって必
要なだけ小さくできる。
る。受信ポインターの値と送信ポインターの値が偶然に
等しいかもしれないという問題である。この場合、その
ような「偶然」の事態が起きる可能性を、状態空間（送
信ポインターと受信ポインターのとり得る値の数）をサ
イクル行列の数Ｎよりも非常に大きくすることによって
減らすことができる。これは、送信ポインターと受信ポ
インターのとり得る値の数をＮの整数倍の数Ｍに等しく
することにより達成できる。このため、送信ポインター
と受信ポインターは本質的に、基本サイズＭのカウンタ
になる。このようにして、データパケット誤配置の確率
は１／Ｍになり、それはＭを大きくすることによって必
要なだけ小さくできる。
【００３５】例えば、三つのサイクル行列（つまり、Ｎ
＝３）、ｍに等しくない全てのｎに対してＰＲ（ｎ）＝
１、ｎ＝ｍにおいてＰＲ（ｍ）＝２という場合を考え
る。これは、システムが各チャンネルｉ、ｊ、ｋからは
一つのデータパケットを取扱い、チャンネルｍからは二
つのデータパケットを同時に取り扱うことを意味する。
よって、チャンネルｍのデータはチャンネルｉ、ｊ、ｋ
のデータよりも優先度が高い。ＰＲ（ｎ）の値の割付
は、特定のチャンネルに対するサービスを他のチャンネ
ルに対するサービスと差別化したいという要求に基づい
ている。ＰＲ（ｎ）の値はサービスのクラスを識別する
ために使用でき、データチャンネルをより良いサービス
をするもの、すなわちデータ送信の割合をより高いのも
のとすることができる。
＝３）、ｍに等しくない全てのｎに対してＰＲ（ｎ）＝
１、ｎ＝ｍにおいてＰＲ（ｍ）＝２という場合を考え
る。これは、システムが各チャンネルｉ、ｊ、ｋからは
一つのデータパケットを取扱い、チャンネルｍからは二
つのデータパケットを同時に取り扱うことを意味する。
よって、チャンネルｍのデータはチャンネルｉ、ｊ、ｋ
のデータよりも優先度が高い。ＰＲ（ｎ）の値の割付
は、特定のチャンネルに対するサービスを他のチャンネ
ルに対するサービスと差別化したいという要求に基づい
ている。ＰＲ（ｎ）の値はサービスのクラスを識別する
ために使用でき、データチャンネルをより良いサービス
をするもの、すなわちデータ送信の割合をより高いのも
のとすることができる。
【００３６】ある周期において、チャンネルｉからのパ
ケット（ｉ1、ｉ2、ｉ3、ｉ4、ｉ5、ｉ6、ｉ7）、チャ
ンネルｊからのパケット（ｊ1、ｊ2、ｊ3、ｊ4）、チャ
ンネルｋからのパケット（ｋ1）及びチャンネルｍから
のパケット（ｍ1、ｍ2、ｍ3、ｍ4）によって構成される
バッチが、ｉ1-ｉ2-ｉ3-ｉ4-ｉ5-ｉ6-ｉ7-ｊ1-ｊ2-ｋ1-
ｊ3-ｊ4-ｍ1-ｍ2-ｍ3-ｍ4の順序で受信部５１１に到着
する場合を考える。パケットｉ1乃至ｉ7はチャンネルｉ
からのバッチ、パケットｊ1、ｊ2はチャンネルｊからの
バッチ、パケットｋ1はチャンネルｋからのバッチ、パ
ケットｊ3、ｊ4はチャンネルｊからの二番目のバッチ、
そしてパケットｍ1からｍ4はチャンネルｍからのバッチ
を表す。各データパケットは固定されたデータビット数
を有する。典型的には、データ転送に使われるスロット
化パケット用施設線のタイムスロットのサイズとデータ
パケットのサイズとは等しい。さらに、メッセージを有
するバッチが到着した時点で、システムは空である（つ
まり、システム内には一つもパケットがなく、全てのポ
インターはゼロにセットされている）ものとする。
ケット（ｉ1、ｉ2、ｉ3、ｉ4、ｉ5、ｉ6、ｉ7）、チャ
ンネルｊからのパケット（ｊ1、ｊ2、ｊ3、ｊ4）、チャ
ンネルｋからのパケット（ｋ1）及びチャンネルｍから
のパケット（ｍ1、ｍ2、ｍ3、ｍ4）によって構成される
バッチが、ｉ1-ｉ2-ｉ3-ｉ4-ｉ5-ｉ6-ｉ7-ｊ1-ｊ2-ｋ1-
ｊ3-ｊ4-ｍ1-ｍ2-ｍ3-ｍ4の順序で受信部５１１に到着
する場合を考える。パケットｉ1乃至ｉ7はチャンネルｉ
からのバッチ、パケットｊ1、ｊ2はチャンネルｊからの
バッチ、パケットｋ1はチャンネルｋからのバッチ、パ
ケットｊ3、ｊ4はチャンネルｊからの二番目のバッチ、
そしてパケットｍ1からｍ4はチャンネルｍからのバッチ
を表す。各データパケットは固定されたデータビット数
を有する。典型的には、データ転送に使われるスロット
化パケット用施設線のタイムスロットのサイズとデータ
パケットのサイズとは等しい。さらに、メッセージを有
するバッチが到着した時点で、システムは空である（つ
まり、システム内には一つもパケットがなく、全てのポ
インターはゼロにセットされている）ものとする。
【００３７】ステップ６０１において、第一のパケット
ｉ1が受信部５１１へ到着する。ステップ６０２におい
て、ＯＣ（ｉ）＝０かどうかチェックするテストがなさ
れる。オーバフロー行列５１０内にはチャンネルｉから
のパケットは無いので、答えはＹＥＳである。ステップ
６０４において、ＣＣ（ｉ）＝０かどうかをチェックす
るテストが行われる。サイクル行列５０７ー５０９には
チャンネルｉからのパケットは無いので、答えはＹＥＳ
である。ステップ６０５において、ＲＰ（ｉ）＝ＴＰか
どうかチェックするテストが行われる。この時点では全
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。ＲＰ
（ｉ）が指定するサイクル行列内に入れられたチャンネ
ルｉからのパケットは無いので、ＣＲ（ｉ）＝０は１に
セットされているＰＲ（ｉ）よりも小さい。答えはＹＥ
Ｓなので、ステップ６０８が実行される。このようにし
て、パケットｉ1は、ＲＰ（ｉ）が指定するサイクル行
列（図９に示すサイクル行列（＃０）５０７）に入れら
れ、ＣＣ（ｉ）及びＣＲ（ｉ）は１にインクリメントさ
れる。各パケットが受信部５１１に到着する毎にこのよ
うなプロセスが繰り返される。
ｉ1が受信部５１１へ到着する。ステップ６０２におい
て、ＯＣ（ｉ）＝０かどうかチェックするテストがなさ
れる。オーバフロー行列５１０内にはチャンネルｉから
のパケットは無いので、答えはＹＥＳである。ステップ
６０４において、ＣＣ（ｉ）＝０かどうかをチェックす
るテストが行われる。サイクル行列５０７ー５０９には
チャンネルｉからのパケットは無いので、答えはＹＥＳ
である。ステップ６０５において、ＲＰ（ｉ）＝ＴＰか
どうかチェックするテストが行われる。この時点では全
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。ＲＰ
（ｉ）が指定するサイクル行列内に入れられたチャンネ
ルｉからのパケットは無いので、ＣＲ（ｉ）＝０は１に
セットされているＰＲ（ｉ）よりも小さい。答えはＹＥ
Ｓなので、ステップ６０８が実行される。このようにし
て、パケットｉ1は、ＲＰ（ｉ）が指定するサイクル行
列（図９に示すサイクル行列（＃０）５０７）に入れら
れ、ＣＣ（ｉ）及びＣＲ（ｉ）は１にインクリメントさ
れる。各パケットが受信部５１１に到着する毎にこのよ
うなプロセスが繰り返される。
【００３８】ステップ６０１において、パケットｉ2が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｉからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェ
ックするテストがなされる。ＲＰ（ｉ）が指定するサイ
クル行列内にチャンネルｉからのパケットが一つあるの
で、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯと
なる。ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２
かどうかチェックするテストがなされる。ＲＰ（ｉ）＝
０、ＴＰ＋２＝２なので、答えはＮＯであり、ステップ
６０９が実行される。ＲＰ（ｉ）は１にインクリメント
され、ＣＲ（ｉ）は１にセットされ、ＲＰ（ｉ）が指定
するサイクル行列（図９に示すサイクル行列（＃１）５
０８）にパケットｉ2が入れられ、ＣＣ（ｉ）は２にイ
ンクリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｉからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェ
ックするテストがなされる。ＲＰ（ｉ）が指定するサイ
クル行列内にチャンネルｉからのパケットが一つあるの
で、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯと
なる。ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２
かどうかチェックするテストがなされる。ＲＰ（ｉ）＝
０、ＴＰ＋２＝２なので、答えはＮＯであり、ステップ
６０９が実行される。ＲＰ（ｉ）は１にインクリメント
され、ＣＲ（ｉ）は１にセットされ、ＲＰ（ｉ）が指定
するサイクル行列（図９に示すサイクル行列（＃１）５
０８）にパケットｉ2が入れられ、ＣＣ（ｉ）は２にイ
ンクリメントされる。
【００３９】ステップ６０１において、パケットｉ3が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｉからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストがなされる。ＲＰ（ｉ）が指定するサイクル行
列内にチャンネルｉからのパケットが一つあるので、Ｃ
Ｒ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｉ）＝１、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｉ）は２にインクリメントされ、
ＣＲ（ｉ）は１にセットされ、ＲＰ（ｉ）が指定するサ
イクル行列（図９に示すサイクル行列（＃２）５０９）
にパケットｉ3が入れられ、ＣＣ（ｉ）は３にインクリ
メントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｉからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストがなされる。ＲＰ（ｉ）が指定するサイクル行
列内にチャンネルｉからのパケットが一つあるので、Ｃ
Ｒ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｉ）＝１、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｉ）は２にインクリメントされ、
ＣＲ（ｉ）は１にセットされ、ＲＰ（ｉ）が指定するサ
イクル行列（図９に示すサイクル行列（＃２）５０９）
にパケットｉ3が入れられ、ＣＣ（ｉ）は３にインクリ
メントされる。
【００４０】ステップ６０１において、パケットｉ4が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｉからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストがなされる。ＲＰ（ｉ）が指定するサイクル行
列内にチャンネルｉからのパケットが一つあるので、Ｃ
Ｒ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｉ）＝２、Ｔ
Ｐ＋２＝２なので、答えはＹＥＳであり、ステップ６０
３が実行される。図９に示すオーバーフロー行列５１０
にパケットｉ4が入れられ、ＯＣ（ｉ）は１にインクリ
メントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｉ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｉからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストがなされる。ＲＰ（ｉ）が指定するサイクル行
列内にチャンネルｉからのパケットが一つあるので、Ｃ
Ｒ（ｉ）＝ＰＲ（ｉ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｉ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｉ）＝２、Ｔ
Ｐ＋２＝２なので、答えはＹＥＳであり、ステップ６０
３が実行される。図９に示すオーバーフロー行列５１０
にパケットｉ4が入れられ、ＯＣ（ｉ）は１にインクリ
メントされる。
【００４１】ステップ６０１において、パケットｉ5が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは一つあるので、答えはＮＯである。パケットｉ5
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が２にインクリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは一つあるので、答えはＮＯである。パケットｉ5
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が２にインクリメントされる。
【００４２】ステップ６０１において、パケットｉ6が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは二つあるので、答えはＮＯである。パケットｉ6
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が３にインクリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは二つあるので、答えはＮＯである。パケットｉ6
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が３にインクリメントされる。
【００４３】ステップ６０１において、パケットｉ7が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは三つあるので、答えはＮＯである。パケットｉ7
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が４にインクリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｉ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｉからのパケ
ットは三つあるので、答えはＮＯである。パケットｉ7
はオーバーフロー行列５１０に入れられ、ＯＣ（ｉ）の
値が４にインクリメントされる。
【００４４】ステップ６０１において、パケットｊ1が
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｊからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｊ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｊ）＜ＰＲ
（ｊ）かどうかチェックするテストが行われる。ＲＰ
（ｊ）が指定するサイクル行列内のチャンネルｊからの
パケットは無いので、ＣＲ（ｊ）＝０はＰＲ（ｊ）より
も小さい。よってステップ６０８が実行され、ＣＲ
（ｊ）は１にセットされる。このようにして、パケット
ｊ1は、ＲＰ（ｊ）が指定するサイクル行列（図９中の
サイクル行列（＃０）５０７である）に入れられ、ＣＣ
（ｊ）及びＣＲ（ｊ）は１にインクリメントされる。
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｊからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｊ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｊ）＜ＰＲ
（ｊ）かどうかチェックするテストが行われる。ＲＰ
（ｊ）が指定するサイクル行列内のチャンネルｊからの
パケットは無いので、ＣＲ（ｊ）＝０はＰＲ（ｊ）より
も小さい。よってステップ６０８が実行され、ＣＲ
（ｊ）は１にセットされる。このようにして、パケット
ｊ1は、ＲＰ（ｊ）が指定するサイクル行列（図９中の
サイクル行列（＃０）５０７である）に入れられ、ＣＣ
（ｊ）及びＣＲ（ｊ）は１にインクリメントされる。
【００４５】ステップ６０１において、パケットｊ2が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｊからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェ
ックするテストがなされる。ＲＰ（ｊ）が指定するサイ
クル行列内にチャンネルｊからのパケットが一つあるの
で、ＣＲ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯと
なる。ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２
かどうかチェックするテストがなされる。ＲＰ（ｊ）＝
０、ＴＰ＋２＝２なので、答えはＮＯであり、ステップ
６０９が実行される。ＲＰ（ｊ）は１にインクリメント
され、ＣＲ（ｊ）は１にセットされ、ＲＰ（ｊ）が指定
するサイクル行列（図９中のサイクル行列（＃１）５０
８）にパケットｊ2が入れられ、ＣＣ（ｊ）は２にイン
クリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｊからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェ
ックするテストがなされる。ＲＰ（ｊ）が指定するサイ
クル行列内にチャンネルｊからのパケットが一つあるの
で、ＣＲ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯと
なる。ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２
かどうかチェックするテストがなされる。ＲＰ（ｊ）＝
０、ＴＰ＋２＝２なので、答えはＮＯであり、ステップ
６０９が実行される。ＲＰ（ｊ）は１にインクリメント
され、ＣＲ（ｊ）は１にセットされ、ＲＰ（ｊ）が指定
するサイクル行列（図９中のサイクル行列（＃１）５０
８）にパケットｊ2が入れられ、ＣＣ（ｊ）は２にイン
クリメントされる。
【００４６】ステップ６０１において、パケットｋ1が
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｋ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｋからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｋ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｋからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｋ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｋ）＜ＰＲ
（ｋ）かどうかチェックするテストが行われる。ＲＰ
（ｋ）が指定するサイクル行列内のチャンネルｋからの
パケットは無いので、ＣＲ（ｋ）＝０はＰＲ（ｋ）より
も小さい。よってステップ６０８が実行され、ＣＲ
（ｋ）は１にセットされる。このようにして、パケット
ｋ1は、ＲＰ（ｋ）が指定するサイクル行列（サイクル
行列（＃０）５０７である）に入れられ、ＣＣ（ｋ）及
びＣＲ（ｋ）は１にインクリメントされる。
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｋ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｋからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｋ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｋからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｋ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｋ）＜ＰＲ
（ｋ）かどうかチェックするテストが行われる。ＲＰ
（ｋ）が指定するサイクル行列内のチャンネルｋからの
パケットは無いので、ＣＲ（ｋ）＝０はＰＲ（ｋ）より
も小さい。よってステップ６０８が実行され、ＣＲ
（ｋ）は１にセットされる。このようにして、パケット
ｋ1は、ＲＰ（ｋ）が指定するサイクル行列（サイクル
行列（＃０）５０７である）に入れられ、ＣＣ（ｋ）及
びＣＲ（ｋ）は１にインクリメントされる。
【００４７】ステップ６０１において、パケットｊ3が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｊからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストがなされる。ＲＰ（ｊ）が指定するサイクル行
列内にチャンネルｊからのパケットが一つあるので、Ｃ
Ｒ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｊ）＝１、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｊ）は２にインクリメントされ、
ＣＲ（ｊ）は１にセットされ、ＲＰ（ｊ）が指定するサ
イクル行列（それはサイクル行列（＃２）５０９であ
る）にパケットｊ3が入れられ、ＣＣ（ｊ）は３にイン
クリメントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｊからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストがなされる。ＲＰ（ｊ）が指定するサイクル行
列内にチャンネルｊからのパケットが一つあるので、Ｃ
Ｒ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｊ）＝１、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｊ）は２にインクリメントされ、
ＣＲ（ｊ）は１にセットされ、ＲＰ（ｊ）が指定するサ
イクル行列（それはサイクル行列（＃２）５０９であ
る）にパケットｊ3が入れられ、ＣＣ（ｊ）は３にイン
クリメントされる。
【００４８】ステップ６０１において、パケットｊ4が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｊからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストがなされる。ＲＰ（ｊ）が指定するサイクル行
列内にチャンネルｊからのパケットが一つあるので、Ｃ
Ｒ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｊ）＝２、Ｔ
Ｐ＋２＝２なので、答えはＹＥＳであり、ステップ６０
３が実行される。オーバーフロー行列５１０にパケット
ｊ4が入れられ、ＯＣ（ｊ）は１にインクリメントされ
る。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｊ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｊからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｊ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｊからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストがなされる。ＲＰ（ｊ）が指定するサイクル行
列内にチャンネルｊからのパケットが一つあるので、Ｃ
Ｒ（ｊ）＝ＰＲ（ｊ）＝１となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｊ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｊ）＝２、Ｔ
Ｐ＋２＝２なので、答えはＹＥＳであり、ステップ６０
３が実行される。オーバーフロー行列５１０にパケット
ｊ4が入れられ、ＯＣ（ｊ）は１にインクリメントされ
る。
【００４９】ステップ６０１において、パケットｍ1が
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｍからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｍ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｍ）＜ＰＲ
（ｍ）かどうかチェックするテストが行われる。ＲＰ
（ｍ）が指定するサイクル行列内のチャンネルｍからの
パケットは無いので、ＣＲ（ｍ）＝０はＰＲ（ｍ）＝２
よりも小さい。よってステップ６０８が実行され、ＣＲ
（ｍ）は１にセットされる。このようにして、パケット
ｍ1は、ＲＰ（ｍ）が指定するサイクル行列（それはサ
イクル行列（＃０）５０７である）に入れられ、ＣＣ
（ｍ）及びＣＲ（ｍ）は１にインクリメントされる。
受信部５１１へ到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバフロー行列５１０内にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかをチェックするテス
トが行われる。サイクル行列５０７ー５０９にはチャン
ネルｍからのパケットは無いので、答えはＹＥＳであ
る。ステップ６０５において、ＲＰ（ｍ）＝ＴＰかどう
かチェックするテストが行われる。この時点では全ての
ポインターはゼロにセットされているので、答えはＹＥ
Ｓである。ステップ６０７において、ＣＲ（ｍ）＜ＰＲ
（ｍ）かどうかチェックするテストが行われる。ＲＰ
（ｍ）が指定するサイクル行列内のチャンネルｍからの
パケットは無いので、ＣＲ（ｍ）＝０はＰＲ（ｍ）＝２
よりも小さい。よってステップ６０８が実行され、ＣＲ
（ｍ）は１にセットされる。このようにして、パケット
ｍ1は、ＲＰ（ｍ）が指定するサイクル行列（それはサ
イクル行列（＃０）５０７である）に入れられ、ＣＣ
（ｍ）及びＣＲ（ｍ）は１にインクリメントされる。
【００５０】ステップ６０１において、パケットｍ2が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｍからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェ
ックするテストがなされる。ＲＰ（ｍ）が指定するサイ
クル行列内にチャンネルｍからのパケットが一つあるの
で、ＣＲ（ｍ）＝１、ＰＲ（ｍ）＝２となり、答えはＹ
ＥＳとなる。ステップ６０８が実行される。ＲＰ（ｍ）
が指定するサイクル行列（それはサイクル行列（＃０）
５０７）にパケットｍ2が入れられ、ＣＣ（ｍ）とＣＲ
（ｍ）は２にインクリメントされる。パケットｍ1とｍ2
の両者がサイクル行列（＃０）５０７にストアされてい
るので、チャンネルｍは他のチャンネルｉ、ｊ、ｋの二
倍の割合の優先度でもってサービスされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列５０７にチャンネルｍからの
パケットが一つあるので、答えはＮＯである。ステップ
６１０において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェ
ックするテストがなされる。ＲＰ（ｍ）が指定するサイ
クル行列内にチャンネルｍからのパケットが一つあるの
で、ＣＲ（ｍ）＝１、ＰＲ（ｍ）＝２となり、答えはＹ
ＥＳとなる。ステップ６０８が実行される。ＲＰ（ｍ）
が指定するサイクル行列（それはサイクル行列（＃０）
５０７）にパケットｍ2が入れられ、ＣＣ（ｍ）とＣＲ
（ｍ）は２にインクリメントされる。パケットｍ1とｍ2
の両者がサイクル行列（＃０）５０７にストアされてい
るので、チャンネルｍは他のチャンネルｉ、ｊ、ｋの二
倍の割合の優先度でもってサービスされる。
【００５１】ステップ６０１において、パケットｍ3が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｍからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェックす
るテストがなされる。ＲＰ（ｍ）が指定するサイクル行
列内にチャンネルｍからのパケットが二つあるので、Ｃ
Ｒ（ｍ）＝ＰＲ（ｍ）＝２となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｍ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｍ）＝０、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｍ）は１にインクリメントされ、
ＣＲ（ｍ）は１にセットされ、ＲＰ（ｍ）が指定するサ
イクルキュー（サイクル行列（＃１）５０８である）に
パケットｍ3が入れられ、ＣＣ（ｍ）は３にインクリメ
ントされる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｍからのパケッ
トが二つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェックす
るテストがなされる。ＲＰ（ｍ）が指定するサイクル行
列内にチャンネルｍからのパケットが二つあるので、Ｃ
Ｒ（ｍ）＝ＰＲ（ｍ）＝２となり、答えはＮＯとなる。
ステップ６１１において、ＲＰ（ｍ）＝ＴＰ＋２かどう
かチェックするテストがなされる。ＲＰ（ｍ）＝０、Ｔ
Ｐ＋２＝２なので、答えはＮＯであり、ステップ６０９
が実行される。ＲＰ（ｍ）は１にインクリメントされ、
ＣＲ（ｍ）は１にセットされ、ＲＰ（ｍ）が指定するサ
イクルキュー（サイクル行列（＃１）５０８である）に
パケットｍ3が入れられ、ＣＣ（ｍ）は３にインクリメ
ントされる。
【００５２】ステップ６０１において、パケットｍ4が
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｍからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェックす
るテストがなされる。ＲＰ（ｍ）が指定するサイクル行
列内にチャンネルｍからのパケットが一つあるので、Ｃ
Ｒ（ｍ）＝１、ＰＲ（ｍ）＝２となり、答えはＹＥＳと
なる。ステップ６０８が実行される。ＲＰ（ｍ）が指定
するサイクル行列（サイクル行列（＃１）５０８）にパ
ケットｍ4が入れられ、ＣＣ（ｍ）は４に、ＣＲ（ｍ）
は２にインクリメントされる。バッチ到着の終了時点で
のシステムの状態は図９に示すようになる。
受信部５１１に到着する。ステップ６０２において、Ｏ
Ｃ（ｍ）＝０かどうかチェックするテストがなされる。
オーバーフロー行列５１０にはチャンネルｍからのパケ
ットは無いので、答えはＹＥＳである。ステップ６０４
において、ＣＣ（ｍ）＝０かどうかチェックするテスト
がなされる。サイクル行列にチャンネルｍからのパケッ
トが三つあるので、答えはＮＯである。ステップ６１０
において、ＣＲ（ｍ）＜ＰＲ（ｍ）かどうかチェックす
るテストがなされる。ＲＰ（ｍ）が指定するサイクル行
列内にチャンネルｍからのパケットが一つあるので、Ｃ
Ｒ（ｍ）＝１、ＰＲ（ｍ）＝２となり、答えはＹＥＳと
なる。ステップ６０８が実行される。ＲＰ（ｍ）が指定
するサイクル行列（サイクル行列（＃１）５０８）にパ
ケットｍ4が入れられ、ＣＣ（ｍ）は４に、ＣＲ（ｍ）
は２にインクリメントされる。バッチ到着の終了時点で
のシステムの状態は図９に示すようになる。
【００５３】図９において、ポインター５０１、５０
２、５０３、５０４、５０５、５０６は、関係するチャ
ンネルｉ、ｊ、ｋ、ｍに対する受信ポインター、サイク
ルカウンタ、オーバーフローカウンタ、優先度レジス
タ、サイクルレジスタ、送信ポインタの値をそれぞれ示
している。５０７、５０８、５０９は、それぞれサイク
ル行列＃０、＃１、＃２であり、それらがストアしてい
るパケットとともに示されている。オーバーフロー行列
ＯＣ５１０も、それがストアしているパケットとともに
示されている。
２、５０３、５０４、５０５、５０６は、関係するチャ
ンネルｉ、ｊ、ｋ、ｍに対する受信ポインター、サイク
ルカウンタ、オーバーフローカウンタ、優先度レジス
タ、サイクルレジスタ、送信ポインタの値をそれぞれ示
している。５０７、５０８、５０９は、それぞれサイク
ル行列＃０、＃１、＃２であり、それらがストアしてい
るパケットとともに示されている。オーバーフロー行列
ＯＣ５１０も、それがストアしているパケットとともに
示されている。
【００５４】図７中のステップ７０１において、送信部
５１２は送信ポインターをゼロに初期化する。送信部５
１２は、サービスの開始（スロット出力の開始）である
ステップ７０２において、送信ポインターが指定するサ
イクル行列（ＣＱ＃ＴＰすなわちＣＱ（０））が空かど
うかをチェックする。上述したバッチの到着の後、送信
部５１２はシステムが空でないことを見いだす。続い
て、ステップ７０３において、送信部５１２は送信ポイ
ンターが指定するサイクル行列５０７内のライン先頭に
あるパケットをサービスする。パケットｉ1が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｉ）
が２にデクリメントされる。ステップ７０４において、
送信ポインターが指定するサイクル行列ＣＱ（ＴＰ）が
空かどうかチェックするテストを行う。答えはＮＯであ
り、ステップ７０３において、送信部５１２は送信ポイ
ンターが指定するサイクル行列（サイクル行列＃０）５
０７内のライン先頭にあるパケットをサービスする。パ
ケットｊ1が施設線５１４上に出力タイムスロットとし
て送られ、ＣＣ（ｊ）が２にデクリメントされる。ステ
ップ７０４において、送信ポインターが指定するサイク
ル行列ＣＱ（ＴＰ）が空かどうかチェックするテストを
行う。答えはＮＯであり、ステップ７０３において、送
信部５１２は送信ポインターが指定するサイクル行列
（サイクル行列＃０）５０７内のライン先頭にあるパケ
ットをサービスする。パケットｋ1が施設線５１４上に
出力タイムスロットとして送られ、ＣＣ（ｋ）が０にデ
クリメントされる。ステップ７０４において、送信ポイ
ンターが指定するサイクル行列ＣＱ（ＴＰ）が空かどう
かチェックするテストを行う。答えはＮＯであり、ステ
ップ７０３において、送信部５１２は送信ポインターが
指定するサイクル行列（サイクル行列＃０）５０７内の
ライン先頭にあるパケットをサービスする。パケットｍ
1が施設線５１４上に出力タイムスロットとして送ら
れ、ＣＣ（ｍ）が３にデクリメントされる。ステップ７
０４において、送信ポインターが指定するサイクル行列
ＣＱ（ＴＰ）が空かどうかチェックするテストを行う。
答えはＮＯであり、ステップ７０３において、送信部５
１２は送信ポインターが指定するサイクル行列（サイク
ル行列＃０）５０７内のライン先頭にあるパケットをサ
ービスする。パケットｍ2が施設線５１４上に出力タイ
ムスロットとして送られ、ＣＣ（ｍ）が２にデクリメン
トされる。ステップ７０４において、送信ポインターが
指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチェッ
クするテストを行う。答えはＹＥＳであり、ステップ７
０５において、送信部は送信ポインターをＴＰ＝１へイ
ンクリメントし、ステップ７０６において、オーバーフ
ロー行列ソーターを初期化する。第一サイクルの終了時
点でのシステムの状態は図１０に示すようになる。
５１２は送信ポインターをゼロに初期化する。送信部５
１２は、サービスの開始（スロット出力の開始）である
ステップ７０２において、送信ポインターが指定するサ
イクル行列（ＣＱ＃ＴＰすなわちＣＱ（０））が空かど
うかをチェックする。上述したバッチの到着の後、送信
部５１２はシステムが空でないことを見いだす。続い
て、ステップ７０３において、送信部５１２は送信ポイ
ンターが指定するサイクル行列５０７内のライン先頭に
あるパケットをサービスする。パケットｉ1が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｉ）
が２にデクリメントされる。ステップ７０４において、
送信ポインターが指定するサイクル行列ＣＱ（ＴＰ）が
空かどうかチェックするテストを行う。答えはＮＯであ
り、ステップ７０３において、送信部５１２は送信ポイ
ンターが指定するサイクル行列（サイクル行列＃０）５
０７内のライン先頭にあるパケットをサービスする。パ
ケットｊ1が施設線５１４上に出力タイムスロットとし
て送られ、ＣＣ（ｊ）が２にデクリメントされる。ステ
ップ７０４において、送信ポインターが指定するサイク
ル行列ＣＱ（ＴＰ）が空かどうかチェックするテストを
行う。答えはＮＯであり、ステップ７０３において、送
信部５１２は送信ポインターが指定するサイクル行列
（サイクル行列＃０）５０７内のライン先頭にあるパケ
ットをサービスする。パケットｋ1が施設線５１４上に
出力タイムスロットとして送られ、ＣＣ（ｋ）が０にデ
クリメントされる。ステップ７０４において、送信ポイ
ンターが指定するサイクル行列ＣＱ（ＴＰ）が空かどう
かチェックするテストを行う。答えはＮＯであり、ステ
ップ７０３において、送信部５１２は送信ポインターが
指定するサイクル行列（サイクル行列＃０）５０７内の
ライン先頭にあるパケットをサービスする。パケットｍ
1が施設線５１４上に出力タイムスロットとして送ら
れ、ＣＣ（ｍ）が３にデクリメントされる。ステップ７
０４において、送信ポインターが指定するサイクル行列
ＣＱ（ＴＰ）が空かどうかチェックするテストを行う。
答えはＮＯであり、ステップ７０３において、送信部５
１２は送信ポインターが指定するサイクル行列（サイク
ル行列＃０）５０７内のライン先頭にあるパケットをサ
ービスする。パケットｍ2が施設線５１４上に出力タイ
ムスロットとして送られ、ＣＣ（ｍ）が２にデクリメン
トされる。ステップ７０４において、送信ポインターが
指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチェッ
クするテストを行う。答えはＹＥＳであり、ステップ７
０５において、送信部は送信ポインターをＴＰ＝１へイ
ンクリメントし、ステップ７０６において、オーバーフ
ロー行列ソーターを初期化する。第一サイクルの終了時
点でのシステムの状態は図１０に示すようになる。
【００５５】図８中のステップ８０１において、オーバ
フロー行列５１０のソーターはそのオペレーションを開
始する。ステップ８０２において、オーバーフロー行列
５１０が空かどうかチェックするテストが行われる。答
えはＮＯであり、ステップ８０３において、オーバフロ
行列のライン先頭にあるパケットのチャンネル番号を読
み取る。ステップ８０４において、ＣＣ（ｉ）＝０かど
うかチェックするテストが行われる。サイクル行列内に
はチャンネルｉからのパケットが二つあるので答えはＮ
Ｏであり、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。チャン
ネルｉからの一つのパケットが、ＰＲ（ｉ）が指定する
サイクル行列内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝
１であり、答えはＮＯで、ステップ８１１において、Ｒ
Ｐ（ｉ）＝ＴＰ＋２かどうかチェックするテストが行わ
れる。ＲＰ（ｉ）＝２でＴＰ＋２＝３だから、答えはＮ
Ｏであり、ステップ８０９が実行される。ＲＰ（ｉ）が
３にインクリメントされ、ＣＲ（ｉ）には値１が割り当
てられ、パケットｉ4が、ＲＰ（ｉ）が指定するサイク
ル行列（サイクル行列＃０）５０７に入れられる。ステ
ップ８１３において、ＣＣ（ｉ）の値は３にインクリメ
ントされ、ＯＣ（ｉ）の値は３にデクリメントされる。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバフロ行列のラ
イン先頭にあるパケットのチャンネル番号を読み取る。
ステップ８０４において、ＣＣ（ｉ）＝０かどうかチェ
ックするテストが行われる。サイクルキュー内にはチャ
ンネルｉからのパケットが三つあるので答えはＮＯであ
り、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）
かどうかチェックするテストが行われる。チャンネルｉ
からの一つのパケットが、ＰＲ（ｉ）が指定するサイク
ル行列内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であ
り、答えはＮＯで、ステップ８１１において、ＲＰ
（ｉ）＝ＴＰ＋２かどうかチェックするテストが行われ
る。ＲＰ（ｉ）＝３でＴＰ＋２＝３だから、答えはＹＥ
Ｓでありステップ８１２が実行され、オーバーフロー行
列ソーターの動作は終了する。オーバフロー行列ソータ
ーのオペレーション終了時点でのシステムの状態は図１
１に示すようになる。
フロー行列５１０のソーターはそのオペレーションを開
始する。ステップ８０２において、オーバーフロー行列
５１０が空かどうかチェックするテストが行われる。答
えはＮＯであり、ステップ８０３において、オーバフロ
行列のライン先頭にあるパケットのチャンネル番号を読
み取る。ステップ８０４において、ＣＣ（ｉ）＝０かど
うかチェックするテストが行われる。サイクル行列内に
はチャンネルｉからのパケットが二つあるので答えはＮ
Ｏであり、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。チャン
ネルｉからの一つのパケットが、ＰＲ（ｉ）が指定する
サイクル行列内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝
１であり、答えはＮＯで、ステップ８１１において、Ｒ
Ｐ（ｉ）＝ＴＰ＋２かどうかチェックするテストが行わ
れる。ＲＰ（ｉ）＝２でＴＰ＋２＝３だから、答えはＮ
Ｏであり、ステップ８０９が実行される。ＲＰ（ｉ）が
３にインクリメントされ、ＣＲ（ｉ）には値１が割り当
てられ、パケットｉ4が、ＲＰ（ｉ）が指定するサイク
ル行列（サイクル行列＃０）５０７に入れられる。ステ
ップ８１３において、ＣＣ（ｉ）の値は３にインクリメ
ントされ、ＯＣ（ｉ）の値は３にデクリメントされる。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバフロ行列のラ
イン先頭にあるパケットのチャンネル番号を読み取る。
ステップ８０４において、ＣＣ（ｉ）＝０かどうかチェ
ックするテストが行われる。サイクルキュー内にはチャ
ンネルｉからのパケットが三つあるので答えはＮＯであ
り、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）
かどうかチェックするテストが行われる。チャンネルｉ
からの一つのパケットが、ＰＲ（ｉ）が指定するサイク
ル行列内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であ
り、答えはＮＯで、ステップ８１１において、ＲＰ
（ｉ）＝ＴＰ＋２かどうかチェックするテストが行われ
る。ＲＰ（ｉ）＝３でＴＰ＋２＝３だから、答えはＹＥ
Ｓでありステップ８１２が実行され、オーバーフロー行
列ソーターの動作は終了する。オーバフロー行列ソータ
ーのオペレーション終了時点でのシステムの状態は図１
１に示すようになる。
【００５６】ステップ７０１において、送信部５１２は
オペレーションを再開する。送信部は、サービスの開始
（スロット出力の開始）であるステップ７０２におい
て、送信ポインターが指定するサイクル行列ＣＱ（Ｔ
Ｐ）が空かどうかをチェックする。サイクル行列（＃
１）５０８は空ではないので、答えはＮＯであり、ステ
ップ７０３において、送信部５１２はライン先頭にある
パケットをサービスする。パケットｉ2が施設線５１４
上に出力タイムスロットとして送られ、ＣＣ（ｉ）が２
にデクリメントされ、ステップ７０４において、送信ポ
インターが指定するサイクル行列ＣＱ（ＴＰ）が空かど
うかチェックするテストを行う。答えはＮＯであり、ス
テップ７０３において、送信部５１２は送信ポインター
が指定するサイクル行列（サイクル行列＃１）５０８内
のライン先頭にあるパケットをサービスする。パケット
ｊ2が施設線５１４上に出力タイムスロットとして送ら
れ、ＣＣ（ｊ）が１にデクリメントされ、ステップ７０
４において、送信ポインターが指定するサイクル行列Ｃ
Ｑ（ＴＰ）が空かどうかチェックするテストを行う。答
えはＮＯであり、ステップ７０３において、送信部５１
２は送信ポインターが指定するサイクル行列（サイクル
行列＃１）５０８内のライン先頭にあるパケットをサー
ビスする。パケットｍ3が施設線５１４上に出力タイム
スロットとして送られ、ＣＣ（ｍ）が１にデクリメント
され、ステップ７０４において、送信ポインターが指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかチェックす
るテストを行う。答えはＮＯであり、ステップ７０３に
おいて、送信部５１２は送信ポインターが指定するサイ
クル行列（サイクル行列＃１）５０８内のライン先頭に
あるパケットをサービスする。パケットｍ4が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｍ）
が０にデクリメントされ、ステップ７０４において、送
信ポインターが指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかチェックするテストを行う。答えはＹＥＳであ
り、ステップ７０５において、送信部は送信ポインター
をＴＰ＝２へインクリメントし、ステップ７０６におい
て、オーバーフロー行列ソーターを初期化する。第二サ
イクルの終了時点でのシステムの状態は、図１２に示す
ようになる。
オペレーションを再開する。送信部は、サービスの開始
（スロット出力の開始）であるステップ７０２におい
て、送信ポインターが指定するサイクル行列ＣＱ（Ｔ
Ｐ）が空かどうかをチェックする。サイクル行列（＃
１）５０８は空ではないので、答えはＮＯであり、ステ
ップ７０３において、送信部５１２はライン先頭にある
パケットをサービスする。パケットｉ2が施設線５１４
上に出力タイムスロットとして送られ、ＣＣ（ｉ）が２
にデクリメントされ、ステップ７０４において、送信ポ
インターが指定するサイクル行列ＣＱ（ＴＰ）が空かど
うかチェックするテストを行う。答えはＮＯであり、ス
テップ７０３において、送信部５１２は送信ポインター
が指定するサイクル行列（サイクル行列＃１）５０８内
のライン先頭にあるパケットをサービスする。パケット
ｊ2が施設線５１４上に出力タイムスロットとして送ら
れ、ＣＣ（ｊ）が１にデクリメントされ、ステップ７０
４において、送信ポインターが指定するサイクル行列Ｃ
Ｑ（ＴＰ）が空かどうかチェックするテストを行う。答
えはＮＯであり、ステップ７０３において、送信部５１
２は送信ポインターが指定するサイクル行列（サイクル
行列＃１）５０８内のライン先頭にあるパケットをサー
ビスする。パケットｍ3が施設線５１４上に出力タイム
スロットとして送られ、ＣＣ（ｍ）が１にデクリメント
され、ステップ７０４において、送信ポインターが指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかチェックす
るテストを行う。答えはＮＯであり、ステップ７０３に
おいて、送信部５１２は送信ポインターが指定するサイ
クル行列（サイクル行列＃１）５０８内のライン先頭に
あるパケットをサービスする。パケットｍ4が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｍ）
が０にデクリメントされ、ステップ７０４において、送
信ポインターが指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかチェックするテストを行う。答えはＹＥＳであ
り、ステップ７０５において、送信部は送信ポインター
をＴＰ＝２へインクリメントし、ステップ７０６におい
て、オーバーフロー行列ソーターを初期化する。第二サ
イクルの終了時点でのシステムの状態は、図１２に示す
ようになる。
【００５７】ステップ８０１において、オーバフロー行
列５１０のソーターはそのオペレーションを開始する。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバフロー行列の
ライン先頭にあるパケットのチャンネル番号（この場合
はｉ）を読み取る。ステップ８０４において、ＣＣ
（ｉ）＝０かどうかチェックするテストが行われる。サ
イクル行列内にはチャンネルｉからのパケットが二つあ
るので答えはＮＯであり、ステップ８１０において、Ｃ
Ｒ（ｉ）＜ＰＲ（ｉ）かどうかチェックするテストが行
われる。チャンネルｉからの一つのパケットが、ＰＲ
（ｉ）が指定するサイクル行列内にあるので、ＣＲ
（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯで、ステッ
プ８１１において、ＲＰ（ｉ）＝ＴＰ＋２かどうかチェ
ックするテストが行われる。ＲＰ（ｉ）＝３でＴＰ＋２
＝４だから、答えはＮＯでありステップ８０９が実行さ
れる。ＲＰ（ｉ）が４にインクリメントされ、ＣＲ
（ｉ）には値１が割り当てられ、パケットｉ5が、ＲＰ
（ｉ）が指定するサイクル行列（サイクル行列＃１）５
０８に入れられる。ステップ８１３において、ＣＣ
（ｉ）の値は３にインクリメントされ、ＯＣ（ｉ）の値
は２にデクリメントされる。ステップ８０２において、
オーバーフロー行列５１０が空かどうかチェックするテ
ストが行われる。答えはＮＯであり、ステップ８０３に
おいて、オーバーフロー行列のライン先頭にあるパケッ
トのチャンネル番号（この場合はｉ）を読み取る。ステ
ップ８０４において、ＣＣ（ｉ）＝０かどうかチェック
するテストが行われる。サイクル行列内にはチャンネル
ｉからのパケットが三つあるので答えはＮＯであり、ス
テップ８１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどう
かチェックするテストが行われる。チャンネルｉからの
一つのパケットが、ＰＲ（ｉ）が指定するサイクル行列
内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であり、答
えはＮＯで、ステップ８１１において、ＲＰ（ｉ）＝Ｔ
Ｐ＋２かどうかチェックするテストが行われる。ＲＰ
（ｉ）＝４でＴＰ＋２＝４だから、答えはＹＥＳであり
ステップ８１２が実行され、オーバーフロー行列ソータ
ーの動作は終了する。オーバーフロー行列ソーターのオ
ペレーション終了時点でのシステムの状態は図１３に示
すようになる。
列５１０のソーターはそのオペレーションを開始する。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバフロー行列の
ライン先頭にあるパケットのチャンネル番号（この場合
はｉ）を読み取る。ステップ８０４において、ＣＣ
（ｉ）＝０かどうかチェックするテストが行われる。サ
イクル行列内にはチャンネルｉからのパケットが二つあ
るので答えはＮＯであり、ステップ８１０において、Ｃ
Ｒ（ｉ）＜ＰＲ（ｉ）かどうかチェックするテストが行
われる。チャンネルｉからの一つのパケットが、ＰＲ
（ｉ）が指定するサイクル行列内にあるので、ＣＲ
（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯで、ステッ
プ８１１において、ＲＰ（ｉ）＝ＴＰ＋２かどうかチェ
ックするテストが行われる。ＲＰ（ｉ）＝３でＴＰ＋２
＝４だから、答えはＮＯでありステップ８０９が実行さ
れる。ＲＰ（ｉ）が４にインクリメントされ、ＣＲ
（ｉ）には値１が割り当てられ、パケットｉ5が、ＲＰ
（ｉ）が指定するサイクル行列（サイクル行列＃１）５
０８に入れられる。ステップ８１３において、ＣＣ
（ｉ）の値は３にインクリメントされ、ＯＣ（ｉ）の値
は２にデクリメントされる。ステップ８０２において、
オーバーフロー行列５１０が空かどうかチェックするテ
ストが行われる。答えはＮＯであり、ステップ８０３に
おいて、オーバーフロー行列のライン先頭にあるパケッ
トのチャンネル番号（この場合はｉ）を読み取る。ステ
ップ８０４において、ＣＣ（ｉ）＝０かどうかチェック
するテストが行われる。サイクル行列内にはチャンネル
ｉからのパケットが三つあるので答えはＮＯであり、ス
テップ８１０において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどう
かチェックするテストが行われる。チャンネルｉからの
一つのパケットが、ＰＲ（ｉ）が指定するサイクル行列
内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であり、答
えはＮＯで、ステップ８１１において、ＲＰ（ｉ）＝Ｔ
Ｐ＋２かどうかチェックするテストが行われる。ＲＰ
（ｉ）＝４でＴＰ＋２＝４だから、答えはＹＥＳであり
ステップ８１２が実行され、オーバーフロー行列ソータ
ーの動作は終了する。オーバーフロー行列ソーターのオ
ペレーション終了時点でのシステムの状態は図１３に示
すようになる。
【００５８】送信部５１２はオペレーションを再開す
る。送信部は、サービスの開始（スロット出力の開始）
であるステップ７０２において、送信ポインターが指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかをチェック
する。サイクル行列（＃２）５０９は空ではないので、
答えはＮＯであり、ステップ７０３において、送信部５
１２はライン先頭にあるパケットをサービスする。パケ
ットｉ3が施設線５１４上に出力タイムスロットとして
送られ、ＣＣ（ｉ）が２にデクリメントされ、ステップ
７０４において、送信ポインターが指定するサイクル行
列ＣＱ（ＴＰ）が空かどうかチェックするテストを行
う。答えはＮＯであり、ステップ７０３において、送信
部５１２は送信ポインターが指定するサイクル行列（サ
イクル行列＃２）５０９内のライン先頭にあるパケット
をサービスする。パケットｊ3が施設線５１４上に出力
タイムスロットとして送られ、ＣＣ（ｊ）が０にデクリ
メントされ、ステップ７０４において、送信ポインター
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチェ
ックするテストを行う。答えはＹＥＳであり、ステップ
７０５において、送信部は送信ポインターをＴＰ＝３へ
インクリメントし、ステップ７０６において、オーバー
フロー行列ソーターを初期化する。第三サイクルの終了
時点でのシステムの状態は、図１４に示すようになる。
る。送信部は、サービスの開始（スロット出力の開始）
であるステップ７０２において、送信ポインターが指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかをチェック
する。サイクル行列（＃２）５０９は空ではないので、
答えはＮＯであり、ステップ７０３において、送信部５
１２はライン先頭にあるパケットをサービスする。パケ
ットｉ3が施設線５１４上に出力タイムスロットとして
送られ、ＣＣ（ｉ）が２にデクリメントされ、ステップ
７０４において、送信ポインターが指定するサイクル行
列ＣＱ（ＴＰ）が空かどうかチェックするテストを行
う。答えはＮＯであり、ステップ７０３において、送信
部５１２は送信ポインターが指定するサイクル行列（サ
イクル行列＃２）５０９内のライン先頭にあるパケット
をサービスする。パケットｊ3が施設線５１４上に出力
タイムスロットとして送られ、ＣＣ（ｊ）が０にデクリ
メントされ、ステップ７０４において、送信ポインター
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチェ
ックするテストを行う。答えはＹＥＳであり、ステップ
７０５において、送信部は送信ポインターをＴＰ＝３へ
インクリメントし、ステップ７０６において、オーバー
フロー行列ソーターを初期化する。第三サイクルの終了
時点でのシステムの状態は、図１４に示すようになる。
【００５９】ステップ８０２において、オーバーフロー
行列５１０が空かどうかチェックするテストが行われ
る。答えはＮＯであり、ステップ８０３において、オー
バーフロー行列のライン先頭にあるパケットのチャンネ
ル番号（この場合はｉ）を読み取る。ステップ８０４に
おいて、ＣＣ（ｉ）＝０かどうかチェックするテストが
行われる。サイクル行列内にはチャンネルｉからのパケ
ットが二つあるので答えはＮＯであり、ステップ８１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストが行われる。チャンネルｉからの一つのパケッ
トが、ＰＲ（ｉ）が指定するサイクル行列内にあるの
で、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯ
で、ステップ８１１において、ＲＰ（ｉ）＝ＴＰ＋２か
どうかチェックするテストが行われる。ＲＰ（ｉ）＝４
でＴＰ＋２＝５だから、答えはＮＯでありステップ８０
９が実行される。ＲＰ（ｉ）が５にインクリメントさ
れ、ＣＲ（ｉ）には値１が割り当てられ、パケットｉ6
が、ＲＰ（ｉ）が指定するサイクルキュー（サイクル行
列＃２）５０９に入れられる。ステップ８１３におい
て、ＣＣ（ｉ）の値は３にインクリメントされ、ＯＣ
（ｉ）の値は１にデクリメントされる。ステップ８０２
において、オーバーフロー行列５１０が空かどうかチェ
ックするテストが行われる。答えはＮＯであり、ステッ
プ８０３において、オーバーフロー行列のライン先頭に
あるパケットのチャンネル番号（この場合はｉ）を読み
取る。ステップ８０４において、ＣＣ（ｉ）＝０かどう
かチェックするテストが行われる。サイクル行列内には
チャンネルｉからのパケットが三つあるので答えはＮＯ
であり、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。チャン
ネルｉからの一つのパケットが、ＰＲ（ｉ）が指定する
サイクルキュー内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）
＝１であり、答えはＮＯで、ステップ８１１において、
ＲＰ（ｉ）＝ＴＰ＋２かどうかチェックするテストが行
われる。ＲＰ（ｉ）＝５でＴＰ＋２＝５だから、答えは
ＹＥＳでありステップ８１２が実行され、オーバーフロ
ー行列ソーターは終了する。
行列５１０が空かどうかチェックするテストが行われ
る。答えはＮＯであり、ステップ８０３において、オー
バーフロー行列のライン先頭にあるパケットのチャンネ
ル番号（この場合はｉ）を読み取る。ステップ８０４に
おいて、ＣＣ（ｉ）＝０かどうかチェックするテストが
行われる。サイクル行列内にはチャンネルｉからのパケ
ットが二つあるので答えはＮＯであり、ステップ８１０
において、ＣＲ（ｉ）＜ＰＲ（ｉ）かどうかチェックす
るテストが行われる。チャンネルｉからの一つのパケッ
トが、ＰＲ（ｉ）が指定するサイクル行列内にあるの
で、ＣＲ（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯ
で、ステップ８１１において、ＲＰ（ｉ）＝ＴＰ＋２か
どうかチェックするテストが行われる。ＲＰ（ｉ）＝４
でＴＰ＋２＝５だから、答えはＮＯでありステップ８０
９が実行される。ＲＰ（ｉ）が５にインクリメントさ
れ、ＣＲ（ｉ）には値１が割り当てられ、パケットｉ6
が、ＲＰ（ｉ）が指定するサイクルキュー（サイクル行
列＃２）５０９に入れられる。ステップ８１３におい
て、ＣＣ（ｉ）の値は３にインクリメントされ、ＯＣ
（ｉ）の値は１にデクリメントされる。ステップ８０２
において、オーバーフロー行列５１０が空かどうかチェ
ックするテストが行われる。答えはＮＯであり、ステッ
プ８０３において、オーバーフロー行列のライン先頭に
あるパケットのチャンネル番号（この場合はｉ）を読み
取る。ステップ８０４において、ＣＣ（ｉ）＝０かどう
かチェックするテストが行われる。サイクル行列内には
チャンネルｉからのパケットが三つあるので答えはＮＯ
であり、ステップ８１０において、ＣＲ（ｉ）＜ＰＲ
（ｉ）かどうかチェックするテストが行われる。チャン
ネルｉからの一つのパケットが、ＰＲ（ｉ）が指定する
サイクルキュー内にあるので、ＣＲ（ｉ）＝ＰＲ（ｉ）
＝１であり、答えはＮＯで、ステップ８１１において、
ＲＰ（ｉ）＝ＴＰ＋２かどうかチェックするテストが行
われる。ＲＰ（ｉ）＝５でＴＰ＋２＝５だから、答えは
ＹＥＳでありステップ８１２が実行され、オーバーフロ
ー行列ソーターは終了する。
【００６０】次に、チャンネルｊから単独のパケットｊ
5が受信部に到着したと想定する。ステップ６０１にお
いて、図１５に示されたようなシステムの状態である。
ステップ６０２において、ＯＣ（ｊ）＝０かどうかチェ
ックするテストが行われる。オーバーフロー行列内には
チャンネルｊからのパケットが一つあるので、答えはＮ
Ｏであり、ステップ６０３が実行される。パケットｊ5
がオーバーフロー行列５１０に挿入され、ＯＣ（ｊ）の
値が２にインクリメントされる。オーバフロー行列ソー
ターのオペレーション終了後、単独パケットが到着した
時点でのシステムは図１６に示すようになる。
5が受信部に到着したと想定する。ステップ６０１にお
いて、図１５に示されたようなシステムの状態である。
ステップ６０２において、ＯＣ（ｊ）＝０かどうかチェ
ックするテストが行われる。オーバーフロー行列内には
チャンネルｊからのパケットが一つあるので、答えはＮ
Ｏであり、ステップ６０３が実行される。パケットｊ5
がオーバーフロー行列５１０に挿入され、ＯＣ（ｊ）の
値が２にインクリメントされる。オーバフロー行列ソー
ターのオペレーション終了後、単独パケットが到着した
時点でのシステムは図１６に示すようになる。
【００６１】送信部５１２はオペレーションを再開す
る。送信部５１２は、サービスの開始（スロット出力の
開始）であるステップ７０２において、送信ポインター
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかをチ
ェックする。サイクル行列（＃０）５０７は空ではない
ので、答えはＮＯであり、ステップ７０３において、送
信部５１２はライン先頭にあるパケットをサービスす
る。パケットｉ4が施設線５１４上に出力タイムスロッ
トとして送られ、ＣＣ（ｉ）が２にデクリメントされ、
ステップ７０４において、送信ポインターが指定するサ
イクル行列ＣＱ（ＴＰ）が空かどうかチェックするテス
トを行う。答えはＹＥＳであり、ステップ７０５におい
て、送信部は送信ポインターをＴＰ＝４へインクリメン
トし、ステップ７０６において、オーバーフロー行列ソ
ーターを初期化する。第四サイクルの終了時点でのシス
テムの状態は図１７に示すようになる。
る。送信部５１２は、サービスの開始（スロット出力の
開始）であるステップ７０２において、送信ポインター
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかをチ
ェックする。サイクル行列（＃０）５０７は空ではない
ので、答えはＮＯであり、ステップ７０３において、送
信部５１２はライン先頭にあるパケットをサービスす
る。パケットｉ4が施設線５１４上に出力タイムスロッ
トとして送られ、ＣＣ（ｉ）が２にデクリメントされ、
ステップ７０４において、送信ポインターが指定するサ
イクル行列ＣＱ（ＴＰ）が空かどうかチェックするテス
トを行う。答えはＹＥＳであり、ステップ７０５におい
て、送信部は送信ポインターをＴＰ＝４へインクリメン
トし、ステップ７０６において、オーバーフロー行列ソ
ーターを初期化する。第四サイクルの終了時点でのシス
テムの状態は図１７に示すようになる。
【００６２】ステップ８０１において、オーバフロー行
列５１０のソーターはそのオペレーションを開始する。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバーフロー行列
のライン先頭にあるパケットのチャンネル番号（この場
合はｉ）を読み取る。ステップ８０４において、ＣＣ
（ｉ）＝０かどうかチェックするテストが行われる。サ
イクル行列内にはチャンネルｉからのパケットが二つあ
るので答えはＮＯであり、ステップ８１０において、Ｃ
Ｒ（ｉ）＜ＰＲ（ｉ）かどうかチェックするテストが行
われる。チャンネルｉからの一つのパケットが、ＰＲ
（ｉ）が指定するサイクルキュー内にあるので、ＣＲ
（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯで、ステッ
プ８１１において、ＲＰ（ｉ）＝ＴＰ＋２かどうかチェ
ックするテストが行われる。ＲＰ（ｉ）＝５でＴＰ＋２
＝６だから、答えはＮＯでありステップ８０９が実行さ
れる。ＲＰ（ｉ）が６にインクリメントされ、ＣＲ
（ｉ）には値１が割り当てられ、パケットｉ7が、ＲＰ
（ｉ）が指定するサイクル行列（サイクル行列＃０）５
０７に入れられる。ステップ８１３において、ＣＣ
（ｉ）の値は３にインクリメントされ、ＯＣ（ｉ）の値
は０にデクリメントされる。ステップ８０２において、
オーバーフロー行列５１０が空かどうかチェックするテ
ストが行われる。答えはＮＯであり、ステップ８０３に
おいて、オーバフロ行列のライン先頭にあるパケットの
チャンネル番号（この場合はｊ）を読み取る。ステップ
８０４において、ＣＣ（ｊ）＝０かどうかチェックする
テストが行われる。サイクル行列内にはチャンネルｊか
らのパケットが無いので、答えはＹＥＳであり、ステッ
プ８０５において、ＲＰ（ｊ）＝ＴＰかどうかチェック
するテストが行われる。ＲＰ（ｊ）＝２でＴＰ＝４なの
で、答えはＮＯで、ステップ８０６が実行される。ＲＰ
（ｊ）は４にセットされ、ＣＲ（ｊ）は１にセットさ
れ、パケットｊ4が、ＲＰ（ｊ）が指定するサイクル行
列に挿入される。ステップ８１３において、ＯＣ（ｊ）
は１にデクリメントされ、ＣＣ（ｊ）は１にインクリメ
ントされる。ステップ８０２において、オーバーフロー
行列５１０が空かどうかチェックするテストが行われ
る。答えはＮＯであり、ステップ８０３において、オー
バーフロー行列のライン先頭にあるパケットのチャンネ
ル番号（この場合はｊ）を読み取る。ステップ８０４に
おいて、ＣＣ（ｊ）＝０かどうかチェックするテストが
行われる。サイクル行列内にはチャンネルｊからのパケ
ットが一つあるので答えはＮＯであり、ステップ８１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストが行われる。チャンネルｊからの一つのパケッ
トが、ＰＲ（ｊ）が指定するサイクル行列内にあるの
で、ＣＲ（ｊ）＝ＰＲ（ｊ）＝１であり、答えはＮＯ
で、ステップ８１１において、ＲＰ（ｊ）＝ＴＰ＋２か
どうかチェックするテストが行われる。ＲＰ（ｊ）＝４
でＴＰ＋２＝６だから、答えはＮＯでありステップ８０
９が実行される。ＲＰ（ｊ）が５にインクリメントさ
れ、ＣＲ（ｊ）には値１が割り当てられ、パケットｊ5
が、ＲＰ（ｊ）が指定するサイクル行列（サイクル行列
＃２）５０９に入れられる。ステップ８１３において、
ＣＣ（ｊ）の値は２にインクリメントされ、ＯＣ（ｊ）
の値は０にデクリメントされる。ステップ８０２におい
て、オーバーフロー行列５１０が空かどうかチェックす
るテストが行われる。答えはＹＥＳであり、ステップ８
１２において、オーバーフロー行列ソーターは終了す
る。オーバーフロー行列ソーターのオペレーション終了
時点でのシステムの状態は、図１８に示すようになる。
列５１０のソーターはそのオペレーションを開始する。
ステップ８０２において、オーバーフロー行列５１０が
空かどうかチェックするテストが行われる。答えはＮＯ
であり、ステップ８０３において、オーバーフロー行列
のライン先頭にあるパケットのチャンネル番号（この場
合はｉ）を読み取る。ステップ８０４において、ＣＣ
（ｉ）＝０かどうかチェックするテストが行われる。サ
イクル行列内にはチャンネルｉからのパケットが二つあ
るので答えはＮＯであり、ステップ８１０において、Ｃ
Ｒ（ｉ）＜ＰＲ（ｉ）かどうかチェックするテストが行
われる。チャンネルｉからの一つのパケットが、ＰＲ
（ｉ）が指定するサイクルキュー内にあるので、ＣＲ
（ｉ）＝ＰＲ（ｉ）＝１であり、答えはＮＯで、ステッ
プ８１１において、ＲＰ（ｉ）＝ＴＰ＋２かどうかチェ
ックするテストが行われる。ＲＰ（ｉ）＝５でＴＰ＋２
＝６だから、答えはＮＯでありステップ８０９が実行さ
れる。ＲＰ（ｉ）が６にインクリメントされ、ＣＲ
（ｉ）には値１が割り当てられ、パケットｉ7が、ＲＰ
（ｉ）が指定するサイクル行列（サイクル行列＃０）５
０７に入れられる。ステップ８１３において、ＣＣ
（ｉ）の値は３にインクリメントされ、ＯＣ（ｉ）の値
は０にデクリメントされる。ステップ８０２において、
オーバーフロー行列５１０が空かどうかチェックするテ
ストが行われる。答えはＮＯであり、ステップ８０３に
おいて、オーバフロ行列のライン先頭にあるパケットの
チャンネル番号（この場合はｊ）を読み取る。ステップ
８０４において、ＣＣ（ｊ）＝０かどうかチェックする
テストが行われる。サイクル行列内にはチャンネルｊか
らのパケットが無いので、答えはＹＥＳであり、ステッ
プ８０５において、ＲＰ（ｊ）＝ＴＰかどうかチェック
するテストが行われる。ＲＰ（ｊ）＝２でＴＰ＝４なの
で、答えはＮＯで、ステップ８０６が実行される。ＲＰ
（ｊ）は４にセットされ、ＣＲ（ｊ）は１にセットさ
れ、パケットｊ4が、ＲＰ（ｊ）が指定するサイクル行
列に挿入される。ステップ８１３において、ＯＣ（ｊ）
は１にデクリメントされ、ＣＣ（ｊ）は１にインクリメ
ントされる。ステップ８０２において、オーバーフロー
行列５１０が空かどうかチェックするテストが行われ
る。答えはＮＯであり、ステップ８０３において、オー
バーフロー行列のライン先頭にあるパケットのチャンネ
ル番号（この場合はｊ）を読み取る。ステップ８０４に
おいて、ＣＣ（ｊ）＝０かどうかチェックするテストが
行われる。サイクル行列内にはチャンネルｊからのパケ
ットが一つあるので答えはＮＯであり、ステップ８１０
において、ＣＲ（ｊ）＜ＰＲ（ｊ）かどうかチェックす
るテストが行われる。チャンネルｊからの一つのパケッ
トが、ＰＲ（ｊ）が指定するサイクル行列内にあるの
で、ＣＲ（ｊ）＝ＰＲ（ｊ）＝１であり、答えはＮＯ
で、ステップ８１１において、ＲＰ（ｊ）＝ＴＰ＋２か
どうかチェックするテストが行われる。ＲＰ（ｊ）＝４
でＴＰ＋２＝６だから、答えはＮＯでありステップ８０
９が実行される。ＲＰ（ｊ）が５にインクリメントさ
れ、ＣＲ（ｊ）には値１が割り当てられ、パケットｊ5
が、ＲＰ（ｊ）が指定するサイクル行列（サイクル行列
＃２）５０９に入れられる。ステップ８１３において、
ＣＣ（ｊ）の値は２にインクリメントされ、ＯＣ（ｊ）
の値は０にデクリメントされる。ステップ８０２におい
て、オーバーフロー行列５１０が空かどうかチェックす
るテストが行われる。答えはＹＥＳであり、ステップ８
１２において、オーバーフロー行列ソーターは終了す
る。オーバーフロー行列ソーターのオペレーション終了
時点でのシステムの状態は、図１８に示すようになる。
【００６３】送信部５１２はオペレーションを再開す
る。送信部は、サービスの開始（スロット出力の開始）
であるステップ７０２において、送信ポインター５０６
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかをチ
ェックする。サイクル行列（＃１）５０８は空ではない
ので、答えはＮＯであり、ステップ７０３において、送
信部５１２はライン先頭にあるパケットをサービスす
る。パケットｉ5が施設線５１４上に出力タイムスロッ
トとして送られ、ＣＣ（ｉ）が２にデクリメントされ、
ステップ７０４において、送信ポインター５０６が指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかチェックす
るテストを行う。答えはＮＯであり、ステップ７０３に
おいて、送信部５１２は送信ポインターが指定するサイ
クル行列（サイクル行列＃１）５０８内のライン先頭に
あるパケットをサービスする。パケットｊ4が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｊ）
が１にデクリメントされ、ステップ７０４において、送
信ポインター５０６が指定するサイクル行列ＣＱ（Ｔ
Ｐ）が空かどうかチェックするテストを行う。答えはＹ
ＥＳであり、ステップ７０５において、送信部は送信ポ
インターをＴＰ＝５へインクリメントし、ステップ７０
６において、オーバーフロー行列ソーターを初期化す
る。第五サイクルの終了時点でのシステムの状態は、図
１９に示すようになる。
る。送信部は、サービスの開始（スロット出力の開始）
であるステップ７０２において、送信ポインター５０６
が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかをチ
ェックする。サイクル行列（＃１）５０８は空ではない
ので、答えはＮＯであり、ステップ７０３において、送
信部５１２はライン先頭にあるパケットをサービスす
る。パケットｉ5が施設線５１４上に出力タイムスロッ
トとして送られ、ＣＣ（ｉ）が２にデクリメントされ、
ステップ７０４において、送信ポインター５０６が指定
するサイクル行列ＣＱ（ＴＰ）が空かどうかチェックす
るテストを行う。答えはＮＯであり、ステップ７０３に
おいて、送信部５１２は送信ポインターが指定するサイ
クル行列（サイクル行列＃１）５０８内のライン先頭に
あるパケットをサービスする。パケットｊ4が施設線５
１４上に出力タイムスロットとして送られ、ＣＣ（ｊ）
が１にデクリメントされ、ステップ７０４において、送
信ポインター５０６が指定するサイクル行列ＣＱ（Ｔ
Ｐ）が空かどうかチェックするテストを行う。答えはＹ
ＥＳであり、ステップ７０５において、送信部は送信ポ
インターをＴＰ＝５へインクリメントし、ステップ７０
６において、オーバーフロー行列ソーターを初期化す
る。第五サイクルの終了時点でのシステムの状態は、図
１９に示すようになる。
【００６４】ステップ８０１において、オーバーフロー
行列５１０のソーターはそのオペレーションを開始す
る。ステップ８０２において、オーバーフロー行列５１
０が空かどうかチェックするテストが行われる。答えは
ＹＥＳであり、ステップ８１２において、オーバーフロ
ー行列ソーターは終了する。送信部５１２はオペレーシ
ョンを再開する。送信部は、サービスの開始（スロット
出力の開始）であるステップ７０２において、送信ポイ
ンター５０６が指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかをチェックする。サイクル行列（＃２）５０９
は空ではないので、答えはＮＯであり、ステップ７０３
において、送信部５１２はライン先頭にあるパケットを
サービスする。パケットｉ6が施設線５１４上に出力タ
イムスロットとして送られ、ＣＣ（ｉ）が１にデクリメ
ントされ、ステップ７０４において、送信ポインター５
０６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうか
チェックするテストを行う。答えはＮＯであり、ステッ
プ７０３において、送信部５１２は送信ポインターが指
定するサイクル行列内のライン先頭にあるパケットをサ
ービスする。パケットｊ5が施設線５１４上に出力タイ
ムスロットとして送られ、ＣＣ（ｊ）が０にデクリメン
トされ、ステップ７０４において、送信ポインター５０
６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチ
ェックするテストを行う。答えはＹＥＳであり、ステッ
プ７０５において、送信部は送信ポインター５０６をＴ
Ｐ＝６へインクリメントし、ステップ７０６において、
オーバーフロー行列ソーターを初期化する。第六サイク
ルの終了時点でのシステムの状態は、図２０に示すよう
になる。
行列５１０のソーターはそのオペレーションを開始す
る。ステップ８０２において、オーバーフロー行列５１
０が空かどうかチェックするテストが行われる。答えは
ＹＥＳであり、ステップ８１２において、オーバーフロ
ー行列ソーターは終了する。送信部５１２はオペレーシ
ョンを再開する。送信部は、サービスの開始（スロット
出力の開始）であるステップ７０２において、送信ポイ
ンター５０６が指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかをチェックする。サイクル行列（＃２）５０９
は空ではないので、答えはＮＯであり、ステップ７０３
において、送信部５１２はライン先頭にあるパケットを
サービスする。パケットｉ6が施設線５１４上に出力タ
イムスロットとして送られ、ＣＣ（ｉ）が１にデクリメ
ントされ、ステップ７０４において、送信ポインター５
０６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうか
チェックするテストを行う。答えはＮＯであり、ステッ
プ７０３において、送信部５１２は送信ポインターが指
定するサイクル行列内のライン先頭にあるパケットをサ
ービスする。パケットｊ5が施設線５１４上に出力タイ
ムスロットとして送られ、ＣＣ（ｊ）が０にデクリメン
トされ、ステップ７０４において、送信ポインター５０
６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうかチ
ェックするテストを行う。答えはＹＥＳであり、ステッ
プ７０５において、送信部は送信ポインター５０６をＴ
Ｐ＝６へインクリメントし、ステップ７０６において、
オーバーフロー行列ソーターを初期化する。第六サイク
ルの終了時点でのシステムの状態は、図２０に示すよう
になる。
【００６５】ステップ８０１において、オーバーフロー
行列５１０のソーターはそのオペレーションを開始す
る。ステップ８０２において、オーバーフロー行列５１
０が空かどうかチェックするテストが行われる。答えは
ＹＥＳであり、ステップ８１２において、オーバーフロ
ー行列ソーターは終了する。送信部５１２はオペレーシ
ョンを再開する。送信部は、サービスの開始（スロット
出力の開始）であるステップ７０２において、送信ポイ
ンター５０６が指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかをチェックする。サイクル行列（＃０）５０７
は空ではないので、答えはＮＯであり、ステップ７０３
において、送信部５１２はライン先頭にあるパケットを
サービスする。パケットｉ7が施設線５１４上に出力タ
イムスロットとして送られ、ＣＣ（ｉ）が０にデクリメ
ントされ、ステップ７０４において、送信ポインター５
０６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうか
チェックするテストを行う。答えはＹＥＳであり、ステ
ップ７０５において、送信部は送信ポインター５０６を
ＴＰ＝７へインクリメントし、ステップ７０６におい
て、オーバーフロー行列ソーターを初期化する。
行列５１０のソーターはそのオペレーションを開始す
る。ステップ８０２において、オーバーフロー行列５１
０が空かどうかチェックするテストが行われる。答えは
ＹＥＳであり、ステップ８１２において、オーバーフロ
ー行列ソーターは終了する。送信部５１２はオペレーシ
ョンを再開する。送信部は、サービスの開始（スロット
出力の開始）であるステップ７０２において、送信ポイ
ンター５０６が指定するサイクル行列ＣＱ（ＴＰ）が空
かどうかをチェックする。サイクル行列（＃０）５０７
は空ではないので、答えはＮＯであり、ステップ７０３
において、送信部５１２はライン先頭にあるパケットを
サービスする。パケットｉ7が施設線５１４上に出力タ
イムスロットとして送られ、ＣＣ（ｉ）が０にデクリメ
ントされ、ステップ７０４において、送信ポインター５
０６が指定するサイクル行列ＣＱ（ＴＰ）が空かどうか
チェックするテストを行う。答えはＹＥＳであり、ステ
ップ７０５において、送信部は送信ポインター５０６を
ＴＰ＝７へインクリメントし、ステップ７０６におい
て、オーバーフロー行列ソーターを初期化する。
【００６６】最終的に、システムは空になる。ステップ
８０２において、オーバフロー行列ソーターはオーバー
フロー行列が空であることを見いだし、ステップ８１２
において、オペレーションを終了する。送信部はオペレ
ーションを再開し、ステップ７０２におけるチェックを
新たなパケット到着まで続ける。従って、システムから
のパケットの出力順序は、ｉ1、ｊ1、ｋ1、ｍ1、ｍ
2（第一サイクル）；ｉ2、ｊ2、ｍ3、ｍ4（第二サイク
ル）；ｉ3、ｊ3（第三サイクル）；ｉ4（第四サイク
ル）；ｉ5、ｊ4（第五サイクル）；ｉ6、ｊ5（第六サイ
クル）；ｉ7（第七サイクル）である。オーバーフロー
行列による歪みが無い場合の順序は、ｉ1、ｊ1、ｋ1、
ｍ1、ｍ2（第一サイクル）；ｉ2、ｊ2、ｍ3、ｍ4（第二
サイクル）；ｉ3、ｊ3（第三サイクル）；ｉ4、ｊ4（第
四サイクル）；ｉ5、ｊ5（第五サイクル）；ｉ6（第六
サイクル）；ｉ7（第七サイクル）となる。ここで、パ
ケットｊ4及びｊ5がサイクルをはずれている。サイクル
行列の数よりも長いバッチは、その中の幾つかのパケッ
トがサイクルをばずれる可能性がある。この現象がシス
テムにとって良い場合もあるし、悪い場合もある。サイ
クル行列の数及び各サイクル行列サイズの選択は、技術
や性能のガイドラインにより決められるべきである。
８０２において、オーバフロー行列ソーターはオーバー
フロー行列が空であることを見いだし、ステップ８１２
において、オペレーションを終了する。送信部はオペレ
ーションを再開し、ステップ７０２におけるチェックを
新たなパケット到着まで続ける。従って、システムから
のパケットの出力順序は、ｉ1、ｊ1、ｋ1、ｍ1、ｍ
2（第一サイクル）；ｉ2、ｊ2、ｍ3、ｍ4（第二サイク
ル）；ｉ3、ｊ3（第三サイクル）；ｉ4（第四サイク
ル）；ｉ5、ｊ4（第五サイクル）；ｉ6、ｊ5（第六サイ
クル）；ｉ7（第七サイクル）である。オーバーフロー
行列による歪みが無い場合の順序は、ｉ1、ｊ1、ｋ1、
ｍ1、ｍ2（第一サイクル）；ｉ2、ｊ2、ｍ3、ｍ4（第二
サイクル）；ｉ3、ｊ3（第三サイクル）；ｉ4、ｊ4（第
四サイクル）；ｉ5、ｊ5（第五サイクル）；ｉ6（第六
サイクル）；ｉ7（第七サイクル）となる。ここで、パ
ケットｊ4及びｊ5がサイクルをはずれている。サイクル
行列の数よりも長いバッチは、その中の幾つかのパケッ
トがサイクルをばずれる可能性がある。この現象がシス
テムにとって良い場合もあるし、悪い場合もある。サイ
クル行列の数及び各サイクル行列サイズの選択は、技術
や性能のガイドラインにより決められるべきである。
【００６７】本発明は、スロット化パケットデータネッ
トワーク内のデータ幹線におけるパケットの取り扱いに
適用可能である。また本発明は、マルチタスク／マルチ
ユーザのコンピュータシステム環境のように効果的なス
ケジューリングプロセスが必要となる環境にも適用可能
である。スロット化パケットデータネットワークの場合
においては、チャンネルＩＤまたはチャンネルＩＤへの
マッピングが可能な何らかの情報をパケットが含む必要
がある。コンピュータシステムの場合においては、各プ
ロセスがＩＤ番号を有する必要がある。
トワーク内のデータ幹線におけるパケットの取り扱いに
適用可能である。また本発明は、マルチタスク／マルチ
ユーザのコンピュータシステム環境のように効果的なス
ケジューリングプロセスが必要となる環境にも適用可能
である。スロット化パケットデータネットワークの場合
においては、チャンネルＩＤまたはチャンネルＩＤへの
マッピングが可能な何らかの情報をパケットが含む必要
がある。コンピュータシステムの場合においては、各プ
ロセスがＩＤ番号を有する必要がある。
【００６８】
【発明の効果】以上述べたように本発明によれば、大規
模なメモリ資源を必要とせずに、データサービスの優先
度に従った公正なオペレーションを行うことが可能なデ
ータチャンネリングのスケジューリング装置及び方法が
提供できる。
模なメモリ資源を必要とせずに、データサービスの優先
度に従った公正なオペレーションを行うことが可能なデ
ータチャンネリングのスケジューリング装置及び方法が
提供できる。
【図１】本発明が適用される複数の交換ノードを有する
データネットワークの一例を示す構成図である。
データネットワークの一例を示す構成図である。
【図２】図１に示すデータネットワークにおいてデータ
幹線を交換ノードに接続するために使用されるデータ幹
線インターフェイスを示す図である。
幹線を交換ノードに接続するために使用されるデータ幹
線インターフェイスを示す図である。
【図３】スロット化されたパケットシステムのタイムス
ロットの一例及び長いデータメッセージを送信用の幾つ
かのスロットに分割する方法を示す図である。
ロットの一例及び長いデータメッセージを送信用の幾つ
かのスロットに分割する方法を示す図である。
【図４】図２に示すデータ幹線インターフェイスの受信
部／送信部対の構成を示すブロック図である。
部／送信部対の構成を示すブロック図である。
【図５】本発明の一実施例によるデータ幹線インターフ
ェイスの受信部／送信部対をオペレーションユニットに
より示す図である。
ェイスの受信部／送信部対をオペレーションユニットに
より示す図である。
【図６】受信部の動作を示すフローチャートである。
【図７】送信部の動作を示すフローチャートである。
【図８】オーバーフロー行列ソーターの動作を示すフロ
ーチャートである。
ーチャートである。
【図９】メッセージのバッチが到着した後のシステムの
状態を示す図である。
状態を示す図である。
【図１０】送信部が第１のサイクル行列をサービスした
後のシステムの状態を示す図である。
後のシステムの状態を示す図である。
【図１１】送信部がオーバーフロー行列ソーターをサー
ビスした後のシステムの状態を示す図である。
ビスした後のシステムの状態を示す図である。
【図１２】送信部が第二サイクルのサービスを行った後
のシステムの状態を示す図である。
のシステムの状態を示す図である。
【図１３】送信部がオーバーフロー行列ソーターへの２
回目のサービスを行った後のシステムの状態を示す図で
ある。
回目のサービスを行った後のシステムの状態を示す図で
ある。
【図１４】送信部が第三サイクルのサービスを行った後
のシステムの状態を示す図である。
のシステムの状態を示す図である。
【図１５】送信部がオーバーフロー行列ソーターへの３
回目のサービスを行った後のシステムの状態を示す図で
ある。
回目のサービスを行った後のシステムの状態を示す図で
ある。
【図１６】単独パケット到着後のシステムの状態を示す
図である。
図である。
【図１７】送信部が第四サイクルのサービスを行った後
のシステムの状態を示す図である。
のシステムの状態を示す図である。
【図１８】送信部がオーバーフロー行列ソーターへの４
回目のサービスを行った後のシステムの状態を示す図で
ある。
回目のサービスを行った後のシステムの状態を示す図で
ある。
【図１９】送信部が第五サイクルのサービスを行った後
のシステムの状態を示す図である。
のシステムの状態を示す図である。
【図２０】送信部が第六サイクルのサービスを行った後
のシステムの状態を示す図である。
のシステムの状態を示す図である。
１０１ アクセスステーション １０３ データ幹線 １１０ 交換ノード １１１ 交換ノード １１２ 交換ノード １１５ 交換ノード １２０ アクセスインターフェイス １２１ アクセスインターフェイス １２２ アクセスインターフェイス １２３ アクセスインターフェイス １３０ データ幹線インターフェイス １３１ データ幹線インターフェイス １３２ データ幹線インターフェイス １３３ データ幹線インターフェイス １３４ データ幹線インターフェイス １３５ データ幹線インターフェイス １４０ バックプレーン １４１ バックプレーン ２０１ データ転送点 ２０２ データ転送点 ２０３ データ転送点 ２０４ データ転送点 ２１０ バス ２２０ バス ３０１ タイムスロット ３０２ ヘッダー ３０３ ペイロード ３０４ トレイラー ３０５ メッセージ ３１１ パケット ３１２ パケット ３１３ パケット ４０１ 受信部バッファ ４０２ 受信制御部 ４０３ ルーティングテーブル ４０４ ＭＩＤ／ＣＩＤテーブル ４０５ 受信ポインタ ４０６ サイクルカウンタ ４０７ オーバーフローカウンタ ４０８ 優先度レジスタ ４０９ サイクルレジスタ ４１０ レジスタ ４１１ ＤＭＡデバイス ４１２ データメモリ ４１３ 送信制御部 ４１４ ＤＭＡデバイス ４１５ 送信部バッファ ５０１ 受信ポインタ ５０２ サイクルカウンタ ５０３ オーバーフローカウンタ ５０４ 優先度レジスタ ５０５ サイクルレジスタ ５０６ 送信ポインタ ５０７ サイクル行列 ５０８ サイクル行列 ５０９ サイクル行列 ５１０ オーバーフロー行列 ５１１ 受信部サーバー（ソーター） ５１２ 送信部サーバー ５１３ 入力線 ５１４ 施設線
───────────────────────────────────────────────────── フロントページの続き (72)発明者 デビッド エス アインシュタイン アメリカ合衆国 08876 ニュージャージ ー ブランチバーグ、マンシー トレイル 13 (72)発明者 ケリー ダブリュー フェンディック アメリカ合衆国 07748 ニュージャージ ー ミドルタウン、ノルウッド ドライブ 1806 (72)発明者 マノエル エー ロドリゲス アメリカ合衆国 07701 ニュージャージ ー レッドバンク、ピンクニー ロード 20
Claims (29)
- 【請求項１】 それぞれ複数のデータチャンネルのうち
の一つを通して受信されかつ一つ以上のデータパケット
からなる複数のデータバッチを含むマルチチャンネルデ
ータ信号を通信施設線へインターフェイスするデータチ
ャンネルのスケジューリング装置において、各データバ
ッチについて特定のチャンネルからのデータパケットが
所定のＰ個以上であることの認識情報がＮ個のサイクル
行列の各行列に入力されることがないように、各データ
バッチの一つ以上のデータパケットの認識情報を前記Ｎ
個のサイクル行列の中にソートするソーター手段と、各
サイクル行列を空にするように周期的に前記施設線にサ
ービスするメモリサーバー手段とを有することを特徴と
するデータチャンネルのスケジューリング装置。 - 【請求項２】 Ｎ個のサイクル行列を含むメモリユニッ
トを有することを特徴とする請求項１記載の装置。 - 【請求項３】 ソーター手段は、全てのサイクル行列が
満杯になっているか各サイクル行列が特定のチャンネル
からのＰ個のデータパケットの認識情報を含んでいるよ
うな飽和状態の後は、前記認識情報をオーバーフロー行
列の中にソートし、引き続いて、特定のチャンネルから
のデータパケットがＰ個以上であることの認識情報がサ
イクル行列に入力されることがないように、オーバーフ
ロー行列中の認識情報を一つ以上のサイクル行列中に連
続的にソートすることを特徴とする請求項１記載の装
置。 - 【請求項４】 ソーター手段は、第１のサイクル行列が
サーバー手段によるサービスを受けた後でかつ他のサイ
クル行列が前記サーバー手段によるサービスを受ける前
に、オーバーフロー行列中の認識情報を少なくとも第１
のサイクル行列の中にソートすることを特徴とする請求
項３記載の装置。 - 【請求項５】 オーバーフロー行列にソートされている
データパケットの数を各チャンネル毎にカウントするオ
ーバーフローカウンタを有することを特徴とする請求項
３記載の装置。 - 【請求項６】 ソートされているサイクル行列が満杯に
なったとソーター手段が決定したときに、データバッチ
内の一つ以上のデータパケットの認識情報がその満杯の
サイクル行列にソートされることのないように、前記ソ
ーター手段はその認識情報を他のサイクル行列またはオ
ーバーフロー行列にストアすることを特徴とする請求項
３記載の装置。 - 【請求項７】 Ｎ個のサイクル行列及びオーバーフロー
行列を含むメモリが予め決められたデータ許容量に達し
ているとソーター手段が決定したとき、ソーター手段は
受信したデータ信号の新たなメッセージに関連する各デ
ータパケットを放棄することを特徴とする請求項６記載
の装置。 - 【請求項８】 各データバッチ内の一つ以上のデータパ
ケットの認識情報が、その一つ以上のデータパケット自
体であることを特徴とする請求項１記載の装置。 - 【請求項９】 各データバッチ内の一つ以上のデータパ
ケットの認識情報が、その一つ以上のデータパケットが
ストアされているメモリ位置を認識するポインタである
ことを特徴とする請求項１記載の装置。 - 【請求項１０】 ソートされているサイクル行列が満杯
になったとソーター手段が決定したときに、受信データ
信号内の一つ以上のデータパケットの認識情報がその満
杯のサイクル行列にソートされることのないように、前
記ソーター手段はその認識情報を他のサイクル行列にス
トアすることを特徴とする請求項１記載の装置。 - 【請求項１１】 Ｎ個のサイクル行列を含むメモリが予
め決められたデータ許容量に達しているとソーター手段
が決定したとき、ソーター手段は受信したデータ信号の
新たなメッセージに関連する各データパケットを放棄す
ることを特徴とする請求項１０記載の装置。 - 【請求項１２】 ソーター手段が、受信したデータ信号
をソートする第１のソーター手段と、オーバーフロー行
列の内容をソートする第２のソーター手段とを含むこと
を特徴とする請求項１記載の装置。 - 【請求項１３】 サーバー手段によるサービスを受けた
サイクル行列の中に認識情報をソートするために、第１
のソーター手段よりも第２のソーター手段に高い優先度
を与えることを特徴とする請求項１２記載の装置。 - 【請求項１４】 ソーター手段が特定のチャンネルから
の認識情報をオーバーフロー行列にソートした後は、そ
のチャンネルからの認識情報が前記オーバーフロー行列
からなくなるまで、前記特定のチャンネルからの認識情
報をサイクル行列にソートしないことを特徴とする請求
項１記載の装置。 - 【請求項１５】 各チャンネルについてのＰの値をそれ
ぞれ独立に決めることを特徴とする請求項１記載の装
置。 - 【請求項１６】 Ｐの値が１であることを特徴とする請
求項１記載の装置。 - 【請求項１７】 各チャンネル毎に、サイクル行列にス
トアされたデータパケットの数をカウントするサイクル
カウンタを有することを特徴とする請求項１記載の装
置。 - 【請求項１８】 各チャンネル毎に、チャンネルからの
認識情報をソートすべきサイクル行列を特定する受信ポ
インタを有することを特徴とする請求項１記載の装置。 - 【請求項１９】 各チャンネル毎に、現在受信ポインタ
により指定されているサイクル行列内にストアされた各
チャンネルからのデータパケットの数をカウントするサ
イクルレジスタを有することを特徴とする請求項１記載
の装置。 - 【請求項２０】 メモリサーバー手段により現在サービ
スされているサイクル行列を示す送信ポインタ有するこ
とを特徴とする請求項１記載の装置。 - 【請求項２１】 認識情報をソートすべきサイクル行列
を各チャンネル毎に特定する受信ポインタ及びメモリサ
ーバー手段により現在サービスされているサイクル行列
を示す送信ポインタを有し、ソーター手段が異なるサイ
クル行列にソートする度に前記受信ポインタがインクリ
メントされ、メモリサーバー手段が異なるサイクル行列
をサービスする度に前記送信ポインタがインクリメント
され、その値がＮの倍数である整数Ｍに達した場合に、
前記受信ポインタ及び送信ポインタが各々リセットされ
ることを特徴とする請求項１記載の装置。 - 【請求項２２】 各サイクル行列にソートされるべきデ
ータパケットの数をチャンネル毎に特定する優先度レジ
スタを有し、そのチャンネルについての数Ｐが大きいほ
ど、他のチャンネルに比べてデータの送信割合が大きく
なるようにしたことを特徴とする請求項１記載の装置。 - 【請求項２３】 それぞれ複数のデータチャンネルのう
ちの一つを通して受信されかつ一つ以上のデータパケッ
トからなる複数のデータバッチを含むマルチチャンネル
データ信号を通信施設線へインターフェイスするデータ
チャンネルのスケジューリング方法において、各データ
バッチについて特定のチャンネルからのデータパケット
が所定のＰ個以上であることの認識情報がＮ個のサイク
ル行列の各行列に入力されることがないように、各デー
タバッチの一つ以上のデータパケットの認識情報を前記
Ｎ個のサイクル行列の中にソートするソーティングステ
ップと、各サイクル行列を空にするように周期的に前記
施設線にサービスするサービングステップとを有するこ
とを特徴とするデータチャンネルのスケジューリング方
法。 - 【請求項２４】 ソーティングステップは、全てのサイ
クル行列が満杯になっているか各サイクル行列が特定の
チャンネルからのＰ個のデータパケットの認識情報を含
んでいるような飽和状態の後は、前記認識情報をオーバ
ーフロー行列の中にソートし、引き続いて、特定のチャ
ンネルからのデータパケットがＰ個以上であることの認
識情報がサイクル行列に入力されることがないように、
オーバーフロー行列中の認識情報を連続的に一つ以上の
サイクル行列中にソートすることを特徴とする請求項２
３記載の方法。 - 【請求項２５】 ソーティングステップは、サービング
ステップの間に第１のサイクル行列がサービスを受けた
後でかつ他のサイクル行列がサービスを受ける前に、オ
ーバーフロー行列中の認識情報を少なくとも第１のサイ
クル行列の中にソートすることを特徴とする請求項２４
記載の方法。 - 【請求項２６】 ソーティングステップが、選択された
サイクル行列が満杯であるかどうかを決定する決定ステ
ップと、データバッチ内の一つ以上のデータパケットの
認識情報がその満杯のサイクル行列にソートされること
がないように、前記認識情報を他のサイクル行列または
オーバーフロー行列にソートするステップとを有するこ
とを特徴とする請求項２４記載の方法。 - 【請求項２７】 決定ステップは、サイクル行列及びオ
ーバーフロー行列が予め決められた許容量に達している
かどうかを決定し、前記決定に応答して、受信したデー
タ信号の新たなメッセージに関連する各データパケット
を放棄することを特徴とする請求項２６記載の方法。 - 【請求項２８】 ソーティングステップが、選択され
たサイクル行列が満杯であるかどうかを決定する決定ス
テップと、受信データの一つ以上のデータパケットの認
識情報がその満杯のサイクル行列にソートされることが
ないように、前記認識情報を他のサイクル行列にソート
するステップとを有することを特徴とする請求項２４記
載の方法。 - 【請求項２９】 決定ステップは、サイクル行列が予め
決められた許容量に達しているかどうかを決定し、許容
量に達している場合、受信したデータ信号の新たなメッ
セージの部分のデータパケットを放棄することを特徴と
する請求項２８記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/629,282 US5166930A (en) | 1990-12-17 | 1990-12-17 | Data channel scheduling discipline arrangement and method |
| US629282 | 1990-12-17 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04315337A JPH04315337A (ja) | 1992-11-06 |
| JPH0720124B2 true JPH0720124B2 (ja) | 1995-03-06 |
Family
ID=24522350
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3351198A Expired - Lifetime JPH0720124B2 (ja) | 1990-12-17 | 1991-12-13 | データチャンネルのスケジューリング装置及び方法 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US5166930A (ja) |
| EP (1) | EP0491489B1 (ja) |
| JP (1) | JPH0720124B2 (ja) |
| AU (1) | AU632006B2 (ja) |
| CA (1) | CA2054355C (ja) |
| DE (1) | DE69131224T2 (ja) |
Families Citing this family (104)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0533900B1 (en) * | 1991-04-10 | 1997-08-06 | Koninklijke Philips Electronics N.V. | Low delay or low loss cell switch for atm |
| JPH05151178A (ja) * | 1991-11-26 | 1993-06-18 | Toshiba Corp | 分散協調型問題解決装置 |
| US5357516A (en) * | 1992-03-25 | 1994-10-18 | Motorola, Inc. | Apparatus for use in time division multiplexed communication systems |
| US5715474A (en) * | 1992-04-30 | 1998-02-03 | Motorola, Inc. | Simultaneous control of radio frequency modem in a multi-tasking system using a single session manager program with separate command queue for each application program |
| GB2272612B (en) * | 1992-11-06 | 1996-05-01 | Roke Manor Research | Improvements in or relating to ATM signal processors |
| JPH06187302A (ja) * | 1992-12-18 | 1994-07-08 | Fujitsu Ltd | 転送要求キュー制御方式 |
| US5408472A (en) * | 1993-09-20 | 1995-04-18 | Motorola, Inc. | Device and method for cell processing in cell relay nodes |
| WO1995018415A1 (en) * | 1993-12-30 | 1995-07-06 | International Business Machines Corporation | Queue management in a data processing link |
| JPH07254906A (ja) * | 1994-03-16 | 1995-10-03 | Mitsubishi Electric Corp | 優先処理機能を有するシフトレジスタ、それを用いたパケット通信用スイッチング装置及びそれを用いたａｔｍネットワーク並びに優先処理を伴うパケット通信方式及び優先処理を伴うａｔｍ通信方式 |
| US5598535A (en) * | 1994-08-01 | 1997-01-28 | International Business Machines Corporation | System for selectively and cumulatively grouping packets from different sessions upon the absence of exception condition and sending the packets after preselected time conditions |
| US5586264A (en) * | 1994-09-08 | 1996-12-17 | Ibm Corporation | Video optimized media streamer with cache management |
| SE9403101L (sv) * | 1994-09-16 | 1996-03-17 | Ericsson Telefon Ab L M | Förfarande för anpassning av dataflöden |
| US5881313A (en) | 1994-11-07 | 1999-03-09 | Digital Equipment Corporation | Arbitration system based on requester class and relative priority including transmit descriptor valid bit for a shared resource having multiple requesters |
| US5793978A (en) * | 1994-12-29 | 1998-08-11 | Cisco Technology, Inc. | System for routing packets by separating packets in to broadcast packets and non-broadcast packets and allocating a selected communication bandwidth to the broadcast packets |
| US5867666A (en) * | 1994-12-29 | 1999-02-02 | Cisco Systems, Inc. | Virtual interfaces with dynamic binding |
| MY121893A (en) * | 1995-04-28 | 2006-03-31 | Qualcomm Inc | Method and apparatus for providing variable rate data in a communications system using statistical multiplexing. |
| EP0748086A1 (en) * | 1995-06-09 | 1996-12-11 | Siemens Aktiengesellschaft | Method for scheduling message cells leaving an ATM node |
| SE506955C2 (sv) * | 1995-07-06 | 1998-03-09 | Ericsson Telefon Ab L M | ATM-flödesstyrning |
| US5787086A (en) * | 1995-07-19 | 1998-07-28 | Fujitsu Network Communications, Inc. | Method and apparatus for emulating a circuit connection in a cell based communications network |
| US5692156A (en) * | 1995-07-28 | 1997-11-25 | International Business Machines Corp. | Computer program product for overflow queue processing |
| US5893924A (en) * | 1995-07-28 | 1999-04-13 | International Business Machines Corporation | System and method for overflow queue processing |
| US6097718A (en) | 1996-01-02 | 2000-08-01 | Cisco Technology, Inc. | Snapshot routing with route aging |
| US6147996A (en) | 1995-08-04 | 2000-11-14 | Cisco Technology, Inc. | Pipelined multiple issue packet switch |
| US5764641A (en) * | 1995-09-08 | 1998-06-09 | Cisco Systems, Inc. | Early and integrated tail packet discard system |
| US5901139A (en) * | 1995-09-27 | 1999-05-04 | Nec Corporation | ATM cell buffer managing system in ATM node equipment |
| US7246148B1 (en) | 1995-09-29 | 2007-07-17 | Cisco Technology, Inc. | Enhanced network services using a subnetwork of communicating processors |
| US6917966B1 (en) | 1995-09-29 | 2005-07-12 | Cisco Technology, Inc. | Enhanced network services using a subnetwork of communicating processors |
| US6182224B1 (en) | 1995-09-29 | 2001-01-30 | Cisco Systems, Inc. | Enhanced network services using a subnetwork of communicating processors |
| US5966163A (en) | 1995-10-20 | 1999-10-12 | Scientific-Atlanta, Inc. | Providing constant bit rate upstream data transport in a two way cable system by scheduling preemptive grants for upstream data slots using selected fields of a plurality of grant fields |
| US6230203B1 (en) | 1995-10-20 | 2001-05-08 | Scientific-Atlanta, Inc. | System and method for providing statistics for flexible billing in a cable environment |
| EP1457895A3 (en) * | 1995-10-26 | 2005-04-20 | Matsushita Electric Industrial Co., Ltd. | File System |
| SE9504231L (sv) * | 1995-11-27 | 1997-05-28 | Ericsson Telefon Ab L M | Kösystem för överföring av informatonspaket |
| US6091725A (en) | 1995-12-29 | 2000-07-18 | Cisco Systems, Inc. | Method for traffic management, traffic prioritization, access control, and packet forwarding in a datagram computer network |
| US6035105A (en) * | 1996-01-02 | 2000-03-07 | Cisco Technology, Inc. | Multiple VLAN architecture system |
| US5870629A (en) * | 1996-03-21 | 1999-02-09 | Bay Networks, Inc. | System for servicing plurality of queues responsive to queue service policy on a service sequence ordered to provide uniform and minimal queue interservice times |
| US7028088B1 (en) | 1996-04-03 | 2006-04-11 | Scientific-Atlanta, Inc. | System and method for providing statistics for flexible billing in a cable environment |
| US5732087A (en) * | 1996-05-10 | 1998-03-24 | Mitsubishi Electric Information Technology Center America, Inc. | ATM local area network switch with dual queues |
| US6243667B1 (en) | 1996-05-28 | 2001-06-05 | Cisco Systems, Inc. | Network flow switching and flow data export |
| US6308148B1 (en) | 1996-05-28 | 2001-10-23 | Cisco Technology, Inc. | Network flow data export |
| US5859853A (en) * | 1996-06-21 | 1999-01-12 | International Business Machines Corporation | Adaptive packet training |
| US6212182B1 (en) | 1996-06-27 | 2001-04-03 | Cisco Technology, Inc. | Combined unicast and multicast scheduling |
| US6434120B1 (en) | 1998-08-25 | 2002-08-13 | Cisco Technology, Inc. | Autosensing LMI protocols in frame relay networks |
| US5875175A (en) * | 1997-05-01 | 1999-02-23 | 3Com Corporation | Method and apparatus for time-based download control |
| WO1998027696A1 (en) * | 1996-12-05 | 1998-06-25 | 3Com Corporation | Method and apparatus for time-based download control |
| JP2001500338A (ja) | 1996-12-06 | 2001-01-09 | フジツウ ネットワーク コミュニケーションズ，インコーポレイテッド | Ａｔｍトラヒックをフロー制御する方法 |
| US6304546B1 (en) | 1996-12-19 | 2001-10-16 | Cisco Technology, Inc. | End-to-end bidirectional keep-alive using virtual circuits |
| JP3213697B2 (ja) * | 1997-01-14 | 2001-10-02 | 株式会社ディジタル・ビジョン・ラボラトリーズ | 中継ノードシステム及び同システムにおける中継制御方法 |
| US6272150B1 (en) | 1997-01-17 | 2001-08-07 | Scientific-Atlanta, Inc. | Cable modem map display for network management of a cable data delivery system |
| US6324267B1 (en) | 1997-01-17 | 2001-11-27 | Scientific-Atlanta, Inc. | Two-tiered authorization and authentication for a cable data delivery system |
| US6487212B1 (en) * | 1997-02-14 | 2002-11-26 | Advanced Micro Devices, Inc. | Queuing structure and method for prioritization of frames in a network switch |
| US6286058B1 (en) | 1997-04-14 | 2001-09-04 | Scientific-Atlanta, Inc. | Apparatus and methods for automatically rerouting packets in the event of a link failure |
| US6122272A (en) * | 1997-05-23 | 2000-09-19 | Cisco Technology, Inc. | Call size feedback on PNNI operation |
| US6356530B1 (en) | 1997-05-23 | 2002-03-12 | Cisco Technology, Inc. | Next hop selection in ATM networks |
| US6862284B1 (en) | 1997-06-17 | 2005-03-01 | Cisco Technology, Inc. | Format for automatic generation of unique ATM addresses used for PNNI |
| US6078590A (en) * | 1997-07-14 | 2000-06-20 | Cisco Technology, Inc. | Hierarchical routing knowledge for multicast packet routing |
| US6330599B1 (en) | 1997-08-05 | 2001-12-11 | Cisco Technology, Inc. | Virtual interfaces with dynamic binding |
| US6157641A (en) * | 1997-08-22 | 2000-12-05 | Cisco Technology, Inc. | Multiprotocol packet recognition and switching |
| US6512766B2 (en) | 1997-08-22 | 2003-01-28 | Cisco Systems, Inc. | Enhanced internet packet routing lookup |
| US6212183B1 (en) | 1997-08-22 | 2001-04-03 | Cisco Technology, Inc. | Multiple parallel packet routing lookup |
| US6343072B1 (en) | 1997-10-01 | 2002-01-29 | Cisco Technology, Inc. | Single-chip architecture for shared-memory router |
| IL132888A0 (en) | 1999-11-11 | 2001-03-19 | Surf Comm Solutions Ltd | Channel load balancing |
| US7200168B1 (en) | 1997-11-13 | 2007-04-03 | Surf Communication Solutions Ltd. | Stable operation of media gateway |
| US7570583B2 (en) | 1997-12-05 | 2009-08-04 | Cisco Technology, Inc. | Extending SONET/SDH automatic protection switching |
| US6424649B1 (en) | 1997-12-31 | 2002-07-23 | Cisco Technology, Inc. | Synchronous pipelined switch using serial transmission |
| US6111877A (en) | 1997-12-31 | 2000-08-29 | Cisco Technology, Inc. | Load sharing across flows |
| US6160853A (en) * | 1998-02-09 | 2000-12-12 | At&T Corp | Modem concentrator |
| US6853638B2 (en) | 1998-04-01 | 2005-02-08 | Cisco Technology, Inc. | Route/service processor scalability via flow-based distribution of traffic |
| US6298070B1 (en) | 1998-05-07 | 2001-10-02 | International Business Machines Corporation | Packet training with an adjustable optimum number of packets |
| US6370121B1 (en) | 1998-06-29 | 2002-04-09 | Cisco Technology, Inc. | Method and system for shortcut trunking of LAN bridges |
| US6920112B1 (en) | 1998-06-29 | 2005-07-19 | Cisco Technology, Inc. | Sampling packets for network monitoring |
| WO2000000911A1 (en) * | 1998-06-29 | 2000-01-06 | Sbc Technology Resources, Inc. | Emergency facility information system and methods |
| US6377577B1 (en) | 1998-06-30 | 2002-04-23 | Cisco Technology, Inc. | Access control list processing in hardware |
| US6182147B1 (en) | 1998-07-31 | 2001-01-30 | Cisco Technology, Inc. | Multicast group routing using unidirectional links |
| US6308219B1 (en) | 1998-07-31 | 2001-10-23 | Cisco Technology, Inc. | Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks |
| US6101115A (en) * | 1998-08-07 | 2000-08-08 | Cisco Technology, Inc. | CAM match line precharge |
| US6389506B1 (en) | 1998-08-07 | 2002-05-14 | Cisco Technology, Inc. | Block mask ternary cam |
| US6771642B1 (en) | 1999-01-08 | 2004-08-03 | Cisco Technology, Inc. | Method and apparatus for scheduling packets in a packet switch |
| US6490298B1 (en) | 1999-02-26 | 2002-12-03 | Harmonic Inc. | Apparatus and methods of multiplexing data to a communication channel |
| US7065762B1 (en) | 1999-03-22 | 2006-06-20 | Cisco Technology, Inc. | Method, apparatus and computer program product for borrowed-virtual-time scheduling |
| US6757791B1 (en) | 1999-03-30 | 2004-06-29 | Cisco Technology, Inc. | Method and apparatus for reordering packet data units in storage queues for reading and writing memory |
| US6603772B1 (en) | 1999-03-31 | 2003-08-05 | Cisco Technology, Inc. | Multicast routing with multicast virtual output queues and shortest queue first allocation |
| US6760331B1 (en) | 1999-03-31 | 2004-07-06 | Cisco Technology, Inc. | Multicast routing with nearest queue first allocation and dynamic and static vector quantization |
| US6401147B1 (en) * | 1999-05-24 | 2002-06-04 | Advanced Micro Devices, Inc. | Split-queue architecture with a first queue area and a second queue area and queue overflow area having a trickle mode and an overflow mode based on prescribed threshold values |
| US7257642B1 (en) | 1999-11-11 | 2007-08-14 | Surp Communication Solutions Ltd. | Channel load balancing |
| US6978311B1 (en) * | 2000-02-09 | 2005-12-20 | Surf Communications Solutions, Ltd. | Scheduling in a remote-access server |
| US20030014484A1 (en) * | 2000-11-09 | 2003-01-16 | Arnon Netzer | Scheduling in a remote-access server |
| US7123622B2 (en) * | 2000-04-13 | 2006-10-17 | International Business Machines Corporation | Method and system for network processor scheduling based on service levels |
| EP1282970A2 (en) | 2000-05-09 | 2003-02-12 | Surf Communication Solutions, Ltd. | Always-on access server pool |
| US6735207B1 (en) | 2000-06-13 | 2004-05-11 | Cisco Technology, Inc. | Apparatus and method for reducing queuing memory access cycles using a distributed queue structure |
| US6975638B1 (en) * | 2000-10-13 | 2005-12-13 | Force10 Networks, Inc. | Interleaved weighted fair queuing mechanism and system |
| JP2002152259A (ja) * | 2000-11-13 | 2002-05-24 | Yozan Inc | 通信端末装置および課金処理装置 |
| US20020126673A1 (en) * | 2001-01-12 | 2002-09-12 | Nirav Dagli | Shared memory |
| US6901073B2 (en) * | 2001-02-14 | 2005-05-31 | Northrop Grumman Corporation | Encapsulation method and apparatus for communicating fixed-length data packets through an intermediate network |
| US7140017B2 (en) * | 2001-02-22 | 2006-11-21 | International Business Machines Corporation | Performance of channels used in communicating between senders and receivers |
| GB2379586A (en) * | 2001-09-06 | 2003-03-12 | Zarlink Semiconductor Ltd | Processing requests for service using FIFO queues |
| US20040194087A1 (en) * | 2002-04-11 | 2004-09-30 | International Business Machines Corporation | Batch processing of requests in a data processing network |
| US7154902B1 (en) * | 2002-10-21 | 2006-12-26 | Force10 Networks, Inc. | Epoch-based packet switching |
| US20040109463A1 (en) * | 2002-12-05 | 2004-06-10 | Alcatel Canada Inc. | Efficient data transmission method |
| US7424003B2 (en) * | 2004-03-08 | 2008-09-09 | Surf Communication Solutions | Multi-parameter scheduling in communication systems |
| WO2006040903A1 (ja) * | 2004-10-14 | 2006-04-20 | Tokyo Denki University | 交換ノード及び交換ノード制御方法 |
| US8954635B2 (en) * | 2011-08-31 | 2015-02-10 | Advanced Micro Devices, Inc. | Buffer management using freelist buffers |
| DE112011106016T5 (de) * | 2011-12-23 | 2014-09-11 | Intel Corporation | Gemeinsame Sendeschlange |
| US9906460B2 (en) | 2015-12-31 | 2018-02-27 | Alcatel-Lucent Usa Inc. | Data plane for processing function scalability |
| US10481801B1 (en) * | 2018-02-22 | 2019-11-19 | Veritas Technologies Llc | Optimizing storage quality of service (SQOS) by dynamically determining and managing optimal queue depth and system capacity |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4499576A (en) * | 1982-08-13 | 1985-02-12 | At&T Bell Laboratories | Multiplexed first-in, first-out queues |
| KR900006793B1 (ko) * | 1984-10-18 | 1990-09-21 | 휴우즈 에어크라프트 캄파니 | 패킷 스위치 다중 대기행렬 NxM 스위치 노오드 및 처리 방법 |
| US4644533A (en) * | 1985-05-06 | 1987-02-17 | American Telephone & Telegraph Company | Packet switch trunk circuit queueing arrangement |
| US5021947A (en) * | 1986-03-31 | 1991-06-04 | Hughes Aircraft Company | Data-flow multiprocessor architecture with three dimensional multistage interconnection network for efficient signal and data processing |
| DE3785799T2 (de) * | 1986-06-27 | 1993-10-28 | Fujitsu Ltd | Paketdatenübertragungssystem mit Ringtypübertragungsleitung. |
| US4899334A (en) * | 1987-10-19 | 1990-02-06 | Oki Electric Industry Co., Ltd. | Self-routing multistage switching network for fast packet switching system |
| JPH01177239A (ja) * | 1988-01-06 | 1989-07-13 | Nec Corp | パケット集線装置及びパケット交換機 |
| JPH02117243A (ja) * | 1988-10-27 | 1990-05-01 | Toshiba Corp | パケット通信装置 |
| US4899335A (en) * | 1988-12-21 | 1990-02-06 | American Telephone And Telegraph Company, At&T Bell Laboratories | Self routing packet switching network architecture |
-
1990
- 1990-12-17 US US07/629,282 patent/US5166930A/en not_active Expired - Lifetime
-
1991
- 1991-10-28 CA CA002054355A patent/CA2054355C/en not_active Expired - Fee Related
- 1991-11-29 AU AU88303/91A patent/AU632006B2/en not_active Ceased
- 1991-12-02 EP EP91311193A patent/EP0491489B1/en not_active Expired - Lifetime
- 1991-12-02 DE DE69131224T patent/DE69131224T2/de not_active Expired - Fee Related
- 1991-12-13 JP JP3351198A patent/JPH0720124B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US5166930A (en) | 1992-11-24 |
| CA2054355A1 (en) | 1992-06-18 |
| DE69131224D1 (de) | 1999-06-17 |
| AU632006B2 (en) | 1992-12-10 |
| DE69131224T2 (de) | 1999-09-23 |
| EP0491489B1 (en) | 1999-05-12 |
| EP0491489A2 (en) | 1992-06-24 |
| AU8830391A (en) | 1992-06-18 |
| CA2054355C (en) | 1994-02-08 |
| EP0491489A3 (en) | 1994-11-23 |
| JPH04315337A (ja) | 1992-11-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0720124B2 (ja) | データチャンネルのスケジューリング装置及び方法 | |
| US5933429A (en) | Multipoint-to-multipoint echo processing in a network switch | |
| US6122279A (en) | Asynchronous transfer mode switch | |
| US7061860B1 (en) | Network traffic shaping | |
| US5379297A (en) | Concurrent multi-channel segmentation and reassembly processors for asynchronous transfer mode | |
| EP0981878B1 (en) | Fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch | |
| US4763319A (en) | Multi-rate synchronous virtual circuit network for voice and data communications | |
| EP0760185B1 (en) | Bus arbitration method for telecommunications switching | |
| US6292491B1 (en) | Distributed FIFO queuing for ATM systems | |
| KR19990087752A (ko) | 효율적인 출력 요구 패킷 스위치와 방법 | |
| JPH11252127A (ja) | オーバースケジュール条件でのａｔｍセル送信の公平なスケジューリング | |
| JPH11234309A (ja) | 非同期転送モード・セル送信スケジューリング | |
| US4707693A (en) | Through-traffic priority protocol in a communications system | |
| US5982296A (en) | Data switching processing method and apparatus | |
| US7209489B1 (en) | Arrangement in a channel adapter for servicing work notifications based on link layer virtual lane processing | |
| US6445706B1 (en) | Method and device in telecommunications system | |
| JPH09319671A (ja) | データ伝送装置 | |
| JP3820272B2 (ja) | 交換装置 | |
| JP2737726B2 (ja) | バッファ制御装置 | |
| EP0839422B1 (en) | Linked-list structures for multiple levels of control in an atm switch | |
| US6643702B1 (en) | Traffic scheduler for a first tier switch of a two tier switch | |
| EP0604538B1 (en) | Method and apparatus for asynchronous transfer mode (atm) network | |
| JP2510875B2 (ja) | トラヒック監視方式 | |
| US7039057B1 (en) | Arrangement for converting ATM cells to infiniband packets | |
| Tyan | A rate-based message scheduling paradigm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080306 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090306 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090306 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100306 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100306 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110306 Year of fee payment: 16 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120306 Year of fee payment: 17 |
|
| EXPY | Cancellation because of completion of term |