JP2001244929A - マルチキャストルーチング方法、その装置及びプログラム記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 遅延時間の上限値が設定された場合で、ルー
プ（呼損）を小とし、かつツリーコストを低い値とす
る。 【解決手段】 ノード接続時にループを生成することな
く経路設定することを保証し、かつ下流にノード接続を
可能とするようなラベル値（□枠内の数値）を遅延時間
に関する再短路木を用いて算出して各ノードに与えてお
き、マルチキャストツリー構成時には、ソースから書く
ノードまでの遅延時間がそのノードのラベル値を越えな
いように経路を設定する。新規参加ノード＃６は＃３か
＃５に接続可能であるが、経路＃６−＃３―＃４−ソー
スでは遅延時間が５（＝３＋１＋１）で許容最大値５を
越えないが、経路＃６−＃５−＃４−ソースは遅延時間
が６（＝４＋１＋１）となり、５を越えるので前者の経
路を設定する。複数の経路で遅延時間条件を満たす場合
はそのうちで経路コストが最小のものを設定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は通信ネットワーク
を通じて複数のノードへ同一情報を同時に配信するマル
チキャスト通信サービスにおいて、特に情報を送信する
ソースから各受信ノードまでの遅延時間の上限値が設定
され、マルチキャスト通信に参加あるいは離脱するノー
ドが逐次的に発生する場合の、新規参加ノードをマルチ
キャストツリーへの接続を行うためのルーチング方法、
その装置及びそのプログラム記録媒体。

【０００２】

【従来の技術】情報通信ネットワーク上で行われるマル
チキャスト通信サービスは、複数の受信者に対して同一
の情報を同時に配信することができる。マルチキャスト
通信を用いれば、ネットワークの負荷をあげることなく
情報を複数の受信者に同時に送信することが可能とな
る。マルチキャスト通信サービスでは、ソースからの情
報は分岐点となるノードで情報をコピーし、受信者が接
続されるノードの方路にあたるリンクにその情報は転送
される。また、マルチキャスト通信サービスでは参加者
がマルチキャスト通信に参加／離脱することが動的に発
生し、インターネットやＡＴＭにおいても途中参加／離
脱が可能となる規定がなされている。

【０００３】また、それらマルチキャストサービスの多
くにはソースから各受信ノードまでの遅延時間に制約が
付く場合が想定される。例えば、テレビ会議では参加者
間に違和感を与えない範囲での遅延時間を保証する必要
がある。動的マルチキャストリンクのコストにだけ注目
した従来の動的マルチキャストルーチングアルゴリズム
について述べる。

【０００４】グリーディアルゴリズム（ｇｒｅｅｄｙ
ａｌｇｏｒｉｔｈｍ）では、新規にマルチキャストグル
ープに参加するノードは、既存参加ノードの中で最も低
コストで接続可能なノードに接続する。このアルゴリズ
ムは最適に近いマルチキャストツリーコストとなること
が報告されている。これ以外の従来のアルゴリズムとし
て、事前に決められたツリーである最短路木（ｓｈｏｒ
ｔｅｓｔ ｐａｔｈ ｔｒｅｅ）を用いるものがある
（以下、刈り込みＳＰＴと呼ぶ）。刈り込みＳＰＴで
は、ネットワーク内にコアあるいはランデブーポイント
（以下、単にコア）と呼ばれるソース以外のノードを設
定し、ソースはコアに対して最短経路に沿ってデータを
送信し、コアからは各ノードへコアを根とする最短路木
に沿ってデータを送信する。ただし、マルチキャストへ
の参加ノードを含まない経路には送信しない。刈り込み
ＳＰＴでは事前にマルチキャストツリーが構成されるの
で、グリーディアルゴリズムに比べて実装が容易であ
る。ただし、刈り込みＳＰＴはグリーディアルゴリズム
に比べてマルチキャストツリー全体のコストは高くな
る。また、刈り込みＳＰＴのＳＰＴの代わりに最小路木
（ＭＳＴ：ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅ
ｅ）を用いたものも同様に考えられる（以下、刈り込み
ＭＳＴと呼ぶ）。 遅延時間制約付き動的マルチキャスト 遅延時間制約付き動的マルチキャストのルーチングアル
ゴリズムとして提案されたものに、ホングリーパーク
（Ｈｏｎｇ−Ｌｅｅ−Ｐａｒｋ）らのアルゴリズムがあ
る。彼らのアルゴリズムでは、各リンクごとにコストと
遅延時間を合成して新たなコストとし、各リンクにその
新たなコストｅを付与し、ｅに基づいた最短経路を算出
する。接続先の既存参加ノードは、グリーディアルゴリ
ズムと同様に最小のｅ合計値となる経路となるものが選
択され、新規参加ノードはその既存参加ノードに接続さ
れて、既存のマルチキャストツリーに接続される。ただ
し、適切な接続先の既存参加ノードを選定するために、
異なるコストｅについて繰り返し計算する必要がある。
このアルゴリズムは、比較的低コストのマルチキャスト
ツリーを構成することができる。

