(57)【要約】【課題】配信パスの性能劣化の発生時等においても、状況に応じた配信ツリーを再構成できる配信ツリー構成装置等に関する技術を提供する。【解決手段】マルチキャスト配信が終了するまで、配信パスのスループット計測、性能の分析及び配信ツリーの構成を繰り返し行う。これにより、ネットワークの物理的な構成を把握していなくても、配信パスの性能劣化に対して状況に応じた配信効率のより高い配信ツリーに切り替えることができる。【選択図】図１
2007235681.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成装置であって、
前記配信ツリーを構成する構成命令に基づき、配信パスの性能に基づいて前記配信ツリーを構成する配信ツリー作成手段と、
前記配信ツリー作成手段に前記構成命令を繰り返し与える情報分析手段と、
を備えることを特徴とする配信ツリー構成装置。
【請求項２】
配信パスの性能としてスループット計測値を記憶するスループット計測値記憶部を備え、
前記配信ツリー作成手段が、前記構成命令を与えられたときに、前記スループット計測値記憶部から前記スループット計測値を読み出し、前記配信ツリーを構成することを特徴とする請求項１に記載の配信ツリー構成装置。
【請求項３】
前記配信ツリー作成手段が構成した配信ツリーを記憶する配信ツリー記憶部をさらに備え、
前記配信ツリー作成手段は、前記スループットに基づいて前記配信ツリーを構成し、前記配信ツリー記憶部に記憶させることを特徴とする請求項１又は請求項２に記載の配信ツリー構成装置。
【請求項４】
予め定められた構成閾値を記憶する構成閾値記憶部をさらに備え、
前記情報分析手段は、前記構成閾値記憶部から前記構成閾値を読み出し、前記スループットと読み出された前記構成閾値とによって前記構成命令を与えるか否かを定めることを特徴とする請求項１から請求項３のいずれか１項に記載の配信ツリー構成装置。
【請求項５】
前記配信ツリー作成手段は、前記構成命令が与えられたときに、前記配信ツリー記憶部から第１の配信ツリーを読み出し、各受信ノードの受信した受信済データ量、前記スループット及び前記第１の配信ツリーに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記配信ツリー記憶部に記憶させることを特徴とする請求項３又は請求項４に記載の配信ツリー構成装置。
【請求項６】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成装置であって、
計測された配信パスのスループットをスループット計測値として記憶するスループット計測値記憶部と、
構成された前記配信ツリーを記憶する配信ツリー記憶部と、
前記配信ツリーを構成する配信ツリー作成手段と、
前記配信ツリー作成手段に前記配信ツリーを構成する構成命令を繰り返し与える情報分析手段と、
前記情報分析手段によって定められた性能劣化原因パスを記憶する性能劣化原因パス記憶部とを備え、
前記配信ツリー作成手段は、
前記構成命令が与えられたときに、前記スループット計測値記憶部から前記スループット計測値を読み出し、前記配信ツリー記憶部から第１の配信ツリーを読み出し、前記性能劣化原因パス記憶部から前記性能劣化原因パスを読み出し、読み出した前記スループット計測値、前記第１の配信ツリー及び前記性能劣化原因パスに基づいて第２の配信ツリーを構成し、前記配信ツリー記憶部に記憶させることを特徴とする配信ツリー構成装置。
【請求項７】
構成閾値を記憶する構成閾値記憶部とをさらに備え、
前記情報分析手段は、
配信パス毎に、前記スループット計測値記憶部から前記スループット計測値を読み出し、前記構成閾値記憶部から前記構成閾値を読み出し、読み出した前記スループット計測値及び前記構成閾値を比較することにより該配信パスが性能劣化パスか否かを定め、性能劣化パスを性能劣化パス記憶部に記憶させる性能調査手段と、
前記性能劣化パス記憶部に記憶された性能劣化パスの集合を読み出し、性能劣化パス毎のスループット計測値を前記スループット計測値記憶部から読み出し、読み出した前記性能劣化パス毎のスループット計測値に基づいて前記性能劣化パスの集合から性能劣化原因パスを定め、定めた性能劣化原因パスを前記性能劣化原因パス記憶部に記憶させる性能劣化原因特定手段と、を含むことを特徴とする請求項６に記載の配信ツリー構成装置。
【請求項８】
前記スループット計測値記憶部から前記スループット計測値を読み出し、読み出した前記スループット計測値に基づいて構成閾値を計算し、前記構成閾値記憶部に記憶させる構成閾値決定手段と、をさらに備えたことを特徴とする請求項７に記載の配信ツリー構成装置。
【請求項９】
各受信ノードの受信したデータの量を受信済データ量として記憶する受信済データ量記憶部と、をさらに備え、
前記配信ツリー作成手段は、前記構成命令が与えられたときに、前記スループット計測値記憶部から前記スループット計測値を読み出し、前記受信済データ量記憶部から前記受信済データ量を読み出し、前記配信ツリー記憶部から第１の配信ツリーを読み出し、前記性能劣化原因パス記憶部から前記性能劣化原因パスを読み出し、読み出した前記スループット計測値、前記受信済データ量、前記第１の配信ツリー及び前記性能劣化原因パスに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記配信ツリー記憶部に記憶させることを特徴とする請求項６から請求項８のいずれか１項に記載の配信ツリー構成装置。
【請求項１０】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成装置であって、
推定された配信パスのスループットをスループット推定値として記憶するスループット推定値記憶部と、
構成された前記配信ツリーを記憶する配信ツリー記憶部と、
前記配信ツリーを構成する配信ツリー作成手段と、
前記配信ツリー作成手段に前記配信ツリーを構成する構成命令を繰り返し与える情報分析手段と、
一定時間毎に、配信パスのスループットを推定し、前記スループット推定値記憶部に記憶させるスループット推定手段と、を備え、
前記配信ツリー作成手段は、
前記構成命令が与えられたときに、前記スループット推定値記憶部から前記スループット推定値を読み出し、前記配信ツリー記憶部から第１の配信ツリーを読み出し、読み出した前記スループット推定値及び前記第１の配信ツリーに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記配信ツリー記憶部に記憶させることを特徴とする配信ツリー構成装置。
【請求項１１】
計測された配信パスのスループットをスループット計測値として記憶するスループット計測値記憶部と、をさらに備え、
前記スループット推定手段は、
スループット推定値更新命令を与えられたときに、前記スループット計測値記憶部から前記スループット計測値を読み出し、読み出した前記スループット計測値に基づいて前記スループット推定値を求め、求めた前記スループット推定値を前記スループット推定値記憶部に記憶させる推定値更新手段と、
前記スループット計測値記憶部から前記スループット計測値を読み出し、前記スループット推定値記憶部から前記スループット推定値を読み出し、各受信ノードの受信した受信済データ量、読み出した前記スループット計測値及び前記スループット推定値に基づいて前記スループット推定値更新命令を前記推定値更新手段に与えるか否かを定める更新条件評価手段とを含むことを特徴とする請求項１０に記載の配信ツリー構成装置。
【請求項１２】
予め定められた構成閾値を記憶する構成閾値記憶部をさらに備え、
前記情報分析手段は、前記スループット推定値記憶部から前記スループット推定値を読み出し、前記構成閾値記憶部から前記構成閾値を読み出し、読み出した前記スループット推定値と前記構成閾値に基づいて前記構成命令を与えるか否かを定めることを特徴とする請求項１０又は請求項１１に記載の配信ツリー構成装置。
【請求項１３】
各受信ノードの受信したデータの量を受信済データ量として記憶する受信済データ量記憶部と、をさらに備え、
前記配信ツリー作成手段は、前記構成命令が与えられたときに、前記スループット推定値記憶部から前記スループット推定値を読み出し、前記受信済データ量記憶部から前記受信済データ量を読み出し、前記配信ツリー記憶部から第１の配信ツリーを読み出し、読み出された前記スループット推定値、前記受信済データ量及び前記第１の配信ツリーによって第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記配信ツリー記憶部に記憶させることを特徴とする請求項１０から請求項１２のいずれか１項に記載の配信ツリー構成装置。
【請求項１４】
前記情報分析手段は、マルチキャストによるデータの配信が終了するまで、その動作を繰り返すことを特徴とする請求項１から請求項１３のいずれか１項に記載の配信ツリー構成装置。
【請求項１５】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
前記配信ツリーを構成する構成命令に基づいて、配信パスの性能に基づいて前記配信ツリーを構成する配信ツリー作成ステップと、
前記配信ツリー作成ステップに前記構成命令を繰り返し与える情報分析ステップと、
を備えることを特徴とする配信ツリー構成方法。
【請求項１６】
配信パスの性能としてスループット計測値を記憶するスループット計測値記憶ステップを備え、
前記配信ツリー作成ステップにおいて、前記構成命令を与えられたときに、前記スループット計測値記憶ステップにおいて記憶された前記スループット計測値を読み出し、前記配信ツリーを構成することを特徴とする請求項１５に記載の配信ツリー構成方法。
【請求項１７】
前記配信ツリー作成ステップにおいて、配信ツリー記憶部に記憶された第１の配信ツリー及び前記スループットに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶させることを繰り返すことを特徴とする請求項１５又は請求項１６に記載の配信ツリー構成方法。
【請求項１８】
前記配信ツリー作成ステップにおいて、前記構成命令を与えられたときに、前記配信ツリー記憶部から第１の配信ツリーを読み出し、各受信ノードの受信した受信済データ量、前記スループット及び読み出した前記第１の配信ツリーに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶させることを繰り返すことを特徴とする請求項１５又は請求項１６に記載の配信ツリー構成方法。
【請求項１９】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
配信パスのスループットと予め定められた構成閾値とに基づいて前記配信ツリーの構成を行うか否かを判断する情報分析ステップと、
前記情報分析ステップにおいて前記構成を行うと判断したときに、配信ツリー記憶部に記憶された第１の配信ツリー及び前記スループットに基づいて第２の配信ツリーを構成する配信ツリー作成ステップと、
前記第２の配信ツリーが構成されたとき、前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶させる配信ツリー記憶ステップと、を繰り返すことを特徴とする配信ツリー構成方法。
【請求項２０】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
配信パス毎の構成閾値を定めるステップと、
スループットが構成閾値に満たない配信パスを性能劣化パスとして記憶する性能劣化パス記憶ステップと、
前記性能劣化パスに基づいて性能劣化原因パスを特定するステップと
前記特定された性能劣化原因パスを記憶する性能劣化原因パス記憶ステップと、
前記性能劣化パス記憶ステップによって記憶された性能劣化パスがあるか否かを調べて、前記配信ツリーを構成する構成命令を与えるか否かを判断する情報分析ステップと、
前記情報分析ステップにおいて前記構成命令を与えると判断したときは、前記スループット、配信ツリー記憶部に記憶された第１の配信ツリー及び特定された前記性能劣化原因パスに基づいて第２の配信ツリーを構成する配信ツリー作成ステップと、
前記第２の配信ツリーが構成されたとき、前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶させる配信ツリー記憶ステップと、を繰り返すことを特徴とする配信ツリー構成方法。
【請求項２１】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
配信パス毎の構成閾値を定めるステップと、
スループットが構成閾値に満たない配信パスを性能劣化パスとして記憶する性能劣化パス記憶ステップと、
前記性能劣化パスに基づいて性能劣化原因パスを特定するステップと
前記特定された性能劣化原因パスを記憶する性能劣化原因パス記憶ステップと、
前記性能劣化パス記憶ステップによって記憶された性能劣化パスがあるか否かを調べて、前記配信ツリーを構成する構成命令を与える否かを判断する情報分析ステップと、
前記情報分析ステップにおいて前記構成命令を与えると判断したときは、前記スループット、配信ツリー記憶部に記憶された第１の配信ツリー及び特定された前記性能劣化原因パスに基づいて第２の配信ツリーを構成する配信ツリー作成ステップと、
前記配信ツリー作成ステップにおいて、前記構成命令が与えられたときに、配信ツリー記憶部に記憶された第１の配信ツリーを読み出し、前記性能劣化原因パス記憶ステップにおいて記憶された前記性能劣化原因パスを読み出し、各受信ノードの受信した受信済データ量、前記スループット、読み出した前記第１の配信ツリー及び前記性能劣化原因パスに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶する配信ツリー記憶ステップと、を繰り返すことを特徴とする配信ツリー構成方法。
【請求項２２】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
配信パスのスループットを推定して生成したスループット推定値をスループット推定値記憶部に記憶させるスループット推定ステップと、
前記スループット推定値と予め定められた構成閾値とを用いて前記配信ツリーを構成する構成命令を与えるか否かを判断する情報分析ステップと、
前記情報分析ステップにおいて前記構成命令を与えると判断したとき、配信ツリー記憶部に記憶された第１の配信ツリー及び前記スループット推定ステップにおいて記憶された前記スループット推定値によって第２の配信ツリーを構成する配信ツリー作成ステップと、
前記第２の配信ツリーが構成されたとき、前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶させる配信ツリー記憶ステップと、を繰り返すことを特徴とする配信ツリー構成方法。
【請求項２３】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成方法であって、
配信パスのスループットを推定して生成したスループット推定値をスループット推定値記憶部に記憶させるスループット推定ステップと、
前記スループット推定値と予め定められた構成閾値とを用いて前記配信ツリーを構成する構成命令を与えるか否かを判断する情報分析ステップと、
前記情報分析ステップにおいて前記構成命令を与えると判断したとき、配信ツリー記憶部に記憶された第１の配信ツリー及び前記スループット推定ステップにおいて記憶された前記スループット推定値によって第２の配信ツリーを構成する配信ツリー作成ステップと、
前記配信ツリー作成手段ステップにおいて、前記構成命令が与えられたときに、前記スループット推定値記憶部から前記スループット推定値を読み出し、前記配信ツリー記憶部から第１の配信ツリーを読み出し、各受信ノードの受信した受信済データ量、読み出された前記スループット推定値及び前記第１の配信ツリーによって第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶する配信ツリー記憶ステップと、を繰り返すことを特徴とする配信ツリー構成方法。
【請求項２４】
前記スループット推定ステップにおいて、
前記スループット推定値及び配信パスのスループットに基づいてスループット推定値の更新を行うか否かを判断する更新条件評価ステップと、
前記更新条件評価ステップにおいて更新を行うと判断したとき、前記スループットに基づいてスループット推定値を定め、定めたスループット推定値を前記スループット推定値記憶部に記憶させるスループット推定値更新ステップと、を繰り返すことを特徴とする請求項２２又は請求項２３に記載の配信ツリー構成方法。
【請求項２５】
前記情報分析ステップにおいて、マルチキャストによるデータの配信が終了するまで、その動作を繰り返すことを特徴とする請求項１５から請求項２４のいずれか１項に記載の配信ツリー構成方法。
【請求項２６】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成構成用プログラムであって、
前記配信ツリーを構成する構成命令に基づいて、配信パスの性能に基づいて前記配信ツリーを構成する配信ツリー作成処理と、
前記配信ツリー作成処理に前記構成命令を繰り返し与える情報分析処理と、
をコンピュータに実行させることを特徴とする配信ツリー構成用プログラム。
【請求項２７】
配信パスの性能としてスループット計測値を記憶するスループット計測値記憶処理をコンピュータに実行させ、
前記配信ツリー作成処理において、前記構成命令を与えられたときに、前記スループット計測値記憶処理で記憶された前記スループット計測値を読み出し、前記配信ツリーを構成することを特徴とする請求項２６に記載の配信ツリー構成用プログラム。
【請求項２８】
前記配信ツリー作成処理において、前記構成命令を与えられたときに、配信ツリー記憶部から第１の配信ツリーを読み出し、各受信ノードの受信した受信済データ量、前記スループット及び読み出した前記第１の配信ツリーに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶する配信ツリー記憶処理を繰り返すことを特徴とする請求項２６又は請求項２７に記載の配信ツリー構成用プログラム。
【請求項２９】
前記情報分析処理において、前記スループットと構成閾値に基づいて前記配信ツリーを構成するか否かを判断し、前記構成命令を与えることを特徴とする請求項２６から請求項２８のいずれか１項に記載の配信ツリー構成用プログラム。
【請求項３０】
配信ツリーの構成の前の前記スループットに基づいて、前記配信ツリーの構成の後に構成閾値を計算する構成閾値決定処理をコンピュータに実行させ、
前記情報分析処理において、
前記スループットと前記構成閾値に基づいて、各配信パスの性能が劣化しているか否かを判断する性能調査処理と、
性能が劣化していると判断された配信パスと前記スループットに基づいて、性能劣化の原因となる配信パスを特定する性能劣化原因特定処理をコンピュータに実行させることを特徴とする請求項２６から請求項２９のいずれか１項に記載の配信ツリー構成用プログラム。
【請求項３１】
前記スループットと配信パスのスループットを推定して生成したスループット推定値と各ノードの受信済みデータ量とに基づいて、前記スループット推定値の更新を行うか否かを判断する更新条件評価処理と、
前記スループットに基づいて前記スループット推定値を更新するスループット推定値更新処理とをコンピュータに実行させ、
前記情報分析処理は、
前記スループット推定値と構成閾値によって配信ツリーを構成するか否かを判断し、前記構成命令を与えることを特徴とする請求項２６から請求項２９のいずれか１項に記載の配信ツリー構成用プログラム。
【請求項３２】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成用プログラムであって、
配信パス毎の構成閾値を定める処理と、
スループットが構成閾値に満たない配信パスを性能劣化パスとして記憶する性能劣化パス記憶処理と、
前記性能劣化パスに基づいて性能劣化原因パスを特定する処理と
前記特定された性能劣化原因パスを記憶する性能劣化原因パス記憶処理と、
前記性能劣化パス記憶処理によって記憶された性能劣化パスがあるか否かを調べて、前記配信ツリーを構成する構成命令を与える否かを判断する情報分析処理と、
前記情報分析処理において前記構成命令を与えると判断したときは、前記スループット、配信ツリー記憶部に記憶された第１の配信ツリー及び特定された前記性能劣化原因パスに基づいて第２の配信ツリーを構成する配信ツリー作成処理と、
前記配信ツリー作成処理において、前記構成命令が与えられたときに、配信ツリー記憶部に記憶された第１の配信ツリーを読み出し、前記性能劣化原因パス記憶処理において記憶された前記性能劣化原因パスを読み出し、各受信ノードの受信した受信済データ量、前記スループット、読み出した前記第１の配信ツリー及び前記性能劣化原因パスに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶する配信ツリー記憶処理と、を繰り返しコンピュータに実行させることを特徴とする配信ツリー構成用プログラム。
【請求項３３】
マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成用プログラムであって、
配信パスのスループットを推定して生成したスループット推定値をスループット推定値記憶部に記憶させるスループット推定値記憶処理と、
前記スループット推定値と予め定められた構成閾値とを用いて前記配信ツリーを構成する構成命令を与えるか否かを判断する情報分析処理と、
前記情報分析ステップにおいて前記構成命令を与えると判断したとき、配信ツリー記憶部に記憶された第１の配信ツリー及び前記スループット推定ステップにおいて記憶された前記スループット推定値に基づいて第２の配信ツリーを構成する配信ツリー作成処理と、
前記配信ツリー作成処理において、前記構成命令が与えられたときに、前記スループット推定値記憶部から前記スループット推定値を読み出し、配信ツリー記憶部に記憶された第１の配信ツリーを読み出し、各受信ノードの受信した受信済データ量、読み出された前記スループット推定値及び前記第１の配信ツリーに基づいて第２の配信ツリーを構成し、構成した前記第２の配信ツリーを前記第１の配信ツリーの代わりに前記配信ツリー記憶部に記憶する配信ツリー記憶処理と、を繰り返しコンピュータに実行させることを特徴とする配信ツリー構成用プログラム。
【請求項３４】
前記情報分析処理において、マルチキャストによるデータの配信が終了するまで、その動作を繰り返すことを特徴とする請求項２６から請求項３３のいずれか１項に記載の配信ツリー構成用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配信ツリーの構成に関し、特に、マルチキャストによるデータの配信を行う配信ツリーの構成に関する。
【背景技術】
【０００２】
複数の宛先に対して同じデータを配信する同報配信において、途中のルータでデータを複製するＩＰマルチキャストは、ＩＰマルチキャストに対応しているルータ設備が必要であることなどの理由により、広範的には普及していない。そのため、ノード（エンドホスト）間ではユニキャスト通信を行い、ノードでデータを複製、転送してマルチキャスト通信を行うアプリケーションレベルマルチキャスト（ＡＬＭ）によって、同報配信が行われている。
【０００３】
ＡＬＭによる配信システムは、一般的に図１２に示されるような構成をしている。図１２を参照すると、上記ＡＬＭによる配信システムは、データの送信及び配信ツリーの管理を行う送信サーバ１と、データの送受信及び配信状況の送信サーバ１への通知を行う受信ノード４及び６と、ネットワーク５から構成されている。
【０００４】
送信サーバ１は、例えば、ユーザから配信開始命令などの入力を受けるコマンド入力手段１１と、配信ツリーに沿ってデータを送信するデータ送信手段１２と、データの送信スループットを計測するスループット計測手段Ｚ１３と、配信ツリーの作成や配信状況を管理するツリー管理装置２と、配信ツリー及び配信ツリー作成に用いるデータを記憶する記憶装置３から構成されている。
【０００５】
ツリー管理装置２は、配信ツリーを作成する配信ツリー作成手段Ｚ２１と、例えば各受信ノードへの配信状況などを示す情報を収集する情報収集手段Ｚ２２を備えている。
【０００６】
記憶装置３は、配信ツリー作成手段Ｚ２１によって作成された配信ツリーを記憶させる配信ツリー記憶部３１と、例えば、各パスで予め測定しておいた遅延時間やスループットなどのような、配信ツリーを作成するときに参照するデータを記憶させるネットワーク情報記憶部Ｚ３２を備えている。
【０００７】
受信ノード４は、配信ツリーに沿ってデータを送信するデータ送信手段４１と、データを受信するデータ受信手段４２と、データの送信スループットを計測するスループット計測手段Ｚ４３と、受信したデータ量を計測する受信済みデータ量計測手段Ｚ４４と、例えば配信完了などを示す情報を、ネットワーク５を介して情報収集手段Ｚ２２に連絡する情報連絡手段Ｚ４５を備えている。
【０００８】
送信サーバ１において、コマンド入力手段１１に配信開始の入力が与えられると、配信ツリー作成手段Ｚ２１は、例えば予め測定するなどしておいた各パスの遅延時間やスループットなどのような情報をネットワーク情報記憶部Ｚ３２から読み込み、例えばＳｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｔｒｅｅのような配信ツリーを作成して配信ツリー記憶部３１に記憶させる。配信ツリーが作成されると、データ送信手段１２が配信ツリー記憶部３１から配信ツリーを読み込み、上記配信ツリーに沿ってデータを送信する。
【０００９】
受信ノード４のデータ受信手段４２がデータを受信すると、データ送信手段４１が次の受信ノード６に対してデータを送信する。
【００１０】
データの送受信と並行して、スループット計測手段Ｚ１３及びＺ４３は、データの送信スループットを計測し、受信済みデータ量計測手段Ｚ４４は、自ノードがこれまでに受信したデータ量を計測する。
【００１１】
受信ノード４においてデータの受信が終了すると、情報連絡手段Ｚ４５は、配信完了の連絡をネットワーク５を介して情報収集手段Ｚ２２に送信する。情報収集手段Ｚ２２が全ての受信ノードからの配信完了の連絡を受信したとき、上記ＡＬＭによる配信システムは、マルチキャスト配信を終了する。
【００１２】
ＡＬＭでは、実際のルータやリンクなどの物理構成は把握せずに、ノード間のコネクションなどの論理的なトポロジーを用いて、図１３に示されるような配信ツリーを作成し、上記配信ツリーに沿ってデータの送信を行っている。
【００１３】
図１３を参照すると、配信ツリーは、送信サーバ１と、受信ノード４−１〜Ｘと、送信サーバと受信ノード、及び受信ノードと受信ノードを結ぶコネクション（上記コネクションをパスと呼ぶ）とから構成されている。受信ノード４−１〜Ｘのそれぞれは、図１２の受信サーバ４と同等の構成及び機能を有している。また、図１３では例として３段の配信ツリーが描かれているが、配信ツリーの段数に決まりはなく、ネットワークの状況や配信ツリー作成のアルゴリズムなどによって変わってくる。
【００１４】
図１３に示されるような配信ツリーが作成されると、データ配信のときに、上記配信ツリーの上から下に向かってデータのユニキャスト送信が行われる。送信サーバ１が、受信ノード４−１〜Ｍに対してデータをユニキャスト通信で送信し、受信ノード４−１〜Ｍは、自ノードとパスで結ばれている下流の受信ノード４−Ｎ〜Ｘに対して受信したデータをユニキャスト通信で転送する。
【００１５】
しかし、ＡＬＭでは、配信ツリーを作成するとき、実際の通信で使用するルータやリンクなどの物理構成を認識できないため、特定のリンクにおいて配信ツリーの複数のパスが競合して配信性能が劣化することがあり、これによって、全てのノードへの配信が完了するまでに時間がかかるという問題があった。
【００１６】
これに対し、従来、例えば非特許文献１に示されるような配信ツリー構成装置、配信ツリー構成方法、及び配信ツリー構成用プログラムが、リンクにおける配信ツリーの複数パスの競合を軽減するために用いられている。
【００１７】
この非特許文献１に記載された配信ツリー構成装置、配信ツリー構成方法、及び配信ツリー構成用プログラムは、配信ツリーを作成した後にリンクにおけるパスの競合を調査し、リンクにおいて競合している複数のパスがあれば、その内の１つのパスの宛先ノードを経由して残りのパスの宛先ノードへデータを転送することで、物理リンクにおけるパスの競合を軽減するものである。
【００１８】
上記システムのパスの競合を軽減する仕組みについて、図１４の例を用いて詳細に説明する。図１４は、図１３に示されるような配信ツリーの一部分であって、物理構成によって記述されている。ここでは、受信ノード４−１がデータの送信を行い、受信ノード４−２及び４−３がデータの受信及び転送を行うものとする。ルータ７１は、各受信ノードを結ぶコネクションの分岐点に存在するルータで、各受信ノードとルータ７１を結んでいるのが物理構成上のリンクであり、パス８１〜８３が論理構成上のパスである。
【００１９】
上記システムは、受信ノードが配信ツリーに参加するときに、予めｔｒａｃｅｒｏｕｔｅコマンドによって各リンクにおける遅延時間と経由するルータを調べておく。そして、配信ツリーを作成したときに、この例ではパス８１及び８２が配信ツリーに組み込まれたとする。すると、受信ノード４−１とルータ７１間のリンクにおいて、パス８１とパス８２は競合していることになる。このとき、上記システムは、同じ受信ノードを送信元とするパスについてのみ、使用しているリンクやルータをｔｒａｃｅｒｏｕｔｅコマンドの結果から調べ、パス８１とパス８２が受信ノード４−１とルータ７１間のリンクにおいて競合していることを検知する。ここで、上記システムは、パスが競合している受信ノード４−１とルータ７１間のリンクにおける遅延時間が、競合しているパス８１及び８２の遅延時間に占める割合を計算し、予め定めた閾値の割合よりも大きい場合はパスの変更を行う。
【００２０】
パスの変更は、以下のように行う。例えば、受信ノード４−１とルータ７１間のリンクにおける遅延時間のパス８１とパス８２とに対して占める割合が、両方とも閾値を超えていて、また競合していない部分の遅延時間に関してパス８２の方が短い場合、パス８１を使用するのをやめて、代わりにパス８３によって受信ノード４−１からのデータを受信ノード４−３へ送信するように変更する。
【００２１】
この変更により、配信ツリーのノードホップ数が１つ増える代わりに、競合しているパスの本数を１つだけ減らせることができる。
【００２２】
上記システムでは、配信ツリーのノードホップ数が過度に増加するのを防ぐため、配信ツリーの各競合部分に対して１回ずつだけ、上記変更を行っている。
【非特許文献１】村上慶司、佐藤文明  著、リンクの負荷と木の深さを考慮したアプリケーションレベルマルチキャストツリーの動的構築方法、情報処理学会研究報告、２００４年１１月４日、第２００４−ＤＰＳ−１２０巻、第１０７号、１〜６頁
【発明の開示】
【発明が解決しようとする課題】
【００２３】
ここで、ＡＬＭによる従来のデータ配信における課題は、ネットワークの物理構成が把握できない等の理由によって、想定外に配信性能が劣化してしまうことである。すなわち、ＡＬＭにおける課題解決の目的は、特定のリンク上における複数の配信パスの競合、その他の配信パスの性能劣化等が起こったときに配信ツリーの配信性能を改善することであり、そのためには、全てのノードに配信が完了するまでの時間を短縮するという観点で配信ツリーの再構成を行うことが必要である。
【００２４】
しかしながら、非特許文献１に記載された技術を一例とする従来技術における配信ツリーの再構成は、特定の物理構成上のリンクに極端な負荷がかかることを回避するために、ネットワークの物理構成上の経路を調べて、リンクにおける配信パスの競合を検知し、競合状態と検知されたリンクに関して最大１回だけ、競合している配信パスの内の１つだけを局所的に変更するものであって、全てのノードへの配信が完了するまでの時間が改善されるものであるとは言えない。
【００２５】
そこで、本発明は、上記課題に鑑みてなされたものであって、配信パスの性能劣化の発生時に、状況に応じて配信効率の高い配信ツリーへと配信ツリーを再構成できる配信ツリー構成装置、配信ツリー構成方法、及び配信ツリー構成用プログラムに関する技術を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記目的を達成するため本発明は、マルチキャストによるデータの配信を行う配信ツリーを構成する配信ツリー構成装置であって、前記配信ツリーを構成する構成命令に基づいて、配信パスのスループットに基づいて前記配信ツリーを構成する配信ツリー作成手段と、前記配信ツリー作成手段に前記構成命令を繰り返し与える情報分析手段と、
を備えることを特徴とする。この構成により、ネットワークの状況に応じた配信ツリーを構成する。
【発明の効果】
【００２７】
本発明によれば、配信パスのスループット計測値を用いて配信ツリーの構成を繰り返し行うため、ネットワークの物理的な構成を把握していなくても、配信パスの性能劣化に対して、ネットワークの状況に応じたより配信効率の高い配信ツリーを構成することができる。したがって、全てのノードへの配信が完了するまでの時間を短縮できる。
【発明を実施するための最良の形態】
【００２８】
（第１の実施の形態）
次に、本発明を実施するための第１の形態について図面を参照して詳細に説明する。
【００２９】
（第１の実施の形態の構成）
図１は、本発明を実施するための第１の実施の形態の構成を示すブロック図である。
【００３０】
図１を参照すると、本発明の第１の実施の形態は、データの送信及び配信ツリーの管理を行う送信サーバ１と、データの送受信及び計測結果の送信サーバ１への通知を行う受信ノード４及び６と、ネットワーク５とを含む。
【００３１】
送信サーバ１は、マルチキャスト配信命令や各パラメータの初期値を入力するコマンド入力手段１１と、配信ツリーに沿ってデータを送信するデータ送信手段１２と、データの送信スループット（以下、スループット計測値と呼ぶ）を計測して記憶装置３のスループット計測値記憶部３２に記憶させるスループット計測手段１３と、プログラム制御により動作して配信ツリーを管理するツリー管理装置２と、配信ツリー及び配信ツリーの再構成に関するデータを記憶する記憶装置３とを含む。
【００３２】
ツリー管理装置２は、配信ツリー作成手段２１と、情報収集手段２２と、情報分析手段２３とを備えている。
【００３３】
配信ツリー作成手段２１は、コマンド入力手段１１から配信ツリー作成命令が与えられると、スループット推定値記憶部３３から各パスのスループット計測値の推定値（以下、スループット推定値と呼ぶ）を読み込み、これをもとに配信ツリーを作成して配信ツリー記憶部３１に記憶させる。
【００３４】
情報収集手段２２は、受信ノード４の情報連絡手段４５からスループット計測値と受信済みデータ量を通知され、上記スループット計測値をスループット計測値記憶部３２に記憶させ、上記受信済みデータ量を受信済みデータ量記憶部３５に記憶させる。
【００３５】
情報分析手段２３は、スループット計測値記憶部３２と再構成閾値記憶部３４から、配信に使用している各パス（以下、配信パスと呼ぶ）のスループット計測値と、配信ツリーの再構成を開始する条件となる閾値（以下、再構成閾値と呼ぶ）とを読み込み、これらをもとに配信パスの性能劣化を調査し、配信ツリーの再構成を行うか否かを判断する。また、配信ツリーの再構成を行うと判断した場合、配信ツリー作成手段２１に配信ツリー再構成命令を与える。
【００３６】
本発明を実施するための第１の実施の形態では、情報分析手段２３は、上記スループット計測値と上記再構成閾値の大きさを比較して配信パスの性能劣化を調査し、例えば、上記スループット計測値が上記再構成閾値未満である場合に再構成を行うと判断する。なお、再構成を行うと判断する基準は、上記スループット計測値が上記再構成閾値未満である場合に限らず、上記スループット計測値が上記再構成閾値以下である場合などの他の場合でもよい。
【００３７】
記憶装置３は、配信ツリー作成手段２１によって作成された配信ツリーを記憶する配信ツリー記憶部３１と、スループット計測手段１３によって計測されたスループット計測値を記憶するスループット計測値記憶部３２と、スループット推定値を記憶するスループット推定値記憶部３３と、再構成閾値を記憶する再構成閾値記憶部３４と、情報収集手段２２から通知された受信済みデータ量を記憶する受信済みデータ量記憶部３５とを備えている。
【００３８】
図２は、本発明の第１の実施の形態の送信サーバ１のハードウェア構成を示すブロック図である。
【００３９】
ここで、送信サーバ１のハードウェア構成の説明をする。
【００４０】
図２は、本実施の形態による送信サーバ１のハードウェア構成を示すブロック図である。
【００４１】
図２を参照すると、本発明による送信サーバ１は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部９２、ネットワーク５を介してデータの送受信を行う通信制御部９３（データ送信手段１２、スループット計測手段１３）、液晶ディスプレイ、プリンタやスピーカ等の提示部９４、キーボードやマウス等の入力部９５（コマンド入力部１１）、周辺機器と接続してデータの送受信を行うインタフェース部９６、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリから構成されるハードディスク装置である補助記憶部９７（記憶装置３）、本情報処理装置の上記各構成要素を相互に接続するシステムバス９８等を備えている。
【００４２】
本発明による送信サーバ１は、その動作を、送信サーバ１内部にそのような機能を実現するプログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品からなる回路部品を実装してハードウェア的に実現することは勿論として、上記した各構成要素の各機能を提供するプログラムを、コンピュータ処理装置上のＣＰＵ９１で実行することにより、ソフトウェア的に実現することができる。
【００４３】
すなわち、ＣＰＵ９１は、補助記憶部９７に格納されているプログラムを、主記憶部９２にロードして実行し、送信サーバ１の動作を制御することにより、上述した各機能をソフトウェア的に実現することが可能である。
【００４４】
受信ノード４は、配信ツリーに沿ってデータを送信するデータ送信手段４１と、データを受信するデータ受信手段４２と、データの送信スループットであるスループット計測値を計測するスループット計測手段４３と、受信済みデータ量を計測する受信済みデータ量計測手段４４と、例えば配信完了などを示す情報を、ネットワーク５を介して情報収集手段２２に連絡する情報連絡手段４５とを備えている。
【００４５】
情報連絡手段４５は、スループット計測手段４３によって計測されたスループット計測値と受信済みデータ量計測手段４４によって計測された受信済みデータ量を読み込み、これらを送信サーバ１のツリー管理装置２の情報収集手段２２に通知する。
【００４６】
受信ノード４は、データ受信手段４２でデータを受信すると、データ送信手段４１が次の受信ノード６に対してデータを送信する。
【００４７】
（第１の実施の形態の動作）
次に、本発明を実施するための第１の実施の形態の動作について詳細に説明する。
【００４８】
最初に、図３〜図５を参照して送信サーバ１の配信ツリー作成手段２１が中心となって行う配信ツリーの作成処理及び配信ツリーの再構成処理についてそれぞれ説明する。
【００４９】
図３〜図５は、本発明の第１の実施の形態の送信サーバの動作を示すフローチャートである。
【００５０】
（第１の実施の形態における配信ツリーの作成処理）
まず、本発明を実施するための第１の実施の形態における配信ツリーの作成処理について、図３を参照してその一例（以下、ＳＷ方式と呼ぶ）を説明する。
【００５１】
配信ツリー作成手段２１は、送信サーバ１を配信ツリーに追加する（ステップＳ１０１）。この時点では、まだノード及びパスの何れも配信ツリーに含まれていない。
【００５２】
次に、配信ツリー作成手段２１は、配信ツリーに含まれていないノードの有無を判断し（ステップＳ１０２）、配信ツリーに含まれていないノードがある場合、配信ツリーに含まれている送信サーバ及びノードを送信元として、配信ツリーに含まれていないノードを宛先とする全てのパスのスループット推定値を、スループット推定値記憶部３３から読み込む（ステップＳ１０３）。
【００５３】
そして、配信ツリー作成手段２１は、読み込んだスループット推定値を比較し、最も大きいスループット推定値を持つパスと、そのパスの宛先のノードを配信ツリーに追加する（ステップＳ１０４）。最も大きいスループット推定値を持つパスが複数存在する場合は、例えば、配信ツリー作成手段２１はその中からランダムで１つのパスを選択し、そのパスとそのパスの宛先のノードを配信ツリーに追加する。
【００５４】
以降、ステップＳ１０２〜ステップＳ１０４の手順を、配信ツリーに含まれていないノードが無くなるまで繰り返して（ステップＳ１０２）、配信ツリーを作成する。
【００５５】
なお、配信ツリーの作成方法は、ＳＷ方式に限らず、配信ツリーにランダムにパスを加えていく方式などの他の方式でもよい。
【００５６】
また、図４を参照して配信ツリーの再構成処理の概略を説明すると、配信ツリー作成手段２１は、情報分析手段２３から配信ツリー再構成命令が与えられた場合、配信ツリー記憶部３１とスループット計測値記憶部３２とスループット推定値記憶部３３と受信済みデータ量記憶部３５から、それまでの配信ツリーと各パスのスループット計測値とスループット推定値と各ノードの受信したデータの量（以下、受信済みデータ量と呼ぶ）を読み込み（ステップＳ２０１）、これらをもとに配信ツリーを再構成して配信ツリー記憶部３１に記憶させる（ステップＳ２０２）。
【００５７】
（第１の実施の形態における配信ツリーの再構成処理）
次いで、本発明を実施するための第１の実施の形態における配信ツリーの再構成処理について、図５を参照してその一例（以下、ＥＣＴ方式と呼ぶ）を詳細に説明する。
【００５８】
配信ツリー作成手段２１は、送信サーバ１を配信ツリーに追加する（ステップＳ３０１）。この時点では、まだノード及びパスの何れも配信ツリーに含まれていない。
【００５９】
次に、配信ツリー作成手段２１は、配信ツリーに含まれていないノードの有無を判断し（ステップＳ３０２）、配信ツリーに含まれていないノードがある場合、配信ツリーに含まれている送信サーバ及びノードを送信元として、配信ツリーに含まれていないノードを宛先とする全てのパスに対して、そのパスのスループット計測値をスループット計測値記憶部３２から、スループット推定値をスループット推定値記憶部３３から読み込み、送信元、宛先となるノードの受信済みデータ量を受信済みデータ量記憶部３５から読み込む（ステップＳ３０３）。
【００６０】
そして、配信ツリー作成手段２１は、読み込んだスループット計測値とスループット推定値と受信済みデータ量から、宛先となるノードにデータの転送が完了する予定時間（以下、転送完了予定時間と呼ぶ）を計算する（ステップＳ３０４）。ここで、送信元候補のノードをｐａｒｅｎｔ、宛先候補のノードをｃｈｉｌｄとし、ｐａｒｅｎｔを送信元としてｃｈｉｌｄを宛先とするパスのスループット計測値（存在しないときはスループット推定値）をｔｈ＿ｃｈｉｌｄとし、ツリーに含まれているパスの中でparentを宛先とするパスのスループット計測値（存在しないときはスループット推定値）をｔｈ＿ｐａｒｅｎｔとし、ｐａｒｅｎｔ、ｃｈｉｌｄの受信済みデータ量をＤＤ＿ｐａｒｅｎｔ、ＤＤ＿ｃｈｉｌｄとし、配信データの総データサイズをｃｏｎｔｅｎｔ＿ｓｉｚｅとすると、転送完了予定時間ＣＴは、例えば以下に示すような式で計算される。
【００６１】
以下に示す式は、本発明の第１の実施の形態による配信ツリーの作成処理の例（ＥＣＴ方式）における、転送完了予定時間ＣＴを計算するための式である。
【００６２】
なお、転送完了予定時間は、以下に示すような式による方法に限らず、他の方法で計算しても良い。
【００６３】
【数１】
2007235681.tif 000003
【００６４】
そして、配信ツリー作成手段２１は、計算した転送完了予定時間を比較し（ステップＳ３０５）、最も短い転送完了予定時間を持つパスとそのパスの宛先のノードを配信ツリーに追加する（ステップＳ３０６）。最も短い転送完了予定時間を持つパスが複数存在する場合は、例えば、配信ツリー作成手段２１はその中からランダムで１つのパスを選択し、そのパスとそのパスの宛先のノードを配信ツリーに追加する。
【００６５】
以降、ステップＳ３０２〜ステップＳ３０６の手順を、配信ツリーに含まれていないノードが無くなるまで繰り返して（ステップＳ３０２）、配信ツリーを作成する。
【００６６】
なお、配信ツリーの再構成処理は、ＥＣＴ方式に限らず、前述のＳＷ方式などの他の方式を用いて行われてもよい。また、配信ツリーを１から再構成することなく、一部のパスやノードを取り除いて部分的に構成された配信ツリー対して、前記方式のような配信パスの選択を行って配信ツリーを再構成してもよい。
【００６７】
次に、図６及び図１を参照して本実施の形態の送信サーバ及び受信サーバにおける配信処理について詳細に説明する。
【００６８】
コマンド入力手段１１に各パスのスループット推定値と再構成閾値が入力されると、コマンド入力手段１１は、上記スループット推定値をスループット推定値記憶部３３に記憶させ、上記再構成閾値を再構成閾値記憶部３４に記憶させる（ステップＡ０（初期設定ステップ））。
【００６９】
コマンド入力手段１１にマルチキャスト配信開始命令が入力されると、コマンド入力手段１１は、配信ツリー作成手段２１に配信ツリー作成命令を与える。配信ツリー作成手段２１は、配信ツリー作成命令が与えられると、スループット推定値記憶部３３から各パスのスループット推定値を読み込み、これをもとに配信ツリーを作成して配信ツリー記憶部３１に記憶させる（ステップＡ１（配信ツリー作成ステップ））。
【００７０】
本発明を実施するための第１の実施の形態における配信ツリーは、例えば前述のＳＷ方式によって作成される。なお、配信ツリーの作成方法は、ＳＷ方式に限らず、配信ツリーにランダムにパスを加えていく方式などの他の方式でもよい。
【００７１】
データ送信手段１２は、配信ツリー記憶部３１から配信ツリーを読み込み、ネットワーク５を経由して上記配信ツリーに沿って受信ノード４のデータ受信手段４２にデータの送信を開始する。また、データ受信手段４２によってデータを受信した受信ノード４は、データ送信手段４１によって次の宛先となる受信ノード６にデータの送信を開始する（ステップＡ２（データ送信指示ステップ））。
【００７２】
送信サーバ１及び受信サーバ４は、情報収集手段２２と情報連絡手段４５間における配信完了を示す情報に基づいて全てのノードに対して配信が終了したか否かを判断し（ステップＡ３（データ配信完了チェックステップ））、全てのノードに対して配信が終了していないときは、データを配信しながら、スループット計測手段１３及び４３において配信パスのスループット計測値をネットワーク５から計測し、受信済みデータ量計測手段４４において受信済みデータ量を計測する。情報連絡手段４５は、上記スループット計測値と上記受信済みデータ量を情報収集手段２２に通知し、情報収集手段２２は、上記スループット計測値をスループット計測値記憶部３２に記憶させ、上記受信済みデータ量を受信済みデータ量記憶部３５に記憶させる（ステップＡ４（スループット計測指示ステップ））。
【００７３】
情報分析手段２３は、スループット計測値と受信済みデータ量が計測されると、スループット計測値記憶部３２と再構成閾値記憶部３４から各配信パスのスループット計測値と再構成閾値を読み込み（ステップＡ５（再構成情報抽出ステップ））、読み込んだスループット計測値と再構成閾値に基づいて配信パスの性能劣化を調査し、配信ツリーの再構成を行うか否かを判断する（ステップＡ６（再構成判断ステップ））。
【００７４】
本発明を実施するための第１の実施の形態では、情報分析手段２３は、上記スループット計測値と上記再構成閾値の大きさを比較し、例えば、上記スループット計測値が上記再構成閾値未満である場合に再構成を行うと判断する。なお、再構成を行うと判断する基準は、前述のように他の場合でもよい。
【００７５】
ステップＡ６において配信ツリーの再構成を行うと判断した場合、情報分析手段２３は、配信ツリー作成手段２１に配信ツリー再構成命令を与え、配信ツリー作成手段２１は、配信ツリー再構成命令が与えられると、配信ツリー記憶部３１とスループット計測値記憶部３２とスループット推定値記憶部３３と受信済みデータ量記憶部３５から現在の配信ツリーと各パスのスループット計測値と各パスのスループット推定値と各ノードの受信済みデータ量を読み込み、これらに基づいて配信ツリーを再構成して配信ツリー記憶部３１に記憶させる（ステップＡ１）。
【００７６】
本発明を実施するための第１の実施の形態における配信ツリーは、例えば前述のＥＣＴ方式によってマルチキャスト配信が終了するまで再構成される。なお、配信ツリーの再構成処理は、ＥＣＴ方式に限らず、前述のＳＷ方式などの他の方式を用いて行われてよい。また、配信ツリーを１から再構成することなく、一部のパスやノードを取り除いて部分的に構成された配信ツリー対して、前記方式のような配信パスの選択を行って配信ツリーを再構成してもよい。
【００７７】
また、ステップＡ６において配信ツリーの再構成を行わないと情報分析手段２３によって判断された場合、ステップＡ２に移行する。
【００７８】
以降、ステップＡ３において全てのノードに対して配信が終了するまで、ステップＡ１〜ステップＡ６を繰り返していく。
【００７９】
一方、ステップＡ３において全てのノードに対して配信が終了した場合、マルチキャスト配信を終了する。
【００８０】
（第１の実施の形態の効果）
次に、本発明を実施するための第１の実施の形態の効果について説明する。
【００８１】
本発明の第１の実施の形態では、ノードの参加や離脱、障害の発生に対してだけでなく、配信パスの性能劣化に対しても再構成を行い、また、マルチキャスト配信が終了するまで、配信パスのスループット計測、性能の分析、配信ツリーの再構成を繰り返していくので、最初に作成した配信ツリーが特定の物理リンクで競合する場合や、配信途中でネットワークの状態が変化した場合に、作成した配信ツリーを、状況に応じてより配信効率が高い配信ツリーに切り替えていくことができる。このため、全てのノードに配信が完了するまでの時間を短縮できる。
【００８２】
（第２の実施の形態）
次に、本発明を実施するための第２の実施の形態について図面を参照し、第１の実施の形態と異なる点を中心に詳細に説明する。
【００８３】
（第２の実施の形態の構成）
図７は、本発明を実施するための第２の実施の形態の構成を示すブロック図である。
【００８４】
図７を参照すると、本発明の第２の実施の形態における記憶装置３は、図１に示された第１の実施の形態における記憶装置３の構成において、性能が劣化している配信パス（以下、性能劣化パスと呼ぶ）を記憶させる性能劣化パス記憶部３６と、性能劣化の原因となる配信パス（以下、性能劣化原因パスと呼ぶ）を記憶させる性能劣化原因パス記憶部３７とを新たに備え、また、情報分析手段２３は、再構成閾値決定手段２３１と、性能調査手段２３２と、性能劣化原因特定手段２３３とを備えている。
【００８５】
再構成閾値決定手段２３１は、記憶装置３のスループット計測値記憶部３２から各配信パスのスループット計測値を読み込み、また、上記配信パスにスループット計測値がないときは、代わりに記憶装置３のスループット推定値記憶部３３から上記配信パスのスループット推定値を読み込み、読み込んだスループット計測値又はスループット推定値に基づいて上記配信パスの再構成閾値を計算し、計算した上記配信パスの再構成閾値を再構成閾値記憶部３４に記憶させる。
【００８６】
本発明を実施するための第２の実施の形態では、全ての配信パスの再構成閾値を、全ての配信パスのスループット計測値（スループット計測値がない配信パスではスループット推定値）の最小値に統一して設定している。
【００８７】
なお、再構成閾値の設定方法は、全ての配信パスの再構成閾値を全ての配信パスのスループット計測値の最小値に統一して設定する方法に限らず、各配信パスの再構成閾値を上記配信パスのスループット計測値のＮ％（Ｎは正の実数）に個別に設定する方法などの他の方法でもよい。
【００８８】
性能調査手段２３２は、スループット計測値記憶部３２と再構成閾値記憶部３４から各配信パスのスループット計測値と再構成閾値を読み込み、読み込んだスループット計測値と再構成閾値に基づいて上記配信パスが性能劣化パスか否かを判断する。
【００８９】
また、性能調査手段２３２は、性能劣化パスであると判断した場合、上記配信パスを性能劣化パス記憶部３６に記憶させ、配信ツリー作成手段２１'に配信ツリー再構成命令を与える。
【００９０】
本発明を実施するための第２の実施の形態では、性能調査手段２３２は、上記スループット計測値と上記再構成閾値の大きさを比較し、例えば、上記スループット計測値が上記再構成閾値未満である場合に、上記配信パスを性能劣化パスであると判断する。
【００９１】
なお、性能劣化パスであると判断する基準は、上記スループット計測値が上記再構成閾値未満である場合に限らず、上記スループット計測値が上記再構成閾値以下である場合などの他の場合でもよい。
【００９２】
性能劣化原因特定手段２３３は、性能劣化パス記憶部３６から全ての性能劣化パスを読み込み、読み込んだ全ての性能劣化パスのスループット計測値をスループット計測値記憶部３２から読み込み、読み込んだスループット計測値に基づいて性能劣化原因パスを特定し、特定した性能劣化原因パスを性能劣化原因パス記憶部３７に記憶させる。
【００９３】
本発明を実施するための第２の実施の形態では、性能劣化原因パスの特定方法は、例えば性能劣化パスの中で、スループット計測値が最小であり、その中で最もソースからのノードホップ数が小さい性能劣化パスを性能劣化原因パスとしている。
【００９４】
なお、性能劣化原因パスの特定方法は上記方法に限らず、スループット計測値が最小である性能劣化パス全てを性能劣化原因パスとする方法などの他の方法でもよい。
【００９５】
また、本発明の第２の実施の形態における配信ツリー作成手段２１'は、情報分析手段２３から配信ツリー再構成命令が与えられると、配信ツリー記憶部３１とスループット計測値記憶部３２とスループット推定値記憶部３３と受信済みデータ量記憶部３５から、それまでの配信ツリーと各パスのスループット計測値と各パスのスループット推定値と各ノードの受信済みデータ量を読み込むことに加えて、性能劣化原因パス記憶部３７から性能劣化原因パスを読み込み、これらに基づいて配信ツリーを再構成して配信ツリー記憶部３１に記憶させるという点において、第１の実施の形態における配信ツリー作成手段２１と異なる。
【００９６】
その他の点は第１の実施の形態と同じであるため説明を省略する。
【００９７】
（第２の実施の形態の動作）
次に、図８及び図７を参照して本実施の形態の送信サーバ及び受信サーバにおける配信処理について、第１の実施の形態と異なる点を中心に詳細に説明する。
【００９８】
コマンド入力手段１１に各パスのスループット推定値が入力されると、コマンド入力手段１１は、上記スループット推定値をスループット推定値記憶部３３に記憶させる（ステップＡ０）。
【００９９】
ステップＡ１で示される第２の実施の形態におけるコマンド入力手段１１、及び配信ツリー記憶部３１、及びスループット推定値記憶部３３の動作は、第１の実施の形態におけるそれらの動作と同一のため、説明は省略する。
【０１００】
また、ステップＡ１で示される第２の実施の形態における配信ツリー作成手段２１'の動作は、最初の配信ツリーの作成処理においては、第１の実施の形態における配信ツリー作成手段２１の配信ツリーの作成処理と同一のため、説明は省略する。
【０１０１】
ステップＡ１の後、再構成閾値決定手段２３１は、各配信パスに対して、スループット計測値をスループット計測値記憶部３２から読み込み、また、上記配信パスにスループット計測値がないときは、代わりに上記配信パスのスループット推定値をスループット推定値記憶部３３から読み込み、読み込んだスループット計測値又はスループット推定値に基づいて上記配信パスの再構成閾値を計算し、計算した上記配信パスの再構成閾値を再構成閾値記憶部３４に記憶させる（ステップＡ５１（再構成閾値計算ステップ））。
【０１０２】
本発明を実施するための第２の実施の形態では、全ての配信パスの再構成閾値を全ての配信パスのスループット計測値（スループット計測値がない配信パスではスループット推定値）の最小値に統一して設定している。なお、再構成閾値の設定方法は、前述のように他の方法でもよい。
【０１０３】
ステップＡ２〜Ａ４で示される第２の実施の形態におけるデータ送信手段１２及び４１、及びデータ受信手段４２、及びスループット計測手段１３及び４３、及び受信済みデータ量計測手段４４、及び情報連絡手段４５、及び情報収集手段２２、及び配信ツリー記憶部３１、及びスループット計測値記憶部３２、及び受信済みデータ量記憶部３５の動作は、第１の実施の形態におけるそれらの動作と同一のため、説明は省略する。
【０１０４】
ステップＡ４においてスループット計測値と受信済みデータ量が計測されると、性能調査手段２３２は、全ての配信パスにおいて上記計測がなされたか否かを判断し（ステップＡ５２（配信パス調査完了チェックステップ））、全ての配信パスにおいて上記計測が完了していない場合にスループット計測値記憶部３２と再構成閾値記憶部３４から各配信パスのスループット計測値と再構成閾値を読み込み（ステップＡ５３（配信パス情報取得ステップ））、読み込んだ各配信パスのスループット計測値と再構成閾値を比較して上記計測がなされていない上記配信パスが性能劣化パスか否かを判断する（ステップＡ５４（スループット計測値評価ステップ））。
【０１０５】
本発明を実施するための第２の実施の形態では、性能調査手段２３２が上記配信パスを性能劣化パスであると判断する基準は、例えば、上記スループット計測値が上記再構成閾値未満である場合である。なお、性能劣化パスであると判断する基準は、前述のように他の場合でもよい。
【０１０６】
ステップＡ５４において性能調査手段２３２が上記配信パスを性能劣化パスでないと判断した場合（例えば、上記スループット計測値が上記再構成閾値以上である場合）、性能調査手段２３２は何の処理も行わず、ステップＡ５２に戻る。
【０１０７】
一方、ステップＡ５４において、例えば、上記スループット計測値が上記再構成閾値未満である場合、性能調査手段２３２は、上記配信パスを性能劣化パスであると判断し、上記配信パスを性能劣化パス記憶部３６に記憶させ（ステップＡ５５（パス性能評価ステップ））、ステップがステップＡ５２に戻る。
【０１０８】
以降、ステップＡ５２において全ての配信パスについて調べ終わるまで（全ての配信パスについて上記計測がなされたと判断されるまで）、ステップＡ５２〜ステップＡ５５を繰り返していく。
【０１０９】
一方、ステップＡ５２において全ての配信パスについて調べ終わった場合（全ての配信パスについて上記計測がなされたと判断された場合）、性能劣化原因特定手段２３３は、性能劣化パス記憶部３６に性能劣化パスが記憶されているかを調べることによって、性能が劣化したパスが存在するか否かを判断し（ステップＡ５７（性能劣化パスチェックステップ））、性能劣化パスが記憶されていない場合、何の処理も行わず、ステップＡ２に移行する。
【０１１０】
また、ステップＡ５７において性能劣化パスが記憶されている場合、性能劣化原因特定手段２３３は、性能劣化パス記憶部３６から全ての性能劣化パスを読み込み、読み込んだ全ての性能劣化パスのスループット計測値をスループット計測値記憶部３２から読み込み、それらに基づいて性能劣化原因パスを特定し、特定した性能劣化原因パスを性能劣化原因パス記憶部３７に記憶させる（ステップＡ５８（性能劣化原因特定ステップ））。
【０１１１】
本発明を実施するための第２の実施の形態では、性能劣化原因パスの特定において、性能劣化原因特定手段２３３が、性能劣化パスの中で、スループット計測値が最小であり、その中で最もソースからのノードホップ数が小さい性能劣化パスを性能劣化原因パスと特定している。なお、性能劣化原因パスの特定方法は、前述のように他の方法でもよい。
【０１１２】
次いで、情報分析手段２３が、配信ツリーの再構成を行うか否かを性能調査手段２３２によって判断し（ステップＡ６）、配信ツリーの再構成が必要であると判断した場合、性能調査手段２３２は、配信ツリー作成手段２１'に配信ツリー再構成命令を与え、配信ツリー作成手段２１'は、配信ツリー再構成命令が与えられると、配信ツリー記憶部３１とスループット計測値記憶部３２とスループット推定値記憶部３３と受信済みデータ量記憶部３５と性能劣化原因パス記憶部３７から、現在の配信ツリーと各パスのスループット計測値と各パスのスループット推定値と各ノードの受信済みデータ量と性能劣化原因パスを読み込み、これらに基づいて配信ツリーを再構成して配信ツリー記憶部３１に記憶させる（ステップＡ１）。
【０１１３】
本発明を実施するための第２の実施の形態における配信ツリーは、例えば前述のＥＣＴ方式によって性能劣化原因パスを選んで再構成を行う。なお、配信ツリーの再構成方法は、ＥＣＴ方式に限らず、前述のＳＷ方式などの他の方式でもよい。また、配信ツリーを１から再構成することなく、一部のパスやノードを取り除いて部分的に構成された配信ツリー対して、前記方式のような配信パスの選択を行って配信ツリーを再構成してもよい。
【０１１４】
また、情報分析手段２３が、ステップＡ６において配信ツリーの再構成を行わないと性能調査手段２３２によって判断した場合、ステップＡ２に移行する。
【０１１５】
以降、ステップＡ３において全てのノードに対して配信が終了するまで、ステップＡ１及びステップＡ５１及びステップＡ２〜ステップＡ４及びステップＡ５２〜ステップＡ５８及びステップA６を繰り返していく。
【０１１６】
一方、ステップＡ３において全てのノードに対して配信が終了した場合、マルチキャスト配信を終了する。
【０１１７】
（第２の実施の形態の効果）
次に、本発明を実施するための第２の実施の形態の効果について説明する。
【０１１８】
本発明の第２の実施の形態では、再構成閾値を配信パスごとに明確に設け、また配信性能の原因である配信パスを選んで再構成を行う。そのため、使用可能な帯域が異なるパスが混在しているネットワークにおいても、配信性能の劣化を検知して余計な再構成を行うことを回避でき、また、再構成の際も余分な配信パスまで組み換えてしまうことを回避できる。これによって、再構成のオーバヘッドを低減しつつ、少ない再構成箇所でも配信効率が高い配信ツリーに切り替えていくことができる。
【０１１９】
（第３の実施の形態）
次に、本発明を実施するための第３の実施の形態について図面を参照し、第１の実施の形態と異なる点を中心に詳細に説明する。
【０１２０】
（第３の実施の形態の構成）
図９は、本発明を実施するための第３の実施の形態の構成を示すブロック図である。
【０１２１】
図９を参照すると、本発明の第３の実施の形態におけるツリー管理装置２は、図１に示された第１の実施の形態におけるツリー管理装置２の構成において、スループット計測値からスループット推定値を推定するスループット推定手段２４を備えている。
【０１２２】
スループット推定手段２４は、初期値設定手段２４１と、推定値更新手段２４２と、更新条件評価手段２４３とを備えている。
【０１２３】
初期値設定手段２４１は、全てのパスのスループット推定値の初期値を設定し、スループット推定値記憶部３３に記憶させる。
【０１２４】
推定値更新手段２４２は、更新条件評価手段２４３から配信パスのスループット推定値更新命令が与えられると、上記配信パスのスループット計測値をスループット計測値記憶部３２から読み込み、読み込んだスループット計測値に基づいて上記配信パスのスループット推定値を求め、スループット推定値記憶部３３に記憶させる。
【０１２５】
更新条件評価手段２４３は、各配信パスのスループット計測値をスループット計測値記憶部３２から読み込み、各配信パスのスループット推定値をスループット推定値記憶部３３から読み込み、各ノードの受信済みデータ量を受信済みデータ量記憶部３５から読み込み、これらを用いてスループット推定値の更新を行うか否かを判断する。
【０１２６】
また、更新条件評価手段２４３は、スループット推定値の更新を行うと判断した場合、推定値更新手段２４２にスループット推定値更新命令を与える。
【０１２７】
また、本発明の第３の実施の形態における配信ツリー作成手段２１"は、情報分析手段２３"から配信ツリー再構成命令が与えられた場合に、スループット計測値記憶部３２から各パスのスループット計測値を読み込むことに替えて、スループット推定値記憶部３３から各パスのスループット推定値を読み込むという点において、第１の実施の形態における配信ツリー作成手段２１と異なる。
【０１２８】
また、本発明の第３の実施の形態における情報分析手段２３"は、配信パスの性能劣化を調査するときに、スループット計測値記憶部３２から各配信パスのスループット計測値を読み込むことに替えて、スループット推定値記憶部３３から各配信パスのスループット推定値を読み込むという点において、第１の実施の形態における情報分析手段２３と異なる。
【０１２９】
本発明を実施するための第３の実施の形態では、情報分析手段２３"は、上記スループット推定値と上記再構成閾値の大きさを比較して配信パスの性能劣化を調査し、例えば、上記スループット推定値が上記再構成閾値未満である場合に再構成を行うと判断する。なお、再構成を行うと判断する基準は、上記スループット推定値が上記再構成閾値未満である場合に限らず、上記スループット計測値が上記再構成閾値以下である場合などの他の場合でもよい。
【０１３０】
その他の点は第１の実施の形態と同じであるため説明を省略する。
【０１３１】
（第３の実施の形態の動作）
次に、本発明を実施するための第３の実施の形態の動作について詳細に説明する。
【０１３２】
最初に、図１０を参照して送信サーバ１の配信ツリー作成手段２１が中心となって行う配信ツリーの再構成処理について説明する。
【０１３３】
図１０は、本発明の第３の実施の形態の送信サーバの動作を示すフローチャートである。
【０１３４】
（第３の実施の形態における配信ツリーの再構成処理）
本発明を実施するための第３の実施の形態における配信ツリーの再構成処理について、その一例（以下、ＥＣＴ'方式と呼ぶ）を詳細に説明する。
【０１３５】
まず、配信ツリー作成手段２１"は、送信サーバ１を配信ツリーに追加する（ステップＳ４０１）。この時点では、まだノード及びパスの何れも配信ツリーに含まれていない。
【０１３６】
次に、配信ツリー作成手段２１"は、配信ツリーに含まれていないノードの有無を判断し（ステップＳ４０２）、配信ツリーに含まれていないノードがある場合、配信ツリーに含まれている送信サーバ及びノードを送信元として、配信ツリーに含まれていないノードを宛先とする全てのパスに対して、そのパスのスループット推定値をスループット推定値記憶部３３から読み込み、送信元、宛先となるノードの受信済みデータ量を受信済みデータ量記憶部３５から読み込む（ステップＳ４０３）。
【０１３７】
そして、配信ツリー作成手段２１"は、読み込んだスループット推定値と受信済みデータ量から、宛先となるノードにデータの転送が完了する予定時間（以下、転送完了予定時間と呼ぶ）を計算する（ステップＳ４０４）。ここで、送信元候補のノードをｐａｒｅｎｔ、宛先候補のノードをｃｈｉｌｄとし、ｐａｒｅｎｔを送信元としてｃｈｉｌｄを宛先とするパスのスループット推定値をＥＴ＿ｃｈｉｌｄとし、ツリーに含まれているパスの中でｐａｒｅｎｔを宛先とするパスのスループット推定値をＥＴ＿ｐａｒｅｎｔとし、ｐａｒｅｎｔ、ｃｈｉｌｄの受信済みデータ量をＤＤ＿ｐａｒｅｎｔ、ＤＤ＿ｃｈｉｌｄとし、配信データの総データサイズをｃｏｎｔｅｎｔ＿ｓｉｚｅとすると、転送完了予定時間ＣＴは、例えば以下に示すような式で計算される。
【０１３８】
以下に示す式は、本発明の第３の実施の形態による配信ツリーの作成処理の例（ＥＣＴ'方式）における、転送完了予定時間ＣＴを計算するための式である。
【０１３９】
なお、転送完了予定時間は、以下に示すような式による方法に限らず、他の方法で計算しても良い。
【０１４０】
【数２】
2007235681.tif 000004
【０１４１】
そして、配信ツリー作成手段２１"は計算した転送完了予定時間を比較し（ステップＳ４０５）、最も短い転送完了予定時間を持つパスとそのパスの宛先のノードを配信ツリーに追加する（ステップＳ４０６）。最も短い転送完了予定時間を持つパスが複数存在する場合は、例えば、配信ツリー作成手段２１"はその中からランダムで１つのパスを選択し、そのパスとそのパスの宛先のノードを配信ツリーに追加する。
【０１４２】
以降、ステップＳ４０２〜ステップＳ４０６の手順を、配信ツリーに含まれていないノードが無くなるまで繰り返して（ステップＳ４０２）、配信ツリーを作成する。
【０１４３】
なお、配信ツリーの再構成処理は、ＥＣＴ方式に限らず、前述のＳＷ方式などの他の方式を用いて行ってもよい。また、配信ツリーを１から再構成することなく、一部のパスやノードを取り除いて部分的に構成された配信ツリー対して、前記方式のような配信パスの選択を行って配信ツリーを再構成してもよい。
【０１４４】
次に、図１１及び図９を参照して本実施の形態の送信サーバ及び受信サーバにおける配信処理について詳細に説明する。
【０１４５】
コマンド入力手段１１に各パスの再構成閾値が入力されると、コマンド入力手段１１は、上記再構成閾値を再構成閾値記憶部３４に記憶させる（ステップＡ０）。
【０１４６】
コマンド入力手段１１にマルチキャスト配信開始命令が与えられると、初期値設定手段２４１は、全てのパスのスループット推定値の初期値を設定し、設定したスループット推定値の初期値をスループット推定値記憶部３３に記憶させる（ステップＡ６１（スループット推定値初期値設定ステップ））。
【０１４７】
本発明を実施するための第３の実施の形態では、初期値設定手段２４１は、各パスの送信元ノードのアクセス回線上り帯域と宛先ノードのアクセス回線下り帯域の内、小さい方をスループット推定値の初期値として設定する。
【０１４８】
ステップＡ１〜Ａ４で示される第３の実施の形態におけるコマンド入力手段１１、及びデータ送信手段１２及び４１、及びデータ受信手段４２、及びスループット計測手段１３及び４３、及び受信済みデータ量計測手段４４、及び情報連絡手段４５、及び情報収集手段２２、及び配信ツリー記憶部３１、及びスループット計測値記憶部３２、及びスループット推定値記憶部３３、及び受信済みデータ量記憶部３５の動作は、第１の実施の形態におけるそれらの動作と同一のため、説明は省略する。
【０１４９】
また、ステップＡ１で示される第３の実施の形態における配信ツリー作成手段２１"の動作は、最初のツリーを作成する場合においては、第１の実施の形態における配信ツリー作成手段２１の動作と同一のため、説明は省略する。
【０１５０】
ステップＡ４においてスループットが計測されると、スループット推定手段２４は、一定時間ごとに配信パスのスループット推定値の更新を開始する（ステップＡ６２（スループット推定値更新開始ステップ））。
【０１５１】
次いで、更新条件評価手段２４３は、全ての配信パスにおいて上記計測がなされたか否かを判断し（ステップＡ６３（配信パス調査完了チェックステップ））、全ての配信パスにおいて上記計測が完了していない場合に各配信パスのスループット計測値をスループット計測値記憶部３２から読み込み、各配信パスのスループット推定値をスループット推定値記憶部３３から読み込み、各ノードの受信済みデータ量を受信済みデータ量記憶部３５から読み込み、これらを用いて上記スループット推定値の更新処理を行うか否かを判断する（ステップＡ６４（配信パス情報取得ステップ））。
【０１５２】
上記配信パスに対してスループット推定値の更新処理を行わないと判断された場合（ステップＡ６５（スループット推定値更新条件評価ステップ））、更新条件評価手段２４３は何の処理も行わず、ステップＡ６３に戻る。
【０１５３】
本発明を実施するための第３の実施の形態では、スループット推定手段２４がスループット推定値の更新を行う条件は、各配信パスにおいて、スループット計測値がスループット推定値より大きい場合か、スループット計測値がスループット推定値より小さく、且つ上記配信パスの送信元ノードの受信済みデータ量が宛先ノードの受信済みデータ量より大きい場合か、スループット計測値がスループット推定値より小さく、且つ上記配信パスの送信元ノードの受信済みデータ量が宛先ノードの受信済みデータ量と等しく、且つ上記配信パスの１つ上流のパスのスループット計測値が上記配信パスのスループット計測値より大きい場合である。
【０１５４】
また、上記配信パスに対してスループット推定値の更新を行うと判断された場合（ステップＡ６５）、更新条件評価手段２４３は、推定値更新手段２４２にスループット推定値更新命令を与え、推定値更新手段２４２は、スループット推定値更新命令が与えられると、上記配信パスのスループット計測値をスループット計測値記憶部３２から読み込み、読み込んだスループット計測値に基づいて上記配信パスのスループット推定値を求め、スループット推定値記憶部３３に記憶させる（ステップＡ６６（スループット推定値計算ステップ））。その後、ステップがステップＡ６３に戻る。
【０１５５】
本発明を実施するための第３の実施の形態では、推定値更新手段２４２は、スループット推定値をスループット計測値の値に書き換えて更新している。
【０１５６】
以降、ステップＡ６３において全ての配信パスが調べ終わるまで（全ての配信パスについて上記計測がなされたと判断されるまで）、ステップＡ６３〜Ａ６６を繰り返していく。
【０１５７】
一方、ステップＡ６３において全ての配信パスを調べ終わった場合（全ての配信パスについて上記計測がなされたと判断された場合）、情報分析手段２３"は、スループット推定値記憶部３３と再構成閾値記憶部３４から各配信パスのスループット推定値と再構成閾値を読み込み（ステップＡ５）、読み込んだスループット推定値と再構成閾値に基づいて配信パスの性能劣化を調査し、配信ツリーの再構成を行うか否かを判断する（ステップＡ６）。
【０１５８】
本発明を実施するための第３の実施の形態では、情報分析手段２３"は、上記スループット推定値と上記再構成閾値の大きさを比較し、例えば、上記スループット推定値が上記再構成閾値未満である場合に再構成を行うと判断する。なお、再構成を行うと判断する基準は、前述のように他の場合でもよい。
【０１５９】
ステップＡ６において配信ツリーの再構成を行うと判断された場合、情報分析手段２３"は、配信ツリー作成手段２１"に配信ツリー再構成命令を与え、配信ツリー作成手段２１"は、配信ツリー再構成命令が与えられると、配信ツリー記憶部３１とスループット推定値記憶部３３と受信済みデータ量記憶部３５から現在の配信ツリーと各パスのスループット推定値と各ノードの受信済みデータ量を読み込み、これらに基づいて配信ツリーを再構成して配信ツリー記憶部３１に記憶させる（ステップＡ１）。
【０１６０】
本発明を実施するための第３の実施の形態における配信ツリーは、例えば前述のＥＣＴ'方式によって再構成される。なお、配信ツリーの再構成方法は、ＥＣＴ'方式に限らず、前述のＳＷ方式などの他の方式でもよい。また、配信ツリーを１から再構成することなく、一部のパスやノードを取り除いて部分的に構成された配信ツリー対して、前記方式のような配信パスの選択を行って配信ツリーを再構成してもよい。
【０１６１】
また、ステップＡ６において配信ツリーの再構成を行わないと情報分析手段２３"によって判断された場合、ステップＡ２に移行する。
【０１６２】
以降、ステップＡ３において全てのノードに対して配信が終了するまで、ステップＡ１〜ステップＡ４及びステップＡ６２〜ステップＡ６６及びステップＡ５〜ステップA６を繰り返していく。
【０１６３】
一方、ステップＡ３において全てのノードに対して配信が終了した場合、マルチキャスト配信を終了する。
【０１６４】
（第３の実施の形態の効果）
次に、本発明を実施するための第３の実施の形態の効果について説明する。
【０１６５】
本発明の第３の実施の形態では、まず、上流のパスの影響を考慮してスループット推定値の更新を行うので、そのときのネットワーク状況で各配信パス自身が有するスループットを推定することができる。
【０１６６】
また、配信ツリーの再構成処理におけるループ手順と連動させてスループット推定処理を何度も行うので、最初の配信ツリーを作成する際にネットワークの精査を行うことなく、また、別途計測用のパケットを用いることなく、ネットワーク内の様々なパスのスループットをネットワーク状態の変化に追従して推定することができ、配信パスの分散に応じて配信パスにおけるスループット推定値の精度を向上させることができる。
【０１６７】
そして、そのスループット推定処理における推定情報と連動させて配信ツリーを再構成することで、ネットワークの性能や状態により即した配信効率の高い配信パスの分散をすることができ、さらにそのループ手順を繰り返すことで、これらの相乗効果をより一層向上させていくことができ、配信完了時間をより短くすることができる。
【産業上の利用可能性】
【０１６８】
本発明は、インターネットを経由して、1つまたは複数のノードに対して、データファイルや動画ストリーミング、セキュリティパッチ等のコンテンツを一斉配信する装置や、前記装置の機能をコンピュータにより実現させるためのプログラムに対して適用することができる。また、配信ツリーを構成し、再構成する機能によって、各ノードを配信元とする配信ツリーを複数用意し、それらを用いて複数拠点にいる参加者の発言を他の拠点に配信するといった、遠隔会議等の用途にも適用することができる。
【図面の簡単な説明】
【０１６９】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の送信サーバのハードウェア構成を示すブロック図である。
【図３】本発明の第１の実施の形態の送信サーバの動作を示すフローチャートである。
【図４】本発明の第１の実施の形態の送信サーバの動作を示すフローチャートである。
【図５】本発明の第１の実施の形態の送信サーバの動作を示すフローチャートである。
【図６】本発明の第１の実施の形態の動作を示すフローチャートである。
【図７】本発明の第２の実施の形態の構成を示すブロック図である。
【図８】本発明の第２の実施の形態の動作を示すフローチャートである。
【図９】本発明の第３の実施の形態の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態の送信サーバの動作を示すフローチャートである。
【図１１】本発明の第３の実施の形態の動作を示すフローチャートである。
【図１２】一般的なアプリケーションレベルマルチキャストの構成を示すブロック図である。
【図１３】一般的なアプリケーションレベルマルチキャストの論理ツリーの構成を示すブロック図である。
【図１４】本発明の背景技術を説明するための図である。
【符号の説明】
【０１７０】
１：送信サーバ
１１：コマンド入力手段
１２：データ送信手段
１３、Ｚ１３：スループット計測手段
２：ツリー管理装置
２１、２１'、２１"、Ｚ２１：配信ツリー作成手段
２２、Ｚ２２：情報収集手段
２３、２３"：情報分析手段
２３１：再構成閾値決定手段
２３２：性能調査手段
２３３：性能劣化原因特定手段
２４：スループット推定手段
２４１：初期値設定手段
２４２：推定値更新手段
２４３：更新条件評価手段
３：記憶装置
３１：配信ツリー記憶部
３２：スループット計測値記憶部
Ｚ３２：ネットワーク情報記憶部
３３：スループット推定値記憶部
３４：再構成閾値記憶部
３５：受信済みデータ量記憶部
３６：性能劣化パス記憶部
３７：性能劣化原因パス記憶部
４、４−１〜４−Ｘ：受信ノード
４１：データ送信手段
４２：データ受信手段
４３、Ｚ４３：スループット計測手段
４４、Ｚ４４：受信済みデータ量計測手段
４５、Ｚ４５：情報連絡手段
５：ネットワーク
６：受信ノード
７１：ルータ
８１〜８３：パス
９１：ＣＰＵ
９２：主記憶部
９３：通信制御部
９４：提示部
９５：入力部
９６：インタフェース部
９７：補助記憶部
９８：システムバス
【図１】
2007235681.tif 000005
【図２】
2007235681.tif 000006
【図３】
2007235681.tif 000007
【図４】
2007235681.tif 000008
【図５】
2007235681.tif 000009
【図６】
2007235681.tif 000010
【図７】
2007235681.tif 000011
【図８】
2007235681.tif 000012
【図９】
2007235681.tif 000013
【図１０】
2007235681.tif 000014
【図１１】
2007235681.tif 000015
【図１２】
2007235681.tif 000016
【図１３】
2007235681.tif 000017
【図１４】
2007235681.tif 000018