JPH0496546A - 待ち行列バッファ構成方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［概要］ 所定長のデータの書き込みと読み出しを行うＦＩＦＯ内
の待ち行列バッファ構成方式に関し。

単独行列を用いながらセル毎の処理優先度に対応して読
み出しの順序を替えることができる待ち行列バッファ構
成方式を提供することを目的としバッファ列をアドレス
引き継ぎによる単独チェーン形式で構成し、入力するデ
ータに処理優先度を表すクラス情報を付加し、データが
書き込まれたバッファ位置を示すクラス別の書き込みポ
インタテーブルを設け、入力データを空きバッファに書
き込み、該空きバッファをデータのクラスに応じたチェ
ーン内の位置に挿入してつなぎ替えるよう構成する。

［産業上の利用分野］ 本発明は所定長のデータの書き込みと読み出しを行うＦ
ＩＦＯ内の待ち行列バッファ構成方式に関する。

近年、将来のＢ　Ｉ　Ｓ　Ｄ　Ｎ　（Ｂｒｏａｄｂａｎ
ｄＩｎｔｅｇｒａｔｅｄ　５ｅｒｖｉｃｅｓ　Ｄｉｇｉ
ｔａｌ　Ｎｅｔｗｏｒｋ）構築の要素技術として、ＡＴ
Ｍ　（八５ｙｎｃｈｒｏｎｏｕｓ　ＴｒａｎｓｆｅｒＭ
ｏｄｅ　）が注目されている。

ＡＴＭスイッチは、一般にセルと呼ばれる固定長情報パ
ケットを蓄積する待ち行列バッファ（以下、キューと呼
ぶ）とこれの書き込み／読み出しを制御する回路及び複
数のキューを接続する線路で構成され、キューは例えば
Ｆ　Ｉ　ＦＱ　（Ｆｉｒｓｔ　ＩｎＦｉｒｓｔ　０ｕｔ
）を用いて構成するが、スイッチ内でのセルの送達遅延
時間とセルの廃棄率の処理方法が重要になっている。

「従来の技術］ 第８図は従来のＡＴＭスイッチの構成例を示す。

この構成は、マルチ・ステージ・セルフ・ルーティング
（Ｍｕｌｔｉ−５ｔａｇｅ　Ｓｅｌｆ−Ｒｏｕｔｉｎｇ
　：Ｍ　Ｓ　Ｓ　Ｒ）式のスイッチを用いた例である。

第８図の動作の概要を説明すると、入力ハイウェイ（Ｉ
ｎｐｕｔ　Ｉｌｉｇｂｗａｙ）から連続して入力するセ
ルはそれぞれハーチセルチャネルナンパ（ｖｉｒｔｕａ
ｌＣｈａｎｎｅｌ　Ｎｕｍｂｅｒ　：以下ＶＣＮという
）を含むヘッダと情報とで構成され、複数のセルがＶＣ
Ｎコンバータ（ＶＣＣという）８０に入力すると、ＶＣ
Ｃは図示されないテーブルを参照してＶＣＮをスイッチ
ングに用いる制御情報であるタグ（ＴＡＧ）に変換する
。セルの本体とタグは、ＭＳＳＲネットワーク８１内の
初段のセルフ・ルーティングモジュール（ＳＲＭという
）８２に入力する。

この中の切替部８２１は、入力したセルをｖＣＣ８０で
発生したタグにより切替え制御し、指定されたルート別
に設けられた待ち行列（キュー）バッファ８２２に入力
する。複数の同じルート（ここでは次段のモジュールへ
のリンク（ＬＩＮＫ））に接続された複数の待ち行列バ
ッファ８２２に書き込まれたセルは順次読み出され多重
部８２３で多重化され次段へ出力され、以下同様に各Ｓ
ＲＭ８２で順次スイッチングが行われて最終段のＳＲＭ
８２から出力ハイウェイに出力される。

なお、呼処理部（Ｃａｌｌ　Ｐｒｏｃｅｓｓｉｎｇ）　
８４は信号処理部（Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎ
ｇ）　　８３からの信号情報を受取り、各■ＣＣのタグ
の制御を行う。

上記のように従来のＡＴＭスイッチは１セルと呼ばれる
固定長情報パケットを蓄積するキューバッファが用いら
れ、一般にＦ、　Ｔ　Ｐ　Ｏを用いて構成する。

