JPH05175987A - 先入先出メモリ及びセル交換装置 - Google Patents

Abstract

(57)【要約】 【構成】 所定の情報をその入力順に記憶する複数のキ
ュー２００ａ、２００ｂと、各キューの同一位置に同一
の情報Ａ、Ｂ、Ｃ、Ｄ、・・・を順に入力する入力手段
１００と、各キュー２００ａ、２００ｂの異なる位置か
ら上記入力手段１００により入力された異なる情報を出
力する出力手段３００を備え、キュー２００ａから情報
Ａを出力し、キュー２００ｂから情報Ｂを出力し、独自
にアクセス可能な各キューからそれぞれ情報を順にとり
出す。 【効果】 キュー２００のアクセスタイムに影響されな
いＦＩＦＯメモリを得ることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、高速なＦＩＦＯメモ
リ及びそれを利用したセル交換装置に関するものであ
る。

【０００２】

【従来の技術】従来から、スイッチの入出力リンク速度
より大きい速度の回線の収容方式が考えられている。例
えば、６００Ｍｂｐｓの回線を８本入力し８本出力する
（以下、６００Ｍｂｐｓ８×８と略記する。また、他の
例も同様に略記する）スイッチで２．４Ｇｂｐｓ２×２
の交換を行なうことや、１５０Ｍｂｐｓ３２×３２のス
イッチで６００Ｍｂｐｓ８×８の交換を行うことが考え
られている。例として、図９を用いて、１５０Ｍｂｐｓ
４×４のスイッチを３００Ｍｂｐｓ２×２のスイッチと
して使用する方法について述べる。３００Ｍｂｐｓのリ
ンク速度を持つ入線Ａ，Ｂ（２本）を１５０Ｍｂｐｓの
速度４本に分離（ＤＭＵＸ）し、これを１５０Ｍｂｐｓ
４×４のスイッチで交換し、交換された１５０Ｍｂｐｓ
４本を多重（ＭＵＸ）し、出線ａ、ｂとして出力する。
ただし、１５０Ｍｂｐｓ４×４の交換を通常の動作で行
うと、セルの順序が保てないので、工夫が必要となる。

【０００３】以下、セルの順序を保つための共通バッフ
ァ方式について述べる。図１０は「共通バッファ形ＡＴ
ＭスイッチのＬＳＩ構成法」として信学技報ＳＳＥ８９
−１４４に記載されたＡＴＭスイッチの図である。

【０００４】各入力リンクのセルは、ＢＦＭ−ＬＳＩ内
の多重器（ＭＵＸ）で多重化され、１セルづつバッファ
メモリ（ＢＦＭ）へ格納される。このとき、セルのルー
ティングヘッダは、ルーティングデコーダ（ＲＴＤＥ
Ｃ）でデコードされ、その出線リンクに対応する書き込
みアドレスレジスタ（ＷＡ）の値を書き込みアドレスと
してＢＦＭに与える。このとき、空アドレスバッファ
（ＩＡＢＦ）（ＢＦＭの空（未使用）アドレスを蓄積す
るもの）から空アドレスを次アドレスとして出力し、Ｂ
ＦＭに格納されるセルと同一のアドレスに格納され、さ
らに書き込みアドレスを出力したＷＡにも格納される。

【０００５】一方、ＢＦＭから読み出されるセルは、そ
の読み出しタイミングに応じてＢＦＭ−ＬＳＩ内の分離
器（ＤＭＵＸ）で各出線リンクに振り分けられる。出線
カウンタ（ＯＵＴＣＮＴ）はこのタイミングに合わせて
出線リンクを指定し、その出線リンクに対応する読み出
しアドレスレジスタ（ＲＡ）から読み出しアドレスをＢ
ＦＭへ出力する。このとき、ＢＦＭからセルと次アドレ
スが読み出され、読み出しアドレスは空アドレスとして
ＩＡＢＦへ格納され、次アドレスは読み出しアドレスを
出力したＲＡに格納される。上記動作により、各出線リ
ンク毎に、次アドレスによってつながるアドレスチェー
ンがＢＦＭ上で論理的に構成される。これにより、ＢＦ
Ｍ上の各アドレスは各出線リンクに対して共通使用でき
る共通バッファ形メモリスイッチ構成となる。

