(57)【要約】  最短経路探索部１０５は、距離メトリック格納部１０２に格納されているランドマークノード間の距離メトリックの測定値に基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、探索した最短経路に沿った距離メトリックを算出する。座標生成部１０１ａは、最短経路探索部１０５で算出された最短経路に沿った距離メトリックから予め定められた次元数の座標軸を生成する。座標算出部１０４ａは、座標算出対象ノードと各ランドマークノードとの間の距離メトリックと、座標軸生成部１０１ａで生成された座標軸とから座標算出対象ノードの座標を算出する。距離メトリック推定部１３４は、座標算出部１０４ａで座標が算出された２つの座標算出対象ノード間の距離メトリックを、上記算出された座標を用いて推定する。
2010035565.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部と、
該距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段と、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段と、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段と、
該座標算出手段で座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する距離メトリック推定手段とを備える距離メトリック推定システム。
【請求項２】
請求項１に記載の距離メトリック推定システムにおいて、
前記最短経路探索手段は、前記座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックとを用いて、前記座標算出対象ノードから前記各ランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第２の距離メトリックを算出し、
前記座標算出手段は、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックの代わりに、前記最短経路探索手段で算出された最短経路に沿った第２の距離メトリックを用いる距離メトリック推定システム。
【請求項３】
請求項１または請求項２に記載の距離メトリック推定システムにおいて、
前記座標軸生成手段は、前記座標軸を生成する際、次元圧縮を行う距離メトリック推定システム。
【請求項４】
請求項１乃至３の何れか１項に記載の距離メトリック推定システムにおいて、
所定の条件を満たす座標算出対象ノードと特定の座標算出対象ノードとの間の距離メトリックを前記距離メトリック推定手段を用いて推定し、該推定した距離メトリックに基づいて前記所定の条件を満たす座標算出対象ノードの中から前記特定の座標算出対象ノードとの間の距離メトリックが最小となる座標算出対象ノードを選択する最近傍決定手段を備える距離メトリック推定システム。
【請求項５】
請求項４記載の距離メトリック推定システムにおいて、
コンテンツのコンテンツ識別子とそのコンテンツを所持している座標算出対象ノードのノード識別子とが関連付けて格納されたデータ所在格納部と、
該データ所在格納部にノード識別子が格納されている座標算出対象ノードの、前記座標算出手段で算出された座標が当該座標算出対象ノードのノード識別子と関連付けて格納された座標格納部とを備え、
前記ネットワークは、通信ネットワークであり、
前記距離メトリックは、遅延時間であり、
前記所定の条件を満たす座標算出対象ノードは、特定のコンテンツを所持している座標算出対象ノードであり、
前記最近傍決定手段は、前記特定の座標算出対象ノードの座標とコンテンツ識別子とが与えられることにより、前記データ所在格納部から検索した前記コンテンツ識別子のコンテンツを所持している座標算出対象ノードのノード識別子と前記特定の座標算出対象ノードの座標とを前記距離メトリック推定手段に渡して前記コンテンツを所持している座標算出対象ノードと前記特定の座標算出対象ノードとの間の遅延時間を推定させ、前記距離メトリック推定手段によって推定された、前記コンテンツを所持している座標算出対象ノードと前記特定の座標算出対象ノードとの間の遅延時間に基づいて、前記コンテンツを所持している座標算出対象ノードの中から前記特定の座標算出対象ノードとの間の遅延時間が最小になる座標算出対象ノードを選択し、
前記距離メトリック推定手段は、前記最近傍決定手段から渡されたノード識別子に関連付けて格納されている座標を前記座標格納部から検索し、該検索した座標と前記特定の座標算出対象ノードの座標とから、前記コンテンツ識別子のコンテンツを所持している座標算出対象ノードと前記特定の座標算出対象ノードとの遅延時間を推定する距離メトリック推定システム。
【請求項６】
請求項１乃至４の何れか１項に記載の距離メトリック推定システムにおいて、
前記ネットワークは、通信ネットワークであり、
前記距離メトリックは、遅延時間である距離メトリック推定システム。
【請求項７】
請求項１乃至４の何れか１項に記載の距離メトリック推定システムにおいて、
前記ネットワークは、通信ネットワークであり、
前記距離メトリックは、データの転送に要する費用である距離メトリック推定システム。
【請求項８】
請求項１乃至４の何れか１項に記載の距離メトリック推定システムにおいて、
前記ネットワークは、交通網であり、
前記距離メトリックは、移動に要する移動時間である距離メトリック推定システム。
【請求項９】
請求項１乃至４の何れか１項に記載の距離メトリック推定システムにおいて、
前記ネットワークは、交通網であり、
前記距離メトリックは、移動に要する費用である距離メトリック推定システム。
【請求項１０】
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部と、
該距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段と、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段と、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段とを備える座標算出ノード。
【請求項１１】
請求項１０に記載の座標算出ノードにおいて、
前記最短経路探索手段は、前記座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックとを用いて、前記座標算出対象ノードから前記各ランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第２の距離メトリックを算出し、
前記座標算出手段は、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックの代わりに、前記最短経路探索手段で算出された最短経路に沿った第２の距離メトリックを用いる座標算出ノード。
【請求項１２】
請求項１０または請求項１１に記載の座標算出ノードにおいて、
前記座標軸生成手段は、前記座標軸を生成する際、次元圧縮を行う座標算出ノード。
【請求項１３】
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部を設け、
最短経路探索手段が、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する第１のステップと、
座標軸生成手段が、前記第１のステップで算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する第２のステップと、
座標算出手段が、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記第２のステップで生成された座標軸とから前記座標算出対象ノードの座標を算出する第３のステップと、
距離メトリック推定手段が、前記第３のステップで座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する第４のステップとを含む距離メトリック推定方法。
【請求項１４】
請求項１３に記載の距離メトリック推定方法において、
前記第１のステップでは、前記座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックとを用いて、前記座標算出対象ノードから前記各ランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第２の距離メトリックを算出し、
前記第３のステップでは、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックの代わりに、前記第１のステップで算出された最短経路に沿った第２の距離メトリックを用いる距離メトリック推定方法。
【請求項１５】
請求項１３または請求項１４に記載の距離メトリック推定方法において、
前記第２のステップでは、前記座標軸を生成する際、次元圧縮を行う距離メトリック推定方法。
【請求項１６】
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部を備えたコンピュータを座標算出ノードとして機能させるためのプログラムであって
前記コンピュータを、
前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段、
該座標算出手段で座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する距離メトリック推定手段として機能させるためのプログラム。
【請求項１７】
請求項１６に記載のプログラムにおいて、
前記最短経路探索手段は、前記座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックとを用いて、前記座標算出対象ノードから前記各ランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第２の距離メトリックを算出し、
前記座標算出手段は、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックの代わりに、前記最短経路探索手段で算出された最短経路に沿った第２の距離メトリックを用いるプログラム。
【請求項１８】
請求項１６または請求項１７に記載のプログラムにおいて、
前記座標軸生成手段は、前記座標軸を生成する際、次元圧縮を行うプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークや交通網などのネットワークにおいて、任意の２ノード間の距離メトリックを推定する距離メトリック推定技術に関する。
【背景技術】
【０００２】
任意の２地点間の距離を求める場合、ＧＰＳ（グローバル・ポジショニング・システム）によって２地点の座標（緯度、経度）を測定し、測定した座標から数学的に２地点間の距離を求めるという方法をとることができる。ＧＰＳでは、複数の衛星から送られてくる電波を受信機で受信し、受信した電波の送信時刻と受信時刻との差分に基づいて受信機の座標を算出する。【０００３】
これと同様の考え方により、通信ネットワーク上の任意の２ノード間の距離メトリックを推定する距離メトリック推定システムが非特許文献１，２に記載されている。距離メトリックとは、２ノード間の距離を表す指標であり、非特許文献１，２では、遅延時間を距離メトリックとしている。【０００４】
図１を参照すると、非特許文献１，２に記載されている距離メトリック推定システムは、座標算出ノード１００と、ランドマークノード１１０，１２０と、座標算出対象ノード１３０，１４０とを含んでいる。図１では、説明を分かりやすくするため、ランドマークノードおよび座標算出対象ノードの台数をそれぞれ２台としたが、実際には、図２に示すように多数のランドマークノードおよび座標算出対象ノードが存在する。なお、図２では、ランドマークノードを●、座標算出ノードを△、座標算出対象ノードを○、中継ノードを□で表している。【０００５】
ランドマークノード１１０，１２０は、ＧＰＳシステムでいうと衛星の役割を果すものであり、それぞれ距離メトリック取得部１１１，１２１を備えている。距離メトリック取得部１１１，１２１は、それぞれ自ノードと他のランドマークノードとの間の距離メトリックを測定し、測定した距離メトリックと、その距離メトリックがどのノード間のものであるのかを示す情報（ノード間情報）とを含んだ距離メトリック情報を座標算出ノード１００へ送信する機能を有する。【０００６】
座標算出対象ノード１３０，１４０は、それぞれ、距離メトリック取得部１３１，１４１と、座標要求部１３２，１４２と、座標格納部１３３，１４３と、距離メトリック推定部１３４，１４４とを備えている。【０００７】
距離メトリック取得部１３１，１４１は、それぞれ自ノードとランドマークノード１１０，１２０との間の距離メトリックを測定し、測定した距離メトリックと、その距離メトリックがどのノード間のものであるのかを示すノード間情報とを含んだ距離メトリック情報を座標要求部１３２，１４２に渡す機能を有する。座標要求部１３２，１４２は、それぞれ距離メトリック取得部１３１，１４１から渡された距離メトリック情報を含んだ座標要求を座標算出ノード１００へ送信し、この座標要求に応答して座標算出ノード１００から返信された自ノードの座標を座標格納部１３３，１４３に格納する機能を有する。距離メトリック推定部１３４，１４４は、任意の２つの座標算出対象ノード内の座標格納部から座標を取得し、そのユークリッド距離を算出することにより、上記２つの座標算出ノード間の距離メトリックを推定する。【０００８】
座標算出ノード１００は、座標軸生成部１０１と、距離メトリック格納部１０２と、座標軸格納部１０３と、座標算出部１０４とを備えている。【０００９】
距離メトリック格納部１０２には、ランドマークノード１１０，１２０から送られてきたランドマークノード間の距離メトリック情報が格納される。座標軸生成部１０１は、距離メトリック格納部１０２に格納されている距離メトリック情報を予め定められた次元数に次元圧縮して座標軸を生成し、生成した座標軸を座標軸格納部１０３に格納する機能を有する。座標算出部１０４は、座標算出対象ノード１３０，１４０から送られてきた座標要求に含まれている距離メトリック情報と座標軸格納部１０３に格納されている座標軸とに基づいて座標算出対象ノード１３０，１４０の座標を算出し、算出した座標を要求元に返却する機能を有する。【００１０】
このような構成を有する非特許文献１，２に記載されている距離メトリック推定システムは、次のように動作する。【００１１】
先ず、ランドマークノード１１０，１２０内の距離メトリック取得部１１１，１２１が、それぞれ自ノードと他のランドマークノードとの間の距離メトリックを測定する。具体的には、距離メトリック取得部１１１，１２１は、他のランドマークノードに対してメッセージを送信し、このメッセージに対する応答を受信するまでのＲＴＴ（ラウンド・トリップ・タイム）を測定し、それを距離メトリックとする。その後、距離メトリック取得部１１１，１２１は、測定した距離メトリックと、その距離メトリックがどのノード間のものであるかを示すノード間情報とを含んだ距離メトリック情報を座標算出ノード１００へ送信する。この距離メトリック情報は、座標算出ノード１００内の距離メトリック格納部１０２に格納される。【００１２】
距離メトリック格納部１０２に対する距離メトリック情報の格納処理が完了すると、座標軸生成部１０１が、距離メトリック格納部１０２に格納されている距離メトリック情報に基づいて座標軸を生成する。【００１３】
この処理を図３のフローチャートを参照して説明すると、座標軸生成部１０１は、先ず、距離メトリック格納部１０２からランドマークノード間の距離メトリック情報を取得する（ステップ２４０１）。ここでは、全てのランドマークノード間のＲＴＴが取得される。その後、座標軸生成部１０１は、取得した距離メトリック情報を予め定められている次元数で線形次元圧縮することで座標軸を生成し、生成した座標軸を座標軸格納部１０３に格納する（ステップ４０２）。【００１４】
ここで、座標軸生成部１０１は、線形次元圧縮を主成分分析（ＰＣＡ：Principal  Component  Analysis）により行っている。主成分分析とは、多次元に分布するデータから、その分散を多くする軸を１または複数取得する処理であり、例えば、次式（１）に示す特異値分解（ＳＤＶ：Singular  Value  Decomposition）によって計算することができる。ここでは、全てのランドマークノード間の距離メトリックを行、列の要素に持つ行列Ｄの特異値分解であり、得られる直交行列Ｕの内、予め定められた次元数分の列を取り出したものが座標軸Ｕ’となる。なお、式（１）において、Ｗは特異値行列、Ｖは直交行列、ＶTはＶの転置行列である。【００１５】
Ｄ＝Ｕ・Ｗ・ＶT・・・（１）
一方、座標算出対象ノード１３０，１４０では、自ノードの座標が必要になった場合、距離メトリック取得部１３１，１４１が自ノードと他の全てのランドマークノード１１０，１２０との間の距離メトリックを測定する。具体的には、例えば、他の全てのランドマークノードに対してＰｉｎｇを実行し、実行結果を距離メトリックとする。そして、他の全てのランドマークノード１１０，１２０との間の距離メトリックの測定が終わると、距離メトリック取得部１３１，１４１は、測定した距離メトリックとその距離メトリックがどのノード間のものであるのかを示すノード間情報とからなる距離メトリック情報を座標要求部１３２，１４２に渡す。これにより、座標要求部１３２，１４２は、距離メトリック取得部１３１，１４１から渡された距離メトリック情報を含んだ座標要求を座標算出ノード１００に送信する。【００１６】
座標算出ノード１００では、座標算出対象ノード１３０，１４０から座標要求が送られてくると、座標軸格納部１０３から座標軸Ｕ’を取得し、これと座標算出対象ノード１３０，１４０から送られてきた座標要求に含まれている距離メトリック情報ｄ１，ｄ２とを用いて次式（２）に示す演算を行うことにより、座標算出対象ノード１３０，１４０の座標ｃ１，ｃ２を算出する。そして、算出した座標ｃ１，ｃ２を要求元のノード１３０，１４０へ返却する。【００１７】
ｃi＝Ｕ’Tｄi・・・（２）
座標算出対象ノード１３０，１４０内の座標要求部１３２，１４２は、座標算出ノード１００から返却された座標ｃ１，ｃ２をそれぞれ座標格納部１３３，１４３に格納する。【００１８】
また、座標算出対象ノード１３０内の距離メトリック推定部１３４は、他の座標算出対象ノード（座標算出対象ノード１４０とする）との間の距離メトリックを推定することが必要になると、座標格納部１３３，１４３から座標算出対象ノード１３０，１４０の座標ｃ１，ｃ２を取得し、両者のユークリッド距離を求める次式（３）の演算を行うことにより、座標算出対象ノード１３０，１４０間の距離メトリックｔ１２を推定する。【００１９】
ｔ12＝||ｃ1−ｃ2||・・・（３）
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Hyuk  Lim,  Jennifer  C.Hou,Chong−Ho  Choi,“Constructing  Internet  Coordinate  System  Based  on  Delay  Measurement”,Proceedings  of  the  3rd  ACM  SIGCOMM  conference  on  Internet  measurement（IMC‘03），2003年10月27日
【非特許文献２】Liying  Tang,Mark  Crovella，“Virtual  Landmarks  for  the  Internet”,Proceedings  of  the  3rd  ACM  SIGCOMM  conference  on  Internet  measurement（IMC‘03），2003年10月27日
【発明の概要】
【発明が解決しようとする課題】
【００２１】
インターネットなどのネットワークは、２ノード間の経路を決定する際、最短経路を選択する特性を有するため、非特許文献１，２に記載されている技術では、実際に測定した各ランドマークノード間の遅延時間（距離メトリック）が最短経路に沿った遅延時間であると考え、測定値をそのまま利用して２ノード間の距離メトリックを推定するようにしている。【００２２】
しかしながら、ＰｌａｎｅｔＬａｂのノードについて、２ノード間で直接通信したときに選択される経路の遅延時間と、他のノードを経由した最短経路で通信したときの遅延時間とを調べたところ、図４に示すように、２ノード間で直接通信を行ったときの方が遅延時間が長くなるケースがかなりあることが分かった。このことは、２ノード間の経路を決定する際、最短経路が選択されない場合があることを示している。なお、図４において、横軸は（２ノード間で直接通信したときの遅延時間）／（他のノードを経由して通信したときの遅延時間）を示し、縦軸は累積度数分布を示している。【００２３】
従って、実際に測定したランドマークノード間の遅延時間には、非最短経路に沿った遅延時間が含まれることになる。非最短経路に沿った距離メトリックは、最短経路を選択するという特性を有するインターネット等のネットワークにとってはノイズとなる情報である。非特許文献１，２に記載されている技術では、ネットワークに対してノイズとなる非最短経路に沿った遅延時間を含んだ測定結果を利用してノード間の遅延時間を推定しているため、推定精度が悪くなるという問題があった。【００２４】
本発明は、上述した課題であるノード間の距離メトリックの推定精度が悪いという問題を解決する距離メトリック推定システムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
本発明にかかる距離メトリック推定システムは、
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部と、
該距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段と、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段と、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段と、
該座標算出手段で座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する距離メトリック推定手段とを備える。【００２６】
本発明にかかる座標算出ノードは、
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部と、
該距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段と、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段と、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段とを備える。【００２７】
本発明にかかる距離メトリック推定方法は、
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部を設け、
最短経路探索手段が、前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する第１のステップと、
座標軸生成手段が、前記第１のステップで算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する第２のステップと、
座標算出手段が、座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記第２のステップで生成された座標軸とから前記座標算出対象ノードの座標を算出する第３のステップと、
距離メトリック推定手段が、前記第３のステップで座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する第４のステップとを含む。【００２８】
本発明にかかるプログラムは、
ネットワーク上に存在するランドマークノード毎に求めた、そのランドマークノードと他のランドマークノードとの間の距離メトリックが格納された距離メトリック格納部を備えたコンピュータを座標算出ノードとして機能させるためのプログラムであって
前記コンピュータを、
前記距離メトリック格納部に格納されているランドマークノード間の距離メトリックに基づいて、ランドマークノード毎にそのランドマークノードから他のランドマークノードへの最短経路を探索し、該探索した最短経路に沿った第１の距離メトリックを算出する最短経路探索手段、
該最短経路探索手段で算出された最短経路に沿った第１の距離メトリックから予め定められた次元数の座標軸を生成する座標軸生成手段、
座標算出対象ノードと前記ネットワーク上に存在する各ランドマークノードとの間の距離メトリックと、前記座標軸生成手段で生成された座標軸とから前記座標算出対象ノードの座標を算出する座標算出手段、
該座標算出手段で座標が算出された２つの座標算出対象ノード間の距離メトリックを、前記算出された座標を用いて推定する距離メトリック推定手段として機能させる。
【発明の効果】
【００２９】
本発明によれば、ネットワーク上の任意の２ノード間の距離メトリックを精度良く推定することができる。
【図面の簡単な説明】
【００３０】
【図１】非特許文献１，２に記載されている技術を説明するためのブロック図である。
【図２】距離メトリックを推定するネットワークの一例を示す図である。
【図３】座標軸を生成する処理を説明するためのフローチャートである。
【図４】２ノード間の直接の通信遅延と、最短経路上の通信遅延との比を示すグラフである。
【図５】本発明にかかる距離メトリック推定システムの第１の実施の形態の構成を示すブロック図である。
【図６】座標軸を生成する際の処理例を示すフローチャートである。
【図７】座標を算出する際の処理例を示すフローチャートである。
【図８】座標算出対象ノード間の距離メトリックを推定する際の処理例を示すフローチャートである。
【図９】本発明にかかる距離メトリック推定システムの第２の実施の形態の構成を示すブロック図である。
【図１０】データ所在格納部の内容例を示す図である。
【図１１】座標格納部の内容例を示す図である。
【図１２】遅延格納部の内容例を示す図である。
【図１３】遅延格納部に格納されている情報に基づいて最短経路探索部が生成した最短経路に沿った遅延時間を示す図である。
【図１４】座標軸生成部が生成した座標軸の一例を示す図である。
【図１５】非特許文献１，２に記載されている技術の問題点を説明するための図である。
【図１６】遅延測定部の測定結果を示す図である。
【図１７】遅延測定部の測定結果に基づいて算出した最短路に沿った遅延時間を示す図である。
【図１８】座標算出部で算出される座標の一例を示す図である。
【図１９】非特許文献１，２に記載されている技術によって算出される座標の一例を示す図である。
【図２０】主にデータ所在管理サーバの処理例を示すフローチャートである。
【図２１】遅延推定部の推定結果を示す図である。
【図２２】非特許文献１，２に記載されている技術によって推定したクライアント間遅延時間を示す図である。
【図２３】遅延時間の実測値を示す図である。
【図２４】ＰｌａｎｅＬａｂシステムのノードの座標を示す図である。
【図２５】ＰｌａｎｅＬａｂシステムのノード間の遅延時間の推測値と実測値との誤差を示すグラフである。
【発明を実施するための形態】
【００３１】
次に、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００３２】
（第１の実施の形態）
図５を参照すると、本発明にかかる距離メトリック推定システムは、座標算出ノード１００の代わりに座標算出ノード１００ａを備えている点で、図１に示した距離メトリック推定システムと相違している。なお、図５においても説明を分かりやすくするために、ランドマークノードおよび座標算出対象ノードをそれぞれ２台としているが、実際には図２に示したように多数存在する。
【００３３】
座標算出ノード１００ａは、座標軸生成部１０１および座標算出部１０４の代わりにそれぞれ座標軸生成部１０１ａおよび座標算出部１０４ａを備えている点と、最短経路探索部１０５が追加されている点が、図１に示した座標算出ノード１００と相違している。
【００３４】
座標軸生成部１０１ａは、距離メトリック格納部１０２に格納されているランドマークノード間の距離メトリック情報から直接座標軸を生成するのではなく、上記距離メトリック情報を最短経路探索部１０５に与えることにより求めた、ランドマークノード間の最短経路に沿った距離メトリック情報を利用して座標軸を生成する点が、図１に示した座標生成部１０１と相違している。
【００３５】
座標算出部１０４ａは、座標算出対象ノード（例えば、座標算出対象ノード１３０）から送られてきた座標算出対象ノード１３０とランドマークノード１１０，１２０との間の距離メトリック情報から直接座標を算出するのではなく、上記距離メトリック情報および距離メトリック格納部１０２に格納されているランドマークノード間の距離メトリック情報を最短経路探索部１０５に与えることにより求めた、座標算出対象ノード１３０と各ランドマークノード１１０、１２０との間の最短経路に沿った距離メトリック情報を利用して座標算出対象ノード１３０の座標を算出する点が、図１に示した座標算出部１０４と相違している。
【００３６】
最短経路探索部１０５は、座標軸生成部１０１ａからランドマークノード間の距離メトリック情報が与えられた場合は、ランドマークノード毎に、そのランドマークノードから他のランドマークノードへの最短経路を探索し、探索した最短経路の距離メトリック情報を座標軸生成部１０１ａに返す。また、座標算出部１０４ａから座標算出対象ノードとランドマークノードとの間の距離メトリック情報と、ランドマークノード間の距離メトリック情報とが与えられた場合は、座標算出対象ノードから各ランドマークノードへの最短経路を探索し、探索した最短経路の距離メトリック情報を座標算出部１０４ａに返す。なお、最短経路の探索法としては、例えば、Ｄｉｊｋｓｔｒａアルゴリズムを利用することができる。
【００３７】
このような機能を有する座標算出ノード１００ａは、プログラム制御により動作するコンピュータによって実現することができる。具体的には、コンピュータを、座標軸生成部１０１ａ、座標算出部１０４ａおよび最短経路探索部１０５として機能させるためのプログラムを記録したディスク、半導体メモリなどの記録媒体を用意し、上記プログラムをコンピュータに読み取らせる。コンピュータは、読み取ったプログラムに従って自身の動作を制御することにより、自コンピュータ上に、座標軸生成部１０１ａ、座標算出部１０４ａおよび最短経路探索部１０５を実現する。また、ランドマークノード１１０，１２０および座標算出対象ノード１３０，１４０もプログラム制御により動作するコンピュータで実現可能である。
【００３８】
なお、図５に示した各ノード１００ａ，１１０，１２０，１３０，１４０の構成は一例に過ぎず、種々の変形が可能である。例えば、座標算出ノードの構成要素の全て、或いは、何れかがランドマークノードに含まれ、ランドマークノード間で情報が分散的に交換される構成であっても良い。また、座標算出対象ノードの構成要素である座標格納部や距離メトリック推定手段については、ランドマークノード１１０，１２０で管理されていても良い。これらの組み合わせの可能性については数え切れないが、ネットワーク上の各ノードにおいて他のノードとの距離メトリックを十分に取得できるようには、分散している必要がある。例えば、インターネットにおけるＰｉｎｇを用いた遅延推定を利用する場合、全てのランドマークノードおよび全ての座標算出対象ノードに距離メトリック取得手段としてのＰｉｎｇ実行手段が分散配置される必要がある。この測定結果から座標を算出する処理は、分散的に複数のノードで行っても、集中的に特定のノードで行っても良い。
【００３９】
次に、本実施の形態の動作について詳細に説明する。
【００４０】
先ず、座標軸を生成するまでの処理の流れを図６のフローチャートを参照して説明する。
【００４１】
先ず、ランドマークノード１１０，１２０内の距離メトリック取得部１１１，１２１が他のランドマークノードとの間の距離メトリックを測定し、測定した距離メトリックと、その距離メトリックがどのノード間のものなのかを示すノード間情報とを含んだ距離メトリック情報を座標算出ノード１００ａへ送信する。これにより、座標算出ノード１００ａ内の距離メトリック格納部１０２に、ランドマークノード間の距離メトリック情報が格納される（ステップ２０１）。
【００４２】
次に、座標算出ノード１００ａの座標軸生成部１０１ａが、ランドマークノード間の距離メトリック情報を、距離メトリック格納部１０２から取得する（ステップ２０２）。
【００４３】
その後、座標軸生成部１０１ａは、ステップ２０２で取得した距離メトリック情報を最短経路探索部１０５に渡し、ランドマークノード間の最短経路に沿った距離メトリック情報を生成することを要求する。これにより、最短経路探索部１０５は、ランドマークノード毎に、そのランドマークノードから他のランドマークノードへの最短経路を探索し、探索した最短経路の距離メトリック情報を座標軸生成部１０１ａに返す（ステップ２０３）。
【００４４】
その後、座標軸生成部１０１ａは、最短経路探索部１０５から返却されたランドマークノード間の最短経路に沿った距離メトリック情報を、前出した式（１）を用いて予め定められた次元数に線形次元圧縮することで座標軸を生成する。そして、最後に座標軸生成部１０１ａは、生成した座標軸を座標軸格納部１０３に格納する（ステップ２０４）。なお、座標軸の生成方法は、式（１）で示される特異値分解にかぎられるものではなく、固有値分解であっても、多次元尺度構成法（ＭＤＳ）であっても良い。
【００４５】
次に、座標算出対象ノードの座標を決定する際の処理の流れを図７のフローチャートを参照して説明する。
【００４６】
座標算出対象ノード（例えば、座標算出対象ノード１３０）の座標を算出する場合は、先ず、座標算出対象ノード１３０内の距離メトリック取得部１３１が、自ノードと特定の複数のランドマークノードとの間の距離メトリックを測定し、測定した距離メトリックとその距離メトリックがどのノード間のものなのかを示すノード間情報とを含んだ距離メトリック情報を座標要求部１３２に渡す（ステップ３０１）。これにより、座標要求部１３２が、上記距離メトリック情報を含んだ座標要求を座標算出ノード１００ａに送信する（ステップ３０２）。
【００４７】
座標算出ノード１００ａの座標算出部１０４ａは、受け取った距離メトリック情報と、距離メトリック格納部１０２に格納されている全てのランドマークノード間の距離メトリック情報を最短経路探索部１０５に渡す。これにより、最短経路探索部１０５は、座標算出対象ノード１３０から全てのランドマークノードへの最短経路に沿った距離メトリック情報を生成する（ステップ３０３）。
【００４８】
その後、座標算出部１０４ａは、座標軸格納部１０３に格納されている座標軸と、最短経路探索部１０５で生成された最短経路に沿った距離メトリックとに対して前出した式（２）に示す演算を行い、両者の積を座標として算出する。そして、算出した座標を要求元のノード１３０に返す（ステップ３０４）。座標算出対象ノード１３０では、座標要求部１３２が座標算出ノード１００ａから返された座標を座標格納部１３３に格納する。
【００４９】
次に、座標算出対象ノード間の距離メトリックを推定する処理について、図８のフローチャートを参照して説明する。
【００５０】
座標算出対象ノード（例えば、座標算出対象ノード１３０）が他の座標算出対象ノード（例えば、座標算出対象ノード１４０）との間の距離メトリックを推測する場合、距離メトリック推定部１３４が、座標格納部１３３，１４３に格納されている各ノード１３０，１４０の座標を取得し、両者のユークリッド距離を算出することで、両ノード１３０，１４０間の距離メトリックを推定する（ステップ４０１）。具体的には、前出の式（３）に示す演算を行うことにより、両ノード１３０，１４０間の距離メトリックを推定する。
【００５１】
（第１の実施の形態の効果）
本実施の形態によれば、ネットワーク上の座標算出対象ノード間の距離メトリックを精度良く推定することができる。その理由は、座標軸生成部１０１ａにおいて座標軸を生成する際、実際に測定したランドマークノード間の距離メトリック（非最短経路に沿った距離メトリックが含まれる）を用いるのではなく、実際に測定した距離メトリックに基づいて最短経路探索部１０５で算出した最短経路に沿った距離メトリックを用いて座標軸を生成するようにしているからである。すなわち、基本的には最短経路を選択するネットワークにおいてはノイズとなる、非最短経路に沿った距離メトリックを、最短経路探索部１０５を用いて最短経路に沿った距離メトリックに変換してから座標軸を生成するようにしており、非最短経路に沿った距離メトリックが及ぼす悪影響を低減できるので、推定精度を高いものにすることができる。
【００５２】
また、本実施の形態は、座標算出部１０４ａにおいて座標算出対象ノードの座標を算出する際、実際に測定した座標算出対象ノードとランドマークノードとの間の距離メトリックを用いるのではなく、実際に測定した距離メトリックに基づいて最短経路探索部１０５が算出した最短経路に沿った距離メトリックを用いて座標を算出するようにしているので、距離メトリックの推定精度を更に高いものにすることができる。
【００５３】
また、本実施の形態によれば、座標算出対象ノードと全てのランドマークノードの距離メトリックを測定しなくとも座標算出部１０４ａにおいて、座標を算出することができる。その理由は、特定のランドマークノード間の距離メトリックが欠落していても、最短経路探索部１０５により、欠落した距離メトリックを、他のランドマークノードを経由した最短経路に沿った距離メトリックで穴埋めすることができるからである。
【００５４】
更に、本実施の形態によれば、ランドマークノードや座標算出対象ノードからなるネットワーク（オーバレイネットワーク）において、ランドマークノードや距離算出対象ノードが最短経路となる迂回経路をとった場合の距離メトリックを推定することができる。その理由は、実際に測定したランドマークノード間の距離メトリックに対して、最短経路探索部１０５による最短経路探索を施し、最短経路に沿った距離メトリックを算出する過程が、実際にネットワーク上でデータを転送した場合の累積遅延を模擬しているといえるためである。
【００５５】
（第２の実施の形態）
次に、本発明にかかる距離メトリック推定システムの第２の実施の形態について詳細に説明する。
【００５６】
本実施の形態は、クライアントが映像コンテンツなどのコンテンツを取得する際、上記コンテンツを所持しているノードのうち、自クライアントに対して最近傍のノードからコンテンツを取得できるようにしたことを特徴とする。ここで、上記ノードを配信専用のサーバとする形態や、ピア・ツー・ピアによりデータ交換を行う他のクライアントとする形態をとることができるが、本実施の形態では、後者の形態をとるものとする。また、本実施の形態中の遅延データは、ＰｌａｎｅｔＬａｂと呼ばれる世界中のインターネット上のサーバ間における実測値を用いており、本発明を適用した実験結果もこれに基づいたものである。
【００５７】
図９を参照すると、本実施の形態は、座標算出サーバ５００と、複数のランドマークサーバ５１０，５２０と、複数のクライアント５３０，５４０，５５０と、データ所在管理サーバ５６０とを備えており、それらはネットワークを介して相互に接続されている。
【００５８】
座標算出サーバ５００は、座標軸生成部５０１、遅延格納部５０２、座標軸格納部５０３、座標算出部５０４および最短経路探索部５０５から構成される。これらは、図５に示した座標軸生成部１０１ａ、距離メトリック格納部１０２、座標軸格納部１０３、座標算出部１０４ａおよび最短経路探索部１０５と同一の構成を有している。
【００５９】
ランドマークサーバ５１０，５２０は、それぞれ遅延測定部５１１，５２１と、通信応答部５１２，５２２とを備えている。
【００６０】
遅延測定部５１１，５２１は、それぞれＰｉｎｇコマンドを実行することにより、他のランドマークサーバとの間の遅延時間を測定し、測定結果を座標算出サーバ５００内の遅延格納部５０２に格納する機能を有する。通信応答部５１２，５２２は、それぞれ他のランドマークサーバあるいはクライアントからの遅延測定メッセージを受け付け応答を返す機能を有する。
【００６１】
クライアント５３０，５４０，５５０は、それぞれ遅延測定部５３１，５４１，５５１と、座標要求部５３２，５４２，５５２と、座標格納部５３３，５４３，５５３と、データ格納部５３４，５４４，５５４と、データ取得部５３５，５４５，５５５とを備えている。
【００６２】
遅延測定部５３１，５４１，５５１は、それぞれＰｉｎｇコマンドを実行することにより、ランドマークサーバ５１０，５２０との間の遅延時間を測定し、測定結果を座標要求部５３２，５４２，５５２に渡す機能を有する。座標要求部５３２，５４２，５５２は、それぞれ遅延測定部５３１，５４１，５５１から渡された測定結果を含んだ座標要求を座標算出サーバ５００へ送信し、これに応答して座標算出サーバ５００から返却され自クライアントの座標を座標格納部５３３，５４３，５５３に格納する機能を有する。データ格納部５３４，５４４，５５４には映像コンテンツなどのコンテンツが格納される。データ取得部５３５，５４５，５５５は、試聴要求の発生したコンテンツのコンテンツ識別子および自クライアントの座標を含んだ最近傍コンテンツ問い合わせをデータ所在管理サーバ５６０に送信する機能や、この問い合わせに応答してデータ所在管理サーバ５６０から返却されたクライアント識別子によって特定されるクライアントからコンテンツを取得する機能を有する。
【００６３】
データ所在管理サーバ５６０は、データ所在格納部５６１と、最近傍決定部５６２と、遅延推定部５６３と、座標格納部５６４とを備えている。
【００６４】
データ所在格納部５６１には、コンテンツを特定するコンテンツ識別子と、そのコンテンツを所持しているクライアントを特定するクライアント識別子とが関連付けて登録されている。
【００６５】
図１０にデータ所在格納部５６１の内容例を示す。
【００６６】
この例の１行目は、コンテンツ識別子「あ」で特定されるコンテンツは、クライアント識別子「ａ」「ｃ」によって特定されるクライアントで所持されていることを示している。なお、以下の説明では、クライアント５３０，５４０，５５０がそれぞれクライアント識別子ａ，ｂ，ｃによって特定されるクライアントであるとする。また、以下の説明ではクライアント識別子ａ，ｂ，ｃのクライアントをクライアントａ，ｂ，ｃと呼ぶ場合がある。
【００６７】
座標格納部５６４には、データ所在格納部５６１にクライアント識別子が登録されているクライアントの座標が登録されている。
【００６８】
図１１に座標格納部５６４の内容例を示す。
【００６９】
最近傍決定部５６２は、クライアントから送られてきた最近傍クライアント問い合わせ中のコンテンツ識別子によって特定されるコンテンツを所持しているクライアントをデータ所在格納部５６１から検索する機能や、問い合わせ元のクライアントの座標とデータ所在格納部５６１から検索したクライアント識別子とを遅延推定部５６３に渡し、クライアント間の遅延時間（距離メトリック）を推定することを依頼する機能や、遅延推定部５６３が推定した遅延時間に基づいて、上記コンテンツを所持している、問い合わせ元のクライアントから最近傍のクライアントを求め、そのクライアントのクライアント識別子を問い合わせ元のクライアントに返却する機能を有する。
【００７０】
遅延推定部５６３は、最近傍決定部５６２から渡されたクライアント識別子によって特定されるクライアントの座標を座標格納部５６４から検索する機能や、検索した座標と問い合わせ元のクライアントの座標とのユークリッド距離を求めることにより、両クライアント間の遅延時間を推定する機能を有する。
【００７１】
次に、本実施の形態の動作について詳細に説明する。
【００７２】
先ず、座標算出に必要になる座標軸の生成処理について説明する。
【００７３】
この座標軸の生成処理においては、先ず、各ランドマークサーバ５１０，５２０内の遅延測定部５１１，５２１が他のランドマークサーバとの間の遅延時間を測定し、その測定結果を座標算出サーバ５００内の遅延格納部５０２に格納する。この遅延格納部５０２に格納された遅延時間の測定結果を図１２に示す。
【００７４】
図１２においてＡ〜Ｈはランドマークサーバの識別子を表し、数字は遅延時間（単位はｍｓｅｃ）を表している。なお、以下の説明では、識別子がＡのランドマークサーバをランドマークサーバＡと呼ぶ場合がある。
【００７５】
次に、座標軸生成部５０１が遅延格納部５０２に格納されているランドマークサーバ間の遅延時間の測定結果を最短経路探索部５０５に渡し、ランドマークサーバ間の最短経路に沿った遅延時間を算出させる。これにより、図１３に示すような、ランドマークサーバ間の最短経路に沿った遅延時間が算出される。
【００７６】
例えば、ランドマークサーバＡからランドマークサーバＤまでの遅延時間の測定値は図１２に示すように２６５ｍｓｅｃであるが、ランドマークサーバＡからランドマークサーバＤまでの最短経路に沿った遅延時間は図１３に示すように１４３ｍｓｅｃとなる。
【００７７】
つまり、ランドマークサーバＡからランドマークサーバＤへの最短経路は、ランドマークサーバＡ→Ｆ→Ｄであり、ランドマークサーバＡからランドマークサーバＦへの遅延時間が３８ｍｓｅｃ、ランドマークサーバＦからランドマークサーバＤへの遅延時間が１０５ｍｓｅｃであるので、ランドマークサーバＡからランドマークサーバＤまでの最短経路に沿った遅延時間は両者の和である１４３ｍｓｅｃとなる。その後、座標軸生成部５０１は、図１３に示した最短経路に沿った遅延時間の情報に対して、特異値分解を用いた主成分分析を行い、主要な３つの座標軸を取り出す。そして、取り出した３つの座標軸を座標軸格納部５０３に格納する。このとき、座標軸格納部５０３に格納された３つの座標軸を図１４に示す。なお、取り出す軸の数はこれに限られるものではない。
【００７８】
ここで、最短経路に沿った遅延時間を用いて座標軸を生成する理由について、図１５を参照して説明する。中継ノード群は、ノードＮ１とノードＮ２との間の経路として経路Ｌ１を選択する。しかし、経路Ｌ１には遅延を大きくする要因Ｘが存在している。この要因Ｘは局所的なものであるため、大域的は無視され、ネットワーク全体にわたって成り立っている最短経路を選ぶ特性を残して次元を圧縮し、座標軸を生成することが望ましい。そのため、ノードＮ１とノードＮ２との間の遅延時間は、経路Ｌ１に沿った遅延時間ではなく、最短経路に沿った遅延時間とすることが望まれる。しかし、中継ノードの設定を変更して遅延時間を測定することはできない。そこで、近似的にノードＮ３を経由した経路を考え、経路Ｌ１の遅延時間よりも、経路Ｌ２の遅延時間と経路Ｌ３の遅延時間との和が小さければ、経路Ｌ１の遅延時間を経路Ｌ２の遅延時間と経路Ｌ３の遅延時間との和に変換して次元圧縮を行うことで、ネットワークが全体として保っている最短経路を選ぶ特性を維持した座標軸を生成することができる。
【００７９】
次に、クライアント識別子ａ，ｂ，ｃを有するクライアント５３０，５４０，５５０の座標を求める際の処理について説明する。先ず、クライアントａ，ｂ，ｃ内の遅延測定部５３１，５４１，５５１が自クライアントと各ランドマークサーバとの間の遅延時間を測定する。各クライアントａ，ｂ，ｃで測定された遅延時間を図１６に示す。
【００８０】
図１６は、クライアントａ，ｂ，ｃがランドマークサーバＡ〜Ｈに対して行った遅延時間の測定結果を表しており、例えばクライアントａがランドマークサーバＡに対して行った遅延時間の測定結果は２３ｍｓｅｃである。
【００８１】
その後、クライアントａ，ｂ，ｃ内の座標要求部５３２，５４２，５５２は、それぞれ遅延時間測定部５３１，５４１，５５１が測定した遅延時間を含んだ座標要求を座標算出サーバ５００へ送信する。例えば、クライアントａが送信する座標要求には、遅延時間（２３，１５，２０７，５０２，１５９，５６，１９７，１８３）が含まれている。
【００８２】
座標算出サーバ５００内の座標算出部５０４は、クライアントａ，ｂ，ｃから座標要求が送られてくると、各座標要求を順次処理対象にして次のような処理を行う。先ず、クライアントａからの座標要求を処理対象にして、それに含まれている遅延時間と遅延格納部５０２から取り出した、図１２に示す遅延時間の情報を最短経路探索部５０５に渡す。これにより、最短経路探索部５０５は、クライアントａから各ランドマークサーバＡ〜Ｈへの最短経路に沿った遅延時間を算出する。
【００８３】
図１７の第１列目に、クライアントａからランドマークサーバＡ〜Ｈへの最短経路に沿った遅延時間を示す。
【００８４】
ここでは、クライアントａからランドマークサーバＤへの遅延時間が、５０２ｍｓｅｃから１６１ｍｓｅｃに更新されている。この遅延時間１６１ｍｓｅｃは、クライアントａからランドマークサーバＦまでの遅延時間５６ｍｓｅｃと、ランドマークサーバＦからランドマークサーバＤまでの遅延時間１０５ｍｓｅｃとの和である。
【００８５】
その後、座標算出部５０４は、クライアントａからランドマークサーバＡ〜Ｈへの最短経路に沿った遅延時間（図１７の第１列目参照）と、座標軸格納部５０３に格納されている座標軸（図１４参照）との積を求めることにより、クライアントａの座標を算出する。クライアントａの座標を図１８の第１列目に示す。なお、座標算出部５０４は、算出した座標をクライアントａに送信し、クライアントａでは、座標要求部５３２が座標算出サーバ５００から送られてきた座標を座標格納部５３３に格納する。
【００８６】
その後、座標算出部５０４は、クライアントｂ，ｃから送られてきた座標要求を順次処理対象にして、前述した処理と同様の処理を行う。これにより、クライアントｂ，ｃからランドマークサーバＡ〜Ｈへの最短経路に沿った遅延時間として図１７の第２列目、第３列目に示す遅延時間が算出され、クライアントｂ，ｃの座標として、図１８の第２行目、第３行目に示す座標が算出される。
【００８７】
なお、非特許文献１，２に記載された技術により求めた各クライアントａ，ｂ，ｃの座標を図１９に示す。
【００８８】
ここで、測定した遅延時間を最短経路に沿った遅延時間で置き換えられたことは、必ずしも全てのランドマークサーバとの間の遅延時間を測定する必要がないことを示している。すなわち、クライアントａはランドマークサーバＤまでの遅延時間を測定しなくても良く、ランドマークサーバＣまでの遅延時間についても、ランドマークサーバＦまでの遅延時間５６ｍｓｅｃと、ランドマークサーバＡからランドマークサーバＣまでの遅延時間１５３ｍｓｅｃとの和から２０９ｍｓｅｃが得られ、実際のランドマークサーバＣまでの遅延時間２０７ｍｓｅｃとほぼ同じ値が得られる。なお、一部のランドマークサーバとの間の遅延時間しか測定しない場合は、自クライアントとの間の遅延時間が小さいと予測されるランドマークサーバ（例えば、クライアントと同じ地域に存在するランドマークサーバ）との間の遅延時間だけを測定するようにすれば良い。
【００８９】
次に、上記した処理で算出されたクライアントの座標を用いて、コンテンツの取得を要求するクライアント（クライアントｂとする）が、他のクライアントから上記コンテンツを取得する場合の動作について説明する。なお、クライアントａ，ｃは既にコンテンツ識別子「あ」の映像コンテンツを視聴済みで、上記コンテンツをデータ格納部５３４，５５４に保持しているとする。また、データ所在管理サーバ５６０のデータ所在格納部５６１には、クライアントａ，ｃからの要求によってクライアント識別子ａ，ｃとコンテンツ識別子「あ」が関連付けて登録され（図１０参照）、座標格納部５６４には、クライアントａ，ｃからの要求によってクライアントａ，ｃの座標が登録されているとする（図１１参照）。また、以下の説明では、コンテンツ識別子「あ」の映像コンテンツを映像コンテンツ「あ」という場合がある。
【００９０】
クライアントｂ内のデータ取得部５４５は、映像コンテンツ「あ」に対する視聴要求が発生すると、図２０のフローチャートに示すように、データ所在管理サーバ５６０に対して最近傍クライアント問い合わせを送信する（ステップ１５０１）。この最近傍クライアント問い合わせには、コンテンツ識別子「あ」と、座標格納部５４３から読み出したクライアントｂの座標とが含まれている。
【００９１】
データ所在管理サーバ５６０内の最近傍決定部５６２は、クライアントｂからの最近傍クライアント問い合わせを受信すると、先ず、映像コンテンツ「あ」を所持しているクライアントのクライアント識別子をデータ所在格納部５６１から検索する（ステップ１５０２）。この例では、クライアント識別子ａ，ｃが検索される。
【００９２】
その後、最近傍決定部５６２は、クライアント識別子ａ，ｃと、クライアントｂの座標とを遅延推定部５６３に渡し、クライアントｂとクライアントａ，ｃとの間の遅延時間を推定することを依頼する（ステップ１５０３）。これにより、遅延推定部５６３は、座標格納部５６４からクライアントａ，ｃの座標を読み出し、これとクライアントｂの座標とから、クライアントａ，ｂ間およびクライアントｂ，ｃ間のユークリッド距離（遅延時間）を推定する。図２１にその推定結果を示す。クライアントａ，ｂ間の遅延時間７０ｍｓｅｃは、［（−１７６＋１４４）２＋（５７−２）２＋（１２−４０）２］１／２により求めたものである。なお、非特許文献１，２に記載されている技術による推定結果、および実測値をそれぞれ図２２および図２３に示す。
【００９３】
その後、最近傍決定部５６２は、遅延推定部５６３の推定結果に基づいて、クライアントｂはクライアントｃよりもクライアントａに近いと判断し、クライアントｂに対して最近傍のクライアントａから映像コンテンツ「あ」を取得することを指示する（ステップ１５０４）。この指示に基づき、クライアントｂのデータ取得部５４５は、クライアントａのデータ格納部５３４にアクセスし、当該コンテンツを取得する。ネットワーク上でコンテンツ「あ」を所持しているクライアントの内の、最近傍のノードが選択されているため、クライアントｂは、短時間でコンテンツを取得することができる。なお、ここで非特許文献１，２の推定結果であれば、図２２から分かるように、クライアントｂは、クライアントａにもクライアントｃにも同一遅延時間であると判断し、クライアントｃに取りに行くことがあり得る。
【００９４】
なお、ここで用いたデータは世界中のインターネット上のノードから構成されたＰｌａｎｅｔＬａｂシステム（９３ノード）のデータを基にしている。上記した実施の形態では、クライアントとして３ノードを例示したが、９３ノードの座標を図２４に示し、その座標から算出した９３ノード間の遅延時間の推定値と実測値との誤差を図２５に示している。また、非特許文献１，２による誤差を破線で示している。この図から本発明の方が推定誤差が小さいことが分かる。
【００９５】
なお、上述した説明では、距離メトリックを遅延時間としたが、通信に要する費用としても良いし、遅延時間と通信に要する費用との両方にしても良い。また、上述した説明では、ネットワークを通信ネットワークとしたが、ネットワークを交通網としても良い。ネットワークを交通網とした場合は、距離メトリックを移動に要する移動時間、移動に要する費用、あるいは移動時間と移動に要する費用との両方にすることができる。上述した説明では、最近傍決定部５６２は、遅延時間が最短の座標算出対象ノードを選択するようにしたが、通信に要する費用を最小にする座標算出対象ノード、あるいは遅延時間と通信に要する費用を最小にする座標算出対象ノードを選択するようにしても良い。また、ネットワークを交通網とした場合には、最近傍決定部５６２は、移動に要する時間が最小の座標算出対象ノード、移動に要する費用が最小の座標算出対象ノード、あるいは移動に要する時間と移動に要する時間が最小の座標算出対象ノードを選択するようにしても良い。
【００９６】
（第２の実施の形態の効果）
本実施の形態によれば、クライアントがコンテンツを取得する際、上記コンテンツを所持している他のクライアントの内、自クライアントから最も遅延時間の短いクライアントからコンテンツを取得することができる。その理由は、最近傍決定部５６２が遅延推定部５６３を用いて、コンテンツを所持しているクライアントと、上記コンテンツの取得を希望しているクライアントとの間の遅延時間を推定し、遅延時間が最も少ないクライアントからコンテンツを取得するように指示しているためである。
【産業上の利用可能性】
【００９７】
本発明は、インターネット上に分散配置されたデータを高速に取得するといった用途に適用できる。例えば、ＣＤＮ（コンテンツ・デリバリー・ネットワーク）では、インターネット上の複数個所に複製された映像・ビデオのデータから、最も近いデータを取得する際に、適用することができる。ここでのデータは、ビデオのような容量の大きなデータに限らず、ファイルのような容量の小さなデータも含まれる。すなわち、広域に分散したデータベースやストレージの高速化に利用することができる。【００９８】
また、別の用途では、交通網を介した時間の見積といった用途に利用でき、最近傍の郵便局を探すといった地理検索にも応用できる。ここでは、ネットワークとして交通網をとり、中継点を駅や交差点とし、ランドマーク部として著名な施設・場所とすると、交通網を介した時間を見積もることのできる座標を算出することができる。すなわち、自宅から著名な施設・場所への時間を設定することで、その自宅に座標を割り振ることができ、他の座標を持った任意の場所との時間を、見積もることができる。【００９９】
以上、実施例を参照して本願発明を説明したが、本願発明は上記実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１００】
この出願は、２００８年９月２９日に出願された日本出願特願２００８−２４９５７８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2010035565.tif 000003
【図２】
2010035565.tif 000004
【図３】
2010035565.tif 000005
【図４】
2010035565.tif 000006
【図５】
2010035565.tif 000007
【図６】
2010035565.tif 000008
【図７】
2010035565.tif 000009
【図８】
2010035565.tif 000010
【図９】
2010035565.tif 000011
【図１０】
2010035565.tif 000012
【図１１】
2010035565.tif 000013
【図１２】
2010035565.tif 000014
【図１３】
2010035565.tif 000015
【図１４】
2010035565.tif 000016
【図１５】
2010035565.tif 000017
【図１６】
2010035565.tif 000018
【図１７】
2010035565.tif 000019
【図１８】
2010035565.tif 000020
【図１９】
2010035565.tif 000021
【図２０】
2010035565.tif 000022
【図２１】
2010035565.tif 000023
【図２２】
2010035565.tif 000024
【図２３】
2010035565.tif 000025
【図２４】
2010035565.tif 000026
【図２５】
2010035565.tif 000027
【国際調査報告】
2010035565.tif 000028
2010035565.tif 000029
2010035565.tif 000030
2010035565.tif 000031