(57)【要約】【課題】【解決手段】相互接続ネットワークを通じて、マルチキャストパケットをスケジューリングするシステムであって、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポート、各出力ポートがｒ１個の出力キューを有するｒ２個の出力ポートを備え、相互接続ネットワークは、ｓ個のサブネットワークを用いて、少なくともｓ倍のスピードアップを有し、各サブネットワークは、全体で少なくともｒ１個の各入力ポートに接続された少なくとも１つの第１内部リンクを備え、さらに、各サブネットワークは、全体で少なくともｒ２である各出力ポートに接続された少なくとも１つの第２内部リンクを備え、ｒ１⊆ｒ２の場合には、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時において多くともｒ１個のパケットを、また、ｒ２⊆ｒ１であるときは多くともｒ１回のスイッチングにおけるスイッチングすべき各スイッチング時において、多くともｒ２個のパケットを、決定論的方式で且つパケットのセグメント化と再組立の必要がなくスケジューリングすることにより、厳密なノンブロッキング方式で作動する。スケジューリングは、各マルチキャストパケットが、２つを超えない相互接続ネットワークを介し、２回を超えないスイッチング回数で、ファンアウト分割されるように実行される。このシステムは、１００％スループット、作業節約的、公正、及びさらに決定論的方式で作動し、それにより、出力ポートは決して輻輳しない。このシステムは、調停に１度だけ繰り返しを、相互接続ネットワークにおける数学的に最小限のスピードアップを用いて、実行される。このシステムは、並べ替えの問題、相互接続ネットワークにおけるパケットの内部ブロッキングを決して伴わないので、真にカットスルー且つファンアウトされる方式で作動する。一実施例において、スピードアップは、１つのみのサブネットワークを用い、サブネットワークを介して３倍のスピードアップを用いて実施される。このシステムは、パケットの並び替えを全く発行せず、相互接続ネットワークに内部バッファがないため、真にカットスルーかつ分散化した方法で作動する。一実施例では、スピードアップは、相互接続ネットワークを３倍のスイッチング速度で通り、相互接続ネットワーク１つだけに実装される。 他の実施例では、システムは、相互接続ネットワークを少なくとも２倍スピードアップした再配置可能なノンブロッキング方式で作動する。入力ポートの数ｒ１が出力ポートのｒ２数に等しく、ｒ１＝ｒ２＝ｒであるときは、相互接続ネットワークは、少なくとも３倍のスピードアップを有し、各スイッチングで多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時において多くともｒ個のパケットをスケジューリングすることによって、本発明による厳密にノンブロッキングで決定論的方式で作動する。また、相互接続ネットワークを少なくとも２倍スピードアップし、システムは、再配置可能なノンブロッキングで決定論的方式で作動する。システムはさらに、入力ポートから出力ポートへのマルチキャストパケットに、エンドツーエンド保証帯域幅および待ち時間を提供する。全実施例で、相互接続ネットワークは、クロスバーネットワーク、共���メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、または任意の内部ノンブロッキング相互接続ネットワーク、または複数のネットワークのネットワークでもよい。【選択図】図１Ｈ
2007510379.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ポートおよび複数の出力ポートを有する相互接続ネットワークを通じて、前記各パケットが、指定出力ポートを有するマルチキャストパケットをスケジューリングするシステムであって、
前記各入力ポートにおける複数の入力キューであって、前記マルチキャストパケットを有する入力キューと、
前記各入力ポートが、前記指定出力ポートに対し、多くとも前記各入力ポートにおける入力キューの数と同数の前記マルチキャストパケットのサービスを要求する手段と、
前記各出力ポートが、複数の要求を許可するための手段と
前記各入力ポートが、多くとも、前記入力キューの数と同数の許可を承認するための手段と、
多くとも、入力キューの数に等しい数の前記マルチキャストパケットを、承認された許可を有する前記各入力ポートから、前記承認された許可に関連付けられた前記各出力ポートに対し、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによって、スケジューリングする手段とを含むことを特徴とするシステム。
【請求項２】
前記各出力ポートにあり、前記相互接続ネットワークを通じて前記マルチキャストパケットを受信する複数の出力キューと、
前記各出力ポートが、多くとも前記出力キューと同数の要求を許可する手段と、
多くとも入力キューの数と同数の前記マルチキャストパケットを、承認された許可およびを出力キューの数と同数の前記マルチキャストパケット有する前記各入力ポートから、前記承認された許可に関連付けられる前記各出力ポート対して、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングする手段と
をさらに含むことを特徴とする、請求項１に記載のシステム。
【請求項３】
前記相互接続ネットワークは、ノンブロッキング相互接続ネットワークであることを特徴とする、請求項１に記載のシステム。
【請求項４】
前記ノンブロッキング相互接続ネットワークは、少なくとも３倍のスピードアップを含むことを特徴とする、請求項３に記載のシステム。
【請求項５】
前記スピードアップは、
並列性の手段、即ち、前記相互接続ネットワークを、少なくとも３回物理的に複製し、前記各入力ポート、および前記各出力ポートからの別個のリンクにより接続する手段、または
前記入力ポートと前記相互接続ネットワークの間、および前記出力ポートと前記相互接続ネットワークとの間のリンク帯域幅において、また前記相互接続ネットワークのクロック速度においても、少なくとも３倍スピードアップする手段、により実現することを特徴とする、請求項４に記載のシステム。
【請求項６】
さらに、前記ノンブロッキング相互接続ネットワークを通じて、マルチキャストパケットの経路を、別のマルチキャストパケットのために既に選択された経路を決して変更しないことによって、常に選択可能であることを特徴とする請求項４に記載のシステムであって、
以後、前記相互接続ネットワークを、「厳密なノンブロッキングネットワーク」と称する前記システム。
【請求項７】
前記ノンブロッキング相互接続ネットワークは、少なくとも２倍のスピードアップを含むことを特徴とする、請求項３に記載のシステム。
【請求項８】
前記スピードアップを、
並列性の手段、即ち、前記相互接続ネットワークを、少なくとも２回物理的に複製し、前記各入力ポート、および前記各出力ポートからの別個のリンクによって接続する手段、または
前記入力ポートと前記相互接続ネットワークの間、および前記出力ポートと前記相互接続ネットワークとの間のリンク帯域幅において、また前記相互接続ネットワークのクロック速度においても、少なくとも２倍スピードアップする手段により実現することを特徴とする、請求項７に記載のシステム。
【請求項９】
さらに、前記ノンブロッキング相互接続ネットワークを通じて、マルチキャストパケットの経路を、必要なときは、別のマルチキャストパケットのために既に選択した経路を変更することによって、常に選択可能であることを特徴とする、請求項７に記載のシステムであって、
以後、前記相互接続ネットワークを、「再配置可能なノンブロッキングネットワーク」と称する前記システム。
【請求項１０】
既にスケジューリングされた前記パケットのスケジュールを保持する前記スケジューリング手段に結合されたメモリを、さらに含むことを特徴とする、請求項１に記載のシステム。
【請求項１１】
既にスケジューリングされた前記パケットのスケジュールを保持する前記スケジューリング手段に結合されたメモリを、さらに含むことを特徴とする、請求項２に記載のシステム。
【請求項１２】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、前記入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする、請求項１に記載のシステム。
【請求項１３】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、前記入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする、請求項２に記載のシステム。
【請求項１４】
前記パケットは、実質的に同一サイズであることを特徴とする、請求項１に記載のシステム。
【請求項１５】
前記入力ポートにおいて先頭ブロッキングが、ユニキャストパケットおよびマルチキャストパケットの双方に関して完全に削除されることを特徴とする、請求項１に記載のシステム。
【請求項１６】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項１に記載のシステム。
【請求項１７】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項２に記載のシステム。
【請求項１８】
前記スケジューリング手段は、多くとも１つのパケットを１回のスイッチングで、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートに対して、スケジューリングすることを特徴とする、請求項１に記載のシステム。
【請求項１９】
前記スケジューリング手段は、多くとも１つのパケットを１回のスイッチングで、承認された許可および多くとも１つのパケットを有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対して、スケジューリングすることを特徴とする、請求項２に記載のシステム。
【請求項２０】
前記各出力ポートは、前記パケットが少なくとも１つある限り、１回のスイッチングで、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するよう作動することを特徴とする、請求項１に記載のシステムであって、
以後、「作業節約システム」と称する前記システム。
【請求項２１】
前記各出力ポートは、前記パケットが少なくとも１つある限り、１回のスイッチングで、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するよう作動することを特徴とする、請求項２に記載のシステムであって、
以後、「作業節約システム」と称する前記システム。
【請求項２２】
前記各出力ポートは、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、１回のスイッチングで、多くとも１つのパケットを受信するよう作動可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項１に記載のシステム。
【請求項２３】
前記各出力ポートは、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、１回のスイッチングで、多くとも１つのパケットを受信するよう作動可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項２に記載のシステム。
【請求項２４】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介して同一経路で前記入力ポートに受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット並べ替えの問題が生じないように作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与える、ことを特徴とする、請求項１に記載のシステム。
【請求項２５】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介して前記入力ポートに受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット並べ替えの問題が生じないように作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項２に記載のシステム。
【請求項２６】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項１に記載のシステムであって、
以後、「公正なシステム」と称する前記システム。
【請求項２７】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項２に記載のシステムであって、
以後、「公正なシステム」と称する前記システム。
【請求項２８】
前記相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、または任意の内部ノンブロッキング相互接続ネットワーク、または複数のネットワークのネットワークであることを特徴とする、請求項１に記載のシステム。
【請求項２９】
前記システムは、１００％スループットで作動することを特徴とする請求項１に記載のシステム。
【請求項３０】
前記システムは、１００％スループットで作動することを特徴とする請求項２に記載のシステム。
【請求項３１】
いずれの入力ポートからも、任意の数の出力ポートへのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項１に記載のシステム。
【請求項３２】
いずれの入力ポートからも、任意の数の出力ポートへのエンドツーエンド保証帯域幅を提供することを特徴とする請求項２に記載のシステム。
【請求項３３】
複数の入力ポートから任意の出力ポートへのパケットの保証された一定の待ち時間を提供することを特徴とする、請求項１に記載のシステム。
【請求項３４】
複数の入力ポートから任意の出力ポートへのパケットの保証された一定の待ち時間を提供することを特徴とする、請求項２に記載のシステム。
【請求項３５】
前記システムは、前記相互接続ネットワークの内部バッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする、請求項１に記載のシステム。
【請求項３６】
前記システムは、前記相互接続ネットワークの内部バッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする請求項２に記載のシステム。
【請求項３７】
複数の入力ポートと複数の出力ポートとを有する相互接続ネットワークを介し、マルチキャストパケットをスケジューリングする前記方法であって、前記各入力ポートは、複数のキューを含み、前記パケットは、それぞれ少なくとも１つの指定出力ポートを有する前記方法において、
多くとも前記各入力ポートにおける入力キューの数と同数の前記マルチキャストパケットのための前記指定出力ポートから前記各入力ポートに対してサービスを要求するステップと、
前記各出力ポートに対して、複数の要求を許可するステップと、
多くとも前記入力キューの数と同数の許可を、前記各入力ポートに対して承認するステップと、
多くとも入力キューの数と同数の前記マルチキャストパケットを、承認された許可を有する前記入力ポートから、前記承認された許可に関連付けられる前記各出力ポート対して、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングするステップとの各ステップを含むことを特徴とする方法。
【請求項３８】
前記各出力ポートに複数の出力キューを備え、
前記各出力ポートが多くとも前記出力キューの数と同数の要求を許可するステップと、
多くとも入力キューの数と同数の前記マルチキャストパケットを、承認された許可および出力キューの数と同数の前記マルチキャストパケットを有する前記入力ポートから、前記承認された許可に関連付けられる前記各出力ポート対して、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングするステップとの各ステップをさらに含むことを特徴とする、請求項３７に記載の方法。
【請求項３９】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、入力ポートによる前記許可の承認とは、１度の繰り返しのみで実行されることを特徴とする、請求項３７に記載の方法。
【請求項４０】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、入力ポートによる前記許可の承認とは、１度の繰り返しのみで実行されることを特徴とする、請求項３８に記載の方法。
【請求項４１】
前記パケットは、実質的に同一サイズであることを特徴とする、請求項３７に記載の方法。
【請求項４２】
前記入力ポートにおいて先頭ブロッキングが完全に削除されることを特徴とする、請求項３７に記載の方法。
【請求項４３】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項３７に記載の方法。
【請求項４４】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項３８に記載の方法。
【請求項４５】
前記スケジューリングは、多くとも１つのパケットを１回のスイッチングで、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力ポートに対してスケジューリングすることを特徴とする、請求項３７に記載の方法。
【請求項４６】
前記スケジューリングは、多くとも１つのパケットを１回のスイッチングで、承認された許可と多くとも１つのパケットを有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対してスケジューリングすることを特徴とする、請求項３８に記載のシステム。
【請求項４７】
前記各出力ポートは、１回のスイッチングで、少なくとも前記１つのパケットがある限り、少なくとも１つのパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項３７に記載の方法。
【請求項４８】
前記各出力ポートは、１回のスイッチングで、少なくとも前記１つのパケットがある限り、少なくとも１つのパケットを、その出力ポートを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項３８に記載の方法。
【請求項４９】
前記各出力ポートは、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、１回のスイッチングで多くとも１つのパケットを受信するよう作動可能であり、
それにより、相互接続ネットワークにおけるスピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項３７に記載の方法。
【請求項５０】
前記各出力ポートは、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、１回のスイッチングで多くとも１つのパケットを受信するよう作動可能であり、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項３８に記載の方法。
【請求項５１】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介して同一経路で前記入力ポートに受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット並べ替えの問題が生じないよう作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項３７に記載の方法。
【請求項５２】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介して前記入力ポートに受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット並べ替えの問題が生じないように作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項３８に記載の方法。
【請求項５３】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項３７に記載の方法。
【請求項５４】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項３８に記載方法。
【請求項５５】
前記方法は、１００％スループットでスケジューリングすることを特徴とする、請求項３７に記載の方法。
【請求項５６】
前記方法は、１００％スループットでスケジューリングすることを特徴とする、請求項３８に記載の方法。
【請求項５７】
前記方法は、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項３７に記載の方法。
【請求項５８】
前記方法は、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項３８に記載の方法。
【請求項５９】
複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供することを特徴とする、請求項３７に記載の方法。
【請求項６０】
複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供することを特徴とする、請求項３８に記載の方法。
【請求項６１】
マルチキャストパケットを、相互接続ネットワークを通じて、スケジューリングするシステムであって、
前記各パケットが指定出力ポートを有するｒ１個の入力ポートおよびｒ２個の出力ポートと、
前記ｒ１個の各入力ポートにある、前記パケットを含むｒ２個の入力キューと、
ｓ≧１個のサブネットワークを含む前記相互接続ネットワークであって、各サブネットワークは、全体でｒ１個の第１内部リンクのために各入力ポートに接続される、少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、全体でｒ２個の第２内部リンクのために各出力ポートに接続される、少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備えた前記相互接続ネットワークと、
前記各入力ポートが、その各入力ポートからの、多くともｒ２個の前記マルチキャストパケットに対し、前記指定出力ポートからのサービスを要求する手段と、
前記各出力ポートが、複数の要求を許可する手段と、
前記各入力ポートが、多くともｒ２個のパケットの許可を承認する手段と、
多くともｒ１個の承認された許可を有する前記マルチキャストパケットを、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対し、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングする手段とを備えたことを特徴とするシステム。
【請求項６２】
前記ｒ２個の各出力ポートにあるｒ１個の出力キューであって、前記相互接続ネットワークを通じてマルチキャストパケットを受信する前記出力キューと、
ｓ≧１個のサブネットワークを備え、各サブネットワークは、各入力ポートに対し全体で少なくともｒ１個の第１内部リンクのための接続される少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、各出力ポートに対し全体で少なくともｒ２個の第２内部リンクのために接続される少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備えた前記相互接続ネットワークと、
前記各出力ポートが、多くともｒ１個のパケットを許可する手段と、
ｒ１≦ｒ２であるときは、多くともｒ１個の承認された許可を有する前記マルチキャストパケットを、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時において、ｒ２≦ｒ１であるときは、多くともｒ２個の承認された許可を有する前記マルチキャストパケットを、多くともｒ１回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対し、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングする手段とをさらに備えたことを特徴とする、請求項６１に記載のシステム。
【請求項６３】
前記相互接続ネットワークは、ノンブロッキング相互接続ネットワークであることを特徴とする、請求項６１に記載のシステム。
【請求項６４】
サブネットワークは、
2007510379.tif 000016
個であり、
さらに、前記ノンブロッキング相互接続ネットワークを通じて、別のマルチキャストパケットに対して、既に選択された経路を決して変更しないことにより、マルチキャストパケットに対し、経路が常に選択可能であることを特徴とする、請求項６３に記載のシステムであり、
以後、前記相互接続ネットワークを「厳密なノンブロッキングネットワーク」と称する前記システム。
【請求項６５】
サブネットワークは、ｓ≧１個であり、
前記第１内部リンクと前記第２内部リンクとの双方が、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも３倍速く作動することと、
前記サブネットワークが、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも３倍速く作動することと、
さらに、前記ノンブロッキング相互接続ネットワークを介して、別のマルチキャストパケットに対して、既に選択された経路を決して変更しないことにより、マルチキャストパケットに対し、経路が常に選択可能であることを特徴とする、請求項６３に記載のシステムであり、
以後、前記相互接続ネットワークを「厳密なノンブロッキングネットワーク」と称する前記システム。
【請求項６６】
サブネットワークは、
2007510379.tif 000017
個であり、
さらに、前記ノンブロッキング相互接続ネットワークを通じて、別のマルチキャストパケットに対して既に選択された経路を、必要であれば変更することにより、マルチキャストパケットに対し経路が常に選択可能であることを特徴とする、請求項６３に記載のシステムであり、
以後、前記相互接続ネットワークを「再配置可能なノンブロッキングネットワーク」と称する前記システム。
【請求項６７】
サブネットワークは、ｓ≧１個であり、
前記第１内部リンクと前記第２内部リンクとの双方が、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも２倍速く作動することと、
前記サブネットワークが、前記入力キューにおいて受信される各パケットのピークレートより、少なくとも２倍速く作動することと、
さらに、前記ノンブロッキングな相互接続ネットワークを介して、別のマルチキャストパケットのため既に選択された経路を、必要であれば変更することにより、マルチキャストパケットに対し経路が常に選択可能であることを特徴とする、請求項６３に記載のシステムであって、
以後、前記相互接続ネットワークを「厳密なノンブロッキングネットワーク」と称する前記システム。
【請求項６８】
前記スケジューリングの手段に結合されるメモリをさらに含み、既にスケジューリングされた前記パケットを保持することを特徴とする、請求項６１に記載のシステム。
【請求項６９】
前記スケジューリングの手段に結合されるメモリをさらに含み、既にスケジューリングされた前記パケットを保持することを特徴とする、請求項６２に記載のシステム。
【請求項７０】
調停、即ち、前記入力ポートによるサービスの要求と、前記出力ポートによる要求の許可と、前記入力ポートによる許可の承認とは、１度の繰り返しのみで実行されることを特徴とする、請求項６１に記載のシステム。
【請求項７１】
調停、即ち、前記入力ポートによるサービスの要求と、前記出力ポートによる要求の許可と、前記入力ポートによる許可の承認とは、１度の繰り返しのみで実行されることを特徴とする、請求項６２に記載のシステム。
【請求項７２】
ｒ１＝ｒ２＝ｒであり、
前記スケジューリングのための手段が、多くともｒ個のパケットを、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時において、許可を承認されて前記許可に結合する前記各出力ポートに対してスケジューリングすることを特徴とする、請求項６１に記載のシステム。
【請求項７３】
ｒ１＝ｒ２＝ｒであり、
前記スケジューリングの手段が、多くともｒ個の承認された許可を有するパケットを、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対し、スケジューリングすることを特徴とする、請求項６２に記載のシステム。
【請求項７４】
前記パケットは、実質的に同一サイズであることを特徴とする、請求項６１に記載のシステム。
【請求項７５】
前記入力ポートにおいて先頭ブロッキングが完全に削除されることを特徴とする、請求項６１に記載のシステム。
【請求項７６】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項６１に記載のシステム。
【請求項７７】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項６２に記載のシステム。
【請求項７８】
前記スケジューリング手段は、多くとも１つのパケットを、１回のスイッチングにより、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対しスケジューリングすることを特徴とする、請求項６１に記載のシステム。
【請求項７９】
前記スケジューリング手段は、多くとも１つのパケットを、１回のスイッチングにより、承認された許可および多くとも１つのパケットを有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対しスケジューリングすることを特徴とする、請求項６２に記載のシステム。
【請求項８０】
前記各出力ポートは、１回のスイッチングにより、少なくとも前記１つのパケットがある限り、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項６１に記載のシステムであって、
以後、「作業節約システム」と称する前記システム。
【請求項８１】
前記各出力ポートは、１回のスイッチングにより、少なくとも前記１つのパケットがある限り、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項６２に記載のシステムであって、
以後、「作業節約システム」と称する前記システム。
【請求項８２】
前記各出力ポートは、１回のスイッチングにより、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、多くとも１つのパケットを受信するように作動し、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項６１に記載のシステム。
【請求項８３】
前記各出力ポートは、１回のスイッチングにより、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、多くとも１つのパケットを受信するように作動し、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用され、前記出力ポートは決して輻輳しないことを特徴とする、請求項６２に記載のシステム。
【請求項８４】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを介して同一経路で前記入力ポートに受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット並べ替えの問題が生じないよう作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項６１に記載のシステム。
【請求項８５】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを通じて前記入力ポートに受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット並べ替えの問題が生じないように作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項６２に記載のシステム。
【請求項８６】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項６１に記載のシステムであって、
以後、「公正なシステム」と称する前記システム。
【請求項８７】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある入力キューの前記の数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項６２に記載のシステムであって、
以後、「公正なシステム」と称する前記システム。
【請求項８８】
前記相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、ハイパーキューブネットワーク、又は任意の内部ノンブロッキング相互接続ネットワーク、又はネットワークのネットワークであることを特徴とする、請求項６１に記載のシステム。
【請求項８９】
前記システムは、１００％スループットで作動することを特徴とする、請求項６１に記載のシステム。
【請求項９０】
前記システムは、１００％スループットで作動することを特徴とする、請求項６２に記載のシステム。
【請求項９１】
前記システムは、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項６１に記載のシステム。
【請求項９２】
前記システムは、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項６２に記載のシステム。
【請求項９３】
前記システムは、複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供することを特徴とする、請求項６１に記載のシステム。
【請求項９４】
前記システムは、複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供することを特徴とする、請求項６２に記載のシステム。
【請求項９５】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする、請求項６１に記載のシステム。
【請求項９６】
前記システムは、前記相互接続ネットワーク内にバッファを必要とせず、従ってカットスルーアーキテクチャであることを特徴とする、請求項６２に記載のシステム。
【請求項９７】
相互接続ネットワークを通じてマルチキャストパケットをスケジューリングする方法であって、
前記各パケットが少なくとも１つの宛先出力ポートを有するｒ１個の入力ポートおよびｒ２個の出力ポートと、
前記ｒ１個の各入力ポートにある、前記パケットを備えたｒ２個の入力キューと、
ｓ≧１個のサブネットワークを備えた前記相互接続ネットワークであって、各サブネットワークは、各入力ポート対し全体で少なくともｒ１個の第１内部リンクのため接続される、少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、各出力ポートに対し全体で少なくともｒ２個の第２内部リンクのため接続される、少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備えた相互接続ネットワークと、を有し、前記方法は、
前記各入力ポートに対する、前記指定出力ポートからの、多くともｒ２個の前記マルチキャストパケットのサービスを要求するステップと、
前記各出力ポートに対する、複数の要求を許可するステップと、
前記各入力ポートに対する、多くともｒ２個のパケットに許可を承認するステップと、
多くともｒ１個の承認された許可を有する前記マルチキャストパケットを、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対し、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することによりスケジューリングするステップとの各ステップを含むことを特徴とする方法。
【請求項９８】
ｒ２個の前記各出力ポートにあるｒ１個の出力キューであって、前記相互接続ネットワークを通じてマルチキャストパケットを受信する前記出力キューと、
ｓ≧１個のサブネットワークを備えた前記相互接続ネットワークであって、各サブネットワークは、各入力ポート対し全体で少なくともｒ１個の第１内部リンクのため接続される、少なくとも１つのリンク（以後、「第１内部リンク」と称する）を備え、各サブネットワークはさらに、各出力ポートに対し全体で少なくともｒ２個の第２内部リンクのため接続される、少なくとも１つのリンク（以後、「第２内部リンク」と称する）を備えた相互接続ネットワークと、
前記各出力ポートに対し、多くともｒ１個のパケットを許可するステップと、
ｒ１≦ｒ２であるときは多くともｒ１個の、承認された許可を有する前記マルチキャストパケットを、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時において、ｒ２≦ｒ１であるときは多くともｒ２個の、承認された許可を有する前記マルチキャストパケットを、多くともｒ１回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記出力ポートに対し、前記入力ポート内の前記各マルチキャストパケットを、多くとも２回ファンアウト分割することにより、スケジューリングするステップとの各ステップをさらに備えたことを特徴とする請求項９７に記載の方法。
【請求項９９】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、前記入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする、請求項９７に記載の方法。
【請求項１００】
調停、即ち、前記入力ポートによる前記サービスの要求と、前記出力ポートによる前記要求の許可と、前記入力ポートによる前記許可の承認とを、１度の繰り返しのみで実行することを特徴とする、請求項９８に記載の方法。
【請求項１０１】
ｒ１＝ｒ２＝ｒであり、
前記スケジューリングは、承認された許可を有する多くともｒ個のパケットを、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対してスケジューリングすることを特徴とする、請求項９７に記載の方法。
【請求項１０２】
ｒ１＝ｒ２＝ｒであり、
前記スケジューリングは、承認された許可を有する多くともｒ個のパケットを、多くともｒ回のスイッチングにおけるスイッチングすべき各スイッチング時において、前記承認された許可に関連付けられる前記各出力ポートに対してスケジューリングすることを特徴とする、請求項９８に記載の方法。
【請求項１０３】
前記パケットは、実質的に同一サイズであることを特徴とする、請求項９７に記載の方法。
【請求項１０４】
前記入力ポートにおける先頭ブロッキングは、ユニキャストパケットおよびマルチキャストパケットの双方について完全に削除されることを特徴とする、請求項９７に記載の方法。
【請求項１０５】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項９７に記載の方法。
【請求項１０６】
前記入力ポートにある前記入力キューのいくつかは、ユニキャストパケットのみを含むことを特徴とする、請求項９８に記載の方法。
【請求項１０７】
前記スケジューリングは、多くとも１つのパケットを１回のスイッチングにより、承認された許可を有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対して、スケジューリングすることを特徴とする、請求項９７に記載の方法。
【請求項１０８】
前記スケジューリングは、多くとも１つのパケットを１回のスイッチングにより、承認された許可および多くとも１つのパケットを有する前記各入力キューから、前記承認された許可に関連付けられる前記各出力キューに対して、スケジューリングすることを特徴とする、請求項９８に記載の方法。
【請求項１０９】
前記各出力ポートは、１回のスイッチングにより、少なくとも１つの前記パケットがある限り、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項９７に記載の方法。
【請求項１１０】
前記各出力ポートは、１回のスイッチングにより、少なくとも１つの前記パケットがある限り、少なくとも１つのパケットを、それを宛先とする前記入力キューのいずれか１つから受信するように作動することを特徴とする、請求項９８に記載の方法。
【請求項１１１】
前記各出力ポートは、１回のスイッチングにより、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、多くとも１つのパケットを受信するように作動し、
それにより、相互接続ネットワークにおける前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用し、前記出力ポートは決して輻輳しないことを特徴とする、請求項９７に記載の方法。
【請求項１１２】
前記各出力ポートは、１回のスイッチングにより、１つを超えるパケットがそれを宛先としていても、前記相互接続ネットワークにおける前記スピードアップに関係なく、多くとも１つのパケットを受信するように作動し、
それにより、前記スピードアップは、前記相互接続ネットワークを決定論的方式で作動させることのみに利用し、前記出力ポートは決して輻輳しないことを特徴とする、請求項９８に記載の方法。
【請求項１１３】
前記入力キューの１つからのパケットは、それらが前記相互接続ネットワークを通じて同一経路で前記入力ポートに受信されるのと同一順序で、宛先出力ポートに対し常に決定論的にスイッチングされ、決してパケット並べ替えの問題が生じないよう作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、ことを特徴とする請求項９７に記載の方法。
【請求項１１４】
前記入力キューのうち１つからのパケットは、それらが前記相互接続ネットワークを介して前記入力ポートに受信されるのと同一順序で、宛先出力ポート内の前記出力キューの１つに対し、常に決定論的にスイッチングされ、前記入力ポート内の前記パケットのセグメント化も、前記出力ポート内の前記パケットの再組立も必要とせず、決してパケット並べ替えの問題が生じないように作動し、
それにより、スイッチング回数は設計時における変数となり、複数のバイトが各スイッチング時にスイッチングされるようにスイッチング回数を選択する余地を与えることを特徴とする、請求項９８に記載の方法。
【請求項１１５】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある前記入力キューの数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項９７に記載の方法。
【請求項１１６】
前記各入力キューの先頭にある前記パケットは、前記各入力ポートにある前記入力キューの数と同数のスイッチング回数を超えては保持されないよう作動することを特徴とする、請求項９８に記載の方法。
【請求項１１７】
前記方法は、前記パケットを１００％スループットでスケジューリングすることを特徴とする、請求項９７に記載の方法。
【請求項１１８】
前記方法は、前記パケットを１００％スループットでスケジューリングすることを特徴とする、請求項９８に記載の方法。
【請求項１１９】
前記方法は、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項９７に記載の方法。
【請求項１２０】
前記方法は、いずれの入力ポートからも、任意の数の出力ポートまでのエンドツーエンド保証帯域幅を提供することを特徴とする、請求項９８に記載の方法。
【請求項１２１】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供するように作動することを特徴とする、請求項９７に記載の方法。
【請求項１２２】
前記方法は、複数の入力ポートから任意の出力ポートまでのパケットの保証待ち時間を提供するように作動することを特徴とする、請求項９８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願に対する相互参照
本出願は、２００３年１０月３０日提出の米国仮特許出願番号６０／５１６，２６５号に関連するものであり、優先権を主張する。本出願は現出願と同一出願人に譲渡され、同時に提出するVenkat Kondaによる「NONBLOCKING AND DETERMINISTIC MULTIRATE MULTICAST PACKET SCHEDULING」と題する関連米国特許出願整理番号Ｖ−０００６号に対するＰＣＴ出願であって、その全体は参照することにより組込まれる。本出願は、現出願と同一出願人に譲渡された２００１年９月２７日提出のVenkat Kondaによる「REARRANGEABLY NON-BLOCKING MULTICAST MULTI-STAGE NETWOARKS」と題する関連連米国特許出願番号０９／９６７，８１５号、及び２００３年９月６日提出の、その一部継続出願のＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７１号に関連し、その全体は参照することにより組込まれる。本出願は、現出願と同一出願人に譲渡された２００１年９月２７日提出の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」と題する米国特許６，３５１，４６６号には、各入力ポートにｒ 個のユニキャストキューと各出力ポートに１つのマルチキャストキューを有する、クロスバー相互接続ネットワークにおけるＶＯＱスイッチング技術が、パケット待ち時間の正確な制御を含む出力キュースイッチであるかのように実行する、少なくとも４倍のスピードアップが必要であると記述されている。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来技術のスイッチファブリックには、多くの問題が伴う。第１に、マルチキャストパケットのためのＨＯＬブロッキングが除去されない。第２に、相互接続における数学的最小限のスピードアップが未知である。第３に、相互接続ネットワークにおけるスピードアップの使用は、出力ポートを氾濫させ、これが出力ポートにおける不必要なパケット輻輳、及びパケットをエグレスポート外に送信するための速度減少を招く。第４に、任意にファンアウトされるマルチキャストパケットは、出力ポートに対してノンブロッキング方式ではスケジューリングできない。第５に、各スイッチング時において、パケット調停が繰り返し実行され、スイッチング時間、費用及び電力コストが高くつく。最後に第６として、現行技術は、スケジューリングを貪欲で非決定論的方式で実行するので、それにより入力ポートと出力ポートにおいてセグメント化と再組立を必要とする
【課題を解決するための手段】
【００１１】
各入力ポートにマルチキャストパケットを含む、複数の入力ポート、複数の出力ポート、及び複数の入力キューを有する相互接続ネットワークを通じてマルチキャストパケットをスケジューリングするシステムは、本発明に従って、多くとも入力キューと同数のパケットを、各入力ポートから各出力ポートに対しスケジューリングすることにより、ノンブロッキング方式で作動する。スケジューリングは、各マルチキャストパケットが、２つ以下の相互接続ネットワークと２回以下のスイッチング回数を介してファンアウト分割されるように実行される。システムは、１００％スループットで、作業節減、規則的であるが決定論的に作動し、それにより出力ポートを輻輳させることは決してない。このシステムは、相互接続ネットワークにおいて数学的に最小限のスピードアップを用い、調停を１度だけの繰り返しで実行する。このシステムは、相互接続ネットワークにおけるパケットの並べ替え問題、パケットの内部バッファリングが決して無く、したがって、真にカットスルーで分散的な方式で作動する。別の実施例においては、各出力ポートも複数の出力キューを含み、各パケットは、宛先出力ポート内の出力キューまで、パケットのサイズに違いがあっても、決定論的方式でパケットのセグメント化及び並べ替えの必要なしに転送される。一実施例においては、スケジューリングは、相互接続ネットワークにおいて少なくとも３倍のスピードアップを用いて、厳密なノンブロッキング方式で実行される。別の実施例においては、スケジューリングは、相互接続ネットワークにおいて少なくとも２倍のスピードアップを用いて、再配置可能なノンブロッキング方式で実行される。このシステムは、マルチキャストパケットのため、入力ポートから出力ポートまで、エンドツーエンドの保証帯域幅と待ち時間を提供する。すべての実施例において、相互接続ネットワークは、クロスバーネットワーク、共有メモリネットワーク、クロスネットワーク、ハイパーキューブネットワーク、又はあらゆる内部ノンブロッキング相互接続ネットワーク又はネットワークのネットワークであってよい。
【発明を実施するための最良の形態】
【００１２】
本発明は、入力ポートに到着するユニキャスト及びの任意ファンアウトマルチキャストパケットを含むスイッチファブリックにおける、通信の性質に無関係なノンブロッキングで決定論的スケジューリングの設計及び操作に関連する。具体的には、本発明は、パケットスケジューリングシステムにおける以下の問題に関する。１）パケットの、厳密に再配列可能なノンブロッキングスケジューリング、２）入力ポートから出力ポートまで（必要な場合は、出力ポート内の特定の出力キューまで）パケットを決定論的に、即ち、出力ポートを輻輳させることなくスイッチングすること、３）パケットのセグメント化と再配列（ＳＡＲ）の実施を必要としないこと、４）調停は、１度の繰り返しだけで行われること、５）相互接続ネットワークにおいて、数学的に最小限のスピードアップを使用すること、及び６）パケットのサイズが可変な場合であっても、１００％スループットで作動すること。
【００１３】
入力ポートにあるパケットが１つを超える出力ポートを宛先としている場合、１対多数のパケット転送を必要とするので、そのパケットをマルチキャストパケットと呼ぶ。入力ポートにあるパケットが唯１つの出力ポートを宛先としている場合、１対１のパケット転送を必要とするので、そのパケットをユニキャストパケットと呼ぶ。入力ポートにあるパケットがすべての出力ポートを宛先としている場合、１対全部のパケット転送を必要とするので、そのパケットをブロードキャストパケットと呼ぶ。一般的に、マルチキャストパケットは、１つを超える出力ポートを宛先とすることを意味するので、ユニキャスト及びブロードキャストパケットを含む。相互接続ネットワークを通じて転送される１組のマルチキャストパケットは、マルチキャスト割当と呼ばれる。スイッチファブリックにおけるマルチキャストパケット割当は、入力ポートにおいて利用可能な任意のパケットが、任意の利用可能な出力ポートに常に転送することができる場合は、ノンブロッキングである。
【００１４】
ここに記述する型のスイッチファブリックは、出力ポートにおいて仮想出力キュー（ＶＯＱ）を採用する。一実施例において、各入力ポートにおいて受信されるパケットは、出力ポートにあるのと同数のキューの中に配置される。各キューは、出力ポートの１つのみを宛先とするパケットを保持する。したがって、ユニキャストパケットは、その宛先出力ポートに対応する対応入力キューの中に置かれ、マルチキャストパケットは、その宛先出力ポートの１つに対応する対応入力キューのいずれか１つの中に置かれる。出力キューがある場合は、一実施例において、入力ポートにあるのと同数のキューが各出力ポートに存在する。パケットは、各出力キューが１つの入力ポートのみからスイッチングされたパケットを保持するよう、出力キューにスイッチングされる。
【００１５】
ここに記述するタイプのスイッチファブリックの一定のものにおいては、一定レートの任意ファンアウトマルチキャストパケットを有すると、出力ポートにおいて同等の帯域幅を割り当てる。一定レートのユニキャストパケットを有し、すべての入力ポートの中に各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートにおいて同等の帯域幅を割り当てることは、上記に参照して組込まれた米国特許出願、弁理士整理番号Ｖ−０００５号及びＰＣＴ出願、弁理士整理番号Ｓ−０００５号に詳細な記述がある。マルチレートユニキャストパケットを有し、各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートにおいて異なる帯域幅を割り当てることは、上記参照して組込まれた米国特許出願、弁理士整理番号Ｖ−０００９号及びそのＰＣＴ出願、弁理士整理番号Ｓ−０００９号に詳細な記述がある。マルチレートマルチキャストパケットを有し、各入力キューを持つノンブロッキングで決定論的スイッチファブリックが、出力ポートにおいて異なる帯域幅を割り当てることは、上記参照して組込まれた米国特許出願、弁理士整理番号Ｖ−００１０号及びそのＰＣＴ出願、弁理士整理番号Ｓ−００１０号に詳細な記述がある。
【００１６】
図１Ａを参照すると、模範的なスイッチファブリック１０は、４つの入力ポート１５１−１５４を含む入力ステージ１１０と、３つの４×４クロスバーネットワーク１３１−１３３を含む相互接続ネットワークの中間ステージ１３０を経由して、４つの出力ポート１９１−１９４を含む出力ステージ１２０から成る。各入力ポート１５１−１５４は、それぞれ入口リンク１４１−１４４を介してマルチキャストパケットを受信する。各出力ポート１９１−１９４は、それぞれ出口リンク２０１−２０４を介してマルチキャストパケットを送信する。各クロスバーネットワーク１３１−１３３は、８つのリンク（以下「第１内部リンク」と言う）ＦＬ１−ＦＬ８を介して、４つの入力ポート１５１−１５４にそれぞれ接続され、さらに８つのリンク（以下「第２内部リンク」と言う）ＳＬ１−ＳＬ８を介して、４つの出力ポート１９１−１９４にそれぞれ接続されている。図１Ａのスイッチファブリック１０においては、入口リンク１４１−１４４、第１内部リンクＦＬ１−ＦＬ８、第２内部リンクＳＬ１−ＳＬ８、及び出口リンク２０１−２０４のそれぞれは、同一レートで作動する。
【００１７】
各入力ポート１５１−１５４において、入口リンク１４１−１４４を介して受信されるマルチキャストパケットは、出力ポート１９１−１９４を宛先とするパケットが、各入力ポート１５１−１５４においてそれぞれ入力キュー１７１−１７４の中に置かれるように、存在する出力ポートと同数の入力キュー１７１−１７４（４個）に、それらマルチキャストパケットの宛先出力ポートに応じてソートされる。一実施例においては、図１Ａのスイッチファブリック１０に示すように、マルチキャストパケットを入力キューに置く前に、優先順位キュー１６１−１６４の中に置いてもよい。各優先順位キュー１６１−１６４は、「１−ｆ」の優先順位に対応するマルチキャストパケットを保持するｆ 個のキューを含む。例えば、出力ポート１９１を宛先とするパケットは、パケットの優先順位「１−ｆ」に基づいて、優先順位キュー１６１の中に置き、最高優先順位のパケットは、次の最優先順位パケットを置く前に、最初に入力キュー１７１の中に置く。優先順位キュー１６１−１６４の使用は、スイッチファブリック１０の作動には関係しないので、図１Ａのスイッチファブリック１０は、別の実施例においては優先順位キュー１６１−１６４無しで実施することもできる。（優先順位キューの使用は、本発明に記述するすべての実施例に無関係なので、すべての実施例は、優先順位キュー無しで、ノンブロッキングで決定論的方式で実施することもできる。）
【００１８】
このネットワークは、入力ステージ１１０、出力ステージ１２０及び中間ステージ１３０に結合されて、入力ポート１５１−１５４から出力ポート１９１−１９４へパケットをスイッチングするスケジューラも含む。スケジューラはメモリの中に、中間ステージ１３０内の相互接続ネットワークを通る経路のため利用可能な宛先のリストを保存している。
【００１９】
一実施例においては、図１Ａに示すように、各出力ポート１９１−１９４は、存在する入力ポート（４個）と同数の出力キュー１８１−１８４を含み、入力ポート１５１−１５４からスイッチングされるパケットが、各出力ポート１９１−１９４において、それぞれ出力キュー１８１−１８４内に置かれるようになっている。図１Ａのスイッチファブリック１０における４つの入力ポート１５１−１５４内の各入力キュー１７１−１７４は、入力ポート１５１内の入力キュー１７１の中にＡ１−Ａ４、および入力ポート１６４内の第４の入力キュー１７４の中にＰ１−Ｐ４の４つのパケットが、出力ポートに対してスイッチングされる態勢の整った模範的な状態を示す。４つの入力ポート１５１−１５４における１６個のすべての入力キュー内の先頭パケットは、それぞれＡ１−Ｐ１で指定される。
【００２０】
表１は、図１Ａのスイッチファブリック１０における、入力キューと出力キューの間の模範的なパケット割当を示す。入力ポート１５１内の入力キュー１７１内のＩ｛１，１｝で示すユニキャストパケットは、Ｏ｛１，１｝で示される出力ポート１９１内の出力キュー１８１に対して割当てられ、スイッチングされる。入力ポート１５１内の入力キュー１７２内のＩ｛１，２｝で示されるユニキャストパケットは、Ｏ｛２，１｝で示される出力ポート１９２内の出力キュー１８１に対して割り当てられ、スイッチングされる。同様に、残りの１６個の入力キュー内のパケットは、表１に示すように、残りの１６個の出力キューに割り当てられる。別の実施例においては、入力キューから出力キューへの割当は、表１と異なるが、本発明に従うと、各出力ポート内の出力キューに対しパケットをスイッチングするのに割当てられる各入力ポート内の入力キューは、１つのみであり、その逆も真である。
【００２１】
【表１】
2007510379.tif 000003
【００２２】
マルチキャスト割当を特徴付けるには、ｘ，ｙ∈｛１−４｝であるときＩ｛ｘ，ｙ｝について、ＯＰ⊆｛１，２，３，４｝が入力キューＩ｛ｘ，ｙ｝のマルチキャストパケットが宛先とする出力ポートのサブセットを示すとき、Ｉ｛ｘ、ｙ｝＝ＯＰとする。一実施例において、入力キューＩ(ｘ、ａ)＝ＯＰ｛ａ，ｂ，ｃ，ｄ｝からのマルチキャストパケットは、４つの出力ポートａ、ｂ、ｃ、及びｄ内の出力キューＯ｛ａ，ｘ｝、Ｏ｛ｂ，ｘ｝、Ｏ｛ｃ，ｘ｝、及びＯ｛ｄ，ｘ｝に対してスイッチングされる。例えば、入力キューＩ｛１、１｝＝ＯＰ｛１，２｝内のマルチキャストパケットは、出力キューＯ｛１，１｝とＯ｛２，１｝に対してスイッチングされる。同様に、入力キューＩ｛１、１｝＝ＯＰ｛１，２，３，４｝内のマルチキャストパケットは、出力キューＯ｛１，１｝、Ｏ｛２，１｝、Ｏ｛３，１｝、及びＯ｛４，１｝に対してスイッチングされる。
【００２３】
入力リンク１４１においてＯＰ⊂｛１，２，３，４｝で受信するマルチキャストパケットは、入力キューＩ｛１，１｝、Ｉ｛１，２｝、Ｉ｛１，３｝、及びＩ｛１，４｝の任意の１つに置かれる。それは、パケットの宛先出力ポートは、すべての出力ポート１９１−１９４であるからである。しかしながら、出願者は、一旦マルチキャストパケットが、例えば入力キューＩ｛１，１｝に、置かれると、続く残りの同一のソースと宛先アドレスを持つパケットは、入力リンク１４１により受信されたパケットの順序を維持するように、同一入力キューに置かれることに注目する。例えば、マルチキャストパケットが、入力キューＩ｛１，２｝＝ＯＰ｛１，２，３，４｝に置かれることもあるが、そのときは、出力キューＯ｛１，１｝、Ｏ｛２，１｝、Ｏ｛３，１｝、及びＯ｛４，１｝に対しスイッチングされる。したがって、どの入力キューに置かれるかに関わりなく、宛先出力ポート内の同一出力キューに対してスイッチングされる。また、図１Ａのスイッチファブリック１０におけるＯＰ⊂｛１，２，３，４｝であるマルチキャストパケット（出力キューによって既に許可された）は、４個すべてのポート１９１−１９４にスイッチングしているため、任意の他のパケットに対して、ファブリックスイッチングサイクル内の出力ポートにスイッチングさせないことが承知されるはずである。
【００２４】
表２は、図１Ａのスイッチファブリック１０において、入力ポートの入力キューにより、入力リンク１４１−１４４を介して受信されるマルチキャストパケット要求の模範的セットを示す。入力キューＩ｛１，１｝におけるマルチキャストパケットは、出力キューＯ｛１，１｝、Ｏ｛２，１｝及びＯ｛３，１｝を宛先としてスイッチングされる。入力キューＩ｛１，２｝におけるマルチキャストパケットは、出力キューＯ｛１，１｝、及びＯ｛２，１｝を宛先としてスイッチングされる。同様に、残りの１６個の入力キューは、表２に示すように、宛先出力キューに割り当てられたマルチキャストパケットを有する。
【００２５】
出願人は、入力キューが表２に示されているようなマルチキャストパケットを含む場合は、入力ポートの競合が生じることを承知している。各入力リンクは、多くとも１回のスイッチングで１個のパケットを、および４回のスイッチングで（以下「ファブリックスイッチングサイクル」という）多くとも４個のパケットを受信する。各出力ポートは、１回のファブリックスイッチングサイクルで多くとも４個のパケットを受信することができるので、各入力ポートの入力キューにある、受信されたすべてのマルチキャストパケットは、出力ポートにスイッチングすることができず、入力ポートの競合が生じる。したがって、そのうちのほんの数個のみが、選択され、出力ポートにスイッチングされる。
【００２６】
【表２】
2007510379.tif 000004
【００２７】
図１Ｂは、本発明にかかる、調停及びスケジューリング方法を、中間ステージ１３０に３基の４×４クロスバーネットワーク１３１−１３３を用いて、即ち、３倍のスピードアップにより、図１Ａのスイッチファブリック１０を厳密なノンブロッキングな決定論的方式で作動させる一実施例により示す。厳密なノンブロッキングな決定論的スイッチングの実施に当たって使用される具体的な方法は、本開示の観点から当業者には明らかな多くの異なる方法の中の任意の方法でよい。このような調停及びスケジューリング方法の１つを、図１Ｂを参照して以下に記述する。
【００２８】
図１Ｂの方法４０の調停部分は（詳細は後述）、３つのステップからなる。即ち、入力ポートによる要求の生成、出力ポートによる許可の発行、及び入力ポートによる許可の承認である。ファブリックスイッチングサイクル毎に出力ポートは、入力ポートを輻輳状態にすることなく、４個のパケットのみを受信することができるので、マルチキャストパケットをそのファンアウト回数だけカウントし、４個のパケットのみを入力ポートからスイッチングすることができる。従って、１回のファブリックスイッチングサイクルにおいて、調停を実行して、各入力ポートからスイッチングすべき最大４個のパケットを選択する。表３は、表２に示すパケットの入力競合を解消した後、出力ポートに対してスイッチングされる各入力ポートからの４個のパケットを示す。入力ポート競合を解消するのに使用される特定の調停基準は、多くとも４個のパケットがファブリックスイッチングサイクル毎に各入力ポートからスイッチングされるように、マルチキャストパケットが選択される限り、本発明には関係がない。
【００２９】
表３に示すように、入力ポート１５１からは、Ｉ｛１，１｝からの１つのパケットが出力ポート１９１、１９２および１９３へ、Ｉ｛１、４｝からの２番目のパケットが出力ポート１９４へ、というように２つのパケットがファブリックスイッチングサイクル毎にスイッチングされる。明らかに、ファブリックスイッチングサイクル毎に入力ポート１５１からスイッチングされるパケットの総数は、マルチキャストパケットをそのファンアウトと同じ回数をカウントすると４個である。表２に示すＩ｛１，２｝及びＩ｛１，３｝からのパケットは、出力ポートにスイッチングされない。これらは、入力ポート競合の解消中の調停において選択されなかったからである。同様に、残りの入力ポートにおいても、表３に示すように、４個のパケットのみが選択され、これらは、ファブリックスイッチングサイクル毎に、出力ポートにスイッチングされる。
【００３０】
【表３】
2007510379.tif 000005
【００３１】
表４は、表３の入力ポートにおいて生成されたパケット要求に対応する出力ポートにより受信されたパケット要求を示す。上述したように、ある入力ポートの入力キューからの各パケットを表１に示したように対応する出力キューに割り当てるので、各出力ポートでパケット要求を４個のみ受信することは明らかである。従って、全パケットに許可を発行でき、出力ポート競合を生じることがない。これと同じく、各入力ポートが多くとも４個までのパケット要求しか生成しないので、パケットの許可はどれも、入力ポートによって承認される。
【００３２】
【表４】
2007510379.tif 000006
【００３３】
本発明によると、１６個のパケットＡ１−Ｐ１の全部が、ユニキャストパケットとマルチキャストパケットのどちらであっても、ファブリックスイッチングサイクルにおいて、中間ステージ１３０の相互接続ネットワークを介し、入力ポートから出力ポートにノンブロッキング方式でスイッチされる。各スイッチングで、各入力ポートの各入力キューから多くとも１つのパケットがスイッチングされ、各出力ポートに多くとも１つのパケットがスイッチングされる。ただし、パケットがマルチキャストパケットである場合、後述するように、生成されたスケジュールによっては、同じスイッチングで、１個の入力キューから１つを超える出力ポートにスイッチアウトされることがある。ここで出願者は、図１Ａのスイッチファブリック１０で、出力ポート１９１−１９４にある１６個の出力キューにスイッチングするために、１６個の任意の ファンアウトマルチキャストパケットＡｌ−Ｐｌを決定論的およびノンブロッキングにスケジューリングすることについての問題は、図１Ｃに示した３ステージのクロスネットワーク１４をノンブロッキングにスケジューリングすることに関係するという重要な見方をしている。 
【００３４】
図１Ｃを参照すると、中間ステージ１３０を経由して入力ステージ１１０と出力ステージ１２０との間の通信要求を満足する１１個のスイッチの時間−空間−時間（ＴＳＴ）構成で作動する、模範的な対称３ステージクロスネットワーク１４が示されている。この場合、入力ステージ１１０は、４個の４×３スイッチＩＳ１−ＩＳ４を含み、出力ステージ１２０は、４個の３×４スイッチＯＳ１−ＯＳ４を含み、中間ステージ１３０は、３個の４×４スイッチＭＳ１−ＭＳ３を含む。入力ステージ１１０の各スイッチに対する入口リンクの数、及び出力ステージ１２０の各スイッチに対する出口リンクの数をｎで表示し、入力ステージ１１０及び出力ステージ１２０のスイッチの数をｒ で表示する。３個の各中間スイッチＭＳ１−ＭＳ３は、ｒ 個のリンク（例えば、各入力スイッチＩＳ１−ＩＳ４から中間スイッチＭＳ１に対し接続されるリンクＦＬ１−ＦＬ４）を介してｒ 個の各入力スイッチに接続され、ｒ 個の第２内部リンク（例えば、中間スイッチＭＳ１から各出力スイッチＯＳ１−ＯＳ４に対して接続されるリンクＳＬ１−ＳＬ４）を介して、ｒ 個の各出力スイッチに接続される。このネットワークは、１６個の入口リンク、即ちＩ｛１，１｝−Ｉ｛４，４｝及び１６個の出口リンク、即ちＯ｛１，１｝−Ｏ｛４，４｝を有する。図１Ａのスイッチファブリック１０と全く同様に、図１Ｃの３ステージクロスネットワーク１４においては、１６個すべての入力リンクが、表１に示すように１６個の出力リンクに割当てられる。図１Ｃのネットワーク１４は、第１ステージにおける各接続要求を多くとも２回、中間ステージ１３０におけるスイッチの数が
2007510379.tif 000007
個に等しいとき、中間ステージにおいては必要とする回数だけ、ファンアウトすることにより、マルチキャスト接続要求のため厳密なノンブロッキング方式で作動することができる（本発明の背景として参照して組込まれる、Venkat Kondaにより現出願と同一出願人に譲渡された２００１年９月２７日提出の「STRICTLY NON-BLOCKING MULTICAST MULTI-STAGE NETWORKS」と題する関連米国特許出願番号０９／９６７，１０６号、及び２００３年９月６日提出の、その一部継続ＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７２号を参照）。
【００３５】
本発明にしたがって、中間ステージ１３０に３個の４×４クロスバーネットワーク１３１−１３３を有する、即ち、３倍のスピードアップを有する一実施例において、図１Ａのスイッチファブリック１０は、入力ポートにおける各パケット要求を、多くとも２回及び、中間ステージ相互接続ネットワークにおいては、必要とする回数だけファンアウトすることにより、厳密なノンブロッキング方式で作動する。厳密なノンブロッキングで決定論的なスイッチングを実施するに当たって使用する具体的な方法は、本開示の観点で当業者には明らかな多数の異なる方法のうちいずれでもよい。このようなスケジューリング方法の１つは、図１Ｂの調停及びスケジューリング方法のスケジューリング部分である。
【００３６】
【表５】
2007510379.tif 000008
【００３７】
表５は、表４の承認に関する４回の各スイッチング時における、図１Ｂの調停及びスケジューリング方法４０のスケジューリング部分を使用した一実施例によるパケットのスケジューリングを示す。図１Ｄ〜図１Ｈは、各スイッチング後の図１Ａのスイッチファブリック１０の状態を示す。図１Ｄは、パケットＥ１及びＫ１が、出力キューにスイッチングする１回目のスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５２からのパケットＥ１は、出力ポート１９１、１９２および１９４を宛先とする。本発明により、マルチキャストパケットは、多くとも２つの相互接続ネットワーク１３１−１３３を介して、４回のスイッチングのいずれかにおいてファンアウトされる。例えば、図１Ｄに示すように、入力ポート１５２からのパケットＥ１は、クロスバーネットワーク１３１を経由して、１回目のスイッチングで、出力ポート１９１の出力キュー１８２および出力ポート１９２の出力キュー１８２の中にスイッチングされる。（パケットＥ１は、後述するように、図１Ｆに示す３回目のスイッチングで、クロスバースイッチ１３３を介して、出力ポート１９４の出力キュー１８２に対してスイッチングされる）。従って、マルチキャストパケットＥ１は、２つのクロスバーネットワークのみ、即ち１回目のスイッチングにおけるクロスバーネットワーク１３１、および２回目のスイッチングにおけるクロスバーネットワーク１３１を介して、ファンアウトされる。
しかしながら、最初のスイッチングでパケットＥ１は出力ポート１９１および１９２にファンアウトされ、３回目のスイッチングタイムで出力ポート１９４にファンアウトされる。
【００３８】
本発明により、入力ポートからのマルチキャストは、中間ステージにある多くとも２つのクロスバーネットワークを介して、おそらくは２回のスイッチングでファンアウトされ、中間ステージ（クロスバー）ネットワークからのマルチキャストパケットは、必要な数の出力ポートに対してファンアウトされる。また、マルチキャストパケットが宛先出力ポートに対して、２回の別にスケジューリングされたスイッチングにおいてスイッチングされる場合、１回目のスイッチング後、そのマルチキャストパケットは、２回目にスケジューリングされたスイッチングで、残りの出力ポートに対してスイッチングされるまで、入力キューの先頭に保たれるままである。したがって、図１Ｄにおいて、パケットＥ１は、まだ入力ポート１５２の入力キュー１７１の先頭にある。
【００３９】
図１Ｄにおいて、入力ポート１５４からの、マルチキャストパケットＭ１（出力ポート１９１−１９４を宛先とする）は、クロスバーネットワーク１３２を介してファンアウトされ、クロスバーネットワーク１３２から、出力ポート１９３の出力キュー１８４及び出力ポート１９４の出力キュー１８４にファンアウトされる。パケットＭ１は、２回目のスイッチングで後述するように出力ポート１９１−１９２にスイッチングされる。マルチキャストパケットＭ１も、まだ入力ポート１５４の入力キュー１７１の先頭に残されている。出願者は、すべての出力ポートは、各スイッチング時において、多くとも１つのパケットを受信するが、マルチキャストパケットがスイッチングされる場合は、すべての入力ポートは、各スイッチング時において、多くとも１つのパケットをスイッチングするわけではないことを承知している。
【００４０】
図１Ｅは、パケットＤ１、Ｋ１及びＭ１が出力キューにスイッチングされる２回目のスイッチングの後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのユニキャストパケットＤ１は、クロスバーネットワーク１３１を経由して出力ポート１９４の出力キュー１８１にスイッチングされる。入力ポート１５３からのユニキャストパケットＫ１は、クロスバーネットワーク１３３を経由して出力ポート１９３の出力キュー１８３にスイッチングされる。入力ポート１５３からのマルチキャストパケットＭ１は、クロスバーネットワーク１３２を介してファンアウトされ、そこから出力ポート１９１の出力キュー１８４、及び出力ポート１９２の出力キュー１８４にファンアウトされる。マルチキャストパケットＭ１は、すべての宛先出力ポートにスイッチングし尽くされるので、先頭から削除され、したがってパケットＭ２が入力ポート１５４の入力キュー１７１の先頭になる。ここでも、２回目のスイッチングで、各入力ポートからパケット１つだけがスイッチングされ、各出力ポートはパケット１つだけを受信する。ここでも、２回目のスイッチングにおけるすべての出力ポートは、多くとも１つのパケットを受信する。
【００４１】
図１Ｆは、パケットＡ１、Ｅ１及びＩ１が出力キューにスイッチングされる３回目のスイッチング後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのマルチキャストパケットＡ１は、クロスバーネットワーク１３１を経由して、出力ポート１９３の出力キュー１８１にファンアウトされる。（マルチキャストパケットＡ１は、４回目のスイッチングでスケジューリングされて出力ポート１９１にファンアウトされる。）したがって、入力ポート１５１の入力キュー１７１の先頭は、まだパケットＡ１を含む。入力ポート１５２からのマルチキャストパケットＥ１は、クロスバーネットワーク１３３を経由して、出力ポート１９４の出力キュー１８２にファンアウトされる。マルチキャストパケットＥ１は、すべての宛先出力ポートにスイッチングし尽くされるので、入力ポート１５２の入力キュー１７１の先頭から削除される。入力ポート１５３からのユニキャストパケットＩ１は、クロスバーネットワーク１３２を介して出力ポート１９１の出力キュー１８３にスイッチングされる。ここでも、３回目のスイッチングにおけるすべての出力ポートは、多くとも１つのパケットを受信する。
【００４２】
図１Ｇは、パケットＡ１、Ｇ１、及びＪ１が出力キューにスイッチングされる、４回目のスイッチング後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５１からのマルチキャストパケットＡ１は、クロスバーネットワーク１３３を介して出力ポート１９２の出力キュー１８１にスイッチングされる。マルチキャストパケットＡ１は、すべての宛先にスイッチングし尽くされるので、入力ポート１５１のキュー１７１の先頭から削除される。入力ポート１５２からのユニキャストパケットＧ１は、クロスバーネットワーク１３２を介して出力ポート１９３の出力キュー１８２にスイッチングされる。入力ポート１５３からのマルチキャストパケットＪ１は、クロスバーネットワーク１３１を介してスイッチングされ、クロスバーネットワーク１３１から出力ポート１９２の出力キュー１８２および出力ポート１９４の出力キュー１８３に２回ファンアウトされる。この場合、マルチキャストパケットＪ１は、１回だけのスイッチングですべての宛先出力ポートに中間ステージ（クロスバー）ネットワークを１つだけ通じてファンアウトされる。マルチキャストパケットＪ１は、すべての宛先にスイッチングし尽くされるので、入力ポート１５３のキュー１７２の先頭から削除される。ここでも、４回目のスイッチングにおけるすべての出力ポートは、多くとも１つのパケットを受信する。
【００４３】
図１Ｈは、パケットＥ２及びＭ２が出力キューにスイッチングされる５回目のスイッチング後の、図１Ａのスイッチファブリック１０の状態を示す。入力ポート１５２からの、パケットＥ３は、クロスバーネットワーク１３１を介して、出力ポート１９１の出力キュー１８２及び出力ポート１９２の出力キュー１８２にスイッチングされる。（パケットＥ２は後のスイッチングにおいて、パケットＥ１とまったく同様に出力ポート１９４の出力キュー１８２にスイッチングされる。）入力ポート１５４からのマルチキャストパケットＭ２は、（出力ポート１９１−１９４を宛先とする）クロスバーネットワーク１３２を通じてファンアウトされ、クロスバーネットワーク１３２から出力ポート１９３の出力キュー１８４及び出力ポート１９４の出力キュー１８４にファンアウトされる。パケットＭ２は、パケットＭ１と全く同様に、後のスイッチングにおいて、出力ポート１９１−１９２にスイッチングされる。マルチパケットＥ２及びＭ２は、まだ宛先出力ポートすべてに対してスイッチングされていないので、それぞれ入力ポート１５２の入力キュー１７１及び入力ポート１５４の入力キュー１７１の先頭に残されている。したがって、図１Ｂの調停及びスケジューリング方法４０は、第１ファブリックスイッチングサイクルのためのスケジュールを実行した後、再スケジューリングを行う必要はない。したがって、いずれかの特定の入力キューから宛先出力キューに対するパケットは、同一経路に沿ってスイッチングされ、入力ポートがそれを受信した通りの順序で移動するので、パケット並べ替えの問題は決して生じない。
【００４４】
ファブリックスイッチングサイクルにおいては、最大１６個のマルチキャストパケットが出力ポートにスイッチングされるので、このスイッチは、本発明に基づき、ノンブロッキングで、１００％スループットで作動する。図１Ａのスイッチファブリック１０は、各出力ポートが、それを宛先とする入力ポートのいずれか１つから少なくとも１つのパケットがある限り、１回のスイッチングにおいて、少なくとも１つのパケットを受信するように作動するので、以後、このスイッチファブリックを「作業節約システム」と呼ぶ。スイッチファブリックがノンブロッキングであるとき、スイッチファブリックがそのままで作業節約的であることに気付くのは容易である。本発明により、図１Ａのスイッチファブリック１０は、各入力キューの先頭にあるパケットが、各入力ポートにある入力キュー（４個）の数に等しいスイッチング回数を超えては保持されないよう作動する。以後このスイッチファブリックを「公正システム」と呼ぶ。仮想出力キューを使用するので、先頭ブロッキングも、ユニキャスト及びマルチキャスト双方のパケットに関して削除される。
【００４５】
本発明により、図１Ｂの調停及びスケジューリング方法４０を用いて、図１Ａのスイッチファブリック１０は、各出力ポートは、相互接続ネットワークにおける３倍のスピードアップを用いて、１回のスイッチングで３個のパケットをスイッチングすることが可能であっても、１回のスイッチングにおいて、多くとも１つのパケットを受信するように作動する。しかもスピードアップは、相互接続ネットワークをノンブロッキング方式で、決して出力ポートを輻輳させないように作動させることのみに厳密に使用される。したがって、図１Ａのスイッチファブリック１０において、パケットをスイッチングする図１Ｃの調停及びスケジューリング方法４０は、決定論的である。各入口リンク１４１−１４４は、パケットを、各出口リンク２０１−２０４が送信するのと同一レート、即ち各スイッチング時に１つのパケットを受信する。各スイッチング時において、１つのパケットのみが、各入力ポート１５１−１５４から決定論的にスイッチングされ、１つのパケットのみが、各出力ポート１９１−１９４の中にスイッチングされるので、図１Ａのパケットファブリック１０は、決して出力ポートを輻輳させない。
【００４６】
本発明に基づく決定論的スイッチングの重要な利点は、スイッチファブリックが予約過多であるときであっても、入力ポートからパケットを高くともピークレートでスイッチングし尽くすことである。これは、出力ポートにおいてパケットは高くてもピークレートで受信されることをも意味する。それは、出力ポートにおいてトラフィック管理が不要であり、パケットは、出力ポートから決定論的に送信されることを意味する。従って、トラフィック管理は、図１Ａのスイッチファブリック１０内の入力ポートにおいてのみ必要である。
【００４７】
図１Ａのスイッチファブリック１０の別の重要な特徴は、特定の入力キューに属するすべてのパケットが、宛先出力ポートの同一出力キューに対してスイッチングされることである。出願者は、出力キューによる３つの重要な利点に注目する。１）スイッチングにおいて、１バイト又は数バイトが入力ポートから出力ポートに対しスイッチングされる。あるいは、スイッチファブリックのスイッチング回数は可変なので、スイッチファブリックの設計段階では、これは柔軟性のあるパラメータである。２）したがって、パケットＡ１−Ｐ１が任意に長く可変のサイズであっても、入力キュー内の各パケットは、宛先出力ポート内の同一出力キューに対してスイッチングされるので、１回のスイッチングで完全なパケットをスイッチングする必要はない。また、出力キューの第２の利点は、大きいパケットを入力ポートにおいて物理的にセグメント化し、出力ポートにおいて再組立する必要がないことである。物理的にパケットをセグメント化することなく、パケットは、出力キューに対して論理的にセグメント毎にスイッチングされる（パケットセグメントのサイズは、スイッチングの回数により決定される）。各パケットにおけるパケットセグメントも、同一経路を介して、入力キューから宛先出力キューまでスイッチングされる。３）出力キューの第３の利点は、パケット及びパケットセグメントが、入力ポートが受信されるのと同一の順序でスイッチングされるので、パケット並べ替えの問題が決して生じないことである。
【００４８】
図１Ｉは、長いパケットをスイッチングするスイッチファブリック１６を示す。各入力キューに１個のパケットがあり、１６個の入力キュー全部で１６個のパケットがある。すなわち、入力ポート１５１の入力キュー１７１にパケット｛Ａ１−Ａ４｝、入力ポート１５１の入力キュー１７２にパケット｛Ｂ１−Ｂ４｝、入力ポート１５１の入力キュー１７３にパケット｛Ｃ１−Ｃ４｝、入力ポート１５４の入力キュー１７４にパケット｛Ｐ１−Ｐ４｝がある。この１６個のパケットのそれぞれは、等しいサイズの４つのパケットセグメントからなる。例えば、パケット｛Ａ１−Ａ４｝は、Ａ１、Ａ２、Ａ３、Ａ４の４つのパケットセグメントからなる。パケットのサイズがパケットセグメントのサイズの４の倍数でない場合、４つめのパケットは、サイズが短いことになる。しかしながら、４個のパケットセグメントの何れも最大パケットセグメントサイズより大きくない。パケットセグメントのサイズは、スイッチング回数により定まる。即ち、各スイッチング時において、いずれかの入力ポートからいずれかの出力ポートに対して、１つのパケットセグメントのみがスイッチングされる。長いパケットサイズを除けば、図１Ｉのスイッチファブリック１６の図は、図１Ａのスイッチファブリック１０の図と同様である。スイッチファブリック１６は、図１Ａのスイッチファブリック１０の場合と同じ方法で実行され、表２中のパケット要求を図１Ｂに示した調停およびスケジューリング方法４０を実行して、表５に示したスケジュールを生成する。 
【００４９】
一実施例で、図１Ｊ〜図１Ｍは、各ファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。図１Ｊは、スケジュールされた先頭パケットセグメントＡｌ−Ｐ１すべてを出力キューにスイッチングする第１のファブリックスイッチングサイクル後の図１Ｉのスイッチファブリック１６の状態を示す。これらマルチキャストパケットセグメントは、図１Ｄ−１Ｇに示すように、図１Ａのスイッチファブリック１０において出力キューにスイッチングするように、図１Ｂの調停及びスケジューリング方法４０を使用して、全く同様の方法で出力キューに、スイッチングされる。図１Ｋは、その間にスケジューリングされたすべての先頭パケットセグメントＡ２−Ｐ２が出力キューにスイッチングする、第２ファブリックスイッチングサイクル後の、図１Ｉのスイッチファブリック１６の状態を示す。図１Ｌは、その間にスケジューリングされたすべての先頭パケットセグメントＡ３−Ｐ３を、出力キューにスイッチングする第３ファブリックスイッチングサイクル後の、図１Ｉのスイッチファブリック１６の状態を示す。図１Ｍは、その間にスケジューリングされたすべての先頭パケットセグメントＡ１−Ｐ１を、出力キューにスイッチングする第４ファブリックスイッチングサイクル後の、図１Ｉのスイッチファブリック１６の状態を示す。第１、第２、第３及び第４の各ファブリックスイッチングサイクルにおいて、パケットセグメントは、図１Ｄ−１Ｇに示すように、図１Ａのスイッチファブリック１０において、パケットＡ１−Ｐ１が出力キューに対してスイッチングされるのと全く同様の方法で、出力キューにスイッチングされる。明らかに、全パケットセグメントは、各入力ポートで受信されるのと同一の順序でスイッチングされる。したがって、パケット並べ替えの問題はない。パケットはまた、１００％スループットで、作業節約的、及び公正な方法でスイッチングされる。
【００５０】
図１Ｊ−１Ｍにおいては、パケットは、論理的にセグメント化され出力ポートにスイッチングされる。一実施例において、タグビット「１」も各パケットセグメントの特定の指定ビット位置に詰め込んで、そのパケットセグメントがそれぞれのパケット内の最初のパケットセグメントであることを表示する。「１」のタグビットを読み取ることにより、出力ポートは、パケットセグメントＡ１−Ｐ１が、新規パケット内の最初のパケットであることを認識する。同様に、各パケットセグメントは、「０」のタグビットを詰め込まれる最後のパケットセグメントを除いて、指定ビット位置に「１」のタグビットが詰め込まれる。（例えば、図１Ｉのスイッチファブリック１６内のパケットセグメントにおいて、パケットセグメントＡ１−Ｐ１、Ａ２−Ｐ２及びＡ３−Ｐ３には「１」のタグビットが詰め込まれる一方で、パケットセグメントＡ４−Ｐ４には「０」のタグビットが詰め込まれる）。タグビットが「０」であると検出されると、出力ポートは、次は新規パケットのパケットセグメント、又は新規パケットであると予測する。パケットの中にパケットセグメントが１つしかない場合、入力ポートにより「０」のタグビットが表示される。出力ポートは、「０」の指定タグビットのパケットセグメントを２個続けて受信すると、２個目のパケットセグメントは、新規パケットの唯一のセグメントであると判定する。
【００５１】
図１Ｉのスイッチファブリック１６において、パケットは４セグメント分の長さである。しかしながら、一般的にパケットの長さは、任意である。加えて、同一キュー内の異なるパケットは、異なるサイズである可能性がある。いずれの場合にも、図１Ｂの調停及びスケジューリング方法４０は、スイッチファブリックをノンブロッキング方式で作動させ、パケットは１００％スループット、作業節約的、及び公正な方法でスイッチングされる。また、入力ポート内のパケットを物理的にセグメント化し、出力ポート内に再組立する必要もない。スイッチファブリックのスイッチング回数も柔軟な設計パラメータであって、各スイッチング時において、パケットをバイト毎、又は数バイト毎にスイッチングするように設定される。
【００５２】
図１Ｂは、図１Ａのスケジューラにより遂行される、一実施例における、図１Ｂの調停及びスケジューリング方法４０の高レベルフローチャートである。この実施例によると、多くともｒ個の要求が、アクト４１において各入力ポートから生成される。各入力ポートが、ｒ個のユニキャストパケット要求を有するとき、各入力キューからの１つの要求に伴って、各入力ポートから多くともｒ 個の要求がある。しかしながら、マルチキャストパケットがあるときは、１回のファブリックスイッチングサイクルにおいて、各出力ポートは、多くともｒ個のパケットしか受信できないので、各入力ポートからのｒ個の要求を満足することは出来ない。このように、マルチキャストパケットは、入力ポートにおいて入力ポート競合を生じる。しかしながら、各入力ポートは、１回のファブリックスイッチングサイクルにおいて、多くともｒ個のパケットだけスイッチングすることができる。したがって、１つの入力ポートからの１つマルチキャストパケット要求は、同一入力ポートの別の入力キューからの別のパケット要求の犠牲の上に成り立つ。そこで、各入力ポートからのｒ個の要求は、ｒ個の異なる出力ポートに対して成されることを承知している必要がある。そのため、アクト４１において、調停方針を用いることにより、すべての要求のパケットの合計が、ｒ個以下になるように、即ち、マルチキャストパケットを、そのファンアウトの回数だけカウントし、各入力ポートの中にマルチキャスト要求のセットが生成される。しかしながら、アクト４１において入力ポート競合を解消するのに使用される選択方針のタイプは、本発明には無関係である。
【００５３】
アクト４２において、各出力ポートは、各要求が関連出力キューに関連付けられる、多くともｒ個の許可を発行する。各入力ポートが１個の要求だけを生成するため、各出力ポートが多くともｒ個の要求、即ち各入力ポートから１個受信することは容易に見ることができる。そして、各出力ポートは、受信されたｒ個の要求すべてに対して許可を発行することができる。したがって、マルチキャストパケットは、出力ポート競合を引き起こさないことを承知している。アクト４３において、各入力ポートは多くともｒ個の許可を承認する。各出力ポートが各入力ポートへ、多くともｒ個の許可を発行するため、各入力ポートは多くともｒ個の許可を受信する。そして、各入力ポートは、ｒ個の要求すべてを承認する。
【００５４】
アクト４４においては、多くともｒ２個の要求が、以前にスケジューリングされたパケットの経路を再配置することなく、スケジューリングされる。本発明にしたがうと、ｒ２個のすべての要求は、厳密なノンブロッキング方式で、中間ステージ１３０において少なくとも３倍のスピードアップを用いてスケジューリングされる。要求の生成、許可の発行、及び承認の生成の調停は、１度だけの繰り返しで実行されることに注目しなければならない。アクト４４の後、制御はアクト４５に戻る。アクト４５においては、入力ポートに、新規で異なる要求があるか否かを点検する。答が「いいえ」であれば、制御はアクト４５に戻る。新規の要求はあるが、それらが、出力キュー要求に対し同一の入力キューを有する点で異ならないときは、同一スケジュールを用いて、次の多くともｒ２個の要求をスイッチングする。入力ポートからの新規で異なる要求があるとき、制御はアクト４５からアクト４１に移り、アクト４１−４５は、ループで実施される。
【００５５】
図１Ｃのネットワーク１４は、中間ステージ１３０におけるスイッチが
2007510379.tif 000009
個であるとき、マルチキャスト接続要求のため再配置可能なノンブロッキング方式で作動させることができる。（本発明に対する背景として参照して組込まれる、Venkat Kondaにより現出願と同一出願人に譲渡され、２００１年９月２７日提出の「REARRANGEABLY NON-BLOCKING MULTICAST MULTI-STAGE NETWORKS」と題する関連の米国特許出願番号０９／９６７，８１５号、及び２００３年９月６日提出の、その一部継続ＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７１号を参照）。同様に、本発明にかかる、入力キューの中にマルチキャストパケットを有し、中間ステージ１３０に２個のみ４×４クロスバーネットワーク１３１を用いる、即ち、２倍のスピードアップを有する別の実施例において、図１Ｎのスイッチファブリック１８は、再配置可能なノンブロッキング方式で作動する。
【００５６】
厳密なノンブロッキングネットワークにおいては、すべての入力キューの先頭にあるパケットを１度にスケジューリングするので、パケットのための入力キューから宛先出力キューまでのネットワークを介した経路を、以前にスケジューリングしたパケットの経路を阻害することなくスケジューリングすることが常に可能であり、１つより多いこのような経路を利用することができるときは、残りのパケットのスケジューリングを懸念することなく、任意の経路を選択することができる。再配置可能なノンブロッキングネットワークにおいては、すべての入力キューの先頭にあるパケットは、１度にスケジューリングされるので、パケットのための入力キューから宛先出力キューまでの経路のスケジューリングは、必要に応じて以前にスケジューリングしたパケットの経路を再配置する、スケジューラの再配置能力の結果として、満足されることが保証されている。本発明により、図１Ｎのスイッチファブリック１８は、再配置可能なノンブロッキング方式で作動する一方、図１Ａのスイッチファブリック１０は、厳密なノンブロッキング方式で作動する。
【００５７】
図２Ａを参照すると、スイッチファブリック２０は、出力キューを有しない以外は、図２Ａのスイッチファブリック２０の図は、図１Ａのスイッチファブリック１０の図と全く同様である。本発明により、スイッチファブリック２０は、入力ポート及び出力ポートにＳＡＲを必要とすることを除いて、図１Ａのスイッチファブリック１０について開示したあらゆる側面において、同様に厳密にノンブロッキングな決定論的方式で作動する。パケットは、スイッチングで判定された通りに、入力ポートにおいてセグメント化する必要があり、別個に再組立の必要がある出力ポートにスイッチングされる。しかしながら、図１Ｂの調停及びスケジューリング方法４０は、図２Ａのスイッチファブリック２０において、パケットをスイッチングするためにも使用される。ここでも、スケジューリングは、１６個すべての先頭パケットに対して同時に実行され、出力ポートには仮想的に１６個の出力キューあると推定して、それらのパケットが、４回のスイッチングでスイッチングされる。しかしながら、そのスイッチングの間に、パケットは、出力キューと異なり、宛先出力ポート内にスイッチングされる。図２Ｂ−２Ｆは、表２に示すパケット要求をスケジューリングすることにより、ファブリックスイッチングサイクルにおける各スイッチング後の、図２Ａのスイッチファブリック２０の状態を示す。図１Ｂの調停及びスケジューリング方法を用い、図１Ａのスイッチファブリック１０において記述したのと同じステップにしたがって、各スイッチング時においてスケジューリングされるパケットを表５に示す。
【００５８】
図２Ｂは、その間にパケットＥ１及びＭ１が出力キューにスイッチングされる１回目のスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５２からのパケットＥ１は、クロスバーネットワーク１３１を経由して、１回目のスイッチングにおいて、出力ポート１９１および出力ポート１９２の中にスイッチングされる。（パケットＥ１は、後述するように、図２Ｃに示す３回目のスイッチングにおいてクロスバースイッチ１３３を介して、出力ポート１９４にスイッチングされる）。そのようにして、マルチキャストパケットＥ１は、クロスバーネットワーク２つのみ、即ち１回目のスイッチングにおけるクロスバーネットワーク１３１、および３回目のスイッチングにおけるクロスバーネットワーク１３３を介してファンアウトされる。しかしながら、最初のスイッチングで、パケットＥ１は、出力ポート１９１及び１９２にファンアウトされ、３回目のスイッチングで出力ポート１９４にファンアウトされる。
【００５９】
本発明により、入力ポートからのマルチキャストは、中間ステージにおいて、多くとも２つのクロスバーネットワークを介して、おそらくは２回のスイッチングでファンアウトされ、中間ステージ（クロスバー）ネットワークからのマルチキャストパケットは、必要な数の出力ポートにファンアウトされる。マルチキャストパケットが、宛先出力ポートに異なるスケジューリングの２回のスイッチングにおいてスイッチングされるときも、１回目のスイッチング後、そのマルチキャストパケットは、スケジューリングされる２回目のスイッチングに残りの出力ポートにスイッチングされるまで、入力キューの先頭に保たれるままである。したがって、図２Ｂにおいて、パケットＥ１は、まだ入力ポート１５２の入力キュー１７１の先頭にある。
【００６０】
図２Ｂにおいて、同様に入力ポート１５４からの、（出力ポート１９１−１９４を宛先とする）マルチキャストパケットＭ１は、クロスバーネットワーク１３２を介してファンアウトされ、クロスバーネットワーク１３２から出力ポート１９３及び出力ポート１９４内にファンアウトされる。パケットＭ１は、後述するように、２回目のスイッチングで出力ポート１９１−１９２にスイッチングされる。マルチキャストパケットＭ１も、まだ入力ポート１５４の入力キュー１７１の先頭にある。出願者は、マルチキャストパケットがスイッチングされると、すべての入力ポートが各スイッチング時において、多くとも１つのパケットをスイッチングするわけではないが、すべての出力ポートは、各スイッチング時において多くとも１つのパケットを受信することを承知している。
【００６１】
図２Ｃは、その間にパケットＤ１、Ｋ１及びＭ１が出力キューにスイッチングされる２回目のスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのユニキャストパケットＤ１は、クロスバーネットワーク１３１を経由して出力ポート１９４の中にスイッチングされる。入力ポート１５３のユニキャストパケットＫ１は、クロスバーネットワーク１３３を経由して出力ポート１９３にスイッチングする。入力ポート１５３からのマルチキャストパケットＭ１は、クロスバーネットワーク１３２を介してファンアウトされ、そこから出力ポート１９１及び出力ポート１９２の中にファンアウトされる。マルチキャストパケットＭ１は、すべての宛先出力ポートにスイッチングし尽くされるので、先頭から削除され、したがってパケットＭ２は、入力ポート１５４の先頭入力キューにある。ここでも、２回目のスイッチングにおいて、各入力ポートからパケット１つのみがスイッチングされ、各出力ポートは、パケット１つのみを受信する。さらにここでも、すべての出力ポートは、２回目のスイッチングにおいて、多くとも１つのパケットを受信する。
【００６２】
図２Ｄは、その間にパケットＡ１、Ｅ１及びＩ１が出力キューにスイッチングされる３回目のスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのマルチキャストパケットＡ１は、クロスバーネットワーク１３１を介してファンアウトされ、クロスバーネットワーク１３１において、出力ポート１９２及び出力ポート１９３へ２回ファンアウトされる。（マルチキャストパケットＡ１はスケジューリングされ、４回目のスイッチングで出力ポート１９１にファンアウトされる。）したがって、入力ポート１５１の入力キュー１７１の先頭は、まだパケットＡ１が成している。入力ポート１５２からのマルチキャストパケットＥ１は、クロスバーネットワーク１３３を経由して出力ポート１９４内にファンアウトされる。マルチキャストパケットＥ１は、すべての宛先にスイッチングし尽されるので、入力ポート１５２の入力キュー１７１の先頭から削除される。入力ポート１５３からのユニキャストパケットＩ１は、クロスバーネットワーク１３２を経由して出力ポート１９１にスイッチングされる。ここで、すべての出力ポートが３回目のスイッチングで多くとも１つのパケットを受信する。
【００６３】
図２Ｅは、その間にパケットＡ１、Ｇ１及びＪ１が、出力キューにスイッチングされる４回目のスイッチング後の、図２Ａのスイッチファブリック２０の状態を示す。入力ポート１５１からのマルチキャストパケットＡ１は、クロスバーネットワーク１３３を経由して出力ポート１９２にスイッチングされる。マルチキャストパケットＡ１は、すべての宛先にスイッチングし尽くされるので、それは入力ポート１５１の入力キュー１７１の先頭から削除される。入力ポート１５２からのユニキャストパケットＧ１は、クロスバーネットワーク１３２を経由して出力ポート１９３にスイッチングされる。クロスバーネットワーク１３１を介し、入力ポート１５３からのマルチキャストパケットＪｌをスイッチングし、クロスバーネットワーク１３１から出力ポート１９２および出力ポート１９４に２回ファンアウトする。この場合、１回のスイッチングだけで、中間ステージ（クロスバー）ネットワークを１つだけ通じて、マルチキャストパケットＪｌをすべての宛先の出力ポートにファンアウトする。また、マルチキャストパケットＪｌをすべての宛先にスイッチングし尽くしたので、入力ポート１５３の入力キュー１７２の先頭から削除される。ここで、４回目のスイッチングで、すべての出力ポートが多くともパケットを１つ受信する。
【００６４】
図２Ｆは、この間にパケットＥ２およびＭ２を出力キューにスイッチングする５回目のスイッチング後の図２Ａのスイッチファブリック２０の状態を示す。クロスバーネットワーク１３１を介し、入力ポート１５２からのパケットＥ２を出力ポート１９１および出力ポート１９２にスイッチングする。（パケットＥｌのように、後のスイッチングでパケットＥ２を出力ポート１９４にスイッチングすることができる）。クロスバーネットワーク１３２を通じて、入力ポート１５４からのマルチキャストパケットＭ２（出力ポート１９１−１９４を宛先とする）をファンアウトし、クロスバーネットワーク１３２から出力ポート１９３および出力ポート１９４にファンアウトする。パケットＭｌのように後のスイッチングで、パケットＭ２を出力ポート１９１−１９２にスイッチングできる。マルチキャストパケットＥ２、Ｍ２は、宛先の出力ポートの全部にスイッチされていないため、それぞれが入力ポート１５２の入力キュー１７１、入力ポート１５４の入力キュー１７１の先頭にまだある。このように、図１Ｂの調停およびスケジューリング方法４０だと、第１のファブリックスイッチング サイクルのスケジューリングを実行した後に、再スケジューリングする必要がない。また、何か特定の入力キューから宛先の出力キューに対するパケットは、同一経路を介してスイッチングされ、入力ポートがそれらを受信した通りの順序で移動するので、パケット並べ換えの問題は決して生じない。
【００６５】
図１Ｂの調停およびスケジューリング方法４０は、やはり厳密なノンブロッキング方式で図２Ａのスイッチファブリック２０を作動し、パケットは、１００％のスループットの作業節約的で公平な方法でスイッチングされる。スイッチファブリックのスイッチング時は、柔軟に設計できるパラメータでもあり、各スイッチングで、バイト毎や数バイト毎にパケットをスイッチングするよう設定できる。しかしながら、スイッチファブリック２０にはＳＡＲが必要であるため、パケットを入力ポートで物理的にセグメントし、出力ポートで再組立しなければならないということである。それでもスイッチファブリック２０では、パケットおよびパケットセグメントは、入力ポートで受信されたのと同じ順序で出力ポートへとスイッチングされる。実際、ＳＡＲ以外では、図１Ｂ調停およびスケジューリング方法４０は、図１Ａのスイッチファブリック１０について開示したあらゆる実施例と同じ方法で、厳密なノンブロッキングで決定論的方式で作動される。
【００６６】
スイッチファブリックのノンブロッキングな作動のための中間ステージにおける３倍のスピードアップは、次の２つの方法で実現される。すなわち、１）並列性と、２）スイッチング速度の３倍化である。例えば、図１Ａのスイッチファブリック１０に示すように、中間ステージで相互接続ネットワーク３つを並行して使用することによって、並列性が実現される。スイッチング速度を３倍にすることは、入力ポートと出力ポート内の各クロックにつき３倍のクロック速度で、第１および第２内部リンクを相互接続ネットワークを作動することによって実現される。第１のクロックでは、スイッチファブリックにあたる第１の相互接続ネットワークが、例えば、図１Ａのスイッチファブリック１０の相互接続ネットワーク１３１のような並行した相互接続ネットワーク３つを実装しているかのように、単一の相互接続ネットワークをスイッチングのために作動する。これと同じく第２のクロックでは、例えば図１Ａのスイッチファブリック１０の相互接続ネットワーク１３２のような第２の相互接続ネットワークとして単一の相互接続ネットワークを作動する。第３のクロックでは、例えば図１Ａのスイッチファブリック１０の相互接続ネットワーク１３３のような第３の相互接続ネットワークとして単一の相互接続ネットワークを動作する。したがって、この実施においては、相互接続ネットワークのクロックにおいて、及び第１、第２、及び第３内部リンクにおいて、３倍のレートが必要である。図１Ｂの調停およびスケジューリング方法４０は、本発明で記述するようなあらゆる側面において、ノンブロッキングな決定論的方式で並列性または３倍のレートのどちらかによるスピードアップを実行したスイッチファブリック両方を動作する。
【００６７】
図３Ａを参照すると、中間ステージ１３０のクロスバー相互接続ネットワーク１つだけのクロック速度を３倍スピードアップしたことと、第１および第２の内部リンクを３倍スピードアップしたことによって、３倍スピードアップを提供していることを除いて、図１Ａのスイッチファブリック１０の図と同様のスイッチファブリック３０を示す。図１Ａのネットワークの他の実施例では、中間ステージの各相互接続ネットワークは、共有メモリネットワークである。図３Ｂは、スイッチファブリック５０を示し、中間ステージ１３０の共有メモリ相互接続ネットワーク３つによって３倍のスピードアップを提供していることを除き、図１Ａのスイッチファブリック１０と同じである。図３Ｃは、スイッチファブリック６０を示し、中間ステージ１３０の共有メモリ相互接続ネットワーク１つだけのクロック速度を３倍スピードアップすることと、第１および第２の内部リンクを３倍スピードアップすることによって３倍スピードアップを提供していることを除き、図３Ａのスイッチファブリック３０と同じである。
【００６８】
同じく図３Ｄは、中間ステージ１３０のハイパーキューブ相互接続ネットワーク３つによって３倍スピードアップを提供していることを除いて、図１Ａのスイッチファブリック１０と同様のスイッチファブリック７０を示す。図３Ｅは、スイッチファブリック６０を示し、中間ステージ１３０のハイパーキューブベースの相互接続ネットワーク１つだけのクロック速度を３倍スピードアップしていることと、第１および第２の内部リンクを３倍スピードアップしていることによって３倍スピードアップを提供していることを除いて、図３Ａのスイッチファブリック３０と全く同じである。
【００６９】
図１Ａのスイッチファブリック１０、図１Ｉの１６、図１Ｎの１８、図２Ａの２０、図３Ａの３０、図３Ｂの５０、図３Ｃの６０、図３Ｄの７０、および図３Ｅの８０で、入力ポート１１０および出力ポート１２０の数は一般的に、各ステージごとに変数ｒで示されている。中間ステージ１３０でのスピードアップは、ｓで示されている。中間ステージ１３０でのスピードアップは、並列性、すなわち、（図４Ａ、図４Ｃおよび図４Ｅに示すような）３つの相互接続ネットワークによるか、（図４Ｂ、図４Ｄおよび図４Ｆに示すような）１つの相互接続ネットワークを３倍のスイッチング速度にすることによるかのどちらかで実現される。各入力ポート１５１−｛１５０＋ｒ｝のサイズは概して、ｒ＊ｓという表記で示され（各入力ポートがｒ個の入力キューを有し、ｓ個の第１内部リンクによってs個の相互接続ネットワークに接続されていることを意味する）、各出力 スイッチ１９１−｛１９０＋ｒ｝のサイズは一般的に、ｓ＊ｒという表記で示され（各出力ポートがｒ個の出力キューを有し、ｓ個の第２内部リンクによってｓ個の相互接続ネットワークに接続されていることを意味する）。同じく、中間ステージ１３０の各相互接続ネットワークのサイズは、ｒ＊ｒと示されている。ここで説明する相互接続ネットワークをクロスバーネットワークか、共有メモリネットワーク、またはサブネットワークのネットワークのどれかにすることができ、各サブネットワークは、クロスバーネットワークや、共有メモリネットワーク、３ステージのクロスネットワーク、ハイパーキューブ相互接続ネットワーク、内部ノンブロッキング相互接続ネットワーク、複数のネットワークを有するネットワークとすることができる。３ステージスイッチファブリックをＶ（ｓ，ｒ）という表記で表す。
【００７０】
必ずしも出力キュー１８１−｛１８０＋ｒ｝と同数の入力キュー１７１−｛１７０＋ｒ｝が必要というわけではないが、対称のネットワークでは、同数になる。ｓ個の中間ステージ 相互接続ネットワーク１３１−１３２の各々は、ｒ個の第１内部リンクを通じて、ｒ個の入力ポートの各々に接続され、ｒ個の第２内部リンクを通じて、出力ポートの各々に接続された。第１内部リンクＦＬｌ−ＦＬｒおよび第２内部リンクＳＬＩ−ＳＬｒの各々は、新規のパケットによる利用が可能であるか、あるいは、別のパケットによって既に取得されているのであれば、利用できないかのどちらかである。
【００７１】
図１Ａのスイッチファブリック１０は、図４Ａ の一般の対称のスイッチファブリックの例であり、中間ステージ１３０で、３つのクロスバー相互接続ネットワークを使用して、３倍のスピードアップを提供する。図４Ｂを参照すると、一般の対称の スイッチファブリックが示され、中間ステージ１３０で、クロスバー相互接続ネットワーク１つだけのクロック速度を３倍スピードアップすることと、第１および第２内部リンクを３倍スピードアップすることによって３倍スピードアップを提供していることを除いて、図４Ａのスイッチファブリックと同じである。
【００７２】
図４Ｃは、一般の対称の スイッチファブリックを示し、中間ステージ１３０でメモリ相互接続ネットワークを３つ使用し、３倍スピードアップを提供する。図４Ｄは、一般の対称の スイッチファブリックを示し、中間ステージ１３０で共有メモリ相互接続ネットワーク１つだけのクロック速度を３倍スピードアップすることと、第１および第２内部リンクを３倍スピードアップすることを使用して、３倍のスピードアップを提供する。
【００７３】
図４Ｅは、一般の対称の スイッチファブリックを示し、中間ステージ１３０で、３ステージクロス相互接続ネットワークを３つ使用することによって、３倍のスピードアップを提供する。 図４Ｆは、一般の対称のスイッチファブリックを示し、中間ステージ１３０で３ステージクロス相互接続ネットワークの１つのクロックスピードだけを３倍スピードアップすることと、第１および第２内部リンクを３倍スピードアップすることを使用して、３倍のスピードアップを提供する。
【００７４】
一般に、中間ステージ１３０の相互接続ネットワークは、次の相互接続ネットワークのどれかであればよい。すなわち、ハイパーキューブ相互接続ネットワークや、バッチャー−バンヤン相互接続ネットワーク、内部ノンブロッキング相互接続ネットワークのいずれか、あるいは複数のネットワークのネットワークである。一実施例では、相互接続ネットワーク１３１−１３３を３種の異なるネットワークとすることができ、例えば、相互接続ネットワーク１３１をクロスバーネットワーク、相互接続ネットワーク１３２を共有メモリネットワーク、さらに相互接続ネットワーク１３３をハイパーキューブネットワークとすることができる。 本発明によると、中間ステージで使用する相互接続ネットワークの種類に関係なく、図１Ｂの調停およびスケジューリング方法４０を使用し、厳密なノンブロッキング方式で、中間ステージでの３倍スピードアップがスイッチファブリックを作動する。また、再配置可能なノンブロッキング方式で、中間ステージの少なくとも２倍のスピードアップがスイッチファブリックを作動する。
【００７５】
スイッチファブリックのスピードアップが相互接続ネットワークの内部でのスピードアップに関係ないことに注目しなければならない。例えば、クロスバーネットワークおよび共有メモリネットワークは完全に接続される形態なので、内部でのスピードアップを何ら加えずに、内部的にノンブロッキングである。例えば、相互接続ネットワーク１３１−１３３は、図１Ａのスイッチファブリック１０や図３Ｂのスイッチファブリック５０のどちらでも、クロスバーネットワークまたは共有メモリネットワークであり、どちらの相互接続ネットワーク１３１−１３３でも、ノンブロッキング方式で動作可能とするためのスピードアップが不要である。しかしながら、相互接続ネットワーク１３１−１３３が３ステージのクロスネットワークである場合、各３ステージのクロスネットワークに、厳密なノンブロッキング方式で動作可能とするために、内部での３倍のスピードアップが必要となる。中間ステージ相互接続ネットワーク１３１−１３３が３ステージのクロスネットワークであるスイッチファブリックでは、３つの異なる ３ステージのクロスネットワーク１３１−１３３の形成に、３倍のスピードアップが提供される。さらに、３ステージのクロスネットワーク１３１−１３３が内部で厳密にノンブロッキングとなるように、ネットワーク１３１−１３３の各々にも、３倍スピードアップを加える必要がある。スイッチファブリックのスピードアップと相互接続ネットワークの内部のスピードアップとが異なることは明らかである。
【００７６】
これと同じく、中間ステージ１３１−１３３の相互接続ネットワークがハイパーキューブネットワークである場合、一実施例では、ｄ−ランク（２ｄのノードを備えた）ハイパーキューブで、ノンブロッキングネットワークとするために内部でのｄ倍のスピードアップが必要となる。本発明によると、中間ステージ相互接続ネットワーク１３１−１３３は、図１Ｂの調停およびスケジューリング方法４０を使用して、中間ステージで３倍スピードアップを用いる厳密なノンブロッキング方式で、スイッチファブリックを作動可能とするため、また、中間ステージで少なくとも２倍スピードアップした再配置可能なノンブロッキング方式で作動可能とするために、内部ノンブロッキング相互接続ネットワークであれば、いずれのネットワークであってもよい。
【００７７】
図４Ｇを参照すると、一実施例で、図３Ｄのスイッチファブリック７０および図３Ｅのスイッチファブリック８０の中間ステージ相互接続ネットワーク１３１−１３３を有する４×４ポート（２ランク）のハイパーキューブに基づく相互接続ネットワークの詳細図が示されている。４−ノードのハイパーキューブに００、０１、１０、１１という４つのノードがある。ノード００は、双方向リンクＡによってノード０１に接続される。ノード０１は、双方向リンクＢによってノード１１に接続される。ノード１１は、双方向リンクＣによってノード１０に接続される。ノード１０は、双方向リンクＤによってノード ００に接続される。また、４つのノードの各々は、スイッチファブリックの入力ポートおよび出力ポートに接続される。ノード００は、第１内部リンクＦＬ１および第２内部リンクＳＬ１に接続され、ノード０１は、第１内部リンクＦＬ２および第２内部リンクＳＬ２に接続される。ノード１０は、第１内部リンクＦＬ３および第２内部リンクＳＬ３に接続される。ノード１１は、第１内部リンクＦＬ４および第２内部リンクＳＬ４に接続される。図４Ｇに示したハイパーキューブネットワーク１３１−１３３が内部ノンブロッキングであるために、一実施例では、両方向に作動させるか、あるいは何倍かスピードアップするか、ハイパーキューブネットワークのスケジューリング構想によるかして、スイッチファブリックの入口リンク（または出口リンク）と同じ速度で、リンク Ａ、Ｂ、Ｃ、Ｄを作動させる必要がある。本発明によると、ハイパーキューブネットワークは、動作内部がノンブロッキング方式で動作することが必要であり、また、スイッチファブリックが図１Ｂの調停およびスケジューリング方法４０を使用して、３倍スピードアップした厳密なノンブロッキング方式で作動可能で、かつ、中間ステージで少なくとも２倍スピードアップし、再配置可能なノンブロッキング方式で作動可能でなければならない。
【００７８】
図４Ａ−４Ｆは、対称のスイッチファブリックの場合と同様に、等しい数の第１内部リンクおよび第２内部リンクを示しているが、非対称のスイッチファブリックにも本発明の範囲を拡張する。通常、マルチキャストパケットのスイッチング用の非対称のスイッチファブリック（ｒ１＊ｒ２）は、各入力ポートが入力キューｒ２を有する入力ポートｒ１と、各出力ポートが出力キューｒ１を有する出力ポートｒ２と、
2007510379.tif 000010
のスピードアップしたサブネットワークを有する相互接続ネットワークを備え、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクに対し、各入力ポートに接続された第１内部リンクを少なくとも１つ備え、全体で少なくともｒ２である第２内部リンクに対し、各出力ポートに接続された第２内部リンクを少なくとも１個さらに備えた非対称のスイッチファブリックであって、ｒ１≦ｒ２の場合、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時に、パケットのセグメント化および再組立を要さずに決定論的方式でスイッチされる多くてｒ１のパケットをスケジューリングすることによって、本発明に係る厳密なノンブロッキング方式で作動する。他の実施例では、スイッチファブリックは、ｒ２≦ｒ１であるときは、多くともｒ１回のスイッチングにおいてスイッチングすべき各スイッチング時に、多くともｒ２個のパケットを、決定論的方式で、またパケットのセグメント化及び再組立を必要とせず、スケジューリングすることにより、厳密なノンブロッキング方法で作動する。このスケジューリングは、２回以下のスイッチングで、２つ以下のサブネットワークを通じて、各マルチキャストパケットがファンアウト分割するように実行される。
【００７９】
このような一般の非対称のスイッチファブリックをＶ｛ｓ，ｒ１，ｒ２｝で示す。一実施例では、本システムは、調停を１回だけの反復と、相互接続ネットワークで数学的に最低限のスピードアップにより実行する。本システムはまた、スループット１００％、作業節約的、公正、さらに決定論的に作動することから、出力ポートが決して輻輳することがない。図１Ｂの調停およびスケジューリング方法４０は、スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝でパケットのスケジューリングにも使用される。
【００８０】
さらに、図１Ｂの調停およびスケジューリング方法４０は、スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝をノンブロッキング方式で作動させ、パケットをスループット１００％、作業節約的、公正な方式でスイッチングする。スイッチファブリックのスイッチング回数は、柔軟に設計できるパラメータでもあり、各スイッチング時で、バイト毎や数バイト毎にパケットをスイッチングするよう設定できる。本発明で説明するようにＳＡＲも必要ない。実施例のなかには、出力キューがなく、入力ポートでパケットを物理的にセグメント化し、かつ再組立しなくてはならないものがある。
【００８１】
同じく一実施例においては、マルチキャストパケットをスイッチングする非対称スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝は、ｒ１≦ｒ２であるときは多くともｒ２回のスイッチングにおいてスイッチングすべき各スイッチング時に、多くともｒ１個のパケットを、決定論的方式で、パケットのセグメント化および再組立を必要とせずにスケジューリングすることにより、相互接続ネットワークにおいて少なくとも
2007510379.tif 000011
のスピードアップを用いて再配置可能でノンブロッキング方式で作動する。別の実施例においては、非対称スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝は、ｒ２≦ｒ１であるときは多くともｒ１回のスイッチングにおいてスイッチングすべき各スイッチング時に、多くともｒ２個のパケットを、決定論的方式で、パケットのセグメント化および再組立を必要とせずにスケジューリングすることにより、相互接続ネットワークにおいて少なくとも
2007510379.tif 000012
のスピードアップを用いて再配置可能でノンブロッキング方式で作動する。このスケジューリングは、各マルチキャストパケットが、２つを超えないサブネットワークを介し、２回を超えないスイッチング回数でファンアウト分割されるように実行される。
【００８２】
マルチキャストパケットをスイッチングする非対称スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝であって、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポート、ｒ２個の出力ポート、及び少なくとも
2007510379.tif 000013
のスピードアップを有しｓ個のサブネットワーク持つ相互接続ネットワークを備え、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクのための各入力ポートに接続される少なくとも１個の第１内部リンクを備え、各サブネットワークはさらに全体で少なくともｒ２個の第２内部リンクのための各出力ポートに接続される少なくとも１個の第２内部リンクを備えた、非対称スイッチファブリックは、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時に、多くともｒ１個のパケットを、決定論的方式で、パケットのセグメント化及び再組立を必要としてスケジューリングすることにより、本発明にかかる、厳密にノンブロッキング方式で作動する。このスケジューリングは、各マルチキャストパケットが、２つを超えないサブネットワークを介し、２回を超えないスイッチング回数でファンアウト分割されるように実行される。図１Ｂの調停及びスケジューリング方法４０は、出力キューを使用せずにスイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝においてパケットをスイッチングするのにも使用される。
【００８３】
マルチキャストパケットをスイッチングする非対称スイッチファブリックＶ｛ｓ，ｒ１，ｒ２｝であって、各入力ポートがｒ２個の入力キューを有するｒ１個の入力ポート、ｒ２個の出力ポート、及び
2007510379.tif 000014
のスピードアップを有し、ｓ個のサブネットワークを持つ相互接続ネットワークを備え、各サブネットワークは、全体で少なくともｒ１個の第１内部リンクのための各入力ポートに接続される少なくとも１つの第１内部リンクを備え、各サブネットワークはさらに全体で少なくともｒ２個の第２内部リンクのための各出力ポートに接続される少なくとも１つの第２内部リンクを備えた非対称スイッチファブリックは、多くともｒ２回のスイッチングにおけるスイッチングすべき各スイッチング時に、多くともｒ１個のパケットを、決定論的方式で、パケットのセグメント化及び再組立を必要として、ウェイトレートに応じてスケジューリングすることにより、本発明にかかる、再配置可能でノンブロッキング方式で作動する。このスケジューリングは、各マルチキャストパケットが、２つを超えないサブネットワークを介し、２回を超えないスイッチング回数でファンアウト分割されるように実行される。
【００８４】
出願者はここで、本発明において記述するすべてのスイッチファブリックは、入力ポート対出力ポートのレート及び保証待ち時間を提供することに注目する。エンドツーエンド保証帯域幅、即ち、任意の入力ポートから任意出力ポートまでの保証帯域幅は、ユニキャスト及びマルチキャストパケットの入力キューの出力キューに対する割当に基づいて提供される。一定の保証待ち時間は、複数の入力ポートから任意の出力ポートへのパケットに提供される。各入力ポートは、宛先出力ポート内のその割当出力キューの中にパケットをスイッチングするので、１つの入力ポートからのパケットは、２番目の入力ポートから同一出力ポート内に別のパケットがスイッチングされるのを妨げないので、すべての入力ポートからのパケットの保証待ち時間は、強化される。スイッチファブリックのスイッチング回数は、各フローにおけるパケットの待ち時間、及び各パケットのパケットセグメントの待ち時間も判定する。
【００８５】
図５Ａは、図１Ｂの調停及びスケジューリング方法４０のアクト４４の実施を示す。アクト４４においては、ｒ２個のパケットのスケジューリングが実行される。アクト４４Ａにおいては、スケジューリングするパケットがさらに存在するか否かを点検する。さらにスケジューリングするパケットがあるとき、即ち、ｒ２個のすべてのパケットがスケジューリングされていないときは、制御は、４４Ｂ１に移る。アクト４４Ｂ１においては、ｒ回のスケジューリングのいずれかを介して中間ステージの３つの相互接続ネットワークのうち１つを通る経路が空いているか否かを点検する。答が「はい」であるとき、制御は、アクト４４Ｃに移る。アクト４４Ｂ１における答が「いいえ」であるとき、制御はアクト４４Ｂ２に移る。アクト４４Ｂ２においては、１回のスイッチング時又はｒ回のスケジューリングのうち任意の２回のいずれかにおける経路２つと相互接続ネットワークを２つだけを、パケット要求のすべての宛先出力ポートまでの利用可能な経路を確保するように検索する。本発明によれば、パケット要求のすべての宛先出力ポートに対し空いた経路があるように、中間ステージ相互接続ネットワーク２つを見出すことは、常に可能である。次に、制御は４４Ｃに移る。パケットは、アクト４４Ｃにおいて選択された１つの経路又は２つの経路を介してスケジューリングされる。４４Ｄにおいては、同一スケジューリング時に別のパケットがこれらのリンクを選択しないよう、選択した第１及び第２内部リンクに選択済みの標識を付ける。次に、制御は４４Ａに戻り、こうして４４Ａ、４４Ｂ、４４Ｃ、及び４４Ｄはループで実行され、各パケットをスケジューリングする。
【００８６】
図５Ｂは、図５Ａの方法４４の方法のアクト４４Ｂ、４４Ｃ、及び４４Ｄの１つの変形の低レベルフローチャートである。４４ＢＡ１に対する制御は、スケジューリングすべき新規パケットがあるとき、アクト４４Ａから移る。アクト４４ＢＡ１は、新規パケット要求にｃを割当て、インデックス変数ｉは、（１，１）を割当てられ、それぞれスケジューリング回数１及び相互接続ネットワーク１を表す。次に、アクト４４ＢＡ２は、ｉは（ｒ，３）より大きいか否かを点検する。これは、ｒ回のスケジューリングすべてにおいて、３つの相互接続ネットワークすべてが点検されるか否かを意味する。答が「いいえ」であるとき、制御はアクト４４ＢＡ４に移る。アクト４４ＢＡ４は、パケット要求ｃが、スケジューリング時ｉ．１（ここで、ｉ．１はタプルｉの第１要素、ｉ．２は第２要素を表す）において、相互接続ネットワークｉ．２に対する利用可能な第１内部リンクを有しないか否かを点検する。答が「いいえ」であるときは、アクト４４ＢＡ５において、２つのセット、即ちＯｉとＯｋを生成し、ｉからの利用可能なリンクを有するｃの宛先スイッチのセットと有しない宛先スイッチのセットをそれぞれ判定する。アクト４４ＢＡ６においては、Ｏｉはパケット要求ｃの必要とする宛先出力ポートすべてを有するか否かを点検する。答が「はい」であるときは、制御は４４Ｃ１に移り、ここでスケジューリングｉ．１時の相互接続ネットワークｉ．２を介して、パケット要求はスケジューリングされる。アクト４４Ｄ１は、ｉへの出入りに使用した第１及び第２内部リンクに利用不可の標識を付ける。アクト４４Ｄ１から、制御はアクト４４Ａに移る。
【００８７】
アクト４４ＢＡ４における答が「はい」であるときは、制御はアクト４４ＢＡ１３に移る。アクト４４ＢＡ１３においては、ｉ．２が３未満のときは、ｉ．２を１だけ増加させるようにタプルｉを調節して、同一スケジューリングｉ．１における次の相互接続ネットワークを点検する。ｉ．２が３に等しいときは、ｉ．１を１だけ増加させるようにタプルｉを調節して、次のスケジューリング及び相互接続ネットワーク１を点検する。次に、制御はアクト４４ＢＡ２に移る。本発明によれば、アクト４４ＢＡ２は、決して「はい」の結果にならないので、アクト４４ＢＡ３には、決して到達しない。このように、アクト４４ＢＡ２、４４ＢＡ４、４４ＢＡ５、４４ＢＡ６、４４ＢＡ７、４４ＢＡ８、及び４４ＢＡ１３は、二重ネストループの外側ループを形成し、パケット要求ｃをスケジューリングする。
【００８８】
アクト４４ＢＡ６が「いいえ」の結果になるときは、制御はアクト４４ＢＡ７に移る。アクト４４ＢＡ７においては、別のインデックス変数ｊに、それぞれスケジューリング回数１及び相互接続ネットワーク１を意味する（１，１）が割当てられる。次に、アクト４４ＢＡ８で、ｊは（ｒ，３）より大きいか否かを点検する。これは、ｒ回のスケジューリングすべてにおける３つのすべての相互接続ネットワークが点検されるか否かを意味する。答が「いいえ」であるとき、制御はアクト４４ＢＡ９に移る。アクト４４ＢＡ９においては、ｉがｊに等しいか否か、即ち、ｉ．１はｊ．１に等しく且つ、ｉ．２もｊ．２に等しいか否かを点検する。アクト４４ＢＡ９が「いいえ」の結果になるときは、制御はアクト４４ＢＡ１０に移る。アクト４４ＢＡ１０においては、Ｏjのセットが生成され、ｊからの利用可能なリンクを有するｃの宛先スイッチのセットを判定する。アクト４４ＢＡ１１においては、ＯkはＯjのサブセットであるか否かを点検する。答が「はい」であるときは、パケット要求ｃが、タプルｉ及びｊで表示される２つの相互接続ネットワークを介してすべての宛先出力ポートまで、空いた経路を有することを意味する。その場合、アクト４４Ｃ２において、パケット要求は、パケット要求ｃの入力ポートにおいて２回ファンアウトすることにより、スケジューリングｉ．１の相互接続ネットワークｉ．２及びスケジューリングｊ．１の相互接続ネットワークｊ．２を介してスケジューリングされる。アクト４４Ｄ２は、使用したｉ及びｊ双方に出入する第１及び第２内部リンクに利用不可の標識を付ける。制御は、アクト４４Ｄ２からアクト４４Ａに移る。
【００８９】
アクト４４ＢＡ１１が「いいえ」の結果になるときは、制御はアクト４４ＢＡ１２に移る。また、アクト４４ＢＡ９が「いいえ」の結果になるときは、制御はアクト４４ＢＡ１２に移る。アクト４４ＢＡ１２においては、ｊ．２が３未満のときは、ｊ．２を１だけ増加させるようにタプルｊを調節して、同一スケジューリング時ｊ．１における次の相互接続ネットワークを点検する。ｊ．２が３に等しいときは、ｊ．１を１だけ増加させるようにタプルｊを調節して、次のスケジューリング及び相互接続ネットワーク１を点検する。次に制御は、アクト４４ＢＡ８に移る。また、アクト４４ＢＡ２が「はい」の結果になるときは、制御はアクト４４ＢＡ１３に移る。このように、アクト４４ＢＡ８、４４ＢＡ９、４４ＢＡ１０、４４ＢＡ１１、及び４４ＢＡ１２は、二重ネストループの内側ループを形成し、パケット要求ｃをスケジューリングする。
【００９０】
次の方法は、図４Ａ−４Ｆのスイッチファブリックの中間ステージ１３０で（３つの相互接続ネットワークを用いるか、又はクロック速度とリンク速度において３倍のスピードアップのいずれかを用いる）３倍のスピードアップを用いて厳密なノンブロッキング方式でｒ２個のパケットをスケジューリングする、図５Ａのスケジューリング方法４４のアクト４４Ｂ、４４Ｃ、４４Ｄの一実装のための擬似コードを示す。
【００９１】
スケジューリング方法の疑似コード
ステップ１：  ｃ＝現在のパケット要求
ステップ２：  ｆｏｒ ｉ= 各スケジューリングにおける相互接続ネットワーク実行｛
ステップ３： もし（ｃ にはｉに対する利用可能リンクがない）継続；
ステップ４：          Ｏｉ＝ｉから利用可能なリンクを有するｃのすべての宛先出力ポ
ートのセット
ステップ５：          Ｏk＝ｉから利用可能なリンクのないｃのすべての宛先出力ポート
のセット
ステップ６：    ｉｆ（Ｏｉ＝ｃの必要とされるすべての宛先出力ポート）｛
ｉを介してｃ をスケジューリング；
使用したｉに出入りするすべてのパスに利用不可の標識を付ける
｝
ステップ７：  ｆｏｒ ｊ＝ 各スケジューリング時の各相互接続ネットワーク
実行｛
ステップ８：      ｉｆ（ｉ＝ｊ）｛
継続；
ステップ９：      ｝ｅｌｓｅ｛
Ｏj＝ｊから利用可能なリンクを有するｃのすべての宛先出力ポ
ートのセット
ステップ１０：        ｉｆ（Ｏk⊆Ｏj）｛
ｉとｊを介してｃをスケジューリング；
使用したｉとｊに出入りするすべての経路に利用不可の標
識を付ける
｝
｝
｝
｝
【００９２】
上記のステップ１は、現在のパケット要求に“ｃ”のラベルを付ける。ステップ２は、ｒ回のスケジューリングそれぞれにおいてすべての相互接続ネットワークを介して二重ネストループの外側ループを開始する。ｃの入力スイッチに、ｉで表すスケジューリングの相互接続ネットワークへの利用可能なリンクが無いときは、ステップ３において、ｉとなるべき、同一スケジューリングにおける次の相互接続ネットワーク、又は次のスケジューリングにおける最初の相互接続ネットワークが選択される。ステップ４及び５は、ｉからの利用可能なリンクを有するｃの宛先出力ポートのセットと有さないｃの宛先出力ポートのセットをそれぞれ判定する。ステップ６においては、ｉで表すスケジューリングにおける相互接続ネットワークが、パケット要求ｃのすべての宛先出力ポートへの利用可能なリンクを有するときは、ｉで表すスケジューリングにおける相互接続ネットワークを介してパケット要求ｃを設定する。また、ｉで表すスケジューリングにおける相互接続ネットワークの出力ポートまで及び入力ポートからの使用したリンクすべてに、今後の要求のために利用不可の標識が付けられる。ステップ７は、内側ループを開始してスケジューリングにおけるすべての相互接続ネットワークを通過し、スケジューリングにおける第２相互接続ネットワークを検索し、ｉがｊと同一であるときは、ステップ８が、ｊとなるべき同一スケジューリング時の次の相互接続ネットワーク、又は次のスケジューリング時における最初の相互接続ネットワークの選択を継続する。ステップ９は、ｊからの利用可能なリンクを有するすべての宛先出力ポートのセットを判定する。そしてステップ１０において、ｉから利用不可のすべてのリンクが、ｊから利用可能であるときは、ｉ及びｊを介してパケット要求ｃはスケジューリングされる。ｉ及びｊから出力ポートまでの、使用したすべての経路には、利用不可の標識が付けられる。これらのステップは、ｒ回の各スケジューリングにおいて、すべての相互接続ネットワークのすべてのペアについて繰り返される。ｒ回のスケジューリングのうち１回又は２回における１つ又は２つの相互接続ネットワークは、常に見出すことができ、それを介してｃをスケジューリングすることができる。このスケジューリング方法が実行するステップの数は、ｓ２＊ｒ２に比例し、その際ｍはネットワーク内の中間スイッチの数であり、したがってこのスケジューリング方法は、時間複雑度Ｏ（ｓ２＊ｒ２）の性質を持つことに気付くのは容易である。
【００９３】
スイッチファブリックの厳密にノンブロッキングなスケジューリングにおいては、パケット要求を入力キューから出力キューまでスケジューリングするため、既にスケジューリングされたパケットの経路を妨げることなくその要求を満足する、相互接続ネットワークを介した経路を見出すことは常に可能であり、このような経路が１つを超えて利用可能なときは、それらの中の任意の経路を、残りのパケット要求のスケジューリングについて心配することなく選択することができる。厳密なノンブロッキングネットワークにおいては、スイッチハードウエアのコストは上昇するが、パケットをスケジューリングするのに必要な回数は、再配置可能なノンブロッキングスイッチファブリックに比較して減少する。時間複雑度Ｏ（ｓ２＊ｒ２）の図５Ａのスケジューリング方法４４を用いる、中間ステージに３倍のスピードアップを使用する厳密なノンブロッキングスイッチファブリックの実施例を、図１Ａのスイッチファブリック１０及び図１Ｉのスイッチファブリック１６に示す。
【００９４】
再配置可能なノンブロッキングスイッチファブリックにおいて、スイッチハードウエアのコストは、パケットをスイッチングするために必要な時間の増加を犠牲に、削減される。再配置可能なノンブロッキングスイッチファブリックにおけるスケジューリング時間は、新規パケットのスケジューリングに加えて、再配置を実施するため分断されたスケジューリング済みのパケットの経路を、再度スケジューリングする必要があるために、増加する。このため、新規パケットをスケジューリングするときは、スケジューリング済みパケットの再配置の必要性を最小限にするか、寧ろ除去するのが望ましい。再配置の必要性が除去されると、そのネットワークは、中間ステージ相互接続ネットワーク及びスケジュール方法次第で、厳密なノンブロッキングである。中間ステージにおいて２倍のスピードアップを用いる、再配置可能なノンブロッキングスイッチファブリックの一実施例を、図１Ｎのスイッチファブリック１８に示す。要求の生成、許可の発行、及び承認の生成の調停は、スイッチファブリックを厳密なノンブロッキング方式で作動させるか、又は再配置可能ノンブロッキング方式で作動させるかに関わりなく、たった１度の繰り返しで実行されることに注目しなければならない。
【００９５】
本発明に記述する厳密なノンブロッキングスイッチファブリックは、Ｏ（ｓ２＊ｒ２）時間複雑度のスケジュール方法を必要とする。中間ステージ相互接続ネットワークにおけるスピードアップをさらに増加すると、スケジュール方法時間複雑度はＯ（ｓ＊ｒ）に減少する。線形スケジューリング時間複雑度を有する厳密なノンブロッキングスイッチファブリックは、上で参照して組込まれる「STRICTLY NON-BLOCKING MULTICAST LINEAR-TIME MULTI-STAGE NETWORKS」と題する,関連米国特許出願番号１０／９３３，８９９号、並びににそのＰＣＴ出願番号０４／２９０４３号、及び「STRICTLY NON-BLOCKING MULTICAST MULTI-SPLIT LINEAR-TIME MULTI-STAGE NETWORKS」と題する、関連米国特許出願番号１０／９３３，９００号並びにそのＰＣＴ出願番号０４／２９０２７号、に記述されている。出願者は、スイッチファブリックは、これら２つの関連米国特許の記述にあるように、中間ステージにおけるスピードアップを直接拡大することにより、またそれにより線形時間複雑度のスケジューリング方法を用いることにより、厳密なノンブロッキング方式で作動させることもできることに注目する。
【００９６】
したがって、追加のスピードアップと、それによる線形時間複雑度のスケジューリング方法を用いて、図６Ａは、図１Ｂの調停及びスケジューリング方法４０のアクト４４の、一実施を示す。アクト４４においては、ｒ２個のパケットのスケジューリングが実行される。アクト４４においては、スケジューリングすべきさらなるパケットがあるか否かを点検する。スケジューリングすべきさらなるパケットがあるとき、即ち、ｒ２個のすべてのパケットがスケジューリングされていないとき、制御は４４Ｂに移る。アクト４４Ｂにおいては、中間ステージにおける３つの相互接続ネットワークのうち１つを介した空き経路を、ｒ回のスケジューリングを介して検索することにより選択する。パケットは選択された経路及び選択されたスケジューリング回数を介して、アクト４４Ｃにおいて、スケジューリングされる。４４Ｄにおいては、選択された第１内部リンク及び第２内部リンクに、選択済みの標識を付け、同一スケジューリング時に他のパケットがこれらのリンクを選択しないようにする。次に、制御はアクト４４Ａに戻り、このようにアクト４４Ａ、４４Ｂ、４４Ｃ、及び４４Ｄがループで遂行され、それぞれのパケットをスケジューリングする。
【００９７】
図６Ｂは、図６Ａのアクト４４の一変形の低レベルのフローチャートを示す。アクト４４は、スケジューリングする新規パケットがあるとき、制御を４４Ｂに移す。アクト４４Ｂ１は、新規パケット要求をｃに割当てる。アクト４４Ｂ２においては、スケジューリング回数１がインデックス変数ｉに割当てられる。次にアクト４４Ｂ３において、ｉがスケジューリング回数ｒより小さいか又は等しいかを点検する。答が「はい」であるとき、制御は４４Ｂ４に移る。アクト４４Ｂ４において、別のインデックス変数ｊを相互接続ネットワーク１に設定する。アクト４４Ｂ５は、ｊは相互接続ネットワーク１−ｘの何れであるかを点検する、ｘの値は関連米国仮特許申請において記述されている通りである。答が「はい」であるとき、制御はアクト４４Ｂ６に移る。アクト４４Ｂ６は、パケット要求ｃがスケジューリングｉにおいて相互接続ネットワークｊへの利用可能な第１内部リンクを有しないかを点検する。答が「いいえ」であるとき、アクト４４Ｂ７が、スケジューリングｉにおいて相互接続ネットワークｊはパケット要求ｃの宛先出力ポートへの利用可能な第２内部リンクを有しないことを点検する。答が「いいえ」であるとき、制御はアクト４４Ｃに移る。アクト４４Ｃにおいて、スケジューリングｉにおける相互接続ネットワークｊを介してパケット要求ｃをスケジューリングし、次に、アクト４４Ｄにおいて、スケジューリングｉにおける相互接続ネットワークｊに対応する第１及び第２の内部リンクに、使用済みの標識が付けられる。次に、制御は４４Ａに進む。アクト４４Ｂ６又はアクト４４Ｂ７の何れかにおいて「はい」の結果となるとき、制御はアクト４４Ｂ９に移り、そこでｊを１だけ増加させてから制御はアクト４４Ｂ５に進む。アクト４４Ｂ５において「いいえ」の結果となるとき、制御はアクト４４Ｂ１０に移る。アクト４４Ｂ１０は、ｉを１だけ増加してから、制御はアクト４４Ｂ３に移る。アクト４４Ｂ３が「いいえ」の結果になることは決してなく、それはパケット要求ｃが、ｒ回のスケジューリング時において、スケジューリングされることが保証されることを意味する。アクト４４Ｂは２つのループを含む。内側ループは、アクト４４Ｂ５、４４Ｂ６、４４Ｂ７、及び４４Ｂ９を含む。外側ループは、アクト４４Ｂ３、４４Ｂ４、４４Ｂ５、４４Ｂ６、４４Ｂ７、４４Ｂ９、及び４４Ｂ１０を含む。アクト４４は、ｒ２個のパケット要求すべてがスケジューリングされるまで、すべてのパケット要求について繰り返される。
【００９８】
以下の方法は、図６Ａのスケジューリング方法４４の一実施例のための、ｒ２個のパケット要求を、図４Ａ−４Ｆのスイッチファブリックにおける中間ステージ１３０に（３つの相互接続ネットワークを用いるか、又はクロック速度およびリンク速度において３倍のスピードアップいずれかを用いる）３倍のスピードアップを用いて、厳密なノンブロッキング方式でスケジューリングする疑似コードを示す。
【００９９】
スケジューリング方法の疑似コード
ステップ１：  各パケット要求のスケジューリング  実行｛
ステップ２：  ｃ＝パケットスケジューリング要求；
ステップ３：  ｆｏｒ  ｉ＝ｓｈｅｄ＿ｔｉｍｅ＿１  ｔｏ  ｓｈｅｄ＿ｔｉｍｅ＿ｒ  ｄｏ｛
ステップ４：      ｆｏｒ  ｊ＝ｉｎｔｅｒ＿ｃｏｎｎ＿ｎｅｔ＿１  ｔｏｉｎｔｅｒ＿ｃｏｎｎ＿ｎｅｔ＿ｘ  ｄｏ｛
ステップ５：ｉｆ（ｃにはｊまでの利用可能な第１内部リンクがない）継続；
ステップ６：ｅｌｓｅｉｆ（ｊにはｃの宛先出力ポートまでの利用可能な第２内部リンク
がない）継続；
ステップ７：          ｅｌｓｅ｛
スケジューリング１に相互接続ネットワークｊを介してｃを
スケジューリング；
相互接続ネットワークｊに出入する使用済みリンクに利用不
可と標識；
｝
｝
｝
｝
【０１００】
ステップ１は、各パケットをスケジューリングするループを開始する。ステップ２は、現在のパケット要求に“ｃ”のラベルを付ける。ステップ３は、第２ループを開始し、ｒ個のスケジューリングすべてを通過する。ステップ４は、第３ループを開始して、ｘ個の相互接続ネットワークすべてを通過する。ステップ５において、パケット要求ｃの入力ポートが、スケジューリングｉにおいて利用可能な相互接続ネットワークｊへの第１内部リンクを有しないときは、制御はステップ４に移って、ｉとなるべき次の相互接続ネットワークを選択する。ステップ６は、パケット要求ｃの宛先出力ポートがスケジューリングｉにおいて利用可能な相互接続ネットワークｊへの第２内部リンクを有しないか否かを点検し、そうであるときは、制御はステップ４に移って、ｉとなるべき次の相互接続ネットワークを選択する。ステップ７においては、パケット要求ｃを、スケジューリングｉにおいて相互接続ネットワークｊ を介して設定する。また、スケジューリングｉにおける相互接続ネットワークｊ への第１および第２内部リンクには、今後のパケット要求のため、利用不可の標識が付けられる。これらのステップは、ｒ回のすべてのスケジューリングにおいてｘ個のすべての相互接続ネットワークについて、利用可能な第１及び第２内部リンクが見出されるまで、繰り返される。本発明により、それを介してパケット要求ｃをスケジューリングすることのできる１つの相互接続ネットワークを、ｒ回のうちの１回のスケジューリングに見出すことができる。このスケジューリング方法が実行するステップの数は、ｓ＊ｒに比例し、その際ｓはｘに等しいスピードアップ、ｒはスケジューリング回数の数であり、したがって、このスケジュール方法が、時間複雑度Ｏ（ｓ＊ｒ）の性質を持つことに気付くのは容易である。
【０１０１】
表６に、特定の一実施例において、上述の疑似コードのステップ１−８が図６Ｂに示す方法のフローチャートの実施方法を示す。
【０１０２】
【表６】
2007510379.tif 000015
【０１０３】
また、本発明により、スイッチファブリックがノンブロッキング方式で作動するため、中間ステージ１３０に必要なスピードアップの直接の拡張は、出力ポートにスイッチングされる前にパケットに付加された制御ビットの数に応じて比例的に調節される。例えば、（パケットを入力ポートから出力ポートにスイッチングするだけのため、これらの制御ビットを導入する場合に）入力ポートから出力ポートにスイッチングするパケット又はパケットセグメント毎に１％の付加制御ビットを追加すると、スイッチファブリックのため中間ステージ１３０において必要なスピードアップは、厳密なノンブロッキング方式で作動させるには、３．０１であり、再配置可能なノンブロッキング方式で作動させるには２．０１である。
【０１０４】
同様に、本発明によれば、パケットがセグメント化されて出力ポートにスイッチングされる場合、最後のパケットセグメントは、パケットセグメントと同一であることも、同一でないこともある。その代わり、パケットのサイズがパケットセグメントのサイズの完全な倍数でない場合、スイッチファブリックのスループットは１００％未満になる。最後のパケットセグメントが頻繁にパケットセグメントより小さい場合は、システムを１００％スループットで作動させるため、中間ステージにおけるスピードアップを比例的に増加する必要がある。
【０１０５】
本発明のノンブロッキングで決定論的スイッチファブリックは、任意に大きい数の入力キューに直接拡張することができる。即ち、各入力ポート内の１つより多い入力キューが、宛先出力ポート内の１つより多い出力キューにスイッチングすること、およびすべての入力ポート内の各入力キューが異なるマルチキャストフロー、又はマルチキャストのグループのマイクロフローを保持することが、レート及び保証待ち時間を有するフロー毎のＱｏＳを提供することができる。エンドツーエンド保証帯域幅、即ち、入力ポートの様々な入力キューにおける任意の宛先出力ポートまでのフローを提供することができる。その上、保証された一定の待ち時間を、入力ポートにおける複数の入力キューから任意の宛先出力ポートまでのパケットのフローに提供する。入力ポートにおける各入力キューは様々なフローを保持しているが、パケットを同一宛先出力ポートの中にスイッチングするので、１つの入力キューからの長いパケットは、同一入力ポートの第２の入力キューからの別の小さいパケットが同一宛先出力ポートの中にスイッチングされるのを妨げない。こうして、入力ポートからのパケットのフローの保証待ち時間を強化する。ここでも、スイッチファブリックのスイッチング回数が、各フローにおけるパケットの待ち時間及び各パケット内のパケットセグメントの待ち時間を判定する。
【０１０６】
入力キューから出力ポートの中に別個にスイッチングされるマルチキャストのフローの数を増加させることにより、エンドツーエンド保証帯域幅、及び待ち時間を、細かい粒度のフローのため提供することができる。また、各フローを個別に形成することもでき、必要に応じて、予約過多の状況下では、予測して所望のフローからパケットの末尾廃棄（tail dropping）し、サービスプロバイダに、個々のフローに対しレートと保証待ち時間とを提案する機会を与え、それにより追加の収入の機会を可能にする。
【０１０７】
ここに記述した実施例、実施、及び模範例に関する多数の変更及び翻案は、開示の観点から当業者には明らかであろう。
【０１０８】
本発明に記述する実施例は、パラレルコンピュータ、ビデオサーバ、負荷バランサ、及びグリッド計算アプリケーションの用途においても直接有用である。本発明に記述する実施例は、ハイブリッドスイッチ、及びルータにおいて、両回路を時間割で切り換え、及びパケットをパケット又はセルで切り換えるのにも有用である。
【０１０９】
このような多数の変更及び翻案は、添付請求項に包含される。
【図面の簡単な説明】
【０１１０】
【図１Ａ】本発明にかかる、短いパケット及び、クロスバーに基づく相互接続ネットワークにおける３倍のスピードアップを含む入力及び出力マルチキャストキューを有する模範的な４×４ポートのスイッチファブリックの図である。
【図１Ｂ】パケットを入力ポートから出力ポートにスイッチングするのに使用される、本発明にかかる、調停及びスケジューリング方法４０の高レベルフローチャートである。
【図１Ｃ】図１Ａのスケジューリングスイッチファブリック１０おける場合と同様の３ステージネットワークの図である。
【図１Ｄ】本発明にかかる連続する５回のスイッチング時における、ノンブロッキングで決定論的パケットスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。
【図１Ｅ】本発明にかかる連続する５回のスイッチング時における、ノンブロッキングで決定論的パケットスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。
【図１Ｆ】本発明にかかる連続する５回のスイッチング時における、ノンブロッキングで決定論的パケットスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。
【図１Ｇ】本発明にかかる連続する５回のスイッチング時における、ノンブロッキングで決定論的パケットスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。
【図１Ｈ】本発明にかかる連続する５回のスイッチング時における、ノンブロッキングで決定論的パケットスイッチング後の図１Ａのスイッチファブリック１０の状態を示す。
【図１Ｉ】本発明にかかる、長いパケット及び、クロスバーに基づく相互接続ネットワークにおける３倍のスピードアップを含む、入力及び出力マルチキャストキューを有する模範的な４×４ポートのスイッチファブリックの図である。
【図１Ｊ】本発明にかかるパケットのセグメント化及び再組立の無いノンブロッキングで決定論的パケットスイッチング後の、連続する４回のファブリックスイッチングサイクル後における、図１Ｉのスイッチファブリック１６の状態を示す。
【図１Ｋ】本発明にかかるパケットのセグメント化及び再組立の無いノンブロッキングで決定論的パケットスイッチング後の、連続する４回のファブリックスイッチングサイクル後における、図１Ｉのスイッチファブリック１６の状態を示す。
【図１Ｌ】本発明にかかるパケットのセグメント化及び再組立の無いノンブロッキングで決定論的パケットスイッチング後の、連続する４回のファブリックスイッチングサイクル後における、図１Ｉのスイッチファブリック１６の状態を示す。
【図１Ｍ】本発明にかかるパケットのセグメント化及び再組立の無いノンブロッキングで決定論的パケットスイッチング後の、連続する４回のファブリックスイッチングサイクル後における、図１Ｉのスイッチファブリック１６の状態を示す。
【図１Ｎ】本発明にかかる、入力及び出力マルチキャストキュー及び、クロスバーに基づく相互接続ネットワークにおける２倍のスピードアップを有する模範的な４×４ポートスイッチファブリックの図である。
【図２Ａ】本発明にかかる、入力マルチキャストキュー、及びクロスバーに基づく相互接続ネットワークにおける３倍のスピードアップを有する模範的な４×４ポートのスイッチファブリックの図である。
【図２Ｂ】本発明にかかるノンブロッキングで決定論的パケットスイッチング後の、連続する５回のスイッチング時における図２Ａのスイッチファブリック２０の状態を示す。
【図２Ｃ】本発明にかかるノンブロッキングで決定論的パケットスイッチング後の、連続する５回のスイッチング時における図２Ａのスイッチファブリック２０の状態を示す。
【図２Ｄ】本発明にかかるノンブロッキングで決定論的パケットスイッチング後の、連続する５回のスイッチング時における図２Ａのスイッチファブリック２０の状態を示す。
【図２Ｅ】本発明にかかるノンブロッキングで決定論的パケットスイッチング後の、連続する５回のスイッチング時における図２Ａのスイッチファブリック２０の状態を示す。
【図２Ｆ】本発明にかかるノンブロッキングで決定論的パケットスイッチング後の、連続する５回のスイッチング時における図２Ａのスイッチファブリック２０の状態を示す。
【図３Ａ】本発明にかかる、入力及び出力マルチキャストキュー及び、クロスバーに基づく相互接続ネットワークにおけるリンク速度とクロック速度が３倍のスピードアップを有する模範的な４×４ポートのスイッチファブリック図である。
【図３Ｂ】本発明にかかる、入力及び出力マルチキャストキュー及び、共有メモリに基づく相互接続ネットワークにおける３倍のスピードアップを有する模範的な４×４ポートのスイッチファブリックの図である。
【図３Ｃ】本発明にかかる入力及び出力マルチキャストキュー及び、共有メモリに基づく相互接続ネットワークにおけるリンク速度とクロック速度における３倍のスピードアップを有する模範的な４×４ポートスイッチファブリックの図である。
【図３Ｄ】本発明にかかる、入力及び出力マルチキャストキュー及び、ハイパーキューブに基づく相互接続ネットワークにおける３倍のスピードアップを有する模範的な４×４ポートスイッチファブリックの図である。
【図３Ｅ】本発明にかかる、入力及び出力マルチキャストキュー及び、ハイパーキューブに基づく相互接続ネットワークにおける３倍のスピードアップを有する模範的な４×４ポートスイッチファブリックの図である。
【図４Ａ】本発明にかかる、入力及び出力マルチキャストキュー及び、クロスバーに基づく相互接続ネットワークにおける３倍のスピードアップを有する一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｂ】本発明にかかる、入力及び出力マルチキャストキュー及び、クロスバーに基づく相互接続ネットワークにおいて、リンク速度とクロック速度が３倍のスピードアップを有する、一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｃ】本発明にかかる、入力及び出力マルチキャストキュー及び、共有メモリに基づく相互接続ネットワークにける３倍のスピードアップを有する一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｄ】本発明にかかる、入力及び出力マルチキャストキュー及び、共有メモリに基づく相互接続ネットワークにおいて、リンク速度とクロック速度が３倍のスピードアップを有する一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｅ】本発明にかかる、入力及び出力マルチキャストキュー及び、３ステージクロスネットワークに基づく相互接続ネットワークにおける３倍のスピードアップを有する一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｆ】本発明にかかる、入力及び出力マルチキャストキュー及び、３ステージクロスネットワークに基づく相互接続ネットワークにおける、リンク速度とクロック速度が３倍のスピードアップを有する一般的ｒ＊ｒポートスイッチファブリックの図である。
【図４Ｇ】図３Ｄのスイッチファブリック７０及び図３Ｅのスイッチファブリック８０における中間ステージ相互接続ネットワーク１３１−１３３の一実施例における４×４ポート（２−ランク）ハイパーキューブに基づく相互接続ネットワークの詳細図を示す。
【図５Ａ】図１Ｂの調停及びスケジューリング方法４０のアクト４４の中間レベル実施である。
【図５Ｂ】図５Ａのアクト４４の一変形の低レベルのフローチャートである。
【図６Ａ】線形時間複雑度スケジューリング方法を用いる図１Ｂの調停及びスケジューリング方法４０のアクト４４の中間レベルの実施である。
【図６Ｂ】図６Ａのアクト４４の一変形の低レベルのフローチャートである。
【図１Ａ】
2007510379.tif 000018
【図１Ｂ】
2007510379.tif 000019
【図１Ｃ】
2007510379.tif 000020
【図１Ｄ】
2007510379.tif 000021
【図１Ｅ】
2007510379.tif 000022
【図１Ｆ】
2007510379.tif 000023
【図１Ｇ】
2007510379.tif 000024
【図１Ｈ】
2007510379.tif 000025
【図１Ｉ】
2007510379.tif 000026
【図１Ｊ】
2007510379.tif 000027
【図１Ｋ】
2007510379.tif 000028
【図１Ｌ】
2007510379.tif 000029
【図１Ｍ】
2007510379.tif 000030
【図１Ｎ】
2007510379.tif 000031
【図２Ａ】
2007510379.tif 000032
【図２Ｂ】
2007510379.tif 000033
【図２Ｃ】
2007510379.tif 000034
【図２Ｄ】
2007510379.tif 000035
【図２Ｅ】
2007510379.tif 000036
【図２Ｆ】
2007510379.tif 000037
【図３Ａ】
2007510379.tif 000038
【図３Ｂ】
2007510379.tif 000039
【図３Ｃ】
2007510379.tif 000040
【図３Ｄ】
2007510379.tif 000041
【図３Ｅ】
2007510379.tif 000042
【図４Ａ】
2007510379.tif 000043
【図４Ｂ】
2007510379.tif 000044
【図４Ｃ】
2007510379.tif 000045
【図４Ｄ】
2007510379.tif 000046
【図４Ｅ】
2007510379.tif 000047
【図４Ｆ】
2007510379.tif 000048
【図４Ｇ】
2007510379.tif 000049
【図５Ａ】
2007510379.tif 000050
【図５Ｂ】
2007510379.tif 000051
【図６Ａ】
2007510379.tif 000052
【図６Ｂ】
2007510379.tif 000053
【国際調査報告】
2007510379.tif 000054