JP2000349789A - メモリー幅の非常に広いｔｄｍスイッチシステム - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】 メモリー幅の非常に広いスイッチシステムを
提供する。 【解決手段】 スイッチシステム１０は通信ライン１６
へパケットを送り出す、ある幅を持った出力ポート部１
４を含む。システムはパケットが移動するキャリア部２
０を含む。このキャリア部２０は出入力ポート部の幅よ
りも大きな幅を持つ。キャリア部２０は各入力ポート
部、各出力ポート部１４に接続されている。システムは
パケットが貯蔵されるメモリー部２２を含む。このメモ
リー部２２はキャリア部２０に接続されている。システ
ムは入力ポート部１２からキャリア部２０を経由してメ
モリー部２２へパケットを供給するためのメカニズムを
含む。該供給部は、各送信サイクル中に、その全体幅が
キャリア部２０の幅に等しいパケットまたはパケットの
部分をメモリー部２２に送ることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は時分割多重スイッチ
(TDM)に関するものである。さらに詳しくいうと、本発
明はメモリーのバス幅が、どんなパケットの幅からも独
立している、スイッチの時分割多重に関するものであ
る。

【０００２】

【発明の背景】時分割多重方式はスイッチシステムを実
行するために使われる１つの技術である。図1に示され
ているように、それぞれがRの割合でパケットを受け取
るN個の入力ポートと、それぞれがRの割合でパケットを
送り出すN個の出力ポートを持ったスイッチ構造を考え
てみよう。１つの共有されているTDMスイッチシステム
のためには、２×N×Rの総バンド幅を持つ１つのメモリ
ーバスが必要とされている。到着するパケットは集めら
れメモリーに書き込まれる。一旦メモリーに書き込まれ
た後、そのパケットはメモリーから読み出され、出力ポ
ート上で送られる。

【０００３】このシステムは、共有されているメモリー
が入力ポートと出力ポートすべてにサービスするのに十
分なバンド幅を持っておれば、正しく障害なく作動す
る。メモリーのバンド幅は、メモリーバスのスピード
と、メモリーバスの幅を増大させると、増すことができ
る。現在のメモリーバスのスピードは、マイクロプロセ
ッサー同期キャッシュメモリーを使って、技術的にだい
たい３００MHzに制限されている。さらにメモリーのバ
ンド幅を増すためには、メモリーバスがもっと拡げられ
なければならない。

【０００４】図２に示されているように、４つの入力ポ
ートと４つの出力ポートを持つTDMスイッチシステムの
例を考えてみよう。入力ポートと出力ポートは、１ビッ
ト幅のデータ経路で構成され、単一の固定されたクロッ
クの速度で作動する。これはすべてのポートとメモリー
バスについて同じである。すべてのパケットが８ビット
の長さであると仮定しよう。その構造物は８ビット幅の
TDMメモリーバスを使って実行されることができる。８
クロック周期以上の期間に、各入力ポートは１クロック
周期が割り与えられ、１つのパケット(８ビット)をメモ
リーに書き込み、各出力ポートは１クロック周期が割り
与えられ、メモリーから１つのパケットを読み込む。

【０００５】TDMスイッチシステムを実用化するには、
設計を複雑にするいくつかの課題がある。スイッチシス
テムのアプリケーションに応じて、パケットは通常はサ
イズが変えられる。パケットのサイズを変えることは、
メモリーバス上でのパケットの断片(fragmentation)の
ためTDMシステムの性能を下げる。もし１つのパケット
がメモリー周期の整数倍を使用しないならば、メモリー
バンド幅は、メモリー幅より小さなデータを読み込み、
または書き込むメモリー周期で無駄になる。典型的に
は、TDMシステムは断片に伴う非効率性を補うために２
×N×Rより大きいメモリーバンド幅で実行されている。

【０００６】断片の課題は、メモリー幅が最小サイズの
データパケットに近づき、あるいは超えるにしたがって
重大となる。メモリーバスの幅がパケットの最小長さの
2倍に等しいシステムを考えてみよう。受け取ったパケ
ットの長さがすべてパケットの最小長さと等しい間は、
メモリーに書き込まれたすべてのパケットがメモリーバ
スのデータビットを半分しか使っていないので、メモリ
ーシステムのバンド幅は５０％に減らされる(または５
０％の効率になる)。

【０００７】メモリーバス上のパケットの断片のため
に、典型的なTDMスイッチシステムは、最小長さのパケ
ットとせいぜい同じ幅のバス幅を使っている。TDMスイ
ッチシステムの共有メモリーの全バンド幅は、メモリー
バスのバンド幅によって制約されている。メモリーバス
のバンド幅は、それの速さ(クロック率)とそれの幅(ビ
ット数)によって決まる。記憶速度が、使用可能な記憶
要素の技術によって固定されているとするならば、TDM
スイッチの全バンド幅は最小パケットサイズによって制
約されていることになる。

【０００８】

