(57)【要約】【課題】オーバーレイネットワークにおいて、コンテキスト情報の範囲検索を実行する場合における検索効率を改善するとともに、データセットの追加及び削除に際して、データセットの移動回数を極小化することによってネットワークの負荷を軽減する。【解決手段】コンテキスト情報管理ノードであって、受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定手段と、前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理手段を有する。【選択図】      図１
2013025382.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上で仮想的に接続されたノードの受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定手段と、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理手段を備えることを特徴とする、コンテキスト情報管理ノード。
【請求項２】
前記判定手段は、
前記自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かの判定を、管理対象とするコンテキスト情報の下限値と上限値が定義された管理テーブルを参照した結果を基に判定することを特徴とする請求項１記載のコンテキスト情報管理ノード。
【請求項３】
前記判定手段は、
前記管理テーブルを更新する更新手段を含むことを特徴とする請求項２記載のコンテキスト情報管理ノード。
【請求項４】
前記判定手段において、前記更新手段は、
前記管理テーブルに定義されたところの、前記管理対象とするコンテキスト情報の下限値及び上限値を、独立して更新可能であることを特徴とする請求項３記載のコンテキスト情報管理ノード。
【請求項５】
前記処理手段は、
前記自ノードが保持しているコンテキスト情報量を基にした乱数値と、所定値とを比較し、当該乱数値が該所定値以下の場合、自ノード及び隣接ノードに対して、複数のコンテキスト情報に関する処理を、一括して実行する手段を含むことを特徴とする請求項１及至４のいずれかに記載のコンテキスト情報管理ノード。
【請求項６】
前記所定値は、ノード毎の固有値として予め定められた値であることを特徴とする請求項５記載のコンテキスト情報管理ノード。
【請求項７】
前記処理手段は、
前記複数のコンテキスト情報に関する処理を一括して実行するに際して、コマンドを利用することを特徴とする、請求項５記載のコンテキスト情報管理ノード。
【請求項８】
コンテキスト情報管理ノードの動作制御のためのコンピュータ・プログラムであって、そのコンピュータ・プログラムにより、コンピュータを、
受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定機能と、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理機能として動作させる
ことを特徴とするコンピュータ・プログラム。
【請求項９】
請求項１及至８のいずれかに記載のノードが仮想的にリング状に複数配置されてなるコンテキスト情報管理システム。
【請求項１０】
受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定し、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行することを特徴とするコンテキスト情報管理ノードの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばデータベースシステムにおいて、コンテキスト（コンテクストとも称される）情報の管理を行う技術分野に関する。
【背景技術】
【０００２】
例えば、センサーや携帯端末などから発生するコンテキスト情報を処理する基盤技術として、コンテキスト情報管理システムがある。コンテキスト情報とは、特定の主体(例えば、人や商品など)に関する状態や状況などを表す情報である。コンテキスト情報管理システムは、例えば、センサーや携帯端末などが検出した温度や位置などのコンテキスト情報を保持するとともに、それら保持した情報の中から、所望の活用目的に対応する情報に絞り込むことなどに使用するシステムである。
【０００３】
これらセンサーや携帯端末などは、例えば、特許文献１（特表２００９−５１７９２１：ピアツーピア・オーバーレイ・ネットワークにおける同報通信メッセージング）に開示される、オーバーレイネットワークのノードとなる。オーバーレイネットワークとは、１つ以上のタイプの下位層の物理ネットワーク接続によって、互いに接続された複数のノードに課せられた、論理又は仮想ネットワークの組織であると定義される。それらのノードは、下位層の物理的ネットワークにおける、１つ以上の経路に一致し得るものとも定義される。
【０００４】
また、各ノードには非特許文献１により示される、アルゴリズム“Ｃｈｏｒｄ”（コード）などの技術において、オーバーレイネットワークの基で、時計回りの順にノードＩＤ（識別子）が割り当てられる。つまり、あるノードにとって時計回りの隣に位置するノードは、“隣接ノード”と定義される（以下、本願において同様）。
【０００５】
コンテキスト情報を検出するセンサーや携帯端末などの数は、ネットワークサービスの普及やきめ細かさにともない増加する。それらのセンサーや携帯端末などの数の増加に伴い、管理対象となるコンテキスト情報の数も増加する。そしてこのような状況において、コンテキスト情報管理システムは、通信ネットワーク（以下、単に「ネットワーク」と略称する）への負荷を軽減する必要がある。
【０００６】
また、温度やＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）による位置情報のように、温度や位置情報センサーの検出値が連続値となる場合がある。このようなセンサーを扱うコンテキスト情報管理システムは、例えば、温度が２℃（摂氏２度）から５℃の間のコンテキスト情報を検索するなどの処理のように、範囲を定めた検索への対応が必要である。以降、本願では、このような範囲を定めた検索処理を、“範囲検索”と称する場合がある。
【０００７】
複数のノードに分散して配置されたキーと値とのペア（以下、単に「データセット」と称する場合がある）の範囲検索を容易にする技術として、スキップグラフ（Ｓｋｉｐ  ｇｒａｐｈ）がある。スキップグラフは、キーと値とのペアを保持するとともに、あるキーが与えられるのに応じて、複数のノードが保持しているデータセットの中から、そのキーと一致する値を容易に検索するための技術である。
【０００８】
係るスキップグラフにおける範囲検索では、ノードに与えるべきキーに順序づけが可能な場合、２つのキーａ、ｂ（ａ＜ｂ）が与えられた際に、保持しているデータセットの中から、ａ以上ｂ未満のキーを持つ全てのキーと、そのキーとペアをなす値とを検索することができる。
【０００９】
また、係るスキップグラフでは、新たなキーと値とのペアをスキップグラフに追加したり、既に保持しているデータセットの中から、指定されたキーと一致するキーと値とを削除することができる。
【００１０】
更に、１つのノードに複数のデータセットを保持することができるというスキップグラフを提案する技術として、Ｒａｉｎｂｏｗ  Ｓｋｉｐ  ｇｒａｐｈ（非特許文献２）やＳｋｉｐ  Ｂ−Ｔｒｅｅｓ（非特許文献３）がある。
【００１１】
これらの技術は、Ｂツリー（Ｂａｌａｎｃｅｄ  Ｔｒｅｅ）をベースにしたデータ構造を使用している。係るスキップグラフでは、１つのノードが保持するデータセット数の最大値ｄを定めておき、データセット数をｄ／２以上ｄ以下に規定することにより、ノード間の保持データ量のバランスを取る。
【００１２】
つまり、スキップグラフにおける保持データの削除では、保持データの数がｄ／２未満になった際に、隣り合う２つのノード間において、保持データの移動を行い、両方のノードの保持データの数を同じにする。このような処理を繰り返した結果、自ノードが保持するデータセットの数がｄ／２−１、隣接ノードが保持するデータセットの数がｄ／２になった際に、自ノードの保持データを隣接ノードに移動し、自ノードが保持していたデータを削除する。
【００１３】
上述したノード間の保持データの移動は、ネットワークを利用して行い、ノードが削除されるまで、保持データの移動が何度も発生することになる。つまり、非特許文献２及び３に記載された、スキップグラフにおいては、キーと値とのペアの追加や削除が行われる場合に、ノード間の保持データ量にバラツキが発生するため、保持データ量のバランスを保つためのデータセットの移動が起こり易いという問題がある。特にこの問題は、ノードを削除する場合に、小さなサイズのデータセットの移動が何度も起こることによって顕著となる。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特表２００９−５１７９２１号公報
【非特許文献】
【００１５】
【非特許文献１】Ion Stoica;Robert Morris,David Karger,M.Frans Kaashoek,and Hari Balakrishnan,”Chord:A Scalable Peer-to-peer Lookup Service for Internet Applications”,ACM SIGCOMM 2001,(2001)
【非特許文献２】I.Abraham,J.Aspnes, and J.Yuan,”Skip B-trees,”in Principles of Distributed Systems; 9th International Conference,OPODIS 2005;Pisa,Italy;December 2005; Revised Selected Papers,vol.3974 of Lecture Notes in Computer Science,pp. 366380,Dec.2005.
【非特許文献３】M.T.Goodrich,M.J.Nelson,and J.Z.Sun,“The rainbow skip graph:a fault-tolerant constant-degree distributed data structure,”inProc.17th Symp. Discrete Algorithms,pp.384393,ACM and SIAM,Jan.2006.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本発明は、上述した課題を解決するためになされた。本発明は、コンテキスト情報を範囲検索する場合における検索効率を改善するとともに、データセットの追加及び削除に際して、データセットの移動回数を極小化することによって、ネットワークの負荷を軽減することが可能なコンテキスト情報管理ノード及びコンテキスト情報管理システムなどの提供を主たる目的とする。
【課題を解決するための手段】
【００１７】
上記の目的を達成するため、本発明のコンテキスト情報管理ノードは、以下の構成を備えることを特徴とする。
【００１８】
すなわち、係るコンテキスト情報管理ノードは、受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定手段と
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理手段を備えることを特徴とする。
【００１９】
また、本発明の同目的を達成する他の見地は、上記構成を有するノードが仮想的にリング状に複数配置されてなるコンテキスト情報管理システムである。
【００２０】
なお、同目的は、上記の各構成を有するコンテキスト情報管理ノードに対応する方法によっても達成される。
【００２１】
また、同目的は、上記の各構成を有するコンテキスト情報管理ノード又はその制御方法を、コンピュータによって実現するコンピュータ・プログラム、及びコンピュータ・プログラムが格納されている、コンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００２２】
上記の本発明によれば、コンテキスト情報を範囲検索する場合における検索効率を改善するとともに、データセットの追加又は削除に際して、データセットの移動回数を極小化することによって、ネットワークの負荷軽減が可能となる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係るコンテキスト情報管理システムのノードを概念的に示すブロック図である。
【図２】本発明の実施形態に係るコンテキスト情報管理システムの構成を示すブロック図である。
【図３】本発明の実施形態に係るコンテキスト情報管理システムにおいて、各種コマンドのフォーマットを説明する図である。
【図４】本発明の実施形態に係るコンテキスト情報管理システムにおいて、ノードが各種コマンドを判定する処理手順を示すフローチャートである。
【図５】本発明の実施形態に係るコンテキスト情報管理システムにおいて、保持データを検索するコマンドの処理手順を示すフローチャートである。
【図６】本発明の実施形態に係るコンテキスト情報管理システムにおいて、データセットを挿入するコマンドの処理手順を示すフローチャートである。
【図７】本発明の実施形態に係るコンテキスト情報管理システムにおいて、保持データを削除するコマンドの処理手順を示すフローチャートである。
【図８】本発明の実施形態に係るコンテキスト情報管理システムを適用可能な、実施例としてのネットワーク構成を概念的に示すブロック図である。
【図９】オーバーレイネットワークを構成するノードへのＩＤ付与を概念的に示すブロック図である。
【図１０】本発明の実施形態において、コンテキスト情報管理システムを構成するノード１０１のハードウエアの構成を概念的に示すブロック図である。
【発明を実施するための最良の形態】
【００２４】
本発明を実施するための最良の形態について、図面を参照して説明する。なお、以下に説明するコンテキスト情報管理システムのノードは、温度や位置などのセンサー機能を保有することを妨げない。
【００２５】
はじめに、本実施形態におけるコンテキスト情報管理システムを構成するノードについて説明する。図１は、本発明の実施形態に係る、コンテキスト情報管理システムのノードを概念的に示すブロック図である。図１を参照すると、本発明の最良の実施形態におけるコンテキスト情報管理システムのノードは、ノード１０１と、データ格納部９とを含む。
【００２６】
また、ノード１０１は、リクエスト情報が自ノード１０１を対象にする情報であるか否かを判定する判定部１１０と、単一のデータセットを処理するか、複数のデータセットを処理するかの制御をする処理部１１１とを含む、情報処理装置である。データ格納部９は、ノード１０１が管理対象とするコンテキスト情報を格納する、記憶装置である。なお、本実施形態においても、ノード１０１は、非特許文献１に示される、自ノードを識別可能な固有ＩＤを有する。ここで、単一のデータセットとは、キーと値とによって構成される、１つのペアをなすデータセットを表す（以下、同様）。
【００２７】
上記構成を備えるノード１０１において、判定部１１０は、リクエスト情報が、自ノード１０１を対象にする場合は、処理部１１１へ、受信したリクエスト情報を送る。隣接ノード１０１などを対象にする場合に、判定部１１０は、隣接ノード１０１などへ受信したリクエスト情報を転送する。
【００２８】
処理部１１１は、受信したリクエスト情報を参照し、参照結果に基づいて単一のデータセットを処理する場合は、自ノード１０１のデータ格納部９に対して、例えば、データ検索や挿入や削除などを行う。一方、処理部１１１は、受信したリクエスト情報を参照した結果、複数のデータセットを一括して処理する場合は、自ノード１０１のデータ格納部９と隣接ノード１０１のデータ格納部９に対して、複数のデータセットの挿入や削除などを一括して行う。
【００２９】
次に、図１に記載したノード１０１を基本構成とする、コンテキスト情報管理システムについて説明する。図２は、本発明の実施形態に係る、コンテキスト情報管理システムの構成を示すブロック図である。図２を参照すると、本発明の最良の実施形態におけるコンテキスト情報管理システムは、複数のノード１０１、ノードリスト保持部１０４、ノードプール管理部１０３、スイッチ１０２、そしてデータ格納部９とを含む。
【００３０】
すなわち、ノード１０１は、コンテキスト情報を保持及び処理をする情報処理装置である。ノードリスト保持部１０４は、ノード１０１の活性及び非活性の状態を記録する、記憶装置である。ノードプール管理部１０３は、ノードリスト保持部１０４を管理する、制御装置である。スイッチ１０２は、ノード１０１とノードプール管理部１０３との情報通信を制御するとともに、例えば、特許文献１に記載されているような、オーバーレイネットワークとの通信を制御する通信装置である。そして、データ格納部９は、ノード１０１が管理対象とするコンテキスト情報を格納する、記憶装置である。
【００３１】
上記構成におけるノード１０１と図１とを対比すると、図１の判定部１１０は、ノード１０１の受信部１、コマンドキー判定部２、ノードキー保持部６とにより構成される。そして、ノード１０１の受信部１は、オーバーレイネッワーク１０００からのリクエスト情報を受信する、受信機である。コマンドキー判定部２は、自ノード１０１へのリクエスト情報か否かの該非判定を行う、判定機である。ノードキー保持部６は、ノードキーと称する管理テーブルを保持する、記憶装置である。ここで、ノードキーとは、ノード１０１が保持対象とするキーの下限値及び上限値を含む管理テーブルを表す（以下、同様）。
【００３２】
更に、図１の処理部１１１は、ノード１０１のコマンド処理部４、検索部１０、挿入部１１、乱数発生部１２、参加部１３、削除部１４、マージ処理部１５、データ処理部８とにより構成される。そして、ノード１０１のコマンド処理部４は、ノード１０１へのコマンドを判定し、各コマンド処理機へ送る、判定機である。検索部１０は、検索コマンドを実行するためのコマンド処理機である。挿入部１１は、乱数発生部１２及び参加部１３とともに、挿入コマンドを実行するためのコマンド処理機である。削除部１４は、マージ処理部１５とともに、削除コマンドを実行するためのコマンド処理機である。また、データ処理部８は、各コマンド処理機の要求に従い、データ格納部９へのデータセットの格納や読出しをしたり、隣接ノード１０１への処理コマンドを送信する、制御機である。
【００３３】
また、図１に不図示のノード１０１のコマンドルータ部３は、ルーティングテーブル７の保持情報の管理と隣接ノード１０１との通信をする、制御機である。ルーティングテーブル７は、隣接ノード１０１と非特許文献１などで定義されるノードＩＤとを関連付けて保持するテーブルである。
【００３４】
上記構成において、コマンドキー判定部２は、オーバーレイネットワーク１０００からのリクエスト情報を受信部１を介して受信する。コマンドキー判定部２は、自ノード１０１へのリクエスト情報か否かの該非判定をノードキー保持部６が保持するノードキーと照合することによって行う。自ノード１０１へのリクエスト情報の場合、コマンドキー判定部２は、コマンド処理部４へ当該リクエスト情報を送る。
【００３５】
隣接ノード１０１へのリクエスト情報の場合、コマンドキー判定部２は、コマンドルータ３を介して、予め設定された隣接ノードのＩＤをルーティングテーブル７より取得するとともに、取得した隣接ノードＩＤに対応する隣接ノード１０１に対して、オーバーレイネットワーク１０００からの当該リクエスト情報を、自ノード１０１の送信部５を介して転送する。
【００３６】
受信したリクエスト情報が、自ノード１０１宛ての場合、コマンド処理部４は、当該コマンドの種別を判定する。すなわち、コマンド処理部４は、そのコマンドが挿入コマンド、検索コマンド、削除コマンド、参加コマンド、或いはマージコマンドの何れを含むかの判定をする。そして、コマンド処理部４は、挿入コマンド又は参加コマンドが含まれる場合は挿入部１１に、検索コマンドが含まれる場合は検索部１０に、そして削除コマンド又はマージコマンドが含まれる場合は削除部１４に当該コマンドを送る。
【００３７】
これら各コマンドのフォーマットについては、以降の図３を参照して後述する。
【００３８】
また、受信したコマンドを参照した結果、隣接ノード１０１への複数のデータセットを一括して移動することを表す場合は、挿入部１１は、参加部１３へ当該コマンドを送る。そして、参加部１３は、データ格納部９が保持している複数のデータセットを一括して隣接ノード１０１に移動する参加コマンドを起動する。更に、受信したコマンドを参照した結果、自ノード１０１と隣接ノード１０１とが保持するデータセットをマージすることを表す場合、削除部１４は、マージ処理部１５へ当該コマンドを送る。そして、マージ処理部１５は、データ処理部８を介して、データ格納部９が保持している複数のデータセットを一括して隣接ノード１０１に移動するマージコマンドを起動する。
【００３９】
これら各コマンドの処理手順の詳細については、以降の図４及至図７を参照して後述する。
【００４０】
次に、上述した如くノード１０１が扱う各コマンドに関して詳細に説明する。図３は、本発明の実施形態に係るコンテキスト情報管理システムにおいて、ノード１０１で処理される各種コマンドのフォーマットを説明する図である。
【００４１】
図３を参照すると、本実施形態において、ノード１０１の動作を指示するためのコマンドは、挿入コマンド２０１（CMD_INSERT）、検索コマンド２０２（CMD_FIND）、削除コマンド２０３（CMD_DELETE）、参加コマンド２０４（CMD_JOIN）、そしてマージコマンド２０５（CMD_MERGE）の５種類である。
【００４２】
そして本実施形態において、挿入コマンド２０１と検索コマンド２０２と削除コマンド２０３とは、オーバーレイネットワーク１０００から各ノード１０１が受信可能なコマンドである。残る２種類のコマンドである、参加コマンド２０４及びマージコマンド２０５は、自ノード１０１と隣接ノード１０１との間で実行されるコマンドである。
【００４３】
ノード１０１は、各コマンドの種類を、図３のフォーマットに示す通り、第１のフィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照することによって区別（識別）することができる。
【００４４】
挿入コマンド２０１、検索コマンド２０２、並びに削除コマンド２０３の場合、第２のフィールド（２０１ｂ、２０２ｂ、２０３ｂ）は、挿入や検索及び削除対象のキーを表す。挿入コマンド２０１の場合は、更に挿入対象のキーとペアをなす値が、第３のフィールド（２０１ｃ）に設定されるとする。
【００４５】
参加コマンド２０４及びマージコマンド２０５の場合、第１のフィールド（２０４ａ、２０５ａ）の次の第２のフィールド（２０４ｄ、２０５ｄ）には、非特許文献１に示されているような、ノードのＩＤを隣接ノードのアドレスとして設定されるとする。次に、参加コマンド２０４及びマージコマンド２０５の場合、係る第２のフィールド（２０４ｄ、２０５ｄ）の次の第３のフィールド（２０４ｅ、２０５ｅ）には、当該フィールド以降への記載範囲となる、ノードキーが設定されるとする。そのノードキーは、図３に示すように、当該キーの下限値ａと上限値ｂとによって構成される。
【００４６】
更に、参加コマンド２０４及びマージコマンド２０５の場合、係る第３のフィールド（２０４ｅ、２０５ｅ）の後には、第４のフィールド（２０４ｆ、２０５ｆ）にキーが設定され、第５のフィールド（２０４ｇ、２０５ｇ）には値が設定されるとする。この場合においても、第４のフィールド（２０４ｆ、２０５ｆ）内のキーと、第５のフィールド（２０４ｇ、２０５ｇ）内の値とはペアをなす。そして、それ以降のフィールドにも、キーと値とによって構成されるペアが設定されることとする。したがって、本実施形態において、参加コマンド２０４及びマージコマンド２０５の場合は、それぞれ、１個以上のキーと値となるペアが配置される。
【００４７】
次に、図４を参照して、オーバーレイネットワーク１０００から受信可能な３種類のコマンド及び、ノード１０１間で通信される２種類のコマンドのノード１０１における判定方法に関して説明する。図４は、本発明の実施形態に係るコンテキスト情報管理システムにおいて、ノードが各種コマンドを判定する処理手順を示すフローチャートである。
【００４８】
すなわち、ノード１０１は、オーバーレイネットワーク１０００からのコマンドを、受信部１を介して受信する（ステップＳ３０１）。コマンドキー判定部２は、受信したコマンドを、ノードキー保持部６が保持しているノードキーを参照して、自ノード１０１が保持対象とするキーの範囲にあるかの判定をする（ステップＳ３０２）。
【００４９】
そして、自ノード１０１に対するコマンドであると判定した場合（ステップＳ３０２にてＹＥＳ判定）、コマンドキー判定部２は、受信したコマンドを、コマンド処理部４へ送る。コマンド処理部４は、受信したコマンドの第１フィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照する（ステップＳ３０４）。一方、ステップＳ３０１にて受信したコマンドが隣接ノード１０１に対するコマンドであると判定した場合（ステップＳ３０２にてＮＯ判定）、コマンドキー判定部２は、送信部５を介して、隣接ノード１０１に当該コマンドを転送する（ステップＳ３０３）。
【００５０】
ステップＳ３０４にて、受信したコマンドの第１フィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照し、挿入コマンド２０１又は参加コマンド２０４の場合（ステップＳ３０５にてＹＥＳ判定）、コマンド処理部４は、当該コマンドを挿入部１１に送る（ステップＳ３０７）。一方、ステップＳ３０５にて受信したコマンドが挿入コマンド又は参加コマンド以外と判定した場合で（ステップＳ３０５にてＮＯ判定）、且つ、受信したコマンドの第１フィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照し、検索コマンド２０２であった場合（ステップＳ３０６にてＹＥＳ判定）、コマンド処理部４は、当該コマンドを検索部１０に送る（ステップＳ３０８）。
【００５１】
一方、ステップＳ３０６にて受信したコマンドが検索コマンド以外と判定した場合（ステップＳ３０６にてＮＯ判定）、コマンド処理部４は、当該コマンドを削除部１４へ送る（ステップＳ３０９）。なお、図４において、削除コマンド２０３の判定を行うことを妨げない。
【００５２】
次に、図５を参照して、図４に示すコマンド判定処理において、検索コマンド２０２と判定した後の、処理手順を説明する。図５は、本発明の実施形態に係るコンテキスト情報管理システムにおいて、保持データを検索するコマンドの処理手順を示すフローチャートである。
【００５３】
検索部１０は、コマンド処理部４から、検索コマンド２０２を受信する（ステップＳ４０１）。検索部１０は、データ処理部８を介して、データ格納部９から検索コマンド２０２の第２フィールド（２０２ｂ）のキーに該当する値をデータ格納部９から読み出す（ステップＳ４０２）。データ処理部８は、データ格納部９から読み出した値を、検索コマンドの第２フィールド（２０２ｂ）のキーに対応した値として、送信部５を経由して、オーバーレイネットワーク１０００へ送信する（ステップＳ４０３）。
【００５４】
図６を参照して、図４において、挿入コマンド２０１又は参加コマンド２０４と判定した後の、処理手順を説明する。図６は、本発明の実施形態に係るコンテキスト情報管理システムにおいて、データセットを挿入するコマンドの処理手順を示すフローチャートである。
【００５５】
挿入部１１は、コマンド処理部４から、挿入コマンド２０１又は参加コマンド２０４を受信する（ステップＳ５０１）。挿入部１１は、受信したコマンドの第１フィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照し、挿入コマンド２０１の場合、当該コマンドを乱数発生部１２に送る（ステップＳ５０２にてＹＥＳ判定）。乱数発生部１２は、保持データ量を基に発生させた乱数値が、本システムの使用者によって、ノード１０１毎に、予め定められた固定値ｐ以上の場合、データ処理部８へ挿入コマンド２０１を送る（ステップＳ５０３にてＹＥＳ判定）。
【００５６】
データ処理部８は、受信したコマンドの第２フィールド（２０１ｂ）のキーに該当するデータ格納部９の位置に、挿入コマンド２０１の第３フィールド（２０１ｃ）の値を格納する（ステップＳ５０４）。
【００５７】
一方、ステップＳ５０３にて、保持データ量を基に発生させた乱数値がコンテキスト情報管理システムの使用者により、予め定められた固定値ｐ以下と判定した場合、挿入部１１は当該コマンドを参加部１３へ送る（ステップＳ５０３にてＮＯ判定）。そして、参加部１３は、参加コマンド２０４を生成し、データ処理部８を介してノードプール管理部１０３から空のノード１０１の割当を受ける（ステップＳ５０５）。データ処理部８は、参加コマンド２０４に従い、挿入コマンド２０１の第２フィールド（２０１ｂ）とデータ格納部９に設定したキーの上限値ｂの間のデータセットを、データ格納部９から抽出する（ステップＳ５０６）。
【００５８】
データ処理部８は、参加コマンド２０４の第２フィールド（２０４ｄ（２０）にステップＳ５０５で割当を受けた空のノード１０１のノードＩＤを、隣接ノードアドレスとして設定する。更に、データ処理部８は、参加コマンド２０４の第３フィールド（２０４ｅ）において、ノードキーをなす値として、挿入コマンド２０１の第２フィールド（２０１ｂ）を下限値aとして設定し、データ格納部９のキーの上限値ｂを空のノード１０１の上限値ｂに設定する。また、データ処理部８は、ステップＳ５０６で抽出した複数のデータセットを、参加コマンド２０４の第４フィールド（２０４ｆ）以降に設定し、送信部５を介して割当てられた空のノード１０１へ送信する（ステップＳ５０７）。
【００５９】
空のノード１０１は、参加コマンド２０４を受信する（ステップＳ５０１）。挿入部１１は、受信したコマンドが挿入コマンド２０１以外の場合（ステップＳ５０２にてＮＯ判定）、当該コマンドを参加部１３に送る。そして、参加部１３は、参加コマンド２０４の第３フィールド（２０４ｅ）のノードキーをノードキー保持部６にコマンド処理部４を介して格納する（ステップＳ５０８）。
【００６０】
また、空のノード１０１の参加部１３は、データ処理部８を介して参加コマンド２０４の第４フィールド（２０４ｆ）以降に収容した複数のデータセットをデータ格納部９に格納する（ステップＳ５０９）。
【００６１】
そして、空のノード１０１は、参加コマンド２０４によるデータセットの移動を完了したことを自ノード１０１へ通知する（ステップＳ５１０）。自ノード１０１のデータ処理部８は、ステップＳ５０６で抽出したデータセットをデータ保持部９から削除する（ステップＳ５１１）。なお、空のノード１０１のアドレスを、データ処理部８以外で参加コマンド２０４に埋め込むことを妨げない。
【００６２】
図７を参照して、図４において、削除コマンド２０３又はマージコマンド２０５と判定した後の、処理手順を説明する。図７は、本発明の実施形態に係るコンテキスト情報管理システムにおいて、保持データを削除するコマンドの処理手順を示すフローチャートである。
【００６３】
削除部１４は、コマンド処理部４から、削除コマンド２０３又はマージコマンド２０５を受信する（ステップＳ６０１）。削除部１４は、受信したコマンドの第１フィールド（２０１ａ、２０２ａ、２０３ａ、２０４ａ、２０５ａ）を参照し、削除コマンド２０３の場合（ステップＳ６０２にてＹＥＳ判定）、削除コマンド２０３の第２フィールド（２０３ｂ）が、自ノード１０１のキーの下限値又はキーの上限値に一致するか否かの判定を、コマンドキー判定部２を介して行う（ステップＳ６０３）。
【００６４】
ステップＳ６０３にてＮＯ判定の場合、削除部１４は、データ処理部８を介してデータ格納部９の、削除コマンド２０３の第２フィールド（２０３ｂ）のキーと一致する、データセットを削除する（ステップＳ６０４）。
【００６５】
そして、ステップＳ６０３にてＹＥＳ判定の場合、削除部１４は、マージ処理部１５に当該コマンドを送り、マージ処理部１５にてマージコマンド２０５を生成する。マージ処理部１５は、データ処理部８を介してデータ格納部９の下限値又は上限値を除くデータセットを抽出する（ステップＳ６０５）。
【００６６】
マージ処理部１５は、コマンドルータ３を介して予め保持された隣接ノード１０１のノードＩＤを隣接ノード１０１のアドレスとして、ルーティングテーブル７から入手する。データ処理部８は、マージ処理部１５から受信したマージコマンド２０５の第２フィールド（２０５ｄ）に隣接ノードアドレスを設定し、第３フィールド（２０５ｅ）に自ノード１０１の下限値及び上限値を設定する。そして、データ処理部８は、ステップＳ６０５で抽出した複数のデータセットを、マージコマンド２０５の第４フィールド（２０５ｆ）及び第５フィールド（２０５ｇ）以降に設定し、送信部５を介して隣接ノード１０１へマージコマンド２０５を送信する（ステップＳ６０６）。
【００６７】
そして、隣接ノード１０１は、マージコマンド２０５を受信する（ステップＳ６０１）。ステップＳ６０２でＮＯ判定の場合、隣接ノード１０１のコマンド処理部４は、受信したマージコマンド２０５の第３フィールド（２０５ｅ）と、ノードキー保持部６が保持するキーの下限値及び上限値を比較する。このコマンド処理部４は、コマンドキー判定部２を用いて、当該隣接ノード１０１のキー保持可能範囲が最大になるように、比較した結果を用いて、ノードキー保持部６の下限値又は上限値を更新する（ステップＳ６０７）。
【００６８】
隣接ノード１０１のマージ処理部１５は、削除部１４を介してマージコマンド２０５を受信し、当該コマンドの第４フィールド（２０５ｆ）以降の複数のデータセットを、データ処理部８を用いてデータ格納部９に保存する（ステップＳ６０８）。
【００６９】
隣接ノード１０１のデータ処理部８は、当該送信部５を介してステップＳ６０８に対するデータセットの保存が終了したことを自ノード１０１のデータ処理部８へ通知する（ステップＳ６０９）。そして、自ノード１０１のデータ処理部８は、データ保持部９のデータ全てを削除する（ステップＳ６１０）。更に、データ処理部８は、ノードプール管理部１０３を介して、自ノード１０１を不活性ノード１０１として、ノードリスト保持部１０４の情報を更新する（ステップＳ６１１）
なお、本実施形態では、ルーティングテーブル７が、隣接するノードのアドレスだけを保持する構成を説明したが、係る構成には限定されない。すなわち、ネットワーク中の１つ以上のノードのアドレスを保持するルーティングテーブルを利用することで、スキップグラフを構成してもよい。
【００７０】
以上説明した本実施形態によれば、オーバーレイネットワークにおいて、コンテキスト情報の範囲検索を実行する場合における、検索効率を改善するとともに、データの追加及び削除に際して、データの移動回数を極小化することによってネットワークの負荷軽減が可能となる。
【００７１】
その理由は、本実施形態に係るコンテキスト情報管理システムにおいては、コマンドキー判定部２に、ノード１０１が保持可能なキーの下限値及び上限値（ノードキー）という範囲を定義することにより、自ノード１０１へのリクエスト情報の該非判定を行う、というシステム構成により、検索効率を改善できるからである。また、本実施形態に係るコンテキスト情報管理システムにおいては、コンテキスト情報管理システムの利用者が予め定めた固定値と比較して、乱数発生部１２で発生した乱数値が小さい場合、隣接ノード１０１への複数のデータセットを一括して移動する、というシステム構成により、データセットの追加及び削除に際して、データセットの移動回数を極小化することができるからである。
【００７２】
（実施例）
次に、上述した実施形態の具体的な実施例を説明する。図８は、本発明の実施形態に係るコンテキスト情報管理システムを適用可能な、実施例としてのネットワーク構成を概念的に示すブロック図である。
【００７３】
図８を参照すると、本実施例におけるコンテキスト情報管理システムは、例えば特許文献１に開示されている、オーバーレイネットワークなどと同様に、物理ネットワーク１００１上に仮想的に構成されたオーバーレイネットワーク１０００と、複数のノード１０１ａからノード１０１ｅとを含む。複数のノード１０１ａからノード１０１ｅはオーバレイネットワーク１０００上で繋がっている。なお、図８においては、ノード１０１が５種記載されているが、５種に限定されるものではない。また、図８において、ノード１０１ａからノード１０１ｅは、物理的な機器を表しているが、特許文献１で定義されるように、物理的なノード１０１に複数の仮想ノード１０１を含むと解釈してもよい。
【００７４】
図９は、オーバーレイネットワークを構成するノードへのＩＤ付与を概念的に示すブロック図である。すなわち、図９は、本実施例におけるオーバーレイネットワーク１０００上に接続される、ノード１０１のＩＤ付与に係り、ノードＩＤの付与順を説明するものである。オーバレイネットワーク１０００上のノードＩＤ８０１の順は、例えば、非特許文献１に示されているように、ネットワーク上で時計回りに付与することができる。図９に示す例では、３ビットのＩＤを用いて８種のノードについて、時計回りにノードＩＤ８０１を付与する状態を示している。
【００７５】
次に、上述した実施形態に係るノード１０１を単体の情報処理装置に実装する場合のハードウエア構成について例示的に説明する。図１０は、本発明の実施形態において、コンテキスト情報管理システムを構成するノード１０１のハードウエアの構成を概念的に示すブロック図である。
【００７６】
図１０を参照すると、ノード１０１を構成する情報処理装置は、ＣＰＵ（Ｃｎｅｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９０１、通信インターフェース９０４、メモリ９０２、記憶装置９０３、入力装置９０５、出力装置９０６、そしてこれらの各構成を接続するバス９０７とを有する。
【００７７】
通信インターフェース９０４には、外部装置と通信可能な現在では一般的な通信ユニットを採用することができる。メモリ９０２は、不図示の揮発性メモリと不揮発性メモリとを含む。記憶装置９０３は、例えば光ディスク、フレキシブルディスク、磁気光ディスク、外付けハードディスク、半導体メモリ、ハードディスクなどの、コンピュータ・プログラムや各種データを格納することができる不揮発性のストレージデバイスである。記憶装置９０３は、例えば、インターフェースを変換するための変換ルールを格納しても良い。
【００７８】
入力装置９０５は、センサーや温度監視装置、キーボードやマウスなどのポインティングデバイスなどである。そして、出力装置９０６は、ディスプレイや印刷装置などである。
【００７９】
ＣＰＵ９０１は、オペレーティングシステム（ＯＳ）を実行することにより、ノード１０１全体を制御する。また、ＣＰＵ９０１は、そのＯＳ実行中に、記憶装置９０３などから読み出したコンピュータ・プログラムやデータに従って、上述した実施形態において、各フローチャート（図４及至図７）を参照して説明した各種の処理（機能）を実現する。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコード或いはコードが記録されたところの、コンピュータ読み取り可能な記録媒体によって構成される。
【００８０】
なお、コンピュータ・プログラムは、通信インターフェース９０４を介して外部装置から入手してもよい。
【００８１】
上述した図１０の情報処理装置の構成は、図１及び図２に機能単位で示したノード１０１の動作を実現するハードウエア環境の例示である。すなわち、図１及び図２に示した機能ブロックは、ハードウエア及びソフトウエアの任意の組合せによって実現される。
【００８２】
図１０を参照して上述した実施例では、説明の便宜上、１台の情報処理装置が１つのノード１０１を構成する場合について説明した。しかしながら、本発明は係る構成には限定されない。すなわち、本発明は、物理的に結合された一つの装置により実現されてもよいし、物理的に二つ以上の装置を有線又は無線で接続して、これら複数の装置により実現されてもよい。更に、少なくとも１台の情報処理装置において複数のノード１０１を仮想的に実行する仮想マシン環境を利用して、上述した実施形態に係るコンテキスト情報管理システムを実現してもよい。
【００８３】
以上、実施形態及び実施例を参照して本発明を説明したが、本発明は以上の実施形態や実施例に限定されるものではない。本発明の構成や機能の詳細には、本発明のスコープ内で同業者が理解し得る様々な変更をすることができる。例えば、図２におけるノードキー保持部６やルーティングテーブル７は、必ずしもノード１０１に含まれる必要はなく、外部の独立した装置でもよい。また、スイッチ１０２やノードプール管理部１０３は、一部のノード１０１に含まれてもよい。
【００８４】
なお、上述した実施形態及びその変形例の一部又は全部は、以下の付記のようにも記載されうる。しかしながら、上述した実施形態及びその変形例により例示的に説明した本発明は、以下には限られない、すなわち、
（付記１）
ネットワーク上で仮想的に接続されたノードの受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定手段と、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理手段を備えることを特徴とする、コンテキスト情報管理ノード。
【００８５】
（付記２）
前記判定手段は、
前記自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かの判定を、管理対象とするコンテキスト情報の下限値と上限値が定義された管理テーブルを参照した結果を基に判定することを特徴とする付記１記載のコンテキスト情報管理ノード。
【００８６】
（付記３）
前記判定手段は、
前記管理テーブルを更新する更新手段を含むことを特徴とする付記２記載のコンテキスト情報管理ノード。
【００８７】
（付記４）
前記判定手段において、前記更新手段は、
前記管理テーブルに定義されたところの、前記管理対象とするコンテキスト情報の下限値及び上限値を、独立して更新可能であることを特徴とする付記３記載のコンテキスト情報管理ノード。
【００８８】
（付記５）
前記処理手段は、
前記自ノードが保持しているコンテキスト情報量を基にした乱数値と、所定値とを比較し、当該乱数値が該所定値以下の場合、自ノード及び隣接ノードに対して、複数のコンテキスト情報に関する処理を、一括して実行する手段を含むことを特徴とする付記１及至付記４のいずれかに記載のコンテキスト情報管理ノード。
【００８９】
（付記６）
前記所定値は、ノード毎の固有値として予め定められた値であることを特徴とする付記５記載のコンテキスト情報管理ノード。
【００９０】
（付記７）
前記処理手段は、
前記複数のコンテキスト情報に関する処理を一括して実行するに際して、コマンドを利用することを特徴とする、付記５記載のコンテキスト情報管理ノード。
【００９１】
（付記８）
前記コンテキスト情報管理ノードは、オーバレイネットワーク上のノードであることを特徴とする、付記５及至７記載のコンテキスト情報管理ノード。
【００９２】
（付記９）
コンテキスト情報管理ノードの動作制御のためのコンピュータ・プログラムであって、そのコンピュータ・プログラムにより、コンピュータを、
受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定する判定機能と、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行する処理機能として動作させる
ことを特徴とするコンピュータ・プログラム。
【００９３】
（付記１０）
付記９に記載したコンテキスト情報管理プログラムを記録した、コンピュータ読み取り可能な記録媒体。
【００９４】
（付記１１）
付記１及至８のいずれかに記載のノードが仮想的にリング状に複数配置されてなるコンテキスト情報管理システム。
【００９５】
（付記１２）
自ノードが保持しているコンテキスト情報を基に、複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として実行する場合に、自ノードの前記処理手段は、該隣接ノードへのデータ移動が完了してから、自ノードの移動対象データを削除することを特徴とする、付記１１記載のコンテキスト情報管理システム。
【００９６】
（付記１３）
受信した要求が、自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定し、
前記受信した要求が、自ノードの対象範囲であるときに、自ノードが保持している複数のコンテキスト情報に関する処理を、自ノード及び隣接ノードを対象として、一括して実行することを特徴とするコンテキスト情報管理ノードの制御方法。
【００９７】
（付記１４）
自ノードにて管理すべきコンテキスト情報の対象範囲であるか否かを判定するに際して、管理対象とするコンテキスト情報の下限値と上限値が定義された管理テーブルを参照した結果を基に判定する
ことを特徴とする付記１３記載のコンテキスト情報管理ノードの制御方法。
【００９８】
（付記１５）
前記管理テーブルの更新を、コンテキスト情報管理の処理と独立して実行可能とすることを特徴とする付記１３記載のコンテキスト情報管理ノードの制御方法。
【符号の説明】
【００９９】
１    受信部
２    コマンドキー判定部
３    コマンドルータ部
４    コマンド処理部
５    送信部
６    ノードキー保持部
７    ルーティングテーブル
８    データ処理部
９    データ格納部
１０    検索部
１１    挿入部
１２    乱数発生部
１３    参加部
１４    削除部
１５    マージ処理部
１０１  ノード
１０２  スイッチ
１０３  ノードプール管理部
１０４  ノードリスト保持部
１１０  判定部
１１１  処理部
２０１  挿入コマンド
２０２  検索コマンド
２０３  削除コマンド
２０４  参加コマンド
２０５  マージコマンド
８０１  ノードＩＤ
９０１  ＣＰＵ
９０２  メモリ
９０３  記憶装置
９０４  通信インターフェース
９０５  入力装置
９０６  出力装置
９０７  バス
１０００    オーバーレイネットワーク
１００１    物理ネットワーク
【図１】
2013025382.tif 000003
【図２】
2013025382.tif 000004
【図３】
2013025382.tif 000005
【図４】
2013025382.tif 000006
【図５】
2013025382.tif 000007
【図６】
2013025382.tif 000008
【図７】
2013025382.tif 000009
【図８】
2013025382.tif 000010
【図９】
2013025382.tif 000011
【図１０】
2013025382.tif 000012