メッセージ配信プログラム、メッセージ配信方法、およびノード
【課題】 ネットワークにおいて、メッセージを配信しながら最短経路木を構築し、重複せずにメッセージを配信するメッセージ配信技術を提供する。
【解決手段】
本発明は、すでに計算済みの最短経路木にメッセージを送信し、受信した他ノードからの返信メッセージに載っているノード接続情報を使って最短経路木を拡張し、その拡張した最短経路木にメッセージを送信することによって、最短経路木の作成とメッセージ配信を同時に行うことを特徴とするメッセージ配信手法に関する。
【解決手段】
本発明は、すでに計算済みの最短経路木にメッセージを送信し、受信した他ノードからの返信メッセージに載っているノード接続情報を使って最短経路木を拡張し、その拡張した最短経路木にメッセージを送信することによって、最短経路木の作成とメッセージ配信を同時に行うことを特徴とするメッセージ配信手法に関する。
【発明の詳細な説明】
【背景技術】
【０００１】
近年、コンピュータネットワークに接続する多数のユーザー間で、特定のデータを要求および提供するためにメッセージを配送するマルチキャスト通信が注目を集めている。
【０００２】
しかし、ネットワーク上の全てのユーザーに対してメッセージを配信する場合、メッセージが重複してネットワークの通信量が大きくなり、負荷がかかってしまう。
【０００３】
これに対し、受信メッセージをキャッシュに格納しておくことで重複したメッセージを破棄する方式（特許文献１参照）や、データ配信の最短経路を求めてからデータを配信する方式（特許文献２参照）が提案されている。
【０００４】
しかしながら、特許文献１では、ネットワークが複雑な場合、破棄される重複メッセージが多くなり、メッセージを識別するＩＤも格納する分、メモリが余計に消費される。また、特許文献２では、実用的な時間で最短経路が求められるネットワークの大きさには限りがあり、最短経路を事前に求めることは難しくなる。さらに、最短経路を求めるサーバが必要である上、同時多発的なデータ配信時に負荷がかかる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−０２１７７０号公報
【特許文献２】特開２００４−２０８２８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述してきた問題を解決するため、本発明では、メッセージを配信しながら最短経路木を構築し、重複せずにメッセージを配信するメッセージ配信技術を提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様は、複数のノードからなるネットワークにおけるメッセージ配信プログラムであって、ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、 前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、前記拡張した最短経路木に前記メッセージを送信するステップと、を送信元ノードに実行させるメッセージ配信プログラムに関する。
【０００８】
上述したように、ノード接続情報を用いて拡張した最短経路木にメッセージを送信する構成とすることによって、重複メッセージをなくすことが可能となる。
【発明の効果】
【０００９】
以上、本発明によれば、返信メッセージのノード接続情報を用いて拡張した最短経路木にメッセージを送信することによって、重複メッセージをなくすことが可能となり、ネットワークにおける通信量を減少させることができる。また、最短経路の計算に必要なネットワーク情報をメッセージ配信しながら収集するのでサーバが不要となる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態になるネットワークにおけるノードの基本構成を示す図である。
【図２】本発明の実施の形態になるノードがメモリに保持する配信情報テーブルのデータ構造を示す図である。
【図３】本発明の実施の形態になる送信メッセージ及び返信メッセージのデータ構造を示す図である。
【図４】本発明の実施の形態になるネットワーク内の各ノードにおける接続情報を説明する図である。
【図５】本発明の実施の形態になるネットワークの最短経路木の計算結果（第１回目）を示す図である。
【図６】本発明の実施の形態になるネットワークの最短経路木の計算結果（第２回目）を示す図である。
【図７】本発明の実施の形態になるネットワークの最短経路木の計算結果（第３回目）を示す図である。
【図８】本発明の実施の形態になる送信元ノードからのメッセージ送信フローを示す図である。
【図９】本発明の実施の形態になる送信メッセージの転送フローを示す図である。
【図１０】本発明の実施の形態になる返信メッセージの送信フローを示す図である。
【図１１】本発明の実施の形態になるネットワークの接続状態が変わった場合の最短経路木の修正を説明する図である。
【図１２】本発明の実施の形態になるネットワークの接続状態が変わった場合の最短経路木の修正結果を示す図である。
【図１３】本発明の実施の形態になる最短経路木のマージ処理フローを示す図である。
【図１４】本発明の実施の形態になる最短経路木のマージを説明する図である。
【発明を実施するための形態】
【００１１】
以下、図面にもとづいて本発明の実施形態を説明する。
【００１２】
図１は、本発明を適用するネットワークの構成例、および該ネットワークを形成する各ノードの基本構成を示している。
【００１３】
本ネットワークは、メッセージの送受信装置である複数のノード１（Ａ、Ｂ・・・Ｇ）とメッセージの送受信経路であるノード１間を結ぶ通信路２とから構成される。以降の実施例では、Ａ、Ｂ・・・Ｇの７個のノード１（ここで、Ａ、Ｂ・・・Ｇは、ノード名を表わしている）が、図のように接続されたネットワーク構成を例として説明する。なお、図では、ノードＡをメッセージの送信元ノードとしている。
【００１４】
各ノード１は、メッセージの受け皿であるメッセージキュー１１（最短経路計算中のメッセージ受信バッファ）を持つメッセージ送受信部１０と、最短経路木を構築する最短経路計算部２０と、メッセージ本文の内容を実行処理するメッセージ処理部３０（例えば、メッセージ本文に転送ファイルがある場合、該ファイルをノードに保存する等の処理）と、それら各部で使用するノード接続情報１０１、最短経路木１０２、及びメッセージ本文１０３のフィールド項目からなる配信情報テーブル１００を格納するデータ格納領域（メモリ）５０とから構成されている。
【００１５】
ここで、ノード１は、図示していないが、ＣＰＵ（Central Processing Unit ）、メモリを有するコンピュータであり、メッセージ送受信部１０、最短経路計算部２０、およびメッセージ処理部３０の各処理を実行するプログラムは、補助記憶装置などに蓄積され、起動時にメモリに展開され、ＣＰＵによって実行処理される。
【００１６】
また、該プログラムは、フレキシブルディスク、ＣＤ（Compact Disk）、ＭＯ（Magneto-Optical Disk）などの可搬の記憶媒体に記録され、各記憶媒体に応じたドライバによって読み取る構成としてもよい。
【００１７】
本発明の一つの特徴は、メッセージ配信と最短経路計算を同時に行うことにある。送信元ノードＡは、ノードの接続情報を記憶した最短経路木（ノードＢ、Ｃ）にメッセージを送信し、ノードＢ、Ｃからの返信メッセージに載っているノード接続情報を使って最短経路木を拡張する。この拡張した最短経路木にメッセージを送信することによって、最短経路木の作成とメッセージ配信が同時に行われる。このように、最短経路計算のアルゴリズムにメッセージ送信を組み合わせることにより、最短経路でメッセージを送信するため、重複メッセージをなくすことが可能となる。最短経路木は、徐々に拡張し大きくなっていくが、最短経路が計算できる限界までメッセージ送信が可能となる。
【００１８】
また、別な特徴は、最短経路配信からマルチキャスト配信に切り替えを可能とすることにある。メッセージ配信時に計算する最短経路木から、最短経路木の深さと平均分枝数を取得し、最短経路木を使うメッセージ配信の総メッセージ数と隣接する全てのノード１にメッセージを送信する従来型のマルチキャスト配信の総メッセージ数を計算する。そして、最短経路木を使う場合の総メッセージ数の方が多くなる場合に、それ以上の最短経路木の更新（拡張）を停止し、最短経路木以外のノード１に対しては、従来のマルチキャスト配信を行う。
【００１９】
さらに、最短経路路木を保持するメモリが限界になった場合にも、配信手法を切り替えることとする。この切り替えにより、メッセージ配信コストが従来手法のコストよりも大きくなることを防ぎ、また、最短経路木作成の限界値を予め計算しなくても、メモリ容量の限界までメッセージを配信することができる。
【００２０】
図２は、ノード１がデータ格納領域５０上に保持する配信情報テーブル１００のデータ構造を示している。配信情報テーブル１００は、ノード接続情報１０１、最短経路木１０２、およびメッセージ本文１０３のフィールド項目から構成されている。
【００２１】
ノード接続情報１０１は、ノード１の接続状態を示し、そのノード間の接続状態をノード対（Ａ：Ｂ、Ａ：Ｃ等）として表わされ、一つ以上のノード対の集合で構成されている。実施例では、ノードＡにおいて、集合｛Ａ：Ｂ、Ａ：Ｃ｝は、ノードＡの接続相手が、ノードＢとノードＣであることを示している。なお、ノード接続情報１０１は、ノード１がネットワークに接続されたタイミングで接続しているノード情報が格納される。
【００２２】
最短経路木１０２のデータは、図１のネットワークの例を用いて示している。最短経路木１０２もノード接続情報と同様に、ノード対の集合で表す。ここで、ノード対には、順番があり、左が親、右が子の関係になり、また、上から下へ根から葉の順序で形成される木構造になっている。また、最短経路木１０２には、ノード１がメッセージの送信元になった際に、最初にノード接続情報からコピーする（後述する図８送信元フローのＳ１１）ことによって格納される。
【００２３】
メッセージ本文１０３では、ユーザがノード１に対してメッセージ送信を要求する際に、送信したい内容をメッセージ本文として渡すことを想定しており、ノード１がこの要求を受けたときに、渡されたメッセージ本文が格納される。
【００２４】
図３は、送信メッセージ２００と返信メッセージ３００のデータ構造を示している。（ａ）は、送信元ノードＡからＢに送信する場合の送信メッセージ２００のデータ構造を示し、（ｂ）は、送信メッセージ２００を受信したノードＢから送信元Ａに返送される場合における返信メッセージ３００のデータ構造を示している。
【００２５】
送信用メッセージ２００は、送信用最短経路木２０２とメッセージ本文２０３から構成され、例えば、「送信用最短経路木」のデータとしては、Ａ：Ｂ、Ａ：Ｃのようなノード対で表されている。また、返信メッセージ３００は、削除経路３０１、返信用最短経路木３０２、およびメッセージ本文３０３の項目から構成されている。例えば、「削除経路」ではＢ：Ｅの経路が削除され、「返信用最短経路木」では、ノードＢからの返信経路として、Ｂ：Ａ、Ｂ：Ｄ、Ｂ：Ｅのノード対が格納されている。
【００２６】
図４は、ノード１の配信情報テーブル１００のデータ構造の一つである、ノード接続情報１０１のデータ構造をネットワーク内の各ノード毎に示している。例えば、ノードＥでは、接続ノードＢ、Ｃ、Ｄ、Ｆが、Ｅ：Ｂ、Ｅ：Ｃ、Ｅ：Ｄ、Ｅ：Ｆのノード対の集合として示されている。
【００２７】
図５〜図７では、最短経路木１０２のデータ構造をネットワークの例を用いて示している。最短経路木１０２もノード接続情報１０１と同様に、ノード対の集合で表わされる。実施例では、ノードＡからメッセージ配信を開始した場合の最短経路木拡張の様子を示しており、図５は、最短経路計算部２０によって計算された第１回目の計算結果によるノードＡの最短経路木１０２を示し、また、図６は、第２回目の計算結果を、図７は、第３回目の計算結果を示している。なお、ネットワーク図中において、最短経路木は太線で示している。
【００２８】
ノードＡの最短経路木は、第１回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、第２回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ、および第３回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ、Ｄ：Ｇとなり、計算の度にその範囲を拡張させている。
【００２９】
図８は、メッセージ送信の手順を説明するフロー図である。本実施例では、送信元のノードＡからメッセージを送信する場合のフローを示している。
【００３０】
まず、ステップＳ１０において、最短経路木１０２にデータが存在するか否かを判定する。最短経路木１０２にデータがなければ、ステップＳ１１において、ノードＡの最短経路計算部２０が、ノードＡの最短経路木１０２にノードＡのノード接続情報１０１をコピーする。
【００３１】
最短経路木１０２にデータがある場合には、ステップＳ１２へスキップし、送信メッセージ２００内の送信用最短経路木２０２にノードＡの最短経路木１０２をコピーし、また、ステップＳ１３において、送信メッセージ２００のメッセージ本文２０３にノードＡのメッセージ本文１０３をコピーする。
【００３２】
さらに、ステップＳ１４において、ノードＡのノード接続情報１０１を集合Ｑ１としてコピーする。そして、ステップＳ１５において、集合Ｑ１が空集合か否かを判定する。
【００３３】
集合Ｑ１が空集合でないとき、ステップＳ１６において、集合Ｑ１からノード対を一つ取り出し、それをｑ（＝Ａ：Ｙ）とする。
【００３４】
ステップＳ１７において、メッセージ送受信部１０が、Ｙに送信メッセージ２００を送信する。ステップＳ１５に戻り、集合Ｑ１が空集合となるまで、ステップＳ１６からＳ１７の処理を繰り返す。集合Ｑ１が空集合になったら、返信メッセージ送信フロー（図１０）に進む。
【００３５】
つぎに、ステップＳ１８において、返信メッセージ送信フローを受けて、最短経路計算部２０が、ノードＡの最短経路木１０２に変化があったかを判定する。変化がなければ終了とし、変化があった場合には、ステップＳ１２に戻り、最短経路木１０２に新たに追加されたノードに対して、以降の処理を繰り返すことによって、最短経路木１０２を更新する。
【００３６】
図９は、送信メッセージ２００を受信したノードが、さらに、子ノードに該メッセージを転送する場合の送信メッセージ転送フローを示している。実施例では、例えば、送信メッセージ２００を受信したノードＢが、子ノードに該メッセージを転送する場合を取り上げて説明する。
【００３７】
まず、ステップＳ２１において、送信元ノードＡから送信メッセージ２００を受信し、ステップＳ２２において、ノードＢの最短経路計算部２０が、送信メッセージ２００内にある送信用最短経路木２０２において、左側がＢであるノード対ｐが存在するか否かを判定する。
【００３８】
送信用最短経路木２０２で左側がＢであるノード対ｐが存在すれば、ステップＳ２３において、ノード対ｐの集合をＱ２とする。つぎに、ステップＳ２４において、集合Ｑ２からノード対を一つ取り出し、それをｑ（＝Ｂ：Ｙ）とする。
【００３９】
そして、ステップＳ２５において、ノード対ｑがノードＢのノード接続情報１０１に含まれるか否かを判定する。含まれていなければ、ステップＳ２６において、ノード対ｑを返信メッセージ３００の削除経路３０１に追加し、ステップＳ２７において、Ｙ宛に該メッセージを転送する。また、ステップＳ２５で、ノード対ｑが含まれているときには、ステップＳ２６をスキップして、ステップＳ２７に進み、転送処理を行う。
【００４０】
つぎに、ステップＳ２８において、集合Ｑ２が空集合か否かを判定する。空集合になったら、返信メッセージ送信フロー（図１０）に進む。また、集合Ｑ２が空集合でないときには、ステップＳ２４に戻り、以降の処理を繰り返す。
【００４１】
一方、ステップＳ２２において、ノード対ｐが存在しないときには、ステップＳ２９に進み、メッセージ処理部３０が、メッセージ本文１０１の実行処理を行い、内容によって処理結果を返信メッセージ本文３０１に格納し、返信メッセージ送信フローへと移行する。
【００４２】
図１０は、返信メッセージの送信フローを示す。本実施例は、例えば、ノードＢが行う処理フローである。なお、返信メッセージ３００には、親の送信元ノードＡへ送信する返信メッセージと、子のノードＤ、Ｅから受信する返信メッセージとが存在するため、以下では、子ノードからの返信メッセージを３００Ｒと表現して区別する。なお、子ノードから戻って来る返信メッセージ３００Ｒのデータ構造も、図３（ｂ）と同様に、削除経路３０１Ｒ、最短経路木３０２Ｒ、およびメッセージ本文３０３Ｒの項目から構成されているものとする。
【００４３】
まず、ステップＳ３１において、返信メッセージ３００の返信用最短経路木３０２にノード接続情報１０１をコピーする。但し、本フローが送信元フローから来た場合は、返信メッセージがないので、返信用最短経路木３０２は、送信元ノードの最短経路木１０２を指す。
【００４４】
つぎに、ステップＳ３２において、最短経路計算部２０は、送受信時にメモリに保持されるメッセージ送受信の状態情報を参照し、子ノードに送信済みのメッセージに対し、受信していない返信メッセージ３００Ｒがあるか否かを判定する。
【００４５】
受信していない返信メッセージ３００Ｒがあれば、ステップＳ３３において、返信メッセージ３００Ｒを受信する。そして、ステップＳ３４において、返信用最短経路木３０２から返信メッセージ３００Ｒの削除経路３０１Ｒを削除する。
【００４６】
さらに、ステップＳ３５において、返信メッセージ３００Ｒの削除経路３０１Ｒを返信メッセージ３００の削除経路３０１に追加し、ステップＳ３６において、返信メッセージ３００Ｒのメッセージ本文３０３Ｒを返信メッセージ３００のメッセージ本文３０３に追加する。なお、本フローが送信元フローから来た場合は、返信メッセージがないので、Ｓ３５、Ｓ３５６のステップはスキップする。
【００４７】
さらに、ステップＳ３７において、返信用最短経路木３０２と、返信メッセージ３００Ｒの返信用最短経路木３０２Ｒをマージする。そして、ステップＳ３２に戻り、受信する返信メッセージ３００Ｒがなくなるまで処理を繰り返す。
【００４８】
受信する返信メッセージ３００Ｒがなければ、ステップＳ３８において、返信先が存在するか否かを判定する。返信先が存在すれば、ステップＳ３８において、返信メッセージ３００を送信メッセージ送信元ノードＡに送信する。返信先が存在しなければ、送信元のメッセージ送信フロー（図８）に戻る。
【００４９】
図１１は、メッセージ配信中にネットワークの接続状態が変わったときに、送信元ノードＡにおける最短経路木１０２の修正過程を示している。ここでは、最短経路計算３回目で、ノードＢ／ノードＥ間の接続が切断された場合を例としている。
【００５０】
（１）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ｝は、ネットワークの最短経路計算２回目の結果によるノードＡの最短経路木１０２を示している。つぎの最短経路計算３回目で、ノードＢからの返信メッセージから削除経路Ｂ：Ｅの情報を取得し、（１）の最短経路木からＢ：Ｅのノード対が削除された（２）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ｝となる。
【００５１】
また、ノードＢからの返信メッセージから返信用最短経路木｛Ｂ：Ａ、Ｂ：Ｄ、Ｄ：Ｇ｝の情報を取得し、（２）の最短経路木をマージして、（３）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ、Ｄ：Ｇ｝が得られる。
【００５２】
さらに、ノードＣの返信メッセージから返信用最短経路木｛Ｃ：Ａ、Ｃ：Ｅ、Ｃ：Ｆ、Ｆ：Ｇ｝の情報を取得し、（３）の最短経路木をマージして、（４）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ、Ｄ：Ｇ、Ｃ：Ｅ｝が得られる。
【００５３】
以上の修正処理によって最終的に得られたノードＡの最短経路木は、図１２のネットワーク図における太線部で表される。
【００５４】
図１３は、あるノードの最短経路木１０２に子ノードからの返信メッセージ３００Ｒに載せられた別の返信用最短経路木３０２Ｒを取り込んでマージ処理するフローを示している。
【００５５】
まず、ステップＳ４１において、子ノードからの返信用最短経路木３０２Ｒの集合Ｓが空集合か否かを判定する。集合Ｓが空でなければ、ステップＳ４２において、集合Ｓからノード対を一つ取り出し、それをｑ（＝Ｘ：Ｙ）とする。
【００５６】
ステップＳ４３において、Ｙがあるノードの最短経路木１０２の根か否かを判定する。あるノードの最短経路木１０２の根でなければ、さらに、ステップＳ４４において、子ノードからの返信用最短経路木３０２Ｒに、右側がＹであるノード対ｐが存在するか否かを判定する。
【００５７】
ノード対が存在すれば、ステップＳ４５において、あるノードの最短経路木１０２のｐをｑに置き換えたとき、根からＹまでの経路が短くなるか否かを判定する。経路が短くなれば、ステップＳ４６において、最短経路木１０２のｐをｑに置き換える。
【００５８】
また、ステップＳ４４で、ノード対が存在しなければ、ステップＳ４７において、最短経路木１０２にｑを追加する。
【００５９】
以上の処理を、別の最短経路木として、子ノードからの返信用最短経路木３０２Ｒの集合Ｓが空集合となるまで繰り返し、空集合となった時点で本フローは終了となる。
【００６０】
図１４は、図１３のマージ処理におけるあるノードの最短経路木をノードＡの最短経路木１０２、また、別な最短経路木を子ノードであるノードＢ及びノードＣからの返信メッセージ３００Ｒに載せられた返信用最短経路木３０２Ｒとした場合のマージ処理の過程を模式的に表したものである。
【００６１】
（１）は、ノードＡの最初の最短経路木｛Ａ：Ｂ、Ａ：Ｃ｝である。これにノードＢからの返信メッセージからの返信用最短経路木｛Ｂ：Ａ、Ｂ：Ｄ、Ｂ：Ｅ｝の情報を取り込んでマージして、（２）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ｝が得られる。さらに、ノードＣからの返信メッセージから返信用最短経路木｛Ｃ：Ａ、Ｃ：Ｅ、Ｃ：Ｆ｝を取り込んで、（３）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ｝が得られる。
【００６２】
以上述べてきたように、本発明では、メッセージ配信と最短経路計算を同時に行うことによって重複メッセージをなくすことができ、ネットワークの通信量を抑えることが可能となる。
【００６３】
さらに、最短経路木が徐々に増大することによるコストアップに対処するため、最短経路配信からマルチキャスト配信へ配信手法を切り替えることが好ましい。その切り替えの仕組みを以下に述べる。
【００６４】
メッセージ配信時に計算する最短経路木から、最短経路木の深さと平均分枝数を取得し、最短経路木を使うメッセージ配信と従来のマルチキャスト配信の総メッセージ数を計算する。最短経路木を使う場合の総メッセージ数の方が多くなる場合は、それ以上の最短経路木更新を停止し、最短経路木以外のノードへは従来のマルチキャスト配信に切り替える。
【００６５】
最短経路木をマージする際に、そのノードの接続数がわかるので、最短経路木が構築されている範囲での平均接続数が計算できる。
【００６６】
つまり、従来のマルチキャスト配信手法の総メッセージ数は、（ノード数）×（平均接続数）として計算できる。一方、最短経路木を使う手法の総メッセージ数は、平均して（ノード数）×（木の深さ）として計算できる。したがって、木の深さが平均接続数を上回ったときに、最短経路木を使う手法から従来手法に切り替えることが可能となる。
【００６７】
また、好ましくは、最短経路木を保持するメモリが限界になった場合にも、配信手法を切り替えるのもよい。
【００６８】
こうした切り替えにより、本発明によるメッセージ配信コストが従来手法のコストよりも大きくなることを防ぐことが可能である。また、最短経路木作成の限界値を予め計算せずに、限界までメッセージ配信することができるメリットを有する。
【産業上の利用可能性】
【００６９】
コンピュータネットワーク上でのメッセージのマルチキャスト配信に関する分野。
【符号の説明】
【００７０】
１ ノード
２ 通信路
１０ メッセージ送受信部
１１ メッセージキュー
２０ 最短経路計算部
３０ メッセージ処理部
５０ データ格納領域
１００ 配信情報テーブル
１０１ ノード接続情報
１０２ 最短経路木
１０３ メッセージ本文
【背景技術】
【０００１】
近年、コンピュータネットワークに接続する多数のユーザー間で、特定のデータを要求および提供するためにメッセージを配送するマルチキャスト通信が注目を集めている。
【０００２】
しかし、ネットワーク上の全てのユーザーに対してメッセージを配信する場合、メッセージが重複してネットワークの通信量が大きくなり、負荷がかかってしまう。
【０００３】
これに対し、受信メッセージをキャッシュに格納しておくことで重複したメッセージを破棄する方式（特許文献１参照）や、データ配信の最短経路を求めてからデータを配信する方式（特許文献２参照）が提案されている。
【０００４】
しかしながら、特許文献１では、ネットワークが複雑な場合、破棄される重複メッセージが多くなり、メッセージを識別するＩＤも格納する分、メモリが余計に消費される。また、特許文献２では、実用的な時間で最短経路が求められるネットワークの大きさには限りがあり、最短経路を事前に求めることは難しくなる。さらに、最短経路を求めるサーバが必要である上、同時多発的なデータ配信時に負荷がかかる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−０２１７７０号公報
【特許文献２】特開２００４−２０８２８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述してきた問題を解決するため、本発明では、メッセージを配信しながら最短経路木を構築し、重複せずにメッセージを配信するメッセージ配信技術を提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様は、複数のノードからなるネットワークにおけるメッセージ配信プログラムであって、ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、 前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、前記拡張した最短経路木に前記メッセージを送信するステップと、を送信元ノードに実行させるメッセージ配信プログラムに関する。
【０００８】
上述したように、ノード接続情報を用いて拡張した最短経路木にメッセージを送信する構成とすることによって、重複メッセージをなくすことが可能となる。
【発明の効果】
【０００９】
以上、本発明によれば、返信メッセージのノード接続情報を用いて拡張した最短経路木にメッセージを送信することによって、重複メッセージをなくすことが可能となり、ネットワークにおける通信量を減少させることができる。また、最短経路の計算に必要なネットワーク情報をメッセージ配信しながら収集するのでサーバが不要となる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態になるネットワークにおけるノードの基本構成を示す図である。
【図２】本発明の実施の形態になるノードがメモリに保持する配信情報テーブルのデータ構造を示す図である。
【図３】本発明の実施の形態になる送信メッセージ及び返信メッセージのデータ構造を示す図である。
【図４】本発明の実施の形態になるネットワーク内の各ノードにおける接続情報を説明する図である。
【図５】本発明の実施の形態になるネットワークの最短経路木の計算結果（第１回目）を示す図である。
【図６】本発明の実施の形態になるネットワークの最短経路木の計算結果（第２回目）を示す図である。
【図７】本発明の実施の形態になるネットワークの最短経路木の計算結果（第３回目）を示す図である。
【図８】本発明の実施の形態になる送信元ノードからのメッセージ送信フローを示す図である。
【図９】本発明の実施の形態になる送信メッセージの転送フローを示す図である。
【図１０】本発明の実施の形態になる返信メッセージの送信フローを示す図である。
【図１１】本発明の実施の形態になるネットワークの接続状態が変わった場合の最短経路木の修正を説明する図である。
【図１２】本発明の実施の形態になるネットワークの接続状態が変わった場合の最短経路木の修正結果を示す図である。
【図１３】本発明の実施の形態になる最短経路木のマージ処理フローを示す図である。
【図１４】本発明の実施の形態になる最短経路木のマージを説明する図である。
【発明を実施するための形態】
【００１１】
以下、図面にもとづいて本発明の実施形態を説明する。
【００１２】
図１は、本発明を適用するネットワークの構成例、および該ネットワークを形成する各ノードの基本構成を示している。
【００１３】
本ネットワークは、メッセージの送受信装置である複数のノード１（Ａ、Ｂ・・・Ｇ）とメッセージの送受信経路であるノード１間を結ぶ通信路２とから構成される。以降の実施例では、Ａ、Ｂ・・・Ｇの７個のノード１（ここで、Ａ、Ｂ・・・Ｇは、ノード名を表わしている）が、図のように接続されたネットワーク構成を例として説明する。なお、図では、ノードＡをメッセージの送信元ノードとしている。
【００１４】
各ノード１は、メッセージの受け皿であるメッセージキュー１１（最短経路計算中のメッセージ受信バッファ）を持つメッセージ送受信部１０と、最短経路木を構築する最短経路計算部２０と、メッセージ本文の内容を実行処理するメッセージ処理部３０（例えば、メッセージ本文に転送ファイルがある場合、該ファイルをノードに保存する等の処理）と、それら各部で使用するノード接続情報１０１、最短経路木１０２、及びメッセージ本文１０３のフィールド項目からなる配信情報テーブル１００を格納するデータ格納領域（メモリ）５０とから構成されている。
【００１５】
ここで、ノード１は、図示していないが、ＣＰＵ（Central Processing Unit ）、メモリを有するコンピュータであり、メッセージ送受信部１０、最短経路計算部２０、およびメッセージ処理部３０の各処理を実行するプログラムは、補助記憶装置などに蓄積され、起動時にメモリに展開され、ＣＰＵによって実行処理される。
【００１６】
また、該プログラムは、フレキシブルディスク、ＣＤ（Compact Disk）、ＭＯ（Magneto-Optical Disk）などの可搬の記憶媒体に記録され、各記憶媒体に応じたドライバによって読み取る構成としてもよい。
【００１７】
本発明の一つの特徴は、メッセージ配信と最短経路計算を同時に行うことにある。送信元ノードＡは、ノードの接続情報を記憶した最短経路木（ノードＢ、Ｃ）にメッセージを送信し、ノードＢ、Ｃからの返信メッセージに載っているノード接続情報を使って最短経路木を拡張する。この拡張した最短経路木にメッセージを送信することによって、最短経路木の作成とメッセージ配信が同時に行われる。このように、最短経路計算のアルゴリズムにメッセージ送信を組み合わせることにより、最短経路でメッセージを送信するため、重複メッセージをなくすことが可能となる。最短経路木は、徐々に拡張し大きくなっていくが、最短経路が計算できる限界までメッセージ送信が可能となる。
【００１８】
また、別な特徴は、最短経路配信からマルチキャスト配信に切り替えを可能とすることにある。メッセージ配信時に計算する最短経路木から、最短経路木の深さと平均分枝数を取得し、最短経路木を使うメッセージ配信の総メッセージ数と隣接する全てのノード１にメッセージを送信する従来型のマルチキャスト配信の総メッセージ数を計算する。そして、最短経路木を使う場合の総メッセージ数の方が多くなる場合に、それ以上の最短経路木の更新（拡張）を停止し、最短経路木以外のノード１に対しては、従来のマルチキャスト配信を行う。
【００１９】
さらに、最短経路路木を保持するメモリが限界になった場合にも、配信手法を切り替えることとする。この切り替えにより、メッセージ配信コストが従来手法のコストよりも大きくなることを防ぎ、また、最短経路木作成の限界値を予め計算しなくても、メモリ容量の限界までメッセージを配信することができる。
【００２０】
図２は、ノード１がデータ格納領域５０上に保持する配信情報テーブル１００のデータ構造を示している。配信情報テーブル１００は、ノード接続情報１０１、最短経路木１０２、およびメッセージ本文１０３のフィールド項目から構成されている。
【００２１】
ノード接続情報１０１は、ノード１の接続状態を示し、そのノード間の接続状態をノード対（Ａ：Ｂ、Ａ：Ｃ等）として表わされ、一つ以上のノード対の集合で構成されている。実施例では、ノードＡにおいて、集合｛Ａ：Ｂ、Ａ：Ｃ｝は、ノードＡの接続相手が、ノードＢとノードＣであることを示している。なお、ノード接続情報１０１は、ノード１がネットワークに接続されたタイミングで接続しているノード情報が格納される。
【００２２】
最短経路木１０２のデータは、図１のネットワークの例を用いて示している。最短経路木１０２もノード接続情報と同様に、ノード対の集合で表す。ここで、ノード対には、順番があり、左が親、右が子の関係になり、また、上から下へ根から葉の順序で形成される木構造になっている。また、最短経路木１０２には、ノード１がメッセージの送信元になった際に、最初にノード接続情報からコピーする（後述する図８送信元フローのＳ１１）ことによって格納される。
【００２３】
メッセージ本文１０３では、ユーザがノード１に対してメッセージ送信を要求する際に、送信したい内容をメッセージ本文として渡すことを想定しており、ノード１がこの要求を受けたときに、渡されたメッセージ本文が格納される。
【００２４】
図３は、送信メッセージ２００と返信メッセージ３００のデータ構造を示している。（ａ）は、送信元ノードＡからＢに送信する場合の送信メッセージ２００のデータ構造を示し、（ｂ）は、送信メッセージ２００を受信したノードＢから送信元Ａに返送される場合における返信メッセージ３００のデータ構造を示している。
【００２５】
送信用メッセージ２００は、送信用最短経路木２０２とメッセージ本文２０３から構成され、例えば、「送信用最短経路木」のデータとしては、Ａ：Ｂ、Ａ：Ｃのようなノード対で表されている。また、返信メッセージ３００は、削除経路３０１、返信用最短経路木３０２、およびメッセージ本文３０３の項目から構成されている。例えば、「削除経路」ではＢ：Ｅの経路が削除され、「返信用最短経路木」では、ノードＢからの返信経路として、Ｂ：Ａ、Ｂ：Ｄ、Ｂ：Ｅのノード対が格納されている。
【００２６】
図４は、ノード１の配信情報テーブル１００のデータ構造の一つである、ノード接続情報１０１のデータ構造をネットワーク内の各ノード毎に示している。例えば、ノードＥでは、接続ノードＢ、Ｃ、Ｄ、Ｆが、Ｅ：Ｂ、Ｅ：Ｃ、Ｅ：Ｄ、Ｅ：Ｆのノード対の集合として示されている。
【００２７】
図５〜図７では、最短経路木１０２のデータ構造をネットワークの例を用いて示している。最短経路木１０２もノード接続情報１０１と同様に、ノード対の集合で表わされる。実施例では、ノードＡからメッセージ配信を開始した場合の最短経路木拡張の様子を示しており、図５は、最短経路計算部２０によって計算された第１回目の計算結果によるノードＡの最短経路木１０２を示し、また、図６は、第２回目の計算結果を、図７は、第３回目の計算結果を示している。なお、ネットワーク図中において、最短経路木は太線で示している。
【００２８】
ノードＡの最短経路木は、第１回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、第２回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ、および第３回目の計算によって、Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ、Ｄ：Ｇとなり、計算の度にその範囲を拡張させている。
【００２９】
図８は、メッセージ送信の手順を説明するフロー図である。本実施例では、送信元のノードＡからメッセージを送信する場合のフローを示している。
【００３０】
まず、ステップＳ１０において、最短経路木１０２にデータが存在するか否かを判定する。最短経路木１０２にデータがなければ、ステップＳ１１において、ノードＡの最短経路計算部２０が、ノードＡの最短経路木１０２にノードＡのノード接続情報１０１をコピーする。
【００３１】
最短経路木１０２にデータがある場合には、ステップＳ１２へスキップし、送信メッセージ２００内の送信用最短経路木２０２にノードＡの最短経路木１０２をコピーし、また、ステップＳ１３において、送信メッセージ２００のメッセージ本文２０３にノードＡのメッセージ本文１０３をコピーする。
【００３２】
さらに、ステップＳ１４において、ノードＡのノード接続情報１０１を集合Ｑ１としてコピーする。そして、ステップＳ１５において、集合Ｑ１が空集合か否かを判定する。
【００３３】
集合Ｑ１が空集合でないとき、ステップＳ１６において、集合Ｑ１からノード対を一つ取り出し、それをｑ（＝Ａ：Ｙ）とする。
【００３４】
ステップＳ１７において、メッセージ送受信部１０が、Ｙに送信メッセージ２００を送信する。ステップＳ１５に戻り、集合Ｑ１が空集合となるまで、ステップＳ１６からＳ１７の処理を繰り返す。集合Ｑ１が空集合になったら、返信メッセージ送信フロー（図１０）に進む。
【００３５】
つぎに、ステップＳ１８において、返信メッセージ送信フローを受けて、最短経路計算部２０が、ノードＡの最短経路木１０２に変化があったかを判定する。変化がなければ終了とし、変化があった場合には、ステップＳ１２に戻り、最短経路木１０２に新たに追加されたノードに対して、以降の処理を繰り返すことによって、最短経路木１０２を更新する。
【００３６】
図９は、送信メッセージ２００を受信したノードが、さらに、子ノードに該メッセージを転送する場合の送信メッセージ転送フローを示している。実施例では、例えば、送信メッセージ２００を受信したノードＢが、子ノードに該メッセージを転送する場合を取り上げて説明する。
【００３７】
まず、ステップＳ２１において、送信元ノードＡから送信メッセージ２００を受信し、ステップＳ２２において、ノードＢの最短経路計算部２０が、送信メッセージ２００内にある送信用最短経路木２０２において、左側がＢであるノード対ｐが存在するか否かを判定する。
【００３８】
送信用最短経路木２０２で左側がＢであるノード対ｐが存在すれば、ステップＳ２３において、ノード対ｐの集合をＱ２とする。つぎに、ステップＳ２４において、集合Ｑ２からノード対を一つ取り出し、それをｑ（＝Ｂ：Ｙ）とする。
【００３９】
そして、ステップＳ２５において、ノード対ｑがノードＢのノード接続情報１０１に含まれるか否かを判定する。含まれていなければ、ステップＳ２６において、ノード対ｑを返信メッセージ３００の削除経路３０１に追加し、ステップＳ２７において、Ｙ宛に該メッセージを転送する。また、ステップＳ２５で、ノード対ｑが含まれているときには、ステップＳ２６をスキップして、ステップＳ２７に進み、転送処理を行う。
【００４０】
つぎに、ステップＳ２８において、集合Ｑ２が空集合か否かを判定する。空集合になったら、返信メッセージ送信フロー（図１０）に進む。また、集合Ｑ２が空集合でないときには、ステップＳ２４に戻り、以降の処理を繰り返す。
【００４１】
一方、ステップＳ２２において、ノード対ｐが存在しないときには、ステップＳ２９に進み、メッセージ処理部３０が、メッセージ本文１０１の実行処理を行い、内容によって処理結果を返信メッセージ本文３０１に格納し、返信メッセージ送信フローへと移行する。
【００４２】
図１０は、返信メッセージの送信フローを示す。本実施例は、例えば、ノードＢが行う処理フローである。なお、返信メッセージ３００には、親の送信元ノードＡへ送信する返信メッセージと、子のノードＤ、Ｅから受信する返信メッセージとが存在するため、以下では、子ノードからの返信メッセージを３００Ｒと表現して区別する。なお、子ノードから戻って来る返信メッセージ３００Ｒのデータ構造も、図３（ｂ）と同様に、削除経路３０１Ｒ、最短経路木３０２Ｒ、およびメッセージ本文３０３Ｒの項目から構成されているものとする。
【００４３】
まず、ステップＳ３１において、返信メッセージ３００の返信用最短経路木３０２にノード接続情報１０１をコピーする。但し、本フローが送信元フローから来た場合は、返信メッセージがないので、返信用最短経路木３０２は、送信元ノードの最短経路木１０２を指す。
【００４４】
つぎに、ステップＳ３２において、最短経路計算部２０は、送受信時にメモリに保持されるメッセージ送受信の状態情報を参照し、子ノードに送信済みのメッセージに対し、受信していない返信メッセージ３００Ｒがあるか否かを判定する。
【００４５】
受信していない返信メッセージ３００Ｒがあれば、ステップＳ３３において、返信メッセージ３００Ｒを受信する。そして、ステップＳ３４において、返信用最短経路木３０２から返信メッセージ３００Ｒの削除経路３０１Ｒを削除する。
【００４６】
さらに、ステップＳ３５において、返信メッセージ３００Ｒの削除経路３０１Ｒを返信メッセージ３００の削除経路３０１に追加し、ステップＳ３６において、返信メッセージ３００Ｒのメッセージ本文３０３Ｒを返信メッセージ３００のメッセージ本文３０３に追加する。なお、本フローが送信元フローから来た場合は、返信メッセージがないので、Ｓ３５、Ｓ３５６のステップはスキップする。
【００４７】
さらに、ステップＳ３７において、返信用最短経路木３０２と、返信メッセージ３００Ｒの返信用最短経路木３０２Ｒをマージする。そして、ステップＳ３２に戻り、受信する返信メッセージ３００Ｒがなくなるまで処理を繰り返す。
【００４８】
受信する返信メッセージ３００Ｒがなければ、ステップＳ３８において、返信先が存在するか否かを判定する。返信先が存在すれば、ステップＳ３８において、返信メッセージ３００を送信メッセージ送信元ノードＡに送信する。返信先が存在しなければ、送信元のメッセージ送信フロー（図８）に戻る。
【００４９】
図１１は、メッセージ配信中にネットワークの接続状態が変わったときに、送信元ノードＡにおける最短経路木１０２の修正過程を示している。ここでは、最短経路計算３回目で、ノードＢ／ノードＥ間の接続が切断された場合を例としている。
【００５０】
（１）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ｝は、ネットワークの最短経路計算２回目の結果によるノードＡの最短経路木１０２を示している。つぎの最短経路計算３回目で、ノードＢからの返信メッセージから削除経路Ｂ：Ｅの情報を取得し、（１）の最短経路木からＢ：Ｅのノード対が削除された（２）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ｝となる。
【００５１】
また、ノードＢからの返信メッセージから返信用最短経路木｛Ｂ：Ａ、Ｂ：Ｄ、Ｄ：Ｇ｝の情報を取得し、（２）の最短経路木をマージして、（３）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ、Ｄ：Ｇ｝が得られる。
【００５２】
さらに、ノードＣの返信メッセージから返信用最短経路木｛Ｃ：Ａ、Ｃ：Ｅ、Ｃ：Ｆ、Ｆ：Ｇ｝の情報を取得し、（３）の最短経路木をマージして、（４）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｃ：Ｆ、Ｄ：Ｇ、Ｃ：Ｅ｝が得られる。
【００５３】
以上の修正処理によって最終的に得られたノードＡの最短経路木は、図１２のネットワーク図における太線部で表される。
【００５４】
図１３は、あるノードの最短経路木１０２に子ノードからの返信メッセージ３００Ｒに載せられた別の返信用最短経路木３０２Ｒを取り込んでマージ処理するフローを示している。
【００５５】
まず、ステップＳ４１において、子ノードからの返信用最短経路木３０２Ｒの集合Ｓが空集合か否かを判定する。集合Ｓが空でなければ、ステップＳ４２において、集合Ｓからノード対を一つ取り出し、それをｑ（＝Ｘ：Ｙ）とする。
【００５６】
ステップＳ４３において、Ｙがあるノードの最短経路木１０２の根か否かを判定する。あるノードの最短経路木１０２の根でなければ、さらに、ステップＳ４４において、子ノードからの返信用最短経路木３０２Ｒに、右側がＹであるノード対ｐが存在するか否かを判定する。
【００５７】
ノード対が存在すれば、ステップＳ４５において、あるノードの最短経路木１０２のｐをｑに置き換えたとき、根からＹまでの経路が短くなるか否かを判定する。経路が短くなれば、ステップＳ４６において、最短経路木１０２のｐをｑに置き換える。
【００５８】
また、ステップＳ４４で、ノード対が存在しなければ、ステップＳ４７において、最短経路木１０２にｑを追加する。
【００５９】
以上の処理を、別の最短経路木として、子ノードからの返信用最短経路木３０２Ｒの集合Ｓが空集合となるまで繰り返し、空集合となった時点で本フローは終了となる。
【００６０】
図１４は、図１３のマージ処理におけるあるノードの最短経路木をノードＡの最短経路木１０２、また、別な最短経路木を子ノードであるノードＢ及びノードＣからの返信メッセージ３００Ｒに載せられた返信用最短経路木３０２Ｒとした場合のマージ処理の過程を模式的に表したものである。
【００６１】
（１）は、ノードＡの最初の最短経路木｛Ａ：Ｂ、Ａ：Ｃ｝である。これにノードＢからの返信メッセージからの返信用最短経路木｛Ｂ：Ａ、Ｂ：Ｄ、Ｂ：Ｅ｝の情報を取り込んでマージして、（２）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ｝が得られる。さらに、ノードＣからの返信メッセージから返信用最短経路木｛Ｃ：Ａ、Ｃ：Ｅ、Ｃ：Ｆ｝を取り込んで、（３）の最短経路木｛Ａ：Ｂ、Ａ：Ｃ、Ｂ：Ｄ、Ｂ：Ｅ、Ｃ：Ｆ｝が得られる。
【００６２】
以上述べてきたように、本発明では、メッセージ配信と最短経路計算を同時に行うことによって重複メッセージをなくすことができ、ネットワークの通信量を抑えることが可能となる。
【００６３】
さらに、最短経路木が徐々に増大することによるコストアップに対処するため、最短経路配信からマルチキャスト配信へ配信手法を切り替えることが好ましい。その切り替えの仕組みを以下に述べる。
【００６４】
メッセージ配信時に計算する最短経路木から、最短経路木の深さと平均分枝数を取得し、最短経路木を使うメッセージ配信と従来のマルチキャスト配信の総メッセージ数を計算する。最短経路木を使う場合の総メッセージ数の方が多くなる場合は、それ以上の最短経路木更新を停止し、最短経路木以外のノードへは従来のマルチキャスト配信に切り替える。
【００６５】
最短経路木をマージする際に、そのノードの接続数がわかるので、最短経路木が構築されている範囲での平均接続数が計算できる。
【００６６】
つまり、従来のマルチキャスト配信手法の総メッセージ数は、（ノード数）×（平均接続数）として計算できる。一方、最短経路木を使う手法の総メッセージ数は、平均して（ノード数）×（木の深さ）として計算できる。したがって、木の深さが平均接続数を上回ったときに、最短経路木を使う手法から従来手法に切り替えることが可能となる。
【００６７】
また、好ましくは、最短経路木を保持するメモリが限界になった場合にも、配信手法を切り替えるのもよい。
【００６８】
こうした切り替えにより、本発明によるメッセージ配信コストが従来手法のコストよりも大きくなることを防ぐことが可能である。また、最短経路木作成の限界値を予め計算せずに、限界までメッセージ配信することができるメリットを有する。
【産業上の利用可能性】
【００６９】
コンピュータネットワーク上でのメッセージのマルチキャスト配信に関する分野。
【符号の説明】
【００７０】
１ ノード
２ 通信路
１０ メッセージ送受信部
１１ メッセージキュー
２０ 最短経路計算部
３０ メッセージ処理部
５０ データ格納領域
１００ 配信情報テーブル
１０１ ノード接続情報
１０２ 最短経路木
１０３ メッセージ本文
【特許請求の範囲】
【請求項１】
複数のノードからなるネットワークにおけるメッセージ配信プログラムであって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、
前記拡張した最短経路木に前記メッセージを送信するステップと、
を送信元ノードに実行させるメッセージ配信プログラム。
【請求項２】
前記最短経路計算ステップは、メッセージ配信時に計算する最短経路木から該最短経路木の深さと平均接続数を取得し、前記最短経路木を使って配信する最短経路木配信及び隣接する全ノードに配信するマルチキャスト配信の各総メッセージ数を計算し、前記最短経路配信の総メッセージ数の方が多くなる場合に、前記マルチキャスト配信へ切り替えることを特徴とする請求項１に記載のメッセージ配信プログラム。
【請求項３】
複数のノードからなるネットワークにおけるメッセージ配信方法であって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、
前記拡張した最短経路木に前記メッセージを送信するステップと、
を送信元ノードに実行させることを特徴とするメッセージ配信方法。
【請求項４】
複数のノードからなるネットワークにおいてメッセージを配信するノードであって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信手段と、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新手段と、
前記拡張した最短経路木に前記メッセージを送信する手段と、
を有することを特徴とするノード。
【請求項１】
複数のノードからなるネットワークにおけるメッセージ配信プログラムであって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、
前記拡張した最短経路木に前記メッセージを送信するステップと、
を送信元ノードに実行させるメッセージ配信プログラム。
【請求項２】
前記最短経路計算ステップは、メッセージ配信時に計算する最短経路木から該最短経路木の深さと平均接続数を取得し、前記最短経路木を使って配信する最短経路木配信及び隣接する全ノードに配信するマルチキャスト配信の各総メッセージ数を計算し、前記最短経路配信の総メッセージ数の方が多くなる場合に、前記マルチキャスト配信へ切り替えることを特徴とする請求項１に記載のメッセージ配信プログラム。
【請求項３】
複数のノードからなるネットワークにおけるメッセージ配信方法であって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信ステップと、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新ステップと、
前記拡張した最短経路木に前記メッセージを送信するステップと、
を送信元ノードに実行させることを特徴とするメッセージ配信方法。
【請求項４】
複数のノードからなるネットワークにおいてメッセージを配信するノードであって、
ノードの接続情報を記憶した最短経路木にメッセージを送信し、他ノードからノード接続情報を載せた返信メッセージを受信するメッセージ送受信手段と、
前記返信メッセージのノード接続情報を用いて拡張した最短経路木を作成する最短経路更新手段と、
前記拡張した最短経路木に前記メッセージを送信する手段と、
を有することを特徴とするノード。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−４９６２０（Ｐ２０１１−４９６２０Ａ）
【公開日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願番号】特願２００９−１９３８５２（Ｐ２００９−１９３８５２）
【出願日】平成２１年８月２５日（２００９．８．２５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願日】平成２１年８月２５日（２００９．８．２５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]