【発明の要旨】本発明は、スイッチシステムに関するも
のである。システムには、ある幅を持つ通信ラインから
パケットを受け取るI個の入力ポート部がある(Iは１以
上の整数である)。システムには、ある幅を持つ通信ラ
インへパケットを送るO個の出力ポート部がある(Oは１
以上の整数である)。システムにはキャリア部があり、
その上をパケットが移動する。キャリア部は入力、出力
通信ラインの幅よりも広い幅を持つ。キャリア部は各入
力ポート部と各出力ポート部に接続されている。システ
ムには、パケットが貯蔵されるメモリー部がある。シス
テムには、入力ポート部からキャリア部を経由してパケ
ットをメモリー部に供給するメカニズムがある。該供給
部は、各送信サイクル中にて、その全体幅がキャリア部
の幅に等しいパケットまたはパケットの部分をメモリー
部に送ることができる。

【０００９】本発明はパケットのスイッチシステムに関
するものである。システムには、ある幅と全バンド幅を
持ち、それぞれのパケットの送受信をするための入力ポ
ート部と、出力ポート部を持った中央資源がある。中央
資源は入力、出力ポート部に割り当てられるタイムスロ
ットによって分割される。中央資源の幅の大きさは、ど
んなパケットの幅の大きさからも独立であり、全バンド
幅は際限なく大きくなりうる。システムにはパケットを
貯蔵するメモリー部があり、メモリー部は中央資源に接
続されている。

【００１０】本発明はスイッチシステムに関するもので
ある。システムには時分割多重バスがある。システムに
は、バスの時分割多重によってアクセスされたバスに接
続されたメモリー部がある。システムにはデータのパケ
ットの境界を知ることなく、パケットのデータをバスを
通じてメモリー部に読み込み、書き込むためのメカニズ
ムがある。

【００１１】本発明はスイッチシステムに関するもので
ある。システムにはある幅を持つ時分割多重キャリア部
がある。システムにはそのキャリア部に接続されたメモ
リー部がある。システムにはパケットのデータが、時分
割多重によって、パケットのデータがバスの幅を満たす
ようパケットのデータをメモリー部に供給するための、
ある幅を持つ入力部がある。バス幅はパケットの幅の非
整数倍である。システムにはパケットのデータをメモリ
ー部から供給するための、ある幅を持つ出力部がある。

【００１２】本発明は、各々がある幅を持っている入力
部から出力部へとパケットを切り換えるための方法に関
するものである。その方法は、最初のパケットと少なく
とも2つ目のパケットをスイッチ部で受け取る工程を含
んでいる。その方法は、ある幅を持つバスの分割多重を
経て、１番目のパケットと２番目のパケットのデータを
メモリー部へ送り、それによってパケットからのデータ
は、バスの幅の所定箇所を満たす工程を含んでいる。バ
スの幅は入力、出力部の幅と同じでない。

【００１３】

【発明の実施の形態】図面に於いて、いくつかの図、よ
り詳しく言うと、図３、４を通じ、そこでは同じ参照番
号は、同種のまたは同じ部分を示している。スイッチシ
ステム(10)が示されている。システム(10)には通信ライ
ン(16)からパケットを受け取るI個のある幅を持つ入力
ポート部(12)がある(Iは１以上の整数である)。１つの
入力ポート部(12)は１つの入力ポートを含んでいるのが
望ましい。システムには通信ライン(16)へパケットを送
るO個のある幅を持つ出力ポート部(14)がある。１つの
出力ポート部(14)は１つの出力ポートを含んでいるのが
望ましい(Oは１以上の整数である)。システムにはキャ
リア部(20)があり、その上をパケットが移動する。キャ
リア部(20)は入力、出力部の幅より広い幅を持つ。キャ
リア部(20)は各入力ポート部と各出力ポート部に接続さ
れている。システム(10)にはパケットが貯蔵されるメモ
リー部(22)がある。システムには入力ポート部(12)から
キャリア部(20)を経由してパケットをメモリー部(22)に
供給するメカニズムがある。該供給部(20)は各送信サイ
クルの間に、その全体幅がキャリア部(20)の幅に等しい
パケット又はパケットの部分をメモリー部(22)に送るこ
とができる。

【００１４】キャリア部(20)の幅の大きさはどの入力、
出力部の幅からも独立であることが望ましい。入力ポー
ト機構は、さまざまなサイズのパケットを受け取るのが
望ましい。出力ポート部は、さまざまサイズのパケット
を通信ライン(16)へと送り出すのが望ましい。通信ライ
ン(16)はＡＴＭネットワークでもよい。

【００１５】供給部(20)もまた、メモリー部(22)からキ
ャリア部(20)を経由して出力ポート部(14)へと、パケッ
トを供給するのが望ましい。供給部(20)は各送信サイク
ルの間に、その全体幅がキャリア部(20)の幅に等しいパ
ケット又はパケットの部分をメモリー部(22)から送るこ
とができる。

【００１６】供給部(20)には、待ち行列群(24)(queue g
roup)の入力段があり、これはキャリア部(20)と入力ポ
ート部(12)に接続されていて、入力ポート部によって受
け取られたパケットを貯蔵する。また、待ち行列群(26)
の出力段があり、これは供給部(20)と、出力ポート部(1
4)に接続されていて、出力ポート部から送り出すべきパ
ケットを貯蔵する。そして各待ち行列群は１つのパケッ
トに対応している。供給部(20)は入力ポート部によって
受け取られたパケットを、対応する待ち行列群の入力段
に配置する仕分け部(28)を含んでいて、この仕分け部(2
8)は入力ポート部(12)と待ち行列群(24)の入力段に接続
されているのが望ましい。供給部(20)は待ち行列群の出
力段にあるパケットを、対応する出力ポート部(14)へと
配置する処理部(30)を含んでいて、この処理部(30)は出
力ポート部(14)と待ち行列群(26)の出力段に接続されて
いるのが望ましい。

