(57)【要約】【課題】  本発明は、新規参加ノードが所定アルゴリズムによってネットワークに参加することによって、新規参加ノードがネットワークにおける各ノード間の位置関係を即座に把握することができ、かつ、当該ネットワーク内におけるノードの故障や離脱等の発生が、当該ネットワークの局所的な部分にしか影響を及ぼさないネットワークトポロジー構成方法を構成するノードを提供する。【解決手段】  本発明に係るノード１０１は、自ノード１０１のハッシュ値「Ｎｉ」及び隣接ノード１０２、１０３のハッシュ値「Ｎｉ＋１」「Ｎｉ−１」を管理する管理部１００ａと、新規参加ノード１０５のハッシュ値「Ｎ」と自ノード１０１のハッシュ値Ｎｉ」と隣接ノード１０２、１０３のハッシュ値「Ｎｉ＋１」「Ｎｉ−１」とに基づいて、リング型ネットワークにおける新規参加ノード１０５の挿入位置を算出する算出部とを具備する。【選択図】  図４
2005198201.tif 000002
【特許請求の範囲】
【請求項１】
リング型ネットワークを構成するノードであって、
自ノードの識別情報から生成される該自ノードのハッシュ値及び隣接ノードの識別情報から生成される該隣接ノードのハッシュ値を管理する管理部と、
前記リング型ネットワークに新規に参加する新規参加ノードの識別情報から生成される該新規参加ノードのハッシュ値と前記自ノードのハッシュ値と前記隣接ノードのハッシュ値とに基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出する算出部とを具備することを特徴とするノード。
【請求項２】
前記新規参加ノードから該新規参加ノードのハッシュ値を取得する取得部と、
前記リング型ネットワークにおける前記新規参加ノードの挿入位置を該新規参加ノードに対して通知する通知部とを具備することを特徴とする請求項１に記載のノード。
【請求項３】
前記算出部は、前記新規参加ノードのハッシュ値と前記自ノードのハッシュ値と前記隣接ノードのハッシュ値とを比較して、前記リング型ネットワークにおいて各ノードがハッシュ値の順に並ぶように該新規参加ノードの挿入位置を算出することを特徴とする請求項１に記載のノード。
【請求項４】
前記管理部は、前記リング型ネットワークを構成する全てのノードの識別情報から生成される該全てのノードのハッシュ値を管理しており、
前記算出部は、前記新規参加ノードのハッシュ値と前記全てのノードのハッシュ値とに基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出することを特徴とする請求項１に記載のノード。
【請求項５】
前記通知部は、前記新規参加ノードの挿入位置を通知するノードを、前記新規参加ノード及び前記隣接ノードに限定することを特徴とする請求項２に記載のノード。
【請求項６】
複数のノードによって構成されているリング型ネットワークに新規に参加するノードであって、
前記リング型ネットワークを構成する任意のノードに対して、自ノードの識別情報から生成される該自ノードのハッシュ値を送信する送信部と、
前記任意のノードから通知された前記リング型ネットワークにおける自ノードの挿入位置に基づいて、該当するノードとの間で接続を確立する接続確立部とを具備することを特徴とするノード。
【請求項７】
複数のノードによって構成されているリング型ネットワークにおけるネットワークトポロジー構成方法であって、
前記リング型ネットワークに新規に参加する新規参加ノードの識別情報から生成される該新規参加ノードのハッシュ値と、該前記リング型ネットワークを構成するノードの識別情報から生成される該ノードのハッシュ値と基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出することを特徴とするネットワークトポロジー構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードによって構成されるリング型ネットワークに新規参加ノードが参加する際のネットワークトポロジー構成方法に関する。また、本発明は、複数のノードによって構成されるリング型ネットワークを構成するノード及び当該リング型ネットワークに新規に参加するノードに関する。
【背景技術】
【０００２】
図１３乃至図１７を参照して、従来のネットワークトポロジー構成方法（Ｇｎｕｔｅｌｌａで使用されている方法）について説明する。具体的には、ノード１０５が、ノード１０１乃至１０４を含むネットワークに新規に参加する動作について説明する。
【０００３】
第１に、図１３に示すように、ノード１０５は、ネットワークを構成する複数のノード１０１乃至１０４の中から、ＩＰアドレス又はＵＲＬ（Ｕｎｉｖｅｒｓａｌ  Ｒｅｓｏｕｒｃｅ  Ｌａｎｇｕａｇｅ）を知っているノード１０１との間でコネクションを確立する。
【０００４】
第２に、図１４に示すように、ノード１０５は、ノード１０１に対して、ノード１０５のＩＰアドレスを含むＰｉｎｇメッセージを、ブロードキャストによって送信する。
【０００５】
第３に、図１５に示すように、ノード１０１は、ノード１０１のＩＰアドレスを含むＰｏｎｇメッセージをノード１０５に返信するとともに、ノード１０５のＩＰアドレスを含むＰｉｎｇメッセージをノード１０２乃至１０４に転送する。
【０００６】
第４に、図１６に示すように、各ノード１０２乃至１０４は、それぞれのＩＰアドレスを含むＰｏｎｇメッセージをノード１０５に返信する。
【０００７】
以上の手順が繰り返されることによって、ノード１０５は、ＰｉｎｇメッセージのＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールドに指定された範囲内のノードのＩＰアドレスを取得することができる。
【０００８】
第５に、図１７に示すように、ノード１０５は、受信したＰｏｎｇメッセージに含まれるＩＰアドレスを参照して、ネットワークを構成するノード１０１乃至１０４の各々とコネクションを確立する。
【０００９】
このようにして、ノード１０５は、ノード１０１乃至１０４によって構成されているネットワークに新規に参加することができる。
【特許文献１】特開２００３-２８９３０２号公報
【特許文献２】特開平１０-６５６６４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述のように、従来のネットワークトポロジー構成方法では、新規参加ノード１０５は、Ｐｉｎｇメッセージ及びＰｏｎｇメッセージを利用して、ランダム的にネットワークに参加するように構成されていた。
【００１１】
しかしながら、従来のネットワークトポロジー構成方法では、新規参加ノード１０５が、参加したネットワークにおける各ノード間の位置関係を即座に把握することが困難であり、また、当該ネットワークを構成する各ノードについてのネットワークトポロジー構成情報を入手するのに時間がかかるという問題点があった。
【００１２】
また、従来のネットワークトポロジー構成方法では、ネットワークを構成するノード間の多数のリンクが存在するため、ノードの故障やノードの当該ネットワークからの離脱等が発生した場合に、隣接ノード間で上述のリンクに係る情報を含むネットワークトポロジー構成情報の更新のためのメッセージ交換が多数行われることによって、ネットワーク負荷が増大し、各ノードにおけるネットワークトポロジー構成情報の更新に時間がかかるという問題点があった。
【００１３】
そこで、本発明は、以上の点に鑑みてなされたもので、新規参加ノードが所定アルゴリズムによってネットワークに参加することによって、新規参加ノードがネットワークにおける各ノード間の位置関係を即座に把握することができ、かつ、当該ネットワーク内におけるノードの故障や離脱等の発生が、当該ネットワークの局所的な部分にしか影響を及ぼさないネットワークトポロジー構成方法及びノードを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の第１の特徴は、リング型ネットワークを構成するノードであって、自ノードの識別情報から生成される該自ノードのハッシュ値及び隣接ノードの識別情報から生成される該隣接ノードのハッシュ値を管理する管理部と、前記リング型ネットワークに新規に参加する新規参加ノードの識別情報から生成される該新規参加ノードのハッシュ値と前記自ノードのハッシュ値と前記隣接ノードのハッシュ値とに基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出する算出部とを具備することを要旨とする。
【００１５】
本発明の第１の特徴において、前記新規参加ノードから該新規参加ノードのハッシュ値を取得する取得部と、前記リング型ネットワークにおける前記新規参加ノードの挿入位置を該新規参加ノードに対して通知する通知部とを更に具備するように構成されていてもよい。
【００１６】
本発明の第１の特徴において、前記算出部が、前記新規参加ノードのハッシュ値と前記自ノードのハッシュ値と前記隣接ノードのハッシュ値とを比較して、前記リング型ネットワークにおいて各ノードがハッシュ値の順に並ぶように該新規参加ノードの挿入位置を算出してもよい。
【００１７】
かかる発明によれば、リング型ネットワークにおいて各ノードがハッシュ値の順に並ぶようにネットワークトポロジーが構成されるため、新規参加ノードであってもネットワークにおける各ノード間の位置関係を即座に把握することができる。
【００１８】
また、かかる発明によれば、リング型ネットワークを構成する各ノードは、隣接ノードに係る情報だけを管理していればよいので、当該ネットワークを構成する各ノードについてのネットワークトポロジー構成情報を入手するのに時間がかかるという問題点を解決することができる。
【００１９】
本発明の第１の特徴において、前記管理部が、前記リング型ネットワークを構成する全てのノードの識別情報から生成される該全てのノードのハッシュ値を管理しており、前記算出部が、前記新規参加ノードのハッシュ値と前記全てのノードのハッシュ値とに基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出してもよい。
【００２０】
本発明の第１の特徴において、前記通知部が、前記新規参加ノードの挿入位置を通知するノードを、前記新規参加ノード及び前記隣接ノードに限定してもよい。
【００２１】
かかる発明によれば、ノードの故障やノードの当該ネットワークからの離脱等が発生した場合であっても、隣接ノード間で上述のリンクに係る情報を含むネットワークトポロジー構成情報の更新のためのメッセージ交換が多数行う必要が無く、ネットワーク負荷を軽減し、各ノードにおけるネットワークトポロジー構成情報の更新に時間がかかるという問題点を解決することができる。
【００２２】
本発明の第２の特徴は、複数のノードによって構成されているリング型ネットワークに新規に参加するノードであって、前記リング型ネットワークを構成する任意のノードに対して、自ノードの識別情報から生成される該自ノードのハッシュ値を送信する送信部と、前記任意のノードから通知された前記リング型ネットワークにおける自ノードの挿入位置に基づいて、該当するノードとの間で接続を確立する接続確立部とを具備することを要旨とする。
【００２３】
本発明の第３の特徴は、複数のノードによって構成されているリング型ネットワークにおけるネットワークトポロジー構成方法であって、前記リング型ネットワークに新規に参加する新規参加ノードの識別情報から生成される該新規参加ノードのハッシュ値と、該前記リング型ネットワークを構成するノードの識別情報から生成される該ノードのハッシュ値と基づいて、該リング型ネットワークにおける該新規参加ノードの挿入位置を算出することを要旨とする。
【発明の効果】
【００２４】
以上説明したように、本発明によれば、新規参加ノードが所定アルゴリズムによってネットワークに参加することによって、新規参加ノードがネットワークにおける各ノード間の位置関係を即座に把握することができ、かつ、当該ネットワーク内におけるノードの故障や離脱等の発生が、当該ネットワークの局所的な部分にしか影響を及ぼさないネットワークトポロジー構成方法及びノードを提供することができる。
【発明を実施するための最良の形態】
【００２５】
＜本発明の第１の実施形態＞
以下、図１乃至図１０を参照して、本発明の第１の実施形態について説明する。本実施形態では、図１に示すように、新規参加ノード１０５が、複数のノード１０１乃至１０３等によって構成されているリング型ネットワークに新規に参加する例について説明する。なお、本実施形態では、図２に示すように、新規参加ノード１０５は、当該リング型ネットワークにおいて、ノード１０１とノード１０２との間に挿入されるものとする。
【００２６】
また、本実施形態では、図１及び図２に示すように、ノード１０１のハッシュ値は「Ｎｉ」であり、ノード１０２のハッシュ値は「Ｎｉ＋１」であり、ノード１０３のハッシュ値は「Ｎｉ−１」であり、ノード１０５のハッシュ値は「Ｎ」である。なお、ノード１０１、１０２、１０３、１０５のハッシュ値は、それぞれ、ノード１０１、１０２、１０３、１０５の識別情報（例えば、ＵＵＩＤ（Ｕｎｉｖｅｒｓａｌ  Ｕｎｉｑｕｅ  Ｉｄｅｎｔｉｆｉｅｒ）等）から生成されるものとする。
【００２７】
第１に、図３を参照して、新規参加ノード１０５の機能について説明する。図３に示すように、新規参加ノード１０５は、分散ハッシュテーブル（ＤＨＴ：Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ）１００ａと、ネットワーク加入処理部１００ｂと、ネットワークトポロジー構成情報送受信部１００ｃとを具備している。
【００２８】
分散ハッシュテーブル１００ａは、自ノード１０５の識別情報から生成される自ノード１０５のハッシュ値「Ｎ」及び隣接ノードの識別情報から生成される該隣接ノードのハッシュ値を管理するものである。
【００２９】
具体的には、分散ハッシュテーブル１００ａは、図３に示すように、「ノード位置」と「ハッシュ値」と「ノードアドレス」とを関連付けるレコードを記憶するものである。
【００３０】
「ノード位置」は、各ノードの位置を示すものである。すなわち、「ノード位置＝自分」は、自ノード１０５の位置を示すものであり、「ノード位置＝前」は、自ノード１０５の直前の位置を示すものであり、「ノード位置＝後」は、自ノード１０５の直後の位置を示すものである。
【００３１】
ここで、リング型ネットワークでは、各ノードがハッシュ値の順に並ぶように構成されている。したがって、例えば、自ノードの直前の位置に配置されたノードは、自ノードのハッシュ値より小さいハッシュ値を有し、自ノードの直後の位置に配置されたノードは、自ノードのハッシュ値より大きいハッシュ値を有している場合が多い（例外は、最小のハッシュ値や最大のハッシュ値を有するノードの場合である）。なお、リング型ネットワークにおいて、自ノードの直前の位置に配置されたノードが、自ノードのハッシュ値より大きいハッシュ値を有し、自ノードの直後の位置に配置されたノードが、自ノードのハッシュ値より小さいハッシュ値を有しているように並べられていてもよい。
【００３２】
「ハッシュ値」は、各「ノード位置」に配置されたノードのハッシュ値を示すものである。また、「ノードアドレス」は、各「ノード位置」に配置されたノードのノードアドレス（例えば、ＩＰアドレスやＵＲＬ）を示すものである。
【００３３】
図３の例では、新規参加ノード１０５が、リング型ネットワークに未だ参加していないため、全ての「ノード位置」に対応する「ハッシュ値」及び「ノードアドレス」が、自ノード１０５のもの（「ハッシュ値＝Ｎ」及び「ノードアドレス＝ＡＤＤＲＥＳＳ-Ｎ」）となっている。
【００３４】
ネットワーク加入処理部１００ｂは、リング型ネットワークに新規に参加するにあたって必要な処理を行うものである。
【００３５】
具体的には、ネットワーク加入処理部１００ｂは、リング型ネットワークに新規に参加する際に、分散ハッシュテーブル１００ａから、自ノード１０５のハッシュ値及びノードアドレスを抽出して、当該自ノード１０５のハッシュ値及びノードアドレスを含むネットワークトポロジー構成情報を生成する。
【００３６】
また、ネットワーク加入処理部１００ｂは、生成したネットワークトポロジー構成情報を、ノードアドレスを知っている任意のノード（例えば、ノード１０１）に対して送信するように、ネットワークトポロジー構成情報送受信部１００ｃに指示する。
【００３７】
また、ネットワーク加入処理部１００ｂは、ネットワークトポロジー構成情報を送信した任意のノード（例えば、ノード１０１）から通知されたリング型ネットワークにおける自ノード１０５の挿入位置に基づいて、該当するノード（例えば、ノード１０１及びノード１０２）との間で接続を確立すると共に、当該自ノード１０５の挿入位置に基づいて分散ハッシュテーブル１００ａを更新する。
【００３８】
ネットワークトポロジー構成情報送受信部１００ｃは、ネットワーク加入処理部１００ｂからの指示に応じて、任意のノード（例えば、ノード１０１）に対してネットワークトポロジー構成情報を送信する。
【００３９】
また、ネットワークトポロジー構成情報送受信部１００ｃは、任意のノード（例えば、ノード１０１）から通知されたリング型ネットワークにおける自ノード１０５の挿入位置を含むネットワークトポロジー構成情報を受信する。
【００４０】
なお、新規参加ノード１０５は、後述するノード１０１の機能（図４参照）を具備するように構成されていることが好ましい。
【００４１】
第２に、図４を参照して、リング型ネットワークを構成するノードの機能について説明する。なお、ノード１０１乃至ノード１０３の機能は、基本的に同一であるため、以下、ノード１０１の機能について説明する。
【００４２】
図４に示すように、ノード１０１は、分散ハッシュテーブル１００ａと、新規参加ノード受け入れ部１００ｄと、ネットワークトポロジー構成情報送受信部１００ｃとを具備している。
【００４３】
分散ハッシュテーブル１００ａは、自ノード１０１の識別情報から生成される自ノード１０１のハッシュ値「Ｎｉ」及び隣接ノードの識別情報から生成される該隣接ノードのハッシュ値を管理するものである。
【００４４】
具体的には、分散ハッシュテーブル１００ａは、図４に示すように、「ノード位置」と「ハッシュ値」と「ノードアドレス」とを関連付けるレコードを記憶するものである。
【００４５】
図４の例は、新規参加ノード１０５が参加する前の状態の分散ハッシュテーブル１００ａを示しているため、分散ハッシュテーブル１００ａは、「ノード位置＝前」と「ハッシュ値＝Ｎｉ−１（ノード１０３のハッシュ値）」と「ノードアドレスＡＤＤＲＥＳＳ-Ｎｉ−１（ノード１０３のノードアドレス）」とを関連付けるレコード、「ノード位置＝自分」と「ハッシュ値＝Ｎｉ（ノード１０１のハッシュ値）」と「ノードアドレスＡＤＤＲＥＳＳ-Ｎｉ（ノード１０１のノードアドレス）」とを関連付けるレコード、及び、「ノード位置＝後」と「ハッシュ値＝Ｎｉ＋１（ノード１０２のハッシュ値）」と「ノードアドレスＡＤＤＲＥＳＳ-Ｎｉ＋１（ノード１０２のノードアドレス）」とを関連付けるレコードを管理している。
【００４６】
新規参加ノード受け入れ部１００ｄは、新規参加ノード１０５がリング型ネットワークに新規に参加するにあたって必要な処理を行うものである。
【００４７】
具体的には、新規参加ノード受け入れ部１００ｄは、リング型ネットワークに新規に参加する新規参加ノード１０５のハッシュ値「Ｎ」と自ノード１０１のハッシュ値「Ｎｉ」と隣接ノード１０２及び１０３のハッシュ値「Ｎｉ＋１」及び「Ｎｉ−１」とに基づいて、当該リング型ネットワークにおける当該新規参加ノード１０５の挿入位置を算出する。
【００４８】
ここで、新規参加ノード受け入れ部１００ｄは、新規参加ノード１０５のハッシュ値「Ｎ」と自ノード１０１のハッシュ値「Ｎｉ」と隣接ノード１０２及び１０３のハッシュ値「Ｎｉ＋１」及び「Ｎｉ−１」とを比較して、リング型ネットワークにおいて各ノードがハッシュ値の順に並ぶように新規参加ノード１０５の挿入位置を算出する。
【００４９】
図２の例では、ハッシュ値の大きさは、各ノード１０１、１０５、１０２、１０３のハッシュ値「Ｎｉ」、「Ｎ」、「Ｎｉ＋１」、「Ｎｉ−１」の順に大きくなっている。
【００５０】
なお、新規参加ノード受け入れ部１００ｄは、同じ大きさのハッシュ値を有するノードの配置について、任意の基準によって決定することができる。
【００５１】
また、新規参加ノード受け入れ部１００ｄは、ネットワークトポロジー構成情報送受信部１００ｃを介して、新規参加ノードのハッシュ値及びノードアドレスを取得するように構成されている。
【００５２】
また、新規参加ノード受け入れ部１００ｄは、リング型ネットワークにおける新規参加ノード１０５の挿入位置に基づいて、分散ハッシュテーブル１００ａを更新すると共に、当該新規参加ノード１０５の挿入位置を通知するためのネットワークトポロジー構成情報を生成して、新規参加ノード１０５及び隣接ノード１０２、１０３に送信するように、ネットワークトポロジー構成情報送受信部１００ｃに指示する。なお、かかるネットワークトポロジー構成情報は、新規参加ノード１０５の挿入位置を含むように構成されていてもよいし、新規参加ノード１０５の挿入が反映された分散ハッシュテーブル１００ａを含むように構成されていてもよい。
【００５３】
ネットワークトポロジー構成情報送受信部１００ｃは、新規参加ノード受け入れ部１００ｄからの指示に応じて、新規参加ノード１０５及び隣接ノード１０２、１０３に対してネットワークトポロジー構成情報を送信する。
【００５４】
また、ネットワークトポロジー構成情報送受信部１００ｃは、新規参加ノード１０５から通知された新規参加ノード１０５のハッシュ値及びノードアドレスを含むネットワークトポロジー構成情報を受信する。
【００５５】
図５乃至図９を参照して、本実施形態に係るネットワークトポロジー構成方法の動作について説明する。具体的には、図１及び図２に示すように、新規参加ノード１０５が、ノード１０１乃至１０３を含むリング型ネットワークに新規に参加する際の動作について説明する。
【００５６】
第１に、図５及び図６を参照して、かかる場合の新規参加ノード１０５の動作について説明する。
【００５７】
図５に示すように、ステップ１００１において、新規参加ノード１０５のネットワーク加入処理部１００ｂが、分散ハッシュテーブル１００ａから、自ノード１０５のハッシュ値「Ｎ」及びノードアドレス「ＡＤＤＲＥＳＳ-Ｎ」を抽出し、抽出したハッシュ値「Ｎ」及びノードアドレス「ＡＤＤＲＥＳＳ-Ｎ」を含むネットワークトポロジー構成情報を生成する。
【００５８】
ステップ１００２において、新規参加ノード１０５のネットワークトポロジー構成情報送受信部１００ｃが、ネットワーク加入処理部１００ｂからの指示に応じて、上述のネットワークトポロジー構成情報をノード１０１に送信する。
【００５９】
ステップ１００３において、ネットワークトポロジー構成情報送受信部１００ｃが、ノード１０１から、リング型ネットワークにおける新規参加ノード１０５の挿入位置（本実施形態では、ノード１０１とノード１０２との間）を含むネットワークトポロジー構成情報を受信する。
【００６０】
ステップ１００４において、ネットワーク加入処理部１００ｂが、受信したネットワークトポロジー構成情報に応じて、図６に示すように分散ハッシュテーブル１００ａを更新すると共に、該当するノード（ノード１０１及びノード１０２）との間で、新しい接続を確立する。
【００６１】
第２に、図７乃至図９を参照して、かかる場合のノード１０１の動作について説明する。
【００６２】
図７に示すように、ステップ２００１において、ノード１０１の新規参加ノード受け入れ部１００ｄが、ネットワークトポロジー構成情報送受信部１００ｃを介して、新規参加ノード１０５から、当該新規参加ノード１０５のハッシュ値及びノードアドレスを含むネットワークトポロジー構成情報を受信する。
【００６３】
ステップ２００２において、新規参加ノード受け入れ部１００ｄが、分散ハッシュテーブル１００ａから、自ノード１０１のハッシュ値及び隣接ノード１０２、１０３のハッシュ値を抽出する。
【００６４】
ステップ２００３において、新規参加ノード受け入れ部１００ｄが、受信した新規参加ノード１０５のハッシュ値、抽出した自ノード１０１及び隣接ノード１０２、１０３のハッシュ値に基づいて、リング型ネットワークにおける当該新規参加ノード１０５の挿入位置を算出する。
【００６５】
図８を参照して、ステップ２００３における新規参加ノード１０５の挿入位置を算出するアルゴリズムの一例について説明する。
【００６６】
ここで、ノード１０１の新規参加ノード受け入れ部１００ｄは、ノード１０１とノード１０２との間に新規参加ノード１０５の挿入位置が挿入されるべきであるかについて、又は、ノード１０１とノード１０３との間に新規参加ノード１０５の挿入位置が挿入されるべきであるかについて判定し、それ以外の場合、ノード１０５の挿入位置は不明であると判定するように構成されている。
【００６７】
なお、図８の例では、リング型ネットワークにおいて、各ノードのハッシュ値は、時計回り方向で大きくなっているものとする。
【００６８】
ステップＡにおいて、本アルゴリズムは、新規参加ノード１０５のハッシュ値「Ｎ」と自ノード１０１のハッシュ値「Ｎｉ」とを比較する。
【００６９】
新規参加ノード１０５のハッシュ値「Ｎ」が自ノード１０１のハッシュ値「Ｎｉ」より大きい場合、ステップＢにおいて、本アルゴリズムは、「最小のハッシュ値が＝Ｎｉ」、「最大のハッシュ値＝Ｎｉ−１」及び「Ｎ＞Ｎｉ−１」の３条件が満たされるか否かについて判定する。
【００７０】
ステップＢにおける３条件が満たされる場合、ステップＫにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０３との間であると決定する。
【００７１】
一方、ステップＢにおける３条件が満たされない場合、ステップＣにおいて、本アルゴリズムは、「最小のハッシュ値＝Ｎｉ＋１」、「最大のハッシュ値＝Ｎｉ」及び「Ｎ＞Ｎｉ」の３条件が満たされるか否かについて判定する。
【００７２】
ステップＣにおける３条件が満たされる場合、ステップＦにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０２との間であると決定する。
【００７３】
一方、ステップＣにおける３条件が満たされない場合、ステップＤにおいて、本アルゴリズムは、「Ｎｉ＜Ｎ＜Ｎｉ＋１」の条件が満たされるか否かについて判定する。
【００７４】
ステップＤにおける条件が満たされる場合、ステップＦにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０２との間であると決定する。
【００７５】
一方、ステップＤにおける条件が満たされない場合、ステップＥにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置が不明であると判定する。すなわち、本アルゴリズムは、新規参加ノード１０５の挿入位置が、ノード１０１とノード１０２との間、及び、ノード１０１とノード１０３との間ではないと判定する。
【００７６】
また、新規参加ノード１０５のハッシュ値「Ｎ」が自ノード１０１のハッシュ値「Ｎｉ」より大きくない場合、ステップＧにおいて、本アルゴリズムは、「最小のハッシュ値＝Ｎｉ＋１」、「最大のハッシュ値＝Ｎｉ」及び「Ｎ＜Ｎｉ＋１」の３条件が満たされるか否かについて判定する。
【００７７】
ステップＧにおける条件が満たされる場合、ステップＦにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０２との間であると決定する。
【００７８】
一方、ステップＧにおける３条件が満たされない場合、ステップＨにおいて、本アルゴリズムは、「最小のハッシュ値＝Ｎｉ」、「最大のハッシュ値＝Ｎｉ−１」及び「Ｎ＜Ｎｉ」の３条件が満たされるか否かについて判定する。
【００７９】
ステップＨにおける３条件が満たされる場合、ステップＫにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０３との間であると決定する。
【００８０】
一方、ステップＨにおける３条件が満たされない場合、ステップＩにおいて、本アルゴリズムは、「Ｎｉ−１＜Ｎ＜Ｎｉ」の条件が満たされるか否かについて判定する。
【００８１】
ステップＩにおける条件が満たされる場合、ステップＫにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置は、ノード１０１とノード１０３との間であると決定する。
【００８２】
一方、ステップＩにおける条件が満たされない場合、ステップＪにおいて、本アルゴリズムは、新規参加ノード１０５の挿入位置が不明であると判定する。すなわち、本アルゴリズムは、新規参加ノード１０５の挿入位置が、ノード１０１とノード１０２との間、及び、ノード１０１とノード１０３との間ではないと判定する。
【００８３】
なお、本発明は、リング型ネットワークにおいて、各ノードのハッシュ値が反時計回り方向で大きくなっている場合についても適用することができる。
【００８４】
ここで、図７のフローチャートに戻ると、ステップ２００４において、新規参加ノード受け入れ部１００ｄが、新規参加ノード１０５の挿入位置が決定されたか否かについて判定する。
【００８５】
新規参加ノード１０５の挿入位置が決定された場合、ステップ２００５において、新規参加ノード受け入れ部１００ｄが、決定された新規参加ノード１０５の挿入位置に基づいて、図９に示すように分散ハッシュテーブル１００ａを更新する。
【００８６】
ステップ２００６において、新規参加ノード受け入れ部１００ｄが、ネットワークトポロジー構成情報送受信部１００ｃを介して、更新後の分散ハッシュテーブル１００ａの内容を含むネットワークトポロジー構成情報を、新規参加ノード１０５及び隣接ノード１０２、１０３に送信する。
【００８７】
一方、新規参加ノード１０５の挿入位置が不明である場合、ステップ２００７において、新規参加ノード受け入れ部１００ｄが、ネットワークトポロジー構成情報送受信部１００ｃを介して、新規参加ノード１０５からのネットワークトポロジー構成情報を隣接ノード（ノード１０２又はノード１０３）に転送する。
【００８８】
かかるネットワークトポロジー構成情報を受信した隣接ノードは、ノード１０１と同様にステップ２００１乃至ステップ２００７の動作を行うことによって、リング型ネットワークにおける新規参加ノード１０５の挿入位置を決定する。
【００８９】
本実施形態に係るネットワークトポロジー構成方法によれば、リング型ネットワークにおいて各ノードがハッシュ値の順に並ぶようにネットワークトポロジーが構成されるため、新規参加ノード１０５であってもネットワークにおける各ノード間の位置関係を即座に把握することができる。
【００９０】
また、本実施形態に係るネットワークトポロジー構成方法によれば、リング型ネットワークを構成する各ノードは、隣接ノードに係る情報だけを管理していればよいので、当該ネットワークを構成する各ノードについてのネットワークトポロジー構成情報を入手するのに時間がかかるという問題点を解決することができる。
【００９１】
また、本実施形態に係るネットワークトポロジー構成方法によれば、ノードの故障やノードの当該ネットワークからの離脱等が発生した場合であっても、隣接ノード間で上述のリンクに係る情報を含むネットワークトポロジー構成情報の更新のためのメッセージ交換が多数行う必要が無く、ネットワーク負荷を軽減し、各ノードにおけるネットワークトポロジー構成情報の更新に時間がかかるという問題点を解決することができる。
【００９２】
＜本発明の第２の実施形態＞
本発明の第２の実施形態では、新規参加ノード１０５及びノード１０１の分散ハッシュテーブル１００ａが、リング型ネットワークを構成する全てのノードの識別情報から生成される全てのノードのハッシュ値を管理するように構成されている。
【００９３】
具体的には、図１０に示すように、分散ハッシュテーブル１００ａは、最小のハッシュ値を有するノードの「ノード位置」を示す「１」から最大のハッシュ値を有するノードの「ノード位置」を示す「ｎ」までの各「ノード位置」に対応する「ハッシュ値」及び「ノードアドレス」を管理している。
【００９４】
すなわち、分散ハッシュテーブル１００ａは、リング型ネットワークを構成する全てのノードの接続形態を示すネットワークトポロジー構成情報を管理している。
【００９５】
また、本実施形態に係るノード１０１の新規参加ノード受け入れ部１００ｄは、新規参加ノード１０５のハッシュ値「Ｎ」と全てのノードのハッシュ値とに基づいて、当該リング型ネットワークにおける新規参加ノード１０５の挿入位置を算出するように構成されている。この結果、上述の第１の実施形態に係るノード１０１の場合と異なり、本実施形態に係るノード１０１は、必ずリング型ネットワークにおける新規参加ノード１０５の挿入位置を算出することができる。
【００９６】
図１１及び図１２を参照して、本実施形態に係るノード１０１の動作について説明する。
【００９７】
図１１に示すように、ステップ３００１において、ノード１０１の新規参加ノード受け入れ部１００ｄが、ネットワークトポロジー構成情報送受信部１００ｃを介して、新規参加ノード１０５から、当該新規参加ノード１０５のハッシュ値及びノードアドレスを含むネットワークトポロジー構成情報を受信する。
【００９８】
ステップ３００２において、新規参加ノード受け入れ部１００ｄが、分散ハッシュテーブル１００ａから、全てのノードのハッシュ値を抽出する。
【００９９】
ステップ３００３において、新規参加ノード受け入れ部１００ｄが、受信した新規参加ノード１０５のハッシュ値、抽出した全てのノードのハッシュ値に基づいて、リング型ネットワークにおける当該新規参加ノード１０５の挿入位置を算出する。
【０１００】
ステップ３００４において、新規参加ノード受け入れ部１００ｄが、決定された新規参加ノード１０５の挿入位置に基づいて、図１２に示すように分散ハッシュテーブル１００ａを更新する。
【０１０１】
ステップ３００５において、新規参加ノード受け入れ部１００ｄが、ネットワークトポロジー構成情報送受信部１００ｃを介して、更新後の分散ハッシュテーブル１００ａの内容を含むネットワークトポロジー構成情報を、新規参加ノード１０５及び隣接ノード１０２、１０３に送信する。
【０１０２】
（変更例）
なお、本発明は、上述の実施形態に限定されることはなく、ノード１０１の代わりに、新規参加ノード１０５が、当該リング型ネットワークにおける当該新規参加ノード１０５の挿入位置を算出するように構成されていてもよい。
【０１０３】
かかる場合、ノード１０１は、リング型ネットワークにおける新規参加ノード１０５の挿入位置を含むネットワークトポロジー構成情報の代わりに、現在の分散ハッシュテーブル１００ａの内容を含むネットワークトポロジー構成情報を、当該新規参加ノード１０５に送信し、当該新規参加ノード１０５は、受信したネットワークトポロジー構成情報に基づいて、当該リング型ネットワークにおける当該新規参加ノード１０５の挿入位置を算出するように構成されている。
【図面の簡単な説明】
【０１０４】
【図１】本発明の第１の実施形態に係る新規参加ノード１０５がリング型ネットワークに新規に参加する前の状態を示す図である。
【図２】本発明の第１の実施形態に係る新規参加ノード１０５がリング型ネットワークに新規に参加した後の状態を示す図である。
【図３】本発明の第１の実施形態に係る新規参加ノード１０５の機能ブロック図である。
【図４】本発明の第１の実施形態に係るリング型ネットワークを構成するノード１０１の機能ブロック図である。
【図５】本発明の第１の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する際の新規参加ノード１０５の動作を示すフローチャートである。
【図６】本発明の第１の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する前後における新規参加ノード１０５の分散ハッシュテーブルの変化を説明するための図である。
【図７】本発明の第１の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する際のノード１０１の動作を示すフローチャートである。
【図８】本発明の第１の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する際にノード１０１が新規参加ノード１０５の挿入位置を算出する動作を示すフローチャートである。
【図９】本発明の第１の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する前後におけるノード１０１の分散ハッシュテーブルの変化を説明するための図である。
【図１０】本発明の第２の実施形態に係る新規参加ノード１０５及びノード１０１の分散ハッシュテーブルの一例を示す図である。
【図１１】本発明の第２の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する際のノード１０１の動作を示すフローチャートである。
【図１２】本発明の第２の実施形態において新規参加ノード１０５がリング型ネットワークに新規に参加する前後におけるノード１０１の分散ハッシュテーブルの変化を説明するための図である。
【図１３】従来技術において、ノード１０５がノード１０１との間でコネクションを確立する動作を示す図である。
【図１４】従来技術において、ノード１０５がノード１０１に対してＰｉｎｇメッセージを送信する動作を示す図である。
【図１５】従来技術において、ノード１０１がノード１０４に対してＰｏｎｇメッセージを送信するとともに、各ノード１０２乃至１０４に対してＰｉｎｇメッセージを送信する動作を示す図である。
【図１６】従来技術において、ノード１０２乃至１０４がノード１０１に対してＰｏｎｇメッセージを送信する動作を示す図である。
【図１７】従来技術において、ノード１０１がノード１０２乃至１０４との間でコネクションを確立する動作を示す図である。
【符号の説明】
【０１０５】
１０１、１０２、１０３、１０４…ノード
１０５…新規参加ノード
１００ａ…分散ハッシュテーブル（ＤＨＴ）
１００ｂ…ネットワーク加入処理部
１００ｃ…ネットワークトポロジー構成情報送受信部
１００ｄ…新規参加ノード受け入れ部
【図１】
2005198201.tif 000003
【図２】
2005198201.tif 000004
【図３】
2005198201.tif 000005
【図４】
2005198201.tif 000006
【図５】
2005198201.tif 000007
【図６】
2005198201.tif 000008
【図７】
2005198201.tif 000009
【図８】
2005198201.tif 000010
【図９】
2005198201.tif 000011
【図１０】
2005198201.tif 000012
【図１１】
2005198201.tif 000013
【図１２】
2005198201.tif 000014
【図１３】
2005198201.tif 000015
【図１４】
2005198201.tif 000016
【図１５】
2005198201.tif 000017
【図１６】
2005198201.tif 000018
【図１７】
2005198201.tif 000019