【０００５】しかしながら、ツリーにループが生成され
る可能性がある。その例を図６を用いて説明する。図中
太い線は既存リンク（マルチキャストツリーに使用され
ているリンク）、細い線はマルチキャストツリーに使用
されていないリンク、白丸はマルチキャスト通信に既に
参加しているノード（既存参加ノード）、黒丸はマルチ
キャスト通信に参加していないノード（非参加ノード）
を示し、各リンクに付けた二つの数字中の左の数字はそ
のリンクのコスト、右の数字はそのリンクの遅延時間を
それぞれ示し、ソースから受信ノードまでの許容遅延時
間の上限値を５とした場合である。この例では、ソース
およびノード＃１，＃３，＃４，＃５が既存参加ノード
である。新たに、ノード＃６から参加要求があった際、
これら既存参加ノードのいずれかに接続されることにな
る。これら既存参加ノードの内、ループが生成すること
なく接続できるのは、ノード＃３と＃５であるが、ソー
スからこれらノード＃３，＃５までのそれぞれの遅延時
間は既に、３（＝２＋１）と５（＝２＋１＋１＋１）に
なっており、新たにノード＃６をノード＃３又は＃５に
接続すれば、ノード＃６までの遅延時間はそれぞれ６、
８となり遅延時間制約値５を超えてしまうことになる。
そこで、接続先としてソースが選ばれ、その経路として
（＃６→＃３→＃４→ソース）が選択されることにな
る。この場合には、ノード＃３と＃４とで、同一のマル
チキャストツリー内のパケットが転送されることとな
り、ループが生成されることになる。また、ループが生
成される場合には、新規参加ノードの参加要求が拒否
（ここでは、呼損と呼ぶ）されるものとみなすこともで
きる。

【０００６】つまりソースから送信する情報には受信先
ノードのアドレスの全てが付けられ、各受信ノードでは
受信情報を同時に受信したアドレスの中の下流側のノー
ドに転送する。従って、新規参加ノード＃６をノード＃
４に接続した場合は、ソースから情報にノード＃１、＃
３、＃４、＃５、＃６が付けられ、ノード＃１と＃４に
送信され、ノード＃４はノード＃３と＃５が下流側とな
り、ノード＃１から転送されノード＃３に受信された情
報はノード＃４と＃５が下流側となるが、ノード＃３で
はその転送に当って、ノード＃１からの受信とノード＃
４からの受信とを区別することができず、同様にノード
＃４ではその転送に当ってソースからの受信とノード＃
３からの受信とを区別できず、ノード＃３はノード＃４
からの受信情報をノード＃４側へ再転送し、ノード＃４
はノード＃３からの受信情報をノード＃３へ再転送し、
ノード＃３と＃４の間で相互に転送するループが生じ
る。

