JP2946193B2 - マルチキャスト接続経路選択方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、マルチキャスト接
続経路選択方法に関し、特に複数の交換ノードで構成さ
れる通信ネットワークを介して複数の端末を一斉に接続
／解放するマルチキャスト接続する場合のマルチキャス
ト接続経路選択方法に関するものである。

【０００２】

【従来の技術】複数の交換ノードで構成される通信ネッ
トワークを利用して、等しい速度でネットワークにデー
タが送信されるＣＢＲ（Constant Bit Rate ）のトラフ
ィック特性を有する音声や、短期間に多量のデータがネ
ットワークに送出されるバースト的なトラフィック特性
を有するコンピュータ処理された画像情報などを、複数
の端末に対して一斉に送信する場合、発端末からの仮想
回線（Virtual Channel:ＶＣ）接続要求に応じて発端末
と各着端末との間を接続するルートを選択しそれぞれ必
要伝送容量に基づく帯域の予約を行う必要がある。

【０００３】従来、このようなマルチキャスト接続経路
を選択する場合、発端末と各着端末とを結ぶ最適な経路
をそれぞれの着端末ごとに求め、これら最適経路のうち
共通して使用されている部分経路を抽出して共用化する
方法が考えられる。図７は、複数の交換ノードから構成
される通信ネットワークの一例を示す説明図であり、Ｒ
Ｔは発端末、ＬＦ１，ＬＦ２は着端末、ａ〜ｇはこれら
発端末ＲＴと各着端末ＬＦ１，ＬＦ２とをリンクを介し
て網状に交換接続する交換ノードである。

【０００４】図７（ａ）に示すような通信ネットワーク
において、発端末ＲＴと着端末ＬＦ１，ＬＦ２を接続す
るマルチキャスト接続経路を選択する場合には、まず発
端末ＲＴと各着端末ＬＦ１，ＬＦ２とをそれぞれ接続す
る最適経路が求められる。着端末ＬＦ１については、ａ
−ｂ−ｃからなる経路が、最も交換ノード数およびリン
ク数の少ない最適な経路となる。

【０００５】また、着端末ＬＦ２については、ａ−ｄ−
ｅからなる経路が、最も交換ノード数およびリンク数の
少ない最適な経路となる。このようにして、図７（ｂ）
に示すように、各着端末ごとに最適経路を求めた後、こ
れら最適経路が共通して使用している部分経路が抽出さ
れる。この場合には、ＲＴ−ａ以外の交換ノード間接続
するリンクが共通して使用されておらず、リンクの共用
は実施されない。

【０００６】

【発明が解決しようとする課題】しかしながら、このよ
うな従来のマルチキャスト接続経路選択方法では、発端
末と各着端末とを結ぶ最適な経路をそれぞれの着端末ご
とに求め、これら最適経路のうち共通して使用されてい
る部分経路を抽出して共用化することから、交換ノード
およびリンクが共用される割合が低くなる傾向があり、
ネットワーク資源を効率よく利用できるマルチキャスト
接続経路を選択することができないという問題点があっ
た。例えば、図７（ｂ）に示したように、前述した従来
の方法により選択されたマルチキャスト接続経路では、
発端末からすべての着端末までの交換ノード数が５、使
用するリンク数が４となる。

【０００７】しかし、図７（ｃ）に示すように、例えば
ａ−ｂ−ｃ−ｅあるいはａ−ｄ−ｅ−ｃというマルチキ
ャスト接続経路は、部分経路ａ−ｂ−ｃあるいはａ−ｄ
−ｅが着端末ＬＦ１，ＬＦ２で共用できるとともに、交
換ノード数が４、リンク数が３となり、従来のマルチキ
ャスト接続経路選択方法では、このようにネットワーク
資源を効率よく利用するマルチキャスト接続経路を選択
できない場合があるという問題点があった。本発明はこ
のような課題を解決するためのものであり、ネットワー
ク資源を効率よく利用でき、かつ伝搬遅延が少ないマル
チキャスト接続経路を選択することができるマルチキャ
スト接続経路選択方法を提供することを目的としてい
る。

【０００８】

【課題を解決するための手段】このような目的を達成す
るために、本発明によるマルチキャスト接続経路選択方
法は、発端末とすべての着端末とをマルチキャスト接続
するＭＣツリー候補を経由交換ノード数が少ない順に選
択するＭＣツリー構成ノード決定処理を実行し、これら
各ＭＣツリー候補について、発端末とこの発端末から最
も離れた着端末とを最も少ない経由リンク数で接続する
アークを決定するＭＣツリー構成アーク決定処理を実行
するようにしたものである。したがって、発端末とすべ
ての着端末とをマルチキャスト接続するＭＣツリー候補
を経由交換ノード数が少ない順に選択され、これら各Ｍ
Ｃツリー候補について、発端末とこの発端末から最も離
れた着端末とを最も少ない経由リンク数で接続するアー
クが決定される。

【０００９】また、ＭＣツリー構成ノード決定処理で
は、探索中の状態にある各ＭＣツリー候補について、そ
の状態におけるすべてのノード候補を検索し、これらノ
ード候補のうちいずれかの着端末を収容する交換ノード
に到達したものあるいは到達する可能性のあるものを探
索中のＭＣツリー候補に順次格納することによりＭＣツ
リーの探索を実行し、探索中ＭＣツリー候補が各着端末
を収容するすべての交換ノードに到達した時点で探索を
終了し、各探索終了ツリーを所望のＭＣツリー候補とし
て出力するようにしたものである。したがって、ＭＣツ
リー構成ノード決定処理では、探索中の状態にある各Ｍ
Ｃツリー候補について、その状態におけるすべてのノー
ド候補が検索され、これらノード候補のうちいずれかの
着端末を収容する交換ノードに到達したものあるいは到
達する可能性のあるものが探索中のＭＣツリー候補に順
次格納され、探索中ＭＣツリー候補が各着端末を収容す
るすべての交換ノードに到達した時点で探索が終了さ
れ、各探索終了ツリーが所望のＭＣツリー候補として出
力される。

