JPH02220533A - セル競合制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、非同期転送モード（ＡＴＭ）を用いたスイッ
チ装置において、同一時刻に同一宛先に出力させるセル
が別々の入力ポートに到着する際に生じる競合を待ち合
わせにより解消するセル競合制御方式に関する。

〔従来の技術〕

第１６図は、入力ポートに入力蓄積装置（バッファ）を
有するスイッチ装置の構成を示す。図におイテ、９０１
．．９０１．、　・・・および９０２゜。

９０２、、・・・はセルを示す。複数のセル９０１゜９
０２のそれぞれにはヘッダ９０５が含まれ、各セルの宛
先情報が記される。セル９０１，９０２は複数の入力ボ
ート９ｏｏｏ、９００１　、・・・に供給され、ヘッダ
９０５に対応する複数の出力ボート９１Ｌ、９１１＋、
・・・から出力される（セル９０３＠　、９０３．、　
・・・および９０４゜、９ｏ４１、・・・）。

一般にセル競合制御は、入力制御部９０９゜。

９０９、、・・・　と、競合制御回路９１２により実現
される。各々の機能を具体的に説明する。

入力ボート９００ａ、９００ｔに供給されるセル９０１
６．９０１１はそれぞれバッファ９０７゜、９０７．に
−旦蓄積されると共に、ヘッダ９０５を入力制御部９０
９゜および９０９１に複写される。

入力制御部９０９゜および９０９．は、到着したセルの
ヘッダ９０５よりセルの宛先を解読し、それに対応する
空間スイッチ９１０の出力ボート番号を求め、この出力
ボート番号を競合制御回路９１２に転送する機能を果た
している。

その際、各入力ポート９００は独立に出力ボート番号を
競合制御回路９１２に送るため、セルが要求する出力ボ
ート番号が重複し同一の出力ポートに複数の送出要求が
生しることがある。しかし、バッファ９０７と出力ポー
ト９１１を接続する空間スイッチ９１０は、複数の入力
ポート９００および出力ポート９１１を１対１で接続さ
せる必要がある。このため、競合制御口Ｉａ９１２は複
数の入力ポート９００から同一の出力ボート番号を宛先
とすＳセルが供給される場合には、対象となる複数の入
力ポートから１つを選択し、出力ポート９１１での競合
を回避させる機能を果たしている。

また、その選択結果は入力制御部９０９に転送され、入
力制御部９０９は、それにしたがってセル９０１を送出
する機能を果たしている。

第１２図は、従来のセル競合制御方式を示す。

（引用文献：　Ｊｏｓｅｐｈ　Ｙ、Ｈｕｉ　ａｎｄ　Ｅ
ｄｗａｒｄ　Ａｒｔｈｕｒｓ“＾Ｂｒｏａｄｂａｎｄ　
Ｐａｃｋｅｔ　５ｗ１ｔｃｈ　ｆｏｒ　Ｉｎｔｅｇｒａ
ｔｅｄＴｒａｎｓｐｏａＬ”、ＩＥＥＥ　　Ｊｏｕｒｎ
ａｌ　　ｏｎ　　５ｅｌｅｃｔｅｄ　　Ａｒｅａｓ　　
１ｎＣｏａ＋ｍｕｎｉｃａｔｉｏｎｓ、　ｖｏｌ、５ａ
ｃ−５＋　Ｎｏ８．　ｐｐ１２６４−１２７３゜ｏｃｔ
ｏｂｅｒ　　１９８７） 第１７図において、端子９５３゜〜９５３．および端子
９６０６〜９６０ｓ　カＩＪＬ＆制御ｒｍｔａ９１２の
入出力端子を示し、第１６図の入力制御部９０９゜、９
０９＋　・・・との間で制御情報を送受する。

ハ・／チ中−網９５４．９５７およびバンヤン網９５９
は複数のスイッチエレメントによって構成されている。

９５１および９５２は競合制御回路９１２への入力信号
を示す。９５１（（１）〜（４））は入力ボート番号信
号であり、９５２（■〜■）はそれぞれの入力ポートか
ら供給されるセルのヘッダが持つ宛先（出力ポート番号
信号）である。

