JP3061042B2 - Ａｔｍスイッチ - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はＡＴＭスイッチに係
わり、特に出力ポートで同一のセルが衝突するのを回避
するようにした入力バッファ型のＡＴＭスイッチに関す
る。

【０００２】

【従来の技術】ＡＴＭ（Asynchronous Transfer Mode：
非同期転送モード）スイッチは、スイッチ入力ポートか
らＡＴＭセルを入力して出力ポートから出力する際のそ
の出力先を設定するスイッチである。すなわち、ＡＴＭ
スイッチは、入力ポートに入力されたＡＴＭセル（以
下、単にセルと称する。）を一時バッファに蓄積して、
そのスイッチング動作によって所定の出力先からこれを
出力するようになっている。ＡＴＭスイッチは、この一
時バッファの構成方法によって、入力バッファ型、共通
バッファ型、出力バッファ型あるいはクロスポイントバ
ッファ型等の種類に分けられている。

【０００３】図２１は、従来の入力バッファ型のＡＴＭ
スイッチの構成の一例を表わしたものである。このＡＴ
Ｍスイッチ２０１は、４×４のＡＴＭスイッチの構成を
表わしたものである。ＡＴＭスイッチ２０１は、第１〜
第４の入力バッファ部２０２ ₁〜２０２₄を備えており、
これらにはそれぞれセルを入力するための第１〜第４の
入力ポート２０３₁〜２０３₄が対応して配置されてい
る。第１〜第４の入力バッファ部２０２₁〜２０２₄から
出力されるセルは自己ルーチング部２０５に入力され、
その出力側に配置された第１〜第４の出力ポート２０６
₁〜２０６₄のいずれに出力するかのルーチングについて
の制御が行なわれるようになっている。

【０００４】このＡＴＭスイッチ２０１には、第１〜第
４の入力バッファ部２０２₁〜２０２₄に入力されたセル
が第１〜第４の出力ポート２０６₁〜２０６₄のいずれか
で出力衝突を行わないようにするために衝突検出部２０
７が設けられている。衝突検出部２０７は、第１〜第４
の入力バッファ部２０２₁〜２０２₄に入力されている各
セルのルーチング情報の送出を受け、同一出力ポートで
の衝突の発生の有無を判別する。そして、判別結果を再
び第１〜第４の入力バッファ部２０２₁〜２０２₄に返送
するようにしている。

【０００５】第１〜第４の入力バッファ部２０２₁〜２
０２₄ではこの判別結果を使用して、第１〜第４の出力
ポート２０６₁〜２０６₄で衝突のないセルの場合にはこ
れらをそのまま自己ルーチング部２０５に送出するよう
にしている。これに反して、衝突が発生するセルについ
ては、それら同士で第１〜第４の出力ポート２０６₁〜
２０６₄に対する出力の勝ち負けを決定する。そして、
勝ったセルはそのまま遅滞なく自己ルーチング部２０５
に送出され、負けたセルは第１〜第４の入力バッファ部
２０２₁〜２０２₄に一時的に蓄積される。これら負けた
セルについては出力に際してこれらのルーチング情報を
再び衝突検出部２０７に送って第１〜第４の出力ポート
２０６₁〜２０６₄のいずれかで出力衝突が発生しないか
どうかを事前に判別することになる。

【０００６】図２２は、従来の入力バッファ型のＡＴＭ
スイッチの他の構成を表わしたものである。このＡＴＭ
スイッチ２１０も、４×４のＡＴＭスイッチの構成を表
わしたものである。この従来のＡＴＭスイッチ２１０
も、第１〜第４の入力バッファ部２１２₁〜２１２₄を備
えており、これらにはそれぞれセルを入力するための第
１〜第４の入力ポート２１３₁〜２１３₄が対応して配置
されている。第１〜第４の入力バッファ部２１２₁〜２
１２₄から出力されるセルのルーチング情報は、自己ル
ーチング部２１５との間に配置された衝突検出部２１７
に送出され、第１〜第４の出力ポート２１６₁〜２１６₄
のいずれかで出力衝突が発生しないかどうかの判別が行
なわれる。

【０００７】第１〜第４の出力ポート２１６₁〜２１６₄
で衝突のないセルは第１〜第４の入力バッファ部２１２
₁〜２１２₄から出力され、衝突検出部２１７を経由して
自己ルーチング部２１５に送られて、これらのルーチン
グ情報に基づいて第１〜第４の入力ポート２１３₁〜２
１３₄への振り分けが行なわれる。これに反して、衝突
が発生するセルについては、それら同士で第１〜第４の
出力ポート２１６₁〜２１６₄に対する出力の勝ち負けを
決定する。そして、勝ったセルはそのまま遅滞なく衝突
検出部２１７を経由して自己ルーチング部２１５に送出
される。負けたセルは第１〜第４の入力バッファ部２１
２₁〜２１２₄に一時的に蓄積される。これら負けたセル
については出力に際してこれらのルーチング情報を再び
衝突検出部２１７に送って第１〜第４の出力ポート２１
６₁〜２１６₄のいずれかで出力衝突が発生しないかどう
かを事前に判別することになる。

【０００８】このようにＡＴＭスイッチでは、何らの調
整も行わない場合には、並設された異なる入力ポートか
ら同時に同一の出力ポートにセルが送出されるような事
態が発生しうる。そこで、図２１および図２２に示した
ように、ＡＴＭスイッチには衝突検出部が配置されてお
り、事前に衝突の発生が検出される。そして、衝突する
セルについては、このうちの１つが出力ポートに出力さ
れ、残りのセルはバッファに一時的に待機した後に繰り
返し衝突の判別が行われて、衝突ありとされたセルが１
つずつ該当する出力ポートから出力されることになる。
これら競合したセルをどのような順序で該当する出力ポ
ートから出力するかについては、セルの競合の調停の問
題として論じられている。

【０００９】ところで、このようにセルの競合が生じる
と、セルからフレームを組み立てる際に途中のセルが無
くなってしまったり（セル損失）、誤った順序でセルの
組立が行われる可能性が生じる。そこで、ＡＴＭスイッ
チにおける各種バッファの構成方法は、セル損失の発生
を一定の割合以下に抑えるために必要とされるバッファ
の量とスイッチの動作に大きな影響を与えることにな
る。

【００１０】一般に、各種バッファの構成方法について
次のようなことが知られている。 （１）必要とするバッファ量についてみると、共通バッ
ファ型は、ＡＴＭスイッチ全体で必要とされる量が各種
バッファの構成方法の中で最も少ない。クロスポイント
バッファ型の場合が最も多くのバッファ量を必要とす
る。 （２）ＡＴＭスイッチ内部のバッファへの読み書きのた
めのアクセス頻度については、共通バッファ型が最も少
なく、次いで出力バッファ型の順序となる。入力バッフ
ァ型およびクロスポイントバッファ型が読み書きのため
のアクセス頻度の最も少ないものとなる。 （３）ＡＴＭスイッチの構成や動作の複雑さについて
は、それぞれのバッファ構成の種類が異なればそれらに
対する要求や問題も異なってくる。したがって、それぞ
れのバッファの構成方法によるＡＴＭスイッチの特性の
違いだけで優劣を競うことはできない。むしろ、ＡＴＭ
スイッチ全体に要求される所要バッファ量の大小や、バ
ッファへのアクセス頻度の大小等が実用上の問題となる
ことが多い。ここで、バッファへのアクセス頻度の大小
は、バッファを構成する記憶素子のアクセス速度等に影
響を与える。

【００１１】ところで、インターネットの発達と共に、
コネクションレス型通信が増大している。ここでコネク
ションレス型通信とはデータの送信に先立って相手先の
呼び出しや仮想回線の確立を行わない通信方式をいう。
個別のデータグラムを送信した際の順序を保たなくてよ
く、転送途中でフレームの廃棄も発生しうる。このよう
なコネクション型通信の増大は、従来からセル損失の発
生を抑えるためのに必要とされたバッファ量の算出効果
としての統計多重効果（可変レートの複数チャネルの情
報を多重すると、トラフィックの確率的な振る舞いを考
慮し、全チャネルあたりの必要なレートを低減できると
する効果）を薄れさせている。このため、バッファ量の
予測をますます困難なものにしている。

【００１２】また、ＡＴＭスイッチの高速化や処理の容
易さが進展した結果として、スイッチの内部でセル長を
変換したり、伝送フレームとの位相合わせの目的や品質
管理のためのモニタリングセルの挿入等が行われてい
る。この結果として、予定外のセルを読み出したり予定
外のセルの待ち合わせが発生することが珍しくなくなっ
ている。このようなことから、従来のバッファ構成モデ
ルを単純に使用して、ＡＴＭスイッチに必要とされるバ
ッファ量を求めることは非常に困難になってきている。

【００１３】そこで、現在商用化されている多くのＡＴ
Ｍスイッチでは、スイッチのバッファ構成方法から必要
とされる本来の量のバッファの他に、ＡＴＭスイッチの
前に大容量のバッファを設置することが行われている。
この大容量のバッファは、予想外のバーストトラヒック
の入力にも耐えられるようにするためである。

【００１４】

【発明が解決しようとする課題】

【００１５】ところが、このようにＡＴＭスイッチの前
に大容量のバッファを設置してセル損失特性を改善する
ことは、ハードウェアの無駄となりバッファ構成の簡易
化に反することになる。

【００１６】そこで、ＦＩＦＯメモリ（先入れ先出しメ
モリ）と選択回路を使用することで、バッファ構成の簡
易化に対処すると共に、スイッチ全体および入力バッフ
ァ部の高速化への適応が図られている。

【００１７】たとえばたとえば特開平５−２９２１１６
号公報に開示された技術では、ＦＩＦＯメモリの先頭か
ら複数のセルの宛先を読み取る読取手段と、ＦＩＦＯメ
モリからのセルの送出を管理する予約管理テーブルを設
けている。そして、予約によって指定されたセル送出時
刻にＦＩＦＯメモリからセルの送出を行うようにしてい
る。

