(57)【特許請求の範囲】
【請求項１】
入力ステージ、中間ステージ、および出力ステージを有するマルチキャストスイッチングシステムであって、
前記入力ステージに設けられ、入力元からのストリームを受信し、および前記受信したストリームの１つを前記中間ステージに伝送する複数の入力スイッチ要素と、
前記中間ステージに設けられ、前記複数の入力スイッチ要素のそれぞれから伝送されたストリームを受信し、および前記受信したストリームを前記出力ステージに伝送する複数の中間スイッチ要素であって、前記複数の中間スイッチ要素は、複数のグループにグループ化されている、中間スイッチ要素と、
前記出力ステージに設けられ、前記複数の中間スイッチ要素のうちの少なくとも１つから伝送されたストリームを受信し、および前記受信したストリームを出力先に出力する複数の出力スイッチ要素と
を備え、
前記複数の入力スイッチ要素のそれぞれは、前記入力元から受信したストリームのそれぞれに対し、前記複数のグループの全てを割り当て、前記割り当てた複数のグループの全てに、前記入力元から受信したストリームを伝送することによって、前記中間ステージへの第１のルーティング処理を行い、
前記複数の出力スイッチ要素は、前記第１のルーティング処理の結果として選択される、前記グループから伝送されるストリームを受信し、および前記受信したストリームを出力先に出力することによって、第２のルーティング処理を行う、
ことを特徴とするマルチキャストスイッチングシステム。
【請求項２】
前記複数の入力スイッチ要素の数はｒ1個であり、前記複数の中間スイッチ要素の数はｍ個であり、前記複数のグループの数はＲ個であり、前記複数の出力スイッチ要素の数はｒ2個であり、
前記ｒ1個の入力スイッチ要素のうちのｉ番目の入力スイッチ要素は、帯域幅ｓ1,iのｎ1,i（ｎ1,i≧１）本の第１の入力リンクと、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ2,iのｎ2,i（ｎ2,i≧１）本の合計ｍ×ｎ2,i本の第１の出力リンクとを有し、前記ｎ1,i本の第１の入力リンクを合計した多重度ｄ1,i（ｄ1,i＞１）で前記ストリームを受信し、および前記ｎ2,i本の第１の出力リンクを合計した多重度ｄ2,i（ｄ1,i＞１）で前記受信したストリームを伝送し、
前記ｍ個の中間スイッチ要素は、前記ｉ番目の入力スイッチ要素と接続する、合計
【数１】
0006795172.tif 000069
本の第２の入力リンクと、前記ｒ2個の出力スイッチ要素のうちのｊ番目の出力スイッチ要素と接続する合計
【数２】
0006795172.tif 000070
本の第２の出力リンクとを有し、前記
【数３】
0006795172.tif 000071
本の第２の入力リンクの各々は、帯域幅ｓ2,iのｎ2,i本のリンクを有し、前記
【数４】
0006795172.tif 000072
本の第２の出力リンクの各々は、帯域幅ｓ3,jのｎ3,j本のリンクを有し、
前記ｊ番目の出力スイッチ要素は、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ3,jのｎ3,j本の合計ｍ×ｎ3,j本の第３の入力リンクと、帯域幅ｓ4,jのｎ4,jの（ｎ4,j≧１）本の第３の出力リンクとを有し、前記ｎ3,j本の第３の入力リンクの合計で多重度ｄ3,j（ｄ3,j＞１）で前記伝送されたストリームを受信し、および前記ｎ4,j本の第３の出力リンクの合計で多重度ｄ4,j（ｄ4,4＞１）で前記受信したストリームを出力し、
式（１）乃至（４）
ｍ＝ｋ×Ｒ＞１（ｋ≧１、Ｒ≧１）
式（１）
前記ｉ番目の入力スイッチ要素において、
ｎ1,i×ｓ1,i≦ｋ×ｎ2,i×ｓ2,i、かつｄ1,i≦ｋ×ｄ2,i
式（２）
前記ｊ番目の出力スイッチ要素において、
ｎ4,j×ｓ4,j≦Ｒ×ｎ3,j×ｓ3,j、かつｄ4,j≦Ｒ×ｄ3,j
式（３）
出力ステージ全体において、
【数５】
0006795172.tif 000073
かつ
【数６】
0006795172.tif 000074
を満たすことを特徴とする請求項１に記載のマルチキャストスイッチングシステム。
【請求項３】
前記複数の入力スイッチ要素のそれぞれは、出力要求の有無によらずに前記第１のルーティング処理を行い、
前記第１のルーティング処理で設定された経路は削除されない
ことを特徴とする請求項２に記載のマルチキャストスイッチングシステム。
【請求項４】
前記複数の入力スイッチ要素の数はｒ1個であり、前記複数の中間スイッチ要素の数はｍ個であり、前記複数の出力スイッチ要素の数はｒ2個であり、
前記ｒ1個の入力スイッチ要素のうちのｉ番目の入力スイッチ要素は、帯域幅ｓ1,iのｎ1,i（ｎ1,i≧１）本の第１の入力リンクと、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ2,iのｎ2,i（ｎ2,i≧１）本の合計ｍ×ｎ2,i本の第１の出力リンクとを有し、前記ｎ1,i本の第１の入力リンクを合計した多重度ｄ1,i（ｄ1,i＞１）で前記ストリームを受信し、および前記ｎ2,i本の第１の出力リンクを合計した多重度ｄ2,i（ｄ1,i＞１）で前記受信したストリームを伝送し、
前記ｍ個の中間スイッチ要素は、前記ｉ番目の入力スイッチ要素と接続する、合計
【数７】
0006795172.tif 000075
本の第２の入力リンクと、前記ｒ2個の出力スイッチ要素のうちのｊ番目の出力スイッチ要素と接続する合計
【数８】
0006795172.tif 000076
本の第２の出力リンクとを有し、前記
【数９】
0006795172.tif 000077
本の第２の入力リンクの各々は、帯域幅ｓ2,iのｎ2,i本のリンクを有し、前記
【数１０】
0006795172.tif 000078
本の第２の出力リンクの各々は、帯域幅ｓ3,jのｎ3,j本のリンクを有し、
前記ｊ番目の出力スイッチ要素は、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ3,jのｎ3,j本の合計ｍ×ｎ3,j本の第３の入力リンクと、帯域幅ｓ4,jのｎ4,jの（ｎ4,j≧１）本の第３の出力リンクとを有し、前記ｎ3,j本の第３の入力リンクの合計で多重度ｄ3,j（ｄ3,j＞１）で前記伝送されたストリームを受信し、および前記ｎ4,j本の第３の出力リンクの合計で多重度ｄ4,j（ｄ4,4＞１）で前記受信したストリームを出力し、
前記ｍ個の中間スイッチ要素の個数ｍは、
ｍ＝ｋ×Ｒ−ｗ＞１（ｋ＞１、Ｒ＞１、ｗ≧１）
式（５）
を満たし、式（６）乃至式（１０）
【数１１】
0006795172.tif 000079
【数１２】
0006795172.tif 000080
【数１３】
0006795172.tif 000081
【数１４】
0006795172.tif 000082
【数１５】
0006795172.tif 000083
によって、それぞれが、ｍi,j個の中間スイッチ要素を有する１個以上の部分集合Ｇi,jに分解され、前記複数のグループの数は、少なくともＲ−ＤR個であり、前記中間スイッチ要素の削減数ｗは、最大でＤR×ｋ個であり、
前記ｉ番目の入力スイッチ要素の入力ステージにおけるルーティング処理において、
少なくとも一つのｗi,j＞０となる部分集合Ｇi,jに属する全てのグループのｙ番目（ｗi,j＋Ｋj≧ｙ≧Ｋj）の中間スイッチ要素の集合Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ）∩Ｇi,j｜がＲi−１であり、全てのグループのｙ’番目 （ｋj＋Ｋj＞ｙ’＞ｗi,j＋Ｋj）がある場合、前記中間スイッチ要素の集合Ｄ（Ｉ，ｙ’）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ’）∩Ｇi,j｜は少なくともＲiであり、
その部分集合Ｇi,jにおいて、Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数がＲi−１であり、かつ、Ｇi,j内で同一の中間スイッチ要素の集合を使用するＤ（Ｉ，ｙ）∩Ｇi,jは、最大でＲi−１組であり、
前記ｉ番目の入力スイッチ要素において、
ｎ1,i×ｓ1,i≦ｋ×ｎ2,i×ｓ2,i、かつｄ1,i≦ｋ×ｄ2,i
式（１１）
を満たし、
前記ｊ番目の出力スイッチ要素において、（ｎ3,j×ｓ3,j）＜ｍａｘ（ｎ2,I×ｓ2,i）の場合、
ｎ4,j×ｓ4,j≦（Ｒ−ＤR）×ｎ3,j×ｓ3,j、かつｄ4,j≦（Ｒ−ＤR）×ｄ3,j
式（１２）
を満たし、（ｎ3,j×ｓ3,j）≧ｍａｘ（ｎ2,I×ｓ2,i）の場合、
ｎ4,j×ｓ4,j≦Ｒ×ｎ3,j×ｓ3,j、かつｄ4,j≦Ｒ×ｄ3,j
式（１３）
を満たし、
出力ステージ全体において、
【数１６】
0006795172.tif 000084
かつ
【数１７】
0006795172.tif 000085
を満たすことを特徴とする請求項１に記載のマルチキャストスイッチングシステム。
【請求項５】
前記複数の出力スイッチ要素は、前記第１のルーティング処理の結果として選択される、前記複数の中間スイッチ要素のうち、その部分集合G（ｉ，ｊ）における少なくともＲi−１個のグループから伝送されるストリームを前記出力先に出力することによって、前記第２のルーティング処理を行い、既存のマルチキャスト配信をその部分集合Ｇ（ｉ，ｊ）における少なくともＲi個のグループの中間スイッチ要素から構成される迂回路に再配置し、
前記第１のルーティング処理で設定された経路は削除されない
ことを特徴とする請求項４に記載のマルチキャストスイッチングシステム。
【請求項６】
前記ｒ1個の入力スイッチ要素のうちの１つもしくは複数は、前記ｉ番目の入力スイッチ要素と接続された前記第１の入力リンクのうちのｎ’1本を、帯域幅ｓ’1で
【数１８】
0006795172.tif 000086
本と置き換えるか、
前記ｍ個の中間スイッチ要素のうちの１つもしくは複数は、前記ｉ番目の入力スイッチ要素の前記第１の出力リンクと接続された前記第２の入力リンクのうちのｎ’2本を、帯域幅ｓ’2で
【数１９】
0006795172.tif 000087
本と置き換えるか、
前記ｍ個の中間スイッチ要素のうちの１つもしくは複数は、前記ｊ番目の出力スイッチ要素の前記第３の入力リンクと接続された前記第２の出力リンクのうちのｎ’3本を、帯域幅ｓ’3で
【数２０】
0006795172.tif 000088
本と置き換えるか、または、
前記ｒ2個の出力スイッチ要素のうちの１つもしくは複数は、前記ｊ番目の出力スイッチ要素と接続された前記第３の出力リンクのうちのｎ’4本を、帯域幅ｓ’4で
【数２１】
0006795172.tif 000089
本と置き換える
ことを特徴とする請求項２乃至５のいずれか一項に記載のマルチキャストスイッチングシステム。
【請求項７】
入出力ステージおよび中間ステージを有するマルチキャストスイッチングシステムであって、
前記入出力ステージに設けられ、入力元からのストリームを受信し、前記受信したストリームを前記中間ステージに伝送する複数の入出力スイッチ要素と、
前記中間ステージに設けられ、前記複数の入出力スイッチ要素のそれぞれから前記伝送されたストリームを受信し、および前記受信したストリームを前記入出力ステージに伝送する複数の中間スイッチ要素であって、前記複数の中間スイッチ要素は、複数のグループにグループ化されている、中間スイッチ要素と
を備え、
前記複数の入出力要素のそれぞれは、前記入力元から受信したストリームのそれぞれに対し、前記複数のグループの全てを割り当て、前記割り当てた複数のグループの全てに、前記入力元から受信したストリームを伝送することによって、前記中間ステージへの第１のルーティング処理を行い、
前記複数の入出力スイッチ要素は、前記第１のルーティング処理の結果として選択される、前記グループから伝送されるストリームを受信し、および前記受信したストリームを出力先に出力することによって、第２のルーティング処理を行う、
ことを特徴とする双方向伝送マルチキャストスイッチングシステム。
【請求項８】
前記複数の入出力スイッチ要素の数はｒ個であり、前記複数の中間スイッチ要素の数はｍ個であり、
前記ｒ個の入出力スイッチ要素のうちのｉ番目の入出力スイッチ要素は、前記入力元および前記出力先のそれぞれと接続する帯域幅ｓiのｎi（ｎi≧１）本の入出力リンクと、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ’iのｎ’i（ｎ’i≧１）本の合計ｍ×ｓ’i本の接続リンクとを有し、前記ｎi本の入出力リンクのうちのｎ1,i（ｎ1,i≧１）本を合計した多重度ｄ1,i（ｄ1,i＞１）で前記ストリームを受信し、および前記ｎi本の入出力リンクのうちのｎ2,i（ｎ2,i≧１）本を合計した多重度ｄ2,i（ｄ1,i＞１）で前記受信したストリームを伝送し、
前記ｍ個の中間スイッチ要素は、前記ｉ番目の入出力スイッチ要素と接続する、合計Σ1≦i≦rｎ’i（ｎ’i≧１）本の接続リンク有し、Σ1≦i≦rｎ’i本の接続リンクの各々は、帯域幅ｓ’iのｎ’i本のリンクを有し、
式（１）乃至（４）
ｍ＝ｋ×Ｒ＞１（ｋ≧１、Ｒ≧１）
式（１）
前記ｉ番目の入出力スイッチ要素において、
ｎ1,i×ｓi≦ｋ×ｎ’i×ｓ’i、かつｄ1,i≦ｋ×ｄ’i
式（２）
ｊ番目の入出力スイッチ要素において、
ｎ2,i×ｓi≦Ｒ×ｎ’i×ｓ’i、かつｄ2,i≦Ｒ×ｄi
式（３）
出力ステージ全体において、
Σ1≦i≦r（ｎi×ｓi）＞Σ1≦i≦r（ｎ’i×ｓ’i）、かつΣ1≦i≦rｄi＞Σ1≦i≦rｄ’i
式（４）
を満たすことを特徴とする請求項７に記載の双方向伝送マルチキャストスイッチングシステム。
【請求項９】
前記複数の入出力スイッチ要素のそれぞれは、出力要求の有無によらずに前記第１のルーティング処理を行い、
前記第１のルーティング処理で設定された経路は削除されない
ことを特徴とする請求項８に記載の双方向伝送マルチキャストスイッチングシステム。
【請求項１０】
前記複数の入出力スイッチ要素の数はｒ個であり、前記複数の中間スイッチ要素の数はｍ個であり、
前記ｒ個の入出力スイッチ要素のうちのｉ番目の入出力スイッチ要素は、前記入力元および前記出力先のそれぞれと接続する帯域幅ｓiのｎi（ｎi≧１）本の入出力リンクと、前記ｍ個の中間スイッチ要素のそれぞれと接続する、帯域幅ｓ’iのｎ’i（ｎ’i≧１）本の合計ｍ×ｓ’i本の接続リンクとを有し、前記ｎi本の入出力リンクのうちのｎ1,i（ｎ1,i≧１）本を合計した多重度ｄ1,i（ｄ1,i＞１）で前記ストリームを受信し、および前記ｎi本の入出力リンクのうちのｎ2,i（ｎ2,i≧１）本を合計した多重度ｄ2,i（ｄ1,i＞１）で前記受信したストリームを伝送し、
前記ｍ個の中間スイッチ要素は、前記ｉ番目の入出力スイッチ要素と接続する、合計Σ1≦i≦rｎ’i（ｎ’i≧１）本の接続リンク有し、Σ1≦i≦rｎ’i本の接続リンクの各々は、帯域幅ｓ’iのｎ’i本のリンクを有し、
前記ｍ個の中間スイッチ要素の個数ｍは、
ｍ＝ｋ×Ｒ−ｗ＞１（ｋ＞１、Ｒ＞１、ｗ≧１）
式（５）
を満たし、式（６）乃至式（１０）
【数２２】
0006795172.tif 000090
【数２３】
0006795172.tif 000091
【数２４】
0006795172.tif 000092
【数２５】
0006795172.tif 000093
【数２６】
0006795172.tif 000094
によって、それぞれが、ｍi,j個の中間スイッチ要素を有する１個以上の部分集合Ｇi,jに分解され、前記複数のグループの数は、少なくともＲ−ＤR個であり、前記中間スイッチ要素の削減数ｗは、最大でＤR×ｋ個であり、
前記ｉ番目の入力スイッチ要素の入力ステージにおけるルーティング処理において、
少なくとも一つのｗi,j＞０となる部分集合Ｇi,jに属する全てのグループのｙ番目（ｗi,j＋Ｋj≧ｙ≧Ｋj）の中間スイッチ要素の集合Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ）∩Ｇi,j｜がＲi−１であり、全てのグループのｙ’番目 （ｋj＋Ｋj＞ｙ’＞ｗi,j＋Ｋj）がある場合、前記中間スイッチ要素の集合Ｄ（Ｉ，ｙ’）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ’）∩Ｇi,j｜は少なくともＲiであり、
その部分集合Ｇi,jにおいて、Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数がＲi−１であり、かつ、Ｇi,j内で同一の中間スイッチ要素の集合を使用するＤ（Ｉ，ｙ）∩Ｇi,jは、最大でＲi−１組であり、
ｊ番目の入出力スイッチ要素において、
ｎ1,i×ｓ1,i≦ｋ×ｎ’i×ｓ’i、かつｄ1,i≦ｋ×ｄ’i
式（１１）
を満たし、
前記ｊ番目の入出力スイッチ要素の出力側において、（ｎ’j×ｓ’j）＜ｍａｘ（ｎ’i×ｓ’i）（ｉ≠ｊ）の場合、
ｎ2,j×ｓ2,j≦（Ｒ−ＤR）×ｎ’j×ｓ’j、かつｄ2,i≦（Ｒ−ＤR）×ｄ’j
式（１２）
を満たし、（ｎ’j×ｓ’j）＝ｍａｘ（ｎ’i×ｓ’i）（ｉ≠ｊ）の場合、
ｎ2,j×ｓ2,j≦Ｒ×ｎ’j×ｓ’j、かつｄ2,i≦Ｒ×ｄ’j
式（１３）
出力ステージ全体において、
Σ1≦i≦r（ｎi×ｓi）＞Σ1≦i≦r（ｎ’i×ｓ’i）、かつΣ1≦i≦rｄi＞Σ1≦i≦rｄ’i
式（１４）
を満たすことを特徴とする請求項７に記載の双方向伝送マルチキャストスイッチングシステム。
【請求項１１】
前記複数の入出力スイッチ要素は、前記第１のルーティング処理の結果として選択される、前記複数の中間スイッチ要素のうち、その部分集合Ｇ（ｉ，ｊ）における少なくともＲi−１個のグループから伝送されるストリームを前記出力先に出力することによって、前記第２のルーティング処理を行い、既存のマルチキャスト配信をその部分集合Ｇ（ｉ，ｊ）における少なくともＲi個のグループの中間スイッチから構成される迂回路に再配置し、
前記第１のルーティング処理で設定された経路は削除されない
ことを特徴とする請求項１０に記載の双方向伝送マルチキャストスイッチングシステム。
【請求項１２】
前記ｒ個の入出力スイッチ要素のうちの１つもしくは複数は、前記ｉ番目の入出力スイッチ要素と接続された前記入出力リンクのうちのｎ’1本を、帯域幅ｓ’1で
【数２７】
0006795172.tif 000095
本と置き換えるか、または
前記ｍ個の中間スイッチ要素のうちの１つもしくは複数は、前記ｉ番目の入出力スイッチ要素と接続された前記接続リンクのうちのｎ’2本を、帯域幅ｓ’2で
【数２８】
0006795172.tif 000096
本と置き換える
ことを特徴とする請求項８乃至１１のいずれか一項に記載の双方向伝送マルチキャストスイッチングシステム。
【請求項１３】
前記複数の入出力スイッチ要素におけるｊ番目の入出力スイッチ要素は、
前記入力元から受信したストリームを、前記複数のグループのそれぞれに伝送し、かつ、前記出力先が同一の入出力スイッチに存在する場合には前記ストリームを前記出力先に直接出力するか、または
前記入力元から受信したストリームを、前記複数のグループのそれぞれに伝送し、および前記複数のグループのいずれかから伝送された前記ストリームを前記出力先に出力する
ことを前記第１のルーティング処理において選択することを特徴とする請求項８乃至１１のいずれか一項に記載の双方向伝送マルチキャストスイッチングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力元からのストリームをノンブロッキングで複数の出力先にマルチキャスト伝送するマルチキャストスイッチングシステムに関する。
【背景技術】
【０００２】
入力総数がＮ1本、出力総数がＮ2本（以後、Ｎ1×Ｎ2と称する）のＣｌｏｓ（Ｃｌｏｓは人の名前）型マルチキャストネットワークは、各々のステージが複数のスイッチ要素を有する３つのステージから構成される。従来技術のＣｌｏｓ型マルチキャストネットワークの構成の例を図１に示す。
【０００３】
図１に示されるように、Ｃｌｏｓ型マルチキャストネットワークは、入力ステージ、中間ステージ、および出力ステージを備える。
【０００４】
入力ステージには、ｎ1×ｍのスイッチ要素がｒ1個存在する（入力スイッチ要素１０１、１０２、および１０３）。入力スイッチ要素１０１、１０２、および１０３はそれぞれ、入力元からのｎ1本の入力リンク、および中間ステージへのｍ本の出力リンクを有する。
【０００５】
中間ステージには、ｒ1×ｒ2の中間スイッチ要素がｍ個存在する（中間スイッチ要素１１１、１１２、および１１３）。中間スイッチ要素１１１、１１２、および１１３はそれぞれ、入力ステージからのｒ1本の入力リンク、および出力ステージへのｒ2本の出力リンクを有する。
【０００６】
出力ステージには、ｍ×ｒ2の出力スイッチ要素がｒ2個存在する（出力スイッチ要素１２１、１２２、および１２３）。出力スイッチ要素１２１、１２２、および１２３はそれぞれ、中間ステージからのｍ本の入力リンク、および出力先へのｎ2本の出力リンクを有する。総入力リンク数Ｎ1は、ｎ1×ｒ1本であり、総出力リンク数Ｎ2は、ｎ2×ｒ2本である。
【０００７】
このようなネットワークにおいて、各スイッチ要素については「ノンブロッキングなマルチキャスト」が可能であると仮定する。ここで、「ノンブロッキングなマルチキャストが可能」とは、任意の入力元から出力先への任意のマルチキャスト接続要求に対して、ネットワークを通じてストリームを伝送する接続パスを提供し、かつ、他の既存の接続を妨害または再配置することなく要求を満たすことが常に可能な状態を意味する。
【０００８】
「任意の接続要求」とは、出力ステージにおいて、出力スイッチ要素および出力リンクが存在し、入力ステージへの既存のストリームまたは新たに伝送されたストリームに対して、出力ステージにおける出力スイッチ要素からの新たな出力を行うための任意の要求である。言い換えると、出力ステージにおける任意の出力スイッチ要素および出力リンクから新たな出力を行うための要求である。これには、新たに伝送されたストリームを利用するだけでなく、既存のマルチキャスト接続に対して、新規の出力先を追加する操作も含まれる。
【０００９】
ストリームをネットワーク上で伝送する場合、ネットワーク上で経路の再配置が行われると、新旧の経路の差に起因して、受信側でデータの損失、および送出順序が逆転するなどの事象が生じる可能性がある。従って、任意のマルチキャスト接続要求によって、既存のマルチキャスト接続に影響を与えないことが、個々のスイッチ要素だけでなくネットワーク全体で満たすべき重要な要件となっている。
【００１０】
任意のマルチキャストは、１対多のストリーム伝送である。３ステージのＣｌｏｓ型マルチキャストネットワークでは、個々のマルチキャストは、入力ステージ、中間ステージ、および出力ステージのそれぞれにおいて分岐を有することのできる「木構造」で表される。図１では、入力ステージの１０３への入力ストリームが、中間ステージ１２０における中間スイッチ要素１１２、次いで出力ステージ１３０における出力スイッチ要素１２１および１２２を経由して、３本の出力にマルチキャストされていることを示している。
【００１１】
従って、「ノンブロッキングなマルチキャストが可能」とは、「任意の接続要求」に対して、既存の木構造の分岐個所で分岐数を減ずることなく、新たな分岐あるいは木を追加することによって、「任意の接続要求」を満たすことが可能な状態を意味する。このような性質を有するネットワークシステムを、本明細書では「ノンブロッキングなマルチキャストシステム」と称することとする。
【００１２】
ストリームをネットワーク上で伝送する場合に、既存のマルチキャスト接続に影響を与えないことが新規の接続要求を受け入れる際に重要な要件であることを述べた。しかしながら、既存のマルチキャスト接続を再配置する可能性およびコストが非常に小さい場合には、そのような再配置を許容しつつ、任意のマルチキャストに対するノンブロッキング性を担保することが重要である場合もある。このようなノンブロッキング性は、「再配置可能なノンブロッキング性（ＲＮＢ：Rearrangeable Non-blocking）」と称される。また、上述したノンブロッキング性については、「広義のノンブロッキング性（ＷＳＮＢ：Wide-sense Non-blocking）」と称される。以下、本明細書では、ＷＳＮＢおよびＲＮＢを、「ノンブロッキングなマルチキャストシステム」総称することとする。
【００１３】
図１のＣｌｏｓ型ネットワークは、もともとはクロスバースイッチを使用した回路接続型のネットワークを対象としており、一つの通信が一つのリンクを占有する前提である。特許文献１および特許文献２は、そのような回線交換型のネットワークに対して中間ステージのスイッチ数ｍが特定の値をとる場合に、その３ステージＣｌｏｓ型ネットワークが、ノンブロッキングであるという点で、マルチキャスト能力を有しているということを示している。
【００１４】
隣接するステージ間の任意のスイッチに対して、少なくとも一つのリンクが存在するネットワーク形態であるＣｌｏｓ型ネットワークを、近年のパケット交換を基にしたパケット交換スイッチを使用して実現することも可能である。このようなパケット交換スイッチでは、スイッチの各リンクにおいて、そのリンクの最大帯域幅を上限として、独立した入力元からの複数のストリームを同時にサポートすることができる。一般的に、ｎ×ｎのパケット交換型マルチキャストスイッチは、ｎ個の入力リンクおよびｎ個の出力リンクを有する。各リンクは、リンクの帯域幅を上限とするｄ個の独立したストリームを伝送し、任意の入力リンクを任意の出力リンクに接続することができる。このようなスイッチは通常のｎｄ×ｎｄのマルチキャストスイッチとして機能する。
【００１５】
例えば、デジタル映像伝送信号をＩＰネットワーク上で伝送する規格として、ＳＭＰＴＥ２０２２−６が存在する。この規格に従って、１．５Ｇｂｐｓの帯域幅を有するデジタル映像信号をＩＰスイッチ上で伝送する場合、各リンクが１０Ｇｂｐｓの帯域幅を有するｎ×ｎのパケット交換型マルチキャストスイッチを使用することによって、リンクにおける多重度を６として各リンクで９Ｇｂｐｓまで伝送することができる。これは、各リンクが１．５Ｇｂｐｓの帯域幅を有する６ｎ×６ｎのマルチキャストスイッチと等価である。
【００１６】
ここで、それぞれの入力ストリームが異なる帯域幅を有してもよい。例えば、同一の１０Ｇｂｐｓの帯域幅を有する各リンクにおいて、１．５Ｇｂｐｓの入力ストリームを４本、５００Ｍｂｐｓの入力ストリームを６本とし、多重度を１０とすることによって、１０ｎ×１０ｎのマルチキャストスイッチと同等にすることができる。
【００１７】
特許文献３では、そのようなスイッチ要素をリンクの多重度ｄのマルチソーススイッチと称している。特許文献３は、図２に示されるＣｌｏｓ型ネットワークでマルチソーススイッチを使用し、全てのリンクの多重度が同一で、かつ、ノンブロッキングなマルチキャストが可能な条件下で、中間ステージのスイッチ数を決定するアルゴリズムを示している。また、特許文献３は、配信時に入力ステージ、中間ステージ、および出力ステージのそれぞれを操作し、経路を設定するルーティングアルゴリズムを開示している。ここで、図２では、ｄ1は入力ステージの入力リンクの多重度、ｄ2は中間ステージの入力リンクの多重度、ｄ3は出力ステージの入力リンクの多重度である。
【００１８】
また、図１に示したＮ1×Ｎ2の３ステージネットワークにおいて、入力ステージのスイッチ要素、および出力ステージのスイッチ要素を一つのスイッチ要素に収容して入出力ステージとする構成が図３に示される。図３に示す構成は、入出力ステージおよび中間ステージを有する。入出力ステージには、入出力スイッチ要素３１１、３１２、および３１３が存在し、中間ステージには、中間スイッチ要素３０１、３０２、および３０３が存在する。入出力スイッチ要素３１１、３１２、３１３、および中間スイッチ３０１、３０２、３０３はそれぞれ、双方向のリンクを有し、中間ステージでストリームを折り返す（畳み込み）。中間スイッチ要素３０１、３０２、および３０３は、図１に示された中間スイッチ要素１１１、１１２、および１１３にそれぞれ相当する。入出力スイッチ要素３１１は、図１に示された入力スイッチ要素１０１および出力スイッチ要素１２１を統合したスイッチ要素である。同様に、入出力スイッチ要素３１２は、入力スイッチ要素１０２および出力スイッチ要素１２２を統合し、入出力スイッチ要素３１３は、入力スイッチ要素１０３および出力スイッチ要素１２３を統合したものである。
【００１９】
図３のネットワークにおいても、基本的には、入力元からのストリームは、入出力ステージ、中間ステージ、および入出力ステージの順でスイッチングされるため、図３は論理的には３ステージとみなすことができる。
【００２０】
実際に使用する入出力リンクは、物理的にスイッチ要素に備えられたリンクを全て使用する必要はなく、また、双方向のリンクの片方向のみを使用することも可能である。よって、図３に示す構成では、入出力ステージのスイッチ要素数ｒはｒ＝ｍａｘ（ｒ1，ｒ2）であり、各々の入出力スイッチ要素における入出力リンク数ｎはｎ＝ｍａｘ（ｎ1，ｎ2）である。ここで、ｍａｘ（ａ，ｂ）は二つの整数ａおよびｂの最大値である。このときｎおよびｒに対して、Ｎ1およびＮ2の上限はＮ＝ｍａｘ（Ｎ1，Ｎ2）＝ｎ×ｒとなる。
【００２１】
図３に示す構造に対してパケット交換スイッチを使用し、マルチソースを実現することも可能である。この場合、スイッチ要素間のそれぞれのリンクと入出力ステージの入出力リンクにおいて、複数個のストリームを伝送することができる。
【００２２】
図３に示すＣｌｏｓ型ネットワークでの伝送では、ストリームの伝送を同一の入出力ステージにおけるスイッチ要素で行う。例えば、入出力スイッチ要素３１２に入力されたストリームが中間スイッチ要素３０１に伝送され、再び入出力スイッチ要素３１２に戻って出力されるような経路を使用してもよい。
【００２３】
しかしながら、図３に示すスイッチ要素として近年一般的なイーサネット（登録商標）のスイッチを使用した場合には、スイッチの動作として同一リンクへのストリームを戻すループバック出力が認められない場合がある。そのような場合は。図３の入出力スイッチ要素３１２に示されるように、中間スイッチ要素へのストリームの伝送をバイパスして、入出力スイッチ要素３１２で入力されたストリームを出力先に直接伝送することも可能である。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特表２００７−５０４７７２号公報
【特許文献２】特表２００７−５３２０３７号公報
【特許文献３】特許４３４１９８２号
【非特許文献】
【００２５】
【非特許文献１】G. M. Masson and B. W. Jordan, “Generalized multi-stage connection networks,” Networks, vol. 2, pp.191-209, 1972
【非特許文献２】D. G. Kirkpatrick, M. Klawe, and N. Pippenger. “Some Graph-Colouring Theorems with Applications to Generalized Connection Networks,” SIAM Journal on Algebraic and Discrete Methods 6, no. 4, pp. 576-582, 1985
【発明の概要】
【発明が解決しようとする課題】
【００２６】
前述のように、スイッチ要素が有する各リンクが、独立した入力元からの複数のストリームを同時に入出力することができるタイプのスイッチ要素を、特許文献３で示された発明と同様に「マルチソーススイッチ」と称することにする。一般的に、ｎ×ｎのパケット交換型マルチキャストスイッチは、各リンクにおいてリンクの帯域幅を上限とするｄ個の独立したストリームを伝送し、任意のストリームを任意の出力先に出力することができる。特許文献３に示された発明と同様に、このようなスイッチを単純にｎ×ｎのｄソースマルチキャストスイッチと称することにする。このようなスイッチは通常のｎｄ×ｎｄのマルチキャストスイッチとして機能する。このようなスイッチの実装例は、パケット交換スイッチである。
【００２７】
しかしながら、特許文献１および特許文献２で示された従来技術は、リンクが一つのストリームによって占有されるＣｌｏｓ型ネットワークを前提としており、マルチソースでマルチキャスト可能なＣｌｏｓ型のネットワークのノンブロッキング条件下でのミドルステージスイッチ数を最小化する技術が示されておらず、文献でのポート数ｎに相当するスイッチへの入力数ｎｄが大きくなるとともに高コストなシステムとなっていた。
【００２８】
特許文献３では、マルチソースでのノンブロッキングなマルチキャストを可能とするのに必要となるスイッチの個数を導出するアルゴリズムが開示されている。しかしながら、より少ないスイッチ数で実現する解がある可能性は否定されていない。また、ルーティングアルゴリズムによって、全ステージの複数のスイッチを操作するため、経路の設定および削除において、最悪値では経路の切り替え時間がネットワークの段数に応じて必要になるという課題があった。
【００２９】
１対１のユニキャスト通信においては、ＲＮＢ条件を満たすネットワークのほうがネットワークのサイズを小さくできることが知られている。非特許文献１および非特許文献２には、マルチキャスト通信におけるＲＮＢ条件が述べられているが、公知のＷＳＮＢ条件を使用した方がネットワークのサイズを小さくすることができ、再配置のリスクを考慮すると、ＲＮＢ条件を使用する利点がなかった。
【００３０】
そのため、マルチソースでノンブロッキングなマルチキャストを、より少ないスイッチ数で実現することができ、かつ、高速な経路の追加・削除・切り替えが可能なシステムが求められている。
【課題を解決するための手段】
【００３１】
本発明は、マルチソースのスイッチ要素を３ステージのＣｌｏｓ型ネットワークにおいて使用した、ノンブロッキングなマルチキャストスイッチングシステムを提供する。本発明のＮ1×Ｎ2マルチキャストシステムは、Ｎ1個の入力元からのストリームをＮ2個の出力先へ出力するものであり、各スイッチ要素間において、２以上の独立したストリームを伝送する。従来のＣｌｏｓ型ネットワークとの違いは、図２に示すように、ステージ間の各スイッチ要素間において、多重度がｄの伝送を行うこと、すなわち、ｄ本の論理的なリンクが存在することに相当するという点である。
【００３２】
本発明では、中間ステージにおけるｍ個（ｍ＞１）のスイッチ要素を、ｋ個（ｋ≧１）の中間スイッチ要素数からなるＲ個（Ｒ≧１）の複数グループに分割する。入力ステージにおける入力スイッチ要素から中間ステージにおける全てのグループに対して、個々のストリームを、グループごとに１個の中間スイッチ要素に伝送する。出力ステージでは、出力スイッチ要素によって要求された個々のマルチキャスト出力要求に対し、全ての中間ステージのグループの中から少なくとも１つのグループを伝送元として選択することによって、マルチキャスト伝送を実現する。
【００３３】
このとき、入力ステージでの経路設定を中間ステージおよび出力側ステージでの経路設定処理と分離し、その経路設定方式がノンブロッキングなマルチキャスト配信を可能とする条件を満たすための条件式を提示する。
【００３４】
また、本発明では、非特許文献１および非特許文献２で開示された技術と比較して、公知のＷＳＮＢ条件よりもネットワークのサイズを小さくすることができるＲＮＢ条件を満たすネットワークの構成方式を示す。後述するように、本発明におけるＷＳＮＢ条件とは、各入力ストリームがＲ通りの迂回路としての中間スイッチ要素に配信され、かつ、出力ステージにおける出力スイッチ要素からの出力が以下で示す式（２）を満たす場合、必ず迂回路を経由した配信が新規に可能になることに基づいている。
【００３５】
本発明におけるＲＮＢ条件は、Ｒ＞１の場合、各入力ストリームが少なくともＲ−１通りの迂回路としての中間スイッチ要素に配信され、かつ、出力ステージにおける出力スイッチ要素からの出力が以下で示す式（２）を満たす場合、必要に応じて既存配信を再配置することより、必ず迂回路を経由した配信を新規に可能にするための配信方法を提示する。
【発明の効果】
【００３６】
本発明は、マルチソースかつマルチキャスト可能なＣｌｏｓ型ネットワークにおいて、本発明による経路設定方式、およびその経路設定方式がノンブロッキングなマルチキャストを実現する条件を満たすための条件式の解に従って、従来知られていた特許文献３で示された方式よりもスイッチ数を削減することができる。
【００３７】
一実施形態では、リンク数が９６×９６のスイッチ要素を利用して、その２倍の１９２×１９２のリンク数のネットワークを構築する場合を想定する。各リンクの多重度を２として、特許文献３に開示された数式により計算を行うと、ｎ＝４、ｒ＝４８、ｍ＝２０がスイッチ数の最小の解である。すなわち、入力ステージにおけるスイッチ要素は４×２０のスイッチが４８個、中間ステージにおけるスイッチ要素は４８×４８のスイッチが２０個、出力ステージにおけるスイッチ要素は２０×４のスイッチが４８個である。
【００３８】
従って、９６×９６のスイッチ要素を使用すると、スイッチ要素を４個ずつ、計８個を９６×９６のスイッチ１個を使用することによって、入力ステージおよび出力ステージを構成することができる（入力ストリーム数４×４＋２０×４＝９６、出力ストリーム数２０×４＋４×４＝９６）。よって、１２個の９６×９６スイッチ要素を使用することによって、全ての入力ステージおよび出力ステージを構成することができる。また、２個のスイッチ要素を使用する代わりに、１個の９６×９６のスイッチを使用することによって、中間ステージを構成することができる（入力ストリーム数４８×２＝９６、出力ストリーム数４８×２＝９６）。よって、１０個の９６×９６スイッチ要素を使用することによって、中間ステージを構成することができる。合計のスイッチ数は２２個である。
【００３９】
一方、本発明においては、後述の実施例で述べるように、ｋ＝Ｒ＝２、ｎ＝３２、ｒ＝６、ｍ＝４がスイッチ数最小のＷＳＮＢ条件を満たす解になる。よって、１０個のスイッチ要素数を使用することによって、１９２×１９２のスイッチ要素数に相当するマルチキャストスイッチングシステムを構成することができる。さらに、この解に基づいて、中間ステージにおける中間スイッチ要素の数を削減して、ｍ＝３やｍ＝２の場合においてもＲＮＢ条件を満たす解を生成することができる。９６×９６のスイッチ要素を使用した場合、ｍ＝３、ｒ＝５で、１５２×１９０、ｍ＝２、ｒ＝４で１２０×１９２のスイッチ要素数に相当するマルチキャストスイッチングシステムを構成することができる。
【００４０】
同様に比較を行うと、同一の９６×９６のスイッチ要素を使用して、ｋ＜６、Ｒ＜６で特許文献３に開示された技術によって導出された解よりもスイッチ要素数の少ない解が存在し、最大で４８０×４８０のリンク数を有するマルチキャストスイッチングシステムを、従来技術より少ないスイッチ要素数で構成することができる。これらの解に基づいて、さらにスイッチ要素数を減じたＲＮＢ条件を満たす解を使用することで、より少ないスイッチ要素数で実現することが可能である。
【００４１】
従来方式では、既存の経路が存在しない場合、入力ステージを含む全てのステージに対して経路設定操作がマルチキャスト要求の受理後に動的に行われる。
【００４２】
一方、本発明においては、入力ステージでの経路設定を中間ステージおよび出力ステージでの経路設定処理と分離し、入力ステージにおける経路設定を事前に行うことが可能である。よって、従来方式の経路設定での経路追加と削除の場合に比べ、操作するスイッチ数が少なく、高速な経路切り替えが可能になる。
【図面の簡単な説明】
【００４３】
【図１】従来技術に従った３ステージのＣｌｏｓ型ネットワーク構成の例を示す図である。
【図２】図１で示されたそれぞれのスイッチ要素を、各リンクにおいて複数の独立したストリームを伝送することができるマルチソーススイッチを使用して構成したＣｌｏｓ型ネットワーク構成の例を示す図である。
【図３】図１で示された３ステージのＣｌｏｓ型ネットワークを、双方向リンクを有するスイッチ要素で構成したネットワーク構成の例を示す図である。
【図４】本発明の一実施形態に従った、３ステージのＣｌｏｓ型ネットワーク構成の例を示す図である。
【図５】図４に示されたＣｌｏｓ型ネットワーク構成を、双方向リンクを有するスイッチ要素を使用して構成したネットワーク構成の例を示す図である。
【図６】本発明の一実施形態に従った、新規および既存のマルチキャスト要求に対するルーティング処理を示すフローチャートである。
【図７】本発明の一実施形態に従った、マルチキャストの経路を削除する処理を示すフローチャートである。
【図８】本発明の一実施形態に従って導出された解に基づいて構成された、９６ポートの１０ギガビットイーサネットスイッチを使用して構成したネットワーク構成の例を示す図である。
【図９】本発明の一実施形態に従って導出された解に基づいて構成された、９６ポートの１０ギガビットイーサネットスイッチを使用して構成したネットワーク構成の別の例を示す図である。
【図１０】本発明の別の実施形態に従った、新規および既存のマルチキャスト要求に対するルーティング処理を示すフローチャートである。
【発明を実施するための形態】
【００４４】
以下、本発明の実施形態について説明する。本明細書において、用語「ストリーム」は、入力元から入力ステージに伝送され、出力先に出力される音声、映像、信号およびデータなどを含む。用語「スイッチ要素」は、内部をマトリクス構造やメモリ構造とする、入力ポートから出力ポートにストリームを出力する物理的装置である。用語「リンク」は、各ステージ間のスイッチ要素をつなぎ、かつスイッチ要素の入力ポートおよび出力ポートに間に接続される物理的な伝送路である。
【００４５】
本発明の実施形態に係るシステムは、マルチソースのスイッチ要素を３ステージのＣｌｏｓ型ネットワークにおいて使用した、ノンブロッキングなマルチキャストスイッチングシステムである。本発明に係るＮ1×Ｎ2マルチキャストスイッチングシステムは、Ｎ1個の入力元からのストリームをＮ2個の出力先へ出力するものであり、各スイッチ要素間のリンクにおいて、１以上の独立したストリームを伝送する。従来のＣｌｏｓ型ネットワークとの違いは、スイッチ間のリンクでの多重度がｄ、すなわち、論理的にｄ本のリンクがあることに相当するという点である。
【００４６】
図２は、図１のそれぞれのスイッチ要素を、各リンクにおいて複数の独立したストリームを伝送することができるマルチソーススイッチを使用して実現したＣｌｏｓ型ネットワークを示す。
【００４７】
入力ステージには、入力スイッチ要素２０１、２０２、および２０３がｒ1個存在する。入力スイッチ要素２０１、２０２、および２０３はそれぞれ、入力元からのｎ1本の入力リンク、およびｒ1本の中間スイッチ要素へのｍ本の出力リンクを有する。入力リンクはそれぞれ、多重度ｄ1を有し、出力リンクはそれぞれ、多重度ｄ2を有する。つまり、入力スイッチ要素は、（ｄ1×ｎ1）×（ｄ2×ｍ）のスイッチ要素である。
【００４８】
中間ステージには、中間スイッチ要素２１１、２１２、および２１３がｍ個存在する。中間スイッチ要素２１１、２１２、および２１３はそれぞれ、ｍ本の入力スイッチ要素からのｒ1本の入力リンク、およびｍ本の出力スイッチ要素へのｒ2本の出力リンクを有する。入力リンクはそれぞれ、多重度ｄ2を有し、出力リンクはそれぞれ、多重度ｄ3を有する。つまり、中間スイッチ要素２１１、２１２、および２１３は、（ｄ2×ｒ1）×（ｄ3×ｒ2）のスイッチ要素である。
【００４９】
出力ステージには、出力スイッチ要素２２１、２２２、および２２３がｒ2個存在する。出力スイッチ要素２２１、２２２、および２２３はそれぞれ、ｒ2本の中間スイッチ要素からのｍ本の入力リンク、および出力先へのｎ4本の出力リンクを有する。入力リンクはそれぞれ、多重度ｄ3を有し、出力リンクはそれぞれ、多重度ｄ4を有する。つまり、出力スイッチ要素２２１、２２２、および２２３は、（ｄ3×ｍ）×（ｄ4×ｎ4）のスイッチである。従って、ネットワーク全体では、（ｄ1×ｎ1×ｒ1）×（ｄ4×ｎ4×ｒ2）の構成を有する。
【００５０】
入力スイッチ要素２０１、２０２、および２０３において、ストリームの多重度ｄ1を構成する複数のストリームは、入力リンクｎ1本にまたがって入力される。このとき、それぞれのストリームの帯域幅が同一でなくてもよい。よって、個々の入力リンクに存在する物理的な帯域幅の上限をｓ1とし、入力の多重度はｄ1を上限としてｎ1本のリンクによって受信し、入力されるストリームの総帯域幅がｎ1×ｓ1であるとする。
【００５１】
同様に、出力スイッチ要素２２１、２２２、および２２３において、出力の多重度ｄ4を構成する複数のストリームは、出力リンクｎ4本にまたがって出力される。出力リンクの物理的な帯域幅の上限をｓ4とし、出力の多重度はｄ4を上限としてｎ4本のリンクによって送信し、出力するストリームの総帯域幅がｎ4×ｓ4であるとする。
【００５２】
さらに、入力スイッチ要素２０１、２０２、２０３、および出力スイッチ要素２２１、２２２、２２３は、それぞれの入力リンクと出力リンクに固有の多重度と総帯域幅を有してもよい。また、入力スイッチ要素２０１、２０２、２０３、および出力スイッチ要素２２１、２２２、２２３のそれぞれが、中間スイッチ要素２１１、２１２、および２１２のそれぞれとの間に固有の多重度と総帯域幅を有してもよい。
【００５３】
図４は、本発明の一実施形態に従った、３ステージのＣｌｏｓ型ネットワーク構成の例を示している。
【００５４】
入力スイッチ要素４０１、４０２、および４０３はそれぞれ、入力ステージにおけるｒ1個のスイッチを表している。
【００５５】
本発明では、後述するように、中間ステージにおいて、ｍ個（ｍ＞１）の中間スイッチ要素を、ｋ個（ｋ≧１）のスイッチ要素からなるＲ個（Ｒ≧１）の複数グループに分割する。グループ４１０はｋ個のスイッチを含む、中間ステージにおける１番目のグループである。グループ４２０は同様にｋ個のスイッチを含む、中間ステージにおけるＲ番目のグループである。中間スイッチ要素４１１は、グループ４１０の１番目のスイッチ要素であり、中間スイッチ要素４１２は、グループ４１０のｋ番目のスイッチ要素である。中間スイッチ要素４２１は、グループ４２０の１番目のスイッチ要素であり、中間スイッチ要素４２２は、グループ４２０のｋ番目のスイッチ要素である。
【００５６】
出力スイッチ要素４３１、４３２、および４３３はそれぞれ、出力ステージにおけるｒ2個のスイッチ要素を表している。
【００５７】
入力リンク４４１は、入力ステージにおける１番目の入力スイッチ要素４０１の入力リンクである。出力リンク４５１は、入力スイッチ要素４０１の出力リンクであるとともに、中間スイッチ要素４１１の入力リンクでもある。入力リンク４４２は、ｒ1番目の入力スイッチ要素４０３の入力リンクである。出力リンク４５２は、入力スイッチ要素４０３の出力リンクであるとともに、中間スイッチ要素４２２の入力リンクでもある。
【００５８】
出力リンク４７１は、出力ステージにおける１番目の出力スイッチ要素４３１の出力リンクである。入力リンク４６１は、出力スイッチ要素４３１の入力リンクであるとともに、中間スイッチ要素４１１の出力リンクでもある。出力リンク４７２は、出力ステージにおけるｒ2番目の出力スイッチ要素４３３の出力リンクである。入力リンク４６２は、出力スイッチ要素４３３の入力リンクであるとともに、中間スイッチ要素４２２の出力リンクでもある。
【００５９】
以後、本発明の実施形態として、入力ステージにおけるｉ番目（ｒ1≧ｉ≧１）の入力スイッチ要素は、図４に示す入力リンク４４１および４４２に相当する入力リンクとして、リンク数ｎ1,i（ｎ1,i≧１）本で総帯域幅ｎ1,i×ｓ1,iの多重度ｄ1,i（ｄ1,i＞１）を上限として、入力元からストリームを受信する。また、ｉ番目の入力スイッチ要素は、図４に示す出力リンク４５１および４５２に相当する出力リンクとして、リンク数ｎ2,i（ｎ2,i≧１）本で総帯域幅ｎ2,i×ｓ2,iの多重度ｄ2,i（ｄ2,i＞１）を上限として、ストリームをそれぞれの中間スイッチ要素に伝送する。
【００６０】
同様に、出力ステージにおけるｊ番目（ｒ2≧ｊ≧１）の出力スイッチ要素は、出力リンクとして、リンク数ｎ4,j（ｎ4,j≧１）本で総帯域幅ｎ4,j×ｓ4,jの多重度ｄ4,j（ｄ4,j＞１）を上限として、ストリームを出力先に出力する。また、ｊ番目の出力スイッチ要素は、入力リンクとして、リンク数ｎ3,j（ｎ3,j≧１）本で総帯域幅ｎ3,j×ｓ3,jの多重度ｄ3,j（ｄ3,j＞１）を上限として、ストリームをそれぞれの中間スイッチ要素から受信する。ここでの出力リンクは、図４に示す出力リンク４７１および４７２に相当し、入力リンクは図４に示す入力リンク４６１および４６２に相当する。
【００６１】
従って、ネットワーク全体の入力ストリーム数Ｎ1は、全ての入力ステージにおけるｒ1個の入力スイッチ要素への入力ストリーム数の総和、すなわち、
【００６２】
【数１】
0006795172.tif 000002
【００６３】
である。また、ネットワーク全体の出力ストリーム数Ｎ2は、全ての出力ステージにおけるｒ2個の出力スイッチ要素からの出力ストリーム数の総和、すなわち、
【００６４】
【数２】
0006795172.tif 000003
【００６５】
である。
【００６６】
説明を簡単にするために、各々の入力スイッチ要素のそれぞれの入力リンクの帯域幅は等しいとした。また、各々の出力スイッチ要素のそれぞれの出力リンクの帯域幅は等しいとした。さらに、送信元スイッチと受信側スイッチを等しくするリンクのそれぞれの帯域幅は等しいとした。後述の実施例で示すように、帯域幅ｓのリンクｎ（ｎ≧１）本を、帯域幅ｓ’（ｓ≠ｓ’）のリンクｎ’（ｎ×ｓ／ｓ’）本で置き換えることはリンクの実装方法により可能である。この置換え操作をｓ’での正規化と呼ぶこととする。
【００６７】
ここで、ストリームの要求する帯域幅およびリンクの帯域幅によっては、正規化により、多重度が変化してしまう可能性がある。例えばｓ＝６（Ｇｂｐｓ）、ｎ＝１、ｓ’＝２（Ｇｂｐｓ）で、一つのストリームが要求する帯域幅が１．５Ｇｂｐｓとすると、ｓに対しての多重度は
【００６８】
【数３】
0006795172.tif 000004
【００６９】
であり、ｓ’に対して正規化した多重度は
【００７０】
【数４】
0006795172.tif 000005
【００７１】
となって、多重度を減じてしまう。従って、以後、正規化の実施には、多重度に関する要求を考慮して行う。
【００７２】
本発明では、ｍ個（ｍ＞１）の中間スイッチ要素を、ｋ個（ｋ≧１）のスイッチ要素数からなるＲ個（Ｒ≧１）の複数グループに分割する。そして、個々のストリームを、入力スイッチ要素のそれぞれから全てのグループに対して、グループごとに１個の中間スイッチ要素に伝送する。出力ステージでは、出力スイッチ要素で要求された個々のマルチキャスト出力要求に対し、全ての中間ステージのグループの中から少なくとも１つのグループを伝送元として選択することによって、マルチキャスト配信を実現する。
【００７３】
このようにして、入力ステージからは、中間ステージの全てのグループにおける一つの中間スイッチ要素にストリームが伝送され、中間ステージおよび／または出力ステージにおいて、どのグループからストリームを伝送／受信するかを選択する。よって、入力ステージでの経路設定を中間ステージおよび出力ステージでの経路設定処理と分離することができる。
【００７４】
このとき、入力ステージにおけるｉ番目の入力スイッチ要素では、入力リンクの総帯域幅（ｎ1,i×ｓ1,i）が、中間ステージのそれぞれのグループ内の全ての中間スイッチ要素へのリンクの合計帯域幅（ｋ×ｎ2,i×ｓ2,i）に等しいか、またはより小さくする。それによって、個々の入力スイッチ要素への全てのストリームが、全てのグループに完全に配信可能であることを保証する。ここで、多重度については、出力ストリームが入力ストリームを上回ることはないから、ｄ1,i≦ｋ×ｄ2,iである。
【００７５】
また、出力ステージにおけるｊ番目のスイッチ要素では、出力リンクの総帯域幅（ｎ4,j×ｓ4,j）が、中間ステージのそれぞれのグループにおける一つの中間スイッチ要素からのリンクの帯域幅のグループ数倍（Ｒ×ｎ3,j×ｓ3,j）に等しいか、または少なくする。それによって、中間スイッチ要素に伝送される全てのストリームを出力可能であることを保証する。ここで、多重度については、出力ストリームが入力ストリームを上回ることはないから、ｄ4,j≦Ｒ×ｄ3,jである。
【００７６】
中間ステージにおけるグループ内の一つの中間スイッチ要素は、全ストリームの部分集合を入力ステージから受信している。このような構成において、ある出力スイッチ要素の全ストリームが特定の部分集合に集中した場合でも、他の（Ｒ−１）個のグループに必要な帯域幅と多重度を確保できるだけの同一のストリームが伝送されているため、他のマルチキャスト経路を変更することなく、ノンブロッキングなマルチキャストが可能になる。ある出力スイッチ要素の全ストリームの１／Ｒを一つのグループが担当し、かつ、それがそのグループにおける一つ中間スイッチ要素に集中したとした場合でも、全てのＲ個のグループから一つずつ中間スイッチ要素を使用するこができ、これによって全出力を賄うことができる。
【００７７】
以上により、本発明に従ったネットワーク構成は、中間ステージがｍ＝（Ｒ×ｋ）個のスイッチ要素を有することを条件に、以下の不等式を満たす解を有する。
入力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ1,i×ｓ1,i≦ｋ×ｎ2,i×ｓ2,i、かつｄ1,i≦ｋ×ｄ2,i
式（１）
出力ステージにおけるｊ番目の出力スイッチ要素では、
ｎ4,j×ｓ4,j≦Ｒ×ｎ3,j×ｓ3,j、かつｄ4,j≦Ｒ×ｄ3,j
式（２）
【００７８】
このとき、ネットワーク全体の出力ストリーム数は、すべての出力スイッチ要素ｒ2個の出力ストリーム数の総和、すなわち、多重度の合計が
【００７９】
【数５】
0006795172.tif 000006
【００８０】
で総帯域幅は
【００８１】
【数６】
0006795172.tif 000007
【００８２】
である。一方、中間ステージ全体の出力ストリーム数は、その中間スイッチ要素から出力ステージにおける全ての出力スイッチ要素に伝送されるストリーム数を合計したものであるから、多重度
【００８３】
【数７】
0006795172.tif 000008
【００８４】
で総帯域幅は
【００８５】
【数８】
0006795172.tif 000009
【００８６】
である。ネットワーク全体の出力ストリーム数が、一つのスイッチ要素の出力ストリーム数を上回らなければ、ネットワークの構築の意義はないため、以下の条件を解が満たすべき条件に加える。
【００８７】
出力ステージ全体において、
【００８８】
【数９】
0006795172.tif 000010
【００８９】
実装に際しては、入力スイッチ要素で利用することができるリンク数、中間スイッチ要素で利用することができるリンク数、出力スイッチ要素で利用することができるリンク数を制約条件に加えて解を導出する。
【００９０】
入力ステージにおけるｉ番目の入力スイッチ要素で入力リンク数の上限をｐ1,i本とし出力リンク数の上限をｐ2,i本とする。個々の中間スイッチ要素では、帯域幅ｘ（ｘ∈｛全てのｓ2,iの中で相異なる値の集合｝）の入力リンク数の上限をｐ3,x本とし、帯域幅ｙ（ｙ∈｛全てのｓ3,jの中で相異なる値の集合｝）の出力リンク数の上限をｐ4,y本とする。出力ステージにおけるｊ番目の出力スイッチ要素の入力リンク数の上限をｐ5,j本とし、出力リンク数の上限をｐ6,j本とする。これまで説明した構成から、以下のような制約条件が追加される。
入力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ1,i≦ｐ1,i
式（４）
入力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ2,i×Ｒ×ｋ≦ｐ2,i
式（５）
中間スイッチ要素の全ての帯域幅ｘのリンクにおいて、
【００９１】
【数１０】
0006795172.tif 000011
【００９２】
中間スイッチ要素の全ての帯域幅ｙのリンクにおいて、
【００９３】
【数１１】
0006795172.tif 000012
【００９４】
出力ステージにおけるｊ番目の出力スイッチ要素では、
ｎ3,j×Ｒ×ｋ≦ｐ5,j
式（８）
出力ステージにおけるｊ番目の出力スイッチ要素では、
ｎ4,j≦ｐ6,j
式（９）
【００９５】
前述のように、スイッチ要素の実装方法によっては、帯域幅ｓのリンクｎ（ｎ≧１）本を帯域幅ｓ’（ｓ≠ｓ’）のリンク
【００９６】
【数１２】
0006795172.tif 000013
【００９７】
本で置き換えることが容易である。このとき、ネットワークがノンブロッキングであるために、入力ステージの入力リンクを、多重度を増やさない範囲で置き換える。入力ステージと中間ステージとの間のリンクと、中間ステージと出力ステージとの間のリンクを、多重度を減らさない範囲で置き換える。出力ステージの出力リンクを、多重度を増やさない範囲で置き換える。
【００９８】
この範囲において、入力ステージの入力リンクを帯域幅ｓ1で正規化し、中間ステージの入力リンクを帯域幅ｓ2で正規化し、中間ステージの出力リンクを帯域幅ｓ3で正規化し、出力ステージの出力リンクを帯域幅ｓ4で正規化して解を導出する。その後、再度異なる帯域幅で正規化してもよい。
【００９９】
中間ステージのリンク帯域幅を正規化した場合、式（５）および（６）はそれぞれ以下の式（１０）および（１１）となる。
【０１００】
中間スイッチ要素において、
【０１０１】
【数１３】
0006795172.tif 000014
【０１０２】
中間スイッチ要素において、
【０１０３】
【数１４】
0006795172.tif 000015
【０１０４】
これらの変数のうち、ｓ1,i、ｓ2,i、ｓ3,j、ｓ4,j、ｐ1,i、ｐ2,i、ｐ3,x、ｐ4,y、ｐ5,j、およびｐ6,jは、使用するスイッチ要素の制約と入力ストリームの帯域幅に依存する帯域幅で決まり、有限個の選択枝を有する。ｎ1,i、ｎ4,j、は、式（４）および（９）によりそれぞれｐ1,iおよびｐ6,jで上限が定められる。Ｒ、ｋ、ｎ2,iおよびｎ3,jは、式（５）および（８）の制約によりｐ2,iおよびｐ5,jで上限が定められる。ｒ1およびｒ2は、式（６）および（７）により、ｐ3,xおよびｐ4,yで上限が定められる。よって、取りうる値の集合は有限である。ｄ1,iは、入力ストリームの帯域幅とｎ1,i、ｓ1,iおよび式（１）によって上限が定められる。ｄ2,iおよびｄ3,jは、入力ストリームの帯域幅と、ｎ2,i、ｎ3,j、ｓ2,i、ｓ3,jによって上限が定められる。ｄ4,jは、入力ストリームの帯域幅と、ｎ4,j、ｓ4,jおよび（２）によって上限が定められる。
【０１０５】
従って、式（１）乃至（９）の不等式は、有限回の探索によって、全ての条件を満たす｛ｎ1,i，ｎ2,i，ｎ3,j，ｎ4,j，ｄ1,i，ｄ2,i，ｄ3,j，ｄ4,j，ｒ1，ｒ2，ｍ｝の組を探索することができる。
【０１０６】
次に、双方向伝送可能なスイッチ要素を使用し、入力ステージの機能と出力ステージの機能を同一のスイッチ要素に統合することによって構成されるマルチキャストスイッチングシステムの実施形態について説明する。
【０１０７】
この場合、図４に示した実施形態で使用される各種の変数を共通化することができる。すなわち、入力スイッチ要素と出力スイッチ要素を入出力スイッチ要素として共有することによって、入出力スイッチ要素数ｒ＝ｍａｘ（ｒj，ｒ2）とする。入力リンクと出力リンクを入出力リンクとして共有することによって、入出力リンク数ｎi＝ｍａｘ（ｎ1,i，ｒ4,j）、多重度ｄi＝ｍａｘ（ｄ1,i，ｄ4,j）とし、以後、ｓi＝ｓ1,i＝ｓ4,j、ｐ1,i＝ｐ6,j、ｐ2,i＝ｐ5,jとすることができる。中間ステージの入力リンクと出力リンクを双方向で共有することによって、接続リンク数ｎ’i＝ｎ2,i＝ｎ3,j、ｓ’i＝ｓ2,i＝ｓ3,j、ｄ’i＝ｄ2,i＝ｄ3,j、ｐ3,x＝ｐ4,xとすることができる。さらに、入出力スイッチ要素で、入出力リンク数と接続リンク数の和はスイッチの全リンク数ｐiに等しいから、ｐi＝ｐ1,i＝ｐ2,iである。
【０１０８】
上記のように、双方向伝送可能なスイッチ要素を使用して、入力ステージの機能と出力ステージの機能を同一のスイッチ要素に統合した実施形態を図５に示す。
【０１０９】
入出力ステージには、ｒ個の入出力スイッチ要素５０１、５０２、および５０３が存在する。入出力スイッチ要素５０１、５０２、および５０３はそれぞれ、図４に示した入力スイッチ要素４０１、４０２、および４０３と出力スイッチ要素４３１、４３２、および４３３とをそれぞれ統合したスイッチ要素である。図４に示した入力リンク４４１は出力リンク４７１と統合され、双方向伝送可能な入出力リンク５３１を構成する。同様に、図４に示した入力リンク４４２は出力リンク４７２と統合され、入出力リンク５３２を構成する。
【０１１０】
グループ５１０は、図４に示したグループ４１０に相当し、グループ４１０における中間スイッチ要素５１１および５１２は、図４に示した中間スイッチ要素４１１および４１２に相当する。グループ５２０は、図４に示したグループ４２０に相当し、グループ５２０における中間スイッチ要素５２１および５２２は、図４に示した中間スイッチ要素４２１および４２２に相当する。図４に示した中間ステージの入力リンク４５１は、その中間ステージの出力リンク４６１と統合されて図５のスイッチ間接続リンク５４１を構成する。図４に示した中間ステージの入力リンク４５２は、その中間ステージの出力リンク４６２と統合されてスイッチ間接続リンク５４２を構成する。
【０１１１】
ここで、前述の変数の共有を行った場合、前述の条件式で式（５）および（８）は同一となる。式（４）および（９）から、ｎi＝ｍａｘ（ｎ1,i，ｎ4,j）≦ｐ1,i（＝ｐ6,j）を得る。これに式（５）の両辺を足した式ｎi＋ｎ2,i×ｒ×ｋ≦ｐ1,i＋ｐ2,i＝ｐiによって、新たに以下の不等式（１２）乃至（１６）を得る。なお、ここでは、あらたに変数ｐ’x＝ｐ3,xとする。
入出力ステージにおけるｉ番目の入出力スイッチ要素では、
ｎ1,i×ｓi≦ｋ×ｎ’i×ｓ’i、かつｄ1,i≦ｋ×ｄ’i
式（１２）
入出力ステージにおけるｉ番目の入出力スイッチ要素では、
ｎ4,j×ｓi≦Ｒ×ｎ’i×ｓ’i、かつｄ4,j≦Ｒ×ｄ’i
式（１３）
入出力ステージ全体において、
【０１１２】
【数１５】
0006795172.tif 000016
【０１１３】
入出力ステージにおけるｉ番目の入出力スイッチ要素では、
ｎi＋ｎ’i×Ｒ×ｋ≦ｐi
式（１５）
中間スイッチ要素の全ての帯域幅ｘのリンクにおいて、
【０１１４】
【数１６】
0006795172.tif 000017
【０１１５】
式（１）乃至（９）と同様に、式（１２）乃至（１６）の全ての条件を満たす｛ｎ1,i，ｎ’2,i，ｎ’i，ｄ1,i，ｄ2,i，ｄ’i，ｒ，ｍ｝の組は有限回の探索によって、探索可能である。
【０１１６】
また、前述のように、スイッチ要素の実装方法によっては、帯域幅ｓ1のリンクｎ1（ｎ1≧１）本を帯域幅ｓ2（ｓ1≠ｓ2）のリンク
【０１１７】
【数１７】
0006795172.tif 000018
【０１１８】
本で置き換えることが容易である。このとき、ネットワークがノンブロッキングであるために、入出力ステージの入出力リンクを、多重度を増やさない範囲で置き換える。入出力ステージと中間ステージとの間のリンクを、多重度を減らさない範囲で置き換える。
【０１１９】
この範囲において、入出力ステージの入出力リンクを帯域幅ｓで正規化し、入出力ステージと中間ステージとの間のリンクを帯域幅ｓ’で正規化して解を導出する。その後、再度異なる帯域幅で正規化してもよい。帯域幅ｓ’での正規化を行った場合、式（１６）は以下の式（１７）となる。
【０１２０】
中間スイッチ要素において、
【０１２１】
【数１８】
0006795172.tif 000019
【０１２２】
一般に、物理リンクの帯域幅より少ない帯域幅を上限とした帯域幅制限を設定することは容易である。そこで、入出力スイッチ要素において、使用する入力リンク数と出力リンク数が異なる場合には（ｎ1,i≠ｎ4,j）、入出力リンクの入出力を独立に扱い、総帯域の少ない方を物理リンクの帯域幅より少ない帯域幅で正規化することも可能である。入出力リンクの物理的な帯域幅がｓ1で、ｎ1,i＞ｎ4,jのように、ストリームの出力時に使用するリンク数が少ないとき、多重度ｄ4,jを増やさない範囲で、出力リンクの帯域幅制限ｓ2（ｓ1＞ｓ2）をかけるとともに、入力リンクの使用本数を
【０１２３】
【数１９】
0006795172.tif 000020
【０１２４】
本と増やしてもよい。逆に、ｎ1,i＜ｎ4,jのように、ストリームの入力時に使用するリンク数が少ないとき、多重度ｄ1,iを増やさない範囲で、入力リンクの帯域幅制限ｓ2（ｓ1＞ｓ2）をかけるとともに、出力リンクの使用本数を
【０１２５】
【数２０】
0006795172.tif 000021
【０１２６】
本としてもよい。
【０１２７】
以下、本発明における経路選択方式について説明する。本経路選択方式は、図４で説明したネットワーク構成において実装される。
【０１２８】
まず、以後の説明のために、本発明における中間スイッチ要素に識別番号を付与する。中間ステージは、ｋ個（ｋ≧１）の中間スイッチ要素からなるＲ個（Ｒ≧１）のグループであり、可算個であるから、任意の規則に従って識別番号ｚ（ｍ≧ｚ≧１）をつけることができる。ここで、グループｘ（Ｒ≧ｘ≧１）に属するｙ（ｋ≧ｙ≧１）番目の中間スイッチ要素の識別番号をＭ（ｘ，ｙ）と表記する。
【０１２９】
この中間スイッチ要素への識別番号の付与においては、入力スイッチ要素ごとに個別の番号付けを行ってもよい。この場合、中間スイッチ要素の識別番号は、入力スイッチ要素の識別番号ｉに従って、Ｍ（ｉ，ｘ，ｙ）と表記される。このような番号付けは、上述したノンブロッキング性を保証することにおいて何ら影響を及ぼさない。また式（１）乃至（１１）においても、何ら影響を及ぼさない。以後、全ての入力スイッチ要素が、中間スイッチ要素への識別番号の付与において同一の写像を使用している場合でも、中間スイッチ要素の識別番号を、以下、Ｍ（i，ｘ，ｙx）と表記する。
【０１３０】
次に、個々の入力スイッチ要素ごとに中間ステージにおけるグループの表記を定義する。
【０１３１】
上述したように、中間スイッチ要素への識別番号の付与においては、入力スイッチ要素ごとに個別の番号付けを行ってもよい。この例を表１および表２に示す。表１は、中間スイッチ要素識別子Ｍ（ｘ，ｙ）（ｘ番目のグループのｙ番目の中間スイッチ要素）をｚ番目の中間スイッチ要素（ＭＳ−ｚ）に割り当てる例を示す表である。表２は、中間スイッチ識別子Ｍ（ｉ，ｘ，ｙ）をｚ番目の中間スイッチ要素（ＭＳ−ｚ）に割り当てる例を示す表である。
【０１３２】
表１は、Ｒ＝３、ｋ＝３の場合で、各項目が中間スイッチ要素の識別子Ｍ（ｘ，ｙ）（ｘ番目のグループのｙ番目の中間スイッチ要素）を示す。表１では、各行が９個の中間スイッチ要素９個の何番目の中間スイッチ要素であるか（ｚ番目をＭＳ−ｚと表記)を示し、各列が１０個の入力スイッチ要素（あるいは入出力スイッチ要素）（ＩＳ−１…ＩＳ−１０）を示す。全ての入力（入出力）スイッチ要素に対し、中間スイッチ要素ＭＳ−１をグループ１の１番目の中間スイッチ要素とし、ＭＳ−２をグループ１の２番目の中間スイッチ要素とし、以下同様にＭＳ−９をグループ３の３番目の中間スイッチ要素として割り当てている。
【０１３３】
【表１】
0006795172.tif 000022
【０１３４】
表１  中間スイッチ要素識別子Ｍ（ｘ，ｙ）のｚ番目の中間スイッチ要素（ＭＳ−ｚ）への割り当て
【０１３５】
一方、表２では、上述した識別子の割り当てが入力（入出力）スイッチ要素ごとに異なり、ｉ番目の入力スイッチ要素では、Ｍ（ｉ，ｘ，ｙ）と表記される。入力スイッチ要素ＩＳ−１に対し、中間スイッチ要素｛ＭＳ−１，ＭＳ−２，ＭＳ−３｝をグループ１に割り当てる。また、中間スイッチ要素｛ＭＳ−４，ＭＳ−５，ＭＳ−６｝をグループ２に割り当てる。そして中間スイッチ要素｛ＭＳ−７，ＭＳ−８，ＭＳ−９｝をグループ３に割り当てる。入力スイッチ要素ＩＳ−２に対し、中間スイッチ要素｛ＭＳ−２，ＭＳ−３，ＭＳ−４｝をグループ１に割り当てる。また、中間スイッチ要素｛ＭＳ−５，ＭＳ−６，ＭＳ−７｝をグループ２に割り当てる。中間スイッチ要素｛ＭＳ−８，ＭＳ−９，ＭＳ−１｝をグループ３に割り当てる。入力スイッチ要素ＩＳ−１乃至ＩＳ−９に対し、すべて異なる中間スイッチ要素が割り当てられているが、入力スイッチ要素ＩＳ−１０は、入力スイッチ要素ＩＳ−１と同一の中間スイッチ要素が割り当てられている。このような場合においても、全ての入力が、Ｒ＝３通りの冗長経路を有しているため、ノンブロッキング性が保証される。
【０１３６】
【表２】
0006795172.tif 000023
【０１３７】
表２  中間スイッチ要素識別子Ｍ（ｉ，ｘ，ｙ）のｚ番目の中間スイッチ要素（ＭＳ−ｚ）への割り当て
【０１３８】
表２では、ｉ番目の入力スイッチ要素において、ｘ番目のグループのｙ番目の中間スイッチ要素をＭ（ｉ，ｘ，ｙ）として割り当て、入力スイッチ要素番号ｉとグループ番号ｘを示したが、個々の入力スイッチ要素で独立にグループ番号を任意に割り当ててもよい。例えば、ＩＳ−１は、各グループ内で１番目の中間スイッチ要素｛Ｍ（１，１，１），Ｍ（１，２，１），Ｍ（１，３，１）｝を｛ＭＳ−１，ＭＳ−４，ＭＳ−７｝の組に割り当てているが、どのスイッチを何番目のグループに割り当てるかは、任意に決定してもよい。
【０１３９】
そこで、入力スイッチ要素番号ｉおよびグループ番号ｘを表２からは省略し、グループ内のｙ番目の中間スイッチ要素として番号ｙのみを示す。この場合、表２は表３に示すように簡略表記される．
【０１４０】
【表３】
0006795172.tif 000024
【０１４１】
表３  各グループ内のｙ番目の中間スイッチ要素の全てのｚ番目の中間スイッチ要素の（ＭＳ−ｚ）への割り当て
【０１４２】
また、以下で、ｉ番目の入力スイッチ要素で各グループのｙ番目の配信先集合をＤ（ｉ，ｙ）として示し、Ｄ（ｉ，ｙ）の要素数を｜Ｄ（ｉ，ｙ）｜と示すことにする。Ｄ（ｉ，ｙ）は、表３において、ｉ番目の列内で同一の数字（ｙ）を有する中間スイッチ要素の集合と同義である。例えば、Ｄ（１，１）は、入力スイッチ要素ＩＳ−１における各グループの１番目の中間スイッチ要素の集合であるから、ＩＳ−１列内で数字１を有する中間スイッチ要素の集合であり、Ｄ（１，１）＝｛ＭＳ−１，ＭＳ−４，ＭＳ−７｝となる。以後、表記上「ＭＳ−」を省略し、これをＤ（１，１）＝｛１，４，７｝と表記する。同様に、Ｄ（１，２）＝｛２，５，８｝，Ｄ（１，３）＝｛３，６，９｝，Ｄ（２，１）＝｛２，５，７｝，Ｄ（２，２）＝｛３，６，９｝，…Ｄ（１０，３）＝｛３，６，９｝となり、表３においては、Ｄ（ｉ，ｙ）は｛１，４，７｝，｛２，５，８｝，｛３，６，９｝の３種類しか存在せず、すべてのｉ、ｙにおいて｜Ｄ（ｉ，ｙ）｜＝３である。
【０１４３】
次に、個々のスイッチ要素における入力リンクおよび出力リンクの表記を定義する。
【０１４４】
入力ステージにおけるｉ番目のスイッチ要素では、前記の定義に従い、帯域幅ｓ1,iの入力リンクｎ1,i本で合計ｄ1,i本のストリームを受信する。このストリームは可算個であるから任意の１対１の写像に従って識別番号ａ1（ｄ1,i≧ａ1≧１）をつけることができ、これをＩ1（ｉ，ａ1）と表記する。また、この入力ステージにおけるｉ番目の入力スイッチ要素では、中間ステージにおけるｚ番目の中間スイッチ要素に、帯域幅ｓ2,iの出力リンクｎ2,i本で合計ｄ2,iのストリームを伝送する。このストリームは可算個であるから任意の１対１の写像に従って識別番号ａ2（ｄ2,i≧ａ2≧１）をつけることができ、これをＩ2（ｉ，ｚ，ａ2）と表記する。
【０１４５】
同様に、出力ステージにおけるｊ番目におけるスイッチ要素では、中間ステージにおけるｚ番目のスイッチに、帯域幅ｓ3,jの出力リンクｎ3,j本で合計ｄ3,jのストリームを伝送する。このストリームは可算個であるから任意の１対１の写像に従って識別番号ａ3（ｄ3,j≧ａ3≧１）をつけることができ、これをＯ1（ｚ，ｊ，ａ3）と表記する。また、この出力ステージにおけるｊ番目のスイッチ要素では、帯域幅ｓ4,jの出力リンクｎ4,j本で合計ｄ4,j本のストリームを出力する。このストリームは可算個であるから任意１対１の写像に従って識別番号ａ4（ｄ4,j≧ａ4≧１）をつけることができ、これをＯ2（ｊ，ａ4）と表記する。
【０１４６】
本発明におけるネットワークの経路設定を行う制御装置の実施形態の一つとして、全てのスイッチ要素を制御することが可能な制御装置を、スイッチ要素の外部に設置してもよい。この場合、入力スイッチ要素は、上述した制御装置の命令に応じて、中間ステージにおける各グループのいずれの中間スイッチ要素にストリームを伝送するかのルーティングを行う。また、中間スイッチ要素および／または出力スイッチ要素は、上述した制御装置の命令に応じて、入力ステージから伝送されたストリームを、どのグループから出力ステージに伝送するかのルーティングを行う。
【０１４７】
また、別の実施形態では、後述する入力ステージにおけるルーティング処理をあらかじめ静的に、例えば、装置の電源投入後に自動的に行うことし、経路設定を行う制御装置を、中間スイッチ要素および出力スイッチ要素のみに接続して制御することも可能である。この場合、中間スイッチ要素および／または出力スイッチ要素のみが、上述した制御装置の命令に応じて、入力ステージから伝送されたストリームを、どのグループから出力ステージに伝送するかのルーティングを行う。
【０１４８】
また、別の実施形態では、それぞれの出力スイッチ要素が、その出力スイッチ要素の出力リンクへのマルチキャスト要求のみを受け付け、入力ステージにおけるルーティング処理の結果に基づき中間スイッチ要素を選択し、その中間スイッチ要素に接続要求を送信することによって、制御装置の機構をスイッチ要素内部に分散することもできる。
【０１４９】
以下、本発明における経路選択方式のうち、入力ステージにおけるルーティング処理について説明する。
【０１５０】
入力ステージにおけるルーティング処理、すなわち、入力スイッチ要素における経路設定は、入力ステージにおけるｉ番目の入力スイッチ要素への入力ストリームＩ1（ｉ，ａ1）に対して、全ての中間ステージのグループｘに対し、グループｘごとに｛ｙx，ａ2,x｝（ｋ≧ｙx≧１，ｄ2,i≧ａ2,x≧１）で一意に定まる中間ステージへの経路を割り当て、その割り当てに従ってストリームを伝送してもよい。これはすべての（ｉ，ａ1）に対して以下のような写像として表記することができる。
Ｉ1（ｉ，ａ1）→｛Ｉ2（ｉ，Ｍ（ｉ，１，ｙ1），ａ2,1），Ｉ2（ｉ，Ｍ（ｉ，２，ｙ2），ａ2,2），…，Ｉ2（ｉ，Ｍ（ｉ，Ｒ，ｙR），ａ2,R）｝
【０１５１】
入力ステージにおけるｉ番目の入力スイッチ要素における全ての上記の入力ストリームと出力ストリームとの関係の集合をＦＩiとする。ここで、入力ストリーム全体の個数は、ａ1の上限ｄ1,iである。全てのｘに対して｛ｙx，ａ2,x｝の個数ｄ2,iよりも少ないことが、前記の式（１）および（１２）と定義によって保証されている。よって、適当な｛ｙx，ａ2,x｝を選択してスイッチ要素間で入力ストリームを分散させることによって、このルーティング処理は常に成功する。
【０１５２】
上記の入力ステージにおけるルーティング処理は、出力ステージでのマルチキャスト接続要求に依存しない。また、他の入力スイッチ要素の状態にも依存しない。そのため、入力ステージにおけるルーティング処理は、中間ステージおよび出力ステージでのルーティング処理と分離可能である。また、入力ステージの写像をあらかじめ設定し、伝送の際に中間ステージおよび出力ステージにおける操作のみによって経路設定が可能である。経路を削除する場合も同様であり、必要に応じて出力ステージおよび中間ステージでの経路設定のみを削除すればよい。この特徴により、経路切り替え時の操作量が減少し、経路切り替えに要する時間が短縮される。
【０１５３】
さらに同一の理由により、実施形態の一つとして、この入力ステージにおけるルーティング処理を行う制御機構を、それぞれの入力スイッチ要素の内部に配置してもよい。また、別の実施形態として、入力スイッチ要素の外部に配置された制御装置で実施してもよい。
【０１５４】
また、別の実施形態では、入力ステージにおけるルーティング処理の結果は、前述の記述と等価なルーティングテーブルで管理されてもよい。この場合、そのルーティングテーブルに基づいてストリームのルーティングを行い、ルーティングの都度、ルーティングテーブルが更新される。さらなる別の実施形態では、入力ステージにおけるルーティング処理は、入力スイッチ要素の識別番号および入力ストリームの識別番号に基づく巡回割り当てや剰余計算などによる１対１の写像で行われ、ルーティングの結果が必要な場合に、同一の計算式により対応関係を再計算により導出してもよい。
【０１５５】
以下、本発明における経路選択方式のうち、出力ステージにおけるルーティング処理について説明する。
【０１５６】
出力ステージにおけるルーティング処理は、中間ステージおよび出力ステージの経路を設定する処理である。ここで対象とする任意のマルチキャスト要求は、ある入力ストリームＩ1（ｉ，ａ1）に対して、ｗ（Ｎ2≧ｗ≧１）個の出力ストリーム｛Ｏ2（ｊ1，ａ4,1），Ｏ2（ｊ1，ａ4,2），…，Ｏ2（ｊw，ａ4,w）｝に対応付ける。
【０１５７】
このとき、中間ステージにおけるｚ番目の中間スイッチ要素では、ある入力ストリームＩ1（ｉ，ａ1）に対して、Ｉ2（ｉ，ｚ，ａ2）を入力源として、ｕ（ｒ2≧ｕ≧１）個の出力ストリーム｛Ｏ1（ｚ，ｊ1，ａ3,1），Ｏ1（ｚ，ｊ2，ａ3,2），…，Ｏ1（ｚ，ｊu，ａ3,u）｝に以下のように対応付ける。
Ｉ1（ｉ，ａ1）→Ｉ2（ｉ，ｚ，ａ2）→｛Ｏ1（ｚ，ｊ1，ａ3,1），Ｏ1（ｚ，ｊ2，ａ3,2），…，Ｏ1（ｚ，ｊu，ａ3,u）｝
【０１５８】
この中間ステージにおけるｚ番目の中間スイッチ要素での全ての上記の入力ストリームと出力ストリームとの関係の集合をＦＭzとする。
【０１５９】
同様に、出力ステージにおけるｊ番目のスイッチでは、入力ストリームＩ1（ｉ，ａ1）に対して、Ｏ1（ｚ，ｊ，ａ3）を入力源として、ｖ（ｄ4,j≧ｖ≧１）個の出力ストリーム｛Ｏ2（ｊ，ａ4,1），Ｏ2（ｊ，ａ4,2），…，Ｏ2（ｊ，ａ4,v）｝に以下のように対応付ける。
Ｉ1（ｉ，ａ1）→Ｏ1（ｚ，ｊ，ａ3）→｛Ｏ2（ｊ，ａ4,1），Ｏ2（ｊ，ａ4,2），…，Ｏ2（ｊ，ａ4,v）｝
【０１６０】
この出力ステージにおけるｊ番目のスイッチにおける全ての上記の入力ストリームと出力ストリームとの関係の集合をＦＯjとする。
【０１６１】
新規のマルチキャスト要求に対するルーティング処理と、既存マルチキャスト要求に対するルーティング処理は、実質的に同一である。図６のフローチャートを参照して、新規および既存のマルチキャスト要求に対するルーティング処理を説明する。
【０１６２】
出力ステージにおけるｊ番目の出力スイッチ要素では、マルチキャスト要求における新たな出力先の一つＯ2（ｊ，ａ4）に対し、識別番号ａ4から使用する出力リンクＬOを求める（ステップＳ６０１）。
【０１６３】
集合ＦＯj内でこの同一出力リンクで使用されている出力ストリームが、出力リンクＬOを収容することができる帯域幅の上限に達している場合は、このマルチキャスト要求を受理せず、ステップＳ６１１に遷移する（ステップＳ６０２）。
【０１６４】
前述の出力ステージにおけるｊ番目の出力スイッチ要素で、前述の入力ストリームＩ1（ｉ，ａ1）が集合ＦＯj内に存在する場合は（ステップＳ６０３）、前述の識別番号ａ4をストリームＩ1（ｉ，ａ1）の登録に加え（ステップＳ６１２）、ステップＳ６１０に遷移する。
【０１６５】
前述の入力ストリームＩ1（ｉ，ａ1）に対応する入力ステージにおけるルーティング処理の結果を取得し、その結果に含まれる中間スイッチ要素のリストを抽出する。例えば、入力ステージにおけるルーティング処理の結果が、｛Ｉ2（ｉ，Ｍ（ｉ，１，ｙ1），ａ2,1），Ｉ2（ｉ，Ｍ（ｉ，２，ｙ2），ａ2,2），…，Ｉ2（ｉ，Ｍ（ｉ，Ｒ，ｙR），ａ2,R）｝である場合、中間スイッチ要素のリストは｛Ｍ（ｉ，１，ｙ1），Ｍ（ｉ，２，ｙ2），…，Ｍ（ｉ，Ｒ，ｙR）｝である（ステップＳ６０４）。
【０１６６】
前述の出力ステージにおけるｊ番目の出力スイッチ要素と、上記リストに含まれるＲ個の中間スイッチ要素との間のリンクＲ×ｎ3,j本について、帯域幅と多重度が上限に達していない伝送可能なリンクを１本選択する（ステップＳ６０５）。そして、そのリンクを保持する中間スイッチ要素識別番号Ｍ（ｉ，ｘ，ｙx）、および中間スイッチ要素の出力ストリームの識別番号ａ3を決定する（ステップＳ６０６）。
【０１６７】
前述の出力ステージにおけるｊ番目の出力スイッチ要素では、入力ストリームＩ1（ｉ，ａ1）が、中間スイッチ要素識別番号Ｍ（ｉ，ｘ，ｙx）、および中間スイッチ要素の出力ストリームの識別番号ａ3で示されるＯ1（Ｍ（ｉ，ｘ，ｙx），ｊ，ａ3）を入力源とし、Ｏ2（ｊ，ａ4,1）を出力することを集合ＦＯj内に新規に登録する（ステップＳ６０７）。そして、前述の出力リンクＬOからの出力設定を行う（ステップＳ６０８）。
【０１６８】
ステップＳ６０５で選択した中間スイッチ要素Ｍ（ｉ，ｘ，ｙx）において、ステップＳ６０３およびステップＳ６０４の結果、すなわち、入力ストリームＩ1（ｉ，ａ1）がＩ2（ｉ，Ｍ（ｉ，ｘ，ｙx）ａ2,x）を入力源とし、Ｏ1（Ｍ（ｉ，ｘ，ｙx），ｊ，ａ3）を新たな出力に加えたことを、
【０１６９】
【数２１】
0006795172.tif 000025
【０１７０】
に登録する（ステップＳ６０９）。そして、出力ストリームＯ1（Ｍ（ｉ，ｘ，ｙx），ｊ，ａ3）を出力する設定を行い、出力リンクＬOからの伝送を開始し、Ｏ2（ｊ，ａ4）に対する処理を終了する（ステップＳ６１０）。
【０１７１】
上記ステップＳ６０１乃至ステップＳ６１０を、マルチキャスト要求の全ての出力ストリームに対して実行する（ステップＳ６１１）。
【０１７２】
実施形態の一つでは、集合ＦＭ2およびＦＯjは、スイッチ要素外部の制御装置にテーブルとして配置されてもよい。また別の実施形態では、集合ＦＭ2およびＦＯjは、パケット交換スイッチが使用するルーティングテーブルと同一であってもよい。また、集合ＦＭ2は、それぞれの中間スイッチ要素内で管理され、集合ＦＯjは、それぞれの出力スイッチ要素内で管理されてもよい。
【０１７３】
ステップＳ６０４での入力ステージにおけるルーティング処理の結果の参照も同様である。実施形態の一つでは、スイッチ外部の制御装置にルーティングテーブルとして配置されてもよい。別の実施形態では、出力ステージにおけるルーティング処理と分離して静的に行うことが可能であるため、個々の中間スイッチ要素および出力スイッチ要素にあらかじめ結果が配布される。また別の実施形態では、識別番号からの再計算によって取得されてもよい。
【０１７４】
実施形態の一つでは、集合ＦＯj、およびステップＳ６０４における入力ステージにおけるルーティング処理の結果を、それぞれの出力スイッチ要素に保有することによって、ステップＳ６０１乃至ステップＳ６０８の処理を、それぞれの出力スイッチ要素において独立かつ並列に実施してもよい。
【０１７５】
ステップＳ６０７およびＳ６０８において、選択の候補であるリンクＲ×ｎ3,j本の現時点での帯域幅および多重度について、出力スイッチ要素だけでなく、個々の中間スイッチ要素も、そのスイッチ要素が保持するリンクを内部状態として保持してもよい。従って、実施形態の一つとして、前述のように、出力スイッチ要素で実施する代わりに、｛Ｍ（ｉ，１，ｙ1），Ｍ（ｉ，２，ｙ2），…，Ｍ（ｉ，Ｒ，ｙR）｝の中間スイッチ要素において個別に利用可能なリンクおよびストリームの識別番号の選択を実施し、その候補のリストから出力スイッチ要素において最終的な選択を行う。また別の実施形態では、出力スイッチ要素において、候補となる中間スイッチ要素を一つ選択し、選択された中間スイッチ要素において出力ストリームの識別番号ａ3を決定する。
【０１７６】
ステップＳ６０９の処理について、実施形態の一つでは、スイッチ要素外部の制御装置が、ステップＳ６０１乃至ステップＳ６０８の結果に基づいてルーティング処理を行ってもよい。別の実施形態では、スイッチ要素外部では制御装置を有さず、ステップＳ６０１乃至ステップＳ６０８を実施した出力スイッチ要素が、任意の通信手段によって、該当する中間スイッチ要素に要求を送出し、中間スイッチ要素自身が設定してもよい。このときの通信手段は、専用の通信路を有してもよく、また、当該出力スイッチ要素と当該中間スイッチ要素との間に存在するマルチキャスト配信用のリンクを使用して行ってもよい。
【０１７７】
上述した入力ステージにおけるルーティング処理、および、出力ステージにおけるルーティング処理の結果に基づいて、入力ソースが出力先へストリームを伝送する方法は、実施形態で使用するスイッチ要素の伝送方式を使用してもよい。
【０１７８】
実施形態の一つでは、スイッチ要素としてイーサネット（登録商標）のスイッチを使用してもよい。この場合、出力先の指定は宛先ＭＡＣアドレスと仮想ネットワーク(ＶＬＡＮ)のいずれか、または両方で宛先を指定する。別の実施形態では、ＩＰスイッチを使用してもよい。この場合、出力先の指定は、宛先ＩＰアドレスで行う。また別の実施形態では、ＯｐｅｎＦｌｏｗ方式のスイッチを使用してもよい。この場合、出力先の指定は、ＯｐｅｎＦｌｏｗの定める任意のパケット情報を使用することができる。一般的なＯｐｅｎＦｌｏｗ方式のスイッチでは、宛先ＭＡＣアドレス、送信元ＭＡＣアドレス、宛先ＩＰアドレス、送信元ＩＰアドレス、宛先ＴＣＰ／ＵＤＰポート番号、送信元ＴＣＰ／ＵＤＰポート番号、ＶＬＡＮ番号、および／または入力ポート番号などを使用して、出力先を決定することができる。
【０１７９】
実施形態の一つとして、一般的なスイッチをスイッチ要素として使用する場合、ある入力ストリームを受信し、それを出力するときに、同一リンクで同一ストリームを複数回伝送する機能を有さないことがある。上記のステップＳ６０１乃至ステップＳ６０７は、このような制約の影響を受けない。また、上記のステップは、任意の入力ストリームについて、任意の中間スイッチ要素から任意の出力スイッチ要素への伝送は、少なくとも一つの伝送によって行われるため、前述の制約は、本発明の実施を妨げない。
【０１８０】
また、実施形態の一つとして、一般的なイーサネットスイッチをスイッチ要素として使用する場合、任意の入力ストリームを受信し、それを出力するときに、同一リンクで出力（ループバック配信）する機能を有さないことがある。上記のステップＳ６０１乃至ステップＳ６０７は、このような制約の影響を受けない。スイッチ要素にそのような制約が存在し、かつ、任意の入力ストリームについて、入力スイッチ要素および出力スイッチ要素が、入出力ステージにおける物理的に同一のｉ番目のスイッチ要素であった場合であっても、入力ステージから中間ステージへの伝送、および中間ステージから出力ステージへの伝送において、ｎ’i本のリンクが存在し、かつ、ｎ’i＞１の条件下において、中間スイッチ要素において入力ストリームおよび出力ストリームに対しそれぞれ異なる物理リンクを使用することによって、必ず中間スイッチ要素を経由する伝送を行うことが可能である。これはステップＳ６０４の物理リンクの選択条件の実施形態の一つである。
【０１８１】
ただし、この場合、入出力スイッチ要素において、入力リンクから中間ステージへの中継経路と、中間ステージから出力リンクへの中継経路を宛先アドレス以外で分離し、中間ステージからのストリームが再び中間ステージへ戻るループを回避する必要がある。イーサネットスイッチを使用する実施形態では、そのような場合、それぞれに異なるＶＬＡＮやそれに類似する仮想ネットワークを割り当てることによって分離することができる。また、ＯｐｅｎＦｌｏｗ方式のスイッチを使用する実施形態では、出力先の経路を指定する際に、入力ポートの指示を含めるルールを作成することによって、同一の宛先アドレスを有するフローを別々に扱うことができる。
【０１８２】
入力スイッチ要素および出力スイッチ要素を統合して、物理的に同一のスイッチ要素を実装する実施形態の一つでは、入力ステージでのルーティング処理における入力ステージにおける入力ストリームと出力ストリームとの関係の集合ＦＩi、および、出力ステージでのルーティング処理における出力ステージにおける入力ストリームと出力ストリームとの関係の集合ＦＯiを、一つの入力ストリームと出力ストリームとの関係ＦＩＯiとして管理してもよい。このような場合の一つの実施形態として、入出力スイッチ要素への入力ストリームＩ1（ｉ，ａ1）を、同一スイッチ要素で当該ストリームを出力する場合には、中間スイッチ要素からストリームを伝送する代わりに、その出力ストリームＯ2（ｉ，ａ4）を直接出力してもよい。これは、ＦＩＯi内の入力ストリームＩ1（ｉ，ａ1）に対する写像が、Ｒ個の中間ステージへの出力ストリームＩ2と、０以上の出力リンクへの出力ストリームＯ2とを含む形式で定義される。
【０１８３】
また、ある実施形態では、入力スイッチ要素および出力スイッチ要素を統合して物理的に同一のスイッチ要素を実装し、任意の入力ストリームに対して、必ず中間ステージを経由する伝送を行うか、または、出力先が同一入出力スイッチ要素にある場合は、中間ステージをバイパスして伝送するかの選択を可能とする。これにより、低遅延の伝送が求められる入力に対してはバイパスを利用し、ばらつきの少ない遅延が求められる入力に対しては、かならず中間ステージを経由することによって、経由するスイッチ要素数を平準化することが可能になる。
【０１８４】
以下、本発明における経路選択方式に基づいて、マルチキャストの経路を削除する場合の削除処理について、図７のフローチャートを参照して説明する。
【０１８５】
出力ステージにおける削除処理は、対象とする任意のマルチキャスト要求、すなわち、１つの入力ストリームＩ1（ｉ，ａ1）に対応付けられたｗ（Ｎ2≧ｗ≧１）個の出力ストリーム｛Ｏ2（ｊ1，ａ4,1），Ｏ2（ｊ2，ａ4,2），…，Ｏ2（ｊw，ａ4,w）｝の中から任意の数の出力先を削除する処理であり、出力ステージ、中間ステージ、および入力ステージの順に設定する。
【０１８６】
ここで、削除対象の出力ストリームをＯ2（ｊ，ａ4）とし、ルーティング処理と同様に、集合ＦＯj、ＦＭzおよびＦＩjが定義されているものとする。
【０１８７】
出力ステージにおけるｊ番目の出力スイッチ要素では、削除対象のＯ2（ｊ，ａ4）の識別番号ａ4から使用する出力リンクＬOを求める（ステップＳ７０１）。そして、入力ストリームＩ1（ｉ，ａ1）の出力リンクＬOからの出力を停止し、集合ＦＯj内の入力ストリームＩ1（ｉ，ａ1）に対応する出力先リストから削除対象のＯ2（ｊ，ａ4）を削除する（ステップＳ７０２）。
【０１８８】
前述の入力ストリームＩ1（ｉ，ａ1）の出力先が集合ＦＯj内で空集合でない場合（ステップＳ７０３）、ステップＳ７１１に遷移する。
【０１８９】
前述の入力ストリームＩ1（ｉ，ａ1）の出力先が集合ＦＯj内で空集合の場合、削除によって出力先が存在しなくなったことを意味するから、入力ストリームＩ1（ｉ，ａ1）に対応する出力ストリームＯ1（ｚ，ｊ，ａ3）をＦＯjから取り出し、入力ストリームＩ1（ｉ，ａ1）の情報を削除する（ステップＳ７０４）。
【０１９０】
ステップＳ７０４におけるＯ1（ｚ，ｊ，ａ3）について、中間ステージにおけるｚ番目の中間スイッチ要素において、削除対象の出力ストリームＯ1（ｚ，ｊ，ａ3）の識別番号ａ3から使用するリンクＬｍを求める（ステップＳ７０５）。そして、入力ストリームＩ1（ｉ，ａ1）のリンクＬｍからの伝送を停止し、集合ＦＭ2内の入力ストリームＩ1（ｉ，ａ1）に対応する出力先リストから削除対象のＯ1（ｚ，ｊ，ａ3）を削除する（ステップＳ７０６）。
【０１９１】
前述の入力ストリームＩ1（ｉ，ａ1）の出力先が集合ＦＭ2内で空集合でない場合（ステップＳ７０７）、ステップＳ７１１に遷移する。
【０１９２】
前述の入力ストリームＩ1（ｉ，ａ1）の出力先が集合ＦＭ2内で空集合の場合、削除によって出力先が存在しなくなったことを意味するので、入力ストリームＩ1（ｉ，ａ1）に対応する入力ストリームＩ2（ｉ，ｚ，ａ2）をＦＭ2から取り出し、入力ストリームＩ1（ｉ，ａ1）の情報を削除する（ステップＳ７０８）。
【０１９３】
ステップＳ７０８における入力ストリームＩ2（ｉ，ｚ，ａ2）について、入力ステージにおけるｉ番目の入力スイッチ要素において、削除対象のＩ2（ｉ，ｚ，ａ2）の識別番号ａ2から使用するリンクＬｉを求める（ステップＳ７０９）。そして、入力ストリームＩ1（ｉ，ａ1）のリンクＬｉからの伝送を停止し、集合ＦＩi内の入力ストリームＩ1（ｉ，ａ1）に対応する出力先リストから削除対象のＩ2（ｉ，ｚ，ａ2）を削除する（ステップＳ７１０）。
【０１９４】
上記ステップＳ７０１乃至ステップＳ７１０を、削除対象の全ての出力先に対して実行する（ステップＳ７１１）。
【０１９５】
実施形態の一つとして、上記のステップＳ７０７乃至ステップＳ７１０を省略し、１つの入力ストリームＩ1（ｉ，ａ1）の出力先が集合ＦＭ2内で空集合であってもよい。これは、中間ステージにおけるｚ番目の中間スイッチ要素では、入力ステージからのストリームを受信しているが、伝送することなく、該当ストリームを破棄している状態を意味する。これにより、中間ステージまではストリームが常に到達していることが保証されるため、前述の出力ステージにおけるルーティング処理を入力ステージにおけるルーティング処理と分離することができる。
【０１９６】
以下、具体例をあげて、本発明における解を示す。これらは実施形態の一つを表しており、これまで示したように、本発明の構成は以下の限定的な数字に限定されるものではない。
【０１９７】
ここでは、例として、１０Ｇｂｐｓおよび４０Ｇｂｐｓのリンク速度を有するイーサネットスイッチをあげる。
【０１９８】
一つは、１０Ｇｂｐｓのリンクを最大９６本有し、スイッチ要素単体はノンブロッキングなマルチキャストが可能である。ここで特定の１０Ｇｂｐｓのリンク４本を４０Ｇｂｐｓのリンク１本と置き換えることができ、全てのリンクを置き換えた場合に４０Ｇｂｐｓのリンクを最大２４本有することができるものとする。各ソースは、１．５Ｇｂｐｓの帯域幅を使用するものとする。
【０１９９】
イーサネット（登録商標）のスイッチは、双方向で通信が可能なリンクを有するので、入力ステージの機能と出力ステージの機能を統合し、式（１２）乃至（１６）に基づいて解を導出する。
【０２００】
簡易化のため、入出力ステージにおけるｉ番目の入出力スイッチ要素について、ｓi＝ｓ’i＝１０（Ｇｂｐｓ）とし、ｐi＝９６とする。また、中間ステージにおけるｊ番目の中間スイッチ要素について、１０（Ｇｂｐｓ）の帯域幅のリンクを使用したポート数ｐ10＝９６を使用する。このとき、式（１２）乃至（１６）は、以下のようになる。
入出力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ1,i≦ｋ×ｎ’i、かつｄ1,i≦ｋ×ｄ’i
式（１８）
入出力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ4,j≦Ｒ×ｎ’i、かつｄ4,j≦Ｒ×ｄ’i
式（１９）
入出力ステージ全体において、
ｎi＞ｎ’i、かつｄi＞ｄ’i
式（２０）
入出力ステージにおけるｉ番目の入出力スイッチ要素では、
ｎi＋ｎ’i×Ｒ×ｋ≦９６
式（２１）
中間スイッチ要素の帯域幅１０Ｇｂｐｓのリンクにおいて、
ｒ×ｎ’i≦９６
式（２２）
これらを満たす解を以下に例示する。
【０２０１】
【表４】
0006795172.tif 000026
【０２０２】
表４  解
【０２０３】
これらの解は、全スイッチ要素数がｒ＋ｍであり、（ｒ×ｄ1）×（ｒ×ｄ4）のストリームをノンブロッキングでマルチキャストすることができるマルチキャストスイッチングシステムの実施形態である。
【０２０４】
番号１に示す解は、スイッチ要素数が１０、１１５２×１１５２のマルチキャストスイッチングシステムである。
【０２０５】
番号２に示す解は、スイッチ要素数が１０、８６４×８６４のマルチキャストスイッチングシステムである。番号１に示す解と比較し、入出力ステージにおけるスイッチ要素の入出力リンク数を減じている。
【０２０６】
番号３に示す解は、スイッチ数が９、９６０×９６０のマルチキャストスイッチングシステムである。番号１に示す解と比較し、入出力ステージにおけるスイッチ要素数を減じている。
【０２０７】
番号４に示す解は、スイッチ要素数が９、入出力数が非対称の５７６×１７２８のマルチキャストスイッチングシステムである。
【０２０８】
番号５に示す解は、スイッチ要素数が２１、１７２８×１７２８のマルチキャストスイッチングシステムである。
【０２０９】
番号６に示す解は、スイッチ要素数が４０、２３０４×２３０４のマルチキャストスイッチングシステムである。
【０２１０】
番号７に示す解は、スイッチ要素数が５７、２８８０×２８８０のマルチキャストスイッチングシステムである。このときの総入出力リンク数はｒ×ｎ＝４８０である。
【０２１１】
番号８に示す解は、スイッチ要素数が２０、入力リンクおよび出力リンク数が非対称の２３０４×１１５２のマルチキャストスイッチングシステムである。
【０２１２】
番号９に示す解は、番号８に示す解と入力リンクと出力リンクとの関係が逆転しており、スイッチ要素数が２０、入力リンクおよび出力リンク数が非対称の１１５２×２３０４のマルチキャストスイッチングシステムである。
【０２１３】
ここで１０Ｇｂｐｓのリンクを使用する場合、リンク１本あたりの多重度は、
【０２１４】
【数２２】
0006795172.tif 000027
【０２１５】
である。４０Ｇｂｐｓのリンクを使用する場合、リンク１本あたりの多重度は
【０２１６】
【数２３】
0006795172.tif 000028
【０２１７】
である。１０Ｇｂｐｓ４本の多重度は２４＝６×４であるから、１０Ｇｂｐｓのリンク４本から４０Ｇｂｐｓのリンク１本に置き換えると、多重度が増加する。前述の記述より、中間ステージにつながるリンクは、この置換を任意に行ってよい。一方、入出力リンクにおいて同様の置換を行ってもよいが、その場合は多重度を２４に維持しなければならない。上記の解には、これらの規則により、リンクの帯域幅の置換を任意に行ってもよい。
【０２１８】
注意すべき点として、番号１乃至６に示す解においては、ｓi＝ｓ’i＝４０（Ｇｂｐｓ）とし、ｐi＝２４としても、同様に解を導出することができ、その場合も前述のリンクの帯域幅の置換を行って、等価な解を導出することができる。一方、番号７に示す解は、ｎ’i＝３であり、中間ステージにおける任意の１つのスイッチ要素と入出力ステージにおける任意の１つのスイッチ要素との間には３０Ｇｂｐｓの帯域幅しか有さないため、ｓi＝ｓ’i＝４０（Ｇｂｐｓ）とした例では導出することができない。
【０２１９】
次に表１に示した解を例として、経路設定の実施形態を例示する。
【０２２０】
図８は、表１に示した解の実施形態を示す。入出力ステージ８３０はｒ＝６個の入出力スイッチ要素８３１、８３２、８３３、８３４、８３５、および８３６を有し、それぞれは９６本の１０ギガビットイーサネットのリンクを有する。中間ステージは、グループ８１０および８２０を有し、それぞれが２個ずつ、計ｍ＝４個の中間スイッチ要素８１１、８１２、８２１、および８２２を有する。中間スイッチ要素８１１、８１２、８２１、および８２２のそれぞれは、９６本の１０ギガビットイーサネットのリンクを有する。入出力スイッチ要素８３１乃至８３６のそれぞれは、帯域幅１０Ｇｂｐｓの入出力リンクをｎi＝３２本有し、多重度６を有するので、合計でｄi＝１９２本の入力ストリームおよび出力ストリームを伝送する。入力元・出力先８４１乃至８４６は、それぞれの入出力スイッチ要素８３１乃至８３６に接続された１９２本の入力元と出力先を示す。リンク８５１に示される各スイッチ要素間の接続には、帯域幅１０Ｇｂｐｓの接続リンクｎ’i＝１６本で合計ｄ’i＝９６本のストリームを伝送する。
【０２２１】
ここで、入出力ステージにおけるｉ番目の入出力スイッチ要素（６≧ｉ≧１）の合計ｄi＝１９２本の入力ストリームに任意の１対１の写像ｆにより識別番号ａ1（ｄ1,i＝１９２≧ａ1≧１）をつける。写像ｆの実施形態の一つとしては、ｘ番目（ｎ＝３２≧ｘ≧１）の入力リンクのｙ番目
【０２２２】
【数２４】
0006795172.tif 000029
【０２２３】
の入力ストリームに対し、ａ1＝ｆ（ｘ，ｙ）＝６（ｘ−１）＋ｙとすることである。別の実施形態では、索引の順序を変えて、ａ1＝ｆ’（ｘ，ｙ）＝ｘ＋３２（ｙ−１）とすることである。また、別の実施形態では、このｎi＝３２本のリンクに、実際のストリームが入力された順番で、ａ1を定義し、その対応表を作る。このような形式は、ストリームの帯域幅が不定であり、またはリンクのそれぞれに収容することができるストリームの本数が不定であった場合でも番号付けが可能である。
【０２２４】
同様に、入出力ステージにおけるｉ番目の入出力スイッチ要素と、中間ステージにおけるｊ番目の中間スイッチ要素（ｍ＝４≧ｊ≧１）との間の接続リンクで定義された合計ｄ’i＝９６本のストリームに任意の１対１の写像ｇにより識別番号ａ2（ｄ’i＝９６≧ａ2≧１）をつける。写像ｇの実施形態の一つは、ｘ番目（１６≧ｘ≧１）のリンクのｙ番目
【０２２５】
【数２５】
0006795172.tif 000030
【０２２６】
のストリームに対し、ａ2＝ｇ（ｘ，ｙ）＝６（ｘ−１）＋ｙとすることである。別の実施形態は、索引の順序を変えて、ａ2＝ｇ’（ｘ，ｙ）＝ｘ＋１６（ｙ−１）とすることである。また別の実施形態では、中間ステージにおけるスイッチ要素の番号ｊを使用して、中間ステージにおけるスイッチ要素間で異なる写像を選択してもよい。
【０２２７】
さらに、前述の識別番号ａ3および識別番号ａ4を付与する。これは、ａ1およびａ2と同様に、かつ、独立に定めてもよい。
【０２２８】
次に、入力ステージにおけるルーティング処理の実施形態を上記の例を元に例示する。
【０２２９】
表１において番号１に示した解の実施例では、Ｒ＝２、ｋ＝２であり、中間スイッチ要素はｍ＝Ｒ×ｋ＝４であるから、これらを｛Ｍ11，Ｍ12，Ｍ21，Ｍ22｝とし、｛Ｍ11，Ｍ12｝と｛Ｍ21，Ｍ22｝がそれぞれ同一のグループに属するとものとする。入出力ステージにおけるｉ番目の入出力スイッチ要素に１９２本のストリームａ1は入力される。このスイッチ要素からそれぞれの中間スイッチ要素に９６本のストリームａ2が伝送される。中間ステージの各グループは２個のスイッチ要素を有するから、各グループにおいて１９２のストリームを１９２（＝９６×２）の出力ストリームに１対１で分配する。これをそれぞれのグループに対して行う。前述の記述を用いて表記すれば、以下の表記で｛ａ2，ａ’2，ｂ，ｂ’｝を定めることに相当する。
Ｉ1（ｉ，ａ1）→｛Ｉ2（ｉ，Ｍ1b，ａ2），Ｉ2（ｉ，Ｍ2b，ａ’2）｝
【０２３０】
実施形態の一つは、写像ｆ1（ｘ，ｙ）＝９６（ｘ−１）＋ｙを使用して、ａ1＝ｆ1（ｂ，ａ2）と関係を定義し、さらにグループ間で同一の写像を使用して、ａ′2＝ａ2，ｂ′＝ｂとすることである。この場合、例としてａ1＝１００とする場合、ｂ＝ｂ’＝２，ａ2＝ａ’2＝４と一意に値が定まる。別の実施形態では、索引の順序を変えた別の写像ｆ2（ｘ，ｙ）＝ｘ＋２（ｙ−１）を使用して、ａ1＝ｆ2（ｂ，ａ2），ａ1＝ｆ2（ｂ’，ａ’2）と定義する。また、別の実施形態では、ａ1＝ｆ1（ｂ，ａ2），ａ1＝ｆ2（ｂ’，ａ’2）のように、グループごとに異なる写像を使用してもよい。また別の実施形態では、写像を使用せずに対応表を作ることで、割り当てを行ってもよい。
【０２３１】
次に、出力ステージにおけるルーティング処理の実施形態を上記の例を元に例示する。
【０２３２】
番号１に示した解の実施形態において、中間ステージにおけるｊ番目の中間スイッチ要素（ｍ＝４≧ｊ≧１）から入出力ステージにおけるｉ番目の入出力スイッチ要素（ｒ＝６≧ｉ≧１）には、帯域幅１０Ｇｂｐｓの接続リンクｎ’i＝１６本で合計ｄ’i＝９６本のストリームが伝送される。このストリームの出力先に識別番号ａ3（ｄ’i＝９６≧ａ3≧１）をつける。実施形態の一つとして、ａ3にはａ2と同一の写像を使用し、ｘ番目のリンクのｙ番目のストリームとａ3＝ｇ（ｘ，ｙ）のように対応付ける。
【０２３３】
同様に、入出力ステージにおけるｉ番目の入出力スイッチ要素は、帯域幅１０Ｇｂｐｓの入力リンクｎi＝３２本で合計ｄi＝１９２本のストリームを出力する。このストリームの出力先に識別番号ａ4＝（ｄ1,i＝１９２≧ａ4≧１）をつける。実施形態の一つとして、出力先ａ4にはａ1と同一の写像を使用し、ｘ番目の出力リンクのｙ番目の出力先とａ4＝ｆ（ｘ，ｙ）のように対応付ける。
【０２３４】
先の入力ストリームＩ1（ｉ，ａ1）に対して、入出力ステージにおけるｉ番目の入出力スイッチ要素の出力先ａ4、すなわちＯ2（ｊ，ａ4）へルーティングを行うものとし、入力ステージにおけるルーティング処理の結果がＩ1（ｉ，ａ1）→｛Ｉ2（ｉ，Ｍ1b，ａ1），Ｉ2（ｉ，Ｍ2b’，ａ’2）｝であるとする。出力ステージにおけるルーティングではグループ１を経由する場合、
Ｉ1（ｉ，ａ1）→Ｉ2（ｉ，Ｍ1b，ａ2）→Ｏ1（Ｍ1b，ｊ，ａ3）→Ｏ2（ｊ，ａ4）となるａ3を決定する。グループ２を経由する場合、
Ｉ1（ｉ，ａ1）→Ｉ2（ｉ，Ｍ2b’，ａ’2）→Ｏ1（Ｍ2’b，ｊ，ａ’3）→Ｏ2（ｊ，ａ4）となるａ’3を決定する。
【０２３５】
実施形態の一つでは、ａ3＝ａ’3＝ａ4ｍｏｄ９６として、利用可能なリンクＯ1を探す。１９２≧ａ4≧１であるから、同一のａ3およびａ’3を共有するストリームは２個あるが、上記のようにグループの候補も２個あるのでどちらかを選択することができる。また別の実施形態では、割り当て要求を受理した順番でａ3およびａ’3を割り当てた対応表を作り管理してもよい。また、別の実施形態では、スイッチ要素がイーサネットスイッチの場合は、ａ2、ａ3およびａ’2、ａ’が同一の物理リンクにならないよう、ａ3およびａ’3の決定において、写像の範囲を制限して探索してもよい。
【０２３６】
図９は、入出力ストリーム数が非対称となる、表１における番号８に示した解８の実施形態を示す。入出力ステージ９３０は、ｒ＝１２個の入出力スイッチ要素９３１乃至９４２を有する。入出力スイッチ要素９３１乃至９４２のそれぞれは、９６本の１０ギガビットイーサネットのリンクを有する。中間ステージは、グループ９１０および９２０を有し、それぞれが４個ずつ、計ｍ＝８個の中間スイッチ要素９１１乃至９１４、および９２０乃至９２４を有する。中間スイッチ要素９１１乃至９１４、および９２０乃至９２４のそれぞれは、９６本の１０ギガビットイーサネットのリンクを有する。入出力スイッチ要素９３１乃至９４２のそれぞれは、帯域幅１０Ｇｂｐｓの入出力リンク９６１乃至９７２をｎi＝ｎ1,i＝３２本有し、それぞれが多重度６を有するので、合計でｄi＝ｄ1,i＝１９２本の入力元を有する。一方、出力リンクについてはｎ2,i＝１６本を使用しｄ2,i＝９６本の出力先を有する。リンク９５１に示される各スイッチ要素間の接続には、帯域幅１０Ｇｂｐｓの接続リンクｎ’i＝１６本で合計ｄi＝９６本のストリームが伝送される。
【０２３７】
入出力リンク９６１乃至９７２において、ノンブロッキングを保証するためには、出力リンクは１０Ｇｂｐｓの帯域で１６本使用することができる。ここで、入出力スイッチ要素９３１乃至９４２のそれぞれは、双方向で伝送可能な入出力リンクを３２本有している。一般に、物理リンクの帯域幅より少ない帯域幅を上限としてリンクに設定することは容易である。そこで、入出力を独立に扱い、総帯域の少ない方を、物理リンクの帯域幅より少ない帯域幅で正規化することも可能である。実施形態の一つにおいては、例えば、入出力リンク９６１乃至９７２の帯域幅上限を５Ｇｂｐｓに設定し、３２本の物理リンクを使用して、９６本の出力先を定義してもよい。
【０２３８】
次に、図４で説明した構成において、ＷＳＮＢ条件を満たす解を基本構成とし、そこから、ＲＮＢ条件を満たす解を導出する方法を示す。
【０２３９】
まず、ＷＳＮＢ条件におけるネットワークの構成と入力ステージにおけるルーティング処理については、個々の入力ストリームが、ｋ個の中間スイッチ要素から構成されるＲ個のグループの送信されることは上述した。このときの個々の入力スイッチ要素は中間スイッチを識別・選択するための固有の識別番号Ｍ（ｉ，ｘ，ｙ）を有することを前提とする。また、任意のｉ番目の入力スイッチ要素で、個々の入力ストリームがグループｘ内のｙ番目のスイッチ要素を選択する際は、全てのグループで共通のｙ（ｋ≧ｙ≧１）番目のスイッチ要素を選択するとする。この修正はＷＳＮＢ条件と矛盾しない。また、個々の入力スイッチ要素が個別に中間スイッチ要素識別番号を有することから、中間スイッチ要素をグループ化し、その中のスイッチ要素を選択する際の自由度は失われない。
【０２４０】
以下、ＲＮＢ条件においては、上記示した式（１）乃至（１１）と等価な以下の式を使用して、入力ステージにおけるルーティング処理、すなわち、入力スイッチ要素における経路設定を行う。この経路設定では、入力ステージにおけるｉ番目の入力スイッチ要素への入力ストリームＩ１（ｉ，ａ1）に対して、ある配信先集合Ｄ（ｉ，ｙ）を選択し、Ｄ（ｉ，ｙ）の要素である中間スイッチ要素のそれぞれに対して、｛ｙ，ａ2,x｝（ｋ≧ｙ≧１，ｄ2,i≧ａ2,x≧１）で一意に定まる中間ステージへの経路を割り当て、その割り当てに従ってストリームを伝送する。これはすべての（ｉ，ａ1）に対して以下のような写像として表記することができる。
Ｉ1（ｉ，ａ1）→｛Ｉ2（ｉ，Ｍ（ｉ，１，ｙ），ａ2,1），Ｉ2（ｉ，Ｍ（i，２，ｙ），ａ2,2），…，Ｉ2（ｉ，Ｍ（i，Ｒ，ｙ），ａ2,R）｝
ここで、Ｄ（ｉ，ｙ）＝｛Ｍ（ｉ，１，ｙ），Ｍ（ｉ，２，ｙ），…Ｍ（ｉ，Ｒ，ｙ）｝である。
【０２４１】
ここで、ＲＮＢ条件に変更するために以下の配信方法を追加する。
【０２４２】
第一に、任意のｗ個（ｋ≧ｗ≧１）個の中間スイッチ要素を削減し、中間スイッチ要素数をｍ＝Ｒ×ｋ−ｗとする。全ての入力スイッチ要素は、削減した中間スイッチ要素数に合わせて中間ステージへの配信数が削減されるが、その際に以下の条件Ａまたは条件Ｂの選択を行う。
【０２４３】
〔条件Ａ〕．各入力ストリームの配信先を少なくともＲ個の中間スイッチ要素に指定する。このとき、中間スイッチ要素の総数を減じているため、各グループ内で使用することができる中間スイッチ要素数を削減する。すなわち、グループ内のｋ個の中間スイッチ要素のうち、
【０２４４】
【数２６】
0006795172.tif 000031
個は使用しないものとし、収容することができる入力ストリーム数を、
【０２４５】
【数２７】
0006795172.tif 000032
個の中間スイッチ要素に相当する数に削減する。この入力ストリームが入力される入力スイッチ要素は、各中間スイッチ要素のグループとして、１番目から
【０２４６】
【数２８】
0006795172.tif 000033
番目までの中間スイッチ要素を使用し、全てのグループのｙ番目
【０２４７】
【数２９】
0006795172.tif 000034
の中間スイッチ要素の集合Ｄ（ｉ，ｙ）は要素数｜Ｄ（ｉ，ｙ）｜が少なくともＲであり、Ｄ（ｉ，ｙ）⊇｛Ｍ（ｉ，１，ｙ），Ｍ（ｉ，２，ｙ），…Ｍ（ｉ，Ｒ，ｙ）｝となる。従って、上記の式（１）は、入力ステージにおけるｉ番目の入力スイッチ要素では、
【０２４８】
【数３０】
0006795172.tif 000035
かつ、
【０２４９】
【数３１】
0006795172.tif 000036
に置き換わる。また、上記式（５）は、入力ステージにおけるｉ番目の入力スイッチ要素では、
ｎ2,i×(Ｒ×ｋ-w)≦ｐ2,i                          式（２５）
に置き換わる。
【０２５０】
〔条件Ｂ〕．中間スイッチ要素数を削減した分を、Ｒ個のグループのＲ番目のグループに対してのみ適用する。具体的には、各グループ内のｋ個のスイッチのうち、１番目からｗ番目までの中間スイッチ要素Ｍ（ｉ，ｘ，ｙ）、ｗ≧ｙ≧１に対して入力ストリームを配信する場合、Ｒ番目のグループには配信しない。すなわち、これらの入力ストリームの配信先は、Ｒ−１個の中間スイッチ要素となり、Ｒ番目のグループに限り、ｋ個ではなくｋ−ｗ個の中間スイッチ要素を有する。各グループ内のｋ個の中間スイッチ要素のうち、ｗ＋１番目以降については、ＷＳＮＢ条件と同様に、Ｒ個の全てのグループに配信する。さらに、ｉ番目の入力スイッチ要素において、全てのグループのｙ番目（ｗ≧ｙ≧１）の中間スイッチ要素の集合Ｄ（ｉ，ｙ）は、上記の記載から配信先を削減したことにより、Ｄ（ｉ，ｙ）＝｛Ｍ（ｉ，１，ｙ），Ｍ（ｉ，２，ｙ），…Ｍ（ｉ，Ｒ−１，ｙ）｝で要素数｜Ｄ（ｉ，ｙ）｜はＲ−１となるが、このとき、「全ての（ｉ，ｙ）に対し、同一の中間スイッチ要素の集合を使用するものは、最大でＲ−１組である」とする。また、ｉ番目の入力スイッチ要素において、全てのグループのｙ’番目（ｋ≧ｙ’＞ｗ）がある場合、その中間スイッチ要素の集合Ｄ（ｉ，ｙ’）は、従前通り、Ｄ（ｉ，ｙ’）⊇｛Ｍ（ｉ，１，ｙ’），Ｍ（ｉ，２，ｙ’），…Ｍ（ｉ，Ｒ，ｙ’）｝で、要素数｜Ｄ（ｉ，ｙ’）｜は少なくともＲである。Ｒ番目以外のグループはｋ個の中間スイッチ要素を有することから、上記式（１）には変更がない。上記式（５）は、式（２５）に置き換わる。
【０２５１】
ＷＳＮＢ条件に記載の手続きと同様に、この条件においても、入力ステージにおけるルーティング処理は必ず成功する。また、出力スイッチ要素のそれぞれは、以下の条件Ｃまたは条件Ｄを満たすものとする。
【０２５２】
〔条件Ｃ〕．その出力スイッチ要素が個々の中間スイッチ要素に接続しているリンクの帯域（ｎ3,j×ｓ3,j）と、上記の条件Ｂを使用する全ての入力スイッチ要素の中で個々の中間スイッチ要素への接続リンクの帯域のなかで最大の帯域ｍａｘ（ｎ2,i×ｓ2,i）とを比較する。（ｎ3,j×ｓ3,j）＜ｍａｘ（ｎ2,i×ｓ2,i）の場合には、中間スイッチ要素と出力スイッチ要素との間の迂回路が入力スイッチ要素と中間スイッチ要素の間の配信経路に比べて細く十分でない。そのため、条件Ｂでの配信先グループ数Ｒ−１を考慮した出力数にとどめる。その出力スイッチ要素は上記式（２）に代わり、式（２６）に置き換わる。
ｎ4,j×ｓ4,j≦（Ｒ−１）×ｎ3,j×ｓ3,j、かつｄ4,j≦（Ｒ−１）×ｄ3,j
式（２６）
また、上記式（８）は、中間ステージにおける中間スイッチ要素数が削減されたため、出力ステージにおけるｊ番目の出力スイッチ要素では、
ｎ3,j×（Ｒ×ｋ−ｗ）≦ｐ5,j
式（２７）
に置き換わる。全ての入力ストリームが少なくともＲ−１通りの迂回路を有し、また出力スイッチ要素からの出力は、Ｒ−１通りの迂回路で全ての入力をカバーすることができる範囲の帯域に抑えられているため、この条件Ｃを満たす出力スイッチ要素は、ＷＳＮＢ条件を満たす（再配置なしにノンブロッキングでの配信が可能である）。
【０２５３】
〔条件Ｄ〕．（ｎ3,j×ｓ3,j）≧ｍａｘ（ｎ2,i×ｓ2,i）の場合には、上記式（２）を満たす。また、中間ステージにおける中間スイッチ要素数が削減されたため、条件Ｃと同様に、出力ステージにおけるｊ番目の出力スイッチ要素では、上記式（２７）を満たす。
【０２５４】
以上の条件をまとめると、本発明に従ったＲＮＢ条件を満たすネットワーク構成は、中間ステージがｍ＝（Ｒ×ｋ−ｗ）個（ｋ≧ｗ≧１）の中間スイッチ要素を有することを条件に、以下の不等式を満たす解を有する。
【０２５５】
入力ステージにおけるｉ番目の入力スイッチ要素では、条件Ａに従う入力ステージにおけるルーティング処理を行う場合は、
【０２５６】
【数３２】
0006795172.tif 000037
【０２５７】
、かつ、
【０２５８】
【数３３】
0006795172.tif 000038
【０２５９】
を満たし、条件Ｂに従う入力ステージにおけるルーティング処理を行う場合は、上記式（１）を満たす。
【０２６０】
出力ステージにおけるｉ番目の出力スイッチ要素では、（ｎ3,j×ｓ3,j）＜ｍａｘ（ｎ2,i×ｓ2,i）の場合には、
ｎ4,j×ｓ4,j≦（Ｒ−１）×ｎ3,j×ｓ3,j、かつｄ4,j≦（Ｒ−１）×ｄ3,j
式（３０）
を満たし、（ｎ3,j×ｓ3,j）≧ｍａｘ（ｎ2,i×ｓ2,i）の場合には、上記式（２）を満たす。
【０２６１】
出力ステージ全体において、上記式（３）を満たし、入力ステージにおけるｉ番目の入力スイッチ要素では、上記式（４）を満たし、入力ステージにおけるｉ番目の入力スイッチ要素では、中間スイッチ要素数を減じ、上記式（２５）を満たす。
【０２６２】
中間スイッチ要素の全ての帯域幅ｘのリンクにおいて、上記式（６）を満たし、中間スイッチ要素の全ての帯域幅ｙのリンクにおいて、上記式（７）を満たし、出力ステージにおけるｊ番目の出力スイッチ要素では、中間スイッチ要素数を減じ、上記式（２７）を満たす。
【０２６３】
出力ステージにおけるｊ番目の出力スイッチ要素では、上記式（９）を満たし、中間スイッチ要素において、リンク帯域幅を正規化する場合、中間スイッチ要素において、上記式（１０）および式（１１）を満たす。
【０２６４】
上述した条件Ｄでは、全ての入力ストリームに対してノンブロッキング性を満たすかどうかは自明でない。そこで、最後に、全ての入力スイッチ要素が条件ＡおよびＢのいずれかを満たす場合、条件Ｄを満たす出力スイッチ要素が全ての入力ストリームに対してＲＮＢ条件を満たすことを以下に示す。
【０２６５】
ある出力スイッチにおいて、現在配信中の全ての入力ストリームに対し、それらの入力の配信先集合の和集合をＤ0とする。新たにその出力スイッチ要素から配信しようとする入力ストリームの配信先集合をＤ1とする。定義により、｜Ｄ0｜≧Ｒ−１，｜Ｄ1｜≧Ｒ−１であるため、｜Ｄ0∪Ｄ1｜≧Ｒ−１が成立する。
【０２６６】
｜Ｄ0∪Ｄ1｜≧Ｒかつ｜Ｄ1｜≧Ｒの場合は、｜Ｄ1｜≧Ｒであることから、少なくともＲ通りの迂回路により、それに見合う出力をカバーしているため、この出力スイッチ要素はＷＳＮＢ条件を満たしている。すなわち、Ｒ通りの迂回路のいずれかを使用して、新規の配信が可能である。
【０２６７】
｜Ｄ0∪Ｄ1｜＝Ｒ−１の場合、その出力スイッチ要素が出力している全ての入力ストリームが同一の中間スイッチ要素の組に配信されている。条件Ｂの定義により、このような配信経路の組（ｉ，ｙ）は最大でＲ−１組である。また、条件Ｄにより、（ｎ3,j×ｓ3,j）≧ｍａｘ（ｎ2,i×ｓ2,i）である。従って、最大でＲ−１組の入力ストリームをＲ−１個の中間スイッチ要素による迂回路を使用して接続し、中間スイッチ要素から出力スイッチ要素へのリンクはそれに見合う帯域を有することから、ＷＳＮＢ条件が成立し、再配置なしにノンブロッキングでの配信が可能である。
【０２６８】
｜Ｄ0∪Ｄ1｜≧Ｒ、｜Ｄ1｜＝Ｒ−１の場合、Ｄ1に属する中間スイッチ要素からのリンクのすべてが、この出力スイッチ要素の既存の配信によって占有されているケースが存在する場合がある。しかし、この場合、｜Ｄ0∪Ｄ1｜≧Ｒ、｜Ｄ1｜＝Ｒ−１の関係から、｜Ｄ0｜≧Ｒが成立する。従って、Ｄ0およびＤ1の差集合（Ｄ0−Ｄ1：Ｄ0の中間スイッチ要素のうち、Ｄ1に属さない中間スイッチ要素の集合）に属する中間スイッチ要素を迂回路として使用することができる既存の配信が必ず存在する。そこで、そのような既存の配信の経路をＤ1内の中間スイッチ要素からＤ0−Ｄ1内の中間スイッチ要素に変更し（再配置）、利用可能になったＤ1内の中間スイッチ要素を新たな配信に割り当てることができる。従って、この出力スイッチ要素に対してはＲＮＢ条件が成立する。
【０２６９】
以上のように、すべての入力スイッチ要素が条件Ａまたは条件Ｂを満たすとき、条件ＣおよびＤにより、全ての出力スイッチ要素において、全ての入力ストリームに対してマルチキャストでのノンブロッキング性を有することが示された。
【０２７０】
ここで、中間スイッチ要素を削減した場合の入力ステージにおける例をいくつか示す。ｋ＝３、Ｒ＝３、ｗ＝３の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を表５に示す。この例では、ｗ＝３であるので、中間スイッチ要素の数は３×３−３＝６に削減されている。上記条件Ａを選択した場合、
【０２７１】
【数３４】
0006795172.tif 000039
であるため、この場合の入力スイッチ要素は、各グループ内で２個の中間スイッチ要素を使用することができる。条件Ｂを選択した場合、Ｒ＝３番目のグループは、ｋ−ｗ＝０個の中間スイッチ要素を有する。すなわち、３番目のグループは存在しない。
【０２７２】
【表５】
0006795172.tif 000040
【０２７３】
表５  ｋ＝３、Ｒ＝３、ｗ＝３の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素ＭＳ−ｚへの割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０２７４】
表５において、ＩＳ−１からＩＳ−１０は、条件Ｂを選択している。Ｄ（１，１）（ＩＳ−１の１番目）に着目すると、Ｄ（１，１）＝｛１，２｝（ＭＳ−１，ＭＳ−２が配信先）となっている。この中間スイッチ要素の組｛１，２｝を値として有するＤ（ｉ，ｙ）は、Ｄ（１，１）およびＤ（６，１）のみである。同様に、Ｄ（ｉ，ｙ）＝Ｄ（ｉ＋５，ｙ），５≧ｙ≧１が全て成立しており、Ｄ（ｉ，ｙ）の要素数｜Ｄ（ｉ，ｙ）｜がＲ−１＝２である全ての（ｉ，ｙ）に対し、同一の集合を使用するものは、最大でＲ−１＝２組である、という条件が成立している。入力スイッチ要素が条件Ｂを選択し、配信先集合の要素数がＲ−１である入力ストリームに対し、表５の項目に網掛けがされている。ＩＳ−１１は条件Ａを選択している。各グループ内で２個のスイッチを使用し３個目は存在しないため、１が３グループ、２が３グループに配信されている。
【０２７５】
６個の中間スイッチから２個を選ぶ組合せは、
【０２７６】
【数３５】
0006795172.tif 000041
通り存在する。表５は、それぞれを条件Ｂの定義に従い、Ｒ−１＝２回使用し、それぞれの入力スイッチ要素において、ｗ＝３回使用する場合の組合せの解であるので、１５×２／３＝１０個の入力スイッチ要素までが条件Ｂに従った配信を行うことができるから、以下の表７のＩＳ−１１以降、入力スイッチ要素を追加する場合は、すべて条件Ａを選択することになる。ＩＳ−１１を含め、条件Ａを選択する場合には、６個のスイッチのいずれか３個を１にし、いずれか３個を２にするかは任意に選択してもよい。なお、ノンブロッキング条件を満たすために、ＩＳ−１１以降の入力スイッチ要素では、入力ポートの使用数に制約がある。しかしながら、この制約によって、マルチキャストに対するノンブロッキング条件（ＲＮＢ条件）が満足されているため、出力ステージでは、出力ステージのスイッチ数ｒ2によらず、全ての出力で任意のマルチキャストを行うことができる。
【０２７７】
次に、ｋ＝３、Ｒ＝３、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を表６に示す、この例では、ｗ＝２であるので、中間スイッチ要素の個数は３×３−２＝７に削減されている。
【０２７８】
【表６】
0006795172.tif 000042
【０２７９】
表６  ｋ＝３、Ｒ＝３、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０２８０】
表６では、ＩＳ−１からＩＳ−２１は条件Ｂを選択しており、Ｄ（ｉ，１）、Ｄ（ｉ，２）は配信先グループ数が削減されている。Ｄ（ｉ，３）については、配信先グループ数を削減せず｜Ｄ（ｉ，３）｜＝３である。Ｄ（１，１）（ＩＳ−１の１番目）に着目すると、Ｄ（１，１）＝｛１，２｝（ＭＳ−１、ＭＳ−２が配信先）となっている。この中間スイッチ要素の組｛１、２｝を値として有するＤ（ｉ，ｙ）は、Ｄ（１，１）およびＤ（８，１）のみである。同様に、Ｄ（ｉ，ｙ）の要素数｜Ｄ（ｉ，ｙ）｝がＲ−１＝２である全ての（ｉ，１）、（ｉ，２）に対し、同一の集合を使用するものは、最大でＲ−１＝２組である、という条件が成立している。
【０２８１】
ＩＳ−２２は条件Ａを選択している。各グループ内で２個のスイッチを使用し３個目は存在しないため、「１」が３グループ、「２」が３グループに配信されている。７個の中間スイッチ要素から２個を選ぶ組合せは、
【０２８２】
【数３６】
0006795172.tif 000043
通り存在する。表６は、それぞれを条件Ｂの定義に従って、全ての入力ステージにおいてＲ−１＝２回使用し、それぞれの入力スイッチ要素において、ｗ＝２個の入力ストリームに対していずれかの組合せを使用した場合の解であるので、２１×２／２＝２１個の入力スイッチ要素までが条件Ｂによる配信を行うことができる。よって、以下の表６に示すＩＳ−２２以降、入力スイッチ要素を追加する場合は、すべて条件Ａを選択することになる。ＩＳ−２２を含め、条件Ａを選択する場合には、７個のスイッチのいずれか３個を１にし、いずれか３個を２にするかは任意に選択してもよい。
【０２８３】
条件Ａを選択した場合、条件の式を満たす範囲で、入力ストリームの配信先をＲ＋１個に増やし、中間スイッチ要素の間で負荷分散を行ってもよい。表８の例では、１番目、２番目の入力ストリームともに、少なくともＲ＝３個に配信しているが、中間スイッチ要素の数が７個であるため、ＭＳ−７は未使用となっている。これを１番目、または、２番目、またはその双方の入力ストリームに多重度を考慮して配分してもよい。出力ステージにおけるルーティング時の判断を簡単にするため、未使用、あるいは、１番目、２番目のいずれかに固定で割り当ててもよい。
【０２８４】
次に、Ｒ＝２の例について述べる。条件Ｂの定義に従うと、Ｒ−１＝１個のスイッチを選択する組を最大でＲ−１＝１回しか使用することができない。ここでは全てのｋ（ｋ＞１）について成立する例をあげる。
【０２８５】
ケース１．中間スイッチ要素の削減数ｗ＝ｋ、すなわち、中間スイッチ要素の数ｍ＝２ｋ−ｋ＝ｋとし、１つの入力スイッチ要素のみが条件Ｂとなり、残りを条件Ａとする。
【０２８６】
ケース２．中間スイッチ要素の削減数ｗ＝２、すなわち、中間スイッチ要素の数ｍ＝２ｋ−２＝２（ｋ−１）とし、ｋ−１個の入力スイッチ要素が条件Ｂとなり、残りを条件Ａとする。
【０２８７】
ケース３．中間スイッチ要素の削減数ｗ＝１、すなわち、中間スイッチ要素の数ｍ＝２ｋ−１とし、２ｋ−１個の入力スイッチ要素が条件Ｂとなり、残りを条件Ａとする。
【０２８８】
ここで、ｋ＝２、３、４の場合の実例をしめす。（これ以外のｋについても上記ケース１、ケース２およびケース３は容易に表に示すことができるため、省略する）
【０２８９】
表７は、ｋ＝２、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記のケース１およびケース２に相当し、ＩＳ−１のみが全ての入力を使用することができる。表８はｋ＝２、Ｒ＝２、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記のケース３に相当する。ＩＳ−１、ＩＳ−２、ＩＳ−３が条件Ｂを選択し、ＩＳ−４、ＩＳ−５、ＩＳ−６が条件Ａを選択している。条件Ａを選択することができる入力スイッチ要素数には制限はない。ＩＳ−４、ＩＳ−５、ＩＳ−６では、入力ストリームを少なくとも２個のグループに配信すればよい。ここでは、３個の中間スイッチ要素を使用して３グループに配信し、出力ステージでの選択枝を増やして負荷分散を図っている。
【０２９０】
【表７】
0006795172.tif 000044
【０２９１】
表７  ｋ＝２、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０２９２】
【表８】
0006795172.tif 000045
【０２９３】
表８  ｋ＝３、Ｒ＝３、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０２９４】
表９は、ｋ＝３、Ｒ＝２、ｗ＝３の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース１に相当する。入力スイッチ要素ＩＳ−１のみが全ての中間スイッチ要素の全ての入力ポートを使用することができる。その他の入力スイッチ要素は、条件Ａを選択しており、条件Ａを選択することができる入力スイッチ要素の数に制限はない。ここでは、３個の中間スイッチ要素を使用して３グループに配信し、出力ステージでの選択枝を増やして負荷分散を図っている。
【０２９５】
【表９】
0006795172.tif 000046
【０２９６】
表９  ｋ＝３、Ｒ＝２、ｗ＝３の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０２９７】
表１０は、ｋ＝３、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース２に相当する。入力スイッチ要素ＩＳ−１およびＩＳ−２が全ての中間スイッチ要素の入力ポートを使用することができる。その他の入力スイッチ要素は条件Ａを選択している。条件Ａを選択することができる入力スイッチ要素の数に制限はない。
【０２９８】
【表１０】
0006795172.tif 000047
【０２９９】
表１０  ｋ＝３、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３００】
表１１は、ｋ＝３、Ｒ＝２、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース３に相当する。入力スイッチ要素ＩＳ−１、ＩＳ−２およびＩＳ−３が条件Ｂを選択しており、入力スイッチ要素ＩＳ−４、ＩＳ−５およびＩＳ−６が条件Ａを選択している。条件Ａを選択することができる入力スイッチ要素の数に制限はない。
【０３０１】
【表１１】
0006795172.tif 000048
【０３０２】
表１１  ｋ＝３、Ｒ＝２、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３０３】
表１２は、ｋ＝４、Ｒ＝２、ｗ＝４の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース１に相当する。入力スイッチ要素ＩＳ−１のみが全ての中間スイッチ要素の入力ポートを使用することができる。その他の入力スイッチ要素は、条件Ａを選択しており、条件Ａを選択することができる入力スイッチ要素の数に制限はない。
【０３０４】
【表１２】
0006795172.tif 000049
【０３０５】
表１２  ｋ＝４、Ｒ＝２、ｗ＝４の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３０６】
表１３は、ｋ＝４、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース２に相当する。入力スイッチ要素ＩＳ−１、ＩＳ−２およびＩＳ−３が全ての中間スイッチ要素の入力ポートを使用することができる。その他の入力スイッチ要素は、条件Ａを選択している。条件Ａを選択することができる入力スイッチ要素の数に制限はない。
【０３０７】
【表１３】
0006795172.tif 000050
【０３０８】
表１３  ｋ＝４、Ｒ＝２、ｗ＝２の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３０９】
表１４は、ｋ＝４、Ｒ＝２、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示しており、上記ケース３に相当する。入力スイッチ要素ＩＳ−１、ＩＳ−２、…、ＩＳ−７が条件Ｂを選択しており、入力スイッチ要素ＩＳ−８が条件Ａを選択している。条件Ａを選択することができる入力スイッチ要素の数に制限はない。
【０３１０】
【表１４】
0006795172.tif 000051
【０３１１】
表１４  ｋ＝４、Ｒ＝２、ｗ＝１の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３１２】
次に、Ｒ＝４の例について述べる。表１５は、ｋ＝４、Ｒ＝４、ｗ＝４の場合の配信先集合Ｄ（ｉ，ｙ）の割り当ての一部の例を示す。入力スイッチ要素ＩＳ−１乃至ＩＳ−４３は、全て条件Ｂを選択している。グループ数はＲ−１＝３であり、グループ内にはｋ＝４個のスイッチ要素が存在する。１２個の中間スイッチ要素から３個を選ぶ組合せは２２０通りある。表１５は、各入力スイッチでそのうちの異なる４通りずつを使用しており、入力スイッチ要素ＩＳ−１乃至ＩＳ−４３は、入力ストリームの配信先集合Ｄ（ｉ，ｙ）（４３≧ｉ≧１、４≧ｙ≧１）において、全ての集合が異なっている。条件Ｂの定義では、そのような集合をＲ−１＝３回使用してもよいので、表１５に示された組み合わせのみを使用した場合でも、４３×３＝１２９個の入力スイッチ要素までが条件Ｂを選択することができる。具体的には、Ｄ（ｉ，ｙ）＝Ｄ（ｉ＋４３，ｙ）＝Ｄ（ｉ＋８６，ｙ）として表１５を拡張することで、１２９個の入力スイッチ要素で条件Ｂを選択できる。
【０３１３】
【表１５】
0006795172.tif 000052
【０３１４】
表１５  ｋ＝４、Ｒ＝４、ｗ＝４の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当て（各列がＩＳ−ｉ、各項目がｙ）
【０３１５】
このように、ｋおよびＲの値が増加すると、条件Ｂを満たす配信先集合の組合せの数は飛躍的に増加する。本発明の実施例は上記表で示された例に限定されない。
【０３１６】
次に、本発明における経路選択の例を説明する。入力ステージにおけるルーティング処理は上述したことと同様に、常に成功する。そこで、出力ステージにおけるルーティング処理について具体的に再配置が必要となる例を使用して説明する。
【０３１７】
まず、ｋ＝２、Ｒ＝２、ｗ＝１の例で、出力ステージにおける多重度ｄ4,j＝４の場合を示す。ｄ4,j＝４であるから各出力スイッチ要素は、４本までのストリームを出力することができる。Ｒ＝２であるから、各中間スイッチ要素からは、最大で２本（＝４／２）までのストリームを受信することができる。表１６は、上記表８に基づいて、ある出力スイッチ要素ＯＳ−ｊに対して、それぞれの中間スイッチ要素から配信されているストリームを示す。ＯＳ−ｊの状態１および状態２内の２つの列は、各行に記されたそれぞれの中間スイッチ要素から受信している中間スイッチ要素あたり２本のストリームを表す。ストリームＡ１、Ａ２は、入力スイッチ要素ＩＳ−３のＤ（３，２）から配信しているストリームである。Ｄ（３，２）＝｛ＭＳ−１，ＭＳ−２｝であるため、表１６の状態１では、Ａ１をＭＳ−１から、Ａ２を中間スイッチ要素ＭＳ−２から配信している。ストリームＡ３は入力スイッチ要素ＩＳ−１のＤ（１，１）から配信している。Ｄ（１，１）＝｛ＭＳ−１｝であるため、Ａ３は中間スイッチ要素ＭＳ−１からしか配信することができない。この時点で、中間スイッチ要素ＭＳ−１からはＡ１、Ａ３の２本のストリームを配信しているため、これ以上のストリームを中間スイッチ要素ＭＳ−１からは配信することはできない。
【０３１８】
ここで、入力スイッチ要素ＩＳ−１のＤ（１，１）に属する第４のストリームＡ４を出力スイッチ要素ＯＳ−ｊから出力することを仮定する。現在配信しているストリームの配信先集合の和（Ｄ0）の要素数は｜Ｄ0｜＝｜Ｄ（３，２）∪Ｄ（１，１）｜＝２（＝Ｒ）であり、新規に配信しようとしているストリームの配信先集合（Ｄ1）の要素数は｜Ｄ1｜＝｜Ｄ（１，１）｜＝１（＝Ｒ−１）である。従って、前述のように、このような競合のケースでは、Ｄ0とＤ1の差集合Ｄ0−Ｄ1＝（Ｄ（３，２）∪Ｄ（１，１））−Ｄ（１，１）＝｛ＭＳ−２｝に迂回路が存在し、かつ、Ｄ1＝｛ＭＳ−１｝から配信中のストリームが必ず存在する。表１６では、ストリームＡ１が該当する。そこで、Ａ１の配信経路を中間スイッチ要素ＭＳ−２に移し、空いた経路を使用して、中間スイッチ要素ＭＳ−１から新規にＡ４を配信する。この操作の結果が状態２である。これで出力スイッチ要素ＯＳ−ｊは多重度４で許容できる出力を全て使用しているため、既存配信を消去しない限り、新規の配信をすることができない。
【０３１９】
【表１６】
0006795172.tif 000053
【０３２０】
表１６  ｋ＝２、Ｒ＝２、ｗ＝１、ｄ4,j＝４の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｊ番目の出力スイッチ要素の状態との関係
【０３２１】
次に、ｋ＝３、Ｒ＝３、ｗ＝３の例で、出力側の多重度ｄ4,j＝３の場合を示す。ｄ4,j＝３であるから各出力スイッチ要素は３本までのストリームを出力することができる。Ｒ＝３であるから、各中間スイッチ要素からは、最大で１本（＝３／３）までのストリームを受信することができる。表１７は、表５に基づいて、ある出力スイッチ要素ＯＳ−ｊに対して、それぞれの中間スイッチ要素から配信されているストリームを示す。ストリームＡ１は、入力スイッチ要素ＩＳ−１のＤ（１，１）から配信しているストリームである。Ｄ（１，１）＝｛ＭＳ−１，ＭＳ−２｝であるため、表１７の状態１では、Ａ１を中間スイッチ要素ＭＳ−１から配信している。ストリームＡ２は、入力スイッチ要素ＩＳ−２のＤ（２，１）から配信している。Ｄ（２，１）＝｛ＭＳ−２，ＭＳ−３｝であるため、Ａ２は中間スイッチ要素ＭＳ−３から配信している。
【０３２２】
ここで、入力スイッチ要素ＩＳ−３のＤ（３，１）に属する第３のストリームＡ３を出力スイッチ要素ＯＳ−ｊから出力することを仮定する。Ｄ（３，１）＝｛ＭＳ−１，ＭＳ−３｝であり、中間スイッチ要素ＭＳ−１はストリームＡ１によって、中間スイッチ要素ＭＳ−３はストリームＡ２によって使用されているため、この状態では、Ａ３を配信することができない。
【０３２３】
現在配信しているストリームの配信先集合の和（Ｄ0）の要素数は｜Ｄ0｜＝｜Ｄ（１，１）∪Ｄ（２，１）｜＝３（＝Ｒ）であり、新規に配信しようとしているストリームの配信先集合（Ｄ1）の要素数は｜Ｄ1｜＝｜Ｄ（３，１）｜＝２（＝Ｒ−１）である。従って、前述のように、このような競合のケースでは、Ｄ0とＤ1の差集合Ｄ0−Ｄ1＝（Ｄ（１，１）∪Ｄ（２，１））−Ｄ（３，１）＝｛ＭＳ−２｝に迂回路が存在し、かつ、Ｄ1＝｛ＭＳ−１，ＭＳ−３｝から配信中のストリームが必ず存在する。表１７では、ストリームＡ１およびＡ２がともに該当する。そこで、Ａ１を再配置の対象に選択し、配信経路をＭＳ−２に移し、空いたルートを使用して、中間スイッチ要素ＭＳ−１から新規にＡ３を配信する。この結果が状態２である。これで出力スイッチ要素ＯＳ−ｊは多重度３で許容できる出力を全て使用しているため、既存配信を消去しない限り、新規の配信をすることができない。
【０３２４】
【表１７】
0006795172.tif 000054
【０３２５】
表１７  ｋ＝３、Ｒ＝３、ｗ＝３、ｄ4,j＝３の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｊ番目の出力スイッチ要素の状態との関係
【０３２６】
以下では、ＲＮＢ条件を満たすネットワークでの経路設定を定式化して説明する。
【０３２７】
入力ステージにおけるルーティング処理Ｍ（ｉ，ｘ，ｙ）の割り当てについては、ＲＮＢ条件を満たすように行う。
【０３２８】
次に、図１０のフローチャートを参照して、ＲＮＢ条件を満たすネットワークでの出力ステージにおけるルーティング処理を説明する。
【０３２９】
出力ステージにおけるｊ番目の出力スイッチ要素では、入力ストリームＩ1（ｉ，ａ1）に対するマルチキャスト要求における新たな出力先の一つＯ2（ｊ，ａ4）に対し、識別番号ａ4から使用する出力リンクＬOを求める（ステップＳ１００１）。
【０３３０】
集合ＦＯj内でこの同一出力リンクで使用されている出力ストリームが、出力リンクＬOを収容することができる帯域幅の上限に達している場合（ステップＳ１００２でＹｅｓ）、このマルチキャスト要求を受理せず、ステップＳ１０１６に遷移する。そうでない場合（ステップＳ１００２でＮｏ）、後続のステップＳ１００３に遷移する。
【０３３１】
前述の出力ステージにおけるｊ番目の出力スイッチ要素で、前述の入力ストリームＩ1（ｉ，ａ1）が集合ＦＯj内に存在する場合は（ステップＳ１００３でＹｅｓ）、前述の識別番号ａ4をストリームＩ1（ｉ，ａ1）の登録に加え（ステップＳ１０１７）、ステップＳ１０１５に遷移する。そうでない場合（ステップＳ１００３でＮｏ）、後続のステップＳ１００４に遷移する。
【０３３２】
前述の入力ストリームＩ1（ｉ，ａ1）に対応する入力ステージにおけるルーティング処理の結果を取得し、その結果に含まれる中間スイッチ要素のリストを抽出する。例えば、入力ステージにおけるルーティング処理の結果が、｛Ｉ2（ｉ，Ｍ（ｉ，１，ｙ1），ａ2,1），Ｉ2（ｉ，Ｍ（ｉ，２，ｙ2），ａ2,2），…，Ｉ2（ｉ，Ｍ（ｉ，Ｒ，ｙR），ａ2,R）｝である場合、中間スイッチ要素のリストは｛Ｍ（ｉ，１，ｙ1），Ｍ（ｉ，２，ｙ2），…，Ｍ（ｉ，Ｒ，ｙR）｝である（ステップＳ１００４）。
【０３３３】
ステップＳ１００４で抽出した、入力ストリームＩ1（ｉ，ａ1）に対応する中間スイッチ要素のリストＤ（ｉ，ｙ）の要素数｜Ｄ（ｉ，ｙ）｜がＲ−１の場合（ステップＳ１００５でＹｅｓ）、ステップＳ１００６に遷移する。そうでない場合（ステップＳ１００５でＮｏ）、後続のステップＳ１００７に遷移する。
【０３３４】
ステップＳ１００７では、前述の出力ステージにおけるｊ番目の出力スイッチ要素と、上記リストに含まれるＲ個の中間スイッチ要素との間のリンクＲ×ｎ3,j本について、帯域幅と多重度が上限に達していない伝送可能なリンクを１本選択する。そして、そのリンクを保持する中間スイッチ要素識別番号Ｍ（ｉ，ｘ，ｙx）、および中間スイッチ要素の出力ストリームの識別番号ａ3を決定する（ステップＳ１００８）。
【０３３５】
ステップＳ１００６では、「上記リストに含まれるＲ−１個の中間スイッチ要素との間のリンク（Ｒ−１）×ｎ3,j本について、帯域幅と多重度が上限に達していない伝送可能なリンクを１本選択する」ことができるか判定する。Ｙｅｓの場合、ステップＳ１００７に遷移し、Ｎｏの場合、ステップＳ１００９に遷移する。は
【０３３６】
ステップＳ１００９では、再配置の対象となるストリーム、および迂回先の中間スイッチ要素を選択する。
【０３３７】
具体的には、ｊ番目の出力スイッチ要素の入出力関係ＦＯjに含まれるすべての入力に対する配信先中間スイッチ要素のリストの和集合をＤ0とし、ステップＳ１００４で抽出した中間スイッチ要素のリストをＤ1とする。Ｄ0とＤ1の差集合Ｄ0−Ｄ1に迂回路が存在し、Ｄ1から配信中のストリームの集合を抽出する。その中から新規に配信予定の入力ストリームＩ1（ｉ，ａ1）と置換可能なストリームＩ1（ｉ’，ａ1’）を少なくとも１つ選択し、それぞれについて迂回先の中間スイッチ要素Ｍ（ｉ’，ｘ’，ｙx’）を選択する。このとき、ストリームＩ1（ｉ’，ａ1’）の出力は出力リンクＬ0’を使用しているものとする。
【０３３８】
次に、再配置対象の入力ストリームの現在の配信を削除する（ステップＳ１０１０）。具体的には、再配置対象である入力ストリームＩ1（ｉ’，ａ1’）に対し、図７で説明したステップＳ７０５乃至ステップＳ７１１を実行して、再配置対象である入力ストリームＩ1（ｉ’，ａ1’）を一時的に削除する。ここで、ステップＳ７０８乃至ステップＳ７１１を省略して、入力ステージにおける経路設定と出力ステージにおける経路設定とを分離してもよい。
【０３３９】
次に、再配置対象の入力ストリームを再配置に基づき再登録する（ステップＳ１０１１）。具体的には，迂回先の中間スイッチ要素識別番号Ｍ（ｉ’,ｘ’，ｙx’）からの出力ストリームの識別番号ａ3’を決定し、図６におけるステップＳ６０６乃至ステップＳ６１０の処理によって、再配置対象である入力ストリームＩ1（ｉ’，ａ1’）が新たに迂回先の中間スイッチ要素Ｍ（ｉ’，ｘ’，ｙx’）の出力ストリームａ3’を使用して出力リンクＬ0’に配信されていることを集合ＦＯj内および集合
【０３４０】
【数３７】
0006795172.tif 000055
内に登録し、出力リンクＬ0’からの配信を継続する。これで、入力ストリームＩ1（ｉ，ａ1）を配信可能とする迂回路が確保できたため、ステップＳ１００６でのＹｅｓの場合の分岐処理を終え、ステップＳ１００７に戻り入力ストリームＩ1（ｉ，ａ1）に対する処理を継続する。
【０３４１】
ステップＳ１０１２では、前述の出力ステージにおけるｊ番目の出力スイッチ要素では、入力ストリームＩ1（ｉ，ａ1）が、中間スイッチ要素識別番号Ｍ（ｉ, ｘ，ｙx）、および中間スイッチ要素の出力ストリームの識別番号ａ3で示されるＯ1（Ｍ（ｉ，ｘ，ｙx），ｊ，ａ3）を入力源とし、Ｏ2（ｊ，ａ4,1）を出力することを集合ＦＯj内に新規に登録する。そして、前述の出力リンクＬ0からの出力設定を行う（ステップＳ１０１３）。
【０３４２】
ステップＳ１００６およびステップＳ１００９で選択した中間スイッチ要素Ｍ（ｉ,ｘ，ｙx）において、ステップＳ１００３およびステップＳ１００４の結果、すなわち、入力ストリームＩ1（ｉ，ａ1）がＩ2（ｉ，Ｍ（ｉ，ｘ，ｙx）ａ2,x）を入力源とし、Ｏ1（Ｍ（ｉ，ｘ，ｙx），ｊ，ａ3）を新たな出力に加えたことを、
【０３４３】
【数３８】
0006795172.tif 000056
【０３４４】
に登録する（ステップＳ１０１４）。そして、出力ストリームＯ1（Ｍ（ｉ,ｘ，ｙx），ｊ，ａ3）を出力する設定を行い、出力リンクＬOからの迂回先からの伝送を開始し、Ｏ2（ｊ，ａ4）に対する処理を終了する（ステップＳ１０１５）。
【０３４５】
その後、新たに配信要求があった入力ストリームに対し、上記ステップＳ１００１乃至ステップＳ１０１５を実行する（ステップＳ１０１６）。
【０３４６】
別の実施形態として、ステップＳ１００６でＮｏと判定された場合、上記ステップＳ１００９、およびステップＳ１０１１（迂回路中間スイッチ要素への再配置対象の入力ストリームの配信の追加）を実行してから、ステップＳ１０１０（再配置対象の現在の配信を削除）を実行してもよい。この場合、その後、新たに配信要求があった入力ストリームに対し、配信中の中間スイッチ要素での新規配信を追加し、出力スイッチ要素での切り替えを行う。
【０３４７】
一実施形態では、出力ステージにおけるルーティング処理で配信元の中間スイッチ要素を選択するときに、各グループの配信数をグループ間で平準化するように選択することができる。このような操作は、特定の中間スイッチ要素に配信が集中することを回避し、｜Ｄ（ｉ，ｙ）｜がＲ−１である他の入力との干渉を抑制することができる。これにより、多重度が大きい時には、再配置の可能性を低減させることができる。具体的な例として、表１６の状態１において、ストリームＡ１を中間スイッチ要素ＭＳ−１から配信し、ストリームＡ２を同じＤ（３，２）に属する中間スイッチ要素ＭＳ−２から配信することが該当する。状態１では、ストリームＡ３は再配置の必要なく配信可能であったが、仮に、Ａ１、Ａ２の両方をＭＳ−１から配信するように設定したとすると、その後、ストリームＡ３をＤ（１，１）から配信しようとした段階で再配置が必要になる。 
【０３４８】
ここまで、片方向のリンクを使用した３ステージのＣｌｏｓ型ネットワークにおいてＲＮＢ条件を満たす構成方法を説明したが、上述したのと同様に、双方向伝送可能なスイッチ要素を使用して、入力ステージの機能と出力ステージの機能を同一のスイッチ要素に統合することができる。ＷＳＮＢ条件ｍ＝Ｒ×ｋに代わり、ＲＮＢ条件ｍ＝Ｒ×ｋ−ｗを使用した場合は、以下のようになる。
【０３４９】
入出力ステージにおけるｉ番目の入出力スイッチ要素では、入力ステージにおけるルーティング処理として、条件Ａに従うルーティング処理を選択する場合に、
【０３５０】
【数３９】
0006795172.tif 000057
【０３５１】
、かつ
【０３５２】
【数４０】
0006795172.tif 000058
【０３５３】
を満たし、条件Ｂを選択する場合、上記式（１２）を満たす。
【０３５４】
入出力ステージにおけるｊ番目の入出力スイッチ要素では、（ｎ’j×ｓ’j）＜ｍａｘ（ｎ’i×ｓ’i）（ｉ≠ｊ）の場合、
ｎ4,j×ｓ4,j≦（Ｒ−１）×ｎ’i×ｓ’i、かつｄ4,j≦(Ｒ−１)×ｄ’j
式（３３）
を満たし、（ｎ’i×ｓ’j）＝ｍａｘ（ｎ’i×ｓ’j）（ｉ≠ｊ）の場合、
ｎ4,j×ｓ4,j≦Ｒ×ｎ’i×ｓ’j、かつｄ4,j≦Ｒ×ｄ’j
式（３４）
を満たす。
【０３５５】
入出力ステージ全体においては、上記式（１４）を満たし、入出力ステージにおけるｉ番目の入出力スイッチ要素では、上記（１５）を満たし、中間スイッチ要素の全ての帯域幅ｘのリンクにおいては、上記式（１６）を満たす。
【０３５６】
帯域幅ｓ’での正規化を行った場合、中間スイッチ要素において、上記式（１７）を満たす。
【０３５７】
これまで、ｍ＝Ｒ×ｋ個の中間スイッチ要素を有するＷＳＮＢ条件を満たすネットワークから、ｗ個の中間スイッチ要素を削減して、ｍ＝Ｒ×ｋ−ｗ個の中間スイッチ要素を有するＲＮＢ条件を満たすネットワークを構成する方法を説明した。次に、ネットワークを分割することによって得られる中間スイッチ要素の部分集合にこの方法を適用する構成法について説明する。
【０３５８】
Ｒ≧４のとき、Ｒ＝Ｒ1＋Ｒ2、Ｒ1≧２、Ｒ2≧２と置き換える。この時、中間スイッチ要素数ｍについて、ｍ＝Ｒ×ｋ＝（Ｒ1＋Ｒ2）×ｋ＝Ｒ1×ｋ＋Ｒ2×ｋであるから、これは全体としてＲ通りの迂回路を有する一方で、Ｒ1個の迂回路に相当する中間スイッチ要素の部分集合を使用するネットワークとＲ2個の迂回路に相当する中間スイッチの部分集合を使用するネットワークとに分割することができることを表している。
【０３５９】
具体例として、Ｒ＝５、ｋ＝２、ｍ＝Ｒ×ｋ＝１０のケースを考える。表１８では、５つのグループに対し、ｋ＝２により、１番目、２番目の中間スイッチ要素を設定している入力ステージにおけるルーティング処理で、ｉ番目の入力スイッチ要素に対するｙ番目の中間スイッチ要素の配信先集合Ｄ（ｉ，ｙ）の割り当ての例を示している。（各入力スイッチ要素で、配信先集合Ｄ（ｉ，ｙ）は｜Ｄ（ｉ，１）｜＝５，｜Ｄ（ｉ，２）｜＝５であるから、「１」が５回、「２」が５回割り当てられる）。しかし、これは、Ｒ＝５＝２＋３と考え、Ｒ×ｋ＝（２＋３）×２＝４＋６であるから、｛ＭＳ−１，ＭＳ−２，ＭＳ−３，ＭＳ−４｝の４個の中間スイッチ要素で独立した２グループを有する部分集合（Ｇ1）と、｛ＭＳ−５，ＭＳ−６，ＭＳ−７，ＭＳ−８，ＭＳ−９，ＭＳ−１０｝のスイッチで独立した３グループを有する部分集合（Ｇ2）として扱うことと等価である。
【０３６０】
【表１８】
0006795172.tif 000059
【０３６１】
表１８  ｋ＝２、Ｒ＝５、ｍ＝１０の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｙ番目の入力スイッチ要素の状態との関係
【０３６２】
部分集合Ｇ1およびＧ2の両方に同一の入力ストリームが配信されているため、出力スイッチ要素において、個々の出力リンクごとに使用する部分ネットワークを部分集合Ｇ1およびＧ2のいずれかに固定して割り当ててもよい。すなわち、
【０３６３】
【数４１】
0006795172.tif 000060
【０３６４】
とすると、上記式（２）より、
ａ1×s4,j≦Ｒ1×ｎ3,j×ｓ3,j、かつｂ1≦Ｒ1×ｄ3,j
式（３５）
ａ2×ｓ4,j≦Ｒ2×ｎ3,j×ｓ3,j、かつｂ2≦Ｒ2×ｄ3,j
式（３６）
（ａ1＋ａ2）×ｓ4,j≦Ｒ×ｎ3,j×ｓ3,j、かつ（ｂ1＋ｂ2）≦Ｒ×ｄ3,j
式（３７）
を満たす。つまり、出力スイッチ要素の出力リンク内のａ1本およびａ2本をそれぞれ、部分集合Ｇ1およびＧ2に割り当てることによって、Ｇ1およびＧ2と各出力スイッチ要素の間の独立した部分ネットワークによって，それぞれが独立してＷＳＮＢ条件を満たす。（双方向伝送可能なリンクを使用したネットワークでは、式（１３）を元に、同じくＷＳＮＢ条件を満たしていることが判る）。
【０３６５】
そこで、表１８において、それぞれ部分集合から中間スイッチ要素を減じ、ＲＮＢ条件を独立に満たすようにする。すなわち、中間ステージ要素のスイッチ要素の全体の削減数ｗに対し、ｗ＝ｗ1＋ｗ2、（ｗ1≧０，ｗ2≧０）と分解し、
ｍ＝Ｒ×ｋ−ｗ＝（Ｒ1×ｋ−ｗ1）＋（Ｒ2×ｋ−ｗ2）
式（３８）
を満たすように、中間スイッチ要素の削減数を部分集合のそれぞれに分配する。分割したそれぞれの部分集合で、最大ｋ個までの削減が可能である。従って、全体の削減数は、２ｋ≧ｗ＞０となり、分割前に比べ削減数を増やすことができる。
【０３６６】
部分集合Ｇ1では、ｉ番目の入力スイッチ要素において全てのグループのｙ番目（ｗ1≧ｙ≧１）の中間スイッチ要素の集合Ｄ（ｉ，ｙ）のうち、Ｇ1に属する中間スイッチ要素数｜Ｄ（ｉ，ｙ）∩Ｇ1｜をＲ1−１とする。全てのグループのｙ’番目（ｋ≧ｙ’＞ｗ1）の中間スイッチ要素が存在する場合、その中間スイッチ要素の集合Ｄ（ｉ，ｙ’）のうち、Ｇ1に属する中間スイッチ要素数｜Ｄ（ｉ，ｙ’）∩Ｇ1｜は少なくともＲ1とし、全ての（ｉ，ｙ）に対し、Ｄ（ｉ，ｙ）∩Ｇ1の要素数がＲ1−１で、かつ、Ｇ1内で同一の中間スイッチ要素の集合を使用するＤ（ｉ，ｙ）∩Ｇ1は、最大でＲ1−１組とする。
【０３６７】
部分集合Ｇ2も同様に、ｉ番目の入力スイッチ要素において全てのグループのｙ番目（ｗ2≧ｙ≧１）の中間スイッチ要素の集合Ｄ（ｉ，ｙ）のうち、Ｇ2に属する中間スイッチ要素数｜Ｄ（ｉ，ｙ）∩Ｇ2｜をＲ2−１とし、全てのグループのｙ’番目（ｋ≧ｙ’＞ｗ2）の中間スイッチ要素が存在する場合、その中間スイッチ要素の集合Ｄ（ｉ，ｙ’）のうち、Ｇ2に属する中間スイッチ要素数｜Ｄ（ｉ，ｙ’）∩Ｇ2｜は少なくともＲ2とし、全ての（ｉ，ｙ）に対し、Ｄ（ｉ，ｙ）∩Ｇ2の要素数がＲ2−１で、かつ、同一の中間スイッチ要素の集合を使用するＤ（ｉ，ｙ）∩Ｇ2は、最大でＲ2−１組とする。これにより、Ｇ1を使用するように割り当てられた出力は、Ｇ1の中で再配置先および迂回路を見つけることができる。Ｇ2を使用するように割り当てられた出力は、Ｇ2の中で再配置先および迂回路を見つけることができる。
【０３６８】
例えば、ｗ1＝１、ｗ2＝２の場合では、Ｇ1からはスイッチ要素を１個削減し、｛ＭＳ−１，ＭＳ−２，ＭＳ−３｝とし、Ｇ2からはスイッチを２個削減し、｛ＭＳ−５，ＭＳ−６，ＭＳ−７，ＭＳ−８｝とする。Ｇ1は、Ｒ1＝２、ｋ＝２であるから、表８のケースと同一であり、Ｒ1−１＝１の中間スイッチ要素の組を少なくとも１個使用することができる。Ｇ2は、Ｒ2＝３、ｋ＝２であるから、Ｒ2−１＝２の中間スイッチ要素の組を少なくとも２個使用することができる。Ｇ1およびＧ2のどちらも、配信数を削減することができる前述の条件Ｂが適用される入力スイッチ要素は３個までである。このときの入力ステージにおけるルーティング処理での配信先集合Ｄ（ｉ，ｙ）の割り当ての例を表１９に示す。
【０３６９】
【表１９】
0006795172.tif 000061
【０３７０】
表１９  ｋ＝２、Ｒ＝５＝２＋３、ｍ＝（２×２−１）＋（２×３−２）＝７の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｙ番目の入力スイッチ要素の状態との関係
【０３７１】
Ｒ＝５、ｋ＝２をそのままＲＮＢ条件を満たすように中間スイッチ要素を削減した場合、ｋ＝２により、最大でも２個の中間スイッチ要素しか削減することができない。一般に分割法を使用しない場合の削減後の中間スイッチ要素数は、もとの中間スイッチ要素数の（Ｒ×ｋ−ｋ）／（Ｒ×ｋ）＝（Ｒ−１）／Ｒを下限とする。
【０３７２】
一方、分割法を使用した場合、分割したそれぞれの部分集合で、ｋ個までの中間スイッチ要素を削減することができるため、削減後の中間スイッチ要素数はもとのスイッチ要素数の（Ｒ−１）／Ｒの下限、すなわち、１／２（Ｒ＝２）にまで効果を高めることができる。表１９の例では、もともとの中間スイッチ要素数１０個から３個を削減することができる。
【０３７３】
また、各入力の入力ステージにおける配信数に着目すると、Ｒの分割数をＤRとした場合、部分集合のそれぞれにおいて、入力ステージにおける配信数を１個少なくすることができる場合がある。従って、全体で見たときのある入力ストリームの配信先中間スイッチ要素の集合Ｄ（ｉ，ｙ）について、｜Ｄ（ｉ，ｙ）｜＝Ｒ−ＤRが最小値となる。表１８では、Ｒ＝５であるため、つねに｜Ｄ（ｉ，ｙ）｜＝Ｒ＝５であるが、表１９では、ＤR＝２により、｜Ｄ（ｉ，ｙ）｜≧５−２＝３である。
【０３７４】
上述した出力スイッチ要素の条件Ｃでは、Ｒの分割数が１の場合の実施例であったため、入力側の配信数の最小値がＲ−１であり、ｊ番目の出力スイッチ要素において、（ｎ3,j×ｓ3,j）＜ｍａｘ（ｎ2,i×ｓ2,i）の場合には、
ｎ4,j×ｓ4,j≦（Ｒ−１）×ｎ3,j×ｓ3,j、かつｄ4,j≦（Ｒ−１）×ｄ3,j
式（３９）
を満たすとした。従って、Ｒの分割数ＤRが１より大きい場合を含めた場合は、
ｎ4,j×ｓ4,j≦（Ｒ−ＤR）×ｎ3,j×ｓ3,j、かつｄ4,j≦（Ｒ−ＤR）×ｄ3,j
式（４０）
を満たす必要がある。
【０３７５】
同様に、ｋを分割することによって部分集合を作成することもできる。ｋ≧４のとき、ｋ＝ｋ1＋ｋ2、ｋ1≧２、ｋ2≧２と置き換える．このとき、中間スイッチ要素数ｍについて、ｍ＝Ｒ×ｋ＝Ｒ×（ｋ1＋ｋ2）＝Ｒ×ｋ1＋Ｒ×ｋ2であるから、それぞれが独立したＲ通りの迂回路を有する部分集合の２つに分割することができる。この場合も、中間ステージのスイッチ要素の全体の削減数ｗに対し、ｗ＝ｗ1＋ｗ2（ｗ1≧０、ｗ2≧０）と分解し、
ｍ＝Ｒ×ｋ−ｗ＝（Ｒ×ｋ1−ｗ1）＋（Ｒ×ｋ2−ｗ2）
式（４１）
を満たすように、中間スイッチ要素の削減数を部分集合のそれぞれに分配する。Ｒの分割と異なり、この場合、ｋ1≧ｗ1、ｋ2≧ｗ2であるから、ｋ＝ｋ1＋ｋ2≧ｗ1＋ｗ2＝ｗとなり、削減数の最大値はｋ個のままである。
【０３７６】
具体例として、Ｒ＝２、ｋ＝５、ｍ＝Ｒ×ｋ＝１０のケースを考える。表２０では、２つのグループに対し、ｋ＝５により、１番目から５番目の中間スイッチ要素を設定している入力ステージにおけるルーティング処理での割り当ての例を示している。（各入力スイッチ要素で、１から５の中間スイッチ番号が２回割り当てられる）。しかし、ｋ1＝２、ｋ2＝３とすると、これは、ｋ＝５＝２＋３と考え、Ｒ×ｋ＝２×（２＋３）＝４＋６であるから、｛ＭＳ−１，ＭＳ−２，ＭＳ−３，ＭＳ−４｝の４個の中間スイッチ要素で独立した２グループ（Ｇ3）、｛ＭＳ−５，ＭＳ−６，ＭＳ−７，ＭＳ−８，ＭＳ−９，ＭＳ−１０｝のスイッチで独立した３グループ（Ｇ4）として扱うことと等価である。
【０３７７】
【表２０】
0006795172.tif 000062
【０３７８】
表２０  ｋ＝５、Ｒ＝２、ｍ＝１０の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｙ番目の入力スイッチ要素の状態との関係
【０３７９】
部分集合Ｇ3および部分集合Ｇ4へは異なる入力ストリームが配信されているため、出力スイッチ要素において、個々の出力は部分集合Ｇ3および部分集合Ｇ4からの経路により任意に出力するが、上記式（２）より、ｎ4,j×ｓ4,j≦Ｒ×ｎ3,j×ｓ3,j、かつｄ4,j≦Ｒ×ｄ3,j
を満たすから、ＷＳＮＢ条件を満たしている。（双方向伝送可能なリンクを使用したネットワークでは、式（１３）を元に、同じくＷＳＮＢ条件を満たしていることを理解することができる）。
【０３８０】
そこで、表２０の部分集合（Ｇ3）および部分集合（Ｇ4）のそれぞれから中間スイッチ要素を削減し、ＲＮＢ条件を独立に満たすようにする。部分集合Ｇ3では、ｉ番目の入力スイッチ要素において全てのグループのｙ番目（ｗ1≧ｙ≧１）の中間スイッチ要素の集合Ｄ（ｉ，ｙ）の要素数｜Ｄ（ｉ，ｙ）｜をＲ−１とする。全てのグループのｙ’番目（ｋ1≧ｙ’＞ｗ1）の中間スイッチ要素が存在する場合、その中間スイッチの集合Ｄ（ｉ，ｙ’）の要素数｜Ｄ（ｉ，ｙ’）｜は少なくともＲである。全ての（ｉ，ｙ）に対し、Ｄ（ｉ，ｙ）の要素数がＲ−１で、かつ、同一のＧ3内の中間スイッチ要素の集合を使用するＤ（ｉ，ｙ）は、最大でＲ−１組とする。
【０３８１】
部分集合Ｇ4も同様に、Ｇ4に属する全てのグループのｙ番目（ｗ2≧ｙ≧ｋ1＋１）の中間スイッチ要素の集合Ｄ（ｉ，ｙ）の要素数｜Ｄ（ｉ，ｙ）｜をＲ−１とする。全てのグループのｙ’番目（ｋ≧ｙ’＞ｗ2）の中間スイッチ要素が存在する場合、その中間スイッチ要素の集合Ｄ（ｉ，ｙ’）の要素数｜Ｄ（ｉ，ｙ’）｜は少なくともＲである。全ての（ｉ，ｙ）に対し、Ｄ（ｉ，ｙ）の要素数がＲ−１で、かつ、同一の中間スイッチ要素の集合を使用するＤ（ｉ，ｙ）は、最大でＲ−１組とする。このとき、部分集合Ｇ3を使用するように割り当てられた入力ストリームは、Ｇ3の中で再配置先および迂回路を有する。また、部分集合Ｇ4を使用するように割り当てられた入力ストリームは、Ｇ4の中で再配置先および迂回路を有する。従って、全ての出力は、Ｇ3およびＧ4の任意の入力ストリームに対して再配置および迂回路を有する。
【０３８２】
例えば、ｗ1＝１およびｗ2＝１の場合では、部分集合Ｇ3からは中間スイッチ要素を１個削減し｛ＭＳ−１，ＭＳ−２，ＭＳ−３｝とし、部分集合Ｇ4からは中間スイッチ要素を１個削減し｛ＭＳ−５，ＭＳ−６，ＭＳ−７，ＭＳ−８，ＭＳ−９｝とする。部分集合Ｇ3およびＧ4も、Ｒ＝２であるから、Ｒ−１＝１の中間スイッチ要素の組を少なくとも１個使用することができる。このときの入力ステージにおけるルーティング処理での配信先集合Ｄ（ｉ，ｙ）の割り当ての例を表２１に示す。
【０３８３】
【表２１】
0006795172.tif 000063
【０３８４】
表２１  ｋ＝５＝２＋３、Ｒ＝２、ｍ＝（２×２−１）＋（２×３−１）＝８の場合の配信先集合Ｄ（ｉ，ｙ）の中間スイッチ要素（ＭＳ−ｚ）への割り当てとｙ番目の入力スイッチ要素の状態との関係
【０３８５】
上記のＲの分解およびｋの分解は独立しているので、部分集合のそれぞれに対して繰り返し適用することができる。すなわち、Ｒの分解数をＤR、ｋの分解数をＤkとし、（分解のない場合はＤR＝１、Ｄk＝１）、
【０３８６】
【数４２】
0006795172.tif 000064
【０３８７】
【数４３】
0006795172.tif 000065
【０３８８】
【数４４】
0006795172.tif 000066
【０３８９】
とすると、
【０３９０】
【数４５】
0006795172.tif 000067
【０３９１】
として、全体を（ＤR×Ｄk）≧１個以上の部分集合Ｇi,jに分解し、ｗi,j＞０となるすべての部分集合において中間スイッチ要素を減じてＲＮＢ条件を満たすネットワークに置き換えてもよい。ここで、ｋに対するｊ番目の分割では、グループ内の番号付けは以下のＫjから始まるｋj個に対応する。 
【０３９２】
【数４６】
0006795172.tif 000068
【０３９３】
すなわち、Ｉ番目の入力スイッチ要素において、部分集合Ｇi,jに属する全てのグループのｙ番目（ｗi,j＋Ｋj≧ｙ≧Ｋj）の中間スイッチ要素の集合Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ）∩Ｇi,j｜がＲi−１である。全てのグループのｙ’番目（ｋj＋Ｋj＞ｙ’＞ｗi,j＋Ｋj）中間スイッチ要素がある場合、その中間スイッチ要素の集合Ｄ（Ｉ，ｙ’）∩Ｇi,jの要素数｜Ｄ（Ｉ，ｙ’）∩Ｇi,j｜は少なくともＲiである。全ての（Ｉ，ｙ）に対し，Ｄ（Ｉ，ｙ）∩Ｇi,jの要素数がＲi−１で、かつ、部分集合Ｇi,j内で同一の中間スイッチ要素の集合を使用するＤ（Ｉ，ｙ）∩Ｇi,jは、最大でＲi−１組とする。
【０３９４】
出力ステージにおけるルーティング処理でも、該当する入力ストリームが配信されている中間スイッチ要素の部分集合Ｇ（ｉ，ｊ）における少なくともＲi−１個の配信先中間スイッチ要素を対象にし、再配置も部分集合Ｇ（ｉ，ｊ）における少なくともＲi個の迂回路を対象に行えばよい。
【０３９５】
この手法は、入力ステージ、中間ステージおよび出力ステージから構成されるネットワークにおいても、また、双方向の伝送リンクを使用した入出力ステージおよび中間ステージから構成されるネットワークにおいても等しく適用できることは、これまでの記載事項から明らかである。
【０３９６】
具体的には、入出力スイッチ要素の条件Ｃでは、Ｒの分割数が１の場合の実施例であったため、入力側の配信数の最小値がＲ−１であり、入出力ステージにおけるｊ番目の入出力スイッチ要素の出力側において、（ｎ’j×ｓ’j）＜ｍａｘ（ｎ’i×ｓ’i）（ｉ≠ｊ）の場合、
ｎ4,j×ｓ4,j≦（Ｒ−１）×ｎ’i×ｓ’i、かつｄ4,j≦(Ｒ−１)×ｄ’j
式（４７）
を満たすとした。この式に代えて、Ｒの分割数ＤRが１より大きい場合を含めた場合は、
ｎ4,j×ｓ4,j≦（Ｒ−ＤR）×ｎ’i×ｓ’i、かつｄ4,j≦(Ｒ−ＤR)×ｄ’j
式（４８）
を満たす必要がある。
【図１】
0006795172.tif 000097
【図２】
0006795172.tif 000098
【図３】
0006795172.tif 000099
【図４】
0006795172.tif 000100
【図５】
0006795172.tif 000101
【図６】
0006795172.tif 000102
【図７】
0006795172.tif 000103
【図８】
0006795172.tif 000104
【図９】
0006795172.tif 000105
【図１０】
0006795172.tif 000106