これらの入力信号はバッチャ−網９５４に供給され、出
力ポート番号信号９５２に注目して番号の小さい順に並
べ換えられる。この処理において、入力ポート番号信号
９５１および出力ポート番号信号９５２は対にして考え
られるので、バッチャ−綱９５４の出力として入力信号
はリンク９５５・〜９５５３に示すように並べ換えられ
る。

次に、リンク９５５゜〜９５５３では、リンク９５５Ｉ
　とリンク９５５．、　　リンク９５５□とリンク９５
５．、　　リンク９５５．とリンク９５５□の出力ポー
ト番号信号９５２が照合される（図中上下方向矢印参照
）。この結果、出力ポート番号信号９５２が異なればそ
のリンクの出力ポート番号信号９５２は有効となり、一
致すれば一方のリンクの出力ポート番号信号９５２は無
効となり、以後の処理は行なわれない。第１７図におい
て、リンク９５５１とリンク９５５□の出力ポート番号
信号９５２は一致するので、リンク９５５□は無効とな
る。その他は有効となる。このようにして、同じ出力ポ
ートへ転送しようとする複数の要求の中から１つのみが
選択されることになる。

次に、選択されたリンク９５５゜、リンク９５５１＋　
　リンク９５５８はバッチャ−Ｍ４９５７に供給される
。このバッチャ−綱９５７においては、入力ポート番号
信号９５１に注目して番号の小さい順に並べ換えられる
。このバッチャ−Ｗ４９５７の出力としてリンク９５８
゜〜９５８．に示す信号が得られ、バンヤン網９５９に
供給される。

バンヤン網９５９は入力ボート番号信号９５１に注目し
て該当する入力ポートにセル９０１，９０２を導き、選
択された入力ボート番号信号９６１を出力する。端子９
６０ｏ〜９６０．は競合制御回路９１２の出力端子であ
ると共に、各入力制御部９０９に接続されており、選択
結果を入力制御部９０９に転送する。

よって、入力制御部９０９ｏおよび９０９．は転送要求
として第１７図に示すように入力ボート番号信号９５１
および出力ボート番号信号９５２を競合制御回路９１２
に転送し、競合制御回路９１２の端子９６０より送出が
可能な入力ボート番号９６１を受信することでセルの送
出許可を得る。

以上より、入力ポート９００と出力ポート９１１の１対
ｌ対応の接続が可能になる。

（例えば端子９０３２に供給されるセル）の存在する入
力ポートは、次の送出要求タイミングに再度送出要求を
出すことになる。このため、その入力ポートは再度送出
要求を行なえるまで待たされその入力ポートは閉塞する
。よって、スループットが最大スループットの５８パ一
セント程度で飽和することが知られており（前記引用文
献中に記載されている）、従来の方式ではスループント
が低下するという問題点があった。

また、スイッチが大規模になるとスイッチエレメントが
大量に必要となり、ハードウェア量が激増するという問
題点があった。

本発明は、このような点にかんがみて創作されたもので
あり、ハード規模を大きくすることなくスループットが
向上するようにしたセル競合制御方式を提供することを
目的としている。

〔発明が解決しようとする課題〕　　　　　　　　　　
〔課題を解決するための手段〕上述したようなセル競合
制御方式では、送出要　　　上述した目的を達成するた
めに、本発明のセル求を出しながら送出許可を受けられ
なかったセル　　競合制御方式は、入力ボートのそれぞ
れに対応して設置され、導入されるセルを複数個蓄積し
て１つずつ出力する複数の入力蓄積手段と、入力蓄積手
段から出力されるセルが出力ポートに転送される転送時
刻を複数の出力ポート毎に予約する出力管理手段と、入
力蓄積手段のそれぞれに対応して設置され、入力蓄積手
段から出力されるセルの転送時刻に転送先の出力ポート
が前記出力管理手段に予約されていれば、別なセルを出
力するように入力蓄積手段に指示する複数の入力制御手
段と、入力蓄積手段のそれぞれから出力されるセルを複
数の入力ボート毎に転送時刻に対応する領域に格納し、
転送時刻順に出力する入力管理手段と、入力管理手段か
ら供給されるセルを転送先の出力ポートに出力する切換
手段とを具えるように構成されている。

〔作　用〕

