JP2000222332A - 交換符号化プロキシのための方法およびシステム - Google Patents

Abstract

(57)【要約】 【課題】 交換符号化の利点を増加させるように、交換
符号化パラメータを動的に調整する方法、装置及びシス
テムを提供すること。 【解決手段】 適応化の方法が、ネットワーク特性及び
交換符号化されるイメージのサイズの可変性を処理する
ように設計される。本発明はまた、交換符号化プロキシ
が１イメージまたは１クライアントごとに、品質対サイ
ズのトレードオフを調整することを可能にする方法及び
装置を提供する。適応交換符号器が各オブジェクトに対
して異なるパラメータを選択し、性能改善を提供する。
本発明は更に、有効帯域幅、イメージの内容及びタイ
プ、及びユーザ選択を考慮して、ポリシ決定を行う汎用
フレームワークを提供する。本発明はまた、最適な交換
符号化パラメータの選択に関するフィードバックをユー
ザに生成する方法を含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文書内に埋め込ま
れるイメージ・オブジェクトを変換するブラウザ・プロ
キシに関し、より一般的には、ＭＩＭＥカプセル化オブ
ジェクト及びワールド・ワイド・ウェブを処理する任意
のプロキシまたはゲートウェイ・システムに関する。

【０００２】

【従来の技術】交換符号化（transcoding）プロキシ
は、時にウェブ・サーバと、諸特性と通信リンクを介し
て接続される様々なクライアント装置間の媒介として作
用する。一般に、交換符号化プロキシは、２つの主な利
点を提供し、それらは、低帯域幅リンクにおけるダウン
ロード時間の劇的な短縮と、クライアント装置へのウェ
ブ・データの個別の適合化である。

【０００３】モバイル装置はしばしば、低帯域幅ワイヤ
レス・モデム・リンクまたは中間帯域幅ワイヤレス・モ
デム・リンクを介して接続され、イメージなどの豊富な
ウェブ内容を見ることを、その非常に長いダウンロード
時間の必要性により、厄介にする。更に、こうしたダウ
ンロードのコストは、有料広域ワイヤレス・ネットワー
クを介すると法外に高くなる。交換符号化ウェブ・プロ
キシは、そのほとんどのセマンティック値を維持しなが
ら、ウェブ・データのサイズを縮小できる。多くの一般
的なウェブ・イメージにおいて、６倍乃至１０倍のダウ
ンロード時間の短縮が、それらの了解度を失うことな
く、達成され得る。

【０００４】第２の重要な利点は、こうした中間プロキ
シは時に、小型で優柔不断に接続されるものの、現在入
手可能なウェブ対応の多数のモバイル装置のために、テ
キスト及びイメージを個別に適合化できることである。
ウェブ内容を受信、処理、記憶及び表示するこれらのモ
バイル装置の能力は様々である。様々なクライアント装
置が存在すると、インターネット内容発行者にとって、
個々の装置のために内容を個別に適合化することは困難
である。結果的に、稼働中のウェブ・プロキシがウェブ
内容を交換符号化または変更し、それにより小型画面の
装置の解像度、色深度、及びサイズ制限に最適に適合化
させたり、記憶データのサイズをそのオリジナル・サイ
ズの一部に縮小するために使用される。

【０００５】典型的な交換符号化ウェブ・プロキシは、
ＨＴＴＰプロキシ内に交換符号化モジュールを追加する
ことにより実現され得る。交換符号化モジュールは、デ
ータ・オブジェクト（例えばイメージまたはＨＴＭＬペ
ージ）を入力として受け取り、それを一連の選択パラメ
ータに従い、低解像オブジェクト（例えば低品質イメー
ジまたは要約ＨＴＭＬページ）に変換する入出力システ
ムである。これらのパラメータは交換符号器に入力さ
れ、交換符号器がオブジェクトの解像度損失及びサイズ
縮小を決定する。以下の議論は主として、イメージ・オ
ブジェクトに関する。

【０００６】交換符号化の利点を最大化するために、最
高の品質のイメージがユーザにより指定される遅延許容
内で送信されるように、品質対サイズのトレードオフを
選択することが重要である。しかしながら、交換符号化
パラメータの適切なセットの選択は、困難である。第１
に、交換符号化されるイメージのサイズを推定すること
は困難である。なぜなら、交換符号化を通じて達成され
る圧縮度合いは、内容に依存するからである。例えば、
あるＪＰＥＧファイルは最大８０％圧縮され得るが、他
のものは５％以下の圧縮を達成するに過ぎなかったりす
る。同じことが、ＧＩＦ−ＧＩＦ変換またはＧＩＦ−Ｊ
ＰＥＧ変換が適用されるときにも当てはまる。交換符号
化は計算集中型のプロセスであるので、処理は高圧縮率
が達成され得る場合だけ、価値がある。既に高度に圧縮
された（または低品質の）イメージの場合、交換符号化
は無駄である。

【０００７】たとえ交換符号化された出力のサイズが予
測できても、ネットワーク可変性がイメージのダウンロ
ード時間の予測を困難にする。ユーザにより感知される
品質及び待ち時間は、最終的な性能指標なので、品質対
サイズのトレードオフの最適ポイントを選択するために
は、ダウンロード時間の正確な推定が必要となる。イン
ターネットなどの最善的サービス・ネットワーク上で
は、ネットワーク特性（帯域幅、遅延、損失率）の正確
な推定値を計算するのは困難である。しばしば、相違が
非常に大きくなり、品質調整を実行する上で、統計的推
定値が意味の無いものになる。

【０００８】ポリシ（policy）決定を複雑なタスクにす
る別の問題は、ネットワーク内のボトルネックの位置で
ある。ウェブ・サーバとプロキシ間の経路がボトルネッ
クの場合、交換符号化は全く役に立たない。それどころ
か、オペレーションの蓄積転送の性質により事態を一層
悪化させる。理想的には、ウェブ・サーバからウェブ・
プロキシへの経路がボトルネックの場合、ウェブ・プロ
キシは常に、イメージをウェブ・サーバからクライアン
トに転送すべきである。プロキシからクライアントへの
経路がボトルネックの場合でさえも、サイズ縮小による
利点が、交換符号化により生じる蓄積転送遅延に対し
て、重み付けされなければならない。

【０００９】ネットワーク特性及びイメージ内容の推定
が困難なことにより、交換符号化プロキシはしばしば、
非常に粗いレベルで、適応化をサポートするだけであ
る。適応化には、通常、予め定義されたデフォルト値の
セットから選択される、またはユーザにより選択され
る、交換符号化パラメータの変更が含まれる。両方のア
プローチに関わる問題は、交換符号化の完全な可能性が
利用されないことである。予め定義された静的ポリシ
は、ネットワーク帯域幅の変化には応答せず、ユーザ選
択可能なポリシ決定は、ネットワークの状態に関する知
識の欠如により、準最適となりがちである。ネットワー
クとプロキシの結合状態に関するフィードバックをユー
ザに提供する方法は存在しない。反復改良を用いること
により、ユーザは交換符号化パラメータの最適な選択に
向けて収束することができるが、こうしたプロセスは時
間を要し、余りユーザフレンドリではない。

【００１０】図１は、様々なリンク及び様々なクライア
ント装置を有する交換符号化プロキシ状況１００の例を
示す。図１に示されるように、ここではクライアント１
３０乃至１３４のための全てのウェブ要求及び応答が、
総称的なＨＴＴＰ（ハイパテキスト転送プロトコル）プ
ロキシ１９０を介して転送される状況について考える。
図１の状況では、最後のリンク１６０乃至１６４を介し
て、プロキシからクライアントへ大きなデータ・オブジ
ェクト、主にイメージをダウンロードすることが、クラ
イアント１３０乃至１３４により経験される終端間応答
時間の遅延の主な原因である。

【００１１】交換符号化プロキシ１９０はウェブ・デー
タの大量のデータ間引きを提供し、低速広域ワイヤレス
・リンクを介して、ウェブ・データのリアルタイム・ブ
ラウジングを可能にする。こうしたワイヤレス・リンク
には、リンクを共用するクライアント数に応じて、１０
ｋｂ／秒以下のスループットを提供するセルラ・デジタ
ル・パケット・データ（ＣＤＰＤ）１６３などが含まれ
る。終端クライアントは、優れたカラー表示装置を有す
る全機能ＰＣ１３４などであり、従って主な問題は帯域
幅の減少である。或いは、クライアントは小型のウェブ
対応のモバイル装置１３０乃至１３２であり、この場
合、ウェブ・データを特定のクライアント装置のため
に、特にクライアントの表示装置特性のために、個別に
適合化することが有利である。交換符号化プロキシ設計
の異なる態様は異なる状況（すなわち、有料プロキシ−
クライアント間リンク、或いは強力なまたは貧弱なクラ
イアント表示装置など）のために役立つが、全てが同一
のプロキシ・アーキテクチャ１００内で良好に処理され
る。

【００１２】図２は、ユーザ指定選択及び静的ポリシに
もとづき、オブジェクトを変換するために使用される交
換符号化プロキシ１９０の実施例のブロック図を示す。
交換符号化プロキシ１９０は、交換符号化モジュール２
４０とＨＴＴＰプロキシ・エンジン２２０とを結合する
ことにより構成される。ＨＴＴＰ要求２２２がクライア
ント２３０から生成され、プロキシ１９０により、ウェ
ブ・サーバ２１０に転送される（２２４）。応答データ
２２６（すなわちＨＴＭＬページ及びＧＩＦ及びＪＰＥ
Ｇイメージ）が交換符号器２４０により変換され、クラ
イアント２３０に転送される（２２８）。一般に、多数
の交換符号化パラメータが交換符号器２４０に対して指
定され、応答データ２２６内に含まれるオブジェクトの
所望の品質及びサイズ縮小を達成する。今日使用される
交換符号化プロキシは、静的ポリシ・セット２５０を使
用するか、経路２６５を介して特定形式のユーザ指定選
択２６０を使用することにより、交換符号化パラメータ
を決定する。交換符号化パラメータの固定セットが全て
のオブジェクトに適用されるとき、結果は常に有利であ
るとは限らない。実際、多くの場合、交換符号化は性能
の劣化を生じる。

【００１３】

【発明が解決しようとする課題】本発明の目的は、交換
符号化の利点を増加させるように、交換符号化パラメー
タを動的に調整する方法、装置及びシステムを提供する
ことである。適応化の方法が、ネットワーク特性及び交
換符号化されるイメージのサイズの可変性を処理するよ
うに設計される。

【００１４】

【課題を解決するための手段】１実施例では、本発明は
３つの新たな要素、すなわちイメージ・サイズ予測器、
ネットワーク帯域幅分析器、及びポリシ・モジュールを
含む。交換符号化活動を開始する前に、ポリシ・モジュ
ールがイメージ・サイズ予測器に、出力イメージのサイ
ズを推定するように問い合わせる。帯域幅分析器は、サ
ーバからプロキシへの、及びプロキシからクライアント
への、イメージ伝送時間の推定値を収集するように問い
合わされる。収集された推定値にもとづき、プロキシは
イメージを交換符号化するか否かを判断する。更にポリ
シ・モジュールが、ユーザ指定性能基準（例えば短縮さ
れた応答時間、または向上された品質）を提供する、品
質対サイズのトレードオフの最適ポイントを計算する。

【００１５】本発明の別の態様は、交換符号化プロキシ
が１イメージまたは１クライアントごとに、品質対サイ
ズのトレードオフを調整することを可能にする方法及び
装置を提供する。適応交換符号器が、各オブジェクトに
対して異なるパラメータを選択し、性能改善を提供す
る。