【００１０】さらに、探索中ＭＣツリー候補の交換ノー
ド数が、各探索終了ツリーの交換ノード数より小さくな
い場合には、探索終了ツリーの数が所定数以上得られて
いるか否か判断し、所定数以上得られている場合には、
ＭＣツリー構成ノード決定処理を終了するようにしたも
のである。したがって、探索中ＭＣツリー候補の交換ノ
ード数が、各探索終了ツリーの交換ノード数より小さく
ない場合には、探索終了ツリーの数が所定数以上得られ
ているか否か判断され、所定数以上得られている場合に
は、ＭＣツリー構成ノード決定処理が終了される。

【００１１】また、ＭＣツリー構成アーク決定処理で
は、探索中ＭＣツリーの交換ノードのうち最も着端末よ
りの交換ノードをそれぞれ選択し、ＭＣツリー候補を構
成する交換ノードのうち探索中ＭＣツリーに含まれてい
ない残りの交換ノードから、前記選択された交換ノード
に隣接する交換ノードへのアークを順次選択して探索中
ＭＣツリーに含めるアーク探索を実行し、各着端末を収
容するすべての交換ノードが探索中ＭＣツリーに含まれ
た時点でアーク探索を終了し、そのアーク探索終了ツリ
ーを所望のＭＣツリーとして出力するようにしたもので
ある。したがって、ＭＣツリー構成アーク決定処理で
は、探索中ＭＣツリーの交換ノードのうち最も着端末よ
りの交換ノードがそれぞれ選択され、ＭＣツリー候補を
構成する交換ノードのうち探索中ＭＣツリーに含まれて
いない残りの交換ノードから、選択された交換ノードに
隣接する交換ノードへのアークが順次選択されて探索中
ＭＣツリーに含められ、各着端末を収容するすべての交
換ノードが探索中ＭＣツリーに含まれた時点でアーク探
索が終了され、そのアーク探索終了ツリーが所望のＭＣ
ツリーとして出力される。

【００１２】

【発明の実施の形態】次に、本発明について図面を参照
して説明する。図１は本発明の一実施の形態であるマル
チキャスト接続経路選択方法の処理手順を示すフローチ
ャートであり、複数の交換ノードで構成されるネットワ
ークにおいて、任意の端末からの所定の接続要求に応じ
てこの発端末（ＲＴ）と発端末からの接続要求で指示さ
れた複数の着端末（ＬＦ）とを一斉にマルチキャスト
（ＭＣ：Multi Cast）接続する場合のマルチキャスト接
続経路を選択するために、通信ネットワークを管理する
所定の交換ノードにて予めまたはその接続要求に応じて
実行される。

【００１３】なお、このマルチキャスト接続経路選択処
理を行うにあたって、交換ノードは処理対象となるネッ
トワーク構成、すなわち交換ノード、各交換ノードを接
続するリンク、および各端末を収容する交換ノードなど
の各種接続情報を把握しているものとする。また、ここ
では各リンクを交換接続する手段としてＡＴＭ交換ノー
ドを例に説明するが、この交換ノードとしては複数の交
換ノードからなるサブネットワークも含められるものと
し、この場合には各サブネットワークを管理するサブネ
ットマネージャによりマルチキャスト接続選択処理が実
行されるものとなる。

【００１４】交換ノードでは、所定の発端末と複数の着
端末とを接続するマルチキャスト接続選択処理として、
図１に示すような処理を実行する。まず、発端末とすべ
ての着端末とをマルチキャスト接続する場合に必要な交
換ノード群をＭＣツリー候補として複数決定するととも
に、これら交換ノード群からなるＭＣツリー候補を経由
交換ノード数の少ない順に出力するために、ＭＣツリー
構成ノード決定処理（ステップ１０）が実行される。な
お、マルチキャスト接続経路の形状が木（ツリー）構造
となることから、以下ではマルチキャスト接続経路の経
路パターンをＭＣツリーという。

【００１５】したがって、ここでは発端末とすべての着
端末とをマルチキャスト接続するためのＭＣツリーを構
成する交換ノード群が、ＭＣツリー候補として経由交換
ノード数が少ない順に出力されるものとなる。なお、同
数の交換ノードであっても異なる交換ノード群からＭＣ
ツリーを構成可能である場合には、各ＭＣツリーごとに
それぞれ交換ノード群がＭＣツリー候補として選択され
るものとなる。

【００１６】次にＭＣツリー構成ノード決定処理によ
り、発端末と複数の着端末とを接続するためのＭＣツリ
ー候補が出力されたか否か判断し（ステップ１１）、Ｍ
Ｃツリー候補が出力されなかった場合には（ステップ１
１：ＮＯ）、これら発端末と複数の着端末とを接続する
ためのＭＣツリーなしと判断して（ステップ１３）処理
を終了する。

