(57)【特許請求の範囲】
【請求項１】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置を介してデータを同報送信するマルチキャストデータ通信システムであって、
前記複数の受信装置は、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出する手段を備え、
前記送信装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより前記受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに前記データを前記受信装置へ向けて送出する手段とを備え、
前記中継装置は、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成する手段と、前記配信表を生成した後に前記受信要求メッセージを送出してきた受信装置側隣接ノードを前記配信表に登録する手段と、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する手段とを備えたマルチキャストデータ通信システム。
【請求項２】
請求項１記載のマルチキャストデータ通信システムにおいて、前記受信要求メッセージは、前記受信装置から該受信要求メッセージを受信した前記中継装置又は前記送信装置に至る経路を示す経路情報を含み、
前記受信装置は、自身を示す情報を前記経路情報として前記受信要求メッセージに含めて送出し、
前記送信装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、
前記中継装置は、前記配信表を生成したかどうか判断する手段を備え、
前記配信表が生成されているときは、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、
前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成し該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成するマルチキャストデータ通信システム。
【請求項３】
請求項１記載のマルチキャストデータ通信システムにおいて、
前記中継装置は、前記配信表を生成したかどうか判断する手段をさらに備え、
前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送すると共に、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成して該データを廃棄し、
前記配信表が生成されているときは、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録するマルチキャストデータ通信システム。
【請求項４】
請求項２又は３記載のマルチキャストデータ通信システムにおいて、
前記中継装置は、自身が所定の負荷を越える高負荷状態であるかどうか判断する手段と、前記高付加状態であると判断されている間、前記配信表に登録されていない受信装置側隣接ノードについては、前記受信要求メッセージが受信装置側隣接ノードから送られてきたときに前記配信表への登録を行うことなく前記送信装置を宛先として該受信要求メッセージを転送する手段とをさらに具備するマルチキャストデータ通信システム。
【請求項５】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置を介してデータを同報送信するマルチキャストデータ通信方法であって、
前記複数の受信装置は、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出し、
前記中継装置は、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成し、
前記送信装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードがデータの受信を要求し続けているかどうか判断し、前記データの受信を要求し続けている受信装置側隣接ノードに対しては前記データを送出し、前記データの受信を要求し続けることを止めた受信装置側隣接ノードに対しては前記データの配送を停止し、
前記中継装置は、前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録し、
前記中継装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断し、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するマルチキャストデータ通信方法。
【請求項６】
請求項５記載のマルチキャストデータ通信方法において、前記受信装置は、自身を示す情報を経路情報として前記受信要求メッセージに含めて送出し、
前記送信装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、
前記受信装置から前記配信表の生成された中継装置に至る経路上に存在し前記配信表が生成されていない中継装置は、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成して該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、
前記受信要求メッセージが前記送信装置又は前記配信表の生成された中継装置まで到達したときに、該送信装置又は該中継装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、
前記配信表の生成された中継装置から前記受信装置に至る経路上に存在し前記配信表が生成されていない中継装置は、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに、該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成するマルチキャストデータ通信方法。
【請求項７】
請求項５記載のマルチキャストデータ通信方法において、前記受信装置から前記配信表の生成された中継装置に至る経路上に存在し前記配信表が生成されていない中継装置は、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送し、
前記受信要求メッセージが前記配信表の生成された中継装置まで到達すると、該中継装置は前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録すると共に、該受信装置側隣接ノードに前記データを送出し、
前記配信表の生成された中継装置から前記受信装置に至る経路上に存在し前記配信表が生成されていない中継装置は、送信装置側隣接ノードから送られてくる前記データを受信して前記配信表を生成すると共に該データを廃棄するマルチキャストデータ通信方法。
【請求項８】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信するマルチキャストデータ通信システムにおける中継装置であって、
前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上に設けられ、
前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信装置側隣接ノードから受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したとき、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成する手段と、
前記配信表を生成し後に前記受信要求メッセージを送出してきた受信装置側隣接ノードを前記配信表に登録する手段と、
前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、
前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する手段と
を具備する中継装置。
【請求項９】
請求項８記載の中継装置において、
前記受信要求メッセージは、前記受信装置から該受信要求メッセージを受信した前記中継装置又は前記送信装置に至る経路を示す経路情報を含み、
前記中継装置は、前記配信表を生成したかどうか判断する手段を備え、
前記配信表が生成されているときは、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信装置から自身の中継装置に至る経路を示す経路情報を前記受信要求メッセージの中から取り出して該経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、
前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成し該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成する中継装置。
【請求項１０】
請求項８記載の中継装置において、
前記配信表を生成したかどうか判断する手段を備え、
前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送すると共に、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成して該データを廃棄し、
前記配信表が生成されているときは、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録する中継装置。
【請求項１１】
請求項９又は１０記載の中継装置において、自身が所定の負荷を越える高負荷状態であるかどうか判断する手段と、前記高付加状態であると判断されている間、前記配信表に登録されていない受信装置側隣接ノードについては、前記受信要求メッセージが受信装置側隣接ノードから送られてきたときに前記配信表への登録を行うことなく前記送信装置を宛先として受信した該受信要求メッセージを転送する手段とをさらに具備する中継装置。
【請求項１２】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信するときに、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置により前記データを中継する中継方法であって、
前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信し、
受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成し、
前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録し、
前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断し、
前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する中継方法。
【請求項１３】
請求項１２記載の中継方法において、
前記配信表を生成するまでは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成して該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、その後、前記送信装置又は配信表を生成した中継装置の生成した前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに、該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成し、
前記配信表を生成した後に、受信装置側隣接ノードから前記受信要求メッセージが送られてきたときに、該受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信装置から自身の中継装置に至る経路を示す経路情報を前記受信要求メッセージから取り出して該経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出する中継方法。
【請求項１４】
請求項１２記載の中継方法において、
前記配信表を生成するまでは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送し、その後、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成すると共に該データを廃棄し、
前記配信表を生成した後は、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録すると共に、該受信装置側隣接ノードに前記データを送出する中継方法。
【請求項１５】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信する際に、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上において前記データを中継するための中継プログラムを記録したコンピュータ読み取り可能な媒体であって、
前記中継プログラムは、
前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信するステップと、
受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成するステップと、
前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録するステップと、
前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断するステップと、
前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するステップと
を具備するコンピュータ読み取り可能な媒体。
【請求項１６】
ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信する際に、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上において前記データを中継するための中継プログラムであって、
前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信するステップと、
受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成するステップと、
前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録するステップと、
前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断するステップと、
前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するステップと
をコンピュータに実行させるための中継プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、１対１通信（ユニキャスト）だけがサポートされている既存のインターネット上で複数の受信ホスト（受信装置）に対してデータを同報するマルチキャストデータ通信方法、マルチキャストデータ通信システム、中継装置、中継方法、中継プログラム、中継プログラムを記録した媒体に関する。
【０００２】
【従来の技術】
従来、インターネット上で複数の受信ホストに対してデータを同報するマルチキャスト通信を実現する方法として、予め定められたマルチキャストＩＰアドレスを用いて行う方法（ＩＰマルチキャスト）がある。この方法は、送信ホスト（送信装置）がマルチキャストＩＰアドレスを宛先としてデータを送信すると、配送途中、インターネット上に配備されたマルチキャストルータ（中継装置）がデータを適宜、コピーすることにより、全ての受信ホストまで同一のデータを届けるというものである。
【０００３】
通常、送信ホストから複数の受信ホストまでのデータ配送経路は、送信ホストを根（ルート）とし、受信ホストを葉（リーフ）とするツリーとなる。これをマルチキャストツリーという。ＩＰマルチキャストにおいて、マルチキャストツリーを構築するプロトコルとしては、ＲＦＣ１０７５のＤＶＭＲＰ（Distance-Vector Multicast Routing Protocol）や、ＲＦＣ１５８４のＭＯＳＰＦ（Multicast Open Shortest Path First）や、ＲＦＣ２３６２のＰＩＭ−ＳＭ（Protocol Independent Multicast-Sparse Mode）などがあり、各受信ホストがツリーに参加したり、離脱したりする操作を管理するためのプロトコルとして、ＲＦＣ１１１２のＩＧＭＰ（Internet Group Management Protocol）がある。
【０００４】
前述したＩＰマルチキャストを実現するためには、全てのルータがＩＰマルチキャストに対応している必要がある。しかし、大部分のルータがＩＰマルチキャストに対応していない現状において、全てのルータをＩＰマルチキャスト対応にさせるのは困難である。また、ＩＰマルチキャストでは、マルチキャストに対応していないネットワークに対してマルチキャストパケットを通過させることができないという問題もある。さらに、ＩＰマルチキャストを実現するには、受信ホストはオペレーティングシステムレベルで拡張しておく必要があり、個々のホストをＩＰマルチキャストに対応させるのは容易ではない。
【０００５】
また、上記プロトコルにはスケーラビリティが無いという欠点がある。すなわち、ＤＶＭＲＰでは受信ホストが存在しなくとも受信ホストの最寄りのルータまでマルチキャストツリーが構築されてしまいデータが配信される。ＭＯＳＰＦは各中継ノードが巨大なマルチキャストツリー全体のトポロジー情報を保持する必要がある。ＰＩＭ−ＳＭはマルチキャストツリーに参加するホストがrendezvous
pointと呼ぶ特定のノードにアクセスする必要がある。
【０００６】
さらに、上記プロトコルはマルチキャストＩＰアドレスがグローバルかつユニークであることを保証する必要があるため、マルチキャストツリーを特定するためのアドレスの管理コストがかかる。加えて、上記プロトコルではマルチキャストツリーに参加していないホストであっても送信ホストになることが可能であるため、悪意のある者がマルチキャストツリーの参加者に対して無用なトラヒックを送りつけるような攻撃を許してしまう。
【０００７】
一方、特開平１０−６３５９８号公報には、ＩＰマルチキャストを使わず、ユニキャストだけを用いたマルチキャストデータ通信方法が開示されている。この方法は、受信ホストから送信された受信開始要求を受けとったマルチキャストサーバー（中継ノード：中継装置）がその受信ホストを記憶し、以後、その受信ホストから受信終了要求を受けとるまで、マルチキャストデータをその受信ホストに配送するというものである。
【０００８】
しかし、この方法では、受信ホストからの受信終了要求が伝送途中に失われた時や受信ホストがハングアップした時は、上記受信ホストへのマルチキャストデータの配送が止まらないという問題があった。また、受信開始要求により、一度配送経路が確定すると、ルータの経路情報の変化により、受信ホストに対し最寄りの中継ノードが変わった場合でも、その受信ホストに配送する経路は変わらないという問題があった。
【０００９】
図７１はマルチキャスト通信が行われるネットワーク構成の一例を示すもので、ここでは１つの中継ノード１に４つの受信ホスト２−１，２−２，２−３，２−４がネットワークを介して接続されている状態を示している。
【００１０】
今、ある送信ホスト（図示せず）がネットワークを介して中継ノード１に接続されていると仮定する。10.10.9.8，10.11.10.9，10.12.11.10，10.13.12.11のアドレスを持つ４つの受信ホスト２−１，２−２，２−３，２−４が中継ノード１に対して送信ホストと反対側にあるものとする。
【００１１】
これらの４つの受信ホスト２−１〜２−４のうち、10.10.9.8，10.11.10.9，10.12.11.10をアドレスに持つ３つの受信ホスト２−１〜２−３が受信要求パケットを送信したとする。これらが中継ノード１に到達した時、中継ノード１には上記送信ホストに対するテーブルが作られ、このテーブルにこれら３つの受信ホスト２−１〜２−３が登録される。
【００１２】
このテーブルは、中継ノード１が送信ホストからのデータパケットを複製し、これら３つの受信ホストに対して配送すべきことを表す。テーブルに登録されたホストを中継ノード１の子という。
【００１３】
このテーブルの一例を図７２に示す。このテーブルには、各子のアドレスが記録されている。
【００１４】
新たにテーブルが作られると、中継ノード１自体が受信要求パケットを送信する。ここで、受信要求パケットを送信ホストの近接ノードまで伝搬させるために、何らかの手段によってルーティングツリーがマルチキャスト識別子毎に決定される。このようにして、やがて受信要求パケットは送信ホストまで到着する。
【００１５】
図７３はマルチキャスト通信が行われているネットワーク構成の他の例を示すもので、ここでは３つの中継ノード１１−１，１１−２，１１−３に７つの受信ホスト（以下、クライアントと呼ぶ）１２−１，１２−２，１２−３，１２−４，１２−５，１２−６，１２−７及び１つの送信ホスト１３（以下、サーバーと呼ぶ）がネットワークを介して接続されている状態を示している。
【００１６】
以下、マルチキャストツリーの構成過程を説明する。
【００１７】
今、図７４に示すように、クライアント１２−１が受信要求パケットを送出したとする。この時、中継ノード１１−１には、クライアント１２−１が子であることを示すテーブルが作られ、さらに図７５に示すように、中継ノード１１−１から受信要求パケットが送出される。
【００１８】
受信要求パケットが中継ノード１１−２に到着すると、中継ノード１１−２でも同じようにテーブルが生成され、中継ノード１１−１が登録される。その後、中継ノード１１−２から受信要求パケットが送出される。この受信要求パケットがサーバー１３に到着することによって、サーバー１３はデータを中継ノード１１−２に送出すべきことを知り、データパケットの送出を始める。
【００１９】
その後、図７６に示すように、クライアント１２−２から受信要求パケットが送出されたとする。この受信要求パケットが中継ノード１１−１に到着すると、既にテーブルがあるので、そこにクライアント１２−２が登録される。さらにクライアント１２−４が受信要求パケットを送出すると、図７７及び図７８に示すように、中継ノード１１−３にはクライアント１２−４が登録され、中継ノード１１−２には中継ノード１１−３が登録される。さらにクライアント１２−５及び１２−６がマルチキャストに参加した時の様子を図７９に示す。
【００２０】
このように、サーバーをルートとし、クライアントをリーフとする、ツリー状の配送経路が出来る。このようなツリー状配送経路はサーバー毎に作られる。このツリーを、ツリーＩＤ（マルチキャスト識別子）という記号で区別することにすると、図７２に示すように、中継ノードではこのツリーＩＤ毎にテーブルが作成される。
【００２１】
各中継ノードでは、サーバーから送出されたデータパケットが、必要であれば複製された後、テーブルに登録されている子に対して送出される。このため、クライアントからサーバーに向かう経路と、サーバーからクライアントに向かう経路とが異なる場合においても、データパケットは常にテーブルが作られた中継ノードを通過することになる。
【００２２】
これらのクライアントがデータパケットの受信をやめる時は、離脱パケットを送出し、それが中継ノードに到着した時、離脱パケットを送出したホストをテーブルから抹消すれば良い。そして、テーブルに登録されている子がなくなった時、その中継ノードが離脱パケットを送出する。ここで、受信要求パケットと同様、離脱パケットも送信ホストの近接ノードまで何らかの方法で伝搬される。このように、各中継ノードが同様な処理を繰り返せば良いことは、特開平１０−６３５９８号公報に記述されている。
【００２３】
【発明が解決しようとする課題】
しかし、前述した通信方法では、クライアントがハングアップした時や離脱パケットを出さずに強制終了した場合、中継ノードのテーブルにこのクライアントが登録されたままになり、サーバーからのデータパケットがこのクライアントに対して送出され続けるという問題がある。
【００２４】
これを防ぐには、中継ノードにタイマーをしかけておき、定期的にテーブルに登録された子に対して問い合わせを行い、子から返答パケットが返ってきた場合は受信をしていると見なしてデータパケットの送信を続け、そうでない場合は送出をやめるという方法が考えられる。
【００２５】
中継ノードに対して親ノードから問い合わせがきた場合は、テーブル内に子が登録されていれば返答パケットを送出し、テーブル内に子が一つも登録されていなければ返答パケットを送出しないか、離脱パケットを親ノードに対して送出する。このようにすることによって、返答パケットを返すクライアントだけにデータパケットを配送するために必要なツリーが維持される。
【００２６】
例えば、図７１に示したネットワーク構成において、中継ノード１は、図７２に示すようにテーブルに登録されている、アドレス10.10.9.8，10.11.10.9，10.12.11.10の３つの子（受信ホスト）に問い合わせをする。アドレス10.10.9.8及び10.11.10.9の子は正常に動作しているので返答パケットを返したが、アドレス10.12.11.10の子はハングアップしていたため、返答パケットを返さなかったとする。この時、アドレス10.12.11.10の子には、データパケットを配送する必要はないと判断し、図８１に示すように、テーブルから削除する。
【００２７】
また、データパケットと問い合わせパケットを別々に送出するのではなく、データパケットを問い合わせパケットと見なし、クライアント（または中継ノード）は、データパケットを受けとると、サーバー宛に返答パケットを返すようにすることにしても良い。
【００２８】
しかし、これらの方法を採用しても、受信開始時にクライアント（または中継ノード）が親ノードのテーブルに登録されるためには、クライアント（または中継ノード）から受信要求パケットを出す必要がある。受信要求パケットが失われる可能性のあるネットワークの場合、親ノードのテーブルに登録されるまで受信要求パケットを繰り返し出す必要がある。そして、親ノードのテーブルに登録後、データパケットに対し、返答パケットを送ることになる。つまり、能動的にパケットを出す状態から受動的にパケットを出す状態への状態遷移が必要となるという問題があった。
【００２９】
以上述べた特開平１０−６３５９８号公報に類似する技術として、Hugh. W. Holbrook, David R. Cheriton, “IP Multicast Channels: EXPRESS Support for Large-scale Single-source Applications”, pp. 65-78, In Proc. of SIGCOMM, 1999や、Ion Stoica, T.S. Eugene Ng, Hui Zhang, “REUNITE: A Recursive Unicast Approach to Multicast”, pp. 1644-1653,In Proc. of INFOCOM2000（以下、REUNITEと言う）がある。
【００３０】
前者はＩＰマルチキャストの拡張であってSource-specific multicast（SSM）と呼ばれており、送信元アドレスとマルチキャストアドレスの組によってマルチキャストツリーを特定している。また、文献REUNITEはアプリケーション層におけるマルチキャスト技術であって、一番最初に要求を出した受信ホストへのforward-pathに基づいてマルチキャストツリーが決定される。その後にこの受信ホストがマルチキャストツリーから離脱すると、別の受信ホストへのforward-pathに基づくマルチキャストツリーが決定されて、マルチキャストツリーの構成を変えるようになっている。
【００３１】
しかしながら、特開平１０−６３５９８号公報，文献SSM，文献REUNITEには次のようなセキュリティ上の問題がある。すなわち、送信ホスト又は受信ホストが、テーブル作成機能を持つパケット（例えば上述した受信要求パケット）を適当な端末アドレスに宛てて送出することで、ホストから宛先に至るパス上に存在する各ノードにテーブルを作成することが可能となる。この性質を利用することにより、悪意のあるユーザが多数のアドレス宛てにテーブル生成パケットを送出すると、無意味なテーブルがネットワーク内のノードに多数生成されてしまう。その結果、ノードの負荷が不必要に重くなってその性能を低下させてしまうという問題がある。
【００３２】
本発明の目的は、悪意のあるユーザによる攻撃によって無意味なテーブルがネットワーク内のノードに多数生成されて負荷が重くなるといった問題を生じず高度なセキュリティを実現できるマルチキャストデータ通信方法、マルチキャストデータ通信システム、中継装置、中継方法、中継プログラム、中継プログラムを記録した媒体を提供することにある。
【００３３】
本発明の目的は、受信ホストが故障したり、伝送路でパケットロスが発生した場合にマルチキャストデータの配送を停止可能なマルチキャストデータ通信方法、マルチキャストデータ通信システム、中継装置、中継方法、中継プログラム、中継プログラムを記録した媒体を提供することにある。
【００３４】
また、本発明の目的は、受信ホストに対する最寄りの中継ノードが変化したり、中継ノードの負荷状態が変化した場合、マルチキャストデータの配送経路を変更可能なマルチキャストデータ通信方法、マルチキャストデータ通信システム、中継装置、中継方法、中継プログラム、中継プログラムを記録した媒体を提供することにある。
【００３５】
さらにまた、本発明の目的は、受信ホストにおいて能動的にパケットを出す状態から受動的にパケットを出す状態への状態遷移が不要なマルチキャストデータ通信方法、マルチキャストデータ通信システム、中継装置、中継方法、中継プログラム、中継プログラムを記録した媒体を提供することにある。
【００３６】
本発明の他の目的は、明細書、図面、特に特許請求の範囲の各請求項の記載から自ずと明らかとなろう。
【００３７】
【課題を解決するための手段】
本発明では、前記目的を達成するため、受信ホストは受信要求を定期的に発行し、送信ホストまたは中継ノードは予め定めた時間間隔内に受信要求がこない受信ホストに対するマルチキャストデータの配送を停止させる方法（以下、Keep alive方式と呼ぶ）を用いる。
【００３８】
具体的には、請求項１記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置を介してデータを同報送信するマルチキャストデータ通信システムであって、前記複数の受信装置は、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出する手段を備え、前記送信装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより前記受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに前記データを前記受信装置へ向けて送出する手段とを備え、前記中継装置は、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成する手段と、前記配信表を生成した後に前記受信要求メッセージを送出してきた受信装置側隣接ノードを前記配信表に登録する手段と、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する手段とを備えたマルチキャストデータ通信システムである。
【００３９】
また、請求項２記載の発明は、請求項１記載のマルチキャストデータ通信システムにおいて、前記受信要求メッセージは、前記受信装置から該受信要求メッセージを受信した前記中継装置又は前記送信装置に至る経路を示す経路情報を含み、前記受信装置は、自身を示す情報を前記経路情報として前記受信要求メッセージに含めて送出し、前記送信装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、前記中継装置は、前記配信表を生成したかどうか判断する手段を備え、前記配信表が生成されているときは、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成し該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成するマルチキャストデータ通信システムである。
【００４０】
また、請求項３記載の発明は、請求項１記載のマルチキャストデータ通信システムにおいて、前記中継装置は、前記配信表を生成したかどうか判断する手段をさらに備え、前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送すると共に、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成して該データを廃棄し、前記配信表が生成されているときは、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録するマルチキャストデータ通信システムである。
また、請求項４記載の発明は、請求項２又は３記載のマルチキャストデータ通信システムにおいて、前記中継装置は、自身が所定の負荷を越える高負荷状態であるかどうか判断する手段と、前記高付加状態であると判断されている間、前記配信表に登録されていない受信装置側隣接ノードについては、前記受信要求メッセージが受信装置側隣接ノードから送られてきたときに前記配信表への登録を行うことなく前記送信装置を宛先として該受信要求メッセージを転送する手段とをさらに具備するマルチキャストデータ通信システムである。
【００４２】
また、請求項５記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置を介してデータを同報送信するマルチキャストデータ通信方法であって、前記複数の受信装置は、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出し、前記中継装置は、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成し、前記送信装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードがデータの受信を要求し続けているかどうか判断し、前記データの受信を要求し続けている受信装置側隣接ノードに対しては前記データを送出し、前記データの受信を要求し続けることを止めた受信装置側隣接ノードに対しては前記データの配送を停止し、前記中継装置は、前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録し、前記中継装置は、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断し、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するマルチキャストデータ通信方法である。
【００４３】
また、請求項６記載の発明は、請求項５記載のマルチキャストデータ通信方法において、前記受信装置は、自身を示す情報を経路情報として前記受信要求メッセージに含めて送出し、前記送信装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、前記受信装置から前記配信表の生成された中継装置に至る経路上に存在し前記配信表が生成されていない中継装置は、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成して該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、前記受信要求メッセージが前記送信装置又は前記配信表の生成された中継装置まで到達したときに、該送信装置又は該中継装置は、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信要求メッセージ中の経路情報を含む配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、前記配信表の生成された中継装置から前記受信装置に至る経路上に存在し前記配信表が生成されていない中継装置は、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに、該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成するマルチキャストデータ通信方法である。
【００４４】
また、請求項７記載の発明は、請求項５記載のマルチキャストデータ通信方法において、前記受信装置から前記配信表の生成された中継装置に至る経路上に存在し前記配信表が生成されていない中継装置は、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送し、前記受信要求メッセージが前記配信表の生成された中継装置まで到達すると、該中継装置は前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録すると共に、該受信装置側隣接ノードに前記データを送出し、前記配信表の生成された中継装置から前記受信装置に至る経路上に存在し前記配信表が生成されていない中継装置は、送信装置側隣接ノードから送られてくる前記データを受信して前記配信表を生成すると共に該データを廃棄するマルチキャストデータ通信方法である。
また、請求項８記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信するマルチキャストデータ通信システムにおける中継装置であって、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上に設けられ、前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信装置側隣接ノードから受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したとき、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成する手段と、前記配信表を生成し後に前記受信要求メッセージを送出してきた受信装置側隣接ノードを前記配信表に登録する手段と、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断する手段と、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する手段とを具備する中継装置である。
【００４５】
また、請求項９記載の発明は、請求項８記載の中継装置において、前記受信要求メッセージは、前記受信装置から該受信要求メッセージを受信した前記中継装置又は前記送信装置に至る経路を示す経路情報を含み、前記中継装置は、前記配信表を生成したかどうか判断する手段を備え、前記配信表が生成されているときは、前記受信要求メッセージを送出してきた受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信装置から自身の中継装置に至る経路を示す経路情報を前記受信要求メッセージの中から取り出して該経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出し、前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成し該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成する中継装置である。
また、請求項１０記載の発明は、請求項８記載の中継装置において、前記配信表を生成したかどうか判断する手段を備え、前記配信表が生成されていないときは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送すると共に、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成して該データを廃棄し、前記配信表が生成されているときは、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録する中継装置である。
【００４６】
また、請求項１１記載の発明は、請求項９又は１０記載の中継装置において、自身が所定の負荷を越える高負荷状態であるかどうか判断する手段と、前記高付加状態であると判断されている間、前記配信表に登録されていない受信装置側隣接ノードについては、前記受信要求メッセージが受信装置側隣接ノードから送られてきたときに前記配信表への登録を行うことなく前記送信装置を宛先として受信した該受信要求メッセージを転送する手段とをさらに具備する中継装置である。
【００４７】
また、請求項１２記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信するときに、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上に設けられた中継装置により前記データを中継する中継方法であって、前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信し、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成し、前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録し、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断し、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送する中継方法である。
【００４８】
また、請求項１３記載の発明は、請求項１２記載の中継方法において、前記配信表を生成するまでは、受信装置側隣接ノードから送られてくる前記受信要求メッセージ中の経路情報に対して自身を示す情報を追加した新たな経路情報を生成して該新たな経路情報を含めた受信要求メッセージを前記送信装置を宛先として送出し、その後、前記送信装置又は配信表を生成した中継装置の生成した前記配信表生成パケットが送信装置側隣接ノードから送られてきたときに、該配信表生成パケット中の経路情報に従って該配信表生成パケットを受信装置側隣接ノードへ転送すると共に前記配信表を生成し、前記配信表を生成した後に、受信装置側隣接ノードから前記受信要求メッセージが送られてきたときに、該受信装置側隣接ノードが前記配信表に登録されていなければ、前記受信装置から自身の中継装置に至る経路を示す経路情報を前記受信要求メッセージから取り出して該経路情報を含む前記配信表生成パケットを生成し、該経路情報に従って前記配信表生成パケットを前記受信装置へ向けて送出する中継方法である。
【００４９】
また、請求項１４記載の発明は、請求項１２記載の中継方法において、前記配信表を生成するまでは、受信装置側隣接ノードから送られてくる前記受信要求メッセージの送信元を自身の中継装置に変更して送信装置側隣接ノードへ転送し、その後、送信装置側隣接ノードから前記データが送られてきたときに前記配信表を生成すると共に該データを廃棄し、前記配信表を生成した後は、前記受信要求メッセージを送出してきた送信元の受信装置側隣接ノードを前記配信表に登録すると共に、該受信装置側隣接ノードに前記データを送出する中継方法である。
【００５０】
また、請求項１５記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信する際に、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上において前記データを中継するための中継プログラムを記録したコンピュータ読み取り可能な媒体であって、前記中継プログラムは、前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信するステップと、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成するステップと、前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録するステップと、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断するステップと、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するステップとを具備するコンピュータ読み取り可能な媒体である。
【００５１】
また、請求項１６記載の発明は、ユニキャスト通信が可能なネットワークを用い、送信装置から複数の受信装置にデータを同報送信する際に、前記送信装置から前記複数の受信装置に至るユニキャスト配送経路上において前記データを中継するための中継プログラムであって、前記複数の受信装置が予め決められた値より小さい時間間隔毎に前記送信装置を宛先として送出する受信要求メッセージを受信するステップと、受信装置側隣接ノードから前記受信要求メッセージを受信した後に送信装置側隣接ノードから前記データ又は配信表生成パケットを受信したときに、前記データを配送すべき受信装置側隣接ノードを登録するための配信表を生成するステップと、前記配信表が生成された後に前記受信要求メッセージを送出してきた前記受信装置側隣接ノードを前記配信表に登録するステップと、前記受信要求メッセージの受信間隔が予め決められた時間間隔未満であるかどうかにより受信装置側隣接ノードが前記データの受信を要求し続けているかどうか判断するステップと、前記受信装置側隣接ノードが前記データの受信を要求し続けていると判断したときに、予め決められた値より小さい時間間隔毎に前記送信装置を宛先とした受信要求メッセージを送出すると共に、送信装置側隣接ノードから送られてくる前記データを複製して前記配信表に登録されている受信装置側隣接ノードへ配送するステップとをコンピュータに実行させるための中継プログラムである。
【００５２】
【発明の実施の形態】
以下、図面に従って本発明の実施の形態を説明する。
【００５３】
初めに、本発明の各実施の形態が適用される領域についてその一例を説明するが、本発明がこうした領域への適用に限定されるものではない。本発明の各実施の形態は、例えば広域網における大衆向けの個人放送局型ストリーム配信に適用することが好ましい。ここで言う個人放送局型ストリーム配信とは、個人の持つ端末がストリームの発信元となるストリーム配信の一形態を意味する。個人が持つ端末は固定端末あるいは移動端末のいずれであっても良いが、移動端末とした場合にはストリームの発信元が時々刻々変わってくる。また、個人放送局型ストリーム配信ではストリームの発信期間が比較的短い場合が多いことが考えられる。こうした個人放送局型ストリーム配信の特質から、マルチキャストツリーを予め計画的に構築しておくことは難しいと言える。
【００５４】
そして、以上のような適用領域を考慮に入れたマルチキャスト通信を実現するためには以下のような要求を満たす必要がある。まず、送信者及び受信者の双方がマス（一般ユーザ）であるため、セキュリティ上の観点から高度な安全性を保証することの可能なプロトコルが必要となってくる。また、ストリームがどこから配信されるのか予想することができないため、オンデマンドでマルチキャストツリーを構築可能であることが必要となってくる。また、ストリームが配信される受信者の数などに対してスケーラビリティを確保するために非集中制御が必要となってくる。また、広域網への適用を考慮すると経路変更などに対して柔軟に対応できる必要がある。
【００５５】
〔実施の形態１〕
図１はマルチキャスト通信が行われるネットワーク構成の一例、ここでは従来例で取り上げた図７１と同様な例について示す。即ち、ここでは１つの中継ノード２１に４つの受信ホスト２２−１，２２−２，２２−３，２２−４（アドレスは図７１のものと同一とする）がネットワークを介して接続され、送信ホスト（図示せず）もネットワークを介して中継ノード２１に接続されているものとする。
【００５６】
各受信ホスト２２−１〜２２−４は、予め決められた値より小さい時間間隔毎に受信要求パケットを送出する。受信要求パケットが中継ノード２１に到着すると、その到着時刻が中継ノード２１のテーブル（以下、配信テーブルという）に記録される。子が登録されている中継ノード２１自身も、予め決められた値より小さい時間間隔毎に受信要求パケットを送信ホストに向かって送出する。より送信ホストに近い中継ノードにこの受信要求パケットが到着すると、到着時刻が記録される。中継ノード自身が受信要求パケットを送信ホストに向かって送出するタイミングについては後述する。
【００５７】
図２は本実施の形態の配信テーブルの一例を示すもので、各子のアドレスと各子からの受信要求パケットが中継ノード２１に到着した時刻が子毎に記録されている。
【００５８】
送信ホストからのデータパケットがこの中継ノード２１に到着した時、現在時刻と、配信テーブルに記録された各子毎の受信要求パケット到着時刻とを比較し、その間隔がある値以上である子はタイムアウトしたと見なし、その子に対してはデータパケットを送出しない。この時、配信テーブルからこの子を削除する。
【００５９】
例えば、図３は、中継ノード２１に送信ホストからのデータパケットが時刻１０：２３：１１に到着した時のようすを示すものである。タイムアウト時間間隔が００：００：１０であったとすると、図２より、子３だけがタイムアウトしていることになる。従って、このデータパケットは、図４に示すように、子１及び子２（受信ホスト２２−１，２２−２）に対してだけ送出される。また、この時、子３は配信テーブルから削除される。子３が削除された後の配信テーブルは、図５に示すようになる。
【００６０】
全ての子がタイムアウトしていた場合には、配信テーブル自体を削除する。配信テーブルに登録された子や配信テーブル自体を削除するための他の方法も考えられる。例えば、受信要求パケットが到着した時に、その受信要求パケットが対応するツリーＩＤの配信テーブルについて、タイムアウトした子の削除操作を行えば、データパケット転送時の処理量を減らすことが出来る。これは、リアルタイムストリームデータなど、転送レートが重要な場合は有益である。また、タイムアウトした子や配信テーブルが、より確実に削除されるようにするには、中継ノード自体に、タイムアウトした子や配信テーブルを削除するプログラムを定期的に起動する仕組みを作っておく方法もある。
【００６１】
Keep alive方式は、受信ホスト（以下クライアントとも言う）のハングアップや強制終了に対する耐性を高めるばかりでなく、中継ノードの負荷状況に応じて、動的にツリーを再構築することを可能にする。
【００６２】
図６はマルチキャスト通信が行われるネットワーク構成の他の例、ここでは従来例で取り上げた図７３と同様な例について示す。即ち、ここでは３つの中継ノード３１−１，３１−２，３１−３に７つの受信ホスト３２−１，３２−２，３２−３，３２−４，３２−５，３２−６，３２−７及び１つの送信ホスト３３（以下、サーバーと呼ぶ）がネットワークを介して接続されている状態を示している。
【００６３】
図７は図６の構成において、図７９と同様な状態、即ちクライアント３２−１，３２−２，３２−４，３２−５，３２−６がマルチキャストに参加している状態から、さらにクライアント３２−７が新たに受信要求パケットを送出してきた状態を示している。ここで、中継ノード３１−３は既に高負荷状態になっており、クライアント３２−７のためにデータパケットを複製する回数を増やす余裕がないものとする。
【００６４】
この時、中継ノード３１−３はクライアント３２−７からの受信要求パケットをそのままサーバー３３に向かって転送する。中継ノード３１−２にクライアント３２−７からの受信要求パケットが到着した時、中継ノード３１−２が高負荷状態でなければ、当該中継ノード３１−２の配信テーブルに子として登録される。この結果、サーバー３３からのデータパケットは、中継ノード３１−２でクライアント３２−７のために複製され、ユニキャストで直接クライアント３２−７に送られる。
【００６５】
クライアント３２−７からの受信要求パケットは、予め決められた値以下の時間間隔で送出され続けられるので、その度毎に中継ノード３１−３で転送され、中継ノード３１−２では配信テーブルの受信要求パケット到着時刻が更新される。
【００６６】
次に、図８に示すように、クライアント３２−５が離脱パケットもしくはタイムアウトにより中継ノード３１−３の配信テーブルから削除され、中継ノード３１−３の負荷が下がり、この結果、中継ノード３１−３は新たに子を増やすことが可能になったものとする。この時、中継ノード３１−３にクライアント３２−７の受信要求パケットが到着すると、中継ノード３１−３はこの受信要求パケットを中継ノード３１−２へ転送せずにクライアント３２−７を配信テーブルに登録する。この様子を、図９に示す。
【００６７】
この結果、中継ノード３１−３からクライアント３２−７へデータパケットが送られることになる。以後、中継ノード３１−２にはクライアント３２−７からの受信要求パケットが届かなくなるので、中継ノード３１−２の配信テーブルでクライアント３２−７はタイムアウトし、中継ノード３１−２からクライアント３２−７へはデータパケットが送られなくなる。
【００６８】
この際、中継ノード３１−２でタイムアウトするまでの間、クライアント３２−７宛に、中継ノード３１−２及び３１−３から同じデータパケットが送られることになる。これに関しては予めデータパケットに番号を付けておき、その番号に基づいて中継ノード３１−３で重複したパケットを廃棄し、クライアント３２−７に対して同じパケットを複数送ることを防げば良い。また、クライアント３２−７においても、同じパケットが複数届いた時は廃棄するようにしておけば良い。
【００６９】
データパケットの番号付けに関しては、ＲＦＣ１８８９のReal-Time Transport Protocol（ＲＴＰ）のように、タイムスタンプとシーケンス番号の組で表しても良い。
【００７０】
以上のようにすることで、中継ノードの負荷状態に応じてマルチキャストツリーの構成を自律的に変更することが可能となって負荷分散を図ることができる。
【００７１】
Keep alive方式は、クライアントやサーバーが移動端末の場合も有用である。例えば、クライアントが移動端末である場合、クライアントが移動することにより、これまで収容されていた中継ノードの収容範囲の外に出た場合、このクライアントは異なる中継ノードに収容されることになる。このような場合でも、クライアントは受信要求パケットを出し続けることによって、新しく収容される中継ノードに登録され、また、これまで収容されていた中継ノードではタイムアウトする。このように、クライアントは収容される中継ノードを意識することなくサーバー３３からのデータパケットを受信し続けることが出来る。
【００７２】
逆に、サーバー３３が移動体である場合、mobile IP等の移動体宛のユニキャストを可能にする仕組みがあれば、サーバー３３宛に送出された受信要求パケットは常にサーバー３３が実際に存在する位置に送られる。サーバー３３が移動することにより、異なる中継ノードに収容されることになった場合、各クライアントからサーバーに至る経路上の中継ノードに配信テーブルが存在しない時にのみ、新たに配信テーブルが作られることになる。
【００７３】
例えば、図１０に示すように、これまで中継ノード３１−２に収容されていたサーバー３３が移動し、中継ノード３１−４に収容されるようになったものとする。
【００７４】
この時、任意のクライアントからサーバー３３へ至るパス上に、サーバー３３の移動前及び移動後において共通に存在する中継ノード３１−１及び３１−３の配信テーブルは変化せず、新たに上記パスに加わった中継ノード３１−４に配信テーブルが生成され、中継ノード３１−１及び３１−３が登録される。そして、中継ノード３１−４はサーバー３３に対して受信要求パケットを送出する。
【００７５】
各クライアントからサーバー３３に至るパスを外れた中継ノード３１−２には受信要求パケットが送られなくなるので、タイムアウトする。この結果、最終的に、図１１に示すような形態になる。
【００７６】
中継ノード３１−２がタイムアウトするまでの間に、中継ノード３１−１及び３１−３には、中継ノード３１−４及び３１−２を経由してデータパケットが届く可能性があり、この場合、同じデータパケットが重複して届くことになる。これに対しては、上記と同様に、シーケンス番号をデータパケットに付加しておくことにより、中継ノードまたはクライアントで、同じパケットが複数届いた時は廃棄するようにしておけば良い。
【００７７】
Keep alive方式において、タイムアウトしていない子を持つ中継ノードは、よりサーバーに近い中継ノードの子としてタイムアウトしないようにしなければならない。最も簡単な方法は、タイマーによる割り込みを利用する方法である。中継ノード自身にタイマーをしかけておき、決められた時間間隔毎に配信テーブルの各子がタイムアウトしているかどうかチェックしにいく。その結果、一つでもタイムアウトしていない子があれば、サーバーに向かって受信要求パケットを送出する。
【００７８】
しかし、この方法では、データパケットや受信要求パケットの処理の途中で、タイマー割り込みが入る可能性があり、場合によってはそのオーバーヘッドが深刻になることが考えられる。
【００７９】
タイマー割り込みを使わない方法としては、受信要求パケットの到着時の処理の一部として実現する方法である。
【００８０】
例えば、クライアントは、時間間隔Ｄ毎に受信要求パケットを送出するものとする。中継ノードは、サーバーに向かって最後に受信要求パケットを送出した時刻Ｔを記録しておく。受信要求パケットが到着した時、送信元がまだ配信テーブルに登録されていなければ登録した上で、現在時刻と前記時刻Ｔとを比較し、（現在時刻−Ｔ）≧Ｄならば、サーバーに向けて受信要求パケットを送出し、時刻Ｔに現在時刻を設定する。
【００８１】
クライアントから中継ノード（またはサーバー）までのリンクの数の最大値をその中継ノード（またはサーバー）の高さと呼ぶことにすると、中継ノード間またはクライアントと中継ノードとの間の伝送遅延にゆらぎがない場合、上記の方法によれば、高さｈの中継ノード（またはサーバー）に受信要求パケットが到着する時間間隔は、高々ｈ×Ｄである。この理由は次のように、帰納的に示すことが出来る。
【００８２】
ある中継ノードが子から受けとる受信要求パケットの（子毎に測定した場合の）到着間隔が高々Ｄ’であると仮定する。この時、上記の方法によれば、この中継ノードから受信要求パケットを送出する間隔が最大になるのは、前に受信要求パケットを送出し、それから時間Ｄが経過する直前に、ある子からの受信要求パケットが到着し、同じ子から次の受信要求パケットが到着するまで、（離脱やハングアップ等の理由により）他の子からの受信パケットが到着しない場合である。
【００８３】
この場合、結局、前に受信要求パケットを送出してから次に送出するまではＤ＋Ｄ’の時間が経過している。また、子が全てクライアントであるような中継ノードはＤ’がＤに等しい。
【００８４】
中継ノード間またはクライアントと中継ノードとの間の伝送遅延にゆらぎがある場合、伝送遅延の増加・減少の量の絶対値（ゆらぎ）をαとすると、子が全てクライアントであるような中継ノードに到着する受信要求パケットの到着時間間隔は、高々Ｄ＋２αになる。よって、上記と同様な理由により、高さｈの中継ノード（またはサーバー）に受信要求パケットが到着する時間間隔は、高々ｈ×（Ｄ＋２α）ということになる。
【００８５】
高さｈの中継ノード（またはサーバー）では、各子について、その子の高さをｈ−１とすると、前回、その子から受信要求パケットを受信してから、ｈ×（Ｄ＋２α）を越える時間が経過している場合はタイムアウトしたと判断すれば良い。さらに、中継ノードの処理遅延のゆらぎがある場合は、伝送遅延と処理遅延の揺らぎとの和をαとして考えれば良い。
【００８６】
但し、パケットが伝送途中で失われ得る場合、クライアントが受信要求パケットを送出し続けている場合でも、高さｈの中継ノード（またはサーバー）では、ｈ×（Ｄ＋２α）を越える時間間隔で受信要求パケットが到着する可能性がある。その場合、タイムアウトを判断する時間間隔を適宜延ばす必要がある。以下では、パケットが伝送途中で失われることがないと仮定する。
【００８７】
使用するネットワークから、ｈの値の上限Ｈが予めわかっている場合は、全ての中継ノードにおいてＨ×（Ｄ＋２α）をタイムアウトを判断するための値として用いれば良い。
【００８８】
ｈの値の上限Ｈが予めわからない場合、ｈを知るためには、例えば受信要求パケットを利用する方法が考えられる。受信要求パケットには、高さを表す変数ｈを用意しておく。クライアントはｈ＝０として、受信要求パケットを送出する。中継ノードでは、各子から受けとった受信要求パケットに含まれる変数ｈの最大値に１を足した値をｈの値として、受信要求パケットを送出する。このようにすることによって、中継ノードが、ある子から受けとった受信要求パケットのｈの値がｈ*であったとすると、その子は高さｈ*であることがわかる。このように、タイムアウトすべき時間間隔を、ツリーの形状に従って動的に変化させることが出来る。
【００８９】
受信要求パケット到着時の中継ノードでの処理フローを図１２に示す。但し、受信要求パケットに含まれる、ツリーＩＤとソース（送信元）アドレスをそれぞれＮ及びＳとする。図１２中の高負荷時の処理は図１３に示す。
【００９０】
また、データパケット到着時の中継ノードでの処理フローを図１４に示す。図１４中のエントリ削除操作は図１５に示す。但し、データパケットには、ツリーＩＤとソース（送信元）アドレスが含まれており、これをＮ及びＳで表すことにする。また、Ｘはタイムアウトと判断する時間間隔である。即ち、受信要求パケットが到着してから、現在までの経過時間がＸを越える場合はタイムアウトと判断する。図１２及び図１４では、Ｘは固定的に与えられる場合を想定している。
【００９１】
上記の方法は、ユーザがサーバーを指定する際、予め決められたサーバー群の中から選択する場合は問題ないが、ユーザがキーボード等を用いてサーバーのアドレスを入力する場合のように、サーバーの指定間違いが起こり得る時は、実際には存在しないサーバーのための配信テーブルが各中継ノードに生成される問題が起こる。このような場合は、受信要求パケットを送出する前に、サーバー宛にサーバー確認パケットを送出し、これに対してサーバーの存在を示すパケットがサーバーから返ってきた時に初めて、受信要求パケットを送出するようにすれば良い。
【００９２】
本実施の形態では、サーバおよび中継ノードは子から受信要求パケットを受信するとともに、子に向けてデータパケットを配信している。また、クライアント及び中継ノードはサーバに向けてデータパケットの配信を要求している。さらに、クライアント及び中継ノードが親ノードからデータパケットを受信したとき、クライアント及び中継ノードにはサーバからデータパケットが送られてくるように見えている。つまり本実施の形態では、受信要求パケットやデータパケットを送信するにあたって、親ノードあるいは子の先にどれだけのノードが接続されているかを意識する必要がなく、スケーラビリティの点で優れている。
【００９３】
なお、上述したクライアント（受信ホスト），中継ノード，サーバ（送信ホスト）内の各部が具備している機能は、実際にはいずれもコンピュータによって実現することが可能である。そのためには、本実施の形態の動作をコンピュータにより実行させるためのプログラム（例えば中継ノードの場合は中継プログラム）をコンピュータにより読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行させることにより、本実施形態の機能を実現にしてもよい。ここでいうコンピュータシステムとは、ＯＳ（オペレーティングシステム）に加えて周辺機器等のハードウェアを含むものとする。またＷＷＷ（World Wide Web）システムを利用している場合であれば、コンピュータはホームページ提供環境（あるいはその表示環境）を含むものとする。上記プログラムは、前述した機能の一部を実現するものでも良く、さらにコンピュータにすでに記録されているプログラムとの組み合わせでかかる機能を実現するもの（いわゆる差分プログラム）でも良い。コンピュータ読み取り可能な記録媒体は、フレキシブルディスク，光磁気ディスク，ＲＯＭ（読み出し専用メモリ），ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置を含む。さらに、コンピュータ読み取り可能な記録媒体は、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間だけ動的にプログラムを保持するものや、コンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。そして、以上のことはこれ以後に説明する各実施の形態やその応用例においても全く同様である。
【００９４】
〔実施の形態２〕
実施の形態１では、サーバーの指定間違いが起こり得る時の対策として、クライアントからサーバー確認パケットと受信要求パケットとの２種頚のパケットを送出する方法を示したが、実施の形態２では、クライアントから送出される受信要求パケットのみであり、かつ、サーバーの指定間違いが起こり得る時にも対応できる実施の形態を示す。
【００９５】
クライアントから送出された受信要求パケットは、クライアントに最寄りの中継ノードに配信テーブルがある場合は、実施の形態１の場合と同様に最寄りの中継ノードに登録される。最寄りの中継ノードが高負荷状態にあり、クライアントを子として収容できない場合も実施の形態１の場合と同様である。
【００９６】
クライアントに最寄りの中継ノードに配信テーブルがない場合、受信要求パケットはサーバーに向けて転送される。但し、転送の途中で通過した中継ノードが受信要求パケットに記録される。
【００９７】
受信要求パケットが、配信テーブルを既に持っている中継ノードまたはサーバーに到着した時には、クライアントから上記中継ノードまたはサーバーに至る経路情報が受信要求パケットに記述されていることになる。上記中継ノードまたはサーバーは、この経路情報を含む配信テーブル生成パケットをクライアントに向かって送出する。
【００９８】
配信テーブル生成パケットは、上記の経路情報を逆に辿ることによりクライアントまで配送され、途中通過する中継ノードにおいて、上記サーバーに対応する配信テーブルが既にあれば単に転送され、配信テーブルがなければ上記サーバーに対応する配信テーブルを生成する。配信テーブル生成パケット内の経路情報に関して、次のノードを配信テーブル生成と同時に登録する方法も可能であるが以下では配信テーブル生成時には何も登録しない手法について説明する。
【００９９】
このように、配信テーブル生成パケットがクライアントに到着するまでに（正確に言うと配信テーブル生成パケットはクライアントの最寄りの中継ノードで廃棄される）、クライアントからサーバーに至る経路上で配信テーブルを持たない中継ノードには、新たに配信テーブルが生成される。クライアントは、実施の形態１の場合と同様に、予め決められた値以下の時間間隔で受信要求パケットを送出し続ける。そのため、クライアントからサーバーに至る経路上の全ての中継ノードに配信テーブルが存在する状態になった後、実施の形態１の場合と同様にクライアントが配信テーブルに登録され、必要であれば、中継ノード自身がサーバー宛に受信要求パケットを送出する。
【０１００】
図１６はマルチキャスト通信が行われるネットワーク構成の一例、ここでは４つの中継ノード４１−１，４１−２，４１−３，４１−４に５つの受信ホスト（以下、クライアントと呼ぶ）４２−１，４２−２，４２−３，４２−４，４２−５及び１つの送信ホスト４３（以下、サーバーと呼ぶ）がネットワークを介して接続されている状態を示している。
【０１０１】
図１６の構成において、例えば図１７に示すように、クライアント４２−３から受信要求パケットが送出され、サーバー４３に至る経路上に中継ノード４１−３及び４１−２があったとする。中継ノード４１−３及び４１−２には配信テーブルがないので、受信要求パケットはサーバー４３まで転送される。但し、この時、転送経路として、中継ノード４１−３及び４１−２が受信要求パケット内に経路情報として書き込まれている。
【０１０２】
図１８に示すように、サーバー４３から、この経路情報を含む配信テーブル生成パケットが送出されると、前記経路を逆に辿ることにより中継ノード４１−２及び４１−３に配信テーブルが生成される。仮に、サーバー４３からクライアント４２−３に至る通常の経路が中継ノード４１−４を通るものであっても、配信テーブル生成パケットは中継ノード４１−２及び４１−３を通ることになる。
【０１０３】
この後、クライアント４２−３から送出される受信要求パケットより、図１９に示すように、中継ノード４１−３及び４１−２の配信テーブルにクライアント４２−３及び中継ノード４１−３がそれぞれ登録され、中継ノード４１−２からサーバー４３に受信要求パケットが送出される。
【０１０４】
続いて、図２０に示すように、クライアント４２−２から受信要求パケットが送出された場合は、中継ノード４１−１に配信テーブルがないため、サーバー４３に向かって転送される。受信要求パケットが中継ノード４１−２に到着すると、中継ノード４１−２には配信テーブルが存在するので、中継ノード４１−２から配信テーブル生成パケットがクライアント４２−２に向かって送出される。図２１に示すように、配信テーブル生成パケットは中継ノード４１−１に配信テーブルを作成し、その後のクライアント４２−２からの受信要求パケットにより、図２２に示すように、クライアント４２−２が中継ノード４１−１の配信テーブルに登録され、中継ノード４１−１は中継ノード４１−２に登録される。
【０１０５】
受信要求パケットにより経路情報が蓄えられ、サーバーまたは中継ノードからクライアントに送出される配信テーブル生成パケットが、上記経路情報を逆に辿るのは、次の理由による。もし、クライアントからサーバーに至る経路とサーバーからクライアントに至る経路とが異なる場合、配信テーブル生成パケットが単純にクライアントに向けて送出された場合、配信テーブルはクライアントからサーバーに至る経路とは異なる経路に作られることになる。この場合、配信テーブルが作られた中継ノードには、受信要求パケットが到着しないため、すぐにタイムアウトすることになる。また、受信要求パケットは、常に配信テーブル生成パケットを送出した中継ノードまたはサーバーまで転送されることになる。このため、データパケットがいつまで経っても到着しないことになる。
【０１０６】
実施の形態２も実施の形態１と同様、クライアントやサーバーが移動端末の場合も有用である。クライアントが移動端末である場合、クライアントは受信要求パケットを出し続けることによって新しく収容される中継ノードに登録され、また、これまで収容されていた中継ノードではタイムアウトする。逆にサーバーが移動体である場合、mobile IP等の移動体宛のユニキャストを可能にする仕組みがあれば、サーバー宛に送出された受信要求パケットは、常にサーバーが実際に存在する位置に送られる。このため、新たに受信要求パケットを受信するようになった中継ノードには配信テーブルが作られ、受信要求パケットが到着しなくなった中継ノードの配信テーブルはタイムアウトする。
【０１０７】
具体的な実装例を示す。受信要求パケットは、ツリーＩＤ  Ｎと、ソース（送信元）アドレスＳと、ソース（送信元）側隣接ノードアドレスＰと、ソースから現ノードまでの経路情報Ｑを持っている。クライアントは、Ｓ及びＰをクライアントアドレス、Ｑ＝Ｓとして、受信要求パケットをサーバーに向かって送出する。受信要求パケットが中継ノードに到着した時、既にツリーＩＤ  Ｎに対応する配信テーブルがある場合、Ｓ＝ＰならばＳを登録し、Ｓ≠ＰならばＳに向かってＱを含む配信テーブル作成パケットを送出する。
【０１０８】
ツリーＩＤ  Ｎに対応する配信テーブルがない場合、Ｐを現中継ノードのアドレスに変え、Ｑに現中継ノードを加えて受信要求パケットを転送する。サーバーまで受信パケットが到着した場合は、上記中継ノードの処理のうち、配信テーブルがある場合と同じ処理を行う。
【０１０９】
受信要求パケットが中継ノードに到着した時の処理フローを図２３に示す。但し、図２３中の時間間隔Ｄは実施の形態１の場合と同様に定義する。また、図２３中の高負荷時の処理は図１３と同じである。配信テーブル生成パケットが中継ノードに到着した時の処理フローを図２４に示す。
【０１１０】
本実施の形態では、受信要求パケットを送信したホストとデータパケットを送信したホストとを結ぶパス上に存在する中継ノードにのみ配信テーブルが生成されるようになっている。このため、適当なアドレスを宛先アドレスとして配信テーブル生成パケットを送出しても、この宛先アドレスに対応するノードが実際に存在しなければ配信テーブルが生成されることはない。したがって、ネットワーク内ノードのアドレスを隠蔽しておけば、配信テーブル生成パケットのみを用いてノードに無用な配信テーブルを作成させることは困難になる。また、配信テーブル生成パケット以外のパケットは配信テーブルの生成機能を持たないので、当然ながら配信テーブルが中継ノードに生成されることはない。さらに、たとえ、配信テーブル生成パケットを送出するホストと受信要求パケットを送出するホストを用意し、これらホストが互いに協力し合って無用なテーブルを両者の間にあるノードに生成させようとしても効果的な攻撃を行うことは難しい。
【０１１１】
〔実施の形態３〕
実施の形態３では、クライアントから送出されるのが受信要求パケットのみであり、かつ、サーバーの指定間違いが起こり得る時にも対応できる他の実施の形態を示す。
【０１１２】
本実施の形態では、クライアントが受信要求パケットを送出し、中継ノードに到着した時、配信テーブルがなければ、送信元を現中継ノードに変えてサーバー宛に転送を行い、配信テーブルがあれば、送信元を登録する。サーバーから送出されたデータパケットは、中継ノードに到着すると、その中継ノードに配信テーブルがない場合は空の配信テーブルを生成して消滅し、配信テーブルがある場合は実施の形態１の場合と同様にタイムアウトしていない子に対して、必要ならば複製して、データパケットを転送する。
【０１１３】
データパケットによって空の配信テーブルが生成された後に到着した受信要求パケットにより、クライアントからこの中継ノードに至るパス上のクライアント側隣接ノードが配信テーブルに登録される。なぜなら、到着した受信要求パケットの送信元アドレスは、上記クライアント側隣接ノードであるからである。この後に到着したデータパケットにより、上記クライアント側隣接ノードにデータパケットが配送され、その結果、上記クライアント側隣接ノードに空の配信テーブルが生成される。
【０１１４】
このように、サーバーからクライアントに向かって配信テーブルが生成されていき、やがてクライアントにデータパケットが配送されるようになる。
【０１１５】
図２５はマルチキャスト通信が行われるネットワーク構成の一例、ここでは４つの中継ノード５１−１，５１−２，５１−３，５１−４に５つの受信ホスト（以下、クライアントと呼ぶ）５２−１，５２−２，５２−３，５２−４，５２−５及び１つの送信ホスト５３（以下、サーバーと呼ぶ）がネットワークを介して接続されている状態を示している。
【０１１６】
図２５の構成において、例えば、クライアント５２−３から受信要求パケットが送出されると、このパケットは各中継ノードでその送信元アドレスを変更されながらサーバー５３まで転送される。サーバー５３は到着した受信要求パケットの送信元が中継ノード５１−２なので、図２６に示すように、中継ノード５１−２宛にデータパケットを送出する。データパケットが到着すると、中継ノード５１−２には配信テーブルがないので、空の配信テーブルが生成される。
【０１１７】
その後、到着する受信要求パケットにより、図２７に示すように中継ノード５１−２の配信テーブルには、送信元である、中継ノード５１−３が登録される。その後、データパケットは、図２８に示すように、中継ノード５１−２の配信テーブルに基づいて中継ノード５１−３へ送出される。
【０１１８】
同様に中継ノード５１−３でも空の配信テーブルが作られた後、図２９に示すように、受信要求パケットによりクライアント５２−３が登録され、最後には、データパケットがクライアント５２−３に配送される。
【０１１９】
クライアントからサーバーに向かう経路とサーバーからクライアントに向かう経路とが異なる場合、配信テーブルは常にクライアントからサーバーへ向かう経路上に作られ、データパケットもその経路上を通過するため、配信テーブルが作られる中継ノードまたはサーバーと、受信要求パケットが到着する中継ノードまたはサーバーとが異なるようなことは起こらない。
経路情報を持たない配信テーブル生成パケット（本実施の形態ではデータパケットに等しい）を単純にクライアントに向けて送出した場合、宛先アドレスが中継ノードに変更されることはないので、配信テーブルはどの中継ノードにもつくられない。
【０１２０】
実施の形態３も実施の形態１と同様、クライアントやサーバーが移動端末の場合も有用である。クライアントが移動端末である場合、クライアントは受信要求パケットを出し続けることによって新しく収容される中継ノードに登録され、また、これまで収容されていた中継ノードではタイムアウトする。逆にサーバーが移動体である場合、mobile IP等の移動体宛のユニキャストを可能にする仕組みがあれば、サーバー宛に送出された受信要求パケットは、常にサーバーが実際に存在する位置に送られる。このため、新たに受信要求パケットを受信するようになった中継ノードには配信テーブルが作られ、受信要求パケットが到着しなくなった中継ノードの配信テーブルはタイムアウトする。
【０１２１】
受信要求パケット及びデータパケットが中継ノードに到着した場合の処理フローをそれぞれ、図３０及び図３１に示す。図３０における高負荷時の処理は、図１３と同じである。図３１中のエントリ削除操作は図１５と同じである。但し、図３１中のＸは固定的に与えられる場合を仮定している。
【０１２２】
実施の形態１と同様に、本実施の形態でも、受信要求パケット，データパケットを転送するにあたり、親ノードあるいは子の先にどれだけのノードが接続されているかを意識する必要がないため、スケーラビリティの点で優れている。
【０１２３】
また本実施の形態では、実施の形態２と同様に、受信要求パケットを送信したホストとデータパケットを送信したホストとを結ぶパス上に存在する中継ノードにのみ配信テーブルが生成されるようになっている。したがって、実施の形態２と同様に、ネットワーク内のノードのアドレスを隠蔽しておくことにより、配信テーブル生成パケットを送出するホストと受信要求パケットを送出するホストとが協力しない限り、ノードに無用なテーブルが作られることはない。加えて、本実施の形態によれば、たとえ受信要求パケットをサーバ側で覗き見たとしても、サーバに隣接するノードを知ることができるのみであり、当該隣接ノード以外のネットワーク内のノードのアドレスを知り得ない。このため、実施の形態２に比べてさらに安全なセキュリティを提供することができる。
【０１２４】
〔ノードの構成〕
図３２は実施の形態１、２及び３に共通のクライアントの構成を示すもので、図中、６１は時計、６２はパケット生成手段、６３は送信手段、６４は受信手段、６５は映像復号手段、６６は映像表示手段である。
【０１２５】
クライアントでは、パケット生成手段６２が時計６１を用いて定期的に受信要求パケットを生成し、送信手段６３によってサーバーへ向けて送信する。また、受信手段６４によってデータパケットを受けとると、映像復号手段６５によってデータパケットにより運ばれてきた映像データを復号し、映像表示手段６６によって映像を表示する。
【０１２６】
なお、特に実施の形態１のクライアントの場合、パケット生成手段６２を用いてサーバー確認パケットを生成し、送信手段６３によってサーバーへ向けて送信し、その応答パケットを受信手段６４によって受信した場合のみ、前述した受信要求パケットの生成及び送信を行う。
【０１２７】
図３３は実施の形態１、２及び３に共通の中継ノードの構成を示すもので、図中、７１は時計、７２はノード負荷測定手段、７３は配信テーブル、７４は配信テーブル管理手段、７５はパケット生成手段、７６は送信手段、７７は受信手段、７８はパケット複製手段である。
【０１２８】
中継ノードは、受信要求パケットを受信手段７７によって受信すると、ノード負荷測定手段７２によって測定した負荷状態により、負荷が高くない場合は時計７１を参照し、配信テーブル管理手段７４により、図１２（実施の形態１の場合）、図２３（実施の形態２の場合）、図３０（実施の形態３の場合）に示したように配信テーブルを更新し、（必要があれば）パケット生成手段７５によって新たに受信要求パケットを生成し、送信手段７６によってサーバーへ向けて送信する。また、データパケットを受信手段７７によって受信すると、図１４（実施の形態１、２の場合）、図３１（実施の形態３の場合）に示したように該データパケットの属するツリーに対応する配信テーブルに登録されている子の数だけ、パケット複製手段７８によりデータパケットを複製し、送信手段７６によって各子へ送信する。
【０１２９】
なお、配信テーブル７３の生成は、配信テーブル管理手段７４により、図１２（実施の形態１の場合）、図２４（実施の形態２の場合）、図３１（実施の形態３の場合）に示したように行われ、また、配信テーブル７３及びそのエントリの削除は、配信テーブル管理手段７４により、図１４（実施の形態１、２の場合）、図３１（実施の形態３の場合）に示したように行われる。
【０１３０】
図３４は実施の形態１、２及び３に共通のサーバーの構成を示すもので、図中、８１は時計、８２は配信テーブル、８３は配信テーブル管理手段、８４はパケット生成手段、８５は送信手段、８６は受信手段、８７はパケット複製手段、８８は配信用データ蓄積手段である。
【０１３１】
サーバーは、中継ノードと同様に、受信要求パケットの送信元及び受信要求パケットの到着時刻を配信テーブル８２に記憶する。この配信テーブル８２への削除・更新・登録などの管理は、配信テーブル管理手段８３が行う。サーバーは、配信用データ蓄積手段８８に蓄積してある配信用データをパケット生成手段８４を用いてパケット化し、配信テーブル８２に登録されているタイムアウトしていない子の数だけ、パケット複製手段８７を用いて複製を作り、送信手段８５を用いてこれらの子に送信する。
【０１３２】
なお、特に実施の形態２のサーバーの場合、配信テーブル生成パケットはパケット生成手段８４により生成され、送信手段８５により送信される。
【０１３３】
〔パケットフォーマット〕
次に、上述した実施の形態１乃至３に係るパケットのフォーマットについて説明し、その前提としてフロー識別についても説明する。
【０１３４】
ネットワーク内では様々なパケットが混在して転送されるため、本発明の各実施の形態に特有のパケット（受信要求パケット，データパケット，配信テーブル生成パケット，サーバ確認パケット）をクライアント，中継ノード，サーバが識別するためのフロー識別を行う必要がある。フロー識別を実現するには種々の手法が考えられるが、一例としてここでは特定ポート(well-known portと呼ぶ)を用いた場合を例に挙げる。同様の手法としては、ポート８０を利用したＨＴＴＰ(Hyper Text Transfer Protocol)が良く知られている。
【０１３５】
ここではプロトコルとしてＵＤＰ(User Datagram Protocol)を想定する。フロー識別のために予め特定ポートを決めておき、パケットのポート番号を参照してこの特定ポートを宛先とするパケットを本発明の各実施の形態に特有のパケットとして識別する。図３５はサーバ１０１，中継ノード１０２及び１０３，クライアント１０４及び１０５を含むネットワークにおける特定ポートを用いたフロー識別の様子を示す図である。同図では、受信要求パケットのソースポートとデータパケットの受信ポートが等しい場合について示してある。また、サーバ１０１のアドレスをＳ，中継ノード１０２及び１０３のアドレスをそれぞれＡ及びＢ、クライアント１０４及び１０５のアドレスをそれぞれＣ１及びＣ２としている。
【０１３６】
受信要求パケットは宛先アドレスとしてアドレスＳ，宛先ポートとして上記特定ポートであるＰｗ，ソースアドレスとしてＸ（ここではＡ，Ｂ，Ｃ１，Ｃ２のいずれか），ソースポートとしてＰｘ（ここではソースアドレスＸに対応してＰａ，Ｐｂ，Ｐｃ１，Ｐｃ２のいずれか）を持つ。また、データパケットは宛先アドレスとしてアドレスＸ，宛先ポートとしてＰｘ，ソースアドレスとしてＳ，ソースポートとしてＰｓを持つ。なお、データパケットのソースアドレスがサーバ１０１のアドレスとなっているのは、配信テーブルがサーバ毎に生成されるために、中継ノードは各配信テーブルがどのサーバに対応するのかをデータパケットのソースアドレスを見て判断するためである。また、各中継ノード１０２，１０３が備える配信テーブル１０６，１０７には、受信要求パケットのソースポートと同一の値が格納される受信ポートのフィールドが、受信要求パケットの送信元（図中では「子」）及び到着時刻の各フィールドと組にされて登録される。
【０１３７】
各クライアント及び各中継ノードは、受信要求パケットの宛先ポートを上記特定ポートとして、データパケットを受信したいポートから当該受信要求パケットをサーバ１０１宛てにユニキャストで送出する。例えば、クライアントＣ１が送出する受信要求パケットのソースアドレスはＣ１，ソースポートはＰｃ１であり、宛先アドレス及び宛先ポートは上述した通りである。
【０１３８】
受信要求パケットが到着した中継ノードでは、受信要求パケットのソースアドレス及びソースポートを配信テーブルに記録する。また、中継ノードは配信テーブルを参照して、タイムアウトしてない各子の受信ポートに宛ててソースアドレス及びソースポートの組を宛先としたデータパケットをユニキャストする。例えば、中継ノード１０３はクライアント１０４からの受信要求パケットに基づいてソースアドレスＣ１，ソースポートＰｃ１，到着時刻１０：２３：０９を組にして配信テーブル１０７に登録する。また中継ノード１０３は、宛先アドレス，宛先ポートをそれぞれＣ１，Ｐｃ１とし、ソースアドレス及びソースポートとしてサーバ１０１側から送られたそのまま値Ｓ，Ｐｓを持つデータパケットをクライアント１０４に宛てて送出する。
【０１３９】
また、中継ノードが受信要求パケットを親ノードに送出する場合はクライアントの場合と同様である。例えば、中継ノード１０３が送出する受信要求パケットでは、宛先アドレス及び宛先ポートはそれぞれ常にＳ，Ｐｗであり、ソースアドレスはＢであり，ソースポートは任意のポート（例えばＰｂ）である。これは、受信要求パケットのみが宛先（サーバー）アドレスとは異なるアドレスを持つ中継ノードで処理される必要があるからである。ただし、ソースポートをPwにした場合、宛先ポートがPwであるデータパケットがネットワーク中を流れることになるが、宛先とは違う中継ノードではデータパケットを処理しないようにする必要がある。
また、受信要求パケットが到着したサーバ１０１は、ソースアドレス及びソースポートがそれぞれＳ，Ｐｓであり、宛先アドレス及び宛先ポートがそれぞれ中継ノード１０２からの受信要求パケットのソースアドレスＡ及びソースポートＰａに等しいデータパケットを送出する。
【０１４０】
なお、あるホスト上に複数のサーバを立ち上げて複数種類のストリームを同時並行的に配信するような形態を採ることも考えられる。ここで、上述した通りフロー識別に特定ポートであるwell-known portを用いているため、ポートに基づいて同一ホスト上の各サーバを区別することはできない。そこで、チャネルＩＤと呼ぶ情報を新たに設けて同一ホスト上の複数のサーバを識別する。このチャネルＩＤは同一ホスト上において一意な値に設定する必要があるが、異なるホスト間では必ずしも一意である必要はない。こうしてサーバアドレスとチャネルＩＤとを組にして用いることでサーバ及びマルチキャストツリーを一意に特定することができる。換言すれば、各中継ノードにはサーバアドレス及びチャネルＩＤの組毎に配信テーブルがそれぞれ生成されることになる。なお、チャネルＩＤは例えばパケットのペイロードに載せれば良い。
【０１４１】
次に、いま述べたフロー識別を前提としたパケットフォーマットについて説明する。図３６は受信要求パケットのフォーマットの一例を示したものであり、宛先（サーバ）アドレス１１１，宛先（サーバ）ポート１１２，送信元アドレス１１３，送信元ポート１１４，チャネルＩＤ１１５，高さ１１６の各フィールドから構成される。宛先アドレス１１１〜チャネルＩＤ１１５は前述した通りである。高さ１１６は、実施の形態１で説明したように、中継ノードがマルチキャストツリー上における高さｈを知るために用いられる。なお、図３５を参照して説明したように、宛先アドレス１１１，宛先ポート１１２は常にサーバに宛てたものとなる。
【０１４２】
次に、図３７はデータパケットのフォーマットの一例を示したものであって、宛先アドレス１２１，宛先ポート１２２，送信元（サーバ）アドレス１２３，送信元（サーバ）ポート１２４，チャネルＩＤ１２５，データ１２６の各フィールドから構成される。宛先アドレス１２１〜チャネルＩＤ１２５は前述した通りである。データ１２６は配信されるストリーム（コンテンツ）である。なお、図３５を参照して説明したように、送信元アドレス１２３，送信元ポート１２４は常にサーバのものとなる。
〔応用例〕
【０１４３】
次に、上述した実施の形態１ないし実施の形態３で説明したマルチキャスト通信に対し、付加機能としてのデータ変換機能を追加した応用例について説明する。ここで言うデータ変換とは、複数の中継ノードによるストリーム等のコンテンツの中継過程においてコンテンツデータの一部又は全部に何らかの変更を行うことを意味する。具体的には、コンテンツデータに対して広告データを付加する機能，コンテンツデータに付加されている広告データを別の広告データに差し替える機能，コンテンツデータのデータ形式をある形式から別の形式に変換する機能等である。
【０１４４】
従来、マルチキャストツリー形のネットワークを介して、サーバからクライアントに対して例えば広告付きのストリームデータを配信する場合、そのサーバにおいて、配信しようとするストリームデータに所要の広告データを事前に付加したものを用意し、これを各クライアントに向け配信する手法が一般に採用されていた。
【０１４５】
以上のような手法を採用した場合、ストリームデータに各クライアント（ユーザ）の嗜好に合った広告データを付加しておくことで、それら各クライアントに対し、より効果の高い広告を提示することが可能となるが、その一方で、存在する各クライアントの嗜好の種類に応じた多数の広告付きストリームデータを用意しておかなければならないため、サーバの負荷が増加してそのスケーラビリティが低下するなどの問題が指摘されていた。
【０１４６】
こうした問題に対処するため、近年、種々の手法が提案されており、例えば、特開２０００−２９７１２号公報には、ゲームプログラムをサーバからダウンロードする際に、各地のゲームセンタなどに設置された端末局において、広告を選択的に付加する手法が開示されている。
【０１４７】
また、本願出願人による特開平１１−１３４３５３号公報には、ネットワーク内に設置された広告付加サーバが、クライアントからのデータ取得要求に伴ってサーバからストリームデータを取得し、当該ストリームデータにクライアントの嗜好に合った広告データを統計的に付加したものを、その取得要求を行ったクライアントに返送する手法が開示されている。
【０１４８】
しかしながら、上述した端末局において広告を選択的に付加する手法では、広告付加処理の負荷分散を行おうとする場合には、それを存在する端末局ごとに行わなければならず、クライアントの数が動的に増減した場合には対処できないという問題があった。
【０１４９】
また、広告付加サーバを用いて所要の広告付きストリームデータを得る手法では、クライアントは、サーバではなく代理サーバにデータ取得要求を行う必要があるため、その広告付加サーバに負荷が集中するという問題があった。
【０１５０】
このほか、クライアントの嗜好に合わせた広告配信に関する技術を開示した文献として特開２００１−３０６６１１公報がある。この文献では嗜好管理サーバ，顧客管理サーバ，広告管理サーバに蓄積された情報に基づいて各ユーザに配信する広告を決定し、ユーザの嗜好に合わせて広告を配信している。しかし、この文献では広告付加を分散して行うことが考慮されておらず、上述した実施の形態１ないし実施の形態３で採用されているマルチキャスト技術と組み合わることができないという問題がある。
【０１５１】
以上のことを背景として、本応用例では上述したマルチキャスト通信に対して以下のような機能を付加するものである。
・各クライアントの嗜好に合った広告などの付加データをコンテンツデータに効率良く付加しあるいは差し替えを行う。
・コンテンツデータの配信過程において、当該コンテンツデータのデータ形式を各クライアントが受信可能な形式に変換する。
・所要のコンテンツデータの配信を、各中継ノード自身の負荷状態や当該各中継ノードの通信リンクの負荷状態を考慮して行う。
【０１５２】
また、本応用例では以下のことを想定して説明を行う。まず、マルチキャストプロトコルとしてはアプリケーション層のものを想定する。また、ＩＰマルチキャストではマルチキャストツリーに参加している者であれば誰でもストリームデータの送信者になりうるが、ここではマルチキャストツリーの根に相当するサーバ等のノードのみが送信者になりうるものとする。また、マルチキャストツリー上における各ノードは子毎に異なる処理を行うために自身の子を区別できるものとし、子も自身の親ノードを明示的あるいは暗黙的に知っているものとする。
【０１５３】
ここでは、理解を容易にするために、まずデータ変換機能に特有な点に絞って説明を行い、その後にデータ変換機能を上述したマルチキャスト通信に付加した場合について説明する。また前者の説明においては、初めに概要として、複数の中継ノードによるストリームデータの中継過程において、当該ストリームデータに対し、所定の付加データとして広告データを付加する場合を想定して説明し、これに引き続き、概要説明に基づく第１及び第２の装置例、ネットワークシステム装置例及び方法例と、その方法例を実施するためのプログラム例及び記録媒体例を順に説明し、さらに、これらの変形例として、上記ストリームデータのデータ形式を変換する場合を想定した第１の変形例及び第２の変形例を挙げて詳細に説明するものとする。
【０１５４】
なお、第１の装置例，第１のネットワークシステム装置例，第１の方法例と第２の装置例，第２のネットワークシステム装置例，第２の方法例とは想定するコストモデルが相違するものの基本的な技術思想は同じである。したがって、第１の装置例，第１のネットワークシステム装置例，第１の方法例と第２の装置例，第２のネットワークシステム装置例，第２の方法例とはいずれか一方を選択的に実施することが可能である。同様に、第１の変形例と第２の変形例とはいずれか一方を選択的に実施することが可能である。また、第１の装置例，第１のネットワークシステム装置例，第１の方法例あるいは第２の装置例，第２のネットワークシステム装置例，第２の方法例のいずれかと、第１の変形例あるいは第２の変形例のいずれかとは、同時に実施することが可能である。
【０１５５】
（概要）
本応用例では、上述したマルチキャスト通信への適用を想定して、サーバから複数のクライアントに対しマルチキャストによりストリームデータを配信する場合を想定する。但し、クライアントが１つである特別な場合を想定することで、本応用例は、１対１の通信（ユニキャスト）にも適用可能である。
【０１５６】
また、クライアント（ユーザ）は、ｎ種類用意された広告カテゴリの中から、１つ又は複数のカテゴリを選択するものとする。但し、このときの広告カテゴリの選択は、ユーザが敢えて明示的に行う必要はなく、例えば、クライアントにおけるネットワークのアクセス履歴から、ユーザの嗜好に関する情報を自動的に抽出するようにしてもよい。
【０１５７】
また、各中継ノードは、ストリームデータに対する広告データの付加又は差し替えを、マルチキャストツリー形のネットワークにおけるリーフ側隣接ノード（以下、「子ノード」又は単に「子」ともいう）ごとに行う機能を具備するものとする。
【０１５８】
以上のような中継ノードにより構成されるマルチキャストネットワークにおいて、サーバから送信されたストリームデータがクライアントに到着するまでに、各中継ノードにおいて、クライアントが嗜好した広告を付加するという条件の下で、ネットワーク全体に亙る広告データの付加・差し替えのコストを最小にするための手段と手法及び手順並びに手続を以下に示す。
【０１５９】
（第１の装置例及びネットワークシステム装置例）
以下に説明する第１の装置例，ネットワークシステム装置例，第１の方法例ならびに第２の装置例，ネットワークシステム装置例，第２の方法例は、マルチキャスト通信に対する付加機能であるデータ変換機能の第１の例である。
まず、図３８は、本応用例における第１の装置例に係る中継ノードの内部構成を示すブロック図である。
【０１６０】
同図に示すように、本装置例に係る中継ノードＮ１は、単一のサーバ（図示せず）から１以上のクライアント（図示せず）に向けストリームデータを配信するためのマルチキャストツリー形のネットワーク（図示せず）に適用され、所要のストリームデータの中継過程において、当該ストリームデータに対し広告データを付加するために、基本的に、広告データ記憶手段１０１１と、付加広告指示テーブル１０１２と、受信手段１０１３と、広告付加・差し替え手段１０１４と、送信手段１０１５と、嗜好情報抽出手段１０１６と、嗜好情報テーブル１０１７と、嗜好情報集計手段１０１８とを具備して構成される。
【０１６１】
このうち、広告データ記憶手段１０１１は、存在する各クライアントに配信しようとする広告データを、要求される複数のカテゴリに亙って事前に記憶するものであり、付加広告指示テーブル１０１２は、各クライアントの嗜好と広告データの付加コストとの間の相関を表した嗜好ベクタ（本発明にいう「嗜好情報」の一形態。詳細は後述）に基づき、存在する１以上のリーフ側隣接ノード（図示せず）へ転送すべき広告データのカテゴリを、リーフ側隣接ノードごとに事前に分類定義したものである。
【０１６２】
また、受信手段１０１３は、ルート側隣接ノード（図示せず）から転送されてくるストリームデータを受信すると共に、１以上のリーフ側隣接ノードから転送されてくる１以上の嗜好ベクタを受信するものである。なお、この受信手段１０１３は、広告データ記憶手段１０１１に事前に登録されるべき広告データをネットワークから受信するようにも機能する。
【０１６３】
さらに、広告付加・差し替え手段１０１４は、受信手段１０１３で受信されたストリームデータのデータ付加形態に応じ、各リーフ側隣接ノードに転送すべき広告データのカテゴリを、付加広告指示テーブル１０１２を参照して選択すると共に、その選択したカテゴリに対応して広告データ記憶手段１０１１に記憶されている広告データを読み出し、当該読出しに係る広告データのストリームデータに対する付加、差し替えを行うものである。
【０１６４】
そして、送信手段１０１５は、広告付加・差し替え手段１０１４により広告データの付加、差し替えが行われたストリームデータを、各リーフ側隣接ノードに向けて送信するものである。
【０１６５】
なお、上記付加広告指示テーブル１０１２は、嗜好情報抽出手段１０１６、嗜好情報テーブル１０１７、及び嗜好情報集計手段１０１８による内容更新が可能なものである。
【０１６６】
即ち、付加広告指示テーブル１０１２は、受信手段１０１３で受信された１以上の嗜好ベクタを抽出（不要なパケットヘッダ等を除去）する嗜好情報抽出手段１０１６と、この嗜好情報抽出手段１０１６により抽出された１以上の嗜好ベクタを保持する嗜好情報テーブル１０１７と、この嗜好情報テーブル１０１７に保持された１以上の嗜好ベクタに所定の演算を集約的に施して、新たな嗜好ベクタを得る嗜好情報集計手段１０１８とに基づく内容更新が可能である。
【０１６７】
なお、以上のように構成された中継ノードＮ１により、マルチキャストデータ通信システムを構成するには、単一のサーバから１以上のクライアントに向けストリームデータを配信するためのマルチキャストツリー形のネットワークを構成し、当該ネットワークに、以上の中継ノードＮ１を複数の中継ノードにそれぞれ割り当てればよい（そのネットワークの形態は、特に図示はしていないが、後述する方法例において明らかとなる）。
【０１６８】
（第１の方法例）
続いて、以上のように構成された中継ノードＮ１及びネットワークシステム装置により実施される第１の方法例について説明する。
【０１６９】
まず、本方法例では、次のようなコストモデルを想定する。即ち、中継ノードＮ１が、ルート側隣接ノード（以下、「親ノード」又は単に「親」ともいう）からのパケットを、各々のリーフ側隣接ノードに対し単に転送するコストは「０」で、広告データの付加・差し替え処理を行うコストは「１」であるとする。
【０１７０】
例えば、ネットワーク上のある中継ノードＮ１が、ｃ個の子を持つ場合、ｘ個の子に対しては単に転送し、残りのｃ−ｘ個の子に対しては、広告データの付加・差し替え処理を実行して送出したとすると、該当する中継ノードＮ１のコストはｃ−ｘとなる。このコストモデルの下でネットワーク全体のコストを少なくすることは、広告データの付加・差し替えの回数を少なくすることを意味する。
【０１７１】
ここでは、まず、上記のコストモデルの下でネットワーク全体のコストを最小化するための方法を以下に説明する。なお、本方法は、「要求フェーズ」と「配送フェーズ」の２つのフェーズにより実現される。
【０１７２】
ここで、要求フェーズでは、クライアントが嗜好する広告のカテゴリ（以下、「広告カテゴリ」又は単に「カテゴリ」ともいう）がネットワークに伝えられ、それをもとに、複数の中継ノード（Ｎ１，Ｎ１，…）の中から、広告データの付加・差し替えを実際に行う中継ノードＮ１を決定する。
【０１７３】
一方、配送フェーズでは、要求フェーズによる決定をもとに、適切な中継ノードＮ１で、適切な広告データの付加・差し替えを実際に行う。以下に、これら要求フェーズ及び配送フェーズの詳細な動作を説明する。
【０１７４】
まず、要求フェーズでは、各中継ノード及びクライアントが、マルチキャストツリーにおける親ノードに向って、以下に定義する嗜好ベクタを定期的に送信する。即ち、広告カテゴリ数をｎとした場合、嗜好ベクタとは、要素を「１」又は「０」とするｎ次元ベクタ（ｎビットベクタ）であり、その嗜好ベクタのｉビット目が「１」であれば、ｉ番目の広告カテゴリを嗜好していることを表す。
【０１７５】
ここで、クライアントは、ｉ番目の広告カテゴリを希望する場合、ｎビットベクタ中のｉビット目を「１」とした嗜好ベクタを親ノードへ送信する。例えば、嗜好ベクタ（０，１，０）は、３つの広告カテゴリから２番目のカテゴリを希望することを表す。
【０１７６】
また、クライアントは、複数の広告カテゴリを同時に希望することも可能であり、例えば、嗜好ベクタ（１，１，０）は、３つの広告カテゴリから１番目または２番目のカテゴリを希望することを表す。従って、どの広告カテゴリでもよい場合には、嗜好ベクタは（１，１，１）となる。
【０１７７】
以下に、上述した嗜好ベクタに基づく要求フェーズの処理を図面を用いて説明する。
【０１７８】
図３９（ａ）及び図３９（ｂ）は、本応用例における第１の方法例に係る要求フェーズの概要を示す図である。
【０１７９】
まず、図３９（ａ）に示すように、中継ノードＮ１は、子から送信された嗜好ベクタの多数決をとり、最も要求の多い広告カテゴリに対応する嗜好ベクタの要素（ビット）のみを「１」にして、当該嗜好ベクタを親ノードに送信する。このとき、最も要求の多い広告カテゴリが複数ある場合は、それら広告カテゴリに対応する嗜好ベクタの要素を全て「１」（他の要素は「０」）とし、その嗜好ベクタを親ノードに送信する。
【０１８０】
例えば、子が２つ存在し、各子から送信された嗜好ベクタが、図示のように（１，０，０），（１，０，１）であった場合、これらの和をとると（２，０，１）となるので、その１ビット目のみを「１」にセットし直した嗜好ベクタ（１，０，０）を親ノードに送信する。つまり、全ての子から送られた嗜好ベクタの和をとり、最大値をとるビットのみを「１」にして他は「０」にセットし、これを親ノードに送信するようにする。
【０１８１】
さらに、図３９（ｂ）に示すように、中継ノードＮ１は、配送フェーズにおいて付加・差し替えを行うべき広告データのカテゴリを示すテーブル、即ち、前述した付加広告指示テーブル１０１２を、各子から送られてきた上述の嗜好ベクタに従って生成し記憶する。
【０１８２】
この付加広告指示テーブル１０１２において、「Ｉｎ」の列は、親ノードからのストリームデータに付加されていた広告データのカテゴリを表し、「Ｏｕｔ１」，「Ｏｕｔ２」，…の列は、１番目，２番目，…の子へ出力するストリームデータに付加すべき広告データのカテゴリを表す。また、「φ」は、広告データが付加されていない状態を表し、「Ａ」，「Ｂ」，「Ｃ」は、それぞれ、１番目，２番目，３番目の広告カテゴリを表す。なお、広告データが付加されていないストリームデータが親ノードから送られてくる場合としては、親ノードであるサーバ又は中継ノードが広告データをストリームデータに付加する機能を備えていないような場合が挙げられる。
【０１８３】
ここで、付加広告指示テーブル１０１２は、嗜好ベクタ（１，０，０）を送信してきた子には、カテゴリＡの広告の付加・差し替えを、また、嗜好ベクタ（１，０，１）を送信してきた子には、カテゴリＡ又はＣの広告の付加・差し替えを行うよう、前述の広告付加・差し替え手段１０１４に指示する。但し、後者の場合、親ノードからのストリームデータに付加されている広告データのカテゴリに応じ、可能な限り転送だけで済むように当該付加広告指示テーブル１０１２を構成する。
【０１８４】
例えば、親ノードからのストリームデータにカテゴリＣの広告データが付加されていた場合には、嗜好ベクタ（１，０，１）を送信してきた子に対しては、カテゴリＣを選択することにより、当該ストリームデータの転送だけで済ませることができる（カテゴリＡを選択した場合、差し替え（カテゴリＣ→カテゴリＡ）が必要になってコストが増加するため、これを回避するようにしている）。
【０１８５】
なお、本来であれば親ノードに要求した通りのカテゴリの広告データが親ノードから送られてくるはずであるが、クライアントが嗜好ベクタを動的に変更したような場合にはタイミングによっては親ノードに要求したものとは異なるカテゴリの広告データが送られてくる可能性がある。このため、親ノードから送られてくる可能性がある全ての広告カテゴリについて付加広告指示テーブル１０１２のエントリを作成するようにしている。
【０１８６】
次に、上述した嗜好ベクタに基づく配送フェーズの処理を図面を用いて説明する。
【０１８７】
図４０は、本応用例における第１の方法例に係る要求フェーズの具体的動作例を示す図である。
【０１８８】
なお、同図において、「Ａ」，「Ｂ」で示されるノードはクライアントを表し、「Ｓ」で示されるノードはサーバを表し、他のノードは中継ノードＮ１（以下、符号「１００１」，「１００２」，「１００３」，「１００４」により代替表示）を表す。また、広告カテゴリは「Ａ」と「Ｂ」の２種類あり、上述のクライアントを示す符号（「Ａ」及び「Ｂ」）は、該当するクライアントが嗜好する広告カテゴリを表す（但し、「Ａ」及び「Ｂ」を、それぞれ、１番目及び２番目の広告カテゴリとする）。
【０１８９】
また、各付加広告指示テーブル１０１２中の記号のうち、「＊」は、任意の広告カテゴリ（広告データが付加されていない状態を含む）に適合することを意味する（「Ｉｎ」，「Ｏｕｔ１」，「Ｏｕｔ２」，「φ」については、図３９（ｂ）のそれらと同様であるが、子の番号については、図の左の子から順に、１，２，３，…というように番号付けされていることを仮定している）。
【０１９０】
同図に示すように、まず、広告カテゴリＡを嗜好するクライアントは、嗜好ベクタ（１，０）を親ノードに送り、広告カテゴリＢを嗜好するクライアントは、嗜好ベクタ（０，１）を親ノードに送る。
【０１９１】
このとき、中継ノード１００３は、嗜好ベクタ（１，０）を子から受け取るので、要求フェーズにおいて、親ノード（中継ノード１００２）から送られてきたストリームデータに付加されている広告データのカテゴリによらず、広告カテゴリＡに属する広告データの付加又は差し替えが行われるよう、付加広告指示テーブル１０１２を生成し、親ノードに対し、子ノードから受け取った嗜好ベクタ（１，０）をそのまま送信する。
【０１９２】
一方、中継ノード１００４では、２つの子から嗜好ベクタ（０，１），（１，０）が送られてくるので、中継ノード１００２からのストリームデータに付加されてきた広告データのカテゴリによらず、図の左の子には広告カテゴリＢに属する広告データの付加又は差し替えが、右の子には広告カテゴリＡに属する広告データの付加又は差し替えが行われるよう付加広告指示テーブル１０１２を構成し、中継ノード１００２に対し、前述した規則に従って生成した新たな嗜好ベクタ（１，１）を送信する。
【０１９３】
以上の結果、中継ノード１００２には、２つの子から嗜好ベクタ（１，０），（１，１）が送られることになり、当該中継ノード１００２は、左の子（中継ノード１００３）に対しては、親ノード（中継ノード１００１）からのストリームデータに付加されている広告データのカテゴリによらず、広告カテゴリＡに属する広告データの付加又は差し替えが、また、右の子（中継ノード１００４）に対しては、広告カテゴリＡ又はＢの何れかに属する広告データ（コストが少なくて済む方のカテゴリに属する広告データ）の付加又は差し替えが行われるよう、付加広告指示テーブル１０１２を構成する。
【０１９４】
即ち、図示の例の場合、中継ノード１００１からのストリームデータに広告カテゴリＡの広告データが付加されていても、広告カテゴリＢの広告データが付加されていても、当該ストリームデータは、そのまま中継ノード１００４に転送されることになる。但し、ストリームデータに広告データが何も付加されていない場合には、中継ノード１００２は、広告カテゴリＡ又はＢのうちの何れかを任意に選択し、その選択したカテゴリの広告データをストリームに付加して、中継ノード１００４に送信する（中継ノード１００１の動作は、前述した中継ノード１００３におけるそれと同様）。
【０１９５】
そして、このようにして生成、構成された付加広告指示テーブルをもとに、配送フェーズにおいて広告データの付加・差し替えが行われる。
【０１９６】
なお、各中継ノード１００１，１００２，１００３，１００４は、子から送られた嗜好ベクタを同時に受け取るとは限らないため、実際には、子から送信された嗜好ベクタを、前述した嗜好情報テーブル１０１７にて記憶しておき、全ての子からの嗜好ベクタが揃った時点で、新たな嗜好ベクタを得るための多数決をとることになる。また、嗜好ベクタの変更や、マルチキャストツリーへのクライアントの参加や離脱などに対応するため、所要の多数決を取る操作は、例えば、子からの嗜好ベクタが変更されたことを契機に行ったり、或いは、予め設定された所定の時間間隔ごとに行うようにするとよい。
【０１９７】
次に、図４１は、本応用例における第１の方法例に係る配送フェーズの具体的動作例を示す図である（図４０に示した要求フェーズに対応）。
【０１９８】
同図に示すように、各中継ノード１００１，１００２，１００３，１００４は、親ノードから送られてきたストリームデータに付加されている広告データをもとに、実際の広告データの付加・差し替えの処理を決定する。このため、要求フェーズによるテーブル更新のタイミングのずれにより、親ノードに送信した嗜好ベクタと矛盾するカテゴリに属する広告データの付加されたストリームデータが、親ノードから送られてきたとしても、「クライアントの嗜好どおりに広告を付加する」という機能が破綻をきたすことはない。
【０１９９】
従って、要求フェーズと配送フェーズとは、独立して動作することが可能であり、要求フェーズによって各付加広告指示テーブル１０１２が更新される時間間隔が十分に長ければ、上記コストモデルのもとでコスト最小の配送が実現される。
【０２００】
次に、図４２は、所要の広告データの付加・差し替え処理を通常の方法により実行した場合のコスト例を示す図である。なお、図中の数字は各ノードのコストである。
【０２０１】
同図に示すように、まず、マルチキャストツリーのリーフを構成する各クライアントが、広告カテゴリとして「Ａ」，「Ｂ」，「Ｃ」の何れかを嗜好している場合を想定する。また、図示の太実線、点線、及び破線は、それぞれ、広告カテゴリＡ，Ｂ，Ｃの広告データが付加されたストリームデータが流れる通信リンクを表し、各中継ノードの近傍に付与された数字は、それら各中継ノードにおけるコストを表す。
【０２０２】
ここで、広告カテゴリＡを嗜好しているクライアントが最も多く存在することを根拠に、サーバ直下の中継ノードにおいて、そのカテゴリＡの広告データをストリームデータに付加し、各クライアントが隣接する中継ノードにおいて、それら各クライアントの嗜好に合わせて広告データの差し替えを行うものとする。
【０２０３】
以上のようにして広告データの差し替えを行った場合、本マルチキャストネットワーク全体のコストは、各中継ノードにおけるコストの和をとれば、「１１」となることが理解される。
【０２０４】
一方、図４３は、本応用例における第１の方法例により広告データの付加・差し替え処理を実行した場合の第２のコスト例を示す図である。なお、図中の数字は各ノードのコストである。
【０２０５】
同図に示すように、本方法例により広告データの差し替えを行った場合、マルチキャストネットワーク全体のコストは、「８」となり、前述した通常の場合よりも少ないコストで、所要の広告データの付加・差し替え処理を実行することが可能となる。
【０２０６】
（第２の装置例及びネットワークシステム装置例）
本装置例及びネットワークシステム装置例は、嗜好ベクタの意味、広告データの付加・差し替えに要するコストを計算するための具体的な手法、および、クライアントが送出する嗜好ベクタの形式が、上述した第１の装置例及びネットワークシステム装置と異なっている。
図４４は、本応用例における第２の装置例に係る中継ノードの内部構成を示すブロック図である。
【０２０７】
同図に示すように、本装置例に係る中継ノードＮ２は、第１の装置例におけるそれと同様、単一のサーバ（図示せず）から１以上のクライアント（図示せず）に向けストリームデータを配信するためのマルチキャストツリー形のネットワーク（図示せず）に適用され、所要のストリームデータの中継過程において、当該ストリームデータに対し広告データを付加するために、基本的に、広告データ記憶手段１０２１と、付加広告指示テーブル１０２２と、受信手段１０２３と、広告付加・差し替え手段１０２４と、送信手段１０２５と、嗜好情報抽出手段１０２６と、嗜好情報テーブル１０２７と、嗜好情報集計手段１０２８とを具備して構成される。
【０２０８】
なお、これら広告データ記憶手段１０２１、付加広告指示テーブル１０２２、受信手段１０２３、広告付加・差し替え手段１０２４、及び送信手段１０２５の構成は、第１の装置例におけるそれと同様であるので、その説明は省略する。
【０２０９】
また、上記付加広告指示テーブル１０２２は、図示の嗜好情報抽出手段１０２６、嗜好情報テーブル１０２７、及び嗜好情報集計手段１０２８による内容更新が可能である。
【０２１０】
即ち、付加広告指示テーブル１０２２は、受信手段１０２３で受信された１以上の嗜好ベクタ（本発明にいう「嗜好情報」の一形態。詳細は後述）を抽出する嗜好情報抽出手段１０２６と、この嗜好情報抽出手段１０２６により抽出された１以上の嗜好ベクタを保持する嗜好情報テーブル１０２７とに基づいて、その内容が更新される。また、嗜好情報集計手段１０２８は、嗜好情報テーブル１０２７に保持された１以上の嗜好ベクタに所定の演算を集約的に施して、新たな嗜好ベクタを得る。
【０２１１】
なお、以上のように構成された中継ノードＮ２により、マルチキャストデータ通信システムを構成するには、単一のサーバから１以上のクライアントに向けストリームデータを配信するためのマルチキャストツリー形のネットワークを構成し、当該ネットワークに、以上の中継ノードＮ２を複数の中継ノードにそれぞれ割り当てればよい（そのネットワークの形態は、特に図示はしていないが、後述する方法例において明らかとなる）。
【０２１２】
（第２の方法例）
続いて、以上のように構成された中継ノードＮ２及びネットワークシステム装置により実施される第２の方法例について、さらに一般的なコストモデルを想定して説明する。
【０２１３】
図４５は、本応用例における第２の方法例に係るコストモデルの概要を示す図である。
【０２１４】
同図に示すように、本方法例では、ある中継ノードＮ２（以下、符号「ｋ」により代替表示）がｃ個の子を持っている場合において、親ノードから送信されてきたストリームデータにｉ番目のカテゴリの広告データが付加されていたときに、その広告データを、ｊ番目の子に対してａ(j)番目のカテゴリの広告データに差し替える状況を想定する。
【０２１５】
このとき、中継ノードｋにおける広告データの付加・差し替えコストが、図示のように、ｆk(ｉ，a(1)，a(2)，…，a(c))で与えられるものとする。但し、親ノードから送られてくるストリームデータに広告データが付加されていない状態も、一つの広告カテゴリであると想定し、以降の説明では、広告データの差し替えのみを考慮するものとする。また、同じ広告カテゴリに属する広告データは、その差し替えコストの観点から、同等であるものとする。そうしない場合は、カテゴリをさらに細分化することにより、上記の条件を満たすようにすればよい。
【０２１６】
例えば、「Ａ」，「Ｂ」，「Ｃ」という広告カテゴリが、それぞれ、「Ａ1」及び「Ａ2」，「Ｂ1」及び「Ｂ2」，「Ｃ1」及び「Ｃ2」に細分化された場合でも、クライアントにとって意味のあるカテゴリ分けが「Ａ」，「Ｂ」，「Ｃ」であるならば、ユーザインターフェイスの上では「Ａ」，「Ｂ」，「Ｃ」というカテゴリ分けにしておき、例えば、広告カテゴリＡを嗜好するときは、実際には、広告カテゴリＡ1又はＡ2を嗜好するように解釈して処理すればよい。
【０２１７】
以上のようなコストモデルに関して、ネットワーク全体のコストが最小になるように広告データの差し替えを行う方法を以下に説明する。なお、本方法も、第１の方法例における場合と同様、「要求フェーズ」と「配送フェーズ」の２つのフェーズにより実現される。
【０２１８】
まず、要求フェーズでは、クライアントは、ストリームデータに、自己の嗜好する広告データが付加されていたときは、コスト「０」であり、それ以外の広告データが付加されていたときは、コスト無限大「∞」であるという情報を、親ノードに送信する。この情報を、広告カテゴリ数ｎに対し、ｎ次元のベクタ（嗜好ベクタ）で表すことにすると、例えば、４番目のカテゴリの広告データを嗜好する子からの嗜好ベクタは、（∞，∞，∞，０，∞，∞，…，∞）となる。
【０２１９】
このように、想定しているコストモデルの違いに起因して、本装置例の嗜好ベクタと上記第１の装置例における嗜好ベクタとはその定義が異なっている。すなわち、上記第１の装置例における嗜好ベクタは、クライアントが個々の広告カテゴリを嗜好しているかどうかに応じて嗜好ベクタの各要素を「１」又は「０」に設定している。これに対して本装置例では、クライアントの嗜好するデータがサーバ側から送られてくるストリームデータに付加されていたかどうかに応じて嗜好ベクタの各要素を０又は無限大に設定している。
【０２２０】
ここで、各中継ノードｋ，ｋ，…は、子から送信された嗜好ベクタと、広告データの差し替えにかかるコストを表す関数ｆk(ｉ，a(1)，a(2)，…，a(c))とに基づき、親から受け取ったストリームデータにカテゴリｉの広告データが付加されていた場合における、中継ノードｋをルートとするサブツリーの最小コスト値を各ｉに対して求め、これを嗜好ベクタで表して親ノードに送信する。
【０２２１】
即ち、いま、中継ノードｋが親ノードＰ(k)から受け取ったストリームデータに、カテゴリｉの広告データが付加されており、その中継ノードｋをルートとするサブツリーをＴ(k)とした場合において、このときに達成し得るＴ(k)の最小コストをｖkiとすれば、当該中継ノードｋは、親ノードＰ(k)に対し、ｎ次元の嗜好ベクタＶk＝（ｖk1，ｖk2，…，ｖkn）を送信する。
【０２２２】
以上の嗜好ベクタは、子ノードから送られた嗜好ベクタと上記関数ｆk(ｉ，a(1)，a(2)，…，a(c))とから計算され（詳細な計算法は後述）、例えば、Ｖkが（１０，２３，４１）であるとすると、広告カテゴリの数は３つあり、親ノードＰ(k)からのストリームデータに、１番目、２番目、又は３番目のカテゴリに属する広告データが付加されていた場合に達成し得るＴ(k)の最小コストは、それぞれ「１０」，「２３」，「４１」であることを表す。そして、上記のような嗜好ベクタの計算・送信処理は、リーフからルートに向かって順に実行される。
【０２２３】
なお、各中継ノードｋにおいて、各ｉ（ｉ＝１，２，…，ｎ）に対しｖkiを達成するために、各子に送出するストリームデータに関して差し替えるべき広告データのカテゴリは、そのｖkiの計算過程において得ることができるので、これを付加広告指示テーブル１０２２として記録しておき、この付加広告指示テーブル１０２２を利用して、第１の方法例と同様に、配送フェーズにおいて広告データの差し替えを行うようにする。
【０２２４】
次に、嗜好ベクタの計算方法について説明すれば、以下のようになる。即ち、まず、ｃ個の子を持つ任意の中継ノードｋが、ストリームデータに付加された広告データを、ｊ（ｊ＝１，２，…，ｎ）番目の子に対して、ａ(j)番目のカテゴリの広告データに差し替える場合を想定する。
【０２２５】
このとき、親ノードＰ(k)から、ｉ番目の広告データが付加されたストリームデータが到着したとすると、中継ノードｋにおける広告データの差し替えに関するコストは、上述の関数ｆk(ｉ，a(1)，a(2)，…，a(c))で表される。
【０２２６】
いま、中継ノードｋに対して、ｊ番目の子から送られてきたｎ次元嗜好ベクタを、Ｕj＝（ｕj1，ｕj2，…，ｕjn）とし、ｊ番目の子が中継ノードＣk(j)であるとすると、中継ノードｋからａ(j)番目の広告データが付加されたストリームデータが送られたときのサブツリーＴ（Ｃk(j)）の最小コストは、ｕja(j)である。
【０２２７】
従って、この場合のサブツリーＴ(k)の最小コストは、ｆk(ｉ，a(1)，a(2)，…，a(c))＋u1a(1)＋…＋uca(c)となる。よって、嗜好ベクタＶk＝（ｖk1，ｖk2，…，ｖkn）の要素ｖkiは、ａ(1)，ａ(2)，…，ａ(c)の全ての組み合せの中におけるｆk(ｉ，a(1)，a(2)，…，a(c))＋u1a(1)＋…＋uca(c)の最小値とすればよい。
【０２２８】
そして、以上の計算を各ｉに関して行って、Ｖk＝（ｖk1，ｖk2，…，ｖkn）を得ると共に、各ｖkiを達成するａ(1)，ａ(2)，…，ａ(c)の組み合せを、各中継ノードｋにおける付加広告指示テーブル１０２２に記録しておくようにする。
【０２２９】
次に、図４６は、本応用例における第２の方法例に係る要求フェーズの具体的動作例を示す図であり、図４７（ａ）乃至図４７（ｃ）は、コスト関数の具体例を示す図である。
【０２３０】
まず、図４６に示すように、サーバとクライアントとの間に、３つの中継ノードが介在している状態において、各中継ノードｋ（１００１，１００２，１００３）に関するコスト関数が、ｆk(ｉ，a(1)，a(2)，…，a(c))＝ｇk(ｉ，a(1))＋ｇk(ｉ，a(2))＋…＋ｇk(ｉ，a(c))と分解できる場合を例に挙げる。
【０２３１】
即ち、ある中継ノードｋに着目した場合、各子への広告データ差し替えの処理に要するコストは、完全に独立であり、かつ、コスト関数としては互いに等しい場合を意味している。
【０２３２】
ここで、各中継ノードにおけるコスト関数ｇkの例を挙げれば、図４７（ａ）乃至図４７（ｃ）の各左列に示すようになる。図中、コスト関数ｇkの各行は差し替え前の広告カテゴリを表し、その各列は差し替え後の広告カテゴリを表し、「φ」，「Ａ」，「Ｂ」については、それぞれ、１番目，２番目，３番目の広告カテゴリとして扱っている。但し、広告データが何も付加されていない状態も一つの広告カテゴリと見なしている。
【０２３３】
例えば、図４６に示す中継ノード１００１において、広告データが何も付加されていない状態から、広告データＡを付加するのに要するコストｇ1001(φ，Ａ)は、「１０」である（同図に示した嗜好ベクタ及び付加広告指示テーブル１０２２は、図４７（ａ）乃至図４７（ｃ）の左列に示すコスト関数をもとに、要求フェーズにおいて送出、生成されたものである）。
【０２３４】
次に、図４８（ａ）及び図４８（ｂ）は、本応用例における第２の方法例に係る要求フェーズの具体的動作例の一部分を示す図であり、図４９（ａ）乃至図４９（ｃ）は、コスト関数の計算例を示す図、図５０は、要求フェーズの具体的動作例の他の一部分を示す図である。
【０２３５】
まず、図４８（ａ）に示すように、中継ノード１００２が、その子である中継ノード１００３から嗜好ベクタＵ1＝（２０，１，２０）を受け取った場合、中継ノード１００１に送信すべき嗜好ベクタと、中継ノード１００２に生成すべき付加広告指示テーブル１０２２の計算法とは、図４９（ａ）乃至図４９（ｃ）に示すようなものとなる。
【０２３６】
ここで、ｇiの表を行列と見なしたとき、子の行列をＧiで表すこととする（図４７（ａ）乃至図４７（ｃ）の各右列参照）。ｇ1002は、中継ノード１００２における処理コストのみを表しているので、
【数１】
0003693978.tif 000002
を計算することで、サブツリーT(2)のコスト値を要素とする行列が得られる（図４９（ａ）参照）。
【０２３７】
上記式１の第ｉ行における最小値は、親ノードからのストリームデータに、ｉ番目のカテゴリの広告データが付加されていた場合に達成し得るサブツリーＴ(2)の最小コストを表している。何れの場合も、子に対して、カテゴリＡの広告データに差し替えて送出することが、最小コストを達成するための選択であることが理解される（図４９（ｂ）参照）。
【０２３８】
そして、以上により、図４９（ｃ）に示すように、中継ノード１００３へ送出する嗜好ベクタと、中継ノード１００２に生成すべき付加広告指示テーブル１０２２とが得られるようになり、以下、図５０に示すように、中継ノード１００２における要求フェーズ処理が完了した後に、同様な処理が中継ノード１００３，１００２，１００１の順に行われて、全ての中継ノードに付加広告指示テーブル１０２２が生成され、これをもとに、以下に説明する配送フェーズにおいて、広告データの付加・差し替え処理が行われる。
【０２３９】
次に、図５１は、本応用例における第２の方法例に係る配送フェーズの具体的動作例を示す図である。
【０２４０】
同図に示すように、サーバから送出されたストリームデータは、各中継ノード１００１，１００２，１００３の各付加広告指示テーブル１０２２に従って処理される。即ち、中継ノード１００１では、広告データが付加されないままストリームデータが転送され、中継ノード１００２では、当該ストリームデータにカテゴリＡの広告データが付加されて転送され、中継ノード１００３では、既にカテゴリＡの広告データがストリームデータに付加されているので、転送のみが行われる。
【０２４１】
上記の方法は、ネットワーク全体のコストを最小にする。図４６の例において、中継ノード１００２のみにより広告データの付加処理が行われるのは、図４７（ａ）乃至図４７（ｃ）に示したように、Ｇ1002が、Ｇ1001及びＧ1003の要素よりも値の小さい要素を持つためである。例えば、このコスト値に、中継ノードの負荷状態を反映させることにより、負荷分散を行えることが理解される。
【０２４２】
次に、図５２は、本応用例における第２の方法例に係る他の要求フェーズの具体的動作例を示す図であり、図５３（ａ）乃至図５３（ｄ）は他のコスト関数の計算例を示す図である。
【０２４３】
まず、図５２に示すように、複数のクライアントに対して、マルチキャストによりストリームデータを配送する場合、中継ノード１００２や中継ノード１００４のように、複数の子を持つノードが存在するため、図４６に示した例の場合と同様に、ｆk(ｉ，a(1)，a(2)，…，a(c))＝ｇk(ｉ，a(1))＋ｇk(ｉ，a(2))＋…＋ｇk(ｉ，a(c))と分解できる場合を仮定すると、ｊ（ｊ＝１，２，…，ｃ）番目の子からの嗜好ベクタＵj＝（ｕj1，ｕj2，…，ｕjn）に対して、ｆk(ｉ，a(1)，a(2)，…，a(c))＋u1a(1)＋u2a(2)＋…＋uca(c)＝(ｇk(ｉ，a(1))＋u1a(1))＋(ｇk(ｉ，a(2))＋u2a(2))＋…＋(ｇk(ｉ，a(c))＋uca(c))となる。
【０２４４】
従って、各ｊに対しｇk(ｉ，a(j))＋uja(j)の最小値を求めて、その和をとることにより、ｆk(ｉ，a(1)，a(2)，…，a(c))＋u1a(1)＋u2a(2)＋…＋uca(c)の最小値を求めることができる（同図に示す嗜好ベクタ及び付加広告指示テーブル１０２２は、ｇkが図５３（ａ）乃至図５３（ｄ）の各左列に示す形態で与えられたときに、要求フェーズにおいて送出、生成されたものである）。なお、中継ノード１００１や中継ノード１００３は、子が１つであるため、嗜好ベクタ及び付加広告指示テーブル１０２２の計算方法は、図４６に示した例と同様である。
【０２４５】
次に、図５４（ａ）及び図５４（ｂ）は、図５２の中継ノード１００２に関わる部分を示す図であり、図５５（ａ）乃至図５５（ｄ）は、図５４（ａ）及び図５４（ｂ）における中継ノード１００２の計算例を示す図、図５６は、図５２の中継ノード１００２が嗜好ベクタを送出する様子を示す図である。
【０２４６】
まず、図５４（ａ）及び図５４（ｂ）に示すように、中継ノード１００２に対し、中継ノード１００３から嗜好ベクタＵ1＝（２０，１，２０）が、また、中継ノード１００４から嗜好ベクタＵ2＝（４，３，３）が、それぞれ到着したものとする。
【０２４７】
このとき、嗜好ベクタＵ1及びＵ2と、ｇ1002を表す行列Ｇ1002とから、図４７（ａ）乃至図４７（ｃ）に示した例と同様な計算を行うことで、図５５（ａ）乃至図５５（ｃ）に示すような計算結果が得られ、さらに、子ごとの最小値の和をとることにより、図５５（ｄ）に示すように、中継ノード１００１に送出すべき嗜好ベクタＶ1002＝（１６，６，１５）が得られるようになる。そして、図５６に示すように、中継ノード１００２における要求フェーズ処理の完了に伴い、同時に最小値を得るために差し替えるべき広告データのカテゴリが、子ノードごとに中継ノードの付加広告指示テーブル１０２２に設定され、これをもとに、以下に説明する配送フェーズにおいて、所要の広告データの付加・差し替え処理が行われる。
【０２４８】
次に、図５７は、本応用例における第２の方法例に係る他の配送フェーズの具体的動作例を示す図である。
【０２４９】
同図に示すように、サーバから送出されたストリームデータは、各中継ノード１００１，１００２，１００３，１００４の各付加広告指示テーブル１０２２に従って処理される。即ち、中継ノード１００１では、ストリームデータにカテゴリＡの広告データが付加され、中継ノード１００２では、既にカテゴリＡの広告データがストリームデータに付加されているので、転送のみが行われ、中継ノード１００３では、同様の理由で転送のみが行われ、中継ノード１００４では、図示の左の子に対してのみ、カテゴリＢの広告データに差し替えられ、右の子に対しては転送のみが行われる。
【０２５０】
つまり、中継ノード１００１及び中継ノード１００４において、所要の広告データの差し替え処理が行われ、中継ノード１００２及び中継ノード１００３においては、単に転送のみが行われるようになっている。これは、図５３（ａ）乃至図５３（ｄ）に示したように、行列Ｇ1001及びＧ1004の要素の値が、行列Ｇ1002及びＧ1003の要素の値よりも相対的に小さいことを反映している。従って、図４６の例の場合と同様、ｇkに各中継ノード１００１，１００２，１００３，１００４の負荷状態を反映させることにより、ネットワーク全体の負荷分散を実現できることが理解される。
【０２５１】
なお、ストリームデータに広告データを付加することにより、トラヒック量が著しく増加することが予想される場合、マルチキャストツリーを構成する通信リンクの中で、使用可能帯域の狭い通信リンクをストリームデータが通過するときは、それに広告データを付加しない方が有効である。
【０２５２】
これを実現するには、例えば、中継ノードｋとｊ番目の子の間とを結ぶツリー上における通信リンクが混雑しているとすると、ａ(j)≠φのときのコスト関数ｆk(ｉ，a(1)，a(2)，…，a(c))の値を大きめに設定することで、この通信リンクを、ストリームデータが通過するときはなるべく広告データが付加されない状態にすることが可能である。
【０２５３】
一方、サーバからのストリームデータに、視聴者数やそのストリームデータの種類、或いは、時々刻々移り変わる場面の情報などを、広告データとは別に付加しておくことにより、各中継ノードにおいて、クライアントが嗜好するカテゴリに属する広告データの中から、視聴者数などの情報に応じた所定の広告データを選択し、付加・差し替えを行うことなどもできる。
【０２５４】
図５８は、本応用例における第２の方法例に適用可能な視聴者数−広告カテゴリ検索テーブルを示す図である。
【０２５５】
同図に示すように、この視聴者数−広告カテゴリ検索テーブル１０２９は、その行が視聴者数を、列が広告カテゴリを表しており、「Ａ１」，「Ａ２」，「Ａ３」が、広告カテゴリＡに属する広告データを、「Ｂ１」，「Ｂ２」，「Ｂ３」が、広告カテゴリＢに属する広告データを、「Ｃ１」，「Ｃ２」，「Ｃ３」が、広告カテゴリＣに属する広告データを、それぞれ表している。
【０２５６】
以上に示す視聴者数−広告カテゴリ検索テーブル１０２９を、付加広告指示テーブル１０２２に加えて各中継ノードＮ２に置くことにより、視聴者数に応じて、付加・差し替えを行うべき広告データを変更することができる。
【０２５７】
例えば、要求フェーズで作成される付加広告指示テーブル１０２２により、カテゴリＢの広告データを付加（差し替え）するよう指示されている場合、サーバからのストリームデータに付加されている視聴者数情報が「５０００」ならば、「Ｂ２」なる広告データを付加（差し替え）するようにすればよい。このような方法を採用することにより、広告主やストリームデータの提供者とユーザとの双方の意向を反映した広告付けを行うことも可能となる。
【０２５８】
（プログラム例及び記録媒体例）
続いて、以上に説明した第１及び第２の方法例の実施に適用しうるプログラム例、及び記録媒体例について説明する。
【０２５９】
実施形態１の最後で述べたように、中継ノードＮ１，Ｎ２は、パケットからなるストリームデータの送受信を行うコンピュータにより構成される。従って、以上に説明した第１及び第２の方法例は、これを実行手順としてプログラム化することが可能である。
【０２６０】
この場合、所要のプログラムとしては、例えば、（ａ）中継ノードのルート側隣接ノードからストリームデータの転送を受けたときに、各クライアントの嗜好と広告データの付加コストとの間の相関を表した嗜好ベクタに基づき、存在する１以上のリーフ側隣接ノードごとに付加広告指示テーブル１０１２，１０２２として事前に分類定義された広告データのカテゴリを選択する処理ステップと、（ｂ）転送されてきたストリームデータに広告データが付加されていない場合に、選択されたカテゴリに対応して広告データ記憶手段１０１１，１０２１に事前に登録されている広告データを各リーフ側隣接ノードへ転送する処理ステップと、（ｃ）転送されてきたストリームデータに広告データが既に付加されており、かつ、当該広告データが、選択されたカテゴリのものと異なる場合に、その広告データを、当該カテゴリに対応して広告データ記憶手段１０１１，１０２１に事前に登録されている広告データに差し替えて各リーフ側隣接ノードへ転送する処理ステップと、（ｄ）転送されてきたストリームデータに広告データが既に付加されており、かつ、当該付加データが、選択されたカテゴリのものと同じ場合に、当該ストリームデータを各リーフ側隣接ノードへそのまま転送する処理ステップとを具備させればよい。
【０２６１】
また、以上のプログラムを構成する各処理ステップからなる一連の手続を任意の記録媒体に書き込んでおき、これを、実行に先立って中継ノードＮ１，Ｎ２（ネットワークを構成する全ての中継ノード）に導入すれば、所要の広告データ付加機能に関する処理が実現されるようになる。
【０２６２】
以上、第１及び第２の装置例及びネットワークシステム装置例並びに方法例、並びにプログラム及び記録媒体につき、ストリームデータに付加すべき所要の付加データとして、広告データを例に挙げて説明したが、これは、単に本発明の一適用例に過ぎず、本発明は、他の任意の付加データに対しても同様に適用可能である。
【０２６３】
（第１の変形例）
続いて、以上に説明した第１及び第２の装置例及びネットワークシステム装置例並びに方法例、並びにプログラム及び記録媒体の変形例として、ストリームデータのデータ形式を変換する場合の例について２つの変形例を説明する。これら変形例はマルチキャスト通信に対する付加機能であるデータ変換機能の第２の例である。なお、この第１の変形例では、ストリームデータのデータ形式が、存在する全ての種別につき互いに変換可能である（可逆性を有する）場合であってもそうでない場合であっても良い。
【０２６４】
図５９は、本変形例に係る中継ノードの内部構成を示すブロック図である。ストリームデータのデータ形式変換を行う場合、中継ノードＮ３として、第１及び第２の装置例にそれぞれ示した広告データ記憶手段（１０１１，１０２１）に代わる記憶手段１０４１、付加広告指示テーブル（１０１２，１０２２）に代わる変換指示テーブル１０４２、及び広告付加・差し替え手段（１０１４、１０２４）に代わるデータ形式変換手段１０４４を新たに構成し、さらに、当該各装置例におけるそれと同様な受信手段１０４３、送信手段１０４５、嗜好情報抽出手段１０４６、嗜好情報テーブル１０４７、及び嗜好情報集計手段１０４８を設定する。
【０２６５】
以上のうち、記憶手段１０４１は、存在する各クライアントに配信しようとするストリームデータのデータ形式を各クライアントが受信可能な形式に変換するためのデータ形式変換手段１０４４を、要求される複数のカテゴリに亙って事前に記憶するものであり、変換指示テーブル１０４２は、各クライアントの嗜好とストリームデータのデータ形式変換コストとの間の相関を表した嗜好ベクタに基づき、存在する１以上のリーフ側隣接ノードにおいて採用すべきデータ形式変換手段１０４４のカテゴリを、リーフ側隣接ノードごとに事前に分類定義したものである。
【０２６６】
また、データ形式変換手段１０４４は、受信手段１０４３で受信されたストリームデータのデータ形式に応じ、各リーフ側隣接ノードにおいて採用すべきデータ形式変換手段１０４４のカテゴリを、変換指示テーブル１０４２を参照して選択すると共に、その選択したカテゴリに対応して記憶手段１０４１に記憶されているデータ形式変換手段１０４４を読み出し、当該読出しに係るデータ形式変換手段１０４４によりストリームデータのデータ形式を変換するものである。
【０２６７】
なお、以上のように構成された中継ノードにより、マルチキャストデータ通信システムを構成するには、単一のサーバから１以上のクライアントに向けストリームデータを配信するためのマルチキャストツリー形のネットワークを構成し、当該ネットワークに、以上の中継ノードを複数の中継ノードにそれぞれ割り当てればよい。
【０２６８】
また、その方法の実施に際しては、第１及び第２の方法例で説明した広告データのカテゴリＡ，Ｂ，φを、それぞれ、互いに翻訳可能な言語であると解釈し、中継ノードが翻訳機能を具備しているものとして説明することができる。これにより、サーバが言語φで記述されたストリームデータを送出し、それを、クライアントに届くまでの経路上にある中継ノードにおいて翻訳することにより、クライアントが要求する言語で記述されたストリームデータを送り届けるサービスに利用することができる。
【０２６９】
例えば、ストリームデータの一例として、映像データなどに対する翻訳を想定すれば、その翻訳とは、エンコード方式の変換又はメディア変換と解釈することができる。但し、この種のデータ変換は片方向にしか行えない場合も少なくないため、本変形例における方法の適用に際しては、以上のデータ変換の特質を考慮するようにする。
【０２７０】
図６０は、本応用例における第１の変形例に係る要求フェーズの具体的動作を示す図であり、図６１は、同変形例における配送フェーズの具体的動作を示す図である。
【０２７１】
まず、図６０に示すように、サーバは、所要のストリームデータをエンコード方式Ｃで送出し、３つのクライアントは、それとは異なるエンコード方式Ａ又はＢによりストリームデータを受信する。但し、以上の各エンコード方式のうち、方式Ｂから方式Ａへの変換は可能であるが、その逆の方式Ａから方式Ｂへの変換はできないものとする（これを「Ｂ⊃Ａ」と表す）。また、本図の説明では、コストモデルとして、簡単化のため、図４０で説明したものと同じコストモデルを用いているが、図４６で説明した一般的なコストモデルに対しても拡張可能である。
【０２７２】
ここで、「Ａ」，「Ｂ」，「Ｃ」を、それぞれ、１番目，２番目，３番目のエンコード方式とした場合、中継ノード１００４は、２つの子から嗜好ベクタ（０，１，０），（１，０，０）を受け取るが、Ｂ⊃Ａであるので、中継ノード１００２に対しては、エンコード方式Ａを要求することはできないため、嗜好ベクタ（０，１，０）を送信する。
【０２７３】
これに対し、中継ノード１００２は、２つの子から、嗜好ベクタ（１，０，０），（０，１，０）を受け取るが、Ｂ⊃Ａであるので、中継ノード１００１に対しては、嗜好ベクタ（０，１，０）を送信する。
【０２７４】
そして、以上の結果、当該要求フェーズにおいて、図示のような変換指示テーブルが各中継ノード１００１，１００２，１００３，１００４に設定され、配送フェーズにおいて、図６１に示すようなエンコード方式の変換が実現される。但し、サーバが送出するデータ形式は、エンコード方式Ｂに変換可能であるとする（そうでない場合は、このようなサービス自体が成り立たない）。
【０２７５】
なお、本変形例においてプログラムを構成する場合、当該プログラムに、例えば、（ａ´）中継ノードのルート側隣接ノードからストリームデータの転送を受けたときに、各クライアントの嗜好とストリームデータのデータ形式変換コストとの間の相関を表した嗜好ベクタに基づき、ストリームデータのデータ形式を各クライアントが受信可能な形式に変換するため、存在する１以上のリーフ側隣接ノードごとに変換指示テーブルとして事前に分類定義されたデータ形式変換手段のカテゴリを選択する処理ステップと、（ｂ´）転送されてきたストリームデータのデータ形式を得るためのデータ形式変換手段が、選択されたカテゴリのものと異なる場合に、当該ストリームデータを、当該カテゴリに対応して記憶手段に事前に登録されているデータ形式変換手段により変換して各リーフ側隣接ノードへ転送する処理ステップと、（ｃ´）転送されてきたストリームデータのデータ形式を得るためのデータ形式変換手段が、選択されたカテゴリのものと同じ場合に、当該ストリームデータを各リーフ側隣接ノードへそのまま転送する処理ステップとを具備させればよい。
【０２７６】
また、以上のプログラムを構成する各処理ステップからなる一連の手続を任意の記録媒体に書き込んでおき、これを、実行に先立って中継ノード（ネットワークを構成する全ての中継ノード）に導入すれば、所要のデータ変換機能に関する処理が実現されるようになる。
【０２７７】
（第２の変形例）
続いて、第２の変形例として、ストリームデータのデータ形式が、存在する全ての種別につき互いに変換可能とは限らない（不可逆性を有するものが存在する）場合の他の例を、前述した第１及び第２の方法例に基づいて説明する。なお、以降の説明では、存在する全データ形式中に、クライアントが要求する何れのデータ形式にも変換可能なデータ形式が、少なくとも１つは存在するものと仮定する（この仮定を無視した場合、全てのクライアントを１つのマルチキャストツリーに収容することは不可能となる）。
【０２７８】
まず、図６２は、本応用例の第２の変形例において、第１の方法例で説明したストリームデータにおけるデータ形式間の変換に関する制約を規定した変換制約グラフ（有向グラフ）を示す図である。
【０２７９】
図示の変換制約グラフ１０３０において、各節点に示す数字は、存在する全データ形式の種別（全４種）をそれぞれ表しており、データ形式ｉからデータ形式ｊへの変換が可能であるとき、節点ｉから節点ｊへ至る有向枝（ｉ，ｊ）が存在する。但し、データ形式ｉをデータ形式ｊへ実際に変換する際に、中間に他の１以上のデータ形式を経る必要がある場合も、「データ形式ｉからデータ形式ｊへの変換が可能である」と定義する。
【０２８０】
これは、第１の方法例で述べたコストモデルでは、任意のデータ形式変換がコスト「１」で行われるので、該当するデータ形式が直接変換可能であるか否については、何ら意味を持たないためである。従って、節点ｉから節点ｊに有向路が存在すれば、必ず有向枝（ｉ，ｊ）が存在する。
【０２８１】
なお、以上の変換制約グラフ１０３０は、第１の方法例の適用を受ける第１の装置例に示した中継ノードＮ１の嗜好情報集計手段１０１８に予め保持させるか、或いは、受信手段１０１３を通じて１以上のリーフ側隣接ノードから転送されてくる嗜好ベクタに、データとして付加させるようにすればよい。
【０２８２】
次に、図６３は、図６２に示した変換制約グラフ１０３０が与えられた場合における各中継ノード又はクライアントが送出する嗜好ベクタと、この嗜好ベクタに対応して配送されるストリームデータとの関係を示す図である。
【０２８３】
なお、嗜好ベクタは、第１の方法例と同様に定義する。即ち、全データ形式数をｎとすると、嗜好ベクタは、要素を「１」又は「０」とするｎ次元ベクタ（ｎビットベクタ）であり、そのｎビット中のｉビット目が「１」であれば、ｉ番目のデータ形式が要求されていることを表す。
【０２８４】
ここで、図示の中継ノード１００１を例として嗜好ベクタの集約方法を説明すれば、嗜好ベクタの定義より、中継ノード１００２は、２番目又は４番目のデータ形式を要求していることが理解される。これらのデータ形式で中継ノード１００１から中継ノード１００２にストリームデータを送り出すためには、変換制約グラフ１０３０の規定により、当該ストリームデータは、２番目、３番目、又は４番目のデータ形式である必要がある。
【０２８５】
このように、中継ノード（又はクライアント）ｊが要求するデータ形式に変換可能な、親ノードからのストリームデータのデータ形式の集合をＳjで表せば、Ｓ1002＝｛２，３，４｝，Ｓ1003＝｛２，３，４｝，Ｓ1005＝｛１，２，３｝となる（ｊ＝４は欠番）。
【０２８６】
このとき、全ての子ノードからの要求を満たすためには、親ノードからのストリームデータのデータ形式は、Ｓ1002∩Ｓ1003∩Ｓ1005＝｛２，３｝でなくてはならない。従って、ここでは、２番目又は３番目のデータ形式を親ノードに対して要求することになる。
【０２８７】
また、全ての子ノードからの嗜好ベクタの和は（１，２，１，２）であるので、親ノードからのストリームデータが２番目のデータ形式であるときの方が、中継ノード１００１における変換コストが少ない。従って、中継ノード１００１は、親ノード（図示の「サーバ１０１０」）に対し（０，１，０，０）を送出する。
【０２８８】
一方、中継ノード１００２及び１００３にて生成される嗜好ベクタ（０，１，０，１）及び（０，０，１，１）は、Ｓ1006＝｛１，２，３，４｝，Ｓ1007＝｛２，３，４｝，Ｓ1008＝｛１，２，３，４｝，及びＳ1009＝｛２，３，４｝であることに基づいて導くことができる。上記Ｓjの積集合は、任意のデータ形式に変換可能なデータ形式が少なくとも１つは存在するので、空集合であることはない。
【０２８９】
各中継ノードでの嗜好ベクタの集約方法をまとめれば、以下のようになる。
１．各子ｊからの嗜好ベクタと変換制約グラフ１０３０からＳjを計算する。
２．各子ｊからの嗜好ベクタの和（ｓ1，ｓ2，…，ｓn）を計算する。
３．Ｓjの積集合の要素をｉとし、ｓiの集合の中で最大値をとるｉの集合をＩとする。
４．親ノードへ送出する嗜好ベクタは（ｂ1，ｂ2，…，ｂn）。但し、ｉ’がＩの要素であれば、ｂi'＝１とし、そうでなければ、ｂi'＝０とする。
【０２９０】
なお、各中継ノードには、第１の方法例と同様に、各子からの嗜好ベクタを満足するデータ形式にストリームデータが変換されるように、変換指示テーブルが生成される。但し、嗜好ベクタ更新時のタイミングなどにより、一時的に、要求したデータ形式以外のデータ形式で、親ノードからストリームデータが到着した場合は、子が要求するデータ形式に変換可能であれば変換し、変換不可能であればデータパケット自体を破棄すればよい。
【０２９１】
このことは、パケットの順序が入れ替わることがない安定したネットワークであれば、さほど問題にはならない。なぜなら、各クライアントや中継ノードが、同じ嗜好ベクタを定期的に送信し続けている間は、以下の理由により、要求したデータ以外のデータ形式で親ノードからストリームデータが届くことはないからである。
【０２９２】
即ち、当該親ノードは、常に子ノードの要求が満たされるように嗜好ベクタを計算するので、上記クライアント又は中継ノード以外の親ノードの子が嗜好ベクタを変更したとしても、親ノードが新たに生成する嗜好ベクタにより要求するストリームデータは、やはり、上記クライアント又は中継ノードが要求するデータ形式に変換可能であるからである。
【０２９３】
ところで、変換制約の特別な場合として、ｉ1＜ｉ2ならば、ｉ2番目のデータ形式からｉ1番目のデータ形式への変換は可能であるが、その逆は不可能であるとする制約が考えられる。この場合、嗜好ベクタの計算は、次のように簡単化できる。
【０２９４】
即ち、中継ノード（又はクライアント）ｊからの嗜好ベクタを（ｂj1，ｂj2，…，ｂjn）、ｂji＝１を満たす添字ｉの最小値をmin(j)とし、全ての子ｊにわたるmin(j)の最大値をＴとすると、全ての子ｊに対するＳjの積集合は、集合｛ｉ｜ｉ≧Ｔ｝である。
【０２９５】
例えば、図６４（変換制約が特別な場合の例）に示す中継ノード１００１の場合、min(2)＝２，min(3)＝３，min(5)＝１であるから（ｊ＝４は欠番）、Ｔ＝３となり、Ｓ1002∩Ｓ1003∩Ｓ1005＝｛３，４｝となる。このとき、３つの子からの嗜好ベクタの和は（１，２，１，２）であるので、中継ノード１００１は、親ノード（図示の「サーバ１０１０」）に対し（０，０，０，１）を送出する。
【０２９６】
以上、第１の方法例で述べたコストモデルに基づく変換制約の対応方法について説明したが、これに対し、第２の方法例で述べたコストモデルでは、関数ｆk(ｉ，a(1)，a(2)，…，a(c))の値を次のように設定することで、所要の変換制約に対応することができる。
【０２９７】
即ち、データ形式ｉからは変換不可能なデータ形式が、a(1)，a(2)，…，a(c)の中に含まれている場合は、ｆk(ｉ，a(1)，a(2)，…，a(c))＝∞（無限大）と設定することにより、このような(ｉ，a(1)，a(2)，…，a(c))の組み合わせを除外することができる。また、ｆk(ｉ，a(1)，a(2)，…，a(c))の値には、データ形式間の変換コストの違いを反映させることができる。
【０２９８】
図６５は、本発明の第２の変形例において、第２の方法例で説明したストリームデータにおけるデータ形式間の変換に関する制約を規定した変換制約グラフ（有向グラフ）を示す図である。なお、各有向枝のラベルは、対応するデータ変換コストを表している。
【０２９９】
ここで、同図に示す変換制約グラフ１０３１が与えられた場合において、第２の方法例と同様に、ｆk(ｉ，a(1)，a(2)，…，a(c))＝ｇk(ｉ，a(1))＋ｇk(ｉ，a(2))＋…＋ｇk(ｉ，a(c))と分解できる場合を考え、さらに、ｇk(ｉ，a(ｊ))を有向枝(ｉ，a(ｊ))のラベルと定義すれば、ｆk(２，１，１，３)＝ｇk(２，１)＋ｇk(２，１)＋ｇk(２，３)＝３＋３＋２＝８と計算される。
【０３００】
このように、各データ形式間の変換コストを(ｉ，a(1)，a(2)，…，a(c))の値に反映させることにより、マルチキャストツリー全体として、より緻密な変換コスト最小化を実現することが可能となる。
【０３０１】
なお、以上の変形例によれば、第２の方法例で述べたような、ｆk(ｉ，a(1)，a(2)，…，a(c))の値に、ノードの負荷状態や通信リンクの使用可能帯域を反映させることなども可能である。
【０３０２】
即ち、ノードの負荷状態を反映させるには、負荷の重い中継ノードでは、関数ｆk(ｉ，a(1)，a(2)，…，a(c))の値を他の中継ノードの関数の値よりも大きく設定することにより、第２の方法例で述べたように、負荷の重い中継ノードにおける変換処理を、なるべく避けるようにすることができる。
【０３０３】
また、通信リンクの使用可能帯域を反映させるには、親ノードとの間の通信リンクが混雑している場合に、必要帯域の大きいデータ形式から他のデータ形式への変換コストを大きめに設定することにより、その必要帯域の大きいデータ形式のストリームデータが上記混雑している通信リンクを通過する可能性を低減することができる。
【０３０４】
（マルチキャスト通信への応用）
次に、本応用例における中継ノードの全体の構成について説明する。図６６は中継ノードＮ４の全体構成の詳細を示したブロック図であって、図３３及び図３８に示したものと同じ構成要素については同一の符号を付している。なお、図中の太実線はデータパケットの流れを示し、細実線は受信要求パケットの流れを示し、点線は制御信号の流れを示している。
【０３０５】
図６６に示した通り、中継ノードの全体構成は基本的に図３３及び図３８の構成要素を合わせたものである。ただし、図３３の受信手段７７及び送信手段７６がそれぞれ図３８の受信手段１０１３及び送信手段１０１５と共通化されているほか、以下に述べるように幾つかの構成要素が一部変更されている。
【０３０６】
まず、配信テーブル管理手段１１７４は配信テーブル７３に加えて付加広告指示テーブル１０１２及び嗜好情報テーブル１０１７も管理（生成，更新，削除）するように構成される。ノード負荷測定手段１１７２は、中継ノードの負荷状態をコスト値に反映させるために嗜好情報集計手段１１１８に対しても測定した負荷状態を送信する。嗜好情報集計手段１１１８は、ノード負荷測定手段１１７２から受信した負荷状態に基づいて自身の中継ノードが高負荷であるかどうか判断し、高負荷であれば子ノードからの受信要求パケットをそのまま親ノードに向かって転送するための指示をパケット生成手段１１７５に送出する。また、嗜好情報集計手段１１１８は、嗜好ベクタに対して集約的演算を施す際にタイムアウトした子の嗜好情報を集約の対象外とするために、配信テーブル７３を参照する。また、パケット生成手段１１７５は嗜好情報集計手段１１１８からの指示が送られた場合に受信要求パケットをソースアドレスを現在のノードのアドレスに変えて親ノードに向けて転送する。
【０３０７】
次に、図６７は本応用例における受信要求パケットのフォーマットを示した図であって、図３６と同じフィールドには同一の符号を付けている。図３６との違いは嗜好ベクタ１１７のフィールドが追加されている点である。つまり、本応用例では受信要求パケットに嗜好ベクタが載せられている。上述したように、実施の形態１ないし３では受信要求パケットが定期的に送出され、データパケットは受信要求パケットが通過した経路の逆順を辿って配信される。一方、本応用例では嗜好ベクタを載せたパケットに基づいてデータパケット上のデータに対するデータ形式変換方法を決定しており、嗜好ベクタを載せたパケットはデータパケットが通過する経路と同じ経路をたどる必要がある。また、クライアントの嗜好の変化に対応した嗜好ベクタの変更に追随するには、少なくとも嗜好ベクタが変化したときに嗜好ベクタを載せたパケットを再送する必要がある。こうしたマルチキャスト配信とデータ変換機能の類似性に鑑み、受信要求パケットに嗜好ベクタを載せてデータ変換機能を効率的に実現するようにしている。
【０３０８】
また、図６８は本応用例におけるデータパケットのフォーマットを示した図であって、図３７と同じフィールドには同一の符号を付けている。図３７との違いはチャネルＩＤ１２５とデータ１２６の間にデータ形式制御情報１２７及びデータ形式１２８の各フィールドが挿入されている点である。データ形式制御情報１２７は、データ１２６に対して部分的に変換処理を施す場合（広告データの付加あるいは差し替えを行う場合）に用いられるものであって、変換処理の対象となる部分の位置を示している。例えば広告データの差し替えを行う場合、データ形式制御情報１２７は差し替え対象となる部分を示す。
【０３０９】
一方、データ形式１２８はデータ１２６を記述しているデータ形式の名称を表している。１つのマルチキャストツリーの中では、広告データの付加／差し替えを行う処理とデータ形式の変換処理の双方を行うことが可能である。このため、データ形式１２８は、ストリームデータの符号化方式（例えばＭＰＥＧ１，ＭＰＥＧ２）である場合もあるし、ストリームに付加された広告データ等を示すデータ名である場合もあるし、あるいは、これらの双方を同時に表している場合もある。各中継ノードはデータ形式１２８として取りうる全ての値に対してそれぞれ変換処理ルーチンを持っており、これら変換処理ルーチンの中でデータ形式制御情報１２７が参照される。なお、広告データの付加あるいは差し替えが行われる場合、データ１２６はストリームデータの他に広告データも含んでいる。
【０３１０】
そして図６６に示した中継ノードの動作は次のようになる。受信要求パケットが中継ノードＮ４に到着すると、受信手段１１７７を介して配信テーブル管理手段１１７４にこの受信要求パケットが渡され、マルチキャスト通信に係る上述した実施の形態１ないし実施の形態３で説明した通りの動作がなされる。ただし、この際、配信テーブル７３の生成・削除または配信テーブル７３を構成する各エントリの生成・削除と同期して、嗜好情報テーブル１０１７及び付加広告指示テーブル１０１２の生成・削除または嗜好情報テーブル１０１７及び付加広告指示テーブル１０１２を構成する各エントリの生成・削除が行われる。
【０３１１】
一方、受信要求パケットは受信手段１１７７を介して嗜好情報抽出手段１０１６にも渡され、本応用例において上述したように処理される。ただし、嗜好情報集計手段１１１８は、嗜好情報テーブル１０１７上の嗜好ベクタに対して集約的演算を施すにあたっては、配信テーブル７３を参照してタイムアウトした子の嗜好情報を集約の対象外としている。
他方、データパケットは受信手段１１７７を介してパケット複製手段７８に渡され、マルチキャスト通信に係る上述した実施の形態１ないし実施の形態３で説明した通りの動作がなされたのち、広告付加・差し替え手段１１１４に渡されて本応用例において上述したように処理されて送信手段１１７６から送出される。
【０３１２】
次に、図６９は本応用例によるクライアントの内部構成を示したブロック図であって、図３２に示したものと同じ構成要素については同一の符号を付けている。本応用例では図３２の構成に対して、ユーザの嗜好に関する情報を取得して嗜好ベクタを生成する嗜好情報取得手段１２０１が追加されている。そして、パケット生成手段１１６２は、時計６１を用いて受信要求パケットを定期的に生成する際に、嗜好情報取得手段１２０１からの嗜好ベクタを受信要求パケットに載せるようにしている。なお、図中、太実線はデータパケットの流れを示し、細実線は受信要求パケットの流れを示し、点線は制御信号の流れを示している。
【０３１３】
なお、図６６では配信テーブル７３，付加広告指示テーブル１０１２，嗜好情報テーブル１０１７を別々のテーブルで構成していたが、これらを単一のテーブルに統合すると効率が良い。図７０はこうした統合型配信テーブルの一例を示したものである。図示したように、統合型配信テーブルは子番号、アドレス，ポート，受信要求パケット到着時間，嗜好ベクタ，広告の各フィールドが組になって構成されている。
【０３１４】
「子番号」，「アドレス」，「受信要求パケット到着時間」の各フィールドは図２に示したものと同様である。「ポート」フィールドは図３５で説明した配信テーブル上における「受信ポート」フィールドに相当する。「嗜好ベクタ」フィールドは各子から送られてくる嗜好ベクタが格納される。「広告」フィールドは親ノードから送られてくる可能性がある広告データのカテゴリφ，Ａ，Ｂ，Ｃ（例えば図３９（ｂ）における「Ｉｎ」に相当）の各々について子に配信される広告データのカテゴリ（例えば図３９（ｂ）における「Ｏｕｔ１」あるいは「Ｏｕｔ２」に相当）が子毎に格納される。
【０３１５】
本発明の応用例によれば、各クライアントの嗜好に合った広告などの付加データをコンテンツデータに効率良く付加することが可能になると共に、コンテンツデータの配信過程において、当該コンテンツデータのデータ形式を各クライアントが受信可能な形式に変換することが可能となり、これに加え、所要のコンテンツデータの配信を、各中継ノード自身の負荷状態や当該各中継ノードの通信リンクの負荷状態を考慮して行うことが可能となる。
【０３１６】
以上、本発明の実施の形態を説明したが、本発明は、必ずしも上述した手段と手法及び手順並びに手続にのみ限定されるものではなく、本発明にいう目的を達成し、後述の効果を有する範囲内において、適宜変更実施することが可能なものである。
【０３１７】
例えば、以上の説明では、コンテンツデータの一例として、ストリームデータを挙げたが、これは、単に本発明の一適用例に過ぎず、本発明は、他の任意のコンテンツデータに対しても同様に適用可能である。
【０３１８】
【発明の効果】
本発明によれば、中継装置は、受信装置が定期的に送出する受信要求メッセージ又は送信装置からのデータのいずれか一方だけを受信しても配信表を生成することはない。このため、悪意のあるユーザが多数のアドレス宛てに配信表生成のためのパケットを送出する等の攻撃を行っても、無意味な配信表がネットワーク内の中継装置に多数生成されてしまうことはない。したがって、上記攻撃により中継装置の負荷が重くなったりその性能が低下したりといったことを防ぐことができる。
【０３１９】
また本発明によれば、受信装置は受信要求メッセージを定期的に発行し、送信装置または中継装置は予め定めた時間間隔内に受信要求メッセージがこない受信装置に対するマルチキャストデータの配送を停止させることにより、受信装置が故障したり、伝送路でパケットロスが発生した場合にマルチキャストデータの配送を停止可能となる。また、受信装置は受信要求メッセージを定期的に発行し続けるため、受信装置に対する最寄りの中継装置が変化したり、中継装置の負荷状態が変化した場合でも、マルチキャストデータの配送経路の変更が可能となり、さらにまた、受信装置は能動的にパケットを出す状態のみで良く、状態遷移が不要となる。
【０３２０】
さらに請求項５，１５記載の発明によれば、各ユーザの嗜好に合った広告などの付加データを受信装置に配信されるコンテンツデータ等へ効率良く付加することが可能になると共に、コンテンツデータ等の配信過程において、例えば当該コンテンツデータのデータ形式を各受信装置が受信可能な形式に変換することが可能となる。これに加えて、請求項６，１６記載の発明によれば、所要のコンテンツデータ等の配信を、各中継装置自身の負荷状態や当該各中継装置の通信リンクの負荷状態を考慮して行うことが可能となる。
【図面の簡単な説明】
【図１】  本発明の実施の形態１に関わるマルチキャスト通信におけるネットワーク構成の一例を示す説明図である。
【図２】  中継ノードで生成され更新される本発明の実施の形態１に関わる配信テーブルの一例を示す説明図である。
【図３】  本発明の実施の形態１に関わる中継ノードからデータがユニキャストされる過程の説明図である。
【図４】  本発明の実施の形態１に関わる中継ノードからデータがユニキャストされる過程の説明図である。
【図５】  本発明の実施の形態１に関わる更新後の配信テーブルの一例を示す図である。
【図６】  本発明の実施の形態１に関わるマルチキャスト通信におけるネットワーク構成の他の例を示す図である。
【図７】  図６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図８】  図６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図９】  図６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図１０】  図６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図１１】  図６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図１２】  本発明の実施の形態１に関わる受信要求パケット到着時の処理を示すフローチャートである。
【図１３】  図１２中の高負荷時の処理を示すフローチャートである。
【図１４】  本発明の実施の形態１に関わるデータパケット到着時の処理を示すフローチャートである。
【図１５】  図１４中のエントリ削除操作の処理を示すフローチャートである。
【図１６】  本発明の実施の形態２に関わるマルチキャスト通信におけるネットワーク構成の一例を示す図である。
【図１７】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図１８】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図１９】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２０】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２１】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２２】  図１６のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２３】  本発明の実施の形態２に関わる受信要求パケット到着時の処理を示すフローチャートである。
【図２４】  本発明の実施の形態２に関わる配信テーブル生成パケット到着時の処理を示すフローチャートである。
【図２５】  本発明の実施の形態３に関わるマルチキャスト通信におけるネットワーク構成の一例を示す図である。
【図２６】  図２５のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２７】  図２５のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２８】  図２５のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図２９】  図２５のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図３０】  本発明の実施の形態３に関わる受信要求パケット到着時の処理を示すフローチャートである。
【図３１】  本発明の実施の形態３に関わるデータパケット到着時の処理を示すフローチャートである。
【図３２】  本発明の実施の形態１乃至３に関わるクライアントの構成例を示すブロック図である。
【図３３】  本発明の実施の形態１乃至３に関わる中継ノードの構成例を示すブロック図である。
【図３４】  本発明の実施の形態１乃至３に関わるサーバーの構成例を示すブロック図である。
【図３５】  本発明の実施の形態１乃至３における特定ポートを用いたフロー識別の様子を示す図である。
【図３６】  本発明の実施の形態１乃至３における受信要求パケットのフォーマットの一例を示した図である。
【図３７】  本発明の実施の形態１乃至３におけるデータパケットのフォーマットの一例を示した図である。
【図３８】  本発明の応用例における第１の装置例に係る中継ノードの内部構成を示すブロック図である。
【図３９】  本発明の応用例における第１の方法例に係る要求フェーズの概要を示す図である。
【図４０】  本発明の応用例における第１の方法例に係る要求フェーズの具体的動作例を示す図である。
【図４１】  本発明の応用例における第１の方法例に係る配送フェーズの具体的動作例を示す図である。
【図４２】  所要の広告データの付加・差し替え処理を通常の方法により実行した場合のコスト例を示す図である。
【図４３】  本発明の応用例における第１の方法例により広告データの付加・差し替え処理を実行した場合のコスト例を示す図である。
【図４４】  本発明の応用例における第２の装置例に係る中継ノードの内部構成を示すブロック図である。
【図４５】  本発明の応用例における第２の方法例におけるコストモデルの概要を示す図である。
【図４６】  本発明の応用例における第２の方法例に係る要求フェーズの具体的動作例を示す図である。
【図４７】  本発明の応用例における第２の方法例に係るコスト関数の具体例を示す図である。
【図４８】  本発明の応用例における第２の方法例に係る要求フェーズの具体的動作例の一部分を示す図である。
【図４９】  本発明の応用例における第２の方法例に係るコスト関数の計算例を示す図である。
【図５０】  本発明の応用例における第２の方法例に係る要求フェーズの具体的動作例の他の一部分を示す図である。
【図５１】  本発明の応用例における第２の方法例に係る配送フェーズの具体的動作例を示す図である。
【図５２】  本発明の応用例における第２の方法例に係る他の要求フェーズの具体的動作例を示す図である。
【図５３】  本発明の応用例における第２の方法例に係る他のコスト関数の計算例を示す図である。
【図５４】  図５２の中継ノード１００２に関わる部分を示す図である。
【図５５】  図５４（ａ）における中継ノード１００２の計算例を示す図である。
【図５６】  図５２の中継ノード１００２が嗜好ベクタを送出する様子を示す図である。
【図５７】  本発明の応用例における第２の方法例に係る他の配送フェーズの具体的動作例を示す図である。
【図５８】  本発明の応用例における第２の方法例に適用可能な視聴者数−広告カテゴリ検索テーブルを示す図である。
【図５９】  本発明の応用例における第１の変形例に係る中継ノードの内部構成を示すブロック図である。
【図６０】  本発明の応用例における第１の変形例に適用される要求フェーズの具体的動作を示す図である。
【図６１】  本発明の応用例における第１の変形例に適用される配送フェーズの具体的動作を示す図である。
【図６２】  本発明の応用例における第２の変形例において、第１の方法例で説明したストリームデータのデータ形式間の変換に関する制約を規定した変換制約グラフ（有向グラフ）を示す図である。
【図６３】  図６２に示した変換制約グラフが与えられた場合における各中継ノード又はクライアントが送出する嗜好ベクタと、この嗜好ベクタに対応して配送されるストリームデータとの関係の一例を示す図である。
【図６４】  変換制約が特別な場合、即ち、ｉ1＜ｉ2ならば、ｉ2番目のデータ形式からｉ1番目のデータ形式への変換は可能であるが、その逆は不可能であるとする制約が存在する場合における各中継ノード又はクライアントが送出する嗜好ベクタと、この嗜好ベクタに対応して配送されるストリームデータとの関係の一例を示す図である。
【図６５】  本発明の応用例における第２の変形例において、第２の方法例で説明したストリームデータのデータ形式間の変換に関する制約を規定した変換制約グラフ（有向グラフ）を示す図である。
【図６６】  データ変換機能を備えた本発明の応用例による中継ノードの内部構成を示すブロック図である。
【図６７】  データ変換機能を備えた本発明の応用例によるマルチキャストデータ通信システムおける受信要求パケットのフォーマットを示す図である。
【図６８】  データ変換機能を備えた本発明の応用例によるマルチキャストデータ通信システムおけるデータパケットのフォーマットを示す図である。
【図６９】  データ変換機能を備えた本発明の応用例によるマルチキャストデータ通信システムおけるクライアントの内部構成を示す図である。
【図７０】  データ変換機能を備えた本発明の応用例による中継ノードが備える統合型配信テーブルの一例を示した図である。
【図７１】  従来のマルチキャスト通信におけるネットワーク構成の一例を示す説明図である。
【図７２】  中継ノードで生成され更新される従来のテーブルの一例を示す説明図である。
【図７３】  従来のマルチキャスト通信におけるネットワーク構成の他の例を示す図である。
【図７４】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図７５】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図７６】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図７７】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図７８】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図７９】  図７３のネットワーク構成におけるマルチキャストツリーの構成過程の説明図である。
【図８０】  中継ノードから受信ホストへの問い合わせのようすを示す説明図である。
【図８１】  図８０において行った問い合わせ後のテーブルの一例を示す図である。
【符号の説明】
２１，３１−１〜３１−４，４１−１〜４１−４，５１−１〜５１−４，１０２〜１０５，Ｎ１〜Ｎ４，ｋ，１００１〜１００４：中継ノード
２２−１〜２２−４，３２−１〜３２−７，４２−１〜４２−５，５２−１〜５２−５，１００５〜１００９：受信ホスト（クライアント）
３３，４３，５３，１０１，１０１０：送信ホスト（サーバー）
６１，７１，８１：時計
６２，７５，８４，１１６２，１１７５：パケット生成手段
６３，７６，８５，１０１５，１０２５，１０４５，１１７６：送信手段
６４，７７，８６，１０１３，１０２３，１０４３，１１７７：受信手段
６５：映像復号手段
６６：映像表示手段
７２，１１７２：ノード負荷測定手段
７３，８２，１０６，１０７：配信テーブル
７４，８３，１１７４：配信テーブル管理手段
７８，８７：パケット複製手段
８８：配信用データ蓄積手段
１１１，１２１：宛先アドレス
１１２，１２２：宛先ポート
１１３，１２３：送信元アドレス
１１４，１２４：送信元ポート
１１５，１２５：チャネルＩＤ
１１６：高さ
１１７：嗜好ベクタ
１２６：データ
１２７：データ形式情報
１２８：データ形式
１０１１，１０２１：広告データ記憶手段
１０１２，１０２２：付加広告指示テーブル
１０１４，１０２４：広告付加・差し替え手段
１０１６，１０２６，１０４６：嗜好情報抽出手段
１０１７，１０２７，１０４７：嗜好情報テーブル
１０１８，１０２８，１０４８，１１１８：嗜好情報集計手段
１０４１：記憶手段
１０４２：変換指示テーブル
１０４４：データ形式変換手段
１０２９：視聴者数−広告カテゴリ検索テーブル
１０３０，１０３１：変換制約グラフ（有向グラフ）
１２０１：嗜好情報取得手段
【図１】
0003693978.tif 000003
【図２】
0003693978.tif 000004
【図３】
0003693978.tif 000005
【図４】
0003693978.tif 000006
【図５】
0003693978.tif 000007
【図６】
0003693978.tif 000008
【図７】
0003693978.tif 000009
【図８】
0003693978.tif 000010
【図９】
0003693978.tif 000011
【図１０】
0003693978.tif 000012
【図１１】
0003693978.tif 000013
【図１２】
0003693978.tif 000014
【図１３】
0003693978.tif 000015
【図１４】
0003693978.tif 000016
【図１５】
0003693978.tif 000017
【図１６】
0003693978.tif 000018
【図１７】
0003693978.tif 000019
【図１８】
0003693978.tif 000020
【図１９】
0003693978.tif 000021
【図２０】
0003693978.tif 000022
【図２１】
0003693978.tif 000023
【図２２】
0003693978.tif 000024
【図２３】
0003693978.tif 000025
【図２４】
0003693978.tif 000026
【図２５】
0003693978.tif 000027
【図２６】
0003693978.tif 000028
【図２７】
0003693978.tif 000029
【図２８】
0003693978.tif 000030
【図２９】
0003693978.tif 000031
【図３０】
0003693978.tif 000032
【図３１】
0003693978.tif 000033
【図３２】
0003693978.tif 000034
【図３３】
0003693978.tif 000035
【図３４】
0003693978.tif 000036
【図３５】
0003693978.tif 000037
【図３６】
0003693978.tif 000038
【図３７】
0003693978.tif 000039
【図３８】
0003693978.tif 000040
【図３９】
0003693978.tif 000041
【図４０】
0003693978.tif 000042
【図４１】
0003693978.tif 000043
【図４２】
0003693978.tif 000044
【図４３】
0003693978.tif 000045
【図４４】
0003693978.tif 000046
【図４５】
0003693978.tif 000047
【図４６】
0003693978.tif 000048
【図４７】
0003693978.tif 000049
【図４８】
0003693978.tif 000050
【図４９】
0003693978.tif 000051
【図５０】
0003693978.tif 000052
【図５１】
0003693978.tif 000053
【図５２】
0003693978.tif 000054
【図５３】
0003693978.tif 000055
【図５４】
0003693978.tif 000056
【図５５】
0003693978.tif 000057
【図５６】
0003693978.tif 000058
【図５７】
0003693978.tif 000059
【図５８】
0003693978.tif 000060
【図５９】
0003693978.tif 000061
【図６０】
0003693978.tif 000062
【図６１】
0003693978.tif 000063
【図６２】
0003693978.tif 000064
【図６３】
0003693978.tif 000065
【図６４】
0003693978.tif 000066
【図６５】
0003693978.tif 000067
【図６６】
0003693978.tif 000068
【図６７】
0003693978.tif 000069
【図６８】
0003693978.tif 000070
【図６９】
0003693978.tif 000071
【図７０】
0003693978.tif 000072
【図７１】
0003693978.tif 000073
【図７２】
0003693978.tif 000074
【図７３】
0003693978.tif 000075
【図７４】
0003693978.tif 000076
【図７５】
0003693978.tif 000077
【図７６】
0003693978.tif 000078
【図７７】
0003693978.tif 000079
【図７８】
0003693978.tif 000080
【図７９】
0003693978.tif 000081
【図８０】
0003693978.tif 000082
【図８１】
0003693978.tif 000083