【００１６】更に本発明の別の態様は、有効帯域幅、イ
メージの内容及びタイプ、及びユーザ選択を考慮して、
ポリシ決定を行う汎用フレームワークを提供する。プロ
キシの管理者は、システムから改善された性能を獲得す
るために、様々な最適化目標の中から選択する。１実施
例では、プロキシ交換符号器のスループットがボトルネ
ックの場合、全ユーザに対する応答時間を短縮するため
に、ポリシ・モジュールが賢明にＣＰＵ資源を使用する
ように命令される。本発明の有利な要素は、方針決定の
自動化の性質であり、ユーザをプロキシのポリシ・エン
ジンの活動的な制御から解放する。

【００１７】更に本発明の別の態様では、最適な交換符
号化パラメータの選択に関するフィードバックを、ユー
ザに生成する方法が提供される。１実施例では、交換符
号化システムが、ユーザ選択スライダ・バーの位置を動
的に調整することにより、フィードバックをユーザに提
供する。ユーザ選択スライダ・バーは、入力装置及び出
力装置の両方として作用する。

【００１８】

【発明の実施の形態】図３は、本発明に従う、交換符号
化プロキシ１９０に対する変更の実施例のブロック図３
００を示す。図３を図２と比較すると、図２の静的ポリ
シ・モジュール２５０が、図３では動的ポリシ・モジュ
ール３７０により置換されているのが分かる。動的ポリ
シ・モジュール３７０の目的は、交換符号化をオン／オ
フする時期、及び使用する交換符号化ポリシ（すなわち
交換符号化アルゴリズム及びそのパラメータ）を決定す
ることである。動的ポリシ・モジュール３７０はまた、
イメージ・サイズ及び遅延予測器３７５、帯域幅推定器
３８０、及びユーザ・フィードバック・プロバイダ３９
０とインタフェースする。図示の実施例では、ポリシ・
モジュール３７０は次の多数の基準を使用する。 １．内容分析フロー図（図５に示される）により決定さ
れるデータの特性（例えばイメージのサイズ、現符号化
効率、ＨＴＭＬページの構造的役割） ２．プロキシ−クライアント間リンク及びサーバ−プロ
キシ間リンクの帯域幅の現推定値 ３．クライアントの特性、特にクライアント表示装置の
能力 ４．データの好適なレンダリング（描画）に関するユー
ザ選択（図１１にユーザ・スライド・バー選択として示
される）

【００１９】図５、図１０及び図１１に示される項目に
ついて、以下で述べる。特に、図１１のユーザ・スライ
ド・バー選択は、交換符号化プロキシと対話し、イメー
ジ品質とダウンロード時間の間のトレードオフを動的に
変更する方法を提供する。入力インタフェースとして作
用することに加え、スライド・バー（図１１の１１４
０、１１５０、１１６０）は出力インタフェースとして
も作用し、動的ポリシ・モジュール３７０から受信され
るフィードバック３９０を表示する。

【００２０】図４は、本発明に従う交換符号化ＨＴＴＰ
プロキシ・システム４００内の、多重解像度キャッシュ
４１０の機能例を示すブロック図である。キャッシュ
は、同一のデータ・オブジェクトに対する（同一のまた
は異なるクライアントによる）反復データ要求に対し
て、短縮された応答時間を提供するために、ＨＴＴＰプ
ロキシ内で有用である。キャッシュされるデータが最新
であることを保証するために、様々な方法が使用され得
る。キャッシュ方式交換符号化システムの例４００で
は、多重解像度キャッシュ４１０が、データのオリジナ
ル・バージョンの他に、特定の装置タイプのために交換
符号化された解像度低下バージョンなどの、他の可能な
形式のデータを記憶する。

【００２１】例えば、再度イメージ・データ・オブジェ
クトの場合について考慮するが、当業者であれば、これ
らの方法が他のデータ・タイプにも適用され得ることが
理解できよう。ここではキャッシュ方式交換符号化プロ
キシ・システムの状況において、様々な形式のデータを
記憶、タグ付け、及び検索する方法について述べる。

【００２２】図４を参照すると、クライアント２３０に
よる要求に応答して、ＪＰＥＧイメージがサーバ２１０
から受信される場合が想定される。このイメージは有損
失のＪＰＥＧ符号化形式から、イメージのビットマップ
表現に復号される。イメージ処理に関わる当業者であれ
ば、ＪＰＥＧ符号化規格が、離散コサイン変換（ＤＣ
Ｔ：Discrete Cosine Transforms）を重み付けする係数
を用いてイメージを記述し、従って各画素の実際の色を
獲得するために、計算集中型の復号ステップが一般に要
求されることが理解できよう。このビットマップは、オ
リジナルＪＰＥＧイメージよりも大きな記憶サイズを要
求する。しかしながら、十分なサイズのキャッシュが提
供される場合、この拡張サイズのイメージを（データ経
路４２０を介して）記憶することが価値がある。それに
より、同一イメージの交換符号化バージョンが、後に、
最初の要求と異なる交換符号化パラメータにより要求さ
れるとき、ＪＰＥＧ復号のための計算集中型のステップ
を回避することができる。第２のステップでは、交換符
号化パラメータ（例えば色深度、スケーリング・ファク
タ、及びＪＰＥＧ品質係数）にもとづき、ＪＰＥＧイメ
ージが再符号化される。イメージはＪＰＥＧイメージと
して、または別の符号化形式で再符号化される。イメー
ジの最後の交換符号化バージョンもまた、データ経路４
２０を介して、多重解像度キャッシュ４１０に記憶され
る。

【００２３】実施例では、追加のデータ要求が発生する
とき、ＨＴＴＰプロキシ２２０が最初に、そのキャッシ
ュ４１０をチェックし、データ・オブジェクトの"最新
の"バージョンが、要求解像度または交換符号化レベル
において、入手可能か否かを確認する。多重解像度キャ
ッシュ４１０内の各オブジェクトは、ＵＲＬ記述、デー
タ・オブジェクトのタイム・スタンプ、及びオブジェク
ト特性を含むバージョン指定子と共に記憶される。ＪＰ
ＥＧイメージの場合、オブジェクト特性は色深度、スケ
ーリング・ファクタ、及びＪＰＥＧ品質係数を含む。別
の実施例は、ＪＰＥＧイメージが復号され、そのビット
マップ形式で記憶されたこと、またはＪＰＥＧイメージ
が変換され、ＧＩＦとして様々な特性と共に記憶された
ことの指示を有する。

【００２４】要求タイプ及び解像度を有するオブジェク
トの最新のバージョンが入手可能な場合、そのバージョ
ンがクライアントに返却される。これが入手可能でない
けれども、オブジェクトの最新のバージョンが、そのオ
リジナルＪＰＥＧ形式または復号ビットマップ形式で存
在する場合、このバージョンが変換符号器２４０に、そ
の特性の指示と共に返却される。これにより変換符号器
２４０はオブジェクトの所望のバージョンを生成するこ
とができ、それがクライアント２３０に返却され、デー
タ経路４２０を介して、多重解像度キャッシュ４１０に
記憶される。

【００２５】この機構には、当業者には明らかな幾つか
の拡張が存在する。ある拡張では、オリジナル・データ
・オブジェクトではなく、オブジェクトの既に交換符号
化されたバージョンを使用し、オブジェクトの解像度低
下バージョンを生成する。キャッシュ内でデータ・オブ
ジェクトの異なる解像度バージョンを管理する方法は、
R．O．LaMaire及びJ．T．Robinsonによる１９９８年２
月１３日付けの米国特許出願第１０２９４４号"Conserv
ing Storage Spase by Means of Low Resolution Objec
ts"（出願人整理番号：ＹＯ９９７３０８）で述べられ
ている。

【００２６】図５は、図３及び図４の動的ポリシ・モジ
ュール３７０のフロー図の例を示す。図５はまた、ポリ
シ・モジュール３７０が、図３のＨＴＴＰプロキシ・エ
ンジン２２０及びオブジェクト変換符号器２４０とイン
タフェースする様子を示す。後述の方法は、テキスト、
イメージ、音声及びビデオを含む多くの内容タイプに当
てはまる。しかしながら、以下の議論は、イメージ・デ
ータ・タイプにだけ着目する。しかしながら、当業者で
あれば、この概念及び動的ポリシが、他の媒体タイプに
も適用可能であることが明らかであろう。

【００２７】図５は、サーバ２１０から受信される応答
ヘッダにもとづき、ＨＴＴＰプロキシ・エンジン２２０
が最初に、オブジェクト５１０のサイズを決定すること
を示す。応答の内容タイプが"image/*"の場合（ステッ
プ５２０）、プロキシ・エンジン２２０は更に分析のた
めに、オブジェクトのハンドルを動的ポリシ・モジュー
ル３７０に受け渡す。ポリシ・モジュール３７０内で
は、入力オブジェクトのサイズが、"size_threshold"と
呼ばれる予め構成済みのしきい値と比較される（ステッ
プ５３０）。オブジェクトが"size_threshold"よりも小
さいか、内容タイプが"image/*"でない場合（ステップ
５２０）、オブジェクトは交換符号化されず、代わりに
内容変更無しにクライアントに転送される（ステップ５
１５）。ウェブ上で見いだされる小さなオブジェクト
（ブレット（bullet）、サムネイル（thumbnail）、ロ
ゴ（logo）など）は一般に、既にＧＩＦ符号化により十
分に圧縮されたＧＩＦオブジェクトである。こうしたオ
ブジェクトの交換符号化は、一般にそれ以上の圧縮を生
成しない。

【００２８】ここではＧＩＦイメージを、サイズ的にま
たは色深度的に低減されたＧＩＦまたはＪＰＥＧイメー
ジに変換する（最終形式としてのＧＩＦまたはＪＰＥＧ
の選択は、イメージ特性に依存する）。更にＪＰＥＧイ
メージを、ＪＰＥＧ品質、サイズ、または色深度的に低
減されたＪＰＥＧイメージに変換する。ＪＰＥＧ品質
は、ＪＰＥＧ符号化規格で使用される離散コサイン変換
の係数が量子化される度合いを決定するために使用され
る、交換符号化パラメータを指し示す。ＪＰＥＧ品質パ
ラメータはまた、知覚されるイメージ品質の良き予測子
であることが判明している。このパラメータは１乃至１
００の範囲内で変化し、１００は非常に高い品質を表
す。ウェブ上で見いだされるＪＰＥＧイメージは、通
常、７５のＪＰＥＧ品質パラメータを有する。

【００２９】大きなイメージの場合、イメージ符号化の
タイプ（ＪＰＥＧまたはＧＩＦ）及び符号化の効率は、
交換符号化の方針決定において重要なファクタである。
ＪＰＥＧは有損失圧縮法であるので、サイズ縮小は品質
係数を低減することにより、常に可能である。しかしな
がら、類似の品質低下はＧＩＦファイルには適用できな
い。なぜなら、ＧＩＦは無損失圧縮法であるからであ
る。品質低下を達成するためには、ＧＩＦファイルは最
初に復号され、次に品質低下されたＪＰＥＧイメージと
して、再符号化されなければならない。しかしながら、
この方法は常にサイズの縮小を提供するとは限らない。
ＧＩＦ形式は通常、地図、ロゴ、及び図を符号化するた
めに、より効率的であるのに対してＪＰＥＧは自然画を
符号化するために、より効率的である。ＧＩＦからＪＰ
ＥＧへの変換は、オリジナルＧＩＦイメージが効率的に
符号化されない場合のみ有用である。

【００３０】ここでは圧縮効率の指標として、１画素当
たりのビット数（ｂｐｐ：bit perpixel）を定義する。
ｂｂｐは、イメージ領域に対するイメージ・ファイル・
サイズの比率として、画素を単位として計算される。処
理ステップ５４０で、イメージ・ヘッダを解析すること
により、入力イメージのＸ及びＹ寸法、及びｂｐｐ値が
計算される。入力オブジェクトが"image/jpg"タイプの
場合（ステップ５５０）、交換符号化が常に実行され
る。しかしながら、内容タイプが"image/gif"の場合
（ステップ５２５）、"gif_threshold"よりも大きいｂ
ｐｐ比率を生じるオブジェクトだけが交換符号化される
（ステップ５３５）。ＧＩＦファイルは余り効率的に符
号化されず、"gif_threshold"よりも大きなｂｐｐ値を
生成する。従って、判断ステップ５３５は、圧縮可能な
ＧＩＦファイルを高精度で識別する上で、非常に効果的
である。図５では示されていないが、当業者であれば、
（進行的に符号化されるデータに対する）スケーリング
及びファイル打ち切り（filetruncation）などの、他の
交換符号化ポリシも十分に圧縮されたＧＩＦに対して使
用され得ることが明らかであろう。