【００１７】仕分け部(28)は、パケットを対応する入力
待ち行列に書き込むための、書き込み用第１有限状態機
(32)(write finite state machine)を含み、供給部(20)
は、パケットを待ち行列群の入力段からメモリー部(22)
へと書き込むための書き込み用第２有限状態機(34)とパ
ケットをメモリー部(22)から待ち行列群の出力段へと読
み込むための読み込み用第１有限状態機(36)を含み、処
理部(30)は、待ち行列群の出力段からネットワークへと
読み込むための読み込み用第２有限状態機(38)を含んで
いるのが望ましい。

【００１８】メモリー部(22)は共有されたメモリー(40)
を含んでいるのが望ましい。パケットまたはパケットの
一部が、時分割多重に基づいてキャリア部(20)を動くの
が望ましい。キャリア部(20)はバス(42)を含むのが望ま
しい。待ち行列群の入力段がデータの少なくとも１つの
キャッシュラインを含むときには、読み込み用第１有限
状態機(36)は待ち行列群の入力段のパケットのデータを
バス(42)へと移送するだけなのが望ましい。

【００１９】本発明はパケットのスイッチシステム(10)
に関するものである。システムには、ある幅と、ある全
バンド幅を持ち、パケットを受け取るための入力ポート
部(12)と、パケットを送り出すための出力ポート部(14)
を持った、中央資源(44)がある。中央資源(44)は入力、
出力ポート部(14)に割り当てられるタイムスロットによ
って分割される。中央資源(44)の幅の大きさはどんなパ
ケットの幅の大きさからも独立であり、全バンド幅は際
限なく大きくなりうる。システム(10)にはパケットを貯
蔵するメモリー部(22)があり、メモリー部(22)は中央資
源(44)に接続されている。

【００２０】中央資源(44)はメモリーバス(42)を含むの
が望ましい。中央資源(44)はパケットが分類される先の
待ち行列の一群を含み、パケットは待ち行列の一群から
読み出されメモリー部(22)へと書き込まれるのが望まし
い。本発明はスイッチシステム(10)に関するものであ
る。システム(10)には時分割多重バス(42)がある。シス
テム(10)にはバス(42)の時分割多重によってアクセスさ
れたバス(42)に接続されたメモリー部(22)がある。シス
テムにはデータのパケットの境界を知らなくして、パケ
ットのデータをバス(42)を通じてメモリー部(22)に読み
込み、書き込むためのメカニズムがある。

【００２１】本発明はスイッチシステム(10)に関するも
のである。システムにはある幅を持つ時分割多重キャリ
ア部(20)がある。システムにはそのキャリア部(20)に接
続されたメモリー部(22)がある。システムにはパケット
のデータが時分割多重によってバス(42)の幅を満たすよ
う、パケットのデータを入力ポート部からメモリー部(2
2)に供給するためのメカニズムがある。バス(42)幅は入
力、出力ポート部の幅の非整数倍である。

【００２２】本発明は入力部から出力部へとパケットを
切り換えるための方法に関するものである。その方法は
最初のパケットと少なくとも２番目のパケットをある幅
を持つスイッチ部で受け取る工程を含んでいる。その方
法は、第１パケットと第２パケットのデータを、ある幅
を持つバス(42)の時分割多重によって、メモリー部(22)
へ送り、パケットからのデータは、バス(42)の幅の所定
部分を満たす工程を含んでいる。バス(42)幅は入力、出
力ポート部の幅と同じではない。

【００２３】バス(42)幅は入力ポート部の幅の正の数の
倍が望ましく、非整数倍でもよい。送信の工程は、最初
のパケットと少なくとも２番目のパケットを待ち行列群
の入力段に配置する工程と、待ち行列群の入力段にある
データを、バス(42)で割り当てられたタイムスロットの
間に、データがバス幅(42)の所定の割合を満たすよう
に、メモリー部(22)に送る工程を含むのが望ましい。

【００２４】データ送信工程の前に、入力待ち行列の一
群が少なくともバス幅(42)の所定の割合を満たすに十分
なデータを持っているかどうかを、データがバス(42)に
送られる前に判定する工程があるのが望ましい。データ
送り工程の前に、待ち行列群の入力段が少なくとも１つ
のキャッシュラインを持っているかどうかを判定する工
程があるのが望ましい。

【００２５】この発明のオペレーション、つまりシステ
ム(10)では、典型的なTDMスイッチシステムのメモリー
幅制限は、パケットを待ち行列群(24)の入力段に仕分け
して、それから待ち行列群(24)の入力段からデータを読
み込みメモリーへ書き込むことにより取り除かれてい
る。メモリー幅は最小限のパケットの大きさから独立で
あり、TDMスイッチシステムの全バンド幅は際限なく大
きくすることが出来る。

