(57)【要約】分散ハッシュテーブル（ＤＨＴ）を含む通信ネットワーク（ＮＥＴ）であって、そのノード（Ｘ１、Ｘ２、Ｘ３・・・ＸＮ）が、通信ネットワークに接続されたネットワーク要素（Ｔ）によってアクセスされるサービスを提供し、分散ハッシュテーブル（ＤＨＴ）が、  −  ネットワーク要素（Ｔ）から、少なくとも１つのサービス識別子（ＩＤ）を含んでいるサービス位置リクエスト（Ｒ）を受信する手段、及び  −  ハッシュテーブル内の少なくとも１つの位置情報を検索する検索手段であって、各情報がサービス識別子によって示されるサービスを提供するノードに対応し、さらにそれ又はそれらをネットワーク要素に送信する、検索手段を有する。  発明は、ハッシュテーブルが、少なくとも１つのサービス識別子を含むキーに該位置情報が対応付けられるように組織化され、そのキーがＰＨＴバイナリツリーのリーフに対応し、ツリーのノードのラベルが分散ハッシュテーブル内に分散されていること、及びリーフの全部又は一部において位置情報を検索するように検索手段が設計され、リーフのラベルがサービスリクエスト内に含まれたサービス識別子のプレフィクスであることを特徴とする。
2010530096.tif 000002
【特許請求の範囲】
【請求項１】
分散ハッシュテーブル（ＤＨＴ）を含む通信ネットワーク（ＮＥＴ）であって、そのノード（Ｘ１、Ｘ２、Ｘ３・・・ＸＮ）が、該通信ネットワークに接続されたネットワーク要素（Ｔ）によってアクセスされるサービスを提供し、前記分散ハッシュテーブル（ＤＨＴ）が、
−  ネットワーク要素（Ｔ）から、少なくとも１つのサービス識別子（ＩＤ）を含んでいるサービス位置リクエスト（Ｒ）を受信する手段、及び
−  前記ハッシュテーブル内の少なくとも１つの位置情報を検索する検索手段であって、各情報が前記サービス識別子によって示されるサービスを提供するノードに対応し、さらにそれ又はそれらを前記ネットワーク要素に送信する、検索手段
を有し、
前記ハッシュテーブルが、少なくとも１つのサービス識別子を含むキーに該位置情報が対応付けられるように組織化され、そのキーがＰＨＴバイナリツリーのリーフに対応し、該ツリーのノードのラベルが前記分散ハッシュテーブル内に分散されていること、及び
リーフの全部又は一部において位置情報を検索するように前記検索手段が設計され、該リーフのラベルが前記サービスリクエスト内に含まれたサービス識別子のプレフィクスであることを特徴とする通信ネットワーク。
【請求項２】
請求項１の通信ネットワークにおいて、前記ネットワーク要素（Ｔ）が通信クライアントであってＳＩＰプロトコルと用いて通信するように設計された通信クライアントである通信ネットワーク。
【請求項３】
請求項２の通信ネットワークにおいて、前記通信クライアントが通信端末である通信ネットワーク。
【請求項４】
請求項１から３いずれか一項に記載の通信ネットワークにおいて、前記ラベル及び前記キーがバイナリワードであり、各ビットの重みが前記バイナリツリー内のレベルの増加レベルに降順で対応するような態様で前記ラベルが形成される、通信ネットワーク。
【請求項５】
請求項１から４いずれか一項に記載の通信ネットワークにおいて、前記サービスがＳＴＵＮ及び／若しくはＴＲＵＮであり、並びに／又はＩＥＴＦのＲＦＣ３４８９の２に準拠する通信ネットワーク。
【請求項６】
請求項１から５いずれか一項に記載の通信ネットワークにおいて、前記ノードが前記分散ハッシュテーブル（ＤＨＴ）のノード（Ｘ１、Ｘ２、Ｘ３・・・ＸＮ）のうちの１つである通信ネットワーク。
【請求項７】
請求項１から６いずれか一項に記載の通信ネットワークにおいて、前記ラベルが少なくとも１つのサービス識別子、トランスポートプロトコル表示、位置情報及びポートで構成された通信ネットワーク。
【請求項８】
請求項７の通信ネットワークにおいて、前記ラベルがさらに、ＩＥＴＦのＲＦＣ１６３０によってユニバーサルリソース識別子ＵＲＩを定義するパラメータの全部又は一部を含む通信ネットワーク。
【請求項９】
分散ハッシュテーブル（ＤＨＴ）によって提供されるサービスに通信デバイス（Ｄ）がアクセスすることを可能とする方法であって、前記サービスの識別子を含むサービス位置リクエストを送信するステップ、及び少なくとも１つの位置情報を前記分散ハッシュテーブルで検索するステップを含み、各情報が前記サービスを提供するノードに対応し、
前記検索ステップがＰＨＴバイナリツリー内で、少なくとも前記識別子を含むキーを検索することからなり、該ツリーのノードのラベルが前記分散ハッシュテーブル内に分散され、該検索することがリーフの全部又は一部において前記位置情報を検索することからなり、該リーフのラベルが前記サービス識別子を前に付けていることを特徴とする方法。
【請求項１０】
請求項９の方法において、前記ネットワーク要素（Ｔ）が通信クライアントであってＳＩＰプロトコルと用いて通信するように設計された通信クライアントである、方法。
【請求項１１】
請求項１０の方法において、前記通信クライアントが通信端末である、方法。
【請求項１２】
請求項９から１１いずれか一項に記載の方法において、前記ラベル及び前記キーがバイナリワードであり、各ビットの重みが前記バイナリツリー内のレベルの増加レベルに降順で対応するような態様で前記ラベルが形成される、方法。
【請求項１３】
請求項９から１２いずれか一項に記載の方法において、前記サービスがＳＴＵＮ及び／若しくはＴＲＵＮであり、並びに／又はＩＥＴＦのＲＦＣ３４８９の２に準拠している、方法。
【請求項１４】
請求項９から１３いずれか一項に記載の方法において、前記ノードが前記分散ハッシュテーブル（ＤＨＴ）のノード（Ｘ１、Ｘ２、Ｘ３・・・ＸＮ）のうちの１つである、方法。
【請求項１５】
請求項９から１４いずれか一項に記載の方法において、前記ラベルが少なくとも１つのサービス識別子、トランスポートプロトコル表示、位置情報及びポートで構成されている、方法。
【請求項１６】
請求項１５の方法において、前記ラベルがさらに、ＩＥＴＦのＲＦＣ１６３０によってユニバーサルリソース識別子ＵＲＩを定義するパラメータの全部又は一部を含む、方法。
【請求項１７】
情報処理デバイスに実装されたときに、請求項９から１６いずれか一項に記載の方法を実行するように設計されたコンピュータプログラム。
【請求項１８】
請求項１７に記載のコンピュータプログラムを含む演算媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はピアトゥピア通信ネットワークの分野に関する。より具体的には、それはそのようなピアトゥピアネットワーク内のサービスを位置特定することに関する。
【背景技術】
【０００２】
ピアトゥピア通信は所定タイプのサービスに対する有効な代替策として徐々に浸透してきている。例えば、企業ＳｋｙｐｅはボイスオーバーＩＰ（ＶｏＩＰ）又はマルチメディアオーバーＩＰ通信セッションを確立するためのピアトゥピアモデルで成功を築いてきた。
他のコンテンツ交換サービスも、とりわけｅＭｕｌｅ、Ｂｉｔｔｏｒｒｅｎｔ、及びＪＸＴＡネットワークのようなピアトゥピア技術に基づいている。
ピアトゥピアネットワークの設立理念は中央団体なしに成り立っている。サービス論理はピアトゥピアネットワークの要素全てにわたって分散され、各要素は潜在的に（サービスを要求する）クライアント及び（サービスを提供する）サーバとなり得る。
【０００３】
多くのピアトゥピアネットワークは分散ハッシュテーブルに基づいている。
分散ハッシュテーブルはピアトゥピアネットワークのような大規模に分散されたシステム内で情報を記憶及び回復するための技術である。原理として、ハッシュテーブルのコンテンツはネットワーク上のピア又はノードの全てにわたって分散され、中央化装置は存在しない。
【０００４】
そのような分散ハッシュテーブルは、とりわけ、H. Balakrishna, F. Kaashoek, D. Karger, R. Morris 、及び I. Stoicaによる論文「Look up Data in P2P Systems」、２００３年２月発行、ＡＣＭの通信ジャーナル、第４６巻第２号に記載されている。
【０００５】
図１はノードＸ１、Ｘ２、Ｘ３・・・ＸＮで構成される分散ハッシュテーブルＤＨＴを示す。
各情報は、それをキーＫに関連付けてそのキーにハッシュ関数Ｈを適用することによってＤＨＴネットワーク内に保存される。値Ｈ（Ｋ）はネットワーク内の特定のノード（例えば、インデックスｉに最も近いノード、又は値がわずかに低いもの等）を識別するためのインデックスを特定する。
情報を回復するために同じプロセスが実施される。
情報の保存及び回復メカニズムは、当業者に入手可能な、それが題材となっている多数の刊行物において既に説明されている。さらに、それらはこの記載の最後の方に多少記載される。
ここで重要なのは、保存プロセスの完全に分散された性質、及び、この態様において、保存されるべき情報のためのスペースはＮ個のノードで構成される記憶スペースに分割され得るということである。
【０００６】
この分散的な側面は、通信ネットワークアーキテクチャに対して、及びボイスオーバーＩＰ（ＶｏＩＰ）／マルチメディアオーバーＩＰ（インターネットプロトコル）アプリケーションに対してやり方は１つではないことにおいて関心事となる。
また、それによって中央化システムが、サービスの加入者数が多いときに中央化システムのサイズを増加すること、それを維持することの必要性及び複雑さ、その故障及び停止時間を扱うこと、等といった何らかの負荷を克服することも可能となる。
ピアトゥピアアーキテクチャの究極の成功は、セッション開始プロトコル（ＳＩＰ）に基づくサービスのための特定のアーキテクチャを定義することを重要視するようにＩＥＴＦ（インターネット・エンジニアリング・タスク・フォース）を促してきた。
ＳＩＰプロトコルはＩＥＴＦのＲＦＣ３２６１によって定義され、インターネットプロトコル（ＩＰ）に基づいてデータを通信するためにネットワーク上にマルチメディアセッションを交渉及び確立することが必要なシグナリングを搬送するように設計される。
この仕事は現在ＩＥＴＦのＰ２Ｐ−ＳＩＰ（「ピアトゥピアＳＩＰ」のための）ワークグループによって行われている。
この仕事を記載した１つの文献は、「dSIP: A P2P Approach to SIP Registration and Resource Location」をタイトルとして「draft-bryan-p2psip-dsip-00」の名の下に２００７年２月に発行されたＩＥＴＦドラフトに記載されている。
【０００７】
ＳＩＰプロトコルは特定数のサービス（「Ｒｅｇｉｓｔｒａｒ」等）を必要とし、それは中央化サーバによってではなく分散ハッシュテーブルによって実施され得る。
これらのサービスはまた、
−  ＲＦＣ３４８９によって定義されたＳＴＵＮ（Simple Traversal of User Datagram Protocol (UDP) through Network Address Translators (NAT)）
−  ２００５年９月に「draft-rosenberg-midcom-turn-08.txt」の名の下に「IETF draft」のステータスで発行されたＴＵＲＮ（「Traversal Using Relay NAT」）
−  メディアリレー
−  存否サービス、等  
を含むことができる。
【０００８】
これらのサービスは分散ハッシュテーブルの１以上のノードによって提供されることができるが、これはＳＩＰクライアント又は他のネットワーク要素がどのようにそれらを位置特定するかという問題を引き起こす。
【０００９】
解決のための幾つかの可能性がＩＥＴＦワークグループの議論で指摘されてきた。
第１のアプローチは、サービスとそれらを提供するサーバのアドレスの間の関連を維持することを目的とする単一の中央化されたサービスを用いることからなる。このサーバはクライアントがそれに容易に接触できるように正しく特定されたアドレスを有しているべきである。このように、ＳＴＵＮサーバを探しているクライアントは「ＳＴＵＮ」をパラメータとして含むサービスリクエストをそれに送り、そのサービスを提供する分散ハッシュテーブルのノードに対応する各アドレスとともにアドレスのリストを受信する。
【００１０】
しかし、この第１のアプローチは中央化サーバを導入するので、それはピアトゥピアネットワークの理念そのものに逆行し、満足のいくものではない。中央化アプローチの上述の欠点は、ピアトゥピアアプローチの創造と成功に導いたが、同時に、特に、このサーバがアーキテクチャにおける弱点となるともいえる。即ち、故障が起こった場合に、クライアントはもはや検索されているサービスを提供するサーバ（ノード）を位置特定することができない。またさらに、この中央化サーバは厄介なサービス拒否攻撃（ＤＯＳ）の恰好の標的となる。
【００１１】
従って、代替策は分散ハッシュテーブル自体に位置特定情報を保存することからなる。
このアプローチによる第１の解決策はキーを位置情報のセットに対応付けることからなる。この考えは２００６年１２月にＩＥＴＦのＰ２Ｐ＿ＳＩＰワークグループのメーリングリストに提出された。
しかし、これは幾つかの欠点に苛まされる。特に、分散ハッシュテーブル内のサービス数及びノード数が多い場合、位置情報は大量のスペースをとることになる。
これはこの情報を扱うノードにおける大型化の問題となってしまう。分散ハッシュテーブルの基本原理によると、テーブルは自己管理型なので、どのノードが所与の各情報を扱っているのかをチェックする方法がない。またさらに、クライアントが分散ハッシュテーブルの一部となるアーキテクチャでは、位置情報は通信クライアントのような制限された容量のノードによって管理されることになる。
記憶保存の問題に加えて、このノードがサービスリクエスト全てを受信するという欠点もある。これは通信ネットワーク内の過負荷点を作ってしまう。
【００１２】
第２の解決策はサービスの各インスタンスに対して異なる位置情報を定義することからなる。例えば、位置情報キーを形成するために、プレフィクスが各サービスに対して定義され、そのインスタンスに対するインデックス番号がそれに付加される。これは「ＳＵＴＮ１」キー（ＳＴＵＮサービスを提供する第１のサーバの少なくともＩＰアドレスを含む各位置情報に対応付けられる）、「ＴＵＲＮ５」キー（ＴＵＲＮサービスを提供する第５のサーバの少なくともＩＰアドレスを含む各位置情報に対応付けられる）等を作成するのに使用できる。
しかし今度は、利用可能なキーについての情報をどのようにして通信クライアントに提供するのか（どのようなサービスが利用可能なのか、各サービスに対してどのようなインデックスが可能なのか）という問題が起こる。
分散ハッシュテーブルは「正確な」リクエスト、即ち、正確に特定されたキーの検索しか受け付けることができないので、各位置情報の検索は、クライアントが（「ＳＴＵＮ」のような）所与のサービスに関連する全ての位置情報を得ることができるように、幾つかの連続したリクエストを必要とする。
またさらに、この方法は分散ハッシュテーブルの動的な側面を扱うことは非常に苦手である。リクエストされたサービスを提供する最後のサーバからクライアントが位置情報を受信するときには、他のサーバはテーブルに接続されているかもしれないし、他は切断されているかもしれない。これによってクライアントが最新情報を得るのが不可能となる。
【発明の概要】
【課題を解決するための手段】
【００１３】
本発明の目的は、要求されたサービスを提供するサーバのセットを位置特定するための解決策を提供することである。
【００１４】
発明の第１の目的は、通信ネットワークに接続されたネットワーク要素にアクセス可能なサービスを提供するノードを有する分散ハッシュテーブルを含む通信ネットワークである。分散ハッシュテーブルは、
−  ネットワーク要素からサービス位置リクエストを受信する手段、なお、前記リクエストが少なくとも１つのサービス識別子を含んでいる、及び
−  分散ハッシュテーブル内の位置情報の少なくとも１つを検索し、それ（又はそれら）をネットワーク要素に送信する検索手段
を有する。
これらの位置情報の各々はサービス識別子で特定されるサービスを提供するノードに対応する。
【００１５】
発明の通信ネットワークは以下を特徴とする。
−  少なくとも１つのサービス識別子を含むキーに位置情報が対応付けられるようにハッシュテーブルが組織化され、キーはバイナリＰＨＴツリー（そのノードのラベルが分散ハッシュテーブル内で分散される）のリーフに対応し、及び
−  リーフ（そのラベルがサービスリクエスト内に含まれるサービス識別子を前に付けている）の全部又は一部における位置情報を検索して、それら（ラベル）をネットワーク要素に送信するように検索手段が設計される。
【００１６】
発明の一実施例では、ネットワーク要素は通信クライアントであり、特に、ＳＩＰプロトコルを用いて通信するように設計された通信クライアントである。
この通信クライアントは通信端末であればよい。
ラベル及びキーは、各ビットの重みがバイナリツリー内の深さの増加レベルに降順に対応するような態様でラベルが形成されたバイナリワードであればよい。
例えば、質問に係るサービスはＳＴＵＮ及び／若しくはＴＵＲＮサービスであってもよいし、並びに／又はＩＥＴＦのＲＦＣ３４８９の２に準拠していてもよい。
サービスを提供するノードは分散ハッシュテーブルのノードの１つであればよい。従って、それは分散ハッシュテーブルの外部のノードであってもよい。
発明の一実施例では、ラベルは少なくとも１つのサービス識別子、トランスポートプロトコル表示、各位置情報、及びポートで構成されていればよい。位置情報は、特に、ＩＰアドレスである。
これらのラベルはまた、ＩＥＴＦのＲＦＣ１６３０によるユニバーサルリソース識別子、即ち、ＵＲＩを定義するパラメータの全て又は幾つかを含むことができる。
【００１７】
発明の他の目的は、分散ハッシュテーブルによって提供されるサービスに通信デバイスがアクセスすることを可能とする方法である。この方法は、
−  サービス位置リクエストを送信するステップ、なお、前記リクエストはサービス識別子を含んでいる、及び
−  少なくとも１つの位置情報のために分散ハッシュテーブルを検索するステップ、なお、これらの位置情報の各々はサービスを提供するノードに対応している
を含む。
本発明の方法は、検索ステップがＰＨＴバイナリツリー内（そのノードのラベルが分散ハッシュテーブル内で分散される）でキーを検索することからなることを特徴とする。
このキーは少なくともサービス識別子を含み、検索はリーフ（そのラベルがサービス識別子を前に付けている）の全部又は一部において位置情報を検索することからなる。
【００１８】
発明の一実施例は、ネットワーク要素は通信クライアントであり、特に、ＳＩＰプロトコルを用いて通信するように設計される。この通信クライアントは通信端末であればよい。
さらにまた、ラベル及びキーはバイナリワードであればよい。
ラベル及びキーは、各ビットの重みがバイナリツリー内の深さの増加レベルに降順に対応するような態様でラベルが形成されたバイナリワードであればよい。
サービスはＳＴＵＮ及び／若しくはＴＵＲＮサービスであってもよいし、並びに／又はＩＥＴＦのＲＦＣ３４８９の２に準拠していてもよい。
サービスを提供するノードは、特に、分散ハッシュテーブルのノードの１つであればよい。
【００１９】
ラベルは少なくとも１つのサービス識別子、トランスポートプロトコル表示、各位置情報、及びポートで構成されていればよい。位置情報は、特に、ＩＰアドレスである。
これらのラベルはまた、ＩＥＴＦのＲＦＣ１６３０によるユニバーサルリソース識別子、即ち、ＵＲＩを定義するパラメータの全部又は一部を含むことができる。
【００２０】
発明の他の目的は、それが情報処理デバイス上に実装されたときに、そのような方法を実行するように設計されたコンピュータプログラムである。このデバイスは、特に、通信ネットワークのような分散システムであればよい。そのような状況において、方法の種々のステップが異なる物理デバイスにわたって分散される異なるソフトウェアモジュールによって実施され得る。
発明の他の目的は、そのようなコンピュータプログラムを含んだ演算媒体である。この媒体はＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭのような光学記憶手段であればよい。それはまた、そこからコンピュータプログラムがダウンロードされ得るハードドライブ、及びそれゆえサーバであってもよい。
【００２１】
本発明及びその有利な効果は、添付図との関連で以降の記載でより明らかとなる。
【図面の簡単な説明】
【００２２】
【図１】図１は上述した分散ハッシュテーブルの図である。
【図２】図２は本発明による１つの可能なアーキテクチャを示す。
【図３】図３は例示のＰＨＴバイナリツリーの図である。
【図４】図４は通信ネットワーク内のＳＴＵＮサーバを位置特定することにおける本発明の１つのアプリケーションを示す。
【発明を実施するための形態】
【００２３】
図２に示すアーキテクチャは本発明の１つの可能な実施例を表す。通信ネットワークＮＥＴはノードＸ１、Ｘ２、Ｘ３・・・ＸＮのセットで構成される分散ハッシュテーブルＤＨＴを含む。自明な態様において、これらのノードの数は動的なものであり、それらは分散ハッシュテーブルから動的に引き抜かれ、及び追加され得る。分散ハッシュテーブルは、それを構成するノード内の情報を再分散することによってこの動的な側面を扱うアルゴリズム的手段を有する。
ネットワーク要素は通信ネットワークＮＥＴに接続され、分散ハッシュテーブルＤＨＴにアクセスすることができる。図はネットワーク要素Ｔと分散ハッシュテーブルＤＨＴの間の直接の接続を示すが、現実には、ネットワークアドレス翻訳ＮＡＴ、セッションボーダーコントローラＳＢＣ、ＳＩＰプロキシ等の種々のタイプのネットワークデバイスがこれら２つのデバイス間に配置され得る。
ネットワーク要素Ｔは通信クライアント、特に、ＳＩＰプロトコルを用いて通信ネットワークＮＥＴと通信するように設計された通信クライアントであればよい。ここで、用語「通信クライアント」とは、リクエスト、特に、ＳＩＰリクエストを送信するために設計された任意のデバイスをいうものとする。
特に、人間のユーザと対話する通信端末であればよい。
【００２４】
これらのネットワーク要素は、検索されているサービスについての少なくとも１つの識別子ＩＤを含むサービス位置リクエストＲを送信することができる。上述のように、このサービスはＳＴＵＮ、ＴＵＲＮ又はＩＣＥサービス、メディアリレー、存否サービス等であればよい。
ＩＥＴＦのＲＦＣ３４８９ビットはＳＴＵＮサービスとＴＵＲＮサービスを単一のサービスに結合する傾向にあるので、検索されているサービスも「統合されたサービス」となり得る。
【００２５】
分散ハッシュテーブルはこれらの位置リクエストを受信するように設計されている。これらの受信手段は全ノードにわたって、又はそれらの一部のみにわたって分散されていればよい。
サービス位置リクエストはネットワーク要素から受信されるが、それらは中間デバイスを介して伝搬することもできる。場合によっては、これらの中間デバイスの一部はサービス位置リクエストのコンテンツを翻訳し、サービス識別子についての最終値を特定する等、幾つかのフィールドを編集してもよい。
【００２６】
そのような場合では、分散ハッシュテーブルＤＨＴは、このサービス識別子ＩＤに対応付けられた位置情報の検索のための手段を有することになる。この位置情報は、問題となっているサービスを提供する分散ハッシュテーブルＤＨＴの１以上のノードに対応する。例えば、それはこれらのノードのＩＰ（「インターネットプロトコル」）アドレスであればよい。
一変形例では、位置情報は分散ハッシュテーブルＤＨＴの外部にあるノードに対応していてもよい。テーブルは位置特定の手段として作用し、外部ノード（又はサーバ）はそれを用いてそれ自体をサービスプロバイダとして登録し、サービス要求元にアクセスできるようにする。
【００２７】
そして、この位置情報は要求ネットワーク要素Ｔに送信される。
【００２８】
本発明において、分散ハッシュテーブルは、ＰＨＴバイナリツリー又はプレフィクスハッシュテーブル上のリーフに対応する少なくとも１つのサービス識別子を含むキーに対して位置情報が対応付けられるような態様で組織化されることを特徴とする。
【００２９】
ＰＨＴバイナリツリーは、Sriram Ramabhadran, Sylvia Ratnasamy, Joseph M. Hellerstein、及びScott Shenkerによる論文「Prefix Hash Tree - An Indexing Data Structure over Distributed Hash Tables」、２００４年２月、Technical Report, Berkeley Intel Researchで説明されている。
それはインターバルリクエストを作るために分散ハッシュテーブル上に配備された構造である。それは「トライ（ｔｒｉｅ）」の広いカテゴリに属する。トライは関連テーブルを保存するのに使用される配列されたツリーを形成するデータ構造であり、そのキーはストリングである。トライのより完全な定義は、とりわけ、Donald Knuthの「The Art of Computer Programming」第３巻「Sorting and Searching」、第３版、Addison-Wesley、１９９７年、４９２−５１２ページで見ることができる。
【００３０】
ＰＨＴでは、ストリングはバイナリストリングである。
【００３１】
ＰＨＴでは通常、ノードのラベルはノード内には保存されないが、ツリー内のノードの位置から演繹できる。
図３はＰＨＴの図である。
各ノードは２個の「子」ノードを有するか、あるいは、無し、である。無しの場合、それはバイナリツリーの「リーフ」といわれる。図ではノードｐ５、ｐ６、ｐ８、ｐ１０、ｐ１１、ｐ１３、ｐ１４、ｐ１６、及びｐ１７がリーフである。
【００３２】
このプロパティは、ＰＨＴバイナリツリーのリーフがユニバーサルプレフィクスのセットを形成することを保障し、各キーについて、１つのリーフ（そのラベルが当該キーのプレフィクスである）のみが存在する。
【００３３】
ノードがリーフではないとき、その２個の子の各々はバイナリ値のブランチ、即ち、「０」値（図の左手側ブランチ）又は「１」値（図の右手側ブランチ）のいずれかによってそれに接続される。
ルートｐ１から始まりリーフに向けて延びるブランチの値をつなげることでリーフのラベルが与えられる。例えば、リーフｐ１４はラベル「００１００」を有し、リーフｐ１０はラベル「１１０」を有する。
【００３４】
従って、ラベル付けは帰納的方法としてみることができ、ノードのラベルが１の場合には、その左及び右の子ノードは、それぞれ「１０」及び「１１」である。
【００３５】
キーはそれらのリーフのラベルに依存してＰＨＴバイナリツリーのリーフ内に保存される。より具体的には、キーＫはリーフ（そのラベルがキーＫのプレフィクスである）に保存される。
【００３６】
以下のテーブルは、上記から導かれる、図３に示す例についてのキーとマッチングリーフの間の整合の一例である。
【表１】
2010530096.tif 000003
【００３７】
ＰＨＴバイナリツリーを構築するために、２つの規則が用いられる。
−  各リーフは有限数のキーを含む。以下、最大値をＢとする。
−  各内部ノードはサブツリーにおいて最大でＢ＋１個を含む。
【００３８】
これらの２つの規則の結果として、１つのリーフが限界値Ｂよりも多いキーを含むことになった場合、それは内部ノードとなり、２個の新たなリーフが子として作られる。これらのキーは２個の子リーフ間で分散することになる。
例えば、十分多い数のキーがｐ１１に追加された場合、２個の新たなリーフがｐ１１から作られる。左側リーフｐ１１ａが「１１１０」でラベル付けされ、右側リーフｐ１１ｂが「１１１１」でラベル付けされる。そしてノードｐ１１は内部ノードとなる。
【００３９】
逆に、内部ノードがサブツリーに十分なキーを有していない場合には、サブツリーのリーフがそれらの親内部ノードに合併される。
例えば、リーフｐ１０及びｐ１１がもはや十分なキーを含まない場合、それらは消滅し、それらのキーはノードｐ７に保存され、その後それがリーフとなる。
【００４０】
またさらに、キー対リーフの関連において各キーは一回のみ現れる。（テーブルでの例として挙げたように）単一のリーフは複数のキーを含むが、単一のキーは１つのリーフのみに割り当てられる。
【００４１】
データ構造を最適化するために、バイナリツリー上の各リーフは直近右側及び左側に位置するリーフに向けたポインタを有することができる。従って、例えば、リーフｐ６はリーフｐ５及びｐ１０へのポインタを有し、リーフｐ１３はリーフｐ５及びｐ１７へのポインタを有する。
【００４２】
上述したように、バイナリツリーは分散ハッシュテーブルＤＨＴの「上に」構築される。
分散ハッシュテーブルについては種々の可能な実施例がある。
図１は容易な理解のために簡略化した例を示すが、発明はこの特定の実施例に限定されるものとして理解されるべきではない。
分散ハッシュテーブルＤＨＴのノードＸ１、Ｘ２、Ｘ３・・・ＸＮのセットは同じ役割で動作する。このテーブル（又はネットワーク）内で値を保存又は回復するために、これらのノードのいずれか１個が接触され得る。
図１の例では、上述のように、デバイスＤがノードＸ３に論理アドレスを提供することによって照会する。
このノードは提供された論理アドレスに基づいてハッシュ関数Ｈを計算する。
ハッシュ関数は大きいサイズのセット（全ての可能な論理アドレスのセット）に属する値を小さいサイズのセットに属する第２の値に変換するのに使用される関数である。ここで、この第２の値は１とＮ（Ｎを含む）の間の値である。なお、Ｎは分散ハッシュテーブルＤＨＴにおけるノード数である。
ハッシュ関数Ｈは一般に次の数学的プロパティ：Ｈ（ｘ）≠Ｈ（ｙ）→ｘ≠ｙ、を守らなければならない。
さらに、ｘ＝ｙの場合には、Ｈ（ｘ）＝Ｈ（ｙ）となる確率が高い。
関数Ｈは理想的には、アドレススペース内の均一なキー分散を実現するのに適している。この分散は多数のキーの場合に均一に向かう傾向にある。
【００４３】
ハッシュ機能によって返される値ｉによって、ノードＸ３は、ノードＸｉが受信論理アドレスと対応ドメインの間の関連を持つノードであると演繹することになる。それはこのリクエストをノードＸｉに送信する。このノードが確かに関連を持つ場合、それは論理アドレスに関連付けられたドメインを返すことになる。そうでない場合、それは関連を持つであろう他の（隣接する）ノードにリクエストを送信する。
これを反復することよって、実際に関連を持つノードにより近い方へ向かってアルゴリズムは収束する。
【００４４】
新たな関連を保存する原理も同様である。ピアトゥピアＤＨＴネットワーク上のいずれのノードも保存リクエストを受信し、ハッシュ関数及び論理アドレスに基づいて値を計算する。
この値は分散ハッシュテーブルＤＨＴの全ノード間から特定のノードを特定し、第１のノードがその特定ノードに保存リクエストを再送信する。割り当てられたノードは関連を保存する。
【００４５】
ＰＨＴバイナリツリーが使用される本発明の状況で、ＰＨＴバイナリツリーのノードのラベルはハッシュテーブルＤＨＴ内で分散される。具体的には、ラベルを保存するために、ハッシュ関数Ｈがそのラベルに適用され、バイナリツリーノードが、ハッシュ関数Ｈによって返された値によって特定されるハッシュテーブルノードで保存される。
【００４６】
本発明では、キーは少なくとも１つのサービス識別子を含み、各位置情報に対応付けられる。例えば、それらは物理アドレス、ＩＰアドレス／ポートのペア関係等を含むことができる。
【００４７】
キーはまた、例えば、使用するトランスポートプロトコルのような他の情報を含むこともできる。
キーの構造は以下のようなものであればよい。
【表２】
2010530096.tif 000004
【００４８】
このキーは、例えば、アドレスがＩＰｖ４の場合、７２ビットとなる。サービス識別子が１６ビットをとり、トランスポートプロトコル８ビット、ＩＰｖ４アドレス３２ビット、及びポート１６ビットである。
トランスポートプロトコル表示は通常は、ＩＡＮＡ（Internet Assigned Numbers Authority）によって定義された値を用いる。
ＩＰｖ６アドレスについては、それが１２８ビット長となる。
【００４９】
自然に考えて、本発明の範囲から離れることなく他のフィールドが付加され得る。
例えば、ＩＥＴＦ＿ＲＦＣ１６３０で与えられたユニバーサルリソース識別子、即ち、ＵＲＩを定義するパラメータの全部又は一部がキー構造又はラベルに付加され得る。
従って、本発明はＲＦＣ１６３０で与えられるＵＲＩのパラメータの全部（又はサブセット）を統合できるという更なる利点を有する。これは、上述したような従来のピアトゥピアアプローチを用いる場合には、ピアトゥピアネットワークで使用されるインデックスがバイナリ番号であるために、及びＵＲＩがＡＳＣＩＩストリングであるために、できないことである。ＰＨＴバイナリツリーを用いることによって、本発明はＵＲＩのＡＳＣＩＩパラメータの（必要であれば）全てを使用することを可能とする。
【００５０】
キーはＰＨＴバイナリツリー上のリーフに対応する。
より正確には、上述のように、各キーはリーフ（そのラベルがキーのプレフィクスである）に保存される。
【００５１】
（一般にキーよりも小さい）ラベルが、上述したように、分散ハッシュテーブルＤＨＴのノードに分散される。
【００５２】
上記でも示したように、分散ハッシュテーブルＤＨＴは位置リクエストを受信するように設計される。これらのリクエストは少なくとも１つのサービス識別子を含む。
さらに、これらはサービス識別子によって示されたサービスを提供する１以上の位置情報を検索する検索手段を有する。
そうするために、検索手段はＰＨＴバイナリツリー内で、サービス識別子に対応する単数又は複数のリーフに含まれるキーを検索するように設計される。
幾つかの検索方法が可能である。その幾つかは上記に引用したSriram Ramabhadran, Sylvia Ratnasamy, Joseph M. Hellerstein、及びScott Shenkerによる論文で説明されている。
【００５３】
例えば、リクエストが「ＳＴＵＮ」サービスの識別子を含む場合、検索手段はこのＳＴＵＮを提供するノードを検索し、幾つかのノードがそれを提供し、又は全てのノードがそれを提供する。言い換えると、複数のノード「ＳＴＵＮ１」、「ＳＴＵＮ２」、「ＳＴＵＮ３」・・・が同じサービスを提供する場合、どのノードが接触しているのかをリクエストの送信元が特定する必要はない。メカニズムは透明性であり、何個のノードが被リクエストサービスを提供しているのかを知る必要すらない。
特に、隣接リーフ間のポインタの使用によって、インターバル検索を容易に実行することが可能となる。また、位置リクエストは、「ＳＴＵＮ１」、「ＳＴＵＮ２」等と指定しない「ＳＴＵＮ」のようなサービス識別子を含むこともできる。その場合、検索手段は対応するリーフの全部又は一部を見つけなければならない。
分散ハッシュテーブルが検索しなければならない応答の数は、例えば、送信元がサービスを提供するＮ個のノードのみを、又はサービスを提供する全ノードのセットを望む場合には、位置リクエストにおいて指定できる。
【００５４】
検索によって見つけられたリーフに保存されるキーは位置情報を含み、それは被リクエストサービスを提供する分散ハッシュテーブルのノードに対応する。上記のように、それらは短いキーのバイナリフィールドであればよい。
この位置情報は位置リクエストの送信元に戻される。そして、それらを分散ハッシュテーブルＤＨＴのノードに接触するために使用することができる。
【００５５】
図４は通信ネットワーク内のＳＴＵＮサービスを位置特定するための本発明のアプリケーション例を示す。
４個のデバイスＮ１、Ｎ２、Ｎ３、Ｎ４が分散ハッシュテーブルＤＨＴ内に接続されている。サブネットワークＳＮはノードＮ２を他のノードＮ１、Ｎ３及びＮ４から「隔離」する。ネットワークアドレス翻訳ＮＡＴはこのサブネットワークＳＮを通信ネットワークの残りの部分に接続する。
これらのノードの幾つかはＳＴＵＮサービスを提供し、図においては斜線部で表されている。それらはノードＮ１、Ｎ２及びＮ４である。
所望の結果及び関数を生成することができるように、ＳＴＵＮサービスは通信ネットワークのパブリックスペースに位置しなければならない。それはＮＡＴデバイスによってパブリックスペースから隔離されたサブネットワークに存在してはならない。サブネットワークは互いに入れ子状となっていることがあるので、サービスをリクエストしている機器がプライベートサブネットワーク内で知られているという事実だけでは、ＮＡＴデバイスの反対側に位置するＳＴＵＮサービスが自動的にパブリックスペースに存在するものと結論付けるには不十分である。
【００５６】
この問題を解決するために、パブリックスペースに属するものとして知られるノードはＳＴＵＮサービスのプロバイダとして最初に定義される。それはブートストラップとして挙動する。
図４では、これはノードＮ１である。
この初期割当ては手動で、又は発明外の自動メカニズムによって行うことができる。
【００５７】
分散ハッシュテーブルＤＨＴにおける、ＳＴＵＮ機能を含む各ノードは、それがパブリックスペース内にあるのかＮＡＴデバイスの背後にあるのかを知らせるために、それ自体がＳＴＵＮメカニズムを介してテストされる。
そうするために、周知の態様で、例えばノードＮ４がＳＴＵＮリクエストをノードＮ１に送信する。Ｎ１はＮ４にＩＰアドレスを周知のやり方で返す。２つのノード間にＮＡＴデバイスが見つからないので、ノードＮ１によって観察されるアドレスはノードＮ４の「現実の」アドレスである。従って、Ｎ４はそれがパブリックスペースにあることを知らせることができ、自身を分散ハッシュテーブルＤＨＴにＳＴＵＮサービスのプロバイダとして追加する。
ノードＮ２はＳＴＵＮサービスを提供するノードの１つ、即ち、ノードＮ１かノードＮ４のいずれかで同じことを行うことができる。
しかし、この時、質問されたノードはＮ２が知るアドレスとは異なるアドレスを返す。そして、このことから、それはＮＡＴデバイスによってパブリックエリアから分離されたサブネットワークＳＮ内に位置するものと結論付けることができる。
従って、それはＳＴＵＮサービスを提供するノードのリストに自身を追加しない。
【００５８】
ノードをリストに追加することは上記の方法を用いて行われる。第１に、キーはＳＴＵＮサービス識別子並びにＩＰアドレス及びポートのような各位置情報に基づいて構築される。そして、キーは、ラベルが分散ハッシュテーブルＤＨＴ内に分散されたＰＨＴバイナリツリー内に保存される。
【００５９】
サブネットワークＳＮ２内に、及びネットワークアドレス翻訳ＮＡＴ２の背後に配置されるデバイスＤはＳＴＵＮサービスにアクセスすることを望む。そうするために、それは位置リクエストを分散ハッシュテーブルＤＨＴに送信する。上述のように、その後分散ハッシュテーブルＤＨＴは保存された情報を検索し、２つのアドレスＮ１及びＮ４又はこれらのうちの１つのみを返す。
そして、デバイスＤは分散ハッシュテーブルの特定ノードに接触してＳＴＵＮサービスを得ることができる。
【図１】
2010530096.tif 000005
【図２】
2010530096.tif 000006
【図３】
2010530096.tif 000007
【図４】
2010530096.tif 000008
【国際調査報告】
2010530096.tif 000009
2010530096.tif 000010
2010530096.tif 000011
2010530096.tif 000012