【００３１】本発明の重要な態様は、決定ステップ５１
０乃至５６５が、イメージ・ヘッダが受信されると直ち
に実行されることである。交換符号化しないことが決定
される場合、イメージ・セグメントはそれらがサーバか
ら受信されると直ちに、蓄積転送遅延を招くことなく転
送される。同様に、交換符号化が実行される場合、イメ
ージがバッファリングされ、続いて交換符号化されるか
（蓄積転送交換符号化法）、各セグメントがオンザフラ
イ式に交換符号化される（ストリーム式交換符号化
法）。

【００３２】圧縮可能なイメージを識別後、次のステッ
プは、選択イメージが交換符号化されるべき程度を決定
する。ポリシ関数５６５は、３つの異なるソース（イメ
ージ・サイズ予測器３７５、帯域幅推定器３８０、ユー
ザ選択セレクタ２６０）から入力を収集し、続いて図８
に示されるステップに従い、交換符号化パラメータを選
択する役目をする。選択されたパラメータは、オブジェ
クト交換符号器２４０により実行される圧縮の程度及び
タイプを決定する。例えば、スケーリング・パラメータ
は、あるイメージがどのくらいダウンサンプリングされ
るかを決定する。量子化パラメータは、イメージが画素
領域内または周波数領域内で、どのように量子化される
かを制御する。カラー・マップド・イメージ内の色の数
が低減されるか、２４ビット・カラー・イメージが８ビ
ット・グレースケールまたはモノクロ表現に変換され得
る。交換符号化のプロセスはステップ５７０で実行さ
れ、交換符号器の出力がクライアント２３０に転送され
る。

【００３３】ポリシ関数５６５の重要な態様は、交換符
号化方針を決定する分析フレームワークである。分析フ
レームワークは、有効帯域幅、イメージのタイプ及びサ
イズ、ユーザ選択などのファクタを考慮し、交換符号化
方針を決定するための目標基準を提供する。例えば、こ
こではユーザにとっての応答時間の最小化を目標と見な
すが、当業者であれば、同一のフレームワークを使用す
ることにより、他の最適化基準も適用され得ることが理
解できよう。ここではいつ交換符号化するのが有利か、
またどの程度まで交換符号化が適用されるべきかを決定
する方法について述べる。ここで述べられる実施例は、
交換符号化パラメータの動的適応化と呼ばれる。

【００３４】図６は、ウェブ要求−応答サイクル例、及
び蓄積転送交換符号化プロキシ１９０を介して、サイズ
Ｓのオブジェクトをフェッチする応答時間を示す。ここ
ではイメージ交換符号器として、蓄積転送イメージ交換
符号器を定義し、これはイメージに対して交換符号化を
開始する前に、入力イメージ全体を蓄積するのを待機し
なければならず、またイメージが出力可能になる前に、
交換符号化イメージ全体を生成するのを待機しなければ
ならない。図６に示されるように、サイズＳ（バイト）
６７０のオリジナル・イメージ６２０が、有効帯域幅Ｂ
_sp（ビット／秒）のサーバ−プロキシ間接続を介して、
蓄積転送プロキシにダウンロードされる。交換符号器は
遅延Ｄ_x（Ｓ）６５０を導入し、サイズＳ_x（Ｓ）６８０
の出力イメージ６３０を生成する。交換符号化遅延６５
０及び出力イメージのバイト・サイズ６８０の両方が、
入力イメージのバイト・サイズＳ６７０に依存して表さ
れる。交換符号化イメージが次に、有効帯域幅Ｂ_pcを有
するプロキシ−クライアント間接続を介して、伝送され
る。

【００３５】ポリシ関数は、交換符号化により達成され
る任意のサイズ縮小に対して、交換符号化の犠牲（遅
延）を重み付けする必要がある。交換符号化が利点を提
供するために、交換符号化により導入される遅延が、圧
縮による伝送時間の短縮により相殺されなければならな
い。非常に低い帯域幅のプロキシ−クライアント間アク
セス・リンクでは、一般に、積極的なイメージ圧縮によ
る応答時間の短縮が、計算集中型の交換符号化に起因す
る応答時間の追加を遥かに上回る。しかしながら、図７
はプロキシ−クライアント間リンクの帯域幅が増加する
と、もはや交換符号化が有利でなくなるポイント（交換
符号化しきい値７１０）に達することを示している。な
ぜなら、積極的な圧縮による応答時間の短縮は、ボトル
ネック・リンクの帯域幅の関数として減少するが、交換
符号化時間は一定に維持されるからである。

【００３６】ここでＲ_oを、交換符号化がオフ状態にお
いて、サイズＳのウェブ・オブジェクトをウェブ・サー
バからフェッチする応答時間とする。同様に、Ｒ_pを同
一のウェブ・オブジェクトの交換符号化バージョンを、
交換符号化プロキシを介してフェッチする応答時間とす
る。以下の議論のために、ここではキャッシングがプロ
キシにおいてサポートされていないものと仮定する。

【００３７】交換符号化がオフ状態において、クライア
ントにより感知される応答時間は、次の３項の合計であ
る。

【数１】 Ｒ_o＝２ＲＴＴ_pc＋２ＲＴＴ_sp＋Ｓ／min（Ｂ_pc、Ｂ_sp）

【００３８】ＲＴＴ_pcは、クライアントとプロキシ間の
ネットワーク往復待ち時間であり、同様にＲＴＴ_spはプ
ロキシとサーバ間の待ち時間である。ウェブ・オブジェ
クトのフェッチは、ＨＴＴＰ要求／応答の他に、ＴＣＰ
ＳＹＮ／ＡＣＫ交換を要求するので２ＲＴＴ_pc＋２Ｒ
ＴＴ_spが遅延項として寄与する。更に、ウェブ・イメー
ジは、その最初のビットと最後のビット間の時間の広が
りに等しい伝送遅延を招く。ここでmin（Ｂ_pc、Ｂ_sp）
は、クライアントとサーバ間のボトルネック帯域幅を示
すものとする。プロキシが不在の場合、イメージの最初
と最後のビットは、Ｓ／min（Ｂ_pc、Ｂ_sp）だけ時間的
に広がる。この広がりは、サーバ−プロキシ−クライア
ント間連結接続を介する、イメージの有効伝送時間に対
応する。

【００３９】交換符号化がオン状態の時、プロキシは蓄
積転送モードで動作する。２ＲＴＴ _pc＋２ＲＴＴ_spが再
度、応答時間の固定要素である。Ｄ_p（Ｓ）は、交換符
号化遅延を表す追加の項である。交換符号化オブジェク
トにおける結果の応答時間は、次のように表される。

【数２】Ｒ_p＝２ＲＴＴ_pc＋２ＲＴＴ_sp＋Ｄ_p（Ｓ）＋Ｓ
／Ｂ_sp＋Ｓ_p（Ｓ）／Ｂ_pc

【００４０】Ｒ_p＜Ｒ_oの場合、すなわち次式が成立する
場合、交換符号化は応答時間を短縮する。

【数３】Ｄ_p（Ｓ）＋Ｓ／Ｂ_sp＋Ｓ_p（Ｓ）／Ｂ_pc＜ｓ／
min（Ｂ_pc、Ｂ_sp）

【００４１】明らかに、Ｂ_pc＞Ｂ_spの場合、Ｒ_pは常に
Ｒ_oよりも大きい。他方、Ｂ_pc＜Ｂ_spの場合には、交換
符号化は次の場合に限り有用となる。

【数４】 Ｄ_p（Ｓ）＋Ｓ／Ｂ_sp＜（Ｓ−Ｓ_p（Ｓ））／Ｂ_pc

【００４２】前記式は、交換符号化が応答時間を短縮す
る状態を正確に特徴化する。図８は、上述した分析フレ
ームワークを用いて構成されるポリシ関数のフロー図を
示す。ステップ８１０は、ポリシ関数の入口ポイントを
記す。ポリシ関数８００は図５のステップ５６５で呼ば
れ、オリジナル・イメージ・オブジェクト・サイズがポ
リシ関数への入力の１つとして選択される。変数Ｓは入
力オブジェクト・サイズに等しくセットされ、品質係数
ｑは、可能な最善の初期イメージ品質（例えば入力イメ
ージの品質）に初期化される。ステップ８３０で、ポリ
シ関数８００は帯域幅推定器３８０に問い合わせを発行
し、指定サーバからプロキシへのオブジェクト・サイズ
Ｓの推定ダウンロード時間、すなわちＴ₁（Ｓ）を尋ね
る。ポリシ関数８００はまた、プロキシからクライアン
トへの同一のオブジェクトの推定ダウンロード時間、す
なわちＴ₂（Ｓ）も問い合わせる。選択された宛先への
以前の接続のログにもとづき、帯域幅推定器はＴ
₁（Ｓ）及びＴ₂（Ｓ）の推定値を返却する。次のステッ
プ８４０で、ポリシ関数はイメージ・サイズ及び遅延予
測器３７５に、交換符号化イメージ・サイズＳ_p（Ｓ）
の推定値を見いだすように問い合わせる。ポリシ関数は
次にステップ８５０で、Ｔ₂（Ｓ）から、交換符号化イ
メージ・サイズのダウンロード時間推定値Ｔ₂（Ｓ
_p（Ｓ））を減算することにより、推定ダウンロード時
間節約を計算する。最後に、ステップ８７０で、２つの
量（交換符号化遅延＋Ｔ₁（Ｓ）−ダウンロード節
約）、及び目標応答時間短縮が比較される。第１の項が
第２の項よりも小さい場合、ステップ８８０で計算は中
止され、選択された品質係数ｑが出力として返却され
る。それ以外では、ｑ値が低減され、ループ８４０乃至
８７０に再入力する。

【００４３】当業者によれば、より効率的な探索技法ま
たは目的関数の変形が、本発明において提供されるポリ
シ関数フレームワークの趣旨から逸れることなく、設計
され得ることであろう。１つの拡張は、ポリシ方程式内
の項を次のように再編成することである。

【数５】応答時間短縮（ｑ）＝｛Ｓ−Ｓ_p（Ｓ）｝／Ｂ
_pc−Ｄ_p（Ｓ）−Ｓ／Ｂ_sp

【００４４】上記式では、Ｓ_p（Ｓ）もまた品質係数の
関数である（出力サイズが小さいほど、品質が低下す
る）。交換符号化遅延は実際上、品質係数に無関係であ
ることが判明している。上記式内には２つの独立変数、
すなわち品質係数ｑ及び目標応答時間短縮が存在する。
上記式のフレームワーク内において、幾つかの異なるポ
リシが生成され得る。それらは例えば、 全てのユーザに対して、応答時間を最小化するポリシ ユーザ指定の応答時間制限において、品質を最大化する
ポリシ １ユーザに対してだけでなく、全体的なシステム性能を
最適化するポリシ などである。

【００４５】交換符号化は計算集中型のタスクであり、
プロキシだけがＣＰＵ能力を制限したので、プロキシの
ＣＰＵサイクルは、全体的なユーザの満足を最大化する
タスクのセットに対して消費された。ピーク利用期間中
に、あらゆるユーザが交換符号化をオンすると、全ての
交換符号化要求を満足するのに十分なＣＰＵサイクル
が、使用可能でなくなり得る。パラメータ選択の責任を
ポリシ関数８００に委任することにより、システムは自
動的に最適な交換符号化パラメータを選択し、エンドユ
ーザに対して、一貫した予測可能な応答を提供すること
ができる。ユーザがこれらのパラメータを独立に選択す
る場合、交換符号化システムは最適な性能レベルで動作
し得ないであろう。

