(57)【要約】【課題】故障発見までの時間を従来技術程度に保ちつつ、ノードを管理するメモリ量を低減できる通信管理方法及びノードを提供することを目的とする。【解決手段】本発明に係る通信管理方法及びノードは、ノードの故障発見時に通知するノードをｓｕｃｃｅｓｓｏｒだけに管理させることで、非特許文献１及び２の手法とほぼ同じ故障発見時間を、３ｌｏｇＮのノードを管理するだけで実現する。このため、本発明はノードにおいて他のノードを管理する必要メモリを削減することができる。また、本発明は、ｓｕｃｃｅｓｓｏｒも故障したときに、通知すべきノードを推定する手段を有する。【選択図】図３
2016052030.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードからなる物理ネットワーク上に形成される構造化オーバレイネットワークを管理する通信管理方法であって、
前記ノードのそれぞれに、
自身のデータ転送先である前記ノードのＩＤをＰｏｉｎｔｅｒとして記憶させ、
自身をデータ転送先とする前記ノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶させ、
自身よりＩＤが小さい前記ノードのうち最大のＩＤを持つ前記ノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶させる記憶手順と、
任意の前記ノードが故障した時に、
故障した前記ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用いて構造化オーバレイネットワークを再構築する再構築手順と、
を備える通信管理方法。
【請求項２】
前記再構築手順では、
故障した前記ノードを転送先としていた前記ノードに対して、前記Ｐｏｉｎｔｅｒから故障した前記ノードを除去させ、
故障した前記ノードの直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードにコピーさせ、
故障した前記ノードを転送先としていた全ての前記ノードに対して、前記Ｐｏｉｎｔｅｒに前記直後ノードを追加させる
ことを特徴とする請求項１に記載の通信管理方法。
【請求項３】
前記直後ノードも故障している場合、
故障した前記ノードを転送先としていた前記ノードに対して、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードを検索させ、
前記次ノードに対して、故障した前記ノードのＩＤと故障した前記ノードを転送先としていた前記ノードのＩＤとの差分を用いて、故障した前記ノードを転送先としていた前記ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記ノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定させ、
推定した前記Ｂａｃｋｐｏｉｎｔｅｒの全ての前記ノードに、故障した前記ノードの代替が前記次ノードであることを通知させる推定通知手順
を備えることを特徴とする請求項１に記載の通信管理方法。
【請求項４】
構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶し、
自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
前記直前ノードが故障した時に、前記記憶部が記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用い、前記直前ノードを兼務するように構造化オーバレイネットワークを再構築する制御部と、
を備えるノード。
【請求項５】
前記制御部は、
故障した前記直前ノードを転送先としていた前記ノードに対して、前記Ｐｏｉｎｔｅｒから故障した前記直前ノードを除去させ、
前記直前Ｂａｃｋｐｏｉｎｔｅｒを、自身よりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードにコピーさせ、
故障した前記直前ノードを転送先としていた前記ノードに対して、自身のＩＤをＰｏｉｎｔｅｒとして追加させる
ことを特徴とする請求項４に記載のノード。
【請求項６】
構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
前記Ｐｏｉｎｔｅｒの前記他のノード、及び前記他のノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである直後ノードの双方が故障している場合、
前記直後ノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである次ノードを検索し、
前記次ノードに、故障した前記他のノードのＩＤと自身のＩＤの差分を用いて、自身が記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記他のノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定させる制御部と、
を備えることを特徴とするノード。
【請求項７】
構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
他のノードから、
自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノード、及び前記直前ノードよりＩＤが小さいノードのうち最大のＩＤを持つノードである従前ノードの双方が故障していることを通知されたときに、
前記従前ノードのＩＤと前記他のノードのＩＤの差分を用いて、前記他のノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記従前ノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定する制御部と、
を備えることを特徴とするノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノード（コンピュータあるいはプロセス）によって構成される論理ネットワークを管理する通信管理方法及びそのノードに関する。
【背景技術】
【０００２】
構造化オーバレイネットワークでは、故障などによってノードが論理ネットワークから離脱すると、ネットワークの構造を維持するために、新たな隣接関係を設定しなければならない。一般の構造化オーバレイネットワークでは、隣接関係にあるノードは定期的にｋｅｅｐ−ａｌｉｖｅメッセージを送信し、応答がなければ故障と判断して新たな隣接関係を設定し始める。
【０００３】
非特許文献１及び２は、隣接関係を事前に共有しておくことで、あるノードが故障を発見すると、他のノードにすぐに通知される。図１に例を示す。ノードｉは、ノードｊ、ｋ、ｌと隣接関係、つまり、データの転送先であるとする。ノードｉはこの転送先ノードをＰｏｉｎｔｅｒとして管理する。同様にノードｊ、ｋ、ｌは、ノードｉをデータの転送先としているため、ノードｊ、ｋ、ｌはノードｉをＰｏｉｎｔｅｒとして管理している。なお、以降「ノードＡはノードＢをデータの転送先としている」ことを「ノードＡはノードＢを指している」と表現することがある。
【０００４】
また、ノードｉは、ノードｊ、ｋ、ｌからデータの転送先とされている（指されている）。このため、ノードｊ、ｋ、ｌはノードｉのＢａｃｋｐｏｉｎｔｅｒと呼ぶことにする。
【０００５】
ここで、ノードｊ、ｋ、ｌは、自分以外の隣接ノードを記憶しておく。たとえば、ノードｊは、ノードｋ、ｌがノードｉと隣接関係にあることを記憶、つまり、ノードｉのＢａｃｋｐｏｉｎｔｅｒを記憶している。もし、ノードｊがノードｉの故障を発見したら、ノードｋ、ｌがノードｉにｋｅｅｐ−ａｌｉｖｅを送るのを待つことなく、ノードｊからノードｋ、ｌに故障を通知する。
【０００６】
隣接ノードの情報を記憶し、隣接ノードの障害時に当情報を利用することで、故障を通知する方法以外に、各ノードが隣接ノードの故障間隔を予測し、予め、構造化オーバレイを冗長化する手法がある（例えば、非特許文献３、４及び５を参照。）。しかしながら、これらの手法は、予めノードの故障間隔の確率モデルを決めておかなければならず、どのようなオーバレイでも、適切に冗長化できるわけではない。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｓ．  Ｚｈｕａｎｇ，  Ｄ．  Ｇｅｅｌｓ，  Ｉ．  Ｓｔｏｉｃａ，  ａｎｄ  Ｒ．Ｈ．  Ｋａｔｚ，  “Ｏｎ  ｆａｉｌｕｒｅ  ｄｅｔｅｃｔｉｏｎ  ａｌｇｏｒｉｔｈｍｓ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔｗｏｒｋｓ”，  ｉｎ  Ｐｒｏｃ．  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＩＮＦＯＣＯＭ），  ｐｐ．２１１２−２１２３，  ２００５．
【非特許文献２】Ｉ．  Ｄｅｄｉｎｓｋｉ，  Ａ．  Ｈｏｆｍａｎｎ，  ａｎｄ  Ｂ．  Ｓｉｃｋ，  “Ｃｏｏｐｅｒａｔｉｖｅ  ｋｅｅｐ−ａｌｉｖｅｓ：  Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｏｕｔａｇｅ  ｄｅｔｅｃｔｉｏｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｐ２ｐ  ｏｖｅｒｌａｙ  ｎｅｔｗｏｒｋｓ”，  ｉｎ  Ｐｒｏｃ．  ＩＥＥＥ  ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｃｏｍｐｕｔｉｎｇ  （ＩＥＥＥ  Ｐ２Ｐ），  ｐｐ．１４０−１５０，  ２００７．
【非特許文献３】Ｇ．  Ｇｈｉｎｉｔａ  ａｎｄ  Ｙ．Ｍ．  Ｔｅｏ，  “Ａｎ  ａｄａｐｔｉｖｅ  ｓｔａｂｉｌｉｚａｔｉｏｎ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｈａｓｈ  ｔａｂｌｅｓ”，  ｉｎ  Ｐｒｏｃ．  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｍｐｏｓｉｕｍ（ＩＰＤＰＳ），  ｐｐ．１−１０，  Ａｐｒｉｌ  ２００６．
【非特許文献４】Ｒ．  Ｐｒｉｃｅ，  Ｐ．  Ｔｉｎｏ，  ａｎｄ  Ｇ．  Ｔｈｅｏｄｏｒｏｐｏｕｌｏｓ，  “Ｓｔｉｌｌ  ａｌｉｖｅ：  Ｅｘｔｅｎｄｉｎｇ  ｋｅｅｐ−ａｌｉｖｅ  ｉｎｔｅｒｖａｌｓ  ｉｎ  ｐ２ｐ  ｏｖｅｒｌａｙ  ｎｅｔｗｏｒｋｓ”，  Ｍｏｂ．  Ｎｅｔｗ．  Ａｐｐｌ．，  ｖｏｌ．１７，  ｎｏ．３，  ｐｐ．３７８−３９４，２０１２．
【非特許文献５】Ｋ．Ｃ．Ｗ．  Ｓｏ  ａｎｄ  Ｅ．Ｇ．  Ｓｉｒｅｒ，  “Ｌａｔｅｎｃｙ  ａｎｄ  ｂａｎｄｗｉｄｔｈ−ｍｉｎｉｍｉｚｉｎｇ  ｆａｉｌｕｒｅ  ｄｅｔｅｃｔｏｒｓ”，  ＳＩＧＯＰＳ  Ｏｐｅｒａｔｉｏｎ  Ｓｙｓｔｅｍ  Ｒｅｖｉｅｗ，  ｖｏｌ．４１，  ｎｏ．３，  ｐｐ．８９−９９，  ２００７．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１では、ノードが離脱してから新たな隣接関係を設定するまでの時間、ネットワークの構造が部分的に崩れており、ルーティングの効率が落ちてしまう。一般の構造化オーバレイは、各ノードが別々にノード故障を発見するため、最も遅いノードが故障を発見するまでの時間は、ｋｅｅｐ−ａｌｉｖｅ送信間隔Ｉにほぼ等しくなる。
【０００９】
非特許文献１は、いずれかのノードが故障を発見すれば他のノードに共有されるため、すべての隣接ノードが発見するまでの時間を大幅に短縮できる。全ノード数をＮとすると、隣接ノード数は約ｌｏｇＮであり、故障発見までの時間をＩ／ｌｏｇＮ程度に短縮できる。しかし、各ノードは、隣接ノードごとに隣接ノード一覧を管理しなければならない。つまり、非特許文献１では、ｐｏｉｎｔｅｒごとにｂａｃｋｐｏｉｎｔｅｒ一覧を管理しなければならず、隣接ノード数はｌｏｇＮであるため、管理するノード数がｌｏｇ２Ｎと多くなるという課題があった。
【００１０】
そこで、本発明は、前記課題を解決するために、故障発見までの時間を非特許文献１程度に保ちつつ、ノードを管理するメモリ量を低減できる通信管理方法及びノードを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明に係る通信管理方法及びノードは、故障ノードの次のＩＤを持つノードに故障ノードの代替をさせることとした。
【００１２】
具体的には、本発明に係る通信管理方法は、複数のノードからなる物理ネットワーク上に形成される構造化オーバレイネットワークを管理する通信管理方法であって、
前記ノードのそれぞれに、
自身のデータ転送先である前記ノードのＩＤをＰｏｉｎｔｅｒとして記憶させ、
自身をデータ転送先とする前記ノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶させ、
自身よりＩＤが小さい前記ノードのうち最大のＩＤを持つ前記ノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶させる記憶手順と、
任意の前記ノードが故障した時に、
故障した前記ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用いて構造化オーバレイネットワークを再構築する再構築手順と、
を備える。
【００１３】
また、本発明に係るノードは、構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶し、
自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
前記直前ノードが故障した時に、前記記憶部が記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用い、前記直前ノードを兼務するように構造化オーバレイネットワークを再構築する制御部と、
を備える。
【００１４】
各ノードがＩＤにおいて直前のノードのＢａｃｋｐｏｉｎｔｅｒと同じ情報を保持しており、あるノードが故障した時に、ＩＤにおいて直後のノードが当該情報を用いて隣接関係を再設定する。このため、本発明では、ノードの故障発見までの時間は非特許文献１と同等でありながら、管理するノード数を３ｌｏｇＮとすることができる。
【００１５】
従って、本発明は、故障発見までの時間を非特許文献１程度に保ちつつ、ノードを管理するメモリ量を低減できる通信管理方法及びノードを提供することができる。
【００１６】
具体的には、本発明に係る通信管理方法及びノードは、故障ノードを発見した時は次のように動作する。
【００１７】
本発明に係る通信管理方法の前記再構築手順では、
故障した前記ノードを転送先としていた前記ノードに対して、前記Ｐｏｉｎｔｅｒから故障した前記ノードを除去させ、
故障した前記ノードの直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードにコピーさせ、
故障した前記ノードを転送先としていた全ての前記ノードに対して、前記Ｐｏｉｎｔｅｒに前記直後ノードを追加させる
ことを特徴とする。
【００１８】
本発明に係るノードの前記制御部は、
故障した前記直前ノードを転送先としていた前記ノードに対して、前記Ｐｏｉｎｔｅｒから故障した前記直前ノードを除去させ、
前記直前Ｂａｃｋｐｏｉｎｔｅｒを、自身よりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードにコピーさせ、
故障した前記直前ノードを転送先としていた前記ノードに対して、自身のＩＤをＰｏｉｎｔｅｒとして追加させる
ことを特徴とする。
【００１９】
また、本発明に係る通信管理方法及びノードは、ＩＤが連続する２つのノードが故障した時は次のように動作する。
【００２０】
本発明に係る通信管理方法は、前記直後ノードも故障している場合、
故障した前記ノードを転送先としていた前記ノードに対して、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードを検索させ、
前記次ノードに対して、故障した前記ノードのＩＤと故障した前記ノードを転送先としていた前記ノードのＩＤとの差分を用いて、故障した前記ノードを転送先としていた前記ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記ノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定させ、
推定した前記Ｂａｃｋｐｏｉｎｔｅｒの全ての前記ノードに、故障した前記ノードの代替が前記次ノードであることを通知させる推定通知手順
を備える。
【００２１】
本発明に係るノード（故障発見ノード）は、構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
前記Ｐｏｉｎｔｅｒの前記他のノード、及び前記他のノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである直後ノードの双方が故障している場合、
前記直後ノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである次ノードを検索し、
前記次ノードに、故障した前記他のノードのＩＤと自身のＩＤの差分を用いて、自身が記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記他のノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定させる制御部と、
を備える。
【００２２】
本発明に係るノード（連続故障ノードの次のノード）は、構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
他のノードから、
自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノード、及び前記直前ノードよりＩＤが小さいノードのうち最大のＩＤを持つノードである従前ノードの双方が故障していることを通知されたときに、
前記従前ノードのＩＤと前記他のノードのＩＤの差分を用いて、前記他のノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記従前ノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定する制御部と、
を備える。
【発明の効果】
【００２３】
本発明は、故障発見までの時間を非特許文献１程度に保ちつつ、ノードを管理するメモリ量を低減できる通信管理方法及びノードを提供することができる。
【図面の簡単な説明】
【００２４】
【図１】従来の構造化オーバレイネットワークを説明する概念図である。
【図２】本発明に係る通信管理方法における構造化オーバレイネットワークを説明する概念図である。
【図３】本発明に係るノードを説明する図である。
【図４】本発明に係る通信管理方法を説明する図である。
【図５】本発明に係る通信管理方法を説明する図である。
【図６】本発明に係る通信管理方法を説明する図である。
【図７】本発明に係る通信管理方法を説明する図である。
【図８】本発明に係る通信管理方法を説明する図である。
【発明を実施するための形態】
【００２５】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２６】
本実施形態の通信管理方法は、複数のノードからなる物理ネットワーク上に形成される構造化オーバレイネットワークを管理する通信管理方法であって、
前記ノードのそれぞれに、
自身のデータ転送先である前記ノードのＩＤをＰｏｉｎｔｅｒとして記憶させ、
自身をデータ転送先とする前記ノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶させ、
自身よりＩＤが小さい前記ノードのうち最大のＩＤを持つ前記ノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶させる記憶手順と、
任意の前記ノードが故障した時に、
故障した前記ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用いて構造化オーバレイネットワークを再構築する再構築手順と、
を備える。
【００２７】
当該通信管理方法を実現するノードは、構造化オーバレイネットワークが形成される物理ネットワークのノードであって、
自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、
自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶し、
自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶する記憶部と、
前記直前ノードが故障した時に、前記記憶部が記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを用い、前記直前ノードを兼務するように構造化オーバレイネットワークを再構築する制御部と、
を備える。
【００２８】
図３は、本実施形態のノード１０を説明する図である。ノード１０は、経路制御モジュール１１、経路情報データベース（ＤＢ）１２、および該ＤＢを管理する維持管理モジュール１３を備える。経路制御モジュール１１は、一般的な構造化オーバレイが持つべきルーティングのモジュールであり、ネットワーク上からコンテンツ等を探索する機能を持つ。なお、経路制御モジュール１１は、前記制御部である。
【００２９】
経路情報ＤＢ１２は、前記記憶部であり、自身のデータ転送先である他のノードのＩＤをＰｏｉｎｔｅｒとして記憶し、自身をデータ転送先とする他のノードのＩＤをＢａｃｋｐｏｉｎｔｅｒとして記憶し、自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノードが記憶するＢａｃｋｐｏｉｎｔｅｒを直前Ｂａｃｋｐｏｉｎｔｅｒとして記憶する。
【００３０】
各ノードにはＩＤが割り当てられる。ノードｉよりＩＤが大きいノードのうち最小のノードを直後ノードｓｉ（ノードｉのｓｕｃｃｅｓｓｏｒ）とする。また、ノードｉよりＩＤが小さいノードのうち最大のノードを直前ノードｐｉ（ノードｉのｐｒｅｄｅｃｅｓｓｏｒ）とする。ノードｉが管理するｐｏｉｎｔｅｒの集合をＰｉとする。また、ノードｉを指しているノードの集合をｂａｃｋｐｏｉｎｔｅｒ集合と呼び、Ｂｉとする。さらに、ノードｉ以外のノード（たとえばｊ）が管理しているＢｉをＢｉｊのように記す。なお、ＢｉとＢｉｊの内容は同じである。
【００３１】
ノードｉは、Ｐｉ、Ｂｉ、Ｂｐｉｊを経路情報ＤＢ１２に保存している。同様に、直後ノードｓｉも、Ｐｓｉ、Ｂｓｉ、Ｂｉｓｉを経路情報ＤＢ１２に保存している。図２では直後ノードｓｉが保存するＢｓｉの記載を省略している。なお、経路情報ＤＢ１２は、ノードのＩＤの他に、通信に必要なＩＰアドレス情報も保管していてもよい。また、図２及び図３には記載されていないが、経路情報ＤＢ１２は、Ｐｏｉｎｔｅｒ集合に含まれるノードの直後ノード（ｓｕｃｃｅｓｓｏｒ）のＩＰアドレス（ｓｉ∀ｉ∈Ｐｉのアドレス）も管理しておく。
【００３２】
なお、図１の既存手法では、ノードｉのＢａｃｋｐｏｉｎｔｅｒ集合に含まれるノード同士で互いのノード情報（ＩＤやＩＰアドレス）を管理している。
【００３３】
維持管理モジュール１３は、以下のようにノード間におけるメッセージの全てのやり取りを行う。
【００３４】
図４及び図５は、ノードｉが管理するＢａｃｋｐｏｉｎｔｅｒ、直後ノードｓｉが管理するノードｉのＢａｃｋｐｏｉｎｔｅｒ、及びノードｊが管理するＰｏｉｎｔｅｒの更新を説明するシーケンス図である。
［図４の説明］
ノードｊは、Ｐｊに含まれる各ノード（ｉ）に対し、定期的にｋｅｅｐ−ａｌｉｖｅを送信する（ステップａ）。ノードｉは、ｋｅｅｐ−ａｌｉｖｅを受信すると、Ｂｉにｊが含まれているかを確かめる。含まれていなければＢｉにｊを追加し（ステップｂ）、直後ノードｓｉが管理するＢｉｓｉにも追加させる（ステップｃ）。ノードｉがｊに応答すると（ステップｄ）、ノードｊはＰｊにｉを追加する。なお、すでにＰｊにｉが含まれていればそのままとする。
［図５の説明］
ノードｉは定期的にＢｉに含まれるノード群（例えばノードｊ）にテスト信号を送信する（ステップａ）。もし、ノードｊが管理するＰｊにｉが含まれていなければ、ノードＪはその旨をノードｉに通知する、あるいは応答しない（ステップｂ）。ノードｉは、各ノードからの返答状況に応じてＢｉを更新する（ステップｃ）。図５ではノードｊからＰｊにｉが含まれていないことを通知されたのでＢｉからｊを削除している。その後、ノードｉは、直後ノードｓｉに対し、Ｂｉｓｉを更新させる（ステップｄ）。図５では、Ｂｉｓｉからｊを削除している。
【００３５】
各ノードが図４及び図５のように動作することで、ノードｊがｉを指しているときは必ずＢｉ及びＢｉｓｉにｊが含まれるようにし、ノードｊがｉを指さなくなったときは必ずＢｉ及びＢｉｓｉからｊを削除するようにする。ノードｉが故障したときに隣接関係を再設定するノードはノードｉを指していたノード、Ｂｉだけなので、直後ノードｓｉが管理するＢｉｓｉに含まれるノードに故障を通知すれば十分ということなる。
【００３６】
なお、直後ノードｓｉが故障している場合、ノードｉは直後ノードｓｉよりＩＤが大きい前記ノードのうち最小のＩＤを持つ次ノードｓｓｉを検索し、次ノードｓｓｉにＢｉを管理させるものとする（図６参照。）。
【００３７】
図７は、ノードｉが故障したときのシーケンス図である。
構造化オーバレイネットワークを再構築する再構築手順では、故障した前記ノードを転送先としていた前記ノードに対して、前記Ｐｏｉｎｔｅｒから故障した前記ノードを除去させ、
故障した前記ノードの直後ノードが記憶する前記直前Ｂａｃｋｐｏｉｎｔｅｒを、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードにコピーさせ、
故障した前記ノードを転送先としていた全ての前記ノードに対して、前記Ｐｏｉｎｔｅｒに前記直後ノードを追加させる。
【００３８】
直後ノードｓｉの前記制御部は、
故障した直前ノード（ノードｉ）を転送先としていたノードに対して、前記Ｐｏｉｎｔｅｒから故障した直前ノード（ノードｉ）を除去させ、
直前Ｂａｃｋｐｏｉｎｔｅｒ（Ｂｉｓｉ）を、自身よりＩＤが大きいノードのうち最小のＩＤを持つノードである次ノードｓｓｉにコピーさせ、
故障した直前ノード（ノードｉ）を転送先としていた前記ノードに対して、自身のＩＤをＰｏｉｎｔｅｒとして追加させる。
【００３９】
［図７の説明］
ノードｊがｉの故障を発見すると、まずノードｊはＰｊからｉを除去する（ステップａ）。そして、ノードｊはＢｉｓｉを管理している直後ノードｓｉにノードｉの故障を通知する（ステップｂ）。構造化オーバレイネットワークの特性により、ノードｉが故障するとノードｉを指していたノード（Ｂｉに含まれるノード）は、代替として直後ノードｓｉを指すことになる。そこで直後ノードｓｉは、自身のｓｕｃｃｅｓｓｏｒである次ノードｓｓｉにＢｉｓｉをコピーする（ステップｃ）。続いて、直後ノードｓｉは、Ｂｉ（＝Ｂｉｓｉ）に含まれるノードに、ノードｉの代替として自身（直後ノードｓｉ）を指すように指示する（ステップｄ）。
なお、ステップｄでは、ノードｊ以外のノードには、ノードｉをＰｏｉｎｔｅｒの集合から削除するように指示する。
【００４０】
図５のようにノードが動作することで、ノードが自身のｂａｃｋｐｏｉｎｔｅｒとｐｒｅｄｅｃｅｓｓｏｒのｂａｃｋｐｏｉｎｔｅｒしか管理していないにもかかわらず、あるノード（図５ではノードｊ）が故障を発見すると、すぐにその情報は全てのノード間で共有される。
【００４１】
図５の情報共有手法は、ｓｕｃｃｅｓｓｏｒを利用して故障情報を全てのノード間で共有する。しかし、ｓｕｃｃｅｓｓｏｒも故障していると（つまり、図５であればノードｉとノードｓｉが同時に故障すると）、Ｂｉを知るノードが不在となるため、故障情報を他のノードに通知できず故障情報を共有できなくなる。
【００４２】
そこで、本実施形態の通信管理方法は、前記直後ノードも故障している場合、
故障した前記ノードを転送先としていた前記ノードに対して、前記直後ノードよりＩＤが大きい前記ノードのうち最小のＩＤを持つ前記ノードである次ノードを検索させ、
前記次ノードに対して、故障した前記ノードのＩＤと故障した前記ノードを転送先としていた前記ノードのＩＤとの差分を用いて、故障した前記ノードを転送先としていた前記ノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒから故障した前記ノードの前記Ｂａｃｋｐｏｉｎｔｅｒを推定させ、
推定した前記Ｂａｃｋｐｏｉｎｔｅｒの全ての前記ノードに、故障した前記ノードの代替が前記次ノードであることを通知させる推定通知手順を備える。
【００４３】
［図８の説明］
このような場合、多くの構造化オーバレイネットワークでは、異なるノードのｂａｃｋｐｏｉｎｔｅｒ同士がそれらのノードのＩＤのズレを補正すれば近似するという特徴を利用する。図１であれば、ＩＤ間隔の分だけリングを回せば（ＰｏｉｎｔｅｒやＢａｃｋｐｏｉｎｔｅｒのＩＤを補正すれば）、リングを回す前の状態と大雑把に似たような状態になる。たとえば、ノードｉ、ｊを考えたとき、｜ｉ−ｊ｜だけＰｏｉｎｔｅｒやＢａｃｋｐｏｉｎｔｅｒのＩＤを補正すれば、ＢｊをＢｉの代替として利用することが可能と考えられる。推定するノードｉのｂａｃｋｐｏｉｎｔｅｒをＢｉ’とすると、ノードｊはＢｊを用いて以下のようにＢｉ’を推定する。
＜推定式＞
Ｂｉ’＝ｋ−｜ｉ−ｊ｜：ｋ∈Ｂｊ
【００４４】
図８は、ｓｕｃｃｅｓｓｏｒが故障している場合のシーケンス図である。ステップａは図７の説明と同じである。ノードｊはノードｉの他にノードｓｉも故障していることを発見する（ステップｂ）と、そのｓｕｃｃｅｓｓｏｒであるノードｓｓｉに故障を通知する（ステップｃ）。ステップｃでは、ノードｊは経路制御モジュール１１を利用して構造化オーバレイのルーティングを用いてノードｓｓｉを探索する。ノードｊは、ノードｓｓｉを発見後、該ノードへのメッセージ送信を行う。ノードｓｓｉは上記推定式を用いてＢｉ’を得て、Ｂｉ’に含まれるノードにｉの故障を通知する。ノードｉとノードｓｉが故障しているときは、ノードｓｓｉがノードｉの代替となる。このため、ノードｉを指していたノードｋは、ノードｓｓｉを指すためにノードｓｓｉにｋｅｅｐ−ａｌｉｖｅを送信する（ステップｅ）。
【００４５】
つまり、ノードｊは、前記Ｐｏｉｎｔｅｒ（Ｐｊ）の他のノード（ノードｉ）、及び前記他のノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである直後ノード（ノードｓｉ）の双方が故障している場合、前記制御部が、前記直後ノードよりＩＤが大きいノードのうち最小のＩＤを持つノードである次ノード（ノードｓｓｉ）を検索し、前記次ノードに、故障した前記他のノードのＩＤと自身のＩＤの差分（｜ｊ−ｉ｜）を用いて、自身が記憶する前記Ｂａｃｋｐｏｉｎｔｅｒ（Ｂｊ）から故障した前記他のノードの前記Ｂａｃｋｐｏｉｎｔｅｒ（Ｂｉ）を推定させる。
【００４６】
一方、ノードｓｓｉは、他のノード（ノードｊ）から、自身よりＩＤが小さいノードのうち最大のＩＤを持つノードである直前ノード（ノードｓｉ）、及び前記直前ノードよりＩＤが小さいノードのうち最大のＩＤを持つノードである従前ノード（ノードｉ）の双方が故障していることを通知されたときに、制御部が、前記従前ノードのＩＤと前記他のノードのＩＤの差分（｜ｊ−ｉ｜）を用いて、前記他のノードが記憶する前記Ｂａｃｋｐｏｉｎｔｅｒ（Ｂｊ）から故障した前記従前ノードの前記Ｂａｃｋｐｏｉｎｔｅｒ（Ｂｉ）を推定する。
【００４７】
（発明によって生じる効果）
本発明は、統一的な論理空間にノードやデータを対応付け、ノードの隣接関係を構造的に管理し、効率的なルーティングを実現する構造化オーバレイネットワークにおいて、ノードの故障発見時に通知するノードをｓｕｃｃｅｓｓｏｒだけに管理させることで、非特許文献１及び２の手法とほぼ同じ故障発見時間を、３ｌｏｇＮのノードを管理するだけで実現する。このため、本発明はノードにおいて他のノードを管理する必要メモリを削減することができる。また、本発明は、ｓｕｃｃｅｓｓｏｒも故障したときに、通知すべきノードを推定する手段を有する。
【符号の説明】
【００４８】
１０：ノード
１１：経路制御モジュール
１２：経路情報データベース
１３：維持管理モジュール
【図１】
2016052030.tif 000003
【図２】
2016052030.tif 000004
【図３】
2016052030.tif 000005
【図４】
2016052030.tif 000006
【図５】
2016052030.tif 000007
【図６】
2016052030.tif 000008
【図７】
2016052030.tif 000009
【図８】
2016052030.tif 000010