JPH063935B2 - バッファメモリ - Google Patents
バッファメモリInfo
- Publication number
- JPH063935B2 JPH063935B2 JP24830391A JP24830391A JPH063935B2 JP H063935 B2 JPH063935 B2 JP H063935B2 JP 24830391 A JP24830391 A JP 24830391A JP 24830391 A JP24830391 A JP 24830391A JP H063935 B2 JPH063935 B2 JP H063935B2
- Authority
- JP
- Japan
- Prior art keywords
- memory
- output
- buffer
- module
- queue
- 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.)
- Expired - Lifetime
Links
- 230000015654 memory Effects 0.000 title claims description 109
- 239000003550 marker Substances 0.000 claims description 10
- 238000000034 method Methods 0.000 description 3
- 238000001514 detection method Methods 0.000 description 2
- 238000005192 partition Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000000638 solvent extraction Methods 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)
Description
【０００１】
【産業上の利用分野】本発明はパケット交換網に用いる
バッファメモリに関し、特にパケット交換網のスイッチ
内でデータパケットを記憶するために用いられるバッフ
ァメモリの共用方法に関する。
バッファメモリに関し、特にパケット交換網のスイッチ
内でデータパケットを記憶するために用いられるバッフ
ァメモリの共用方法に関する。
【０００２】
【従来の技術】パケット交換網における１つのスイッチ
の機能はすべての入来データパケットを集めそしてそれ
らをそのスイッチの正しい出力ポートに切換えることで
ある。任意の時点で２以上の入力ポートに到着するパケ
ットを１つの同一の出力ポートに向けることがありうる
から、各スイッチ内にバッファメモリを設け、パケット
を一時的に記憶しその間それらが送られるべき出力ポー
トを他のパケットの送信に用いるようにする必要があ
る。そのようなメモリを設けることについてはいくつか
の方法がある。それらの内の最も基本的なものは各出力
ポートに別々に先入れ先出し（ＦＩＦＯ）メモリを設け
たものである。この場合、その出力ポートに向けられる
パケットはまずＦＩＦＯ待ち行列内に置かれ、そこで前
に入ったパケットのすべてが出力されてしまうまで保持
される。しかしながらそのようなシステムは各出力ポー
トに固定メモリサイズを置かなくてはならないのでメモ
リスペースの点で非常に不利である。このように、使用
頻度の高い出力ポートでのＦＩＦＯ待ち行列は容易に満
杯となり、隣りの使用頻度の低い出力ポートでの待ち行
列に充分な使用可能スペースがあるにも拘らず、それ以
上のパケットを記憶できないこととなる。
の機能はすべての入来データパケットを集めそしてそれ
らをそのスイッチの正しい出力ポートに切換えることで
ある。任意の時点で２以上の入力ポートに到着するパケ
ットを１つの同一の出力ポートに向けることがありうる
から、各スイッチ内にバッファメモリを設け、パケット
を一時的に記憶しその間それらが送られるべき出力ポー
トを他のパケットの送信に用いるようにする必要があ
る。そのようなメモリを設けることについてはいくつか
の方法がある。それらの内の最も基本的なものは各出力
ポートに別々に先入れ先出し（ＦＩＦＯ）メモリを設け
たものである。この場合、その出力ポートに向けられる
パケットはまずＦＩＦＯ待ち行列内に置かれ、そこで前
に入ったパケットのすべてが出力されてしまうまで保持
される。しかしながらそのようなシステムは各出力ポー
トに固定メモリサイズを置かなくてはならないのでメモ
リスペースの点で非常に不利である。このように、使用
頻度の高い出力ポートでのＦＩＦＯ待ち行列は容易に満
杯となり、隣りの使用頻度の低い出力ポートでの待ち行
列に充分な使用可能スペースがあるにも拘らず、それ以
上のパケットを記憶できないこととなる。
【０００３】メモリスペースのこの使用効率の低い問題
を解決する１つの手段は単一の共用ランダムアクセスメ
モリ（ＲＡＭ）を使用することである。メモリを各出力
ポートでの使用のために保存されるエリアに分割するた
めの固定区分の代りに、区画境界をフレキシブルにして
別途メモリスペースを必要とするＦＩＦＯ待ち行列がＲ
ＡＭ全体の中の不使用のメモリスペースの利用を行うこ
とができるようにする。これは、頻繁に使用される１個
の出力ポートにおける出力待ち行列が満杯のためにパケ
ットの失われる数は少ないからパケットのスループット
を改善するものであるが、極めて微小なメモリ実現技術
がある動作期間後に細分化されたメモリを再構成するに
必要となる。
を解決する１つの手段は単一の共用ランダムアクセスメ
モリ（ＲＡＭ）を使用することである。メモリを各出力
ポートでの使用のために保存されるエリアに分割するた
めの固定区分の代りに、区画境界をフレキシブルにして
別途メモリスペースを必要とするＦＩＦＯ待ち行列がＲ
ＡＭ全体の中の不使用のメモリスペースの利用を行うこ
とができるようにする。これは、頻繁に使用される１個
の出力ポートにおける出力待ち行列が満杯のためにパケ
ットの失われる数は少ないからパケットのスループット
を改善するものであるが、極めて微小なメモリ実現技術
がある動作期間後に細分化されたメモリを再構成するに
必要となる。
【０００４】
【発明が解決しようとする課題】ＩＢＭ Ｔｅｃｈｎｉ
ｃａｌ Ｄｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ．vo
l.32、NO. 3B、１９８９年８月、pp４８８−４９２に
は、“単一の共用ランダムアクセスメモリからのＦＩＦ
Ｏ待ち行列を管理するためのアルゴリズム”と題名がつ
けられた記事があり、この記事には上記技術に必要な細
分化されたメモリの再構成のための“不要部分の整理”
動作を不要とするアルゴリズムが示されている。この文
献では第１ＲＡＭがすべてのパケットの記憶に用いら
れ、第２ＲＡＭが出力待ち行列内のパケットの位置を示
すポインタの記憶に用いられる。このシステムは、次の
パケットを読取るための第１ＲＡＭ内のアドレスを示す
ために各出力ポートにレジスタを設けている。このレジ
スタは、第２ＲＡＭの、第１ＲＡＭに記憶されるパケッ
トのアドレスと同一のアドレスから出力待ち行列内の次
のパケットが記憶されるアドレスを読取ることによりそ
のパケットが送られている間に更新される。このメモリ
構成は従来のシステムに対し有利であるが、第２メモリ
が余分なハードウエアオーバヘッドを増加する。更に、
第１ＲＡＭのサイズは設計上の点で固定されるから、新
しい出力ポートおよび入力ポートの付加によるシステム
の拡張は、メモリ自体のサイズを増加させることができ
ないためデータ損失が許容される場合にのみ可能であ
る。本発明の目的はデータパケットスイッチを通るデー
タの量が増加するときに複雑なアルゴリズムまたは実質
的なハードウエアの付加を伴わずに容易に拡張しうるデ
ータパケットスイッチで用いるためのＦＩＦＯバッファ
メモリを提供することである。
ｃａｌ Ｄｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ．vo
l.32、NO. 3B、１９８９年８月、pp４８８−４９２に
は、“単一の共用ランダムアクセスメモリからのＦＩＦ
Ｏ待ち行列を管理するためのアルゴリズム”と題名がつ
けられた記事があり、この記事には上記技術に必要な細
分化されたメモリの再構成のための“不要部分の整理”
動作を不要とするアルゴリズムが示されている。この文
献では第１ＲＡＭがすべてのパケットの記憶に用いら
れ、第２ＲＡＭが出力待ち行列内のパケットの位置を示
すポインタの記憶に用いられる。このシステムは、次の
パケットを読取るための第１ＲＡＭ内のアドレスを示す
ために各出力ポートにレジスタを設けている。このレジ
スタは、第２ＲＡＭの、第１ＲＡＭに記憶されるパケッ
トのアドレスと同一のアドレスから出力待ち行列内の次
のパケットが記憶されるアドレスを読取ることによりそ
のパケットが送られている間に更新される。このメモリ
構成は従来のシステムに対し有利であるが、第２メモリ
が余分なハードウエアオーバヘッドを増加する。更に、
第１ＲＡＭのサイズは設計上の点で固定されるから、新
しい出力ポートおよび入力ポートの付加によるシステム
の拡張は、メモリ自体のサイズを増加させることができ
ないためデータ損失が許容される場合にのみ可能であ
る。本発明の目的はデータパケットスイッチを通るデー
タの量が増加するときに複雑なアルゴリズムまたは実質
的なハードウエアの付加を伴わずに容易に拡張しうるデ
ータパケットスイッチで用いるためのＦＩＦＯバッファ
メモリを提供することである。
【０００５】
【課題を解決するための手段】本発明はこの目的を、夫
々がすべての入力ポートからアクセスすることができ、
そしてそこからデータが出力ポートのいずれにも読取る
ことのできる一連のメモリモジュールでこのスイッチの
出力待ち行列をつくることにより達成する。出力ポート
にアドレスされるべきパケットは特定の１つのモジュー
ルが満杯となるまでこれらメモリモジュールの内のその
モジュールに読込まれる。次のデータパケットは他のメ
モリモジュール内の次に使用可能なフリースペースに読
込まれそしてマーカが第１モジュールに置かれて待ち行
列が次に使用可能なモジュールに続くことを示す。１つ
のモジュールからデータを読だすことにより、このマー
カが検出されそしてこのシステムは、このモジュールか
らのデータ読出しを停止し次のモジュールに以降の待ち
行列エントリを見出すことを知ることになる。
々がすべての入力ポートからアクセスすることができ、
そしてそこからデータが出力ポートのいずれにも読取る
ことのできる一連のメモリモジュールでこのスイッチの
出力待ち行列をつくることにより達成する。出力ポート
にアドレスされるべきパケットは特定の１つのモジュー
ルが満杯となるまでこれらメモリモジュールの内のその
モジュールに読込まれる。次のデータパケットは他のメ
モリモジュール内の次に使用可能なフリースペースに読
込まれそしてマーカが第１モジュールに置かれて待ち行
列が次に使用可能なモジュールに続くことを示す。１つ
のモジュールからデータを読だすことにより、このマー
カが検出されそしてこのシステムは、このモジュールか
らのデータ読出しを停止し次のモジュールに以降の待ち
行列エントリを見出すことを知ることになる。
【０００６】本発明では付加ハードウエアオーバーヘッ
ドは極めて少くそしてしかも使用可能なメモリスペース
のすべてを完全に利用することができる。そのモジュラ
ー構成は、任意の１つのスイッチが連続的にオーバロー
ドとなりデータ損失の問題の生じる場合にその使用可能
なバッファメモリが容易に拡張されうることを意味す
る。メモリモジュール間の極めて短い切換え時間によ
り、１つのメモリモジュールが満杯となりパケットが他
のメモリモジュールに読込まれるべきときのデータサイ
クルは失われることがない。
ドは極めて少くそしてしかも使用可能なメモリスペース
のすべてを完全に利用することができる。そのモジュラ
ー構成は、任意の１つのスイッチが連続的にオーバロー
ドとなりデータ損失の問題の生じる場合にその使用可能
なバッファメモリが容易に拡張されうることを意味す
る。メモリモジュール間の極めて短い切換え時間によ
り、１つのメモリモジュールが満杯となりパケットが他
のメモリモジュールに読込まれるべきときのデータサイ
クルは失われることがない。
【０００７】
【実施例】モジュールバッファメモリの１つのメモリモ
ジュールの構造を図１に示す。このバッファメモリに記
憶されるデータパケットはｋ個の入力ライン１０ａ−ｋ
の内の１つに入力される。これら入力ライン１０ａ−ｋ
の夫々は１つのメモリモジュールのモジュール入力ライ
ン１５ａ−ｋに接続するのみならず、ライン２０ａ−ｋ
を介して他のメモリモジュールにも接続する。同様に、
スイッチ出力ライン１６０ａ−ｋはライン１７０ａ−ｋ
を介して他のメモリモジュールに接続する。これを図２
に示す。
ジュールの構造を図１に示す。このバッファメモリに記
憶されるデータパケットはｋ個の入力ライン１０ａ−ｋ
の内の１つに入力される。これら入力ライン１０ａ−ｋ
の夫々は１つのメモリモジュールのモジュール入力ライ
ン１５ａ−ｋに接続するのみならず、ライン２０ａ−ｋ
を介して他のメモリモジュールにも接続する。同様に、
スイッチ出力ライン１６０ａ−ｋはライン１７０ａ−ｋ
を介して他のメモリモジュールに接続する。これを図２
に示す。
【０００８】入力ライン１５ａ−ｋの夫々はＡＮＤゲー
ト６０ａ−ｋの１方の入力端子に接続され、その他方の
入力は第１セットーリセットラッチ５０の出力に接続す
る。ＡＮＤゲート６０ａ−ｋの出力端子はマルチ入力‐
マルチ出力ポートメモリ９０のデータ入力端子に接続さ
れる。このメモリ９０は周知のマルチポートメモリで形
成することができる。メモリコントローラ１００がこの
メモリの内部構造を制御し、そして出力されるべきすべ
てのデータパケットを記憶するためにメモリ９０内に出
力バッファ待ち行列８０ａ−ｋをつくる。出力バッファ
待ち行列８０ａ−ｋの夫々はメモリ出力ライン１５５
ａ−ｋを有し、これはＡＮＤゲート１５０ａ−ｋに接続
され、これらゲートの他の入力は第２セットーリセット
ラッチ１４０ａ−ｋからのものである。スイッチ出力ラ
イン１６０ａ−ｋはＡＮＤゲート１５０ａ−ｋの出力に
接続される。第１ラッチ５０のセット入力はライン３０
を介して前のメモリモジュールのライン４０に接続され
る。同様に。第２ラッチ１４０ａ−ｋのセット入力はラ
イン１２０ａ−ｋを介して前のモジュールの対応するラ
イン１３０ａ−ｋに接続される。
ト６０ａ−ｋの１方の入力端子に接続され、その他方の
入力は第１セットーリセットラッチ５０の出力に接続す
る。ＡＮＤゲート６０ａ−ｋの出力端子はマルチ入力‐
マルチ出力ポートメモリ９０のデータ入力端子に接続さ
れる。このメモリ９０は周知のマルチポートメモリで形
成することができる。メモリコントローラ１００がこの
メモリの内部構造を制御し、そして出力されるべきすべ
てのデータパケットを記憶するためにメモリ９０内に出
力バッファ待ち行列８０ａ−ｋをつくる。出力バッファ
待ち行列８０ａ−ｋの夫々はメモリ出力ライン１５５
ａ−ｋを有し、これはＡＮＤゲート１５０ａ−ｋに接続
され、これらゲートの他の入力は第２セットーリセット
ラッチ１４０ａ−ｋからのものである。スイッチ出力ラ
イン１６０ａ−ｋはＡＮＤゲート１５０ａ−ｋの出力に
接続される。第１ラッチ５０のセット入力はライン３０
を介して前のメモリモジュールのライン４０に接続され
る。同様に。第２ラッチ１４０ａ−ｋのセット入力はラ
イン１２０ａ−ｋを介して前のモジュールの対応するラ
イン１３０ａ−ｋに接続される。
【０００９】これらメモリモジュールのいずれも現在は
パケットを記憶しておらず、しかも入来する第１パケッ
トが図１のモジュールに記憶されているものとしてこの
メモリモジュールの動作を説明する。この場合、ラッチ
５０はセットされそしてＡＮＤゲート６０ａ−ｋは入力
ライン１５ａ−ｋ上のパケットを直接メモリ９０に通
す。メモリコントローラ１００はこれら入来パケットが
正しい出力待ち行列８０ａ−ｋ内に確実に置かれ、それ
からメモリ出力ライン１５５ａ−ｋに沿ってＡＮＤゲー
ト１５０ａ−ｋに出力される。更に他のモジュールから
も現在はパケットが出力されておらずそしてラッチ１４
０ａ−ｋのすべてがセットされているものとする。従っ
てデータパケットはＡＮＤゲート１５０ａ−ｋを通り、
スイッチ出力ライン１６０ａ−ｋに出力される。
パケットを記憶しておらず、しかも入来する第１パケッ
トが図１のモジュールに記憶されているものとしてこの
メモリモジュールの動作を説明する。この場合、ラッチ
５０はセットされそしてＡＮＤゲート６０ａ−ｋは入力
ライン１５ａ−ｋ上のパケットを直接メモリ９０に通
す。メモリコントローラ１００はこれら入来パケットが
正しい出力待ち行列８０ａ−ｋ内に確実に置かれ、それ
からメモリ出力ライン１５５ａ−ｋに沿ってＡＮＤゲー
ト１５０ａ−ｋに出力される。更に他のモジュールから
も現在はパケットが出力されておらずそしてラッチ１４
０ａ−ｋのすべてがセットされているものとする。従っ
てデータパケットはＡＮＤゲート１５０ａ−ｋを通り、
スイッチ出力ライン１６０ａ−ｋに出力される。
【００１０】データパケットはメモリが満杯となるまで
入力ライン１０ａ−ｋに沿ってそのメモリに入力され続
ける。これはメモリコントローラ１００がＭＥＭ＿ＦＵ
ＬＬ信号を出すことにより知らされる。データ損失を防
ぐためにこのＭＥＭ＿ＦＵＬＬ信号はメモリ８０内の使
用可能なメモリセルの数がｋより小さくなったとき送ら
れる。このｋは１つのパケットがすべての入力端に入る
最悪のケースに適合するに必要なものである。これは時
間的にほぼ１サイクル前に検出でき、それ故次のモジュ
ールはサービスの準備に充分な時間をもつことができ
る。
入力ライン１０ａ−ｋに沿ってそのメモリに入力され続
ける。これはメモリコントローラ１００がＭＥＭ＿ＦＵ
ＬＬ信号を出すことにより知らされる。データ損失を防
ぐためにこのＭＥＭ＿ＦＵＬＬ信号はメモリ８０内の使
用可能なメモリセルの数がｋより小さくなったとき送ら
れる。このｋは１つのパケットがすべての入力端に入る
最悪のケースに適合するに必要なものである。これは時
間的にほぼ１サイクル前に検出でき、それ故次のモジュ
ールはサービスの準備に充分な時間をもつことができ
る。
【００１１】ＭＥＭ＿ＦＵＬＬ信号はライン４５を介し
て第１ラッチ４５０のリセット入力に入り、そこで第１
ラッチ５０をリセットしそしてＡＮＤゲート６０ａ−ｋ
をパケットが通らないようにする。ラッチ５０はパケッ
トがＡＮＤゲート６０ａ−ｋを通っているときにのみセ
ットまたはリセットされる。このように、ライン１５
ａ−ｋはパケットが入っている間にオフとなることはで
きない。またこれはライン４０に沿って次のメモリモジ
ュールの第１ラッチ５０をセットする。次のメモリモジ
ュール内の第１ラッチ５０がセットされると、データは
次のメモリモジュールの対応するＡＮＤゲート６０
ａ−ｋを通り、そのモジュールのメモリ９０に入る。そ
れ故、入力ライン１０ａ−ｋに入るパケットはライン２
０ａ−ｋに沿って次のモジュールへ転送される。夫々の
メモリモジュール内の第１ラッチ５０のみが一時にセッ
トしうるから、そべてのパケットは１つのメモリモジュ
ールのメモリ９０にのみ読込まれる。
て第１ラッチ４５０のリセット入力に入り、そこで第１
ラッチ５０をリセットしそしてＡＮＤゲート６０ａ−ｋ
をパケットが通らないようにする。ラッチ５０はパケッ
トがＡＮＤゲート６０ａ−ｋを通っているときにのみセ
ットまたはリセットされる。このように、ライン１５
ａ−ｋはパケットが入っている間にオフとなることはで
きない。またこれはライン４０に沿って次のメモリモジ
ュールの第１ラッチ５０をセットする。次のメモリモジ
ュール内の第１ラッチ５０がセットされると、データは
次のメモリモジュールの対応するＡＮＤゲート６０
ａ−ｋを通り、そのモジュールのメモリ９０に入る。そ
れ故、入力ライン１０ａ−ｋに入るパケットはライン２
０ａ−ｋに沿って次のモジュールへ転送される。夫々の
メモリモジュール内の第１ラッチ５０のみが一時にセッ
トしうるから、そべてのパケットは１つのメモリモジュ
ールのメモリ９０にのみ読込まれる。
【００１２】ＭＥＭ＿ＦＵＬＬ信号はライン３５を介し
てマーカ回路７０に入る。この回路はマーカを出力待ち
行列８０ａ−ｋのすべてに置いてそのメモリモジュール
内の待ち行列記憶の終了を信号で知らせ、そしてその待
ち行列のそれ以上のエントリが以降のモジュールにある
ことを示す。これらマーカは通常の出力待ち行列エント
リと同様に処理される特殊なコードワードで形成しても
よくあるいは通常の待ち行列エントリ内の保存ビットに
記憶されるべき単一ビットとしても形成しうる。
てマーカ回路７０に入る。この回路はマーカを出力待ち
行列８０ａ−ｋのすべてに置いてそのメモリモジュール
内の待ち行列記憶の終了を信号で知らせ、そしてその待
ち行列のそれ以上のエントリが以降のモジュールにある
ことを示す。これらマーカは通常の出力待ち行列エント
リと同様に処理される特殊なコードワードで形成しても
よくあるいは通常の待ち行列エントリ内の保存ビットに
記憶されるべき単一ビットとしても形成しうる。
【００１３】メモリ９０内に含まれる出力バッファ待ち
行列８０ａ−ｋからスイッチの出力へのエントリの読出
しには、パケットがＡＮＤゲート１５０ａ−ｋを通過し
うるように第２ラッチ１４０ａ−ｋをセットする必要が
ある。マーカの存在が検出器１１０ａ−ｋの１個により
検出されるまで、これらラッチはセットされたままであ
りそして出力バッファ待ち行列８０ａ−ｋからのエント
リは出力ライン１６０ａ−ｋを切換えるためにメモリ出
力ライン１５５ａ−ｋに沿って出力される。第２ラッチ
１４０ａ−ｋはパケットがメモリ出力ライン１５５
ａ−ｋに沿って出力されている間にはセットまたはリセ
ットされ得ない。夫々の検出器１１０ａ−ｋは、現メモ
リモジュール内の各第２ラッチ１４０ａ−ｋをリセット
しそしてライン１３０ａ−ｋを介して次のメモリモジュ
ールの対応する第２ラッチ１４０ａ−ｋをセットする信
号を送る。このように、記憶されたパケットはスイッチ
出力ライン１６０ａ−ｋに出力されつづけるが、このと
きこれらは次のメモリモジュールの対応する出力バッフ
ァ待ち行列８０ａ−ｋから来る。パケットは出力バッフ
ァ待ち行列８０ａ−ｋの夫々から他の出力バッファ待ち
行列８０ａ−ｋのすべてとは無関係に読出される。出力
バッファ待ち行列８０ａ−ｋの内の１個におけるマーカ
の検出により、第２ラッチ１４０ａ−ｋのすべてがリセ
ットされるのではなく、特定の出力バッファ待ち行列８
０ａ−ｋに接続されるラッチ１４０ａ−ｋをリセットす
るだけである。このようにライン１６０ａ−ｋ上で読出
されるパケットは異なるメモリモジュールに記憶される
ことが可能となる。
行列８０ａ−ｋからスイッチの出力へのエントリの読出
しには、パケットがＡＮＤゲート１５０ａ−ｋを通過し
うるように第２ラッチ１４０ａ−ｋをセットする必要が
ある。マーカの存在が検出器１１０ａ−ｋの１個により
検出されるまで、これらラッチはセットされたままであ
りそして出力バッファ待ち行列８０ａ−ｋからのエント
リは出力ライン１６０ａ−ｋを切換えるためにメモリ出
力ライン１５５ａ−ｋに沿って出力される。第２ラッチ
１４０ａ−ｋはパケットがメモリ出力ライン１５５
ａ−ｋに沿って出力されている間にはセットまたはリセ
ットされ得ない。夫々の検出器１１０ａ−ｋは、現メモ
リモジュール内の各第２ラッチ１４０ａ−ｋをリセット
しそしてライン１３０ａ−ｋを介して次のメモリモジュ
ールの対応する第２ラッチ１４０ａ−ｋをセットする信
号を送る。このように、記憶されたパケットはスイッチ
出力ライン１６０ａ−ｋに出力されつづけるが、このと
きこれらは次のメモリモジュールの対応する出力バッフ
ァ待ち行列８０ａ−ｋから来る。パケットは出力バッフ
ァ待ち行列８０ａ−ｋの夫々から他の出力バッファ待ち
行列８０ａ−ｋのすべてとは無関係に読出される。出力
バッファ待ち行列８０ａ−ｋの内の１個におけるマーカ
の検出により、第２ラッチ１４０ａ−ｋのすべてがリセ
ットされるのではなく、特定の出力バッファ待ち行列８
０ａ−ｋに接続されるラッチ１４０ａ−ｋをリセットす
るだけである。このようにライン１６０ａ−ｋ上で読出
されるパケットは異なるメモリモジュールに記憶される
ことが可能となる。
【００１４】図２は上記多数のメモリモジュールを接続
する方法を示す。図１で用いた参照番号を、第１モジュ
ールについて２００、第２モジュールについて４００、
ｎ番目のモジュールについて６００を加算した数字とす
る点を除き図２の対応するエレメントに付してある。図
２において、入力２１０ａ−ｋはライン２２０ａ−ｋを
介してすべてのモジュールの入力ライン２１５ａ−ｋ、
４１５ａ−ｋ、６１５ａ−ｋに接続される。同様に、出
力ライン３５５ａ−ｋ、５５５ａ−ｋ、７５５ａ−ｋは
ＡＮＤゲート３５０ａ−ｋ、５５０ａ−ｋ、７５０
ａ−ｋを通じて、ライン３７０ａ−ｋを介してスイッチ
出力ライン３６０ａ−ｋに接続される。信号ＭＥＭ＿Ｆ
ＵＬＬ信号を送信するライン２４０、４４０、６４０は
ライン４３０、６３０、２３０を介して以降のメモリモ
ジュールの第１ラッチ４５０、６５０、２５０に夫々接
続する。出力バッファ待ち行列２８０ａ−ｋ、４８０
ａ−ｋ、６８０ａ−ｋのマーカの検出を示すための信号
を送信するライン３３０ａ−ｋ、５３０ａ−ｋ、７３０
ａ−ｋは次のメモリモジュールのラッチ５４０ａ−ｋ、
７４０ａ−ｋ、３４０ａ−ｋに夫々接続する。
する方法を示す。図１で用いた参照番号を、第１モジュ
ールについて２００、第２モジュールについて４００、
ｎ番目のモジュールについて６００を加算した数字とす
る点を除き図２の対応するエレメントに付してある。図
２において、入力２１０ａ−ｋはライン２２０ａ−ｋを
介してすべてのモジュールの入力ライン２１５ａ−ｋ、
４１５ａ−ｋ、６１５ａ−ｋに接続される。同様に、出
力ライン３５５ａ−ｋ、５５５ａ−ｋ、７５５ａ−ｋは
ＡＮＤゲート３５０ａ−ｋ、５５０ａ−ｋ、７５０
ａ−ｋを通じて、ライン３７０ａ−ｋを介してスイッチ
出力ライン３６０ａ−ｋに接続される。信号ＭＥＭ＿Ｆ
ＵＬＬ信号を送信するライン２４０、４４０、６４０は
ライン４３０、６３０、２３０を介して以降のメモリモ
ジュールの第１ラッチ４５０、６５０、２５０に夫々接
続する。出力バッファ待ち行列２８０ａ−ｋ、４８０
ａ−ｋ、６８０ａ−ｋのマーカの検出を示すための信号
を送信するライン３３０ａ−ｋ、５３０ａ−ｋ、７３０
ａ−ｋは次のメモリモジュールのラッチ５４０ａ−ｋ、
７４０ａ−ｋ、３４０ａ−ｋに夫々接続する。
【００１５】これらモジュールは、図２の下部に示す最
終のメモリモジュールが図２の上部に示すメモリモジュ
ールに接続されるようにリング状に接続される。かくし
てｎ番目のメモリモジュールのメモリ６９０が満杯であ
ることをメモリコントローラ７００が検出すると、ＭＥ
Ｍ＿ＦＵＬＬ信号がライン６４０と２３０に沿って第１
メモリモジュールの第１ラッチ２５０の入力に送られそ
して以降のパケットが第１モジュールの出力待ち行列２
８０ａ−ｋに記憶される。メモリモジュールが出力待ち
行列２８０ａ−ｋ内に新しいエントリを受けることがで
きるようになる前にそのモジュールを完全に空にする必
要はない。すなわち、新しいエントリのすべてが出力待
ち行列２８０ａ−ｋ内のマーカの後に置かれるからであ
る。これらマーカは新エントリから古いエントリを分け
そして前述のように、以降のメモリモジュールの出力待
ち行列４８０ａ−ｋ、６８０ａ−ｋの古いエントリが現
メモリモジュールの出力待ち行列２８０ａ−ｋの新しい
エントリの前に読出されるようにする。
終のメモリモジュールが図２の上部に示すメモリモジュ
ールに接続されるようにリング状に接続される。かくし
てｎ番目のメモリモジュールのメモリ６９０が満杯であ
ることをメモリコントローラ７００が検出すると、ＭＥ
Ｍ＿ＦＵＬＬ信号がライン６４０と２３０に沿って第１
メモリモジュールの第１ラッチ２５０の入力に送られそ
して以降のパケットが第１モジュールの出力待ち行列２
８０ａ−ｋに記憶される。メモリモジュールが出力待ち
行列２８０ａ−ｋ内に新しいエントリを受けることがで
きるようになる前にそのモジュールを完全に空にする必
要はない。すなわち、新しいエントリのすべてが出力待
ち行列２８０ａ−ｋ内のマーカの後に置かれるからであ
る。これらマーカは新エントリから古いエントリを分け
そして前述のように、以降のメモリモジュールの出力待
ち行列４８０ａ−ｋ、６８０ａ−ｋの古いエントリが現
メモリモジュールの出力待ち行列２８０ａ−ｋの新しい
エントリの前に読出されるようにする。
【００１６】同様に、ｎ番目のメモリモジュールの出力
待ち行列６８０ａ−ｋの１つに記憶されたパケットのす
べてが読出されそして検出器７１０ａ−ｋの内の適当な
１個によりマーカが検出されると、第１メモリモジュー
ル内の第２ラッチ３４０ａ−ｋの対応する１個をセット
して出力待ち行列２８０ａ−ｋの夫々から次のパケット
を読出しうるようにするための信号がライン７３０
ａ−ｋの内の１本を介して送られる。図２においては例
として３個のメモリモジュールを示しているが、その数
は任意である。
待ち行列６８０ａ−ｋの１つに記憶されたパケットのす
べてが読出されそして検出器７１０ａ−ｋの内の適当な
１個によりマーカが検出されると、第１メモリモジュー
ル内の第２ラッチ３４０ａ−ｋの対応する１個をセット
して出力待ち行列２８０ａ−ｋの夫々から次のパケット
を読出しうるようにするための信号がライン７３０
ａ−ｋの内の１本を介して送られる。図２においては例
として３個のメモリモジュールを示しているが、その数
は任意である。
【図１】本発明によるモジューラ形バッファメモリの１
個のメモリモジュールの構造を示す図。
個のメモリモジュールの構造を示す図。
【図２】図１のメモリモジュールの接続を示す図。
１０ａ−ｋ，１５ａ−ｋ 入力ライン ３０，３５，４０ ライン ５０ 第１セットーリセットラッチ ６０ａ−ｋ，１５０ａ−ｋ ＡＮＤゲート ７０ マーカ回路 ８０ａ−ｋ 出力待ち行列 ９０ メモリ １００ メモリコントローラ １１０ａ−ｋ 検出器 １４０ａ−ｋ 第２セットーリセットラッチ １５５ａ−ｋ メモリ出力ライン １６０ａ−ｋ スイッチ出力ライン
フロントページの続き (72)発明者 アントニウス、ヨハネス、エングベルセン スイス国リヒテルスビル、シュペールシュ トラーセ、63
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 JPH04292038A (ja) | 1992-10-16 |
| JPH063935B2 true 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 |
| JPH04292038A (ja) | 1992-10-16 |
| EP0492026B1 (en) | 1995-07-26 |
| US5574885A (en) | 1996-11-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH063935B2 (ja) | バッファメモリ | |
| EP0379709B1 (en) | Single-fifo high speed combining switch | |
| US6700894B1 (en) | Method and apparatus for shared buffer packet switching | |
| US6212597B1 (en) | Apparatus for and method of architecturally enhancing the performance of a multi-port internally cached (AMPIC) DRAM array and like | |
| US6636518B1 (en) | Synchronizing source-synchronous links in a switching device | |
| EP0195589B1 (en) | Switching system for transmission of data | |
| EP0492025B1 (en) | High-speed multi-port FIFO buffer circuit | |
| JPS581465B2 (ja) | デ−タ信号の緩衝方式 | |
| US4918597A (en) | Adaptive interface for transferring segmented message between device and microcomputer on line division multiplexed bus | |
| US6904046B2 (en) | Self-route multi-memory packet switch adapted to have an expandable number of input/output ports | |
| US7054969B1 (en) | Apparatus for use in a computer system | |
| US20030133447A1 (en) | Data transmission system with multi-memory packet switch | |
| US6819675B2 (en) | Self-route multi-memory expandable packet switch with overflow processing means | |
| US5617414A (en) | Power reduction in time-space switches | |
| JP3103298B2 (ja) | Ａｔｍスイッチのアドレス生成回路 | |
| JP2853652B2 (ja) | プロセッサ間通信におけるパケット送信方法およびその装置 | |
| US6831920B1 (en) | Memory vacancy management apparatus and line interface unit | |
| US7130302B2 (en) | Self-route expandable multi-memory packet switch | |
| JPH06284453A (ja) | Ａｔｍセルスイッチ | |
| JPH0323026B2 (ja) | ||
| KR960002686B1 (ko) | 이중링 구조의 모듈통신 수신장치 | |
| JPH05173991A (ja) | 並列処理システムとデータ転送方法 | |
| JP2505021B2 (ja) | 主記憶制御装置 | |
| JP3169510B2 (ja) | データ待ち行列装置 | |
| JP2962667B2 (ja) | 非同期転送モード交換システム |