(57)【特許請求の範囲】
【請求項１】
コンテンツを記憶し、配信するためのシステムであって、コンテンツを要求するための複数のエンドユーザーブラウザと、コンテンツを配信するための少なくとも１つのコンテンツプロバイダオリジナルサイトと、通信用のネットワークにより相互に接続している、コンテンツを記憶するための少なくとも１つのプロキシサーバーとを含むシステムにおいて、
予備取り出し帯域幅割当て値を使用して、少なくとも１つのプロキシサーバーに、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しさせるためのコンテンツ配信サービスプロバイダであって、該コンテンツ配信サービスプロバイダは、
ｄ（ｂ）は、ｂの帯域幅単位が前記コンテンツを予備取り出しするために利用された場合に観察された単位遅延であり、congestion（Util）は、congestion（Util）＝β／(Utilθ＋α)＋φ、または、congestion（Util）＝β× (1.0 - Util)α＋φ、として表すことができる混雑関数であり、Utilは、最大ネットワーク帯域幅に対して利用されるネットワーク帯域幅の比率を表し、パラメータα、β、およびφが、前記混雑関数を帯域幅利用比率と応答遅延との関係を示す混雑曲線に適合させるために利用される場合において、ｂの帯域幅単位を利用して、サイズsize（ｏ）のコンテンツｏの検索時間を、ret（ｏ）＝congestion × size（ｏ）× ｄ（ｂ）、としてモデル化し、
Ｐは、予備取り出し帯域幅の大きさであり、Ｂは、前記システムにとって有効な全帯域幅であり、ｒ（ｔ）＝（１−σ（Ｐ））× ｕ（ｔ）は、少なくとも１つのプロキシサーバー内に記憶されていないコンテンツに対するエンドユーザーブラウザ要求を検索するためにシステムが利用する帯域幅の大きさであり、σ（Ｐ）は、帯域幅がＰである場合のキャッシュの新しさおよび有効性の数値であり、ｕ（ｔ）は、ユーザーのアクセス速度である場合において、時刻ｔ0において、少なくとも１つのコンテンツプロバイダから取り出したコンテンツについて、少なくとも１つのプロキシサーバーが観察した遅延の量を、ret（Ｐ）＝congestion（（Ｐ＋ｒ（ｔ0））／Ｂ）× ｒ（ｔ0）× ｄ、としてモデル化し、
δret（Ｐ）／δＰ＝０を解くことにより、最適の予備取り出し帯域幅割当て値Ｐを計算し、
少なくとも１つのプロキシサーバーへ、最適の予備取り出し帯域幅割当て値Ｐを通信する、
ようにプログラムされていることを特徴とするコンテンツ配信サービスプロバイダ。
【請求項２】
前記コンテンツ配信サービスプロバイダは、
Ｐについて、現在の帯域幅消費量（Ｒ＝ｒ（ｔ0））を利用して、δret（Ｐ）／δＰ＝０を解き、
現在の帯域幅消費量（Ｒ＝ｒ（ｔ0））を利用して、ret（Ｐ）を計算し、
ｐが今後の参照の度合である場合に、時刻ｔ0までのｒ（ｔ）の性質を示す履歴関数ｈr（ｔ）を利用して、期間［ｔ0，ｔ0＋ret（Ｐ）×ｐ］内の最大の帯域幅消費量Ｒmaxを推定し、
最大の帯域幅消費量の推定値（Ｒ＝Ｒmax）を利用してδret（Ｐ）／δＰ＝０を解くことによって、調整済みの予備取り出し帯域幅割当ての数値Ｐadjustedを計算し、
少なくとも１つのプロキシサーバーに対して、調整済みの予備取り出し帯域幅割当ての数値Ｐadjustedを通信する、
ことにより、最悪の場合の帯域幅利用の推定値を考慮に入れる調整済みの予備取り出し帯域幅割当ての数値を計算するように、さらにプログラムされていることを特徴とする請求項１に記載のコンテンツ配信サービスプロバイダ。
【請求項３】
前記コンテンツ配信サービスプロバイダは、
最大の帯域幅消費量の推定値（Ｒmax）を利用して、Δｔ＝ret（Ｐadjusted）×ｐを計算し、
【数１】
0003575428.tif 000020
が、帯域幅消費量についての予備知識または履歴関数ｈr（ｔ）により推定される場合において、帯域幅の平均使用幅を、
【数２】
0003575428.tif 000021
と定義し、
UtilavgおよびＰavgを利用して、予想検索時間Retexp（Ｐavg）を定義することにより、δretexp（Ｐavg）／δＰavg＝０を解くことによって、推定的な平均予備取り出し帯域幅割当ての数値Ｐavgを計算し、
少なくとも１つのプロキシサーバーに対して、前記平均予備取り出し帯域幅割当ての数値Ｐavgを通信する、
ことにより、平均帯域幅利用の推定値を考慮に入れる平均予備取り出し帯域幅割当ての数値を計算するように、さらにプログラムされていることを特徴とする請求項２に記載のコンテンツ配信サービスプロバイダ。
【請求項４】
前記コンテンツ配信サービスプロバイダは、
各コンテンツＯIに対する、問い合わせ頻度（Ｏi）、更新頻度（Ｏi）および期限切れ時間（Ｏi）は、キャッシュログファイルから入手され、ｃ1、ｃ2およびｃ3は、前の期間からの統計または一定の時間間隔における経験的計算を利用して割り当てることができる配列係数である場合において、コンテンツＯIを予備取り出しするための優先順位の数値を、
【数３】
0003575428.tif 000022
として計算し、
計算した優先順位の数値と、所与の予備取り出し帯域幅とを利用して、次のΔｔ単位時間内に予備取り出しする一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、 ように、さらにプログラムされていることを特徴とする請求項１に記載のコンテンツ配信サービスプロバイダ。
【請求項５】
前記コンテンツ配信サービスプロバイダは、
【数４】
0003575428.tif 000023
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる古いオブジェクトの予想数を、
【数５】
0003575428.tif 000024
として計算し、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数６】
0003575428.tif 000025
を維持しながら、
【数７】
0003575428.tif 000026
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、 ように、さらにプログラムされていることを特徴とする請求項１に記載のコンテンツ配信サービスプロバイダ。
【請求項６】
前記コンテンツ配信サービスプロバイダは、
Δｔ時間単位中における、オブジェクトｏiに対する予想アクセス回数は、Δｔ×ｑ（ｏi）であり、
【数８】
0003575428.tif 000027
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる新しいオブジェクトの予想数を、
【数９】
0003575428.tif 000028
として計算するために、size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数１０】
0003575428.tif 000029
を維持しながら、
【数１１】
0003575428.tif 000030
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、 ように、さらにプログラムされていることを特徴とする請求項１に記載のコンテンツ配信サービスプロバイダ。
【請求項７】
コンテンツを記憶し、配信するためのシステムであって、コンテンツを要求するための複数のエンドユーザーブラウザと、コンテンツを配信するための少なくとも１つのコンテンツプロバイダオリジナルサイトと、通信用のネットワークにより相互に接続している、コンテンツを記憶するための少なくとも１つのプロキシサーバーとを含むシステムにおいて、
予備取り出し接続の数を使用して、少なくとも１つのプロキシサーバーに、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しさせるためのコンテンツ配信サービスプロバイダであって、該コンテンツ配信サービスプロバイダは、
congestion（Util）は、congestion（Util）＝β／(Utilθ＋α)＋φ、または、congestion（Util）＝β× (1.0 - Util)α＋φ、として表すことができる混雑関数であり、Utilは、許可された接続の最大数に対して開放されている接続の比率を表し、パラメータα、β、およびφが、前記混雑関数をシステムリソース利用と応答遅延との関係を示す混雑曲線に適合させるために利用される場合において、サイズsize（ｏ）のコンテンツｏの検索時間を、ret（ｏ）＝congestion × size（ｏ）、としてモデル化し、
Ｐは、予備取り出し接続の数であり、Ｂは、許可された接続の最大数であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、少なくとも１つのプロキシサーバー内に記憶されていないコンテンツを要求により取り出すために、前記システムが利用する接続の数であり、σ（Ｐ）は、帯域幅がＰである場合のキャッシュの新しさおよび有効性の数値であり、ｕ（ｔ）は、ユーザー接続アクセス速度である場合において、時刻ｔ0において、少なくとも１つのコンテンツプロバイダオリジナルサイトから取り出したコンテンツについて、少なくとも１つのプロキシサーバーにおいて観察された遅延の量を、ret（Ｐ）＝congestion（（Ｐ＋ｒ（ｔ0）＋ｕ（ｔ0））／Ｂ）×（ｕ（ｔ0）＋ｒ（ｔ0））× 平均的オブジェクトサイズ、としてモデル化し、
δret（Ｐ）／δＰ＝０を解くことにより、最適の予備取り出し接続数Ｐを計算し、
少なくとも１つのプロキシサーバーへ、最適の予備取り出し接続数Ｐを通信する、
ようにプログラムされていることを特徴とするコンテンツ配信サービスプロバイダ。
【請求項８】
前記コンテンツ配信サービスプロバイダは、
Ｐについて、現在の使用接続数（Ｒ＝ｒ（ｔ0））を利用して、δret（Ｐ）／δＰ＝０を解き、
ＲおよびＰを使用して計算した前記混雑を利用して、Ｐのコンテンツを予備取り出しするために必要な時間の長さρを見出すことにより、ｐは、Ｐのコンテンツを予備取り出しするのに必要な時間である場合において、時刻ｔ0までのｒ（ｔ）の性質を示す履歴関数ｈr（ｔ）を利用して、期間［ｔ0，ｔ0＋ｐ］内における要求による取り出し接続の最大数Ｒmaxを推定し、
要求による取り出し接続の最大数の推定値（Ｒ＝Ｒmax）を利用して、δret（Ｐ）／δＰ＝０を解くことにより、調整済みの予備取り出し接続数Ｐadjustedを計算し、
少なくとも１つのプロキシサーバーに対して、調整済みの予備取り出し接続数Ｐadjustedを通信する、
ことにより、最悪の場合の接続利用の推定値を考慮に入れる調整済みの予備取り出し接続数を計算するように、さらにプログラムされていることを特徴とする請求項７に記載のコンテンツ配信サービスプロバイダ。
【請求項９】
前記コンテンツ配信サービスプロバイダは、
Δｔを、Ｐadjustedの接続を予備取り出しするために必要な、最悪の場合の時間の長さとして定義し、
【数１２】
0003575428.tif 000031
が、予備取り出し接続についての予備知識または履歴関数ｈr（ｔ）を利用して推定される場合において、帯域幅の平均使用幅を、
【数１３】
0003575428.tif 000032
と定義し、
UtilavgおよびＰavgを使用して、予想検索時間Retexp（Ｐavg）を定義し、
δretexp（Ｐavg）／δＰavg＝０を解くことによって、平均的な予備取り出し接続数の推定値Ｐavgを計算し、
少なくとも１つのプロキシサーバーに対して、平均的な予備取り出し接続数の推定値Ｐavgを通信する、
ことにより、平均的な接続利用の推定値を考慮に入れる平均的な予備取り出し接続数を計算するように、さらにプログラムされていることを特徴とする請求項８に記載のコンテンツ配信サービスプロバイダ。
【請求項１０】
前記コンテンツ配信サービスプロバイダは、
各コンテンツＯIに対する、問い合わせ頻度（Ｏi）、更新頻度（Ｏi）および期限切れ時間（Ｏi）は、キャッシュログファイルから入手され、ｃ1、ｃ2およびｃ3は、前の期間からの統計または一定の時間間隔における経験的計算を利用して割り当てることができる配列係数である場合において、コンテンツＯIを予備取り出しするための優先順位の数値を、
【数１４】
0003575428.tif 000033
として計算し、
計算した優先順位の数値と、所与のネットワーク接続の数とを利用して、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、
ように、さらにプログラムされていることを特徴とする請求項７に記載のコンテンツ配信サービスプロバイダ。
【請求項１１】
前記コンテンツ配信サービスプロバイダは、
【数１５】
0003575428.tif 000034
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる古いオブジェクトの予想数を、
【数１６】
0003575428.tif 000035
として計算し、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数１７】
0003575428.tif 000036
を維持しながら、
【数１８】
0003575428.tif 000037
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、 ように、さらにプログラムされていることを特徴とする請求項７に記載のコンテンツ配信サービスプロバイダ。
【請求項１２】
前記コンテンツ配信サービスプロバイダは、
Δｔ時間単位中における、オブジェクトｏiに対する予想アクセス回数は、Δｔ×ｑ（ｏi）であり、
【数１９】
0003575428.tif 000038
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる新しいオブジェクトの予想数を、
【数２０】
0003575428.tif 000039
として計算し、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数２１】
0003575428.tif 000040
を維持しながら、
【数２２】
0003575428.tif 000041
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択し、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する、
ように、さらにプログラムされていることを特徴とする請求項７に記載のコンテンツ配信サービスプロバイダ。
【請求項１３】
コンテンツを記憶し、配信するためのシステムであって、コンテンツを要求するための複数のエンドユーザーブラウザと、コンテンツを配信するための少なくとも１つのコンテンツプロバイダオリジナルサイトと、通信用のネットワークにより相互に接続している、コンテンツを記憶するための少なくとも１つのプロキシサーバーとを含むシステムにおいて、
予備取り出し帯域幅割当て値を使用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しするため方法であって、該方法は、
ｄ（ｂ）は、ｂの帯域幅単位が前記コンテンツを予備取り出しするために利用された場合に観察された単位遅延であり、congestion（Util）は、congestion（Util）＝β／(Utilθ＋α)＋φ、または、congestion（Util）＝β× (1.0 - Util)α＋φ、として表すことができる混雑関数であり、Utilは、最大ネットワーク帯域幅に対して利用されるネットワーク帯域幅の比率を表し、パラメータα、β、およびφが、前記混雑関数を帯域幅利用比率と応答遅延との関係を示す混雑曲線に適合させるために利用される場合において、ｂの帯域幅単位を利用して、サイズsize（ｏ）のコンテンツｏの検索時間を、ret（ｏ）＝congestion × size（ｏ）× ｄ（ｂ）、としてモデル化する段階と、
Ｐは、予備取り出し帯域幅の大きさであり、Ｂは、前記システムにとって有効な全帯域幅であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、少なくとも１つのプロキシサーバー内に記憶されていないコンテンツに対するエンドユーザーブラウザ要求を検索するためにシステムが利用する帯域幅の大きさであり、σ（Ｐ）は、帯域幅がＰである場合のキャッシュの新しさおよび有効性の数値であり、ｕ（ｔ）は、ユーザーの接続アクセス速度である場合において、時刻ｔ0において、少なくとも１つのコンテンツプロバイダオリジナルサイトから取り出したコンテンツについて、少なくとも１つのプロキシサーバーが観察した遅延の量を、ret（Ｐ）＝congestion（（Ｐ＋ｒ（ｔ0））／Ｂ）×ｒ（ｔ0）×ｄ、としてモデル化する段階と、
δret（Ｐ）／δＰ＝０を解くことにより、最適の予備取り出し帯域幅割当ての数値Ｐを計算する段階と、
最適の予備取り出し帯域幅割当ての数値Ｐを利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含むことを特徴とする方法。
【請求項１４】
前記方法は、さらに、最悪の場合の帯域幅利用の推定値を考慮に入れる調整済みの予備取り出し帯域幅割当ての数値を計算するためのものであって、該方法は、さらに、
Ｐについて、現在の帯域幅消費量（Ｒ＝ｒ（ｔ0））を利用して、δret（Ｐ）／δＰ＝０を解く段階と、
現在の帯域幅消費量（Ｒ＝ｒ（ｔ0））を利用して、ret（Ｐ）を計算する段階と、
ｐが今後の参照の度合である場合に、時刻ｔ0までのｒ（ｔ）の性質を示す履歴関数ｈr（ｔ）を利用して、期間［ｔ0，ｔ0＋ret（Ｐ）×ｐ］内の最大の帯域幅消費量Ｒmaxを推定する段階と、
最大の帯域幅消費量の推定値（Ｒ＝Ｒmax）を利用してδret（Ｐ）／δＰ＝０を解くことにより、調整済みの予備取り出し帯域幅割当ての数値Ｐadjustedを計算する段階と、
調整済みの予備取り出し帯域幅割当ての数値Ｐadjustedを利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含むことを特徴とする請求項１３に記載の予備取り出し帯域幅割当て値を利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しするための方法。
【請求項１５】
前記方法は、さらに、平均帯域幅利用の推定値を考慮に入れる平均予備取り出し帯域幅割当ての数値を計算するためのものであって、該方法は、さらに、
最大の帯域幅消費量の推定値Ｒmax）を利用して、Δｔ＝ret（Ｐadjusted）を計算する段階と、
【数２３】
0003575428.tif 000042
が、帯域幅消費量についての予備知識または履歴関数ｈr（ｔ）により推定される場合において、帯域幅の平均使用幅を
【数２４】
0003575428.tif 000043
と定義する段階と、
UtilavgおよびＰavgを利用して、予想検索時間Retexp（Ｐavg）を定義する段階と、
δretexp（Ｐavg）／δＰavg＝０を解くことによって、推定的な平均予備取り出し帯域幅割当ての数値Ｐavgを計算する段階と、
前記平均予備取り出し帯域幅割当ての数値Ｐavgを利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含むことを特徴とする請求項１４記載の予備取り出し帯域幅割当て値を利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しするための方法。
【請求項１６】
前記方法は、
各コンテンツＯIに対する、問い合わせ頻度（Ｏi）、更新頻度（Ｏi）および期限切れ時間（Ｏi）は、キャッシュログファイルから入手され、ｃ1、ｃ2およびｃ3は、前の期間からの統計または一定の時間間隔における経験的計算を利用して割り当てることができる配列係数である場合において、コンテンツＯIを予備取り出しするための優先順位の数値を、
【数２５】
0003575428.tif 000044
として計算する段階と、
計算した優先順位の数値と、所与の予備取り出し帯域幅とを利用して、次のΔｔ単位時間内に予備取り出しする一組のコンテンツＯpを選択する段階と、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する段階と
をさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１７】
前記方法は、
【数２６】
0003575428.tif 000045
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる古いオブジェクトの予想数を
【数２７】
0003575428.tif 000046
として計算する段階と、size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数２８】
0003575428.tif 000047
を維持しながら、
【数２９】
0003575428.tif 000048
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択する段階と、
一組のコンテンツＯpから、次のΔｔ時間単位内に、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
をさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１８】
前記方法は、
Δｔ時間単位中における、オブジェクトｏiに対する予想アクセス回数は、Δｔ×ｑ（ｏi）であり、
【数３０】
0003575428.tif 000049
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる新しいオブジェクトの予想数を、
【数３１】
0003575428.tif 000050
として計算する段階と、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数３２】
0003575428.tif 000051
を維持しながら、
【数３３】
0003575428.tif 000052
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択する段階と、
一組のコンテンツＯpから、次のΔｔ時間単位内に、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
をさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１９】
コンテンツを記憶し、配信するためのシステムであって、コンテンツを要求するための複数のエンドユーザーブラウザと、コンテンツを配信するための少なくとも１つのコンテンツプロバイダオリジナルサイトと、通信用のネットワークにより相互に接続している、コンテンツを記憶するための少なくとも１つのプロキシサーバーとを含むシステムにおいて、
予備取り出し接続の数を使用して、少なくとも１つのプロキシサーバーに、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しさせるための方法であって、該方法は、
congestion（Util）は、congestion（Util）＝β／(Utilθ＋α)＋φ、または、congestion（Util）＝β× (1.0 - Util)α＋φ、として表すことができる混雑関数であり、Utilは、許可された接続の最大数に対して開放されている接続の比率を表し、パラメータα、β、およびφが、前記混雑関数を統計的に得られたシステムリソース利用と応答遅延との関係を示す混雑曲線に適合させるために利用される場合において、サイズsize（ｏ）のコンテンツｏの検索時間を、ret（ｏ）＝congestion × size（ｏ）、としてモデル化する段階と、
Ｐは、予備取り出し接続の数であり、Ｂは、許可された接続の最大数であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、少なくとも１つのプロキシサーバー内に記憶されていないコンテンツを要求により取り出すために、前記システムが利用する接続の数であり、σ（Ｐ）は、帯域幅がＰである場合の、キャッシュの新しさおよび有効性の数値であり、ｕ（ｔ）は、ユーザー接続アクセス速度である場合において、時刻ｔ0において、少なくとも１つのコンテンツプロバイダオリジナルサイトから取り出したコンテンツについて、少なくとも１つのプロキシサーバーにおいて観察された遅延の量を、ret（Ｐ）＝congestion（（Ｐ＋ｒ（ｔ0）＋ｕ（ｔ0））／Ｂ）×（ｕ（ｔ0）＋ｒ（ｔ0））×平均的オブジェクトサイズ、としてモデル化する段階と、
δret（Ｐ）／δＰ＝０を解くことにより、最適の予備取り出し接続数Ｐを計算する段階と、最適の予備取り出し接続数Ｐを使用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含むことを特徴とする方法。
【請求項２０】
前記方法は、さらに、最悪の場合の接続利用の推定値を考慮に入れる調整済みの予備取り出し接続数を計算するためのものであって、該方法は、さらに、
Ｐについて、現在の使用接続数（Ｒ＝ｒ（ｔ0））を利用して、δret（Ｐ）／δＰ＝０を解く段階と、
ＲおよびＰを使用して計算した前記混雑を利用して、Ｐのコンテンツを予備取り出しするために必要な時間の長さρを見出す段階と、
ｐは、Ｐのコンテンツを予備取り出しするのに必要な時間である場合において、時刻ｔ0までのｒ（ｔ）の性質を示す履歴関数ｈr（ｔ）を使用して、期間［ｔ0，ｔ0＋ｐ］内における要求による取り出し接続の最大数Ｒmaxを推定する段階と、
要求による取り出し接続の最大数の推定値（Ｒ＝Ｒmax）を利用して、δret（Ｐ）／δＰ＝０を解くことにより、調整済みの予備取り出し接続数Ｐadjustedを計算する段階と、
最適の予備取り出し接続数Ｐadjustedを利用して、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含むことを特徴とする請求項１９に記載の予備取り出し接続の数を使用して、少なくとも１つのプロキシサーバーに、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しさせるための方法。
【請求項２１】
前記方法が、さらに、平均的な接続利用の推定値を考慮に入れる平均的な予備取り出し接続数を計算するためのものであって、該方法が、さらに、
Δｔを、Ｐadjustedの接続を予備取り出しするために必要な、最悪の場合の時間の長さとして定義する段階と、
【数３４】
0003575428.tif 000053
が、予備取り出し接続についての予備知識または履歴関数ｈr（ｔ）を利用して推定される場合において、帯域幅の平均使用幅を、
【数３５】
0003575428.tif 000054
と定義する段階と、
UtilavgおよびＰavgを使用して、予想検索時間Retexp（Ｐavg）を定義する段階と、
δretexp（Ｐavg）／δＰavg＝０を解くことによって、平均的な予備取り出し接続数の推定値Ｐavgを計算する段階と、
平均的な予備取り出し接続数Ｐavgにより、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
を含む請求項２０に記載の予備取り出し接続の数を使用して、少なくとも１つのプロキシサーバーに、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しさせるための方法。
【請求項２２】
前記方法は、
各コンテンツＯIに対する、問い合わせ頻度（Ｏi）、更新頻度（Ｏi）および期限切れ時間（Ｏi）は、キャッシュログファイルから入手され、ｃ1、ｃ2およびｃ3は、前の期間からの統計または一定の時間間隔における経験的計算を利用して割り当てることができる配列係数である場合において、コンテンツＯIを予備取り出しするための優先順位の数値を、
【数３６】
0003575428.tif 000055
として計算する段階と、
計算した優先順位の数値と、所与のネットワーク接続の数とを利用して、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択する段階と、
少なくとも１つのプロキシサーバーに対して、この一組のコンテンツＯpを通信する段階と
をさらに含むことを特徴とする請求項１９に記載の方法。
【請求項２３】
前記方法は、
【数３７】
0003575428.tif 000056
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる古いオブジェクトの予想数を、
【数３８】
0003575428.tif 000057
として計算する段階と、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数３９】
0003575428.tif 000058
を維持しながら、
【数４０】
0003575428.tif 000059
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択する段階と、
一組のコンテンツＯpから、次のΔ単位時間内に、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
をさらに含むことを特徴とする請求項１９に記載の方法。
【請求項２４】
前記方法は、
Δｔ時間単位中における、オブジェクトｏiに対する予想アクセス回数は、Δｔ×ｑ（ｏi）であり、
【数４１】
0003575428.tif 000060
であり、ｑ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）問い合わせ確率であり、Ｏは、一組のオブジェクトであり、ｕ（ｏi）は、すべてのｏi∈Ｏに対する（単位時間の間の）更新確率であり、ｌｒ（ｏi）は、すべてのｏi∈Ｏに対する最後の検索時間である場合において、次のΔｔ単位時間内にアクセスされる新しいオブジェクトの予想数を【数４２】
0003575428.tif 000061
として計算する段階と、
size（ｏi）は、すべてのｏi∈Ｏに対するサイズであり、Ｐは、予備取り出し帯域幅である場合において、真のステートメントとして、
【数４３】
0003575428.tif 000062
を維持しながら、
【数４４】
0003575428.tif 000063
を最大にするための０−１ナップザックアルゴリズムを利用して、次のΔｔ単位時間内にアクセスされる古いオブジェクトの数が最小になるように、次のΔｔ単位時間内に予備取り出しするための一組のコンテンツＯpを選択する段階と、
一組のコンテンツＯpから、次のΔ単位時間内に、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを予備取り出しする段階と
をさらに含むことを特徴とする請求項１９に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概して、コンテンツ配信（ｃｏｎｔｅｎｔ  ｄｅｌｉｖｅｒｙ）ネットワークに関し、好ましい実施形態の場合には、Ｗｅｂコンテンツを効率的に取り出し、またリフレッシュする目的で、インテリジェントネットワーク帯域幅およびシステムリソースを使用するための方法および装置に関する。
【０００２】
【従来の技術】
Ｗｅｂの性能は、コンテンツプロバイダの間の分化の最も重要なポイントである。主要なＷｅｂサイトが混乱状態にあり、また低速状態にあることが、大量のＷｅｂトラフィックを克服しようとしている各社が当面している困難な問題を証明している。インターネットのバックボーン技術が発達するにつれて、ネットワーク帯域幅を改善し、Ｗｅｂコンテンツの検索時間を短縮するために、サービス管理の品質のような多くの革新が使用されてきた。しかし、インフラストラクチャに関するこれらの改善は、インターネット内の任意のある点で発生するトラフィックの問題を解決することはできない。例えば、図１の場合には、日本のネットワーク１２内のエンドユーザー１０が、米国のネットワーク１６内のコンテンツプロバイダオリジナルＷｅｂサイト１４内の、あるページにアクセスしようとしている。この要求は、コンテンツプロバイダオリジナルＷｅｂサイト１４に届く前に、いくつかのインターネットサービスプロバイダ（ＩＳＰ）のゲートウェイ１８、２０および２２を通過する。ゲートウェイのボトルネックと、ユーザーとコンテンツプロバイダオリジナルＷｅｂサイト１４との間のインターネット経路に沿った他の遅延要因とのために、ゲートウェイのエンドユーザー側で、プロキシサーバーを利用するコンテンツ取出し／リフレッシュ方法を使用すれば、応答時間を短縮することができる。
【０００３】
図２は、複数の非特定Ｗｅｂサイト２８および３０に接続しているキャッシュシステム２６を含む、通常のＷｅｂコンテンツ配信およびキャッシュスキーム２４である。キャッシュシステム２６は、プロキシサーバーまたはキャッシュサーバー３２およびキャッシュ３４からなる。別の方法としては、図２のキャッシュシステム２６の代わりに、コンテンツ配信サービスプロバイダとすでに加入者契約を結んでいるＷｅｂサイトに接続しているコンテンツ配信サービスプロバイダおよびミラーサイトを利用することができる。これら加入者Ｗｅｂサイトは、監視するためのコンテンツ配信サービスプロバイダにコンテンツを配信する（ｄｅｌｉｖｅｒｙ）が、コンテンツが変更された場合、必ずしもコンテンツ配信サービスプロバイダに通知しない。さらに、キャッシュ３４は、プロキシキャッシュ、縁部キャッシュ（ｅｄｇｅ  ｃａｃｈｅ）、フロントエンドキャッシュ、逆キャッシュ（ｒｅｖｅｒｓｅ  ｃａｃｈｅ）等であってもよいことを理解すべきである。
【０００４】
図２の場合、コンテンツがＷｅｂサイトからキャッシュ３４に配信されると、メタ記述またはメタデータと呼ばれるヘッダが、コンテンツと一緒に配信される。メタデータはコンテンツのサブセットであってもよいし、またはコンテンツのある種の特性を表示することもできる。例えば、メタデータは、最後に修正した日付、ある時期にコンテンツが期限切れになる推定値、コンテンツが直ちに期限切れになるか、またはキャッシュすべきでないという表示を含むことができる。コンテンツおよびメタデータが配信された後で、メタデータが、キャッシュ３４内にコンテンツを記憶するように表示している場合には、コンテンツが、キャッシュ３４に記憶される。
【０００５】
ユーザー３６（ユーザー１）が、Ｗｅｂサイト２８（Ｗｅｂサイト１）からあるページ（例えば、ｉｎｄｅｘ．ｈｔｍｌ）へのアクセスを要求した場合には、ユーザー１のＷｅｂブラウザは、最初に、Ｗｅｂサイト１のドメイン名に対応するインターネットプロトコル（ＩＰ）アドレスを見出すために、要求をドメイン名サーバー（ＤＮＳ）に送る。図２の例の場合のように、キャッシュシステム２６を利用した場合には、ＷｅｂブラウザをＷｅｂサイト１にではなく、プロキシサーバー３２に送ることができる。その後で、プロキシサーバー３２は、要求したコンテンツがキャッシュ３４内に存在するかどうかを判断する。
【０００６】
しかし、要求したコンテンツがキャッシュ３４内で見出せたとしても、キャッシュ３４内のコンテンツが最新のものであるかどうかを判断しなければならない。この問題は、データベース同期として説明することができる。すなわち、キャッシュ３４およびＷｅｂサイト１としては、同じコンテンツを持つことが望ましい。しかし、すでに説明したように、加入者Ｗｅｂサイトは、そのコンテンツが変更されたとき、それをプロキシサーバー３２に知らせることができない。それ故、プロキシサーバー３２は、コンテンツが最新のものであることを容易に判断できるように、キャッシュ３４内に記憶している、要求されたコンテンツに関連するメタデータをチェックする。
【０００７】
キャッシュ３４内で要求されたコンテンツが見出され、メタデータが期限切れの推定日時が、まだ来ていないことを示している場合には、ある種のキャッシュシステムは、単に、コンテンツをユーザー１に直接配信する。しかし、もっと高度なキャッシュシステムの場合には、必要なコンテンツが、最後に更新された日時に関する情報を求めて、Ｗｅｂサイト１に要求を送ることができる。キャッシュ３４への最後のリフレッシュ以降にコンテンツが更新されている場合には、キャッシュ３４内に現在入っているコンテンツは最新のものではなくなり、最新のコンテンツが、ユーザー１に配信される前に、Ｗｅｂサイト１からキャッシュ３４に配信される。しかし、コンテンツが変更されたかどうかを判断するためにＷｅｂサイトをチェックするこのプロセスは、より広い帯域幅またはシステムリソース利用を必要とすることも理解すべきである。
【０００８】
同様に、キャッシュ３４内で要求されたコンテンツを見出したが、そのコンテンツが直ちに時間切れになるものである場合には、ある種のキャッシュシステムは、単に、Ｗｅｂサイト１からコンテンツを取り出し、それをユーザー１に配信する。しかし、ユーザーが、データが最新のものであるかどうかの確認を要求した場合には、ある種のキャッシュシステムは、必要なコンテンツが最後に更新された日時に関する情報を求めて、Ｗｅｂサイト１に要求を送ることができる。キャッシュ３４に対する最後のフレッシュの前にコンテンツが更新された場合には、コンテンツは依然として最新のものであり、キャッシュシステムは、そのコンテンツが「直ちに期限切れになる」状態であっても、それをユーザー１に配信する。
【０００９】
要求されたコンテンツがキャッシュ３４内に入っていない場合には、プロキシサーバー３２は、必要なＷｅｂページ（例えば、ｉｎｄｅｘ．ｈｔｍｌ）のテキストを取り出すために、Ｗｅｂサイト１に要求を送る。ユーザー１のＷｅｂブラウザが、ｉｎｄｅｘ．ｈｔｍｌを受信した後で、ブラウザはｈｔｍｌページを分析し、画像またはアイコンのような、任意の埋設されているオブジェクトを取り出すために、Ｗｅｂサイト１に追加要求を発行することができる。しかし、キャッシュシステム２６を利用している場合には、プロキシサーバー３２は、最初に、埋設されているオブジェクトがキャッシュ３４内で有効であるかどうかを判断する。すべてのトラフィック（すなわち、データの流れ）は、プロキシサーバー３２内のログファイル３８内に記録される。ログファイル３８は、要求の発行が行われる位置のＩＰアドレス、取り出したオブジェクトのＵＲＬ、各性質のタイムスタンプ等を含むことができる。プロキシサーバー３２は、通常、多くのエンドユーザーにより共有され、そのため、同じ様な利害関係を持つユーザーが、キャッシュ３４内のコンテンツにアクセスできることを特筆しておく。すなわち、ユーザー１があるページにアクセスし、そのページがキャッシュ３４に記憶されている場合であって、他のユーザー４０（ユーザー２）が同じページを要求した場合には、プロキシサーバー３２は、単に、キャッシュ３４内のコンテンツをユーザー２に供給することができる。
【００１０】
ある種のキャッシュシステムの場合には、コンテンツに対するエンドユーザーの要求がない場合でも、リフレッシュを実行することができる。ユーザーからの要求を受信しない場合でも、キャッシュは、要求を、Ｗｅｂサイトのコンテンツが、最後に更新された日時を判断するために、キャッシュ内にコンテンツを配信するＷｅｂサイトに要求を送ることができる。コンテンツが変更された場合には、そのコンテンツは、Ｗｅｂサイトからキャッシュに、リフレッシュされて送り返される。それ故、エンドユーザーからコンテンツに対する要求を受信した場合には、キャッシュ内のコンテンツが最新のものであり、直ちにエンドユーザーに直接送信される可能性が高い。
【００１１】
ネットワーク帯域幅リソースおよびシステムリソースは、インターネットに接続しているエンドユーザーおよびプロキシサーバーにとって重要なものである。エンドユーザーおよびプロキシサーバーは、帯域幅および接続リソースを入手するために、相互に「競合している」と見なすことができる。しかし、エンドユーザーおよびプロキシサーバーの目標は同じである。すなわち、最も速い応答時間をユーザーに供給することである。
【００１２】
図３は、通常のプロキシサーバー４２が利用することができる接続を示す。個々の要求に対する最も速い応答時間は、要求されたコンテンツが、プロキシサーバーキャッシュ内に位置していて、最新のものである場合に達成することができる。そのため、プロキシサーバー４２は、インターネットを通してＷｅｂサイトからコンテンツを取り出す必要はない。この状況は、キャッシュ「ヒット」と呼ばれる。キャッシュヒット率が非常に高い場合には、システム全体を通して、最も速い応答時間が達成される。それ故、予め取り出しておき４４、リフレッシュしておき、確認しておけば、最新のコンテンツが増え、キャッシュヒット率がもっと高くなり、一人のエンドユーザーに対する応答時間がもっと速くなることをハッキリと理解することができるだろう。しかし、折り合いをつける必要がある。非常に高いキャッシュヒット率を達成するためには、プロキシサーバー４２は、コンテンツのリフレッシュ、予備取り出し、取出し、または予備確認４４をキャッシュに対して行うために、ネットワークの大きなパーセンテージの帯域幅を使用しなければならない。しかし、大量のフレッシュにもかかわらず、エンドユーザーが、キャッシュ内にまだリフレッシュしていない、または単にキャッシュに位置していないコンテンツを要求する事態が起こる場合がある。そのような場合には、プロキシサーバー４２は、Ｗｅｂサイトからそのコンテンツを要求するために、要求取出し４６を発行しなければならない。しかし、他のコンテンツをリフレッシュするために、帯域幅の過度の帯域が現在利用されている場合には、Ｗｅｂサイトからの要求コンテンツを取り出すために、キャッシュにとって有効な帯域幅が不十分である場合があり、コンテンツ取り出しの応答時間が、実際にはかなり長くなる場合がある。それ故、キャッシュリフレッシュおよび予備取り出しは、Ｗｅｂサイトのコンテンツ取出しと競合し、Ｗｅｂサイトのコンテンツ取出しに悪影響を及ぼす恐れがあることを理解すべきである。
【００１３】
もちろん、任意の瞬間に、利用していない帯域幅がある場合には、要求しているエンドユーザーが利用することができるように、最も優先権の高いコンテンツをキャッシュ内に予め取り出しておくことは合理的な方法である。例えば、Ｗｅｂサイトからコンテンツを取り出すために、帯域幅の２０％を利用していると仮定した場合、エンドユーザーがコンテンツを要求した場合には、キャッシュヒットは起こらない。上記取出しのために、帯域幅の２０％が利用されている場合には、帯域幅の８０％は利用されていない。この利用されていない帯域幅は、キャッシュ内に他のコンテンツを予め取り出すために利用することができる。そのため、エンドユーザーが、そのコンテンツを要求した場合には、該コンテンツは、エンドユーザーにとって有効となる。
【００１４】
ネットワーク帯域幅に対するキャッシュサーバーリフレッシュ、予備取り出し、Ｗｅｂサイトコンテンツ取り出しの間で競合が行われ、またこれらのプロセスに帯域幅が割り当てられる結果、ユーザーの応答時間が影響を受けるので、最善の応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのための帯域幅の最適な割当てを決定するための方法が必要になる。さらに、帯域幅制限のために、キャッシュ内に記憶しているコンテンツのほんの一部しかリフレッシュまたは予備取り出しできない場合には、キャッシュヒット率を最大にし、応答時間を最短にするために、どのコンテンツをリフレッシュし、予め取り出すべきかを決定する方法が必要になる。
【００１５】
【発明が解決しようとする課題】
それ故、本発明の実施形態の一つの利点は、最短のエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのための帯域幅の最適な割当てを決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュ用のインテリジェントネットワーク帯域幅およびシステムリソースを利用するための方法および装置を提供することである。
【００１６】
本発明の実施形態のもう一つの利点は、有効なネットワーク帯域幅の変動を考慮に入れながら、最短のエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのための帯域幅の最適な割当てを決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行う目的で、インテリジェントネットワーク帯域幅、およびシステムリソースを利用するための方法および装置を提供することである。
【００１７】
本発明の実施形態のさらにもう一つの利点は、最短のエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのためのネットワーク接続の最適な数を決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行う目的で、インテリジェントネットワーク帯域幅およびシステムリソースを利用するための方法および装置を提供することである。
【００１８】
本発明の実施形態のさらにもう一つの利点は、ネットワーク接続の有効数の変動を考慮に入れながら、最短のエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しを行う目的で、ネットワーク接続の最適な数を決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行うために、インテリジェントネットワーク帯域幅およびシステムリソースを利用するための方法および装置を提供することである。
【００１９】
本発明の実施形態のさらにもう一つの利点は、キャッシュヒット率および応答時間を最適なものにするために、どのコンテンツをリフレッシュし、予備取り出しを行うべきかを決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行うために、インテリジェントネットワーク帯域幅およびシステムリソースを利用するための方法および装置を提供することである。
【００２０】
【課題を解決するための手段】
上記および他の利点は、最適な予備取り出し帯域幅割当ての数値を利用して、少なくとも１つのプロキシサーバーが、少なくとも１つのコンテンツプロバイダオリジナルサイトからコンテンツを取り出すことができるようにするためのコンテンツ配信サービスプロバイダにより達成することができる。コンテンツ配信サービスプロバイダは、コンテンツを要求するための複数のエンドユーザーブラウザ、上記コンテンツを配信するための少なくとも１つのコンテンツプロバイダオリジナルサイト、および上記コンテンツを記憶するための少なくとも１つのプロキシサーバーを含むコンテンツを記憶し、配信するためのシステムの一部である。これらの素子は、通信用のネットワークにより相互に接続している。
【００２１】
コンテンツ配信サービスプロバイダは、下記の目的のためにプログラムされている。
・  ｄ（ｂ）は、ｂの帯域幅単位が、コンテンツの予備取り出しに利用された場合に観察された単位遅延であり、ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）は、ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β／（Ｕｔｉｌθ＋α）＋φ、または、ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β×（１．０−Ｕｔｉｌ）α＋φで表すことができる場合に、ｂの帯域幅単位を利用して、サイズ、ｓｉｚｅ（ｏ）のコンテンツｏの検索時間を、ｒｅｔ（ｏ）＝ｃｏｎｇｅｓｔｉｏｎ×ｓｉｚｅ（ｏ）×ｄ（ｂ）、としてモデル化すること。
・  Ｐは、予備取り出し帯域幅であり、Ｂは、システムにとって有効な全帯域幅であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、少なくとも１つのプロキシサーバー内に記憶されていないコンテンツに対するエンドユーザーブラウザ要求を検索するために、システムが利用する帯域幅の広さであり、σ（Ｐ）は、帯域幅がＰである場合のキャッシュの新しさ（ｆｒｅｓｈｎｅｓｓ）および有効性（ａｖａｉｌａｂｉｌｉｔｙ）の数値であり、ｕ（ｔ）は、ユーザーのアクセス速度である場合に、時刻ｔ０において、少なくとも１つのコンテンツプロバイダオリジナルサイトから取り出したコンテンツについて、少なくとも１つのプロキシサーバーが観察した遅延の量を、ｒｅｔ（ｐ）＝ｃｏｎｇｅｓｔｉｏｎ（（Ｐ＋ｒ（ｔ０））／Ｂ）×ｒ（ｔ０）×ｄ、としてモデル化すること。
・  δｒｅｔ（Ｐ）／δＰ＝０を解くことにより、最適の予備取り出し帯域幅割当ての数値を計算すること。
・  少なくとも１つのプロキシサーバーへ、最適の予備取り出し帯域幅割当て値Ｐを通信すること。
【００２２】
当業者であれば、添付の図面を参照しながら、本発明の実施形態の下記の詳細な説明を読めば、本発明の実施形態の上記および他の目的、機能および利点を理解することができるだろう。
【００２３】
【発明の実施の形態】
好ましい実施形態の以下の説明においては、本明細書の一部を形成し、本発明を実施することができる例示としての特定の実施形態を示す添付の図面を参照する。他の実施形態を利用することもできるし、本発明の好ましい実施形態の範囲から逸脱することなしに構造を変更することができることを理解すべきである。
【００２４】
コンテンツに対する個々のエンドユーザーの要求を処理するための最も速い応答時間は、要求コンテンツが、プロキシサーバーのキャッシュ内に位置していて、最新（古くなっていない）場合に達成することができる。この状態をキャッシュ「ヒット」と呼ぶ。キャッシュヒットがある場合には、キャッシュから要求を行っているエンドユーザーのブラウザへ直接配信することができ、プロキシサーバーは、インターネットを通してコンテンツプロバイダのＷｅｂサイトからコンテンツを取り出す必要はない。キャッシュヒット率が非常に高い場合には、システム全体を通して、最も速い応答時間が達成される。それ故、キャッシュ内に記憶しているリフレッシュ、予備取り出し、および予備確認の数を増やせば、最新のコンテンツが増え、キャッシュヒットの数が増大し、一人のエンドユーザーに対する応答時間がもっと短くなることを理解することができるだろう。しかし、折り合いをつける必要がある。非常に高いキャッシュヒット率を達成するためには、プロキシサーバーは、コンテンツをリフレッシュし、キャッシュ内に予備取り出しするために、ネットワークの大きなパーセンテージの帯域幅を利用しなければならない。しかし、大量のリフレッシュを行っても、エンドユーザーが、キャッシュ内にまだリフレッシュしていないコンテンツを要求する事態が起こる場合がある。そのような場合には、キャッシュは、Ｗｅｂサイトからそのコンテンツを要求しなければならない。しかし、他のコンテンツをリフレッシュするために帯域幅の過度の帯域が現在利用されている場合には、Ｗｅｂサイトからの要求コンテンツを取り出すために、キャッシュにとって有効な帯域幅が不十分である場合があり、コンテンツ取り出しの応答時間が、現実にかなり長くなる場合がある。それ故、キャッシュリフレッシュおよび予備取り出しは、Ｗｅｂサイトのコンテンツ取り出しと競合し、Ｗｅｂサイトのコンテンツ取り出しに悪影響を及ぼす恐れがあることを理解すべきである。
【００２５】
結合した帯域幅利用が少ない場合には、すなわち、結合ユーザー帯域幅利用および予備取り出し帯域幅利用が、有効な最大バックボーン帯域幅よりかなり下方にある場合には、ユーザーの要求および関連する応答時間は影響を受けない。しかし、すでに説明したように、結合帯域幅利用が最大有効帯域幅に近づくと、ネットワークを通してサービスを受けるユーザー要求を処理する際に、有意な待ち時間が発生する場合がある。
【００２６】
本明細書で使用する応答時間とは、単に、ユーザーの要求と、ユーザーへのコンテンツの配信との間の実際の時間ではないことを理解すべきである。この実際の時間は、予測することができないし、エンドユーザーの物理的位置、および必要なコンテンツにアクセスするために、ネットワーク内において通過しなければならないゲートウェイの数のような要因により異なる。それ故、この場合における、応答時間のより合理的な表現は、キャッシュヒット率である。キャッシュヒット率は、そのコンテンツに対して要求を行った場合に、エンドユーザーが、キャッシュからコンテンツに直接アクセスすることができる回数の百分率である。すなわち、エンドユーザーが、キャッシュから直接必要なコンテンツに、１０回のうち８回アクセスできた場合には、キャッシュヒット率は８０％になる。
【００２７】
また、「リフレッシュ」「取り出し」、「予備取り出し」、「確認」および「予備確認」という用語は、これらの用語が、同じ方法で、帯域幅またはシステムリソースを必要とするという点で類似していることを特筆しておく。それ故、本明細書の説明においては、「リフレッシュ」、「取り出し」、「予備取り出し」、「確認」または「予備確認」しか参照しないが、本明細書に記載する技術は、「リフレッシュ」、「取り出し」、「予備取り出し」、「確認」および「予備確認」に適用される。
【００２８】
図４は、本発明のある実施形態のコンテンツを記憶し、配信するためのシステム４８である。図４の場合には、キャッシュシステム５０は、コンテンツ配信サービスプロバイダ５２の制御の下で動作する。上記プロバイダ５２は、最短の応答時間を達成するためのキャッシュサーバーリフレッシュおよび予備取り出し用の最適帯域幅割当てを決定することができ、最短の応答時間を達成するためのキャッシュサーバーリフレッシュおよび予備取り出しのためのネットワーク接続の最適な数を決定することができ、または、キャッシュヒット率および応答時間を最適にするために、キャッシュ内に記憶しているコンテンツの中のどれをリフレッシュ、または予備取り出しすべきかを決定することができる。コンテンツ配信サービスプロバイダ５２の一例としては、「効率的にコンテンツを配信するためのシステムおよび方法」という名称の２０００年４月７日付の、米国係属特許出願第０９／５４５，８０５号が開示している、「ＣａｃｈｅＰｏｒｔａｌ（キャッシュポータル）」（商標）がある。上記米国特許出願は、引用によって本明細書の記載に援用する。図４のコンテンツ配信サービスプロバイダ５２は、多数のキャッシュシステムを任意に制御する独立のサーバーであってもよいし、または、コンテンツサービスプロバイダ５２は、本明細書に記載するように、各キャッシュシステム５０内のプロキシサーバー５４の一部であってもよい。
【００２９】
＜最適な予備取り出し帯域幅の決定＞
キャッシュ内にコンテンツを予備取り出しするために予約しておかなければならないネットワーク帯域幅の最適な幅を決定するための方法について説明する。Ｂを、システムにとって有効な全帯域幅とし、ｐ（ｔ）を、キャッシュ内にコンテンツを予備取り出しするために使用する帯域幅の幅とする。予備取り出しを行う必要があるコンテンツは、ユーザーのアクセス頻度およびキャッシュの新しさにより異なり、キャッシュの新しさは、キャッシュを更新するために使用する帯域幅の幅により異なる。予備取り出しする帯域幅ｐ（ｔ）および他のパラメータが分かれば、キャッシュの新しさおよびσ（ｐ（ｔ））の有効性を維持できると仮定する。その場合、ユーザーアクセス速度ｕ（ｔ）が分かれば、実効帯域幅のσ（ｐ（ｔ））×ｕ（ｔ）をキャッシュ（すなわち、最新のデータに対するキャッシュヒット）から入手することができる。従って、コンテンツのｒ（ｔ）＝（１−σ（ｐ（ｔ）））×ｕ（ｔ）を、ネットワークを通してＷｅｂサイトから取り出さなければならない。（すなわち、データはキャッシュ内に位置していないか、または取り出されていない）。
【００３０】
ユーザーのアクセス速度は、時間と共に変動する。それ故、時刻ｔ０までのｒ（ｔ）の性質を示す関数ｈｒ（ｔ）（すなわち、ｔ＜ｔ０に対するｈｒ（ｔ）＝ｒ（ｔ）が、決定でき、経験的に入手することができ、インターネットサービスプロバイダ（ＩＳＰ）が供給することができると仮定する。時刻ｔ０においては、予め取り出す帯域幅の幅ｐが必要となるので、ｐ（ｔ）＝Ｐである場合には、ネットワークで観察される全検索時間は最も短くなる。
【００３１】
ｂの帯域幅単位を利用するサイズ、ｓｉｚｅ（ｏ）のコンテンツＯの検索時間は、ｒｅｔ（ｏ）＝ｃｏｎｇｅｓｔｉｏｎ×ｓｉｚｅ（ｏ）×ｄ（ｂ）、としてモデル化することができる。この場合、ｄ（ｂ）は、ｂの帯域幅単位が、コンテンツの検索に利用された場合に観察された単位遅延である。パラメータ、ｃｏｎｇｅｓｔｉｏｎは、オブジェクトの大きさには左右されないが、ネットワーク帯域幅の利用により異なることを特筆しておく。
【００３２】
図５は、帯域幅利用と混雑（ｃｏｎｇｅｓｔｉｏｎ）の間の関係である。図５の遅延５４は、ユーザーの要求に対する応答時間と等しいことを理解すべきである。図５に示すように、０％から８０％までの帯域幅利用は（参照番号５６参照）、遅延内に僅かな変化しかを起こさない。しかし、帯域幅利用が８０％、そしてその後で９０％を超すと、ユーザーの要求に対する応答時間は劇的に増大する。帯域幅利用の回数がさらに多くなると、コンテンツに対する異なる要求の衝突が起こる。衝突が起こると、ＣＰＵはその要求を再度送信し始めることができる。衝突の回数がもっと多くなると、要求の再送信の回数がさらに増え、まもなく、すべての要求が相互に衝突し、性能の低下がおこり、完全に停止する場合もある。図５は、任意のタイプの帯域幅利用をカバーすることを理解すべきである。
【００３３】
この性質は、ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β／（Ｕｔｉｌθ＋α）＋φおよびｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β×（１．０−Ｕｔｉｌ）α＋φを含む種々の関数で近似することができる。この場合、Ｕｔｉｌは、最大ネットワーク帯域幅に対する、利用したネットワーク帯域幅の比率を表し、パラメータ、α、β、φおよびθは、混雑関数（ｃｏｎｇｅｓｔｉｏｎ  ｆｕｎｃｔｉｏｎ）を混雑曲線（ｃｏｎｇｅｓｔｉｏｎ  ｃｕｒｖｅ）に適当に適合させるために利用され、統計的に、経験的に入手することができ、またはＩＳＰにより供給される。データ取出しリンクの性質を表示する混雑関数が分かっている場合には、時刻ｔ０において取り出したデータ要求により観察した遅延の量は、下記式によりモデル化することができる。
ｒｅｔ（Ｐ）＝ｃｏｎｇｅｓｔｉｏｎ（（Ｐ＋ｒ（ｔ０））／Ｂ）×ｒ（ｔ０）×ｄ
ここで、Ｂは全帯域幅であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、キャッシュ内に入っていないユーザー要求を検索するために、システムが利用している帯域幅の幅である。
【００３４】
例えば、図６は、予備取り出しのために利用する帯域幅とエンドユーザーの応答時間との間の関係を、関数Ｐ０／（Ｂ−Ｒ）で示す。このグラフのために使用した混雑関数は、ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝１．０／（１．０−Ｕｔｉｌ６）である。この関数は、第一の近似に対応することを特筆しておく。この場合、α＝−１．０、β＝−１．０、θ＝６、φ＝０．０である。すでに説明したように、帯域幅利用は、実際には、二つの成分に分解される。第一の成分はユーザーの要求を処理し、第二の成分は予備取り出しを処理する。図６が示すように、予備取り出し用に利用する帯域幅の幅は、０％から６０％に増大し（参照番号５８参照）、エンドユーザーの応答時間は短くなる。しかし、すでに説明したように、予備取り出しのためにあまりに広い帯域幅を使用すると、応答時間が長くなる。図６は、予備取り出しに６０％以上の帯域幅を利用した場合、全体の応答時間が、８０％のところで増大を始め、応答時間が劇的に増大する様子を示す。図６は、帯域幅利用が、（コンテンツ予備取り出しのために、余分な全帯域幅を割り当てることにより）１００％に近づいた場合、応答時間が悪影響を受ける様子を示す。
【００３５】
帯域幅利用が１００％に近づくにつれて、ネットワークを通してコンテンツを配信しようとする要求が渋滞するので、衝突の回数がますます多くなる。すでに処理中の要求を処理するのに帯域幅が不十分であるので、新しい要求は引続き衝突および渋滞を続ける。その結果、トラフィックは完全に渋滞してしまって、その状態を解消することができない。不完全な要求が処理されず、他の不完全なユーザーの要求と引続き衝突を続けるので、実際の通信は停止し、その結果、トラフィックは停止してしまう。このようなトラフィックの完全な渋滞を防止する一つの方法は、要求の受付を制限することである。要求受付の制限は、帯域幅利用が１００％に近づくのを許さない防衛手段の一つの形式である。例えば、帯域幅利用が、８０％のマークまで増大するのを許すが、８０％になると、ユーザーの要求は受け付けないという手段である。いつでも有効な状態に維持されている残りの２０％は、すでに進行中の要求を処理するために利用される。現在の要求の処理が完了するまで、他のリフレッシュまたは予備取り出しは計画されない。もちろん、防衛手段として余りに多くの帯域幅が留保した場合には、ユーザーの応答時間は最も短くはならない。
【００３６】
図６の利用曲線は、ユーザーの応答時間が最も短い場合、最適な予備取り出し帯域幅割当てが、勾配が０である曲線の最も低い点で見出せることを示す。この最適な予備取り出し帯域幅割当ての数値は、Ｐに対する下記の微分方程式を解くことにより計算することができる。
δｒｅｔ（Ｐ）／δＰ＝０
【００３７】
＜変動する帯域幅利用の考察＞
上記方法は、ｒ（ｔ）が、ある時間の間の定数（Ｒ＝ｒ（ｔ０））であると仮定することにより上記微分方程式を解く。しかし、すでに説明したように、キャッシュ内に位置していないコンテンツを検索するために使用する帯域幅の幅は一定ではなく、時間の関数（ｒ（ｔ））である。さらに、「帯域幅の消費量は、オブジェクトを取り出すのに十分な時間の間一定である」という仮定が成立しない場合には、ｒ（ｔ）の数値の僅かな増大が検索時間を非常に長くする場合がある。
【００３８】
例えば、すでに説明したように、図６は、帯域幅の２０％の一定部分が、ユーザー要求用に利用されると仮定した場合の、予備取り出し用に使用する帯域幅利用曲線を示す。しかし、ユーザーの要求のために利用する帯域幅の百分率が、２０％から変動した場合には、予備取り出し用の６０％の帯域幅も変動する。すなわち、コンテンツを取り出すためのエンドユーザーの帯域幅利用パターンが、２０％の点の付近で変動した場合には、予備取り出し用の帯域幅利用も、６０％の点の付近で変動する。しかし、図６は、予備取り出し用の６０％に対する最適な帯域幅利用が予備取り出し用の８０％に対する帯域幅の不十分な百分率に非常に近くなり、そのため、これらの変動が、応答時間のかなりの延長を起こす恐れがある場合を示す。
【００３９】
この変動を、エンドユーザーが利用する帯域幅の幅の中に収容する一つの方法は、図６の例に示す計算した最適な点を使用しないで、それより低い点を使用する方法である。図６は、予備取り出し用の帯域幅利用が、６０％から５０％に低下した場合に、応答時間にわずかな違いが起こるが、その変化は、エンドユーザー要求が使用する帯域幅内の変動を収容するための安全限界の余分な手段を提供する。
【００４０】
予備取り出しのための最適な帯域幅利用は、多数の他の要因によって異なることを理解すべきである。例えば、コンテンツを予備取り出しするために使用するアルゴリズムは不正確な場合があり、その結果、多数のユーザーの要求が、Ｗｅｂサイトからコンテンツにアクセスしなければならなくなる。キャッシュ内に記憶されているコンテンツは、また、頻繁に変化する場合があり、その結果、ユーザーの要求は、頻繁に古くなったコンテンツに遭遇することになり、Ｗｅｂサイトからコンテンツにアクセスしなければならなくなる。これらの要因は、Ｗｅｂサイトからコンテンツを取り出すのに使用する、帯域幅の百分率に影響を与え、そのため、エンドユーザーの要求の全応答時間に影響を与える。
【００４１】
＜予備取り出し帯域幅の調整＞
帯域幅消費量の小さな変動が、検索時間の長い延長を引き起こす確率を小さくするために、帯域幅消費量の関数のもう一つの性質を考察することができる。この性質は、（それを有効である場合には）リソース予約契約を利用することにより、または検索帯域幅およびまた予備取り出し帯域幅の最大幅を推定するための履歴（ｈｉｓｔｏｒｙ）ｈｒ（ｔ）を利用することによって見出すことができる。
【００４２】
予備取り出し帯域幅は、下記のように、もう一つの性質を使用して調整することができる。
・  Ｐに対する現在の帯域幅消費量（Ｒ＝ｒ（ｔ０））を使用して、δｒｅｔ（Ｐ）／δＰ＝０を解くこと。
・  現在の帯域幅消費量（Ｒ＝ｒ（ｔ０））を使用して、ｒｅｔ（Ｐ）を見出すこと。
・  履歴ｈｒ（ｔ）を使用して、期間［ｔ０，ｔ０＋ｒｅｔ（Ｐ）×ｐ］内の最大の帯域幅消費量Ｒｍａｘを推定すること。この場合、ｐは今後の参照の度合である。・  Ｐａｄｊｕｓｔｅｄに対する帯域幅の最大要件（Ｒ＝Ｒｍａｘ）を使用して、δｒｅｔ（Ｐ）／δＰ＝０を解くこと。
【００４３】
Ｐａｄｊｕｓｔｅｄを、帯域幅消費量の最悪の場合の性質の推定値を使用して計算すること。Ｐａｄｊｕｓｔｅｄは、今後のことを全然考慮しないで計算したＰより小さい可能性が高い。
【００４４】
＜使用の改善＞
前節においては、帯域幅利用の最悪の場合の性質の推定により予備取り出し帯域幅を選択することにより、エンドユーザー変動を考慮に入れる最悪の場合の方法について説明した。この方法は、ピークのユーザーアクセストラフィックを選択し、期間中、上記ピークは一定であると仮定する。その後で、このピーク値は、最適な帯域幅予備取り出し使用を発生するために使用され、特定の式の形で表される。しかし、この方法は、有効な帯域幅利用を不必要なほど低減する場合がある。この節においては、最悪の場合の帯域幅を使用しないで帯域幅利用を予測しようとする、改善された方法について説明する。
【００４５】
この節で説明する基本的なコンセプトは、エンドユーザーのアクセスパターンをチェックし、その後で、予測した今後のエンドユーザーの帯域幅利用に基づいて、予備取り出しのために使用する帯域幅を再計算することである。それ故、例えば、一定期間の間に、エンドユーザーの帯域幅利用がある量だけ変化した場合には、次の一定期間中にそれを予測することができ、エンドユーザーの帯域幅利用は、その割合で増大を続ける場合がある。予測したエンドユーザーの帯域幅利用に基づいて、予備取り出しのために使用する帯域幅の新しい数値を計算することができる。もちろん、エンドユーザーの帯域幅利用の変化が最小である場合には、エンドユーザーの帯域幅利用の新しい予測数値を予備取り出しのために使用するために、帯域幅を再計算する必要は全然ない。それ故、予備取り出しのために使用する帯域幅の最適な百分率は、最適な応答時間を維持するために引続き再計算される。
【００４６】
予備取り出しのための最適な帯域幅使用のこの計算がスタートすると、ユーザーの要求に対してどれだけの帯域幅が使用されるのか、また、予備取り出しのためにどれだけの帯域幅が使用されるのかについての最初の仮定が行われる。一例を挙げると、帯域幅の２０％がユーザーの要求のために使用され、６０％が予備取り出しのために使用され、これらの百分率により、二つの第二のユーザーの要求の応答時間が決定されると仮定する。一定期間（例えば、５分間）が経過した後で、ユーザーの要求のためにどれくらいの帯域幅が使用されるのか、また、予備取り出しのためにどれくらいの帯域幅が使用されるのかを決定するために、新しい計算が行われる。さらに、応答時間がもう一度測定される。上記百分率が、前の測定値より劇的に変化している場合には、その５分間の間にある傾向が発生したと仮定することができる。この傾向は、５分間より前に再計算を行った場合には恐らく検出することができたであろうから、再計算の時間をもっと早い時間（例えば、３分）に移動する。より早い時間に、帯域幅利用および応答時間を再計算することにより上記傾向を早期に検出することができ、帯域幅利用の調整も早期に行うことができる。
【００４７】
例えば、５分間の間に、エンドユーザーが利用した帯域幅が２０％ではなく、２５％であり、予備取り出しのために使用した帯域幅が６０％ではなく、５５％であったと決定されたと仮定する。これらの違いは、最初の帯域幅利用が最適なものではなく、調整が必要であったことを示す。
【００４８】
一方、５分後に、エンドユーザーが使用した帯域幅が２０％のままであり、予備取り出しのために使用した帯域幅が６０％のままであった場合には、帯域幅利用が、最適使用に近く、変更が必要ないことを示す。それ故、前の帯域幅の数字と５分後の帯域幅の数字の間に小さな違いが認められる場合には、再計算の点を（例えば、１０分後というように）後にずらすことができる。すなわち、帯域幅利用の数字が一定であり、最適値に近い限りは、帯域幅利用の数字および応答時間の再計算はあまり頻繁に起こらない。しかし、帯域幅利用の数字が、測定の度に変化する場合には、計算の間の時間を徐々に短くする。
【００４９】
予備取り出しのために使用する帯域幅の百分率は、本明細書で説明するように、予備取り出し、リフレッシュ、または、単に、キャッシュ内のコンテンツの現状を確認するために使用する帯域幅の百分率を意味することを理解すべきである。
【００５０】
さらに、エンドユーザーの帯域幅利用に対する今後の数値の予測は、必ずしも、簡単な線形予測ではないことも理解すべきである。それどころか、変動するエンドユーザーの帯域幅アクセスパターンを記述するために、複雑な関数を開発することができる。この方法の場合、変動するエンドユーザーの帯域幅のパターンも予測することができる。しかし、この改良した方法は、キャッシュシステムを増大する遅延応答時間の領域に入れる予備取り出し帯域幅利用となる、予測したエンドユーザーの帯域幅利用の数値を計算しない。その代わりに、上記計算は、良好なエンドユーザーの応答時間を保存する予備取り出し帯域幅利用数を計算する。
【００５１】
Ｐと、Ｐａｄｊｕｓｔｅｄとの間の違いが非常に大きい場合には、（推定した）最悪の場合の消費量の代わりに、（推定した）平均の帯域幅消費量を考慮に入れるために、下記のように再調整することができる。
・  Δｔを推定最大使用帯域幅（Ｒｍａｘ）により計算したｒｅｔ（Ｐａｄｊｕｓｔｅｄ）×ｐとする。
・  平均使用を、
【数４５】
0003575428.tif 000002
と定義する。
・  ＵｔｉｌａｖｇおよびＰａｖｇを利用して、予想検索時間Ｒｅｔｅｘｐ（Ｐａｖｇ）を定義する。
・  Ｐａｖｇについて、δｒｅｔｅｘｐ（Ｐａｖｇ）／δＰａｖｇ＝０を解く。
【００５２】
Ｐａｖｇは、Ｐより小さく、Ｐａｄｊｕｓｔｅｄより大きい可能性が高い。さらに、Ｐａｖｇは、帯域幅消費量の今後の性質を考慮して計算されるので、帯域幅消費量の変化により影響を受ける可能性は少ない。さらに、最悪の場合の性質に基づいて計算していないので、帯域幅利用は最悪の場合より良好である可能性が高い。
【００５３】
この方法は、
【数４６】
0003575428.tif 000003
の数値を推定するための方法を必要とすることを特筆しておく。それ故、（リソース予約プロトコルを利用するシステムで有効な）帯域幅消費量についての予備知識が必要であり、または、システムの今後の性質を、その過去の性質についての有効な統計（ｈｒ（ｔ））を利用して推定しなければならない。この情報は、ＩＳＰにより近似または供給することができる。
【００５４】
＜オブジェクトのリフレッシュおよび予備取り出しのスケジューリング＞
予備取り出しのために利用すべき帯域幅の百分率が、ユーザーの実際のアクセスパターンに基づいて決定されると、次の段階において、エンドユーザーの問い合わせの頻度および更新の頻度に基づいて、予備取り出しの際に、どのコンテンツにより高い優先順位を与えるべきかが決定される。すなわち、所与の有効なネットワーク帯域幅、および記憶しているコンテンツに対する所与の問い合わせ頻度および所与の更新頻度に対して、この節は、オブジェクトのリフレッシュスケジュールおよび予備取り出しスケジュールを決定する。すなわち、どのコンテンツをリフレッシュすべきか、予備取り出しすべきかが決定される。
【００５５】
予備取り出しの優先順位が最も高いコンテンツは、頻繁に問い合わせがあり、頻繁に更新されるコンテンツである。次の二つの最善の選択は、頻繁に問い合わせがあるが、頻繁には更新されないコンテンツ、または非常に頻繁に問い合わせはないが、非常に頻繁に更新が行われるコンテンツである。予備取り出しされる可能性が最も低いコンテンツは、頻繁に問い合わせが行われず、頻繁に更新されないコンテンツである。
【００５６】
あるオブジェクトＯｉの取り出し、またはリフレッシュの優先順位は、
【数４７】
0003575428.tif 000004
として定義することができる。この場合、ｃ１、ｃ２およびｃ３は、問い合わせ頻度、更新頻度および期限切れ時間の要因に適用される配列係数（ｏｒｄｅｒ  ｃｏｅｆｆｉｃｉｅｎｔｓ）である。優先順位の順位が高ければ高いほど、そのオブジェクトは、リフレッシュまたは予備取り出しのために早期にスケジュールされる。
【００５７】
優先順位の式から推測できるように、二つの情報の問い合わせ頻度および更新頻度が同じである場合には、期限切れ時間が関連要因になる。例えば、キャッシュ内に二つの情報が位置していると仮定する。すべての他のものが同じであり、一方が１分以内に期限切れになるように設定され、他方が５分経過後に期限切れになるように設定されていると仮定する。この例の場合、１分以内に記期限切れになるように設定されているコンテンツを最初に取り出すか、またはリフレッシュしなければならない。何故なら、他方のコンテンツは予備取り出し、またはリフレッシュを行う時間に余裕があるからである。
【００５８】
しかし、上記優先順位の式には、配列係数ｃ１、ｃ２およびｃ３が存在することを特筆しておく。これらの配列係数は、ネットワークの状況により異なり、問い合わせ頻度、更新頻度および期限切れ時期の加重が異なる場合があることを示している。さらに、最適のリフレッシュおよび予備取り出しスケジュールに対するｃ１、ｃ２およびｃ３の数値は、時間の経過と共に変化する場合がある。問題は、これらの配列係数の決定方法である。
【００５９】
ｃ１、ｃ２およびｃ３に対する新しい数値を、前の期間からの統計を利用して割り当てることができる。この方法は、問い合わせ頻度および更新頻度に基づくスケジューリングであると見なすことができる。例えば、ある方法は、配列係数の最初の一組でスタートし、その一組の係数が、各コンテンツの優先順位番号を決定する。その後で、これらの優先順位の数値は、予備取り出しに対する順位を決定する。この優先順位のリストに基づいて、コンテンツの予備取り出しを、ある時間の間行うことができ、エンドユーザーの平均応答時間を決定することができる。例えば、係数の元の組を、５秒の間の予備取り出しの優先順位を決めるために使用した場合、エンドユーザーの平均応答時間が２秒になるような優先順位のリストを作成したと仮定する。この時間の間に、すべてのエンドユーザーの要求に対して、応答時間データが記録されると、収集したデータを、ある意味では、異なる係数を利用して、その時間を再生するために利用することができる。それ故、他の５秒の間の、予備取り出しの優先順位を決めるために、新しい組の係数を利用することができ、新しいエンドユーザーの平均応答時間が発生する。このプロセスは、全アクセス時間を最短にする一組の係数が選択することができるまで、複数の期間に対して反復することができる。
【００６０】
別の例を説明すると、他の方法は、最初の組の配列係数を使用してスタートし、各コンテンツに対する優先順位番号、および予備取り出し優先順位を決定し、一連の各期間（例えば、Ｔ１、Ｔ２、Ｔ３等）の間の全応答時間を計算する。これらの期間の間、最適な応答時間を発生する一組の係数が見出されるまで配列係数を調整することができる。
【００６１】
さらに他の実施形態の場合には、リフレッシュおよび予備取り出しスケジュールを、要求したコンテンツがキャッシュ内に位置していないか、リフレッシュされていない確率を最低限度まで低減することにより入手することができる。問題は下記の通りである。Ｏを一組のオブジェクトとする。予備取り出し帯域幅がＰ、期間がΔｔ、すべてのｏｉ∈Ｏに対する、（単位時間の間の）問い合わせ確率がｑ（ｏｉ）、すべてのｏｉ∈Ｏに対する（単位時間の間の）更新確率がｕ（ｏｉ）、すべてのｏｉ∈Ｏに対する最後の検索時間がｌｒ（ｏｉ）、すべてのｏｉ∈Ｏに対するサイズがｓｉｚｅ（ｏｉ）、および現在の時間がＴである場合には、次のΔｔの間にアクセスした古いオブジェクトの数が最も少なくなるように、次のΔｔ時間単位内に予備取り出しするために一組のオブジェクトＯｐを選択する。
【００６２】
エンドユーザーのアクセスパターンは分かっているので、キャッシュ内に記憶しているコンテンツに対して、特定のコンテンツが、次にアクセスされる可能性を表す確率の数値を決定することができる。次のΔｔ時間単位の間にアクセスされる古いオブジェクトの予想の数字は、下記式により計算することができる。
【数４８】
0003575428.tif 000005
【００６３】
上記確率は、問い合わせ頻度および更新頻度に基づくもであることを特筆しておく。ｏｉがアクセスされる確率は、期限切れ時間で、問い合わせ頻度を除算したものに対応する。この方法と前の方法との間の違いは、上記式においては、過去を参照しないという点である。重要なことは、そのコンテンツが今後アクセスされる確率である。もちろん、そうするために、エンドユーザーのアクセスパターンを観察しなければならない。
【００６４】
上記式の他の部分は、ＯＩが古くなる確率である。更新頻度は統計的手段の中で、いつでも最も正確なものであるとは限らないことを特筆しておく。何故なら、特定の期間の間、特定のコンテンツ更新されたことが分かっていても、そのコンテンツが、その期間中に一回更新されたのか、または何回も更新されたのかが分からないからである。
【００６５】
ｏｉが、Δｔ時間単位内にアクセスされる確率は、ｐｒｏｂ（ｏｉがアクセスされる）＝１−（１−ｑ（ｏｉ））Δｔである。次のΔｔ時間単位中に、あるオブジェクトが古くなる確率は、
【数４９】
0003575428.tif 000006
である。
【００６６】
ユーザーが古いデータにアクセスする確率を最低限度まで低減するために、総和からそれを除去した場合、全体からみて減少が最も大きくなる一組のオブジェクトを選択しなければならない。すなわち、Ｏｐが、予備取り出しするためのオブジェクトの組である場合には、該オブジェクトが
【数５０】
0003575428.tif 000007
という有効な帯域幅内に収まる一方で、
【数５１】
0003575428.tif 000008
を最大にする必要がある。
【００６７】
この問題は、「０−１ナップザック問題」として周知の問題である。この問題を解くために有効である多くのアルゴリズムがある。これらのアルゴリズムの説明は、アルゴリズム関係の文献に記載されているので、この問題は、当業者であればよく理解することができる。選択したオブジェクトが検索されると、これらのオブジェクトの最後の更新時間を適当に更新しなければならない。
【００６８】
この問題の別の構成は、下記の通りであることを特筆しておく。古いオブジェクトの数をただ数える代わりに、各オブジェクトがアクセスされる予想回数を下記式により説明することができる。
【数５２】
0003575428.tif 000009
【００６９】
Δｔ時間単位中に、オブジェクトｏｉに対する予想アクセス回数は、Δｔ×ｑ（ｏｉ）である。それ故、代わりに下記の関数が最大になる。
【数５３】
0003575428.tif 000010
【００７０】
＜最適リソース利用率の決定＞
今までの節においては、コンテンツの予備取り出しおよびリフレッシュを行うために、最適なネットワーク帯域幅を選択するための技術について説明した。この節においては、ネットワーク帯域幅が十分であるが、システム（すなわち、キャッシュサーバーまたはプロキシサーバー）リソースが、ボトルネックになっている状況における、ネットワーク接続の最適な関数を選択するために適応させることができる。
【００７１】
Ｂを、プロキシサーバーが同時に開くことができる接続の数（すなわち、プロセスまたはスレッドの数）とする。Ｂは、ユーザー接続、コンテンツ接続および要求取出し接続の間で分割しなければならないことを特筆しておく。
【００７２】
ｐ（ｔ）は、オブジェクトを、時刻ｔで、キャッシュ内に予備取り出しするために使用する接続の数を示すものとする。要求により取り出さなければならないオブジェクトの数は、ユーザーアクセス頻度およびキャッシュの新しさにより異なることを特筆しておく。オブジェクトの予備取り出しを行うために、ｐ個の接続をすでに割り当て済みであると仮定する。また、これらｐ個の接続を使用して、キャッシュの新しさおよびσ（ｐ）の有効性を維持できるものと仮定する。時刻ｔにおいて、ｕ（ｔ）接続のユーザーアクセス率（すなわち、各要求が、一つの接続を利用するｕ（ｔ）要求）が分かっている場合には、σ（ｐ）×ｕ（ｔ）接続を、プロキシキャッシュからサービスすることができる。残りのｒ（ｔ）＝（１−σ（ｐ））×ｕ（ｔ）接続（すなわち、各要求が一つの接続を利用するｒ（ｔ）＝（１−σ（ｐ））×ｕ（ｔ）要求）は、ソースから要求により取り出さなければならない。
【００７３】
目標は、時刻ｔ０において、ｐ（ｔ０）＝Ｐである場合に、このプロキシサーバーのユーザーが観察した全検索時間（遅延）が最低限度に低減するような、接続Ｐの予備取り出し数を見出すことである。
【００７４】
＜検索時間および最適の予備取り出し帯域幅＞
サイズがｓｉｚｅ（ｏ）のあるオブジェクトを、プロキシサーバーから、またプロキシサーバーへ検索する時間は、ｒｅｔ（ｏ）＝ｃｏｎｇｅｓｔｉｏｎ×ｓｉｚｅ（ｏ）、としてモデル化することができる。この場合、パラメータ、ｃｏｎｇｅｓｔｉｏｎは、オブジェクトのサイズからは独立しているが、プロキシサーバーのところで開く同時接続の数に依存する。図７は、同時接続の数とｃｏｎｇｅｓｔｉｏｎとの間の関係を示す。この曲線は、図５の曲線とは異なる。しかし、近似した遅延関数６０を、システムリソース利用と遅延との間の関係用の遅延関数６２を表すために利用することができる。下記の二つの関数は、この目的のために利用することができる。
・  ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β／（Ｕｔｉｌθ＋α）＋φ、および、
・  ｃｏｎｇｅｓｔｉｏｎ（Ｕｔｉｌ）＝β×（１．０−Ｕｔｉｌ）α＋φ
ここで、Ｕｔｉｌは、曲線された接続の最大数に対する、開いた接続の比率を示し、パラメータ、α、β、φおよびθは、統計的に得られた混雑曲線に混雑関数を適当に当てはめるために利用される。
【００７５】
混雑関数が分かっている場合には、時刻ｔ０において、プロキシサーバーのところで観察した遅延の長さを下記式でモデル化することができる。
ｒｅｔ（Ｐ）＝ｃｏｎｇｅｓｔｉｏｎ（（Ｐ＋ｒ（ｔ０）＋ｕ（ｔ０））／Ｂ）×（ｕ（ｔ０）＋ｒ（ｔ０））×平均的オブジェクトサイズ
ここで、Ｂは、許可された接続の最大数であり、ｕ（ｔ）はユーザー要求の数であり、ｒ（ｔ）＝（１−σ（Ｐ））×ｕ（ｔ）は、キャッシュ内でリフレッシュされていないオブジェクトを要求により取り出すために必要な接続の数である。要求により取り出したコンテンツは、二回の遅延を経験することを特筆しておく。一方の遅延は、元のソースから取り出すための遅延であり、他方の遅延は、エンドユーザーに配信するための遅延である。
【００７６】
図６によれば、接続の数が最大値に近づくと、検索時間が悪影響を受ける。図６は、また検索時間が最も短くなる予備取り出し接続の最適な数があることも示す。この最適値は、Ｐに対して、下記の微分方程式を解くことにより計算することができる。
δｒｅｔ（Ｐ）／δＰ＝０
【００７７】
＜変動する接続の使用の考察＞
上記方法の大きな欠点は、ある期間の間、ｒ（ｔ）が一定である（Ｒ＝ｒ（ｔ０））であると仮定してのみ微分方程式を解くことができることである。しかし、キャッシュ内に位置していないオブジェクトを要求により取り出すのに必要な接続の数は一定ではなく、時間の関数である。さらに、ｒ（ｔ）の数値が少し増大すると、（図６にグラフで示す性質と同じように）検索時間が非常に長くなる場合がある。このような性質を防止するために、要求による取出し関数の今後の性質を考慮しなければならない。この性質は、許可された要求による取出しの関数を制限するか、またはその履歴ｈｒ（ｔ）を利用することによって見出すことができる。
【００７８】
＜予備取り出し接続の調整＞
今後の性質を使用する予備取り出し接続の数は、下記のように調整することができる。
・  現在の帯域幅消費量（Ｒ＝ｒ（ｔ０））を利用して、Ｐについてδｒｅｔ（Ｐ）／δＰ＝０を解く。
・  ＲおよびＰを利用して計算した混雑の数値を使用して、Ｐ個のオブジェクトを予備取り出しするために必要な時間の長さρを見出す。
・  履歴ｈｒ（ｔ）を利用して、期間［ｔ０，ｔ０＋ρ］の間の最大要求による取り出し接続を推定する。この場合、ρはＰ個の接続を予備取り出しするのに必要な時間である。
・  Ｐａｄｊｕｓｔｅｄについて、最大推定値（Ｒ＝Ｒｍａｘ）を使用して、δｒｅｔ（Ｐ）／δＰ＝０を再度解く。
【００７９】
Ｐａｄｊｕｓｔｅｄは、帯域幅消費量の最悪の場合の性質の推定により計算されるので、Ｐａｄｊｕｓｔｅｄは、将来のことを全然考慮しないで計算したＰより小さい可能性が高い。
【００８０】
＜利用の改善＞
上記方法は、ユーザーの要求の推定した最悪の場合および対応する要求による取出し要件により、予備取り出し接続の数を選択する。しかし、このことが、有効な帯域幅利用を不必要なほど低減する場合がある。
【００８１】
Ｐと、Ｐａｄｊｕｓｔｅｄとの間の違いが非常に大きい場合には、この問題は、（推定の）最悪の場合の帯域幅消費量ではなく、（推定）平均の帯域幅消費量を考慮して、Ｐを再調整することにより除去することができる。
・  Δｔを、Ｐａｄｊｕｓｔｅｄ接続を予備取り出しするために必要な時間（最悪の場合）の長さとする。
・  平均使用を下記式のように定義する。
【数５４】
0003575428.tif 000011
・  ＵｔｉｌａｖｇおよびＰａｖｇを使用して、予想検索時間Ｒｅｔｅｘｐ（Ｐａｖｇ）を定義する。
・  Ｐａｖｇについて、δｒｅｔｅｘｐ（Ｐａｖｇ）／δＰａｖｇ＝０を解く。
【００８２】
Ｐａｖｇは、Ｐより小さく、Ｐａｄｊｕｓｔｅｄより大きい可能性が高い。さらに、Ｐａｖｇは、今後の性質を考慮して計算されるので、帯域幅消費量の変化により影響を受ける可能性は低い。さらに、最悪の場合の性質に基づいて計算していないので、利用は、最悪の場合と比較すると良好である可能性が高い。
【００８３】
この方法は、
【数５５】
0003575428.tif 000012
の数値を推定するためのある方法を必要とすることを特筆しておく。予備知識が必要である場合もあるし、または、その過去の性質についての有効な統計（ｈｒ（ｔ））を使用して、システムの今後の性質を推定しなければならない場合もある。
【００８４】
＜コンテンツのリフレッシュおよび予備取り出しスケジューリング＞
この節においては、上記技術により決定することができる所与の数の予備取り出し接続に対する、オブジェクトの問い合わせ頻度および更新頻度に基づいて、オブジェクトの予備取り出しスケジュールを決定するための技術を説明する。
【００８５】
コンテンツＯｉの取り出しまたはリフレッシュの優先順位は、下記式のように定義することができる。
【数５６】
0003575428.tif 000013
ここで、ｃ１、ｃ２およびｃ３は、問い合わせ頻度、更新頻度および期限切れ時間の要因に適用される配列係数である。優先順位の数値が高ければ高いほど、そのコンテンツがリフレッシュまたは予備取り出しされる順位は早くなる。ｃ１、ｃ２およびｃ３は、ネットワークの状況により異なる場合があり、最適なリフレッシュおよび予備取り出しスケジュールに対するｃ１、ｃ２およびｃ３の数値は、時間の経過と共に変化することを特筆しておく。ｃ１、ｃ２およびｃ３の新しい数値は、前の時期からの統計により割り当てることができる。
【００８６】
Ｏを一組のオブジェクトとする。予備取り出し接続がＰ、期間がΔｔ、すべてのｏｉ∈Ｏに対する（単位時間の間の）問い合わせ確率がｑ（ｏｉ）、すべてのｏｉ∈Ｏに対する（単位時間の間の）更新確率がｕ（ｏｉ）、すべてのｏｉ∈Ｏに対する最後の検索時間がｌｒ（ｏｉ）、すべてのｏｉ∈Ｏに対するサイズがｓｉｚｅ（ｏｉ）、および現在の時間がｔである場合には、次のΔｔの間にアクセスする古いオブジェクトの数が最も少なくなるように、次のΔｔ時間単位内に予備取り出しするために、一組のオブジェクトＯｐを選択する。
【００８７】
＜スケジューリング技術＞
次のΔｔ時間単位内にアクセスされる古いオブジェクトの予想数は、下記式により計算することができる。
【数５７】
0003575428.tif 000014
【００８８】
ｏｉが、Δｔ時間単位内に少なくとも一回アクセスされる確率は、ｐｒｏｂ（ｏｉがアクセスされる）＝１−（１−ｑ（ｏｉ））Δｔである。次のΔｔ時間単位中に、あるオブジェクトが古くなる確率は、
【数５８】
0003575428.tif 000015
である。
【００８９】
ユーザーが、古いデータにアクセスする確率を最低限度まで低減するために、総和からそれを除去した場合、全体からみて減少が最も大きくなる一組のオブジェクトを選択しなければならない。すなわち、Ｏｐが、予備取り出しするためのオブジェクトの組である場合には、該オブジェクトが、
【数５９】
0003575428.tif 000016
という有効な接続数内に収まる一方で、
【数６０】
0003575428.tif 000017
を最大にする必要がある。
【００９０】
この問題は、「０−１ナップザックアルゴリズム」を利用して解くことができる。選択したオブジェクトが検索されると、これらのオブジェクトの最後の更新時間を適当に更新しなければならない。
【００９１】
この問題の別の構成は下記の通りであることを特筆しておく。古いオブジェクトの数をただ数える代わりに、古い各オブジェクトがアクセスされる予想回数を下記式により説明することができる。
【数６１】
0003575428.tif 000018
【００９２】
Δｔ時間単位中に、オブジェクトｏｉに対する予想アクセス回数は、Δｔ×ｑ（ｏｉ）である。それ故、代わりに下記の関数が最大になる。
【数６２】
0003575428.tif 000019
【００９３】
本発明の実施形態は、最も速いエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのを行う目的で、帯域幅の最適な割当てを決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行うため、インテリジェントネットワーク帯域幅、およびシステムリソースを使用するための方法および装置を提供する。さらに、本発明の実施形態は、有効なネットワーク帯域幅の変動を考慮に入れながら、最も速いエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのための帯域幅の最適な割当てを決定する。
【００９４】
本発明の実施形態は、最も速いエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しを行う目的で、ネットワーク接続の最適な数を決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行うため、インテリジェントネットワーク帯域幅、およびシステムリソースを使用するための方法および装置を提供する。本発明の実施形態は、また、ネットワーク接続の有効数の変動を考慮に入れながら、最も速いエンドユーザー応答時間を達成するために、キャッシュサーバーリフレッシュおよび予備取り出しのためのネットワーク接続の最適な数も決定する。
【００９５】
本発明の実施形態は、また、キャッシュヒット率および応答時間を最適にするために、どのコンテンツをリフレッシュし、予備取り出しすべきかを決定する効率的なＷｅｂコンテンツ取り出しおよびリフレッシュを行うために、インテリジェントネットワーク帯域幅およびシステムリソースを使用するための方法および装置も提供する。
【図面の簡単な説明】
【図１】エンドユーザーとＷｅｂサイトとの間の従来のコンテンツ配信経路の一例のブロック図である。
【図２】従来のキャッシュシステムの一例のブロック図である。
【図３】プロキシサーバーが利用することができる通常の接続の一例のブロック図である。
【図４】キャッシュサーバーリフレッシュおよび予備取り出しのための帯域幅の最適な割当てを決定するか、キャッシュサーバーリフレッシュおよび予備取り出し用のネットワーク接続の最適な数を決定するか、または本発明の実施形態に従ってユーザー応答時間を最短にするには、どのコンテンツをリフレッシュおよび予備取り出しすべきかを決定するためのコンテンツ配信サービスプロバイダを備える、例示としてのキャッシュシステムのブロック図である。
【図５】帯域幅利用と遅延との間の関係を示すグラフである。
【図６】予備取り出しのために利用した帯域幅の一部と、そこから、予備取り出しのために利用する帯域幅の最適な百分率が、本発明の実施形態により計算されるエンドユーザーの応答時間との間の関係を示すグラフである。
【図７】ネットワーク接続の数とエンドユーザーの応答時間との間の関係を示すグラフである。
【符号の説明】
４８  コンテンツを記憶し、配信するためのシステム
５０  キャッシュシステム
５２  コンテンツ配信サービスプロバイダ
５４  プロキシサーバー
【図１】
0003575428.tif 000064
【図２】
0003575428.tif 000065
【図３】
0003575428.tif 000066
【図４】
0003575428.tif 000067
【図５】
0003575428.tif 000068
【図６】
0003575428.tif 000069
【図７】
0003575428.tif 000070