キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構

全文

(1)Vol. 43. No. 1. 情報処理学会論文誌. Jan. 2002. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構中下. 野條. 真. 賢† 司††. 春本要†† 西尾章治郎†. インターネットの普及とともに，WWW（ World Wide Web ）は情報コンテンツの提供手段として広く利用されている．WWW では，画像を代表とする多くのインラインオブジェクトをページに埋め込むことにより，視覚的効果の高い情報を提供できる．通常，これらのインラインオブジェクトは，配送された順序でブラウザ上に表示されるため，ユーザが電話回線などの低速リンクを利用してアクセスしている場合など，配送に時間のかかる状況では，その配送順序がユーザに与える影響は大きい．筆者らの研究グループはこの点に着目し，情報提供者がこれらの配送順序を制御できるインラインオブジェクト配送順序制御機構を提案している．しかし，これまでの配送順序制御機構の実現においては，現在インターネット上で重要な役割を果たしているキャッシングプロキシの存在を考慮していなかった．本論文では，まず，キャッシングプロキシが存在する場合の配送順序制御機構の実現について考察し，効率的に配送順序制御を実現できる配送手法を提案する．次に，提案手法の性能を分析し，実測評価によってその有効性を示す．. An Effective Web Page Transmission with Transmission Order Control of Inline Objects Via a Caching Proxy Tadashi Nakano,† Kaname Harumoto,† Shinji Shimojo†† and Shojiro Nishio † Due to the increasing popularity of the Internet, the WWW (World Wide Web) has become the most popular way to distribute multimedia contents. In the WWW, impressive information can be provided by embedding a large number of inline objects such as images in a Web page. Since these inline objects are generally presented on a Web browser in the transmission order, the order of inline objects becomes very important, especially for users accessing the Internet with a low-speed link such as a dial-up line. Focusing on this point, we have proposed a web page transmission mechanism with transmission order control of inline objects. However, the behavior of caching proxy has not been considered in the proposed mechanism. In this paper, we consider how a caching proxy should behave in the mechanism, and then extend the mechanism. We also analyze the potential benefit of the extended mechanism, and verify it by performance evaluation in an experimental environment.. 画像，BGM などのインラインオブジェクトを多数含. 1. はじめに. めることにより，視覚的効果の高い情報を提供できる．. 現在，インターネットの急速な普及により，オンラ. しかし，クライアントのネットワーク帯域幅が狭い場. インショッピングやインターネット広告などの電子商. 合，ページの配送に長い時間が必要となるため，ユー. 取引の基盤として，WWW（ World Wide Web ）が. ザによって途中で転送を中断される可能性がある．こ. 広く利用されている．WWW では，ページの中にテ. れは現在，WWW 上にビジネスを展開する企業にとっ. キスト情報だけではなく，静止画像，アニメーション. て深刻な問題となっている．この状況を改善するため，筆者らの研究グループでは，ユーザによって途中で転送を中断されないよう. † 大阪大学大学院工学研究科情報システム工学専攻 Department of Information Systems Engineering, Graduate School of Engineering, Osaka University †† 大阪大学サイバーメディアセンター Cybermedia Center, Osaka University. な効果的なページ配送手法に関する研究を行っている6)∼8),10),11) ．これまでに，ページ配送に時間がかかる場合に，インラインオブジェクトの配送順序がユー 101.