ＡＴＭｌｉｌに収容されているメディアとしては画像、
音声、データ等の各種があり、それぞれ要求する通話品
質に応じて、セル廃棄率や送達の許容遅延時間が相違す
る。例えば、音声や動画像の場合はリアルタイム性が重
要視され、遅延時間は一定時間内に維持される必要があ
るが、セル廃棄が生じても影響が少ない。これに対しデ
ータの場合は２セル廃棄が生じると意味がなくなるが、
遅延時間に対しては比較的影響がすくない。

そこで１通信クラスを複数定義して、これに基づいてス
イッチ内の前記許容値を調整することによって、各種メ
ディアに必要な通信品質を保証する概念がＣＣＩＴＴ等
で検討されている。通信クラスは、送信者がセルのヘッ
ダ中に表示するビット列で表し、網はこのビット列を認
識して前記許容値に応じたスイッチングを行うという考
えである。

［発明が解決しよ・うとする課題］ 従来のＡＴＶスイッチでは、入力線当たり１個のキュー
を設置し、複数種類のセル、すなわち通信クラスが異な
るものを処理するのが一般的である。この方式では、ス
イッチのスルーブツトを向上させるかまたは、キュー長
を増加させる等のスイッチ全体の性能向上によって、要
求条件を満たずことになり、ハードウェアの負担は飛躍
的に増大するという問題がある。

これに対し、キューを通信クラス毎に分割して設置し、
これらのキューの読み出しアクセスに優先度を付加する
ことによって等価的に前記許容値を変化させる方法が考
えられる。しかし、この方法も通信クラスに対応してキ
ューのハード量が増大することになり上記の問題を解決
しないし、トラフィックの偏りに対しても柔軟な対応が
取りにくい。

また、優先度が高い通信クラスのセルを、待ち行列の途
中に割り込ませる方法も存在するが、従来の入力した順
番に出力を行う単純ＦＴＦＯでは実現困難であった。

本発明は単独行列を用いながらセル毎の処理優先度に対
応して読み出しの順序を替えることができる待ち行列バ
ッファ構成方式を提供することを目的とする。

［課題を解決するための手段］ 第１図は本発明の原理構成図である。

第１図において、１０はヘッダと情報からなりヘッダに
処理優先度（通信種別）を含む固定長情報のセル、１１
はクラス別の書き込みポインタを格納した書き込みポイ
ンタテーブル、１２は読み出しポインタ格納手段、１３
は空きバッファポインタ格納手段、１４はＦＩＦＯ内の
書き込みバッファの待ち行列を形成する書き込みバ・ソ
ファ、１５はＦＩＦＯ内の空きバッファの待ち行列を形
成する空きバッファである。

本発明は固定長情報中に処理優先度を表すクラス情報を
付加し、固定長情報を格納するために単独の待ち行列を
用いながら、情報を格納する時に各クラスの優先度の順
番に応じた位置に書き込みバッファを配置替えするもの
である。

「作用］ 書き込みバッファを形成する各バッファＩ４はそれぞれ
セル（ヘッダと情報）が書き込まれておす、先頭に自バ
ッファの後につながるバッファのバッファアドレスが格
納され、その後にセルが格納されている。このバッファ
の待ち行列は先頭から順次最後のバッファまでアドレス
引き継ぎの形式でチェーンを形成する。

先頭のバッファはセルが書き込まれた後、現在まで読み
出しが行われていないバッファの中で最モ優先度の高い
バッファを表し、そのバッファアドレスは読み出しポイ
ンタ格納手段】２に格納されている。また、これらの待
ち行列バッファはクラス別に優先度の高いものを先頭に
低い方に順番に順序付けられてチェーンが形成されてお
り。

同じクラスのセルの間では、先に到着したセルの方が前
の位置（読み出しが早い位置）に置かれる。

書き込みバッファの待ち行列の中で各クラスのセルが書
き込まれた最後のバッファのバッファアドレスが、クラ
ス別の書き込みポインタテーブル１１にクラス別に格納
されており、各クラスに対応してそのクラスの書き込み
バッファがあるか否かを表す書き込みフラグ（ＷＦで表
示）も設定される（書き込み済は“ｌ　ｌ　ＩＩ、書き
込まれてない時はＯ゛）。図の例では、クラス１はバッ
ファアドレスＡにクラス１のセルのｉｔｔ後＜最新＞の
データが格納されていることを示し、クラス２はバッフ
ァアドレスＣに最後のデータが格納されていることを表
す。