【００１７】一方、ＭＣツリー構成ノード決定処理によ
りいずれかのＭＣツリー候補が出力された場合には（ス
テップ１１：ＹＥＳ）、各ＭＣツリー候補について、そ
の交換ノード群を介して発端末とその発端末から最も離
れた着端末とを最も少ない経由リンク数で接続するため
に、ＭＣツリー構成アーク決定処理が実施される（ステ
ップ１２）。なお、アークとは木構造における任意の方
路（枝）のことであり、実際には交換ノード間を接続す
るリンクから構成される。

【００１８】したがって、ここでは交換ノード数が少な
い各ＭＣツリー候補について、発端末と各着端末とを最
も少ない数の経由リンクでマルチキャスト接続するため
のＭＣツリーを構成するリンク群が決定されるものとな
る。なお、同じリンク数であっても異なるリンク群から
ＭＣツリーを構成可能である場合には、異なるＭＣツリ
ーとして選択されるものとなる。

【００１９】このように、所定の発端末とすべての着端
末とをマルチキャスト接続するＭＣツリー候補を経由交
換ノード数が少ない順に選択した後、これら各ＭＣツリ
ー候補について、発端末から最も離れた着端末まで最も
少ない経由リンク数で接続するアークを決定するように
したので、従来のように、発端末と各着端末とを結ぶ最
適な経路をそれぞれの着端末ごとに求め、これら最適経
路のうち共通して使用されている部分経路を抽出して共
用化するものと比較して、交換ノード数および経由リン
ク数が最も少ないマルチキャスト接続経路を確実に選択
することができ、ネットワーク資源を効率よく利用し、
かつ伝搬遅延を低減することが可能となる。

【００２０】次に、図２を参照して、本発明によるＭＣ
ツリー構成ノード決定処理について説明する。図２はＭ
Ｃツリー構成ノード決定処理を示すフローチャートであ
り、前述（図１）のステップ１０に相当する処理の一例
である。ここでは、任意の探索中の状態にあるＭＣツリ
ー候補について、その状態におけるすべてのノード候補
を検索し、そのうち着端末を収容する交換ノードすなわ
ちＬＦ収容ノードに到達したものあるいは到達する可能
性のあるものをＭＣツリー候補に順次格納することによ
りツリーの探索を実施する。

【００２１】さらに、すべてのＬＦ収容ノードに到達し
た時点で探索を終了し、これら探索終了ツリーのうち交
換ノード数の小さい順に所望のＭＣツリー候補として出
力するものとなる。なお、以下の説明において、探索処
理対象となるＭＣツリー候補を示す交換ノード数および
各交換ノードの集合をｍｔｎ（）とし、ｍｔｎ（）にて
到達していない残りのＬＦ収容ノードからなる集合をｌ
ｎとする。

【００２２】また、探索中の状態にあるＭＣツリー候補
を示す交換ノード群ｍｔｎ（）および対応する残りＬＦ
収容ノード群ｌｎ（）を交換ノード数数順に保持する集
合をＱとし、探索終了ツリーを交換ノード数順に保持す
る集合をＭＴＮとする。さらに、任意の探索中の状態に
あるＭＣツリー候補におけるすべてのノード候補からな
る集合をａｎとする。

【００２３】図３はＭＣツリー構成ノード決定処理の遷
移を示す説明図であり、前述（図７）のネットワークと
同じ構成となっている。まず、初期化処理として、発端
末を収容する交換ノードすなわちＲＴ収容ノードのみか
らなるＭＣツリー候補を示す交換ノード群をｍｔｎ
（１）としてＱに格納し（ステップ２０）、そのＭＣツ
リー候補の残りＬＦ収容ノード群をｌｎ（１）としてす
べてのＬＦ収容ノードを格納する（ステップ２１）。

【００２４】これにより、Ｑには、探索中ＭＣツリー候
補として、 Ｑ＝｛ ｍｔｎ（１）＝｛１＋２，ａ｝，ｌｎ（１）＝｛ｃ，ｅ｝ ｝ が格納される。なお、ｍｔｎ（）において、最初の要素
は任意の探索状態においてそれぞれのＭＣツリー候補を
構成するのに最低限必要な交換ノード数を示しており、
ここではＲＴ収容ノードａを示す個数「１」と、ＬＦ収
容ノードｃ，ｅを示す個数「２」との和となる。

【００２５】次に、ステップ２２〜３３により、個々の
ＭＣツリー候補に対するツリー探索処理が実施される。
まず、Ｑの先頭から探索中ＭＣツリー候補を取り出す
（ステップ２２）。この場合、後述するようにＱ内のＭ
Ｃツリー候補は個々の交換ノード数順に格納されること
から、ここでは常にＱのうち最も交換ノード数の小さい
探索中ＭＣツリー候補が選択される。

【００２６】取り出された探索中ＭＣツリー候補は、処
理変数ｍｔｎおよびｌｎに格納され、初期化直後ではＱ
は空となる。 ｍｔｎ＝ｍｔｎ（１）＝｛１＋２，ａ｝ ｌｎ＝ｌｎ（１）＝｛ｃ，ｅ｝ Ｑ＝｛｝

【００２７】続いて、ｍｔｎの最初要素である交換ノー
ド数が、探索終了ツリー群ＭＴＮ内の各ＭＣツリー候補
の交換ノード数より小さいか否か、あるいはＭＴＮ内に
探索終了ツリーが存在しないか否か判断する（ステップ
２３）。ここで、ｍｔｎの最初要素である交換ノード数
が、探索終了ツリー群ＭＴＮ内の各ＭＣツリー候補の交
換ノード数より小さい場合、あるいはＭＴＮ内に探索終
了ツリーが存在しない場合には（ステップ２３：ＹＥ
Ｓ）、次のようなノード検索処理および格納判断処理を
開始する。

