JPH03242064A - パケットスイッチに基づく高容量メモリ - Google Patents

Abstract

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

Description

【発明の詳細な説明】 構成パケットスイッチに関する。

従来技術 パケットスイッチの設計において、同し出力に向けられ
同時に到来した幾つかの入力パケットを受信するスイッ
チの能力が考えられている。効率よくこれを達成するた
め、パケットスイッチの内部構成部品の多くが到来パケ
ットのデータ速度より数倍速く動作しなければならない
．この高速動作を得るのに、パケットスイッチの重要な
部品は通常単一チップに実装されるか、極めて高速で高
価なハードウェア部品を用いた回路基板を用いる。

最近、メモリ構成パケットスイッチが高速パラレルアー
キテクチャを用いて要求される高速動作を得るのに提案
された．そのようなパケットスイッチの１つの例は、Ｉ
ＥＥＥ通信分野ジャーナル（Ｊｏｕｒｎａｌ　ｏｆ　５
ｅｌｅｃｔｅｄ　Ａｒｅａ　ｉｎＣｏｍｍｕｎｉｃａｔ
ｉｏｎｓｌ　、　Ｖｏ１、　６　、　Ｎｏ、　９．１９
８８年■２月、第１５２８〜１５３７頁のＭ　、　Ｄｅ
ｖａｕｌｔ　ｅｔ　ａ１、著の論文’　　Ｔｈｅ　　＋
Ｐｒｅｌｕｄｅ″　ＡＴＤ　　Ｅｘｐｅｒｉｍｅｎｔ　
：　Ａｓｓｅｓｓｍｅｎｔｓａｎｄ　Ｆｕｔｕｅｒ　Ｐ
ｒｏｓｐｅｃｔｓ’　　ｒ序、ＡＴＤ実験：アセスメン
トと将来の展望」に述べられている。そのスイッチでは
、中央メモリの分離された部分が細分化されそしてその
一部がパケットスイッチの出力の各々に割り当てられる
。パケットスイッチに対し入力に到来したパケットは試
験されそしてそのパケットが向けられた特定の出力に関
連するメモＪの部分の次に利用可能なロケーションに置
かれる。スイッチは並行処理によって高速動作が得られ
るが、出力に関連のメモリの部分がオーバフローしない
ことを保証するため各出力に関連の大容量メモリが要求
される。更に、もし到来パケットの宛先が均等に分布さ
れていないならば、メモリの大部分が浪費されているこ
とになる。更に、アドレス処理手段が別なパケットの到
来の間に１つのアドレスを処理していないことを保証す
るために複雑な処理アルゴリズムが要求される。従来技
術に残されている問題は合理的なメモリ容量そして高度
な並行処理を有する高速なメモリ構成パケットスイッチ
を提供することである。

及！目１４要 従来技術の前述の問題は本発明の種々の側面に従って解
決される。本発明のパケットスイッチにおいて、各到来
パケットのＮビットがパケットスイッチの入力ポートか
ら出力ボートへとＮビットパラレルバスによって転送さ
れ、高速ロジックを用いることなくｌ対Ｎの高速化を提
供する。

又、複数のアドレス処理手段即ちルックアップ手段が互
いに独立して動作するよう用いられ、そして１つの実施
例では中心化されたキューが全ての出力ボートで共有さ
れ、各出力に向けられたデータパケットを記憶するため
の個々のキューを用いている従来技術メモリ構成パケッ
トスイッチと比較したとき大きさで一桁以上必要なメモ
リを減少させる。そして、パケットの宛先アドレスがス
イッチに読込まれた後、このアドレスはパケットの残り
が受信されている間に処理される。従って、アドレスは
パケットがスイッチに読込まれる特進に既に処理され遅
延を減らしている。

逢豊女栽１ 第１図は、（１）入力セクション１１７−１１９、（２
）書き込みバス１１３　、（３）読出しバス１２０、（
４）主メモリ１２５、その内部の要素がこの後詳細に説
明されるシステムマネジャ１２１　、　　（６）出力バ
ッファ　１１４−１１６　、　　（７）メモリアドレス
バス１２６　、　Ｊよび（８）制御ライン１２７からな
る本発明のパケットスイッチの実施例のブロック部分を
示している。要素間の接続の多くは明瞭化のため示され
てはいないがこれらの接続の機能は次の記述から明らか
となるであろう、入力セクション１１７かまず入力セク
ション１１８と１１９が同じように動作するという把握
のもと記述される。全体のスイッチの動作はそれから入
力セクション１１７−１１９を参照しつつ記述される。