【０００６】図に示すように、入力Ａのセルは、タイミ
ングをずらして順序性を保ちつつＢＦＭ−ＬＳＩ入力
０、２へ、入力Ｂのセルも同様にＢＦＭ−ＬＳＩ入力
１、３へ振り分ける。出力ａのセルは、ＢＦＭ−ＬＳＩ
出力０、２から出力され、ＭＵＸで多重される。このと
き、出力０、２間で順序性が保たれる必要がある。出力
ｂのセルについても同様である。

【０００７】そこで、ＣＴＲＬ−ＬＳＩは、ＢＦＭ−Ｌ
ＳＩ出力０〜３に対応する４つのチェーンを構成するの
ではなく、出力ａ，ｂでそれぞれ２つのチェーンを構成
する。これにより、ＢＦＭ−ＬＳＩ出力０、２間、およ
び、ＢＦＭ−ＬＳＩ出力１、３間で順序性を保つことが
可能となる。以上の動作により、スイッチ全体は、リン
ク速度３００Ｍｂｐｓ２×２スイッチとして動作する。
この例の基本的な考え方としては、アドレスキューを出
線別に４本持つのではなく、回線単位に持つ（この例で
は２本持つ）ことにより、順序保存を行うものである。

【０００８】

【発明が解決しようとする課題】従来のセル交換装置は
以上のように構成されているので、４本の出線に対して
アドレスキューを２本もっており、ひとつのアドレスキ
ューから同時に２つのアドレスを読み出すことにより４
本の出線に対する出力を確保していた。ひとつのアドレ
スキューがひとつの出線に対応している場合は、図１１
（ａ）に示すようにひとつのアドレスキューからひとつ
のアドレスを読み出せばよく、１回のアクセスですむ
が、このように、ひとつのアドレスキューが２本の出線
に対応している場合は、図１１（ｂ）に示すように２回
のアクセスが必要になる。このアドレスキューは通常Ｒ
ＡＭで構成されているため、ＲＡＭへのアクセスタイム
がネックになるという不具合が生じることになる。

【０００９】この発明は上記のような問題点を解消する
ためになされたもので、アクセスタイムの高速な先入先
出メモリを得るとともに、スイッチの入出力リンク速度
より大きい速度の回線を収容しても高速なセル交換が可
能なセル交換装置を得ることを目的とする。

【００１０】

【課題を解決するための手段】請求項１記載の発明に係
る先入先出メモリは以下の要素を有するものである。
（ａ） 所定の情報をその入力順に記憶する複数のキュ
ー、（ｂ） 上記各キューに同一の情報を順に入力し、
各キューの同一の位置にその情報を記憶させる入力手
段、（ｃ） 上記各キューの異なる位置から上記入力手
段により順に入力された異なる情報を出力する出力手
段。

【００１１】また、請求項２記載の発明に係るセル交換
装置は、上記先入先出メモリをアドレスキューとして用
いたものである。

【００１２】

【作用】第１の発明に係る先入先出メモリは、入力手段
が複数のキューそれぞれに同一データを順に記録し、出
力手段がそれぞれのキューの異なる位置から異なるデー
タを一度に読み出すので、一度のアクセスで複数のデー
タが読み出し可能となる。

【００１３】第２の発明に係るセル変換装置は、上記先
入先出メモリをひとつのアドレスキューとして使用する
ので、ひとつのアドレスキューから一度のアクセスで複
数のアドレスが得られるためアドレスキューへのアクセ
スネックが解消される。

【００１４】

【実施例】実施例１．図１は、第１の発明の先入先出メ
モリの一実施例を示すブロック図であり、１００は入力
手段、２００はＲＡＭで構成されたキュー２００ａ、２
００ｂをもつアドレスキュー、３００は出力手段であ
る。入力手段１００は、同一のアドレス情報Ａ，Ｂ，Ｃ
等を、それぞれのキュー２００ａ、２００ｂの同一位置
に順に書き込む。出力手段３００は読み出し時に、キュ
ー２００ａの先頭の値Ａとキュー２００ｂの２番目の値
Ｂを読み出す。次のアクセスでは、キュー２００ｂの２
番目まですでに読んでいるのでキュー２００ａの３番目
の値Ｃから読み出し、同時にキュー２００ｂの４番目の
値Ｄを読み出す。以上の動作を行なうことで、２本のキ
ューで順序保存が可能になり、かつ、ＲＡＭへのアクセ
スタイムネックが生じないようになる。