【０００７】他の遅延時間制約付き動的マルチキャスト
のルーチングアルゴリズムとして、前述の刈り込みＳＰ
Ｔと刈り込みＭＳＴのそれぞれを拡張したものが考えら
れる。つまり刈り込みＳＰＴではコストに関する最短路
木を用いていたが、それを遅延時間に関する最短路木に
置き換える方法がある（刈り込み遅延時間ＳＰＴ：ｐｒ
ｕｎｅｄ ｄｅｌａｙ−ＳＰＴと呼ぶ）。このアルゴリ
ズムでは、ソースから各ノードまでの遅延時間が最小と
なる経路が常に選ばれることとなる。また、刈り込みＭ
ＳＴはリンクのコストに関する最小路木を用いていた
が、それを遅延時間制約付きのコストに関する最小路木
に置き換える方法がある（刈り込み遅延時間制約付きＭ
ＳＴ：ｐｒｕｎｅｄ ｄｅｌａｙ−ｃｏｎｓｔｒａｉｎ
ｅｄ ＭＳＴと呼ぶ）。遅延時間制約付きの最小路木
は、これまでに提案されてきた遅延時間制約付き静的マ
ルチキャストのためのルーチングアルゴリズムを用いる
ことによって構成することができる。これらのアルゴリ
ズムでは、ソースから各ノードまでに遅延時間制約を満
足する経路が存在するならば、それぞれのノードからの
接続要求を拒否されず、かつ経路にループも生成されな
い。

【０００８】しかしこれら刈り込み遅延時間ＳＰＴや刈
り込み遅延時間ＳＭＴは、後で明らかにするが、何れも
マルチキャストツリー全体のコストが高くなる欠点があ
る。

【０００９】

【発明が解決しようとする課題】この発明の目的は呼損
をできるだけ少なく抑え、かつ低コストのマルチキャス
トツリーを構成することができるマルチキャストルーチ
ング方法、その装置及びプログラム記録媒体を提供する
ことにある。

【００１０】

【課題を解決するための手段】この発明では、マルチキ
ャスト通信に各ノードが逐次的に参加／離脱するマルチ
キャストサービスを対象とし、またマルチキャスト通信
に既に参加しているノードに対しては、当該マルチキャ
スト通信から当該ノードが離脱するまで、ソースから当
該ノードへの情報転送経路の変更は行わないものとす
る。この発明の方法によれば、各ノードにラベル値を予
め付与する。ノードｉのラベル値はΔ−ｍａｘ｛ｄｅｌ
ａｙ（Ｌ_ij）｜ｊ∈Ｖ_leaf(i)｝とする。Ｌ_ijはソース
を根とする遅延時間に関する最短路木上のノードｉから
ｊまでの経路を、Ｖ _leaf(i)はその最短路木上でノード
ｉに中継されるノードの集合を示す。例えば図４Ａに示
すようにソースを根とする最短路木が構成されている場
合に、ノード＃ｉに中継されているノードの集合Ｖ
_leaf(i)は｛＃ｊ１，＃ｊ２，＃ｊ３｝となる。Δはソ
ースから受信ノードまでの許容遅延時間の上限値を示
し、通常はシステムにより決まる、ｄｅｌａｙ（Ｌ）は
経路（Ｌ）における遅延時間を示す。図４Ａに示した例
ではｄｅｌａｙ（Ｌｉｊ₁ ），ｄｅｌａｙ（Ｌｉｊ
₂ ），ｄｅｌａｙ（Ｌｉｊ₃ ）の内の最大のｄｅｌａｙ
（Ｌｉｊ₃ ）をΔから差し引いた値がノード＃ｉのラベ
ル値となる。

【００１１】新規参加ノードからマルチキャスト通信へ
の接続要求が発生すると、その新規参加ノードを前記マ
ルチキャスト通信のマルチキャストツリーに接続するこ
とができる経路候補を求め、これら各経路候補から、そ
の経路上の各ノードのソースからの遅延時間が、そのノ
ードのラベル値を超えない経路候補を選択し、その選択
された経路候補が複数の場合はその各経路候補中のコス
トが最小のものを新規接続経路とし、前記選択した候補
が１つの場合はその候補を新規接続経路として、新規参
加ノードをマルチキャストツリーに接続する。

【００１２】

【発明の実施の形態】この発明の理解を速めるめに、こ
の発明による新規参加ノードのマルチキャストネットワ
ークへの接続例を図１を参照して説明する。図１におい
て太い実線はマルチキャスト通信に現に利用しているリ
ンクを示す。つまり太実線の全体が既存のマルチキャス
トツリーを構成する。細い線は現在の所マルチキャスト
通信に利用されていないリンクを示す。白丸はマルチキ
ャスト通信に参加している既存参加ノードを、黒丸はマ
ルチキャスト通信に参加していないノードを示す。各リ
ンクの横に付けられた２つの数字の左側のものはリンク
コスト、右側のものはリンク遅延時間をそれぞれ示す。
更に各ノードの４角枠内に記入された数字はそのノード
のラベル値であり、これは前記Δ−ｍａｘ｛ｄｅｌａｙ
（Ｌ_ij）｜ｊ∈Ｖ _leaf(i)｝により計算された値であ
る。ソースからノードまでの許容遅延時間の上限値を５
とした場合である。