【００４６】次に、交換符号化遅延及びサイズ推定につ
いて考えてみよう。判断ステップ８７０は２つの追加の
入力、すなわち、交換符号化イメージのサイズの推定値
Ｓ_p（Ｓ）、及び交換符号化プロセスの間に導入される
交換符号化遅延Ｄ_p（Ｓ）を要求する。これらの２つの
量の正確な予測は、獲得するのが困難である。なぜな
ら、それらはイメージ内容、使用される符号化のタイ
プ、オリジナル品質係数、プロセッサ・スピード、及び
プロキシの負荷に依存するからである。帯域幅推定器の
場合同様、本発明は統計的方法を使用し、これら２つの
量を推定する。

【００４７】図９は、本発明に従うイメージ・サイズ予
測モジュールの例のブロック図である。ブロック９１０
に示されるように、ここではシステムを、イメージの大
きなベンチマーク・セットにもとづく、Ｓ_x（ｑ）の統
計的特性により初期化する。ブロック９１０に示される
方法は、パラメータｂｐｐ及びｑに依存する交換符号化
イメージ・サイズ分布関数を初期化するために使用され
る。プロキシは新たなイメージ・オブジェクトをフェッ
チし、交換符号化するとき、頻繁に新たなサンプル・ポ
イントを分布関数に追加する（ブロック９２０）。ブロ
ック９２０の関数は、イメージ・サイズ予測器３７５が
その振舞いを、クライアントがアクセスしているかも知
れない異なるデータ・セットに適応化することを可能に
する。

【００４８】従って、ブロック９３０で述べられる方法
では、統計的方法により、遅延及び出力サイズを推定
し、ｂｐｐ比率をイメージのより正確な分類を実行する
ための、従って結果の交換符号化ファイル・サイズのよ
り良い推定値を形成するための基準として使用する。こ
の方法は特にＧＩＦファイルに対して良く作用する。

【００４９】類似の統計的方法を使用することにより、
Ｄ_p（Ｓ）が統計的モデルのベンチマーク初期化及びオ
ンライン更新にもとづき推定され得る。また、統計的作
業から、交換符号化遅延が、（ファイル・サイズではな
く）画素数の線形関数として、良く特徴化されることが
判明した。

【００５０】次に、帯域幅及びダウンロード時間推定に
ついて考えてみよう。判断ステップ８７０の精度は、イ
メージ・ダウンロード時間推定値の精度にも大きく依存
する。図３乃至図５に示される帯域幅推定器３８０は、
これらの時間推定値を提供する責任がある。帯域幅推定
器３８０は、プロキシにおけるあらゆるパケット送受信
事象を記録し、収集されたトレースに対して統計分析を
実行し、ネットワークの状態に関して決定を行う。ネッ
トワーク・モニタリングの当業者であれば、ネットワー
ク・モニタリング機能が、幾つかの異なる方法により実
現され得ることが理解できよう。１技法は、プロキシ・
アプリケーションとソケット層間のシム層（shim laye
r）である。別の技法は、任意のパケット・フィルタリ
ング・ソフトウェア上の処理層である。一般に、パケッ
ト・フィルタリング・ソフトウェア上で構成される技法
は、帯域幅及びダウンロード時間のより正確な推定値を
提供する。本発明は、帯域幅モニタ３８０及びポリシ決
定ステップ８７０の両方が、同一のマシン上で実行され
ることを要求しないが、２つのモジュールを一緒に配置
することが、それらの間の通信のオーバヘッドを最小化
する。

【００５１】図１０は、本発明に従う帯域幅予測モジュ
ール３８０の例を示す。このモジュールは２つの構成要
素、すなわちトレース・モニタ１０１０及び統計分析器
１０２０から成る。トレース・モニタは、クライアント
とプロキシ間の全ての接続を連続的にモニタする。同一
のトレース・モニタ（または別のトレース・モニタ）
が、プロキシと全てのウェブ・サーバ間のトラフィック
をモニタするために使用される。モニタされる各接続に
対して、次の情報が記録される。 新たな接続が確立される時刻 各ネットワーク接続の出所アドレス、出所ポート番号、
及び宛先アドレス、宛先ポート番号 各接続上で送受信されるバイト数、及び各送受信事象の
それぞれのタイムスタンプ 接続が閉じられる時刻

【００５２】統計分析器１０２０は、過去の全ての及び
現在の全ての活動接続のデータベースを保持する。各接
続に対して、統計分析器はまた、何時どのように多数の
バイトがその接続上で送信または受信されたかの履歴を
保持する。この履歴にもとづき、統計分析器１０２０は
将来の接続のダウンロード時間に関して予測を行うこと
ができる。サーバからプロキシへのダウンロード時間、
及びプロキシからクライアントへのダウンロード時間を
予測するために異なる発見的方法を使用する。

【００５３】サーバからプロキシへのトレースは、広域
ＴＣＰ接続間で一般的な振舞いを示す。シーケンス対タ
イムスタンプのトレースは非線形であることが観測さ
れ、平均すなわち中央帯域幅などの線形予測の概念は、
正確な予測を生成しないことが見い出された。所与のサ
イズのオブジェクトのダウンロード時間を予測するため
に、帯域幅予測器は、選択された宛先への接続の履歴を
参照し、おおよそ同一サイズを有する全てのオブジェク
トに対する、ダウンロード時間の分布関数を計算する。
この分布の中央値（median）または他の適切な統計関数
が、ダウンロード時間推定値として返却される。

【００５４】それとは対象的に、プロキシ−クライアン
ト間のＴＣＰ振舞いは、一般に最終ホップ１６０乃至１
６４に相当する帯域幅制限リンクを有する影響により、
支配される。ボトルネック・リンクが存在するので、ク
ライアントへの全ての活動ＴＣＰ接続の集合体は、一般
にボトルネック・リンクを飽和状態にする。従って、プ
ロキシからクライアントへのダウンロード時間予測を提
供するために、帯域幅推定器はクライアントへの全ての
活動接続を、単一のグループに集合させる。各接続グル
ープに対して、帯域幅推定器は時間対バイト数をプロッ
トし、次にデータに対して線形曲線近似を実行する。こ
の技法は、プロキシとクライアント間の現在使用可能な
帯域幅の正確な推定値を提供する。この値は時間と共に
変化するが、変動はほとんどの場合制限される。例え
ば、帯域幅モニタは、曲線近似アルゴリズムの出力にお
いて分析することにより、クライアントが１０Ｍｂのイ
ーサネット、１４．４モデム、または２８．８モデムの
いずれにより接続されるかを、容易に検出できる。予測
値は正確ではないが（正確な値から２０％乃至３０％の
偏差を有する）、当業者であれば、帯域幅推定の精度が
推定アルゴリズムを改良することにより、改善され得る
ことが理解できよう。

【００５５】次に、交換符号化ユーザ・インタフェース
について考えてみよう。交換符号化ユーザ・インタフェ
ースは、ユーザがイメージ品質とダウンロード時間の間
のトレードオフを動的に変更するためのインタフェース
である。これは図２乃至図５のアイテム２６０として表
される。図１１は、本発明によるユーザ選択インタフェ
ースの１実施例を示す。このユーザ・インタフェース
は、Ｊａｖａアプレットとして実現され得る直線スライ
ド・バーとして表され、ユーザが連続的にイメージ品質
を変更することを可能にする。図１１に示されるよう
に、（グレースケールに対して）カラーを選択するオプ
ションも提供される。更に、オートパイロットを選択す
るオプションも、次の２つの態様で使用され得る。すな
わち、（１）上述のように、プロキシがクライアント−
プロキシ間及びプロキシ−サーバ間リンク帯域幅の現予
測、及び現在使用可能なＣＰＵ資源にもとづき、交換符
号化を実行するか否かを自動的に決定できることを、プ
ロキシに伝えるための指示として、或いは（２）プロキ
シに、ユーザが現在経験している現ダウンロード時間を
試行し、維持するように伝える指示として（すなわち、
プロキシにおいてイメージ品質を変更することにより、
帯域幅推定サブシステムにより検出される動的帯域幅変
化を補償する）、または前記（１）及び（２）の両方と
してである。ユーザが完全忠実度のデータ・バージョン
を要求するとき、彼らはスライド・バーを（下方に）調
整し、より高品質のデータを要求することにより、改良
データを容易に要求することができる。一般に、ほとん
ど全てのウェブ・ブラウジングが、イメージをそれらの
オリジナル・サイズの６分の１または１０分の１に交換
符号化することにより実行され、改良を要求する必要の
ある地図などのオブジェクトは、実際には稀に見い出さ
れるだけであることが判明した。別のＨＴＭＬ専用イン
タフェースは、ウィンドウズＣＥベースのプラットフォ
ームなどの、非Ｊａｖａ装置をサポートするために考案
されたことも述べておく。

【００５６】次に、ストリーム式イメージ交換符号化に
ついて述べる。上述の説明は一般に、蓄積転送交換符号
化プロキシに当てはまる。以下では、ストリーム式イメ
ージ交換符号器にとって、交換符号化に従事することが
有利である条件について述べる。ストリーム式イメージ
交換符号器は、入力形式に符号化されたイメージ全体に
対応する完全な入力ストリーム・バイトを完全に読込む
前に、出力形式に符号化されたイメージ・データの書出
しを開始する、イメージ交換符号器である。

【００５７】図１２は、タイミング図により、アルゴリ
ズムの背後にある論拠を示す。入力イメージは、１／Ｂ
_spの間隔をあけたビット・ストリームとして到来する。
ストリーム式イメージ交換符号器が、交換符号化のため
にＧビットのグループを受信し、小さな蓄積転送遅延Ｄ
₁を生じる。ビット・グループが次にＧ_p出力ビットのグ
ループに交換符号化され、遅延Ｄ₂が生じる。Ｄ₂＜Ｄ₁
の場合、イメージ交換符号器は、各入力グループＧを次
の入力グループＧが処理される必要がある以前に、その
対応する出力グループＧ_pに変換できる。この場合、ス
トリーム式イメージ交換符号器の内部メモリ要求は制限
される。しかしながら、Ｄ₂＞Ｄ₁の場合、イメージ交換
符号器は入力ビットを十分に速く処理することができな
い。この後者の場合、連続入力ストリームが供給される
と、イメージ交換符号器の内部メモリ要求が制限無しに
成長する。すなわち、イメージ交換符号器の有限長内部
ＲＡＭバッファがオーバフローする。従って、交換符号
化遅延Ｄ₂が、Ｄ₂＜Ｄ₁を満足することが望まれる。明
らかに、Ｄ₁＝Ｇ／Ｂ_spである。Ｄ₂を見いだすために、
Ｄ_p（Ｓ）をＳビットのイメージの予測イメージ交換符
号化時間とする（Ｄ_p（Ｓ）は実際、イメージ内容及び
寸法などの他のパラメータに依存するが、ここでは表記
上の簡略化のため、Ｄ_p（Ｓ）を使用する）。従って、
Ｄ₂＝Ｄ_p（Ｓ）／（Ｓ／Ｇ）となる。ＲＡＭバッファの
オーバフローを回避するため、グループ交換符号化遅延
は、Ｄ_p（Ｓ）／（Ｓ／Ｇ）＜Ｇ／Ｂ_sp、または次式を
満足しなければならない。

【数６】Ｄ_p（Ｓ）＜Ｓ／Ｂ_sp （条件Ａ）