入力および出力のいずれの数をも使用され得る、つ、ま
りここでは３という数は図示の目的のためにのみ用いら
れているということを理解すべきである。

入力セクション１１７は、（１）入力１０１かもの到来
パケットを受けとるための大力バッファ１０４、（２）
この後詳細に説明するが、各到来パケットに含まれるア
ドレスを受は取るためのアドレスバッファ、（３）その
目的はこの後詳述されるが、ルックアップ手段１２２、
及びこれもこの後記述するがメモリアドレスバッファ１
１０からなる。

動作上は、その各々が宛先アドレスと情報フィールドを
含むデータパケットが入力セクション１１７の入力１０
１に到達し、大力バッファ１０４に連続的にクロックイ
ンされる。それと同時に到着するパケットの宛先アドレ
スはアドレスバッファ１０７にクロックインされる。ア
ドレスの最後のビットがアドレスバッファ１０７にクロ
ックインされた後に、そこに対してパケットが届けられ
る特定の交換出力バッファに対応するアドレスすなわち
出力バッファ１１４　、１１５又は１１６に受信された
アドレスを翻訳する。この翻訳されたアドレスはそれか
らアドレスバッファ１０７に記憶され、このバッファに
前に記憶されたアドレスを置き代える。アドレスバッフ
ァ中のインジケータビットは又セットされ、アドレスバ
ッファ内のアドレスが翻訳されたアドレスであって入力
パケットに到着したアドレスではないことを指示する。

この概念を他の入力セクション１１８−１１９を含むよ
う拡張すると、動作中のランダムな時間において入力セ
クション１１７−１１９と関連するアドレスバッファの
異なったものが翻訳アドレスを記憶し、そこでは各翻訳
アドレスは宛先出力バッファに対応することがわかる。

システムマネジャー１２１は、ｆｌ）例えば、ボール１
、ボール２、およびボール３とそれぞれ印づけられるポ
ーリング手段、（２）主メモリ１２５からのすべての不
使用メモリロケーションのりスト１２９　、　ｆ３）処
理手段１２８、および（４）それぞれ出力バッファ　１
１４−１１６の各々と関連する複数のアドレスキュー（
アドレス待行列）　ＱＩＩ４−１１６からなる。主メモ
リロケーションが゛°使用される”か否かについては以
下で明らかにする。ボール１は、それがインジケータビ
ットがセラ１−されたアドレスバッファに出会うまでア
ドレスバッファ１０７−１０９を引き続いて問う。イン
ジケータピットセットを見出すと、（１）不使用ロケー
ション１２９のリストから予約ロケーションのアドレス
をとり除くことによって、処理手段１２８に主メモリ１
２５から不使用メモリロケーションを予約させかつ（２
）アドレスバッファ中のインジケータビットをリセット
する。予約された主メモリ内１２５内のアドレスは、入
力セクション１１７−１．１９中のメモリアドレスバッ
ファ　１１０−１１２の関連するものにロードされ、同
様に、パケットが届けられる出力バッファに対応するキ
ューＱ１１４−ＱＩ１．６の特定のものにもロードされ
る。これはすべてアＩＺレスがアドレスバッファに完全
にロードされた直後であって、パケットの残りのものが
入力バッファ１０４−１０６の関連するものに読み出さ
れるやや前に起こる。

ボール２は大力バッファ　１０４−１０６をポーリング
し、データパケットを含む入力バッファを探索する。ボ
ール２が大力バッファ内で完全なパケットに出くわすと
メモリアドレスバッファ１１０−１１２の関連するもの
が、大力バッファ１０４−１０６の対応するものの中の
パケットに対して前に予約されたメモリ２５のロケーシ
ョンを決定するために利用される。パケットは、それか
ら書き込みバス１１３を介して大力バッファから主メモ
リ１２５の適当なロケーションまで転送され、メモリア
ドレスバッファは初期値にリセットされる。

このようにして、パケットは独立してかつ連続して入力
１０１−１０３に到着するので、ボールｌとボール２の
結合は、主メモリ１２５の別々のメモリロケーションに
各パケットを次々と記憶するよう機能し、又パケットが
届けられる出力バッファに対応する適当なアドレスキュ
例えば、Ｑ１１４における記憶ロケーションを記録する
よう機能する。

ボール３は、ボール１および２と独立に動作し、システ
ムマネジャー１２１内に含まれるアドレスキューＱｌ１
４−Ｑ１１６を問う。このポーリングはいずれかの所定
のシーケンスでなされ得る。