【００２８】最初に、ｍｔｎの各交換ノードから任意の
ＬＦ収容ノード、および任意のＬＦ収容ノードに到達す
る可能性のある交換ノードのすべてを検索する（ステッ
プ２４）。ここで、図４を参照して、このノード検索方
法について説明する。図４はノード検索方法を示す説明
図であり、ＮＤ１〜ＮＤ１８は交換ノードである。特
に、ＮＤ１（斜線ハッチング）はＲＴ収容ノード、ＮＤ
８，ＮＤ９，ＮＤ１４〜１６，ＮＤ１８（太線）はＬＦ
収容ノードである。

【００２９】この場合には、ＮＤ１はｍｔｎを構成する
唯一の要素（ＲＴ収容ノード）であり、ＮＤ１からのす
べてのノード候補を検索するものとする。まず、ｍｔｎ
内の各要素に隣接するノードのうち、ＬＦ収容ノードま
たは所有アーク数が３本以上のノードを選択する（条件
１）。図４の場合では、ＮＤ１に隣接するＬＦ収容ノー
ドとしてＮＤ１５、ＮＤ１６が選択されるとともに、所
有アーク数が３本以上のノードとしてＮＤ２が選択され
る。

【００３０】次に、ｍｔｎ内の各要素に隣接するノード
のうち、所有アーク数が２本であって、かつそのアーク
で接続されるノードのうちｍｔｎ内のノード以外のもう
一方のノードを選択するとともに、これを条件１のノー
ドが現れるまで繰り返し選択する（条件２）。図４の場
合では、ＮＤ３およびＮＤ４、またＮＤ１３およびＮＤ
１４が一括してノード候補として選択される。

【００３１】また、条件２において、到達ノードがＬＦ
収容ノードでなく、かつ所有アーク数が１本の場合に
は、ノード候補として選択しない（条件３）。図４で
は、ＮＤ１０と、ＮＤ１１およびＮＤ１２とがこれに該
当する。さらに、条件２において、到達ノードがｍｔｎ
内の要素として含まれるノードである場合には、ノード
候補として選択しない（条件４）。図４では、ＮＤ５お
よびＮＤ６がこれに該当する。

【００３２】なお、条件２において、ＬＦ収容ノードを
介してｍｔｎ内の要素であるノードに到達する場合に
は、ｍｔｎ内の要素からそのＬＦ収容ノードへのアーク
のうち、経由ノード数が小さいアークに対応するノード
を優先して選択する（条件５）。図４では、例えばＮＤ
３およびＮＤ４がすでにｍｔｎに含まれている場合、Ｎ
Ｄ４からＮＤ７を介してＮＤ８へ経由するアークより、
ＮＤ４から直接ＮＤ８へ行くアークに対応するノードが
選択される。

【００３３】このようにして、ステップ２４では、ｍｔ
ｎの各交換ノードに接続される任意のＬＦ収容ノード、
および任意のＬＦ収容ノードに到達する可能性のある交
換ノードのすべてが検索される。したがって、図３
（ａ）では、ＲＴ収容ノードａから、ａｎ（１）として
ｂ−ｃ、ａｎ（２）としてｄ−ｅおよびａｎ（３）とし
てｆ−ｇ−ｃという３つのノード候補が検索され、ノー
ド候補群集合ａｎに格納される。 ａｎ＝｛（ｂ，ｃ），（ｄ，ｅ），（ｆ，ｇ，ｃ）｝

【００３４】続いて、ノード検索処理により検索された
ノード候補があったかどうか判断され（ステップ２
５）、１つ以上のノード候補が検索された場合には（ス
テップ２５：ＹＥＳ）、そのノード候補の中から任意の
ノード候補を順に選択し（ステップ２６）、選択した各
ノード候補に対応する交換ノードに対してｍｔｎへ格納
判断処理（ステップ２７〜３１）が行われる。まず、選
択した任意のノード候補により新たに接続されるノード
がＬＦ収容ノードか否か判断する（ステップ２７）。

【００３５】ここで、ＬＦ収容ノードである場合には、
所望のＬＦ収容ノードの１つに到達したことから、その
ＬＦ収容ノードをそのｍｔｎの残り収容ノード群ｌｎか
ら削除する（ステップ２８）。さらに、残り収容ノード
がなくなったかどうか判断し（ステップ２９）、残り収
容ノードがなくなった場合には、ｍｔｎがすべての所望
のＬＦ収容ノードに到達したと判断して、選択したノー
ド候補を含んだｍｔｎを探索終了ツリーとして交換ノー
ド数順にＭＴＮに格納する（ステップ３０）。

【００３６】一方、ステップ２７において、選択した任
意のノード候補により新たに接続されるノードがＬＦ収
容ノードでない場合（ステップ２７：ＮＯ）、およびス
テップ２９において、残り収容ノードがまだある場合
（ステップ２９：ＮＯ）には、選択したノード候補を含
む新たなｍｔｎを生成して、交換ノード数順にＱに格納
する（ステップ３１）。

【００３７】したがって、図３（ａ）において、ノード
候補としてａｎ（１）が選択された場合には、ｌｎから
ＬＦ収容ノードｃが削除され（ステップ２８）、新たな
ｍｔｎがＱに格納される。 ａｎ（１）＝（ｂ，ｃ） ｌｎ＝ｌｎ−（ｃ）＝｛ｅ｝ ｍｔｎ＝ｍｔｎ＋ａｎ（１）＝｛１＋３，ａ，ｂ，ｃ｝ Ｑ＝｛ ｍｔｎ（１）＝｛１＋３，ａ，ｂ，ｃ｝，ｌｎ（１）＝｛ｅ｝ ｝