【００１８】図２３はこの特開平５−２９２１１６号公
報に開示された技術の概要を示したものである。入力Ｆ
ＩＦＯメモリ２２１は先頭セルと次のセルの一方または
双方を読み出すためのタップが付いたメモリである。こ
れら２つののタップには、入力制御回路２２２と２つの
セルの一方を選択するためのセレクタ２２３が接続され
ている。セレクタ２２３から出力されるセルは、セル送
出メモリ２２４に入力され、ここからセルが読み出され
て送出されるようになっている。入力制御回路２２２
は、セル送出テーブル２２５と共通制御部２２６の双方
に接続されている。この図に示したＡＴＭスイッチで
は、入力制御回路２２２から共通制御部２２６へのセル
送出要求信号の伝播時間や、共通制御部２２６から入力
制御回路２２２への応答信号の伝播時間および入力制御
回路２２２から入力ＦＩＦＯメモリ２２１への制御信号
の伝播時間は、２つのセルを処理するので半減すること
になる。

【００１９】また、特開平６−１０５３５１号公報に開
示された技術では、セルのランダムな読み出しが可能な
第１のセルバッファと、ＦＩＦＯメモリからなる第２の
セルバッファを配置している。そして、第２のセルバッ
ファに輻輳状態が通知されると、第１のセルバッファに
蓄積されているセルの中で輻輳状態でないセルが出力さ
れるようになっている。この技術によれば、ＨＯＬ（He
ad Of Line）効果によるスループットの低下を避ける
ことができる。ここでＨＯＬ効果によるスループットの
低下とは、セル衝突を回避するためにセルの出力をＦＩ
ＦＯメモリ内で停止すると、そのＦＩＦＯメモリの該当
するセル以降のセルが同様に待機状態となってしまうこ
とをいう。

【００２０】しかしながら、従来のＡＴＭスイッチでは
ＨＯＬ効果によるスループットの低下を防止しても、入
力バッファ内に衝突回避のために蓄積されたセルに対し
てその都度、衝突が発生するかどうかの判別（シャッフ
ル動作）を行わなければならないという問題があった。
すなわち、従来の入力バッファ型のＡＴＭスイッチで
は、いくらシャッフル動作によってセルの送出順序を入
れ替えてみても、一度に１つのセルしか入力バッファか
ら読み出すことができない。したがって、入力バッファ
内に複数の蓄積セルが存在する場合には、競合関係が消
えて該当する複数の出力ポートが空いていても、送出で
きずに待機状態とされるセルが存在し、他のバッファ形
式のＡＴＭスイッチと比較してスループットが低下し、
輻輳が長引いてしまうという問題があった。

【００２１】そこで本発明の目的は、バッファ構成を簡
略化し、しかもスループットが向上する入力バッファ型
のＡＴＭスイッチを提供することにある。

【００２２】

【課題を解決するための手段】請求項１記載の発明で
は、（イ）ＡＴＭセルを時間的に並列して入力する複数
の入力ポートと、（ロ）これら入力ポートに１つずつ対
応して配置され対応する入力ポートから入力されるセル
を複数蓄積して入力された順番に１つずつ読み出す主バ
ッファ手段と、（ハ）入力ポートに１つずつ対応して配
置され、前段のバッファから送り出されたセルを入力し
て保持する第１のセル保持手段と、この第１の保持手段
とは別にセルを保持する第２のセル保持手段と、これら
のセル保持手段の出力側に配置されこれらから同時に出
力されるセルの１つを選択する選択手段を備え、選択手
段の選択したセルをセル送出タイミングで送り出すと共
に送り出した同一のセルを第２のセル保持手段に入力す
るようにその１単位が構成され、かつそれぞれの単位が
直列接続されており、最先の単位に属する第１のセル保
持手段に主バッファの出力したセルが入力されるように
なったザブバッファ手段と、（ニ）このザブバッファ手
段の各単位の選択手段から出力されるセルを前記した複
数の入力ポート分だけ並列して入力してこれらの出力ポ
ート側でのセルの衝突の有無を検出する衝突検出手段
と、（ホ）この衝突検出手段の検出結果をそれぞれの入
力ポートの各選択手段ごとに入力して出力ポートのいず
れでセルの衝突が生じるか否かと衝突が生じたときの今
回出力するセルとしての勝ちセルを判定する判定手段
と、（へ）この判定手段の判定結果を入力してザブバッ
ファ手段のそれぞれの選択手段を制御しザブバッファ手
段から衝突の生じないセルあるいは衝突の生じる場合に
勝ちセルとして判定されたセルを出力させるとともにこ
れら出力するセルがない場合にはそのタイミングで空き
セルを出力させるバッファ手段制御手段と、（ト）この
バッファ手段制御手段の制御によって入力ポートに１つ
ずつ対応したザブバッファ手段から出力されるセルの中
から空きセルを除去し、各セルごとに対応する出力ポー
トに送出するルーチング手段とをＡＴＭスイッチに具備
させる。

【００２３】すなわち請求項１記載の発明では、入力ポ
ートごとに入力されるセルを主バッファ手段に一旦蓄積
し、サブバッファ手段では直列に接続された複数単位の
サブバッファの最初のサブバッファの第１のセル保持手
段にこれを入力する。最初のサブバッファには第１のセ
ル保持手段の他に第２のセル保持手段も設けられてお
り、これらの出力側にはこれらから出力されるセルを選
択する選択手段が配置されている。選択手段の選択した
セルはセル送出タイミングで次段の回路部分に送り出さ
れると共に送り出した同一のセルは第２のセル保持手段
に入力される。このような１単位のサブバッファが複数
段直列に接続されてサブバッファ手段が構成されてい
る。このサブバッファ手段のそれぞれの選択手段の出力
が衝突検出手段に入力されることで、衝突するセルが１
段ずつ遅延されて出力可能な状態となる。衝突検出手段
は、出力ポート側でのセルの衝突を検出し、判定手段は
衝突が生じるときにはそのセルが勝ちセルとなるかどう
かを判定する。バッファ手段制御手段はこの判定結果を
使用して主バッファ手段およびサブバッファ手段を制御
してサブバッファ手段から衝突するセルが空きセルに変
換されたセルを出力させる。ルーチング手段はこれらの
セルをそれぞれの出力ポートに割り振ることになる。

【００２４】請求項２記載の発明では、（イ）ＡＴＭセ
ルを時間的に並列して入力する複数の入力ポートと、
（ロ）これら入力ポートに１つずつ対応して配置され対
応する入力ポートから入力されるセルを複数蓄積して入
力された順番に１つずつ読み出す主バッファ手段と、
（ハ）前段のバッファから送り出されたセルを１セル分
蓄積する第１のバッファと、同じくセルを１セル分蓄積
する第２のバッファと、これら第１および第２のバッフ
ァの一方を選択してセルを出力させる選択回路とを備
え、選択回路から出力されるセルを次段に出力すると共
に第２のバッファに送り込むように構成され、対応する
入力ポートごとに互いに直列接続され、最前段の手段内
の第１のバッファには主バッファの出力したセルが入力
されるようになった複数のザブバッファ手段と、（ニ）
各ザブバッファ手段の選択回路から出力されるセルを前
記した複数の入力ポート分だけ並列して入力してこれら
の出力ポート側でのセルの衝突の有無を検出する衝突検
出手段と、（ホ）この衝突検出手段の検出結果をそれぞ
れの入力ポートに対応した各サブバッファ手段の選択回
路ごとに入力して出力ポートのいずれでセルの衝突が生
じるか否かと衝突が生じたときの今回出力するセルとし
ての勝ちセルを判定する判定手段と、（へ）この判定手
段の判定結果を入力して前記した複数のザブバッファ手
段のそれぞれの選択回路を制御し前記複数のザブバッフ
ァ手段ごとに衝突の生じないセルあるいは衝突の生じる
場合に勝ちセルとして判定されたセルを出力させるとと
もにこれら出力するセルがないザブバッファ手段からは
そのタイミングで空きセルを出力させるバッファ手段制
御手段と、（ト）このバッファ手段制御手段の制御によ
って前記した複数のザブバッファ手段から出力されるセ
ルを対応する出力ポートに送出するルーチング手段とを
ＡＴＭスイッチに具備させる。

【００２５】すなわち、請求項２記載の発明では、入力
ポートごとに入力されるセルを主バッファ手段に一旦蓄
積する。複数のサブバッファ手段は直列に接続されてお
り、最前段のサブバッファ手段内の第１のバッファには
主バッファの出力したセルが入力されるようになってい
る。これらのサブバッファ手段はセルを１セル分蓄積す
る第１のバッファと、同じくセルを１セル分蓄積する第
２のバッファとこれらの出力側に配置された選択回路を
備えて構成されている。衝突検出手段は、各選択回路か
ら出力されるセルが出力ポートで衝突するかどうかを検
出し、判定手段は衝突が生じるときにはそのセルが勝ち
セルとなるかどうかを判定する。バッファ手段制御手段
はこの判定結果を使用して主バッファ手段および各サブ
バッファ手段を制御してサブバッファ手段から衝突する
セルが空きセルに変換されたセルを出力させる。ルーチ
ング手段はこれらのセルをそれぞれの出力ポートに割り
振ることになる。