【００１５】実施例２．次に、図２は、３本のキュー２
００ａ〜２００ｃでひとつのアドレスキューを構成する
場合を示しており、各キューから情報を２つおきに読み
出すことにより入力順序が保存されたまま出力されるこ
とになる。

【００１６】実施例３．図３は、３本のキュー２００ａ
〜２００ｃがあり、１回目のアクセスでキュー２００ｃ
からの読み出しが保留された場合の動作を説明するもの
であり、１回目のアクセスで第２番目まで（Ａ，Ｂま
で）読み出したので、２回目のアクセスは、キュー２０
０ａの３番目の値Ｃから以降を読み出す場合を示してい
る。このように出力手段３００の出力は常にキュー２０
０ａから順に行なうように設定しておくことにより、出
力手段３００の構成が簡単になる。このように、出力を
常にキュー２００ａから順に行なうようにしても、入力
順を保存して出力するということは保証されている。

【００１７】実施例４．次に、第２の発明の一実施例に
ついて説明する。図４において、１ａ〜１ｎは、宛先情
報としての出線番号を含むヘッダ部とデータ部よりなる
セルが入力されるｎ（ｎ≧２）本の入線、２ａ〜２ｍ
は、セルがそのヘッダ部にて指定された宛先に応じて出
力されるｍ（ｍ＞２）本の出線である。１０は前記各入
線１のそれぞれに対応して設けられ、対応する入線１よ
り入力されたセルのヘッダ部より宛先の出線２を検出す
るヘッダ処理回路である。２１ａ〜２１ｎは前記入線１
ａ〜１ｎの各々に対応して設けられ、前記ヘッダ処理回
路より出力されるセルを蓄積し、高速に読み出すことに
より速度調整を行なう入線速度調整バッファである。

【００１８】また、１１はそれぞれにバッファメモリ番
号＃０，＃１，・・・が付与され、指定されたアドレス
に前記セルを蓄積して、そのアドレスを指定することに
よって書き込みの際の順序とは無関係に蓄積されたセル
を読み出すことができるｐ（ｎ≦ｐ）個のバッファメモ
リで、１つのバッファメモリ１１にセルを蓄積できるバ
ッファ２３をｑを個持つ。またバッファ２３は書き込み
セルが同報セルであれば同報する宛先数を、同報セルで
なければセルを送る数１をセルに付けて書き込むことが
できるものである。１２はこのバッファメモリ１１の各
々に対応して設けられ、例えばＦＩＦＯタイプのメモリ
を用いて空きアドレスの管理を行い、対応付けられたバ
ッファメモリ１１にリードアドレスおよびライトアドレ
スを与える記憶制御回路である。

【００１９】１３は前記入線速度調整バッファ２１ａ〜
２１ｎを所定のバッファメモリ１１に選択的に接続する
入線空間スイッチであり、１４は各バッファメモリ１１
を所定の出線２に対応した出線速度調整バッファ２２ａ
〜２２ｍに選択的に接続する出線空間スイッチである。

【００２０】２２ａ〜２２ｍは前記出線２ａ〜２ｍに対
応して設けられ、前記バッファメモリ１１ａ〜１１ｐよ
り高速に読み出され出線空間スイッチ１３によって接続
されたセルを蓄積し、出線の速度に調整する出線速度調
整バッファである。

【００２１】１５は入線空間スイッチ１３のスイッチン
グを制御してセルが蓄積されるバッファメモリ１１の選
択を行うとともに、出線空間スイッチ１４のスイッチン
グを制御して、バッファメモリ１１に蓄積されたセルを
そのヘッダ部で指定される出線２に所定の順番で出力さ
せるバッファ制御回路である。