【００２６】スイッチシステム(10)の入力ポートに到着
したパケットは待ち行列の一群(24)のある決まった番号
に分類される。１つの待ち行列は３段階で各群に実装さ
れる。 １．入力段階： 待ち行列の後尾は書き込み用第１有限
状態機(W-FSM)によりスイッチ構造に実装される。 ２．メモリー段階： 待ち行列の中央は共有されたメモ
リーで実装される。 ３．出力段階： 待ち行列の先頭は読み込み用第１有限
状態機(W-FSM)によりスイッチ構造に実装される。

【００２７】共有されたメモリーへの読み込み・書き込
みは待ち行列群の中のデータ上で実行され、待ち行列で
のパケットの境界が意識されることはない。共有された
メモリーへのアクセスは、共有されたメモリーバスの時
分割多重によって読み込み用・書き込み用FSMに割り当
てられる。

【００２８】W-FSMは以下のように実装される： W-FSMが待ち行列に格納する過程： パケットは入力ポートから到着した後、分類されW-FSM上の待ち行列 群の後尾に追加される。 W-FSMが待ち行列に排出する過程： (TDMバスにタイムスロットが割り当てられたとき) (W-FSMが少なくとも1つのデータキャッシュラインを含むのであれば) キャッシュラインをW-FSMの先頭で、共有されたメモリ待ち行列の後尾 に書き込む。 R-FSMは以下のように実装される： R-FSMが待ち行列にデータを格納する過程 (TDMバスに割り当てられたタイムスロットにおいて) もし(R-FSMがデータを含まない場合) もし(共有されたメモリーがこの待ち行列群のためのデータ を含んでいる場合) 共有されたメモリー待ち行列の先頭において、キャッシュラ インを読込、R-FSM待ち行列の後尾にキューする。 そうでないならば(共有されたメモリーが、この待ち行列群のためのデ ータを含んでいないなら、) W-FSM待ち行列の先頭から(キャッシュラインまでの)R-FSM 待ち行列の後尾までの任意のデータを読み込む。 R-FSMが待ち行列にデータを排出する過程 パケットはR-FSM待ち行列の出力段の先頭から取り出されて、処理さ れ、出力ポートへと転送される。

【００２９】更に特定すると、１つのセルまたは１つの
パケットは、スイッチ(45)の１つの入力ポートに到着す
る。W-FSM(32)は待ち行列群(24)へとパケットを分類す
る。他のパケットがスイッチ(45)の入力ポートに到着す
ると、それらもまたW-FSM(32)によりそれらの対応する
待ち行列群(24)へと分類される。待ち行列群に一旦分類
されると、それら(パケット)は対応する入力段の待ち行
列群の後尾に付け加えられる。スイッチ(45)の入力ポー
トに到着したセルの分類と格納はその後も続いていく
が、ある決まった入力段の待ち行列群(24)については、
１つのパケットが分類されると、そのパケットが対応す
る入力段の待ち行列群の後尾に付け加えられる。

【００３０】入力段の待ち行列群(24)に対応する書き込
み用第２有限状態機(34)は、入力段の待ち行列群(24)内
のパケットの個数を記録している。入力段の待ち行列群
(24)上のデータに十分なパケットが入力段の待ち行列群
(24)にあるときは、書き込み用第２有限状態機(34)は、
入力段の待ち行列群(24)にバス上で割り与えられたタイ
ムスロットの到着を待っている。割り当てられたタイム
スロットが到着しても、キャッシュラインを満たすのに
十分なデータが入力段の待ち行列群(24)にないために、
以前は入力段の待ち行列群(24)からデータを解放しなか
ったものの、いまやキャッシュラインを満たすのに十分
なデータがあるので、書き込み用第２有限状態機(34)
は、入力段の待ち行列群(24)から、入力段の待ち行列群
(24)に割り当てられたタイムスロットの間にキャッシュ
ラインを満たすのに十分なデータを送る。割り当てられ
たタイムスロットとは、入力段の待ち行列群(24)からバ
スへとデータキャッシュラインが送られるのを許容する
に十分な期間である。入力段の待ち行列群(24)からのデ
ータキャッシュラインがバス上で送られると、入力段の
待ち行列群(24)に残るデータは入力段の待ち行列群(24)
の先頭まで移動される。更に入力段の待ち行列群(24)の
先頭に移動されたデータは次のパケットや入力段の待ち
行列群(24)に入ろうとするデータのための余地をうみだ
す。データが入力段の待ち行列群(24)からバスに送られ
ているまさにその時、セルが入力段の待ち行列群(24)の
後尾に配置されることもありうる。

【００３１】キャッシュラインのサイズによっては、バ
スに送られたデータは、入力段の待ち行列群(24)内のパ
ケットが持つデータの整数倍以外の場合がある。例えば
キャッシュラインは、キャッシュラインのデータがメモ
リー(40)へとバス上で送られた後に、入力段の待ち行列
群(24)にパケットの一部が残るような幅となる場合であ
る。書き込み用第２有限状態機(34)は、セルやパケット
の境界を意識することなく、セルやパケットの一体性に
対する結果が何であれ、データでキャッシュラインを満
たすことのみが問題となる。よって、セルやパケットは
割り与えられたタイムスロット内でデータがキャッシュ
ラインを満たすという制約条件に適応すべく分割され
る。