(2) 102. Jan. 2002. 情報処理学会論文誌. ザに大きな影響を与える点に着目し，インラインオブジェクトの配送順序制御機構を提案している7),8),11) ．提案機構では，たとえば，リンクに使用されている画像から先に配送することで，ユーザに快適な WWW アクセスを提供することや，1 つの絵を構成する複数の分割画像を並行して配送することで，効果的なページ表示を実現する．しかし，これまでの提案機構の実現においては，クライアントがサーバに直接アクセスする単純な環境. Fig. 1. 図 1 配送順序記述および配送の直列化 Transmission order description and the transmission serialization.. を想定しており，クライアント・サーバ間にキャッシングプロキシが存在する環境を考慮していなかった．キャッシングプロキシは，応答時間の短縮，サーバの負荷軽減，および，ネットワークトラフィックの低減など，現在のインターネットにおいて重要な役割を果たしており，無視することはできない．そこで本論文では，クライアント・サーバ間にキャッシングプロキシが存在する場合の配送順序制御機構の実現について考察する．なお，本論文では，簡単のため，クライアント・サーバ間に存在するキャッシングプロキシの数を 1 として議論する．以下では，2 章で筆者らがこれまでに提案している配送順序制御機構の概要について述べる．3 章で配送. Fig. 2. 図 2 HTSP による配送順序制御 Transmission order control by HTSP.. 順序制御機構におけるキャッシングプロキシの振舞いについて考察し，効率的に配送順序制御を実現できる. に導入した MGET メソッドは，HTTP における GET. 配送手法を提案する．4 章で提案手法を分析し，実測. メソッドとは異なり，1 回の要求で複数のオブジェク. 評価によって分析結果の正当性を示す．5 章で関連研. トを指定配送順序で要求できる．以下に，HTSP リク. 究について述べ，最後に 6 章でまとめとする．. エストメッセージの例を示す．なお，ヘッダ情報は省略している．. 2. 配送順序制御機構筆者らの研究グループではこれまでに配送順序制御. MGET [”A”,”B”,”C”]5 HTSP/0.9. 機構を実現するため，情報提供者が配送順序を柔軟に. ここで，‘ ’ は直列配送を，‘[ ]’ は並列配送を意味. 指定できる配送順序記述言語と，配送順序制御を効率的. している．ただし，実際のデータ転送においては，並. に実現する配送プロトコルとして HTSP（ Hypertext. 列配送を実現できないため，各オブジェクトを分割し. Streaming Protocol ）を提案している. 7),8),11). ．. て交互に配送することで実現している．本研究ではこ. 2.1 配送順序記述言語配送順序記述言語では，オブジェクトを一列に並べて配送する直列配送指定，および，複数のオブジェク. で指定された配送順序の記述を配送シナリオと呼んで. トを同時に並行して配送する並列配送指定を組み合わ. いる．このリクエストに対応した配送の直列化処理を. せることで，多様な配送を表現できる．配送順序の記. 図 1 右下に示す．なお，提案プロトコルのバージョン. 述例を図 1 左に，この指定により実現される配送のイ. は 0.9 としている．. メージを同図右上に示す．なお，これらの配送順序指定は，HTML 文書中の head 部にメタ情報として記述している．. 2.2 HTSP. の処理を配送の直列化と呼び，その際のオブジェクトの分割数を ‘[ ]’ の後に記述する．また，これらの記号. HTSP を用いた配送順序制御の実現方法を図 2 に示す．まず，クライアントは配送順序記述言語によりインラインオブジェクトの配送順序が指定された HTML 文書をサーバから取得する．続いて，HTML に記述. 5). HTSP は HTTP を拡張した配送プロトコルであり，配送順序制御を効率的に実現する．HTSP で新た. された配送順序指定を配送シナリオに変換し，MGET メソッドを用いて，サーバにインラインオブジェクト.

(3) Vol. 43. No. 1. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構. 103. を指定配送順序で要求する．これに対しサーバは，配送シナリオに基づいてインラインオブジェクトを直列化し，それをレスポンスとしてクライアントに返す．クライアントは直列化されたオブジェクトから，各オブジェクトを順次抽出し，それをブラウザ上に表示させていく．提案機構では，以上のようにして配送順序. Fig. 3. 図 3 キャッシングプロキシを介した配送順序制御 Transmission order control via a caching proxy.. 制御を実現している．. 3. 配送順序制御機構の拡張. のリクエストでは，クライアントに指定された配送順. 本章では，キャッシングプロキシの存在を考慮して. は，サーバからのレスポンスを受信しながら，クライ. 序でサーバにリクエストを送信するべきである．これ. 配送順序制御機構を拡張する．3.1 節で，配送順序制. アントにオブジェクトを配送できるためである．状況. 御機構におけるキャッシングプロキシの振舞いについ. (3) におけるこの配送の例を図 3 に示す．この例では，. て考察し，これまでの機構をそのまま利用した場合に. サーバから配送されるオブジェクト A，B の適切な位. は，効率的にオブジェクトを配送できない場合がある. 置にプロキシが保持するオブジェクト C を挿入しな. 点を指摘する．3.2 節で，この問題を解決できる配送. がら，クライアントに直列化したオブジェクトを配送. 手法を提案する．3.3 節で，提案手法を実現するため. している．. に HTSP を拡張する．. 以上のように処理することで，キャッシングプロキ. 3.1 キャッシングプロキシを介する場合の問題点 HTSP においては，クライアントは一度に複数のオブジェクトを要求できるため，プロキシがクライアン. プロキシの利点である応答時間の短縮効果を低下させ. トからリクエストを受けた時点で，プロキシのキャッ. るなどの問題が生じる．. シュには，次に示す 3 通りの状況が考えられる．すなわち，要求されたオブジェクトのうち，(1) 全部が存在する，(2) 全部が存在しない，(3) 一部が存在する，である．上記の各状況のうち，状況 (1) と (2) は一般的に生. シが存在する環境においても，提案機構を容易に実現できる．しかし，状況 (3) においては，キャッシング. 3.1.1 プロキシ・サーバ間の伝搬遅延に起因する問題（応答時間の増加）プロキシがクライアントからリクエストを受けた時点で，最初に送信すべきオブジェクトがキャッシュに存在しない場合には，まず最初に，サーバからオブジェ. じることが分かるが，状況 (3) についても頻繁に生じ. クトを取得する必要がある．この間は，たとえ他のオ. ると考えられる．たとえば，Web サイトのバナー画像. ブジェクトをキャッシュしていたとしても，それらを. や宣伝画像，ページのアイコン画像など，複数のペー. 送信することはできず，応答時間の短縮効果は得られ. ジで共有しているオブジェクトは，他のオブジェクト. ない．また，この間のクライアント・プロキシ間の帯. に比べてキャッシュされている可能性が高く，このた. 域は空き状態となっており，帯域幅を有効に利用でき. めに，状況 (3) が起こる場合がある．また，ページの. ていない．. 更新にともない，新たな画像が追加された場合，追加. サーバにアクセスする際に必要となる TCP コネク. された画像はキャッシュされていることはないが，以. ションの確立コストは，HTTP におけるデータ転送に. 前から使用されていた画像がキャッシュされているこ. おいて重要な要素となっている．これに関して，文献. とにより，状況 (3) が生じる．. 4) では，プロキシがサーバとの間の TCP コネクショ. ここで，上記の各状況において，プロキシがどのよ. ンを維持し，複数のクライアントに対して，同一のコ. うに動作すべきかを述べる．状況 (1) では，プロキシ. ネクションを再利用するコネクションキャッシングを. において直列化処理を行い，クライアントにレスポン. 用いることで，応答時間を改善する手法を評価してい. スを返す．状況 (2) では，クライアントのリクエストを. る．結果として，コネクションキャッシングは，ドキュ. サーバに転送し，サーバからのレスポンスをそのまま. メントキャッシングより高い効果が得られる場合があ. クライアントに転送する．状況 (3) では，まず，キャッ. ることを示している．この文献が示すとおり，TCP コ. シュに存在しないオブジェクトをサーバから取得し，. ネクションの確立コストは無視できない．また，サー. プロキシにおいて直列化処理を行う．その後，クライ. バに負荷が集中している場合には，HTTP メッセー. アントにレスポンスを返す．. ジの処理にある程度の時間が必要となるため，HTTP. また，状況 (2) および (3) のプロキシからサーバへ. メッセージのラウンドトリップ時間は大きくなる．以.

