(57)【要約】【課題】より柔軟に分散ハッシュテーブル（ＤＨＴ）を構築することのできるＤＨＴノードを提供すること。【解決手段】ＤＨＴノード３は、特定のハッシュ値を分担するＤＨＴノードが受信すべきメッセージを、受信先ノードを特定できずに送信する場合に、転送先候補となるＤＨＴノードを登録したフィンガーテーブル３５を持つ。管理部３６は、自ノード以外のＤＨＴノードのうちから、フィンガーテーブル３５に登録すべきものを、指定されたパラメータに応じて定まる個数だけ選択する。その際、管理部３６は、自ノードに係るハッシュ値に２のｒ乗（ｒは０≦ｒ＜ｍの範囲から選択された実数、ｍはＤＨＴが管理するハッシュ空間のビット数）を追加して得たハッシュ値と、自ノード以外のＤＨＴノードに係るハッシュ値とに基づいて、フィンガーテーブルに登録すべきノード装置を選択する。【選択図】      図２
2008234536.tif 000002
【特許請求の範囲】
【請求項１】
相異なるハッシュ値の範囲を分担する複数のノード装置からなる分散ハッシュテーブルシステムを構成する一つのノード装置において、
特定のハッシュ値を分担するノード装置が受信すべきメッセージを、そのノード装置を特定できずに送信すべき場合に、該メッセージを転送すべき候補になる複数のノード装置の情報を登録したフィンガーテーブルと、
前記分散ハッシュテーブルシステムを構成する自ノード以外の全てのノード装置のうちから、前記フィンガーテーブルに登録すべきノード装置を、指定されたパラメータに応じて定まる個数だけ選択する選択手段とを備え、
前記分散ハッシュテーブルシステムを構成するノード装置それぞれには相異なるハッシュ値が対応付けられており、
前記選択手段は、自ノードに対応付けられたハッシュ値に２のｒ乗（ｒは０≦ｒ＜ｍの範囲から選択された実数であり、ｍは前記分散ハッシュテーブルシステムが管理するハッシュ空間のビット数である。）を追加して得たハッシュ値と、自ノード以外の前記ノード装置に対応付けられたハッシュ値とに基づいて、前記フィンガーテーブルに登録すべきノード装置を選択することを特徴とするノード装置。
【請求項２】
前記選択手段は、前記パラメータに応じて、前記ｒの値を変化させることによって、前記個数のノード装置を選択することを特徴とする請求項１に記載のノード装置。
【請求項３】
前記選択手段は、自ノードに対応付けられたハッシュ値に２の（ｉ・ｍ／Ｍ）乗（Ｍは任意の値であり、ｉは０≦ｉ≦Ｍ−１の範囲の任意の整数値であり、ｍは前記分散ハッシュテーブルシステムが管理するハッシュ空間のビット数である。）を追加して得たハッシュ値と、自ノード以外の前記ノード装置に対応付けられたハッシュ値とに基づいて、前記フィンガーテーブルに登録すべきノード装置を選択することを特徴とする請求項１に記載のノード装置。
【請求項４】
前記Ｍは、前記パラメータに基づいて定まる値であり、
前記選択手段は、０≦ｉ＜Ｍ−１を満たす全てのｉについてそれぞれ前記ノード装置の選択を行うことを特徴とする請求項３に記載のノード装置。
【請求項５】
前記Ｍは、前記パラメータをfとして、Ｍ＝f・mで与えられるものであることを特徴とする請求項３または４に記載のノード装置。
【請求項６】
前記パラメータfは、アプリケーションからの要求により決定されるものであることを特徴とする請求項５に記載のノード装置。
【請求項７】
前記パラメータを設定する設定手段を更に備えたことを特徴とする請求項１ないし６のいずれか１項に記載のノード装置。
【請求項８】
前記特定のハッシュ値と、前記フィンガーテーブルに登録されている前記複数のノード装置それぞれに対応付けられているハッシュ値とに基づいて、前記メッセージを転送すべき一つのノード装置を特定する手段を更に備えたことを特徴とする請求項１ないし７のいずれか１項に記載のノード装置。
【請求項９】
前記分散ハッシュテーブルシステムを構成するノード装置それぞれが分担するハッシュ値の範囲は、当該ノード装置が記憶・管理するデータに対するキー情報のハッシュ値であるとともに、該キー情報は、個品流通管理・トレーサビリティシステムにおいて個品毎に付与される識別子であり、該データは、該識別子を付与された個品に関する情報であり、
前記メッセージは、前記キー情報を指定した問い合わせメッセージであることを特徴とする請求項１ないし８のいずれか１項に記載のノード装置。
【請求項１０】
相異なるハッシュ値の範囲を分担する複数のノード装置からなる分散ハッシュテーブルシステムを構成し、特定のハッシュ値を分担するノード装置が受信すべきメッセージを、そのノード装置を特定できずに送信すべき場合に、該メッセージを転送すべき候補になる複数のノード装置の情報を登録したフィンガーテーブルを備えた一つのノード装置の転送先ノード決定方法において、
前記ノード装置の備える設定手段が、指定されたパラメータを設定するステップと、
前記ノード装置の備える選択手段が、前記分散ハッシュテーブルシステムを構成する自ノード以外の全てのノード装置のうちから、前記パラメータに応じて定まる個数だけ、前記フィンガーテーブルに登録すべきノード装置を選択するステップとを備え、
前記分散ハッシュテーブルシステムを構成するノード装置それぞれには相異なるハッシュ値が対応付けられており、
前記選択手段は、自ノードに対応付けられたハッシュ値に２のｒ乗（ｒは０≦ｒ＜ｍの範囲から選択された実数であり、ｍは前記分散ハッシュテーブルシステムが管理するハッシュ空間のビット数である。）を追加して得たハッシュ値と、自ノード以外の前記ノード装置に対応付けられたハッシュ値とに基づいて、前記フィンガーテーブルに登録すべきノード装置を選択することを特徴とする転送ノード決定方法。
【請求項１１】
相異なるハッシュ値の範囲を分担する複数のノード装置からなる分散ハッシュテーブルシステムを構成する一つのノード装置としてコンピュータを機能させるためのプログラムにおいて、
特定のハッシュ値を分担するノード装置が受信すべきメッセージを、そのノード装置を特定できずに送信すべき場合に、該メッセージを転送すべき候補になる複数のノード装置の情報を登録したフィンガーテーブルと、
前記分散ハッシュテーブルシステムを構成する自ノード以外の全てのノード装置のうちから、前記フィンガーテーブルに登録すべきノード装置を、指定されたパラメータに応じて定まる個数だけ選択する選択手段とをコンピュータに実現させるためのものであるとともに、
前記分散ハッシュテーブルシステムを構成するノード装置それぞれには相異なるハッシュ値が対応付けられており、
前記選択手段は、自ノードに対応付けられたハッシュ値に２のｒ乗（ｒは０≦ｒ＜ｍの範囲から選択された実数であり、ｍは前記分散ハッシュテーブルシステムが管理するハッシュ空間のビット数である。）を追加して得たハッシュ値と、自ノード以外の前記ノード装置に対応付けられたハッシュ値とに基づいて、前記フィンガーテーブルに登録すべきノード装置を選択することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ハッシュテーブルに用いられるノード装置、転送ノード決定方法及びプログラムに関する。
【背景技術】
【０００２】
分散ハッシュテーブル（ＤＨＴ（Distributed Hash Table））方式の一つとして、Ｃｈｏｒｄ方式（非特許文献１）が知られている。
【０００３】
Ｃｈｏｒｄにおいては、ＤＨＴ構築のための方式が固定されている。具体的には、短絡経路の設計方法が変形２分木探索に等しくなっており、探索のためのコストは、ＤＨＴノードの数をＮとしたときにＯ（log２ Ｎ）である。このため、様々なアプリケーションの要求に柔軟に応えることが困難であった。特に、機能維持のための通信コストと、問い合わせ応答にかかる時間あるいは再帰段数との間にはトレードオフの関係があり、これを制御することができなかった。
【非特許文献１】I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of ACM SIGCOMM, August 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＤＨＴの一つとして知られているＣｈｏｒｄでは、例えばＤＨＴを利用するアプリケーションのニーズに応じて柔軟にＤＨＴを構築することができなかった。
【０００５】
本発明は、上記事情を考慮してなされたもので、より柔軟にＤＨＴを構築することのできるＤＨＴのノード装置、転送ノード決定方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、相異なるハッシュ値の範囲を分担する複数のノード装置からなる分散ハッシュテーブルシステムを構成する一つのノード装置において、特定のハッシュ値を分担するノード装置が受信すべきメッセージを、そのノード装置を特定できずに送信すべき場合に、該メッセージを転送すべき候補になる複数のノード装置の情報を登録したフィンガーテーブルと、前記分散ハッシュテーブルシステムを構成する自ノード以外の全てのノード装置のうちから、前記フィンガーテーブルに登録すべきノード装置を、指定されたパラメータに応じて定まる個数だけ選択する選択手段とを備え、前記分散ハッシュテーブルシステムを構成するノード装置それぞれには相異なるハッシュ値が対応付けられており、前記選択手段は、自ノードに対応付けられたハッシュ値に２のｒ乗（ｒは０≦ｒ＜ｍの範囲から選択された実数であり、ｍは前記分散ハッシュテーブルシステムが管理するハッシュ空間のビット数である。）を追加して得たハッシュ値と、自ノード以外の前記ノード装置に対応付けられたハッシュ値とに基づいて、前記フィンガーテーブルに登録すべきノード装置を選択することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、より柔軟にＤＨＴを構築することができるようになる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照しながら本発明の実施形態について説明する。
【０００９】
図１に、本発明の一実施形態に係る分散ハッシュテーブル（ＤＨＴ（Distributed Hash Table））システムの構成例を示す。
【００１０】
図１において、１はクライアント、３はＤＨＴノード、８はネットワークである。
【００１１】
複数台のＤＨＴノード３が連携して、１つの分散ハッシュテーブルを構成する。図１では、分散ハッシュテーブルを構成するＤＨＴノードとして８台のＤＨＴノードが示されているが、これは一例であり、分散ハッシュテーブルシステムを構成するＤＨＴノードの台数は任意である。また、ＤＨＴサーバの台数は、参加・離脱によって、変動し得るものである。
【００１２】
１つの分散ハッシュテーブルを構成する複数のＤＨＴノード３は、ネットワーク８を介して、相互に通信可能である。なお、ネットワーク８は、どのようなネットワークでもよい。
【００１３】
クライアント１は、ネットワーク８を介して任意のＤＨＴノード３にアクセス可能とする。図１では、１台のクライアント計算機のみが示されているが、もちろん、クライアント計算機は複数台存在し得る。なお、クライアント１が、いずれかのＤＨＴノード３にローカルに接続される構成も可能である。
【００１４】
さて、本実施形態の分散ハッシュテーブルにおいては、ハッシュ値の集合で構成されるハッシュ空間において、両端が連結された閉じた数直線としてハッシュ空間を形成した場合を考える。複数のＤＨＴノード３は、ハッシュ空間の相異なるハッシュ値に対応付けられる。この場合、各ＤＨＴノード３は、いずれも、二つの他のＤＨＴノード３と隣接することになる。
【００１５】
ここで、或るＤＨＴノードに対応するハッシュ値をαとして、ハッシュ空間においてハッシュ値が増加する方向でαに最も近いハッシュ値に対応付けられているＤＨＴノードを、該或るＤＨＴノードに対して「増加方向側隣接ノード」と呼び、ハッシュ値が減少する方向でαに最も近いハッシュ値に対応付けられているＤＨＴノードを、該或るＤＨＴノードに対して「減少方向側隣接ノード」と呼ぶものとする。
【００１６】
本実施形態では、或るＤＨＴノードに対応するハッシュ値をｘ１、該或るＤＨＴノードの減少方向側隣接ノードに対応するハッシュ値をｘ０であるとして、該或るＤＨＴノードが、ｘ０＜ｈ≦ｘ１の範囲のハッシュ値ｈを分担するような分担方法を採用する場合を例にとって説明する。もしろん、これ以外の分担方法も可能である。
【００１７】
例えば、ｈ０＜ｈ≦ｈ１の範囲のハッシュ値ｈを分担するＤＨＴノードＡ１は、キーとなる情報（以下、識別子と呼ぶ）のハッシュ値ｈがｈ０＜ｈ≦ｈ１の範囲にあるような識別子について、当該識別子と、当該識別子をキーとして検索されるデータとを記録したデータベースを記憶・管理することになる。
【００１８】
また、上記ＤＨＴノードＡ１の増加方向側隣接ノードであるＤＨＴノードＡ２は、これに対応するハッシュ値をｘ２とすると、識別子のハッシュ値ｈがｈ１＜ｈ≦ｈ２となるような識別子について、当該識別子と、当該識別子をキーとして検索されるデータとを記録したデータベースを記憶・管理することになる。
【００１９】
なお、上記ＤＨＴノードＡ１は、自ノードのハッシュ値（又はそのもととなる情報）の他に、その減少方向側隣接ノードＡ０に対応するハッシュ値（又はそのもととなる情報）と、その増加方向側隣接ノードＡ２に対応するハッシュ値（又はそのもととなる情報）とを記憶しておけば、自ノードＡ１の分担範囲と、増加方向側隣接ノードＡ２の分担範囲とを特定することができる（この場合、減少方向側隣接ノードＡ０の分担範囲は分からない）。
【００２０】
上記のハッシュ関数としては、ビット数が充分長くて一様な割り当てが行なわれる関数を用いると好ましい。そのようなハッシュ関数として、例えば、ＳＨＡ−１やＭＤ５を採用することができる。ハッシュ空間は、０〜２ｍ−１のｍビットの整数で表わされる（ＳＨＡ−１の場合は、ｍ＝１６０となり、ＭＤ５の場合は、ｍ＝１２８となる）。
【００２１】
なお、各ＤＨＴノード３に対応付けるハッシュ値の決め方としては、例えば、当該ＤＨＴノード３の持つアドレス（例えばＩＰアドレス）に対してハッシュ関数を適用して得られるハッシュ値とする方法を採用してもよいし、他の方法を採用してもよい。
【００２２】
図２に、本実施形態に係るＤＨＴノードの構成例を示す。
【００２３】
図２に示されるように、ＤＨＴノード３は、メッセージ処理部３１、自ノード情報記憶部３２、隣接ノード情報記憶部３３、データベース３４、フィンガーテーブル３５、フィンガーテーブル管理部３６、通信部３７を備えている。また、フィンガーテーブル管理部３６には、パラメータ設定部３６１、計算部３６２、ノード探索部３６３が含まれる。
【００２４】
通信部３７は、ネットワーク８を介してクライアント１や他のＤＨＴノード３とメッセージ通信等を行うためのものである。なお、ＤＨＴノード３にローカルにクライアント１が接続する場合には、クライアント１と接続するためのインタフェースを備えればよい。
【００２５】
メッセージ処理部３１は、クライアント１や他のＤＨＴノード３から通信部３７を介して問い合せメッセージを受信した場合に、受信した問い合せメッセージを処理し、必要に応じて、通信部３７を介して、クライアント１へ応答メッセージを送信したり、あるいは、他のＤＨＴノード３へ問い合せメッセージを転送したりするためのものである。
【００２６】
自ノード情報記憶部３２は、自ノードのアドレスや自ノードに対応するハッシュ値など、自ノードに関する情報を記憶する。
【００２７】
隣接ノード情報記憶部３３は、自ノードに対する減少方向側隣接ノードについて、これに対応するハッシュ値を記憶する（そのアドレスをも記憶しても構わない）。また、増加方向側隣接ノードについて、そのアドレスと、これに対応するハッシュ値を記憶する。
【００２８】
データベース３４は、自ノードの分担するハッシュ空間に属するハッシュ値を与える識別子を持つデータについて、当該識別子と、当該識別子をキーとして検索されるデータとを対にして記憶する。図３に、データベース３４の一例を示す。なお、データベース３４に格納されるデータは、クライアント１が最終的に取得したいデータとすることもできるし、クライアント１が最終的に取得したいデータを取得するためのＵＲＬのような情報とすることもできる。
【００２９】
フィンガーテーブル（経路表）３５は、問い合せメッセージを転送する候補となる幾つかのＤＨＴノード（後述するＭ＝ｆａｍｐ×ｍ個のＤＨＴノード）について、そのＤＨＴノードのアドレスと、そのＤＨＴノードに対応するハッシュ値を記憶する。図４に、フィンガーテーブル３５の一例を示す。図４中のｉはエントリのインデックスである（図５のｎｅｘｔに相当するものである）。
【００３０】
フィンガーテーブル管理部３６は、詳しくは後述するが、フィンガーテーブル３５を管理するためのものである。
【００３１】
なお、あるＤＨＴノードのアドレスのハッシュ値を、そのＤＨＴノードに対応するハッシュ値とする場合には、自ノード情報記憶部３２、隣接ノード情報記憶部３３、フィンガーテーブル３５において、アドレスのみ記憶しておき、ハッシュ値は、記憶せずに、その都度計算する方法も可能である。
【００３２】
なお、本実施形態のＤＨＴノード３において、自ノードに関する情報の管理、参加・離脱制御、隣接ノードに関する情報の管理、データベースの管理、自ノードの属するハッシュ空間上の任意のハッシュ値を担当するＤＨＴノードの検索などは、基本的には、従来からある方法を用いて構わない。
【００３３】
次に、フィンガーテーブル３５に登録するＤＨＴノードの探索について説明する。
【００３４】
図５に、本実施形態のＤＨＴノード３のフィンガーテーブル管理部３６が、フィンガーテーブル３５に登録するＤＨＴノードを探索するアルゴリズム（Ｆｉｎｇｅｒ経路の決定のためのアルゴリズム）の一例を示す。
【００３５】
なお、パラメータ設定部３６１に、予め、パラメータｍ、パラメータｆａｍｐ（Ｆｉｎｇｅｒ  Ａｍｐｌｉｆｉｃａｔｉｏｎ  Ｒａｔｉｏ）（０より大きい実数値）が設定されているものとする。また、ｍは、ハッシュ空間（０〜２ｍ−１）のビット幅であり、採用しているハッシュ関数に応じて定まる値である（ＳＨＡ−１の場合は、ｍ＝１６０となり、ＭＤ５の場合は、ｍ＝１２８となる）。また、ｆａｍｐは、任意に設定可能であり、例えばユーザが適宜設定できるようにしてもよいし、他のアプリケーションが指定できるようにしてもよい。
【００３６】
フィンガーテーブル３５に登録するＤＨＴノードの数（Ｆｉｎｇｅｒの経路表エントリ数）は、上記のＭになる（すなわち、ｆａｍｐを調整することによってコントロールすることができる）。
【００３７】
アルゴリズムで使用されるｎｅｘｔは、１〜Ｍまで変化する整数であり、フィンガーテーブル３５に登録するＤＨＴノードの順番を表すパラメータ（Ｆｉｎｇｅｒの経路表エントリのインデックス）である。
【００３８】
上記アルゴリズムにおいては、まず、計算部３６２が、ｎｅｘｔに０を設定し（ステップＳ１）、Ｍにｆａｍｐ×ｍを設定する（ステップＳ２）。
【００３９】
ただし、Ｍは、ｍ・ｆａｍｐに近い整数値になるように用意する。その際、小数点以下四捨五入、切り上げ、切り捨て、２以上の数を単位にしたその他の丸め方など、種々の近似方法を採用可能である。
【００４０】
なお、ステップＳ１とステップＳ２は、上記と逆の順に実行してもよいし、同時に実行してもよい。
【００４１】
以降は、ｎｅｘｔを１ずつ増加させながら行う繰り返し処理になる。すなわち、まず、ｎｅｘｔ＝１として（ステップＳ３）、ステップＳ６〜ステップＳ８の処理を行い、指定の秒数待った（ステップＳ９）後に、ｎｅｘｔを１増加して（ステップＳ３）、同様の処理を繰り返し、ｎｅｘｔがＭを超えるときに（ステップ４）、再度、ｎｅｘｔを１に戻して（ステップＳ５）、同様の処理を繰り返す。
【００４２】
さて、繰り返し処理において、計算部３６２は、ｒにｍ×（ｎｅｘｔ−１）／Ｍを設定し（ステップＳ６）、ＤＨＴのハッシュ空間上の目標値ｔａｒｇｅｔに、ｎ＋２ｒを設定し（ステップＳ７）、次いで、ノード探索部３６３が、finger［next］＝find_succ（target）を実行する（ステップＳ８）。
【００４３】
なお、ｎは、自ノードに対応するハッシュ値である。
【００４４】
例えば、ｆａｍｐ＝２．０、ｍ＝１６０の場合に、ｎｅｘｔ＝１のときは、ｒ＝０、ｔａｒｇｅｔ＝ｎ＋１から、finger［1］＝find_succ（ｎ＋１）を実行する。
【００４５】
ｎｅｘｔ＝２のときは、ｒ＝１／２、ｔａｒｇｅｔ＝ｎ＋２１／２から、finger［1］＝find_succ（ｎ＋２１／２）を実行する。
【００４６】
ｎｅｘｔ＝３１９のときは、ｒ＝３１８／２、ｔａｒｇｅｔ＝ｎ＋２３１８／２から、finger［1］＝find_succ（ｎ＋２３１８／２）を実行する。
【００４７】
ｎｅｘｔ＝３２０のときは、ｒ＝３１９／２、ｔａｒｇｅｔ＝ｎ＋２３１９／２から、finger［1］＝find_succ（ｎ＋２３１９／２）を実行する。
【００４８】
このfinger［next］＝find_succ（target）は、ｔａｒｇｅｔで表されるハッシュ値に最も近いＤＨＴノード（ここでは、ハッシュ値のサクセッサーとする。）を探索し、該ＤＨＴノードに関する情報を、フィンガーテーブル３５の第next番目のエントリに記入するものである。
【００４９】
なお、ｔａｒｇｅｔで表されるハッシュ値と各ＤＨＴノードのハッシュ空間上の位置との近さの評価は、メッセージ転送（Ｋｅｙ  Ｂａｓｅｄ  Ｒｏｕｔｉｎｇ）のアルゴリズムと矛盾してなければ、ノードのハッシュ空間上の位置の差の絶対値でもよいし、ハッシュ空間の順序性による制約を与えてもよい。
【００５０】
上記では、Ｃｈｏｒｄと同様、ハッシュ値のサクセッサー（ハッシュ空間上でハッシュ値の増加方向で最も近いＤＨＴノード）が対応するデータを持つ場合を一例として示しているが、アルゴリズムの詳細には様々なバリエーションがあり得る。例えば、プレデセッサー（ハッシュ空間上でハッシュ値の現象方向で最も近いＤＨＴノード）が対応するデータを持つ場合も同様に実現可能である。
【００５１】
Ｃｈｏｒｄの問題は、そのアルゴリズムが柔軟性に欠ける点であるが、本実施形態では、ＤＨＴノードにおけるＦｉｎｇｅｒを設定するモジュール等において、アプリケーションからの要求に従ってＦｉｎｇｅｒを設定する方式を変動させる機構を導入することができる。より具体的には、例えばアプリケーションが求めるＤＨＴの特性に基づき任意に決定するパラメータｆａｍｐを調整することによって、ｆｉｎｇｅｒの宛先の選択の粒度をコントロールすることができる。
【００５２】
図６〜図８に、それぞれ、ｆａｍｐ＝１．０，２．０，３．０の場合に得られるｔａｒｇｅｔの様子を示す。図６〜図８では、円が、ハッシュ空間の両端が連結されているものとみなしてハッシュ空間をループ状に形成した場合のハッシュ空間を示し、円の頂上側（０時の方向）が自ノードに対応するハッシュ値の位置を示し、自ノードから出ている各矢印の先端が円と交わる位置が、自ノードに対するｔａｒｇｅｔのハッシュ値がどのように配置されるかを計算で求めた結果を示している（なお、円周の１／１６未満に相当するｔａｒｇｅｔの配置は省略している）。なお、図６が従来のＣｈｏｒｄと同じになる。
【００５３】
図６〜図８を一見して明らかなように、ｔａｒｇｅｔの分布はｆａｍｐを増大させるごとに密度が濃くなり、円周上のより多くのエリアに短かいホップ数で到達できるようになることがわかる。
【００５４】
すなわち、ｆａｍｐ＝１．０にすると、Ｃｈｏｒｄと同じアルゴリズムになり、ｆａｍｐ＜１．０にすると、Ｃｈｏｒｄよりも、問い合わせにかかる時間および再帰段数の平均が増えるが、維持コストを低くでき、ｆａｍｐ＞１．０にすると、Ｃｈｏｒｄよりも、維持コストが高くなるが、問い合わせにかかる時間（再帰段数の平均）を減らせることが期待できる。
【００５５】
なお、図５のアルゴリズムは一例であり、他のアルゴリズムも実施可能である。
【００５６】
次に、ＤＨＴにおけるメッセージ転送について説明する。
【００５７】
前述のように、ハッシュ値のサクセッサーが対応するデータを持つ場合を一例として示しているが、プレデセッサーが対応するデータを持つ場合など、種々のバリエーションがあり得る。
【００５８】
図９に、本実施形態に係るＤＨＴノードの問い合せメッセージ受信時における処理手順の一例を示す。
【００５９】
クライアント１は、分散ハッシュテーブルシステムから、所望の識別子に対応するデータを取得したい場合には、いずれかのＤＨＴノード３に、所望の識別子を含む問い合せメッセージを送信する。なお、クライアント１は、複数のＤＨＴノード３のアドレスを知っている場合には、それらのうちの任意のＤＨＴノード３に問い合せメッセージを送信して構わない。
【００６０】
ＤＨＴノード３は、クライアント１から問い合せメッセージを受信すると（または、クライアント１が送信し、他の１以上のＤＨＴノードにより転送されてきた問い合せメッセージを受信すると）（ステップＳ１１）、まず、問い合せメッセージに含まれる識別子のハッシュ値（宛先ハッシュ値）ｈｍを計算する（ステップＳ１２）。
【００６１】
そして、これが、自ノードの分担範囲に含まれるものかどうか調べる（ステップＳ１３）。もし、自ノードの分担範囲に含まれる場合、自ノード内で、データベースを検索して（ステップＳ１４）、該識別子に対応するデータを取得し、該データを含む応答メッセージを、クライアント１へ返送する（ステップＳ１５）。
【００６２】
次に、自ノードの分担範囲に含まれない場合、増加方向側隣接ノードの分担範囲に含まれるものかどうか調べる（ステップＳ１６）。もし、増加方向側隣接ノードの分担範囲に含まれるならば、上記問い合せメッセージを、増加方向側隣接ノードへ転送する（ステップＳ１７）。ここでは、上記ハッシュ値ｈｍが自ノードに対応するハッシュ値ｎと、ｎのサクセッサーとの間に存在するのであれば、ｎのサクセッサーに問い合せメッセージを転送する。  
それ以外の場合には、フィンガーテーブル３５を参照して、転送先ノードを選択し（ステップＳ１８）、選択した転送先ノードへ、問い合せメッセージを転送する（ステップＳ１９）。
【００６３】
ここでは、上記ハッシュ値ｈｍと、フィンガーテーブル３５の各エントリｉ（＝ｎｅｘｔ）に対するｔａｒｇｅｔ［ｉ］とを比較して、ｔａｒｇｅｔ［ｉ］がｈｍよりもハッシュ空間の順方向（ハッシュ値が増加する方向）に対して自ノード側（ハッシュ値が減少する側）である最大のｉ（すなわち、ｎからハッシュ空間を順方向に辿ってｈｍに至る範囲内で最大のｉ）を探し、見付かった最大のｉに対応するフィンガーテーブル３５のエントリｉに記入されたＤＨＴノードへ、メッセージを転送する。
【００６４】
なお、上記のアルゴリズムを用いる場合、ｔａｒｇｅｔ［ｉ］と各ＤＨＴノードのハッシュ空間上の位置との距離は、ハッシュ空間を順方向に考えたときに、ｎからｔａｒｇｅｔ［ｉ］に至る空間に存在するＤＨＴノードのうちから、ｔａｒｇｅｔ［ｉ］との間の距離を計算する（ハッシュ空間の順方向に制約）とするのがよい。
【００６５】
なお、図９のアルゴリズムは一例であり、他のアルゴリズムも実施可能である。例えば、図９のアルゴリズムでは、問い合せメッセージに含まれる識別子に係るデータを保持するＤＨＴノードが、クライアントへ応答メッセージを返送するものとしたが、最初にクライアントから問い合わせメッセージを受信したＤＨＴノードを経由して、クライアントへ応答メッセージを返送するようにしてもよい。また、クライアントとＤＨＴノードとの間の問い合せメッセージのフォーマットと、ＤＨＴノード間の問い合せメッセージのフォーマットが異なるものであってもよい。
【００６６】
次に、本分散ハッシュテーブルシステムを、電子タグを利用した個品流通管理・トレーサビリティシステムの構築に利用する場合について説明する。
【００６７】
一般に、個品ごとに付与されるＩＤは、会社ＩＤ・商品種別ＩＤ・個品ＩＤの３階層からなる。
【００６８】
図１０に、個品毎に付与されるＩＤの一例として、ＥＰＣｇｌｏｂａｌにおけるＧＩＤ−９６（EPCglobal. EPC tag data standards version 1.3. EPCglobal Ratified Specification, March 2006.）を示す。
【００６９】
このようなＩＤにタグ付けられた大量の個品の情報を、安価かつスケーラブルに管理するためにＤＨＴを用いることが考えられる。しかし、商品毎にトレーサビリティシステムに要求されるサービス品質とかけられるコストは異なるため、単一のＤＨＴではこれら全てをカバーすることは難しい。そのため、例えば会社毎、商品種別毎にＤＨＴを割り当て、あるいは、ｆａｍｐ毎にＤＨＴを割り当て、それらで個品ＩＤまで含めたＩＤと、それに対応する情報を管理する。
【００７０】
この場合、個々のＤＨＴはそれぞれの企業が顧客に提供するサービスであり、品質とコストのトレードオフは企業が決定したい。しかし、ＤＨＴでもっとも実証されているアルゴリズムの一つである従来のＣｈｏｒｄを用いた場合、主にＦｉｎｇｅｒのアルゴリズムが固定されていることが理由で、このトレードオフは制御できない。
【００７１】
そこで、トレーサビリティシステムにおける個々のＤＨＴにおいて、これまで説明してきたＤＨＴシステムを実施することで、このトレードオフが制御可能になる。具体的には、アプリケーションは要求から求められるｆａｍｐを設定し、本実施形態のアルゴリズムに従いフィンガーテーブルを構築する。これにより、トレードオフが制御できるようになる。例えば、トレーサビリティシステムを使う場合は基本的に事故が発生したとき、という意味で、一般的な食品の情報は通常は低コストで維持可能となるように設定（ｆａｍｐ＝１．０程度）したＤＨＴで管理することが考えられる。一方で、ブランド食品など、トレーサビリティによる与信が商品価値の向上に役立つ場合は、システムの反応速度を向上させるために、通信コストとしては高コストである一方、問い合わせには短時間で応答できる（ｆａｍｐ＝４．０程度）ＤＨＴを設定し、その上での情報管理を行ってもよい。
【００７２】
ところで、図５のフローチャートにおいて、ｔａｒｇｅｔ＝ｎ＋２ｒとあるが、この２ｒに相当する部分の計算方法にはいくつかのバリエーションが考えられる。
【００７３】
例えば、何らかの操作により、ｔａｒｇｅｔ＝ｎ＋ｂｒとし、ｂとｒの両方を制御してもよい。あるいは、ｒのかわりに０以上の適当な範囲の整数値ｉを利用し、ｔａｒｇｅｔ＝ｎ＋ｂｉとしても良い。この場合、適当な範囲とは、ｂｉあるいはｂｒが２ｍ（ｍはＣｈｏｒｄで用いるハッシュ関数のビット幅）を超えない範囲、すなわちハッシュ空間を一周しない範囲となる。例えば、ｔａｒｇｅｔ＝ｎ＋ｂｉの式を利用し、かつｍ＝１６０の場合、ｂ＝１．５とするならば、ｉは４３７までである。
【００７４】
また、一般に、計算機における浮動小数点数の計算はコストが高い。このコストを避けたい場合は、ｔａｒｇｅｔの算出において利用するパラメータを、固定小数点あるいは２進数における分数で計算可能な組み合わせに限定するようにしてもよい。２ｒ、あるいは、ｂｉ、あるいは、ｂｒの組み合わせを用意し、利用者はその組み合わせの中から目的に適うものを選択するようにしてもよい。
【００７５】
さらに、事前にｔａｒｇｅｔの計算に必要な２ｒあるいはｂｉあるいはｂｒに相当するテーブルを用意し、必要に応じてルックアップするようにしても構わない。この場合、そのためのメモリを実装する必要があるが、計算はローコストで行える。
【００７６】
以下では、パラメータを動的に適応させる場合について説明する。
【００７７】
実際には、ある商品に対する需要は変動し、需要が高い時期にはたとえＣｈｏｒｄネットワークの維持にかかるトラフィック量が増大したとしても、問い合わせにかかる再帰段数を減少させたほうがトラフィックの総量を減少させることができるなどといった場合が考えられる。こういった場合に備えて、ＤＨＴの各ノードは、トレードオフを決定するパラメータ（例えば、ｆａｍｐ）を動的に変更する機構を導入することもできる。
【００７８】
ただし、ＤＨＴにおいては、通信は常に局所的であり、全体のトラフィックがどのように発生しているかを知ることは困難である。従って、個々のノードは自身に到着した問い合わせの頻度と、推測した現在のネットワークの密度から、ｆａｍｐを増加させるか減少させるかを判断することになる。
【００７９】
ネットワークの密度から、ｆａｍｐを変更させたときに実際に利用されることになるフィンガーテーブルの数が推測できる。ＤＨＴ維持のためのトラフィックは利用するフィンガーテーブルの数に比例するため、これでＤＨＴ維持のトラフィックの変動が推測できたことになる。
【００８０】
また、ｆａｍｐを変更した際に、問い合わせが何度転送されるか（再帰段数）も、同じアルゴリズムであれば同じ傾向となるため、事前に測定や解析などによって求めたモデルにｆａｍｐを代入することで求めることができる。問い合わせ１つあたりに消費するトラフィック量は、再帰の方式にも依るが、問い合わせと応答がほぼ同等サイズのメッセージであれば、再帰段数にほぼ比例する。従って、これと問い合わせ頻度から、ＤＨＴサービスのトラフィックの変動が推測できたことになる。
【００８１】
この推測値から、もっともコストの低いｆａｍｐを算出し選択することができる。また、サービスの品質保証を行う場合は、ｆａｍｐの最低値を定めて、最低値を下まわらない範囲でのｆａｍｐを利用することができる。さらに、上限値を定めて、これを超えた場合は管理者に警報を出すことでシステムの過負荷を避けることもできる。これは、ＤＨＴの場合は適切にノードを追加すれば負荷分散可能な点による。
【００８２】
ｆａｍｐの大幅な変更はフィンガーテーブルの大幅な書き換えを招くので、実際にはｆｉｘ  ｆｉｎｇｅｒｓを走らせる度に微少な変更を逐次的に加えていくのが望ましい。
【００８３】
ｆｉｎｄ＿ｓｕｃｃの処理は古いＦｉｎｇｅｒを利用するため、その近傍（特にサクセッサー側）の検索は低コストで実現できる。従って、特にｆａｍｐを小さくする方向（Ｆｉｎｇｅｒの間隔を大きくする方向）のコストが大幅に削減できる。
【００８４】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【００８５】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００８６】
【図１】本発明の一実施形態に係る分散ハッシュテーブルシステムの構成例を示す図
【図２】同実施形態に係るＤＨＴノードの構成例を示す図
【図３】データベース３４の一例を示す図
【図４】フィンガーテーブルの一例を示す図
【図５】フィンガーテーブルに登録するＤＨＴノードを探索する手順の一例を示すフローチャート
【図６】ｆａｍｐ＝１．０の場合に得られるｔａｒｇｅｔについて説明するための図
【図７】ｆａｍｐ＝２．０の場合に得られるｔａｒｇｅｔについて説明するための図
【図８】ｆａｍｐ＝３．０の場合に得られるｔａｒｇｅｔについて説明するための図
【図９】問い合せメッセージ受信時における処理手順の一例を示すフローチャート
【図１０】個品流通管理・トレーサビリティシステムにおいて個品毎に付与されるＩＤのフォーマットの一例を示す図
【符号の説明】
【００８７】
１…クライアント、３…ＤＨＴノード、８…ネットワーク、３１…メッセージ処理部、３２…自ノード情報記憶部、３３…隣接ノード情報記憶部、３４…データベース、３５…フィンガーテーブル、３６…フィンガーテーブル管理部、３７…通信部、３６１…パラメータ設定部、３６２…計算部、３６３…ノード探索部
【図１】
2008234536.tif 000003
【図２】
2008234536.tif 000004
【図３】
2008234536.tif 000005
【図４】
2008234536.tif 000006
【図５】
2008234536.tif 000007
【図６】
2008234536.tif 000008
【図７】
2008234536.tif 000009
【図８】
2008234536.tif 000010
【図９】
2008234536.tif 000011
【図１０】
2008234536.tif 000012