【００３８】これら、ステップ３０およびステップ３１
を実行した後、ノード候補群ａｎに未選択のノード候補
があるか否か判断し（ステップ３２）、未選択のノード
候補がある場合には（ステップ３２：ＹＥＳ）、前述し
たステップ２６に戻る。したがって、次のノード候補と
してａｎ（２）が選択され、 ａｎ（２）＝（ｄ，ｅ） ｌｎ＝ｌｎ−（ｅ）＝｛ｃ｝ ｍｔｎ＝ｍｔｎ＋ａｎ（２）＝｛１＋３，ａ，ｄ，ｅ｝ Ｑ＝｛ ｍｔｎ（１）＝｛１＋３，ａ，ｂ，ｃ｝，ｌｎ（１）＝｛ｅ｝ ｍｔｎ（２）＝｛１＋３，ａ，ｄ，ｅ｝，ｌｎ（２）＝｛ｃ｝ ｝ となる。

【００３９】さらに、ノード候補としてａｎ（３）が選
択され、 ａｎ（３）＝（ｆ，ｇ，ｃ） ｌｎ＝ｌｎ−（ｃ）＝｛ｅ｝ ｍｔｎ＝ｍｔｎ＋ａｎ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ｝ Ｑ＝｛ ｍｔｎ（１）＝｛１＋３，ａ，ｂ，ｃ｝，ｌｎ（１）＝｛ｅ｝ ｍｔｎ（２）＝｛１＋３，ａ，ｄ，ｅ｝，ｌｎ（２）＝｛ｃ｝ ｍｔｎ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ｝，ｌｎ（３）＝｛ｅ｝ ｝ となる。

【００４０】また、すべてのノード候補の選択が終了し
た場合には（ステップ３２：ＮＯ）、Ｑ内に他のｍｔｎ
があるか否か判断し（ステップ３３）、他のｍｔｎがあ
る場合には（ステップ３３：ＹＥＳ）、前述したステッ
プ２２に戻る。したがって、Ｑの先頭からｍｔｎ（１）
が選択され、ＭＴＮに探索終了ツリーが格納されていな
いことから、図３（ｂ）に示すように、ｍｔｎ（１）の
ノード候補としてａｎ（１）が選択される。

【００４１】 ｍｔｎ＝ｍｔｎ（１）＝｛１＋３，ａ，ｂ，ｃ｝ ｌｎ＝ｌｎ（１）＝｛ｅ｝ Ｑ＝｛ ｍｔｎ（２）＝｛１＋３，ａ，ｄ，ｅ｝，ｌｎ（２）＝｛ｃ｝ ｍｔｎ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ｝，ｌｎ（３）＝｛ｅ｝ ｝

【００４２】 ａｎ＝｛ｅ｝ ａｎ（１）＝（ｅ） ｌｎ＝ｌｎ−（ｅ）＝｛｝ ｍｔｎ＝ｍｔｎ＋ａｎ（１）＝｛１＋３，ａ，ｂ，ｃ，ｅ｝ ＭＴＮ＝｛ ＭＴＮ（１）＝｛１＋３，ａ，ｂ，ｃ，ｅ｝ ｝

【００４３】続いて、Ｑの先頭からｍｔｎ（２）が選択
される。ここで、その交換ノード数「１＋３」が探索終
了ツリー群ＭＴＮ内の各ＭＣツリー候補の交換ノード数
「１＋３」より小さくないことから（ステップ２３：Ｎ
Ｏ）、ＭＴＮ内に探索終了ツリーが所望の通信品質ＱＯ
Ｓなどにより決定される所定数以上格納されているか否
か判断する（ステップ３４）。所定数以上格納されてい
る場合には（ステップ３４：ＹＥＳ）、所望する数だけ
ＭＣツリー候補が得られたと判断して一連のツリー構成
ノード決定処理を終了する。

【００４４】また、ＭＴＮ内に探索終了ツリーが所定数
以上格納されていない場合には（ステップ３４：Ｎ
Ｏ）、ステップ２４に移行して処理を継続する。したが
って、図３（ｃ）に示すように、ｍｔｎ（２）のノード
候補としてａｎ（１）が選択される。 ｍｔｎ＝ｍｔｎ（２）＝｛１＋３，ａ，ｄ，ｅ｝ ｌｎ＝ｌｎ（２）＝｛ｃ｝ Ｑ＝｛ ｍｔｎ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ｝，ｌｎ（３）＝｛ｅ｝ ｝

【００４５】 ａｎ＝｛ｃ｝ ａｎ（１）＝（ｃ） ｌｎ＝ｌｎ−（ｃ）＝｛｝ ｍｔｎ＝ｍｔｎ＋ａｎ（１）＝｛１＋３，ａ，ｄ，ｅ，ｃ｝ ＭＴＮ＝｛ ＭＴＮ（１）＝｛１＋３，ａ，ｂ，ｃ，ｅ｝ ＭＴＮ（２）＝｛１＋３，ａ，ｄ，ｅ，ｃ｝ ｝

【００４６】さらに、Ｑからｍｔｎ（３）が選択された
場合、ＭＴＮ内に２つのＭＣツリー候補が格納されてい
るが、所定数を満足していない場合には、ステップ２４
に戻って図３（ｂ）と同様のアーク選択処理が実行され
る。 ｍｔｎ＝ｍｔｎ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ｝ ｌｎ＝ｌｎ（３）＝｛ｅ｝ Ｑ＝｛｝ ａｎ＝｛ｅ｝ ａｎ（１）＝（ｅ）