【００５８】条件Ａが真を維持すると仮定すると、出力
交換符号化グループＧ_pがＤ₁に等しい遅延により、均一
に間隔をあけられる。伝送チャネルは各交換符号化ビッ
ト・グループＧ_pを、時間Ｄ₃＝Ｇ_p／Ｂ_pc内に送信する
ことができる。ケース（ｉ）すなわちＤ₃（ｉ）＜Ｄ₁で
は、各出力グループＧ_pが、次の出力グループが伝送準
備完了となる前に送信され得る。ケース（ｉｉ）すなわ
ちＤ₃（ｉｉ）＞Ｄ₁では、出力伝送リンクは生成ビット
を出力キューを空に維持する程、十分に速く送信するこ
とができない。ケース（ｉｉ）では、交換符号化ビット
の連続ストリームが供給される場合、伝送リンクの出力
キューが制限無しに成長し、有限長リンク・バッファの
オーバフローを生じる。従って、交換符号化出力グルー
プ・サイズにより引き起こされる遅延が、Ｄ₃（ｉ）＜
Ｄ₁であることが所望される。明らかに、Ｄ₃（ｉ）＝Ｇ
_p／Ｂ_pcである。伝送リンクの出力バッファのオーバフ
ローを回避するために、交換符号化出力イメージ・グル
ープ・サイズＧ_pは、Ｇ_p／Ｂ _pc＜Ｇ／Ｂ_sp、または次式
を満足しなければならない。

【数７】 γ＞Ｂ_sp／Ｂ_pc （条件Ｂ）

【００５９】ここで、γ＝グループ・イメージ圧縮率Ｇ
／Ｇ_pであり、これは平均的に、全体的なイメージ圧縮
率に等価であると仮定する。要するに、ストリーム式イ
メージ交換符号器は、条件Ａ及び条件Ｂの両方が満足さ
れる場合にだけ、交換符号化を実行すべきである。プロ
キシ−サーバ間リンクがボトルネックの場合、すなわち
Ｂ_cp＜Ｂ_pcの場合、条件Ｂがγ＞Ｎに軽減される。ここ
でＮは１未満の数である。通常、圧縮率は常に１よりも
大きい。従って、条件Ｂは常に満足される。この場合、
交換符号化が不利にならないために、条件Ａだけが満足
されなければならない。実際、プロキシ−サーバ間リン
クがボトルネックの場合、条件Ｂは交換符号化イメージ
に対して許容される拡張率、すなわち１／γ＜Ｂ_pc／Ｂ
_spの上限を提供するものと解釈される。イメージの拡張
は、例えばＧＩＦからパーム（Palm）・フォーマットへ
の変換などの、フォーマット変換が強要されるとき、時
折必要とされる。前記の式は、こうしたフォーマット変
換がバッファ・オーバフローの機会を増す場合、及びフ
ォーマット変換がバッファ・オーバフローを生じない場
合の判断を可能にする。例えば、Ｂ_sp＝１ｂｐｓ、Ｂ_pc
＝２ｂｐｓ、及びＧ＝１ビットの場合、条件Ｂは、出力
グループＧ_pが最大２ビットに拡張し得ることを示す。
クライアント−プロキシ間リンクがボトルネック、すな
わちＢ_sp＞Ｂ _pcの場合、条件Ｂは、交換符号化が価値あ
るためには、イメージ圧縮率γが、クライアント−プロ
キシ間帯域幅に対するプロキシ−サーバ間帯域幅の比率
よりも、大きくなければならないことを示す。更に、条
件Ａが依然満足されなければならない。

【００６０】条件Ａ及び条件Ｂは、バッファが決してオ
ーバフローを許可されてはならないとする厳格な制限で
ある。当業者であれば、イメージが前記分析において仮
定された連続ストリームではなく、有限長と仮定すれ
ば、緩和された制限が導出され得ることが理解できよ
う。より緩和された制限は、交換符号化のためにより長
い時間を許容し、大して活発でない計算を可能にする。

【００６１】従って、本発明の１態様は、通信ネットワ
ークを介して接続されるクライアント装置とサーバ間の
ブラウジングを容易にする、交換符号化プロキシのため
の方法を提供することである。本方法は、クライアント
装置から、サーバの１つに記憶されるオブジェクトに対
するＨＴＴＰ獲得（GET）要求を受信するステップと、
オブジェクトに対する獲得要求をサーバに転送するステ
ップと、サーバからオブジェクトを受信するステップ
と、クライアント装置のユーザにより指定される選択を
調査するステップと、オブジェクトの内容を調査するス
テップと、通信ネットワーク特性を調査するステップ
と、交換符号化パラメータのセットを選択するステップ
と、オブジェクトの交換符号化形式を形成するステップ
と、交換符号化形式をクライアントに送信するステップ
とを含む。ネットワーク特性を調査するステップは、サ
ーバとプロキシ間の、及びプロキシとクライアント間の
ネットワーク帯域幅を推定するステップと、サーバとプ
ロキシ間の遅延、及びプロキシとクライアント装置間の
遅延を推定するステップと、オブジェクトに対して実行
される交換符号化のレベルに関し、ユーザにフィードバ
ックを提供するステップとを含む。調査するステップ
は、オブジェクトのサイズを決定するステップと、オブ
ジェクトの寸法を決定するステップと、オブジェクトの
圧縮率を計算するステップとを含む。オブジェクトがイ
メージ・タイプの場合、イメージ・オブジェクトの寸法
は、正方形の画素によるイメージの領域により決定さ
れ、圧縮率がイメージ・オブジェクトのｂｐｐ比率によ
り決定される。本発明は、蓄積転送及びストリーム式交
換符号化の両方を可能にし、それにより、オブジェクト
をサーバから受信するステップが完了する前に、交換符
号化形式を形成することを可能にする。この方法はＪＰ
ＥＧ、ＧＩＦ、及び他のイメージ・タイプにも適用可能
である。本発明の別の態様は、オブジェクトの交換符号
化形式を形成するステップが完了する前に、交換符号化
形式を送出することを可能にする。

【００６２】他の重要な幾つかの考慮すべき点が存在す
る。本発明の概念の上述の例は、イメージ及びビデオな
どにとっては、普通である。インターネットの広範な利
用は、ＪＰＥＧ及びＭＰＥＧ圧縮イメージ・データの価
値を示した。音声符号化データもまた伸張され、特殊な
音響効果と混合され、他の音声データと併合され、実領
域において編集及び処理される必要がある。類似の技法
が、他の産業、商業、及び軍事アプリケーションにおい
ても実行される。

【００６３】本発明はプロセス、製造物、装置、システ
ム、アーキテクチャ、またはコンピュータ製品としても
提供される。例えば、本発明は、コンピュータに本発明
の方法を実行するように指示する、コンピュータ読出し
可能プログラム・コード手段を有するコンピュータ使用
可能媒体を含む製造物として実現される。本発明の説明
は、特定のステップの構成に関して述べられたが、本発
明の趣旨及び概念は、他の構成にも適しており、適用可
能である。例えば、ここで述べた実施例はウェブ・ブラ
ウジングだけに関連したが、本発明は任意のブラウザに
適用可能である。主な重点は動的技法に向けられたが、
本発明は静的、準動的及び動的技法の組み合わせと共に
使用され得る。当業者には、ここで開示された実施例の
他の変更も、本発明の趣旨及び範囲から逸れることな
く、可能であることが明らかであろう。従って、これら
の全ての変形及び変更が、本発明の範囲内に含まれるよ
うに意図される。