入力蓄積手段にセルが導入されると、出力管理手段にお
いて、このセルの転送時刻を転送先の出力ポートに予約
する。転送時刻を予約されたセルは、入力管理手段の転
送時刻に対応する領域に格納され、転送時刻になると切
換手段に供給されて転送先の出力ポートに送出される。

出力管理手段に転送時刻を予約する際に、この転送時刻
に転送先の出力ポートが予約されていれば、入力制御手
段の指示に基づいて、入力蓄積手段が蓄積する別なセル
が供給される。

本発明にあっては、複数のセルを入力蓄積手段に蓄積し
て、これらのセルから入力管理手段および出力管理手段
によって転送時刻および出力ポートが一致しないセルを
順次切換手段に供給することができるので、スループッ
トが向上する。

〔実施例］ 以下、図面に基づいて本発明の実施例について詳細に説
明する。

第２図は、４つの入力ポート（１）〜（４）と４つの出
力ポート■〜■を具える場合の第１実施例の構成を示す
。

図において、２０１０〜２１０３は入力蓄積装置（バッ
ファ）、２００．〜２０ｏ、はバッファ２０１に既に蓄
積されているセルの宛先情報、２０４は空間スイッチ、
２０２゜〜２０２．はポインタ２０３を持つ入力制御部
、２１５は競合制御回路を示す９Ｍ合制御回路２１５は
、送出管理テーブル２０５と出力予約テーブル２０６を
有し、送出管理テーブル２０５と出力予約テーブル２゜
６はリンク２０７．〜２０７４によって接続されている
。

各入力制御部２０２のポインタ２０３は、移動命令がな
ければバッファ２０１に蓄積されているセルの一番先頭
を示す。

送出管理テーブル２０５は、マトリクス構造をしており
、行は各入力ポートに対応し、列は予約されているセル
を空間スイッチ２０４へ送出する未来送出時刻ＣＬ　＋
１　）、（ｔ＋２）、（（＋３）、（ｔ＋４）（現在の
時刻りに１〜４を加算、４は入力ボート数）に対応する
。

ここで用いている時刻ｔは、セルを空間スイッチ２０４
に供給すると進む時刻である。以後この時刻の単位を「
セル時間」と称する。

送出管理テーブル２０５は、入出力端子２０８を介して
入力制御部２０２と制御情報（セル送出要求等）の送受
を行なうと共に、バッファ２０１から予約に成功したセ
ルを受信して送出時刻まで蓄積する。また、送出管理テ
ーブル２０５の現在の時刻りに格納されているセルを空
間スイッチ２０４に供給する。各入力ポートと未来送出
時刻（ｔ＋１）〜（ｔ＋４）との接続関係は後述する。

出力予約テーブル２０６は空間スイッチ２０４の出力ポ
ートの予約の有無を表示する。この出力予約テーブル２
０６は、マトリクス構造をしており、その行は各出力ポ
ートに対応し、列は現在の時刻りに１〜４を加算した未
来送出時刻に対応する。

送出管理テーブル２０５．出力予約テーブル２０６は、
初期状態では何も格納していない「空」（予約可能）を
示す。予約が行なわれると送出管理テーブル２０５では
該当する部分に送出予約済セルが格納される。出力予約
テーブル２０６では予約済であれば例えばデータ“１″
゛を格納し、予約可能であればデータパ０“が格納され
る。第２図では、記憶されたセルの出力ボート番号およ
び斜線を表示することにより「予約済」を示している。

第１実施例では、バッファ２０１は第１図の入力蓄積手
段、入力制御部２０２は入力制御手段、出力予約テーブ
ル２０３は出力管理手段、送出管理テーブル２０５は入
力管理手段、空間スイッチ２０４は切換手段に対応して
いる。

次に予約手順を詳しく説明する。

バッファ２０１゜〜２０１３のそれぞれに宛先情報２０
０゜〜２００４を持つセルが先頭から到着順に蓄積され
ている。予約過程の始めではポインタ２０３はバッファ
２０１の先頭セル（最も古いセル）を示すものとする。

入力制御部２０２は、ポインタ２０３の指示するセルの
宛先情報を複写し、それを送出管理テーブル２０５の入
出力端子２０８に転送する。

送出管理テーブル２０５では、各セルの宛先情報を異な
る未来送出時刻に受は付けている。