【００４７】 ｌｎ＝ｌｎ−（ｅ）＝｛｝ ｍｔｎ＝ｍｔｎ＋ａｎ（１）＝｛１＋４，ａ，ｆ，ｇ，ｃ，ｅ｝ ＭＴＮ＝｛ ＭＴＮ（１）＝｛１＋３，ａ，ｂ，ｃ，ｅ｝ ＭＴＮ（２）＝｛１＋３，ａ，ｂ，ｅ，ｃ｝ ＭＴＮ（３）＝｛１＋４，ａ，ｆ，ｇ，ｃ，ｅ｝ ｝

【００４８】この後、ステップ３３にて、Ｑに他のｍｔ
ｎがないことから（ステップ３３：ＮＯ）、すでに求め
られている集合ＭＴＮを所望のＭＣツリー候補群とし
て、一連のＭＣツリー構成ノード決定処理を終了する。

【００４９】このように、ＭＣツリー構成ノード決定処
理では、探索中の状態にある各ＭＣツリー候補につい
て、その状態におけるすべてのノード候補を検索し、そ
のうち着端末を収容する交換ノードすなわちＬＦ収容ノ
ードに到達したものあるいは到達する可能性のあるもの
をＭＣツリー候補に順次格納することによりツリー探索
処理を実施するようにしたものである。

【００５０】さらに、すべての着端末に到達した時点で
ツリー探索処理を終了し、これら探索終了ツリーを所望
のＭＣツリー候補として出力するようにしたものであ
る。したがって、これら探索終了ツリーを交換ノード数
が少ない順にＭＣツリー候補として出力することによ
り、所定の発端末と複数の着端末とを接続するリンクを
数多く共用してマルチキャスト接続するＭＣツリー構成
ノードを確実に得ることが可能となる。

【００５１】また、Ｑから取り出した探索中ＭＣツリー
候補の交換ノード数が、探索終了ツリー群ＭＴＮの各交
換ノード数より小さくない場合には、ＭＴＮ内に探索終
了ツリーの数が所定数以上格納されているか否か判断
し、所定数以上格納されている場合には、ＭＣツリー構
成ノード決定処理を終了するようにしたので、例えば所
定数として、所望の通信品質ＱＯＳなどにより指定され
るマルチキャスト接続不成功時の繰り返し回数を設定す
ることにより、不要なＭＣツリー候補の探索処理を省く
ことが可能となるとともに、交換ノード数順に通信品質
を満足する数のＭＣツリー候補を得ることが可能とな
る。

【００５２】また、ノード検索方法として、ｍｔｎ内の
各要素に隣接するノードのうち、ＬＦ収容ノードまたは
所有アーク数が３本以上のノードを選択し（条件１）、
また所有アーク数が２本であって、かつそのアークで接
続されるノードのうちｍｔｎ内のノード以外のもう一方
のノードを選択するとともに、これを条件１のノードか
現れるまで繰り返し選択する（条件２）ようにしたの
で、ｍｔｎ構成に変化がないノードについては一括して
選択することが可能となり、処理に要する時間を短縮す
ることができる。

【００５３】また、条件２において、到達ノードがＬＦ
収容ノードでなく、かつ所有アーク数が１本の場合（条
件３）、さらには、条件２において、到達ノードかｍｔ
ｎ内の要素として含まれるノードである場合（条件４）
には、ノード候補として選択せず、また条件２におい
て、ＬＦ収容ノードを介してｍｔｎ内の要素であるノー
ドに到達する場合には、ｍｔｎ内の要素からそのＬＦ収
容ノードへのアークのうち、経由ノード数が小さいアー
クに対応するノードを優先して選択する（条件５）よう
にしたので、不要なアークを削除して、その後の選択し
た各ノード候補に対するｍｔｎへの格納判断処理に要す
る時間を短縮することが可能となる。

【００５４】次に、図５を参照して、本発明によるＭＣ
ツリー構成アーク決定処理について説明する。図５はＭ
Ｃツリー構成アーク決定処理を示すフローチャートであ
り、前述（図１）のステップ１２に相当する処理の一例
である。ここでは、前述のＭＣツリー構成ノード決定処
理（ステップ１０）により選択された各ＭＣツリー候補
について、発端末から最も離れた着端末までの経由リン
ク数が最も小さい接続経路を決定するものとなる。

【００５５】図６はＭＣツリー構成アーク決定処理を示
す遷移図であり、（ａ）はＭＣツリー構成ノード決定処
理により選択されたＭＣツリー候補の構成を示してお
り、（ｂ）は一般的な深さ優先探査方法に基づいてアー
クを決定した場合、（ｃ）は本発明の幅優先探査方法に
基づいてアークを決定した場合のＭＣツリーを示してい
る。図６において、ＮＤ１〜ＮＤ７は交換ノードであ
り、特にＮＤ１は（斜線ハッチング）ＲＴ収容ノード、
ＮＤ３〜ＮＤ５、ＮＤ７（太線）はＬＦ収容ノードであ
る。

【００５６】まず、初期化処理として、所望のＭＣツリ
ーにＲＴ収容ノードを格納する（ステップ５０）。次
に、ＭＣツリーから最も着端末よりの交換ノード群ＬＮ
（）を抽出し（ステップ５１）、そのうちからいずれか
の交換ノードＬＮ（ｉ）を選択する（ステップ５２）。