ボール３がアドレスキューを問うのにもとづいて、その
アドレスキューにおける次のメモリロケーションのアド
レスがメモリアドレスバス上に現われ、主メモリ１２５
のそのアドレスに記憶されたパケットが読み出しバス１
２０上に送出される。

さらに、問われつつあるアドレスキューに対応する出力
バッファのみが読み出しバス１２０からデータを受信す
るようイネーブルにされるようにして制御ライン１２７
が現われる。例えば、Ｑ］、１４がボール３によって問
われる場合、制御ライン１２７は、出力バッファ１１４
のみが読み出しバス１２０からデータを受信するようイ
ネーブルにされるように現われる。このようにして、ボ
ール３によって問われつつあるキューと関連する出力バ
ッファに届けられるメモリ１２５中の次のパケットはそ
れぞれの出力バッファに転送され、そこで次々とパケッ
トスイッチからクロックアウトされる。さらに、パケッ
トによって以前に占有された主メモリアドレスは、処理
手段１２８によって不使用メモリロケーション１２９の
リストに加えられる。

いくつかの実行の細部は何６価値がない、まず第１に、
パケットに対する予約メモリアドレスは、パケットに対
する宛先アドレスがスイッチに読み出された直後ではあ
るが、パケットの残りがスイッチによって受信される前
に、アドレスキューＱｌ１４−Ｑｌ１６の適当なものの
中に置かれるということに注意すべきである。したがっ
て、スイッチにまだ完全に読み出されてないパケットに
対応する、キューＱＩ１４−ＱＩ１６の１つの６のにお
けるアドレスにポール３が出くわすことが可能である。

問題は、例えば、パケットが主メモリ１２５中の適当な
ロケーションにロードされるときにセットされる、各ア
ドレスキューＱｌ１４−Ｑｌ１６の各ロケーションにお
けるビットをもつことにより、もしくは対応するパケッ
ト全体が主メモリ１２５にロードされるまではキューＱ
ｌ１４−Ｑ１１６の適当なちのにアドレスをロードしな
いことにより容易に解決される。第２に、各パケットが
、ポール３が次の時間関連するアドレスキューを問う時
出力バッファが新しいパケットを受けとるのが容易なよ
う十分早く出力バッファから読み出されねばならないこ
とである。最後に、時間からパケットが完全に大力バッ
ファにロードされ、それがメモリ１２５に転送されるま
で、その入力バッファとそれと関連するアドレスバッフ
ァおよびメモリアドレスバッファはそれ以上の任意のパ
ケットを受信するのに役立たないことである。このため
、−旦パケットが完全にロードされ２つの入力セクショ
ンに転送され、そこで２つのメモリアドレスバッファと
アドレスバッファを使用してそれが処理され得るよう２
つの入力セクションを各入力にもつことが望まれる。そ
のときは、たとえ第１のパケットがまだメモリ１２５に
転送されなかった場合でも、第２のパケットは到着でき
処理されるべき第１の入力パケット、アドレスバッファ
およびメモリアドレスバッファを使用することができる
。それとは別に、主入力セクションが満ばいの場合には
、スイッチはその入力セクションで別の入力セクション
に到着するパケットを導くべく利用され得る。

発明の１つの欠点は並行なデータバスになされるべく要
求される接続の数である。特に、Ｊのユーザがサービス
を受けており、各到着パケットがＮビットの長さである
と仮定するとバスへの接続の必要な数はＪＮとなる。こ
れらバスへのＪＮの接続は、バス上のかなり大くの容量
負荷をもたらし、これにより達成し得る動作速度を減少
させることになる。この欠点は、以下で記述されるよう
な１つ以上のマルチプレクサを使用することで容易に解
決され得る。