【００１３】この発明では新規参加ノードをマルチキャ
ストツリー（既存の参加ノード）に接続する際に、その
経路上の各ノードのソースからの遅延時間がそのノード
のラベル値を超えないようにされる。また各ラベル値
は、各ノードの接続時にループを生成することなく経路
を設定することを保証する値が付与される。従ってノー
ド＃３はソース＃１−＃３の経路で接続しようとする
と、この経路の遅延時間は３（＝２＋１）であるが、ノ
ード＃３のラベル値は２であり、遅延時間がラベル値を
超えるため、この経路による接続は許されない。一方、
ソース＃４−＃３なる経路においてはソース−＃４間の
遅延時間は１であり、ノード＃４のラベル値は１である
から、ノード＃４のこの接続は認められ、更にソース−
＃４−＃３の遅延時間は２（＝１＋１）であり、ノード
＃３のラベル値は２であるから、この経路によるノード
＃３の接続も認められて、このようなマルチキャストツ
リーが構成されている。

【００１４】この構成は、ノード＃６が新規にマルチキ
ャスト通信に参加する場合、ノード＃６のため経路（＃
６→＃３→＃４→ソース）を確保しているものであり、
ノード＃６をこの経路により接続しても、ループは生じ
ない。さらに、各ノードのラベル値は遅延時間に関する
最短路木を用いて算出されることからループが生じな
い。またこのラベル値の算出方法ではラベル値は各ノー
ドに付与可能な最大値となっている。ラベル値は将来の
他ノードのマルチキャスト参加時における経路を確保し
ておくためのものであり、ループを生成しないという意
味では、必ずしも大きな値である必要はない。しかしな
がら、ノードの接続要求時においては、新規参加ノード
から既存のツリーまででの経路は、経路上の各ノードで
の遅延時間が各ラベル値以下である経路の内、最小コス
トの経路が選択される。すなわち、既存のツリーまでで
の経路は、グリーディアルゴリズムと同様の考え方に従
っている。よって、選択可能な経路の候補が多いほどツ
リーコストを低く抑えることができることが期待され
る。ここでは、ラベル値は付与可能な最大値となってい
ることから、選択可能な経路の候補数を多くすることが
できる。

【００１５】以上のようなルーチング制御を行うため、
マルチキャスト通信サービスを行う通信ネットワークの
ソース、ノードの何れか、又は全てに、あるいは単独の
管理サーバにマルチキャストルーチング制御装置が設け
られる。マルチキャストルーチング制御装置は例えば図
２に示す機能構成を備えている。この制御装置はネット
ワーク情報記憶部１１にその通信ネットワークの構成、
各リンクの遅延時間とリンクのコスト、更に各ノードの
ラベル値などのネットワーク情報が記憶されている。各
ノードのラベル値は先に述べたΔ−ｍａｘ｛ｄｅｌａｙ
（Ｌ_ij）｜ｊ∈Ｖ_leaf(i)｝により予め計算され、記憶
されてある。またツリー情報記憶部１２に現にマルチキ
ャスト通信に参加している各参加ノードの番号と、その
ソースとの経路情報などのツリー情報が記憶されてい
る。経路情報はそのノードのソース側の直前のノード番
号のみでよい。この経路情報の全体によりマルチキャス
トツリーを構成することができる。このツリー情報記憶
部１２はマルチキャスト通信に新規参加ノードが加われ
ばそのノード番号と経路情報が書込まれ、マルチキャス
ト通信から離脱するノードがあれば、そのノード番号と
対応経路情報が消去される。

【００１６】マルチキャスト通信に新規に参加する要求
は参加要求受付部１３で受付けられる。この参加要求は
マルチキャストルーチング制御装置が設けられているノ
ード（又はサーバ、ソース）に、新規参加要求ノードか
ら通信ネットワークを通じる通信により行われ参加要求
受付部１３に受信される。また新規参加ノードにマルチ
キャストルーチング制御装置が設けられている場合は、
そのノードに接続された端末、例えばパーソナルコンピ
ュータから入力された参加要求が参加要求受付部１３に
入力される。