【００５７】続いて、ＬＮ（ｉ）に関するアーク探索処
理として、探索中ＭＣツリーに含まれていない残りの交
換ノードのうち、ＬＮ（ｉ）にリンクを介して直接接続
される交換ノード群ＭＮＬ（）を抽出し（ステップ５
３）、そのうちからいずれかの交換ノードＭＬＮ（ｋ）
を選択する（ステップ５４）。ここで、ＭＬＮ（ｋ）が
存在するか否か判断し（ステップ５５）、存在する場合
には（ステップ５５：ＹＥＳ）、ＬＮ（ｉ）からＭＬＮ
（ｋ）へのアーク、ここではリンクおよびＭＬＮ（ｋ）
を探索中ＭＣツリーに格納する（ステップ５６）。

【００５８】この後、ステップ５４に戻って、他のＭＬ
Ｎ（ｋ）を選択し、ＭＬＮ（ｋ）が存在しなくなった場
合には（ステップ５５：ＮＯ）、すべてのＬＮ（ｉ）を
選択したか否か判断する（ステップ５７）。ここで、他
のＬＮ（ｉ）が存在する場合には（ステップ５７：Ｎ
Ｏ）、ステップ５２に戻って、新たなＬＮ（ｉ）を選択
し前述したアーク探索処理を実施する（ステップ５３〜
５６）。

【００５９】一方、すべてのＬＮ（ｉ）を選択した場合
には（ステップ５７：ＹＥＳ）、探索中ＭＣツリーに含
まれていない残りの交換ノードが存在するか否か判断し
（ステップ５８）、まだ残りの交換ノードが存在する場
合には（ステップ５８：ＹＥＳ）、ステップ５１に戻っ
て、探索中ＭＣツリーから最も着端末よりの交換ノード
群ＬＮ（）を新たに抽出するとともに、各ＬＮ（ｉ）に
関するアーク探索処理を実施する。

【００６０】すべての交換ノードがＭＣツリーに含ま
れ、残りの交換ノードがなくなった場合には（ステップ
５８：ＮＯ）、一連のＭＣツリー構成アーク決定処理を
終了する。したがって、図６（ａ）のＭＣツリー候補で
は、最初にＲＴ収容ノードであるＮＤ１がＮＬ（ｉ）と
して選択され、ＮＤ２およびＮＤ６がそれぞれＭＮＬ
（ｋ）として選択されて探索中ＭＣツリーに格納され
る。

【００６１】続いて、ＮＤ２およびＮＤ６がＮＬ（ｉ）
として選択され、ＮＤ２については、ＮＤ３およびＮＤ
４がＭＮＬ（ｋ）として選択されて探索中ＭＣツリーに
格納されるとともに、ＮＤ６については、ＮＤ５および
ＮＤ７がＭＮＬ（ｋ）として選択されて探索中ＭＣツリ
ーに格納され、残りの交換ノードがなくなったことから
処理が終了する。これにより、図３（ｃ）のようなＭＣ
ツリーが決定される。

【００６２】一方、一般的な深さ優先探査方法により、
任意に選択したアークがそれ以上アークのないＬＦ収容
ノードに到達するまで、繰り返しアークを選択するよう
にした場合には、図３（ｂ）のようなＭＣツリーとな
る。すなわち、ＮＤ１から例えばＮＤ２が選択された場
合には、その先のＮＤ３が選択された後、ＮＤ２に戻っ
てＮＤ４が選択され、さらにその先のアークとして、Ｎ
Ｄ５，ＮＤ６およびＮＤ７が選択されるものとなる。

【００６３】したがって、この場合のようにＮＤ１から
ＮＤ７までの経由リンク数が５となるのと比較して、図
３（ｃ）ではすべてのＬＦ収容ノードまでの経由リンク
数が２以内となり、より少ない経由リンク数でマルチキ
ャスト接続することが可能となり、発端末から各着端末
までの伝搬遅延を低減させることができる。

【００６４】

【発明の効果】以上説明したように、本発明は、発端末
とすべての着端末とをマルチキャスト接続するＭＣツリ
ー候補を経由交換ノード数が少ない順に選択するＭＣツ
リー構成ノード決定処理を実行し、これら各ＭＣツリー
候補について、発端末から最も離れた着端末までを最も
少ない経由リンク数で接続するアークを決定するＭＣツ
リー構成アーク決定処理を実行するようにしたので、従
来のように、発端末と各着端末とを結ぶ最適な経路をそ
れぞれの着端末ごとに求め、これら最適経路のうち共通
して使用されている部分経路を抽出して共用化するもの
と比較して、交換ノード数および経由リンク数が最も少
ないマルチキャスト接続経路を確実に選択することがで
き、ネットワーク資源を効率よく利用し、かつ伝搬遅延
を低減することが可能となる。

【００６５】また、ＭＣツリー構成ノード決定処理で
は、探索中の状態にある各ＭＣツリー候補について、そ
の状態におけるすべてのノード候補を検索し、これらノ
ード候補のうちいずれかの着端末を収容する交換ノード
に到達したものあるいは到達する可能性のあるものを探
索中のＭＣツリー候補に順次格納することによりＭＣツ
リーの探索を実行し、探索中ＭＣツリー候補が各着端末
を収容するすべての交換ノードに到達した時点で探索を
終了し、これら各探索終了ツリーを所望のＭＣツリー候
補として出力するようにしたので、所定の発端末と複数
の着端末とを接続するリンクをより共用してマルチキャ
スト接続するＭＣツリー構成ノードを確実に得ることが
可能となる。