【００６４】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００６５】（１）通信ネットワークを介して接続され
る複数のクライアント装置と複数のサーバ間のブラウジ
ングを容易にする、交換符号化プロキシのための方法で
あって、前記クライアント装置の１つから、前記サーバ
の１つに記憶されるオブジェクトに対する要求を受信す
るステップと、前記オブジェクトに対する要求を前記サ
ーバの１つに転送するステップと、前記サーバの１つか
ら前記オブジェクトを受信するステップと、前記クライ
アント装置の１つのユーザにより指定される選択を調査
するステップと、前記オブジェクトの内容を調査するス
テップと、通信ネットワーク特性を調査するステップ
と、交換符号化パラメータのセットを選択するステップ
と、前記オブジェクトの交換符号化形式を形成するステ
ップと、前記交換符号化形式を前記クライアント装置の
１つに送信するステップとを含む、方法。 （２）前記ネットワーク特性が帯域幅を含み、前記ネッ
トワーク特性を調査するステップが、前記サーバの１つ
と前記プロキシ間の、及び前記プロキシと前記クライア
ント装置の１つとの間のネットワーク帯域幅を推定する
ステップを含む、前記（１）記載の方法。 （３）前記ネットワーク特性が遅延を含み、前記ネット
ワーク特性を調査するステップが、前記サーバの１つと
前記プロキシ間の遅延、及び前記プロキシと前記クライ
アント装置の１つとの間の遅延を推定するステップを含
む、前記（１）記載の方法。 （４）前記交換符号化形式を形成するために、前記オブ
ジェクトに対して実行される交換符号化のレベルに関す
るフィードバックを、ユーザに提供するステップを含
む、前記（１）記載の方法。 （５）前記調査するステップが、前記オブジェクトのサ
イズを決定するステップを含む、前記（１）記載の方
法。 （６）前記オブジェクトがイメージ・オブジェクトを形
成するイメージ・タイプであり、前記方法が、前記イメ
ージ・オブジェクトの寸法を決定するステップと、前記
イメージ・オブジェクトの圧縮率を計算するステップと
を含む、前記（１）記載の方法。 （７）前記イメージ・オブジェクトの寸法が、正方形の
画素によるイメージの領域により決定され、前記圧縮率
が前記イメージ・オブジェクトのｂｐｐ比率により決定
される、前記（６）記載の方法。 （８）前記交換符号化形式を形成するステップが、動的
適応化を使用する、前記（１）記載の方法。 （９）前記オブジェクトを前記サーバの１つから受信す
るステップが完了する前に、前記交換符号化形式を形成
するステップが開始される、前記（１）記載の方法。 （１０）受信される前記オブジェクトのタイプが、ＪＰ
ＥＧオブジェクトを形成するＪＰＥＧタイプである、前
記（９）記載の方法。 （１１）前記交換符号化形式を形成するステップが、Ｊ
ＰＥＧ−ＪＰＥＧイメージ交換符号化を実行するステッ
プを含み、前記交換符号化形式を送信するステップが、
前記オブジェクトが完了する前に、ＪＰＥＧ符号化出力
イメージ・データの少なくとも１つのＭＣＵの書出しを
開始する、前記（１０）記載の方法。 （１２）前記交換符号化形式を送出するステップが、前
記受信オブジェクトの初期部分の処理後に、且つ前記サ
ーバの１つから前記イメージ・オブジェクトを受信する
ステップが完了する前に開始される、前記（１）記載の
方法。 （１３）前記交換符号化形式を送出するステップが、前
記オブジェクトの交換符号化形式を形成するステップが
完了する前に開始される、前記（１）記載の方法。 （１４）サーバから入手可能なオブジェクトに対するク
ライアントからの要求に応じて、前記サーバから受信さ
れるオブジェクトの交換符号化形式を形成するプロキシ
のための方法であって、前記クライアントのために前記
オブジェクトを交換符号化するためのパラメータを、動
的に適応化するステップと、前記オブジェクトの交換符
号化形式を形成するステップと、前記交換符号化形式を
前記クライアントに送信するステップとを含む、方法。 （１５）前記パラメータを適応化するステップが、前記
オブジェクトの少なくとも１つの特性を決定するステッ
プを含む、前記（１４）記載の方法。 （１６）前記特性の１つが、前記オブジェクトのサイズ
及びタイプに関する情報を提供するオブジェクト・ヘッ
ダである、前記（１５）記載の方法。 （１７）前記オブジェクトのサイズを"size_threshold"
と呼ばれるしきい値パラメータと比較するステップを含
む、前記（１６）記載の方法。 （１８）前記パラメータを適応化するステップが、前記
サーバと前記プロキシ間、及び前記プロキシと前記クラ
イアント間の現ネットワーク特性を収集するステップを
含む、前記（１４）記載の方法。 （１９）前記特性の１つがネットワーク帯域幅であり、
前記適応化するステップが、前記サーバと前記プロキシ
間、及び前記プロキシと前記クライアント間のネットワ
ーク帯域幅を推定するステップを含む、前記（１８）記
載の方法。 （２０）前記交換符号化形式が前記推定帯域幅に依存す
る、前記（１９）記載の方法。 （２１）前記適応化するステップが、ユーザの選択を取
り出すステップを含み、前記交換符号化形式が前記選択
に依存する、前記（１４）記載の方法。 （２２）前記適応化するステップが、前記オブジェクト
の内容を調査するステップを含む、前記（１４）記載の
方法。 （２３）前記オブジェクトがイメージ・オブジェクトを
形成するイメージ・タイプであり、前記イメージ・オブ
ジェクトの内容を調査するステップが、前記イメージの
寸法を決定するステップを含む、前記（２２）記載の方
法。 （２４）前記適応化するステップが、前記イメージ・オ
ブジェクトの圧縮率の決定に依存する、前記（２３）記
載の方法。 （２５）前記イメージ・オブジェクトのタイプがＧＩＦ
であり、前記適応化するステップが、前記圧縮率と"gif
_threshold"と呼ばれる所定のポリシしきい値の比較に
依存する、前記（２４）記載の方法。 （２６）前記オブジェクトの前記交換符号化形式の少な
くとも１つのパラメータを予測するステップを含む、前
記（１４）記載の方法。 （２７）前記交換符号化形式が、前記オブジェクトのオ
リジナル形式と同一である、前記（２６）記載の方法。 （２８）前記パラメータの少なくとも１つが、前記交換
符号化形式のサイズを含む、前記（２６）記載の方法。 （２９）前記パラメータの少なくとも１つが、前記オブ
ジェクトを交換符号化するのに費やされる時間を含む、
前記（２６）記載の方法。 （３０）オブジェクトの交換符号化形式のパラメータを
予測する方法であって、前記オブジェクトが初期サイズ
及び寸法を有し、前記オブジェクトに対するクライアン
トからの要求に応じて、前記オブジェクトがサーバから
受信されるものにおいて、前記オブジェクトのｂｐｐ比
率を計算するステップと、複数の以前に交換符号化され
たオブジェクトの統計のセットを収集するステップと、
前記統計のセット及び前記ｂｐｐ比率を使用し、前記パ
ラメータを予測するステップとを含む、方法。 （３１）前記パラメータの少なくとも１つがサイズであ
り、前記統計のセットが複数の以前に交換符号化された
オブジェクトの統計のサイズを含む、前記（３０）記載
の方法。 （３２）前記オブジェクトがイメージ・タイプであり、
前記統計のセットがイメージ品質を含む、前記（３０）
記載の方法。 （３３）前記複数の以前に交換符号化されたオブジェク
トが、イメージの所定のベンチマーク一式から選択され
る、前記（３２）記載の方法。 （３４）前記予測するステップが、現交換符号化オブジ
ェクトの統計を用いて、前記統計のセットを動的に更新
するステップを含む、前記（３１）記載の方法。 （３５）前記パラメータの少なくとも１つが、オブジェ
クトの交換符号化形式を形成する期間であり、前記統計
のセットが、複数の以前に交換符号化されたオブジェク
トを形成する期間を含む、前記（３０）記載の方法。 （３６）通信ネットワークを介して接続される複数のク
ライアント装置と複数のサーバ間のブラウジングを容易
にする、交換符号化プロキシ・システムであって、前記
クライアント装置の１つから、前記サーバの１つに記憶
されるオブジェクトに対する要求を受信するＨＴＴＰプ
ロキシ・エンジンと、交換符号化のためのパラメータの
セットを用いて、前記オブジェクトの交換符号化形式を
形成するオブジェクト交換符号器と、交換符号化のため
の前記パラメータのセットを決定する動的ポリシ・モジ
ュールと、前記オブジェクトの特性を収集するイメージ
・サイズ及び遅延予測器モジュールと、前記クライアン
ト装置の１つのユーザにより指定される品質選択を収集
するユーザ選択モジュールと、有効ネットワーク帯域幅
を推定する帯域幅推定モジュールとを含み、前記動的ポ
リシ・モジュールがユーザの満足を改善するために、前
記イメージ・サイズ及び遅延予測器モジュール、前記ユ
ーザ選択モジュール、及び前記帯域幅推定モジュールか
ら受信される入力を用いて、交換符号化のための前記パ
ラメータを動的に調整し、前記交換符号化プロキシ・シ
ステムが、実行される交換符号化のレベルに関するフィ
ードバックをユーザに提供する、システム。 （３７）前記ユーザ選択モジュールが、前記クライアン
ト装置の１つの表示サイズ、解像度、及びＣＰＵスピー
ドなどの特性を収集するステップと、前記特性を前記動
的ポリシ・モジュールに提供するステップとを含む、前
記（３６）記載のシステム。 （３８）前記帯域幅推定モジュールが、前記サーバの１
つと前記プロキシ間で、以前に確立されたネットワーク
接続のトレースを収集するステップと、前記プロキシと
前記クライアント装置の１つとの間で、以前に確立され
たネットワーク接続のトレースを収集するステップと、
収集された前記トレースに対して統計分析を実行するこ
とにより、前記オブジェクトのダウンロード時間を推定
するステップとを含む、前記（３６）記載のシステム。 （３９）前記サーバの１つと前記プロキシ間の帯域幅を
推定するために使用される統計分析が、収集された前記
トレースから決定される、以前にフェッチされたオブジ
ェクトのダウンロード時間の中央値、平均またはモード
などの統計指標の計算にもとづき実行される、前記（３
８）記載のシステム。 （４０）前記プロキシと前記クライアント装置の１つと
の間の帯域幅を推定するために使用される統計分析が、
前記プロキシと当該クライアント装置間の全ての活動状
態の接続の総帯域幅の計算にもとづき実行される、前記
（３８）記載のシステム。 （４１）前記クライアント装置の１つの表示装置上に、
ユーザ指定選択を収集するためのスライド・バーを表示
するステップを含む、前記（３６）記載のシステム。 （４２）前記クライアント装置の１つのユーザが、スラ
イド・バーを有するグラフィカル・ユーザ・インタフェ
ースを使用することにより、ダウンロード時間とデータ
品質間のトレードオフを指定できる、前記（３６）記載
のシステム。 （４３）前記クライアント装置の１つのユーザが、スラ
イド・バーを有するグラフィカル・ユーザ・インタフェ
ースを使用することにより、ダウンロード時間とイメー
ジ品質間のトレードオフを指定でき、カラーまたはグレ
ースケールを所望の出力形式として選択するための特定
のスイッチを含む、前記（４１）記載のシステム。 （４４）前記クライアント装置の１つのユーザが、スラ
イド・バーを有するグラフィカル・ユーザ・インタフェ
ースを使用することにより、前記システムが自動的にデ
ータ品質（従ってデータ・ダウンロード・サイズ）を低
下し、当該クライアントへの帯域幅の動的変化を補償す
るように、目標応答時間を維持する要求を指定できる、
前記（４１）記載のシステム。 （４５）前記グラフィカル・ユーザ・インタフェースの
前記スライド・バーが、前記交換符号化パラメータの最
適な選択をユーザに示すための出力インタフェースとし
ても使用される、前記（４１）記載のシステム。 （４６）交換符号化プロキシにおいて、オブジェクトの
交換符号化形式の動的適応化を指示する、コンピュータ
読出し可能プログラム・コード手段を有するコンピュー
タ使用可能媒体を含む製品であって、前記コンピュータ
読出し可能プログラム・コード手段が、ユーザに関連付
けられるオブジェクトをサーバから受信するように、コ
ンピュータに指示する手段と、前記オブジェクトのパラ
メータを決定するように、前記コンピュータに指示する
手段と、ユーザの選択を取り出すように、前記コンピュ
ータに指示する手段と、現ネットワーク特性を収集する
ように、前記コンピュータに指示する手段と、交換符号
化ポリシしきい値を獲得するように、前記コンピュータ
に指示する手段と、前記オブジェクト・パラメータ、前
記ユーザ選択、前記ネットワーク特性、及び前記ポリシ
しきい値にもとづき、ポリシ決定を実行するように、前
記コンピュータに指示する手段と、交換符号化オブジェ
クトを形成するように、前記コンピュータに指示する手
段と、前記オブジェクトに実行される交換符号化のレベ
ルのフィードバックを、ユーザに提供するように、前記
コンピュータに指示する手段と、交換符号化オブジェク
トをユーザに送信するように、前記コンピュータに指示
する手段とを含む、製品。 （４７）通信ネットワークを介して接続される複数のク
ライアント装置と複数のサーバ間のブラウジングを容易
にするように、交換符号化プロキシに指示する、コンピ
ュータ読出し可能プログラム・コード手段を有するコン
ピュータ使用可能媒体を含む製品であって、前記コンピ
ュータ読出し可能プログラム・コード手段が、前記クラ
イアント装置の１つから、前記サーバの１つに記憶され
るオブジェクトに対する要求を受信するように、コンピ
ュータに指示する手段と、前記オブジェクトに対する要
求を前記サーバの１つに転送するように、前記コンピュ
ータに指示する手段と、前記サーバの１つから前記オブ
ジェクトを受信するように、前記コンピュータに指示す
る手段と、前記クライアント装置の１つのユーザにより
指定される選択を調査するように、前記コンピュータに
指示する手段と、前記オブジェクトの内容を調査するよ
うに、前記コンピュータに指示する手段と、通信ネット
ワーク特性を調査するように、前記コンピュータに指示
する手段と、交換符号化パラメータのセットを選択する
ように、前記コンピュータに指示する手段と、前記オブ
ジェクトの交換符号化形式を形成するように、前記コン
ピュータに指示する手段と、前記交換符号化形式を前記
クライアント装置の１つに送信するように、前記コンピ
ュータに指示する手段とを含む、製品。 （４８）前記コンピュータ読出し可能プログラム・コー
ド手段が、前記交換符号化形式を形成するために、前記
オブジェクトに対して実行される交換符号化のレベルに
関するフィードバックをユーザに提供するように、前記
コンピュータに指示する手段を含む、前記（４７）記載
の製品。 （４９）前記コンピュータ読出し可能プログラム・コー
ド手段が、前記オブジェクトの寸法を決定するように、
前記コンピュータに指示する手段と、前記オブジェクト
の圧縮率を計算するように、前記コンピュータに指示す
る手段とを含む、前記（４７）記載の製品。 （５０）前記コンピュータ読出し可能プログラム・コー
ド手段が、前記オブジェクトを前記サーバの１つから受
信するステップが完了する前に、前記交換符号化形式を
形成するステップを開始するように、前記コンピュータ
に指示する手段を含む、前記（４７）記載の方法。 （５１）サーバから入手可能なオブジェクトに対するク
ライアントからの要求に応じて、前記サーバから受信さ
れるオブジェクトの交換符号化形式を形成するように、
プロキシに指示するコンピュータ読出し可能プログラム
・コード手段を有する、コンピュータ使用可能媒体を含
むコンピュータ・プログラム製品であって、前記コンピ
ュータ・プログラム・コード手段が、前記クライアント
のために前記オブジェクトを交換符号化するためのパラ
メータを動的に適応化するように、コンピュータに指示
する手段と、前記オブジェクトの交換符号化形式を形成
するように、前記コンピュータに指示する手段と、前記
交換符号化形式を前記クライアントに送信するように、
前記コンピュータに指示する手段とを含む、コンピュー
タ・プログラム製品。 （５２）前記コンピュータ・プログラム・コード手段
が、前記サーバと前記プロキシ間、及び前記プロキシと
前記クライアント間の現ネットワーク特性を収集するよ
うに、前記コンピュータに指示する手段を含む、前記
（５１）記載のコンピュータ・プログラム製品。 （５３）前記コンピュータ・プログラム・コード手段
が、推定帯域幅及びユーザ選択にもとづき、交換符号化
のためのパラメータを適応化するように、前記コンピュ
ータに指示する手段を含む、前記（５２）記載のコンピ
ュータ・プログラム製品。 （５４）オブジェクトの交換符号化形式のパラメータを
予測する方法を実行する、マシンにより実行可能な命令
のプログラムを実現するマシンにより読出し可能なプロ
グラム記憶装置であって、前記オブジェクトが初期サイ
ズ及び寸法を有し、前記オブジェクトに対するクライア
ントからの要求に応じて、前記オブジェクトがサーバか
ら受信されるものにおいて、前記方法が、前記オブジェ
クトのｂｐｐ比率を計算するステップと、複数の以前に
交換符号化されたオブジェクトの統計のセットを収集す
るステップと、前記統計のセット及び前記ｂｐｐ比率を
使用し、前記パラメータを予測するステップとを含む、
プログラム記憶装置。 （５５）前記予測するステップが、現交換符号化オブジ
ェクトの統計を用いて、前記統計のセットを更新するス
テップを含む、前記（５４）記載のプログラム記憶装
置。