例えば、入力制御部２０２゜から供給される宛先情報は
未来送出時刻（ｔ＋１）、入力制御部２０２、から供給
される宛先情報は未来送出時刻（ｔ＋２）、入力制御部
２０２□から供給される宛先情報は未来送出時刻（ｔ＋
３）、入力制御部２０２１から供給される宛先情報は未
来送出時刻（ｔ＋４）に受は付けられる。この場合、宛
先情報２００゜〜２００３は送出管理テーブル２０５中
の接続点２１０ｏ〜２１Ｏ１を経由して各々対応するリ
ンク２０７．〜２０７４によって出力予約テーブル２０
６の同じ未来送出時刻の列に供給される。

各入力ポートに対応する接続点２１００〜２１０３は周
期的に移動する（後述する）。

出力予約テーブル２０６では、未来送出時刻毎に供給さ
れてくる宛先情報２００゜〜２００．に対応する出力ポ
ートの予約状況を参照する。

以上の動作において送出管理テーブル２０５の接続点２
１０と、出力予約テーブル２０６の出力ポートの予約状
況の状態により以下の４つの場合が生じる。

■接続点２１０が「空」、出力ポート予約状況が「空」
の場合。

■接続点２１０が「空」、出力ポート予約状況が「予約
済」　（図中斜線部分）の場合。

■接続点２１０が「予約済」　（図中斜線部分）、出力
ポート予約状況が「空」の場合。

■接続点２１０が「予約済」　（図中斜線部分）、出力
ポート予約状況が「予約済Ｊ　（図中斜線部分）の場合
。

■の場合、送出管理テーブル２０５と出力予約テーブル
２０６を経由してセルの予約が行なわれる。この予約は
、送出管理テーブル２０５の接続点２１０に出力ポート
番号を蓄積し、出力予約テーブル２０６の宛先の出力ポ
ートを「予約済ｊにかえ、入力制御部２０２に予約終了
を通知する八〇に信号を転送して行なわれる。

■の場合、送出管理テーブル２０５は予約可能であるが
（未来送出時刻は受は付は可能であるが）、出力予約テ
ーブル２０６で予約不可能であるので（宛先として指定
した出力ポートが既に予約されているので）、予約が行
なえなかったことを通知するＮＡＣＫ信号を入力制御部
２０２に転送する。

■の場合、出力予約テーブル２０６は予約可能であるが
送出管理テーブル２０５で予約が不可能であるので、Ｎ
ＡＣＫ信号を入力制御部２０２に転送する。

■の場合、送出管理テーブル２０５．出力予約テーブル
２０６で予約が行なえないのでＮＡＣＫ信号を入力制御
部２０２に転送する。

ＡＣＫ信号が転送された場合、ポインタ２０３の指し示
すセルを送出管理テーブル２０５の接続点２１０に転送
し、転送によって生じたバッファ２０１内の空きを後ろ
に蓄積されたセルで順次つめて予約過程を終了する。

ＮＡＣＫ信号が転送された場合、ＮＡＣＫ信号に応じて
入力制御部２０２は移動命令を出力し、ポインタ２０３
をバッファ内の１つ後ろ（次に古いセル）を指し示すよ
うにする。そしてそのセルについて上記の予約試行動作
を繰り返す。

すべての入力ボートの予約過程が終了し、送出管理テー
ブル２０５の現在の時刻ｔのセルが空間スイッチ２０４
に供給されると、送出管理テーブル２０５および出力予
約テーブル２０６が未来送出時刻毎に格納するすべての
データはそれぞれ（ｔ＋１）→１．　　（む＋２）→（
ｔ＋１）、（ｔ＋３）→（Ｌ＋２）、（ｔ＋４）→（ｔ
＋３）にシフトすることになる。これは時刻がｒｌＪセ
ル時間進むことを表す。

予約に失敗した入力ボートは独立に「１」セル時間の間
で可能な限り複数回（回路実現上限界が生じる）移動命
令を出力してポインタ２０３を後ろのセルに移動し上記
予約試行動作を繰り返す。

それでもなお予約が成功しない場合、その入力ボートは
セルを予約しないで予約過程を終了する。