【００６６】さらに、探索中ＭＣツリー候補の交換ノー
ド数が、各探索終了ツリーの交換ノード数より小さくな
い場合には、探索終了ツリーの数が所定数以上得られて
いるか否か判断し、所定数以上得られている場合には、
ＭＣツリー構成ノード決定処理を終了するようにしたの
で、例えば所定数として、所望の通信品質ＱＯＳなどに
より指定されるマルチキャスト接続不成功時の繰り返し
数を設定することにより、不要なＭＣツリー候補の探索
処理を省くことが可能となるとともに、交換ノード数順
に通信品質を満足する数のＭＣツリー候補を得ることが
可能となる。

【００６７】ＭＣツリー構成アーク決定処理では、探索
中ＭＣツリーの交換ノードのうち最も着端末よりの交換
ノードをそれぞれ選択し、ＭＣツリー候補を構成する交
換ノードのうち探索中ＭＣツリーに含まれていない残り
の交換ノードから、選択された交換ノードに隣接する交
換ノードへのアークを順次選択して探索中ＭＣツリーに
含めるアーク探索を実行し、各着端末を収容するすべて
の交換ノードが探索中ＭＣツリーに含まれた時点でアー
ク探索を終了し、そのアーク探索終了ツリーを所望のＭ
Ｃツリーとして出力するようにしたので、より少ない経
由リンク数ですべての着端末をマルチキャスト接続する
ことが可能となり、発端末から各着端末までの伝搬遅延
を低減させることができる。

【図面の簡単な説明】

【図１】 本発明の一実施の形態によるマルチキャスト
接続経路選択方法の処理手順を示すフローチャートであ
る。

【図２】 ＭＣツリー構成ノード決定処理を示すフロー
チャートである。

【図３】 ＭＣツリー構成ノード決定処理の遷移を示す
説明図である。

【図４】 ノード検索方法を示す説明図である。

【図５】 ＭＣツリー構成アーク決定処理を示すフロー
チャートである。

【図６】 ＭＣツリー構成アーク決定処理の遷移を示す
説明図である。

【図７】 従来のマルチキャスト接続経路選択方法を示
す説明図である。

【符号の説明】

１１…ＭＣツリー構成ノード決定処理、１３…ＭＣツリ
ー構成アーク決定処理、ＲＴ…発端末、ＬＦ１，ＬＦ２
…着端末、ａ〜ｇ，ＮＤ１〜ＮＤ１８…交換ノード。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平８−242226（ＪＰ，Ａ) 昭和63年信学秋季大会、Ｂ−147、ｐ. Ｂ−２−23 1990年信学春季大会、Ｂ−587、ｐ. ３−165 1995年信学総合大会、Ｂ−825、ｐ. 271 1995年信学総合大会、ＳＢ−４−１、 ｐ．639 (58)調査した分野(Int.Cl.⁶，ＤＢ名) H04L 12/18

Claims (4)

(57)【特許請求の範囲】
1. 【請求項１】 複数の交換ノードで構成される通信ネッ
   トワークを介して所定の発端末と複数の着端末とを一斉
   に接続するマルチキャスト接続を行う場合に、その接続
   経路を選択するマルチキャスト接続経路選択方法におい
   て、 発端末とすべての着端末とをマルチキャスト接続するＭ
   Ｃツリー候補を経由交換ノード数が少ない順に選択する
   ＭＣツリー構成ノード決定処理を実行し、 これら各ＭＣツリー候補について、発端末とこの発端末
   から最も離れた着端末とを最も少ない経由リンク数で接
   続するアークを決定するＭＣツリー構成アーク決定処理
   を実行するようにしたことを特徴とするマルチキャスト
   接続経路選択方法。
2. 【請求項２】 請求項１記載のマルチキャスト接続経路
   選択方法において、 ＭＣツリー構成ノード決定処理では、 探索中の状態にある各ＭＣツリー候補について、その状
   態におけるすべてのノード候補を検索し、 これらノード候補のうちいずれかの着端末を収容する交
   換ノードに到達したものあるいは到達する可能性のある
   ものを探索中のＭＣツリー候補に順次格納することによ
   りＭＣツリーの探索を実行し、 探索中ＭＣツリー候補が各着端末を収容するすべての交
   換ノードに到達した時点で探索を終了し、各探索終了ツ
   リーを所望のＭＣツリー候補として出力するようにした
   ことを特徴とするマルチキャスト接続経路選択方法。
3. 【請求項３】 請求項２記載のマルチキャスト接続経路
   選択方法において、 探索中ＭＣツリー候補の交換ノード数が、各探索終了ツ
   リーの交換ノード数より小さくない場合には、探索終了
   ツリーの数が所定数以上得られているか否か判断し、所
   定数以上得られている場合には、ＭＣツリー構成ノード
   決定処理を終了するようにしたことを特徴とするマルチ
   キャスト接続経路選択方法。
4. 【請求項４】 請求項１記載のマルチキャスト接続経路
   選択方法において、 ＭＣツリー構成アーク決定処理では、 探索中ＭＣツリーの交換ノードのうち最も着端末よりの
   交換ノードをそれぞれ選択し、 ＭＣツリー候補を構成する交換ノードのうち探索中ＭＣ
   ツリーに含まれていない残りの交換ノードから、前記選
   択された交換ノードに隣接する交換ノードへのアークを
   順次選択して探索中ＭＣツリーに含めるアーク探索を実
   行し、 各着端末を収容するすべての交換ノードが探索中ＭＣツ
   リーに含まれた時点でアーク探索を終了し、そのアーク
   探索終了ツリーを所望のＭＣツリーとして出力するよう
   にしたことを特徴とするマルチキャスト接続経路選択方
   法。