(57)【特許請求の範囲】
【請求項１】
送信側ノードから１つまたは複数の受信側ノードにネットワークを通してデータ・ストリームを転送するための方法であって、
前記送信側ノードと前記受信側ノードの間の受信者ノードが、前記送信側ノードにより送信された、前記データ・ストリームの一部および前記データ・ストリームに注入された１つまたは複数のマーカであって、前記データ・ストリーム内の参照ポイントを指定するマーカを有するマーク付きストリームを受信するステップと、
前記受信者ノードが、前記マーク付きストリームを前記受信者ノードのバッファ内に格納するステップと、
前記受信者ノードが、前記マーク付きストリームを１つまたは複数の次の受信者ノードに転送するステップと、
前記受信者ノードが、前記次の受信者ノードの１つからの要求に応答して、指定のマーカ以降のストリーム・データを前記次の受信者ノードの１つに転送するステップと
を含む方法。
【請求項２】
前記マーカが、一意の識別子を有する認識可能なビット・フィールドである、請求項１に記載の方法。
【請求項３】
前記マーカが、前記送信側ノードまたは前記受信者ノードにより前記データ・ストリームに注入される、請求項１に記載の方法。
【請求項４】
前記格納するステップが、前に受信したマーカの記録を含むマーカ索引を最も最近受信したマーカの記録で更新するステップを含む、請求項１に記載の方法。
【請求項５】
前記マーカ索引が、受信した各マーカに対して、一意の識別子および前記バッファ内の位置を記録する、請求項４に記載の方法。
【請求項６】
前記受信側ノードが、前記データ・ストリームをアプリケーションに配信するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記配信するステップにより配信されるデータ・ストリームが、前記マーカのうちの１つから開始する、請求項６に記載の方法。
【請求項８】
前記配信するステップにより配信されるデータ・ストリームが、前記マーカのうちの１つの後の指定された位置から開始する、請求項６に記載の方法。
【請求項９】
前記１つまたは複数の次の受信者ノードが、前記マーク付きデータ・ストリームの転送、および１つまたは複数のアプリケーションに配信するために前記マーク付きデータ・ストリームの受信の両方を行うことができる、請求項１に記載の方法。
【請求項１０】
送信側ノードから受信側ノードへネットワークを通してのデータの中断したトランスポートを再開するための方法であって、
前記受信側ノードが、ストリーム・データおよび前記ストリーム・データに注入された１つまたは複数のマーカであって、前記ストリーム・データ内の参照ポイントを指定するマーカを含むマーク付きストリームを、前記送信側ノードと前記受信側ノードの間の転送ノードから受信するステップと、
前記転送ノードが故障したときに、前記受信側ノードが、指定したマーカ以降のストリーム・データを前記転送ノードの代わりとなる他の転送ノードに要求するステップと、
前記他の転送ノードが、前記指定したマーカ以降のストリーム・データを前記受信側ノードに転送するステップと
を含む方法。
【請求項１１】
ネットワークを通してデータを転送するためのシステムであって、
ストリーム・データを送信する送信側ノードと、
前記ストリーム・データを受信する受信側ノードと、
前記送信側ノードと前記受信側ノードの間において前記ストリーム・データを転送する複数の転送ノードとを含み、
前記送信側ノードまたは前記転送ノードが、前記ストリーム・データ内に参照ポイントを指定するマーカを注入し、
前記ストリーム・データを前記受信側ノードに転送する転送ノードが故障したときに、前記受信側ノードが、指定したマーカ以降のストリーム・データを故障した転送ノードの代わりとなる他の転送ノードに要求し、
前記他の転送ノードが、前記指定したマーカ以降のストリーム・データを前記受信側ノードに転送する、システム。
【請求項１２】
送信側ノードから１つまたは複数の受信側ノードに、ネットワークを通してデータ・ストリームを転送するためのプログラムであって、
前記送信側ノードにより送信された、前記データ・ストリームの一部および前記データ・ストリームに注入された１つまたは複数のマーカであって、前記データ・ストリーム内の参照ポイントを指定するマーカを有するマーク付きストリームを受信するステップと、
前記マーク付きストリームをバッファ内に格納するステップと、
前記マーク付きストリームを１つまたは複数の次の受信者ノードに転送するステップと、
前記次の受信者ノードの１つからの要求に応答して、指定のマーカ以降のストリーム・データを前記次の受信者ノードの１つに転送するステップと
をコンピュータに実行させるプログラム。
【請求項１３】
送信側ノードから受信側ノードへネットワークを通してのデータの中断したトランスポートを再開するためのプログラムであって、
ストリーム・データおよび前記ストリーム・データに注入された１つまたは複数のマーカであって、前記ストリーム・データ内の参照ポイントを指定するマーカを含むマーク付きストリームを、前記送信側ノードと前記受信側ノードの間の転送ノードから受信するステップと、
前記転送ノードが故障したときに、指定したマーカ以降のストリーム・データを前記転送ノードの代わりとなる他の転送ノードに要求するステップと、
前記指定したマーカ以降のストリーム・データを前記他の転送ノードから受信するステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータ・システムおよびコンピュータ・ネットワークに関し、特に、コンピュータ・ネットワークを通してのコンテンツの配信に関する。より詳細には、本発明は、コンピュータ・ネットワークを通してデータを適応転送するための方法および装置に関する。
【背景技術】
【０００２】
図１は、ネットワークを通してデータを転送するためのシステム１００の一実施形態の略図である。送信側１０２（例えば、サーバ）から１つまたは複数の受信側１０４にデータのストリーム１１２を経路指定するために、（とりわけ、オーバレイ・ネットワーク、エンド・システム・マルチキャスト、プロキシ・サーバ、ネットワーク・アドレス変換、およびプロトコル・トンネリングを含む）広い範囲のエンドツーエンド・コンピューティング・アプリケーションは、仲介者（intermediary）または転送ノード１０６１〜１０６ｎ（例えば、コンピューティング装置またはルータ）を使用する。受信側１０４は、データを１つまたは複数のコンピューティング・アプリケーション１０８に配信することができる。
【０００３】
システム１００のようなシステムに関する典型的な問題は、任意の転送ノードのところで故障または混乱が起こると、エンドツーエンド・チェーンが混乱し、受信側へのデータの配信が不完全になることである。この問題は大型のネットワークの場合に特に問題になる。何故なら、ノードが故障を起こす確率は、実施する転送ノードの数が増大するにつれて増大するからである。転送ネットワーク内のノード故障を処理する従来の解決方法としては、データ・ソースと受信側間の送信制御プロトコル／インターネット・プロトコル（ＴＣＰ／ＩＰ）セッションのようなソースをベースとする修復、パケット数をベースとする再送信要求、および種々のアプリケーション特定およびコンテンツ特定の障害から回復するスキーム（例えば、ファイルの開始からの特定のバイト・オフセットのところでのファイル・トランスポート・プロトコルの再開、または特定のフレーム数のところでのビデオ送信の再開）がある。しかし、これらの従来の解決方法は、スケーラビリティの制限、および異質の輸送を使用する、または一般的な（コンテンツ特定ではない）データ・ストリームを配信するネットワークを通しての使用に適合できないことを含む多数の制限を受ける。それ故、従来の解決方法は、コンテンツから独立した方法で、複数の二地点間プロトコルを使用して適合するように変化するネットワークを通してデータを配信するのには適していない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
それ故、コンピュータ・ネットワークを通して障害回復力のあるデータ転送を行うための方法および装置が求められている。
【課題を解決するための手段】
【０００５】
一実施形態の場合には、本発明は、コンピュータ・ネットワークを通して障害回復力のあるデータ転送を行うための方法および装置である。一実施形態の場合には、例えば、送信ノードのところでデータ・ストリーム内にマーカが導入され、転送ノードまたは受信側あるいはその両方がデータ・ストリーム受信を効率的に追跡できるようにする。マーカは、データ・トランスポート・プロセスに対するチェックポイントとして機能し、各転送ノードおよび受信側のところで識別され、索引が付けられる。各受信側は、データをアプリケーションに配信する前にマーカをセーブし、それによりすべての先行するデータが、アプリケーションに配信されたことが確認されるデータ・ストリーム内のあるポイントを指定する。それ故、転送ノードが故障した場合、受信側は、マーカから始まるデータを提供することを別の転送ノードに指定することにより、別の転送ノードからストリーム・データを要求することができる。
【０００６】
本発明の上記実施形態を達成し、詳細に理解することができる方法、上記短く要約した本発明のより詳細な説明は、添付の図面に示すその実施形態を参照することにより入手することができる。しかし、添付の図面は、本発明の典型的な実施形態を示しているものであって、本発明の範囲を制限するものと見なすべきではないことに留意されたい。何故なら、本発明は、他の同様に効果的な実施形態に適用することができるからである。
【０００７】
容易に理解できるように、各図面に共通な同じ要素を示すために、できる限り同じ参照番号を使用している。
【発明を実施するための最良の形態】
【０００８】
本発明は、コンピュータ・ネットワークを通して障害回復力のあるデータ転送を行うための方法および装置である。一実施形態の場合には、転送ノードの故障、性能の劣化、問合せ、リソース使用のアンバランス等のようなトリガ条件が、データ・ストリームの送信受信を正確に再開するために、ネットワーク適合を開始する。
【０００９】
図２は、本発明による送信側から１つまたは複数の受信側に障害回復力のあるデータ転送を行うことができるようにするための方法２００の一実施形態を通してのデータの流れを示すフローチャートである。方法２００は、ステップ２０２において開始し、ステップ２０４に進み、そこで送信ノードまたは転送ノード（例えば、送信側１０２または図１の転送ノード１０６のうちの任意の１つ）が、データ・ストリームの少なくとも一部を（送信側の場合には）入手し、または（転送ノードの場合には）受信する。一実施形態の場合には、データ・ストリームは、単に遥かに大きなデータ・ストリームの一部または任意の大きさのデータ・セグメントであってもよい。すなわち、もっと大きいデータ・ストリームの「チャンク」または「部分」のシーケンスが、送信ノードから受信ノードに送られる。ステップ２０６において、送信側または転送ノードは、データ・ストリームの一部内にマーカを注入し、「マーク付き」データ・ストリームを、さらに修正し、または修正しないで、二地点間の信頼性のあるトランスポート・プロトコル（例えば、ＴＣＰ／ＩＰ等のようなパケット損失回復力のあるプロトコル）を介して、ネットワーク内の１つまたは複数の次の受信者ノード（例えば、１つまたは複数の以降の転送ノードまたは受信ノード）に転送する。マーカは一般のデータ・ストリーム内の参照点を指定し、一実施形態の場合には、一意の識別子を有する認識することができるビット・フィールドである。マーカは、予約ビット・シーケンス、固定マーカ間オフセット、または前のマーカが指定したオフセットにより認識することができる。それ故、マーカをデータ・ストリーム内に周期的に注入することができ、そのため複数のマーク付きのデータ・ストリームがネットワークを通してトランスポートされる。
【００１０】
ステップ２０６においてマーカを注入した後で、方法２００は２つの可能な以降のプロセスのうちの少なくとも一方に分岐する。ステップ２０８〜２１０において、方法は、転送ノードの機能によりステップを実行する。ステップ２０９〜２１４において、方法２００は、受信ノードの機能によりステップを実行する。
【００１１】
ステップ２０８において、方法２００は、マーク付きデータ・ストリームの受信者が転送ノードであるか否かを問い合わせる。方法２００が受信者が転送ノードであると判定した場合には、方法２００はステップ２１０に進み、そこで方法２００は、受信データ・ストリームをチェックし、転送ノードのローカル・バッファ内にデータを格納し、転送ノードのところでマーカ索引（marker index）を生成または更新する。一実施形態の場合には、方法２００が更新するマーカ索引は、２つの重要な構成要素、すなわち、（１）最も最近受信したマーカの記録、および（２）転送ノードが前に受信し、格納している各マーカの記録を含む。方法２００がマーカ索引を更新すると、方法２００はマーク付きデータ・ストリームを、ネットワーク内の次の受信者（例えば、１つまたは複数の他の転送ノードまたは受信側）に転送する。マーク付きデータ・ストリームは、ステップ２１０からのループで示すように、方法２００の点、すぐ次のステップ２０６から開始する次の受信者ノードにより処理される。それ故、すべての転送ノードは、マーク付きデータ・ストリームを受信し、このマーク付きデータ・ストリームを次の転送ノードまたは受信側に中継し、マーカを索引する。
【００１２】
図３は、図２のステップ２１０において方法２００により更新されたマーカ索引のような本発明によるマーカ索引３００の一実施形態の略図である。一実施形態の場合には、マーカ索引３００は表である。図に示すように、マーカ索引３００は、各マーカ（例えば、マーカＭ１〜Ｍ３）に対して、マーカの一意の識別子およびローカル・バッファ内のその位置を格納する。図４を参照しながら以下にさらに説明するように、この格納した情報は、例えば、転送ノードの故障により喪失したデータを回復するために使用することができる。
【００１３】
図２にもどって説明すると、方法２００がステップ２０８においてマーク付きデータ・ストリームの受信者が転送ノードでないと結論した場合には、方法２００は終了する。
【００１４】
また、ステップ２０６においてマーカを注入した後で、方法２００は、ステップ２０９において受信者が受信ノードであるか否かについて問合せを行う。方法２００が、受信者が受信ノードであると結論した場合には、方法２００は、ステップ２１２に進み、マーカを発見するまで受信側が受信したストリーム・データをキューイングする。ステップ２１４において、方法２００は、マーカをセーブして、キューイングされたデータ（すなわち、データ・ストリーム内のマーカに先行するすべての配信していないマークが付いていないデータ）をもとのデータ・ストリームを必要とするプロセス（例えば、アプリケーションまたは格納プロセス）に配信する。方法２００がステップ２０８において受信者が受信ノードでないと結論した場合には、方法２００は終了する。
【００１５】
一実施形態の場合には、１つまたは複数のノードは、転送ノードでもあり、受信ノードでもある。すなわち、あるノードは、アプリケーションに配信するためにデータを受信するように適合させることもできるし、また他のノードに受信データを転送するように適合させることもできる。それ故、このノードは、方法２００が含んでいる転送および受信方法の両方を実行することができる。それ故、転送および受信プロセス（例えば、それぞれステップ２０８〜２１０および２０９〜２１４）は、シーケンシャルな参照番号で指定されるが、参照番号はプロセスを行う順序を含んでいない。それ故、当業者であれば、転送および受信方法が別々に行われること、およびこれらの方法を実際に同時に行うことができること、または任意の順序で順次行うことができることを理解することができるだろう。それ故、ステップ２０８〜２１６に適用した場合、参照番号のシーケンスは如何なる意味でも制限することを目的としていない。
【００１６】
それ故、データ・ストリーム内に注入したマーカは、データ・トランスポート・プロセスのチェックポイントを示す。受信側のところでマーカをセーブすることにより、方法２００は、待機しているアプリケーションにすべての先行するデータが、高い信頼性で正しい順序で配信された、データ・ストリーム内のポイントを指定する。また、方法２００は、すべての後続のデータが配信されていないデータ・ストリーム内のポイントを指定する機能も提供する。このセーブしたマーカ情報は、例えば、転送ノードの故障により喪失したデータを回復するために使用することができる。
【００１７】
図４は、データ・ストリーム内の喪失したデータを回復するための方法４００の一実施形態を示すフローチャートである。例えば、方法４００は、転送ノード（例えば、図１の転送ノード１０６）が、故障し（例えば、ネットワークからの切断または電源障害により）、そのため以降の受信者にデータを転送するのを止めた場合に実行することができる。方法４００はステップ４０２から開始し、ステップ４０４に進み、ここで方法４００は、転送ノードの故障を識別し、受信側（または以降の転送ノード）を別の転送ノードまたは「バックアップ・ノード」（例えば、ルーティング経路内の故障したノードに先行するノード）に接続する。別の方法としては、方法４００は、受信側をデータ・ストリームを依然として受信している故障した転送ノードの任意の「姉妹」ノードに接続することができる。一実施形態の場合には、バックアップ・ノードは、効率のために選択される。例えば、故障したノードが図１のノードＸｎである場合には、バックアップ・ノードは、ノードＸ１またはノードＸｎ＋１となるように選択することができる。正しいノードの選択は、距離、遅延、計算コスト等に基づいて行うことができる。
【００１８】
次に、方法４００は、ステップ４０６に進み、ここで方法４００は、バックアップ・ノードから受信側がセーブした最後のマーカＭから開始するデータ・ストリームを要求する。他の実施形態の場合には、方法４００は、最後のマーカＭの後の指定した位置（例えば、マーカＭの後の４ビット目）から開始するストリーム・データを要求することができる。この要求は、マーカＭに対する一意の識別子を含む。ステップ４０７において、方法４００は、バックアップ・ノードがステップ４０６において行った要求を受け入れるか否かについて問い合わせする。バックアップ・ノードがこの要求を拒否した場合には、方法４００はステップ４０４に戻り、他のバックアップ・ノードに接続する。別の方法としては、バックアップ・ノードがステップ４０７において要求を受け入れた場合には、方法４００は、バックアップ・ノードが、バックアップ・ノードのマーカ索引内のマーカＭを参照することができるようにする。マーカＭが存在する場合には、バックアップ・ノードは、ローカル・バッファ内のマーカＭの位置を始点として使用して、マークのついたデータ・ストリームの送信を開始する。一実施形態の場合には、マーカＭのポイントの後のローカル・バッファ内に常駐する任意のデータを廃棄する。
【００１９】
ステップ４０８において、方法４００は、マーカＭの直後の位置に受信側のキュー「書込みポインタ」をリセットする。また、方法４００は、ローカル・バッファ内の書込みポインタの後のデータを削除し、受信側はここで新しい転送ノードからの新しい接続を通してキューイング・データを開始する。マーク付きデータ・ストリームが、バックアップ・ノードからの新しい接続を通して受信側に到着すると、到着したデータ・ストリームが、書き込みポインタにより指定される、受信側のローカル・バッファ内のマーカＭ以降のデータに上書きされる。他の実施形態の場合には、方法４００は、複数のバックアップ・ノードからのマーク付きデータ・ストリームの個々の部分を要求することができる。
【００２０】
ステップ４１０において、方法４００は、次のマーカＭ＋１が受信側のところに到着したか否かについて問い合わせる。次のマーカＭ＋１が到着している場合には、方法４００は（マーカＭを引いた）受信側によりキューイングされたデータを、ステップ４１２においてデータを要求しているアプリケーションに配信する。次のマーカＭ＋１が到着していない場合には、方法４００はバックアップ・ノードからの新しい接続を通してデータを引き続きキューイングする。当業者であれば、方法４００のステップ４０８〜４１２は、通常受信側ノードにより実行されるステップであることを理解することができるだろう。これらステップについては、受信側ノードが、喪失データの回復に関連するこのようなステップを実施することができる方法を説明するために、方法４００のところですでに説明した。
【００２１】
それ故、方法４００は、中断の時点でデータ送信を再開することにより、故障を正確にまた効率的に修復することができる。さらに、修復が近くの転送／バックアップ・ノードとの通信を要求しているだけなので、修復経路（repair path）は短く、ネットワーク負荷が公平に分配される。また、方法４００は、任意の信頼性のある二地点間トランスポート・プロトコルによりアプリケーション層のところで動作し、既存の二地点間プロトコルをテコ入れすることができ、再構成およびマルチプロトコル転送を可能にする。それ故、方法４００は、トランスポート・プロトコルから独立して、またデータ・ストリームのコンテンツから独立して動作する。
【００２２】
図５は、汎用コンピューティング装置５００により実施される本発明の障害回復力のある転送システムのハイレベルのブロック図である。一実施形態の場合には、汎用コンピューティング装置５００は、プロセッサ５０２、メモリ５０４、障害回復力のある転送機構またはモジュール５０５、およびディスプレイ、キーボード、マウス、モデム等のような種々の入出力（Ｉ／Ｏ）装置５０６を備える。一実施形態の場合には、少なくとも１つのＩ／Ｏ装置は、記憶装置（例えば、ディスク・ドライブ、光ディスク・ドライブ、フレキシブル・ディスク・ドライブ）である。障害回復力のある転送機構５０５は、通信チャネルを通してプロセッサと結合している物理デバイスまたはサブシステムであってもよいことを理解されたい。
【００２３】
別の方法としては、障害回復力のある転送機構５０５は、１つまたは複数のソフトウェア・アプリケーション（または例えば特定用途向け集積回路（ＡＳＩＣ）を使用する、ソフトウェアおよびハードウェアの組合わせ）により表すことができる。この場合、ソフトウェアは、記憶媒体（例えば、Ｉ／Ｏ装置５０６）からロードされ、汎用コンピューティング装置５００のメモリ５０４内のプロセッサ５０２により動作する。それ故、一実施形態の場合には、障害回復力のある転送機構５０５および先行する図面を参照しながら本明細書で説明した関連する方法は、コンピュータ読み取り可能媒体またはキャリア（例えば、ＲＡＭ、磁気または光ドライブまたはディスケット等）上に格納することができる。
【００２４】
上記方法をノードの故障からのシステムの回復を参照しながら説明してきたが、当業者であれば、本発明がコンテンツ配信の分野の他のアプリケーションを含むことができることを理解することができるだろう。例えば、任意のネットワーク再構成により、および何らかの理由で高い信頼性で確実にデータを配信するために本発明を実施することができる。他の再構成技術としては、とりわけ、ノードの集中または分散登録によるバックアップ・ノードの発見（例えば、周知のサーバまたはドメイン・ネーム・サービス（ＤＮＳ）ルックアップ）、分散ハッシュ・テーブル・ルックアップ、または放送サーチ（broadcast search）等がある。ネットワークを再構成する他の理由としては、とりわけ、性能劣化への応答、ネットワーク・リソース利用の最適化、および負荷バランス等がある。
【００２５】
それ故、本発明は、コンテンツ配信の分野における有意な進歩である。本発明は、ネットワークを通して効率的で障害回復力のあるデータ転送を行うことができるようにするための方法および装置を提供する。ネットワークは、受信側に冗長なまたは故障したデータを送信しなくても、中断の時点で正確に、効率的にデータ送信を再開することができる。送信側からデータを要求しているアプリケーションにとって、システムの故障および回復は実質的に透明である。さらに、本発明の方法はアプリケーション特定のものではなく、コンテンツが何であれ、また任意のタイプの信頼性のあるトランスポート・プロトコルにより、任意のタイプのデータ・ストリームと一緒に使用するために適合させることができる。
【００２６】
今まで本発明の好ましい実施形態について説明してきたが、本発明の他の実施形態を、本発明の基本的範囲から逸脱することなしに思い付くことができるだろう。本発明の範囲は添付の特許請求の範囲に記載してある。
【図面の簡単な説明】
【００２７】
【図１】エンドツーエンド・コンピューティング・ネットワークの一実施形態の略図である。
【図２】本発明による送信側から１つまたは複数の受信側に障害回復力のあるデータ転送を行うことができるようにするための方法の一実施形態を示すフローチャートである。
【図３】図２のシステムを使用するコンテンツを配信するための１つの方法を示す表である。
【図４】データ・ストリーム内の失われたデータを回復するための方法の一実施形態を示すフローチャートである。
【図５】汎用コンピューティング装置により実施される本発明の障害回復力のある転送システムのハイレベルのブロック図である。
【図１】
0004857261.tif 000002
【図２】
0004857261.tif 000003
【図３】
0004857261.tif 000004
【図４】
0004857261.tif 000005
【図５】
0004857261.tif 000006