【００２６】請求項３記載の発明では、（イ）ＡＴＭセ
ルを時間的に並列して入力する複数の入力ポートと、
（ロ）これら入力ポートに１つずつ対応して配置され対
応する入力ポートから入力されるセルを複数蓄積して入
力された順番に１つずつ読み出すＦＩＦＯメモリから構
成された主バッファ手段と、（ハ）この主バッファ手段
から送り出されたセルを１セル分蓄積する第１のバッフ
ァと、同じくセルを１セル分蓄積する第２のバッファ
と、これら第１および第２のバッファの一方を選択して
セルを出力させる選択回路とを備え、選択回路から出力
されるセルを次段に出力すると共に第２のバッファに送
り込むように構成され、対応する入力ポートごとに配置
された第１のザブバッファ手段と、（ニ）この第１のサ
ブバッファ手段から送り出されたセルを１セル分蓄積す
る第１のバッファと、空きセルを発生させる空きセル生
成回路と、この空きセル生成回路と第１のバッファの一
方を選択してセルを出力させる第１の選択回路と、セル
を１セル分蓄積する第２のバッファと、この第２のバッ
ファと第１の選択回路の出力のバッファの一方を選択し
てセルを出力させる第２の選択回路とを備え、第２の選
択回路から出力されるセルを次段に出力すると共に第２
のバッファに送り込むように構成され、第１のザブバッ
ファ手段と共に対応する入力ポートごとに互いに直列接
続された第２段あるいはこれ以降の複数段のザブバッフ
ァ手段と、（ホ）第１のザブバッファ手段の選択回路お
よび第２段あるいはこれ以降の複数段のザブバッファ手
段の第２の選択回路から出力されるセルを前記した複数
の入力ポート分だけ並列して入力してこれらの出力ポー
ト側でのセルの衝突の有無を検出する衝突検出手段と、
（へ）この衝突検出手段の検出結果をそれぞれの入力ポ
ートに対応した各サブバッファ手段の第１または第２の
選択回路ごとに入力して出力ポートのいずれでセルの衝
突が生じるか否かと衝突が生じたときの今回出力するセ
ルとしての勝ちセルを判定する判定手段と、（ト）この
判定手段の判定結果を入力して主バッファ手段および第
１のザブバッファ手段以降のザブバッファ手段のそれぞ
れの選択回路を制御し前記した複数のザブバッファ手段
ごとに衝突の生じないセルあるいは衝突の生じる場合に
勝ちセルとして判定されたセルを出力させるとともにこ
れら出力するセルがないザブバッファ手段からはそのタ
イミングで空きセルを出力させるバッファ手段制御手段
と、（チ）このバッファ手段制御手段の制御によって前
記した複数のザブバッファ手段から出力されるセルを対
応する出力ポートに送出するルーチング手段とをＡＴＭ
スイッチに具備させる。

【００２７】すなわち請求項３記載の発明では、主バッ
ファ手段がＦＩＦＯメモリ（先入れ先だしメモリ）から
構成され、入力されたセルの順番で後段の第１のザブバ
ッファ手段にセルが送出されるようになっている。第１
のザブバッファ手段から出力されるセルはそれ自体が衝
突検出手段に入力される他、第２段のザブバッファ手段
に入力される。ＡＴＭスイッチによってはサブバッファ
手段として第１および第２段のザブバッファ手段だけが
用意されていてもいてもよいし、第３のサブバッファ手
段等のこれ以降のサブバッファ手段が設けられていても
よい。第２段のザブバッファ手段以降に第３段等のサブ
バッファ手段が多く設けられるほど、後に説明するシャ
ッフルの深さが深くなり、同時に衝突するセルの数が多
い場合に対応することになる。なお、請求項３記載の発
明における第２段のザブバッファ手段には空きセル生成
回路が備えられており、空きセルを出力することができ
る。これに関連してこの空きセル生成回路の出力と第１
のバッファの一方を選択してセルを出力させる第１の選
択回路と、第２のバッファと第１の選択回路の出力のバ
ッファの一方を選択してセルを出力させる第２の選択回
路の２つの選択回路が設けられている。バッファ手段制
御手段はこの判定結果を使用して主バッファ手段および
各サブバッファ手段を制御してサブバッファ手段から衝
突するセルが空きセルに変換されたセルを出力させる。
ルーチング手段はこれらのセルをそれぞれの出力ポート
に割り振ることになる。

【００２８】請求項４記載の発明では、請求項１〜請求
項３記載のＡＴＭスイッチにおいて、バッファ手段制御
手段は、判定手段のそれぞれの判定結果に対する主バッ
ファ手段およびザブバッファ手段の状態遷移を真理値表
で表わしたものを基にした論理素子で構成されているこ
とを特徴としている。論理素子の使用で処理の高速化を
図ることができる。

【００２９】請求項５記載の発明では、請求項１〜請求
項３記載のＡＴＭスイッチにおいて、ルーチング手段の
手前には、判定手段を経て送られてきたそれぞれのセル
を入力して、空きセルでない有効セル数の最大値が、出
力ポート数以下になるように設定するためのソータ手段
が配置されていることを特徴としている。各サブバッフ
ァ手段から複数通りのセルが出力され、これらのセルの
うちの有効なセルを空きセルに変換することにしている
ので、ルーチング手段でルーチングを行う前に余分な空
きセルを除去することにしている。

【００３０】請求項６記載の発明では、請求項２記載の
ＡＴＭスイッチにおいて、第１のバッファをクリアする
ことによって空きセルを発生させこれを出力することを
特徴としている。これにより、空きセル生成回路が不要
になる。

【００３１】

【発明の実施の形態】

【００３２】

【実施例】以下実施例につき本発明を詳細に説明する。

【００３３】図１は本発明の一実施例における４×４の
ＡＴＭスイッチの構成を表わしたものである。この例の
ＡＴＭスイッチは、シャッフルの深さが２列の場合を示
している。実施例のＡＴＭスイッチは第１〜第４の入力
バッファ部１１₁〜１１₄を備えており、これらにはそれ
ぞれセルを入力するための第１〜第４の入力ポート１２
₁〜１２₄が対応して配置されている。第１〜第４の入力
バッファ部１１₁〜１１₄からはそれぞれ２種類のセル出
力１３₁〜１３₄、１４₁〜１４₄が出力され、衝突判定部
１５に入力されるようになっている。衝突判定部１５
は、セル同士の出力衝突を検出して、衝突がある場合に
は１つのセルを衝突の勝ちと判定する。また、残りのセ
ルを衝突の負けと判定する。これらの判定結果は、それ
ぞれのセルの図示しないスイッチング情報部に衝突情報
として書き込むようになっている。衝突判定部１５のそ
れぞれの対応する出力１６₁〜１６₄、１７₁〜１７₄は、
第１〜第４の入力バッファ部１１₁〜１１₄にそれぞれ対
応した第１〜第４のセル変換部１９₁〜１９₄に入力され
るようになっている。

【００３４】第１〜第４のセル変換部１９₁〜１９₄は、
入力されたこれらの出力１６₁〜１６₄、１７₁〜１７₄に
おける衝突情報を見て、これらの衝突情報２１₁〜２１₄
および２２₁〜２２₄を第１〜第４の入力バッファ部１１
₁〜１１₄のバッファ制御部に返信すると共に、衝突の勝
ちと判定した勝ち情報を有するセル２３₁〜２３₄、２４
₁〜２４₄を次段のソータ部２５に供給するようになって
いる。

【００３５】なお、この図では第１〜第４の入力バッフ
ァ部１１₁〜１１₄および第１〜第４のセル変換部１９₁
〜１９₄は共に同一の構成となっているが、これらのう
ちの第１の入力バッファ部１１₁と第１のセル変換部１
９₁の回路構成を代表的に具体的に示している。すなわ
ち、第１の入力バッファ部１１₁は第１の入力ポート１
２₁に接続された主バッファ部３１₁と、この主バッファ
部３１₁から出力されるセルを第１および第２のサブバ
ッファ部３２ａ₁、３２ｂ₁に順次伝達し、このうちの第
２のサブバッファ部３２ｂ₁から出力されるセルがセル
出力１３₁となり、第１のサブバッファ部３２ａ₁から出
力されるセルがセル出力１４₁となるようになってい
る。第１のセル変換部１９₁から第１の入力バッファ部
１１₁に送られてくる衝突情報２１₁および２２₁は、第
１の入力バッファ部１１₁内のバッファ制御部３４₁に入
力されて、各部の制御が行われるようになっている。ま
た、第１のセル変換部１９₁内には第１の変換回路３６₁
と第２の変換回路３６₂が配置されている。第１の変換
回路３６₁は、衝突判定部１５の出力１７₁を入力して衝
突情報２２₁と、衝突の勝ちと判定した勝ち情報を有す
るセル２４₁を出力し、第２の変換回路３６₂は、衝突判
定部１５の出力１６₁を入力して衝突情報２１₁と、衝突
の勝ちと判定した勝ち情報を有するセル２３₁を出力す
るようになっている。第２〜第４の入力バッファ部１１
₂〜１１₄および第２〜第４のセル変換部１９₂〜１９₄の
動作はこれら第１の入力バッファ部１１₁および第１の
セル変換部１９₁の回路動作と同一なので、それらの説
明は省略する。

【００３６】第１〜第４のセル変換部１９₁〜１９₄の次
段に配置されたソータ部２１は、第１〜第４のセル変換
部１９₁〜１９₄からセル２３₁〜２３₄および２４₁〜２
４₄を入力して、これらをソートした結果としてのセル
２７₁〜２７₄を最終段の自己ルーチング部２８に対して
出力する。ソータ部２５に入力するセル２３₁〜２３₄お
よび２４₁〜２４₄は勝ちセルであり、衝突で負けたセル
は空きセルに変換されている。したがって、空きセルで
ない有効なセル数の最大値は第１〜第４の出力ポート２
９₁〜２９₄の数に自動的に等しい値となっている。

【００３７】自己ルーチング部２８は、バンヤン網やオ
メガ網、あるいはクロスバー型スイッチ等の既存のノン
ブロッキング網あるいはノンブロッキングスイッチで構
成されている。本実施例のＡＴＭスイッチの場合には、
自己ルーチング部２８へ入力される各セルは出力衝突が
存在しないことが保証されている。したがって、衝突の
事態を配慮することなくルーチングに専念することがで
きる。

【００３８】なお、この図１で第１〜第４の入力バッフ
ァ部１１₁〜１１₄は入力バッファ部を構成し、衝突判定
部１５、第１〜第４のセル変換部１９₁〜１９₄およびソ
ータ部２５は、衝突検出・シャッフル部を構成し、残り
の自己ルーチング部２８が自己ルーチング部を構成して
いる。

