(57)【要約】      （修正有）【課題】ノードの死活管理を適切に行なうことが可能な通信装置を提供する。【解決手段】通信装置は他の通信装置の名称、該装置からの最新のシーケンス番号、受信時刻をノード情報として管理し、最新のシーケンス番号を他の通信装置から受信し、現在時刻と送信元通信装置の最新受信時刻との差分に基づき、シーケンス番号の標本平均の第１の補正値を計算し、ノード情報における送信元の受信時刻を現在時刻に更新し、ノード情報の送信元のシーケンス番号を送信元からのデータに含まれるシーケンス番号に更新し、通信装置の受信データ総数、シーケンス番号平均値、死活確率を死活情報として管理し、第１の補正値、ノード死活情報における送信元からのデータ総数、受信データのシーケンス番号に基づいて標本平均の第２の補正値を計算し、補正値、受信データのシーケンス番号の平均値に基づいて、受信データのシーケンス番号が平均値として受信される確率を計算する。【選択図】図４
2018046516.tif 000002
【特許請求の範囲】
【請求項１】
他の通信装置の名称、この通信装置から受信したデータに付与される最新のシーケンス番号、およびこの通信装置から最新のデータを受信した時刻である受信時刻をノード情報として管理する第１の管理手段と、
複数の通信装置の名称、および、他の通信装置が管理する、前記複数の通信装置の前記最新のシーケンス番号を含むデータを前記他の通信装置から受信する受信手段と、
前記データを受信したときの現在時刻と、前記ノード情報で示される、前記受信したデータの送信元である通信装置についての前記受信時刻との差分に基づいて、前記受信したデータで示される前記シーケンス番号の標本平均の第１の補正値を計算する第１の計算手段と、
前記ノード情報における前記送信元である通信装置についての前記受信時刻を、前記現在時刻に更新し、前記ノード情報における前記送信元である通信装置についての前記シーケンス番号を、前記送信元である通信装置からの前記データに含まれる前記シーケンス番号に更新する更新手段と、
他の通信装置の名称、この通信装置から受信した各データの総数、前記他の通信装置から受信した各データに付与される前記シーケンス番号の平均値、およびこの通信装置の死活確率をノード死活情報として管理する第２の管理手段と、
前記第１の補正値、前記ノード死活情報における前記送信元である通信装置から受信した各データの総数、および、前記送信元である通信装置から受信したデータに含まれる前記シーケンス番号に基づいて、前記シーケンス番号の標本平均の第２の補正値を計算する第２の計算手段と、
前記第２の補正値、および、前記受信したデータに含まれる前記シーケンス番号の平均値に基づいて、前記受信したデータに付与される前記シーケンス番号が前記平均値として受信される確率を計算する第３の計算手段と
を備えたことを特徴とする通信装置。
【請求項２】
前記現在時刻と、前記ノード情報における各通信装置の前記受信時刻とを比較して、前記現在時刻との差分が最も大きい前記受信時刻について前記ノード情報で対応する通信装置を新たなデータの送信先として選択して、この選択した通信装置に前記新たなデータを送信する送信手段をさらに備えた
ことを特徴とする請求項１に記載の通信装置。
【請求項３】
通信装置に適用される方法であって、
他の通信装置の名称、この通信装置から受信したデータに付与される最新のシーケンス番号、およびこの通信装置から最新のデータを受信した時刻である受信時刻をノード情報として管理し、
複数の通信装置の名称、および、他の通信装置が管理する、前記複数の通信装置の前記最新のシーケンス番号を含むデータを前記他の通信装置から受信し、
前記データを受信したときの現在時刻と、前記ノード情報で示される、前記受信したデータの送信元である通信装置についての前記受信時刻との差分に基づいて、前記受信したデータで示される前記シーケンス番号の標本平均の第１の補正値を計算し、
前記ノード情報における前記送信元である通信装置についての前記受信時刻を、前記現在時刻に更新し、前記ノード情報における前記送信元である通信装置についての前記シーケンス番号を、前記送信元である通信装置からの前記データに含まれる前記シーケンス番号に更新し、
他の通信装置の名称、この通信装置から受信した各データの総数、前記他の通信装置から受信した各データに付与される前記シーケンス番号の平均値、およびこの通信装置の死活確率をノード死活情報として管理し、
前記第１の補正値、前記ノード死活情報における前記送信元である通信装置から受信した各データの総数、および、前記送信元である通信装置から受信したデータに含まれる前記シーケンス番号に基づいて、前記シーケンス番号の標本平均の第２の補正値を計算し、
前記第２の補正値、および、前記受信したデータに含まれる前記シーケンス番号の平均値に基づいて、前記受信したデータに付与される前記シーケンス番号が前記平均値として受信される確率を計算する
ことを特徴とする通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、通信装置および通信方法に関する。
【背景技術】
【０００２】
IoT（（Internet of Things））ビジネスが盛んになると、多くの機器が相互接続され、多量のデータを格納する必要がある。  
この結果、分散システム化が進むので、分散システムを構成する通信装置であるノードの死活管理が問題となる。
【０００３】
ノード間の通信のための従来技術としてゴシッププロトコル（Gossip Protocol）がある。  
このゴシッププロトコルでは、各ノードは通信先のノードをΔｔ時間ごとにランダムに選択し、この選択したノードに自身が持っているデータを送信する。
【０００４】
選択されたノードは、送信元のノードから受信したデータと自身が持っているデータとを比較し、自身が、より新しい情報を持っている場合には、この新しい情報を、差分データとして送信元のノードに返却する。  
このゴシッププロトコルは、噂話や伝染病の広がり具合と同様で、ノード数が増加しても情報伝達が早いプロトコルである。
【０００５】
また、ノードの故障検出のための従来技術として、アクノーアル故障検出器がある。このアクノーアル故障検出器は、各ノードのハートビートを故障検出器でサンプリングウインドウ分だけサンプリングし、ハートビート受信時間間隔をもとに正規分布を作って故障確率φを計算する。このアクノーアル故障検出器は、故障確率φの値に従って各ノードが故障の疑いを数段階で管理する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】The ψ Accrual Failure Detector, Naohiro Hayashibara1, Xavier Defago1,2, Rami Yared1,and Takuya Katayama1,May 10, 2004,２０１６年８月２５日検索、インターネット＜http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.7427&rep=rep1&type=pdf＞
【非特許文献２】林原尚浩, “アクノーアル故障検出器ACCMOSの実装と評価”, 情報処理学会論文誌, Vol.51, No.12, pp.2310-2318, Dec. 2010.
【非特許文献３】林原尚浩, "アクルーアル故障検出器を用いた故障検出精度の制御," 第141回マルチメディア通信と分散処理(DPS)研究会, 2009-DPS-141, 情報処理学会, 2009年11月.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のアクノーアル故障検出器は、故障検出器自体がノード（プロセス）の外側に存在するので、故障検出器自体が故障点になってしまい、ノードごとに故障確率を管理することができない。  
また、アクノーアル故障検出器は、ある程度のサンプリング数が得られないとノードの死活管理ができない。
【０００８】
また、上記のゴシッププロトコルにおいて、メッセージを収受したノードは、ネットワーク上での遅延や自身の負荷の変化によって、最新の死活情報を有することができない可能性がある。
【０００９】
本発明の目的は、ノードの死活管理を適切に行なうことが可能な通信装置および通信方法を提供することである。
【課題を解決するための手段】
【００１０】
実施形態における通信装置は、他の通信装置の名称、この通信装置から受信したデータに付与される最新のシーケンス番号、およびこの通信装置から最新のデータを受信した時刻である受信時刻をノード情報として管理する第１の管理手段と、複数の通信装置の名称、および、他の通信装置が管理する、前記複数の通信装置の前記最新のシーケンス番号を含むデータを前記他の通信装置から受信する受信手段と、前記データを受信したときの現在時刻と、前記ノード情報で示される、前記受信したデータの送信元である通信装置についての前記受信時刻との差分に基づいて、前記受信したデータで示される前記シーケンス番号の標本平均の第１の補正値を計算する第１の計算手段と、前記ノード情報における前記送信元である通信装置についての前記受信時刻を、前記現在時刻に更新し、前記ノード情報における前記送信元である通信装置についての前記シーケンス番号を、前記送信元である通信装置からの前記データに含まれる前記シーケンス番号に更新する更新手段と、他の通信装置の名称、この通信装置から受信した各データの総数、前記他の通信装置から受信した各データに付与される前記シーケンス番号の平均値、およびこの通信装置の死活確率をノード死活情報として管理する第２の管理手段と、前記第１の補正値、前記ノード死活情報における前記送信元である通信装置から受信した各データの総数、および、前記送信元である通信装置から受信したデータに含まれる前記シーケンス番号に基づいて、前記シーケンス番号の標本平均の第２の補正値を計算する第２の計算手段と、前記第２の補正値、および、前記受信したデータに含まれる前記シーケンス番号の平均値に基づいて、前記受信したデータに付与される前記シーケンス番号が前記平均値として受信される確率を計算する第３の計算手段とを有する。
【発明の効果】
【００１１】
本発明によれば、ノードの死活管理を適切に行なうことができる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施形態における通信システムの構成例を示す図。
【図２】第１の実施形態における通信システムのノードが管理するノード情報の構成例を表形式で示す図。
【図３】第１の実施形態における通信システムのノードが管理するノード死活情報の構成例を表形式で示す図。
【図４】第１の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャート。
【図５】第１の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャート。
【図６】第１の実施形態における通信システムのノードによる管理情報の変更の一例を示す図。
【図７】第１の実施形態における通信システムのノードの死活確率の分布の一例を示す図。
【図８】第２の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャート。
【図９】第２の実施形態における通信システムのノードによるメッセージ送信の一例を示す図。
【発明を実施するための形態】
【００１３】
以下、実施形態について図面を用いて説明する。  
（第１の実施形態）
まず、第１の実施形態について説明する。図１は、第１の実施形態における通信システムの構成例を示す図である。  
図１に示すように、第１の実施形態における通信システムは、複数のノード１０がネットワーク２０により通信可能に接続されてなる。図１では２つのノードを示すが、数は特に限られない。
【００１４】
ノード１０は、クロック生成部１１、ノード情報ＤＢ（データベース）１２（第１の管理手段）、ノード死活情報ＤＢ１３（第２の管理手段）、ノード死活判定部１４（第１の計算手段、第２の計算手段、第３の計算手段）、メッセージ受信部１５およびメッセージ送信部１６を有する。
【００１５】
ノード１０は、ゴシッププロトコルで通信を行う主体である。すべてのノード１０は同じ機能を有するとする。  
クロック生成部１１は、現在時刻を計時する。ノード情報ＤＢ１２と、ノード死活情報ＤＢ１３は、例えば不揮発性メモリなどの記憶装置により実現される。
【００１６】
図２は、第１の実施形態における通信システムのノードが管理するノード情報の構成例を表形式で示す図である。  
ノード情報ＤＢ１２は、図２に示すノード情報を記憶する。このノード情報は、各ノード１０に固有のノード名称、各ノードから送信されたパケットデータであるメッセージデータ（以下、メッセージと称することがある）のそれぞれに付与された通し番号である、最新のシーケンス番号、各ノードからのデータの最新メッセージの受信時刻を各ノードについて関連付けて管理するための情報である。
【００１７】
図３は、第１の実施形態における通信システムのノードが管理するノード死活情報の構成例を表形式で示す図である。  
ノード死活情報ＤＢ１３は、図３に示すノード死活情報を記憶する。このノード死活情報は、各ノード１０に固有のノード名称、各ノードのそれぞれから受信したメッセージの総数、各ノード１０それぞれから逐次受信したメッセージに含まれるシーケンス番号の平均値、各ノード１０の死活確率を関連付けて管理する。
【００１８】
図４は、第１の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャートである。  
この第１の実施形態では、メッセージとして受信した各ノードのシーケンス番号に基づいて、各ノードの死活確率をベイズ統計で推定し、更新処理も併せて行う。
【００１９】
ノード１０のメッセージ受信部１５が、他のノードからメッセージ（各ノードのノード名称、シーケンス番号を含む）を受信すると、クロック生成部１１は、ノードの現時刻（現在時刻）ｔｎｏｗを取得する（Ａ１）。
【００２０】
次に、ノード死活判定部１４は、ノード情報ＤＢ１２からノード情報を取得する（Ａ２）。  
ノード死活判定部１４は、受信メッセージにおけるｉ＝０，…，ｎ個のエントリ数（送信元のノードの数）だけ繰り返すループを開始し、上記のように受信したメッセージにおける現在のエントリのノード名称をノード名称ｎｏｄｅとする。
【００２１】
次に、ノード死活判定部１４は、ノード情報におけるノード名称ｎｏｄｅに対応する最新メッセージ受信時刻ｔｌａｓｔを取得する。  
また、他のノードから受信したメッセージに含まれる、各ノードのシーケンス番号を、平均値μおよび分散σ２の正規分布
【００２２】
【数１】
2018046516.tif 000003
【００２３】
に従う母集団から取得した標本であると仮定したとき、ｎ個のメッセージに含まれるシーケンス番号をそれぞれ取得している間に時間が経過して、各ノードが送信するシーケンス番号がインクリメントされる。
【００２４】
そこで、ノード死活判定部１４は、上記の受信したｎ個のメッセージに含まれるシーケンス番号の標本平均
【００２５】
【数２】
2018046516.tif 000004
【００２６】
を以下の式（１）にしたがって補正する（Ａ３（第１の計算手段としての処理））。
【００２７】
【数３】
2018046516.tif 000005
【００２８】
現在のエントリにおける受信メッセージに含まれるシーケンス番号が、ノード情報に含まれるシーケンス番号以上であれば（Ａ４のＹＥＳ）、ノード死活判定部１４は、現在のエントリにおける受信メッセージに記録されたノード名称ｎｏｄｅに対応するノードからの最新メッセージ受信時刻である、Ａ１で取得した現時刻を、ノード情報におけるノード名称ｎｏｄｅに記録された最新メッセージ受信時刻に反映する。  
また、ノード死活判定部１４は、現在のエントリにおける受信メッセージに記録されたノード名称ｎｏｄｅのシーケンス番号を、ノード情報におけるノード名称ｎｏｄｅのシーケンス番号に反映する（Ａ５）。
【００２９】
次に、ノード死活判定部１４は、ノード死活情報での死活確率φを計算する（Ａ６）。この計算の詳細については後述する。  
そして、受信メッセージにおけるｉ＝０，…，ｎ個のエントリ数だけ繰り返すループが終了すると、メッセージ送信部は、メッセージを送信してきたノード向けにノード情報を送信する（Ａ７）。
【００３０】
次に、Ａ６の処理の詳細について説明する。図５は、第１の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャートである。Ａ６の処理として、ノード死活判定部１４は、ノード死活情報で対応する、現在のエントリの受信メッセージ総数をｎとする（Ｂ１）。
【００３１】
ノード死活判定部１４は、Ａ３で求めた標本平均
【００３２】
【数４】
2018046516.tif 000006
【００３３】
を以下の式（２）に応じて補正する（Ｂ２（第２の計算手段としての処理））。
【００３４】
【数５】
2018046516.tif 000007
【００３５】
このとき、ノードが、ｎ個だけシーケンス番号を他のノードから受信できた場合、事後分布（平均値μの確率密度関数）は
【００３６】
【数６】
2018046516.tif 000008
【００３７】
となる。  
ノード死活判定部１４は、ノード死活情報における、現在のエントリの受信メッセージの平均シーケンス番号を上記の事後分布のμに代入することで、受信した最新のメッセージに含まれるシーケンス番号が平均値μとして観測される確率である死活確率φを求める（Ｂ３（第３の計算手段としての処理））。
【００３８】
Ｂ３で計算した確率φが一定値未満であれば（Ｂ４のＮｏ）、ノード死活判定部１４は、ノード死活情報における、該当ノードのノード死活確率φを、Ｂ３で計算した確率φに更新する（Ｂ５）。
【００３９】
一方、Ｂ３で計算した確率φが一定値以上であれば（Ｂ４のＹｅｓ）、ノード死活判定部１４は、ノード死活情報における、該当ノードの受信メッセージ総数をクリアし、ノード情報における最新のシーケンス番号をクリアする（Ｂ６）。  
Ｂ５またはＢ６の処理がなされることで、Ａ６の処理が終了する。
【００４０】
図６は、第１の実施形態における通信システムのノードによる管理情報の変更の一例を示す図である。  
図６に示すように、ノードＢがノードＡからメッセージを受信したと仮定すると、このノードＢによる上記のＡ１からＡ７までの処理を行なうことで、ノードＢが管理するノード情報における、ノードＡ，Ｄのシーケンス番号、最新メッセージ受信時刻が、ノードＡから受信したメッセージにおける、ノードＡ，Ｄのシーケンス番号、およびこれらの受信したメッセージの受信時刻に更新される。
【００４１】
また、ノードＢが管理するノード死活情報における、ノードＡの死活確率は、更新前と比較して現状維持（高いまま）となり、ノードＣの死活確率は更新前と比較して大きく下げられ、ノードＤの死活確率は前回の受信で一旦大きく下げられるが、今回の受信で上げられる。
【００４２】
具体的には、ノードＡについて、前回のメッセージ受信時刻(時刻172)における死活確率の計算結果が比較的高く、今回のメッセージ受信時刻（時刻195）における死活確率の計算結果も、今回受信したシーケンス番号について観測される可能性が高い確率である。
【００４３】
ノードＣについて、前回のメッセージ受信時刻(時刻172)における死活確率の計算結果が比較的高いとする。今回のメッセージ受信時刻（時刻195）において、シーケンス番号が200から更新されなかったために、最新メッセージ受信時刻が170から更新されなかった。これにより、今回送信されたシーケンス番号について観測される可能性が低い確率であるために、ノードＣの死活確率が低くなる。
【００４４】
ノードＤについて、前々回のメッセージ受信時刻(時刻152)における死活確率の計算結果が比較的高いとし、前回のメッセージ受信時刻(時刻172)における死活確率の計算結果で比較的低いとする。ここで、今回のメッセージ受信時刻（時刻195）においてシーケンス番号が122から126に更新されたことで、今回受信したシーケンス番号について観測される可能性が高い確率であるために、ノードＤの死活確率は上昇する。
【００４５】
図７は、第１の実施形態における通信システムのノードによるノードの死活確率の分布の一例を示す図である。  
図７に示すように、死活確率φに応じて、各ノードの信用度合いを表現することができる。今まで受信できていたデータのシーケンス番号から外れたシーケンス番号を受信するほど該当のノードの信用度合いは下がる。
【００４６】
図７に示したように、初期状態では、シーケンス番号の平均値μを横軸とした場合のノードＡの死活確率φ１、ノードＣの死活確率φ２、ノードｎの死活確率φｎの、分布は一律（低い確率）と仮定した場合で、他のノードからメッセージを受信するたびに、確率分布を更新した場合、新たに受信した、あるシーケンス番号に応じた確率が高い時は、ノードの信用度合いが高いとし、確率が低い時は、ノードの信用度合いが低いとして、ノードが機能しておらず、初期状態に戻す必要があると判断できる。
【００４７】
以上のように、第１の実施形態では、複数のサンプルデータが必要な従来のアクルーアル故障検知と比べて、各ノードの情報が十分集まらない状況下でも、ベイズ推定を用いる事で、少ない情報しかない状況でも、ある確率を仮定してノードの死活管理を行なうことができる。
【００４８】
また、各ノードが他ノードの死活確率を自律的に計算するため、他のノードから送信されてくるメッセージをそのまま信用せずに、それぞれが一番信用できるノードを利用することができるようになる。
【００４９】
（第２の実施形態）
次に、第２の実施形態について説明する。なお、この第２の実施形態について、第１の実施形態で説明した内容と同一の内容については説明を省略する。  
図８は、第２の実施形態における通信システムのノードによるノード死活管理のための手順の一例を示すフローチャートである。  
第２の実施形態では、各ノードは、自身が管理しているノード情報におけるノード名称およびシーケンス番号を、Δｔ時間ごとに他の１つのノードに向けて送信する。Δｔは各ノードで一律とする。
【００５０】
従来のゴシッププロトコルでは、各ノードは、送信先としての１つのノードをランダムに選択するが、本実施形態では、各ノードからの最新のメッセージの受信時刻を、ノード情報における最新メッセージ受信時刻に記録しておき、各ノードのうち、ノード情報における最新メッセージ受信時刻が一番古いノードを、送信先のノードとして優先的に選択する。つまり、できる限り、他のノードと交わりの少ないノードと交わるようにする。
【００５１】
ノード１０のメッセージ送信部１６は、Δｔごとにノード情報ＤＢ１２に格納されているノード情報を取得する（Ｃ１）。  
メッセージ送信部１６は、クロック生成部１１にて取得した現在時刻と、ノード情報で示される各ノードの最新メッセージ受信時刻とを比較し、一番時間が経過しているノード、つまり最新メッセージ受信時刻が最も古いノードを選択する（Ｃ２）。  
メッセージ送信部１６は、Ｃ２で選択したノードに向けて、直近に送信したシーケンス番号を１インクリメントしたしシーケンス番号を含むメッセージを送信する（Ｃ３）。
【００５２】
図９は、第２の実施形態における通信システムのノードによるメッセージ送信の一例を示す図である。  
図９に示したように、ノードＡが、ノードＢ、Ｃ、Ｄの中からメッセージの送信先のノードを選択する際に、ノードＡは、ノード情報で示されるノードＢ、Ｃ、Ｄの最新メッセージ受信のうち、最も古い時刻に対応する、ここでは時刻「１００」がノード情報で管理されるノードＢ（図９に示した例では「１０」→「１１」）を、新たなメッセージの送信先として選択する。  
ノードＡは、ノード情報で管理されるノードＡにおけるシーケンス番号を１インクリメント（図９に示した例では「１０」→「１１」）した番号を含むメッセージを、このノードＢに送信する。
【００５３】
以上のように、第２の実施形態では、従来のゴシッププロトコルと比べて、通信相手のノードをランダムに選ばないので、メッセージ収受の早い段階で、すべてのノード情報がネットワーク全体に拡散することを実現できる。
【００５４】
なお、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００５５】
１０…ノード、１１…クロック生成部、１２…ノード情報ＤＢ、１３…ノード死活情報ＤＢ、１４…ノード死活判定部、１５…メッセージ受信部、１６…メッセージ送信部、２０…ネットワーク。
【図１】
2018046516.tif 000009
【図２】
2018046516.tif 000010
【図３】
2018046516.tif 000011
【図４】
2018046516.tif 000012
【図５】
2018046516.tif 000013
【図６】
2018046516.tif 000014
【図７】
2018046516.tif 000015
【図８】
2018046516.tif 000016
【図９】
2018046516.tif 000017