(4) 104. 情報処理学会論文誌. Jan. 2002. 上のように，プロキシが最初の応答をクライアントに返すまでの間に長い時間を要する場合があり，応答時間を大幅に増加させる場合がある．. 3.1.2 プロキシ・サーバ間の転送速度に起因する問題（非効率な帯域の利用）クライアト・プロキシ間の転送速度が高速な場合においても，プロキシ・サーバ間の転送速度が低い場合には，この速度がボトルネックとなり，オブジェクトを転送するのに時間を要してしまう．この場合においても，クライアント・プロキシ間の帯域幅を有効に利用できていない．このような状況は，サーバへのアクセス集中によって処理速度が低下している場合や，クライアント側で. 図 4 HARD による配送と SOFT による配送の比較 Fig. 4 Comparison between hard transmission and soft transmission.. 高速の LAN を構築し，LAN とインターネットの境界にプロキシを配置している環境において生じる．. 3.2 HARD による配送と SOFT による配送前節で述べた問題は，プロキシが指定された配送順. 短縮できる簡単な例を示す．これは，プロキシ・サーバ間の転送速度がボトルネックとなっている状況下で，クライアントからプロキシへのリクエストにおいて，. 序を必ず保証しようとするために生じる．配送順序制. 配送シナリオが A,B,C であり（指定された配送順. 御機構において，指定された配送順序でオブジェクト. ，オブジェクト序が A，B，C の順であることを示す）. を配送することは当然のことある．しかし，プロキシ. A，B，C のうち，B，C がプロキシにキャッシュされ. が存在する場合には，配送順序を必ずしも保証すべき. ている場合に，プロキシからクライアントに対して行. ものではないとすることによって，前節の問題が解決. われる両手法による配送を示している．. され，通常の配送よりも応答時間を短縮できる．る問題に対しては，プロキシがキャッシュに存在する. HARD による配送では，クライアントからのリクエストが到着した時点で，プロキシはキャッシュに存在しないオブジェクト A をサーバに要求し，それが. オブジェクトを先にクライアントに配送しておくこ. 送信されるのを待つ．サーバから A が送信され次第，. たとえば，プロキシ・サーバ間の伝搬遅延に起因す. とで，ユーザの応答時間を改善できる．また，プロキ. クライアントに A を転送し，続いて，キャッシュから. シ・サーバ間の転送速度に起因する問題に対しては，サーバから転送されるデータをそのままクライアント. B，C を送信する． SOFT による配送においても，リクエストの到着時. に送信するのではなく，サーバからある程度のデータ. に，サーバに対して A を要求するが，同時にクライ. 量を取得するまでデータをバッファリングしておき，. アントに対してキャッシュに存在するオブジェクト B，. その間はキャッシュにあるオブジェクトを送信してお. C の送信を始めることにより，応答時間の短縮を狙う．. く．バッファリングが完了した時点で，サーバから取. B，C を送信している間に A をバッファリングできた. 得したデータをクライアントに送信することにより，. 場合，クライアント・プロキシ間の転送速度で送信で. クライアント・プロキシ間の転送速度でデータを送信. きる．結果として，全オブジェクトの配送時間が短縮. できる．. される．. このように，プロキシが配送順序を適宜調整してオ. ここで，図 4 に示した両手法による配送を，全オブ. ブジェクトを配送できれば，最初の応答を返すまでの. ジェクトの配送時間ではなく，特定のオブジェクトの. 時間や，全オブジェクトの配送に必要な時間を短縮で. 表示完了時間の点で比較した場合，SOFT による配送. きる．そこで，キャッシングプロキシを考慮した配送順. が必ずしも有効であるとはいえない．なぜなら，最優. 序制御機構においては，プロキシがキャッシュの状況. 先で配送したいオブジェクト A の表示完了時間では，. によってオブジェクトの配送順序を変更できるように. HARD による配送のほうが優れているためである．. 配送順序制御機構を拡張する．以下では，拡張前の配. したがって，表示順序を考慮した場合のキャッシュ. 送を HARD による配送とし，拡張後の配送を SOFT. に存在しないオブジェクトの配送方針として，図 4 で. による配送として，両者の配送を比較する．. 示したように単純に最後に送信するのではなく，ある. まず，図 4 に SOFT による配送により，配送時間を. 程度取得した時点で，クライアントに送信することが.