【００１７】経路候補作成部１４は新規参加ノード番
号、記憶部１１のネットワーク情報、記憶部１２のツリ
ー情報が入力され、新規参加ノードを既存のマルチキャ
ストツリー（の既存参加ノード）に接続することが可能
な経路候補を作成する。遅延時間計算部１５は経路候補
と、ネットワーク情報、特にリンク遅延時間が入力さ
れ、その経路候補の経路上の各ノードのソースからの遅
延時間を計算する。

【００１８】経路候補選択部１６は経路候補の経路上の
各ノードのソースからの遅延時間と、ネットワーク情
報、特にラベル値とが入力され、各ノードまでの遅延時
間がそのノードのラベル値以下である経路候補を選択す
る。選択候補数判定部１７は選択された経路候補数が１
個以上か否かを判定する。経路コスト計算部１８は選択
経路候補と、ネットワーク情報、特にリンクコストが入
力され、その経路候補のコストが計算される。選択され
た経路候補中のコストが最小のものが最小コスト経路候
補検出部１９で決定される。

【００１９】経路接続処理実行部２１は新規接続経路が
入力され、送受信部２２を介して通信ネットワークを制
御して新規参加ノードを新規接続経路を通じて既存マル
チキャストツリーに接続する。制御部２３は参加要求受
付部１３からの参加受付けを入力して、記憶部１１，１
２の読出し、記憶部１２の書込み、経路候補作成部１
４、遅延時間計算部１５などの各部に必要な入力を与え
て動作させ、その結果を必要に応じて一次記憶部２４に
一時記憶させ、最終的には参加要求に応じた新規参加ノ
ードをマルチキャストツリーに接続することを行わせ
る。

【００２０】次に新参加要求が発生した場合の処理手順
を図３を参照して説明する。受付部１３に参加要求を受
付けると（Ｓ１）、記憶部１１からネットワーク情報
を、記憶部１２からツリー情報を読出し（Ｓ２）、経路
候補作成部１４で、参加要求ノードをマルチキャストツ
リーに接続することができる経路の候補を全て作成し、
これら経路候補を一時記憶部２４に保存する（Ｓ３）。
例えば図４Ｂに示すようにノード＃６が新規参加要求す
ると経路候補Ｒ１，Ｒ２，…が作成されて記憶部２４に
一時記憶される。

【００２１】次に経路候補の１つを記憶部２４から取出
し、またネットワーク情報中のリンク遅延時間を取出し
て（Ｓ４）、その経路候補の経路上の各ノードのソース
からの遅延時間を遅延時間計算部１５で計算する（Ｓ
５）。その計算した各ノードの遅延時間がそのノードの
ラベル値を超えたものがないかを経路候補選択部１６で
調べる（Ｓ６）。つまり図４Ｂ中の経路候補Ｒ１につい
てみれば、ソース−＃１間の遅延時間がノード＃１のラ
ベル値を超えていないか、ソース＃１−＃２の遅延時間
がノード＃２のラベル値を超えていないか、ソース−＃
１−＃２−＃３の遅延時間がノード＃３のラベル値を超
えていないか、ソース−＃１−＃２−＃３−＃６の遅延
時間がノード＃６のラベル値を超えていないかを調べ、
これらの何れかの遅延時間がラベル値を超えている場合
はその経路候補を外し、何れの遅延時間もラベル値を超
えていない場合はその経路候補を選択経路候補として一
時記憶部２４に保存する（Ｓ７）。

【００２２】次にこの遅延時間がラベル値を超えないか
の検査をしていない経路候補が残っているかを調べ（Ｓ
８）、残っている場合はステップＳ４に戻って別の経路
候補を取出し、その遅延時間がラベル値を超えないかの
検査を同様に行うことを繰返す。ステップＳ８で検査し
ていない経路候補が残っていない場合は、選択経路候補
が１つであるかを選択候補数判定部１７で判定し（Ｓ
９）、１つでなければ、一時記憶部２４から選択経路候
補を１つ取出し、また記憶部１１からリンクコストを取
出し（Ｓ１０）、その選択経路候補の経路コストを経路
コスト計算部１８で計算し、その計算結果をその候補と
共に記憶部２４に一時記憶する（Ｓ１１）。