第２図は、＋１１発明の実施例で大力バッファとして使
用され得る１組のシフトレジスタ２０１−２０２　、　
（２１マルチプレクサ２１３−２１８　、　（３１単一
チツブ２１９　、８よび（４）書き込みバス１１３を示
している。追加のマルチプレクサがレジスタ２０１−２
１２の所定のビットをマルチブレクスするために利用さ
れ得るが図の明瞭化のため示されてないことを理解すべ
きである。第２図のシステムを使用して１２ビツトのパ
ケット長をちった４つのユーザが適合されることを望ん
でいると仮定する。レジスタ２０１−２１２は、そのお
のおのが２０１−２０３゜２０４−２０６，２０７−２
０９および２１０−２１２であるような３つのレジスタ
の４つの組にグルフ化される。レジスタの各組は直列に
接続され、別々の入力バッファとして使用される、すな
わち第１図の入力バッファ１０４は３つのレジスタ２０
１−２０３から構成され得る。このようにして、第２図
が４つの大カバッファ即ちその各々が１２ビツトからな
る４つの入力バッファを示していることは明らかである
。しかしながら、すべての大力バッファからのビット“
ａ”がマルチプレクサ２１３−２１５を使用して一緒に
マルチブレクスされる場合には、これら４ビツトを必要
とする、バス１１３への接続の数は４から１へと減少さ
れる。同様に、各入力バッファからのビット“氾”がマ
ルチブレススされた２１６−２１８を用いた同様の方法
でマルチブレクスされ、その一方ですべての他のビット
が同様にマルチブレクスされ得る。バスへの接続の数は
ＪＮから単にＮへと減少される。マルチプレクサは、入
力バッファが問われているときにその入力バッファのビ
ットａ−Ｊ２が書き込みアドレスバスに現われるよう（
勿論前に述べたように全部のパケットがバッファに存在
しているとする）ポール２によって匍目卸される。

第２図の実施例は又実行の拡張性と容易性を示している
。特に、屯−チップ２１９は複数ＷＡＬのレジスタおよ
び１以上のマルチプレクサを用いて製造され得るであろ
う。必要となる半田接続の数はファクタ比Ｎ／１、だけ
さらに減少され得るであろう。たとえば、マルチプレク
サ２１６は単一チップ２１９に編入され、こうして無半
田接続がマルチプレクサ２１６への入力で要末されるこ
とに注意すべきである。さらに、この実施例を用いるこ
とにより、６っと多くの行又は列を追加することにより
それぞれパケットの長さとユーザの数が容易に拡張され
得る。

第３図は、（１）出力バッファ１１４−１１６、（２）
メモリアドレスバス１２６　、　　（３）処理手段１２
８、および（４）入力セクション１１７−１１９からな
る本発明のスイッチの実施例の一部を示している。第１
図のスイッチと類似して、第３図における出力バッファ
　１１４−１１６の各々は別々のキューでありいくつか
のパケットを記憶し得る。ルックアップ手段１２２−１
２４は、前述したように全部のパケットが大力バッファ
にロードされ、転送されたアドレスがすでにアドレスバ
ッファにロードされているように動作する。

ポール２は、引きつづいて入力バッファを問い、全部の
パケットを探索する。全部のパケットに出合った場合、
バケッｔ・はそれぞれの宛先出力バッファへと書き込み
バス１１３を介して転送される。メモリアドレスバス１
２６は、適当な出力バッファが書き込みバス１１３から
データを受信できるよう機能する。この実行は、第１図
のものよりも多くのメモリを必要とするが、複雑さは少
ない。

さらにこの実行は、１つの受信パケットを複数の宛先へ
と放送するのには適している。特に移送されるべきパケ
ットは、出力バッファ１１４−１１６の１つ以上のもの
に単純に読み出される。ポール２は入力バッファをポー
リングして完全なパケットを探索する。この実施例は出
力と同じ数の出力キュをもち、パケット遅延が前述した
パケット交換機における単一のルックアップ手段という
よりはむしろ複数のルックアップ手段を利用することに
より減少される点においてなお新規であると考えられる
。

ポーリング手段は、別のマイクロプロセッサ上かは同じ
プロセッサにおいて実行され得る。さらに、メモリアド
レスバッファ　１１０−１１２　Ｊよびアドレスバッフ
ァ　１０７−１０９は入力セクションと相互に位置づけ
られる必要はない。主メモリ１２５は、ここで述べた１
つのキューよりはむしろいくつかのパケットキューを設
定するために使用され得る。キューの数が出力の数より
も少ない限り、スイッチは、オバーフローの同じ可能性
を得るのにパケットスイッチにもとづ〈従来技術のメモ
リよりも少ないメモリを必要とするであろう、最後に、
アドレスキュＱｌ１４−Ｑｌ１６は単一のキューで置換
され得る。ポール３は各アドレスキュＱｌ１４−Ｑｌ１
６を引きつづいて試験するというよりはむしろポール３
は単一のアドレスキューを探索即ちまず１つの出力に対
するパケットを監視しそれから次の出力に対するものを
監視するというようにするものである。

【図面の簡単な説明】

