(57)【要約】従来技術では、マルチソースでマルチキャスト可能なＣｌｏｓ型のネットワークのノンブロッキング条件下でのミドルステージスイッチ数を最小化する技術が示されておらず、高コストなシステムとなっていた。また、データの損失なしでは接続の追加や削除が行えなかった。課題を解決する手段として、ノンブロッキング条件下でのミドルステージスイッチの数を最小化する技術、および、データの損失なしに既存のマルチキャストツリーに接続を追加／削除する技術により、低コストで、データの損失なしに運用できる、マルチソースかつマルチキャスト可能なＣｌｏｓ型ネットワークを提供する。
2008056684.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、
アウトプットステージのスイッチ数はｒ２個であり、ミドルステージスイッチの数ｍ個が下記数式（Ａ１）を満たすマルチキャストスイッチングシステム。
【数Ａ１】
2008056684.tif 000052
【請求項２】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化（即ち各ラインは最大でもｋチャネルを有する）がされているマルチキャストスイッチングシステムであって、
アウトプットステージのスイッチ数はｒ２個であり、ミドルステージスイッチの数ｍ個が下記数式（Ａ１）を満たすマルチキャストスイッチングシステム。
【数Ａ１】
2008056684.tif 000053
【請求項３】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
アウトプットステージのスイッチ数はｒ２個と、ミドルステージスイッチの数ｍ個を下記数式（Ａ１）を満たすように定めるマルチキャストスイッチングシステムの設計方法。
【数Ａ１】
2008056684.tif 000054
【請求項４】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
アウトプットステージのスイッチ数はｒ２個と、ミドルステージスイッチの数ｍ個を下記数式（Ａ１）を満たすように定めるマルチキャストスイッチングシステムの設計方法。
【数Ａ１】
2008056684.tif 000055
【請求項５】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステム。
【表１】
2008056684.tif 000056
【請求項６】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステム。
【表１】
2008056684.tif 000057
【請求項７】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステムの設計方法。
【表１】
2008056684.tif 000058
【請求項８】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステムの設計方法。
【表１】
2008056684.tif 000059
【請求項９】
請求項１、２、５、６、のいずれか一に記載のマルチキャストスイッチングシステムであって、次の順序でそのケースを扱うことによりスイッチを制御する制御部を有するマルチキャストスイッチングシステム。
Ｃａｓｅ１：新しいアウトプットチャネルが、既にツリーを形成しているアウトプットステージのスイッチのアウトプットチャネルであるのならば、そのアウトプットステージのスイッチ内で接続を作成する。
Ｃａｓｅ２：Ｃａｓｅ１でなく、かつ、新しいアウトプットチャネルを含むアウトプットステージのスイッチが既存のミドルステージのスイッチのアウトプットポートで空いているチャネルから接続できるのならば、そのミドルステージスイッチ内で接続を作成し、上記空いているチャネルからの接続を行う。
Ｃａｓｅ３：Ｃａｓｅ１でもＣａｓｅ２でもなく、かつ、既存のマルチキャストツリーがｘ（システム上の制限により１ソースがつながり得るミドルステージスイッチの数の上限値）未満のミドルステージのスイッチしか使っていない場合は、（ステージ間リンクを介し）目的のアウトプットステージのスイッチに到達するような、空いたアウトプットポートチャネルと空いたインプットポートチャネルをもつマルチキャストツリーに含まれないミドルステージスイッチを選び、接続を行う。
【請求項１０】
請求項１、２、５、６のいずれか一に記載のマルチキャストスイッチングシステムであって、インプットステージのソースを出力するスイッチと、下記の表２に示されるＲｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍで選択されるミドルステージのスイッチと、を接続するための制御を行う制御部を有するマルチキャストスイッチングシステム。
【表２】
2008056684.tif 000060
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多重化されたソースをノンブロッキングでマルチキャスト伝送するネットワークシステムに関する。
【背景技術】
【０００２】
伝統的に、Ｎ１×Ｎ２のＣｌｏｓ（Ｃｌｏｓは人の名前；以下同様）型マルチキャストネットワークは３ステージのスイッチモジュールから構成される。インプットステージにはｒ１個のｎ１×ｍスイッチモジュールが存在し、ミドルステージにはｍ個のｒ１×ｒ２スイッチモジュールが存在し、そしてアウトプットステージにはｒ２個のｍ×ｎ２スイッチモジュールが存在する。ここで、図１に示されるように、総入力ライン数Ｎ１はｎ１×ｒ１であり、総出力ライン数Ｎ２はｎ２×ｒ２である。このようなネットワークにおいて、となりあったステージの任意の２つのスイッチモジュール間にはただ一つのリンクのみが存在し、各スイッチモジュールはマルチキャスト可能であると仮定する。従来技術では、ｍが特定の値をとる場合にその３ステージＣｌｏｓ型ネットワークがノンブロッキングな意味でのマルチキャスト能力を持っているということが示されている。
【特許文献１】特表２００７−５０４７７２
【発明の開示】
【発明が解決しようとする課題】
【０００３】
近年、新しい技術が開発されるに従って、より強力なスイッチングエレメントが商業的に利用可能となってきた。このようなスイッチでは、スイッチの各ポートが、独立したソースからの複数のデータストリームを同時にサポートすることができる。このタイプのスイッチを「マルチソーススイッチ」と呼ぶことにする。一般的に、ｓ×ｓのマルチソースマルチキャストスイッチは、ｓ個の入力ポートとｓ個の出力ポートを持ち、各ポートはｋ個の独立したリンクを持っていて、任意の入力リンクを任意の出力リンクに接続することができる。このようなスイッチを単純にｓ×ｓのｋソーススイッチと呼ぶ。このスイッチは、通常のｓｋ×ｓｋマルチキャストスイッチとして機能する。実際には、このようなスイッチの内部の実装は、パケットスイッチングである。たとえば、ｋ＝５として、各ポートが１０Ｇの帯域幅を持つｓ×ｓマルチソーススイッチは、各リンクが２Ｇの通常のｓｋ×ｓｋマルチキャストスイッチと等価である。【０００４】
しかし、従来技術では、マルチソースでマルチキャスト可能なＣｌｏｓ型のネットワークのノンブロッキング条件下でのミドルステージスイッチ数を最小化する技術が示されておらず、高コストなシステムとなっていた。更に、既存のマルチキャストツリーに接続を追加したり削除したりするアルゴリズムが示されておらず、データの損失なしでは接続の追加や削除が行えなかった。
【課題を解決するための手段】
【０００５】
本発明におけるネットワークは、上記のようなマルチソーススイッチングエレメントを３ステージＣｌｏｓ型ネットワークにおいて使用した、ノンブロッキングマルチキャストスイッチングネットワークである。本発明のＮ１×Ｎ２マルチキャストネットワークはＮ１個の入力ポートとＮ２個の出力ポートを持ち、各ポートはｋ個のリンクを持っている。これをＮ１×Ｎ２のｋソースマルチステージネットワークと呼ぶ。従来のＣｌｏｓ型ネットワークと比してのもっとも大きな違いは、図２に示すように、ｋソースマルチステージネットワークにはステージ間の各スイッチ間にはｋ本のリンクがあるということである。【０００６】
本発明では、本ネットワークを用いた場合の、ノンブロッキング条件下でのミドルステージスイッチの数（伝統的なコストメトリックであるクロスポイント数ではない）を最小化する技術を提供する。更に、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりする技術を提供する。
【発明の効果】
【０００７】
マルチソースかつマルチキャスト可能なＣｌｏｓ型ネットワークにおける、ノンブロッキング条件下でのミドルステージスイッチの数を最小化する技術により、左記ネットワークを、低コストで提供できる効果を奏する。更に、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりするアルゴリズムにより、データの損失なしで上記ネットワークを運用できるという効果を奏する。
【発明を実施するための最良の形態】
【０００８】
以下、本件発明の実施の形態について、添付図面を用いて説明する。なお、本件発明は、これら実施形態に何ら限定されるべきものではなく、その要旨を逸脱しない範囲において、種々なる態様で実施し得る。【０００９】
なお、以下の実施形態と請求項の関係は次の通りである。実施形態１は、主に請求項１、２、３、４について説明する。実施形態２は、主に請求項５、６、７、８について説明する。実施形態３は、主に請求項９について説明する。実施形態４は、主に請求項１０について説明する。
＜＜実施形態１＞＞【００１０】
＜実施形態１の概要＞【００１１】
本実施形態の概要は、マルチキャスト可能なＣｌｏｓ型のネットワークのノンブロッキング条件下でのミドルステージのスイッチを極力減らしたシステムおよびその設計方法を提供することである。【００１２】
ここで「ノンブロッキング」とは、任意の接続要求に対して、ネットワークを通る接続パスを提供して、他の既存の接続を妨害することなく要求を満たすことが常に可能な状態を指す。上記「任意の接続要求」とは、出力可能なアウトプットステージスイッチの存在を前提として、インプットステージの空きポートへの新たな入力又は既存の入力に対して、アウトプットステージスイッチからの新たな出力を任意に行うための要求である。別の言い方をすれば、アウトプットステージの任意のスイッチから新たな出力を行うための要求である。【００１３】
＜実施形態１の構成＞【００１４】
本実施形態は、マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、アウトプットステージのスイッチ数はｒ２個であり、ミドルステージスイッチの数ｍ個が下記数式（Ａ１）を満たすマルチキャストスイッチングシステム、または、その設計方法である。
【数Ａ１】
2008056684.tif 000003
【００１５】
本実施形態のマルチキャストスイッチングシステムは、例えば図２のネットワーク構成図に示すような複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなる、Ｃｌｏｓ型ネットワークを構成する。【００１６】
ここで「ステージ」とは、スイッチを複数個備えた１層以上からなるスイッチの集合体である。１ステージが複数層で実現される場合は、複数層が１層に等価的に集約できる場合である。また、１層に複数ステージを含めた場合（例えば１層で、インプットステージとアウトプットステージを実現する場合など）もＣｌｏｓ型ネットワークに該当する。上記「スイッチ」とは、例えば図３に示すような、スイッチの内部をマトリクス構造とすることで、任意の入力ポートからの信号を任意の出力ポートへの信号とすることができるスイッチを指す。【００１７】
また「Ｃｌｏｓ型ネットワーク」とは、論理的に３層以上にネットワークスイッチを接続することで大規模ネットワークを構成する方法であり、ミドルステージのポート数を、インプットステージやアウトプットステージのポート数より大きくすることで任意の入力から任意の出力に、決して他の通信を邪魔する（または他の通信に邪魔される）ことなく通信できる(ノンブロッキングで通信できる)という理想的な性質をもたせることができるネットワークを指す。【００１８】
本マルチキャストスイッチングシステムは、マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなる。【００１９】
ここで「マルチキャスト」とは、ネットワーク上で複数の相手を指定してデータを送信することを指す。すなわち１対多（１入力に対して複数の出力）のデータ送信を行うことを指す。【００２０】
本マルチキャストスイッチングシステムのインプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有する。【００２１】
すなわち、図２に示すように、システム全体で考えた場合にはインプットステージの各スイッチの各入力ポートがシステムの入力であり、１つのインプットステージのスイッチには最低ｎ１個のラインの入力ポートを有する。又、アウトプットステージの各スイッチの各出力ポートがシステムの出力であり、１つのアウトプットステージのスイッチには最低ｎ２個のラインの出力ポートを有する。【００２２】
ここで「ライン」とは、各ステージ間のスイッチどうしをつなぐ伝送路であり、出力ポート、入力ポート間に接続される物理的媒体をいう。１ポートには１ラインがつながり得るものとする。１ラインには同時に複数ソース分の信号を流すことができる。即ち、１ラインは複数チャネルから構成され得る。またラインとしては例えば光ファイバーのようなものや、金属導線のようなものや、無線の接続線（光、電磁波、音）のようなものが該当する。さらに、１ラインに含まれるチャンネルは必ずしも物理的に１本の光ファイバーなどで構成されなくともよく、複数のチャンネルを複数の光ファイバーなどで分担して構成してもよい。【００２３】
本マルチキャストスイッチングシステムのインプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続される。【００２４】
すなわち、インプットステージの任意の１スイッチは、全てのミドルステージのスイッチと、出力ポート−入力ポート間で、最低１ラインで接続されている。ミドルステージの任意の１スイッチは、全てのアウトプットステージのスイッチと、出力ポート−入力ポート間で、最低１ラインで接続されている。【００２５】
本マルチキャストスイッチングシステムの最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされている。【００２６】
すなわち、図２に示すように、各ステージの入出力ポートの１ライン上では、最大でｋ重の多重化された情報（ソース又はチャネル）が伝送され得る。例えば、異なった複数のコンテンツの映像ソースが多重化されて伝送され得る。本実施形態における各スイッチは、多重化されたソース（チャネル）を入力ポートから入力でき、かつ、スイッチ内部で多重化を解いたりｋの多重化の範囲内で任意に新たな多重化を作成して出力ポートから出力できるものである。【００２７】
ここで「多重化」とは、１ラインで同時に複数の情報を送るために分離可能に信号を重ねることである。１ライン上の多重化は１本の伝送路により行われても良いし、複数本の伝送路により行われても良い。【００２８】
多重化の方式については一般的に用いられている、波長分割多重方式（ＷＤＭ：  Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）を利用しても良い。「波長分割多重方式」は、一例として、光ファイバーを使った通信に応用される。波長分割多重方式においては、波長の違う複数の光信号を光ファイバー上において同時に多重化して利用することができるので、光ファイバー上の情報伝送量を飛躍的に増大させることができる。ＷＤＭをより高密度化したものをＤＷＤＭ（Ｄｅｎｓｅ  ＷＤＭ）という。本実施形態ではＤＷＤＭを利用したものであっても良い。ＷＤＭやＤＷＤＭは従来技術であるため、詳細説明は省略する。但し、本実施形態においては、多重化の方式はＷＤＭやＤＷＤＭに限定されるものではなく、間欠送信多重化（ＰＡＭ）、時分割多重化（ＴＤＭ）、周波数分割多重化（ＦＤＭ）、符号分割多重化（ＣＤＭ）、偏波分割多重化（ＰＤＭ）などの多重化方式であっても良い。【００２９】
本マルチキャストスイッチングシステムのアウトプットステージのスイッチ数はｒ２個であり、ミドルステージスイッチの数ｍは、数式（Ａ１）を満たす個数である。【００３０】
すなわち本マルチキャストスイッチングシステムにおいて、インプットステージの各スイッチの入力ポート数の最低値ｎ１、アウトプットステージの各スイッチの出力ポート数の最低値ｎ２、アウトプットステージのスイッチ数ｒ２、１ラインの最大多重度ｋ（１ラインで多重化されうる最大値）、から、本システムでノンブロッキングを達成するためのミドルステージスイッチ数ｍ、が数式（Ａ１）により求まる、ということである。ここで数式（Ａ１）におけるｘは、システム上の制限により１ソースがつながり得るミドルステージスイッチの数の上限値を示し、数式（Ａ１）によりｍと共に求められる値である。数式（Ａ１）における└  ┘は床関数であり└  ┘内の値を超えない最大の整数を示す。数式（Ａ１）の右辺第一項は、既に接続されていて新たな接続を行えないミドルステージのスイッチ数を示し、第二項は、ノンブロッキングを達成するために必要とする接続可能なミドルステージのスイッチ数を示す。【００３１】
以下に数式（Ａ１）を導き出すための詳細説明を行う。【００３２】
＜数式（Ａ１）を導き出すための詳細説明＞【００３３】
簡単のためＮ１＝Ｎ２＝Ｎ、ｎ１＝ｎ２＝ｎ、ｒ１＝ｒ２＝ｒの対称型のネットワークを考える。その後、非対称型に一般化する。【００３４】
従来のＣｌｏｓ型マルチキャストネットワークでは、あるミドルステージスイッチのデスティネーション集合を、そのミドルステージスイッチから接続されているアウトプットステージスイッチのラベル（識別子）の集合として定義している。しかしながら、ｋソースＣｌｏｓ型マルチキャストネットワークにおいては、ミドルステージスイッチは、ある１つのアウトプットステージスイッチに対してｋ本までの接続を持つことができる。したがって、以下のような記法で定義されるような、要素が１より大きい多重度を持つデスティネーション多重集合で考える。Ｏ＝｛１，２，...，ｒ｝を、１からｒまで番号を振られたすべてのアウトプットステージスイッチのラベル（識別子）の集合とする。あるミドルステージスイッチｊ∈｛１，２，...，ｍ｝からあるアウトプットステージスイッチｐ∈Ｏへのマルチキャスト接続はｋ本まで可能なので、デスティネーション多重集合（その基集合はＯ）を表現するためにＭｊを使う。ここでｊからｐへのマルチキャスト接続が１つより多い場合、ｐは一度以上現れ得る。Ｍｊ中にｐが現れる回数、もしくはｊからｐへのマルチキャスト接続の数を、多重集合Ｍｊにおけるｐの多重度と呼ぶことにする。【００３５】
より厳密には、多重集合を以下のように表記する。
【数１】
2008056684.tif 000004
ここで、０≦ｉｊ１，ｉｊ２，...，ｉｊｒ≦ｋはそれぞれ要素１，２，...，ｒの多重度である。ここで、各多重度がｋ未満なら、すなわち０≦ｉｊ１，ｉｊ２，...，ｉｊｒ≦ｋ−１なら、既存のいかなる接続も妨害せずにミドルステージスイッチｊを経由して実現することのできる最大限のマルチキャスト接続は、｛１，２，...，ｒ｝である（ミドルステージスイッチｊから到達可能なアウトプットステージスイッチの集合という面で）。一般的に、ミドルステージスイッチｊを経由して実現することのできる最大限のマルチキャスト接続は｛ｐ｜０≦ｉｊｐ＜ｋ，ｆｏｒ１≦ｐ≦ｒ｝である。なお、数式（１）の意味がわかりにくいので平たく説明すると以下のとおりとなる。つまり数式（１）は、ミドルステージのｊ番目のスイッチからアウトプットステージに向かって既に利用されているチャンネルを集合のかたちで表したものである。右辺のカッコ内の各要素は、それぞれアウトプットとステージの各スイッチに向かって利用されているこのミドルステージスイッチからのチャンネルの数を示すもので、例えば、一番目の要素に関しては、アウトプットステージの１番目のスイッチに向けて既にｉｊ１チャンネルが利用されていることを示す。また例えば二番目の要素に関しては、アウトプットステージの２番目のスイッチに向けて既にｉｊ２  チャンネルが利用されていることを示す。これらはｊ番目のミドルステージスイッチに関するもので、同じように１番目のミドルステージのスイッチ、２番目のミドルステージスイッチ、という具合に各ミドルステージスイッチに対してこれと同様の集合を定義できる。２つのミドルステージスイッチｊおよびｈを経由して実現可能な最大限のマルチキャスト接続を求めるために、まず、多重集合の共通集合をとる操作を以下のように定義する。
【数２】
2008056684.tif 000005
したがって、２つのミドルステージスイッチｊおよびｈを経由して実現できる最大限のマルチキャスト接続は、多重集合Ｍｊ∩Ｍｈと等しいデスティネーション多重集合を持つある１つのミドルステージスイッチを経由して実現できる最大限のマルチキャスト接続である。【００３６】
マルチキャスト接続の実現という観点から、Ｍｊのうち多重度がｋに達している要素は使用不可とみなし、通常の集合で特徴づける。したがって、Ｍｊの要素数を以下のように定義する。
すなわち「要素数」とは
【数３】
2008056684.tif 000006
であり、「選択されたミドルステージスイッチｊから到達不可能なアウトプットステージスイッチの数」を意味する。
又、Ｍｊが空であるとは、以下の状態であると定義する。
【数４】
2008056684.tif 000007
【００３７】
ここで、ファンアウトｒを持つ新規マルチキャスト接続リクエストを満たすには、使用可能なミドルステージスイッチの中から高々ｘ（ｘ≧１）個のミドルステージスイッチｉ１，...，ｉｘを使用すればよく、このときの必要十分条件はｘ個のミドルステージスイッチのデスティネーション集合の共通集合が空であることである。すなわち、∩ｘｊ＝１Ｍｊｉ＝φであることである。【００３８】
従来のマルチキャストネットワークのためのノンブロッキング条件の結果をｋソースマルチキャストネットワークに拡張する。すなわち、デスティネーション集合を、数式（１）で定義されたようなｋを超えない多重度を持ち数式（２）から（４）で定義されたような演算を持つ多重集合に置き換える。【００３９】
すると、以下のような定理１が得られる。【００４０】
＜定理１＞【００４１】
任意のｘ，１≦ｘ≦ｍｉｎ｛ｎ−１，ｒ｝に対して、ｍ´を以下の条件を満たすようなミドルステージスイッチの個数の最小値、すなわち、ノンブロッキングを達成するために必要とする接続可能なミドルステージスイッチの個数と置く。デスティネーション多重集合のどの多重度もｋを超えず、高々（ｎｋ−１）個の１、（ｎｋ−１）個の２、...、（ｎｋ−１）個のｒが、ｍ´個のデスティネーション多重集合の中に分布している。そしてそれらのデスティネーション多重集合の任意のｘ個の共通集合がどれも空でない。そうであるならば、下記数式が得られる、というものである。
2008056684.tif 000008
【００４２】
上記定理１を以下に証明する。【００４３】
＜定理１の証明＞【００４４】
これらｍ´個のミドルステージスイッチ１，２，...，ｍ´がデスティネーション多重集合Ｍ１，Ｍ２，...，Ｍｍを持つと仮定すると、仮定よりこれらの多重集合は空でない。明らかに、数式（３）、（４）を用いて
2008056684.tif 000009
が得られる。【００４５】
高々（ｎｋ−１）個の１、（ｎｋ−１）個の２、...、（ｎｋ−１）個のｒが、ｍ´個のデスティネーション多重集合の中に分布している。また、数式（３）より、Ｍｉ中に同じ要素がｋ個あると、｜Ｍｉ｜の値は１となる。したがって、任意のｊ（１≦ｊ≦ｒ）について、要素ｊの多重度が（ｎｋ−１）であるならばΣｍ´ｉ＝１｜Ｍｉ｜の値は└（ｋ−１）／ｋ┘を超えることはない。したがって
2008056684.tif 000010
を得る。Ｍｊ１を
2008056684.tif 000011
を満たすような多重集合とする。すると
2008056684.tif 000012
を得る。したがって、｜Ｍｊ１｜＞０であるため、
【数５】
2008056684.tif 000013
である。多重集合Ｍｊ１において、多重度がｋである｜Ｍｊ１｜個の要素を１，２，...，｜Ｍｊ１｜と定義する。いま、ｍ´個の新しい多重集合Ｍｊ１∩Ｍｉｆｏｒ１≦ｉ≦ｍ´を与えると、数式（２）、（３）および、任意の２つの多重集合の共通集合は空ではないという定義から、
2008056684.tif 000014
である。そして、多重集合Ｍｊ１∩Ｍｉの要素１，２，...，｜Ｍｊ１｜だけが多重度ｋを持っているので｜Ｍｊ１∩Ｍｉ｜の値へ寄与することができる。高々（ｎｋ−１）個の１、（ｎｋ−１）個の２，...，（ｎｋ−１）個の｜Ｍｊ１｜はｍ´多重集合Ｍｊ１∩Ｍｉｆｏｒ１≦ｉ≦ｍ´に分配される。上記同様の解析を用いて、次式
【数６】
2008056684.tif 000015
を得る。Ｍｊ２を多重集合とし、
2008056684.tif 000016
とする。その結果，同様に｜Ｍｊ１∩Ｍｊ２｜＞０であるため、
【数７】
2008056684.tif 000017
を得ることができる。一般的に、２≦ｙ≦ｘのとき、以下となる。
【数８】
2008056684.tif 000018
そして高々ｘのオリジナルの多重集合の共通集合が空ではないという仮定に基づき、｜∩ｙｌ＝１Ｍｊｌ｜＞０である。他方では、このｍ´多重集合（∩ｘ−１ｌ＝１Ｍｊｌ）∩Ｍｉ（１≦ｉ≦ｍ´）も仮定に基づいて全て空ではない。これは｜（∩ｘ−１ｌ＝１Ｍｊｌ）∩Ｍｉ｜≧１ｆｏｒ１≦ｉ≦ｍ´および
2008056684.tif 000019
という意味である。その結果、数式（６）の導出と同様の根拠を用いて、以下が導出される。
【数９】
2008056684.tif 000020
ｍ´は数式（５），（８）及び（９）の右辺の幾何学的平均より大きくならないため、
2008056684.tif 000021
を得る。【００４６】
定理１の直接的推論１は以下の通りである。【００４７】
Ｃｌｏｓ型ｋソースマルチキャストネットワークにおいて、ファンアウトｒ'，１≦ｒ'≦ｒの新しいマルチキャスト接続要求に対して、この接続要求のために利用可能なミドルステージスイッチが（ｎ−１）ｒ'１／ｘ，１≦ｘ≦ｍｉｎ｛ｎ−１，ｒ'｝より多く存在したならば、そのときいつでもこの新たな接続要求を満たすｘ個のミドルステージスイッチが存在する。【００４８】
したがって、k-ソースマルチキャストネットワークのためのノンブロッキング条件を以下のように構築できる。【００４９】
＜定理２＞【００５０】
すなわち定理２とは、Ｃｌｏｓ型ｋソースＮ×Ｎマルチキャストネットワークは以下の関係式を満たせば、どんなマルチキャストの割り当てでもノンブロッキングとなる、というものである。
【数１０】
2008056684.tif 000022
【００５１】
上記定理２は、以下のように証明される。【００５２】
＜定理２の証明＞【００５３】
マルチキャスト接続を実現するルーティング方法は高々ｘのミドルステージスイッチを用いるので、上記直接的推論１によって、新たなマルチキャスト接続要求に利用可能なミドルステージスイッチが（ｎ−１）ｒ１／ｘより多くあるならば、いつでもこの新たなマルチキャスト接続要求を実現するx個のミドルステージスイッチを選ぶことができる。【００５４】
ここで、「ルーティング」とは本実施形態のマルチキャストスイッチングシステムにおける、マルチキャスト接続の経路制御のことを指す。【００５５】
ここで、他のマルチキャスト接続のために使用される入力リンクは最大で nk-1 個存在しうる。ルーティング方法によって、それらの各々は、このインプットステージスイッチにおける異なったアウトプットのときに高々ｘ本のリンクに接続されて、そして、高々ｘ個のミドルステージスイッチに接続される。伝統的なネットワークとは異なり、マルチソースのマルチキャストネットワークにおいては、異なった入力ポートの２つのリンクはインプットステージスイッチの同じ出力の２個のリンクに接続して、そして、同じミドルステージスイッチに接続することができる。ここで、最悪の場合に新たなマルチキャスト接続に利用できないミドルステージスイッチの数はいくつかを求める。各々のポートはｋリンクを持っており、現在のインプットステージスイッチからミドルステージスイッチへつながっているポートのすべてのｋリンクはｋの既存のマルチキャスト接続に使用されているなら、このミドルステージスイッチは利用することができない。したがって、高々
2008056684.tif 000023
のミドルステージスイッチは新しいマルチキャスト接続要求に利用できない。故に、ミドルステージスイッチの必要とする総数、ｍは、最悪のケースの利用できないミドルステージスイッチの数とマルチキャスト接続の実現に必要だった利用可能なミドルステージスイッチの最大の数を足した数より大きい。ｍの最小値は（１０）から右辺の式のｘのとり得るすべての値の最小化によって得られる。【００５６】
より一般的なネットワークに関しての結果は、以下の定理３により与えられる。【００５７】
すなわち定理３とは、Ｃｌｏｓ型ｋソースＮ１×Ｎ２マルチキャストネットワークは以下の関係式を満たせば、どんなマルチキャストの割り当てでもノンブロッキングとなる、というものである。
【数１１】
2008056684.tif 000024
【００５８】
＜実施形態１の効果＞【００５９】
本実施形態により、本ネットワークのノンブロッキング条件下でのミドルステージのスイッチを極力減らすことができ、同ネットワークを、低コストで提供できる効果というを奏する。
＜＜実施形態２＞＞【００６０】
＜実施形態２の概要＞【００６１】
本実施形態の概要は、上記実施形態で得たネットワークに対し、ミドルステージのスイッチを最小化したシステムおよびその設計方法を提供することである。【００６２】
＜実施形態２の構成＞【００６３】
本実施形態は、マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステム、または、その設計方法である。
【表１】
2008056684.tif 000025
【００６４】
本マルチキャストスイッチングシステムは、マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなる。これらについては既に実施形態１で説明済みであるため、説明を省略する。【００６５】
本マルチキャストスイッチングシステムのインプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有する。これらについては既に実施形態１で説明済みであるため、説明を省略する。【００６６】
本マルチキャストスイッチングシステムのインプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続されている。これらについては既に実施形態１で説明済みであるため、説明を省略する。【００６７】
本マルチキャストスイッチングシステムの最低保証される各ラインは、最大でもｋ（ｋ≧１）重の信号の多重化がされている。これらについては既に実施形態１で説明済みであるため、説明を省略する。【００６８】
本マルチキャストスイッチングにおいて、ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅは、表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められる。【００６９】
すなわち本マルチキャストスイッチングシステムにおいて、アウトプットステージの各スイッチの出力ポート数の最低値ｎ２、アウトプットステージのスイッチ数ｒ２、数式（Ａ１）を満たす値ｘ（すなわち、システム上の制限により１ソースがつながり得るミドルステージスイッチの数）、実施形態１で求められたノンブロッキングを達成するために必要とする接続可能なミドルステージスイッチの個数ｍ´、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 Ｎ´から、ノンブロッキングを達成するために必要とする接続可能なミドルステージスイッチの個数の最小値ｍ´ｒｅｆｉｎｅが表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められる、ということである。【００７０】
ここで、「ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 Ｎ´」とは、ミドルステージとアウトプットステージ間のラインのうち最悪の条件下でフルになっているラインの数、のことである。すなわち、アウトプットステージ全体では、ｎ２×ｒ２本ある出力ラインのうち（ｎ２−１）×ｒ２本の出力ラインが最悪の状態でフルになっている可能性があり、ミドルステージとアウトプットステージの間のラインも（ｎ２−１）×ｒ２本がフルになっている状態が最悪の状態であると言え、結局（ｎ２−１）×ｒ２が、ミドルステージとアウトプットステージ間のラインのうち最悪の条件下でフルになっているラインの数となる。ｎ２×ｒ２本すべてがフルになっている状態は新しい接続要求リクエストに応える必要がないので最悪の状態ではない。同様に、出力ステージのスイッチがどれか一つでもｎ２本フルになっている状態も最悪状態ではない。【００７１】
以下に表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍを説明する。【００７２】
行０１、０２は初期化部分である。すなわち、ｍｍ´はｍ´ｒｅｆｉｎｅの候補を示す変数であり、行０１において、ｍ´（施形態１で求められた値）を代入し初期化している。また、ｃｃｊ（ｊ＝１，...，ｘ）はミドルステージスイッチをｊ個選択した場合の共通集合の要素数（すなわち、選択されたｊ個のミドルステージスイッチから到達不可能なアウトプットステージスイッチの数；実施形態１の数式（８）参照）であり、行０２にて全て０に初期化している。【００７３】
行０３から行１３はＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍの本体部分でありｃｃｘが０である限りは、ｍｍ´（ｍ´ｒｅｆｉｎｅの候補）を減らすことができることを示している。ｃｃｘが０であるとは、ｘ個のミドルステージスイッチを選択すれば（１ソースに対してｘ個のミドルステージスイッチまで選択可能である）、ミドルステージスイッチから到達不可能なアウトプットステージスイッチは無くなる（すなわちノンブロッキングが達成される）ことを示している。【００７４】
行０４は、１つのミドルステージスイッチを選んだ場合の要素数を計算する箇所である。すなわち、実施形態１の数式（５）で示される要素数（数式（５）の右辺分母）を計算している。【００７５】
行０５から行０７は、ｃｃｊ（ｊ＝２，...，ｘ）を計算する部分であり、実施形態１の数式（８）で示される共通集合の要素数（数式（８）の右辺分母）の計算に相当する。【００７６】
行０８から行１１は、ｃｃｘが０（すなわちノンブロッキングが達成される）ならば、ｍ´ｒｅｆｉｎｅの候補としてｍｍ´を代入し、保存しておく。また、システムパラメータｃｊ（ｊ＝１，...，ｘ）の候補としてｃｃｊ（ｊ＝１，...，ｘ）を代入し、保存しておく。ｍｍ´＝ｍ´の場合は、実施形態１の定理３によりｃｃｘは０（すなわちノンブロッキングが達成される）であるため、必ず保存される。【００７７】
行１２では、ｍｍ´がデクリメントされ、行０３から行１１が繰り返される。すなわち、ｍｍ´を減らしてもｃｃｘが０である（すなわちノンブロッキングが達成される）限り、ｍ´ｒｅｆｉｎｅと、システムパラメータｃｊの候補が保存される。行１２でｍｍ´を減らした後、行０８にてｃｃｘが０で無くなったと判断されたとき（すなわちノンブロッキングが達成されない場合）は、ｍ´ｒｅｆｉｎｅと、システムパラメータｃｊの候補は保存されず、更に行０３にてｗｈｉｌｅループを抜けて終了する。終了時には、ノンブロッキングが達成される最小のｍ´ｒｅｆｉｎｅとそのときのシステムパラメータｃｊ（ｊ＝１，...，ｘ）が得られる。【００７８】
以下に、具体例をあげつつ、Ｒｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍを説明する。【００７９】
＜Ｒｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍの具体例による説明＞【００８０】
実施形態１で、初期の解析を行い、マルチソースのノンブロッキングマルチキャストスイッチングネットワークの第一のデザインを得た。定理１，２，３の論理的限界は、最適化が実数の関数であること、に起因している。前記実数の関数は、使用可能なミドルステージスイッチを決める近似線を与える。デスティネーション多重集合の要素数は、整数であるという事実を考慮すれば、以下のような最小化を得て、コストを下げられる。【００８１】
以下に、あるｋソースマルチキャストネットワーク（Ｎ＝１６０；ｎ＝８；ｒ＝２０；ｋ＝５）を取り上げ、ミドルステージスイッチ数を最小化する一例を具体的に示す。
ここで再び各数値について記すと、「Ｎ」は入力ステージの全ポート数であり出力ステージの全ポート数でもある。「ｎ」は、入力ステージと、出力ステージの各スイッチが有するポート数である。「ｒ」は、入力ステージのスイッチ数であり、出力ステージのスイッチ数でもある。また、次に出てくる「ｋ」は各ライン（各ポートにつながれている信号線）に許される多重度、言い換えれば各ラインに許されるチャンネル数である。【００８２】
ｋソースマルチキャストネットワークに以下のパラメータを当てはめ、
Ｎ＝１６０；ｎ＝８；ｒ＝２０；ｋ＝５；
定理２を用いてｘおよびｍを以下のように計算できる。
ｘ＝３，ｍ＝４３
使用可能なミドルステージスイッチの数の限界（ｍ´）は以下で示される。
2008056684.tif 000026
上式で┌  ┐は天井関数であり、┌  ┐内の値を下回らない最小の整数を示す。
新しいマルチキャスト接続のリクエストは、使用可能なミドルステージのスイッチのｍ´＝２０から選ばれた、ｘ＝３のミドルステージのスイッチを用いることで、実現されうることをまず証明する。数式（５）によると最初に選ぶミドルステージスイッチｊ１は以下を満足するものである。
2008056684.tif 000027
数式（７）によると次に選ぶミドルステージスイッチｊ２は以下を満足するものである。
2008056684.tif 000028
そして最後に、３回目に選ぶミドルステージスイッチｊ３は以下を満足するものである。
2008056684.tif 000029
よってＭｊ１∩Ｍｊ２∩Ｍｊ３＝φを得られた。ということは、どんなマルチキャストリクエストであっても、ｍ´＝２０の使用可能なミドルステージスイッチから選ばれた３つのミドルステージスイッチｊ１，ｊ２とｊ３により実現されうる。実施形態１で、ｍ´は実数の関数ベースで計算されたので、実際のｍ´は僅かにもうすこし小さい。この固有のケースでは、ｍ´＝２０でなくｍ´＝１８がｘ＝３を実現する新しいマルチキャスト接続リクエストの条件を保障する最も小さいｍ´である、ということを以下のように証明しうる。最初に選ぶミドルステージスイッチｊ１は
2008056684.tif 000030
２番目に選ぶミドルステージスイッチｊ２は
2008056684.tif 000031
３番目に選ぶミドルステージスイッチｊ３は
2008056684.tif 000032
である。よって、ｘ（＝３）のミドルステージスイッチは、ｍ´＝１８でマルチキャスト接続を実現するのに十分である。一方、ｍ´＝１８が最も小さいことが判るが、ｍ´＝１７ではどんなマルチキャスト接続も実現することができないことを示す。最初に選ぶミドルステージスイッチｊ１は
2008056684.tif 000033
２番目に選ぶミドルステージスイッチｊ２は
2008056684.tif 000034
３番目に選ぶミドルステージスイッチｊ３は
2008056684.tif 000035
である。Ｍｊ１∩Ｍｊ２∩Ｍｊ３≠φということが判る。すなわち、ｘ（＝３）のミドルステージスイッチでは、すべてのマルチキャスト接続を可能とするわけではない（実現できないマルチキャスト接続があるかもしれない）。よって、ｍ´＝１８が最も小さいことが証明された。したがって、このネットワーク構造は以下のように最小化されうる。
ｎ＝８，ｒ＝２０，Ｎ＝１６０，ｋ＝５、ｘ＝３、ｍ＝４１【００８３】
デスティネーション多重集合の共通集合化の際の（最小のｍ´＝１８を求める）ｘ（＝３）ステップの中で得られた、最小要素数は以下である。
ｃ１＝７、ｃ２＝２、ｃ３＝０
一般には、デスティネーション多重集合の共通集合化の際の（最小のｍ´を求める）ｘステップの中で得られた、最小要素数は以下である。
（数１２）
ｃ１、ｃ２，...，ｃｘ 【００８４】
以下に、Ｎ１×Ｎ２ネットワークの最小化アルゴリズムを提供する。【００８５】
表（１）に示すように、ネットワークパラメータｎ１，ｒ１，ｎ２，ｒ２、選ばれたｘ、初期値ｍ´値（例えば（ｎ２−１）ｒ２１／ｘから選べる）、ミドルステージスイッチで配分された最大のエレメント数であるＮ´（例えば（ｎ２−１）ｒ２）を入力する。このアルゴリズムの出力は、最小化されたｍ´ｒｅｆｉｎｅと数式（１２）のシステムパラメータである。【００８６】
最終的には、最小化されたｍは定理３に従うと、このようになる。
2008056684.tif 000036
この最小化アプローチは、ｋソース３ステージマルチキャストネットワークであれば、任意のｋ≧１に適用できるので、ｋ＝１の従来のマルチキャストネットワークにも適用できる。【００８７】
＜実施形態２の効果＞【００８８】
本実施形態により、本ネットワークのノンブロッキング条件下でのミドルステージのスイッチ数を最小化することができ、同ネットワークを、低コストで提供できるという効果を奏する。
＜＜実施形態３＞＞【００８９】
＜実施形態３の概要＞【００９０】
本実施形態の概要は、上記実施形態に加え、更に、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりするアルゴリズムを提供することである。ここで「マルチキャストツリー」とは目的のソースが利用中のシステム内のツリー部分を言う。【００９１】
＜実施形態３の構成＞【００９２】
本実施形態のマルチキャストスイッチングシステムは、実施形態１又は２に記載のマルチキャストスイッチングシステムであって、例えば図４で示されるような場合に、次の順序でそのケースを扱うことによりスイッチを制御する制御部を有するマルチキャストスイッチングシステムである。すなわちその順序とは、Ｃａｓｅ１：新しいアウトプットチャネルが、既にツリーを形成しているアウトプットステージのスイッチのアウトプットチャネルであるのならば、そのアウトプットステージのスイッチ内で接続を作成する。Ｃａｓｅ２：Ｃａｓｅ１でなく、かつ、新しいアウトプットチャネルを含むアウトプットステージのスイッチが既存のミドルステージのスイッチのアウトプットポートで空いているチャネルから接続できるのならば、そのミドルステージスイッチ内で接続を作成し、上記空いているチャネルからの接続を行う。Ｃａｓｅ３：Ｃａｓｅ１でもＣａｓｅ２でもなく、かつ、既存のマルチキャストツリーがｘ（システム上の制限により１ソースがつながり得るミドルステージスイッチの数の上限値）未満のミドルステージのスイッチしか使っていない場合は、（ステージ間リンクを介し）目的のアウトプットステージのスイッチに到達するような、空いたアウトプットポートチャネルと空いたインプットポートチャネルをもつマルチキャストツリーに含まれないミドルステージスイッチを選び、接続を行う、というものである。【００９３】
制御部は、本マルチキャストスイッチングシステムは、次の順序でそのケースを扱うことによりスイッチを制御する（図４（ａ）、（ｂ）、（ｃ））。【００９４】
制御部の制御順序を以下に示す。ここで、制御部による各スイッチへの制御方法としては、アドレス制御であっても良いし、パケット制御であっても良い。【００９５】
Ｃａｓｅ１としては、新しいアウトプットチャネルが、既にツリーを形成しているアウトプットステージのスイッチのアウトプットチャネルであるのならば、そのアウトプットステージのスイッチ内で接続を作成する（図４（ａ））。【００９６】
すなわち、アウトプットステージスイッチから新しい出力チャネルを作りたいときに、そのスイッチ内からチャネルを供給できる場合はスイッチ内で接続を作成するだけで足りる。【００９７】
Ｃａｓｅ２としては、Ｃａｓｅ１でなく、かつ、新しいアウトプットチャネルを含むアウトプットステージのスイッチが既存のミドルステージのスイッチのアウトプットポートで空いているチャネルから接続できるのならば、そのミドルステージスイッチ内で接続を作成し、上記空いているチャネルからの接続を行う（図４（ｂ））。【００９８】
すなわち、アウトプットステージスイッチから新しい出力チャネルを作りたいときに、そのスイッチ内からチャネルは供給できないが、あるミドルステージスイッチから供給できる（そのミドルステージスイッチの空き出力ポートも存在する）場合は、そのミドルステージスイッチ内でミドルステージスイッチの空き出力ポートへ接続を作成し、その出力ポートから目的のアウトプットステージスイッチへ接続を作成すれば良い、ということである。【００９９】
Ｃａｓｅ３としては、Ｃａｓｅ１でもＣａｓｅ２でもなく、かつ、既存のマルチキャストツリーがｘ（システム上の制限により１ソースがつながり得るミドルステージスイッチの数の上限値）未満のミドルステージのスイッチしか使っていない場合は、（ステージ間リンクを介し）目的のアウトプットステージのスイッチに到達するような、空いたアウトプットポートチャネルと空いたインプットポートチャネルをもつマルチキャストツリーに含まれないミドルステージスイッチを選び、接続を行う（図４（ｃ））。【０１００】
すなわち、アウトプットステージスイッチから新しい出力チャネルを作りたいときに、そのスイッチ内やミドルステージからチャネルは供給できないが、あるインプットステージスイッチから供給できる場合（そのスイッチのマルチキャストツリーがｘ未満のミドルステージのスイッチしか使っていない場合）は、ノンブロッキングが達成されることは既に保障済みなので適正なミドルステージスイッチを選べば、目的のアウトプットステージスイッチへ接続できる、ということである。ここで適正なミドルステージスイッチとは、空いたアウトプットポートチャネルと空いたインプットポートチャネルをもつマルチキャストツリーに含まれないミドルステージスイッチであり、かつ、目的のアウトプットステージスイッチに達し得るミドルステージスイッチのことである。【０１０１】
＜マルチキャスト接続を追加・削除するアルゴリズムの詳細＞【０１０２】
本実施形態では、マルチソースノンブロッキングマルチキャストネットワークのためのルーティングアルゴリズムを提示する。シングルソースマルチキャストルーティングアルゴリズムに比して、主な差異は以下である。【０１０３】
すなわち、既存のマルチキャストツリーにブランチを追加したり削除したりすること、二つのステージ間のスイッチの接続は複数のリンクを持っているという状況を扱う、ということである。【０１０４】
＜ルーティングアルゴリズムのための用語の定義＞【０１０５】
ルーティングアルゴリズムを提供する前に、以下に用語の定義を行う。次に述べられるものは、すべて、スイッチングネットワークの論理的レイアウトの記述であり、物理的レイアウトの記述ではない。よって、単純にスイッチモジュールをスイッチとして言及する。【０１０６】
３ステージマルチソースのマルチキャストスイッチングネットワークのあるチャネル（若しくはリンク）は５要素で記述される。
【数１３】
2008056684.tif 000037
ここで、Ｓｔａｇｅは集合｛ＩＮ，ＭＩＤ，ＯＵＴ｝の１つの値をとり、どのステージに属するか表現する。ＩｎＯｕｔは集合｛ＩＮ，ＯＵＴ｝の１つの値をとり、チャネルのスイッチサイド（インプット側かアウトプット側か）を表現する。Ｓｗｉｔｃｈ＃はそのステージのスイッチの番号、Ｐｏｒｔ＃はそのスイッチのポートの番号、Ｃｈａｎｎｅｌ＃はそのポートのチャネル番号（０からｋ−１）である。ネットワークのインプットチャネルを、実際には＜ＩＮ，ＩＮ，Ｓｗｉｔｃｈ＃，Ｐｏｒｔ＃，Ｃｈａｎｎｅｌ＃＞だが＜Ｓｗｉｔｃｈ＃，Ｐｏｒｔ＃，Ｃｈａｎｎｅｌ＃＞と記述する。また、同様にアウトプットチャネルを、実際には＜ＯＵＴ，ＯＵＴ，Ｓｗｉｔｃｈ＃，Ｐｏｒｔ＃，Ｃｈａｎｎｅｌ＃＞を意味するが＜Ｓｗｉｔｃｈ＃，Ｐｏｒｔ＃，Ｃｈａｎｎｅｌ＃＞と記述する。あるマルチキャストアドレスはアウトプットチャネルの１集合として定義する。
【数１４】
2008056684.tif 000038
しかしながら、アウトプットステージのスイッチにのみ着目すれば良いので（アウトプットステージのスイッチに達してしまえばどのポート／チャネルからも出力できるので）、あるマルチキャストアドレスはアウトプットステージスイッチラベル（識別子）で表現し得る。
【数１５】
2008056684.tif 000039
マルチキャスト接続リクエストはインプットチャネルとマルチキャストアドレスのペアで定義する。
【数１６】
2008056684.tif 000040
与えられたマルチキャスト接続リクエストのマルチキャストルーティングは、いくつかの選ばれたスイッチ上で接続の設定をしていくことによりマルチキャストツリーを構築することである。その選ばれるスイッチとはインプットステージではそのインプットチャネルが入ってきているスイッチであり、それからいくつかのミドルステージのスイッチが選ばれ、それからマルチキャストアドレスに関連しているアウトプットステージのスイッチがすべて選ばれる。通常、あるスイッチの内部の設定は、あるインプットポートのチャネルから、このスイッチの異なるアウトプットポートのチャネルへの、１対多接続となる。アウトプットステージのスイッチでは、同じアウトプットポートに対して１つ以上のチャネルを使うこともある。あるスイッチの中で見たときの１対多の接続に対し、このスイッチのインプットチャネルを「ローカルインプットチャネル」、このスイッチのアウトプットチャネルの集合を「ローカルマルチキャストアドレス」という。あるスイッチのなかの１対多の接続は、あるマルチキャストツリーの一部分であり、以下のように表現する。
【数１７】
2008056684.tif 000041
加えて、あるマルチソースＣｌｏｓ型マルチステージネットワークのステージ間の接続は固定化されており、接続される隣り合ったステージのスイッチ間で、いくつかのチャネルを強制的な接続とする。すると、以下の式を得る。
【数１８】
2008056684.tif 000042
そのため、マルチキャスト接続リクエストは、数式（１７）に示す１対多接続集合により構築されたマルチキャストツリーによるスイッチングネットワークで実現し得る。選ばれたスイッチのなかで数式（１７）と数式（１８）に示すステージ間の固定化されたリンクを使って表現できる。明らかに、あるマルチキャストツリーにおいて、選択されたミドルステージスイッチ間で、２つのスイッチから、同一のアウトプットスイッチに繋がることはない。マルチキャストツリーのどの接続も、あるスイッチにおいて、他のマルチキャストツリーとチャネルを共有しないので、異なるマルチキャストツリー間では衝突はない。今後の便利化のため、あるインプットステージスイッチの１対多接続（数式（１７））のローカルマルチキャストアドレスは、ミドルステージスイッチラベル（識別子）の１集合として表現し得る。
2008056684.tif 000043
あるミドルステージスイッチのローカルマルチキャストアドレスは、アウトプットステージスイッチラベル（識別子）の１集合として表現し得る。
【数１９】
2008056684.tif 000044
実施形態２で定義したミドルステージのデスティネーション多重集合は、ルーティングアルゴリズムを記述する際にも使用し得る。
【数２０】
2008056684.tif 000045
また、あるミドルステージスイッチの接続を追加／削除するのを記述するために、次のような集合をベースとして多重集合Ｍｊと集合｛０，１，...，ｒ−１｝をベースとした通常集合Ｖの＋と−の演算を定義する。
【数２１】
2008056684.tif 000046
もしも、０未満、又は、ｋを超える多重度があれば、数式（２１）の結果の多重集合は、成り立たない。【０１０７】
＜マルチソースネットワークの追加／削除の具体例＞【０１０８】
一般的に、インプットベースのマルチキャストルーティングとアウトプットベースのマルチキャストルーティングの２タイプのマルチキャスト接続リクエストがある。インプットベースのマルチキャストルーティングは、ネットワークのインプットリンクから新しいマルチキャストツリーを作ることである。マルチキャスト接続を（丸ごと）削除するリクエストがあったとき、そのインプットリンクを根とするツリー全体を消してしまう。文献４のルーティングアルゴリズムを用いてこの目的のため使える。【０１０９】
アウトプットベースのマルチキャストルーティングにおいて、追加のリクエストがあったとき、アウトプットリンクから既存のマルチキャストツリーへブランチを加える。削除要求があったときは、マルチキャストツリーからネットワークのアウトプットリンクにくっついたブランチを除去する。【０１１０】
明らかに、削除作業はノンブロッキングが達成し得る。なぜならマルチキャストツリーのミドルステージスイッチの数が増えないからである。したがって、マルチソースネットワークにおける削除作業に対しては、他のアウトプットチャネルに向けた他のブランチ（使用中のブランチ）を持つツリーの接合部に達するまで、ネットワークのインプットサイドへ向けたアウトプットチャネルからのツリーのブランチを削除することが、簡単にできる。【０１１１】
残りの文章では、追加作業に的を絞る。次のルーティングアルゴリズムのスケッチで見られるように、１度に１つのブランチを加えれば、ノンブロッキング条件に反せずにできる。また多くのケースで接続をつくるのが簡単になる。【０１１２】
次の順序でそのケースを扱うことにより、ルーティングアルゴリズムをアウトライン化できる。
Ｃａｓｅ１：もし、新しいアウトプットチャネルが既存のアウトプットステージスイッチのなかにあるとき、そのマルチキャストツリースイッチのインプットポートのチャネルからアウトプットチャネルへ、アウトプットステージスイッチの接続を簡単に作れる。（図４（ａ）参照）
Ｃａｓｅ２：新しいアウトプットチャネルがあるアウトプットステージスイッチが、既存のミドルステージスイッチのアウトプットポートであいているチャネルから接続できるのならば、マルチキャストツリーがあいているチャネルへ伸ばすように、ミドルステージスイッチ上で接続を作成する。そのツリーを、ミドルステージスイッチのチャネルから、アウトプットステージスイッチへのステージ間リンクを介して伸ばしたので、最終的に、ｃａｓｅ１と同様、アウトプットステージスイッチの接続を作成できる。例えば図４（ｂ）のようにできる。
Ｃａｓｅ３：既存のマルチキャストツリーがｘ（予め定義された値）以下のミドルステージスイッチを使うのなら、（ステージ間リンクを介し）このアウトプットステージスイッチへ導く、あいたアウトプットポートチャネルをもつ使用可能なミドルステージスイッチを選べる。（そのようなミドルステージスイッチはノンブロッキングが保障されているため必ず存在する）
＜実施形態３の効果＞
本実施形態では、上記実施形態の効果に加え、更に、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりするアルゴリズムにより、データの損失なし、かつ、ノンブロッキング状態で本ネットワークを運用できるという効果を奏する。
＜＜実施形態４＞＞
＜実施形態４の概要＞【０１１３】
本実施形態の概要は、上記実施形態に加え、更に、既存のマルチキャストツリーのミドルステージスイッチ選択がｘに達している場合にも、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりできるアルゴリズムを提供することである。
＜実施形態４の構成＞【０１１４】
本実施形態は、実施形態１又は２に記載のマルチキャストスイッチングシステムであって、インプットステージのソースを出力するスイッチと、下記の表２に示されるＲｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍで選択されるミドルステージのスイッチと、を接続するための制御を行う制御部を有するマルチキャストスイッチングシステム、である。
【表２】
2008056684.tif 000047
【０１１５】
制御部は、インプットステージのソースを出力するスイッチと、（表２）に示されるＲｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍで選択されるミドルステージのスイッチと、を接続するための制御を行う。【０１１６】
本ルーティングアルゴリズムは、同じ根をもつ既存マルチキャストツリーをベースとした新しいマルチキャストツリーを作るものであり、既存のマルチキャストツリーのミドルステージスイッチ選択がｘに達している場合（図４（ｄ））に利用するものである。【０１１７】
制御部で実現される本ルーティングアルゴリズムの詳細を以下に示す。ここで、制御部による各スイッチへの制御方法は、アドレス制御であっても良いし、パケット制御であっても良い。【０１１８】
このアルゴリズムへの入力は、アウトプットステージスイッチの集合である"ＭｃａｓｔＡｄｄｒｎｅｗ"をもった新しいマルチキャスト接続リクエスト、新しい接続リクエストのための接続可能なミドルステージスイッチの集合（それは同じ根をもつ既存マルチキャストツリーのミドルステージスイッチを含む）、デスティネーション多重集合、既存マルチキャストツリーのミドルステージスイッチの集合、既存マルチキャストツリーのミドルステージスイッチの１対多接続のローカルマルチキャストアドレスである。アルゴリズムの出力は、新しいマルチキャストツリーのための選ばれたミドルステージの集合、新しいマルチキャストツリーの選ばれたミドルステージスイッチの１対多接続のローカルマルチキャストアドレス、である。【０１１９】
本ルーティングアルゴリズムは、既存のマルチキャストツリーのミドルステージスイッチ選択がｘに達している場合に利用するものなので、同じ根を持つ既存マルチキャストツリーのためのミドルステージスイッチの数は既にｘに達しているはずなので、集合Ｆｅｘｉｓｔは｛ｉ１，ｉ２，...，ｉｘ｝と表現できる。初期化では、Ｗｑは（数式２１を使い）ｑ∈Ｆｅｘｉｓｔに対し、多重集合Ｍｑ−ＬＭｑ、または単にＭｑと定義される。そしてＶｑは、ミドルステージスイッチｑから、空いているリンクのないアウトプットステージスイッチの集合として定義される。【０１２０】
アルゴリズムの main 関数において、集合 MASK は初期値として McastAddrnew が代入される。事前に与えられたシステムパラメータc1, c2, . . . , cx をベースに、高々x 回の繰り返しが行われる。各繰り返しの中で、新しいマルチキャストツリーのための中間ステージスイッチp を選択するためにselect(cj ,MASK)を呼び（そしてp をFnew に格納して）、それから新しいツリーのミドルステージスイッチp における1 対多接続のローカルマルチキャストアドレスLMnew,p （アウトプットステージスイッチの集合）を生成し、最後に変数MASK などを更新する。【０１２１】
関数select(cj ,MASK) では、まず既存のマルチキャストツリーにおいて|Vq ∩ MASK| ≦ cj を満たすような任意のミドルステージスイッチq が存在するかどうかをチェックする。そのようなスイッチが複数存在する場合、数式(22) の値が最少となるようなものを返す。そのようなスイッチが存在しない場合、|Vp ∩ MASK| ≦ cjを満たすような任意のスイッチp を返す。【０１２２】
以下に、本ルーティングアルゴリズムの説明および証明を行う。【０１２３】
＜本ルーティングアルゴリズムの説明と証明＞【０１２４】
実施形態５では達成できなかった、既存マルチキャストツリーがすでにｘのミドルステージスイッチを使っているワーストケースで、たかだかｘのミドルステージスイッチが使われるのを保障できるように、既存マルチキャストツリーを変更する。以下の方法により、どのデータとも衝突せず、どのパケットも失わないように、中断のない変更を行う。【０１２５】
＜オーバーラップしたマルチソースマルチキャストツリーの特性＞【０１２６】
同じインプットチャネルをその根に持ち、少なくとも部分的に（新旧のツリーで）オーバーラップしたマルチキャストアドレスを持つ、２つのマルチキャストツリーを考える。まるで１番目の（旧）ツリーが開放された（消された）かのように、２番目の（新）ツリーが独立して決定される。しかしながら、その２つのツリーが同時にネットワーク上で存在しているかのように仮定する。したがって、オーバーラップしたブランチにおいて、あるチャネルでは２つのツリーの衝突がある。より正確には、2 つのタイプのチャネルマージ（衝突）が起こり得る。あるスイッチの同じインプットポート上の 2 つのチャネル（2 つのツリーの2 つのブランチとして）がこのスイッチのアウトプットポートのひとつのチャネルにマージされるとき、これをチャネルレベルのブランチマージと呼ぶ。あるスイッチの異なるインプットポートの 2 つのチャネル（2 つのツリーの2 つのブランチとして）が
そのスイッチのひとつのアウトプットポートのひとつのチャネルとしてマージされるとき、これをスイッチレベルのブランチマージと呼ぶ。以下の定理は、これらの同じ根を持つ 2 つの独立して決められたマルチキャストツリーのためのすべての可能なオーバーラップの
ケースを記述したものである。【０１２７】
＜定理４＞【０１２８】
定理２，３のノンブロッキング状態を満足する、Ｃｌｏｓ型の３ステージマルチソースマルチキャストネットワークにおいて、同じインプットチャネルから、２つのオーバーラップしたマルチキャストアドレスへの、２つの独立的に決定されたマルチキャストツリーは、そのスイッチの他のインプットチャネルを根とするマルチキャストツリーとはオーバーラップしない。一方で、2 つのツリーはいくつかのブランチ（すなわち、スイッチ内での接続）をインプットステージスイッチ、ミドルステージスイッチ、もしくはアウトプットステージスイッチにおいて共有することがある。2 つのツリーはチャネルレベルのブランチマージをミドルステージスイッチもしくはアウトプットステージスイッチで持つことがあり、スイッチレベルのブランチマージをアウトプットステージスイッチで持つことがある。【０１２９】
＜定理４の証明＞【０１３０】
同じインプットチャネルを根とする２つのマルチキャストツリーの各々は、  ｍ´＝ｍ−［（ｎ１−１／ｋ）ｘ］の接続可能なミドルステージスイッチから選ばれた高々ｘのミドルステージスイッチを使って決定されるので、定理２又は３により、それらの各々は、そのスイッチの他の異なるインプットチャネルを根とする他の（高々）ｎ１ｋ−１のマルチキャストツリーとはいかなる衝突もない。【０１３１】
一方で、2 つのツリーにおいて同じ入力チャネルから始まる共通な出力チャネルへのパスを考慮する。2 つのツリーはツリーのブランチ（すなわちスイッチ内の接続）をインプットステージスイッチ、ミドルステージスイッチそしてアウトプットステージスイッチ内で共有することができる。インプットステージスイッチ内の接続において、2 つのツリーに対してはただ一つのインプットチャネルしかないので、このインプットポートの2 つのチャネル（2 つのツリーの2 つのブランチ）がこのインプットステージスイッチのアウトプットポートのアウトプットチャネルにマージすることは不可能である。しかしながら、そのようなチャネルレベルのブランチマージは双方のマルチキャストツリーで共有される
ミドルステージスイッチやアウトプットステージスイッチでは起こっても良い。また、ミドルステージスイッチ内の接続において、2 つのツリーのツリーブランチは同じインプットステージスイッチから来るので、このミドルステージスイッチの異なる2 つのインプットポートの2 つのチャネル（2 つのツリーの2つのブランチとして）は、2 つのインプットステージスイッチからきてこのミドルステージスイッチのチャネルへマージすることは不可能である。そのようなスイッチレベルのブランチマージはインプットステージのスイッチにおいても不可能である。しかしながら、アウトプットステージのスイッチにおいては可能なこともある。いくつかのケースの例を図 5 に示す。【０１３２】
図５は、＜ｉｃ１，｛ｏｃ１，ｏｃ２，ｏｃ３，ｏｃ４｝＞のマルチキャスト接続リクエストに対する、２つのオーバーラップしたマルチキャストツリーのイラストを示す。実線は、最初のマルチキャストツリーのみに対するツリーのブランチであり、破線は、２個目（組み換え後）のマルチキャストツリーのみに対するツリーのブランチである。太線は、シェアーされている（旧・新で使っている）ツリーのブランチ（例えばｉｃ１からｏｃ１）である。また、ＡとＢは、それぞれミドルステージスイッチのアウトプットステージスイッチのチャネルレベルのブランチのマージの（同じポートだがチャネルが異なる状態で入り同一のポートからでる）ポイントである。"Ｃ"はスイッチレベルのブランチのマージの（異なるポートから入り同一のポートからでる）ポイントである。【０１３３】
ネットワークにおけるマルチキャスト接続 <InChannel,McastAddr1> のための既存のマルチキャストツリーが与えられ、出力チャネル ocnew を持つ新規マルチキャスト接続ブランチを加えて、結果として新しいマルチキャスト接続が McastAddr2 = McastAddr1 ∪ {ocnew} となるようなケースに、定理 4 を適用する。明らかに、定理 2,3 のノンブロッキング条件により、その新規マルチキャストツリーは同じ入力チャネルを根とする既存のマルチキャストツリーを無視して構築することができる。すなわち、新規マルチキャストツリーは、異なるチャネルを根とする既存のマルチキャストツリーとはコンフリクトすることがない。新しく作られたツリーは同じ根を持つ既存のツリーとはコンフリクトするかもしれない。これは定理 4 で詳らかにされている。このタイプのコンフリクトは、既存のツリーと新しいツリーが同じデータを送信しているので、本質的にデータロスや混信を起こさない。【０１３４】
（従来技術の）回路的スイッチングにおいては、マージ能力を持った回路が与えられる時、中断なしのデータ伝送を提供するために、まず一瞬のうちに新しい接続パスを追加し（定理 2, 3 より、m' 個の使用可能な中間ステージスイッチは、2 つのマルチキャストツリーのための 2 セットの x 個の中間ステージスイッチ（そのうちのいくつかはオーバラップするかもしれない）を持つことができる）、それから古いマルチキャストツリーを解放する。最終的に、新しいマルチキャスト接続リクエストを実現する新しいマルチキャストツリーは高々x 個の中間ステージスイッチを使用するにとどまるので、そのネットワークにおける将来のマルチキャストリクエストに対してのノンブロッキング条件を保証することができる。【０１３５】
この実施形態のようなパケットスイッチングにおいて、各々のスイッチのルーディグテーブルに対して適切なセッティングを行うと、効率的に同じようなことができる。【０１３６】
論理上、実施形態１又は２の基本的なルーティングアルゴリズム（すなわち全てのマルチキャストツリーを作成し直す方法）を使うことができる。しかし、既存マルチキャストツリーへマルチキャストブランチを加える操作として、変更していないオリジナル接続を残したほうがよい。この目的を達せられるか見るために、定理４で述べられた異なるケースのすべてを解析する。明らかに、２つのツリーがいくつかのブランチをシェアしている時には、これらのブランチの既存ツリーのオリジナルセッティングを残すことができる。「チャネルレベルのブランチのマージ」のケースにおいても、オリジナルセッティングを用いることができる（図５のｉｃ１からＡへのパスや、ｉｃ１からＢへのパスで示されるように）。なぜなら、オリジナルセッティングと新しいセッティングは、次のステージの同じスイッチへつながるためである。しかし、スイッチレベルのブランチのマージのケースでは、既存ツリーと新しいツリーの間でブランチを交換する必要がある。【０１３７】
マルチキャストルーティングのキーとなるステップは、x 個までの中間ステージスイッチを選択することである。入力チャネルはそのスイッチを経由して、マルチキャストアドレスで示される出力ステージのスイッチへと接続される。以下で、新しいマルチキャストツリーを生成するルーティングアルゴリズムを示す。このアルゴリズムは既存のマルチキャストツリーのブランチを可能な限り使用し、スイッチレベルのブランチマージを可能な限り少なく保つ。まず、これらのゴールを達成するために有用ないくつかの特性を示す。【０１３８】
与えられたネットワークに対して、高々 x 回の各選択ステップにおけるデスティネーション多重集合の共通集合の濃度の上限として、システムパラメータ c1, c2, . . . , cx がある。そのような上限の例は数式 (12) に見られる。実施形態 2 における議論に基づいて、i 番目のステップにおいて、直前の i - 1 番目までのステップで選択されたミドルステージスイッチとの共通集合の濃度が ci を超えないような任意のミドルステージスイッチが選択される。最小の濃度となるミドルステージスイッチを選ぶ必要はないということに注意すること。これにより、従来のアルゴリズムよりも選択肢が多くなった。このケースでは、そのようなミドルステージスイッチの濃度の中で同じ根の既存のツリーにすでにあるようなミドルステージスイッチを選択したい。それによってそのスイッチの既存の設定を利用できるので一つめのゴールが達成される。【０１３９】
既存のツリーと共有されるミドルステージスイッチを選択することのもうひとつの利点は、スイッチレベルのブランチマージを削減できることである。これは 2 つめのゴールである。図 5 の例では、もし最初にミドルステージスイッチ MW1 を選択したら、既存のブランチはアウトプットステージスイッチ OW1 において oc1 と oc2 の両方をカバーできるので、ミドルステージスイッチ MW3 をあとから選択したときに OW1 をもうカバーする必要がないので、C 点におけるスイッチレベルのブランチマージも発生しなくなる。【０１４０】
一方で、そのような中間ステージスイッチを選択することの潜在的な欠点を調査してみよう。図 5 の他の例で見られるように、中間ステージスイッチ MW2 （ローカルマルチキャストアドレス LM2 = {OW3,OW4}という既存の接続を持っている）を選択したならば、新しい接続が新しいローカルマルチキャストアドレスLMnew,2 = {OW2,OW3,OW4} を実現するときに出力ステージスイッチ OW2 の oc2 および oc3 においてスイッチレベルのブランチマージが起こってしまうことになる。したがって、同じ根をもつ既存のマルチキャストツリー中に複数の中間ステージスイッチの候補がある場合、選択の優先度は、以下のような条件を満たす中間ステージスイッチを選ぶということになる：
【数２２】
2008056684.tif 000048
これによってスイッチレベルのブランチマージの回数を削減できる。もちろん、上記の例では MW2 だけがそのような中間スイッチなので、それを選ぶ必要がある。【０１４１】
図 6 は 2 つのオーバラップしたマルチキャストツリーのもうひとつの例である。細い実線は 1 つめの接続リクエスト <ic1, ｛oc1, oc2, . . . , oc6}> に対するマルチキャストツリーにのみ存在するブランチ、破線は 2 つめの接続リクエスト <ic1, {oc1, oc2, . . . , oc6, oc7}> に対するマルチキャストツリーにのみ存在するブランチ、太い実線は両方のマルチキャストツリーで共有されているブランチを表している。【０１４２】
＜本ルーティングアルゴリズムのチャネルレベルでの実装＞【０１４３】
前記のルーティングアルゴリズムは、新マルチキャストツリーのスイッチの集合および、各スイッチでのポートレベルでの１対多接続を生成するものである。ここでは、チャネルレベルでの実装を記述する。すなわち、既存のツリーと新しいツリーの間でチャネルレベルで共有されたブランチを識別して保持する方法や、既存のツリーだけに属するブランチ識別して削除する方法や、新しいツリーだけに属するブランチを識別して追加する（さらに、チャネルを割り当てる）方法や、既存のツリーおよび新しいツリー両方に含まれるスイッチ上で、コネクションを変更する（削除と追加を同時に行う）方法について議論する。追加と削除のルーティングアルゴリズムの実装とは、実際には既存のツリーが新しいツリーに換わるようにスイッチのルーティングテーブルを新しいツリーのコネクションをアップデートすることである。ここで、スイッチモジュールのルーティングテーブルは数式 (17) の形の 1 対多接続の集合である。【０１４４】
数式（１７）で示される１対多接続は、具体的には数式（２３）のように表すことができる。
【数２３】
2008056684.tif 000049
ここでｉｐ１とｏｐｉはスイッチの入力ポートおよびスイッチの出力ポートをそれぞれ表し、ｉｃ１とｏｃｉはポートの入力チャネルおよび出力チャネルをそれぞれ表す。既存のツリーの接続についてはチャネルは既知であるが、新しいツリーについては、入力チャネルおよび新しいマルチキャスト接続要求で指定されている出力チャネル以外は決められるものである。【０１４５】
＜アルゴリズムの対象となるスイッチの特定と操作＞【０１４６】
ＳＷｅｘｉｓｔとＳＷｎｅｗはそれぞれ既存のツリーと新しいツリーのスイッチの集合とする。明らかに、ＳＷｅｘｉｓｔ−ＳＷｎｅｗに含まれる任意のスイッチに対しては、削除操作のみを行う必要がある。また、ＳＷｎｅｗ−ＳＷｅｘｉｓｔに含まれる任意のスイッチに対しては、追加操作のみを行う必要がある。しかしながら、ＳＷｎｅｗ∩ＳＷｅｘｉｓｔに含まれる任意のスイッチに対しては、このスイッチにおける既存のツリーと新しいツリーのためのコネクションに依存して操作が行われることが必要である。このタイプの操作を混合操作と呼ぶ。【０１４７】
＜削除操作単独の場合＞【０１４８】
削除操作のみを行う必要のあるスイッチについては、既存のツリーにおいてただ１つのみの１対多接続（数式（２３）の形式）を持っている。我々はこのスイッチのルーティングテーブルから単純にそれを取り除くことが出来る。このケースの例は図６のＭＷ１である。【０１４９】
＜追加操作単独の場合＞【０１５０】
追加操作のみの実行が必要なスイッチに関しては、それは実際には新しいツリーの一部である。したがって、ポートレベルでの1 対多接続は既知である。しかし、対応するチャンネルはここで新たに決める必要がある。すなわち、数式（２３）は次のように書き表すことが出来る。
2008056684.tif 000050
ここで、"(?)" の意味は、そのチャンネル番号を決める必要があるということである。そのスイッチがアウトプットステージにある場合、明らかにチャンネル oci は新しいマルチキャスト接続リクエストのマルチキャストアドレスの詳細によって決められる。そうでなければ、そのスイッチの、対応する出力ポートのチャンネル oci をこのポートの上の任意のアイドルなチャンネルに割り当てることができる（アイドルなチャンネルは前記ルーティングアルゴリズムに基づいて、必ず存在する)。残りは、チャネルｉｃ１を決定することである。そのスイッチがインプットステージにある場合、ic1 は接続リクエストのインプットチャンネルでなければならない。そうでなければ、新しいツリーにおける1 つ前のステージから突き止められる。実際、数式 (18) を用いて、1 つ前のステージのスイッチ番号とアウトプットポート番号を見つけることができ、それは新しいマルチキャストツリー内でユニークであり、チャネルはすでに決められている。したがって、再び数式 (18) を用いて、1 つ前のステージのそのチャネルを ic1 とすることができる。このケースの例は図６のＭＷ３とＯＷ５である。【０１５１】
＜混合操作＞【０１５２】
スイッチが既存のツリーにも新しいツリーにも含まれいている場合、二つのツリーの上で、このスイッチにおける１対多接続の差分を見つけなければならない。定理４によって示されるように、一般に、既存のツリーと新しいツリーのポートレベルでの１対多接続は、スイッチのインプットポートを共有するので、新しいツリーのチャンネル ic1 を既存のツリーのそれと同じであるとすることができる（チャネルレベルでブランチのマージを避けるため）；アウトプットステージスイッチにおいてのみ、二つの１対多接続はこのスイッチで異なった入力ポートを持つかもしれない。そのスイッチにおける新しいサブツリーと既存のサブツリーの間の関係に依存して、異なったケースがある。以下の混合操作１から４は、既存のツリーと新しいツリーの１対多接続がスイッチ上の同じ入力ポートを共有している場合であり、混合操作５は、１対多接続がスイッチ上の二つの異なった入力ポートを使用している場合である。【０１５３】
＜混合操作１：新サブツリー＝既存サブツリーの場合＞【０１５４】
このケースでは、既存のツリーと新しいツリーでの 1 対多接続が、そのスイッチ上で同じである（インプットステージかミドルステージのスイッチではポートレベルで、アウトプットステージ上のスイッチではアウトプットチャンネルレベルで）。既存のツリーでのこのスイッチの 1 対多接続（チャンネルレベルで）は新しいツリーによってそのまま使用することができる。したがって、することは何もない。このケースの例は図６のＯＷ３とＯＷ４である。【０１５５】
＜混合操作２：新サブツリー⊂既存サブツリーの場合＞【０１５６】
このケースでは、既存のツリーと新しいツリーのポートレベルの１対多接続はスイッチの入力ポートを共有する。しかし、新しいツリーのローカルマルチキャストアドレスは既存のツリーのローカルマルチキャストのサブセットだけになる。それ故に、実際は新しいツリーで必要ないローカルマルチキャストアドレスを削除することによって、既存のツリーのルーティングテーブルの数式（２３）の１対多接続を変更する。例として、もし＜ｏｐ１，ｏｃ１＞，＜ｏｐ２，ｏｃ２＞が新しいツリーに存在しないなら、数式（２３）の接続は、ルーティングテーブル内で以下のように修正される。
2008056684.tif 000051
【０１５７】
＜混合操作３：新サブツリー⊃既存サブツリーの場合＞【０１５８】
このケースでは、既存のツリーと新しいツリーのポートレベルの１対多接続はスイッチの入力ポートを共有する。しかし、新しいツリーのローカルマルチキャストアドレスは既存のツリーのローカルマルチキャストのスーパーセットになる。単にいくつかのローカルマルチキャストアドレスを数式（２３）へ追加する。それは前記＜追加動作単独の場合＞と同様であるが、ここでは ic1 をすでに使っているので決める必要がない。それが既に使用中なので。このケースの例は図６のＭＷ２である。【０１５９】
＜混合操作４：新サブツリー≠既存ツリーの上記以外の場合＞【０１６０】
このケースでは、再び既存のツリーと新しいツリーのポートレベルの１対多接続はスイッチの入力ポートを共有する。しかし、新しいツリーのいくつかの＜ｏｐｉ，ｏｃｉ（？）＞は既存のツリーにはなく、そして、既存のツリーのいくつかの＜ｏｐｊ，ｏｃｊ＞は新しいツリーにはない。数式（２３）のローカルマルチキャストアドレスを、新しいツリーのためのそれへと修正することができる。このケースの例は図６のＩＷ１である。２本のツリーでのブランチの共有がないような特別なケースもあるかもしれない。【０１６１】
＜混合操作５：新サブツリーと既存サブツリーでスイッチの入力ポートの共有なしの場合＞【０１６２】
このケースでは、既存のツリーと新しいツリーの１対多接続がスイッチの異なった入力ポートを使う。それはスイッチレベルでのブランチのマージであり、定理４に述べられているようにアウトプットステージでのみ起こる。ルーティングテーブル内では、＜削除操作単独の場合＞のように既存のツリーへの１対多接続を削除すること、そして同時に＜追加操作単独の場合＞のように新しいツリーへ１対多接続を追加すること、が必要である。このケースの例は図６のＯＷ１とＯＷ２である。【０１６３】
出力ベースのルーティングアルゴリズムはｋソース３ステージマルチキャストネットワークに対して、任意のｋ≧１で適用可能であり、特にｋ＝１の場合の従来のマルチキャストネットワークも含んでいることになる。【０１６４】
＜実施形態４の効果＞
本実施形態では、上記実施形態の効果に加え、更に、既存のマルチキャストツリーのミドルステージスイッチ選択がｘに達している場合にも、データの損失なしに既存のマルチキャストツリーに接続を追加したり削除したりするアルゴリズムを提供することができ、データの損失なし、かつ、ノンブロッキング状態で本ネットワークを運用できるという効果を奏する。
【図面の簡単な説明】
【０１６５】
【図１】従来技術のマルチキャストスイッチングシステムの概要を表す図
【図２】本発明のマルチキャストスイッチングシステムの概要を表す図
【図３】本発明のマルチキャストスイッチングシステムの構成要素であるスイッチの概要を表す図
【図４】実施形態３と実施形態４を説明するための概念図
【図５】実施形態４を説明するための概念図１
【図６】実施形態５を説明するための概念図２
【図１】
2008056684.tif 000061
【図２】
2008056684.tif 000062
【図３】
2008056684.tif 000063
【図４】
2008056684.tif 000064
【図５】
2008056684.tif 000065
【図６】
2008056684.tif 000066
【手続補正書】
【提出日】平成20年3月27日(2008.3.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステム。
【数Ａ１】
2008056684.tif 000067
【表１】
2008056684.tif 000068
【請求項２】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムであって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステム。
【数Ａ１】
2008056684.tif 000069
【表１】
2008056684.tif 000070
【請求項３】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、最低ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、最低ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに最低保証される各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステムの設計方法。
【数Ａ１】
2008056684.tif 000071
【表１】
2008056684.tif 000072
【請求項４】
マルチキャスト能力を有する複数のスイッチをそれぞれ備えたインプット、ミドル、アウトプットの３ステージからなり、
インプットステージの各スイッチは、ｎ１個のラインの入力ポートを有し、アウトプットステージのスイッチは、ｎ２個のラインの出力ポートを有するとともに、
インプットステージの各スイッチは、全てのミドルステージスイッチのそれぞれに対して最低１ライン接続され、ミドルステージの各スイッチは、全てのアウトプットステージのそれぞれのスイッチに対して最低１ライン接続され、
さらに各ラインは最大でもｋ（ｋ≧１）重の信号の多重化がされているマルチキャストスイッチングシステムの設計方法であって、
ｘは数式（Ａ１）を満たす値であり、アウトプットステージのスイッチ数はｒ２個、ミドルステージスイッチとアウトプットステージの間で全てのチャネルがふさがっているライン数の最大値 はＮ´（ただし、Ｎ´は「（ｎ２−１）×ｒ２」を意味する。）であり、ミドルステージスイッチの数ｍ´ｒｅｆｉｎｅが下記の表１に示されるＲｅｆｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍに従って求められるマルチキャストスイッチングシステムの設計方法。
【数Ａ１】
2008056684.tif 000073
【表１】
2008056684.tif 000074
【請求項５】
請求項１、２、のいずれか一に記載のマルチキャストスイッチングシステムであって、次の順序でそのケースを扱うことによりスイッチを制御する制御部を有するマルチキャストスイッチングシステム。
Ｃａｓｅ１：新しいアウトプットチャネルが、既にツリーを形成しているアウトプットステージのスイッチのアウトプットチャネルであるのならば、そのアウトプットステージのスイッチ内で接続を作成する。
Ｃａｓｅ２：Ｃａｓｅ１でなく、かつ、新しいアウトプットチャネルを含むアウトプットステージのスイッチが既存のミドルステージのスイッチのアウトプットポートで空いているチャネルから接続できるのならば、そのミドルステージスイッチ内で接続を作成し、上記空いているチャネルからの接続を行う。
Ｃａｓｅ３：Ｃａｓｅ１でもＣａｓｅ２でもなく、かつ、既存のマルチキャストツリーがｘ（システム上の制限により１ソースがつながり得るミドルステージスイッチの数の上限値）未満のミドルステージのスイッチしか使っていない場合は、（ステージ間リンクを介し）目的のアウトプットステージのスイッチに到達するような、空いたアウトプットポートチャネルと空いたインプットポートチャネルをもつマルチキャストツリーに含まれないミドルステージスイッチを選び、接続を行う。
【請求項６】
請求項１、２のいずれか一に記載のマルチキャストスイッチングシステムであって、インプットステージのソースを出力するスイッチと、下記の表２に示されるＲｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍで選択されるミドルステージのスイッチと、を接続するための制御を行う制御部を有するマルチキャストスイッチングシステム。
【表２】
2008056684.tif 000075
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
なお、以下の実施形態と請求項の関係は次の通りである。実施形態１は、主に請求項１、２、３、４について説明する。実施形態２は、主に請求項１、２、３、４について説明する。実施形態３は、主に請求項５について説明する。実施形態４は、主に請求項６について説明する。
【国際調査報告】
2008056684.tif 000076
2008056684.tif 000077