(57)【特許請求の範囲】
【請求項１】
インターネットに接続するＮ個のノードに対して、コンピュータ制御により各ノード間の距離を推定するノード間距離推定方法において、
予め各ノードを次元ｋの幾何学的な座標空間にマッピングし、かつそのグローバルな座標空間上の各ノードを予め定めたＫ個のクラスタに分割し、各ノードのグローバルな座標空間における座標位置と、各ノードに自身がマッピングされたクラスタにおけるローカルな座標空間における座標位置をメモリに保持しておき、
該コンピュータは、グローバルな座標空間における座標位置およびローカルな座標空間における座標位置の２つを持つ各ノードに対し、前記メモリから読み出した座標位置を用いることにより、任意の２ノード間の距離を推定することを特徴とする通信網におけるノード間距離推定方法。
【請求項２】
請求項１に記載の通信網におけるノード間距離推定方法において、
前記ノード内のコンピュータは、対象とする前記Ｎ個のノードの中から、ｍ個のランドマークノードを選択し、ランドマークノードＬ_ｉとＬ_ｊの間での距離ｄ（Ｌ_ｉ,Ｌ_ｊ)を測定して、該距離ｄをメモリに保持し、次に、該メモリから読み出した前記距離ｄを用いてｍ個のランドマークノードをＫ個のクラスタにグループ化して、グループ化された情報をメモリに保持し、
その後、ランドマークノードでない各一般ノードｉは各ランドマークノードＬ_ｊまでの距離ｄ（ｉ，Ｌ_ｊ)を測定し、該ノードｉは最も近いランドマークノードの属するクラスタへ所属させることを特徴とする通信網におけるノード間距離推定方法。
【請求項３】
請求項２に記載の通信網におけるノード間距離推定方法において、
前記ランドマークノード内のコンピュータは、ランドマークノードＬ_iとＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素に持つｍ×ｍのマトリクスＤを作成して、これをメモリに保持し、
上記マトリクスＤに対して特異値分解と呼ばれる行列分解を実施して、Ｄ＝Ｕ・Ｗ・ＶＴを出力し（ここで、Ｕ，Ｖはｍ×ｍの直交行列、Ｗは対角行列、ＶＴはＶの転置行列）、
次に、該コンピュータは、ランドマークノードＬ_ｉに対して、Ｌ_ｉとＬ_ｊの距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素に持つｍ×１のベクトルφ（Ｌ_ｉ）＝［ｄ（Ｌ_ｉ，Ｌ_１），ｄ（Ｌ_ｉ，Ｌ_２），・・，ｄ（Ｌ_ｉ，Ｌ_ｍ）］Ｔを作成して、これを該メモリに保持し、
一方、該メモリから読み出されたＵの最初のｋ列を抜き出して、それをＵｋとし（ｍ×ｋの行列）、φ’（Ｌ_ｉ）＝ＵｋＴ×φ（Ｌ_ｉ）で得られたｋ次元ベクトルφ’（Ｌ_ｉ）を、ランドマークノードＬ_ｉのグローバルな座標位置とすることを特徴とする通信網におけるノード間距離推定方法。
【請求項４】
請求項２に記載の通信網におけるノード間距離推定方法において、
前記ランドマークノード内のコンピュータは、あるクラスタｘに属するｍｘ個のランドマークノードＬ_{ｌ，ｘ｝，Ｌ_｛２,ｘ｝，・・・，Ｌ_{ｍｘ，ｘ｝に対して、ランドマークノードＬ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の間での距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×ｍｘのマトリクスＤｘを作成し、そのＤｘに対して特異値分解を実施し、その結果をＤｘ＝Ｕｘ・Ｗｘ・ＶｘＴとし、
次に、ランドマークノードＬ_｛ｉ，ｘ｝に対して、Ｌ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（Ｌ_ｉ）＝［ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛１，ｘ｝，ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛２，ｘ｝），・・・・，ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、一方、Ｕｘの最初のｋ列を抜き出して、それをＵｘｋとし（ｍｘ×ｋの行列）、φｘ’（Ｌ_ｉ）＝ＵｘｋＴ×φｘ（Ｌ_ｉ）で得られたｋ次元ベクトルφｘ’（Ｌ_ｉ）を、ランドマークノードＬ_｛ｉ，ｘ｝のクラスタｘ内でのローカルな座標位置とすることを特徴とする通信網におけるノード間距離推定方法。
【請求項５】
請求項２に記載の通信網におけるノード間距離推定方法において、
前記ランドマークノード内のコンピュータは、クラスタｘに属する一般ノードｉ_ｘに対して、ｉ_ｘとランドマークノードＬ_｛ｊ，ｘ｝の距離ｄ（ｉ_ｘ，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（ｉ）＝［ｄ（ｉ_ｘ，Ｌ_｛１，ｘ｝），ｄ（ｉ_ｘ，Ｌ_｛２，ｘ｝，・・・・，ｄ（ｉ_ｘ，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、後は請求項４の方法により、一般ノードｉ_ｘのクラスタｘでのローカルな座標位置を計算することを特徴とする通信網におけるノード間距離推定方法。
【請求項６】
請求項２に記載の通信網におけるノード間距離推定方法において、
前記一般ノード内のコンピュータは、クラスタｘからＬｘ個のノードを選択し、ノードｊ（ｊ＝１，・・・，Ｌｘ）のグローバルな座標位置をφｘ’Ｇ（ｊ）（ｋ×１次元のベクトル）、ローカルな座標位置をφｘ’Ｃ（ｊ）（ｋ×１次元のベクトル）とし、Ｌｘ×ｋの行列ＰＧｘ＝［φｘ’Ｇ（１），φｘ’Ｇ（２），・・・，φｘ’Ｇ（Ｌｘ）］Ｔ，ＰＣｘ＝［φｘ’Ｃ（ｌ），φｘ’Ｃ（２），・・・，φｘ’Ｃ（Ｌｘ）］Ｔを作成し、ＴＧｘ＝ＰＧｘ×ＰＣｘ−１（ＰＣｘ−１は逆行列を意味し、ＰＣｘ×ＰＣｘ−１＝単位行列、を満たす）を計算し、ＴＧｘを当該クラスタｘでのローカルな座標空間からグローバルなそれへ変換する変換行列とし、該クラスタ内のあるノードｙに対して、そのローカルな座標位置がφｘ’Ｃ（ｙ）として与えられたときに、φｘ’Ｇ（ｙ）＝ＴＧｘ×φｘ’Ｃ（ｙ）として、そのノードのグローバルな座標位置φｘ’Ｇ（ｙ）を推定することを特徴とする通信網におけるノード間距離推定方法。
【請求項７】
請求項６に記載の通信網におけるノード間距離推定方法において、
前記一般ノード内のコンピュータは、得られたノードｉのグローバルな座標位置φ’（ｉ）を用いて、φ’（ｉ）＝［（ｆｌ_ｉ，ｆ２_ｉ，・・・，ｆｋ_ｉ］Ｔとして、ノードｉ，ｊ間の距離を√｛（ｆ１_ｉ−ｆ１_ｊ）∧２＋（ｆ２_ｉ-ｆ２_ｊ）∧２＋・・・＋（ｆｋ_ｉ-ｆｋ_ｊ）∧２｝により推定することを特徴とする通信網におけるノード間距離推定方法。
【請求項８】
請求項６または７に記載の通信網におけるノード間距離推定方法において、
前記一般ノード内のコンピュータは、得られたローカルな座標位置を用いて、同一クラスタ内の２ノード間の距離を推定することを特徴とする通信網におけるノード間距離推定方法。
【請求項９】
請求項３に記載の通信網におけるノード間距離推定方法において、
前記ランドマークノード内のコンピュータは、得られた各ランドマークノードの座標位置を用いてランドマークＬ_ｉとＬ_ｊの間の距離を請求項７に記載の方法で計算した結果をδ（Ｌ_ｉ，Ｌ_ｊ）とし、一方、ランドマークＬ_ｉとＬ_ｊの間の距離の実測値をｄ（Ｌ_ｉ，Ｌ_ｊ）とし、
【数１】
0004774559.tif 000004
で計算されるαｋをスケールパラメータとし、請求項３に記載の方法で求まる座標位置にαｋを乗ずることにより座標位置を補正することを特徴とする通信網におけるノード間距離推定方法。
【請求項１０】
自身のランドマークノードＬ_ｉと他のランドマークノードＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を測定する距離測定管理部と、
前記距離測定管理部により測定した結果を保持する座標計算・保持部と、
他のランドマークノードから距離の情報ｄ（Ｌ_ｋ，Ｌ_ｊ）を収集する距離収集部と、
前記距離収集部で収集された結果を受け取り、Ｋ個のクラスタにグループ化し、どのランドマークノードがどのクラスタに属するかを通知するクラスタ計算部と、
前記距離収集部で収集された距離情報を受け取り、それを基に、ランドマークノードＬ_ｉとＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素にもつｍ×ｍのマトリクスＤを作成し、Ｄに対して特異値分解と呼ばれる行列分解を実施して、その結果Ｄ＝Ｕ・Ｗ・ＶＴを得（Ｕ，Ｖはｍ×ｍの直交行列、Ｗは対角行列、ＶＴはＶの転置行列）た後、Ｕの最初のｋ列を抜き出して、それをグローバル座標計算用行列Ｕｋ（ｍ×ｋの行列）とし、その結果を他のランドマークノード内の座標計算・保持部に通知する座標計算用行列算出部と、
クラスタｘからＬｘ個のノードを選択し、ノードｊ（ｊ＝１，・・・，Ｌｘ）のグローバルな座標位置φｘ’Ｇ（ｊ）（ｋ×１次元のベクトル）、ローカルな座標位置φｘ’Ｃ（ｊ）（ｋ×１次元ベクトル）を各ノードに問い合わせて収集する座標位置収集部と、
前記座標収集部で収集された座標位置情報を受け取り、Ｌｘ×ｋの行列ＰＧｘ＝［φｘ’Ｇ（１），φｘ’Ｇ（２），・・・，φｘ’Ｇ（Ｌｘ）］Ｔ，ＰＣｘ＝［φｘ’Ｃ（ｌ），φｘ’Ｃ（２），・・・，φｘ’Ｃ（Ｌｘ）］Ｔを作成し（ＴＧｘ＝ＰＧｘ×ＰＣｘ−１（ＰＣｘ−１は逆行列、ＰＣｘ×ＰＣｘ−１＝単位行列、を満たす）、ＴＧｘを当該クラスタｘでのローカルな座標空間からグローバルなそれへ変換する変換行列とし、これを保持する変換行列算出部とを具備することを特徴とする通信網におけるランドマークノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットにおけるエンド・ツー・エンドの通信品質を向上させるノード間距離推定方法とその装置に関し、特に、ＩＰネットワーク上に論理的に形成されたオーバレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させることが可能な通信網におけるノード間距離推定方法およびその装置に関する。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展かつ普及してきており、昨今では、ＶｏＩＰ（Ｖｏｉｃｅ  ｏｖｅｒ  ＩＰ）やストリーミングに代表されるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）に敏感な実時間アプリケーション等の収容も急速に発展している。
【０００３】
これに伴って、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツ−・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上で、以下に述べるような問題点がある。
（１）インタ−ネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
（２）インターネットは管理主体の異なる複数のＡＳ（Ａｕｔｏｎｏｍｏｕｓ  Ｓｙｓｔｅｍ）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００４】
こうした中、下位のネットワークレイヤを変更することなく、エンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えばＬ．Ｚｈｉ  ａｎｄ  Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔ−ｗｏｒｋｓ，”ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ２００４．（非特許文献１参照）に記載の、オーバーレイネットワークによるＱｏＳ管理技術が注目されている。オーバレイネットワークとは、例えばＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェント研究報告書，第１７部，２００２．（非特許文献２参照）においても記載されているように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００５】
このようなオーバーレイネットワークによるＱｏＳ管理の基本的な概念を図１により説明する。
図１において、ノードａからノードｃに向けて通信したい場合を考える。
このとき、ａからｃへ直接転送した場合の遅延時間よりも、ａから一旦ｂへ転送し、ｂからｃへ転送するという迂回経路を経由した方が遅延時間が小さい場合がある（例えば、ＩＰネットワークでのドメイン間ルーチングポリシーなどに起因する）。このとき、オーバーレイノードａ，ｂ，ｃで形成されるオーバーレイネットワークを用いて、実践矢印で表される経路（オーバーレイノードａ→オーバーレイノードｂ→オーバーレイノードｃ）にトラヒックを迂回させることができれば、ＱｏＳを向上することができる。
【０００６】
実際に、亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．（非特許文献３参照）、Ｓ．Ｒｅｗａｓｋａｒ  ａｎｄ  Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ  ｔｈｅ  Ｓｃａｌａｂｉｌｉｔｙ  ｏｆ  Ｏｖｅｒｌａｙ  Ｒｏｕｔｉｎｇ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，”Ｐｒｏｃ．ＰＡＭ２００４．Ａｐｒｉｌ  ２００４．（非特許文献４参照）、Ｓ．Ｂａｎｅｒｊｅｅ，Ｔ．Ｇ．Ｇｒｉｆｉｎ  ａｎｄ  Ｍ．Ｐｉａｓ，“Ｔｈｅ  Ｉｎｔｅｒｄｏｍａｉｎ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ＰｌａｎｅｔＬａｂ  Ｎｏｄｅｓ，”Ｐｒｏｃ．ＰＡＭ２００４，Ａｐｒｉｌ  ２００４．（非特許文献５参照）では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。
【０００７】
しかし、このような迂回経路を見つけるためには、任意の２ノード間距離を測定する必要がある。上記非特許文献３と非特許文献５の結果は、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間の品質測定情報を用いて通信経路の計算を行うことは実現的には不可能である、という問題があった。
【０００８】
また、オーバーレイネットワークに限らず、例えばコンテンツ配信において、複数のサーバが存在するとき、距離の近いサーバを選択する、といった場合においても、ノード間の品質情報が必要になる。
【０００９】
【特許文献１】Ｌ．Ｚｈｉ  ａｎｄ  Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔ−ｗｏｒｋｓ，”ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ２００４．
【特許文献２】ＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェント研究報告書，第１７部，２００２．
【特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【特許文献４】Ｓ．Ｒｅｗａｓｋａｒ  ａｎｄ  Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ  ｔｈｅ  Ｓｃａｌａｂｉｌｉｔｙ  ｏｆ  Ｏｖｅｒｌａｙ  Ｒｏｕｔｉｎｇ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，”Ｐｒｏｃ．ＰＡＭ２００４．Ａｐｒｉｌ  ２００４．
【特許文献５】Ｓ．Ｂａｎｅｒｊｅｅ，Ｔ．Ｇ．Ｇｒｉｆｉｎ  ａｎｄ  Ｍ．Ｐｉａｓ，“Ｔｈｅ  Ｉｎｔｅｒｄｏｍａｉｎ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ＰｌａｎｅｔＬａｂ  Ｎｏｄｅｓ，”Ｐｒｏｃ．ＰＡＭ２００４，Ａｐｒｉｌ  ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述のように、オーバーレイネットワークによるＱｏＳ管理の基本的な概念では、一旦、迂回経路を経由した方が遅延時間が小さい場合がある。しかし、迂回経路を見つけるためには、任意の２ノード間距離を測定しなければならなかった。ところが、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）が低下することについては考慮されいなかった。すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間の品質測定情報を用いて通信経路の計算を行うこと等は、実現的でなかった。
【００１１】
（目的）
本発明の目的は、上述の問題点を解決し、全ての２ノード間の距離を直接測定することなく、任意の２ノード間距離を推定することが可能な通信網におけるノード間距離推定方法およびその装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明のノード間距離推定方法は、（１）インターネットに接続するＮ個のノードに対して、各ノード間の距離（ｒｏｕｎｄ  ｔｒｉｐ  ｔｉｍｅ：ＲＴＴ等）を推定するノード間距離推定方法において、各ノードを次元ｋの幾何学的な座標空間にマッピングし、かつそのグローバルな座標空間上の各ノードを予め定めたＫ個のクラスタに分割し、各ノードは自身がマッピングされたクラスタにおいてローカルな座標空間を持つ。つまり、各ノードは、グローバルな座標空間における座標位置およびローカルな座標空間における座標位置の２つを持つ。これら座標位置を用いて、任意の２ノード間の距離を推定することを特徴としている。
ここでは、インターネット上の各ノードを、仮想的な座標空間にマッピングしている。例えば、座標空間の次元を２次元とし、ノードａの座標位置が（ｘ_a,y_a )、ノードｂのそれが（ｘ_ｂ，ｙ_ｂ）とする。このように座標空間にマッピングできれば、ノード間距離はｓｑｒｔ〔（ｘ_ａ−ｘ_ｂ〕∧２＋（ｙ_ａ−ｙ_ｂ）∧２〕で計算できる。つまり、着目する２ノード間距離をその都度測定することなく、そのノードの座標位置さえ決まってしまえば、簡易に計算することが可能となる。
また、ここで、複数のクラスタに分割して、各ノードはいずれかのクラスタに所属させ、そのクラスタ内でのローカルな座標位置を併せて持つようにしている。このようにすることで、同一のクラスタに属する２ノード間の距離を推定する場合には、ローカルな座標位置を用いて距離を推定することができる。
【００１３】
本発明のノード間距離推定方法は、（２）対象とするＮ個のノードの中から、ｍ個のランドマークノードを選択し、ランドマークノードＬ_ｉとＬ_ｊの間での距離ｄ（Ｌ_ｉ,Ｌ_ｊ)を測定し、それを用いてｍ個のランドマークノードをＫ個のクラスタにグループ化する。その後、各一般ノードｉ（ランドマークノードでないノード）は各ランドマークノードＬ_ｊまでの距離ｄ（ｉ，Ｌ_ｊ)を測定し、該ノードｉは最も近いランドマークノードの属するクラスタへ所属させることを特徴としている。
ここで、ｍ個のランドマークをＫ個のクラスタに分類する方法としては、例えば典型的な統計分析手法であるＫ~ｍｅａｎｓ法などを用いればよい。
【００１４】
本発明のノード間距離推定方法は、（３）ランドマークノードＬ_iとＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素に持つｍ×ｍのマトリクスＤを作成し、Ｄに対して特異値分解（ｓｉｎｇｕｌａｒｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ：ＳＶＤ）と呼ばれる行列分解を実施し、その結果をＤ＝Ｕ・Ｗ・ＶＴとする。ここで、Ｕ，Ｖはｍ×ｍの直交行列であり、Ｗは対角行列である。また、ＶＴはＶの転置行列を意味する。次に、ランドマークノードＬ_ｉに対して、Ｌ_ｉとＬ_ｊの距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素に持つｍ×１のベクトルφ（Ｌ_ｉ）＝［ｄ（Ｌ_ｉ，Ｌ_１），ｄ（Ｌ_ｉ，Ｌ_２），・・，ｄ（Ｌ_ｉ，Ｌ_ｍ）］Ｔを作成し、一方、Ｕの最初のｋ列を抜き出して、それをＵｋとし（ｍ×ｋの行列）、φ’（Ｌ_ｉ）＝ＵｋＴ×φ（Ｌ_ｉ）で得られたｋ次元ベクトルφ’（Ｌ_ｉ）を、ランドマークノードＬ_ｉのグローバルな座標位置とすることを特徴としている。
【００１５】
本発明のノード間距離推定方法は、（４）一般ノードｉに対して、ｉとランドマークノードＬ_ｊの距離ｄ（ｉ，Ｌ_ｊ）を要素にもつｍ×１のベクトルφ’（ｉ）＝［ｄ（ｉ，Ｌ_１），ｄ（ｉ，Ｌ_２），・・・，ｄ（ｉ，Ｌ_ｍ）］Ｔを作成し、後は上記（３）の方法と同様の手順により、一般ノードｉのグローバルな座標位置を計算することを特徴としている。
【００１６】
本発明のノード間距離推定方法は、（５）あるクラスタｘに属するｍｘ個のランドマークノードＬ_{ｌ，ｘ｝，ｌ_｛２,ｘ｝，・・・，Ｌ_{ｍｘ，ｘ｝に対して、ランドマークノードＬ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の間での距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×ｍｘのマトリクスＤｘを作成し、そのＤｘに対して特異値分解を実施し、その結果をＤｘ＝Ｕｘ・Ｗｘ・ＶｘＴとする。次に、ランドマークノードＬ_｛ｉ，ｘ｝に対して、Ｌ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（Ｌ_ｉ）＝［ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛１，ｘ｝，ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛２，ｘ｝），・・・・，ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、一方、Ｕｘの最初のｋ列を抜き出して、それをＵｘｋとし（ｍｘ×ｋの行列）、φｘ’（Ｌ_ｉ）＝ＵｘｋＴ×φｘ（Ｌ_ｉ）で得られたｋ次元ベクトルφｘ’（Ｌ_ｉ）を、ランドマークノードＬ_｛ｉ，ｘ｝のクラスタｘ内でのローカルな座標位置とすることを特徴としている。
【００１７】
本発明のノード間距離推定方法は、（６）クラスタｘに属する一般ノードｉ_ｘに対して、ｉ_ｘとランドマークノードＬ_｛ｊ，ｘ｝の距離ｄ（ｉ_ｘ，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（ｉ）＝［ｄ（ｉ_ｘ，Ｌ_｛１，ｘ｝），ｄ（ｉ_ｘ，ｌ_｛２，ｘ｝，・・・・，ｄ（ｉ_ｘ，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、後は上記（５）の方法と同様の手順により、一般ノードｉ_ｘのクラスタｘでのローカルな座標位置を計算することを特徴としている。
【００１８】
本発明のノード間距離推定方法は、（７）クラスタｘからＬｘ個のノードを選択し、ノードｊ（ｊ＝１，・・・，Ｌｘ）のグローバルな座標位置をφｘ’Ｇ（ｊ）（ｋ×１次元のベクトル）、ローカルな座標位置をφｘ’Ｃ（ｊ）（ｋ×１次元のベクトル）とし、Ｌｘ×ｋの行列ＰＧｘ＝［φｘ’Ｇ（１），φｘ’Ｇ（２），・・・，φｘ’Ｇ（Ｌｘ）］Ｔ，ＰＣｘ＝［φｘ’Ｃ（ｌ），φｘ’Ｃ（２），・・・，φｘ’Ｃ（Ｌｘ）］Ｔを作成し、ＴＧｘ＝ＰＧｘ×ＰＣｘ−１（ＰＣｘ−１は逆行列を意味し、ＰＣｘ×ＰＣｘ−１＝単位行列、を満たす）を計算し、ＴＧｘを当該クラスタｘでのローカルな座標空間からグローバルなそれへ変換する変換行列とし、該クラスタ内のあるノードｙに対して、そのローカルな座標位置がφｘ’Ｃ（ｙ）として与えられたときに、φｘ’Ｇ（ｙ）＝ＴＧｘ×φｘ’Ｃ（ｙ）として、そのノードのグローバルな座標位置φｘ’Ｇ（ｙ）を推定することを特徴としている。
【００１９】
本発明のノード間距離推定方法は、（８）上記（４）または（７）の方法で得られたノードｉのグローバルな座標位置φ’（ｉ）を用いて、φ’（ｉ）＝［（ｆｌ_ｉ，ｆ２_ｉ，・・・，ｆｋ_ｉ］Ｔとして、ノードｉ，ｊ間の距離を√｛（ｆ１_ｉ−ｆ１_ｊ）∧２＋（ｆ２_ｉ-ｆ２_ｊ）∧２＋・・・＋（ｆｋ_ｉ-ｆｋ_ｊ）∧２｝により推定することを特徴としている。
【００２０】
本発明のノード間距離推定方法は、（９）上記（５）または（６）の方法で得られたローカルな座標位置を用いて、同一クラスタ内の２ノード間の距離を推定することを特徴としている。
【００２１】
本発明のノード間距離推定方法は、（１０）上記（３）の方法での各ランドマークノードの座標位置を用いてランドマークＬ_ｉとＬ_ｊの間の距離を上記（８）の方法で計算した結果をδ（Ｌ_ｉ，Ｌ_ｊ）とし、一方、ランドマークＬ_ｉとＬ_ｊの間の距離の実測値をｄ（Ｌ_ｉ，Ｌ_ｊ）とし、
【００２２】
【数１】
0004774559.tif 000002
で計算されるαｋをスケールパラメータとし、上記（３），（４）の方法で求まる座標位置にαｋを乗ずることにより座標位置を補正することを特徴としている。
【００２３】
本発明のノード間距離推定方法は、（１１）上記（１０）の方法と同じ手順に従って、あるクラスタに属するランドマークノードのみを用いてそのクラスタでのスケールパラメータを算出し、上記（５），（６）の方法の手順で求めたローカルな座標位置にそのαｋを乗ずることにより座標位置を補正することを特徴としている。
【００２４】
本発明のノード間距離推定装置は、（１２）上記（１），（２）のいずれかの方法でノードを複数のクラスタに分類する手段、上記（３）の方法でランドマークノードのグローバルな座標位置を決定する手段、上記（４）または（７）に記載の方法で、一般ノードのグローバルな座標位置を決定する手順、上記（５）または（６）の方法でローカルな座標位置を決定する手順、上記（８）または（９）の方法でノード間距離を推定する手段、上記（１０），（１１）の方法で座標位置の補正を行う手段を具備することを特徴としている。
【発明の効果】
【００２５】
本発明によれば、全てのノード間において直接距離を測定することなく、座標位置という情報のみを用いて任意の２ノード間の距離を推定することが可能となり、例えば、距離の短いノードを中継ノードとして選択することにより、ＱｏＳ向上を可能とするネットワーク管理が可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、図面を用いて本発明の実施例を詳細に説明する。
【実施例１】
【００２７】
図２は、本発明が適用されるネットワークの基本構成の一例を示す構成図である。
ここで、黒丸はランドマークノード、白丸は一般ノードである。Ｎ個のノードがこのネットワークに接続しているものとする。
ランドマークノードの選定は、このネットワークの管理者が選定してもよいし、各ノードがネットワークに接続する際に、自身がランドマークノードになるか否かを選択し、ランドマークノードになるのであれば、その旨を既に接続しているノードに通知してもよい。
【００２８】
図３は、図２におけるランドマークノードの機能構成図である。
図３に示す各装置は、いずれもコンピュータにより制御されるものである。
まず最初に、各ランドマークノードにおける距離測定管理部１１は、自身（ランドマークノードＬ_ｉ）とＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を測定し、その結果を座標計算・保持部１２で保持する。
この距離として、ノード間のｒｏｕｎｄ  ｔｒｉｐ  ｔｉｍｅを測定する（他の例としては、片道遅延や、パケット損失率を距離にマッピングしたもの（パケット損失率が大きければ、距離が大きくなるような関数を予め用意）でもよい。それを用いてｍ個のランドマークノードをＫ個のクラスタにグループ化する。Ｋ個のクラスタ化は、例えばｋ−ｍａｎｓ法と呼ばれる一般的な統計手法を用いる。クラスタの決定は、ネットワーク管理者が行ってもよいし、ランドマークノードの誰かを代表として、そこで決定してもよい。
【００２９】
図３のうち、点線で記載の部分は、例として代表のランドマークノードに付加される機能である。ここでは、距離収集部１３において、他のランドマークノードから距離の情報ｄ（Ｌ_ｋ，Ｌ_ｊ）を収集し、その結果をクラスタ計算部１４に伝えると、クラスタ計算部１４では、上述の手順でＫ個のクラスタにグループ化し、どのランドマークノードがどのクラスタに属するかを通知する。なお、図２では、３つのクラスタが存在する例を示している。
【００３０】
距離収集部１３は、収集された距離情報を座標計算用行列算出部１５に通知する。そこで、ランドマークノードＬ_ｉとＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）を要素にもつｍ×ｍのマトリクスＤを作成し、Ｄに対して特異値分解（ｓｉｎｇｕｌａｒ  ｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ：ＳＶＤ）と呼ばれる行列分解を実施し、その結果をＤ＝Ｕ・Ｗ・ＶＴとする。ここで、Ｕ，Ｖはｍ×ｍの直交行列であり、Ｗは対角行列である。また、ＶＴはＶの転置行列を意味する。次に、Ｕの最初のｋ列を抜き出して、それをグローバル座標計算用行列Ｕｋ（ｍ×ｋの行列）とする。その結果を他のランドマークノード内の座標計算・保持部１２に通知する。
【００３１】
ランドマークノードＬ_ｉでの座標計算・保持部１２は、ｍ×１のベクトルφ（Ｌ_ｉ）＝［ｄ（Ｌ_ｉ，Ｌ_１），ｄ（Ｌ_ｉ，Ｌ_２），・・・，ｄ（Ｌ_ｉ，Ｌ_ｍ）］Ｔを作成し、φ’（Ｌ_ｉ）＝ＵｋＴ×φ（Ｌ_ｉ）で得られたｋ次元ベクトルφ’（Ｌ_ｉ）を、ランドマークノードＬ_ｉのグローバルな座標位置とし、これを保持しておく。
【００３２】
上述した手順は、グローバルな座標位置を計算するまでのフローであるが、ローカルな座標位置に関しても同様である。具体的には、以下の通りである。
座標計算用行列算出部１５は、ランドマークノードＬ_ｉとＬ_ｊの間での距離ｄ（Ｌ_ｉ，Ｌ_ｊ）をクラスタ毎に分け、クラスタｘに属するｍｘ個のランドマークノードＬ_｛１，ｘ｝，Ｌ_｛２，ｘ｝，・・・，Ｌ_｛ｍｘ，ｘ｝に対して、ランドマークノードＬ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の間での距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×ｍｘのマトリクスＤｘを作成し、そのＤｘに対して特異値分解を実施し、その結果をＤｘ＝Ｕｘ・Ｗｘ・ＶｘＴとする。Ｕｘの最初のｋ列を抜き出して、それをローカル座標計算用行列Ｕｘｋとする（ｍｘ×ｋの行列）。
その結果をクラスタｘに属する他のランドマークノード内の座標計算・保持部１２に通知する。
【００３３】
ランドマークノードＬ_｛ｉ,ｘ｝での座標計算・保持部１２は、自身Ｌ_｛ｉ，ｘ｝とＬ_｛ｊ，ｘ｝の距離ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（Ｌ_ｉ）＝［ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛１，ｘ｝），ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛２，ｘ｝），・・・，ｄ（Ｌ_｛ｉ，ｘ｝，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、φｘ’（Ｌ_ｉ）＝ＵｘｋＴ×φｘ（Ｌ_ｉ）で得られたｋ次元ベクトルφｘ’（Ｌ_ｉ）を、ランドマークノードＬ_｛ｉ，ｘ｝のクラスタｘ内でのローカルな座標位置として保持しておく。
【００３４】
また、クラスタｘ内のあるランドマークノードでの座標位置収集部１６は、クラスタｘからＬｘ個のノードを選択し、ノードｊ（ｉ＝１，・・・，Ｌｘ）のグローバルな座標位置φｘ’Ｇ（ｊ）（ｋ×１次元のベクトル）、ローカルな座標位置φｘ’Ｃ（ｊ）（ｋ×１次元ベクトル）を各ノードに問い合わせて収集する。その収集された座標位置情報を、変換行列算出部１７に通知する。変換行列算出部１７は、Ｌｘ×ｋの行列ＰＧｘ＝［φｘ’Ｇ（１），φｘ’Ｇ（２），・・・，φｘ’Ｇ（Ｌｘ）］Ｔ，ＰＣｘ＝［φｘ’Ｃ（ｌ），φｘ’Ｃ（２），・・・，φｘ’Ｃ（Ｌｘ）］Ｔを作成し、ＴＧｘ＝ＰＧｘ×ＰＣｘ−１（ＰＣｘ−１は逆行列を意味し、ＰＣｘ×ＰＣｘ−１＝単位行列、を満たす）を計算し、ＴＧｘを当該クラスタｘでのローカルな座標空間からグローバルなそれへ変換する変換行列とし、これを保持しておく。
【００３５】
図４は、図２における一般ノードの機能構成図である。
図４に示す装置も、コンピュータにより制御される。
ランドマークノードでない一般ノードの振舞いについて、図４により説明する。
距離測定管理部２１は、自ノードｉから各ランドマークノードＬ_ｊまでの距離ｄ（ｉ，Ｌ_ｊ）を測定し、該ノードｉは最も近いランドマークノードに対して、そのノードの属するクラスタへ所属する旨を通知する。
クラスタｘに属する一般ノードｉ_ｘでの座標計算・保持部は、自身ｉ_ｘとランドマークノードＬ_｛ｊ，ｘ｝の距離ｄ（ｉ_ｘ，Ｌ_｛ｊ，ｘ｝）を要素にもつｍｘ×１のベクトルφｘ（ｉ）＝［ｄ（ｉ_ｘ，Ｌ_｛１，ｘ｝），ｄ（ｉ_ｘ，Ｌ_｛２，ｘ｝），・・・，ｄ（ｉ_ｘ，Ｌ_｛ｍｘ，ｘ｝）］Ｔを作成し、一方、ランドマークノードからローカル座標計算用行列Ｕｘｋを受信し、φｘ’（ｉ）＝ＵｘｋＴ×φｘ（ｉ）で得られたｋ次元ベクトルφｘ’（ｉ）を、クラスタｘ内でのローカルな座標位置として、保持しておく。
【００３６】
グローバル座標計算・保持部２４は、ランドマークノード内の変換行列計算部１７にて保持されている変換行列ＴＧｘを受け取り、自身ｉ_ｘのローカルな座標位置をφｘ’Ｃ（ｉ_ｘ）をローカル座標計算・保持部２２から読み出し、φｘ’Ｇ（ｉ_ｘ）＝ＴＧｘ×φｘ’Ｃ（ｉ_ｘ）という計算を行い、それをノードのグローバルな座標位置として保持しておく。
距離推定部２３は、距離を推定したい相手のノードｊからグローバルな座標位置を通知してもらい、自身ｉのグローバルな座標位置をφ’（ｉ）＝［ｆｌ_ｉ，ｆ２_ｉ，・・・，ｆｋ_ｉ］Ｔとして、ノードｉ，ｊ間の距離を√｛（ｆ１_ｉ-ｆ１_ｊ）∧２＋（ｆ２_ｉ-ｆ２_ｊ）∧２＋・・・＋（ｆｋ_ｉ-ｆｋ_ｊ）∧２｝により推定する。
あるいは、相手が同一クラスタ内であれば、相手のローカルな座標位置を通知してもらい、２ノード間の距離を推定する。
【実施例２】
【００３７】
実施例１では、変換行列ＴＧｘを用いてグローバルな座標位置を計算していたが、実施例２ではその代わりに、自身をノードｉとして、ｉとランドマークノードＬ_ｉの距離ｄ（ｉ，Ｌ_ｊ）を要素にもつｍ×１のベクトルφ（ｉ）＝［ｄ（ｉ，Ｌ_ｉ），ｄ（ｉ，Ｌ_２），・・・，ｄ（ｉ，Ｌ_ｍ）］Ｔを作成し、後は、実施例１（請求項３）と同様の手順により、一般ノードｉのグローバルな座標位置を計算する。
【実施例３】
【００３８】
実施例１の座標計算・保持部１２において、ノードの座標位置を計算していたが、その座標位置に対して、以下で計算されるスケールパラメータαｋを乗じて補正する。
まず、各ランドマークノードの座標位置を用いてランドマークＬ_ｉとＬ_ｊの間の距離を推定した結果、δ（Ｌ_ｉ，Ｌ_ｊ）とし、一方、ランドマークＬ_ｉとＬ_ｊの間の距離の実測値をｄ（Ｌ_ｉ，Ｌ_ｊ）とし、
【００３９】
【数２】
0004774559.tif 000003
で計算されるαｋをスケールパラメータとする。
【００４０】
また、あるクラスタに属するランドマークノードのみを用いて、そのクラスタでのスケールパラメータを算出し、実施例１の手順でローカルな座標位置を計算した結果に、そのαｋを乗ずることにより、推定量を補正する。
【図面の簡単な説明】
【００４１】
【図１】オーバレイネットワークによる経路制御の概念を説明する図である。
【図２】本発明が適用されるネットワークの基本構成の一例を示す構成図である。
【図３】図２におけるランドマークノードの構成例を示すブロック図である。
【図４】図２における一般ノードの構成例を示すブロック図である。
【符号の説明】
【００４２】
１１  距離測定管理部
１２  座標計算・保持部
１３  距離収集部
１４  クラスタ計算部
１５  座標計算用行列算出部
１６  座標位置収集部
１７  変換行列算出部
２１  距離測定管理部
２２  ローカル座標計算・保持部
２３  距離推定部
２４  グローバル座標計算・保持部
【図１】
0004774559.tif 000005
【図２】
0004774559.tif 000006
【図３】
0004774559.tif 000007
【図４】
0004774559.tif 000008