(57)【要約】  本発明は、並列式の情報の生成、配布、および処理を行うシステム（９００）を対象とする。このスケーラブルでパイプライン化された制御およびスイッチングシステム（９００）は、着信する複数のデータストリーム（１３２、１３４）を効率的かつ公平に管理し、サービスクラスとサービス品質要求を適用する。本発明は、データパケットスイッチ（９３０）を制御するスケーラブルなＭＬＭＬスイッチファブリックも使用し、これにはデータパケットスイッチ（９３０）を制御するのに使用される要求処理スイッチ（１０４）が含まれる。また、各出力ポートへのすべてのデータフローを管理し、承認する、各出力ポートのための要求プロセッサ（１０６）と、要求プロセッサ（１０６）から要求元の入力ポートに応答パケットを送り返す応答スイッチ（１０８）も含まれる。
2005513827.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの入力ポートＡおよびＢ、複数の出力ポート、および入力ポートＡのメッセージＭＡを有する相互接続構造であって、メッセージＭＡのすべてまたは一部を前記相互接続構造に挿入する決定は、入力ポートＢへの１つまたは複数のメッセージの到着に少なくとも部分的に依存することを特徴とする相互接続構造。
【請求項２】
入力ポートＡを含む複数の入力ポート、出力ポートＸを含む複数の出力ポート、および入力ポートＡに到着するメッセージＭＡのすべてまたは一部を有する相互接続構造であって、前記相互接続構造にメッセージＭＡを挿入する決定は、出力ポートＸに関連付けられたロジックに少なくとも部分的に基づくことを特徴とする相互接続構造。
【請求項３】
入力ポートＢおよび入力ポートＢのメッセージＭＢをさらに含み、出力ポートＸのロジックは、前記相互接続構造にメッセージＭＡを挿入する決定を部分的にメッセージＭＢについての情報に基づいて行うことを特徴とする請求項２に記載の相互接続構造。
【請求項４】
メッセージＭＡおよびＭＢは、出力ポートＸを宛先とすることを特徴とする請求項３に記載の相互接続構造。
【請求項５】
前記相互接続構造にＭＡを挿入するタイミングは、少なくとも部分的に、入力ポートＢへの１つまたは複数のメッセージの到着に依存することを特徴とする請求項３に記載の相互接続構造。
【請求項６】
構造に入る複数の入力ポートおよび前記構造から出る複数の出力ポートと、前記相互接続構造の出力ポートＯを宛先とする入力ポートＰのメッセージＭＰと、入力ポートＰから出力ポートＯに関連付けられたロジックＬに要求を送信する手段とを有し、前記要求は、入力ポートＰから出力ポートＯにメッセージＭＰを送信することを求めることを特徴とする相互接続構造Ｓ。
【請求項７】
複数のデータ入力ポートおよび複数のデータ出力ポートと、前記複数のデータ入力ポートの２つ以上で着信データパケットを共同して監視する手段とを含むことを特徴とする相互接続構造。
【請求項８】
前記監視手段は、前記データ入力ポートの１つまたは複数に到着するデータパケットが出力ポートとして宛先とする前記複数のデータ出力ポートの１つに関連付けられることを特徴とする請求項７に記載の相互接続構造。
【請求項９】
前記複数のデータ出力ポートはそれぞれ、各自に関連付けられた監視手段を有することを特徴とする請求項８に記載の相互接続構造。
【請求項１０】
前記相互接続構造は、データスイッチ、要求スイッチ、および応答スイッチを含み、前記要求スイッチおよび応答スイッチは前記データスイッチに類似することを特徴とする請求項９に記載の相互接続構造。
【請求項１１】
前記監視手段は、前記要求スイッチおよび前記応答スイッチを含むことを特徴とする請求項１０に記載の相互接続構造。
【請求項１２】
前記監視手段は、前記データ入力ポートから前記データスイッチへの着信データパケットのフローを制御し、それにより前記相互接続構造の過負荷が防止されることを特徴とする請求項１１に記載の相互接続構造。
【請求項１３】
前記監視手段は、前記着信データパケットに含まれるサービス品質のパラメータに応じて前記データスイッチへのアクセスを許可することを特徴とする請求項１２に記載の相互接続構造。
【請求項１４】
前記監視手段は、着信データパケットが部分的に破棄されないことを保証し、深刻な過負荷状況中にはサービス品質が低いデータパケットのみが破棄されることを特徴とする請求項１３に記載の相互接続構造。
【請求項１５】
各データ入力ポートは入力カードを含み、前記入力カードは、前記要求スイッチに要求データパケットを送信して、宛先とするデータ出力ポートにデータパケットを送信する許可を求める手段を含むことを特徴とする請求項１４に記載の相互接続構造。
【請求項１６】
前記応答スイッチは、前記データスイッチにデータパケットを送信する許可を前記入力カードに与える手段を含むことを特徴とする請求項１５に記載の相互接続構造。
【請求項１７】
複数のデータ入力ポートからデータ出力ポートＺに選択的にデータパケットを転送する相互接続構造Ｎであって、出力ポートＺを宛先とするデータパケットの相互接続構造Ｎへの入力を制御する、出力ポートＺに関連付けられたロジックＬZを含むことを特徴とする相互接続構造。
【請求項１８】
ロジックＬZは、出力ポートＺに関連付けられたバッファのステータスに基づいて、相互接続構造Ｎへのデータパケットの入力をスケジュールすることを特徴とする請求項１７に記載の相互接続構造。
【請求項１９】
前記ロジックＬZは、出力ポートに関連付けられたバッファに通じるチャネルの帯域幅に基づいて、相互接続構造Ｎへのデータパケットの入力をスケジュールすることを特徴とする請求項１７に記載の相互接続構造。
【請求項２０】
前記ロジックＬZは、出力ポートＺからのチャネルの帯域幅に基づいて、相互接続構造Ｎへのデータパケットの入力をスケジュールすることを特徴とする請求項１７に記載の相互接続構造。
【請求項２１】
データ入力ポートＩに関連付けられたロジックＬIが、入力ポートＩから相互接続構造Ｎを通じて出力ポートＺにデータパケットＭを送信する許可を、出力ポートＬZに関連付けられた前記ロジックＬZに要求することを特徴とする請求項１８に記載の相互接続構造。
【請求項２２】
前記ロジックＬZは、相互接続構造Ｎを通じて出力ポートＺにデータパケットＭを送信する要求を受諾または拒否することを特徴とする請求項２１に記載の相互接続構造。
【請求項２３】
前記ロジックＬZは、将来の時間Ｔにおける相互接続構造ＮへのデータパケットＭの入力をスケジュールすることを特徴とする請求項２２に記載の相互接続構造。
【請求項２４】
メッセージのシーケンスＳが相互接続構造Ｎのデータ入力ポートで受信され、宛先とされる相互接続構造のデータ出力ポートに関連付けられたロジックが、Ｓの所定のメンバが入力ポートＮに入る所定の時間をスケジュールすることを特徴とする請求項１７に記載の相互接続構造。
【請求項２５】
前記入力ポートに関連付けられたロジックが前記シーケンスＳの順序を変えて、Ｓのメンバが、前記宛先とされるデータ出力ポートに関連付けられた前記ロジックによって決定される時間に相互接続構造Ｎに入るようにすることを特徴とする請求項２４に記載の相互接続構造。
【請求項２６】
前記シーケンスの順序の変更は、データを順次バッファに入れ、前記データを異なる順番で除去することによって実現されることを特徴とする請求項２５に記載の相互接続構造。
【請求項２７】
相互接続構造中への複数の入力ポートおよび前記相互接続構造からの複数の出力ポートを含み、ＰおよびＱが前記構造中への入力ポートであり、入力ポートＰおよびＱへのメッセージフローを共同して監視する手段を含むことを特徴とする相互接続構造Ｓ。
【請求項２８】
相互接続構造Ｓの出力ポートＯに関連付けられたロジックＬが、出力ポートＯを宛先とする入力ポートＰおよびＱ両方からのメッセージを監視することを特徴とする請求項２７に記載の相互接続構造。
【請求項２９】
前記ロジックＬは、入力ポートＰのメッセージが前記相互接続構造に入る許可を与えることを特徴とする請求項２８に記載の相互接続構造。
【請求項３０】
前記ロジックＬは、入力ポートＰのメッセージが前記相互接続構造に入る許可を拒否することを特徴とする請求項２８に記載の相互接続構造。
【請求項３１】
前記ロジックＬは、入力ポートＰのメッセージＭＰおよび入力ポートＱのメッセージＭＱが前記相互接続構造に入る許可を受諾するか、拒否するかの決定を行うために、ＭＰに関する情報とＭＱに関する情報を調べることを特徴とする請求項２８に記載の相互接続構造。
【請求項３２】
相互接続構造に入る複数の入力ポートおよび前記相互接続構造への複数の出力ポートと、前記相互接続構造の入力ポートＰにあり、前記相互接続構造の出力ポートＯを宛先とするメッセージＭＰと、入力ポートＰから出力ポートＯに関連付けられたロジックＬに、入力ポートＰがメッセージＭＰを出力ポートＯに送信するための要求を送信するように設計された装置とを含むことを特徴とする相互接続構造Ｓ。
【請求項３３】
前記ロジックが、入力ポートＰが前記相互接続構造を通じて出力ポートＯにメッセージＭＰを送信する許可を与えるか、または拒否するかは、少なくとも部分的には、メッセージＭＰについての情報と、入力ポートＰ以外の入力ポートにあり、同じく出力ポートＯを宛先とするメッセージについての情報とに基づくことを特徴とする請求項３２に記載の相互接続構造。
【請求項３４】
要求Ｒが入力ポートＰからロジックＬに送信され、前記要求は、入力ポートＰから相互接続構造Ｓを通じて出力ポートＯにメッセージＭＰを送信する許可を求めることを特徴とする請求項３３に記載の相互接続構造。
【請求項３５】
前記要求はデータパケットＲＰであることを特徴とする請求項３４に記載の相互接続構造。
【請求項３６】
データパケットＲＰは、入力ポートＰから相互接続構造Ｓを通じてロジックＬに送信されることを特徴とする請求項３５に記載の相互接続構造。
【請求項３７】
データパケットＲＰは、相互接続構造Ｓとは異なる相互接続構造Ｔを通じて入力ポートＰからロジックＬに送信されることを特徴とする請求項３２に記載の相互接続構造。
【請求項３８】
データパケットＲＰはデータを含むことを特徴とする請求項３５に記載の相互接続構造。
【請求項３９】
データパケットＲＰはデータを含まないことを特徴とする請求項３５に記載の相互接続構造。
【請求項４０】
前記入力ポートと出力ポートは、複数のノードおよび相互接続線を介して接続されることを特徴とする請求項３２に記載の相互接続構造。
【請求項４１】
前記相互接続構造の各出力ポートは、当該出力ポートに関連付けられたロジックＬを有することを特徴とする請求項４０に記載の相互接続構造。
【請求項４２】
相互接続構造を通じてメッセージＭＡを送信する方法であって、前記相互接続構造は、少なくとも２つの入力ポートＡおよびＢを有し、前記メッセージＭＡは入力ポートＡに到着し、前記方法は、
入力ポートＢへの１つまたは複数のメッセージの到着を監視するステップと、
前記相互接続構造にメッセージＭＡのすべてまたは一部を挿入する決定を、少なくとも部分的に前記入力ポートＢに到着するメッセージの監視に基づくステップと
を含むことを特徴とする方法。
【請求項４３】
相互接続構造を通じてメッセージＭＡを送信する方法であって、前記相互接続構造は、入力ポートＡと、出力ポートＸを含む複数の出力ポートを有し、メッセージＭＡのすべてまたは一部が入力ポートＡに到着し、前記方法は、
出力ポートＸに関連付けられたロジックを監視するステップと、
前記相互接続構造中にメッセージＭＡを挿入する決定を、少なくとも部分的に、Ｘを宛先とし、Ａ以外の入力で前記相互接続構造に入るメッセージＭＢに関する情報に基づくステップと
を含むことを特徴とする方法。
【請求項４４】
複数のデータ入力ポートと複数のデータ出力ポートを有する相互接続構造を通じてデータパケットを送信する方法であって、前記複数のデータ入力ポートの２つ以上で着信データパケットを共同して監視するステップを含むことを特徴とする方法。
【請求項４５】
複数のデータ入力ポートから相互接続構造Ｎを通じてデータ出力ポートＺにデータパケットを選択的に転送する方法であって、出力ポートＺを宛先とするデータパケットの前記相互接続構造Ｎへの入力を制御する、出力ポートＺに関連付けられたロジックＬZを監視するステップを含むことを特徴とする方法。
【請求項４６】
相互接続構造Ｓを通じてメッセージを送信する方法であって、前記相互接続構造は、複数の入力ポートと複数の出力ポートを含み、入力ポートＰのメッセージＭＰは出力ポートＯを宛先とし、前記方法は、
入力ポートＰから出力ポートＯに関連付けられたロジックＬに要求を送信するステップと、ロジックＬが、入力ポートＰから出力ポートＯにメッセージＭＰを送信する要求を承認するか、拒否するかを監視するステップと
を含むことを特徴とする方法。
【請求項４７】
モジュールＭ、および構造の非アクティブな部分であるモジュールＮを含む複数のモジュールから構成される相互接続システムであって、
前記モジュールＭに欠陥があるかどうかを判定する方法があり、前記モジュールＭに欠陥がある場合は自動的に前記モジュールＮに交換されることを特徴とする相互接続システム。
【請求項４８】
長さＬ1のメッセージセグメントＭ1が構造を通じてルーティングされ、長さＬ2のメッセージセグメントＭ2が前記構造を通じてルーティングされ、Ｌ1とＬ2は等しくなく、長さＬ1のメッセージセグメントのために確保された相互接続線と、長さＬ2のメッセージのために確保された別個の相互接続線があることを特徴とする相互接続構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示するシステムおよび動作方法は、次の特許および特許出願に開示される主旨に関連し、これらの特許および特許出願は参照により全体を本明細書に組み込まれる。
【０００２】
１．米国特許出願番号０９／００９，７０３（承認済みであるが未発行）「A Scaleable Low Latency Switch for Usage in an Interconnect Structure」、発明者Ｊｏｈｎ  Ｈｅｓｓｅ
２．米国特許第５，９９６，０２０号「A Multiple Level Minimum Logic Network」
３．米国特許出願番号０９／６９３，３５９「Multiple Path Wormhole Interconnect」、発明者Ｊｏｈｎ  Ｈｅｓｓｅ
４．米国特許出願番号０９／６９３，３５７「Scalable Wormhole-Routing Concentrator」、発明者Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄ
５．米国特許出願番号０９／６９３，６０３「Scaleable Interconnect Structure for Parallel Computing and Parallel Memory Access」、発明者Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄ
６．米国特許出願番号０９／６９３，３５８「Scalable Interconnect Structure Utilizing Quality-Of-Service Handling」、発明者Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈｅｓｓｅ
７．米国特許出願番号０９／６９２，０７３「Scalable Method and Apparatus for Increasing Throughput in Multiple Level Minimum Logic Networks Using a Plurality of Control Lines」、発明者Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈｅｓｓｅ
【０００３】
本発明は、音声およびビデオの通信システムおよびデータ／インターネット接続に適用することが可能な相互接続構造を制御する方法および手段に関する。より詳細には、本発明は、電子スイッチ、および電子的な制御を備えた光学スイッチに適用することが可能なインテリジェントな制御を備える最初のスケーラブルな相互接続スイッチ技術を対象とする。
【背景技術】
【０００４】
世界中での情報転送が今世紀の世界経済の原動力となることは疑いがない。現在、個人間、企業間、および国家間で転送される情報の量は、今後相当増加していくことが予想される。このため、近い将来多くの当事者間で伝達される多量の情報に対処する効率的で低コストのインフラストラクチャが整備されているかが死活問題となる。下記で述べるように、本発明は、この問題に対して肯定的に答える。
【０００５】
多数の通信分野の応用例に加えて、高度な並列スーパーコンピュータ、並列ワークステーション、密に結合されたワークステーションシステム、およびデータベースエンジンを含む各種の製品を可能にする数多くの他の応用例が存在する。デジタル信号処理を含む多数のビデオへの応用例がある。スイッチングシステムは、医療用画像処理を含む画像処理でも使用することができる。この他の応用例には、ビデオゲームや仮想現実を含む娯楽がある。
【０００６】
世界規模で多数の当事者間で行われる音声データおよびビデオを含む情報転送は、世界中に広がる通信ハイウェイを相互に接続するスイッチに依存する。例えばＣｉｓｃｏ社から供給される機器を代表とする現在の技術では、（例えばＯＳ−１９２プロトコルに対応する）１６個のＩ／Ｏスロットが使用可能で、全帯域幅で１６０ＧＢＳを提供することができる。Ｉ／Ｏスロットの数は、既存のＣｉｓｃｏ社製スイッチを選択的に相互接続することによって増すことができるが、その結果、コストが相当増大し、１ポート当りの帯域幅がかなり低下する。したがって、現在Ｃｉｓｃｏ社のスイッチが広く使用されているが、既存のＣｉｓｃｏ製品を代表とする現在の技術は、将来世界中の通信ハイウェイを流れる増大する多量の情報に対応することができない。近い将来当事者間で転送される多量の情報に対処するという現在の問題と予想される問題を軽減するために、本発明の譲受人によりパテントファミリーが形成されている。本発明の大きな前進を完全に理解するには、ここに組み込まれる先の発明を簡単に説明することが必要であり、これらの発明はすべて参照により本明細書に組み込み、本発明の基礎となる構築ブロックとなる。
【０００７】
そのようなシステムの１つである「A Multiple Level Minimum Logic Network」（ＭＬＭＬネットワーク）が１９９９年１１月３０日にＣｏｋｅ  Ｓ．Ｒｅｅｄに付与された米国特許第５，９９６，０２０（「発明＃１」）に記載され、同特許の教示は参照により本明細書に組み込まれる。発明＃１は、相互接続構造中で伝達されるメッセージパケットのタイミングと配置とに基づくデータフロー技術を利用するネットワークおよび相互接続構造を記載する。スイッチングの制御を構造中の複数のノードに分散して、グローバルな制御機能を提供する管理コントローラと複雑なロジック構造を回避する。このＭＬＭＬ相互接続構造は、各ノードにおける処理と記憶のオーバーヘッドを最小に抑える「デフレクション」あるいは「ホットポテト」システムとして動作する。グローバルコントローラの排除とノードにおけるバッファリングの排除により、相互接続構造中の制御およびロジック構造の量が大幅に減り、制御コンポーネントとネットワーク相互接続コンポーネント全体が簡略化すると同時に、パケット通信のスループットが向上し、低待ち時間が実現される。
【０００８】
より詳細には、Ｒｅｅｄ特許は、所望の出力ポートが利用可能になるまでパケットを保持するのではなく、追加的な出力ポートを通じて相互接続構造中の同じレベルのノードにメッセージパケットをルーティングすることにより、各ノードにおける処理と記憶のオーバーヘッドを大幅に減らす設計を記載する。この設計を用いると、各ノードでバッファを使用せずにすむ。
【０００９】
Ｒｅｅｄ特許の一態様によれば、ＭＬＭＬ相互接続構造は、複数レベル構造中の複数のノードと、そのノードを複数のレベル構造で選択的に接続する複数の相互接続線を含み、構造のレベルは、リッチに相互接続されたリングの集合を含み、複数のレベル構造は、レベルの階層中の複数のＪ＋１個のレベルと、各レベルにつき複数のＣ・２K個のノードを含む（Ｃは、ノードが位置するアングルの数を表す整数）。各ノードが隣接する外側のレベルのノードに続くノードであり、同じレベルのノードのすぐ後に続くノードである、相互接続構造中のデータ伝送の競合を解決するために、制御情報が送信される。すぐ前のノードからのメッセージデータは優先度が高い。制御情報が、あるレベルのノードから隣接する外側のレベルのノードに送信され、競合が発生しそうであることを警告する。
【００１０】
Ｒｅｅｄ特許は、パケットが、あるノードの入力ポートの利用可能性に基づいて相互接続構造中を進行し、パケットの最終的な宛先に至る従来技術に対して大きな前進である。Ｒｅｅｄ特許におけるノードは、各ノードの入力ポートで複数の同時のパケットを受信することができる。しかし、Ｒｅｅｄ特許の一実施形態では、入力パケットを送信することができるブロックされないノードの利用可能性が１つしか保証されないので、この実施形態では、実際には、Ｒｅｅｄ特許のノードは同時の入力パケットを受け付けることができない。しかしＲｅｅｄ特許は、各ノードが、現在のパケットレベルより１レベル以上下のレベルからの情報を考慮することができ、したがってスループットを減少し、ネットワーク中の待ち時間の低減を達成することを教示した。
【００１１】
最適なネットワーク構造を実現する第２の方式が、Ｊｏｈｎ  Ｅ．Ｈｅｓｓｅによって発明され、１９９８年１月２０日に出願された米国特許出願番号０９／００９，７０３（「発明＃２」：「A Scaleable Low Latency Switch for Usage in an Interconnect Structure」）に示され、述べられている。同特許出願は、本願と同じエンティティに譲渡され、その教示は参照によりすべてを本明細書に組み込まれる。発明＃２は、発明＃１に教示されるような、すべてのタイプのコンピュータ、ネットワーク、および通信システムで使用するための複数レベル最小ロジック（ＭＬＭＬ）の相互接続構造の機能性を拡張するスケーラブルな低待ち時間スイッチを記載する。発明＃２に記載されるスケーラブルな低待ち時間のスイッチを使用した相互接続構造は、パケットをネットワークに挿入するための新規の手順によりワームホールルーティングを実現する方法を用いる。このスケーラブルな低待ち時間のスイッチは、レベルおよび列で配列として配置された多数の極めて単純な制御セル（ノード）からなる。発明＃２では、配列の最上位レベル（外側のシリンダ）のすべてのブロックされていないノードに同時にパケットを挿入するのではなく、数クロック期間ずつ後に各列（アングルアングル）に挿入する。これによりワームホール伝送が望ましく達成される。さらに、どのノードでもパケットのバッファリングは行わない。ここで使用するワームホール伝送とは、パケットペイロードの最初の部分がスイッチチップを出る時に、そのパケットの最後尾がまだチップに入ってさえいないことを意味する。
【００１２】
発明＃２は、単一の電子集積回路でＭＬＭＬ相互接続の完全な実施形態を実施する方法を教示する。この単一チップの実施形態は、それを通じてデータパケットをワームホール伝送するセルフルーティングＭＬＭＬスイッチファブリックを構成する。同発明のスケーラブルな低待ち時間のスイッチは、多数の極めて単純な制御セル（ノード）からなる。制御セルは、配列に配置される。配列中の制御セルの数は設計パラメータであり、通例は６４〜１０２４個の範囲であり、通例は２のべき乗であり、配列はレベルと列（それぞれ発明＃１に記載されるシリンダとアングルに相当する）に配置される。各ノードは、２つのデータ入力ポートと２つのデータ出力ポートを有し、ノードは、大幅に低い待ち時間で相互接続を通じてパケットを移動する「ペアノード」設計など、より複雑な設計に形成することができる。列の数は通例は４〜２０個、あるいはそれ以上である。各配列が２J個の制御セルを含むとき、レベルの数は通例Ｊ＋１である。このスケーラブルな低待ち時間のスイッチは、スイッチのサイズ、パフォーマンス、およびタイプを決定する複数の設計パラメータに従って設計される。数十万個の制御セルを有するスイッチを単一のチップにレイアウトするので、有用なスイッチサイズは、ネットワークのサイズではなくピンの数によって制限される。同発明は、複数のチップを構築ブロックとして使用してより大型のシステムを構築する方法も教示する。
【００１３】
同発明のスイッチの一部の実施形態は、１対全または１対多のパケットのブロードキャストを行うマルチキャストのオプションを含む。このマルチキャストのオプションを使用すると、どの入力ポートも任意選択で多数またはすべての出力ポートにパケットを送信することができる。パケットはスイッチ内で複製して、１つの出力ポートにつき１つのコピーを生成する。マルチキャスト機能は、ＡＴＭおよびＬＡＮ／ＷＡＮスイッチ、スーパーコンピュータに関連する。マルチキャストは、集積回路のロジックをおよそ２０〜３０％増加させる追加的な制御線を使用して、単純な方式で実装する。
【００１４】
本発明の譲受人に譲渡されたパテントファミリーによって対処される次の問題は、発明＃１および＃２の概念を拡大し、一般化する。この一般化（発明＃３「Multiple Path Wormhole Interconnect」）は、米国特許出願番号０９／６９３，３５９において遂行されている。この一般化は、そのノードがそれ自体で発明＃２に記載されるタイプの相互接続であるネットワークを含む。また、発明＃２の変形形態も含まれ、これには、発明＃１および＃２の制御の相互接続に含まれるよりも大きく、種々のノードグループを接続するよりリッチな制御システムが含まれる。同特許は、各種のＦＩＦＯのレイアウト方式と、効率的なチップフロアの設計ストラテジについても述べている。
【００１５】
本発明と同じ譲受人に譲渡されたパテントファミリーによってなされた次の前進が、Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄが発明者であり、発明の名称が「Scalable Worm Hole-Routing Concentrator」である米国特許出願番号０９／６９３，３５７（「発明＃４」）に開示される。
【００１６】
通信ネットワークあるいはコンピュータネットワークは、例えば金属ケーブルや光ファイバーケーブルなどの通信媒体を通じて物理的に接続された数個または多数のデバイスからなることが知られている。ネットワークに含めることが可能なデバイスの１タイプは集線装置である。例えば、大規模な時分割方式のスイッチングネットワークは、中央スイッチングネットワークと、スイッチングネットワーク内の他のデバイスの入力端および出力端に接続された一連の集線装置を含むことができる。
【００１７】
集線装置は通例、複数のネットワークとの複数ポートの接続性、あるいは複数のネットワークのメンバ間の複数ポート接続性をサポートするために使用される。集線装置は、より少ない線に情報を集める、複数の共有通信線に接続されるデバイスである。
【００１８】
高度なパラレルコンピューティングシステムと通信システムに常に伴う問題は、多数の負荷が軽い線が、より少ない数のより負荷が重い線にデータを送信するときに発生する。この問題は、現在のシステムでは遮断を引き起こすか、あるいは待ち時間を増大させる可能性がある。
【００１９】
発明＃４は、遮断を回避することにより迅速にデータをルーティングし、情報の流れを改善し、実質的に制約がなくスケーラブルであり、低待ち時間と高スループットをサポートする集線装置構造を提供する。より詳細には、同特許は、制御信号を使用する制御セルを通じた単一ビットのルーティングを使用して情報集線装置の動作を大幅に向上させる相互接続構造を提供する。一実施形態では、この構造に入るメッセージパケットは決して破棄されず、したがって構造に入るパケットはいずれも構造を出ることが保証される。この相互接続構造は、複数のノードを交差しない経路で接続する相互接続線のリボンを含む。一実施形態では、相互接続線のリボンは、ソースレベルから宛先レベルまで複数のレベルを通って曲折して進む。曲折の数は、ソースレベルから宛先レベルに近づくに従って減少する。この相互接続構造はさらに、レベルの屈折を通じて横断方向にリボンを横切ってノードを結合する相互接続線によって形成される複数の列を含む。この相互接続構造を通じてデータを通信する方法は、複数の階層レベルを通じてデータパケットをルーティングする高速で最小限のロジックを使用する方法も組み込む。
【００２０】
本発明と同じ譲受人に譲渡されたパテントファミリーによってなされる次の前進が、Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄを発明者とし、発明の名称を「Scalable Interconnect Structure for Parallel Computing and Parallel Memory Access」とする米国特許出願番号０９／６９３６０３に開示されている（「発明＃５」）。
【００２１】
発明＃５によれば、相互接続構造中でデータは最上位のソースレベルから最低位の宛先レベルへと流れる。この相互接続の構造の多くの部分は、本明細書に組み込まれる他の特許の相互接続と同様である。しかし、重要な相違点がある。すなわち、発明＃５では、データの処理はネットワーク自体の中で行うことができ、そのためネットワークに入るデータはその経路に沿って一部変更され、ネットワーク自体の内部で計算が行われる。
【００２２】
同発明によれば、複数のプロセッサが、いくつかの革新的な技術を使用して同じデータにパラレルにアクセスすることができる。第１に、数個のリモートプロセッサが、同一のデータロケーションからの読み出しを要求することができ、その要求は重複した期間に満たされることができる。第２に、いくつかのプロセッサが、同じ場所に位置するデータ項目にアクセスすることができ、重複する時間に同じデータ項目の読み取り、書き込み、あるいは複数の操作を行うことができる。第３に、いくつかの場所に１つのデータパケットをマルチキャストすることができ、複数のパケットを目標とする複数の場所のセットにマルチキャストすることができる。
【００２３】
本発明の譲受人によってなされるさらなる前進が、Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈａｓｓｅを発明者とし、発明の名称を「Scalable Interconnect Structure Utilizing Quality-of-Service Handling」とする米国特許出願番号０９／６９３，３５８に記載されている（「発明＃６」）。
【００２４】
ネットワークまたは相互接続構造を通じて通信されるデータの重要な部分は、伝送中に優先処理を必要とする。
【００２５】
ネットワークシステムまたは相互接続システム中の情報またはパケットの大量のトラフィックは、輻輳を生じさせ、結果として情報の遅延や損失につながる問題を引き起こす可能性がある。多量のトラフィックがあると、システムは情報を格納し、その情報の送信を複数回試みる可能性があり、結果として通信セッションが延長され、伝送コストが増大する。従来、ネットワークまたは相互接続システムはすべてのデータを同じ優先度で処理することができ、すべての通信は、輻輳がひどい期間中には同じように低質のサービスになっていた。そのため、特定のデータタイプの伝送について最低限の要件を課せる各種のパラメータを記述するために適用することができる「サービス品質（ＱＯＳ）」が認識され、定義されている。ＱＯＳパラメータを利用して、帯域幅などのシステムリソースを割り振ることができる。ＱＯＳパラメータは、典型的に、セルの損失、パケットの損失、読み取りのスループット、読み取りのサイズ、時間遅延または待ち時間、ジッタ、累積遅延、およびバーストサイズの考慮を含む。ＱＯＳパラメータは、データパケットを直ちに転送しなければならないか、あるいは短い期間の後に破棄しなければならないマルチメディアの応用例におけるオーディオやビデオのストリーミング情報などの緊急のデータタイプに関連付けられることができる。
【００２６】
発明＃６は、高優先度の情報を、高サービス品質を処理する能力を備えるネットワークまたは相互接続構造を通じて伝達することを可能にするシステムおよび動作技術を対象とする。発明＃６のネットワークは、本明細書に組み込む他の発明の構造に類似する構造を有するが、ＱＯＳが高いメッセージにＱＯＳが低いメッセージを上回る優先度を与える追加的な制御線およびロジックを備える。また、一実施形態では、ＱＯＳが高いメッセージのための追加的なデータ線が提供される。発明＃６の一部の実施形態では、パケットのサービス品質レベルは、より低いレベルの最低限のサービス品質レベルに対して少なくとも所定のレベルでなければならないという追加的な条件がある。この所定のレベルは、ルーティングノードの場所によって決まる。この技術は、相互接続構造中の進行の初期段階で、サービス品質のより高いパケットが、サービス品質のより低いパケットより速く進むことを可能にする。
【００２７】
本発明の譲受人によってなされたさらなる前進が、Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈｅｓｓｅを発明者とし、発明の名称を「Scalable Method and Apparatus for Increasing Throughput in Multiple Level Minimum Logic Networks Using a Plurality of Control Lines」とする米国特許出願番号０９／６９２，０７３（「発明＃７」）に記載されている。
【００２８】
発明＃７では、ＭＬＭＬ相互接続構造は、階層的な複数レベル構造のノードを選択的に結合する複数の相互接続線を備えた複数のノードを含む。構造中のノードのレベルは構造中のノードの位置によって決まり、構造中では、データはソースレベルから宛先レベルに移動するか、あるいは複数レベル構造のあるレベルに沿って水平方向に移動する。データメッセージ（パケット）は、ソースノードから複数の指定される宛先ノードの１つに複数レベル構造を通じて伝送される。前記複数のノード中に含まれる各ノードは、複数の入力ポートと複数の出力ポートを含み、各ノードは、自身の入力ポートの２つ以上で同時のデータメッセージを受信することができる。各ノードは、そのノードが受信した各データメッセージを自身の出力ポートのうち別々のポートを通じて相互接続構造中の別個のノードに送信できる場合に、同時のデータメッセージを受信することができる。相互接続構造中のどのノードも、データメッセージを受信するノードより１つ以上下のレベルのノードに関する情報を受け取ることができる。発明＃７では、本明細書に組み込む他の発明よりも多くの制御相互接続線がある。この制御情報はノードで処理され、他の発明よりも多くのメッセージを所与のノードに流すことを可能にする。
【００２９】
上述の特許および特許出願からなるパテントファミリーは、すべて参照により本明細書に組み込まれ、本発明の基礎となる。
【発明の開示】
【発明が解決しようとする課題】
【００３０】
したがって、本発明の目的は、上述の発明を利用して、電子スイッチ、電子的制御を備える光学スイッチ、および完全に光学式のインテリジェントスイッチに使用することができるインテリジェントな制御を備えるスケーラブルな相互接続スイッチを作成することである。
【００３１】
本発明のさらなる目的は、完全なシステム情報を利用する最初の真のルータ制御を提供することである。
【００３２】
本発明の別の目的は、出力ポートの過負荷によりメッセージの破棄が要求された場合に、相互接続構造中で優先度が最も低いメッセージだけを破棄することである。
【００３３】
本発明のさらなる目的は、部分的なメッセージの破棄を決して許可せず、スイッチファブリックの過負荷を常に防止することである。
【００３４】
本発明の別の目的は、イーサネット（登録商標）パケット、インターネットプロトコルパケット、ＡＴＭパケット、およびＳｏｎｎｅｔフレームを含むすべてのタイプのトラフィックをスイッチングできるようにすることである。
【００３５】
本発明のさらなる目的は、すべてのフォーマットの光データをスイッチングするインテリジェントな光学ルータを提供することである。
【００３６】
本発明のさらなる目的は、テレビ会議を扱うエラーのない方法を提供し、またビデオあるいはビデオオンデマンド映画を配信する効率的で低コストの方法を提供することである。
【００３７】
本発明のさらなる全般的な目的は、既存のスイッチの帯域幅をはるかに上回り、電子スイッチ、電子的な制御を備える光スイッチ、および完全に光学式のインテリジェントスイッチに適用することができる、低コストで効率的なスケーラブル相互接続スイッチを提供することである。
【課題を解決するための手段】
【００３８】
従来技術を使用して実装することが不可能な大型のインターネットスイッチの実装には、２つの大きな要件が伴う。第１に、そのシステムは、大きく、効率的でスケーラブルなスイッチファブリックを含まなければならず、第２に、ファブリック中に移動するトラフィックを管理する包括的でスケーラブルな方法がなければならない。参照により組み込まれる特許は、セルフルーティング方式でノンブロッキングである高度に効率的でスケーラブルなＭＬＭＬスイッチファブリックを記載している。さらに、バースト性のトラフィックに対応するために、これらのスイッチは、所与の時間ステップ中に複数のパケットを同じシステム出力ポートに送信することができる。これらの機能のために、これらのスタンドアロンネットワークは、スケーラブルで自主管理型のスイッチファブリックを望まれるように提供する。バーストを除いてはシステム中のどのリンクも過負荷にならないことを保証する効率的で包括的なトラフィック制御を備えるシステムでは、参照により組み込まれる特許に記載されたスタンドアロンネットワークが、スケーラビリティとローカルの管理性の目標を満たす。しかし、対処すべき問題はなおある。
【００３９】
現実世界の状況では、包括的トラフィック管理は決して最適なものではなく、トラフィックは、長時間にわたってスイッチからの１つまたは複数の出力線が過負荷になるような形でスイッチに入る可能性がある。過負荷状態は、複数のアップストリームのソースが同じダウンストリームアドレスを有するパケットを同時に送信し、相当の時間にわたってそれを続ける時に発生する可能性がある。その結果生じる過負荷は深刻で、適当な量のローカルバッファリングでは対処することができない。トラフィックの一部を破棄せずにこの過負荷状態を解決できる種のスイッチを設計することは不可能である。したがって、アップストリームのトラフィック状況によってこの過負荷が発生するシステムでは、他のトラフィックを阻害することなく、原因となる（offending）トラフィックの一部を公平に破棄するための何らかのローカルの方法がなければならない。トラフィックの一部を破棄する場合、それは価値が低いトラフィックあるいはサービス品質の格付けが低いトラフィックであるべきである。
【００４０】
以下の説明では、用語「パケット」とは、インターネットプロトコル（ＩＰ）パケット、イーサネット（登録商標）フレーム、ＳＯＮＥＴフレーム、ＡＴＭセル、スイッチファブリックセグメント（より大きなフレームまたはパケットの一部）、あるいはシステムを通じて送信することを求める他のデータオブジェクトなどのデータ単位を指す。ここに開示するスイッチングシステムは、１つまたは複数のフォーマットの着信パケットを制御し、ルーティングする。
【００４１】
本発明では、参照により組み込まれる特許に記載された相互接続を使用して、従来技術で与えられるクロスバースイッチを含む各種のスイッチトポロジを管理する方法を示す。さらに、参照により組み込まれる特許に教示される技術を使用して各種の相互接続構造を管理し、サービス品質およびサービスタイプ、マルチキャスト、およびトランキング（trunking）に対応するスケーラブルで効率的な相互接続スイッチングシステムを構築する方法を示す。また、アップストリームのトラフィックパターンがローカルのスイッチングシステムで輻輳を生じさせうる状況を管理する方式も示す。ここに開示する構造および方法は、任意の種類のアップストリームのトラフィック状態を公平かつ効率的に管理し、ダウンストリームのポートおよび接続に輻輳を生じさせることなく着信する各パケットを管理する方式を決定するスケーラブルな手段を提供する。
【００４２】
また、ネットワークプロセッサと称することもあるラインカードプロセッサと物理媒体取付コンポーネントによって成されるＩ／Ｏ機能がある。以下の説明では、パケットの検出、バッファリング、ヘッダおよびパケットの解析、出力アドレスの検索、優先度の割り当ての機能、およびその他の一般的なＩ／Ｏ機能は、一般的なスイッチングおよびルーティングの実践で与えられるデバイス、コンポーネント、および方法によって行われると想定する。優先度は、スイッチングシステム１００の現在の制御状態と、サービスタイプ、サービス品質、および所与のパケットの緊急度や価値に関連する他の項目を含む着信するデータパケット中の情報に基づくことができる。この説明は主として、（１）その送信先、および（２）優先度、緊急度、クラス、およびサービスタイプが判定された後に着信パケットに行われる事柄に関連する。
【００４３】
本発明は、パラレルな制御情報の生成、配布、および処理を行うシステムである。このスケーラブルでパイプライン型の制御およびスイッチングシステムは、複数の着信データストリームを効率的かつ公平に管理し、サービスクラスとサービス品質の要件を適用する。本発明は、ここに組み込まれる発明に教示されるタイプのスケーラブルなＭＬＭＬスイッチファブリックを使用して、類似のタイプまたは否類似のタイプのデータパケットスイッチを制御する。換言すると、要求処理スイッチを使用してデータパケットスイッチを制御する。即ち、第１のスイッチは要求を送信し、他方第２のスイッチはデータパケットを送信する。
【００４４】
入力プロセッサは、アップストリームからデータパケットを受信すると送信要求パケットを生成する。この要求パケットは、そのデータパケットについての優先度情報を含んでいる。各出力ポートに要求プロセッサがあり、その出力ポートへのすべてのデータフローを管理し、承認する。要求プロセッサは、その出力ポートを対象とするすべての要求パケットを受信する。要求プロセッサは、データパケットをその出力ポートに送信してよいかどうか、および／またはその送信の時間を判定する。要求プロセッサは、各要求の優先度を調べ、より優先度が高いパケットまたはより緊急性の高いパケットをより早く送信するようにスケジュールする。出力ポートが過負荷の時には、要求プロセッサは低優先度または低価値の要求を拒絶する。本発明の中心的な特徴は、複数の入力ポートに到着するメッセージを共同して監視することである。各出力ポートに関連付けられた別個のロジックがあること、あるいは共同の監視がハードウェアで行われるか、ソフトウェアで行われるかということは重要でない。重要なのは、入力ポートＡへのパケットＭＡの到着に関する情報と、入力ポートＢへのパケットＭＢの到着に関する情報を併せて検討する手段が存在することである。
【００４５】
応答スイッチと称する第３のスイッチは、第１のスイッチと同様であり、要求プロセッサからの応答パケットを要求元の入力ポートに送り返す。出力ポートで過負荷が発生しそうな時間中は、要求は、害を及ぼさない形で要求プロセッサにより、破棄されることができる。これは、その要求が後の時間に容易に再び生成されることができるからである。データパケットは、出力ポートに送信する許可を与えられるまで入力ポートに格納され、過負荷中に許可を受け取らない低優先度のパケットが、所定の時間後に破棄されることができる。要求プロセッサは過負荷が生じることを許さないので、出力ポートは決して過負荷になることがない。過負荷状態中に、より優先度が高いデータパケットは出力ポートに送信することを許可される。出力ポートで過負荷が発生そうな時、低優先度のパケットが、より優先度が高いパケットをダウンストリームに送信することを妨げることはできない。
【００４６】
入力プロセッサは、それが送信を行う先の出力場所のみから情報を受け取り、要求プロセッサは、その要求プロセッサへの送信を求める入力ポートのみから要求を受け取る。これらの動作はすべてパイプライン化した並列方式で行われる。重要な点として、所与の入力ポートプロセッサおよび所与の要求プロセッサの処理の仕事量は、Ｉ／Ｏポートの総数が増加するのに比例して増加しない。要求、応答、およびデータを送信するこのスケーラブルなＭＬＭＬスイッチファブリックは、ポート数に関係なく、同じ１ポート当りのスループットを有利に維持する。したがって、この情報生成、処理、および配布のシステムは、サイズにアーキテクチャ上の制限がない。
【００４７】
この輻輳が生じないスイッチングシステムは、データスイッチ１３０と、パケットがデータスイッチに入るのを許可する可否とその時間を決定するスケーラブルな制御システムとから構成される。この制御システムは、入力コントローラのセット１５０、要求スイッチ１０４、要求プロセッサのセット１０６、応答スイッチ１０８、および出力コントローラ１１０から構成される。一実施形態では、システムの各出力ポート１２８につき１つの入力ポートコントローラＩＣ１５０と１つの要求プロセッサＲＰ１０６がある。制御システムにおける要求および応答（回答）の処理は、データスイッチを通じたデータパケットの送信と重なった方式で行われる。制御システムが一番最近到着したデータパケットについての要求を処理する間に、データスイッチは、以前の周期に肯定の応答を受け取ったデータパケットを送信することにより、自身のスイッチング機能を実行する。
【００４８】
データスイッチの輻輳は、輻輳を生じさせると思われるトラフィックをデータスイッチに入れないことによって防止される。一般的に、この制御は、到着したパケットに行う動作を決定するデータスイッチの論理的な相似形を使用することによって実現する。このデータスイッチの相似形を要求コントローラ１２０と呼び、これは、通常は少なくともデータスイッチ１３０と同じ数のポートを備える要求スイッチファブリック１０４を含む。要求スイッチは、データスイッチによって処理される大きなデータパケットではなく、小さな要求パケットを処理する。入力コントローラ１５０にデータパケットが到着すると、入力コントローラは、要求パケットを生成し、要求スイッチに送信する。この要求パケットは、送信元の入力コントローラを識別するフィールドと優先度情報を示すフィールドを含む。これらの要求は要求プロセッサ１０６によって受け取られるが、それぞれの要求プロセッサ１０６は、データスイッチの出力ポートの代表である。一実施形態では、各データ出力ポートにつき１つの要求プロセッサがある。
【００４９】
入力コントローラの機能の１つは、到着するデータパケットを固定長のセグメントに分割することである。入力コントローラ１５０は、ターゲット出力ポートのアドレス２１４を含むヘッダを各セグメントの前に挿入し、そのセグメントをデータスイッチ１３０に送信する。受け取った出力コントローラ１１０によりセグメントをリアセンブルしてパケットにし、ラインカード１０２の出力ポート１２８を通じてスイッチから送信する。所与のパケット送信周期に線１１６を通じて１つのセグメントしか送信できないスイッチに適した単純な実施形態では、入力コントローラは、データスイッチを通じて単一のパケットを送信する要求を行う。要求プロセッサは、データスイッチへのパケットの送信について入力コントローラに対する許可を承認または拒否する。第１の方式では、要求プロセッサは、パケットの単一のセグメントだけを送信する許可を与え、第２の方式では、要求プロセッサは、パケットの全セグメントまたは多くのセグメントを送信する許可を与える。この第２の方式では、セグメントは、セグメントのすべてまたは大半が送信されるまで連続的に送信される。１つのパケットを構成するセグメントは、中断せずに連続的に送信することができ、あるいは、図３Ｃに示すようなスケジュールされた方式で各セグメントを送信して他のトラフィックが伴うことを可能にすることができる。第２の方式には、入力コントローラが行う要求がより少なく、したがって要求スイッチがよりビジーでなくなる利点がある。
【００５０】
要求周期中に、要求プロセッサ１０６は、零個、１つまたは複数の要求パケットを受信する。少なくとも１つの要求パケットを受信した各要求プロセッサは、優先度によってパケットにランク付けし、１つまたは複数の要求を承認し、残りの要求を拒否することができる。要求プロセッサは、直ちに応答（回答）を生成し、応答スイッチＡＳ１０８と称する第２のスイッチファブリック（ＭＬＭＬスイッチファブリックであることが好ましい）により応答を入力コントローラに返す。要求プロセッサは、承認された要求に対応する受諾の応答を送信する。一部の実施形態では、拒否の応答も送信する。別の実施形態では、要求および応答は、スケジューリングの情報を含む。応答スイッチは、要求プロセッサを入力コントローラに接続する。受諾の応答を受信した入力コントローラは、対応するデータパケットセグメントを次の１つまたは複数のデータ周期またはスケジュールされた時間にデータスイッチに送信することを許可される。受諾を受け取らなかった入力コントローラは、データスイッチにデータパケットを送信しない。そのような入力コントローラは、パケットが最終的に受諾されるまで後の周期に要求を提出することができ、あるいは、要求が繰り返し拒否された後にデータパケットを破棄することができる。入力コントローラは、その入力バッファ中でパケットが古くなるにつれてパケットの優先度を上げることもでき、より緊急性の高いトラフィックを送信することを有利に可能にする。
【００５１】
ある要求が承認されたことを入力プロセッサに通知するのに加えて、要求プロセッサはまた、ある要求が拒否されたことを要求プロセッサに通知することができる。要求が拒否された場合には、追加的な情報を送信することができる。後に行う要求が成功する可能性についてのこの情報は、要求される出力ポートに送信を行いたい他の入力コントローラの数、他の要求の相対的な優先度、および出力ポートのビジー度に関する最近の統計についての情報を含むことができる。具体的な例で、要求プロセッサが５つの要求を受信し、そのうち３つを承認できるとする。この要求プロセッサが行う処理の量は最小限である。すなわち、優先度によって要求にランク付けし、そのランクに基づいて３つの受諾応答パケットと２つの拒否応答パケットを送信するだけでよい。受諾を受け取った入力コントローラは、次のパケット送信時間からセグメントを送信する。一実施形態では、拒否を受け取った入力コントローラは、何周期か待機した後に、拒否されたパケットについてもう１回要求を提出することができる。他の実施形態では、要求プロセッサは、要求プロセッサがデータスイッチを通じてセグメントパケットを送信する将来の時間をスケジュールすることができる。
【００５２】
相当数の入力ポートが、単一の出力ポートを通じてダウンストリームに送信すべきパケットを受信した時には潜在的な過負荷状況が発生する。その場合、入力コントローラは、単独で、また迫りつつある過負荷についての知識を持たずに、要求スイッチを通じて同じ要求プロセッサに各自の要求パケットを送信する。重要な点として、要求スイッチ自体が輻輳することはない。その理由は、要求スイッチは、固定された最大数の要求のみを要求プロセッサに送信し、残りの要求はスイッチファブリック中で破棄するためである。換言すると、要求スイッチは、自身のどの出力ポートを通じても固定数の要求しか許可しないように設計される。その数を超えるパケットは、一時的に要求スイッチファブリック内で循環するが、予め設定された時間後に破棄され、ファブリック中の輻輳を防止する。したがって、所与の要求に関連して、入力コントローラは、受諾、拒否、または無応答を受け取ることができる。以下を含むいくつかの可能な応答がある。
・次のセグメント送信時間にパケットの１セグメントだけを送信する。
・次の送信時間からすべてのセグメントを順次送信する。
・要求プロセッサによって規定された将来のある時間からすべてのセグメントを順次送信する。
・各セグメントについて規定された将来の時間にセグメントを送信する。
・データスイッチにセグメントを一切送信しない。
・拒否の応答が返されたか、応答が返されないことにより、その要求プロセッサに提出された要求が多すぎたために要求が損失したことが通知されたので、データスイッチにセグメントを送信せず、少なくとも指定される時間量だけ待機してから要求を再度提出する。
【００５３】
あるデータパケットに対して拒否を受け取った入力コントローラは、そのデータパケットを自身の入力バッファに保持し、拒否されたそのパケットについて後の周期に別の要求パケットを再度生成することができる。入力コントローラが要求パケットを破棄しなければならない場合でも、システムは効率的かつ公平に機能する。過度の過負荷となる具体的な例では、２０個の入力コントローラが、同じ時間に同じ出力ポートにデータパケットを送信することを求めるとする。これら２０個の入力コントローラはそれぞれ、その出力ポートにサービスする要求プロセッサに要求パケットを送信する。要求スイッチは、例えばそのうち５つのパケットを要求プロセッサに転送し、残りの１５個を破棄する。１５個の入力コントローラは一切通知を受け取らず、その出力ポートに深刻な過負荷状態が存在していることが示唆される。要求プロセッサにより５つの要求のうち３つが承認され、２つが拒否される場合は、拒否の応答を受け取るか、または応答を受け取らない１７個の入力コントローラは、後の要求周期にその要求を再度行うことができる。
【００５４】
「複数選択」の要求処理は、１つまたは複数の拒否を受け取った入力コントローラが、直ちに別々のパケットについて１つまたは複数の追加的な要求を行うことを可能にする。単一の要求周期は、２つ以上の副周期あるいは段階を有する。一例として、入力コントローラがそのバッファに５つあるいはそれ以上のパケットを有するとする。さらに、このシステムが、所与のパケット送信周期中に入力コントローラがデータスイッチを通じて２つのパケットセグメントを送信できるシステムであるとする。要求プロセッサは、最も高いランクの優先度を有する２つのパケットを選択し、対応する要求プロセッサに２つの要求を送信する。さらに、要求プロセッサが１つのパケットを受諾し、他のパケットを拒否するとする。入力コントローラは、直ちに別のパケットについての別の要求を異なる要求プロセッサに送信する。その要求を受け取る要求プロセッサは、その入力コントローラがそのパケットのセグメントをデータスイッチに送信する許可を受諾または拒否する。したがって、そうでなければ次の完全な要求周期まで待たなければならないのに対して、拒否を受け取った入力コントローラは、第２希望のデータパケットを送信することを許可され、そのバッファを有利に空にする。この要求と応答のプロセスは、要求周期の２番目の段階に完了する。第１回目に拒否された要求をバッファに保持しても、第１回および第２回に受諾された他の要求をデータスイッチに送信することができる。トラフィック条件と設計パラメータに応じて、３番目の段階にさらにもう１回試行を行うことができる。このようにして、入力コントローラは、各自のバッファからデータを出し続けることができる。したがって、入力コントローラが所与の時間にデータスイッチの線１１６を通じてＮ個のパケットセグメントを送信することができる場合、入力コントローラは、所与の要求周期に最高Ｎ個の同時の要求を要求プロセッサに対して行うことができる。その要求のうちＫ個が承認される場合、入力コントローラは、Ｎ−Ｋ個のパケットからなる別のセットをデータスイッチを通じて送信するための第２の要求を行うことができる。
【００５５】
あるいはまた別の実施形態では、入力コントローラは、いつデータスイッチにパケットを送信できる状態となるかを知らせるスケジュールを要求プロセッサに提供する。このスケジュールは、要求を行っている他の入力プロセッサのスケジュールおよび優先度の情報と、出力ポート自体の可用性のスケジュールと併せて要求プロセッサによって調べられる。要求プロセッサは、いつデータをスイッチに送信すべきかを入力プロセッサに知らせる。この実施形態は、制御システムの仕事量を減らし、全体のスループットを有利に高める。このスケジュール法の別の利点は、現在個々の出力ポートへの送信を求めているすべての入力プロセッサについての情報がより多く要求プロセッサに提供され、したがって、要求プロセッサが、どの時間にどの入力ポートが送信できるかについてより多くの情報に基づいた決定を行うことができ、それによりスケーラブルな手段における優先度、緊急性、および現在のトラフィック状況の平衡が保たれることである。
【００５６】
概して、入力コントローラは、同時にデータスイッチに送信することが可能な数より少ないパケットをそのバッファに有し、そのため複数選択のプロセスは滅多に行われないことに留意されたい。ただし、重要な点として、輻輳が発生しそうになるのは、データスイッチにおける輻輳を防止し、サービスの優先度、タイプおよびクラス、およびその他のＱＯＳパラメータに基づいて効率的かつ公平にトラフィックを下流に移動するためにここに開示するグローバル制御システムが最も必要とされるその時である。
【００５７】
上述の実施形態では、パケットがデータスイッチに入ることを拒否された場合は、後の時間に入力コントローラがその要求を再度提出することができる。他の実施形態では、要求プロセッサは、その要求が送信されたことを記憶しており、後に機会が利用可能である時に送信の許可を与える。一部の実施形態では、要求プロセッサは受諾の応答しか送信しない。他の実施形態では、要求プロセッサはすべての要求に応答する。その場合、要求プロセッサに到着する各要求に対して、入力コントローラは要求プロセッサから応答パケットを得る。パケットが拒否された場合は、この情報は時間セグメントＴを与えることができ、要求プロセッサは要求を再提出する前に時間Ｔだけ待機しなければならない。あるいは、要求プロセッサは、要求プロセッサにおける競合するトラフィックのステータスを記述する情報を与えることもできる。この情報は、制御システムによってすべての入力コントローラにパラレルに配信され、常に現在の最新の情報である。有利な点として、入力コントローラは、拒否されたパケットが受諾される可能性とその時間を判定することができる。関連のない情報は提供も生成もされない。このパラレルな情報配信法の望ましい結果は、各入力コントローラが、共通の要求プロセッサへの送信を求めるすべての他の入力コントローラ、そしてそれらの入力コントローラのみの保留中のトラフィックについての情報を持つことである。
【００５８】
一例として、過負荷状況中に、入力コントローラが、最近要求が拒否された４つのパケットをそのバッファに有するとする。４つの要求プロセッサはそれぞれ、入力コントローラが４つのパケットそれぞれが後の時間に受諾される可能性を推定することができる情報を送信している。入力コントローラは、受諾の確率と優先度に基づいてパケットを破棄するか、またはその要求を形成し直して、システム１００を通じて効率的にトラフィックを転送する。ここに開示する制御システムは、重要な点として、スイッチに送信するトラフィックを公平かつ公正に決定するのに必要とするすべての情報を各入力コントローラに与える。スイッチは決して輻輳せず、低待ち時間で動作する。ここに開示する制御システムは、参照により本明細書に組み込む特許に開示されるスイッチとクロスバースイッチなどのスイッチに、スケーラブルなグローバル制御を容易に提供することができる。
【００５９】
入力コントローラは、入力コントローラ「にある」データについて要求を行う。そのデータは、あるメッセージからの他のデータが到着していない時に到着したメッセージの一部である可能性があり、入力ポートのバッファに格納されたメッセージ全体から構成される場合も、あるいはメッセージの一部がすでにデータスイッチを通じて送信されている場合にはメッセージのセグメントから構成される場合もある。上述の実施形態では、入力コントローラがデータスイッチにデータを送信する要求を行うと、要求が承認され、その後データは常にそのデータスイッチに送信される。したがって、例えば、入力コントローラがデータスイッチに通じるデータ搬送線を４本有する場合、その入力コントローラは、５本の線を使用する要求は決して行わない。別の実施形態では、入力コントローラは、それが使用できるより多くの要求を行う。要求プロセッサは、１つの入力コントローラにつき最大で１つの要求を受け入れる。入力コントローラが複数の受諾を受け取る場合、入力コントローラは、１つのパケットをデータスイッチに送信するようにスケジュールし、次の回に、すべての追加的な要求の２回目の要求を行う。この実施形態では、出力コントローラは、決定を行うための情報をより多く持ち、したがってより適切な決定を行うことができる。ただし、この実施形態では、要求手順の各回がより高費用になる。さらに、入力コントローラからデータスイッチに４本の線があり、時間のスケジュールを用いないシステムでは、１回のデータ送信につき少なくとも４回の要求を行う必要がある。
【００６０】
また、マルチキャストとトランキングを行う手段が必要となる。マルチキャストとは、１つの入力ポートから複数の出力ポートにパケットを送信することを言う。ただし、数個の入力ポートが多数のマルチキャストパケットを受信するとどのシステムでも過負荷になる可能性がある。したがって、過度なマルチキャストを検出し、それを制限することにより輻輳を防止することが必要である。具体例として、不良状態にあるアップストリームのデバイスが連続的な一連のマルチキャストパケットを送信し、各パケットがダウンストリームのスイッチで増加されて、深刻な輻輳が生じる可能性がある。下記のマルチキャスト要求プロセッサは、過負荷のマルチキャストを検出し、必要な場合にはそれを制限することができる。トランキングとは、同じダウンストリーム経路に接続された複数の出力ポートを統合することを言う。通例は、複数のデータスイッチ出力ポートをダウンストリームに光ファイバーなどの高容量の伝送媒体と接続する。このポートのセットをしばしばトランクと称する。異なるトランクが、異なる数の出力ポートを有することができる。そのトランクに向かうパケットにはそのセットのメンバである出力ポートをいずれも使用することができる。トランキングサポートの手段を本明細書に開示する。各トランクは、データスイッチ中に単一の内部アドレスを有する。そのアドレスに送信されるパケットは、データスイッチにより、そのトランクに接続された利用可能な出力ポートに送信され、トランク媒体の容量を望ましく利用する。
【発明を実施するための最良の形態】
【００６１】
図１に、複数のラインカード１０２に接続されたデータスイッチ１３０および制御システム１００を示す。ラインカードは、入力線１３４を通じてスイッチおよび制御システム１００にデータを送信し、線１３２を通じてスイッチおよび制御システム１００からデータを受信する。ラインカードは、外部と接続された複数の入力線１２６および出力線１２８を通じて外部世界とのデータの送受信を行う。相互接続システム１００はデータを送信および受信する。すべてのパケットは、ラインカード１０２を通じてシステム１００に入り、システム１００から出る。システム１００に入るデータは、長さが様々に異なるパケットの形態である。Ｊ個のラインカードをＬＣ0、ＬＣ1、．．．、ＬＣJ-1と表す。
【００６２】
ラインカードは、複数の機能を行う。ラインカードは、従来技術で与えられる標準的な伝送プロトコルに関連するＩ／Ｏ機能を行うのに加えて、パケット情報を使用して物理的な出力ポートアドレス２０４とサービス品質（ＱＯＳ）２０６をパケットに割り当てる。ラインカードは、パケットを図２Ａに示すフォーマットに構築する。パケット２００は、ＢＩＴ２０２、ＯＰＡ２０４、ＱＯＳ２０６、およびＰＡＹ２０８の４つのフィールドから構成される。ＢＩＴフィールドは、常に１に設定され、パケットの存在を示す１ビットフィールドである。出力アドレスフィールドＯＰＡ２０４は、ターゲット出力のアドレスを含む。一部の実施形態では、ターゲット出力の数はラインカードの数と等しい。他の実施形態では、データスイッチは、ラインカードの数より多くの出力アドレスを有することができる。ＱＯＳフィールドは、サービス品質のタイプを示す。ＰＡＹフィールドは、ＯＰＡアドレスで指定される出力コントローラ１１０にデータスイッチ１３０を通じて送信するペイロードを含む。一般に、着信するパケットは、ＰＡＹフィールドよりもかなり大きい場合がある。セグメンテーションおよびリアセンブリ（ＳＡＲ）技術を使用して、着信パケットを複数のセグメントに再分割する。一部の実施形態ではすべてのセグメントを同じ長さにし、他の実施形態ではセグメントの長さは異なってよい。各セグメントを、データスイッチを通じたパケット２００の一連の伝送のＰＡＹフィールドに入れる。出力コントローラは、セグメントのリアセンブリを行い、完成したパケットをラインカードを通じて下流に転送する。この方法により、システム１００は、長さに大きなばらつきがあるペイロードに対処することができる。ラインカードは、到着するパケットのヘッダ中の情報からＱＯＳフィールドを生成する。ＱＯＳフィールドを構築するのに必要な情報はＰＡＹフィールドに残すことができる。その場合、システム１００は、もはや使用しない時にはＱＯＳフィールドを破棄することができ、下流のラインカードはＰＡＹフィールドからサービス品質の情報を得ることができる。
【００６３】
図２に各種パケットのデータのフォーマッティングを示す。
【００６４】
表１に、パケットのフィールド内容の概要を簡単に示す。
【００６５】
【表１】
2005513827.tif 000003
【００６６】
ラインカード１０２は、図２Ａに示すパケット２００を伝送線１３４を通じて入力コントローラ１５０に送信する。入力コントローラをＩＣ０、ＩＣ１、．．．ＩＣＪ−１と表す。この実施形態では、入力コントローラの数はラインカードの数と同じに設定する。一部の実施形態では、１つの入力コントローラが複数のラインカードを処理することができる。
【００６７】
入力コントローラおよび出力コントローラによってなされる機能の一覧により、システム全体の動作の概要を提供する。入力コントローラ１５０は、少なくとも以下の６つの機能を行う。
１．長いパケットを、データスイッチによって都合良く処理されることができるセグメント長に分割する。
２．自身が使用する制御情報、および要求プロセッサが使用する制御情報を生成する。
３．着信パケットをバッファリングする。
４．データスイッチを通じてパケットを送信する許可を求める要求を要求プロセッサに対して行う。
５．要求プロセッサから応答を受け取り、処理する。
６．データスイッチを通じてパケットを送信する。
【００６８】
出力コントローラ１１０は、次の３つの機能を行う。
１．データスイッチからパケットまたはセグメントを受け取り、バッファリングする。
２．データスイッチから受け取ったセグメントをリアセンブルして、ラインカードに送信する完全なデータパケットにする。
３．リアセンブルしたパケットをラインカードに送信する。
【００６９】
制御システムは、入力コントローラ１５０、要求コントローラ１２０、および出力コントローラ１１０から構成される。要求コントローラ１２０は、要求スイッチ１０４、複数の要求プロセッサ１０６、および応答スイッチ１０８から構成される。制御システムは、パケットまたはセグメントをデータスイッチに送信すべきか、そしていつ送信すべきかを判定する。データスイッチファブリック１３０は、入力コントローラ１５０から出力コントローラ１１０にセグメントをルーティングする。次いで、制御およびスイッチングの構造と制御方法を詳細に説明する。
【００７０】
入力コントローラは、直ちには、着信パケットＰを、線１１６、データスイッチを通じて、Ｐのヘッダに指定される出力ポートに送信しない。この理由は、データスイッチから、Ｐの宛先に至る出力ポートまでの経路１１８に最大の帯域幅があり、複数の入力が同じ出力ポートに一度に送信すべきパケットを有する可能性があるためである。さらに、入力コントローラ１５０からデータスイッチ１３０への経路１１６に最大の帯域幅があり、出力コントローラ１１０に最大のバッファ空間があり、出力コントローラからラインカードまでに最大のデータ転送速度がある。パケットＰは、これらのコンポーネントのいずれかに過負荷を生じさせる時にデータスイッチに送信してはならない。このシステムは、破棄しなければならないパケットの数を可能な限り少なくすることを意図する。ただし、ここで述べる実施形態では、パケットを破棄することが必要な場合には、出力エンドではなく入力エンドで入力コントローラによって破棄を行う。さらに、データは、サービス品質（ＱＯＳ）および他の優先度値に慎重に注意を払いながら体系的な方式で破棄する。パケットの１セグメントを破棄する場合は、そのパケット全体を破棄する。したがって、送信するパケットがある各入力コントローラは送信の許可を要求する必要があり、要求プロセッサがその許可を付与する。
【００７１】
パケットＰ２００が線１３４を通じて入力コントローラに入ると、入力コントローラ１５０は、いくつかの動作を行う。図１Ｂの例示的な入力コントローラと出力コントローラの内部コンポーネントのブロック図を参照されたい。図２Ａに示すパケット２００の形態のデータは、ラインカードから入力コントローラプロセッサ１６０に入る。ＰＡＹフィールド２０８は、ＩＰパケット、イーサネット（登録商標）フレーム、あるいはシステムによって受信される他のデータオブジェクトを含む。入力コントローラは、内部で使用されるパケットを生成することによって到着するパケットＰに応答し、生成したパケットを自身のバッファ１６２、１６４、および１６６に格納する。着信パケットＰに関連付けられたデータを格納するには多数の方式がある。本実施形態で提示する方法は、Ｐに関連付けられたデータを次の３つの記憶領域に格納するものである。
１．入力セグメント２３２およびそれに関連付けられた情報を格納するのに使用するパケットバッファ１６２
２．要求バッファ１６４
３．ＫＥＹ２１０を保持するキーバッファ１６６
【００７２】
データを準備し、ＫＥＹバッファ１６６に格納する際、入力コントローラは、到着するパケットＰに関連付けられたルーティングおよび制御の情報を処理する。入力コントローラは、どの要求を要求コントローラ１２０に送信するかを決定する際にＫＥＹ２１０情報を使用する。図２Ｂに示す形のデータをＫＥＹ２１０と呼び、これはキーバッファ１６６のＫＥＹアドレスに格納される。ＢＩＴフィールド２０２は、パケットの存在を示す際には１に設定される１ビット長フィールドである。ＩＰＤフィールド２１４は、要求コントローラ１２０に対してどのような要求を行うかを決定する際に入力コントローラ１６０が使用する制御情報データを保持する。ＩＰＤフィールドは、サブフィールドとしてＱＯＳフィールド２０６を含むことができる。また、ＩＰＤフィールドは、所与のパケットがバッファにある時間と、入力バッファの使用率を示すデータも含むことができる。ＩＰＤは、出力ポートアドレスと、入力コントローラプロセッサが提出する要求を決定する際に使用する他の情報を含むことができる。ＰＢＡフィールド２１６は、パケットバッファアドレスフィールドであり、メッセージバッファ１６２のパケットＰに関連付けられたデータ２２０の開始部の物理的位置を含む。ＲＢＡフィールド２１８は、要求バッファアドレスフィールドであり、要求バッファ１６４中のパケットＰに関連付けられたデータのアドレスを示す。入力コントローラプロセッサは要求コントローラ１２０に提出する要求に関するすべての決定を行う際にこのデータを使用するので、バッファ１６６のアドレス「キーアドレス」に格納されたデータをＫＥＹと呼ぶ。実際、要求コントローラにどの要求を送信するかに関する決定は、ＩＰＤフィールドの内容に基づいて行われる。ＫＥＹを入力制御装置１５０の高速キャッシュに保持しておくと望ましい。
【００７３】
到着するインターネットプロトコル（ＩＰ）パケットおよびイーサネット（登録商標）フレームは、長さに大きなばらつきがある。セグメンテーションおよびリアセンブリ（ＳＡＲ）プロセスを使用して、より効率的に処理できるように、大きなパケットやフレームを分割してより小さなセグメントにする。パケットＰに関連付けられたデータを準備し、パケットバッファ１６２に格納する際、入力コントローラプロセッサ１６０は、まずパケット２００のＰＡＹフィールド２０８を所定の最大長さのセグメントに分割する。図１２Ａに示すような一部の実施形態では、システムで使用するセグメントの長さは１つである。図１２Ｂに示すようなノードを有する他の実施形態では、複数のセグメント長がある。複数のセグメント長があるシステムでは、図２に示すものとはわずかに異なるデータ構造が必要となる。当業者は、複数の長さに対応するようにデータ構造に明瞭な変更を加えることができる。図２Ｃに従ってフォーマットしたパケットデータは、パケットバッファ１６２の場所ＰＢＡ２１６に格納する。ＯＰＡフィールド２０４は、パケットＰのデータスイッチのターゲット出力ポートのアドレスを保持する。ＮＳフィールド２２６は、Ｐのペイロード２０８を保持するのに必要なセグメントの数２３２を示す。
【００７４】
ＫＡフィールド２２８はパケットＰのＫＥＹのアドレスを示し、ＩＰＡフィールドは入力ポートアドレスを示す。ＫＡフィールドはＩＰＡフィールドと共に、パケットＰの一意の識別子を形成する。ＰＡＹフィールドは分割してＮＳ個のセグメントにする。図で、ＰＡＹフィールドの最初のビットはスタックの最上部に格納され、第１のセグメントのすぐ後のビットは最初のビットのすぐ下に格納される。このプロセスは、到着する最後のビットがスタックの最下部に格納されるまで継続する。ペイロードはセグメント長の整数倍でない場合があるので、スタックの最下部のエントリは、セグメント長よりも短い可能性がある。
【００７５】
要求パケット２４０は、図２Ｄに示すフォーマットを有する。パケットＰに関連付けられた入力コントローラプロセッサ１６０は、要求バッファ１６４の要求バッファアドレスＲＢＡに要求パケットを格納する。ＲＢＡ２１８はＫＥＹ２１０中のフィールドでもあることに留意されたい。ＢＩＴフィールドは、そのバッファ位置にデータが存在する時には常に１に設定される単一ビットからなる。パケットＰのターゲットとなる出力ポートアドレスは、出力ポートアドレスフィールドＯＰＡ２０４に格納される。要求プロセッサデータフィールドＲＰＤ２４６は、要求プロセッサ１０６がパケットＰをデータスイッチに送信することを許可するか否かを決定する際に使用する情報である。ＲＰＤフィールドは、ＱＯＳフィールド２０６をサブフィールドとして含むことができる。ＲＰＤフィールドは、次のような他の情報を含むことができる。
・パケットＰが格納された入力ポートのバッファの使用率
・パケットＰが格納されている時間に関する情報
・パケット中のセグメント数
・マルチキャスト情報
・入力コントローラがセグメントを送信できる時間に関するスケジュール情報
・要求プロセッサが、パケットＰをデータスイッチ１３０に送信する許可を与えるか与えないかについての決定を行う際に有用な追加的な情報
【００７６】
フィールドＩＰＡ２３０およびＫＡ２２８はパケットを一意に識別し、図２Ｅに示す応答パケット２５０のフォーマットで要求プロセッサから戻される。
【００７７】
図１Ａでは、各入力コントローラＩＣ１５０から要求コントローラ１２０に複数のデータ線１２２があり、各入力コントローラからデータスイッチ１３０にも複数のデータ線１１６がある。また、要求コントローラ１２０から各入力コントローラにも複数のデータ線１２４があり、データスイッチから各出力コントローラ１１０にも複数のデータ線１１８があることにも注目されたい。データスイッチの入力ポート１１６のうち１つのみが所与の出力ポート１１８に対するパケットを持つ実施形態では、データスイッチＤＳ１３０は単純なクロスバーでよく、図１Ａの制御システム１００は、スイッチをスケーラブルな方式で制御することができる。
【００７８】
次のパケット送信時間に送信を行うための要求
要求時間Ｔ0、Ｔ1、．．．、Ｔmaxに、入力コントローラ１５０は、将来のパケット送信時間Ｔmsgにスイッチ１３０にデータを送信する要求を行うことができる。時間Ｔn+1に送信される要求は、まだ要求が行われていない最近到着したパケットと、時間Ｔ0、Ｔ1，．．．、Ｔnに送信した要求に対して要求コントローラから受信した受諾および拒否とに基づく。データスイッチにパケットを送信する許可を求める各入力コントローラＩＣnは、時間Ｔ0に始まる期間内に最大でＲmax個の要求を提出する。この要求に対する応答に基づいて、ＩＣnは、時間Ｔ1に開始する期間内に最大Ｒmax個の追加的な要求を提出する。このプロセスは、可能なすべての要求が行われるか、要求周期Ｔmaxが完了するまで、入力コントローラによって繰り返される。時間Ｔmsgに、入力コントローラは、要求プロセッサによって受け付けられたパケットをデータスイッチに送信し始める。それらのパケットをデータスイッチに送信すると、新しい要求周期が時間Ｔ0＋Ｔmsg、Ｔ1＋Ｔmsg、．．．Ｔmax＋Ｔmsgに開始する。
【００７９】
この説明では、ｎ番目の送信周期は、（ｎ＋１）番目の要求周期の第１回目と同じ時間に開始する。他の実施形態では、ｎ番目のパケット送信周期は、（ｎ＋１）番目の要求周期の第１回目より前に開始しても、後に開始してもよい。
【００８０】
時間Ｔ0に、データスイッチ１３０を通じて出力コントローラプロセッサ１７０に送信する許可を待っている１つまたは複数のパケットＰをバッファに有する入力コントローラ１５０がいくつかある。そのような入力コントローラプロセッサ１６０はそれぞれ、データスイッチを通じた送信を要求するのに最も望ましいと思われるパケットを選択する。この決定は、ＫＥＹ中のＩＰＤ値２１４に基づいて行う。時間Ｔ0に入力コントローラプロセッサが送信する要求パケットの数は、最大値Ｒmaxに制限される。これらの要求は、同時または逐次行うことができ、あるいは要求の群をシリアル方式で送信することもできる。Ｊ個の行が最上位レベルにある時に、要求を異なる列（あるいは発明＃１の用語では「アングル」）に挿入することにより、発明＃１、＃２、および＃３に教示されるタイプのスイッチにはＪ個を超える要求を行うことができる。複数のパケットが所与の一行に収まる場合にのみ、複数の列に同時に挿入できることを思い出されたい。要求パケットが比較的短いので、この例ではこれが実現可能である。あるいは、発明＃４に教示されるタイプの集線装置には要求を同時に挿入することができる。別の選択肢は、２番目のパケットを最初のパケットのすぐ後に続けて、パケットを順次単一の列（アングル）に挿入するものである。これは、これらのタイプのＭＬＭＬ相互接続ネットワークでも可能である。さらに別の実施形態では、スイッチＲＳ、および可能性としてはスイッチＡＳとＤＳが、ラインカードより多くの数の入力ポートを含む。また、事例によっては、要求スイッチの１行当たりの出力列の数は、データスイッチ中の１行当たりの出力ポートの数より多いことが望ましい。さらに、これらのスイッチが本明細書に組み込む特許に開示されるタイプである場合は、スイッチは、各自の最上位レベルにラインカードより多くの行を容易に含むことができる。こうした技術の１つを使用して、Ｔ0からＴ0＋ｄ1（ｄ1は正の値）までの期間に要求スイッチにパケットを挿入する。要求プロセッサは、時間Ｔ0からＴ0＋ｄ2（ｄ2はｄ1より大きい）までに受け取るすべての要求を検討する。次いで、それらの要求に対する応答を入力コントローラに返す。その応答に基づいて、入力コントローラは、時間Ｔ1（Ｔ1はＴ0＋ｄ2より大きい時間）に次の要求の回を送信することができる。要求プロセッサは、応答として受諾または拒否を送信することができる。Ｔ0〜Ｔ0＋ｄ1の期間に送信される要求の中には、時間Ｔ0＋ｄ2までに要求プロセッサに到着しないものがある可能性がある。要求プロセッサは、そうした要求には応答しない。無応答の原因は要求スイッチ内の輻輳なので、このように応答しないことにより入力コントローラに情報が与えられる。それらの要求は、Ｔmsgより前の別の要求送信時間Ｔn、またはＴmsgより後の別の時間に提出することができる。図６Ａおよび６Ｂを参照してタイミングをより詳細に説明する。
【００８１】
要求プロセッサは、受信したすべての要求を調べる。要求のすべてまたは一部について、要求プロセッサは、要求に関連付けられたパケットを出力コントローラに送信する許可を入力コントローラに付与する。優先度がより低い要求は、データスイッチへの入力を拒否することができる。要求プロセッサは、要求パケットデータフィールドＲＰＤの情報に加えて、パケット出力バッファ１７２のステータスに関する情報を有する。要求プロセッサは、そのバッファから情報を受け取ることにより、パケット出力バッファのステータスを知ることができる。あるいは、要求プロセッサは、自身がそのバッファに入れた内容とラインカードがそのバッファを空にできる速さを知ることにより、このステータスを追跡することもできる。一実施形態では、各出力コントローラに１つの要求プロセッサを関連付ける。他の実施形態では、複数の出力ポートに複数の要求プロセッサを関連付けることができる。あるいは別の実施形態では、１つの集積回路に複数の要求プロセッサを配置し、さらに他の実施形態では、１つまたは数個の集積回路に完全な要求コントローラ１２０を配置して、スペースを節減し、コストと処理力を集積することが望ましい。別の実施形態では、制御システムとデータスイッチ全体を単一のチップに配置することができる。
【００８２】
要求プロセッサによる決定は、次を含むいくつかの要素に基づくことができる。
・パケット出力バッファのステータス
・入力コントローラによって設定される単一値の優先度フィールド
・データスイッチから出力コントローラまでの帯域幅
・応答スイッチＡＳからの帯域幅
・要求パケットの要求プロセッサデータフィールドＲＰＤ２４６の情報
【００８３】
要求プロセッサは、データスイッチを通じて送信するデータに関して適正な決定を行うために必要な情報を有する。その結果、要求プロセッサは、データスイッチおよび出力コントローラ、ラインカード、そしてダウンストリームの接続に通じる出力線１２８へのデータの流れを調整することができる。重要な点として、トラフィックは、入力コントローラを出ると輻輳を生じさせずにデータスイッチファブリックを通じて流れる。破棄する必要があるデータがある場合、それは優先度が低いデータであり、入力コントローラで破棄される。スイッチファブリックに入って輻輳を生じさせ、他のトラフィックの流れを害することがないので有利である。
【００８４】
パケットは、システム１００に入るのと同じ順序でシステム１００を出ることが望ましく、順序を外れるデータがないことが望ましい。データスイッチにデータパケットを送信する時には、新しいデータが送信される前にすべてのデータをそのスイッチから出すようにする。このような方式で、セグメントは常に出力コントローラに順番に到着する。これは、次を含むいくつかの方式で実現することができる。
１．要求プロセッサの動作を十分に控えめにして、すべてのデータが固定された時間量でデータスイッチを通過するようにする。
２．要求プロセッサは、すべてのデータがデータスイッチを通過したことを通知する信号を待ってから、さらなるデータがデータスイッチに入るのを許可することができる。
３．セグメントが、リアセンブリプロセスで使用されるセグメント番号を示すタグフィールドを含む。
４．データスイッチを、入力コントローラを出力コントローラに直接接続するクロスバースイッチにする。あるいは、
５．発明３に開示される階段型のＭＬＭＬ相互接続タイプのデータスイッチは、クロスバーよりも使用するゲートが少なく、適切に制御するとパケットがスイッチを出る際に順序を外れることがないので、有利に使用することができる。
【００８５】
上述のケース（１）および（２）では、所与の出力ポートを宛先とする挿入されるパケットが固定数のＮ個以下である所与のサイズのスイッチを使用することにより、パケットがそのスイッチにとどまることが可能な時間Ｔの上限を予測することができる。したがって、要求プロセッサは、時間単位Ｔに１つの出力ポートにつきＮ個を超える要求を許可しないことにより、損失するパケットがないことを保証することができる。
【００８６】
図１Ａに示す実施形態では、データスイッチから出力コントローラに複数の線がある。一実施形態では、要求プロセッサは、パケットに所与の線を割り当てて、そのパケットのすべてのセグメントがその同一の線で出力コントローラに入るようにすることができる。この場合、要求プロセッサからの応答は、パケットセグメントヘッダ中のＯＰＡフィールドを修正するために使用する追加的情報を含んでいる。また、要求プロセッサは、入力コントローラが所与のパケットのすべてのセグメントを中断せずに送信する許可を与えることができる。これには次のような利点がある。
・データパケットのすべてのセグメントについて単一の要求を生成し、送信するので、入力コントローラの仕事量が減る。
・入力コントローラが１回の動作で複数のセグメントをスケジュールし、それを完了することが可能になる。
・要求プロセッサが処理する要求が少なくなるので、より多くの時間をかけて分析を完了し、応答パケットを生成することができる。
【００８７】
特定の出力コントローラの入力ポートを割り当てるには、データパケットのヘッダで追加的なアドレスビットを使用することが必要となる。追加的なアドレスビットを処理する利便な方式の１つは、データスイッチに追加的な入力ポートと追加的な出力ポートを提供するものである。追加的な出力ポートを使用してパケット出力バッファの正しいビンにデータを入れ、追加的な入力ポートを使用してデータスイッチに通じる追加的な入力線に対処することができる。あるいは、追加的なアドレスビットは、パケットがデータスイッチを出た後に分解することができる。
【００８８】
入力コントローラおよび出力コントローラとシステムの残りの部分を接続する複数の経路を利用する実施形態の場合は、３つのスイッチ、ＲＳ１０４、ＡＳ１０８、およびＤＳ１３０はすべて、同じアドレスに複数のパケットを伝達できることに留意されたい。３つの場所すべてで、この条件に対応する能力を持つスイッチを使用しなければならない。帯域幅が増加するという明白な利点に加えて、この実施形態では要求プロセッサは各々の決定をより大きなデータセットに基づいて行うので、要求プロセッサがよりインテリジェントな決定を行うことが可能になる。第２の実施形態では、要求プロセッサは有利に、バッファが比較的一杯になった１つの入力コントローラＩＣnから単一の出力コントローラＯＣmに複数の緊急のパケットを送信することができ、一方で、トラフィックの緊急性がより低い他の入力コントローラからの要求を拒絶することができる。
【００８９】
図１Ｂ、１Ｃおよび６Ａも参照すると、システム１００の動作では、イベントは所与の時間間隔で発生する。時間Ｔ0に、いくつかの入力コントローラプロセッサ１６０が、データスイッチ１３０を通じて出力コントローラプロセッサ１７０に送信できる状態の１つまたは複数のパケットＰをバッファに有する。データスイッチへの送信がまだスケジュールされていないパケットを持つ各入力コントローラプロセッサは、データスイッチを通じて宛先の出力ポートに送信する許可を要求する１つまたは複数のパケットを選択する。所与の時間に要求を承認するこの決定は、一般には、ＫＥＹ中のＩＰＤ値２１４に基づいて行う。時間Ｔ0に、そのようなデータパケットを１つまたは複数含む各入力コントローラプロセッサ１６０は、要求コントローラ１２０に要求パケットを送信して、データパケットをデータスイッチに送信する許可を求める。要求は、要求パケットのＩＰＤフィールドに基づいて受諾または拒否される。ＩＰＤフィールドは、「優先度値」からなるか、あるいは含むことができる。この優先度値が単一の数である場合、要求プロセッサの唯一の仕事はその数を比較することである。この優先度値は、パケットのＱＯＳ数の関数である。ただし、パケットのＱＯＳ数が時間的に固定されているのに対して、優先度値は、入力ポートのバッファにメッセージがある時間等のいくつかの要素に基づいて時間的に変化する可能性がある。選択されたデータパケットに関連付けられた要求パケット２４０を要求コントローラ１２０に送信する。これらの要求はそれぞれ、同じ時間に要求スイッチ１０４に到着する。要求スイッチは、パケットのＯＰＡフィールド２０４を使用して、パケット２４０を、そのパケットのターゲット出力ポートに関連付けられた要求プロセッサ１０６にルーティングする。要求プロセッサＲＰ１０６は、応答スイッチ１０８を通じて個々の入力コントローラに返す応答パケット２５０をランク付けし、生成する。
【００９０】
一般的な場合は、いくつかの要求が同じ要求プロセッサ１０６を宛先とすることができる。要求スイッチ１０４が単一のターゲット要求プロセッサ１０６に複数のパケットを伝達できることが必要である。参照により組み込まれる特許に開示されるＭＬＭＬネットワークは、この要件を満たすことができる。ＭＬＭＬネットワークはセルフルーティングを行い、ノンブロッキングである事と併せてこの特性を考慮すると、ＭＬＭＬネットワークがこの応用例で使用するスイッチの明白な選択肢となる。要求パケット２４０が要求スイッチを通じて搬送される時に、ＯＰＡフィールドを除去する。すなわち、パケットはこのフィールドがない状態で要求プロセッサに到着する。出力フィールドは、パケットの場所によって示唆されるのでこの時点では必要でない。各要求プロセッサは、受信する各要求のＲＰＤフィールド２４６のデータを調べ、所定の時間にデータスイッチ１３０に送信することを許可する１つまたは複数のパケットを選択する。要求パケット２４０は、その要求を送信する入力コントローラの入力ポートアドレス２３０を含んでいる。要求プロセッサは次いで、各要求に対して応答パケット２５０を生成し、それを入力プロセッサに送り返す。このようにして、入力コントローラは、承認された各要求について応答を受信する。入力コントローラは常に、受信する応答を受け入れる。換言すると、要求を承認する場合は対応するデータパケットをデータスイッチに送信し、承認しない場合はデータパケットを送信しない。要求プロセッサから入力コントローラに送信される応答パケット２５０は、図２Ｅに示すフォーマットを使用する。要求を承認しない場合、要求プロセッサは、入力コントローラに否定の応答を送信する。この情報は、所望の出力ポートのビジーなステータスと、入力コントローラが後に行う要求が成功する可能性を推定するのに使用することができる情報を含むことができる。この情報は、送信された他の要求の数、それらの要求の優先度、および最近の出力ポートのビジー度も含むことができる。この情報は、要求を再提出するための提案される時間も含むことができる。
【００９１】
時間Ｔ1に、入力プロセッサＩＣnがＴ0の回に受諾も拒否もされなかったパケットをバッファに有し、さらに、ＩＣnが、Ｔ0の回に受諾されたパケットに加えて、時間Ｔmsgに追加的なデータパケットを送信できると想定する。そして時間Ｔ1に、ＩＣnは、時間Ｔmsgにデータスイッチを通じて追加的なパケットを送信する要求を行う。ここでも、要求プロセッサ１０６は、受信したすべての要求の中から送信を許可するパケットを選ぶ。
【００９２】
要求周期中に、入力コントローラプロセッサ１６０は、ＫＥＹバッファのＩＰＤビットを使用して各自の決定を行い、要求プロセッサ１０６はＲＰＤビットを使用して選択を行う。これを行う方式については下記でより詳しく説明する。
【００９３】
時間Ｔ0、Ｔ1、Ｔ3，．．．、Ｔmaxの要求周期が完了すると、受諾された各パケットをデータスイッチに送信する。図２Ｃを参照すると、入力コントローラが選択された（winning）パケットの最初のセグメントをデータスイッチに送信する時に、最上位のペイロードセグメント２３２（下付き文字が最も小さいセグメント）をペイロードセグメントのスタックから除去する。非ペイロードフィールド２０２、２０４、２２６、２２８、および２３０をコピーし、取り除いたペイロードセグメント２３２の前に配置して、図２Ｆに示すフォーマットを持つパケット２６０を形成する。入力コントローラプロセッサは、どのペイロードセグメントが送信され、どのセグメントが残っているかを常に把握している。これはＮＳフィールド２２６をデクリメントすることによって行うことができる。最後のセグメントを送信すると、そのパケットに関連付けられたすべてのデータを３つの入力コントローラバッファ１６２、１６４、および１６６から除去することができる。最初の要求が承認された後に２番目の要求を送信した入力コントローラプロセッサはないので、データスイッチの各入力ポートは、１つまたは零個のセグメントパケット２６０を受信する。出力ポートが処理できる以上の要求を承認した出力コントローラはないので、データスイッチの各出力ポートは、パケットを受信しないか、１つのパケットを受信する。セグメントパケットがデータスイッチ１３０を出ると、セグメントパケットは出力コントローラ１１０に送信され、そこでリアセンブルして標準フォーマットにする。リアセンブルされたパケットは、ダウンストリームの送信のためにラインカードに送信される。
【００９４】
この制御システムは、どの入力ポートまたは出力ポートも複数のデータセグメントを受信しないことを保証するので、データスイッチとして使用するのにクロスバースイッチが許容できる。したがって、この単純な実施形態は、バースト性のトラフィックがあり、サービス品質およびサービスタイプをサポートする相互接続構造で大きなクロスバーを管理する効率的な方法を実証する。クロスバーの利点は、その内部スイッチを設定してしまうとクロスバーを通じた待ち時間が実質的に零になることである。重要な点として、クロスバーの望ましくない特性は、内部ノードスイッチの数がＮ2（Ｎはポート数）として増加することである。従来技術の方法を使用すると、インターネットトラフィックの高速度で動作する大きなクロスバーにはＮ2個の設定を生成することが重要である。クロスバーの入力を行で表し、出力ポートを接続する列で表すとする。上記に開示した制御システム１２０は、セグメントパケット２６０のＯＰＡフィールド２０４を列アドレスに単純に変換し、そのアドレスをパケットがクロスバーに入る行に供給することにより、制御設定を容易に生成する。当業者は、マルチプレクサと称するこの１からＮへの変換をクロスバー入力に容易に適用することができる。データスイッチからのデータパケットが宛先とする出力コントローラ１１０に到着すると、出力コントローラプロセッサ１７０は、セグメントからのパケットのリアセンブルを開始することができる。これが可能であるのは、ＮＳフィールド２２６から受信したセグメントの数が得られ、ＫＡフィールド２２８がＩＰＡフィールド２３０と共に一意のパケット識別子を形成するためである。Ｎ個のラインカードがある場合は、Ｎ×Ｎより大きいクロスバーを構築することが望ましい場合があることに留意されたい。このようにして、複数の入力１１６と複数の出力１１８を得ることができる。この制御システムは、このタイプの最小限のサイズよりも大きいクロスバースイッチを制御する設計となっている。
【００９５】
データスイッチには複数のスイッチファブリックを使用することができるが、好ましい実施形態では、ここに組み込まれる特許に記載されるタイプのＭＬＭＬ相互接続ネットワークをデータスイッチに使用する。その理由は以下である。
・データスイッチへの入力がＮ個の場合、スイッチ中のノード数はおよそＮ・ｌｏｇ（Ｎ）になる。
・複数の入力が同じ出力ポートにパケットを送信することができ、ＭＬＭＬスイッチファブリックは内部でそのパケットをバッファリングする。
・ネットワークがセルフルーティングし、ノンブロッキングである。
・待ち時間が低い。
・所与の出力に送信されるパケットの数を制御システムによって管理すると、システムを通過するのにかかる最大時間が分かる。
【００９６】
一実施形態では、要求プロセッサ１０６は有利に、セグメントごとに個別の許可を求めずに、複数のセグメントから構成されるパケット全体を送信する許可を付与することができる。この方式には、すべてのセグメントを中断なしに受信するので、要求プロセッサの仕事量が減少し、パケットのリアセンブリが簡単になるという利点がある。実際、この方式では、入力コントローラ１５０は、ラインカード１０２からパケット全体が到着する前にセグメントの送信を開始することができる。同様に、出力コントローラ１１０は、すべてのセグメントが出力コントローラに到着する前にラインカードにパケットを送信し始めることができる。したがって、パケットの一部は、パケット全体がスイッチ入力線に入る前に、スイッチの出力線から送信される。別の方式では、パケットセグメントごとに別個の許可を要求することができる。この方式の利点の１つは、緊急のパケットが緊急でないパケットに優先（ｃｕｔ  ｔｈｒｏｕｇｈ）できることである。
【００９７】
パケット時間スロットの確保
パケット時間スロットの確保は、先の項で教示したパケットのスケジューリング方法の変形形態である管理技術である。要求時間Ｔ0、Ｔ1、．．．、Ｔmaxに、入力コントローラ１５０は、今後のパケット送信時間のリストの１つに開始するデータスイッチへのパケット送信を求める要求を行うことができる。時間Ｔn+1に送信される要求は、まだ要求を行っていない最近到着したパケットと、時間Ｔ0、Ｔ1、．．．、Ｔnに送信した要求に応答して要求プロセッサから受信した受諾または拒否とに基づく。データスイッチにパケットを送信する許可を求める各入力コントローラＩＣnは、時間Ｔ0に始まる期間中に最大でＲmax個の要求を提出する。この要求に対する応答に基づいて、ＩＣnは、時間Ｔ1に開始する期間中に最大でＲmax個の追加的な要求を提出する。このプロセスは、可能なすべての要求が行われるか、要求周期Ｔmaxが完了するまで入力コントローラによって繰り返される。要求周期Ｔ0、Ｔ1、．．．、Ｔmaxがすべて完了すると、要求を行うプロセスが時間Ｔ0＋Ｔmax、Ｔ1＋Ｔmax、．．．、Ｔmax＋Ｔmaxの要求周期に開始する。
【００９８】
データスイッチを通じたパケットの送信を要求する際、入力コントローラＩＣnは、パケットのすべてのセグメントを順次データスイッチに送信できるように、パケットＰをデータスイッチに挿入することが可能な時間のリストを送信する。パケットＰがｋ個のセグメントを有する場合、ＩＣnは、時間の連続Ｔ、Ｔ＋１、．．．、Ｔ＋ｋ−１にパケットのセグメントを挿入することができるように開始時間Ｔをリストする。要求プロセッサは、要求される時間の１つを承認するか、またはそれらの時間をすべて拒否する。先と同様に、どの要求も承認されるとデータが送信される。Ｔ0からＴ0＋ｄ1の期間にすべての時間が拒否された場合は、ＩＣnは、別の時間セットの１つにＰを送信する要求を後の時間に行うことができる。Ｐを送信するための承認された時間に達すると、ＩＣnは、データスイッチを通じてＰのセグメントの送信を開始する。
【００９９】
この方法は、要求スイッチを通じて送信する要求がより少ない点で、先の項で教示した方法に優る利点を有する。欠点は、１）要求を処理するために要求プロセッサがより複雑でなければならないことと、２）この「すべてか無か」の要求を承認できない可能性がかなり高いことである。
【０１００】
セグメント時間スロットの確保
セグメント時間スロットの確保は、前の項で教示した方法の変形である管理技術である。要求時間Ｔ0、Ｔ1、．．．、Ｔmaxに、入力コントローラ１５０は、データスイッチへのパケット送信をスケジュールする要求を行うことができる。ただし、この方法は、１つのセグメントを別のセグメントのすぐ後に続けてメッセージを送信する必要がない点でパケットの時間スロットの確保法と異なる。一実施形態では、入力コントローラは、データスイッチにパケットを送信することが可能な複数の時間を知らせる情報を要求プロセッサに提供する。各入力コントローラは、将来の時間スロットのいつにセグメントを送信することがスケジュールされているかを示す時間スロットバッファＴＳＡ１６８を保持する。図６Ａも参照すると、各ＴＳＡビットは、セグメントをデータスイッチに送信できる１つの期間６２０を表し、ＴＳＡの１番目のビットは、現在の時間以降の次の期間を表す。別の実施形態では、各入力コントローラは、データスイッチまで有する各経路１１６につき１つのＴＳＡバッファを有する。
【０１０１】
ＴＳＡバッファの内容は、優先度を含む他の情報と共に要求プロセッサに送信される。要求プロセッサは、この時間の可用性情報を使用して、入力コントローラがいつデータスイッチにパケットを送信すべきかを決定する。図３Ａおよび３Ｂは、ＴＳＡフィールドを含む要求パケットおよび応答パケットの図である。要求パケット３１０は、要求パケット２４０と同じフィールドを含み、加えて要求時間スロット可用性フィールドＲＴＳＡ３１２を含む。応答パケット３２０は、応答パケット２５０と同じフィールドを含み、加えて応答時間スロットフィールドＡＴＳＡ３２２を含む。ＡＴＳＡ３２２の各ビットは、データスイッチにパケットを送信できる１つの期間６２０を表し、ＡＴＳＡの１番目のビットは、現在の時間以降の次の期間を表す。
【０１０２】
図３Ｃは、時間スロット確保の処理の一例を示す図である。この例では１つのみのセグメントを検討する。要求プロセッサは、要求プロセッサの可用性スケジュールであるＴＳＡバッファ３３２を含む。ＲＴＳＡバッファ３３０は、入力コントローラから受け取る要求時間である。バッファの内容を時間ｔ０とｔ０’に示しており、ｔ０は現在の期間についての要求処理が開始される時間であり、時間ｔ０’は要求の処理が完了する時間である。時間ｔ０に、ＲＰｒは、２つの入力コントローラＩＣｉおよびＩＣｊから２つの要求パケット３１０を受信する。各ＲＴＳＡフィールドは、期間ｔ１〜ｔ１１を表す１ビットのサブフィールド３０２のセットを含む。値１は、個々の入力コントローラがそれら個々の期間に各自のパケットを送信できることを意味し、値０は送信できないことを意味する。ＲＴＳＡ要求３０２は、ＩＣｉが時間ｔ１、ｔ３、ｔ５、ｔ６、ｔ１０、およびｔ１１にセグメントを送信できることを示す。ＩＣｊのＲＴＳＡフィールドの内容も図に示す。時間スロット可用性バッファＴＳＡ３３２は、要求プロセッサ中に維持される。時間スロットｔ１のＴＳＡサブフィールドは０であり、その時間に出力ポートがビジーであることを示す。出力ポートは、時間ｔ２、ｔ４、ｔ６、ｔ９およびｔ１１にセグメントを受け付けられることに留意されたい。
【０１０３】
要求プロセッサは、要求中の優先度情報と併せてこれらのバッファを調べ、各要求をいつ満たすことができるかを判定する。図３Ｃでこの説明で対象とするサブフィールドを円で囲って示す。時間ｔ２は、ＴＳＡ３３２の１で示すように、データスイッチにパケットを送信することが可能な許可できる最も早い時間である。要求はともにサブフィールドｔ２が０なので、入力コントローラはいずれもこの時間を利用することができない。同様に、どの入力コントローラも時間ｔ４を使用することができない。時間ｔ６  ３３４は、出力ポートを利用できる最も早い時間であり、入力コントローラによっても使用することができる。両方の入力コントローラは時間ｔ６に送信することができ、要求プロセッサは、優先度に基づいて勝者としてＩＣｉを選択する。要求プロセッサは、時間ｔ６のサブフィールド３０６が１であり、その他のすべての位置が０である応答時間スロットフィールド３４０を生成する。このフィールドをＩＣｉに送り返す応答パケットに含める。要求プロセッサは、そのＴＳＡバッファのサブフィールドｔ６  ３３４を０に再設定し、その時間には他の要求を送信できないことを示す。要求プロセッサは、ＩＣｊからの要求を調べ、時間ｔ９が、ＩＣｊからの要求を満たすことができる最も早い時間であると判定する。要求プロセッサは、ＩＣｊに送信する応答パケット４４２を生成し、ＴＳＡバッファのビットｔ９を０に再設定する。
【０１０４】
ＩＣｉは、応答パケットを受信すると、ＡＴＳＡフィールド３４０を調べてデータスイッチにデータセグメントを送信すべき時間を判断する。この例ではそれは時間ｔ６である。受信したフィールドがすべて零の場合は、そのサブフィールドが対象とする期間中にはパケットを送信することができない。ＩＣｉはまた、（１）そのｔ６サブフィールドを０に再設定し、（２）すべてのサブフィールドを１つの位置分左シフトすることにより、自身のバッファを更新する。前者のステップは、時間ｔ６をスケジュールすることを意味し、後者のステップでは次の期間ｔ１に使用するためにバッファを更新する。同様に、各要求バッファは、時間ｔ１に受信する要求に備えるためにすべてのサブフィールドを１ビット左シフトする。
【０１０５】
この項で教示する実施形態ではセグメンテーションおよびリアセンブリ（ＳＡＲ）を有利に用いる。長いパケットが到着すると、それを多数のセグメントに分割し、その数はパケットの長さによって決まる。要求パケット３１０は、セグメント数を示すフィールドＮＳ２２６を含む。要求プロセッサは、ＴＳＡ情報と併せてこの情報を使用して個々のセグメントを送信する時間をスケジュールする。重要な点として、すべてのセグメントについて単一の要求および応答を使用する。パケットを５つのセグメントに分割すると想定する。要求プロセッサは、自身のＴＳＡバッファと併せてＡＴＳＡフィールドを調べ、セグメントを送信する５つの期間を選択する。この場合ＡＴＳＡは５つの「１」を含んでいる。５つの期間は連続している必要はない。これにより、長さと優先度が異なるパケットに時間スロットを割り振る解決法の自由度がかなり増す。到着する１つのＩＰパケットまたはイーサネット（登録商標）パケットにつき平均して１０個のセグメントがあると想定する。したがって、データスイッチを通じて送信される１０個のセグメントごとに要求を満たさなければならない。したがって、要求と応答を行う周期は、データスイッチ周期の約８倍または１０倍の長さになり、要求プロセッサがその処理を完了するためにより多くの時間量が有利に得られ、スタックされた（パラレルの）データスイッチファブリックがビット並列方式でデータセグメントを移動することが可能になる。
【０１０６】
緊急のトラフィックに対処すべき場合、一実施形態では、要求プロセッサは、緊急のトラフィックのために近い将来の特定の期間を確保する。トラフィックが、高い割合の緊急性のない大きなパケット（多くのセグメントに分割される）と、それよりも短いが緊急性のある音声パケットの少量の部分から構成されると想定する。少数の大きなパケットは、通常は出力ポートを相当の時間量にわたって占有する可能性がある。この実施形態では、時間的に近いスロットが空いていても、大きなパケットに関連する要求を直ちに送信または連続的に送信するようにスケジュールするとは限らない。有利には、緊急のトラフィックが到着した場合に備えて一定の間隔で空スロットを常に確保しておく。したがって、緊急のパケットが到着すると、同じ出力ポートを通じて複数の長いパケットが同時に送信されていても、空けておいた早い時間スロットをそのパケットに割り当てる。
【０１０７】
時間スロットの可用性情報を使用する実施形態は、制御システムの仕事量を有利に減らし、全体のスループットを高める。この方法の別の利点は、現在個々の出力ポートへの送信を求めている各入力プロセッサについての時間可用性情報を含むより多くの情報が要求プロセッサに提供されることである。したがって、要求プロセッサは、どの入力ポートがどの時間に送信できるかに関してより多くの情報に基づく決定を行い、それによりスイッチングシステム制御のスケーラブルな手段における優先度、緊急性、および現在のトラフィック状況のバランスを取ることができる。
【０１０８】
要求を過剰に行う実施形態
上述の実施形態では、入力コントローラは、要求が受け付けられればパケットを送信できることが確実な時にのみ要求を提出する。さらに、入力コントローラは、常に許可された時間にパケットまたはセグメントを送信することにより受諾を受け入れる。したがって、要求プロセッサは、出力ポートに送信される正確なトラフィック量を知ることができる。別の実施形態では、入力コントローラは、データパケットを供給できる以上の要求を提出することを許される。そのため、入力コントローラからデータスイッチにＮ本の線１１６がある場合、入力コントローラは、ＭがＮより大きい場合でも、システムを通じてＭ個のパケットを送信する要求を行うことができる。この実施形態では、１つのデータ送信周期につき複数の要求周期があってよい。入力コントローラは、要求プロセッサから複数の受諾の通知を受信すると、対応するパケットまたはセグメントを送信することにより、受け入れる最高Ｎ個の受諾を選択する。入力コントローラが受け入れるより１つまたは複数多くの受諾がある場合は、その入力コントローラは、どの受諾を受け入れ、どの受諾を受け入れないかを要求プロセッサに通知する。拒否を受け取った入力コントローラは、次の要求周期に、最初の周期で受諾されなかったパケットについて第２の要求の回を送信する。要求プロセッサはいくつかの受諾を送り返し、各要求プロセッサは、それが作用する追加的な受諾を選択することができる。このプロセスは、何回かの要求周期にわたって継続する。
【０１０９】
これらのステップが完了した時、要求プロセッサは、データスイッチに提出できる最大数を超えるパケットは許可していない。この実施形態には、要求プロセッサが決定を行うための情報をより多く持ち、したがって、要求プロセッサが適切なアルゴリズムを用いると、要求プロセッサがより多くの情報に基づいた応答を与えることができるという利点がある。欠点は、この方法にはより多くの処理が必要となる可能性があり、わずか１つのデータ搬送周期中に複数の要求周期を行わなければならない点である。
【０１１０】
システムプロセッサ
図１Ｄを参照すると、システムプロセッサ１４０は、ラインカード１０２、入力コントローラ１５０、出力コントローラ１１０、および要求プロセッサ１０６との間でデータの送受信を行うように構成されている。システムプロセッサは、運営および管理システムなどシステム外の外部デバイス１９０と通信する。システムプロセッサが使用するために、データスイッチの数個のＩ／Ｏポート１４２および１４４、および制御システムの数個のＩ／Ｏポート１４６および１４８が確保される。システムプロセッサは、入力コントローラ１５０および要求プロセッサ１０６から受信したデータを使用して、グローバル管理システムにローカルの状況を知らせ、グローバル管理システムの要求に応答することができる。入力コントローラと出力コントローラは、相互との通信手段である経路１５２によって接続される。また、接続１５２により、システムプロセッサは、接続された出力コントローラにデータスイッチを通じてパケットを送信することにより、所与の入力コントローラ１５０にパケットを送信することができる。出力コントローラは、接続された入力コントローラにパケットを転送する。同様に、接続１５２により、出力コントローラは、まず接続された入力コントローラを通じてパケットを送信することにより、システムプロセッサにパケットを送信することができる。システムプロセッサは、Ｉ／Ｏ接続１４６により制御システム１２０にパケットを送信することができる。システムプロセッサは、接続１４８により制御システムからパケットを受信する。したがって、システムプロセッサ１４０は、各要求プロセッサ１０６、入力コントローラ１５０、および出力コントローラ１１０について送信および受信の機能を備える。この通信機能の使用の一部には、入力コントローラおよび出力コントローラ、要求プロセッサからステータス情報を受信し、セットアップおよび動作上のコマンドおよびパラメータを動的にそれらに送信することが含まれる。
【０１１１】
要求スイッチとデータスイッチの一体化
図１Ｅに示す実施形態では、要求プロセッサＲＰN１０６と出力コントローラＯＣN１１０の両方の機能を行う単一のデバイスＲＰ／ＯＣN１５４がある。また、要求スイッチＲＳ１０４とデータスイッチＤＳ１３０の両方の機能を行う単一のスイッチＲＳ／ＤＳ１５６がある。ラインカード１０２は、データパケットを受け付け、本文書にすでに述べた機能を行う。入力コントローラ１５０は、パケットを解析し、分解して複数のセグメントにし、またすでに述べた他の機能を行う。そして、入力コントローラは、パケットまたはセグメントをデータスイッチに挿入する許可を要求する。
【０１１２】
第１の実施形態では、要求パケットは図２Ｄに示す形態である。この要求パケットをＲＳ／ＤＳスイッチ１５６に挿入する。一方式では、この要求パケットは、データパケットと同時にＲＳ／ＤＳスイッチに挿入する。別の方式では、特別な要求パケット挿入時間にこれらのパケットを挿入する。要求パケットは一般にデータパケットより短いので、先の項の複数パケット長に対応するスイッチの実施形態は、この目的に有利に使用することができる。
【０１１３】
第２の実施形態では、要求パケットは、図２Ｆに示すセグメントパケットでもある。入力コントローラは、ＲＳ／ＤＳスイッチを通じてパケットの最初のセグメントＳ0を送信する。Ｓ0がＲＰ／ＯＣNの要求プロセッサ部に到着すると、要求プロセッサは、パケットのセグメントの残りの送信を許可するかどうかを決定し、セグメントの残りの部分を許可する場合は、要求プロセッサはそれらのセグメントの送信をスケジュールする。この決定は、図１Ａの要求プロセッサが行うのとほぼ同じ方式で行われる。この決定に対する応答を、応答スイッチＡＳを通じて入力コントローラに送信する。一方式では、要求プロセッサは、パケットの最初のセグメントを受信した時にのみ応答を送信する。別の方式では、要求プロセッサは、各要求に対して応答を送信する。一実施形態では、応答は、要求プロセッサが同じパケットの別のセグメントを送信するまでに待機しなければならない最小限の時間間隔の長さを含む。ＲＰ／ＯＣN１５４に通じる線１６０の数は、通例、ＲＰ／ＯＣNに入る許可を与えられるセグメントの数より多い。このようにして、ＲＳ／ＤＳスイッチを出ることをスケジュールされたセグメントは、ＲＳ／ＤＳスイッチを通過して出力コントローラに入ることができ、一方、同様に要求であるセグメントもＲＰ／ＯＣNへの経路を有する。要求セグメントの数とスケジュールされるセグメント数の合計が、ＲＳ／ＤＳスイッチ１５６から出力コントローラ１５４への線１６０の数を超える場合は、超過分のパケットは、スイッチＲＳ／ＤＳ１５６の内部でバッファリングし、次の周期にターゲットＲＰ／ＯＣに入ることができる。
【０１１４】
すべての出力線がブロックされているためにパケットが直ちにスイッチを出ることができない場合に備えて、データパケットのセグメントを順序外れにしない手順がある。この手順は、ＲＳ／ＤＳが過負荷になることも防ぐ。入力コントローラＩＣPからＲＰ／ＯＣKの出力コントローラ部に搬送されるパケットセグメントＳMの場合は、次の手順に従う。パケットセグメントＳMがＲＰ／ＯＣKに入ると、ＲＰ／ＯＣKは、スイッチＡＳ１０８を通じてＩＣP１５０に肯定応答パケット（図示せず）を送信する。ＩＣPは、肯定応答パケットを受信した後にのみ次のセグメントＳM+1を送信する。応答スイッチは、ＲＳ／ＤＳスイッチを通って出力コントローラに到着したパケットセグメントにしか肯定応答パケットを送信しないので、パケットのセグメントは順序を外れることがない。代替の方式は、セグメントパケットにセグメント番号フィールドを含め、それを出力コントローラが使用してセグメントを適切にアセンブルして、ダウンストリームに送信する有効なパケットにするものである。
【０１１５】
ＲＰ／ＯＣKからＩＣPへの肯定応答は、図２Ｅに示す応答パケットの形態で送信される。このパケットのペイロードはセグメントパケットの長さに比べて短いので、このシステムは、セグメントＳMをＲＰ／ＯＣKに送信する入力コントローラが、通常は、セグメントＳM全体をスイッチＲＳ／ＤＳに挿入し終わる前に応答を受け取るように設計することができる。このようにして、応答が肯定である場合、入力ポートプロセッサは、セグメントＳMの送信のすぐ後にセグメントＳM+1の送信を有利に開始することができる。
【０１１６】
入力コントローラは、それが行う各要求に対して１つの応答しか受け取らない。したがって、１つの単位時間当たりに入力コントローラが受け取る応答の数は、同じ入力コントローラから送信される１単位時間についての要求の数を超えることはない。有利には、所与の入力コントローラに送信されるすべての応答は、そのコントローラによって以前に送信された要求に対するものなので、この手順を用いる応答スイッチは過負荷になることがない。
【０１１７】
図１Ａを参照すると、図示しない代替の実施形態では、要求スイッチ１０４および応答スイッチ１０８を単一のコンポーネントとして実装し、このコンポーネントが要求と応答の両方を処理する。この２つの機能は、要求と応答を時分割方式で交互に処理する単一のＭＬＭＬスイッチファブリックによって行われる。このスイッチは、ある時間には要求スイッチ１０４の機能を行い、次の時間に応答スイッチ１０８の機能を行う。要求スイッチ１０４を実装するのに適したＭＬＭＬスイッチファブリックは、一般には、ここで述べる組み合わせた機能に適している。要求プロセッサ１０６の機能は、図１Ｅおよび１Ｆについて述べたようなＲＰ／ＯＣプロセッサ１５４によって扱われる。この実施形態におけるシステムの動作は、論理的には、制御されるスイッチシステム１００に相当する。この実施形態は、制御システム１２０を実装するのに必要な回路の量を有利に減らす。
【０１１８】
単一スイッチの実施形態
図１Ｆに、スイッチＲＡＤＳ１５８が要求スイッチ、応答スイッチ、およびデータスイッチについてのすべてのパケットを搬送し、交換する本発明の一実施形態を示す。この実施形態では、後に図１２Ｂおよび１４で述べる複数パケット長のスイッチを使用すると有用である。この実施形態におけるシステムの動作は、論理的には、図１Ｅについて述べたデータスイッチと要求スイッチを組み合わせた実施形態に相当する。この実施形態は、制御システム１２０およびデータスイッチシステム１３０を実装するのに必要な回路の量を有利に減らす。
【０１１９】
上述の制御システムは、２つのタイプのフロー制御方式を用いることができる。第１の方式は、要求−応答方式であり、要求プロセッサ１０６またはＲＰ／ＯＣプロセッサ１５４から肯定の応答を受信した後にのみ入力コントローラ１５０からデータを送信する。この方式は、図１Ａおよび１Ｅに示すシステムでも使用することができる。これらのシステムでは、特定の要求パケットを生成し、要求プロセッサに送信し、要求プロセッサは応答を生成し、入力コントローラに送り返す。入力コントローラは常に、ＲＰ／ＯＣプロセッサから肯定の応答を受信するまで待ってから、次のセグメントまたは残りのセグメントを送信する。図１Ｅに示すシステムでは、最初のデータセグメントは要求パケットとデータセグメントの組み合わせとして扱うことができ、その要求は、次のセグメントか、残りのすべてのセグメントに関連する。
【０１２０】
第２の方式は「停止されるまで送信する」方法であり、ＲＰ／ＯＣプロセッサが停止送信または送信一時停止のパケットを入力コントローラに送り返さない限り、入力コントローラはデータセグメントを継続して送信する。セグメント自体が要求を示唆するので、別個の要求パケットは使用しない。この方法は、図１Ｅおよび１Ｆに示すシステムで使用することができる。入力コントローラは、停止または一時停止の信号を受信しなければセグメントおよびパケットの送信を継続する。そうでなく、停止信号を受信すると、入力コントローラは、ＲＰ／ＯＣプロセッサから送信再開パケットを受信するまで待機するか、または一時停止信号を受信した場合は、送信一時停止パケットに指示される数の期間だけ待機した後に送信を再開する。このようにして、トラフィックは入力から出力に即座に移動し、出力で発生が迫りつつある輻輳を直ちに調整し、出力ポートの過負荷状態を望ましく防止する。この「停止されるまで送信する」実施形態は、特にイーサネット（登録商標）スイッチに適する。
【０１２１】
高度にパラレルのコンピュータを構築すると、プロセッサが大規模な単一スイッチネットワークを介して通信することができる。当業者は、本発明の技術を使用して、コンピュータネットワークが要求スイッチ、応答スイッチ、およびデータスイッチとして機能するソフトウェアプログラムを構築することができよう。このように、本特許に記載する技術はソフトウェアで使用することができる。
【０１２２】
この単一スイッチの実施形態および他の実施形態では、可能な応答が複数ある。パケットを送信する要求を受信した際の応答には、これらに限定しないが次が含まれる。１）現在のセグメントを送信し、パケット全体を送信するまでセグメントの送信を続ける。２）現在のセグメントを送信するが、追加的なセグメントを送信する要求を後に行う。３）将来の指定されない時間に、現在のセグメントを送信する要求を再提出する。４）現在のパケットを送信する要求を将来の所定の時間に再提出する。５）現在のセグメントを破棄する。６）現在のセグメントを今送信し、将来の所定の時間に次のセグメントを送信する。当業者は、各種のシステム要件に一致する他の応答を見つけられよう。
【０１２３】
大型のＭＬＭＬスイッチを使用したマルチキャスト
マルチキャストとは、１つの入力ポートから複数の出力ポートにパケットを送信することを言う。本特許および参照により組み込む特許に開示されるスイッチの電子実施形態の多くでは、ノードにおけるロジックは非常に単純であり、多くのゲートを必要としない。利用可能なＩ／Ｏ接続の量に比べて、ロジックには最小限のチップ面積（real estate）を使用する。そのため、スイッチのサイズは、ロジックの量ではなくチップ上のピンの数によって制限される。したがって、チップ上に多数のノードを置く余地が十分にある。要求プロセッサから要求スイッチにデータを搬送する線１２２はチップ上にあるので、それらの線の帯域幅は、チップの入力ピンに通じる線１３４の帯域幅よりもはるかに大きい可能性がある。さらに、要求スイッチをその帯域幅を扱うのに十分な大きさにすることが可能である。ＭＬＭＬネットワークの最上位レベルの行の数がＮ×入力コントローラ数であるシステムでは、単一のパケットをＮ個もの出力コントローラにマルチキャストすることが可能である。Ｋ個の出力コントローラ（Ｋ≦Ｎ）へのマルチキャストは、入力コントローラからまずＫ個の要求を要求プロセッサに提出させ、提出される各要求が別個の出力ポートアドレスを有することによって実現することができる。すると、要求プロセッサは、Ｌ個の承認（Ｌ≦Ｋ）を入力コントローラに返す。入力コントローラは次いで、それぞれ同じペイロードを有するが出力ポートアドレスが異なるＬ個の別個のパケットをデータスイッチを通じて送信する。Ｎ個を超える出力をマルチキャストするには、上述の周期を十分な回数繰り返すことが必要である。このタイプのマルチキャストを実現するために、入力コントローラは、記憶されたマルチキャストアドレスセットへのアクセス権を持たなければならない。このタイプのマルチキャストを実装するのに必要な基本システムへの必要な変更は、当業者には明らかであろう。
【０１２４】
特別なマルチキャストハードウェア
図４Ａ、４Ｂ、および４Ｃに、マルチキャストをサポートするシステム１００の別の実施形態を示す。図１Ａに示す要求コントローラ１２０をマルチキャスト要求コントローラ４２０に置き換え、データスイッチ１３０をマルチキャストデータスイッチ４４０に置き替えている。ここで用いるマルチキャスト技術は、発明＃５に教示される技術に基づく。マルチキャストパケットは、共にマルチキャストセットを形成する複数の出力ポートに送信される。マルチキャストセットのメンバ数には固定された上限がある。制限がＬであり、実際のセットにＬより多いメンバがある場合は、複数のマルチキャストセットを使用する。出力ポートは、複数のマルチキャストセットのメンバとなることができる。
【０１２５】
マルチキャストＳＥＮＤ要求は、間接アドレス指定を介して実現する。論理演算装置ＬＵは対４３２および４５２になっており、１つが要求コントローラ４２０にあり、１つがデータスイッチ４４０にある。論理演算装置の各対は、一意の論理出力ポートアドレスＯＰＡ２０４を共有し、このアドレスは、どの物理的出力ポートアドレスとも異なる。この論理アドレスは、複数の物理出力アドレスを表す。対の各論理演算装置はストレージリングを含み、このストレージリングはそれぞれ、全く同じ物理出力ポートアドレスのセットと共にロードされる。ストレージリングはアドレスのリストを含み、このアドレスは実際にはアドレスのテーブルを形成し、そのテーブルは特別なアドレスによって参照される。この表形式の出力ポートアドレス方式を用いることにより、マルチキャストスイッチＲＭＣT４３０およびＤＭＣT４５０は、すべてのマルチキャスト要求を効率的に処理する。要求パケットおよびデータパケットは、各自のストレージリング４３６および４５６に従って論理演算装置４３２および４５２によって複製される。したがって、あるマルチキャストアドレスに送信される単一の要求パケットは、該当する論理演算装置４３２または４５２によって受信され、論理演算装置は、自身のストレージリングに含まれるテーブルの各項目につき１回そのパケットを複製する。複製された各パケットは、テーブルから取られた新しい出力アドレスを有し、要求プロセッサ１０６または出力コントローラ１１０に転送される。非マルチキャスト要求はマルチキャストスイッチＲＭＣT４３０には決して入らず、代わりにスイッチＲＳB４２６の下位レベルに導かれる。同様に、非マルチキャストデータパケットは決してマルチキャストデータスイッチＤＭＣT４５０に入らず、代わりにスイッチＤＳB４４４の下位レベルに導かれる。
【０１２６】
図２Ｇ、２Ｈ、２Ｉ、２Ｊ、２Ｋ、および２Ｌに、マルチキャストをサポートするための追加的パケットとフィールドの変更を示す。表２は、そのフィールドの内容の概要である。
【０１２７】
【表２】
2005513827.tif 000004
【０１２８】
マルチキャストアドレスセットのロード
ストレージリング４３６および４５６のロードは、フォーマットがパケット２００のフォーマットに基づく図２Ｇに示すマルチキャストパケット２０５を使用して実現される。システムプロセッサ１４０は、ＬＯＡＤ要求を生成する。パケットが入力コントローラＩＣ１５０に到着すると、入力コントローラプロセッサ１６０は、出力ポートアドレスＯＰＡ２０４を調べ、そのアドレスによりマルチキャストパケットが到着していることに気付く。マルチキャストロードフラグＭＬＦ２０３がオンの場合、そのパケットはマルチキャストロードであり、ロードするアドレスのセットはＰＡＹフィールド２０８にある。一実施形態では、与えられる論理出力ポートアドレスは、先に要求者に供給されている。他の実施形態では、論理出力ポートアドレスは、利用可能な論理演算装置の対についての論理出力ポートアドレスをコントローラに選択させるダミーアドレスであり、このＯＰＡは、対応するマルチキャストデータパケットを送信する際に使用するために要求者に戻される。いずれの場合も、入力コントローラプロセッサは次いでパケットエントリ２２５を生成して、マルチキャストロードバッファ４１８に格納し、ＫＥＹＳバッファ１６６にマルチキャストバッファＫＥＹエントリ２１５を作成する。バッファＫＥＹ２１５は、２ビットのマルチキャストロードカウンタＭＬＣ２１３を含み、これをオンにするとＬＯＡＤ要求を処理できる状態であることを示す。マルチキャストロードバッファアドレスＰＬＢＡ２１１は、マルチキャストロードパケットが格納されたマルチキャストロードバッファのアドレスを含む。要求周期中に、入力コントローラプロセッサは、マルチキャストロードパケットを要求コントローラ４２０に送信して論理演算装置のストレージリングをアドレスＯＰＡ２０４にロードし、ＭＬＣ２１３の１番目のビットをオフにしてそのＬＯＡＤが完了したことを示す。同様に、入力コントローラプロセッサは、同じマルチキャストローカルパケットをデータコントローラ４４０に送信するデータ周期を選択し、ＭＬＣ２１３の２番目のビットをオフにする。ＭＬＣ２１３の両ビットがオフになると、入力コントローラプロセッサは、そのロード要求における自身の役割が完了したので、その要求についてのすべての情報をＫＥＹバッファとマルチキャストロードバッファから除去することができる。マルチキャストロードパケットの処理は、要求コントローラ４２０とデータコントローラ４４０の両方で同じである。各コントローラは、出力ポートアドレスを使用して、そのＭＣTスイッチを通じて該当する論理演算装置ＬＵ４３２またはＬＵ４５２にパケットを送信する。マルチキャストローカルフラグＭＬＦ２０３がオンになっているので、各論理演算装置は、パケットペイロードＰＡＹ２０８の情報を使用して各自のストレージリング中のアドレスを更新することを求められていることに気付く。この更新法により、対応するストレージリングの対のアドレスセットが同期される。
【０１２９】
データパケットのマルチキャスト
マルチキャストパケットは、その出力ポートアドレスＯＰＡ２０４により非マルチキャストパケットと区別される。マルチキャストロードフラグＭＬＦ２０３がオンになっていないマルチキャストパケットをマルチキャスト送信パケットと呼ぶ。入力コントローラプロセッサ１６０はパケット２０５を受け取り、出力ポートアドレスとマルチキャストロードフラグからそれがマルチキャスト送信パケットであると判定すると、プロセッサは、自身のパケット入力バッファ１６２、要求バッファ１６４、およびＫＥＹバッファ１６６に適切なエントリを作成する。マルチキャストバッファＫＥＹ２１５の２つの特別なフィールドがＳＥＮＤ要求に使用される。マルチキャスト要求マスクＭＲＭ２１７は、対象のストレージリングからどのアドレスが選択されるかを常に把握する。このマスクは、最初に、リング中のすべてのアドレスを選択するように設定する（すべて「１」）。マルチキャスト送信マスクＭＳＭ２１９は、要求されるどのアドレスが要求プロセッサＲＰ１０６によって承認されたかを追跡する。このマスクは最初はすべて零に設定し、まだ承認が与えられていないことを表す。
【０１３０】
入力コントローラプロセッサが自身のＫＥＹＳバッファを調べ、要求コントローラ４２０に提出するマルチキャスト送信エントリを選択すると、バッファキーの現在のマルチキャスト要求マスクを要求パケット２４５中にコピーし、それにより得られるパケットを要求プロセッサに送信する。要求スイッチＲＳ４２４は、出力ポートアドレスを使用してマルチキャストスイッチＲＭＣTにパケットを送信し、マルチキャストスイッチＲＭＣTは、ＯＰＡ２０４で指定される論理演算装置ＬＵ４３２にパケットをルーティングする。論理演算装置はＭＬＦ２０３からそれがロード要求でないと判定し、マルチキャスト要求マスクＭＲＭ２１７を使用して、自身のストレージリングのどのアドレスをマルチキャストに使用するかを決定する。選択された各アドレスについて、論理演算装置は、要求パケット２４５を複製して、以下の変更を行う。第１に、論理出力ポートアドレスＯＰＡ２０４を選択したリンクデータの物理ポートアドレスに変える。第２に、マルチキャストフラグＭＬＦ２０３をオンにして、要求プロセッサにそれがマルチキャストパケットであることを知らせる。第３に、マルチキャスト要求マスクを、出力ポートアドレスにロードされたストレージリング中のアドレスの場所を識別するマルチキャスト応答マスクＭＡＭ２５１に変える。例えば、ストレージリングの３番目のアドレスについて作成されたパケットは、３番目のマスクビットに値１を有し、その他の位置は零となる。論理演算装置は、生成した各パケットをスイッチＲＭＣBに送信し、ＲＭＣBは物理出力ポートアドレスを使用して該当する要求プロセッサＲＰ１０６にパケットを送信する。
【０１３１】
各要求プロセッサは、各自の要求パケットのセットを調べ、どれを承認するかを決定し、各承認についてマルチキャスト応答パケット２５５を生成する。マルチキャストの承認のために、要求プロセッサはマルチキャスト応答マスクＭＡＭ２５１を含む。要求プロセッサは、生成した応答パケットを応答スイッチＡＳ１０８に送信し、応答スイッチはＩＰＡ２３０を使用して各パケットを各自の発信元の入力制御ユニットに送り返す。入力コントローラプロセッサは、応答パケットを使用してバッファＫＥＹのデータを更新する。マルチキャストＳＥＮＤ要求の場合、この更新動作には、マルチキャスト応答マスクで承認された出力ポートをマルチキャスト送信マスクに追加し、その出力ポートをマルチキャスト要求マスクから除くことが含まれる。したがって、マルチキャスト要求マスクは、まだ承認を受け取っていないアドレスを把握し、マルチキャスト送信マスクは、承認され、データコントローラ４４０に送信できる状態のアドレスを把握する。
【０１３２】
ＳＥＮＤ周期中に、承認されたマルチキャストパケットを、マルチキャスト送信マスクＭＳＭ２１９を含むマルチキャストセグメントパケット２６５としてデータコントローラに送信する。出力ポートアドレスをデータスイッチＤＳ４４２およびＭＣT４３０で使用して、パケットを指定される論理演算装置にルーティングする。論理演算装置は、マルチキャストセグメントパケットのセットを作成し、各パケットは元のパケットと全く同じであるが、マルチキャスト送信マスクについての情報に従って論理演算装置から供給される物理出力ポートアドレスを有する。次いで、修正されたマルチキャストセグメントパケットはマルチキャストスイッチＭＣBを通過し、スイッチＭＣBはパケットを適切な出力コントローラ１１０に送信する。
【０１３３】
出力コントローラプロセッサ１７０は、パケット識別子ＫＡ２２８およびＩＰＡ２３０、およびＮＳ２２６フィールドを使用することによりセグメントパケットをリアセンブルする。リアセンブルしたセグメントパケットをＬＣ１０２に送信するためにパケット出力バッファ１７２に入れ、これでＳＥＮＤ周期が完了する。非マルチキャストパケットは、マルチキャストスイッチ４４８を通らない点を除いては同様の方式で処理される。代わりに、データスイッチ４４２がパケットの物理出力ポートアドレスＯＰＡ２０４に基づいてスイッチＤＳ４４４を通じてパケットをルーティングする。
【０１３４】
マルチキャストバススイッチ
図５Ａおよび５Ｂは、オンチップバス構造を使用するマルチキャストを実装し、サポートするための代替の方法を示す図である。図５Ａは、マルチキャスト要求バススイッチ５１０で相互に接続された複数の要求プロセッサ５１６を示す図である。図５Ｂは、データパケット搬送マルチキャストバススイッチ５４０で相互に接続された複数の出力プロセッサ５４６を示す図である。
【０１３５】
マルチキャストパケットは、共にマルチキャストセットを形成する複数の出力ポートに送信される。バス５１０は、接続を特定の要求プロセッサに送信することを可能にする。マルチキャストバスはＭ×Ｎのクロスバースイッチのように機能し、ＭとＮは等しい必要はなく、リンク５１４および５４４。バス中の１つのコネクタ５１２は１つのマルチキャストセットを表す。各要求プロセッサは、零個または１つのコネクタ５１２を有するＩ／Ｏリンク５１４を形成することができる。これらのリンクはバスの使用前に確立しておく。所与の要求プロセッサ５１６は、それが属するマルチキャストセットを表すコネクタ５１２のみにリンクし、バス中の他のコネクタには接続されない。出力ポートプロセッサ５４６も同様に出力マルチキャストバス５４０の零個または１つ以上のデータ搬送コネクタ５４２にリンクされる。同じセットのメンバである出力ポートプロセッサは、そのセットを表すバス上のコネクタ５４２へのＩ／Ｏリンク５４４を有する。これらの接続リンク５１４および５４４は動的に構成することが可能である。そのため、特別なＭＣ  ＬＯＡＤメッセージで、所与のマルチキャストセットのメンバとしての出力ポートを追加し、変更し、除去する。
【０１３６】
１つの要求プロセッサが、所与のマルチキャストセットの代表として指定される（ＲＥＰプロセッサ）。入力ポートプロセッサは、そのセットのＲＥＰプロセッサ５１８だけにマルチキャスト要求を送信する。図６Ｃは、指定された期間ＭＣＲＣ６５０だけにマルチキャスト要求を行うマルチキャストタイミング方式を示す。入力コントローラ１５０は、そのバッファに１つまたは複数のマルチキャスト要求を有する場合、マルチキャスト要求周期６５０を待ってその要求をＲＥＰプロセッサに送信する。マルチキャスト要求を受信したＲＥＰプロセッサは、共有されるバスコネクタ５１２で信号を送信することにより、そのセットの他のメンバに通知する。この信号は、そのコネクタにリンクされたすべての他の要求プロセッサで受信される。ＲＥＰプロセッサが２つ以上のマルチキャスト要求を同時に受信した場合は、要求中の優先度情報を使用してどの要求をバスに置くかを決定する。
【０１３７】
ＲＥＰプロセッサは、バスに置く１つまたは複数の要求を選択すると、コネクタ５１２を使用してセットの他のメンバに問い合わせてから、選択された入力コントローラに応答パケットを送り返す。要求プロセッサは、１つまたは複数のマルチキャストセットのメンバとなることができ、２つ以上のマルチキャスト要求の通知を一度に受信する可能性がある。換言すると、複数のマルチキャストセットのメンバである要求プロセッサは、複数のマルチキャストバス接続５１４が同時にアクティブであることを検出する可能性がある。その場合は、１つまたは複数の要求を受諾することができる。各要求プロセッサは同じバスコネクタを使用して、その要求を受諾する（または拒否する）ことをＲＥＰプロセッサに通知する。この通知は、時分割方式を使用することにより、各要求プロセッサからＲＥＰプロセッサにコネクタ５１２を通じて送信される。各要求プロセッサは、受諾または拒否を伝える時に特定の時間スロットを有する。したがって、ＲＥＰプロセッサは、セットの１メンバにつき１ビットのビットシリアル方式ですべてのメンバから応答を受信する。あるいは別の実施形態では、非ＲＥＰプロセッサは、自身がビジーになることを予めＲＥＰプロセッサに通知する。
【０１３８】
次いで、ＲＥＰプロセッサは、マルチキャストセットのどのメンバが要求を受諾するかを示すマルチキャストビットマスクを構築し、値１は受託を表し、値０は拒否を表し、ビットマスク中の位置がメンバを表す。ＲＥＰプロセッサから入力コントローラへの返信は、このビットマスクを含み、応答スイッチにより要求元の入力コントローラに送信される。ＲＥＰプロセッサはまた、ビットマスクがすべて零である場合は、拒否の応答パケットを入力コントローラに送信する。拒否されたマルチキャスト要求は、後のマルチキャスト周期に再度試みることができる。あるいは別の実施形態では、各出力ポートは、自身がメンバである各マルチキャストセットについての特別なバッファ領域を保持する。規定された時間に、出力ポートは、自身のマルチキャストセットに対応する各ＲＥＰプロセッサにステータスを送信する。このプロセスはデータ送信周期中に継続する。このようにして、ＲＥＰは、どの出力ポートがマルチキャストパケットを受信できるかを予め知り、したがってすべてのメンバに要求を送信することなく直ちにマルチキャスト要求に応答することができる。
【０１３９】
マルチキャストデータ周期中に、受諾のマルチキャスト応答を有する入力コントローラは、マルチキャストビットマスクをデータパケットヘッダに挿入する。入力コントローラは次いで、出力でそのマルチキャストセットを表す出力ポートにデータパケットを送信する。出力ポートプロセッサは、要求プロセッサをマルチキャストバス５１０に接続する手段と同様に、マルチキャスト出力バス５４０に接続されることを思い出されたい。パケットヘッダを受信した出力ポートプロセッサＲＥＰは、マルチキャストビットマスクを出力バスコネクタに送信する。出力ポートプロセッサは、セット中の自身に対応する時間に０または１を探す。１が検出された場合は、その出力ポートプロセッサが出力に選択される。マルチキャストビットマスクを送信すると、ＲＥＰ出力ポートプロセッサは直ちにデータパケットを同じコネクタに置く。選択された出力ポートプロセッサは単に、ペイロードを出力接続にコピーし、マルチキャスト動作を望ましく完了する。あるいは別の実施形態では、所与のマルチキャストセットを表す単一のバスコネクタ５１２および５４２を複数のコネクタによって実装することができ、ビットマスクを送信するのにかかる時間量を望ましく低減する。別の実施形態では、バス上のすべての出力がパケットを受諾できる場合にのみマルチキャストパケットを送信し、０は受諾を表し、１は拒否を表す。すべてのプロセッサが同時に応答し、１つの「１」を受信した場合には要求は拒否される。
【０１４０】
２つ以上のマルチキャスト要求を受信した要求プロセッサは、１つまたは複数の要求を受諾することができ、これは、要求元の入力コントローラによって受信されるビットマスク中の１で表される。要求を拒否する要求プロセッサは、ビットマスク中では０で表される。入力コントローラがセットのすべてのメンバについてすべて１（１００％の承認を表す）を受け取らない場合は、後のマルチキャスト周期に再度試行することができる。その場合、要求は、セットのどのメンバが要求に応答する、または要求を無視すべきかを示すために使用されるビットマスクをヘッダ中に有する。一実施形態では、マルチキャストパケットは常に、受信されると直ちに出力プロセッサから送信される。別の実施形態では、出力ポートは、マルチキャストパケットを他のパケットと同じように扱うことができ、後の時間に送信するために出力ポートバッファに格納することができる。
【０１４１】
アップストリームのデバイスが頻繁にマルチキャストパケットを送信する場合、または２つ以上のアップストリームのソースが１つの出力ポートに多量のトラフィックを送信する場合には、過負荷状態が発生する可能性がある。データスイッチの出力ポートを出るすべてのパケットは個々の要求プロセッサによって承認されていなければならないことを思い出されたい。マルチキャスト要求の結果として、または多数の入力ソースが出力ポートに送信を行いたいため、あるいはその他の理由で、所与の要求プロセッサが多すぎる要求を受信した場合、要求プロセッサは、出力ポートを通じて送信できるだけの要求だけを受け付ける。したがって、ここに開示する制御システムを使用する時には出力ポートの過負荷は発生し得ない。
【０１４２】
図１Ｄも参照すると、データスイッチを通じたパケットの送信の許可を拒否された入力コントローラは、後に試みることができる。重要な点として、入力コントローラは、過負荷が発生しそうな時にはそのバッファ中のパケットを破棄することができる。入力コントローラは、どの出力ポートでどのパケットが受諾されないかについての十分な情報を持ち、状況を評価し、過負荷のタイプと原因を判定することができる。そして、データスイッチを通じてシステムプロセッサ１４０にパケットを送信することにより、システムプロセッサ１４０にその状況を知らせることができる。システムプロセッサは、制御システム１２０およびデータスイッチ１３０へのＩ／Ｏ接続を複数有することを思い出されたい。システムプロセッサは、１つまたは複数の入力コントローラからのパケットを一度に処理することができる。システムプロセッサ１４０は、次いで、適切なパケットを生成し、アップストリームのデバイスに送信して過負荷状態を知らせ、そのため問題をソースで解決することができる。システムプロセッサはまた、所与の入力ポートプロセッサに、バッファに有する特定のパケットと今後受信する可能性のあるパケットを無視し、破棄するように指示することもできる。重要な点として、ここに開示するスケーラブルな交換システムはその原因に関係なく過負荷の影響を受けず、したがって輻輳が生じないものと見なされる。
【０１４３】
マルチキャストパケットは、特別な時間に、または他のデータと同時にデータスイッチを通じて送信することができる。一実施形態では、特別なビットが、そのパケットをバスのすべてのメンバにマルチキャストする、または何らかのビットマスクに含まれるメンバにマルチキャストすることをＲＥＰ出力ポートプロセッサに知らせる。後者の場合は、特別なセットアップ周期により、スイッチをそのビットマスクで選択されるメンバに設定する。別の実施形態では、バスのすべてのメンバがパケットを受信する場合にのみ、特別なマルチキャストハードウェアを通じてパケットを送信する。マルチキャストセットの数は、出力ポートの数より多い可能性がある。他の実施形態では、複数のマルチキャストセットがあり、各出力ポートは１つだけのマルチキャストセットのメンバである。次の３つのマルチキャスト方式を提示した。
１．入力コントローラに到着する単一のパケットにより複数の要求が要求スイッチに送信され、複数のパケットがデータスイッチに送信される、特別なハードウェアを必要としないタイプのマルチキャスト。
２．発明＃５に教示される回転するＦＩＦＯ構造を使用したタイプのマルチキャスト。
３．マルチキャストバスを必要とするタイプのマルチキャスト。
【０１４４】
マルチキャストを使用する所与のシステムは、これらの方式の１つ、２つ、または３つすべてを採用することができる。
【０１４５】
システムタイミング
図１Ａを参照すると、到着したパケットは、ラインカード１０２の入力線１２６を通じてシステム１００に入る。ラインカードはパケットヘッダおよび他のフィールドを分析して、その送信先と、優先度およびサービス品質を判定する。この情報はパケットと共に経路１３４を通じて、接続された入力コントローラ１５０に送信される。入力コントローラはこの情報を使用して制御システム１２０に送信する要求パケット２４０を生成する。この制御システムでは、要求スイッチ１０４は、所与の出力ポートに送信されるすべてのトラフィックを制御する要求プロセッサ１０６に要求パケットを送信する。一般的な場合は、１つの要求プロセッサ１０６が１つの出力ポート１１０を表し、すべてのトラフィックを制御して、パケットが対応する要求プロセッサによって承認されずにシステム出力ポート１２８に送信されることがないようにする。一部の実施形態では、図１Ｅおよび１Ｆに示すように要求プロセッサ１０６を物理的に出力コントローラ１１０に接続する。要求プロセッサはパケットを受信し、同じ出力ポートに送信したいデータパケットを有する他の入力コントローラからの要求を受信することができる。要求プロセッサは、各パケット中の優先度の情報に基づいて要求をランク付けし、他の要求を拒否するのと同時に１つまたは複数の要求を受け付けることができる。要求プロセッサは、直ちに１つまたは複数の応答パケット２５０を生成し、それを応答スイッチ１０８を通じて送信して、受諾された「勝者」パケットと拒否された「ｌｏｏｓｉｎｇ」パケットを入力コントローラに通知する。受諾されたデータパケットを持つ入力コントローラは、データスイッチ１３０にデータパケットを送信し、データスイッチ１３０はそれを出力コントローラ１１０に送信する。出力コントローラは、内部的に使用するフィールドがあればそれを除去し、経路１３２を通じてパケットをラインカードに送信する。ラインカードは、パケットを、物理的なダウンストリーム送信１２８に適したフォーマットに変換する。１つまたは複数の要求を拒否する要求プロセッサは追加的に、入力コントローラに拒否を通知する応答パケットを送信して、そのパケットが後の周期で受諾される可能性を推定するために使用する情報を提供する。
【０１４６】
図６Ａも参照すると、要求および応答の処理のタイミングは、データスイッチを通じたデータパケットの送信と重なっており、パケットの送信は、入力コントローラと連動してラインカードによって行われるパケットの受信と解析とも重なっている。到着したパケットＫ６０２はまずラインカードによって処理され、ラインカードはヘッダと他の関連するパケットフィールド６０６を調べて、パケットの出力ポートアドレス２０４とＱＯＳ情報を判定する。時間ＴAに新しいパケットがラインカードに到着する。時間ＴRの時点で、ラインカードは十分なパケット情報を受信し、処理しており、入力コントローラは自身の要求周期を開始することができる。入力コントローラは要求パケット２４０を生成する。期間ＴRQ６１０は、システムが要求を生成し、処理し、選択された入力コントローラで受信および応答するために使用する時間である。期間ＴDC６２０は、データスイッチ１３０が入力ポート１１６から出力ポート１１８にパケットを送信するために使用する時間量である。一実施形態では、ＴDCはＴRQよりも長い期間である。
【０１４７】
図６Ａに示す例では、パケットＫ６０２が時間ＴAにラインカードに受信される。入力コントローラは、期間ＴRQに、制御システムによって処理される要求パケット２４０を生成する。この期間に、先に到着したパケットＪ６２０がデータスイッチを通じて移動する。また期間ＴRQには、別のパケットＬ６２２がラインカードに到着する。重要な点として、要求プロセッサはその出力ポートに対する要求をすべて認識し、輻輳を生じさせうる以上の要求は受け付けないので、データスイッチは過負荷になる、あるいは輻輳することがない。入力コントローラには、各自のバッファ中のパケットに次に行う動作を決定するのに必要かつ十分な情報が与えられる。破棄しなければならないパケットは、各自のヘッダ中のすべての関連情報に基づいて公平に選択される。要求スイッチ１０４、応答スイッチ１０８、およびデータスイッチ１３０は、発明＃１、＃２、および＃３に教示されるタイプのスケーラブルなワームホール型ＭＬＭＬ相互接続である。したがって、要求はデータパケットの交換と重なる形で処理され、遅延を生じずにシステムを通じてデータパケットを移動できる方式で、スケーラブルでグローバルなシステムの制御が有利に行われる。
【０１４８】
図６Ｂは、複数の要求副周期もサポートする実施形態の時間的に重複した処理のステップをより詳細に示すタイミング図である。以下のリストは、同図の番号を付した線６３０を参照する。
１．入力コントローラＩＣ１５０が、要求パケット２４０を構築するのに十分な情報をラインカードから受け取っている。入力コントローラは、入力バッファに他のパケットを有する可能性があり、最高優先度の要求としてその１つまたは複数を選択することができる。時間ＴRに最初の要求パケットを要求スイッチに送信することが要求周期の開始の印となる。時間ＴRの後に、１回目の要求がなかったパケットが少なくとももう１つバッファにあり、１回目の要求の１回または複数が拒否された場合、入力コントローラは、２回目（または３回目）の要求副周期で使用する優先度が２番目に高い要求パケット（図示せず）を直ちに作成する。
２．要求スイッチ１０４が、時間ＴRに要求パケットの最初のビットを受信し、要求のＯＰＡフィールド２０４で指定される対象要求プロセッサにパケットを送信する。  
３．この例では、要求プロセッサが、時間Ｔ3から連続的に到着する要求を３つまで受信する。
４．３番目の要求が時間Ｔ4に到着すると、要求プロセッサは、パケット中の優先度情報に基づいて要求をランク付けし、受諾する１つまたは複数の要求を選択することができる。各要求パケットは、要求元の入力コントローラのアドレスを含んでいる。要求元の入力コントローラのアドレスを応答パケットの宛先アドレスとして使用する。
５．応答スイッチ１０８がＩＰＡアドレスを使用して、要求を行っている入力コントローラに受諾パケットを送信する。
６．入力コントローラが時間Ｔ6に受諾の通知を受け取り、受諾パケットに関連付けられたデータパケットを次のデータ周期６４０の開始時にデータスイッチに送信する。入力コントローラからのデータパケットは、時間ＴDにデータスイッチに入る。
７．要求プロセッサが拒否の応答パケット２５０を生成し、拒否された要求を行った入力コントローラに応答スイッチを通じて送信する。
８．最初の拒否パケットを生成すると、それを応答スイッチ１０８に送信し、その後に他の拒否パケットを送信する。最後の拒否パケットは、時間Ｔ8に入力コントローラによって受信される。これにより要求周期、あるいは複数の要求副周期を用いる実施形態では最初の副周期が完了した印となる。
９．要求周期１６０は時間ＴRに開始し、継続時間ＴRQの後に時間Ｔ8に終了する。要求副周期をサポートする実施形態では、要求周期６１０を最初の副周期と見なす。２番目の副周期６１２は、すべての入力コントローラに承認された要求と拒否された要求が通知された後に時間Ｔ8に開始する。Ｔ3からＴ8の間の時間に、最初の周期で要求がなかったパケットを持つ入力コントローラは、２番目の副周期のために要求パケットを構築する。その要求はＴ8に送信する。複数の副周期を使用する場合、データパケットは最後の副周期（図示せず）の完了時にデータスイッチに送信する。
【０１４９】
この時間的に重複した処理法により、制御システムは有利にデータスイッチと速度を合わせることができる。この時間的に重複した処理法により、制御システムは有利にデータスイッチと速度を合わせることができる。
【０１５０】
図６Ｃは、特別なマルチキャスト処理周期をサポートする制御システムの一実施形態のタイミング図である。この実施形態では、非マルチキャスト（通常の）要求周期ＲＣ６１０にはマルチキャスト要求を許可しない。マルチキャストのパケットを有する入力コントローラは、マルチキャスト要求周期ＭＣＲＣ６５０まで待ってその要求を送信する。そのため、マルチキャスト要求が通常の要求と競合せず、マルチキャストのすべてのターゲットポートが利用可能である可能性を高めるので有利である。通常の周期とマルチキャスト周期の比およびそれらのタイミングは、システムプロセッサ１４０によって動的に制御される。
【０１５１】
図６Ｄは、図３Ａ、３Ｂ、および３Ｃと共に述べた時間スロット確保のスケジューリングをサポートする制御システムの一実施形態のタイミング図である。この実施形態は、データパケットは概して相当数のセグメントに再分割され、パケットのすべてのセグメントに対して１つのみの要求が行われるという事実を活用する。１つの時間スロット要求周期ＴＳＲＣ６６０に、単一の時間スロット確保要求パケット３１０を送信し、応答パケット３２０を受信する。応答を受信すると、より短い時間スロットデータ周期ＴＳＤＣ６６２に、１ＴＳＤＣ周期につき１セグメントの割合で複数のセグメントを送信する。一例では、平均的なデータパケットを１０セグメントに分割するとする。これは、データスイッチに送信する１０個のセグメントごとに、システムは１つのみのＴＳＲＣ周期を行えばよいことを意味する。したがって、要求周期６６０はデータ周期６６２の１０倍の長さとなり、制御システム１２０はなおすべての着信トラフィックを処理することができる。実際には、入力ポートが短いパケットのバーストを受信する状況に対処するには平均以下の比を使用しなければならない。
【０１５２】
電力節減方式
ＭＬＭＬスイッチファブリックには、パケットビットをシリアルに送信するコンポーネントが２つある。それは、１）制御セルと、２）スイッチファブリックの各行にあるＦＩＦＯバッファである。図８Ａおよび１３Ａを参照すると、クロック信号１３００によりデータビットがバケツリレー方式でこれらのコンポーネントを通じて移動していく。ＭＬＭＬスイッチファブリックの好ましい実施形態では、シミュレーションにより、所与の時間にこれらのコンポーネントを通過するパケットを有するのはこれらのコンポーネントのわずか１０〜２０％であり、残りは空であることが分かる。しかし、パケットがない（すべて零）の時でもシフトレジスタが電力を消費する。電力節減の実施形態では、パケットが存在しない時にはクロック信号を適切にオフにする。
【０１５３】
第１の電力節減方式では、所与のセルがそのセルに入ったパケットがないと判断すると直ちにそのセルを駆動させるクロックをオフにする。この判断にかかる時間は、所与の制御セルについてわずか１クロックサイクルである。次のパケット到着時間１３０２にクロックを再度オンにし、プロセスを繰り返す。第２の電力節減方式では、自身の行のＦＩＦＯにパケットを送信するセルが、そのＦＩＦＯにパケットが入るか入らないかを判定する。したがって、そのセルがＦＩＦＯのクロックをオンまたはオフにする。
【０１５４】
コントロール配列８１０全体のセルのいずれもパケットを受信しない場合は、同じレベルのコントロール配列の右のセルまたはＦＩＦＯにはパケットが入ることはできない。第３の電力節減方式では、その右にパケットを送信するセルがコントロール配列中にない時には、そのコントロール配列の右のすべての同じレベルのセルとＦＩＦＯについてクロックをオフにする。
【０１５５】
構成可能な出力接続
出力ポートにおけるトラフィック速度は時間の経過と共に変化する可能性があり、一部の出力ポートは他のポートよりも高い速度を経験することがある。図７は、発明＃２および＃３で教示されるタイプのＭＬＭＬデータスイッチの最下位レベルの図であり、物理的な出力ポート１１８への構成可能な接続を作成する仕組みを示している。スイッチの最下位レベルのノード７１０は、スイッチチップの出力ポート１１８への設定可能な接続７０２を有する。行アドレス０のノードＡは、リンク７０２により１つの出力ポート１１８に接続し、行１  ７０４のノードＢ、Ｃ、およびＤは同じ出力アドレスを有する。３つの列で、ノードＢ、Ｃ、およびＤが３つの異なる物理出力ポート７０６に接続する。同様に、出力アドレス５および６はそれぞれ２つの出力ポートに接続する。したがって、出力アドレス１、５、および６は、データスイッチ出力における帯域幅容量がより高い。
【０１５６】
トランキング
トランキングとは、共通のダウンストリーム接続に接続された複数の出力ポートを集約することを言う。データスイッチでは、１つのトランクに接続された出力ポートをそのデータスイッチ内で単一のアドレス、またはアドレスのブロックとして扱う。異なるトランクが異なる数の出力ポート接続を有することができる。図８は、トランキングをサポートするように変更した、発明＃２および＃３で教示されるタイプのＭＬＭＬデータスイッチの下位レベルの図である。システムプロセッサ１４０から送信される特別なメッセージでノードを構成して、ヘッダアドレスビットを読み取るか、または無視するようにする。「ｘ」で表すノード８０２は、パケットヘッダビット（アドレスビット）を無視し、パケットを次のレベルにルーティングする。同じトランクに到達する同じレベルのノードを点線の枠８０４内に示す。図で、出力アドレス０、１、２および３は、同じトランクＴＲ０８０６に接続する。これらのアドレスのいずれかに送信されるデータパケットは、ＴＲ０の４つの出力ポート１１８のいずれかでデータスイッチを出る。換言すると、出力アドレスが０、１、２または３のデータパケットは、トランクＴＲ０の４つのポートのいずれかでスイッチを出る。統計的には、パケットのアドレス０、１、２または３に関係なく、トランクＴＲ０８０６のどの出力ポート１１８も使用される可能性が等しい。この特性により、複数の出力接続１１８から出て行くトラフィックが有利に均等になる。同様に、アドレス６または７に送信されるパケットは、トランクＴＲ６８０８から送信される。
【０１５７】
高速のＩ／Ｏおよびより多くのポートのための並列化
セグメンテーションおよびリアセンブリ（ＳＡＲ）を利用する場合、スイッチを通じて送信されるデータパケットは、完全なパケットではなくセグメントを含んでいる。図６Ｄに示すタイミング方式を用いる図１Ａに示すシステムの一実施形態では、要求プロセッサは、パケットのすべてのセグメントを各自のターゲット出力コントローラに送信する許可を一度に与えることができる。入力コントローラは、完全なパケットにいくつセグメントがあるかを示す単一の要求を作成する。要求プロセッサは要求をランク付けする際にこの情報を使用する。複数セグメントの要求が承認されている場合、要求プロセッサは、すべてのセグメントが送信される時まで後続の要求は一切許可しない。入力コントローラ、要求スイッチ、要求プロセッサ、および応答スイッチの仕事量は望ましく低減する。そのような実施形態では、要求プロセッサが比較的アイドルである間データスイッチはビジーな状態が続く。この実施形態では、要求周期６６０は、データ（セグメント）スイッチ周期６６２よりも長い継続時間とすることができ、制御システム１２０の設計とタイミングの制約を有利に緩和する。
【０１５８】
別の実施形態では、要求プロセッサの容量を上げずに、データスイッチを通じた速度を上げる。これは、図９のスイッチおよび制御システム９００で示すように、複数のデータスイッチに向かうデータを管理する単一のコントローラ１２０を備えることによって実現することができる。この設計の一実施形態では、所与の期間に、各入力コントローラ９９０は、データスイッチのスタック９３０の各データスイッチにパケットを送信することができる。別の実施形態では、入力コントローラは、同一のパケットの異なるセグメントを各データスイッチに送信することを決定するか、または異なるパケットのセグメントをデータスイッチに送信することを決定することができる。他の実施形態では、所与の時間ステップに、同じパケットの異なるセグメントを異なるデータスイッチに送信する。さらに別の実施形態では、データスイッチのスタック全体に１つのセグメントをビット並列方式で送信して、セグメントがデータスイッチをワームホール式に通過するのにかかる時間量を、スタック中のスイッチチップの数に比例する量だけ減らす。
【０１５９】
図９で、この設計では、単一の要求スイッチと単一の応答スイッチを備える要求コントローラ１２０によって管理される複数のデータスイッチが可能になる。他の設計では、要求コントローラは、複数の要求スイッチ１０４と複数の応答スイッチ１０８を含む。さらに他の設計では、複数の要求スイッチおよび複数の応答スイッチと複数のデータスイッチがある。最後の場合は、データスイッチの数は要求制御装置の数と同じでよく、要求プロセッサの数はデータスイッチの数より多くとも少なくともよい。
【０１６０】
一般的な場合は、マルチキャスト要求だけを処理するＰ個の要求プロセッサ、マルチキャストパケットだけを処理するＱ個のデータスイッチ、直接の要求を処理するＲ個の要求プロセッサ、および直接アドレス指定されたデータ交換を処理するＳ個のデータスイッチがある。
【０１６１】
要求スイッチの複数のコピーを有利に用いる一方式は、各要求スイッチにＪ本の線でデータを受信させるものであり、Ｊ個の入力コントローラプロセッサそれぞれから１つの線が到着する。この実施形態では、入力プロセッサの役割の１つは、要求スイッチへの負荷を均等にすることである。要求プロセッサは、データスイッチにデータを送信する際に同様の方式を使用する。
【０１６２】
図１Ｄを参照すると、システムプロセッサ１４０は、ラインカード、入力プロセッサ、および要求プロセッサとデータの送受信を行い、運営および管理システムなどシステム外の外部デバイスと通信するように構成される。データスイッチＩ／Ｏポート１４２および１４４、制御システムＩ／Ｏポート１４６および１４８は、システムプロセッサが使用するために確保される。システムプロセッサは、入力プロセッサおよび要求プロセッサから受信したデータを使用して、グローバル管理システムにローカルの状況を知らせ、グローバル管理システムの要求に応答することができる。要求プロセッサが各自の決定を行うために使用するアルゴリズムおよび方法は、テーブル検索の手順か、または単一値の優先度フィールドによる単純な要求のランク付けに基づくことができる。システムプロセッサは、システム内およびシステム外からの情報に基づいて、たとえば要求プロセッサの検索テーブルを一部変更することにより、要求プロセッサが使用するアルゴリズムを変えることができる。ＩＣ  ＷＲＩＴＥメッセージ（図示せず）が経路１４２でデータスイッチを通じて出力コントローラ１１０に送信され、コントローラ１１０は、経路１５２を通じて、関連付けられた入力コントローラ１５０にメッセージを送信する。同様に、ＩＣ  ＲＥＡＤメッセージが入力コントローラに送信され、入力コントローラは、データスイッチを通じてシステムプロセッサのポートアドレス１４４に返信を送信することによって応答する。ＲＰ  ＷＲＩＴＥメッセージ（図示せず）を使用して、要求スイッチ１０４を用いて経路１４６で要求プロセッサに情報を送信する。ＲＰ  ＲＥＡＤメッセージを同様に使用して要求プロセッサに問い合わせ、要求プロセッサはその返信を応答スイッチ１０８を通じて経路１４８でシステムプロセッサに送信する。
【０１６３】
図１０Ａに、さらに別の程度の並列性を実現したシステム１０００を示す。制御システムとデータスイッチを含むスイッチ全体１００または９００の複数のコピーを、より大きなシステムを構築するためのモジュールとして使用する。それぞれのコピーをレイヤ１００４と呼び、レイヤはいくつあってもよい。一実施形態では、スイッチおよび制御システム１００のＫ個のコピーを使用して大規模なシステムを構築する。レイヤは、大規模な光学システムであってよく、レイヤは基板上のシステムを構成しても、あるいは１つのラックまたは多数のラック中のシステムを構成してもよい。以下の説明では、レイヤが基板上のシステムから構成されるものと考えると好都合である。このようにして、小さなシステムが１つのみの基板（１つのレイヤ）から構成できるのに対し、より大きなシステムは複数の基板からなる。
【０１６４】
図１Ａに示す最も単純なレイヤの場合のレイヤｍのコンポーネントのリストを以下に記す。
・１つのデータスイッチＤＳm
・１つの要求スイッチＲＳm
・１つの要求プロセッサＲＣm
・１つの応答スイッチＡＳm
・Ｊ個の要求プロセッサＲＰ0、m、ＲＰ1、m、．．．、ＲＰJ-1、m
・Ｊ個の入力コントローラＩＣ0、m、ＩＣ1、m、．．．、ＩＣJ-1、m
・Ｊ個の出力コントローラＯＣ0、m、ＯＣ1、m、．．．、ＯＣJ-1、m
【０１６５】
Ｋ個のレイヤそれぞれに上記のコンポーネントを有するシステムは、以下の「パーツ数」を有する：Ｋ個のデータスイッチ、Ｋ個の要求スイッチ、Ｋ個の応答スイッチ、Ｊ・Ｋ個の入力コントローラ、Ｊ・Ｋ個の出力コントローラ、およびＪ・Ｋ個の要求プロセッサ。
【０１６６】
一実施形態では、Ｊ個のラインカードＬＣ0、ＬＣ1，．．．，ＬＣJ-1があり、各ラインカード１００２はすべてのレイヤにデータを送信する。この実施形態では、ラインカードＬＣnは、入力コントローラＩＣn、0、ＩＣn、1、．．．、ＩＣn、K-1に供給する。外部の入力線１０２０が波長分割多重（ＷＤＭ）方式の光データをＫ個のチャネルで搬送する例では、データを逆多重化し、光／電子（Ｏ／Ｅ）変換装置で電子信号に変換する。各ラインカードはＫ個の電子信号を受信する。別の実施形態では、各ラインカードに通じる電子線１０２２がＫ本ある。データ入力線１２６の一部は、他の線よりも重い負荷がかかる。負荷を分散するために、所与の入力線からラインカードに入るＫ個の信号は、有利に異なるレイヤに置くことができる。着信するデータを逆多重化するのに加えて、ラインカード１００２は出て行くデータを再度多重化することができる。これには、着信データには光から電子への変換が、出て行くデータには電子から光への変換が必要になる場合がある。
【０１６７】
すべての要求プロセッサＲＰN、0、ＲＰＮN、1、．．．、ＲＰN、K-1は、ラインカードＬＣNにパケットを送信する要求を受信する。図１０Ａに示す実施形態では、レイヤ間で通信を行わない。所与のラインカードに対応するＫ個の入力コントローラとＫ個の出力コントローラがある。したがって、各ラインカードは、Ｋ個の入力コントローラにデータを送信し、Ｋ個の出力コントローラからデータを受け取る。各ラインカードは、所与の出力コントローラに対応する指定された入力ポートのセットを有する。この設計により、レイヤが１つしかない先の場合と同じ容易でセグメントのリアセンブリを行うことができる。
【０１６８】
図１０Ｂの実施形態では、Ｊ・Ｋ個の入力コントローラもあるが、出力コントローラはＪ個のみである。各ラインカード１０１２は、各レイヤ１０１６に１つあるＫ個の入力コントローラ１０２０に供給する。図１０Ａと異なり、各出力コントローラ１０１４には１つのみのラインカードが関連付けられる。この構成により、出力バッファすべてのプーリングが得られる。実施形態１０１０では、要求に対して最適な応答を与えるために、単一のラインカードへのデータフローを制御するすべての要求プロセッサ間に情報の共有があると有利である。このようにして、レイヤ間の通信リンク１０３０を使用して、要求プロセッサＲＰN、0、ＲＰN、1、．．．、ＲＰN、K-1は、ラインカードＬＣN中のバッファのステータスに関する情報を共有する。各データスイッチの出力１０１８と出力コントローラ１０１４の間に集線装置１０４０を配置すると有利である可能性がある。発明＃４は、要求プロセッサによって保証されるデータ転送速度を与えられると、集線装置が入ってくるすべてのデータを各自の出力接続に搬送できる特性を有する高データ転送速度の集線装置について記載する。これらのＭＬＭＬ集線装置がこの応用例に最適の選択肢である。集線装置の目的は、その期間中に他のレイヤからのデータが軽量である場合に、所与のレイヤのデータスイッチが過度の量のデータを集線装置に伝達し続けることを可能にすることである。したがって、分散されない負荷とバースト性のトラフィックがある時に、Ｋ個のレイヤからなる統合システムは、Ｋ個の接続されないレイヤに比べて高い帯域幅を実現することができる。このデータフローの増大は、要求プロセッサが各集線装置に入るすべてのトラフィックについての知識を有することによって可能になる。このようなシステムの不都合点は、パケットセグメントをリアセンブルするのにより多くのバッファリングと処理が必要となり、Ｊ個の通信リンク１０３０があることである。
【０１６９】
「ツイステッドキューブ（ｔｗｉｓｔｅｄ  ｃｕｂｅ）」の実施形態
データスイッチとスイッチ管理システムからなる基本的なシステムを図１Ａに示す。入力ポートと出力ポートの数を増やさずにこのシステムの帯域幅を高めるための変形を図９、１０Ａ、および１０Ｂに示す。この項の目的は、全帯域幅を増すのと同時に入力ポートと出力ポートの数を増加する方式を説明することである。この技術は、縦に配置された２つの「回転したキューブ」の概念に基づき、各キューブはＭＬＭＬスイッチファブリックのスタックである。ＭＬＭＬネットワークおよび集線装置をコンポーネントとして含むシステムが発明＃４に記載される。ツイステッドキューブシステムの小規模なバージョンの実例を図１１Ａに示す。システム１１００は、電子システムでも光学システムであってもよいが、ここでは電子システムを説明するのが利便である。このようなシステムの基本的な構築ブロックは、各レベルにＮ個の行とＬ個の列を有する発明＃２および＃３に教示されるタイプのＭＬＭＬスイッチファブリックである。最下位レベルにはＮ個の行があり、１行につきＬ個のノードがある。最低レベルの各行にはＭ個の出力ポートがあり、ＭはＬを超えない。このようなスイッチネットワークは、Ｎ個の入力ポートとＮ・Ｍ個の出力ポートを有する。Ｎ個のスイッチ１１０２からなるスタックをキューブと呼び、それに続くＮ個のスイッチ１１０４のスタックは別のキューブであり、最初のキューブに対して９０度ねじられている。
【０１７０】
２つのキューブを図１１Ａの平面的な配置で示し、Ｎ＝４である。２Ｎ個のこのようなスイッチングブロックと２Ｎ個の集線装置ブロックからなるシステムは、Ｎ2個の入力ポートとＮ2個の出力アドレスを有する。ここで例示する図１１Ａの小規模なネットワークは、８つのスイッチファブリック１１０２および１１０４を有し、それぞれ４つの入力と４つの出力アドレスを有する。したがって、システム１１００全体は、１６の入力と１６の出力を有するネットワークを形成する。パケットは、スイッチ１１０２の入力ポートに入り、スイッチ１１０２はターゲット出力の最初の２ビットを固定する。パケットは次いでＭＬＭＬ集線装置１１１０に入り、集線装置１１１０は、第２のスタックの１つのスイッチの４つの入力ポートに一致するように、第１のスタックの１２個の出力ポートからのトラフィックを均等にする。所与の集線装置に入るパケットはすべて、同じＮ／２個の最上位アドレスビットを有し、この例では２ビットである。集線装置の目的は、比較的負荷が軽いより多くの数の線を、比較的負荷が重いより少ない数の線に供給することである。集線装置は、バースト性のトラフィックが第１のスイッチスタックから第２のスタックに移動することを可能にするバッファとしても機能する。集線装置の第３の目的は、第２のデータスイッチセットの入力に入るトラフィックを均等にすることである。第２のスイッチセット１１０４と最後のネットワーク出力ポートの間にも集線装置の別のセット１１１２が配置される。
【０１７１】
図１１Ａに示すタイプの大きなスイッチを図１Ａに示すシステム１００のスイッチモジュールに使用する場合、要求コントローラ１２０を実装するには２つの方法がある。第１の方法は、スイッチＲＳ１０４およびＡＳ１０８の代わりに図１１Ａのツイステッドキューブのネットワークアーキテクチャを使用するものである。この実施形態では、Ｎ2個のシステム出力ポートに対応するＮ2個の要求プロセッサがある。要求プロセッサは、第２の集線装置のセット１１１２より前にあっても後にあってもよい。図１１Ｂに、要求コントローラ１１５２中の要求スイッチモジュール１１５４および応答スイッチモジュール１１５８と、データスイッチ１１６０にツイステッドキューブ型のスイッチファブリックを使用する大規模なシステム１１５０を示す。このシステムは、ここに教示する相互接続制御システムおよびスイッチシステムのスケーラビリティを実証する。Ｎがキューブの１つのスイッチコンポーネント１１０２および１１０４のＩ／Ｏポートの数であるとすると、ツイステッドキューブシステム１１００には合計でＮ2個のＩ／Ｏポートがある。
【０１７２】
例示的な例の図１Ａ、１１Ａ、および１１Ｂを参照すると、単一のチップが、４つの独立した６４ポートスイッチ実施形態を含む。各スイッチ実施形態は、６４本の入力ピンと１９２（３・６３）本の出力ピンを使用し、１つのスイッチにつき合計で２５６本のピンがある。したがって、４スイッチのチップは、１０２４（４・２５６）本のＩ／Ｏピンと、タイミング、制御信号、および電力の接続を有する。キューブは、１６チップからなるスタックで形成され、全体で６４（４・１６）個の独立したＭＬＭＬスイッチを含む。１６個のチップからなるこのスタック（１つのキューブ）は同様のキューブに接続され、したがって１つのツイステッドキューブセットにつき３２個のチップが必要となる。３２個のチップはすべて単一のプリント回路基板に搭載することが好ましい。結果得られるモジュールは６４・６４個、すなわち４０９６個のＩ／Ｏポートを有する。スイッチシステム１１５０は、これらのモジュールのうち３つ１１５４、１１５８、１１６０を使用し、４０９６個の利用可能ポートを有する。これらのＩ／Ｏポートをラインカードで多重化して、より少ない数の高速送信線をサポートすることができる。各電子Ｉ／Ｏ接続１３２および１３４が３００メガビット／秒の控えめな速度で動作すると想定する。したがって、それぞれ毎秒２．４ギガビットで動作する５１２  ＯＣ−４８光ファイバーを１：８の比で多重化して、ツイステッドキューブシステム１１５０の４０９６個の電子接続とのインタフェースをとる。この控えめに設計されたスイッチシステムは、毎秒１．２３テラビットの横断帯域幅を提供する。スイッチモジュールのシミュレーションから、モジュールは、バースト性のトラフィックを処理しながら連続的な８０〜９０％の速度で容易に動作することが分かり、これは、従来技術の大型のパケット交換システムを大幅に上回る数字である。当業者は、速度がより高く、容量がより大きいより大型のシステムを容易に設計し、構成することができよう。
【０１７３】
スイッチファブリックにツイステッドキューブを用いるシステムを管理する第２の方法では、スイッチ１１０２の最初の列と集線装置１１１０の最初の列の間に要求プロセッサ１１８２をもう１レベル追加する。この実施形態の制御システム１１８０を図１１Ｃに示す。データスイッチ間の各集線装置に対応して１つの要求プロセッサＭＰ１１８２がある。これらの中間の要求プロセッサをＭＰ0、ＭＰ1、．．．、ＭＰJ-1と表す。集線装置の役割の１つはバッファとして機能することである。中間プロセッサのストラテジは、集線装置のバッファ１１００がオーバーフローにならないようにすることである。複数の入力コントローラが、中間の集線装置１１１０の１つを通じて流れる多数の要求を送信する場合、その集線装置は過負荷になる可能性があり、第２の要求プロセッサのセットに要求のすべてが到着しない可能性がある。要求の一部を選択的に破棄することが中間プロセッサ１１８２の目的である。中間要求プロセッサ１１８２は、出力コントローラのバッファのステータスについての知識を持たずに決定を行うことができる。中間要求プロセッサは、中間要求プロセッサから中間集線装置１１１０までの帯域幅、中間集線装置から第２の要求スイッチ１１０４までの帯域幅、第２のスイッチ１１０４中の帯域幅、および第２のスイッチから要求プロセッサ１１８６までの帯域幅の総帯域幅を考慮するだけでよい。中間プロセッサは、要求の優先度を検討し、要求プロセッサに送信していたら要求プロセッサによって破棄されると思われる要求を破棄する。
【０１７４】
単一パケット長のルーティング
図１２Ａは、参照により本明細書に組み込む特許に開示されるＭＬＭＬ相互接続で使用するタイプのノードの図である。ノード１２２０は、パケットのための２つの水平方向の経路１２２４および１２２６と、２つの垂直方向の経路１２０２および１２０を有する。このノードは、２つの制御セルＲおよびＳ１２２２と、どちらかの制御セルがどちらかの下方への経路１２０２または１２０４を使用することを許可する２×２のクロスバースイッチ１２１８を含む。発明＃２および＃３に教示されるように、上から１２０２でセルＲに到着するパケットは常に経路１２２６で直ちに右にルーティングされ、上から１２０４でセルＳに到着するパケットは常に経路１２２４で直ちに右にルーティングされる。左からセルＲに到着するパケットは、そのパケットを宛先に近づける経路で下にルーティングされ、または、その経路が利用可能でない場合はパケットは常に経路１２２６で右にルーティングされる。左からセルＳに到着するパケットはそのパケットを宛先に近づける経路で下にルーティングされ、あるいはその経路が利用可能でない場合は常に経路１２２４で右にルーティングされる。下への経路が利用可能であり、セルＲおよびＳがそれぞれその経路を使用したいパケットを有する場合は、１つのみのセルがその下方の経路を使用することを許可される。この例では、セルＲが優先度がより高いセルを有し、下方の経路を使用する第１の選択権を得、それによりセルＳはブロックされ、セルＳのパケットを経路１２２４で右に送信する。セルＲおよびＳはそれぞれ、左からの入力を１つのみと、右への出力を１つのみ有する。右への経路が使用中の場合セルは上からのパケットを受け付けられず、制御信号（図示しないが経路１２０２および１２０４と並行に送られる）がより高いレベルのセルへと上に送信されることに留意されたい。このようにして、常に、競合を生じさせることが予想される上からのパケットがセルに入らないようにする。重要な点として、左からあるノードに到着するパケットは常に、利用可能な右への出口経路と、しばしば、その宛先に向かう下方への利用可能な出口を有し、ノードにおけるバッファリングの必要性をなくし、ＭＬＭＬスイッチファブリックを通じたトラフィックのワームホール伝送をサポートするので望ましい。
【０１７５】
図１３Ａは、図１２Ａに示すノード１２２０のタイミング図である。このノードにはクロック１３００とロジック設定信号１３０２が供給される。グローバルクロック１３００を使用して、１クロック期間当り１ビットの割合で、セル中の内部シフトレジスタ（図示せず）を通じてパケットビットを段階的に移動する。各ノードは、到着するパケットを送信する方向を決定するロジック要素１２０６を含む。ノードに到着するパケットのヘッダビットと、より低いレベルのセルからの制御信号情報をロジック設定時間１３０２にロジック１２０６によって調べる。ロジックは次いで、（１）パケットのルーティング先、すなわち下または右と、（２）クロスバー１２１８の設定方式を決定し、（３）その設定を、そのパケットがノードを通過する時間にわたって内部レジスタに格納する。次のロジック設定時間１３０２にこのプロセスを繰り返す。
【０１７６】
本発明の主旨である制御システムを備えるデータスイッチは、短いセグメントと同時に長いパケットを処理するのに非常に適している。長さが異なる複数のパケットが、この機能をサポートするデータスイッチの一実施形態を通じて効率的にワームホール式に進行する。次いで、複数のパケット長をサポートするが、必ずしもセグメンテーションとリアセンブリを使用しない実施形態について述べる。この実施形態では、データスイッチは、複数の内部経路のセットを有し、各セットは異なる長さのパケットを処理する。データスイッチ中の各ノードは、そのノードを通過する各セットからの経路を少なくとも１つ有する。
【０１７７】
図１２Ｂに、複数のパケット長、この例では４つの長さを望ましくサポートするセルＰおよびＱを有するノード１２４０を示す。ノード１２４０の各セル１２４２および１２４４は、４つの水平方向の経路を有し、これらの経路は４つの異なる長さのパケットの伝送経路である。経路１２５８は、最も長いパケットまたは半永久的な接続のための経路であり、経路１２５６は長いパケットの経路であり、経路１２５４は中程度の長さのパケットの経路であり、経路１２５２は最も短いパケットに使用される。図１３Ｂは、ノード１２４０のタイミング図である。４つの経路それぞれに別個のロジック設定のタイミング信号がある。ロジック設定信号１３１０は、経路１２５２の長さが短いパケットに関連し、信号１３１２は経路１２５４の中程度の長さのパケットに関連し、信号１３１４は経路１２５６の長いパケットに関連し、信号１３１６は経路１２５８の半永久的な接続に関連する。長さが長いパケットのための接続は、長さがより短いパケットよりも前にノード中で設定することが重要である。これにより、より長いパケットが、下方への経路１２０２および１２０４を使用し、スイッチをより早く出る可能性が高まり、全体の効率が高まる。したがって、半永久的な信号１３１６を最初に発行する。長いパケット用の信号１３１４は、半永久的な信号１３１６の１クロック期間後に発行される。同様に、中程度の長さのパケットの信号１３１２をさらに１クロック期間後に発行し、その１クロック期間後に短いパケットの信号１３１０を発行する。
【０１７８】
セルＰ１２４２は、それぞれ経路１２５２、１２５４、１２５６、および１２５８で左から一度に入るパケットを零個、１つ、２つ、３つ、または４つ有することができる。左から到着するすべてのパケットのうち、零個または１つのパケットを下方に送信することができる。また同時に、１２０２で上から入るパケットを零または１つ有することができるが、それは、そのパケットの右への出口経路が利用可能な場合のみである。一例として、セルＰが左から入るパケットを３つ有し、それが短いパケット、中程度のパケット、および長いパケットであるとする。中程度のパケットを下方に送信すると想定する（短いパケットと長いパケットは右に送信する）。その結果、右への中程度および半永久的なパケットの経路が不使用となる。したがって、セルＰは、経路１２０２で上から中程度または半永久的なのパケットを受け付けることができるが、上からの短いパケットまたは長いパケットは受け付けることができない。同様に、同じノードのセルＱ１２４４は、左から到着するパケットを０〜４個、および経路１２０４で上から到着するパケットを零または１個有することができる。別の例では、セルＱ１２４４は左からの４つのパケットを受信し、クロスバー１２１８の設定に応じて、経路１２５２の長さが短いパケットを経路１２０２または１２０４で下方にルーティングする。その結果、右への短い長さ用の出口経路が利用可能になる。したがって、セルＱは、短いパケット（だけ）を経路１２０４で下方に送信することができる。このパケットは、直ちに経路１２５４で右にルーティングされる。上のセルが下に送信したい短いパケットを持たない場合は、下方への送信を許可されるパケットはない。したがって、経路１２５８を使用するスイッチの部分が入力から出力への長期間の接続を形成し、経路１２５６を使用する別の部分がＳＯＮＥＴフレームなどの長いパケットを搬送し、経路１２５４は長いＩＰパケットおよびイーサネット（登録商標）フレームを搬送し、経路１２５２はセグメントまたは個々のＡＴＭセルを搬送する。垂直方向の経路１２０２および１２０４は、任意の長さのパケットを搬送する。
【０１７９】
複数長パケットのスイッチ
図１４は、長さが異なるパケットの同時の伝送をサポートするスイッチの一部の回路図と、ＭＬＭＬ相互接続ファブリックの２つの列および２つのレベルのノードを示す接続である。これらのノードは図１２Ｂに示すタイプであり、複数のパケット長をサポートするが、図を簡略にするために図には短いパケット１４３４と長いパケット１４３６の２つの長さのみを示す。ノード１４３０は、それぞれそのセルを通過する２つの水平方向の経路１４３４および１４３６を有するセルＣおよびＤを含む。セルＣ１４３２は、上からの単一の入力１２０２を有し、下への経路１２０２および１２０４の両方をセルＤと共有する。垂直方向の経路１２０２および１２０４は、どちらかの長さの伝送を搬送することができる。左から２つのパケットがセルＬに到着している。長いパケットＬＰ１が最初に到着し、経路１２０２で下にルーティングされる。短いパケットＳＰ１が後に到着し、同じく経路１２０２を使用したいが、右にルーティングされる。セルＬは、セルＣおよびＤを含むノードから長いパケットを搬送することを許可するが、右への短い経路１４３４が使用中なので短いパケットを許可することができない。セルＣは長いパケットＬＰ２を受信し、そのパケットはセルＬに移動したい。セルＬはその移動を許可し、セルＣは経路１２０４でＬＰ２をセルＬに送信し、セルＬは常にそのパケットを右にルーティングする。セルＤは短いパケットＳＰ２を受信し、このパケットも経路１２０４でセルＬに移動することを要求するが、経路１２０４は長いパケットＬＰ２によって使用中なのでＤは送信することができない。さらに、ＣからＬへの長いパケットがない場合でも、セルＬが上からの短いパケットの送信をブロックしているので、セルＤはその短いパケットを下に送信することができない。
【０１８０】
チップの境界
図１Ａ、１Ｄ、１Ｅ、および１Ｆに示すようなシステムでは、複数のシステムコンポーネントを単一のチップに配置することが可能である。例えば、図１Ｅに示すシステムでは、入力コントローラ（ＩＣ）と出力コントローラ、および出力コントローラと組み合わせた要求プロセッサ（ＲＰ／ＯＣ）は、ラインカードから受信するメッセージのタイプに固有のロジックを有することができる。そのため、ＡＴＭメッセージを受信するラインカードの入力コントローラは、インターネットプロトコルメッセージまたはイーサネット（登録商標）フレームを受信する入力コントローラとは異なる可能性がある。ＩＣおよびＲＰ／ＯＣは、すべてのシステムプロトコルに共通のバッファとロジックも含む。
【０１８１】
一実施形態では、次のコンポーネントのすべてまたは複数を単一のチップに配置することができる。
・要求およびデータスイッチ（ＲＳ／ＤＳ）
・応答スイッチ（ＡＳ）
・すべてのプロトコルに共通のＩＣ中のロジック
・ＩＣバッファの一部
・すべてのプロトコルに共通のＯＣ／ＲＰのロジック
・ＯＣ／ＲＰバッファの一部
【０１８２】
所与のスイッチを単独でチップ上に配置しても、いくつかのチップに配置しても、多数の光学コンポーネントからなってもよい。スイッチへの入力ポートは、チップ上の物理ピンとすることができ、光／電子インタフェースにあってよく、単に単一のチップ上のモジュール間の相互接続であってもよい。
【０１８３】
高データ転送速度の実施形態
多くの点で、本特許に記載するシステムの物理的実施は、ピンによって制限される。先の項で述べたチップ上のシステムを考えられたい。これを具体的な５１２×５１２の例によって例示する。この例では、低力の差分ロジックを使用し、１つのデータ信号につきチップ上とチップ外の２本のピンが必要とされる。したがって、チップ上とチップ外でデータを搬送するために合計２０４８本のピンが必要となる。また、チップから入力コントローラのチップ外部分に信号を送信するには５１２本のピンが必要である。この特定の例では差分ロジックのピンの対が毎秒６２５メガビット（Ｍｂｐｓ）を搬送可能であると想定する。すると、各差分ピンの対のチャネルが６２５Ｍｂｐｓで動作する５１２×５１２スイッチとして１チップシステムを使用することができる。別の実施形態では、各チャネルが毎秒１．２５ギガビット（Ｇｂｐｓ）の２５６×２５６スイッチとして単一のチップを使用することができる。他の選択肢には、２．５Ｇｂｐｓの１２５×１２５スイッチ、５Ｇｂｐｓの６４×６４スイッチ、あるいは１０Ｇｂｐｓの３２×３２スイッチが含まれる。データ転送速度がより高く、チャネル数がより少ないチップを使用する場合は、所与のメッセージの複数のセグメントを所与の時間にチップに供給することができる。あるいは、同じ入力ポートに到着する異なるメッセージのセグメントをチップに供給することができる。いずれの場合も、内部のデータスイッチはなお５１２×５１２スイッチであり、異なる内部Ｉ／Ｏを使用して各種のセグメントを正しい順序に保つ。別の選択肢には、特許＃２のマスタースレーブのオプションが含まれる。さらに別のオプションでは、内部の単一線のデータ搬送線の代わりに、よりバス幅が広いバスを使用することができる。このバス設計は容易な汎化であり、この変更は当業者によって行うことができる。より高いデータ転送速度を有するシステムを構築するために、図１０Ａおよび１０Ｂに示すようなシステムを用いることができる。例えば、２つのスイッチングシステムチップを用いて、各線が１０Ｇｂｐｓを搬送する６４×６４ポートシステムを構築することができ、各線が１０Ｇｂｐｓを搬送する１２８×１２８ポートシステムは４つのスイッチングシステムチップで構築することができる。同様に、１０Ｇｐｓの２５６×２５６システムには８個のチップが必要であり、１０Ｇｂｐｓの５１２×５１２システムには１６個のチップが必要である。
【０１８４】
１チップ当りのピンがより少ない他の技術は、１つのピンの対当り最高２．５Ｇｂｐｓの速度で動作することができる。Ｉ／Ｏがチップロジックより高速に動作する場合は、チップ上の内部スイッチは、チップ上のピンの対より多くの行を最上位レベルに有することができる。
【０１８５】
自動的なシステム修復
上述のシステムで述べた実施形態の１つを使用し、そのシステムを構築するのにＮ個のシステムチップが必要であるとする。図１０Ａおよび１０Ｂに示すように、各システムチップをすべてのラインカードに接続する。自動的な修復機能を備えるシステムでは、Ｎ＋１個のチップを用いる。それらのＮ個のチップをＣ0、Ｃ1、．．．、ＣNと表す。通常モードではチップＣ0、Ｃ1、．．．、ＣN-1を用いる。所与のメッセージをセグメントに分割する。所与のメッセージの各セグメントに識別子ラベルを与える。セグメントを集める時に、識別子ラベルを比較する。セグメントの１つが欠ける場合、あるいは正しくない識別子ラベルを有する場合は、チップの１つに欠陥があることになり、その欠陥のあるチップを特定することができる。自動修復システムでは、各チップＣKへのデータ経路をＣK+1に切り替えることができる。このようにして、不適正な識別子ラベルによりチップＪに欠陥があることが判明した場合は、そのチップを自動的に切り替えてシステムから除外することができる。
【０１８６】
システム入力−出力
多数の低データ転送速度の信号を受信し、少数のより高いデータ転送速度の信号を生成するチップと、少数の高データ転送速度の信号を受信し、多数の高データ転送速度の信号を生成するチップが市販されている。これらのチップは、集線装置ではなく、単にデータを拡大または縮小する多重化（ｍｕｘ）チップである。６２５Ｍｂｐｓの差分ロジックを使用するシステムを１０Ｇｂｐｓの光学システムに接続するには、１６：１および１：１６のチップが市販されている。１６個の入力信号には、各入力／出力ポートに関連付けられた３２本の差分ロジックピンが必要であり、このシステムには１つの１６：１ｍｕｘ、１つの１：１６ｍｕｘ、１つの市販のラインカード、および１つのＩＣ−ＲＰ／ＰＣチップが必要である。別の設計では、３２：１の集線ＭＵＸを使用せずに、１６個の信号により１６個のレーザを供給して１０ＧｂｐｓのＷＤＭ信号を生成する。したがって、今日の技術を使用すると、最大１０Ｇｂｐｓで動作する５１２×５１２の完全に制御されたスマートなパケット交換システムには、１６個のカスタムスイッチシステムチップと５１２  Ｉ／Ｏチップセットが必要となる。そのようなシステムは、毎秒５．１２テラビット（Ｔｂｐｓ）の横断帯域幅を有する。
【０１８７】
別の現在利用可能な技術では、１ポートにつき２．５Ｇｂｐｓで動作する１２８×１２８スイッチチップシステムの構築が可能である。１２８個の入力ポートには、２５６本の入力ピンと２５６本の出力ピンが必要となる。４つのそのようなチップを使用して１０Ｇｂｐｓのパケット交換システムを形成することができる。
【０１８８】
前述の本発明の開示と説明は説明を目的とし、例示的なものであり、本発明の精神から逸脱せずに頭記の特許請求の範囲内で変形形態を作成することができる。
【図面の簡単な説明】
【０１８９】
【図１Ａ】入力プロセッサおよびバッファ、出力プロセッサおよびバッファ、トラフィックの管理および制御に使用されるネットワーク相互接続スイッチ、およびターゲット出力ポートへのデータをスイッチングするのに使用されるネットワーク相互接続スイッチを含む構築ブロックから構築される汎用システムの一例を示す概略ブロック図である。
【図１Ｂ】入力コントローラの概略的ブロック図である。
【図１Ｃ】出力コントローラの概略的ブロック図である。
【図１Ｄ】システムプロセッサとスイッチングシステムおよび外部デバイスへのその接続を示す概略的なブロック図である。
【図１Ｅ】図１Ａに示すタイプの完全なシステムの一例を示す概略的なブロック図であり、要求スイッチとデータスイッチシステムを単一のコンポーネントに組み合わせることにより、特定の応用例で有利に処理を簡略化し、システムを実装するのに必要な回路量を減らすシステムの図である。
【図１Ｆ】図１Ａに示すタイプの完全なシステムの一例を示す概略的なブロック図であり、要求スイッチ、応答スイッチ、およびデータスイッチシステムを１つのコンポーネントに組み合わせ、それにより特定の応用例でシステムを実装するのに必要な回路量を有利に減らすシステムの図である。
【図２Ａ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｂ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｃ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｄ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｅ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｆ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｇ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｈ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｉ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｊ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｋ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図２Ｌ】スイッチングシステムの各種実施形態でシステムの各種コンポーネント中で使用されるパケットのフォーマットを示す図である。
【図３Ａ】パケットの時間スロット確保のスケジューリングのために各種コンポーネントで使用されるパケットフォーマットを示す図である。
【図３Ｂ】パケットの時間スロット確保のスケジューリングのために各種コンポーネントで使用されるパケットフォーマットを示す図である。
【図３Ｃ】入力プロセッサが将来の指定された期間の送信を要求する方式、要求プロセッサがその要求を受け取る方式、および要求プロセッサが要求元の入力プロセッサに返信して送信が可能な時間を知らせる方式を示す、時間スロット確保の方法の図である。
【図４Ａ】マルチキャスト機能を備える入力制御装置の概略的ブロック図である。
【図４Ｂ】マルチキャスト機能を備える要求コントローラを示す概略的ブロック図である。
【図４Ｃ】マルチキャスト機能を備えるデータスイッチを示す概略的ブロック図である。
【図５Ａ】制御システムに代替のマルチキャストサポート手段を備えた、図１のシステムの一例を示す概略的ブロック図である。
【図５Ｂ】データスイッチファブリック中の代替のマルチキャストサポート手段を示す概略的ブロック図である。
【図６Ａ】制御およびスイッチングシステムの主要コンポーネントによる時間的に重複した処理を示す概略的なタイミング図である。
【図６Ｂ】制御システムコンポーネントによる時間的に重複した処理をより詳細に示すタイミング図の一例の図である。
【図６Ｃ】指定された期間にのみマルチキャスト要求を行うマルチキャストタイミング方式を示すタイミング図である。
【図６Ｄ】図３Ａ、３Ｂおよび３Ｃを用いて述べた時間スロット確保のスケジューリングをサポートする制御システムの一実施形態の概略的なタイミング図である。
【図７】トラフィック要件に動的に対処する際の柔軟性を物理的実施形態に有利に与える電子スイッチの構成可能な出力接続の図である。
【図８】ノード中のトランキングをサポートする電子ＭＬＭＬスイッチファブリックの下位レベルの回路図である。
【図９】単一の制御スイッチに対応する複数のデータスイッチを用いることにより高帯域幅を提供する設計の概略的ブロック図である。
【図１０Ａ】レイヤ中でラインカードのセットに接続して、システムの容量と速度をスケーラブルな方式で増大する複数システム１００を示す概略的ブロック図である。
【図１０Ｂ】複数の出力コントローラを組み合わせて単一の装置とした図１０Ａのシステムの変形形態の図である。
【図１１Ａ】スイッチ間で集線装置を使用するツイステッドキューブ型のデータスイッチの概略的ブロック図である。
【図１１Ｂ】ツイステッドキューブを含むツイステッドキューブ型のデータスイッチおよび制御システムの概略的ブロック図である。
【図１１Ｃ】２つの管理レベルを有するツイステッドキューブ型システムの概略的ブロック図である。
【図１２Ａ】２つの東からのデータ経路、２つの北からのデータ経路、２つの西へのデータ経路、および２つの南へのデータ経路を有するノードの略図である。
【図１２Ｂ】短いパケット、中程度のパケット、長いパケット、および極めて長いパケットそれぞれに異なる経路がある、複数の東からのデータ経路と西へのデータ経路を示す概略的ブロック図である。
【図１３Ａ】図１２Ａに示すタイプのノードのタイミング図である。
【図１３Ｂ】図１２Ｂに示すタイプのノードのタイミング図である。
【図１４】長さが異なるパケットの同時の伝送をサポートするスイッチの一部の回路図と、ＭＬＭＬ相互接続ファブリックの２つの列および２つのレベルのノードを示す接続の図である。
【図１Ａ】
2005513827.tif 000005
【図１Ｂ】
2005513827.tif 000006
【図１Ｃ】
2005513827.tif 000007
【図１Ｄ】
2005513827.tif 000008
【図１Ｅ】
2005513827.tif 000009
【図１Ｆ】
2005513827.tif 000010
【図２Ａ】
2005513827.tif 000011
【図２Ｂ】
2005513827.tif 000012
【図２Ｃ】
2005513827.tif 000013
【図２Ｄ】
2005513827.tif 000014
【図２Ｅ】
2005513827.tif 000015
【図２Ｆ】
2005513827.tif 000016
【図２Ｇ】
2005513827.tif 000017
【図２Ｈ】
2005513827.tif 000018
【図２Ｉ】
2005513827.tif 000019
【図２Ｊ】
2005513827.tif 000020
【図２Ｋ】
2005513827.tif 000021
【図２Ｌ】
2005513827.tif 000022
【図３Ａ】
2005513827.tif 000023
【図３Ｂ】
2005513827.tif 000024
【図３Ｃ】
2005513827.tif 000025
【図４Ａ】
2005513827.tif 000026
【図４Ｂ】
2005513827.tif 000027
【図４Ｃ】
2005513827.tif 000028
【図５Ａ】
2005513827.tif 000029
【図５Ｂ】
2005513827.tif 000030
【図６Ａ】
2005513827.tif 000031
【図６Ｂ】
2005513827.tif 000032
【図６Ｃ】
2005513827.tif 000033
【図６Ｄ】
2005513827.tif 000034
【図７】
2005513827.tif 000035
【図８】
2005513827.tif 000036
【図９】
2005513827.tif 000037
【図１０Ａ】
2005513827.tif 000038
【図１０Ｂ】
2005513827.tif 000039
【図１１Ａ】
2005513827.tif 000040
【図１１Ｂ】
2005513827.tif 000041
【図１１Ｃ】
2005513827.tif 000042
【図１２Ａ】
2005513827.tif 000043
【図１２Ｂ】
2005513827.tif 000044
【図１３Ａ】
2005513827.tif 000045
【図１３Ｂ】
2005513827.tif 000046
【図１４】
2005513827.tif 000047
【国際調査報告】
2005513827.tif 000048