また、空きバッファ１５の待ち行列が設けられ。

先頭の空キハッファのバッファアドレスが空きバッファ
ポインタ格納手段１３に格納される。

セルが到着すると、空きバッファポインタ格納手段１３
の内容により示す空きバッファ列の先頭バッファ１５（
図の例ではＥ）を獲得し、同時に空きバッファポインタ
を次の空きバッファアドレス（図ではＦ）に更新する。

次に到着したセルを獲得した空きバッファアドレスに書
き込む。

一方、セルのクラスを識別して、書き込みポインタテー
ブル１１の該当クラスの書き込みポインタを検索し、直
前に到着したセルの格納アドレスを知り、そのバッファ
の先頭の引き継ぎ先バッファアドレスを上記獲得したバ
ッファアドレス（Ｅ）に変更する。次に、直前に到着し
たセルが格納されていたバッファの変更前（元の）の引
き継ぎ先のアドレスを上記獲得したバッファアドレス（
Ｅ）の先頭に引き継ぎ先アドレスとして格納する。

これにより、クラス毎の末端のバッファに新しいバッフ
ァをつなぐことができ、且つ全体のチェーンの連続性が
保たれる。また、クラス別の書き込みポインタテーブル
１１内の該当クラスのポインタは新たにセルが書き込ま
れたポインタに更新される。

読み出し動作は、読み出し要求が発生する毎に読み出し
ポインタ格納手段１２に示す書き込み済み待ち行列バッ
ファの先頭から読め出され、同時に読み出しポインタの
内容は１次バッファアドレスに更新される。読み出し後
のバッファは、空きバッファ列にチェーンされる。

チェーンの末端に位置するバッファの引き継ぎ先アドレ
ス部には常にエンド・マークを挿入し書き込み・読み出
し動作において、共に空きハラファまたは読み出しバッ
ファの引き継ぎ先アドレスとしてエンドマーク（ＥＭで
表示）を検出した場合は何れの動作も停止する。新たに
チェーンを形成する際は、ＢＭの代わりに新たなバッフ
ァの先頭アドレスをロードする。

［実施例］ 第２図は実施例のハードウェア構成図、第３図は初期設
定の動作シーケンス、第４図（ａ）及び第４図（ｂ）ば
書き込み動作シーケンス、第５図は読み出し動作シーケ
ンス、第６図は積込み済バッファ列の構成例、第７図は
空きバッファ列の構成例である。

第２図のハードウェア構成図は２本発明を実施するのに
必要な主要な構成が示されている。

２０は空きバッファポインタメモリ　（ＥＰＭで表示）
、２】は書き込みポインタメモリ　（ＷＰＭで表示）、
２２は読み出しポインタレジスタ（ＲＰＲで表示）、２
３．２４はセレクタ（ＳＥＬで表示）、２５は空きバッ
ファの待ち行列及び書き込みバッファ待ち行列が形成さ
れるメモリ　２６はメモリの読み出し、書き込みを制御
するメモリ制御回路、２７はメモリの初期化を行うリセ
ット回路、２８は空きバッファアドレスラッチ　２９は
積込法バッファアドレスラッチ、３０は引き継ぎバッフ
ァアドレスラッチ、３１−１〜３１−３は比較回路（Ｃ
ＯＭＰ）、３２は各部の動作を制御する制御部である。

空きバッファポインタメモリ　（ＥＭＰ）２０には、空
きバッファ列の先頭のアドレスである空きバッファポイ
ンタ（ＥＲＰ）と空きバッファ列の最後のアドレスであ
る空きバッファ積込みポインタ（ＥＷＰ）とが格納され
、書き込みポインタメモリ（ＷＰＭ）２１には、クラス
別置き込みポインタ（ＷＰ）と積込みフラグとが各クラ
ス別に書き込まれている。また、読み出しポインタレジ
スタ２２は書き込み済の待ち行列バッファの先頭のバッ
ファアドレス（現時点で読み出し優先度の最も高いバッ
ファアドレス）が格納されている。

第２図の構成を用い、制御部３２の制御による各動作シ
ーケンスを第３図乃至第５図により説明する。

第３図は初期設定の動作シーケンスである。