第２図の例では、入力ボート（１）から供給される宛先
情報２０００以外は予約に成功し、出力予約テーブル２
０６の該当する出力ポートの予約状況を「予約済」　（
図中○印）にかえ、入力制御部２０２〜２０２．にＡＣ
Ｋ信号を転送する。ＡＣＫ信号を転送された入力制御部
２０２１〜２０２３はそれぞれポインタ２０３１〜２０
３．で指し示すセルを送出管理テーブル２０５の接続点
２１０、〜２ＩＯ１に転送する。

宛先情報２００゜（出力ポート■）は既に未来送出時刻
（ｔ＋１）の入力ボート（２）に受は付けられており「
予約済」である。よって、入力制御部２０２゜は宛先情
報２００゜の次に古い宛先情報２００、（出力ポート■
）をコピーし、宛先情報２００４を送出管理テーブル２
０５の接続点２１０゜を経由してリンク２０７４によっ
て出力予約テーブル２０６に供給する。出力ポート■は
「空」であるので予約が成功し、ＡＣＫ信号が入力制御
部２０２゜に転送される。ＡＣＫ信号に応じてポインタ
２０３゜が指し示すセルが送出管理テーブル２０５の接
続点２１０゜に転送される。

ｉｉ′　　　　　と　　ボー　の 第３図に送出管理テーブル２０５が受は付けるセルの未
来送出時刻と入力ボートとの接続関係を示す。

第２図に示す接続点２１０．〜２１０．は送出管理テー
ブル２０５の対角線上に並んでいる。常にこの状態でセ
ルを受は付ける場合、入力ポート（１）から供給される
セルは他の入力ポートより優先的に未来送出時刻の宛先
出力ボートを予約できる。

従って、各入力ポートが平等に出力ポートを選択できる
ように未来送出時刻を決定する接続点２１０の配置を周
期的に変更する。

例えば接続点２１０の配置を口→Δ→Ｏ→◎（第３図（
ｂ）参照）のように４つの配置で変更するものとする。

この４つの配置を第３図（ａ）に示す。

また、第３図（ｃ）は、送出管理テーブル２０５が格納
するデータを送出時刻でｒｌ、セル時間道める（ｔ＋１
→Ｌのようにシフトする）替わりに、横軸に絶対時刻を
とり、現在時刻ｔの進みと共に送出管理テーブル２０５
が左に延長されていくように表現を書き換えたものであ
る。

図において、口等の記号内の数字は予約された順番を示
す。

例えば入力ポート（１）は、最初の４セル時間は未来送
出時刻（Ｌ＋１）（口で示す配置）で送出を受は付ける
。次の４セル時間は未来送出時刻（し＋４）（Δで示す
配置）、続く４セル時間は未来送出時刻（ｔ＋３）（Ｏ
で示す配置）、続く４セル時間は未来送出時刻（ｔ＋２
）（◎で示す配置）で送出を受は付ける。

第３図（Ｃ）に示す太線内は、現在の時刻（絶対時刻）
も＝５における送出管理テーブル２０５の内容を示す。

図かられかるように接続点２１０の配置は、過去の方向
には戻さないように構成されており、セルの順番は逆転
しない。

このようにして、接続点２１０の配置を周期的に変更す
ることにより、各入力ボート間の予約不平等をなくすこ
とが可能となる。

上述した予約過程では、接続点２１０の配置の周期式な
変更を４セル時間で行なったが、６セル時間で変更をお
こなった例を第４図に示す。このように、変更時間は任
意で良い。

ニー」１口１１但 第５図は、第２図に示した第１実施例を基にした別な構
成の第２実施例を示す。第２図と同一符号は同一回路部
を示す。

第５図において、第２実施例は、バッファ２０１と、バ
レルシフタ５０２と４つの出力予約テーブル５０３６〜
５０３．と４つの送出管理テーブル５０５゜〜５０５．
と空間スイッチ２０４を具える。出力予約テーブル５０
３゜〜５０３３は、各出力ポートに対応する４つの予約
状況格納部と未来送出時刻格納部を具え、送出管理テー
ブル５０５゜〜５０５．は、各入力ポートに対応し、送
出時刻毎の宛先格納部を具えている。

バレルシフタ５０２．出力予約テーブル５０３および送
出管理テーブル５０５は、競合制御回路を構成する。