(5) Vol. 43. No. 1. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構. Table 1. 図 5 表示順序を考慮した SOFT による配送 Fig. 5 Effective soft transmission considering presentation order.. 望ましい．この配送の例を図 5 に示す．これは，前述. Dcp Dps Sp Ss Bcp Bps. 105. 表 1 変数定義 Valuable definitions.. クライアント・プロキシ間の伝搬遅延プロキシ・サーバ間の伝搬遅延プロキシ・キャッシュに存在するデータサイズサーバから取得するデータサイズクライアント・プロキシ間の帯域幅プロキシ・サーバ間の帯域幅. は実装依存としている．. 4. 評. 価. の配送において，サーバから送信される A の 3 分の. 本章では，SOFT による配送の有効性を示すため，. 1 のデータサイズを取得するごとに，それをクライアントに送信した場合であり，各オブジェクトの表示速度の点でも改善が期待できる．. SOFT による配送と HARD による配送を配送時間の点で比較評価する．4.1 節で理論的な分析により， HARD による配送の有効性を示す．4.2 節で，SOFT. 3.3 HTSP の拡張 SOFT による配送では，プロキシがクライアントによる指定配送順序とは異なる順序でオブジェクトを. による配送を実現するプロキシを実装し，実験環境において実測評価をすることにより，分析結果の正当性を確認する．. キシによる順序変更に対応できるように HTSP を拡. 4.1 分析本節では，プロキシ・サーバ間の伝搬遅延と全オブ. 張する必要がある．本研究では，プロキシが配送順序. ジェクトの配送時間の相関関係を分析する．配送時間. を変更してオブジェクトを配送する際，送信するオブ. を導出する際に考慮する変数と定義を表 1 に示す．伝. ジェクトの識別子および送信サイズをヘッダで明示す. 搬遅延は，HTTP メッセージが相手先まで到達する. 送信する場合がある．そのため，クライアントがプロ. ることにより，SOFT による配送を実現する．以下に，. のに必要な時間を意味しており，HTTP メッセージ. HTSP に新たに追加したヘッダを示す．. の処理時間も含む．帯域幅は実際のデータ転送速度を. • Object: id=identification，volume=length プロキシが配送順序を変更してキャッシュのオブ. 意味する．これらの変数のほかに，配送順序によって配送時間が変化してくるが，一般的な配送順序を考慮. ジェクトを送信する場合に用いる．このヘッダは，. することは困難であるため，以下では，HARD によ. identification で示されるオブジェクトの length バ. る配送と SOFT による配送において，最も配送時間. イトを配送することを示す． • Serialized: volume=length プロキシが直列化処理に基づいた配送を行う場合. て，配送時間を導出する（配送シナリオ中で Ss およ. に用いる．直列化本体の未配送部分の length バイ. の差が大きくなる場合の < Ss , Sp > を配送順序としび Sp を用いる場合は，データサイズではなく，オブジェクトを指すこととする）．. トを配送することを示す．volume の指定がない. まず，HARD による配送の配送時間を図 6(a) から. 場合，直列化本体の最後までを配送する． • Transmission: order=method クライアントがプロキシに対して，配送手法を指. なっている転送速度で Ss を送信することになる．し. 定するために用いる．たとえば，クライアントが. SOFT による配送に対応している場合，method に SOFT を指定する．デフォルトでは，HARD とする．本研究において，以上のヘッダを HTSP の仕様に. 導く．この場合，Bcp と Bps のうち，ボトルネックとたがって，配送時間 T は次式で表される．. T = 2Dcp + 2Dps +. Sp Ss (1) + Bcp min(Bcp , Bps ). 次に，SOFT による配送の配送時間を導出する．プロキシがサーバからの応答を受信する前に，全 Sp の S. p < 2Dps )，配送時間は次式配送が終了する場合 ( Bcp. 追加した．ただし，これらのヘッダはオブジェトを識. で表される（図 6(b) 参照）．. 別するために用いられるものであり，プロキシがオブ. T = 2Dcp + 2Dps +. ジェクトを図 4 のように配送するのか，もしくは，図 5 のように配送するのかといった，プロキシの配送方針. Ss min(Bcp , Bps ). (2). 逆に，プロキシがサーバから応答を受信した時点で.

(6) 106. Jan. 2002. 情報処理学会論文誌. 図 6 配送時間の導出 Calculation of the transmission time.. Fig. 6 S. p は，全 Sp の配送が終了していない場合 ( Bcp > 2Dps ). る．そのため，s0 については Bcp の転送速度で. を考える．この場合，Bcp と Bps の大小関係により. 送信できる．同様にして，s0 を送信している間に，. 場合分けをする必要がある．. s0 Bcp. • Bcp < Bps の場合，Ss の配送終了後に Sp の残．しがたっりのデータを送信する（図 6(c) 参照）て，次式が得られる． Sp Ss T = 2Dcp + + (3) Bcp Bcp • Bcp > Bps の場合，図 5 で示した表示順序を考慮した配送により，Ss の一部を取得するごとにそれをクライアントに送信していくことが望まし. × Bps (= s1 ) だけのデータ量をバッファでき，. このデータは Bcp の転送速度で送信できる．このことから，Ss のうち Bcp の転送速度でクライアントに送信できるデータ量 S は，次式で表される．. S=. ∞ n=0. sn =. ∞ Bps. (. n=0. Bcp. )n × s 0 =. s0 1−. Bps Bcp. (4). いと述べたが，本節の配送時間の導出においては，. ここで，Ss が S 以下の場合，全 Ss を Bcp の転. 全 Sp の送信が終了した時点で，Ss の送信に切. 送速度で送信でき，また，Ss が S より大きい場. り替えるとする（図 6(d) 参照）．. 合，Ss のうちの S は Bcp で送信できるが，残. この場合，プロキシはクライアントに対して Ss の. りの Ss − S は Bps で送信しなければならない. p − 配送を開始するまでの間に，Ss のうちの ( Bcp. ことに着目すると次式が得られる．. S. 2Dps ) × Bps (= s0 ) のデータ量をバッファでき. – Ss < S の場合.

(7) Vol. 43. No. 1. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構. Fig. 7. (2Dps <. 107. 図 7 配送時間と遅延の関係 Correlation between the transmission time and the latency.. Sp Bcp. − ( B1ps − B1cp )Ss )， Sp Ss T = 2Dcp + + Bcp Bcp. – Ss > S の場合 Sp (2Dps > Bcp − ( B1ps −. (5). 1 )Ss )， Bcp. Sp S Ss − S + + Bcp Bcp Bps Ss = 2Dcp + 2Dps + (6) Bps. T = 2Dcp +. 以上から，配送時間と遅延の関係は図 7 で表される．なお，本節では HARD による配送と SOFT に Fig. 8. よる配送において，最も配送時間の差が大きくなる. 図 8 プロキシの動作概要 Overview of the proxy operation.. < Ss , Sp > を配送順序として配送時間を導出した．配送順序が [Ss , Sp ]n の場合など，並列の配送が含ま. (2). リクエストを受信したプロキシは，要求された. れる場合においても，直列の配送に置き換えて考える. オブジェクトをキャッシュに存在するものと存. ことで同様に導出できる．. 在しないものの 2 つのグループに分けた後，マ. 4.2 実験本研究では，実環境において前節の分析結果が得ら. ルチスレッド処理により，以下の 2 つの処理を. れるかどうかを確認するために，プロキシの実装およ. • サーバにオブジェクトを要求する．クライアントからのリクエストメッセージに，キャッシュに存在するオブジェクトの. び実測評価を行った．. 4.2.1 実装本研究では，前章で導入したヘッダを用いて，SOFT による配送に対応したキャッシングプロキシを Jigsaw. 同時に行う．. ファイルサイズをヘッダで明示して，サーバにリクエストを送信する．サーバは，こ. Web サーバ12)を用いて実装した．本実装では，前章で述べた表示順序を考慮した SOFT による配送方針. のファイルサイズを用いて直列化処理を行. を採用した．以下，図 8 を用いて，本実装におけるプ. 序でオブジェクトを送信する．. ロキシの動作概要を述べる．. (1). クライアントからプロキシに HTSP リクエストが送信される．. うことで，プロキシに対して最適な配送順. • クライアントにオブジェクトを配送する．この時点では全オブジェクトが存在しないために，直列化できない場合がある．そのような場合には，キャッシュに存在しない.

