(57)【特許請求の範囲】
【請求項１】
各々が１つの出力ポートを有する少なくとも１つのラインカードであって、パケットを出力待ち行列で格納および配列するために設けられると共に、前記出力ポートにおける出力待ち行列の状態をアービタに通知するための少なくとも１つのフィードバック情報の単位を生成するためのポート制御を備えるラインカードと、
前記ラインカードの少なくとも１つに接続された少なくとも１つのスイッチカードであって、前記ラインカードの前記ポート制御から供給された前記フィードバック情報の単位にしたがって切換動作を行うクロスポイント・マトリックスと、前記ポート制御から通知された前記出力待ち行列の状態により前記クロスポイント・マトリックスを制御するための前記アービタとを備えるスイッチカードと、
を備えるパケット切換装置。
【請求項２】
前記パケット切換装置における入力ポートと出力ポートとの間での可能な組み合わせを記述するための状態マトリックスと、
入力ポートと出力ポートとの間での受け入れられた前記組み合わせが切換の後でマークされた決定マトリックスと、
フィードバック情報の単位を表示する１つの要素を備えるフィードバックベクトルであって、前記状態マトリックスでの前記可能な組み合わせを低減させるために、用いられるフィードバックベクトルと、
を備えることを特徴とする請求項１に記載のパケット切換装置。
【請求項３】
出力ポートと前記パケット切換装置の前記アービタとの間に、前記パケット切換装置の少なくとも１つの出力ポートの出力待ち行列の状態を前記アービタに通知する、少なくとも１つのリンクが設けられていることを特徴とする請求項１に記載のパケット切換装置。
【請求項４】
パケット切換装置用のラインカードであって、出力ポートと、出力待ち行列への入来データパケットを格納および配列すると共に、前記出力ポートの出力待ち行列の状態をアービタに通知するための少なくとも１つのフィードバック情報の単位を生成するためのポート制御と、を備えるラインカード。
【請求項５】
パケット切換装置用のスイッチカードであって、クロスポイント・マトリックスとアービタとを備え、前記アービタはラインカードの出力ポートから受信されたフィードバック情報の単位にしたがって前記クロスポイント・マトリックスを制御するために設けられ、前記フィードバック情報の単位はこのスイッチカードに接続された前記ラインカードの出力ポートの出力待ち行列の状態を表示する、スイッチカード。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のラインカードとスイッチカードとを備えるパケット切換装置に係り、特にアービタのフィードバック方法を備えるパケット切換装置に関する。
【０００２】
【従来の技術】
Ｒ．ショーネン（R. Schoenen）、Ｇ．ポスト（G. Post）およびＧ．サンダー（G. Sander）により、'９９ 年ブロードバンド・スイッチング・シンポジウムでの公知文献「１００％のスループットを有する入力待ち行列化されたスイッチ用の優先権を備える重み付けされたアービットレーション（仲裁）アルゴリズム」は、パケット切換装置の種々の重み付けされた切換アルゴリズムを比較している。この切換アルゴリズムは、パケット切換装置の同一の出力ポートを対象とした幾つかのパケットの衝突を防止すると共に、結果的にデータの損失および遅延を低減させるよう試みている。しかしながら、切換動作中の出力ポートの状態を考慮に入れる方法は、この公知文献の中では説明されていない。
【０００３】
【発明が解決しようとする課題】
したがって、この発明はその目的として、出力ポートでのパケットの形式におけるデータの切換に際して切換損失から自由となることを保証するようにすることにある。
【０００４】
【課題を解決するための手段】
上記の目的は、各々が１つの出力ポートを有する少なくとも１つのラインカードであって、パケットを出力待ち行列で格納および配列するために設けられると共に、前記出力ポートにおける出力待ち行列の状態をアービタに通知するための少なくとも１つのフィードバック情報の単位を生成するためのポート制御を備えるラインカードと、前記ラインカードの少なくとも１つに接続された少なくとも１つのスイッチカードであって、前記ラインカードの前記ポート制御から供給された前記フィードバック情報の単位にしたがって切換動作を行うクロスポイント・マトリックスと、前記ポート制御から通知された前記出力待ち行列の状態により前記クロスポイント・マトリックスを制御するための前記アービタとを備えるスイッチカードと、を備えるパケット切換装置によって達成される。
【０００５】
パケット切換装置は、幾つかのラインカードと、幾つかのスイッチカードとを備えている。ラインカードは、本質的な構成要素としてのポート制御を含んでいる。各ポート制御は、複数の並列のスイッチカードに接続されており、そのタスクは、優先権によりパケット切換装置に入来するパケットと、このパケット切換装置の所望の出力ポートを配列することである。優先権によるパケットとパケット切換装置のポート制御における所望の出力ポートとの配列は、仮想出力待ち行列（ＶＯＱ―virtual output queue―）として知られている。
【０００６】
ポート制御は、状態（ステータス）情報として知られる、仮想出力待ち行列を条件とする情報を有しており、この情報を規則的な間隔（インターバル）によりスイッチカードへと送る。
【０００７】
各スイッチカードは、クロスポイント・マトリックスおよびアービタを備えている。クロスポイント・マトリックスの構成は、パケットを切り換えるためのパケット切換装置の入力および出力ポート間で生成された新たな組み合わせと、アービタとにより、規則的な間隔で再決定される。
【０００８】
各ポート制御の出力では、データパケットがポート制御およびパケット切換装置を離れる前に待ち行列として緩衝（バッファ）されている。もしも出力ポートの動作速度がパケット切換装置の動作速度よりも低速であるならば、データパケットは、充分に迅速に出力ポートを離れることができず、待ち行列はデータパケットにより満杯になりすぎてしまう。
【０００９】
この出力ポートが待ち行列で満杯になりすぎることを入力ポートに通知するために、ポート制御はフィードバック情報の複数の単位を生成する。
【００１０】
このフィードバック情報の複数の単位を構成する情報の流れ、この情報の流れは出力ポートと入力ポートとの間のフィードバックで求められ、直接接続を介してではなく、直接でない（間接）接続を介して生成されている。直接接続により、例えば、フィードバック情報の複数の単位は、出力ポートからパケット切換装置を介して入力ポートへと送ることができる。間接接続により、出力ポートのポート制御により生成されたフィードバック情報の複数の単位は、アービタに送られる。このアービタは、受け入れられたフィードバック情報の複数の単位を集めて、これらを用いて入力ポートを出力ポートに結び付けるための決定を行なう。アービタからの結果は入力ポート（さらにまたクロスポイント・マトリックス）へと伝達されており、また、アービタからの結果は出力ポートからのフィードバック情報の複数の単位により影響を受けているので、暗黙のうちに、出力ポートのフィードバック情報の複数の単位が入力ポートへと流れることになる。
【００１１】
フィードバック情報の複数の単位は、フィードバックベクトル内のアービタにより保持され続けることが可能である。フィードバック情報の複数の単位を用いるならば、アービタは、パケット切換装置の入力ポートと出力ポートとの間の可能な結合を減少させる。フィードバックベクトルは、幾つかの構成要素を含んでおり、各構成要素はそれぞれのケースにおける出力ポートの状態を反映するフィードバック情報の単位を表現している。
【００１２】
スイッチングは、フィードバックベクトルにより発生している。パケット切換装置の状態マトリックスは出力ポートに対する入力ポートの各結合の重み付けを表示する幾つかの構成要素を含んでいる。出力ポートの対応する構成要素よりも少ないかまたはこれと等しい状態マトリックスの複数の構成要素は、スイッチングの際には考慮されていない。対応する入力ポートは、考慮されていない出力ポートに対してデータパケットを送ることができない。フィードバックベクトル内の対応する構成要素よりも大きい状態マトリックスの複数の構成要素は、スイッチングの際に考慮されている。
【００１３】
この発明はまた、出力ポートの待ち行列の状態をアービタに通知するための少なくとも１つのフィードバック情報の単位を生成するため、出力ポートおよびポート制御を備えるパケット切換装置用のラインカードに関するものである。
【００１４】
この発明はまた、出力ポートの待ち行列の状態に関してアービタに対する情報用に少なくとも１つのフィードバックの単位を生成するために、出力ポートとポート制御とを有する少なくとも１つのラインカードを有するパケット切換装置用のクロスポイント・マトリックスと、このクロスポイント・マトリックスを制御するアービタと、を備えるスイッチカードに関するものである。
【００１５】
【発明の実施の形態】
この発明は、発明を限定するものではない添付図面に示された実施形態の具体例を参照しながらさらに詳細に説明される。
【００１６】
図１に示されたパケット切換装置は、２つのラインカード１および２と、幾つかのスイッチカード３〜５より構成される。ラインカード１および２の数は、しばしば２つよりもずっと大きくなり、例えば６４であるが、この実施形態の具体例においては、分かり易くするために２つに限定している。ラインカード１および２は、この実施形態の具体例の説明とは関係のない、したがって図示されていない異なる構成要素より構成されており、それは例えば、光送信ユニット、フレーム生成器、ネットワークプロセッサ等や、実施形態の具体例にとっては本質的なものであるポート制御６および７である。スイッチカード３ないし５のそれぞれは、クロスポイント・マトリックス８とアービタ９とより構成されている。それぞれの並列スイッチカード３ないし５におけるアービタ９およびクロスポイント・マトリックス８の両者は、ポート制御６および７のそれぞれに接続されている。
【００１７】
一定の長さのデータパケットはセルとして知られており、切り換え動作に用いられている。一定の長さのセルはパケットのサイズを変化させることよりも切り換える方法の方がより容易であるので、入来するパケットは、ラインカード１および２の中で一定の長さの複数のセルに分割され、一時的に出力待ち行列の中で保持される。成功した切り換え動作、すなわち、入力ポートのそれぞれの出力ポートへの許容される割り当ての後に、複数のセルは出力待ち行列から取り外される。
【００１８】
重み付けを用いるならば、ポート制御はアービタに対して、入力ポート内のセルが切り換えられるべきか、および、どのくらい緊急に切り換えられるべきかを通知する。重み付けは、優先権に関するデータやパケットの等級（クラス）または入力ポート内の待ち行列の待ち時間やサイズを含んでいても良い。
【００１９】
ポート制御６および７は、アービタ９に対する重み付けを含むクロスポイント・マトリックスの構成を決定するために必要となる情報を送っている。この情報は、入力ポートおよび出力ポートの両方の状態を説明する幾つかの情報の単位を含んでいる。もしも、パケット切換装置の出力ポート内で、更なるセルのためのそれ以上の容量がないのであるならば、このことは、この構成を決定する際にアービタにより考慮される。
【００２０】
アービタがクロスポイント・マトリックス８の構成を決定してしまってこの構成をポート制御およびクロスポイント・マトリックスの両方へ送ったときには、それぞれのスイッチカードのクロスポイント・マトリックス８はそれに応じて構成される。ポート制御６および７は、セル期間として知られる規則的な間隔で、切り換え動作のためにクロスポイント・マトリックス８へセルを送っている。
【００２１】
図２は、出力ポートのメモリ１０の異なる状態を示している。出力ポート内のセルの出力待ち行列は、共通のメモリにより生成される。出力ポート内で容易に役にたつメモリのサイズは、複数のセルが出力ポートに対して対応する優先権により切り換えられることに従って、ガイドライン値として解釈されることができる。
【００２２】
メモリ状態は、幾つかのステージ１１ないし１５に分割されている。このメモリは、メモリの状態がステージ１１に達したときに空（エンプティ―empty―）になる。メモリの状態がステージ１２であるものと仮定したときには、このメモリはほとんど空である。メモリの状態がステージ１３に達したときには、このメモリは半分満たされ、ステージ１４は、ほとんど満杯の状態に対応している。ステージ１５では、このメモリは満杯であり、これ以上のセルを取り込むことはできない。
【００２３】
メモリの満杯およびほとんど満杯の状態（ステージ１４および１５）では、アービタ９がそれらの出力ポートに対してセルを切り換えることはない。もしもメモリが全くまたはほんの僅かなセルしか含んでいないならば、メモリ状態（ステージ１２および１３）は、空であるか、ほとんど空である。この場合、アービタは、この出力ポートに対して何れかの優先権によりセルを切り換えることができる。メモリの半分満たされた状態（ステージ１３）においては、アービタ９は、この出力ポートに対する低い優先権のためにセルを切り換えることがなく、高い優先権によりセルを切り換えることから自由なメモリの残りの部分を確保している。
【００２４】
フィードバック情報の複数の単位は、出力ポートのメモリの状態に関する情報を含んでいる。
【００２５】
図３は、４つの入力ポートＩ０ないしＩ３および４つの出力ポートＯ０ないしＯ３を備えるパケット切換装置の切り換え動作を説明している。状態マトリックス１６は、入力ポートＩ０ないしＩ３の出力ポートＯ０ないしＯ３へのそれぞれの結合の重み付けを示す１６の構成要素を含んでいる。もしもこれらのセルへの重付けが最小数のビット（１ビット）へと低減されたならば、状態マトリックス１６は、バイナリ形態（２値化）として情報の１つの項目のみを含む幾つかの１と幾つかの０より構成されており、すなわち、対応する入力ポート内で切り換え動作のために、セルが存在しているかしていないかである。切り換え動作１７の間に、アービタ９は結果としての結合を計算している。決定マトリックス１８内で、結果としての結合がマーク（印）を付けられる。
【００２６】
セルの切り換え動作は、パケット切り換え装置の入力ポートを出力ポートに結合させることを意味している。結合を決定する際に、アービタ９は状態マトリックス１６を用いており、この状態マトリックス１６から対応するアルゴリズムを用いる高く重付けされた結合（組み合わせ）を選択している。このアービタがそれぞれの入力ポートまたは出力ポートのための組み合わせを決定してしまったときには、これらの組み合わせは、決定マトリックス１８内でマークされると共にこの決定マトリックス１８にしたがって構成されたクロスポイント・マトリックス８内でもマークされる。
【００２７】
この発明に係る実施形態の具体例を説明するために、ＳＩＭＰアルゴリズムが決定アルゴリズムとして用いられる。状態マトリックスのコラムにより機能するこのアルゴリズムは、Ｒ．ショーネン（R. Schoenen）、Ｇ．ポスト（G. Post）、Ｇ．サンダー（G. Sander）により、'９９ 年ブロードバンド・スイッチング・シンポジウムでの公知文献「１００％のスループットを有する入力待ち行列化されたスイッチ用の優先権を備える重み付けされたアービットレーション（仲裁）アルゴリズム」にさらに詳細に説明されている。他のアルゴリズム、例えば、ロウ方向に機能するＴ−ＳＩＭＰアルゴリズムもまた、この具体例のために用いられても良い。
【００２８】
第１の出力ポートＯ０の状態マトリックス１６のコラムにおいて４つの値を有する構成要素は第１のコラムの他の構成要素よりも大きいので、この組み合わせは切り換え動作１７により許容されて決定マトリックス１８内でマークされる。第２の出力ポートＯ１では、次の組み合わせが、それぞれの出力ポートが受け入れられた組み合わせを有するまで、同じような過程を経て受け入れられている。１つの出力ポートは同時に２つの入力ポートと組み合わせ（結合させ）られることはできず、１つの入力ポートは２つの出力ポートへと割り当てられることはできない。このようなわけで、第１の出力ポートＯ０は、第３の入力ポートＩ２と結合され、第２の出力ポートＯ１は第１の入力ポートＩ０と結合され、第３の出力ポートＯ２は第４の入力ポートＩ４と結合され、第４の出力ポートＯ３は第２の入力ポートＩ１と結合されて、他の入力ポートの全てはもはやこのセル期間においては用いることができなくなる。
【００２９】
図４は、４つの入力ポートＩ０ないしＩ３および４つの出力ポートＯ０ないしＯ３を備えるパケット切換装置を示しており、この装置は、フィードバックベクトル１９を用いて実行されると共にセルが切り換えられたときに出力ポートでの待ち行列の状態を考慮するフィードバック方法を用いている。図３に示されている状態マトリックス１６、切り換え動作１７および決定マトリックス１８は、第２の状態マトリックス２０およびフィードバックベクトル１９により補足されている。フィードバックベクトル１９は、それぞれの構成要素が出力ポートの状態を反映するフィードバック情報単位を表示する４つの構成要素を含んでいる。状態マトリックス２０は、切り換え動作１７の間にフィードバックベクトルを用いて決定される状態マトリックス１６の構成要素を含んでいる。
【００３０】
切り換え動作の機能は、図３について説明された動作の機能に対応している。フィードバックベクトル１９を用いる点で相違しているだけである。出力ポートの対応する構成要素よりも少ないかまたはこれと等しくなった状態マトリックス１６の構成要素は、（図４に×印でマークされた）切り換え動作においては考慮されていない。対応する入力ポートＩ０ないしＩ３は、出力ポートＯ０ないしＯ３へセルを送ることができない。フィードバックベクトル１９における対応する構成要素よりも大きい状態マトリックス１６の構成要素は、切り換え動作の際に考慮される。フィードバックベクトル１９により決定されフィルタされたこれらの構成要素は、状態マトリックス２０内に見つけ出すことができる。
【００３１】
第１の出力ポートＯ０については、第１のコラム内の全ての構成要素がフィードバックベクトルの対応する構成要素よりも少ないかまたは等しいものであるので、入力ポートは切り換えられることができない。このようにして、状態マトリックス２０は第１のコラムには構成要素を含まなくなる。第２の出力ポートＯ１については、状態マトリックス１６２つの構成要素（５および６）が有用であるので、これら２つの構成要素は状態マトリックス２０としての第２のコラム内に見出すことができる。第３の出力ポートＯ２については、状態マトリックス１６のたった１つの構成要素のみが有用であるので、第３の入力ポートのみが切り換え動作のために考慮されると共に、状態マトリックス２０の第３のコラムに残されることになる。第４の出力ポートＯ３については、２つの構成要素が有用であり、これら２つの構成要素は結果的に状態マトリックス２０の第４のコラム内に書き留められる。
【００３２】
切り換え動作１７の間に、出力ポートＯ１は、状態マトリックス２０の構成要素を考慮する入力ポートＩ０に結合され、結果的には決定マトリックス１８にマークされる。入力ポートＩ０は既に第２の出力ポートＯ１に結合されるものとして受け入れられているので、第４の出力ポートＯ３は入力ポートＩ１とのみ結合することができる。
【図面の簡単な説明】
【図１】この発明の実施形態によるパケット切換装置を示す説明図である。
【図２】出力ポートにおけるメモリの状態を示す説明図である。
【図３】入力ポートと出力ポートとの結合に対する状態の表示と決定マトリックスとを示す説明図である。
【図４】フィードバックベクトルを備える入力ポートと出力ポートとの結合に対する状態の表示と決定マトリックスとを示す説明図である。
【符号の説明】
１、２  ラインカード
３〜５  スイッチカード
６、７  ポート制御
８  クロスポイント・マトリックス
９  アービタ
１６  状態マトリックス
１７  切り換え動作
１８  決定マトリックス
【図１】
0003929837.tif 000002
【図２】
0003929837.tif 000003
【図３】
0003929837.tif 000004
【図４】
0003929837.tif 000005