【００２３】次にコスト計算をしていない選択経路候補
が残っているかを調べ（Ｓ１２）、残っている場合はス
テップＳ１０に戻って別の選択経路候補のコスト計算を
行い、経路コストを計算していない選択経路候補が残っ
ていないならば、記憶部２４から各選択経路候補ごとの
経路コストを読出し（Ｓ１３）、これらのうち経路コス
トが最も小さい選択経路候補を最小コスト経路候補検出
部１９で検出して、この候補を新規接続経路とする（Ｓ
１４）。

【００２４】ステップＳ９で選択経路候補が１つの場合
は、その選択経路候補を新規接続経路と決定する（Ｓ１
５）。以上のようにして決定された新規接続経路を接続
する処理を経路接続処理実行部２１により行って新規参
加ノードをマルチキャストツリーに接続する（Ｓ１
６）。上述において、経路候補を１つ作成するごとに、
その遅延時間からレベル値を超えたものがないかの検査
を行って選択経路候補か否かの判定を行なってもよい。
また選択経路候補と決定されると、これに対し、直ちに
その経路コストを計算してもよい。

【００２５】図２中の各機能を、コンピュータにプログ
ラムを解読実行させて行うようにしてもよい。

【００２６】

【発明の効果】以上述べたこの発明によるマルチキャス
トルーチング方法が優れていることをコンピュータシミ
ュレーションにより示す。ここでは、マルチキャスト通
信のネットワークとして次のようなモデルを考える。評
価モデルとして、従来のマルチキャストルーチンング方
法の評価において利用されてきたランダムグラフを用い
る。ランダムグラフでは、ノードを表わすＮ個の接点を
平面上に配置し、リンクを表わす接点のペア（ｕ，ｖ）
の枝の発生率を

【００２７】

【数１】

【００２８】で与える。ただし、ｅ′は平均次数（ある
ノードに接続されるリンクの数の平均）、ｋはノードペ
アの平均距離を決定するパラメータとする。また、Ｌは
（ｕ，ｖ）の取り得る最大の距離、ｄ（ｕ，ｖ）をｕと
ｖのユークリッド距離、βとαはパラメータで０＜β，
α＜１とする。また、枝のコストをｄ（ｕ，ｖ）で与え
る。さらに、各リンクに対して遅延時間として１を与え
る。すなわち、この評価モデルでは遅延時間制約をホッ
プ数で与えることになる。また、遅延時間制約値Δを、
通常はシステムにより決る値であるが、以下のように与
えるものとする。

【００２９】 Δ＝ρｄmax （Ｔ_c）＋（１−ρ）ｄmax （Ｔ_d） （１） ただし、Ｔ_cをコストに関する最短路木、Ｔdを遅延時間
に関する最短路木、ｄmax（Ｔ）をＴにおけるソースか
ら各ノードまでの遅延時間の最大値とする。また、パラ
メータρ（０＜ρ＜１）を遅延時間制約率（ｄｅｌａｙ
ｂｏｕｎｄ ｒａｔｉｏ）と呼ぶ。このモデルではマ
ルチキャスト通信への参加および離脱を行う。あるノー
ドのマルチキャスト通信への参加の確率を以下のように
与える。

【００３０】Ｐ_c（ｑ）＝｛γ（Ｎ−ｑ）｝／｛γ（Ｎ
−ｑ）＋（１−γ）ｑ｝ ただし、ｑはその時点でマルチキャスト通信に参加して
いるノード数とする。γ（０＜γ＜１）は平衡状態にお
けるマルチキャスト通信に参加しているノード数を決定
し、平均参加ノード数はγＮで与えられる。評価のため
の基本パラメータを図５Ａに示す。また、評価は参加お
よび離脱ごとに算出されるマルチキャストツリー全体の
コストの平均で行う。

