(57)【要約】【課題】ストリーミングメディアデータの符号化ビットレートを制御するシステムおよび方法を提供する。【解決手段】この符号化ビットレートの制御は、符号化ビットレートを動的に調整して、クライアントバッファがアンダーフローしないようにクライアントバッファ時間を制御し、同時に、平均符号化ビットレートをネットワークの平均送信ビットレートに近く維持する（したがってデータ再生の品質を最大に高める）。最適線形二次制御の理論を用いて、クライアントバッファ時間が、可能な限り目標レベルに近く保たれ、同時に符号化ビットレート（ひいては品質）を可能な限り一定に保つ。また、制御ループにリーキーバケツを取り入れて、瞬時符号化ビットレートの自然な変動に起因するバッファ時間の変化が、ネットワークの輻輳に起因するバッファ時間の変化と間違えられないようにする。【選択図】図５
2006174419.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークを通じてサーバからクライアントに送信されるストリーミングメディアデータの符号化ビットレートを制御する、コンピュータで実施される方法であって、
線形二次制御技術を用いて、前記ストリーミングメディアデータの現在の符号化ビットレートを継続的に確立する動作であって、前記符号化ビットレートは、前記ストリーミングメディアデータの高品質の再生を提供し、同時に、前記サーバからストリーミングメディアデータを受信するために使用される前記クライアントのデコーダバッファを所望の時間レベルに充たされる状態にして、結果として前記クライアントによる前記ストリーミングメディアデータの再生の中断につながるアンダーフロー条件の危険性を低減するように推定されることと、
確立された各符号化ビットレートを使用して、前記ストリーミングメディアデータの前記レートを制御する動作と、
を実行するステップを備えることを特徴とする方法。
【請求項２】
前記現在の符号化ビットレートを確立する前記方法動作は、
前記クライアントバッファレベルをほぼ前記所望の目標レベルに維持するものと推定された前記符号化ビットレートを、フレーム単位で求める動作と、
前記符号化ビットレートの推定が、前記最後に確立されたレートとの関連で所望の程度以上変化しないと判定される場合のみ、新しい符号化ビットレートを確立する動作と、
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記クライアントバッファレベルは、前記推定された符号化ビットレートにおける前記ストリーミングメディアデータのリーキーバケツモデルによって求められることを特徴とする請求項２に記載の方法。
【請求項４】
前記クライアントバッファをほぼ前記所望のレベルに維持すると推定された前記符号化ビットレートをフレーム単位で求める前記方法動作は、検討対象のフレームの推定された最新の予想到着時間と、規定された目標到着時間との差を縮小する符号化ビットレートを識別する動作を備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記クライアントバッファをほぼ前記所望のレベルに維持すると推定された前記符号化ビットレートをフレーム単位で求める前記方法動作は、二次コスト関数を使用して、前記符号化ビットレートの変化を規定の程度に低減する動作を備えることを特徴とする請求項４に記載の方法。
【請求項６】
検討対象のフレームの最新の予想到着時間を推定する方法動作は、
検討対象のフレームの直前のフレームが前記現在の符号化ビットレートを示す場合は、前記直前のフレームに関連付けられた最新の予想到着時間を再度推定する動作と、
前記再度推定された時間を、前記現在の符号化ビットレートを現在の瞬時フレームレートとフレームの推定到着レートとの積で割った値に加える動作と、
を備えることを特徴とする請求項５に記載の方法。
【請求項７】
検討対象のフレームの直前のフレームに関連付けられた最新の予想到着時間を再推定する前記方法動作は、
クライアントによって測定された前記直前のフレームの実際の到着時間を、前記直前のフレームについての前記サーバのエンコーダバッファの上限との差分を、前記直前のフレームに関連付けられた前記推定到着レートで割った値に加える動作を備え、フレームの前記上限との差分は、前記サーバのエンコーダバッファが、前記フレームが完全に前記エンコーダバッファに入力された後に現在保持しているビットを越えて収容することができるデータビット数として定義されることを特徴とする請求項６に記載の方法。
【請求項８】
前記現在の符号化ビットレートを推定する前記方法動作は、前記クライアントによって達成され、前記クライアントは、前記エンコーダバッファの状態に関する前記サーバから受け取られた情報に基づいて、前記検討対象フレームの前記最新の予想到着時間を推定することを特徴とする請求項７に記載の方法。
【請求項９】
前記サーバから受け取られる情報は、符号化ビットレートを示すフレームの連続の最初のフレームの一部として受信される、前記クライアントによって受信されている前記ストリーミングメディアデータの前記現在の符号化ビットレートを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記クライアントによって受信された各フレームの前記上限との差分を推定する動作をさらに備え、前記推定は、
前記最後に受信されたフレームが前記エンコーダバッファに入れられた場合の前記エンコーダバッファの充足度を、前記最後に受信されたフレームが挿入される前の前記エンコーダバッファの充足度の最後に計算された値と、最後に受信されたそのフレームのサイズとの合計として計算する動作であって、
前記ストリーミングメディアの前記現在の符号化ビットレートで前記クライアントによって受信された最初のフレームに関連付けられた、前記最後に受信されたフレームが挿入される前の前記エンコーダバッファの充足度は、その実際の値に関係なくゼロになると想定され、
前記現在の符号化ビットレートで前記クライアントによって受信される各後続フレームに関連付けられた、最後に受信されたフレームが挿入される前の前記エンコーダバッファの充足度は、ゼロとみなされるか、または、前記最後に受信されたフレームが挿入された後の前記エンコーダバッファの充足度を、前記瞬時フレームレートで割った値（いずれか大きい方）の差と見なされ、前記瞬時フレームレートは、これから受信される次のフレームの予定された再生時間から、前記最後に受信されたフレームの予定された再生時間を引いた値の逆数に等しいことと、
前記最後に受信されたフレームに関連付けられた前記上限との差分を、前記エンコーダバッファのサイズから、前記最後に受信されたフレームが挿入された後の前記エンコーダバッファの充足度について最後に計算された値を引いた値として計算する動作と、
を備えることを特徴とする請求項９に記載の方法。
【請求項１１】
前記エンコーダバッファのサイズは、前記符号化ビットレートに応じて異なり、前記サーバから利用することができるすべての符号化ビットレートについて、前記ストリーミングメディアデータのプリアンブルとして前記サーバから前記クライアントに受け取られることを特徴とする請求項１０に記載の方法。
【請求項１２】
直前のフレームと異なる符号化ビットレートを有するフレームが前記クライアントに受信されると、
受信したばかりのフレームに関連付けられた現在予定された目標到着時間をシフト値だけシフトする動作であって、前記シフト値は、前記フレームの前記上限との差分と、前記直前の符号化ビットレートで符号化された場合に前記フレームに関連付けられた前記上限との差分との差に相当することと、
後続のフレームの前記現在予定された目標到着時間を、それらの時間が、ある時間をかけて、それらフレームの元の目標到着時間に全体で近づいていき、最終的には一致するようにシフトする動作と、
前記最後に受信されたフレームが挿入された後の前記エンコーダバッファの充足度値と、現在の符号化ビットレートを前記フレームレートで割り、その値を前記最後に受信されたフレームに関連付けられた推定到着レートで割った値との差だけ、シフトされた各フレームをシフトする動作と、
を備えることを特徴とする請求項１０に記載の方法。
【請求項１３】
前記直前の符号化ビットレートで符号化された場合に前記フレームに関連付けられる前記上限との差分は、前記エンコーダバッファのサイズから、前記最後に受信されたフレームが挿入された後の前記エンコーダバッファの充足度について計算された最後の値を引いた値として計算され、前記最後に受信されたフレームが挿入された後の前記エンコーダバッファの充足度は、前記最後に受信されたフレームが挿入される前の前記エンコーダバッファの充足度の最後に計算された値と、前記最後に受信されたフレームのサイズとの合計として計算され、前記最後に受信されたフレームが挿入される前の前記エンコーダバッファの充足度値は、ゼロと計算されるか、前記最後に受信されたフレームの前に受信されたフレームが挿入された後の前記エンコーダバッファの充足度について計算された値と、直前の符号化ビットレートを、前記最後に受信されたフレームの前に受信されたフレームに関連付けられた前記瞬時フレームレートで割った値（いずれか大きい方）の差として計算されることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記サーバから受け取られる前記情報は、
前記現在の符号化ビットレートを示すフレームの連続の最初のフレームの一部として受信される、前記クライアントによって受信されている前記ストリーミングメディアデータの前記現在の符号化ビットレートと、
すべてのフレームの一部として受信される、現在の上限との差分と、
を含むことを特徴とする請求項８に記載の方法。
【請求項１５】
前記サーバから受け取られる前記情報は、
前記現在の符号化ビットレートを示すフレームの連続の最初のフレームの一部として受信される、前記クライアントによって受信されている前記ストリーミングメディアデータの前記現在の符号化ビットレートと、
前記連続の最初のフレームの一部としても受信される、前記現在の符号化ビットレートを示すフレームの連続の最初のフレームに関連付けられた前記現在の上限との差分と、
を含むことを特徴とする請求項８に記載の方法。
【請求項１６】
前記サーバから受け取られる前記情報は、前記直前のフレームと異なる符号化ビットレートを示すフレームの連続の最初のフレームの一部として受信されたシフト値をさらに含み、前記シフト値は、前記現在の符号化ビットレートで符号化された場合に前記クライアントによって受信された前記直前のフレームに関連付けられることになる前記上限との差分と、直前の符号化ビットレートで符号化された前記直前のフレームに実際に関連付けられた前記上限との差分との差に相当することを特徴とする請求項１５に記載の方法。
【請求項１７】
直前のフレームと異なる符号化ビットレートを有するフレームが前記クライアントで受信されると、前記受信されたばかりのフレームに関連付けられた前記現在予定された目標到着時間を前記シフト値だけシフトし、後続のフレームの前記現在予定された目標到着時間を、それらの時間が、ある時間をかけて、それらフレームの元の目標到着時間に全体として近づいていき、最終的には一致するようにシフトする動作をさらに備え、前記目標値のシフトは、クライアントが、前記フレームの到着レートの変化ではなく、古い符号化レートと新しい符号化レートでの前記上限との差分の変化に基づいて新しい符号化ビットレートを確立することを試みないようにするために行われることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記現在の符号化ビットレートを示すフレームの連続の最初のフレームでないフレームがクライアントで受信されるたびに、前記上限との差分を推定する動作をさらに備えることを特徴とする請求項１５に記載の方法。
【請求項１９】
前記ストリーミングメディアデータのフレームの推定到着レートを計算する動作は、
現在受信されたパケットの１つ前のパケットに計算された推定到着時間と第１の分数の重み係数との積を、前記現在受信されたパケットの前記瞬間到着レートと第２の分数の重み係数との積に加えた値をパケット単位で計算する動作を備え、前記分数の重み係数の少なくとも１つは、定数ではなく、前記パケット間の時間に基づくことを特徴とする請求項６に記載の方法。
【請求項２０】
検討対象のフレームの前記推定された最新の予想到着時間と、前記規定された目標到着時間との差を縮め、同時に前記符号化ビットレートの変化を規定の程度まで低減する前記符号化ビットレートを識別する前記方法動作は、
前記検討対象のフレームの前記規定された目標到着時間が、そのフレームに予定された再生時間より早い規定された時間量になるように選択する動作を備えることを特徴とする請求項５に記載の方法。
【請求項２１】
前記検討対象のフレームの前記規定された目標到着時間を選択する前記方法動作は、前記規定された時間量を、スタートアップ期間後に、フレームの実際の到着時間をその目標到着時間より後にする可能性のあるネットワークジッタ、遅延、およびスループットの変化の結果、前記フレームが予定されたその再生時間より後に到着することにならないようにするのに十分な大きさにする動作を備えることを特徴とする請求項２０に記載の方法。
【請求項２２】
前記検討対象のフレームの前記規定された目標到着時間を選択する前記方法動作は、前記ストリーミングメディアデータが前記クライアントに受信され始める時から、前記最初のフレームが再生される時までのスタートアップの遅延を短縮するのを助けるために、スタートアップ期間中に到着するフレームについて、スタートアップ期間後よりもスタートアップ期間中に、前記目標到着時間を前記再生時間により近くする動作をさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記検討対象のフレームの前記規定された目標到着時間を選択する前記方法動作は、対数の目標スケジュールを使用して、前記ストリーミングメディアの各フレームの前記目標到着時間を設定する動作をさらに備えることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記検討対象のフレームの前記規定された目標到着時間を選択する前記方法動作は、２部分からなる線形の目標スケジュールを使用して前記ストリーミングメディアの各フレームの前記目標到着時間を設定する動作をさらに備え、スタートアップ期間中に到着するフレームの目標到着時間から再生時間までの差は、ネットワークジッタ、遅延、およびスループットの変化を補償するのに十分な大きさの規定の時間量まで線形に増大し、規定の時間量に達した後は、実質的に一定になることを特徴とする請求項２２に記載の方法。
【請求項２５】
前記スタートアップまでの遅延を短縮する方法動作をさらに備え、短縮する前記動作は、
初期の符号化ビットレートでアンダーフロー条件が発生しないことを保証するのに必要な最小量のデータが前記クライアントのデコーダバッファに得られると、早くも前記ストリーミングメディアレートの最初のフレームの再生を開始する動作を備えることを特徴とする請求項２２に記載の方法。
【請求項２６】
前記クライアントの前記デコーダバッファに最小量のデータが得られると、早くも前記ストリーミングメディアデータの最初のフレームの再生を開始する前記方法動作は、
前記最初のフレームに関連付けられたエンコーダバッファの初期充足度値を得る動作であって、前記エンコーダバッファの初期充足値は、前記エンコーダバッファのサイズから、前記最初のフレームのサイズと、前記最初のフレームに関連付けられた前記上限との差分を引いた値として定義されることと、
前記最小のデータ量を、前記初期符号化ビットレートに関連付けられた前記エンコーダバッファのサイズからエンコーダバッファの初期充足度を引いた値として確立する動作と、
を備えることを特徴とする請求項２５に記載の方法。
【請求項２７】
前記初期符号化ビットレート、初期エンコーダバッファ充足度、およびエンコーダバッファサイズが、前記ストリーミングメディアデータのプリアンブルとして前記サーバから受信されることを特徴とする請求項２６に記載の方法。
【請求項２８】
前記スタートアップまでの遅延を短縮する方法動作は、前記最小量のデータは、前記到着レートが前記符号化ビットレートに相対的に上がると下がり、前記スタートアップまでの遅延は、実質的に、前記最小のデータ量を前記到着レートで割った値であるので、前記符号化ビットレートが前記到着レートより小さい場合、前記必要とされる最小のデータ量がより小さくなり、前記スタートアップまでの遅延がより短くなる可能性があるため、前記初期符号化ビットレートを前記ストリーミングメディアデータの前記予想到着レートより小さいレベルに設定する動作をさらに備えることを特徴とする請求項２６に記載の方法。
【請求項２９】
前記現在の符号化ビットレートを確立する前記方法動作は、スタートアップ期間の後にのみ前記符号化ビットレートの確立を開始する動作を備え、前記スタートアップ期間は、そのフレームの目標到着時間より早くなっており、初期符号化レートについて計算された検討対象のフレームの推定された最新の到着時間の最初の場合（ｉｎｓｔａｎｃｅ）より前の期間と定義されることを特徴とする請求項５に記載の方法。
【請求項３０】
前記符号化ビットレートがその程度まで下げられる前記規定された程度は、前記符号化ビットレートが増したかどうかによって異なり、前記符号化ビットレートが増した場合は、前記符号化ビットレートのその後の変化がその程度に低減される前記規定された程度は、前記符号化ビットレートの最後の変化がレートを下げた場合の規定された程度と比較して大きくされることを特徴とする請求項５に記載の方法。
【請求項３１】
前記ストリーミングメディアデータの現在の符号化ビットレートを確立する方法動作は、前記求められた符号化ビットレートが、直前の符号化ビットレートからの上昇に相当する場合は、新しい符号化ビットレートが、前記フレームの現在の推定到着レートを超えない場合のみ、新しい符号化ビットレートを確立する動作を備えることを特徴とする請求項３に記載の方法。
【請求項３２】
前記ストリーミングメディアデータの現在の符号化ビットレートを確立する方法動作は、前記求められた符号化ビットレートが、前記フレームの現在の推定到着レートを超える、直前の符号化ビットレートからの上昇に相当する場合、現在のクライアントバッファが、規定された時間が経過する前により高い符号化ビットレートで費やされないとクライアントで推定される量だけ、前記所望のレベルを超える場合のみ、新しい符号化ビットレートを確立する動作を備えることを特徴とする請求項３に記載の方法。
【請求項３３】
前記ストリーミングメディアデータの現在の符号化ビットレートを確立する方法動作は、前記求められた符号化ビットレートが直前の符号化ビットレートからの低下に相当する場合、新しい符号化ビットレートが前記直前の符号化ビットレートからの著しい逸脱に相当する場合でも、新しい符号化ビットレートを確立する動作を備えることを特徴とする請求項３に記載の方法。
【請求項３４】
コンピュータネットワークを通じてサーバからクライアントに送信されるストリーミングメディアデータの符号化ビットレートを制御する、コンピュータで実施される方法であって、前記サーバを使用して、
前記サーバでサポートされた符号化ビットレートを示し、スタートアップ期間後には前記クライアントから要求されるレートに関連する符号化ビットレートを示すストリーミングメディアストリームを生成する方法動作と、
前記クライアントに送信される前に前記ストリーミングメディアデータの一部を記憶するために用いられる前記サーバのエンコーダバッファの状態を示すパラメータを計算する方法動作と、
前記エンコーダバッファの状態パラメータと前記ストリーミングメディアデータのストリームを前記クライアントに提供し、それにより、前記パラメータを前記クライアントによって使用して、前記ストリーミングメディアデータの現在の符号化ビットレートを継続的に確立することができる動作であって、推定された前記現在の符号化ビットレートは、前記ストリーミングメディアデータの高品質の再生を提供し、同時に、前記サーバからストリーミングメディアデータを受信するために使用される前記クライアントのデコーダバッファを所望の時間レベルに充たされる状態にしておき、結果として前記クライアントによる前記ストリーミングメディアデータの再生の中断につながるアンダーフロー条件の危険性を低減するように推定されることと、
を実行することを特徴とする方法。
【請求項３５】
前記エンコーダバッファの状態を示すパラメータを計算する前記方法動作は、前記サーバによってサポートされた各符号化ビットレートについて、前記符号化ビットレートに対応するデータストリームが前記サーバからストリーミングされた場合に存在することになる前記エンコーダバッファの初期状態を定義するパラメータのセットを計算する動作を備え、前記エンコーダバッファパラメータは、前記データストリームに関連付けられた前記符号化ビットレート、前記データストリームの前記符号化ビットレートに用いられる前記エンコーダバッファのサイズ、並びに、前記データストリームの前記符号化ビットレートで示されるエンコーダバッファの初期充足度を示す値を備えることを特徴とする請求項３４に記載の方法。
【請求項３６】
前記エンコーダバッファの状態パラメータと前記ストリーミングメディアデータを前記クライアントに提供する前記方法動作は、前記ストリーミングメディアデータを送信する前に前記クライアントに送信されるプリアンブルの一部として、前記サポートされた符号化ビットレートの１つを示す各データストリームについて計算された前記エンコーダバッファパラメータを前記クライアントに提供する動作を備えることを特徴とする請求項３５に記載の方法。
【請求項３７】
前記データストリームの前記符号化ビットレートに用いられる前記エンコーダバッファのサイズは、前記符号化ビットレートと前記初期エンコーダバッファ充足度を前提として、前記ストリーミングプロセスのどの時点においても前記データストリームをなお収容する最小サイズのバッファになるように選択されることを特徴とする請求項３５に記載の方法。
【請求項３８】
前記サーバが、前記サーバによってサポートされた各符号化ビットレートに生成される前記ストリーミングメディアデータの各フレームについての上限との差分を計算する方法動作をさらに備え、前記上限との差分は、生成されたばかりのフレームが前記エンコーダバッファに完全に入力された後に前記サーバのエンコーダバッファが現在収容しているビットを越えて収容することができるデータビット数として定義されることを特徴とする請求項３５に記載の方法。
【請求項３９】
フレームの連続の最初のフレームの直前に生成されたフレームに関連付けられた符号化ビットレートと異なる符号化ビットレートを示すフレームの連続の最初のフレームに計算された上限との差分を、前記フレームの連続に関連付けられた前記符号化ビットレートの指示とともに、クライアントに提供する方法動作をさらに備え、前記差分値と前記符号化ビットレートは、前記連続の前記最初のフレームとともに提供されることを特徴とする請求項３８に記載の方法。
【請求項４０】
前記クライアントは、前記関連付けられた差分値を含まない、前記サーバから提供されるフレームについて前記上限との差分を推定することを特徴とする請求項３９に記載の方法。
【請求項４１】
前記クライアントは、前記エンコーダバッファパラメータと前記上限との差分値を用いて、前記クライアントバッファをほぼ前記所望のレベルに維持する前記符号化ビットレートをフレーム単位で判定し、前記判定は、検討対象のフレームの推定された最新の予想到着時間と規定された目標到着時間との差を縮小する符号化ビットレートを識別することを備えることを特徴とする請求項４０に記載の方法。
【請求項４２】
前記サーバが、前記連続の最初のフレームの直前に生成された前記フレームと異なる符号化ビットレートを示すフレームの連続の最初のフレームに相当する各フレームのシフト値を計算する方法動作であって、前記シフト値は、前記現在の符号化ビットレートで符号化された場合に、前記連続の前記最初のフレームの直前に生成されたフレームに関連付けられることになる前記上限との差分と、１つ前の符号化ビットレートで符号化された前記連続の最初のフレームの直前に生成された前記フレームに実際に関連付けられた前記上限との差分との差に相当することと、
前記連続の最初のフレームの直前に生成されたフレームと異なる符号化ビットレートを示す各フレーム連続の最初のフレームに計算された前記シフト値を、その最初のフレームを含む前記データとともに前記クライアントに提供する方法動作と、
をさらに備えることを特徴とする請求項３９に記載の方法。
【請求項４３】
１つ前のフレームと異なる符号化ビットレートを有するフレームが前記クライアントに提供されると、受信したばかりのフレームに関連付けられた現在予定された目標到着時間が、前記受信したばかりのフレームとともに提供された前記シフト値だけシフトされ、後続のフレームについて現在予定された目標到着時間が、ある時間をかけて、それらフレームの元の目標到着時間に全体として近づいていき、最終的には一致するようにシフトされることを特徴とする請求項４２に記載の方法。
【請求項４４】
限られた数の符号化ビットレートが前記サーバによってサポートされ、前記サーバによってサポートされた符号化ビットレートを示し、最初のスタートアップ期間後は前記クライアントから要求されるレートに関連する符号化ビットレートを示すストリーミングメディアデータを生成する方法動作は、
（ａ）前記クライアントから符号化ビットレート要求を受信する動作と、
（ｂ）前記要求される符号化ビットレートに等しいサポートされた符号化ビットレート、または等しいレートがない場合は、要求される符号化ビットレートに最も近く、より小さいサポートされた符号化ビットレートを見つける動作と、
（ｃ）前記ストリーミングメディアデータの最後に生成されたフレームに関連付けられた符号化ビットレートより低いサポートされた符号化ビットレートが見つけられると、後続のすべてのフレームをそのサポートされたレートで生成する動作と、
（ｄ）前記ストリーミングメディアデータの前記最後に生成されたフレームに関連付けられた前記符号化ビットレートより高いサポートされた符号化ビットレートが見つけられると、前記見つけられたサポートされた符号化ビットレートで符号化された場合に前記最後に生成されたフレームに関連付けられた前記上限との差分と、前記現在の符号化ビットレートで符号化されたそのフレームに関連付けられた前記上限との差分との差が、許容される最大の差分値以下であるかどうかを判定し、
前記差が、前記許容される最大の差分値未満である時は、後続のすべてのフレームを前記見つけられたサポートされたレートで生成し、
前記差が、前記許容される最大の差分値より小さくない時は、次に低いサポートされた符号化ビットレートを見つけ、動作（ｃ）〜（ｄ）を繰り返す動作と、
を備えることを特徴とする請求項３８に記載の方法。
【請求項４５】
前記許容される最大の差分値は、前記符号化ビットレート要求とともに前記クライアントから受信されることを特徴とする請求項４４に記載の方法。
【請求項４６】
前記クライアントは、前記クライアントによって検討対象とするフレームの直前に前記サーバから提供されたフレームが、前記要求された符号化ビットレートで符号化されていた場合に関連付けられる最新の予想到着時間が、そのフレームの目標到着時間からその再生期限までの隔たりの規定された分数以下になるように前記許容される最大の差分値を選択することを特徴とする請求項４５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストリーミングメディアの符号化ビットレートの制御に関し、より詳細には、高速のスタートアップ、途切れのない再生、およびストリーミングセッション全体にわたる最大限の品質と滑らかさを提供する、ストリーミングメディアデータの符号化ビットレートを制御するシステムおよび方法に関する。
【背景技術】
【０００２】
恐らく、インターネットを通じて要求に応じてメディアをストリーミングする際の主要な技術的問題は、変化するネットワーク条件に適合する必要性である。競合する通信プロセスが開始し、終了するのに伴い、利用可能な帯域幅、パケット損失、およびパケット遅延がすべて変動する。何十秒にもわたるネットワークの停止が発生する可能性があり、実際に発生する。リソースの予約とＱＯＳ（Ｑｕａｌｉｔｙ  ｏｆ  ｓｅｒｖｉｃｅ）は一助となることができるが、それらも、ネットワークリソースが安定することを保証することはできない。例えばネットワーク経路が無線リンクを含む場合、干渉によって時折ネットワークの容量が減少する可能性がある。そのため、商業グレードのストリーミングメディアシステムは、悪いネットワーク条件に対して堅牢である必要がある。さらに、そのような堅牢性は、積極的な（事後対応型でない）伝送のみでは実現することはできない。パケット損失のたびに再送を行う一定ビットレート伝送でも、チャネル容量より高いスループットは達成することができない。したがって、ネットワークに対するある程度の適合性が必要となる。
【０００３】
エンドユーザは、優れたストリーミングメディアシステムが、次のような振る舞いを示すことを期待する。要求に応じて再生されるコンテンツが短い遅延でスタートアップする。一旦スタートアップすると、ユーザによって中断されない限り、連続して（停止することなく）再生し、利用可能な平均通信帯域幅を考慮して、可能な限り高い品質で再生する。変化するネットワーク条件に直面してこれらの期待に応えるために、復号と再生の前にクライアントにおいてコンテンツをバッファリングすることが必要となる。
【０００４】
クライアントにおけるバッファリングは、いくつかの異なる、しかし同時に存在する目的を果たす。第１に、バッファリングにより、クライアントが、パケット伝送遅延の短時間の変動（ジッタ）を補償することが可能になる。第２に、バッファリングにより、クライアントに、必要な場合はパケット損失の回復を行う時間が与えられる。第３に、バッファリングにより、クライアントが、ネットワーク帯域幅の低下中にコンテンツの再生を続けることが可能になる。そして、最後に、バッファリングにより、可変のビットレートでコンテンツを符号化することが可能になり、全体的な品質を劇的に向上させることができる。いわゆる一定ビットレート（ＣＢＲ）で符号化されたコンテンツも、実際には、所与のサイズの復号バッファの制約内で、可変ビットレートにより符号化されることに留意されたい。復号バッファのサイズが大きいほど、品質はよくなる。必要とされる復号バッファリングは、より大きなクライアントバッファの一部となる。
【０００５】
クライアントバッファのサイズは、バッファ時間（ｂｕｆｆｅｒ  ｄｕｒａｔｉｏｎ）と呼ばれる、バッファ内のコンテンツの秒数で表すことができる。バッファ時間は、コンテンツがバッファに入ると増し、コンテンツがバッファを出ると減る傾向がある。コンテンツは、再生される際に、実時間の１秒につきｖ秒分のコンテンツのレートでバッファを出る。ｖは、再生速度である（ｖは、一般に通常の再生では１であるが、高速再生の場合は１より大きく、低速再生の場合は１より小さい可能性がある）。コンテンツは、ネットワークを通じてクライアントに到着する時に、実時間の１秒につきｒａ／ｒｃ秒分のコンテンツのレートでバッファに入る。ｒａは、到着レート、すなわち実時間の１秒当たりにクライアントに到着する平均ビット数であり、ｒｃは、符号化ビットレート、すなわち、１秒分のコンテンツを符号化するために必要な平均ビット数である。したがって、バッファ時間は、ｒａを上げるか、ｒｃを下げるか、および／またはｖを下げることによって延ばすことができる（バッファ時間を減らす場合はそれらの逆）。バッファ時間は、ｒａを変えるか、ｖを変えることによって瞬間的に調整することはできるが、それらの数値は、一般には、長時間にわたって自在に調整することはできない。平均到着レートｒａは、ネットワーク容量によって決まり、一方、平均の再生速度ｖは、ユーザの好みによって決定される。したがって、ネットワーク容量がある持続した時間にわたって劇的に低下した場合は、符号化ビットレートｒｃを下げることが、バッファが再度満たされる間に再生が停止する（ｖ＝０）再バッファリングイベントを防止する唯一の適切な手段となる。
【０００６】
したがって、変化するネットワーク条件への適合性は、バッファだけでなく、何らかの手段が、コンテンツの符号化ビットレートｒｃを調整することを必要とする。これは、マルチビットレート（ＭＢＲ）符号化、または粗粒度（ｃｏａｒｓｅ  ｇｒａｉｎｅｄ）もしくは細粒度（ｆｉｎｅ  ｇｒａｉｎｅｄ）のスケーラブルな符号化と組み合わせたストリームの切り替えによって行うことができる。今日の商業ストリーミングメディアシステム［１］は、ＭＢＲ符号化だけでなく、粗粒度スケーラビリティの一形態であるシニング（ｔｈｉｎｎｉｎｇ）に依拠する。ＭＢＲ符号化では、意味的に同一のコンテンツが、異なる符号化ビットレートで代替の複数のビットストリームに符号化され、サーバにおいて同じメディアファイルに記憶され、それにより、恐らくはビットストリームの切り替えを使用して、符号化ビットレートｒｃに対応する異なる品質レベルでコンテンツをストリーミングできるようにする［２］。粗粒度のスケーラブルな符号化（ＭＰＥＧ−２／４時間またはＳＮＲスケーラビリティ）では、コンテンツがいくつかのサブストリームまたはレイヤに符号化され、一度に１つのコンテンツレイヤを（恐らくは制約された時に）追加または破棄することにより、大きな差分で符号化ビットレートｒｃを変えることができる。シニングは粗粒度スケーラビリティの特殊な事例であり、他に依存するビデオフレーム（ＰおよびＢフレーム）が、独立したビデオフレーム（Ｉフレーム）の前に破棄され、独立したビデオフレームは、オーディオフレームの前に破棄される。将来の商業システムは、細粒度のスケーラビリティ（ＦＧＳ）もサポートする可能性がある。細粒度のスケーラブル符号化（３Ｄ  ＳＰＩＨＴ［６］、ＭＰＥＧ−４  ＦＧＳ［７］、またはＥＡＣ［８］など）では、符号化ビットレートｒｃが、プレゼンテーションごとに、場合によってはわずか１バイトの差分でいつでも変化することができる。ＦＧＳ符号化は、可変のネットワーク条件に適合する際により高い柔軟性を提供し、そのような条件下で品質を確実に向上させる。
【０００７】
変化するネットワーク条件に適合することを試みてコンテンツの符号化ビットレートｒｃを調整する既存技術のいくつかの例には、ｄｅ  ＣｕｅｔｏｓとＲｏｓｓ［９］が含まれ、この技術では、伝送レートと符号化ビットレートを分離する。この技術では、伝送レートが、ネットワークの伝送プロトコル（ＴＣＰあるいはＴＦＲＣ）によって決定されると想定する。それに基づいて、符号化ビットレートの適合型制御のための発見的なリアルタイムアルゴリズムを開発し、ストリーミングの前に伝送レートが分かる場合は、そのパフォーマンスを、最適なオフライン符号化ビットレート制御ポリシーと比較する。Ｒｅｊａｉｅ、Ｈａｎｄｌｅｙ、およびＥｓｔｒｉｎによる研究［４］は、ユニキャストの輻輳制御のコンテクストで、レイヤ化されたビデオを送信する方式を提案し、この方式は基本的に２つの機構を含む。１つの機構は、レイヤを追加および破棄する粗粒度の機構である（全体的な符号化ビットレートと品質を変える）。もう１つの機構は、（全体的な符号化ビットレートや品質を変えずに）受信機バッファを管理する、細粒度のレイヤ間帯域割り当て機構である。この手法に伴う可能性のある問題は、一度に１つの（恐らくは粗粒度の）レイヤを追加または破棄することにより、符号化ビットレートを変える点である。ＦＧＳ符号化メディアの場合のようにレイヤが細粒度である場合、一度に１つの（細粒度の）レイヤを追加または破棄することでは、通例、符号化ビットレートの十分に迅速な変化を提供することはできない。さらに、この追加および破棄の機構はやや経験的なので、この機構は、単にＦＧＳメディアに適さない可能性がある。Ｑ．Ｚｈａｎｇ、Ｚｈｕ、およびＹ−Ｑ．Ｚｈａｎｇによる研究［５］は、推定されるネットワーク帯域幅に合わせて符号化ビットレートを適合するリソース割り当て方式を提案する。この手法の新規な点は、オーディオ／ビデオのストリーミングに加えて、ファイル転送やウェブブラウズなどのすべての用途の歪みを可能な限り抑えること（換言すれば品質を可能な限り高めること）を考慮する点である。しかし、この手法の最適化プロセスは、個々のストリームの滑らかさは含まず、潜在的な品質の変動につながる可能性がある。
【０００８】
しかし、バッファリングと、符号化ビットレートを調整する能力をもってしても、インターネットを通じて要求に応じてメディアをストリーミングする既存の技術には、２つの問題がある。  
１．ネットワークの輻輳中に再生がしばしば失速する。すなわち、高ビットレートのコンテンツを再生している際に、ネットワークのビットレートがコンテンツのビットレート以下に低下すると、クライアントのバッファにコンテンツが足りなくなり、クライアントが再度バッファを満たす（「再バッファリング」イベントと称される）間、再生が停止する。  
２．スタートアップまでの遅延がしばしば長すぎる（約５秒）。
【０００９】
これらの両方の問題には既存の解決法があるが、常に有効であるとは限らない。最初の問題の解決法の１つは、ネットワークを通じて送信される平均ビットレート（伝送ビットレート）に比べて低い符号化ビットレートで符号化されたコンテンツをストリーミングするものである。これは、バッファが時間の経過とともに蓄積することを可能にする。そのように未再生の情報がクライアントに大量に確保されていると、一時的なネットワーク輻輳は再生に影響しなくなる。しかし、この解決法には２つの問題がある。第１に、コンテンツの符号化ビットレートは、ネットワークの平均伝送ビットレートほど高くなく、そのため、品質が本来可能な品質より低くなってしまう。第２に、バッファが、ストリーミングされるファイル自体とほぼ同じサイズに増大する可能性がある。これは、クライアント装置で余りにも多くのリソースを要する可能性がある。
【００１０】
最初の問題の別の解決法は、クライアントバッファを一定のレベル（通例は約１０秒）に維持することを試み、同時に、同じコンテンツについて異なる符号化ビットレートを切り替えて、ネットワークの伝送ビットレートに合わせようとするものである。しかし、ストリームを切り替える的確な時間を選択するのは難しいので、実際一般には再バッファリングイベントが観測される。的確に時間を選択することが難しい理由の１つは、いわゆる一定ビットレートの符号化でも、コンテンツの瞬間的な符号化ビットレートには自然な変動があり、それが、クライアントバッファの管理アルゴリズムを混乱させる場合があることである。
【００１１】
上記の第２の問題（スタートアップまでの遅延が長い）にも複数の解決法がある。解決法の１つは、短時間の初期伝送レートのバーストで、クライアントバッファを迅速に充たすものである。クライアントバッファが一杯になると、安全に再生を開始することができる。しかし、この解決法にはいくつかの問題がある。第１に、この解決法は、数秒間にわたって伝送ビットレートを上げるのに十分な「余裕」がネットワークにある時にしか適用できない。したがって、例えばモデム接続には通常は適用することができない。第２に、この解決法は、ネットワークに負荷をかけて、ネットワーク中の他のアプリケーションを低下させる。バースト期間中には、８０％ものパケット損失が発生する場合があり、同じボトルネックを共有するすべてのＴＣＰ接続を低下させることが分かっている。第３に、ネットワークにバーストのための余裕がある場合、ストリーミングアプリケーションは、暗に、ファイルの残りの期間に利用できる全帯域幅を使用していない可能性があり、すなわち品質が本来より低くなる可能性がある。
【００１２】
第２の問題の別の解決法は、実時間より遅くコンテンツを再生し、クライアントバッファが蓄積する間に再生を開始できるようにするものである。これは、革新的な解決法であるが、明らかな時間的歪みがある。
【００１３】
第２の問題の最後の解決法は、コンテンツの符号化ビットレートを一時的にネットワークの伝送ビットレートより低くして、クライアントバッファが蓄積する間に再生を開始できるようにするものである。これは、［１３］でＣｈｏｕ他によって提案される解決法である。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
本発明のシステムおよび方法は、これら既存技術の問題を解決し、高速のスタートアップ、途切れのない再生、およびストリーミングセッション全体にわたって最大限の品質と滑らかさを提供する。
【００１５】
先行する段落と、本明細書の残りの部分では、説明は、角括弧の対に含まれる数値識別子で識別される各種の個々の文献を参照することに留意されたい。例えば、そのような参照は、「参考文献［１］」、または単に「［１］」と記載することによって識別される。各識別子に対応する文献を含む参考文献のリストは、詳細な説明のセクションの最後に見つけることができる。
【課題を解決するための手段】
【００１６】
本発明は、コンピュータネットワークを通じてサーバからクライアントに送信されるストリーミングメディアデータの符号化ビットレートを制御するシステムおよび方法を対象とする。概して、この符号化ビットレートの制御は、ストリーミングメディアデータの符号化ビットレートを動的に調整してクライアントバッファ時間（ｂｕｆｆｅｒ  ｄｕｒａｔｉｏｎ）を制御するものである。その目的は、クライアントバッファがアンダーフローしないようにし、同時に、平均符号化ビットレートをネットワークの平均送信ビットレートに近く維持する（したがってデータの再生の品質を最大限に高める）ことである。符号化ビットレート制御の問題は、クライアントバッファ時間が可能な限り目標レベル近くに制御される、線形二次最適制御の標準的な問題として組み立てられる。最適制御プロセスの一部として符号化ビットレートを変更するかどうかを判断する際には、連続するフレームにわたる平均符号化ビットレートの平滑さも考慮される。これにより、ネットワーク条件が変化しても、より高く安定した品質が得られる。また、所与の平均符号化ビットレートに発生する瞬時符号化ビットレートの自然な変動も明示的に考慮に入れられる。これは、制御ループにリーキーバケツモデルを取り入れて、瞬時符号化ビットレートの自然な変動に起因するバッファ時間の変化が、ネットワークの輻輳に起因するバッファ時間の変化と間違えられないようにすることによって達成される。このシステムおよび方法では、クライアントバッファの実際の充足度ではなく、クライアントバッファにビットが到着する時間の上限が、目標レベルに合わせて制御されることに留意されたい。上限は、符号化ビットレートのリーキーバケツモデルに基づく。
【００１７】
クライアントバッファのアンダーフローを防止し、同時に平均符号化ビットレートをネットワークの平均送信ビットレートに近く維持することは、上述のユーザの期待の２つを満たす。すなわち、バッファがアンダーフローしなければ、途切れのない再生が可能になる。また、平均符号化ビットレートをネットワークの平均送信ビットレートに近く保つことは、利用できる平均通信帯域幅を前提として、可能な最高の品質でデータが再生されることを意味する。この結果、残る問題はスタートアップまでの遅延となる。本システムおよび方法では、この問題は、時間の経過とともにクライアントバッファのサイズを制御することによって解決される。より詳細には、上述のクライアントバッファの目標レベルが、スタートアップ時は小さく、そして時間の経過とともに徐々に増大していくように調整される。バッファが初めに小さいと、スタートアップまでの遅延を短くすることができる。また、バッファが最終的に大きく増大することを許されると、システムの堅牢性を高め、また、高く、ほぼ安定した品質を生み出す。したがって、クライアントバッファの管理は、ストリーミングメディアシステムのパフォーマンスに影響する主要な要素の１つである。
【００１８】
より詳細には、本システムおよび方法は、サーバによってサポートされるいくつかの符号化ビットレートの１つを示すストリーミングメディアデータストリームを生成するサーバを含む。初めに、サーバは、スタートアップ期間中に符号化ビットレートを選択する。しかし、スタートアップ期間が終わると、クライアントは、符号化ビットレート要求をサーバに与える。それに応答して、サーバは、クライアントから要求されるレートに最も近い、サポートされる符号化ビットレートの中で最も適当なレートでストリーミングメディアデータを送信する。クライアントによって要求される符号化ビットレートは、ストリーミングメディアデータの高品質の再生を提供し、同時にサーバからストリーミングメディアデータを受信するために使用されるクライアントのデコーダバッファが所望の持続時間レベルに満たされた状態を維持すると推定されるレートである。
【００１９】
クライアントは、上述の線形二次最適制御技術を使用して、所望の結果を与える符号化ビットレートを継続的に計算する。符号化ビットレートの計算は、検討対象のフレームの推定される最新の予想到着時間と規定された目標到着時間との差を小さくし、同時に符号化ビットレートの変化を規定された程度まで低減する符号化ビットレートを、フレーム単位で判定することを含む。上述のリーキーバケツモデルを利用する一実施形態では、符号化ビットレートの計算は、サーバのエンコーダバッファの状態を示すパラメータに基づく。それらのパラメータは、サーバで計算され、ストリーミングメディアデータとともにクライアントに与えられる。
【００２０】
より詳細には、サーバは初めに、サポートされるある符号化ビットレートに対応するデータストリームがサーバからストリーミングされた場合に存在するエンコーダバッファの初期状態を定義するパラメータのセットを計算する。サポートされる符号化ビットレートごとに別個のパラメータセットが計算され、ストリーミングメディアデータのプリアンブルでクライアントに提供される。それらのパラメータには、データストリームに関連付けられた符号化ビットレート、データストリームの符号化ビットレートに用いられるエンコーダバッファのサイズ、および、データストリームのその符号化ビットレートで示されるエンコーダバッファの初期の充足度を示す値が含まれる。サポートされる各符号化ビットレートに用いられるエンコーダバッファのサイズは様々に異なり、符号化ビットレートとエンコーダバッファの初期充足度を考慮して、ストリーミングプロセスのどの時点でもなおデータストリームを含む最小サイズのバッファとなるように選択されることに留意されたい。
【００２１】
エンコーダバッファの初期パラメータに加えて、サーバは、サーバでサポートされる各符号化ビットレートに生成されるストリーミングメディアデータの各フレームの上限との差分も計算する。この上限との差分は、生成されたばかりのフレームがバッファに完全に入力された後にバッファに現在保持されているビットに加えてサーバのエンコーダバッファが保持することのできるデータビット数として定義される。より詳細には、各フレームの上限との差分は、エンコーダバッファのサイズと、生成されたばかりのフレームが挿入された後のエンコーダバッファの充足度について計算された最後の値との差として計算される。生成されたばかりのフレームが挿入された後のエンコーダバッファの充足度は、生成されたばかりのフレームが挿入される前のエンコーダバッファの充足度値の計算された最後の値と、生成されたばかりのフレームのサイズとの合計として計算される。生成されたばかりのフレームを挿入する前のエンコーダバッファの充足度値は、ゼロと計算されるか、または、生成されたばかりのフレームの直前に生成されたフレームが挿入された後のエンコーダバッファの充足度について計算された値と、当該先行するフレームに関連付けられた符号化ビットレートを、前記先行フレームに関連付けられた瞬時フレームレートで割った値（いずれか大きい方の値）との差として計算される。瞬時フレームレートは、次のフレームが符号化されることが予定された時間から、生成されたばかりのフレームが符号化された時間を引いた値の逆数に等しい。一実施形態では、サーバが、符号化ビットレートが変化した後に生成されたフレームの連続の最初のフレームについて計算した上限との差分を、その連続の最初のフレームに関連付けられたデータの一部として、そのフレームの連続に関連付けられた符号化ビットレートの指示とともにクライアントに提供する。別の実施形態では、サーバは、生成されるすべてのフレームとともに差分値を提供する。
【００２２】
クライアントは、クライアントバッファをほぼ所望の時間レベルに維持するために、エンコーダバッファパラメータと上限との差分値（ｇａｐ  ｖａｌｕｅ）を用いて、検討対象のフレームの推定される最新の予想到着時間と、そのフレームの規定される目標到着時間との差を縮小するだろう符号化ビットレートを、フレーム単位で求める。上限との差分が、符号化ビットレートの変化の後の最初のフレームだけとともに提供される場合、クライアントは、差分値を含まないフレームについての上限との差分を推定する。上述のエンコーダバッファの初期条件を与えられると、クライアントは受信するすべてのフレームの上限との差分値を計算できることにも留意されたい。したがって、サーバが差分値を継続的に計算し、提供するように構成されない代替的な実施形態でも、クライアントコンピュータが自身で差分値を計算することができる。
【００２３】
新しい平均符号化ビットレートのフレームがクライアントに到着すると、上限の差分にシフトがある。このシフトは、約数秒であり、したがって無視できるものではなく、コントローラを混乱させる可能性がある。これを解決する方法の１つは、制御目標スケジュールに同時に起こるシフトを導入するものである。そのために、サーバは、符号化ビットレートの変化があった後の最初のフレームに相当する各フレームのシフト値も計算する。このシフト値は、その新しい符号化ビットレートで符号化された場合に、その最初のフレームの直前に生成されるフレームに関連付けられることになる上限との差分と、元の符号化ビットレートで符号化されたフレームに実際に関連付けられた上限との差分との差に相当する。シフト値は、符号化ビットレートが変化した後の最初のフレームとともにクライアントに提供される。クライアントは、受信したばかりの「最初の」フレームに関連付けられた、現在予定された目標到着時間を、提供されたシフト値だけシフトさせ、そして、後続のフレームに現在予定された目標到着時間が、ある時間をかけて、それらのフレームの元の目標到着時間に全体として（ｃｏｌｌｅｃｔｉｖｅｌｙ）近づいて行き、最終的には一致するように、それらの目標到着時間をシフトさせる。このようにして、符号化ビットレートが変更された際の上限との差分のシフトの悪影響が緩和され、目標到着時間の値が最終的には再度制御される。
【００２４】
各フレームの目標到着時間に関して、目標到着時間は、フレームの目標時間とその再生時間との間の時間量を、スタートアップ期間後に、フレームの実際の到着時間をその目標到着時間より後にする可能性のあるネットワークジッタ、遅延、およびスループットによって、フレームが予定されたその再生時間より後に到着することにならないようにするのに十分な大きさにするように選択される。スタートアップ期間中に、目標到着時間は、スタートアップまでの遅延を短くするのを助けるために、目標到着時間を再生時間により近くするように選択される。一実施形態では、これは、対数的な目標スケジュールを使用して各フレームの目標到着時間を設定することによって達成される。別の実施形態では、これは、２つの部分からなる線形目標スケジュールを使用して各フレームの目標到着時間を設定することによって達成され、その場合は、スタートアップ期間中に到着するフレームの目標到着時間と再生時間との間の差が、ネットワークジッタ、遅延、およびスループットの変化を補償するのに十分な大きさの規定の時間量まで線形に増大し、規定の時間量に達した後は、差は実質的に一定のままになる。
【００２５】
スタートアップまでの遅延は、初期符号化ビットレートでアンダーフロー条件が発生しないことを保証するのに必要な最小量のデータがクライアントのデコーダバッファに得られた時にストリーミングメディアデータの最初のフレームの再生を開始することにより、さらに最小に抑えられることに留意されたい。さらに、アンダーフロー条件が発生しないことを保証するのに必要な最小のデータ量は、符号化ビットレートに相対的に到着レートが上がるのにつれて減るので、初期符号化ビットレートは、クライアントにおけるストリーミングメディアデータの予想到着レートより小さいレベルに設定することができる。したがって、クライアントが符号化ビットレートの変更を要求する前のスタートアップ期間中は、サーバは、初期符号化ビットレートでストリーミングメディアデータを提供する。一実施形態では、初期符号化ビットレートは、予想到着レートのおよそ２分の１に設定され、予想到着レートは、ネットワークで利用可能な現在の帯域幅でのサーバからの予想送信レートになると推定される。スタートアップ期間は、初期符号化レートについて計算された検討対象のフレームの推定された一番遅い到着時間の最初の瞬間の前であって、そのフレームの目標到着時間より早くなっている期間と定義されることができることに留意されたい。
【００２６】
クライアントが、また符号化ビットレートの変化を規定の程度に低減する各フレームの符号化ビットレートを識別することに関しては、規定の程度は、符号化ビットレートが上昇したかどうかに応じて異なってよいことに留意されたい。上昇していた場合、その後の符号化ビットレートの変化がその程度まで最小化される規定の程度は、符号化ビットの最も新しい変化がレートを下げた場合と比べて大きくされる。さらに、符号化ビットレートの大きな変更、あるいは頻繁な変更に起因する品質の変動を最小に抑えることも望ましい。符号化ビットレートの変化を安定させるために、以下の措置を取ることができる。初めに、クライアントが、上昇を意味する新しい符号化ビットレートを識別した場合は、新しいレートが現在のフレームの移動平均到着レートを超えない場合のみ、サーバに新しい符号化ビットレートが要求される。別の実施形態では、新しい符号化ビットレートが現在のフレームの移動平均到着レートを超える場合でも、現在のクライアントバッファ時間が、規定の時間（例えば６０秒）が経過する前により高い符号化ビットレートで費やされないと推定される量だけ所望の時間レベルを超える場合は、上昇を意味する新しい符号化ビットレートがサーバに要求される。しかし、クライアントが、減少を意味する新しい符号化ビットレートを識別した場合は、１つ前の符号化ビットレートからの著しい逸脱を意味する場合でも、新しい符号化ビットレートがサーバに要求される。この理由は、符号化ビットレートが下がる際にはクライアントバッファがアンダーフローする危険性が少ないためである。
【００２７】
上述のフレームの移動平均到着レートに関して、このレートを計算する新しい手順が本システムおよび方法で用いられる。より詳細には、移動平均到着レートは、現在受信されるパケットの１つ前のパケットに計算される移動平均到着レートと分数の（ｆｒａｃｔｉｏｎａｌ）重み係数との積を、現在受信されるパケットの瞬間到着レートと、１から分数の重み係数を引いた値との積に加えることにより、パケット単位で計算される。この計算で、分数の重み係数は、従来のように定数ではなく、受信されるパケット間の到着間の差分に基づく。より詳細には、現在受信されるパケットｋの分数の重み係数β（ｋ）は、
【００２８】
【数１】
2006174419.tif 000003
【００２９】
と計算され、αは、規定された時間定数の逆数であり、ｔ（ｋ）は、現在のパケットの実際の到着時間であり、ｔ（ｋ−１）は、現在のパケットの直前に受信されたパケットの実際の到着時間であり、ｔ（０）は、ストリーミングメディアデータの最初のパケットの到着時間である。この場合、現在のパケットｋの瞬時到着レートｒａ（ｋ）は、
【００３０】
【数２】
2006174419.tif 000004
【００３１】
と計算され、ｂ（ｋ）は、現在のパケットの大きさである。ｂ（ｋ）をビット単位で表し、ｔａ（ｋ）−ｔａ（ｋ−１）を秒単位で表すと、移動平均到着レートが、一秒当たりのストリーミングメディアデータビットの到着レートを表す。ストリーミングメディアのレートの任意の単位に同様の手順を用いることができることに留意されたい。
【００３２】
先に述べたように、サーバは、サーバによってサポートされる複数の符号化ビットレートの１つを示すデータストリームを生成し、クライアントから要求されるレートに最も近い、最も適切なサポートされる符号化ビットレートでデータストリームを送信する。利用できる符号化ビットレートの数は、データの符号化方式によって決まる。例えば、細粒度のスケーラブルな符号化方式が用いられる場合、理論的には、多数のレートを利用することができる（実際的な理由から数は５０個など理論上より低くなる場合が多い）。これに対し、粗粒度のスケーラブル符号化方式または複数ビットレートの符号化方式が用いられる場合は、サーバから利用できる符号化ビットレートの数はより限られる。したがって、事例によっては、クライアントによって識別された最適な符号化ビットレートがサーバから利用できない場合がある。また、利用可能な一致する符号化ビットレートがある場合でも、上限との差分が、そのレートに切り替えるとクライアントバッファのアンダーフローの危険性があるような差分である場合もある。これらを考慮して、本システムおよび方法は、クライアントによって識別された最適な符号化ビットレートを考慮して、利用可能なレートの中から最も適当な符号化ビットレートを判定する技術を含む。利用可能なレートは、ストリーミングメディアデータのプリアンブルでサーバからクライアントに提供できることに留意されたい。そのような場合は、クライアント自身が、分析を行い、結果判定されたサポートされる符号化ビットレートをサーバに要求する。しかし、代替の実施形態では、クライアントが識別した最適な符号化ビットレートを要求し、サーバが分析を行ってサポートされるレートの中でどのレートが最も適当かを判定する。そして、サーバは、選択された符号化ビットレートを示すデータストリームを提供する。いずれの場合も、分析は、クライアントで識別された最適な符号化ビットレートと等しい、あるいは、等しいレートがない場合は、最適な符号化ビットレートに最も近く、小さい、サポートされた符号化ビットレートを見つけるものである。見つけられたサポートされた符号化ビットレートが、ストリーミングメディアデータの最後に生成されたフレームに関連付けられた符号化ビットレートより低いと、後続のフレーム（またはクライアントによって指定されたフレームから開始するフレーム）はすべて、そのサポートされたレートで生成される。これに対し、見つけられたサポートされる符号化ビットレートが、最後に生成されたフレームに関連付けられた符号化ビットレートより高い場合は、見つかったそのサポートされた符号化ビットレートで符号化された場合に最後に生成されたフレームに関連付けられる上限との差分と、現在の符号化ビットレートで符号化されたそのフレームに関連付けられた上限との差分との差が、許容される最大の差分値以下、あるいは等しいかどうかが判定される。差分が許容される最大の差分値より小さい場合、影響を受ける後続フレームは、見つけられたサポートされたレートで生成される。これに対し、差が許容される最大の差分値以上である場合は、次に低いサポートされた符号化ビットレートが見つけられ、前述の動作が繰り返されて、最終的に適切なレートを特定する。
【００３３】
許容される最大の差分値は、クライアントで計算され、サーバが上記の分析を行う場合は、クライアントは、新しい符号化ビットレートでデータの要求とともに差分値を提供する。クライアントは、クライアントで検討対象とされるフレームの直前にサーバから提供されたフレームが要求される符号化ビットレートで符号化された場合にそのフレームに関連付けられる最新の予想到着時間が、そのフレームの目標到着時間からその再生期限までの隔たりの規定された分数（例えば隔たりの３分の１）以下になるように、許容される最大の差分値を選択する。
【００３４】
ここで述べた利点に加えて、本発明の他の利点は、添付図面と併せて以下の詳細な説明を読むことにより明らかになろう。
【００３５】
本発明の具体的な特徴、態様、および利点は、以下の説明、頭記の特許請求の範囲、および添付図面とともにより理解されよう。
【発明を実施するための最良の形態】
【００３６】
以下の本発明の好ましい実施形態の説明では、添付図面を参照するが、それらの図面は、説明の一部をなし、それらの図面には、本発明が実施されることが可能な具体的な実施形態が例示として示される。他の実施形態を利用することができ、本発明の範囲から逸脱せずに、構造的な変更を加えてよいことが理解される。
【００３７】
Ｉ．コンピューティング環境
本発明の好ましい実施形態を説明する前に、本発明の一部を実装することが可能な適切なコンピューティング環境の簡単で概略的な説明を述べる。図１に、適切なコンピューティングシステム環境１００の例を示す。コンピューティングシステム環境１００は、適切なコンピューティング環境の一例に過ぎず、本発明の使用または機能性の範囲についての限定を示唆するものではない。また、コンピューティング環境１００は、例示的な動作環境１００に示す構成要素の１つまたは組合せに関連する依存性や必要要件を有するものとも解釈すべきでない。
【００３８】
本発明は、数多くの他の汎用または特殊目的のコンピューティングシステム環境または構成で機能する。本発明に使用するのに適する可能性があるよく知られるコンピューティングシステム、環境、および／または構成の例には、これらに限定しないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサを利用したシステム、セットトップボックス、プログラム可能な家電製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスを含む分散コンピューティング環境などがある。
【００３９】
本発明は、コンピュータによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的な文脈で説明することができる。一般に、プログラムモジュールには、特定のタスクを行うか、特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本発明は、通信ネットワークを通じてつながれた遠隔の処理デバイスによってタスクが行われる分散コンピューティング環境で実施してもよい。分散コンピューティング環境では、プログラムモジュールは、メモリ記憶装置を含むローカルおよびリモート両方のコンピュータ記憶媒体に置くことができる。
【００４０】
図１を参照すると、本発明を実施する例示的なシステムは、コンピュータ１１０の形態の汎用コンピューティングデバイスを含む。コンピュータ１１０の構成要素には、これらに限定しないが、処理装置１２０、システムメモリ１３０、およびシステムメモリを含む各種のシステム構成要素を処理装置１２０に結合するシステムバス１２１が含まれうる。システムバス１２１は、各種のバスアーキテクチャを使用した、メモリバスあるいはメモリコントローラ、ペリフェラルバス、およびローカルバスを含む数種のバス構造のいずれでもよい。限定ではなく例として、そのようなアーキテクチャには、ＩＳＡバス、ＭＣＡバス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡローカルバス、および、メザニンバスとも称されるＰＣＩバスがある。
【００４１】
コンピュータ１１０は、通例、各種のコンピュータ読取り可能媒体を含む。コンピュータ読取り可能媒体は、コンピュータ１１０によるアクセスが可能な利用可能媒体でよく、揮発性および不揮発性の媒体、取り外し可能および取り外し不能の媒体を含む。限定ではなく例として、コンピュータ読取り可能媒体は、コンピュータ記憶媒体と通信媒体からなることができる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、あるいは他のデータなどの情報を記憶するための方式または技術で実施された、揮発性および不揮発性、取り外し可能および取り外し不能の媒体が含まれる。コンピュータ記憶媒体には、これらに限定しないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶、または他の磁気記憶装置、あるいは必要とする情報を記憶するために使用することができ、コンピュータ１１０によるアクセスが可能な他の媒体が含まれる。通信媒体は、通例、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを、搬送波や他の移送機構などの変調データ信号として実施し、情報伝達媒体を含む。用語「変調データ信号」とは、信号中に情報を符号化するような方式で特性の１つまたは複数を設定または変化させた信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークや直接配線接続などの有線媒体と、音響、ＲＦ、赤外線、他の無線媒体などの無線媒体がある。上記の媒体の組合せもコンピュータ読取り可能媒体の範囲に含める。
【００４２】
システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性メモリおよび／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動時などにコンピュータ１１０内の要素間の情報転送を助ける基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）は、通例、ＲＯＭ１３１に記憶される。ＲＡＭ１３２は、通例、処理装置１２０から即座にアクセス可能な、および／または処理装置１２０によって現在操作されているデータおよび／またはプログラムモジュールを保持する。限定ではなく例として、図１には、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００４３】
コンピュータ１１０は、この他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体も含むことができる。単なる例として、図１には、取り外し不能、不揮発性の磁気媒体の読み書きを行うハードディスクドライブ１４１、取り外し可能、不揮発性の磁気ディスク１５２の読み書きを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光学媒体などの取り外し可能、不揮発性の光ディスク１５６の読み書きを行う光ディスクドライブ１５５を示す。例示的動作環境で使用することができる他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体には、これらに限定しないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体素子ＲＡＭ、固体素子ＲＯＭなどがある。ハードディスクドライブ１４１は通例、インターフェース１４０などの取り外し不能メモリインターフェースを通じてシステムバス１２１に接続され、磁気ディスクドライブ１５１と光ディスクドライブ１５５は、通例、インターフェース１５０などの取り外し可能メモリインターフェースでシステムバス１２１に接続される。
【００４４】
上記で説明し、図１に示すドライブとそれに関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、および他のデータの記憶をコンピュータ１１０に提供する。図１では、例えば、ハードディスクドライブ１４１に、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７が記憶されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでも異なってもよいことに留意されたい。ここでは、それらが少なくとも異なるコピーであることを表すために、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７には、異なる参照符号を付している。ユーザは、キーボード１６２や、一般にはマウス、トラックボール、タッチパッドと称されるポインティングデバイス１６１などの入力装置を通じてコンピュータ１１０にコマンドと情報を入力することができる。他の入力装置（図示せず）としては、マイクロフォン、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナ等が可能である。上記および他の入力装置は、多くの場合、システムバス１２１に結合されたユーザ入力インターフェース１６０を通じて処理装置１２０に接続されるが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）などの他のインターフェースおよびバス構造で接続することもできる。モニタ１９１または他のタイプの表示装置も、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタに加えて、コンピュータは、スピーカ１９７やプリンタ１９６などの他の周辺出力装置も含むことができ、それらの装置は、出力周辺インターフェース１９５を通じて接続されることができる。画像のシーケンス１９３を取り込むことができるカメラ１９２（デジタル／電子静止画像カメラまたはビデオカメラ、あるいはフィルム／写真スキャナ）も、パーソナルコンピュータ１１０の入力装置として含めることができる。さらに、図には１つのみのカメラを示すが、パーソナルコンピュータ１１０の入力装置として複数のカメラを含めてもよい。１つまたは複数のカメラからの画像１９３は、適切なカメラインターフェース１９４を介してコンピュータ１１０に入力される。インターフェース１９４は、システムバス１２１に接続され、それにより、ＲＡＭ１３２、またはコンピュータ１１０に関連付けられた他のデータ記憶装置の１つに画像を送り、記憶することができる。しかし、画像データは、カメラ１９２の使用を必要とせずに、上記のコンピュータ読取り可能媒体からコンピュータ１１０に入力されることもできることに留意されたい。
【００４５】
コンピュータ１１０は、リモートコンピュータ１８０などの１つまたは複数のリモートコンピュータとの論理接続を使用するネットワーク環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードであり、図１にはメモリ記憶装置１８１のみを示すが、通例は、コンピュータ１１０との関連で上述した要素の多くまたはすべてを含む。図１に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１とワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含むことも可能である。このようなネットワーク環境は、オフィス、企業内のコンピュータネットワーク、イントラネット、およびインターネットで一般的である。
【００４６】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、ネットワークインターフェースあるいはアダプタ１７０を通じてＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、通例、インターネットなどのＷＡＮ１７３を通じて通信を確立するためのモデム１７２または他の手段を含む。モデム１７２は、内蔵型でも外付け型でもよく、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク環境では、コンピュータ１１０との関連で図示するプログラムモジュール、またはその一部は、遠隔のメモリ記憶装置に記憶することができる。限定ではなく例として、図１では、リモートアプリケーションプログラム１８５がメモリ装置１８１にある。図のネットワーク接続は例示的なものであり、コンピュータ間に通信リンクを確立する他の手段を使用してよいことは理解されよう。
【００４７】
ここまで例示的動作環境を説明したので、この説明のセクションの残りの部分では本発明を実施するプログラムモジュールを説明する。
【００４８】
ＩＩ．問題の明確化
Ａ．時間座標
時間を表すために使用される時間座標、あるいは計時機構を区別することは有用である。本明細書では、メディア時間とは、元のコンテンツを取り込み、タイプスタンプを付すために使用されるデバイス上で稼動する計時機構を意味し、一方、クライアント時間とは、コンテンツを再生するために使用されるクライアント上で稼動する計時機構を指す。メディア時間は、メディアの取り込み時に実時間（すなわち実時間の１秒に１秒のメディア時間が経過する）であり、一方、クライアント時間は、メディアの再生時に実時間であると想定する。対応するイベントを示す下付き文字および他の引数と併せて、記号τを使用してメディア時間を表し、記号ｔでクライアント時間を表す。例えば、τｄ（０）、τｄ（１）、τｄ（２）．．．を使用して、メディア時間のフレーム０，１，２の再生の期限を表し、一方、ｔｄ（０）、ｔｄ（１）、ｔｄ（２）．．．を使用して、クライアントにおけるフレーム０，１，２．．．の再生の期限を表す。コンテンツは、実時間のｖ倍のレートで再生されることができる。したがって、メディア時間からクライアント時間への変換は、
【００４９】
【数３】
2006174419.tif 000005
【００５０】
と表すことができ、ｔ０とτ０は、それぞれメディアの座標系とクライアントの座標系におけるフレーム０の再生（あるいはシークまたは再バッファリングイベントの後の最初のフレームの再生）などの一般的な最初のイベントの時間を表す。
【００５１】
Ｂ．リーキーバケツモデル
ここで、ネットワーク２０４の等時性通信チャネルでエンコーダ２００とデコーダ２０２の両方が実時間で稼動するシナリオを考えられたい。その場合、瞬間的なチャネルレートに瞬間的な符号化ビットレートを一致させるために、図２に示すように、エンコーダ２００とネットワーク２０４の間にエンコーダバッファ２０６が必要とされ、ネットワーク２０４とデコーダ２０２の間にデコーダバッファ２０８が必要とされる。スケジュールは、符号化ビットストリームの連続したビットが通信パイプラインの所与の点を通過する時間の連続である。図３のグラフは、図２の点Ａ、Ｂ、Ｃ、およびＤを通過するビットのスケジュールを示す。スケジュールＡは、取り込まれたフレームが瞬間的に符号化され、エンコーダバッファに入れられるスケジュールである。このスケジュールは、ｎ番目のステップが時間τ（ｎ）にｂ（ｎ）ビットだけ上がる階段型になっており、τ（ｎ）は、フレームｎが符号化される時であり、ｂ（ｎ）は、結果として生じる符号化にあるビット数である。スケジュールＢおよびＣは、それぞれビットが通信チャネルに入るスケジュールと、通信チャネルを出るスケジュールである。これらスケジュールの勾配は、１秒当たりＲビットであり、Ｒは、チャネルの通信レートである。スケジュールＤは、フレームがデコーダバッファから取り出され、表示のために瞬間的に復号されるスケジュールである。スケジュールＤは、単にスケジュールＡをずらしたものであることに留意されたい。また、スケジュールＢはスケジュールＡの下限であり、一方、スケジュールＣはスケジュールＤの上限であることにも気づかれよう。実際、スケジュールＡとＢの差分は、どの時点においてもエンコーダバッファのサイズをビット単位で表し、一方、スケジュールＣとＤの差分も同様にデコーダバッファのサイズを表す。エンコーダバッファとデコーダバッファのサイズは、相補的である。したがって、符号化スケジュール（ＡまたはＤ）は、図４のグラフで示すように、バッファチューブの中に含まれることができ、バッファチューブは、勾配Ｒ、高さＢ、およびチューブの一番上からの初期オフセットＦｄ（あるいは、同等にチューブの一番下からの初期オフセットＦｅ＝Ｂ−Ｆｄ）を有する。Ｄ＝Ｆｄ／Ｒは、最初のビットが受信機に到着する時間から、最初のフレームが復号される時間までのスタートアップの遅延であることが理解できよう。したがって、所与のＲについてＦｄを最小にすることが重要となる。
【００５２】
リーキーバケツとは、エンコーダバッファの喩えである。エンコーダは、時間τ（ｎ）にリーキーバケツにｂ（ｎ）ビットを投入し、そのビットは、レートＲで漏れ出して行く。一般に、バケツが時に空になるように、リークレートＲを高くすることが可能である。したがって、フレームｎがバケツに加えられる直前のエンコーダバッファの充足度Ｆｅ（ｎ）と、フレームｎがバケツに加えられた直後のエンコーダバッファの充足度Ｂｅ（ｎ）は、動的なシステムに従って、最初のエンコーダバッファの充足度Ｆｅ（０）＝Ｆｅから進展して行き、
Ｂｅ（ｎ）＝Ｆｅ（ｎ）＋ｂ（ｎ）                                （２）
Ｆｅ（ｎ＋１）＝ｍａｘ｛０，Ｂｅ（ｎ）−Ｒ／ｆ（ｎ）｝          （３）
ここで
【００５３】
【数４】
2006174419.tif 000006
【００５４】
がｎ＝０，１，２．．．についての瞬間的なフレームレートである。Ｒが十分に低い場合、バケツは、空になる（アンダーフローする）ことは決してないが、Ｒが低すぎると、バケツは最終的にオーバーフローする。バッファが決して空にならないような最大のＲを、ビットストリームの平均符号化ビットレートｒｃとみなす。これは、続く２つの段落でより正確にする。
【００５５】
サイズＢ、レートＲ、および初期の充足度Ｆｅを有するリーキーバケツが、すべてのｎについてＢｅ（ｎ）≦Ｂである場合に、段差｛（ｂ（ｎ），τ（ｎ））｝を特徴とするスケジュールを有するストリームを含むものとする。リークレートＲと初期の充足度Ｆｅを与えられて、ストリームを含むのに必要とされる最小のバケツの大きさは、
【００５６】
【数５】
2006174419.tif 000007
【００５７】
と定義され、一方、それに対応する初期デコーダバッファの充足度は、
【００５８】
【数６】
2006174419.tif 000008
【００５９】
と定義される。
【００６０】
Ｆｅに対するこれらそれぞれの最小値は、
【００６１】
【数７】
2006174419.tif 000009
【００６２】
と表される。注目すべき点として、これらはそれぞれ、同じＦｅの値で最小になることが［１０］、定理２に示され、したがってＦｅは
【００６３】
【数８】
2006174419.tif 000010
【００６４】
に等しい。したがって、スケジュール｛（ｂ（ｎ），τ（ｎ））｝を有するビットストリーム、各ビットレートＲにつき、そのストリームを含み、最小のバッファサイズＢと最小のスタートアップ遅延Ｄ＝Ｆｄ／Ｒとを有する固有のリーキーバケツがある。これらのパラメータは、上記の式で計算することができる。
【００６５】
リークレートＲが十分に低いと、リーキーバケツは、初期の充足度
【００６６】
【数９】
2006174419.tif 000011
【００６７】
で開始するときにアンダーフローしない。最大のそのようなレートＲを、符号化スケジュール｛（ｂ（ｎ），τ（ｎ））｝を有するビットストリームの平均符号化ビットレートｒｃとして使用することができる。
【００６８】
ｒｃより大きいリークレートＲを用いることもできる。
【００６９】
【数１０】
2006174419.tif 000012
【００７０】
と
【００７１】
【数１１】
2006174419.tif 000013
【００７２】
の両方が、Ｒで区分的線形に凸で減少することが［１０］に示されている。したがって、伝送レートＲが平均符号化ビットレートｒｃより大きい場合、スタートアップまでの遅延
【００７３】
【数１２】
2006174419.tif 000014
【００７４】
は、
【００７５】
【数１３】
2006174419.tif 000015
【００７６】
と比較して短縮することができる。この事実は、後にセクションＩＶ−Ａにおいて用いる。
【００７７】
したがって、リークレートＲ＝ｒｃ、サイズ
【００７８】
【数１４】
2006174419.tif 000016
【００７９】
、および、初期のデコーダバッファ充足度
【００８０】
【数１５】
2006174419.tif 000017
【００８１】
を有するリーキーバケツは、図４のように符号化スケジュールの境界を定める直線のバッファチューブに相当する。メディアファイルの各ストリームは、符号化スケジュールを有し、そのため、各ストリームは、そのストリームの平均符号化ビットレートｒｃに等しい勾配を有する直線のバッファチューブに相当する。バッファチューブのサイズＢと、符号化スケジュールに対するバッファチューブのオフセットＦｅ（またはＦｄ）は、可変ビットレート（ＶＢＲ）ストリーム（スケーラブルストリームの一定品質のサブストリームなど）については上記の式で計算するか、または、ストリームが一定ビットレート（ＣＢＲ）ストリームである場合は、ストリームを符号化するために使用される実際のエンコーダバッファのサイズＢおよび初期状態Ｆｅから得ることができる。
【００８２】
以下で、図４に示す、フレームｎにおける、バッファチューブの上限と符号化スケジュールとの差分ｇ（ｎ）を考察する。デコーダバッファの充足度Ｆｄ（ｎ）＝Ｂ−Ｆｅ（ｎ）は、次のように表すこともでき、
【００８３】
【数１６】
2006174419.tif 000018
【００８４】
ｒｃ（ｎ）は、バッファチューブの符号化ビットレートであり、ここでは、符号化ビットレートの制御が適用され、ストリームが切り替えられるのに伴って、異なる符号化ビットレートを有する異なるバッファチューブに様々なフレームがある可能性があることを考慮に入れることに留意されたい。
【００８５】
Ｃ．レート制御モデル
ここで、ビットが一定のレートｒａでクライアントに到着するものと想定されたい。そして、フレームｎ−１のｂ（ｎ）／ｒａ秒後に、フレームｎ（サイズｂ（ｎ））がクライアントに到着する。実際、ビットのインデックスは、その到着時間に比例する。図４のスケジュールの縦の目盛りをｒａで割ると、図５のグラフに示すように、ビットではなくクライアント時間に換算したスケジュールが得られる。ｒａで割った符号化スケジュールが到着スケジュールになり、到着スケジュールは、各ｎについて、クライアントにフレームｎが到着する時間ｔａ（ｎ）を提供する。バッファチューブの上限（ビット単位）をｒａで割ったものがバッファチューブの上限（時間単位）になり、この上限は、フレームｎがそれまでには到着することが保証される時間ｔｂ（ｎ）を各ｎに提供する。同じグラフに再生の期限が示され、これは、（瞬間的な復号の後に）フレームｎが再生されることが予定される時間ｔｄ（ｎ）である。したがって、フレームの到着時間からその再生の期限までの差分が、フレームの到着時におけるクライアントのバッファ時間になる。この差分は、連続的な再生を可能にするために非負（ｎｏｎ−ｎｅｇａｔｉｖｅ）でなければならない。
【００８６】
実際には、到着レートは、一定ではない。ｔａ（ｎ−１）とｔａ（ｎ）が、それぞれフレームｎとｎ−１の到着時間である場合は、
【００８７】
【数１７】
2006174419.tif 000019
【００８８】
をフレームｎにおける瞬間的な到着レートと定義することができる。実際には、フレームｎにおける平均到着レートは、セクションＩＶ−Ｃで詳しく述べるように、ｒａ（ｎ）の以前の値の移動平均
【００８９】
【数１８】
2006174419.tif 000020
【００９０】
によって推定される。したがって、式（１１）を使用して、フレームｎの到着時間は、フレームｎ−１の到着時間に換算して次のように表すことができ、
【００９１】
【数１９】
2006174419.tif 000021
【００９２】
ｖ（ｎ）の項は、低速で移動する移動平均
【００９３】
【数２０】
2006174419.tif 000022
【００９４】
を用いる効果を取り込む誤差の項である。しかし、式（１０）から、
【００９５】
【数２１】
2006174419.tif 000023
【００９６】
であることが分かり、そのため（式（１４）を式（１３）に置き換えると）次が得られる。
【００９７】
【数２２】
2006174419.tif 000024
【００９８】
次いで、次のようにフレームｎのバッファチューブの上限（時間単位）を定義し、
【００９９】
【数２３】
2006174419.tif 000025
【０１００】
そのため、
【０１０１】
【数２４】
2006174419.tif 000026
【０１０２】
となり、次の更新した式が得られる。
【０１０３】
【数２５】
2006174419.tif 000027
【０１０４】
ここで
【０１０５】
【数２６】
2006174419.tif 000028
【０１０６】
は、この場合も、局所的に一定である到着レートを中心とした変動を捉える誤差の項である。
【０１０７】
式（１６）を使用して、クライアントは、測定された到着時間ｔａ（ｎ−１）、推定された到着レート
【０１０８】
【数２７】
2006174419.tif 000029
【０１０９】
、および、ｇ（ｎ−１）（これは、フレームｎ−１でデータとともにクライアントに送信するか、セクションＶ−Ｅで述べるようにクライアントで計算することができる）から、ｔｂ（ｎ−１）を計算することができる。そして、式（１８）を使用して、クライアントは、フレームレートと到着レートがほぼ一定のままであると想定して、ｔｂ（ｎ）が所望の値に達するように符号化ビットレートｒｃ（ｎ）を調整することができる。この観点から、式（１８）は、フィードバック制御システムの状態遷移式とみなすことができ、したがって、制御理論的手法を用いて符号化ビットレートを規制することができる。
【０１１０】
Ｄ．制御の目標
式（１８）に定義した状態遷移式で、クライアントバッファがアンダーフローしないように符号化ビットレートを規制することにより、途切れのない再生を実現することができる。時間の経過とともに増加するような安全性のマージンを導入するために、図５に示すように目標スケジュールが導入され、再生期限からのその距離は、時間の経過とともに徐々に増大する。符号化ビットレートを規制することにより、目標スケジュールを追跡するようにバッファチューブの上限をコントロールすることが試みられる。バッファチューブの上限が目標スケジュールに近いと、すべてのフレームの到着時間は、各自の再生期限より確実に早くなり、したがって、途切れのない再生が保証される。（上限ではなく）実際の到着時間を目標に合わせて制御すると、１フレーム当たりのビット数がほぼ一定になり、その結果、全体として非常に低い品質になることに留意されたい。リーキーバケツモデルを考慮に入れることにより、所与の平均符号化ビットレートに対して以前に設定された限界内で、コンテンツの符号化の複雑度に従って瞬間的な符号化ビットレートを自然に変動させる制御を確立することが可能になる。
【０１１１】
目標スケジュールに合わせて上限を制御することが本発明の主要な目的であるが、符号化ビットレートの大きなあるいは頻繁な変更に起因する品質の変動を最小に抑えることも望ましい。これは、相対的な符号化ビットレートの差についてのペナルティをコスト関数に取り込むことによって実現することができる。
【０１１２】
ｔＴ（ｎ）がフレームｎの目標を表すとすると、次のコスト関数を使用して両方の考慮事項を反映する。
【０１１３】
【数２８】
2006174419.tif 000030
【０１１４】
最初の項は、目標スケジュールからのバッファチューブ上限の逸脱に制約を課し、２番目の項は、連続したフレーム間の相対的な符号化ビットレートの差に制約を課す。Ｎは、制御ウィンドウの大きさであり、σは、これら２つの項の均衡をとるラグランジュ乗数あるいは重み付けパラメータである。
【０１１５】
ＩＩＩ．最適な制御の解決法
最適な制御の解決法を提示する前に、目標スケジュールの設計原理を説明する。
【０１１６】
Ａ．目標スケジュールの設計
図６は、例示的な目標スケジュールを示すグラフである。再生の期限と目標スケジュールとの差分が、要求されるクライアントバッファ時間（クライアント時間単位）である。差分がストリーミングのスタートアップ時に小さいと、スタートアップまでの遅延を小さくすることが可能になり、一方、差分が時間の経過とともに徐々に増大すると、ジッタ、遅延、およびスループットの変化に対処する受信機能力を次第に増大させる。
【０１１７】
目標スケジュールの勾配は、平均符号化ビットレートを平均到着時間に関連付ける。フレームｎの目標をｔＴ（ｎ）とする。図６に示すように、フレームｎにおける目標スケジュールの勾配は、
【０１１８】
【数２９】
2006174419.tif 000031
【０１１９】
である。
【０１２０】
式（１８）から、上限ｔｂ（ｎ）が完全に目標スケジュールと合致すると（すなわちｔｂ（ｎ）＝ｔＴ（ｎ））、到着レートｒａが一定になる（すなわちｗ（ｎ−１）の項が消滅する）。
【０１２１】
【数３０】
2006174419.tif 000032
【０１２２】
したがって、初めに、勾配が低い、すなわち１／ｖより小さいと、ｒａ／ｒｃがｖより大きくなり、クライアント時間の１秒当たりｖ秒分以上のコンテンツが受信され、クライアントバッファを増大させる（バッファはクライアント時間の１秒にｖ秒分のコンテンツしか再生して放出しない）。時間が経過し、勾配が１／ｖに近づくにつれてｒａ／ｒｃがｖに近づき、コンテンツは同じ速度ｖで受信および再生されるので、バッファは、相対的に一定のままとなる（瞬間的な符号化ビットレートの変動による変化以外は）。次に、一般的な設計理念を示す２つの目標スケジュール関数を提示する。
【０１２３】
１）対数の目標スケジュール
目標スケジュールｔＴを選択する１つの方式は、クライアントバッファ時間を時間とともに対数的に増大させるものである。具体的には、ｔｄを再生の期限とすると、何らかの開始時間ｔｄ０より大きい各ｔｄについて、
【０１２４】
【数３１】
2006174419.tif 000033
【０１２５】
となる。
【０１２６】
式（１）により、ｔｄ＝ｔｄ０＋（τｄ−τｄ０）／ｖなので、これにより
【０１２７】
【数３２】
2006174419.tif 000034
【０１２８】
が得られ、したがって、フレーム０における（ｔｄ＝ｔｄ０の時）初期の勾配は、ｓ（０）＝（１−ｂ）／ｖになる。ｂ＝０．５に設定することは、初めｒｃ／ｒａ＝０．５／ｖになり、クライアントバッファを最初に実時間の２倍で増大させることを意味する。さらにａ＝０．１５に設定することは、ｖに関係なく、クライアントバッファ時間が１分後に７．６８秒になり、１０分後に１５．０４秒になり、１００分後に２２．６８秒になることを意味する。
【０１２９】
２）２つの部分からなる線形の目標スケジュール
目標スケジュールｔＴを選択する別の方式は、バッファ時間がメディア時間のａ秒に達するまで、クライアントバッファ時間をクライアント時間の１秒につきメディア時間のｂ秒のレートで直線的に増大させるものであり、メディア時間のａ秒に達するとバッファ時間は一定のままになる。具体的には、何らかの開始時間ｔｄ０より大きい各ｔｄについて、
【０１３０】
【数３３】
2006174419.tif 000035
【０１３１】
初期の勾配はこの場合もｓ（０）＝（１−ｂ）／ｖになる。ｂ＝０．５に設定することは、初めにｒｃ／ｒａ＝０．５／ｖになり、クライアントバッファを初めに実時間の２倍で増大させることを意味する。さらにａ＝１０に設定することは、ｖに関係なく、クライアントバッファ時間が、クライアント時間の２０秒後にメディア時間の１０秒に達することを意味する。
【０１３２】
図７（ａ）および図７（ｂ）に、上記の２つの目標スケジュールのグラフを示す。グラフから分かるように、１０秒のクライアントバッファ時間を、ジッタ、遅延、およびネットワークの変動に対して安全なレベルであると考えると、２つの部分からなる線形の目標スケジュールは、２０秒後にこの安全なレベルに達し、これは、対数の目標スケジュールよりはるかに速い。一方、２つの部分からなる線形目標スケジュールの勾配は、より長く低いまま推移し（したがって符号化ビットレートと品質が長時間低くなる）、さらに２０秒後にその勾配が０．５／ｖから１／ｖに変わる時に急な変化が生じる。その結果、符号化ビットレートは対数目標スケジュールほど滑らかには変化しないが、コントローラの設計で滑らかさが目標とされるために、スケジュール自体ほど急ではない。
【０１３３】
Ｂ．最適なコントローラ設計
式（１８）から、符号化ビットレートｒｃ（ｎ）に換算してバッファチューブの上限ｔｂ（ｎ）の展開を記述する、次の基本的な状態遷移式を思い出されたい。
【０１３４】
【数３４】
2006174419.tif 000036
【０１３５】
ここで、フレームレートｆと、平均到着レート
【０１３６】
【数３５】
2006174419.tif 000037
【０１３７】
が比較的一定であると仮定する。この仮定からの逸脱がｗ（ｎ）によって取り込まれる。
【０１３８】
符号化ビットレートを調整することによって上限をコントロールすることが望まれる。各フレームがクライアントに到着すると、フィードバックループがサーバにメッセージを送信して符号化ビットレートを調整することができる。ただし、フレームｎが完全にクライアントに到着する時までに、フレームｎ＋１がすでにサーバからストリーミングを開始していることに留意されたい。したがって、フレームｎ＋１の符号化ビットレートｒｃ（ｎ＋１）は、時間ｔａ（ｎ）までにはすでに決定されていなければならない。実際に、時間ｔａ（ｎ）には、フレームｎ＋２が、コントローラが符号化ビットレートを決定することができる最も早いフレームである。したがって、時間ｔａ（ｎ）に、コントローラのジョブは、ｒｃ（ｎ＋２）を選択することでなければならない。このフィードバックループの１フレーム分の遅延は、明示的に補償されなければならない。
【０１３９】
簡潔にするために、目標スケジュールが、フレームｎが到着する時間の前後に線形化される。線形化は、特定の時点におけるおよその目標スケジュールとしての元の目標スケジュールに接する線を使用することに等しい。したがって、
ｔＴ（ｎ＋１）−２ｔＴ（ｎ）＋ｔＴ（ｎ−１）＝０                （２７）
となる。
【０１４０】
制限なしで増大する上限の展開を直接制御するのではなく、安定性のために誤差空間の定式化が用いられる。誤差を次のように定義すると、
ｅ（ｎ）＝ｔｂ（ｎ）−ｔＴ（ｎ）                              （２８）
その結果
ｅ（ｎ＋１）−ｅ（ｎ）
＝（ｔｂ（ｎ＋１）−ｔＴ（ｎ＋１））−（ｔｂ（ｎ）−ｔＴ（ｎ））    （２９）
＝（ｔｂ（ｎ＋１）−ｔｂ（ｎ））−（ｔＴ（ｎ＋１）−ｔＴ（ｎ））    （３０）
【０１４１】
【数３６】
2006174419.tif 000038
【０１４２】
になり、そこから、
【０１４３】
【数３７】
2006174419.tif 000039
【０１４４】
となる。
【０１４５】
そして制御入力が次のように定義され、
【０１４６】
【数３８】
2006174419.tif 000040
【０１４７】
【数３９】
2006174419.tif 000041
【０１４８】
は、ｒｃ（ｎ＋１）の可能性としては量子化されたバージョンであり（セクションＩＶ−Ｄで定義する）、擾乱（ｄｉｓｔｕｒｂａｎｃｅ）が次のように定義される。
【０１４９】
【数４０】
2006174419.tif 000042
【０１５０】
そして、式（３３）を次のように書き換えることができる。
【０１５１】
【数４１】
2006174419.tif 000043
【０１５２】
したがって、誤差ベクトルを定義し、
【０１５３】
【数４２】
2006174419.tif 000044
【０１５４】
システムの誤差空間表現を次のように表すことができる。
【０１５５】
【数４３】
2006174419.tif 000045
【０１５６】
あるいは、適切な行列Φ、Γ、およびΓｄについて、ｅ（ｎ＋１）＝Φｅ（ｎ）＋Γｕ（ｎ）＋Γｄｄ（ｎ）になる。
【０１５７】
擾乱ｄ（ｎ）が純粋な白色雑音であると仮定し、完璧な状態測定（すなわち推定器を使用せずにｅ（ｎ）のすべての成分を測定することができる）を仮定すると、擾乱ｄ（ｎ）は、コントローラ設計に影響しない。そのため、
ｕ（ｎ）＝−Ｇｅ（ｎ）                                        （３９）
で表される線形コントローラを使用することができ、Ｇはフィードバックゲインである。フレームｎが完全に受信される時までにｅ（ｎ）のすべての要素をクライアントで得ることができ、したがってｕ（ｎ）が計算されることができる。そして、フレームｎ＋２の理想的な符号化ビットレートを
【０１５８】
【数４４】
2006174419.tif 000046
【０１５９】
と計算することができる。
【０１６０】
最適な線形コントローラを見つけることは、セクションＩＩ−Ｄで定義される二次コスト関数を最小にするフィードバックゲインＧ＊を見つけることに相当する。設計を続ける前に、任意のフレームレートｆについての最大階数（ｆｕｌｌ  ｒａｎｋ）を有するシステムの制御性行列Ｃ
【０１６１】
【数４５】
2006174419.tif 000047
【０１６２】
が初めに確認される。したがって、システムは、完全に制御可能となり、状態ｅ（ｎ）は、所望の値に規制されることができる。ここで、セクションＩＩ−Ｄで定義されたコスト関数が
【０１６３】
【数４６】
2006174419.tif 000048
【０１６４】
であり、Ｑ＝ＣＴＣ（Ｃ＝［１  ０  ０］）、Ｒ＝σであることを思い出されたい。そして、符号化ビットレートの変動を平滑化する間に目標スケジュールを追跡する元の制御問題（すなわちコスト関数Ｉを最小にする）が、誤差空間の標準的なレギュレータ問題に転換される。Ｎ→∞とすると、無限計画最適制御問題は、［１１］、セクション３．３の結果を適用して、最適なレギュレータを次の２ステップで得ることによって解決することができる。１）Ｓを得るために、離散代数Ｒｉｃｃａｔｉ式（ＤＡＲＥ）を解き、
Ｓ＝ΦＴ｛Ｓ−ＳΓ［ΓＴＳＴ＋Ｒ］−１ΓＳ｝Φ＋Ｑ              （４４）
２）最適なフィードバックゲインを計算する
Ｇ＊＝［ΓＴＳΓ＋Ｒ］−１ΓＴＳΦ                                （４５）
Ｑが非負の定値で、Ｒが正定値である時に、Ｓ（ひいてはＧ＊）の存在と一意性が保証される、これは、この場合容易に検証することができる。
【０１６５】
Ｃ．フレームレート
１つ前のセクションでは、フレームレートが一定であると仮定した。この仮定は、音声のないビデオなど、単一のメディアをストリーミングする際には妥当である。可変フレームレートのビデオは、通常、フレームを飛ばすことによって達成され、フレームを飛ばすことは、ｂ（ｎ）＝０に設定することによって対処されることができる。しかし、通常は、ビデオと音声はともにストリーミングされ、それらの併合された符号化スケジュールは、固定されたフレームレートを持たない場合がある。固定のフレームレートｆがある場合でも、例えばフィードバックレートを下げるために、ｆより低いレートでコントローラを操作することが望ましい場合がある。
【０１６６】
これらの問題に対応するために、実際には、仮想フレームレートの概念が用いられる。仮想フレームレートｆは次のように選択される。毎秒ｆ＝１フレーム（ｆｐｓ）であり、メディア時間が大きさ１／ｆの期間に区分され、各期間内に到着するすべてのフレーム（オーディオおよびビデオ）が、その復号および再生の期限をその期間の終わりとする仮想フレームとしてモデル化される。
【０１６７】
この手法にはいくつかの利点がある。第１に、ストリームの実際のフレームレートまたは複数のストリームに依存しない、汎用的なフィードバックゲインのオフライン設計が可能になる。第２に、クライアントからサーバへのフィードバックのレートを下げることができる。そして最後に、仮想フレームと仮想フレームの間隔は、通例、往復遅延時間（ＲＴＴ）より確実に長いので、誤差空間モデルにおける１フレーム分の遅延（１つ前のセクションで説明した）で十分にフィードバック遅延をモデル化することができる。そうでなければ、およそＲＴＴ／ｆの追加的な状態変数でフィードバック遅延をモデル化して、長さＲＴＴ／ｆのシフトレジスタを使用してネットワーク遅延を表すことが必要となる。
【０１６８】
この説明の残りの部分では、仮想フレームレートｆ＝１ｆｐｓが用いられ、これを単にフレームレートと称する。同様に、仮想フレームは、単にフレームと称する。
【０１６９】
このコントローラ設計の原理では、制御目標からのバッファチューブの上限の逸脱は、σ値を下げることによって縮小できることに気づかれよう。σ値を小さくすることは、コスト関数の逸脱の項に相対的に大きな制約が課せられることを示唆し、したがって上限が目標値のより近くをたどることを強制する。しかし、コスト関数の対応する項への重み付けが小さくなるので、これは符号化ビットレートの平滑さを犠牲にして行われる。σ＝５００では、バッファチューブの上限が制御目標からわずかしか逸脱していない時、符号化ビットレートに望ましくない変動が生じることが分かっている。一方、σの値を大きくすると、確実に平滑な符号化ビットレートが得られるが、バッファチューブの上限が制御目標から著しく逸脱することが許容されるので、クライアントバッファのアンダーフローを招く可能性がある。したがって、σの適切な選択は、このトレードオフを考慮しなければならない。本システムおよび方法のテストされた実施形態では、符号化ビットレートが上方に切り替わる時にはσ＝４０００が選択され、ビットレートが下方に切り替わるときにはσ＝２０００が選択された。後者の場合は、クライアントバッファのアンダーフローの可能性をさらに低減するために、わずかにより積極的な手法が許されることに留意されたい。
【０１７０】
ＩＶ．ストリーミングに伴う実際的問題
Ａ．高速のスタートアップ
これまでのセクションで述べたように、スタートアップまでの遅延は、コンテンツが最初にクライアントに到着し始める時間から、再生が開始する時間までの期間の長さである。この期間中に、コンテンツが受信機バッファに蓄積して、パケットジッタ、再送の遅延、ネットワーク帯域幅の変動、および瞬間的な符号化ビットレートの変動に対処する。スタートアップまでの遅延が長くなると、動的なネットワーク環境では連続した再生を維持できる可能性が増すことが予想される。一方、ユーザは、スタートアップまでの遅延ができるかぎり短いことを期待する。したがって、堅牢性を維持しながらスタートアップまでの遅延を短縮できる技術を研究することが望ましい。可能な手法の１つは、ストリーミングのスタートアップ時に通常のレートより速いレートでコンテンツを送信するものである。このバースト技術は、確かに少ない時間でバッファ時間を構築する。しかし、通常の初期帯域幅より高い帯域幅を要求する（利用できない場合もある）ことによって、ネットワークに余分な負荷をかける。
【０１７１】
本システムおよび方法は、適合型メディアの特性を利用する、代替の高速スタートアップ技術を用いる。これまでのセクションで述べたように、到着レートｒａ（必要な場合は再生速度ｖで割る）の半分に等しい初期符号化ビットレートｒｃを選択することにより、クライアントバッファ時間は、再生中に実時間の２倍で増大することができる。再生中にクライアントバッファを増大させるとバッファ時間がまだ短い間に再生が開始することができるので、スタートアップの遅延を小さくすることが可能になる。任意の短い間隔中に深刻な輻輳が発生する確率は低いので、バッファ時間が短い間に再生を開始することは、短い時間では特に危険ではない。しかし、長い時間間隔中に深刻な輻輳が発生する確率は高いので、バッファ時間は、長い時間にわたっては高いことが重要である。再生中にバッファ時間を増大させることができないと、バッファ時間が長時間にわたり連続した再生を保証するのに十分な長さになるまで、スタートアップを遅延させなければならなくなる。
【０１７２】
さらに、伝送レートが符号化ビットレートの２倍である場合、スタートアップの遅延は、リーキーバケツモデル［１０］の特性を利用することにより、さらに短縮することができる。セクションＩＩ−Ｂで詳しく述べたように、所与のビットストリームのスタートアップの遅延は、ストリームがレートＲで送信される場合
【０１７３】
【数４７】
2006174419.tif 000049
【０１７４】
になる。ストリームの符号化ビットレートでストリームを送信する場合、これは、通常
【０１７５】
【数４８】
2006174419.tif 000050
【０１７６】
に等しくなる。しかし、レートｒａ＞ｒｃ（ｒｃ＝０．５ｒａ／ｖ）でストリームを送信すると、スタートアップの遅延は、
【０１７７】
【数４９】
2006174419.tif 000051
【０１７８】
に低下する。したがって、スタートアップの遅延Ｄは、分子が小さくなることと、分母が大きくなることの両方により減少する。
【０１７９】
図８のグラフに、Ｒがｒｃからｒａに変化する際の初期デコーダバッファの充足度
【０１８０】
【数５０】
2006174419.tif 000052
【０１８１】
の低下を示す。詳細には、このグラフは、所与のビットストリームの符号化スケジュールと、両方ともその符号化スケジュールを含む、それぞれリークレートｒｃとｒａの２つのリーキーバケツに対応するチューブＩおよびチューブＩＩと表される上限と下限を示している。所与のストリームを含むリーキーバケツの最小の大きさＢｍｉｎ（Ｒ）は、リークレートＲで小さくなっていくので、チューブＩＩはチューブＩより小さい［１０］。同様に、初期のデコーダバッファの充足度Ｆｍｉｎ（Ｒ）は、Ｒで小さくなっていく［１０］。したがって、フレーム０の再生期限は、
【０１８２】
【数５１】
2006174419.tif 000053
【０１８３】
ではなく、クライアント時間
【０１８４】
【数５２】
2006174419.tif 000054
【０１８５】
に早くも開始することができる。そこから、再生の期限は、メディア時間の１秒につきクライアント時間の１／ｖ秒ずつ早くなる。
【０１８６】
Ｂ．コントローラの初期化
図８に示すように、目標スケジュールは、再生の期限と同じ時間に開始し、所定の関数に従って増大していく。コントローラは、目標スケジュールに合わせてチューブＩの上限を調整することを試みる。初め、チューブＩの上限は、目標スケジュールを上回っている（実際には、安全であることは分かっているが再生の期限を上回っている）。したがって、再生が開始するときに、コントローラは、符号化ビットレートを下げることにより差分を狭くすることを試みる。しかし、クライアントバッファを増大させるために現在の符号化ビットレートはすでに到着レートより低くなっているので、これは望ましくない。符号化ビットレートをそれ以上下げることは適当ではない。この影響を回避するために、チューブＩの上限が目標スケジュールを越えた時、すなわち図８の点Ｂで、コントローラが初期化される。点Ｂは、解析的に見つけることができるが、実際には、点Ｂを明示的に求める必要はない。コントローラは、チューブＩの上限が目標を上回るとすぐに初期化してよい。
【０１８７】
Ｃ．到着レートの指数的な平均化
（瞬間的な到着レートの代わりに）平均到着レートを用いることは、符号化ビットレートの変動を低減する助けとなる。このセクションでは、到着レートの新たな指数的な平均化アルゴリズムについて詳しく述べる。
【０１８８】
【数５３】
2006174419.tif 000055
【０１８９】
とｒ（ｋ）を、それぞれパケットｋが受信される時の平均到着レートと瞬時到着レートとする。制御動作とは異なり、レートの平均化動作は、フレームが到着するたびではなく、パケットが到着するたびに行ってよいことに留意されたい。したがって、フレームインデックスｎではなく、別個のパケットインデックスｋを使用する。広く採用されている指数的に重み付けされる移動平均（ＥＷＭＡ）
【０１９０】
【数５４】
2006174419.tif 000056
【０１９１】
を一定のβ（ｋ）＝βで用いる代わりに、指数平均化は、より綿密に行われる。このアルゴリズムでは、係数β（ｋ）は一定でなく、パケットの到着間の差分に応じて変化する。この新しいアルゴリズムには、一定のβ（ｋ）を用いるＥＷＭＡアルゴリズムを上回るいくつかの利点がある。第１に、最後のパケット以降の差分が無限に向かうのに従って、平均到着レートの推定値
【０１９２】
【数５５】
2006174419.tif 000057
【０１９３】
が
【０１９４】
【数５６】
2006174419.tif 000058
【０１９５】
以下に制限されるのではなく、自然にゼロに向かう。第２に、最後のパケット以降の差分がゼロになるのに従って、平均到着レート
【０１９６】
【数５７】
2006174419.tif 000059
【０１９７】
の推定値が無限にならない。パケットはしばしばバーストで到着し、極めて高い瞬時到着レートを発生させるので、これは特に重要である。そして最後に、平均到着レート
【０１９８】
【数５８】
2006174419.tif 000060
【０１９９】
の推定値が、無限の過去を表すかのように、初期条件を過度に重み付けしない。これは、推定の早い段階で特に重要である。
【０２００】
式（１１）のように、パケットｋの後の瞬時到着レートは、
【０２０１】
【数５９】
2006174419.tif 000061
【０２０２】
と定義され、ｂ（ｋ）は、パケットｋの大きさを表し、ｔａ（ｋ）は、パケットｋの到着時間を表す。図９のグラフに示すように、
すべてのｔ∈（ｔａ（ｋ−１），ｔａ（ｋ））についてｒａ（ｔ）＝ｒａ（ｋ）
（４８）
によって、離散時間関数ｒａ（ｋ）が、区分的な一定の連続した時間関数ｒａ（ｔ）に拡張される。そして、関数ｒａ（ｔ）が何らかの時間定数１／αについての指数インパルス応答αｅ−ａｔでフィルタリングされ、ｔ≧０である。
【０２０３】
【数６０】
2006174419.tif 000062
【０２０４】
（この箇所およびこの下位セクションの残りでは、到着時間ｔａ（ｋ）の下付き文字を記載しない。）
【０２０５】
【数６１】
2006174419.tif 000063
【０２０６】
であり、分母の積分は、１−ｅ−ａ（ｔ（ｋ）−ｔ（０））と表せることに留意されたい。次いで、分子の積分の範囲が、（ｔ（０），ｔ（ｋ−１））と（ｔ（ｋ−１），ｔ（ｋ））に分けられて、
【０２０７】
【数６２】
2006174419.tif 000064
【０２０８】
とｒａ（ｋ）から見た
【０２０９】
【数６３】
2006174419.tif 000065
【０２１０】
の再帰的表現を得る。
【０２１１】
【数６４】
2006174419.tif 000066
【０２１２】
【数６５】
2006174419.tif 000067
【０２１３】
ここで
【０２１４】
【数６６】
2006174419.tif 000068
【０２１５】
β（ｋ）は、ｋが無限に向かうにつれて数値的に安定することに留意されたい。ただし、差分δ＝ｔ（ｋ）−ｔ（ｋ−１）がゼロになると、１−β（ｋ）はゼロになり、一方ｒａ（ｋ）は無限になる。しかし、それらの積は、よい振る舞いを見せる。実際、
【０２１６】
【数６７】
2006174419.tif 000069
【０２１７】
の規則を使用すると、δ→０であるため、
【０２１８】
【数６８】
2006174419.tif 000070
【０２１９】
となる。したがって、式（５４）は、ｔ（ｋ）＝ｔ（ｋ−１）である場合の更新規則となる。
【０２２０】
Ｄ．符号化ビットレートを前提としてストリームを選択する
クライアントが符号化ビットレートｒｃ（ｎ）を要求すると、サーバは、ｒｃ（ｎ）にほぼ等しい符号化ビットレート
【０２２１】
【数６９】
2006174419.tif 000071
【０２２２】
を有するストリーム（またはスケーラブルなストリームのサブストリーム）を選択することによって応じる。
【０２２３】
【数７０】
2006174419.tif 000072
【０２２４】
がｒｃ（ｎ）と異なってよい理由はいくつかある。最初の理由は、細粒度のスケーラブルな符号化を使用する場合でも、メディアファイルには有限数のストリーム（またはサブストリーム）しかないためである。そのため、正確にｒｃ（ｎ）に等しい平均符号化ビットレートを有するストリームがメディアファイルにない場合がある。第２の理由は、正確にｒｃ（ｎ）に等しい平均符号化ビットレートのストリームがメディアファイルにある場合でも、クライアントバッファのアンダーフローを生じさせる危険性なしに、そのストリームへの切り替えを許すには、そのストリームのバッファチューブが大き過ぎる可能性がある。実際、ストリームが切り替わる際には、一般に、正か負いずれかの、上限の不連続がある。上限の正の変化を図１０のグラフに示し、この変化が大きいと、直ちに、または最終的にクライアントバッファをアンダーフローさせる可能性がある。
【０２２５】
したがって、サーバは、クライアントから供給される何らかの量Δｍａｘｇ（ｎ−１）を越えずに上限を上方に推移させるストリームを選ばなければならない。クライアントは、クライアント時間ｔａ（ｎ−２）のすぐ後に（フレームｎ−１がすでにストリーミングを開始した後に）、そのフィードバックでｒｃ（ｎ）とともにΔｍａｘｇ（ｎ−１）をサーバに供給する。フィードバックを受け取ると、サーバは、
【０２２６】
【数７１】
2006174419.tif 000073
【０２２７】
となるように可能な限り高い符号化ビットレート
【０２２８】
【数７２】
2006174419.tif 000074
【０２２９】
を有するストリームを選択し、
【０２３０】
【数７３】
2006174419.tif 000075
【０２３１】
の場合（すなわちそれが上方へのレートの切り替えである場合）に、ｇｎｅｗ（ｎ−１）−ｇｏｌｄ（ｎ−１）≦Δｍａｘｇ（ｎ−１）１になり、ｇｎｅｗ（ｎ−１）とｇｏｌｄ（ｎ−１）は、図１０に示される。Δｍａｘｇ（ｎ−１）によって与えられる制約は、それが下方へのレートの切り替えである場合は適用されない。
【０２３２】
クライアントは、新しい符号化ビットレートが実行された場合に、上限が時間ｔａ（ｎ−１）にとる値（その予測）を制限するΔｍａｘｇ（ｎ−１）を選択する。すなわち、
【０２３３】
【数７４】
2006174419.tif 000076
【０２３４】
となる。
【０２３５】
すなわち、クライアントは、目標ｔＴ（ｎ−１）から再生の期限ｔｄ（ｎ−１）への隔たりの何分の１かであるｐより大きくならないように
【０２３６】
【数７５】
2006174419.tif 000077
【０２３７】
を制限するΔｍａｘｇ（ｎ−１）を選択する。本システムおよび方法のテストされた実施形態では、ｐ＝１／３が選択された。
【０２３８】
代替的な実施形態では、サーバがサポートする符号化ビットレートについての情報がクライアントに事前に提供されることができ、クライアントが、前述の分析を行う役割を担うことができることに留意されたい。その場合、クライアントは、サーバでサポートされる符号化ビットレートを要求するのみで、要求とともにΔｍａｘｇ（ｎ−１）をサーバに提供する必要はない。
【０２３９】
Ｅ．制御目標の調整
新しい平均符号化ビットレート
【０２４０】
【数７６】
2006174419.tif 000078
【０２４１】
のフレームが時間ｔａ（ｎ）にクライアントに到着した時、上限の変化がある。この変化は、およそ数秒であり、したがって無視できるものではなく、コントローラを混乱させる可能性がある。例えば、変化が上方への場合、コントローラは、直ちに符号化ビットレートｒｃ（ｎ＋２）を下げることを試みる。一方、変化が下方への変化である場合は、コントローラは、直ちに符号化ビットレートｒｃ（ｎ＋２）を上げることを試みる。どちらの方法も恐らくは適切ではない。すなわち、その意図は、到着レートに動きがない限りは
【０２４２】
【数７７】
2006174419.tif 000079
【０２４３】
が、維持されるというものである。解決法の１つは、
【０２４４】
【数７８】
2006174419.tif 000080
【０２４５】
に等しい制御目標スケジュールの同時の変化を導入するものであり、Δｇ（ｎ−１）＝ｇｎｅｗ（ｎ−１）−ｇｏｌｄ（ｎ−１）が、図１０に示すように、サーバで計算されるフレームｎ−１における上限の実際の変化（ビット単位）となる。サーバは、この値をフレームｎとともにクライアントに送信することができる。ストリームの変化がない場合、この値は、単にゼロになる。
【０２４６】
符号化ビットレートが変わるたびに制御目標スケジュールが調整されると、制御目標スケジュールは、もはや意図された目標スケジュールに従わなくなる。意図される目標スケジュール（または単に目標スケジュール）と区別するために、調整された目標スケジュールを制御目標スケジュールと称する。
【０２４７】
言うまでもなく、制御目標スケジュールは、意図される目標スケジュールに近づいて行く傾向を持つべきである。根本となる考えは、意図される目標スケジュールより高い時には制御目標スケジュールの勾配を下げ、意図される目標スケジュールより低い時には勾配を上げることである。
【０２４８】
対数の目標スケジュール
【０２４９】
【数７９】
2006174419.tif 000081
【０２５０】
（ｔｄ＝ｔｄ０＋（τｄ−τｄ０）／ｖ））の場合、式（２４）によると、メディア時間τｄにおける勾配は
【０２５１】
【数８０】
2006174419.tif 000082
【０２５２】
となる。再生期限と目標スケジュールとの距離をｄと定義する、すなわち
【０２５３】
【数８１】
2006174419.tif 000083
【０２５４】
とした場合、勾配は、ｄの関数として表すことができる。
【０２５５】
【数８２】
2006174419.tif 000084
【０２５６】
したがって、ｄが再生の期限と制御目標との距離である場合には、制御目標の勾配は、式（５９）でｓに設定される。具体的には、
【０２５７】
【数８３】
2006174419.tif 000085
【０２５８】
が変化後のフレームｎにおける制御目標である場合、
【０２５９】
【数８４】
2006174419.tif 000086
【０２６０】
は
【０２６１】
【数８５】
2006174419.tif 000087
【０２６２】
になるように再設定される。そして、ｔＴ（ｎ）とｔＴ（ｎ−１）に代えて
【０２６３】
【数８６】
2006174419.tif 000088
【０２６４】
と
【０２６５】
【数８７】
2006174419.tif 000089
【０２６６】
を使用して式（３７）で誤差ベクトルｅ（ｎ）を計算する。次いで、得られた誤差ベクトルを使用して、式（４０）で理想的な符号化ビットレートを計算する。
【０２６７】
２部分からなる線形目標スケジュールの場合、勾配は、制御目標スケジュールが目標スケジュールに戻るためにかかると予想される所定の時間を使用して容易に計算することができる。そして、距離ｄとその時間から、制御目標スケジュールの勾配を計算することができる。本システムおよび方法のテストされた実施形態では、時間は５０秒に設定された。
【０２６８】
Ｖ．実施の詳細
このセクションでは、送信者側と受信者側双方の実施の詳細について述べる。
【０２６９】
Ａ．仮想ストリームの生成
本システムおよび方法のテストされた実施形態では、細粒度のスケーラブル（ＦＧＳ）ストリームは、データユニットのセットからなり、各データユニットは、そのデータユニットがクライアントに受信された場合の歪みのビット単位の低減を表すラグランジュ乗数λでタグ付けされる。データユニットのλが閾値を上回る場合、そのデータユニットは、その閾値に対応する仮想ストリームに含められる。各閾値は、総ビット数と、したがって仮想ストリームの平均符号化ビットレートに対応する。テストされた実施形態では、Ｎ＝５０の仮想ストリームが生成される。結果として得られるストリームが、下限と上限の間の対数領域で均一の間隔を空けた符号化ビットレートを有するように、各ストリームの閾値が選択される。
【０２７０】
ストリーミング中に、サーバがメディアファイルからデータユニットを読み出す時、サーバは、ラグランジュ乗数λがそのストリームの閾値を上回る場合は、現在送信されている仮想ストリームにそのデータユニットを含める。
【０２７１】
Ｂ．サーバにおけるリーキーバケツの計算
仮想ストリームごとに、リーキーバケツのパラメータ
【０２７２】
【数８８】
2006174419.tif 000090
【０２７３】
がＲ＝ＲａｖｇおよびＲ＝Ｒｍａｘについてオフラインであらかじめ計算され、Ｒａｖｇ＝ｒｃは、ストリームの平均符号化ビットレートであり、Ｒｍａｘ＝２ｒｃである。そのリーキーバケツパラメータは、プリアンブルでクライアントに送信される。
【０２７４】
また、ストリーミング中に、サーバは、各ストリームについてオンラインのリーキーバケツのシミュレーションを行う。具体的には、サーバがメディアファイルからデータユニットを読み出す時には、そのデータユニットのラグランジュ乗数と各ストリームの閾値のリストを用いて、そのデータユニットが属する仮想ストリームを判定する。そして、送信者は、判定されたストリームについて、式（２）および（３）を使用して、平均符号化ビットレートＲａｖｇに等しいリークレートを有するリーキーバケツの状態を更新する。メディアファイルからフレームのデータユニットがすべて読み出されると、送信者は、各仮想ストリームのｇ（ｎ）＝Ｂｍｉｎ（Ｒａｖｇ）−Ｂｅ（ｎ）を計算する。ストリームの切り替え
【０２７５】
【数８９】
2006174419.tif 000091
【０２７６】
があると、下記のように、新しいストリームの差分ｇｎｅｗ（ｎ）が、Δｇ（ｎ−１）＝ｇｎｅｗ（ｎ−１）−ｇｏｌｄ（ｎ−１）とともにクライアントに送信される。リーキーバケツの状態を更新するコストはかなり低いことは容易に理解されよう。しかし、それらの値を事前に計算し、各データユニットとともにメディアファイルに格納することも可能である。
【０２７７】
Ｃ．初期符号化ビットレートの選択
ストリーミングセッションのスタートアップ時に、送信者は、初期符号化ビットレート（通例は帯域幅の２分の１）を選択できるように、利用可能なネットワーク帯域幅の知識を有する必要がある。帯域幅の推定は、パケットの対［１２］、経路のチャープ（ｃｈｉｒｐ）［３］等の手法を使用する事前対応型の測定か、または履歴値に基づく事後対応型の近似から引き出すことができる。初期の帯域幅推定の正確な形は、この研究の範囲外である。
【０２７８】
Ｄ．符号化ビットレートの切り替え
クライアントからのレート制御のフィードバックは、フィードバックが生成されたフレーム番号（例えば１つ前のセクションでのｎ−２）と、許容される最大の上限のシフト（ビット単位）（例えば１つ前のセクションのΔｍａｘｇ（ｎ−１））を含んでいる。送信者が適切な符号化ビットレートを見つけ、フレームｎで切り替えを行う場合、送信者は、新しい符号化ビットレート
【０２７９】
【数９０】
2006174419.tif 000092
【０２８０】
、上限との現在の差分ｇｎｅｗ（ｎ）、および、シフトΔｇ（ｎ−１）＝ｇｎｅｗ（ｎ−１）−ｇｏｌｄ（ｎ−１）、の３つの値をフレームとともにクライアントに送信する。この情報で、クライアントは、その制御目標スケジュールとその上限を正しく調整することができる。符号化ビットレートの切り替えは、常に、新しいフレームの始まりで行われ、決してフレームの中では行われないことに留意されたい。
【０２８１】
Ｅ．クライアントにおける最適なレート制御
新しい符号化ビットレートが開始する時には、クライアントは、新しいフレームとともに値ｇ（ｎ）を受け取る。そして、符号化ビットレート
【０２８２】
【数９１】
2006174419.tif 000093
【０２８３】
とフレームのサイズｂ（ｎ）に基づいて、続くフレームのｇ（ｎ）の値をクライアント自身で推測することができる。クライアントは、到着フレーム時間ｔａ（ｎ）を記録し、バッファチューブの上限ｔｂ（ｎ）を計算し、偏差ｅ（ｎ）を計算する。符号化ビットレートの切り替えがある場合には、クライアントは、バッファチューブのシフトも計算し、それに応じて制御目標スケジュールを調整する。ｅ（ｎ）が最適レートコントローラに与えられ、コントローラは、要求される新しい符号化ビットレートを出力する。フィードバックの機会があるたびに、最新の新しい符号化ビットレートが送信者に返され、フィードバックは、規則的な間隔で、または要求に応じて生成されることができる。
【０２８４】
Ｆ．例示的な方法
次いで、前述のシステムを実施する例示的な方法を本発明の一実施形態に適用できるものとして提供する。
【０２８５】
図１１Ａ〜図１１Ｃを参照すると、サーバは初めに、サポートされる符号化ビットレートに対応するデータストリームがサーバからストリーミングされた場合に存在することになるエンコーダバッファの初期状態を定義するパラメータのセットを、サポートされる各符号化ビットレートについて計算する（方法動作１１００）。これらのパラメータは、データストリームに関連付けられた符号化ビットレート、データストリームのその符号化ビットレートに用いられるエンコーダバッファのサイズ、および、データストリームの符号化ビットレートに示される初期のエンコーダバッファの充足度を示す値を含み、ストリーミングメディアデータのプリアンブルでクライアントに提供される（方法動作１１０２）。サーバは次いで、スタートアップ期間中に、規定された初期符号化ビットレートでメディアデータをクライアントにストリーミングする（方法動作１１０４）。データがストリーミングされるのと同時に、サーバは、サーバによってサポートされる各符号化ビットレートに生成される各フレームの上限との差分を計算する（方法動作１１０６）。初めに、クライアントは、エンコーダバッファのパラメータを用いて、フレーム単位で、後続のフレームの新しい最適な符号化ビットレートを求める（方法動作１１０８）。また、クライアントは、その後続のフレームの直前にサーバによって生成されるフレームの上述した許容される最大の差分値、すなわち最大シフト値を計算する（方法動作１１１０）。クライアントはまた、アンダーフロー条件が初期符号化ビットレートで生じないことを保証するのに必要な最小量のデータがクライアントのデコーダバッファに得られると直ちに、受信したフレームの再生を開始し、その後受信される各フレームの再生を続ける（方法動作１１１２）。また、上述のスタートアップ期間が終了すると、クライアントは、求められた最適な符号化レートに対応する新しい符号化ビットレートで、当該後続のフレームから開始するストリーミングメディアデータを供給するように要求し、その要求とともに最大シフト値を提供する（方法動作１１１４）。
【０２８６】
サーバは、クライアントによって要求される最適な符号化ビットレートに等しい、サポートされる符号化ビットレート、あるいは等しいレートがない場合は、最適ビットレートに最も近いより低いレートを見つける（方法動作１１１６）。次いで、見つかったサポートされる符号化ビットレートが、クライアントの要求で指定されるフレームの直前に生成されたフレームに関連付けられた符号化ビットレートより低いか、高いかがサーバによって判定される（方法動作１１１８）。低い場合、サーバは、クライアント要求で指定されるフレームの直前に生成されたフレームの上述のシフト値を計算し（方法動作１１２０）、クライアントから指定されたフレームで始まるすべての後続フレームを、見つかったサポートされるレートで生成し、そのフレームを、計算された上限の差分とシフト値、および新しい符号化ビットレートの指示とともにクライアントにストリーミングする（方法動作１１２２）。一方、見つかったサポートされる符号化ビットレートの方が高い場合、サーバは、クライアント要求で指定されるフレームの直前に生成されたフレームのシフト値を計算し（方法動作１１２４）、そのシフト値が、クライアント要求で提供される最大のシフト値以下であるかどうかを判定する（方法動作１１２６）。シフト値が最大シフト値以下である場合、サーバは、クライアントから指定されたフレームで開始するすべての後続フレームを、見つかったサポートされる符号化ビットレートで生成し、そのフレームを、計算された上限の差分とシフト値、および新しい符号化ビットレートの指示とともにクライアントにストリーミングする（方法動作１１２２）。しかし、シフト値が最大シフト値より大きい場合は、サポートされるレートの中で次に低い符号化ビットレートが見つけられ（方法動作１１２８）、方法動作１１１８〜１１２８が繰り返される。
【０２８７】
クライアントは、新しい符号化ビットレートで受信したばかりの最初のフレームに関連付けられた、現在スケジュールされている目標到着時間を、提供されたシフト値だけずらし、現在スケジュールされている後続フレームの目標到着時間が、ある時間をかけて、それら後続フレームの１つ前の目標到着時間にまとめて近づいていき、最終的には一致するように、目標到着時間をシフトする（方法動作１１３０）。次いで、クライアントは、サーバから提供されたエンコーダバッファパラメータと上限差分の値を用いて、後続フレームの新しい最適な符号化ビットレートを求め、その後続フレームの直前にサーバで生成されたフレームの最大シフト値を計算する（方法動作１１３２）。クライアントは、クライアントによって指定されるその後続フレームで開始する、求められた最適符号化レートに対応する新しい符号化ビットレートでストリーミングメディアデータを供給するように要求し、計算された最大シフト値を含める（方法動作１１３４）。そして、ストリーミングメディアデータの送信の継続時間にわたって、方法動作１１１６から１１３４が繰り返される。
【０２８８】
ＶＩ．複数ビットレートのストリーミング
複数ビットレート（ＭＢＲ）ストリーミングは、商業的なストリーミングメディアシステムで広く使用されるネットワーク適合技術である。ＭＢＲストリーミングでは、スケーラブルなストリーミングと異なり、コンテンツは、異なる符号化ビットレートでいくつかの（通例は５〜７つ）の独立したストリームに符号化される。多くの場合、各ストリームは、一般的なタイプのネットワーク接続（ダイヤルアップ、ＤＳＬ、ケーブルなど）のために最適化される。ＭＢＲストリーミングセッション中に、途切れのない再生の条件下で可能な最大限の品質を実現することを目標として、利用可能なネットワーク帯域幅に基づいて、適正な符号化ビットレートが動的に選択される。ＭＢＲストリーミングがスケーラブルストリーミングに似ていることは容易に理解される。実際、ＭＢＲストリーミングは、利用できる符号化ビットレートの数が限られた、特殊な事例のスケーラブルストリーミングと見なすことができる。したがって、前述の最適な制御手法をこの事例に適用することができる。
【０２８９】
しかし、ＭＢＲストリーミングを複雑にするいくつかの相違点があり、これは慎重に対処する必要がある。第１に、すぐ上で述べたように、ＭＢＲストリーミングでは、制限された数の符号化ビットレートしか利用することができない。この要求される符号化ビットレートの粗量子化は、閉ループシステムに著しい非線形性を招く。実際、利用可能な符号化ビットレート間のギャップが大きいと、振動（ｏｓｃｉｌｌａｔｉｏｎ）を招く。例えば、隣接する２つの符号化ビットレートが一定の到着レートをまたいでいる場合、コントローラは、クライアントバッファを目標レベルに維持するように試みて、２つの符号化ビットレートの間で振動する。
【０２９０】
第２に、ＭＢＲストリーミングでは、符号化ビットレートは、任意の時に切り替えることができない。実際、サーバが新しいストリームに切り替えるには、その新しいストリーム中の次のクリーンポイント（Ｉフレームなど）を待たなければならない場合があり、そのポイントは５秒後あるいは１０秒後である場合がある。したがって、新しい符号化ビットレートに切り替わる前に、古い符号化ビットレートがしばらく継続する可能性がある。コントローラの観点から見ると、この長く、不規則な余分な遅延は、閉ループシステムを不安定にする傾向がある。
【０２９１】
第３、そして最後に、ＭＢＲストリーミングでは、サーバの性能問題が重要となる。ＭＲＢストリーミングを用いる商業グレードのストリーミングメディアシステムがＭＲＢストリーミングを用いる理由は、スケーラブルなストリーミングに比べて、サーバに課される計算負荷が最小であるためである。したがって、ＭＲＢストリーミングでは、ほぼすべての計算と状態の維持をクライアント側に管理することが重要である。詳細には、サーバは、各ストリームのリーキーバケツ情報を更新することができない。代わりに、クライアントがその情報を推定し、保守するための何らかの機構を使用しなければならない。
【０２９２】
Ａ．控えめな（ｃｏｎｓｅｒｖａｔｉｖｅ）上方への切り替え
このサブセクションでは、制御システムの安定化を助け、安定状態の振動を少なくとも１分間に減らす技術を説明する。この技術では、迅速な下方への切り替えが許される。実際、σの値は、２０００から５００に下げられ、迅速な切り替え応答を優先して、符号化ビットレートの反応性と滑らかさのバランスを変える。これに対して、控えめな上方への切り替えのみが許される。控えめな上方への切り替えは、符号化ビットレートの見せかけの変化が生じず、符号化ビットレートの振動が低い周波数になることを保証する。詳細には、控えめな上方への切り替えでは、隣接しているが広い間隔が空いた、到着レートを超えるビットレートと、到着レートを下回るビットレートの２つのＭＢＲ符号化ビットレート間の振動を低減する。
【０２９３】
一実施形態では、控えめな上方への切り替えは、符号化ビットレートを到着レート以下に制限する控えめな制限を確立する。しかし、別の実施形態では、控えめな上方への切り替えの背後にある方法は、符号化ビットレートを、到着レートを超えてどれだけ高く上げられるかについての控えめな制限を確立することである。現在の符号化ビットレートが到着レートより低く、クライアントバッファ時間がその目標レベルを超えて増大し始める場合、符号化ビットレートは、新しい符号化ビットレートが控えめな制限より低い場合のみ、到着レートより高い新しい符号化ビットレートに切り替えることができる。クライアントバッファ時間が目標レベルで開始する時、控えめな制限値は、到着レートに等しくなる。しかし、クライアントバッファ時間が増すと、控えめな制限値も増す。したがって、現在の符号化ビットレートが到着レートより低く、次に高い符号化ビットレートが到着レートより高い場合には、クライアントバッファ時間が十分に増して控えめな制限値が次に高い符号化ビットレートを上回った時に初めて、次に高い符号化ビットレートに切り替えることが可能になる。符号化ビットレートがより高い符号化ビットレートに切り替えられると、符号化ビットレートが到着レートより高くなるので、クライアントバッファは、中身を排出し始める。最終的に、バッファが排出して再びその目標レベルを下回ると、コントローラは、符号化ビットレートを、到着レートより低い符号化ビットレートに迅速に切り替える。
【０２９４】
現在のクライアントバッファ時間に基づき、控えめな制限値は、符号化ビットレートがその値の新しい符号化ビットレートに切り替えられた場合に、クライアントバッファが中身を排出して目標レベルに戻るのに少なくともクライアント時間のΔｔ秒を要するような値に設定される。したがって、この機構は、変動の持続時間が少なくともΔｔ秒になることを保証する。本システムおよび方法のテストされた実施形態では、Δｔは６０秒に設定される。
【０２９５】
図１２に、控えめな制限値の計算法を示す。符号化ビットレートが
【０２９６】
【数９２】
2006174419.tif 000094
【０２９７】
から
【０２９８】
【数９３】
2006174419.tif 000095
【０２９９】
に切り替えられる瞬間のクライアントバッファ時間（メディア時間）をΔτ１とする。したがって、Δτ１は、新しい符号化ビットレートのコンテンツが消費され始める前に、古い符号化ビットレート
【０３００】
【数９４】
2006174419.tif 000096
【０３０１】
で消費される、コンテンツの秒数になる。（簡潔にするために、切り替え時にクライアントバッファにあるすべてのコンテンツはレート
【０３０２】
【数９５】
2006174419.tif 000097
【０３０３】
で符号化されていると仮定する。）クライアントバッファ時間が、目標レベルΔτＴより大きい何らかのレベルΔτ３（メディア時間）に低下する前に、新しい符号化ビットレート
【０３０４】
【数９６】
2006174419.tif 000098
【０３０５】
で消費される、コンテンツの秒数をΔτ２とする。この段階の持続時間は、切り替え以降の合計時間が正確にΔｔ＝（Δτ１＋Δτ２）／ｖ秒（クライアント時間）になるように決定される。ここで、この時間内に到着するビット数は、
【０３０６】
【数９７】
2006174419.tif 000099
【０３０７】
、あるいは
【０３０８】
【数９８】
2006174419.tif 000100
【０３０９】
になり、ここでΔｔＴは、クライアント時間での目標バッファ時間である。パラメータΔｔは、望む振る舞いをもたらすように調整されることができる。Δｔが大きいことは上方への切り替えがより控えめになることを意味し、一方、Δｔが小さいと、上方への切り替えがより迅速になることを意味する。テストされた実施形態では、Δｔは６０秒に設定され、一方目標ΔｔＴは、通例、約１０秒である。
【０３１０】
Ｂ．バッファチューブの上限の推定
セクションＶ−Ｄで、サーバは、符号化ビットレートが変化するたびにそのレートのスタートアップ時に３つの値をクライアントに送信すると述べた。３つの値は、新しい符号化ビットレート
【０３１１】
【数９９】
2006174419.tif 000101
【０３１２】
、現在の上限との差分ｇｎｅｗ（ｎ）、および制御目標のシフトΔｇ（ｎ−１）＝ｇｎｅｗ（ｎ−１）−ｇｏｌｄ（ｎ−１）である。サーバは、各符号化ビットレートにリーキーバケツのシミュレータを実行することにより後の２つの値を計算する。クライアントは、新しい符号化ビットレートに独自のリーキーバケツシミュレータを実行することにより、新しい符号化ビットレートのｇ（ｎ）を更新し続ける。すなわち、初期条件Ｆｅ（ｎ）＝Ｂ−ｂ（ｎ）―ｇｎｅｗ（ｎ）から開始し、後続の各フレームにつき、クライアントは、
Ｂｅ（ｎ）＝Ｆｅ（ｎ）＋ｂ（ｎ）                                    （６１）
【０３１３】
【数１００】
2006174419.tif 000102
【０３１４】
を計算し、
【０３１５】
【数１０１】
2006174419.tif 000103
【０３１６】
が、式（２）、（３）、および（４）のように瞬間的なフレームレートとなる。これから、クライアントは、各フレームについて
ｇ（ｎ）＝Ｂ−Ｂｅ（ｎ）                                      （６４）
を計算することができる。
【０３１７】
しかし、サーバがリーキーバケツをシミュレートする機能を持たず、ｇｎｅｗ（ｎ）をクライアントに送ることができない場合、クライアントは、この情報を自身で推定しなければならない。その場合は、クライアントが
【０３１８】
【数１０２】
2006174419.tif 000104
【０３１９】
のような上限としてｇｎｅｗ（ｎ）を推定することが推奨される。そして、初期条件
【０３２０】
【数１０３】
2006174419.tif 000105
【０３２１】
（この場合は０に等しい）から開始して、続くフレームごとに、クライアントは、
【０３２２】
【数１０４】
2006174419.tif 000106
【０３２３】
ならびに
【０３２４】
【数１０５】
2006174419.tif 000107
【０３２５】
を計算する。
【０３２６】
演繹法により、
【０３２７】
【数１０６】
2006174419.tif 000108
【０３２８】
、
【０３２９】
【数１０７】
2006174419.tif 000109
【０３３０】
、かつ
【０３３１】
【数１０８】
2006174419.tif 000110
【０３３２】
になることが容易に理解できる。さらに、これらの制限はそれぞれ、δ（ｎ）＞０、すなわちＦｅ（ｎ＋１）が式（６６）で０にされると、
【０３３３】
【数１０９】
2006174419.tif 000111
【０３３４】
だけ、より厳しくなる。実際に、十分な時間を与えられれば、これらの制限は、最終的には厳しいものになることができる。
【０３３５】
制限がδ（ｎ）＞０だけ厳しくなると、制御目標は、
【０３３６】
【数１１０】
2006174419.tif 000112
【０３３７】
だけシフトされなければならず、Δｇ（ｎ）＝−δ（ｎ）であることに留意されたい。さらに、ｎが新しい符号化ビットレートの最初のフレームである時には、制御目標は、
【０３３８】
【数１１１】
2006174419.tif 000113
【０３３９】
だけシフトされるべきであり、
【０３４０】
【数１１２】
2006174419.tif 000114
【０３４１】
である。ここで、余分なもう一ステップについて、すなわちｎが新しい符号化ビットレートの最初のフレームである場合について、式（６５）、（６６）、および（６７）を実行することにより
【０３４２】
【数１１３】
2006174419.tif 000115
【０３４３】
を求めることができる。
【０３４４】
【数１１４】
2006174419.tif 000116
【０３４５】
【数１１５】
2006174419.tif 000117
【０３４６】
であれば、式（６８）で計算されて
【０３４７】
【数１１６】
2006174419.tif 000118
【０３４８】
となることは容易に理解される。
【０３４９】
ＶＩＩ．送信者主導型のストリーミング
上記の論述では、優勢な条件に合わせてストリームまたはそのビットレートを適合する制御プロセスがクライアント内に置かれると想定した。クライアント（すなわち受信者）がそれらの決定を行い、サーバ（すなわち送信者）に通知するので、これは、受信者主導型のストリーミングと呼ばれる。しかし、制御プロセスが送信側で機能する送信者主導型のストリーミングも可能であることは、明らかであろう。例えば、ストリーミングメディアデータの送信にＴＣＰを使用すると、制御プロセスがクライアントで動作して各フレームの到着時間を測定し、到着レートを推定する代わりに、制御プロセスがサーバで動作して、各フレームの伝送時間を測定し、伝送レートを推定することができる。ＴＣＰを使用すると、フレームの伝送時間は、実質的に到着時間と同じになり、同様に、伝送レートは、実質的に到着レートと同じになる。したがって、それらを相互に代えて使用することができる。一般に、パケットの伝送時間または到着時間は、タイムスタンプと呼ばれることがある。送信者主導型のストリーミングでは、サーバは、サーバがすでに送信した内容を把握し、それら送信されたフレームの再生時間を把握することにより、クライアントバッファの状態を推測することができる。送信者主導型のストリーミングは、クライアントとサーバの間で制御情報を通信するオーバーヘッドを減らすが、サーバへの計算負荷が増す。状況によっては、これは、望ましいトレードオフとなる場合もある。当業者は、制御アルゴリズムがクライアントではなくサーバあるいは別の場所にある事例に合わせて、ここに記載されるプロトコルに適当に変更を加えることが可能であることを認識されよう。
【０３５０】
ＶＩＩＩ．参考文献
【０３５１】
【表１】
2006174419.tif 000119
【０３５２】
【表２】
2006174419.tif 000120
【０３５３】
【表３】
2006174419.tif 000121
【図面の簡単な説明】
【０３５４】
【図１】本発明を実施する例示的システムを構成する汎用コンピューティングデバイスを示す図である。
【図２】簡略化したストリーミングメディア通信パイプラインのブロック図である。
【図３】ビット対メディア時間から見た、図２の通信パイプラインの点Ａ、Ｂ、Ｃ、およびＤを符号化ビットストリームのビットが通過するスケジュールを示すグラフである。
【図４】ビット対メディア時間から見た、符号化スケジュールを含むバッファチューブを示すグラフである。
【図５】クライアント時間対メディア時間で到着スケジュールとその上限を示すグラフであり、時間の経過とともに堅牢性を増すように、再生の期限よりも次第に早くなっていく目標スケジュールに合わせて上限が調整されるグラフである。
【図６】目標到着スケジュールの設定を示すグラフである。
【図７ａ】対数の目標到着スケジュールを示すグラフである。
【図７ｂ】２つの部分からなる線形の目標到着スケジュールを示すグラフである。
【図８】各種の送信レートのバッファチューブを示すグラフである。
【図９】指数的な平均化を示すグラフである。
【図１０】バッファチューブの変化と制御目標の調整を示すグラフである。
【図１１Ａ】本発明による符号化ビットレートの制御方法の一実施形態を示す流れ図である。
【図１１Ｂ】本発明による符号化ビットレートの制御方法の一実施形態を示す流れ図である。
【図１１Ｃ】本発明による符号化ビットレートの制御方法の一実施形態を示す流れ図である。
【図１２】符号化ビットレートを控えめに上方に切り替える手順で使用される控えめな制限を示す時間線である。
【符号の説明】
【０３５５】
１１０  コンピュータ
１４１  ハードディスクドライブ
１５１  磁気ディスクドライブ
１５５  光ディスクドライブ
１５６  不揮発性の光ディスク
１９３  画像のシーケンス
【図１】
2006174419.tif 000122
【図２】
2006174419.tif 000123
【図３】
2006174419.tif 000124
【図４】
2006174419.tif 000125
【図５】
2006174419.tif 000126
【図６】
2006174419.tif 000127
【図７ａ】
2006174419.tif 000128
【図７ｂ】
2006174419.tif 000129
【図８】
2006174419.tif 000130
【図９】
2006174419.tif 000131
【図１０】
2006174419.tif 000132
【図１１Ａ】
2006174419.tif 000133
【図１１Ｂ】
2006174419.tif 000134
【図１１Ｃ】
2006174419.tif 000135
【図１２】
2006174419.tif 000136