マルチキャストシステム及びマルチキャストシステムのノード
【課題】新規ノードの追加やマルチキャストツリーの再構成を行う必要が生じたときに、配信遅延を所定の遅延量以下に収まるように迅速にマルチキャストツリーを構築することができるマルチキャストシステムを提供する。
【解決手段】複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、算出した予測遅延量を記憶する手段と、追加ノードを設ける際に予測遅延量を用いて、追加ノードを接続するノードを決定する手段と、を備える。
【解決手段】複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、算出した予測遅延量を記憶する手段と、追加ノードを設ける際に予測遅延量を用いて、追加ノードを接続するノードを決定する手段と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャストシステムに関する。特に、ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに関する。さらには、マルチキャストシステムのノード、マルチキャストツリー更新方法、マルチキャストシステムにおいてノードを追加してツリーを再構成するコンピュータプログラムに関する。
【背景技術】
【０００２】
ＷＥＢサーバーの更新情報や、センサなどが生成するデータを多数の機器に配信する際に、データの配信元をルートとするマルチキャストツリーを用いて配信するマルチキャストシステムがある。
【０００３】
このマルチキャストツリーは、そのデータを利用するノードで構成される論理ネットワークで、配信元毎に作成する場合や、１つのマルチキャストツリーを共有する場合がある。データはマルチキャストツリーの構成に従ってノード間を転送される。
【０００４】
マルチキャストツリー構成方法に関して、多量の利用者に対しリアルタイムにデータを配信するためのマルチキャストツリーを構築する手段がいくつか提案されている。
【０００５】
例えば、特許文献１では、ノードのＣＰＵ使用率、メモリ利用率、ＣＰＵスペック、物理的近傍度、生存時間といった情報を周囲のノードと交換し、周囲から受信する複数の情報を比較評価することによって、マルチキャストツリーを構築する手段が開示されている。なお、「物理的近傍度」は、ノードとノードとの間でピア間接続動作の応答時間を測定することにより得ることができる。また、「生存時間」は、１回の接続でその端末のネットワークへの平均接続時間を、平均生存時間とすることができる。
【０００６】
また、特許文献２では、ホップ数またはある時刻における到着パケットのシーケンス番号の推定値で評価し、マルチキャストツリーを構築する手段が開示されている。
【０００７】
さらに、特許文献３では、複数のノードにより構成されるネットワークにおいて、与えられた始点ノードから複数の終点ノードまでのマルチキャスト転送経路を求めるためのマルチキャスト転送経路計算方法であって、ネットワークのトポロジ情報と遅延情報とを用いて、始点ノードから終点ノードまでの遅延最小経路を各終点ノード毎に求め、始点ノードと各終点ノードまでの複数の遅延最小経路のうちの１つの遅延最小経路上のノードを、マルチキャスト転送における集約点ノードの候補ノードとして選択し、各候補ノードに対し、候補ノードから終点ノードまでの遅延最小経路を各終点ノード毎に算出し、各終点ノード毎の複数の遅延最小経路の遅延のうちの最大値と最小値との差を求め、誤差が最小となる候補ノードを集約点ノードとして選択し、始点ノードから集約点ノードまでの遅延最小経路と、集約点ノードから各終点ノードまでの各遅延最小経路とをマルチキャスト転送経路として出力する。上記特許文献３によれば、マルチキャスト転送経路の計算速度の向上を実現し、また、ユーザ間遅延分散の削減を可能とすることができると記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−２５２５９６号公報
【特許文献２】特開２００４−２４６７９０号公報
【特許文献３】特開２００４−２０８２８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
なお、上記特許文献１乃至特許文献３の全開示内容はその引用をもって本書に繰込み記載する。
【００１０】
以下の分析は、本発明によって与えられたものである。
【００１１】
従来技術における第１の問題は、マルチキャストツリーにおけるデータ配信において、配信遅延を指定した値以下に迅速に収めることができないということである。
【００１２】
その理由は、特許文献１および２において、配信遅延の最悪値についてなんら考慮されていないためである。また、特許文献３によれば、配信遅延の最悪値について一応考慮されているが、配信途中において、ルートノードとの中間に位置するノードが脱落したような場合、迅速なマルチキャストツリーの再構築ができないという問題が存在する。
【００１３】
従来技術における第２の問題は、マルチキャストシステムにおける配信遅延のばらつきを一定の範囲内に収めることができない場合があるということである。
【００１４】
一般に、マルチキャストツリーに参加しているノードは、マルチキャストツリー上の位置により、データを受け取るタイミングが異なる。その結果マルチキャストツリーにおける配信遅延のばらつきが大きくなってしまうためである。特許文献３には、一応配信遅延のばらつきを抑えるようにルートを選択するものが記載されているが、ルートの選択によって配信遅延のばらつきを抑えるのには限界がある。
【００１５】
本発明は、このような事情を考慮してなされたものであり、その第１の目的は、ノード内転送処理遅延と転送リンクのネットワーク遅延を考慮したマルチキャストツリーを迅速に構築することによって、参加するノードの配信遅延を指定した値以下に収めることができるマルチキャストシステムを提供することにある。
【００１６】
また、その第２の目的は、マルチキャストツリーに参加するノード間における、配信遅延のばらつきの小さいマルチキャストシステムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明の第１の視点によれば、複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、前記算出した予測遅延量を記憶する手段と、前記追加ノードを設ける際に前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する手段と、を備えるマルチキャストシステムが提供される。
【００１８】
本発明の第２の視点によれば、ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、前記ルートノードから各ノードまでの遅延量を算出する手段と、基準とする遅延量と前記算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、前記各ノードへのデータ到着時に前記算出した意図的な遅延量を挿入する手段と、を備えるマルチキャストシステムが提供される。
【００１９】
本発明の第３の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるノードであって、自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部と、前記算出した予測遅延量を記憶するノード情報記憶部と、を備えるマルチキャストシステムのノードが提供される。
【００２０】
本発明の第４の視点によれば、複数のノードがルートノードからツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるルートノードであって、前記ツリー状に接続された前記各ノードから自己のノードの配下に新たにノードを追加したと仮定してあらかじめ計算された予測遅延量を収集する推定遅延量収集機能部と、前記収集された予測遅延量を用いて前記マルチキャストツリー構造の変更を行うトポロジ決定機能部と、を備えるマルチキャストシステムのルートノードが提供される。
【００２１】
本発明の第５の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておくステップと、前記追加ノードを設ける必要が生じたときに、前記あらかじめ算出しておいた予測遅延量を用いて、前記追加ノードを接続するノードを決定するステップと、前記決定に基づいて、追加ノードをマルチキャストツリーに組み込んでデータ配信を行うステップと、を備えるマルチキャストシステムのマルチキャストツリー更新方法が提供される。
【００２２】
本発明の第６の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて用いられるコンピュータプログラムであって、前記複数のノードのいずれかに新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出し、記憶手段に記憶させる処理と、前記追加ノードを設ける必要が生じたときに、前記記憶手段に記憶された前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する処理と、を前記マルチキャストシステムに含まれる少なくとも一つのコンピュータに実行させるマルチキャストシステムのコンピュータプログラムが提供される。
【発明の効果】
【００２３】
本発明の第１、第３乃至第６の視点によれば、マルチキャストシステムにおけるデータ配信において、配信遅延を指定した値以下に迅速に収めることが可能になる。
【００２４】
また、本発明の第２の視点によれば、マルチキャストシステムにおける配信遅延のばらつきを一定の範囲内に収めることが可能になる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施形態のマルチキャストシステムにおける（ａ）再構成前のマルチキャストツリーの構成と、（ｂ）再構成後のマルチキャストツリーの構成を示す概念図である。
【図２】マルチキャストシステムにおけるマルチキャストツリーの構成例を示す概念図である。
【図３】本発明の実施形態によるマルチキャストシステムに用いられるルートノードの内部構成を示すブロック図である。
【図４】本発明の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。
【図５】第１の実施形態におけるノード情報データベースのデータ構成の一例を示す概念図である。
【図６】第１の実施形態におけるルートノードの処理フローチャートである。
【図７】第１の実施形態におけるルートノード以外のノードの処理フローチャートである。
【図８】第２の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。
【発明を実施するための形態】
【００２６】
本発明の実施形態の概要について説明する。本発明の一実施形態によるマルチキャストシステムは、図１に一例を示すように複数のノードを有するマルチチャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量（図１の各ノードＩＤの３項目）を、追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段（たとえば、図４の２１２）と、算出した予測遅延量を記憶する手段（図４の２２１、図３の１２１）と、を備える。さらに、追加ノードを設ける際に上記予測遅延量を用いて、追加ノードを接続するノードを決定する手段（図３の１１３）を備える。
【００２７】
上記実施形態によれば、マルチキャストツリーに変更を加える前に各ノードの配下に追加ノードを新たに接続した場合の予測遅延量をノード毎にあらかじめ算出しておくので、マルチキャストツリーの変更が実際に必要になった場合に迅速に最適なマルチキャストツリーの変更を実施できる。従って、データ配信の途中で中間のノードの一部が脱落するような状況が発生しても、遅延量を所定の遅延値以下に収めて迅速にマルチキャストツリーの再構築を行うことができる。
【００２８】
また、本発明の別の実施形態によるマルチキャストシステムは、図８に一例を示すようにルートノード（図２の１００）から複数のノード（図２の２００を２００Ａと読み替え）がツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、ルートノード１００から各ノード２００Ａまでの遅延量を算出する手段（図８の２１２）と、基準とする遅延量と算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段２３１と、各ノードへのデータ到着時に算出した意図的な遅延量を挿入する手段２３２と、を備える。
【００２９】
上記別の実施形態によるマルチキャストシステムによれば、各ノードの遅延量を精度よく揃えることができる。
【００３０】
なお、上記実施形態の概要に付記した図面参照符号は専ら理解を助けるための例示であり、図示の態様に限定することを意図するものではない。以上で概要についての説明を終え、以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。
【００３１】
［第１の実施形態］
図２は、マルチキャストシステムにおけるマルチキャストツリーの構成例を示す概念図である。図２において、マルチキャストツリー１は、ルートノード１００と複数のノード２００によって論理ネットワークを構成している。ルートノード１００は、少なくとも一つのノード２００に接続され、そのノード２００は、ツリーの末端となるノード２００を除いて少なくとも一つの別のノード２００に接続されている。ルートノード１００、ノード２００から複数のノード２００に枝分かれして接続されることによって、ルートノード１００を頂点とするネットがツリー状に広がり、ルートノード１００から発信する情報がツリー状に多数のノード２００に伝えられることになる。
【００３２】
ノード２００は、ルートノード１００、もしくは１つまたは複数のノード２００と接続する。各ノード２００は、接続しているルートノード１００、もしくはノード２００からデータを受信した場合に、マルチキャストツリー１での下流にあるノード２００にデータを転送する。
【００３３】
図１は、実施形態１の概念を示す図面であり、図１（ａ）は、再構成前のマルチキャストツリーの構成を示す概念図であり、図１（ｂ）再構成後のマルチキャストツリーの構成を示す概念図である。図１のマルチキャストツリー１において、配信遅延を指定した値以下に収めるため、ノードを移動させることによってマルチキャストツリーの構成を変更する構成例を示している。図１（ａ）がノード移動前、図１（ｂ）がノード移動後である。
【００３４】
図１において、ルートノード１００、ノード２００にそれぞれコロンで区切って付している３つの符号は、左端の一つ目の符号は、各ノードのノードＩＤを示している。また、中央の二つ目の符号は、ルートノード１００（ノードＩＤ：ｎ２）から自己のノードまでの配信遅延量である。この遅延量は推定遅延量であってもよいし、実測値が得られていれば実測値であってもよい。さらに、右端の三つ目の符号は、自己のノードに新たなノードを直接接続して追加すると仮定した場合の配信遅延の予測値である。この予測値は、ルートノードから追加ノードまでの予測遅延量を表している。この予測遅延量は、新規にマルチキャストツリーに接続するノードが接続先を選択する場合の目安とする数値である。
【００３５】
あるノードｉの（推定）遅延量をＤ＿ｉ、１世代下のｊ番目のノードへデータを配信するための処理遅延量をＤＰ＿ｉｊ、上記ノードｉとその１世代下のｊ番目のノード間のネットワーク遅延をＤＮ＿ｉｊとすると、ノードｉの１世代下のｊ番目のノードの推定遅延量Ｄ＿ｉｊは、式１で表すことができる。
【００３６】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ＿ｉｊ＋ＤＮ＿ｉｊ （式１）
【００３７】
ここで、Ｐ＿ｉ０を、ノードｉがノードｉの親ノードからパケットを受信してから配下１番目の１世代下のノードへデータを送信するまでのノード内転送処理遅延、Ｐ＿ｉｊをノードｉにおける配下ｊ番目の１世代下のノードへデータを送信してから配下ｊ＋１番目の１世代下のノードへデータを送信するまでのノード内転送処理遅延とすると、１世代下のｊ番目のノードへデータを配信するための処理遅延量ＤＰ＿ｉｊは、
ＤＰ＿ｉｊ＝ＤＰ＿ｉ（ｊ−１）＋Ｐ＿ｉ（ｊ−１）
ＤＰ＿ｉ１＝Ｐ＿ｉ０
と書ける。
【００３８】
このとき、ノードｉにおける配下ノード間、および配下ノードへのデータ送信処理に差分がないとすると式１は簡略化することができる。具体的には、Ｐ＿ｉ０＝Ｐ＿ｉ１＝Ｐ＿ｉ２＝Ｐ＿ｉ３…、かつＤＮ＿ｉ１＝ＤＮ＿ｉ２＝ＤＮ＿ｉ３＝ＤＮ＿ｉ４…と仮定出来る時、式１は、式２のように簡略化できる。
【００３９】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ＿ｉ×ｊ＋ＤＮ＿ｉ （式２）
【００４０】
ここでＤＰ＿ｉは、ノードｉにおける１回のデータ転送に掛かる処理遅延である。また、ＤＮ＿ｉはノードｉにおける１世代下のノードへのネットワーク遅延である。この値は、例えば、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）、代表的な配下のノードまたは１世代上のノードの値、から静的または動的に算出する。なお、「処理遅延」とは、ノード内部の遅延であり、「配信遅延」とは、ノード間を接続するネットワークの遅延である。すなわち、各ノードの実際の処理遅延、各ノード間の実際の配信遅延、各ノードの実際の処理能力を用いて算出する。「ノード処理能力」は、マシンの性能であるため、固定であるが、「処理遅延」はマシン内の処理状況により変化し、「配信遅延」はネットワークの状況により変化する。この変化するパラメータについて、たとえば平均値を用いて静的に算出してもよいし、一定時間の移動平均を用いて動的に算出してもよい。
【００４１】
さらに、マルチキャストツリーに参加するどのノードにおいても、ＤＰ＿１＝ＤＰ＿２＝…＝ＤＰ、かつＤＮ＿１＝ＤＮ＿２＝…＝ＤＮと仮定できる場合、式２をさらに簡略化して式３とすることができる。
【００４２】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ×ｊ＋ＤＮ （式３）
【００４３】
ここで、ＤＰは、１回のデータ転送に掛かる処理遅延である。また、ＤＮは１世代下のノードへのネットワーク遅延である。この値は、例えば、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）、任意のノードの値、から静的または動的に算出する。
【００４４】
図１の例ではルートノードｎ２の推定遅延量を０として、式３を適用し、かつＤＰ＝ＤＮ＝１とした場合を示している。例えば、ルートノードｎ２の遅延量は０、配下１番目のノードｎ８の遅延量は２となり、ルートノードｎ２がノードｎ８に続いてデータを転送するノードｎ１１の遅延量は３となる。
【００４５】
また、具体的には、新たに接続するノードの予測遅延量とは、そのノードに新たにノードが接続してきた場合の、その新規に接続してきたノードの推定遅延量と定義する。新規に接続するノードや、接続先を変更するノードにとって、新たに接続するノードの（推定）遅延量が小さいノードに接続した方が、より配信遅延が小さいことになる。新たに接続するノードの予測遅延量を式で表現する場合、新たに接続するノードがノードｉのｎ番目の子供（配下に直接接続されるノード）になるとして、あるノードｉの（推定）遅延量をＤ＿ｉ、ノードｉの新たに接続するノードの予測遅延量をＤ＿ｉｎ、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の予測値をＤＰ＿ｉｎ、新規ノードが接続した場合のネットワーク遅延の予測値をＤＮ＿ｉｎとすると、式４が成立する。
【００４６】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ＿ｉｎ＋ＤＮ＿ｉｎ （式４）
【００４７】
ここで、式１から式２の導出と同様に、ノードｉにおける配下ノード間、および配下ノードへのデータ送信処理に差分がないとすると、式４は簡略化することができる。具体的には、Ｐ＿ｉ０＝Ｐ＿ｉ１＝Ｐ＿ｉ２＝Ｐ＿ｉ３…、かつＤＮ＿ｉ１＝ＤＮ＿ｉ２＝ＤＮ＿ｉ３＝ＤＮ＿ｉ４…と仮定出来る時、式４は、式５のように簡略化できる。
【００４８】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ＿ｉ×ｎ＋ＤＮ＿ｉ （式５）
【００４９】
さらに、式２から式３の導出と同様に、マルチキャストツリーに参加するどのノードにおいても、ＤＰ＿１＝ＤＰ＿２＝…＝ＤＰ、かつＤＮ＿１＝ＤＮ＿２＝…＝ＤＮと仮定できる場合、式５をさらに簡略化して式６とすることができる。
【００５０】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ×（ｃ＋１）＋ＤＮ （式６）
【００５１】
また、上記式１から式６において、Ｄ＿ｉをノードｉの推定遅延量としたが、実測した遅延量が分かる場合はＤ＿ｉに実測した遅延量を用いても良い。
【００５２】
図１の例では、ルートノードｎ２の推定遅延量を０として、式３および式６を適用し、かつＤＰ＝ＤＮ＝１とした場合の、推定遅延量を所定の遅延量８以内に収めるための構成例を示している。具体的には図１（ａ）ではノードｎ９の遅延量は９、ノードｎ１５の遅延量は１０であり、所定の遅延量８より大きい。従って、ノードの組み換えが要求される。また、図１（ａ）において、自己のノードの配下に追加ノードを新たに設けたときの予測遅延量が所定の遅延量８より小さいノードが存在する（ノードｎ２、ｎ８、ｎ１１、ｎ２２の予測遅延量は、それぞれ、０、６、６、７）。従って、ノードｎ９、ｎ１５を上記予測遅延量が８より小さいノードｎ２、ｎ８、ｎ１１、ｎ２２のいずかに接続を変更することにより、全ノードの遅延量を所定の遅延量８以内に収める可能性があると考えられる。図１（ｂ）では、ノードｎ９をノードｎ１１の配下に、ノードｎ１５をルートノードｎ２の配下に移動させている。
【００５３】
この結果、ルートノードｎ２の新たに接続する追加ノードの予測遅延量が４から５に、ノードｎ１１の新たに接続する追加ノードの予測遅延量が６から７に、ノードｎ１５の推定遅延量および新たに接続する追加ノードの予測遅延量がそれぞれ１０から４および１２から６に、ノードｎ９の推定遅延量および新たに接続するノードの予測遅延量がそれぞれ９から６および１１から８に、更新され、全てのノードの（推定）遅延量が指定された所定の遅延量８を超えない構成となる。なお、ノードｎ２３の配下に接続されるノードがなくなったため、ノードｎ２３の追加ノードの予測遅延量も、１１から９に更新されている。このように、配信遅延が指定した値以下に納まらないノードを、追加ノードの予測遅延量を基準に配信遅延が指定した値以下に納まるノードへ接続先を変更させ、マルチキャストツリーを再構成することにより、マルチキャストツリーにおいて配信遅延を指定した値以下に収めることができる。
【００５４】
次に、上記図１を用いて説明した実施形態１のマルチキャストツリーの変更を行うマルチキャストシステムのノード２００及びルートノードの構成について説明する。
【００５５】
図４は、図１、図２におけるルートノード１００以外のノードの内部構成を示すブロック図である。図４において、ノード２００は、主制御部２１０とネットワークインターフェイス２２０と、ノード情報データベース２２１と、を有する。ネットワークインターフェイス２２０は、ネットを介してルートノード１００又は他のノード２００と接続されている。
【００５６】
主制御部２１０は、ＣＰＵ、ＲＡＭ、及びＯＳなどで構成されたコンピュータの主要部であり、主制御部２１０の中に、動作するプログラムとして構成されている送受信部２１１と、推定遅延量計算機能部２１２と、を有する。
【００５７】
図５は、図２におけるノード情報データベース２２１の内部データ構成の一例を示す概念図である。データの一例として図２におけるノードｎ３のノード情報データベース２２１を例示している。ノード情報データベース２２１は、マルチキャストツリー１におけるノード情報を保存する。ノード情報とは、ノード２００を一意に識別するノードＩＤ、ＩＰアドレス、ポート番号など他のノード２００とメッセージを送受信するために必要な情報であり、マルチキャストツリー１のツリー構造において自ノードより上及び下にあるノード２００の情報である。また、ノード情報データベース２２１には各ノードの（推定）遅延量および新たに接続する追加ノードの予測遅延量も保存される。
【００５８】
推定遅延量計算機能部２１２は、マルチキャストツリーにおいて、配下に接続しているノード２００の（推定）遅延量と自ノードの新たに接続する追加ノードの予測遅延量を計算する。配下に接続しているノード２００の（推定）遅延量の計算は、式１または式２を用いる。また、新たに接続する追加ノードの予測遅延量の計算は、式４または式５を用いる。ただし、新たに接続されると仮定している追加ノードは、まだ特定されていないのでで、ネットワーク遅延の推定値ＤＮ＿ｉｎは仮想的な値である。計算結果は、ノード情報データベース２２１に保存し、配下に接続しているノード２００の推定遅延量は、該当する配下のノード２００に通知する。
【００５９】
推定遅延量計算機能部２１２における、（推定）遅延量と新たに接続する追加ノードの予測遅延量の計算は、ルートノード１００からの（推定）遅延量と新たに接続するノードの予測推定遅延量収集の要求が来た場合、配下のノード２００に増減などの変化があった場合、ノード２００のオペレータからの指示があった場合などに実施される。
【００６０】
図３は、第１の実施形態によるマルチキャストシステムに用いられるルートノード１００の内部構成を示すブロック図である。図３において、ルートノード１００は、主制御部１１０とネットワークインターフェイス１２０と、ノード情報データベース１２１と、を有する。主制御部１１０は、ＣＰＵ、ＲＡＭ、及びＯＳなどで構成されたコンピュータの主要部である。ルートノード１００は、主制御部１１０の中に、動作するプログラムとして構成されている送受信部１１１と、推定遅延量収集機能部１１２と、トポロジ決定機能部１１３と、を有する。
【００６１】
ノード情報データベース１２１は、図５を用いてすでに説明したノード２００のノード情報データベース２２１に相当するデータベースである。ただし、ルートノード１００のノード情報データベース１２１の場合は、推定遅延量収集機能部１１２が各ノードから収集した各ノードのノード情報と（推定）遅延量および各ノードに新たに追加ノードが接続された場合の予測遅延量も保存される。
【００６２】
送受信部１１１は、ネットワークインターフェイス１２０を介して、ノード２００からのメッセージを受信して、メッセージ種別を見た上で、推定遅延量収集機能部１１２またはトポロジ決定機能部１１３に送る。
【００６３】
また、送受信部１１１は、推定遅延量収集機能部１１２またはトポロジ決定機能部１１３からメッセージを受け取り、メッセージに記載されている宛先であるノード２００にネットワークインターフェイス１２０を介してメッセージを送信する。
【００６４】
推定遅延量収集機能部１１２は、マルチキャストツリー１に参加するノードから、それぞれの（推定）遅延量および新たに接続する追加ノードの予測遅延量を収集し、ノード情報データベース１２１を更新する。（推定）遅延量および新たに接続するノードの予測遅延量の収集方法としては、例えば、ルートノード１００から配下のノード２００に対し、推定遅延量および新たに接続する追加ノードの予測遅延量を要求するメッセージを送信し、推定遅延量および新たに接続する追加ノードの予測遅延量を要求するメッセージを受信したノード２００は、さらに配下のノード２００にメッセージを転送し、マルチキャストツリー１のリーフの位置のノード２００から（推定）遅延量および新たに接続するノードの予測遅延量を、逆順で返信していく方法がある。あるいはルートノード１００がマルチキャストツリー１に接続しているノード２００とそれぞれ直接通信して（推定）遅延量および新たに接続するノードの予測遅延量を収集してもよい。また、実測した遅延量が分かる場合は推定遅延量に代わりに実測した遅延量を用いても良い。
【００６５】
トポロジ決定機能部１１３は、ノード情報データベース１２１を参照し、マルチキャストツリー１に参加しているノード２００の（推定）遅延量および新たに接続するノードの予測遅延量を参照する。次に、指定された遅延量より大きい（推定）遅延量のノード２００を抽出する。ここで抽出されたノード群をノード群Ａとする。また、指定された遅延量より小さい新たに接続するノードの予測遅延量を有するノード２００を抽出する。ここで抽出されたノード群をノード群Ｂとする。すなわち、ノード群Ａのノードは、そのノードの現在の（推定）遅延量が指定された基準となる遅延量より大きいノードであり、ノード群Ｂのノードは、新たに配下にノードを追加した場合の予測遅延量が指定された基準となる遅延量より小さい遅延量を有するノードである。
【００６６】
このとき、ノード群Ａの中に、ひとつ以上のノード２００が含まれていた場合、ノード群Ａをノード群Ｂの配下に接続させる。
【００６７】
ノード群Ａのどのノード２００をノード群Ｂのどのノード２００の配下に接続するかは、例えば、予測遅延量の大きいノード順に、新たに接続するノードの推定遅延量が小さいノードへ接続させることができる。また、マルチキャストツリー１上の位置がなるべく変わらない位置になるノードの配下に接続させることでもよい。それ以外の方法でもよいが、遅延量の大きなノードをそのノードの現在の遅延量より予測遅延量が小さいノードに接続をつなぎ変えることにより、遅延量の最大値を小さくすることができる。また、タイムスタンプを利用するなどによって、実測した遅延量が分かる場合はノード群Ａを抽出する際に推定遅延量に替わりに実測した遅延量を用いても良い。
【００６８】
トポロジ決定機能部１１３は、ノードの移動先を決定したのち、移動させるノード２００に対し、移動のメッセージを送信する。
【００６９】
ここで、配信遅延時間の指定はマルチキャストツリーのオペレータにより静的または動的に設定される。マルチキャストツリー１に参加するノード２００の数により配信遅延時間の指定には下限がある。下限よりもさらに小さい値を指定する場合、ノード群Ａのノードの数の方がノード群Ｂのノードの数よりも大きくなり、配信遅延が指定した値以下にならないノード２００が存在してしまう。このとき、前記ノードに対し、アラームを通知する、または強制的にマルチキャストツリー１から離脱させる、などの方法をとる。
【００７０】
また、トポロジ決定機能部１１３は、新規にマルチキャストツリーに参加するノード２００に対し、すでにマルチキャストツリーに参加しているノード２００の新たに接続する追加ノードの予測遅延量の情報を提供する。新規にマルチキャストツリーに参加するノード２００は、入手した新たに接続するノードの予測遅延量の情報から指定されている配信遅延時間を超えない接続先となるノード２００を選出し、接続することでマルチキャストツリーに参加する。このとき、指定されている配信遅延時間を超えない接続先が存在しない場合、アラームを上げた上で接続する、または接続を断念する、などの方法を取る。
【００７１】
推定遅延量収集機能部１１２における、（推定）遅延量と新たに接続するノードの予測遅延量の収集、および、トポロジ決定機能部１１３におけるトポロジ決定とノードの移動は、マルチキャストツリー１に接続するノード２００に増減などの変化があった場合、ルートノード１００のオペレータからの指示があった場合などに実施される。
【００７２】
次に、第１の実施形態の動作について、特に特徴的な部分について説明する。
【００７３】
図６は、本実施形態におけるルートノード１００において、マルチキャストツリー１における配信遅延を一定値以内に収めるようトポロジを変更する場合の動作を示すフローチャートである。動作を開始すると、まず送受信部１１１が他のノード２００、もしくはルートノード１００内の主制御部１１０からの通信を待つ状態（以後、アイドル状態という）となる（ステップＳ３００）。
【００７４】
ルートノード１００は、アイドル状態中に（ステップＳ３００）、マルチキャストツリー１に接続するノード２００に増減などの変化があった場合または、ルートノード１００のオペレータからの指示があった場合などに、マルチキャストツリー１に参加するノード２００から（推定）遅延量と新たに接続するノードの予測遅延量を収集し（ステップＳ３０１）、ノード情報データベース１２１を更新する（ステップＳ３０２）。
【００７５】
続いて、ノード情報データベース１２１を参照し、指定された遅延量より（推定）遅延量が大きいノード２００を抽出する（ステップＳ３０３）。さらに、ノード情報データベース１２１を参照し、指定された遅延量より追加ノードの予測遅延量が小さいノード２００を抽出する（ステップＳ３０４）。さらに、ステップＳ３０３で抽出したノードをステップＳ３０４で抽出したノードへ接続させる（ステップＳ３０５）。次に、ステップＳ３０３で抽出したノードの数とステップＳ３０４で抽出したノードの数を比較し（ステップＳ３０６）、ステップＳ３０４で抽出したノードの数の方が大きい場合は、ステップＳ３００のアイドル状態に戻る。ステップＳ３０３で抽出したノードの数の方が大きい場合は（ステップＳ３０６の下への遷移）、移動できなかったノード２００に対しアラームを送信し（ステップＳ３０７）、アイドル状態に戻る。
【００７６】
なお、図６で説明したフローチャートに係る各ステップの動作内容は、ルートノード１００が予め備えるコンピュータ（主制御部）で動作するプログラムとして実行させるように構成することができる。
【００７７】
上述した説明では、すでに存在するマルチキャストツリー１の再構成について説明したが、新たなノードが、新規にマルチキャストツリー１に参加する場合において、すでにマルチキャストツリー１を構成しているどのノード２００に接続するかを決定する時に、新たに接続するノードの予測遅延量をマルチキャストツリー１に参加している各ノード２００から収集し、追加ノードの予測遅延量を基準として、追加ノードの予測遅延量が小さいノードに接続することによって、マルチキャストツリー１の配信遅延を指定した値以下に収めるようにすることもできる。このとき、マルチキャストツリー１の配信遅延を指定した値以下に収めることができるような接続先がない場合、新規参加を拒否する、またはアラームを通知した上で参加を許可する、ということもできる。
【００７８】
図７は、第１の実施形態におけるルートノード以外のノード２００の処理フローチャートである。動作を開始すると、まず送受信部２１１が他のノード２００、もしくはルートノード１００内の主制御部１１０からの通信を待つ状態（以後、アイドル状態という）となる（ステップＳ４００）。ルートノードからの指示により、当該ノードの接続が変わる場合（ステップＳ４０１でＹｅｓ）は、ノード情報データベース２２１のトポロジ情報を更新する（ステップＳ４０２）。また、ステップＳ４０２ではタイムスタンプ等を利用して遅延値の実測値が得られたら、推定遅延値を実測値に置き換えてもよい。
【００７９】
ステップＳ４０３では、ルートノード１００や当該ノードとルートノードとの間に介在するノード（親ノード）からノード情報データベース２２１の照会があった場合（ステップＳ４０３でＹｅｓ）は、当該照会の内容に応答して最新のノード情報データベース２２１の内容を問い合わせ先に回答し（ステップＳ４０４）、その後、ステップＳ４００のｉｄｌｅ状態に戻る。一方、ノード情報データベース２２１の照会がなかった場合（ステップＳ４０３でＮｏの場合）は、何もせず、ステップＳ４００のｉｄｌｅ状態に戻る。
【００８０】
また、上述した説明では、ルートノード１００がマルチキャストツリー１に参加するノード２００から、（推定）遅延量と新たに接続するノードの予測遅延量を収集し、マルチキャストツリー１のトポロジを決定するとしたが、この機能はルートノード１００が持たなくてもよい。すなわちあるノード２００でもよいし、第３のコンピュータでもよい。この場合、ルートノード１００もノード２００と同様のノードとして動作する。
【００８１】
［第２の実施形態］
次に、本発明の第２の実施形態を、図面を参照して説明する。
【００８２】
本発明の第２の実施形態では、ある指定した推定遅延量を基準に、データ到着時に遅延を挿入することにより、マルチキャストツリーに参加するノード間における、配信遅延のばらつきを小さくすることができる。
【００８３】
図１（ａ）を例として、第２の実施形態の概念から説明する。図１（ａ）において、ノードｎ８の（推定）遅延量は２、ノードｎ２２の（推定）遅延量は５である。このとき、ノードｎ８において（推定）遅延量３の分だけデータ受信時にノード内部で遅延させると推定遅延量５相当となり、ノードｎ８とノードｎ２２の間の配信遅延の差が小さくなる。
【００８４】
さらに、遅延量１０を基準とすると、ノードｎ８は遅延量８の遅延、ノードｎ２２は遅延量５の遅延、ノードｎ１１は遅延量７の遅延というように、自ノードの遅延量と基準遅延量の差分だけ、データ受信時にノード内部で遅延させると、データ受信の配信遅延が、全てのノードでほぼ等しくなる。なお、配下に他のノードが接続されているノードは、配下に転送するデータに関しては、遅延を挿入せずに、データ到着時、速やかに配下のノードに転送する。たとえば、ノードｎ８はノードｎ３とノードｎ４４、ノードｎ１１はノードｎ２２にデータ転送を行うが、この他のノードへ転送するデータには、遅延を挿入しない。この様な処理を行うことにより、配信先の末端での配信遅延のばらつきを小さくすることができる。式で表現すると、ノードｉの遅延量をＤ＿ｉ、基準とする遅延量をＤＢ、意図的に挿入する遅延量をΔＤ＿ｉとすると、式７が成立する。
【００８５】
ΔＤ＿ｉ＝ＤＢ−Ｄ＿ｉ （式７）
【００８６】
このとき基準とする遅延量は、マルチキャストツリー１に参加するノード２００の中で最大の遅延量と同じか、大きくする必要がある。この基準とする遅延量を決定するには、マルチキャストツリー１に参加するノード２００の中で最大の遅延量が分かればよい。マルチキャストツリー１に参加するノード２００の中で最大の遅延量は、トポロジを決定する過程で得られる。ただし、全ノードの（実測または推定の）遅延量の情報を得ることが困難な場合、例えばマルチキャストツリーに参加するノード２００の数が膨大である場合、マルチキャストツリー１に参加するノード２００の中で最大の遅延量を推定する。その方法は例えば、マルチキャストツリーに参加するノード２００の数から推定する、マルチキャストツリーの最下層のあるノードの推定遅延量から推定する、などがある。
【００８７】
また、データ到着時に挿入する遅延量は少ない方が好ましいため、前述の意図的に挿入する遅延量を求める前に、本発明の第１の実施形態の手段を用いて、予めマルチキャストツリー１に参加するノード２００の中で最大の推定遅延量を小さくしておくとよい。具体的には、基準とする推定遅延量を下限に設定し、マルチキャストツリー１のトポロジを変更しておくことで、マルチキャストツリー１に参加するノード２００の中で最大の推定遅延量を小さくできる。
【００８８】
また、基準とする遅延量の周知は、例えば初回のデータとして送付することで周知させることができる。基準とする遅延量をマルチキャストツリーに参加するノードに周知させておくことにより、最大遅延量または最大遅延量よりも大きな値を基準値として事前に与えておき、それを基準に意図的に挿入する遅延量ΔＤ＿ｉを算出することができる。
【００８９】
図８は、第２の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。図８のノード２００Ａは、第１の実施形態のノード２００に置き換えて用いる。図８のノード２００Ａについて、図４を用いて説明した第１の実施形態のノード２００と異なる構成について説明する。第１の実施形態のノード２００と構成が同一である部分については、同一の符号を付し、重複する説明は省略する。
【００９０】
挿入遅延量算出部２３１は、ルートノード１００から基準とする遅延量の指定を受けて、ノード情報データベースに含まれる自ノードの（推定）遅延量に基づいて、データ受信時に挿入する遅延量を算出する。
【００９１】
遅延挿入部２３２は、ルートノード１００からデータの配信を受ける際に、送受信部に受信したデータを挿入遅延量算出部２３１が算出した挿入遅延量に基づいて、遅延させる。
【００９２】
また、ルートノード１００は、初回のデータ配信において、基準となる遅延量を各ノード２００Ａに対して送信することを除いて、第１の実施形態のルートノード１００をそのまま用いることができる。
【００９３】
上述した説明では、マルチキャストツリー１全体でひとつの基準とする推定遅延量を周知させることにより、配信遅延のばらつきを小さくすることができるとしたが、マルチキャストツリー１に参加するノードを複数のグループに分割し、そのグループそれぞれで基準とする推定遅延量を設定し、グループ内の基準とする推定遅延量から意図的に挿入する遅延量ΔＤ＿ｉを算出し、データ到着時に遅延を挿入することにより、グループ内のノード間における、配信遅延のばらつきを小さくすることができる。
【００９４】
また、上述した説明では、マルチキャストツリー１全体で基準とする推定遅延量を周知させることにより、配信遅延のばらつきを小さくすることができるとしたが、推定遅延量が同じまたは近いノード２００をグループ化することで、グループ内の配送遅延のばらつきを小さくすることも出来る。
【００９５】
図１（ａ）を例とすると、ノードｎ４４と、ノードｎ２２は何れも推定遅延量５である。これらのノードをグループとすると、グループ内では推定遅延量が同値であるため、グループ内の配送遅延のばらつきを小さくすることが出来る。
【００９６】
以上説明したように、推定遅延量をノード内転送処理遅延と転送リンクのネットワーク遅延の総和から算出し、推定遅延量および新たに接続するノードの推定遅延量を基準に、配信遅延が指定した値以下に納まらないと推定されるノードを、配信遅延が指定した値以下に納まるように、マルチキャストサービス開始より前に移動させ、マルチキャストツリーを再構成することにより、マルチキャストツリーに参加するノードの配信遅延を指定した値以下に収めることができる。
【００９７】
また、以上説明したように、推定遅延量をノード内転送処理遅延と転送リンクのネットワーク遅延の総和から算出し、推定遅延量および新たに接続するノードの推定遅延量を基準に、データ到着時に遅延を挿入することにより、マルチキャストツリーに参加するノード間における、配信遅延のばらつきを小さくすることができる。
【００９８】
なお、本発明において下記の形態が可能である。
［形態１］
前記第１の視点に記載のマルチキャストシステムのとおり。
［形態２］
前記追加ノードを接続するノードを決定する手段は、前記予測遅延量が所定の遅延値以下であるノードに前記追加ノードを接続し、
前記予測遅延量が所定の遅延量以下となるノードが存在しない場合は、前記追加ノードを含めた前記複数のノードの遅延量がいずれも前記所定の遅延量以下となるように、前記マルチキャストツリーを組み替えることが好ましい。
［形態３］
前記各ノードは、それぞれ、
自己ノードの下流に追加ノードを接続すると仮定した場合の予測遅延量を算出する手段と、
前記算出した予測遅延量を記憶する手段と、を備え、
前記マルチキャストシステムは、前記各ノードが算出した前記各ノードの予測遅延量を収集して一括して記憶する手段を備え、
前記ノードを決定する手段は、前記一括して記憶された各ノードの予測遅延量を用いて前記追加ノードを接続するノードを決定することが好ましい。
［形態４］
前記予想遅延量を算出する手段は、前記接続先となり得るノードの処理能力と、ルートノードから当該ノードまでの遅延量と、当該ノードから前記追加ノードまでのネットワーク遅延を平均的であると仮定した仮想ネットワーク遅延量と、に基づいて予想遅延量を算出することが好ましい。
［形態５］
前記第２の視点に記載のマルチキャストシステムのとおり。
［形態６］
前記第３の視点に記載のマルチキャストシステムのノードのとおり。
［形態７］
前記マルチキャストツリー構造がルートノードから前記複数のノードがツリー状に接続されたマルチキャストシステムであって、
前記推定遅延量計算機能部と前記ノード情報記憶部とを備える前記ノードが、前記ルートノード以外の前記ノードであることが好ましい。
［形態８］
前記第４の視点に記載のマルチキャストシステムのルートノードのとおり。
［形態９］
前記第５の視点に記載のマルチキャストシステムのマルチキャストツリー更新方法のとおり。
［形態１０］
前記第６の視点に記載のマルチキャストシステムのコンピュータプログラムのとおり。
［形態１１］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、を有するマルチキャストシステム。
［形態１２］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集する手段と、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成する手段と、を有するマルチキャストシステム。
［形態１３］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、新規にマルチキャストツリーに参加するノードに対し、マルチキャストツリーを構成するノードの配下に新たにノードが接続したと仮定した時の推定遅延量を通知する手段と、前記推定遅延量から、配信遅延が指定した値以下に納まる接続先となるノードを選出する手段と、を有するマルチキャストシステム。
［形態１４］
前記形態１１乃至１３のいずれかに記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、任意のノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１５］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーを構成する全ノードの平均の、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１６］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１７］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、処理遅延と配信遅延が等しいと仮定して、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１８］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーを構成する全ノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）で重み付けした平均値を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１９］
前記形態１１乃至１３のいずれかに記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、任意のノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２０］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーを構成する全ノードの平均の、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２１］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２２］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２３］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、処理遅延と配信遅延が等しいと仮定して、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２４］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーを構成する全ノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）で重み付けした平均値を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２５］
マルチキャストシステムを構成するノードであって、マルチキャストツリーに参加するノードから、それぞれの推定または実測の遅延量および新たに接続するノードの推定遅延量を収集する手段と、収集した推定または実測の遅延量および新たに接続するノードの推定遅延量から、指定された推定遅延量より大きい推定または実測の遅延量のノードを、指定された推定遅延量より小さい新たに接続するノードの推定遅延量をもつノードの配下に接続させる手段と、マルチキャストツリーに参加するノードの推定または実測の遅延量および新たに接続するノードの推定遅延量を含むノード情報を保持する手段と、を有するノード。
［形態２６］
マルチキャストシステムを構成するノードであって、配下に接続しているノードの推定または実測の遅延量と自ノードの新たに接続するノードの推定遅延量を計算する手段と、自ノードの推定または実測の遅延量および新たに接続するノードの推定遅延量を含むノード情報を保持する手段と、を有するノード。
［形態２７］
マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーを構成するノードの推定遅延量を算出する手段と、基準とする遅延量とノードの推定または実測の遅延量の差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、データ到着時に前記意図的な遅延量を挿入する手段と、を有するマルチキャストシステム。
［形態２８］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、実測遅延量の最悪値とするマルチキャストシステムであることが好ましい。
［形態２９］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、推定遅延量の最大値とするマルチキャストシステムであることが好ましい。
［形態３０］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、推定遅延量が大きくなりそうな位置にあるノードの実測値とするマルチキャストシステムであることが好ましい。
［形態３１］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーに参加するノードを複数のグループに分割する手段と、そのグループそれぞれで基準とする推定または実測の遅延量を設定する手段と、グループ内の基準とする推定または実測の遅延量から意図的に挿入する遅延量を算出する手段と、前記遅延量の分だけデータ到着時に遅延を挿入する手段と、を有するマルチキャストシステムであることが好ましい。
［形態３２］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、推定または実測の遅延量が、同じまたは近いノードをグループ化する手段と、を有するマルチキャストシステムであることが好ましい。
［形態３３］
マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集するステップと、指定された推定または実測の遅延量より大きい遅延量のノードを抽出するステップと、指定された推定または実測の遅延量より小さい新たに接続するノードの推定遅延量のノードを抽出するステップと、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成するステップと、を有するマルチキャスツリー構成方法。
［形態３４］
マルチキャストツリーから構成されるマルチキャストシステムを構成するノードを制御するコンピュータに、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集する機能と、指定された推定または実測の遅延量より大きい遅延量のノードを抽出する機能と、指定された推定または実測の遅延量より小さい新たに接続するノードの推定遅延量のノードを抽出する機能と、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成する機能と、を実行させるプログラム。
［形態３５］
基準とする遅延量を指定する手段と、
前記複数のノードのうち、少なくとも一部のノードは、前記基準とする遅延量と自己の遅延量との差分を求める手段と、当該ノードへのデータ到着時に前記差分を埋める遅延量を挿入する手段と、を備える形態１乃至３のいずれかに記載のマルチキャストシステムであることが好ましい。
［形態３６］
前記推定遅延量計算機能部は、前記マルチキャストツリーに含まる他のノードが計算した予測遅延量を収集する機能を含み、
さらに、前記収集した予測遅延量を用いて前記マルチキャストツリーの再構築を行うトポロジ決定機能部をさらに含むことを特徴とする形態６又は７に記載のマルチキャストシステムのノードであることが好ましい。
［形態３７］
前記推定値遅延量収集機能部は、自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部を兼ね備え、
前記推定遅延量収集機能部が集積した前記予測遅延量を含む現在の前記マルチキャストツリー構造のトポロジを記憶するノード情報記憶部をさらに備え、
前記トポロジ決定機能部が、前記ノード情報記憶部に記憶されたマルチキャストツリー全体のノード情報を用いて前記マルチキャストツリー構造の変更を行う形態８に記載のマルチキャストシステムのルートノードであることが好ましい。
［形態３８］
前記各ノードのうち、データ配信の目的地であると共に他のノードへのデータ転送の中継も行うノードにおいて、前記意図的な遅延量を挿入する手段は、前記他のノードへ中継するデータには前記遅延量を挿入せずに、データの受信後、速やかにデータ転送を行う形態５のマルチキャストシステムであることが好ましい。
【００９９】
本発明の全開示（特許請求の範囲及び図面を含む）の枠内において、さらにその基本的技術思想に基づいて、実施例ないし実施例の変更・調整が可能である。また、本発明の特許請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、特許請求の範囲及び図面を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１００】
１：マルチキャストツリー
１００：ルートノード
２００、２００Ａ：ノード
１１０、２１０：主制御部
１２０、２２０：ネットワークインターフェイス
１２１、２２１：ノード情報データベース
１１１、２１１ 送受信部
１１２：推定遅延量収集機能部
１１３：トポロジ決定機能部
２１２：推定遅延量計算機能部
２３１：挿入遅延量算出部
２３２：遅延挿入部
【技術分野】
【０００１】
本発明は、マルチキャストシステムに関する。特に、ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに関する。さらには、マルチキャストシステムのノード、マルチキャストツリー更新方法、マルチキャストシステムにおいてノードを追加してツリーを再構成するコンピュータプログラムに関する。
【背景技術】
【０００２】
ＷＥＢサーバーの更新情報や、センサなどが生成するデータを多数の機器に配信する際に、データの配信元をルートとするマルチキャストツリーを用いて配信するマルチキャストシステムがある。
【０００３】
このマルチキャストツリーは、そのデータを利用するノードで構成される論理ネットワークで、配信元毎に作成する場合や、１つのマルチキャストツリーを共有する場合がある。データはマルチキャストツリーの構成に従ってノード間を転送される。
【０００４】
マルチキャストツリー構成方法に関して、多量の利用者に対しリアルタイムにデータを配信するためのマルチキャストツリーを構築する手段がいくつか提案されている。
【０００５】
例えば、特許文献１では、ノードのＣＰＵ使用率、メモリ利用率、ＣＰＵスペック、物理的近傍度、生存時間といった情報を周囲のノードと交換し、周囲から受信する複数の情報を比較評価することによって、マルチキャストツリーを構築する手段が開示されている。なお、「物理的近傍度」は、ノードとノードとの間でピア間接続動作の応答時間を測定することにより得ることができる。また、「生存時間」は、１回の接続でその端末のネットワークへの平均接続時間を、平均生存時間とすることができる。
【０００６】
また、特許文献２では、ホップ数またはある時刻における到着パケットのシーケンス番号の推定値で評価し、マルチキャストツリーを構築する手段が開示されている。
【０００７】
さらに、特許文献３では、複数のノードにより構成されるネットワークにおいて、与えられた始点ノードから複数の終点ノードまでのマルチキャスト転送経路を求めるためのマルチキャスト転送経路計算方法であって、ネットワークのトポロジ情報と遅延情報とを用いて、始点ノードから終点ノードまでの遅延最小経路を各終点ノード毎に求め、始点ノードと各終点ノードまでの複数の遅延最小経路のうちの１つの遅延最小経路上のノードを、マルチキャスト転送における集約点ノードの候補ノードとして選択し、各候補ノードに対し、候補ノードから終点ノードまでの遅延最小経路を各終点ノード毎に算出し、各終点ノード毎の複数の遅延最小経路の遅延のうちの最大値と最小値との差を求め、誤差が最小となる候補ノードを集約点ノードとして選択し、始点ノードから集約点ノードまでの遅延最小経路と、集約点ノードから各終点ノードまでの各遅延最小経路とをマルチキャスト転送経路として出力する。上記特許文献３によれば、マルチキャスト転送経路の計算速度の向上を実現し、また、ユーザ間遅延分散の削減を可能とすることができると記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−２５２５９６号公報
【特許文献２】特開２００４−２４６７９０号公報
【特許文献３】特開２００４−２０８２８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
なお、上記特許文献１乃至特許文献３の全開示内容はその引用をもって本書に繰込み記載する。
【００１０】
以下の分析は、本発明によって与えられたものである。
【００１１】
従来技術における第１の問題は、マルチキャストツリーにおけるデータ配信において、配信遅延を指定した値以下に迅速に収めることができないということである。
【００１２】
その理由は、特許文献１および２において、配信遅延の最悪値についてなんら考慮されていないためである。また、特許文献３によれば、配信遅延の最悪値について一応考慮されているが、配信途中において、ルートノードとの中間に位置するノードが脱落したような場合、迅速なマルチキャストツリーの再構築ができないという問題が存在する。
【００１３】
従来技術における第２の問題は、マルチキャストシステムにおける配信遅延のばらつきを一定の範囲内に収めることができない場合があるということである。
【００１４】
一般に、マルチキャストツリーに参加しているノードは、マルチキャストツリー上の位置により、データを受け取るタイミングが異なる。その結果マルチキャストツリーにおける配信遅延のばらつきが大きくなってしまうためである。特許文献３には、一応配信遅延のばらつきを抑えるようにルートを選択するものが記載されているが、ルートの選択によって配信遅延のばらつきを抑えるのには限界がある。
【００１５】
本発明は、このような事情を考慮してなされたものであり、その第１の目的は、ノード内転送処理遅延と転送リンクのネットワーク遅延を考慮したマルチキャストツリーを迅速に構築することによって、参加するノードの配信遅延を指定した値以下に収めることができるマルチキャストシステムを提供することにある。
【００１６】
また、その第２の目的は、マルチキャストツリーに参加するノード間における、配信遅延のばらつきの小さいマルチキャストシステムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明の第１の視点によれば、複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、前記算出した予測遅延量を記憶する手段と、前記追加ノードを設ける際に前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する手段と、を備えるマルチキャストシステムが提供される。
【００１８】
本発明の第２の視点によれば、ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、前記ルートノードから各ノードまでの遅延量を算出する手段と、基準とする遅延量と前記算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、前記各ノードへのデータ到着時に前記算出した意図的な遅延量を挿入する手段と、を備えるマルチキャストシステムが提供される。
【００１９】
本発明の第３の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるノードであって、自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部と、前記算出した予測遅延量を記憶するノード情報記憶部と、を備えるマルチキャストシステムのノードが提供される。
【００２０】
本発明の第４の視点によれば、複数のノードがルートノードからツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるルートノードであって、前記ツリー状に接続された前記各ノードから自己のノードの配下に新たにノードを追加したと仮定してあらかじめ計算された予測遅延量を収集する推定遅延量収集機能部と、前記収集された予測遅延量を用いて前記マルチキャストツリー構造の変更を行うトポロジ決定機能部と、を備えるマルチキャストシステムのルートノードが提供される。
【００２１】
本発明の第５の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておくステップと、前記追加ノードを設ける必要が生じたときに、前記あらかじめ算出しておいた予測遅延量を用いて、前記追加ノードを接続するノードを決定するステップと、前記決定に基づいて、追加ノードをマルチキャストツリーに組み込んでデータ配信を行うステップと、を備えるマルチキャストシステムのマルチキャストツリー更新方法が提供される。
【００２２】
本発明の第６の視点によれば、複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて用いられるコンピュータプログラムであって、前記複数のノードのいずれかに新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出し、記憶手段に記憶させる処理と、前記追加ノードを設ける必要が生じたときに、前記記憶手段に記憶された前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する処理と、を前記マルチキャストシステムに含まれる少なくとも一つのコンピュータに実行させるマルチキャストシステムのコンピュータプログラムが提供される。
【発明の効果】
【００２３】
本発明の第１、第３乃至第６の視点によれば、マルチキャストシステムにおけるデータ配信において、配信遅延を指定した値以下に迅速に収めることが可能になる。
【００２４】
また、本発明の第２の視点によれば、マルチキャストシステムにおける配信遅延のばらつきを一定の範囲内に収めることが可能になる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施形態のマルチキャストシステムにおける（ａ）再構成前のマルチキャストツリーの構成と、（ｂ）再構成後のマルチキャストツリーの構成を示す概念図である。
【図２】マルチキャストシステムにおけるマルチキャストツリーの構成例を示す概念図である。
【図３】本発明の実施形態によるマルチキャストシステムに用いられるルートノードの内部構成を示すブロック図である。
【図４】本発明の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。
【図５】第１の実施形態におけるノード情報データベースのデータ構成の一例を示す概念図である。
【図６】第１の実施形態におけるルートノードの処理フローチャートである。
【図７】第１の実施形態におけるルートノード以外のノードの処理フローチャートである。
【図８】第２の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。
【発明を実施するための形態】
【００２６】
本発明の実施形態の概要について説明する。本発明の一実施形態によるマルチキャストシステムは、図１に一例を示すように複数のノードを有するマルチチャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量（図１の各ノードＩＤの３項目）を、追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段（たとえば、図４の２１２）と、算出した予測遅延量を記憶する手段（図４の２２１、図３の１２１）と、を備える。さらに、追加ノードを設ける際に上記予測遅延量を用いて、追加ノードを接続するノードを決定する手段（図３の１１３）を備える。
【００２７】
上記実施形態によれば、マルチキャストツリーに変更を加える前に各ノードの配下に追加ノードを新たに接続した場合の予測遅延量をノード毎にあらかじめ算出しておくので、マルチキャストツリーの変更が実際に必要になった場合に迅速に最適なマルチキャストツリーの変更を実施できる。従って、データ配信の途中で中間のノードの一部が脱落するような状況が発生しても、遅延量を所定の遅延値以下に収めて迅速にマルチキャストツリーの再構築を行うことができる。
【００２８】
また、本発明の別の実施形態によるマルチキャストシステムは、図８に一例を示すようにルートノード（図２の１００）から複数のノード（図２の２００を２００Ａと読み替え）がツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、ルートノード１００から各ノード２００Ａまでの遅延量を算出する手段（図８の２１２）と、基準とする遅延量と算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段２３１と、各ノードへのデータ到着時に算出した意図的な遅延量を挿入する手段２３２と、を備える。
【００２９】
上記別の実施形態によるマルチキャストシステムによれば、各ノードの遅延量を精度よく揃えることができる。
【００３０】
なお、上記実施形態の概要に付記した図面参照符号は専ら理解を助けるための例示であり、図示の態様に限定することを意図するものではない。以上で概要についての説明を終え、以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。
【００３１】
［第１の実施形態］
図２は、マルチキャストシステムにおけるマルチキャストツリーの構成例を示す概念図である。図２において、マルチキャストツリー１は、ルートノード１００と複数のノード２００によって論理ネットワークを構成している。ルートノード１００は、少なくとも一つのノード２００に接続され、そのノード２００は、ツリーの末端となるノード２００を除いて少なくとも一つの別のノード２００に接続されている。ルートノード１００、ノード２００から複数のノード２００に枝分かれして接続されることによって、ルートノード１００を頂点とするネットがツリー状に広がり、ルートノード１００から発信する情報がツリー状に多数のノード２００に伝えられることになる。
【００３２】
ノード２００は、ルートノード１００、もしくは１つまたは複数のノード２００と接続する。各ノード２００は、接続しているルートノード１００、もしくはノード２００からデータを受信した場合に、マルチキャストツリー１での下流にあるノード２００にデータを転送する。
【００３３】
図１は、実施形態１の概念を示す図面であり、図１（ａ）は、再構成前のマルチキャストツリーの構成を示す概念図であり、図１（ｂ）再構成後のマルチキャストツリーの構成を示す概念図である。図１のマルチキャストツリー１において、配信遅延を指定した値以下に収めるため、ノードを移動させることによってマルチキャストツリーの構成を変更する構成例を示している。図１（ａ）がノード移動前、図１（ｂ）がノード移動後である。
【００３４】
図１において、ルートノード１００、ノード２００にそれぞれコロンで区切って付している３つの符号は、左端の一つ目の符号は、各ノードのノードＩＤを示している。また、中央の二つ目の符号は、ルートノード１００（ノードＩＤ：ｎ２）から自己のノードまでの配信遅延量である。この遅延量は推定遅延量であってもよいし、実測値が得られていれば実測値であってもよい。さらに、右端の三つ目の符号は、自己のノードに新たなノードを直接接続して追加すると仮定した場合の配信遅延の予測値である。この予測値は、ルートノードから追加ノードまでの予測遅延量を表している。この予測遅延量は、新規にマルチキャストツリーに接続するノードが接続先を選択する場合の目安とする数値である。
【００３５】
あるノードｉの（推定）遅延量をＤ＿ｉ、１世代下のｊ番目のノードへデータを配信するための処理遅延量をＤＰ＿ｉｊ、上記ノードｉとその１世代下のｊ番目のノード間のネットワーク遅延をＤＮ＿ｉｊとすると、ノードｉの１世代下のｊ番目のノードの推定遅延量Ｄ＿ｉｊは、式１で表すことができる。
【００３６】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ＿ｉｊ＋ＤＮ＿ｉｊ （式１）
【００３７】
ここで、Ｐ＿ｉ０を、ノードｉがノードｉの親ノードからパケットを受信してから配下１番目の１世代下のノードへデータを送信するまでのノード内転送処理遅延、Ｐ＿ｉｊをノードｉにおける配下ｊ番目の１世代下のノードへデータを送信してから配下ｊ＋１番目の１世代下のノードへデータを送信するまでのノード内転送処理遅延とすると、１世代下のｊ番目のノードへデータを配信するための処理遅延量ＤＰ＿ｉｊは、
ＤＰ＿ｉｊ＝ＤＰ＿ｉ（ｊ−１）＋Ｐ＿ｉ（ｊ−１）
ＤＰ＿ｉ１＝Ｐ＿ｉ０
と書ける。
【００３８】
このとき、ノードｉにおける配下ノード間、および配下ノードへのデータ送信処理に差分がないとすると式１は簡略化することができる。具体的には、Ｐ＿ｉ０＝Ｐ＿ｉ１＝Ｐ＿ｉ２＝Ｐ＿ｉ３…、かつＤＮ＿ｉ１＝ＤＮ＿ｉ２＝ＤＮ＿ｉ３＝ＤＮ＿ｉ４…と仮定出来る時、式１は、式２のように簡略化できる。
【００３９】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ＿ｉ×ｊ＋ＤＮ＿ｉ （式２）
【００４０】
ここでＤＰ＿ｉは、ノードｉにおける１回のデータ転送に掛かる処理遅延である。また、ＤＮ＿ｉはノードｉにおける１世代下のノードへのネットワーク遅延である。この値は、例えば、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）、代表的な配下のノードまたは１世代上のノードの値、から静的または動的に算出する。なお、「処理遅延」とは、ノード内部の遅延であり、「配信遅延」とは、ノード間を接続するネットワークの遅延である。すなわち、各ノードの実際の処理遅延、各ノード間の実際の配信遅延、各ノードの実際の処理能力を用いて算出する。「ノード処理能力」は、マシンの性能であるため、固定であるが、「処理遅延」はマシン内の処理状況により変化し、「配信遅延」はネットワークの状況により変化する。この変化するパラメータについて、たとえば平均値を用いて静的に算出してもよいし、一定時間の移動平均を用いて動的に算出してもよい。
【００４１】
さらに、マルチキャストツリーに参加するどのノードにおいても、ＤＰ＿１＝ＤＰ＿２＝…＝ＤＰ、かつＤＮ＿１＝ＤＮ＿２＝…＝ＤＮと仮定できる場合、式２をさらに簡略化して式３とすることができる。
【００４２】
Ｄ＿ｉｊ＝Ｄ＿ｉ＋ＤＰ×ｊ＋ＤＮ （式３）
【００４３】
ここで、ＤＰは、１回のデータ転送に掛かる処理遅延である。また、ＤＮは１世代下のノードへのネットワーク遅延である。この値は、例えば、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）、任意のノードの値、から静的または動的に算出する。
【００４４】
図１の例ではルートノードｎ２の推定遅延量を０として、式３を適用し、かつＤＰ＝ＤＮ＝１とした場合を示している。例えば、ルートノードｎ２の遅延量は０、配下１番目のノードｎ８の遅延量は２となり、ルートノードｎ２がノードｎ８に続いてデータを転送するノードｎ１１の遅延量は３となる。
【００４５】
また、具体的には、新たに接続するノードの予測遅延量とは、そのノードに新たにノードが接続してきた場合の、その新規に接続してきたノードの推定遅延量と定義する。新規に接続するノードや、接続先を変更するノードにとって、新たに接続するノードの（推定）遅延量が小さいノードに接続した方が、より配信遅延が小さいことになる。新たに接続するノードの予測遅延量を式で表現する場合、新たに接続するノードがノードｉのｎ番目の子供（配下に直接接続されるノード）になるとして、あるノードｉの（推定）遅延量をＤ＿ｉ、ノードｉの新たに接続するノードの予測遅延量をＤ＿ｉｎ、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の予測値をＤＰ＿ｉｎ、新規ノードが接続した場合のネットワーク遅延の予測値をＤＮ＿ｉｎとすると、式４が成立する。
【００４６】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ＿ｉｎ＋ＤＮ＿ｉｎ （式４）
【００４７】
ここで、式１から式２の導出と同様に、ノードｉにおける配下ノード間、および配下ノードへのデータ送信処理に差分がないとすると、式４は簡略化することができる。具体的には、Ｐ＿ｉ０＝Ｐ＿ｉ１＝Ｐ＿ｉ２＝Ｐ＿ｉ３…、かつＤＮ＿ｉ１＝ＤＮ＿ｉ２＝ＤＮ＿ｉ３＝ＤＮ＿ｉ４…と仮定出来る時、式４は、式５のように簡略化できる。
【００４８】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ＿ｉ×ｎ＋ＤＮ＿ｉ （式５）
【００４９】
さらに、式２から式３の導出と同様に、マルチキャストツリーに参加するどのノードにおいても、ＤＰ＿１＝ＤＰ＿２＝…＝ＤＰ、かつＤＮ＿１＝ＤＮ＿２＝…＝ＤＮと仮定できる場合、式５をさらに簡略化して式６とすることができる。
【００５０】
Ｄ＿ｉｎ＝Ｄ＿ｉ＋ＤＰ×（ｃ＋１）＋ＤＮ （式６）
【００５１】
また、上記式１から式６において、Ｄ＿ｉをノードｉの推定遅延量としたが、実測した遅延量が分かる場合はＤ＿ｉに実測した遅延量を用いても良い。
【００５２】
図１の例では、ルートノードｎ２の推定遅延量を０として、式３および式６を適用し、かつＤＰ＝ＤＮ＝１とした場合の、推定遅延量を所定の遅延量８以内に収めるための構成例を示している。具体的には図１（ａ）ではノードｎ９の遅延量は９、ノードｎ１５の遅延量は１０であり、所定の遅延量８より大きい。従って、ノードの組み換えが要求される。また、図１（ａ）において、自己のノードの配下に追加ノードを新たに設けたときの予測遅延量が所定の遅延量８より小さいノードが存在する（ノードｎ２、ｎ８、ｎ１１、ｎ２２の予測遅延量は、それぞれ、０、６、６、７）。従って、ノードｎ９、ｎ１５を上記予測遅延量が８より小さいノードｎ２、ｎ８、ｎ１１、ｎ２２のいずかに接続を変更することにより、全ノードの遅延量を所定の遅延量８以内に収める可能性があると考えられる。図１（ｂ）では、ノードｎ９をノードｎ１１の配下に、ノードｎ１５をルートノードｎ２の配下に移動させている。
【００５３】
この結果、ルートノードｎ２の新たに接続する追加ノードの予測遅延量が４から５に、ノードｎ１１の新たに接続する追加ノードの予測遅延量が６から７に、ノードｎ１５の推定遅延量および新たに接続する追加ノードの予測遅延量がそれぞれ１０から４および１２から６に、ノードｎ９の推定遅延量および新たに接続するノードの予測遅延量がそれぞれ９から６および１１から８に、更新され、全てのノードの（推定）遅延量が指定された所定の遅延量８を超えない構成となる。なお、ノードｎ２３の配下に接続されるノードがなくなったため、ノードｎ２３の追加ノードの予測遅延量も、１１から９に更新されている。このように、配信遅延が指定した値以下に納まらないノードを、追加ノードの予測遅延量を基準に配信遅延が指定した値以下に納まるノードへ接続先を変更させ、マルチキャストツリーを再構成することにより、マルチキャストツリーにおいて配信遅延を指定した値以下に収めることができる。
【００５４】
次に、上記図１を用いて説明した実施形態１のマルチキャストツリーの変更を行うマルチキャストシステムのノード２００及びルートノードの構成について説明する。
【００５５】
図４は、図１、図２におけるルートノード１００以外のノードの内部構成を示すブロック図である。図４において、ノード２００は、主制御部２１０とネットワークインターフェイス２２０と、ノード情報データベース２２１と、を有する。ネットワークインターフェイス２２０は、ネットを介してルートノード１００又は他のノード２００と接続されている。
【００５６】
主制御部２１０は、ＣＰＵ、ＲＡＭ、及びＯＳなどで構成されたコンピュータの主要部であり、主制御部２１０の中に、動作するプログラムとして構成されている送受信部２１１と、推定遅延量計算機能部２１２と、を有する。
【００５７】
図５は、図２におけるノード情報データベース２２１の内部データ構成の一例を示す概念図である。データの一例として図２におけるノードｎ３のノード情報データベース２２１を例示している。ノード情報データベース２２１は、マルチキャストツリー１におけるノード情報を保存する。ノード情報とは、ノード２００を一意に識別するノードＩＤ、ＩＰアドレス、ポート番号など他のノード２００とメッセージを送受信するために必要な情報であり、マルチキャストツリー１のツリー構造において自ノードより上及び下にあるノード２００の情報である。また、ノード情報データベース２２１には各ノードの（推定）遅延量および新たに接続する追加ノードの予測遅延量も保存される。
【００５８】
推定遅延量計算機能部２１２は、マルチキャストツリーにおいて、配下に接続しているノード２００の（推定）遅延量と自ノードの新たに接続する追加ノードの予測遅延量を計算する。配下に接続しているノード２００の（推定）遅延量の計算は、式１または式２を用いる。また、新たに接続する追加ノードの予測遅延量の計算は、式４または式５を用いる。ただし、新たに接続されると仮定している追加ノードは、まだ特定されていないのでで、ネットワーク遅延の推定値ＤＮ＿ｉｎは仮想的な値である。計算結果は、ノード情報データベース２２１に保存し、配下に接続しているノード２００の推定遅延量は、該当する配下のノード２００に通知する。
【００５９】
推定遅延量計算機能部２１２における、（推定）遅延量と新たに接続する追加ノードの予測遅延量の計算は、ルートノード１００からの（推定）遅延量と新たに接続するノードの予測推定遅延量収集の要求が来た場合、配下のノード２００に増減などの変化があった場合、ノード２００のオペレータからの指示があった場合などに実施される。
【００６０】
図３は、第１の実施形態によるマルチキャストシステムに用いられるルートノード１００の内部構成を示すブロック図である。図３において、ルートノード１００は、主制御部１１０とネットワークインターフェイス１２０と、ノード情報データベース１２１と、を有する。主制御部１１０は、ＣＰＵ、ＲＡＭ、及びＯＳなどで構成されたコンピュータの主要部である。ルートノード１００は、主制御部１１０の中に、動作するプログラムとして構成されている送受信部１１１と、推定遅延量収集機能部１１２と、トポロジ決定機能部１１３と、を有する。
【００６１】
ノード情報データベース１２１は、図５を用いてすでに説明したノード２００のノード情報データベース２２１に相当するデータベースである。ただし、ルートノード１００のノード情報データベース１２１の場合は、推定遅延量収集機能部１１２が各ノードから収集した各ノードのノード情報と（推定）遅延量および各ノードに新たに追加ノードが接続された場合の予測遅延量も保存される。
【００６２】
送受信部１１１は、ネットワークインターフェイス１２０を介して、ノード２００からのメッセージを受信して、メッセージ種別を見た上で、推定遅延量収集機能部１１２またはトポロジ決定機能部１１３に送る。
【００６３】
また、送受信部１１１は、推定遅延量収集機能部１１２またはトポロジ決定機能部１１３からメッセージを受け取り、メッセージに記載されている宛先であるノード２００にネットワークインターフェイス１２０を介してメッセージを送信する。
【００６４】
推定遅延量収集機能部１１２は、マルチキャストツリー１に参加するノードから、それぞれの（推定）遅延量および新たに接続する追加ノードの予測遅延量を収集し、ノード情報データベース１２１を更新する。（推定）遅延量および新たに接続するノードの予測遅延量の収集方法としては、例えば、ルートノード１００から配下のノード２００に対し、推定遅延量および新たに接続する追加ノードの予測遅延量を要求するメッセージを送信し、推定遅延量および新たに接続する追加ノードの予測遅延量を要求するメッセージを受信したノード２００は、さらに配下のノード２００にメッセージを転送し、マルチキャストツリー１のリーフの位置のノード２００から（推定）遅延量および新たに接続するノードの予測遅延量を、逆順で返信していく方法がある。あるいはルートノード１００がマルチキャストツリー１に接続しているノード２００とそれぞれ直接通信して（推定）遅延量および新たに接続するノードの予測遅延量を収集してもよい。また、実測した遅延量が分かる場合は推定遅延量に代わりに実測した遅延量を用いても良い。
【００６５】
トポロジ決定機能部１１３は、ノード情報データベース１２１を参照し、マルチキャストツリー１に参加しているノード２００の（推定）遅延量および新たに接続するノードの予測遅延量を参照する。次に、指定された遅延量より大きい（推定）遅延量のノード２００を抽出する。ここで抽出されたノード群をノード群Ａとする。また、指定された遅延量より小さい新たに接続するノードの予測遅延量を有するノード２００を抽出する。ここで抽出されたノード群をノード群Ｂとする。すなわち、ノード群Ａのノードは、そのノードの現在の（推定）遅延量が指定された基準となる遅延量より大きいノードであり、ノード群Ｂのノードは、新たに配下にノードを追加した場合の予測遅延量が指定された基準となる遅延量より小さい遅延量を有するノードである。
【００６６】
このとき、ノード群Ａの中に、ひとつ以上のノード２００が含まれていた場合、ノード群Ａをノード群Ｂの配下に接続させる。
【００６７】
ノード群Ａのどのノード２００をノード群Ｂのどのノード２００の配下に接続するかは、例えば、予測遅延量の大きいノード順に、新たに接続するノードの推定遅延量が小さいノードへ接続させることができる。また、マルチキャストツリー１上の位置がなるべく変わらない位置になるノードの配下に接続させることでもよい。それ以外の方法でもよいが、遅延量の大きなノードをそのノードの現在の遅延量より予測遅延量が小さいノードに接続をつなぎ変えることにより、遅延量の最大値を小さくすることができる。また、タイムスタンプを利用するなどによって、実測した遅延量が分かる場合はノード群Ａを抽出する際に推定遅延量に替わりに実測した遅延量を用いても良い。
【００６８】
トポロジ決定機能部１１３は、ノードの移動先を決定したのち、移動させるノード２００に対し、移動のメッセージを送信する。
【００６９】
ここで、配信遅延時間の指定はマルチキャストツリーのオペレータにより静的または動的に設定される。マルチキャストツリー１に参加するノード２００の数により配信遅延時間の指定には下限がある。下限よりもさらに小さい値を指定する場合、ノード群Ａのノードの数の方がノード群Ｂのノードの数よりも大きくなり、配信遅延が指定した値以下にならないノード２００が存在してしまう。このとき、前記ノードに対し、アラームを通知する、または強制的にマルチキャストツリー１から離脱させる、などの方法をとる。
【００７０】
また、トポロジ決定機能部１１３は、新規にマルチキャストツリーに参加するノード２００に対し、すでにマルチキャストツリーに参加しているノード２００の新たに接続する追加ノードの予測遅延量の情報を提供する。新規にマルチキャストツリーに参加するノード２００は、入手した新たに接続するノードの予測遅延量の情報から指定されている配信遅延時間を超えない接続先となるノード２００を選出し、接続することでマルチキャストツリーに参加する。このとき、指定されている配信遅延時間を超えない接続先が存在しない場合、アラームを上げた上で接続する、または接続を断念する、などの方法を取る。
【００７１】
推定遅延量収集機能部１１２における、（推定）遅延量と新たに接続するノードの予測遅延量の収集、および、トポロジ決定機能部１１３におけるトポロジ決定とノードの移動は、マルチキャストツリー１に接続するノード２００に増減などの変化があった場合、ルートノード１００のオペレータからの指示があった場合などに実施される。
【００７２】
次に、第１の実施形態の動作について、特に特徴的な部分について説明する。
【００７３】
図６は、本実施形態におけるルートノード１００において、マルチキャストツリー１における配信遅延を一定値以内に収めるようトポロジを変更する場合の動作を示すフローチャートである。動作を開始すると、まず送受信部１１１が他のノード２００、もしくはルートノード１００内の主制御部１１０からの通信を待つ状態（以後、アイドル状態という）となる（ステップＳ３００）。
【００７４】
ルートノード１００は、アイドル状態中に（ステップＳ３００）、マルチキャストツリー１に接続するノード２００に増減などの変化があった場合または、ルートノード１００のオペレータからの指示があった場合などに、マルチキャストツリー１に参加するノード２００から（推定）遅延量と新たに接続するノードの予測遅延量を収集し（ステップＳ３０１）、ノード情報データベース１２１を更新する（ステップＳ３０２）。
【００７５】
続いて、ノード情報データベース１２１を参照し、指定された遅延量より（推定）遅延量が大きいノード２００を抽出する（ステップＳ３０３）。さらに、ノード情報データベース１２１を参照し、指定された遅延量より追加ノードの予測遅延量が小さいノード２００を抽出する（ステップＳ３０４）。さらに、ステップＳ３０３で抽出したノードをステップＳ３０４で抽出したノードへ接続させる（ステップＳ３０５）。次に、ステップＳ３０３で抽出したノードの数とステップＳ３０４で抽出したノードの数を比較し（ステップＳ３０６）、ステップＳ３０４で抽出したノードの数の方が大きい場合は、ステップＳ３００のアイドル状態に戻る。ステップＳ３０３で抽出したノードの数の方が大きい場合は（ステップＳ３０６の下への遷移）、移動できなかったノード２００に対しアラームを送信し（ステップＳ３０７）、アイドル状態に戻る。
【００７６】
なお、図６で説明したフローチャートに係る各ステップの動作内容は、ルートノード１００が予め備えるコンピュータ（主制御部）で動作するプログラムとして実行させるように構成することができる。
【００７７】
上述した説明では、すでに存在するマルチキャストツリー１の再構成について説明したが、新たなノードが、新規にマルチキャストツリー１に参加する場合において、すでにマルチキャストツリー１を構成しているどのノード２００に接続するかを決定する時に、新たに接続するノードの予測遅延量をマルチキャストツリー１に参加している各ノード２００から収集し、追加ノードの予測遅延量を基準として、追加ノードの予測遅延量が小さいノードに接続することによって、マルチキャストツリー１の配信遅延を指定した値以下に収めるようにすることもできる。このとき、マルチキャストツリー１の配信遅延を指定した値以下に収めることができるような接続先がない場合、新規参加を拒否する、またはアラームを通知した上で参加を許可する、ということもできる。
【００７８】
図７は、第１の実施形態におけるルートノード以外のノード２００の処理フローチャートである。動作を開始すると、まず送受信部２１１が他のノード２００、もしくはルートノード１００内の主制御部１１０からの通信を待つ状態（以後、アイドル状態という）となる（ステップＳ４００）。ルートノードからの指示により、当該ノードの接続が変わる場合（ステップＳ４０１でＹｅｓ）は、ノード情報データベース２２１のトポロジ情報を更新する（ステップＳ４０２）。また、ステップＳ４０２ではタイムスタンプ等を利用して遅延値の実測値が得られたら、推定遅延値を実測値に置き換えてもよい。
【００７９】
ステップＳ４０３では、ルートノード１００や当該ノードとルートノードとの間に介在するノード（親ノード）からノード情報データベース２２１の照会があった場合（ステップＳ４０３でＹｅｓ）は、当該照会の内容に応答して最新のノード情報データベース２２１の内容を問い合わせ先に回答し（ステップＳ４０４）、その後、ステップＳ４００のｉｄｌｅ状態に戻る。一方、ノード情報データベース２２１の照会がなかった場合（ステップＳ４０３でＮｏの場合）は、何もせず、ステップＳ４００のｉｄｌｅ状態に戻る。
【００８０】
また、上述した説明では、ルートノード１００がマルチキャストツリー１に参加するノード２００から、（推定）遅延量と新たに接続するノードの予測遅延量を収集し、マルチキャストツリー１のトポロジを決定するとしたが、この機能はルートノード１００が持たなくてもよい。すなわちあるノード２００でもよいし、第３のコンピュータでもよい。この場合、ルートノード１００もノード２００と同様のノードとして動作する。
【００８１】
［第２の実施形態］
次に、本発明の第２の実施形態を、図面を参照して説明する。
【００８２】
本発明の第２の実施形態では、ある指定した推定遅延量を基準に、データ到着時に遅延を挿入することにより、マルチキャストツリーに参加するノード間における、配信遅延のばらつきを小さくすることができる。
【００８３】
図１（ａ）を例として、第２の実施形態の概念から説明する。図１（ａ）において、ノードｎ８の（推定）遅延量は２、ノードｎ２２の（推定）遅延量は５である。このとき、ノードｎ８において（推定）遅延量３の分だけデータ受信時にノード内部で遅延させると推定遅延量５相当となり、ノードｎ８とノードｎ２２の間の配信遅延の差が小さくなる。
【００８４】
さらに、遅延量１０を基準とすると、ノードｎ８は遅延量８の遅延、ノードｎ２２は遅延量５の遅延、ノードｎ１１は遅延量７の遅延というように、自ノードの遅延量と基準遅延量の差分だけ、データ受信時にノード内部で遅延させると、データ受信の配信遅延が、全てのノードでほぼ等しくなる。なお、配下に他のノードが接続されているノードは、配下に転送するデータに関しては、遅延を挿入せずに、データ到着時、速やかに配下のノードに転送する。たとえば、ノードｎ８はノードｎ３とノードｎ４４、ノードｎ１１はノードｎ２２にデータ転送を行うが、この他のノードへ転送するデータには、遅延を挿入しない。この様な処理を行うことにより、配信先の末端での配信遅延のばらつきを小さくすることができる。式で表現すると、ノードｉの遅延量をＤ＿ｉ、基準とする遅延量をＤＢ、意図的に挿入する遅延量をΔＤ＿ｉとすると、式７が成立する。
【００８５】
ΔＤ＿ｉ＝ＤＢ−Ｄ＿ｉ （式７）
【００８６】
このとき基準とする遅延量は、マルチキャストツリー１に参加するノード２００の中で最大の遅延量と同じか、大きくする必要がある。この基準とする遅延量を決定するには、マルチキャストツリー１に参加するノード２００の中で最大の遅延量が分かればよい。マルチキャストツリー１に参加するノード２００の中で最大の遅延量は、トポロジを決定する過程で得られる。ただし、全ノードの（実測または推定の）遅延量の情報を得ることが困難な場合、例えばマルチキャストツリーに参加するノード２００の数が膨大である場合、マルチキャストツリー１に参加するノード２００の中で最大の遅延量を推定する。その方法は例えば、マルチキャストツリーに参加するノード２００の数から推定する、マルチキャストツリーの最下層のあるノードの推定遅延量から推定する、などがある。
【００８７】
また、データ到着時に挿入する遅延量は少ない方が好ましいため、前述の意図的に挿入する遅延量を求める前に、本発明の第１の実施形態の手段を用いて、予めマルチキャストツリー１に参加するノード２００の中で最大の推定遅延量を小さくしておくとよい。具体的には、基準とする推定遅延量を下限に設定し、マルチキャストツリー１のトポロジを変更しておくことで、マルチキャストツリー１に参加するノード２００の中で最大の推定遅延量を小さくできる。
【００８８】
また、基準とする遅延量の周知は、例えば初回のデータとして送付することで周知させることができる。基準とする遅延量をマルチキャストツリーに参加するノードに周知させておくことにより、最大遅延量または最大遅延量よりも大きな値を基準値として事前に与えておき、それを基準に意図的に挿入する遅延量ΔＤ＿ｉを算出することができる。
【００８９】
図８は、第２の実施形態によるマルチキャストシステムに用いられるルートノード以外のノードの内部構成を示すブロック図である。図８のノード２００Ａは、第１の実施形態のノード２００に置き換えて用いる。図８のノード２００Ａについて、図４を用いて説明した第１の実施形態のノード２００と異なる構成について説明する。第１の実施形態のノード２００と構成が同一である部分については、同一の符号を付し、重複する説明は省略する。
【００９０】
挿入遅延量算出部２３１は、ルートノード１００から基準とする遅延量の指定を受けて、ノード情報データベースに含まれる自ノードの（推定）遅延量に基づいて、データ受信時に挿入する遅延量を算出する。
【００９１】
遅延挿入部２３２は、ルートノード１００からデータの配信を受ける際に、送受信部に受信したデータを挿入遅延量算出部２３１が算出した挿入遅延量に基づいて、遅延させる。
【００９２】
また、ルートノード１００は、初回のデータ配信において、基準となる遅延量を各ノード２００Ａに対して送信することを除いて、第１の実施形態のルートノード１００をそのまま用いることができる。
【００９３】
上述した説明では、マルチキャストツリー１全体でひとつの基準とする推定遅延量を周知させることにより、配信遅延のばらつきを小さくすることができるとしたが、マルチキャストツリー１に参加するノードを複数のグループに分割し、そのグループそれぞれで基準とする推定遅延量を設定し、グループ内の基準とする推定遅延量から意図的に挿入する遅延量ΔＤ＿ｉを算出し、データ到着時に遅延を挿入することにより、グループ内のノード間における、配信遅延のばらつきを小さくすることができる。
【００９４】
また、上述した説明では、マルチキャストツリー１全体で基準とする推定遅延量を周知させることにより、配信遅延のばらつきを小さくすることができるとしたが、推定遅延量が同じまたは近いノード２００をグループ化することで、グループ内の配送遅延のばらつきを小さくすることも出来る。
【００９５】
図１（ａ）を例とすると、ノードｎ４４と、ノードｎ２２は何れも推定遅延量５である。これらのノードをグループとすると、グループ内では推定遅延量が同値であるため、グループ内の配送遅延のばらつきを小さくすることが出来る。
【００９６】
以上説明したように、推定遅延量をノード内転送処理遅延と転送リンクのネットワーク遅延の総和から算出し、推定遅延量および新たに接続するノードの推定遅延量を基準に、配信遅延が指定した値以下に納まらないと推定されるノードを、配信遅延が指定した値以下に納まるように、マルチキャストサービス開始より前に移動させ、マルチキャストツリーを再構成することにより、マルチキャストツリーに参加するノードの配信遅延を指定した値以下に収めることができる。
【００９７】
また、以上説明したように、推定遅延量をノード内転送処理遅延と転送リンクのネットワーク遅延の総和から算出し、推定遅延量および新たに接続するノードの推定遅延量を基準に、データ到着時に遅延を挿入することにより、マルチキャストツリーに参加するノード間における、配信遅延のばらつきを小さくすることができる。
【００９８】
なお、本発明において下記の形態が可能である。
［形態１］
前記第１の視点に記載のマルチキャストシステムのとおり。
［形態２］
前記追加ノードを接続するノードを決定する手段は、前記予測遅延量が所定の遅延値以下であるノードに前記追加ノードを接続し、
前記予測遅延量が所定の遅延量以下となるノードが存在しない場合は、前記追加ノードを含めた前記複数のノードの遅延量がいずれも前記所定の遅延量以下となるように、前記マルチキャストツリーを組み替えることが好ましい。
［形態３］
前記各ノードは、それぞれ、
自己ノードの下流に追加ノードを接続すると仮定した場合の予測遅延量を算出する手段と、
前記算出した予測遅延量を記憶する手段と、を備え、
前記マルチキャストシステムは、前記各ノードが算出した前記各ノードの予測遅延量を収集して一括して記憶する手段を備え、
前記ノードを決定する手段は、前記一括して記憶された各ノードの予測遅延量を用いて前記追加ノードを接続するノードを決定することが好ましい。
［形態４］
前記予想遅延量を算出する手段は、前記接続先となり得るノードの処理能力と、ルートノードから当該ノードまでの遅延量と、当該ノードから前記追加ノードまでのネットワーク遅延を平均的であると仮定した仮想ネットワーク遅延量と、に基づいて予想遅延量を算出することが好ましい。
［形態５］
前記第２の視点に記載のマルチキャストシステムのとおり。
［形態６］
前記第３の視点に記載のマルチキャストシステムのノードのとおり。
［形態７］
前記マルチキャストツリー構造がルートノードから前記複数のノードがツリー状に接続されたマルチキャストシステムであって、
前記推定遅延量計算機能部と前記ノード情報記憶部とを備える前記ノードが、前記ルートノード以外の前記ノードであることが好ましい。
［形態８］
前記第４の視点に記載のマルチキャストシステムのルートノードのとおり。
［形態９］
前記第５の視点に記載のマルチキャストシステムのマルチキャストツリー更新方法のとおり。
［形態１０］
前記第６の視点に記載のマルチキャストシステムのコンピュータプログラムのとおり。
［形態１１］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、を有するマルチキャストシステム。
［形態１２］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集する手段と、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成する手段と、を有するマルチキャストシステム。
［形態１３］
マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する手段と、新規にマルチキャストツリーに参加するノードに対し、マルチキャストツリーを構成するノードの配下に新たにノードが接続したと仮定した時の推定遅延量を通知する手段と、前記推定遅延量から、配信遅延が指定した値以下に納まる接続先となるノードを選出する手段と、を有するマルチキャストシステム。
［形態１４］
前記形態１１乃至１３のいずれかに記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、任意のノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１５］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーを構成する全ノードの平均の、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１６］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１７］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、処理遅延と配信遅延が等しいと仮定して、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１８］
前記形態１４に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、あるノードの推定遅延量を算出する際に、マルチキャストツリーを構成する全ノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）で重み付けした平均値を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態１９］
前記形態１１乃至１３のいずれかに記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、任意のノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２０］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーを構成する全ノードの平均の、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、１世代下のノードへデータを配信するための処理遅延量と、前記ノードとその１世代下のノード間のネットワーク遅延を算出し、前記処理遅延量と前記ネットワーク遅延量の累積からあるノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２１］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２２］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーにおいて隣接するノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２３］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、処理遅延と配信遅延が等しいと仮定して、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２４］
前記形態１９に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、そのマルチキャストツリーに参加する前に参加後のノードの推定遅延量を接続先のノードごとに算出する際に、マルチキャストツリーを構成する全ノードの、実際の処理遅延、配信遅延、ノードの処理能力（ＣＰＵ速度、ＣＰＵ利用率）で重み付けした平均値を用いて、新規ノードが接続した場合のそのノードへデータを配信するまでの処理遅延の推定値と、新規ノードが接続した場合のネットワーク遅延の推定値を算出し、前記処理遅延の推定値と前記ネットワーク遅延の推定値の累積から新たに接続するノードが接続する前に新たに接続するノードの推定遅延量を算出するマルチキャストシステムであることが好ましい。
［形態２５］
マルチキャストシステムを構成するノードであって、マルチキャストツリーに参加するノードから、それぞれの推定または実測の遅延量および新たに接続するノードの推定遅延量を収集する手段と、収集した推定または実測の遅延量および新たに接続するノードの推定遅延量から、指定された推定遅延量より大きい推定または実測の遅延量のノードを、指定された推定遅延量より小さい新たに接続するノードの推定遅延量をもつノードの配下に接続させる手段と、マルチキャストツリーに参加するノードの推定または実測の遅延量および新たに接続するノードの推定遅延量を含むノード情報を保持する手段と、を有するノード。
［形態２６］
マルチキャストシステムを構成するノードであって、配下に接続しているノードの推定または実測の遅延量と自ノードの新たに接続するノードの推定遅延量を計算する手段と、自ノードの推定または実測の遅延量および新たに接続するノードの推定遅延量を含むノード情報を保持する手段と、を有するノード。
［形態２７］
マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーを構成するノードの推定遅延量を算出する手段と、基準とする遅延量とノードの推定または実測の遅延量の差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、データ到着時に前記意図的な遅延量を挿入する手段と、を有するマルチキャストシステム。
［形態２８］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、実測遅延量の最悪値とするマルチキャストシステムであることが好ましい。
［形態２９］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、推定遅延量の最大値とするマルチキャストシステムであることが好ましい。
［形態３０］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、データ到着時に意図的に挿入する遅延量を算出する際に、基準とする値を、推定遅延量が大きくなりそうな位置にあるノードの実測値とするマルチキャストシステムであることが好ましい。
［形態３１］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーに参加するノードを複数のグループに分割する手段と、そのグループそれぞれで基準とする推定または実測の遅延量を設定する手段と、グループ内の基準とする推定または実測の遅延量から意図的に挿入する遅延量を算出する手段と、前記遅延量の分だけデータ到着時に遅延を挿入する手段と、を有するマルチキャストシステムであることが好ましい。
［形態３２］
前記形態２７に記載の、マルチキャストツリーから構成されるマルチキャストシステムであって、推定または実測の遅延量が、同じまたは近いノードをグループ化する手段と、を有するマルチキャストシステムであることが好ましい。
［形態３３］
マルチキャストツリーから構成されるマルチキャストシステムであって、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集するステップと、指定された推定または実測の遅延量より大きい遅延量のノードを抽出するステップと、指定された推定または実測の遅延量より小さい新たに接続するノードの推定遅延量のノードを抽出するステップと、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成するステップと、を有するマルチキャスツリー構成方法。
［形態３４］
マルチキャストツリーから構成されるマルチキャストシステムを構成するノードを制御するコンピュータに、マルチキャストツリーを構成するノードから、推定または実測の遅延量およびそのノードの配下に新たにノードが接続したと仮定した時の推定遅延量を収集する機能と、指定された推定または実測の遅延量より大きい遅延量のノードを抽出する機能と、指定された推定または実測の遅延量より小さい新たに接続するノードの推定遅延量のノードを抽出する機能と、配信遅延が指定した値以下に納まらないノードを、推定または実測の遅延量から、配信遅延が指定した値以下に納まるノードの配下に移動させ、マルチキャストツリーを再構成する機能と、を実行させるプログラム。
［形態３５］
基準とする遅延量を指定する手段と、
前記複数のノードのうち、少なくとも一部のノードは、前記基準とする遅延量と自己の遅延量との差分を求める手段と、当該ノードへのデータ到着時に前記差分を埋める遅延量を挿入する手段と、を備える形態１乃至３のいずれかに記載のマルチキャストシステムであることが好ましい。
［形態３６］
前記推定遅延量計算機能部は、前記マルチキャストツリーに含まる他のノードが計算した予測遅延量を収集する機能を含み、
さらに、前記収集した予測遅延量を用いて前記マルチキャストツリーの再構築を行うトポロジ決定機能部をさらに含むことを特徴とする形態６又は７に記載のマルチキャストシステムのノードであることが好ましい。
［形態３７］
前記推定値遅延量収集機能部は、自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部を兼ね備え、
前記推定遅延量収集機能部が集積した前記予測遅延量を含む現在の前記マルチキャストツリー構造のトポロジを記憶するノード情報記憶部をさらに備え、
前記トポロジ決定機能部が、前記ノード情報記憶部に記憶されたマルチキャストツリー全体のノード情報を用いて前記マルチキャストツリー構造の変更を行う形態８に記載のマルチキャストシステムのルートノードであることが好ましい。
［形態３８］
前記各ノードのうち、データ配信の目的地であると共に他のノードへのデータ転送の中継も行うノードにおいて、前記意図的な遅延量を挿入する手段は、前記他のノードへ中継するデータには前記遅延量を挿入せずに、データの受信後、速やかにデータ転送を行う形態５のマルチキャストシステムであることが好ましい。
【００９９】
本発明の全開示（特許請求の範囲及び図面を含む）の枠内において、さらにその基本的技術思想に基づいて、実施例ないし実施例の変更・調整が可能である。また、本発明の特許請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、特許請求の範囲及び図面を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１００】
１：マルチキャストツリー
１００：ルートノード
２００、２００Ａ：ノード
１１０、２１０：主制御部
１２０、２２０：ネットワークインターフェイス
１２１、２２１：ノード情報データベース
１１１、２１１ 送受信部
１１２：推定遅延量収集機能部
１１３：トポロジ決定機能部
２１２：推定遅延量計算機能部
２３１：挿入遅延量算出部
２３２：遅延挿入部
【特許請求の範囲】
【請求項１】
複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、
前記算出した予測遅延量を記憶する手段と、
前記追加ノードを設ける際に前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する手段と、
を備えることを特徴とするマルチキャストシステム。
【請求項２】
前記追加ノードを接続するノードを決定する手段は、前記予測遅延量が所定の遅延値以下であるノードに前記追加ノードを接続し、
前記予測遅延量が所定の遅延量以下となるノードが存在しない場合は、前記追加ノードを含めた前記複数のノードの遅延量がいずれも前記所定の遅延量以下となるように、前記マルチキャストツリーを組み替えることを特徴とする請求項１記載のマルチキャストシステム。
【請求項３】
前記各ノードは、それぞれ、
自己ノードの下流に追加ノードを接続すると仮定した場合の予測遅延量を算出する手段と、
前記算出した予測遅延量を記憶する手段と、を備え、
前記マルチキャストシステムは、前記各ノードが算出した前記各ノードの予測遅延量を収集して一括して記憶する手段を備え、
前記ノードを決定する手段は、前記一括して記憶された各ノードの予測遅延量を用いて前記追加ノードを接続するノードを決定することを特徴とする請求項１又は２記載のマルチキャストシステム。
【請求項４】
前記予想遅延量を算出する手段は、前記接続先となり得るノードの処理能力と、ルートノードから当該ノードまでの遅延量と、当該ノードから前記追加ノードまでのネットワーク遅延を平均的であると仮定した仮想ネットワーク遅延量と、に基づいて予想遅延量を算出することを特徴とする請求項１乃至３いずれか１項記載のマルチキャストシステム。
【請求項５】
ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、
前記ルートノードから各ノードまでの遅延量を算出する手段と、
基準とする遅延量と前記算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、
前記各ノードへのデータ到着時に前記算出した意図的な遅延量を挿入する手段と、
を備えることを特徴とするマルチキャストシステム。
【請求項６】
複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるノードであって、
自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部と、
前記算出した予測遅延量を記憶するノード情報記憶部と、
を備えることを特徴とするマルチキャストシステムのノード。
【請求項７】
前記マルチキャストツリー構造がルートノードから前記複数のノードがツリー状に接続されたマルチキャストシステムであって、
前記推定遅延量計算機能部と前記ノード情報記憶部とを備える前記ノードが、前記ルートノード以外の前記ノードであることを特徴とする請求項６記載のマルチキャストシステムのノード。
【請求項８】
複数のノードがルートノードからツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるルートノードであって、
前記ツリー状に接続された前記各ノードから自己のノードの配下に新たにノードを追加したと仮定してあらかじめ計算された予測遅延量を収集する推定遅延量収集機能部と、
前記収集された予測遅延量を用いて前記マルチキャストツリー構造の変更を行うトポロジ決定機能部と、
を備えることを特徴とするマルチキャストシステムのルートノード。
【請求項９】
複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておくステップと、
前記追加ノードを設ける必要が生じたときに、前記あらかじめ算出しておいた予測遅延量を用いて、前記追加ノードを接続するノードを決定するステップと、
前記決定に基づいて、追加ノードをマルチキャストツリーに組み込んでデータ配信を行うステップと、
を備えることを特徴とするマルチキャストシステムのマルチキャストツリー更新方法。
【請求項１０】
複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて用いられるコンピュータプログラムであって、
前記複数のノードのいずれかに新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出し、記憶手段に記憶させる処理と、
前記追加ノードを設ける必要が生じたときに、前記記憶手段に記憶された前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する処理と、
を前記マルチキャストシステムに含まれる少なくとも一つのコンピュータに実行させることを特徴とするマルチキャストシステムのコンピュータプログラム。
【請求項１】
複数のノードを有するマルチキャストツリーにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておく手段と、
前記算出した予測遅延量を記憶する手段と、
前記追加ノードを設ける際に前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する手段と、
を備えることを特徴とするマルチキャストシステム。
【請求項２】
前記追加ノードを接続するノードを決定する手段は、前記予測遅延量が所定の遅延値以下であるノードに前記追加ノードを接続し、
前記予測遅延量が所定の遅延量以下となるノードが存在しない場合は、前記追加ノードを含めた前記複数のノードの遅延量がいずれも前記所定の遅延量以下となるように、前記マルチキャストツリーを組み替えることを特徴とする請求項１記載のマルチキャストシステム。
【請求項３】
前記各ノードは、それぞれ、
自己ノードの下流に追加ノードを接続すると仮定した場合の予測遅延量を算出する手段と、
前記算出した予測遅延量を記憶する手段と、を備え、
前記マルチキャストシステムは、前記各ノードが算出した前記各ノードの予測遅延量を収集して一括して記憶する手段を備え、
前記ノードを決定する手段は、前記一括して記憶された各ノードの予測遅延量を用いて前記追加ノードを接続するノードを決定することを特徴とする請求項１又は２記載のマルチキャストシステム。
【請求項４】
前記予想遅延量を算出する手段は、前記接続先となり得るノードの処理能力と、ルートノードから当該ノードまでの遅延量と、当該ノードから前記追加ノードまでのネットワーク遅延を平均的であると仮定した仮想ネットワーク遅延量と、に基づいて予想遅延量を算出することを特徴とする請求項１乃至３いずれか１項記載のマルチキャストシステム。
【請求項５】
ルートノードから複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムであって、
前記ルートノードから各ノードまでの遅延量を算出する手段と、
基準とする遅延量と前記算出した各ノードの遅延量との差分から、データ到着時に意図的に挿入する遅延量を算出する手段と、
前記各ノードへのデータ到着時に前記算出した意図的な遅延量を挿入する手段と、
を備えることを特徴とするマルチキャストシステム。
【請求項６】
複数のノードがツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるノードであって、
自己のノードの配下に新たにノードを追加したと仮定した場合の予測遅延量をあらかじめ算出しておく推定遅延量計算機能部と、
前記算出した予測遅延量を記憶するノード情報記憶部と、
を備えることを特徴とするマルチキャストシステムのノード。
【請求項７】
前記マルチキャストツリー構造がルートノードから前記複数のノードがツリー状に接続されたマルチキャストシステムであって、
前記推定遅延量計算機能部と前記ノード情報記憶部とを備える前記ノードが、前記ルートノード以外の前記ノードであることを特徴とする請求項６記載のマルチキャストシステムのノード。
【請求項８】
複数のノードがルートノードからツリー状に接続されたマルチキャストツリー構造を有するマルチキャストシステムに用いられるルートノードであって、
前記ツリー状に接続された前記各ノードから自己のノードの配下に新たにノードを追加したと仮定してあらかじめ計算された予測遅延量を収集する推定遅延量収集機能部と、
前記収集された予測遅延量を用いて前記マルチキャストツリー構造の変更を行うトポロジ決定機能部と、
を備えることを特徴とするマルチキャストシステムのルートノード。
【請求項９】
複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて、新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出しておくステップと、
前記追加ノードを設ける必要が生じたときに、前記あらかじめ算出しておいた予測遅延量を用いて、前記追加ノードを接続するノードを決定するステップと、
前記決定に基づいて、追加ノードをマルチキャストツリーに組み込んでデータ配信を行うステップと、
を備えることを特徴とするマルチキャストシステムのマルチキャストツリー更新方法。
【請求項１０】
複数のノードがツリー状に接続されたマルチキャストツリーを有するマルチキャストシステムにおいて用いられるコンピュータプログラムであって、
前記複数のノードのいずれかに新たに追加ノードを接続すると仮定したときの予測遅延量を、前記追加ノードを設ける前に、接続先となり得るノード毎にあらかじめ算出し、記憶手段に記憶させる処理と、
前記追加ノードを設ける必要が生じたときに、前記記憶手段に記憶された前記予測遅延量を用いて、前記追加ノードを接続するノードを決定する処理と、
を前記マルチキャストシステムに含まれる少なくとも一つのコンピュータに実行させることを特徴とするマルチキャストシステムのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１２４７０８（Ｐ２０１２−１２４７０８Ａ）
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願番号】特願２０１０−２７３７１７（Ｐ２０１０−２７３７１７）
【出願日】平成２２年１２月８日（２０１０．１２．８）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２２年度、独立行政法人情報通信研究機構次世代ネットワーク（ＮＧＮ）基盤技術の研究開発）は産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願日】平成２２年１２月８日（２０１０．１２．８）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２２年度、独立行政法人情報通信研究機構次世代ネットワーク（ＮＧＮ）基盤技術の研究開発）は産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]