(57)【特許請求の範囲】
【請求項１】
一連の処理装置（Ｍ１、Ｍ２、Ｍ３）の間で分散され、各ノードが一意の後続ノードを有するように円形に配置された一連のノード（Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５、Ｎ６）からなるピアツーピアネットワークであって、各ノードがキーと関連付けられたデータ（Ｄ）を格納するためのメモリを有し、キーを含んでいる要求を受信すると前記キーと関連付けられたデータを提供し、第１のノードのメモリに格納された各データ項目が前記第１のノードとは異なる第２のノードのメモリに複写され、前記第２のノードが、前記第１のノードが配置された処理装置とは異なる処理装置に配置された、前記円形内の直後のノードであり、
少なくとも１つのノードが、前記円形内の先行ノードの出力を検出するのを試みた後に第１の値をとり、前記先行ノード内に含まれるデータを再同期する段階の後に第２の値をとる同期情報を有し、前記ノードが、そのメモリ中にキーと関連付けられたデータがあることと、前記同期情報との両方に基づいて、そのキーを含んでいる要求に応答するように設計された、ピアツーピアネットワーク。
【請求項２】
前記処理装置の数が、前記ノードの数より少ない、請求項１に記載のピアツーピアネットワーク。
【請求項３】
前記データが、前記ネットワークの２つ以上のノードのメモリに複写される、請求項１または２に記載のピアツーピアネットワーク。
【請求項４】
請求項１から３のいずれか一項に記載のピアツーピアネットワーク（Ｎｐ２ｐ）を含んでいる通信要素（Ｅ２）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一連の処理装置にピアツーピアネットワークを導入することに関する。より詳細には本発明は、電気通信アプリケーションにこうしたピアツーピアネットワークを使用することに関係する。
【背景技術】
【０００２】
ある一定の電気通信アプリケーションを、特に一連の処理ノードに分散させることが知られている。このような方法では各ノードは、そのアプリケーションに向けられる要求の一部を処理するにすぎず、必要であれば、これらの要求を処理するのに必要とされるリソースに基づいてノードの数を動的に合わせることが可能である。このようなアーキテクチャはまた、アプリケーションが、ノード間の固有の冗長性によって容易にフォールトトレラントにされうることを意味する。
【０００３】
しかしながらある一定のアプリケーションについては、この一連のノード内のコンテキスト情報の記憶場所の問題が依然として存在する。シグナリング要素のようなある一定のアプリケーションは、送信される２つのメッセージ間でコンテキストの格納を必要とする場合がある。このコンテキストは、次に続くメッセージを適切に処理するために使用されることが可能である。ＳＩＰセッション（ＳＩＰは「Ｓｅｓｓｉｏｎ  Ｉｎｉｔｉａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ」を表す）のステータスに基づいて要求を処理しなければならないＳＩＰまたは「プロキシＳＩＰ」のシグナリング要素の場合がこれである。
【０００４】
このタイプのアプリケーションについては、第１にこのコンテキスト情報を格納し、第２に上記情報を適切な時間に捜し出すことができることもまた必要である。
【０００５】
１つの可能な手法は、ノードのそれぞれがアクセスでき、ノードのそれぞれが管理するセッションのコンテキスト情報を格納および取り出すことができる集中化されたデータベースを有することを含む。
【０００６】
しかしながら、この集中化されたデータベースがハードディスクまたは同等のハードウェアのサポート上に実装されるとき、情報アクセス時間は限定的になり、この解決法は、電気通信アプリケーションのような非常に短いレスポンス時間を要求するアプリケーションには不適切となる。
【０００７】
データベースをメモリに実装すると、このアクセス時間の問題を解消するが、アクセスの負荷を分散するために、およびフォールトトレランスの制約に対処するために冗長性を組み込む必要性がシステムを複雑にする。実際にはこれは、一連の処理ノードから離れた基地のネットワークを構成することを含む。このような手法が知的レベルであまり満足のいくものではないように思われることに加えて、これは構成の問題ももたらし、管理の柔軟性も、容易性もない。
【０００８】
分散されたハッシュ表を利用することによりピアツーピアネットワークが使用されると、アプリケーションの開発者、および上記アプリケーションと通信する必要があるアプリケーション外部の装置に自動的およびトランスペアレントな方法でこれらの問題を解決する。
【０００９】
図１は、ＮノードＸ１、Ｘ２、Ｘ３、Ｘ４、……ＸＮを含むピアツーピアネットワークを略図の形態で表す。
【００１０】
格納されるべきコンテキスト情報は、この一連のノードに分配されるキーと関連付けられる。一般にはこの分配は、キーの空間をノードの空間に投影してこれらのノードの間で負荷が上手く分散されるように使用されるハッシング関数によって実行される。
【００１１】
コンテキスト情報は、キーから見つけ出すことができる。同じハッシング関数のアプリケーションが使用されて、このキーと関連付けられたノードを判定し、次にこのノードに格納された、キーと関連付けられた情報を取り出す。
【００１２】
システムをフォールトトレラントにするためには、一般に、キーとコンテキスト情報との各関連付けが第２のノードで複製されるようにする。このように、第１のノードがもはや作動しない場合、コンテキスト情報は、この第２のノードから取り出されることが可能である。
【００１３】
一般に、どのノードがコンテキスト情報のコピーを格納しなければならないかを決定するために使用される簡単なアルゴリズムは、後続ノード、言い換えればピアツーピアネットワークの順番で次に来るノードを選択することを含む。このような選択の利点は、ノードの障害の場合に、コンテキスト情報のコピーが直ちに捜し出されることである。したがってこれは、要求への不正なレスポンスを行うことなくこの期間を正しく管理するには追加手順を必要とする、障害に続く不安定な期間を回避する。
【００１４】
したがって、要求されるキーに適用されるハッシュ関数がノードＸ２を指定し、このノードがもはやアクセスできない、またはもはや動作不良後に来る情報を含んでいない場合、システムは自動的に、要求されるコンテキスト情報のコピーがノードＸ３で捜し出されると判断する。
【００１５】
こうしたピアツーピアネットワークの実行は、Ｉａｎ  Ｓｔｏｉｃａ、Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ、Ｄａｖｉｄ  Ｋａｒｇｅｒ、Ｍ．Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ  ａｎｄ  Ｈａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎによる論文、「Ｃｈｏｒｄ：Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  ２００１、Ｓａｎ  Ｄｉｅｇｏ、ＣＡ、２００１年８月、１４９−１６０頁にさらに詳細に説明されている。
【００１６】
「Ｃｈｏｒｄ」ネットワークにおいてフォールトトレランスを向上させる方法を説明する論文がある。例えば、Ｈａｉｆｅｎｇ  Ｙｕ、Ｐｈｉｌｉｐ  Ｂ．ＧｉｂｂｏｎｓおよびＳｕｍａｎ  Ｎａｔｈによる論文、「Ａｖａｉｌａｂｉｌｉｔｙ  ｏｆ  ｍｕｌｔｉ−ｏｂｊｅｃｔ  ｏｐｅｒａｔｉｏｎｓ」は、このようなネットワークでデータがどうのように複製されるかを調べることを提案する。
【００１７】
しかしながら実際には、フォールトトレランスの技術的な問題が残っている。ピアツーピアネットワークは、実際には処理装置のネットワーク上に導入される。これらの装置はますます強力になっているので、処理装置の数をノードの数より少なくすることに加えて、同じ装置上にいくつかのノードを配置することが有利である。
【００１８】
図１の例では、ノードＸ２およびＸ３は装置Ｍ２上に設置され、ノードＸ１およびＸＮは装置Ｍ１上に設置され、ノードＸ４は装置Ｍ３上に設置される。
【００１９】
結果として、処理装置が動作不良を起こす場合、ノードは影響を受けて、もはや作動しない可能性がある。したがって、処理装置Ｍ２が故障する場合、２つのノードＸ２およびＸ３はもはや作動しない。
【００２０】
さらに後続ノード上に情報のコピーを置くことを含む伝統的なアルゴリズムによれば、ノードＸ２に格納された情報はノードＸ３上に複写される。結果として、最新技術のフォールトトレランスメカニズムにもかかわらず、このノードと関連するコンテキスト情報はもはや利用できない。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Ｉａｎ  Ｓｔｏｉｃａ、Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ、Ｄａｖｉｄ  Ｋａｒｇｅｒ、Ｍ．Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ  ａｎｄ  Ｈａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎによる論文、「Ｃｈｏｒｄ：Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  ２００１、Ｓａｎ  Ｄｉｅｇｏ、ＣＡ、２００１年８月、１４９−１６０頁
【非特許文献２】Ｈａｉｆｅｎｇ  Ｙｕ、Ｐｈｉｌｉｐ  Ｂ．ＧｉｂｂｏｎｓおよびＳｕｍａｎ  Ｎａｔｈによる論文、「Ａｖａｉｌａｂｉｌｉｔｙ  ｏｆ  ｍｕｌｔｉ−ｏｂｊｅｃｔ  ｏｐｅｒａｔｉｏｎｓ」
【発明の概要】
【発明が解決しようとする課題】
【００２２】
この最新技術は、十分なフォールトトレランスを提供するには不適切である。本発明の目的は、ピアツーピアネットワークの管理を改善することによって、この不十分な点を克服することである。
【課題を解決するための手段】
【００２３】
そこで、本発明の目的は、一連の処理装置の間で分散され、各ノードが一意の後続ノードを有するように円形に配置された一連のノードからなるピアツーピアネットワークであって、各ノードがキーと関連付けられたデータを格納するメモリを有し、キーを含んでいる要求を受信すると、上記キーと関連付けられたデータを提供し、第１のノードのメモリに格納された各データ項目が、上記第１のノードとは異なる第２のノードのメモリに複写される、ピアツーピアネットワークである。
【００２４】
このピアツーピアネットワークは、第２のノードが、上記第１のノードが配置された処理装置とは異なる一連の処理装置に配置されたノードの中から選択されることを特徴とする。
【００２５】
本発明の諸実施形態によれば、第２のノードは、上記第１のノードの処理装置とは異なる処理装置上に配置された上記円形内の第１のノードであることが可能である。
【００２６】
少なくとも１つのノードが、上記円形内の先行ノードの出力が検出された後に第１の値をとり、上記先行ノード内に含まれたデータを再同期する段階の後に第２の値をとる同期情報を有することができ、上記ノードは、そのメモリに、および上記同期情報に、キーと関連付けられたデータがあることに応じてそのキーを含んでいる要求に応答するように設計される。
【００２７】
上記データはさらに、上記ネットワークの２つ以上のノードのメモリに複写されることが可能である。
【００２８】
本発明は、添付の図面を参照して、次の説明の中でより明らかになるであろう。
【図面の簡単な説明】
【００２９】
【図１】最新技術に従ったピアツーピアネットワークを略図の形態で示す図である。
【図２】本発明に従って一連の処理装置に導入されたピアツーピアネットワークを略図の形態で示す図である。
【図３】本発明による通信要素を示す図である。
【発明を実施するための形態】
【００３０】
図２は、３つの処理装置Ｍ１、Ｍ２、Ｍ３からなるネットワークに導入されたピアツーピアネットワークを示す。このピアツーピアネットワークは、円形Ｃに配置された一連のノードＮ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５、Ｎ６から形成される。それによって各ノードは、単一の後続ノードおよび単一の先行ノードを有する。
【００３１】
各ノードは、キーと関連付けられたデータを格納するためのメモリを有する。
【００３２】
一般的には、ハッシュ関数がピアツーピアネットワーク全体と関連付けられ、データ項目に基づいてキーを判定できるようにする。キーの方では、ネットワークのノードを判定できるようにする。
【００３３】
このように、このようなピアツーピアネットワークに新しい値を格納するには、関連付けられたキーを判定するためにその値にハッシュ関数が適用されるべきであり、次にそのキーによって判定されたノードに格納要求が送信されるべきである。
【００３４】
保存されたデータを捜し出すために、キーはまた、キーを含んでいるノードを直接に判定する。
【００３５】
これらのメカニズムの様々な実装が存在し、最新技術の中で十分に説明されている。例えば、上述のＣｈｏｒｄに関する論文は、これらのメカニズムの一般的な実装を示している。
【００３６】
各データ項目はさらに、ハッシュ関数によって判定されたノードとは異なるノードのメモリに複製される、すなわち再コピーされる。本発明によれば、この第２のノードは、第１のノードが配置された処理装置とは異なる一連の処理装置に配置されたノードの中から選択される。
【００３７】
優先的には、第２のノードは、第１のノードの処理装置とは異なる処理装置上に配置された、円形Ｃの中の直後のノードである。
【００３８】
図２の例では、データＤにハッシュ関数を適用することが、これを保存するためにノードＮ２を判定することを可能にした。このノードＮ２は、処理装置Ｍ２に配置されている。
【００３９】
円形Ｃは、ノードＮ２の後続ノードがノードＮ３となるように配置されている。しかしながら、このノードＮ３は、ノードＮ２と同じ処理装置Ｍ２に配置されており、したがって適当ではない。
【００４０】
異なる処理装置上に配置された、このノードＮ２の直後のノードは、ノードＮ４である。本発明のこの優先的な実施では、ノードＮ４が、したがって複写されたデータＤをそのメモリに格納するために選択されるノードである。
【００４１】
処理装置Ｍ２が動作しなくなった場合、ノードＮ２およびＮ３も動作しなくなり、ピアツーピアネットワークは、残りのノードＮ１、Ｎ４、Ｎ５、Ｎ６の中からピアツーピアネットワークを再編成する。この再編成の段階は当業者にはよく知られており、文献の中で、詳細には上述の論文の中で説明されている。
【００４２】
データＤはノードＮ４に複製されたので、これらは依然としてピアツーピアネットワーク内にある。
【００４３】
ノードＮ２のみが動作しなくなるとき同じことが言える。ノードＮ３は依然として動作しており、したがってピアツーピアネットワークのメンバであるが、データＤは同じルールに従ってノードＮ４のメモリに複写される。
【００４４】
このように、単一のルールが一律に適用され、ピアツーピアネットワークに保存されたデータ項目Ｄを捜し出すために、まず従来のメカニズムが使用されて求められているデータと関連付けられたノードを捜し出し、次に異なる処理装置に配置された直後のノードが判定されるべきである。
【００４５】
動作不良後など、ノードがピアツーピアネットワークから抜けるときはいつでも、ネットワークはネットワークを再編成する。この再編成の段階は、保存されたデータの再配布、および詳細には複写されたデータに基づいて以前はノードＮ２のメモリ内に含まれていたデータを複製させることができる。データが完全に再編成されるまで、ピアツーピアネットワークは再同期段階を行っている。
【００４６】
本発明のメカニズムは、この同期段階を処理する際にさらなる問題を提起する。
【００４７】
これは、この同期段階の間、ピアツーピアネットワークから抜けたノードとその直後の異なる処理装置上に配置されたノードとの間に位置する（１つまたは複数の）ノードが、その位置を明確に知らないからである。
【００４８】
図２の例では、ノードＮ２が抜けた後、データＤと関連付けられたキーを含んでいる要求は、ハッシュ関数の適用によってノードＮ３に至る。
【００４９】
このノードＮ３には、そのメモリにデータＤがない。
【００５０】
しかしながら、ノードＮ３は、データＤが存在しないことを報告するメッセージでこの要求に応答しないことが重要である。
【００５１】
したがって本発明は、照会されたノードからの早計な、および不正確な応答を防ぐためのメカニズムを特徴とする。
【００５２】
単純なメカニズムは、要求を常に直後のノードに送信することからなることに注意されたい。しかしながら、このようなメカニズムは、ノードが対応するデータを持っていない各要求に対して追加の送信を伴うため、非常にコストがかかる。言い換えればこれは、ピアツーピアネットワーク内にデータ項目が存在しないときは常に、メッセージが不必要に送信されることを含む。
【００５３】
したがってこのメカニズムは、受け入れられない。
【００５４】
本発明の１つの実装形態によれば、ノードＮ３は、２つの値をとることができる同期情報を有する。
【００５５】
ノードＮ３がピアツーピアネットワーク内の先行するノードＮ２の出力を検出するときはいつでも、同期情報は第１の値をとる。
【００５６】
ノード内に含まれているデータを再同期する段階に続いて、同期情報は第２の値をとる。このデータ再同期の段階は、ノードが抜けるときに起動されるネットワークの再編成段階の間に起こる。
【００５７】
再編成段階後にノードＮ３のデータは、次のノード内に含まれているデータと同期する。したがってデータＤは、ノードＮ４からノードＮ３へ再コピーされる。ノードＮ４は、データＤを冗長コピーとして保存する。
【００５８】
キーを含んでいる要求へのノードＮ３の応答は、そのノードのメモリにそのデータがあることと、同期情報の値の両方によって決まる。
【００５９】
要求されるノードがノードのメモリ内にある場合、そのノードはデータを提供することによって要求に応答する。
【００６０】
そうではなく、同期情報が第１の値を持つ場合、要求は次のノードに送信され、同期情報が第２の値を有する場合、ノードＮ３は、求められているノードがピアツーピアネットワーク内にないことを示すメッセージで応答する。
【００６１】
１つの変形によれば、同期情報が第１の値を有するときはいつでも、ノードＮ３は同期段階の終了を待つ。このとき、ノードＮ３は、そのメモリ内に要求されたデータがあるかどうかによって応答する。
【００６２】
別の変形は、ノードＮ３がまだ応答することができないことを示し、要求の送信者にその要求を繰り返すよう求めるメッセージで要求に応答することからなることができる。
【００６３】
図３は、通信要素と共に本発明によるピアツーピアネットワークのアプリケーションを示す。これは、ＩＭＳ（「ＩＰマルチメディアサブシステム」）アーキテクチャのような、通信アーキテクチャにおけるアプリケーションサーバである場合がある。またこれは、ＩＥＴＦのＲＦＣ３２６１によって規定されるＳＩＰプロトコル（「Ｓｅｓｓｉｏｎ  Ｉｎｖｉｔａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ」）に準拠したプロキシ、またはＩＭＳアーキテクチャの中のＣＳＣＦ機能（「Ｃａｌｌ  Ｓｅｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｆｕｎｃｔｉｏｎ」）のようなシグナリング要素である場合もある。
【００６４】
この通信要素Ｅ２は、通信ネットワークＮＴＥＬを介して別の要素Ｅ１から来る要求Ｒｅｑを受信する手段を有する。要求Ｒｅｑは、通信セッションの各第１の要求に対して、どのノードＮ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５がこの要求を処理しなければならないかを決定するよう意図された、負荷分散モジュールＬＢによって処理される。これらのノードは、前述のようにピアツーピアネットワークＮｐ２ｐを形成する。
【００６５】
要求の処理により、同じセッションに属する別の要求の処理に有用または必要であり得るコンテキスト情報の生成をもたらすことができる。したがってこれはキーと関連付けられ、このキーに対応するノードに格納される。
【００６６】
関連付けは、セッション識別子（例えば、発行中の通信要素Ｅ１のＩＰアドレス、ＳＩＰ要求であり得る「Ｃａｌｌ  ＩＤ」ヘッダなど）に適用されるハッシュ関数によって行われる。このハッシング関数の結果は、ネットワークのノードの数を法として、ノードの数を直接求めることができる。これらの様々なメカニズムは、最新技術に知られており、この特許請求では詳細を記載しない。前述した、「Ｃｈｏｒｄ」メカニズムに関する論文を調べると、これらの詳細の一部を得ることができる。
【００６７】
図３の例では、コンテキスト情報ＣはノードＮ２に格納される。これは、直後のノード内に複写され、同じ処理装置上に導入されない。これがノードＮ４であると仮定される。
【００６８】
このように、同じセッションに属する次の要求は、ノードＮ２上にあるテキスト情報を回復することによって、またこのノードの障害時には後続のノードＮ４上にあるテキスト情報を回復することによって処理されることが可能である。
【００６９】
２つのノードＮ２およびＮ４は同じ処理装置上にないので、この２つのノードが同時に機能しなくなる可能性は非常に低い。
【００７０】
したがって本発明は、ピアツーピアネットワーク管理の知られているメカニズムを根本的に変えることなく、技術的な問題を解決する。
【図１】
0005575142.tif 000002
【図２】
0005575142.tif 000003
【図３】
0005575142.tif 000004