(8) 108. Jan. 2002. 情報処理学会論文誌. オブジェクトのファイルサイズを 0 として直列化処理を行い，仮の配送順序を決定する．その後，この順序に従って，一定サイズごとに Object ヘッダを挿入して配送する．本実装においては，このサイズが最大で 8192 バイトとなるようにヘッダを挿入した．本実装では，このサイズを固定値として扱っ. Fig. 9. 図 9 実験環境 Experimental environment.. ているが，サーバのスループットやクライアントの帯域幅を考慮して動的に決定することで性能を向上させることも考えられる．. Table 2. 表 2 使用マシン Components used in the experiment.. なお，本実装では，プロキシがクライアントか. Component. OS. ら要求を受けたときに，キャッシュに存在するオ. Client. Windows98. ブジェクトの有効性をサーバに問い合わせない. Proxy. Solaris2.6. Server. Windows98. ことととした．有効性を確認する場合，サーバに対するオブジェクトの要求では，ファイルサイズではなく，オブジェクトの識別子（ Entity-. Tag または Last-Modified ）を付加する．その間，クライアントに対するオブジェクトの配送は行わない．一般に，キャッシュオブジェクト. PPP Server Windows NT 4.0. Table 3. の有効性の確認は，サーバに指示された有効期限が切れた場合や，クライアントからの指示により必要となる．. (3). サーバからのレスポンスがプロキシに到着し，. Sp Ss Bcp Bps. CPU MMX Pentium (166 MHz) Ultra SPARC-II (300 MHz)x2 MMX Pentium (266 MHz) Pentium III (550 MHz) x 2. Memory 96M 512M 96M 1024M. 表 3 実験用の設定 Configuration in the experiment.. experiment (A) 50 KB 50 KB 38.4 kbps 112.6 kbps. experiment (B) 50 KB 50 KB 57.6 kbps 38.4 kbps. レスポンスヘッダを取得した時点で，再度，直. (4). 列化処理を行う．その後，( 2 ) のクライアント. アントとサーバのそれぞれを PPP サーバとシリアル. に対するオブジェクトの送信を中断する．. ケーブル上で PPP 接続させ，その転送速度を変化させ. プロキシは，サーバからのレスポンスをバッファ. ることにより，クライアント・プロキシ間とプロキシ・. リングしながら，クラアイントに SOFT によ. サーバ間の帯域幅を調整できるようにしている．PPP. る配送を行う．ただし，これは ( 2 ) で送信した. サーバとサーバ間は 10 Mbps のイーサネット LAN で. 部分を除いた配送となる．. 接続している．また，各構成要素において使用したマ. ここでは，Serialized ヘッダを用いて直列化処. シンを表 2 に示す．. 理に基づいた配送を行うが，volume の値には，サーバレスポンスのバッファリング状況から，. 次に，実験用の設定を表 3 に示す．実験 A では Bcp < Bps の場合を，実験 B では Bcp > Bps の場合. その時点で送信できる最大のデータサイズを指. を評価する．両実験とも，データサイズが 25 KB の. 定する．指定した volume 分の配送が終了後，. JPEG 画像 4 つ（ Sp1 ，Sp2 ，Ss1 ，Ss2 ）を用い，プ. 再度同じ処理を繰り返す．ただし，次に送信す. ロキシ側に Sp1 ，Sp2 を，サーバ側に Ss1 ，Ss2 を配. べきデータが存在しない場合，Object ヘッダを. 置し，配送順序を < Ss1 , Ss2 , Sp1 , Sp2 > と設定した．. 用いて，そのデータ以降に送信する予定のキャッ. 実験では，2Dps を 0 から 19 秒までの間で変化させ. シュに存在するデータを 8192 バイト単位で配. て，クライアントがリクエストを送信してから，全オ. 送する． 4.2.2 実測評価. ブジェクトの受信が終了するまでの配送時間をクライ. 本項では，実装したプロキシを用いて，SOFT によ. リクエスト受信時にスリープを挿入することにより，. る配送と HARD による配送の配送時間を実測評価し，. 4.1 節の分析結果の正当性を確認する．まず，実験環境を図 9 に示す．本実験では，クライ. アント側で測定した．なお，本実験では，サーバ側で. 2Dps を変化させている．実験結果を図 10 に示す．この図において，縦軸は配送時間を示し，横軸はプロキシ・サーバ間の遅延.