【００２２】また、このバッファ制御回路１５内におい
て、１６は前記各入線１に対応付けられたヘッダ処理回
路１０にセル到着時に検出された当該セルの宛先出線番
号２ａ〜２ｍを受け、当該セルを蓄積すべきバッファメ
モリ１１を選択してそれを該当するヘッダ処理回路１０
に接続するために、前記入線空間スイッチ１３のスイッ
チングを制御する書き込みバッファ選択回路である。１
７はこの書き込みバッファ選択回路１６から送られてく
る前記出線番号２ａ〜２ｍを参照して到着したセルを宛
先別に分け、当該セルが書き込まれたバッファメモリ１
１上のバッファのライトアドレスを、そのバッファメモ
リ１１に対応する記憶制御回路１２より得て、それを後
述する宛先別待ち行列に書き込むアドレス交換回路（入
力手段の一例）である。

【００２３】１８はその宛先別アドレス待ち行列（キュ
ーあるいはアドレスキューの一例）であり、実施例１〜
３で述べたＦＩＦＯタイプのメモリによって構成されて
前記出線２の各々に対応して設けられている。この宛先
別アドレス待ち行列１８には、それが対応付けられた出
線２毎に、当該出線２を宛先とするセルが蓄積されたバ
ッファメモリ１１上のバッファアドレスが前記アドレス
交換回路１７によって、セルが到着した順番に書き込ま
れる。

【００２４】１９はこの宛先別待ち行列１８を参照して
バッファメモリ１１から読み出すセルを決定し、出線空
間スイッチ１４のスイッチングを制御して、前記バッフ
ァメモリ１１を該当する出線２に付随した出線速度調整
バッファと接続する読みだしバッファ選択回路（出力手
段の一例）である。

【００２５】次にスイッチの入出力リンク速度より大き
い速度の回線を収容する（入線のデータをＤＭＵＸして
交換し、ＭＵＸして出線に出力する）場合の動作を説明
する。図５、図６でセルをバッファに書き込むまでの動
作、図７ではセルをバッファから読みだし出線へ出力す
る動作を示す。簡単のため入・出線数２、バッファメモ
リ数２、１メモリに含まれるバッファ数２、処理速度は
入・出線速度と等しいとする。

【００２６】あるタイムスロットで１個または２個のセ
ルが入線１に入力すると、セルの到着したヘッダ処理回
路１０はそのヘッダ部より宛先の出線番号２ａ，２ｂ
を、宛先情報として読み取り、セルの到着順に各セルの
宛先情報を書き込みバッファ選択回路１６へ送る。セル
は入線速度調整バッファ２１へ書き込まれる。書き込み
バッファ選択回路１６は各々のセルを書き込むバッファ
メモリ番号を番号順に決定する。ただし、そのメモリに
空きバッファがないときには次番号のバッファメモリを
選択する。同報セルは複数の宛先を持つが１つのバッフ
ァに１セル格納する。入線空間スイッチ１３はセルの書
き込まれている入線速度調整バッファ２１と決定したメ
モリを接続し、セルを所定のバッファに格納する。

【００２７】図５はバッファ００にセルＡが格納されて
いるとき、入線１ａにセルＢが到着し、１ｂにセルＣが
順に到着した状態で、図６はこの２つのセルの書き込み
が終了した状態である。まず、セルＢの書き込みバッフ
ァメモリを選択する。ここでバッファメモリ１１ｂを選
択したとする。セルＢはバッファ１０に格納し、このバ
ッファアドレス１０を、宛先別アドレス待ち行列１８
ａ，１８ｂの両方に並べる。次にセルＣの書き込みメモ
リを選択する。バッファメモリ１１ａに空きがあるので
バッファメモリ１１ａを選択する。書き込みバッファア
ドレス０１が決まると、セルＣをバッファに格納し、書
き込みバッファアドレス０１を宛先別アドレス待ち行列
１８ａ，１８ｂの両方に並べる。

【００２８】ここではセルの書き込み速度を入・出線と
等しくしたので同時に到着したセルＡとセルＢは異なる
バッファメモリに格納したが、書き込み速度を入線のｗ
（２≦ｗ≦入線数）倍にすると１タイムスロットで１つ
のメモリにｗ個のセルを書き込むことができる。例えば
バッファメモリ１１ａに空きバッファがなくバッファメ
モリ１１ｂに空バッファが２個あった場合、速度２倍で
はセルを２個バッファメモリ１に格納できる。ただし１
タイムスロットは１処理時間（入線に１セル到着する時
間）である。