【００３９】このような本実施例のＡＴＭスイッチの構
成を更に具体的に説明する。

【００４０】図２は図１に示した第１の入力バッファ部
の構成を具体的に表わしたものである。第１の入力バッ
ファ部１１₁の主バッファ部３１₁は、主バッファ４１を
収容している。主バッファ４１は、入力バッファ型ＡＴ
Ｍスイッチにおける既存の入力バッファとしての機能を
有する大容量のＦＩＦＯ（先入れ先出しメモリ）で構成
されている。そして、バッファ制御部３４₁が主バッフ
ァ部３１₁に対して主バッファ読出一時停止信号４２を
送出しない状態では、セル送出タイミングに従って、１
つずつ読み出し、これらのセル４３を第１のサブバッフ
ァ部３２ａ₁に出力する。また、主バッファ４１は第１
の入力ポート１２₁から入力されるセルを到着順に格納
していく。

【００４１】第１のサブバッファ部３２ａ₁は、容量が
それぞれ１セル分のＰバッファ４４とＮバッファ４５
と、これらの出力側に配置された選択回路４６とによっ
て構成されている。主バッファ部３１₁から出力される
セル４３はＮバッファ４５に入力されるようになってい
る。そして、選択回路４６から出力される出力セル１４
₁は第２のサブバッファ部３２ｂ₁に出力される一方でＰ
バッファ４４に入力されるようになっている。選択回路
４６はセル送出タイミングでＰバッファ４４とＮバッフ
ァ４５のいずれかに格納されているセルを選択して出力
セル１４₁として出力する。いずれのバッファ４５、４
６を選択するかはバッファ制御部３４₁から送られてく
る主バッファ読出一時停止信号４２によって定まる。な
お、出力セル１４₁は図１に示した衝突判定部１５にも
入力されるようになっている。

【００４２】第２のサブバッファ部３２ｂ₁も第１のサ
ブバッファ部３２ａ₁と同様に容量がそれぞれ１セル分
のＰバッファ４８ｂとＮバッファ４９ｂを備えている。
第１のサブバッファ部３２ａ₁から出力される出力セル
１４₁はＮバッファ４９ｂに入力されるようになってい
る。第２のサブバッファ部３２ｂ₁には空きセル生成回
路５１ｂが配置されており、その出力とＮバッファ４９
ｂの出力が第１の選択回路５２ｂに入力され、この第１
の選択回路５２ｂの出力とＰバッファ４８ｂの出力が第
２の選択回路５３ｂに入力されるようになっている。こ
れら第１および第２の選択回路５２ｂ、５３ｂは、それ
ぞれバッファ制御部３４₁から出力される選択制御信号
５４ｂ₁および衝突情報２１₁によって制御される。第２
の選択回路５３ｂから出力されるセル出力１３₁は、Ｐ
バッファ４８ｂに供給される他、図１に示した衝突検出
・シャッフル部の衝突判定部１５に入力されるようにな
っている。

【００４３】バッファ制御部３４₁は、選択制御信号５
４ｂ₁を出力するオア回路５６と、主バッファ読出一時
停止信号４２を出力するアンド回路５７から構成されて
いる。図１に示した第１のセル変換部１９₁から出力さ
れる衝突情報２１₁はそのまま第２の選択回路５３ｂに
供給される他、オア回路５６およびアンド回路５７の一
方の入力となるようになっている。第１のセル変換部１
９₁から出力される衝突情報２２₁の方は、これらオア回
路５６およびアンド回路５７の他方の入力となるように
なっている。

【００４４】このような構成のバッファ制御部３４₁で
は、衝突情報２１₁および２２₁に従って主バッファ部３
１₁の読み出しの動作を一時的に停止させたり、第１の
サブバッファ部３２ａ₁および第２のサブバッファ部３
２ｂ₁の出力を制御する。これについては後に詳しく説
明する。

【００４５】図３は、図１に示した衝突判定部の具体的
な構成を表わしたものである。衝突判定部１５は、同一
バッファ内での衝突の検出と入力ポートの復元を行う同
一ポート内衝突検出回路６１と、その後段に配置され、
すべての入力バッファ間で同一出力の検出と入力ポート
の復元を行う同一宛先セル衝突検出回路６２とによって
構成されている。

【００４６】本実施例の衝突判定部１５はバーチャ型の
衝突検出回路を採用している。そして同一宛先セル衝突
検出回路６２の出力側に現われる出力１６₁〜１６₄、１
７₁〜１７₄は、図１に示す第１〜第４のセル変換部１９
₁〜１９₄に入力されるようになっている。衝突判定部１
５は、次に詳しく説明する２入力２出力の単位ソーティ
ング回路６３と、２入力２出力の単位スイッチ回路６４
によって組み合わされている。これらの単位ソーティン
グ回路６３および単位スイッチ回路６４の動作について
は後に詳しく説明する。なお、これらの回路の基本的な
動作については特開平８−１７２４３６号公報にも説明
されている。

【００４７】衝突判定部１５の次の段に存在する第１〜
第４のセル変換部１９₁〜１９₄（図１参照）は、図１で
第１のセル変換部１９₁について例示的に示したように
第１の変換回路３６₁および第２の変換回路３６₂によっ
て構成されている。このうちの第１の変換回路３６
₁は、第１の入力バッファ部１１₁のセル出力１４₁を衝
突判定部１５に入力することによってこれから得られた
出力１７₁をチェックしている。また、第２の変換回路
３６₂は、第１の入力バッファ部１１₁のセル出力１３₁
を衝突判定部１５に入力することによってこれから得ら
れた出力１６₁をチェックしている。第１の変換回路３
６₁から出力される衝突情報２１₁および第２の変換回路
３６₂から出力される衝突情報２２₁はそれぞれ第１の入
力バッファ部１１₁のバッファ制御部３４₁に入力される
ことはすでに説明した。また、衝突の勝ちと判定した勝
ち情報を有するセルはそのまま２３₁〜２３₄、２４₁〜
２４₄として次段のソータ部２５に供給されるが、負け
と判定されたセルの場合には空きセルに変換した後にソ
ータ部２５に供給されることになる。第１〜第４のセル
変換部１９₁〜１９₄の動作については後に詳しく説明す
る。

【００４８】図４は、図１に示したソータ部の具体的な
構成を表わしたものである。ソータ部２５は、既存のバ
ーチャ型ソータ回路を採用している。これが一般のバー
チャ型ソータ回路と異なる点は、セル２３₁〜２３₄およ
び２４₁〜２４₄を入力してセル２７₁〜２７₄を出力する
８入力４出力の非対称型となっている点である。これ
は、すでに説明したように、衝突判定部１５では出力衝
突の有無が検出され、第１〜第４のセル変換部１９₁〜
１９₄によって勝ちセルのみが出力され、衝突で負けた
セルは空きセルに変換される。従って、空きセルでない
有効セル数の最大値が、常に出力ポート数以下になるよ
うに自動設定するためである。

【００４９】図１に示した最終段の自己ルーチング部２
８は、その具体的な回路構成を示していないが、すでに
説明したように既存のバンヤン網やオメガ網、あるいは
クロスバー型スイッチ等の既存のノンブロッキング網あ
るいはノンブロッキングスイッチで構成されることにな
る。

【００５０】図５は、本実施例のＡＴＭスイッチに入力
されるセルについてのフォーマットを示したものであ
る。ＡＴＭスイッチ入力セル７１は、ペイロード部７１
Ａおよびヘッダ部７１Ｂからなる標準のＡＴＭセルにス
イッチング情報部７１Ｃというヘッダ部分を更に付加し
た構成となっている。スイッチング情報部７１Ｃは、先
頭から順に有効表示部７１Ｃ₁、衝突情報部７１Ｃ₂、バ
ッファ識別子７１Ｃ₃およびルーティング情報部７１Ｃ₄
に分かれている。

【００５１】有効表示部７１Ｃ₁は、全体が有効セルの
場合に信号“１”を示し、無効な空きセルの場合には信
号“０”を示すようになっている。衝突情報部７１Ｃ₂
は、同一出力ポートへの衝突がないか、あるいは衝突が
あっても勝った場合に信号“０”を示し、同一出力ポー
トへの衝突で負けた場合には信号“１”を表示するよう
になっている。

【００５２】バッファ識別子７１Ｃ₃は、第１〜第４の
入力バッファ部１１₁〜１１₄に共通に、セルの送出元で
ある第１および第２のサブバッファ部３２ａ₁、３２ｂ₁
を表わす識別子である。本実施例の場合には、第１のサ
ブバッファ部３２ａ₁を必要に応じて代表的に説明する
と、これから出力されるセルについては信号“１”が設
定され、第２のサブバッファ部３２ｂ₁から出力される
セルには信号“２”が設定されることになる。

【００５３】ルーティング情報部７１Ｃ₄は、スイッチ
の出力ポートを表わす情報である。本実施例の場合、図
１に示した第１の出力ポート２９₁行きのセルの場合に
は信号“０”が設定され、第２の出力ポート２９₂行き
のセルの場合には信号“１”が設定される。一般には、
第Ｍの出力ポート２９_M行きのセルの場合には信号“Ｍ
−１”が設定されることになる。

【００５４】次に入力バッファ部の構成とバッファ制御
について詳細に説明する。図２に示す第１および第２の
サブバッファ部３２ａ₁、３２ｂ₁から出力される２種類
のセル出力１３₁、１４₁は、図１に示した第１のセル変
換部１９₁内の第１の変換回路３６₁と第２の変換回路３
６₂から帰還される２種類の衝突情報２２₁および２１₁
によって、バッファ制御部３４₁で制御されることにな
る。図２に示したように、第１および第２のサブバッフ
ァ部３２ａ₁、３２ｂ₁は、それぞれ１セル分の容量のＰ
バッファ４４、４８ｂと、Ｎバッファ４５、４９ｂと、
これらの出力側に配置された選択回路４６、５３ｂを内
蔵している。また、第２の変換回路３６ ₁の場合には、
追加された構成の選択回路５２ｂも備えている。

