(57)【要約】本発明は、方向が決められたリングトポロジに配列された複数のノード（９００〜２２００）からなる電気通信システムの分散ディレクトリのコンテンツを検索するための方法であって、方法は分散ハッシュ関数によって上記コンテンツの格納位置を特定するステップからなり、ハッシュ関数が要素をノードにマッピングし、ノード（１３００）が当該ノードとその後方ノードの間のハッシュ値を持つ要素を伝達する責任を負う方法に関する。本発明はさらに、対応するコンピュータソフトウェア製品、電気通信装置、及び電気通信システムに関する。
2009543237.tif 000002
【特許請求の範囲】
【請求項１】
方向が決められたリングトポロジに配列された複数のノード（９００〜２２００）からなる電気通信システムの分散ディレクトリのコンテンツを検索するための方法であって、該方法が分散ハッシュ関数によって前記コンテンツの格納位置を特定するステップからなり、該ハッシュ関数が要素をノードにマッピングし、
該ノード（図１、１３００）が該ノードとその後方ノードの間のハッシュ値を持つ要素を伝達する責任を負うことを特徴とする方法。
【請求項２】
請求項１の方法において、ノード故障の場合にデータ複製のための隣接ノードを識別して該隣接ノードでバックアップを生成するために、冗長後方リンクが反対方向、即ち、該リング方向の逆方向に向けて用いられることを特徴とする方法。
【請求項３】
請求項２の方法において、バックアップ目的で使用された該複製データが、探索のルーティングに最も高い可能性で関与されるノード上に位置することを特徴とする方法。
【請求項４】
請求項２の方法において、さらに、新たなノード（１３００）を前方ノード（１２００）に、該前方ノードがその後方ノードに完全に接続された状態で、バインディングする新たなノード（１３００）を挿入するステップ（図６）、該前方ノードからの要素を該新たなノードに転送するステップ（図７）、その後、該後方ノードと該冗長リンクが該前方ノードから該新たなノードに転送され、さらに、該新たなノードを該リングトポロジに加えるステップ、及び該後方ノードへのリンクを持つ該前方ノードによって冗長リンクをアップデートするステップからなることを特徴とする方法。
【請求項５】
コンピュータソフトウェア製品であって、請求項１の方法を実行するように適合されたプログラミング手段からなることを特徴とするコンピュータソフトウェア製品。
【請求項６】
電気通信装置であって、請求項５のコンピュータソフトウェア製品を備えたことを特徴とする電気通信装置。
【請求項７】
ノードとして電気通信装置からなる電気通信システムであって、請求項５のコンピュータソフトウェア製品を備えたことを特徴とする電気通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は分散ディレクトリのコンテンツを検索するための方法、コンピュータソフトウェア製品、電気通信装置及び電気通信システムに関する。
【背景技術】
【０００２】
最少の中央化インフラを有する低い動作費用（ＯＰＥＸ）の通信システムはよく、オーバーレイネットワーク（例えばピアトゥピアネットワーク）において相当に分散されたデータベースを用いる。それらは、ロバスト技術を作り出し、記憶されたデータの整合性を確かなものとするための自己統制メカニズムを実装している。負荷の均衡化、バックアップ戦略及びデータベース照会の高度なルーティングの使用が増して、サービスの発動はそれらのネットワークの全体効率に影響を与えている。
【０００３】
I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek及びH. Balakrishnanは、「CHORD: A Scalable Peer-to-peer Lookup Protocol for Internet Applications」、IEEE/ACM Transactions on Networking, 第１１巻、第１号（２００３年２月）、１７−３２ページに、オーバーレイ・リング・トポロジを形成して冗長リンクをその後続のネットワークノードに対して生成する解決手段を開示した。冗長リンクによってネットワークがノードの耐故障性を持つことが可能となる。各ノードは探索事項について使用される分散データベースの一部となるため、完結した記憶データの特定の部分に対して責任を担う。データベースに対する照会は後方ノードにリングに沿って、又はフィンガーと言われるいくつかのショートカットに沿って、責任を負う１つのノードに到達するまでルーティングされる。ノード故障の場合におけるバックアップ上の理由のため、各ノードはそのデータをその後方ノードに転送する。
【０００４】
Ｃｈｏｒｄプロトコルはキーの位置をどのように見つけるか、新しいノードがどのようにシステムに参加するか、及び既存のノードの故障（又は計画された隔離）からどのように回復するかを指定する。その核心で、Ｃｈｏｒｄはハッシュ関数マッピングキーの高速分散計算を、それらに責任を負うノードに与える。それは整合ハッシュ法を用いる。高い確率でハッシュ関数は負荷のバランスをとる。即ち、全てのノードはほぼ同じ数のキーを受信する。また、ノードがネットワークに参加する（又は離脱する）ときに、高い確率で限られた関数のキーのみが異なる位置に移動される。
【０００５】
Ｃｈｏｒｄは各ノードが残りの全ノードについて知識を持っているとする要件を回避することによって整合ハッシュ法の適応性を向上する。Ｃｈｏｒｄノードは少ないルーティング情報しか必要としない。この情報は分散されているので、ノードは幾つかの他のノードと通信することによってハッシュ関数を解く。探索メッセージはＯ(ｌｏｇ  ｎ)回のホップを必要とする。ノードがネットワークに対して参加又は離脱する時に、Ｃｈｏｒｄはルーティング情報をアップデートしなければならない。なお、参加又は離脱はＯ(ｌｏｇ２ｎ)個のメッセージを必要とする。
【０００６】
整合ハッシュ関数は基本ハッシュ関数を用いて各ノード及びキーを識別子に割り当てる。ノードの識別子はノードのＩＰアドレスをハッシュすることによって選択される一方、キー識別子はキーをハッシュすることによって生成される。整合ハッシュ法は以下の要領でキーをノードに割り当てる。識別子は識別子円に（線形的に並べられて)、即ち、何らかのモジュロ演算について配列される。キーは、その識別子に等しいかそれに続く識別子を持つ第１のノードに割り当てられる。整合ハッシュ法はノードに最小限の中断でネットワークに出入りさせるように設計される。ノードがネットワークに参加するときに整合ハッシュマッピングを維持するために、後方ノードに以前に割り当てられた特定のキーが今度は参加ノードに割り当てられる。ノードがネットワークから離脱するとき、その割り当てられたキーの全ては後方ノードに再割り当てされる。
【０００７】
Ｃｈｏｒｄはバックアップ及びルーティングの課題のために後方ノードへのリンクを使用する。従って、責任を負うノードにリクエストが後方から接近してきても、バックアップデータはリングの前方に沿って記憶されるので、バックアップデータを負荷のバランスをとるためには利用することはできない。
【０００８】
新たに参加するノードは、それらの前方ノードによってネットワークに組み込まれるまで受動的に待たなければならない。これは、参加時間が確定的でなく統計的に分散されるということに帰着する。前もってルーティングデータベースのリクエストが改善され得る。
【０００９】
本発明は分散通信システムに改善された分散データベースを提供して負荷均衡化、即時参加、及び更なる効率化を図るという課題に着目する。
【発明の概要】
【課題を解決するための手段】
【００１０】
これは、方向が決められたリング状トポロジに配置された複数のノードからなる電気通信システムの分散ディレクトリのコンテンツを検索するための方法によって解決される。この方法は、分散ハッシュ関数の手段によってそのコンテンツの格納位置を特定するステップを含み、ハッシュ関数は要素をノードにマッピングし、そのノードは当該ノードとその後方ノード間のハッシュ値を有する要素を伝達する責任を負う。
【００１１】
好ましくは、ノード故障の場合にデータ複製のための隣接ノードを識別して隣接ノードでバックアップを生成するために、冗長後方リンクが、反対方向、即ち、リング方向の逆方向において使用される。
【００１２】
探索のルーティングに最も高い可能性で関与するノード上で、前もってバックアップのためにデータを複製することが好ましい。
【００１３】
そして、以下の要領で新たなノードを直ちに挿入することが好ましい。まず、前方ノードがその後方ノードに完全に接続されたままの状態で、新たなノードの前方ノードへのバインディングを確立し、要素を前方ノードから新たなノードに転送し、その後、後方ノード及び冗長リンクは前方ノードから新たなノードに転送され、最後に新たなノードをリングトポロジに加え、そして、後方ノードへのリンクを持つ前方ノードによって冗長リンクをアップデートする。
【００１４】
課題は、その方法を実行するように適合されたプログラム手段からなるコンピュータソフトウェア製品によって解決される。このプログラムは通常、電気通信装置において、又はノードのような電気通信装置からなる電気通信システム全体の中で実行される。
【００１５】
本発明にはいくつかの有利な効果がある。均等に分布された（現実の）探索において、負荷の大幅な低減を実現することができる。いくつかのリソースが他のリソースよりもより頻繁にリクエストされるような異質のシナリオ、即ち、あるノードでリクエストが集中する場合に、さらに改善がみられる。
【００１６】
本発明によって配置されたバックアップデータは負荷均衡化に利用され得る。最後の不要な「ディアー（ｄｅｅｒ）ジャンプ」が回避される。照会をルーティングするメッセージは質問毎に１ホップ少なくて済む。Ｃｈｏｒｄにおける前方ノードへの安定化ピング動作は必要ない。この新しい方法では、参加するノードが最後にかつ即座にリングトポロジに参加する前に、まず責任を負う全てのデータを引き受けるので、より高いデータ整合性レベルが与えられる。予め参加ノードに転送されるべきデータの量に参加する時間が依存するだけで、ランダムには分散されない。ノードが非常に高いレート（解約率）で離脱及び参加する場合には安定性がより速く低下する。実用的なシステムの解約率は低いので、これはアカデミックな問題である。本発明はＣｈｏｒｄ系システムの３つのバリエーションをここに開示する。これらによってデータ整合性及びノードに対するリクエスト処理のピーク負荷の観点で非常に有利な効果がもたらされる。
【図面の簡単な説明】
【００１７】
【図１】図１は本発明の方法におけるノードの責任を説明する図である。
【図２】図２は従来技術のＣｈｏｒｄ法におけるノードの責任を説明する図である。
【図３】図３は本発明の方法における冗長管理を説明する図である。
【図４】図４は本発明の方法における複製を説明する図である。
【図５】図５は本発明の方法における冗長と複製の組合せを説明する図である。
【図６】図６は本発明の方法における参加ノードを説明する図である。
【図７】図７は本発明の方法における、ノードが参加するときのデータ転送を説明する図である。
【図８】図８は本発明の方法における離脱ノードを説明する図である。
【発明を実施するための形態】
【００１８】
本発明はネットワークを稼動させる分散データベース及びメカニズムとしてのオーバーレイネットワーク及びネットワーク要素からなる。オーバーレイ・ネットワーク・トポロジはリングであり、これは公知技術であるピアトゥピアネットワークＣｈｏｒｄと非常に似ている。メッセージのルーティング、データ責任及びデータバックアップのための新しくかつ有利ないくつかのメカニズムが導入される。
【００１９】
オーバーレイネットワークは、基本的には、適応性・拡張性を制限しＯＰＥＸ（特定のブートストラップサポートを除く）を増加させてしまう中央制御装置を使用することなく、任意数のノードで形成される。ノードの各々は固有の識別子を有し、後続の大きい識別子を持つノードに対してリンクを張る。このメカニズムによって隣接ノードがノード（Ｉ）の前方ノード（Ｐ）又は後方ノード（Ｓ）として動作するリングトポロジを導く。
【００２０】
図１はノード９００、１２００、１３００、１５００、１９００及び２２００からなるリングの一部を示す。各ノードは分散データベースに格納されるべきキー／値の対に対して責任を持つ。公知のハッシュ関数はデータをキーにマッピングする。各ノードは、それ自身とその後方ノード間に位置するキーを格納する責任を持つ。
【００２１】
ノード間のメッセージは、送付先識別子（再使用キーに等しい）に比べて小さい識別子を持つ次の既知ノードにメッセージを転送することによってルーティングされる。
【００２２】
図１はキー１４００の調査を示す。図示するフィンガーテーブルの第１のノード９００から始まり、ルーティング経路は送付先ノード１３００で終わるフィンガーを辿らなければならない。このノードはキー１４００に対して責任を負う。フィンガーは矢印で示す。なお、リングに沿って送付先ノード１３００からその先のノード１５００までディアージャンプはない。
【００２３】
既知のノードはリングに沿って（後方ノードを経由して）、あるいはいくつかのショートカットリンク（いわゆるフィンガー）に沿ってアプローチされる。メカニズムは、データベースに格納されたデータが前方ノード上で複製されることを確実にする。データベース照会が前方ノードによって既に回答済みの場合、負荷均衡化は達成されている。参加ノードは、トポロジに組み込まれる前に、責任を負うデータをその前方ノードから受信する。ノードのリングへの組み込みは、他のノードから独立して、データ転送後直ちに終了する。ノードがデータベースのその部分とともにリングを離脱する場合、その前方ノードが当該データに責任を負うことになる。
【００２４】
本発明を公知のＣｈｏｒｄアルゴリズムとの違いに関して説明する。（図１と）同じ部分を形成することによってリングトポロジを作成するＣｈｏｒｄオーバーレイネットワークを図２に示す。（図１との）相違は、キー１４００を探すときに、送付先ノード１３００にフィンガーを経由して到達するが、その後の最終送付先ノード１５００への更なるジャンプが必要となる点にある（Ｃｈｏｒｄではこのノードがキー１４００に対して責任を負うので）。Ｃｈｏｒｄでは、ノードは、キーがそれ自身の識別子以下でかつその前方ノード識別子よりも大きい場合に、キー／値の対を格納する責任を負うものとされている。
【００２５】
ノード故障の場合でもリングトポロジが閉じた状態を維持することを確実にするために、各ノードは後方ノードの最新版のリストを保持する責任を負う。バックアップのために後方ノードはデータベースコンテンツをそれらの前方ノード全てから複製する。単純な装置及び攻略アルゴリズムを用いて、メッセージは最大Ｏ（ｌｏｇ  ｎ）回のホップでその送付先に到着する。
【００２６】
負荷均衡化はデータ複製とトポロジ冗長メカニズムを組み合わせることによって改善される。改善された方法と同様にＣｈｏｒｄでは、リングトポロジは追加の冗長後方リンクを加えることによってノード故障に耐性を持つ。
【００２７】
図３に冗長ファクタ５の場合の原理を示す。Ｃｈｏｒｄでは、それらのリンクもデータ複製のために使用される。ノード９００はそのデータを（冗長ファクタに応じて）その後方ノード１２００、１３００、１５００、・・・においても格納する。ノード９００がネットワークから離脱する場合、ノード１２００はそのデータに対して責任を負うことになる。リングに沿ってルーティングの方向が小さい識別子から大きい識別子へ向かうので、どのデータベースリクエストもノード１２００へ自動的にルーティングされる。
【００２８】
本発明による方法では、ノード故障の場合に、冗長後方リンクがデータ複製のために反対方向で再使用されて隣接ノードでバックアップを生成する。
【００２９】
図４及び５に新規なバックアップ戦略を示す。Ｃｈｏｒｄとは異なり、データは小さい識別子を持つノードで複製される。バックアップのために使用される複製データは、探索のルーティングに最も高い可能性で関与されるノードに位置する。従って、これらのノードはデータの有効なコピーを有しているので探索照会に既に回答していることになる。また、照会を分散させトラフィックピークをさらに低減する負荷均衡化の動作が実現される。
【００３０】
整合した即座の参加及びデータ複製は通信システムのための更なる要件である。発明に係るシステムは、参加ノードがリングトポロジに完全に参加する前に責任を負うべきデータ全てを前方ノードから引き受ける点でＣｈｏｒｄとは異なる。
【００３１】
基本的な参加処理はメッセージ並びに参加ノード及びその前方ノードの状態機械だけに依存する。データの転送後に、参加ノードは第３のノードに影響されることなくルーティングトポロジに即座に組み込まれる。複製リンクとともに冗長リンクは瞬間的に認証される。
【００３２】
図６はリングにおける新たなノード１３００の初期参加を説明するものである。図７に前方ノード１２００の後方でリングに参加する新たなノード１３００の参加シナリオを示す。参加処理中に、ノードは以下のステップを実行する。まず、参加処理中に、前方ノード１２００がその後方ノード１５００に完全に接続されたままの状態で、新たなノード１３００を前方ノード１２００にバインディングする。その後、分散ハッシュテーブル情報を前方ノード１２００から新たなノード１３００へ転送する。後方ノード及び冗長リンクが前方ノード１２００から新たなノード１３００へ転送される。最後に、後方ノード１５００に接触することによって新たなノード１３００がリングに完全に参加する。前方ノード１２００は後方ノード１５００に対するそのリンクのタイプを後続モードから冗長モードに変える。新たなノード１３００からの複製リンクはその新たな前方ノードからのリクエストに応じて連続的に構築される。
【００３３】
これに対して、Ｃｈｏｒｄでは、参加ノードはまずトポロジを閉じることを終了してからデータを引き継ぐ。参加は後続のノードによって扱われる。リングトポロジ及びその整合するデータバックアップは参加ノードＩとその前方ノードＰ１間の安定した前方リンクに依存する。このリンクは、新たなノードが新たな後方ノードになったという前方ノードによる情報をＰ１が受信する前には確立されない。
【００３４】
この手順は安定化アルゴリズムにおいて周期的に実行されるので、参加ノードはそれがトポロジに組み込まれる前に安定化アルゴリズムを受動的に待たなくてはならない。
【００３５】
修正Ｃｈｏｒｄでは、ノードが故障中である場合やノードの参加が瞬時に発生して何らかの安定化期間を待つことなく参加中のノードによって能動的に終了され得る場合に、参加処理中のデータ完全性がより高い。
【００３６】
図７は、ノード１３００が冗長ファクタ２のトポロジに参加する場合に影響を受けるノードによって移動されるべきデータを示す。これは、各ノードが２つの先行するノードを追跡し、これらのノードが責任を負うデータのためのバックアップノードとして作用することを示すものである。前方ノード１２００は参加処理を取り扱う。新たなノード１３００がそれらのキーに責任を負うことになるので、それ（前方ノード１２００）がキー（１３００−１５００）のためのデータを送信する。さらに、キー（１５００−２２００）のためのデータが送信される。なぜなら、新たなノード１３００がそのデータのためのバックアップとして作用するからである。ノード５００、９００及び１２００は、それらのバックアップ間隔が減少したのでデータを廃棄する。後方ノード１５００はこの処理に影響を受けない。
【００３７】
シフトされたデータ責任によって減少したルーティングは、ノードに自身の識別子以上であるがその後方ノードの識別子よりも小さい全てのキー／値の対について責任を負わせることによって達せられる。従って、メッセージのルーティングは若干変化する。
【００３８】
従来技術のＣｈｏｒｄルーティングアルゴリズムでは、リクエストは責任を負うノードの前方ノードに直接アプローチしなければならない。なぜなら、その前方ノードだけがリクエストされたキーが自身とこの責任を負うノード間に位置することを明示的に知っているからである。前方ノードは、リクエストを送付先キーよりも大きい識別子のノードに転送することが許される唯一のノードである。これによって常に最終ホップ（ここでは「ディアージャンプ」）に帰着してしまう（図２参照)。
【００３９】
ここに記載する発明に係るシステムでは、メッセージの送付先は先行するノードである。「ディアージャンプ」の問題はなくなる。従って、送付先への平均ホップ数は１だけ減るので、１ファクタ分だけパフォーマンス全体を改善する。
【００４０】
図８は新たなノード１３００を除去する手順を示す。ノード１３００によって伝達される要素は、矢印で図示するように、リング逆方向に伝搬されなければならない。その後、ノード１３００とのリンク関係は除去されなければならず、このノードの後方ノードと前方ノード間のリング関係は維持されなくてはならない。即ち、リングは閉じられ、それに従って回復リンクが維持されなければならない。
【００４１】
以下に、変形例が擬似コード表示で開示される。
Nidを現在のノード、Fiをフィンガーｉ、Nlist、succを後方ノードのリストとする。両アルゴリズムは標準的なＣｈｏｒｄと強化されたＣｈｏｒｄシステムのルーティングアルゴリズム間の差を示している。両システムは経路上にあるそれらのメッセージを最終送付先へ向けて、可能な限り大きいがメッセージの送付先識別子以下である識別子を持つノードに転送する。
【００４２】
強化されたＣｈｏｒｄでは単一の手順によって既に最終送付先に通じているが、標準Ｃｈｏｒｄは最後のホップ（「ディアージャンプ」）のための更なる手順を必要とする。この理由はノードが責任を負う範囲が異なることによる。強化されたＣｈｏｒｄシステムでは、ノードはそれ自身と次の後方ノードの間の領域に対して責任を負う。標準Ｃｈｏｒｄではそれは前方ノードとそれ自身の間の領域に対して責任を負う。従って、メッセージは現実の送付先の識別子よりも一度下がってルーティングされなければならない。これはその前方ノードによって行われるのみである。なぜなら、送付先の識別子と責任のあるノードの間に更なるピアがないこと（これは前方ノードにとっての後方ノードとなるので）を排除することができる唯一のピアだからである。このディアージャンプは以下の手順に図示されている。
【００４３】
手順１．２  Ｎ．探索（キー：見つけるべき識別子）
【数１】
2009543237.tif 000003
【００４４】
保守手順は両システムにおいて類似する。
手順１．３  Ｎ．受信（ｍｓｇ）
【数２】
2009543237.tif 000004
【００４５】
手順２．２  Ｎ．受信（ｍｓｇ）
【数３】
2009543237.tif 000005
【００４６】
ディアージャンプ回避手順は以下の通り。
手順１．１  Ｎ．最も近い先行フィンガー（キー）
【数４】
2009543237.tif 000006
【００４７】
手順２．１  Ｎ．次のホップを得る（キー）
【数５】
2009543237.tif 000007
【００４８】
なお、電気通信装置の機能の５０％以上が、例えば、メディア（ｅメール、メッセージ、マルチメディア、・・・）をサーバから検索すること、アドレス（電話、インターネット、メディアアクセス制御、ユーザ情報、コンタクトポイント）を探すこと等、データベース検索にかかわっている。従って、探索のための効率的なデータ構造の適合性は電気通信システムにとって非常に重要なものである。
【図１】
2009543237.tif 000008
【図２】
2009543237.tif 000009
【図３】
2009543237.tif 000010
【図４】
2009543237.tif 000011
【図５】
2009543237.tif 000012
【図６】
2009543237.tif 000013
【図７】
2009543237.tif 000014
【図８】
2009543237.tif 000015
【国際調査報告】
2009543237.tif 000016
2009543237.tif 000017