(57)【要約】【課題】オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間を即時に判定することができる遅延時間推定方法等を提供する。【解決手段】ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルを有する。そして、各ピアノードが、ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する第１のステップと、複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する第２のステップと、送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定する第３のステップと、送信元ピアノードから宛先ピアノードへの遅延時間を、平均遅延時間と、ホップ数との乗算によって導出する第４のステップとを有する。【選択図】図４
2010103786.tif 000002
【特許請求の範囲】
【請求項１】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延時間推定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルを有し、
各ピアノードが、前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する第１のステップと、
各ピアノードが、複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する第２のステップと、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定する第３のステップと、
送信元ピアノードから宛先ピアノードへの遅延時間を、前記平均遅延時間と、前記ホップ数との乗算によって導出する第４のステップと
を有することを特徴とする遅延時間推定方法。
【請求項２】
第３のステップについて、
前記オーバレイネットワークでは、送信元ピアノードの第１の識別値から、２ｋ（ｋは１以上の整数）毎の識別値を有するピアノードへ、１ホップで通信可能であって、
送信元ピアノードの第１の識別値と、宛先ピアノードの第２の識別値との差である距離値を算出し、
ｋを所定最大ホップ乗数から１減分しつつ、前記距離値から２ｋが減算できるか否かを判定し、減算できる場合に前記距離値から２ｋを減算し、減算された前記距離値が１ピアノードの管理する識別値空間である平均識別値空間より小さくなるまで繰り返し、
２ｋを減算することができた数に１を加えた値を、前記ホップ数として推定する
ことを特徴とする請求項１に記載の遅延時間推定方法。
【請求項３】
前記平均遅延時間及び前記平均識別値空間を、ピアノード間で相互に交換し、
自ピアノードにおける平均遅延時間及び平均識別値空間と、他ピアノードにおける平均遅延時間及び平均識別値空間とを用いて、自ピアノードにおける平均遅延時間及び平均識別値空間を算出することを特徴とする請求項２に記載の遅延時間推定方法。
【請求項４】
第１のステップについて、前記ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、該ＲＴＴ値から遅延時間を算出することを特徴とする請求項１から３のいずれか１項に記載の遅延時間推定方法。
【請求項５】
ファイルサーバが接続された複数のファイルサーバピアノードが、前記オーバレイネットワークに接続されており、
第１の端末が接続された第１のピアノードが、複数のファイルサーバピアノードへ、データを保存するデータ保存ステップと、
第２の端末が接続された第２のピアノードが、前記複数のファイルサーバピアノードの中で、第１のステップから第４のステップによって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードから前記データを取得するデータ取得ステップと
を有することを特徴とする請求項１から４のいずれか１項に記載の遅延時間推定方法。
【請求項６】
前記データ保存ステップについて、第１の端末は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出し、各ハッシュ値を識別値とする前記ファイルサーバピアノードへ前記データを保存し、
前記データ取得ステップについて、第２の端末は、前記ファイル名及び複製番号に基づいて前記複数のハッシュ値を導出し、各ハッシュ値を第２の識別値として前記遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードから前記データを取得する
ことを特徴とする請求項５に記載の遅延時間推定方法。
【請求項７】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する平均遅延時間算出手段と、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定するホップ数推定手段と、
送信元ピアノードから宛先ピアノードへの遅延時間を、前記平均遅延時間と、前記ホップ数との乗算によって導出する遅延時間導出手段と
を有することを特徴とするピアノード。
【請求項８】
ファイルサーバが接続された複数のファイルサーバピアノードが、前記オーバレイネットワークに接続されており、
複数のファイルサーバピアノードへ、データを保存するデータ保存手段と、
前記複数のファイルサーバピアノードの中で、前記遅延時間導出手段によって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードから前記データを取得するデータ取得手段と
を有することを特徴とする請求項７のいずれか１項に記載のピアノード。
【請求項９】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルを有し、
前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する平均遅延時間算出手段と、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定するホップ数推定手段と、
送信元ピアノードから宛先ピアノードへの遅延時間を、前記平均遅延時間と、前記ホップ数との乗算によって導出する遅延時間導出手段と
してコンピュータを機能させることを特徴とするピアノード用のプログラム。
【請求項１０】
ファイルサーバが接続された複数のファイルサーバピアノードが、前記オーバレイネットワークに接続されており、
複数のファイルサーバピアノードへ、データを保存するデータ保存手段と、
前記複数のファイルサーバピアノードの中で、前記遅延時間導出手段によって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードから前記データを取得するデータ取得手段と
してコンピュータを更に機能させることを特徴とする請求項９に記載のピアノード用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーバレイネットワークにおける遅延時間推定方法、ピアノード及びプログラムに関する。
【背景技術】
【０００２】
図１は、オーバレイネットワークのシステム構成図である。
【０００３】
図１のシステムによれば、複数のピアノード１、第１の端末２及び第２の端末３が物理ネットワーク４に接続されている。その物理ネットワーク４上には、複数のピアノード１によって仮想的にオーバレイネットワーク５が構成されている。オーバレイネットワークの代表的な例として、Ｐ２Ｐ(Peer to Peer)ネットワークがある。Ｐ２Ｐネットワークは、ＩＰ層を覆い隠して（オーバレイして）、端末間の相互接続を可能とする。図１によれば、第１の端末２及び第２の端末３が、ピアノード１に対するＳＩＰ−ＵＡ(SIP - User Agent)として機能し、オーバレイネットワークが、例えばＰ２ＰＳＩＰ(Peer to Peer - Session Initiation Protocol)によって構築されている。
【０００４】
また、図１のシステムによれば、ピアノード１は、ファイルサーバ（又はレプリカ（複製）サーバ）であって、第１の端末（データ保存元端末）から送信されたデータを、分散的且つ複製的に蓄積する。これに対し、第２の端末（データ取得元端末）は、第１の端末によって蓄積されたファイルサーバピアノードから、データを取得する。
【０００５】
近年、構造化オーバレイの代表例として、キーワードのハッシュ値に基づいて端末間のデータを分散管理する「分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）」の技術がある（例えば非特許文献１参照）。Napster又はGunutellaに代表される従来のＰ２Ｐ技術と異なって、「分散ハッシュテーブル」は、ネットワーク全体に分散配置されたデータを高速に検索することができる。また、ピアノードの頻繁な参加・離脱に対しても、自律分散的にネットワークを再構築することができる。
【０００６】
また、ＩＥＴＦ(Internet Engineering Task Force)によれば、ＳＩＰのシグナリング制御に、Ｐ２Ｐ(Peer-to-Peer)と称される自律分散ネットワークアーキテクチャ技術を融合させた「Ｐ２ＰＳＩＰ」技術を開示している（例えば非特許文献３参照）。Ｐ２ＰＳＩＰによれば、ＳＩＰによるセッション制御機能を、ピアノードに搭載することによって、サーバレスのシステムを実現する。Ｐ２Ｐを用いることにより、ピアノード間で情報の分散管理及び分散制御を実行するために、加入者数の増加に対してもサーバシステムの増強が不要となる。
【０００７】
更に、オーバレイネットワーク構築時やデータ検索時に必要となるメッセージングを規定した技術がある（例えば非特許文献２参照）。具体的には、ＲＥＬＯＡＤ(REsource LOcation And Discovery)について規定する。
【０００８】
更に、オーバレイネットワーク内で診断を実行する技術もある（例えば非特許文献３参照）。この技術によれば、診断を実行する第１の端末が、宛先ＩＤ(IDentifier)（識別値）に向けてEcho要求メッセージを送信し、当該ＩＤを管理する第２の端末までの中継端末数及び遅延時間を測定する。Echoメッセージにタイムスタンプ情報を付加することで、第１の端末と第２の端末間での片方向／往復遅延の測定をすることができる。また、第２の端末でのプログラムの稼働時間(Uptime)及び空きディスク容量の情報も取得することができる。更に、第２の端末のみがEcho応答メッセージを送信するPingモードに加えて、Echo要求メッセージを中継した全ピアノードが、第１の端末に対してEcho応答メッセージを送信するTracerouteモードも規定されている。このモードを用いることによって、ネットワーク内のループの検出やボトルネック箇所を特定し、且つ、Malicious端末を検出することができる。
【０００９】
【非特許文献１】Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, and Hari Balakrishnan、”Chord: A Scalable Peer-to-peer LookupService for Internet Applications”、Proc. ACM SIGCOMM'01、San Diego, Sept. 2001、[online]、［平成２０年１０月２４日検索］、インターネット＜ＵＲＬ：http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf＞
【非特許文献２】IETF Internet Draft: “REsource LOcation AndDiscovery (RELOAD)”、draft-ietf-p2psip-reload-00.txt、[online]、［平成２０年１０月２４日検索］、インターネット＜ＵＲＬ：http://www.ietf.org/internet-drafts/draft-ietf-p2psip-reload-00.txt＞
【非特許文献３】IETF Internet Draft: “Diagnose P2PSIPOverlay Network Failures”, draft-zheng-p2psip-diagnose-02、[online]、［平成２０年１０月２４日検索］、インターネット＜ＵＲＬ：http://tools.ietf.org/id/draft-zheng-p2psip-diagnose-02.txt＞
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、オーバレイネットワークによれば、ピアノード数が膨大となった場合、宛先ピアノードまでの中継ピアノード数も膨大となる。特に、リアルタイム性を要するセッション制御については、セッション確立時間が増大するという問題があった。例えば、ピアノード数を１０００万台とし、ピアノード間での遅延時間を５０ｍ秒と仮定した場合、セッション確立時間は最大４.６秒になると試算される。
【００１１】
非特許文献１及び２に記載された技術によれば、オーバレイネットワーク上での遅延時間を判定する技術については何ら開示していない。また、非特許文献３に記載された技術によれば、遅延時間の測定は、オーバレイネットワーク上にEchoメッセージを送信する必要があり、宛先ＩＤが与えられた時点で、遅延時間を即時に判定することはできない。
【００１２】
また、前述した図１のシステムによれば、データ保存元となる第１の端末から送信されたデータを、オーバレイネットワークを介して複数のファイルサーバピアノードによって分散的且つ複製的に蓄積する。データ取得元となる第２の端末は、いずれか１つのファイルサーバサーバピアノードからデータを取得する。このとき、第２の端末と、データ取得の対象となるファイルサーバピアノードとの間の遅延時間までは、全く考慮されていない。
【００１３】
そこで、本発明は、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間を即時に推定することができる遅延時間推定方法、ピアノード及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延時間推定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルを有し、
各ピアノードが、ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する第１のステップと、
各ピアノードが、複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する第２のステップと、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定する第３のステップと、
送信元ピアノードから宛先ピアノードへの遅延時間を、平均遅延時間と、ホップ数との乗算によって導出する第４のステップと
を有することを特徴とする。
【００１５】
本発明の遅延時間推定方法における他の実施形態によれば、第３のステップについて、
オーバレイネットワークでは、送信元ピアノードの第１の識別値から、２ｋ（ｋは１以上の整数）毎の識別値を有するピアノードへ、１ホップで通信可能であって、
送信元ピアノードの第１の識別値と、宛先ピアノードの第２の識別値との差である距離値を算出し、
ｋを所定最大ホップ乗数から１減分しつつ、距離値から２ｋが減算できるか否かを判定し、減算できる場合に距離値から２ｋを減算し、減算された距離値が１ピアノードの管理する識別値空間である平均識別値空間より小さくなるまで繰り返し、
２ｋを減算することができた数に１を加えた値を、ホップ数として推定する
ことも好ましい。
【００１６】
本発明の遅延時間推定方法における他の実施形態によれば、
平均遅延時間及び平均識別値空間を、ピアノード間で相互に交換し、
自ピアノードにおける平均遅延時間及び平均識別値空間と、他ピアノードにおける平均遅延時間及び平均識別値空間とを用いて、自ピアノードにおける平均遅延時間及び平均識別値空間を算出することも好ましい。
【００１７】
本発明の遅延時間推定方法における他の実施形態によれば、第１のステップについて、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、該ＲＴＴ値から遅延時間を算出することも好ましい。
【００１８】
本発明の遅延時間推定方法における他の実施形態によれば、
ファイルサーバが接続された複数のファイルサーバピアノードが、オーバレイネットワークに接続されており、
第１の端末が接続された第１のピアノードが、複数のファイルサーバピアノードへ、データを保存するデータ保存ステップと、
第２の端末が接続された第２のピアノードが、複数のファイルサーバピアノードの中で、第１のステップから第４のステップによって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードからデータを取得するデータ取得ステップとを有することも好ましい。
【００１９】
本発明の遅延時間推定方法における他の実施形態によれば、
データ保存ステップについて、第１の端末は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出し、各ハッシュ値を識別値とするファイルサーバピアノードへデータを保存し、
データ取得ステップについて、第２の端末は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出し、各ハッシュ値を第２の識別値として遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードからデータを取得することも好ましい。
【００２０】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する平均遅延時間算出手段と、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定するホップ数推定手段と、
送信元ピアノードから宛先ピアノードへの遅延時間を、平均遅延時間と、ホップ数との乗算によって導出する遅延時間導出手段と
を有することを特徴とする。
【００２１】
本発明のピアノードにおける他の実施形態によれば、
ファイルサーバが接続された複数のファイルサーバピアノードが、オーバレイネットワークに接続されており、
複数のファイルサーバピアノードへ、データを保存するデータ保存手段と、
複数のファイルサーバピアノードの中で、遅延時間導出手段によって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードからデータを取得するデータ取得手段と
を有することも好ましい。
【００２２】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルを有し、
ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する平均遅延時間算出手段と、
送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定するホップ数推定手段と、
送信元ピアノードから宛先ピアノードへの遅延時間を、平均遅延時間と、ホップ数との乗算によって導出する遅延時間導出手段と
してコンピュータを機能させることを特徴とするピアノード用のプログラム。
【００２３】
本発明のピアノード用のプログラムにおける他の実施形態によれば、
ファイルサーバが接続された複数のファイルサーバピアノードが、オーバレイネットワークに接続されており、
複数のファイルサーバピアノードへ、データを保存するデータ保存手段と、
複数のファイルサーバピアノードの中で、遅延時間導出手段によって導出された遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードからデータを取得するデータ取得手段と
してコンピュータを更に機能させることも好ましい。
【発明の効果】
【００２４】
本発明の遅延時間推定方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間を即時に推定することができる。
【発明を実施するための最良の形態】
【００２５】
以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。
【００２６】
図２は、本発明で用いる構造化オーバレイの説明図である。
【００２７】
分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた代表的な構造化オーバレイの技術として、Ｃｈｏｒｄがある。Ｃｈｏｒｄは、時計回りに識別値が増加していく、リング状（環状）ハッシュ空間を考える。識別値は、ＳＨＡ１ハッシュ関数の値である。各ピアノードは、例えばＩＰアドレス及びポート番号を連結した値を入力としてハッシュ関数から得られた値を、ノード識別値として決定する。分散ハッシュテーブルの特徴の１つに、拡張性（スケーラビティ）がある。データ検索時に中継するピアノード数は、ピアノード総数のログオーダに抑えられるため、ピアノード数が増加した場合であっても効率的な検索が可能となる。
【００２８】
図２によれば、オーバレイネットワークを構成するピアノードが、リング状ハッシュ空間に配置されている。端末は、いずれか１つのピアノードに接続される。また、例えばレプリカサーバのようなファイルサーバピアノードも、リング状ハッシュ空間に配置されている。図２によれば、データ取得元となる第２の端末は、ピアノードＮ８に接続しており、ファイルサーバピアノードは、Ｎ１５、Ｎ３９、Ｎ５４及びＮ１である。
【００２９】
更に、第２の端末は、例えばファイル名及び複製番号を入力としてハッシュ関数から得られた値を、宛先識別値として決定する。このとき、図２によれば、宛先識別値は、例えばＮ５４とする。
【００３０】
ここで、「サクセッサリスト」及び「フィンガーテーブル」が用いられる。「サクセッサリスト」とは、ハッシュ空間上で隣接する複数のピアノードの情報を保持する。従って、当該ピアノードの識別値ｋを与えたとき、時計回りに辿って、最初に存在するピアノードを得られる。
【００３１】
「フィンガーテーブル」には、ルーティングテーブルが保持される。フィンガーテーブルは、当該ピアノードの識別値（例えばＮ８）に、２のｋ乗（１，２，４，８，１６・・・）を加算した数ｘと、その数ｘを入力としたサクセッサ（ｘ）のピアノードの識別値とを記憶する。また、各ピアノードは、定期的にフィンガーテーブルに登録された他の複数のピアノードへ、Keep-Aliveメッセージを送信することによって、ＲＴＴを測定している。フィンガーテーブルは、複数のピアノードとの間の遅延時間の平均値を平均遅延時間として記憶する。
【００３２】
図２は、６ビットのハッシュ識別値空間の例であり、フィンガーテーブルの行数は６個となる（例えば、１６０ビットのハッシュ識別値空間の場合、フィンガーテーブルの行数は１６０個）。Ｎ５４をルックアップする場合について説明する。
【００３３】
（ホップ１）Ｎ８は、Ｎ５４をルックアップするに当たり、フィンガーテーブルを参照し、Ｎ５４から反時計回りに最も近い、８＋２６（３２）＝４０、即ち、ピアノードが存在するＮ４２を検索する。そして、Ｎ８は、ルックアップメッセージをＮ４２へ転送する。
（ホップ２）Ｎ４２は、Ｎ５４をルックアップするに当たり、フィンガーテーブルを参照して、Ｎ５４から反時計回りに最も近い数、４２＋２４（８）＝５０、即ち、ピアノードが存在するＮ５１を検索する。そして、Ｎ４２は、ルックアップメッセージをＮ５１へ転送する。
（ホップ３）Ｎ５１は、Ｎ５４をルックアップするに当たり、フィンガーテーブルを参照し、Ｎ５１から反時計回りに最も近い、５１＋２１（２）＝５３、即ち、ピアノードが存在するＮ５４を検索する。そして、Ｎ５１は、ルックアップメッセージをＮ５４へ転送する。これによって、Ｎ８に接続された第２の端末は、Ｎ５４のファイルサーバピアノードのデータを取得することができる。
【００３４】
図３は、本発明におけるデータ保存ステップの説明図である。
【００３５】
第１の端末は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出する。図３によれば、例えば以下のようなハッシュ値が導出される。
h(FileName, Replica1)＝Ｎ５４
h(FileName, Replica2)＝Ｎ１４
h(FileName, Replica3)＝Ｎ３９
h(FileName, Replica4)＝Ｎ１
ハッシュ関数hは、全てのピアノードで予め共有される。そして、第１の端末は、各ハッシュ値を識別値とするファイルサーバピアノードＮ５４、Ｎ１４、Ｎ３９及びＮ１へデータを保存する。
【００３６】
図４は、本発明におけるデータ取得ステップの説明図である。
【００３７】
第２の端末も、ファイル名及び複製番号に基づいて複数のハッシュ値を導出する。第１の端末と同様に、以下のようなハッシュ値が導出される。
h(FileName, Replica1)＝Ｎ５４
h(FileName, Replica2)＝Ｎ１４
h(FileName, Replica3)＝Ｎ３９
h(FileName, Replica4)＝Ｎ１
【００３８】
図４によれば、例えばＮ５４をルックアップする場合におけるホップ数を推定する。
（ホップ１）Ｎ８のフィンガーテーブルによれば、Ｎ５４から反時計回りに最も近い数は８＋２６（３２）の４０である。ここで、ピアノードＮ４０が存在すると仮定する。
（ホップ２）Ｎ４０のフィンガーテーブルによれば、Ｎ５４から反時計回りに最も近い数は４０＋２３（８）＝４８である。ここで、ピアノードＮ４８が存在すると仮定する。
（ホップ３）Ｎ４８のフィンガーテーブルによれば、Ｎ５４から反時計回りに最も近い数は４８＋２２（４）＝５２である。ここで、ピアノードＮ５２が存在すると仮定する。例えば、１つのピアノードが管理する平均識別値空間が３であるとする。そうすると、ピアノードＮ５２とピアノードＮ５４との差は、２であるので、ホップ数の計数を終了する。従って、ホップ数４と推定される。尚、平均識別値空間とは、自ピアノードが管理する識別値空間、あるいはサクセッサリストに含まれるリング状ハッシュ空間を、サクセッサ数で除算した１ピアノードが管理する識別値空間を意味する。
【００３９】
平均遅延時間及び平均識別値空間を、ピアノード間で相互に交換されてもよい。これによって、自ピアノードにおける平均遅延時間及び平均識別値空間と、他ピアノードにおける平均遅延時間及び平均識別値空間とを、例えば平均することによって、自ピアノードにおける平均遅延時間及び平均識別値空間を算出することができる。単一のピアノードにおける平均遅延時間及び平均識別値空間では、オーバレイネットワーク全体から見て誤差を生じる場合があるからである。
【００４０】
図５は、ホップ数を推定するプログラムである。
【００４１】
Ｃｈｏｒｄのオーバレイネットワークでは、送信元ピアノードのアドレスから導出される第１の識別値から、２ｋ（ｋは１以上の整数）毎の識別値を有するピアノードへ、１ホップで通信可能である。
interval：サクセッサリストに含まれるリング状ハッシュ空間を、サクセッサ数で除算した平均識別値空間（１ピアノードが管理する識別値空間）
distance：送信元ピアノードのアドレスから導出される第１の識別値と、宛先ピアノードのアドレスから導出される第２の識別値との差である距離値
hop：推定されたホップ数（初期値１）
bit_num：最大ホップ乗数（リング状ハッシュ空間を表すビット数）
【００４２】
距離値distanceが平均識別値空間よりも大きい場合に、以下のステップが繰り返される。
（１）ｋを所定最大ホップ乗数から１減分する。
（２）距離値distanceから２ｋが減算できるか否か、即ち、距離値distanceが２ｋよりも大きいか否かを判定する。
減算できる場合に、ホップ数を増分する。
距離値から２ｋを減算する。
（３）距離値distanceが平均識別値空間よりも小さくなった場合、処理を終了する。
【００４３】
次に、第２の端末は、全ての宛先識別値についてホップ数を推定した後、遅延時間を算出する。遅延時間は、ＲＴＴ値に基づく平均遅延時間と、ホップ数との乗算によって導出する。例えば、平均遅延時間が１００ｍｓで且つホップ数４である場合、遅延時間は、１００ｍｓ×４＝４００ｍｓとなる。
【００４４】
最後に、第２の端末は、遅延時間が最も小さいファイルサーバピアノードを選択する。例えば、図４によれば、Ｎ５４の遅延時間が最も小さいと推定されたとする。この場合、第２の端末は、ファイルサーバピアノードＮ５４からデータを取得する。
【００４５】
図６は、図３に対応して、図５のプログラムの各ステップを説明したプログラムステップである。尚、各ステップは、前述した図３と同じである。
【００４６】
図７は、本発明におけるシーケンス図である。
【００４７】
図７のシーケンスは、データ保存ステップ（Ｓ７０１〜Ｓ７０３）と、隣接ピアノードに対する平均遅延時間算出ステップ（Ｓ７１１〜Ｓ７１２）と、データ取得ステップ（Ｓ７２１〜Ｓ７２７）とを有する。
【００４８】
［データ保存ステップ］
（Ｓ７０１）データ保存元となる第１の端末２が、ピアノードＮ５８へデータ保存要求を送信する。
（Ｓ７０２）ピアノードＮ５８は、ファイル名及び複製番号に基づいてハッシュ関数から複数のハッシュ値を導出する。図７によれば、例えばＮ５４、Ｎ３９、Ｎ１４及びＮ１が導出されたとする。
（Ｓ７０３）ピアノードＮ５８は、導出されたハッシュ値を宛先識別値として、保存すべきデータを含むデータ保存要求を送信する。図７によれば、データ保存要求は、ファイルサーバピアノードＮ５４、Ｎ３９、Ｎ１４及びＮ１へ送信される。これによって、第１の端末２から送信された保存すべきデータは、ファイルサーバピアノードＮ５４、Ｎ３９、Ｎ１４及びＮ１によって分散的且つ複製的に保存される。
【００４９】
［平均遅延時間算出ステップ］
（Ｓ７１１）各ピアノードが、ルーティングテーブル（フィンガーテーブル）に登録された複数の次ピアノードへ、Keep-Aliveメッセージを定期的に送信し、その応答メッセージを受信する。Ｃｈｏｒｄによれば、フィンガーテーブルには、自ピアノードＩＤに２ｍ（m=159, 158, … 0）を加算した値を、次ピアノードとして登録している。これによって、各ピアノードは、次ピアノードとの間の遅延時間ＲＴＴ(Round Trip Time)を計測する。遅延時間は、そのルーティングテーブルに記憶される。図７によれば、ピアノードＮ８は、フィンガーテーブルに登録されているＮ１４、Ｎ２１、Ｎ３２及びＮ４２各々へ、Keep-Aliveメッセージを送信し、それらの応答を受信する。
（Ｓ７１２）ピアノードＮ８は、ピアノードＮ１４、Ｎ２１、Ｎ３２及びＮ４２の遅延時間の総和を４で除算することによって、次ピアノードに対する平均遅延時間を算出する。
【００５０】
［データ取得ステップ］
（Ｓ７２１）データ取得元となる第２の端末が、ピアノードＮ８へ、データ取得要求を送信する。
（Ｓ７２２）ピアノードＮ８は、ファイル名及び複製番号に基づいてハッシュ関数から複数のハッシュ値を導出する。図７によれば、ピアノードＮ５８におけるＳ７０２と同様に、例えばＮ５４、Ｎ３９、Ｎ１４及びＮ１が導出される。
（Ｓ７２３）ピアノードＮ８は、導出されたハッシュ値を宛先識別値として、Ｎ５４、Ｎ３９、Ｎ１４及びＮ１各々までのホップ数を推定する。ホップ数の推定については、図３〜図５で説明したとおりである。
（Ｓ７２４）ピアノードＮ８は、Ｎ５４、Ｎ３９、Ｎ１４及びＮ１各々について、平均遅延時間とホップ数との乗算によって遅延時間を導出する。
（Ｓ７２５）遅延時間が最も小さいピアノードが選択される。図７によれば、例えばＮ５４が選択されている。
（Ｓ７２６）ピアノードＮ８は、Ｎ４２及びＮ５１を介してファイルサーバピアノードＮ５４へ、データ取得要求を送信する。
（Ｓ７２７）これに対し、ファイルサーバピアノードＮ５４は、そのデータを、Ｎ４２及びＮ５１を介してピアノードＮ８へ送信する。ピアノードＮ８は、そのデータを、第２の端末へ送信する。これによって、第１の端末２から送信された保存すべきデータは、第２の端末３によって取得される。
【００５１】
図８は、本発明におけるピアノードの機能構成図である。
【００５２】
図８によれば、データ記憶部１００を有するファイルサーバピアノード１は、ルーティングテーブル１０１と、遅延時間計測部１０２と、平均遅延時間算出部１０３と、ホップ数推定部１０４と、遅延時間導出部１０５と、データ保存部１０６と、データ取得部１０７とを有する。これら機能構成部は、ピアノードに搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００５３】
ルーティングテーブル１０１は、１ホップで通信可能な識別値を有する次ピアノードを登録する。Ｃｈｏｒｄの場合におけるフィンガーテーブルである。オーバレイネットワークでは、送信元ピアノードの第１の識別値から、２ｋ（ｋは１以上の整数）毎の識別値を有するピアノードへ、１ホップで通信可能である。
【００５４】
遅延時間計測部１０２は、ルーティングテーブル１０１に登録された次ピアノード毎に遅延時間を計測する。遅延時間計測部１０２は、ルーティングテーブル１０１に登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、該ＲＴＴ値から遅延時間を算出する。
【００５５】
平均遅延時間算出部１０３は、複数の次ピアノードとの間の複数の遅延時間の平均遅延時間を算出する。尚、平均遅延時間及び平均識別値空間を、ピアノード間で相互に交換してもよい。自ピアノードにおける平均遅延時間及び平均識別値空間と、他ピアノードにおける平均遅延時間及び平均識別値空間とを、例えば平均することによって、自ピアノードにおける平均遅延時間及び平均識別値空間を算出する。
【００５６】
ホップ数推定部１０４は、送信元ピアノードからオーバレイネットワークを介して宛先ピアノードまでのホップ数を推定する。ホップ数推定部１０４は、送信元ピアノードの第１の識別値と、宛先ピアノードの第２の識別値との差である距離値を算出する。そして、ｋを所定最大ホップ乗数から１減分しつつ、距離値から２ｋが減算できるか否かを判定し、減算できる場合に距離値から２ｋを減算し、減算された距離値が１ピアノードの管理する平均識別値空間より小さくなるまで繰り返す。最終的に、２ｋを減算することができた数に１を加えた値を、ホップ数として推定する。
【００５７】
遅延時間導出部１０５は、送信元ピアノードから宛先ピアノードへの遅延時間を、平均遅延時間と、ホップ数との乗算によって導出する。
【００５８】
データ保存部１０６は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出し、各ハッシュ値を宛先識別値とするファイルサーバピアノードへデータを保存する。
【００５９】
データ取得部１０７は、ファイル名及び複製番号に基づいて複数のハッシュ値を導出し、各ハッシュ値を宛先識別値として遅延時間が最も小さいファイルサーバピアノードを選択し、該ファイルサーバピアノードからデータを取得する。
【００６０】
以上、詳細に説明したように、本発明の遅延時間推定方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間を即時に推定することができる。
【００６１】
遅延時間を即時に判定することによって、様々な用途に適用することができる。例えば、複数のレプリカサーバによってオーバレイネットワークが構成されている場合、互いに共有するハッシュ関数を用いて、保存すべきデータを、複数のファイルサーバピアノードに分散的且つ複製的に保存することができる。また、本発明を用いることによって、データ取得元のピアノードは、遅延時間が最も小さいと推定されたファイルサーバピアノードから、データを取得することができる。
【００６２】
また、例えば、事業者システムであるＩＭＳ(IP Multimedia Subsystem)／ＭＭＤ(Multimedia Domain)と、ピアノードで構築したオーバレイネットワークとを連携されることによって、高品質なセッション制御を低コストで実現することができる。ＩＭＳシステム及びオーバレイネットワークの双方に接続したピアノードは、セッション確立時に、オーバレイネットワークを優先的に使用することによって、ＩＭＳシステムへの負荷を削減することができる。しかしながら、ピアノード数が膨大となる場合には、データ検索時の中継ピアノード数も無視できなくなる。特にリアルタイム性を求められるセッション制御では、セッション確立時間が増大するという問題があった。そのため、本発明によって、送信元ピアノードが、オーバレイネットワーク上でのセッション確立処理に要する遅延時間を推定する。その遅延時間が規定時間を超える場合に、ＩＭＳシステムを介したセッションを確立する。これによって、システムとしてのセッション確立時間を保証することが可能となる。
【００６３】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００６４】
【図１】オーバレイネットワークのシステム構成図である。
【図２】Ｃｈｏｒｄを用いた構造化オーバレイの説明図である。
【図３】本発明におけるデータ保存ステップの説明図である。
【図４】本発明におけるデータ取得ステップの説明図である。
【図５】ホップ数を推定するプログラムである。
【図６】図３に対応して、図５のプログラムの各ステップを説明したプログラムステップである。
【図７】本発明におけるシーケンス図である。
【図８】本発明におけるピアノードの機能構成図である。
【符号の説明】
【００６５】
１  ピアノード
１０１  ルーティングテーブル
１０２  遅延時間計測部
１０３  平均遅延時間算出部
１０４  ホップ数推定部
１０５  遅延時間導出部
１０６  データ保存部
１０７  データ取得部
２  第１の端末
３  第２の端末
４  物理ネットワーク
５  オーバレイネットワーク
【図１】
2010103786.tif 000003
【図２】
2010103786.tif 000004
【図３】
2010103786.tif 000005
【図４】
2010103786.tif 000006
【図５】
2010103786.tif 000007
【図６】
2010103786.tif 000008
【図７】
2010103786.tif 000009
【図８】
2010103786.tif 000010