(57)【要約】【課題】処理時間の揺らぎを低減し、かつ、処理を高速に行うことができるピア検索方法を得ること。【解決手段】分散ハッシュテーブル方式を採用するピアツーピアネットワークを構成するピアがコンテンツ要求の送信先または転送先を転送先ピア情報のなかから検索するピア検索方法であって、転送先ピア情報に含まれるピアのハッシュ値を用いて分岐条件が定義された検索木を生成し、検索木の上段から順にコンテンツの鍵のハッシュ値が分岐条件を満たすかを判断するステップ（Ｓ１０７）と、分岐条件を満たすと判断された最も下段の分岐条件に対応するピアを検索結果とするステップ（Ｓ１０８）と、を含む。【選択図】        図３
2009134341.tif 000002
【特許請求の範囲】
【請求項１】
分散ハッシュテーブル方式を採用してコンテンツを分散管理するピアツーピアネットワークを構成するピアが、それぞれ自装置に割り当てられたハッシュ値に基づいて決定するデータ転送先のピアを転送先ピア情報として管理する場合に、コンテンツ要求の送信先または前記コンテンツ要求の転送先のピアを前記転送先ピア情報に含まれるピアのなかから検索するピア検索方法であって、
前記転送先ピア情報に含まれるピアのハッシュ値である転送先ピアハッシュ値を用いて分岐条件が定義された検索木を生成する検索木生成ステップと、
前記コンテンツ要求に対応するコンテンツの鍵のハッシュ値が前記検索木の上段から順に前記分岐条件を満たすか否かの判断を行う判断ステップと、
前記分岐条件を満たすと判断された分岐条件のうち、前記検索木の最も下段に位置する分岐条件に対応する転送先ピアハッシュ値を求め、その転送先ピアハッシュ値に対応するピアを検索結果とするピア決定ステップと、
を含むことを特徴とするピア検索方法。
【請求項２】
コンテンツを管理するピアまたはコンテンツを受信したピアが、そのコンテンツを要求元に送信するために、転送先のピアであるコンテンツ転送ピアを検索する場合に、前記判断ステップおよび前記ピア決定ステップによって前記コンテンツ転送ピアを検索することを特徴とする請求項１に記載のピア検索方法。
【請求項３】
前記判断ステップで、一度も分岐条件を満たさなかった場合には、前記転送先ピア情報に含まれるピアのうち、ハッシュ値が特定の条件を満たすピアを検索結果とすることを特徴とする請求項１または２に記載のピア検索方法。
【請求項４】
前記判断ステップの実施前に、「コンテンツ要求に対応するコンテンツの鍵のハッシュ値が前記転送先ピア情報に含まれるピアのうち、ハッシュ値が特定の条件を満たすピアにて分岐条件を満たすと判断した」と初期状態を設定し、前記判断ステップで前記分岐条件を満たすと判断された分岐条件が無かった場合には、前記ピア決定ステップでは前記初期状態を前記判断ステップの判断結果とすることを特徴とする請求項１または２に記載のピア検索方法。
【請求項５】
前記検索木生成ステップでは、前記転送先ピア情報に含まれるピアの数が前記転送先ピア情報に含まれる最大のピア数より少ない場合は、生成した検索木に、前記最大のピア数と分岐条件の数が同一となりかつ平衡木となるように、前記転送先ピア情報に含まれるピアのうち、ハッシュ値が特定の条件を満たすピアを１つまたは複数個追加することを特徴とする請求項１〜４のいずれか１つに記載のピア検索方法。
【請求項６】
前記判断ステップにおける、前記検索木の上段から順に行う判断処理のそれぞれを、並列処理により実施することを特徴とする請求項１〜５のいずれか１つに記載のピア検索方法。
【請求項７】
分散ハッシュテーブル方式を採用してコンテンツを分散管理するピアツーピアネットワークを構成し、それぞれ自装置に割り当てられたハッシュ値に基づいて決定するデータ転送先の通信装置を転送先ピア情報として管理し、コンテンツ要求の送信先または前記コンテンツ要求の転送先の通信装置を前記転送先ピア情報に含まれるピアのなかから検索する通信装置であって、
前記転送先ピア情報に含まれるピアのハッシュ値である転送先ピアハッシュ値を用いて分岐条件が定義された検索木を格納するための記憶手段と、
前記記憶手段から前記検索木を読み出し、前記コンテンツ要求に対応するコンテンツの鍵のハッシュ値が前記検索木の上段から順に前記分岐条件を満たすか否かを判断し、前記分岐条件を満たすと判断された分岐条件のうち、前記検索木の最も下段に位置する分岐条件に対応する転送先ピアハッシュ値を求め、その転送先ピアハッシュ値に対応する通信装置を検索結果とする判断手段と、
を備えることを特徴とする通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツが分散管理されるピアツーピアネットワークにおいて、検索対象のコンテンツを保持する通信装置（ピア）を探索するピア検索方法および通信装置に関するものである。
【背景技術】
【０００２】
近年、インターネットなどのＩＰ（Internet  Protocol）ネットワークを利用して、既存のネットワーク機器の機能を変更せずに、特定のサービスを行うために、様々な種類のピアツーピアネットワークが構築されており、ネットワークの数や規模は年々増加している。ピアツーピアネットワークでは、参加するピア（通信装置）の増加に比例してコンテンツ情報量が増加する。そのため、参加するピア数の多い大規模なピアツーピアネットワークでは、コンテンツをサーバで集中管理することが困難になる。
【０００３】
そこで、大規模なピアツーピアネットワークでは、コンテンツを各ピアに分散させて管理するコンテンツ分散管理方式が用いられている。コンテンツ分散管理方式の一つに、分散ハッシュテーブル技術（以降、ＤＨＴ（Distributed  Hash  Table）という）がある。ＤＨＴでは、コンテンツの題名といったコンテンツを探し出す鍵を、ハッシュ関数を用いて固定長のｂｉｔ列（ハッシュ）に変換し、ハッシュの値に応じて、そのハッシュを管理すべきピアを決める。ＤＨＴでは、ハッシュが作り出すハッシュ空間の表現方法の違いにより、幾つかの実装方式が提案されている。
【０００４】
たとえば、ハッシュ空間を一次元で表したＤＨＴ実装方式として、カリフォルニア大学バークレー校のＳｔｏｉｃａらが開発したＣｈｏｒｄがある（下記非特許文献１参照）。Ｃｈｏｒｄでは、ハッシュをＮｂｉｔで示す場合、ハッシュ値２N−１の次をハッシュ値０とすることによりハッシュ空間を円状の空間と見なしている。
【０００５】
Ｃｈｏｒｄネットワークでは、参加するピアにそれぞれユニークなハッシュが与えられる。各ピアでは、自分のハッシュ以下で、かつハッシュ空間で小さい方に隣接するピアのハッシュより大きいハッシュを持つコンテンツを管理する。例えば、３ｂｉｔ（Ｎ＝３）の一次元ハッシュ空間で、３台のピアのハッシュがそれぞれ“０”，“１”，“３”であるケースでは、ハッシュが“０”のピア（以降、ハッシュがｍのピアをピア＃ｍと呼ぶ）はコンテンツの鍵のハッシュが“４”，“５”，“６”，“７”，“０”となるコンテンツ情報だけを管理する。
【０００６】
また、参加するピアの数が多くなると、各々のピアが参加するピアの全てと接続できるメッシュ形態の転送先を管理するテーブルを持つことが、困難になる。そこで、Ｃｈｏｒｄでは各ピアは、一部のピアだけと接続する。これらのピアをＦｉｎｇｅｒと呼び、Ｆｉｎｇｅｒを管理するテーブルをＦｉｎｇｅｒテーブルと呼ぶ。各ピアは、自分のハッシュに２i（ｉは０≦ｉ＜Ｎの整数）を加算したハッシュと等しいか、それより大きなハッシュを持つ一番近いピア（以降、このピアをＦｉｎｇｅｒ［ｉ］と呼ぶ）をＦｉｎｇｅｒテーブルで管理し、Ｆｉｎｇｅｒテーブルに含まれるピアだけに転送を行う。上記の３台のピアの例では、ピア＃０は、ｉ＝０のＦｉｎｇｅｒに相当するピア１と、ｉ＝１のＦｉｎｇｅｒに相当するピア＃３のみを転送先として管理し、この２つのピアのみにデータの転送ができる。同様に、ピア＃１は、ピア＃３とピア＃０を転送先として管理し、この２つのピアのみにデータの転送ができる。また、ピア３は、ピア０のみを転送先として管理し、ピア＃０のみにデータの転送ができる。
【０００７】
各ピアは、データを受信すると、まず、そのデータのコンテンツの鍵のハッシュを求め、自分のＤＨＴで管理するハッシュかどうかを比較する。比較の結果、自分のＤＨＴの管理外のハッシュである場合には、Ｆｉｎｇｅｒテーブルの中から適切なピアを検索して求め、受信データを転送する。
【０００８】
このときのピア探索の具体的な処理内容について、説明する。ここで、［ｘ，ｙ）の表記は、ｘ以上ｙ未満のハッシュ空間の領域を示すものとする。また、コンテンツの鍵のハッシュをｈとする。はじめに、ｉ＝Ｎ−１、ｙ＝自ピアのハッシュとする。つぎに、ｘをＦｉｎｇｅｒ［ｉ］のハッシュとし、ｈが［ｘ，ｙ）の領域に含まれているかを判断し、含まれていればＦｉｎｇｅｒ［ｉ］のピアを転送先として決定する。含まれていなければ、ｙをｘとし、ｉから１を減じる。そして、再び、ｘをＦｉｎｇｅｒ［ｉ］のハッシュとして、再度ｈが［ｘ，ｙ）の領域に含まれているかを判断し、含まれていればＦｉｎｇｅｒ［ｉ］のピアを転送先とする。含まれていなければ、ｙをｘとし、さらにｉから１を減じる。そして、ピアの転送先を決定するか、ｉ＝０となるまで、ｉの値を１ずつ減じて処理を繰り返す。ｉ＝０としてもｈが［ｘ，ｙ）の領域に含まれていない場合には、転送先のピアはＦｉｎｇｅｒ［０］のピアとする。
【０００９】
ハッシュ空間では２N−１と０が繋がっていることから、ｘがｙより大きい場合もある。この場合には、ｈが［ｘ，ｙ）の領域に含まれているかの判断に替えて、ｈが［ｘ，２N−１］または［０，ｙ）に含まれているかを判断する。
【００１０】
たとえば、ピア＃１が、コンテンツの鍵のハッシュが“４”となるコンテンツを管理するピアを求めたい場合は、上述の検索処理によってＦｉｎｇｅｒ［２］＝ピア３が転送先として決定され、ピア＃１はピア＃３にデータを転送する。ピア＃３は、上述の検索処理を行い、ｉ＝０の場合もｈが［ｘ，ｙ）の領域に含まれていないため、転送先としてＦｉｎｇｅｒ［０］であるピア＃０を決定し、ピア＃０にデータを転送する。最後に、このデータを受信したピア０は、ハッシュ（鍵のハッシュ）“４”のコンテンツは自分のＤＨＴにあることから、自分が管理するコンテンツであると認識し、該当コンテンツを探し出し、ピア＃１宛てに送付する。
【００１１】
要求元のピアにコンテンツを送付するときにも、ピアツーピアネットワークを用いる場合がある。この場合も上述の検索処理によって要求元のピアを見つける。上記の例ではピア＃０が、ハッシュが“１”であるピア＃１にコンテンツを送付するために上述の検索処理を行い、ピア＃０のＦｉｎｇｅｒ［０］であるピア＃１にコンテンツを送付する。ピア＃１は、受信したコンテンツデータの要求元のピアが自ピアと一致するので、このコンテンツを取得する。
【００１２】
このようにＦｉｎｇｅｒテーブルを用いることで、参加ピア数がＫのピアツーピアネットワークでは、任意のコンテンツをＯ（ｌｏｇＫ）の転送回数で得ることができる。また、ピアツーピアネットワークに参加するピア数が多く、ピアのハッシュやコンテンツのハッシュが均等に分散されている場合、一つのピアが、ｈがＦｉｎｇｅｒ［ｉ］の管理領域に含まれているかどうかの判断（領域比較）を行う回数の期待値は、Σ｛コンテンツの鍵のハッシュがＦｉｎｇｅｒ［ｉ］に存在する確率×Ｆｉｎｇｅｒ［ｉ］に至る比較回数｝で求めることができる。ｉが大きいものほど比較回数は少なく、かつハッシュ空間に占める領域は広いため、ハッシュの存在確率が高くなり、期待値の最大は２回となる。実際のピアツーピアネットワークでは、Ｆｉｎｇｅｒ［ｉ］とＦｉｎｇｅｒ［ｉ＋１］が重なっている（Ｆｉｎｇｅｒ［ｉ］とＦｉｎｇｅｒ［ｉ＋１］が同じピア）場合があるので、重なっている場合に領域比較しない工夫を施すと、期待値は２回より小さくなる。
【００１３】
また、Ｃｈｏｒｄでは、ハッシュ関数にＳｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ  １（以降ＳＨＡ−１と呼ぶ）を採用している。ＳＨＡ−１は米国標準技術局によってアメリカ政府に採用された標準ハッシュ関数であり、電子文書の認証、改ざん検出などに用いられている。ＳＨＡ−１では１６０ｂｉｔのハッシュを生成するので、ＣｈｏｒｄのＦｉｎｇｅｒでは理論上、最大で１６０台のピアを管理する。また、ＳＨＡ−１では、１６０ｂｉｔの正の整数同士で領域比較を行うことになる。現時点では、１６０ｂｉｔの整数比較を１命令で行えるようなプロセッサは、特殊品を除いては無い。このため、複数の命令を使って領域比較を実行することになり、比較回数が増えると処理速度に影響を与えるほどの処理負荷となる。
【００１４】
一方、ピアツーピアネットワーク上でも、動画配信に代表されるような、高い伝送レートを要するサービスを利用したい要求が高まってきている。前述したように、コンテンツの要求元のピアまたはコンテンツを管理するピア以外のピアでも、データ転送を行う必要があるため、伝送レートはそれぞれのピアの転送性能に大きく左右される。サービスの伝送レートを上げるため、各ピアでデータ転送処理を効率良く実行する必要がある。
【００１５】
【非特許文献１】I．Stoica，R．Morris，D．Karger，M．F．Kaashoek  and  H．Balakrishnan，“Chord：  A  scalable  peer-to-peer  lookup  service  for  Internet  applications”，In  Proceedings  of  ACM  SIGCOMM  2001，San  Diego，CA.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記従来の技術によれば従来技術では、Ｃｈｏｒｄなど一次元ハッシュ空間を用いるピアツーピアネットワークにおける転送先のピアの探索処理の、ハッシュの値によって領域比較を行う回数が異なるため、処理時間が異なる。このため、音声サービスなど、一定の間隔でデータ受信するアプリケーションの場合、処理時間が揺らぎ、データ品質の劣化が生じる、という問題がある。たとえば、送信元ピアで音声データを一定間隔で送信した場合でも、データを中継するピアがその音声データ以外のコンテンツも転送していると、コンテンツごとに検索処理を行うため、他データの検索処理の影響を受け、音声データを出力する間隔は揺らいでしまう。その場合、音声データの要求元のピア（受信ピア）では、デコード方式によっては、受信が遅れた音声データに相当する時間だけ再生される音声が無音になってしまうこともある。中継するピアが多くなるほど、受信ピアでのデータ到着間隔が大きく揺らいでしまい、音声品質が悪くなる。
【００１７】
このようなデータの到着間隔の揺らぎを防ぐための対策として、各ピアで、常にＳＨＡ−１での最大の領域比較回数である１６０回の領域比較を行う時間を検索処理時間として確保するという方法がある。しかし、この方法では、揺らぎが無くても遅延が大きくなってしまう。遅延が大きくなると、音声が遅れて聞こえるため、通話相手の反応が遅くなり、通話者に不快を与える、という問題がある。
【００１８】
また、遅延を低減するため、処理を並列化することで処理時間の低減を図る方法があるが、前述のように比較回数の期待値は２回なので、ＳＨＡ−１で１６０回の領域比較の処理時間は８０並列化して期待値と同等の処理時間となる。しかし、８０もの並列処理は現実的ではない。したがって、ある程度の並列処理を行ったとしても、揺らぎを防ぐ対策を行うと、対策をしない場合より遅延が大きくなってしまう、という問題がある。
【００１９】
また、ファイル転送サービスのような、データ到着間隔の影響を受けないサービスを考える。多くのファイル転送サービスでは、ＩＰネットワークにおいてＴＣＰ／ＩＰプロトコルを用いている。ＴＣＰ／ＩＰは、ピア間の伝送特性により伝送レートを変更するフロー制御機能を持つ。この機能は、データ到着遅延が大きくなるほど、送信元ピアの送信レートを落とすように作用する。そのため、上述のような揺らぎを防ぐ対策を行うと、ＴＣＰ／ＩＰを用いたデータ転送レートが低くなってしまう、という問題がある。
【００２０】
本発明は、上記に鑑みてなされたものであって、コンテンツが分散管理されるピアツーピアネットワークにおいて、コンテンツを管理するピアの検索処理の処理時間の揺らぎを低減し、また、コンテンツを管理するピアの検索処理を高速に行うことができるピア検索方法および通信装置を得ることを目的とする。
【課題を解決するための手段】
【００２１】
上述した課題を解決し、目的を達成するために、本発明は、分散ハッシュテーブル方式を採用してコンテンツを分散管理するピアツーピアネットワークを構成するピアが、それぞれ自装置に割り当てられたハッシュ値に基づいて決定するデータ転送先のピアを転送先ピア情報として管理する場合に、コンテンツ要求の送信先または前記コンテンツ要求の転送先のピアを前記転送先ピア情報に含まれるピアのなかから検索するピア検索方法であって、前記転送先ピア情報に含まれるピアのハッシュ値である転送先ピアハッシュ値を用いて分岐条件が定義された検索木を生成する検索木生成ステップと、前記コンテンツ要求に対応するコンテンツの鍵のハッシュ値が前記検索木の上段から順に前記分岐条件を満たすか否かの判断を行う判断ステップと、前記分岐条件を満たすと判断された分岐条件のうち、前記検索木の最も下段に位置する分岐条件に対応する転送先ピアハッシュ値を求め、その転送先ピアハッシュ値に対応するピアを検索結果とするピア決定ステップと、を含むことを特徴とする。
【発明の効果】
【００２２】
この発明によれば、転送先ピアのハッシュ値を用いて分岐条件を定めた検索木を用いて、コンテンツの鍵のハッシュが分岐条件を満たすか否かを判断し、分岐条件を満たすハッシュに対応するピアのなかで検索木の最も下段のピアを検索結果とするようにしたので、コンテンツを管理するピアの検索処理の処理時間の揺らぎを低減し、かつ、ピアの検索処理を高速に行うことができる、という効果を奏する。
【発明を実施するための最良の形態】
【００２３】
以下に、本発明にかかるピア検索方法および通信装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００２４】
実施の形態１．
図１は、本発明にかかる実施の形態１のネットワークシステムの一次元ハッシュ空間におけるピア（通信装置）の配置例を示す図である。図１の一次元ハッシュ空間１は、６ビットのハッシュ空間を示している。本実施の形態のネットワークシステムは、６ビットのハッシュを各ピアに割り当てるピアツーピアネットワークである。また、本実施例では、コンテンツを分散管理することとし、各ピアは、コンテンツの鍵のハッシュが自分のＤＨＴの範囲にあるコンテンツを管理していることとする。
【００２５】
図１のピア２は、コンテンツを検索するピアでありハッシュ“３０”が割り当てられている。Ｆｉｎｇｅｒピア３は、ピア２が管理するＦｉｎｇｅｒテーブルに含まれるピアである。図１では、ピア２とピア２がＦｉｎｇｅｒテーブルで管理するピアのみを示しているが、本実施の形態のネットワークシステム全体としては、一次元ハッシュ空間１上にこれら以外のピアも含んでいることとする。
【００２６】
図２−１は、ピア２が管理するＤＨＴの一例を示す図である。ピア２は、コンテンツの鍵のハッシュがＤＨＴの範囲に含まれるコンテンツを管理している。したがって、この場合は、ピア２は、コンテンツの鍵のハッシュが“２６〜３０”の範囲にあるコンテンツを管理している。
【００２７】
本実施の形態では、所望のコンテンツを管理するピアを検索するために、２分検索木を用いる。図２−２は、ピア２の２分検索木の一例を示す図である。本実施の形態では、Ｆｉｎｇｅｒテーブルに含まれる各ピアのハッシュに基づいて２分検索木を生成する。本実施の形態では、ＤＨＴ実装方式としてＣｈｏｒｄ方式を採用することとし、自分のハッシュに２i（ｉは０≦ｉ＜Ｎの整数：Ｎはハッシュのビット数）を加算したハッシュと等しいか、それより大きなハッシュを持つ一番近いピアだけをＦｉｎｇｅｒテーブルにより管理する。図２−２の上図は、ピア２のＦｉｎｇｅｒテーブルを示し、ｉごとに、自分（ピア２）のハッシュに２iを加算したハッシュをＦｉｎｇｅｒ［ｉ］のハッシュとして示している。以下では、ＦｉｎｇｅｒテーブルのｉをＦｉｎｇｅｒ識別番号と呼ぶこととする。図２−１では下図の２分検索木の各ノードをハッシュの値で示しているが、実際には、２分検索木は、Ｆｉｎｇｅｒ識別番号と対応するハッシュの両方が２分検索木で管理されていることとする。なお、２分検索木の生成方法は、通常の検索木の生成方法であればどのような方法により生成してもよい。
【００２８】
つづいて、本実施の形態の、所望のコンテンツを管理するピアを検索するための処理（ピア検索処理）について説明する。図３は、本実施の形態のピア検索処理手順の一例を示すフローチャートである。
【００２９】
従来のピア検索処理では、Ｆｉｎｇｅｒごとに、コンテンツの鍵のハッシュがそれぞれのＦｉｎｇｅｒが管理するコンテンツの範囲に含まれるか否かをそれぞれ判断していた。本実施の形態では、２分検索木の上段から順に、コンテンツの鍵のハッシュが２分検索木を構成する各ノードのハッシュ未満の値である（条件成立）か否かの判断を実施して、条件成立した最後のノードに対応するＦｉｎｇｅｒをコンテンツの送信先のピアとして求める。
【００３０】
図２−１，図２−２，図３を用いて本実施の形態のピア検索処理を説明する。まず、ピア２は、所望のコンテンツの鍵のハッシュを求め、ｈとする（ステップＳ１０１）。つぎに、ピア２は、ｈが自分のＤＨＴのなかにあるか否かを判断する（ステップＳ１０２）。ｈが自分のＤＨＴのなかにあると判断した場合（ステップＳ１０２  Ｙｅｓ）は、コンテンツは自分が管理していると判断し（ステップＳ１０３）、ピア検索処理を終了する。
【００３１】
ｈが自分のＤＨＴのなかにないと判断した場合（ステップＳ１０２  Ｎｏ）は、変数ｄｓｔを初期化する（たとえば、ＮＵＬＬを代入する）（ステップＳ１０４）。ｄｓｔは、コンテンツ要求の送信先として求めるＦｉｎｇｅｒのハッシュを示す数値である。つぎに、図２−２で示した２分検索木の根ノードに対応するＦｉｎｇｅｒ識別番号（図２−１のＦｉｎｇｅｒテーブルのｉ）をｐに代入する（ステップＳ１０５）。ｐは、後述のステップＳ１０７で条件成立の判断対象となるＦｉｎｇｅｒのＦｉｎｇｅｒ識別番号を示す変数である。つぎに、ピア２は、変数ｘにＦｉｎｇｅｒ［ｐ］を代入する（ステップＳ１０６）。
【００３２】
つぎに、ピア２は、ｈがｘより小さいか否かを判断し（ステップＳ１０７）、ｈがｘより小さくないと判断した場合（ステップＳ１０７  Ｎｏ：条件成立）は、ｄｓｔにｘを代入する（ステップＳ１０８）。そして、ｐが２分検索木の最下段のノードであるか否かを判断し（ステップＳ１０９）、最下段のノードでないと判断した場合（ステップＳ１０９  Ｎｏ）は、２分検索木の右下のノードのＦｉｎｇｅｒ識別子をｐに代入し（ステップＳ１１０）、ステップＳ１０６に戻り、ステップＳ１０６以降の処理を繰り返す。
【００３３】
また、ステップＳ１０７で、ｈがｘより小さいと判断した場合（ステップＳ１０７  Ｙｅｓ：条件非成立）は、さらに、ｐが２分検索木の最下段のノードであるか否かを判断する（ステップＳ１１１）。そして、ステップＳ１１１で最下段のノードでないと判断した場合（ステップＳ１１１  Ｎｏ）は、２分検索木の左下のノードのＦｉｎｇｅｒ識別子をｐに代入し（ステップＳ１１２）、ステップＳ１０６に戻り、ステップＳ１０６以降の処理を繰り返す。
【００３４】
ステップＳ１０９で最下段のノードであると判断した場合（ステップＳ１０９  Ｙｅｓ）、および、ステップＳ１１１で最下段のノードであると判断した場合（ステップＳ１１１  Ｙｅｓ）は、ｄｓｔが初期化されたままであるか否かを判断し（ステップＳ１１３）、初期化されたままでないと判断した場合（ステップＳ１１３  Ｎｏ）には、検索処理を終了する。ステップＳ１１３でｄｓｔが初期化されたままであると判断した場合（ステップＳ１１３  Ｙｅｓ）には、ｄｓｔにＦｉｎｇｅｒテーブル上のＦｉｎｇｅｒ［ｉ］の最大値（最大Ｆｉｎｇｅｒ）を代入し（ステップＳ１１４）、処理を終了する。
【００３５】
ピア２は、以上のピア検索処理の後、ステップＳ１０３でコンテンツは自分が管理していると判断した場合（ステップＳ１０３  Ｙｅｓ）には、自分が管理しているそのコンテンツの情報に基づいてコンテンツを取得する。それ以外の場合は、ピア２は、検索処理の終了時点のｄｓｔに対応する（ｄｓｔの値がハッシュとして割り当てられている）Ｆｉｎｇｅｒへコンテンツの取得要求（コンテンツの鍵を含む）を送信する。
【００３６】
ｈ＝３１のケースを一例として、図３の処理を具体的に説明する。“３１”はピア２のＤＨＴのなかに無いため、ステップＳ１０４〜ステップＳ１０７を実施する。ステップＳ１０７では、“３１”は、根ノードのハッシュ“３６”より小さいため条件非成立となる。また、この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。２回目のステップＳ１０７では、ｈは、２番目のノードのハッシュ“３１”より小さくないため条件成立となり、ステップＳ１０８へ進む。そして、この時点でｐは最下段ではないので、ステップＳ１０９，ステップＳ１１０を実施し、ｐを右下のノードとして、ステップＳ１０６へ戻る。３回目のステップＳ１０７では、ｈは３番目のノードのハッシュ“３２”より小さいので条件非成立となり、ステップＳ１１１にすすむ。この時点でｐは最下段となるので、さらに、ステップＳ１１３に進む。ステップＳ１１３の判断では、ｄｓｔは初期化されたままではないと判断される（ステップＳ１１３  Ｎｏ）ため、そのまま処理を終了する。そして、処理の終了時点では、最後に条件成立したノードのハッシュ“３１”がｄｓｔに代入されており、ハッシュが“３１”に対応するピアがコンテンツ要求の送信先となる。
【００３７】
つぎに、ｈ＝２のケースを一例として、同様に図３の処理を具体的に説明する。“２”はピア２のＤＨＴのなかに無いため、ステップＳ１０４〜ステップＳ１０７を実施する。ステップＳ１０７では、“２”は、根ノードのハッシュ“３６”より小さいため条件非成立となる。また、この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。２回目のステップＳ１０７では、ｈは、２番目のノードのハッシュ“３１”より小さいためふたたび条件非成立となる。この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。３回目のステップＳ１０７では、ｈは３番目のノードのハッシュ“５”より小さいので条件非成立となり、ステップＳ１１１に進むが、この時点でｐは最下段のノードである（ステップＳ１１１  Ｙｅｓ）ため、ステップＳ１１３に進む。この例では、ｄｓｔは一度も更新されていないため初期値のままである。したがって、ステップＳ１１３では、ｄｓｔは初期値のままであると判断し（ステップＳ１１３  Ｙｅｓ）、ステップＳ１１４でｄｓｔに最大Ｆｉｎｇｅｒが代入される。
【００３８】
ｈ＝２のように、Ｆｉｎｇｅｒテーブルの中の一番小さなハッシュより小さなｈは、一次元ハッシュ空間１上で、ハッシュ０を挟んでＦｉｎｇｅｒテーブルの中の最大のハッシュと最小のハッシュの間に存在する。このため、本実施の形態では、ステップＳ１０７の判断で条件成立が一度もなかった場合（ｄｓｔが初期値のまま）に、コンテンツ要求の送信先を、Ｆｉｎｇｅｒテーブルの中の最大のハッシュである“４８”に対応するピアとする。
【００３９】
図４−１は、ｈ＝３１の場合の本実施の形態のピア検索処理の概念を示す図であり、図４−２は、ｈ＝２の場合の本実施の形態のピア検索処理の概念を示す図である。図４−１，４−２では、条件成立するノードに○を示し、条件非成立となるノードに×を示している。
【００４０】
以上の説明では、ピア２が、コンテンツ要求の送信先を選択する例を述べたが、コンテンツ要求は、直接、そのコンテンツを管理するピアに送信されるとは限らない。したがって、コンテンツ要求を受信したピアでは、上述したピア検索処理を同様の処理で行い、そのコンテンツ要求が自ピアで管理するコンテンツに関する要求でないと判断した場合には、ピア検索処理によって送信先として求めたピアにそのコンテンツ要求を転送する。このような動作を繰り返すことにより、最終的にピア２から要求されたコンテンツを管理するピアへコンテンツ要求が送信されることになる。
【００４１】
なお、本実施の形態では、コンテンツを取得する際の処理について説明したが、コンテンツを管理するピアが、そのコンテンツを要求元（上述の例の場合はピア２）へコンテンツを送信する場合に、要求元のピアを検索する場合に、ピア検索処理と同様の処理を行ってコンテンツを送信すべきピアを検索するようにしてもよい。
【００４２】
また、本実施の形態では、２分検索木を用いてピア検索処理を行う例について説明したが、これに限らず、検索木を用いる方法であれば、これに限らずどのような検索木を用いてもよい。たとえば、４分検索木の場合、条件成立を判断するためのハッシュは３つの数値となるが、これらをｚ（１），ｚ（２），ｚ（３）とする。このとき、たとえば、ｈがｚ（１）より小さい場合は、条件非成立とし、ｈがｚ（１）以上かつｚ（２）未満の場合はｚ（１）に対して条件成立とし、ｈがｚ（２）以上かつｚ（３）未満の場合はｚ（２）に対して条件成立とし、ｈがｚ（３）以上の場合はｚ（３）に対して条件成立として、検索処理を順次すすめていくようにすればよい。
【００４３】
このように、本実施の形態では、Ｆｉｎｇｅｒを検索するための検索木を用いて、検索木の各ノードごとに条件成立のためのハッシュの範囲を定め、条件成立するノードのなかの検索木の最も下段のノードに対応するピアをコンテンツ要求の送信先として選択するようにした。このため、従来のピア検索処理にくらべ、高速に処理を行うことができる。また、ｈの値の違いによる処理時間の違い（揺らぎ）も低減することができる。
【００４４】
たとえば、Ｆｉｎｇｅｒの二分木を平衡させるものとする（必須条件ではない）と、Ｎｂｉｔの一次元ハッシュ空間での本方式のハッシュ比較回数の最大は、Ｒｏｕｎｄ（ｌｏｇ２（Ｎ＋１））に抑えることができる（Ｒｏｕｎｄは切り上げの関数）。Ｃｈｏｒｄの１６０ｂｉｔの一次元ハッシュ空間で比較すると、従来技術での最大比較回数が１６０回（領域の両端で比較するため、実際には２倍になる）であったのに対し、本実施の形態では最大比較回数を９回に削減できる。
【００４５】
実施の形態２．
図５は、本発明にかかる実施の形態２のピア検索処理手順の一例を示すフローチャートである。本実施の形態のネットワークシステムの構成は実施の形態１と同様である。実施の形態１と同様の構成要素については、同一の符号を用いることとし、説明を省略する。本実施の形態のピア２のＦｉｎｇｅｒテーブルおよび２分検索木も、実施の形態１と同様とする。
【００４６】
図５に示すように、ステップＳ１０１、ステップＳ１０２は実施の形態１と同様である。ステップＳ１０２でｈが自分のＤＨＴに含まれると判断した場合（ステップＳ１０２  Ｙｅｓ）は、実施の形態１と同様にステップＳ１０３に進み、処理を終了する。ステップＳ１０２でｈが自分のＤＨＴに含まれないと判断した場合（ステップＳ１０２  Ｎｏ）には、ｄｓｔに最大Ｆｉｎｇｅｒを代入する（ステップＳ２０１）。そして、実施の形態１と同様のステップＳ１０５〜ステップＳ１１２を実施する。ただし、ステップＳ１１１でｐが最下段であると判断した場合（ステップＳ１１１  Ｙｅｓ）、および、ステップＳ１０９でｐが最下段であると判断した場合（ステップＳ１０９  Ｙｅｓ）には、実施の形態１のステップＳ１１３，Ｓ１１４を実施せず、処理を終了する。本実施の形態のこれ以外の処理は、実施の形態１と同様である。
【００４７】
ｈ＝３１のケースを一例として、図５の処理を具体的に説明する。“３１”はピア２のＤＨＴのなかに無いため、ｄｓｔに最大Ｆｉｎｇｅｒを代入する（ステップＳ２０１）。そして、ステップＳ１０５〜ステップＳ１０７を実施する。ステップＳ１０７では、“３１”は、根ノードのハッシュ“３６”より小さいため条件非成立となる。また、この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。２回目のステップＳ１０７では、ｈは、２番目のノードのハッシュ“３１”より小さくないため条件成立となり、ステップＳ１０８へ進む。そして、この時点でｐは最下段ではないので、ステップＳ１０９，ステップＳ１１０を実施し、ｐを右下のノードとして、ステップＳ１０６へ戻る。３回目のステップＳ１０７では、ｈは３番目のノードのハッシュ“３２”より小さいので条件非成立となり、ステップＳ１１１にすすむ。この時点でｐは最下段となるので、そのまま処理を終了する。そして、処理の終了時点では、最後に条件成立したノードのハッシュ“３１”がｄｓｔに代入されており、ハッシュが“３１”に対応するピアがコンテンツ要求の送信先となる。
【００４８】
つぎに、ｈ＝２のケースを一例として、同様に図５の処理を具体的に説明する。“２”はピア２のＤＨＴのなかに無いため、ｄｓｔに最大Ｆｉｎｇｅｒを代入する（ステップＳ２０１）。そして、ステップＳ１０５〜ステップＳ１０７を実施する。ステップＳ１０７では、“２”は、根ノードのハッシュ“３６”より小さいため条件非成立となる。また、この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。２回目のステップＳ１０７では、ｈは、２番目のノードのハッシュ“３１”より小さいためふたたび条件非成立となる。この時点でｐは最下段ではないので、ステップＳ１１１，ステップＳ１１２を実施し、ｐを左下のノードとして、ステップＳ１０６へ戻る。３回目のステップＳ１０７では、ｈは３番目のノードのハッシュ“５”より小さいので条件非成立となり、ステップＳ１１１に進むが、この時点でｐは最下段のノードである（ステップＳ１１１  Ｙｅｓ）ため、そのまま処理を終了する。処理の終了時点では、ｄｓｔは最大Ｆｉｎｇｅｒが代入されたままなので、最大Ｆｉｎｇｅｒの“４８”に対応するピアがコンテンツ要求の送信先となる。
【００４９】
図６−１は、ｈ＝３１の場合の本実施の形態のピア検索処理の概念を示す図であり、図６−２は、ｈ＝２の場合の本実施の形態のピア検索処理の概念を示す図である。図６−１，６−２では、条件成立するノードに○を示し、条件非成立となるノードに×を示している。
【００５０】
このように、本実施の形態では、Ｆｉｎｇｅｒを検索するための検索木を用いて、検索木のノードごとに条件成立のためのハッシュの範囲を定め、送信先のピアのハッシュ値の初期値として最大Ｆｉｎｇｅｒを設定した後に、条件成立するノードのなかの最下段のノードに対応するピアをコンテンツ要求の送信先として選択するようにした。このため、実施の形態１と同様の効果を得られるとともに、実施の形態１にくらべ処理を削減することができる。本実施の形態の処理をハードウエアで実現する場合、実施の形態１には必要であった、ステップＳ１１３，Ｓ１１４の処理の回路が不要となり、初期値を与えるだけで済むので、全体の回路構成が簡単になり、ハードウエア化が容易となる。
【００５１】
実施の形態３．
図７は、本発明にかかる実施の形態３のネットワークシステムの一次元ハッシュ空間におけるピア（通信装置）の配置例を示す図である。図７の一次元ハッシュ空間１ａは、１５ビットのハッシュ空間を示している。本実施の形態のネットワークシステムは、１５ビットのハッシュを各ピアに割り当てるピアツーピアネットワークである。また、本実施例では、コンテンツを分散管理することとし、各ピアは、コンテンツの鍵のハッシュが自分のＤＨＴの範囲にあるコンテンツを管理していることとする。図７に示すハッシュ空間において、３０〜４０台ほどのピアがネットワークに参加していると仮定して以下の説明を行う。
【００５２】
本実施の形態では、コンテンツの要求元のピア２には、ハッシュ“６０００ｈ”（ｈは１６進数を示す）が割り当てられているとする。図８は、本実施の形態のピア２のＦｉｎｇｅｒテーブルの一例を示す図である。ネットワークに参加するピアのハッシュが特定の範囲に集中することは少なく、多くの場合分散するため、ハッシュ空間を“１０００ｈ”ごとの範囲に分割して考えると、それぞれの範囲に３〜６台ずつ位存在することが多い。そのため、Ｆｉｎｇｅｒ［ｉ］のｉが小さい場合には、複数のｉに対応するＦｉｎｇｅｒ［ｉ］が同一になることが多くなる。
【００５３】
たとえば、図８の例では、ピア２のハッシュ値に２0，２1，…，２8をそれぞれ加算した範囲に相当する“６００１ｈ”〜“６１００ｈ”間のハッシュを持つピアが存在せず、ピア２に一番近いハッシュ値をもつのは、ハッシュが“６１Ｆ０ｈ”となるピアであるため、Ｆｉｎｇｅｒ［０］〜Ｆｉｎｇｅｒ［８］は“６１Ｆ０ｈ”となる。同様に、Ｆｉｎｇｅｒ［９］もＦｉｎｇｅｒ［１０］も同一となる。
【００５４】
一方、１５ｂｉｔのハッシュ空間では、Ｆｉｎｇｅｒの二分検索木は最大で４段の深さを持つ。図８の例では、Ｆｉｎｇｅｒ［ｉ］が同一となるｉが多くなるため、Ｆｉｎｇｅｒ［ｉ］の実質のピア数が１５より少ない。本実施の形態では、このような場合でも二分検索木を構成するノード（ピア）数が１５個となるように、最大のハッシュとなるピアをダミーとして複製する。すなわち、本実施の形態では、二分検索木は平衡木となる。こうして作成した二分検索木の一例が図９−１，図９−２である。図９−１，図９−２では、条件成立するノードに○を示し、条件非成立となるノードに×を示している。図９−１は、ｈ＝７Ｆ００ｈとした場合の例であり、図９−２は、ｈ＝２１Ｅ３ｈの場合の例である。
【００５５】
本実施の形態のピア検索処理は、図３で説明した実施の形態１と同様である。また、コンテンツ検索処理以外の動作も、上述の二分検索木の生成方法以外は、実施の形態１と同様である。ｈ＝７Ｆ００ｈの場合を一例に、本実施の形態のピア検索処理を具体的に説明する。“７Ｆ００ｈ”はピア２のＤＨＴに含まれていないとする。まず、図３のステップＳ１０１およびステップＳ１０２を実施し、ステップＳ１０２では、ｈは、自分のＤＨＴに含まれていないと判断して（ステップＳ１０２  Ｎｏ）、ステップＳ１０４〜Ｓ１０７を実施する。ステップＳ１０７では、ｈが根ノードのハッシュ“７３２１ｈ”以上なので、条件成立となり、ステップＳ１０８へ進む。そして、この時点でｐは最下段ではないので、ステップＳ１０９，ステップＳ１１０を実施し、ｐを右下のノードとして、ステップＳ１０６へ戻る。２回目のステップＳ１０７でもｈを“７３２１ｈ”と比較することになるので、1回目と同様にステップＳ１０８〜ステップＳ１１０を実施してステップＳ１０６へ戻る。以降、３回目、４回目のステップＳ１０７でも条件成立となり、４回目のステップＳ１０７の後は、ステップＳ１０８，Ｓ１０９を実施後、ステップＳ１１３に進み、処理を終了する。処理の終了時点で、最後に条件成立したハッシュ“７３２１ｈ”に対応するピアがコンテンツ要求の送信先となる。
【００５６】
また、ｈ＝２１Ｅ３ｈの場合については以下のようになる。“２１Ｅ３ｈ”はピア２のＤＨＴに含まれていないとする。まず、図３のステップＳ１０１およびステップＳ１０２を実施し、ステップＳ１０２では、ｈは、自分のＤＨＴに含まれていないと判断して（ステップＳ１０２  Ｎｏ）、ステップＳ１０４〜Ｓ１０７を実施する。ステップＳ１０７では、ｈが根ノードのハッシュ“７３２１ｈ”未満なので、条件非成立となり、ステップＳ１１１へ進む。そして、ステップＳ１１１，ステップＳ１１２の実施後にステップＳ１０６に戻る。２回目のステップＳ１０７では、ｈは２段目のノードの“６６ＢＡｈ”未満なので、条件非成立となり、ステップＳ１１１へ進む。そして、ステップＳ１１１，ステップＳ１１２の実施後にステップＳ１０６に戻る。そして、３回目のステップＳ１０７では、ｈは３段目のノードの“２１Ｅ３ｈ”以上なので、条件成立となりステップＳ１０８へ進む。そして、この時点でｐは最下段ではないので、ステップＳ１０９，ステップＳ１１０を実施し、ｐを右下のノードとして、ステップＳ１０６へ戻る。４回目のステップＳ１０７では、ｈは４段目のノードの“６１Ｆ０ｈ”未満なので、条件非成立となり、ステップＳ１１１，ステップＳ１１３の後に処理を終了する。そして、処理の終了時に最後に成立したハッシュ“２１Ｅ３ｈ”に対応するピアがコンテンツ要求の送信先となる。
【００５７】
本実施の形態では、コンテンツ探索処理に要する時間は、コンテンツおよびピアのハッシュに依存せず、またＦｉｎｇｅｒの個数にも依存せずに一定となる。図１０−１は、本実施の形態のピア検索処理を用いた場合の並列処理タイミングの一例を示す図である。図１０−２は、従来のピア検索処理を用いた場合の並列処理タイミングの一例を示す図である。図１０−１に示すように、各ピアは、受信したピアツーピアネットワークデータを、３個のスレッド（スレッド＃１〜スレッド＃３）で並列処理して出力しているとする。また、コンテンツＡのデータをデータＡとし、コンテンツＡとは異なるコンテンツであるコンテンツＢのデータをデータＢとする。このとき、ピア検索処理の処理時間が一定であるとすると、図１０−１に示すように、データＡの送信間隔は、受信間隔とほぼ等しくなり、到着間隔に揺らぎが生じないという効果がある。
【００５８】
一方、図１０−２に示すコンテンツ検索処理を用いた例でも、図１０−１と同様に、各ピアは、受信したピアツーピアネットワークデータを、３個のスレッドで並列処理して出力しているとする。このとき、図１０−１の例の場合は、ピア検索処理時間が、ハッシュに依存するため一定ではない。ここでは、データＡのピア検索処理時間の方が、データＢのピア検索処理時間より短いものとする。この場合、スレッド＃２がデータＢの送信処理中（送信処理完了前）に、スレッド＃３は、ピア検索処理が完了してしまう。したがって、スレッド＃２とスレッド＃３の使用するネットワークポートが重なっている場合には、スレッド＃３は、スレッド＃２のデータＢの送信処理完了を待って、データＡの送信処理を開始する。この待機時間が発生するため、データＡの送信間隔が、受信間隔よりも長くなる。したがって、受信間隔に揺らぎが発生してしまうという問題が生じる。これに対し、上述のように本実施の形態では、受信間隔の揺らぎは生じない。
【００５９】
ところで、データの遅延時間を考えると、従来方式の方が処理時間が短く、データの遅延時間も短いケースもある。上述のように、Ｎｂｉｔのハッシュ空間では、従来のピア検索処理の領域比較を行う回数の期待値が２回×２（１領域で２回の比較）であるのに対し、本探索方式では、常に、Ｒｏｕｎｄ（ｌｏｇ（Ｎ＋１））回の条件成立の判断を行うので、Ｎ＝１６０のＣｈｏｒｄ方式の場合、判断回数は９回となり、従来の領域比較回数の期待値より大きくなるためである。
【００６０】
しかしながら、本実施の形態のピア検索処理では、並列化の効果が線形的に得られる。すなわち、たとえば、図１０−１のように３並列化を行うと、処理時間を３分の１に削減することができる。最大９回の判断を行う場合、並列化すると３回分の処理に相当するので、揺らぎの発生を防ぎつつ、従来の方式に比べて処理速度を向上させることも可能である。また、処理時間を一定にしていることから、ハードウエア回路では、待ち合わせ用バッファなどの回路を不要にできるため、従来方式に比べてさらに並列化の実現が容易になる。
【００６１】
図１１は、本実施の形態のピア検索処理をハードウエアで実現する検索処理装置の機能構成例を示す図である。図１１では、図３のステップＳ１０６およびステップＳ１０７（以下、比較処理という）に相当する処理を行う構成要素についてのみ示している。図１１に示すように、検索処理装置は、比較回路（判断手段）４と、メモリ５と、メモリバス６と、で構成される。
【００６２】
各ピアのＦｉｎｇｅｒテーブルは、メモリ５に格納されている。比較回路４は、メモリバス６経由でリード命令を送信することにより一つ分のＦｉｎｇｅｒの情報（Ｆｉｎｇｅｒ［ｉ］）を読み出す。Ｆｉｎｇｅｒの情報は、２分検索木におけるＦｉｎｇｅｒ［ｉ］の位置と関連付けて格納されているとする。比較回路４は、図３の比較処理を行う場合、Ｆｉｎｇｅｒ［ｐ］に対応するアドレスを指定してメモリバス６経由でメモリ５にリード命令を送信し、メモリ５からメモリバス６経由でリード応答としてＦｉｎｇｅｒ［ｐ］の値を得てｘとする。そして、ｈとｘを比較する。ここで、比較回路４，メモリ５，メモリバス６の処理はパイプライン化できる。パイプライン化すると、この構成例では、パイプライン化しない場合の３倍の速度で処理を行うことが可能である。図１２は、パイプライン化した場合の処理の一例を示す図である。
【００６３】
なお、本実施の形態では処理時間を一定にしていることから、パイプライン化しても、比較処理の結果が出力される順番が入れ替わることが無い。そのため、後段に順序保証回路を設ける必要はなく、また、比較回路４から前段へ、探索が完了して入力を送っても良いことを知らせる信号を送る必要もない。また、前段での待ち合わせ回路も不要である。このため、パイプライン化による高速処理可能なハードウエアの実現が容易になる。
【００６４】
なお、本実施の形態では、２分検索木を平衡木となるようにして実施の形態１と同様のピア検索処理を行う場合について説明したが、２分検索木を平衡木となるようにして実施の形態２のピア検索処理を行うようにしてもよい。この場合も、比較処理の部分は実施の形態１と同様であるため、処理時間は一定となり、パイプライン化による高速処理が容易に実現できる。
【００６５】
このように、本実施の形態では、２分検索木の構成ノード数が最大ノード数となるように、不足するノードについては最大ハッシュに対応するノードを追加して２分検索木を生成し、実施の形態１と同様に２分検索木にしたがってピア検索処理を実施するようにした。このため、ピア検索処理の処理時間が一定となり、また、パイプライン化が容易になるため、実施の形態１よりさらに処理を高速化することができる。
【産業上の利用可能性】
【００６６】
以上のように、本発明にかかる通信装置およびピア検索方法は、コンテンツを分散管理するピアツーピアネットワークに有用であり、特に、広帯域のデータを行うネットワークや多種のコンテンツのサービスを実施するピアツーピアネットワークに適している。
【図面の簡単な説明】
【００６７】
【図１】本発明にかかる実施の形態１のネットワークシステムの一次元ハッシュ空間におけるピアの配置例を示す図である。
【図２−１】コンテンツ要求元のピアが管理するＤＨＴの一例を示す図である。
【図２−２】コンテンツ要求元のピアの２分検索木の一例を示す図である。
【図３】実施の形態１のピア検索処理手順の一例を示すフローチャートである。
【図４−１】ｈ＝３１の場合の実施の形態１のピア検索処理の概念を示す図である。
【図４−２】ｈ＝２の場合の実施の形態１のピア検索処理の概念を示す図である。
【図５】実施の形態２のピア検索処理手順の一例を示すフローチャートである。
【図６−１】ｈ＝３１の場合の実施の形態２のピア検索処理の概念を示す図である。
【図６−２】ｈ＝２の場合の実施の形態２のピア検索処理の概念を示す図である。
【図７】実施の形態３のネットワークシステムの一次元ハッシュ空間におけるピアの配置例を示す図である。
【図８】実施の形態３の送信元のピアのＦｉｎｇｅｒテーブルの一例を示す図である。
【図９−１】実施の形態３の二分検索木の一例を示す図である。
【図９−２】実施の形態３の二分検索木の一例を示す図である。
【図１０−１】実施の形態３のピア検索処理を用いた場合の並列処理タイミングの一例を示す図である。
【図１０−２】従来のピア検索処理を用いた場合の並列処理タイミングの一例を示す図である。
【図１１】本実施の形態のピア検索処理をハードウエアで実現する検索処理装置の機能構成例を示す図である。
【図１２】パイプライン化した場合の処理の一例を示す図である。
【符号の説明】
【００６８】
１，１ａ  一次元ハッシュ空間
２  ピア
３  Ｆｉｎｇｅｒピア
４  比較回路
５  メモリ
６  メモリバス
【図１】
2009134341.tif 000003
【図２−１】
2009134341.tif 000004
【図２−２】
2009134341.tif 000005
【図３】
2009134341.tif 000006
【図４−１】
2009134341.tif 000007
【図４−２】
2009134341.tif 000008
【図５】
2009134341.tif 000009
【図６−１】
2009134341.tif 000010
【図６−２】
2009134341.tif 000011
【図７】
2009134341.tif 000012
【図８】
2009134341.tif 000013
【図９−１】
2009134341.tif 000014
【図９−２】
2009134341.tif 000015
【図１０−１】
2009134341.tif 000016
【図１０−２】
2009134341.tif 000017
【図１１】
2009134341.tif 000018
【図１２】
2009134341.tif 000019