(57)【要約】【課題】複数のノードが接続された通信ネットワークにおいて、効率的なメッセージ配信シーケンスを実現するためのノード装置、及び、メッセージ配信方法を提供する。【解決手段】メッセージを配信する通信ネットワーク１を構成するノード１０において、ノード１０は、隣接履歴保持部１３に保持されている履歴に基づいて、隣接するノード１０に配信すべきメッセージの配信順序を決定する。【選択図】      図２
2005027099.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを配信する通信ネットワークを構成するノード装置において、
前記ノード装置に隣接する隣接ノード装置との接続状態に関する履歴を保持する隣接履歴保持手段と、
前記隣接履歴保持手段に保持されている履歴に基づいて、前記隣接ノード装置に配信すべきメッセージの配信順序を決定する配信順序決定手段と
を含むことを特徴とするノード装置。
【請求項２】
前記隣接履歴保持手段は、前記隣接ノード装置を識別するための隣接ノード識別情報と、該隣接ノード装置と前記ノード装置とが接続した時刻とを対応付けて、前記履歴として保持しており、
前記配信順序決定手段は、前記隣接ノード識別情報で識別される隣接ノード装置に対して、前記隣接ノード識別情報に対応付けられている時刻が古い順に、前記メッセージを配信することを決定することを特徴とする請求項１に記載のノード装置。
【請求項３】
前記配信順序決定手段は、前記隣接履歴保持手段に保持されている履歴に基づいて、自装置に隣接する隣接ノード装置を判定し、該判定された隣接ノード装置のうち、隣接するノード装置の数が多い順に、該隣接ノード装置にメッセージを配信することを決定することを特徴とする請求項１又は２に記載のノード装置。
【請求項４】
前記隣接ノード装置毎に、該隣接ノード装置が自装置にメッセージを配信してきた頻度を管理するメッセージ受信頻度管理手段をさらに有し、
前記配信順序決定手段は、前記接続履歴保持手段に保持されている履歴に基づいて、自装置に隣接する隣接ノード装置を判定し、
該判定された隣接ノード装置に対して、前記メッセージ受信頻度管理手段により管理されている前記頻度が高い順に、前記メッセージを配信することを特徴とする請求項１乃至３のいずれか１項に記載のノード装置。
【請求項５】
特定のノード装置と、該特定のノード装置に隣接する隣接ノード装置との接続状態に関する履歴に基づいて、前記隣接ノード装置にメッセージを配信するメッセージ配信方法において、
前記特定のノード装置が前記隣接ノード装置に接続したことを表す履歴と、前記特定のノード装置が前記隣接ノード装置によって接続されたことを表す履歴との、少なくとも一方の履歴を検索する検索ステップと、
前記検索ステップにおいて検索された履歴が古い順に、該履歴で表される隣接ノード装置に対して、前記メッセージを配信する配信ステップと、
を有することを特徴とするメッセージ配信方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メッセージを配信するノード装置、及び、メッセージ配信方法に関し、特に、接続された複数のノードに効率的にメッセージを配信するためのノード装置、及び、メッセージ配信方法に関する。
【０００２】
【従来の技術】
複数のノードが接続された通信ネットワークにおいて、配信元のノードから他のノードへメッセージを配信する方式としては、従来より、図１６に示す方式が知られている（例えば、非特許文献１参照）。同図に示す通信ネットワークは、メッセージのルーティングを行うルータと、パーソナルコンピュータやサーバ等のノードとを含む構成であり、ルータによってメッセージの転送が行われる。
【０００３】
一方、近年では、図１７に示すメッセージ転送方式の研究が行われている。同図に示す方式では、ルータによっては全くメッセージのルーティングは行われず、各ノードが保持している、隣接するノードとの接続状態に関する情報に基づいて、隣接ノードとの間でメッセージ転送が行われる。
また、ノードの接続状態に関する情報に基づいて処理を行う技術としては、ノード同士が接続した履歴に基づいて、効率的にノード同士が接続する技術が知られている（例えば、特許文献１参照）。
【０００４】
【特許文献１】
特開平１１−１５７１５号公報（図８）
【非特許文献１】
Ｄ．  Ｗａｉｔｚｍａｎ他”Ｄｉｓｔａｎｃｅ  Ｖｅｃｔｏｒ  Ｍｕｌｔｉｃａｓｔ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ”，［ｏｎｌｉｎｅ］，Ｎｏｖｅｍｂｅｒ  １９９８，ＲＦＣ１０７５，Ｔｈｅ  Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ（ＩＥＴＦ），［平成１５年６月２３日検索］インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ１０７５．ｔｘｔ＞
【０００５】
【発明が解決しようとする課題】
ルータはデータ転送に特化した装置であり、複数のネットワークインターフェースを備えている。このため、図１６に示すルータを用いたメッセージ転送方式では、全ての隣接ノードに、同時にメッセージの転送を行うことが可能である。一方、図１７に示すルータを利用しないメッセージ転送方式では、各ノードがメッセージ転送を担うこととなる。ところが、ノードは、単一のネットワークインターフェースしか備えていないため、ノードは、当該ネットワークインターフェースを時分割して利用し、メッセージ転送を行う。従って、ノードは、全ての隣接ノードに同時にメッセージ転送を行うことはできず、隣接するノード毎に順にメッセージ転送を行う。このため、各隣接ノードへのメッセージ転送には、時間差が生じる。また、ノードが隣接ノードにメッセージを転送する順序によっては、接続された全てのノードにメッセージが転送されるまでに時間がかかってしまうという問題がある。
【０００６】
図１８には、メッセージ配信グループにおけるノード間の接続形態（以下、「配信ツリー」という）の一例を示す。図中の円はノードであり、円内の数字は、ノードが配信グループに参加した（配信ツリーを構成するノードに接続した）順序を示す。
図１９と図２０には、図１８のように構成された配信ツリーにおいて、ノード間をメッセージが転送される場合のメッセージ配信シーケンスの例を示す。
【０００７】
図１９に示すメッセージ配信シーケンスは、メッセージ配信元のノードが、配信グループに参加した順番が遅い隣接ノードから順に、メッセージを配信する場合のシーケンス例である。一方、図２０に示すメッセージ配信シーケンスは、メッセージ配信元のノードが、配信グループに参加した順番が早い隣接ノードから順に、メッセージを配信する場合のシーケンス例である。
【０００８】
このような配信ツリーにおいて、各ノード間におけるリンク確立までの遅延時間が同等であり、かつ、ノード間をメッセージ転送するのに必要な時間が同等であると仮定すると、図中の１つの矢印で示される１つのメッセージ配信シーケンスは、単位時間を表していると考えることができる。すなわち、配信ツリーを構成するノード全てにメッセージを配信するまでには、図中に示されたメッセージ配信シーケンスの番号に比例した時間がかかることになる。従って、図１９に示すメッセージ配信シーケンスは、図２０に示すメッセージ配信シーケンスに比べて、配信ツリーを構成するノード全てにメッセージを配信するまでに、７／４倍の時間がかかってしまうことになる。このような時間差が生じるのは、隣接ノードの数が多いノードに先にメッセージを配信した方が、効率的にメッセージを配信できる確率が高く、また、配信グループに参加した順が早いノードほど隣接ノードの数が多くなる確率が高いからである。
【０００９】
ルータを用いないノード間のメッセージ配信方式においては、図２０に示すような効率的なメッセージ通信シーケンスは保証されておらず、伝送遅延が発生するという問題点がある。効率的なメッセージ配信シーケンスを常に保証するためには、各ノードが保持する、隣接ノードとの接続状態に関する情報を用いて、メッセージを効率的に配信する仕組みを構築する必要がある。
【００１０】
ここで、特許文献１には、他のノードとの接続状態に関する履歴を保持する構成が記載されている。しかし、当該履歴は、接続先のノードに対して、接続可能な時刻を予測するために用いられている。このため、特許文献１に記載されている技術を、既にノード同士が接続されている配信ツリーにおいてメッセージを効率的に配信する仕組みを構築するために利用することはできない。
この発明は上記に鑑みてなされたものであり、その目的は、複数のノードが接続された通信ネットワークにおいて、効率的なメッセージ配信シーケンスを実現するノード装置、及び、メッセージ配信方法を提供することである。
【００１１】
【課題を解決するための手段】
上記課題を解決するために、請求項１に記載の発明は、メッセージを配信する通信ネットワークを構成するノード装置において、前記ノード装置に隣接する隣接ノード装置との接続状態に関する履歴を保持する隣接履歴保持手段と、前記隣接履歴保持手段に保持されている履歴に基づいて、前記隣接ノード装置に配信すべきメッセージの配信順序を決定する配信順序決定手段とを含むことを特徴とするノード装置を提供する。
【００１２】
請求項１に記載の発明によれば、前記ノード装置は、前記隣接履歴保持手段により保持されている前記ノード装置に隣接する隣接ノード装置との接続状態に関する履歴に基づいて、メッセージ配信順序を決定するため、前記ノード装置は、最適な順序でメッセージを配信することができる。このため、前記通信ネットワーク全体として、最適なメッセージ配信シーケンスを実現することができ、効率的に、短時間で、前記通信ネットワークが備えるノード装置全体にメッセージを転送することができる。このため、各ノード装置へのメッセージ到達遅延を防ぐことができる。また、効率的な転送を実現できることにより、限られた前記通信ネットワークの資源を有効に活用することができる。
【００１３】
また、請求項２に記載の発明は、請求項１に記載のノード装置において、前記隣接履歴保持手段は、前記隣接ノード装置を識別するための隣接ノード識別情報と、該隣接ノード装置と前記ノード装置とが接続した時刻とを対応付けて、前記履歴として保持しており、前記配信順序決定手段は、前記隣接ノード識別情報で識別される隣接ノード装置に対して、前記隣接ノード識別情報に対応付けられている時刻が古い順に、前記メッセージを配信することを決定することを特徴とする。
【００１４】
請求項２に記載の発明によれば、古くから自装置に接続していた隣接ノード装置に対して、先にメッセージを配信することができるために、古くから自装置に接続していたノード装置に、より多くのノード装置が接続されているという前提の基、より多くのノード装置が接続されている隣接ノード装置に対して、先にメッセージを配信することができる。このために、最適な配信シーケンスを実現することができ、効率的に、前記通信ネットワークが備えるノード装置全てにメッセージを配信することができる。このため、ノード装置全てに短時間でメッセージを配信することができ、各ノード装置へのメッセージ到達遅延を防ぐことができる。
【００１５】
また、請求項３に記載の発明は、請求項１又は２に記載のノード装置において、前記配信順序決定手段は、前記隣接履歴保持手段に保持されている履歴に基づいて、自装置に隣接する隣接ノード装置を判定し、該判定された隣接ノード装置のうち、隣接するノード装置の数が多い順に、該隣接ノード装置にメッセージを配信することを決定することを特徴とする。
【００１６】
請求項３に記載の発明によれば、前記配信順序決定手段は、前記隣接ノード装置に隣接するノード装置の数が多い順に、前記隣接ノード装置にメッセージを配信することを決定するため、確実に、より多くのノード装置が接続されているノード装置に、先にメッセージを転送することができる。このために、最適な配信シーケンスを実現することができ、効率的に、前記通信ネットワークが備えるノード装置全てにメッセージを配信することができる。このため、ノード装置全てに短時間でメッセージを配信することができ、各ノード装置へのメッセージ到達遅延を防ぐことができる。
【００１７】
また、請求項４に記載の発明は、請求項１乃至３のいずれか１項に記載のノード装置において、前記隣接ノード装置毎に、該隣接ノード装置が自装置にメッセージを配信してきた頻度を管理するメッセージ受信頻度管理手段をさらに有し、前記配信順序決定手段は、前記接続履歴保持手段に保持されている履歴に基づいて、自装置に隣接する隣接ノード装置を判定し、該判定された隣接ノード装置に対して、前記メッセージ受信頻度管理手段により管理されている前記頻度が高い順に、前記メッセージを配信することを特徴とする。
【００１８】
請求項４に記載の発明によれば、自装置にメッセージを配信してきた頻度が高いノード装置に、先にメッセージを配信することができるために、メッセージを配信してくる頻度が高いノード装置には、多くのノード装置が接続されているという前提の基、より多くのノード装置が接続されているノード装置に、先にメッセージを配信することができる。このために、最適な配信シーケンスを実現することができ、効率的に、前記通信ネットワークが備えるノード装置全てにメッセージを配信することができる。このため、ノード装置全てに短時間でメッセージを配信することができ、各ノード装置へのメッセージ到達遅延を防ぐことができる。
【００１９】
請求項５に記載の発明は、特定のノード装置と、該特定のノード装置に隣接する隣接ノード装置との接続状態に関する履歴に基づいて、前記隣接ノード装置にメッセージを配信するメッセージ配信方法において、前記特定のノード装置が前記隣接ノード装置に接続したことを表す履歴と、前記特定のノード装置が前記隣接ノード装置によって接続されたことを表す履歴との、少なくとも一方の履歴を検索する検索ステップと、前記検索ステップにおいて検索された履歴が古い順に、該履歴で表される隣接ノード装置に対して、前記メッセージを配信する配信ステップとを有することを特徴とするメッセージ配信方法を提供する。
【００２０】
請求項５に記載の発明によれば、前記履歴が古い順に、該履歴で表される隣接ノード装置に対して、前記メッセージを配信する手順としたために、古くから自装置に接続していた隣接ノード装置にメッセージを配信することができる。このために、古くから自装置に接続していたノード装置に、多くのノード装置が接続されているという前提の基、より多くのノード装置が接続されている隣接ノード装置に、先にメッセージを配信することができる。このように最適な配信シーケンスを実現できるため、効率的に、前記通信ネットワークが備えるノード装置全てにメッセージを転送することができる。このため、ノード装置全てに短時間でメッセージを転送することができ、各ノード装置へのメッセージ到達遅延を防ぐことができる。
【００２１】
【発明の実施の形態】
次に、図面を参照して本発明の実施の形態について説明する。なお、以下の説明において参照する各図においては、他の図と同等部分に同一符号が付されている。
［１．第１実施形態］
［１．１．構成］
図１には、この発明の第１実施形態に係る通信ネットワーク１の構成を示す。この通信ネットワーク１は、複数のノードを含んで構成される。同図においては、通信ネットワーク１は、９つのノード１０ａ、１０ｂ、・・・、１０ｉが相互に接続され、配信ツリーを構成している。これらの接続された複数のノードは、例えば、マルチキャストグループ（Ｍｕｌｔｉｃａｓｔ  ｇｒｏｕｐ）と呼ばれるデータ配信グループを形成する。各ノードは、他のノードとの間で、マルチキャストメッセージ等のデータを転送する。
【００２２】
なお、各ノードは、同じ機能と構成を備えているため、以下の説明では、通信ネットワーク１が備える各ノードを特に区別する必要がない場合には、ノード１０として説明する。
ノード１０は、パーソナルコンピュータやサーバ等の装置であり、一般的なコンピュータのハードウェア構成を備えている。すなわち、ノード１０は、ノード１０全体を制御するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）やハードディスク装置を備えた記憶部と、隣接するノードとデータの授受を制御する通信インターフェイスと、時刻（年月日時分秒）を計時する計時部と、を含んで構成されている。これらのハードウェアや、記憶部に記憶されているソフトウェアにより、図２に示すノード１０の機能が実現される。
【００２３】
図２は、ノード１０の機能構成を示すブロック図である。同図に示すように、ノード１０は、メッセージ受信部１２と、隣接履歴保持部１３と、メッセージ送信部１４と、管理制御部１５とを備えている。
隣接履歴保持部１３は、ノード１０に隣接する隣接ノードとの接続状態に関する履歴を記憶する。隣接履歴保持部１３は、接続履歴テーブル１３１と、被接続履歴テーブル１３２とを備えている。
【００２４】
接続履歴テーブル１３１には、自ノード１０が隣接ノードに接続した履歴が記憶される。また、被接続履歴テーブル１３２には、自ノード１０が隣接ノードに接続された履歴が記憶される。
図３には、接続履歴テーブル１３１と被接続履歴テーブル１３２とに記憶される履歴のデータ構成を示す。同図に示すように、接続履歴テーブル１３１に記憶される履歴は、自ノード１０が隣接ノードに接続した「時刻」と、隣接ノードを識別するための「ノードＩＤ」とを含んで構成される。また、被接続履歴テーブル１３２に記憶される履歴は、自ノード１０が隣接ノードに接続された「時刻」と、隣接ノードの「ノードＩＤ」とを含んで構成される。これらの履歴は、ノード１０と他のノードとが接続した場合に、ノード１０によって生成され、テーブル１３１、１３２に記憶される。
【００２５】
メッセージ受信部１２は、隣接ノードからメッセージを受信する。メッセージ送信部１４は、メッセージを隣接ノードへ配信する。管理制御部１５は、ノード１０の各部を制御することにより、自ノード１０を配信元とした隣接ノードへのメッセージの配信や、隣接ノードから受信したメッセージの他の隣接ノードへの配信（すなわち、メッセージの転送）の制御を行う。管理制御部１５は、配信順序決定機能１５１を備えている。配信順序決定機能１５１は、接続履歴保持部１３に保持されている履歴に基づいて、隣接する他のノードに配信すべきメッセージの配信順序を決定する。
【００２６】
次に、ノード１０の管理制御部１５が行うメッセージ配信の制御機能について説明する。まず、図４のフローチャートを参照して、メッセージ配信元であるノード１０が、メッセージを他のノードに配信する場合のメッセージ配信処理について説明する。
なお、このメッセージ配信処理のアルゴリズムは、「より多くのノードが接続されているノードに、先にメッセージを配信する」という考えと、「以前から配信グループに存在していたノードには（古くから自ノード１０に接続していたノードには）、より多くのノードが接続されている」という考えに基づいている。
【００２７】
まず、ノード１０の管理制御部１５は、自ノード１０から接続した隣接ノードが存在するか否か判定する（ステップＳ１０１）。具体的には、管理制御部１５は、隣接履歴保持部１３の接続履歴テーブル１３１に履歴が記憶されているか否かを検索する。検索した結果、該当ノードが存在すると判定された場合には（ステップＳ１０１；該当ノードあり）、配信順序決定機能１５１は、該当ノードの中から、一番初めに（最も古い時刻に）接続した隣接ノードを判定する。具体的には、配信順序決定機能１５１は、該当ノードを内包する履歴の中から、最も古い「時刻」を内包する履歴を判定し、当該履歴の「ノードＩＤ」を抽出する。
【００２８】
そして、管理制御部１５は、メッセージ送信部１４に対して、抽出した「ノードＩＤ」で識別されるノードにメッセージを配信するよう指示する。
そして、管理制御部１５は、メッセージを配信したノードを、ステップＳ１０１の検索対象から外す（ステップＳ１０２）。
管理制御部１５は、ステップＳ１０１〜１０２の処理を、対象のノードが存在しなくなる（ステップＳ１０１；該当ノードなし）まで繰り返す。
【００２９】
対象のノードが存在しなくなった場合に（ステップＳ１０１；該当ノードなし）、管理制御部１５は、隣接ノードのうち、自ノード１０に接続してきた隣接ノードが存在するか否かを判定する（ステップＳ１０３）。具体的には、管理制御部１５は、隣接履歴保持部１３の被接続履歴テーブル１３２に履歴が記憶されているか否かを検索する。検索した結果、該当ノードが存在すると判定された場合には（ステップＳ１０３；該当ノードあり）、配信順序決定機能１５１は、該当ノードの中から、一番初め（最も古い時刻）に接続してきた隣接ノードを判定する。具体的には、配信順序決定機能１５１は、該当ノードを内包する履歴の中から、最も古い「時刻」を内包する履歴を判定し、当該履歴の「ノードＩＤ」を抽出する。そして、管理制御部１５は、メッセージ送信部１４に対して、抽出した「ノードＩＤ」で識別されるノードにメッセージを配信するよう指示する。そして、管理制御部１５は、メッセージ配信済みの隣接ノードを、ステップＳ１０３の検索対象から外す（ステップＳ１０４）。管理制御部１５は、ステップＳ１０３〜１０４の処理を、対象のノードが存在しなくなる（ステップＳ１０３；該当ノードなし）まで繰り返す。
【００３０】
次に、図５のフローチャートを参照して、ノード１０が、隣接するノードより転送されてきたメッセージを、他の隣接するノードに転送するメッセージ転送処理について説明する。
図５に示すメッセージ転送処理が、図４に示すメッセージ配信処理と異なる点は、ノード１０のメッセージ受信部１２が隣接ノードよりメッセージを受信したことがきっかけとなって処理が行われる点と、ステップＳ２０１とステップＳ２０３において該当ノードが存在するか否かを判定する際に、メッセージ転送元の隣接ノードを対象外とする点である。その他の図５に示すメッセージ転送処理の流れは、図４に示すメッセージ配信処理と同様であるため、重複した説明を省略する。
【００３１】
［１．２．動作］
次に、上記構成における第１実施形態の動作について説明する。
前提として、以下の動作で説明する通信ネットワーク１は、図６に示すように、ノード１０ａ、ノード１０ｂ、・・・、ノード１０ｉの９つのノードが接続されて配信ツリーを構成している。また、ノード１０ａを識別するためのノードＩＤは“１”、ノード１０ａのノードＩＤは“２”、・・・、ノード１０ｉのノードＩＤは“９”であり、当該情報は各々のノードの記憶部で管理されているものとする。
【００３２】
また、ノード１０ｂの隣接履歴保持部１３ｂには、図３に示すデータ内容の履歴が記憶されているものとする。また、ノード１０ａの隣接履歴保持部１３ａには、図７に示すデータ内容の履歴が記憶されており、ノード１０ｃの隣接履歴保持部１３ｃには、図８に示すデータ内容の履歴が記憶されているものとする。これらの履歴に内包されているノードＩＤで識別されるノードは、隣接ノードに接続（配信グループに参加）した（された）後、当該配信グループから離脱（脱退）していないものとする。したがって、隣接履歴保持部１３に保持されているノードＩＤで識別されるノードは、全て、ノード１０と接続している隣接ノードとなる。
【００３３】
また、各ノード間の通信リンク確立までの遅延時間は同等であり、ノード間をメッセージ転送するのに必要な時間が同等であるものとする。したがって、図６中、１つの矢印で示されるメッセージ配信シーケンスは、同一の単位時間を表している。
以下では、図４〜６を参照しながら、ノードＩＤ“２”で識別されるノード１０ｂが、メッセージを隣接ノードに配信した場合の、通信ネットワーク１を構成する各ノードの動作について、単位時間（シーケンス番号）順に、時系列に沿って説明する。
【００３４】
［シーケンス１］
＜ノード１０ｂの動作＞
まず、ノード１０ｂの管理制御部１５ｂは、一番初めにメッセージを配信するノードを決定するために、図４に示すように、自ノードから接続した隣接ノードが存在するか否かを判定する（ステップＳ１０１）。具体的には、管理制御部１５ｂは、隣接履歴保持部１３ｂの接続履歴テーブル１３１ｂに履歴が記憶されているか否かを検索する。ここでは、図３に示すように、接続履歴テーブル１３１ｂには、ノードＩＤ“１”で識別されるノード１０ａの履歴が記憶されているため、管理制御部１５ｂは、該当ノードが存在すると判定する（ステップＳ１０１；該当ノードあり）。
【００３５】
次に、管理制御部１５ｂの配信順序決定機能１５１ｂは、該当ノードと判定されたノードの中から、一番初めに接続したノードを判定する。そして、管理制御部１５ｂは、メッセージ送信部１４ｂに対して、当該判定されたノードにメッセージを配信する指示を行う。ここでは、該当ノードと判定されたノードは１つであるため、管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ノードＩＤ“１”で識別されるノード１０ａにメッセージを配信するよう指示する。メッセージ送信部１４ｂは、ノード１０ａにメッセージを配信する（図６に示すメッセージ配信シーケンス１）。そして、管理制御部１５ｂは、メッセージ配信済みの隣接ノード１０ａを、ステップＳ１０１の検索対象から外す（ステップＳ１０２）。
【００３６】
［シーケンス２］
＜ノード１０ｂの動作＞
ノード１０ｂの管理制御部１５ｂは、シーケンス１のメッセージを配信した後、図４のステップＳ１０１に戻る。管理制御部１５ｂは、自ノード１０ｂから接続した隣接ノードが存在するか否かを判定する（ステップＳ１０１）。具体的には、管理制御部１５ｂは、隣接履歴保持部１３ｂの接続履歴テーブル１３１ｂを検索する。ここでは、ノードＩＤ“１”で識別される隣接ノードの履歴は、検索対象から外されているため、管理制御部１５ｂは、該当ノードなしと判断する（ステップＳ１０１；該当ノードなし）。
【００３７】
次に、管理制御部１５ｂは、隣接ノードのうち、自ノードに接続してきた隣接ノードが存在するか否かを判定する（ステップＳ１０３）。具体的には、管理制御部１５ｂは、隣接履歴保持部１３ｂの被接続履歴テーブル１３２ｂに履歴が記憶されているか否かを検索する。ここでは、図３に示すように、被接続履歴テーブル１３２ｂには、ノードＩＤ“６”を内包する履歴と、ノードＩＤ“８”を内包する履歴と、ノードＩＤ“９”を内包する履歴との、３つの履歴が記憶されているため、管理制御部１５ｂは、該当ノードが存在すると判断する（ステップＳ１０３；該当ノードあり）。
【００３８】
次に、管理制御部１５ｂの配信順序決定機能１５１ｂは、該当するノードの中から、一番初めに接続してきた隣接ノードを判定する。具体的には、配信順序決定機能１５１ｂは、上述した３つの履歴の中から、最も古い「時刻」を内包する履歴を判定する。ここでは、図３に示すように、ノードＩＤ“６”に対応する「時刻」が最も古い時刻であるため、配信順序決定機能１５１ｂは、ノードＩＤ“６”で識別されるノード１０ｆが一番初めに接続してきた隣接ノードであると判定する。そして、管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ノード１０ｆにメッセージを配信するよう指示する。メッセージ送信部１４ｂは、ノード１０ｆにメッセージを配信する（図６のノード１０ｂからノード１０ｆへのシーケンス２）。そして、管理制御部１５ｂは、メッセージを配信した隣接ノード１０ｆを、ステップＳ１０３の検索対象から外す（ステップＳ１０４）。
【００３９】
＜シーケンス２；ノード１０ａの動作＞
一方、シーケンス１のメッセージをノード１０ｂより受信したノード１０ａの動作について説明する。ノード１０ａのメッセージ受信部１２ａがメッセージを受信すると、ノード１０ａの管理制御部１５ａは、図５に示すメッセージ転送処理を行う。まず、ノード１０ａの管理制御部１５ａは、メッセージ転送元ノード１０ｂ以外で、自ノード１０ａから接続した隣接ノードが存在するか否かを判定する（ステップＳ２０１）。具体的には、管理制御部１５ａは、隣接履歴保持部１３ａの接続履歴テーブル１３１ａに履歴が記憶されているか否か検索する。ここでは、図７に示すように、接続履歴テーブル１３１ａには、履歴は記憶されていないため、管理制御部１５ａは、該当ノードなしと判断する（ステップＳ２０１；該当ノードなし）。
【００４０】
次に、管理制御部１５ａは、メッセージ転送元ノード１０ｂ以外の隣接ノードのうち、自ノード１０ａに接続してきた隣接ノードが存在するか判定する（ステップＳ１０３）。具体的には、管理制御部１５ａは、隣接履歴保持部１３ａの被接続履歴テーブル１３２ａに履歴が記憶されているか否か検索する。ここでは、図７に示すように、被接続履歴テーブル１３２ａには、ノードＩＤ“２”を内包する履歴と、ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴との、３つの履歴が記憶されている。メッセージ転送元ノード１０ｂのノードＩＤ“２”は対象外であるが、ノードＩＤ“３”、“４”は対象ノードのノードＩＤであるため、管理制御部１５ａは、該当ノードが存在すると判定する（ステップＳ２０３；該当ノードあり）。
【００４１】
次に、管理制御部１５ａの配信順序決定機能１５１ａは、該当ノードの中から、一番初めに接続してきた隣接ノードを判定する。具体的には、配信順序決定機能１５１ａは、該当ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴とのうち、最も古い「時刻」を内包する履歴を判定する。ここでは、ノードＩＤ“３”に対応する「時刻」が、最も古い時刻であるため、配信順序決定機能１５１ａは、ノードＩＤ“３”で識別されるノード１０ｃが一番初めに接続してきた隣接ノードであると判定する。そして、管理制御部１５ａは、メッセージ送信部１４ａに対して、ノード１０ｃにメッセージを転送するよう指示する。メッセージ送信部１４ａは、ノード１０ｃにメッセージを転送する（図６のノード１０ａからノード１０ｃへのシーケンス２）。そして、管理制御部１５ａは、メッセージ転送済みの隣接ノード１０ｃを、ステップＳ２０３の検索対象から外す（ステップＳ２０４）。
【００４２】
［シーケンス３］
＜ノード１０ｂの動作＞
ノード１０ｂの管理制御部１５ｂは、シーケンス２のメッセージをノード１０ｆに配信した後、図４のステップＳ１０３に戻る。そして、管理制御部１５ｂは、自ノード１０ｂから接続した隣接ノードが存在するか否か判定する（ステップＳ１０３）。具体的には、管理制御部１５ｂは、既にメッセージを配信したノード１０ｆのノードＩＤ“６”を内包する履歴を検索対象外として、隣接履歴保持部１３の被接続履歴テーブル１３２ｂに記憶されている履歴を検索する。ここでは、図３に示すように、被接続履歴テーブル１３２ｂには、ノードＩＤ“６”を内包する履歴以外には、ノードＩＤ“８”を内包する履歴と、ノードＩＤ“９”を内包する履歴との、２つの履歴が記憶されているため、管理制御部１５ｂは、該当ノードが存在すると判断する（ステップＳ１０３；該当ノードあり）。
【００４３】
次に、管理制御部１５ｂの配信順序決定機能１５１ｂは、該当ノードの中から、一番初めに接続してきたノードを判定する。具体的には、配信順序決定機能１５１ｂは、該当ノードＩＤ“８”を内包する履歴とノードＩＤ“９”を内包する履歴とのうち、古い「時刻」を内包する履歴を判定する。ここでは、図３に示すように、ノードＩＤ“８”に対応する「時刻」が古い時刻であるため、配信順序決定機能１５１ｂは、ノードＩＤ“８”で識別されるノード１０ｈが一番初めに接続してきた隣接ノードであると判定する。そして、管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ノード１０ｈにメッセージを配信するよう指示する。メッセージ送信部１４ｂは、ノード１０ｈにメッセージを配信する（図６に示すノード１０ｂからノード１０ｈへのシーケンス３）。そして、管理制御部１５ｂは、メッセージ配信済みのノード１０ｈを、ステップＳ１０３の検索対象から外す（ステップＳ１０４）。
【００４４】
＜シーケンス３；ノード１０ａの動作＞
ノード１０ａの管理制御部１５ａは、ノード１０ｃに、シーケンス２のメッセージを転送した後、図５のステップＳ２０３に戻る。
管理制御部１５ａは、メッセージ転送元ノード１０ｂと、既にメッセージを転送したノード１０ｃとを除いて、自ノードに接続してきた隣接ノードが存在するか判定する（ステップＳ２０３）。具体的には、管理制御部１５ａは、隣接履歴保持部１３の被接続履歴テーブル１３２ａを検索する。ここでは、図７に示すように、被接続履歴テーブル１３２ａには、ノードＩＤ“２”を内包する履歴と、ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴との、３つの履歴が記憶されている。メッセージ転送元ノード１０ｂのノードＩＤ“２”と、既にメッセージを転送したノード１０ｃのノードＩＤ“３”とは対象外であるが、ノードＩＤ“４”は対象ノードＩＤであるため、管理制御部１５ａは、該当ノードが存在すると判定する（ステップＳ２０３；該当ノードあり）。
【００４５】
次に、管理制御部１５ａの配信順序決定機能１５１ａは、該当ノードの中から、一番初めに接続してきた隣接ノードを判定する。ここでは、該当ノードＩＤは“４”のみであるため、配信順序決定機能１５１ａは、ノードＩＤ“４”で識別されるノード１０ｄが一番初めに接続してきた隣接ノードであると判定する。管理制御部１５ａは、メッセージ送信部１４ａに対して、ノード１０ｄにメッセージを転送するよう指示する。メッセージ送信部１４ａは、ノード１０ｄにメッセージを転送する（図６に示すノード１０ａからノード１０ｄへのシーケンス３）。そして、管理制御部１５ａは、メッセージを転送済みの隣接ノード１０ｄを、ステップＳ２０３の検索対象から外す（ステップＳ２０４）。
【００４６】
次に、管理制御部１５ａは、ステップＳ２０３に戻り、メッセージ転送元ノード１０ｂを除いて、該当ノードが存在するか否か判定する。ここでは、既に、ノード１０ｃ、１０ｄにメッセージを転送済みであることにより、ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴とは検索対象外である。このため、管理制御部１５ａは、該当ノードなしと判断し（ステップＳ２０３；該当ノードなし）、処理を終了する。
【００４７】
＜シーケンス３；ノード１０ｃの動作＞
一方、ノード１０ａより、シーケンス２のメッセージを受信したノード１０ｃの動作について説明する。
ノード１０ｃのメッセージ受信部１２ｃがメッセージを受信すると、管理制御部１５ｃは、図５に示されるメッセージ転送処理を行う。
まず、管理制御部１５ｃは、メッセージ転送元ノード１０ａ以外で、自ノード１０ｃから接続した隣接ノードが存在するか判定する（ステップＳ２０１）。具体的には、管理制御部１５ａは、隣接履歴保持部１３ｃの接続履歴テーブル１３１ｃを検索する。ここでは、図８に示すように、接続履歴テーブル１３１ｃにはメッセージ転送元ノード１０ａのノードＩＤ“１”を内包した履歴しか記憶されていないため、管理制御部１５ｃは該当ノードなしと判断する（ステップＳ２０１；該当ノードなし）。
【００４８】
次に、管理制御部１５ｃは、メッセージ転送元ノード１０ａ以外の隣接ノードのうち、自ノードに接続してきた隣接ノードが存在するか判定する（ステップＳ２０３）。具体的には、管理制御部１５ｃは、隣接履歴保持部１３ｃの被接続履歴テーブル１３２ｃを検索する。ここでは、図８に示すように、被接続履歴テーブル１３２ｃには、ノードＩＤ“５”を内包した履歴とノードＩＤ“７”を内包した履歴との２つの履歴が記憶されており、どちらのノードＩＤも検索対象外のノードＩＤでないため、管理制御部１５ｃは、該当ノードが存在すると判断する（ステップＳ２０３；該当ノードあり）。
【００４９】
次に、管理制御部１５ｃの配信順序決定機能１５１ｃは、該当ノードの中から、一番初めに接続してきた隣接ノードを判定する。具体的には、配信順序決定機能１５１ｃは、ノードＩＤ“５”を内包した履歴とノードＩＤ“７”を内包した履歴との２つの履歴のうち、古い「時刻」を内包する履歴を判定する。ここでは、図８に示すように、ノードＩＤ“５”に対応する「時刻」が最も古い時刻であるため、配信順序決定機能１５１ｃは、ノードＩＤ“５”で識別されるノード１０ｅが一番初めに接続してきた隣接ノードであると判定する。そして、管理制御部１５ｃは、メッセージ送信部１４ｃに対して、ノード１０ｅにメッセージを転送するよう指示する。メッセージ送信部１４ａは、ノード１０ｅにメッセージを転送する（図６のノード１０ｃからノード１０ｅへのシーケンス３）。そして、管理制御部１５ｃは、メッセージ転送済みの隣接ノード１０ｅを、ステップＳ２０３の判定対象から外す（ステップＳ２０４）。
【００５０】
［シーケンス４］
＜ノード１０ｂの動作＞
次に、ノード１０ｂは、ノード１０ｈにシーケンス３のメッセージを配信した後、再度、図４のステップＳ２０３に戻る。そして、ノード１０ｂの管理制御部１５ｂは、隣接ノードのうち、自ノード１０ｂに接続してきた隣接ノードが存在するか否かを判定する（ステップＳ２０３）。具体的には、管理制御部１５ｂは、隣接履歴保持部１３の被接続履歴テーブル１３２ｂを検索する。ここでは、図３に示すように、被接続履歴テーブル１３２ｂには、ノードＩＤ“６”  を内包した履歴と、ノードＩＤ“８”を内包した履歴と、ノードＩＤ“９”を内包した履歴との、３つの履歴が記憶されている。ノードＩＤ“６”、“８”で識別されるノードには、既にメッセージが配信されているため対象外であるが、ノードＩＤ“９”は、対象ノードＩＤであるため、管理制御部１５ｂは、該当ノードが存在すると判断する（ステップＳ１０３；該当ノードあり）。
【００５１】
次に、管理制御部１５ｂの配信順序決定機能１５１ｂは、該当するノードを内包する履歴の中から、一番初めに接続してきた隣接ノードを判定する。ここでは、該当するノードＩＤは“９”のみであるため、配信順序決定機能１５１ｂは、ノードＩＤ“９”で識別されるノード１０ｉが一番初めに接続してきた隣接ノードであると判定する。管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ノード１０ｉにメッセージを配信する指示を行う。メッセージ送信部１４ｂは、ノード１０ｉにメッセージを配信する（図６に示すノード１０ｂからノード１０ｉへのシーケンス４）。そして、管理制御部１５ｂは、メッセージを配信した隣接ノード１０ｉを、ステップＳ１０３の判定対象から外す（ステップＳ１０４）。
管理制御部１５ｂは、再び、ステップＳ１０３に戻るが、既に、自ノード１０ｂに隣接するノード全てにメッセージを配信しており、該当するノードは存在しないため（ステップＳ１０３；該当ノードなし）、処理を終了する。
【００５２】
＜シーケンス４；ノード１０ｃの動作＞
ノード１０ｃは、ノード１０ｅに、シーケンス３のメッセージを転送した後、図５のステップＳ２０３に戻る。管理制御部１５ｃは、メッセージ転送元ノード１０ａと、既にメッセージを転送したノード１０ｅ以外で、自ノード１０ｃに接続してきた隣接ノードが存在するか否かを判定する（ステップＳ２０３）。具体的には、管理制御部１５ｃは、隣接履歴保持部１３ｃの被接続履歴テーブル１３２ｃを検索する。ここでは、図８に示すように、被接続履歴テーブル１３２ａには、ノードＩＤ“５”を内包する履歴と、ノードＩＤ“７”を内包する履歴との、２つの履歴が記憶されており、既にメッセージを転送したノード１０ｅのノードＩＤ“５”は対象外であるが、ノードＩＤ“７”は対象ノードＩＤであるため、管理制御部１５ｃは、該当ノードが存在すると判断する（ステップＳ２０３；該当ノードあり）。
【００５３】
次に、管理制御部１５ｃの配信順序決定機能１５１ｃは、該当ノードの中から、一番初めに接続してきた隣接ノードを判定する。ここでは、該当ノードＩＤは“７”のみであるため、配信順序決定機能１５１ｃは、ノードＩＤ“７”で識別されるノード１０ｇが一番初めに接続してきた隣接ノードであると判定する。管理制御部１５ｃは、メッセージ送信部１４ｃに対して、ノード１０ｇにメッセージを転送する指示を行う。メッセージ送信部１４ｃは、ノード１０ｇにメッセージを転送する（図６のノード１０ｃからノード１０ｇへのシーケンス４）。そして、管理制御部１５ｃは、メッセージを転送済みの隣接ノード１０ｇを、ステップＳ２０３の検索対象から外す（ステップＳ２０４）。
【００５４】
管理制御部１５ｃは、ステップＳ２０３に戻り、自ノードに接続してきたノードが存在するか否か判定する。ここでは、隣接ノード１０ｅ、１０ｇには、既に、メッセージを転送済みであり、対象外であるため、管理制御部１５ｃは、該当ノードなしと判断し（ステップＳ２０３；該当ノードなし）、処理を終了する。
以上のように、ノード１０が隣接履歴保持部１３に保持されている履歴を用いて、古くから自ノード１０と接続しているノードから順にメッセージを配信することで、最適なメッセージ配信シーケンスを実現することができる。このため、配信ツリーを構成する全てのノードに、最も短い４シーケンス（４単位時間）でメッセージを配信することができる。
【００５５】
［２．第２実施形態］
［２．１．構成］
次に、本発明に係る第２実施形態について説明する。まず、本第２実施形態における構成について説明する。
ノード１０の記憶部には、第１実施形態とは異なるプログラムが記憶されている。これにより、管理制御部１５の配信順序決定機能１５１は、第１実施形態とは異なるアルゴリズムにより、メッセージの配信順序を決定する。第２実施形態におけるメッセージの配信順序を決定するアルゴリズムは、「より多くのノードが接続されているノードに、先にメッセージを配信する」という考えに基づいている。
【００５６】
また、隣接履歴保持部１３に保持されている、隣接ノードとの接続状態に関する履歴は、第１実施形態において保持されていた自ノード１０についての履歴に加えて、通信ネットワーク１を構成する他の全てのノードについての履歴が保持されている。当該履歴は、他のノードの接続状態が変更されたときに、当該他のノードからノード１０に変更情報が通知されて、隣接履歴保持部１３に追加保持される。配信順序決定機能１５１は、メッセージ転送処理やメッセージ配信処理を行う際に、隣接履歴保持部１３に保持されている履歴を基に、自ノード１０の隣接ノードに接続されている隣接ノード数を算出する。
【００５７】
上記以外の第２実施形態の構成は、第１実施形態の構成と同様である。
次に、メッセージ配信元のノード１０が実行するメッセージ配信処理について、図９のフローチャートを参照しながら説明する。
まず、管理制御部１５の配信順序決定機能１５１は、隣接履歴保持部１３に保持されている履歴を参照して、現在、自ノード１０に接続されている隣接ノードを把握する。そして、配信順序決定機能１５１は、把握した隣接ノードについて、各々の隣接ノードに接続されている隣接ノード数を算出する。配信順序決定機能１５１は、算出した隣接ノード数の大きさを比較する。そして、配信順序決定機能１５１は、一番大きい隣接ノード数を有する隣接ノードを選択する（ステップＳ３０１：該当ノードあり）。
【００５８】
管理制御部１５は、メッセージ送信部１４に対して、ステップＳ３０１において選択したノードに対して、メッセージの配信を指示する。そして、管理制御部１５は、当該ノードを選択対象より外す（ステップＳ３０２）。
配信順序決定機能１５１は、ステップＳ３０１に戻り、ステップＳ３０２において、選択対象外としたノードを除いて、隣接ノード数が最も大きいノードを選択する。
【００５９】
全て選択対象外となり、該当ノードが存在しなくなった場合には（ステップＳ３０１；該当ノードなし）、管理制御部１５は、処理を終了する。
該当ノードが存在する場合には（ステップＳ３０１；該当ノードあり）、管理制御部１５は、該当ノードが存在しなくなるまで（ステップＳ３０１；該当ノードなし）、該当ノードにメッセージを配信する（ステップＳ３０２）。
【００６０】
次に、隣接ノードよりメッセージを受信したノード１０が実行するメッセージ転送処理について、図１０のフローチャートを参照しながら説明する。
図１０のメッセージ転送処理が、図９のメッセージ配信処理と異なる点は、ノード１０のメッセージ受信部１２が隣接ノードよりメッセージを受信したことがきっかけとなって処理が行われる点と、ステップＳ４０１において、該当ノードが存在するか否かを判定する際に、メッセージ転送元の隣接ノードを対象外とする点である。その他の図１０に示すメッセージ転送処理の流れは、図９のメッセージ配信処理と同様であるため、重複した説明を省略する。
【００６１】
［２．２．動作］
次に、上記構成における、第２実施形態の動作について説明する。
第２実施形態においても、第１実施形態と同様に、図６に示すように構成された配信ツリーにおいて、ノード１０ｂからメッセージが配信されるものとする。また、その他の第２実施形態における前提は、第１実施形態と同様である。
まず、ノード１０ｂのメッセージ配信処理について、図９を参照しながら説明する。ノード１０ｂは、一番初めにメッセージを配信する隣接ノードを決定する。具体的には、管理制御部１５ｂの配信順序決定機能１５１ｂは、隣接履歴保持部１３ｂに保持されている履歴を参照して、自ノード１０ｂに現在接続されている隣接ノードを把握する。
【００６２】
ここでは、図３に示すように、接続履歴テーブル１３１ｂには、ノードＩＤ“１”を内包する履歴が記憶されており、また、被接続履歴テーブル１３２ｂには、ノードＩＤ“６”  を内包する履歴と、ノードＩＤ“８”  を内包する履歴と、ノードＩＤ“９”  を内包する履歴とが記憶されている。このため、配信順序決定機能１５１ｂは、ノード１０ａ、１０ｆ、１０ｈ、１０ｉの４つが隣接ノードであると把握する。
【００６３】
そして、配信順序決定機能１５１ｂは、ノード１０ａ、１０ｆ、１０ｈ、１０ｉ各々について、隣接履歴保持部１３ｂに保持されている履歴を参照して、各々のノードに接続されている隣接ノード数を算出する。ここでは、配信順序決定機能１５１ｂは、ノード１０ａの隣接ノード数“３”と、ノード１０ｆの隣接ノード数“１”と、ノード１０ｈの隣接ノード数“１”と、ノード１０ｉの隣接ノード数“１”とを算出する。そして、配信順序決定機能１５１ｂは、各々の隣接ノード数の大きさを比較する。そして、配信順序決定機能１５１ｂは、一番大きい隣接ノード数“３”を保持する隣接ノード１０ａを選択する（ステップＳ３０１：該当ノードあり）。
【００６４】
管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ステップＳ３０１において選択したノード１０ａにメッセージを配信するよう指示する。メッセージ送信部１４ｂは、ノード１０ａにメッセージを配信する。管理制御部１５ｂは、当該ノード１０ａを選択対象より外す（ステップＳ３０２）。
そして、管理制御部１５ｂは、該当ノードがなくなるまで（ステップＳ３０１：該当ノードなし）、該当ノードにメッセージを配信する（ステップＳ３０２）。
【００６５】
なお、隣接ノード数が同一のノードが存在した場合には、管理制御部１５ｂは、例えば、第１実施形態で用いた配信順序決定のアルゴリズムを用いて、配信順序を決定する。
次に、ノード１０ｂよりメッセージを受信したノード１０ａのメッセージ転送処理について、図１０を参照しながら説明する。
【００６６】
ノード１０ａのメッセージ受信部１２ａがメッセージを受信すると、管理制御部１５ａの配信順序決定機能１５１ａは、隣接履歴保持部１３ａに保持されている履歴を参照して、転送元ノード１０ｂ以外で、自ノード１０ａに現在接続されている隣接ノードを把握する。ここでは、図７に示すように、接続履歴テーブル１３１ａには、なにも履歴が記憶されておらず、また、被接続履歴テーブル１３２ａには、ノードＩＤ“２”を内包する履歴と、ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴とが記憶されている。このため、配信順序決定機能１５１ａは、ノード１０ｂ、１０ｃ、１０ｄの３つが隣接ノードであると把握するが、ノード１０ｂはメッセージ転送元ノードのため、選択対象外とする。
【００６７】
そして、配信順序決定機能１５１ａは、ノード１０ｃとノード１０ｄについて、隣接履歴保持部１３ａに保持されている履歴を参照して、各々のノードに接続されている隣接ノード数を算出する。ここでは、配信順序決定機能１５１ａは、ノード１０ｃの隣接ノード数“３”、ノード１０ｄの隣接ノード数“１”を算出する。配信順序決定機能１５１ａは、これらの隣接ノード数を比較する。そして、配信順序決定機能１５１ａは、一番大きい隣接ノード数“３”を有する隣接ノード１０ｃを選択する（ステップＳ４０１：該当ノードあり）。
【００６８】
管理制御部１５ａは、メッセージ送信部１４ａに対して、ステップＳ４０１において選択したノード１０ｃにメッセージを転送するよう指示する。メッセージ送信部１４ａは、ノード１０ｃに、メッセージを転送する。管理制御部１５ａは、メッセージ転送済みのノード１０ｃを選択対象より外す（ステップＳ４０２）。そして、管理制御部１５ａは、該当ノードがなくなるまで（ステップＳ４０１：該当ノードなし）、該当ノードにメッセージを転送する（ステップＳ４０２）。
【００６９】
図６に示す配信ツリーを構成する、その他のノードの動作は、上述したノード１０ａの動作と基本的に同様である。また、第１実施形態と第２実施形態において説明した配信順序決定のアルゴリズムは、多くのノードが接続されているノードに、先にメッセージを配信するアルゴリズムであるため、第２実施形態におけるメッセージ配信シーケンスは、第１実施形態と同様のメッセージ配信シーケンスとなる。
以上のように、多くのノードが接続されているノードに、先にメッセージを配信するアルゴリズムとすることで、効率的なメッセージ配信シーケンスを実現することができる。
【００７０】
［３．第３実施形態］
［３．１．構成］
次に、本発明に係る第３実施形態について説明する。
まず、第３実施形態における構成について説明する。図１１は、第３実施形態におけるノード１０の機能構成を示すブロック図である。第１実施形態と異なる点は、ノード１０がメッセージ受信頻度管理部１１を備えている点である。
当該メッセージ受信頻度管理部１１は、図１２に示すように、転送元ノードを識別するための「ノードＩＤ」毎に、メッセージを受信した「頻度」を記憶している。ここでは、「頻度」は、例えば、１時間という単位時間の間に、転送元ノードより配信されてきたメッセージの数を表している。
【００７１】
また、ノード１０の記憶部には、第１実施形態と異なるプログラムが記憶されている。ノード１０のＣＰＵが、このプログラムを実行することにより、メッセージ受信部１２が受信したメッセージの数を、転送元ノードＩＤ毎に、時間単位で集計し、メッセージ受信頻度管理部１１に記憶する。
また、ノード１０の記憶部には、第１実施形態とは異なる、配信順序決定のためのプログラムが記憶されている。これにより、管理制御部１５の配信順序決定機能１５１は、第１実施形態と異なるアルゴリズムを用いて、メッセージの配信順序を決定する。第３実施形態におけるメッセージの配信順序を決定するアルゴリズムは、「より多くのノードが接続されているノードに、先にメッセージを配信する」という考えと、「メッセージを高い頻度で配信してくるノードには、より多くのノードが接続されている」という考えに基づいている。
【００７２】
上記以外の第３実施形態の構成は、第１実施形態と同様である。
次に、メッセージ配信元のノード１０が実行するメッセージ配信処理について、図１３のフローチャートを参照しながら説明する。
まず、管理制御部１５の配信順序決定機能１５１は、隣接履歴保持部１３に記憶されている履歴を参照して、第２実施形態と同様に、自ノードに現在接続されている隣接ノードを全て把握する。配信順序決定機能１５１は、把握した隣接ノードのノードＩＤをメッセージ受信頻度管理部１１より検索する。そして、配信順序決定機能１５１は、検索した「ノードＩＤ」に対応する「頻度」を読み出す。配信順序決定機能１５１は、読み出した「頻度」同士を比較する。そして、配信順序決定機能１５１は、一番高い「頻度」に対応する「ノードＩＤ」で識別されるノードを選択する（ステップＳ５０１：該当ノードあり）。
【００７３】
管理制御部１５は、メッセージ送信部１４に対して、ステップＳ５０１において選択したノードにメッセージを配信するよう指示する。そして、管理制御部１５は、当該ノードを選択対象より外す（ステップＳ５０２）。
配信順序決定機能１５１は、ステップＳ５０１に戻り、選択対象外としたノードを除いた隣接ノードの中から、メッセージを受信した頻度が高いノード１０を選択する。
【００７４】
なお、「頻度」が同一であるノードが存在した場合には、配信順序決定機能１５１は、例えば、第１実施形態や第２実施形態において説明したアルゴリズムを用いて配信順序を決定する。
また、メッセージ受信部１２によるメッセージの受信が１度もないために、メッセージ受信頻度管理部１１に「頻度」に関するデータが管理されていない隣接ノードが存在する場合には、配信順序決定機能１５１は、当該隣接ノードの「頻度」を“０”と判断し、当該隣接ノードに対して一番後にメッセージを配信する。
【００７５】
全て選択対象外のノード１０となり、該当ノード１０が存在しない場合には（ステップＳ５０１；該当ノードなし）、管理制御部１５は、処理を終了する。
該当ノードが存在する場合には（ステップＳ５０１；該当ノードあり）、管理制御部１５は、該当ノードが存在しなくなるまで（ステップＳ５０１；該当ノードなし）、該当ノードにメッセージを配信する（ステップＳ５０２）。
【００７６】
次に、隣接ノードよりメッセージを受信したノード１０が実行するメッセージ転送処理について、図１４のフローチャートを参照しながら説明する。
図１４のメッセージ転送処理が、図１３のメッセージ配信処理と異なる点は、メッセージ受信部１２が隣接ノードよりメッセージを受信したことがきっかけとなって処理が開始される点と、ステップＳ６０１において、該当ノードが存在するか否かを判定する際に、メッセージ転送元の隣接ノードを対象外とする点である。その他の図１４に示すメッセージ転送処理の流れは、図１３に示すメッセージ配信処理と同様であるため、重複した説明を省略する。
【００７７】
［３．２．動作］
次に、上記構成における、第３実施形態の動作について説明する。
第３実施形態においても、第１実施形態と同様に、図６に示すように構成された配信ツリーにおいて、ノード１０ｂからメッセージが配信されるものとする。また、その他の前提も第１実施形態と同様であるものとする。
また、ノード１０ｂのメッセージ受信頻度管理部１１ｂには、図１２に示すデータが管理されているものとする。また、ノード１０ａのメッセージ受信頻度管理部１１ａには、図１５に示すデータが管理されているものとする。
【００７８】
まず、ノード１０ｂのメッセージ配信処理について、図１３を参照しながら説明する。管理制御部１５ｂの配信順序決定機能１５１ｂは、隣接履歴保持部１３ｂに記憶されている履歴を参照して、自ノード１０ｂに現在接続されている隣接ノードを把握する。
ここでは、第２実施形態と同様に、配信順序決定機能１５１ｂは、ノードＩＤ“１”で識別されるノード１０ａと、ノードＩＤ“６”で識別される１０ｆと、ノードＩＤ“８”で識別される１０ｈと、ノードＩＤ“９”で識別される１０ｉとが隣接ノードであると把握する。
【００７９】
そして、配信順序決定機能１５１ｂは、把握した隣接ノードについて、メッセージ受信頻度管理部１１ｂより、当該ノードに対応するメッセージの「頻度」を読み出す。ここでは、配信順序決定機能１５１ｂは、ノードＩＤ“１”の「頻度」“１０回／ｈ”、ノードＩＤ“６”の「頻度」“５回／ｈ”、ノードＩＤ“８”の「頻度」“７回／ｈ”、ノードＩＤ“９”の「頻度」“４回／ｈ”を読み出す。配信順序決定機能１５１は、読み出した「頻度」を比較する。そして、配信順序決定機能１５１ｂは、一番頻度が高いのは「頻度」“１０回／ｈ”であるため、転送元ノードＩＤ“１”で識別されるノード１０ａを選択する（ステップＳ５０１：該当ノードあり）。
【００８０】
管理制御部１５ｂは、メッセージ送信部１４ｂに対して、ノード１０ａにメッセージを配信するよう指示する。メッセージ送信部１４ｂは、ノード１０ａにメッセージを配信する。そして、管理制御部１５ｂは、メッセージ配信済みのノード１０ａを選択対象より外す（ステップＳ５０２）。
配信順序決定機能１５１ｂは、ステップＳ５０１に戻り、選択対象外のノード１０ａを除いた隣接ノードのうち、「頻度」が高いノードＩＤ“６”を選択し（ステップＳ５０１；該当ノードあり）、管理制御部１５ｂはノードＩＤ“６”で識別される１０ｆにメッセージを配信する指示を行う（ステップＳ５０２）。そして、管理制御部１５ｂは、該当ノードが存在しなくなるまで（ステップＳ５０１；該当ノードなし）、該当ノードにメッセージを配信する（ステップＳ５０２）。
【００８１】
次に、ノード１０ｂよりメッセージを受信したノード１０ａのメッセージ転送処理について、図１４を参照しながら説明する。
メッセージ受信部１２ａがメッセージを受信すると、第２実施形態と同様に、管理制御部１５ａの配信順序決定機能１５１ａは、隣接履歴保持部１３ａに記憶されている履歴を参照して、転送元ノード１０ｂ以外で、自ノード１０ａに現在接続されている隣接ノードを把握する。ここでは、図７に示すように、接続履歴テーブル１３１ａには、なにも履歴が記憶されておらず、また、被接続履歴テーブル１３２ａには、ノードＩＤ“２”を内包する履歴と、ノードＩＤ“３”を内包する履歴と、ノードＩＤ“４”を内包する履歴とが記憶されている。このため、配信順序決定機能１５１ａは、ノード１０ｂ、１０ｃ、１０ｄの３つが隣接ノードであると把握するが、ノード１０ｂはメッセージ転送元ノードのため、選択対象外とする。
【００８２】
そして、配信順序決定機能１５１ａは、ノードＩＤ“３”で識別されるノード１０ｃと、ノードＩＤ“４”で識別されるノード１０ｄについて、メッセージ受信頻度管理部１１ａより、当該ノードに対応するメッセージの「頻度」を読み出す。ここでは、配信順序決定機能１５１ａは、ノードＩＤ“３”の「頻度」“３回／ｈ”と、ノードＩＤ“４”の「頻度」“１回／ｈ”とを読み出す。配信順序決定機能１５１ａは、読み出した「頻度」を比較する。そして、配信順序決定機能１５１ａは、一番高い頻度は、「頻度」“３回／ｈ”であるため、ノードＩＤ“３”で識別されるノード１０ｃを選択する（ステップＳ６０１：該当ノードあり）。
【００８３】
管理制御部１５ａは、メッセージ送信部１４ａに対して、ノード１０ｃにメッセージを転送するよう指示する。メッセージ送信部１４ａは、ノード１０ｃにメッセージを転送する。そして、管理制御部１５ａは、メッセージ転送済みのノード１０ｃを選択対象より外す（ステップＳ６０２）。
配信順序決定機能１５１ａは、ステップＳ６０１に戻り、選択対象外のノード１０ｃを除いた隣接ノードのうち、「頻度」が高いノードＩＤ“４”を選択し（ステップＳ６０１；該当ノードあり）、管理制御部１５ａは、ノードＩＤ“４”で識別される１０ｄにメッセージを転送するよう指示する（ステップＳ６０２）。これにより、該当ノードが存在しなくなるため（ステップＳ５０１；該当ノードなし）、管理制御部１５ａは処理を終了する。
【００８４】
図６に示す配信ツリーを構成する、その他のノードの動作は、上述したノード１０ａの動作と基本的に同様である。また、第１実施形態乃至第３実施形態において説明した配信順序決定のアルゴリズムは、多くのノードが接続されているノードに、先にメッセージを配信するアルゴリズムである。よって、第３実施形態におけるメッセージ配信シーケンスは、メッセージを他のノードから受信する頻度と、当該他のノードに接続されている隣接ノード数とが比例する場合には、第１実施形態及び第２実施形態と同様のメッセージ配信シーケンスとなる。
【００８５】
このように、メッセージを配信してくる頻度が高いノードを選択して、先にメッセージを配信することにより、メッセージの頻度とノードに接続されているノードの数とが比例するという前提の基、多くのノードが接続されているノードに、先にメッセージを配信することができるため、最適なメッセージ配信のシーケンスを実現できる。
【００８６】
［４．変形例］
以上、本発明の実施形態について説明したが、本発明は係る実施形態に限定されるものではなく、その技術思想の範囲内で様々な変形が可能である。変形例としては、例えば、以下のようなものが考えられる。
（１）上記第１実施形態乃至第３実施形態においては、配信順序決定機能１５１による配信順序決定のアルゴリズムを３種類説明したが、これらのアルゴリズムは例示に過ぎない。上記３種類のアルゴリズムは、「より多くのノードが接続されているノードに、先にメッセージを配信する」という考えに基づいている。この考えに基づいており、かつ、隣接履歴保持部１３に保持された履歴を利用するものであれば、他のアルゴリズムを用いてもよい。
【００８７】
例えば、図４に示すアルゴリズムにおいては、ノード１０は、自ノード１０が接続した隣接ノードにメッセージを配信した後に、自ノード１０が接続された隣接ノードにメッセージを配信したが、その逆に、自ノードが接続された隣接ノードにメッセージを配信してから、自ノードが接続した隣接ノードにメッセージを配信するようにしてもよい。
【００８８】
また、自ノード１０が隣接ノードに接続した場合と接続された場合とを区別せずに、長い間接続している隣接ノードに、先にメッセージを送信するようにしてもよい。
また、上記で説明したアルゴリズムを複合的に用いて配信順序を決定してもよい。例えば、メッセージ配信元となるノードのアルゴリズムとして、第１実施形態において図４に示したアルゴリズムを用い、受信したメッセージを他のノードに転送するノードのアルゴリズムとして、第２実施形態の図１０に示したアルゴリズムを用いてもよい。
【００８９】
（２）上記実施形態で説明した隣接履歴保持部１３のデータ構成は例示に過ぎない。例えば、隣接履歴保持部１３には、接続履歴テーブル１３１と被接続履歴テーブル１３２との２つのテーブルを設けたが、１つのテーブルとしてもよい。また、上記実施形態においては、隣接履歴保持部１３には、隣接ノードの接続（参加）に関する履歴のみが保持されており、隣接ノードは配信グループに参加した後に離脱（脱退）していないとして説明したが、離脱に関する情報も履歴として保持するようにしてもよい。この場合には、管理制御部１５は、メッセージ配信処理又はメッセージ転送処理を行う際に、隣接履歴保持部１３に保持されている、接続に関する情報と離脱に関する情報とに基づいて、現在接続している隣接ノードを判定するようにする。
【００９０】
（３）上記第２実施形態においては、ノード１０の隣接履歴保持部１３には、通信ネットワーク１を構成する全てのノードについての履歴が、他のノードより通知されて保持されているとして説明したが、他のノードより通知される情報は、これに限定されない。例えば、ノード１０に通知されてくる情報は、接続変更に関する情報（履歴）のみならず、隣接ノード数であってもよいし、他のノードの構成情報や管理情報であってもよい。また、上記第２実施形態においては、他のノードの接続状態が変更されたときに、当該他のノードからノード１０に変更情報が通知されるとして説明したが、他のノードからノード１０への通知タイミングは、これに限定されない。例えば、毎週定期的に、他のノードからノード１０へ、変更情報が通知されるようにしてもよい。
【００９１】
（４）第３実施形態におけるメッセージ受信頻度管理部１１では、ノードＩＤ毎にメッセージが配信されてきた「頻度」を記憶することとしたが、これに限定されない。例えば、メッセージ受信頻度管理部１１は、「頻度」の代わりに、「メッセージ受信日時」とメッセージ転送元の「ノードＩＤ」とを記憶するようにし、メッセージ転送処理時に、当該記憶されている情報に基づいて、メッセージ転送元ノード毎に、「頻度」を算出するようにしてもよい。また、「頻度」は、上記実施形態においては、１時間当たりのメッセージ受信数として説明したが、これに限定されず、例えば、１分間当たりのメッセージ受信数であってよい。また、「頻度」の算出方法としては、他のノードから受信したメッセージの累積受信回数を、当該ノードと接続している経過時間で除算を行ってもよいし、また、リアルタイムで、１時間毎に他のノードから受信したメッセージ数を逐次算出する仕組みであってもよい。
【００９２】
【発明の効果】
以上説明したように、ノード装置は、隣接ノード装置との接続状態に関する履歴に基づいてメッセージ配信順序を決定するため、最適な配信シーケンスにより、効率的に、前記通信ネットワークが備えるノード装置全てにメッセージを転送することができる。このため、ノード装置全てに短時間でメッセージを配信することができ、各ノード装置へのメッセージ到達遅延を防ぐことができる。
【図面の簡単な説明】
【図１】本発明の第１実施形態に係る通信ネットワークの構成を示すブロック図である。
【図２】本発明の第１実施形態に係るノードの機能構成を示すブロック図である。
【図３】本発明の第１実施形態に係る隣接履歴保持部が保持するデータの構成を示す図である。
【図４】本発明の第１実施形態に係るメッセージ配信元のノードが行うメッセージ配信処理を示すフローチャートである。
【図５】本発明の第１実施形態に係るメッセージを転送するノードが行うメッセージ転送処理を示すフローチャートである。
【図６】本発明の第１実施形態に係るメッセージ配信シーケンスを説明するための図である。
【図７】本発明の第１実施形態に係るノード１０ａの隣接履歴保持部が保持するデータ内容を示す図である。
【図８】本発明の第１実施形態に係るノード１０ｃの隣接履歴保持部が保持するデータ内容を示す図である。
【図９】本発明の第２実施形態に係るメッセージ配信元のノードが行うメッセージ配信処理を示すフローチャートである。
【図１０】本発明の第２実施形態に係るメッセージを転送するノードが行うメッセージ転送処理を示すフローチャートである。
【図１１】本発明の第３実施形態に係るノードの機能構成を示すブロック図である。
【図１２】本発明の第３実施形態に係るメッセージ受信頻度管理部により管理されるデータ構成を示す図である。
【図１３】本発明の第３実施形態に係るメッセージ配信元のノードが行うメッセージ配信処理を示すフローチャートである。
【図１４】本発明の第３実施形態に係るメッセージを転送するノードが行うメッセージ転送処理を示すフローチャートである。
【図１５】本発明の第３実施形態に係るノード１０ａのメッセージ受信頻度管理部により管理されるデータ内容を示す図である。
【図１６】従来の通信ネットワークにおけるルータを用いたメッセージ転送方式を説明する図である。
【図１７】従来のルータを用いないノード間のメッセージ転送方式を説明する図である。
【図１８】従来のメッセージ配信グループにおける配信ツリーの構成例を示す図である。
【図１９】配信ツリーにおける最適化されていないメッセージ配信シーケンスを説明するための図である。
【図２０】配信ツリーにおける最適化されたメッセージ配信シーケンスを説明するための図である。
【符号の説明】
１      通信ネットワーク
１０    ノード
１１    メッセージ受信頻度管理部
１２    メッセージ受信部
１３    隣接履歴保持部
１４    メッセージ送信部
１５    管理制御部
１５１  配信順序決定機能
【図１】
2005027099.tif 000003
【図２】
2005027099.tif 000004
【図３】
2005027099.tif 000005
【図４】
2005027099.tif 000006
【図５】
2005027099.tif 000007
【図６】
2005027099.tif 000008
【図７】
2005027099.tif 000009
【図８】
2005027099.tif 000010
【図９】
2005027099.tif 000011
【図１０】
2005027099.tif 000012
【図１１】
2005027099.tif 000013
【図１２】
2005027099.tif 000014
【図１３】
2005027099.tif 000015
【図１４】
2005027099.tif 000016
【図１５】
2005027099.tif 000017
【図１６】
2005027099.tif 000018
【図１７】
2005027099.tif 000019
【図１８】
2005027099.tif 000020
【図１９】
2005027099.tif 000021
【図２０】
2005027099.tif 000022