(57)【要約】【課題】【解決手段】第１のデータレートにより特徴付けられる複数の受信ポート及び複数の送信ポートを有する共有メモリについて説明する。メモリは、行及び列で編成された複数のメモリバンクを含む。メモリアレイの動作は、第２のデータレートにより特徴付けられる。ノンブロッキング受信クロスバー回路は、任意の受信ポートを任意のメモリバンクに接続する働きをする。ノンブロッキング送信クロスバー回路は、任意のメモリバンクを任意の送信ポートに接続する働きをする。バッファリングは、第１のデータレートでの受信及び送信ポートの動作を、第２のデータレートでのメモリアレイの動作から切り離す働きをする。スケジューリング回路は、ポートと、クロスバー回路と、メモリアレイとの相互作用を制御し、共有メモリ内のデータセグメントの格納及び検索を達成する働きをする。スケジューリング回路は、更に、行の一つのメモリバンク全体における、フレームの各データセグメントのストライピングを容易にし、アレイの連続行全体における、フレームの連続データセグメントのストライピングを容易にする働きをする。【選択図】図１
2008527922.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリであって、
第１のデータレートにより特徴付けられる複数の受信ポートと、
前記第１のデータレートにより特徴付けられる複数の送信ポートと、
行及び列で編成された複数のメモリバンクを含み、第２のデータレートにより動作が特徴付けられるメモリアレイと、
任意の前記受信ポートを任意の前記メモリバンクに接続する働きをするノンブロッキング受信クロスバー回路と、
任意の前記メモリバンクを任意の前記送信ポートに接続する働きをするノンブロッキング送信クロスバー回路と、
前記第１のデータレートでの前記受信及び送信ポートの動作を、前記第２のデータレートでの前記メモリアレイの動作から切り離す働きをするバッファリングと、
前記ポート、クロスバー回路、及びメモリアレイの相互作用を制御し、前記共有メモリ内のデータセグメントの格納及び検索を達成する働きをし、前記行の一つの前記メモリバンク全体における、フレームの各データセグメントのストライピングを容易にし、前記アレイの連続行全体における、前記フレームの連続データセグメントのストライピングを容易にする働きをするスケジューリング回路と
を備える共有メモリ。
【請求項２】
前記受信及び送信クロスバー回路の動作は、第３のデータレートを特徴とし、前記バッファリングは、各受信ポートと前記受信クロスバー回路との間の第１のバッファと、各送信ポートと前記送信クロスバー回路との間の第２のバッファとを含み、前記第１及び第２のバッファは、前記第１のデータレートでの前記受信及び送信ポートの動作を、前記第３のデータレートでの前記受信及び送信クロスバー回路の動作から切り離す働きをする請求項１記載の共有メモリ。
【請求項３】
前記第１のバッファのそれぞれは、フレームのセグメント全体を格納する働きをする請求項２の共有メモリ。
【請求項４】
前記第２のバッファのそれぞれは、前記共有メモリの全てのジッタを捕らえるのに十分な大きさである請求項２記載の共有メモリ。
【請求項５】
前記受信及び送信クロスバー回路の動作は、第３のデータレートを特徴とし、前記バッファリングは、前記受信クロスバー回路と前記メモリバンクのそれぞれとの間の第１のバッファと、前記送信クロスバー回路と前記メモリバンクのそれぞれとの間の第２のバッファとを含み、前記第１及び第２のバッファは、前記第２のデータレートでの前記メモリアレイの動作を、前記第３のデータレートでの前記受信及び送信クロスバー回路の動作から切り離す働きをする請求項１記載の共有メモリ。
【請求項６】
前記スケジューリング回路は、前記受信クロスバー回路の連続出力ポートを介して各データセグメントの各連続ワードを送信するように前記受信クロスバー回路を制御することで、行内の前記メモリバンク全体での各データセグメントのストライピングを容易にする働きをする請求項１記載の共有メモリ。
【請求項７】
仲裁の決定は、前記受信クロスバー回路により、データセグメントにつき一度のみ行われる請求項６記載の共有メモリ。
【請求項８】
前記スケジューリング回路は、前記送信クロスバー回路の連続入力ポートを介して各データセグメントの各連続ワードを受信するように前記送信クロスバー回路を制御する働きをする請求項１記載の共有メモリ。
【請求項９】
仲裁の決定は、前記送信クロスバー回路により、データセグメントにつき一度のみ行われる請求項８記載の共有メモリ。
【請求項１０】
前記スケジューリング回路は、各フレームの最初のセグメントをストライピングするために、前記メモリバンクの行の第１のものを選択する働きをし、前記第１の行の選択は、疑似乱数的又は決定論的に実行される請求項１記載の共有メモリ。
【請求項１１】
前記第１の行の前記選択は、決定論的に実行され、前記第１の行は、前記メモリバンクの行の中から、線形順序で選択される請求項１０記載の共有メモリ。
【請求項１２】
前記第１の行の前記選択は、決定論的に実行され、前記第１の行は、前記メモリバンクの行の中から、割り当て頻度の最も低いものに関するアルゴリズムに従って選択される請求項１０記載の共有メモリ。
【請求項１３】
前記受信クロスバー回路及び前記送信クロスバー回路のそれぞれは、複数の段階に配置された複数のクロスバーを備える請求項１記載の共有メモリ。
【請求項１４】
前記受信クロスバー回路の前記複数のクロスバーは、複数の入力クロスバーを備え、前記共有メモリの前記受信ポートのそれぞれは、前記入力クロスバーの一つに関連する請求項１３記載の共有メモリ。
【請求項１５】
前記複数の入力クロスバーは、等しいサイズの二つの入力クロスバーを備え、前記受信ポートの半分は、前記入力クロスバーのそれぞれに関連する請求項１４記載の共有メモリ。
【請求項１６】
前記送信クロスバー回路の前記複数のクロスバーは、複数の出力クロスバーを備え、前記共有メモリの前記受信ポートのそれぞれは、前記出力クロスバーの一つに関連する請求項１３記載の共有メモリ。
【請求項１７】
前記複数の出力クロスバーは、等しいサイズの二つの出力クロスバーを備え、前記送信ポートの半分は、前記出力クロスバーのそれぞれに関連する請求項１６記載の共有メモリ。
【請求項１８】
前記受信クロスバー回路は、前記受信ポートのそれぞれに関連する入力と、前記メモリアレイ内の前記列のそれぞれに関連する出力とを有する少なくとも一つの入力クロスバーを備え、更に、それぞれが前記メモリアレイ内の前記列の少なくとも一つに関連し、前記入力クロスバー出力の少なくとも一つを前記関連列内の前記メモリバンクに接続する働きをする複数の列クロスバーを備える請求項１３記載の共有メモリ。
【請求項１９】
前記送信クロスバー回路は、前記送信ポートのそれぞれに関連する出力と、前記メモリアレイ内の前記列のそれぞれに関連する入力とを有する少なくとも一つの出力クロスバーを備え、更に、それぞれが前記メモリアレイ内の前記列の少なくとも一つに関連し、前記出力クロスバー入力の少なくとも一つを前記関連列内の前記メモリバンクに接続する働きをする複数の列クロスバーを備える請求項１３記載の共有メモリ。
【請求項２０】
更に、前記メモリアレイ内での前記データセグメントの格納を達成する際に、前記スケジューリング回路により使用するために、前記データセグメントからの制御情報を分離する働きをする、各受信ポートに関連する受信ポートロジックを備える請求項１記載の共有メモリ。
【請求項２１】
更に、前記関連送信ポートでの送信のために、前記制御情報を前記データセグメントに再結合する働きをする、各送信ポートに関連する送信ポートロジックを備える請求項２０記載の共有メモリ。
【請求項２２】
前記制御情報は、前記データセグメントに関連する全ての制御情報を含み、前記データセグメントに関連するペイロードデータのみが前記メモリアレイに格納される請求項２０記載の共有メモリ。
【請求項２３】
前記制御情報の少なくとも一部は、前記データセグメントに関連するペイロードデータと共に前記メモリアレイに格納される請求項２０記載の共有メモリ。
【請求項２４】
前記制御情報は、前記関連データセグメントの長さをエンコードし、エンドオブフレームビットと、誤りビットとを含む請求項２３記載の共有メモリ。
【請求項２５】
更に、前記フレームのそれぞれにフレームレベル処理を提供する働きをするフレーム制御回路を備え、前記受信及び送信クロスバー回路と、前記メモリアレイと、前記バッファリングの少なくとも一部と、前記スケジューリング回路と、前記受信及び送信ポートのそれぞれの第１の部分と、前記フレーム制御回路の第１の部分とは、非同期領域で動作する非同期回路を備え、前記受信及び送信ポートのそれぞれの残りの部分と、前記フレーム制御回路の残りの部分とは、同期領域で動作する同期回路を備える請求項１記載の共有メモリ。
【請求項２６】
前記共有メモリの前記同期回路により、前記共有メモリは、同期システムにおいて同期ブロックとして動作可能になる請求項２５記載の共有メモリ。
【請求項２７】
各データセグメントは、複数のサブセグメントを備え、前記スケジューリング回路は、データセグメント毎に前記メモリアレイ内のスペースを一度のみ割り当てると同時に、前記共有メモリを介した各個別サブセグメントの移動を容易にする働きをする請求項１記載の共有メモリ。
【請求項２８】
各データセグメントは、２５６バイトを備え、各サブセグメントは、６４バイトを備える請求項２７記載の共有メモリ。
【請求項２９】
前記スケジューリング回路は、様々な長さのフレームの処理を容易にする働きをする請求項１記載の共有メモリ。
【請求項３０】
前記スケジューリング回路は、格納及び転送モードと、カットスルーモードとのそれぞれにおいて、前記共有メモリの動作を容易にする働きをする請求項２９記載の共有メモリ。
【請求項３１】
前記スケジューリング回路は、前記メモリアレイに対する第１のデータセグメントの格納と、前記メモリアレイからの第２のデータセグメントの検索とを、前記第１及び第２のデータセグメントが無関係である状態において、実質的に同時に容易にする働きをする請求項１記載の共有メモリ。
【請求項３２】
前記スケジューリング回路は、前記受信及び送信クロスバー回路に対する独立制御ストリームを生成する働きをする請求項３１記載の共有メモリ。
【請求項３３】
前記受信及び送信クロスバー回路のそれぞれは、前記独立制御ストリームの一方がそれぞれに関連する二つの独立クロスバーを備える請求項３２記載の共有メモリ。
【請求項３４】
前記受信クロスバー回路は、複数の入力チャネルと、複数の出力チャネルとを備え、前記送信クロスバー回路は、複数の入力チャネルと、複数の出力チャネルとを備え、前記スケジューリング回路は、前記受信クロスバー回路の前記入力チャネルと、前記送信クロスバー回路の前記出力チャネルとに対する制御データを直列化し、前記受信クロスバー回路の前記出力チャネルと、前記送信クロスバー回路の前記入力チャネルとに対する制御データを並列化する働きをする請求項１記載の共有メモリ。
【請求項３５】
前記バッファリングは、前記送信ポートのそれぞれに関連する出口バッファを含み、各送信ポートは、前記フレームの第１の数の前記データセグメントが前記出口バッファに格納されるまで、前記関連出口バッファからフレームのセグメントを受信するのを待つ働きをする請求項１記載の共有メモリ。
【請求項３６】
前記第１の数は、前記第１のデータレートを参照して決定される請求項３５記載の共有メモリ。
【請求項３７】
各送信ポートは、前記関連出口バッファに格納された前記データセグメントの一つが前記フレームの終わりを示す時、前記フレームの前記データセグメントの受信を開始する働きをする請求項３５記載の共有メモリ。
【請求項３８】
請求項１記載の共有メモリを備え、該共有メモリに関連するスイッチングプロトコルを有するスイッチ。
【請求項３９】
前記スイッチングプロトコルは、イーサネット（登録商標）を含む請求項３８記載のスイッチ。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、米国特許法第１１９（ｅ）条に基づき、出典を明記することでその開示内容全体を実質上本願明細書の一部とすべく、２００５年１月１２日提出の米国仮出願第６０／６４３，７９４号（ＦＵＬＣＰ０１１Ｐ）に基づく優先権を主張する。
【０００２】
本発明は、スイッチ基礎システム構成（ファブリックアーキテクチャ）に関する。更に具体的には、本発明は、高速スループットを維持する任意のポート間で、任意の長さのフレーム又はパケットを切り替えるために採用し得る共有メモリスイッチアーキテクチャを提供する。
【背景技術】
【０００３】
共有メモリアーキテクチャは、メモリの使用を更に効率化するためべく、多くのポートを備える高速スイッチにとって有利となる。即ち、メモリがポート自体に常駐する場合、アイドルポートのメモリは、未使用のままとなる一方で、アクティブポートのメモリは、特に送信プロトコルが非常に大きなパケットを許容する場合、過度に使用される。加えて、スイッチの設計対象である送信プロトコルがマルチキャスト要件（例えば、イーサネット）を有する場合、共有メモリでは、マルチキャストパケットを一度メモリに書き込むことのみが必要となる。マルチキャストパケットの対象となる多数のポートは、その後、同じメモリ位置を読むことになり、この動作に要するオーバヘッドは、ポートが異なるメモリ位置を読む場合のもの以下となる。この適合性のため、共有メモリアーキテクチャは、特にイーサネットスイッチを実現する際に人気が高い。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
こうしたアーキテクチャを設計する従来のアプローチでは、特にポート数と各ポートで必要な速度との両方が増加を続けるに従って大きな障害に直面することになる、同期回路及び設計フローを採用している。そのため、こうしたアプローチに対して、性能への要求の増加に対応可能な代替方法を提供することが望ましい。
【課題を解決するための手段】
【０００５】
本発明によれば、適度な最大メモリ速度でありながら、高ポート数を可能にする、共有メモリアーキテクチャが提供される。特定の実施形態によれば、第１のデータレートにより特徴付けられる複数の受信ポート及び複数の送信ポートを有する共有メモリが提供される。メモリは、行及び列で編成された複数のメモリバンクを含む。メモリアレイの動作は、第２のデータレートにより特徴付けられる。ノンブロッキング受信クロスバー回路は、任意の受信ポートを任意のメモリバンクに接続する働きをする。ノンブロッキング送信クロスバー回路は、任意のメモリバンクを任意の送信ポートに接続する働きをする。バッファリングは、第１のデータレートでの受信及び送信ポートの動作を、第２のデータレートでのメモリアレイの動作から切り離す働きをする。スケジューリング回路は、ポートと、クロスバー回路と、メモリアレイとの相互作用を制御し、共有メモリ内のデータセグメントの格納及び検索を達成する働きをする。スケジューリング回路は、更に、行の一つのメモリバンク全体における、フレームの各データセグメントのストライピングを容易にし、アレイの連続行全体における、フレームの連続データセグメントのストライピングを容易にする働きをする。
【０００６】
本発明の性質及び利点の更なる理解は、明細書の残りの部分と図面とを参照することで達成し得よう。
【発明を実施するための最良の形態】
【０００７】
次に、本発明を実施する最良の形態と本発明者が考えるものを含む、本発明の特定の実施形態を詳細に参照する。こうした特定の実施形態の例は、添付図面に例示する。本発明について、こうした特定の実施形態に関連して説明するが、説明した実施形態に本発明を限定するものではないことは理解されよう。反対に、添付特許請求の範囲により定義される本発明の趣旨及び範囲に含まれ得る代替物、変形例、及び等価物が網羅される。以下の説明において、本発明の完全な理解を提供するため、具体的な詳細について述べる。本発明は、こうした具体的な詳細の一部又は全部が無くとも実現し得る。加えて、周知の特徴については、本発明を不必要に曖昧にしないため、詳細に説明していない場合がある。
【０００８】
アーキテクチャの一部が非同期、非遅延敏感、又は疑似非遅延敏感の設計フローに従って実現された、様々な実施形態について説明する。非同期ＶＬＳＩは、デジタル回路設計における活発な研究開発分野である。これは、グローバルクロック同期信号が存在しない、あらゆる形態のデジタル回路を意味する。非遅延敏感非同期設計は、その本質からして、従来の設計パラダイムの進歩にとって唯一最大の障害となってきた信号伝搬遅延に対して敏感ではない。即ち、非遅延敏感回路設計は、デジタル回路内の何らかの遷移が際限のない遅延を有する場合でも、回路が依然として正しい挙動を示す特性を維持する。回路は、順序づけを強制するが、絶対的なタイミングを強制しない。この設計様式は、タイミングの想定、グリッチ、又は競合状態により生じる設計及び検証の問題を回避する。
【０００９】
非遅延敏感非同期デジタル設計の背景情報については、出典を明記することでその開示内容全体を実質上本願明細書の一部とする以下の文書を参照されたい：A. J. Martin, "Compiling Communicating Processes into Delay-Insensitive Circuits", Distributed Computing, Vol. 1, No. 4, pp. 226-234, 1986、U. V. Cummings, A. M. Lines, A. J. Martin, "An Asynchronous Pipelined Lattice Structure Filter", Advanced Research in Asynchronous Circuits and Systems, IEEE Computer Society Press, 1994、A. J. Martin, A. M. Lines, et al., "The Design of an Asynchronous MIPS R 3000 Microprocessor", Proceedings of the 17th Conference on Advanced Research in VLSI, IEEE Computer Society Press, 1997、及びA. M. Lines, "Pipelined Asynchronous Circuits", Caltech Computer Science Technical Report CS-TR-95-21, Caltech, 1995。
【００１０】
出典を明記することでその開示内容全体を実質上本願明細書の一部とすべく、１９９８年５月１２日発行の米国特許第５，７５２，０７０号「非同期プロセッサ」及び２０００年３月１４日発行の第６，０３８，６５６号「パイプライン型の非同期通信の完成」も参照されたい。
【００１１】
最初に、本願で説明する手法及び回路の多くは、非遅延敏感非同期ＶＬＳＩとして説明及び実現されることに留意されたい。しかしながら、本発明の原理及び手法の多くは、例えば、非遅延敏感ではない非同期ＶＬＳＩ及び同期ＶＬＳＩといった別の状況においても使用し得る。
【００１２】
本発明の様々な実施形態は、本発明の範囲から逸脱することなく、広範な方法で実施し得ることも理解されたい。即ち、本明細書で説明する非同期プロセス及び回路は、ソフトウェア（オブジェクトコード及び機械コード）において、コンパイルの様々な段階において、一つ以上のネットリストとして、シミュレーション言語において、ハードウェア記述言語において、一組の半導体処理マスクにより、部分的又は完全に実現された半導体デバイスとして、（制限無く）表現し得る。例えば、本明細書で説明するプロセス及び回路を設計及び製造するのに適した、様々な種類のコンピュータ読み取り可能な媒体、ソフトウェア言語（例えば、Ｖｅｒｉｌｏｇ、ＶＨＤＬ）、シミュレート可能な表現（例えば、ＳＰＩＣＥネットリスト）、半導体プロセス（例えば、ＣＭＯＳ、ＧａＡｓ、ＳｉＧｅ等）、及びデバイスタイプ（例えば、ＦＰＧＡ）は、本発明の範囲に含まれる。
【００１３】
加えて、こうした実施形態の特定のものについては、１０ギガビットイーサネットデータのスイッチングを参照して説明する。しかしながら、本発明の基本原理は様々な状況において適用し得るものであり、したがって、こうした実施形態の参照により本発明が限定されないことに最初に留意されたい。
【００１４】
次に図１のブロック図を参照すると、マルチポートスイッチの一部が図示されている。受信（Ｒｘ）クロスバー１０２は、複数のＲｘポート１０４の何れかから、メモリアレイ１０６内のメモリの複数のバンクの何れかへの着信データを切り替える。メモリアレイ１０６内のデータは、複数の送信（Ｔｘ）ポート１０８の何れかへ、Ｔｘクロスバー１１０を介して切り替えられる。特定の実施形態によれば、各Ｒｘポート１０４と、対応する一個のＴｘポート１０８とは、イーサネットポートに対応する。簡略化のため、単一のＲｘ及びＴｘポートのみを図示していることは理解されよう。加えて、以下では、本発明の実施形態について、２０個、２４個、３２個等、特定のポート数を参照して説明している。しかしながら、こうした数字は単なる例であり、本発明の範囲を限定するのに使用するべきではないことは理解されよう。
【００１５】
Ｒｘポート１０４がデータを受信する時、データの一部、例えば、フレーム又はパケットヘッダは、コピーされ、フレーム制御ブロック１１２へ送信され、全てのデータ、即ち、コピー部分とペイロードとを含むデータは、メモリアレイ１０６へ送信され、格納される。フレーム制御１１２は、フレーム制御情報をスケジューラ１１４へ提供し、メモリ内でのペイロードの格納を容易にするパイプライン型ユニットである。フレーム制御１１２は、例えば、フレームを修正するか、或いは廃棄するかについて、フレーム毎に判断をする。フレーム制御１１２は、その後、データを移動させ格納する制御の発生を担う制御スケジューラ１１４へ、判断を送信する。
【００１６】
特定の実施形態によれば、クロスバー１０２及び１１０と、メモリアレイ１０６と、スケジューラ１１４と、ポート１０４及び１０８のそれぞれの一部と、フレーム制御１１２の一部と（全て破線に囲まれる）は、上記の非同期設計様式により実現される。ポート及びフレーム制御の残りの部分は、従来の様々な同期設計手法の何れかを使用して実現される。イーサネットの実施例によれば、ポートの同期部分は、スイッチが接続されるシステム（群）により予想される、予想外部インタフェースを提供する。フレーム制御の同期部分は、複雑だが、こうした設計様式が最適となる比較的直接的なロジックを備えるため、少なくとも部分的には、同期設計様式、例えばＶｅｒｉｌｏｇにより実現される。このアプローチの詳細及び利点は、以下の説明を参照することで更に明白となる。
【００１７】
特定の実施例によれば、アーキテクチャの同期及び非同期部分間のインタフェースは、出典を明記することでその開示内容全体を実質上本願明細書の一部とする、２００３年８月２１日公開の「同期及び非同期領域間の変換を容易にする手法」に関する米国特許公報第２００３０１５９０７８号（代理人整理番号ＦＵＬＣＰ００２）において説明される手法により実現し得る。
【００１８】
上記のように、本発明のスイッチアーキテクチャは、任意の長さのフレーム又はパケットをポート間で切り替える働きをする。以下説明するように、アレイ内のメモリは、本明細書で「セグメント」と呼ばれる固定サイズのブロックに割り当てられる。しかしながら、特定の実施形態によれば、データは、本明細書において「サブセグメント」と呼ばれる更に小さな固定サイズのブロックにおいて、スイッチファブリックを介して移動させる。スイッチアーキテクチャがイーサネットスイッチとして実施されることを想定した、いくつかの数字の例は、教示的なものである。以下の説明にかかわらず、セグメント及びサブセグメントという用語が同じサイズのデータ単位を示す実施例が考えられる。
【００１９】
例えば、最小長６４バイトから最大長約１０キロバイトまでの広範な長さを有するフレームに対応することは、設計上の大きな課題である。当業者が理解するように、こうした極端に長いフレームを認めることは、カットスルー及びマルチキャスト用途において問題となる。本発明の特定の実施形態によれば、メモリは、２５６バイトのセグメントに割り当てられる。この長さにより、セグメント処理のオーバヘッドは管理可能な状態に保たれ、例えば、メモリポインタの数は、理にかなった範囲に維持される。しかしながら、データは、待ち時間を低減するために、６４バイトのサブセグメントを使用するスイッチファブリックを介して移動される。「フレーム」及び「パケット」という用語は、相互交換可能に使用し得るものであり、本発明の様々な実施形態が実現されるシステムに関連するプロトコルにおいて、様々な長さのネイティブデータ単位を示すことを理解されたい。
【００２０】
次に、本発明の様々な実施形態を実現するのに適したデータパスの構成の一例について、図２を参照して説明する。Ｒｘクロスバー２０２は、Ｎチャネル×６４チャネルのクロスバーとして図示されており、Ｔｘクロスバー２０４は、６４×Ｎクロスバーとして図示されている。様々な実施形態によれば、Ｎは、広範な値の何れかをとり得る。以下に説明する実施形態において、説明される特定のアーキテクチャは、３２ポートまでを扱うように物理的に構成される。しかしながら、性能の説明の大部分では、３２ポートより少ない数、例えば、２０又は２４ポートに対してアーキテクチャが提供されることを想定している。Ｎは、３２より大きな値にしてもよく、但し最終的に、Ｎは、設計が万全なものとなるメモリの速度により限定及び増減されることを理解されたい。更に、各チャネルがマルチビットデータパス、例えば、３２ビットデータパスを有することは理解されよう。
【００２１】
メモリアレイ２０６は、それぞれ２５６バイトである４，０９６セグメントのアレイであり、各セグメントはそれぞれ６４バイトである四つのサブセグメントに対応すると考えられる。アレイは、ＳＲＡＭの６４個の１６ｋＢバンク２０８に分割され、６４本のＲｘ及びＴｘクロスバーチャネルのそれぞれに対して一個のバンクとなり、即ち、各バンクのライトチャネルは、Ｒｘクロスバー出力チャネルの一本に接続され、リードチャネルは、Ｔｘクロスバー入力チャネルの一本に接続される。図２のアレイの例は１６列４行を有しているが、列及び行の数は、本発明が適切な無数の用途において大きく変化し得ることは理解されよう。
【００２２】
フレームの６４バイトサブセグメントがメモリに着信すると、サブセグメントの各４バイトワードは、増分するＳＲＡＭ位置に配置され、フレームに対応するセグメントのリンク済みリストにおいて、６４ＳＲＡＭバンクによる「ストライピング」が行われる。特定の実施形態によれば、各サブセグメントは、特定の行のバンクによりストライピングされ、セグメント内の連続するサブセグメントは、連続する行においてストライピングされる。
【００２３】
一部の実施形態によれば、一定のバンクで開始される連続フレームは、同じサブセグメントにおいて書き込みが開始される。しかしながら、これにより、メモリバンクの「下方」部分は非常に酷使されるが、「上方」部分は頻繁にアイドルとなる。そのため、一部の実施形態によれば、特定のバンクで開始される連続フレームに対して、バンク内で異なるサブセグメント開始点が選択される。この選択は、疑似乱数的又は決定論的に実行し得る。一実施形態によれば、新しいフレームの開始点の選択は、多数のポートがメモリの特定のバンクに同時にアクセスを試みる状態の検出に応答する。こうしたアプローチは、一定の数のポートにおいて、ＳＲＡＭアレイが最大のパケットレートより遅い速度で動作する実施形態に対して、フレームが抜け落ちる可能性を低減するために使用される。また、こうしたアプローチは、付加的なマージンを提供するために使用し得る。
【００２４】
上記のようにサブセグメント内でバンクを循環させることに加え、セグメント内のサブセグメントを循環させる本発明の実施形態が考えられる。選択は、ここでも疑似乱数的又は決定論的に実行し得る。決定論的選択では、例えば、線形順序を採用し得る。また、割り当て頻度の最も低いものに関するアプローチに基づいて選択される「スコアボーディング」のアプローチを採用し得る。
【００２５】
本発明のスイッチアーキテクチャのデータパス要素は非同期で実現されるため、ポートのデータレートに遅れないためにＳＲＡＭメモリアレイがどのくらいの速さで動作する必要があるかについて、大きな利点が達成される。ポートがイーサネットポートに対応する場合、各ポートは、連続フレーム間に固定サイズの２０バイトのギャップを有して、毎秒１５００万フレーム（≧６４バイト）を処理できなくてはならない（即ち、１０ギガビットのデータレート）。２４個の１０Ｇｂ／ｓポートに対して、最悪のケースの万全なスイッチファブリックを提供するために、同期メモリは、リードとライトの両方において、４６９ＭＨｚ（即ち、最大データレート又はバースト速度）で動作する必要がある（２４０Ｇｂ／ｓ／５１２ｂストライプ＝４６９ＭＨｚ）。しかしながら、非同期ＳＲＡＭはフレーム間の２０バイトのギャップ中に失速する可能性があるため、クロスバーのみが、バースト速度についていくのに十分な速さで動作する必要があり、メモリは、持続速度、即ち、フレームレートをポート数倍したもの（デュアルポートＳＲＡＭにおいて３６０ＭＨｚ、或いはシングルポートＳＲＡＭにおいて７２０ＭＨｚにほぼ等しい）において、フレーム落ちなしで動作できる。
【００２６】
こうした実施例において、最大データレートは、データがＳＲＡＭによりストライピングされる形で処理される。即ち、２４個のポートを想定すると、単一のＳＲＡＭ行は、二つの事柄の一方が起こる前に、多くとも２４個の６４バイトサブセグメントを受信することになる。一定のポートで受信されるフレームが完了した場合、ＳＲＡＭバンクは、アイドル状態となる。一方、２４フレームの何れかが追加のサブセグメントを有する場合、データは、ＳＲＡＭバンクの次の行（アイドル状態にあり、稼働準備ができているもの）へ移行し、ＳＲＡＭによるストライピングを継続する。したがって、フレーム間ギャップのため、非同期ＳＲＡＭは、（最大データレートとは反対に）最大フレームレートより高速で動作しなくても万全なものとなる。
【００２７】
非同期データパスは、このシステム内の緩みを利用して、着信データのバースト性を平坦化し、２４ポートスイッチを効率化する。反対に、３６０ＭＨｚで動作する同程度のデュアルポート同期メモリは、１８ポートしかサポートできない。加えて、特定の実施形態によれば、本発明の実施形態は、出典を明記することでその開示内容全体を実質上本願明細書の一部とする、２００４年７月１３日提出の米国特許出願第１０／８９０，８１６号「非同期スタティックランダムアクセスメモリ」（代理人整理番号ＦＵＬＣＰ００８）において説明される（交互に読み書きを行う）シングルポート非同期ＳＲＡＭアーキテクチャを使用して実現し得る。即ち、こうしたメモリは、２４ポートが必要とする同等の７２０ＭＨｚの速度で動作可能であるが、相対的に小さなシングルポートアーキテクチャの設置面積を有する。２４ポートスイッチ用のシングルポート設計は９３８ＭＨｚで動作する必要があり、０．１３μｍテクノロジにおける標準的な同期メモリの実施例にとって高すぎると考えられるため、同程度の同期システムでは、（遥かに多くの領域を消費する）デュアルポートアーキテクチャを使用するしかない。
【００２８】
次に、様々な速度の動作を説明するために図３を参照すると、バーストＦＩＦＯ３０２及び３０４が、各メモリバンク３０６と対応するＲｘクロスバー出力チャネル及びＴｘクロスバー入力チャネルとの間に設けられる。ＦＩＦＯ３０２及び３０４は、クロスバーチャネルからの最悪のケースのバーストを処理するのに十分な大きさである。即ち、Ｒｘ及びＴｘクロスバーは、多数のポート（例えば、２０以上）との間でデータを送受信するように準備される。これにより、クロスバーにはＳＲＡＭバンク３０６について実現が難しい動作速度要件が強制される。ＦＩＦＯ３０２及び３０４により、ＳＲＡＭバンク３０６は、更に穏やかな動作速度を有することが可能となり、また、Ｒｘ及びＴｘクロスバーは、それぞれの最大動作速度でバーストのデータを送受信できる。
【００２９】
図１に示したように、Ｒｘ及びＴｘクロスバーは、それぞれ単一の３２×６４又は６４×３２クロスバーとして実現し得る。しかしながら、こうした大きなクロスバーの実現は、電気的に効率が悪い。そのため、図４に例示した本発明の特定の実施形態によれば、３２ポートは、個々のメモリバンク４１４への進入及び退出のために１６個の２×４クロスバー４１０及び１６個の４×２クロスバー４１２と組み合わせて、ポートの受信及び送信側の両方で二つの１６×１６クロスバー（４０２乃至４０６）を使用して、６４個のメモリバンクに接続される。即ち、例えば、クロスバー４０２の各３２ビット出力チャネルは、クロスバー４１０の一つにおいて、二本の入力チャネルの一方に結合される。各クロスバー４１０の四本の出力チャネルのそれぞれは、関連する四個のメモリバンク４１４の一つのライトチャネルに結合される。それぞれのメモリバンク４１４のリードチャネルは、関連するクロスバー４１２の一つにおいて、四本の入力チャネルの一つに結合される。各クロスバー４１２の出力チャネルのそれぞれは、その後、クロスバー４０６又は４０８の一方において、入力チャネルの一つに結合される。この分散ノンブロッキングクロスバーシステムは、ポート（３２個まで）のそれぞれを、ＳＲＡＭの６４バンクのそれぞれのリード及びライトチャネルに接続する。
【００３０】
特定の実施形態によれば、周知のＣＬＯＳアーキテクチャに由来する手法を、ポートのスケーラビリティの問題に応用する。ＣＬＯＳアーキテクチャには、二つの要件があり、即ち、１）ＣＣＢ（定クロスセクション帯域幅）（スイッチの中間層による２Ｎ−１リンク）と、２）利用可能なリンクへのスケジューリングを行う何らかの機構とを有する。本明細書で説明する実施形態によれば、多数の非同期クロスバーを使用して、ＣＣＢ多段スイッチを形成する。加えて、ストライピング手法（下記）により、メモリ要素へのセグメントのスケジューリングを行うノンブロッキング手段を形成する。これにより、何らかのブロッキングを持ち込むことなく、メモリ速度の基本的な限界まで、ポート数の拡大が可能となる。一部の実施形態によれば、ランダムなストライピングによりメモリの最悪のケースのイベントレートに対処する時に、より高い統計的性能が可能になる場合、更なる拡大が可能となる。非ブロッキングアーキテクチャに関連する追加情報については、出典を明記することでその開示内容全体を実質上本願明細書の一部とする、Charles ClosによるA study of non-blocking switching networks, The Bell System Technical Journal, 1953, vol. 32, no. 2, pages 406-424を参照されたい。
【００３１】
サイズ及び／又はクロスバーの組み合わせに関係なく、各クロスバーは、様々な形で実現し得る。一組の実施形態によれば、クロスバーは、出典を明記することでその開示内容全体を実質上本願明細書の一部とする、２００３年８月７日公開の「決定論的又は仲裁制御による非同期クロスバー」に関する米国特許公報第２００３０１４６０７３Ａ１号（代理人整理番号ＦＵＬＣＰ００１）において説明されるように実現し得る。
【００３２】
次に、上記のデータパスに対する制御信号の分散について、図５Ａ、５Ｂ、及び図６を参照して説明する。図５Ａにおいて、Ｒｘ及びＴｘクロスバーは、ここでも簡略化のため、単一の３２×６４及び６４×３２クロスバーとして表現される。更に、図５Ａ及び５Ｂでは、両方とも簡略化のため、単一ブロックとしての制御を図示している。制御信号がどのように生成されるかに関する更なる詳細は、後続の図を参照して以下に説明する。
【００３３】
特定の実施例によれば、制御５０２は、スケジューラ（表示無し）から単一の制御ストリーム（制御５０２に入力される「アレイ制御チャネル」として表現される）を受信し、Ｒｘクロスバー５０４と、ＳＲＡＭバンク５０６と、Ｔｘクロスバー５０８とに対して制御チャネルを生成する。ＳＲＡＭ制御情報は、アドレスとリード／ライトビットとを含む。各クロスバーのクロスバー制御情報は、クロスバーの入力及び出力チャネル（即ち、送信及び受信クロスバーポートの組み合わせ）と、フレーム又はパケットの長さとを特定する。アレイ制御チャネルは、リードビットと、リードアドレスと、リードポートと、リード長と、ライトビットと、ライトアドレスと、ライトポートと、ライト長とを含む。特定の実施形態によれば、リード及びライト長は、フレームの最終の６４バイトサブセグメントに何個の未使用ワードがあるかを表す。これにより、ダミー情報でメモリ位置を占有するのではなく、フレームが終了した時に、読み出し及び書き込みを停止できる。
【００３４】
したがって、アレイ制御チャネルは、メモリに６４バイトサブセグメントを書き込み、メモリから６４バイトセグメントを読み出すために情報を同時に提供し、二つのセグメントは、関連していても関連していなくてもよい。最大パケットレート３００ＭＨｚ（２０ポートを想定）及び６４バイトのサブセグメントサイズでは、リード及びライトチャネルには、それぞれが約６００ＭＨｚで動作する場合に、万全なものとなり得る。例えば、万全に準備された２０ポートスイッチについて、これは、制御５０２の動作において、１．２ＧＨｚのデータレートと同等のものとなる。しかしながら、Ｒｘ及びＴｘに対して二つの独立した制御ストリームを使用することで、実際のデータレートは、丁度６００ＭＨｚとなる。低い最大パイプライン速度又は高いポート数は、制御ストリームを四個のクロスバーのそれぞれに従う四本の独立したストリームに分割することで達成できる（注：これは四個のクロスバーの例を想定している）。
【００３５】
制御５０２は、アレイ制御チャネル上の一つのコマンドを、一つの６４バイトサブセグメントをＳＲＡＭアレイに書き込み、一つの６４バイトサブセグメントをアレイから読み出すのに必要な全てのものに変換する。特定の実施形態によれば、制御情報をクロスバー及びＳＲＡＭへ送信する方法では、以前のコマンドの第１のワード（群）のみの書き込み／読み出し後、次のコマンドの実行を開始できる。例えば、受信側では、あるコマンドに関連するワード０は、以前のコマンドのワード０に続くサイクルにおいて（或いは、以前のコマンドのワード１と同時に）メモリに送信される。即ち、一サイクルだけ同期を外して、連続コマンドが実行される。
【００３６】
このコマンドの「重複」実施は、制御情報がＳＲＡＭアレイに導入される方法により促進される。即ち、制御情報は、ＳＲＡＭバンク５０６の第１の「列」に提供され、その後、アレイ全体で、矢印５１０で示す他の列内の対応するバンクへ「波及」する。フレームがＳＲＡＭバンク全体で「ストライピング」される方法のため、各連続バンクにおいて、同じ開始アドレスが使用して、特定のフレームのサブセグメントを格納する。したがって、アドレス情報は、制御５０２から一度だけ送信すればよく、その後、列の間で共有される。情報がアレイ全体に波及する際には、格納又は読み出し対象のデータが存在しなくなった時に、書き込み又は読み出しが停止するように長さが低減され、即ち、アドレス情報は、サブセグメントの長さ（１６ワード以下）に達して「消滅」するまで波及する。これにより、データパスにおいてテールビットを使用することなく、効率的な可変長伝送が可能となる。
【００３７】
Ｒｘ及びＴｘクロスバーは、サイクル毎にサブセグメントの送信（１６サイクルを要する可能性がある）を開始できるように、パイプライン化され、完全に並列となる。
【００３８】
次に、図４を参照して説明した分散クロスバーアーキテクチャに対するデータパスへの制御情報の送信について、図５Ｂを参照して説明する。二つの１６×１６Ｒｘクロスバー５５２及び５５４の出力チャネルのそれぞれは、ＳＲＡＭバンク５５８の１６列のそれぞれにおいて、２×４クロスバー５５６の入力チャネルに接続される。各クロスバー５５６の四本の出力チャネルのそれぞれは、四個のＳＲＡＭバンク５５８の一つに結合される。このようにして、３２本までのＲｘ入力チャネルは、ＳＲＡＭの６４バンクのそれぞれに接続し得る。同様に、列内のＳＲＡＭバンクのそれぞれは、その列の４×２クロスバー５６０の入力チャネルに接続される。各クロスバー５６０の二本の出力チャネルは、それぞれ、Ｔｘクロスバー５６２及び５６４の入力チャネルの一つに接続される。このようにして、６４ＳＲＡＭバンクのそれぞれは、３２本までのＴｘ出力チャネルに接続し得る。
【００３９】
制御チャネルは、制御５０２により、データパス内のクロスバーへ送られる。一本の制御チャネルが、クロスバー５５２、５５４、５６２、及び５６４のそれぞれに対して送られる。一本の制御チャネルは、ＳＲＡＭバンクの第１の「列」内のクロスバー５５６及び５６０にも送られる。この制御情報は、その後、（矢印５６６で示すように）他の１６の「列」全体に波及し、ＳＲＡＭ制御情報について説明したように、連続するＳＲＡＭバンクにフレームの連続ワードが格納され、即ち、ストライピングされるようになる。
【００４０】
各１６×１６クロスバーに対する制御情報は、８ビットを含み、４ビットは入力又は出力チャネルを特定し（ＲｘかＴｘかによる）、４ビットは「長さ」、即ち、サブセグメント内のワード数を示す。２×４及び４×２クロスバーに対する制御情報は、７ビットを含み、３ビットは、入力／出力チャネルの組み合わせをエンコードするためのものであり、４ビットはサブセグメント長を表す。ＳＲＡＭアレイの第１の「列」における四個のＳＲＡＭバンク５５８のそれぞれの制御情報は、１７ビットを含み、１２ビットのアドレス（即ち、各バンク内の４０９６種類の可能な２５６バイトセグメントの一つ）、１リード／ライトビット、及びサブセグメント長を表す４ビットとなる。上記のように、この情報は、アレイ全体において、各連続列内の対応するバンクへ（即ち、情報が「消滅」するまで）波及する。
【００４１】
図６は、４ビットの入力チャネル情報の単一ストリームと４ビットの長さの情報とを、１６×１６Ｒｘクロスバーの一つにおいて、必要なデータレートに対応する十分な素早さで、どのように分散し得るかを例示している。１６×１６Ｔｘクロスバーに対して、同様だが「鏡像」となる制御パスを実現することに留意されたい。最初に、８ビットの情報が、直列である「外側」制御情報に使用される一方のストリームと、並列である「内側」制御情報に使用される他方とにより、コピーされる（６０２）。即ち、以下説明するように、外側クロスバーチャネル（即ち、Ｒｘの入力側及びＴｘの出力側）の制御は直列化され、一方、内側クロスバーチャネル（即ち、Ｔｘの入力側及びＲｘの出力側）の制御は並列化される。
【００４２】
外側制御情報は、４ビットの入力チャネル情報に従って、１６方向、即ち、各入力ポートに対して分割される（６０４）。これにより、Ｒｘクロスバーの入力チャネルに対する制御が直列化される一方で、サブセグメントの送信に１６サイクルを要するとしても、連続サブセグメントに対する制御情報は、連続するサイクルで分散可能となる。制御は、セグメントの長さに達するまで、クロスバーの対応する入力チャネルに対して反復される（長さのカウントを減分することで決定される）（６０６）。
【００４３】
内側制御情報は、Ｒｘクロスバー（６０８−０乃至６０８−１５）の出力チャネル制御を介して波及し、Ｒｘクロスバーの指定入力チャネルを、（４ビット長で示す）ＳＲＡＭアレイの連続バンクへサブセグメントを送信するのに必要となる１６本の出力チャネルへ連続的に接続する。したがって、Ｒｘクロスバー出力チャネルの制御は、並列化される。上記のように、１６×１６Ｔｘクロスバーに対する制御は、並列化されたＴｘクロスバーの入力チャネルに対する制御と、直列化された出力チャネルに対する制御である点を除き、同一に近い。
【００４４】
次に、図７及び８を参照して、本発明で使用するＲｘ及びＴｘポートの一部の例の性質に関する更に詳細な説明（例えば、図１のポート１０４及び１０８）を行う。説明の他の部分と同様に、イーサネットによる実施例が、例示の目的で想定されるが、本発明の範囲を限定するために用いるべきではない。
【００４５】
図７は、予想インタフェース特性（イーサネットの仕様により定義される）をスイッチの外部へ提供する同期ブロックであるＲｘイーサネットポートロジック（ＥＰＬ）７０２を含む、ポートのＲｘ部分の簡略ブロック図を示す。Ｒｘ非同期ポートロジック（ＡＰＬ）７０４は、名前が示すように、Ｒｘ  ＥＰＬ７０２からの着信データの適切な部分をスケジューラ７０６（動作は以下説明）及びフレーム制御（図示なし）へ提供する非同期ブロックである。ＳＲＡＭアレイ７０８に格納されるべき全てのサブセグメントについて、Ｒｘ  ＡＰＬ７０４は、８ビットのサブセグメントデータ（ＲｘＳＳ）、即ち、サブセグメントの長さ（即ち、１乃至６４バイト）をエンコードする６ビットと、エンドオブフレーム（ＥＯＦ）ビットと、誤りビットとを、スケジューラ７０６へ提供する。サブセグメントデータは、ＦＩＦＯ７１０に配置され、その後、スケジューラ７０６からの制御情報に従って、アレイ７０８に格納される。Ｒｘ  ＡＰＬ７０４は、更に、全フレームの最初の１６バイトと、（フレームの終わりからの）長さ及び誤りフラグを、以下に説明する用途のためフレーム制御（表示なし）に提供する。
【００４６】
ＦＩＦＯ７１０は、二つの利点を有する「ジッタ」ＦＩＦＯである。本発明のクロスバー（群）はノンブロッキングであるため、データは、スイッチポートロジック（例えば、Ｒｘ  ＥＰＬ７０２）において停滞しない。しかしながら、仲裁の許可が受領されるまでに僅かな待ち時間が存在し得る。ＦＩＦＯ７１０は、この待ち時間を吸収するバッファリングを提供する。加えて、ＦＩＦＯ７１０により、データは、ポートロジックの速度ではなく、クロスバー（群）の速度で、共有メモリアレイへストリーミング可能となり、即ち、ポートロジックの動作速度は、クロスバーのものから分離される。特定の実施形態によれば、ＦＩＦＯ７１０（Ｒｘ  ＡＰＬ７０４と統合可能）は、セグメント全体を格納可能であり、これにより、共有メモリのカットスルー動作が可能になる。
【００４７】
ここでも、本発明の様々な具体的実施形態は、本明細書で説明した具体的な実施例の詳細に限らず一般化し得ることを理解されたい。例えば、図７を参照して説明した実施例において、Ｒｘ  ＡＰＬ７０４の非同期の性質は、特に重要ではないことを理解されたい。即ち、Ｒｘ  ＡＰＬ７０４は、この特定の実施形態では、たまたま非同期となっている。むしろ、可変パケット格納、カットスルー転送、万全に準備されたマルチキャスト、及び出口でのタグ付けといった特徴を含む、本発明により設計された一般的なスイッチ要素の境界として概念化されるべきである。対照的に、Ｒｘ  ＥＰＬ７０２は、こうしたスイッチを実現する際に従う、特定用途向けのコンテキスト（即ち、イーサネット）である「プロトコルパーソナリティ」を提供しているに過ぎない。他の相互接続技術、例えば、シリアルラピッドＩ／Ｏ、アドバンスドスイッチング、インフィニバンド等は、異なる境界要素特性を発生させる異なるコンテキストを提供する。特定の相互接続テクノロジの多数のパーソナリティ（例えば、多数のイーサネットパーソナリティ）と、より高レベルの処理（例えば、ＩＰ処理）とを更にサポートし得る。
【００４８】
図８は、ポートのＴｘ部分の簡略ブロック図を示す。Ｔｘ  ＡＰＬ８０２は、ＦＩＦＯ８０４の状態を追跡し、ＳＲＡＭアレイ８０８からの別のサブセグメントに対する余裕がＦＩＦＯ８０４に存在する時、「レディ」信号をスケジューラ８０６へ送る。スケジューラ８０６は、８ビットのサブセグメントデータ（ＴｘＳＳ）、即ち、パケットの長さを表す６ビットと、ＥＯＦビットと、誤りビットとを、カウンタ８１０へ提供する。Ｔｘ  ＡＰＬ８０２は、「枯渇」していない状態を確保するのに十分な現行フレーム用サブセグメントがＦＩＦＯに存在するようになるまで、ＦＩＦＯ８０４からのサブセグメントの排出を開始しない。これは、二つの条件の一方が満たされた後のみ、即ち、カウンタ８１０がカウントを完了した時、或いはフレームの終わりが検出された時、Ｔｘ  ＡＰＬ８０２に対して「許可」信号をアサートするカウンタ８１０を使用して確保される。
【００４９】
特定の実施形態によれば、カウンタ８１０は、スケジューラ８０６から受領したプログラム可能な値を使用して、フレーム毎にリセットされる。スケジューラ内のレジスタは、アーキテクチャの都合に合わせて選択したことに留意されたい。この値は、システム内のどこかにあるレジスタに格納し得ることは理解されよう。様々な具体的実施形態によれば、カウンタ値は、現行又は予想システム状態に応じて、複数の値の何れかになり得る。
【００５０】
特定の実施形態によれば、三種類の状態に対応する三種類のプログラム可能な値が使用される。第１に、フレームが６４バイトのみである場合、カウンタ値はゼロとなり、即ち、「許可」信号がアサートされ、Ｔｘ  ＡＰＬ８０２は、ＦＩＦＯ８０４の排出開始を即座に許可される（即ち、フレームは一セグメント以下であり、定義上、ジッタが存在しない）。第２に、システムが「格納及び転送」モードで動作している場合（即ち、フレームの送信がフレーム全体の受領後のみに開始される場合）、カウンタ値は、何らかの数（例えば、四個）のサブセグメントがＦＩＦＯ内にある場合、「許可」信号がアサートされるように設定される（例えば、フレームの書き込みが読み出しより一セグメント（２５６バイト）先行する）。最後に、システムが「カットスルー」モードで動作している場合（即ち、フレーム全体が受信される前に、フレームの送信が許可される場合）、カウンタ値は、格納及び転送の場合の値を二倍するように設定され、この場合、ジッタが最も多くなる。したがって、スケジューラは、スケジューリングを開始する時にセグメント全体が存在するかを判断する情報を有しているため、どのウォーターマークを使用するかを最適化できる。こうした値は、単なる例であり、任意の適切なカウンタ値をシステム動作の調整に採用してよいことは理解されよう。
【００５１】
カウンタ８１０は、更に、フレーム終了が検出された時にサブセグメントデータのコピーを受領して、カウンタ８１０に対してＥＯＦ信号をアサートするＥＯＦ検出器８１２から、フレーム終了の通知を受領する。ＥＯＦ信号に応答して、カウンタ８１０は、Ｔｘ  ＡＰＬ８０２に対して「許可」信号をアサートする（カウンタ値に基づいて既にアサートされていない場合）。
【００５２】
特定の実施例によれば、フレーム制御（図示なし）は、更に、スイッチから外部へ向かう途中のフレームを修正するために、Ｔｘ  ＡＰＬ８０２（又はＥＰＬ  ８１６）に対してフレームレベル情報を送信する（即ち、出口タグパケット処理）。このフレームレベル情報（スケジューラ８０６を通過し得る）は、フレームを送信するためのサイドバンド情報であり、通常、Ｔｘ  ＡＰＬ又はＥＰＬに対して、何らかの形でフレームヘッダを修正することを命令する。例えば、イーサネットの実施例において、このフレームレベル情報は、ＶＬＡＮタグ修正情報を含むことができる。
【００５３】
ＲｘＳＳ誤りビットが誤りを示す時、送信が開始される前に、その誤りがフレームに追いつくことが可能である場合、即ち、送信開始前に、スイッチが誤りを「知っている」場合、フレームはサイレントに廃棄される。これは、格納及び転送モードにおいて常に生じる。しかしながら、カットスルーモードにおいて、これは、一部の状況、例えば、スイッチの混雑状態又はショートフレームにおいてのみ発生する。ＴｘＳＳ誤りビットが誤りを示す場合には、破損ＣＲＣをフレーム（例えば、ＥＰＬ）に挿入する。
【００５４】
本明細書での使用において「ジッタ」は、本発明のスイッチ要素における仲裁、直列化、バンキングの何れかにより持ち込まれる、連続動作間の何らかの遅延を示す。「ジッタ」には、アーキテクチャの様々な特徴により平坦化される二つの主なソースが存在する。ジッタの第１のソースは、スケジューラが各ポートを順番にクエリするが、同じポートでの連続するクエリの間隔が大幅に、例えば０乃至３５ｎｓで、変化する可能性があるという事実による。ジッタの第２の更に大きなソースは、データパス性能の「バースト性」を平坦化するために、システム内に相当量の制御チャネルのバッファリングが存在するという事実による。即ち、このバッファリングは、こうしたバーストに対してシステム性能を平坦化する上でプラスの効果を有するが、この緩みは、十分である場合に、システムにジッタを持ち込む可能性がある。
【００５５】
この実施例では、ペイロードデータのみが共有メモリアレイに保持され、他の全ての制御情報（例えば、ヘッダ）は、制御パスの別個のアレイ（例えば、スケジューラ内）に保持される。このアプローチの利点の一つは、フレームが既にＣＲＣを含んでいるため、アレイ内のデータが追加のパリティビットを有する必要がないことである。加えて、制御情報は、通常、何らかの形で操作され、サイズが変化し得るため、この情報をデータパスから除外することで、規則的且つ効率的な形で、データをアレイ内に格納できる。更に、制御及びペイロードデータを共有メモリアレイにおいて混合する設計では、スイッチがデータをどのように処理するか決定可能となる前に、データの大きなバックログが高速で蓄積される可能性がある。本発明の設計の少なくとも一部では、データ及び制御パスが並行して維持され、即ち、ペイロードデータが制御情報の解析と並行してアレイ内に導入されるため、これは回避される。しかしながら、こうした利点にもかかわらず、少なくとも一部の制御情報がペイロードデータと共にアレイに格納される本発明の実施形態が考えられる。例えば、より低いフォールスルーの待ち時間を達成するために、データパスにおいて何らかのレベルのロックを実現できる。
【００５６】
上記のように、データパスに対する制御信号は、スケジューラにより、単一の制御ストリーム（本明細書でアレイ制御チャネルと呼ばれる）から生成される。スケジューラは、ポートをクエリし、スイッチを通過するトラフィックを追跡し、ＳＲＡＭアレイに対するアクセスが全てのアクティブなスイッチポートについて適正にインタリーブされるように、アレイ制御チャネルにコマンドを発行する。何れかのポートに与えられるアレイへのアクセスの順番が多すぎる場合、他のポートではトラフィックのボトルネックが発生する可能性がある。したがって、特定の実施形態によれば、スケジューラは、循環的順序でアレイへのアクセスをスケジュールするように試み、例えば、２４ポートのスイッチに対して、１乃至２４の順序を反復する。以下説明するように、特定のポートは、例えば、送信するのに十分なデータが集まっていない場合、順番をスキップしなくてはならない場合がある。
【００５７】
次に、本発明の実施形態で使用するスケジューラの特定の実施例について、図９を参照して説明する。スケジューラ９０２は、主に三つの機能を実行する。フレームスケジューラ９０４は、データパスを介して送信されるフレームのキューを維持し、順序付ける。一実施例によれば、１００個のキューが使用される（四つの優先順位に２５個ずつ）。しかしながら、この数は増減可能であり、実質的に同じアーキテクチャで大幅に大きくできる（例えば、２００個、４００個等）。
【００５８】
フレームスケジューラ９０４は、フレームのサイズに関係なく、フレーム単位で情報を追跡する。フレームスケジューラ９０４によりフレームがスケジュールされると、サブセグメントスケジューラ９０６は、各フレーム内で個々のサブセグメントをスケジュールする。メモリ割り当てブロック９０８は、メモリの割り当てを担当し、即ち、共有メモリアレイ９１０において各フレームの格納を開始する場所を決定する。
【００５９】
スケジューラ９０２は、転送チャネル上において、フレーム制御９１２から特定のフレームに関するフレーム制御情報を受領する。フレーム制御情報の一部は、ヘッドストレージ９１４に書き込まれ、残りは、ヘッドストレージ９１４の右に図示したパイプラインを進んでいく。ヘッドストレージ９１４は、全ての実施例で必要なわけではないが、この実施例では、フレームスケジューラ９０４のスケジューリング機能を達成するのに必要ではないフレーム制御情報の一部（例えば、ＶＬＡＮタグ付けデータ）を一時的に格納するために使用される。この一時的に格納された情報は、その後、情報が利用される機能に先立って「回収」される。これにより、フレームスケジューラパイプラインのブロックのそれぞれにおいて、ＳＲＡＭアレイのサイズが節約される。即ち、全てのデータがブロック９１６、９２２にコピーされる場合には、更に多くの合計格納量が必要となる。
【００６０】
メモリ割り当てブロック９０８は、現在使用されていない共有メモリアレイ９１０内の４０９６個の２５６バイトセグメントそれぞれの「フリー」リストを維持する。メモリ割り当てブロック９０８からの入力に応答して、ヘッドストレージ９１４は、フレーム制御情報の一部を、自分のＳＲＡＭアレイ（図示なし）の４０９６のスロットの一つに配置し、各スロットは、共有メモリアレイ９１０内の４０９６個のセグメントの一つに対応する。指定されたスロットは、フレームの第１のセグメントが格納されるべき共有メモリアレイの位置に対応する。フレームが一セグメントより長い場合、メモリ割り当て９０８は、必要な任意の追加セグメントのリンク済みリストをサブセグメントスケジューラ９０６へ直接提供する。
【００６１】
フレームの「ヘッド」セグメントのアドレスは、システム内の各フレームに対する一意の識別子となる。Ｒｘキュー９１６、エラーストレージ９１８、及びサブセグメントスケジューラ９０６のそれぞれにある個別のＳＲＡＭアレイ（図示なし）も、共有メモリアレイ９１０の４０９６個のセグメントとの同じ一対一の対応性を有する４０９６のスロットを有する。
【００６２】
ヘッドストレージ９１４がメモリ割り当てブロック９０８からアドレスを受領した後、ヘッドストレージアレイに格納されていないフレーム制御情報は、フレームスケジューラパイプラインに沿って、アドレス情報と共に伝搬する。フレームが格納及び転送モードで送信されている場合、フレーム制御情報は、フレーム全体がアレイ９１０に入ったという通知（例えば、サブセグメントスケジューラ９０６からエラーストレージ９１８を介して通信されるＥＯＦにより表される）を受領するまで、待機室９２０のスロットに置かれ、この通知の時点で、フレーム制御情報は、Ｒｘキュー９１６へ転送される。待機室は、こうしたスロットをＲｘポート毎に一つ有する。一方、フレームがカットスルーモードで送信されている場合、フレーム制御情報は、待機室９２０で格納されることなく、Ｒｘキュー９１６へ進む。
【００６３】
Ｒｘキュー９１６及びＴｘキュー９２２は、各フレーム（以降、単に「フレーム」）のフレーム制御情報が指定Ｔｘポート（群）への送信の順番待ちの行列を作るキューのセットを含む。Ｒｘキュー９１６内で行列を作るフレームは、そのフレームがどのポート（群）へ送信されるべきかを示す宛先マスクを含む。Ｒｘキュー９１６は、宛先マスク情報を含め、アレイ９１０内の４０９６個のセグメントのそれぞれに対するスロットを有する点において、万全に準備される。
【００６４】
Ｔｘキュー９２２は、フレームのマルチキャスト、即ち、一つのＲｘポートから多数のＴｘポートへのフレームの送信を容易にするために、Ｒｘキュー９１６から分離された状態を維持する。選択された複製をマルチキャストするアプローチに応じて、様々な問題が発生する。例えば、フレームがＲｘキュー９１６の先頭に達した後にのみ複製が発生する場合、設計されたＴｘポートの全てが利用可能であるという保証はない。一方、Ｒｘキュー内で複製が発生する場合、キューが万全な状態を確保するために、キューのアレイを望ましくないほど大きくする必要がある。したがって、本発明の特定の実施形態によれば、Ｔｘキュー９２２は、ユニキャストにおいてのみ万全となる。しかしながら、以下説明するように、これは妥当なマルチキャスト要件を処理可能とする上で十分すぎる。
【００６５】
本実施形態によれば、Ｒｘキュー９１６の各フレームは、Ｔｘキュー９２２のスロットにコピーされ、マルチキャストフレームは、送信されるべき全てのポートに対して複製される。Ｔｘキュー９２２の各エントリは、フレームが送信されるべき単一のＴｘポートを示す。ユニキャストでＴｘキュー９２２を万全にするために、任意の時点でアレイ９１０内に格納可能なフレームの最大数に対応して４０９６スロットが提供される。Ｒｘキュー９１６内のアレイとは異なり、これら４０９６のスロットには、アレイ９１０内のセグメントに対するインデックスが作成されない。その結果、Ｔｘキューは、スロットを着信フレームに割り当てるために、独自のフリーリストを利用する。このフリーリストをメモリ割り当てブロックのフリーリストから切り離して維持することで、マルチキャストのメモリの効率を高めることができる。即ち、アレイ９１０内の僅かなパーセンテージのフレームのみがマルチキャストされる可能性が高いため、第２のリストを作成することで、最悪のケースのマルチキャストではなく、実際のマルチキャスト程度のメモリストレージが可能となる。
【００６６】
Ｔｘキュー９２２内の４０９６のスロットは、ユニキャストに対してのみ万全となるが、アレイ９１０において平均フレームが２５６バイトセグメントサイズより大きいという事実のため、実際には、著しいマルチキャスト要件をサポートするのに十分なスペースを提供する。結果として、任意の時点において、アレイには、事実上、常に４０９６フレームより遥かに少ないフレームが格納される。これは、任意の時点において、Ｒｘキュー９１６の４０９６スロットの多数、即ち、Ｒｘキュー９１６内の著しい数のフレームをマルチキャスト用に複製する必要がある場合でも、Ｔｘキューの４０９６スロットが全てを保持するのに十分となるような、十分に多くの数が対応して未使用になることを意味する。
【００６７】
特定の実施例によれば、ＲｘキューとＴｘキューとの間に、四種類のファブリック優先順位による、信用に基づくフロー制御機構が存在する。これにより、Ｔｘキューは、優先順位の高いマルチキャストに対して（Ｔｘキューが万全に準備されていないためＴｘキューのスペースが無くなるコーナーケースにおいて）ある程度のスペースを確保できる。Ｔｘキューが完全に満たされている場合、パケットの抜け落ちは生じないが、ＴｘキューからＲｘキューへの転送は停滞し、マルチキャストにおけるわずかな量のＨＯＬブロッキングにつながる。この優先機構は、コーナーケースにおける高優先順位のＨＯＬブロッキングを防止する。
【００６８】
特定の２４ポートの実施例（ＣＰＵ用に追加の２５番目のポートを有する）によれば、フレームは、四種類の優先順位に従って送信され、Ｒｘキュー９１６は、Ｒｘポート及び優先順位により編成された１００個のキューを有し、即ち、一つの優先順位に対して、各Ｒｘポートに一個のキューを有する。Ｔｘキュー９２２も１００個のキューを有するが、Ｔｘポート及び優先順位により編成される。したがって、例えば、Ｔｘキュー９２２において、一定の優先順位に対するスペースが無くなった場合、異なる優先順位のマルチキャストフレームは、依然として転送可能となる。
【００６９】
Ｔｘキュー９２２のサイズは、様々な実施例において増減してもよいことに留意されたい。例えば、この実施例では、ユニキャストに対して万全となることから４０９６スロットアレイを選択した。また、Ｔｘキュー９２２のスロット数を増加させることで、統計的に可能性の低いイベントに対する付加的なマージンを提供してもよい。加えて、Ｒｘキュー９１６が完全に満たされる可能性が常に低いならば、Ｔｘキュー９２２がマルチキャストトラフィックのバーストにより満杯となっても、Ｒｘキュー９１６の未使用スロットは、依然として、システムが失速する可能性を低くする。
【００７０】
サブセグメントスケジューラ９０６は、特定のＴｘポートに対する新しいフレームを必要とする時、そのポート用にフレームを利用できるか、Ｑキャッシュ９２４をクエリする。Ｑキャッシュ９２４は、「イエス／ノー」の回答を返信する。回答が「イエス」である場合、Ｑキャッシュ９２４は、更に、サブセグメントスケジューラ９０６に対して、Ｔｘキュー９２２に格納されたフレーム制御情報を、フレームがフレームスケジューラ９０４に入った時にヘッドストレージ９１４に最初に残された追加情報と共に送信する。Ｑキャッシュ９２４は、Ｔｘキュー９２２が追いつけない可能性のある速度で着信し得るサブセグメントスケジューラ９０６からの要求に遅れないようにするため、Ｔｘキュー９２２から切り離して維持される。
【００７１】
一実施形態によれば、フレームの転送には、サブセグメントスケジューラ９０６からの要求と、Ｔｘキュー及びヘッドストレージ９１４に格納されたフレーム情報のその後の転送とが伴う。この相互作用は、万全に準備された２４ポートスイッチにおいて、３６０ＭＨｚのフレームレートで発生する必要がある。しかしながら、計算の複雑さと、９０６、９１４、及び９２２内の大きなメモリとの相互作用は、０．１３μｍのＣＭＯＳにおいて達成が難しい。そのため、Ｑキャッシュ９２４を導入して、この待ち時間ループを短縮する。Ｑキャッシュは、１００個のキューについて「キューの先頭」を格納し、これはポートに優先順位を掛けたものに等しい。サブセグメントスケジューラは、Ｑキャッシュをクエリする時、優先順位を選択し（出口スケジューリングアルゴリズムを参照）、キューの先頭の情報を９０６へ供給する。そうでない場合、そのキューでは適格なフレームに反応せず、９０６は次のポートへ移動し得る。この情報を送信した後、そのキューは空になる。この状態は、Ｔｘキュー９２２に報告され、Ｔｘキュー９２２は、ヘッドストレージ９１４及びエラーストレージ９１８からＱキャッシュへ送信されるべき、そのポート優先キュー内の次のフレームを準備する。これにより、９１４、９１８、及び９２２から情報を引き出すために、一つのみではなく、二つのサイクルが効果的に提供される。
【００７２】
様々な実施形態によれば、本発明のアーキテクチャは、厳密な優先順位と、加重ラウンドロビン出口スケジューリングアルゴリズムとをサポートする。特定の実施例によれば、Ｑキャッシュは、ヘッドストレージから、適格性、即ち、ポート優先キューの何れかの最初に送信するフレームが存在することを判断する。サブセグメントスケジューラから、ポート可用性情報を受領する。ポート内の全優先順位について、信用情報を維持する。多数の異なるスケジューリングアルゴリズムの何れかを局所的且つ効率的に計算する。アーキテクチャは、Ｑキャッシュに対する僅かな修正により追加される多くの新しいアルゴリズムに対応する。
【００７３】
特定の実施形態によれば、出口スケジューリングは、サブセグメントスケジューラ９０６からの出口スケジューリングアルゴリズム及び情報と、ポート毎のフロー制御とに基づいて、Ｑキャッシュ９２４において実行される。フレームが適格であり（即ち、フレームがカットスルーモードにおいて転送される状態であり、フレームの６４バイトが共有メモリアレイ９１０に格納されている、或いはフレームが格納及び転送モードで、フレーム全体が共有メモリアレイに格納されていることから、送信準備ができており）、ポートがフロー制御されていない場合には、出口スケジューリングアルゴリズムに入る。スケジューリングは、Ｑキャッシュ９２４のパイプライン回路の効率を高めるためにループ内で実現される。多数の標準的スケジューリングアルゴリズム、例えば厳密な優先順位及び加重ラウンドロビンを、このアーキテクチャにおいて効率的に実現し得る。加えて、ポート毎のフロー制御情報は、優先順位情報を含むことが可能であり、スイッチ要素が優先順位に基づくフロー制御に応答するのを可能にする。
【００７４】
特定の実施形態によれば、Ｑキャッシュ９２４は、１００スロットを有し、Ｔｘキュー９２２内の１００個のキューのそれぞれの先頭にあるフレームを各スロットが格納している。即ち、Ｑキャッシュ９２４は、ポート毎に四つまでのフレームを格納可能であり、各フレームは、四種類の優先順位の何れかを有する。サブセグメントスケジューラ９０６が特定のＴｘポートに対するフレームを要求する時、Ｑキャッシュ９２４は、そのポートに対する四個のキューの何れかに含まれるものを有する場合に、そのポートに対するフレームを送信する。Ｑキャッシュ９２４は、１００個のキューの一つを空にする時、Ｔｘキュー９２２に対して、１００個のキューの対応する一つにおける次のフレームの要求を送る。これは、このアーキテクチャの特にスケーラブルな態様である。
【００７５】
そのキュー内のフレームをＴｘキュー９２２が有すると仮定すると、Ｔｘキュー９２２は、そのエントリをＱキャッシュ９２４へ送るが、但し直接的にではない。Ｔｘキュー９２２は、フレームをヘッドストレージ９１４へ送り、フレームが最初にスケジューラに入った時にヘットストレージ９１４に格納されたフレームに関する情報を拾い出す。その後、完全なフレーム制御情報がＱキャッシュ９２４へ送られ、適切なスロットに格納される。
【００７６】
上記のように、サブセグメントスケジューラは、それぞれが送信する何かを有しているかについて、連続してスイッチポートをクエリするループ内で動作する。特定の実施形態によれば、サブセグメントスケジューラ９０６は、ループを連続して通過する際に、Ｑキャッシュ９２４からの特定のポートに対する新しいフレームを要求することを明確に却下される。これにより、サブセグメントスケジューラ９０６とＳＲＡＭアレイ９１０とのバースト性が平坦化され、そうでない場合には、サイクル毎に新たな最小サイズ（即ち、６４バイト）のフレームが関連することになる。これは、更に、必要なバッファリングの量と、こうしたバーストにより発生するジッタとを低減する。
【００７７】
特定の実施形態によれば、Ｑキャッシュに格納されたエントリは、エラーストレージ９１８から受領した、フレームに関する誤り情報を含む。エラーストレージ９１８の目的は、格納及び転送モードでの動作の際に、誤りによるフレームの抑制を容易にすることである。フレームがアレイに完全に入った場合、エラーストレージ９１８は、フレームが到着したＲｘポートがフレームに誤りの印を付けたかを示す誤りビットを格納する。このメカニズムにより、フレームの誤り情報は、フレームの終わりからフレームの始まりへ伝搬可能となる。この情報は、その後、フレームの抑制を容易にするためにサブスケジューラ９０６により使用される。
【００７８】
一方、システムがカットスルーモードで動作している場合、フレームの送信は、ＥＯＦが受領される前に既に開始され得る。こうした場合、サブセグメントスケジューラ９０６に受領された誤り情報（図９のＴＥ）は、出口タグ処理のため、単純にＴｘポートへ渡される。特定の実施形態によれば、カットスルーモードで送信中のフレームが不良と判断された場合、フレームのＣＲＣは、誤りの性質に応じて無効にしても、しなくてもよい。誤りが不良であるＣＲＣ自体の結果である場合、フレームは、同じＣＲＣと共に外部へ出ることが認められる。また、誤りが、フレーム内の別の何かに対応する場合、ＣＲＣは、フレームが外部に出る前に、例えば、Ｔｘポートにおいて無効にされる。
【００７９】
上記のように、エラーストレージ９１８に格納された誤りビットにより、サブセグメントスケジューラは、格納及び転送モードでのフレーム抑制を容易にできる。しかしながら、ＥＯＦが受領される前にフレーム転送が開始される場合（例えば、カットスルーモード）、エラーストレージ９１８の情報は、無視される。したがって、特定の実施形態によれば、特定のフレームについて、そのフレームに対する誤りビットが書き込まれる前にエラーストレージ９１８が読み出されているかを検出するロック機構が提供される。
【００８０】
こうしたロック機構を実現する一方法は、エラーストレージ９１８において誤りビット及び妥当性ビットを提供することである。妥当性ビットは、無効として開始される。ＥＯＦが誤り情報と共に着信した場合、これに対応して誤りビットが設定され、妥当性ビットは、有効に設定されて、誤り情報が現行のものであることを示す。その後、サブセグメントスケジューラ９０６は、Ｑキャッシュ９２４からフレームを読み出す時、妥当性ビットに注目して、誤りビットを無視するべきか否かを判断する。
【００８１】
しかしながら、こうしたアプローチでは、フレーム間に、妥当性ビットを設定し、その後リセットする必要がある。フレームを３００ＭＨｚ相当で書き込む上記の実施形態では、誤りビットも３００ＭＨｚ相当で書き込まれ、その後、同じ速度で読み出される。妥当性ビットのリセットも、この速度に一致させる必要があり、困難な設計上の問題を提示する。そのため、この付加的な速度要件を回避することが望ましい。
【００８２】
特定の実施によれば、妥当性ビットの極性は、関連する誤り情報が有効かを判断するのに利用される。即ち、妥当性ビットが使用される度に、極性は、反対の状態へ切り替えられる。その後、これをフレーム（実際には、フレームの第１のセグメント）の「極性」と比較し、誤りビットが有効かを判断する。フレームの極性は、フレームの第１のセグメントに対応するメモリ割り当てブロック９０８内のフリーリストのエントリにおいて、極性ビットにより表される。
【００８３】
各フレームに対するフリーリストのエントリは、更に、アレイに書き込まれる前にサブセグメントの読み出しが開始されない状態を確保するためにサブセグメントスケジューラ９０６が利用する、第２の極性ビットを含む。一実施形態によれば、この実施例は、直接的なロック機構である。メモリに格納された各セグメントにつき四個のサブセグメントの何れかにおいて、サブセグメントスケジューラに格納されたロッキングビットがフリーリストに記録された同じ極性と一致しない場合、データは未だにアレイに書き込まれておらず、サブセグメントスケジューラは、書き込みを待ってから、そのデータをスケジュールする。このロック機構を使用することで、サブセグメントスケジューラでは、サブセグメントレートで動作するために、フレーム毎に数ビットのみが必要となる。この速度はフレームレートの二倍であり、スイッチは、６４バイトのサブセグメントに対してカットスルーを実行することが可能となり、非常に待ち時間の低いスイッチにつながる。
【００８４】
上記のように、サブセグメントスケジューラ９０６は、全てのスイッチポートを「ループ」し、各ポートのＲｘ及びＴｘ部分の両方にサービスを提供する。特定の実施例において、サブセグメントスケジューラ９０６は、アレイ９１０内の４０９６セグメントによりインデックス化された４０９６スロットのＳＲＡＭを含む。サブセグメントスケジューラ９０６のアレイは、セグメントのリンク済みリストを格納するセグメントと、セグメントの最後のサブセグメントにおいて有効なバイト数を示すパディング情報と、用途について以下に説明する参照カウントとにより編成される。
【００８５】
幾つかの実施形態によれば、スイッチアーキテクチャ内のＳＲＡＭアレイの大部分は、シングルポートアレイとして実現されるが、サブセグメントスケジューラ９０６のＳＲＡＭアレイは、必要なリード及びライト速度に十分なマージンを提供するため、デュアルポートＳＲＡＭとして実現される。こうした一実施形態によれば、サブセグメントスケジューラ９０６のＳＲＡＭアレイは、出典を明記することでその開示内容全体を実質上本願明細書の一部とする、米国特許出第１０／８９０，８１６号（代理人整理番号ＦＵＬＣＰ００８）において説明されるデュアルポート１０Ｔ  ＳＲＡＭアレイとして実現される。
【００８６】
フレームの第１のサブセグメントは、アレイ９１０に着信する時、メモリ割り当て９０８及びヘッドストレージ９１４が選んだセグメントアドレスに書き込まれる。第１のサブセグメントの到着が、転送チャネル上のフレーム制御情報をスケジューラ９０２が利用可能となるより前か後かについて制約はないため、メモリ割り当て９０８及びヘッドストレージ９１４が実行するセグメントアドレスの割り当ては、各ポートに対して、一フレーム先に行われ、即ち、「事前の割り当て」が行われる。
【００８７】
即ち、システムが初期化される時、メモリ割り当て９０８は、開始セグメントアドレスをポート毎にヘッドストレージ９１４へ提供する（例えば、上記の２５ポートの実施形態での２５の異なるセグメントアドレス）。ヘッドストレージ９１４は、次に、こうしたセグメントアドレスポインタを、サブセグメントスケジューラ９０６に提供し、何れかのフレームが受信される前に、サブセグメントスケジューラ９０６がポート毎に割り当てられた開始セグメントを有するようにする。したがって、フレームの第１のセグメントが特定のＲｘポートで受信された時、サブセグメントスケジューラ９０６は、そのＲｘポートに対して事前に割り当てられたセグメントアドレスを読むことができる。ヘッドストレージ９１４は、転送チャネルでフレーム制御情報を受信し、上記の事前に割り当てられたアドレスを使用する時、メモリ割り当て９０８から別の事前に割り当てられたアドレスを取得し、そのＲｘポートのためにサブセグメントスケジューラ９０６に提示する
【００８８】
ＳＲＡＭアレイ９１０内のセグメントは、そのデータがＴｘポートへ送出される時、再使用のために解放される（即ち、メモリ割り当て９０８のフリーリストに再び置かれる）。しかしながら、特定のフレームのセグメントが廃棄される時には、Ｔｘポートへ送られないため、こうしたアドレスを解放するために別の機構を設ける必要がある。こうした機構の一つは、その「ポート」へ廃棄セグメントが送信されたかのように、アドレスを再びフリーリストへスプールする特別な廃棄Ｔｘユニットを使用する。
【００８９】
第２の実施例によれば、ヘッドストレージ９１４は、そのポートで受信されたフレームが廃棄されるべきものかを示す廃棄ビットを、Ｒｘポート毎にサブセグメントスケジューラへ提供する。この廃棄ビットは、全てがゼロの宛先マスクを含む、転送チャネルで送信されたフレーム制御情報に由来する。特定のフレームのための第１のセグメントは既に上記のように割り当てられているため、フレームに関して受信された最初の四つのサブセグメントは（フレームに廃棄の印がついているか否かに関係なく）、割り当てられたセグメントに対して書き込まれる。第１のセグメントのある程度の数（例えば、３又は４個）のサブセグメントが受信された後（廃棄ビットを設定できる十分な時間がある場合）、サブセグメントスケジューラ９０６は、ヘッドストレージ９１４により提供された廃棄ビットを読み出して、このフレームにアレイ９１０内の更なるセグメントを割り当てるべきかを判断する。サブセグメントスケジューラ９０６は、その後、ヘッドストレージ９１４へ返信する完了信号により、この廃棄の確認応答を行う。これにより、将来のフレームが同じアドレスを使用してスケジュールされるのを防止する。確認応答の仕組みは、競合状態を防止する。
【００９０】
更に、エラーストレージ９１８から待機室、及びその後の待機室からヘッドストレージ９１４への矢印により表される、エラーストレージ９１８内の極性ビットでの同様のロック問題が存在する。極性ビットの仕組みはフレーム廃棄の場合に困難となるため、次のフレームに極性が有効となるように、「間違った」極性がポインタデータに書き込まれる状態を維持することが重要である。こうしたループと、このロック機構とにより、この結果が達成される。
【００９１】
フレームが廃棄対象であることを廃棄ビットが示す場合、そのフレームには更なるセグメントは割り当てられない。逆に、既に割り当てられた第１のセグメントは、そのフレーム用に以前に受信されたサブセグメントに上書きされる後続のサブセグメントで、単純に再使用される。したがって、アレイ９１０内の単一のセグメントのみが、廃棄対象であるフレームに割り当てられる。廃棄対象のフレーム用のセグメントに対する書き込みが終了した時、そのセグメントは、次のフレームにおいて、そのポートに対する事前割当セグメントとして使用される。これにより、セグメントを解放するための別個のメカニズムは必要なくなる。
【００９２】
上記のように、廃棄されないフレームについては、そのフレームのサブセグメントを格納するために使用されたアレイ９１０内のセグメントは、各セグメントのコンテンツがＴｘポートへ送信される際に、再使用のために解放される。しかしながら、フレームがマルチキャストされている場合、そのセグメントは、単一のＴｘポートへの送信後に解放されるべきではない。即ち、セグメントは、フレームがマルチキャストされている最終のＴｘポートに対する送信時にのみ解放されるべきである。そのため、フレームが必要な数のＴｘポートに対して送信されたかを追跡する参照カウントを維持する。
【００９３】
このカウントは、例えば、転送チャネルを介してヘッドストレージ９１４が受信した宛先マスクから、セグメント毎に決定可能である。即ち、サブセグメントスケジューラ９０６は、Ｔｘポートへの特定のセグメントの送信を促進する度に、メモリ割り当て９０８への通知が可能であり、その後、メモリ割り当て９０８はカウントを減分できる。参照カウントがゼロに達すると、メモリ割り当て９０８は、セグメントをフリーリストに戻すことができる。
【００９４】
こうした回路の性能要件を考えると、このように参照カウントを実施することは、誤り及び妥当性ビットを参照して上記したものと殆ど同じ理由で、困難となる可能性がある。これは、特に、参照カウントを二度書き込み、一度読み出す必要のあるユニキャストの場合に当てはまる。そのため、特定の実施例によれば、フリーセグメントが割り当てられる時は常に、現在の参照カウントがゼロであることが分かっているという事実、即ち、セグメントがフリーリストに入るためには、その参照カウントがゼロでなくてはならないという事実から利点が得られる。参照カウントをポートまで増加させ、その後、ゼロに達するまで一つずつ減分する代わりに、この実施形態では、モジュロ演算と、有限ビットサイズカウンタとを採用して、同じ結果を達成する。
【００９５】
即ち、セグメントのコンテンツがＴｘポートに送信される度に、参照カウントに数が追加され、ポート数に達した時に、参照カウントがゼロに戻るようになる。セグメントが送信される、一つを除いた全てのポートについて、参照カウントに追加される数は、１である。残りのポートへの送信を表す数は、カウンタをゼロに戻すのに必要となる何らかの数である。したがって、全てのポートに対する数を参照カウントに追加した時（即ち、セグメントを全ての対象ポートに送信した時）、カウントはゼロに戻り、セグメントをフリーリストに戻し得ることを示す。ユニキャストの場合、数は、ゼロ、或いはカウンタの総カウント数、例えば、６ビットカウンタでは６４にすることができる。
【００９６】
参照カウントに追加されるべき数は、Ｒｘキュー９１６とＴｘキュー９２２との間でのマルチキャストの複製の時点で決定される。即ち、Ｒｘキュー９１６は、マルチキャストの複製を行う時、宛先ビットマスクを参照して、必要な参照カウントへの寄与を決定し、この数をＴｘキューのエントリと共に含める。したがって、Ｔｘキューの各エントリについて、上記のようにＱキャッシュ９２４を介してサブセグメントスケジューラ９０６へ提供され、最終的にメモリ割り当て９０８へ提供される参照カウント寄与数が存在する。
【００９７】
次に、フレームを廃棄する第２の機構について説明する。上記のフレーム廃棄機構は、フレームが廃棄対象であることを示すフレーム制御から受信された情報に依存する。しかしながら、フレーム制御情報に示されない、フレームを廃棄対象にする必要のある他のケースが存在する。例えば、フレームは、通常はフレーム制御情報の前に着信しないＥＯＦが示す誤りを有し得る。上記のように、こうした誤りは、フレームエントリがＱキャッシュ９２４内にある時にのみ明らかとなる。
【００９８】
加えて、イーサネットの仕様は、フレームがスイッチ内で「生存」を認められる最大時間を指定するタイムアウト要件を課す。時間を過ぎると（例えば、Ｑキャッシュ９２４に対するポーズ制御をアサートするポート、或いは低優先度トラフィックを止める高優先度トラフィックのバーストの結果）、フレームは、廃棄する必要がある。特定の実施形態において、フレームは、ヘッドストレージ９１４に着信する時、スロット内のフレームの何れかの期限が過ぎているかを判断するためにＱキャッシュが使用するタイムスタンプを受ける。
【００９９】
どのような場合でも、Ｑキャッシュ９２４内のフレームを廃棄すべきだと判断された時、サブセグメントスケジューラ９０６は、こうしたフレームを廃棄する。
【０１００】
アレイ９１０内のセグメントは、通常、全てのサブセグメントがＴｘポートへ送信された後でのみ、メモリ割り当て９０８のフリーリストに戻されることに留意されたい。しかしながら、この機構によりフレームを廃棄する時には、割り当てられていた第１のセグメント全体を即座に廃棄できる。連続フレームが廃棄される場合には、これにより、メモリ割り当て９０８が準備されたものより高い速度で解放されるセグメントが生じる可能性がある。そのため、ＦＩＦＯ９２６及びスロットル機構を、サブセグメントスケジューラ９０６とメモリ割り当て９０８との間に設けて、この状態に対処する。
【０１０１】
一つ以上のＴｘポートへのセグメントの送信が成功した結果として、サブセグメントスケジューラ９０６からメモリ割り当て９０８へトークンが送られる時、トークンは、無条件にＦＩＦＯ９２６に挿入される。しかしながら、フレームが廃棄されたためにトークンが送信されている場合、サブセグメントスケジューラ９０６は、ＦＩＦＯ９２６をクエリして、トークンを受領する余裕がＦＩＦＯにあるかを判断する。ある場合には、トークンがＦＩＦＯ９２６へ送信される。ない場合には、サブセグメントスケジューラ９０６は、ループ内で再度ＦＩＦＯ９２６をクエリする時（即ち、フレームが最初に対象としていたポートに次にサービスを提供する時）まで待つ。これは、ＦＩＦＯ９２６に余裕ができるまで継続する。最終的に、トークンは、メモリ割り当て９０８に達し、対応するセグメントはフリーリストに戻される。
【０１０２】
メモリ割り当て９０８は、混雑状態管理方針の処理のため、スケジューラからフレーム制御へチャネル「ステータス」に関するステータス状態を報告する。フレームプロセッサは、この情報を使用して、複雑な混雑状態管理方針の計算を、効率的な形で中央化し得る。これにより、更に、９１２から９１４への転送情報に、混雑状態管理処理の結果を含めることができる。こうした処理は、加重ランダム早期廃棄と、後部廃棄と、隣接スイッチへのＴｘ（又は出口）ポーズ信号の生成と、順方向又は逆方向での明示的な混雑状態の通知の生成と、他の形態の混雑状態管理とを含み得る。共有メモリアレイ９１０のメモリ割り当てでは、２５６バイトセグメントを使用するが、ステータスは、他の任意の基本セグメントサイズに音付いて報告してよい。例えば、一実施例では、１０２４バイトのセグメントサイズを使用して、ステータスチャネルのイベントレートを低減する。
【０１０３】
一部の実施形態によれば、フレームは、多数の論理キューに関連する。各キューは、確保された物理的メモリを必要とせず、フレームは、１）入口クロスバーがノンブロッキングであり、２）フレームが共有メモリに格納される際に混雑状態管理計算が適用され、３）フレーム内のデータについて、リンク済みリストにより順序付けが維持される場合、４）各出口スケジューリングキュー内のフレームについては９２２及び９２４により、多数のキューに関連付けし得る。こうした全ての条件は、図示した特定の実施例において多数のキューの関連付けを可能にするために必要となる。
【０１０４】
フレームを多数のキューに関連付けることで、共有メモリ９１０におけるデータの複製無しで、一組の豊富な混雑状態管理処理が可能となる。考えられる一実施例において、新しいフレームは、クロスバーを通過する入口でＲｘポートに関連付けられ、転送情報が９１２から受信された時にＴｘポートに関連付けられ、更にはメモリ全体に関連付けられる。フレーム制御９１２は、ステータス情報を照合する、混雑状態管理処理用の多数のウォーターマークを含み得る。特に、各ポートに対するプライベート割り当ての概念を含んでよく、その後、メモリ全体から各ポートのプライベートメモリの合計を引いたものとして「共有プール」値を作成してよい。Ｒｘプライベートウォータマークを上回るＲｘポートステータスは、共有プールに寄与し、その後、差異を提供する。
【０１０５】
別の実施例では、各フレームを関連付けした優先順位に基づいてステータス情報を生成し、ポート優先順位、或いは、スイッチ内で同じ優先度である全てのポートのパケットの合計である大域的優先順位にも基づいて、ステータス情報を混雑状態管理処理に使用できる。
【０１０６】
以上、本発明について、その特定の実施形態を参照して図示及び説明してきたが、本発明の趣旨又は範囲から逸脱することなく、開示した実施形態の形態及び詳細を変更し得ることは、当業者には理解されよう。例えば、本発明の実施形態について、本明細書ではイーサネット仕様を参照して説明してきた。しかしながら、本発明の基本原理は、様々なコンテキストでスイッチファブリックアーキテクチャを実現するのに使用し得ることは理解されよう。即ち、本発明は、例えば、イーサネット、シリアルラピッドＩ／Ｏ、アドバンスドスイッチング、任意のストリーミングプロトコル（例えば、ＴＤＭ、ＳＰＩ−４）、上位相プロトコル（例えば、ＴＣＰ／ＩＰ）、及びあるプロトコルを別のものにトンネリングする任意のアプリケーション（例えば、イーサネット上でのハイパトランスポート）を含め、事実上あらゆるプロトコル又は相互接続技術に対して実現し得る。
【０１０７】
更に、本発明の様々な利点、態様、及び目的について様々な実施形態を参照して本明細書で説明してきたが、本発明の範囲は、こうした利点、態様、及び目的の参照により限定されるべきではないことは理解されよう。本発明の範囲は、添付特許請求の範囲を参照して決定するべきである。
【図面の簡単な説明】
【０１０８】
【図１】本発明の特定の実施形態によるマルチポートスイッチを示すブロック図である。
【図２】本発明の特定の実施形態で使用するデータパスの部分を示すブロック図である。
【図３】本発明の特定の実施形態で使用するデータパスの部分を示すブロック図である。
【図４】本発明の特定の実施形態で使用するデータパスの部分を示す更に詳細なブロック図である。
【図５Ａ】本発明の特定の実施形態で使用するデータパスにおける制御の分布を示すブロック図である。
【図５Ｂ】本発明の特定の実施形態で使用するデータパスにおける制御の分布を示すブロック図である。
【図６】本発明の特定の実施形態で使用するデータパスにおける制御の分布を示す更に詳細なブロック図である。
【図７】本発明の特定の実施形態によるマルチポートスイッチ用のポートの受信部分を示すブロック図である。
【図８】本発明の特定の実施形態によるマルチポートスイッチ用のポートの送信部分を示すブロック図である。
【図９】本発明の特定の実施形態によるスケジューラの動作を示すブロック図である。
【図１】
2008527922.tif 000003
【図２】
2008527922.tif 000004
【図３】
2008527922.tif 000005
【図４】
2008527922.tif 000006
【図５Ａ】
2008527922.tif 000007
【図５Ｂ】
2008527922.tif 000008
【図６】
2008527922.tif 000009
【図７】
2008527922.tif 000010
【図８】
2008527922.tif 000011
【図９】
2008527922.tif 000012
【国際調査報告】
2008527922.tif 000013