(57)【要約】【課題】【解決手段】３段階ネットワークが本発明による厳密にノンブロッキングな方式で動作し、ｒ１個のスイッチおよびｒ１個のスイッチのそれぞれに対するｎ１個のインレットリンクを有する入力段階と、ｒ２個のスイッチおよびｒ２個のスイッチのそれぞれに対するｎ２個のアウトレットリンクを有する出力段階を含む。そのネットワークはｍ個のスイッチから成る中間段階も有し、各中間スイッチは、少なくともｒ１個の第１内部リンクの全体に対して各入力スイッチに接続された少なくとも１つのリンクと、少なくともｒ２個の第２内部リンクの全体に対して各出力スイッチに接続された少なくとも１つのリンクを有し、ここで、2007532037.tif 000045である。１実施形態においては、各マルチキャスト接続は、中間段階内の１つのスイッチのみを使用することで、そのような３段階ネットワークを通して確立される。入力段階スイッチの数ｒ１が出力段階のスイッチの数ｒ２と等しく、ｒ１＝ｒ２＝ｒである場合、さらに各入力スイッチ内のインレットリンクの数ｎ１が各出力スイッチ内のアウトレットリンク数ｎ２に等しく、ｎ１＝ｎ２＝ｎである場合、３段階ネットワークは2007532037.tif 000046を満たす、本発明による厳密にノンブロッキングな方式で動作する。さらに本発明に従って、ｍ≧ｘ＊ＭＩＮ（ｎ１，ｎ２）、２≦ｘ≦ｒ２を満たすｍ個の中間スイッチを有する３段階ネットワークが、各マルチキャスト接続のファンアウトがｘ以下である場合に、厳密にノンブロッキングな方式で動作する。【選択図】図２Ｂ
2007532037.tif 000002
【特許請求の範囲】
【請求項１】
複数のマルチキャスト接続を有するネットワークであって、前記ネットワークは、
ｒ１個の入力スイッチおよび、前記ｒ１個の入力スイッチの各々に対するｎ１個のインレットリンクを備える入力段階と；
ｒ２個の出力スイッチおよび、前記ｒ２個の出力スイッチの各々に対するｎ２個のアウトレットリンクを備える出力段階と；
ｍ個の中間スイッチを備える中間段階であって、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンク（以下“第１内部リンク”という）を備え、各中間スイッチは、総数少なくともｒ２個の第２内部リンクに対して、各出力スイッチに接続された少なくとも１つのリンク（以下“第２内部リンク”という）をさらに備える前記中間段階と；
を備えるネットワークであって、
前記ネットワークはさらに、既存のマルチキャスト接続のパスを変更することなく、前記マルチキャスト接続を常に確立でき、前記ネットワークは、これ以降“厳密にノンブロッキングなネットワーク”と称することとし、ここで、
2007532037.tif 000041
を満たし、
インレットリンクからの各マルチキャスト接続が１つの中間スイッチのみを通して、かつ前記マルチキャスト接続はさらに前記１つの中間スイッチのみから複数のアウトレットリンクに移ることを特徴とするネットワーク。
【請求項２】
前記マルチキャスト接続を確立するために前記の入力、出力および中間段階の各々に結合したコントローラをさらに備える、請求項１に記載のネットワーク。
【請求項３】
前記のｒ１個の入力スイッチおよびｒ２個の出力スイッチは同数のスイッチであり、ｒ１＝ｒ２＝ｒであることを特徴とする、請求項１に記載のネットワーク。
【請求項４】
前記のｎ１個のインレットリンクおよびｎ２個のアウトレットリンクは同数のリンクであり、ｎ１＝ｎ２＝ｎであって、
2007532037.tif 000042
であることを特徴とする、請求項１に記載のネットワーク。
【請求項５】
前記入力スイッチの各々、または前記出力スイッチの各々、または前記中間スイッチの各々はさらに１つまたは複数のネットワークを再帰的に備えることを特徴とする請求項１に記載のネットワーク。
【請求項６】
ネットワークにおける１つまたは複数のマルチキャスト接続を確立する方法であって、前記ネットワークは、ｎ１＊ｒ１個のインレットリンクおよびｒ１個の入力スイッチを有する入力段階と、ｎ２＊ｒ２個のアウトレットリンクおよびｒ２個の出力スイッチを有する出力段階と、ｍ個の中間スイッチを有する中間段階であって、各中間スイッチは、前記ｒ１個の入力スイッチの各々にｒ１個の第１内部リンクを通して接続され、かつ、各中間スイッチは、総数少なくともｄ個の第２内部リンクに対して、多くともｄ個の前記出力スイッチに接続された少なくとも１つのリンクをさらに備え、ここで１≦ｄ≦ｒ２である前記中間段階とを有するネットワークにおいて、前記方法は、
前記入力段階でマルチキャスト接続を受信するステップと；
前記入力段階で前記マルチキャスト接続を１つの中間スイッチのみにファンアウトし、前記ｒ２個の出力スイッチ中の複数の出力スイッチへの前記マルチキャスト接続を確立し、その際、前記複数の出力スイッチは前記マルチキャスト接続の宛先として特定され、前記入力スイッチから前記１つの中間スイッチのみへの第１内部リンクと、前記１つの中間スイッチのみから前記宛先への第２内部リンクとが利用可能である、前記接続をファンアウトするステップとを備え；
前記ファンアウト動作は、別の中間スイッチを通るために既存のどの接続も変更することなく行われることを特徴とする方法。
【請求項７】
前記ファンアウト動作は再帰的に行うことを特徴とする、請求項６に記載の方法。
【請求項８】
ネットワークにおける１つまたは複数のマルチキャスト接続を確立する方法であって、前記ネットワークは、ｎ１＊ｒ１個のインレットリンクおよびｒ１個の入力スイッチを有する入力段階と、ｎ２＊ｒ２個のアウトレットリンクおよびｒ２個の出力スイッチを有する出力段階と、ｍ個の中間スイッチを有する中間段階であって、各中間スイッチは前記ｒ１個の入力スイッチの各々にｒ１個の第１内部リンクを通して接続され、かつ、各中間スイッチは、総数少なくともｄ個の第２内部リンクに対して、多くともｄ個の前記出力スイッチに接続された少なくとも１つのリンクをさらに備え、ここで１≦ｄ≦ｒ２である前記中間段階とを有するネットワークにおいて、前記方法は、
前記マルチキャスト接続の宛先出力スイッチの全てが中間スイッチに対する利用可能な第２内部リンクを有するかどうかをチェックするステップを備える方法。
【請求項９】
前記マルチキャスト接続の前記入力スイッチは、前記の第１中間スイッチに対する利用可能な第１内部リンクを有するかどうかをチェックするステップをさらに備える請求項８に記載の方法。
【請求項１０】
宛先出力スイッチ全てに対して利用可能な第２内部リンクの前記のチェックを、前記第１中間段階スイッチ以外の各中間段階スイッチで繰り返すステップをさらに備える請求項８に記載の方法。
【請求項１１】
利用可能な第１内部リンクの前記のチェックを、前記第１中間段階スイッチ以外の各中間段階スイッチで繰り返すステップをさらに備える請求項８に記載の方法。
【請求項１２】
前記入力スイッチから前記出力スイッチへの前記マルチキャスト接続の各々を、前記のチェックによって選択された１つの中間スイッチのみを通して、前記入力スイッチ内で前記マルチキャスト接続を前記１つ以下の中間段階スイッチにファンアウトすることによって、確立するステップをさらに備える請求項８に記載の方法。
【請求項１３】
前記チェックおよび確立動作のいずれも再帰的に行うことを特徴とする、請求項８に記載の方法。
【請求項１４】
複数のマルチキャスト接続を有するネットワークであって、前記ネットワークは、
ｒ１個の入力スイッチおよび、前記ｒ１個の入力スイッチの各々に対するｎ１個のインレットリンクを備える入力段階と；
ｒ２個の出力スイッチおよび、前記ｒ２個の出力スイッチの各々に対するｎ２個のアウトレットリンクを備える出力段階と；
ｍ個の中間スイッチを備える中間段階であって、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンク（以下“第１内部リンク”という）を備え、各中間スイッチは、総数少なくともｒ２個の第２内部リンクに対して、各出力スイッチに接続された少なくとも１つのリンク（以下“第２内部リンク”という）をさらに備える前記中間段階とを備え；
前記ネットワークは、さらに、既存のマルチキャスト接続のパスを変更することなく前記マルチキャスト接続を常に確立でき、かつ、前記ネットワークは、これ以降“厳密にノンブロッキングなネットワーク”と称することとし、ここで、ｍ≧ｘ＊ＭＩＮ（ｎ１，ｎ２）、２≦ｘ≦ｒ２を満たし、前記マルチキャスト接続はファンアウトをｘ以下のファンアウトを有し；
インレットリンクからの各マルチキャスト接続は１つの中間スイッチのみを通して、前記マルチキャスト接続はさらに前記１つの中間スイッチのみから複数のアウトレットリンクに移ることを特徴とするネットワーク。
【請求項１５】
前記マルチキャスト接続を確立するために前記の入力、出力および中間段階の各々に結合したコントローラをさらに備える請求項１４に記載のネットワーク。
【請求項１６】
前記のｒ１個の入力スイッチおよびｒ２個の出力スイッチは同数のスイッチであり、ｒ１＝ｒ２＝ｒであることを特徴とする、請求項１４に記載のネットワーク。
【請求項１７】
前記のｎ１個のインレットリンクおよびｎ２個のアウトレットリンクは同数のリンクであり、ｎ１＝ｎ２＝ｎであって、ｍ≧ｘ＊ｎを満たし、ここで２≦ｘ≦ｒであることを特徴とする、請求項１４に記載のネットワーク。
【請求項１８】
前記入力スイッチの各々、または前記出力スイッチの各々、または前記中間スイッチの各々は、さらに１つまたは複数のネットワークを再帰的に備えることを特徴とする請求項１４に記載のネットワーク。
【請求項１９】
複数のマルチキャスト接続を有するネットワークであって、前記ネットワークは、ｒ１個の入力スイッチおよび、前記ｒ１個の入力スイッチの各々に対する、ｗ∈［１，ｒ１］かつｎ１＝ＭＡＸ（ｎ１ｗ）となるようなｎ１ｗ個のインレットリンクを入力スイッチｗ内に備える入力段階と；
ｒ２個の出力スイッチおよび、前記ｒ２個の出力スイッチの各々に対する、ｖ∈［１，ｒ２］かつｎ２＝ＭＡＸ（ｎ２ｖ）となるようなｎ２ｖ個のアウトレットリンクを出力スイッチｖ内に備える出力段階と；
ｍ個の中間スイッチを備える中間段階であって、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンク（以下“第１内部リンク”という）を備え、各中間スイッチは、総数少なくともｄ個の第２内部リンクに対して、多くともｄ個の前記出力スイッチに接続された少なくとも１つのリンク（以下“第２内部リンク”という）をさらに備え、ここで１≦ｄ≦ｒ２である前記中間段階とを備え；
前記ネットワークは、さらに、既存のマルチキャスト接続のパスを変更することなく前記マルチキャスト接続を常に確立でき、前記ネットワークは、これ以降“厳密にノンブロッキングなネットワーク”と称することとし、ここで、
2007532037.tif 000043
を満たし、その際、
インレットリンクからの各マルチキャスト接続が１つの中間スイッチのみを通して、かつ、前記マルチキャスト接続は、さらに前記１つの中間スイッチのみから複数のアウトレットリンクに移ることを特徴とするネットワーク。
【請求項２０】
前記マルチキャスト接続を確立するために前記の入力、出力および中間段階の各々に結合したコントローラをさらに備える、請求項１９に記載のネットワーク。
【請求項２１】
前記のｒ１個の入力スイッチおよびｒ２個の出力スイッチは同数のスイッチであり、ｒ１＝ｒ２＝ｒであることを特徴とする、請求項１９に記載のネットワーク。
【請求項２２】
前記のｎ１個のインレットリンクおよびｎ２個のアウトレットリンクは同数のリンクであり、ｎ１＝ｎ２＝ｎであって、
2007532037.tif 000044
であることを特徴とする、請求項１９に記載のネットワーク。
【請求項２３】
前記入力スイッチの各々、または前記出力スイッチの各々、または前記中間スイッチの各々は、さらに１つまたは複数のネットワークを再帰的に備えることを特徴とする、
請求項１９に記載のネットワーク。
【請求項２４】
複数の入力サブネットワーク、複数の中間サブネットワークおよび複数の出力サブネットワークを備えるネットワークであって、前記入力サブネットワーク、前記中間サブネットワークおよび前記出力サブネットワークの少なくとも１つが再帰的に、
ｒ１個の入力スイッチおよび、前記ｒ１個の入力スイッチの各々に対する、ｗ∈［１，ｒ１］かつｎ１＝ＭＡＸ（ｎ１ｗ）を満たす、入力スイッチｗ内のｎ１ｗ個のインレットリンクを備える入力段階と；
ｒ２個の出力スイッチおよび、前記ｒ２個の出力スイッチの各々に対する、ｖ∈［１，ｒ２］かつｎ２＝ＭＡＸ（ｎ２ｖ）を満たす、出力スイッチｖ内のｎ２ｖ個のアウトレットリンクを備える出力段階と；
ｍ個の中間スイッチを備える中間段階であって、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンク（以下“第１内部リンク”という）を備え、各中間スイッチは、総数少なくともｄ個の第２内部リンクに対して、多くともｄ個の前記出力スイッチに接続された少なくとも１つのリンク（以下“第２内部リンク”という）をさらに備え、ここで、１≦ｄ≦ｒ２である前記中間段階とを備え；
インレットリンクからの各マルチキャスト接続が、１つの中間スイッチのみを通して、かつ、前記マルチキャスト接続は、さらに前記１つの中間スイッチのみから複数のアウトレットリンクに移ることを特徴とするネットワーク。
【請求項２５】
複数のマルチキャスト接続を有するネットワークであって、前記ネットワークは、
ｒ１個の入力スイッチと、前記ｒ１個の入力スイッチの各々に対する、ｗ∈［１，ｒ１］かつｎ１＝ＭＡＸ（ｎ１ｗ）を満たす、入力スイッチｗ内のｎ１ｗ個のインレットリンクとを備える入力段階と；
ｒ２個の出力スイッチと、前記ｒ２個の出力スイッチの各々に対する、ｖ∈［１，ｒ２］かつｎ２＝ＭＡＸ（ｎ２ｖ）を満たす、出力スイッチｖ内のｎ２ｖ個のアウトレットリンクとを備える出力段階と；
ｍ個の中間スイッチを備える中間段階であって、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンク（以下“第１内部リンク”という）を備え、各中間スイッチは、総数少なくともｄ個の第２内部リンクに対して、多くともｄ個の前記出力スイッチに接続された少なくとも１つのリンク（以下“第２内部リンク”という）をさらに備え、ここで１≦ｄ≦ｒ２である前記中間段階とを備え；
前記ネットワークは、さらに、既存のマルチキャスト接続のパスを変更することなく前記マルチキャスト接続を常に確立でき、前記ネットワークは、これ以降“厳密にノンブロッキングなネットワーク”と称することとし、ここでｍ≧ｘ＊ＭＩＮ（ｎ１，ｎ２）、２≦ｘ≦ｒ２を満たし、前記マルチキャストは、ｘ以下のファンアウトを有し；
インレットリンクからの各マルチキャスト接続が1つの中間スイッチのみを通して、かつ、前記マルチキャスト接続は、さらに前記１つの中間スイッチのみから複数のアウトレットリンクに移ることを特徴とするネットワーク。
【請求項２６】
前記マルチキャスト接続を確立するために前記の入力、出力および中間段階の各々に結合したコントローラをさらに備える、請求項２５に記載のネットワーク。
【請求項２７】
前記のｒ１個の入力スイッチおよびｒ２個の出力スイッチは同数のスイッチであり、ｒ１＝ｒ２＝ｒであることを特徴とする、請求項２５に記載のネットワーク。
【請求項２８】
前記のｎ１個のインレットリンクおよびｎ２個のアウトレットリンクは同数のリンクであり、ｎ１＝ｎ２＝ｎであって、ｍ≧ｘ＊ｎを満たし、ここで２≦ｘ≦ｒであることを特徴とする、請求項２５に記載のネットワーク。
【請求項２９】
前記入力スイッチの各々、または前記出力スイッチの各々、または前記中間スイッチの各々は、さらに１つまたは複数のネットワークを再帰的に備えることを特徴とする、請求項２５に記載のネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の記載
本出願は、２００３年９月６日出願の米国仮特許出願番号６０／５００，７９０に関し、それに対する優先権を主張する。本出願は、本出願と同一の出願人に譲渡され、同時に出願された、Ｖｅｎｋａｔ  Ｋｏｎｄａによる“厳密にノンブロッキングなマルチキャスト線形時間多段階ネットワーク”というタイトルの関連米国特許出願ドケット番号Ｖ−０００３に対するＰＣＴ出願であり、その全体を言及により組み込む。
【０００２】
本出願は、２００１年９月２７日出願の関連米国特許出願番号０９／９６７，８１５およびその一部継続出願である２００３年９月６日出願のＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７１に関し、それら全体を言及により組み込む。本出願は、２００１年９月２７日出願の関連米国特許出願番号０９／９６７，１０６およびその一部継続出願である２００３年９月６日出願のＰＣＴ出願番号ＰＣＴ／ＵＳ０３／２７９７２に関し、それら全体を言及により組み込む。
【０００３】
本出願は、２００３年９月６日出願の関連米国仮特許出願番号６０／５００，７８９およびそれの米国特許出願ドケット番号Ｖ−０００４と共に、同時に出願されたそのＰＣＴ出願ドケット番号Ｓ−０００４に関し、それら全体を言及により組み込む。
【背景技術】
【０００４】
当分野では公知のように、Ｃｌｏｓスイッチングネットワークは、多段階ネットワークとして構成されたスイッチのネットワークであり、インレットリンク（“入力”とも呼ばれる）およびアウトレットリンク（“出力”とも呼ばれる）間の接続を実装するために必要なスイッチングポイントの数は、同数の入力および出力を有する単一段階（例えばクロスバー）スイッチが要する数よりも少ない。Ｃｌｏｓネットワークはデジタルクロスコネクト、光クロスコネクト、スイッチファブリックおよび並列コンピュータシステムにおいて非常に多く使用される。しかしながら、Ｃｌｏｓネットワークは接続要求の一部をブロックする可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
一般的に、３つのタイプのノンブロッキングなネットワークがある。即ち、厳密にノンブロッキング、広義のノンブロッキング、および再配置可能なノンブロッキング（背景として、言及により組み込んだ、Ｖ．Ｅ．Ｂｅｎｅｓの“ネットワーク接続および電話トラフィックの数学的理論（Ｍａｔｈｅｍａｔｉｃａｌ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｎｎｅｃｔｉｎｇ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ｔｅｌｅｐｈｏｎｅ  Ｔｒａｆｆｉｃ)”、１９６５年アカデミック出版(Ａｃａｅｍｉｃ  Ｐｒｅｓｓ)、を参照）である。再配置可能なノンブロッキングネットワークにおいては、新しい着呼を受信した時に以前の接続を再配置するネットワーク能力の結果として、接続パスが保証される。厳密にノンブロッキングなネットワークにおいては、１つのインレットリンクからアウトレットリンクの集合への任意の接続要求に対して、ネットワークを通る接続パスを提供して、他の既存の接続を妨害することなく要求を満たすことが常に可能である。そのようなパスが複数利用可能な場合、将来の接続要求の実現を懸念せずに任意のパスを選択することができる。広義のノンブロッキングなネットワークにおいても、ネットワークを通る接続パスを提供して、他の既存の接続を妨害することなく要求を満たすことが常に可能であるが、この場合は、接続要求を満たすために使用するパスは、将来の潜在的な接続要求に対するノンブロッキング接続能力を維持するために慎重に選択しなければならない。
【０００６】
Ｙａｎｇ他に付与された “ノンブロッキングなブロードキャストネットワーク”というタイトルの米国特許５，４５１，９３６を、ここで本発明の背景として、言及により組み込む。この特許は、背景の節の１列２２行目から３列目の５９行目までに、多数の公知のノンブロッキング多段階スイッチングネットワークを記述する。
【０００７】
１９９１年９月のＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｃｏｍｐｕｔｅｒ，Ｖｏｌ．４０，Ｎｏ．９におけるＹ．ＹａｎｇとＧ．Ｍ．，Ｍａｓｓｏｎによる“ノンブロッキングなブロードキャストネットワーク”というタイトルの論文を背景として言及により組み込んでいるが、この論文は、３段階ネットワークの中間段階におけるスイッチ数ｍが関係ｍ≧ｍｉｎ（（ｎ−１）（ｘ＋ｒ１／ｘ）、１≦ｘ≦ｍｉｎ（ｎ−１，ｒ）を満たす場合、結果として生じるネットワークはマルチキャスト割当に対してノンブロッキングであることを示す。この関係において、ｒは入力段階におけるスイッチの数で、ｎは各入力スイッチにおけるインレットリンクの数である。ＫｉｍおよびＤｕ（ここに言及により組み込んだ２０００年８月のＤ．Ｓ．Ｋｉｍ、Ｄ．Ｄｕによる“３段階マルチキャストネットワークに対する分割ルーティングアルゴリズムの性能（Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  Ｓｐｌｉｔ  Ｒｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｒｅｅ−ｓｔａｇｅ  ｍｕｌｔｉｃａｓｔ  ｎｅｔｗｏｒｋｓ）”、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｎｅｔｗｏｒｋ，Ｖｏｌ．８，Ｎｏ．４を参照）は、異なるスケジューリングアルゴリズムに対するマルチキャスト接続のブロッキング確率を研究した。
【課題を解決するための手段】
【０００８】
３段階のネットワークは、本発明に従って厳密にノンブロッキングな方法で動作し、ｒ１個のスイッチとｒ１個のスイッチの各々に対するｎ１個のインレットリンクとを有する入力段階、およびｒ２個のスイッチとｒ２個のスイッチの各々に対するｎ２個のアウトレットリンクとを有する出力段階を含む。ネットワークはｍ個のスイッチを有する中間段階も有し、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンクと、総数少なくともｒ２個の第２内部リンクに対して、各出力スイッチに接続された少なくとも１つのリンクとを有する。ここで、
2007532037.tif 000003
である。
【０００９】
１実施形態においては、各マルチキャスト接続を、そのような３段階ネットワークを通して中間段階でスイッチを１つだけ使用することによって、確立する。入力段階のスイッチの数ｒ１が出力段階のスイッチの数ｒ２と等しく、ｒ１＝ｒ２＝ｒであり、さらに各入力スイッチ内のインレットリンクの数ｎ１が各出力スイッチ内のアウトレットリンクの数ｎ２と等しく、ｎ１＝ｎ２＝ｎであるとき、３段階ネットワークは本発明による厳密にノンブロッキングな方式で動作し、ここで
2007532037.tif 000004
である。
【００１０】
さらに本発明に従って、
2007532037.tif 000005
であるｍ個の中間スイッチを有する３段階ネットワークが、各マルチキャスト接続のファンアウトがｘ以下であるとき、厳密にノンブロッキングな方式で動作する。
【発明を実施するための最良の形態】
【００１１】
本発明は、ブロードキャスト、ユニキャストおよびマルチキャスト接続のための多段階スイッチングネットワークの設計および動作に関する。送信装置が同時に複数の受信装置に情報を送信するとき、送信装置と受信装置間で要求される１対多の接続はマルチキャスト接続と呼ばれる。マルチキャスト接続の集合をマルチキャスト割当と言う。送信装置が１つの受信装置に情報を送信するとき、送信装置と受信装置間で要求される１対１の接続はユニキャスト接続と呼ばれる。送信装置が同時に全ての利用可能な受信装置に情報を送信するとき、送信装置と受信装置間で要求される１対全の接続はブロードキャスト接続と呼ばれる。
【００１２】
一般的に、マルチキャスト接続は１対多の接続を意味し、ユニキャストおよびブロードキャスト接続を含む。スイッチングネットワークにおけるマルチキャスト割当は、利用可能なインレットリンクのいずれかが利用可能なアウトレットリンクのいずれかに常時接続できる場合に、ノンブロッキングである。ここで記述したタイプの一定の多段階ネットワークにおいて、任意のファンアウトの任意の接続要求、即ち、ネットワークの１つのインレットリンクからアウトレットリンク（単数または複数）への接続要求を、以前の接続要求のいずれも再配置する必要なく、ブロッキングされずに満足することができる。そのようなネットワークの中間段階内のスイッチ数によって、そのような接続要求は、上述の中で言及により組み込んだ米国特許出願番号０９／９６７，８１５で詳細に記述されているように、必要なら以前の接続要求のいくつかを再配置することで、ブロッキングなしに満たすことができる。そのようなネットワークの中間段階内のスイッチ数および使用するスケジューリング方法のタイプによって、そのような接続要求を、上述の中で言及により組み込んだ米国特許出願番号０９／９６７，１０６で詳細に記述されているように、再配置さえすることなく満足することができる。
【００１３】
図１Ａを参照すると、電話の呼またはデータパケット接続の確立等の、中間段階１３０を経由した入力段階１１０と出力段階１２０の間の通信要求を満足するための１４個のスイッチからなる例示的な対称３段階Ｃｌｏｓネットワークが示されている。ここで、入力段階１１０は４つの３Ｘ６スイッチＩＳ１−ＩＳ４から成り、出力段階１２０は４つの６Ｘ３スイッチＯＳ１−ＯＳ４から成り、中間段階１３０は６つの４Ｘ４スイッチＭＳ１−ＭＳ６から成る。そのようなネットワークは厳密にノンブロッキングな方式で動作することができる。なぜならば、中間段階１３０内のスイッチ数（即ち、６つのスイッチ）が
2007532037.tif 000006
に等しいからである。ここで、ｎは入力段階１１０および出力段階１２０内のスイッチの各々のリンク数（即ち、３つのインレットリンク）であり、ｒは入力段階１１０および出力段階１２０内のスイッチ数である。厳密なノンブロッキング接続性の実装に使用される具体的方法は、本発明の開示内容を考慮すると当業者には自明であるような多くの異なる方法のいずれであってもよい。そのような方法の１つを図１Ｂを参照して以下に記述する。
【００１４】
このネットワークの１実施形態においては、入力スイッチＩＳ１−ＩＳ４および出力スイッチＯＳ１−ＯＳ４の各々は単段階スイッチである。ネットワークの段階数が１の場合、スイッチングネットワークは単段階スイッチングネットワーク、クロスバースイッチングネットワークまたはより簡潔にクロスバースイッチと呼ばれる。Ｎ個のインレットリンクとＭ個のアウトレットリンクを有する（Ｎ＊Ｍ）クロスバースイッチングネットワークは、ＮＭ個のクロスポイントから成る。Ｎの値とＭの値が大きくなると、そのようなクロスバースイッチングネットワークの作成コストは法外に高くなる。図１Ａにおけるネットワークの別の実施形態においては、入力スイッチＩＳ１−ＩＳ４および出力スイッチＯＳ１−ＯＳ４の各々は共有メモリスイッチである。
【００１５】
入力段階１１０のスイッチ数および出力段階１２０のスイッチ数は、一般に各段階に対する変数ｒで表すことができる。中間スイッチ数はｍで表される。各入力スイッチＩＳ１−ＩＳ４の大きさは一般にｎ＊ｍの表記法で表され、各出力スイッチＯＳ１−ＯＳ４の大きさは一般にｍ＊ｎの表記法で表すことができる。同様に、各中間スイッチＭＳ１−ＭＳ６の大きさはｒ＊ｒとして表すことができる。ここで使用されるスイッチは、１つのクロスバースイッチ、またはスイッチの各々がクロスバースイッチもしくはスイッチのネットワークであってよいスイッチのネットワークであることができる。３段階ネットワークはＶ（ｍ，ｎ，ｒ）の表記法で表すことができる。ここで、ｎは各入力スイッチに対するインレットリンク（例えば入力スイッチＩＳ１に対するリンクＩＬ１−ＩＬ３）の数を表し、ｍは中間スイッチＭＳ１−ＭＳ６の数を表す。アウトレットリンクＯＬ１−ＯＬ１２と同じ数だけインレットリンクＩＬ１−ＩＬ１２がある必要はないが、対称ネットワークにおいては、それらの数は同じである。ｍ個の中間スイッチＭＳ１−ＭＳ６の各々は、ｒ個の入力スイッチの各々に対してｒ個のリンク（以下“第１内部”リンクという。例えば、入力スイッチＩＳ１−ＩＳ４の各々から中間スイッチＭＳ１に接続されたリンクＦＬ１−ＦＬ４）を通して接続され、出力スイッチのそれぞれに対してｒ個の第２内部リンク（以下“第２内部”リンクという。例えば、中間スイッチＭＳ１から出力スイッチＯＳ１−ＯＳ４のそれぞれに対して接続されたリンクＳＬ１−ＳＬ４）に接続される。
【００１６】
第１内部リンクＦＬ１−ＦＬ２４および第２内部リンクＳＬ１−ＳＬ２４の各々は、新規接続による使用に対して利用可能か、既存の接続により現在使用されている場合に利用不能であるかのいずれかである。入力スイッチＩＳ１−ＩＳ４はネットワーク入力ポートとも呼ばれる。入力段階１１０はしばしば第１段階と呼ばれる。出力スイッチＯＳ１−ＯＳ４はネットワーク出力ポートとも呼ばれる。出力段階１２０はしばしば最終段階と呼ばれる。３段階ネットワークにおいては、第２段階１３０は中間段階と呼ばれる。中間段階スイッチＭＳ１−ＭＳ６は中間スイッチまたは中間ポートと呼ばれる。
【００１７】
１実施形態においては、入力段階１１０、出力段階１２０および中間段階１３０の各々と結合し、インレットリンクＩＬ１−ＩＬ１２および任意数のアウトレットリンクＯＬ１−ＯＬ１２の間の接続を形成するコントローラも含む。この実施形態においては、コントローラはメモリ内に、中間スイッチ（例えば図１Ａ内のＭＳ１）を通る接続に対して利用可能な宛先のリストを維持し、１つのファンアウトを実装する。同様の方式で、ｎ個のリストの集合が、ｎ個のファンアウトを使用するコントローラの実施形態内に維持される。
【００１８】
図１Ｂは、図１Ａのコントローラによって実行される１実施形態におけるスケジューリング方法１４０の高レベルフローチャートを示す。この実施形態によると、マルチキャスト接続要求が動作１４１で受信される。その後、要求を満足させる接続が動作１４２で、入力スイッチから中間段階１３０の１つのスイッチのみにファンアウトすることによって、確立される。
【００１９】
図１Ａに示される例においては、入力スイッチがＩＳ２の場合、マルチキャスト接続を満足させるために６つのファンアウトが可能であるが、この方法によると１つの中間段階スイッチのみが使用される。１つのファンアウトを選択するときに選ばれる特定の中間スイッチは、１つの中間スイッチのみが選択されて接続要求を満足させることを保証する限り、図１Ｂの方法とは無関係である。即ち、接続要求により識別される宛先スイッチは、選択されたファンアウトの一部である中間スイッチから到達可能である。要するに、入力スイッチから１つの中間スイッチのみへファンアウトを制限することで、ネットワーク１００は本発明による厳密にノンブロッキングな方式で動作できる。
【００２０】
動作１４２の後で制御は動作１４１に戻され、動作１４１および１４２は、各マルチキャスト接続要求に対してループ内で実行される。以下でさらに示す１実施形態によると、図１Ｂのスケジューリング方法を使用するときネットワークが厳密にノンブロッキングな対称スイッチングネットワークであるために、図１Ａのネットワーク１００において
2007532037.tif 000007
より多くの中間段階スイッチを有する必要はない。ここで、インレットリンクＩＬ１−ＩＬ３の数はアウトレットリンクＯＬ１−ＯＬ３の数に等しく、両者は変数ｎで表され、入力段階１１０内のスイッチＩＳ１−ＩＳ４の数は出力段階１２０内のスイッチＯＳ１−ＯＳ４の数に等しく、両者は変数ｒで表される。
【００２１】
図１Ｂの方法１４０を参照して上述したタイプの接続要求は、その例によって、ユニキャスト接続要求、マルチキャスト接続要求またはブロードキャスト接続でありうる。接続要求の３つの場合の全てにおいて、入力スイッチ内の１つのファンアウトが使用される。即ち、単一中間段階スイッチが使用されて要求を満足させる。さらに、上述の実施形態において、１つという制限を中間段階スイッチへのファンアウトに置いたが、その制限は、図２Ａを参照して以下で論じるように、ネットワーク内の中間段階スイッチの数によって、より大きくなりうる（一方で、ネットワーク動作の厳密にノンブロッキングな性質は維持される）。さらに、図１Ｂを参照して上述した方法１４０において接続要求を満足させるために、任意のファンアウトを各中間段階スイッチと各出力段階スイッチの間で使用してもよく、任意のファンアウトを各出力段階スイッチ内で使用してもよい。さらに、図１Ｂの方法１４０は図１Ａの１４個のスイッチからなるネットワーク１００における例で示したが、図２Ａおよび図２Ｂに示したタイプの任意の一般的なネットワークに使用できる。
【００２２】
図１Ａのネットワークは、図２Ａに示した一般的な対称３段階ネットワークの１例である。一般的な対称３段階ネットワークは以下の条件を満たす場合、厳密にノンブロッキングな方式で動作できる。
2007532037.tif 000008
ここで図２Ａのネットワークは、ｒ個の入力スイッチＩＳ１−ＩＳｒの各々に対するｎ個のインレットリンク（例えば入力スイッチＩＳ１へのリンクＩＬ１１−ＩＬ１ｎ）を有し、ｒ個の出力スイッチＯＳ１−ＯＳｒの各々に対するｎ個のアウトレットリンク（例えば出力スイッチＯＳ１へのＯＬ１１−ＯＬ１ｎ）を有する。ｍ個のスイッチＭＳ１−ＭＳｍの各々は、各入力スイッチにｒ個の第１内部リンク（例えば、入力スイッチＩＳ１−ＩＳｒの各々から中間スイッチＭＳ１に接続されたリンクＦＬ１１−ＦＬｒ１）を通して接続され、ｒ個の第２内部リンク（例えば、中間スイッチＭＳ１から出力スイッチＯＳ１−ＯＳｒの各々に接続されたリンクＳＬ１１−ＳＬｒ１）を通して出力スイッチの各々に接続される。そのような一般的な対称ネットワークにおいて、図１Ｂに示したタイプのスケジューリング方法を使用するときネットワークが厳密にノンブロッキングな方式で動作可能であるために、
2007532037.tif 000009
図２Ａは、対称３段階ネットワークのための場合のように同数の第１内部リンクと第２内部リンクを示すが、本発明は図２Ｂに示すタイプの非対称ネットワークに対しても適用する（後述する）。
【００２３】
一般に、（Ｎ１＊Ｎ２）の3段階の非対称ネットワークは以下の条件を満たす場合、厳密にノンブロッキングな方式で動作できる。
2007532037.tif 000010
ここで、ネットワーク（図２Ｂ）は第１段階内にｒ１（ｎ１＊ｍ）個のスイッチＩＳ１−ＩＳｒ１を有し、中間段階内にｍ（ｒ１＊ｒ２）個のスイッチＭＳ１−ＭＳｍを有し、最終段階内にｒ２（ｍ＊ｒ２）個のスイッチＯＳ１−ＯＳｒ２を有する。ここで、Ｎ１＝ｎ１＊ｒ１はネットワークのインレットリンクの総数で、Ｎ２＝ｎ２＊ｒ２はネットワークのアウトレットリンクの総数である。
2007532037.tif 000011
の各々は入力スイッチの各々にｒ１個の第１内部リンク（例えば、入力スイッチＩＳ１−ＩＳｒ１の各々から中間スイッチＭＳ１に接続されたリンクＦＬ１１−ＦＬｒ１１）を通して接続され、ｒ２個の第２内部リンク（例えば、中間スイッチＭＳ１から出力スイッチＯＳ１−ＯＳｒ２のそれぞれに接続されたリンクＳＬ１１−ＳＬｒ２１）を通して出力スイッチのそれぞれに接続される。そのような多段階スイッチングネットワークはＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークとして表される。ｎ１＝ｎ２＝ｎかつｒ１＝ｒ２＝ｒである特殊な対称の場合、３段階ネットワークはＶ（ｍ，ｎ，ｒ）のネットワークとして表される。一般に、インレットリンクの集合は｛１，２，．．．ｒ１ｎ１｝として表され、出力スイッチの集合はＯ＝｛１，２，．．．ｒ２｝として表される。非対称３段階ネットワークにおいては、ｒ１個の入力スイッチの各々に対するｎ１個のインレットリンク、ｒ２個の出力スイッチの各々に対するｎ２個のアウトレットリンクを用いて図２Ｂに示すように、
2007532037.tif 000012
の中間段階スイッチであることが、図１Ｂのスケジューリング方法を使用するときネットワークが厳密にノンブロッキングであるために、必要である。ネットワークは、各接続パスが１つの中間スイッチのみを通って全ての宛先アウトレットリンクに接続されるように、全ての接続を確立する。
【００２４】
１実施形態において、ここで論じた多段階ネットワーク内のあらゆるスイッチはマルチキャスト能力を有する。Ｖ（ｍ，ｎ１，ｎ２，ｒ２）のネットワークにおいては、ネットワークのインレットリンクが同一出力スイッチ上の複数のアウトレットリンクに接続される場合、対応する入力スイッチがその出力スイッチへの１つのパスを有することだけが必要である。パスは、必要なだけ多くのアウトレットリンクに対する出力スイッチ内のマルチキャストでありうるので、これが成り立つ。従って、マルチキャスト割当は、入力スイッチと出力スイッチ間接続の観点から記述できる。入力スイッチからｒ’個の出力スイッチへの既存の接続または新規の接続は、ファンアウトｒ’を有すると言われる。入力スイッチの任意のインレットリンクが出力スイッチ内で多くて１つのアウトレットリンクに接続されるような、第１のタイプのマルチキャスト割当全てが実現可能な場合、各入力スイッチの任意のインレットリンクが同じ出力スイッチ内で複数のアウトレットリンクに接続されるような、第２のタイプのマルチキャスト割当も実現できる。この理由から、以下の詳論は（１≦ｒ’≦ｒ２であるファンアウトｒ’を有する）第１のタイプの一般的なマルチキャスト接続に制限されるが、同様な詳論が第２のタイプに適用可能である。
【００２５】
マルチキャスト割当を特徴づけるため、各インレットリンクｉ∈｛１，２，...ｒ１ｎ１｝に対して、Ｉ１＝Ｏ、Ｏ⊂｛１，２，...ｒ２｝とし、インレットリンクｉがマルチキャスト割当内で接続される出力スイッチのサブセットを表す。例えば、図１Ａのネットワークは、マルチキャスト割当Ｉ２＝｛１，３，４｝、Ｉ６＝｛３｝、Ｉ９＝｛２｝およびｊ＝［１−１２］である他の全てのＩｊ＝Φを有する、例示的な３段階ネットワーク、即ちＶ（６，３，４）を示す。接続Ｉ２は第１段階スイッチＩＳ１内で中間段階スイッチＭＳ３にファンアウトし、中間スイッチＭＳ３内で出力スイッチＯＳ１、ＯＳ３、およびＯＳ４にファンアウトすることに注意すべきである。接続Ｉ２はさらに最終段階スイッチＯＳ１、ＯＳ３、およびＯＳ４内でアウトレットリンクＯＬ１、ＯＬ７およびＯＬ１２にそれぞれファンアウトする。接続Ｉ６は入力スイッチＩＳ２内で１度中間スイッチＭＳ２にファンアウトし、中間段階スイッチＭＳ２内で最終段階スイッチＯＳ３にファンアウトする。接続Ｉ６は出力スイッチＯＳ３内で１度アウトレットリンクＯＬ９にファンアウトする。接続Ｉ９は入力スイッチＩＳ３内で１度中間スイッチＭＳ４にファンアウトし、中間スイッチＭＳ４内で１度出力スイッチＯＳ２にファンアウトする。接続Ｉ９は出力スイッチＯＳ２内でアウトレットリンクＯＬ４、ＯＬ５、およびＯＬ６にファンアウトする。本発明によると、各接続は第１段階スイッチ内で１つの中間段階スイッチのみにファンアウトでき、中間スイッチおよび最終段階スイッチ内で接続要求によって要求される任意の回数ファンアウトできる。
【００２６】
ｉ≠ｊに対する２つのマルチキャスト接続要求Ｉｉ＝ＯｉとＩｊ＝Ｏｊは、Ｏｉ∩Ｏｊ＝Φである場合に限り互換性があると言われる。これは、要求ＩｉとＩｊに互換性があって、インレットリンクｉとｊが同一入力スイッチに属さない場合、同一中間スイッチを通してその接続を確立できることを意味する。
【００２７】
下の表１はＶ（９，３，９）のネットワークにおけるマルチキャスト割当を示す。このネットワークは総数２７個のインレットリンクと２７個のアウトレットリンクを有する。表１のマルチキャスト割当は、最初の３つの入力スイッチから各３個ずつの、９個のマルチキャスト接続を示す。９個の接続の各々は３個のファンアウトを有する。例えば、接続要求Ｉ１は宛先として出力スイッチＯＳ１、ＯＳ２、およびＯＳ３（表１において１、２、３として参照される）を有する。要求Ｉ１は出力スイッチを示すのみで、どのアウトレットリンクが宛先かは示さない。しかしながら、各出力スイッチは、各出力スイッチ内で３個のアウトレットリンクの全てを使用して、表１のマルチキャスト割当内で３回のみ使用されることが分かる。例えば、出力スイッチ１が要求Ｉ１、Ｉ４、Ｉ７内で使用されると、出力スイッチ１の３個のアウトレットリンク全てが使用中となり、各アウトレットリンクの固有ＩＤは無関係である。従って、９個の接続全てが確立されると、２７個のアウトレットリンク全てが使用中となる。
2007532037.tif 000013
【００２８】
図３Ａは、表１の接続Ｉ１−Ｉ８が前もって確立されるＶ（９，３，９）のネットワークの初期状態を示す。(簡潔にするため、図３Ａおよび図３Ｂは、中間スイッチＭＳ７、ＭＳ８、およびＭＳ９に接続された第１内部リンクおよび第２内部リンクを示さない。)Ｉ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５、Ｉ６、Ｉ７、およびＩ８は中間スイッチＭＳ１、ＭＳ２、ＭＳ３、ＭＳ４、ＭＳ５、ＭＳ６、ＭＳ７、およびＭＳ８をそれぞれ通る。これらの接続の各々は、入力スイッチ内で１度だけファンアウトし、各中間スイッチ内で３度ファンアウトしている。入力スイッチＩＳ１からの接続Ｉ１は中間スイッチＭＳ１に１度ファンアウトし、中間スイッチＭＳ１から３度出力スイッチＯＳ１、ＯＳ２、ＯＳ３にファンアウトする。入力スイッチＩＳ１からの接続Ｉ２は中間スイッチＭＳ２に１度ファンアウトし、中間スイッチＭＳ２から３度出力スイッチＯＳ４、ＯＳ５、ＯＳ６にファンアウトする。入力スイッチＩＳ１からの接続Ｉ３は中間スイッチＭＳ３に１度ファンアウトし、中間スイッチＭＳ３から３度出力スイッチＯＳ７、ＯＳ８、ＯＳ９にファンアウトする。入力スイッチＩＳ２からの接続Ｉ４は中間スイッチＭＳ４に１度ファンアウトし、中間スイッチＭＳ４から３度出力スイッチＯＳ１、ＯＳ４、ＯＳ７にファンアウトする。入力スイッチＩＳ２からの接続Ｉ５は中間スイッチＭＳ５に１度ファンアウトし、中間スイッチＭＳ５から３度出力スイッチＯＳ２、ＯＳ５、ＯＳ８にファンアウトする。入力スイッチＩＳ２からの接続Ｉ６は中間スイッチＭＳ６に１度ファンアウトし、中間スイッチＭＳ６から３度出力スイッチＯＳ３、ＯＳ６、ＯＳ９にファンアウトする。入力スイッチＩＳ３からの接続Ｉ７は中間スイッチＭＳ７に１度ファンアウトし、中間スイッチＭＳ７から３度出力スイッチＯＳ１、ＯＳ５、ＯＳ９にファンアウトする。入力スイッチＩＳ３からの接続Ｉ８は中間スイッチＭＳ８に１度ファンアウトし、中間スイッチＭＳ８から３度出力スイッチＯＳ２、ＯＳ６、ＯＳ７にファンアウトする。
【００２９】
図１Ｂの方法１４０は次に、入力スイッチＩＳ３から出力スイッチＯＳ３、ＯＳ４およびＯＳ８への接続Ｉ９を以下のように確立する。図３Ｂは、表１の接続Ｉ９が確立された後の図３Ａのネットワーク状態を示す。動作１４２において、図１Ｂのスケジューリング方法が、中間スイッチＭＳ９のみが接続Ｉ９を確立するために利用可能である（全ての他の中間スイッチＭＳ１−ＭＳ８の、少なくとも１つの宛先スイッチに対する第２内部リンクが利用不能なため）ことを発見し、スイッチＭＳ９を通る接続を確立する。従って、入力スイッチＩＳ３からの接続Ｉ９は１度だけ中間スイッチＭＳ９にファンアウトし、中間スイッチＭＳ９から３度出力スイッチＯＳ３、ＯＳ４、およびＯＳ８にファンアウトして、全ての宛先に接続される。
【００３０】
図４Ａは、図１Ｂにおける動作１４０の１変形の中間レベルフローチャートである。図１Ｂの動作１４２は１実施形態において、図４Ａに示された動作１４２Ａ−１４２Ｄによって実装される。詳細には、この実施形態において、動作１４２は動作１４２Ａ、１４２Ｂ、１４２Ｃおよび１４２Ｄによって実装される。動作１４２Ａは、中間スイッチが入力スイッチに対して利用可能なリンクを有するかどうかをチェックし、要求された宛先スイッチ全てに対する利用可能なリンクを有する。動作１４２Ｂにおいて、図４Ａの方法は、全ての中間スイッチが１４２Ａでチェックされたかどうかをチェックする。図４Ｂに示すように、動作１４２Ｂは動作１４２Ａでの決定が“いいえ”のとき到達される。動作１４２Ｂの結果が“いいえ”の場合、制御は動作１４２Ｃに行き、次の中間スイッチが選択されて制御は動作１４２Ａに移る。しかしながら、動作１４２Ｂの結果は決して“はい”にならず、これは図４Ａの方法が常に１つの中間スイッチを見つけて接続を確立することを意味する。動作１４２Ａの結果が“はい”のとき、制御は動作１４２Ｄに移り、接続が確立される。そしてその後、制御は動作１４１に移る。
【００３１】
図４Ｂは、図４Ａにおける動作１４２の１変形の低レベルフローチャートである。動作１４２に対する制御は、接続要求が受信された後に動作１４１から来る。動作１４２Ａ１において、インデックス変数ｉを、段階１３０（図２Ｂ）を形成する中間スイッチグループ内の第一の中間スイッチ１に設定し、単一のネストしたループの（動作１４２Ａ２、１４２Ａ３、１４２Ｂ、１４２Ｃから形成される）ループを初期化する。動作１４２Ａ２は、接続の入力スイッチが中間スイッチｉに対する利用可能なリンクを有するかどうかをチェックする。利用可能なリンクがなければ、制御は動作１４２Ｂに行く。中間スイッチｉに対する利用可能なリンクがあれば、制御は動作１４２Ａ３に行く。動作１４２Ａ３は中間スイッチｉが、マルチキャスト接続要求の宛先スイッチ全てに対する利用可能なリンクを有するかどうかをチェックする。あれば、制御は動作１４２Ｄに行き、接続が中間スイッチｉを通して確立される。そして中間スイッチｉから宛先出力スイッチへの使用されたリンクの全てが、将来の要求に対して利用不能とマーク付けされる。さらにその方法は“成功”を返す。動作１４２Ａ３の結果が“いいえ”の場合、制御は動作１４２Ｂへ行く。動作１４２Ｂは中間スイッチｉが最終段階スイッチであるかどうかをチェックするが、動作１４２Ｂの結果は決して“はい”にならず、それは、常に１つの中間スイッチを見つけて接続を確立することを意味する。動作１４２Ｂの結果が“いいえ”の場合、制御は動作１４２Ｃに行き、ｉは次の中間スイッチに設定される。そしてループの次の繰り返しが開始する。ｒ１個の入力スイッチの各々に対するｎ１個のインレットリンク、ｒ２個の出力スイッチの各々に対するｎ２個のアウトレットリンクを有する図２Ｂの３段階ネットワークにおいて、
2007532037.tif 000014
の中間段階スイッチであることが、ネットワークが厳密にノンブロッキングであるために、また、その結果として、図４Ａの方法が常に中間スイッチを見つけて接続を確立するために、必要である。
【００３２】
図４Ｃは、図４Ｂにおけるスケジューリング方法の1例のコンピュータ実装を、フローチャートで示す。フローチャート図４Ｃは、１つの相違点を除いてフローチャート図４Ｂと同じである。フローチャート図４Ｂにおいて、ループ脱出テストがループの終わりで行われる一方、フローチャート図４Ｃにおいてはループ脱出テストがループの初めに行われる。
【００３３】
以下の方法は、本発明で論じたのと同数の中間スイッチがネットワーク内にあるとき、図２Ｂのネットワークを通る新規マルチキャスト接続要求を常に確立するための図４Ｃのスケジューリング方法を実装する擬似コードを示す。
スケジューリング方法の擬似コード：
ステップ１：c=現在の接続要求；Ｏ=cの全ての宛先スイッチ集合；
ステップ２：for i=mid_switch_1 to mid_switch_m do{
ステップ３：  if(cがiに対して利用可能なリンクを有しない) continue;
ステップ４：      Ａｉ=iから使用可能なリンクを有する、全ての宛先スイッチ集合
ステップ５：    if(Ｏ⊆Ａｉ){
集合Ｏ内の全ての宛先スイッチに対して、iを通るcを確立;
iへ、およびiからの使用されたリンク全てを利用不能としてマーク付け;
return(“成功”);
}
}
ステップ６： return(“決して生じず”);
【００３４】
上述のステップ１において、現在の接続要求を“ｃ”とラベル付けし、さらにｃの宛先スイッチの集合を“Ｏ”とラベル付けする。ステップ２においてループが開始され、全ての中間スイッチを通る。ｃの入力スイッチが中間スイッチｉへの利用可能なリンクを有していない場合、ステップ３において次の中間スイッチが選択されてｉになる。ステップ４においては、中間スイッチｉからの利用可能なリンクを有するｃの宛先スイッチの集合を判定する。ステップ５において、中間スイッチｉが接続要求ｃの宛先スイッチ全てへの利用可能なリンクを有する場合、接続要求ｃは中間スイッチｉを通して確立される。そして、中間スイッチｉの出力スイッチへの使用されたリンクの全てが将来の要求に対して利用不能とマーク付けされる。さらにその方法は”成功“を返す。これらのステップが全ての中間スイッチに対して繰り返される。１つの中間スイッチを常に発見することができ、それを通るｃが確立される。従って制御は決してステップ６に届かない。スケジューリング方法によって行われるステップ数がｍに比例することは容易に分かるが、ここで、ｍはそのネットワーク内の中間スイッチ数であり、従ってスケジューリング方法は時間計算量Ｏ（ｍ）によるものである。
【００３５】
表２は、１つの特定の実装例において、上述の擬似コードのステップ１−１６により、図４Ｃに示す方法のフローチャートがどのように実装されるかを示す。
2007532037.tif 000015
【００３６】
図４Ｄは１実施形態において、図４Ｃの方法を実装するコントローラのメモリからデータを格納、引き出すために使用されるデータ構造を示す図である。この実施形態において、各接続の入力スイッチ内の唯一のファンアウトが、２つのデータ構造（配列またはリンクリスト等）を使用して実装され、１つの中間スイッチから到達可能な宛先を示す。各接続要求５１０は宛先スイッチ識別子の配列５２０（および入力スイッチ識別子のインレットリンク）によって特定される。中間スイッチの別の配列５３０は、ネットワークの中間スイッチ全てに対して各１個ずつ、ｍ個の要素を含む。配列５３０の各要素は、配列５４０−１から５４０−ｍのｍ個の配列の１つに対するポインタを有し、図４Ｄに示す各出力スイッチＯＳ１−ＯＳｒに対する利用可能状態を示す状態ビット（以下、利用可能状態ビットという）を含む。出力スイッチに対する第２内部リンクが中間スイッチから利用可能な場合、図４Ｄに示すように、利用可能状態配列内の対応ビットは‘Ａ’（利用可能、即ち未使用リンクを表す）に設定される。それ以外の場合、対応ビットは‘Ｕ’（利用不可能、即ち使用されたリンクを表す）に設定される。
【００３７】
各接続５１０に対して、各中間スイッチＭＳｉをチェックして接続５１０の宛先全てがＭＳiから到達可能かどうかを調べる。詳細には、この条件は中間スイッチＭＳｉの利用可能状態配列５４０−ｉを使用してチェックされ、ＭＳｉから利用可能な接続５１０の宛先を判定する。１実装例においては、各宛先は中間スイッチＭＳｉから利用可能かどうかをチェックされ、中間スイッチＭＳｉが特定の宛先に対して利用可能性を有さない場合、中間スイッチＭＳｉ使用できず、接続は確立しない。図４Ｄの実施形態を実装して、（図１Ａ、図２Ａ、および図２Ｂ等を参照して上述した）コントローラ５５０およびメモリ５００内の接続を確立することができる。
【００３８】
再配置可能なノンブロッキングネットワークにおいては、スイッチのハードウェアコストは、接続確立に要する時間の増加の代償として削減される。再配置可能なノンブロッキングネットワークにおいては、新規接続に加えて、再配置を実装するために中断される既存接続がそれ自身確立される必要があるので、接続確立時間は増加する。このため、新規接続を確立するとき、既存接続に対する再配置の必要性を最小化または排除するのが望ましい。再配置の必要性が排除されると、そのネットワークは、中間スイッチ数およびスケジューリング方法によって、広義のノンブロッキングまたは厳密にノンブロッキングのいずれかである。２＊ｎ個以上の中間スイッチを使用する再配置可能なノンブロッキングネットワークの実施形態が、上述の中で言及により組み込んだ関連米国特許出願番号０９／９６７，８１５に記述されている。
【００３９】
厳密にノンブロッキングなマルチキャストネットワークにおいては、インレットリンクからアウトレットリンクの集合へのマルチキャスト接続を形成する任意の要求に対して、ネットワークを通るパスを発見し、既存のいずれのマルチキャスト接続を妨げることなく要求を満足させることが常に可能で、そのようなパスが複数利用可能な場合、将来の潜在的なマルチキャスト接続要求の実現を懸念せずに、任意のパスを選択できる。広義のノンブロッキングマルチキャストネットワークにおいても、ネットワークを通る接続パスを提供し、他の既存のマルチキャスト接続を妨げることなく要求を満足させることが常に可能であるが、この場合、接続要求を満足させるために使用されるパスは、将来のマルチキャスト接続要求に対してノンブロッキングな接続能力を維持するよう選択されなければならない。厳密にノンブロッキングなネットワークおよび広義のノンブロッキングネットワークにおいては、スイッチのハードウェアコストは増加するが、接続確立に要する時間は再配置可能なノンブロッキングネットワークと比較して削減される。３＊ｎ−１個以上の中間スイッチを使用する厳密にノンブロッキングなネットワークの実施形態は、時間計算量Ｏ（ｍ２）のスケジューリング方法を使用し、上述の中で言及により組み込んだ関連米国特許出願番号０９／９６７，１０６で記述されている。前述の詳論は、時間計算量Ｏ（ｍ）のスケジューリング方法の使用により、接続確立の時間をさらに削減する、厳密にノンブロッキングなネットワークの実施形態に関する。
【００４０】
次に本発明に対する証明を示す。上記で論じたように、Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークにおいては、インレットリンクが同一出力スイッチ上の複数のアウトレットリンクに接続される場合、対応する入力スイッチに唯一必要とされることは、その出力スイッチに対する１個のパスを有することである。従って、その接続は出力段階スイッチ内の望ましい出力リンクにファンアウトされる。従って出願人は、マルチキャスト問題は次の３つの異なるアプローチで解決できることを指摘する。
１）２段階内で１度だけファンアウトし、第１段階内で任意回数ファンアウトする。
２）第１段階内で１度だけファンアウトし、第２段階内で任意回数ファンアウトする。
３）第１および第２段階内の両方で最適な任意の回数ファンアウトする。
【００４１】
ＭａｓｓｏｎおよびＪｏｒｄａｎ（Ｇ．Ｍ．Ｍａｓｓｏｎ、Ｂ．Ｗ．Ｊｏｒｄａｎ、“一般化した多段階接続ネットワーク”、Ｎｅｔｗｏｒｋｓ，２：１９１−２０９頁、１９７２年Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，Ｉｎｃ）は、“第２段階内で１度だけファンアウトし、第１段階内で任意回数ファンアウトする”アプローチ１によって、再配置可能なノンブロッキングネットワークおよび厳密にノンブロッキングなネットワークを提示した。上述の中で言及により組み込んだ米国特許出願番号０９／９６７，８１５、および上述の中で言及により組み込んだ米国特許出願番号０９／９６７，１０６は、“第１および第２段階内の両方で最適な任意の回数ファンアウトする”アプローチ３によって、再配置可能なノンブロッキングネットワークおよび厳密にノンブロッキングなネットワークをそれぞれ提示した。
【００４２】
本発明は、“第１段階内で１度だけファンアウトし、第２段階内で任意回数ファンアウトする”アプローチ２を使用して、厳密にノンブロッキングなネットワークを提示する。本発明で提示された厳密にノンブロッキングなネットワークは、時間計算量Ｏ（ｍ）のスケジューリング方法を使用する。本発明に対する証明をするため、最初に本発明の対称ネットワークＶ（ｍ，ｎ，ｒ）の厳密にノンブロッキングな振る舞いに対する証明を提示する。その後、その証明を非対称ネットワークＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）にも拡張する。本発明に従って、出願人はＶ（ｍ，ｎ，ｒ）ネットワークに関するキーとなるいくつかの重要な所見を指摘する。
【００４３】
ユニキャスト接続に対する厳密にノンブロッキングな振る舞いはｍ≧２×ｎ−１であることを要し、ブロードキャスト接続に対する厳密にノンブロッキングな振る舞いはｍ≧ｎであることを要するので、接続のファンアウトがｘ（１≦ｘ≦ｒ）以下のとき、要求される中間スイッチの数は最大値に達することが分かる。これは、接続のファンアウトが１からｘまで増加すると、必要とされるｍが増加して最大値に達することを意味する。そして、接続のファンアウトがｘからｒまで増加すると必要とされるｍは、ネットワークが厳密にノンブロッキングな振る舞いで動作可能なように最大値からｎまで減少する。これは、ｘのどの値でｍが最大値に達し、ｍの最大値はいくつかという疑問にたどりつく。
【００４４】
Ｖ（ｍ，ｎ，ｒ）ネットワークの基本的な特性の１つは、同一入力ポートからは、２個のインレットリンクからの接続は同一中間スイッチを通して確立できないということである。これは、たとえ２個の要求に互換性があるとしても、それらは２個の異なる中間スイッチを通して確立されなければならないことを意味する。従って、ファンアウトｘを有するマルチキャスト割当が中間スイッチの最大値を要するためには、以下の２つの条件を満足させる必要がある。
１）同一入力スイッチのインレットリンクからの接続全ては、互換性であってもよく、なくてもよい。
２）入力ポートからの各インレットリンクは、残りの他の全ての入力ポートのインレットリンク全てからの接続と非互換性で、その非互換性は共通の宛先出力ポートが１つしかないために生じる。
【００４５】
これらの２つの条件を満たすとき、各接続は異なる中間スイッチを通して確立しなければならない。表１は３段階ネットワーク、即ちＶ（９，３，９）（図３Ａおよび図３Ｂに示す）に対する例示的なマルチキャスト割当を示しているが、ここでは、
2007532037.tif 000016
である。そのマルチキャスト割当は、図３Ａ（および図３Ｂ）のネットワークの出力リンク全てを使用する。表１のマルチキャスト割当は、上述した条件の両方を満足させる。入力スイッチの各々からの３つの接続要求は、それらの間では互換性があるが、その接続要求の全ては、残る全ての入力スイッチからの接続要求とは非互換性であり、その非互換性は共通出力ポートが１つしかないのために生じる。例えば、要求Ｉ１は宛先出力スイッチをＯＳ１、ＯＳ２、およびＯＳ３に有する。これらは要求Ｉ２の宛先スイッチＯＳ４、ＯＳ５、およびＯＳ６とは異なり、要求Ｉ３の宛先ＯＳ７、ＯＳ８、およびＯＳ９とも異なる。要求Ｉ１は入力スイッチＩＳ２からの要求、即ちＩ４、Ｉ５、Ｉ６とは非互換性である。それは、共通の宛先出力スイッチ１、２、および３が、それぞれ１つしかないためである。
【００４６】
Ｖ（９，３，９）のネットワークに対する表１のマルチキャスト割当において、ｎは
2007532037.tif 000017
であり奇数である。各要求のファンアウトは
2007532037.tif 000018
である。そのマルチキャスト割当においては、各出力ポートが全ての要求においてｎ回出現しているので、ネットワークの全てのアウトレットリンクが使用される。表１に示すマルチキャスト割当から、出願人は、各マルチキャスト接続を、その各入力スイッチからの接続が３＊３正方行列を形成する正方行列の行として表す。この３＊３正方行列は、各要素が異なる整数であり、行または列の数が例えばｎという奇数に等しいとすると、２つの異なる行列に属する任意の２つの行が有する共通要素はただ１つで、同一の行列に属する任意の２つの行は共通要素を有しないように配置することで、ｎ個の行列を生成できる。第２の行列を生成するため、第１の行列を転置する。第３の行列に対する割当を得るため、ｘを列数とするｘ−１の位置でラップアラウンドすることで、第２の行列の各列が上方にシフトされる。出願人は、これは行数または列数が奇数である任意の正方行列で真であると指摘する。
【００４７】
従って出願人は、本発明による３段階ネットワークにおいて、
2007532037.tif 000019
３） マルチキャスト割当のファンアウトが、異なるファンアウトの任意の組み合わせであるとき：出願人は、ファンアウトの任意の組み合わせのマルチキャスト割当に対する証明は、上記の３つの証明から直接導かれることを指摘する。
【００４８】
本発明の証明は、他の場合に対して一般化される。
2007532037.tif 000020
【００４９】
従って、本発明によると、一般的な対称３段階ネットワークＶ（ｍ，ｎ，ｒ）は以下の条件を満たす場合に厳密にノンブロッキングな方式で動作できる。
2007532037.tif 000021
【００５０】
出願人はここで、ｒ＝２のとき、ｍ≧ｎである場合、Ｖ（ｍ，ｎ，ｒ）のネットワークはマルチキャスト割当に対して再配置可能なノンブロッキング方式で動作可能であるという所見を述べる。これは、ユニキャスト割当に対してＶ（ｍ，ｎ，ｒ）のネットワークは再配置可能なノンブロッキングであり、ブロードキャスト割当、即ちファンアウトが２であるものに対しては、それが厳密にノンブロッキングであることが知られているからである。従って、任意のファンアウト、即ち１または２のいずれかのファンアウトのマルチキャスト割当に対して、ｍ≧ｎのとき、Ｖ（ｍ，ｎ，２）のネットワークは再配置可能なノンブロッキング方式で動作可能である。
【００５１】
本発明をＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークに拡張するため、以下の２つの場合を考える。最初は
2007532037.tif 000022
が奇数のときである。
１）  ｎ１＜ｎ２：ネットワーク内に総数ｎ２＊ｒ２個のアウトレットリンクがある場合でも、最悪の場合のシナリオにおいては、ｎ２＊ｒ２個の第２内部リンクのみが必要となる。これは、ｎ２＊ｒ２個の出力リンク全てが接続の宛先であったとしても、出力スイッチ内でのマルチキャスティングが実現できるためである。従って、ネットワークが厳密にノンブロッキングな振る舞いで動作可能であるためには、中間スイッチは
2007532037.tif 000023
個で十分である。
２）  ｎ１＞ｎ２：この場合、ネットワークに対して総数ｎ２＊ｒ２個のアウトレットリンクがあるため、ｎ２＊ｒ２個のアウトレットリンク全てがネットワーク接続の宛先であるとしても、最大でｎ２＊ｒ２個の第１内部リンクのみがアクティブとなる。従って、ネットワークが厳密にノンブロッキングな方式で動作可能であるためには、中間スイッチ
2007532037.tif 000024
個で十分である。
【００５２】
2007532037.tif 000025
【００５３】
出願人は、前述の証明の直接的拡張において、マルチキャスト割当のファンアウトが
2007532037.tif 000026
の範囲にあるｘ以下のとき、ｍ≧ｘ＊ＭＩＮ（ｎ１，ｎ２）で、Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）は厳密にノンブロッキングな方式で動作可能であることを指摘する。例えば、デュアルキャスト割当（ファンアウトが２以下）に対して、Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークはｍ≧２＊ＭＩＮ（ｎ１，ｎ２）のとき厳密にノンブロッキングな方式で動作可能である。同様にトリプルキャスト割当（ファンアウトが３以下）に対して、Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークはｍ≧３＊ＭＩＮ（ｎ１，ｎ２）のとき厳密にノンブロッキングな方式で動作可能、などである。最後に、ファンアウトが
2007532037.tif 000027
に等しいマルチキャスト割当に対して、Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークは以下を満たすとき厳密にノンブロッキングな方式で動作可能である。
2007532037.tif 000028
【００５４】
図５Ａを参照すると、５段階の厳密にノンブロッキングなネットワークが、再帰を以下のように使用する本発明の実施形態に従って示されている。５段階ネットワークは、それぞれがインレットリンクＩＬ１−ＩＬ１２およびアウトレットリンクＯＬ１−ＯＬ１２を有する入力段階１１０および出力段階１２０を備え、入力段階１１０は６つの２Ｘ４スイッチＩＳ１−ＩＳ６から成り、出力段階１２０は６つの４Ｘ２スイッチＯＳ１−ＯＳ６から成る。しかしながら、図１Ａの３段階ネットワークにおける中間段階１３０の単一スイッチとは異なり、図５Ａの中間段階１３０は４つの６Ｘ６の３段階サブネットワークＭＳ１−ＭＳ４（ここで“サブネットワーク”という用語は“ネットワーク”と同じ意味を有する）から成る。４つの中間スイッチＭＳ１−ＭＳ４の各々は６つの第１内部リンク（例えば、入力スイッチＩＳ１−ＩＳ６の各々から中間スイッチＭＳ１に対して接続されたリンクＦＬ１−ＦＬ６）を通して接続され、６つの第２内部リンク（例えば、中間スイッチＭＳ１から出力スイッチＯＳ１−ＯＳ６の各々に対して接続されたリンクＳＬ１−ＳＬ）を通して出力スイッチの各々に接続される。１実施形態においては、ネットワークは、入力段階１１０、出力段階１２０および中間段階サブネットワーク１３０と結合され、インレットリンクＩＬ１−ＩＬ１２および任意数のアウトレットリンクＯＬ１−ＯＬ１２の間の接続を形成するコントローラも含む。
【００５５】
中間スイッチＭＳ１−ＭＳ４の各々は、Ｖ（４，２，３）の３段階サブネットワークである。例えば、３段階サブネットワークＭＳ１は、インレットリンクＦＬ１−ＦＬ６を有する３つの２Ｘ４スイッチＭＩＳ１−ＭＩＳ３から成る入力段階と、アウトレットリンクＳＬ１−ＳＬ６を有する３つの４Ｘ２スイッチＭＯＳ１−ＭＯＳ３から成る出力段階とを備える。中間段階ＭＳ１は、４つの３Ｘ３スイッチＭＭＳ１−ＭＭＳ４から成る。中間スイッチＭＭＳ１−ＭＭＳ４の各々は、３つの第１内部リンク（例えば、入力スイッチＭＩＳ１−ＭＩＳ３の各々から中間スイッチＭＭＳ１に接続されたリンクＭＦＬ１−ＭＦＬ３）を通して入力スイッチＭＩＳ１−ＭＩＳ３の各々に接続され、３つの第２内部リンク（例えば、中間スイッチＭＭＳ１から出力スイッチＭＯＳ１−ＭＯＳ３の各々に接続されたリンクＭＳＬ１−ＭＳＬ３）を通して出力スイッチのＭＯＳ１−ＭＯＳ３の各々に接続される。同様に、段階の数は７、９等に増加できる。
【００５６】
本発明によると、図５Ａの３段階ネットワークは、
2007532037.tif 000029
の中間段階３段階サブネットワークであることが、厳密にノンブロッキングな方式で動作可能であるために必要である。従って、ｎが２に等しく、ｒが６に等しい図５Ａにおいては、中間段階１３０は
2007532037.tif 000030
が４に等しい中間段階の３段階ネットワークＭＳ１−ＭＳ４を有する。さらに、本発明によると、中間段階ネットワークＭＳ１−ＭＳ４の各々は３段階ネットワークであり、
2007532037.tif 000031
の中間スイッチＭＭＳ１−ＭＭＳ４であることを必要とする。ここで、ｐ１は各中間入力スイッチＭＩＳ１−ＭＩＳ３に対するインレットリンクの数で、ｑ１は中間段階内のスイッチの数（図５Ａにおいて３に等しい）で、ｐ２は中間出力スイッチＭＯＳ１−ＭＯＳ３に対するアウトレットリンクの数で、ｑ２は中間段階内のスイッチの数（図５Ａにおいて３に等しい）である。
【００５７】
一般に、一定の実施形態によると、第１、中間、最終段階のいずれかにおける、１つまたは複数のスイッチは任意のファンアウトのマルチキャスト接続に対して厳密にノンブロッキングな動作をするために、
2007532037.tif 000032
個以下の中間段階スイッチを有する３段階サブネットワークと再帰的に置換できる。ここで、ｎ１はサブネットワーク内の第１段階に対するインレットリンクの数、ｒ１はサブネットワークの第１段階におけるスイッチの数であり、ｎ２はサブネットワークの最終段階に対するアウトレットリンクの数、ｒ２はサブネットワークの最終段階におけるスイッチの数である。“サブネットワーク”という用語が“ネットワーク”と同じ意味を有するので、ちょうど今記述した置換は、実施形態によって、望ましい回数だけ再帰的に繰り返すことができる。さらに各サブネットワークは、対応するネットワークのマルチキャスト接続をスケジューリングする別個のコントローラおよびメモリを有してもよい。
【００５８】
当然のことながら、今まで論じた方法は、ネットワーク内の任意のスイッチ上で開発された設計基準を再帰的に使用することによって、ｋ＞３であるｋ段階ネットワークに対して適用可能である。３段階ネットワークの観点で方法を提示したのは、表記上の利便性のためだけである。即ち、これらの方法は、ネットワーク内の（少なくとも１つの）スイッチの各サブセットをより小さな３段階ネットワークと再帰的に置換することにより一般化できる。ここで、より小さな３段階ネットワークは置換されるスイッチと同数のインレットリンク総数およびアウトレットリンク総数を有する。例えば、３段階ネットワークにおいて、入力、中間または出力段階のいずれかにおける１つまたは複数のスイッチを３段階ネットワークと置換して、ネットワークを拡張できる。例えば、５段階ネットワークが望ましいならば、全ての中間スイッチ（または全ての入力スイッチまたは全ての出力スイッチ）が３段階ネットワークと置換される。
【００５９】
本発明によると、任意の再帰的３段階ネットワークにおいて、各接続は第１段階スイッチ内で１つの中間段階サブネットワークにのみファンアウトでき、中間スイッチおよび最終段階スイッチ内で、接続要求によって要求される任意回数ファンアウトできる。例えば図５Ａのネットワーク内で示されるように、接続Ｉ１は第１段階スイッチＩＳ１内で１度中間段階サブネットワークＭＳ１にファンアウトする。中間段階サブネットワークＭＳ１内で、その接続は出力スイッチＯＳ１、ＯＳ２、およびＯＳ３に３度ファンアウトする。出力スイッチＯＳ１およびＯＳ３内でその接続は２度ファンアウトする。詳細には、出力スイッチＯＳ１内でアウトレットリンクＯＬ１、ＯＬ２にファンアウトし、出力スイッチＯＳ３内でアウトレットリンクＯＬ５、ＯＬ６にファンアウトする。出力スイッチＯＳ２内で、その接続は１度アウトレットリンクＯＬ４にファンアウトする。しかしながら３段階ネットワークＭＳ１においては、その接続は１度だけ第１段階内でファンアウトする。例えば、接続Ｉ１は入力スイッチＭＩＳ１内で３段階サブネットワークＭＳ１の中間スイッチＭＭＳ２に１度ファンアウトする。同様に、接続は任意の３段階サブネットワークの中間および最終段階内で任意回数ファンアウトできる。例えば、接続Ｉ１は中間スイッチＭＭＳ２内で２度、３段階サブネットワークＭＳ１の出力スイッチＭＯＳ１およびＭＯＳ２にファンアウトする。３段階サブネットワークＭＳ１の出力スイッチＭＯＳ１内で、その接続は２度出力スイッチＯＳ１およびＯＳ２にファンアウトする。３段階サブネットワークＭＳ１の出力スイッチＭＯＳ２内で、その接続は１度出力スイッチＯＳ３にファンアウトする。
【００６０】
接続Ｉ３は３段階サブネットワークＭＳ２に１度ファンアウトし、そこで出力スイッチＯＳ２、ＯＳ４、およびＯＳ６に３度ファンアウトする。出力スイッチＯＳ２、ＯＳ４、およびＯＳ６内で、その接続は１度アウトレットリンクＯＬ３、ＯＬ８、およびＯＬ１２にそれぞれファンアウトする。接続Ｉ３は３段階サブネットワークＭＳ２の入力スイッチＭＩＳ４内で１度、３段階サブネットワークＭＳ２の中間スイッチＭＭＳ６にファンアウトし、そこで３段階サブネットワークＭＳ２の出力スイッチＭＯＳ４、ＭＯＳ５、およびＭＯＳ６に３度ファンアウトする。３段階サブネットワークＭＳ２の３つの出力スイッチＭＯＳ４、ＭＯＳ５およびＭＯＳ６の各々において、その接続は１度出力スイッチＯＳ２、ＯＳ４、およびＯＳ６にそれぞれファンアウトする。
【００６１】
図５Ｂは、図５Ａのコントローラによって実行される１実施形態における、厳密なスケジューリング方法のハイレベルなフローチャートを示す。図５Ｂの方法は、３つの段階を有し、その各段階が３段階サブネットワークから構成されるネットワークに対してのみ、図５Ａを参照して上述した再帰的な方式で使用される。この実施形態によると、マルチキャスト接続要求は動作２５０（図５Ｂ）において受信される。その後、要求を満足する接続が、その入力スイッチから１つの中間段階サブネットワークのみにファンアウトすることによって、動作２６０において確立される。その後、１実施形態においては、制御は動作２７０に進む。動作２７０はネットワーク内に含まれる各サブネットワークを再帰的に通る。動作２７０で発見される各サブネットワークに対して、制御は動作２８０に進み、各サブネットワークはネットワークとして扱われ、スケジューリングが同様に行われる。全ての再帰的サブネットワークがスケジューリングされると、制御は動作２７０から動作２５０に移り、各マルチキャスト接続はループ内で同様にスケジューリングされる。
【００６２】
表３は、Ｖ（ｍ，ｎ，ｒ）のネットワークが厳密にノンブロッキングな方式で動作可能であるために要求される中間段階スイッチの最小数ｍを、数個の例示的なｒの値に対して列挙する。
2007532037.tif 000033
【００６３】
Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークは、１実施形態において、以下の段階を有することによりさらに一般化することができる。その段階とは、ｒ１個の入力スイッチおよび、そのｒ１個の入力スイッチの各々に対する、ｗ∈［１，ｒ１］かつｎ１＝ＭＡＸ（ｎ１ｗ）となるような、入力スイッチｗ内のｎ１ｗ個のインレットリンクを備える入力段階；ｒ２個の出力スイッチおよび、そのｒ２個の出力スイッチの各々に対する、ｖ∈［１，ｒ２］かつｎ２＝ＭＡＸ（ｎ２ｖ）となるような、出力スイッチｖ内のｎ２ｖ個のアウトレットリンクを備える出力段階；およびｍ個の中間スイッチを備え、各中間スイッチは、総数少なくともｒ１個の第１内部リンクに対して、各入力スイッチに接続された少なくとも１つのリンクを備え；さらに各中間スイッチは、総数少なくともｄ個（１≦ｄ≦ｒ２）の第２内部リンクに対して、多くともｄ個の出力スイッチに接続された少なくとも１つのリンクを備える中間段階である。出願人は、本発明によると、そのような実施形態は、以下を満たすとき入力スイッチ内で１度だけファンアウトすることによりマルチキャスト接続に対して厳密にノンブロッキングな方式で動作できることを指摘する。
2007532037.tif 000034
【００６４】
本発明は、時間計算量Ｏ（ｍ）のスケジューリング方法を使用する厳密にノンブロッキングなネットワークの実施形態に関し、マルチキャスト接続は入力スイッチ内で１度だけファンアウトすることにより確立される。時間計算量Ｏ（ｍ）のスケジューリング方法を使用するが、マルチキャスト接続が、そのマルチキャスト接続を選択的に２度以上ファンアウト分割することにより、入力スイッチ内で２度以上ファンアウトされるような厳密にノンブロッキングなネットワークの実施形態は、（ここで、厳密にノンブロッキングな動作のためにより少ない数の中間スイッチｍを要求し、従ってネットワークのコストを削減する実施形態もある）上述の中で参照により組み込んだ関連米国特許出願ドケット番号Ｖ−０００４およびそのＰＣＴ出願ドケット番号Ｓ−０００４において記述されている。
【００６５】
これまで記述したＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークの実施形態は、本発明においては、空間‐空間‐空間、別名ＳＳＳ構成で実装される。この構成では、全ての入力スイッチ、出力スイッチ、および中間スイッチは別個のスイッチ、例えば１実施形態ではクロスバースイッチとして実装される。３段階ネットワークＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）は時間‐空間‐時間、別名ＴＳＴ構成で実装されることもできる。ＴＳＴ構成では、第１段階および最終段階において全ての入力スイッチおよび全ての出力スイッチは別個のスイッチとして実装される。
2007532037.tif 000035
であり、各中間スイッチは全ての入力スイッチに接続されたｒ１個の第１内部リンクと、全ての出力スイッチに接続されたｒ２個の第２内部リンクとを有する。ＴＳＴ構成は、本発明によると、循環方式fashionでＭＩＮ（ｎ１，ｎ２）ステップでスイッチング機構を実装する。従ってＴＳＴ構成においては、中間段階は物理的に
2007532037.tif 000036
の中間スイッチのみを実装し；それらはＭＩＮ（ｎ１，ｎ２）ステップで時間的に共有され、入力ポートから出力ポートへパケットまたはタイムスロットをスイッチする。
【００６６】
ＴＳＴ構成で実装された３段階ネットワークＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）は、通信スイッチングシステムにおいてキーとなる役割を果たす。ＳＯＮＥＴ／ＳＤＨシステム等のＴＤＭベースのスイッチングシステムにおけるクロスコネクトの１実施形態においては、各通信リンクは、例えばＯＣ−１２  ＳＯＮＥＴリンクが時分割多重された３３６  ＶＴ１．５チャネルから成るように、時分割多重される。ＩＰパケットなどをスイッチするパケットベースのスイッチングシステムにおけるスイッチファブリックの別の実施形態においては、各通信リンクは統計的に時分割多重される。Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークがＴＤＭまたはパケットベースのリンクをスイッチするとき、ｒ１個の入力スイッチの各々は時分割多重信号を受信する。例えば、各入力スイッチがＯＣ−１２  ＳＯＮＥＴストリームを受信し、スイッチング粒度がＶＴ１．５である場合、ｎ１（＝３３６）個のインレットリンクのそれぞれはＯＣ−１２フレーム内で異なるＶＴ１．５チャネルを受信する。Ｖ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークを使用してスイッチするクロスコネクトは、ＴＳＴ構成を実装し、リンク内の通信が時分割多重方式で行われるのとちょうど同じようにスイッチングも時分割多重方式で行われる。
【００６７】
例えば、図６Ａのネットワークは、空間‐空間‐空間構成においてマルチキャスト割当Ｉ１＝｛１｝、Ｉ２＝｛１，３，４｝、Ｉ６＝｛３｝、Ｉ９＝｛２｝、Ｉ１１＝｛４｝、Ｉ１２＝｛３，４｝を有する例示的な３段階ネットワーク、即ちＶ（６，３，４）を示す。本発明によると、マルチキャスト割当は、各接続を第１段階内で多くて１回ファンアウトすることにより確立される。接続Ｉ１は第１段階スイッチＩＳ１内で中間段階スイッチＭＳ１にファンアウトし、中間段階ＭＳ１内で出力スイッチＯＳ１にファンアウトする。接続Ｉ１はまた、最終段階スイッチＯＳ１内でアウトレットリンクＯＬ２およびＯＬ３にファンアウトする。接続Ｉ２は第１段階スイッチＩＳ１内で中間段階スイッチＭＳ３にファンアウトし、中間段階スイッチＭＳ３内で出力スイッチＯＳ１、ＯＳ３、およびＯＳ４にファンアウトする。接続Ｉ２はまた、最終段階スイッチＯＳ１、ＯＳ３、およびＯＳ４内でアウトレットリンクＯＬ１、ＯＬ７およびＯＬ１２にそれぞれファンアウトする。接続Ｉ６は入力スイッチＩＳ２内で１度中間スイッチＭＳ２にファンアウトし、中間段階スイッチＭＳ２内で最終段階スイッチＯＳ３にファンアウトする。接続Ｉ６は出力スイッチＯＳ３内で１度アウトレットリンクＯＬ９にファンアウトする。
【００６８】
接続Ｉ９は入力スイッチＩＳ３内で１度中間スイッチＭＳ４にファンアウトし、中間スイッチＭＳ４内で１度出力スイッチＯＳ２にファンアウトする。接続Ｉ９は出力スイッチＯＳ２内でアウトレットリンクＯＬ４、ＯＬ５、およびＯＬ６にファンアウトする。接続Ｉ１１は入力スイッチＩＳ４内で１度中間スイッチＭＳ６にファンアウトし、中間スイッチＭＳ６内で１度出力スイッチＯＳ４にファンアウトする。接続Ｉ１１は出力スイッチＯＳ４内でアウトレットリンクＯＬ１０にファンアウトする。接続Ｉ１２は入力スイッチＩＳ４内で１度中間スイッチＭＳ５にファンアウトし、中間スイッチＭＳ５内で２度出力スイッチＯＳ３およびＯＳ４にファンアウトする。接続Ｉ１２は出力スイッチＯＳ３およびＯＳ４内でアウトレットリンクＯＬ８およびＯＬ１１にそれぞれファンアウトする。
【００６９】
図６Ｂ、図６Ｃ、および図６Ｄは、図６ＡにおけるＶ（６，３，４）のネットワークのＴＳＴ構成の実装を示す。本発明によると、ＴＳＴ構成においてもマルチキャスト割当は、ＳＳＳ構成で行われるのとまさに同じスケジューリング方法で、各接続を第１段階内で多くて１度ファンアウトすることにより確立される。図６Ａのネットワークにおいてｎ＝３であるから、図６ＡのネットワークのＴＳＴ構成はｎ＝３個の異なる時間ステップを有し、ｍ／ｎ＝２であるから、ＴＳＴ構成における中間段階は、図６Ｂ、図６Ｃ，および図６Ｄに示したように４つの第１内部リンクおよび４つの第２内部リンクを各々が有する２つの中間段階スイッチのみを実装する。第１時間ステップにおいては、図６Ｂに示すように、２つの中間スイッチは図６ＡのネットワークのＭＳ１およびＭＳ２のように機能する。同様に第２時間ステップにおいては、図６Ｃに示すように、２つの中間スイッチは図６ＡのネットワークのＭＳ３およびＭＳ４のように機能し、第３時間ステップにおいては、図６Ｄに示すように、２つの中間スイッチは図６ＡのネットワークのＭＳ５およびＭＳ６のように機能する。
【００７０】
第１時間ステップにおいて、図６Ｂは中間スイッチＭＳ１およびＭＳ２のスイッチング機能性を実装し、図６Ａのネットワークにおいて接続Ｉ１とＩ６は中間スイッチＭＳ１およびＭＳ２を通して出力スイッチＯＳ１およびＯＳ３にそれぞれファンアウトされるため、全ての３段階において図６Ａのネットワーク内でそれらが確立されるのと全く同じように、接続Ｉ１とＩ６は宛先アウトレットリンクＯＬ２、ＯＬ３およびＯＬ９にそれぞれファンアウトされる。同様に第２時間ステップにおいては、図６Ｃは中間スイッチＭＳ３およびＭＳ４のスイッチング機能性を実装し、図６Ａのネットワークにおいて接続Ｉ２とＩ９は中間スイッチＭＳ３およびＭＳ４を通して出力スイッチ｛ＯＳ１、ＯＳ３、ＯＳ４｝およびＯＳ２にそれぞれファンアウトされるため、全ての３段階において図６Ａのネットワーク内でそれらが確立されるのと全く同じように、接続Ｉ２とＩ９は宛先アウトレットリンク｛ＯＬ１、ＯＬ７、ＯＬ１２｝および｛ＯＬ４、ＯＬ５、ＯＬ６｝にそれぞれファンアウトされる。
【００７１】
同様に第３時間ステップにおいては、図６Ｄは中間スイッチＭＳ５およびＭＳ６のスイッチング機能性を実装し、図６Ａのネットワークにおいて接続Ｉ１１とＩ１２は中間スイッチＭＳ５およびＭＳ６を通して出力スイッチＯＳ４および｛ＯＳ３、ＯＳ４｝にそれぞれファンアウトされるため、全ての３段階において図６Ａのネットワーク内でそれらがルーティングされるのと全く同じように、接続Ｉ１１とＩ１２は宛先アウトレットリンクＯＬ１０および｛ＯＬ８、ＯＬ１１｝にそれぞれファンアウトされる。デジタルクロスコネクト、光クロスコネクト、およびパケットまたはセルスイッチファブリックにおいては、インレットリンクおよびアウトレットリンクが時分割多重方式で使用されるため、ＴＳＴ構成で実装されたＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワーク等のスイッチングネットワークはコスト、電力および空間を節約するであろう。
【００７２】
本発明によると、ＴＳＴ構成で実装されたＶ（ｍ，ｎ１，ｒ１，ｎ２，ｒ２）のネットワークは、ＳＳＳ構成におけるスケジューリング方法と同じものを使用、即ち、各接続が第１段階スイッチ内で１つの中間段階スイッチのみにファンアウトし、中間スイッチ内および最終段階スイッチ内で接続要求によって要求された任意回数ファンアウトできることで、中間スイッチの数がｍ／ＭＩＮ（ｎ１，ｎ２）である厳密にノンブロッキングな方式で動作可能である。ここで、
2007532037.tif 000037
である。
【００７３】
ここで記述した実施形態、実装、および例の多数の変更および適合化は、本発明の観点から当業者に対して明らかである。
【００７４】
例えば１実施形態において、入力段階スイッチが１度のみ中間段階にファンアウトする場合、入力段階スイッチはマルチキャスト能力なしにユニキャスト能力のみで実装できる。
【００７５】
例えば、別の実施形態において、上述したタイプの方法は以下のようにマルチレート多段階ネットワークを確立するよう変更される。詳細には、マルチレート接続はある種のマルチキャスト接続として特定できる。マルチキャスト接続においては、インレットリンクは複数のアウトレットリンクに送信する一方、マルチレート接続においては、全ての使用中のパス内のデータ転送率がマルチレート接続要求の要件を満たすとき、複数のインレットリンクが単一のアウトレットリンクに送信する。そのような場合、マルチレート接続は（出力段階から入力段階に逆方向で働く方法で）、出力段階内で多くとも２度（ファンアウトの代わりに）ファンインし、入力段階および中間段階内で任意にファンインして、確立できる。３段階マルチレートネットワークは、特定の実施形態に対して上述した中間段階スイッチの数に関するものと全く同じ要件で、厳密にノンブロッキングな方式で動作する。
【００７６】
多数のそのような修正および適合化は、添付の請求項によって包含される。
【図面の簡単な説明】
【００７７】
【図１Ａ】図１Ａは、本発明による例示的なマルチキャスト接続を有する例示的な３段階対称ネットワークの図である。
【図１Ｂ】図１Ｂは、図１Ａのネットワーク１００におけるマルチキャスト接続の確立に使用される、本発明によるスケジューリング方法の高レベルフローチャートである。
【図２Ａ】図２Ａは、ｒ個の入力段階スイッチ内の各々にｎ個のインレットリンクを有し、ｒ個の出力段階スイッチ内の各々にｎ個のアウトレットリンクを有し、さらに
【数１】
2007532037.tif 000038
１実施形態における図１Ｂの方法とともに使用されるｍ個の中間段階スイッチを有する、一般的な対称３段階厳密ノンブロッキングネットワークの図である。
【図２Ｂ】図２Ｂは、ｒ１個の入力段階スイッチ内の各々にｎ１個のインレットリンクを有し、ｒ２個の出力段階スイッチ内の各々にｎ２個のアウトレットリンクを有し、さらに
【数２】
2007532037.tif 000039
であるような１実施形態における図１Ｂの方法とともに使用される個の中間段階スイッチを有する、一般的な非対称３段階厳密ノンブロッキングネットワークの図である。
【図３Ａ】図３Ａは、一定の既存マルチキャスト接続を有する例示的なＶ（９，３，９）のネットワークを示す図である。
【図３Ｂ】図３Ｂは、１実装例における図１Ｂの方法を使用して、ネットワーク内の中間スイッチの１つを選択することによって新規接続を確立した後の図３Ａのネットワークを示す図である。
【図４Ａ】図４Ａは、図１Ｂにおける動作１４０の１実装例の中間レベルフローチャートである。
【図４Ｂ】図４Ｂは、図４Ａの方法における動作１４２の１変形の低レベルフローチャートである。
【図４Ｃ】図４Ｃは、図４Ｂのスケジューリング方法の1例に対する擬似コードを示すフローチャートである。
【図４Ｄ】図４Ｄは、１実施形態において、図４Ｃの方法を実装するコントローラのメモリからデータを格納、引き出すために使用されるデータ構造を実装する図である。
【図５Ａ】図５Ａは、中間段階スイッチがそれぞれ３段階ネットワークである、例示的な３段階ネットワークの図である。
【図５Ｂ】図５Ｂは、１実施形態において図５Ａのネットワーク等の再帰的に大きな多段階ネットワークにおいて再帰的にスケジューリングする方法の、高レベルフローチャートである。
【図６Ａ】図６Ａは、
【数３】
2007532037.tif 000040
を満たすｍ＝２×ｎ個の中間段階スイッチを有し、空間‐空間‐空間構成で実装され、図１Ｂの方法１４０を使用して確立した一定の既存マルチキャスト接続を有する、例示的なＶ（６，３，４）の３段階ネットワークの図である。
【図６Ｂ】図６Ｂは、図６ＡにおけるネットワークのＴＳＴ実装の第１時間ステップである。
【図６Ｃ】図６Ｃは、図６ＡにおけるネットワークのＴＳＴ実装の第２時間ステップである。
【図６Ｄ】図６Ｄは、図６ＡにおけるネットワークのＴＳＴ実装の第３時間ステップである。
【図１Ａ】
2007532037.tif 000047
【図１Ｂ】
2007532037.tif 000048
【図２Ａ】
2007532037.tif 000049
【図２Ｂ】
2007532037.tif 000050
【図３Ａ】
2007532037.tif 000051
【図３Ｂ】
2007532037.tif 000052
【図４Ａ】
2007532037.tif 000053
【図４Ｂ】
2007532037.tif 000054
【図４Ｃ】
2007532037.tif 000055
【図４Ｄ】
2007532037.tif 000056
【図５Ａ】
2007532037.tif 000057
【図５Ｂ】
2007532037.tif 000058
【図６Ａ】
2007532037.tif 000059
【図６Ｂ】
2007532037.tif 000060
【図６Ｃ】
2007532037.tif 000061
【図６Ｄ】
2007532037.tif 000062
【国際調査報告】
2007532037.tif 000063
2007532037.tif 000064