(9) Vol. 43. No. 1. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構. (a) 実験 A に対する結果. 109. (b) 実験 B に対する結果図 10 実験結果 Fig. 10 Results.. （ 2Dps ）を示している．実際の配送においては，TCP のコネクション確立のためのオーバヘッドやスロースタート，ネットワークの混雑状況，実装上のオーバヘッド，シリアルリンクの実際の転送速度など，様々な要因がからみあって配送時間が決まる．そのため， (a) 実験 A の 2Dps = 10 における配送. 配送時間そのものについては前節で導出した理論値とは多少異なっているが，グラフ全体の特性としては，前節の分析結果と類似した実験結果が得られた．結果より，あらゆる場合において，SOFT による配送が. HARD による配送よりも性能が良いこと分かる．また，HARD による配送では，プロキシ・サーバ間の伝. (b) 実験 B の 2Dps = 3 における配送. 搬遅延やサーバのリクエスト処理などにより生じる遅延が大きくなるにつれて，配送時間も同様にして増加. Fig. 11. 図 11 配送状況 Transmission from the proxy to the client.. するが，SOFT による配送では，ある程度の遅延まではほぼ一定時間で配送できている．SOFT による配送. スレッド処理において，デーモン間の同期の際にオー. の問題点として，HARD による配送においては不要. バヘッドが生じているためと考えられる．図 11(b) に. なヘッダを使用しているために送信する総データサイ. おいて，SOFT による配送では，Sp2 の配送中にサー. ズが大きくなる点があげられるが，本実験で受信デー. バから Ss1 が到着した際，Ss1 の配送に切り替える. タサイズを測定したところ，数キロバイトの差であっ. ことにより，クライアントによる指定配送順序を考慮. ため特に問題はない．. した配送を実現できている．その際，Bcp > Bps で. 最後に，HARD による配送と SOFT による配送. はあるが，バッファリングした Ss1 を配送すること. の各オブジェクトの配送状況を比較する．実験 A の. により，Bcp の転送速度で Ss1 を送信することに成. 2Dps = 10 における配送状況を図 11(a) に，実験 B. 功している．同様に，Ss2 も Bcp の転送速度で送信. の 2Dps = 3 における配送状況を図 11(b) に示す．. できている．図 11(a)，(b) のいずれの配送において. 図 11(a) の SOFT による配送では，プロキシがサー. も，SOFT による配送では，キャッシュに存在するオ. バからレスポンスを取得するまでの間に，Sp1 と Sp2. ブジェクトをプロキシ・サーバ間の伝搬遅延の影響を. の配送を終了しており，その分の時間差が HARD に. 受けることなく，即座に配送できる．これにより，応. よる配送と SOFT による配送の配送時間の差として. 答時間の大幅な短縮を実現している．. 現れている．SOFT による配送において，Sp2 と Ss1 の配送の間に隙間が生じているのは，本実装のマルチ.