【００３２】バスから共有されたメモリー(40)にデータ
キャッシュラインが到着した時、コントローラ(47)はデ
ータキャッシュラインを共有されたメモリー(40)に貯蔵
し、入力段の待ち行列群(24)からのキャッシュラインお
よびキャッシュラインの接続元である入力段の待ち行列
群(24)の順番にならって、共有されたメモリー(40)での
番地を記録する。その後、異なる入力段の待ち行列群(2
4)から送られるデータキャッシュラインが、コントロー
ラ(47)により、共有されたメモリー(40)に貯蔵される。
そして入力段の待ち行列群(24)から送られた次のキャッ
シュラインも同様に共有されたメモリー(40)に貯蔵され
る。コントローラ(47)は、待ち行列群(24)入力段からの
キャッシュラインが格納される番地のトラックを保持し
ておく。仮に入力段待ち行列群(24)からの最初のキャッ
シュラインがセルの最初の部分を有し、入力段待ち行列
群(24)からの２番目のキャッシュラインがセルの２番目
の部分を持っていたとしても、入力段待ち行列群(24)か
らの次のキャッシュラインは必ずしも同一番地に格納さ
れたり、又は互いに隣り合った２つの番地に格納される
ことは必要でない。

【００３３】パケットが出力ポートから送り出される時
は、ある出力段の待ち行列群(26)に対応する読み込み用
第１有限状態機(36)は、その出力段の待ち行列群(26)に
バス上で割り当てられたタイムスロットを待っている。
読み込み用第１有限状態機(36)は出力段の待ち行列群(2
6)に読み込まれる共有されたメモリー(40)内のデータを
とどめる。読み込み用第１有限状態機(36)はコントロー
ラ(47)と書き込み用第１有限状態機(32)に接続されてい
るため、どのデータが対応する出力段の待ち行列群(26)
に送られるかが分かる。出力段の待ち行列群(26)に次の
割り当てられたタイムスロットが到着すると、出力段の
待ち行列群(26)のための共有されたメモリー(40)にある
キャッシュラインは読み込み用第１有限状態機(36)によ
って出力段の待ち行列群(26)に読み込まれる。読み込み
用第１有限状態機(36)はコントローラ(47)と接続される
ことによって、どの場所からキャッシュラインを読み込
むべきかが分かる。キャッシュラインは順番に読み込ま
れ出力段の待ち行列群(26)に配置されるので、共有され
たメモリー(40)への書き込み段階で出力段の待ち行列群
(26)が再結合されると、分割された全てのセルもまた再
結合される。出力段の待ち行列群(26)のために割り与え
られたタイムスロットが到着した時に、何のデータもな
い時は読み込み用第１有限状態機は入力段の待ち行列群
(24)から直接キャッシュラインへとデータを読み込み、
そのデータは最終的に出力段の待ち行列群(26)へと伝達
されることとなる。

【００３４】読み込み用第２有限状態機(38)は出力段の
待ち行列群のパケットの情報をとどめている。パケット
の中で所定量が出力段の待ち行列群(26)で形成された時
のみ読み込み用第２有限状態機(38)は出力段の待ち行列
群(26)から所定量までパケットを読み込み、ネットワー
クにパケットを送り出す。

【００３５】メモリーへの読み込み・書き込みは全てデ
ータの全てのキャッシュラインを含むため、メモリーバ
ス(42)の効率は１００％である。小さなパケットはメモ
リーバス(42)上でデータの断片化を起こさない。さらに
メモリーバスの幅は際限なく増大することができ、パケ
ットの大きさに制限されない。

【００３６】待ち行列群のモデルは、任意の待ち行列構
造を実装するために用いることができる。出力待ち行列
を実装するには、１個の待ち行列群が各出力ポートに割
り与えられる。待ち行列群は入力段の待ち行列群、共有
されたメモリーに蓄えられたあるキャッシュライン、出
力段の待ち行列群で構成される。パケットの仕分け部は
入力の際にパケットをそれぞれ検査し、パケットを適切
な出力段の待ち行列に分類する。パケットは、その出力
段の待ち行列群に対応する入力段の待ち行列群に関連付
けられる。出力段の待ち行列群(28)は、W-FSM、R-FSMを
用いてメモリーから、またメモリーへとキューされる。
R-FSMの後、パケットは直ちに出力ポートへキューされ
る。

【００３７】１つの待ち行列群(24)を入力ポート毎に関
連づけることにより、簡単なパケット仕分け部を使って
入力待ち行列が実装される。優先順位に基づいた仕組み
は以下のように実装される。１つの待ち行列群が、いく
つかの優先順位レベルの夫々に対して定義される。入力
の際、１つのパケットは、優先した待ち行列群の１つへ
仕分けられる。待ち行列群はW-FSMやR-FSMを用いてメモ
リーにキューされる。R-FSMの後、パケットはそれぞれ
の出力ポートを決定するために処理され、システムから
送り出される。

【００３８】

