JPH04292038A - バッファメモリ - Google Patents
バッファメモリInfo
- Publication number
- JPH04292038A JPH04292038A JP3248303A JP24830391A JPH04292038A JP H04292038 A JPH04292038 A JP H04292038A JP 3248303 A JP3248303 A JP 3248303A JP 24830391 A JP24830391 A JP 24830391A JP H04292038 A JPH04292038 A JP H04292038A
- Authority
- JP
- Japan
- Prior art keywords
- memory
- output
- buffer
- module
- lines
- 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.)
- Granted
Links
- 230000015654 memory Effects 0.000 title claims abstract description 114
- 239000003550 marker Substances 0.000 claims abstract description 14
- 238000000034 method Methods 0.000 description 4
- 238000001514 detection method Methods 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 238000005192 partition Methods 0.000 description 2
- 238000010276 construction Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
Classifications
-
- 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
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Information Transfer Systems (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明はパケット交換網に用いる
バッファメモリに関し、特にパケット交換網のスイッチ
内でデータパケットを記憶するために用いられるバッフ
ァメモリの共用方法に関する。
バッファメモリに関し、特にパケット交換網のスイッチ
内でデータパケットを記憶するために用いられるバッフ
ァメモリの共用方法に関する。
【０００２】
【従来の技術】パケット交換網における１つのスイッチ
の機能はすべての入来データパケットを集めそしてそれ
らをそのスイッチの正しい出力ポートに切換えることで
ある。任意の時点で２以上の入力ポートに到着するパケ
ットを１つの同一の出力ポートに向けることがありうる
から、各スイッチ内にバッファメモリを設け、パケット
を一時的に記憶しその間それらが送られるべき出力ポー
トを他のパケットの送信に用いるようにする必要がある
。そのようなメモリを設けることについてはいくつかの
方法がある。それらの内の最も基本的なものは各出力ポ
ートに別々に先入れ先出し（ＦＩＦＯ）メモリを設けた
ものである。この場合、その出力ポートに向けられるパ
ケットはまずＦＩＦＯ待ち行列内に置かれ、そこで前に
入ったパケットのすべてが出力されてしまうまで保持さ
れる。しかしながらそのようなシステムは各出力ポート
に固定メモリサイズを置かなくてはならないのでメモリ
スペースの点で非常に不利である。このように、使用頻
度の高い出力ポートでのＦＩＦＯ待ち行列は容易に満杯
となり、隣りの使用頻度の低い出力ポートでの待ち行列
に充分な使用可能スペースがあるにも拘らず、それ以上
のパケットを記憶できないこととなる。
の機能はすべての入来データパケットを集めそしてそれ
らをそのスイッチの正しい出力ポートに切換えることで
ある。任意の時点で２以上の入力ポートに到着するパケ
ットを１つの同一の出力ポートに向けることがありうる
から、各スイッチ内にバッファメモリを設け、パケット
を一時的に記憶しその間それらが送られるべき出力ポー
トを他のパケットの送信に用いるようにする必要がある
。そのようなメモリを設けることについてはいくつかの
方法がある。それらの内の最も基本的なものは各出力ポ
ートに別々に先入れ先出し（ＦＩＦＯ）メモリを設けた
ものである。この場合、その出力ポートに向けられるパ
ケットはまずＦＩＦＯ待ち行列内に置かれ、そこで前に
入ったパケットのすべてが出力されてしまうまで保持さ
れる。しかしながらそのようなシステムは各出力ポート
に固定メモリサイズを置かなくてはならないのでメモリ
スペースの点で非常に不利である。このように、使用頻
度の高い出力ポートでのＦＩＦＯ待ち行列は容易に満杯
となり、隣りの使用頻度の低い出力ポートでの待ち行列
に充分な使用可能スペースがあるにも拘らず、それ以上
のパケットを記憶できないこととなる。
【０００３】メモリスペースのこの使用効率の低い問題
を解決する１つの手段は単一の共用ランダムアクセスメ
モリ（ＲＡＭ）を使用することである。メモリを各出力
ポートでの使用のために保存されるエリアに分割するた
めの固定区分の代りに、区画境界をフレキシブルにして
別途メモリスペースを必要とするＦＩＦＯ待ち行列がＲ
ＡＭ全体の中の不使用のメモリスペースの利用を行うこ
とができるようにする。これは、頻繁に使用される１個
の出力ポートにおける出力待ち行列が満杯のためにパケ
ットの失われる数は少ないからパケットのスループット
を改善するものであるが、極めて微小なメモリ実現技術
がある動作期間後に細分化されたメモリを再構成するに
必要となる。
を解決する１つの手段は単一の共用ランダムアクセスメ
モリ（ＲＡＭ）を使用することである。メモリを各出力
ポートでの使用のために保存されるエリアに分割するた
めの固定区分の代りに、区画境界をフレキシブルにして
別途メモリスペースを必要とするＦＩＦＯ待ち行列がＲ
ＡＭ全体の中の不使用のメモリスペースの利用を行うこ
とができるようにする。これは、頻繁に使用される１個
の出力ポートにおける出力待ち行列が満杯のためにパケ
ットの失われる数は少ないからパケットのスループット
を改善するものであるが、極めて微小なメモリ実現技術
がある動作期間後に細分化されたメモリを再構成するに
必要となる。
【０００４】
【発明が解決しようとする課題】ＩＢＭ Ｔｅｃｈｎ
ｉｃａｌ Ｄｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉ
ｎ．ｖｏｌ．３２、ＮＯ． ３Ｂ、１９８９年８月、ｐ
ｐ４８８−４９２には、“単一の共用ランダムアクセス
メモリからのＦＩＦＯ待ち行列を管理するためのアルゴ
リズム”と題名がつけられた記事があり、この記事には
上記技術に必要な細分化されたメモリの再構成のための
“不要部分の整理”動作を不要とするアルゴリズムが示
されている。この文献では第１ＲＡＭがすべてのパケッ
トの記憶に用いられ、第２ＲＡＭが出力待ち行列内のパ
ケットの位置を示すポインタの記憶に用いられる。この
システムは、次のパケットを読取るための第１ＲＡＭ内
のアドレスを示すために各出力ポートにレジスタを設け
ている。このレジスタは、第２ＲＡＭの、第１ＲＡＭに
記憶されるパケットのアドレスと同一のアドレスから出
力待ち行列内の次のパケットが記憶されるアドレスを読
取ることによりそのパケットが送られている間に更新さ
れる。このメモリ構成は従来のシステムに対し有利であ
るが、第２メモリが余分なハードウエアオーバヘッドを
増加する。更に、第１ＲＡＭのサイズは設計上の点で固
定されるから、新しい出力ポートおよび入力ポートの付
加によるシステムの拡張は、メモリ自体のサイズを増加
させることができないためデータ損失が許容される場合
にのみ可能である。本発明の目的はデータパケットスイ
ッチを通るデータの量が増加するときに複雑なアルゴリ
ズムまたは実質的なハードウエアの付加を伴わずに容易
に拡張しうるデータパケットスイッチで用いるためのＦ
ＩＦＯバッファメモリを提供することである。
ｉｃａｌ Ｄｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉ
ｎ．ｖｏｌ．３２、ＮＯ． ３Ｂ、１９８９年８月、ｐ
ｐ４８８−４９２には、“単一の共用ランダムアクセス
メモリからのＦＩＦＯ待ち行列を管理するためのアルゴ
リズム”と題名がつけられた記事があり、この記事には
上記技術に必要な細分化されたメモリの再構成のための
“不要部分の整理”動作を不要とするアルゴリズムが示
されている。この文献では第１ＲＡＭがすべてのパケッ
トの記憶に用いられ、第２ＲＡＭが出力待ち行列内のパ
ケットの位置を示すポインタの記憶に用いられる。この
システムは、次のパケットを読取るための第１ＲＡＭ内
のアドレスを示すために各出力ポートにレジスタを設け
ている。このレジスタは、第２ＲＡＭの、第１ＲＡＭに
記憶されるパケットのアドレスと同一のアドレスから出
力待ち行列内の次のパケットが記憶されるアドレスを読
取ることによりそのパケットが送られている間に更新さ
れる。このメモリ構成は従来のシステムに対し有利であ
るが、第２メモリが余分なハードウエアオーバヘッドを
増加する。更に、第１ＲＡＭのサイズは設計上の点で固
定されるから、新しい出力ポートおよび入力ポートの付
加によるシステムの拡張は、メモリ自体のサイズを増加
させることができないためデータ損失が許容される場合
にのみ可能である。本発明の目的はデータパケットスイ
ッチを通るデータの量が増加するときに複雑なアルゴリ
ズムまたは実質的なハードウエアの付加を伴わずに容易
に拡張しうるデータパケットスイッチで用いるためのＦ
ＩＦＯバッファメモリを提供することである。
【０００５】
【課題を解決するための手段】本発明はこの目的を、夫
々がすべての入力ポートからアクセスすることができ、
そしてそこからデータが出力ポートのいずれにも読取る
ことのできる一連のメモリモジュールでこのスイッチの
出力待ち行列をつくることにより達成する。出力ポート
にアドレスされるべきパケットは特定の１つのモジュー
ルが満杯となるまでこれらメモリモジュールの内のその
モジュールに読込まれる。次のデータパケットは他のメ
モリモジュール内の次に使用可能なフリースペースに読
込まれそしてマーカが第１モジュールに置かれて待ち行
列が次に使用可能なモジュールに続くことを示す。１つ
のモジュールからデータを読だすことにより、このマー
カが検出されそしてこのシステムは、このモジュールか
らのデータ読出しを停止し次のモジュールに以降の待ち
行列エントリを見出すことを知ることになる。
々がすべての入力ポートからアクセスすることができ、
そしてそこからデータが出力ポートのいずれにも読取る
ことのできる一連のメモリモジュールでこのスイッチの
出力待ち行列をつくることにより達成する。出力ポート
にアドレスされるべきパケットは特定の１つのモジュー
ルが満杯となるまでこれらメモリモジュールの内のその
モジュールに読込まれる。次のデータパケットは他のメ
モリモジュール内の次に使用可能なフリースペースに読
込まれそしてマーカが第１モジュールに置かれて待ち行
列が次に使用可能なモジュールに続くことを示す。１つ
のモジュールからデータを読だすことにより、このマー
カが検出されそしてこのシステムは、このモジュールか
らのデータ読出しを停止し次のモジュールに以降の待ち
行列エントリを見出すことを知ることになる。
【０００６】本発明では付加ハードウエアオーバーヘッ
ドは極めて少くそしてしかも使用可能なメモリスペース
のすべてを完全に利用することができる。そのモジュラ
ー構成は、任意の１つのスイッチが連続的にオーバロー
ドとなりデータ損失の問題の生じる場合にその使用可能
なバッファメモリが容易に拡張されうることを意味する
。メモリモジュール間の極めて短い切換え時間により、
１つのメモリモジュールが満杯となりパケットが他のメ
モリモジュールに読込まれるべきときのデータサイクル
は失われることがない。
ドは極めて少くそしてしかも使用可能なメモリスペース
のすべてを完全に利用することができる。そのモジュラ
ー構成は、任意の１つのスイッチが連続的にオーバロー
ドとなりデータ損失の問題の生じる場合にその使用可能
なバッファメモリが容易に拡張されうることを意味する
。メモリモジュール間の極めて短い切換え時間により、
１つのメモリモジュールが満杯となりパケットが他のメ
モリモジュールに読込まれるべきときのデータサイクル
は失われることがない。
【０００７】
【実施例】モジュールバッファメモリの１つのメモリモ
ジュールの構造を図１に示す。このバッファメモリに記
憶されるデータパケットはｋ個の入力ライン１０ａ−ｋ
の内の１つに入力される。これら入力ライン１０ａ−ｋ
の夫々は１つのメモリモジュールのモジュール入力ライ
ン１５ａ−ｋに接続するのみならず、ライン２０ａ−ｋ
を介して他のメモリモジュールにも接続する。同様に、
スイッチ出力ライン１６０ａ−ｋはライン１７０ａ−ｋ
を介して他のメモリモジュールに接続する。これを図２
に示す。
ジュールの構造を図１に示す。このバッファメモリに記
憶されるデータパケットはｋ個の入力ライン１０ａ−ｋ
の内の１つに入力される。これら入力ライン１０ａ−ｋ
の夫々は１つのメモリモジュールのモジュール入力ライ
ン１５ａ−ｋに接続するのみならず、ライン２０ａ−ｋ
を介して他のメモリモジュールにも接続する。同様に、
スイッチ出力ライン１６０ａ−ｋはライン１７０ａ−ｋ
を介して他のメモリモジュールに接続する。これを図２
に示す。
【０００８】入力ライン１５ａ−ｋの夫々はＡＮＤゲー
ト６０ａ−ｋの１方の入力端子に接続され、その他方の
入力は第１セットーリセットラッチ５０の出力に接続す
る。ＡＮＤゲート６０ａ−ｋの出力端子はマルチ入力‐
マルチ出力ポートメモリ９０のデータ入力端子に接続さ
れる。このメモリ９０は周知のマルチポートメモリで形
成することができる。メモリコントローラ１００がこの
メモリの内部構造を制御し、そして出力されるべきすべ
てのデータパケットを記憶するためにメモリ９０内に出
力バッファ待ち行列８０ａ−ｋをつくる。出力バッファ
待ち行列８０ａ−ｋの夫々はメモリ出力ライン１５５ａ
−ｋを有し、これはＡＮＤゲート１５０ａ−ｋに接続さ
れ、これらゲートの他の入力は第２セットーリセットラ
ッチ１４０ａ−ｋからのものである。スイッチ出力ライ
ン１６０ａ−ｋはＡＮＤゲート１５０ａ−ｋの出力に接
続される。第１ラッチ５０のセット入力はライン３０を
介して前のメモリモジュールのライン４０に接続される
。同様に。第２ラッチ１４０ａ−ｋのセット入力はライ
ン１２０ａ−ｋを介して前のモジュールの対応するライ
ン１３０ａ−ｋに接続される。
ト６０ａ−ｋの１方の入力端子に接続され、その他方の
入力は第１セットーリセットラッチ５０の出力に接続す
る。ＡＮＤゲート６０ａ−ｋの出力端子はマルチ入力‐
マルチ出力ポートメモリ９０のデータ入力端子に接続さ
れる。このメモリ９０は周知のマルチポートメモリで形
成することができる。メモリコントローラ１００がこの
メモリの内部構造を制御し、そして出力されるべきすべ
てのデータパケットを記憶するためにメモリ９０内に出
力バッファ待ち行列８０ａ−ｋをつくる。出力バッファ
待ち行列８０ａ−ｋの夫々はメモリ出力ライン１５５ａ
−ｋを有し、これはＡＮＤゲート１５０ａ−ｋに接続さ
れ、これらゲートの他の入力は第２セットーリセットラ
ッチ１４０ａ−ｋからのものである。スイッチ出力ライ
ン１６０ａ−ｋはＡＮＤゲート１５０ａ−ｋの出力に接
続される。第１ラッチ５０のセット入力はライン３０を
介して前のメモリモジュールのライン４０に接続される
。同様に。第２ラッチ１４０ａ−ｋのセット入力はライ
ン１２０ａ−ｋを介して前のモジュールの対応するライ
ン１３０ａ−ｋに接続される。
【０００９】これらメモリモジュールのいずれも現在は
パケットを記憶しておらず、しかも入来する第１パケッ
トが図１のモジュールに記憶されているものとしてこの
メモリモジュールの動作を説明する。この場合、ラッチ
５０はセットされそしてＡＮＤゲート６０ａ−ｋは入力
ライン１５ａ−ｋ上のパケットを直接メモリ９０に通す
。メモリコントローラ１００はこれら入来パケットが正
しい出力待ち行列８０ａ−ｋ内に確実に置かれ、それか
らメモリ出力ライン１５５ａ−ｋに沿ってＡＮＤゲート
１５０ａ−ｋに出力される。更に他のモジュールからも
現在はパケットが出力されておらずそしてラッチ１４０
ａ−ｋのすべてがセットされているものとする。従って
データパケットはＡＮＤゲート１５０ａ−ｋを通り、ス
イッチ出力ライン１６０ａ−ｋに出力される。
パケットを記憶しておらず、しかも入来する第１パケッ
トが図１のモジュールに記憶されているものとしてこの
メモリモジュールの動作を説明する。この場合、ラッチ
５０はセットされそしてＡＮＤゲート６０ａ−ｋは入力
ライン１５ａ−ｋ上のパケットを直接メモリ９０に通す
。メモリコントローラ１００はこれら入来パケットが正
しい出力待ち行列８０ａ−ｋ内に確実に置かれ、それか
らメモリ出力ライン１５５ａ−ｋに沿ってＡＮＤゲート
１５０ａ−ｋに出力される。更に他のモジュールからも
現在はパケットが出力されておらずそしてラッチ１４０
ａ−ｋのすべてがセットされているものとする。従って
データパケットはＡＮＤゲート１５０ａ−ｋを通り、ス
イッチ出力ライン１６０ａ−ｋに出力される。
【００１０】データパケットはメモリが満杯となるまで
入力ライン１０ａ−ｋに沿ってそのメモリに入力され続
ける。これはメモリコントローラ１００がＭＥＭ＿ＦＵ
ＬＬ信号を出すことにより知らされる。データ損失を防
ぐためにこのＭＥＭ＿ＦＵＬＬ信号はメモリ８０内の使
用可能なメモリセルの数がｋより小さくなったとき送ら
れる。このｋは１つのパケットがすべての入力端に入る
最悪のケースに適合するに必要なものである。これは時
間的にほぼ１サイクル前に検出でき、それ故次のモジュ
ールはサービスの準備に充分な時間をもつことができる
。
入力ライン１０ａ−ｋに沿ってそのメモリに入力され続
ける。これはメモリコントローラ１００がＭＥＭ＿ＦＵ
ＬＬ信号を出すことにより知らされる。データ損失を防
ぐためにこのＭＥＭ＿ＦＵＬＬ信号はメモリ８０内の使
用可能なメモリセルの数がｋより小さくなったとき送ら
れる。このｋは１つのパケットがすべての入力端に入る
最悪のケースに適合するに必要なものである。これは時
間的にほぼ１サイクル前に検出でき、それ故次のモジュ
ールはサービスの準備に充分な時間をもつことができる
。
【００１１】ＭＥＭ＿ＦＵＬＬ信号はライン４５を介し
て第１ラッチ４５０のリセット入力に入り、そこで第１
ラッチ５０をリセットしそしてＡＮＤゲート６０ａ−ｋ
をパケットが通らないようにする。ラッチ５０はパケッ
トがＡＮＤゲート６０ａ−ｋを通っているときにのみセ
ットまたはリセットされる。このように、ライン１５ａ
−ｋはパケットが入っている間にオフとなることはでき
ない。またこれはライン４０に沿って次のメモリモジュ
ールの第１ラッチ５０をセットする。次のメモリモジュ
ール内の第１ラッチ５０がセットされると、データは次
のメモリモジュールの対応するＡＮＤゲート６０ａ−ｋ
を通り、そのモジュールのメモリ９０に入る。それ故、
入力ライン１０ａ−ｋに入るパケットはライン２０ａ−
ｋに沿って次のモジュールへ転送される。夫々のメモリ
モジュール内の第１ラッチ５０のみが一時にセットしう
るから、そべてのパケットは１つのメモリモジュールの
メモリ９０にのみ読込まれる。
て第１ラッチ４５０のリセット入力に入り、そこで第１
ラッチ５０をリセットしそしてＡＮＤゲート６０ａ−ｋ
をパケットが通らないようにする。ラッチ５０はパケッ
トがＡＮＤゲート６０ａ−ｋを通っているときにのみセ
ットまたはリセットされる。このように、ライン１５ａ
−ｋはパケットが入っている間にオフとなることはでき
ない。またこれはライン４０に沿って次のメモリモジュ
ールの第１ラッチ５０をセットする。次のメモリモジュ
ール内の第１ラッチ５０がセットされると、データは次
のメモリモジュールの対応するＡＮＤゲート６０ａ−ｋ
を通り、そのモジュールのメモリ９０に入る。それ故、
入力ライン１０ａ−ｋに入るパケットはライン２０ａ−
ｋに沿って次のモジュールへ転送される。夫々のメモリ
モジュール内の第１ラッチ５０のみが一時にセットしう
るから、そべてのパケットは１つのメモリモジュールの
メモリ９０にのみ読込まれる。
【００１２】ＭＥＭ＿ＦＵＬＬ信号はライン３５を介し
てマーカ回路７０に入る。この回路はマーカを出力待ち
行列８０ａ−ｋのすべてに置いてそのメモリモジュール
内の待ち行列記憶の終了を信号で知らせ、そしてその待
ち行列のそれ以上のエントリが以降のモジュールにある
ことを示す。これらマーカは通常の出力待ち行列エント
リと同様に処理される特殊なコードワードで形成しても
よくあるいは通常の待ち行列エントリ内の保存ビットに
記憶されるべき単一ビットとしても形成しうる。
てマーカ回路７０に入る。この回路はマーカを出力待ち
行列８０ａ−ｋのすべてに置いてそのメモリモジュール
内の待ち行列記憶の終了を信号で知らせ、そしてその待
ち行列のそれ以上のエントリが以降のモジュールにある
ことを示す。これらマーカは通常の出力待ち行列エント
リと同様に処理される特殊なコードワードで形成しても
よくあるいは通常の待ち行列エントリ内の保存ビットに
記憶されるべき単一ビットとしても形成しうる。
【００１３】メモリ９０内に含まれる出力バッファ待ち
行列８０ａ−ｋからスイッチの出力へのエントリの読出
しには、パケットがＡＮＤゲート１５０ａ−ｋを通過し
うるように第２ラッチ１４０ａ−ｋをセットする必要が
ある。マーカの存在が検出器１１０ａ−ｋの１個により
検出されるまで、これらラッチはセットされたままであ
りそして出力バッファ待ち行列８０ａ−ｋからのエント
リは出力ライン１６０ａ−ｋを切換えるためにメモリ出
力ライン１５５ａ−ｋに沿って出力される。第２ラッチ
１４０ａ−ｋはパケットがメモリ出力ライン１５５ａ−
ｋに沿って出力されている間にはセットまたはリセット
され得ない。夫々の検出器１１０ａ−ｋは、現メモリモ
ジュール内の各第２ラッチ１４０ａ−ｋをリセットしそ
してライン１３０ａ−ｋを介して次のメモリモジュール
の対応する第２ラッチ１４０ａ−ｋをセットする信号を
送る。このように、記憶されたパケットはスイッチ出力
ライン１６０ａ−ｋに出力されつづけるが、このときこ
れらは次のメモリモジュールの対応する出力バッファ待
ち行列８０ａ−ｋから来る。パケットは出力バッファ待
ち行列８０ａ−ｋの夫々から他の出力バッファ待ち行列
８０ａ−ｋのすべてとは無関係に読出される。出力バッ
ファ待ち行列８０ａ−ｋの内の１個におけるマーカの検
出により、第２ラッチ１４０ａ−ｋのすべてがリセット
されるのではなく、特定の出力バッファ待ち行列８０ａ
−ｋに接続されるラッチ１４０ａ−ｋをリセットするだ
けである。このようにライン１６０ａ−ｋ上で読出され
るパケットは異なるメモリモジュールに記憶されること
が可能となる。
行列８０ａ−ｋからスイッチの出力へのエントリの読出
しには、パケットがＡＮＤゲート１５０ａ−ｋを通過し
うるように第２ラッチ１４０ａ−ｋをセットする必要が
ある。マーカの存在が検出器１１０ａ−ｋの１個により
検出されるまで、これらラッチはセットされたままであ
りそして出力バッファ待ち行列８０ａ−ｋからのエント
リは出力ライン１６０ａ−ｋを切換えるためにメモリ出
力ライン１５５ａ−ｋに沿って出力される。第２ラッチ
１４０ａ−ｋはパケットがメモリ出力ライン１５５ａ−
ｋに沿って出力されている間にはセットまたはリセット
され得ない。夫々の検出器１１０ａ−ｋは、現メモリモ
ジュール内の各第２ラッチ１４０ａ−ｋをリセットしそ
してライン１３０ａ−ｋを介して次のメモリモジュール
の対応する第２ラッチ１４０ａ−ｋをセットする信号を
送る。このように、記憶されたパケットはスイッチ出力
ライン１６０ａ−ｋに出力されつづけるが、このときこ
れらは次のメモリモジュールの対応する出力バッファ待
ち行列８０ａ−ｋから来る。パケットは出力バッファ待
ち行列８０ａ−ｋの夫々から他の出力バッファ待ち行列
８０ａ−ｋのすべてとは無関係に読出される。出力バッ
ファ待ち行列８０ａ−ｋの内の１個におけるマーカの検
出により、第２ラッチ１４０ａ−ｋのすべてがリセット
されるのではなく、特定の出力バッファ待ち行列８０ａ
−ｋに接続されるラッチ１４０ａ−ｋをリセットするだ
けである。このようにライン１６０ａ−ｋ上で読出され
るパケットは異なるメモリモジュールに記憶されること
が可能となる。
【００１４】図２は上記多数のメモリモジュールを接続
する方法を示す。図１で用いた参照番号を、第１モジュ
ールについて２００、第２モジュールについて４００、
ｎ番目のモジュールについて６００を加算した数字とす
る点を除き図２の対応するエレメントに付してある。図
２において、入力２１０ａ−ｋはライン２２０ａ−ｋを
介してすべてのモジュールの入力ライン２１５ａ−ｋ、
４１５ａ−ｋ、６１５ａ−ｋに接続される。同様に、出
力ライン３５５ａ−ｋ、５５５ａ−ｋ、７５５ａ−ｋは
ＡＮＤゲート３５０ａ−ｋ、５５０ａ−ｋ、７５０ａ−
ｋを通じて、ライン３７０ａ−ｋを介してスイッチ出力
ライン３６０ａ−ｋに接続される。信号ＭＥＭ＿ＦＵＬ
Ｌ信号を送信するライン２４０、４４０、６４０はライ
ン４３０、６３０、２３０を介して以降のメモリモジュ
ールの第１ラッチ４５０、６５０、２５０に夫々接続す
る。出力バッファ待ち行列２８０ａ−ｋ、４８０ａ−ｋ
、６８０ａ−ｋのマーカの検出を示すための信号を送信
するライン３３０ａ−ｋ、５３０ａ−ｋ、７３０ａ−ｋ
は次のメモリモジュールのラッチ５４０ａ−ｋ、７４０
ａ−ｋ、３４０ａ−ｋに夫々接続する。
する方法を示す。図１で用いた参照番号を、第１モジュ
ールについて２００、第２モジュールについて４００、
ｎ番目のモジュールについて６００を加算した数字とす
る点を除き図２の対応するエレメントに付してある。図
２において、入力２１０ａ−ｋはライン２２０ａ−ｋを
介してすべてのモジュールの入力ライン２１５ａ−ｋ、
４１５ａ−ｋ、６１５ａ−ｋに接続される。同様に、出
力ライン３５５ａ−ｋ、５５５ａ−ｋ、７５５ａ−ｋは
ＡＮＤゲート３５０ａ−ｋ、５５０ａ−ｋ、７５０ａ−
ｋを通じて、ライン３７０ａ−ｋを介してスイッチ出力
ライン３６０ａ−ｋに接続される。信号ＭＥＭ＿ＦＵＬ
Ｌ信号を送信するライン２４０、４４０、６４０はライ
ン４３０、６３０、２３０を介して以降のメモリモジュ
ールの第１ラッチ４５０、６５０、２５０に夫々接続す
る。出力バッファ待ち行列２８０ａ−ｋ、４８０ａ−ｋ
、６８０ａ−ｋのマーカの検出を示すための信号を送信
するライン３３０ａ−ｋ、５３０ａ−ｋ、７３０ａ−ｋ
は次のメモリモジュールのラッチ５４０ａ−ｋ、７４０
ａ−ｋ、３４０ａ−ｋに夫々接続する。
【００１５】これらモジュールは、図２の下部に示す最
終のメモリモジュールが図２の上部に示すメモリモジュ
ールに接続されるようにリング状に接続される。かくし
てｎ番目のメモリモジュールのメモリ６９０が満杯であ
ることをメモリコントローラ７００が検出すると、ＭＥ
Ｍ＿ＦＵＬＬ信号がライン６４０と２３０に沿って第１
メモリモジュールの第１ラッチ２５０の入力に送られそ
して以降のパケットが第１モジュールの出力待ち行列２
８０ａ−ｋに記憶される。メモリモジュールが出力待ち
行列２８０ａ−ｋ内に新しいエントリを受けることがで
きるようになる前にそのモジュールを完全に空にする必
要はない。すなわち、新しいエントリのすべてが出力待
ち行列２８０ａ−ｋ内のマーカの後に置かれるからであ
る。これらマーカは新エントリから古いエントリを分け
そして前述のように、以降のメモリモジュールの出力待
ち行列４８０ａ−ｋ、６８０ａ−ｋの古いエントリが現
メモリモジュールの出力待ち行列２８０ａ−ｋの新しい
エントリの前に読出されるようにする。
終のメモリモジュールが図２の上部に示すメモリモジュ
ールに接続されるようにリング状に接続される。かくし
てｎ番目のメモリモジュールのメモリ６９０が満杯であ
ることをメモリコントローラ７００が検出すると、ＭＥ
Ｍ＿ＦＵＬＬ信号がライン６４０と２３０に沿って第１
メモリモジュールの第１ラッチ２５０の入力に送られそ
して以降のパケットが第１モジュールの出力待ち行列２
８０ａ−ｋに記憶される。メモリモジュールが出力待ち
行列２８０ａ−ｋ内に新しいエントリを受けることがで
きるようになる前にそのモジュールを完全に空にする必
要はない。すなわち、新しいエントリのすべてが出力待
ち行列２８０ａ−ｋ内のマーカの後に置かれるからであ
る。これらマーカは新エントリから古いエントリを分け
そして前述のように、以降のメモリモジュールの出力待
ち行列４８０ａ−ｋ、６８０ａ−ｋの古いエントリが現
メモリモジュールの出力待ち行列２８０ａ−ｋの新しい
エントリの前に読出されるようにする。
【００１６】同様に、ｎ番目のメモリモジュールの出力
待ち行列６８０ａ−ｋの１つに記憶されたパケットのす
べてが読出されそして検出器７１０ａ−ｋの内の適当な
１個によりマーカが検出されると、第１メモリモジュー
ル内の第２ラッチ３４０ａ−ｋの対応する１個をセット
して出力待ち行列２８０ａ−ｋの夫々から次のパケット
を読出しうるようにするための信号がライン７３０ａ−
ｋの内の１本を介して送られる。図２においては例とし
て３個のメモリモジュールを示しているが、その数は任
意である。
待ち行列６８０ａ−ｋの１つに記憶されたパケットのす
べてが読出されそして検出器７１０ａ−ｋの内の適当な
１個によりマーカが検出されると、第１メモリモジュー
ル内の第２ラッチ３４０ａ−ｋの対応する１個をセット
して出力待ち行列２８０ａ−ｋの夫々から次のパケット
を読出しうるようにするための信号がライン７３０ａ−
ｋの内の１本を介して送られる。図２においては例とし
て３個のメモリモジュールを示しているが、その数は任
意である。
【図１】本発明によるモジューラ形バッファメモリの１
個のメモリモジュールの構造を示す図。
個のメモリモジュールの構造を示す図。
【図２】図１のメモリモジュールの接続を示す図。
１０ａ−ｋ，１５ａ−ｋ 入力ライン３０，３５，４
０ ライン ５０ 第１セットーリセットラッチ ６０ａ−ｋ，１５０ａ−ｋ ＡＮＤゲート７０ マ
ーカ回路 ８０ａ−ｋ 出力待ち行列 ９０ メモリ １００ メモリコントローラ １１０ａ−ｋ 検出器 １４０ａ−ｋ 第２セットーリセットラッチ１５５ａ
−ｋ メモリ出力ライン １６０ａ−ｋ スイッチ出力ライン
０ ライン ５０ 第１セットーリセットラッチ ６０ａ−ｋ，１５０ａ−ｋ ＡＮＤゲート７０ マ
ーカ回路 ８０ａ−ｋ 出力待ち行列 ９０ メモリ １００ メモリコントローラ １１０ａ−ｋ 検出器 １４０ａ−ｋ 第２セットーリセットラッチ１５５ａ
−ｋ メモリ出力ライン １６０ａ−ｋ スイッチ出力ライン
Claims (6)
- 【請求項１】データ入力用の入力ライン（１０ａ−ｋ）
と、データ出力用のスイッチ出力ライン（１６０ａ−ｋ
）と、夫々がメモリ制御手段（１００）により制御され
る１個のメモリ（９０）を含む複数のメモリモジュール
とを備え、前記メモリ（９０）の夫々が前記入力ライン
（１０ａ−ｋ）のすべてにそして前記スイッチ出力ライ
ン（１６０ａ−ｋ）のすべてに個々に接続されることを
特徴とするデータパケットスイッチに使用されるバッフ
ァメモリ。 - 【請求項２】前記メモリ（９０）は一連の可変サイズの
出力バッファ待ち行列（８０ａ−ｋ）を内部的に与え、
夫々の待ち行列が前記スイッチ出力ライン（１６０ａ−
ｋ）の１個に接続されることを特徴する請求項１記載の
バッファメモリ。 - 【請求項３】前記入力ライン（１０ａ−ｋ）はＡＮＤゲ
ート（６０ａ−ｋ）を介して前記メモリ（９０）に接続
され、前記ゲートの他方の入力は第１ラッチ（５０）の
出力に接続され、この第１ラッチ（５０）は前段のメモ
リモジュールの前記メモリ制御手段（１００）から送ら
れるＭＥＭ＿ＦＵＬＬ信号によりセットされそして同一
のメモリモジュールの前記メモリ制御手段（１００）か
ら送られるＭＥＭ＿ＦＵＬＬ信号によりリセットされ、
上記ＭＥＭ＿ＦＵＬＬ信号は上記メモリ（９０）がそれ
以上データを記憶しえないことを示すことを特徴とする
請求項１および２に記載のバッファメモリ。 - 【請求項４】前記メモリモジュールの夫々は、前記ＭＥ
Ｍ＿ＦＵＬＬ信号が前記メモリ制御手段（１００）から
受信されるときマーカを前記出力バッファ待ち行列（８
０ａ−ｋ）の夫々に挿入するマーカ回路（７０）を備え
ていることを特徴とする請求項３記載のバッファメモリ
。 - 【請求項５】前記出力バッファ待ち行列（８０ａ−ｋ）
の夫々は前記ＡＮＤゲート（１５０ａ−ｋ）の１つを介
して前記スイッチ出力ライン（１６０ａ−ｋ）の対応す
る１個に接続され、このゲートの他方の入力は一連の第
２ラッチ（１４０ａ−ｋ）の出力から入るようになって
おり、一連の検出器（１１０ａ−ｋ）も前記出力バッフ
ァ待ち行列（８０ａ−ｋ）に接続され、前記出力バッフ
ァ待ち行列（８０ａ−ｋ）の内の１個に前記マーカの１
個があることを前記検出器が検出するとき同一のメモリ
モジュール内の前記第２ラッチ（１４０ａ−ｋ）の夫々
を前記バッファ待ち行列がリセットするようになってお
り、そして前記出力バッファ待ち行列は次のメモリモジ
ュール内の前記第２ラッチ（１４０ａ−ｋ）の夫々をセ
ットすることを特徴とする請求項４記載のバッファメモ
リ。 - 【請求項６】前記メモリモジュールの数は任意であるこ
とを特徴とする請求項１乃至５のいずれかに記載のバッ
ファメモリ。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| SE90811014.1 | 1990-12-20 | ||
| EP90811014A EP0492026B1 (en) | 1990-12-20 | 1990-12-20 | Modular buffer memory for packet switched network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04292038A true JPH04292038A (ja) | 1992-10-16 |
| JPH063935B2 JPH063935B2 (ja) | 1994-01-12 |
Family
ID=8205976
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP24830391A Expired - Lifetime JPH063935B2 (ja) | 1990-12-20 | 1991-09-02 | バッファメモリ |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5574885A (ja) |
| EP (1) | EP0492026B1 (ja) |
| JP (1) | JPH063935B2 (ja) |
| DE (1) | DE69021213T2 (ja) |
Families Citing this family (26)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5774745A (en) * | 1995-03-31 | 1998-06-30 | Cirrus Logic, Inc. | Method and apparatus for writing and reading entries in an event status queue of a host memory |
| GB9510932D0 (en) * | 1995-05-31 | 1995-07-26 | 3Com Ireland | Adjustable fifo-based memory scheme |
| EP0748087A1 (en) | 1995-06-09 | 1996-12-11 | International Business Machines Corporation | Access control system for a shared buffer |
| US5757799A (en) * | 1996-01-16 | 1998-05-26 | The Boeing Company | High speed packet switch |
| DE69633910T2 (de) * | 1996-02-26 | 2005-05-25 | Freescale Semiconductors, Inc., Austin | ATM-Übertragungsschicht und Verfahren zum Betrieb eines Übertragungsschalters |
| US5946318A (en) * | 1997-03-21 | 1999-08-31 | International Business Machines Corporation | Method and apparatus for processing and packetizing data from a data stream |
| US6021440A (en) * | 1997-05-08 | 2000-02-01 | International Business Machines Corporation | Method and apparatus for coalescing and packetizing data |
| FR2783118B1 (fr) * | 1998-09-08 | 2004-05-28 | Bull Sa | Routeur pour acheminer des paquets de donnees |
| US6625159B1 (en) * | 1998-11-30 | 2003-09-23 | Hewlett-Packard Development Company, L.P. | Nonblocking and fair queuing switching method and shared memory packet switch |
| US6731645B1 (en) | 2000-02-29 | 2004-05-04 | International Business Machines Corporation | Methods, switches, systems, and computer program products for fair transmission of data received at multiple inputs in the order received in a queued memory switch |
| US6999464B2 (en) * | 2001-08-28 | 2006-02-14 | Axiowave Networks, Inc. | Method of scalable non-blocking shared memory output-buffered switching of variable length data packets from pluralities of ports at full line rate, and apparatus therefor |
| DE102004026248A1 (de) * | 2004-05-28 | 2005-12-29 | Infineon Technologies Ag | Halbleiter-Bauelement-Test-Verfahren, insbesondere für ein System mit mehreren jeweils ein Daten-Zwischenspeicher-Bauelement aufweisenden Modulen, sowie Test-Modul zur Verwendung bei einem derartigen Verfahren |
| US8644140B2 (en) * | 2009-09-09 | 2014-02-04 | Mellanox Technologies Ltd. | Data switch with shared port buffers |
| US8699491B2 (en) | 2011-07-25 | 2014-04-15 | Mellanox Technologies Ltd. | Network element with shared buffers |
| US9582440B2 (en) | 2013-02-10 | 2017-02-28 | Mellanox Technologies Ltd. | Credit based low-latency arbitration with data transfer |
| US8989011B2 (en) | 2013-03-14 | 2015-03-24 | Mellanox Technologies Ltd. | Communication over multiple virtual lanes using a shared buffer |
| US9641465B1 (en) | 2013-08-22 | 2017-05-02 | Mellanox Technologies, Ltd | Packet switch with reduced latency |
| US9548960B2 (en) | 2013-10-06 | 2017-01-17 | Mellanox Technologies Ltd. | Simplified packet routing |
| US9325641B2 (en) | 2014-03-13 | 2016-04-26 | Mellanox Technologies Ltd. | Buffering schemes for communication over long haul links |
| US9584429B2 (en) | 2014-07-21 | 2017-02-28 | Mellanox Technologies Ltd. | Credit based flow control for long-haul links |
| US10951549B2 (en) | 2019-03-07 | 2021-03-16 | Mellanox Technologies Tlv Ltd. | Reusing switch ports for external buffer network |
| US11470010B2 (en) | 2020-02-06 | 2022-10-11 | Mellanox Technologies, Ltd. | Head-of-queue blocking for multiple lossless queues |
| US11558316B2 (en) | 2021-02-15 | 2023-01-17 | Mellanox Technologies, Ltd. | Zero-copy buffering of traffic of long-haul links |
| US12474833B2 (en) | 2021-11-02 | 2025-11-18 | Mellanox Technologies, Ltd | Queue bandwidth estimation for management of shared buffers and allowing visibility of shared buffer status |
| US11973696B2 (en) | 2022-01-31 | 2024-04-30 | Mellanox Technologies, Ltd. | Allocation of shared reserve memory to queues in a network device |
| US12375404B2 (en) | 2022-08-25 | 2025-07-29 | Mellanox Technologies, Ltd | Flow-based congestion control |
Family Cites Families (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4158235A (en) * | 1977-04-18 | 1979-06-12 | Burroughs Corporation | Multi port time-shared associative buffer storage pool |
| FR2458196A1 (fr) * | 1979-06-01 | 1980-12-26 | Materiel Telephonique | Niveau de commutation d'un operateur pour reseau de commutation de donnees numeriques par paquets |
| JPS6024613B2 (ja) * | 1980-03-10 | 1985-06-13 | 日本電気株式会社 | デ−タ伝送装置 |
| IT1205640B (it) * | 1983-04-06 | 1989-03-23 | Yason Srl | Nuovi composti ad attivita' antiinfiammatoria,procedimento per la loro preparazione e composizioni farmaceutiche che li contengono |
| US4556972A (en) * | 1983-12-27 | 1985-12-03 | At&T Bell Laboratories | Arrangement for routing data packets through a circuit switch |
| US4862461A (en) * | 1987-01-12 | 1989-08-29 | International Business Machines Corp. | Packet switch network protocol |
| US4847812A (en) * | 1986-09-18 | 1989-07-11 | Advanced Micro Devices | FIFO memory device including circuit for generating flag signals |
| EP0291079B1 (en) * | 1987-05-15 | 1994-08-17 | Hitachi, Ltd. | Apparatus for controlling packet switched networks |
| US4839866A (en) * | 1987-05-29 | 1989-06-13 | Texas Instruments Incorporated | Cascadable first-in, first-out memory |
| NL8702672A (nl) * | 1987-11-09 | 1989-06-01 | Philips Nv | Serieel geheugen, alsmede beeldgeheugeninrichting en weergeeftoestel voorzien van een of meer seriele geheugens. |
| US5282201A (en) * | 1987-12-22 | 1994-01-25 | Kendall Square Research Corporation | Dynamic packet routing network |
| SG43795A1 (en) * | 1988-03-31 | 1997-11-14 | At & T Corp | Arrangement for switching concentrated telecommunications packet traffic |
| JPH02117243A (ja) * | 1988-10-27 | 1990-05-01 | Toshiba Corp | パケット通信装置 |
| US4932020A (en) * | 1988-11-14 | 1990-06-05 | At&T Bell Laboratories | Packet switching arrangement including packet retransmission |
| US4991171A (en) * | 1989-09-26 | 1991-02-05 | At&T Bell Laboratories | Broadcast packet switch network |
-
1990
- 1990-12-20 DE DE69021213T patent/DE69021213T2/de not_active Expired - Fee Related
- 1990-12-20 EP EP90811014A patent/EP0492026B1/en not_active Expired - Lifetime
-
1991
- 1991-09-02 JP JP24830391A patent/JPH063935B2/ja not_active Expired - Lifetime
-
1994
- 1994-11-17 US US08/341,467 patent/US5574885A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP0492026A1 (en) | 1992-07-01 |
| DE69021213T2 (de) | 1996-02-29 |
| DE69021213D1 (de) | 1995-08-31 |
| EP0492026B1 (en) | 1995-07-26 |
| US5574885A (en) | 1996-11-12 |
| JPH063935B2 (ja) | 1994-01-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH04292038A (ja) | バッファメモリ | |
| EP0195589B1 (en) | Switching system for transmission of data | |
| US5790545A (en) | Efficient output-request packet switch and method | |
| USRE34528E (en) | Delta network of a cross-point switch | |
| US4788679A (en) | Packet switch with variable data transfer rate links | |
| US4821258A (en) | Crosspoint circuitry for data packet space division switches | |
| EP0492025B1 (en) | High-speed multi-port FIFO buffer circuit | |
| KR960700599A (ko) | 데이타 전달 스위치, 억세스 제어형 비동기식 전달 모드(ATM)스위치 및 정보 셀 흐름 제어 방법(Controlled Access ATM Switch) | |
| JP2533223B2 (ja) | 多段通信ネットワ―ク | |
| HU180481B (en) | Digital switching network of distributed control | |
| JPH05207062A (ja) | パケット交換方式 | |
| DK156319B (da) | Multiport digitalt koblingselement | |
| US5410300A (en) | Distributed crossbar switch architecture | |
| US6601116B1 (en) | Network switch having descriptor cache and method thereof | |
| EP0345891B1 (en) | Switching system for switching packet oriented data as well as circuit oriented data | |
| US5721833A (en) | Push-out of low priority signals from switch buffers | |
| Kang et al. | A high speed ATM switch with common parallel buffers | |
| JP2583679B2 (ja) | セル交換装置 | |
| JPH04291548A (ja) | 高速大容量マトリクス型時間分割ラベル交換方式 | |
| US20030076824A1 (en) | Self-route expandable multi-memory packet switch | |
| JPH02179141A (ja) | スイッチ制御方式 | |
| JPH11163882A (ja) | Ａｔｍスイッチ | |
| JP3075187B2 (ja) | Ａｔｍスイッチ | |
| JP2505021B2 (ja) | 主記憶制御装置 | |
| JPH06216932A (ja) | Ａｔｍスイッチ |