(57)【要約】【課題】検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見できるコンテキストノードを提供する。【解決手段】  応答メッセージ数AMN，AMNを計数してメッセージ数差AMN-AMNを算出し、これをノンペア隣接ノードごとに繰り返してメッセージ数差の最大値Δmax1を求め、メッセージ数差の最大値Δmax1および当該最大値を与える前記一のノンペア隣接ノードAを相手ノードNへ通知し、相手ノードNから、当該相手ノードにおいて同様に求められたメッセージ数差の最大値Δmax2および当該最大値を与える一のノンペア隣接ノードBmaxの情報を取得し、各メッセージ数差の最大値Δmax1、Δmax2に基づいてトポロジ制御の要否を判定し、トポロジ制御の要判定がなされると、自ノードとノンペア隣接ノードAmaxとのリンクを切断して、その代わりにノンペア隣接ノードBmaxとのリンクを確立する。【選択図】図２
2015026951.tif 000002
【特許請求の範囲】
【請求項１】
検索用のメッセージを中継するネットワークノードにおいて、
隣接ノードの一つと隣接ノードペアを設定する隣接ノードペア設定手段と、
隣接ノードペアの相手ノードと当該相手ノード以外の一のノンペア隣接ノードとの間で送受される第１メッセージ数を計数し、これをノンペア隣接ノードごとに繰り返す第１計数手段と、
自ノードおよび前記一のノンペア隣接ノード以外の各ノンペア隣接ノードと前記一のノンペア隣接ノードとの間で送受される第２メッセージ数を計数し、これをノンペア隣接ノードごとに繰り返す第２計数手段と、
前記一のノンペア隣接ノードが同一である第１メッセージ数から第２メッセージ数を減じてメッセージ数差を算出し、これをノンペア隣接ノードごとに繰り返してメッセージ数差の最大値Δmax1を求める応答状況検知手段と、
前記メッセージ数差の最大値Δmax1および当該最大値を与える前記一のノンペア隣接ノードAmaxを前記相手ノードへ通知する手段と、
前記相手ノードから、当該相手ノードにおいて同様に求められたメッセージ数差の最大値Δmax2および当該最大値を与える一のノンペア隣接ノードBmaxの情報を取得する手段と、
前記各メッセージ数差の最大値Δmax1、Δmax2に基づいてトポロジ制御の要否を判定する判定手段と、
前記判定手段によりトポロジ制御の要判定がなされると、自ノードと前記一のノンペア隣接ノードAmaxとのリンクを切断して、その代わりに前記一のノンペア隣接ノードBmaxとのリンクを確立するノード交換手段とを具備したことを特徴とするネットワークノード。
【請求項２】
前記トポロジ制御の要否判定および要判定された際のノード交換が、前記隣接ノードペアの相手ノードを他の隣接ノードに変更しながら繰り返されることを特徴とする請求項１に記載のネットワークノード。
【請求項３】
前記判定手段は、前記各メッセージ数差の最大値Δmax1、Δmax2の和が所定の閾値以上であればトポロジ制御の要判定を行うことを特徴とする請求項１または２に記載のネットワークノード。
【請求項４】
前記メッセージが検索応答メッセージであることを特徴とする請求項１ないし３のいずれかに記載のネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーバーレイネットワーク上で検索元ノードが自ノードのコンテキスト値に近いコンテキスト値を有する十分な数のヒットノードを検索できるコンテキスト検索ネットワークのネットワークノードに関する。
【背景技術】
【０００２】
コンテキスト検索において、中央にサーバを持たないpeer-to-peerシステムでは、各ノード（peer）は、問い合わせを自ノードで解決できない場合、当該問い合わせを隣接するノードへ転送することによって処理する。このようなコンテキスト検索用のオーバーレイネットワークのトポロジを、コンテキスト検索に好適なトポロジに逐次変更するコンテキスト検索トポロジの制御方式が知られている。
【０００３】
非特許文献１には、コンテキスト検索の結果に基づいて、自ノードのコンテキスト値に近いコンテキスト値を有することが判明したノードへリンク接続することにより、コンテキスト検索の際のヒットノード数を増加させる技術が開示されている。
【０００４】
非特許文献２には、自ノードのコンテキスト値に近いコンテキスト値を有するノードに接続するリンクに加えて、ランダムに選択したノードに接続するリンクも設定することにより、検索対象となるコンテキスト値が広いコンテキスト検索においてもヒットノード数を増加させる技術が開示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】B. Yang and H. Garcia-Molina, "Improving Search in Peer-to-Peer Networks", Proc. in IEEE ICDCS'02.
【非特許文献２】V. Kalogeraki, D. Gunopulos, and D. Zeinalipour-Yazti, "A Local Search Mechanism for Peer-to-Peer Networks", Proc. in ACM CIKM'02.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１では、検索対象となるコンテキスト値の幅が広くなった場合、ヒットノード数を増加させることができない。
【０００７】
非特許文献２では、検索対象となるコンテキスト値の幅が多様に変化した場合、十分な数のヒットノードを発見することができない。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見できるコンテキスト検索ネットワークに好適なネットワークノードを提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、図１に示したように、検索用のメッセージを中継するネットワークノードMにおいて、隣接ノードペアM，Nを設定する手段と、隣接ノードペアの相手ノードNと当該相手ノード以外の一のノンペア隣接ノードA1との間で送受される第１メッセージ数を計数し、これをノンペア隣接ノードA1，A2，A3ごとに繰り返す手段と、自ノードMおよび前記一のノンペア隣接ノードA1以外の各ノンペア隣接ノードA2，A3と前記一のノンペア隣接ノードA1との間で送受される第２メッセージ数を計数し、これをノンペア隣接ノードごとに繰り返す手段と、前記一のノンペア隣接ノードが同一である第１メッセージ数から第２メッセージ数を減じてメッセージ数差を算出し、これをノンペア隣接ノードA1，A2，A3ごとに繰り返してメッセージ数差の最大値Δmax1を求める手段と、前記メッセージ数差の最大値Δmax1および当該最大値を与える前記一のノンペア隣接ノードAmax（例えば、A1）を相手ノードNへ通知する手段と、相手ノードNから、当該相手ノードにおいて同様に求められたメッセージ数差の最大値Δmax2および当該最大値を与える一のノンペア隣接ノードBmax（例えば、B1）の情報を取得する手段と、前記各メッセージ数差の最大値Δmax1、Δmax2に基づいてトポロジ制御の要否を判定する手段と、トポロジ制御の要判定がなされると、自ノードとノンペア隣接ノードAmaxとのリンクを切断して、その代わりにノンペア隣接ノードBmaxとのリンクを確立する手段とを具備した。
【発明の効果】
【００１０】
本発明によれば、応答メッセージの経由するリンク数、すなわち各検索元ノードからヒットノードへ至るホップ数を減じることができるので、検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見することができ、トポロジ制御の速度と安定性に関して、適切なバランスを実現することができる。
【００１１】
すなわち、各ネットワークノードにおいて、通過する応答メッセージが経由するリンク数を減少させることにより、ネットワークのトポロジを、ノードが持つコンテキスト値の差と検索ネットワーク上の距離とが対応した検索トポロジに変形させることができるため、検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見できるようになる。
【００１２】
また、トポロジ制御の要否を判定する正の閾値を適切な値に設定することにより、トポロジ制御の速度と安定性に関して、適切なバランスを実現することができる。たとえば、正の閾値を大きくするほど、トポロジ制御の速度は低下するものの、トポロジ制御の確実性が増して安定性が向上する。逆に、正の閾値を小さくするほど、トポロジ制御の確実性が減って安定性が低下するものの、トポロジ制御の速度を向上させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明が適用されるコンテキスト検索ネットワークおよびそのネットワークノードの主要部の構成を示した機能ブロック図である。
【図２】本発明における隣接ノード関係の模式図である。
【図３】本発明の動作を示したフローチャートである。
【図４】ノード交換後のトポロジを示した図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が適用されるコンテキスト検索ネットワークおよびそのネットワークノードの主要部の構成を示した機能ブロック図である。コンテキスト検索ネットワークは、物理ネットワーク上に仮想的に構築されたオーバーレイネットワークであり、各ネットワークノードは、同一または同等の構成を備えているので、ここではノードMの構成で各ネットワークノードの構成を代表する。
【００１５】
ノードMにおいて、隣接ノードペア設定部１０１は、自ノードに隣接する多数の隣接ノードの一つとの間に隣接ノードペアの関係を構築する。ここでは、ノードM，Nが隣接ノードペアであるものとして説明を続ける。
【００１６】
検索応答メッセージ転送部１０２は、検索要求メッセージを送信したノードに検索応答メッセージを転送する。メッセージ数カウント部１０３は、自ノードが検索要求元ノードである場合に受信した応答メッセージ、自ノードがヒットノードである場合に返信した応答メッセージを含めて、自ノードを通過した応答メッセージ数をカウントする。
【００１７】
前記カウント部１０３において、第１計数部１０３ａは、隣接ノードペアの相手ノードNと当該相手ノード以外の一のノンペア隣接ノードA1（隣接ノードではあるが隣接ノードペアの関係にないノード）との間で、自ノードを中継して送受される第１応答メッセージ数を計数し、これを他のノンペア隣接ノードA2，A3についても繰り返す。
【００１８】
第２計数部１０３ｂは、自ノードMおよび前記一のノンペア隣接ノードA1以外の各ノンペア隣接ノードA2，A3と前記一のノンペア隣接ノードA1との間で、自ノードを中継して送受される第２応答メッセージ数を計数し、これを他のノンペア隣接ノードA2，A3についても繰り返す。
【００１９】
応答状況検知部１０４は、一のノンペア隣接ノードが同一である第１応答メッセージ数から第２応答メッセージ数を減じてメッセージ数差を算出し、これをノンペア隣接ノードA1，A2，A3ごとに繰り返してメッセージ数差の最大値Δmax1を求める。
【００２０】
応答情報交換部１０５において、情報通知部１０５ａは、前記メッセージ数差の最大値Δmax1および当該最大値を与える前記一のノンペア隣接ノード（例えば、A1）をペアの相手ノードNへ通知する。情報取得部１０５ｂは、ペアの相手ノードNから、当該相手ノードNにおいて同様に求められたメッセージ数差の最大値Δmax2および当該最大値を与える一のノンペア隣接ノード（例えば、B1）の情報を取得する。
【００２１】
トポロジ制御判定部１０６は、前記各メッセージ数差の最大値Δmax1、Δmax2に基づいてトポロジ制御の要否を判定する。本実施形態では、各メッセージ数差の最大値Δmax1、Δmax2の和が所定の閾値以上であれば、トポロジ制御が必要と判定される。
【００２２】
ノード交換部１０７は、前記トポロジ制御判定部１０６によりトポロジ制御の要判定がなされると、自ノードMと前記メッセージ数差の最大値Δmax1を与えたノンペア隣接ノードA1とのリンクを切断して、その代わりに相手ノードNから通知された前記ノンペア隣接ノードB1とのリンクを確立する。同様に、相手ノードNのノード交換部１０７は、自ノードと前記メッセージ数差の最大値Δmax2を与えたノンペア隣接ノードB1とのリンクを切断して、その代わりに相手ノードMから通知されたノンペア隣接ノードA1とのリンクを確立する。
【００２３】
このとき、隣接ノードペアにおけるリンク先の交換が他のノードの検索に影響を与えることも考えられるが、トポロジ制御の要否を判定する正の閾値を十分大きく設定しておけば、他の隣接ノードペアにおけるリンク先の交換から受ける影響は小さくできる。すなわち、他の隣接ノードペアにおけるリンク先の交換から影響を受ける前に、自ノードペアにおいて誤ったリンク先の交換が行われることを防止できる。
【００２４】
次いで、図２に示した隣接ノード関係の模式図および図３のフローチャートを参照して本発明の一実施形態の動作について詳細に説明する。
【００２５】
図２において、ノードM，Nは隣接ノードペアであり、ノンペア隣接ノード集合aは、ノードMの隣接ノードではあるがノードMと隣接ノードペアを構成していないノード（ノンペア隣接ノードA1，A2，A3…）の集合である。注目ノンペア隣接ノードAは、ノンペア隣接ノード集合aから選択される一のノンペア隣接ノードである。
【００２６】
同様に、ノンペア隣接ノード集合bは、ノードNの隣接ノードではあるがノードNと隣接ノードペアを構成していないノード（ノンペア隣接ノードB1，B2…）の集合である。注目ノンペア隣接ノードBは、ノンペア隣接ノード集合bから選択される一のノンペア隣接ノードである。
【００２７】
本実施形態では、隣接ノードペアM，Nで同一の処理が実行されるので、ここではノードMの動作に注目して説明する。
【００２８】
ステップＳ１では、前記隣接ノードペア設定部１０１において、ノードMについて隣接ノードペアが設定される。ここでは、隣接ノードペアM，Nが設定されたものとして説明を続ける。ステップＳ２では、ノードMのノンペア隣接ノード集合aから一のノンペア隣接ノードが選択されて今回の注目ノンペア隣接ノードAに設定される。
【００２９】
ステップＳ３では、前記第１計数部１０３ａにおいて、隣接ノードペアの相手ノードNから自ノードMを中継して注目ノンペア隣接ノードAとの間で送受される応答メッセージ数AMNが求められる。ステップＳ４では、前記第２計数部１０３ｂにおいて、自ノードMおよびノンペア隣接ノード集合aと注目ノンペア隣接ノードAとの間で送受される応答メッセージ数AMNが求められる。ここで、自ノードMとノンペア隣接ノード集合aとの間で送受される応答メッセージ数は、ノードMが検索元ノード又はヒットノードである場合の応答メッセージ数である。
【００３０】
ステップＳ５では、ノンペア隣接ノード集合aに属する全てのノンペア隣接ノードが注目ノンペア隣接ノードAとして選択済みであるか否かが判断される。最初は選択済みではないと判断されるのでステップＳ２へ戻り、注目ノンペア隣接ノードAをノンペア隣接ノード集合a内の他のノンペア隣接ノードに切り替えて上記の各処理が繰り返される。
【００３１】
以上のようにして、ノンペア隣接ノード集合aの全てのノンペア隣接ノードについて、当該各ノードを注目ノンペア隣接ノードAとしたときの各応答メッセージ数AMN，AMNの計数が完了すると、ステップＳ６では、前記応答状況検知部１０４において、[AMN-AMN]の最大値[AMN-AMN]maxおよび当該最大値[AMN-AMN]maxを与える注目ノンペア隣接ノードAmaxが判定される。
【００３２】
ステップＳ７では、前記応答情報交換部１０５において、前記最大値[AMN-AMN]maxおよび当該最大値を与える注目ノンペア隣接ノードAmaxが隣接ノードペアの相手ノードNへ送信され、また当該相手ノードNにおいて同様に求められた最大値[BNM-BNM]maxおよび当該最大値を与える注目ノンペア隣接ノードBmaxが受信される。
【００３３】
ステップＳ８では、前記トポロジ制御判定部１０６において、前記ステップＳ６で算出された最大値[AMN-AMN]maxと前記ステップＳ７で隣接ノードペアの相手ノードNから受信した最大値[BNM-BNM]maxとの和が所定の正の閾値以上であるか否かが判定され、閾値以上であればステップＳ９へ進む。
【００３４】
ステップＳ９では、前記ノード交換部１０７において、前記注目ノンペア隣接ノードAmaxとのリンクが切断され前記注目ノンペア隣接ノードBmaxとのリンクが新たに確立される。なお、本実施形態では前記正の閾値が全てのノードにおいて共通なので、隣接ノードペアの相手ノードNにおいても同様な処理が同時に行われる。その結果、相手ノードNでは、注目ノンペア隣接ノードBmaxとのリンクが切断され前記注目ノンペア隣接ノードAmaxとのリンクが新たに確立される。図４は、ノード交換後のネットワークトポロジを示した図である。
【００３５】
なお、上記のノード交換では、前記閾値が正でありさえすれば検索応答メッセージのホップ数は全体として減少するものの、カウントされる応答メッセージ数には誤差が含まれている可能性がある。また、他の隣接ノードペアにおけるリンク先の交換によって、検索応答メッセージの経路が変化する場合も考えられる。このため、前記閾値はある程度大きな値にして、リンク先の交換によって検索応答メッセージのホップ数が全体として十分減少する場合にのみ、リンク先の交換が行われるようにすることが望ましい。すなわち、前記正の閾値は、トポロジ制御の速度とトポロジ制御の安定性のバランスを考慮して決定する必要がある。
【００３６】
ステップＳ１０では、ノードA，M間のリンクおよびノードB，N間のリンクを通過する応答メッセージ数をリセットし、ノードA，N間のリンクおよびノードB，M間のリンクを通過する応答メッセージ数をゼロから計数するための初期化処理が実行される。
【００３７】
ステップＳ１１では、ノードMが隣接ノードペアを構成し得る全ての隣接ノードとの隣接ノードペアについて上記の各処理が完了したか否かが判定される。完了していなければステップＳ１へ戻り、相手ノードを他の隣接ノードに交換した新たな隣接ノードペアに関して、上記の各処理が繰り返される。
【００３８】
本実施形態によれば、全体的に検索応答メッセージの所要ホップ数が減少するように、コンテキスト検索トポロジの改善が図られる。また、検索応答メッセージの転送ルートと、対応する検索要求メッセージの転送ルートは等しいので、ヒットするノードへ至る検索要求メッセージの所要ホップ数が減少し、ヒットノード数を増加させることができる。
【００３９】
さらに、本実施形態によれば、実際に要求されるコンテキスト検索に応じて、コンテキスト検索トポロジの制御を行うので、検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見することができるのみならず、検索応答メッセージ数に対する正の閾値の大きさを変化させことにより、トポロジ制御の速度と安定性に関して、適切なバランスを実現することができる。
【００４０】
さらに具体的に説明すれば、各ネットワークノードにおいて、通過する応答メッセージが経由するリンク数を減少させることにより、ネットワークのトポロジを、ノードが持つコンテキスト値の差と検索ネットワーク上の距離とが対応した検索トポロジに変形させることができるので、検索対象となるコンテキスト値の幅が多様に変化しても、十分な数のヒットノードを発見できるようになる。
【００４１】
また、トポロジ制御の要否を判定する正の閾値を適切な値に設定することにより、トポロジ制御の速度と安定性に関して、適切なバランスを実現することができる。たとえば、正の閾値を大きくするほど、トポロジ制御の速度は低下するものの、トポロジ制御の確実性が増して安定性が向上する。逆に、正の閾値を小さくするほど、トポロジ制御の確実性が減って安定性が低下するものの、トポロジ制御の速度を向上させることができる。
【符号の説明】
【００４２】
１０１…隣接ノードペア設定部，１０２…検索応答メッセージ転送部，１０３…メッセージ数カウント部，１０３ａ…第１計数部，１０３ｂ…第２計数部，１０４…応答状況検知部，１０５…応答情報交換部，１０５ａ…情報通知部，１０５ｂ…情報取得部，１０６…トポロジ制御判定部，１０７…ノード交換部
【図１】
2015026951.tif 000003
【図２】
2015026951.tif 000004
【図３】
2015026951.tif 000005
【図４】
2015026951.tif 000006