バッファ２０１゜〜２０１．から供給される宛先情報５
００゜〜５００３は、バレルシフタ５０２を経由し、そ
れぞれに対応するリンク５０７〜５０７４によって対応
する出力予約テーブル５０３に供給される。出力予約テ
ーブル５０３のそれぞれは興なる未来送出時刻に対応し
、例えば図に示すように入力ポート（１）は出力予約テ
ーブル５０３、の未来送出時刻（Ｌ＋４）に接続されて
いる。

宛先清報５００゜が出力ポート■であれば出力予約テー
ブル５０３．の出力ポート■の予約状況を確認する（図
中「Ｎ」は予約可能、「Ｒ」は予約不可能〕。出力予約
テーブル５０３で予約の有無を確認すると、予約可能な
セルはバレルシフタ５０２の入出力端子５０Ｇを経由し
て送出管理テーブル５０５の対応する入力ポートの未来
送出時刻に格納される。例えば宛先情報５００゜のセル
であれば、送出管理テーブル５０５゜の未来送出時刻（
ｔ＋４）に格納される。

基本的な予約試行動作は第１実施例と同じである。

本実施例は、入力ポート間の不平等をなくす機能を有す
るバレルシフタ５０２を具えることを特徴とする。

以下、第６図、第７図を参照してバレルシフタ５０２の
動作を説明する。図において、予約時刻として記載され
ているのは絶対時刻であるが、実際には絶対時刻を基に
した未来送出時刻として処理される。例えば絶対時刻ｔ
＝２における予約時刻ｔ＝３．４，５．６はそれぞれ現
在の時刻り一２の場合の（ｔ＋１）、（ｔ＋２）、（ｔ
＋３）（ｔ＋４）となる。

まず、絶対時刻１＝０において、第６図（ａ）に示す未
来送出時刻（Ｌ＋４．）に対応する出力予約テーブル５
０３３　　（図中太い矢印物）が格納する各出力ポート
の予約データが消去される。

入出力端子５０６゜に供給される宛先情報５００゜はリ
ンク５０７゜、入出力端子５０６．に供給される宛先情
報５００．はリンク５０７．、入出力端子５０６□に供
給される宛先情報５００□はリンク５０７□、入出力端
子５０６．に供給される宛先情報５００３はリンク５０
７．に出力される。リンク５０７のそれぞれは出力予約
テーブル５０３゜〜５０３．に供給され、予約動作が行
なわれる。

空間スイッチ２０４に現在の時刻りからセルが供給され
ると「１」セル時間進む。各出力予約テーブル５０３の
未来送出時刻が（ｔ＋１）→むにシフトする。

絶対時刻Ｌ＝１において、新たに未来送出時刻（Ｌ　＋
４　）に対応する出力予約テーブル５０３゜（図中太い
矢印に））が格納する各出力ポートの予約データが消去
され、出力予約テーブル５０３゜は未来送出時刻（ｔ、
＋４　（ボート数））を受は付ける。

バレルシフタ５０２内の接続が切り替わり、入出力端子
５０６゜に供給される宛先情報５００゜はリンク５０７
＋、入出力端子５０６１に供給される宛先情報５００．
はリンク５０７□、入出力端子５０６．に供給される宛
先情報５００、はリンク５０７３、入出力端子５０６．
に供給される宛先情報５００３はリンク５０７゜に出力
される（第６図（ｂ）参照）。

このようにしてバレルシフタ５０２が切り替わり、各入
力ポートが平等に受は付けられる。

以下同様にして繰り返される。

データの消去は第６図および第７図に示す太い矢印（＋
−）のように未来送出時刻（ｔ＋４）に当たる出力予約
テーブル５０３゜〜５０３３を巡回する。

ここで、４セル時間に１回バレルシフタ５０２の動作を
停止する。この動作により、例えば入力ポート（１）の
未来送出時刻は（を十ｉ）→（ｔ＋１）→（ｔ、＋１）
→（ｔ＋１）（停止）→（ｔ＋４）→（ｔ＋４）→（ｔ
＋４）→（ｔ＋４）（停止）→（Ｌ＋３）→（ｔ＋３）
→（ｔ＋３）→（１＋３）（停止）→（−ｔ＋２）→（
ｔ＋２）→（１＋２）→（ｔ＋２）と変化し、第１実施
例で示した第３図（ｃ）と同様になる。

