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