(57)【要約】      （修正有）【課題】ノードがリンクによって接続されるオーバーレイネットワークにおいてサーバとクライアントとの間の複数のパスを選択する方法を提供する。【解決手段】各ノードにおいて、当該ノードと直接隣接するノードに接続する各リンクについて、サービス品質メトリックを測定し、測定したメトリックをサーバへ送信する。サーバにおいて、メトリックに基づくリンク相関行列およびリンク相関行列に基づくパス相関行列を求める。次に、メトリック、リンク相関行列、およびパス相関行列に基づいて複数のパスの選択を行う。【選択図】図１
2005136982.tif 000002
【特許請求の範囲】
【請求項１】
リンクによって接続された複数のノードを有するオーバーレイネットワークにおいてサーバとクライアントとの間の複数のパスを選択する方法であって、前記複数のノードは、前記サーバおよび前記クライアントを含み、各パスは、選択されたリンクの集合を含み、
各ノードにおいて、該ノードを直接隣接するノードに直接接続する各リンクのサービス品質メトリックを測定することと、
前記サーバへ前記メトリックを送信することと、
前記サーバにおいて、前記メトリック、該メトリックに基づくリンク相関行列、および該リンク相関行列に基づくパス相関行列を維持管理することと、
前記メトリック、前記リンク相関行列、および前記パス相関行列のみに基づいて前記複数のパスを選択することと
を含むサーバとクライアントとの間の複数のパスを選択する方法。
【請求項２】
前記複数のパスを通じて前記サーバから前記クライアントへデータをストリーミングすることをさらに含む請求項１に記載の方法。
【請求項３】
前記サーバのみに前記データのコピーを格納することをさらに含む請求項１に記載の方法。
【請求項４】
前記ストリーミングデータは、マルチメディアである請求項２に記載の方法。
【請求項５】
前記リンク相関行列は、
【数１】
2005136982.tif 000009
であり、ここで、ｉｊおよびｍｎは２つのノードを接続するリンクの対であり、Ｅは期待値であり、ＬｉｊおよびＬｍｎはリンクｉｊおよびリンクｍｎに対する前記メトリックであり、平均Ｌｉｊ（バー）＝Ｅ（Ｌｉｊ）である請求項１に記載の方法。
【請求項６】
前記メトリックは、前記リンクの帯域幅、待ち時間、およびパケット損失率を含む請求項１に記載の方法。
【請求項７】
前記測定すること、送信すること、維持管理すること、および選択することは、時間ウィンドウにわたり動的および定期的に実行される請求項１に記載の方法。
【請求項８】
前記パス相関行列は、
【数２】
2005136982.tif 000010
であり、ここで、ＰａｔｈＡはａを要素とするリンク集合Ａを含み、ＰａｔｈＢはｂを要素とするリンク集合Ｂを含む請求項５に記載の方法。
【請求項９】
前記メトリックに基づいて第１パスを最初に選択することと、
前に選択されたパスに従って各リンクの利用可能帯域幅を更新することと、
パスについて前に選択されたリンク集合Ｓに関して各リンクＬに対する相関費用（ｃｃ）を
【数３】
2005136982.tif 000011
のように求めることと、
費用関数
【数４】
2005136982.tif 000012
（ここで、Ｗは前記メトリックであり、αおよびαｉは重み係数である）
を用いて各リンクに対する費用を得るために前記相関費用および前記メトリックを組み合わせることと、
更新された費用ＣｏｓｔＳＬに基づいて次の最短パスを選択することと、
前記複数のパスが選択されるまで前記更新すること、求めること、組み合わせること、および選択することを繰り返すことと
をさらに含む請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークに関し、より詳細には、物理ネットワークおよびオーバーレイネットワークを含む異種混合ネットワークにおいて、データをストリーミングするために複数の通信パスを選択することに関する。
【背景技術】
【０００２】
インターネットを通じて、信頼性および費用効果の高い方法でデータをストリーミングすることが求められている。通常、ストリーミングされるデータは、ビデオおよび／またはオーディオ信号である。ストリーミングデータは、遅延制約が厳格であること、およびパケット損失に対して敏感であることによって特徴づけることができる。インターネットのようなパケットネットワークの現在のインフラストラクチャは、ストリーミングアプリケーションを適切にサポートするには不十分である。エンドツーエンドストリーミングの品質は、マルチプルディスクリプション符号化（ＭＤＣ）やfine-granularity-scalability（ＦＧＳ）符号化のような特別の符号化技法を用いることによって改善することができる。
【０００３】
これらの符号化技法は、記述のために複数のパスが用いられる場合に特に良好に作用する。Apostolopoulos著「Reliable video communication over lossy packet networks using multiple state encoding and path diversity」（VCIP, 2001）、Lin等著「Video Transport over Ad Hoc Networks Using Multiple Paths」（Proceedings of The 2002 IEEE International Symposium on Circuit and Systems, May 2002）、Zhou等著「Multi-path transport of FGS video」（Packet Video Workshop, 2003）、Begen等著「Multi-path selection for multiple description encoded video streaming」（IEEE ICC, 2003）、およびBegen等著「Fast Heuristics for multi-path selection for multiple description encoded video streaming」（IEEE ICME, 2003）を参照されたい。
【０００４】
ＭＤＣビデオストリーミングのためのパスダイバーシティを提供するために、コンテンツ配信ネットワーク（ＣＤＮ）が用いられている。Apostolopoulos等著「On multiple description streaming with content delivery networks」（IEEE INFOCOM, 2002）を参照されたい。しかし、この方法では、ビデオがネットワークのエッジサーバにあらかじめ格納されることが必要である。エッジサーバは、宛先クライアントの近くに配置される。このことは、ストリーミングの費用を増大させる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術のパス選択は、通常、選択されるパスにおけるすべてのリンクが重複しないことを必要とする。すなわち、パスは「無相関」である。しかし、極大リンク非重複パスに基づく技法は、利用可能なパスの数を著しく制限し、平均としては、費用、待ち時間、およびパケット損失が大きくなる傾向がある。
【課題を解決するための手段】
【０００６】
ノードがリンクによって接続されるオーバーレイネットワークにおいて、サーバとクライアントとの間の複数のパスを選択する方法を提供する。
【０００７】
ノードは、サーバおよびクライアントを含む。各パスは、選択されたリンクの集合を含む。まず、各ノードにおいて、当該ノードを直接隣接するノードに直接接続する各リンクについて、サービス品質メトリックを測定する。メトリックとしては、帯域幅、待ち時間、およびパケット損失率が挙げられる。
【０００８】
メトリックは、サーバへ送信される。サーバにおいて、メトリックに基づくリンク相関行列およびリンク相関行列に基づくパス相関行列を求める。
【０００９】
次に、メトリック、リンク相関行列、およびパス相関行列のみに基づいて複数のパスを選択する。その時点で、データをサーバからクライアントへストリーミングすることができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明によるデータをストリーミングするために複数のパスを選択する方法を使用する異種混合ネットワーク１００を示している。本ネットワーク１００は、オーバーレイネットワーク１１０および物理ネットワーク１２０を含む。オーバーレイネットワークのオーバーレイノード１１１（白丸で示す）は、オーバーレイリンク１１２によって接続され、物理ネットワークの物理ノード１２１（黒丸で示す）は、物理リンク１２２によって接続される。
【００１１】
オーバーレイネットワーク１１０は、既存の物理ネットワーク（例えばインターネット）上に構築された仮想ネットワークである。Andersen等著「Resilient overlay networks」（18th ACM Symposium on Operation Systems Principles, 2001）を参照されたい。縦線１０５は、オーバーレイネットワークのノードと物理ネットワークのノードとの間の関係を示す。利点として、本オーバーレイネットワーク１１０は、基礎となる物理ネットワーク１２０の最小限のサポートおよび知識しか必要としない。
【００１２】
オーバーレイネットワーク１１０は、ストリーミングされるべきデータのソースとしてのサーバノード１０１と、ストリーミングされるデータの宛先としてのクライアントノード１０２を含む。ソースノードと宛先ノードは、中間ノード１０３およびオーバーレイリンク１１２によって接続される。サーバとクライアントとの間の完全なエンドツーエンドコネクションを提供するリンクの集合をパスと呼ぶ。いくつかの異なるパスが可能である。
【００１３】
本発明の１つの目的は、サーバからクライアントへの複数の最適パスを決定することである。本発明のもう１つの目的は、ネットワーク条件およびトラフィックパターンが時間によって変化するとともに動的にこのような最適パスを維持管理することである。
【００１４】
本オーバーレイネットワーク１１０は、基礎となる物理ネットワーク１２０の知識およびサポートに関して最小限の仮定をする。定期的に、クライアント１０２は、サーバ１０１からストリーミングデータを受信することを求める要求を行う。サーバがこのような要求を受信すると、サーバは、オーバーレイネットワークにおけるパスを用いてクライアントへストリーミングデータを配信するための複数のパスを動的に選択する。本発明によって選択される複数のパスを用いることにより、サービス品質（ＱｏＳ）は、従来技術よりも改善される。
【００１５】
従来技術では、ネットワークのエッジにあるサーバに、要求されたビデオのコピーを格納することによって、サービスの改善を達成することができる。すなわち、サーバは、クライアントの近くにある。しかし、ビデオは、大量の記憶領域を消費するため、要求されたすべてのビデオのコピーを格納するために複数のエッジサーバを使用すれば、システム全体の費用が激しく増大する。これに対して、本発明では、サーバがクライアントからどんなに遠く離れていても、発信側サーバにビデオのコピーを１つ格納するだけである。
【００１６】
本発明によれば、オーバーレイネットワーク１１０内の各ノード１１１が、直接隣接するノードへの直接リンク１１２のＱｏＳメトリック（例えば帯域幅、待ち時間、およびパケット損失率）を監視する。各リンクに対するこれらのメトリックがサーバ１０１へ転送される。サーバは、以下で詳細に説明するように、メトリックを用いて、サーバからクライアントへの複数の最適パスを動的に選択する。
【００１７】
従来技術のパス選択方法の問題点は、それらの方法がリンクの非重複集合を用いたパスを必要とすることである。すなわち、リンクは、複数のオーバーレイパスの部分となることができない。この選択方法にはいくつかの問題点がある。まず第１に、選択は、ネットワーク条件ではなく、主としてネットワークトポロジーに基づいている。これを図１の例示的ネットワークに示す。ここで、オーバーレイリンク１１３〜１１４は異なるが、その一部は共通のリンク１２５によって実現されている。極大リンク非重複パス法のような従来の技法を用いると、ネットワーク１００に対して複数のパスを選択することは不可能である。第２に、従来の方法は、選択可能なパスの個数を著しく制限する。これは、パスが、平均として、必要以上に長く、費用がかかる傾向があることの結果である。パスが長くなると、パフォーマンスは低下する傾向がある。
【００１８】
この問題点に対する本発明の解決法には、２つの面がある。第１に、マルチパス選択問題に対して、リンク相関およびパス相関の両方に基づくＱｏＳメトリックを使用する。第２に、複数のパスを最適に選択するために、リンク相関およびパス相関に対する費用関数を提供する。本発明は、物理ネットワークのバックボーンにおける多くのリンクが非常に大きい帯域幅を有し、極めて信頼性が高いことを認識している。実際、このようなリンクのＱｏＳメトリックは、時が経つとともに絶えず向上している。したがって、実際的アプリケーションでは、複数のオーバーレイパスの間でこのような高いパフォーマンスの物理リンクを共用することが十分に考えられ、おそらくは有利である。
【００１９】
相関行列
本オーバーレイネットワーク１１０において、サーバ１０１は、すべてのリンクに対するリンク相関行列１５０およびすべてのパスに対するパス相関１５１行列を維持管理する。リンク相関行列は、同じくサーバによって維持管理されるＱｏＳメトリック１５２に基づいて、各オーバーレイリンクをすべての他のオーバーレイリンクに関連づける。同様に、パス相関行列は、それぞれの可能なパスをすべての他の可能なパスに関連づける。
【００２０】
リンク相関
従来技術とは異なり、本発明では、基礎となる物理ネットワーク１２０の状態やトポロジーに関して何も仮定しない。サーバ１０１において、リンクおよびパスの相関１５０〜１５１を画定するために、ノード１１１によって収集されるリンク１１２の統計情報１５２を使用する。各ノードは、当該ノードをそれぞれの直接隣接するノードに接続する直接リンクに関するメトリックを収集する。
【００２１】
メトリックＬに基づくリンク相関（Ｃｒ）１５０は、次式の通りである。
【００２２】
【数１】
2005136982.tif 000003
【００２３】
ここで、ｉｊおよびｍｎはリンクの対であり、Ｅは、それらのリンクに対する期待値である。この公式は、２つのランダムベクトル間の線形相関に対する共分散を分散で割るという標準的定義に基づいている。通常、期待値は、範囲［−１、＋１］にある。しかし、本発明では、式（１）において、スケーリングした形、すなわち、（１／２＋１／２［・］）を用いる。これは、０≦Ｃｒ（Ｌｉｊ、Ｌｍｎ）≦１であることを保証する。値ＬｉｊおよびＬｍｎは、リンクｉｊおよびリンクｍｎに対するメトリックである。メトリックは、例えば、帯域幅、待ち時間、およびパケット損失率を考慮することができる。ここで、メトリックの平均はＬｉｊ（バー）＝Ｅ（Ｌｉｊ）である（ここで、Ｌｉｊ（バー）は、Ｌｉｊの上にバーが付されているものを示す）。
【００２４】
パスが選択される必要がある時にサーバにおける情報１５０〜１５２が常に最新となるように、すべての期待値およびＣｒ（Ｌｉｊ、Ｌｍｎ）を、ある時間ウィンドウにわたって動的かつ定期的に測定することができる。さらに、仮にデータがストリーミングされている間にネットワーク条件が変化した場合、例えば、パスの条件が劣化した場合には、データが常に最も効果的にストリーミングされるように、より良好なパスを選択することができる。
【００２５】
既に述べたように、各オーバーレイノードは、当該ノードを隣接するオーバーレイノードに接続するリンクを調べることにより、リンク情報１５２を取得する。この情報は、定期的に更新して、通常のルーティングパケットによりサーバへ送信することができる。サーバは、時間ウィンドウサイズを設定し、同じく定期的に相関行列１５０〜１５１を更新する。
【００２６】
パス相関モデル
パス相関行列１５１は、ＱｏＳメトリック１５２にも基づいている。ＰａｔｈＡおよびＰａｔｈＢが、オーバーレイネットワークにおけるａを要素とするリンク集合Ａおよびｂを要素とするリンク集合Ｂに対する２つのパスとする。これらの２つのパスに対する相関行列は、次式のように定義される。
【００２７】
【数２】
2005136982.tif 000004
【００２８】
この相関行列を、待ち時間、パケット損失率および帯域幅のような測定されたＱｏＳメトリック１５２とともに用いることにより、データ（例えばビデオ）をストリーミングするためにサーバ１０１とクライアント１０２との間の複数のパスを選択する。
【００２９】
極小相関マルチパス選択問題
本パス選択方法は、最適化問題として定式化することができる。以下の説明では、２つのパスを選択する。しかし、本方法を用いて２つより多くのパスを選択することができることが理解されるべきである。
【００３０】
本マルチパス選択方法では、オーバーレイネットワーク１１０をグラフＧＳ＝（ＶＳ、ＬＳ）で表現する。ここで、ＶＳは、ノードの集合であり、ＬＳは、リンクの集合である。各リンク（ｉ、ｊ）∈ＬＳは、非負のＲおよび加法的ＱｏＳ値Ｗｒ（ｉ、ｊ）（ｒ＝１、２、．．、Ｒ）１５２に関連づけられる。加法的ＱｏＳメトリックとは、パスメトリックがそのパスを規定するリンクの集合ＬＳのメトリックの総和であることを意味する。加法的ＱｏＳメトリックの例として、待ち時間、遅延ジッタ、および帯域幅がある。パケット損失率のようないくつかの非加法的ＱｏＳメトリックは、通常の対数関数を用いて加法的メトリックに変換することができる。詳細については、Zheng等著「Quality of service routing for supporting multimedia applications」（IEEE Journal of Selected Areas in Communications, Vol.14, No.7, pp.1228-1234, 1996）を参照されたい。
【００３１】
さらに、以下に定義するようなＲ個の対応するパスＱｏＳ制約Ｄｒ（ｒ＝１、２、．．、Ｒ）がある。リンク（ｉ、ｊ）と（ｍ、ｎ）との間の相関は、式（１）によりＣｒ（Ｌｉｊ、Ｌｍｎ）として定義される。
【００３２】
また、リンク有効性指示ベクトルＸ＝（．．Ｘｉｊ．．）およびＹ＝（．．Ｙｉｊ．．）も定義する。これらのベクトルは、リンク（ｉ、ｊ）が第１パスにおいて有効である（Ｘｉｊ＝１）かどうか、または第２パスにおいて有効である（Ｙｉｊ＝１）かどうかを示す。
【００３３】
そこで、下式（３）をリンク有効性Ｘｉｊ∈｛０、１｝、Ｙｍｎ∈｛０、１｝、∀（ｉ、ｊ）に従って、そして、下式（４）〜（６）の制約の下で最小化する。
【００３４】
【数３】
2005136982.tif 000005
【００３５】
式（４）は、Ｒ個の異なるＱｏＳメトリック制約Ｗ１５２を表し、式（５）および式（６）は、それぞれ第１パスおよび第２パスに対するリンク制約である。式（５）および式（６）において、記号ｓおよびｄは、それぞれサーバ（ソースノード）およびクライアント（宛先ノード）を示す。
【００３６】
この最小化は、ＮＰ困難問題である。行列Ｃ｜Ｅ｜×｜Ｅ｜は、Ｃｒ（Ｌｉｊ、Ｌｍｎ）個の成分を有する。下式のベクトルを定義して、最小化目標が（１／２）ＰＴＤＰとなるように、対応する制約を変更することができる。
【００３７】
【数４】
2005136982.tif 000006
【００３８】
ここで、Ｔは、通常のように転置を表す。これは、ＮＰ困難問題である既知の二次計画法の標準的形式である。
【００３９】
マルチパス選択方法
図２に示すように、本マルチパス選択問題がＮＰ困難であることから、ヒューリスティック解を提供することが必要となる。ステップ０で、オーバーレイネットワークにおいてターゲットストリーミングレートより小さい利用可能帯域幅を有するすべてのリンクを無効化する。上記のようにして、リンクに対するＱｏＳメトリックを測定し、リンク相関行列およびパス相関行列を構成し維持管理する。
【００４０】
ステップ１で、まず、所定のＱｏＳメトリック（例えば、待ち時間およびパケット損失率）に基づいて「最短」パスを選択する。
【００４１】
ステップ２で、前に選択されたパスに従って、各リンクの利用可能帯域幅を更新する。再び、ターゲットストリーミングレートより小さい帯域幅を有するリンクがあれば無効化する。
【００４２】
ステップ３で、リンク間の相関を考慮する。そこで、次式のように、パスについて前に選択されたリンク集合Ｓに関して各リンクＬに対する相関費用（ｃｃ）を求める。
【００４３】
【数５】
2005136982.tif 000007
【００４４】
ここで、上記で定義したとおり、Ｌ∈ＬＳ、およびａ∈Ｓである。選択された集合Ｓに対するリンクＬ＝（ｉ、ｊ）の相関費用は、Ｌと、集合Ｓ内の各リンクとの間のすべての対ごとの相関の総和である。
【００４５】
次に、ステップ４で、相関費用とＲ個の測定されたメトリックＷとを組み合わせることにより、次式の費用関数を用いて各リンクに対する新たな費用を得る。
【００４６】
【数６】
2005136982.tif 000008
【００４７】
この費用関数は、パス相関行列１５１とメトリックＷ１５２との重み付き和である。ここで、αおよびαｉは、重み係数である。
【００４８】
ステップ５で、帯域幅、待ち時間およびパケット損失率のような通常のリンクメトリックに基づいて、次の最短パスを求める。相関費用をもう１つの制約として用いて、次の最短パスを求める。複数の制約を満たす１つのパスを求めるため、相関費用と、最も重要なリンクメトリック（例えば、パケット損失率および待ち時間）を組み合わせた式（８）の費用関数を、適当な重み係数を用いて使用する。
【００４９】
既知のダイクストラアルゴリズムを用いて、新たな費用に従って、次の最短パスを求める。ダイクストラアルゴリズムは、最小費用のパスに基づいてネットワークコネクションのメッシュを通る最短パスを求めるのに役立つリンク状態ルーティングプロトコルのために用いられる。このアルゴリズムは、既知の方法で、ノードまでの経路の費用と、最小費用の経路とを最終的に生成する一連の計算を実行する。
【００５０】
複数の制約付きでパスを求めることは、ＮＰ困難問題として知られているので、式（８）を用いることにより、パフォーマンスを向上させる。この問題のための種々の近似アルゴリズムも既知である。ステップ４およびステップ５をこのような既知の近似で置き換えることができる。
【００５１】
すべてのパスが求められるまでステップ２〜５を繰り返す。
【００５２】
選択方法の動的バージョンでは、すべてのリンクを再評価し、ステップ０から繰り返すことによって、現在の動的なネットワーク条件に応じて新たなパスを選択する。
【００５３】
発明の効果
本発明は、インターネットのオーバーレイネットワークにおいてマルチプルディスクリプション符号化（ＭＤＣ）ビデオをストリーミングするためのマルチパス選択方法を提供する。ＱｏＳメトリックおよびリンク相関行列が提供される。本発明は、リンク相関行列に基づいて、オーバーレイネットワークのマルチパス選択問題に対するパス相関行列を提供する。また、本発明は、相関費用ルーティングと呼ばれる効率的なマルチパス選択手続きを提供することにより、オーバーレイネットワークにおける複数のパスを求める。本発明によれば、ストリーミングされるＭＤＣビデオに対する従来技術の極大リンク非重複パスと比べて最大３ｄＢのパフォーマンスの改善がある。
【００５４】
極大リンク非重複パスに基づく従来技術の選択方法は、オーバーレイネットワークにおけるパス間の相関を正確に指定しないため、ＰＳＮＲが低い。本発明の相関費用ルーティング手続きは、オーバーレイリンク間の静的および動的双方の相関をパス選択方法に取り入れているので、ＰＳＮＲが高くなる。本方法によれば、１つのリンクを複数のパスで用いることが可能となるため、極大リンク非重複パス法よりも遅延制約を満たす可能性が高くなる。実際、本方法のほうがパスダイバーシティによるパケット損失率が低い。また、本方法のほうがパス長が短いために遅延パケット数が少なく、実現するための複雑さが少ない。
【００５５】
最も重要な相違点として、従来技術は、まずネットワークトポロジーを考慮して実現可能なパスを選択した後ではじめてパスＱｏＳメトリックを考慮する。これに対して、本発明は、リンクおよびパスのＱｏＳメトリックの相関に全面的に基づいている。ネットワークトポロジーは要因ではない。
【００５６】
以上、好ましい実施形態を例として本発明を説明したが、本発明の精神および範囲内で、種々の他の適応および修正を行うことが可能であることが理解されるべきである。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るすべてのそのような変形および修正を包含することである。
【図面の簡単な説明】
【００５７】
【図１】本発明による異種混合ネットワークの図である。
【図２】本発明によるオーバーレイネットワークにおいて複数のパスを選択する方法のブロック図である。
【図１】
2005136982.tif 000013
【図２】
2005136982.tif 000014
【外国語明細書】
2005136982.tif 000015
2005136982.tif 000016
2005136982.tif 000017
2005136982.tif 000018
2005136982.tif 000019
2005136982.tif 000020
2005136982.tif 000021
2005136982.tif 000022
2005136982.tif 000023
2005136982.tif 000024
2005136982.tif 000025
2005136982.tif 000026
2005136982.tif 000027
2005136982.tif 000028
2005136982.tif 000029
2005136982.tif 000030
2005136982.tif 000031
2005136982.tif 000032