コンテキスト検索方法およびシステム
【課題】検索要求メッセージの転送数や、これに対する検索応答メッセージの転送数を効率よく動的に削減できるコンテキスト検索方法およびシステムを提供する。
【解決手段】ホップ数制限値設定部１０４は、検索要求メッセージのホップ数を制限することで検索要求メッセージの転送数を抑制するための第１および第２制限値を設定する。第１制限値E1は、ホップ数の絶対的な制限値であり、第１制限値E1を超えて検索要求メッセージが転送されることはない。第２制限値E2は、前記第１制限値E1よりも小さな値に設定されるが、検索要求メッセージを受信した検索対象ピアPdi，Ptjがコンテキスト条件を満足していると初期化される。検索要求生成部１０６は、第１制限値E1が第１許容ホップ数e1として記述され、第２制限値E2が第２許容ホップ数e2として記述され、さらに第２制限値E2およびコンテキスト検索条件の記述された検索要求メッセージを生成する。
【解決手段】ホップ数制限値設定部１０４は、検索要求メッセージのホップ数を制限することで検索要求メッセージの転送数を抑制するための第１および第２制限値を設定する。第１制限値E1は、ホップ数の絶対的な制限値であり、第１制限値E1を超えて検索要求メッセージが転送されることはない。第２制限値E2は、前記第１制限値E1よりも小さな値に設定されるが、検索要求メッセージを受信した検索対象ピアPdi，Ptjがコンテキスト条件を満足していると初期化される。検索要求生成部１０６は、第１制限値E1が第１許容ホップ数e1として記述され、第２制限値E2が第２許容ホップ数e2として記述され、さらに第２制限値E2およびコンテキスト検索条件の記述された検索要求メッセージを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテキスト検索方法およびシステムに係り、特に、コンテキスト検索のメッセージに許容ホップ数が設定されるコンテキスト検索方法およびシステムに関する。
【背景技術】
【０００２】
ピアツーピアネットワーク上でコンテキスト検索を行う検索元ピアノードが、コンテキスト検索条件の記述された検索要求メッセージを、許容ホップ数等の制約を設けてブロードキャストで送信し、この検索要求メッセージを受信したピアノードのコンテキストが検索条件を満足すると、検索元ピアノードに対して検索応答メッセージを返信するコンテキスト検索の手法が非特許文献１に開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Y. Chawathe, S. Ratnasamy, L. Breslau, and S. Shenker, "Making Gnutella-like P2P Systems Scalable", ACM SIGCOMM 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術には、以下のような技術課題があった。
(1)コンテキスト検索要求メッセージは、許容ホップ数の範囲内であればブロードキャスト転送されるので、検索要求メッセージの転送数が増加してしまう。
(2)コンテキスト検索条件を満足するピアが、検索要求メッセージに対して個別に検索応答メッセージを返信するので、検索応答メッセージの転送数が増加してしまう。
【０００５】
本発明の目的は、上記した従来技術の課題を解決し、検索要求メッセージの転送数や、これに対する検索応答メッセージの転送数を効率よく動的に削減できるコンテキスト検索方法およびシステムを提供することにある。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために、本発明は、コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索システムにおいて、以下のような手段を講じた点に特徴がある。
【０００７】
(1)検索元ピアが、検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手段と、第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手段と、検索要求メッセージを検索対象のピアへ送信する手段とを具備し、
【０００８】
検索対象の各ピアが、検索要求メッセージを受信する手段と、受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手段と、検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手段と、中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手段と、検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手段と、検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手段と、検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手段と、中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手段と、前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手段とを具備し、
【０００９】
検索元ピアがさらに、各検索対象のピアから返信される検索応答メッセージを受信する手段を具備したことを特徴とする。
【００１０】
(2)検索元ピアがさらに、検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手段と、タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手段とをさらに具備し、
【００１１】
検索対象ピアがさらに、検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手段と、検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手段と、タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手段とを具備し、
【００１２】
前記検索元ピアは、タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、以下のような効果が達成される。
【００１４】
(1)検索要求メッセージに設定された許容ホップ数が、コンテキスト検索条件を満足するピアおよびその近傍のピアでは、それ以外のピアおよびその近傍のピアよりも緩和されるので、コンテキストの一致するピア同士が近接するネットワークトポロジであれば、コンテキスト検索条件を満足するピアへ到達する可能性の高いメッセージのホップ数を、コンテキスト検索条件を満足するピアへ到達する可能性の低いメッセージのホップ数よりも長くできる。
【００１５】
(2)コンテキスト検索条件を満足するピアは、自ピアが中継した検索要求メッセージに対して返信されて自ピアで中継する各検索応答メッセージを、自ピアの検索応答メッセージと共に集約して中継するので、検索応答メッセージの転送数を削減できるようになる。
【図面の簡単な説明】
【００１６】
【図１】本発明が適用されるピアツーピアネットワークの一例を示した図である。
【図２】第１実施形態に係る検索元ピアの構成を示した機能ブロック図である。
【図３】第１実施形態に係る検索対象ピアの構成を示した機能ブロック図である。
【図４】第１実施形態における検索元ピアの動作を示したフローチャートである。
【図５】第１実施形態における各検索対象ピアの動作を示したフローチャートである。
【図６】第２実施形態に係る検索元ピアの構成を示した機能ブロック図である。
【図７】第２実施形態に係る検索対象ピアの構成を示した機能ブロック図である。
【図８】第２実施形態における検索元ピアの動作を示したフローチャートである。
【図９】第２実施形態における各検索対象ピアの動作を示したフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１７】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明が適用されるピアツーピアネットワークの一例を示した図であり、黒丸印は、コンテキスト検索条件の記述された検索要求メッセージを送信してコンテキスト検索を実行する検索元ピアPsを表している。斜線丸印は、検索条件を満足するピアPdiを表し、白丸印は、検索条件を満足しないピアPtjを表している。
【実施例２】
【００１８】
図２は、前記検索元ピアPsの主要部の構成を示した機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１９】
ホップ数制限値設定部１０４は、検索要求メッセージのホップ数を制限することで検索要求メッセージの転送数を抑制するための第１および第２制限値を設定する。第１制限値E1は、ホップ数の絶対的な制限値であり、本実施形態では、当該第１制限値E1を超えて検索要求メッセージが転送されることはない。第２制限値E2は、前記第１制限値E1よりも小さな値に設定されるが、検索要求メッセージを受信した検索対象ピアがコンテキスト条件を満足していると初期化される。当該第１および第２制限値E1，E2の機能については、後に詳述する。
【００２０】
検索条件設定部１０５は、多数の検索対象ピアの中から目的のピアを検索するためのコンテキスト検索条件Xを設定する。検索要求生成部１０６は、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージを生成する。当該検索要求メッセージは、検索要求送信部１０２から通信インターフェース１０１を介して各検索対象ピアへブロードキャストで送信される。
【００２１】
検索応答受信部１０３は、前記検索要求メッセージを受信した検索対象ピアのうち、前記コンテキスト条件を満足するピアPdiから返信される検索応答メッセージを前記通信インターフェース１０１経由で受信する。検索応答処理部１０７は、受信された検索応答メッセージに基づいて、コンテキスト検索条件を満足するピアを識別する。
【００２２】
図３は、前記検索対象ピアPdi，Ptjの主要部の構成を示した機能ブロック図であり、ここでも、本発明の説明に不要な構成は図示が省略されている。
【００２３】
検索要求受信部２０２は、前記検索元ピアPsから送信された、あるいは他の検索対象ピアにより中継された検索要求メッセージを通信インターフェース２０１経由で受信する。検索条件判定部２０６は、受信した検索要求メッセージに記述されているコンテキスト検索条件Xと自ピアのコンテキストデータベース２１０に登録されているコンテキストとを比較・照合し、自ピアがコンテキスト検索条件を満足しているか否かを判定する。
【００２４】
中継判定部２０７は、受信した検索要求メッセージを他のピアへさらに中継するか否かを、当該検索要求メッセージに記述されている第１および第２許容ホップ数e1，e2ならびに自ピアが検索条件を満足しているか否かに基づいて判定する。メッセージ破棄部２０８は、中継しないと判定された検索要求メッセージを破棄する
【００２５】
メッセージ更新部２０９は、中継する検索要求メッセージの第１許容ホップ数e1を更新（デクリメント）する更新部２０９ａ、第２許容ホップ数e2を更新（デクリメント）する更新部２０９ｂ、および第２許容ホップ数e2を初期化して第２制限値E1に戻す初期化部２０９ｃを含む。更新された検索要求メッセージは、検索要求中継部２０４から通信インターフェース２０１経由で他のピアへ中継される。検索応答中継部２０３は、前記中継した検索要求メッセージに対して返信される検索応答メッセージを中継する。検索応答返信部２０５は、自ピアがコンテキスト検索条件を満足するときに検索応答メッセージを返信する。
【００２６】
次いで、フローチャートを参照して、本発明の第１実施形態の動作を詳細に説明する。図４は、前記検索元ピアPsの動作を示したフローチャートであり、図５は、前記各検索対象ピアの動作を示したフローチャートである。
【００２７】
検索元ピアPsでは、図４のステップＳ１０１において、検索要求メッセージのホップ数を制限するための第１制限値E1および第２制限値E2が前記ホップ数制限値設定部１０４により設定される。本実施形態では、第１制限値E1として「５」が設定され、第２制限値E2として「２」が設定されたものとして説明を続ける。ステップＳ１０２では、前記検索条件設定部１０５によりコンテキスト検索条件Xが設定される。
【００２８】
ステップＳ１０３では、前記検索要求生成部１０６により、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージが生成される。ステップＳ１０４では、前記検索要求送信部１０２により検索要求メッセージがブロードキャスト送信される。
【００２９】
図５へ進み、各検索対象ピアPdi，Ptjは、ステップＳ２０１において前記検索要求メッセージが検索要求受信部２０２で受信されるとステップＳ２０２へ進み、同一の検索要求メッセージを既に別経路で受信済みであるか否かが判定される。受信済みであればステップＳ２３０へ進み、前記メッセージ破棄部２０８により当該検索要求メッセージが破棄される。
【００３０】
これに対して、最初の検索要求メッセージであればステップＳ２０３へ進み、前記検索条件判定部２０６により、当該検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足しているか否かが判定される。図１のピアPt0，Pt1，Pt2であれば、検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が初期値の「２」から「１」に更新される。
【００３１】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが、前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進む。ステップＳ２２２では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「５」から「４」に更新される。
【００３２】
ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２２４へ進む。ステップＳ２２４では、前記第１許容ホップ数e1＝４，第２許容ホップ数e2＝１に更新された検索要求メッセージが、前記検索要求中継部２０４により他のピアへ中継される。
【００３３】
ステップＳ２２５では、前記中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２２６へ進み、当該検索応答メッセージが中継される。このような検索応答メッセージの中継処理は、ステップＳ２２７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００３４】
次いで、検索条件を満足しないピアPt3に注目して説明する。ピアPt3は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が「１」から「０」に更新される。ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」と判定されるのでステップＳ２３０へ進み、当該検索要求メッセージが破棄される。
【００３５】
次いで、検索条件を満足するピアPd0に注目して説明する。ピアPd0は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６によりコンテキスト検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。
【００３６】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「４」から「３」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが、前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２０７へ進む。ステップＳ２０７では、前記第１許容ホップ数e1＝３，第２許容ホップ数e2＝２に更新された検索要求メッセージが前記検索要求中継部２０４により送信される。
【００３７】
ステップＳ２０８では、前記検索応答返信部２０５により自ピアの検索応答メッセージが生成されて返信される。ステップＳ２０９では、前記ステップＳ２０７で中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２１０へ進み、当該検索応答メッセージが中継される。この検索応答メッセージの中継処理は、ステップＳ２１１で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００３８】
次いで、検索条件を満足しないピアPt10に注目して説明する。ピアPt10は、ステップＳ２０１において、ピアPd3で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が「２」から「１」に更新される。
【００３９】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進む。ステップＳ２２２では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。ここでは、第１許容ホップ数e1が「１」から「０」に更新される。ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」と判定されるのでステップＳ２３０へ進み、当該検索要求メッセージが破棄される。
【００４０】
次いで、検索条件を満足するピアPd4に注目して説明する。ピアPd4は、ステップＳ２０１において、ピアPt7で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。この第２制限値E2は検索要求メッセージに記述されているものを用いる。
【００４１】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「１」から「０」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」と判定されるのでステップＳ２１２へ進む。ステップＳ２１２では、当該検索要求メッセージが破棄される。ステップＳ２１３では、前記検索応答返信部２０５により自ピアの検索応答メッセージが生成されて返信される。
【００４２】
図４へ戻り、検索元ピアPsは、ステップＳ１０５において、前記検索応答受信部１０３により検索応答メッセージが受信されるとステップＳ１０６へ進み、当該メッセージの送信元ピアの識別情報がコンテキスト検索結果として取り込まれる。この検索応答メッセージの受信処理は、ステップＳ１０７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【実施例３】
【００４３】
上記の第１実施形態では、各検索対象ピアは、自身が中継した検索要求メッセージに対して返信される検索応答メッセージを、これが受信されるごとに中継するものとして説明したが、第２実施形態では、各検索対象ピアノードに検索応答メッセージの受信期間を設定し、各検索対象ピアノードは、当該受信期間中に受信された少なくとも一つの検索応答メッセージを集約し、一つの検索応答メッセージにまとめて中継するようにした点に特徴がある。
【００４４】
図６は、本発明の第２実施形態における検索元ピアPsの主要部の構成を示した機能ブロック図であり、前記と同一の符号は同一または同等部分を表している。
【００４５】
受信期間設定部１０８は、検索元ピアPsおよび各検索対象ピアノードが検索応答メッセージの受信に備えて待機する受信期間Tmを設定する。前記検索要求生成部１０６は、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記受信期間Tm、前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージを生成する。検索応答受信部１０３の解体部１０３ａは、複数の検索応答メッセージが集約されたメッセージを解体して各検索応答メッセージを検索応答処理部１０７へ提供する。
【００４６】
図７は、本発明の第２実施形態における検索対象ピアの主要部の構成を示した機能ブロック図であり、前記と同一の符号は同一または同等部分を表している。
【００４７】
検索応答中継部２０３において、一時保持部２０３ａは、所定の受信期間Tm内に受信された全ての検索応答メッセージを一時的に保持する。集約化部２０３ｂは、前記受信期間Tm内に受信された全ての検索応答メッセージを集約し、一つのメッセージにまとめて送信元ピア側へ返信する。前記集約化部２０３ｂは、たとえば公知のカプセル化によって複数の検索応答メッセージを集約化する。メッセージ更新部２０９において、受信期間更新部２０９ｄは、中継する検索要求メッセージに記述されている受信期間Tmを時短方向に更新する。
【００４８】
次いで、フローチャートを参照して、本発明の第２実施形態の動作を詳細に説明する。図８は、前記検索元ピアPsの動作を示したフローチャートであり、図９は、前記各検索対象ピアの動作を示したフローチャートである。
【００４９】
検索元ピアPsでは、図８のステップＳ１０１において、検索要求メッセージのホップ数を制限するための第１制限値E1および第２制限値E2が前記ホップ数制限値設定部１０４により設定される。本実施形態では、第１制限値E1として「５」が設定され、第２制限値E2として「２」が設定されたものとして説明を続ける。ステップＳ１０１ａでは、前記受信期間設定部１０８により、検索応答メッセージの受信期間Tmが設定される。ステップＳ１０２では、前記検索条件設定部１０５によりコンテキスト検索条件が設定される。
【００５０】
ステップＳ１０３では、前記検索要求生成部１０６により、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記受信期間Tm，前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージが生成される。ステップＳ１０４では、前記検索要求送信部１０２により検索要求メッセージが送信される。ステップＳ１０４ａでは、前記受信期間Tmのタイマがスタートする。
【００５１】
図９へ進み、各検索対象ピアは、ステップＳ２０１において前記検索要求メッセージが検索要求受信部２０２で受信されるとステップＳ２０２へ進み、同一の検索要求メッセージを既に別経路で受信済みであるか否かが判定される。受信済みであればステップＳ２３０へ進み、前記メッセージ破棄部２０８により当該検索要求メッセージが破棄される。
【００５２】
これに対して、最初の検索要求メッセージであればステップＳ２０３へ進み、前記検索条件判定部２０６により、当該検索要求メッセージに記述されたコンテキスト検索条件を自ノードが満足しているか否かが判定される。図５のピアPt0，Pt1，Pt2であれば、検索条件を満足していないと判定されるとステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が初期値の「２」から「１」に更新される。
【００５３】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進み、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「５」から「４」に更新される。ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２４へ進む。ステップＳ２２４では、前記第１許容ホップ数e1＝４，第２許容ホップ数e2＝１に更新された検索要求メッセージが、前記検索要求中継部２０４により中継される。
【００５４】
ステップＳ２２５では、前記中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２２６へ進み、当該検索応答メッセージが中継される。この検索応答メッセージの中継処理は、ステップＳ２２７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００５５】
次いで、検索条件を満足するピアPd0に注目して説明する。ピアPd0は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。
【００５６】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「４」から「３」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２０６ａへ進む。
【００５７】
ステップＳ２０６ａでは、前記メッセージ更新部２０９により、受信期間Tmが所定時間Δtだけ短縮される。ステップＳ２０７では、前記第１許容ホップ数e1＝３，第２許容ホップ数e2＝２、受信期間Tm＝Tm−Δtに更新された検索要求メッセージが、前記検索要求中継部２０４により送信される。ステップＳ２０７ａでは、前記更新された受信期間Tmのタイマがスタートする。
【００５８】
ステップＳ２０９では、前記ステップＳ２０７で中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２０９ａへ進んで一時的に保持される。ステップＳ２１１では、前記タイマがタイムアウトしたか否かが判定され、タイムアウトするまでは、ステップＳ２０９へ戻って次の検索応答メッセージの受信に備える。
【００５９】
ステップＳ２１１においてタイムアウトが検知されるとステップＳ２１１ａへ進む。ステップＳ２１１ａでは、前記受信期間Tm内に受信された全ての検索応答メッセージが一つの検索応答メッセージに集約される。ステップＳ２１１ｂでは、前記集約されて一つになった検索応答メッセージが返信される。
【００６０】
図８へ戻り、検索元ピアPsは、ステップＳ１０５において、前記集約されて一つにまとめられた検索応答メッセージが受信されるとステップＳ１０５ａへ進み、当該メッセージが解体されて各検索応答メッセージが抽出される。ステップＳ１０６では、各検索応答メッセージの送信元ピアの識別情報がコンテキスト検索結果として取り込まれる。この検索応答メッセージの受信処理は、ステップＳ１０７で受信期間Tmがタイムアウトしたと判定されるまで継続される。
【符号の説明】
【００６１】
１０１…通信インターフェース，１０２…検索要求送信部，１０３…検索応答受信部，１０４…ホップ数制限値設定部，１０５…検索条件設定部，１０６…検索要求生成部，１０７…検索応答処理部，２０１…通信インターフェース，２０２…検索要求受信部，２０３…検索応答中継部，２０４…検索要求中継部，２０５…検索応答返信部，２０６…検索条件判定部，２０７…中継判定部，２０８…メッセージ破棄部，２０９…メッセージ更新部，２１０…コンテキストデータベース
【技術分野】
【０００１】
本発明は、コンテキスト検索方法およびシステムに係り、特に、コンテキスト検索のメッセージに許容ホップ数が設定されるコンテキスト検索方法およびシステムに関する。
【背景技術】
【０００２】
ピアツーピアネットワーク上でコンテキスト検索を行う検索元ピアノードが、コンテキスト検索条件の記述された検索要求メッセージを、許容ホップ数等の制約を設けてブロードキャストで送信し、この検索要求メッセージを受信したピアノードのコンテキストが検索条件を満足すると、検索元ピアノードに対して検索応答メッセージを返信するコンテキスト検索の手法が非特許文献１に開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Y. Chawathe, S. Ratnasamy, L. Breslau, and S. Shenker, "Making Gnutella-like P2P Systems Scalable", ACM SIGCOMM 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術には、以下のような技術課題があった。
(1)コンテキスト検索要求メッセージは、許容ホップ数の範囲内であればブロードキャスト転送されるので、検索要求メッセージの転送数が増加してしまう。
(2)コンテキスト検索条件を満足するピアが、検索要求メッセージに対して個別に検索応答メッセージを返信するので、検索応答メッセージの転送数が増加してしまう。
【０００５】
本発明の目的は、上記した従来技術の課題を解決し、検索要求メッセージの転送数や、これに対する検索応答メッセージの転送数を効率よく動的に削減できるコンテキスト検索方法およびシステムを提供することにある。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために、本発明は、コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索システムにおいて、以下のような手段を講じた点に特徴がある。
【０００７】
(1)検索元ピアが、検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手段と、第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手段と、検索要求メッセージを検索対象のピアへ送信する手段とを具備し、
【０００８】
検索対象の各ピアが、検索要求メッセージを受信する手段と、受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手段と、検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手段と、中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手段と、検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手段と、検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手段と、検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手段と、中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手段と、前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手段とを具備し、
【０００９】
検索元ピアがさらに、各検索対象のピアから返信される検索応答メッセージを受信する手段を具備したことを特徴とする。
【００１０】
(2)検索元ピアがさらに、検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手段と、タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手段とをさらに具備し、
【００１１】
検索対象ピアがさらに、検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手段と、検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手段と、タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手段とを具備し、
【００１２】
前記検索元ピアは、タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、以下のような効果が達成される。
【００１４】
(1)検索要求メッセージに設定された許容ホップ数が、コンテキスト検索条件を満足するピアおよびその近傍のピアでは、それ以外のピアおよびその近傍のピアよりも緩和されるので、コンテキストの一致するピア同士が近接するネットワークトポロジであれば、コンテキスト検索条件を満足するピアへ到達する可能性の高いメッセージのホップ数を、コンテキスト検索条件を満足するピアへ到達する可能性の低いメッセージのホップ数よりも長くできる。
【００１５】
(2)コンテキスト検索条件を満足するピアは、自ピアが中継した検索要求メッセージに対して返信されて自ピアで中継する各検索応答メッセージを、自ピアの検索応答メッセージと共に集約して中継するので、検索応答メッセージの転送数を削減できるようになる。
【図面の簡単な説明】
【００１６】
【図１】本発明が適用されるピアツーピアネットワークの一例を示した図である。
【図２】第１実施形態に係る検索元ピアの構成を示した機能ブロック図である。
【図３】第１実施形態に係る検索対象ピアの構成を示した機能ブロック図である。
【図４】第１実施形態における検索元ピアの動作を示したフローチャートである。
【図５】第１実施形態における各検索対象ピアの動作を示したフローチャートである。
【図６】第２実施形態に係る検索元ピアの構成を示した機能ブロック図である。
【図７】第２実施形態に係る検索対象ピアの構成を示した機能ブロック図である。
【図８】第２実施形態における検索元ピアの動作を示したフローチャートである。
【図９】第２実施形態における各検索対象ピアの動作を示したフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１７】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明が適用されるピアツーピアネットワークの一例を示した図であり、黒丸印は、コンテキスト検索条件の記述された検索要求メッセージを送信してコンテキスト検索を実行する検索元ピアPsを表している。斜線丸印は、検索条件を満足するピアPdiを表し、白丸印は、検索条件を満足しないピアPtjを表している。
【実施例２】
【００１８】
図２は、前記検索元ピアPsの主要部の構成を示した機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１９】
ホップ数制限値設定部１０４は、検索要求メッセージのホップ数を制限することで検索要求メッセージの転送数を抑制するための第１および第２制限値を設定する。第１制限値E1は、ホップ数の絶対的な制限値であり、本実施形態では、当該第１制限値E1を超えて検索要求メッセージが転送されることはない。第２制限値E2は、前記第１制限値E1よりも小さな値に設定されるが、検索要求メッセージを受信した検索対象ピアがコンテキスト条件を満足していると初期化される。当該第１および第２制限値E1，E2の機能については、後に詳述する。
【００２０】
検索条件設定部１０５は、多数の検索対象ピアの中から目的のピアを検索するためのコンテキスト検索条件Xを設定する。検索要求生成部１０６は、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージを生成する。当該検索要求メッセージは、検索要求送信部１０２から通信インターフェース１０１を介して各検索対象ピアへブロードキャストで送信される。
【００２１】
検索応答受信部１０３は、前記検索要求メッセージを受信した検索対象ピアのうち、前記コンテキスト条件を満足するピアPdiから返信される検索応答メッセージを前記通信インターフェース１０１経由で受信する。検索応答処理部１０７は、受信された検索応答メッセージに基づいて、コンテキスト検索条件を満足するピアを識別する。
【００２２】
図３は、前記検索対象ピアPdi，Ptjの主要部の構成を示した機能ブロック図であり、ここでも、本発明の説明に不要な構成は図示が省略されている。
【００２３】
検索要求受信部２０２は、前記検索元ピアPsから送信された、あるいは他の検索対象ピアにより中継された検索要求メッセージを通信インターフェース２０１経由で受信する。検索条件判定部２０６は、受信した検索要求メッセージに記述されているコンテキスト検索条件Xと自ピアのコンテキストデータベース２１０に登録されているコンテキストとを比較・照合し、自ピアがコンテキスト検索条件を満足しているか否かを判定する。
【００２４】
中継判定部２０７は、受信した検索要求メッセージを他のピアへさらに中継するか否かを、当該検索要求メッセージに記述されている第１および第２許容ホップ数e1，e2ならびに自ピアが検索条件を満足しているか否かに基づいて判定する。メッセージ破棄部２０８は、中継しないと判定された検索要求メッセージを破棄する
【００２５】
メッセージ更新部２０９は、中継する検索要求メッセージの第１許容ホップ数e1を更新（デクリメント）する更新部２０９ａ、第２許容ホップ数e2を更新（デクリメント）する更新部２０９ｂ、および第２許容ホップ数e2を初期化して第２制限値E1に戻す初期化部２０９ｃを含む。更新された検索要求メッセージは、検索要求中継部２０４から通信インターフェース２０１経由で他のピアへ中継される。検索応答中継部２０３は、前記中継した検索要求メッセージに対して返信される検索応答メッセージを中継する。検索応答返信部２０５は、自ピアがコンテキスト検索条件を満足するときに検索応答メッセージを返信する。
【００２６】
次いで、フローチャートを参照して、本発明の第１実施形態の動作を詳細に説明する。図４は、前記検索元ピアPsの動作を示したフローチャートであり、図５は、前記各検索対象ピアの動作を示したフローチャートである。
【００２７】
検索元ピアPsでは、図４のステップＳ１０１において、検索要求メッセージのホップ数を制限するための第１制限値E1および第２制限値E2が前記ホップ数制限値設定部１０４により設定される。本実施形態では、第１制限値E1として「５」が設定され、第２制限値E2として「２」が設定されたものとして説明を続ける。ステップＳ１０２では、前記検索条件設定部１０５によりコンテキスト検索条件Xが設定される。
【００２８】
ステップＳ１０３では、前記検索要求生成部１０６により、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージが生成される。ステップＳ１０４では、前記検索要求送信部１０２により検索要求メッセージがブロードキャスト送信される。
【００２９】
図５へ進み、各検索対象ピアPdi，Ptjは、ステップＳ２０１において前記検索要求メッセージが検索要求受信部２０２で受信されるとステップＳ２０２へ進み、同一の検索要求メッセージを既に別経路で受信済みであるか否かが判定される。受信済みであればステップＳ２３０へ進み、前記メッセージ破棄部２０８により当該検索要求メッセージが破棄される。
【００３０】
これに対して、最初の検索要求メッセージであればステップＳ２０３へ進み、前記検索条件判定部２０６により、当該検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足しているか否かが判定される。図１のピアPt0，Pt1，Pt2であれば、検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が初期値の「２」から「１」に更新される。
【００３１】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが、前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進む。ステップＳ２２２では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「５」から「４」に更新される。
【００３２】
ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２２４へ進む。ステップＳ２２４では、前記第１許容ホップ数e1＝４，第２許容ホップ数e2＝１に更新された検索要求メッセージが、前記検索要求中継部２０４により他のピアへ中継される。
【００３３】
ステップＳ２２５では、前記中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２２６へ進み、当該検索応答メッセージが中継される。このような検索応答メッセージの中継処理は、ステップＳ２２７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００３４】
次いで、検索条件を満足しないピアPt3に注目して説明する。ピアPt3は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が「１」から「０」に更新される。ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」と判定されるのでステップＳ２３０へ進み、当該検索要求メッセージが破棄される。
【００３５】
次いで、検索条件を満足するピアPd0に注目して説明する。ピアPd0は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６によりコンテキスト検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。
【００３６】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「４」から「３」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが、前記中継判定部２０７により判定され、ここでは「０」以外と判定されるのでステップＳ２０７へ進む。ステップＳ２０７では、前記第１許容ホップ数e1＝３，第２許容ホップ数e2＝２に更新された検索要求メッセージが前記検索要求中継部２０４により送信される。
【００３７】
ステップＳ２０８では、前記検索応答返信部２０５により自ピアの検索応答メッセージが生成されて返信される。ステップＳ２０９では、前記ステップＳ２０７で中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２１０へ進み、当該検索応答メッセージが中継される。この検索応答メッセージの中継処理は、ステップＳ２１１で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００３８】
次いで、検索条件を満足しないピアPt10に注目して説明する。ピアPt10は、ステップＳ２０１において、ピアPd3で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していないと判定されるのでステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が「２」から「１」に更新される。
【００３９】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進む。ステップＳ２２２では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。ここでは、第１許容ホップ数e1が「１」から「０」に更新される。ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」と判定されるのでステップＳ２３０へ進み、当該検索要求メッセージが破棄される。
【００４０】
次いで、検索条件を満足するピアPd4に注目して説明する。ピアPd4は、ステップＳ２０１において、ピアPt7で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。この第２制限値E2は検索要求メッセージに記述されているものを用いる。
【００４１】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「１」から「０」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」と判定されるのでステップＳ２１２へ進む。ステップＳ２１２では、当該検索要求メッセージが破棄される。ステップＳ２１３では、前記検索応答返信部２０５により自ピアの検索応答メッセージが生成されて返信される。
【００４２】
図４へ戻り、検索元ピアPsは、ステップＳ１０５において、前記検索応答受信部１０３により検索応答メッセージが受信されるとステップＳ１０６へ進み、当該メッセージの送信元ピアの識別情報がコンテキスト検索結果として取り込まれる。この検索応答メッセージの受信処理は、ステップＳ１０７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【実施例３】
【００４３】
上記の第１実施形態では、各検索対象ピアは、自身が中継した検索要求メッセージに対して返信される検索応答メッセージを、これが受信されるごとに中継するものとして説明したが、第２実施形態では、各検索対象ピアノードに検索応答メッセージの受信期間を設定し、各検索対象ピアノードは、当該受信期間中に受信された少なくとも一つの検索応答メッセージを集約し、一つの検索応答メッセージにまとめて中継するようにした点に特徴がある。
【００４４】
図６は、本発明の第２実施形態における検索元ピアPsの主要部の構成を示した機能ブロック図であり、前記と同一の符号は同一または同等部分を表している。
【００４５】
受信期間設定部１０８は、検索元ピアPsおよび各検索対象ピアノードが検索応答メッセージの受信に備えて待機する受信期間Tmを設定する。前記検索要求生成部１０６は、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記受信期間Tm、前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージを生成する。検索応答受信部１０３の解体部１０３ａは、複数の検索応答メッセージが集約されたメッセージを解体して各検索応答メッセージを検索応答処理部１０７へ提供する。
【００４６】
図７は、本発明の第２実施形態における検索対象ピアの主要部の構成を示した機能ブロック図であり、前記と同一の符号は同一または同等部分を表している。
【００４７】
検索応答中継部２０３において、一時保持部２０３ａは、所定の受信期間Tm内に受信された全ての検索応答メッセージを一時的に保持する。集約化部２０３ｂは、前記受信期間Tm内に受信された全ての検索応答メッセージを集約し、一つのメッセージにまとめて送信元ピア側へ返信する。前記集約化部２０３ｂは、たとえば公知のカプセル化によって複数の検索応答メッセージを集約化する。メッセージ更新部２０９において、受信期間更新部２０９ｄは、中継する検索要求メッセージに記述されている受信期間Tmを時短方向に更新する。
【００４８】
次いで、フローチャートを参照して、本発明の第２実施形態の動作を詳細に説明する。図８は、前記検索元ピアPsの動作を示したフローチャートであり、図９は、前記各検索対象ピアの動作を示したフローチャートである。
【００４９】
検索元ピアPsでは、図８のステップＳ１０１において、検索要求メッセージのホップ数を制限するための第１制限値E1および第２制限値E2が前記ホップ数制限値設定部１０４により設定される。本実施形態では、第１制限値E1として「５」が設定され、第２制限値E2として「２」が設定されたものとして説明を続ける。ステップＳ１０１ａでは、前記受信期間設定部１０８により、検索応答メッセージの受信期間Tmが設定される。ステップＳ１０２では、前記検索条件設定部１０５によりコンテキスト検索条件が設定される。
【００５０】
ステップＳ１０３では、前記検索要求生成部１０６により、前記第１制限値E1が第１許容ホップ数e1として記述され、前記第２制限値E2が第２許容ホップ数e2として記述され、さらに前記受信期間Tm，前記第２制限値E2およびコンテキスト検索条件Xの記述された検索要求メッセージが生成される。ステップＳ１０４では、前記検索要求送信部１０２により検索要求メッセージが送信される。ステップＳ１０４ａでは、前記受信期間Tmのタイマがスタートする。
【００５１】
図９へ進み、各検索対象ピアは、ステップＳ２０１において前記検索要求メッセージが検索要求受信部２０２で受信されるとステップＳ２０２へ進み、同一の検索要求メッセージを既に別経路で受信済みであるか否かが判定される。受信済みであればステップＳ２３０へ進み、前記メッセージ破棄部２０８により当該検索要求メッセージが破棄される。
【００５２】
これに対して、最初の検索要求メッセージであればステップＳ２０３へ進み、前記検索条件判定部２０６により、当該検索要求メッセージに記述されたコンテキスト検索条件を自ノードが満足しているか否かが判定される。図５のピアPt0，Pt1，Pt2であれば、検索条件を満足していないと判定されるとステップＳ２２０へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が「１」だけデクリメントされる。すなわち、第２許容ホップ数e2が初期値の「２」から「１」に更新される。
【００５３】
ステップＳ２２１では、更新後の第２許容ホップ数e2が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２２へ進み、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「５」から「４」に更新される。ステップＳ２２３では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２２４へ進む。ステップＳ２２４では、前記第１許容ホップ数e1＝４，第２許容ホップ数e2＝１に更新された検索要求メッセージが、前記検索要求中継部２０４により中継される。
【００５４】
ステップＳ２２５では、前記中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２２６へ進み、当該検索応答メッセージが中継される。この検索応答メッセージの中継処理は、ステップＳ２２７で所定の待機時間がタイムアウトしたと判定されるまで継続される。
【００５５】
次いで、検索条件を満足するピアPd0に注目して説明する。ピアPd0は、ステップＳ２０１において、ピアPt0で中継された検索要求メッセージを受信するとステップＳ２０２へ進み、これが最初の検索要求メッセージであればステップＳ２０３へ進む。ステップＳ２０３では、前記検索条件判定部２０６により検索条件を満足していると判定されるのでステップＳ２０４へ進み、前記メッセージ更新部２０９により、第２許容ホップ数e2が初期化されて第２制限値E2（＝２）に戻される。
【００５６】
ステップＳ２０５では、前記メッセージ更新部２０９により、第１許容ホップ数e1が「１」だけデクリメントされる。すなわち、第１許容ホップ数e1が「４」から「３」に更新される。ステップＳ２０６では、更新後の第１許容ホップ数e1が「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ２０６ａへ進む。
【００５７】
ステップＳ２０６ａでは、前記メッセージ更新部２０９により、受信期間Tmが所定時間Δtだけ短縮される。ステップＳ２０７では、前記第１許容ホップ数e1＝３，第２許容ホップ数e2＝２、受信期間Tm＝Tm−Δtに更新された検索要求メッセージが、前記検索要求中継部２０４により送信される。ステップＳ２０７ａでは、前記更新された受信期間Tmのタイマがスタートする。
【００５８】
ステップＳ２０９では、前記ステップＳ２０７で中継した検索要求メッセージに対する検索応答メッセージが前記検索応答中継部２０３により受信されたか否かが判定される。受信が検知されるとステップＳ２０９ａへ進んで一時的に保持される。ステップＳ２１１では、前記タイマがタイムアウトしたか否かが判定され、タイムアウトするまでは、ステップＳ２０９へ戻って次の検索応答メッセージの受信に備える。
【００５９】
ステップＳ２１１においてタイムアウトが検知されるとステップＳ２１１ａへ進む。ステップＳ２１１ａでは、前記受信期間Tm内に受信された全ての検索応答メッセージが一つの検索応答メッセージに集約される。ステップＳ２１１ｂでは、前記集約されて一つになった検索応答メッセージが返信される。
【００６０】
図８へ戻り、検索元ピアPsは、ステップＳ１０５において、前記集約されて一つにまとめられた検索応答メッセージが受信されるとステップＳ１０５ａへ進み、当該メッセージが解体されて各検索応答メッセージが抽出される。ステップＳ１０６では、各検索応答メッセージの送信元ピアの識別情報がコンテキスト検索結果として取り込まれる。この検索応答メッセージの受信処理は、ステップＳ１０７で受信期間Tmがタイムアウトしたと判定されるまで継続される。
【符号の説明】
【００６１】
１０１…通信インターフェース，１０２…検索要求送信部，１０３…検索応答受信部，１０４…ホップ数制限値設定部，１０５…検索条件設定部，１０６…検索要求生成部，１０７…検索応答処理部，２０１…通信インターフェース，２０２…検索要求受信部，２０３…検索応答中継部，２０４…検索要求中継部，２０５…検索応答返信部，２０６…検索条件判定部，２０７…中継判定部，２０８…メッセージ破棄部，２０９…メッセージ更新部，２１０…コンテキストデータベース
【特許請求の範囲】
【請求項１】
コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索方法において、
検索元ピアが、
検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手順と、
前記第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手順と、
前記検索要求メッセージを検索対象のピアへ送信する手順とを具備し、
検索対象の各ピアが、
検索要求メッセージを受信する手順と、
受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手順と、
検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手順と、
中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手順と、
中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手順と、
検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手順と、
検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手順と、
検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手順と、
中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手順と、
中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手順と、
前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手順とを具備し、
前記検索元ピアがさらに、
前記各検索対象のピアから返信される検索応答メッセージを受信する手順を具備したことを特徴とするコンテキスト検索方法。
【請求項２】
前記検索元ピアがさらに、
検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手順と、
前記タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手順とをさらに具備し、
前記検索対象ピアがさらに、
検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手順と、
検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手順と、
前記タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手順とを具備し、
前記検索元ピアは、前記タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする請求項１に記載のコンテキスト検索方法。
【請求項３】
コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索システムにおいて、
検索元ピアが、
検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手段と、
前記第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手段と、
前記検索要求メッセージを検索対象のピアへ送信する手段とを具備し、
検索対象の各ピアが、
検索要求メッセージを受信する手段と、
受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手段と、
検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、
中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手段と、
中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手段と、
検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手段と、
検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手段と、
検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、
中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手段と、
中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手段と、
前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手段とを具備し、
前記検索元ピアがさらに、
前記各検索対象のピアから返信される検索応答メッセージを受信する手段を具備したことを特徴とするコンテキスト検索システム。
【請求項４】
前記検索元ピアがさらに、
検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手段と、
前記タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手段とをさらに具備し、
前記検索対象ピアがさらに、
検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手段と、
検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手段と、
前記タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手段とを具備し、
前記検索元ピアは、前記タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする請求項３に記載のコンテキスト検索システム。
【請求項１】
コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索方法において、
検索元ピアが、
検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手順と、
前記第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手順と、
前記検索要求メッセージを検索対象のピアへ送信する手順とを具備し、
検索対象の各ピアが、
検索要求メッセージを受信する手順と、
受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手順と、
検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手順と、
中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手順と、
中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手順と、
検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手順と、
検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手順と、
検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手順と、
中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手順と、
中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手順と、
前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手順とを具備し、
前記検索元ピアがさらに、
前記各検索対象のピアから返信される検索応答メッセージを受信する手順を具備したことを特徴とするコンテキスト検索方法。
【請求項２】
前記検索元ピアがさらに、
検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手順と、
前記タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手順とをさらに具備し、
前記検索対象ピアがさらに、
検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手順と、
検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手順と、
前記タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手順とを具備し、
前記検索元ピアは、前記タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする請求項１に記載のコンテキスト検索方法。
【請求項３】
コンテキスト検索の検索元ピアが検索要求メッセージを送信し、検索対象の各ピアが、受信した検索要求メッセージを所定の制限下で他のピアへ中継すると共に、自身が検索条件を満足すれば検索応答メッセージを返信するピアツーピア型のコンテキスト検索システムにおいて、
検索元ピアが、
検索要求メッセージのホップ数を制限するための第１および第２制限値を、第１制限値が第２制限値よりも大きくなるように設定する手段と、
前記第１制限値が第１許容ホップ数として記述され、前記第２制限値が第２許容ホップ数として記述され、さらに前記第２制限値およびコンテキスト検索条件の記述された検索要求メッセージを生成する手段と、
前記検索要求メッセージを検索対象のピアへ送信する手段とを具備し、
検索対象の各ピアが、
検索要求メッセージを受信する手段と、
受信した検索要求メッセージに記述されたコンテキスト検索条件を自ピアが満足するか否かを判定する手段と、
検索条件を満足しない検索要求メッセージに記述された第１および第２許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、
中継しないと決定された、検索条件を満足しない検索要求メッセージを破棄する手段と、
中継すると決定された、検索条件を満足しない検索要求メッセージの第１および第２許容ホップ数をデクリメントする手段と、
検索条件を満足する検索要求メッセージに対して検索応答メッセージを返信する手段と、
検索条件を満足する検索要求メッセージの第２許容ホップ数を第２制限値に初期化する手段と、
検索条件を満足する検索要求メッセージの第１許容ホップ数に基づいて、当該検索要求メッセージを中継するか否かを決定する手段と、
中継しないと決定された、検索条件を満足する検索要求メッセージを破棄する手段と、
中継すると決定された、検索条件を満足する検索要求メッセージの第１許容ホップ数をデクリメントする手段と、
前記第１許容ホップ数がデクリメントされ、第２許容ホップ数が初期化された検索要求メッセージを中継する手段とを具備し、
前記検索元ピアがさらに、
前記各検索対象のピアから返信される検索応答メッセージを受信する手段を具備したことを特徴とするコンテキスト検索システム。
【請求項４】
前記検索元ピアがさらに、
検索応答メッセージの受信期間に対応したタイマ値を検索要求メッセージに記述する手段と、
前記タイマ値の記述された検索要求メッセージの送信に応答して前記タイマ値の計時を開始する手段とをさらに具備し、
前記検索対象ピアがさらに、
検索条件を満足する検索要求メッセージを中継する際に、そのタイマ値を短縮する手段と、
検索条件を満足してタイマ値を短縮された検索要求メッセージの中継に応答して、当該短縮されたタイマ値の計時を開始する手段と、
前記タイマ値の計時が完了するまでに受信された検索応答メッセージおよび自身の検索応答メッセージを集約し、一つの検索応答メッセージにまとめて返信する手段とを具備し、
前記検索元ピアは、前記タイマ値の計時が完了するまで検索応答メッセージの受信を継続することを特徴とする請求項３に記載のコンテキスト検索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−１９８３１９（Ｐ２０１０−１９８３１９Ａ）
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願番号】特願２００９−４２４３５（Ｐ２００９−４２４３５）
【出願日】平成２１年２月２５日（２００９．２．２５）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願日】平成２１年２月２５日（２００９．２．２５）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]