【図面の簡単な説明】

【図１】様々なリンク及び様々なクライアント装置を有
する交換符号化プロキシ状況を示す図である。

【図２】ユーザ指定選択及び静的ポリシにもとづき、オ
ブジェクトを変換するために使用される交換符号化プロ
キシのブロック図である。

【図３】本発明に従い、イメージ・サイズ予測器、帯域
幅推定器、動的ポリシ・モジュール、及びユーザ・フィ
ードバック発生器を含むように変更された、交換符号化
プロキシのブロック図である。

【図４】本発明に従い、キャッシング・モジュール及び
交換符号化モジュールを有するＨＴＴＰプロキシのブロ
ック図である。

【図５】本発明に従う交換符号化動的ポリシ・モジュー
ルのフロー図である。

【図６】本発明に従う交換符号化プロキシを使用する、
ウェブ要求−応答サイクルを示す図である。

【図７】本発明に従い交換符号化が有用である状態を示
す図である。

【図８】本発明に従うポリシ関数のフロー図である。

【図９】本発明に従うイメージ・サイズ予測モジュール
のブロック図である。

【図１０】本発明に従う帯域幅予測モジュールのブロッ
ク図である。

【図１１】本発明に従う入力／フィードバック・ユーザ
・インタフェースを示す図である。

【図１２】本発明に従うストリーム式交換符号化のタイ
ミング図である。

【符号の説明】

１００ 交換符号化プロキシ状況 １３０、１３１、１３２、１３３、１３４、２３０ ク
ライアント １６０、１６１、１６２、１６３、１６４ リンク １９０ 交換符号化プロキシ ２１０ ウェブ・サーバ ２２０ ＨＴＴＰプロキシ・エンジン ２２２ ＨＴＴＰ要求 ２２６ 応答データ ２４０ 交換符号化モジュール ２５０ 静的ポリシ・モジュール ２６０ ユーザ指定選択 ２６５ 経路 ３７０ 動的ポリシ・モジュール ３７５ 遅延予測器 ３８０ 帯域幅推定器 ３９０ ユーザ・フィードバック・プロバイダ ４００ 交換符号化ＨＴＴＰプロキシ・システム ４１０ 多重解像度キャッシュ ４２０ データ経路 ５６５、８００ ポリシ関数 ６２０ オリジナル・イメージ ６３０ 出力イメージ ６５０ 遅延Ｄ_x（Ｓ） ６７０ サイズＳ ６８０ サイズＳ_x（Ｓ） １０１０ トレース・モニタ １０２０ 統計分析器

フロントページの続き (72)発明者 プラビン・バグワット アメリカ合衆国10583、ニューヨーク州ス カーズデール、ナンバー６ ティエヌ、モ ロー・アベニュー 40 (72)発明者 リチャード・イェウ−ウェイン・ハン アメリカ合衆国10023、ニューヨーク州ニ ューヨーク、ナンバー３ エフ、セブンテ ィ・フィフス・ストリート、ウエスト 34 (72)発明者 リチャード・オービル・ルメアー アメリカ合衆国10598、ニューヨーク州ヨ ークタウン・ハイツ、カリフォルニア・ロ ード 138 (72)発明者 トッド・ウィリアム・ムマート アメリカ合衆国10541、ニューヨーク州マ ホパック、ドレプス・ドライブ 18 (72)発明者 ジェームス・ルバス アメリカ合衆国10598、ニューヨーク州ヨ ークタウン・ハイツ、ワイルドウッド・コ ート 791

Claims (55)

【特許請求の範囲】
1. 【請求項１】通信ネットワークを介して接続される複数
   のクライアント装置と複数のサーバ間のブラウジングを
   容易にする、交換符号化プロキシのための方法であっ
   て、 前記クライアント装置の１つから、前記サーバの１つに
   記憶されるオブジェクトに対する要求を受信するステッ
   プと、 前記オブジェクトに対する要求を前記サーバの１つに転
   送するステップと、 前記サーバの１つから前記オブジェクトを受信するステ
   ップと、 前記クライアント装置の１つのユーザにより指定される
   選択を調査するステップと、 前記オブジェクトの内容を調査するステップと、 通信ネットワーク特性を調査するステップと、 交換符号化パラメータのセットを選択するステップと、 前記オブジェクトの交換符号化形式を形成するステップ
   と、 前記交換符号化形式を前記クライアント装置の１つに送
   信するステップとを含む、方法。
2. 【請求項２】前記ネットワーク特性が帯域幅を含み、前
   記ネットワーク特性を調査するステップが、前記サーバ
   の１つと前記プロキシ間の、及び前記プロキシと前記ク
   ライアント装置の１つとの間のネットワーク帯域幅を推
   定するステップを含む、請求項１記載の方法。
3. 【請求項３】前記ネットワーク特性が遅延を含み、前記
   ネットワーク特性を調査するステップが、前記サーバの
   １つと前記プロキシ間の遅延、及び前記プロキシと前記
   クライアント装置の１つとの間の遅延を推定するステッ
   プを含む、請求項１記載の方法。
4. 【請求項４】前記交換符号化形式を形成するために、前
   記オブジェクトに対して実行される交換符号化のレベル
   に関するフィードバックを、ユーザに提供するステップ
   を含む、請求項１記載の方法。
5. 【請求項５】前記調査するステップが、前記オブジェク
   トのサイズを決定するステップを含む、請求項１記載の
   方法。
6. 【請求項６】前記オブジェクトがイメージ・オブジェク
   トを形成するイメージ・タイプであり、前記方法が、 前記イメージ・オブジェクトの寸法を決定するステップ
   と、 前記イメージ・オブジェクトの圧縮率を計算するステッ
   プとを含む、請求項１記載の方法。
7. 【請求項７】前記イメージ・オブジェクトの寸法が、正
   方形の画素によるイメージの領域により決定され、前記
   圧縮率が前記イメージ・オブジェクトのｂｐｐ比率によ
   り決定される、請求項６記載の方法。
8. 【請求項８】前記交換符号化形式を形成するステップ
   が、動的適応化を使用する、請求項１記載の方法。
9. 【請求項９】前記オブジェクトを前記サーバの１つから
   受信するステップが完了する前に、前記交換符号化形式
   を形成するステップが開始される、請求項１記載の方
   法。
10. 【請求項１０】受信される前記オブジェクトのタイプ
    が、ＪＰＥＧオブジェクトを形成するＪＰＥＧタイプで
    ある、請求項９記載の方法。
11. 【請求項１１】前記交換符号化形式を形成するステップ
    が、ＪＰＥＧ−ＪＰＥＧイメージ交換符号化を実行する
    ステップを含み、前記交換符号化形式を送信するステッ
    プが、前記オブジェクトが完了する前に、ＪＰＥＧ符号
    化出力イメージ・データの少なくとも１つのＭＣＵの書
    出しを開始する、請求項１０記載の方法。
12. 【請求項１２】前記交換符号化形式を送出するステップ
    が、前記受信オブジェクトの初期部分の処理後に、且つ
    前記サーバの１つから前記イメージ・オブジェクトを受
    信するステップが完了する前に開始される、請求項１記
    載の方法。
13. 【請求項１３】前記交換符号化形式を送出するステップ
    が、前記オブジェクトの交換符号化形式を形成するステ
    ップが完了する前に開始される、請求項１記載の方法。
14. 【請求項１４】サーバから入手可能なオブジェクトに対
    するクライアントからの要求に応じて、前記サーバから
    受信されるオブジェクトの交換符号化形式を形成するプ
    ロキシのための方法であって、 前記クライアントのために前記オブジェクトを交換符号
    化するためのパラメータを、動的に適応化するステップ
    と、 前記オブジェクトの交換符号化形式を形成するステップ
    と、 前記交換符号化形式を前記クライアントに送信するステ
    ップとを含む、方法。
15. 【請求項１５】前記パラメータを適応化するステップ
    が、前記オブジェクトの少なくとも１つの特性を決定す
    るステップを含む、請求項１４記載の方法。
16. 【請求項１６】前記特性の１つが、前記オブジェクトの
    サイズ及びタイプに関する情報を提供するオブジェクト
    ・ヘッダである、請求項１５記載の方法。
17. 【請求項１７】前記オブジェクトのサイズを"size_thre
    shold"と呼ばれるしきい値パラメータと比較するステッ
    プを含む、請求項１６記載の方法。
18. 【請求項１８】前記パラメータを適応化するステップ
    が、前記サーバと前記プロキシ間、及び前記プロキシと
    前記クライアント間の現ネットワーク特性を収集するス
    テップを含む、請求項１４記載の方法。
19. 【請求項１９】前記特性の１つがネットワーク帯域幅で
    あり、前記適応化するステップが、前記サーバと前記プ
    ロキシ間、及び前記プロキシと前記クライアント間のネ
    ットワーク帯域幅を推定するステップを含む、請求項１
    ８記載の方法。
20. 【請求項２０】前記交換符号化形式が前記推定帯域幅に
    依存する、請求項１９記載の方法。
21. 【請求項２１】前記適応化するステップが、ユーザの選
    択を取り出すステップを含み、前記交換符号化形式が前
    記選択に依存する、請求項１４記載の方法。
22. 【請求項２２】前記適応化するステップが、前記オブジ
    ェクトの内容を調査するステップを含む、請求項１４記
    載の方法。
23. 【請求項２３】前記オブジェクトがイメージ・オブジェ
    クトを形成するイメージ・タイプであり、前記イメージ
    ・オブジェクトの内容を調査するステップが、前記イメ
    ージの寸法を決定するステップを含む、請求項２２記載
    の方法。
24. 【請求項２４】前記適応化するステップが、前記イメー
    ジ・オブジェクトの圧縮率の決定に依存する、請求項２
    ３記載の方法。
25. 【請求項２５】前記イメージ・オブジェクトのタイプが
    ＧＩＦであり、前記適応化するステップが、前記圧縮率
    と"gif_threshold"と呼ばれる所定のポリシしきい値の
    比較に依存する、請求項２４記載の方法。
26. 【請求項２６】前記オブジェクトの前記交換符号化形式
    の少なくとも１つのパラメータを予測するステップを含
    む、請求項１４記載の方法。
27. 【請求項２７】前記交換符号化形式が、前記オブジェク
    トのオリジナル形式と同一である、請求項２６記載の方
    法。
28. 【請求項２８】前記パラメータの少なくとも１つが、前
    記交換符号化形式のサイズを含む、請求項２６記載の方
    法。
29. 【請求項２９】前記パラメータの少なくとも１つが、前
    記オブジェクトを交換符号化するのに費やされる時間を
    含む、請求項２６記載の方法。
