(57)【要約】【課題】各ノードのアクセス回線速度が均一でない場合でも、コンテンツ配送処理の負荷を軽減する通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供する。【解決手段】ネットワーク１００は、論理的にモデル化した論理ネットワークであり、ソースノード２００と配信対象ノード２０１、２０２、２０３間が、論理リンクであるパス３０１〜３０６によってフルメッシュで接続された構成となっており、ソースノード２００と各配信対象ノード２０１、２０２、２０３のアクセス回線速度を基にファンアウト数上限値を算出し、この算出したファンアウト数上限値と、各ノード間のスループットの大きさとを基準にしてノード間のパスと配信先ノードを順次選択することで、コンテンツの配信経路となるツリーを構築し、複数の配信対象ノード２０１、２０２、２０３にマルチキャストにより同一の情報コンテンツを配信する。【選択図】図１
2006287919.tif 000002
【特許請求の範囲】
【請求項１】
配信元のノードからマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワークにおいて、前記配信元のノード及び前記配信先のノードのアクセス回線速度に基づいて、前記配信元のノード及び前記配信先のノード毎のファンアウト数上限値を算出し、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記コンテンツの配信経路となるツリーを構築し、前記ツリーに従って前記コンテンツの配信を行うことを特徴とする通信ネットワーク。
【請求項２】
配信元のノードからマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワークにおいて、各ノード毎のファンアウト数上限値を、前記配信元のノード又は前記配信先のノードのアクセス回線速度に比例した値となるように算出し、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記コンテンツの配信経路となるツリーを構築し、前記ツリーに従って前記コンテンツの配信を行うことを特徴とする通信ネットワーク。
【請求項３】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り上げて算出することを特徴とする請求項１又は請求項２に記載の通信ネットワーク。
【請求項４】
前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットの大きさを基準にして前記ノード間のパスと前記配信先ノードを選択することにより、前記コンテンツの配信経路となるツリーを構築することを特徴とする請求項１から請求項３の何れか１項に記載の通信ネットワーク。
【請求項５】
前記配信元ノード及び前記配信先ノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットが最大のパスから順に選択することを特徴とする請求項１から請求項４の何れか１項に記載の通信ネットワーク。
【請求項６】
既に前記ツリーに加えられた前記配信元ノード及び前記配信先ノードのうち前記ファンアウト数が前記ファンアウト数上限値未満のノードと前記ツリーに加えられていない前記配信先ノード間のスループットが最大である前記パスと前記パスに接続される前記配信先ノードを順次選択することを特徴とする請求項１から請求項５の何れか１項に記載の通信ネットワーク。
【請求項７】
前記スループットが同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムの最も小さい前記パスを選択することを特徴とする請求項４から請求項６の何れか１項に記載の通信ネットワーク。
【請求項８】
前記スループット値に代えて、前記アクセス回線速度の大きさを基準にして前記ノード間のパスと前記配信先ノードを順次選択することを特徴とする請求項４から請求項７の何れか１項に記載の通信ネットワーク。
【請求項９】
前記送信元ノードの上り方向のアクセス回線速度と前記送信先ノードの下り方向のアクセス回線速度のうち、小さい方の値を前記アクセス回線速度とすることを特徴とする請求項８に記載の通信ネットワーク。
【請求項１０】
前記アクセス回線速度が同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムが最も小さい前記パスを選択することを特徴とする請求項８又は請求項９に記載の通信ネットワーク。
【請求項１１】
前記ラウンドトリップタイムが同一の複数の前記パスが選択された場合に、任意の前記パスを選択することを特徴とする請求項７又は請求項１０に記載の通信ネットワーク。
【請求項１２】
前記送信元ノードが、前記ファンアウト数上限値の算出及び前記ツリーの構築を行うことを特徴とする請求項１から請求項１１に記載の通信ネットワーク。
【請求項１３】
前記通信ネットワークに管理サーバを備え、前記管理サーバが、前記ファンアウト数上限値の算出及び前記ツリーの構築を行うことを特徴とする請求項１から請求項１１に記載の通信ネットワーク。
【請求項１４】
マルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワークのコンテンツ配信ノードであって、配信元のノード及び前記配信先のノードのアクセス回線速度に基づいて、前記配信元のノード及び前記配信先のノード毎のファンアウト数上限値を算出する機能と、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記コンテンツの配信経路となるツリーを構築する機能を有することを特徴とするコンテンツ配信ノード。
【請求項１５】
マルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワークのコンテンツ配信ノードであって、各ノード毎のファンアウト数上限値を、前記配信元のノード又は前記配信先のノードのアクセス回線速度に比例した値となるように算出する機能と、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記コンテンツの配信経路となるツリーを構築する機能を有することを特徴とするコンテンツ配信ノード。
【請求項１６】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り上げて算出することを特徴とする請求項１４又は請求項１５に記載のコンテンツ配信ノード。
【請求項１７】
前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットの大きさを基準にして前記ノード間のパスと前記配信先ノードを選択することにより、前記コンテンツの配信経路となるツリーを構築する機能を有することを特徴とする請求項１４から請求項１６の何れか１項に記載のコンテンツ配信ノード。
【請求項１８】
前記配信元ノード及び前記配信先ノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットが最大のパスから順に選択する機能を有することを特徴とする請求項１４から請求項１６の何れか１項に記載のコンテンツ配信ノード。
【請求項１９】
既に前記ツリーに加えられた前記配信元ノード及び前記配信先ノードのうち前記ファンアウト数が前記ファンアウト数上限値未満のノードと前記ツリーに加えられていない前記配信先ノード間のスループットが最大である前記パスと前記パスに接続される前記配信先ノードを順次選択する機能を有することを特徴とする請求項１４から請求項１８の何れか１項に記載のコンテンツ配信ノード。
【請求項２０】
前記スループットが同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムの最も小さい前記パスを選択する機能を有することを特徴とする請求項１７から請求項１９の何れか１項に記載のコンテンツ配信ノード。
【請求項２１】
前記スループットに代えて、前記アクセス回線速度の大きさを基準にして前記ノード間のパスと前記配信先ノードを順次選択する機能を有することを特徴とする請求項１７から請求項２０の何れか１項に記載のコンテンツ配信ノード。
【請求項２２】
前記送信元ノードの上り方向のアクセス回線速度と前記送信先ノードの下り方向のアクセス回線速度のうち、小さい方の値を前記アクセス回線速度とすることを特徴とする請求項２１に記載のコンテンツ配信ノード。
【請求項２３】
前記アクセス回線速度が同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムが最も小さい前記パスを選択する機能を有することを特徴とする請求項２１又は請求項２２に記載のコンテンツ配信ノード。
【請求項２４】
前記ラウンドトリップタイムが同一の複数の前記パスが選択された場合に、任意の前記パスを選択する機能を有することを特徴とする請求項２０又は請求項２３に記載のコンテンツ配信ノード。
【請求項２５】
前記送信元ノードが、前記ファンアウト数上限値の算出及び前記ツリーの構築を行う機能を有することを特徴とする請求項１４から請求項２３に記載のコンテンツ配信ノード。
【請求項２６】
配信元のノードからマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワーク上で、前記コンテンツの配信経路となるツリーを構築する方法であって、前記配信元のノード及び前記配信先のノードのアクセス回線速度に基づいて、前記配信元のノード及び前記配信先のノード毎のファンアウト数上限値を算出するステップと、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記ノード間のパスと前記配信先ノードを選択するステップと、前記選択された前記パス及び前記ノードを前記ツリーに追加するステップとを有することを特徴とするツリー構築方法。
【請求項２７】
配信元のノードからマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する通信ネットワーク上で、前記コンテンツの配信経路となるツリーを構築する方法であって、各ノード毎のファンアウト数上限値を、前記配信元のノード又は前記配信先のノードのアクセス回線速度に比例した値となるように算出するステップと、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記ノード間のパスと前記配信先ノードを選択するステップと、前記選択された前記パス及び前記ノードを前記ツリーに追加するステップとを有することを特徴とするツリー構築方法。
【請求項２８】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り上げて算出することを特徴とする請求項２６又は請求項２７に記載のツリー構築方法。
【請求項２９】
前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットの大きさを基準にして前記ノード間のパスと前記配信先ノードを選択することを特徴とする請求項２６から請求項２８の何れか１項に記載のツリー構築方法。
【請求項３０】
前記配信元ノード及び前記配信先ノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットが最大のパスから順に選択することを特徴とする請求項２６から請求項２９の何れか１項に記載のツリー構築方法。
【請求項３１】
既に前記ツリーに加えられた前記配信元ノード及び前記配信先ノードのうち前記ファンアウト数が前記ファンアウト数上限値未満のノードと前記ツリーに加えられていない前記配信先ノード間のスループットが最大である前記パスと前記パスに接続される前記配信先ノードを順次選択することを特徴とする請求項２６から請求項３０の何れか１項に記載のツリー構築方法。
【請求項３２】
前記スループットが同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムの最も小さい前記パスを選択することを特徴とする請求項２９から請求項３１の何れか１項に記載のツリー構築方法。
【請求項３３】
前記スループットに代えて、前記アクセス回線速度の大きさを基準にして前記ノード間のパスと前記配信先ノードを順次選択することを特徴とする請求項２９から請求項３２の何れか１項に記載のツリー構築方法。
【請求項３４】
前記送信元ノードの上り方向のアクセス回線速度と前記送信先ノードの下り方向のアクセス回線速度のうち、小さい方の値を前記アクセス回線速度とすることを特徴とする請求項３３に記載のツリー構築方法。
【請求項３５】
前記アクセス回線速度が同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムが最も小さい前記パスを選択することを特徴とする請求項３３又は請求項３４に記載のツリー構築方法。
【請求項３６】
前記ラウンドトリップタイムが同一の複数の前記パスが選択された場合に、任意の前記パスを選択することを特徴とする請求項３２又は請求項３５に記載のツリー構築方法。
【請求項３７】
コンピュータ装置である配信元のノード上で実行され、通信ネットワーク上でマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する機能を実現するコンテンツ配信制御プログラムであって、前記配信元のノード及び前記配信先のノードのアクセス回線速度に基づいて、前記配信元のノード及び前記配信先のノード毎のファンアウト数上限値を算出する機能と、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記ノード間のパスと前記配信先ノードを選択する機能と、前記選択された前記パス及び前記ノードを前記ツリーに追加して前記コンテンツの配信経路となるツリーを構築し、前記ツリーに従って前記コンテンツの配信を行う機能を前記配信元のノードに持たせることを特徴とするコンテンツ配信制御プログラム。
【請求項３８】
コンピュータ装置である配信元のノード上で実行され、通信ネットワーク上でマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する機能を実現するコンテンツ配信制御プログラムであって、各ノード毎のファンアウト数上限値を、前記配信元のノード又は前記配信先のノードのアクセス回線速度に比例した値となるように算出するステップと、前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、前記ノード間のパスと前記配信先ノードを選択するステップと、前記選択された前記パス及び前記ノードを前記ツリーに追加するステップとを有することを特徴とするコンテンツ配信制御プログラム。
【請求項３９】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り上げて算出する機能を前記配信元のノードに持たせることを特徴とする請求項３７又は請求項３８に記載のコンテンツ配信制御プログラム。
【請求項４０】
前記配信元のノード及び前記配信先のノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットの大きさを基準にして前記ノード間のパスと前記配信先ノードを選択する機能を前記配信元のノードに持たせることを特徴とする請求項３７から請求項３９の何れか１項に記載のコンテンツ配信制御プログラム。
【請求項４１】
前記配信元ノード及び前記配信先ノードのファンアウト数が、前記ファンアウト数上限値を超えないように、スループットが最大のパスから順に選択する機能を前記配信元のノードに持たせることを特徴とする請求項３７から請求項４０の何れか１項に記載のコンテンツ配信制御プログラム。
【請求項４２】
既に前記ツリーに加えられた前記配信元ノード及び前記配信先ノードのうち前記ファンアウト数が前記ファンアウト数上限値未満のノードと前記ツリーに加えられていない前記配信先ノード間のスループットが最大である前記パスと前記パスに接続される前記配信先ノードを順次選択する機能を前記配信元のノードに持たせることを特徴とする請求項３７から請求項４１の何れか１項に記載のコンテンツ配信制御プログラム。
【請求項４３】
前記スループットが同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムの最も小さい前記パスを選択する機能を前記配信元のノードに持たせることを特徴とする請求項４０から請求項４２の何れか１項に記載のコンテンツ配信制御プログラム。
【請求項４４】
前記スループットに代えて、前記アクセス回線速度の大きさを基準にして前記ノード間のパスと前記配信先ノードを順次選択する機能を前記配信元のノードに持たせることを特徴とする請求項４０から請求項４３の何れか１項に記載のコンテンツ配信制御プログラム。
【請求項４５】
前記送信元ノードの上り方向のアクセス回線速度と前記送信先ノードの下り方向のアクセス回線速度のうち、小さい方の値を前記アクセス回線速度とすることを特徴とする請求項４４に記載のコンテンツ配信制御プログラム。
【請求項４６】
前記アクセス回線速度が同一の複数の前記パスが選択された場合に、当該複数のパスのうち、ラウンドトリップタイムが最も小さい前記パスを選択する機能を前記配信元のノードに持たせることを特徴とする請求項４４又は請求項４５に記載のコンテンツ配信制御プログラム。
【請求項４７】
前記ラウンドトリップタイムが同一の複数の前記パスが選択された場合に、任意の前記パスを選択する機能を前記配信元のノードに持たせることを特徴とする請求項４３又は請求項４６に記載のコンテンツ配信制御プログラム。
【請求項４８】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り下げて、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数に満たないときは、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数以上となるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって算出することを特徴とする請求項１又は請求項２に記載の通信ネットワーク。
【請求項４９】
前記ファンアウト数上限値設定によりツリーを生成したときに、前記配信元ノード及び全ての前記配信先ノードを含むツリーが生成されなかった場合に、前記配信元ノードと全ての前記配信先ノードを含むツリーが生成されるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって前記ファンアウト数上限値を算出することを特徴とする請求項４８に記載の通信ネットワーク。
【請求項５０】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り下げて、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数に満たないときは、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数以上となるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって算出することを特徴とする請求項１４又は請求項１５に記載のコンテンツ配信ノード。
【請求項５１】
前記ファンアウト数上限値設定によりツリーを生成したときに、前記配信元ノード及び全ての前記配信先ノードを含むツリーが生成されなかった場合に、前記配信元ノードと全ての前記配信先ノードを含むツリーが生成されるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって前記ファンアウト数上限値を算出することを特徴とする請求項５０に記載のコンテンツ配信ノード。
【請求項５２】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り下げて、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数に満たないときは、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数以上となるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって算出することを特徴とする請求項２６又は請求項２７に記載のツリー構築方法。
【請求項５３】
前記ファンアウト数上限値設定によりツリーを生成したときに、前記配信元ノード及び全ての前記配信先ノードを含むツリーが生成されなかった場合に、前記配信元ノードと全ての前記配信先ノードを含むツリーが生成されるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって前記ファンアウト数上限値を算出することを特徴とする請求項５２に記載のツリー構築方法。
【請求項５４】
前記ファンアウト数上限値を、前記配信元ノード及び前記配信先ノードの前記アクセス回線速度の和を前記配信先ノードの数で除算して得られる値によって各ノードの前記アクセス回線速度を除算した値を切り下げて、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数に満たないときは、各ノードの前記ファンアウト数上限値の合計値が前記配信先ノードの数以上となるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって算出する機能を前記配信元のノードに持たせることを特徴とする請求項３７又は請求項３８に記載のコンテンツ配信制御プログラム。
【請求項５５】
前記ファンアウト数上限値設定によりツリーを生成したときに、前記配信元ノード及び全ての前記配信先ノードを含むツリーが生成されなかった場合に、前記配信元ノードと全ての前記配信先ノードを含むツリーが生成されるまで、各ノードについて前記アクセス回線速度を前記ファンアウト数上限値に１を加えた値で除算した値を算出しこれが最大であるノードの前記ファンアウト数上限値を１増やすことによって前記ファンアウト数上限値を算出する機能を前記配信元ノードに持たせることを特徴とする請求項５４に記載のコンテンツ配信制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツをマルチキャストによって配信する通信ネットワークに関し、特に、コンテンツ配信処理の負荷の軽減と伝送効率の向上を実現する通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムに関する。
【背景技術】
【０００２】
情報通信ネットワーク上で行われるマルチキャスト通信サービスは、送信者が複数の受信者に対して同一の情報を同時に配信することを目的とする。マルチキャスト通信を用いると、ネットワークの負荷を上げることなく情報を複数の受信者に一斉に送信することができる。一方、アプリケーション層マルチキャスト（ＡＬＭ：Ａｐｐｌｉｃａｔｉｏｎ−ｌａｙｅｒ  Ｍｕｌｔｉｃａｓｔ）は、送信者及び受信者だけを構成要素とするオーバレイネットワーク（論理ネットワーク）上にマルチキャストツリーを形成し、分岐点に位置する受信者が情報のコピーを下流の受信者に転送することで、ツリーに沿ってバケツリレー式に情報の配信を行う方式である。また、ＡＬＭを行う場合、データの中継を行うのを受信者だけに限る必要はなく、中継だけを行う中継ノードを情報の中継に使用することもできる。
【０００３】
上述のような従来技術の情報通信ネットワーク上でより効率的な配信処理を実現する技術として、例えば、特許文献１や非特許文献１が開示されている。
【０００４】
特許文献１は、データ配信システムにおいて、送信サーバが、時刻ｊにおいて直接接続する端末Ｒｊのそれぞれに対してデータ及び少なくともアドレスリストからなる２次配信依頼情報を順次送信する。そして、送信サーバは、この送信とともに、同時刻における通信数の上限値である輻輳制限数ｓｊと、端末Ｒｊの台数で表される分木数Ｎからなる輻輳制限パラメータと、データを直接的又は間接的に受信する端末の全台数である送信端末数ｄｊとを算出し、これら輻輳制限数ｓｊ、分木数Ｎ、及び送信端末数ｄｊを端末Ｒｊのそれぞれに対して送信する。特許文献１は、このようにすることで、通信時に生じる輻輳を制限し、効率的な配信処理を実現するシステムを提供している。
【０００５】
非特許文献１は、ＡＬＭツリーについて、ツリー上の往復遅延時間（ＲＴＴ：Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）最小化に加えて、上流の受信者が情報の複製を下流の受信者に転送する数（ファンアウト数）が受信者ごとに設定された設定値を超えないようにＡＬＭツリーを構築することによって、効率的な配信処理を実現するシステムを提供している。
【特許文献１】特開２００４−４０７１６号公報
【非特許文献１】S.Y. Shi and J.S. Turner著 「Multicast Routing and Bandwidth Dimensioning in Overlay Networks」 IEEE Journal on Selected Areas in Communications, vol.20, no.8、ｐｐ．１４４４−１４５５、２００２年１０月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、上述した従来の効率的な配信処理を実現するシステムにおいては、以下に述べるような問題点が存在する。
【０００７】
第１の問題点は、特許文献１等の従来技術では、各ノードのアクセス回線速度が均一でない場合に、各ノードのアクセス回線がボトルネックとなるので、効率的なコンテンツ配信処理を実現できないことである。
【０００８】
その理由は、制御用パラメータが、端末間で共用されるネットワーク（バックボーン）や無線空間側の輻輳制御を目的として設定されており、各端末のアクセス回線速度及びその速度の不均質性が考慮されていないためである。
【０００９】
第２の問題点は、送信者及び受信者のアクセス回線上り速度や、受信者のファイル転送方式が均一でない場合に、配信性能が低下することである。
【００１０】
その理由は、各ノードのアクセス回線速度や各ファイル転送機能が均一でないにもかかわらず、そのことを考慮せずにこのネットワーク全体でファンアウト数を均等化すると、ツリーの上流にボトルネックが生じて配信性能が低下するためである。
【００１１】
ただし、ここでファイル転送方式とは、受信完了後に転送を開始する方式、受信開始後一定時間待ってから転送を開始する方式、受信開始と同時に転送を開始する方式など、受信者が受信した情報を転送する場合の方式を指している。
【００１２】
第３の問題点は、より迅速に配信完了したノードが発生し始めるようにツリーを構築することで、障害に対する信頼性を確保する必要があるが、この点が考慮されておらず、障害に対する信頼性が確保されていないことである。
【００１３】
第４の問題点は、ノード数が多い大規模なネットワークの場合、ラウンドトリップタイムやスループット等の最適化メトリックに関する情報をエンドツーエンドで測定すると、測定トラフィックが膨大となり、ネットワークや測定端末に大きな負荷を掛けてしまうことである。特に、時刻と共に変化するスループット情報を計測するためには、膨大な測定トラフィックをネットワークに送出する必要がある。
【００１４】
第５の問題点は、より迅速に配信完了したノードが発生し始めるようにツリーを構築することで、一部の遅いアクセス回線速度をもつ受信ノードのアクセス回線がボトルネックとなって受信ノード便益の総和が低下することを回避する必要があるが、この点が考慮されておらず、アクセス回線速度が不均質な環境化における配信の効率性が確保されていないことである。
【００１５】
本発明の目的は、各端末のアクセス回線速度及びその速度の不均質性を考慮することにより、コンテンツ配送処理の負荷を軽減する通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供することにある。
【００１６】
本発明の第２の目的は、各ノードのアクセス回線速度及びファンアウト数上限値を個々に考慮することにより、伝送効率が向上し、コンテンツ配信完了時間が短縮する通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供することにある。
【００１７】
本発明の第３の目的は、コンテンツ配信の完了したノードがより迅速に発生し始めるようにツリーを構築することにより、信頼性が向上する通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供することにある。
【００１８】
本発明の第４の目的は、スループットに代えて、アクセス回線速度の大きさを基準にすることにより、最適化メトリックに関する情報を測定する際に、ネットワークや測定端末に大きな負荷を掛けない通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供することにある。
【００１９】
本発明の第５の目的は、コンテンツ配信の完了したノードがより迅速に発生し始めるようにツリーを構築することにより、一部の遅いアクセス回線速度をもつ受信ノードのアクセス回線がボトルネックとなって受信ノード便益の総和が低下することを回避する、通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムを提供することにある。
【課題を解決するための手段】
【００２０】
上記目的を達成するための本発明では、通信ネットワーク上で、配信元ノードからマルチキャストにより複数の配信先のノードに対して同一のコンテンツを配信する場合に、配信元ノードが、配信元のノード及び配信先のノードのアクセス回線速度に基づいて、配信元のノード及び配信先のノード毎のファンアウト数上限値を算出する。また、配信元のノード又は配信先のノードのアクセス回線速度に比例した値となるように、各ノード毎のファンアウト数上限値を算出する。さらに、配信元のノード及び配信先のノードのファンアウト数が、算出されたファンアウト数上限値を超えないように、スループットの大きさを基準にしてノード間のパスと配信先ノードを選択する。
【００２１】
また、本発明の好ましい態様では、配信元ノード及び配信先ノードのファンアウト数が、ファンアウト数上限値を超えないように、スループットが最大のパスから順に選択する。
【００２２】
さらに、本発明の好ましい態様では、既にツリーに加えられた配信元ノード及び配信先ノードのうち、ファンアウト数が上限値未満のノードと、ツリーに加えられていない配信先ノード間のスループットが最大であるパスと、パスに接続される配信先ノードとを、順次選択することで、コンテンツの配信経路となるツリーを構築する。ツリー構築が完了するとそのツリーに従ってコンテンツの配信を行う。
【００２３】
また、本発明の好ましい他の態様では、複数のパスのうち、スループットが同一の複数のパスが選択された場合に、この複数のパスのうち、ラウンドトリップタイムが最も小さいパスを選択することで、コンテンツの配信経路となるツリーを構築する。ツリー構築が完了するとそのツリーに従ってコンテンツの配信を行う。
【００２４】
さらに、本発明の好ましい別の態様では、スループットに代えて、アクセス回線速度の大きさを基準にしてノード間のパスと配信先ノードを順次選択することで、コンテンツの配信経路となるツリーを構築する。そして、ツリー構築が完了するとそのツリーに従ってコンテンツの配信を行う。
【発明の効果】
【００２５】
本発明の通信ネットワーク、コンテンツ配信ノード、ツリー構築方法、コンテンツ配信制御プログラムによれば、以下の効果が得られる。
【００２６】
第１の効果は、通信ネットワークの各ノードのアクセス回線速度が均一でない場合でも、全配信対象ノードに対するコンテンツ配送処理の負荷が特定リンクに集中しないようなツリーを構築できることである。
【００２７】
その理由は、通信ネットワーク全体でファンアウト数を均等化することはせずに、各ノードのアクセス回線速度を用いて、各ノードの個々のアクセス回線速度に応じて算出した各ノードのファンアウト数上限値に基づいてコンテンツを配信するので、各ノードのアクセス回線速度が均一でない場合でも、各ノードのアクセス回線がボトルネックとならないツリーを構築できるからである。
【００２８】
第２の効果は、通信ネットワークの各ノードのアクセス回線速度が均一でない場合でも、コンテンツ配信完了時間を小さくするツリーを構築できることである。
【００２９】
その理由は、各端末のアクセス回線速度及びその速度の不均質性を考慮し、スループットが大きいパスを選択することによってツリーを構築してコンテンツを配信するので、各ノードのアクセス回線速度が均一でない場合でも、効率的なツリーを形成できるためである。
【００３０】
第３の効果は、障害に対するより高い信頼性を確保するツリーを構築できることである。
【００３１】
その理由は、各ノード又は各ノード間のファンアウト数上限値、スループット及びラウンドトリップタイムに基づいてツリーを構築するので、より迅速に配信完了ノードが発生し始めるため、コンテンツの複製がより迅速にネットワーク上に配置されていくからである。
【００３２】
第４の効果は、最適化メトリックに関する情報をエンドツーエンドで測定することなく、各ノード間のスループットに代えて、各ノードのアクセス回線速度の大きさを基準にして各ノード間のパスと配信先ノードを順次選択するので、ネットワークや測定端末に大きな負荷を掛けてしまうスループットの測定に要するトラフィックを軽減することにより、処理負荷を軽減できることである。
【００３３】
第５の効果は、一部の遅いアクセス回線速度をもつ受信ノードのアクセス回線がボトルネックとなって他の受信ノードの配信完了時間に影響を与え、受信ノードの便益の総和が低下することを回避できることである。
【００３４】
その理由は、各ノード又は各ノード間のファンアウト数上限値、スループット及びラウンドトリップタイムに基づいてツリーを構築するので、一部の遅いアクセス回線速度をもつ受信ノードのアクセス回線がボトルネックとなるのを防ぎ、より迅速に配信完了ノードを発生させることができるからである。
【発明を実施するための最良の形態】
【００３５】
本発明の実施の形態について図面を参照して詳細に説明する。
【００３６】
（第１の実施の形態）
図２は、本発明を適用するネットワークの物理的な構成を示す図である。このネットワーク１５０においては、ルータ２１１〜２１４を有するバックボーン回線１６０を介して、コンテンツの配信元であるソースノード２００と、コンテンツの配信先となる配信対象ノード２０１〜２０３が接続されている。
【００３７】
ここでは、ソースノード２００のバックボーン回線１６０に対する上り方向のアクセス回線速度Ａ１が１００Ｍｂｐｓ、配信対象ノード２０３の上り方向のアクセス回線速度Ａ２が７０Ｍｂｐｓ、配信対象ノード２０１の上り方向のアクセス回線速度Ａ３が１０Ｍｂｐｓ、配信対象ノード２０２の上り方向のアクセス回線速度Ａ４が１Ｍｂｐｓであると想定する。
【００３８】
上記のような構成のネットワーク１５０において、ソースノード２００から全ての配信対象ノード２０１〜２０３に対して同一のコンテンツがマルチキャストにより配信されるものである。
【００３９】
本発明においては、図２に示すようなネットワーク１５０上でコンテンツ配信を行う場合に、ネットワーク１５０の論理的な構成を示す、図１に示すような論理フルメッシュで形成される論理ネットワーク１００上で、後述する方法によってコンテンツ配信のためのツリーを構築し、その構築したツリーに従ってコンテンツのマルチキャストによる配信を実行する。なお、論理ネットワークは、全ノードを含むトポロジーとなっていれば、必ずしもフルメッシュである必要はない。
【００４０】
図１に示すように、図２の物理的なネットワーク１５０を論理的にモデル化したネットワークである論理ネットワーク１００は、ソースノード２００と、配信対象ノード２０１、２０２、２０３間が、論理リンクであるパス３０１〜３０６によってフルメッシュで接続された構成となっている。
【００４１】
図３は、本実施の形態による論理ネットワーク１００の特性を示す模式図である。
【００４２】
図３に示すように、各パス３０１〜３０６にソースノード２００と各配信対象ノード２０１〜２０３間のスループットとラウンドトリップタイム（ＲＴＴ）の情報が付与されている。スループットは、各パスに付した矢印と数値によって示しており、例えば、パス３０１のルートノード２００から配信対象ノード２０３に向う方向のスループットは「５５（Ｍｂｐｓ）」であることを示している。
【００４３】
また、各パス３０１〜３０６のラウンドトリップタイムであるＲＴＴ１〜ＲＴＴ６は、ＲＴＴ２＜ＲＴＴ４、ＲＴＴ３＜ＲＴＴ６＜ＲＴＴ５の関係を有している。
【００４４】
これらの情報は、予めソースノード２００に登録されて管理される。
【００４５】
図４は、ソースノード２００のハードウェア構成例を示すブロック図である。
【００４６】
図４を参照すると、ソースノード２００は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ４０１、主記憶部４０２、ネットワーク伝送制御部４０３、ハードディスク装置等の補助記憶部４０４、キーボードやマウス等の入力部４０５、液晶ディスプレイ等の表示部４０６を備えている。
【００４７】
ソースノード２００では、補助記憶部４０４に格納されたコンテンツ配信制御プログラム５００を主記憶部４０２にロードしてＣＰＵ４０１上で実行することにより、後述するコンテンツ配信のためのツリー構築の処理を行う機能及びマルチキャストによるコンテンツの配信を行う機能を提供する。
【００４８】
なお、ノードＩＤ、ＩＰアドレス、アクセス回線情報（スループット値、ラウンドトリップタイム（ＲＴＴ）値等）、各ノード間のスループット値、ＲＴＴ値等を含む情報についても、補助記憶部４０４などに格納される。
【００４９】
以下、本実施の形態による論理ネットワーク１００におけるコンテンツ配信制御の手順について詳細に説明する。
【００５０】
図５は、論理ネットワーク１００上で、ソースノード２００が、複数の配信対象ノード２０１〜２０３に対して同一のコンテンツを配信する場合のツリー構築手順を示すフローチャートである。また、図７は、図１のネットワークについて本発明を適用した場合における、ツリー状態の変化を示す図である。
【００５１】
まず、ソースノード（配信サーバ）２００に、配信対象（配信先）としてのノードを登録する（ステップ５０１）
【００５２】
ここでは、ノード２０１、２０２、２０３のノードＩＤ、ＩＰアドレス、アクセス回線情報（スループット値、ラウンドトリップタイム（ＲＴＴ）等）、各ノード間のスループット値、ＲＴＴ値等を含む情報を、ソースノード２００に登録する。図７では、配信対象ノード２０１、２０２、２０３のノードＩＤをそれぞれ＃１、＃２、＃３としている。
【００５３】
なお、図１のネットワーク構成の場合、初期状態では、図７（ａ）に示すように、ソースノード２００だけがツリーに追加され、配信対象ノード及びパスの何れもツリーに追加されていない。
【００５４】
配信対象ノード２０１〜２０３をソースノードに登録した後、以下の手順によってツリーを構築することにより、そのツリーに従ってソースノード２００が複数の配信対象ノード２０１〜２０３に対して同一のコンテンツをマルチキャストにより配信する。
【００５５】
ソースノード２００において、ソースノード２００及び各配信対象ノード２０１〜２０３のファンアウト数の上限値を算出する（ステップ５０２）。
【００５６】
ステップ５０２におけるソースノード２００による各ノードのファンアウト数の上限値算出の処理手順について、図６のフローチャートに従って説明する。
【００５７】
配信対象ノード２０１〜２０３について、上り方向のアクセス回線速度Ａｉ毎のノード数ａｉを求める（ステップ６０１）。ここで、ｉは１からノード数ｎの任意の整数である。例えば、ネットワーク全体において、上り回線速度が速い順に、上り方向のアクセス回線速度Ａｉ毎のノード数ａｉを求めるものとする。
【００５８】
ソースノード２００及び配信対象ノード２０１〜２０３について、上り方向のアクセス回線速度Ａｉを求める（ステップ６０１）。ここで、ｉは、１からノード数ｎの任意の整数である。
【００５９】
図１及び図２に示すネットワークにおいて、上り方向のアクセス回線速度Ａ１を１００Ｍｂｐｓ、上り方向のアクセス回線速度Ａ２を７０Ｍｂｐｓ、上り方向のアクセス回線速度Ａ３を１０Ｍｂｐｓ、上り方向のアクセス回線速度Ａ４を１Ｍｂｐｓとする。
【００６０】
次いで、下記の式１に基づいて、ｘ（Ｍｂｐｓ）を算出する（ステップ６０２）。
【００６１】
【数１】
2006287919.tif 000003
【００６２】
上記の例では、
【００６３】
【数２】
2006287919.tif 000004
【００６４】
となり、全配信対象ノード数は、配信対象ノード２０１〜２０３の「３」であるから、式１からｘ（Ｍｂｐｓ）＝１８１／３≒６０．３が算出される。
【００６５】
このｘ（Ｍｂｐｓ）は、ネットワーク上の各ノードに割り当てられる平均の配信速度を意味している。
【００６６】
最後に、各ノードのファンアウト数の上限値として、Ａｉ／ｘを切り上げた値を算出する（ステップ６０３）。
【００６７】
上記例の場合、ソースノード２００のファンアウト数の上限値として、１００／６０．３≒１．７を切り上げた値「２」が算出される。同様に、配信対象ノード２０１のファンアウト数の上限値として、１０／６０．３≒０．１７を切り上げた値「１」が、配信対象ノード２０２のファンアウト数の上限値として、１／６０．３≒０．０１７を切り上げた値「１」が、配信対象ノード２０３のファンアウト数の上限値として、７０／６０．３≒１．２を切り上げた値「２」がそれぞれ算出される。
【００６８】
なお、アクセス回線速度については、回線が全二重（ＦＴＴＨ、ＡＤＳＬ等の回線）である場合には、その回線の上り回線速度そのものとし、回線が半二重（無線ＬＡＮ等の回線）である場合には、回線速度の２分の一が本実施の形態でいう上り回線速度とする。
【００６９】
各ノードのファンアウト数の上限値が算出されると、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとツリーに追加されていないノードとの間のスループットが最大であるパス及びそのパスを含むノードを選択する（ステップ５０３）。
【００７０】
図７（ａ）に示す状態では、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとしては、ソースノード２００が該当し、追加されていないノードとして配信対象ノード２０１〜２０３が該当するので、ルートノード２００と各配信対象ノード２０１〜２０３間のパスのスループットを調べ、ルートノード２００と未加入ノード間のスループットが最大であるパスとしてパス３０１が選択され、パス３０１に接続される配信対象ノード２０３が選択される。この状態を図７（ｂ）に示す。図７では、選択されているノード及びパスを波線で示し、選択後に追加されたノード及びパスを太線で示している。
【００７１】
次いで、スループット最大のパスが複数存在するかを調べ（ステップ５０４）、存在する場合には、ラウンドトリップタイムが最も小さいパスを選択する（ステップ５０５）。
【００７２】
また、ラウンドトリップタイムに基づく選択でも、ラウンドトリップタイム最小のパスが複数存在するかを調べ（ステップ５０６）存在する場合には、任意の１つのパス及びサーバを選択する（ステップ５０７）。
【００７３】
ステップ５０４とステップ５０６で複数のパスが存在しない場合には、ステップ５０８の処理に進む。
【００７４】
そして、ステップ５０３、５０５、５０７で選択されたパス及びノードをツリーに追加する（ステップ５０８）。
【００７５】
図３の場合、ステップ５０３で選択されたパスは、パス３０１だけであるので、選択されたパス３０１と配信対象ノード２０３が、ステップ５０８でツリーに追加される。この状態を図７（ｃ）に示す。
【００７６】
次いで、ネットワークの全てのノードがツリーに含まれているか（全てのノードが追加されているか）を調べる（ステップ５０９）。
【００７７】
ステップ５０９で全てのノードがツリーに含まれていなければ、ステップ５０３に戻り、全ノードが追加されるまで処理を繰り返す。
【００７８】
ステップ５０９で全てのノードが含まれていれば、ツリーが完成した（ツリー構築が完了した）ことを示しているので、完成したツリーに従ってソースサーバ２００から各配信対象ノード２０１〜２０３に対してコンテンツが配信される（ステップ５１０）。
【００７９】
図７（ｃ）の状態では、全てのノードがツリーに含まれていないので、ステップ５０３に戻り選択処理がなされる。
【００８０】
以下、図１に示すネットワークについてツリーが完成するまでの手順を説明する。
【００８１】
パス３０１と配信対象ノード２０３が追加された状態（図７（ｃ））では、ソースノード２００のファンアウト数が「１」、配信対象ノード２０３のファンアウト数が「０」である。
【００８２】
図７（ｃ）の状態で、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとしては、ソースノード２００と配信対象ノード２０３が該当し、追加されていないノードが配信対象ノード２０１、２０２であるので、ルートノード２００と配信対象ノード２０１、２０２間及び配信対象ノード２０３と配信対象ノード２０１、２０２間のパスのスループットを調べ、スループットが最大であるパスとしてパス３０２とパス３０４が選択され、パス３０２及び３０４に接続される配信対象ノード２０１が選択される（図７（ｄ））。
【００８３】
図７（ｄ）の状態で、スループット最大のパスが複数存在するので（ステップ５０４）、パス３０２とパス３０４のうち、ラウンドトリップタイムが最も小さいパスを選択する（ステップ５０５）。
【００８４】
ここでは、パス３０２のラウンドトリップタイム（ＲＴＴ２）がパス３０４のラウンドトリップタイム（ＲＴＴ４）より小さいので、ステップ５０５でパス３０２が選択される（図７（ｅ））。
【００８５】
ラウンドトリップタイム最小のパスはパス３０２だけであるので、選択されたパス３０２とパス３０２に含まれる配信対象ノード２０１がステップ５０８でツリーに追加される（図７（ｆ））。
【００８６】
パス３０２と配信対象ノード２０１が追加された状態（図７（ｆ））では、ソースノード２００のファンアウト数が「２」、配信対象ノード２０１、２０３のファンアウト数が「０」である。
【００８７】
図７（ｆ）の状態では、全てのノードがツリーに含まれていないので、ステップ５０３に戻り選択処理がなされる（ステップ５０９）。
【００８８】
図７（ｆ）の状態で、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとしては、配信対象ノード２０１と配信対象ノード２０３が該当し、追加されていないノードが配信対象ノード２０２である。ソースノード２００については、ファンアウト数が「２」であり、ステップ５０３でファンアウト数の上限値未満の条件を満たさないので対象から除かれる。
【００８９】
ステップ５０３で、配信対象ノード２０１と配信対象ノード２０２間及び配信対象ノード２０３と配信対象ノード２０２間のパスのスループットを調べ、スループットが最大であるパスとしてパス３０５とパス３０６が選択され、パス３０５及び３０６に接続される配信対象ノード２０２が選択される（図７（ｇ））。
【００９０】
図７（ｇ）の状態で、スループット最大のパスが複数存在するので（ステップ５０４）、パス３０５とパス３０６のうち、ラウンドトリップタイムが最も小さいパスを選択する（ステップ５０５）。
【００９１】
ここでは、パス３０６のラウンドトリップタイム（ＲＴＴ６）の方がパス３０５のラウンドトリップタイム（ＲＴＴ５）より小さいので、ステップ５０５でパス３０６が選択される（図７（ｈ））。
【００９２】
ラウンドトリップタイム最小のパスはパス３０６だけであるので、選択されたパス３０６とパス３０６に含まれる配信対象ノード２０２がステップ５０８でツリーに追加される（図７（ｉ））。
【００９３】
パス３０６と配信対象ノード２０２が追加された状態（図７（ｉ））では、ソースノード２００のファンアウト数が「２」、配信対象ノード２０１、２０２のファンアウト数が「０」、配信対象ノード２０３のファンアウト数が「１」である。
【００９４】
図７（ｉ）の状態において、全てのノードがツリーに含まれている状態となるので（ステップ５０９でＹＥＳ）、ツリーが完成していることからステップ５１０に進み、完成したツリーに従ってソースサーバ２００から全ての配信対象ノード２０１〜２０３に対して同一のコンテンツが配信されることになる（ステップ５１０）。
【００９５】
以下、本実施の形態によって得られる効果を述べる。
【００９６】
本実施の形態の第１の効果は、ネットワーク１５０の各ノード２００〜２０３の上りのアクセス回線速度Ａ１〜Ａ４が均一でない場合でも、全配信対象ノード２０１〜２０３に対するコンテンツ配送処理の負荷が特定リンクに集中しないようなツリーを構築できることである。
【００９７】
その理由は、本発明が、論理ネットワーク１００全体でファンアウト数ｆを均等化することはせずに、各ノード２００〜２０３の上りのアクセス回線速度Ａ１〜Ａ４を用いて算出した各ノード２００〜２０３のファンアウト数上限値に基づいてコンテンツを配信するので、各ノード２００〜２０３のアクセス回線速度Ａ１〜Ａ４を超えることなくコンテンツを配信できることから、各ノード２００〜２０３のアクセス回線速度Ａ１〜Ａ４が均一でない場合でも、各ノード２００〜２０３の上りのアクセス回線速度Ａ１〜Ａ４がボトルネックとならないツリーを構築できるからである。
【００９８】
本実施の形態の第２の効果は、ネットワーク１５０の各ノード２００〜２０３のアクセス回線速度が均一でない場合でも、コンテンツ配信完了時間を短縮できるツリーを構築できることである。
【００９９】
その理由は、各ノード２００〜２０３のアクセス回線速度Ａ１〜Ａ４及びその速度の不均質性を考慮し、上りのアクセス回線速度Ａ１〜Ａ４及び全ノード数に基づいて各ノード２００〜２０３のファンアウト数上限値を算出し、各ノード２００〜２０３のファンアウト数上限値に応じ、各ノード２００〜２０３間のスループット値が大きいパスを選択し、ラウンドトリップタイムが小さいパスを選択することによってツリーを構築してコンテンツを配信するので、各ノード２００〜２０３のアクセス回線速度Ａ１〜Ａ４が均一でない場合でも、コンテンツ配信完了時間を小さくする効率的なツリーを形成できるためである。
【０１００】
本実施の形態の第３の効果は、障害に対するより高い信頼性を確保するツリーを構築できることである。
【０１０１】
その理由は、各ノード２００〜２０３又は各ノード２００〜２０３間のファンアウト数上限値、スループット及びラウンドトリップタイムに基づいてツリーを構築するので、より迅速に配信完了ノードが発生し始めるからである。
【０１０２】
本実施の形態の第４の効果は、上記のような手順で構築したツリーに従って、全ての配信対象ノード２０１〜２０３に対してマルチキャストによるコンテンツ配信を行うことによってボトルネックの発生を回避できることから、配信対象ノード２０１〜２０３のうち、コンテンツの配信を完了するノードがより早いタイミングで発生する可能性が高くなるので、障害でコンテンツの配信が中断される可能性を極力なくした高い信頼性を実現することができる。
【０１０３】
また、配信を完了した配信対象ノードが、配信されたコンテンツのコピーを下流のノードにより迅速に転送することができることである。
【０１０４】
本実施の形態の第５の効果は、上記のような手順で構築したツリーに従って、全ての配信対象ノード２０１〜２０３に対してマルチキャストによるコンテンツ配信を行うことによってボトルネックの発生を回避できることから、配信対象ノード２０１〜２０３のうち、コンテンツの配信を完了するノードがより早いタイミングで発生する可能性が高くなるので、一部の遅いアクセス回線速度をもつ受信ノードのアクセス回線がボトルネックとなって他の受信ノードの配信完了時間に影響を与えることを回避できるので、受信ノードの便益の総和を向上させることができる。
【０１０５】
以上の説明では、図１の構成のネットワークについて、ファンアウト数の上限値を算出した場合を示したが、ノード数ｎのネットワークについてファンアウト数の上限値を算出する場合の方法について、図８を参照して説明する。
【０１０６】
図８において、ノード数ｎのネットワークについて、各ノードの上り回線速度Ａ１〜Ａｎを求める（図６のステップ６０１）。この求めた上り回線速度Ａ１〜Ａｎに基づいた式１によってｘを算出し（図６のステップ６０２）、ノード毎に上り回線速度に応じてファンアウト数上限値を算出する（図６のステップ６０３）。
【０１０７】
コンテンツの配信元であるソースサーバは、このようにして算出した各ノード毎のファンアウト数上限値を図８に示すようなテーブルの形式で格納し、ツリー構築手順におけるパスの選択の条件として用いる。
【０１０８】
図９及び図１０は、ファンアウト数上限値の算出結果の他の例を示している。
【０１０９】
図９に示すようなネットワークにおいて、上り回線速度は、１００Ｍｂｐｓ、５０Ｍｂｐｓ、１０Ｍｂｐｓの３種類が存在する。そして、上り回線速度が速い順に、上り回線速度が同じである各ノード数を求めると、上り回線速度１００Ｍｂｐｓのノード数は、ソースノード２００と配信対象ノード２０３の２つであり、上り回線速度５０Ｍｂｐｓのノード数は、配信対象ノード２０１の１つであり、上り回線速度１０Ｍｂｐｓのノード数は、配信対象ノード２０２の１つである。
【０１１０】
ここで、上述した算出ステップによって、同一の上り回線速度における１ノードあたりのファンアウト数上限値を算出すると、図１０に示すように、上り回線速度１００Ｍｂｐｓのノードについては、ファンアウト数上限値が「２」となり、上り回線速度５０Ｍｂｐｓと１０Ｍｂｐｓのノードについては、ファンアウト数上限値が「１」となる。
【０１１１】
次いで、本発明によるファンアウト数上限値を条件に用いたツリー構築を行った場合の効果について説明する。
【０１１２】
図１１と図１２は、ノード数５０、第１の回線の上り回線速度が１００Ｍｂｐｓ、第２の回線の上り回線速度が５Ｍｂｐｓ、第１の回線の本数と第２の回線の本数との比が１対４である構成のネットワークにおいて、全ノードについて均一に設定したファンアウト数上限値を用いてツリーを構築した場合と、本発明を適用して算出したファンアウト数上限値とを用いてツリーを構築した場合に、サイズ１ＧＢのコンテンツをマルチキャスト配信した時の配信完了時間を比較して示した図である。
【０１１３】
なお、図１１は、転送方式がｗａｉｔのものであり、図１２は、転送方式がｎｏ−ｗａｉｔのものである。ここで、転送方式ｗａｉｔとは、コンテンツ受信を完了してから転送を開始する転送方式であり、転送方式ｎｏ−ｗａｉｔとは、コンテンツ受信と転送を同時に開始する転送方式である。
【０１１４】
図１１を参照すると、本発明を適用して算出したファンアウト数上限値を用いてツリーを構築した場合、全ノードに対して均一にファンアウト数上限値を設定してツリーを構築した場合と比較して、配信完了時間が大幅に短縮されることが分かる。
【０１１５】
また、図１２を参照すると、本発明を適用して算出したファンアウト数上限値を用いてツリーを構築した場合、全ノードに対して均一にファンアウト数上限値を設定してツリーを構築した場合と比較して、転送方式がｗａｉｔの場合程ではないが、配信完了時間が短縮されていることが分かる。図１１，図１２の結果から分かるように、転送方式を「ｗａｉｔ」と「ｎｏ−ｗａｉｔ」間で切り替えて転送を行う場合、例えば、ファンアウト数上限値を「１」に設定したときには、他の値に設定されたときと比較すると、転送方式「ｎｏ−ｗａｉｔ」では、効率的に転送がなされるのに対し、転送方式「ｗａｉｔ」では、極端に転送効率が下がってしまう。これに対し、本発明を適用すれば、上記の様に転送方式「ｗａｉｔ」でも転送効率が下がることがなく、良好な結果が得られる。その理由は、各端末のアクセス回線速度及びその速度の不均質性等について、上記論理ネットワーク全体との関係を考慮してファンアウト数上限値を算出し、その算出したファンアウト数上限値を超えないようにして上記コンテンツを配信対象ノードに配信しているからである。
【０１１６】
（第２の実施の形態）
なお、上述した実施の形態では、ネットワークでコンテンツを配信するソースノードが、上述したような方法によってツリー構築を実行する場合について説明したが、第２の実施の形態では、図１３に示すように、論理ネットワーク１００に対してツリー構築を実行するための専用の管理サーバ４００を備えた構成とすることも可能である。
【０１１７】
管理サーバ４００は、各ノード（ソースノード及び配信対象ノード）のノードＩＤとＩＰアドレス、パスのアクセス回線情報（スループット値、ＲＴＴ値等）、各ノード間のスループット値、ＲＴＴ値等を含む情報を有しており、ファンアウト数の上限値の算出処理及び図５に示す手順によるツリー構築を実行する。
【０１１８】
そして、ソースノード２００は、管理サーバ４００から完成したツリーの情報を取得することで、そのツリーに従ってコンテンツの配信を実行する。
【０１１９】
（第３の実施の形態）
上述した第１の実施の形態では、図５のステップ５０３で、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとツリーに追加されていないノードとの間のスループットが最大であるパス及びそのパスを含むノードを選択しているが、この第３の実施の形態においては、スループットに代えてアクセス回線速度が最大であるパスを選択するようにしている。より詳細には、各ノード２００〜２０３間のスループットに代えて、配信元ノードの上り方向のアクセス回線速度Ａ１〜Ａ４と配信先ノード２０１〜２０３の下り方向のアクセス回線速度とのうち、小さい方の値のアクセス回線速度を基準として、アクセス回線速度が最大である各ノード２００〜２０３間のパスと配信先ノード２０１〜２０３を順次選択してツリーを構築する。
【０１２０】
本実施の形態によれば、時刻と共に変化するスループット情報を計測するためには、膨大な測定トラフィックをネットワークに送出する必要があるが、最適化メトリックに関する情報をエンドツーエンドで測定することなく、各ノード間のスループットに代えて、各ノード２００〜２０３のアクセス回線速度Ａ１〜Ａ４を基準にして各ノード２００〜２０３間のパスと配信先ノード２０１〜２０３を順次選択してツリーを構築するので、ネットワーク１５０や測定端末に大きな負荷を掛けてしまうスループットの測定に要するトラフィックを軽減できるため、処理負荷を軽減できることである。
【０１２１】
（第４の実施の形態）
上述した第１の実施の形態では、図６のステップ６０３で、各ノードのファンアウト数の上限値として、Ａｉ／ｘを切り上げた値を算出しているが、この第４の実施の形態においては、Ａｉ／ｘの小数点以下を切り捨てた値を算出して、その結果設定された各ノードのファンアウト数上限値の合計値が配信対象ノードの合計ノード数に満たないときは、各ノードのファンアウト数上限値の合計値が配信対象ノードの合計ノード数以上となるまで、各ノードについてスループット値をファンアウト数上限値に１を加えた値で除算した値が最大となるノードのファンアウト数上限値を１増やす。
【０１２２】
ただし、そのようなノードが複数存在する場合は、その複数のノードのファンアウト数上限値を等しく１ずつ増やす。この作業をファンアウト数上限値の合計数が配信先ノードの合計数（ｎ−１）に到達するまで繰り返す。
【０１２３】
また、このようにファンアウト数上限値を設定してツリーを生成したにも関わらず、配信元ノードと全ての配信先ノードを含むツリーが生成されない場合には、同様の操作でファンアウト数上限値を増やし、再度ツリーを生成する。
【０１２４】
図１及び図２に示すネットワークにおいて、上り方向のアクセス回線速度Ａ１を１００Ｍｂｐｓ、上り方向のアクセス回線速度Ａ２を７０Ｍｂｐｓ、上り方向のアクセス回線速度Ａ３を１０Ｍｂｐｓ、上り方向のアクセス回線速度Ａ４を１Ｍｂｐｓとする。
【０１２５】
次いで、下記の式１に基づいて、ｘ（Ｍｂｐｓ）を算出する。
【０１２６】
【数３】
2006287919.tif 000005
【０１２７】
上記の例では、
【０１２８】
【数４】
2006287919.tif 000006
【０１２９】
となり、全配信対象ノード数は、配信対象ノード２０１〜２０３の「３」であるから、式１からｘ（Ｍｂｐｓ）＝１８１／３≒６０．３が算出される。
【０１３０】
このｘ（Ｍｂｐｓ）は、ネットワーク上の各ノードに割り当てられる平均の配信速度を意味している。
【０１３１】
次に、各ノードのファンアウト数の上限値として、Ａｉ／ｘを切り下げた値を算出する。
【０１３２】
上記例の場合、ソースノード２００のファンアウト数の上限値として、１００／６０．３≒１．７を切り下げた値「１」が算出される。同様に、配信対象ノード２０１のファンアウト数の上限値として、１０／６０．３≒０．１７を切り下げた値「０」が、配信対象ノード２０２のファンアウト数の上限値として、１／６０．３≒０．０１７を切り下げた値「０」が、配信対象ノード２０３のファンアウト数の上限値として、７０／６０．３≒１．２を切り下げた値「１」がそれぞれ算出される。
【０１３３】
ここで、上記ファンアウト数の上限値の合計値は１＋０＋０＋１＝２となり、ノード数４から１を引いた値３に満たないので、ファンアウト数の上限値を追加する。ソースノード２００のファンアウト数上限値を１増やした場合の上限値は２で、この値でスループット１００を割ると５０となる。同様に、配信対象ノード２０１の場合１０÷１＝１０となり、配信対象ノード２０２の場合１÷１＝１となり、配信対象ノード２０３の場合７０÷２＝３５となる。したがって、上限値を１増やした場合のファンアウト数１当たりの単位スループットを比較すると、ソースノード２００の５０という値が最も大きいので、ソースノード２００のファンアウト数の上限値を増やすことになる。結果として、この場合、ソースノード２００のファンアウト数の上限値として「２」が算出され、配信対象ノード２０１のファンアウト数の上限値として「０」が、配信対象ノード２０２のファンアウト数の上限値として「０」が、配信対象ノード２０３のファンアウト数の上限値として「１」がそれぞれ算出される。
【０１３４】
上記のようにファンアウト数の上限値を設定してツリーを生成したときに、ファンアウトの上限値設定の影響で配信元ノードと全ての配信先ノードを含むツリーが生成されない場合には、上記と同様の作業によりファンアウト数の上限値を増やして、再度ツリーを生成する。
【０１３５】
なお、アクセス回線速度については、回線が全二重（ＦＴＴＨ、ＡＤＳＬ等の回線）である場合には、その回線の上り回線速度そのものとし、回線が半二重（無線ＬＡＮ等の回線）である場合には、回線速度の２分の一が本実施の形態でいう上り回線速度とする。
【０１３６】
本実施の形態によれば、Ａｉ／ｘを切り上げることによって上り速度が遅いノードにファイルを転送させる可能性が生じるのを避けることによって、ツリーの性能が低下するのを防ぐことができる。
【０１３７】
（第５の実施の形態）
上述した第１の実施の形態では、式１によってパラメータｘの値を設定して、そのｘの値によりファンアウト数上限値を設定するが、この第５の実施の形態では、バックボーンネットワークが他のトラヒックによって混雑して、バックボーンリンクの平均利用可能帯域が式１によって得られる値よりも小さくなった場合には、ｘの値を式１で得られる値の代わりにバックボーンリンクの平均利用可能帯域とすることでファンアウト数上限値を設定する。バックボーンリンクの平均利用可能帯域は、例えば、各ノード間スループットの平均値などで表すことができる。
【０１３８】
本実施の形態によれば、バックボーンリンクの平均利用可能帯域が式１で与えられる値よりも小さい場合に、式１で与えられる値をｘとしてファンアウト数上限値を設定すると、各ノードのファンアウト数を不要に厳しく制限してしまうことで配信性能が低下してしまうのを防ぎ、バックボーンネットワークが他のトラヒックによって混雑した状況においてツリーの配信性能を向上させることができる。
【０１３９】
（第６の実施の形態）
上述した第１の実施の形態では、図５のステップ５０２〜５０７で、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとツリーに追加されていないノードとの間のスループットが最大であるパス及びそのパスを含むノード、これが等しい場合はＲＴＴが最小であるパス及びそのパスを含むノード、更にこれが等しい場合は任意のパス及びそのパスを含むノードを選択しているが、この第６の実施の形態においては、ツリーに追加されていないノードのうちファンアウト数上限値が１以上のノードが存在する場合は、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとツリーに追加されていないノードのうちファンアウト数上限値が１以上のノードとの間のスループットが最大であるパス及びそのパスを含むノード、これが等しい場合はＲＴＴが最小であるパス及びそのパスを含むノード、更にこれが等しい場合は任意のパス及びそのパスを含むノードを選択する。
【０１４０】
また、ツリーに追加されていないノードのうちファンアウト数上限値が１以上のノードが存在しない場合は、既にツリーに追加されているノードでファンアウト数が算出した上限値未満（ファンアウト数＜上限値）のノードとツリーに追加されていないノードとの間のスループットが最大であるパス及びそのパスを含むノード、これが等しい場合はＲＴＴが最小であるパス及びそのパスを含むノード、更にこれが等しい場合は任意のパス及びそのパスを含むノードを選択する。
【０１４１】
本実施の形態によれば、ツリー生成の初期の段階で、上流にファンアウト数上限値が０であるノードが選ばれることによって、配信元ノードと全ての配信先ノードを含むツリーが生成されないことがなくなるので、ファンアウト数上限値を増やす動作を行わずにツリーを生成することができる。
【図面の簡単な説明】
【０１４２】
【図１】本発明の第１の実施の形態による論理ネットワークの構成を示す図である。
【図２】本発明の第１の実施の形態によるネットワークの物理的な構成を示す図である。
【図３】第１の実施の形態による論理ネットワークの特性を示す模式図である。
【図４】第１の実施の形態による論理ネットワークのソースノードのハードウェア構成を示すブロック図である。
【図５】第１の実施の形態による複数の配信対象ノードに対して同一のコンテンツを配信する場合の処理手順を示すフローチャートである。
【図６】第１の実施の形態によるファンアウト数上限値の算出処理を示すフローチャートである。
【図７】図１の論理ネットワークについて本発明を適用した場合における、ツリー状態の変化を示す図である。
【図８】ノード数ｎのネットワークについてファンアウト数の上限値を算出する場合の方法を説明する図である。
【図９】ファンアウト数上限値の算出結果の他例を示すためのネットワーク構成を示す図である。
【図１０】ファンアウト数上限値の算出結果の他例を示す図である。
【図１１】第１の実施の形態によるファンアウト数上限値を条件に用いたツリー構築を行った場合の効果を、ファンアウト数上限値と、配信完了時間との関係を示す図である。
【図１２】第１の実施の形態によるファンアウト数上限値を条件に用いたツリー構築を行った場合の効果を、ファンアウト数上限値と、配信完了時間との関係を示す図である。
【図１３】本発明の第２の実施の形態による論理ネットワークの構成を示す図である。
【符号の説明】
【０１４３】
１００：論理ネットワーク
１５０：ネットワーク
１６０：バックボーン回線
２００：ソースノード
２０１，２０２，２０３：配信対象ノード
２１１，２１２，２１３，２１４：ルータ
３０１，３０２，３０３，３０４，３０５，３０６：パス
４０１：ＣＰＵ
４０２：主記憶部
４０３：ネットワーク伝送制御部
４０４：補助記憶部
４０５：入力部
４０６：表示部
５００：コンテンツ配信制御プログラム
Ａ１，Ａ２，Ａ３，Ａ４：上り方向のアクセス回線速度
【図１】
2006287919.tif 000007
【図２】
2006287919.tif 000008
【図３】
2006287919.tif 000009
【図４】
2006287919.tif 000010
【図５】
2006287919.tif 000011
【図６】
2006287919.tif 000012
【図７】
2006287919.tif 000013
【図８】
2006287919.tif 000014
【図９】
2006287919.tif 000015
【図１０】
2006287919.tif 000016
【図１１】
2006287919.tif 000017
【図１２】
2006287919.tif 000018
【図１３】
2006287919.tif 000019