【００５５】図６は、第１および第２のサブバッファ部
における、次回のセル送出タイミングで読み出して出力
すべき内部バッファの種類と、同時に各サブバッファ内
のＮバッファへのデータの読込動作の様子を表わしたも
のである。ここで内部バッファとは、Ｎバッファ、Ｐバ
ッファおよび空きセルをいう。この図では、読出バッフ
ァ（Ｎバッファ、Ｐバッファおよび空きセル）の種類
と、同時に行なわれる、第１および第２のサブバッファ
３２ａ₁、３２ｂ₁内のＮバッファへのデータの読込動作
（前段のバッファの出力と一時停止）を組み合わせて４
つの状態に対応させたものである。

【００５６】まず、「初期状態」は、スイッチの動作開
始時点、または出力セル間に衝突のない状態での動作を
表わしている。この状態では第１のサブバッファ３２ａ
₁のＮバッファから有効セルが出力され、第２のサブバ
ッファ３２ｂ₁からは空きセルが出力される。同時に第
１および第２のサブバッファ３２ａ₁、３２ｂ₁の各々の
Ｎバッファ４５、４９ｂには、各々のサブバッファ３２
ａ₁、３２ｂ₁の前段の主バッファ部３１₁と第１のサブ
バッファ３２ａ₁の出力が読み込まれる様子を示してい
る。

【００５７】「第１の状態」は、第１のサブバッファ３
２ａ₁の出力セルが衝突で負け、第２のサブバッファ３
２ｂ₁からは有効セルがないか、または出力セル間に衝
突がないか、あるいは衝突があった場合にこれに勝った
状態の動作を表わしている。衝突で負けた第１のサブバ
ッファ３２ａ₁の出力セルは出力と同時に第２のサブバ
ッファ３２ｂ₁のＮバッファ４９ｂにも書き込まれてお
り、同時に第１のサブバッファ３２ａ₁のＮバッファ４
５には前段の主バッファ部３１₁からの新たなセル４３
が書き込まれている。従って、次回のセル出力では、第
１および第２のサブバッファ部３２ａ₁、３２ｂ₁の各々
のＮバッファ４５、４９ｂからそれぞれのセルが出力さ
れることになる。この「第１の状態」では、また同時に
各々のサブバッファ３２ａ₁、３２ｂ₁の前段の主バッフ
ァ部３１₁および第１のサブバッファ３２ａ₁の出力が、
各々のＮバッファ４５、４９ｂに読み込まれる様子も示
している。

【００５８】「第２の状態」は、第２のサブバッファ３
２ｂ₁の出力セルが衝突で負け、第１のサブバッファ３
２ａ₁からは有効セルがないか、または出力セル間に衝
突がないか、あるいは衝突があった場合にこれに勝った
状態の動作を表わしている。衝突で負けた第２のサブバ
ッファ３２ｂ₁の出力セルは出力と同時に第２のサブバ
ッファ３２ｂ₁自身のＰバッファ４８ｂにも書き込まれ
ており、同時に第１のサブバッファ３２ａ₁のＮバッフ
ァ４５には前段の主バッファ部３１₁からの新たなセル
４３が書き込まれている。従って、次回のセル出力で
は、第１のサブバッファ３２ａ₁はＮバッファ４５か
ら、また第２のサブバッファ３２ｂ₁の場合にはＰバッ
ファ４８ｂからそれぞれのセルを出力する。この「第２
の状態」では、また同時に各々のサブバッファ３２
ａ₁、３２ｂ₁の前段の主バッファ部３１₁および第１の
サブバッファ３２ａ₁の出力が、各々のＮバッファ４
５、４９ｂに読み込まれる様子も示している。

【００５９】「第３の状態」は、第１および第２のサブ
バッファ部３２ａ₁、３２ｂ₁の双方の出力セルが衝突で
負けた場合を表わしている。この場合にはそれぞれの出
力セルは第１および第２のサブバッファ部３２ａ₁、３
２ｂ₁の各々のＰバッファ４４、４８ｂにも書き込まれ
ている。従って、次回のセル出力では、第１および第２
のサブバッファ部３２ａ₁、３２ｂ₁は各々のＰバッファ
４４、４８ｂからそれぞれのセルを出力する。この場合
には、第１のサブバッファ部３２ａ₁のＮバッファ４５
には前段の主バッファ部３１₁の出力するセル４３がす
でに格納されている。従って、第１のサブバッファ部３
２ａ₁のＮバッファ４５へのデータの読み込みは一時停
止される。また、第２のサブバッファ３２ｂ₁のＮバッ
ファ４９ｂには何時も前段の第１のサブバッファ部３２
ａ₁の出力するセル出力１４₁が格納されている。

【００６０】状態遷移を示す図６を用いて、図１に示し
た第１の入力バッファ部１１₁における第１および第２
のサブバッファ部３２ａ₁、３２ｂ₁の入出力動作と衝突
の様子を詳細に説明したが、図６を検討すると、各状態
の遷移イベントである第１の変換回路３６₁と第２の変
換回路３６₂の組み合わせと、各状態がすべて一致して
いることが分かる。すなわち、第１の変換回路３６₁と
第２の変換回路３６₂の組み合わせを（「第１の変換回
路」、「第２の変換回路」）で表わしたとき、これが
（０、０）であるならば「初期状態」であり、（１、
０）であるならば「第１の状態」となっている。また、
（０、１）のときには「第２の状態」となっており、
（１、１）のときには「第３の状態」となっている。こ
のように、これらは一意に決定されることになる。

【００６１】この意味するところは、本実施例の第１の
入力バッファ部１１₁の第１および第２のサブバッファ
部３２ａ₁、３２ｂ₁の動作を説明するために図６に示し
たような状態遷移図を用いて状態を考察する必要はな
く、すべてを真理値表の形で表現できることである。

【００６２】図７は、図６に示した状態遷移図を真理値
表にしたものである。なお、この図では表示のスペース
を省略するために、第１の変換回路３６₁をＧ₁、第２の
変換回路３６₂をＧ₂とそれぞれ略記し、主バッファ４１
をＢＦ₀、第１のサブバッファ部３２をＢＦ₁、第２のサ
ブバッファ部３２ｂをＢＦ₂と略記している。また、Ｐ
バッファについては単にＰ、Ｎバッファについては単に
Ｎと略記している。各変換回路Ｇ₁、Ｇ₂における「０」
と「１」の意味は次の通りである。すなわち、「０」と
は、すべての入力方路で同一の宛先のセルの衝突がない
か、あるいは衝突がある場合にはそれに勝った状態を示
している。「１」とはすべての入力方路で同一の宛先の
セルの衝突があり、衝突で負けた状態を示している。な
お、初期状態では主バッファ４１および第１および第２
のサブバッファ部３２、３２ｂは、すべてクリアされる
ようになっている。図７に示すように真理値表が得られ
ると、これを基にしてバッファ制御論理を導くことは容
易になる。この真理値表を実際の論理素子に置き換えた
のが、図２に示すバッファ制御部３４₁の内部構成とな
る。

【００６３】さて、図１に示す第１〜第４の入力バッフ
ァ部１１₁〜１１₄から出力される複数のセル出力１３₁
〜１３₄、１４₁〜１４₄は衝突判定部１５に入力される
ようになっている。衝突判定部１５は図３に示すような
バッチャ型の検出回路で構成されている。衝突判定部１
５では、すでに説明したように同一バッファ内での衝突
の検出と入力ポートの復元を行う同一ポート内衝突検出
回路６１と、その後段に配置され、すべての入力バッフ
ァ間で同一出力の検出と入力ポートの復元を行う同一宛
先セル衝突検出回路６２とによって構成されている。バ
ッチャ型の検出回路は、２入力２出力の単位ソーティン
グ回路６３と、２入力２出力の単位スイッチ回路６４を
組み合わせて構成したものである。

【００６４】図８および図９は、バッチャ型の検出回路
における２入力２出力の単位ソーティング回路の各動作
を示したものである。ここで符号Ａ、Ｂはルーチング情
報を示しており、符号ＢＦ_k、ＢＦ_mはバッファ識別子を
表わしている。図８（ａ）および（ｂ）は、単位ソーテ
ィング回路６３に入力されるセルのスイッチング情報部
７１Ｃ（図５参照）が有効セルであり、衝突で負けがな
く、ルーチング情報７１Ｃ₄が等しくない場合を示して
いる。同図（ａ）では単位ソーティング回路６３から結
果の信号“０”が出力され、同図（ｂ）では結果の信号
“１”が出力されている。

【００６５】同図（ｃ）および（ｄ）はルーチング情報
７１Ｃ₄が等しい場合を示している。このような場合に
は、ソーティング方向と入力の関係とバッファ識別子７
１Ｃ ₃の大小で勝ち負けが決定される。これは、図５に
示したサブバッファ識別子の大きな時間的に古いセルを
優先的に出力するためである。

【００６６】図９（ｅ）および（ｆ）は、ルーチング情
報７１Ｃ₄が等しい場合ですでに一度負けているセルの
場合を示している。このようなすでに一度負けているセ
ルの場合には、ソーティング方向と入力の関係とバッフ
ァ識別子７１Ｃ₃の大小関係は意味をなさなくなり、常
に負けと判定される。

【００６７】同図（ｇ）は、負けセル同士の場合を示し
ており、判定の対象外となっている。同図（ｈ）および
（ｉ）は空きセルが入力された場合を示している。これ
らの図に示したように空きセルは常に無視される。

【００６８】図１０は、バッチャ型の検出回路における
単位スイッチ回路の各動作を示したものである。ここで
符号Ａ、Ｂはルーチング情報を示しており、符号Ｂ
Ｆ_k、ＢＦ_mはバッファ識別子を表わしている。このうち
同図（ａ）は入力される状態信号が信号“０”の場合に
おける単位スイッチ回路６４の動作を示したものであ
り、入力はそのまま平行に出力される。同図（ｂ）は入
力される状態信号が信号“１”の場合を示している。こ
の場合には、入力を上下それぞれ反対に切り替えて出力
が行なわれることになる。