最初に初期設定要求が発生すると、制御部３２から初期
化信号が発生し、クラス別置き込みポインタＷＰ（第２
図の２１のＷＰＭ内）を全て０゛に設定すると共に、積
込みフラグは全てオフにし次に読み出しポインタ（第２
図のＲＰ２２内）にＥＭ（エンドマーク）を書き込み、
空きバッファポインタ（第２図のＥＰＭ２０内のＥＰＲ
）に′“００°゛を書き込み、更にその空きバッファの
アドレス“”ｏｏ”に次空きバッファのアドレスの初期
値を書き込む（以上第３図３００〜３０３）。

次に空きバッファに書き込まれた引き継ぎアドレス（書
き込みアドレス）が規定値（空きバッファに割当てられ
たアドレスの最後のアドレス）に達したか否かを判断し
く同３０４）、達していない場合、ステップ３０５〜３
０７において順次空きバッファチェーンを形成する。そ
の際、引き継ぎアドレス＋固定値を書き込みデータ（引
き継ぎ先アドレス）として書き込む。

こうして、書き込みアドレス（空きバッファの先頭）が
規定値に達すると書き込みアドレスにデータ“ＥＭ”を
書き込み、空きバッファ積込みポインタ（第２図のＥＰ
Ｍ２０を構成する図示されないレジスタＥＷＰに格納す
る）に規定値を書き込んでリターンする（同３０８，３
０９，３１０）。

このようにして形成された空きバッファ列の構成例を第
７図に示す。図に示すように、空きバッファ積込みポイ
ンタ（ＥＷＰ）は、空きバッファの最後のバッファアド
レスを保持し、空きバッファポインタ（ＥＲＰ）は、空
きバッファ列の先頭のバッファアドレスを保持（初期値
は００）する。

次に、セルが入力した時の書き込み動作シーケンスを第
４図（ａ）及び第４図（ｂ）を用い、第６図及び第７図
を参照しながら説明する。

セルが到着すると、空きバッファポインタ（ＥＲＰ）を
読み出す（第４図（ａ）　４０２　）　。この時第７図
の例では、データとして“Ｃ”（バッファアドレス）が
読み出される。獲得した空きバッファが有効か否か（読
み出しデータが“’　Ｂ　Ｍ　”でないか否か）を判断
しく同４０３）する。“’ＥＭ”の場合、後述するステ
ップ４０４以下の処理が行われるが、有効（“Ｃ゛の場
合）なら、そのアドレス“′Ｃ°゛の内容をリードする
（同４１ｏ）。この例では２　アドレス″Ｃ゛のバッフ
ァのデータ（引き継ぎアドレス）として“Ｄ′”が得ら
れる（これは第２図の空きバッファアドレスラッチ２８
に格納される）。

次に、空きバッファポインタＥＲＰ　（第２図の２０内
）にデーラダ“Ｄ”を書き込む（同４１１）。

この°′Ｄ”は後続するセルの書き込み先に使用する。

次に、入力したセルのクラス情報を取り出し。

そのクラスを用いて書き込みポインタメモリ（第２図の
ＷＰＭ２１）からクラス別置き込みポインタと積込みフ
ラグを取り出す（同４１２）。第６図の例ではクラスが
“Ｍ”の場合、書き込みポインタが“Ａ゛′で、積込み
フラグはオン（°“１′′）のデータが取り出される。

次に積込みフラグがオン（当該クラスの書き込みバッフ
ァが有るか）か否か判別しく同４１３）オンならこのク
ラスのセルが以前に書き込み済（読み出し前）であるこ
とが分かる。オフの場合図示しないが、上位のクラスの
フラグがオンになっている書き込みポインタＷＰを読み
出して、そのアドレスのバッファの引き継ぎ先アドレス
を取り出し、上記獲得したアドレス゛Ｃ″のバッファの
引き継ぎ先アドレスとして書き込み、■の経路により後
述するステップ４１６に移行する。

ステップ４１３で積込みフラグがオンの場合このクラス
（“Ｍ”とする）のセルの最後に書き込まれたバッファ
アドレス゛Ａ°°　（ステップ４１２で読み出した）の
内容を読み出す（同４１４）。

この結果、第６図の例の場合、引き継ぎ先アドレスとし
て“Ｂ”が読み出される。この引き継ぎ先アドレス“Ｂ
゛は、先に獲得した空きバッファであるアドレス゛Ｃ°
“のバッファ内の引き継ぎ先アドレスとして書き込まれ
る（同４１５）。こうして、アドレス“′Ｃ″のバッフ
ァの後にアドレス”　Ｂ　”のバッファがつながれたこ
とになる。