第１図は、本発明のパケットスイッチの実施例の一部分
のブロックダイヤグラムを示す図、第２図は、本発明の
好ましい実施例の一部を示す図、および第３図は、本発
明の他の実施例を示す図である。 １１７． １０１゜ ２１ １１４． ２０１゜ 〈主要部分の符号の説明〉 １１８　、１１９−−一人カセクション１０２　、１０
３−、−入力 一−−−−−−−−−−−システムマネジャ１１５　、
１１６−−−出力バッファ ２０２−−−−−−−−−シフトレジスタ手続補正書（
方式） 平成　３年

Claims (1)

1. 【特許請求の範囲】 １、データパケットを受信するための複数の入力； 各々が関連の出力バッファを含み、該受信されたデータ
   パケットを転送するための複数の出力； 該複数の入力に接続され、データパケットがどの出力に
   向けられているかを決定するため各受信されたデータパ
   ケットを処理する手段； 該出力の数より少ない所定数のキューであって、該処理
   されたデータパケットを記憶するキュー； 及び 該処理手段からの該処理されたデータパケットを１つ若
   しくはそれより多くのキューにそして１つ若しくはそれ
   より多くのキューから該出力バッファに転送する手段と
   からなるパケットスイッチ。 ２、請求項第１に記載のパケットスイッチであって、各
   受信されたデータパケットは所定長Ｎでありそして該転
   送手段は、 該処理手段からの各データパケットをキューの１つに転
   送する第１のＮビットパラレルバス；及び 該キューの１つからの各データパケットを該データパケ
   ットの向けられた出力に関連の出力バッファへ転送する
   第２のＮビットパラレルバスとからなることを特徴とす
   るパケットスイッチ。 ３、請求項第２に記載のパケットスイッチであって、該
   処理手段は、 分離された受信データパケットを記憶するよう構成され
   た少なくとも１つの入力バッファ； 該入力バッファに受信された分離受信データパケットが
   記憶されるべきキューの１つにおける分離されたメモリ
   ロケーションに関連の分離されたアドレスを記憶するよ
   う構成された少なくとも１つのメモリアドレスバッファ
   、及び 各受信されたデータパケットが出力バッファのどれに向
   けられているかを決定するよう構成された少なくとも１
   つのルックアップ手段とからなることを特徴とするパケ
   ットスイッチ。 ４、請求項第２又は第３に記載のパケットスイッチであ
   って、該転送する手段は更に受信されたデータパケット
   の所定のものの所定の部分を多重化する少なくとも１つ
   のマルチプレクサからなることを特徴とするパケットス
   イッチ。 ５、データパケットを受信する複数の入力；各々が関連
   の出力バッファを含む該受信 データパケットを転送する複数の出力； 各受信データパケットがどの出力に向けられているか決
   定するための複数の受信データパケットを同時的に処理
   する該複数の入力に接続された手段； 該処理されたデータパケットを記憶する所定数のキュー
   ；及び 該処理手段からの該処理されたデータパケットを１つ若
   しくはそれより多くのキューへそして該１つ若しくはそ
   れより多くのキューから該出力バッファへと転送する手
   段とからなるパケットスイッチ。 ６、請求項第５に記載のパケットスイッチであって、該
   受信データパケットの各々は所定長Ｎでありそして該転
   送手段は、 各データパケットを該キューの１つに転送する第１のＮ
   ビットパラレルバス；及び 該キューの１つからのデータパケットの各々を該データ
   パケットが向けられている出力に関連の出力バッファに
   転送する第２のＮビットパラレルバスとからなることを
   特徴とするパケットスイッチ。 ７、請求項第６に記載のパケットスイッチであって、該
   処理手段は、 分離された受信データパケットを記憶するよう構成され
   た少なくとも１つの入力バッファ； 該入力バッファで受信された該分離データパケットが記
   憶されるべきキューの１つにおける分離メモリロケーシ
   ョンに関連の分離アドレスを記憶するよう構成されてい
   る少なくとも１つのメモリアドレスバッファ；及び 所定の入力で受信されたデータパケットがどの出力バッ
   ファに向けられているかを決定するよう構成されている
   複数のルックアップ手段からなることを特徴とするパケ
   ットスイッチ。 ８、請求項第６又は第７に記載のパケットスイッチであ
   って、該転送手段は更に該受信データパケットの所定の
   ものの所定の部分を多重化する少なくとも１つのマルチ
   プレクサからなることを特徴とするパケットスイッチ。