【００６９】図１１は、図１に示した第１〜第４のセル
変換部における第１の変換回路の動作を示したものであ
る。第１の変換回路３６₁と第２の変換回路３６₂はそれ
ぞれの入力信号に対して全く同一の動作を行うので、第
２の変換回路３６₂の動作の説明は省略する。なお、こ
のような動作を行う第１の変換回路３６₁と第２の変換
回路３６₂は、衝突判定部１５からセルの受信部と衝突
で負けがあったかを検出する判定回路および、負けセル
と判定した場合に負けセルに対応した所定の空きセルを
生成し、次段のソータ部に送出する（空き）セル送出回
路で構成されている。

【００７０】図１１のステップＳ１０１では、まず図１
に示した衝突判定部１５から出力１７₁があるか、すな
わちセルの入力があるかどうかを監視する。セルの入力
があった場合には（Ｙ）、図５に示すスイッチング情報
部７１Ｃの有効表示部７１Ｃ ₁を見て、その入力セルが
有効セルか空きセルかの判別を行う（ステップＳ１０
２）。

【００７１】有効セルの場合には（Ｙ）、同じく図５に
示すスイッチング情報部７１Ｃの衝突情報部７１Ｃ₂を
見てそれが「０」であるかどうかを判別する（ステップ
Ｓ１０３）。衝突情報部７１Ｃ₂が「０」の場合には、
衝突がないか、または衝突があっても勝った場合のセル
である。そこでこの場合には（Ｙ）、入力されたセルを
そのままソータ部２５へ出力する（ステップＳ１０
４）。そして、ステップＳ１０５に進む。これに対して
衝突情報部７１Ｃ₂が「１」の場合には衝突で負けたセ
ルなので（ステップＳ１０３：Ｎ）、入力されたそのセ
ルを空きセルに変換してソータ部２５へ出力する（ステ
ップＳ１０６）。そして、ステップＳ１０５に進む。ス
テップＳ１０５では、ステップＳ１０３で参照したセル
の衝突情報部７１Ｃ₂を、対応する第１の入力バッファ
部１１₁のバッファ制御部３４₁に衝突情報２２₁として
返送して衝突状況を知らせる。そして、その後、再びス
テップＳ１０１に戻って衝突判定部１５から入力される
セルを待機することになる。

【００７２】図１２は、本実施例の第１の変形例として
バンヤン網で構成した自己ルーチング部を示したもので
ある。この例では先の実施例と同様に入出力関係が４×
４構成の場合を示している。

【００７３】図１３は、本実施例の第２の変形例として
８×８構成のバンヤン網で構成した自己ルーチング部を
示したものである。この例に示したように８×８のＡＴ
Ｍスイッチあるいは他の入出力関係のＡＴＭスイッチを
採用することは当然ながら自由である。

【００７４】図１４は、本発明の第３の変形例として８
×８構成のオメガ網で構成した自己ルーチング部を示し
たものである。これら第１〜第３の変形例では図１と同
一部分には同一の符号を付しており、これらの説明は省
略する。

【００７５】図１５は、本発明の第４の変形例のＡＴＭ
スイッチの構成を表わしたものである。この図で図１と
同一部分には同一の符号を付しており、これらの説明を
適宜省略する。この第４の変形例では、ＡＴＭスイッチ
のシャッフルの深さを３列にして、図１に示した２列の
ＡＴＭスイッチよりもシャッフル効率を向上させてい
る。すなわち、第１〜第４の入力バッファ部１１Ａ₁〜
１１Ａ₄のうちで回路をより具体的に示した第１の入力
バッファ部１１Ａ₁から明らかなように、第１および第
２のサブバッファ部３２ａ₁、３２ｂ₁の後には第３のサ
ブバッファ部３２ｃ ₁が設けられている。バッファ制御
部３４Ａ₁は、主バッファ部３１₁と各サブバッファ部３
２ａ₁、３２ｂ₁、３２ｃ₁の制御を行う。第２のサブバ
ッファ部３２ｂ₁から出力されるセル出力１３₁は第３の
サブバッファ部３２ｃ₁に入力されると共に衝突判定部
１５Ａに入力される。また、第３のサブバッファ部３２
ｃ₁の出力するセル出力８２₁は、他の２種類のセル出力
１３₁、１４₁と共に衝突判定部１５Ａに入力されるよう
になっている。

【００７６】一方、第１〜第４のセル変換部１９Ａ₁〜
１９Ａ₄には、第１のセル変換部１９Ａ₁に代表して示し
たように第１の変換回路３６₁と第２の変換回路３６₂の
他に第３の変換回路３６₃が配置されている。第１のセ
ル変換部１９Ａ₁内の第３の変換回路３６₃は、衝突判定
部１５Ａの対応する出力８４₁を入力して、衝突情報８
５₃を第１の入力バッファ部１１Ａ₁のバッファ制御部３
４Ａ₁に返信すると共に、衝突の勝ちと判定した勝ち情
報を有するセル８６₁を次段のソータ部２５Ａに供給す
るようになっている。なお、第２〜第４の入力バッファ
部１１Ａ₂〜１１Ａ₄および第２〜第４のセル変換部１９
Ａ₂〜１９Ａ₄の構成および動作は第１の入力バッファ部
１１Ａ₁および第１のセル変換部１９Ａ₁と同一であるの
で、これらの説明は省略する。

【００７７】図１６は、この第４の変形例における第１
の入力バッファ部の回路構成を具体的に表わしたもので
ある。この図１６で先の実施例の図２と同一部分には同
一の符号を付しており、これらの説明を適宜省略する。

【００７８】第１の入力バッファ部１１Ａ₁内の第３の
サブバッファ部３２ｃ₁も第２のサブバッファ部３２ｂ₁
と同様に容量がそれぞれ１セル分のＰバッファ４８ｃと
Ｎバッファ４９ｃを備えている。第２のサブバッファ部
３２ｂ₁から出力される出力セル１３₁はＮバッファ４９
ｃに入力されるようになっている。第３のサブバッファ
部３２ｃ₁には空きセル生成回路５１ｃが配置されてお
り、その出力とＮバッファ４９ｃの出力が第１の選択回
路５２ｃに入力され、この第１の選択回路５２ｃの出力
とＰバッファ４８ｃの出力が第２の選択回路５３ｃに入
力されるようになっている。これら第１および第２の選
択回路５２ｃ、５３ｃは、それぞれバッファ制御部３４
Ａ₁から出力される選択制御信号５４ｃ₁および衝突情報
８５₃によって制御される。第２の選択回路５３ｃから
出力されるセル出力８２₁は、Ｐバッファ４８ｃに供給
される他、図１５に示した衝突検出・シャッフル部の衝
突判定部１５Ａに入力されるようになっている。

【００７９】バッファ制御部３４Ａ₁は、２つのアンド
回路５７Ａ、９８ｂと１つのオア回路９９を備えてい
る。第１のアンド回路５７Ａは３入力の論理積をとる回
路であり、衝突情報２１₁、２２₁および８５₃の論理積
をとるようになっている。第１のアンド回路５７Ａから
出力される主バッファ読出一時停止信号４２Ａは主バッ
ファ部３１₁に供給される他、第１のサブバッファ部３
２ａ₁の選択回路４６に供給される。

【００８０】一方、第２のアンド回路９８ｂは衝突情報
２１₁と８５₃の２入力の論理積をとって、これを選択制
御信号１０１ｂ₁として第２の選択回路５３ｂに供給す
るようになっている。なお、第１のサブバッファ部３２
ａ₁内の選択回路４６には主バッファ読出一時停止信号
４２Ａがそのまま供給される。また、第２のサブバッフ
ァ部３２ｂ₁の第１の選択回路５２ｂには衝突情報２２₁
がそのまま供給されるようになっている。オア回路９９
は２つの衝突情報２２₁、８５₃の論理和をとってその出
力を選択制御信号５４ｃ₁として第３のサブバッファ部
３２ｃ₁内の第１の選択回路５２ｃに供給される。ま
た、衝突情報８５₁はそのまま第３のサブバッファ部３
２ｃ₁内の第２の選択回路５３ｃに供給されるようにな
っている。

【００８１】図１７は、この第４の変形例におけるバッ
ファ制御部の真理値表を表わしたものである。なお、こ
の図では図示のスペースを省略するために、第１の変換
回路３６₁をＧ₁、第２の変換回路３６₂をＧ₂、第３の変
換回路３６₃をＧ₃とそれぞれ略記し、主バッファ４１を
ＢＦ₀、第１のサブバッファ部３２をＢＦ₁、第２のサブ
バッファ部３２ｂをＢＦ₂、第３のサブバッファ部３２
ｃをＢＦ₃と略記している。また、Ｐバッファについて
は単にＰ、Ｎバッファについては単にＮと略記してい
る。各変換回路Ｇ₁、Ｇ₂、Ｇ₃における「０」と「１」
の意味は次の通りである。すなわち、「０」とは、すべ
ての入力方路で同一の宛先のセルの衝突がないか、ある
いは衝突がある場合にはそれに勝った状態を示してい
る。「１」とはすべての入力方路で同一の宛先のセルの
衝突があり、衝突で負けた状態を示している。なお、初
期状態では主バッファ４１および第１〜第３のサブバッ
ファ部３２ａ、３２ｂ、３２ｃは、すべてクリアされる
ようになっている。

【００８２】この第４の変形例では、図１５に示すよう
に衝突判定部１５Ａの各入力バッファ部に対応する入力
回路がそれぞれ３入力となる。したがって、衝突判定部
１５Ａ全体では１２入力１２出力となる。また同様に、
第１〜第４のセル変換部１９Ａ₁〜１９Ａ₄の内部の各変
換回路３６₁、３６₂、３６₃もすでに説明したように３
回路ずつ必要となり、ソータ部２５Ａも１２入力４出力
構成となる。自己ルーチング部２８自体の構成は先の実
施例の場合と同様である。