【例】４つの入力ポート、４つの出力ポートのパケット
スイッチがシステム(10)を使って実装される。システム
は全体的に同期していて20MHzクロック周期で動作す
る。４つの入力は８ビット幅で動作し、４つの160Mbps
インターフェースを実装する。パケットは図５に示され
ているようにパケット始端(SOP)とパケット終端(EOP)を
あらわす符号語によって区切られている。

【００３９】この例は出力待ち行列スイッチを仮定して
いる。スイッチシステム(10)の入力ポートに到着したパ
ケットは、各出力ポートに対して１つが対応し、４つの
待ち行列群に分類される。図４を参照すると、出力待ち
行列は各群３つのサブシステムに実装される： １．後尾はスイッチ構造内で書き込み用第１有限状態機
(W-FSM)により実装される。 ２．中間は共有されたメモリーに実装される。 ３．先頭は読み込み用第１有限状態機(R-FSM)によりス
イッチ構造中へ実装される。

【００４０】共有されたメモリーへの読み込み・書き込
みは待ち行列群のデータ上で実装され、待ち行列内のデ
ータのパケット境界を意識することなく実行される。共
有されたメモリーへのアクセスは共有されたメモリーバ
スの時分割多重によって、読み込み用・書き込み用第１
有限状態機に割り当てられる。共有されたメモリーバス
幅はキャッシュラインと呼ばれている。

【００４１】本発明の入力段・出力段にある待ち行列群
の先頭と後尾はシフトレジスタ(51)の中で直接実装され
る。シフトレジスタ(51)はやってくるデータのインター
フェースと同じ幅でメモリーキャッシュラインと同じ長
さである。４つのポートのスイッチのためのデータパス
は図６に示されている。

【００４２】キャッシュラインは６４ビット長で、８バ
イトそのものである。各ポートからのデータは８ビット
幅キャッシュラインのシフトレジスタへと８レジスタの
深さでシフトされる。示されていないのは、同じく８レ
ジスターの深さで８ビットのシフトレジスターの前の、
同期シフトレジスターである。メモリーバスは図７に示
されているようにTDM(時分割多重)方式で、それぞれが
各入力・出力ポート用に８つのタイムスロットに分割さ
れる。一例としてのスイッチが出力待ち行列を実装して
いるため、出力待ち行列は常に同じ割合で排出され、従
って常にバス上の同じタイムスロットを使うこととな
る。到着するパケットはどの出力ポートにも向けられる
ため、入力段の待ち行列はいかなる割合でも満たすこと
ができる。入力段の待ち行列は必要なだけ入力バスのタ
イムスロットを割り当てられる。総入力率は４つのタイ
ムスロットを超えないので、入力段が４つの入力段タイ
ムスロットを任意に調節させるのに十分である。

【００４３】同期レジスタはどのデータも失われないこ
とを補償するために使用される。典型的にはデータは同
期レジスタには貯蔵されない。到着する全てのパケット
はキャッシュレジスタに直接書き込まれる。もしキャッ
シュレジスタがTDMバス上のそのタイムスロットの前に
満たされた場合、同期レジスタはデータを貯蔵し始め、
一旦キャッシュラインレジスタが空になると同期レジス
タからのデータはキャッシュラインレジスタに押し込ま
れる。もしキャッシュラインレジスタがまだ一杯なら、
すぐに次の入力バスサイクルを調節する。満たされたキ
ャッシュラインレジスタのみがバスサイクルを調節す
る。

【００４４】図８に示されているように、(この発明の
入力、出力段)の先頭と後尾は、ハードウェアのFIFO待
ち行列に直接実装される。待ち行列群の中間部分はメモ
リーに実装され、キャッシュラインに貯蔵されている。
この例では１クロック周期のみでキャッシュライン全体
を読み込み、書き込める２５６層メモリーが使われてい
る。Zero turn around memories (ZBT)が仮定され、書
き込みが直接読み込みに続くようになっている。

【００４５】図９に示されているように５つのFIFO待ち
行列(57)がメモリーの待ち行列群の中間部分を実装する
のに必要とされる。待ち行列の４つはメモリーに含まれ
るキャッシュラインの番地を含み、５つ目の待ち行列は
フリーリストと呼ばれ、空のキャッシュラインの番地を
含んでいる。フリーリストのリセット操作により、FIFO
は初期化されメモリーに含まれるキャッシュラインの全
ての番地を含むようになり、チャンネル番地FIFOは空に
なる。データパスは８つの状態のうち１つで動作する： Ain, Bin, Cin, Din, Aout, Bout, Cout, Dout

【００４６】この状態は上記メモリーの枠組みにより示
されるタイムスロットにより決定される。この例では４
つの出力待ち行列群は個々の特定した状態を使ってい
る。入力段は入力状態のうちどれでも使うことを要求す
る。調整機構はどの入力段が適切な入力タイムスロット
を使うのかを明らかにする。全ての入力(出力)状態は同
様に動作する。入力段Aがうまく入力状態を調整してい
る入力状態Ainを考えてみる。TDMの枠組みの最初のクロ
ック周期ではAinは以下のように動作する： (TDMバスに割り当てられたタイムスロットで) もし(キャッシュラインレジスタが一杯ならば) ― メモリーバスを駆動するためにフリーリストの先 頭で番地を使う。 ― チャンネルAキャッシュラインのレジスタに含 まれているデータをメモリーに書き込む。 ― フリーリストのメモリー番地を押し出す。 ― フリーリストのメモリー番地をチャンネルA番 地FIFOの後尾に押し込む。