この後、■により第４図（ｂ）に移り、ハンｌ−（獲得
）済の空きバッファ（アドレス“Ｃ″）に、到着セル情
報（固定長）を書き込み（同４１６）。

さらに書き込みポインタメモリ　（ＷＰＭ）の該当クラ
スにデータ゛′Ｃ”°を書き込み（同４１７）以前に積
込みフラグがオフの場合１　ここでオンに設定し、アド
レス”　Ａ　”の引き継ぎ先アドレスとしてデータ“′
Ｃ゛を書き込む（同４１８）。これにより、アドレス“
′Ａパのバッファの後にアドレス“Ｃｏｏのバッファが
つながり、書き込みポインタが更新される。

次に読み出しポインタＲＰ（第２図２２）を読み出して
、その内容がＥＭ（エンドマーク）と−致するか判断し
て、一致する場合は読み出しポインタに“′Ｃ゛を書き
込む（ステップ４１９，４２０）。これは、読み出しポ
インタが最後のバッファまで読み出した状態で停止した
時、アドレスＣを先頭アドレスとしてここから読み出さ
せるものである。

上記ステップ４０３において、空きバッファがない場合
（ＥＲＩ）−ＥＭの時）、到着セルが表示するクラスに
対応するクラス別置き込みポインタ（ＷＰ）を読み出し
く同４０４）、読み出されたバッファアドレス（”Ａ’
”とする）により該当バッファの引き継ぎ先アドレスを
読み出す（同４０５）。この例ではアドレスパＢ゛″が
得られるものとする。この“Ｂ”が、ＥＭであるか否か
を判断する（同４０６）、　　もしＥＭであれば到着セ
ルを書き込むべきバッファが無いものとして到着セルを
廃棄する（同４０９）。ＥＭでない場合は、ハント済バ
ッファ（アドレス”Ｂ”）に到着セル情報を二重書き込
みして前の情報を消す（同４０７）。次に、書き込みポ
インタメモリＷＰＭにデータ゛′Ｂ”を書き込み、同時
に該当クラスの積込みフラグをオンにする（同４０８）
。上記ステップ４０４〜４０９の動作はセルが表示する
クラスＭにおいて実行される。

この他に、クラスＭ以下で、かつ積込みフラグが非活性
（オフ）の全てのクラスの書き込みボインタＷＰに対し
て、上記ステップ４０８の動作（データ゛′Ｂ゛を書き
込む）を行うようにする。

但し、この中で、既にフラグがオンのものが存在すれば
、このクラス以下の書き込みポインタＷＰについては除
外する。以−にの動作によってクラス間の優先度は保存
される。

次に第５図に示す読み出し動作シーケンスについて説明
する。

読み出し要求が発生すると、読み出しポインタ（ＲＰ）
を読み出す（第５図５０１）。第６図の例では、Ｅ”が
読み出される。次に読み出した内容が空きか（ＲＰ＝Ｅ
Ｍか）否かを判別し、空きなら終了し、データが入って
いる場合（アドレス“Ｅ”の場合）、そのアドレスの積
込み（書き込み済）バッファからセル情報（引き継ぎア
ドレスの後のデータ）を読み出す（同５０３）。読み出
したデータは、第２図のメモリ２５からデータＯＵＴと
して出力される。

この後クラス別置き込みポインタＷＰの内容と前記のデ
ータ（アドレス゛’Ｅ”）を比較し、−敗したらこのク
ラスの最後の書き込みバッファであるので、このクラス
の積込みはフラグをオフにする（同５０５，５０６）。

次に、アドレス（“Ｅｏｏ）の引き継ぎ先アドレス（”
Ｆ”）を、読み出しポインタＲＰに書き込んで読み出し
アドレスを更新する（同５０７）。そして、アドレス゛
′Ｅ”°にデータ“”　Ｅ　Ｍ　”を書き込む（同５０
８）。

これは、読み出した後のバッファを空きバッファの最後
に組み込む準備であり、続けて空きバッファ積込みポイ
ンタＥＷＰ　（第３図及び第７図参照）の内容を読み出
し、アドレスデータ（第７図の例では”ｃ”）を得て（
同５０９）、　　このアドレス（“Ｇ゛″）のバッファ
の引き継ぎ先アドレスとして前記最後に付加されるバッ
ファのアドレス“′Ｅ゛′を書き込む（同５１０）。最
後に、空きバッファ積込みポインタＥＷＰにアドレス“
Ｅｏ”を書き込み（同５１１）、空きバッファの最後の
バッファ位置を表示する。