30. 【請求項３０】オブジェクトの交換符号化形式のパラメ
    ータを予測する方法であって、前記オブジェクトが初期
    サイズ及び寸法を有し、前記オブジェクトに対するクラ
    イアントからの要求に応じて、前記オブジェクトがサー
    バから受信されるものにおいて、 前記オブジェクトのｂｐｐ比率を計算するステップと、 複数の以前に交換符号化されたオブジェクトの統計のセ
    ットを収集するステップと、 前記統計のセット及び前記ｂｐｐ比率を使用し、前記パ
    ラメータを予測するステップとを含む、方法。
31. 【請求項３１】前記パラメータの少なくとも１つがサイ
    ズであり、前記統計のセットが複数の以前に交換符号化
    されたオブジェクトの統計のサイズを含む、請求項３０
    記載の方法。
32. 【請求項３２】前記オブジェクトがイメージ・タイプで
    あり、前記統計のセットがイメージ品質を含む、請求項
    ３０記載の方法。
33. 【請求項３３】前記複数の以前に交換符号化されたオブ
    ジェクトが、イメージの所定のベンチマーク一式から選
    択される、請求項３２記載の方法。
34. 【請求項３４】前記予測するステップが、現交換符号化
    オブジェクトの統計を用いて、前記統計のセットを動的
    に更新するステップを含む、請求項３１記載の方法。
35. 【請求項３５】前記パラメータの少なくとも１つが、オ
    ブジェクトの交換符号化形式を形成する期間であり、前
    記統計のセットが、複数の以前に交換符号化されたオブ
    ジェクトを形成する期間を含む、請求項３０記載の方
    法。
36. 【請求項３６】通信ネットワークを介して接続される複
    数のクライアント装置と複数のサーバ間のブラウジング
    を容易にする、交換符号化プロキシ・システムであっ
    て、 前記クライアント装置の１つから、前記サーバの１つに
    記憶されるオブジェクトに対する要求を受信するＨＴＴ
    Ｐプロキシ・エンジンと、 交換符号化のためのパラメータのセットを用いて、前記
    オブジェクトの交換符号化形式を形成するオブジェクト
    交換符号器と、 交換符号化のための前記パラメータのセットを決定する
    動的ポリシ・モジュールと、 前記オブジェクトの特性を収集するイメージ・サイズ及
    び遅延予測器モジュールと、 前記クライアント装置の１つのユーザにより指定される
    品質選択を収集するユーザ選択モジュールと、 有効ネットワーク帯域幅を推定する帯域幅推定モジュー
    ルとを含み、前記動的ポリシ・モジュールがユーザの満
    足を改善するために、前記イメージ・サイズ及び遅延予
    測器モジュール、前記ユーザ選択モジュール、及び前記
    帯域幅推定モジュールから受信される入力を用いて、交
    換符号化のための前記パラメータを動的に調整し、前記
    交換符号化プロキシ・システムが、実行される交換符号
    化のレベルに関するフィードバックをユーザに提供す
    る、システム。
37. 【請求項３７】前記ユーザ選択モジュールが、 前記クライアント装置の１つの表示サイズ、解像度、及
    びＣＰＵスピードなどの特性を収集するステップと、 前記特性を前記動的ポリシ・モジュールに提供するステ
    ップとを含む、請求項３６記載のシステム。
38. 【請求項３８】前記帯域幅推定モジュールが、 前記サーバの１つと前記プロキシ間で、以前に確立され
    たネットワーク接続のトレースを収集するステップと、 前記プロキシと前記クライアント装置の１つとの間で、
    以前に確立されたネットワーク接続のトレースを収集す
    るステップと、 収集された前記トレースに対して統計分析を実行するこ
    とにより、前記オブジェクトのダウンロード時間を推定
    するステップとを含む、請求項３６記載のシステム。
39. 【請求項３９】前記サーバの１つと前記プロキシ間の帯
    域幅を推定するために使用される統計分析が、収集され
    た前記トレースから決定される、以前にフェッチされた
    オブジェクトのダウンロード時間の中央値、平均または
    モードなどの統計指標の計算にもとづき実行される、請
    求項３８記載のシステム。
40. 【請求項４０】前記プロキシと前記クライアント装置の
    １つとの間の帯域幅を推定するために使用される統計分
    析が、前記プロキシと当該クライアント装置間の全ての
    活動状態の接続の総帯域幅の計算にもとづき実行され
    る、請求項３８記載のシステム。
41. 【請求項４１】前記クライアント装置の１つの表示装置
    上に、ユーザ指定選択を収集するためのスライド・バー
    を表示するステップを含む、請求項３６記載のシステ
    ム。
42. 【請求項４２】前記クライアント装置の１つのユーザ
    が、スライド・バーを有するグラフィカル・ユーザ・イ
    ンタフェースを使用することにより、ダウンロード時間
    とデータ品質間のトレードオフを指定できる、請求項３
    ６記載のシステム。
43. 【請求項４３】前記クライアント装置の１つのユーザ
    が、スライド・バーを有するグラフィカル・ユーザ・イ
    ンタフェースを使用することにより、ダウンロード時間
    とイメージ品質間のトレードオフを指定でき、カラーま
    たはグレースケールを所望の出力形式として選択するた
    めの特定のスイッチを含む、請求項４１記載のシステ
    ム。
44. 【請求項４４】前記クライアント装置の１つのユーザ
    が、スライド・バーを有するグラフィカル・ユーザ・イ
    ンタフェースを使用することにより、前記システムが自
    動的にデータ品質（従ってデータ・ダウンロード・サイ
    ズ）を低下し、当該クライアントへの帯域幅の動的変化
    を補償するように、目標応答時間を維持する要求を指定
    できる、請求項４１記載のシステム。
45. 【請求項４５】前記グラフィカル・ユーザ・インタフェ
    ースの前記スライド・バーが、前記交換符号化パラメー
    タの最適な選択をユーザに示すための出力インタフェー
    スとしても使用される、請求項４１記載のシステム。
46. 【請求項４６】交換符号化プロキシにおいて、オブジェ
    クトの交換符号化形式の動的適応化を指示する、コンピ
    ュータ読出し可能プログラム・コード手段を有するコン
    ピュータ使用可能媒体を含む製品であって、前記コンピ
    ュータ読出し可能プログラム・コード手段が、 ユーザに関連付けられるオブジェクトをサーバから受信
    するように、コンピュータに指示する手段と、 前記オブジェクトのパラメータを決定するように、前記
    コンピュータに指示する手段と、 ユーザの選択を取り出すように、前記コンピュータに指
    示する手段と、 現ネットワーク特性を収集するように、前記コンピュー
    タに指示する手段と、 交換符号化ポリシしきい値を獲得するように、前記コン
    ピュータに指示する手段と、 前記オブジェクト・パラメータ、前記ユーザ選択、前記
    ネットワーク特性、及び前記ポリシしきい値にもとづ
    き、ポリシ決定を実行するように、前記コンピュータに
    指示する手段と、 交換符号化オブジェクトを形成するように、前記コンピ
    ュータに指示する手段と、 前記オブジェクトに実行される交換符号化のレベルのフ
    ィードバックを、ユーザに提供するように、前記コンピ
    ュータに指示する手段と、 交換符号化オブジェクトをユーザに送信するように、前
    記コンピュータに指示する手段とを含む、製品。
47. 【請求項４７】通信ネットワークを介して接続される複
    数のクライアント装置と複数のサーバ間のブラウジング
    を容易にするように、交換符号化プロキシに指示する、
    コンピュータ読出し可能プログラム・コード手段を有す
    るコンピュータ使用可能媒体を含む製品であって、前記
    コンピュータ読出し可能プログラム・コード手段が、 前記クライアント装置の１つから、前記サーバの１つに
    記憶されるオブジェクトに対する要求を受信するよう
    に、コンピュータに指示する手段と、 前記オブジェクトに対する要求を前記サーバの１つに転
    送するように、前記コンピュータに指示する手段と、 前記サーバの１つから前記オブジェクトを受信するよう
    に、前記コンピュータに指示する手段と、 前記クライアント装置の１つのユーザにより指定される
    選択を調査するように、前記コンピュータに指示する手
    段と、 前記オブジェクトの内容を調査するように、前記コンピ
    ュータに指示する手段と、 通信ネットワーク特性を調査するように、前記コンピュ
    ータに指示する手段と、 交換符号化パラメータのセットを選択するように、前記
    コンピュータに指示する手段と、 前記オブジェクトの交換符号化形式を形成するように、
    前記コンピュータに指示する手段と、 前記交換符号化形式を前記クライアント装置の１つに送
    信するように、前記コンピュータに指示する手段とを含
    む、製品。
48. 【請求項４８】前記コンピュータ読出し可能プログラム
    ・コード手段が、前記交換符号化形式を形成するため
    に、前記オブジェクトに対して実行される交換符号化の
    レベルに関するフィードバックをユーザに提供するよう
    に、前記コンピュータに指示する手段を含む、請求項４
    ７記載の製品。
49. 【請求項４９】前記コンピュータ読出し可能プログラム
    ・コード手段が、 前記オブジェクトの寸法を決定するように、前記コンピ
    ュータに指示する手段と、 前記オブジェクトの圧縮率を計算するように、前記コン
    ピュータに指示する手段とを含む、請求項４７記載の製
    品。
50. 【請求項５０】前記コンピュータ読出し可能プログラム
    ・コード手段が、前記オブジェクトを前記サーバの１つ
    から受信するステップが完了する前に、前記交換符号化
    形式を形成するステップを開始するように、前記コンピ
    ュータに指示する手段を含む、請求項４７記載の方法。
51. 【請求項５１】サーバから入手可能なオブジェクトに対
    するクライアントからの要求に応じて、前記サーバから
    受信されるオブジェクトの交換符号化形式を形成するよ
    うに、プロキシに指示するコンピュータ読出し可能プロ
    グラム・コード手段を有する、コンピュータ使用可能媒
    体を含むコンピュータ・プログラム製品であって、前記
    コンピュータ・プログラム・コード手段が、 前記クライアントのために前記オブジェクトを交換符号
    化するためのパラメータを動的に適応化するように、コ
    ンピュータに指示する手段と、 前記オブジェクトの交換符号化形式を形成するように、
    前記コンピュータに指示する手段と、 前記交換符号化形式を前記クライアントに送信するよう
    に、前記コンピュータに指示する手段とを含む、コンピ
    ュータ・プログラム製品。
52. 【請求項５２】前記コンピュータ・プログラム・コード
    手段が、前記サーバと前記プロキシ間、及び前記プロキ
    シと前記クライアント間の現ネットワーク特性を収集す
    るように、前記コンピュータに指示する手段を含む、請
    求項５１記載のコンピュータ・プログラム製品。
53. 【請求項５３】前記コンピュータ・プログラム・コード
    手段が、推定帯域幅及びユーザ選択にもとづき、交換符
    号化のためのパラメータを適応化するように、前記コン
    ピュータに指示する手段を含む、請求項５２記載のコン
    ピュータ・プログラム製品。
54. 【請求項５４】オブジェクトの交換符号化形式のパラメ
    ータを予測する方法を実行する、マシンにより実行可能
    な命令のプログラムを実現するマシンにより読出し可能
    なプログラム記憶装置であって、前記オブジェクトが初
    期サイズ及び寸法を有し、前記オブジェクトに対するク
    ライアントからの要求に応じて、前記オブジェクトがサ
    ーバから受信されるものにおいて、前記方法が、 前記オブジェクトのｂｐｐ比率を計算するステップと、 複数の以前に交換符号化されたオブジェクトの統計のセ
    ットを収集するステップと、 前記統計のセット及び前記ｂｐｐ比率を使用し、前記パ
    ラメータを予測するステップとを含む、プログラム記憶
    装置。
55. 【請求項５５】前記予測するステップが、現交換符号化
    オブジェクトの統計を用いて、前記統計のセットを更新
    するステップを含む、請求項５４記載のプログラム記憶
    装置。