バレルシフタ５０２の停止動作周期は任意であり、第８
図に６セル時間毎にバレルシフタ５０２を停止した例を
示す。

Ｕ実益ｉｌｌ 第９図に本発明の第３実施例を示す。図において第２図
と同一符号は同一回路部である。

第３実施例は、バッファ２０１　タイムループ８０２．
４つの出力予約テーブル８０３゜〜８０３１．４つの送
出管理テーブル８０５゜〜８０５１．空間スイッチ２０
４を具える。出力予約テーブル８０３のそれぞれは、出
力ポートに対応する４つの予約状況格納部と未来送出時
刻格納部を具え、送出管理テーブル８０５のそれぞれは
、入力ボートに対応して未来送出時刻毎の送出セルの格
納部を具えている。

出力予約テーブル８０３．送出管理テーブル８０５およ
びタイムループ８０２は、競合制御回路を構成する。

バッファ２０１のそれぞれから構成される装置は、対応
する出力予約テーブル８０３において予約が可能である
ことを確認し、予約可能であれば対応する送出管理テー
ブル８０５にセルを供給する。送出管理テーブル８０５
のそれぞれは現在の時刻りから空間スイッチ２０４に順
次セルを送出する。

タイムループ８０２は、出力予約テーブル８０３の同じ
出力ポートおよび未来送出時刻を順次接続し、出力予約
テーブル８０３゜〜８０３３の予約状況と予約時刻を送
受し、それによってバッファ２０１（各入力ポート）と
未来送出時刻の接続関係を換える働きを有している。

第９図において、予約開始点は未来送出時刻（む＋４）
に対応する出力予約テーブル８０３２の右上のような黒
塗、予約終了点は未来送出時刻（ｔ＋１）に対応する出
力予約テーブル８０３３の右上のような白抜で示す。

以下、第１θ図〜第１２図を使用してタイムループ８０
２の動作を説明する。

第１０図（ａ）において、出力予約テーブル８０３３は
、未来送出時刻（ｔ＋４）における各出力ポートの予約
データを持ち、他の出力予約テーブル８０３は、それぞ
れループ方向に向かって、未来送出時刻（ｔ＋３）、（
ｔ＋２）、（ｔ＋１）の予約データを持つ。この状態で
、各バッファ２０１と送出管理テーブル８０５と出力予
約テーブル８０３の間では、第１実施例に述べた予約過
程が実行される。

第１０図（ａ）に絶対時刻む−０における出力予約テー
ブル８０３を示す。未来送出時刻を決定するために、予
約開始時刻と予約終了時刻が設定される。ここでは、入
力ボート番号（１）に対応する出力予約テーブル８０３
゜（未来送出時刻（１十１））を予約終了点、入力ボー
ト番号（４）に対応する出力予約テーブル８０３３　（
未来送出時刻（ｔ＋４））を予約開始点とする。

第３実施例では、予約が成功すると、送出管理テーブル
８０５と出力予約テーブル８０３のデータを第１実施例
と同様に更新すると共に、予約終了点の出力予約テーブ
ル８０３゜が格納するデータを消去する。

この後、各出力予約テーブル８０３のデータをタイムル
ープ８０２を通してループ方向（（し＋４）→（Ｌ　＋
３　）→（ｔ＋２）→（ｔ＋１）→（ｔ＋４））にシフ
トする。このとき、（ｔ＋１）→（ｔ＋４）のシフトで
はデータが消去された出力予約テーブル８０３ｏからの
シフトが行なわれるので、予約開始点である出力予約テ
ーブル８０３、のデータは全て予約可能な状態となる。

ここで、各入力ポートを平等に受は付けために、４セル
時間毎に１回はシフトを行なわず、予約開始点、予約終
了点をループ方向と反対に動かして位置を変更する（第
１０図（ｅ）参照）。

これにより、例えば入力ポート１）から供給されるセル
が受は付けられる未来送出時刻は、絶対時刻の経過と共
に（ｔ＋１）→（乞＋１）→（【＋１）→（ｔ＋１）→
（ｔ＋４）→（ｔ＋４）→（ｔ＋４）→（ｔ、＋４）→
（ｔ＋３）→（ｔ＋３）→（ｔ＋３）→（ｔ＋３）→（
ｔ＋２）→（１十２）→（ｔ＋２）→（ｔ＋２）・・・
と変化する（第１Ｏ図〜第１２図参照）。