」二重の動作において１書き込み、読み出し動作では、
共に空きポインタ、読み出しポインタのそれぞれがエン
ドマーク（ＥＭ）を表示した時点で停止する。そのため
に、チェーンの末端に位置するバッファの引き継ぎ先ア
ドレス部には常にＥＭを挿入する。新たに、チェーンを
形成する際には。

各ポインタの先頭アドレスがロードされる。

通信別置き込みポインタはセルの到着毎に更新されるが
、−旦該クラスのセルが積込み済バッファになくなると
次に該クラスのセルが到着した場合、該クラスより上位
のクラスの内セルが積込み済の状態にある最下位クラス
の書き込みポインタを用いて、そのバッファのつなぎ込
み動作が行われる。

上記のように、クラス別の処理優先度が保証され、優先
度が高いセルについて遅延時間及び廃棄特性が改善され
る。

［発明の効果］ 本発明によれば単独行列を用いて、セル毎に処理優先度
（通信種別）を付加できるため、高速と低速の混合処理
を必要とする通信において１比較的低速動作の装置を用
いて機能を満足させることが可能である。また、複数種
類の通信クラスを持つセルを一括処理できるため１通信
クラス間のトラフィックの偏りにも柔軟に対応すること
ができバッファの分割損（バッファを分割して管理する
ための負担）が緩和できる。

【図面の簡単な説明】

第１図は本発明の原理構成図、第２図は実施例のハード
ウェア構成図、第３図は初期設定の動作シーケンス、第
４図（ａ）及び第４図（ｂ）は書き込み動作シーケンス
、第５図は読み出し動作シーケンス。 孝 第６図は積込みバッファ列の構成例、第７図は空へ きバッファ列の構成例、第８図は従来のＡＴＭスイッチ
の構成例である。 第１図中 １０：固定長情報のセル １１：クラス別の書き込みポインタテーブル１２：読み
出しポインタ格納手段 １３：空きバッファポインタ格納手段 １４：書き込みバッファ １５：空きバッファ

Claims (4)

【特許請求の範囲】
1. （１）所定長のデータの書き込みと読み出しを行うＦＩ
   ＦＯ内の待ち行列バッファ構成方式において、 バッファ列をアドレス引き継ぎによる単独チェーン形式
   で構成し、 入力するデータに処理優先度を表すクラス情報を付加し
   、 データが書き込まれたバッファ位置を示すクラス別の書
   き込みポインタテーブル（１１）を設け、入力データを
   空きバッファ（１５）に書き込み、該空きバッファ（１
   ５）をデータのクラスに応じたチェーン内の位置に挿入
   してつなぎ替えることを特徴とする待ち行列バッファ構
   成方式。
2. （２）ヘッダと情報とで構成する所定長のセルを格納し
   て読み出すＦＩＦＯ内の待ち行列バッファ構成方式にお
   いて、 各セルのヘッダに処理優先度を表すクラス情報を付加し
   、 優先度の高いクラスから順次アドレス引き継ぎによる単
   独チェーン形式でセルが書き込まれる待ち行列バッファ
   と、 クラス別のセル書き込みバッファの後端の位置を格納す
   る書き込みポインタテーブル（１１）と、空きバッファ
   位置を示す空きバッファポインタ格納手段（１３）と、 書き込み待ち行列バッファのアドレス引き継ぎにより更
   新される読み出しポインタ格納手段（１２）とを備え、 入力セルを空きバッファ（１５）に書き込み、該セルの
   クラスに対応して書き込みポインタテーブルを用いて待
   ち行列バッファ中につなぎ替えることを特徴とする待ち
   行列バッファ構成方式。
3. （３）請求項（２）において、 入力セルを書き込むべき空きバッファをチェーン形式で
   保持する空きバッファポインタ格納手段（１３）を備え
   ることを特徴とする待ち行列バッファ構成方式。
4. （４）請求項（１）〜（３）において、 クラス別の書き込みポインタテーブル（１１）に、各ク
   ラスのセルが書き込まれて読み出しが終了していないこ
   とを表す積込みフラグが格納されることを特徴とする待
   ち行列バッファ構成方式。