(57)【特許請求の範囲】
【請求項１】
物理的なネットワーク構成にかかわらず論理的なデータ配信経路が設定されるデータ配信システムの配信経路構築方法において、
調査パケット送信端末からネットワーク内の複数の端末に調査パケットを送信し、前記複数の端末のそれぞれの端末からの前記調査パケットに対応する応答パケットの受信の有無を調査する調査ステップと、
調査結果に基づき、受信のある前記応答パケットの送信元の端末群を含む第１のグループと、受信のない前記応答パケットの送信元の端末群を含む第２のグループとにグループ化するグループ化ステップと、
前記第１のグループと前記第２のグループ間の配信経路の数を減少させるようにデータ通信の相手となる端末を変更する通信相手変更ステップと、
を含むことを特徴とする配信経路構築方法。
【請求項２】
請求項１記載の配信経路構築方法において、
前記調査ステップで前記調査パケットを送信した全ての端末から応答パケットを受信した場合、次回の前記調査ステップで送信する調査パケット数を増加させる増加ステップを
有することを特徴とする配信経路構築方法。
【請求項３】
請求項２記載の配信経路構築方法において、
前記グループ化ステップは、前記応答パケットを受信できた端末群と、前記応答パケットを受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報と矛盾している場合は、前記調査パケット数の増加を停止する
ことを特徴とする配信経路構築方法。
【請求項４】
請求項３記載の配信経路構築方法において、
前記グループ化ステップは、前記応答パケットを受信できた端末群と、前記応答パケットを受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報との矛盾を解消した場合は、前記調査パケット数の増加を再開する
ことを特徴とする配信経路構築方法。
【請求項５】
請求項３又は４記載の配信経路構築方法において、
前記グループ化ステップで得られる前記グループ情報に変化がなくなった場合、前記応答パケットを受信できなかった端末群のいずれかの端末を新たな調査パケット送信端末に指名する指名ステップを
有することを特徴とする配信経路構築方法。
【請求項６】
請求項５記載の配信経路構築方法において、
前記指名ステップで新たに指名された調査パケット送信端末は、前記調査パケット送信端末において送信する調査パケット数を受け継いで、前記調査パケットの一斉送信を行う
ことを特徴とする配信経路構築方法。
【請求項７】
請求項１記載の配信経路構築方法において、
前記調査ステップと前記グループ化ステップと前記通信相手変更ステップを繰り返して配信経路の再構築を行う
ことを特徴とする配信経路構築方法。
【請求項８】
物理的なネットワーク構成にかかわらず論理的なデータ配信経路が設定されるデータ配信システムの端末装置において、
調査パケット送信端末からネットワーク内の複数の端末に調査パケットを送信し、前記複数の端末のそれぞれの端末からの前記調査パケットに対応する応答パケットの受信の有無を調査する調査手段と、
前記調査手段の調査結果に基づき、受信のある前記応答パケットの送信元の端末群を含む第１のグループと、受信のない前記応答パケットの送信元の端末群を含む第２のグループとにグループ化するグループ化手段と、
前記第１のグループと前記第２のグループ間の配信経路の数を減少させるようにデータ通信の相手となる端末を変更する通信相手変更手段と、
を有することを特徴とする端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ配信システムの配信経路構築方法及び端末装置に関する。
【背景技術】
【０００２】
クライアント・サーバ型のデータ配信システムでは、データ受信端末数の増加に応じて、配信サーバの負荷が大きくなる。このため、大規模なデータ配信システムにおいては、アクセスが集中する配信サーバやネットワークインフラの容量を大きくする必要があり、配信コストが増加してしまう。そのため、近年では、Ｐ２Ｐ（ｐｅｅｒ−ｔｏ−ｐｅｅｒ）技術を応用したデータ配信方法が注目されている。
【０００３】
Ｐ２Ｐを利用したストリーミング配信方法では、例えば、データを受信した端末が、そのデータを他の端末へ転送する。この場合、各端末がそれぞれ中継装置として動作し、大規模な同報配信が実現される。この方法によれば、端末の数が増加しても、配信サーバの負荷はさほど増加することはない。
【０００４】
Ｐ２Ｐデータ配信は、物理的なネットワーク構成を意識する必要はなく、端末間の論理リンクで形成される論理ネットワーク、或いは、オーバーレイネットワーク上でのデータ配信とみなすことができる。つまり、論理的なデータ配信経路は物理的なネットワーク構成にかかわらず設定される。また、Ｐ２Ｐデータ配信においては、論理ネットワーク上の端末同士の接続方法により、物理的なネットワーク上を流れるデータトラフィック量が決まる。
【０００５】
図１乃至図４は、Ｐ２Ｐデータ配信について説明するための図である。図１に示す物理的なネットワークでは、４台の端末（ノード＃１〜＃４）がスイッチングハブ（ＳＷ）とルータを介して接続されている。図１に示す物理ネットワーク上で、図２に示すような論理ネットワークを構成した場合、図１のネットワーク上を流れるデータは矢印のようになる。なお、図１と図２における矢印に付した括弧付き数字は配信の順序を示し、互いに対応している。
【０００６】
ここで、ノードとスイッチ間，スイッチとスイッチ間，スイッチとルータ間の接続をパス（又はリンク）と呼び、例えばノード間を接続するパスの数をパス長と呼ぶ。例えば図１の（１）の矢印で表されるノード＃１〜ノード＃２間のパス長は５である。
【０００７】
データ配信のパス長がより短い手順を適切に選択すれば、データ配信の効率が高くなる。図２に示すような論理ネットワークから図４に示すような論理ネットワークを構成した場合、物理ネットワークを流れるデータの流れは図３に示すようになる。図１における（１）〜（３）の矢印のパス長（総和）が１４であるのに対し、図３における（１）〜（３）の矢印のパス長（総和）は１０に減少し、データ配信の効率が高くなる。
【０００８】
関連する技術として、特許文献１には、宅内ネットワークの構成調査を行う通信装置が記載されている。この通信装置は以下の構成を備える。ＴＴＬを変化させたルータ調査用パケットを生成し、前記ルータ調査用パケットの送信先を切替える調査用パケット作成部。前記ルータ調査用パケットに対応してルータから返信されるＩＣＭＰパケットから前記ルータのアドレスを取得する受信パケット解析部。前記受信パケット解析部から情報を取得し、前記ルータ調査用パケット作成部を制御し、ネットワークの調査を施す制御部。前記ルータ調査用パケットおよびＩＣＭＰパケットを送受信するパケット送受信部。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−３４５３４７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
物理的なネットワーク構成が既知であれば、データ配信のパス長がより短い配信の順序を適切に選択することは可能であるが、大規模な映像データの配信等で、物理的なネットワーク構成を把握することは実質的に不可能である。特に、サブネットワーク内は、レイヤ２（Ｌ２）のスイッチングハブで構成されており、一般的に使用されるレイヤ３（Ｌ３）のパス長を把握するためのｔｒａｃｅｒｏｕｔｅ等のツールを使って、データ配信のパス長がより短い配信の順序つまりデータ配信経路を適切に選択することはできないという問題があった。
【００１１】
開示の配信経路構築方法は、効率の良いデータ配信経路を構築することを目的とする。
【課題を解決するための手段】
【００１２】
開示の一実施形態による配信経路構築方法は、物理的なネットワーク構成にかかわらず論理的なデータ配信経路が設定されるデータ配信システムの配信経路構築方法において、
調査パケット送信端末からネットワーク内の複数の端末に調査パケットを送信し、前記複数の端末のそれぞれの端末からの前記調査パケットに対応する応答パケットの受信の有無を調査する調査ステップと、
調査結果に基づき、受信のある前記応答パケットの送信元の端末群を含む第１のグループと、受信のない前記応答パケットの送信元の端末群を含む第２のグループとにグループ化するグループ化ステップと、
前記第１のグループと前記第２のグループ間の配信経路の数を減少させるようにデータ通信の相手となる端末を変更する通信相手変更ステップと、
を含む。
【発明の効果】
【００１３】
本実施形態によれば、効率の良いデータ配信経路を構築することができる。
【図面の簡単な説明】
【００１４】
【図１】Ｐ２Ｐデータ配信について説明するための図である。
【図２】Ｐ２Ｐデータ配信について説明するための図である。
【図３】Ｐ２Ｐデータ配信について説明するための図である。
【図４】Ｐ２Ｐデータ配信について説明するための図である。
【図５】レイヤ２機器で接続されたネットワークの一実施形態を示す図である。
【図６】グループ化を説明するための図である。
【図７】物理的なネットワーク構成の一実施形態を示す図である。
【図８】論理的なデータ配信経路を示す図である。
【図９】端末装置の一実施形態のブロック図である。
【図１０】調査パケットの構成を示す図である。
【図１１】応答パケットの構成を示す図である。
【図１２】物理的なネットワーク構成と論理的なデータ配信経路を重ねた図である。
【図１３】配信経路構築処理の一実施形態のフローチャートを示す図である。
【図１４】配信経路構築処理の一実施形態のフローチャートを示す図である。
【図１５】応答のない端末を示す図である。
【図１６】配信経路の再構築を説明するための図である。
【図１７】配信経路の再構築を説明するための図である。
【図１８】論理的なデータ配信経路を示す図である。
【図１９】応答のない端末を示す図である。
【図２０】論理的なデータ配信経路を示す図である。
【図２１】応答のない端末を示す図である。
【図２２】論理的なデータ配信経路を示す図である。
【図２３】物理的なネットワーク構成と論理的なデータ配信経路を重ねた図である。
【図２４】グループ情報に矛盾が発生した場合の処理のフローチャートを示す図である。
【図２５】グループ情報に矛盾が発生した場合の処理のフローチャートを示す図である。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて実施形態を説明する。
【００１６】
＜第１実施形態＞
図５にレイヤ２機器で接続されたネットワークの一実施形態を示す。図５において、括弧付き数字を付した矢印がＰ２Ｐネットワークのデータの流れである配信経路を示し、弧付き数字は配信の順序を示している。
【００１７】
まず、任意の端末であるノード＃１が複数の端末へ図中に破線の矢印で示すように調査パケットを同報送信し、これを受信した各端末つまりノード＃２〜＃４はノード＃１に応答を返す。ノード＃１は応答が受信できたか否かを観測する。応答を受信できなかったノード（例えばノード＃２、＃４）が１つ以上ある場合、図６に示すように、応答を受信できたグループつまりノード＃１、＃３と、応答を受信できなかったグループつまりノード＃２、＃４とにグループ化してグループ情報として保持する。
【００１８】
応答を受信できたグループ（ノード＃１、＃３）と受信できなかったグループ（ノード＃２、＃４）の間のデータ通信量つまりパス数を減少させるように通信相手を変更する。これを繰り返しながら、Ｐ２Ｐのデータ通信経路を最適化して行く。
【００１９】
また、調査対象となる全端末から応答パケットを受信した場合には、次回に送信する調査パケットのデータ量つまりパケット数を増加させることで、輻輳による調査パケットのパケットロスを発生しやすくさせる。この際、Ｐ２Ｐネットワークを流れる実際のデータも同時にパケットロスする可能性があるが、ＦＥＣ（Ｆｏｒｗａｒｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ）やＡＲＱ（Ａｕｔｏｍａｔｉｃ  Ｒｅｐｅａｔ  ｒｅＱｕｅｓｔ）等のパケットロス訂正技術を併用することで、影響を最小限に抑えることが可能である。
【００２０】
また、グループ情報を保持する際に、同一調査パケットを受信できたグループと、受信できなかったグループが、以前に保持しているグループ情報と矛盾している場合は、調査パケットのデータ量の増加を一時停止する。例えば、図５で、ノード＃２、＃３からの応答パケットが戻って来なかった場合のグループ情報は、（ノード＃１、＃４），（ノード＃２、＃３）の形で保持される。その後、調査を進めた結果、ノード＃２、＃４からの応答パケットが戻って来なかった場合のグループ情報は、（ノード＃１、＃３），（ノード＃２、＃４）の形になり、前者のグループ情報と矛盾が発生する。この場合に調査パケットのデータ量の増加を一時停止することで、上記のどちらが正しい情報かの調査を行うことが可能になる。
【００２１】
また、グループ情報を保持する際に、同一調査パケットを受信できたグループと受信できなかったグループが、以前に保持しているグループ情報との矛盾が解消した場合は、調査パケットのデータ量の増加を再開する。例えば、上記の矛盾が発生している状況で、調査を続けた際に、ノード＃２、＃４からの応答パケットが戻ってこない頻度が高ければ、（ノード＃１、＃３），（ノード＃２、＃４）のグループ情報が正しいものと推定でき、矛盾が解消される。このため、調査パケットのデータ量の増加を再開できる。
【００２２】
グループ情報を保持する際に、調査パケットを受信できたグループと、受信できなかったグループの構成つまりグループ情報に変化がなくなる場合がある。例えば図６においてノード＃２、＃４からの応答が返って来ない状態が続く場合である。この場合、ノード＃１は調査パケットを受信できなかったグループ（ノード＃２、＃４）の中から新たな調査パケット送信する端末として例えばノード＃２を指名する。新たに指名された調査パケット送信端末であるノード＃２は、指名直前の調査パケットのデータ量から調査パケットの一斉送信を開始する。
【００２３】
＜第２実施形態＞
＜ネットワーク構成＞
図７に物理的なネットワーク構成の一実施形態を示す。図７ではサブネットワークを示している。図７において、ルータ１１は他のサブネットワークに接続されると共に、レイヤ２スイッチ（ＳＷ＃１，ＳＷ＃４）１２，１３に接続されている。スイッチ１２にはレイヤ２スイッチ（ＳＷ＃２，ＳＷ＃３）１４，１５と、ノード＃３としての端末１６が接続されている。スイッチ１４にはノード＃１，＃２としての端末１７，１８が接続されている。スイッチ１５にはノード＃４としての端末１９が接続されている。
【００２４】
スイッチ１３にはレイヤ２スイッチ（ＳＷ＃５，ＳＷ＃６）２０，２１と、ノード＃６としての端末２２が接続されている。スイッチ２０にはノード＃５としての端末２３が接続されている。スイッチ２１にはノード＃７，＃８としての端末２４，２５が接続されている。
【００２５】
図７に示すサブネットワークはＰ２Ｐの配信ネットワークを構成するものであり、例えばリアルタイムで映像データ等の配信を行うために用いられ、サブネットワーク内は全二重通信を行う。
【００２６】
図８に当初のＰ２Ｐネットワークにおける論理的なデータ配信経路を示す。括弧付き数字を付した矢印がＰ２Ｐネットワークのデータの流れである配信経路を示し、弧付き数字は経路番号を示している。この括弧付き数字を付した矢印の持つ意味は以降の図においても同様である。
【００２７】
＜端末装置の構成＞
図９にノードとしての端末装置の一実施形態のブロック図を示す。端末装置３０はハードウェア構成として、通信装置３１、ＣＰＵ３２、記憶装置３３を有する。この他に必要に応じて入力装置、二次記憶装置、出力装置などを有していても良い。
【００２８】
通信装置３１は調査パケット送信部４１，指示部４２，調査パケット送信端末指名部４３，応答パケット受信部４４，データパケット受信部４５，データパケット送信部４６として機能する。調査パケット送信部４１は全体制御部４７の制御により各端末に調査パケットを送信する。
【００２９】
指示部４２は全体制御部４７の制御により経路組み替え対象の端末に対し、接続を切替えることで経路組み替えを行わせるための指示を送信する。調査パケット送信端末指名部４３は全体制御部４７の制御により所望の端末に対し調査パケット送信端末となることを指名する情報を送信する。応答パケット受信部４４は各端末からの応答パケットを受信して全体制御部４７に供給する。データパケット受信部４５は上流ノードの端末から送信されたメディア等のデータパケットを受信する。データパケット送信部４６は下流ノードの端末にメディア等のデータパケットを送信する。
【００３０】
ＣＰＵ３２は記憶装置３３に格納されているプログラムを実行することで全体制御部４７，再生部４８として機能する。記憶装置３３はプログラムを格納すると共に、グループ情報保持部４９，バッファ部５０として機能する。
【００３１】
全体制御部４７は配信経路構築の処理プログラムを実行し、端末装置全体を制御する。再生部４８はバッファ部５０で一時バッファリングしたデータの復号や再生を行い、得られた映像信号や音声信号等を出力する。グループ情報保持部４９は頻度カウンタを含むグループ情報や最適化終了カウンタを保持する。バッファ部５０は受信したデータパケットを一時バッファリングする。
【００３２】
＜調査パケットと応答パケットの構成＞
図１０に調査パケットの構成を示す。調査パケットはＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）パケットであり、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ヘッダとＵＤＰヘッダに続いて、パケットを送信する毎につまりパケット毎に１だけインクリメントされるシーケンス番号が付与される。その後に、応答先アドレスとポート番号つまり送信元端末のアドレスポート番号が設けられている。
【００３３】
図１１に応答パケットの構成を示す。応答パケットはＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）パケットであり、ＩＰヘッダとＴＣＰヘッダに続いて、受信した調査パケットから抽出したシーケンス番号が付与される。その後に、親端末数と、前記親端末数分の親端末アドレスとポート番号が設けられている。更に、子端末数と、前記子端末数分の親端末アドレスとポート番号が設けられている。ここで、親端末とは自端末に対しデータパケットを送信した端末であり、子端末とは自端末がデータパケットを送信した端末である。応答パケットに調査パケットから抽出したシーケンス番号を付与することで、調査パケットを送信した端末において、応答パケットの抜けを検出することが可能になる。
【００３４】
映像などのデータの配信とは独立に、調査パケット送信端末からサブネットワーク内の各端末に対し調査パケットがブロードキャスト送信又はマルチキャスト送信される。サブネットワーク内の各端末は、調査パケット送信端末から定期的にＵＤＰでブロードキャスト送信又はマルチキャスト送信された調査パケットを受信した際に、ＴＣＰで送信元に応答パケットを送信する。これにより、送信側で応答パケットが戻ってこない場合に該当端末との経路の途中で輻輳が発生していると想定される。
【００３５】
調査パケット送信端末は、サブネットワーク内の論理ネットワーク構成を把握している。例えば図１１のように応答パケットに自端末の親端末（データ送信元）と子端末（データ送信先）の情報を付与することで、調査パケット送信端末で論理ネットワーク構成を把握することが可能となる。
【００３６】
＜配信経路構築処理＞
ここで、図７に示す物理的なネットワーク構成と、図８に示す当初の論理的なデータ配信経路を重ねたものを図１２に示す。図１２における矢印（１）〜（７）の配信経路のパス長の合計は３１である。
【００３７】
図１３及び図１４に配信経路構築処理の一実施形態のフローチャートを示す。この処理は調査パケット送信端末の全体制御部４７が実行する。なお、図７のサブネットワークの外部と配信経路を持つ、サブネット内の任意の端末（例えばノード＃４）を調査パケット送信端末とする。
【００３８】
図１３において、ステップＳ１で調査パケット送信端末は調査パケット毎にシーケンス番号をインクリメントして設定する。ステップＳ２で調査パケット送信端末は送信レート増加フラグがオンか否かを判別し、オンであればステップＳ３で送信レートつまり１回に送信する調査パケット数を増加する。前回の調査パケット数をｋとすると、ステップＳ３では例えば送信する調査パケット数をα倍（αは１以上の実数で、例えばα＝２）に増加する。そして、ステップＳ４で調査パケット送信端末はサブネットワーク内のノード＃１〜＃３，＃５〜＃８に調査パケットをブロードキャスト送信する。調査パケットのブロードキャスト送信を図１２に破線矢印で示す。
【００３９】
その後、ステップＳ５で調査パケット送信端末は各端末（ノード＃１〜＃８）からの応答パケットを受信し、ステップＳ６で未応答端末が存在するかどうかをチェックする。未応答パケットが存在しない場合はステップＳ８で調査パケット送信端末は送信レート増加フラグをオンにしてステップＳ１に戻る。
【００４０】
一方、未応答パケットが存在する場合ステップＳ７で調査パケット送信端末は送信レート増加フラグをオフにして図１４のステップＳ９に進み、未応答端末と応答端末をグループ化する。例えば図１５に示すように、ノード＃５〜＃８から応答が返ってこなかったとすると、図１５におけるルータ１１とスイッチ１２，１３間の経路Ｐ１，Ｐ２に含まれるパスで輻輳が発生している可能性が高いと推定されるため、応答が返ってきたノード＃１〜＃４をグループＡ、応答が返ってこなかったノード＃５〜＃８をグループＢとして調査パケット送信端末のグループ情報保持部４９に（ノード＃１、＃２、＃３、＃４），（ノード＃５、＃６、＃７、＃８）という形でグループ情報を保持する。
【００４１】
次に、ステップＳ１０で調査パケット送信端末は今回得た上記グループ情報が過去のグループ情報中に存在するかを確認する。存在しない場合はステップＳ１１で調査パケット送信端末は最適化終了カウンタをリセットする。最適化終了カウンタは、それ以上調査してもグループの細分化ができないことを判定するために用いる。
【００４２】
その後、ステップＳ１２で調査パケット送信端末は矛盾フラグがオフか否かを判別する。オフだった場合は、ステップＳ１３で調査パケット送信端末は、グループ情報保持部４９に保持されている過去のグループ情報と照らし合わせて、グループ情報に矛盾が存在するかを確認する。矛盾が存在する場合はステップＳ１４で調査パケット送信端末は矛盾フラグをオンにし、送信レート増加フラグをオフにした後ステップＳ１に戻る。矛盾については後述する。
【００４３】
一方、矛盾が存在しない場合は、ステップＳ１５で調査パケット送信端末はグループＡとＢの間の配信経路が減少するように配信経路を再構成する。ここでは、調査パケット送信端末であるノード＃４では各端末からの応答パケットによって図８に示す論理的なデータ配信経路であることが分かっているため、ノード＃１をノード＃３の下流に接続し、ノード＃６，＃７をノード＃５の下流に接続すればグループＡとＢの間の配信経路の数つまりパスを１つに減少できることが分かる。
【００４４】
このため、調査パケット送信端末であるノード＃４は図１６に示すようにノード＃１をノード＃３の下流に接続させ、次に、ノード＃４は図１７に示すようにノード＃６，＃７をノード＃５の下流に接続させるための経路組み替えの指示を指示部４２からノード＃１、ノード＃６，＃７に送信する。
【００４５】
その結果、論理ネットワークは、図１８に示す論理的なデータ配信経路となる。図８に示す物理的なネットワーク構成と、図１８に示す論理的なデータ配信経路を重ねたものを図１９に示す。図２１におけるパス長の合計は２６に減少する。
【００４６】
その後、図１４のステップＳ１６で調査パケット送信端末は送信レート増加フラグをオンにしてステップＳ１に戻る。上記ステップＳ１５の配信経路の再構築を行うことで、図１９におけるパス長の合計は２６に減少する。また、図１９における経路Ｐ１，Ｐ２のように輻輳が発生している可能性が高い経路の配信データ量が減少するため、調査パケットの送信レートを更に増加させて調査することが可能になる。
【００４７】
同様にして、図１９に示す経路Ｐ３のパスで輻輳が発生し、ノード＃７、＃８から応答が返ってこなかった場合、ノード＃７、＃８をグループＣとし、調査パケット送信端末のグループ情報保持部４９に（ノード＃１、＃２、＃３、＃４）（ノード＃５、＃６、（ノード＃７、＃８））の形でグループ情報を保持する。そして、グループＢとグループＣの間の配信経路の数が減少し１つになるようにノード＃８をノード＃７の下流に接続させて配信経路の再構築を行う。
【００４８】
この結果、論理ネットワークは、図２０に示す論理的なデータ配信経路となる。図８に示す物理的なネットワーク構成と、図２０に示す論理的なデータ配信経路を重ねたものを図２１に示す。図２１におけるパス長の合計は２４に減少する。
【００４９】
その後、図２１の状態で更に調査を進めた結果、ノード＃５〜＃８から応答が返ってこなかったとすると、図１４のステップＳ１０で過去のグループ情報と一致するためステップＳ１７に進み、グループ情報の矛盾が発生していない場合はステップＳ１７の判別で矛盾フラグはオフであるためステップＳ１８に進む。これに対し、ステップＳ１７の判別で矛盾フラグがオンの場合は矛盾発生時フロー２に進む。
【００５０】
ステップＳ１８で調査パケット送信端末は最適化終了カウンタを１だけインクリメントする。何度もノード＃５〜＃８からの応答が帰ってこないと、最適化終了カウンタが閾値に到達しステップＳ１９からステップＳ２１に進む。なお、上記の閾値は例えば１０とする。ステップＳ２１では調査パケット送信端末の候補があるか否かを判別する。なお、調査パケット送信候補は、例えばグループ情報を保持する際に、応答が返ってこないグループ内の端末を候補として保持する。
【００５１】
候補があれば、ステップＳ２２で調査パケット送信端末であるノード＃４は調査パケット送信候補の中から、図２０における応答が返ってこないグループＢの例えばノード＃６を新たな調査パケット送信端末として選出し、調査パケット送信端末指名部４３から指名の情報を送信する。なお、調査パケット送信候補からの新調査パケット送信端末の選択は、例えば、応答が返ってこないグループの中でサブグループに含まれていない端末であるノード＃５又はノード＃６から選択する方法がある。
【００５２】
ステップＳ２３で現調査パケット送信端末であるノード＃４は調査パケットの送信を止める。この際、ノード＃６に調査パケットの送信レート、最新の論理ネットワーク構成及びグループ情報を通知することで、ノード＃６側で継続してデータ配信経路を最適化することが可能になる。
【００５３】
ノード＃６より輻輳発生時の送信レートから調査パケットの送信レートを上げながら調査を進めた結果、ノード＃１、＃２から応答が返ってこなかったとすると、図２２に示すように、ノード＃１、＃２をグループＤとしてグループ情報を保持し、グループＡとＤの間の配信経路の数が１つになるように配信経路の再構築を行う。図２２ではノード＃２をノード＃１の下流に接続させて配信経路の再構築を行っている。
【００５４】
図８に示す物理的なネットワーク構成と、図２２に示す論理的なデータ配信経路を重ねたものを図２３に示す。図２３おけるパス長の合計は２３に減少する。ネットワークは全二重通信であるため、配信方向であるノード＃４からノード＃６に向かう方向と、反対方向のノード＃６からノード＃４に向かう方向との双方に調査パケットを送信することで、現在の輻輳区間とは別の新たな輻輳区間、例えば図２１の輻輳経路Ｐ４を発見できる可能性がある。
【００５５】
以上のように調査と配信経路の再構築を行うことで、パス長の合計が少なく効率の良い最適なデータ配信経路を早期に見つけることが可能となる。
【００５６】
＜グループ情報の矛盾＞
次に、グループ情報に矛盾が発生した場合の動作について、図２４及び図２５の矛盾発生時フロー１，２のフローチャートを用いて説明する。グループ情報に矛盾が発生するのは、異なるレイヤ２スイッチで同時に調査パケットのパケットロスが発生した場合などである。
【００５７】
例えば図１５において、ノード＃５〜＃８から応答が返ってこなかったとすると、応答が返ってきたノード＃１〜＃４をグループＡ、応答が返ってこなかったノード＃５〜＃８をグループＢとして、（ノード＃１、＃２、＃３、＃４）（ノード＃５、＃６、＃７、＃８）という形でグループ情報（第１グループ情報と呼ぶ）を保持する。
【００５８】
その後、図１８及び図１９のように最適化された後に調査を続けた結果、ノード＃１、＃２、＃７、＃８から応答が返ってこなかったとすると、グループ情報は（ノード＃３、＃４、＃５、＃６）（ノード＃１、＃２、＃７、＃８）という形になり（第２グループ情報と呼ぶ）、第１グループ情報と矛盾が発生することになる。この場合、図１４のステップＳ１３からステップＳ１４に進み、対象グループである第１グループ情報と第２グループ情報に対する矛盾フラグをオンとし、以降、矛盾解消のための調査を行う。
【００５９】
更にその後、例えばノード＃７、＃８から応答が返ってこなかったとすると、グループ情報は（ノード＃１、＃２、＃３、＃４、＃５、＃６）（ノード＃７、＃８）という形になり（第３グループ情報と呼ぶ）、過去のグループ情報とは異なるので図１４のステップＳ１０からステップＳ１１に進み、矛盾フラグがオンのためステップＳ１２から矛盾発生時フロー１に進む。
【００６０】
図２４の矛盾発生時フロー１において、ステップＳ１０１で調査パケット送信端末は今回得たグループ情報は該当グループ情報と統合可能であるかを判別する。ここでは、第３グループ情報は第１グループ情報と統合可能と判定され、ステップＳ１０２で調査パケット送信端末は第３グループ情報を第１グループ情報に統合し、（ノード＃１、＃２、＃３、＃４）（ノード＃５、＃６、（ノード＃７、＃８））という形にする（第４グループ情報と呼ぶ）。この際に、統合後のグループ情報（第４グループ情報）の矛盾フラグもオンにする。
【００６１】
次に、ステップＳ１０３で調査パケット送信端末は統合前の第１グループ情報と統合後の第３グループ情報の頻度カウンタをそれぞれインクリメントし、ステップＳ１０４で頻度カウンタが閾値未満か否かを判別する。頻度カウンタが閾値未満の場合はステップＳ１に戻る。なお、ステップＳ１９における閾値が例えば１０であるとすると、ステップＳ１０４における閾値は例えば５程度である。
【００６２】
頻度カウンタが閾値以上の場合、ステップＳ１０５で調査パケット送信端末は対象グループである第１〜第３グループ情報の矛盾フラグをオフとする。この後、ステップＳ１０６で調査パケット送信端末は無効なグループ情報、ここでは、第２グループ情報を削除し、ステップＳ１０７で最適化が必要か否かを判別する。最適化が必要であれば、ステップＳ１０８で配信経路の再構築を行う。ここでは、ノード＃５、＃６とノード＃７、＃８の間で配信経路の数が１つになるように最適化する。すなわち、図２０に示すようにノード＃８をノード＃７の下流に接続する。更に、ステップＳ１０９で調査パケット送信端末は送信レート増加フラグをオンにした後、ステップＳ１に戻る。
【００６３】
一方、矛盾発生時に、ノード＃５〜＃８から応答が戻ってこなかった場合、過去のグループ情報と同じであり、かつ、矛盾フラグがオンであるので図１４のステップＳ１０からステップＳ１７を経て、図２５の矛盾発生時フロー２に進む。
【００６４】
矛盾発生時フロー２では、ステップＳ２０１で調査パケット送信端末は該当グループつまり第１グループ情報の頻度カウンタをインクリメントした後、ステップＳ２０２で頻度カウンタが閾値未満か否かを判別する。頻度カウンタが閾値未満の場合はステップＳ１に戻る。なお、ステップＳ１９における閾値が例えば１０であるとすると、ステップＳ２０２における閾値は例えば５程度である。
【００６５】
頻度カウンタが閾値以上の場合、ステップＳ２０３で調査パケット送信端末は対象グループである第１，第２グループ情報の矛盾フラグをオフとする。この後、ステップＳ２０４で調査パケット送信端末は無効なグループ情報、ここでは、第２グループ情報を削除し、配信経路の最適化は既に行われているのでステップＳ２０５からステップＳ２０７に進み、送信レート増加フラグをオンにした後（Ｓ２０６）にステップＳ１に戻る。なお、ステップＳ２０５で最適化が必要であれば、ステップＳ２０６で配信経路の再構築を行う。
【００６６】
以上のように、グループ情報に矛盾が発生した際も、対象となるグループ情報の発生頻度を調査することで矛盾を解消し、配信経路の最適化を行うことが可能となる。
【００６７】
このように、本実施形態によれば、サブネットワーク内で構築されているＰ２Ｐネットワークのデータ配信経路を早期に最適化することが可能である。
（付記１）
物理的なネットワーク構成とは独立した論理的なデータ配信経路をとるデータ配信システムの配信経路構築方法において、
調査パケット送信端末からネットワーク内の複数の端末に少なくとも一つ以上の調査パケットを一斉送信し、各端末からの応答パケットの受信有無を調査する調査ステップと、
調査結果として同一調査パケットに対する応答パケットを受信できなかった端末があれば、前記同一調査パケットに対する応答パケットを受信できた端末群と、受信できなかった端末群とをグループ化し、グループ情報として保持するグループ化ステップと、
受信できたグループと受信できなかったグループ間の通信データ量を減少させるようにデータ通信の相手となる端末を変更する通信相手変更ステップと、
を有し、前記調査ステップと前記グループ情報保持ステップと前記通信相手変更ステップを繰り返して配信経路の再構築を行う
ことを特徴とする配信経路構築方法。
（付記２）
付記１記載の配信経路構築方法において、
前記調査ステップで前記調査パケットを送信した全ての端末から応答パケットを受信した場合、次回の前記調査ステップで一斉送信する調査パケット数を増加させる増加ステップを
有することを特徴とする配信経路構築方法。
（付記３）
付記２記載の配信経路構築方法において、
前記グループ化ステップは、前記同一調査パケットに対する応答パケットを受信できた端末群と、前記受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報と矛盾している場合は、前記調査パケット数の増加を停止する
ことを特徴とする配信経路構築方法。
（付記４）
付記３記載の配信経路構築方法において、
前記グループ化ステップは、前記同一調査パケットに対する応答パケットを受信できた端末群と、前記受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報との矛盾を解消した場合は、前記調査パケット数の増加を再開する
ことを特徴とする配信経路構築方法。
（付記５）
付記１乃至４のいずれか１項記載の配信経路構築方法において、
前記グループ化ステップで得られる前記グループ情報に変化がなくなった場合、前記同一調査パケットに対する応答パケットを受信できなかった端末群のいずれかの端末を新たな調査パケット送信端末に指名する指名ステップを
有することを特徴とする配信経路構築方法。
（付記６）
付記５記載の配信経路構築方法において、
前記指名ステップで新たに指名された調査パケット送信端末は、前記現在の調査パケット送信端末における一斉送信する調査パケット数を受け継いで前記調査パケットの一斉送信を行う
ことを特徴とする配信経路構築方法。
（付記７）
付記１乃至６のいずれか１項記載の配信経路構築方法において、
前記データ配信システムは、Ｐ２Ｐデータ配信を行うことを特徴とする配信経路構築方法。
（付記８）
付記１乃至７のいずれか１項記載の配信経路構築方法において、
前記調査パケットの一斉送信は、ブロードキャスト送信もしくはマルチキャスト送信であることを特徴とする配信経路構築方法。
（付記９）
物理的なネットワーク構成にかかわらず論理的なデータ配信経路が設定されるデータ配信システムの端末装置において、
調査パケット送信端末からネットワーク内の複数の端末に少なくとも一つ以上の調査パケットを一斉送信し、各端末からの応答パケットの受信有無を調査する調査手段と、
調査結果として同一調査パケットに対する応答パケットを受信できなかった端末があれば、前記同一調査パケットに対する応答パケットを受信できた端末群と、受信できなかった端末群とをグループ化し、グループ情報として保持するグループ化手段と、
受信できたグループと受信できなかったグループ間の配信経路の数を減少させるようにデータ通信の相手となる端末を変更する通信相手変更手段と、
を有することを特徴とする端末装置。
（付記１０）
付記９記載の端末装置において、
前記調査手段で前記調査パケットを送信した全ての端末から応答パケットを受信した場合、次回の前記調査ステップで一斉送信する調査パケット数を増加させる増加手段を
有することを特徴とする端末装置。
（付記１１）
付記１０記載の端末装置において、
前記グループ化手段は、前記同一調査パケットに対する応答パケットを受信できた端末群と、前記受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報と矛盾している場合は、前記調査パケット数の増加を停止する
ことを特徴とする端末装置。
（付記１２）
付記１１記載の端末装置において、
前記グループ化手段は、前記同一調査パケットに対する応答パケットを受信できた端末群と、前記受信できなかった端末群とをグループ化したグループ情報が、先に保持しているグループ情報との矛盾を解消した場合は、前記調査パケット数の増加を再開する
ことを特徴とする端末装置。
（付記１３）
付記９乃至１２のいずれか１項記載の端末装置において、
前記グループ化ステップで得られる前記グループ情報に変化がなくなった場合、前記同一調査パケットに対する応答パケットを受信できなかった端末群のいずれかの端末を新たな調査パケット送信端末に指名する指名手段を
有することを特徴とする端末装置。
（付記１４）
付記１３記載の端末装置において、
前記指名手段で新たに指名された調査パケット送信端末は、前記現在の調査パケット送信端末における一斉送信する調査パケット数を受け継いで前記調査パケットの一斉送信を行う
ことを特徴とする端末装置。
【符号の説明】
【００６８】
１１  ルータ
１２〜１５，２０，２１  スイッチ
１６〜１９，２２〜２５  端末
３０  端末装置
３１  通信装置
３２  ＣＰＵ
３３  記憶装置
４１  調査パケット送信部
４２  指示部
４３  調査パケット送信端末指名部
４４  応答パケット受信部
４５  データパケット受信部
４６  データパケット送信部
４７  全体制御部４７
４８  再生部
４９  グループ情報保持部
５０  バッファ部
【図１】
0005803656.tif 000002
【図２】
0005803656.tif 000003
【図３】
0005803656.tif 000004
【図４】
0005803656.tif 000005
【図５】
0005803656.tif 000006
【図６】
0005803656.tif 000007
【図７】
0005803656.tif 000008
【図８】
0005803656.tif 000009
【図９】
0005803656.tif 000010
【図１０】
0005803656.tif 000011
【図１１】
0005803656.tif 000012
【図１２】
0005803656.tif 000013
【図１３】
0005803656.tif 000014
【図１４】
0005803656.tif 000015
【図１５】
0005803656.tif 000016
【図１６】
0005803656.tif 000017
【図１７】
0005803656.tif 000018
【図１８】
0005803656.tif 000019
【図１９】
0005803656.tif 000020
【図２０】
0005803656.tif 000021
【図２１】
0005803656.tif 000022
【図２２】
0005803656.tif 000023
【図２３】
0005803656.tif 000024
【図２４】
0005803656.tif 000025
【図２５】
0005803656.tif 000026