(10) 110. Jan. 2002. 情報処理学会論文誌. 5. 関連研究 HTTP プロキシにおいて配送順序を制御することにより，ユーザの待ち時間を短縮する研究がいくつか行われている．文献 3) では，プロキシにおける全ユーザのアクセスパターンから，あるユーザにより要求された Web ページの次に要求される Web ページを予測し，ユーザに要求されるよりも前に，プロキシがクライアントマシンに Web ページを配送するプリプッシュ手法を提案している．これは，Web ページ間の配送順序制御手法ということができ，本論文で提案したインラインオブジェクト間の配送順序制御手法とは補完的な技術である．文献 1) では，クライアントから. HTML ファイルを要求された際に，プロキシにおいて HTML ファイルを解析し，リンク先の HTML ファイルおよびインラインオブジェクトをサーバから取得するプリフェッチ手法を提案している．また，文献 2) では，オブジェクトのプリプッシュ手法やプリフェッチ手法ではなく，DNS 問合せや TCP コネクションのプリフェッチ手法を評価し，その有効性を示している．これらの手法は，配送順序制御機構においても利用することができ，プロキシ・サーバ間の伝搬遅延の影響を小さくできる．. 6. まとめ本論文では，キャッシングプロキシを考慮して配送順序制御機構を拡張した．拡張機構では，クライアント・サーバ間にプロキシが存在する場合，プロキシが配送順序を適宜調整することにより，オブジェクトの配送時間を短縮できる．また，理論的分析および実測評価により，拡張機構の有効性を示した．本手法は， HTTP におけるパイプライン処理に対しても同様に適用できると考え，同研究グループにおいて現在研究を行っている．今後の課題として，クライアント・サーバ間において複数のプロキシが協調作業を行う場合の効率的な配送方式や，配送順序制御機構に適したキャッシュの管理方式を考察する予定である．また，これまでは HTTP とは異なるプロトコルである HTSP を利用して配送順序制御を実現してきたが，今後は HTTP 拡張機構9) を用いて実現する予定である．謝辞本研究の一部は，日本学術振興会未来開拓学術研究推進事業における研究プロジェクト「マルチメディア・コンテンツの高次処理の研究（ JSPS-. RFTF97P00501 ）」によっている．ここに記して謝意. を表す．. 参考文献 1) Chinen, K. and Yamaguchi, S.: An interactive prefetching proxy server for improvement of WWW latency, Proc. INET ’97 Conference (June 1997). 2) Cohen, E. and Kaplan, H.: Prefetching the means for document transfer: A new approach for reducing web latency, Proc. IEEE INFOCOM 2000 Conference (2000). 3) Fan, L., Jacobson, Q., Cao, P. and Lin, W.: Web prefetching between low-bandwidth clients and proxies: Potential and performance, Proc. SIGMETRICS ’99 Conference (May 1999). 4) Feldmann, A., Caceres, R., Douglis, F., Glass, G. and Rabinovich, M.: Performance of web proxy caching in heterogeneous bandwidth environments, Proc. IEEE INFOCOM’99 Conference (1999). 5) Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P. and Berners-Lee, T.: RFC2616: Hyper-text Transfer Protocol — HTTP/1.1 (1999). 6) Harumoto, K., Nakano, T., Shimojo, S. and Nishio, S.: A WWW server with media scaling mechanism based on page transmission latency, Proc. 1999 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (Aug. 1999). 7) Harumoto, K., Nakano, T. and Shimojo, S.: An architecture for adaptive multimedia contents delivery, New Generation Computing, Vol.18, No.4, pp.375–389, Ohmsha, Ltd. and Springer-Verlag (2000). 8) Nakano, T., Harumoto, K., Shimojo, S. and Nishio, S.: Controlling transmission order of inline objects for effective web page publishing, Proc. 2000 ACM Symposium on Applied Computing (Mar. 2000). 9) Nielsen, H., Leach, P. and Lawrence, S.: RFC2774: An HTTP Extension Framework (2000). 10) 中野賢，春本要，下條真司，西尾章治郎：ページ配送時間を考慮した画質調整機能をもつ WWW サーバ，電子情報通信学会論文誌 D-I， Vol.J83-D-I, No.1, pp.194–202 (Jan. 2000). 11) 中野賢，春本要，下條真司，西尾章治郎：インラインオブジェクトの配送順序制御が可能なページ配送機構，電子情報通信学会論文誌 D-I， Vol.J84-D-I, No.2, pp.155–164 (Feb. 2001). 12) World Wide Web Consortium: Jigsaw — The.