【００３１】比較評価では、刈り込み遅延時間ＳＰＴ、
刈り込み遅延時間制約付きＭＳＴと、この発明のラベル
アルゴリズムとを比較する。遅延時間制約付きＭＳＴの
算出には、従来提案されていた静的な遅延時間制約付き
アルゴリズムを用いた。さらに、各アルゴリズムで得ら
れた平均ツリーコストは、参加要求時ごとにマルチキャ
ストツリーを前述の静的な遅延時間制約付きアルゴリズ
ムを用いて再構成する方法（再構成法）で得られたコス
トで正規化した。再構成する方法は参加、離脱ごとに最
適なマルチキャストツリーを構成するものであるから、
再構成ごとに各参加ノードの経路を変更することにな
り、現実には利用できない。しかしツリーコストを小さ
くする点で理想的に近い。しかしこの再構成法を用いて
も必ずしも下限値を求めることができるわけではない
が、下限値に近い値を算出されることが期待できる。ま
た、コスト評価は参加及び離脱ごとに算出されるマルチ
キャストツリー全体のコストの平均で行った。なお、シ
ミュレーションは異なる１０のネットワークを対象にし
て評価を行った。また、ノードの参加／離脱のイベント
数２００００を１度のシミュレーションランとし、更に
初期状態の影響を無くすため各ランの最初のイベント数
２０００までを評価から削除した。

【００３２】異なる平均マルチキャストグループサイズ
のもとでの平均ツリーコストを図５Ｂに示す。△印は刈
込み遅延時間制約付きＳＰＴ、□印は刈込み遅延時間制
約付きＳＭＴ、○印はこの発明のラベルアルゴリズムで
ある。この発明のラベルアルゴリズムは正規化コストが
１に近く、刈り込み遅延時間ＳＰＴおよび刈り込み遅延
時間制約付きＭＳＴよりも、グループサイズによらず常
に再構成法に近いツリーコストとなっている。これは、
ラベルアルゴリズムでは、グリーディアルゴリズムと同
様に新規参加ノード接続時にできるかぎりコスト増加が
少ない経路を選択していることによる。

【００３３】これに対して、刈り込み遅延時間ＳＰＴは
コストを考慮に入れることなく、マルチキャストツリー
を構成するため、グループサイズによらず高いツリーコ
ストとなっている。また、刈り込み遅延時間制約付きＭ
ＳＴでは、グループサイズが小さい時には高コストとな
り、グループサイズが大きい時にはラベルアルゴリズム
に近い低コストとなっている。これは、参加ノード数が
多い時には、遅延時間制約付きＭＳＴが最適に近いマル
チキャストツリーとなっていることによる。

【００３４】以上のようにこの発明方法によれば従来法
よりも低コストのマルチキャストツリーを構成できる。
またラベル値は遅延時間に関する最短路木を用いて算出
され、かつ新規参加ノードを接続するための経路を確保
するような値としているため、ループを生成することな
く経路を設定することが保証され、呼損が少なくなる。

【図面の簡単な説明】

【図１】この発明方法を用いた場合の新規参加ノードの
接続と、通信ネットワーク、既存マルチキャストツリ
ー、各ノードのラベル値などの例を示す図。

【図２】この発明の装置の実施例の機能構成を示すブロ
ック図。

【図３】この発明の方法の実施例の処理手順を示す流れ
図。

【図４】この発明の説明に用いるネットワークとマルチ
キャストツリーの例を示す図。

【図５】Ａは評価実験に用いたパラメータ値を示す図、
Ｂは実験結果を示すグラフである。

【図６】従来の方法を説明するためのネットワーク、マ
ルチキャストツリーなどを示す図。