【００２９】次に、図７を用いて、セルの読み出しを説
明する。図７はセルＡ，セルＢ，セルＣがそれぞれバッ
ファ００，１０，０１に格納されている状態で、ここか
ら各出線２ａ，２ｂに１セル出力したものである。宛先
別アドレス待ち行列１８ａの先頭にあるバッファアドレ
スからセルを読み出す。宛先別アドレス待ち行列１８ａ
の先頭には００が並んでいるので出線２ａにはバッファ
００に格納されているセルＡを出力する。宛先別アドレ
ス待ち行列１８ｂの２番目には１０が並んでいるのでバ
ッファ１０に格納されているセルＢを読みだす。出力し
たセルはいったん出線速度調整バッファ２２に書き込ん
で出線速度に合わせて出線へ出力する。

【００３０】また、次の出力では、宛先別アドレス待ち
行列１８ａの３番目が０１であるので、バッファ０１に
格納されているセルＣを読み出すことになる。ここでは
セルの読みだし速度を出線と等しくしたが、ｒ（２≦ｒ
≦出線数）倍にすると同一バッファメモリから１タイム
スロットでｒ個のセルを読み出すことができる。

【００３１】上記実施例では、バッファ００とバッファ
１０は異なるメモリにあるのでセルＡ，セルＢとも出力
できたが、図８に示すように、もし同時に読み出したい
セルが同一メモリにあった場合は１セルのみ出力し、残
りのセルはバッファ内にとどまり次に読み出されるまで
待ち合わせを行う。

【００３２】図８では、本来なら宛先別アドレス待ち行
列１８ａの先頭からバッファ００のセルＡと宛先別アド
レス待ち行列１８ｂの２番目からバッファ０１のセルＢ
を同時に読みこみたいところであるが、セルＡとセルＢ
が同一メモリにあるので、この場合はセルＡのみをまず
読み出すことになる。そして２回目のアクセスでは、再
び宛先待ち行列１８ａ（の２番目）を参照してバッファ
０１のセルＢを出力することになる。この際宛先別アド
レス待ち行列１８ｂの３番目は１０なのでバッファ１０
のセルＣもセルＢとともに出力されることになる。

【００３３】

【発明の効果】以上のように、第１の発明による先入先
出メモリによれば、アクセスタイムに影響されない高速
メモリが実現できる。

【００３４】また、第２の発明によるセル変換装置によ
れば、スイッチの入出力速度よりも大きい速度の回線を
収容しても高速なセル変換が可能になる。

【図面の簡単な説明】

【図１】第１の発明に係る先入先出メモリの実施例１を
示す図。

【図２】第１の発明に係る先入先出メモリの実施例２を
示す図。

【図３】第１の発明に係る先入先出メモリの実施例３を
示す図。

【図４】第２の発明に係るセル交換装置のブロックを示
す図。

【図５】第２の発明に係るセル交換装置の書き込み動作
説明図。

【図６】第２の発明に係るセル交換装置の書き込み動作
説明図。

【図７】第２の発明に係るセル交換装置の読み出し動作
説明図。

【図８】第２の発明に係るセル交換装置の読み出し動作
説明図。

【図９】回線の収容方式を説明する図。

【図１０】従来の回線の収容方式を説明する図。

【図１１】従来の先入先出メモリの動作を示す図。

【符号の説明】

１７，１００ 入力手段 １８，２００ アドレスキュー（キューの一例） １９，３００ 出力手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者 大島 一能 鎌倉市大船五丁目１番１号 三菱電機株式 会社通信システム研究所内

Claims (2)

【特許請求の範囲】
1. 【請求項１】 以下の要素を有する先入先出メモリ （ａ） 所定の情報をその入力順に記憶する複数のキュ
   ー、 （ｂ） 上記各キューに同一の情報を順に入力し、各キ
   ューの同一の位置にその情報を記憶させる入力手段、 （ｃ） 上記各キューの異なる位置から上記入力手段に
   より順に入力された異なる情報を出力する出力手段。
2. 【請求項２】 上記先入先出メモリを備えたことを特徴
   とするセル交換装置。