【００４７】もしフリーリストのメモリー番地でFIFOが
空ならチャンネルAキャッシュラインレジスタに位置す
るデータは落とされる。チャンネルAで落とされたパケ
ットを特定するためには注意が必要である。他の入力チ
ャンネルはそれら自身の特定されたメモリータイムスロ
ットで同様に動作する。TDMの枠組みでの出力状態Aout
を考えてみる。５つ目のクロック周期ではAoutは次のよ
うに動作する： (TDMバスに割り当てられたタイムスロットで) もし(R-FSMがデータを何も持っていない場合) もし(共有されたメモリーがこの待ち行列群のためのデータを 含んでいるなら) キャッシュラインを共有されたメモリーの待ち行列の先 頭でR-FSM待ち行列の後尾に読み込む。 そうでないならば(共有されたメモリーがこの待ち行列群のた めのデータを含んでいない場合) W-FSM待ち行列の先頭から(キャッシュラインに至るまで の)全てのデータをR-FSMの後尾に読み込む。

【００４８】R-FSM待ち行列の排出過程については、パ
ケットはR-FSM待ち行列の先頭から押し出されて伝達さ
れ、出力ポートに送られる。メモリーへの読み込み・書
き込みは全てデータの全てのキャッシュラインを含むた
め、メモリーバス(42)の効率は１００％である。小さな
パケットはメモリーバス(42)上でデータの断片化を起こ
さない。さらにメモリーバスの幅は際限なく増大するこ
とができ、パケットの大きさに制限されない。

【００４９】この発明は図示のために前述の具体化方法
において詳述されてきたものだが、この詳しい部分は、
この目的(図示)のためだけのものであり、技術分野の者
なら以下の特許請求の範囲で述べられるものは別にし
て、この発明の真意と範囲から逸脱することなく、変更
を加え得ると理解されるべきである。

【図面の簡単な説明】

添付の図では、この発明の望ましい具体例と、この発明
を実行する望ましい方法が示されている。

【図１】従来技術の時分割多重スイッチの概略図であ
る。

【図２】４つの入力、４つの出力を持った従来技術の時
分割多重スイッチの概略図である。

【図３】本発明のスイッチシステムの概略図である。

【図４】本発明のスイッチシステムの概略図である。

【図５】記号語の概略図である。

【図６】4つのポートパスのデータ経路の概略図であ
る。

【図７】TDM方式で分割されたメモリーバスの概略図で
ある。

【図８】メモリーの概略図である。

【図９】５つのFIFO待ち行列の概略図である。

【符号の説明】

(10) スイッチシステム (12) 入力ポート部 (16) 通信ライン (20) キャリア部 (22) メモリー部 (24) 入力段待ち行列群 (26) 出力段待ち行列群 (28) 仕分け部 (30) 処理部 (32) 書込み用第１有限状態機 (34) 書込み用第２有限状態機 (36) 読込み用第１有限状態機 (38) 読込み用第２有限状態機 (40) メモリー (42) バス (44) 中央資源

Claims (24)

【特許請求の範囲】
1. 【請求項１】 通信ラインからパケットを受け取る、あ
   る幅を持ったＩ個の入力ポート部(Ｉは１より大きい整
   数)と；通信ラインへとパケットを送り出す、ある幅を
   持ったO個の出力ポート部(Oは１より大きい整数)と；パ
   ケットが移動するキャリア部であって、このキャリア部
   は出入力ポート部の幅よりも大きな幅を持ち、該キャリ
   ア部は、各入力ポート部、各出力ポート部に接続されて
   いる；パケットが貯蔵されるメモリー部であって、この
   メモリー部はキャリア部に接続されている；入力ポート
   部からキャリア部を経由してメモリー部へとパケットを
   供給するメカニズムであって、該供給部は、各送信サイ
   クル中に、その全体幅がキャリア部の幅に等しいパケッ
   トまたはパケットの部分をメモリー部に送ることができ
   る；を有するスイッチシステム。
2. 【請求項２】 キャリア部の幅の大きさは、どのパケッ
   トの幅からも独立である、請求項１に規定されたスイッ
   チシステム。
3. 【請求項３】 入力ポート部は、さまざまな大きさのパ
   ケットを受け取る、請求項２に規定されたシステム。
4. 【請求項４】 出力ポート部は、通信ラインへさまざま
   な大きさのパケットを送り出す、請求項３に規定された
   システム。
5. 【請求項５】 供給部もまた、メモリー部からキャリア
   部を経由して出力ポート部へと、パケットを供給し、各
   送信サイクルの間に、その全体幅がキャリア部の幅に等
   しいパケットかパケットの部分をメモリー部に送ること
   ができる、請求項４に規定されたシステム。
6. 【請求項６】 供給部には、待ち行列群の入力段があ
   り、キャリア部と、入力ポート部によって受け取ったパ
   ケットを貯蔵するための入力ポート部とに接続されてい
   る一方、待ち行列群の出力段があり、供給部と、出力ポ
   ート部から送り出すパケットを貯蔵するための出力ポー
   ト部とに接続されている、請求項５に規定されたシステ
   ム。
