(57)【要約】【課題】  ピアツーピア・ネットワークにおいてより信頼性の高い通信を実現するネットワークピアを提供する。【解決手段】  ピア１００は、第１の固有リクエストＩＤを有し、ピア１００の第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のリクエストメッセージを受信すると、そのメッセージを別のピアへ送る手段１１０と、第１の固有リクエストＩＤを有し、前記サービスの提供が成功したか否かを示す指標を含むものであるフィードバック・メッセージを受信すると、そのメッセージをその他のピアへ送る手段１２０と、第２の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスをリクエストするものである第２のリクエストメッセージを受信すると、そのメッセージを前記指標に基づいて選択されたピアへ送る手段１３０とを備えるものである。【選択図】  図１Ａ
2008187702.tif 000002
【特許請求の範囲】
【請求項１】
自分に関連する第１のサービスＩＤを有するネットワークピア（１００）であって、
第１の固有のリクエストＩＤを有し、前記第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のサービス・リクエスト・メッセージを受信すると、前記第１のサービス・リクエスト・メッセージを別のネットワークピアへ送る手段（１１０）と、
前記第１の固有のリクエストＩＤを有し、第２のサービスＩＤを持つサービスが成功裏に提供されたか否かを示す指標を含むものであるフィードバック・メッセージを受信すると、前記フィードバック・メッセージをその他のネットワークピアへ送る手段（１２０）と、
第２の固有のリクエストＩＤを有し、前記第２のサービスＩＤを持つサービスをリクエストするものである第２のサービス・リクエスト・メッセージを受信すると、前記第２のサービス・リクエスト・メッセージを前記指標に基づいて選択されたネットワークピアへ送る手段（１３０）と
を備えるものであるネットワークピア（１００）。
【請求項２】
固有のリクエストＩＤを有し、サービスＩＤを持つサービスをリクエストするものであるサービス・リクエスト・メッセージを作成する手段を更に備えるものである請求項１に記載のネットワークピア（１００）。
【請求項３】
サービス・リクエスト・メッセージに関連する固有のＩＤを有するフィードバック・メッセージを作成する手段を更に備えるものである請求項１または２に記載のネットワークピア（１００）。
【請求項４】
異なる固有のリクエストＩＤを有し、前記第１のサービスＩＤを持つサービスをリクエストするものである異なるサービス・リクエスト・メッセージを受信すると、前記第１のサービスＩＤを持つサービスを提供する手段を更に備えるものである請求項１乃至３のいずれか１項に記載のネットワークピア（１００）。
【請求項５】
前記サービス・リクエスト・メッセージを作成する手段は、更に有効期限タイマを開始するように構成されるものであり、前記フィードバック・メッセージを作成する手段は、前記サービスＩＤを持つサービスが提供される前に前記有効期限タイマが時間切れした際には、負の指標を有する負のフィードバック・メッセージを作成し、前記有効期限タイマが時間切れになる前に、前記サービスＩＤを持つサービスを成功裏に受けた際には、正の指標を有する正のフィードバック・メッセージを作成するように構成されるものである、請求項３または４に記載のネットワークピア（１００）。
【請求項６】
前記第１のサービス・リクエスト・メッセージを送る手段は、前記第１のサービス・リクエスト・メッセージを送るときに第２の有効期限タイマを開始するように構成されるものであり、前記第２のサービス・リクエスト・メッセージを送る手段は、前記第２の有効期限タイマが時間切れする前に前記第１の固有のリクエストＩＤを有する前記フィードバック・メッセージが受信されない場合には前記第２のサービスＩＤを持つサービスは成功裏に提供されていないと見なすように構成されるものである、請求項１乃至５のいずれか１項に記載のネットワークピア（１００）。
【請求項７】
前記フィードバック・メッセージを作成する手段は更に、前記フィードバック・メッセージが正または負のいずれであるかを示す単一ビットを前記フィードバック・メッセージに含ませるように構成されるものである、請求項５または６に記載のネットワークピア（１００）。
【請求項８】
前記第１あるいは第２のサービス・リクエスト・メッセージを送る手段は更に、それ自身に関する情報、前記第１または第２の固有のリクエストＩＤ、前記第１あるいは第２のサービス・リクエスト・メッセージがそこから受信されたネットワークピア、前記第１あるいは第２のサービス・リクエスト・メッセージの発信源、又は目標のネットワークピアを、送られる前記第１または第２のサービス・リクエスト・メッセージに含ませるように構成されるものである、請求項１乃至７のいずれか１項に記載のネットワークピア（１００）。
【請求項９】
前記第２のサービス・リクエスト・メッセージを送る手段は、前記指標に基づく不具合予測を含むテーブルからネットワークピアを選択するように構成されるものである、請求項１乃至８のいずれか１項に記載のネットワークピア（１００）。
【請求項１０】
前記不具合予測は確率的概念学習に基づくものである、請求項９に記載のネットワークピア（１００）。
【請求項１１】
前記不具合予測は、メッセージがそこから送信もしくは送られた一つ前のネットワークピアと、メッセージをそこへ送信もしくは送ることが可能な次のネットワークピアと、サービスＩＤとのいずれか１つもしくはそれらの組み合わせを参照するものである、請求項９または１０に記載のネットワークピア（１００）。
【請求項１２】
前記第１の固有のリクエストＩＤを有するフィードバック・メッセージを送る手段は、前記フィードバック・メッセージを、前記第１の固有のリクエストＩＤを有する前記第１のサービス・リクエスト・メッセージが送られた先と同じネットワークピアへ送るように構成されるものである、請求項１乃至１１のいずれか１項に記載のネットワークピア（１００）。
【請求項１３】
ルーティングテーブルを管理するとともにサービス・ロケーション情報を提供する手段を更に備えるものである請求項１乃至１２のいずれか１項に記載のネットワークピア（１００）。
【請求項１４】
前記ルーティングテーブルを管理する手段は、分散ハッシュテーブルの一部を管理するものである、請求項１３に記載のネットワークピア（１００）。
【請求項１５】
ピアツーピア・ネットワークにおいて第１のサービスＩＤに基づいて通信するための方法であって、
第１の固有のリクエストＩＤを有し、前記第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のサービス・リクエスト・メッセージを受信すると、前記第１のサービス・リクエスト・メッセージをネットワークピアへ送るステップと、
前記第１の固有のリクエストＩＤを有し、第２のサービスＩＤを持つサービスが成功裏に提供されたか否かを示す指標を含むものであるフィードバック・メッセージを受信すると、前記フィードバック・メッセージを前記ネットワークピアへ送るステップと、
第２の固有のリクエストＩＤを有し、前記第２のサービスＩＤを持つサービスをリクエストするものである第２のサービス・リクエスト・メッセージを前記指標に基づいて選択されたネットワークピアへ送るステップと
を含む方法。
【請求項１６】
コンピュータ上で実行させた際に請求項１５に記載された方法を実行するプログラムコードを有するコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピアツーピア・オーバーレイ・システム、より詳しくはピアツーピア・システムにおける悪意のあるネットワークノードを克服するためのフォワード・フィードバック機構に関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ：peer-to-peer）ネットワークは、リソース群の高速探索を可能にする自律分散型オーバーレイ・ネットワーク（self-organizing, distributed overlay networks）である。それらは、参加ノード同士を繋ぐ物理接続が何であれ、その上にアプリケーションレイヤ・オーバーレイ・ネットワークとして実現される。Ｐ２Ｐネットワークで取り組まれる基本的な問題は、１セットのピアにわたる１セットのリソースの、シーケンシャル（順次）高速検索を可能にする、自律分散方法である。
【０００３】
この問題を解決するための有望なアプローチは、分散ハッシュテーブル（ＤＨＴ：Distributed Hash Table）としても知られる構造化Ｐ２Ｐネットワークである。ＤＨＴでは、ピア達が、鍵空間（key space）からの鍵によって特定されるリソースの特定の部分集合を協力して管理する。この際、各ピアは、鍵空間に属する１つの鍵と関連付けられる。１セットのピアが与えられたとすると、各ピアの鍵は、鍵空間の一区画と関連付けられ、これにより、ピアは、関連付けられた区画に属する鍵によって特定される全てのリソースを管理する責任を負うようになる。一般的に、鍵区画は、適切なメトリック（metric）でピアの鍵に最も近い全ての鍵から成る。鍵の近さは、距離関数によって評価される。リソースリクエストを送るために、ピアの鍵区画との関連付けに関する知識を考慮することにより、ピア達は、ルーティングネットワークを形成する。
【０００４】
ピアは一般的に、隣接する鍵を有する全てのピアへの短距離のリンクを維持しており、加えて、一部の選ばれた遠いピアまでの長距離の少数のリンクを維持する。このように構築されたルーティングネットワークを使って、ピアはリソースリクエストをそれらのルーティングテーブルにある他のピアへ指示通りに送るが、検索中の鍵までの距離をどん欲に減らす試みを同時に行う。ほとんどのＤＨＴは、この構築されたものとルーティングアルゴリズムに基づいて、ネットワークのサイズの対数で表されたルーティングテーブルを使用することによって同じくネットワークのサイズの対数で表された多数のメッセージの検索を実現する。
【０００５】
通常、鍵は、ピアのＩＰアドレスとランダムに選ばれた文字列のハッシュ値を計算することによって、ピアに割り当てられる。ハッシュ関数を利用してリソース鍵をピアにマップする副目標は、各ピアが、ほぼ同数の鍵に関与するときに、負荷の配分をバランスさせることである。
【０００６】
まとめると、ＤＨＴの特定の構成は、鍵空間と、距離関数と、鍵分割と、リンク戦略の選択とに依存する。しかしながら、ルーティングの効率性に関わるような優れた特性については自由にはならない。ＤＨＴを構築し、維持するため、ピアは特にノードの参加と故障（による離脱）の問題に対処する必要がある。構造化Ｐ２Ｐネットワークにおいて隣接ノードを選択する自由度は制約されるため、メンテナンスアルゴリズムはネットワークダイナミクスが存在する中でルーティングテーブルの整合性を再構築する必要がある。ネットワークによって与えられる保証のタイプに応じて、異なる決定論的および確率論的メンテナンス戦略が開発されてきた。メンテナンス作業は様々なイベント、例えば定期的なノードの参加もしくは離脱または矛盾のあるルーティングテーブルに起因するルーティング障害などで引き起こされる。異なるメンテナンス戦略は、メンテナンスコストと整合性とを対比し、従ってネットワークの故障回復力をトレードオフする。
【０００７】
ピアツーピア・アーキテクチャにおいて、ピアは、互いに別のサービスを提供する。サービスには、メッセージを送り先に発送／転送したり、鍵の値のペアを分散ハッシュテーブルに保存したり、あるいはファイルをダウンロードすることなどが含まれる。サービスの提供により、プロバイダのリソースが消費される。しかしながら、プロバイダは、どこか他のプロバイダからのサービスの受け手となることで利益を得る場合がある。こうしたサービスの相互交換には、ピア同士の協力が欠かせない。一般的なピアツーピア・ネットワーク展開においては、各ピアは、異なるユーザによって所有される。ユーザは、ピアが従う通信プロトコルを完全にコントロールしている。特に、ユーザは、ピアのソフトウェアを、他のピアからサービスを要求して受け取るだけにして、自分では何のサービスも提供しないように勝手に修正することができる。ユーザの行為とは無関係に、ピアは、通常従うべき通信プロトコルの変更をもたらす内部故障も経験する場合がある。故障がユーザによって引き起こされたかどうかとは関係なく、ピアは、任意にその期待される振る舞いから外れることがあり得る。
【０００８】
これは、一般にビザンチン故障（Byzantine failure）（非特許文献１参照）と呼ばれている。これは、全ての他のタイプの故障を内包する１つのタイプの故障である。サービスの受け手の観点からすれば、これらの故障の部分集合が重要であり、すなわちサービスがサービスの受け手に提供されていない、またはサービスがサービスの受け手に満足できないやり方で提供されているという結果をもたらす故障が重要である。
【０００９】
ピアツーピア・ネットワークにおいて協力関係を構築するための多数のアプローチは、ピアのユニバーサル認証、すなわちネットワークにおける任意のピアの同一性を確実に認証する能力、に依存する。例えば評判（reputation）ベースのアプローチにおいて、各ピアは、各自関連する評判を有する。評判は、あるプロバイダＰによるサービス提供の履歴に基づいて計算される。プロバイダＰの評判を計算するため、ピア達は、プロバイダＰとの過去のやり取りについての情報を交換する必要がある。このためプロバイダＰからサービスを要求する２つの異なるピアは、プロバイダＰについての何らかの情報を交換する前に両方とも同じプロバイダＰと実際にやり取りしたことがなければならない。明らかに、評判は、ユニバーサルまたはグローバルな認証を必要とする。
【００１０】
評判ベースのモデルでは、所与のノードＡに対する信頼度は、ノードＡの過去の行動に基づいて決定される。あらゆるノードＶiは、Ｖi自身が経験したノードＡの行動についての情報のみを有する。ノードＡの評判を計算するため、ノード達は、そのノードらが観察したノードＡの行動についての情報を交換する必要がある。この交換および評判の計算は、多くのやり方で進めることができる。アプローチは、ソーシャルネットワーク、確率推定（probabilistic estimation）、ゲーム理論的モデル（game-theoretic models）および進化的アプローチ（evolutionary approaches）の４つのクラスに分類される（非特許文献２参照）。
【００１１】
ソーシャルネットワークアプローチは、ノード間のソーシャルリンクの有向グラフの存在を想定する。ノード間のやり取りは、リンクに沿って進行し、各リンクには、信頼値（trust value）が付随している。その値は、リンクの両端におけるノード間のやり取りに基づいて更新される。ノードＶは、次のように別の隣接していないノードＷの信頼値を他のノードから集約することによって計算することができる。
１．ノードＷからノードＶへの（全ての）経路を列挙する。
２．それらの経路に沿って信頼値を集約する。
３．ノードＶにおいて集約結果を最終的な信頼値としてまとめる。
【００１２】
ソーシャルネットワークアプローチは、上記３つのステップの詳細、例えば信頼を表すためにどういったドメインが使用されるか、選択された経路は何か、集約・マージ関数は何かなどによって変動する。信頼値は、特定のＷとＶとの間の要求に応じて、あるいは信頼値の固有状態（Eigenstate）に収束する何らかの形の反復方法を利用する全てのノードに対して同時に計算される。
【００１３】
ソーシャルネットワークにおける計算は、解釈が難しい信頼値を生み出す。特に、ノードＡの信頼値が与えられた上で、その値をノードＡが協力する確率に変換することは難しい。しかしながら、これはノードの確率的な振る舞いについての仮定が明示的になされるならば、ベイズ推定や最大尤度推定といった周知の確率推定技術が所与のピアの信頼値を計算するために利用される。これは、確率推定方法が行うことである。一例として、パフォーマンスが信頼できる固有の確率が付随するピアから成るネットワークを議論する。θjをピアｊの確率とする。ピアｊがｎ個の他のピアｐ1、ｐ2、・・・、ｐnと相互作用し、これらの相互作用におけるパフォーマンスがｘ1、・・・、ｘn（ただしｘi∈｛０，１｝、“１”は正直なパフォーマンスを表し、“０”は不正直なパフォーマンスを表す）であったと仮定する。ピアｊのパフォーマンスに関するレポートを依頼するとき、証人ｐ1、・・・、ｐnは嘘をつき、誤った報告をする場合がある。かれらが特定の確率（ピアｐkに対してはｌk）で嘘をつくと仮定すると、ピアｐkから報告ｙkを観測する確率は次のように計算することができる。
【数１】
2008187702.tif 000003
【００１４】
定義により、レポートｙ1、ｙ2、・・・、ｙnのランダム標本に関連する尤度関数は次のようになる。
Ｌ（θj）＝Ｐ［Ｙ1＝ｙ1］Ｐ［Ｙ2＝ｙ2］・・・Ｐ［Ｙn＝ｙn］
【００１５】
ピア（ｊ）に関する報告を収集した後、信頼値を計算するピアは、この積を計算してそれを最大にするθjを見つけなければならない。この数は、未知の確率の最大尤度推定値である。
【００１６】
これを実行するため、計算を行うピアは、パラメータｌ1，．．．，ｌnの良い推定値を得なければならない。それらは、自己のパフォーマンスをこれらに関する報告と比較することによって得られる。自己の経験は、シームレスにこのモデルに組み込まれ、信頼値を計算するソースピアｉは、自己の経験ｘiに対してｐi＝１と置く必要があることにも留意する。確率論的方法の利点として、ソーシャルネットワークと比較すると、それらは通信オーバヘッドの大きな削減をもたらすことが強調される。その理由は、ソーシャルネットワークが全ての利用可能なフィードバック、すなわち全てのピアの全ての他のピアについてのオピニオンを基本的に集約するのに対し、確率論的方法は目標ピアに関するフィードバックのみを取り扱うという点にある。
【００１７】
評判システムに対するゲーム理論的アプローチでは、多くの場合、プレイヤは自己のペイオフ（報酬）を最大にすることのみに興味があるという意味で完全に合理的であると仮定される。これらの仮定のおかげで、ピア達が戦略を変更する誘因を持たない戦略プロファイルとしてナッシュ均衡の計算ができる。通常、評判効果のゲーム理論的なモデリングは、プレイヤ同士のそれらの競争相手のペイオフに関する反復相互作用と不確定性を必要とする（非特許文献３参照）。
【００１８】
より最近では、これらのモデルを現実世界の設定により近づくようモデリングするための拡張が試みられている。とりわけ、２つの重要なモデルは、プライベート監視ゲームとパブリック監視ゲームである。これらのゲームでは、プレイヤは互いの行為を観察するのではなく、それらの信号のみを観察する。プライベート監視ゲームでは、信号はプレイヤが異なれば異なる（非特許文献４参照）。それに対し、パブリック監視ゲームでは、全てのピアは他のピアの行為について同じ信号を観察する（非特許文献５参照）。
【００１９】
しかしながら、ゲーム理論的な評判モデルの適用に関して多数の問題が見られる。プレイヤの完全合理性が期待できない多くの設定が存在する。人間プレイヤによる任意の設定がその一例である。第２の問題は、合理性の仮定を評判メカニズムの実装自体に導入することの難しさにある。
【００２０】
ゲーム理論家は、より実験的な角度からＰＤプレイヤ（ＰＤ＝prisoner's dilenma、囚人のジレンマ）の集団における協力の問題にもアプローチしてきた。とりわけ、非特許文献６では進化的囚人ジレンマ設定におけるしっぺ返し（ＴＦＴ：tit-for-tat）戦略の成功が実証された。この設定では、プレイヤのペアは、繰り返されるＰＤゲームに含まれる。各プレイヤは、ＰＤペイオフ行列に基づいてあらゆるゲームラウンドが終了した後に更新されるスコアを保持する。最高のスコアを持つプレイヤは、最も適合するものと見なされ、それらの戦略は、他の適合しない戦略と置き換わって複製される。成功したＴＦＴ戦略は、以下の３つのシンプルなルールに従う。
１．最初は協力する−初めて競争相手と相互作用するときは常に協力する。
２．罰する−競争相手が前回のラウンドで離反した場合は、その競争相手を離反により罰する。
３．許す−競争相手が前回のラウンドで協力した場合は、その競争相手に離反の履歴が存在しても協力する。
【００２１】
ＴＦＴ戦略は、発展的に安定であることが示されており、協力者を悪用しようとする侵略的な離反者の小さな集団を絶滅へと追いやることができる。それと同時に、報復者（tit-for-taters）のグループは、常に互いに協力し合い、そのおかげで報復者達は、スコアを黒字に累積することができる。そして今度は、それを一時的な離反者のグループと闘うために使用することができる。
【非特許文献１】Lamport, Shostak, and Pease,「The byzantine general problem, Advances in Ultra-Dependable Distributed Systems」, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press, 1995
【非特許文献２】Zoran Despotovic, 「Building Trust-Aware P2P Systems, From Trust and Reputation Management to Decentralized e-Commerce Applications」 Diploma thesis, EPFL, Swiss Federal Institute of Technology, Lausanne
【非特許文献３】David M. Kreps and Robert Wilson, 「Reputation and imperfect information」, Journal of Economic Theory, 27:253-279, 1982
【非特許文献４】Michihiro Kandori and Hitoshi Matsushima, 「Private observation, communication and collusion」, Econometrica, 66(3):627-652, May 1998
【非特許文献５】George J. Mailath and Stephen Morris, 「Repeated games with almostpublic monitoring」, CARESS Working Papres almost-pub, University of Pennsylvania Center for Analytic Research and Economics in the Social Sciences, August 1999
【非特許文献６】Robert M. Axelrod, 「The Evolution of Cooperation」, Basic Books, 1984
【発明の開示】
【発明が解決しようとする課題】
【００２２】
本発明の課題は、ピアツーピア（Ｐ２Ｐ）ネットワークにおいてより信頼性の高い通信を実現することができるネットワークピアおよび通信方法を提供することにある。
【課題を解決するための手段】
【００２３】
上記課題は、請求項１に記載されたネットワークピアと請求項１５に記載された通信方法によって解決される。
【００２４】
本発明は、上記課題を解決するため、自身に関連する第１のサービスＩＤ（identification）を有するネットワークピアを提供する。本発明のネットワークピアは、第１の固有リクエストＩＤを有し、第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のサービス・リクエスト・メッセージを受信すると、前記第１のサービス・リクエスト・メッセージを別のネットワークピアへ送る手段を備えている。本発明のネットワークピアは、第１の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスが成功裏に提供されたか否かを示す指標（indication）を含むものであるフィードバック・メッセージを受信すると、前記フィードバック・メッセージをその他のネットワークピアへ送る手段を更に備えている。上記手段に加え、本発明のネットワークピアは、第２の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスをリクエストするものである第２のサービス・リクエスト・メッセージを受信すると、前記サービス・リクエスト・メッセージを前記指標に基づいて選択されたネットワークピアへ送る手段を更に備えている。
【００２５】
本発明は、上記課題を解決するため、ピアツーピア・ネットワークにおいて第１のサービスＩＤに基づいて通信するための方法（通信方法）も提供する。本発明の通信方法は、第１の固有リクエストＩＤを有し、第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のサービス・リクエスト・メッセージを受信すると、前記第１のサービス・リクエスト・メッセージをネットワークピアへ送るステップを含む。本発明の通信方法は、第１の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスが成功裏に提供されたか否かを示す指標（indication）を含むものであるフィードバック・メッセージを受信すると、前記フィードバック・メッセージを前記ネットワークピアへ送るステップを更に含む。上記ステップに加え、本発明の通信方法は、第２の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスをリクエストするものである第２のサービス・リクエスト・メッセージを前記指標に基づいて選択されたネットワークピアへ送るステップを更に含む。
【００２６】
本発明は、ピアツーピア・ネットワークにおける協力の問題は、既存のホップバイホップ・サービス・ロケーション機能（hop-by-hop service location functionality）の上に積み重ねることができるプロトコルを利用することで解決することができるという考えに基づいている。ネットワークのピア同士の間でシングル・フィードバック・メッセージを交換することができ、そのフィードバックに基づいて各ピアは、ローカルかつ独立に不具合の避け方を学習し、すなわち、正常に機能しないノードを特定することができる。本発明の方法は、例えば分散ハッシュテーブル（ＤＨＴ）を通じた情報のパブリック・シェアリング（公的共有）が一切存在しないという利点を提供する。さらに、ネットワークにおける学習プロセスは、協力をトータルで最大化し、サービス提供の不履行を減らすことができる。それゆえ、本発明の実施形態は、多くのピアツーピア・アプリケーション、とりわけユーザまたはピアが不正を働くことが利益だと分かるものにとって有効である。故に本発明の実施形態は、より信頼できる、より低コストのシステム運営を実現する。それらのおかげで、ピアツーピア・システムは、ピアまたはユーザの自主性がもたらす脅威をより強力に克服する。故に、本発明の実施形態は、全体としてシステムに対する有益な経済的効果をもたらすことができる。
【００２７】
ピア認証のピアツーピアベースの分散型実装は、従来のアプローチの問題であるピアの協力が必要である。本発明のアプローチでは、ピアの同一性（identity）が最小限必要とされるのみである。すなわち、通信リンクを確立した一対のピアの同一性は、その通信リンクの存続時間の間は変わらないことが保証される。言い換えると、通信リンクで通信している両方のピアは、リンクの他端におけるピアの同一性が通信中は変わっていない保証を必要とする。これは、例えばＳＳＬ（Secure Sockets Layer）といった周知のソリューションを利用してシンプルに実現される。
【００２８】
本発明の実施形態は、ピアツーピア・ネットワークにおける不満足なサービス提供または失敗したサービス提供を最適化、好ましくは最小化する仕組みを提供する。サービス提供が可能になる前に、サービスを提供するピアの位置が検索（あるいは特定）される必要がある。このサービス・ロケーション機能は、ピアツーピア・ネットワークにおいては一般的に分散して実施され、このため、それにはピア同士の間の協力が必要である。本発明の実施形態は、サービスリクエストが要求ピア（requesting peer）から発信され、要求されたサービスを提供することが可能なサービスプロバイダまでホップバイホップで経路指定（routing）される一般的なサービス・ロケーション・アルゴリズムを利用する。本発明の実施形態は、サービスリクエストがどのように経路指定されるべきかは指定せず、それは、アプリケーションまたは現時点で最新の経路指定メカニズムに委ねられる。しかしながら、サービス・ロケーションが不首尾に終われば、誤ったサービスが提供されたり、あるいはサービスが全く提供されない事態が起こりかねない。本発明の実施形態は、既存の基礎にあるサービス・ロケーション・プロトコル（従来技術の任意のサービス・ロケーション・プロトコルでよい）の上にフィードバック・プロトコルを構築することでサービス・ロケーションの失敗の数を減らす。
【００２９】
グローバルな同一性の必要をなくすほかに、本発明の実施形態は、他のアプローチ（非特許文献［Radu Jurca and Boi Faltings, Towards incentive-compatible reputation management, Trust, Reputation and Security: Theories and Practice (L. Korba R. Falcone, S. Barber and M. Singh, eds.), vol. Lecture Notes in AI 2631, Springer-Verlag, Berlin Heidelberg, 2003, pp. 138-147］参照）において協力を可能にするために必要とされるフィードバック・インセンティブ（feedback incentives）の必要性を取り除く必要もある。本発明の実施の一形態によれば、フィードバックは、強制的であり、意図的にフィードバック・メッセージを保留するネットワークノードのピアは、故障していると見なされ、それらからのサービスはドロップされる。
【００３０】
ほとんどの従来のアプローチでは、欠陥が検出されたピアは、ネットワークから隔離される。つまり、それには何のメッセージも送信されず、それから受信されたメッセージはドロップされる。本発明の実施形態は、ネットワークピアが故障の性質を学習し、欠陥ピアのまだ正常な機能の利用を最適化するという利点を提供する。それゆえ、本発明の実施の一形態によれば、正常に機能しないネットワークノードまたはピアは、そのまだ正常な機能が生きている限りはネットワークの協力にまだ含まれる。このおかげで、既存のアプローチより高いレベルの協力がもたらされる。故に、本発明の実施形態は、本発明の協力アルゴリズム（cooperation algorithm）が既存のホップバイホップ・サービス・ロケーション・プロトコルに組み込まれるという利点を提供する。本発明のプロトコルまたは通信方法は、ゼロから構築され、どの機能性もＤＨＴまたは認証インフラなどの他のレイヤに委譲することなく、送受信される全てのメッセージを完全に特定する。
【００３１】
さらに、本発明においてフィードバックは強制的であり、フィードバックを保留することは、別の故障／不具合と見なされるため、本発明の実施形態は、フィードバック・インセンティブを必要としない。さらに、本発明の実施形態は、部分的に欠陥のあるピアは、それらのまだ正常な機能の利用が最適化、好ましくは最大化されるため、本発明の実施形態によるネットワークからは完全に隔離されないとう利点を提供する。実装の観点から言えば、本発明の実施形態はシンプルかつ軽快であり、本発明のネットワークピアはそれらの観察または状態に関する情報を一切交換する必要はなく、シングル・フィードバック・メッセージのみが交換される。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施の最良の形態を添付図面を参照して詳細に説明する。
【００３３】
図１Ａに本発明のネットワークピア（network peer）１００を示している。ネットワークピア１００は、自身に関連する第１のサービスＩＤを有する。ネットワークピア１００は、第１の固有リクエストＩＤを有し、第１のサービスＩＤとは異なる第２のサービスＩＤを持つサービスをリクエストするものである第１のサービス・リクエスト・メッセージを受信すると、その第１のサービス・リクエスト・メッセージを別のネットワークピアへ転送する手段１１０を備えている。ネットワークピア１００は、第１の固有リクエストＩＤを有するフィードバック・メッセージを受信すると、そのフィードバック・メッセージをその他のネットワークピアへ転送する手段１２０を更に備えている。この場合のフィードバック・メッセージは、第２のサービスＩＤを持つサービスが成功裏に提供されたか否かを示す指標（indication）を含んでいる。ネットワークピア１００は、第２の固有リクエストＩＤを有し、第２のサービスＩＤを持つサービスをリクエストするものである更なるサービス・リクエスト・メッセージを受信すると、そのサービス・リクエスト・メッセージをその指標に基づいて選択されたネットワークピアへ転送する手段１３０を更に備えている。
【００３４】
実施の一形態において、ネットワークピア１００は、固有リクエストＩＤを有し、サービスＩＤを持つサービスをリクエストするものであるサービス・リクエスト・メッセージを作成する手段を更に備えている。ネットワークピア１００は、サービス・リクエスト・メッセージに関連する固有リクエストＩＤを有するフィードバック・メッセージを作成する手段を更に備えることができる。別の実施形態では、ネットワークピア１００は、異なる固有リクエストＩＤを有し、第１のサービスＩＤを持つサービスをリクエストするものである異なるサービス・リクエスト・メッセージを受信すると、第１のサービスＩＤを持つサービスを提供する手段を備えている。これらまたは他の実施形態において、サービス・リクエスト・メッセージを作成する手段は更に、有効期限タイマ（expiration timer）を開始するように構成され、フィードバック・メッセージを作成する手段は、リクエストしたサービスＩＤを持つサービスが提供される前に前記有効期限タイマが時間切れした際には、負の指標を有する負のフィードバック・メッセージを作成し、前記有効期限タイマが時間切れになる前に、リクエストしたサービスＩＤを持つサービスを受けた際には、正の指標を有する正のフィードバック・メッセージを作成するように構成されるものである。
【００３５】
他の実施形態では、第１のサービス・リクエスト・メッセージを転送する手段は、第１のサービス・リクエスト・メッセージを転送するときに第２の有効期限タイマを開始するように構成され、第２のサービス・リクエスト・メッセージを転送する手段は、第２の有効期限タイマが時間切れになる前に第１の固有リクエストＩＤを有するフィードバック・メッセージが受信されない場合には、第２のサービスＩＤを持つサービスは提供されていないと見なすように構成されるものである。
【００３６】
さらに、フィードバック・メッセージを作成する手段は更に、フィードバック・メッセージが正または負のいずれであるかを示す単一ビットをフィードバック・メッセージの中に含ませるように構成することができる。フィードバック・メッセージは、このとき固有リクエストＩＤと指標ビットとを含むものである。
【００３７】
他の実施形態では、第１または第２のサービス・リクエスト・メッセージを転送する手段は更に、それ自身に関する情報、第１または第２の固有リクエストＩＤ、第１または第２のサービスリクエストがそこから受信されたネットワークピア、第１または第２のサービスリクエストの発信源（origin）、または目標ネットワークピアを、転送される第１または第２のサービス・リクエスト・メッセージに含ませるように構成される。第２のサービス・リクエスト・メッセージを転送する手段は、本発明の実施形態における前記指標に基づく不具合予測（failure predictions）から成るテーブルからネットワークピアを選択するように構成することができる。さらに、前記不具合予測は、確率的概念学習（probabilistic concepts learning）に基づくことが可能である。実施の一形態によれば、前記不具合予測は、メッセージがそこから送信または転送された一つ前のネットワークピア（previous network peer）、メッセージをそこへ送信もしくは転送することが可能な次のネットワークピア、またはサービスＩＤの１つもしくはそれらの組み合わせを参照することが可能である。
【００３８】
第１の固有リクエストＩＤを持つフィードバック・メッセージを転送する手段は、そのフィードバック・メッセージを、第１の固有リクエストＩＤを持つ第１のサービス・リクエスト・メッセージが転送された先と同じネットワークピアへ転送するように構成することができる。これにより、本発明の実施の一形態によれば、ネットワークピアは、最初にサービスリクエストをその隣接するピアの１つへ転送し、次にフォワード・フィードバック（forward feedback）が受信されたときに、フィードバック・メッセージはまさに同じ隣接するピアへ転送される。このおかげで、不具合予測テーブルを全てのサービスリクエストにわたって管理することができる。本発明の実施形態は、ルーティングテーブルを管理し、サービス・ロケーション情報を提供する手段を更に備え得る。ルーティングテーブルを管理する手段は、分散ハッシュテーブルも管理し得る。
【００３９】
本発明の実施形態は、ピアツーピア・ネットワークにおける協力の問題を解決する。本発明の方法は、任意の既存の再帰的なホップバイホップ・サービス・ロケーション機能の上に積み重ねることが可能である。本発明の単一ビットのフィードバック・メッセージを利用し、それらをネットワークのピア同士の間で交換することによって、各ノードはフィードバックに基づいてローカルかつ独立に不具合を避けることを学習する。例えば、分散ハッシュテーブルを通じての情報のパブリックな共有は全く必要ない。本発明の実施形態は、サービス提供の不履行を低減または最小化しながら、協力をまとめて最適化または最大化する。
【００４０】
従って、本発明の実施形態は、協力を安定化するのにシステムワイドな認証またはどんなタイプのインセンティブ・システムの存在にも頼らない。本発明の実施形態は、フィードバックを強制的とし、それゆえフィードバックを保留することは、不具合と見なされる。さらに、他の解決法のように部分的に不具合のあるノードをネットワークから隔離する代わりに、ネットワークは、部分的に不具合のあるノードのまだ正常な機能を利用して協力を最適化することを学習する。
【００４１】
結果として生じる本発明の通信プロトコルまたは通信方法は、故障ケースにおいて非常に頑強であり、さらに多数の方法で拡張できるほかに、ピアツーピア用途において発生する特定の協力問題を解決するようカスタマイズすることもできる利点を有する。
【００４２】
それゆえ、本発明の実施形態は、協力方法またはアルゴリズムが従来から周知の既存のホップバイホップ・サービス・ロケーション・プロトコルに組み込まれる利点を提供する。従って、本発明の実施形態は、ゼロから構築されるプロトコル拡張を提供し、それは、どの機能性もＤＨＴまたは認証インフラなどの他のレイヤに委譲することなく送受信される全てのメッセージを完全に特定する。本発明の実施形態は、フィードバックが強制的であり、フィードバックの保留が不具合として取り扱われるので、フィードバック・インセンティブの必要性がないという利点を更に提供する。
【００４３】
さらに、部分的に不具合のあるピアは、本発明の実施形態によれば、それらのまだ正常な機能が最適化される、好ましくは最大化されるために、ネットワークからは完全に隔離されない。本発明の通信方法は、シンプルかつ軽快であり、本発明のネットワークピアは、観察または状態についての情報を一切交換する必要はなく、更に、単一ビットのフィードバック・メッセージのみが交換される。
【００４４】
次に、本発明の実施形態をさらに詳細に説明する。図１Ｂ、本発明の実施形態が既存のシステムにどのようにして組み込めるかを示している。図１Ｂは、アプリケーション２１０と、フォワード・フィードバック・プロトコル２２０と、不具合プレディクタ（predictor）２３０と、ｐ概念ランナー２４０と、サービス・ロケーション・プロトコル２５０とを示している。図１Ｂは、システムが異なる機能またはモジュールに分割され、それらが依存し合っている様子を示している。既に言及したように、サービス・ロケーション・プロトコル２５０は、従来技術から採用することが可能で、それは適切なサービスをホップバイホップのやり方で見つけ出す。本発明のフォワード・フィードバック・プロトコル２２０は、従来技術のサービス・ロケーション・プロトコル２５０にサービス提供の成功または失敗についてのフィードバック・メッセージを付加している。サービス提供のこれらの成功および失敗は、プロトコルからの任意のデビエーション（deviation）と一緒に不具合プレディクタ２３０に報告される。不具合プレディクタ２３０は、ルーティングサービスがサービスリクエストをサービスの提供を失敗に導きそうな次のホップまたは隣接するピアへ転送することを避けるよう要求するときに使用される。不具合プレディクタ２３０は、ｐ概念学習アルゴリズム２４０を利用してその予測を行うものである（非特許文献［Kearns and Schapire, "Efficient distribution-free learning of probabilistic concepts, Computational Learning Theory and Natural Learning Systems, Volume I: Constraints and Prospect", edited by Stephen Jose Hanson, George A. Drastal, and Ronald L. Rivest, Bradford/MIT Press, vol. 1, 1994］）。
【００４５】
図１Ｂにおいて、アプリケーション２１０は、例えばファイル検索またはファイルダウンロードなどの任意のアプリケーションであることが可能である。サービス・ロケーション・プロトコル（service location protocol）２５０は、サービスリクエストをホップバイホップのやり方でサービスリクエスタから、サービスリクエストまたはサービス・リクエスト・メッセージに指定されたサービスを提供するサービスプロバイダへ経路指定するサービス・ロケーション機能を提供する。サービスは、サービスリクエストの中でサービス記述子またはサービスＩＤによって指定される。単一のサービス記述子またはサービスＩＤは、唯一つのサービスだけでなく多くの異なるサービスと適合することができる。
【００４６】
次に、有向グラフＧ＝（Ｖ，Ｅ）をピア同士を繋ぐネットワークとする。ただし、Ｖはピアの集合、Ｅは一方向接続を表すピア対の集合である。outneigh：Ｖ→２Vとinneigh：Ｖ→２VをそれぞれＶのアウトリンク（outlinks）とインリンク（inlinks）で指し示されるピアの集合とする。Ｓをサービスの集合とし、offeredServices：Ｖ→２Sを所与のピアｖによって提供されるサービスの集合とする。
【００４７】
サービス記述子の集合をＤとする。matchedServices：Ｄ→２Sは、指定されたサービス記述子が適合するサービスの集合を返す。サービス・ロケーション機能は、単一関数selectNectHop：Ｓ×Ｖ×２V→Ｖとして表される。これは、場所が特定される必要のあるサービスのサービス記述子、現在のノードおよび可能な次のホップを引数とし、選ばれた次のホップを返す。
【００４８】
フォワード・フィードバック・プロトコル２２０は、サービスリクエストを経路指定するために、既存のホップバイホップ・プロトコルに付け加わる。サービスリクエスタからサービスプロバイダまでの指定経路上のあらゆるノードは、経路上のその１つ前のホップからフィードバック・メッセージを受信することを期待する。フィードバック・メッセージは、サービスが成功裏に提供されたか否かを記述する。第１のフィードバック・メッセージは、サービスリクエスタがサービスを受け取った後にそのサービスリクエスタによって送られる。続いて、サービスフィードバック・メッセージは、サービスリクエストがたどった経路と正確に同じ経路をたどってサービスプロバイダに到達するまで転送される。このプロセスを図２に示している。以下、そのアルゴリズムを詳しく説明する。
【００４９】
図２において、発信源（origin）２６０は、最初のステップにおいてサービス・リクエスト・メッセージを発行するサービスリクエスタ（service requestor）として機能する。サービス・リクエスト・メッセージは、複数の中間ピアまたはホップ２６５を含むピアツーピア・ネットワークを通ってサービスプロバイダ２７０まで経路指定される。次に第２のステップにおいて、サービスプロバイダ２７０は、サービスをサービスリクエスタまたは発信源２６０に提供する。発信源またはサービスリクエスタ２６０がサービスを受け取ったら、あるいは所定のタイマが時間切れした後にサービスが成功裏に受け取られなかった場合には、第３のステップにおいて発信源２６０は、フィードバック・メッセージを発行する。このフィードバック・メッセージは、サービス・リクエスト・メッセージが通過したのと正確に同じ中間ピアまたはホップ２６５を含むピアツーピア・ネットワークを進んでプロバイダ２７０に提供される。
【００５０】
サービスリクエスタの観点から言えば、アプリケーションがあるサービス記述子に対してrequestServiceを呼び出すと、ピア（サービスリクエスタ）はServiceRequestメッセージを生成し、それを適切な次のホップへ送る。そのピアは、その後、アプリケーションから、サービスが提供されたか否かを示すためのserviceProvidedコールを待つことになる。そのコールがタイムアウトＴservice内に起こらないとき、サービス提供は、失敗したと見なされる。サービスプロバイダの観点から言えば、サービスプロバイダは、このプロバイダがそれに対するサービスを提供することができるサービス記述子を持つServiceRequestを受信すると、サービス・リクエスト・メッセージの発振源（リクエスタ）にサービスが提供される。いくつかの転送ピアｖcの観点から言えば、その転送ピアが一つ前のホップｖphからサービスリクエストを受信すると、そのサービスリクエストを次のホップｖnhへ転送し、転送ピアｖcは、ｖphから、サービス提供が成功したか否かに関するフィードバックを待つことになる。そのフィードバックがタイムアウトＴfeedback内に到着しない場合、サービス提供は失敗したと見なされる。フィードバックがタイムアウトＴfeedback内に到着する場合、それは対応するサービスリクエストが以前にたどったのと同じ次のホップへ転送される。これは固有識別子（rid）をあらゆるサービスリクエストに割り当て、ｎhアレイで採用された次のホップを想起することによって実現される。
【００５１】
次に、本発明のネットワークピアまたは通信方法の実施形態を詳述するために、第１の疑似コードを示す。
＜擬似コード（第１バージョン）＞
【数２】
2008187702.tif 000004
【００５２】
function requestServiceおよびServiceRequest構文は、サービスリクエスタにおいてどのようにサービス・リクエスト・メッセージが作成されるかを示している。サービス・リクエスト・メッセージは、一つ前のホップと、サービスＩＤと、サービスリクエスタと、サービス記述子との情報を含んでよいことが分かる。この情報は、サービス・リクエスト・メッセージがサービスリクエスタで作成されたか中間のネットワークピアによって転送されたかに応じて、違った設定がなされる。さらに、receive ServiceRequestが示すように、サービスリクエストが受信される場合には、ServiceRequestの受信者自身がリクエストされたサービスを提供することが可能であるかどうかがチェックされる。可能な場合、リクエストされたサービスが発信者（リクエスタ）に提供される。サービス・リクエスト・メッセージの受信者がリクエストされたサービスを提供することができない場合、サービスリクエストは転送される。
【００５３】
function forwardServiceRequestは、サービスメッセージの転送がどのように実行されるかを示している。サービス・リクエスト・メッセージの転送先となる次ネットワークピアを決定するため、候補ホップ（cadidate hops）のリストが評価される。候補ホップの評価は、転送されたフィードバック・メッセージを基に行われる。本発明の実施の一形態によれば、それは転送されたフィードバック・メッセージから決定された信頼度情報に基づいている。
【００５４】
サービスが提供されたら、または所定の時間Ｔserviceが経過した後、function serviceProvidedは、サービスが成功裏に提供されたか否かを示す指標とサービスＩＤをと含むフィードバック・メッセージを作成する。フィードバック・メッセージが受信されたとき、フィードバック・メッセージの受信者がサービスプロバイダでなかった場合には、フィードバック・メッセージは転送される。フィードバック・メッセージの受信者がサービスプロバイダであった場合、フィードバック・メッセージはこれ以上どこにも転送されない。
【００５５】
実施の一形態として、上記フォワード・フィードバック（forward feedback）プロトコルは、サービス提供の全ての失敗を無視する。そこで上記アルゴリズムは不具合プレディクタ２３０に不具合（サービス提供の失敗）を報告し、不具合プレディクタ２３０を使って次のホップとしてどれを避けるべきかを決定するよう修正される。斯かるフォワード・フィードバック・プロトコル２２０の疑似コードの第２のバーション（修正版）を以下に示す。
＜擬似コード（第２バージョン）＞
【数３】
2008187702.tif 000005
【００５６】
最初のフォワード・フィードバック・プロトコルの擬似コードは、サービス提供の全ての失敗を無視した。そこで今度は、不具合プレディクタに不具合を報告して、不具合プレディクタを使って次のホップとしてどれを避けるべきかを決定するようにアルゴリズムを修正する。第２の疑似コードに斯かる完璧な形のフォワード・フィードバック・プロトコルを提示する。不具合プレディクタに報告されるものは、サービスリクエストが転送されたコンテクストと、その転送の結果、当該サービスの提供が成功したか否かとを記述するサンプルである。サンプルｓ＝（ｐｈ，ｎｈ，ｓｄ，ｂ）∈Ｖ×Ｖ×Ｄ×｛０，１｝は、サービスリクエストがそこから受信された一つ前のホップ（ph=previous hop）と、サービスリクエストが転送された先の次のホップ（nh=next hop）と、リクエストのサービス記述子（sd=service descriptor）と、そのホップがサービス提供の成功をもたらしたかどうかを示すブールリアンフラグ（Boolean flag）ｂとから成る。ｂ＝１のとき、サンプルは、正（positive）、それ以外の場合はサンプルは負（negative）である。一つ前のホップは、リクエスタでは空（null）、次のホップは、プロバイダでは空（null）である。報告されたサンプルの集合が与えられた上で、不具合プレディクタ２３０は、サービス提供において不具合を引き起こす可能性のある疑いがかかった次のホップを返信する。疑いがかかった次ホップは、このあと次のホップの候補のリストから外され、それ以後、サービス提供には考慮されないようにすることができる。次のホップは、一時的にのみ疑いがかけられる可能性があり、サンプルが報告されるときに、不具合プレディクタによって返信された疑いのかかった次のホップの集合は、変わる場合がある。全ての次のホップに疑いがかけられる場合も起こり得る。この場合、サービスリクエストは、取り下げられる。これはNHnullイベントとして定義される。
【００５７】
不具合プレディクタは、サンプルを蓄積し、それらに基づいてコンテクストトリプル（ｐｈ，ｎｈ，ｓｄ）∈Ｖ×Ｖ×Ｄがサービス提供の成功という結果をもたらすかどうかの予測を行う。学習タスクは、与えられたコンテクストトリプル及びサンプル集合における成功の確率を学習することである。Rivestの決定リスト（非特許文献［Ronald L. Rivest, "Learning decision lists", Machine Learning 2 (1987), no. 3, 229-246］参照）に基づく確率的概念（ｐ概念）学習と称される学習法が採用される（非特許文献［Kearns and Schapire,「Efficient distribution-free learning of probabilistic concepts, Computational Learning Theory and Natural Learning Systems, Volume I: Constraints and Prospect」, edited by Stephen Jose Hanson, George A. Drastal, and Ronald L. Rivest, Bradford/MIT Press, vol. 1, 1994］参照）。
【００５８】
概念（concept）は、ドメイン集合Ｘ上で定義されたブーリアン関数である。Rivestは、サンプルの集合（ｘ，ｂ）（ｘ∈Ｘおよびｂ∈｛０，１｝はラベル）が与えられたときに、未知の概念が集合ｋ−ＤＬ（ＤＬ＝decision list）、すなわち連言節がサイズｋの決定リストに属する場合に、その概念が効率的に学習できることを示した。集合ｋ−ＤＬは、決定木（decidion trees）と、節あたりｋリテラルの集合ｋ−ＤＮＦ（ＤＮＦ＝disjunctive normal form、選言標準形）と、ｋ−ＣＮＦ（ＣＮＦ＝conjunctive normal form、連言標準形）とを含んで表すのに十分である。Kearns等は、この結果を確率的概念（probablistic concepts）、すなわちｃ：Ｘ→［０，１］の形の関数にまで拡張した。ここでｃ（ｘ）は、正のサンプル（ｘ、ｂ＝１）を観測する確率と解釈される。
【００５９】
Kearnsは、予測集合Ｆn上の確率的決定リストｃを（ｆ1，ｒ1），．．．，（ｆs，ｒs）となるように定義する。ただしｆi∈Ｆnおよびｒi∈［０，１］である。ｃ（ｘ）の値は、ｆj（ｘ）が真（true）となるような最小のｊに対するｒjである。決定リストは、１≦ｉ＜ｓに対して｜ｒi−ω｜≧｜ｒi＋１−ω｜の場合にω収束する。斯かるリストは、Kearnsのアルゴリズムによって出力される。ω＝１／２に対するリストの特別なケースが使用され、これは確信度が低下する順のリストに対応する。最も確かな述語（０または１に最も近いｒjの値を持つもの）は、リストの最前部にあり、一番目と適合する。この場合、ドメインＸは、全てのコンテクストトリプルの集合Ｘ＝Ｖ×Ｖ×Ｄである。述語の集合Ｆnは、以下の特性を有する。
・各述語は、シングルリテラルまたは２つ以上のリテラルの間の連言（論理積）である。
・３タイプのリテラルが存在する。
（１）ｐｈ＝ｖi、ｖi∈Vの形の一つ前のホップ（previous hop）リテラル、
（２）ｎｈ＝ｖj、ｖi∈Vの形の次のホップ（next hop）リテラル、
（３）ｓｄ＝ｄi、ｄi∈Ｄの形のサービス記述子リテラル。
・述語は、各タイプごとに最大１つのリテラルに言及することができる。このことから、述語は最大３つのリテラルを有することができると言える。
【００６０】
例えば、述語ｐｈ＝ｖ12∧ｓｄ＝ｄ4は、Ｆnに属するが、一方、述語ｐｈ＝ｖ12∧ｓｄ＝ｄ4∧ｐｈ＝ｖ15は、属さない。述語集合Ｆnは、Kearnsのｐ概念アルゴリズムを実行する前にサンプル集合Ｓからもたらされる。あらゆるサンプルｓ＝（ｐｈ＝ｖi，ｎｈ＝ｖj，ｓｄ＝ｄk，ｂ）∈Ｓに対して、次の最大７つの対応する述語を生成することが可能である。
（１）ｐｈ＝ｖi、
（２）ｎｈ＝ｖj、
（３）ｓｄ＝ｄk、
（４）ｐｈ＝ｖi∧ｎｈ＝ｖj、
（５）ｐｈ＝ｖi∧ｓｄ＝ｄk、
（６）ｎｈ＝ｖi∧ｓｄ＝ｄk、
（７）ｐｈ＝ｖi∧ｎｈ＝ｖi∧ｓｄ＝ｄk
【００６１】
サンプル集合Ｓとそれからもたらされる述語集合Ｆnが与えられた上で、ｐ概念アルゴリズムが実行され、決定リストが生成される。各可能なｎｈごとに、引数がｐｈおよびｓｄの関数getSuspectedNextHopsが呼び出されると、コンテクストトリプル（ｐｈ，ｎｈ，ｓｄ）が生成され、その特定のコンテクストトリプルに対する成功確率を計算するために決定リストが参照される。その確率が所定の閾値ｐminより低い場合、ｎｈは、疑わしいと見なされる。決定リストに適合する述語が存在しない場合、確率１．０が想定される。特に、Ｓが要素を全く持たない初期段階において決定リストが空のときに、これは全てのコンテクストトリプルに対して起こる。これは、不具合プレディクタの初期オプティミズム（initial optimism）と呼ばれる。サンプル集合Ｓの大きさは、Kearnsによって記述された最小範囲には収まらない。これらの範囲は、非現実的であるからである。比較的大きなエラー（γ＝０．１、ε＝０．１、δ＝０．１）が許されるとしても、必要サンプルの最小量は１０6のオーダにある。代わりに、サンプル集合を管理するのにシンプルヒューリスティックが使用される。
【００６２】
２つのＦＩＦＯキュー（First In, First Out queues）が存在する。１つは正のサンプルだけを含むキューＳ+と、もう１つは負のサンプルだけを含むキューＳ-である。これらのキューのサイズの上限は、Ｓmax+とＳmax-に設定され、定数である。新たなサンプルが到着すると、そのサンプルは、キューの最初に挿入される。キューのサイズがその最大サイズより大きいと、キューの最後の要素が取り除かれる。サンプル集合Ｓは、述語帰納（predicate induction）とｐ概念アルゴリズムとを実行する前に、Ｓ-∪Ｓ+に設定される。Kearnsのアルゴリズムに特有の第２の限界は、ラベルｂの値とは無関係に、述語に適合する、その述語を決定リストの一部と考えるのに必要なサンプルの最小数である。その限界は、残念ながら現実的でもない。もっと低い限界ｎacceptを使用することが可能であり、それは実験的に十分であることが示され得る。決定リストを新たなサンプルが到着するごとに毎回計算し直すことはコストがかかる。決定リストは定期的にｎr番目ごとにサンプルを計算する。
【００６３】
カスタム開発されたイベント駆動型（event-driven）シミュレータにおいて、各イベントは仮想的なシミュレーション時間（simulated time）のある特定の瞬間に起こり、このセクションにおいて時間と言えば全て、実時間ではなく、このシミュレーション時間に関係する。サービスロケーショングラフは、Chordにおけるように単位リング上にピアを配置することによって生成される（非特許文献［Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan, 「Chord: A scalable Peer-To-Peer lookup service for internet applications」, pp. 149-160］参照）。最初の隣人が現ノードにリング距離で最も近いノードに接続するようにコネクションが生成され、あらゆる次ノードは、最大距離に到達するまで２倍ほど遠い。最大の理論的なリング距離は０．５であるが、しかし単一の接続が張ることができる最大距離は０．１に設定できる。これの目標は、必要なルーティングホップの平均数を人為的に増大することである。これはアルゴリズムを評価するためのよりやりがいのある設定を提供する。ホップの数が増えると、サービスリクエストのルーティング中に欠陥ノードに遭遇する確率は高くなる。
【００６４】
シミュレートされたオーバーレイにおける各正常な、つまり欠陥のないピアは、ポアソン過程においてサービスリクエストを生成する。生成速度は全てのノードにわたって同じで、毎秒１リクエストに等しい。サービスリクエストが作成されるごとに、そのサービス記述子が全ての可能な記述子の集合から一様にランダムに選択される。
【００６５】
シミュレーション実行はいくつかの測定時期（measurement epochs）に分割される。各測定時期の始めに全ての測定変数がリセットされる。測定時期の終わりには蓄積された測定値が記録される。各測定時期は、デフォルトで１０秒継続する。全てのメッセージは１００ｍｓと２００ｍｓの間に一様に分布する待ち時間で配信される。基礎となるネットワークトポロジーはエクスプリシットにシミュレートされない。このネットワークモデルは、このプロトコルを評価するのに十分である。
【００６６】
ピアがフォワード・フィードバック・プロトコルから逸脱することができる多数の方法が存在する。障害は次のような方法でモデリングされる。デビエーション（deviation）π∈Ｐは、ピアが従うフォワード・フィードバック・プロトコルにおける自動変更である。無条件デビエーションは、π∈Ｐuはピアのプライベート状態に依存しないデビエーションであり、特に受信メッセージの履歴を含む。条件付きデビエーションπ∈Ｐcは、プライベート状態に依存するデビエーションである。Ｐ＝Ｐu∈Ｐc。ピアの振る舞いφ∈２Pは、振る舞いを構成するデビエーションの集合である。正常なピアは、φ＝Φ（空）を有する。次のような可能な無条件デビエーションの集合Ｐuが議論される。
・Ｇ−一般的な障害
・GDef−サービスの提供に失敗する、または不満足な方法でサービスを提供する。
・GNoFP−不具合プレディクタに全くサンプルを報告しない。
・GNoWorkload−全くサービスリクエストを送信しない。
・Ｍ−変異障害（mutation failures）
・MRq−変異したサービスリクエストを送信する、いずれかのフィールドが変更された。
・MRe−変異したサービスリスポンスを送信する、いずれかのフィールドが変更された。
・MF−変異したフィードバック・メッセージを送信する、いずれかのフィールドが変更された。あるいは、
・MF0−フィードバック・メッセージを失敗に変更する。
・MF1−フィードバック・メッセージを成功に変更する。
・Ｏ−怠慢障害（omission failures）−メッセージが期待されるように送信されない。
・ORq−サービスリクエストの送信または転送を怠る。
・ORe−サービスリスポンスの送信または転送を怠る。
・OF−フィードバック・メッセージの送信または転送を怠る。
・Ｉ−挿入障害（insertion failures）−メッセージが送られるが、プロトコルによればそれは送られるべきではない−このクラスの障害は、自明に処理できるので階層には展開されない。
【００６７】
条件付きデビエーションは、ｃ→π∈Ｐu、ｃ∈Ｃおよびπ∈Ｐの形を有する。これは、“条件ｃは無条件デビエーションπを引き起こす”と読む。以下の条件（集合Ｃ）が定義される。
・Ctx[*]−受信されたフィードバック・メッセージまたはサービスリクエストのコンテクストトリプルは以下の特性を有する。
Ctx[ph=vi]−一つ前のホップはｖiである。
Ctx[nh=vi]−選ばれた次のホップはｖiである。
Ctx[sd=di]−サービス記述子はｄiに設定される。
・F[success=s]−受信されたフィードバック・メッセージは、ｓにセットされた成功フラグを有する。
・全知の競争相手（Omniscient adversary）−ある競争相手が、ネットワーク内の全ての欠陥ノードにおける全てのプライベート状態と、送信／受信メッセージの完全な知識とを有し、その知識から次のような何か新しい条件が引き出せると仮定される。
PFaulty−サービスプロバイダが欠陥ノードである場合に真。
RFaulty−サービスリクエスタが欠陥ノードである場合に真。
・条件を含む述語（Predicate involving conditions）−任意のブーリアン表現へ条件を一般化することで、他の条件がリテラルとして現れる。
【００６８】
割合αのピアが同じ欠陥のある振る舞いφfを示し、割合（１−α）のピアが正常であるようなケースにおけるフォワード・フィードバック・プロトコルの回復力が検査される。欠陥のあるピアは、集団内に一様にランダムに分布している。φfの以下のケースが議論される。
・DEFECTOR− GDef, GNoFP, GNoWorkload
・DROPPER− ORq, OF, GNoFP, GNoWorkload
・WHITELIAR− MF1, GDef, GNoFP, GNoWorkload
・BADMOUTHER− MF0, GDef, GNoFP, GNoWorkload
・SMARTLIAR− PFaulty→MF1, ¬PFaulty→MF0, GDef, GNoFP,GNoWorkload
・QUIET− GNoWorkload
上記振る舞いの全ては、不具合プレディクタのインスタンスを実行しない（GNoFP）、なぜなら、これは、協力レベルを改善できるだけだからである。それらはサービスリクエストも作成しない（GNoWorkload）、なぜなら、潜在的に協力を増やせるからである。
【００６９】
DEFECTORは、それが良いサービスを決して提供しない以外は全ての側面で正しく振る舞う。DROPPERは、全てのサービスリクエストと全てのフィードバック・メッセージを一貫してドロップする。WHITELIARは、成功フラグを、それが転送する全てのフィードバック・メッセージに対して真（true）に設定する。逆に、BADMOUTHERは、成功フラグを偽（false）に設定する。SMARTLIARは、欠陥のあるサービスプロバイダが良く言われ、正常なサービスプロバイダが悪く言われる最悪ケースの嘘をつく。ＱＵＩＥＴの振る舞いは、サービスリクエストのトラフィック量が異常な振る舞いのケースと同じ基本シナリオを生成するために使用される。
【００７０】
異なる振る舞いのほかに、サービスのピアへの次のような異なる割当も使用される。
・one−to−one（１対１）−各ピアは１つのサービスしか提供しない。各サービスは唯一つのピアによって提供される。
・many−on−one（多対１）−サービス数はピア数に等しい。各サービスは平均４つのピアによって提供される。
【００７１】
one−to−oneのケースでは、プロバイダに欠陥があれば、サービスを提供する他の手段は全くない。many−on−oneのケースでは、サービスが代わりの正常なプロバイダによって提供されるチャンスがある。両方のケースでは、サービスあたり１つのサービス記述子が存在し、あらゆるサービス記述子は唯一つのサービスと適合する。シミュレーションの際のパラメータは、次のようなものである。ネットワークには２００個のノードが存在する。確率ｐminは０．５に設定されたとする。つまり、決定リストのエントリは、コンテクストトリプルが不具合プレディクタによって成功と見なされるためには少なくとも０．５の確率を持たなくてはならない。Ｓmax+とＳmax-は、１０００に設定され、キューが飽和すると正および負のサンプルの数は等しく、サンプル集合の釣り合いがとられる。決定リストは、ｎr＝３０サンプルごとに学習し直される。また、述語が決定リストに置くことができる前に必要なｎaccept＝１０個の適合サンプルが存在する。全てのφfに対して、αは０．２５、すなわち集団の２５％に欠陥がある。ＴfeedbackおよびＴserviceは、共に１０秒に設定される。
【００７２】
システムにおける次のイベントがカウントされる。
・coop−サービス提供が成功した。
・def−サービスプロバイダは、リクエスタにサービスを不満足な方法で提供した、またはサービスを一切提供しなかった。
・NHnull−全ての次のホップが不具合プレディクタによって疑わしいとされた。
・SRtimeout−リクエスタにおいて、Ｔservice前にserviceProvided関数がアプリケーションによって呼び出されなかった。つまり、アプリケーションに欠陥がなければサービスは提供されていない。
・FBtimeout−フォーワーダ（forwarder）またはサービスプロバイダにおいて、Ｔfeedback前にフィードバック・メッセージが到着していない。
これらのカウントの各カウントは、１０秒の１測定期間にわたって累積的に集約される。結果を図３ａ乃至図３ｉに提示する。これらの図の中のグラフは、シミュレーション時間に対するそれぞれのイベント数を示している。
【００７３】
図３ａのシナリオは、２５％のピアに対してサービスリクエストの送信を止め、同数のピアがGNoWorkload デビエーションを有する残りの実験にベースラインを提供する。測定期間ごとに最大可能協力数（１０００）が得られる。図３ｂのシナリオでは、１つのピアに対して唯１つのサービスが存在する。ネットワークは、サービスリクエストを、それらを配信して間違ったサービスリクエストのリスクを取るよりも、リクエスタにおいて直ちにドロップすることを学習する。欠陥ノード上にある２５％のサービスは、プロバイダには決して成り得ないため、最大可能協力数は７５０である。
【００７４】
図３ｃのシナリオは図３ｂと同じだが、今回はシングルサービスに対応する多くのピアが存在するという違いがある。所与のサービスに対して、それを提供する一部のノードに欠陥があっても、代替ノードを見つけることが可能である。ネットワークはそれを学習し、協力数は理論的最大値１０００に達する。図３ｄのシナリオは、部分的に欠陥のあるノードがそれらの一部の機能を失っているのにもかかわらずネットワークにおいてどのようにまだ使用されるかを示している。各DROPPERは、他のノードが提供することができないシングルサービスを提供する責任を負う。もしそれがネットワークから隔離されたとしたら、そのサービスは提供できなくなってしまっていたであろう。ネットワークは、転送のためにドロッパ（droppers）を避けることを学習し、タイムアウト数は減るが、それらはまだサービスプロバイダとして利用され、長い時間をかけて最大協力数に達することになる。
【００７５】
図３ｅおよび図３ｆのシナリオは、どのような形の一貫した嘘も最大協力レベルへの到達を妨げることはないことを示している。またそれは失敗したサービス提供の数を高く維持することも妨げない。図３ｅのケースでは、GDefピアが良いように嘘をつかれていることを学習するのに多大な時間がかかる。
【００７６】
図３ｇおよび図３ｈのシナリオは、最も有害な形の嘘にネットワークがどのように対処するかをデモンストレーションしている。両方のケースone−on−one（１対１）およびmany−on−one（多対１）において最大の理論的な協力レベルに到達する。図３ｇのシナリオでは、最初に、多数のタイムアウトが存在しており、このタイムアウトは、正確に動作するのに十分なサンプルを集められなかった不具合プレディクタにおいて不当な疑いがかけられた次のホップの突然の増加によって引き起こされたものである。時間の経過とともに不具合プレディクタは、負のフィードバックが特定の次のホップまたはサービス記述子よりも一つ前のホップ（嘘つき）と関連があることにより確信を持つようになる。結果、これらの前のホップからのサービスリクエストは、ドロップされる。このようにして、嘘ついたものは、フォーワードサービスリクエストの信頼できる転送先となる次のホップを解放する。最後には嘘ついたものからサービスリクエストを受け取る次のホップは、存在しなくなり、嘘ついたものは、効率的にドロッパ（droppers）になる。それが一旦起こると、それらはもはやフォーワーダとして利用されず、それらがフィードバック・メッセージに嘘を入れ込むことは絶対にできなくなる。嘘ついたものが、消滅し、協力性が安定化する。
【００７７】
全てのテストケースにおいて、２５％のノード（これは大規模システムでは大きな割合を占める）に欠陥があっても、協力レベルは、均衡状態においてその理論的最大値に到達する。実現可能性評価は、他のアプローチで一般的に議論されるタイプの誤動作のみに限定され、全ての可能なタイプの誤動作をカバーしない。これはプロトコルが少なくともその他のものと同程度に頑強であることを実証している。
【００７８】
本発明の実施形態は、協力方法またはアルゴリズムが従来技術で知られている既存のホップバイホップ・サービス・ロケーション・プロトコルに組み込まれるという利点を与える。本発明の実施形態は、ゼロから構築されるプロトコル拡張を提供し、それはどの機能性もＤＨＴまたは認証インフラなどの他のレイヤに委譲することなく送受信される全てのメッセージを完全に特定する。本発明の実施形態は更に、フィードバックは強制的であるとともにフィードバックの保留は故障（あるいは不具合）として取り扱われるので、フィードバック・インセンティブの必要性が全くないという利点を更に与える。
【００７９】
さらに、部分的に欠陥のあるピアは、それらのまだ正常な機能の利用が最適化、好ましくは最大化されるため、本発明の実施形態によるネットワークからは完全に隔離されない。本発明の通信方法は、シンプルかつ軽快であり、本発明のネットワークピアは観察または状態に関する情報を一切交換する必要はなく、更に、単一ビットのフィードバック・メッセージのみが交換される。
【００８０】
本発明の方法の一定の実施要件に応じて、本発明の方法はハードウェアまたはソフトウェアで実施が可能である。本発明の実施は、本発明の方法が実行されるようにプログラム可能なコンピュータシステムと協働することができるデジタル記憶媒体、特に電子読み取りが可能な制御信号が保存された磁気ディスク、ＤＶＤまたはＣＤを使用して行うことができる。従って、本発明は、コンピュータ上で実行させた際に本発明の方法を実行する働きをするプログラムコードが機械読み取り可能な媒体に記憶されたコンピュータ・プログラム製品である。言い換えると、本発明の方法は、コンピュータ上で実行させた際に本発明の少なくとも１つの方法を実行するためのプログラムコードを有するコンピュータ・プログラムである。
【図面の簡単な説明】
【００８１】
【図１Ａ】本発明の実施の一形態によるネットワークピアの略構成図である。
【図１Ｂ】本発明の方法が既存プロトコルと相互作用する様子を示す図である。
【図２】ピアツーピア・ネットワーク内における本発明の実施の一形態による通信方法の手順を示す図である。
【図３ａ−３ｃ】本発明の実施形態を調べたシミュレーション結果を示す図である。
【図３ｄ−３ｆ】本発明の実施形態を調べたシミュレーション結果を示す図である。
【図３ｇ−３ｉ】本発明の実施形態を調べたシミュレーション結果を示す図である。
【符号の説明】
【００８２】
１００  ネットワークピア
１１０  第１のサービス・リクエスト・メッセージを転送する手段
１２０  フィードバック・メッセージを転送する手段
１３０  第２のサービス・リクエスト・メッセージを転送する手段
２１０  アプリケーション
２２０  フォワード・フィードバック・プロトコル
２５０  サービス・ロケーション・プロトコル
２３０  不具合プレディクタ
２４０  ｐ概念ラーナー
２５０  サービス・ロケーション・プロトコル
２６０  発信源／リクエスタ
２６５  中間ピア／ホップ
２７０  プロバイダ
【図１Ａ】
2008187702.tif 000006
【図１Ｂ】
2008187702.tif 000007
【図２】
2008187702.tif 000008
【図３ａ−３ｃ】
2008187702.tif 000009
【図３ｄ−３ｆ】
2008187702.tif 000010
【図３ｇ−３ｉ】
2008187702.tif 000011
【外国語明細書】
2008187702.tif 000012
2008187702.tif 000013
2008187702.tif 000014
2008187702.tif 000015
2008187702.tif 000016
2008187702.tif 000017
2008187702.tif 000018
2008187702.tif 000019
2008187702.tif 000020
2008187702.tif 000021
2008187702.tif 000022
2008187702.tif 000023
2008187702.tif 000024
2008187702.tif 000025
2008187702.tif 000026
2008187702.tif 000027
2008187702.tif 000028
2008187702.tif 000029
2008187702.tif 000030
2008187702.tif 000031
2008187702.tif 000032
2008187702.tif 000033
2008187702.tif 000034
2008187702.tif 000035
2008187702.tif 000036
2008187702.tif 000037
2008187702.tif 000038
2008187702.tif 000039
2008187702.tif 000040
2008187702.tif 000041
2008187702.tif 000042
2008187702.tif 000043
2008187702.tif 000044
2008187702.tif 000045
2008187702.tif 000046
2008187702.tif 000047
2008187702.tif 000048
2008187702.tif 000049
2008187702.tif 000050
2008187702.tif 000051
2008187702.tif 000052
2008187702.tif 000053
2008187702.tif 000054
2008187702.tif 000055
2008187702.tif 000056