(57)【要約】【課題】【解決手段】相互接続ネットワークを介してユニキャストパケットをスケジューリングするシステムであって、それぞれがｒ２個の入力キューを有するｒ１個の入力ポートと、それぞれがｒ１個の出力キューを有するｒ２個の出力ポートと、少なくとも式（Ｉ）2007510376.tif 000015のスピードアップとサブネットワークを有する相互接続ネットワークとを有するシステムであって、各サブネットワークは、各サブネットワークは総数少なくともｒ１個の第１内部リンクに対する各入力ポートに接続される、少なくとも１個の第１内部リンクを備え、各サブネットワークはさらに総数少なくともｒ２個の第２内部リンクに対する各出力ポートに接続される、少なくとも１個の第２内部リンクを備える。本システムは、決定論的な方式で、かつパケットのセグメント化および再組立を要求することなく、ｒ１≦ｒ２のときは、スイッチングすべき各スイッチング時間において、多くともてｒ１回のスイッチング時間だけ、多くともｒ１個のパケットをスケジューリングし、ｒ２≦ｒ１のときは、スイッチングｓｙべき各スイッチング時間において、多くともｒ１回のスイッチング時間だけ、多くともｒ２個のパケットをスケジューリングすることで、本発明による厳密にノンブロッキング方式で動作する。本システムはさらに、１００％スループット、処理保存的、公正に、それでいてなお決定論的に動作し、それにより出力ポートを決して輻輳させない。本システムは調停に対して１度だけの繰り返しで、相互接続ネットワークにおいて数学的に最小のスピードアップで実行する。本システムは、相互接続ネットワークにおけるパケット再順序付けの問題と、パケットの内部バッファリングが全くなく動作し、従って真にカットスルーかつ分散した方式で動作する。一実施形態において、本システムは、唯一のサブネットワークで、かつそのサブネットワークを介して２倍のスイッチングレートで、厳密にノンブロッキング方式で動作する。別の実施形態において、本システムは、相互接続ネットワークにおいて、少なくとも式（II）2007510376.tif 000016のスピードアップで、再配置可能なノンブロッキング方式で動作する。入力ポートの数ｒ１が出力ポートの数ｒ２に等しく、ｒ１＝ｒ２＝ｒのとき、少なくとも式（III）2007510376.tif 000017のスピードアップを有する相互接続ネットワークが、スイッチングすべき各スイッチング時間において、多くともｒ回のスイッチング時間だけ決定論的な方式で、多くともｒ個のパケットをスケジューリングすることで、本発明による厳密にノンブロッキングで決定論的方式で動作する。そして相互接続ネットワーク内におきて、少なくとも式（IV）2007510376.tif 000018のスピードアップで、システムは再配置可能なノンブロッキングで決定論的方式で動作する。本システムは、入力ポートから出力ポートへのパケットに対するエンドツーエンド保証帯域幅およびレイテンシを提供する。全ての実施形態において、相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、任意の内部ノンブロッキング相互接続ネットワークまたはネットワークのネットワークであってよい。【選択図】図１Ｈ
2007510376.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ポートと複数の出力ポートとを有する相互接続ネットワークを介して、ユニキャストパケットをスケジューリングするシステムにおいて、前記パケットはそれぞれ指定出力ポートを有する前記システムであって、前記システムは、
前記各入力ポートにある複数の入力キューであって、前記入力キューは、ユニキャストパケットを有する入力キューと、
前記各入力ポートが、前記各入力ポートにある入力キューの数と多くとも同数のパケットのために、前記指定出力ポートからのサービスを要求する手段と、
前記各出力ポートが、複数の要求を許可する手段と、
前記各入力ポートが、前記入力キューと多くとも同数の許可を承認する手段と、
承認された許可を有する前記各入力ポートから、承認された許可に関連付けられる前記各出力ポートへの入力キューの数と多くとも同数のパケットをスケジューリングする手段とを備えることを特徴とするシステム。
【請求項２】
前記各出力ポートにある複数の出力キューであって、前記出力キューは、前記相互接続ネットワークを介して、ユニキャストパケットを受信する出力キューと、
前記各出力ポートが、前記出力キューと多くとも同数の要求を許可する手段と、
承認された許可を有する前記各入力ポートからの入力キューの数と多くとも同数のパケットと、承認された許可に関連付けられる前記各出力ポートへの出力キューの数と多くとも同数のパケットとをスケジューリングする手段とをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項３】
前記相互接続ネットワークは、ノンブロッキング相互接続ネットワークであることを特徴とする請求項１に記載のシステム。
【請求項４】
前記ノンブロッキング相互接続ネットワークは、少なくとも２のスピードアップを備えることを特徴とする請求項３に記載のシステム。
【請求項５】
前記スピードアップは、
並列性の手段、即ち、前記相互接続ネットワークを、少なくとも２回物理的に複製し、前記各入力ポート、および前記各出力ポートからの別個のリンクにより接続する手段、または、
前記入力ポートと前記相互接続ネットワークとの間、および前記出力ポートと前記相互接続ネットワークとの間のリンク帯域幅において、また前記相互接続ネットワークのクロックスピードにおいても、少なくとも２倍スピードアップする手段により実現することを特徴とする請求項４に記載のシステム。
【請求項６】
さらに、前記ノンブロッキング相互接続ネットワークを介して、ユニキャストパケットパスを、別のユニキャストパケットのための既に選択されたパスを決して変更しないことにより、常に選択可能であることを特徴とする請求項４に記載のシステムであって、
以後、前記相互接続ネットワークを「厳密なノンブロッキングネットワーク」と称する前記システム。
【請求項７】
前記ノンブロッキング相互接続ネットワークは、少なくとも１のスピードアップを備えることを特徴とする請求項３に記載のシステム。
【請求項８】
さらに、前記ノンブロッキング相互接続ネットワークを介して、ユニキャストパケットパスを、別のユニキャストパケットの既に選択したパスを、必要であれば変更することにより、常に選択可能であることを特徴とする請求項７に記載のシステムであって、
以後、前記相互接続ネットワークを「再配置可能なノンブロッキングネットワーク」と称する前記システム。
【請求項９】
既にスケジューリングされた前記パケットのスケジュールを保持する前記スケジューリング手段に結合されたメモリをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１０】
既にスケジューリングされた前記パケットのスケジュールを保持する前記スケジューリング手段に結合されたメモリをさらに備えることを特徴とする請求項２に記載のシステム。
【請求項１１】
調停、即ち、前記入力ポートによる前記サービスの前記要求と、前記出力ポートによる前記要求の前記許可と、前記入力ポートによる前記許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項１に記載のシステム。
【請求項１２】
調停、即ち、前記入力ポートによる前記サービスの前記要求と、前記出力ポートによる前記要求の前記許可と、前記入力ポートによる前記許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項２に記載のシステム。
【請求項１３】
前記パケットは、実質的に同一サイズであることを特徴とする請求項１に記載のシステム。
【請求項１４】
前記入力ポートにおいて行頭ブロッキングは、完全に削除されることを特徴とする請求項１に記載のシステム。
【請求項１５】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートへの、多くとも１個のパケットをスケジューリングすることを特徴とする請求項１に記載のシステム。
【請求項１６】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューからの多くとも１個のパケットと、前記承認された許可に関連付けられる前記各出力キューへの多くとも１個のパケットとをスケジューリングすることを特徴とする請求項２に記載のシステム。
【請求項１７】
前記パケットが少なくとも１つある限り、前記各出力ポートが、スイッチング時間において、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するよう動作することを特徴とする請求項１に記載のシステムであって、
以後、前記システムは「処理保存的システム」と称する前記システム。
【請求項１８】
前記パケットが少なくとも１つある限り、前記各出力ポートが、スイッチング時間において、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するよう動作することを特徴とする請求項２に記載のシステムであって、
以後、前記システムは「処理保存的システム」と称する前記システム。
【請求項１９】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において、多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項１に記載のシステム。
【請求項２０】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において、多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項２に記載のシステム。
【請求項２１】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング時間は設計時において可変となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング時間を選択する余地を与えることを特徴とする請求項１に記載のシステム。
【請求項２２】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング時間は設計時において可変となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング時間を選択する余地を与えることを特徴とする請求項２に記載のシステムム。
【請求項２３】
前記各入力キューの行頭にあるいずれの前記パケットも、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項１に記載のシステムであって、
以後、前記システムは「公正なシステム」と称する前記システム。
【請求項２４】
前記各入力キューの行頭にあるいずれの前記パケットも、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項２に記載のシステムであって、
以後、前記システムは「公正なシステム」と称する前記システム。
【請求項２５】
前記相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、又は任意の内部ノンブロッキング相互接続ネットワーク、又はネットワークのネットワークであることを特徴とする請求項１に記載のシステム。
【請求項２６】
前記システムは、１００％スループットで動作することを特徴とする請求項１に記載のシステム。
【請求項２７】
前記システムは、１００％スループットで動作することを特徴とする請求項２に記載のシステム。
【請求項２８】
前記システムは、任意の入力ポートから任意の出力ポートまでエンドツーエンド保証帯域幅を提供することを特徴とする請求項１に記載のシステム。
【請求項２９】
前記システムは、任意の入力ポートから任意の出力ポートまでエンドツーエンド保証帯域幅を提供することを特徴とする請求項２に記載のシステム。
【請求項３０】
複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供することを特徴とする請求項１に記載のシステム。
【請求項３１】
複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供することを特徴とする請求項２に記載のシステム。
【請求項３２】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする請求項１に記載のシステム。
【請求項３３】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする請求項２に記載のシステム。
【請求項３４】
複数の入力ポートと複数の出力ポートとを有する相互接続ネットワークを介し、ユニキャストパケットをスケジューリングする方法において、前記各入力ポートは、複数入力のキューを備え、前記パケットは、それぞれ少なくとも１つの指定出力ポートを有する前記方法であって、前記方法は、
前記各入力ポートにある入力キューの数と多くとも同数のパケットのための前記指定出力ポートから、前記各入力ポートに対しサービスを要求するステップと、
前記各出力ポートに対し、複数の要求を許可するステップと、
前記入力キューの数と多くとも同数の許可を、前記各入力ポートに対し承認するステップと、
承認された許可を有する前記入力ポートから、前記承認された許可に関連付けられる前記各出力ポートへの入力キューの数と多くとも同数の前記パケットをスケジューリングするステップとを備えることを特徴とする前記方法。
【請求項３５】
前記各出力ポートに複数の出力キューと、
前記出力ポートにある前記出力キューの数と多くとも同数の前記各出力ポートの要求を許可するステップと、
承認された許可を有する前記各入力ポートからの入力キューの数と多くとも同数のパケットと、承認された許可に関連付けられる前記各出力ポートへの出力キューの数と多くとも同数のパケットとをスケジューリングするステップとをさらに備えることを特徴とする請求項３４に記載の方法。
【請求項３６】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする請求項３４に記載のシステム。
【請求項３７】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする請求項３５に記載のシステム。
【請求項３８】
前記パケットは、実質的に同一サイズであることを特徴とする請求項３４に記載の方法。
【請求項３９】
前記入力ポートにおいて行頭ブロッキングは、完全に削除されることを特徴とする請求項３４に記載の方法。
【請求項４０】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートへの、多くとも１個のパケットをスケジューリングすることを特徴とする請求項３４に記載の方法。
【請求項４１】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューからの多くとも１個のパケットと、前記承認された許可に関連付けられる前記各出力キューへの多くとも１個のパケットとをスケジューリングすることを特徴とする請求項３５に記載の方法。
【請求項４２】
前記各出力ポートは、スイッチング時間において、少なくとも前記１個のパケットがある限り、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように動作することを特徴とする請求項３４に記載の方法。
【請求項４３】
前記各出力ポートは、スイッチング時間において、少なくとも前記１個のパケットがある限り、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように動作することを特徴とする請求項３５に記載の方法。
【請求項４４】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において多くとも１個のパケットを受信するよう動作可能であり、
それにより、相互接続ネットワークにおけるスピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項３４に記載の方法。
【請求項４５】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項３５に記載の方法。
【請求項４６】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット順序付けの問題が生じないよう動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項３４に記載の方法。
【請求項４７】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項３５に記載の方法。
【請求項４８】
前記各入力キューの行頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項３４に記載の方法。
【請求項４９】
前記各入力キューの行頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項３５に記載の方法。
【請求項５０】
前記方法は、１００％スループットでスケジューリングすることを特徴とする請求項３４に記載の方法。
【請求項５１】
前記方法は、１００％スループットでスケジューリングすることを特徴とする請求項３５に記載の方法。
【請求項５２】
前記方法は、いずれの入力ポートからいずれの出力ポートまでもエンドツーエンド保証帯域幅を提供するように動作することを特徴とする請求項３４に記載の方法。
【請求項５３】
前記方法は、いずれの入力ポートからいずれの出力ポートまでもエンドツーエンド保証帯域幅を提供するように動作することを特徴とする請求項３５に記載の方法。
【請求項５４】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供するように動作することを特徴とする請求項３４に記載の方法。
【請求項５５】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供するように動作することを特徴とする請求項３５に記載の方法。
【請求項５６】
相互接続ネットワークを介して、ユニキャストパケットをスケジューリングするシステムであって、前記システムは、
前記各パケットが指定出力ポートを有するｒ１個の入力ポートおよびｒ２個の出力ポートと、
前記ｒ１個の各入力ポートにある、前記パケットを備えるｒ２個の入力キューと、
ｓ≧１個のサブネットワークを備える前記相互接続ネットワークであって、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクのために各入力ポートに接続される少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、全体で少なくともｒ２個の第２内部リンクのために各出力ポートに接続される少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備える前記相互接続ネットワークと、
前記各入力ポートが、その各入力ポートからの、多くともｒ２個のパケットに対し、前記指定出力ポートからのサービスを要求する手段と、
前記各出力ポートが、複数の要求を許可する手段と、
前記各入力ポートが、多くともｒ２個のパケットの許可を承認する手段と、
多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ１個のパケットをスケジューリングする手段とを備えることを特徴とするシステム。
【請求項５７】
前記ｒ２個の各出力ポートにあるｒ１個の出力キューであって、前記相互接続ネットワークを介してユニキャストパケットを受信する前記出力キューと、
ｓ≧１個のサブネットワークを備え、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクのために各入力ポートに接続される少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、全体で少なくともｒ２個の第２内部リンクのために各出力ポートに接続される少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備える前記相互接続ネットワークと、
前記各出力ポートが、多くともｒ１個のパケットを許可する手段と、
ｒ１≦ｒ２であるときは、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時間において、多くともｒ１個のパケットを、およびｒ２≦ｒ１であるときは、多くともｒ１回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する多くともｒ２個のパケットと、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ２個のパケットをスケジューリングする手段とをさらに備えることを特徴とする請求項５６に記載のシステム。
【請求項５８】
前記相互接続ネットワークは、ノンブロッキング相互接続ネットワークであることを特徴とする請求項５６に記載のシステム。
【請求項５９】
前記システムは、
2007510376.tif 000013
個のサブネットワークを備え、
さらに、前記ノンブロッキング相互接続ネットワークを介して、別のユニキャストパケットに対して、既に選択されたパスを決して変更しないことにより、ユニキャストパケットに対し、パスが常に選択可能であることを特徴とする請求項５８に記載のシステムであって、
以後、前記相互接続ネットワークは「厳密なノンブロッキングネットワーク」と称する、前記システム。
【請求項６０】
前記システムは、ｓ≧１個のサブネットワークを備え、
前記第１内部リンクと前記第２内部リンクとの双方は、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも２倍速く動作し、
前記サブネットワークは、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも２倍速く動作するシステムであって、
前記システムは、さらに、前記ノンブロッキング相互接続ネットワークを介して、別のユニキャストパケットのために、既に選択されたパスを決して変更しないことにより、ユニキャストパケットに対し、パスが常に選択可能であることを特徴とする請求項５８に記載のシステムであって、
以後、前記相互接続ネットワークは「厳密なノンブロッキングネットワーク」と称する、前記システム。
【請求項６１】
前記システムは、
2007510376.tif 000014
個のサブネットワークを備え、
前記第１内部リンクと前記第２内部リンクとの双方は、前記入力キューにおいて受信される各パケットのピークレートと、少なくとも同じ速さで動作し、
前記サブネットワークは、前記入力キューにおいて受信される各パケットのピークレートと、少なくとも同じ速さで動作するシステムであって、
前記システムは、さらに、前記ノンブロッキングな相互接続ネットワークを介して、別のユニキャストパケットの既に選択されたパスを、必要であれば変更することにより、ユニキャストパケットに対し、パスが常に選択可能であることを特徴とする請求項５８に記載のシステムであって、
以後、前記相互接続ネットワークは「再配置可能なノンブロッキングネットワーク」と称する、前記システム。
【請求項６２】
前記スケジューリングの手段に結合されるメモリをさらに備え、既にスケジューリングされた前記パケットのスケジュールを保持することを特徴とする請求項５６に記載のシステム。
【請求項６３】
前記スケジューリングの手段に結合されるメモリをさらに備え、既にスケジューリングされた前記パケットのスケジュールを保持することを特徴とする請求項５７に記載のシステム。
【請求項６４】
調停、即ち、前記入力ポートによるサービスの前記要求と、前記出力ポートによる要求の前記許可と、前記入力ポートによる許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項５６に記載のシステム。
【請求項６５】
調停、即ち、前記入力ポートによるサービスの前記要求と、前記出力ポートによる要求の前記許可と、前記入力ポートによる許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項５７に記載のシステム。
【請求項６６】
ｒ１＝ｒ２＝ｒであり、前記スケジューリングの手段は、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ個のパケットをスケジューリングすることを特徴とする請求項５６に記載のシステム。
【請求項６７】
ｒ１＝ｒ２＝ｒであり、前記スケジューリングの手段は、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ個のパケットをスケジューリングすることを特徴とする請求項５７に記載のシステム。
【請求項６８】
前記パケットは、実質的に同一サイズであることを特徴とする請求項５６に記載のシステム。
【請求項６９】
前記入力ポートにおいて行頭ブロッキングは、完全に削除されることを特徴とする請求項５６に記載のシステム。
【請求項７０】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートへの、多くとも１個のパケットをスケジューリングすることを特徴とする請求項５６に記載のシステム。
【請求項７１】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューからの多くとも１個のパケットと、前記承認された許可に関連付けられる前記各出力キューへの多くとも１個のパケットとをスケジューリングすることを特徴とする請求項５７に記載のシステム。
【請求項７２】
前記パケットが少なくとも１つある限り、前記各出力ポートが、スイッチング時間において、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するよう動作することを特徴とする請求項５６に記載のシステムであって、
以後、前記システムは「処理保存的システム」と称する前記システム。
【請求項７３】
前記パケットが少なくとも１つある限り、前記各出力ポートが、スイッチング時間において、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するよう動作することを特徴とする請求項５７に記載のシステムであって、
以後、前記システムは「処理保存的システム」と称する前記システム。
【請求項７４】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において、多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項５６に記載のシステム。
【請求項７５】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において、多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項５７に記載のシステム。
【請求項７６】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項５６に記載のシステム。
【請求項７７】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項５７に記載のシステム。
【請求項７８】
前記各入力キューの行頭にあるいずれの前記パケットも、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項５６に記載のシステムであって、
以後、前記システムは「公正なシステム」と称する前記システム。
【請求項７９】
前記各入力キューの行頭にあるいずれの前記パケットも、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項５７に記載のシステムであって、
以後、前記システムは「公正なシステム」と称する前記システム。
【請求項８０】
前記相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、又は任意の内部ノンブロッキング相互接続ネットワーク、又はネットワークのネットワークであることを特徴とする請求項５６に記載のシステム。
【請求項８１】
前記システムは、１００％スループットで動作することを特徴とする請求項５６に記載のシステム。
【請求項８２】
前記システムは、１００％スループットで動作することを特徴とする請求項５７に記載のシステム。
【請求項８３】
前記システムは、任意の入力ポートから任意の出力ポートまでエンドツーエンド保証帯域幅を提供することを特徴とする請求項５６に記載のシステム。
【請求項８４】
前記システムは、任意の入力ポートから任意の出力ポートまでエンドツーエンド保証帯域幅を提供することを特徴とする請求項５７に記載のシステム。
【請求項８５】
複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供することを特徴とする請求項５６に記載のシステム。
【請求項８６】
複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供することを特徴とする請求項５７に記載のシステム。
【請求項８７】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする請求項５６に記載のシステム。
【請求項８８】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする請求項５７に記載のシステム。
【請求項８９】
相互接続ネットワークを介するユニキャストパケットのスケジューリングの方法であって、
前記各パケットが少なくとも１つの指定出力ポートを有するｒ１個の入力ポートおよびｒ２個の出力ポートと、
前記ｒ１個の各入力ポートにある、前記パケットを備えるｒ２個の入力キューと、
ｓ≧１個のサブネットワークを備え、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクのために各入力ポートに接続される少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、全体で少なくともｒ２個の第２内部リンクのために各出力ポートに接続される少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備える前記相互接続ネットワークとを有する前記方法であって、前記方法は、
多くともｒ２個の前記パケットのための前記指定出力ポートから、前記各入力ポートに対しサービスを要求するステップと、
前記各出力ポートに対し、複数の要求を許可するステップと、
多くともｒ２個の前記パケットにある前記各入力ポートに対し、要求を承認するステップと、
多くともｒ２個のパケットにある前記各入力ポートに対し、許可を承認するステップと、
多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ１個のパケットをスケジューリングするステップとを備えることを特徴とする前記方法。
【請求項９０】
ｒ２個の前記各出力ポートにあるｒ１個の出力キューであって、前記相互接続ネットワークを介してマルチレートユニキャストパケットを受信する前記出力キューと、
ｓ≧１個のサブネットワークを備える前記相互接続ネットワークであって、各サブネットワークは、各入力ポート対し全体で少なくともｒ１個の第１内部リンクのため接続される、少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、各出力ポートに対し全体で少なくともｒ２個の第２内部リンクのため接続される、少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備える相互接続ネットワークと、
前記各出力ポートに対し、多くともｒ１個のパケットを許可するステップと、
ｒ１≦ｒ２であるときは、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記出力ポートへの多くともｒ１個のパケットをスケジューリングし、ｒ２≦ｒ１であるときは、多くともｒ１回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記出力ポートへの多くともｒ２個のパケットをスケジューリングするステップとをさらに備えることを特徴とする請求項８９に記載の方法。
【請求項９１】
調停、即ち、前記入力ポートによる前記サービスの前記要求と、前記出力ポートによる前記要求の前記許可と、前記入力ポートによる前記許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項８９に記載の方法。
【請求項９２】
調停、即ち、前記入力ポートによる前記サービスの前記要求と、前記出力ポートによる前記要求の前記許可と、前記入力ポートによる前記許可の前記承認とを、１度の繰り返しのみで実行することを特徴とする請求項９０に記載の方法。
【請求項９３】
ｒ１＝ｒ２＝ｒであり、前記スケジューリングの手段は、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ個のパケットをスケジューリングすることを特徴とする請求項８９に記載の方法。
【請求項９４】
ｒ１＝ｒ２＝ｒであり、前記スケジューリングの手段は、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時間において、承認された許可を有する、前記承認された許可に関連付けられる前記各出力ポートへの多くともｒ個のパケットをスケジューリングすることを特徴とする請求項９０に記載の方法。
【請求項９５】
前記パケットは、実質的に同一サイズであることを特徴とする請求項８９に記載の方法。
【請求項９６】
前記入力ポートにおける行頭ブロッキングは、完全に削除されることを特徴とする請求項８９に記載の方法。
【請求項９７】
前記スケジューリング手段は、スイッチング時間に、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートへの、多くとも１個のパケットをスケジューリングすることを特徴とする請求項８９に記載の方法。
【請求項９８】
前記スケジューリング手段は、スイッチング時間において、承認された許可を有する前記各入力キューからの多くとも１個のパケットと、前記承認された許可に関連付けられる前記各出力キューへの多くとも１個のパケットとをスケジューリングすることを特徴とする請求項９０に記載の方法。
【請求項９９】
前記各出力ポートは、スイッチング時間において、少なくとも前記１個のパケットがある限り、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように動作することを特徴とする請求項８９に記載の方法。
【請求項１００】
前記各出力ポートは、スイッチング時間において、少なくとも前記１個のパケットがある限り、少なくとも１個のパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように動作することを特徴とする請求項９０に記載の方法。
【請求項１０１】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において多くとも１個のパケットを受信するよう動作可能であり、
それにより、相互接続ネットワークにおけるスピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項８９に記載の方法。
【請求項１０２】
前記各出力ポートは、１個より多いパケットがその出力ポートを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、スイッチング時間において多くとも１個のパケットを受信するよう動作可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で動作させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする請求項９０に記載の方法。
【請求項１０３】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項８９に記載のシステム。
【請求項１０４】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介する同一パスで、前記入力ポートにより受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット順序付けの問題が生じないように動作し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時間においてスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする請求項９０に記載のシステム。
【請求項１０５】
前記各入力キューの行頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項８９に記載の方法。
【請求項１０６】
前記各入力キューの行頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう動作することを特徴とする請求項９０に記載の方法。
【請求項１０７】
前記方法は、１００％スループットで動作することを特徴とする請求項８９に記載の方法。
【請求項１０８】
前記方法は、１００％スループットで動作することを特徴とする請求項９０に記載の方法。
【請求項１０９】
前記方法は、いずれの入力ポートからいずれの出力ポートまでもエンドツーエンド保証帯域幅を提供するように動作することを特徴とする請求項８９に記載の方法。
【請求項１１０】
前記方法は、いずれの入力ポートからいずれの出力ポートまでもエンドツーエンド保証帯域幅を提供するように動作することを特徴とする請求項９０に記載の方法。
【請求項１１１】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供するように動作することを特徴とする請求項８９に記載の方法。
【請求項１１２】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証された一定のレイテンシを提供するように動作することを特徴とする請求項９０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願に対する相互参照
本願は、２００３年１０月３０日出願の米国仮特許出願番号６０／５１６，０５７に関し、それに対する優先権を主張する。本願は、本願と同一の出願人に譲渡され、同時出願された、Venkat Kondaによる「NONBLOCKING AND DETERMINISTIC UNICAST PACKET SCHEDULING」と題する関連米国特許出願、代理人整理番号Ｖ−０００５に対するＰＣＴ出願であり、その全体を参照により組み込む。本願は、本願と同一の出願人に譲渡された２００１年９月２７日出願のＶｅｎｋａｔ  Ｋｏｎｄａによる「REARRANGEABLY NON-BLOCKING MULTICAST MULTI-STAGE NETWORKS」と題する関連米国特許出願番号０９／９６７，８１５およびその一部継続出願である２００３年９月６日出願のＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７１に関し、その全体を参照により組み込む。本願は、本願と同一の出願人に譲渡され、Venkat Kondaによる「STRICTLY NON-BLOCKING MULTICAST MULTI-STAGE NETWORKS」と題する２００１年９月２７日出願の関連米国特許出願番号０９／９６７，１０６およびその一部継続出願である２００３年９月６日出願のＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７２に関し、その全体を参照により組み込む。
【０００２】
本願は、２００３年９月６日出願の米国仮特許出願番号６０／５００，７９０およびその米国特許出願番号１０／９３３，８９９、ならびに、その２００４年９月５日出願のＰＣＴ出願番号０４／２９０４３に関し、その全体を参照により組み込む。本願は、２００３年９月６日出願の米国仮特許出願番号６０／５００，７８９およびその米国特許出願番号１０／９３３，９００、およびその２００４年９月５日出願のＰＣＴ出願番号０４／２９０２７に関し、その全体を参照により組み込む。
【０００３】
本願は、２００３年１０月３０日出願の関連米国仮特許出願番号６０／５１６，２６５およびその米国特許出願、代理人整理番号Ｖ−０００６、および同時出願されたそのＰＣＴ出願、代理人整理番号Ｓ−０００６に関し、その全体を参照により組み込む。本願は、２００３年１０月３０日出願の米国仮特許出願番号６０／５１６，１６３、米国特許出願、代理人整理番号Ｖ−０００９、および同時出願されたそのＰＣＴ出願、代理人整理番号Ｓ−０００９に関し、その全体を参照により組み込む。本願は、２００３年１０月３０日出願の米国仮特許出願番号６０／５１５，９８５、米国特許出願、代理人整理番号Ｖ−００１０、および同時出願されたそのＰＣＴ出願、代理人整理番号Ｓ−００１０に関し、その全体を参照により組み込む。
【背景技術】
【０００４】
今日のＡＴＭスイッチおよびＩＰルータは通常、多種の相互接続ネットワークを使用し、入力ポート（「入口ポート」とも呼ばれる）から所望の出力ポート（「出口ポート」とも呼ばれる）へパケットをスイッチングする。相互接続ネットワークを介してパケットをスイッチングするには、入力ポートもしくは出力ポート、または入力ポートと出力ポートの双方でキューイングされる。パケットは１つまたは複数の出力ポートを宛先としてよい。１つの出力ポートのみを宛先とするパケットをユニキャストパケットと呼び、１つを超える出力ポートを宛先とするパケットをマルチキャストパケットと呼び、全ての出力ポートを宛先とするパケットをブロードキャストパケットと呼ぶ。
【０００５】
出力キュー（ＯＱ）スイッチは出力ポートでのみキューを採用する。出力キュースイッチにおいては、入力ポートにおいてパケットを受信すると即座に宛先出力ポートキューにスイッチングする。パケットは、即座に出力ポートキューに転送されるので、ｒ＊ｒの出力キュースイッチにおいては、相互接続ネットワークにおいはｒのスピードアップを必要とする。入力キュー（ＩＱ）スイッチは、入力ポートでのみキューを採用する。入力キュースイッチは、相互接続ネットワークにおいて、１のみのスピードアップを必要とする。あるいは、ＩＱスイッチにおいてスピードアップは必要ない。しかしながら、入力キュースイッチは行頭（ＨＯＬ）ブロッキングを除去しない。これは、入力キューの行頭にあるパケットの宛先出力ポートがスイッチング時間においてビジーである場合、キュー内の次のパケットの宛先ポートが空いていても、これも遮断してしまうことを意味する。
【０００６】
入出力複合キュー（ＣＩＯＱ）スイッチは、その入力ポートと出力ポートの双方でキューを採用する。このようなスイッチは、相互接続ネットワークにおいて１からｒの間のスピードアップを採用することにより、ＯＱとＩＱスイッチ双方で最良の結果を出す。仮想出力キュー（ＶＯＱ）スイッチと呼ばれる別種のスイッチは、各入力ポートに、各出力ポートのうち１つを宛先とするパケットにそれぞれ対応するｒ個のキューを持つ設計となっている。ＶＯＱスイッチはＨＯＬブロッキングを除去する。
【０００７】
ＶＯＱスイッチは、近年非常に注目を集めている。「The iSLIP Scheduling Algorithm for Input-Queued Switches」と題するNick Mckeownの論文、IEEE/ACM Transactions on Networking、１９９９年４月、７巻２号は、本発明の背景として参照によりここに組込まれる。この論文には、１８８頁から１９０頁の序章において、クロスバーを基礎とする相互接続ネットワークのための数多くのスケジューリングアルゴリズムが説明されている。
【０００８】
背景として参照によりここに組込まれる、Nick Mckeownに権利が付与された「Combined Unicast and Multicast Scheduling」と題する米国特許６，２１２，１８２号は、各入力ポートにおいてｒ 個のユニキャストキューと１つのマルチキャストキューを用いるＶＯＱスイッチング技術について説明している。各スイッチング時間で、繰り返し調停が実行し、１個のパケットを各出力ポートにスイッチングする。
【０００９】
背景として参照してここに組込まれるPrabhakarらに権利が付与された「Switching System and Methods of Operation of Switching System」と題する米国特許６，３５１，４６６号には、各入力ポートにｒ個のユニキャストキューと、各出力ポートに１つのマルチキャストキューを有し、パケットレイテンシの正確な制御を含む出力キュースイッチのようなクロスバー相互接続ネットワークのＶＯＱスイッチング技術に、少なくとも４のスピードアップが必要であると説明されている。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、先行技術のスイッチファブリックには多くの問題がある。第１に、マルチキャストパケットに対するＨＯＬブロッキングが除去されない。第２に、相互接続内の数学的に最小のスピードアップが未知である。第３に、相互接続ネットワークにおけるスピードアップの使用は、出力ポートをフラッドさせ、これが出力ポートにおける不必要なパケット輻輳、及びパケットをエグレスポート外に送信するためのレート減少を招く。第４に、任意にファンアウトされるマルチキャストパケットは、出力ポートに対してノンブロッキング方式ではスケジューリングできない。第５に、各スイッチング時間でパケット調停が繰り返し実行され、スイッチング時間、コストおよび電力の点で高くつく。最後に第６として、現行技術は、スケジューリングを最長で非決定論的方式で実行するため、入力ポートと出力ポートでのセグメント化と再組立を必要とする。
【課題を解決するための手段】
【００１１】
各入力ポートにユニキャストパケットを備える、複数の入力ポート、複数の出力ポート、及び複数の入力キューを有する相互接続ネットワークを介してマルチレートマルチキャストパケットをスケジューリングするシステムは、本発明に従って、各入力ポートから各出力ポートへの入力キューと多くとも同数のパケットをスケジューリングすることにより、ノンブロッキング方式で動作する。システムは１００％スループットで、処理保存的、公正ながら決定論的に動作し、それにより出力ポートを輻輳させることは決してない。本システムは、相互作用ネットワークにおける数学的に最小のスピードアップにより、調停を１度だけの繰り返しで実行する。システムは、相互接続ネットワークにおけるパケットの再順序付け問題と、パケットの内部バッファリングが全くなく、従って真にカットスルーで分散的な方式で動作する。別の実施形態において、各出力ポートも複数の出力キューを備え、各パケットは、宛先出力ポート内の出力キューまで、パケットのサイズに違いがあっても、ノンブロッキングで決定論的方式で、パケットのセグメント化及び再組立の必要なしに転送される。一実施形態において、スケジューリングは、相互接続ネットワークにおいて少なくとも２のスピードアップを用いて、厳密なノンブロッキング方式で実行される。別の実施形態において、スケジューリングは相互接続ネットワークにおいて、少なくとも１のスピードアップを用いて、再配置可能なノンブロッキング方式で実行される。本システムは、パケットのため、入力ポートから出力ポートまで、エンドツーエンド保証帯域幅とレイテンシトを提供する。全ての実施形態において、相互接続ネットワークは、クロスバーネットワークや、共有メモリネットワーク、クロス（Ｃｌｏｓ）ネットワーク、ハイパーキューブネットワーク、任意の内部ノンブロッキング相互接続ネットワーク、またはネットワークのネットワークであってよい。
【発明を実施するための最良の形態】
【００１２】
本発明は、トラフィックの性質に関わらず、ユニキャストパケットを備え、ユニキャストパケットは入力ポートに到着するスイッチファブリックにおける、ノンブロッキングで決定論的スケジューリングの設計および動作に関する。具体的には、本発明は、パケットスケジューリングシステムにおける以下の問題に関する。即ち、１）パケットの厳密に再配置可能なノンブロッキングスケジューリング、２）入力ポートから出力ポートまで（必要ならば出力ポートの特定の出力キューまで）決定論的に、即ち、出力ポートを輻輳させることなく、パケットをスイッチングすること、３）パケットのセグメント化と再組立（ＳＡＲ）の実装を必要としないこと、４）調停は、１度の繰り返しだけで行われること、５）相互接続ネットワークにおいて、数学的に最小のスピードアップを使用すること、６）パケットのサイズが可変な場合であっても、１００％スループットで公正な方式で動作することである。
【００１３】
入力ポートのパケットが１つより多い出力ポートを宛先としている場合、１対多のパケット転送が必要であり、マルチキャストパケットと呼ばれる。入力ポートのパケットがただ１つの出力ポートを宛先としている場合、１対１のパケット転送が必要であり、ユニキャストパケットと呼ばれる。入力ポートのパケットが全ての出力ポートを宛先としている場合、１対全のパケット転送が必要であり、ブロードキャストパケットと呼ばれる。相互接続ネットワークを介して転送されるセットのマルチキャストパケットは、マルチキャスト割当と呼ばれる。
【００１４】
ここで説明する種類のスイッチファブリックは、入力ポートの仮想出力キュー（ＶＯＱ）を使用する。一実施形態において、各入力ポートで受信したパケットは、出力ポートにあるのと同数のキューに配置される。各キューは、出力ポートの１つのみを宛先とするパケットを保持する。スイッチファブリックは、出力ポートに出力キューがあることも、ないこともある。出力キューがある場合、一実施形態において、入力ポートにあるのと同数のキューが各出力ポートに存在する。パケットは、各出力キューが１つの入力ポートのみからスイッチングされたパケットを保持するように、出力キューにスイッチングされる。
【００１５】
ここで説明した種類のスイッチファブリックのなかには、全ての入力ポート内の各入力キューが一定レートのユニキャストパケットを備え、出力ポート内で同等の帯域幅を配分する。一定レートのマルチキャストパケットを有し、すべての入力ポートの中に各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートにおいて同等の帯域幅を配分することは、先に参照により組込んだ米国特許出願、代理人整理番号Ｖ−０００６号及びＰＣＴ出願、代理人整理番号Ｓ−０００６号で詳しく説明されている。一定レートのマルチキャストパケットを有し、すべての入力ポート内に各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートにおいて同一の帯域幅を配分することは、先に参照により組込まれた米国特許出願、代理人整理番号Ｖ−０００９号及びそのＰＣＴ出願、代理人整理番号Ｓ−０００９号で詳しく説明されている。一定レートのマルチキャストパケットを有し、すべての入力ポート内に各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートに異なる帯域幅を配分し、先に参照により組み込んだ米国特許出願、代理人整理番号Ｖ−００１０、およびそのＰＣＴ出願、代理人整理番号Ｓ−００１０で詳しく説明されている。
【００１６】
図１Ａを参照すると、２つの４×４クロスバーネットワーク１３１−１３２から成る相互ネットワークである中間ステージ１３０を経由し、４個の入力ポート１５１−１５４から成る入力ステージ１１０と、４個の出力ポート１９１−１９４から成る出力ステージ１２０とを有する例示的なスイッチファブリック１０が示されている。各入力ポート１５１−１５４は、それぞれ入口リンク１４１−１４４を介してパケットを受信する。各出力ポート１９１−１９４は、それぞれ出口リンク２０１−２０４を介してパケットを送信する。各クロスバーネットワーク１３１−１３２は、８個のリンク（以下、「第１内部リンク」と呼ぶ）ＦＬ１−ＦＬ８を介して、４個の入力ポート１５１−１５４の各々に接続され、さらに８個のリンク（以下、「第２内部リンク」と呼ぶ）ＳＬ１−ＳＬ８を介して、４個の出力ポート１９１−１９４の各々に接続されている。図１Ａのスイッチファブリック１０において、入口リンク１４１−１４４、第１内部リンクＦＬ１−ＦＬ８、第２内部リンクＳＬ１−ＳＬ８、および出口リンク２０１−２０４の各々は、同一レートで動作する。
【００１７】
出力ポート１９１−１９４を宛先とするパケットが各入力ポート１５１−１５４でそれぞれ入力キュー１７１−１７４内に置かれるように、各入力ポート１５１−１５４において、入口リンク１４１−１４４を介して受信されるパケットを、存在する出力ポートと同数の入力キュー１７１−１７４（４個）に、宛先出力ポートに従ってソートする。一実施形態において、図１Ａのスイッチファブリック１０に示すように、パケットは入力キューに置かれる前に、優先度キュー１６１−１６４内に置かれてもよい。各優先度キュー１６１−１６４は、優先度［１-ｆ］に対応するパケットを保持するｆ個のキューを含む。例えば、出力ポート１９１を宛先とするパケットは、そのパケットの優先度［１-ｆ］に基づく優先度キュー１６１内に置かれ、最も高い優先度のパケットを最初に入力キュー１７１内に置いた後に、次に高い優先度のパケットを置く。優先度キュー１６１−１６４の使用は、スイッチファブリック１０の動作に無関係なので、図１Ａのスイッチファブリック１０は、別の実施形態では優先度キュー１６１−１６４なしで実装することもできる（優先度キューの使用は本発明で説明する全ての実施形態に無関係なので、全ての実施形態は、優先度キューなしにノンブロッキングで決定論的方式で、実装することもできる）。
【００１８】
また、ネットワークは、入力ステージ１１０、出力ステージ１２０、および中間ステージ１３０の各々に結合し、入力ポート１５１−１５４から出力ポート１９１−１９４へパケットをスイッチングするスケジューラを含む。スケジューラは、中間ステージ１３０内の相互接続ネットワークを介するパスに対して利用可能な宛先のリストをメモリ内に維持している。
【００１９】
一実施形態において、図１Ａに示すように、各出力ポート１９１−１９４は、存在する入力ポート（４個）と同数の出力キュー１８１−１８４から成り、入力ポート１５１−１５４からスイッチングされるパケットが各出力ポート１９１−１９４内の出力キュー１８１−１８４内にそれぞれ置かれるようになっている。図１Ａのスイッチファブリック１０における４個の入力ポート１５１−１５４内の各入力キュー１７１−１７４は、入力ポート１５１の入力キュー１７１内にＡ１−Ａ４を有し、出力ポートにスイッチングされる状態にある入力ポート１６４の４番目の入力キュー１７４内にＰ１−Ｐ４を有する例示的な４個のパケットを示す。４個の入力ポート１５１−１５４内の１６個の入力キュー全てにおける行頭パケットは、各々Ａ１−Ｐ１により指定される。
【００２０】
表１は、図１Ａのスイッチファブリック１０における入力キューと出力キューとの間の例示的なパケット割当を示す。Ｉ｛１，１｝で示される入力ポート１５１内の入力キュー１７１内のパケットは、Ｏ｛１，１｝で示される出力ポート１９１内の出力キュー１８１に対して割当てられてスイッチングされる。Ｉ｛１，２｝で示される入力ポート１５１内の入力キュー１７２内のパケットは、Ｏ｛２，１｝で示される出力ポート１９２内の出力キュー１８１に対して割当てられてスイッチングされる。同様に残りの１６個の入力キューにおけるパケットは、表１に示すように、残りの１６個の出力キューに割り当てられる。別の実施形態において、入力キューから出力キューへの割当は表１と異なってもよいが、本発明に従うと、各出力ポート内の出力キューにパケットをスイッチングするよう割り当てられた各入力ポート内の入力キューは１つのみであり、逆も真である。
【００２１】
【表１】
2007510376.tif 000003
【００２２】
本発明によると、全て１６個のパケットＡ１−Ｐ１は４回のスイッチング時（以降、“ファブリックスイッチングサイクル”と呼ぶ）に、ノンブロッキング方式で、中間ステージ１３０内の相互接続ネットワーク経由で入力ポートから出力ポートにスイッチングされる。各スイッチング時間において、多くとも１個のパケットが各入力ポートからスイッチングされ、多くとも１個のパケットが各出力ポートにスイッチングされる。各入力ポートは４個のユニキャストパケットのみを受信することができるため、図１Ａのスイッチファブリック１０において入力ポート衝突は決して生じない。任意の入力ポートからの各入力キューは、各出力ポート内の唯一の指定出力キューにのみスイッチングされるため、図１Ａのスイッチファブリック１０において出力ポート衝突は決して生じない。従って、調停の３つのステップ、即ち入力ポートによる要求の生成、出力ポートによる許可の発行および入力ポートによる許可の承認、が要求される。ここで出願人は、図１Ａのスイッチファブリック１０内の出力ポート１９１−１９４にスイッチングすべき１６個のパケットＡ１−Ｐ１の決定論的およびノンブロッキングなスケジューリングに関する問題は、図１Ｃに示す３ステージクロスネットワーク１４のノンブロッキングなスケジューリングに関係するという重要な見方をしている。
【００２３】
図１Ｃを参照すると、中間ステージ１３０を経由して入力ステージ１１０と出力ステージ１２０との間の通信要求を満たす１０個のスイッチの時間−空間−時間（ＴＳＴ）構成で動作する例示的な対称型３ステージクロスネットワーク１４が示されている。ここで、入力ステージ１１０は、４個の４×２スイッチＩＳ１−ＩＳ４から成り、出力ステージ１２０は４個の２×４スイッチＯＳ１−ＯＳ４から成り、中間ステージ１３０は２個の４×４スイッチＭＳ１−ＭＳ２から成る。入力ステージ１１０内のスイッチそれぞれに対する入口リンクと、出力ステージ１２０内のスイッチそれぞれに対する出口リンクの数はｎで表され、入力ステージ１１０と出力ステージ１２０におけるスイッチの数はrで表される。２個の中間スイッチＭＳ１−ＭＳ２それぞれは、ｒ個のリンクを介してｒ個の入力スイッチそれぞれに接続され（例えば、リンクＦＬ１−ＦＬ４は入力スイッチＩＳ１−ＩＳ４それぞれから、中間スイッチＭＳ１に接続される）、ｒ個の第２内部リンクを介して出力スイッチそれぞれに接続される（例えば、リンクＳＬ１−ＳＬ４は、中間スイッチＭＳ１から出力スイッチＯＳ１−ＯＳ４それぞれに接続される）。ネットワークは、１６個の入口リンク、即ちＩ｛１，１｝−Ｉ｛４，４｝および、１６個の出口リンクＯ｛１，１｝−Ｏ｛４，４｝を有する。図１Ｃの３ステージクロスネットワーク１４において、図１Ａのスイッチファブリック１０とちょうど同じように、表１に示すように、全ての１６個の入力リンクは１６個の出力リンクに割り当てられる。図１Ｃのネットワーク１４は、中間ステージ１３０内のスイッチ数が
2007510376.tif 000004
個に等しいとき、ユニキャスト接続要求に対して厳密なノンブロッキング方式で動作する（本発明の背景として参照により組み込んだ、Charles Closによる「A Study of Non-Blocking Switching Networks」、１９５３年１月、The Bell System Technical Journal発行、第３２巻、Ｎｏ，１、４０６−４２４頁を参照）。
【００２４】
本発明によると、中間ステージ１３０内の２個の４×４クロスバーネットワーク１３１−１３２、即ち、２のスピードアップを有する一実施形態において、図１Ａのスイッチファブリック１０が厳密なノンブロッキング方式で動作する。その厳密にノンブロッキングで決定論的スイッチングの実装に使用する詳細な方法は、本発明の開示内容の観点から当業者には自明である、多くの様々な方法のいずれであってもよい。そのような調停およびスケジューリング方法の１つは、以下の図１Ｂにおいて述べる。
【００２５】
【表２】
2007510376.tif 000005
【００２６】
表２は、一実施形態おいて、４回のスイッチング時それぞれにおける表１のパケット要求、許可と承認、に対するパケットのスケジュールを示し、これは図１Ｂの調停およびスケジューリング方法４０のスケジューリング部を使用して計算される。図１Ｄから図１Ｈは、各スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。図１Ｄは、パケットＡ１、Ｋ１、およびＰ１が出力キューにスイッチングされる第１のスイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＡ１は、クロスバーネットワーク１３１経由で、出力ポート１９１の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＦ１は、クロスバーネットワーク１３１経由で、出力ポート１９２の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＫ１は、クロスバーネットワーク１３２経由で、出力ポート１９３の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＰ１は、クロスバーネットワーク１３２経由で、出力ポート１９４の出力キュー１８４にスイッチングされる。最初のスイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートが唯一１個のパケットを受信することは明らかである。
【００２７】
図１ＥはパケットＤ１、Ｅ１、およびＯ１が出力キューにスイッチングされる第２スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＤ１は、クロスバーネットワーク１３１経由で、出力ポート１９４の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＥ１は、クロスバーネットワーク１３１経由で、出力ポート１９１の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＪ１は、クロスバーネットワーク１３２経由で、出力ポート１９２の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＯ１は、クロスバーネットワーク１３２経由で、出力ポート１９３の出力キュー１８４にスイッチングされる。再び、第２スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートが唯一１個のパケットを受信する。
【００２８】
図１ＦはパケットＣ１、Ｈ１、Ｉ１、およびＮ１が出力キューにスイッチングされる第３スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＣ１は、クロスバーネットワーク１３１経由で、出力ポート１９３の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＨ１は、クロスバーネットワーク１３１経由で、出力ポート１９４の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＩ１は、クロスバーネットワーク１３２経由で、出力ポート１９１の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＮ１は、クロスバーネットワーク１３２経由で、出力ポート１９２の出力キュー１８４にスイッチングされる。再び、第３スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートが唯一１個のパケットを受信する。
【００２９】
図１Ｇは、パケットＢ２、Ｇ２、およびＬ１が出力キューにスイッチングされる第４スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＢ２は、クロスバーネットワーク１３２経由で、出力ポート１９２の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＧ１は、クロスバーネットワーク１３１経由で、出力ポート１９３の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＬ１は、クロスバーネットワーク１３１経由で、出力ポート１９４の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＭ１は、クロスバーネットワーク１３２経由で、出力ポート１９１の出力キュー１８４にスイッチングされる。第４スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートが唯一１個のパケットを受信することは明らかである。
【００３０】
図１Ｈは、パケットが、第１スイッチング時間においてＡ１、Ｆ１、Ｋ１およびＰ１がスイッチされるのと同じように、Ａ２、Ｆ２、Ｋ２、およびＰ２が出力キューにスイッチングされる第５スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＡ２は、クロスバーネットワーク１３１経由で、出力ポート１９１の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＦ２は、クロスバーネットワーク１３１経由で、出力ポート１９２の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＫ２は、クロスバーネットワーク１３２経由で、出力ポート１９３の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＰ２は、クロスバーネットワーク１３２経由で、出力ポート１９４の出力キュー１８４にスイッチングされる。従って図１Ｂの調停およびスケジューリング方法４０は、最初のファブリックスイッチングサイクルに対するスケジューリングが実行された後に、再スケジューリングする必要はない。従って、任意の特定の入力キューから宛先出力キューへのパケットは、同じパスに沿ってスイッチングされ、入力ポートがそれらを受信するのと同じ順番で移動し、従ってパケットの再順序付け問題は決して生じない。
【００３１】
ファブリックスイッチングサイクルにおいて、全ての１６個のパケットＡ１−Ｐ１が宛先出力ポートにスイッチングされるので、スイッチは本発明に従ってノンブロッキングであり１００％スループットで動作する。図１Ａのスイッチファブリック１０は、スイッチング時間において、パケットが少なくとも１個ある限り、各出力ポートは、その出力ポートを宛先とする入力キューのいずれか１つから、少なくとも１個のパケットを受信するよう動作するので、以後そのスイッチファブリックは、「処理保存的システム」と呼ばれる。スイッチファブリックは、ノンブロッキングである場合、直接的に処理保存的であることは簡単に分かる。本発明によると、図１Ａのスイッチファブリック１０は、各入力キューの行頭のパケットはどれも、各入力ポートでの入力キュー数（４）と同数のスイッチング回数より多く維持されないよう動作するため、以後そのスイッチファブリックは、「公正なシステム」と呼ばれる。仮想出力キューは行頭で使用されるため、ブロッキングも除去される。
【００３２】
本発明によると、相互接続ネットワークにおいて２のスピードアップを使用してスイッチング時間において２個のパケットをスイッチング可能である場合でも、図１Ｂの調停およびスケジューリング方法４０を使用して、図１Ａのスイッチファブリック１０は、各出力ポートがスイッチ時に、多くとも１個のパケットを受信するように動作する。そのスピードアップは、相互接続ネットワークをノンブロッキング方式で動作させるためだけに厳密に使用され、かつ、出力ポートを決して輻輳させないように使用される。従って、図１Ａのスイッチファブリック１０内のパケットをスイッチングするための図１Ｃの調停およびスケジューリング方法４０は、決定論的である。各入口リンク１４１−１４４は各出口リンク２０１−２０４が送信するレートと同一レートで、即ち、各スイッチング時間において１個のパケットで、パケットを受信する。１個のパケットのみが各スイッチング時間で決定論的に各入力ポート１５１−１５４からスイッチされ、１個のパケットのみが各出力ポート１９１−１９４にスイッチングされるため、図１Ａのスイッチファブリック１０は決して出力ポートを輻輳させない。
【００３３】
本発明による決定論的なスイッチングの大きな利点は、パケットが、高くともピークレートで入力ポートからスイッチングされることである。このことは、パケットが、高くともピークレートで出力ポートにおいて受信されることも意味する。それは、出力ポートでトラフィック管理が必要なく、パケットは出力ポートから決定論的に送信されることを意味する。従って、トラフィック管理は、図１Ａのスイッチファブリック１０内の入力ポートでのみ必要となる。
【００３４】
図１Ａのスイッチファブリック１０の別の重要な特性は、特別な入力キューに属する全てのパケットが、宛先出力ポート内の同じ出力キューにスイッチングされることである。出願人は、出力キューによる３つのキーとなる利点を指摘する。１）スイッチング時間において、１バイトまたは一定数のバイトが入力ポートから出力ポートにスイッチングされる。あるいは、スイッチファブリックのスイッチング時間は可変であるため、スイッチファブリックの設計段階で柔軟なパラメータである。２）従って、たとえパケットＡ１−Ｐ１が任意の長さであり、サイズが可変であっても、入力キュー内の各パケットが宛先出力ポート内の同じ出力キューにスイッチングされるため、完全なパケットがスイッチング時間においてスイッチングされる必要はない。あるいは、出力キューの第２の利点は、長いパケットを入力ポート内で物理的にセグメント化する必要がなく、出力ポート内で再配置する必要がないということである。パケットは、物理的にセグメント化されずに、１セグメントずつ出力キューに論理的にスイッチングされる（パケットセグメントのサイズはスイッチング時間によって決定される）。各パケット内のパケットセグメントも、入力キューから宛先出力キューへの同一パスを介してスイッチングされる。３）出力キューの第３の利点は、パケットとパケットセグメントは、入力ポートがそれらを受信するのと同じ順番でスイッチングされ、決してパケット再順序付けの問題が生じないことである。
【００３５】
図１Ｉは、長いパケットをスイッチングするスイッチファブリック１６を示す。各入力キュー内には１個のパケットがあり、これにより１６個の全ての入力キューには１６個のパケットを作る。即ち、入力ポート１５１内の入力キュー１７１にはパケット｛Ａ１−Ａ４｝が、入力ポート１５１内の入力キュー１７２にはパケット｛Ｂ１−Ｂ４｝が、入力ポート１５１内の入力キュー１７３にはパケット｛Ｃ１−Ｃ４｝などが作られ、入力ポート１５４内の入力キュー１７４にはパケット｛Ｐ１−Ｐ４｝がある。これらの１６個のパケットそれぞれは、４個の等しいサイズのパケットセグメントから成る。例えば、パケット｛Ａ１−Ａ４｝は４個のパケットセグメント、即ちＡ１、Ａ２、Ａ３およびＡ４から成る。パケットのサイズが完全にパケットセグメントのサイズの４倍でない場合、４番目のパケットのサイズはより短い。しかしながら、４個のパケットセグメントのうちどれも、パケットセグメントのサイズの最大値よりは長くない。パケットセグメントのサイズはスイッチング時間によって決定される。即ち、各スイッチング時間において、唯一のパケットセグメントが任意の入力ポートから任意の出力ポートにスイッチングされる。より長いパケットのサイズ除いて、図１Ｉのスイッチファブリック１６の図は図１Ａのスイッチファブリック１０の図と同じである。
【００３６】
図１Ｊから図１Ｍは、各ファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。図１Ｊは、全ての行頭パケットセグメントＡ１−Ｐ１が出力ポートにスイッチングされる第１ファブリックスイッチングサイクル後の、図１Ｉのスイッチファブリック１６の状態を示す。図１Ｄ−１Ｇに示すように、これらのパケットセグメントは、図１Ｂの調停およびスケジューリング方法４０を使用して、図１Ａのスイッチファブリック１０においてパケットＡ１−Ｐ１が出力キューにスイッチングされるのと全く同じ方法で、出力キューにスイッチングされる。図１Ｋは、全ての行頭パケットセグメントＡ１−Ｐ１が出力キューにスイッチング第２ファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。図１Ｌは、全ての行頭パケットセグメントＡ３−Ｐ３が出力キューにスイッチングされる第３ファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。図１Ｍは、全ての行頭パケットセグメントＡ１−Ｐ１が出力キューにスイッチングされる第４ファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。第１、第２、第３、および第４のファブリックスイッチングサイクルの各々において、図１Ｄ−１Ｇに示すように、パケットＡ１−Ｐ１が、図１Ａのスイッチファブリック１０において、出力キューにスイッチングされるのと全く同じ方法で、パケットセグメントは出力キューにスイッチングされる。明らかに、全てのパケットセグメントは、各々の入力ポートが受信するのと同じ順序でスイッチングされる。従って、パケット再順序付けの問題はない。パケットはさらに１００％スループット、処理保存的、および公正な方式でスイッチングされる。
【００３７】
図１Ｊ−１Ｍにおいて、パケットは論理的にセグメント化され、出力ポートにスイッチングされる。一実施形態において、タグビット「１」がさらに各パケットセグメントの特別に指定されたビット位置にパディングされ、そのパケットセグメントが各パケット内で最初のパケットセグメントであることを表す。「１」のタグビットを読むことで、出力ポートはパケットセグメントＡ１−Ｐ１が、新規パケット内の最初のパケットセグメントであることを認識する。同様に各パケットセグメントは、「０」でパディングされる最後のパケットセグメントを除いて、指定ビット位置に「１」のタグビットでパディングされる（例えば、図１Ｉのスイッチファブリック１６内のパケットセグメントにおいて、パケットセグメントＡ１−Ｐ１、Ａ２−Ｐ２およびＡ３−Ｐ３は「１」のタグビットでパディングされ、パケットセグメントＡ４−Ｐ４は「０」のタグビットでパディングされる）。タグビットが「０」として検出されるとき、出力ポートは次に新規パケットのパケットセグメントまたは新規パケットを期待する。パケット内に１個のみのパケットセグメントがある場合、それは入力ポートによって「０」のタグビットで表される。出力ポートが「０」の指定タグビットを有する２つの連続パケットセグメントを受信した場合、出力ポートは、２番目のパケットセグメントを新規パケットの唯一のパケットセグメントであると判定する。
【００３８】
図１Ｉのスイッチファブリック１６において、パケットは４セグメントの長さである。しかしながら、一般にパケットは任意の長さである。加えて、同一キュー内の異なるパケットは異なるサイズでありうる。双方の場合において、図１Ｂの調停およびスケジューリング方法は、スイッチファブリックをノンブロッキング方式で動作させ、パケットは１００％スループット、処理保存的、および公正な方式でスイッチされる。さらに、入力ポート内でパケットを物理的にセグメント化し、出力ポート内で再組立する必要はない。スイッチファブリックのスイッチング時間は柔軟な設計パラメータでもあり、各スイッチング時間において１バイトずつ、または数バイトずつパケットをスイッチングするように設定される。
【００３９】
図１Ｂは、一実施形態において図１Ａのスケジューラにより実行される調停およびスケジューリング方法４０の高レベルフローチャートを示す。この実施形態による、多くともｒ個の要求が、アクト４１で各入力ポートから生成される。各入力ポートは、各入力キューから多くとも１個の要求を備えた、ｒ個の入力キューを有するので、各入力ポートからの多くともｒ個の要求が存在することになる。これらｒ個の要求の各々は異なる出力ポートにも宛てられる。アクト４２において、各出力ポートは多くともｒ個の許可を発行することになる。このとき、各要求は関連する出力キューに対応する。各入力ポートは、唯一の要求を生成するので、各出力ポートが、多くともｒ個の要求を各入力ポートから１個受信することは簡単に分かる。そして各出力ポートは許可を、ｒ個の受信された要求全てに発行できる。アクト４３において、各入力ポートは多くともｒ個の許可を承認する。各出力ポートは多くともｒ個の許可を各入力ポートに対して１個発行するので、各入力ポートは多くともｒ個の許可を受信する。そして各入力ポートはｒ個の許可全てを承認する。
【００４０】
アクト４４において、全てのｒ２個の要求が、以前スケジューリングしたパケットのパスを再配置せずにスケジューリングされる。本発明によると、全てのｒ２個の要求は中間ステージ１３０における少なくとも２のスピードアップで厳密にノンブロッキング方式でスケジューリングされる。要求生成の調停、許可の発行、承認の生成が、１度だけの繰り返しで実行されることに留意されたい。アクト４４の後に、制御はアクト４５に戻る。アクト４５において、入力ポートで新規の要求または異なる要求があるかどうかがチェックされる。結果が「ノー」の場合、制御はアクト４５に戻る。新規要求はあるが同一の要求であり、出力キュー要求に対して同じ入力キューを有する場合、同じスケジュールが使用され、次のｒ２個の要求をスイッチングする。入力ポートから新規の要求および異なる要求があるとき、制御はアクト４５からアクト４１に移る。そしてアクト４１−４５がループ内で実行される。
【００４１】
図１Ｃのネットワーク１４は、中間ステージ１３０のスイッチの数が
2007510376.tif 000006
に等しいとき、ユニキャスト接続要求に対して再配置可能なノンブロッキング方式で動作することもできる。同様に本発明によると、中間ステージ１３０内で４×４クロスバーネットワーク１３１を１つだけ、即ち少なくとも１のスピードアップを有する別の実施形態において、図１Ｎのスイッチファブリック１８は、再配置可能なノンブロッキング方式で動作する。
【００４２】
厳密にノンブロッキングなネットワークにおいて、全ての入力キューの行頭でパケットが一度にスケジューリングされると、以前スケジューリングしたパケットのパスを乱すことなく、ネットワークを介して入力キューから宛先出力キューまで、パケットのパスをスケジューリングすることが常に可能であり、１個より多くののそのようなパスが利用可能な場合、残りのパケットのスケジューリングを気にすることなく、任意のパスを選択できる。再配置可能なノンブロッキングなネットワークにおいて、全ての入力キューの行頭でパケットが一度にスケジューリングされると、入力キューから宛先出力キューへのパケットのパスをスケジューリングすることは、再配置が必要な場合は、以前スケジューリングしたパケットのパスをスケジューラが再配置することで満足されるよう保証される。本発明によると、図１Ａのスイッチファブリック１０が厳密にノンブロッキング方式で動作するのに対して、図１Ｎのスイッチファブリック１８は再配置可能なノンブロッキング方式で動作する。
【００４３】
図２Ａを参照すると、スイッチファブリック２０は出力キューを有さない。そうでなければ、図２Ａのスイッチファブリック２０は、図１Ａのスイッチファブリック１０の図と全く同じである。本発明によると、スイッチファブリック２０は、入力ポートおよび出力ポート内にＳＡＲが必要であるのを除いて、図１Ａのスイッチファブリック１０について開示したのと全ての点で同じように、厳密にノンブロッキングで決定論的方式で動作する。パケットは、スイッチング時間によって決定されたように入力ポート内でセグメント化され、出力ポートにスイッチングされて、別個に再組立される必要がある。しかしながら、図１Ｂの調停およびスケジューリング方法４０は、図２Ａのスイッチファブリック２０内のパケットをスイッチングするためにも使用される。ここでさらに、スケジューリングは全ての１６個の行頭パケット上で同時に実行され、仮想的に１６個の出力キューがあると仮定すると、パケットは４回のスイッチング時間でスイッチングされる。しかしながら、スイッチング時間の間、パケットは出力キューの代わりに、宛先出力ポートにスイッチングされる。図２Ｂ−２Ｆは、図１Ｂの調停およびスケジューリング方法を使用し、表１に示すパケット要求をスケジューリングすることによる、各スイッチング時間後の図２Ａのスイッチファブリック２０の状態を示す。
【００４４】
図２Ｂは、パケットＡ１、Ｆ１、Ｋ１、およびＰ１が出力キューにスイッチングされる最初のスイッチング時間後の図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのパケットＡ１は、クロスバーネットワーク１３１経由で、出力ポート１９１にスイッチングされる。入力ポート１５２からのパケットＦ１は、クロスバーネットワーク１３１経由で、出力ポート１９２にスイッチングされる。入力ポート１５３からのパケットＫ１は、クロスバーネットワーク１３２経由で、出力ポート１９３にスイッチングされる。入力ポート１５４からのパケットＰ１は、クロスバーネットワーク１３２経由で、出力ポート１９４にスイッチングされる。第１スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートは唯一１個のパケットを受信することは明らかである。
【００４５】
図２Ｃは、パケットＤ１、Ｅ１、Ｊ１およびＯ１が出力キューにスイッチングされる第２スイッチング時間後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのパケットＤ１は、クロスバーネットワーク１３１経由で、出力ポート１９４にスイッチングされる。入力ポート１５２からのパケットＥ１は、クロスバーネットワーク１３１経由で、出力ポート１９１にスイッチングされる。入力ポート１５３からのパケットＪ１は、クロスバーネットワーク１３２経由で、出力ポート１９２にスイッチングされる。入力ポート１５４からのパケットＯ１は、クロスバーネットワーク１３２経由で、出力ポート１９３にスイッチングされる。再び、第２スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートは唯一１個のパケットを受信する。
【００４６】
図２Ｄは、パケットＣ１、Ｈ１、Ｉ１およびＮ１が出力キューにスイッチングされる第３スイッチング時間後の図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのパケットＣ１は、クロスバーネットワーク１３１経由で、出力ポート１９３にスイッチングされる。入力ポート１５２からのパケットＨ１は、クロスバーネットワーク１３１経由で、出力ポート１９４にスイッチングされる。入力ポート１５３からのパケットＩ１は、クロスバーネットワーク１３２経由で、出力ポート１９１にスイッチングされる。入力ポート１５４からのパケットＮ１は、クロスバーネットワーク１３２経由で、出力ポート１９２にスイッチングされる。再び、第３スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートは唯一１個のパケットを受信する。
【００４７】
図２Ｅは、パケットＢ１、Ｇ１、Ｌ１およびＭ１が出力キューにスイッチングされる第４スイッチング時間後の図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのパケットＢ１は、クロスバーネットワーク１３２経由で、出力ポート１９２にスイッチングされる。入力ポート１５２からのパケッＧ１は、クロスバーネットワーク１３１経由で、出力ポート１９３にスイッチングされる。入力ポート１５３からのパケットＬ１は、クロスバーネットワーク１３１経由で、出力ポート１９４にスイッチングされる。入力ポート１５４からのパケットＭ１は、クロスバーネットワーク１３２経由で、出力ポート１９１にスイッチングされる。第４スイッチング時間において、各入力ポートから唯一１個のパケットがスイッチングされ、各出力ポートは唯一１個のパケットを受信するは明らかである。
【００４８】
図２Ｆは、Ａ１、Ｆ１、Ｋ１およびＰ１が、第１スイッチング時間においてスイッチングされるのと全く同じように、パケットＡ２、Ｆ２、Ｋ２およびＰ２が出力キューにスイッチングされる第５スイッチング時間後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのパケットＡ２は、クロスバーネットワーク１３１経由で、出力ポート１９１にスイッチングされる。入力ポート１５２からのパケットＦ２は、クロスバーネットワーク１３１経由で、出力ポート１９２にスイッチングされる。入力ポート１５３からのパケットＫ２は、クロスバーネットワーク１３２経由で、出力ポート１９３にスイッチングされる。入力ポート１５４からのパケットＰ２は、クロスバーネットワーク１３２経由で、出力ポート１９４にスイッチングされる。
【００４９】
また、図１Ｂの調停およびスケジューリング方法４０は、図２Ａのスイッチファブリック２０を厳密にノンブロッキング方式で動作させ、パケットは、１００％スループット、処理保存的、および公正な方式で動作する。スイッチファブリックのスイッチング時間は、柔軟な設計パラメータでもあり、各スイッチング時間において１バイトずつまたは数バイトずつパケットをスイッチングするよう設定することができる。しかしながら、スイッチファブリック２０にＳＡＲ必要となり、パケットが入力ポート内で物理的にセグメント化され、出力ポート内で再組立される必要があることになる。それにも関わらず、スイッチファブリック２０において、パケットおよびパケットセグメントは、入力ポートが受信するのと同じ順序で、出力ポートにスイッチングされる。実際、ＳＡＲを除き、図１Ｂの調停およびスケジューリング方法４０は、図１Ａのスイッチファブリック１０に関して説明したのと全ての点で、同じ方法でスイッチファブリック２０を動作させる。
【００５０】
スイッチファブリックがノンブロッキングに動作するための中間ステージにおける２のスピードアップは、２つの方法で実現される。即ち、１）並列処理および２）スイッチングレートの２倍化である。並列処理は、例えば図１Ａのスイッチファブリック１０で示すように、中間ステージ内の２個の相互接続ネットワークを並列に使用することで実現される。スイッチングレートの２倍化は、入力ポートおよび出力ポート内の各クロックに対して、単一の相互接続ネットワーク、第１および第２の内部リンクを２倍のクロックレートで動作させることで実現される。第１クロックにおいて、単一の相互接続ネットワークは、２個の並列相互接続ネットワークで実装された等価なスイッチファブリックの第１相互接続、例えば図１Ａのスイッチファブリック１０内の相互接続ネットワーク１３１として、スイッチングに対して動作する。同様に第２クロックにおいて、単一の相互ネットワークは、第２相互接続ネットワーク、例えば図１Ａのスイッチファブリック１０内の相互接続ネットワーク１３２として動作する。従って、相互接続ネットワークのクロックスピードと、第１および第２の内部リンクとにおいて２倍のレートがこの実装に必要となる。図１Ｂの調停およびスケジューリング方法４０は、並列処理または２倍のレートによるスピードアップを実装して、双方のスイッチファブリックを、本発明において説明したように、全ての点でノンブロッキングで決定論的方式で動作させる。
【００５１】
図３Ａを参照すると、図３Ａはスイッチファブリック３０を示す。中間ステージ１３０内の唯一のクロスバー相互接続ネットワークでのクロックスピードを２スピードアップさせることと、第１および第２の内部リンクを２スピードアップさせることを除いて、図１Ａのスイッチファブリック１０の図と同じである。図１Ａのネットワークの別の実施形態において、中間ステージ内の各相互接続ネットワークは共有メモリネットワークである。図３Ｂは、スイッチファブリック５０を示す。中間ステージ１３０内の２個の共有メモリ相互接続ネットワークをスピードアップさせることを除いて、図１Ａのスイッチファブリック１０と同じである。図３Ｃは、スイッチファブリック６０を示す。中間ステージ１３０内の唯一の共有メモリ相互接続ネットワークのクロックスピードを２スピードアップさせることと、第１および第２の内部リンクを２スピードアップさせることを除いて、図３Ａのスイッチファブリック３０と全く同じである。
【００５２】
同様に、図３Ｄは、スイッチファブリック７０を示す。２スピードアップに、中間ステージ１３０内の２個のハイパーキューブ相互接続ネットワークを２スピードアップさせることを除いて、図１Ａのスイッチファブリック１０と全く同じである。図３Ｅは、スイッチファブリック６０を示す。中間ステージ１３０内の唯一のハイパーキューブベースの相互接続ネットワークのクロックレートを２スピードアップさせることと、第１および第２の内部リンクを２スピードアップさせることを除いて、図３Ａのスイッチファブリック３０と全く同じである。
【００５３】
図１Ａのスイッチファブリック１０、図１Ｉの１６、図１Ｎの１８、図２Ａの２０、図３Ａの３０、図３Ｂの５０、図３Ｃの６０、図３Ｄの７０、および図３Ｅの８０において、入力ポート１１０の数と出力ポート１２０の数が、一般に各ステージに対する変数ｒで表される。中間ステージにおけるスピードアップはｓで表される。中間ステージにおけるスピードアップは、並列処理、即ち２個の相互接続ネットワーク（図４Ａ、図４Ｃおよび図４Ｅに示す）、または１個の相互接続ネットワークにおける２倍のスイッチングレート（図４Ｂ、図４Ｄおよび図４Ｆに示す）のいずれかにより実現される。各入力ポートのサイズ１５１−{１５１＋ｒ}は、一般にｒ＊ｓの記法で表され（各入力ポートがｒ個の入力キューを有し、ｓ個の相互接続ネットワークとｓ個の第１内部リンクで接続されるということである）、各出力スイッチのサイズ１９１−{１９１＋ｒ}は、一般にｓ＊ｒの記法で表される（各出力ポートがｒ個の出力キューを有し、ｓ個の相互接続ネットワークとｓ個の第２内部リンクで接続されるということである）。同様に、中間ステージ１３０内の各相互接続ネットワークのサイズはｒ＊ｒと表される。ここで説明した相互接続ネットワークは、クロスバーネットワークや、共有メモリネットワーク、各々がクロスバーまたは共有メモリネットワークであるサブネットワークのネットワーク、３ステージクロスネットワーク、ハイパーキューブ、任意の内部ノンブロッキング相互接続ネットワーク、またはネットワークのネットワークであってよい。３ステージスイッチファブリックは、Ｖ（ｓ，ｒ）の記法で表される。
【００５４】
存在する出力キュー１８１−{１８１＋ｒ}と同数の入力キュー１７１−{１７１＋ｒ}がある必要はないが、対称ネットワークにおいてそれらは同数である。ｓ個の中間ステージ相互接続ネットワーク１３１−１３２それぞれは、ｒ個の第１内部リンクを介して、ｒ個の入力ポートのそれぞれに接続され、ｒ個の第２内部リンクを介して、出力ポートそれぞれに接続される。第１の内部リンクＦＬ１−ＦＬｒそれぞれ、および第２内部リンクＳＬ１−ＳＬｒそれぞれは、新規パケットにより使用可能か、または別のパケットにより既に取得されている場合に利用可能でないかのいずれかである。
【００５５】
図１Ａのスイッチファブリック１０は、図４Ａの一般的な対称スイッチファブリックの例であり、中間ステージ１３０内の２個のクロスバー相互接続ネットワークを使用することで２のスピードアップを提供する。図４Ｂを参照すると、一般的な対称スイッチファブリックが示される。中間ステージ１３０内の唯一のクロスバー相互接続ネットワークのクロックスピードを２スピードアップすることと、第１および第２の内部リンクを２スピードアップすることを除いて、図４Ａのスイッチファブリック３０と同じである
【００５６】
図４Ｃは、一般的な対称スイッチファブリックを示す。中間ステージ１３０内の２個の共有メモリ相互接続ネットワークを使用することで２のスピードアップを提供する。図４Ｄは、一般的な対称スイッチファブリックを示す。これは、中間ステージ１３０内の唯一の共有メモリ相互接続ネットワークのクロックスピードを２スピードアップし、第１および第２の内部リンクを２スピードアップすることを使用することで、２のスピードアップを提供する。
【００５７】
図４Ｅは、一般的な対称スイッチファブリックを示す。中間ステージ１３０内の２個の３ステージクロス相互接続ネットワークを使用することで、２のスピードアップを提供する。図４Ｆは、一般的な対称スイッチファブリックを示す。中間ステージ１３０内の唯一の３ステージクロス相互接続ネットワークを２スピードアップさせることと、第１および第２の内部リンクを２スピードアップさせることを使用することで、２のスピードアップを提供する。
【００５８】
一般に、中間ステージ１３０内の相互接続ネットワークは、任意の相互接続ネットワーク、即ち、ハイパーキューブや、バッチャバニアン相互接続ネットワーク、任意の内部ノンブロッキング相互接続ネットワーク、またはネットワークのネットワークであってよい。一実施形態において、相互接続ネットワーク１３１および１３２は、２つの異種のネットワークのであってよい。例えば、相互接続ネットワーク１３１は、クロスバーネットワークであってよく、相互接続ネットワーク１３２は、共有メモリネットワークであってよい。本発明によると、中間ステージにおいて使用される相互接続ネットワークの種類とは無関係に、中間ステージ内の少なくとも２のスピードアップが、図１Ｂの調停およびスケジューリング方法４０を使用して、厳密にノンブロッキング方式でスイッチファブリックを動作させる。そして中間ステージ内の少なくとも１のスピードアップが、そのスイッチファブリックを再配置可能なノンブロッキング方式で動作させる。
【００５９】
スイッチファブリック内のスピードアップは、相互接続ネットワークの内部スピードアップに関係しないことに留意されたい。例えば、クロスバーネットワークおよび共有メモリネットワークは完全接続のトポロジーであり、何ら追加的な内部スピードアップなくても、内部的にノンブロッキングである。例えば、図１Ａのスイッチファブリック１０または図３Ｂのスイッチファブリック５０のいずれかにおける相互接続ネットワーク１３１−１３２は、クロスバーネットワークまたは共有メモリネットワークであり、ノンブロッキング方式で動作するために相互接続ネットワーク１３１−１３２のいずれかに必要となるスピードアップはない。しかしながら、相互接続ネットワーク１３１−１３２が３ステージクロスネットワークである場合、各３ステージクロスネットワークには、厳密にノンブロッキング方式で動作可能であるために、内部での２のスピードアップが必要となる。中間ステージ相互接続ネットワーク１３１−１３２が３ステージクロスネットワークであるスイッチファブリックにおいて、スイッチファブリックの２のスピードアップは、１３１および１３２のような２個の異なる３ステージクロスネットワークの形で提供される。加えて、各３ステージクロスネットワーク１３１および１３２は、それ自体が内部的に厳密にノンブロッキングであるために、さらに２のスピードアップが必要である。明らかに、スイッチファブリックのスピードアップは、相互接続ネットワークの内部のスピードアップとは異なる。
【００６０】
同様に、中間ステージ１３１および１３２内の相互接続ネットワークがハイパーキューブネットワークである場合、ある実施形態においてｄランクのハイパーキューブ（２ｄ個のノードを備える）において、それがノンブロッキングネットワークであるために、ｄの内部のスピードアップが必要である。本発明によると、中間ステージの相互接続ネットワーク１３１または１３２は、スイッチファブリックが図１Ｂの調停およびスケジューリング方法４０を使用して、中間ステージ内で２のスピードアップで、厳密にノンブロッキング方式で動作可能であり、また、中間ステージ内で少なくとも１のスピードアップで、再配置可能なノンブロッキング方式で動作可能であるために、任意の内部ノンブロッキング相互接続ネットワークであることができる。
【００６１】
図４Ｇを参照すると、中間ステージ相互接続ネットワーク１３１または１３２が図３Ｄのスイッチファブリック７０および図３Ｅのスイッチファブリック８０内にある一実施形態における、４×４ポート（２ランク）のハイパーキューブベース相互接続ネットワークの詳細図が示されている。４ノードハイパーキューブには４個のノード、即ち００、０１、１０および１１がある。ノード００は、ノード０１に双方向リンクＡで接続される。ノード０１は、ノード１１に双方向リンクＢで接続される。ノード１１は、ノード１０に双方向リンクＣで接続される。ノード１０は、ノード００に双方向リンクＤで接続される。４個のノードそれぞれは、スイッチファブリックの入力ポートおよび出力ポートに接続される。ノード００は、第１内部リンクＦＬ１と第２内部リンクＳＬ１に接続される。ノード０１は、第１内部リンクＦＬ２と第２内部リンクＳＬ１に接続される。ノード１０は、第１内部リンクＦＬ３と第２内部リンクＳＬ３に接続される。ノード１１は、第１内部リンクＦＬ４と第２内部リンクＳＬ４に接続される。図４Ｇに示すハイパーキューブネットワーク１３１または１３２が内部的にノンブロッキングであるために、一実施形態において、スイッチファブリックの入口リンク（または出口リンク）と同じレートで、あるいはハイパーキューブネットワークのスケジューリング体系に左右される幾らか要因のスピードアップによって、リンクＡ、Ｂ、Ｃ、Ｄを双方向に動作させる必要がある。本発明に従うと、ハイパーキューブが内部的にノンブロッキング方式で動作すること、スイッチファブリックが図１Ｂの調停およびスケジューリング方法４０を使用して、少なくとも２のスピードアップで厳密にノンブロッキング方式で動作可能であること、およびスイッチファブリックが中間ステージで少なくとも１のスピードアップで、再配置可能なノンブロッキング方式で動作可能であることが必要になる。
【００６２】
図４Ａ−４Ｆは、同数の第１内部リンクと第２内部リンクを示すが、対称スイッチファブリックの場合のように、本発明は非対称スイッチファブリックに拡張される。一般に、（ｒ１＊ｒ２）の非対称スイッチファブリックであって、その非対称スイッチファブリックは、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポートと、各出力ポートがｒ１個の出力キューを有するｒ２個の出力ポートと、ｓ個のサブネットワークを備えた、少なくとも
2007510376.tif 000007
のスピードアップを有する相互接続ネットワークとを備え、各サブネットワークは総数少なくともｒ１個の第１内部リンクに対する各入力ポートに接続される少なくとも１個の第１内部リンクを備え、各サブネットワークはさらに総数少なくともｒ２個の第２内部リンクに対する各出力ポートに接続される少なくとも１個の第２内部リンクを備える。その非対称スイッチファブリックは、ｒ１≦ｒ２のときに、スイッチングすべき各スイッチング時間において、多くともｒ２回のスイッチング時間だけ決定論的な方式で、かつパケットのセグメント化および再組立を要求することなく、多くともｒ１個のパケットをスケジューリングすることで、本発明による厳密にノンブロッキング方式で動作する。別の実施形態においては、スイッチファブリックは、ｒ２≦ｒ１のときに、スイッチングすべき各スイッチング時間において、多くともｒ１回のスイッチング時間だけ決定論的な方式で、かつパケットのセグメント化および再組立を要求することなく、多くともｒ２個のパケットをスケジューリングすることで、本発明による厳密にノンブロッキング方式で動作する。
【００６３】
そのような一般的な非対称スイッチファブリックはＶ（ｓ，ｒ１，ｒ２）として表される。一実施形態において、システムは調停に対して、相互接続ネットワークにおいて数学的に最小のスピードアップで一回のみの繰り返しを実行する。システムは１００％スループット、処理保存的、公正、それでいて決定論的に動作し、それによって出力ポートを決して輻輳させない。図１Ｂの調停およびスケジューリング方法４０は、Ｖ（ｓ，ｒ１，ｒ２）のスイッチファブリックにおいてパケットをスケジューリングするためにも使用される。
【００６４】
図１Ｂの調停およびスケジューリング方法４０は、一般的なＶ（ｓ，ｒ１，ｒ２）スイッチファブリックもノンブロッキング方式で動作させ、パケットは１００％スループット、処理保存的、公正な方式でスイッチングされる。スイッチファブリックのスイッチング時間は、柔軟な設計パラメータでもあり、各スイッチング時間において１バイトずつまたは数バイトずつパケットをスイッチングするよう設定されることもできる。さらに、本発明において説明したようにＳＡＲの必要もない。出力キューなしの実施形態において、パケットは入力ポート内で物理的にセグメント化され、出力ポートで再組立される必要がある。
【００６５】
同様に、一実施形態において、非対称スイッチファブリックＶ（ｓ，ｒ１，ｒ２）は、相互接続ネットワークにおいて、少なくとも
2007510376.tif 000008
のスピードアップで再配置可能なノンブロッキング方式で動作する。これは、ｒ１≦ｒ２のときに、スイッチングすべき各スイッチング時間において、多くともｒ２回のスイッチング時間だけ決定論的な方式で、かつパケットのセグメント化および再組立を要求することなく、多くともｒ１個のパケットをスケジューリングすることで動作する。別の実施形態において、非対称スイッチファブリックＶ（ｓ，ｒ１，ｒ２）は、相互接続ネットワークにおいて、少なくとも
2007510376.tif 000009
のスピードアップで再配置可能なノンブロッキング方式で動作する。これは、ｒ２≦ｒ１のときに、スイッチングすべき各スイッチング時間において、多くともｒ１回のスイッチング時間だけ決定論的な方式で、かつパケットのセグメント化および再組立を要求することなく、多くともｒ２個のパケットをスケジューリングすることで動作する。
【００６６】
非対称スイッチファブリックＶ（ｓ，ｒ１，ｒ２）であって、その非対称スイッチファブリックは、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポートと、ｒ２個の出力ポートと、ｓ個のサブネットワークを備えた、少なくとも
2007510376.tif 000010
のスピードアップを有する相互接続ネットワークとを備え、各サブネットワークは、少なくとも総数ｒ１個の第１内部リンクに対する各入力ポートに接続された、少なくとも１つの第１内部リンクを備え、各サブネットワークは、さらに少なくとも総数ｒ２個の第２内部リンクに対する各出力ポートに接続された、少なくとも１つの第２内部リンクを備える。その非対称スイッチファブリックは、本発明に従い、スイッチングすべき各スイッチング時間において、多くともｒ２回のスイッチング時間だけ決定論的な方式で、多くともｒ１個のパケットをスケジューリングし、かつパケットのセグメント化および再組立を要求することで、厳密にノンブロッキング方式で動作する。図１Ｂの調停およびスケジューリング方法４０は、出力キューを使用せずに、Ｖ（ｓ，ｒ１，ｒ２）スイッチファブリックにおいてパケットをスイッチングするためにも使用される。
【００６７】
非対称スイッチファブリックＶ（ｓ，ｒ１，ｒ２）であって、その非対称スイッチファブリックは、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポートと、ｒ２個の出力ポートと、ｓ個のサブネットワークを備えた、少なくとも
2007510376.tif 000011
のスピードアップを有する相互接続ネットワークとを備え、各サブネットワークは、少なくとも総数ｒ１個の第１内部リンクに対する各入力ポートと接続された少なくとも１つの第１内部リンクを備え、各サブネットワークは、さらに少なくとも総数ｒ２個の第２内部リンクに対する各出力ポートに接続された少なくとも１つの第２内部リンクを備える。その非対称スイッチファブリックは、本発明に従い、スイッチングすべき各スイッチング時間において、多くともｒ２回のスイッチング時間だけ決定論的な方式で、多くともｒ１個のパケットをスケジューリングし、かつパケットのセグメント化および再組立を要求することで、再配置可能なノンブロッキング方式で動作する。
【００６８】
出願人は、本発明で説明した全てのスイッチファブリックは、入力ポートから出力ポートへ、レートおよびレイテンシの保証を提供することを指摘している。エンドツーエンド保証帯域幅、即ち、任意の入力ポートから任意の出力ポートへの帯域幅が、表１に示す入力キューから出力キューへの割当に基づいて与えられる。保証された一定のレイテンシが、複数の入力ポートから任意の出力ポートへのパケットに与えられる。各入力ポートはその宛先出力ポート内の割当出力キューにパケットをスイッチングするため、ある入力ポートからのパケットは、同じ出力ポートにスイッチングする第２の入力ポートからの別のパケットを妨害せず、従って入力ポート全てからのパケットのレイテンシ保証を強制する。スイッチファブリックのスイッチング時間は、各フローにおけるパケットのレイテンシを決定し、さらに各パケット内のパケットセグメントのレイテンシも決定する。
【００６９】
図５Ａは、図１Ｂの調停およびスケジューリング方法４０のアクト４４の実装を示す。ｒ２個のパケットのスケジューリングがアクト４４で実行される。アクト４４Ａにおいて、スケジューリングすべきパケットがまだあるかどうかがチェックされる。スケジューリングすべきパケットがまだある場合、即ち、ｒ２個のパケット全てがスケジューリングされない場合、制御はアクト４４Ｂに移る。アクト４４Ｂにおいて、中間ステージ内の２個の相互接続ネットワークのうち１個を介するオープンパスが、ｒ個のスケジューリング時間を介して検索することで選択される。パケットは、アクト４４Ｃにおいて、選択されたパス、選択されたスケジューリング時間を介してスケジューリングされる。４４Ｄにおいて、選択された第１内部リンクと第２内部リンクは選択済とマーク付けされ、他のパケットはどれも、同じスケジューリング時間においてこれらのリンクを選択できない。その後、制御はアクト４４Ａに戻り、従ってアクト４４Ａ、４４Ｂ、４４Ｃ、および４４Ｄは、ループ内で実行されて各パケットをスケジューリングする。
【００７０】
図５Ｂは、図５Ａのアクト４４の一変形の低レベルフローチャートである。アクト４４Ａは、スケジューリングすべき新規パケット要求がある場合、制御をアクト４４Ｂに移す。アクト４４Ｂ１は新規パケット要求をｃに割り当てる。アクト４４Ｂ２において、sched_time_1がインデックス変数ｉに割り当てられる。その後、アクト４４Ｂ３はｉがスケジューリング時間ｒ以下であるかどうかをチェックする。結果が「イエス」ならば、制御はアクト４４Ｂ４に移る。アクト４４Ｂ４において、別のインデックス変数ｊが相互接続ネットワーク１に設定される。アクト４４Ｂ５はｊが相互接続ネットワーク１または２のいずれであるかどうかをチェックする。結果が「イエス」ならば制御はアクト４４Ｂ６に移る。アクト４４Ｂ６は、パケット要求ｃがスケジューリング時間ｉにおいて、相互接続ネットワークｊに対する利用可能な第１内部リンクを有しないかどうかをチェックする。結果が「ノー」の場合、アクト４４Ｂ７は、スケジューリング時間ｉにおいて相互接続ネットワークｊが、パケット要求ｃの宛先出力ポートに対する利用可能な第２内部リンクを有しないかどうかをチェックする。結果が「ノー」の場合、制御はアクト４４Ｃに移る。アクト４４Ｃにおいて、パケット要求ｃはスケジューリング時間ｉにおいて、相互接続ネットワークｊを介してスケジューリングされ、その後、アクト４４Ｄにおいて第１および第２の内部リンクが、スケジューリング時間ｉにおける相互接続ネットワークｊに対応して、使用済とマーク付けされる。その後、制御はアクト４４Ａに移る。アクト４４Ｂ６またはアクト４４Ｂ７のいずれかにおいて、結果が「イエス」の場合、制御はアクト４４Ｂ９に移り、ｊが１増加され、制御はアクト４４Ｂ５に移る。アクト４４Ｂ５において結果が「ノー」の場合、制御はアクト４４Ｂ１０に移る。アクト４４Ｂ１０はｉを１増加し、制御はアクト４４Ｂ３に移る。アクト４４Ｂ３の結果は、決して「ノー」にならず、これはｒ個のスケジューリング時間において、パケット要求ｃはスケジューリングされるよう保証されることを意味する。アクト４４Ｂは２個のループを備える。内部ループはアクト４４Ｂ５、４４Ｂ６、４４Ｂ７、および４４Ｂ９から成る。外部ループはアクト４４Ｂ３、４４Ｂ４、４４Ｂ５、４４Ｂ６、４４Ｂ７、４４Ｂ９、および４４Ｂ１０から成る。アクト４４は、全てのｒ２個のパケット要求がスケジューリングされるまで、全てのパケットに対して繰り返される。
【００７１】
以下の方法は、図５Ａのスケジューリング方法４４の一実装に対する擬似コードを示す。この擬似コードは、図４Ａ−４Ｆにおけるスイッチファブリック内の中間ステージ１３０の２のスピードアップ（２個の相互接続ネットワーク、またはクロックスピードおよびリンクスピードの２のスピードアップによる）を使用して、ｒ２個のパケットを厳密にノンブロッキング方式でスケジューリングする。
【００７２】
スケジューリング方法の擬似コード：
ステップ１：for スケジューリングすべき各パケット要求 do{
ステップ２： c=パケットスケジュール要求；
ステップ３： for i=shed_time_１ to sched_time_r do{
ステップ４：  for j=inter_conn_net_１ to inter_conn_net_２ do{
ステップ５：  if(cがjに対する利用可能な第１内部リンクを有さない) continue；
ステップ６：  elseif(jがcの宛先出力ポートに対する利用可能な第２内部リンクを有さない) continue；
ステップ７：  else{
スケジューリング時間iにおいて、相互接続ネットワークjを介してcをスケジューリング；
相互接続ネットワークjへ、およびそこから使用されたリンクを利用不可としてマークづけ；
}
}
}
}
【００７３】
ステップ１は、各パケットをスケジューリングするループを開始する。ステップ２は、現在のパケット要求を「ｃ」としてラベル付けする。ステップ３は、第２ループを開始し、全てのｒスケジューリング時間を通る。ステップ４は、第３ループを開始し、２個の相互接続ネットワークを通る。パケット要求ｃの入力ポートが、ステップ５において、スケジューリング時間ｉにおいて相互接続ネットワークｊに対して利用可能な第１内部リンクを有さない場合、制御はステップ４に移り、次の相互接続ネットワークをｉとして選択する。ステップ６は、パケット要求ｃの宛先出力ポートが、スケジューリング時間ｉにおける相互接続ネットワークｊから利用可能な第２内部リンクを有しないかどうかをチェックし、もしそうならば制御はステップ４に移り、次の相互接続ネットワークをｉとして選択する。ステップ７において、パケット要求ｃが、スケジューリング時間ｉにおける相互接続ネットワークｊを介してセットアップされる。スケジューリング時間ｉにおける相互接続ネットワークｊに対する第１および第２の内部リンクが、将来のパケット要求のために利用不可としてマーク付けされる。これらのステップは、利用可能な第１および第２の内部リンクが見つかるまで、全てのｒ回のスケジューリング時間において、全ての２個の相互接続ネットワークに対して繰り返される。本発明に従って、ｒ回のスケジューリング時間の１つにおける１個の相互接続ネットワークを常に発見することができ、それを通してパケット要求ｃがスケジューリングされる。スケジューリング方法を実行するステップの数がｓ＊ｒに比例すると理解するのは簡単である。ここで、ｓは２に等しいスピードアップであり、ｒはスケジューリング時間の回数で、従ってそのスケジューリング方法は時間計算量Ｏ（ｓ＊ｒ）である。
【００７４】
表３は、上記の擬似コードのステップ１−８が、ある特別な実装における図５Ｂに示した方法のフローチャートをどのように実装するかを示す。
【００７５】
【表３】
2007510376.tif 000012
【００７６】
厳密にノンブロッキングなスイッチファブリックのスケジューリングにおいて、入力キューから出力キューへのパケット要求をスケジューリングするため、相互接続ネットワークを介するパスを発見し、既にスケジューリングされたパケットのパスを阻害することなく要求を満足することが常に可能であり、１つ以上のそのようなパスが利用可能な場合、任意のそれらを残りのパケット要求のスケジューリングを気にすることなく選択できる。厳密にノンブロッキングなネットワークにおいて、スイッチハードウェアのコストは増加するが、パケットをスケジューリングするのに要求される時間は、再配置可能なノンブロッキングなスイッチファブリックと比較して減少する。中間ステージ内の２のスピードアップを有する厳密にノンブロッキングなスイッチファブリックの実施形態は、時間計算量Ｏ（ｓ＊ｒ）である図５Ａのスケジューリング方法４４を使用し、図１Ａのスイッチファブリック１０および図１Ｉのスイッチファブリック１６において示されている。
【００７７】
再配置可能なノンブロッキングなスイッチファブリックにおいて、スイッチハードウェアのコストは、パケットをスケジューリングするのに要求される時間の増加の代償として削減される。スケジューリング時間は、再配置可能なノンブロッキングネットワークにおいて増加する。なぜならば、新規パケットのスケジューリングに加えて、再配置を実装するために乱された、既にスケジューリングされたパケットのパスを再度スケジューリングする必要があるからである。この理由のため、新規パケットをスケジューリングするときは、既にスケジューリングされたパケットを再配置する必要性を最小化または排除するのが望ましい。再配置の必要性が排除されるとき、そのネットワークは、中間ステージ相互接続ネットワークの数およびスケジューリング方法に左右されて、厳密にノンブロッキングである。中間ステージにおいてスピードアップを使用しない再配置可能なノンブロッキングスイッチファブリックの一実施形態が、図１Ｎのスイッチファブリック１８において示されている。要求生成、許可発行、および承認の生成の調停は、スイッチファブリックが厳密にノンブロッキング方式で動作するか、または再配置可能なノンブロッキング方式で動作するか否かに関わらず、唯一の繰り返しで実行されることは留意されたい。
【００７８】
出願人は、出力キューにキューイングされたスイッチに関する２、３の考察を行っている。出願人は、出力キューにキューイングされたスイッチは、入力ポートで受信したパケットを即座に宛先出力キューに送信することで、出力ポートを輻輳させることを指摘する。例えば、ｒ＊ｒのＯＱスイッチにおいて、全ての入力ポートが同じ出力ポートに入る場合、出力ポートは、受信するように設計された出力ポートよりもｒ回多くパケットを受信する。出力ポートの輻輳は、以下の不必要な問題を生み出す。１）追加的なパケットの優先度付けおよび管理が出力ポート内で要求される、２）レート保証の実装が極度に困難、３）出力ポートから送信される各パケットのレートが減少する、４）出力ポートにおけるトラフィック輻輳を排除することが、入力ポート内でパケットをランダムに落とすことを要求する、５）これらの全ての要因が、追加的なトラフィック管理コスト、電力およびメモリの要求につながる。本質的に出力キューイングは、ファブリックを越えてパケットを転送することで、局所的にのみパケットスイッチングを解消するが、ネットワーク装置における１００％スループットでのトラフィックの決定論的なフローという目標は達成できない。
【００７９】
出願人はここで、ＶＯＱスイッチファブリック内の出力ポートを潜在的に輻輳させうる方法を説明する。図６Ａおよび図６Ｂは、スピードアップを完全に使用した、各スイッチング時間後の図１Ａのスイッチファブリック１０の状態を示す。即ち、中間ステージ内の相互接続ネットワークにおけるスピードアップを使用し、パケットにより出力ポートが送信可能なレートの２倍でパケットを送信する。図６Ａは、パケットＡ１、Ｄ１、Ｅ１、Ｆ１、Ｊ１、Ｋ１、Ｏ１およびＰ１が出力キューにスイッチングされる第１スイッチング時間後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＡ１は、クロスバーネットワーク１３１経由で、出力ポート１９１の出力キュー１８１にスイッチングされる。入力ポート１５１からのパケットＤ１は、クロスバーネットワーク１３２経由で、出力ポート１９４の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＥ１は、クロスバーネットワーク１３２経由で、出力ポート１９１の出力キュー１８２にスイッチングされる。入力ポート１５２からのパケットＦ１は、クロスバーネットワーク１３１経由で、出力ポート１９２の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＪ１は、クロスバーネットワーク１３２経由で、出力ポート１９２の出力キュー１８３にスイッチングされる。入力ポート１５３からのパケットＫ１は、クロスバーネットワーク１３１経由で、出力ポート１９３の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＰ１は、クロスバーネットワーク１３１経由で、出力ポート１９４の出力キュー１８４にスイッチングされる。入力ポート１５４からのパケットＯ１は、クロスバーネットワーク１３２経由で、出力ポート１９３の出力キュー１８４にスイッチングされる。明らかに、第１スイッチング時間において、各入力ポートから２個のパケットがスイッチングされ、各出力ポートは２個のパケットを受信する。
【００８０】
図６Ｂは、パケットＢ１、Ｃ１、Ｇ１、Ｈ１、Ｉ１、Ｌ１、Ｍ１およびＮ１が出力キューにスイッチングされる第２スイッチング時間後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのパケットＢ１は、クロスバーネットワーク１３１経由で、出力ポート１９２の出力キュー１８１にスイッチングされる。入力ポート１５１からのパケットＣ１は、クロスバーネットワーク１３２経由で、出力ポート１９３の出力キュー１８１にスイッチングされる。入力ポート１５２からのパケットＧ１は、クロスバーネットワーク１３１経由で、出力ポート１９３の出力キュー１８２にスイッチングされる。入力ポート１５２からのパケットＨ１は、クロスバーネットワーク１３２経由で、出力ポート１９４の出力キュー１８２にスイッチングされる。入力ポート１５３からのパケットＩ１は、クロスバーネットワーク１３２経由で、出力ポート１９１の出力キュー１８３にスイッチングされる。入力ポート１５３からのパケットＬ１は、クロスバーネットワーク１３１経由で、出力ポート１９４の出力キュー１８３にスイッチングされる。入力ポート１５４からのパケットＭ１は、クロスバーネットワーク１３１経由で、出力ポート１９１の出力キュー１８４にスイッチングされる。入力ポート１５４からのパケットＮ１は、クロスバーネットワーク１３２経由で、出力ポート１９２の出力キュー１８４にスイッチングされる。再び、第２スイッチング時間において、各入力ポートから２個のパケットがスイッチングされ、各出力ポートは２個のパケットを受信する。
【００８１】
しかしながら、出力ポートは、各スイッチング時間において１個のパケットを送信するのみであるといえる。さらに各入力ポートは、各スイッチング時間で１個のパケットのみを受信する。従って第３および第４スイッチング時間に対して、出力ポート内に十分な出力キュー領域がない場合、出力ポートは複数のパケットを受信できない。たとえ十分な領域がある場合でも、それは持続されることはできず、何らかの時点で出力キュー領域は満杯になり、出力ポートがクリアされるまで、入力ポートからのスイッチングは停止しなければならない。従って、スピードアップを完全に使用することは持続可能でなく、出力ポートにおける不必要な輻輳を生み出す。
【００８２】
さらに本発明に従って、スイッチファブリックがノンブロッキング方式で動作するために、中間ステージ１３０内で要求されるスピードアップの直接的な拡張が、パケットが出力ポートにスイッチングされる前に、追加された制御ビットの数によって比例的に調節される。例えば、１％という追加的な制御ビットが、入力ポートから出力ポートへスイッチングすべき、どのパケットまたはパケットセグメントにも追加される場合（これらの制御ビットは、入力ポートから出力ポートへのパケットをスイッチングするためだけに導入される、中間ステージ１３０において、スイッチファブリックのために要求されるスピードアップは、厳密にノンブロッキング方式で動作するためには２．０１であり、再配置可能なノンブロッキング方式で動作するためには１．０１である。
【００８３】
同様に本発明に従って、パケットがセグメント化されて出力ポートにスイッチングされるとき、最後のパケットセグメントはそのパケットセグメントと同じであっても、また同じでなくてよい。あるいはパケットのサイズがパケットセグメントのサイズの完全な倍数でない場合、スイッチファブリックのスループットは１００％未満である。最後のパケットセグメントがそのパケットセグメントのサイズより頻繁に小さい場合、中間ステージにおけるスピードアップは、システムが１００％スループットで動作するために比例的に増加する必要がある。
【００８４】
ノンブロッキングで決定論的スイッチファブリックに関する本発明は、任意の多数の入力キューに直接的に拡張できる。即ち、各入力ポート内の２個以上の入力キューは、宛先出力ポート内の２個以上の出力キューにスイッチングし、全ての入力ポート内の、異なるユニキャストフローまたはユニキャストマイクロフローのセットを保持する入力キューそれぞれは、レートおよびレイテンシ保証を有する１フローずつのＱｏＳを提供する。エンドツーエンド保証帯域幅は、即ち、入力ポートの異なる入力キューにおける、任意の宛先出力ポートへの複数のユニキャストフローに対して、提供することができる。さらに、保証された一定のレイテンシが、入力ポート内の複数の入力キューから任意の宛先出力ポートへのパケットフローに対して提供される。入力ポート内の各入力キューは異なるフローを保持するけれども、パケットを同じ宛先出力ポートにスイッチングするので、１個の入力キューからのより長いパケットは、同じ宛先出力ポートにスイッチングする同じ入力ポートの第２入力キューからの小さな別のパケットを妨害しない。従って入力ポートからのパケットフローのレイテンシ保証を強制する。ここで、スイッチファブリックのスイッチング時間は、各フローにおけるパケットのレイテンシを決定し、各パケットにおけるパケットセグメントのレイテンシも決定する。
【００８５】
入力キューから出力ポートへ別個にスイッチングされるフローの数を増加することで、エンドツーエンド保証帯域幅とレイテンシは、細粒度のフローに対して提供することもできる。さらに、各フローは独立して形成することもでき、必要であれば、オーバーサブスクリプション下の所望のフローから予測的にパケットをテールドロップすることと、サービスプロバイダを提供して、レートおよびレイテンシ保証を個別フローに提供し、従って追加的な収入機会を可能とすることにより、形成することもできる。
【００８６】
ここで説明した実施形態、実装、および例の多数の修正および適合化は、本開示内容を参照することで当業者には明らかであろう。
【００８７】
また、本発明で説明した実施形態は、並列コンピュータ、ビデオサーバ、ロードバランサのアプリケーション、およびグリッドコンピューティングアプリケーションにおいて直接的に有用である。さらに、本発明で説明した実施形態は、回線交換タイムスロットおよび、パケット交換されたパケットまたはセルの双方をスイッチングするために、ハイブリッドスイッチおよびルータにおいて直接的に有用である。
【００８８】
多数のそのような修正および適合化は、添付の請求項に包含されている。
【図面の簡単な説明】
【００８９】
【図１Ａ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、短いパケットを含む入力および出力ユニキャストキューと２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図１Ｂ】本発明に従って、入力ポートから出力ポートへパケットをスイッチングするために使用する、調停およびスケジューリング方法４０の高レベルフローチャートである。
【図１Ｃ】図１Ａのスイッチファブリック１０のスケジューリングにおける同様の３ステージネットワークの図である。
【図１Ｄ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図１Ａのスイッチファブリックの状態を示す図である。
【図１Ｅ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図１Ａのスイッチファブリックの状態を示す図である。
【図１Ｆ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図１Ａのスイッチファブリックの状態を示す図である。
【図１Ｇ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図１Ａのスイッチファブリックの状態を示す図である。
【図１Ｈ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図１Ａのスイッチファブリックの状態を示す図である。
【図１Ｉ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、長いパケットを含む入力および出力ユニキャストキューと２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図１Ｊ】本発明に従って、４回連続のファブリックスイッチングサイクル後の、パケットのセグメント化および再組立なしのノンブロッキングで決定論的パケットスイッチング後の、図１Ｉのスイッチファブリック１６の状態を示す図である。
【図１Ｋ】本発明に従って、４回連続のファブリックスイッチングサイクル後の、パケットのセグメント化および再組立なしのノンブロッキングで決定論的パケットスイッチング後の、図１Ｉのスイッチファブリック１６の状態を示す図である。
【図１Ｌ】本発明に従って、４回連続のファブリックスイッチングサイクル後の、パケットのセグメント化および再組立なしのノンブロッキングで決定論的パケットスイッチング後の、図１Ｉのスイッチファブリック１６の状態を示す図である。
【図１Ｍ】本発明に従って、４回連続のファブリックスイッチングサイクル後の、パケットのセグメント化および再組立なしのノンブロッキングで決定論的パケットスイッチング後の、図１Ｉのスイッチファブリック１６の状態を示す図である。
【図１Ｎ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、入力および出力ユニキャストキューを有し、スピードアップがない例示的な４×４ポートスイッチファブリックの図である。
【図２Ａ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、入力ユニキャストキューと２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図２Ｂ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す図である。
【図２Ｃ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す図である。
【図２Ｄ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す図である。
【図２Ｅ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す図である。
【図２Ｆ】本発明に従って、５回連続のスイッチング時間におけるノンブロッキングで決定論的パケットスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す図である。
【図３Ａ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図３Ｂ】本発明に従って、共有メモリベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図３Ｃ】本発明に従って、共有メモリベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図３Ｄ】本発明に従って、ハイパーキューブベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図３Ｅ】本発明に従って、ハイパーキューブベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する例示的な４×４ポートスイッチファブリックの図である。
【図４Ａ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｂ】本発明に従って、クロスバーベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｃ】本発明に従って、共有メモリベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｄ】本発明に従って、共有メモリベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｅ】本発明に従って、３ステージのクロスネットワークベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｆ】本発明に従って、３ステージのクロスネットワークベースの相互接続ネットワークにおける、入力および出力ユニキャストキューと、リンクスピードおよびクロックスピードにおいて２のスピードアップとを有する一般的なｒ＊ｒポートスイッチファブリックの図である。
【図４Ｇ】図３Ｄのスイッチファブリック７０および図３Ｅのスイッチファブリック８０内の中間ステージ相互接続ネットワーク１３１または１３２の１の実施形態における４×４ポート（ランク２）のハイパーキューブベースの相互接続ネットワークを詳細に示す図である。
【図５Ａ】図１Ｃの調停およびスケジューリング方法４０のアクト４４に対する中間レベルの実装を示す図である。
【図５Ｂ】図５Ａのアクト４４の一変形に対する低レベルフローチャートである。
【図６Ａ】２回連続のスイッチング時間における、スピードアップを最大に使用してパケットをスイッチングした後の、図１Ａのスイッチファブリック１０の状態を示す図である。
【図６Ｂ】２回連続のスイッチング時間における、スピードアップを最大に使用してパケットをスイッチングした後の、図１Ａのスイッチファブリック１０の状態を示す図である。
【図１Ａ】
2007510376.tif 000019
【図１Ｂ】
2007510376.tif 000020
【図１Ｃ】
2007510376.tif 000021
【図１Ｄ】
2007510376.tif 000022
【図１Ｅ】
2007510376.tif 000023
【図１Ｆ】
2007510376.tif 000024
【図１Ｇ】
2007510376.tif 000025
【図１Ｈ】
2007510376.tif 000026
【図１Ｉ】
2007510376.tif 000027
【図１Ｊ】
2007510376.tif 000028
【図１Ｋ】
2007510376.tif 000029
【図１Ｌ】
2007510376.tif 000030
【図１Ｍ】
2007510376.tif 000031
【図１Ｎ】
2007510376.tif 000032
【図２Ａ】
2007510376.tif 000033
【図２Ｂ】
2007510376.tif 000034
【図２Ｃ】
2007510376.tif 000035
【図２Ｄ】
2007510376.tif 000036
【図２Ｅ】
2007510376.tif 000037
【図２Ｆ】
2007510376.tif 000038
【図３Ａ】
2007510376.tif 000039
【図３Ｂ】
2007510376.tif 000040
【図３Ｃ】
2007510376.tif 000041
【図３Ｄ】
2007510376.tif 000042
【図３Ｅ】
2007510376.tif 000043
【図４Ａ】
2007510376.tif 000044
【図４Ｂ】
2007510376.tif 000045
【図４Ｃ】
2007510376.tif 000046
【図４Ｄ】
2007510376.tif 000047
【図４Ｅ】
2007510376.tif 000048
【図４Ｆ】
2007510376.tif 000049
【図４Ｇ】
2007510376.tif 000050
【図５Ａ】
2007510376.tif 000051
【図５Ｂ】
2007510376.tif 000052
【図６Ａ】
2007510376.tif 000053
【図６Ｂ】
2007510376.tif 000054
【国際調査報告】
2007510376.tif 000055