(57)【要約】ネットワークを介して圧縮ビデオ・パケットを送信する方法は、送信区間を離散的タイムスロットへ区分する工程、送信ノードから受信ノードへネットワークを介してスケジューリング・パケットを送る工程、受信ノードの応答を評価して異なるタイムスロットでのネットワークの信頼度を決定する工程、および評価工程に従って圧縮ビデオ・パケットを配信するため1つまたは複数のタイムスロットを選択する工程を含む。他の送信機は、同様に、受信ノードへまだ割り振られていないタイムスロットで送信するように準備することができる。2009509462.tif 000003
2009509462.tif 000002
【特許請求の範囲】
【請求項１】
以下の工程を含む、コンピュータ・ネットワークを介して圧縮ビデオ・パケットを送信する方法：
（1）送信ノードから、意図された受信ノードへスケジューリング要求を送信する工程；
（2）意図された受信ノードから、送信されたスケジューリング要求への応答を受信する工程；
（3）意図された受信ノードへの送信が他の送信機と衝突しないタイムスロットを決定するために、該応答を評価する工程；および
（4）工程（3）で評価されたタイムスロットを使用して、送信ノードから、意図された受信ノードへ圧縮ビデオ・パケットを送信する工程。
【請求項２】
圧縮ビデオ・パケットがDV圧縮標準に従って圧縮される、請求項1記載の方法。
【請求項３】
工程（1）が、意図された受信ノードへ質問を送信することを含む、請求項1記載の方法。
【請求項４】
工程（1）が、意図された受信ノードへ帯域幅要件を送信することを含む、請求項1記載の方法。
【請求項５】
工程（1）が、意図された受信ノードへ、提案された配信スケジュールを送信することを含む、請求項1記載の方法。
【請求項６】
提案された配信スケジュールが送信マップである、請求項5記載の方法。
【請求項７】
工程（1）が、複数の異なるタイムスロットの間にネットワークを介して複数のテスト・パケットを送信することを含み、工程（2）が、該送信されたテスト・パケットに対応する返却パケットからなる応答を受信することを含む、請求項1記載の方法。
【請求項８】
工程（3）が、返却パケットに関連づけられたドロップ・パケット・レートを評価することを含む、請求項7記載の方法。
【請求項９】
工程（3）が、返却パケットに関連づけられたパケット潜時を評価することを含む、請求項7記載の方法。
【請求項１０】
圧縮ビデオ・パケットが、パケット交換網を介して送信されたインターネット・プロトコル（IP）パケットを含む、請求項1記載の方法。
【請求項１１】
コンピュータ・ネットワークがイーサネットを含む、請求項1記載の方法。
【請求項１２】
送信ノードと受信ノードとの間で、タイムスロットが基礎を有する時間周期を定期的に同期する工程をさらに含む、請求項1記載の方法。
【請求項１３】
工程（2）が、意図された受信ノードから受信マップを受信することを含む、請求項1記載の方法。
【請求項１４】
実行されるときに以下の工程を達成する、実行可能な命令でプログラムされたコンピュータ：
（1）送信ノードから、意図された受信ノードへスケジューリング要求を送信する工程；
（2）意図された受信ノードから、送信されたスケジューリング要求への応答を受信する工程；
（3）意図された受信ノードへの送信が他の送信機と衝突しないタイムスロットを決定するために、該応答を評価する工程；および
（4）送信ノードから、工程（3）で評価されたタイムスロットを使用して、意図された受信ノードへ圧縮ビデオ・パケットを送信する工程。
【請求項１５】
圧縮ビデオ・パケットがDV圧縮標準に従って圧縮される、請求項14記載のコンピュータ。
【請求項１６】
工程（1）が、意図された受信ノードへ質問を送信することを含む、請求項14記載のコンピュータ。
【請求項１７】
工程（1）が、意図された受信ノードへ帯域幅要件を送信することを含む、請求項14記載のコンピュータ。
【請求項１８】
工程（1）が、意図された受信ノードへ、提案された配信スケジュールを送信することを含む、請求項14記載のコンピュータ。
【請求項１９】
提案された配信スケジュールが送信マップである、請求項18記載のコンピュータ。
【請求項２０】
工程（1）が、複数の異なるタイムスロットの間にネットワークを介して複数のテスト・パケットを送信することを含み、工程（2）が、該送信されたテスト・パケットに対応する返却パケットからなる応答を受信することを含む、請求項14記載のコンピュータ。
【請求項２１】
工程（3）が、返却パケットに関連づけられたドロップ・パケット・レートを評価することを含む、請求項20記載のコンピュータ。
【請求項２２】
工程（3）が、返却パケットに関連づけられたパケット潜時を評価することを含む、請求項20記載のコンピュータ。
【請求項２３】
送信ノードと受信ノードとの間で、提案されたタイムスロットが基礎を有する時間周期を定期的に同期する工程をさらに含む、請求項14記載のコンピュータ。
【請求項２４】
工程（2）が、意図された受信ノードから受信マップを受信することを含む、請求項14記載のコンピュータ。
【請求項２５】
コンピュータ・ネットワークを介して圧縮ビデオ・パケットを送信する装置であって、
ビデオ圧縮機と、
意図された受信ノードへスケジューリング要求を送信し、送信されたスケジューリング要求への応答を該意図された受信ノードから受信し、該応答を評価して、意図された受信ノードへの送信が他の送信機と衝突しないタイムスロットを決定し、該タイムスロットを使用して、意図された受信ノードへ圧縮ビデオ・パケットを送信するパケット・スケジューラおよび送信機と
を含む装置。
【請求項２６】
ビデオ圧縮機がDV圧縮機である、請求項25記載の装置。
【請求項２７】
パケット・スケジューラおよび送信機が、意図された受信ノードへ質問を送信する、請求項25記載の装置。
【請求項２８】
パケット・スケジューラおよび送信機が、意図された受信ノードへ帯域幅要件を送信する、請求項25記載の装置。
【請求項２９】
パケット・スケジューラおよび送信機が、意図された受信ノードへ、提案された配信スケジュールを送信する、請求項25記載の装置。
【請求項３０】
提案された配信スケジュールが送信マップである、請求項29記載の装置。
【請求項３１】
パケット・スケジューラおよび送信機が、複数の異なるタイムスロットの間にネットワークを介して意図された受信ノードへ複数のテスト・パケットを送信し、該送信されたテスト・パケットに対応する返却パケットからなる応答を受信する、請求項25記載の装置。
【請求項３２】
パケット・スケジューラおよび送信機が、返却パケットに関連づけられたドロップ・パケット・レートを評価する、請求項31記載の装置。
【請求項３３】
パケット・スケジューラおよび送信機が、返却パケットに関連づけられたパケット潜時を評価する、請求項31記載の装置。
【請求項３４】
送信ノードと受信ノードの間で、提案されたタイムスロットが基礎を有する時間周期を定期的に同期するクロックをさらに含む、請求項25記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互参照
本出願は、主題において、「Empirical Scheduling of Network Packets」と題して2003年9月17日に出願された米国特許出願第10/663,378号および「Endpoint Packet Scheduling System」と題して2003年10月31日に出願された米国特許出願第10/679,103号に関連する。
【０００２】
発明の背景
本発明は概して、ネットワークに接続された装置が、ネットワークに影響を与えずに圧縮ビデオデータ・パケットを送受信するのを可能にするシステムに関する。
【０００３】
イーサネット・ネットワークおよびパケット交換インタネット・プロトコル（IP）ネットワークは、様々なポイントの間でデータを送信するシステムである。これらのシステムは、「競合ベースの」システムと呼ばれている。すなわち、すべての送信器がネットワーク・リソースを求めて競合する。そのようなシステムにおいて、複数の送信機は、パケットがネットワーク・ポートへ同時に到着する時間にパケットを送信することができる。これが起こるとき、ネットワーク・リソースは過剰に申し込まれ、損失または遅延データを生じ、ネットワークは損なわれる。
【０００４】
従来のネットワークは、ローカルエリアネットワーク（LAN）または広域ネットワーク（WAN）を介して接続された終点、例えば、コンピュータを含む。パケットは、パケット交換デバイス、例えば、LANスイッチまたはWANルータを介して、ネットワークの1つの終点から他の終点へ送られる。例えば、図1において、ネットワークは、イーサネットLANへ接続された複数のローカルエリアネットワーク（LAN）終点を含むように示される。エンドポイントは1つまたは複数のLANスイッチ102に結合され、LANスイッチ102はネットワークの他の部分を通して1つまたは複数の他のLANエンドポイント103に接続されている。エンドポイント101がエンドポイント103にパケットを送信するとき、パケットは、他のLANエンドポイントからのパケットも取り扱う他のLANスイッチ102を通して送信される。他のエンドポイントによって103に同時に送信されるパケットが多すぎる場合、LANスイッチ102のキューがオーバーフローし、パケットが失われる恐れがある。（用語「パケット」は、LANまたはワイド・エリア・ネットワーク（WAN）環境におけるデータグラムを指すのに使用される。LAN環境では、パケットは「フレーム」とも呼ばれる。パケット交換WAN環境では、パケット交換装置は通常、「ルータ」と呼ばれる。）
【０００５】
図2は、LAN環境でもWAN環境でも起こる可能性があるパケット喪失問題の性質を示している。複数のエンドポイントがネットワークを介してパケットを同時に送信している周期には、LANスイッチ102が過負荷になり、したがって、いくつかのパケットが破棄される可能性がある。これは通常、LANスイッチ内の内部キューが満杯になり、したがって、発信パケットがキューから除去されるまで新しいパケットを受け入れられなくなることによって起こる。このため、送信器エンドポイントがそのパケットを確実に到着させることができなくなり、伝送制御プロトコル（TCP）のような信頼できる転送プロトコルを使用することなどの他の解決策が必要になるという問題が起こる。TCPはデータ損失を検出することができ、完備したデータ・ファイルの完璧なコピーが受信側デバイスへ配信されるまで、データの再送信を引き起こす。しかし、多くのデバイスはTCPまたは再送信方法を使用することができない。なぜなら、極めて遅いからである。
【０００６】
対話式ビデオ、対話式音声、および他のリアルタイム・アプリケーションは、最初に、データの正確な配信を必要とする。リアルタイム・ビデオは、個々の画像またはビデオ・フレームのシーケンスを含み、個々の画像またはビデオ・フレームは、ネットワークを介して圧縮形式で送られ、到着したとき受信機によって高速継起で表示される。リアルタイム・ビデオまたはリアルタイム音声アプリケーションの場合、受信機は、ビデオを見るか音を聞く前に、大きなファイルがダウンロードされるまで待機する必要はない。むしろ、メディアは連続ストリームとして送られ、到着したときに再生される。受信機は、特殊プログラムであるプレーヤを必要とする。特殊プログラムは、ビデオ・データを解凍してディスプレイへ送り、オーディオ・データを解凍してスピーカへ送る。リアルタイム・ビデオは、通常、前もって記録されたビデオ・ファイルから送られるが、ライブのブロードキャスト「送り込み」の一部分として配布されることもできる。
【０００７】
DV圧縮標準は、リアルタイム・メディア・アプリケーションで使用される普通のフォーマットである。DVフォーマットは、ネットワークを介するリアルタイム・ビデオ能力を必要とするアプリケーションによって使用されるデジタル・ビデオの縮小および圧縮を定義する。DVフォーマットにおいて、ビデオは個々のビデオ・フレームへ分割され、次に離散コサイン変換を使用して圧縮される。DVはイントラフレーム圧縮を使用する。これは、各々の圧縮されたビデオ・フレームが完全に自分自身によって決まり、先行または後続ビデオ・フレームからのデータによっては決まらないことを意味する。しかしそれはさらに、適応インタフィールド圧縮を使用する。すなわち、圧縮機が、ビデオ・フレームの2つのインタレースされたフィールド間でほとんど差異を検出しなければ、圧縮機はそれらのフィールドを一緒に圧縮し、「ビット予算」の幾らかを解放して全体的品質を高くすることができる。
【０００８】
DV圧縮ビデオを使用するリアルタイム・ビデオ・アプリケーションの場合、高いネットワーク・トラフィックは、接続、ダウンロード、および再生問題を引き起こす可能性がある。プレーヤが高トラフィックに遭遇したとき、それは連続再生を維持しようと試みて品質を劣化させる。これらのアプリケーションが良好に動作するためには、光速ですら、所望されない遅延を引き起こす。このようにして、DVリアルタイム・ビデオ・アプリケーションの場合、再送信遅延を含むTCPまたは方法を使用することは、しばしば、うまく行かない。
【０００９】
したがって、問題は、競合ベースのネットワーク上で、信頼できる最初の配信をどのように提供するかを決定することである。様々なアプローチが試みられた。最も普通に提案されたシステムは、ネットワーク内のデータの優先順位付けに頼る。このアプローチの場合、リアルタイム制約を有するデータは優先順位符号化によって同定され、このデータが他のデータよりも前に送信される。
【００１０】
優先順位付けは、最初は良好な解決法のように見える。しかし、よく考えてみると、それは同じ難点を有する。優先順位付けは、より低い優先順位データに対する相対的配信優位を提供するだけである。それは他の優先順位データに対する優位を提供しない。解析およびテストが示すところによれば、このアプローチはある場合には有効であるが、優先順位データの量が小さいときだけである。大容量送信、例えば、リアルタイム・ビデオ・アプリケーションに優先順位付けを使用するとき、優先順位データの量は非常に大きくなる。さらに、同じ高さの優先順位レベルでデータを送信する複数のビデオ・フローは相互に競合する。このようにして、リアルタイム・ビデオ・アプリケーションにおいて、優先順位付けは競合およびパケット損失を防止できない可能性が高い。
【００１１】
さらに、いくつかのネットワークおよび装置は、データ・パケットの複数の優先順位レベルをサポートすることができない。例えば、いくつかのパケット・スイッチは、1つのパケット優先順位レベル（すなわち、優先順位付けされたパケット用のキューと優先順位付けされないパケット用の他のキューの2つのキュー）しかサポートすることができず、そのような方式は実施が困難である。
【００１２】
他のアプローチは、データを多重化することである。本方法の場合、データの1つのフローに関連づけられたデータのバーストは、他のデータのバーストから分離される。多重化は、通常、あるタイプの時間領域システム（時間領域多重化（TDM）として知られる）を使用して、フローを分離する。TDMは、特定のタイムスロットが個々のフローへ割り当てられるように、ネットワークを組織する。言い換えれば、割り当てられたタイムスロットを送信機が使用する可能性がない場合でも、ネットワーク上の各々の潜在的送信機は、送信するためのタイムスロットを保証される。これらの未使用頻度が高いタイムスロットは、イーサネットおよびIPネットワークと比較したとき、TDMを非効率的にする。
【００１３】
非同期転送モード（ATM）は、データ・ネットワークを多重化して、競合を低減する他の技術である。ATMは、すべてのデータ・フローを、等しい長さのデータ・ブロックへ分解する。さらに、ATMは、任意のフローまたはアプリケーションが利用できるデータ・ブロックの数を限定することができる。結果は、仮想TDM多重化システムである。ATMはさらに限定されたアドレス空間を有し、したがってイーサネットおよびIPとは異なり、大型ネットワークへ拡大することはできない。
【００１４】
TDMおよびATMの双方は競合の低減を提供するが、かなりの付加された複雑性、コスト、コンポーネント、および帯域幅性能の損失を代価として提供する。他のアプローチは特殊ハードウェアに頼ってパケット配信をスケジュールするが、ハードウェア・コストを押し上げる。
【発明の開示】
【００１５】
発明の概要
本発明は、送信ノードと受信ノード間の通信に基づき圧縮ビデオ・パケットの配信をスケジュールすることによって、イーサネットまたはIPパケット・ネットワーク内で圧縮ビデオ・パケットを送信する方法を提供する。送信ノードと受信ノード間の通信は、好ましい配信スケジュールを決定するために評価される。
【００１６】
1つの変形例では、意図された受信ノードへ送信ノードが質問を送信し、圧縮ビデオを送信する意図を知らせる。受信ノードは、既に他の送信ノードによって割り当てられているのはどの送信タイム・スロットであるか（または、代わりに、どの送信タイム・スロットが利用可能であるか）を示す受信マップで対応する。送信ノードは次いで、既に送信ノードに割り当てられているあらゆるタイム・スロットを考慮に入れて受信ノードに送信マップを提案する。受信ノードは、提案された送信マップを受け入れるかまたは代わりの送信マップを提案する。ノード同士が合意すると、送信ノードは、提案された送信マップに従って圧縮ビデオの送信を開始し、受信ノードは、提案された送信マップをその割り当てテーブルに組み込む。提案された配信スケジュールは、2つのエンドポイント間で合意されているので、他の場合にはエンドポイントの近傍のネットワーク・スイッチをオーバフローさせる可能性のある調整されていない競合が回避される。スケジュールは、2つのエンドポイントによって決定されるため、ネットワーク・リソース間の調整を行うネットワークアービタは必要とされない。
【００１７】
他の変形例では、送信ノードは、圧縮ビデオ送信の帯域幅要件を、意図された受信ノードに送信する。意図された受信ノードは、既に他の送信器に割り当てられているタイム・スロットを評価した後、送信器に必要な帯域幅を維持しつつ、既にスケジューリングされている他のパケットとの競合を回避するため、送信器が圧縮ビデオパケットを送信すべきタイム・スロットを示す提案された配信スケジュールで対応する。送信器はその後、提案された配信スケジュールによってパケットを送信する。
【００１８】
なお他の変形例では、送信ノードは、送信ノードが圧縮ビデオパケットを送信するよう提案する時間に対応するタイム・スロットを示す提案された配信スケジュールを、意図された受信器に送信する。意図された受信器は、提案された配信スケジュールに合意するか、または送信器の帯域幅要件を考慮に入れた代わりの配信スケジュールを提案する。ノード同士が合意すると、合意された配信スケジュールに従って送信が行われる。スケジュールは送信の終了時に解除することができる。
【００１９】
さらに他の変形例において、公知のデータ転送速度に従って圧縮ビデオ・パケットを送信する必要がある送信ノードは、異なる配信時間を使用して、ネットワーク上の意図された受信機へ一連のテスト・パケットを送信する。テスト・パケットは、どの配信時間が最小の潜時および/またはパケット損失を経験するかを決定するために評価され、この配信時間が使用されて、送信を持続するためにパケットをスケジュールする。他の終点は類似のスキームを使用し、各々の終点は、どの配信スケジュールが、可能性が高い最小パケット損失および潜時を有するパケット送信に最も適しているかを評価することができる。圧縮ビデオ・データ、テスト・パケット、およびネットワーク内の他のデータを送信するため、異なる優先順位レベルが使用される。
【００２０】
発明の詳細な説明
図3〜6は、本発明の仕組みを実施する異なる方法を示している。これらの方法について説明する前に、本発明によってパケットをネットワークを介してノード同士の間で転送できるようにパケットをスケジューリングするにはどうするかについて説明することが役立つ。
【００２１】
図8を参照すると、送信間隔は、データ・パケットを送信できる時間の単位および（任意に）小単位に分割されている。図8の例では、100ミリ秒の任意の送信間隔（マスタ・フレーム）をそれぞれの持続時間が10ミリ秒のサブフレームに分割することができ、各サブフレームをそれぞれの持続時間が1ミリ秒の二次サブフレームに分割することができる。各二次サブフレームは、持続時間が100マイクロ秒のタイム・スロットに分割される。したがって、100ミリ秒の周期は、持続時間が100マイクロ秒の1000個のスロットを含む。本発明の一変形例によれば、受信ノードへの各送信帯域幅単位の転送周期は、図8に示されている方式などの方式を使用して分割され、各パケットは、送信時にこのスケジュールに従って各タイム・スロットに割り当てられる。この方式は、ネットワークにおける時分割マルチプレキシング（TDM）に類似している。
【００２２】
パケット・サイズおよび基本的なネットワーク帯域幅に応じて、実際には各タイム・スロットのある可変的な一部を使用してパケットが送信される。125バイト（1000ビット）のパケット・サイズと10mbpsで動作する10BaseTイーサネットとを仮定すると、単一の100マイクロ秒タイム・スロットを使用して各パケットが送信される。1500バイトのパケット・サイズを仮定すると、各パケット送信によって12個の100マイクロ秒間隔が消費される。
【００２３】
本発明の一変形例によれば、このスケジューリング転送方式は、ネットワークにおける優先順位付けされたパケットに適用され、他の優先順位付けされないパケットはこの方式に含められない。したがって、優先順位トラフィックおよび非優先順位トラフィックのみをサポートするシステムでは、このスケジューリング転送方式はすべての優先順位トラフィックに適用され、アドホック・ネットワーク・トラフィックは引き続き優先順位なしで転送される。言い換えれば、すべての優先順位トラフィックは、非優先順位トラフィックが転送される前に転送される。
【００２４】
図8の配信スケジュールは、例示的なものに過ぎず、他の周期方式を使用することができる。例えば、送信間隔を図示のようにサブフレームに分割する必要はなく、その代わり、任意の間隔を、各タイム・スロットを特定の送信ノードに割り当てることのできる100ミリ秒タイム・スロットに分割することができる。もちろん他の周期を使用することができ、本発明は、任意の特定のタイム・スロット方式に限定されるものではない。この配信スケジュールは、グローバル・ポジショニング・システム（GPS）、無線の時間源、または他のネットワーク同期方法から与えられるようなクロックから得ることができる。タイム・スロットをネットワークにおいて同期させる手段について以下に詳しく論じる。
【００２５】
本発明によって教示される方法は、DV圧縮標準によって圧縮されるリアルタイム・ビデオに適用されてよい。DV25、DV50、DV100、MPEG、およびH260変種などを含むこの標準は、デジタル・ビデオを縮小および圧縮する普通のフォーマットである。DV標準の下では、ビデオがネットワークを介して受信機へ送信される前に、ビデオはビデオ・フレームへ分割され、その後で離散コサイン変換を使用して圧縮される。DV標準はイントラフレーム圧縮を使用する。これは、各々の圧縮されるビデオ・フレームが完全にそれ自身によって決まり、先行または後続するビデオ・フレームからのデータによっては決まらないことを意味する。しかし、DV標準はさらに適応インタフィールド圧縮を使用する。すなわち、DV圧縮機がビデオ・フレームの2つのインタレースされたフィールド間にほとんど差異を検出しなければ、DV圧縮機はそれらのフィールドを一緒に圧縮し、「ビット予算」の幾らかを解放して、全体的品質を高めることができる。
【００２６】
DV標準の1つの例はDV25である。DV25フォーマットの下では、ビデオ情報は公称の1秒当たり25メガビット（Mビット/秒）データ・ストリームで搬送される。オーディオの中に、サブコード（タイムコードを含む）、挿入および追跡情報（ITI）、および誤り訂正を付加した後、全体のデータ・ストリームは約30Mビット/秒で送信する。
【００２７】
送信ノードはネットワーク上でリアルタイム・ビデオ接続をサポートする必要があると仮定する。DV25圧縮ビデオを送信する単一のリアルタイム・ビデオ接続について、30Mビット/秒の帯域幅が必要である。2048バイトまたは16,384ビットのパケット・サイズを仮定すると、これは1秒当たり約1,800パケットが送信されなければならないことを意味する。これは（平均で）1ミリ秒ごとに2つのパケットの計算になる。図8の例において、これは図面の最下部にある二次サブフレームごとに、タイムスロットの少なくとも2つの間にパケットを送信することを意味する。
【００２８】
図3に戻ると、工程301で、送信ノードは、ネットワークにおける意図された受信ノードに、受信マップを求めるクエリーを送信する。
【００２９】
1つの態様において、受信マップ（図9参照）を用いて、受信ノードによって受信できるように、既に他の送信器に割り当てられているタイム・スロット（またはまだ割り当てられていないタイム・スロット、または送信の候補であるタイム・スロット）を示す。より一般的には、受信マップは、意図された受信ノードへの送信が他の送信器と競合しないタイム・スロットを何らかの形式で示すデータ構造である。このようなマップを表す数多くの方法があるが、各ビットが1つのタイム・スロットに対応し、「1」が、タイム・スロットが送信ノードに割り当てられていることを示し、「0」が、タイム・スロットがまだ割り当てられていないことを示すビットマップを使用する手法がある。したがって、図9は、配信スケジュールの25個のタイム・スロットを表しており、あるタイム・スロット（図9では「x」で示されている）は既に他の送信器に割り当てられている。100ミリ秒転送間隔を100マイクロ秒タイム・スロットに分割する場合、受信マップには1000ビットが存在する。このマップは、帯域幅が高いほど大きくなる。例えば、毎秒100メガビットのリンクの場合、マップは、同じスロット当たりスループットを表すのに10,000ビットなどを有してよい。
【００３０】
工程302で、意図された受信ノードは、既に他の送信器に割り当てられているのはどのタイム・スロットかを示す、図9に示されているような受信マップで対応する。これがこの受信ノードに最初に送信を行う送信器である場合、受信マップは空になる。もちろん、最初の送信をサポートするためにタイム・スロットが同じ送信器に既に割り当ててあってもよい（すなわち、同じ送信器が同じ受信側との第2の接続を確立する必要がある）。
【００３１】
工程303で、送信器は、提案された送信マップを意図された受信ノードに送信する。提案された送信マップは好ましくは、意図された受信ノードから受信された割り当てられたタイム・スロットを考慮しており、したがって、既に割り当てられているタイム・スロットは避けられる。送信器は、既に割り当てられているタイム・スロットを避けつつ、送信に必要な帯域幅をサポートするのに十分なタイム・スロットを割り当てる。
【００３２】
工程304で、意図された受信側は、提案された送信マップをレビューし、それに合意するか、または代わりの送信マップを提案する。例えば、意図された受信側が、送信器が帯域幅の交渉を行っている間に、提案されたタイム・スロットの一部を他の送信器に割り当てた場合、新たに提案された配信スケジュールと対立する可能性がある。この状況では、対称となる受信側は、送信器の帯域幅要件を維持する他のマップを提案することができる。
【００３３】
工程305において、送信機は、合意された配信スケジュールに従って、意図された受信側へパケットまたはパケット・バーストを繰り返して送信する。各々のパケットは、圧縮されたビデオ・フレームまたはビデオ・フレーム部分を含む。例えば、リアルタイム・ビデオ接続をサポートするため、送信機は10ミリ秒ごとに6つの80バイト・パケットを送信することができる。より高精細のリアルタイム・ビデオ接続の場合、送信機は、より頻度の高いレートで送信することができる。最後に、工程306では、送信機が送信をもはや必要としなくなったとき、受信機のマップは割り振りを解除される。
【００３４】
2方向通信の場合、一方が、ノードAがノードBへの送信を行うための接続であり、他方の接続が、ノードBがノードAへの送信を行うための接続である2つの別々の接続を確立することができる。本発明の仕組みについては1方向送信に関して説明するが、2方向接続が望ましい場合は他方のエンドポイントで同じ工程が繰り返されることを理解されたい。
【００３５】
図4は、本発明の仕組みを実施する他の方法を示している。まず工程401で、送信器は、意図された受信側に帯域幅要件を送信する。例えば、送信器は、パケット・サイズおよび帯域幅を指示することができ、意図された受信側は、その帯域幅をサポートするのにどのスロットを割り当てることができるかを判定することができる。工程402で、意図された受信側は、既に割り当てられているタイム・スロットを考慮して、提案された送信マップを送って応答する。
【００３６】
工程403で、送信器は、提案された送信マップに合意し、意図された受信側に、合意されたタイム・スロットに「ロック・イン」させ（この工程は省略することができる）、工程404で、送信器は、合意されたスケジュールに従ってパケットを送信する。最後に工程405で、送信マップは、接続の終了時に割り当てを解除する。
【００３７】
図5は、本発明の方法の他の変形例を示している。工程501で、送信ノードは、提案された送信マップを意図された受信側に送信する。工程502で、意図された受信側は、提案された送信マップに合意する（提案された送信マップがいずれかの既に割り当てられているマップに対応する場合）か、または提案された送信マップから推論することのできる送信器の帯域幅要件を満たす他のマップを提案する。例えば、送信器がタイム・スロット1、11、21、31、41、、、における送信を提案している場合、送信器が10タイム・スロットごとに一度送信を行う必要があることは明白である。要求されたスロットが利用可能でない場合、意図された受信側はその代わりにスロット2、12、22、32、、、を提案する。
【００３８】
工程503で、送信器は、合意された配信スケジュールに従って圧縮ビデオフレームを含むパケットを送信し、工程504で、送信の終了時に送信マップが割り当て解除される。
【００３９】
他の変形例では、送信器は帯域幅を要求することができ（例えば、10ミリ秒ごとに1つの1000バイト・パケット）、受信側はプレースメント・メッセージ（例えば、75番目の100マイクロ秒スロットから始める）で対応する。受信側は、複数の代替で対応することもできる（例えば、75番目、111番目、または376番目のタイム・スロットから始める）。送信器は、使用を予定していたタイム・スロット（例えば、111番目）で対応し、送信を開始する。この変形例は、本明細書における意味での「送信マップ」および「受信マップ」の送信の範囲内であることを目的としている。
【００４０】
図6は発明的方法の他の変形例を示す。工程601から始まって、ネットワーク（例えば、イーサネット・ネットワークまたはIPネットワーク）上の2つの終点が通信を望むかどうかが決定される。この決定は、受話器が取り上げられ、電話番号がダイアルされた結果であってよく、2つのノードが圧縮ビデオに適切な接続を開始する必要があることを知らせる。あるいは、ビデオ・データを送信しているノードと受信ノード間で、片方向接続が確立される必要があるかもしれない。これら接続タイプの各々は、ネットワーク上にある量のデータ・パケット・トラフィックを課すものと予想される。
【００４１】
工程602では、上記の態様で説明されたように、図8で示されるようなスキームに従って、配信スケジュールがタイムスロットへ区分される。注意すべきは、この工程が前もって行われ得ること、および2つの終点間で接続が確立される度に繰り返される必要はないことである。工程603では、上記の態様で説明されたように、2つの終点間で必要とされる帯域幅が決定される。例えば、単一のリアルタイム・ビデオ接続について、1秒当たり400キロビットの帯域幅が必要である。480バイトまたは3840ビットのパケット・サイズを仮定すると（当面、パケット・オーバヘッドを無視する）、これは1秒当たり約100パケットが送信されなければならないことを意味する。これは（平均で）10ミリ秒ごとに1つのパケットの計算になる。
【００４２】
工程604では、複数のテスト・パケットが、異なるタイムスロットの間に、所望の帯域幅をサポートするのに必要なレートで送信される。各々のテスト・パケットは、「発見」レベルの優先順位を使用して送信される。この優先順位は、正規のデータ・パケット（例えば、TCPパケット）に調和する優先順位よりも高いが、リアルタイム・データ・トラフィックに割り当てられた優先順位よりも低い（下記で説明される）。例えば、しばらくの間、図7に注意を向けると、スケジュールが1ミリ秒のタイムスロットへ区分されたと仮定する。テスト・パケットは、図示されるように、タイムスロット1、3、5、7、9、11、および12の間に送信されてよい。各々のテスト・パケットは、好ましくは、「発見」レベルの優先順位、パケットが送られた時を知らせる日時表示、パケットが送信された後に、このパケットを同定できる一意のシーケンス番号、およびどのタイムスロットを使用してパケットを送信したかを同定する何らかの手段を含む。（タイムスロットはシーケンス番号から推論されてよい）。受信終点は、テスト・パケットを受信すると、送信側へパケットを返却する。これによって、送信側は、（a）送られたパケットのいくつかが実際に受信されたかを確認し、および（b）各パケットの潜時を決定することができる。もちろん、潜時を決定する他のアプローチが使用されてよい。評価は、送信側、受信側、または両者の組み合わせによって行われてよい。
【００４３】
工程605において、送信側はテスト・パケットを評価して、接続を実行するためには、どのタイムスロットが最も好都合であるかを決定する。例えば、タイムスロット＃1を使用して送信されたパケットが、他のスロットよりも低い平均ドロップ・パケット・レートを経験したことが決定されるならば、このスロットが好ましい。同様に、最低パケット潜時（送信側からの往復）を生じたタイムスロットは、より高い潜時を有した他のタイムスロットよりも好ましい。応力を受け始めるパケット・スイッチが、満杯になり始める待ち行列を有し、潜時およびドロップ・パケットの増加を引き起こすという理論である。したがって、発明的原理によれば、他のタイムスロットを使用して、それらスイッチ内の待ち行列の長さを増加させる可能性が高い期間でのパケット送信を避けることができる。1つの変形例によれば、タイムスロットは「過度の応力」を与えられて、システムを少しだけ伸長することができる。例えば、実際には80バイト・パケットだけが必要とされるならば、テスト段階では160バイト・パケットを送信して、過負荷状態を表現することができる。過負荷状態は、正規の80バイト・パケットが顕現しない隘路を顕現するかもしれない。
【００４４】
日時表示されたパケットを受信側が送り返すのではなく、収集されたテスト・パケット上で統計を遂行し、各タイムスロットに関連づけられた潜時およびドロップ・パケット・レートを同定するレポートを、受信側が送り返すことができる。
【００４５】
上記で説明されたように、パケット・ヘッダ・オーバヘッドは無視されたが、典型的には、評価プロセスの中に含められる必要がある（すなわち、80バイト・パケットは、パケット・ヘッダのサイズだけ増加する）。テスト・パケット用のスロット選択はランダムに決定されるか（すなわち、テスト・パケットについては、タイムスロットのランダム選択が選択される）、前に使用されたタイムスロットに基づいて決定される。例えば、送信ノードが既にタイムスロット3で送信していれば、そのようなタイムスロットは第2の接続に望ましい選択ではないことを送信ノードが前もって知る。他の例として、送信ノードが既にタイムスロット3で送信していれば、テスト・パケットはタイムスロット3から最も離れたタイムスロットで送信され、できるだけパケット配分を広げることができる。
【００４６】
工程606では、2つの終点間で接続が確立され、パケットは、より高い「リアルタイム」優先順位レベルを使用して、および送信に一層好ましいと決定されたスロットを使用して送信される。より高い優先順位レベルが使用されるので、接続は、より低い優先順位レベルでネットワークを送信されたテスト・パケットによって影響を受けない。1つの変形例において、IPパケット・ヘッダ内のIP優先度フィールドを使用して、異なる優先順位レベルを確立することができる。
【００４７】
図7は、本発明の様々な原理を採用するシステムを示す。図7で示されるように、2つの終点の各々は、正確なタイムクロック同期を得るためGPS受信機に頼る（例えば、日時表示および潜時決定のため）。IPネットワークは複数のルータおよび/または他のネットワーク・デバイスを含んでよい。これらは、パケット（例えば、IPパケットまたはイーサネット・パケット）の経路を、1つの終点から他の終点へ究極的に決めることができる。ネットワークを構成している組織は、ネットワーク上で使用される優先順位レベルの制御能力を有し、他のノードが発見的優先順位レベルおよびリアルタイム優先順位レベルを使用することを妨げると仮定する。前述したように、本発明は、タイムクロック同期を達成するGPS受信機に限定されない。無線の時間源または他のネットワーク同期方法が使用されてよい。
【００４８】
理解すべきは、テスト・パケットを異なるタイムスロットで同時に送信するのではなく、送信用の適切なスロットが見出されるまで、1つのスロットをテストし、次に他のスロットをテストし、以下同様に次々にテストしてよいことである。これは、接続を確立するために必要な時間を増加させる。さらに、上記で説明したように、両方向接続の場合、双方の終点が接続確立工程を実行してよい。
【００４９】
他の変形例では、パケット潜時およびドロップ・パケット・レートが終点間の接続中に監視され、いずれかのパラメータの下方傾向を検出したことに基づいて追加のテスト・パケットが送信され、より良好なタイムスロットを見出して接続を移動することができる。
【００５０】
図10に示されているように、ネットワークは、スイッチ1003を通して接続された様々なエンドポイント1001〜1002を含む。本発明の一変形例によれば、GSPクロック・ソース1004は、電線1005を通して、スケジューリング転送方式に参加する各ネットワーク・ノードに結合される。GSPクロック・ソース1004は、各ノードに送信され、配信スケジュールの根拠として使用されるパルスを生成する。各ノードは、タイマ・カード、またはタイミング信号を使用して共通の基準フレームを確立することのできる他の機構（例えば、割込み駆動オペレーティング・システム）を含んでよい。したがって、この同期手段は、同期信号を各ノードに送信するための（ネットワークから分離されかつ離れた）物理的ワイヤを含んでよい。この手段はさらに、同期信号を検出し復号するためハードウェア・カードおよび／またはソフトウェアを各ノードに含んでよい。ワイヤ1005は、同軸ケーブル、またはクロック・ソースを各ノードに接続する他の手段を含んでよい。1つの変形例では、このワイヤは、送信の影響および遅延が回避されるように十分に短い距離（数百フィート）の接続である。
【００５１】
クロック・パルスは、パルスの開始時に同期させられるタイム・スロットを生成するために各ノードによって使用される合意された間隔（例えば、1秒）によるパルスを含んでよい。または、クロック・ソースは高周波数信号を生成することができ、この信号は次いで、各ノードによってタイム・スロットに分割される。もちろん、他の手法も可能である。
【００５２】
他の方法として、各クロック・ソースは、米国政府によって送信される無線信号のような共通の基準信号に同期させられてもよい。図11で示されるように、様々な終点1101〜1102は、それぞれクロック・ソース1104〜1105に接続される。各々のクロック・ソースは無線受信機を含み、クロック信号無線送信機1103から受信された周期的信号に基づいて、時間同期情報を終点ノードへ配信する。
【００５３】
各ノード間でタイム・スロットおよび配信スケジュールを同期させる他の方法または手段は、あるノードに、ノード上の同期パケットをネットワークを介して（例えば、マルチキャストを介して）周期的に送信させることである。各ノードは、このパケットを受信し、それを使用して参照のために内部クロックを同期させる。マルチキャスト手法の代わりに、あるネットワーク・ノードを、送信に伴うスタガー遅延を考慮しつつ、参加している各ネットワーク・ノードに個々に同期パケットを送信するように構成することができる。例えば、同期ノードは、ネットワーク上の第1のノードに同期パケットを送信し、次いでネットワーク上の第2のノードに同じパケットを送信する。パケットは、第2のノードには遅れて受信される。この時間差を、定量化し、共通の基準点に対して補正するのに使用することができる。もちろん他の手法も可能であり、これらの同期手段はどれも互いに独立に使用することができる。
【００５４】
図12は、本発明の仕組みを使用することにより、送信器と受信側との間で圧縮ビデオデータ・パケットをより効率的にスケジューリングすることによって、輻輳をどのように低減させるかを示している。図12に示されているように、各送信ノードが、転送すべきパケットを、他のノードによって送信されるパケットと競合しない時間にスケジューリングするため、失われるパケットはない。
【００５５】
図13は、送信機、受信機、およびこれらのサブコンポーネント間で起こり得る通信を例示する。1つの態様において、送信ノード1302はDV圧縮機1304およびパケット・スケジューラ/送信機1306を含む。受信ノード1308はパケット・スケジューラ/受信機1310およびDV解凍機1312を含む。圧縮されたビデオ送信を送るため、送信ノード1302は内部DV圧縮機1304を使用してビデオ・ファイルを圧縮する。送信機のパケット・スケジューラ/送信機1306は、LANまたはWAN1314を介して、受信機のパケット・スケジューラ/受信機1310との間で通信を送受信し、次いでこの通信を評価して、圧縮されたビデオを送るための好ましいタイムスロットを決定する。パケット・スケジューラ間の様々な通信方法、および好ましいタイムスロットの決定方法は、上記で詳細に説明される。最後に、送信機のパケット・スケジューラ/送信機1306は、決定された送信スケジュールに従って、LANまたはWANネットワーク1314の上で圧縮ビデオ・パケットを送る。
【００５６】
すべてのフレームの位相は、相互に独立であってよいことを理解すべきである。それらは共通クロックから引き出される必要があるだけである。異なる終点はフレームを相互に同期させる必要はない。言い換えれば、各々の時間区間は、時間区間が相対的同期状態に維持される限り、異なる終点間で一意に同定される必要はない。この原理は図14を参照して示される。図14は、異なる位相を有するが共通クロックへ参照されるフレームを参照して指定された時間区間を、どのようにして2つの終点が参照できるかを示す。（実際に終点を共通クロックへ同期させる必要はないが、図14は各理解のためにこれを示す）。
【００５７】
図14で示されるように、終点A（図14の最下部）は、パケット遅延を導入するWANを介して、終点B（図14の最上部）と通信する必要があると仮定する。各々の終点は関連づけられたネットワーク接続デバイス（NCD）を有し、NCDはWANとの接続を処理する。さらに、図14の最上部を横切る時系列および図13の最下部を横切る時系列は「絶対」時間を表現すると仮定する。すなわち、図14の最上部にある時間区間1は、絶対時間内で図14の最下部にある時間区間1と同じ時点に現れる。さらに、NCD Aは区間1の間にネットワークを横切って第1のテスト・パケットXを送信し、区間3の間にネットワークを横切って第2のテスト・パケットYを送信すると仮定する。WANによって導入されたパケット遅延に起因して、テスト・パケットXは、終点Bが時間区間4にあることを認識するまで、終点Bに到着しない。同様に、テスト・パケットYは、終点Bが時間区間6にあることを認識するまで、終点Bに到着しない。それでも、終点AおよびBは、（それぞれのネットワーク接続デバイスNCD AおよびNCD Bを介して）将来のパケットがどの時間区間に送信されるかについて合意する必要がある。
【００５８】
要するに、テスト・パケットXが最小遅延で受信されたことをNCD Bが決定するとき、NCD Bは、「パケットX」として同定されたテスト・パケットが、将来の送信に関して経験的に好都合であったことをNCD Aに通知する。このようにして、NCD Aは適切な時間区間を区間1として同定し、NCD Bは適切な時間区間を区間4として同定する。同様に、NCD AはパケットYの適切な時間区間を区間3として同定し、NCD BはパケットYの適切な時間区間を区間6として同定する。図14の最上部にある時系列および図14の最下部にある時系列が、相互に対して移動しない限り、システムはパケット遅延に順応することができ、終点は、どの時間区間の場所を使用してパケットを送信するかについて合意することができる。もちろん、他のアプローチが使用可能である。
【００５９】
本発明はさらに、ルータ待ち行列の中の「早期廃棄」設定と一緒に働く。なぜなら、廃棄状態が近づいていることを経験的方法が検出するからである。
【００６０】
本発明を実施する現在好ましい態様を含む特定の例に関して本発明を説明したが、当業者には、添付の特許請求の範囲に記載された本発明の趣旨および範囲内の上述のシステムおよび技術の多数の変形例および順列があることが理解されよう。本明細書に記載されたあらゆる方法工程は、コンピュータ・ソフトウェアで実現することができ、かつ汎用または専用コンピュータで実行できるようにコンピュータ可読媒体上に記憶することができ、そのようなコンピュータ可読媒体は、対象となる発明の範囲内に含まれる。本発明は、方法だけでなく、本発明の仕組みを実施するようにプログラムされたコンピュータ・ノードにも拡張される。特許請求の範囲内のプロセス工程に関連する番号付けは、都合上のものに過ぎず、特定の順序付けやシーケンスを意味するとみなすべきではない。
【図面の簡単な説明】
【００６１】
【図１】パケットを失わせるオーバフロー状態をパケット・スイッチにおいて発生させるバースト状態のパケットの問題を示す図である。
【図２】2組のエンドポイントがバースト条件の下で共通のネットワーク・リソースを共用する場合にネットワークの輻輳によってどのようにパケットが失われるかを示す図である。
【図３】送信ノードと意図された受信ノードとの間の送信用の配信スケジュールを調整する一方法を示す図である。
【図４】送信ノードと意図された受信ノードとの間の送信用の配信スケジュールを調整する第2の方法を示す図である。
【図５】送信ノードと意図された受信ノードとの間の送信用の配信スケジュールを調整する第3の方法を示す図である。
【図６】テスト・パケットを使用して、送信ノードおよび意図された受信ノード間で送信するため配信スケジュールを調整する第4の方法を示す。
【図７】第1の終点から第2の終点へのテスト・パケット配信スケジュールを使用するシステムを示す。
【図８】送信間隔をマスタ・フレーム、サブフレーム、および二次フレームに分解することのできるフレーム構造を示す図である。
【図９】一定の送信間隔についての1つの考えられる受信マップを示す図である。
【図１０】ネットワーク・ノード間の配信スケジュールを時間同期させる方式を示す図である。
【図１１】ネットワーク・ノード間の配信スケジュールを時間同期させる代替スキームを示す。
【図１２】本発明の仕組みを使用してネットワークの輻輳を回避し、ネットワークにおけるパケットのスケジューリングをより効率的に行うにはどうするかを示す図である。
【図１３】ネットワークを介する送信機および受信機間の通信を示す。
【図１４】異なる位相を有するが共通クロックへ参照されるフレームを参照して指定された時間区間を、2つの終点がどのようにして参照できるかを示す。
【図１】
2009509462.tif 000004
【図２】
2009509462.tif 000005
【図３】
2009509462.tif 000006
【図４】
2009509462.tif 000007
【図５】
2009509462.tif 000008
【図６】
2009509462.tif 000009
【図７】
2009509462.tif 000010
【図８】
2009509462.tif 000011
【図９】
2009509462.tif 000012
【図１０】
2009509462.tif 000013
【図１１】
2009509462.tif 000014
【図１２】
2009509462.tif 000015
【図１３】
2009509462.tif 000016
【図１４】
2009509462.tif 000017
【国際調査報告】
2009509462.tif 000018