(57)【要約】そのスケジューリングタスクを、複数の出口制御ユニット１２に存在する複数の出口スケジューラ７８に分散させ、そのデータ記憶を複数のパケットバッファユニット１６に分散させ、スケジューラ７８とパケットバッファユニット１６が、高速リンクを介して相互接続されている共有メモリパケットスイッチファブリック１４。入口制御ユニット１０は、パケットを受信し、スイッチファブリック１４を構成する複数のパケットバッファユニット（ＰＢＵ）１６の１つにそれを送信する。受信するＰＢＵ１６は、パケットをメモリに格納し、メモリ情報を備えた通知メッセージを関係あるすべての出口制御ユニット１２に送信する。通知を受信する出口制御ユニット１２は、待ち行列の空き容量が十分にある場合、そのメモリ情報をその待ち行列に格納する。次いで出口制御ユニット１２は、パケットを将来要求する予定であることを示す予約メッセージを送信する。
2004526391.tif 000002
【特許請求の範囲】
【請求項１】
複数の入口制御ユニットと、複数の出口制御ユニットと、前記複数の入口制御ユニットおよび前記複数の出口制御ユニットに結合されているスイッチファブリックとを含むパケット交換システムであって、前記複数の入口制御ユニットによって受信されたパケットが、前記スイッチファブリックに格納され、各出口制御ユニットが、それぞれのスケジューリングアルゴリズムに従って、前記出口制御ユニットに宛てられたパケットを識別し、かつ前記スイッチファブリックにパケットを要求し、前記スイッチファブリックが、前記要求されたパケットを取り出し、パケットを宛先に転送するために前記要求する出口制御ユニットに送信することを特徴とするパケット交換システム。
【請求項２】
前記スイッチファブリックが、前記複数の入口制御ユニットから受信した前記パケットを格納するメモリをそれぞれ有する複数の記憶ユニットを含む、請求項１に記載のパケット交換システム。
【請求項３】
各入口制御ユニットが、擬似ランダムアルゴリズムに基づいて、パケットを格納するために前記複数の記憶ユニットのうちの１つを選択することをさらに特徴とする、請求項２に記載のパケット交換システム。
【請求項４】
前記擬似ランダムアルゴリズムが各記憶ユニットの負荷情報に基づいて変更される、請求項３に記載のパケット交換システム。
【請求項５】
前記スイッチファブリックが、格納されているパケットの少なくとも一部を取り出すのに使用できるアドレス情報を含む通知メッセージを、１つまたは複数の出口制御ユニットに送信することをさらに特徴とする、請求項１に記載のパケット交換システム。
【請求項６】
前記通知メッセージを受信する前記出口制御ユニットのそれぞれが、それぞれの待ち行列の充填レベルに基づいて、前記通知メッセージを破棄するか、前記通知メッセージに含まれている前記アドレス情報を前記待ち行列に格納するかを決定することをさらに特徴とする、請求項５に記載のパケット交換システム。
【請求項７】
前記アドレス情報を前記待ち行列に格納している出口制御ユニットが、前記格納されているパケットを将来要求する予定であることを示す予約メッセージを、前記スイッチファブリックに送信することをさらに特徴とする、請求項６に記載のパケット交換システム。
【請求項８】
前記アドレス情報をその待ち行列に格納している出口制御ユニットが、前記格納されているパケットを取り出すよう求める要求メッセージを前記スイッチファブリックに送信することをさらに特徴とする、請求項６に記載のパケット交換システム。
【請求項９】
前記出口制御ユニットによって送信される、前記格納されているパケットを取り出すことを求める要求メッセージがそれ以上ない場合、前記スイッチファブリックが前記格納されているパケットに関連する記憶域を解放する、請求項８に記載のパケット交換システム。
【請求項１０】
前記通知メッセージの内容が、前記格納されているパケットに関連するタグデータに基づいている、請求項５に記載のパケット交換システム。
【請求項１１】
前記タグデータが、前記通知メッセージを受信することになっている一群の出口制御ユニットを示すグループの表示を含む、請求項１０に記載のパケット交換システム。
【請求項１２】
前記１つまたは複数の出口制御ユニットが、前記グループの印を含む加入メッセージを前記スイッチファブリックに送信して、前記スイッチファブリックが、前記１つまたは複数の出口制御ユニットを前記グループの表示に関連付けできるようにする、請求項１０に記載のパケット交換システム。
【請求項１３】
前記スイッチファブリックが共有メモリスイッチファブリックである、請求項１に記載のパケット交換システム。
【請求項１４】
複数の入口制御ユニット、複数の出口制御ユニット、および前記複数の入口および出口制御ユニットに結合されているスイッチファブリックを含むパケット交換システムを介してパケットを送信する方法であって、
前記入口制御ユニットの１つを介してパケットを受信することと、
前記スイッチファブリックに前記パケットを格納することと、
前記スイッチファブリックを介して、前記格納されているパケットに関連するアドレス情報を含む通知メッセージを１つまたは複数の出口制御ユニットに送信することと、
前記スイッチファブリックで、前記１つまたは複数の出口制御ユニットによって送信された、前記アドレス情報を含む要求メッセージを受信することと、
前記アドレス情報に基づいて前記パケットを取り出すことと、
前記取り出されたパケットを各要求する出口制御ユニットに送信することと
を含む方法。
【請求項１５】
前記スイッチファブリックが、メモリをそれぞれ有する複数の記憶ユニットを含み、前記方法が、擬似ランダムアルゴリズムに基づいて、前記パケットを関連付けられたメモリに格納するために前記複数の記憶ユニットのうちの１つを選択することをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記擬似ランダムアルゴリズムが各記憶ユニットの負荷情報に基づいて変更される、請求項１５に記載の方法。
【請求項１７】
前記１つまたは複数の出口制御ユニットで前記通知メッセージを受信することと、
各受信する出口制御ユニットの待ち行列の充填レベルに基づいて、前記通知メッセージを破棄するか、前記通知メッセージに含まれる前記アドレス情報を前記待ち行列に格納するかを決定することをさらに含む、請求項１４に記載の方法。
【請求項１８】
予約メッセージを送信する出口制御ユニットが、前記格納されているパケットを将来要求する予定であることを示す前記予約メッセージを、前記スイッチファブリックに送信することをさらに含む、請求項１４に記載の方法。
【請求項１９】
前記出口制御ユニットによって送信される、前記格納されているパケットを取り出すことを求める要求メッセージがそれ以上ない場合は、前記格納されているパケットに関連する記憶域を解放することをさらに含む、請求項１４に記載の方法。
【請求項２０】
前記通知メッセージの内容が、前記格納されているパケットに関連するタグデータに基づいている、請求項１４に記載の方法。
【請求項２１】
前記タグデータがグループの表示を含み、前記スイッチファブリックで、前記グループの表示に関連する前記１つまたは複数の出口制御ユニットを識別して、前記通知メッセージを送信することをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記グループの表示を含む加入メッセージを前記スイッチファブリックに送信して、前記スイッチファブリックが、前記１つまたは複数の出口制御ユニットを前記グループの表示に関連付けできるようにすることをさらに含む、請求項２１に記載の方法。
【請求項２３】
前記スイッチファブリックが共有メモリスイッチファブリックである、請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にパケット交換システムに関し、より詳細には、スケジューリングを複数の出口スケジューラに分散させる共有メモリスイッチファブリック（ｆａｂｒｉｃ）に関する。
【背景技術】
【０００２】
データ通信スイッチのスイッチファブリックは、入口ポートから受信したデータパケットを出口ポートに移送して、そのパケットを宛先に転送することを容易にする。スイッチファブリックは、クロスバースイッチ、セルスイッチ、または共有メモリパケットスイッチとして実施することができる。他のタイプのスイッチファブリックと比較したときの共有メモリパケットスイッチの１つの利点は、高トラフィック負荷下での頑強性である。共有メモリパケットスイッチでは一般に、他のタイプのスイッチファブリックよりパケットロスが少なく、待ち時間が短い。
【０００３】
しかし、共有メモリパケットスイッチは、すべての出口ポートに宛てられたすべてのパケットのスケジューリング決定を行う単一の中央論理回路を使用する。ファブリックサイズが増大するにつれて、中央論理回路への負担も増大する。したがって、共有メモリパケットスイッチは、１００ギガビット／秒のデータ転送速度を超えるとしばしば拡張性を欠く。さらに、大規模なシステムの帯域幅を支持するのに必要な電気インターフェースの数によって、スイッチファブリックのサイズ拡大が阻まれている。
【０００４】
仮想出力待ち行列（ＶＯＱ）スケジューリングを実施するクロスバーファブリック、セルファブリック、または他のスイッチファブリックは、共有メモリパケットスイッチのサイズ以上にスケール調整することはできるが、頑強性を欠き、また高トラフィック負荷中、ＨＯＬブロッキング（ｈｅａｄ  ｏｆ  ｌｉｎｅ  ｂｌｏｃｋａｇｅ）を受けやすい。さらに、ＶＯＱスケジューリングを実施するスイッチファブリックは、単一の中央スケジューラに依存するのではなく、さまざまな入口スケジューラにスケジューリングタスクを分散させるが、各入口ポートが、出口ポートごとにそれ自体の出口待ち行列の組を維持しなければならず、作成し維持する必要のある待ち行列の数が増加するという欠点がある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって、高トラフィック負荷下でその頑強性を損なうことなく、容易にスケール調整可能なスイッチファブリックが必要である。
【課題を解決するための手段】
【０００６】
本発明は、スケジューリングタスクを複数の出口制御ユニットにある複数の出口スケジューラに分散させる、共有メモリパケットスイッチファブリックを対象とする。スイッチファブリックは、トラフィックの一部をそれぞれが管理するいくつかのスイッチ装置およびデータ記憶装置を含む。
【０００７】
一実施形態によれば、パケット交換システムは、複数の入口制御ユニット、複数の出口制御ユニット、および複数の入口制御ユニットおよび複数の出口制御ユニットに結合されているスイッチファブリックを含む。スイッチファブリックを使用して、複数の入口制御ユニットが受信したパケットを格納し、各出口制御ユニットは、そのそれぞれのスケジューリングアルゴリズムに従って、出口制御ユニットに宛てられたパケットを識別し、かつスイッチファブリックにパケットを要求する。スイッチファブリックは、要求されたパケットを取り出し、パケットを宛先に転送するために要求する出口制御ユニットに送信する。
【０００８】
別の実施形態によれば、スイッチファブリックは、通知メッセージを１つまたは複数の出口制御ユニットに送信し、各受信した出口制御ユニットは、そのそれぞれの待ち行列の充填レベル（ｆｉｌｌｉｎｇ  ｌｅｖｅｌ）に基づいて、通知メッセージを破棄するか、通知メッセージに含まれているメモリ情報を待ち行列に格納するかを決定する。そのそれぞれの待ち行列にメモリ情報を格納する出口制御ユニットは、格納されているパケットを将来要求する予定であることを知らせる予約メッセージを、スイッチファブリックに送信する。
【０００９】
メモリ情報をそのそれぞれの待ち行列に格納している出口制御ユニットは、格納されているパケットを取り出すよう求める要求メッセージを、スイッチファブリックに送信する。要求メッセージを受信したスイッチファブリックは、要求されたパケットを取り出し、送信する。さらなるパケットの要求が予想されない場合は、格納されているパケットに関連する記憶域が解放される。
【００１０】
したがって、本発明は、スイッチファブリックのサイズが大きくなるにつれて、単一の中央スケジューリング論理回路に負担をかける必要性をなくすものであることを理解されたい。スケジューリングアルゴリズムに従ってパケットを識別し、かつパケットをスイッチファブリックに、要求する複数の出口制御ユニットにスケジューリングタスクを分散させることによって、こうした負担がなくなり、スイッチファブリックを容易にスケール変更できるようになる。さらに、スイッチファブリックを共有メモリスイッチファブリックとして実装することによって、交換システムが、こうした共有メモリスイッチファブリックによって提供される頑強性を利用できるようになる。
【００１１】
本発明のこれらおよび他の特徴、態様、および利点は、以下の詳細な説明、特許請求の範囲、および添付の図面を併せ読めば、より十分に理解できよう。
【発明を実施するための最良の形態】
【００１２】
図１は、本発明の一実施形態によるパケット交換システムの概略ブロック図である。このシステムは、高速シリアルリンク１８ａ、ｌ８ｂを介してスイッチファブリック１４に結合されている、Ｍ個の入口制御ユニット（ＩＣＵ）１０およびＭ個の出口制御ユニット（ＥＣＵ）１２を含む。スイッチファブリック１４は、１つまたは複数のＩＣＵ１０から受信したパケットを格納しかつ転送する、Ｎ個のパケットバッファユニット（ＰＢＵ）１６から成る。
【００１３】
各ＩＣＵ１０は、１つまたは複数の結合される入力ポート２０を有し、各ＥＣＵは、１つまたは複数の結合される出力ポート２２を有することができる。さらに、各ＩＣＵおよびＥＣＵは、各ＩＣＵおよびＥＣＵが各ＰＢＵと通信できるように、各ＰＢＵ１６へのリンク１８ａ、ｌ８ｂを含む。一実施形態によれば、各ＩＣＵ／ＥＣＵ１０、１２の入力／出力ポート２０、２２は、ともに１０ギガビット／秒の総データ転送速度で伝送し、各リンク１８ａ、ｌ８ｂは、１ギガビット／秒のデータ転送速度で伝送する。
【００１４】
所与のときに、ＩＣＵ１０の全部または一部は、出力ポート２２の全部または一部に宛てられたデータパケットを受信する。それだけには限定されないが、パケットは、イーサネット（登録商標）フレーム、ＡＴＭセル、ＴＣＰ／ＩＰ、および／またはＵＤＰ／ＩＰパケットを含むことができ、また他のレイヤ２（データリンク／ＭＡＣレイヤ）、レイヤ３（ネットワークレイヤ）、またはレイヤ４（トランスポートレイヤ）データユニットを含んでいてもよい。ＩＣＵがパケットを受信すると、ＩＣＵは、格納するためにパケットをＰＢＵに転送する。ＰＢＵは、パケットをメモリに格納し、そのパケットの受信に関係がある可能性のあるすべてのＥＣＵに通知を送信する。受信したＥＣＵのその適切な待ち行列に十分なスペースがある場合、ＰＢＵからパケットを取り出すのに使用するメモリアドレスへの参照を待ち行列に入れ、予約メッセージと呼ばれる、アドレスへの参照が待ち行列に入れられていることを知らせる指示をＰＢＵに送信する。予約メッセージによりＰＢＵは、予約したすべてのＥＣＵから要求されるまで、パケットをメモリに保持するよう促され、その後でメモリが解放される。
【００１５】
パケットをその宛先に転送するときになったら、そのパケットを予約していたＥＣＵは、パケットを取り出すよう求める要求をＰＢＵ１６に送信する。ＰＢＵは、パケットを取り出し、要求したＥＣＵに送信し、要求したＥＣＵは、１つまたは複数の結合される出口ポートを介してパケットを転送する。
【００１６】
図２は、本発明の一実施形態によるＩＣＵ１０の例の概略ブロック図である。例示の実施形態のＩＣＵは、入口プロセッサ３２に結合されている入口データ記憶装置３０を含み、入口プロセッサ３２は、入口インターフェース３４に結合されている。入口データ記憶装置３０は、入ってくるデータパケットを受信し、一時的に格納する先入れ先出し（ＦＩＦＯ）バッファとすることができる。１つまたは複数の入口ポート２０のデータ転送速度が、ＰＢＵへの高速シリアルリンク１８ａのデータ転送速度より遅い場合または速い場合は、入口データ記憶装置３０が望ましい。しかし、ＩＣＵ１０が、入口データ記憶装置３０を含まない一実施形態が存在してもよい。
【００１７】
入口パケットプロセッサ３２は、監視、アカウンティング、転送、および当技術分野における従来のパケットに関する他の任意のパケット処理タスクを行う。さらに、入口パケットプロセッサ３２は、通知タグをパケットに添付し、パケットを受信し格納するためのスイッチファブリック内のＰＢＵ１６を選択する。本発明の一実施形態によれば、ＩＣＵ１０からＰＢＵ１６への各リンク１８ａは、その結合されるＰＢＵの負荷または充填レベルに基づいて動的に更新される重みに関連付けられている。入口パケットプロセッサ３２は、重み情報によって調整される擬似ランダムアルゴリズムに基づいて、リンク１８ａ、したがって結合されるＰＢＵを選択し、作業負荷のバランスが様々なＰＢＵ間で保たれるのを助ける。次いで添付の通知タグを備えるパケットは、入口インターフェース３４を介して選択されたリンク上に送信され、選択されたＰＢＵに格納される。様々なＰＢＵの負荷の更新は、高速シリアルリンク１８ａまたは個別の低速シリアル制御リンク（図示せず）を介して受信することができる。
【００１８】
図３は、本発明の一実施形態による、入口プロセッサ３２によって生成された通知タグ９２を含むデータパケット９０の概略構成図である。代替実施形態では、通知タグは、ＩＣＵ１０にパケットを送信する前にネットワークプロセッサによって生成される。
【００１９】
図３に示した実施形態によれば、通知タグは、フローグループフィールド９４、優先度フィールド９６、パケットバッファ番号（ＰＢＮ）フィールド９８、および任意の送信元識別子（ＳＩＤ）１００を含む。
【００２０】
フローグループフィールド９４は、パケットに関連付けられているフローグループを示すフローグループ番号を含む。本発明の一実施形態によれば、フローグループは、フローグループに加入しているＥＣＵのリストを含む。ＥＣＵは、その１つまたは複数の出口ポートがフローグループに属している場合、フローグループに加入する。ポートは、開始後、ハードウェアまたはソフトウェアのいずれかを介してフローグループ、およびそのパケットの出口ポートを決定するために入口で照会される転送表に含まれているこうした情報に関連付けられる。
【００２１】
優先度フィールド９４は、パケットに与えられるサービスの品質（ＱｏＳ）のタイプを示す、差別化サービスコードポイント（ＤＣＳＰ）値を示す。この情報は、パケットのヘッダデータから得られ、通知タグに含めることができる。
【００２２】
送信元識別子１００もまた通知タグに含まれており、これは、パケットが受信された入口ポートを示す。送信元識別子は、パケットのヘッダデータから得られることもできる。
【００２３】
ＰＢＮフィールド９８は、パケットを格納するために選択されたＰＢＵ１６の記憶域への参照を含む。通知タグの他のフィールドとは異なり、ＰＢＮフィールド９８は、こうした記憶域が識別されると、ＰＢＵ１６によって埋められる。
【００２４】
図４は、本発明の一実施形態によるＰＢＵ１６の例の概略ブロック図である。例示の実施形態のＰＢＵは、ＩＣＵ１０から受信したパケットを格納する中央メモリ４０を含む。
【００２５】
ＰＢＵ１６は、動的ランダムアクセスメモリ（ＤＲＡＭ）または静的ＲＡＭ（ＳＲＡＭ）として実施することができるＰＢＮバッファ４２をさらに含む。ＰＢＮバッファ４２への各エントリは、ＰＢＮアドレスと呼ばれる、パケットの少なくとも一部が格納されている中央メモリ４０へのポインタのアドレスを含む。本発明の一実施形態によれば、ＰＢＮアドレスは、パケットの異なる部分が格納されている記憶域へのポインタのリンクリストの第１のポインタのアドレスである。
【００２６】
ＰＢＵバッファ４２に格納されている各ＰＢＮアドレスは、リンク１８ｂ、およびそれらの対応するＥＣＵを反映している複数の予約ビットと関連付けられる。こうしたＥＣＵは、ＰＢＮアドレスへの参照を対応する待ち行列にローカルに入れ、予約動作を介して、ＰＢＮアドレスに関連付けられているパケットの受信と関係があることを知らせている。各予約ビットは、任意に、ＰＢＮアドレスに関して受信された予約数を示す予約カウントと関連付けることもできる。
【００２７】
ＰＢＮバッファ４２は、中央メモリ４０の空き記憶容量を制御するメモリマネージャ４４に結合され、中央メモリに格納する必要のある新しいパケットに空き記憶容量を割り当て、中央メモリからパケットを取り出すのを手伝う。空きＰＢＮ記憶装置（ｆｒｅｅ  ＰＢＮ  ｓｔｏｒｅ）４６は、新しく入ってくるパケットに割り振ることができる空き記憶域の追跡を維持するために使用する。
【００２８】
ＰＢＵ１６は、フローグループ（ＦＧＲＰ）加入表（ｓｕｂｓｃｒｉｐｔｉｏｎ  ｔａｂｌｅ）５０に結合されている中央通知論理回路４８も含む。ＦＧＲＰ加入表５０は、特定のフローグループごとに、フローグループに加入しているＥＣＵを示す。一実施形態によれば、中央通知論理回路４８は、入ってくるパケットに関連付けられているフローグループを決定し、そのフローグループに加入しており、したがってパケットの受信と関係があるＥＣＵに通知を送信する。本発明の一実施形態によれば、通知は、入ってくるパケットに添付されている通知タグのすべてまたは一部である。
【００２９】
ＰＢＵ１６はさらに、高速シリアルリンク１８ａ、１８ｂを介してＩＣＵ１０およびＥＣＵ１２と通信するスイッチインターフェース５２を含む。スイッチインターフェース５２は、ＩＣＵ１０およびＥＣＵ１２から異なるタイプのパケットを受信し、異なるタイプのパケットを分けてＰＢＵ内の適切な構成要素に転送する。
【００３０】
例えば、スイッチインターフェース５２は、入ってくる通知タグ付きのパケットをＩＣＵ１０から受信する。通知タグは、データパケットから取り除かれ、中央通知論理回路４８に送信されてＰＢＮフィールド９８を完成させ、通知タグのすべておよび一部が、通知メッセージとして適切なＥＣＵ１２に送信される。パケットのデータ部分は、中央メモリ４０に送信されて格納される。
【００３１】
スイッチインターフェース５２はさらに、予約メッセージおよびパケット要求メッセージをＥＣＵ１２から受信する。これらはＥＣＵのパケットを予約する、あるいは取り出すためにメモリマネージャ４４に転送される。また、スイッチインターフェース５２は、特定のフローグループに加入するおよび加入を取り消す、加入メッセージおよび加入取消メッセージ（ｕｎｓｕｂｓｃｒｉｐｔｉｏｎ  ｍｅｓｓａｇｅ）も受信する。加入メッセージおよび加入取消メッセージは、ＦＧＲＰ加入表５０を更新するために中央通知論理回路４８に送信される。
【００３２】
図５は、本発明の一実施形態によるＰＢＮバッファ４２の概略構成図である。ＰＢＮバッファは、複数のエントリを含んでおり、各エントリは、ＰＢＮエントリ番号６０、複数の関連する予約ビット６２、およびＰＢＮアドレス６４を含む。新しいパケットが中央メモリ４０に格納されると、新しいエントリが、メモリマネージャによってＰＢＮバッファに追加される。
【００３３】
ＰＢＮエントリ番号６０（ＰＢＮへの参照とも呼ぶ）は、予約ビット６２および関連するＰＢＮアドレス６４への参照として使用される。一実施形態によれば、ＰＢＮエントリ番号６０は、通知タグ９２のＰＢＮフィールド９８に格納される。
【００３４】
ＰＢＮアドレス６４（単にＰＢＮとも呼ぶ）は、特定のパケットの異なる部分を格納する記憶域へのポインタのリンクリストの開始アドレスである。
【００３５】
予約ビット６２は、関連するＰＢＮエントリ番号を出口待ち行列に入れることによって、パケットを予約しているＥＣＵ１２を示す。一実施形態によれば、各予約ビットが特定のＥＣＵに関連付けられる。各ビットは、対応するＥＣＵから予約メッセージを受信すると設定され、そのＥＣＵから解除ビット指示（ｒｅｌｅａｓｅ  ｂｉｔ  ｉｎｄｉｃａｔｉｏｎ）付きのパケット要求メッセージを受信すると設定解除される。
【００３６】
図６は、本発明の一実施形態による、各ＰＢＵにあるＦＧＲＰ加入表５０の概略構成図である。表は、フローグループ番号７０、または他の任意のタイプの識別子、およびグループに加入しているＥＣＵ１２を示す複数の加入ビット７２を含んでいることが好ましい。本発明の一実施形態によれば、各加入ビットは、特定のＥＣＵに関連付けられている。各ビットは、対応するＥＣＵから加入メッセージを受信すると設定され、対応するＥＣＵから加入取消メッセージを受信すると設定解除される。ＦＧＲＰ加入表５０の加入情報を使用して、パケットの受信に関係があり、したがってＰＢＵから通知メッセージを受信することになっている、入ってくるパケットで示されるフローグループに加入するＥＣＵが決定される。特定のフローグループへの加入および加入取消は、ハードウェアまたはソフトウェアで行うことができる。
【００３７】
図７は、本発明の一実施形態によるＥＣＵ１２の例を示す概略ブロック図である。例示の実施形態によれば、ＥＣＵ１２は、高速シリアルリンク１８ｂを介してＰＢＵ１６と通信する出口インターフェース７０を含む。出口インターフェース７０は、異なるタイプのパケットをＰＢＵから受信し、それらのパケットを処理し、適切な出口構成要素に転送する。
【００３８】
本発明の一実施形態によれば、出口インターフェース７０は、１つまたは複数の出口ポート２２を介して転送する前に、パケットを一時的に格納する出口データ記憶装置７２に、ＰＢＵから取り出したデータパケットを送信する。出口データ記憶装置７２は、先入れ先出し（ＦＩＦＯ）バッファとして実装することができる。１つまたは複数の出口ポート２２のデータ転送速度が、ＰＢＵからの高速シリアルリンク１８ｂのデータ転送速度より低い場合または高い場合は、出口データ記憶装置７２が望ましい。しかし、ＥＣＵ１２が、出口データ記憶装置７２を含んでいない実施形態が存在してもよい。
【００３９】
出口インターフェース７０はさらに、ＰＢＵ１６から通知メッセージパケットを受信し、出口通知論理回路７４にそれらを転送する。本発明の一実施形態によれば、通知メッセージは、ＰＢＵが受信したパケットに添付されている通知タグである。それに応答して出口通知論理回路７４は、通知メッセージに関連付けられているパケットを予約するか破棄するかを決定する。これに関して、出口通知論理回路７４は、通知メッセージで転送されるフローグループ番号に基づいてパケットを転送すべき出口ポート２２を決定する。出口通知論理回路７４は、フローグループ情報に関してＦＧＲＰポート表８０に問合せを行い、示されたフローグループと関連付けられる１つまたは複数の出口ポート２２を決定する。
【００４０】
出口通知論理回路７４は、加入されたポートに関連する出口待ち行列７６の待ち行列レベルを決定する。現在使用されている輻輳制御アルゴリズムに基づいて待ち行列レベルが高すぎると決定されると、通知は破棄される。
【００４１】
そうではなく、パケットを待ち行列に入れることが可能な場合、出口通知論理回路７４によって、通知メッセージで送信されるＰＢＮへの参照が、通知メッセージのフローグループフィールド９４、および優先度フィールド９６に基づいて選択された出口待ち行列７６に入れられる。出口通知論理回路７４はさらに、ＰＢＮへの参照が待ち行列に入れられたことを示す通知メッセージを送信したＰＢＵ１６に予約メッセージを送信する。一実施形態によれば、予約メッセージは、予約されるパケットを一意に識別する少なくともＰＢＮへの参照を含む。ＥＣＵは、たとえ１つを超える出口ポートが、ＦＧＲＰフィールド９４で示されるフローグループに加入されている場合でも、単一の予約要求を送信する。ただし、パケットが複数のＥＣＵによって送信されることになっている場合、ＰＢＵは、同じＰＢＮについての複数の予約要求を受信することができる。
【００４２】
ＥＣＵ１２は、例えば重み付けされたラウンドロビンアルゴリズム、クラスベースのデキューなど、特定のスケジューリングアルゴリズムに従って、参照ＰＢＮを各出口待ち行列７６から取り出す出口スケジューラ７８を含む。待ち行列に入れられたＰＢＮへの参照に関連付けられているパケットが、スケジューリング機構によって決められているように転送されるよう予定されているとき、出口通知論理回路７４は、パケット要求メッセージをＰＢＵに送信する。一実施形態によれば、パケット要求メッセージは、ＰＢＮへの参照および解除ビットを含む。解除ビットが設定されている場合、解除ビットは、その要求がそのパケットに関する最後の要求であることを示し、パケットの予約ビットをクリアできるようにする。要求メッセージで示されるパケットは、ＰＢＵによって取り出され、要求側ＥＣＵに送信される。次いでパケットは、１つまたは複数の適切な出口ポートを介して転送される。
【００４３】
図８は、本発明の一実施形態による図２のＩＣＵ１０の例によって実行される処理ステップを示すプロセスフロー図である。プロセスが開始し、ステップ１１０で、入口ポート２０は、入ってくるデータパケットを受信する。ステップ１１２で、入口プロセッサ３２は、通知タグを生成し、パケットにそのタグを添付する。ステップ１１４で、入口プロセッサは、各ＰＢＵに関連付けられた重みによって調整される、当技術分野における従来の擬似ランダムアルゴリズムに基づいてＰＢＵ１６を選択する。ステップ１１６で、ＩＣＵは、通知タグを備えるデータパケットを選択されたＰＢＵに転送する。
【００４４】
ＩＣＵ１０はさらに、関連する高速シリアルリンク１８ａまたは個別制御リンク（図示せず）を介して、ＰＢＵ１６からフィードバックパケットを受信する。一実施形態によれば、フィードバックパケットは、送信側ＰＢＵの負荷を示す。ステップ１１３で、負荷情報を使用して、次に入ってくるパケットを受信すべきＰＢＵの決定に使用する、各ＰＢＵに関連する重みを変更する。
【００４５】
図９は、本発明の一実施形態による図４のＰＢＵ１６によって実行される処理ステップを示すプロセスフロー図である。プロセスが開始し、ステップ１２０で、ＰＢＵはＩＣＵまたはＥＣＵによって送信されるパケットを受信する。ステップ１２２で、パケットが、ＩＣＵによって送信されたデータパケットであるかどうかについての決定が行われる。パケットがデータパケットの場合、ステップ１２４で、パケットに添付されている通知タグがスイッチインターフェース５２によって取り除かれる。通知タグは、中央通知論理回路４８に送信され、データパケットはメモリマネージャ４４に送信される。
【００４６】
ステップ１２６および１２８で、メモリマネージャ４４は、使用可能な記憶域へのＰＢＮアドレスに関して空きＰＢＮ記憶装置４６に問合せを行い、パケットのすべてまたは一部をその記憶域に格納する。記憶域へのポインタのリンクリストが、ＰＢＮアドレスに基づいて生成され、残りの任意の部分のパケットが記憶域に格納される。ステップ１３０で、ＰＢＮアドレスは、ＰＢＮバッファ４２に格納される。
【００４７】
次いで中央通知論理回路４８は、パケットの通知タグによって示されるフローグループに加入しているＥＣＵ１２に、新しく到着したパケットの通知を送信する。この点について、ステップ１３２で、中央通知論理回路４８は、通知タグからフローグループ番号を取り出す。ステップ１３４で、中央通知論理回路４８は、ＦＧＲＰ加入表５０に問合せを行い、示されたフローグループに属するＥＣＵを識別する。ステップ１３６で、中央通知回路４８は次に、通知タグを通知メッセージとして識別されたＥＣＵに送信する。
【００４８】
ステップ１４０を参照すると、受信したパケットが、ＥＣＵから要求されるまで、ＰＢＵがパケットをメモリに維持すべきであることを指示するＥＣＵからの予約メッセージである場合、その予約メッセージは、メモリマネージャ４４に転送される。メモリマネージャは、メッセージを送信するＥＣＵ、および予約すべきパケットのＰＢＮエントリ番号を決定する。ステップ１４２で、対応するＰＢＮエントリ番号およびＥＣＵの予約ビットが、ＰＢＮバッファ４２に設定される。
【００４９】
ステップ１４６で、受信したパケットが、ＥＣＵからのパケット要求メッセージであると決定されると、パケットはメモリマネージャ４４に転送される。メモリマネージャ４４は、メッセージに示されたＰＢＮエントリ番号に基づいてＰＢＮアドレスを取り出し、ＰＢＮアドレスを記憶域へのポインタのリンクリストの開始アドレスとして使用し、ステップ１４８で記憶域に格納されている内容を取り出す。
【００５０】
メモリマネージャはさらに、ステップ１５２で、解除ビットをパケット要求メッセージに設定するかどうかを決定する。回答がＹＥＳの場合、この特定のＥＣＵからはそれ以上のパケット要求は期待されず、ステップ１５４で、ＥＣＵのＰＢＮに関連する予約ビットの設定が解除される。
【００５１】
ステップ１５６で、すべての予約ビットがクリアされるかどうかの決定が行われる。回答がＹＥＳの場合、そのパケットについてそれ以上の要求は期待されず、ステップ１５８で、ＰＢＮアドレスおよび関連する記憶域が解放される。解放されたＰＢＮはさらに、ステップ１６４で空きＰＢＮ記憶装置に戻される。
【００５２】
代替実施形態では、予約ビットをクリアして記憶域を解放する解除ビットではなく、予約メッセージを受信すると増加し、特定のＰＢＮエントリのパケット要求メッセージを受信すると減少する予約カウントが、ＰＢＮエントリごとに維持される。予約カウントが０に到達すると、ＰＢＮアドレスに関連する記憶域が解放される。
【００５３】
次にステップ１６０を参照すると、受信されたパケットが加入メッセージの場合、そのメッセージは、フローグループ番号をメッセージから取り出す中央通知論理回路４８に中継される。次いで中央通知論理回路は、示されたフローグループの送信側制御ユニットの加入ビットを設定する。
【００５４】
図１０は、本発明の一実施形態による図７のＥＣＵ１２によって実行される処理ステップを示すプロセスフロー図である。プロセスが開始し、ステップ１７０で、出口スケジューラ７８は、スケジューリングアルゴリズムを実行して、その出口ポート２２を介してパケットを転送する。ステップ１７２で、出口スケジューラ７８は、スケジューリングアルゴリズムに基づいて待ち行列を選択し、ステップ１７４で、待ち行列のパケット要求を送信する。
【００５５】
ステップ１７６で、ＥＣＵ１２は、入ってくるパケットを受信し、ステップ１７８および１５６で、パケットが通知パケットであるかデータパケットであるかに関する決定が行われる。パケットがＥＣＵによって要求されたデータパケットの場合、そのパケットは、ステップ１９０で出口ポート２２を介して宛先に転送される。
【００５６】
パケットが通知パケットの場合は、出口通知論理回路７４に転送されて、出口通知論理回路７４は、ステップ１８０で、通知からＰＢＮエントリ番号、フローグループ番号、および優先度情報が取り出す。ステップ１８２で、出口通知論理回路は、フローグループポート表８０に問合せを行い、示されたフローグループおよび優先度に関連する１つまたは複数の出口待ち行列７６を識別する。ステップ１８４で、識別された待ち行列の充填レベルが高すぎるかどうかについての決定が行われる。回答がＹＥＳの場合、充填レベルが高すぎる待ち行列ごとに通知が破棄される。
【００５７】
少なくとも１つの待ち行列に関して回答がＮＯの場合、ステップ１８６で、識別された待ち行列について、ＰＢＮエントリ番号に関連するパケットを予約する予約要求が送信される。ステップ１８８で、ＰＢＮエントリ番号は、充填レベルによって待ち行列に入れることが許可されている各待ち行列に入れられる。
【００５８】
本発明は、ある特定の実施形態について説明されてきたが、当分野の技術者であれば、本発明の範囲および意図から逸脱することなく変更形態を考案することは難しくない。したがって、本発明は、具体的に記載したものとは別の方法で行うことができることを理解されたい。したがって、本発明の本実施形態は、あらゆる点において、例示のために示したものにすぎず、本発明を限定するものではなく、本発明の範囲は、上記の説明ではなく、特許請求の範囲、およびその均等物によって示されるものとみなすべきである。
【図面の簡単な説明】
【００５９】
【図１】本発明の一実施形態による、Ｍ個の入口制御ユニット、Ｎ個のパケットバッファユニット、およびＭ個の出口制御ユニットを有する、パケット交換システムの概略ブロック図である。
【図２】本発明の一実施形態による入口制御ユニットの例の概略ブロック図である。
【図３】本発明の一実施形態による図２の入口制御ユニットによって生成される、通知タグを含むデータパケットの概略構成図である。
【図４】本発明の一実施形態によるパケットバッファユニットの例の概略ブロック図である。
【図５】本発明の一実施形態による図４のパケットバッファユニットにおけるＰＢＮバッファを示す概略構成図である。
【図６】本発明の一実施形態による図４のパケットバッファユニットにあるＦＧＲＰ加入表を示す概略構成図である。
【図７】本発明の一実施形態による出口制御ユニットの例の概略ブロック図である。
【図８】本発明の一実施形態による図２の入口制御ユニットによって実行される処理ステップを示すプロセスフロー図である。
【図９】本発明の一実施形態による図４のパケットバッファユニットによって実行される処理ステップを示すプロセスフロー図である。
【図１０】本発明の一実施形態による図７の出口制御ユニットによって実行される処理ステップを示すプロセスフロー図である。
【図１】
2004526391.tif 000003
【図２】
2004526391.tif 000004
【図３】
2004526391.tif 000005
【図４】
2004526391.tif 000006
【図５】
2004526391.tif 000007
【図６】
2004526391.tif 000008
【図７】
2004526391.tif 000009
【図８】
2004526391.tif 000010
【図９】
2004526391.tif 000011
【図１０】
2004526391.tif 000012
【国際公開パンフレット】
2004526391.tif 000013
2004526391.tif 000014
2004526391.tif 000015
2004526391.tif 000016
2004526391.tif 000017
2004526391.tif 000018
2004526391.tif 000019
2004526391.tif 000020
2004526391.tif 000021
2004526391.tif 000022
2004526391.tif 000023
2004526391.tif 000024
2004526391.tif 000025
2004526391.tif 000026
2004526391.tif 000027
2004526391.tif 000028
2004526391.tif 000029
2004526391.tif 000030
2004526391.tif 000031
2004526391.tif 000032
2004526391.tif 000033
2004526391.tif 000034
2004526391.tif 000035
2004526391.tif 000036
2004526391.tif 000037
【国際調査報告】
2004526391.tif 000038