このようにしてバッファ２０１と予約時刻との関係が変
化し、入力ポート間の不平等をなくすことができる。

第１Ｏ図〜第１２図に示す動作を行なうことで第１実施
例の第３図（ｃ）と等価な動作を実行できる。また、予
約開始点、予約終了点の変更周期は任意であり、上記に
述べた４セル時間に限定されるものではない。第１３図
〜第１５図に６セル時間毎に１回行なう例査示す。この
例は第１実施例で示した第４図と等価な動作となる。

■６　　　ｌのまとめ 入力蓄積装置の中に蓄積された複数のセルのうちから、
出力予約テーブル２０３　（５０３，８０３）、送出管
理テーブル２０５　（５０５，８０５）を用いて未来時
刻に送出可能なセルを検索することにより、セルの送出
予約を行なう。このセルの送出時刻の決定は、送出まで
の間の時刻を利用して各入力ポートの入力蓄積装置が順
次その時刻の時刻管理手段にアクセスし、予約してい（
ので、送出するときには、はとんど全部の出力ボートが
予約済となり、スルーブツトが向上する。

〔発明の効果〕

上述したように、本発明によれば、複数のセルを入力蓄
積手段に蓄積して、これらのセルから入力管理手段およ
び出力管理手段によって転送時刻および出力ボートが一
致しないセルを順次切換手段に供給することができるの
で、スループットが向上する。

【図面の簡単な説明】

第１図は本発明の原理図、 第２図は本発明の第１実施例によるセル競合制御方式の
構成図、 第３図、第４図は第１実施例の予約管理テーブルの説明
図、 第５図は本発明の第２実施例によるセル競合制御方式の
構成図、 第６図、第７図、第８図は第２実施例の予約管理テーブ
ルの説明図、 第９図は本発明の第３実力缶例によるセル競合制御方式
の構成図、 第１Ｏ図、第１１図、第１２図、第１３図、第１４図、
第１５図は第３実施例の予約管理テーブルの説明図、 第１６図は従来のセル競合制御方式の構成図、第１７図
は競合制御回路の構成図である。 図において ２０１．９０７はバッファ、 ２０２．９０９は入力制御部、 ２０３．５０３，８０３は出力予約テーブル、２０４．
９１０は空間スイッチ、 ２０５．５０５．８０５は送出管理テーブル、２０７．
５０７，９５５．９５８はリンク、２０８．５０６は入
出力端子、 ２１５．９１２は競合制御回路、 ５０２はバレルシフタ、 ８０２はタイムループ、 ９００は入力ボート、 ９０１．９０２　９０３ ９０５はヘッダ、 ９１１は出力ボート、 ９５１．９６１は入力ボート番号信号、９５２は出力ボ
ート番号信号、 ９５３．９６０は端子である。 ９０４はセル、 ６０ｈ６ 第 図 第 １′、４ 第１６ 図

Claims (1)

【特許請求の範囲】
1. （１）複数の入力ポートから複数の出力ポートにセルを
   転送する際のセル競合制御方式において、前記入力ポー
   トのそれぞれに対応して設置され、導入されるセルを複
   数個蓄積して１つずつ出力する複数の入力蓄積手段と、 前記入力蓄積手段から出力されるセルが前記の出力ポー
   トに転送される転送時刻を前記複数の出力ポート毎に予
   約する出力管理手段と、 前記入力蓄積手段のそれぞれに対応して設置され、前記
   入力蓄積手段から出力されるセルの前記転送時刻に転送
   先の出力ポートが前記出力管理手段に予約されていれば
   、別なセルを出力するように前記入力蓄積手段に指示す
   る複数の入力制御手段と、 前記入力蓄積手段のそれぞれから出力されるセルを前記
   複数の入力ポート毎に前記転送時刻に対応する領域に格
   納し、前記転送時刻順に出力する入力管理手段と、 前記入力管理手段から供給されるセルを転送先の出力ポ
   ートに出力する切換手段と、 を具えるように構成することを特徴とするセル競合制御
   方式。