【００８３】図１８は、本発明の第５の変形例としてＡ
ＴＭスイッチのシャッフルの深さを４列にした場合の入
力バッファ部におけるバッファ制御部の動作を表わす真
理値表の内容を示したものである。なお、この図では図
示のスペースを省略するために、第１の変換回路３６₁
をＧ₁、第２の変換回路３６₂をＧ₂、第３の変換回路３
６₃をＧ₃、第４の変換回路３６₄をＧ₄とそれぞれ略記
し、主バッファ４１をＢＦ ₀、第１のサブバッファ部３
２をＢＦ₁、第２のサブバッファ部３２ｂをＢＦ₂、第３
のサブバッファ部３２ｃをＢＦ₃、第４のサブバッファ
部をＢＦ₃と略記している。また、Ｐバッファについて
は単にＰ、Ｎバッファについては単にＮと略記してい
る。各変換回路Ｇ₁、Ｇ₂、Ｇ₃、Ｇ₄における「０」と
「１」の意味は次の通りである。すなわち、「０」と
は、すべての入力方路で同一の宛先のセルの衝突がない
か、あるいは衝突がある場合にはそれに勝った状態を示
している。「１」とはすべての入力方路で同一の宛先の
セルの衝突があり、衝突で負けた状態を示している。な
お、初期状態では主バッファ４１および第１〜第４のサ
ブバッファ部３２ａ、３２ｂ、３２ｃ（第４のサブバッ
ファ部は図示していない）は、すべてクリアされるよう
になっている。

【００８４】図１９は、図１８に示した真理値表を参考
にして、シャッフルの深さを“ｍ”と一般化した場合の
入力バッファ部の内部構成を表わしたものである。図１
６と同一部分には同一の符号を付しており、これらの説
明を適宜省略する。図１９で第１の入力バッファ部１１
Ｍ₁内の第ｋのサブバッファ部３２ｋ₁および第Ｍのサブ
バッファ部３２ｍ₁も、第２のサブバッファ部３２ｂ₁と
同様に容量がそれぞれ１セル分のＰバッファ４８ｋ、４
８ｍとＮバッファ４９ｋ、４９ｍを備えている。それぞ
れ前段のサブバッファ部から出力される出力セル９３ｋ
₁、９３ｍ₁はＮバッファ４９ｋ、４９ｍに入力されるよ
うになっている。

【００８５】第ｋのサブバッファ部３２ｋ₁および第Ｍ
のサブバッファ部３２ｍ₁には、それぞれ空きセル生成
回路５１ｋ、５１ｍが配置されており、それぞれの出力
とＮバッファ４９ｋ、４９ｍの出力が第１の選択回路５
２ｋ、５２ｍに入力され、この第１の選択回路５２ｋ、
５２ｍの出力とＰバッファ４８ｋ、４８ｍの出力が第２
の選択回路５３ｋ、５３ｍに入力されるようになってい
る。これら第１および第２の選択回路５２ｋ、５２ｍ、
５３ｋ、５３ｍは、それぞれバッファ制御部３４Ｍ₁か
ら出力される選択制御信号５４ｋ₁、５４ｍ₁および衝突
情報８５k₁、８５ｍ₁によって制御される。ここで衝突
情報８５k₁、８５ｍ₁は、それぞれ第ｍの変換回路３
６_k、３６_m（図示せず）からそれぞれ出力される情報で
あり、衝突情報８５₃は図１５に示す衝突情報８５₃に等
しく、衝突情報８５₂は衝突情報２１₁に、衝突情報８５
₁は衝突情報２２₁にそれぞれ等しい。

【００８６】第２の選択回路５３ｋ、５３ｍから出力さ
れるセル出力９３ｍ₁、８２ｍ₁は、それぞれ対応するＰ
バッファ４８ｋ、４８ｍに供給される。このうちセル出
力９３ｍ₁は次段の図示しないサブバッファ部３２（ｋ
＋１）₁に送出され、最終段のセル出力８２ｍ₁は図１に
示した衝突検出・シャッフル部の衝突判定部１５と同様
の衝突検出・シャッフル部の衝突判定部１５Ａ（図示せ
ず）に入力されるようになっている。

【００８７】バッファ制御部３４Ｍ₁は、（ｍ−１）個
のアンド回路５７Ａ、９８ｂ、……９８ｋ、……９８
（ｍ−１）と、１つのオア回路９９を備えている。第１
のアンド回路５７Ａはシャッフルの深さ“ｍ”に対応し
た第１〜第ｍの変換回路３６₁〜３６_m（図示せず）から
出力されるすべての衝突情報２１₁、２２₁……８５_mの
論理積（先に説明したようにこれは衝突情報８５₁、８
５₂……８５_mと等価）をとるようになっている。第１の
アンド回路５７Ａから出力される主バッファ読出一時停
止信号４２ｍは主バッファ部３１₁に供給される他、第
１のサブバッファ部３２ａ₁の選択回路４６に供給され
る。

【００８８】一方、第ｋのサブバッファ部３２ｋ₁の第
２の選択回路５３ｋには、第ｋのアンド回路９８ｋから
出力される選択制御信号１０１ｋ₁が入力され、第１の
選択回路５２ｋには選択制御信号５４ｋ₁が供給される
ようになっている。ここで第ｋのアンド回路論理９８ｋ
は衝突情報８５_m，８５_m-1……と８５ｋの論理積をとる
ようになっている。これは、論理積の結果が“１”の場
合、すなわち“ｋ”以降の後段のサブバッファですべて
衝突が発生したかを検出するためである。また、オア回
路９９は衝突情報８５_m-1と衝突情報８５_mの論理和をと
るようになっている。

【００８９】なお、第１のサブバッファ部３２ａ₁内の
選択回路４６には主バッファ読出一時停止信号４２Ａが
そのまま供給される。また、第ｋのサブバッファ部３２
ｋ₁の第１の選択回路５２ｋには衝突情報８５_k-1がその
まま供給されるようになっている。

【００９０】図２０は、本発明の第６の変形例としての
第１の入力バッファ部の構成を表わしたものである。こ
の変形例の第１の入力バッファ部１１Ｂは、先の実施例
の図２と同様に主バッファ部３１₁と第１のサブバッフ
ァ部３２ａ₁、第２のサブバッファ部３２ｂ_1Aおよびバ
ッファ制御部３４_1Aから構成されている。この図で図２
と同一部分には同一の符号を付しており、これらの説明
を適宜省略する。

【００９１】この第６の変形例では、第２のサブバッフ
ァ部３２ｂ_1Aの構成を簡略化している。すなわち、図２
に示す第２のサブバッファ部３２ｂ₁と比べると、空き
セル生成回路５１ｂと、その出力とＮバッファ４９ｂの
出力とを選択する第１の選択回路５２ｂが存在していな
い。この変形例の第２のサブバッファ部３２ｂ_1Aでは、
Ｎバッファ４９ｂのクリアによって空きセルの送出を行
わせるようになっている。

【００９２】

【発明の効果】以上説明したように請求項１〜請求項３
記載の発明によれば、セルを入力順に取り出すＦＩＦＯ
メモリ等のメモリと幾つかの小容量のバッファメモリお
よび選択回路を設けることで、入力バッファ内に蓄積す
るセルのシャッフル動作を行うことで、入力バッファ型
のＡＴＭスイッチのバッファ構成を簡略化することがで
き、入力バッファ部の高速化とバッファ制御の容易化を
実現することができる。また、請求項１〜請求項３記載
の発明によれば、セルの競合がない場合には該当の出力
ポートが空いており、バッファの部分から複数のセルを
一度に読み出して出力することが可能であり、従来の入
力バッファ型ＡＴＭスイッチのスループットの低下や輻
輳状態の長期化といった問題が発生せず、高速処理を実
現することができる。

【００９３】また請求項３記載の発明では、第２段のザ
ブバッファ手段に空きセル生成回路を設けたので、空き
セルの送出処理を高速化することができる。更に、請求
項６記載の発明では空きセルを専用の回路を設けること
なく発生させるので、回路の簡素化に貢献することにな
る。

【図面の簡単な説明】

【図１】本発明の一実施例における４×４のＡＴＭスイ
ッチの構成を表わしたブロック図である。

【図２】図１に示した第１の入力バッファ部の構成を具
体的に表わしたブロック図である。

【図３】図１に示した衝突判定部の具体的な構成を表わ
したブロック図である。

【図４】図１に示したソータ部の具体的な構成を表わし
たブロック図である。

【図５】本実施例のＡＴＭスイッチに入力されるセルに
ついてのフォーマットを示したフォーマット説明図であ
る。

【図６】本実施例の第１および第２のサブバッファ部に
おける状態遷移図である。

【図７】図６に示した状態遷移図を真理値表に表わした
説明図である。

【図８】本実施例のバッチャ型の検出回路における２入
力２出力の単位ソーティング回路の各動作を示した説明
図である。

【図９】本実施例のバッチャ型の検出回路における２入
力２出力の単位ソーティング回路の各動作を示した説明
図である。

【図１０】本実施例のバッチャ型の検出回路における単
位スイッチ回路の各動作を示した説明図である。

【図１１】図１に示した第１〜第４のセル変換部におけ
る第１の変換回路の動作を示した流れ図である。

【図１２】本実施例の第１の変形例としてバンヤン網で
構成した自己ルーチング部を示したブロック図である。

【図１３】本実施例の第２の変形例として８×８構成の
バンヤン網で構成した自己ルーチング部を示したブロッ
ク図である。

【図１４】本発明の第３の変形例として８×８構成のオ
メガ網で構成した自己ルーチング部を示したブロック図
である。

【図１５】本発明の第４の変形例のＡＴＭスイッチの構
成を表わしたブロック図である。

【図１６】この第４の変形例における第１の入力バッフ
ァ部の回路構成を具体的に表わしたブロック図である。

【図１７】第４の変形例におけるバッファ制御部の真理
値表の内容を表わした説明図である。

