(57)【要約】【課題】複数のパスを使用してデータネットワーク上でデータを転送するためのシステム及び方法を提供する。【解決手段】データが、ネットワークのデフォルトパス（１０２）にわたって転送される。次に、デフォルトパス（１０２）のデータ損失率（６０６）が求められる。デフォルトパス（１０２）のデータ損失率が第１のしきい値を超えている場合、第１の代替パス（１０４）のデータ損失率（６１２）が求められる。第１の代替パス（１０４）のデータ損失率（６１２）が第２のしきい値よりも小さい場合、データの第１の部分が、第１の代替パス（１０４）へ転送される。その上、第１の代替パス（１０４）のデータ損失率（６１２）が第２のしきい値を満たすか又は超えるまで、データの追加部分が第１の代替パス（１０４）へ転送される。【選択図】図１
2008509602.tif 000002
【特許請求の範囲】
【請求項１】
複数のパスを使用してデータネットワーク上でデータを転送するための方法であって、
前記ネットワークのデフォルトパス（１０２）にわたってデータを転送することと、
前記デフォルトパス（１０２）のデータ損失率（６０６）を求めることと、
前記デフォルトパス（１０２）の前記データ損失率（６０６）が第１のしきい値を超えている場合に、
第１の代替パス（１０４）のデータ損失率（６１２）を求めることと、
前記第１の代替パス（１０４）の前記データ損失率（６１２）が第２のしきい値よりも小さい場合に、
前記データの第１の部分を前記第１の代替パス（１０４）へ転送することと、
前記データの追加部分を前記第１の代替パス（１０４）へ転送することであって、データの前記追加部分は、前記第１の代替パス（１０４）の前記データ損失率（６１２）が前記第２のしきい値を満たすか又は超えるまで、前記第１の代替パス（１０４）へ転送される、転送することと
を含む方法。
【請求項２】
前記第１の代替パス（１０４）の前記データ損失率（６１２）が前記第２のしきい値を超えている場合、前記第１の代替パス（１０４）へ転送されるデータの前記部分は、前記デフォルトパス（１０２）の前記損失率（６０６）にかかわらず削減される
請求項１に記載の方法。
【請求項３】
第２の代替パス（１０４）の前記データ損失率（６１２）を求めることと、
前記第２の代替パス（１０４）の前記データ損失率（６１２）が第３のしきい値よりも小さい場合に、
前記データの第２の部分を前記第２の代替パス（１０４）へ転送することと
をさらに含む請求項１に記載の方法。
【請求項４】
前記第２の代替パス（１０４）の前記データ損失率（６１２）が前記第３のしきい値よりも小さい場合に、
前記データの第３の部分を前記第２の代替パス（１０４）へ転送すること
をさらに含む請求項３に記載の方法。
【請求項５】
前記第２の代替パス（１０４）の前記データ損失率（６１２）が、前記第３のしきい値を超えるまで、前記データの追加部分が、前記第２の代替パス（１０４）へ転送される
請求項４に記載の方法。
【請求項６】
４つの代替パス（１０４）のうちの最大のものが利用される
請求項１に記載の方法。
【請求項７】
前記第１の代替パス（１０４）の前記第２のしきい値は、約０．１パーセントである
請求項１に記載の方法。
【請求項８】
複数のパスを使用してデータネットワーク上でデータを転送するためのデバイスであって、
デフォルトパス（１０２）のデータ損失率を求めるように構成されるデフォルトパスディターミナ（６０６）と、
前記デフォルトパスディターミナ（６０６）と接続されるデフォルトパス比較器（６０８）であって、前記デフォルトパス（１０２）の前記データ損失率（６０２）を第１のしきい値と比較するように構成されるデフォルトパス比較器（６０８）と、
前記デフォルトパスディターミナ（６０６）と通信接続される代替パスディターミナ（６１４）であって、代替パス（１０４）のデータ損失率を求めるように構成される代替パスディターミナ（６１４）と、
前記代替パスディターミナ（６１４）と接続される代替パス比較器（６１６）であって、前記代替パス（１０４）の前記データ損失率を第２のしきい値と比較するように構成される代替パス比較器（６１６）と
を備え、
前記デフォルトパス（１０２）の前記データ損失率が前記第１のしきい値を超え、且つ、前記代替パス（１０４）の前記データ損失率が前記第２のしきい値よりも小さい場合に、前記デフォルトパス（１０２）からのデータの第１の部分を前記代替パス（１０４）へ転送するように構成されるようになっている
デバイス。
【請求項９】
前記代替パスディターミナ（６１４）は、複数の代替パス（１０４）を求めるように構成される
請求項８に記載のデバイス。
【請求項１０】
４つの代替パス（１０４）のうちの最大のものが、前記代替パスディターミナ（６１４）によって利用される
請求項９に記載のデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、データネットワーク動作に関する。より詳細には、複数のパスを使用してデータネットワーク上でデータを転送するためのシステム及び方法に関する。
【背景技術】
【０００２】
ネットワークスループットが安定していることを必要とするストリーミングメディア等の多くのアプリケーションが存在する。一般に、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、インターネット等のネットワーク構成におけるスループットを提供する方法には、多数の方法がある。変化するスループットに対処する従来の手法は、送信ソースにおける適応を使用して、支配的な（prevailing）ネットワーク状態に従いソースのスループット要件を調節することである。マルチメディアデータの場合、これは、通常、メディアを何らかの方法でレートスケーラブルにすることを必要とする。ライブコンテンツの場合、これは、多くの場合、適応符号化の形を前提とする。記憶されたコンテンツの場合、異なるビットレートの同じコンテンツの複数のコピー間でのミッドストリームスイッチングが、多くの場合、使用される。
【０００３】
しかしながら、これら適応型ソース方式（adaptive source scheme）の問題のいくつかには、複数のコピーを生成して管理することが複雑であること、及び、支配的なスループットが変化するにつれてメディア品質の変動が大きくなることが含まれる。より重要なことには、ほとんどのコンテンツは、記憶された単一レートのフォーマットで存在し、適応型ソースモデル（adaptive source model）と適合しないということである。
【０００４】
アプリケーションのスループット要件を満たす別の方法は、単一のデータソース又はストリーミングソースについて複数の送信パスを同時に使用することである。このような方法では、１つのパスが、スループットボトルネックを伴う場合、他のパスを使用することによってそのボトルネックを迂回することが可能である。
【０００５】
今日のネットワークの多くは、基本的なサービスとして接続性を提供し、２つのエンドポイント間のトラフィックは、所定のデフォルトパスを横断する。しかしながら、デフォルトパスに加えて複数のパスを同時に使用することが実用的となる実際の設定が多く存在する。たとえば、次世代のインターネットプロトコルであるＩＰｖ６は、「ソースルーティング」をサポートしている。このソースルーティングは、送信ソースが、あらゆるパケットが横断するパスを明示的に指定することを可能にするものである。現在の公衆インターネットは、このようなソースルーティングをサポートしていない。しかしながら、さまざまな形のオーバーレイネットワーク及びピアツーピアネットワークにおけるより進歩したネットワークインフラストラクチャの出現によって、複数のパスを使用したデータ配送が実用的となり得るプラットフォームが提供される。具体的には、これらの進歩したインフラストラクチャは、トラフィックを中継できる追加ノードを提供する。このような方法では、異なるノードを使用してトラフィックを中継することにより、複数のパスを実現することができる。
【０００６】
オーバーレイネットワークの一例は、コンテンツ配信ネットワーク（ＣＤＮ）である。ＣＤＮは、応答時間を改善し、且つ、ウェブトラフィックのネットワーク資源使用量を削減するためのインターネット内部のキャッシングインフラストラクチャである。ＣＤＮは、インターネットに依拠して、ＣＤＮのノードへのトラフィック及びＣＤＮのノードからのトラフィックを配送するので、オーバーレイネットワークと呼ばれる。
【０００７】
複数のパスの使用によって、サービス品質は潜在的により良くなる可能性がある。それにもかかわらず、エンドアプリケーションに複数のパスを使用する自由選択が与えられるシステムでは、アプリケーションの各インスタンスは、「利己的な」方法で利用可能なパスの中からトラフィックを割り当てる。すなわち、インスタンスは、同じアプリケーション又は異なるアプリケーションの他のインスタンスへの影響にかまわず、自身の利得を最大にするためにトラフィックを割り当てる。利己的な割り当てがアプリケーションによって採用されると、複数のパスを使用する柔軟性を認めるシステムは、単一のパスのみを許可するシステムよりも性能が悪くなる場合がある。したがって、エンドアプリケーションの利己的な振る舞いと相まって、性能の改善を約束するパスを選択する際の柔軟性により、実際には、性能は劣化する可能性がある。
【０００８】
利己的な振る舞いと相まった選択によって性能が劣化する可能性があるという事実は、さまざまな状況において長い間知られていた。具体的には、道路交通工学では、新たな道路の建設によって、実際には、運転時間が長くなる場合があることが長い間知られ、且つ、観察されており、これはブライスのパラドックスとよく呼ばれる現象である。同様の振る舞いは、新たな回線の追加によって呼損確率が増加する電話網を含めて、多くの異なる状況でも報告されている。
【特許文献１】米国特許第６１９５３５４号
【特許文献２】米国特許出願公開第２００２／１８４３８２号
【特許文献３】米国特許出願公開第２００２／１１４３３２号
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、複数のパスを使用してデータネットワーク上でデータを転送するためのシステム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の実施の形態は、複数のパスを使用してデータネットワーク上でデータを転送するためのシステム及び方法を提供する。一実施の形態では、データが、ネットワークのデフォルトパスにわたって転送される。次に、デフォルトパスのデータ損失率が求められる。デフォルトパスのデータ損失率が第１のしきい値を超えている場合、第１の代替パスのデータ損失率が求められる。第１の代替パスのデータ損失率が第２のしきい値よりも小さい場合、データの第１の部分が、第１の代替パスへ転送される。その上、第１の代替パスのデータ損失率が第２のしきい値を満たすか又は超えるまで、データの追加部分が第１の代替パスへ転送される。
【００１１】
添付図面は、本出願に援用されて、本出願の一部を成す。添付図面は、本発明の実施の形態を示し、その説明と共に、本発明の原理を説明する機能を果たす。この説明で参照される図面は、言及がある場合を除き、一律の縮尺で描かれていないものと理解されるべきである。
【発明を実施するための最良の形態】
【００１２】
次に、本発明のさまざまな実施の形態を詳細に参照することにする。本発明のさまざまな実施の形態の例は、添付図面に示されている。本発明をこれらの実施の形態と共に説明するが、実施の形態は、本発明をこれらの実施の形態に限定することを目的とするものではないことが理解されよう。逆に、本発明は、代替的なもの、変更したもの、及び均等なものをカバーすることを目的としている。これらの代替的なもの、変更したもの、及び均等なものは、添付の特許請求の範囲によって画定された本発明の趣旨及び範囲内に含めることができる。さらに、本発明の以下の説明では、本発明の十分な理解を提供するために、多数の具体的な詳細が述べられている。それ以外の場合には、本発明の態様を不必要に不明瞭にしないように、既知の方法、手順、コンポーネント、及び回路は詳細に説明されていない。
【００１３】
本発明の態様は、コンピュータシステムにおいて実施することができる。このコンピュータシステムは、一般に、情報及び命令を処理するためのプロセッサ、情報及び命令を記憶するためのランダムアクセス（揮発性）メモリ（ＲＡＭ）、静的な情報及び命令を記憶するための読み出し専用（不揮発性）メモリ（ＲＯＭ）、情報及び命令を記憶するための磁気ディスク又は光ディスク及びディスクドライブ等のデータストレージデバイス、コンピュータユーザに情報を表示するための表示デバイス等のオプションのユーザ出力デバイス（たとえば、モニタ）、情報及びコマンドの選択されたものをプロセッサへ通信するための英数字キー及びファンクションキーを含むオプションのユーザ入力デバイス（たとえば、キーボード）、並びに、ユーザ入力情報及びユーザ入力コマンドの選択されたものをプロセッサへ通信するためのカーソル制御デバイス等のオプションのユーザ入力デバイス（たとえば、マウス）を含む。
【００１４】
［概観及び専門用語］
本発明の実施の形態は、複数のパスを使用してデータネットワーク上でデータを転送するためのシステム及び方法を提供する。すなわち、一実施の形態では、本発明のデータ転送方法は、ネットワークで動作するが、ダイレクトパスの無制限な使用のみを許可している。たとえばオーバーレイネットワーク等の任意の代替パスを依然として使用することができるが、しかしながら、それら代替パスは、損失率がその代替パスで生じ得ない範囲に制約される。すなわち、代替パスの損失率（たとえば、パケット廃棄、欠損データ等）は、低い状態（たとえば、或るしきい値未満の状態）でなければならない。したがって、代替パスは輻輳を受けないので、代替パスに沿った他のネットワークトラフィックに不利な影響はなく、その結果、他のネットワークトラフィックの性能劣化を増大させず、したがって、ネットワークの性能劣化を増大させない。
【００１５】
次に図１を参照して、本発明の一実施の形態による一例示のコンテンツ配信ネットワークの図が示されている。すなわち、スループットボトルネック（リンク３）を迂回するオーバーレイルート１０４（たとえば、代替パス）が示されている。一実施の形態では、ダイレクトパス１０２は、リンク１、２、３、４を通り、ノードＡを通るオーバーレイパス１０４は、リンク１、５、６、７、８、４を通る。オーバーレイパス１０４は、より多くのリンクを含むが、より大きなスループットを有することもできる。
【００１６】
場合によっては、オーバーレイパス（代替パス）は、より多くの資源を消費する可能性があり、ダイレクトパスよりも効率が低くなる可能性がある。たとえば、ネットワーク１００では、ダイレクトパス１０２は４つのホップしか有しないのに対して、オーバーレイパス１０４は６つのホップを有する。一般に、オーバーレイルーティングが、アプリケーションに利用可能にされる場合、同じタスクを達成している間、資源消費が全体的に増加する可能性があり、潜在的に、全体的な性能劣化につながる可能性がある。この劣化した性能は、各トラフィックストリームが、パスの中でトラフィックの最良な個別割り当てを個々に実行している時にも発生する場合がある。たとえば、アプリケーションが、ダイレクトパス１０２で５０パーセントのデータ損失率を受けている場合、そのアプリケーションは、代替パス１０４を使用して、データ損失率を、単一の５０パーセントのデータ損失率の代わりに２つの２５パーセントのデータ損失率に削減することができる。その際、トラフィックストリームは、パスの中でトラフィックの最良の割り当てを実行している。しかしながら、トラフィックストリームは、ダイレクトパスの４つのリンクの代わりに１０個のリンクの動きも止めている。具体的には、４つのリンクのダイレクトパスを使用した或るデータ量の送信Ｒは、４Ｒの資源を使用する。ダイレクトパスでの送信＿Ｒ及び代替パス（６つのリンク）での送信＿Ｒは、（４＊＿Ｒ）＋（６＊＿Ｒ）＝５Ｒの資源を使用する。第２（又は、第１０等）のユーザもネットワークを使用している場合、そのユーザも、自身のトラフィックを分割しようと試みて、ネットワークにより多くのトラフィックを導入する場合がある。その際、ネットワークリンクの平均トラフィックは増加され、その結果、損失率は高くなる。たとえば、第１のユーザは、デフォルトパスのみが使用された時の５０％ではなく６０％の損失を経験する場合がある。
【００１７】
一方、本発明は、ネットワークのオーバーレイパス１０４のデータ損失を制限することによって、アプリケーションの「利己性」を制限する方法を提供する。すなわち、一実施の形態では、デフォルトパス１０２のデータ損失率がたとえ何（たとえば、５０パーセント）であろうと、このデータ損失率は、代替パス１０４には拡散されない。その代わり、代替パスのデータ損失率は、しきい値未満に維持される。加えて、ネットワークにアクセスする第２のユーザ又はアプリケーションが存在する場合、双方のユーザは、それぞれのデフォルトパスのみに沿って送信することにより送信を開始している。それらユーザの代替パスは、他方のユーザのデフォルトパスと部分的に重なる場合がある。しかしながら、双方のユーザは、それらユーザの各代替パスを、損失がない程度までしか使用せず、他方のユーザの輻輳を増大させることはない。その結果、ネットワーク性能の劣化はなくなる。
【００１８】
ネットワークは、任意の個数の段とすることができ、任意の個数のノードを利用できることが十分理解される。すなわち、図１には、一組のノードしか示されていないが、本発明は、より複雑なトポロジーを有する一般的なネットワークで使用できることが理解されるはずである。その際、通常のノード間ナビゲーションにノード内転送が加わることによって、各ノード内のダイナミクスはさらに複雑化される。
【００１９】
次に図２を参照して、本発明の一実施の形態による例示のトラフィックフォーマット及びそれらトラフィックフォーマットの要件が示されている。一実施の形態では、この技術分野で既知のように、ビデオトラフィック２０４は伸縮性がない（inelastic）。すなわち、レートＲで符号化されたビデオトラフィックは、Ｒの転送レートを持続することを要求し、Ｒよりも低いレートを許容できず、Ｒを超えるレートがわずかに有益であることが分かる。ビデオについてＲの転送レートを持続する必要があるため、送信されたビデオトラフィックは、ネットワークの状態にかかわらず、一定のビットレートストリームで使用される。すなわち、ストリームが１つのパスを使用していようと、複数のパスを使用していようと、価値のあるあらゆるビデオを受信するようにストリームのかなりの部分を維持しなければならない。加えて、ネットワークが複数のビデオデータを通過させている時、各ストリームがレートＲに維持されることが重要である。
【００２０】
［実施態様］
次に図３を参照して、本発明の一実施の形態による、ネットワーク上でデータを転送するためのステップのフロー図が示されている。
【００２１】
次に図３のステップ３０２を参照して、最初に、トラフィックは、デフォルトパスのみにわたって配備される。すなわち、複数のパスをサポートするネットワークが利用されているが、初期のパス（たとえば、デフォルトパス）がデータを転送するのに選択される。一実施の形態では、ネットワークがデフォルトパスを割り当てる。別の実施の形態では、ユーザ又はアドミニストレータがデフォルトパスを選択する。
【００２２】
次に図３のステップ３０４を参照して、一実施の形態では、デフォルトパスのデータ損失が測定される。たとえば、データがデフォルトパスに配備されている間、デフォルトパスの損失率が測定される。一実施の形態では、ピングを使用して、デフォルトパスの損失率を測定することができる。本明細書ではピングが使用されるが、この技術分野で既知の任意の測定手段を使用して、損失率を測定できることが十分理解される。ピングの使用は単に明快にするためにすぎない。
【００２３】
次に図３のステップ３０６を参照して、測定結果が解析される。換言すれば、デフォルトパスに損失があるか？デフォルトパスに損失がない場合、このプロセスが繰り返される。すなわち、トラフィックが、デフォルトパスにのみ配備されて、データ損失についてデフォルトパスが監視される。一実施の形態では、デフォルトパスは、第１のしきい値の損失率を有する。その上、一実施の形態では、この第１のしきい値は０である。後述するように、本発明のさまざまな実施の形態では、しきい値は、約０．１パーセントの値を仮定している。データ損失率を十分低くして、ユーザがデータ損失によるビデオストリームの劣化を視覚的に認識することを確実に防止するために、さまざまな実施の形態でこのような値が使用される。しかしながら、本発明は、他のさまざまなニーズを満たすように選択された他のさまざまなデフォルト値にもよく適していることが理解されるはずである。一実施の形態では、デフォルトパスの損失が第１のしきい値（たとえば、０、１％、５％、１２％、２５％等）を上回る場合、代替パスが評価される。一般に、ユーザが、オーバーレイネットワークから代替パスを選択することもできるし、アプリケーション又はネットワークが、代替パスを割り当てることもできる。一実施の形態では、複数の代替パスを解析のために選択することができる。
【００２４】
次に図３のステップ３０８を参照して、代替パスのデータ損失率が判明しているかどうかを確認するチェックが行われる。代替パスのデータ損失率が判明していない場合、ピング（たとえば、ステップ３１０）が代替パスに対して実行されて、損失率が求められる。ピング（又は他の試験プロセス）が一旦行われると、結果の損失率データが評価される。
【００２５】
次に図３のステップ３１２を参照して、代替パスの損失率が解析されて、その損失率が第２のしきい値未満であることが確かめられる。すなわち、代替パスの損失率は、代替パスの許容可能な損失率と比較される。一実施の形態では、第２のしきい値の喪失率は、約０．１パーセント未満の喪失率である。このような喪失率は、本実施の形態では第２のしきい値とみなされるが、本発明は、第２のしきい値として他のさまざまな喪失率を使用することにもよく適している。一実施の形態では、第１のしきい値、第２のしきい値、及びあらゆる追加されたしきい値は、同じとすることができる。しかしながら、本発明は、各パスについて異なるしきい値を有することにもよく適している。したがって、デフォルトパスについて第１のしきい値があり、第１の代替パスについて第２のしきい値があり、第２の代替パスについて第３のしきい値がある等となる。この場合、これらしきい値は、すべて同じとすることもできるし、異なるものとすることもできるし、或いは、一部を同じとする等も可能である。加えて、一実施の形態では、しきい値は可変とすることもできる。たとえば、しきい値は、ネットワークのユーザ数、ネットワークにおけるデマンド、時刻、アプリケーションの優先度、ユーザの優先度等に依存することができる。
【００２６】
次に図３のステップ３１４を参照して、代替パスが、第２のしきい値よりも小さな損失率を有する場合、データトラフィックの一部が代替パスへ移される。たとえデータトラフィックの一部が代替パスへ移されても、データトラフィック転送も、デフォルトパス上に維持される。加えて、データトラフィックの一部が代替パスへ一旦移されると、デフォルトパスの損失率の問題（たとえば、ステップ３０６）が再び処置される。すなわち、デフォルトパスにもはや損失がない場合（又は、損失率が第１のしきい値未満に下がった場合）、デフォルトパスのデータ損失の測定（たとえば、ステップ３０４）が維持されるが、それ以上データは転送されない。
【００２７】
一方、デフォルトパスの損失がまだ第１のしきい値を超えている場合、データの一部を代替パスへ転送するプロセスが、或る警告と共に、上述したものと同じ方法で繰り返される。使用中の第１の代替パスのデータ損失率がまだ最小（たとえば、しきい値未満）である場合、より多くのデータを第１の代替パスへ転送することができる。データのより多くの部分を第１の代替パスへ追加して転送することは、デフォルトパスが第１のしきい値未満のデータ損失率を有するか、又は、許容可能な不注意な損失率を超える損失率が第１の代替パスで発生するかのいずれかまで続けることができる。
【００２８】
次に図３のステップ３１６を参照して、第１の代替パスの損失率が、許容可能な第２のしきい値を超えている場合、第１の代替パスへそれ以上データは転送されない。換言すれば、データトラフィックが第１の代替パスへ追加して移されることはなく、第１の代替パスは、移されたデータトラフィックの当該パスの以前の負荷を維持する。一実施の形態では、第１の代替パスが損失率を示し始めた場合、第１の代替パスへ移されたデータ量を削減して、第１の代替パスのデータ損失率を第２のしきい値未満の値へ戻すことができる。
【００２９】
プロセスは、その後、ステップ３０６に戻る。すなわち、デフォルトパスに損失があるかどうかを確かめるチェックが行われる。一実施の形態では、（デフォルトパスが損失を有している間の）代替パスの検索を継続することができる。たとえば、複数の代替パスを使用して、デフォルトパスの損失率を軽減することができる。加えて、あらゆる可能な代替パスを監視することができる。たとえば、最初の通過時に、第２の代替パスが、第３のしきい値よりも高い損失率を示している場合、その第２の代替パスは、次の通過時に、第３のしきい値よりも高いデータ損失率をまだ示しているかどうかを確認するチェックを受けることができる。第２の代替パスが第３のしきい値よりも高いデータ損失率を示していない場合、第２の代替パスを利用して、デフォルトパスから損失の一部を軽減することができる。
【００３０】
一方、無損失の代替パスが見つからない場合（又は、十分でない無損失の代替帯域幅が見つかった場合）、この無損失方法は、デフォルトパスのみにおける損失率を維持する。それによって、損失がネットワークの他のノード及びパスへ伝搬されない。たとえば、本明細書で述べたように、代替パスの個数がたとえ何であろうと、しきい値を超える損失率を有する唯一のパスは、デフォルトパスである。すなわち、損失率は、利用されているすべてのパスにわたって均一に拡散されない。その代わり、デフォルトパスのみが損失率を有する場合がある。第１のしきい値を超える損失率をデフォルトパスにのみ制限することによって、有害なネットワーク劣化が削減され、より効率的な無制限ネットワークが提供される。
【００３１】
解析の目的で、一実施の形態では、すべてのトラフィックは、ストリームが分岐（leave）せず、且つ、新たなストリームが加わらない定常状態動作のビデオストリームであると仮定される。ビデオストリームは、１Ｍｂｐｓのレートであり、ネットワークの異なるソース及びデスティネーションを有する。各ビデオストリームのソースは、デフォルトパス及び一組の代替パスにアクセスすることができ、収束が達成されるまで、利用可能なパスについて、勾配降下アルゴリズムを個々に実行して、輻輳の高いリンクから輻輳の低いリンクへトラフィックを移す。
【００３２】
本発明の一例示の実施の形態をより十分に説明するために、デフォルト方式、無制限方式、及び無損失方式の３つの複数パス送信方式の比較を使用する。デフォルト方式の下では、デフォルトパスのみを使用することができ、正確に１つのパスがメディアデータを配送する。
【００３３】
無制限方式は、一組の代替パスが、すべてのユーザの無制限な使用に利用可能である「利己的な」複数パス方式の直接的な実施態様を表している。無制限方式を実施するシステムによって、ユーザは、ダイレクトパスと一組の代替パスとの間でトラフィックを任意に分割することが可能になる。具体的には、各ユーザは、非ゼロのトラフィックを有するすべてのパスが同じ損失率を有する平衡状態に達するまで、高損失のパスから低損失のパスへトラフィックを適応的に移すことによって、自身の利得を最適にする。この状態は、ユーザが自身のトラフィック割り当てを変更する動機を有しないので、平衡点を表している。各ユーザは、ダイレクトパスのみに沿ってすべてのトラフィックを送信することにより送信を開始しており、勾配降下アルゴリズムを使用して、高い瞬時損失を有するパスから低い瞬時ロスを有するパスへトラフィックの割り当てを徐々に移す。
【００３４】
無制限方式は、各ユーザが使用できるネットワーク資源の量に制限がないので、複数のパスの送信の一方の極端な場合を表している。複数のパスを惜しみなく使用することによって、或る場合には、デフォルト方式と比較してシステムスループットがかなり改善される可能性もあれば、他の場合には、システムスループットがかなり劣化される可能性もある。
【００３５】
本発明の無損失方式は、複数のパスの制約された使用を表している。具体的には、デフォルト方式によって達成されるシステムスループット以上のシステムスループットを保証するために、無損失方式は、代替パスが損失のない時にのみ代替パスの使用を可能にする。このような方法では、代替パストラフィックは、無損失リンクのみを横断し、したがって、どのリンクにも輻輳を追加して招くことはなく、システムスループットの劣化の可能性がなくなる。無損失手法の場合、各ユーザは、自身のトラフィック割り当てを適応的に変更して、ネットワーク全体に有害な影響を与えることなく利得を最大にしようと試みる。以下のルール、すなわち、
・パス（デフォルト又は代替）が損失のない場合、そのパスの割り当てを増加させること、及び、
・代替パスが、許される限界を超える損失を有する場合、そのパスの割り当てを減少させること、
に従う勾配降下アルゴリズムがこれを達成する。
【００３６】
上記ルールから、代替パスは、デフォルトパスとは異なる取り扱いを受けることは明らかである。すなわち、ユーザは、デフォルトパスについてのみ無制限な使用を有し、損失のない代替パスしか使用できない。したがって、無損失方式は、デフォルト方式と比較したスループットの劣化が起きないように保証されるという利点を有する。
【００３７】
次に図４を参照して、本発明の実施の形態による、異なる個数の代替パスについての例示の性能損失対トラフィック負荷の一組のグラフ４０２、４０４、４０６、及び４０８が示されている。マーカ「×」は、無制限方式の性能がどのくらいの頻度で（パーセントで）デフォルト方式を下回ったかを示し、マーカ「○」は、無損失方式の性能がどのくらいの頻度で（パーセントで）デフォルト方式を下回ったかを示している。図４に示すように、無制限方式は、全トラフィックが２００Ｍｂｐｓを超えた時に、デフォルト方式よりも性能が低くなり始める。３００Ｍｂｐｓのトラフィックでは、無制限方式は、回数の９０％を超えて、デフォルト方式よりも性能が低くなる可能性がある。２００Ｍｂｐｓという数字は、この例では特別な意味を有する。すなわち、この数字は、ほとんどのネットワークリンクが飽和すると予想される前に、ネットワークが扱うことができるトラフィック量である。したがって、図４のグラフは、無制限方式が、（たとえば、グラフ４０２、４０４、４０６、及び４０８に示すように）ネットワークが飽和するかなりの数のケースにおいて、デフォルト方式と比較して性能が劣化する可能性があることを示している。また、すべての状況において、無損失方式は、（たとえば、同じくグラフ４０２〜４０８に示すように）デフォルト方式と少なくとも同じシステムスループットを達成することにも留意されたい。すなわち、無損失方式は、無損失のオーバーレイパスのみを使用するので、ネットワークの他のストリームの損失率を増大させる可能性はない。
【００３８】
したがって、無損失方式を利用することは、デフォルトパスが十分でないことが判明した時に必要とされるスループットを供給するための方法である。加えて、無損失方式の設計使用ルール（design usage rule）により、個々のユーザの利己的な振る舞いがシステムの大惨事に変換されないことが保証される。したがって、本発明の実施の形態を利用することによって、場合によっては不十分な性能が達成されるというリスクなしに、より良い性能が実現される。
【００３９】
次に図５を参照して、本発明の一実施の形態による、複数のパスを使用してネットワーク上でデータを転送するためのステップのフローチャートが示されている。一般に、無損失方式によって、デフォルトパスのみの無制限な使用が可能になる。たとえばオーバーレイネットワークによって提供されるどの追加パスも、輻輳がそれら追加パスに生じない（たとえば、損失率が、小さなしきい値よりも低い）範囲内において使用することができる。追加パスは輻輳を受けないので、他のトラフィックに対して追加パス使用の不利な影響がないことが保証され、それによって、ネットワークの性能劣化は引き起こされない。加えて、実施の形態は控えめに見えるかもしれないが、無損失方式は、本明細書で説明したような広範囲の状況にわたって無制限方式及びダイレクトネットワーク方式のより良いものに近い性能を提供する。
【００４０】
次に図５のステップ５０２を参照して、一実施の形態では、データが、ネットワークのデフォルトパスにわたって転送される。一実施の形態では、ネットワークがデフォルトパスを選択する。図１の図１００に示すように、デフォルトパスは、ソースからデスティネーションへのパスを提供するパス１０２とすることができる。別の実施の形態では、ユーザがデフォルトパスを選択することができる。
【００４１】
次に図５のステップ５０４を参照して、一実施の形態では、デフォルトパスのデータ損失率が求められる。たとえば、デフォルトパスを通るデータフローが維持されている間、デフォルトパスの損失率が測定される。図１のデフォルトパス１０２の損失が特定されないか、又は、検出されない場合、それ以上何らの動作も取る必要はない。
【００４２】
次に図５のステップ５０６を参照して、一実施の形態では、デフォルトパスのデータ損失率が第１のしきい値を超えている場合、第１の代替パスが選択され、第１の代替パスのデータ損失率が求められる。すなわち、デフォルトパス（たとえば、図１の１０２）の損失が一旦特定されると、代替パス（たとえば、図１の１０４）が特定される。一実施の形態では、ネットワークが代替パス１０４を選択する。別の実施の形態では、代替パス１０４は、無制限ネットワークによって選択されないが、その代わり、別個のエンティティによって選択される。換言すれば、代替パス１０４は、ソフトウェア、ユーザ、デフォルト等によって選択することができる。
【００４３】
（図１の）代替パス１０４の選択期間中、提案された又は割り当てられた代替パス１０２は、その代替に何らかのデータを転送する前にデータ損失率のチェックを受ける。すなわち、代替パス１０４が選択された後、代替パス１０４は、何らかのデータ又はデータの一部がデフォルトパスからその代替パスに渡される前に、第２のしきい値未満のデータ損失率を有していなければならない。一実施の形態では、代替パス１０４がチェックを受けた時、０．１％以上のデータ損失率が存在する場合、代替パス１０４へのデータの転送は行われない。その際、代替パス１０４は、過負荷でない場合がある。この制限は、或るアプリケーション又はデータファイルが、ネットワークの２つ以上のパスを過負荷にして、複数のネットワークパスにわたって損失を引き起こすことを防止するものである。
【００４４】
その上、デフォルトパスのデータ損失率がどんなに大きくても、代替パスは、データ損失率を招かない。すなわち、データ損失率は、すべての可能なパス間で等しくされるまで、ネットワークの各パスにわたって拡散されない。その代わり、データ損失率は、デフォルトパスにのみ発生する場合がある。したがって、データ損失がデフォルトパスで発生しているが、「利己的な」方法でネットワークにわたって拡散されていない。たとえば、デフォルトパスは、８０パーセントの損失を有する場合があり、代替パスは、依然として無損失のままである。
【００４５】
別の実施の形態では、複数の代替パスが存在することができ、各パスをデータ損失について監視することができる。或る代替パスが最初にデータ損失を示していたが、その後、データ損失を示さない場合、デフォルトパスからのデータの一部を、現在使用が自由なその代替パスへ渡すことができる。したがって、代替パスの個数は、ネットワークにおける代替パスの最大数までとすることができる。一実施の形態では、可能な代替パスに対する唯一の制限は、ネットワークにおけるノード数である。別の実施の形態では、各データ転送は、デフォルトパス及び一定の個数の代替パスに制限することができる。たとえば、一実施の形態では、代替パスの制限を４つとすることができる。４つのパス制限を本明細書で述べたが、パス制限は、ネットワークで利用可能な代替パスの最大数を含めてその最大数までの任意の個数とすることができることが十分理解される。
【００４６】
次に図５のステップ５０８を参照して、一実施の形態では、代替パスのデータ損失率が第２のしきい値よりも小さい場合、デフォルトパスからのデータの一部が、その代替パス（又は複数の代替パス）へ渡される。加えて、代替パスへ渡されるデータ量は、デフォルトパスにわたる負担をさらに取り除く（又は損失率を削減する）ために増加させ続けることができる。たとえば、データの第２の部分を代替パスへ渡すことができる。一実施の形態では、代替パスへ渡されるデータ量は、デフォルトパスのデータ損失が第１のしきい値を下回るか、又は、代替パスが第２のしきい値よりも高いデータ損失を示し始めるかのいずれかまで増加し続けることができる。
【００４７】
次に図５のステップ５１０を参照して、一実施の形態では、第１の代替パスのデータ損失率が第２のしきい値を満たすか又は超えるまで、データの追加部分が代替パスへ転送される。すなわち、代替パスにわたって転送されるデータの部分が代替パスをそのしきい値よりも上に押し上げないように、当該代替パスにわたって転送されるデータの部分は制限される。たとえば、代替パスへ転送されるデータは、第２のしきい値を超えるデータ損失が代替パスで発生するまでしか増加させることができない。すなわち、デフォルトパスから代替パスへ転送されるデータは、代替パスのデータ損失率が０．１％に達すると制限することができる。０．１％が本明細書で使用されているが、代替パスへ転送されるデータを制限するための第２のしきい値データ損失は、ネットワーク又はネットワークのアドミニストレータ（若しくはユーザ）のいずれかによって指示された任意の損失パーセンテージとすることができる。
【００４８】
一実施の形態では、代替パスがデータ損失を一旦示し始めると、代替パス（たとえば、図１の１０４）へ転送されるデータは、その代替パスのデータの損失がなくなるデータ転送レートに削減される。一実施の形態では、この削減は、デフォルトパスの損失率にかかわらず、代替パスに対して行われる。したがって、デフォルトパスのデータ損失を削減するためにデータをさらに散布することが必要とされる場合、データ損失を有しない第２の代替パスの検索を行わなければならない。たとえば、第２の代替パスが選択されるか又は割り当てられる。この第２の代替パスのデータ損失率が求められる。第２の代替パスのデータ損失率が第３のしきい値よりも小さい場合、データの一部が、第２の代替パスへ転送される。一般に、第２（又は第４若しくは第１０）の代替パスに関する動作及びルールは、第１の代替パスに関するルールと同じである。したがって、データは、デフォルトパス及び１つ又は２つ以上の代替パスを通過させることができる。したがって、或るアプリケーション又はデータファイルの有害な影響が複数のネットワークパスの動きを妨げず、且つ、全体のネットワーク動作に悪影響を与えることなく、マルチパスネットワークの効率的な働きが可能になる。
【００４９】
一方、一実施の形態では、デフォルトパスの損失率がどれほど高くても、代替パス（複数可）は、データ損失率が、指定されたしきい値未満のままである。加えて、代替パスのしきい値は、ネットワークのユーザ又はアドミニストレータが調整又は指定することができる。加えて、各しきい値は、ネットワークのユーザ若しくはアプリケーションの数、又は、ネットワークを通過しているデータトラフィックに基づいて動的に調整可能とすることができる。たとえば、単一のアプリケーションのみがネットワーク上でデータを通過させている場合、代替パス（複数可）のしきい値は、より高くすることができる。一方、複数のユーザが存在する場合、代替パスのしきい値は、より低くすることができる。
【００５０】
一実施の形態では、しきい値は、ネットワーク使用量に基づいてリアルタイム又は準リアルタイムで変化させることができる。換言すれば、単一のユーザがネットワークに存在し、大量のデータを通過させている場合、代替パスのしきい値は高くすることができるが、別のユーザ又はアプリケーションがネットワークにアクセスした時、代替パスのしきい値は低くすることができる。その場合、１つ又は複数の代替パスが、それら代替パスが転送しているデータの部分を削減すると、最初のユーザは、デフォルトパスにわたるデータ損失率が際立って増加することに気付くことができる。
【００５１】
次に図６を参照して、本発明の一実施の形態による、複数パスをサポートするネットワーク上でデータを転送するためのデバイスが示されている。デバイス６００は、デフォルトパス比較器６０８を有するデフォルトパスディターミナ（determiner：求値器）６０６と、代替パス比較器６１６を有する代替パスディターミナ６１４とを含む。一実施の形態では、デバイス６００のコンポーネントは、ネットワークに分散させることもできるし、ネットワークの中央に配置することもできる。すなわち、コンポーネントは、たとえば、中央ノードに存在することできるし、すべての異なるノードに存在することもできるし、それらの任意の組み合わせとすることもできる。
【００５２】
本明細書で詳細に説明したように、一実施の形態では、データ６０２は、ネットワークのノード６１８（たとえば、デスティネーション）へ移動する必要がある。最初に、デフォルトパス６０４が利用されて、転送動作が実行される。デフォルトパス６０４がデータを転送している間、デバイス６００は、データ転送速度を監視している。すなわち、デバイス６００内では、デフォルトパスディターミナ６０６が、デフォルトパス６０４のデータ損失率を監視する。加えて、デフォルトパスディターミナ６０６では、デフォルトパス６０４のデータ損失率を第１のしきい値と比較するデフォルトパス比較器６０８のロジックが動作している。換言すれば、第１のしきい値が、（自動的に又は手動のいずれかで。一実施の形態では、リアルタイムの調節を受けて）デフォルトパス比較器６０８に入力される。デフォルトパスディターミナ６０６によって求められたデータ損失率がデフォルトパス比較器６０８の第１のしきい値以上である場合、動作が取られる。
【００５３】
一実施の形態では、デバイス６００が代替パスを選択する。代替パスは、自動的に選択することもできるし、手動で選択することもできる。たとえば、代替パスは、ユーザ入力６１３によって選択することができる。代替パス６１２が一旦選択されると、デバイス６００は、代替パスディターミナ６１４を利用して、代替パス６１２のデータ損失率を求める。代替パス比較器６１６は、その後、（上述したのと同じ方法で）代替パスのデータ損失率を、そこに記憶された第２のしきい値と比較する。代替パス比較器６１６が、代替パスが第２のしきい値未満のデータ損失率を有すると判断した場合、データ６１０の一部は、デフォルトパス６０４から代替パス６１２へ渡される。一方、代替パス比較器６１６が、代替パス６１２が第２のしきい値以上のデータ損失率を有すると判断した場合、データ６１０の一部はそれ以上代替パス６１２に渡されない。
【００５４】
すなわち、代替パス６１２がデフォルトパス６０４を支援してすでにデータを通過させているかどうかは重要ではない。いずれにしても、代替パスが、しきい値以上のデータ損失率を有する場合に、より多くのデータ量がデフォルトパス６０４から代替パス６１２へ渡されることはない。
【００５５】
一実施の形態では、本明細書で述べたように、多数の代替パス６１２がデータ６１０の複数の部分を通過させることができる。別の実施の形態では、単一のデフォルトパス６０４のデータを通過させる代替パス６１２の個数を制限することができる（たとえば、４つのパスに制限される）。本明細書では４つが述べられているが、任意の個数を制限個数とすることができる。さらに、代替パスの個数は、動的に制限することもできる。たとえば、１人のユーザしか存在しない場合、代替パスの個数は、ネットワークの最大数とすることができる。一方、複数のユーザが存在する場合、各ユーザに利用可能な代替パスの個数は、ネットワークの最大数の一部に制限することができる。
【００５６】
たとえば、８つの可能な代替パスを有するネットワークにおいて、単一のユーザのみがネットワークにアクセスしている場合、全部で８つの代替パスを利用可能にすることができる。一方、第２のユーザがネットワークにアクセスした場合、双方のユーザには、それぞれ４つの代替パスへのアクセスしか許可することができない。加えて、４人のユーザがネットワークにアクセスした場合、各ユーザは、２つの代替パスしか受け取ることができない。別の実施の形態では、代替パスへのアクセスは、ユーザの必要なものに制限することができる。たとえば、１人のユーザは、４つの代替パスへのアクセスを受け取ることができるのに対して、それ以外の３人のユーザは、それぞれ１つの代替パスのみへのアクセスを受け取る。さらに別の実施の形態では、２人のユーザが、同じ代替パス６１２を共有することができる。したがって、代替パスの分配は、固定することもできるし、可変とすることもでき、ユーザ、トラフィック、アプリケーション、ステータス等に基づくことができることが十分理解される。
【００５７】
このように、本発明の実施の形態は、複数のパスを使用してネットワーク上でデータを転送するための方法及びシステムを提供する。無損失方式を使用することによって、ネットワークノードの混雑及びネットワークトラフィックの劣化を大幅に削減することができる。その上、データ転送は、オーバーレイネットワークの非損失パスを使用できることにより、ダイレクトパスネットワークに対して増加される。加えて、第２、第３、第４等の追加の非損失パスをネットワークに保持するとともに、パス共有ルールを設けることによって、ユーザは、別のユーザが複数の代替パスの動きを妨げることを心配する必要がない。すなわち、データは、ダイレクトパスの損失しか引き起こすことができず、代替パスの損失が始まるまでしか提供されないので、ネットワークは、アプリケーション又はデータストリームがネットワーク全体を通る複数のパスで動作することによる動きの妨げを受けなくなる。
【００５８】
本発明の実施の形態は、上記のように説明される。本発明を特定の実施の形態で説明してきたが、本発明は、このような実施の形態によって限定されるものと解釈されるべきでなく、逆に、添付の特許請求の範囲に従って解釈されるべきであることが十分理解されるべきである。
【図面の簡単な説明】
【００５９】
【図１】本発明の一実施の形態による一例示のコンテンツ配信ネットワークの図である。
【図２】伸縮性のあるネットワークトラフィック対伸縮性のないネットワークトラフィックのグラフである。
【図３】本発明の一実施の形態による、複数のパスを使用してデータネットワーク上でデータを転送するためのステップのフロー図である。
【図４】本発明の一実施の形態による、例示の性能損失対ノード及びトラフィック負荷を示す一組のグラフである。
【図５】本発明の一実施の形態による、複数のパスを使用してデータネットワーク上でデータを転送するためのステップのフローチャートである。
【図６】本発明の一実施の形態による、複数のパスを使用してデータネットワーク上でデータを転送するためのデバイスのブロック図である。
【符号の説明】
【００６０】
１００・・・ネットワーク
１０２・・・ダイレクトパス
１０４・・・オーバーレイパス
６００・・・デバイス
６０２・・・データ
６０４・・・デフォルトパス
６０６・・・デフォルトパスディターミナ
６０８・・・デフォルトパス比較器
６１０・・・データの一部
６１２・・・代替パス
６１３・・・ユーザインターフェース
６１４・・・代替パスディターミナ
６１６・・・代替パス比較器
６１８・・・デスティネーション
【図１】
2008509602.tif 000003
【図２】
2008509602.tif 000004
【図３】
2008509602.tif 000005
【図４】
2008509602.tif 000006
【図５】
2008509602.tif 000007
【図６】
2008509602.tif 000008
【国際調査報告】
2008509602.tif 000009
2008509602.tif 000010