(57)【要約】  通信ネットワークにおいてグループ通信を処理する方法であって、グループの参加クライアントを容認し構成するステップと、参加クライアント間のストリームメディアの指示された交換のために通信セッションを確立し、通信リソース、特に、ストリームメディアの交換の指示を調整する、すなわち、クライアントが通信リソースを要求した場合、この通信リソースをこのクライアントに再割り当てするステップと、参加ピアＰ１、Ｐ２、Ｐ３によってピアツーピアネットワークを介して参加ピアに発信されたストリームメディアをパイピングし、要求１’によって選出を開始することにより相互排除通信リソースを調整し、ピアツーピアネットワークを使用してピア間の分散選出アルゴリズムによって公正かつ有効に同時要求２’、４’、７’、６’を解決するステップとを含む方法に関する。
2008541519.tif 000002
【特許請求の範囲】
【請求項１】
グループの参加クライアントを容認し構成するステップと、
参加クライアント間のストリームメディアの指示された交換のために、通信セッションを確立するステップと、
通信リソースを要求したクライアントにこの通信リソースを再割り当てすることにより、通信リソース、特にストリームメディアの交換の指示を調整するステップと
を含む、通信ネットワークにおいてグループ通信を処理する方法であって、クライアントが通信ネットワークにおいてピアとして対称的に編成され、
参加ピア（Ｐ１、Ｐ２、Ｐ３）の前記グループのうちの少なくとも１つの参加ピア（Ｐ１、Ｐ２、Ｐ３）をソースピアとして選出することと、
少なくとも１つの参加ピアによって発信されたストリームメディアをピアツーピアネットワークを介して参加ピアに送信するためにパイプを使用することと、
デッドロックもなくスターベーションもない（１’、２’、４’、７’、６’）分散相互排除アルゴリズムを使用することにより送信するために、ピアのうちの１つによる通信リソースへの排他的アクセスを保証することと
により、ストリームメディアの交換の指示を調整するために参加クライアント間のピアツーピアネットワークが確立されることを特徴とする、方法。
【請求項２】
リソースが、ストリームメディアを他の参加ピアに送信する機能を提供するプッシュツートークサービスであることを特徴とする、請求項１に記載の方法。
【請求項３】
選出アルゴリズムが、任意選択でＲｉｃａｒｔ−Ａｇｒａｗａｌａ最適化を含むＬａｍｐｏｒｔｓのアルゴリズムであることを特徴とする、請求項１に記載の方法。
【請求項４】
選出アルゴリズムが、Ｓａｎｄｅｒｓアルゴリズムなどの情報構造体ベースのアルゴリズムであることを特徴とする、請求項１に記載の方法。
【請求項５】
前記参加クライアントのうちの１つのストリームメディアの注入によって要求がトリガされ、要求が受け容れられるまで遅延されることを特徴とする、請求項１に記載の方法。
【請求項６】
ストリームメディアの注入が、選出が前記参加クライアントのうちの１つへの一意のリソースの割り当てを保証するように音声検出によって検出された音声であることを特徴とする、請求項５に記載の方法。
【請求項７】
通信ネットワークにおいてグループ通信を処理するためのコンピュータソフトウェア製品（ＳＶＣ）であって、請求項１に記載の方法を実施するためのプログラミング手段を含むことを特徴とする、コンピュータソフトウェア製品（ＳＶＣ）。
【請求項８】
請求項７に記載のコンピュータソフトウェア製品（ＳＶＣ）を含むことを特徴とする、ネットワーククライアント（ＣＤ１、ＣＤ２、ＣＤ３）。
【請求項９】
請求項８に記載の複数のネットワーククライアント（ＣＤ１、ＣＤ２、ＣＤ３）を含むことを特徴とする、通信システム（ＣＮＷ）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、耐障害性の高信頼性ストリーム処理のための方法に関する。本発明はまた、コンピュータソフトウェア製品、ネットワーククライアント、およびそれらのための通信システムにも関する。
【背景技術】
【０００２】
（セルラ）ネットワークを介してのプッシュツートーク（ＰＴＴ）は、（セルラ）ネットワークに新しいリアルタイム直接１対１および１対多の音声通信サービスを導入する。このサービスを裏付ける通信の原理は単純であり、押して話すだけである。「常時オン」接続のおかげで、すなわち、セルラネットワークがサービスをサポートし、利用可能であり、過負荷でなければ、通常、加入者は加入後、追加の手段（ダイヤルアップなど）なしにサービスに直接アクセスすることができるので、キーを押すだけで個人にも通話グループにもコールが開始されることができる。コール接続はほとんど瞬間的であり、受信者はコールに応答しなくてもよい。
【０００３】
共用チャネルがいくつかの移動局によって制御されるようなシステムは、米国特許出願公開第２００３／００５００８３号Ａ１から知られる。
【０００４】
プッシュツートークサービスのユーザは、通常、電話コール以外の何らかの活動に従事していて、その活動中にグループトラフィックをリスンする。ユーザは、名指しでコンタクトされることができ、時々グループに何か言いたいと思うこともあり得る。そのような使用例には半二重トラフィックが理想的である。
【０００５】
プッシュツートークサービスは、既存のセルラサービスの代替物ではないので、正真正銘の差別化音声サービスである。
【０００６】
プッシュツートークサービスはまた、ＩＰ（インターネットプロトコル）マルチメディアサブシステム（ＩＭＳ）におけるＩＰマルチメディア通信サービスの不可欠な構成部分でもよい。たとえば、モバイルネットワークを介しての半二重ボイスオーバＩＰ（ＶｏＩＰ）技術に基づいていてもよい。ＩＰ技術のおかげで、プッシュツートークサービスは、セルラアクセスおよび無線リソースを回路スイッチセルラサービスより効率よく使用し、ネットワークリソースを全コールセッションの間ではなくトークスパートの継続期間の間だけ保持する。
【０００７】
ＰＴＴを実施し運用することは、たとえば音声品質を含む最良の成功のために考慮され、最終的に解決／管理されなければならない多くの問題があるので単純な問題ではない、すなわち、ＰＴＴのためのＩＰ技術の使用は、ちょうどサービス品質（ＱｏＳ）が固定ネットワーク上でのＶｏＩＰに関して問題であるように、音声のＱｏＳ、コールセットアップ時間、すなわちＰＴＴセッションに参加するユーザを選出した瞬間から会話を開始することができる時間までの継続期間、またはＰＴＴの相互運用性の問題を固有に追加する。
【０００８】
ＰＴＴの核心には、ＩＰ通信および無線ソフトスイッチネットワークのインフラストラクチャのために使用されるセッション開始プロトコル（ＳＩＰ）として知られているＩＥＴＰ標準化プロトコルがある。ＰＴＴは、ＩＰをトランスポート／ベアラとして使用するので、２．５Ｇおよび３Ｇ技術およびインフラストラクチャの発展、拡張および改良に高度に依存する。オープンモバイルアライアンス（ＯＭＡ）は、独自のアプローチから技術およびサービスプロバイダの間で一様かつシームレスに動作するはずであるよりオープンなアプローチまでのＰＴＴの進化の結果であるプッシュツートークオーバセルラ（ＰｏＣ）をサポートするインフラストラクチャおよびプロセスを標準化する。ＯＭＡは以下のインフラストラクチャネットワーク要素を提供するように努めている。
ＳｉＰシグナリングおよび音声バーストのためのエンドポイント、参加者リスト配布の処理、課金システムへの報告、およびメディア配布などの機能を提供する、サーバ側論理を含むＰｏＣサーバ。
ＳＩＰプロキシおよびＳＩＰレジスタを含むＩＭＳコア。ＵｅはＰｏＣサーバへのＳＩＰシグナリングのためのＩＭＳコアにアクセスする。ＩＭＳコアはまた、認証およびアカウンティング機能、ならびにパーソナルおよびグループインスタントトークセッションのトリガリングを処理する。グループ／リストマネージャサーバ（ＧＬＭＳ）は、コンタクトリスト、グループリスト、アクセスリスト、およびＤｏ−Ｎｏｔ−Ｄｉｓｔｕｒｂなどの許可管理の管理を担当する。ユーザ機器（Ｕｅ）は、ＰｏＣアプリケーションソフトウェアを含む端末クライアント機器（移動電話）である。
【０００９】
したがって、現在のＰＴＴサービスの概念は、非常に長い送信遅延を生じさせ、アドホックネットワークに適しない中央サーバに基づいている。さらに、分散サーバクラスタも通信および調整のためのボトルネックになる可能性がある。
【００１０】
直接接続会話は、通常のコールと異なる経験を生成する。プッシュツートーク機能は、人々がとりとめなく話すのをやめさせる傾向がある。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
現在のシステムは、ほとんど瞬間的に生じるべき何かのために接続を確立するのにボタンを押した後、１０から１５秒を必要とする。さらに厄介なことには、話した後で相手が言われたことを聞くまでに少なくとも５秒の遅延がある。その結果は、１人の人が話し終わる度に、苦痛に感じる中断である。
【課題を解決するための手段】
【００１２】
この問題は、通信ネットワークにおいてグループ通信を処理する方法であって、参加クライアントがグループとして容認され構成され、参加クライアント間のストリームメディアの指示された交換のために通信セッションが確立され、通信リソース、特に、ストリームメディアの交換の指示などのリソースが調整され、すなわち、クライアントが通信リソースを要求した場合、クライアントが通信ネットワークにおいてピアとして対称的に編成されるように、通信リソースをクライアントに再割り当てする、すなわち、同等のピアの分散システム以外に区別された（中央集積化された）クライアントはなく、要求されたリソースをディスパッチすることに関しては参加ピアの前記グループのうちの少なくとも１つの参加ピアを選出することによりストリームメディアの交換の指示を調整するために参加クライアント間のピアツーピアネットワークが確立され、少なくとも１つの参加ピアによってピアツーピアネットワークを介して参加ピアに発信されたストリームメディアを交換し、選出を開始することによりリソース要求を調整し、ピアツーピアネットワークを使用してピア間の分散選出アルゴリズムによって同時要求を公正かつ有効に解決する方法によって克服される。問題は、とりわけ、この方法を実行するコンピュータソフトウェア製品、ネットワーククライアント、およびそれらのための通信システムによって解決される。
【００１３】
これは、システムがスケーラブルになり、大きな遅延をこうむらないという利点を有する。さらに、本発明はアドホックネットワークに適している。
【００１４】
さらに、本発明は、通信システムの信頼性および耐障害性が高められるという利点を有する。
【００１５】
さらに、強靭でスケーラブルなピアツーピアアーキテクチャは、リソースの利用を節約し、待ち時間を低減し、中央集権化された（ボトルネック）サーバを回避するという利点を有する。
【００１６】
本発明は、以下で図を使用して詳細に説明される。
【発明を実施するための最良の形態】
【００１７】
図１は、管理システムプラットフォームと呼ばれることもある情報構造体ＭＳＰにおけるエンティティ間のマッピングＭＡＰ、ならびにクライアント装置ＣＤ１、ＣＤ２、およびＣＤ３を含む通信ネットワークハードウェアＣＮＷを示す。情報構造体ＭＳＰは、（バーチャル）エンティティＰ１、Ｐ２、Ｐ３、たとえば情報オブジェクトまたはプロセス、およびエンティティによって呼び出されることもできる１組のサービスＳ１、…、Ｓ５を含む。
【００１８】
図２は、一般に適用されるクライアントサーバパラダイム、または、より正確には、マッピングＭＡＰをこのように指定するクライアントサーバアーキテクチャのトポロジを示す。
【００１９】
サーバＳＲＶは、サービスＳ１、…、Ｓ５を提供するサービスコンポーネントＳＶＣを含む。このサーバＳＶＲは、通信ネットワークハードウェアＣＮＷの一部分である。各クライアント装置ＣＤ１、ＣＤ２、およびＣＤ３は、それぞれの情報オブジェクトＰ１、Ｐ２、およびＰ３の情報を担持するためのクライアントＣ１、Ｃ２、Ｃ３と呼ばれる１つのソフトウェアを含む。
【００２０】
図３は、ハードウェアコンポーネントとソフトウェアコンポーネントとの間の対話を示す。クライアント装置ＣＤ１のクライアントＣ１は、相互排他通信リソースを要求すること１により通信ネットワークを介してサーバＳＶＲのサービスコンポーネントＳＶＣのサービスを呼び出すことができる。サービスコンポーネントは、どのクライアントが通知されるべきかを決定し２、通信ネットワークを介して対応するクライアント装置ＣＤ２、…内のクライアントＣ２、…に通知する３。通知されたクライアントＣ２、…は、それらのビューを更新し４、必要なら通信リソースを解放し、解放を肯定応答する５。最後に、サービスコンポーネントがそのステータスを更新し６、要求されたリソースが利用可能な場合は、要求されたリソースを第１に述べられたクライアントＣ１に与える７。
【００２１】
これは、前述の不利な点を有する。したがって、図４では、代替マッピングＭＡＰが開発され、各クライアント装置ＣＤ１、ＣＤ２は、対称的管理サービスインフラストラクチャを含む。したがって、各クライアント装置は、（バーチャル）ネットワークビューを生成することができるそれ自体の情報構造体ＭＳＰを有し、このことは、各クライアント装置が別のクライアント装置ＣＤ２にある他の情報構造体を知っていることを意味する。
【００２２】
以下では、バーチャルエンティティＰ１、Ｐ２、Ｐ３を含むこのビューは、ピアツーピアネットワークと呼ばれ、エンティティは、ピアと呼ばれる。ピアツーピアインフラストラクチャは一般にＰ２Ｐとして知られている。これは、ネットワークの端部で利用可能なリソース（ストレージ、サイクル、コンテンツ、人間の存在）を利用する一種のアプリケーションである。Ｐ２Ｐアーキテクチャでは、ピアはそれら自体の間で直接通信し、どの役割がネットワークにとって最も効率がよいか考えて、クライアントとしてもサーバとしても働くことができる。ピアシステムはサービス指向アーキテクチャ（ＳＯＡ）を強化する。しかし、誰がプロバイダ、コンシューマ、またはレジストラであるかの決定は非常に緩やかである。
【００２３】
ピアツーピア技術は、分散ネットワークにまたがってのリアルタイム通信およびコラボレーションを容易にするために使用される。ピアツーピアモデルでは、サーバを使用せずに、ピアと呼ばれる各クライアントがデータを交換し、リソースを共用し、他のピアまたはユーザの位置を検出し、通信し、あるいはリアルタイムで直接コラボレートすることができる。ピアツーピア技術を使用することによって、コンピュータのＣＰＵサイクルおよびストレージの使用を調整するアプリケーションが、インターネットなどのネットワークに接続された小さなグループまたは大きなグループのコンピュータの間でリソースを共用することができる。
【００２４】
スケーラブルＰ２Ｐアーキテクチャ上の帯域幅の必要条件が低減されたＰＴＴサービスは、サービスプロバイダのためにかなりのリソースを節減することができ、帯域幅消費に対するユーザベースの制御を含むことができる。情報構造体、たとえば携帯電話用のＰＴＴクライアントは、ダウンロード可能である。
【００２５】
たとえＰＴＴクライアント自体が標準化されていなくても、移動電話にクライアントをダウンロードする多かれ少なかれ標準化された方法は、ＰＴＴを非常に簡単に試そうとする者には非常に有用であり（移動電話の店に行く必要がない）、ＰＴＴの採用を迅速に加速するであろう。特にＰ２Ｐアーキテクチャに基づくＰＴＴサービスは、リソースおよび帯域幅の使用を節約することができ、ＣＤＭＡ、ＧＰＲＳ、ＵＭＴＳ、８０２．１１ｘ、および有線を含むいかなるパケットベースのＩＰネットワーク上でも稼働する。インターネットプロトコル（マルチメディアサブシステム）（ＩＭＳ）は、バランスされたリソースを互いに共用する機械の通信手段として使用されることができる。
【００２６】
各ユーザは自分のバディリストを処理する。参加者のアベイラビリティ（存在）をチェックするために、調査および精査による参加者についての知識を含む解決機構が知られている。通信コミュニティグループが確立された後は、ストリーム通信（音声）のために指示された（論理）ネットワークが確立されなければならない。複数の人々宛の場合、マルチキャストが使用されることができるか、あるいはメッセージが順々に送信される。効率のよい選出アルゴリズムがネットワークの方向を推論することによりプッシュツートーク機能を保証する。
【００２７】
実際、もともとのインターネットは、基本的にピアツーピアシステムとして設計された。時間が経つにつれて、インターネットは徐々に何百万のコンシューマクライアントが１組のサーバと通信するクライアント／サーバになってきた。現在のピアツーピアアプリケーションは、インターネットを、もともと設計されたように、すなわち、同等物として互いにリソースを共用する機械のための通信手段として使用している。
【００２８】
参加者のアベイラビリティ（存在）をチェックするために、単純なセッション開始プロトコル（ＳＩＰ）手順が、たとえば送信勧誘および肯定応答を使用して、アベイラビリティ（存在、プリファレンス）に関するバディリストを更新するために使用されてもされなくてもよい。これはまた、参加者のＳＩＰアドレスに関する知識をも含む。
【００２９】
メッセージは、直接ＲＴＰ／ＵＴＰ音声パッケージで、定義された参加へ押し進められることができる。複数の人々宛の場合、マルチキャストプロトコルが使用されることができるか、またはメッセージが順々に送信される。クライアントは、ハンドセット、スマートフォン、ＰＤＡまたはデスクトップ上にダウンロード可能であり、ＳＩＰ、ＲＴＰ、ＵＤＰ、ＳＩＭＰＬＥ、および３ＧＰＰ規格に準拠することを保証する。
【００３０】
ピアツーピア技術は１組のプロトコルとみなされることもできる。各プロトコルは、プロトコルにおいて参加者の間で交換される１つまたは複数のメッセージによって定義され、各メッセージは予め定義されたフォーマットを有し、様々なデータフィールドを含むことができる。
【００３１】
基本的に６つのプロトコル、すなわち、ピアディスカバリプロトコル、ピアリゾルバプロトコル、ピア情報プロトコル、ピアメンバーシッププロトコル、パイプバインディングプロトコル、エンドポイントルーティングプロトコルがある。
【００３２】
ピアは、ピアに必要なプロトコルを話すことができる任意のエンティティである。これは、インターネットに近く、インターネットノードはＩＰプロトコルのスイートを話すことができる任意のエンティティである。したがって、ピアは、プロセッサ、プロセス、機械、またはユーザの形で現れることができる。メッセージは、非同期、非信頼、一方向トランスポートの上で使用可能なように設計される。したがって、メッセージは、本体と共にエンベロープおよびプロトコルヘッダのスタックを含むデータグラムとして設計される。エンベロープはヘッダ、メッセージダイジェスト、（任意選択で）ソースエンドポイント、および宛先エンドポイントを含む。エンドポイントは、データグラムスタイルのメッセージを送受信することができる任意のネットワークトランスポート上にＵＲＩの形で与えられる論理的宛先である。
【００３３】
ピアグループは、ピアグループプロトコルのセットを話すバーチャルエンティティである。通常、ピアグループは、共通のサービスセットを提供する協力ピアの集まりである。
【００３４】
パイプはメッセージを送受信するための通信チャネルであり、非同期である。パイプはまた一方向性であり、したがって、入力パイプおよび出力パイプがある。パイプはまたバーチャルであり、パイプのエンドポイントが１つまたは複数のピアエンドポイントに結びつけられることができる。パイプは、通常、ランタイムにパイプバインディングプロトコルを介してピアに動的に結びつけられる。これはまた、パイプが様々な時間に様々なピアに移動され結びつけられることができることを意味する。
【００３５】
パイプは、前述の例示的プッシュツートークピア間の相互通信チャネル、すなわち通信リソースにサービスを提供し、一方、チャネル要求の同期が送信の相互排除を保証する必要がある。これは、システムの任意のライフタイムにただ１人の送信者と複数の受信者がいることを意味する。これは、以下で説明される、ある同期、たとえば単純な分散優先Ｌａｍｐｏｒｔアルゴリズム、またはより（おそらく最も）効率のよいアルゴリズムを必要とする。
【００３６】
既存の相互排除アルゴリズム分散システムは、そのようなシステムに適していない。分散相互排除のための「ルックアヘッド」技法の概念は、システムのすべてのピア間に相互排除を強要するのではなく、同時にクリティカルセクションを求めて競合しているサイト間にだけ相互排除を強要し、その結果、メッセージオーバヘッドが少なくなる。この概念は、要求メッセージを送出する前に、まず最初に、現在クリティカルセクションを要求しているサイトを見つけ出そうとする。ルックアヘッド相互排除の設計には２つのことが必要である。すなわち、第１に、同時にクリティカルセクション（プッシュリクエストなど）を求めて競合するサイトを識別することと、第２に、これらのサイト間に相互排除を強要することである。
【００３７】
これは、図５のシーケンスチャートに示されている。クライアント装置ＣＤ１にある第１ピアＰ１が相互排除リソースを要求する１’。この要求はその他のピアに配布され、各関係ピアは、結局第１ピアＰ１に与えられる７’リソースの同期に寄与する（２’、４’）。各ピアＰ１、Ｐ２、…自体がそのシステムビューを保持する６’。効率のよい選出アルゴリズムが詳細に説明される。
【００３８】
分散アプリケーションは、１つまたは複数のプロセスが任意の単一サイト上で実行していることができるように、ピアがシステム内の１組のコンピュータ上で実行するプロセスの集まりから成る。サイトはどのメモリも共用せず、完全にメッセージパッシングによって通信する。メッセージ伝搬遅延は有限であるが、通常、予測できない。ピアツーピア環境では、基礎となる通信手段は信頼性が高く、サイトはクラッシュしないと考えることができる。
【００３９】
過去１０年にわたって、分散システムにおける相互排除の問題がかなりの注目を浴びてきて、分散システムにおいて相互排除を実現するためのいくつかのアルゴリズムが提案されてきた。たとえば、Ｊｏｙｄｅｅｐ  ＧａｎｇｕｌｙおよびＭｉｃｈａｅｌ  Ｄ．Ｌｅｍｍｏｎの、「Ｔｈｅｏｒｙ  ｏｆ  Ｃｌｏｃｋ  Ｓｙｎｃｈｒｏｎｉｚｅｄ  ａｎｄ  Ｍｕｔｕａｌ  Ｅｘｃｌｕｓｉｏｎ  ｉｎ  Ｎｅｔｗｏｒｋｅｄ  Ｃｏｎｔｒｏｌ  Ｓｙｓｔｅｍｓ」、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ｏｆ  ｔｈｅ  ＩＳＩＳ  Ｇｒｏｕｐ  ａｔ  ｔｈｅ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｎｏｔｒｅ  Ｄａｍｅ、を参照されたい。また、アプローチおよび認識の調査も出ている。
【００４０】
トークンベースのものなどより単純なアルゴリズムは、一般に、競合していないサイトも要求メッセージを送られるので、効率がよくない。したがって、そのようなアルゴリズムは、低帯域幅を消費し、高リアルタイム必要条件を有するコンピューティングシステムには適しない。ピアツーピアアプリケーションのコンテキストで選出に最も適しているのは、非トークンアルゴリズムのようである。ＬａｍｐｏｒｔアルゴリズムまたはＲｉｃａｒｔ−Ａｇｅａｗａｌａアルゴリズムなど、引用された文献の５．２項を参照されたい。
【００４１】
効率を上げるために、改善された分散相互排除アルゴリズムが提案され、ピアがクリティカルセクションの実行を必要とする場合、すべてのピアから許可を得る必要はなく、ピアのサブセットだけから許可を得ればよく、その結果、メッセージオーバヘッドが低くなる。したがって、分散相互排除のためのルックアヘッドの概念は、すべてのピア間に相互排除を強要するのではなく、相互排除は現在クリティカルセクションを求めて競合しているピア間にだけ強要される。この概念は、要求メッセージを送出する前に、まず最初に、どのサイトが現在要求しているのか見つけ出そうとするので、われわれはこれを「ルックアヘッド」技法と名づける。ピアは、クリティカルセクションを求めて競合しているピアを調べるだけでよい。
【００４２】
ルックアヘッド相互排除には２つの利点がある。（ｉ）ルックアヘッド相互排除アルゴリズムは、サイト間の不必要な通信を排除するので、より効率がよい。メッセージトラフィックは、任意の時間におけるアクティブサイトの平均数に比例する（必ずしもサイトの合計数にではない）。また、非要求サイトは、要求サイトからの要求メッセージを処理するオーバヘッドを有しない。（ｉｉ）理論的には、ルックアヘッド相互排除アルゴリズムは動的分散アルゴリズムに別の次元（ｄｉｍｅｎｓｉｏｎ）を導入する。
【００４３】
各ピアに関して、同時セットがこのピアと同時に相互排除を呼び出すピアのセットであると仮定する。これは、ピアと同時に競合するピアを識別し、第２ステップで同時に競合するサイト間に相互排除を強要することを必要とする。
【００４４】
ルックアヘッド相互排除アルゴリズムの設計における大きな問題は、過度のメッセージを交換せずに要求サイトの同時セットを識別することである。
【００４５】
第１ステップで、同時セットが識別される。サイトがどのピアが現在競合しているか見つけ出す。これをするには少なくとも３つのやり方がある。中央式：中央サーバがすべてのサイトの最新の状態を保持する。サイトがそれらの状態変化を中央サイトに通知する。この方法は相互排除に対する分散ソリューションではなく、したがって、効率がよくない。スヌーピー式：この方法は、ブロードキャストタイプの通信手段を有するシステムにだけ適用可能である。サイトは、通信手段上でメッセージ転送アクティビティをモニタリングすることにより他のサイトの状態を知る。この方法は、少しのオーバヘッドしか有しないが、ブロードキャスト通信アーキテクチャを備えたシステムに限定される。分散式：この方法では、ピアは、その状態を通知するために他のピアにメッセージを送信する。これをするには、やはり少なくとも２つのやり方がある。ピアは、その状態の変化を他のすべてのサイトに通知することができる、あるいは、ピアは、クリティカルセクションを実行することを決めるときはいつでも、他のピアの状態を精査することができる。しかし、これらの方法は高価である――少なくとも２つの＊（ピア数−１）メッセージを必要とする。以下の観察を部分的に使用することにより、状態情報発信／取得に起因するメッセージトラフィックを低減することができる。Ｉがその要求状態をＪに通知する場合、ＪはＩが要求したときはいつでも自動的に通知される。したがって、ＪはＩに状態情報を明示的に要求する必要がない。
【００４６】
ピアは１、２、３、…、ｎとし、ｉｎｆｏ  Ｉは、Ｉが要求していることをＩが通知するピアのセットであるとする。さらに、ｓｔａｔｅ  Ｉは、要求していることをＩに通知するピアのセットとする。
【００４７】
条件１：セットの構築
Ｉ．すべてのピアＩに関して：Ｉｎｆｏ＿Ｉ  Ｕｓｔａｔｅ＿Ｉ＝すべてのピア
ＩＩ．すべてのピアＩおよびＪに関して：Ｉがｉｎｆｏ＿Ｊにある場合、Ｊはｓｔａｔｅ  Ｉにある
【００４８】
明らかに、ピアＩがシステム全体における要求アクティビティを知るのに十分な条件は、ＩがすべてのＪにその状態を通知するかまたはＪによってその状態を通知されることを必要とする。
【００４９】
セットの最小性のために、ｓｔａｔｅ＿Ｉとｉｎｆｏ＿Ｉは非結合である。そうでなければ、情報交換において冗長があるであろう、すなわち、ＩがＪによって通知されるばかりでなく、ＩがＪに通知する。条件は、システム内のセットがどのように開始されるか述べる。条件を満たすこれらのセットの任意の開始が良い。
【００５０】
十分条件が続く場合、その結果として、ピアＩとＪのすべての対に関して、Ｉがｉｎｆｏ＿ＪにあるかまたはＪがｉｎｆｏ＿Ｉにある。
【００５１】
サイトＩは、２つのやり方で他の現在要求しているサイトについて知る。（ｉ）Ｊがｓｔａｔｅ＿Ｉにある場合、Ｊはそれ自体でＩに通知する。（ｉｉ）Ｊがｉｎｆｏ．Ｉにある場合、ＩがＪに通知し、ＪはＩにＪが現在要求しているかどうか通知する。正式には、これは以下のようになる。
【００５２】
条件２：要求の処理
ＩがＪから要求メッセージを受信した場合、Ｉ自体がその時に要求していてＪがｓｔａｔｅ＿Ｉにあるならば、Ｉは要求メッセージをＪに送信する、すなわち、Ｉはｓｔａｔｅ＿ＩからＪを削除し、ｉｎｆｏ＿ＩにＪを追加する。
【００５３】
したがって、ピアＩが別のピアＩが要求していることを知った場合、ピアＩはエントリＪをｉｎｆｏ＿Ｉに追加する。Ｉもその時に要求している場合、ＩはＪに要求メッセージを（まだ送信されていない場合）送信する。このように要求を処理することは、要求しているピアが、他のどのサイトが同時に要求しているかどうか知ることを可能にし、これは以下のように表される。すべてのサイトが条件１および２に従う場合、サイトは、結局、同時に要求しているすべてのサイトについて知る。ｉｎｆｏ＿Ｉ内のサイトだけがＩと同時に要求していることができる。
【００５４】
ｉｎｆｏセットのレゾリューションが対応するサイトと同時に実際に要求しているｉｎｆｏ＿ｘ内のピアの一部分であるとする。ピアは、同時にクリティカルセクションを要求しているすべてのサイトに許可を要求しなければならない。しかし、ピアが、同時に要求していない少数のサイトにも許可を要求する場合、正確さには影響を与えず、性能に影響を与えるだけである。
【００５５】
サイトが、同時に要求しているすべてのサイトを知った後は、サイトは、相互排除を強要するためにピアに対して、たとえばＲｉｃａｒｔ−Ａｇｒａｗａｌａ法、または他の任意の除外アルゴリズムを使用することができる。
【００５６】
サイトＩが要求を受信した場合、サイトＩは、サイトＩが要求していない場合、またはサイトＩの要求の優先度が着信要求の優先度より低い場合、要求に応答して応答メッセージを送信する。そうでない場合は、応答を遅らせる。サイトは、他のすべてのサイトから応答メッセージを受信した後でだけ、クリティカルセクションを入力する。
【００５７】
最初にｉｎｆｏセット内のピアにそれらの状態を問い合わせるためにメッセージを送信し、次いで、要求メッセージを実際に要求しているサイトにだけ送信することは、高価であるはずである（大きなメッセージトラフィックおよび大幅な遅延になる）。したがって、ピアが要求メッセージを最初にそのｉｎｆｏセット内のすべてのサイトに送信することがより望ましいであろう。このｉｎｆｏセット内のピアだけが同時に要求していることができる。したがって、要求するために、ピアがそのｉｎｆｏセット内のすべてのピアに要求を送信する。ピアは、要求を徐々に知るにつれて、エントリの追加を漸増することに留意されたい（条件２）。したがって、サイトは、ピアから要求を受信し、それらをその状態セット内に追加するにつれて、ピアへの要求の送信を漸増する（条件２）。
【００５８】
条件３：要求の処理
サイトＩは、サイトＩが要求していない場合、またはサイトＩの要求の優先度が着信要求の優先度より低い場合、要求に応答して応答を送信する。
【００５９】
条件２と条件３の両方が要求の処理に関係する。どのようにセットを更新するかを述べる条件２は、ルックアヘッド手法全体に共通であり、一方条件３は、相互排除を強要するＲｉｃａｒｔ−Ａｇｒａｗａｌａアルゴリズムに特有である。
【００６０】
条件４：クリティカルセクションの実行
サイトＩは、送出したすべての要求に対する応答メッセージを受信した後でだけ、クリティカルセクションを実行する。
【００６１】
条件２の継続された適用によって、ｉｎｆｏセットのサイズは単調に増大し、その結果、レゾリューションが減少する。ＩがＪから応答を受信した場合、その瞬間に、Ｉはｉｎｆｏ  Ｊにあり、Ｊはｉｎｆｏ  Ｉにある。
【００６２】
したがって、そのような状況が生じた場合、サイトＩはｉｎｆｏ＿ＩからＪを削除すべきである、またはその逆である。Ｉがｉｎｆｏ＿ＩからＪを削除した場合、相互排除が保証されない可能性があることに留意されたい。したがって、唯一の選択は、条件１を満たすために、Ｊがｉｎｆｏ＿ＪからＩを削除する（そして、それをｓｔａｔｕｓ＿Ｊに入れる）ことである。Ｉは、Ｊから応答メッセージを受信した場合、これらの動作を行うことができることにさらに留意されたい。
【００６３】
条件５：応答メッセージの処理
サイトＩは、Ｊから応答を受信した後で、ｉｎｆｏ＿ＩからＪのエントリを削除し、ｓｔａｔｅ＿Ｉに入れる。
【００６４】
結果として、Ｉがクリティカルセクションを実行する直前にＪがｉｎｆｏ＿Ｉにある場合、Ｉは、Ｉがクリティカルセクションを実行した後でｉｎｆｏ＿Ｊにある。ピアＩが実行を終了した後で、ｉｎｆｏ＿Ｉ内のすべてのエントリが、保留中の要求を有するピアに対応する。
【００６５】
したがって、ピアは、実行を終了した後で、そのｉｎｆｏセット内のすべてのサイトに応答を送信すべきである。
【００６６】
条件６：クリティカルセクションからの退出
退出時、ピアＩはｉｎｆｏ＿Ｉ内のすべてのピアに応答を送信する。
【００６７】
ピアの情報に関するインバリアントは実行によって保持される。さらに、条件２から６までで取られたアクションが条件１を保持する。このアルゴリズムはいくつかの利点を有する。このアルゴリズムは正確である、すなわち、相互排除を保持し、デッドロックがなく、スターベーションがない。さらに、最も重要なことは、このアルゴリズムは、メッセージトラフィックのかなりの低減のため、非常に高性能であることである。
【図面の簡単な説明】
【００６８】
【図１】ハードウェア上への情報構造体の概念的マッピングの必要性を示す図である。
【図２】従来技術によるクライアントサーバアーキテクチャによって実現される通信システムを示す図である。
【図３】従来技術によるクライアントサーバアーキテクチャの対話を示すシーケンスチャートを示す図である。
【図４】本発明によるピアツーピアアーキテクチャによって実現される通信システムを示す図である。
【図５】本発明によるピアツーピアアーキテクチャの対話を示すシーケンスチャートを示す図である。
【図１】
2008541519.tif 000003
【図２】
2008541519.tif 000004
【図３】
2008541519.tif 000005
【図４】
2008541519.tif 000006
【図５】
2008541519.tif 000007
【国際調査報告】
2008541519.tif 000008
2008541519.tif 000009
2008541519.tif 000010