【図１８】本発明の第５の変形例としてＡＴＭスイッチ
のシャッフルの深さを４列にした場合の入力バッファ部
におけるバッファ制御部の動作を表わす真理値表の内容
を表わした説明図である。

【図１９】図１８に示した真理値表を参考にして、シャ
ッフルの深さを“ｍ”と一般化した場合の入力バッファ
部の内部構成を表わした説明図である。

【図２０】本発明の第６の変形例としての第１の入力バ
ッファ部の構成を表わしたブロック図である。

【図２１】従来の入力バッファ型のＡＴＭスイッチの構
成の一例を表わしたブロック図である。

【図２２】従来の入力バッファ型のＡＴＭスイッチの構
成の他の例を表わしたブロック図である。

【図２３】ＦＩＦＯメモリを使用した従来のＡＴＭスイ
ッチの要部を示すブロック図である。

【符号の説明】

１１₁〜１１₄ 第１〜第４の入力バッファ部 １２₁〜１２₄ 第１〜第４の入力ポート １５ 衝突判定部 １９₁〜１９₄ 第１〜第４のセル変換部 ２５ ソータ部 ２８ 自己ルーチング部 ２９₁〜２９₄ 第１〜第４の出力ポート ３１₁ 主バッファ部 ３２ａ₁ 第１のサブバッファ部 ３２ｂ₁ 第２のサブバッファ部 ３４₁ バッファ制御部 ３６₁ 第１の変換回路 ３６₂ 第２の変換回路 ４１ 主バッファ ４４、４８ Ｐバッファ ４５、４９ Ｎバッファ ４６ 選択回路 ５２ 第1の選択回路 ５３ 第２の選択回路 ６３ 単位ソーティング回路 ６４ 単位スイッチ回路 ７１ ＡＴＭスイッチ入力セル ７１Ｃ スイッチング情報部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平５−292116（ＪＰ，Ａ) 特開 平６−105351（ＪＰ，Ａ) 特開 平８−172436（ＪＰ，Ａ) 特開 平２−303246（ＪＰ，Ａ) 特開 平４−942（ＪＰ，Ａ) 特開 平４−943（ＪＰ，Ａ) 特開 平８−172438（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04L 12/28 H04L 12/56

Claims (6)

(57)【特許請求の範囲】
1. 【請求項１】 ＡＴＭセルを時間的に並列して入力する
   複数の入力ポートと、 これら入力ポートに１つずつ対応して配置され対応する
   入力ポートから入力されるセルを複数蓄積して入力され
   た順番に１つずつ読み出す主バッファ手段と、 前記入力ポートに１つずつ対応して配置され、前段のバ
   ッファから送り出されたセルを入力して保持する第１の
   セル保持手段と、この第１の保持手段とは別にセルを保
   持する第２のセル保持手段と、これらのセル保持手段の
   出力側に配置されこれらから同時に出力されるセルの１
   つを選択する選択手段を備え、選択手段の選択したセル
   をセル送出タイミングで送り出すと共に送り出した同一
   のセルを第２のセル保持手段に入力するようにその１単
   位が構成され、かつそれぞれの単位が直列接続されてお
   り、最先の単位に属する第１のセル保持手段に前記主バ
   ッファの出力したセルが入力されるようになったザブバ
   ッファ手段と、 このザブバッファ手段の各単位の選択手段から出力され
   るセルを前記複数の入力ポート分だけ並列して入力して
   これらの出力ポート側でのセルの衝突の有無を検出する
   衝突検出手段と、 この衝突検出手段の検出結果をそれぞれの入力ポートの
   各選択手段ごとに入力して出力ポートのいずれでセルの
   衝突が生じるか否かと衝突が生じたときの今回出力する
   セルとしての勝ちセルを判定する判定手段と、 この判定手段の判定結果を入力して前記ザブバッファ手
   段のそれぞれの選択手段を制御し前記ザブバッファ手段
   から衝突の生じないセルあるいは衝突の生じる場合に勝
   ちセルとして判定されたセルを出力させるとともにこれ
   ら出力するセルがない場合にはそのタイミングで空きセ
   ルを出力させるバッファ手段制御手段と、 このバッファ手段制御手段の制御によって前記入力ポー
   トに１つずつ対応したザブバッファ手段から出力される
   セルの中から空きセルを除去し、各セルごとに対応する
   出力ポートに送出するルーチング手段とを具備すること
   を特徴とするＡＴＭスイッチ。
2. 【請求項２】 ＡＴＭセルを時間的に並列して入力する
   複数の入力ポートと、 これら入力ポートに１つずつ対応して配置され対応する
   入力ポートから入力されるセルを複数蓄積して入力され
   た順番に１つずつ読み出す主バッファ手段と、 前段のバッファから送り出されたセルを１セル分蓄積す
   る第１のバッファと、同じくセルを１セル分蓄積する第
   ２のバッファと、これら第１および第２のバッファの一
   方を選択してセルを出力させる選択回路とを備え、選択
   回路から出力されるセルを次段に出力すると共に前記第
   ２のバッファに送り込むように構成され、対応する入力
   ポートごとに互いに直列接続され、最前段の手段内の第
   １のバッファには前記主バッファの出力したセルが入力
   されるようになった複数のザブバッファ手段と、 各ザブバッファ手段の前記選択回路から出力されるセル
   を前記複数の入力ポート分だけ並列して入力してこれら
   の出力ポート側でのセルの衝突の有無を検出する衝突検
   出手段と、 この衝突検出手段の検出結果をそれぞれの入力ポートに
   対応した各サブバッファ手段の選択回路ごとに入力して
   出力ポートのいずれでセルの衝突が生じるか否かと衝突
   が生じたときの今回出力するセルとしての勝ちセルを判
   定する判定手段と、 この判定手段の判定結果を入力して前記複数のザブバッ
   ファ手段のそれぞれの選択回路を制御し前記複数のザブ
   バッファ手段ごとに衝突の生じないセルあるいは衝突の
   生じる場合に勝ちセルとして判定されたセルを出力させ
   るとともにこれら出力するセルがないザブバッファ手段
   からはそのタイミングで空きセルを出力させるバッファ
   手段制御手段と、 このバッファ手段制御手段の制御によって前記複数のザ
   ブバッファ手段から出力されるセルを対応する出力ポー
   トに送出するルーチング手段とを具備することを特徴と
   するＡＴＭスイッチ。
3. 【請求項３】 ＡＴＭセルを時間的に並列して入力する
   複数の入力ポートと、 これら入力ポートに１つずつ対応して配置され対応する
   入力ポートから入力されるセルを複数蓄積して入力され
   た順番に１つずつ読み出すＦＩＦＯメモリから構成され
   た主バッファ手段と、 この主バッファ手段から送り出されたセルを１セル分蓄
   積する第１のバッファと、同じくセルを１セル分蓄積す
   る第２のバッファと、これら第１および第２のバッファ
   の一方を選択してセルを出力させる選択回路とを備え、
   選択回路から出力されるセルを次段に出力すると共に前
   記第２のバッファに送り込むように構成され、対応する
   入力ポートごとに配置された第１のザブバッファ手段
   と、 この第１のサブバッファ手段から送り出されたセルを１
   セル分蓄積する第１のバッファと、空きセルを発生させ
   る空きセル生成回路と、この空きセル生成回路と前記第
   １のバッファの一方を選択してセルを出力させる第１の
   選択回路と、セルを１セル分蓄積する第２のバッファ
   と、この第２のバッファと前記第１の選択回路の出力の
   バッファの一方を選択してセルを出力させる第２の選択
   回路とを備え、第２の選択回路から出力されるセルを次
   段に出力すると共に前記第２のバッファに送り込むよう
   に構成され、前記第１のザブバッファ手段と共に対応す
   る入力ポートごとに互いに直列接続された第２段あるい
   はこれ以降の複数段のザブバッファ手段と、 前記第１のザブバッファ手段の前記選択回路および第２
   段あるいはこれ以降の複数段のザブバッファ手段の第２
   の選択回路から出力されるセルを前記複数の入力ポート
   分だけ並列して入力してこれらの出力ポート側でのセル
   の衝突の有無を検出する衝突検出手段と、 この衝突検出手段の検出結果をそれぞれの入力ポートに
   対応した各サブバッファ手段の第１または第２の選択回
   路ごとに入力して出力ポートのいずれでセルの衝突が生
   じるか否かと衝突が生じたときの今回出力するセルとし
   ての勝ちセルを判定する判定手段と、 この判定手段の判定結果を入力して前記主バッファ手段
   および第１のザブバッファ手段以降のザブバッファ手段
   のそれぞれの選択回路を制御し前記複数のザブバッファ
   手段ごとに衝突の生じないセルあるいは衝突の生じる場
   合に勝ちセルとして判定されたセルを出力させるととも
   にこれら出力するセルがないザブバッファ手段からはそ
   のタイミングで前記空きセルを出力させるバッファ手段
   制御手段と、 このバッファ手段制御手段の制御によって前記複数のザ
   ブバッファ手段から出力されるセルを対応する出力ポー
   トに送出するルーチング手段とを具備することを特徴と
   するＡＴＭスイッチ。
4. 【請求項４】 前記バッファ手段制御手段は、判定手段
   のそれぞれの判定結果に対する主バッファ手段およびザ
   ブバッファ手段の状態遷移を真理値表で表わしたものを
   基にした論理素子で構成されていることを特徴とする請
   求項１〜請求項３記載のＡＴＭスイッチ。
5. 【請求項５】 前記ルーチング手段の手前には、前記判
   定手段を経て送られてきたそれぞれのセルを入力して、
   空きセルでない有効セル数の最大値が、出力ポート数以
   下になるように設定するためのソータ手段が配置されて
   いることを特徴とする請求項１〜請求項３記載のＡＴＭ
   スイッチ。
6. 【請求項６】 前記第１のバッファをクリアすることに
   よって空きセルを発生させこれを出力することを特徴と
   する請求項２記載のＡＴＭスイッチ。