7. 【請求項７】 供給部は、入力ポート部によって受け取
   られたパケットを、対応する待ち行列群に配置する仕分
   け部を含んでおり、この仕分け部が入力ポート部と待ち
   行列群の入力段に接続されている、請求項６に規定され
   たシステム。
8. 【請求項８】 供給部は、待ち行列群の出力段にあるパ
   ケットを、対応する出力ポート部へと配置する処理部を
   含んでいて、この処理部が出力ポート部と待ち行列群の
   出力段に接続されている、請求項７に規定されたシステ
   ム。
9. 【請求項９】 仕分け部は、パケットを対応する入力待
   ち行列に書き込むための、書き込み用第１有限状態機を
   含み、供給部はパケットを待ち行列群の入力段からメモ
   リー部へと書き込むための書き込み用第２有限状態機
   と、パケットをメモリー部から待ち行列群の出力段へと
   読み込むための読み込み用第１有限状態機を含み、処理
   部は待ち行列群の出力段からネットワークへと読み込む
   ための読み込み用第２有限状態機を含んでいる、請求項
   ８に規定されたシステム。
10. 【請求項１０】 メモリー部は、共有されたメモリーを
    含んでいる、請求項９に規定されたシステム。
11. 【請求項１１】 パケットまたはパケットの部分が、時
    分割多重に基づいたキャリア部上を移動する、請求項１
    ０に規定されたシステム。
12. 【請求項１２】 キャリア部は、バスを含んでいる、請
    求項１１に規定されたシステム。
13. 【請求項１３】 待ち行列群の入力段は、データの少な
    くとも１つのデータのキャッシュラインを含むときに
    は、読み込み用第１有限状態機は、待ち行列群の入力段
    のパケットのデータをバスへと移送だけする、請求項１
    ２に規定されたシステム。
14. 【請求項１４】 通信ラインは、ATMネットワークであ
    る、請求項１３に規定されたシステム。
15. 【請求項１５】 以下の構成を含む、パケットのための
    スイッチシステム：ある幅と、ある全バンド幅を持ち、
    パケットを受け取るための入力ポート部と、パケットを
    送り出すための出力ポート部とを持った中央資源であっ
    て、この中央資源は、入力、出力ポート部に割り当てら
    れるタイムスロットによって分割され、中央資源の幅の
    大きさはどんなパケットの大きさからも独立であり、全
    バンド幅は際限なく大きくなりうる；パケットを貯蔵す
    るメモリー部であって、該メモリー部は中央資源に接続
    されている。
16. 【請求項１６】 中央資源は、メモリーバスを含んでい
    る、請求項１５に規定されたシステム。
17. 【請求項１７】 中央資源は、パケットが分類される待
    ち行列群を含み、パケットは待ち行列群から読み出さ
    れ、メモリー部へと書き込まれる、請求項１６に規定さ
    れたシステム。
18. 【請求項１８】 以下の構成を含むスイッチシステム時
    分割多重バス；バスに接続されており、バスの時分割多
    重によってアクセスされるメモリー部；データのパケッ
    トの境界を知ることなく、パケットのデータを、バスを
    通じてメモリー部に読み込み、書き込むためのメカニズ
    ム。
19. 【請求項１９】 以下の構成を含むスイッチシステム：
    ある幅を持つ時分割多重キャリア部と；該キャリア部に
    接続されたメモリー部と；パケットのデータが時分割多
    重によってバスの幅を満たすよう、パケットのデータを
    メモリー部(22)に供給するための、ある幅を持った入力
    段部であって、バス幅は入力段部の幅の非整数倍であ
    る。
20. 【請求項２０】 パケットを切り換えるための以下の工
    程を含む方法：最初のパケットと、少なくとも２番目の
    パケットとをスイッチ部で受け取り；パケットからのデ
    ータがバス幅の所定の割合を満たすように、最初のパケ
    ットと２番目のパケットをバスの時分割多重によってメ
    モリー部に送り；バスの幅はどのパケットにも含まれて
    いるデータの関数に必ずしもなっていない。
21. 【請求項２１】 バスの幅は、パケットの大きさの非整
    数倍である、請求項２０に規定された方法。
22. 【請求項２２】 送信の工程は、最初のパケットと少な
    くとも２番目のパケットを待ち行列群の入力段に配置す
    る工程と、待ち行列群の入力段にあるデータを、バスで
    割り当てられたタイムスロットの間に、データがバス幅
    の所定の割合を満たすように、メモリー部に送る工程を
    含む、請求項２１説明された方法。
23. 【請求項２３】 データを送る工程の前に、入力待ち行
    列群が少なくともバス幅の所定の割合を満たすに十分な
    データを持っているかどうかを、データがバスに送られ
    る前に決定する工程を含む、請求項２２に規定された方
    法。
24. 【請求項２４】 データを送る工程の前に、待ち行列群
    の入力段が少なくとも１つのキャッシュラインを持って
    いるかどうかを決定する工程を含む、請求項２３に規定
    された方法。