(57)【特許請求の範囲】
【請求項１】
少なくとも１つのブートストラップノードを含み、ネットワークに接続された複数のノードを備え、
前記ノードが、一意な属性情報のハッシュ値に基づいたノードＩＤを有し、仮想円周上に前記ノードＩＤに応じてマッピングされ、前記仮想円周上にマッピングされた位置と、前記仮想円周上にハッシュ値に応じてマッピングされたデータの位置とに基づいて、該データを管理するノードが決定される分散管理ネットワークシステムにおいて、
前記ブートストラップノードは、ユニークに割り当てられた固定長のプレフィックスで前記ノードＩＤの先頭の一部を上書きし、
前記ノードの中でブートストラップノード以外の非ブートストラップノードは、前記ネットワーク上で最も近いブートストラップノードのプレフィックスの先頭の一部のビットが同一な可変長のプレフィックスで前記ノードＩＤの先頭の一部を上書きし、
前記非ブートストラップノードのプレフィックスのビット長は、該非ブートストラップノードに前記ネットワーク上で最も近いブートストラップノードが前記仮想円周上にマッピングされた位置と、前記仮想円周上で該非ブートストラップノードを該ブートストラップノードと挟むようにマッピングされたブートストラップノードの位置との間の距離が長くなるに連れて短くなるように定められることを特徴とする分散管理ネットワークシステム。
【請求項２】
前記ブートストラップノードは、前記ネットワーク内に１から連続して割り当てられたブートストラップノード番号から１を減じた値のビット位置を上位と下位とを反転させたプレフィックスで前記ノードＩＤの先頭の一部を上書きすることを特徴とする請求項１に記載の分散管理ネットワークシステム。
【請求項３】
前記非ブートストラップノードのプレフィックスのビット長は、前記ブートストラップノードが前記仮想円周を実質的に等分するようにマッピングされた場合には、すべて等しくなるように定められることを特徴とする請求項２に記載の分散管理ネットワークシステム。
【請求項４】
前記ブートストラップノードが前記仮想円周を実質的に等分するようにマッピングされなかった場合には、前記仮想円周上における前記ブートストラップノード間の長さが長い領域にマッピングされた非ブートストラップノードのプレフィックスのビット長は、前記仮想円周上における前記ブートストラップノード間の長さが短い領域にマッピングされた非ブートストラップノードのプレフィックスのビット長より１ビット短くなるように定められることを特徴とする請求項２または請求項３に記載の分散管理ネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化オーバレイネットワークにおいて、複数のノードにデータを分散して管理させる分散管理システムに関する。
【背景技術】
【０００２】
構造化オーバレイは、コンピュータネットワーク上の各ノードに一意となるノードＩＤを割り当て、このＩＤに基づいてアプリケーション層で構築されるネットワーク技術である。
【０００３】
構造化オーバレイは、耐障害性および拡張性に優れていることから、大規模自律分散システムの基盤技術として期待されており、その代表的な適用例として分散ハッシュテーブル（Distributed Hash Table、以下「ＤＨＴ」という）が知られている。
【０００４】
ＤＨＴは、ハッシュテーブルを複数のノードで分散管理する技術である。ＤＨＴでは、データのハッシュ値から、そのデータを管理するノードが一意に定まるため、対象とするデータに対する非常に高い探索成功率と探索効率を持つ。
【０００５】
ＤＨＴは、ファイル配信分野を中心に実用化が進められてきたが（非特許文献１、２参照）、近年、ＶｏＩＰ(Voice over IP)システムにも適用されている（非特許文献３〜７参照）。
【０００６】
さらに、社内／構内に閉じた自営網でのＶｏＩＰシステムも、ＤＨＴの利用により低コストで構築することが可能となっている。しかし、ＤＨＴは、アプリケーション層のネットワークトポロジと下位層のネットワークトポロジとの相違に起因するデータ検索時の遅延伸長（以下、「Lookup遅延」という）が問題点の１つとして指摘されている（非特許文献８参照）。
【０００７】
このLookup遅延を解消するものとして、ノード同士の物理的な近接さを考慮するものがあり、なかでも、Proximity Identifier Selection（以下「ＰＩＳ」という）という技術が知られている（非特許文献６、９〜１１参照）。
【０００８】
ＰＩＳは、ノード同士の物理的な近接差を考慮したNode-IDを各ノードに付与することでLookup遅延の低減を図る技術である（非特許文献６参照）。ＰＩＳは、実装が容易であり、使用する構造化オーバレイのルーティングアルゴリズムから独立しており、ノード間の周期的なメッセージの送受信が不要なため、ネットワークに負荷を与えないという利点を有する。
【０００９】
このＰＩＳを適用する技術として、distributed binning（非特許文献９参照）、ＬＤＨＴ（Locality-aware Distributed Hash Table）（非特許文献１０参照）、ＬＰＤＨＴ（Locality-Aware and Partition-Space DHT）（非特許文献６参照）およびLocation-based node IDs（非特許文献１１参照）が知られている。
【００１０】
distributed binningでは、各ノードがネットワーク上に散在するLandmarkに対するＲＴＴ（Round Trip Time）を計測し、ＲＴＴの小さい順にLandmarkに序列をつける。このLandmarkの序列のことを"bin"と呼ぶ。distributed binningでは、ＲＴＴに応じたレベルをLandmarkに付与することでbinを数値化し、それをNode-IDとして使用している。
【００１１】
例えば、ＲＴＴが０〜１００ｍｓのときには、レベル０、１００から２００ｍｓのときには、レベル１、２００ｍｓ以上のときには、レベル２と定義した場合には、あるノードからLandmark l1，l2，l3に対するＲＴＴがそれぞれ２３２ｍｓ、５１ｍｓ、１１７ｍｓとすると、このノードのbinは"l2, l3, l1"となり、数値化されたbinは"０１２"となり、これをNode-IDのPrefixとして使用される。
【００１２】
ＬＤＨＴでは、各ノードはWHOIS query/responseにより自身のＡＳ（Autonomous System）番号を取得し、取得したＡＳ番号をNode-IDのPrefixとして使用する。ＬＰＤＨＴおよびLocation-based node IDsでは、地理ドメインおよび２次元の地理エリアに番号をマップして、マップした番号をNode-IDのPrefixとして使用する。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】P.Druschel and A. Rowstron, "PAST: A large-scale, persistent peer-to-peer storage utility", HotOS VIII, schuss Elmau, Germany, May 2001.
【非特許文献２】M.J. Freedman, E. Freudenthal, and D. Mazie`res, "Democratizing Content Publication with Coral," Proc. Networked Systems Design and Implementation (NSDI), pp. 239-252, 2004.
【非特許文献３】R. Cox, A. Muthitacharoen, and R. Morris, "Serving DNS using Chord," presented at the 1st Int.Workshop on Peer-to-Peer Systems (IPTPS'02), Cambridge, MA, Mar. 2002.
【非特許文献４】C. Jennings, B. Lowekamp, Ed., E. Rescorla, S. Baset, and H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) Base Protocol", draft-ietf-p2psip-base-08, http://datatracker.ietf.org/doc/draft-ietf-p2psip-base/, March 2010.
【非特許文献５】Guangyu Shi, Jian Chen, Hao Gong, Lingyuan Fan, Haiqiang Xue, Qingming Lu, and Liang Liang, "SandStone: A DHT Based Carrier Grade Distributed Storage System", Parallel Processing, 2009, ICPP '09, International Conference on, pp 420-428.
【非特許文献６】Wei Mi, Chunhong Zhang, Xiaofeng Qiu, Lichun Li, Yan Wang, and Yang Ji,"LPDHT: A Locality-Aware and Partitioned-Space Architecture for Peer-to-Peer SIP", Wireless Communications, Networking and Mobile Computing, 2009, WiCom '09. 5th International Conference on.
【非特許文献７】Mosiuoa Tsietsi, Alfredo Terzoli, and George Wells,"Prototyping a P2P SIP User Agent With Support for Multiple Overlays", Pervasive Computing and Communications, 2008, PerCom 2008, Sixth Annual IEEE International Conference on.
【非特許文献８】J. Risson and T. Moors,"Survey of Research towards Robust Peer-to-Peer Networks:Search Methods", RFC4981, September 2007.
【非特許文献９】Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker, "Topologically-Aware Overlay Construction and Server Selection", In Proceedings of the INFOCOMM, 2002.
【非特許文献１０】Weiyu Wu, Yang Chen, Xinyi Zhang, Xiaohui Shi, Lin Cong, Beixing Deng, and Xing Li, "LDHT: Locality-aware Distributed Hash Tables", Information Networking, 2008, ICOIN 2008, International Conference on.
【非特許文献１１】Shuheng Zhou, Gregory R. Ganger and Peter Steenkiste, "Location-based node IDs: enabling explicit locality in DHTs," Carnegie Mellon University, Tech. Rep. CMU-CS-03-171, 2003.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、distributed binningにおいては、数値化されたbinのカテゴリによりノード密度に大きな偏りが生じることにより、ノード間のオーバレイパス長が短くなるため、ノードが管理するデータ量の偏りが大きくなってしまうといった課題があった。
【００１５】
また、ＬＤＨＴにおいては、ＡＳ番号をそのままPrefixに利用するため、distributed binningと同様に、ノードが管理するデータ量の偏りが大きくなってしまうといった課題があった。
【００１６】
また、ＬＰＤＨＴやLocation-based node IDsにおいては、２次元の地理情報をそのままNode-IDのPrefixとして用いるため、ビルのような立体環境で高密度にノードが存在する自営網のような小規模ネットワークに適用することが困難であるといった課題があった。
【００１７】
本発明は、このような従来の課題を解決するためになされたもので、立体環境の小規模ネットワークに適用することができ、ノードが管理するデータ量の偏りを抑制することができる分散管理ネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明の分散管理ネットワークシステムは、少なくとも１つのブートストラップノードを含み、ネットワークに接続された複数のノードを備え、前記ノードが、一意な属性情報のハッシュ値に基づいたノードＩＤを有し、仮想円周上に前記ノードＩＤに応じてマッピングされ、前記仮想円周上にマッピングされた位置と、前記仮想円周上にハッシュ値に応じてマッピングされたデータの位置とに基づいて、該データを管理するノードが決定される分散管理ネットワークシステムにおいて、前記ブートストラップノードは、ユニークに割り当てられた固定長のプレフィックスで前記ノードＩＤの先頭の一部を上書きし、前記ノードの中でブートストラップノード以外の非ブートストラップノードは、前記ネットワーク上で最も近いブートストラップノードのプレフィックスの先頭の一部のビットが同一な可変長のプレフィックスで前記ノードＩＤの先頭の一部を上書きし、前記非ブートストラップノードのプレフィックスのビット長は、該非ブートストラップノードに前記ネットワーク上で最も近いブートストラップノードが前記仮想円周上にマッピングされた位置と、前記仮想円周上で該非ブートストラップノードを該ブートストラップノードと挟むようにマッピングされたブートストラップノードの位置との間の距離が長くなるに連れて短くなるように定められる構成を有している。
【００１９】
この構成により、本発明の分散管理ネットワークシステムは、仮想円周上にノードを集中させないようにマッピングすることができるため、ノードが管理するデータ量の偏りを抑制することができる。
【００２０】
また、本発明の分散管理ネットワークシステムは、ノードを仮想円周上にマッピングした上で、データを管理させるノードを決定するため、立体環境の小規模ネットワークに適用することができる。
【００２１】
なお、前記ブートストラップノードは、前記ネットワーク内に１から連続して割り当てられたブートストラップノード番号から１を減じた値のビット位置を上位と下位とを反転させたプレフィックスで前記ノードＩＤの先頭の一部を上書きするようにしてもよい。
【００２２】
この構成により、本発明の分散管理ネットワークシステムは、仮想円周上にブートストラップノードを集中させないようにマッピングすることができる。
【００２３】
また、前記非ブートストラップノードのプレフィックスの長さは、前記ブートストラップノードが前記仮想円周を実質的に等分するようにマッピングされた場合には、すべて等しくなるように定められるようにしてもよい。
【００２４】
この構成により、本発明の分散管理ネットワークシステムは、仮想円周上におけるブートストラップノード間で実質的に等分するように非ブートストラップノードをマッピングすることができる。
【００２５】
また、前記ブートストラップノードが前記仮想円周を実質的に等分するようにマッピングされなかった場合には、前記仮想円周上における前記ブートストラップノード間の長さが長い領域にマッピングされた非ブートストラップノードのプレフィックスの長さは、前記仮想円周上における前記ブートストラップノード間の長さが短い領域にマッピングされた非ブートストラップノードのプレフィックスのビット長より１ビット短くなるように定められるようにしてもよい。
【００２６】
この構成により、本発明の分散管理ネットワークシステムは、仮想円周上におけるブートストラップノード間で非ブートストラップノードを集中させないようにマッピングすることができる。
【発明の効果】
【００２７】
本発明は、立体環境の小規模ネットワークに適用することができ、ノードが管理するデータ量の偏りを抑制することができる分散管理ネットワークシステムを提供することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の一実施の形態に係る分散管理ネットワークシステムの構成を示すブロック図である。
【図２】本発明の一実施の形態に係る分散管理ネットワークシステムを構成するノードのハードウェア構成図である。
【図３】本発明の一実施の形態に係る分散管理ネットワークシステムを構成するブートストラップノードが生成するプレフィックスを示す概念図である。
【図４】本発明の一実施の形態に係る分散管理ネットワークシステムにおける仮想円周に対するノードのマッピングを説明するための概念図であり、（ａ）は、仮想円周上にブートストラップノードをマッピングした例を示し、（ｂ）は、仮想円周上にノードをマッピングした例を示している。
【図５】本発明の一実施の形態に係る分散管理ネットワークシステムを構成する非ブートストラップノードのプレフィックスビット長決定動作を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下に、本発明の実施の形態に係る分散管理ネットワークシステムについて、図面を参照しながら説明する。
【００３０】
図１に示すように、本発明の一実施の形態に係る分散管理ネットワークシステム１は、登録サーバ２と、登録サーバ２に自営網３を介して接続されたルータ４ａ、４ｂと、ルータ４ａに接続されたＬ２スイッチ５ａと、ルータ４ｂに接続されたＬ２スイッチ５ｂ、５ｃと、Ｌ２スイッチ５ａに接続されたノード６ａ、７ａ〜７ｃと、Ｌ２スイッチ５ｂに接続されたノード６ｂ、ノード７ｄ、７ｅと、Ｌ２スイッチ５ｃに接続されたノード７ｆ〜７ｈとを備えている。
【００３１】
なお、図１に示す、分散管理ネットワークシステム１の構成は、一例に過ぎず、本発明の分散管理ネットワークシステムは、少なくとも１つのブートストラップノードを含む複数のノードを備えていればよい。
【００３２】
各ルータ４ａ、４ｂは、サブネットワークを構成するための一般的なルータによって構成されている。また、各Ｌ２スイッチ５ａ〜５ｃは、一般的なＬ２スイッチによって構成されている。
【００３３】
なお、図１において、２つのルータ４ａ、４ｂと、３つのＬ２スイッチ５ａ〜５ｃが図示されているが、ルータおよびＬ２スイッチは、分散管理ネットワークシステム１のネットワーク構成によって適宜設けられる。
【００３４】
また、本実施の形態において、各ノード６ａ、６ｂは、それぞれブートストラップノードを構成し、以下、総称して「ブートストラップノード６」と記載し、各ノード７ａ〜７ｈは、ブートストラップノード以外の非ブートストラップノードを構成し、以下、総称して「非ブートストラップノード７」と記載し、ブートストラップノード６および非ブートストラップノード７を総称して「ノード」と記載する。
【００３５】
登録サーバ２は、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ハードディスク装置と、ノード６、７と自営網３を介して通信するための通信モジュールとを備えた一般的なコンピュータ装置によって構成されている。
【００３６】
ＲＯＭやハードディスク装置には、当該コンピュータ装置を登録サーバ２として機能させるためのプログラムが記憶されている。すなわち、ＣＰＵがＲＡＭを作業領域としてＲＯＭやハードディスク装置に記憶されたプログラムを実行することにより、当該コンピュータ装置は、登録サーバ２として機能する。
【００３７】
登録サーバ２のハードディスク装置には、ブートストラップノード６のＵＲＩ（Uniform Resource Identifier）がリスト化されたブートストラップリスト８が格納されている。ブートストラップリスト８は、ブートストラップノード６のＵＲＩを要素とした一次元のリストによって構成される。
【００３８】
ブートストラップノード６は、基本的には１つのサブネットに１つずつ配置される。サブネット内のノード数が少ない場合には、ネットワーク的に近接した複数のサブネットに対して１つのブートストラップノード６を配置してもよい。
【００３９】
各ノードが構造化オーバレイを構成するときのシーケンスは、ＩＥＴＦ  Ｐ２ＰＳＩＰに準拠する（非特許文献４参照）。すなわち、ノードがオーバレイに参加する場合には、起動時に、登録サーバ２にアクセスし、ブートストラップリスト８を入手する。
【００４０】
非ブートストラップノード７は、ブートストラップリスト８に基づいて、各ブートストラップノード６にエコー要求パケットを送信し、これに応じて返信されたエコー応答に含まれるＴＴＬ（Time to live）またはＲＴＴに基づいて、ネットワーク上で最も近いブートストラップノード６を選択し、選択したブートストラップノード６を介してメッセージやデータの送受信を行うようになっている。
【００４１】
ブートストラップリスト８の各要素に該当するブートストラップノード６は、全て稼動状態にあり、長期間オーバレイに参加した状態を維持するのに対して、非ブートストラップノード７は、オーバレイに対して必要に応じて参加および脱退してもよい。
【００４２】
図２に示すように、各ノードは、ＣＰＵ１０と、ＲＡＭ１１と、ＲＯＭ１２と、ハードディスク装置１３と、キーボード装置やポインティングデバイス等よりなる入力装置１４と、表示装置１５と、登録サーバ２や他のノードと自営網３を介して通信するための通信モジュール１６とを備えた一般的なコンピュータ装置によって構成されている。
【００４３】
ＲＯＭ１２やハードディスク装置１３には、当該コンピュータ装置をノードとして機能させるためのプログラムが記憶されている。すなわち、ＣＰＵ１０がＲＡＭ１１を作業領域としてＲＯＭ１２やハードディスク装置１３に記憶されたプログラムを実行することにより、当該コンピュータ装置は、ノードとして機能する。
【００４４】
また、ハードディスク装置１３には、分散管理ネットワークシステム１において分散管理するデータに加えて、当該ノードの一意な属性情報のハッシュ値に基づいたノードＩＤが格納されている。
【００４５】
本実施の形態において、各ノードは、分散管理ネットワークシステム１でユニークかつ固定的に割り当てられたＩＰアドレスのハッシュ値の先頭にプレフィックスを上書きすることによってノードＩＤを生成し、生成したノードＩＤをハードディスク装置１３に記憶するようになっている。
【００４６】
分散管理ネットワークシステム１を構成するブートストラップノード６の最大数ＭＢＮ（Maximum Bootstrap node Number）を２５６とすると、ブートストラップノード６は、８ビットのプレフィックスを生成するようになっている。なお、ＭＢＮは、ブートストラップノード６の増設を考慮し、分散管理ネットワークシステム１を構成するブートストラップノード６の数より多い２の冪乗よりなる。
【００４７】
具体的には、図３に示すように、ブートストラップノード６は、自営網３内に１から連続して割り当てられたブートストラップノード番号、すなわち、ブートストラップリスト８における自己のＵＲＩの登録番号から１を減じた値のビット位置を上位と下位とを反転させたプレフィックスを生成するようになっている。
【００４８】
ブートストラップノード６は、例えば１６０ビットのハッシュ値の先頭に、生成したプレフィックスを上書きし、プレフィックスを上書きしたハッシュ値をノードＩＤとしてハードディスク装置１３に格納するようになっている。
【００４９】
図４（ａ）に示すように、各ノードは、仮想円周上にノードＩＤに応じて各ノードをマッピングするようになっている。なお、図４（ａ）においては、発明を理解しやすくするために、ブートストラップノード６のみがマッピングされた例が示されている。
【００５０】
図４（ａ）において、ブートストラップリスト８において先頭に登録されているブートストラップノードＰｂ（１）は、０ｘ００のプレフィックスが上書きされたノードＩＤに応じた位置にマッピングされ、次に登録されているブートストラップノードＰｂ（２）は、０ｘ８０のプレフィックスが上書きされたノードＩＤに応じた位置にマッピングされ、末尾に登録されているブートストラップノードＰｂ（３）は、０ｘ４０のプレフィックスが上書きされたノードＩＤに応じた位置にマッピングされている。
【００５１】
この例においては、ブートストラップノードＰｂ（１）のノードＩＤより大きくブートストラップノードＰｂ（３）のノードＩＤ以下のハッシュ値が得られるデータは、ブートストラップノードＰｂ（３）によって管理される。
【００５２】
同様に、ブートストラップノードＰｂ（３）のノードＩＤより大きくブートストラップノードＰｂ（２）のノードＩＤ以下のハッシュ値が得られるデータは、ブートストラップノードＰｂ（２）によって管理され、ブートストラップノードＰｂ（２）のノードＩＤより大きい、または、ブートストラップノードＰｂ（１）のノードＩＤ以下のハッシュ値が得られるデータは、ブートストラップノードＰｂ（１）によって管理される。
【００５３】
非ブートストラップノード７は、ネットワーク上で最も近いブートストラップノード６のプレフィックスの先頭の一部のビットが同一な可変長のプレフィックスを生成するようになっている。
【００５４】
具体的には、非ブートストラップノード７は、ブートストラップノード６が仮想円周を実質的に等分するようにマッピングされている場合、すなわち、分散管理ネットワークシステム１を構成するブートストラップノード６の数ＮＢ（Number of Bootstrap nodes）が２の冪乗である場合には、ビット長が等しいプレフィックスを生成するようになっている。ここで、指数をｍとすると、プレフィックスのビット長は、ｍとなる。
【００５５】
一方、ブートストラップノード６が仮想円周を実質的に等分するようにマッピングされていない場合には、仮想円周上におけるブートストラップノード６間の長さが長い領域にマッピングされた非ブートストラップノード７のプレフィックスのビット長は、仮想円周上におけるブートストラップノード６間の長さが短い領域にマッピングされた非ブートストラップノード７のプレフィックスのビット長より１ビット短くなるように定められる。
【００５６】
より具体的には、ブートストラップノード６が仮想円周を実質的に等分するようにマッピングされたブートストラップノード６の数（すなわち、ＮＢを超えない最小の２ｍ）より大きいブートストラップノード番号のブートストラップノード６は、仮想円周が実質的に等分された後に、仮想円周上にマッピングされるため、次のブートストラップノード６との間の長さが短くなる。
【００５７】
したがって、非ブートストラップノード７は、ネットワーク上で最も近いブートストラップノード６のブートストラップノード番号ＮＣＢ（Number of Connecting Bootstrap node）に対して、ＮＣＢ＞２ｍ（以下、「第１条件」ともいう）が成立する場合には、ビット長がｍ＋１のプレフィックスを生成するようになっている。
【００５８】
また、ＮＢを超えない最小の２ｍにブートストラップノード番号を加算した値がＮＢ以下のブートストラップノード６は、仮想円周が実質的に等分された後に仮想円周上にマッピングされるブートストラップノード６の直前にマッピングされているため、次のブートストラップノード６との間の長さが短くなる。
【００５９】
したがって、非ブートストラップノード７は、２ｍ＋ＮＣＢ≦ＮＢ（以下、「第２条件」ともいう）が成立する場合には、ビット長がｍ＋１のプレフィックスを生成するようになっている。
【００６０】
また、非ブートストラップノード７は、ＮＣＢおよびＮＢが第１条件および第２条件の何れも成立しない場合には、ビット長がｍのプレフィックスを生成するようになっている。
【００６１】
例えば、図４（ｂ）において、ブートストラップノードＰｂ（１）およびブートストラップノードＰｂ（２）は、仮想円周を実質的に２等分するようにマッピングされており、ブートストラップノードＰｂ（３）は、仮想円周が実質的に２等分された後に仮想円周上にマッピングされている。
【００６２】
このため、ＮＣＢが３の非ブートストラップノードＰｎ（３）は、第１条件が成立し、ビット長がｍ＋１、すなわち、ブートストラップノードＰｂ（３）の先頭の２ビットからプレフィックス"０１"を生成する。
【００６３】
また、ＮＣＢが１の非ブートストラップノードＰｎ（１）は、ブートストラップノードＰｂ（３）の直前にマッピングされるため、第２条件が成立し、ビット長がｍ＋１、すなわち、ブートストラップノードＰｂ（１）の先頭の２ビットからプレフィックス"００"を生成する。
【００６４】
また、ＮＣＢが２の非ブートストラップノードＰｎ（２ａ）〜Ｐｎ（２ｃ）は、第１条件および第２条件の何れも成立しないため、ビット長がｍ、すなわち、ブートストラップノードＰｂ（２）の先頭の１ビットからプレフィックス"１"を生成する。
【００６５】
以上のように構成された非ブートストラップノード７のプレフィックスビット長決定動作を図５に示すフローチャートを参照しながら説明する。非ブートストラップノード７は、指数ｍの初期値を０として（ステップＳ１）、以下の処理を実行する。
【００６６】
まず、非ブートストラップノード７は、ブートストラップノード６の数ＮＢが２ｍであるか否かを判断する（ステップＳ２）。ここで、ＮＢが２ｍであると判断した場合には、非ブートストラップノード７は、プレフィックスのビット長ｐｌｅｆｉｘ＿ｐをｍに定め（ステップＳ３）、プレフィックスビット長決定動作を終了する。
【００６７】
一方、ＮＢが２ｍ乗でないと判断した場合には、非ブートストラップノード７は、２ｍ＜ＮＢ＜２ｍ＋１が成立しているか否かを判断する（ステップＳ４）。ここで、２ｍ＜ＮＢ＜２ｍ＋１が成立していないと判断した場合には、非ブートストラップノード７は、ｍをインクリメントし（ステップＳ５）、ステップＳ２を実行する。
【００６８】
一方、２ｍ＜ＮＢ＜２ｍ＋１が成立していると判断した場合には、非ブートストラップノード７は、ネットワーク上で最も近いブートストラップノード６のブートストラップノード番号ＮＣＢが２ｍより大きい、すなわち、ＮＣＢ＞２ｍ、または２ｍ＋ＮＣＢ≦ＮＢの何れか一方の条件が成立しているか否かを判断する（ステップＳ６）。
【００６９】
ここで、ＮＣＢ＞２ｍまたは２ｍ＋ＮＣＢ≦ＮＢの何れか一方の条件が成立していると判断した場合には、非ブートストラップノード７は、プレフィックスのビット長ｐｌｅｆｉｘ＿ｐをｍ＋１に定め（ステップＳ７）、プレフィックスビット長決定動作を終了する。
【００７０】
一方、ＮＣＢ＞２ｍまたは２ｍ＋ＮＣＢ≦ＮＢの何れの条件も成立していないと判断した場合には、非ブートストラップノード７は、プレフィックスのビット長ｐｌｅｆｉｘ＿ｐをｍに定め（ステップＳ３）、プレフィックスビット長決定動作を終了する。
【００７１】
このように、本発明の一実施の形態に係る分散管理ネットワークシステム１は、仮想円周上にノードを集中させないようにマッピングすることができるため、ノードが管理するデータ量の偏りを抑制することができる。
【００７２】
また、分散管理ネットワークシステム１は、ノードを仮想円周上にマッピングした上で、データを管理させるノードを決定するため、立体環境の小規模ネットワークに適用することができる。
【産業上の利用可能性】
【００７３】
本発明の分散管理ネットワークシステムは、構造化オーバレイネットワークにおいて、複数のノードにデータを分散して管理させるシステムとして利用することができる。
【符号の説明】
【００７４】
１  分散管理ネットワークシステム
２  登録サーバ
３  自営網
４ａ、４ｂ  ルータ
５ａ〜５ｃ  Ｌ２スイッチ
６、６ａ、６ｂ、Ｐｂ  ブートストラップノード
７、７ａ〜７ｈ、Ｐｎ  非ブートストラップノード
８  ブートストラップリスト
１０  ＣＰＵ
１１  ＲＡＭ
１２  ＲＯＭ
１３  ハードディスク装置
１４  入力装置
１５  表示装置
１６  通信モジュール
【図１】
0005558318.tif 000002
【図２】
0005558318.tif 000003
【図３】
0005558318.tif 000004
【図４】
0005558318.tif 000005
【図５】
0005558318.tif 000006