───────────────────────────────────────────────────── フロントページの続き Ｆターム(参考） 5K030 GA02 GA20 HA08 HC01 HD03 HD09 JA11 JL07 KA01 KA05 LA19 LB05 LD02 LD08 LD18 MB06 MD09 5K051 AA01 AA03 CC02 FF01 FF16 9A001 CC06 GG19

Claims (3)

【特許請求の範囲】
1. 【請求項１】 通信ネットワーク上で、情報を送信する
   ソースから各受信ノードまでの遅延時間に上限値Δが設
   定されているマルチキャスト通信に、参加あるいは離脱
   するノードが逐次的に発生したとき、遅延時間が上記上
   限値Δを超えない経路を用いてマルチキャストサービス
   を行うことができるマルチキャストルーチング方法にお
   いて、 各ノードｉにラベル値（Δ−ｍａｘ｛ｄｅｌａｙ
   （Ｌ_ij）｜ｊ∈Ｖ_leaf(i)｝）を予め付与する過程と、
   ただしＬ_ijはソースを根とする遅延時間に関する最短路
   木上のノードｉからｊまでの経路、Ｖ_leaf(i)は上記最
   短路木上でノードに中継されているノードの集合、ｄｅ
   ｌａｙ（Ｌ）は経路Ｌにおける遅延時間である、 新規参加ノードより上記マルチキャスト通信への接続要
   求が発生し、既存のマルチキャストツリーへ接続する際
   に、新規参加ノードを接続することができる複数の経路
   候補の内、その経路候補上の各ノードのソースからの遅
   延時間が、そのノードのラベル値を超えない経路候補を
   選択し、その選択された経路候補が複数の場合はその内
   の最小コストで接続可能な経路候補を用い、選択された
   経路候補が１つの場合はその経路候補を新規接続経路と
   して用いて、新規参加ノードから既存のマルチキャスト
   ツリーへ接続する過程と、 を有することを特徴とするマルチキャストルーチング方
   法。
2. 【請求項２】 通信ネットワーク上で、情報を送信する
   ソースから各受信ノードまでの遅延時間に上限値が設定
   されているマルチキャスト通信に参加するノードが逐次
   的に発生したときに、その新規参加ノードを既存マルチ
   キャストツリーへ接続するマルチキャストルーチング制
   御装置において、 上記通信ネットワークの構成、各リンクの遅延時間及び
   コスト、各ノードの遅延上限値及び最短路木上の経路の
   遅延時間に関連したラベル値などのネットワーク情報が
   記憶された第１記憶部と、 各参加ノードごとの既存マルチキャストツリーへの接続
   経路などのツリー情報が記憶された第２記憶部と、 参加要求を受付ける手段と、 参加要求したノードと、ネットワーク情報と、ツリー情
   報を入力して、参加ノードを既存マルチキャストツリー
   に接続可能な経路候補を求める経路候補作成手段と、 上記経路候補とネットワーク情報を入力して、その上記
   経路候補上の各ノードのソースからの遅延時間を計算す
   る遅延時間計算手段と、 上記計算した遅延時間と、そのノードのラベル値を入力
   して遅延時間がラベル値以下か否かを判定し、各ノード
   の遅延時間がラベル値以下の経路候補を選択する経路候
   補選択手段と、 選択された経路候補とネットワーク情報を入力して、そ
   の経路候補の経路コストを計算するコスト計算手段と、 上記選択した経路候補が１つの場合はその経路候補を、
   複数の場合は経路コストが最小の経路候補を新規接続経
   路と決定する手段と、 上記決定された新規接続経路の接続処理を実行させる接
   続実行手段と、 上記第１、第２記憶部の読出し、第２記憶部の書込み、
   各手段を機能させる制御を行う制御手段と、 を具備するマルチキャストルーチング制御装置。
3. 【請求項３】 通信ネットワーク上で情報を送信するソ
   ースから各受信ノードまでの遅延時間に上限値が設定さ
   れているマルチキャスト通信に参加するノードが逐次的
   に発したときに、その新規参加ノードを既存マルチキャ
   ストツリーへ接続するマルチキャストルーチング制御装
   置のコンピュータに、 参加要求を受付ける処理と、 ネットワーク情報及びマルチキャストツリー情報から参
   加ノードを既存マルチキャストツリーに接続することが
   できる経路候補を求める処理と、 ネットワーク情報を用いて上記各経路候補上のノードの
   ソースからの遅延時間を求める処理と、 上記各経路候補上の各ノードの遅延時間が、そのノード
   のラベル値より小さいか否かを判定する処理と、 経路候補から、その経路上の各ノードの遅延時間がその
   ノードのラベル値以下である経路候補を選択する処理
   と、 上記選択された経路候補が１つであるか否かを判定する
   処理と、 選択された経路候補が１でない場合は、その各経路候補
   のコストをネットワーク情報を用いて計算する処理と、 上記選択された経路候補が１つと判定されるとその経路
   候補を新規接続経路と決定し、選択された経路候補が１
   つでないと判定されると上記計算したコストが最も小さ
   い経路候補を新規接続経路と決定してその新規接続経路
   の接続処理を実行させる処理と、 を実行させるプログラムを記録した記録媒体。