(57)【要約】  本発明は経路選択にリンクメトリックを用いるルーティング機構を以下のように拡張する。全てのリンクに対するリンクメトリック相互相関ベクトルであって、当該ベクトルの各要素が他の何らかのリンクに対応するとともに、データフローが既にこの他のリンクを用いているとした場合のリンクメトリックにおける変化を反映するリンクメトリック相互相関ベクトルが求められる。本発明はさらに、全ての相互相関を有するリンクが互いに隣接する、すなわちそれらリンクが１つの共通したノードを終点又は起点とする特定の実施形態についても説明している。拡張ルーティンググラフを生成するための仕組みについても記載している。この拡張グラフは、（最短パスアルゴリズムのような）最適経路の構築及び最適経路メトリックの探索を同時に行う標準的な多項式時間アルゴリズムを、隣接するリンクが相互相関を有する場合に対しても利用可能とする。
2008544688.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワーク内のデータ伝送フローのための経路を選択する方法であって、送信者から受信者への、少なくとも、少なくとも第１のリンクを有する第１の経路とに対する合成経路メトリックと少なくとも第２のリンクを有する第２の経路とに対する合成経路メトリックとを比較するステップと、前記第１の経路及び前記第２の経路に対する前記経路メトリックは、前記少なくとも第１のリンク及び前記少なくとも第２リンクのリンクメトリックにそれぞれ基づき、前記少なくとも１つのリンクのリンクメトリック値を、前記ネットワーク内の少なくとも１つの他のリンクのリンクメトリックの相関に基づいて決定するステップを有することを特徴とする方法。
【請求項２】
前記第１のリンクの前記リンクメトリック値を、あるデータフローが前記ネットワーク内の他のリンクを既に用いているとした場合に当該リンクメトリック値に生じるであろう変化を表す相互相関値に基づいて求めるステップをさらに有することを特徴とする請求項１記載の方法。
【請求項３】
前記経路が少なくとも２つのリンクを有し、前記他のリンクが前記少なくとも１つのリンクと同じ経路に含まれることを特徴とする請求項１又は請求項２記載の方法。
【請求項４】
前記リンクメトリック値が、リンクメトリック相互相関ベクトルに基づいて算出され、前記リンクメトリック相互相関ベクトルは、前記少なくとも１つのリンクについて他のリンクに対応する相互相関値を有すると共に、データフローが既に前記他のリンクを用いているとした場合に前記少なくとも１つのリンクに対する前記リンクメトリック値に生じるであろう変化を反映することを特徴とする請求項１乃至請求項３のいずれか１項に記載の方法。
【請求項５】
前記リンクメトリック値が、相関及び／又は情報が存在するものに対する組（ｂ，σba）からなる値の集合に基づいて算出され、ここで、ｂは別のリンクであり、（σba）はデータフローが既に前記他のリンクを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１乃至請求項３のいずれか１項に記載の方法。
【請求項６】
前記リンクメトリック値が、関数ｍa￣＝ｆa（ｍa，σpa）に従って算出され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項４又は請求項５に記載の方法。
【請求項７】
前記リンクメトリック値が、以下の関数
2008544688.tif 000013
に従って算出され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、Ｐは考慮すべき全リンクの集合、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項４又は請求項５に記載の方法
【請求項８】
前記少なくとも１つのリンクの前記リンクメトリック値を、データフローが前記第１のリンクを既に用いているとした場合に前記リンクメトリック値に生じるであろう変化に基づいて算出するステップをさらに有することを特徴とする請求項１乃至請求項７のいずれか１項に記載の方法。
【請求項９】
− 元のリンクメトリックｍaと、標準的なｋ−最短パス構築法を用いて、所定数ｋの最短パスを探索するステップと、
− 前記ｋの最短パスを集合Ｐに含めるステップ、
とにより、可能性のあるパスの集合Ｐを決定するステップをさらに有することを特徴とする請求項１乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
前記相互相関値が、複数のリンクが互いにどのように影響するかについての知見に基づいて求められることを特徴とする請求項３乃至請求項９のいずれか１項に記載の方法。
【請求項１１】
前記相互相関値が、複数のリンクメトリックがどのように相関するのかの経時的な監視に基づいて求められることを特徴とする請求項３乃至請求項９のいずれか１項に記載の方法。
【請求項１２】
補正された相互相関値σba(new)を以下の式
2008544688.tif 000014
（ここで、ｇおよびｈは関数であり、αbaは前記他のリンクが前記第１のリンクに与えるであろう影響を表す重み係数であり、ｍaは現在のリンクメトリック値であり、ｍ’aはフローがパスを用いる場合の前記リンクメトリック値である）によって算出するステップをさらに有することを特徴とする請求項１乃至請求項１１のいずれか１項に記載の方法。
【請求項１３】
− 仮想ノード及び仮想リンクを導入して拡張ルーティンググラフを生成するステップと、
− 標準的な最短パスアルゴリズムをルーティンググラフに適用して最短パスを決定するステップと、
− 仮想ノードの各々を対応するノードと置き換えると共に、仮想リンクの各々を対応するリンクと置き換えることにより、経路を抽出するステップと、
− 前記拡張ルーティンググラフにおける経路メトリックを用いて、前記経路メトリックを抽出するステップとをさらに有することを特徴とする請求項１記載の方法。
【請求項１４】
電気通信ネットワークで用いるためのノード(S,R,I)であり、当該ノードから開始する第１のリンクに対するリンクメトリックを求めるために必要とされるリンク特性を制御及び／又は監視するように構成されたリンクメトリック関数部（ＬＭＦ）を備えるノードであって、前記リンクメトリック関数部は、前記第１のリンクのリンクメトリック値を、データフローが前記ネットワーク内の他のリンクを既に用いているとした場合に前記第１のリンクの前記リンクメトリックに生じるであろう変化を表す相互相関値に基づいて算出する様に構成されることを特徴とするノード。
【請求項１５】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、リンクメトリック相互相関ベクトルに基づいて算出するように構成されており、前記リンクメトリック相互相関ベクトルは、前記少なくとも１つのリンクについて他のリンクに対応する相互相関値を有すると共に、データフローが既に前記他のリンクを用いているとした場合に前記少なくとも１つのリンクに対する前記リンクメトリック値に生じるであろう変化を反映することを特徴とする請求項１４記載のノード。
【請求項１６】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、相関及び／又は情報が存在するものに対する組（ｂ，σba）からなる値の集合に基づいて算出するように構成されており、ｂは別のリンクであり、（σba）はデータフローが既に前記他のリンクを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１５記載のノード。
【請求項１７】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、関数ｍa￣＝ｆa（ｍa，σpa）に従って算出するように構成されており、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１５又は請求項１６に記載のノード。
【請求項１８】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、以下の関数
2008544688.tif 000015
に従って算出するように構成され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、Ｐは考慮すべき全リンクの集合、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１５又は請求項１６に記載のノード。
【請求項１９】
前記リンクメトリック関数部（ＬＭＦ）が、前記少なくとも１つのリンクの前記リンクメトリック値を、データフローが前記第１のリンクを既に用いているとした場合に前記リンクメトリック値に生じるであろう変化に基づいて算出するように構成されることを特徴とする請求項１４乃至請求項１８のいずれか１項に記載のノード。
【請求項２０】
− 元のリンクメトリックｍaと、標準的なｋ−最短パス構築法を用いて、所定数ｋの最短パスを探索するステップと、
− 前記ｋの最短パスを集合Ｐに含めるステップ、
とにより、可能性のあるパスの集合Ｐを決定する手段(7)をさらに有することを特徴とする請求項１４乃至請求項１９のいずれか１項に記載のノード。
【請求項２１】
前記リンクメトリック関数部が、複数のリンクが互いにどのように影響するかについての知見に基づいて求められた相互相関値を用いるように構成されることを特徴とする請求項１５乃至請求項２０のいずれか１項に記載のノード。
【請求項２２】
前記リンクメトリック関数部が、複数のリンクメトリックがどのように相関するのかの経時的な監視に基づいて求められた相互相関値を用いるように構成されることを特徴とする請求項１５乃至請求項２１のいずれか１項に記載のノード。
【請求項２３】
補正された相互相関値σba(new)を以下の式
2008544688.tif 000016
（ここで、ｇおよびｈは関数であり、αbaは前記他のリンクが前記第１のリンクに与えるであろう影響を表す重み係数であり、ｍaは現在のリンクメトリック値であり、ｍ’aはフローがパスを用いる場合の前記リンクメトリック値である）によって算出する手段(９)をさらに有することを特徴とする請求項１４乃至請求項２２のいずれか１項に記載のノード。
【請求項２４】
前記リンクメトリック関数部（ＬＭＦ）が、
− 仮想ノード及び仮想リンクを導入して拡張ルーティンググラフを生成し、
− 標準的な最短パスアルゴリズムをルーティンググラフに適用して最短パスを決定し、
経路及び経路メトリックを、
− 仮想ノードの各々を対応するノードと置き換えると共に、仮想リンクの各々を対応するリンクと置き換え、
− 前記拡張ルーティンググラフにおける経路メトリックを前記経路メトリックとして得ることにより抽出する、
ように構成されることを特徴とする請求項１４記載のノード。
【請求項２５】
請求項１４乃至請求項２４のいずれか１項に記載のノード(S,R,I)を少なくとも１つ有する通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は請求項１のプリアンブルに規定されるようなトラフィックをルーティングする方法および、請求項１４のプリアンブルに規定されるようなノードに関する。
【背景技術】
【０００２】
本発明は送信者から受信者へ、複数の中間ネットワークノードを介してデータを伝送可能な通信ネットワークに適用される。データは、通常１つ又は複数の中間ネットワークノードを有する様々な経路を介して伝送されうる。隣接する２ノード間の直接パスをリンクと呼ぶ。どの通信リンクが通信フローに用いられるかに応じて、送信者から受信者への、ネットワークを通じた様々な伝送経路（又はパス）を区別することができる。
【０００３】
そのような通信システムにおいては、可能な限り効率的にリソースを用いるため、経路の選択を最適化することが重要である。
【０００４】
既存の経路解決法において、経路選択は通常、各通信ルートにコスト値又はメトリック、すなわち経路メトリックを割り当てることに基づいている。経路メトリックは一般にはその経路中の全リンク又はホップに対するメトリック値の合計として求められる。リンクメトリック値は、ある種の性能目標に関して、ある特定のリンクの「品質」又は有用性を反映させるために良く用いられる。典型的には（必ずしもそうであるとは限らないが）、各ノードは自身のリンクインタフェースに対するリンクメトリック値を求め、この値をルーティングプロコルを用いて他のノードへ配信する。典型的には、最良の経路メトリックを有するような経路が最良の経路として選択される。
上述したように、従来技術において、各リンクは独立したものと見なされている。他のリンクにおけるリンク変更によって生じうる影響については考慮されていない。
【０００５】
あるリンクの「品質」又は有用性は、他のリンクで何が起きたかによって影響されうる。このような状態は例えば、例えば様々なホップ上の伝送に用いられる同一のＣＳＭＡ媒体のように、結合コンテンションを用いて同じ媒体又はチャネルを共用する複数のリンクに対して、例えば、異なる無線アクセス技術が同一又は隣接するスペクトルを用いるような、互いに干渉しあう異なった複数のチャネル上で伝送する複数のリンクに対して、例えば、複数のリンクが同一ノード内にあり、共通するＤＳＰ、ＲＡＭ資源を用いる場合のように、共通する処理能力、メモリ又は他の共用リソースを用いる複数のリンクの伝送について起こりうる。
【０００６】
多周波数(multi-radio)マルチホップネットワークにおいては、複数の通信ノード間に複数の異なるリンクが存在するのが通常であり、これら複数のリンクは異なる無線アクセス技術又はチャネルを用いている。そのような状況において、個々のリンクメトリックに基づく経路メトリックのみが考慮される経路決定では、あるルートにおける様々なリンクの干渉による影響が考慮されていないため、最適な結果が得られない。
【０００７】
発明の目的
本発明の一目的は、ネットワークを通じたルーティングを改善することにより、ネットワークリソースのより効率的な利用を可能にすることにある。
【発明の開示】
【０００８】
上述の目的は、冒頭に規定したように、請求項１の特徴的な構成をそれぞれ有する方法によって達成される。上述の目的はまた、冒頭に指定したように、請求項１４に記載される特徴的な構成をそれぞれ有するノードによっても達成される。
【０００９】
本発明の下地となる基本的なアイデアは、データトラフィックに対して新たな経路を決定する際、リンクメトリックに、既存のリンクおよび潜在的に生じうるリンク間の相互作用(interaction)および結合(coupling)を反映させることである。本発明はルーティング決定を改良することにより、通信ネットワークの性能、サービス品質サポートおよび容量を改善する。
【００１０】
簡潔に言えば、リンク間の結合は、送信機と意図的でない受信機との間の伝送電力レベルおよびパスゲインを含む物理層に関連するが、何よりも、（例えば処理能力又はメモリにおける）リソース共有制限およびリンク上のトラフィック負荷に関連する。特には、本発明の一実施形態として、リンクメトリック相互作用の線型モデルが提案される。線型モデル（一次近似）は問題を単純化するとともに、予期される相互作用の変化がリンクメトリック値と比較して相対的に小さい場合には正確である。これは通常、相互作用要因においてトラフィック負荷が支配的である場合に当てはまる。
【００１１】
本発明は、経路選択にリンクメトリックを用いるルーティングの仕組みを、以下のように拡張する。リンクメトリック相互相関ベクトルを各リンクａに対して求め、このベクトルの１要素は、別のリンクｂに対応し、あるデータフローがこの別のリンクｂを既に使っていたとした場合のリンクメトリック値の変化を反映する。
【００１２】
ある特定の実施形態において、相互相関を有する全てのリンク（相互相関ベクトルに０でない値を有するリンク）が互いに隣接する。すなわち、それらのリンクは、１つの共通ノードで終端するか、１つの共通ノードから開始する。
【００１３】
拡張ルーティンググラフを生成するための仕組みについて説明する。この拡張グラフは、最適経路の構築および最適な経路メトリックの探索を同時に行う標準的な（最短パスアルゴリズムのような）多項式時間アルゴリズムを、隣接リンクが相互相関を有する場合についても利用することを可能にする。
【００１４】
このアイデアは、主に、経路設定前に各リンクが付随するリンクメトリックを有し、メトリックが既存かつアクティブなリンク間の結合を反映するようなルーティング機構の拡張を通じて実現されることが好ましい。
【００１５】
経路設定において、経路メトリックを最小化する経路が選択され、この経路メトリックは前記経路に沿った新たな更新されたリンクメトリックからなるとともに、新たな更新されたリンクメトリックは、古いリンクメトリックおよびリンク間の結合に基づいている。
【００１６】
具体的には、メトリック値に加え、リンクメトリック相互相関ベクトルが各リンクａに対して決定される。このベクトルの各要素は、何らかの他のリンクｂに対応する。これは、あるデータフローに対して選択された経路がリンクｂも用いたとした場合に、リンクメトリック値がどう変化するかの指標(measure)である。
【００１７】
経路選択機構は、リンクメトリック相互相関ベクトルを、例えば２つ又はそれより多い連続するリンクの先行又は後続ホップにおけるデータフローの存在が、中間のホップのリンクメトリックに望ましくない影響を与えるようなパスを避けるために用いることができる。
【００１８】
当業者は容易に理解するであろうが、本発明はルーティングが行われる(routed)任意の通信ネットワークに対して適用可能である。しかしながら、本発明は異種のリンク技術（例えば無線アクセス技術）を用いる無線マルチホップネットワークにおいて特に有用である。同一ノードペア間で２つの異なるリンク技術が利用可能であるとすると、本発明によればそれらは別々のリンクメトリック並びにリンクメトリック相互相関ベクトルを有する別個のリンクとして取り扱われる。
【００１９】
この手法は、同時係属中の出願PCT/SE2005/000948に記載されるような、あるパスへの新しいトラフィックフローの許可「後」の予測メトリックが経路決定において考慮される予測ルーティングアルゴリズムと組み合わせた場合に特に有用であることに留意されたい。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態を、添付図面を参照してより詳細に説明する。
本発明は、各リンクａに対し、リンクメトリックｍaに加えてリンクメトリック相互相関ベクトルσaを導入することにより、リンクメトリックに基づくルーティング機構を拡張する。所与のデータフローに対するルーティング問題を検討する。ベクトル中の各成分σbaは、フローに対して選択された経路がリンクｂも用いたとした場合に、リンクａ上のリンクメトリック値ｍaがどのように変化するかの指標である。σaの何らかの成分は０であってもよいことに留意されたい。これは、対応するリンクメトリックがｍaと無相関であるか、相関情報が入手できないことを意味する。実際にはσaは、集合として実装されても良く、その場合、相関を有するおよび／又は情報が存在するものについての要素は（ｂ，σba）の複数組である。自己相関σaaは、データフローがそのリンクを用いた際に、リンクメトリック値に自身が引き起こす変化である。
【００２１】
相関補正されたリンクおよび経路メトリックの推定
リンクメトリック相互相関ベクトルσaは、経路メトリックの計算およびパス評価の際、経路選択機構によって用いることができる。機構は、所与のパスｐ∈Ｐ（Ｐは候補パスの集合）について、相関補正された(correlation-corrected)リンクメトリックの推定値ｍa￣を、リンクメトリックｍおよび相互相関ベクトルσの関数ｆとして以下のように計算することができる。
【００２２】
2008544688.tif 000003
【００２３】
ｐ内の全リンクａについて、σpl＝（σa1l，．．．，σa|p|l）は、σaにおいてパスｐ内のリンクｂ1，．．．，ｂ|p|に対応する要素である。これにより、相関補正された経路メトリックの推定値は、必要に応じて、例えばリンクメトリックｍa￣の合計として算出することができる。
【００２４】
実際には、リンクメトリック相互作用について、線型モデル（一次近似）を用いることができる。そして、相関補正されたリンクメトリックの推定値は、ｐ内のリンクのリンクメトリックおよび相互相関値の合計として算出することができる。
【００２５】
2008544688.tif 000004
【００２６】
経路の構築
上に概要を述べた算出手法は、候補パスｐの集合Ｐが先ず形成され、その後、ｐ∈Ｐである各パスｐの相関補正された経路メトリックが評価されることを仮定している。各リンクは多くの可能性のある相関補正されたリンクメトリック値の推定値（候補パス当たり最大１つ）を有しうること、選択すべき正しい１つはパスが選択されるまで決定されないことから、この仮定は一般に必要である。しかしながら、パスの数はノード／リンクの数に従って指数関数的に増加するため、通常、ネットワーク内における全ての可能性のある候補パスを列挙することは実現不能である。
【００２７】
以下、候補パスの集合Ｐにどのパスを含めるべきかを、どのように決定するかについて説明する。
【００２８】
Ｐを決定するための１つの現実的な方法は、
１．全てのリンクａにおけるリンクメトリック相互相関ベクトルσaを無視し、従前のリンクメトリックｍaのみを用いる。
２．ｋ−パス経路構築方法、例えばｋ−最短パスアルゴリズムを、リンクメトリックｍaに関して、ｋ最短パス（最短、２番目に最短、・・・、ｋ番目に最短まで）を見出すために用いる（例えばEppstein [1]を参照）。
３．そして、見つかったｋのパスをＰとする。
というものである。
【００２９】
この方法は、相関補正されたリンクメトリックｍa￣に関して最適なパスを見出せないだろうが、候補パスの数ｋが小さければ実際上効果的であろう。
【００３０】
いくつかの場合には、徹底的な列挙に訴えることなく、ｍa￣に関して最適なパスを直接計算可能である。そのような場合の１つは、リンクメトリックが隣接する複数のリンクのメトリックとの相互相関のみを有する場合、すなわち、複数のリンクが１つの共通ノードを共用する場合である。この特定の場合について、以下に説明する。
【００３１】
複数のリンクメトリックが他の任意のリンクメトリックと相関を持ちうる一般的な場合には、おそらくは集中型のルーティング機能が必要となる。隣接リンクメトリック相互相関のみの場合については、標準的な組み合わせ経路構築アルゴリズムを用いることができる。これは、各ノードが、リンク情報を伝播するルーティングプロトコルからネットワークビューを取得する、集中的でない動作を少なくとも可能にする。ここで、リンクメトリック相関ベクトルσaは、任意の既存ルーティングプロトコルによって伝播される、従前のリンクメトリック値ｍaを含むリンク情報上に載せることが可能である。
【００３２】
相互相関値の決定
様々な方法によって相関ベクトルσaを求めることができる。
- なんらかの中央エンティティ(central entity)で終端される（あるいは何らかの形で制御される）リンクａに対しては、例えばスケジュールされるべき（タイムスロット、周波数、符号、等といった）リソース、電力レベル等についての詳細な知見に基づいて、相関を適正に抽出することができる。
- 集中的な方法で制御されないリンクａ（別々のノードへの／からのリンク）であって、周波数／範囲／時間における重複によって依然として干渉するリンクに対しては、例えばリンクメトリックがどのように相関の影響を受けるかを経時的に監視することによってメトリックの補正の決定を行うことができる。
【００３３】
後者の場合、ルーティング前後のリンクメトリックを監視することにより実現可能である。p上の１リンクａを想定する。パスｐ上のフローのルーティング前後のリンクａのメトリック値をｍaおよびｍ’aとする。このリンクのリンクメトリックがｐ内の他の複数のリンクｂのリンクメトリックとどのように相関するかについてのアプリオリな知見なしには、どの（１つ以上の）リンクが、ｍaからｍ’aへの変化を引き起こすか及び、このルーティングがどのくらいの平均相互相関の振る舞いを呈するかを判定することは困難である。一般に、更新された相互相関値の推定値は、以下のように表すことができる。
【００３４】
2008544688.tif 000005
【００３５】
ここで、ｇ及びｈは何らかの関数であり、αbaはリンクｂに対して起こりうる影響を表す重み係数である。重み係数は、地理的に近接した複数のリンクは相関するリンクメトリックを有する可能性がより高いと考えられる場合には、例えば地理的な距離を表すことができる。関数ｈは単にリンクメトリック間の差であってよく、関数ｇは重み付けされた結合又は何らかの移動平均であってよい。
【００３６】
相関ベクトルσaに関する問題は、それらがリンクメトリックｍaに依存すること、すなわち、経路決定中に多数のパスについて経路が変更された場合、相関値もまた変化するであろうことである。相関値がどのように変化するかは、それらが絶対的なリンクメトリックに対して自明でない（非線形な）関係を有しうるため、推定が困難かもしれない。そのため、いくつかの場合においては監視に基づいてもよい。これは、１つの経路決定において考慮可能なパスの総数には実際的な限度が存在しうることを意味する。
【００３７】
リンクメトリックと相互相関ベクトルとの依存関係を処理する１つの手法としては、方法を、上述した同時係属中の出願に記載されるような、あるパスへの新たなトラフィックフローが許可された「後」の予測メトリックが経路決定において考慮される予測ルーティングアルゴリズムと組み合わせることである。本発明の用語において、予測ルーティングアルゴリズムは、自己相関σaaの推定と見なすことができる。組み合わせられた方法は、当然ながら、予測をσaの全要素に拡張する。
【００３８】
図１は、通信ネットワークを通じた複数の可能性のある経路を介した、送信者Ｓから受信者Ｒへのデータ伝送を模式的に示す図である。ネットワークは複数の中間ノードＩを有し、中間ノードＩを通じてデータをルーティングすることができる。図１において、５つの異なる経路１，２，３，４，５が示されている。通常各ノードは、自身を起点とするリンクに対するリンクメトリックを求めるために必要なリンク特性を制御及び／又は監視するリンクメトリック関数部ＬＭＦを有している。図１に点線で示すように、各ノードについてのリンクメトリックは、他のノードのリンクメトリック関数部へ通信される。ノードがリンクメトリック関数部を持たない場合、そのノードについてのリンクメトリックは別のノードによって求められ得る。
【００３９】
ノードＩ，Ｓ，Ｒの１つ以上は、上述したように可能性のあるパスの集合を決定するパス決定部７を更に有してもよい。加えて、１つ以上のノードＩは、上述したように相互相関値を更新するための相互相関値決定部９を備えることができる。図１においては、図を簡潔にするため、これらの構成７，９は、ノードＩの１つにのみ示している。あるいは、パス決定部７及び相互相関値決定部９の機能を、リンクメトリック関数部ＬＭＦで実行してもよい。ＬＭＦもまた、求められたパス及び相互相関情報を、ネットワーク内の他のノードへ通信する。
【００４０】
図２Ａ、２Ｂ及び２Ｃは、リンクメトリック相互相関ベクトルが、経路決定をどのようにして改善可能であるのかを説明する図である。図２Ａ、２Ｂ及び２Ｃのそれぞれは、３つのノード１，２，３のネットワークを示しており、各ノードは２つの異なるリンク技術Ａ，Ｂを利用可能である。ノード１から３へのあるデータフローに対する経路選択が行われるものとする。４つの「自然な」単独パスが候補として考慮される。ルーティング機構は、経路選択にリンクメトリックを用いる。
【００４１】
４つのリンクについての、経路決定「前」のリンクメトリック値を表１に示す。Ａ１２はノード１からノード２への技術Ａを用いるパスを、Ａ２３はノード２からノード３への技術Ａを用いるパスを、Ｂ１２はノード１からノード２への技術Ｂを用いるパスを、Ｂ２３はノード２からノード３への技術Ｂを用いるパスをそれぞれ表している。
【００４２】
2008544688.tif 000006
【００４３】
図２Ａの点線は、これらのリンクメトリックに基づいて決定された最良経路｛Ｂ１２，Ｂ２３｝を示している。本例において、リンクメトリックの合計が最小となる経路としてこの経路が選択されている。
【００４４】
図２Ｂ及び表２は、経路決定後の状況、即ち、点線で示される経路｛Ｂ１２，Ｂ２３｝が選択され、データフローに対して用いられたとした場合の状況を示している。
【００４５】
2008544688.tif 000007
【００４６】
表２から分かるように、本例において、経路選択の結果として、２つのリンクＢ１２及びＢ２３に対するリンクメトリック値が（Ｂ２３については顕著に）増加している。この増加の理由は、リンクの１つがルーティングによって大きな負荷を受けるようになったからでも、この経路中で同じリンク技術を用いる２つのホップがリソースを共有しなければならないか、互いに干渉しあっているからでもよい。結局のところ、選択された経路は、可能な限り最適なものとはならなかったことになる。
【００４７】
図２Ｃ及び表３において、リンクメトリックはリンクメトリック相互相関ベクトルによって補完されており、２つのパス｛Ｂ１２，Ａ２３｝及び｛Ｂ１２，Ｂ２３｝に対するリンクメトリックが調整されている。第１のパスにおいて選択されたリンクに関する調整済リンクメトリックは、以下の式に従って計算される（同様にして、第２のパスについての調整済リンクメトリックも計算される）。
【００４８】
2008544688.tif 000008
【００４９】
2008544688.tif 000009
【００５０】
ルーティング機構は、今や、経路パスを決定するためにリンクメトリック相互相関ベクトルを用いることが可能である。本例においては相関補正されたリンクメトリックの推定値の最小合計値を有する経路として選択された最良経路を再び点線で示す。
【００５１】
実際のリンクメトリック合計が5.1から3.7に削減されているため、パス｛Ｂ１２，Ａ２３｝は、（経路メトリックという観点からすれば）｛Ｂ１２，Ｂ２３｝よりも明らかによい。
【００５２】
図３は、送信者Ｓ１と受信者Ｒ１との間のルーティングの別の例における、本発明によるルーティングを説明する図である。それぞれが２つのリンク、ａ及びｂ（ノード２経由）と、ｃ及びｄ（ノード３経由）とからなる２つのパスが可能である。本例においては、各リンクの容量ｃが６単位であり、現在は全リンクにおいてｆ＝３単位が用いられているものとする（整数単位のみが使用可能であるとする）。リンクメトリックは各リンクの残り容量に反比例するものとする。すなわち、現在の各リンクメトリック値は以下のように表すことができる。
【００５３】
2008544688.tif 000010
【００５４】
これは、ノードＳ１からノードＲ１への２つのパスが（このメトリック下においては）同等に良好であること、またそれらが等しい確率で当面のルーティングに用いられることを示唆している。なお、これは、ｆ＝ｃである場合を考慮していない単純化された式であることに留意されたい。実際には、ｆ＝ｃである場合には、ｍを何らかの（大きな）数とするか、式中の容量ｃを例えばｃ’＝ｃ＋ε（εは小さな数）で置換することで対処することになるだろう。
【００５５】
ここで、リンクａ及びｂが同一のリンク技術を用い、かつタイムスロットを共用しなければならないものとする（リンクｃ及びｄは異なるリンク技術を用い、相関するリンクメトリックを有さないものとする）。さらに、ノード２は受信と送信を同時には行えないものとする。これにより、タイムスロットがリンクａ及びリンクｂの両方で利用可能な場合が生じるが、タイムスロットを一緒に利用することはできない。そのような状況の１つを、リンクａ及びｂの隣の箱の集合によって示す。ここで、箱の各々はタイムスロットであり、影の付いた箱は占有されたスロットである。２つのリンクは利用可能な空きタイムスロットを有するが、同時送受信の制約から、ａ及びｂにおける空きスロットの結合を実行することはできない。このような状況が、平均して１００のルーティング毎に発生するものと仮定する。
【００５６】
経路決定を改善するため、リンクメトリック相互相関ベクトルを用いることができるが、問題はどうやって相互相関値σba及びσabを選択するかである。この場合のリンクメトリックを、仮にｍ＝２ｃ＝１２とすることにより、この競合シナリオを測定(measure)できるものとする。さらに、平均負荷ｆが３単位であるとする。この場合、予期されるメトリックは以下の通りである。
【００５７】
2008544688.tif 000011
【００５８】
追加のリンクメトリック相互相関値が用いられるとすると、この場合の合理的な推定値は、σba＝σab＝0.1/2＝0.05と設定することができる。これは等しい負荷状況下において、ｃおよびｄ上のパスを優先させることにはなるだろうが、ａ及びｂ上のパスの利用に完全に取って代わるものではない。
【００５９】
隣接リンク相互相関−拡張ルーティンググラフ
本発明に固有で、かつ良くある場合は、相互相関のある全てのリンクが隣接する場合、即ち、所与のリンクａ＝(i,j)について、σba≠０のリンクｂが全てノードｉで終端されるか、ノードｊから開始する（ｂが他の何らかのノードｋに対し、ｂ＝(k,i)又はｂ＝(j,k)である）場合である。
【００６０】
単独パスの経路が用いられ、かつ経路メトリックが（最短パスアルゴリズムのような）最適経路の構築と最適経路メトリックの探索とを同時に行う多項式時間アルゴリズムを認めるとすると、これらのアルゴリズムを隣接リンクが相互相関を有する場合の最適パス探索にも用いることができる。
【００６１】
各リンクが多数の可能性のある推定リンクメトリック値（候補パス当たり最大１つの値）を有しうるため、一般にはこれで簡単にリンクメトリック相互相関ベクトルを用いることができるということにはならない。最適経路を構築し、また最適経路メトリックを計算するには、各リンクに対して用いるべき正しいメトリックを見つけ出すための方法が必要である。隣接リンクが相互相関を有する場合については、以下の手順を利用可能である。
【００６２】
考え方としては、まず拡張ルーティンググラフを生成し、次にこのグラフにおける最短パスを算出し、最後に元のグラフにおける経路及び経路メトリックを得る、というものである。ここで、リンクには方向づけがなされており（即ち、(i,j)と(j,i)とは異なる）、メトリック及び推定メトリックの全ては、負でないものと仮定されていることに留意されたい。さらに、同一の起点及び宛先ノード間において、２つの異なるリンク技術（例えば無線アクセス技術）が利用可能である場合、それらは別個のリンクとして取り扱われる。
【００６３】
拡張ルーティンググラフは各ノードを、ノードがフローに関して有することのできる様々な役割を表す、異なる複数の仮想ノードで置き換えることによって構築される（フローはここではエンドツーエンドルーティング事例であり、すなわち、送信元及び宛先ノード間のパスである）。
【００６４】
図４は、いずれも点線で示される２つの入来リンクａおよびｂと、２つの出力リンクｃおよびｄを有する１つのノードを示している。ａ及びｄに対するメトリックは他のリンクメトリックと相関していないが、ｂに対するメトリックはｃに対するメトリックと相関を有し、ｃに対するメトリックはａに対するメトリック及びｂに対するメトリックの両方と相関を有している。
【００６５】
このノードの役割について、４つのケースを区別する必要がある。
１．ノードがフローの最終宛先である場合。この場合、入来リンク上のメトリックは、従前のメトリックと同等である。そのフローは出力リンクを用いないので、その入来リンクメトリックがある出力リンクメトリックと相関を有する場合であってもやはり同様のことが成り立つ。この状況は図４において実線の矢印１１で示される。
２．ノードがフローの始点である場合。この場合、出力リンク上のメトリックは従前のメトリックと同等である。その論拠は上で述べたのものと同様である。この状況は図４において実線の矢印１２で示される。
３．ノードがフローの中継(transshipment)ノードであり（即ち、起点でも宛先でもない）、入来リンクメトリックも出力リンクメトリックも互いに相関しない場合。この場合、入来リンク及び出力リンクの両方におけるリンクメトリックは、対応する従前のメトリックと同等である。この状況は図４において実線の矢印１３で示される。
４．ノードがフローの中継ノードであり、入来リンクメトリックが出力リンクメトリックと相関を有するか、出力リンクメトリックが入来リンクメトリックと相関を有するか、両方のリンクメトリックが互いに相関を有する場合。この場合、入来及び出力リンク上のリンクメトリックに、対応する相互相関値を反映させる必要がある。この状況は図４において実線の矢印１４で示される。
【００６６】
図４において、これら４つの事例は、４つの異なるフローに関して示されている。一例として、リンクｃ上のメトリックは、フロー１２をルーティングする際にはｍc￣＝ｍcであるが、フロー１４をルーティングする際にはｍc￣＝ｆc（ｍc，σac）である。リンクｂ上のメトリックはフロー１１をルーティングする際、すなわち、図４におけるノードが宛先である際にはｍb￣＝ｍbである。フロー１３をルーティングする際にはメトリックはｍb￣＝ｆb（ｍb，σcb）となる。
【００６７】
事例１，２及び３は、それぞれ１つの仮想ノードのみが必要である。事例１及び２はノードが宛先もしくは起点である全てのフローに当てはまり、事例３については、相関しないリンクメトリックを有する入来及び出力リンクの全ての組について、同じ仮想ノードを使用することができる。しかし、事例４は、一方（又は両方）のリンクメトリックがもう一方と相関を有する入来及び出力リンクの組の各々に対して１つの仮想ノードが必要となる。
【００６８】
正式には、拡張ルーティンググラフは以下のように構築される。
１．まだ考慮されていないノードｉを、元のグラフから取り出し、以下を加算する。
a)１つの宛先仮想ノードｉt
b)１つの起点仮想ノードｉs
c)リンクメトリックが相関を持たない入来及び出力リンクの組が少なくとも１つ存在するならば、即ち、
∃a,b: a=(k,i), b=(i,j)  ここでσba＝０かつσab＝０
であれば、１つの非相関中継仮想ノードｉ0,0、そして最後に、
d)一方（又は両方）の対応するリンクメトリックがもう一方と相関を有する入来リンクａ及び出力リンクｂの各組について、１つの相関を有する中継仮想ノードｉa,b。すなわち、
∀a,b: a=(k,i), b=(i,j)  ここでσba≠０又は／及びσab≠０
【００６９】
２．元のグラフにおける全てのノードが考慮されたならば、３へ進み、さもなければ１へ戻る。
【００７０】
３．次に、元のグラフにおいて考慮されていないリンクａ＝（ｉ，ｊ）を取得し、以下を加算する。
a)リンクメトリックｍ￣＝ｍaを有する１つの仮想リンク（ｉs，ｊt）、
b)リンクメトリックｍ￣＝ｍaを有する１つの仮想リンク（ｉs，ｊ0,0）、
c) ｊa,bが存在する全てのｂに対して、リンクメトリックｍ￣＝ｆa（ｍa，σba）を有する仮想リンク（ｉs，ｊa,b）、
d)リンクメトリックｍ￣＝ｍaを有する１つの仮想リンク（ｉ0,0，ｊt）、
e)リンクメトリックｍ￣＝ｍaを有する１つの仮想リンク（ｉ0,0，ｊ0,0）、
f)ｊa,bが存在する全てのｂに対して、リンクメトリックｍ￣＝ｆa（ｍa，σba）を有する仮想リンク（ｉ0,0，ｊa,b）、
g)ｉb,aが存在する全てのｂに対して、リンクメトリックｍ￣＝ｆa（ｍa，σba）を有する仮想リンク（ｉb,a，ｊt）、
h) ｉb,aが存在する全てのｂに対して、リンクメトリックｍ￣＝ｆa（ｍa，σba）を有する仮想リンク（ｉb,a，ｊ0,0）、
i) ｉb,a及びｊa,cが存在する全てのｂ及びｃに対して、リンクメトリックｍ￣＝ｆa（ｍa，σba，σca）を有する仮想リンク（ｉb,a，ｊa,c）。
【００７１】
４．元のグラフにおける全てのリンクが考慮されたならば終了し、さもなければ３へ戻る。
【００７２】
ここで、サブステップ３ｃ，３ｆ，３ｇ，３ｈ及び３ｉにおけるリンクメトリックのいくつかの相互相関値は０であってもよいことに留意されたい。これは、他の隣接リンクの相関を反映させるために、関連する相関中継仮想ノードが加算された場合に生じる。しかし、元のグラフの接続性を維持するため、仮想リンクは依然として必要である。
【００７３】
上述した手順は宛先及び起点仮想ノードを常に加算するが、どのようなルーティングを行っても決して起点及び／又は宛先にならないことが分かっているノードについては、対応する仮想ノード並びにリンクを除外してよいことは言うまでもない。
【００７４】
拡張ルーティンググラフの例を図５Ａ及び５Ｂに示す。図５Ａは、４つのノードＮ１，Ｎ２，Ｎ３，Ｎ４と５つのリンクａ，ｂ，ｃ，ｄ，ｅを有する元のルーティンググラフを示す。０でないリンクメトリック相互相関値も示されている。図５Ｂは対応する拡張ルーティンググラフを示す。物理ノードＮ２，Ｎ３の各々が、仮想ノードとして参照される回数だけ示されていることに留意されたい。ノードに対応する各仮想ノードは、異なるパスにおいて用いられる。簡単にするため、ノードＮ１の宛先仮想ノード及びノードＮ４の起点仮想ノードは示していない。本例において、ノードＮ１は送信ノードとしてのみ、ノードＮ４は受信ノードとしてのみ考慮される。
【００７５】
拡張ルーティンググラフは、任意の標準的な組み合わせ経路構築アルゴリズム、例えば最短パス方法により、所与のフローに対する最適経路及び合計経路メトリックを探索することを可能にする。フローの起点及び宛先ノードがそれぞれｏ及びｄであれば、仮想ノードｏs及びｄtが拡張ルーティンググラフにおいて用いられるべきである。最適経路メトリックは拡張ルーティンググラフから直接求められ、各仮想ノードを対応する元のノードで置き換えるとともに、仮想リンクについて同様に処理することにより元のグラフにおける経路が簡単に構築される。
【００７６】
図５Ｂから分かるように、２つのノード間のリンクに対するメトリックは、そのリンクが一部を占めるパスにおける他のリンクに依存して変化する。
【００７７】
単独のリンク又はホップからなるパスについてのメトリックを、表４に示す。
【００７８】
2008544688.tif 000012
表４：送信ノードＮ１，Ｎ２，Ｎ３及び宛先ノードＮ２，Ｎ３，Ｎ４間の単独ホップパスに対するメトリック
【００７９】
送信ノードＮ１から宛先ノードＮ３への、ノードＮ２を経由したパスに対するリンクメトリックは以下の通りである。
ノードＮ１からノードＮ２：ｍa
ノードＮ２からノードＮ３：ｍd＋σad
【００８０】
送信ノードＮ１から宛先ノードＮ４への、ノードＮ２を経由したパスに対するリンクメトリックは以下の通りである。
ノードＮ１からノードＮ２：ｍa＋σba
ノードＮ２からノードＮ４：ｍb
【００８１】
送信ノードＮ１から宛先ノードＮ４への、ノードＮ３を経由したパスに対するリンクメトリックは以下の通りである。
ノードＮ１からノードＮ３：ｍc
ノードＮ３からノードＮ４：ｍe＋σce
【００８２】
送信ノードＮ１から宛先ノードＮ４への、ノードＮ２及びＮ３の両方を経由したパスに対するリンクメトリックは以下の通りである。
ノードＮ１からノードＮ２：ｍa 
ノードＮ２からノードＮ３：ｍd＋σad＋σed
ノードＮ３からノードＮ４：ｍe
【００８３】
送信ノードＮ２から宛先ノードＮ４への、ノードＮ３を経由したパスに対するリンクメトリックは以下の通りである。
ノードＮ２からノードＮ３：ｍd＋σed
ノードＮ３からノードＮ４：ｍe
【００８４】
特定のパスに対するパスメトリックは、そのパス内の全リンクに対するリンクメトリックを加算することにより求められる。通常、最も小さいパスメトリックを有するパスが選択されるべきパスである。
【００８５】
図６は、本発明に係る方法全体のフローチャートである。
ステップＳ１で、候補パスｐの集合Ｐを決定する。
ステップＳ２で、集合Ｐから、メトリックを求めるべきパスｐを選択する。
ステップＳ３で、パスｐ内の各リンクに対し、相関補正されたリンクメトリック値を計算する。上述の通り、この計算は、個々のリンクに対する相互相関ベクトル及び現在のリンクメトリックに基づく。
ステップＳ４で、相関補正されたリンクメトリック値が全てのパスに対して計算されたか判定する。もしNOであれば、ステップＳ２に戻り、リンクメトリック値が計算されていないパスｐを選択し、YESであれば、ステップＳ５へ進む。
ステップＳ５：各パス内のリンクに対する相関補正されたリンクメトリック値に基づき、コネクションのための最適パスを選択する。実際には、各パスについて、パス内の全リンクに対する補正されたリンクメトリック値を加算する工程が含まれるであろう。そして、全てのパスに対して得られた値を比較することができ、最も好ましいメトリック値を有するパスを選択することができる。
必要に応じて実行されるステップＳ６において、トラフィックを選択したパス上で伝送する。
【００８６】
ステップＳ３において用いられる相互相関値をどのように取得するかは、既に述べた通りである。
【００８７】
図７は、図４、図５Ａ及び図５Ｂに関連して上述したような拡張ルーティンググラフが用いられる場合の、本発明に係る方法のフローチャートである。
ステップＳ１０：上述のように仮想ノード及び仮想リンクを導入して、拡張ルーティンググラフを生成する。
ステップＳ１１：ステップＳ１０で生成したルーティンググラフに標準的な最短パスアルゴリズムを適用して、最短パスを決定する。
ステップＳ１２：経路及び経路メトリックを抽出する。経路は、仮想ノードの各々を、対応するノードと置き換えるとともに、仮想リンクの各々を対応するリンクと置き換えることによって得られる。経路メトリックは拡張ルーティンググラフにおける経路メトリックと同一である。
大きな値を有する方がよい（例えば、サポートするレート、リンク品質、等）メトリックもあれば、小さな値を有する方がよい（例えば、遅延、ホップ数、等）メトリックもある点に留意されたい。異なるメトリックは互いに影響しうる。異なるメトリックを１つの比較可能な値に合体するための１つの方法において、それ自体知られた効率関数を利用することができる。
【００８８】
参考文献
［１］Eppstein. D., 「ｋ最短パスの探索」SIAM Journal on Computing, 第２８巻、第２号、１９９８年
【図面の簡単な説明】
【００８９】
【図１】複数の可能性のあるルートを介した、ネットワークを通じた伝送を模式的に示す図である。
【図２Ａ】、
【図２Ｂ】、
【図２Ｃ】第１の例示ネットワークにおける、本発明によるルーティングを説明する図である。
【図３】第２の例示における、本発明によるルーティングを説明する図である。
【図４】ネットワーク内の、２つの入来リンクおよび２つの出力リンクを有する１つのノードを示す図である。
【図５Ａ】、
【図５Ｂ】本発明の実施形態に係る、ルーティンググラフおよび対応する拡張ルーティンググラフをそれぞれ示す図である。
【図６】本発明の方法のフローチャートである。
【図７】拡張ルーティンググラフが用いられた場合の本発明の方法のフローチャートである。
【図１】
2008544688.tif 000017
【図２Ａ】
2008544688.tif 000018
【図２Ｂ】
2008544688.tif 000019
【図２Ｃ】
2008544688.tif 000020
【図３】
2008544688.tif 000021
【図４】
2008544688.tif 000022
【図５Ａ】
2008544688.tif 000023
【図５Ｂ】
2008544688.tif 000024
【図６】
2008544688.tif 000025
【図７】
2008544688.tif 000026
【手続補正書】
【提出日】平成19年4月12日(2007.4.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
通信ネットワーク内のデータ伝送フローのための経路を選択する方法であって、送信者から受信者への、少なくとも、少なくとも第１のリンクを有する第１の経路とに対する合成経路メトリックと少なくとも第２のリンクを有する第２の経路とに対する合成経路メトリックとを比較するステップと、前記第１の経路及び前記第２の経路に対する前記経路メトリックは、前記少なくとも第１のリンク及び前記少なくとも第２リンクのリンクメトリックにそれぞれ基づき、前記少なくとも１つのリンクのリンクメトリック値を、あるデータフローが前記ネットワーク内の他のリンクを既に用いているとした場合に当該リンクメトリック値に生じるであろう変化を表す相互相関値に基づいて求めるステップを有することを特徴とする方法。
【請求項２】
前記経路が少なくとも２つのリンクを有し、前記他のリンクが前記少なくとも１つのリンクと同じ経路に含まれることを特徴とする請求項１記載の方法。
【請求項３】
前記リンクメトリック値が、リンクメトリック相互相関ベクトルに基づいて算出され、前記リンクメトリック相互相関ベクトルは、前記少なくとも１つのリンクについて他のリンクに対応する相互相関値を有すると共に、データフローが既に前記他のリンクを用いているとした場合に前記少なくとも１つのリンクに対する前記リンクメトリック値に生じるであろう変化を反映することを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
前記リンクメトリック値が、相関及び／又は情報が存在するものに対する組（ｂ，σba）からなる値の集合に基づいて算出され、ここで、ｂは別のリンクであり、（σba）はデータフローが既に前記他のリンクを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１乃至請求項３のいずれか１項に記載の方法。
【請求項５】
前記リンクメトリック値が、関数ｍa￣＝ｆa（ｍa，σpa）に従って算出され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項３又は請求項４に記載の方法。
【請求項６】
前記リンクメトリック値が、以下の関数
2008544688.tif 000027
に従って算出され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、Ｐは考慮すべき全リンクの集合、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項３又は請求項４に記載の方法
【請求項７】
前記少なくとも１つのリンクの前記リンクメトリック値を、データフローが前記第１のリンクを既に用いているとした場合に前記リンクメトリック値に生じるであろう変化に基づいて算出するステップをさらに有することを特徴とする請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項８】
− 元のリンクメトリックｍaと、標準的なｋ−最短パス構築法を用いて、所定数ｋの最短パスを探索するステップと、
− 前記ｋの最短パスを集合Ｐに含めるステップ、
とにより、可能性のあるパスの集合Ｐを決定するステップをさらに有することを特徴とする請求項１乃至請求項７のいずれか１項に記載の方法。
【請求項９】
前記相互相関値が、複数のリンクが互いにどのように影響するかについての知見に基づいて求められることを特徴とする請求項２乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
前記相互相関値が、複数のリンクメトリックがどのように相関するのかの経時的な監視に基づいて求められることを特徴とする請求項２乃至請求項８のいずれか１項に記載の方法。
【請求項１１】
補正された相互相関値σba(new)を以下の式
2008544688.tif 000028
（ここで、ｇおよびｈは関数であり、αbaは前記他のリンクが前記第１のリンクに与えるであろう影響を表す重み係数であり、ｍaは現在のリンクメトリック値であり、ｍ’aはフローがパスを用いる場合の前記リンクメトリック値である）によって算出するステップをさらに有することを特徴とする請求項１乃至請求項１０のいずれか１項に記載の方法。
【請求項１２】
− 仮想ノード及び仮想リンクを導入して拡張ルーティンググラフを生成するステップと、
− 標準的な最短パスアルゴリズムをルーティンググラフに適用して最短パスを決定するステップと、
− 仮想ノードの各々を対応するノードと置き換えると共に、仮想リンクの各々を対応するリンクと置き換えることにより、経路を抽出するステップと、
− 前記拡張ルーティンググラフにおける経路メトリックを用いて、前記経路メトリックを抽出するステップとをさらに有することを特徴とする請求項１記載の方法。
【請求項１３】
電気通信ネットワークで用いるためのノード(S,R,I)であり、当該ノードから開始する第１のリンクに対するリンクメトリックを求めるために必要とされるリンク特性を制御及び／又は監視するように構成されたリンクメトリック関数部（ＬＭＦ）を備えるノードであって、前記リンクメトリック関数部は、前記第１のリンクのリンクメトリック値を、リンクメトリック相互相関ベクトルに基づいて算出するように構成されており、前記リンクメトリック相互相関ベクトルは、前記少なくとも１つのリンクについて他のリンクに対応する相互相関値を有すると共に、データフローが既に前記他のリンクを用いているとした場合に前記少なくとも１つのリンクに対する前記リンクメトリック値に生じるであろう変化を反映することを特徴とするノード。
【請求項１４】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、相関及び／又は情報が存在するものに対する組（ｂ，σba）からなる値の集合に基づいて算出するように構成されており、ｂは別のリンクであり、（σba）はデータフローが既に前記他のリンクを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１３記載のノード。
【請求項１５】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、関数ｍa￣＝ｆa（ｍa，σpa）に従って算出するように構成されており、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１３又は請求項１４に記載のノード。
【請求項１６】
前記リンクメトリック関数部（ＬＭＦ）が、前記リンクメトリック値を、以下の関数
2008544688.tif 000029
に従って算出するように構成され、ｍa￣は算出すべき前記リンクメトリック値、ｍaは現在のリンクメトリック値、Ｐは考慮すべき全リンクの集合、σbaはデータフローが既に前記他のリンクｂを用いているとした場合に前記第１のリンクの前記リンクメトリック値に生じるであろう変化を反映する相互相関値であることを特徴とする請求項１３又は請求項１４に記載のノード。
【請求項１７】
前記リンクメトリック関数部（ＬＭＦ）が、前記少なくとも１つのリンクの前記リンクメトリック値を、データフローが前記第１のリンクを既に用いているとした場合に前記リンクメトリック値に生じるであろう変化に基づいて算出するように構成されることを特徴とする請求項１３乃至請求項１６のいずれか１項に記載のノード。
【請求項１８】
− 元のリンクメトリックｍaと、標準的なｋ−最短パス構築法を用いて、所定数ｋの最短パスを探索するステップと、
− 前記ｋの最短パスを集合Ｐに含めるステップ、
とにより、可能性のあるパスの集合Ｐを決定する手段(7)をさらに有することを特徴とする請求項１３乃至請求項１７のいずれか１項に記載のノード。
【請求項１９】
前記リンクメトリック関数部が、複数のリンクが互いにどのように影響するかについての知見に基づいて求められた相互相関値を用いるように構成されることを特徴とする請求項１３乃至請求項１８のいずれか１項に記載のノード。
【請求項２０】
前記リンクメトリック関数部が、複数のリンクメトリックがどのように相関するのかの経時的な監視に基づいて求められた相互相関値を用いるように構成されることを特徴とする請求項１３乃至請求項１９のいずれか１項に記載のノード。
【請求項２１】
補正された相互相関値σba(new)を以下の式
2008544688.tif 000030
（ここで、ｇおよびｈは関数であり、αbaは前記他のリンクが前記第１のリンクに与えるであろう影響を表す重み係数であり、ｍaは現在のリンクメトリック値であり、ｍ’aはフローがパスを用いる場合の前記リンクメトリック値である）によって算出する手段(９)をさらに有することを特徴とする請求項１３乃至請求項２０のいずれか１項に記載のノード。
【請求項２２】
前記リンクメトリック関数部（ＬＭＦ）が、
− 仮想ノード及び仮想リンクを導入して拡張ルーティンググラフを生成し、
− 標準的な最短パスアルゴリズムをルーティンググラフに適用して最短パスを決定し、
経路及び経路メトリックを、
− 仮想ノードの各々を対応するノードと置き換えると共に、仮想リンクの各々を対応するリンクと置き換え、
− 前記拡張ルーティンググラフにおける経路メトリックを前記経路メトリックとして得ることにより抽出する、
ように構成されることを特徴とする請求項１３記載のノード。
【請求項２３】
請求項１３乃至請求項２２のいずれか１項に記載のノード(S,R,I)を少なくとも１つ有する通信ネットワーク。
【国際調査報告】
2008544688.tif 000031
2008544688.tif 000032
2008544688.tif 000033