(11) Vol. 43. No. 1. キャッシングプロキシを考慮したインラインオブジェクトの配送順序制御機構. W3C’s Web Server. http://www.w3.org/Jigsaw/. (平成 13 年 1 月 17 日受付) (平成 13 年 10 月 16 日採録). 111. 下條真司（正会員）. 1981 年大阪大学基礎工学部情報工学科卒業．1986 年同大学院基礎工学科博士後期課程修了．工学博士．同年大阪大学基礎工学部情報工学科助. 中野. 賢. 手．1989 年同大学大型計算機セン. 1999 年大阪大学工学部情報システム工学科卒業．2000 年同大学院工学. ター講師．1991 年同助教授．1998 年同教授．2000 年. 研究科博士前期課程修了．現在，同. のアクセス方式の性能評価，分散処理システムの性能. 大学院工学研究科博士後期課程在学. 評価，分散型オペレーションシステムの研究に従事．. 同サイバーメディアセンター教授（改組により）．LAN. 中．マルチメディアコンテンツの配信・適応機構，Web キャッシング等の研究開発に従事．. 西尾章治郎（正会員）. 1975 年京都大学工学部数理工学科春本. 要（正会員）. 1992 年大阪大学基礎工学部情報工. 卒業．1980 年同大学院工学研究科博士課程修了．工学博士．京都大学工. 学科卒業．1994 年同大学院基礎工学. 学部助手，大阪大学基礎工学部およ. 研究科博士前期課程修了．同年，大. び情報処理教育センター助教授を経. 阪大学大学院工学研究科情報システ. て，1992 年より大阪大学大学院工学研究科情報システ. ム工学専攻助手．1999 年大阪大学. ム工学専攻教授となり，現在に至る．2000 年より大阪. 大型計算機センター講師．2000 年同大学サイバーメ. 大学サイバーメディアセンター長を併任．この間，カ. ディアセンター講師となり，現在に至る．博士（工学）．. ナダ・ウォータールー大学，ビクトリア大学客員．デー. データベースシステム，マルチメディア通信システム. タベース，知識ベース，分散システムの研究に従事．現. 等の研究に従事．電子情報通信学会，IEEE 各会員．. 在，Data & Knowledge Engineering，Data Mining. and Knowledge Discovery，The VLDB Journal 等の論文誌編集委員．ACM，IEEE 等 8 学会の会員．.

(12)