(57)【特許請求の範囲】
【請求項１】
ｍ個のサーバＳ’＝｛Ｓ1，．．．，Ｓm｝、ｎ人の能動顧客Ｃ’＝｛Ｃ1，．．．，Ｃn｝、およびｇ個の地理的位置Ｇ’＝｛Ｇ1，．．．，Ｇg｝を持つコンテンツ配送システムにおいて、ｓｄｅｌkが、サーバＳkのサーバ遅延であり、ｎｄｅｌj,kが、サーバＳkからコンテンツを検索する際に、地理的位置Ｇjで、顧客が観察したネットワーク遅延であり、ｐjが顧客Ｃiの優先順位の値であり、ｃiが顧客Ｃiの全負荷であり、ｕi,jが、領域Ｇjから顧客Ｃiへの要求の一部であり、ａi,j,kが、サーバＳkにリダイレクトされた、領域Ｇjから顧客Ｃiへの要求の一部を表わすマッピングであり、ｓkがサーバＳkの負荷容量を表わす場合に、サーバ負荷を分配する方法であって、該方法が、平均観察応答時間を下記式で表わすステップと、
【数１】
0003546850.tif 000018
前記ＡＯＲＴを最小にしながら、顧客から特定のサーバへの要求を割り当てるマッピングを作成するステップとを含むことを特徴とする方法。
【請求項２】
さらに、全領域内の全顧客からの全要求を各Ｃi∈Ｃ’、Ｇg∈Ｇ’に対して下記式
【数２】
0003546850.tif 000019
のように特定のサーバに割り当てるステップを含むことを特徴とする請求項１記載の方法。
【請求項３】
さらに、各Ｓk∈Ｓ’に対して、下記式
【数３】
0003546850.tif 000020
のように確実に各サーバの負荷容量を超えないようにしながら、要求を特定のサーバに割り当てるステップを含むことを特徴とする請求項１記載の方法。
【請求項４】
さらに、各サーバの負荷をすべてのサーバのペアＳkおよびＳlに対して、下記式
【数４】
0003546850.tif 000021
のように、バランスがとれている状態Θから最大許容偏差範囲内でバランスさせながら要求を特定のサーバに割り当てるステップを含むことを特徴とする請求項１記載の方法。
【請求項５】
前記コンテンツ配送システムが、一つまたはそれ以上のサーバを追加、または一人またはそれ以上の顧客を削除した場合に、バランスがとれている状態Θから、最大許容偏差を超えない限り、各サーバの負荷が再分配されないことを特徴とする請求項４記載の方法。
【請求項６】
さらに、ＡＯＲＴnew≦（１＋Φ）×ＡＯＲＴoldの場合だけ、前記コンテンツ配送システムに一人またはそれ以上の顧客を追加するステップを含む方法であって、
ＡＯＲＴoldおよびＡＯＲＴnewは、下記式
【数５】
0003546850.tif 000022
および
【数６】
0003546850.tif 000023
が定義するＡＯＲＴの古い値と新しい値であり、
ここで、ａ'i,j,kは、一人またはそれ以上の顧客を追加したことによる新しいマッピングであり、
Φは、現在のクライアントに対するＡＯＲＴ内の許容できる変更であることを特徴とする請求項１記載の方法。
【請求項７】
さらに、前記マッピングを作成するために線形制約条件解決装置を使用するステップを含むことを特徴とする請求項１記載の方法。
【請求項８】
さらに、前記マッピングを作成するために非線形制約条件解決装置を使用するステップを含むことを特徴とする請求項１記載の方法。
【請求項９】
さらに、前記マッピングを作成する目的で、もっと小さなＡＯＲＴ値を生成するために、小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）に大きなａi,j,k値を割り当てるステップを含む発見的アルゴリズムを使用するステップを含むことを特徴とする請求項１記載の方法。
【請求項１０】
前記発見的アルゴリズムが、
Ｃi値をｃiの昇順に分類し、＜Ｃi，Ｇj＞のペアをｕi,jの昇順に分類し、Ｓk値をｓｄｅｌkの昇順に分類し、＜Ｇj，Ｓk＞のペアをｎｄｅｌj,kの昇順に分類することにより複数の分類リストを作成するステップと、
各リストの一番上の最も小さい値の項からスタートして、分類リストの数に等しい複数の三文字＜Ｃi，Ｇj，Ｓk＞を生成するために他のリストから比較可能な最小値の項を識別するステップと、
前記複数の三文字＜Ｃi，Ｇj，Ｓk＞から最も小さいｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ三文字＜Ｃi，Ｇj，Ｓk＞を選択するステップと、
前記選択した三文字＜Ｃi，Ｇj，Ｓk＞のサーバＳkに＜Ｃi，Ｇj＞ペアから残りの負荷を割り当てるステップと、
すべての＜Ｃi，Ｇj＞ペアからの負荷がサーバＳkに割り当てられるまで、各反復中に、Ｃi値および前のサーバ割当ての結果としての＜Ｃi，Ｇj＞のペアの値の変化を考慮に入れて、複数の分類リストの作成からスタートして、前記発見的アルゴリズムを反復して実行するステップとを含み、
前記発見的アルゴリズムの任意の反復中に、前記残りの負荷を処理するのに、前記サーバＳkの負荷容量が十分でない場合には、前記サーバＳkの残りの負荷を＜Ｃi，Ｇj＞の負荷のあるものに割り当て、＜Ｃi，Ｇj＞からの負荷の割り当てられていない部分を前記反復プロセス内に再挿入することを特徴とする請求項９記載の方法。
【請求項１１】
前記発見的アルゴリズムが、さらに、
Ｃi値を残りの負荷容量ｓkの降順に分類することにより負荷容量の優先順位付き分類リストを作成するステップと、
負荷容量の優先順位付き三文字＜Ｃi，Ｇj，Ｓk＞を生成するために、前記負荷容量の優先順位付きリスト内の一番上の最大値の項からスタートして、前記他のリストから比較することができる最小値の項を識別するステップと、
最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ前記一番上の三文字＜Ｃi，Ｇj，Ｓk＞の選択の際に、負荷容量の優先順位付き三文字＜Ｃi，Ｇj，Ｓk＞を考慮するステップと、
すべての＜Ｃi，Ｇj＞ペアからの負荷が、サーバＳkに割り当てられるまで、各反復中に、Ｃi値、＜Ｃi，Ｇj＞ペア、および前のサーバ割当ての結果としての残りの負荷容量の値の変化を考慮に入れて、複数の分類リストの作成からスタートして、前記発見的アルゴリズムを反復して実行するステップとを含むことを特徴とする請求項１０記載の方法。
【請求項１２】
前記発見的アルゴリズムが、さらに、
顧客ＣiのコンテンツがサーバＳk内に記憶されるコンテンツ入手可能な＜Ｃi，Ｓk＞のリストを作成するステップと、
コンテンツ入手可能な＜Ｃi，Ｓk＞ペアのリストの一部である最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ前記三文字＜Ｃi，Ｇj，Ｓk＞を選択するステップとを含み、
前記発見的アルゴリズムの任意の反復中に、同様に、コンテンツ入手可能な＜Ｃi，Ｓk＞のペアのリストの一部である三文字＜Ｃi，Ｇj，Ｓk＞が存在しない場合には、最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ適当な三文字＜Ｃi，Ｇj，Ｓk＞が選択され、顧客ＣiのデータがサーバＳkに送られることを特徴とする請求項１０記載の方法。
【請求項１３】
前記発見的アルゴリズムが、さらに、それに対して顧客ＣiのコンテンツをサーバＳk内に記憶する必要がない移動時間ペナルティの昇順のコンテンツ入手可能な＜Ｃi，Ｓk＞のペアのリストを作成するステップを含み、前記発見的アルゴリズムの任意の反復中に、同様に、コンテンツ入手可能な＜Ｃi，Ｓk＞ペアのリストの一部である三文字＜Ｃi，Ｇj，Ｓk＞が存在しない場合には、最小の組合せｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値および＜Ｃi，Ｓk＞移動時間ペナルティを持つ適当な三文字＜Ｃi，Ｇj，Ｓk＞が選択され、顧客ＣiのデータがサーバＳkに送られることを特徴とする請求項１２記載の方法。
【請求項１４】
さらに、ＨＴＴＰログを使用して非永続接続に対するｎｄｅｌj,kを推定するステップを含み、前記ＨＴＴＰログを使用して非永続接続に対するｎｄｅｌj,kを推定するステップが、
ｔcon_req_rec（ｉ＋１）が、（ｉ＋１）番目の対象物に対して、前記サーバによる接続要求メッセージ受信時間を表わし、ｔresp_send_end（ｉ）が、前記サーバのｉ番目の対象物を送信停止時間を表わす場合に、前記ＨＴＴＰログ内に記憶している情報から、推定往復遅延Δｒserver,clientを、ｔcon_req_rec（ｉ＋１）−ｔresp_send_end（ｉ）として計算するステップと、
ｔcon_req_recがある対象物に対する前記サーバによる接続要求メッセージの受信時間を表わし、ｔresp_send_endが前記サーバの前記対象物の送信停止時間を表わす場合に、前記応答時間を、下記式
【数７】
0003546850.tif 000024
により計算するステップとを含むことを特徴とする請求項１記載の方法。
【請求項１５】
さらに、ＨＴＴＰログを使用して永続接続に対するｎｄｅｌj,kを推定するステップを含み、前記ＨＴＴＰログを使用して永続接続に対するｎｄｅｌj,kを推定するステップが、
ｔcon_close_recが、前記サーバの前記永続接続をオフにするための要求受信時間を表わし、ｔresp_send_end（ｌａｓｔ）が、最後の要求に対する前記サーバの応答送信停止時間を表わす場合に、推定往復遅延Δｒserver,clientをｔcon_close_rec−ｔresp_send_end（ｌａｓｔ）として計算するステップと、
ｔcon_req_recが接続要求時間を表わす場合に、前記応答時間を、下記式
【数８】
0003546850.tif 000025
により計算するステップとを含むことを特徴とする請求項１記載の方法。
【請求項１６】
ＴＣＰログを使用してあるサーバからデータを検索しながら、ある地理的位置にいて、要求を行っている構成要素が観察した、バイト当りのネットワーク遅延αを推定するための方法において、該方法が、
ｔcon_estが、前記サーバとの接続が確立した時間を表わし、ｔack_sendが、前記サーバが、前記要求を行っている構成要素から受信した接続要求メッセージに対して受信通知を送信した時間を表わす場合に、ＴＣＰログ内に記憶している情報から、前記サーバと前記要求を行っている構成要素との間の直接往復遅延Δｒimmを計算するステップと、
ｔdata_send（ｈ）が、前記サーバのデータのｈ番目のバイトの送信時間を表わし、ｔack_receive（ｋ）が、前記サーバの前記データのｋ番目のバイト（ｋ≧ｈ）に対する受信通知受信時間を表わす場合に、計算した直接往復遅延Δｒimm、式ｔack_receive（ｋ）−ｔdata_send（ｈ）＝Δｒimm＋α×（ｋ−ｈ）、および前記ＴＣＰログ内に記憶している情報を使用してバイト当りのネットワーク遅延αを決定するステップとを含むことを特徴とする方法。
【請求項１７】
ＨＴＴＰログを使用して、非永続接続を通してあるサーバから対象物を検索しながら、ある地理的位置にいて要求を行っている構成要素が観察した応答時間を推定するための方法であって、該方法が、
ｔcon_req_rec（ｉ＋１）が、（ｉ＋１）番目の対象物に対する前記要求を行っている構成要素から前記サーバが接続要求メッセージを受信した時間を表わし、ｔresp_send_end（ｉ）が、前記サーバが前記要求を行っている構成要素に対するｉ番目の対象物の送信を停止した時間を表わす場合に、前記ＨＴＴＰログ内に記憶している情報から推定往復遅延Δｒserver,clientをｔcon_req_rec（ｉ＋１）−ｔresp_send_end（ｉ）として計算するステップと、
ｔcon_req_recが、前記サーバがある対象物に対して要求を行っている構成要素から接続要求メッセージを受信した時間を表し、
ｔresp_send_endが、前記サーバが前記要求を行っている構成要素への前記対象物の送信を停止した時間を表わす場合に、前記応答時間を下記式
【数９】
0003546850.tif 000026
により計算するステップとを含むことを特徴とする方法。
【請求項１８】
ＨＴＴＰログを使用して、永続接続を通してあるサーバから対象物を検索しながら、ある地理的位置にいて要求を行っている構成要素が観察した応答時間を推定するための方法であって、該方法が、
ｔcon_close_recが、前記サーバが永続接続オフ要求を受信した時間を表わし、ｔresp_send_end（ｌａｓｔ）が、前記サーバが最後の要求に対する応答送信停止時間を表わす場合に、推定往復遅延Δｒserver,clientを、ｔcon_close_rec−ｔresp_send_end（ｌａｓｔ）として計算するステップと、
ｔcon_req_recが、接続要時間を表わす場合に、前記応答時間を、下記式
【数１０】
0003546850.tif 000027
により計算するステップとを含むことを特徴とする方法。
【請求項１９】
ｍ個のサーバＳ’＝｛Ｓ1，．．．，Ｓm｝、ｎ人の能動顧客Ｃ’＝｛Ｃ1，．．．，Ｃn｝、およびｇ個の地理的位置Ｇ’＝｛Ｇ1，．．．，Ｇg｝を持つコンテンツ配送ネットワーク内において、サーバ負荷を分配するためのコンテンツ配送システムであって、該システムが、
サーバＳkのサーバ遅延ｓｄｅｌkと、サーバＳkからコンテンツを検索する際に、地理的位置Ｇjで顧客が観察したネットワーク遅延ｎｄｅｌj,kと、顧客Ｃiの優先順位の値ｐjと、顧客Ｃiの全負荷ｃiと、領域Ｇjから顧客Ｃiへの要求の一部ｕi,jと、サーバＳkにリダイレクトされた、領域Ｇjから顧客Ｃiへの要求の一部を表わすマッピングａi,j,kと、サーバＳkの負荷容量ｓkとを記憶するためのメモリと、
平均観察応答時間を下記式
【数１１】
0003546850.tif 000028
により表示し、ＡＯＲＴを最小にしながら、顧客から特定のサーバへの要求を割り当てるマッピングを作成するようにプログラムされているプロセッサとを備えることを特徴とするシステム。
【請求項２０】
前記プロセッサが、さらに、全領域内の全顧客からの全要求を、各Ｃi∈Ｃ’、Ｇg∈Ｇ’に対して下記式
【数１２】
0003546850.tif 000029
のように特定のサーバに割り当てるステップをのように割り当てるようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２１】
前記プロセッサが、さらに、各Ｓk∈Ｓ’に対して、下記式
【数１３】
0003546850.tif 000030
のように確実に各サーバのように確実に各サーバの負荷容量を超えないようにしながら、要求を特定のサーバに割り当てるようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２２】
前記プロセッサが、さらに、各サーバの負荷を、すべてのサーバのペアＳkおよびＳlに対して、下記式
【数１４】
0003546850.tif 000031
のように、バランスがとれている状態Θから最大許容偏差範囲内にバランスさせながら、要求を特定のサーバに割り当てるようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２３】
前記コンテンツ配送システムが、一つまたはそれ以上のサーバを追加、または一人またはそれ以上の顧客を削除した場合に、前記プロセッサが、バランスがとれている状態Θから、最大許容偏差を超えない限り、各サーバの負荷が再分配されないようにプログラムされていることを特徴とする請求項２２記載のシステム。
【請求項２４】
前記プロセッサが、さらに、ＡＯＲＴnew≦（１＋Φ）×ＡＯＲＴoldの場合だけ、前記コンテンツ配送システムに一人またはそれ以上の顧客を追加することができるようにプログラムされているシステムであって、
ＡＯＲＴoldおよびＡＯＲＴnewは、下記式
【数１５】
0003546850.tif 000032
および
【数１６】
0003546850.tif 000033
が定義するＡＯＲＴの古い値と新しい値であり、
ここで、ａ'i,j,kは、一人またはそれ以上の顧客を追加したことによる新しいマッピングであり、Θは、現在のクライアントに対するＡＯＲＴ内の許容できる変更であることを特徴とする請求項１９記載のシステム。
【請求項２５】
前記プロセッサが、さらに、前記マッピングを作成するために線形制約条件解決装置を使用するようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２６】
前記プロセッサが、さらに、前記マッピングを作成するために非線形制約条件解決装置を使用するようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２７】
前記プロセッサが、さらに、もっと小さな全ＡＯＲＴ値を生成するために、小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値に大きなａi,j,k値を割り当てることにより前記マッピングを作成するようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項２８】
前記プロセッサが、さらに、
Ｃi値をｃiの昇順に分類し、＜Ｃi，Ｇj＞のペアをｕi,jの昇順に分類し、Ｓk値をｓｄｅｌkの昇順に分類し、＜Ｇj，Ｓk＞のペアをｎｄｅｌj,kの昇順に分類することにより複数の分類リストを作成し、
各リスト内の一番上の最も小さい値の項からスタートして、分類リストの数に等しい複数の三文字＜Ｃi，Ｇj，Ｓk＞を生成するために他のリストから比較することができる最小値の項を識別し、
前記複数の三文字＜Ｃi，Ｇj，Ｓk＞から最も小さいｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ三文字＜Ｃi，Ｇj，Ｓk＞を選択し、
前記選択した三文字＜Ｃi，Ｇj，Ｓk＞のサーバＳkに＜Ｃi，Ｇj＞のペアから残りの負荷を割り当て、
すべての＜Ｃi，Ｇj＞ペアからの負荷がサーバＳkに割り当てられるまで、各反復中に、Ｃi値および前のサーバ割当ての結果としての＜Ｃi，Ｇj＞ペア内の値の変化を考慮に入れて、前記複数の分類リストの作成からスタートして、前記発見的アルゴリズムを反復して実行する、
ようにプログラムされていて、前記発見的アルゴリズムの任意の反復中に、前記残りの負荷を処理するのに、前記サーバＳkの負荷容量が十分でない場合には、前記サーバＳkの残りの負荷容量が、＜Ｃi，Ｇj＞の負荷のあるものに割り当てられ、＜Ｃi，Ｇj＞からの負荷の割り当てられていない部分を前記反復プロセス内に再挿入することを特徴とする請求項２７記載のシステム。
【請求項２９】
前記プロセッサが、さらに、Ｃi値を残りの負荷容量ｓkの降順に分類することにより負荷容量の優先順位付き分類リストを作成するように、負荷容量の優先順位付き三文字＜Ｃi，Ｇj，Ｓk＞を生成するために、前記負荷容量の優先順位付きリスト内の一番上の最大値の項からスタートして、前記他のリストから比較することができる最小値の項を識別するように、最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ前記一番上の三文字＜Ｃi，Ｇj，Ｓk＞の選択の際に、前記負荷容量の優先順位付き三文字＜Ｃi，Ｇj，Ｓk＞を考慮するように、すべての＜Ｃi，Ｇj＞ペアからの負荷が、サーバＳkに割り当てられるまで、各反復中に、Ｃi値、＜Ｃi，Ｇj＞ペア、および前のサーバ割当ての結果としての残りの負荷容量の値の変化を考慮に入れて、複数の分類リストの作成からスタートして、前記発見的アルゴリズムを反復して実行するようにプログラムされていることを特徴とする請求項２８記載のシステム。
【請求項３０】
前記プロセッサが、さらに、
顧客ＣiのコンテンツがサーバＳk内に記憶されるコンテンツ入手可能な＜Ｃi，Ｓk＞のペアのリストを作成し、
コンテンツ入手可能な＜Ｃi，Ｓk＞ペアのリストの一部である最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ前記三文字＜Ｃi，Ｇj，Ｓk＞を選択する、
ようにプログラムされていて、前記発見的アルゴリズムの任意の反復中に、同様に、コンテンツ入手可能な＜Ｃi，Ｓk＞ペアのリストの一部である三文字＜Ｃi，Ｇj，Ｓk＞が存在しない場合には、最小のｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ適当な三文字＜Ｃi，Ｇj，Ｓk＞が選択され、顧客ＣiのデータがサーバＳkに送られることを特徴とする請求項２８記載のシステム。
【請求項３１】
前記プロセッサが、さらに、
それに対して前記顧客ＣiのコンテンツをサーバＳk内に記憶されない移動時間ペナルティの昇順のコンテンツ入手可能な＜Ｃi，Ｓk＞ペアのリストを作成し、
前記発見的アルゴリズムの任意の反復中に、同様に、コンテンツ入手可能な＜Ｃi，Ｓk＞のペアのリストの一部である、三文字＜Ｃi，Ｇj，Ｓk＞が存在しない場合には、最小の組合せｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値、および＜Ｃi，Ｓk＞移動時間ペナルティを持つ適当な三文字＜Ｃi，Ｇj，Ｓk＞が選択され、顧客Ｃiの前記データがサーバＳkに送られることを特徴とする請求項３０記載のシステム。
【請求項３２】
前記プロセッサが、さらに、ｔcon_req_rec（ｉ＋１）が、（ｉ＋１）番目の対象物に対して前記サーバによる接続要求メッセージ受信時間を表わし、ｔresp_send_end（ｉ）が、前記サーバのｉ番目の対象物の送信停止時間を表わす場合に、前記ＨＴＴＰログ内に記憶している情報から推定往復遅延Δｒserver,clientをｔcon_req_rec（ｉ＋１）−ｔresp_send_end（ｉ）として計算し、
ｔcon_req_recが、ある対象物に対する前記サーバによる接続要求メッセージの受信時間を表わし、ｔresp_send_endが、前記サーバの前記対象物の送信停止時間を表わす場合に、前記応答時間を、下記式
【数１７】
0003546850.tif 000034
により計算することにより、
ＨＴＴＰログを使用して、非永続接続に対するｎｄｅｌj,kを推定するようにプログラムされていることを特徴とする請求項１９記載のシステム。
【請求項３３】
前記プロセッサが、さらに、
ｔcon_close_recが、前記サーバの前記永続接続をオフにするための要求受信時間を表わし、ｔresp_send_end（ｌａｓｔ）が、最後の要求に対する前記サーバの応答送信停止時間を表わす場合に、推定往復遅延Δｒserver,clientを、ｔcon_close_rec−ｔresp_send_end（ｌａｓｔ）として計算し、
ｔcon_req_recが、接続要求時間を表わす場合に、前記応答時間を、下記式
【数１８】
0003546850.tif 000035
により計算することにより、
ＨＴＴＰログを使用して、永続接続に対するｎｄｅｌj,kを推定するようにプログラムされていることを特徴とする請求項１９記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概して、コンテンツ配送システムに関し、好適な実施形態の場合には、ウェブ・コンテンツにアクセスするためのユーザの応答時間を最短にするコンテンツ・プロバイダ・サーバの負荷をインテリジェントに分配するためのシステムおよび方法に関する。
【０００２】
【従来の技術】
図１に示すように、従来のコンテンツ配送ネットワーク１０は、通常、複数のエンドユーザ１６（クライアント・ブラウザ）と、インターネットのような大型のワイド・エリア・ネットワーク１４上に分布している複数のコンテンツ・プロバイダ・サーバ１８を含む。ワイド・エリア・ネットワーク１４は、世界中の種々の地理的領域にほぼ対応するもっと小さなネットワーク２０を含むことができる。例えば、エンドユーザＡが、コンテンツ・プロバイダ・サーバ１８からのコンテンツ（例えば、ｈｔｍｌページおよび埋設対象物）に対する要求２２を行った場合には、コンテンツ・プロバイダ・サーバ１８は、要求されたコンテンツをエンドユーザＡに返送する。
【０００３】
【発明が解決しようとする課題】
しかし、上記要求およびコンテンツが、複数のネットワーク２０およびゲートウェイ２６を通過する時に発生する遅延により、エンドユーザＡから見た全体の応答時間が非常に長くなる場合がある。
【０００４】
全体の応答時間は、二つの要素、すなわち、ネットワーク遅延とサーバ遅延からなる。ネットワーク遅延は、すでに説明したように、要求およびコンテンツが、種々のネットワーク、およびネットワーク境界のところのゲートウェイを通過する際に発生する遅延である。サーバ遅延は、サーバが要求を実際に受信した場合の処理の際の遅延である。多くの場合、これら二つの遅延要素の間で折り合いがつけられる。
【０００５】
ミラー・サーバは、エンドユーザから見た場合のウェブの性能を改善するために使用されてきた。（ミラー・サーバ１２は、本明細書に定義するように、同様に、プロキシ・サーバおよびキャッシュを含むことができることを理解されたい。）図２に示すように、ミラー・サーバ１２を使用する従来のコンテンツ配送システム１０の場合には、コンテンツ・プロバイダ・サーバ１８からのコンテンツは、一つまたはそれ以上のミラー・サーバ１２内にコピーされる。その後で、例えば、エンドユーザＡが、そのコンテンツに対して、コンテンツ・プロバイダ・サーバ１８に要求２２を送信した場合には、上記要求は、そのコンテンツを記憶しているミラー・サーバＢに回される（リダイレクトされる）（参照番号２４参照）。ミラー・サーバは、多くの場合、地理的に、要求を行ったエンドユーザの近くに（または、論理的に近くに）位置しているので、ネットワーク遅延を短縮することができる、すなわち、全応答時間を短縮することができる。しかし、多くの場合、ミラー・サーバの位置および負荷が要求を行ったエンドユーザから見た実際の応答時間を決定する。
【０００６】
その結果、応答時間を短縮するために、二つの方法が使用されてきた。一方の方法は、位置をベースとする方法であり、他方の方法は負荷をベースとする方法である。位置をベースとする方法は、ワイド・エリア・ネットワーク１４、またはインターネットを、多くの場合、インターネットを形成する複数のネットワーク２０の周囲に組織された複数の領域に分割する。その場合、強力なミラー・サーバ１２が、各領域内に位置する。図２の例の場合には、ミラー・サーバＢは領域Ｃ内に位置する。この方法の目的は、コンテンツ要求を地理的にエンドユーザ１６に近いところに（または、論理的に近くに）位置するミラー・サーバ１２に再度割り当てることにより、エンドユーザ１６から見たネットワーク遅延を短縮することである。
【０００７】
位置をベースとする方法を使用する従来のコンテンツ配送システムの場合には、特定の領域内のすべてのエンドユーザは、その領域内のミラー・サーバに再度割り当てられる。このようなコンテンツ配送システムは、地域的な境界により制約され、エンドユーザを他の領域内のミラー・サーバに再度割り当てることができない。通常、この制約により全応答時間は速くなる。何故なら、地域的境界を通過する際に発生するネットワーク遅延を避けることができるからである。しかし、この制約があると、実際には、ミラー・サーバが過負荷になった場合には、全応答時間が長くなる場合がある。
【０００８】
例えば、図２に示すように、領域Ａ内の多くのエンドユーザ１６の要求が、ミラー・サーバＢに再度割り当てられたと仮定しよう。そのようなマッピングにより、ネットワーク遅延を最低限度まで短くすることはできるけれども、要求の数が、ミラー・サーバＢに対する負荷容量を超えた場合には、ミラー・サーバＢのサーバ遅延は劇的に長くなり、全応答時間が非常に長くなる。また、説明の便宜上、近隣の領域Ｄが要求されたコンテンツのコピーを記憶しているが、コンテンツに対する要求を数個しか受信していないミラー・サーバＥを含んでいると仮定しよう。その場合には、サーバ遅延は最も短くなる。この例の場合には、領域Ｃ内のエンドユーザの中のあるものが、領域Ｄ内のミラー・サーバＥに再度割り当てられた場合には、全平均応答時間は、実際に短くなるが、従来の位置をベースとする方法の地域的制限がそれを許さない。
【０００９】
一方、従来の負荷をベースとする方法の目的は、どれか一つのミラー・サーバが過負荷になるのを防止するために、すべてのミラー・サーバに負荷を平等に分配することである。負荷をベースとする方法を使用するコンテンツ配送システムは、地域的な境界を考慮しない。むしろ、上記システムは、実際の要求からの統計を維持し、すべてのミラー・サーバがほぼ等しい負荷を負担するようにこれらの統計に基づいてミラー・サーバの負荷のバランスをとろうとする。
【００１０】
負荷をベースとする方法は、ネットワーク遅延は無視できる仮定するが、このような仮定は必ずしも真実ではない。通常、負荷をバランスさせると、全応答時間が短くなる。何故なら、すべてのミラー・サーバが、合理的な負荷を負担していて、そのため、サーバ遅延が最も短くなるからである。しかし、負荷をバランスさせると、ミラー・サーバの負荷をバランスさせるために、エンドユーザの要求が、地域的境界を通して再度割り当てられる場合には、実際には、ネットワーク遅延が長くなり、全応答時間が長くなる場合がある。コンテンツ配送システムへの位置をベースとする方法は、また、各領域内で負荷をバランスさせる技術を使用することができることに留意されたい。
【００１１】
しかし、上記文献に記載されている通り、ミラー・サーバ内に記憶しているウェブ対象物が、（画像またはストリーミング媒体のように）大きい場合には、上記二つの方法は、両方ともうまく動作するが、大きな対象物の全応答時間は、ネットワーク状況に極度に大きく左右される。大部分の動的コンテンツの場合のように対象物の大きさがもっと小さい（約４ｋＢ以下）場合には、配送経路が地理的位置バリヤを横切らない限り、全応答時間は、ネットワーク遅延にそれほど大きく左右されない。しかし、反対に、動的コンテンツは、ミラー・サーバの負荷に極度に大きく左右される。何故なら、通常、その下に位置するデータベースまたはバックエンド・システムの規模を簡単に大きくすることができず、この部分が狭くなる恐れがあるからである。
【００１２】
【課題を解決するための手段】
それ故、本発明の実施形態の利点は、コンテンツ配送システムのユーザから見た全応答時間を最も短くする割当てを使用して要求を行っているユーザと同じ領域内のミラー・サーバにエンドユーザをリダイレクトするためのシステムおよび方法を提供することである。
【００１３】
本発明の実施形態のもう一つの利点は、負荷能力を考慮に入れて、ミラー・サーバの負荷のバランスをとる割当てを使用してエンドユーザをミラー・サーバにリダイレクトするためのシステムおよび方法を提供することである。
【００１４】
本発明の実施形態のさらにもう一つの利点は、コンテンツ配送システムのユーザから見た全応答時間を最も短くする割当てを使用して、要求を行っているユーザと同じ領域、または他の領域内のミラー・サーバにエンドユーザをリダイレクトするためのシステムおよび方法を提供することである。この場合、負荷バランス制限が守られる限り、新しいミラー・サーバ、または顧客コンテンツ・プロバイダのサービス・ターミネーションの追加によるリソースの増加により負荷の再配分は起こらない。
【００１５】
本発明の実施形態のさらにもう一つの利点は、コンテンツ配送システムのユーザから見た全応答時間を最も短くする割当てを使用して、要求を行っているユーザと同じ領域、または他の領域内のミラー・サーバにエンドユーザをリダイレクトするためのシステムおよび方法を提供することである。この場合、全応答時間が指定のしきい値以下に維持されている限り、新しい顧客コンテンツ・プロバイダが追加されるだけである。
【００１６】
本発明の実施形態のさらにもう一つの利点は、コンテンツ配送システムのユーザから見た全応答時間を最も短くする割当てを使用して要求を行っているユーザと同じ領域、または他の領域内のミラー・サーバにエンドユーザをリダイレクトするためのシステムおよび方法を提供することである。この場合、負荷または現在の顧客が変化しても、全応答時間は、指定のしきい値を超えるほど大きく変化しない。
【００１７】
上記および他の利点は、ｍ個のサーバＳ’＝｛Ｓ1，．．．，Ｓm｝、ｎ人の能動顧客Ｃ’＝｛Ｃ1，．．．，Ｃn｝、およびｇ個の地理的位置Ｇ’＝｛Ｇ1，．．．，Ｇg｝を持つコンテンツ配送システムにより達成される。この場合、ｓｄｅｌkは、サーバＳkのサーバ遅延であり、ｎｄｅｌj,kは、サーバＳkからコンテンツを検索する際に、地理的位置Ｇj内で顧客が観察したネットワーク遅延であり、ｐjは、顧客Ｃiの優先順位の値であり、ｃiは、顧客Ｃiの全負荷であり、ｕi,jは、領域Ｇjから顧客Ｃiへの要求の一部であり、ａi,j,kは、サーバｓkにリダイレクトされた、領域Ｇjから顧客Ｃiへの要求の一部を表わすマッピングであり、ｓkは、サーバＳkの負荷容量を表わす。このようなシステムにおいては、サーバの負荷を分配するための方法は下記式
【数１９】
0003546850.tif 000002
で表わされる平均観察応答時間を表わすステップ、および、その後で、ＡＯＲＴを最も短くしながら顧客からの要求を特定のサーバへ割り当てるマッピングを作成するステップとを含む。
【００１８】
発見的アルゴリズムが、上記マッピングを作成するために使用される。この場合、大きなａｉ，ｊ，ｋが、もっと小さな全ＡＯＲＴを作成するために、小さなｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）値に割り当てられる。
【００１９】
当業者であれば、添付の図面を参照しながら本発明の実施形態の以下の詳細な説明を読めば、本発明の実施形態の上記およびその他の目的、特徴および利点を理解することができるだろう。
【００２０】
【発明の実施の形態】
好適な実施形態の以下の説明においては、本明細書の一部であり、本発明を実行することができる例示としての特定の実施形態を示す添付の図面を参照する。本発明の好適な実施形態の範囲から逸脱することなしに他の実施形態を使用することもできるし、構造を変更することもできることを理解されたい。
【００２１】
コンテンツ配送システムに対する従来の位置をベースとする方法、または負荷をベースとする方法は、領域境界をどうしても遵守しなければならなかったり、領域境界が考慮されていなかったために、不当に制限を受けている。反対に、本発明の実施形態は、領域境界および領域境界を横切ることによる、ネットワーク遅延を考慮に入れているが、これらの境界に厳格に固執しない。むしろ、本発明の実施形態は、要求を行っているエンドユーザを、領域境界を横切ってミラー・サーバにインテリジェントに再度割り当てすることができ、そうすることにより、全平均ユーザ応答時間を最も短くする。このようなシステムは、ユーザの応答時間の二つの要因、すなわち、ネットワーク遅延とサーバ遅延のバランスをとろうとする。すなわち、追加のネットワーク遅延により表わされるペナルティが、システム上の負荷の軽減により得られる利得より少ない場合には、領域境界を横切ってエンドユーザの要求を分配することは望ましいことである。
【００２２】
＜システムのモデル＞
動的なコンテンツ配送システムは、その顧客（コンテンツ配送サービスに加入している会社または個人）のクライアント（エンドユーザ・ブラウザ）が観察する性能（全応答時間）を改善する。コンテンツ配送システムの一例としては、２０００年４月７日付の、「効率的なコンテンツ配送システムおよび方法」という名称の、米国特許係属出願第０９／５４５，８０５号が開示しているキャッシュ・ポータル（商標）がある。上記米国特許出願の内容は、引用によって本明細書の記載に援用する。エンドユーザの要求の全応答時間を改善するために、コンテンツ配送システムは、インターネットを横切って配置されているミラー・サーバを使用する。より詳細に説明すると、任意のコンテンツ配送システムのタスクは、その顧客のクライアントにより発生した負荷を、上記システムが使用するミラー・サーバを横切って分配することである。
【００２３】
しかし、負荷を効率的に分配するには、本発明の好適な実施形態のコンテンツ配送システムは、下記のものを含むが、それらに限定されない、各顧客
【数２０】
0003546850.tif 000003
の観察可能な特性を考慮に入れる。
・その公表したウェブ・コンテンツ
・（１秒間の間にそのクライアントが発生した要求で表わした）その負荷要件の大きさ
・（所与の時間の、そのクライアントが位置する場所の）その負荷要件の地域的分配
【００２４】
さらに、好適な実施形態は、彼らが要求する性能保証（クライアントが必要とする最大応答時間）を含むことができるが、それに限定されない、各顧客の異なる選択可能な要件を考慮に入れる。
【００２５】
しかし、これらの特性およびネットワークの特性は、エンドユーザの使用パターンが、時間および地域内の位置が変化するにつれて、その日のうちに変更する場合があることを理解されたい。それ故、（最適コンテンツ設置戦略のような）静的な解決方法では十分でない。代わりに、本発明の実施形態は、各顧客に対してクライアント−サーバ割当てを動的に調整する。
【００２６】
上記割当てプロセスについて、以下に簡単に説明する。図３のシステムについて説明するが、これは単に例示としてのものに過ぎない。コンテンツ配送ネットワーク２８は、三つの地理的領域、すなわち、太平洋領域３０、中央領域３２、および大西洋領域３４を含む。太平洋領域３０内においては、ある時間の特定の地点の特定の顧客に対する要求の全数は、ブロック３６で表わされる。さらに、この例のシステムは、三つのミラー・サーバ、すなわち、太平洋領域３０内に位置するミラー・サーバ３８、中央領域３２内に位置するミラー・サーバ４０、および大西洋領域３４内に位置するミラー・サーバ４０を含む。
【００２７】
すでに説明したように、すべての要求３６が、ミラー・サーバ３８に再度割り当てられた場合には、このミラー・サーバ３８の過度の負荷により、全応答時間は最も短くはならない。それ故、本発明の実施形態は、上記要求の中のあるものをミラー・サーバ４０または４２に再度割り当てる。しかし、各ミラー・サーバに関連する別のネットワーク遅延が存在する場合がある。この例の場合には、要求３６が、ミラー・サーバ３８に再度割り当てられた場合には（参照番号４４参照）、エンドユーザおよびミラー・サーバの両方が、太平洋領域内に位置しているために、また横切るネットワーク・ゲートウェイの数が少ないので、説明の都合上、ネットワーク遅延は無視できるものと仮定する。要求３６が、ミラー・サーバ４０に再度割り当てられた場合には（参照番号４６参照）、上記要求は、ゲートウェイ２６を通過しなければならないので、説明の都合上、ネットワーク遅延は１単位であると仮定する。要求３６が、ミラー・サーバ４２に再度割り当てられた場合には（参照番号４８参照）、上記要求は、ゲートウェイ２６を通過しなければならないので、説明の都合上、ネットワーク遅延は２単位であると仮定する。
【００２８】
一人のエンドユーザは、実質的に、ネットワーク・トラヒックおよびネットワーク遅延に影響を与えることはできないので、ネットワークへの変更は、通常、時間の経過とともにゆっくりと発生するものであり、多くのエンドユーザの行為を組合せた結果である。本発明の実施形態は、任意の時点においては、ネットワーク遅延は安定していて、ユーザ応答時間を周期的に再計算するだけでよいという事実を利用する。これらの計算した応答時間は、新しいユーザ応答時間が再計算されるまで、所与の時間の間の最適な解（割当てまたはマッピング）を決定するために使用される。
【００２９】
すでに説明したように、本発明の実施形態は、また、各ミラー・サーバの負荷容量およびサーバ遅延を考慮する。図３について説明すると、太平洋領域３０内のエンドユーザと、ミラー・サーバ３８との間のネットワーク遅延は無視できるので、最初は、太平洋領域からのすべての要求３６は、ミラー・サーバ３８に再度割り当てるべきもののように思われる。しかし、ミラー・サーバ３８は、要求により過負荷になり、その負荷容量以上になり、サーバ遅延が増大し始める。全エンドユーザ応答時間を確実に最も短かくするために、本発明の実施形態は、応答時間を再計算し、割当てまたはマッピングを作成するために、（後で説明する）発見的アルゴリズムを実行し、マッピングに従って、要求の中のあるものをミラー・サーバ４０（参照番号４６参照）、およびミラー・サーバ４８（参照番号４８参照）へ再度割り当てる。図３の例の場合には、要求の中の５０％は、ミラー・サーバ３８に再度割り当てられ、要求の中の３０％は、ミラー・サーバ４０に再度割り当てられ、要求の中の２０％は、ミラー・サーバ４２に再度割り当てられる。その結果、全ユーザ応答時間が最も短かくなる。
【００３０】
この解は、計算した応答時間が示す、地理的または地域的情報を考慮していないことを理解されたい。それ故、本発明の実施形態は、負荷をベースとする方法よりも柔軟である。何故なら、地理的領域を考慮に入れているからである。本発明の実施形態は、位置をベースとする方法よりも柔軟である。何故なら、本発明の実施形態は、上記マッピングが全応答時間を短縮するなら、地域的境界を横切って異なるミラー・サーバにエンドユーザ要求を再度割り当てることができるからである。
【００３１】
以下に、割当てプロセスをさらに本格的に説明する。もっと正確な言い方をすれば、コンテンツ配送システムが、下記のものを持っている場合には、すなわち、
・ｍ個のサーバ、Ｓ’＝｛Ｓ1，．．．，Ｓm｝
・ｎ人の顧客、Ｃ’＝｛Ｃ1，．．．，Ｃn｝、および
・ｇ個の地理的位置、Ｇ’＝｛Ｇ1，．．．，Ｇg｝
を持っている場合には、本発明の実施形態の目標は、ａi,j,k＝μ／１００である場合、地理的位置Ｇjからの顧客Ｃiのサイトへの要求のμ％が、サーバＳkに割り当てられるように、下記のマッピング（すなわち、ある割当て）を作成することである。
ａ：Ｃ’×Ｇ’×Ｓ’→［０，１］
【００３２】
例えば、コンテンツ配送サーバが、全部で三つのサーバＳ1、Ｓ2およびＳ3を持っている場合には、地理的領域Ｇj内の顧客Ｃiが分かっているので、下記のマッピングが作成される。
ａ1,1,1＝０．５０
ａ1,1,2＝０．３０
ａ1,1,3＝０．２０
【００３３】
上記マッピングは、地理的領域Ｇ1内の顧客Ｃiに対する要求の５０％が、サーバＳ1にリダイレクトされ、地理的領域Ｇ1内の顧客に対する要求の３０％が、サーバＳ２にリダイレクトされ、地理的領域Ｇ1内の顧客Ｃiに対する要求の２０％が、サーバＳ３にリダイレクトされることを示す。
【００３４】
上記マッピングを作成するために、本発明の実施形態は、下記のものを含むが、それらに限定されない動的コンテンツ配送ネットワークの種々の面について知らなければならない。
・サーバＳkから地理的位置Ｇjへ、通常の動的コンテンツ（〜４ｋＢサイズ）を配送するために必要なネットワーク遅延ｎｄｅｌj,k。
・サーバＳkから通常の動的コンテンツ（〜４ｋＢサイズ）要求をサービスするために必要なサーバ遅延ｓｄｅｌj,k（サーバ負荷が増大するにつれ、この遅延が増大する場合があり、ｓｄｅｌj,kが、サーバ負荷にの関数になる場合もあることに留意されたい）。
・それを超えた場合、サーバが過負荷になりすぎて役にたたなくなるサーバＳkの負荷容量ｓk。
・位置Ｇjに位置するエンドユーザが発生した顧客Ｃiの負荷要件。
顧客Ｃiの全負荷要件をｃiで表わした場合、Ｇjに位置するエンドユーザが発生したこの部分は、ｕi,j×ｃiに等しい。この場合、ｕi,j＝地理的位置Ｇjから顧客Ｃiへの要求の一部であり、ｕi,j×ｃi＝地理的位置Ｇjから顧客Ｃiへのすべての要求である。
【００３５】
本発明の実施形態のコンテンツ配送システムのこれらの面が分かっているので、ある種の拘束が存在することに留意されたい。
・コンテンツ配送システムは、サーバが処理できる以上の負荷をサーバに割り当ててはならない。すなわち、各Ｓｋ∈Ｓ’に対して下記式のようになる。
【数２１】
0003546850.tif 000004
・各エンドユーザの要求は、あるサーバに割り当てなければならない。各Ｃｎ∈Ｃ’，Ｇｇ∈Ｇ’に対して下記式
【数２２】
0003546850.tif 000005
のようになる。
・エンドユーザ要求は、要求されたコンテンツを持たないサーバに割り当ててはならない。それ故、顧客への要求が多数あり、その顧客に対する適当なサーバが存在しない場合には、本発明の実施形態は、適当なサーバの対応するデータを適当なサーバに移動しなければならない場合がある。
【００３６】
また、定義により、マッピングのａｉ，ｊ，ｋの値は負になることはできないことに注意したい。すなわち、各Ｃｊ∈Ｃ’，Ｇｇ∈Ｇ’，Ｓｋ∈Ｓ’に対して、下記式のようになる。
ａｉ，ｊ，ｋ≧０
【００３７】
それ故、ｎ×ｇ×ｍ個の変数（αｉ，ｊ，ｋ）により割当てを選択している間に、本発明の実施形態は、ｍ＋ｎ×ｇ×ｍ＋ｎ×ｇの線形拘束条件を考慮しなければならない。
【００３８】
本発明の実施形態によれば、ある解を計算する際に考慮する変数の数と比較した場合、拘束条件が多いので、同じ結果をもたらす複数の解が得られることになる。これら複数の解による混乱は、特定の解を再計算した場合、すべての前のマッピングを大きく変更する新しい解を選択することになる。新しいマッピングは、破局をもたらすようなものではないにしても、遅延を増大する恐れがある。何故なら、新しい接続を地理的境界を横切って行わなければならないし、システムの性能が不安定になる恐れがあるからである。それ故、他の実施形態の場合には、解に対するもう一つの制約は、一つ以上の可能な最適な解が分かっている場合には、前のマッピングと新しいマッピングとの間の違いを最も少なくする解を選択しなければならない。
【００３９】
ある条件の下では、解を発見するのに考慮しなければならない種々の制約条件を相互に掛け合わせたり、冪にしたりしないで、定数だけを掛けることができる、変数により指定することができる種々の制約条件である線形制約条件として指定することができる。上記制約条件は、線形制約条件として指定することができるので、本発明の他の実施形態の場合には、当業者であれば周知の複雑な計算である線形制約条件解法を使用する場合がある。しかし、線形制約条件を解くのには、多くの時間が掛かる。
【００４０】
本発明のさらに他の実施形態の場合には、種々の制約条件を非線形制約条件で指定することができるし、解を得るために非線形制約条件解法を使用することができる。しかし、非線形制約条件を解くのは、通常、線形制約条件を解くのと比較すると遥かに非効率的である。そのため、通常、時間が掛かる。後で説明するように、本発明の好適な実施形態により、発見的アルゴリズムを使用する場合には、制約条件は、非線形制約条件として指定する場合があるが、もっと短い時間で解を得ることができる。
【００４１】
＜動的コンテンツ配送ネットワークの性能調整＞
＜応答時間について＞
すでに説明したように、各ミラー・サーバは、通常、その負荷の関数である関連予想サーバ遅延時間を持つ。図４は、ミラー・サーバの遅延時間の特性の一例である。ミラー・サーＳｉは、ある負荷ｓｉまで、比較的一定の応答時間を供給する。上記ある負荷を超えると、サーバ遅延時間は、突然増大する（参照番号５０参照）。それ故、ミラー・サーバの負荷がｓｉ以下に維持されている限りは、サーバの通常の遅延（ｓｄｅｌ１）であっても、その最悪の場合の遅延時間（ｓｄｅｌ２）であっても、サーバ遅延は、定数として推定することもできるし、線形定数として指定することもできる。
【００４２】
本発明の好適な実施形態の場合には、サーバ遅延の推定値の精度を上げるために、上記サーバ負荷制約条件を、このしきい値ｓｋ以下に維持し、線形領域内に維持する目的で、例えば、最大サーバ負荷容量の８０％に調整することができる。しかし、上記制約条件の下で解が計算され、その解が次の周期に対して正しい位置にある場合には、実際のサーバ負荷をｓｋの上または下に変動させることができる。
【００４３】
動的コンテンツ配送ネットワークの平均観察応答時間（ＡＯＲＴ）は、下記式により定義することができる。
【数２３】
0003546850.tif 000006
【００４４】
ここで、ｓｄｅｌkは、サーバ遅延であり、ｎｄｅｌj,kは、サーバＳkにアクセスしている間に、地理的位置Ｇjで顧客が観察したネットワーク遅延であり、ｐjは、（そのサービス契約に基づく）その顧客の優先順位である。説明を分かりやすくするために、本明細書で説明する例の場合には、すべての顧客が、同じ優先順位を持つものと仮定する。すなわち、すべてのＣi∈Ｃ’に対して，ｐi＝１となる。
【００４５】
しかし、本発明の実施形態は、異なる優先順位値ｐｉを考慮することができることに留意されたい。
【００４６】
ＡＯＲＴの他に、個々の平均観察応答時間（ＡＯＲＴｉ）を個々の顧客のクライアント（エンドユーザ）に対して定義することができる。
【数２４】
0003546850.tif 000007
【００４７】
応答時間のこれらの定義は線形であることに留意されたい。それ故、これらを、ｓｉｍｐｌｅｘのような線形最適化技術を使用して最小にすることもできるし／解くこともできる。しかし、サーバ遅延が、定数として処理できない場合には、上記定義は、線形ではなく、（通常、遥かに高価な）非線形最適化技術を使用しなければならない。
【００４８】
上記式を理解するために、ＡＯＲＴiの構成要素について説明する。すでに説明したように、ｓｄｅｌkは、サーバＳkのサーバ遅延であり、ｎｄｅｌj,kは、地理的位置ＧjとサーバＳkとの間のネットワーク遅延である。それ故、ｓｄｅｌk＋ｎｄｅｌj,kは、地理的領域ＧjからサーバＳkへの要求から見た全遅延である。さらに、ｃiは、顧客Ｃiの全負荷であり、ｕi,jは、領域Ｇjから顧客Ｃiへの要求の一部である。それ故、ｕi,j×ｃiは、顧客Ｃiから領域Ｇjへの要求の数に等しい。さらに、ａi,j,kは、サーバＳkに再度割り当てられた領域Ｇjから顧客Ｃiへの要求の一部である。それ故、ａi,j,k×ｕi,j×ｃiは、サーバＳkに割り当てられた領域Ｇjから顧客Ｃiへの全要求に等しい。この結果に、ｓｄｅｌk＋ｎｄｅｌj,kを掛けた場合には、その結果は、サーバＳkに割り当てられた、領域Ｇjから顧客Ｃiへのすべての要求の全遅延である。その後で、この遅延は、すべてのサーバ上、およびすべての地理的位置上において合計される。それ故、ＡＯＲＴiの分子は、すべてのサーバに割り当てられたすべての領域から顧客Ｃiへのすべての要求に対する遅延である。ＡＯＲＴiの分子を、顧客Ｃiへの要求の全数であるｃiで割ることにより、これらすべての要求に対する平均応答時間を計算することができる。
【００４９】
本発明の他の実施形態の場合には、線形制約条件解法を使用して、ＡＯＲＴおよびＡＯＲＴｉの両方を最小にすることによって、応答時間を最も短かくすることができる。しかし、線形制約条件解法を使用して、解を得るのに必要な時間が長すぎて実際に使用することができない。例えば、本発明の実施形態の場合には、システムは、例えば、３０秒のようなある時間が経過した後で、新しい解を再計算することができる。この解が計算されると、次の３０秒間に発生した要求は、前に計算した解に従う。しかし、線形制約条件解法を使用して解を計算するには１時間以上掛かる場合がある。ここでもまた、解が個々の要求に基づいて、計算されるのではないことを理解されたい。代わりに、エンドユーザの要求の全応答時間がモニタされ、全応答時間時間が増大し始めたら、システムは、他の場所にこれら要求の中のあるものを再度割り当てる新しい解を計算することができる。
【００５０】
＜サーバの負荷のバランス＞
最短の全応答時間を与える上記線形制約条件の他に、本発明の好適な実施形態の場合には、追加の線形制約条件をミラー・サーバの負荷のバランスをとるために使用することができる。最短応答時間を得るために、負荷のバランスを必ずしもとらなくてもよいが、負荷のバランスは、ある状況においては、一つの要因でありうる。例えば、再び、図４について説明すると、応答時間を最短にする解を使用した場合には、すべてのミラー・サーバは、ｓkより軽いサーバ負荷を持つことになり、負荷バランスをとらない場合には、個々のミラー・サーバに対するサーバ負荷のバランスをとることができない。すなわち、一つのミラー・サーバは、ｓkに非常に近いサーバ負荷を持つことができ、一方、他のミラー・サーバは、ｓkとは非常に異なるサーバ負荷を持つことができる。そのため、いくつかの問題が起こる場合もある。何故なら、ｓkに近いサーバ負荷を持つミラー・サーバが、そのサーバ負荷をｓk以上にするような負荷の変動に遭遇する場合があり、応答時間が過度に長くなるからである。解こうとしている問題に、負荷バランス制約条件を追加することにより、すべてのミラー・サーバ負荷が、できるだけ、ｓkから異なるなるものになり、負荷の変動が、応答時間を過度に長くする可能性が少なくなる。
【００５１】
以下に負荷バランス要求について、さらに本格的に説明する。バランスがとれているミラー・サーバからの最大許容偏差を示すΘが分かっている場合には、すべてのサーバの組ＳｋおよびＳｉに対して、下記の制約条件を満足させなければならない。
【数２５】
0003546850.tif 000008
【００５２】
Θの適当な値は、用途に依存にすることもできるし、実行可能な一組の式が発見されるまで、二分探索により探索することもできる。このことにより、ｍ×（ｍ−１）の余計な不等式を、システムが負担することになることに留意されたい。
【００５３】
上記式の理解を助けるために、その構成部分について以下に説明する。上記式が、二つのミラー・サーバＳkおよびＳlの間の負荷バランスを表わすことを理解されたい。ここでもまた、ｃiは、顧客Ｃiの全負荷であり、ｕi,jは、領域Ｇjから顧客Ｃiへの要求の百分率であり、ａi,j,kは、サーバＳkに再度割り当てられた領域Ｊから顧客Ｉへの要求の一部である。それ故、ａi,j,k×ｕi,j×ｃiは、サーバＫにリダイレクトされた、領域Ｇjから顧客Ｃiへのすべての要求に等しい。上記式の分子において、ミラー・サーバＳkに対する全負荷を発生するために、この値は、すべての領域およびすべての顧客に対して合計される。ミラー・サーバＳlに対する全負荷を知るために、分母に対しても、同じことが行われる。それ故、式の左辺は、ミラー・サーバＳkおよびミラー・サーバＳlの負荷の比率である。この比率は、（１＋Θ）にだけ、式の右辺に示すあるしきい値より小さいものでなければならない。この場合、Θは、どの程度の不均衡が許容されるかを示す分数値である。
【００５４】
さらに、上記式の右辺も、比率ｓk／ｓlを含むことに留意されたい。この場合、ｓkは、サーバＳkの負荷容量を示し、ｓlは、サーバＳlの負荷容量を示す。上記式がこのような比率を含むのは、すべてのミラー・サーバが、同じ負荷容量を持っているわけではなく、その負荷容量が異なる場合に、二つのミラー・サーバの負荷をバランスさせるのは意味がないからである。それ故、例えば、サーバＫが、サーバＳlより遥かに大きな負荷容量を持っている場合には、ミラー・サーバのバランスのとれた組は、ミラー・サーバＳkが、サーバＳlより、より多くの要求を処理できたとしても、各ミラー・サーバは、最大容量の、例えば、６０％で稼働することになる。
【００５５】
別の方法としては、上記の応答時間制約条件が計算するのにあまりに高くつく場合でも、またはネットワーク遅延が無視できる場合でも、負荷の不均衡は、ハッキリと最小限度まで低減する。この場合には、ＡＯＲＴ関数を最小にする代わりに、下記のように、不均衡関数（ＩＭＢＬ）を最小にする。
【数２６】
0003546850.tif 000009
ここで、
【数２７】
0003546850.tif 000010
はサーバＳkの負荷である。
【００５６】
＜動的コンテンツ配送ネットワークの安定性の維持＞
すでに説明したように、コンテンツ配送システムに影響を与える（顧客負荷要件のような）システム・パラメータは、頻繁に変更することができ、それ故、上記システムは、変更に迅速に適応できなければならない。さらに、新しい解が計算された場合には、本発明の好適な実施形態は、前の解にできるだけ近い解を計算する。さらに、上記適応は、現在の顧客に供給しているサービスを最小限度に混乱させるか、全然混乱させないものでなければならない。例えば、
・新しいサーバの追加または顧客のサービス終了によるリソースの増加は、それが負荷バランス制約条件Θに違反しない限り、負荷の再分配を引き起こさないものでなければならない。
・新しい顧客は、現在の顧客に対する平均観察応答時間があまり長くならない場合だけ、システム内に受け入れるものとする。すなわち、ＡＯＲＴ関数の古い値および新しい値は、下記式のようになる。
【数２８】
0003546850.tif 000011
および
【数２９】
0003546850.tif 000012
【００５７】
システムは、確実に下記式を満足させるものでなければならない。
ＡＯＲＴｎｅｗ≦（１＋Φ）×ＡＯＲＴｏｌｄ
ここで、ａ’ｉ，ｊ，ｋは、新しい割当てあり、Φは、現在の顧客に対する平均応答時間の変更の許容範囲である。このことは、平均して、顧客の応答時間を大きく変更しないことを保証するが、個々の顧客が観察する変更を制限することに留意されたい。それ故、顧客指定の応答時間変更の制約条件も使用することができる。
【００５８】
ＡＯＲＴｉ，ｎｅｗ≦（１＋Φｉ）×ＡＯＲＴｉ，ｏｌｄ
ここで、Φｉは、顧客Ｃｉの平均応答時間の許容できる部分的変更である。Φｉは、０．０５（５％）のように最初に選択される値であることに留意されたい。しかし、５％の変更制約条件を満足させることができる解がない場合には、本発明の好適な実施形態は、自動的にある解が発見されるまで、ある量だけ、Φｉの値を増大させる。
【００５９】
・現在の顧客の要求率（または負荷）の変更は、現在の顧客の平均観察応答時間に影響を与えるものであってはならない。この制約条件は、前の項の制約条件と同様に定義することができる。
【００６０】
＜割当てマッピングを計算するための技術＞
すでに説明したように、上記制約条件は、通常、線形制約条件の形で表現することができる。それ故、本発明の他の実施形態の場合には、上記制約条件を最適に解くために、メープル・ソフトウェア（ｓｉｍｐｌｅｘを含む）のような汎用線形最適化ツールを使用することができる。しかし、図４に示すように、ミラー・サーバ遅延が一定でない場合には、制約条件は非線形になり、非線形制約条件最適化技術を使用しなければならない。しかし、問題の範囲が大きくなると、変数および制約条件の数も急速に増大するので、これらのオプションの両方は、非常に高価なものになる。さらに、これらオプションの規模はうまくスケールアップしない。
【００６１】
それ故、本発明の好適な実施形態の場合には、短い実行時間で、最適に近い結果を生じる効率的な発見的アルゴリズムが実行される。好適な実施形態の場合には、発見的方法は、上記制約条件ＡＯＲＴおよびＡＯＲＴｉを解くことができ、また、上記負荷バランス制約条件、および応答時間制約条件の増大を解くことができる。
【００６２】
＜直感的洞察＞
本発明の好適な実施形態の、発見的アルゴリズムの背後にある直感的洞察について以下に説明する。平均観察応答時間（ＡＯＲＴ）を再び検討すると、下記式のようになる。
【数３０】
0003546850.tif 000013
【００６３】
ＡＯＲＴが急速に長くなるのを防止する一つの方法は、ｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）に大きなａｉ，ｊ，ｋを割り当てることにより、分子内の合計値を制限することであることを理解することができるだろう。このような割当てを行うと、合計の個々の項、それ故、全ＡＯＲＴが、通常、小さくなる。例えば、ｉ，ｊ，ｋの三文字が２，２，３であり、ｉ，ｊ，ｋの三文字２，２，３に対するｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）の値が５０となる場合があると仮定しよう。ただし、これは説明のためだけのものである。また、ｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）の値を２４にする別のｉ，ｊ，ｋの三文字２，１，４があると仮定しよう。さらに、数値０．２または０．４をａｉ，ｊ，ｋに割り当てることができると仮定しよう。小さなｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）の値（２４）に大きなａｉ，ｊ，ｋの値（０．４）を割り当てることにより全応答時間を短縮することができる。
【００６４】
＜反復組合せをベースとする技術＞
本発明の実施形態の発見的アルゴリズムは反復的なものである。一回の反復毎に、少なくとも四つの分類リストが作成される。
・Ｃiは、ｃiの昇順に分類される（すなわち、顧客は、サーバの負荷の昇順に分類される）。
・＜Ｃi，Ｇj＞の組は、ｕi,jの昇順に分類される（すなわち、顧客と領域の組は、領域Ｇjから顧客Ｃiへの要求の一部の昇順に分類される）。
・Ｓk値は、ｓｄｅｌkの昇順に分類される（すなわち、サーバは、サーバ遅延の昇順に分類される）。
・＜Ｃi，Ｇj＞の組は、ｎｄｅｌj,k昇順に分類される（すなわち、サーバと領域の組は、ネットワーク遅延の昇順に分類される）。ｎｄｅｌj,kが一定ではなく、ミラー・サーバ負荷の関数である場合には、各反復毎にこの項を調整しなければならないことに留意されたい。それ故、好適な実施形態の発見的アルゴリズムは、問題の非線形の場合まで延長される。
さらに、好適な実施形態の場合には、負荷バランスを促進するために、
・Ｃi値は、残りの負荷容量Ｓkの降順に分類される（すなわち、サーバは、残りの負荷容量の降順に分類される）。
【００６５】
これらの分類された値は、現在の解が再計算される前のある時点で測定したものであることに留意されたい。
【００６６】
分類されたリストが作成されると、本発明の実施形態の発見的アルゴリズムは、反復ステップのシーケンスを実行する。各反復毎に、最も小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値を持つ一番上の三文字＜Ｃi，Ｇj，Ｓk＞が、組合せ動作により選択される。その後で、選択した三文字＜Ｃi，Ｇj，Ｓk＞のサーバＳkが、＜Ｃi，Ｇj＞の組に割り当てられる。サーバＳkの負荷容量が、残りの負荷を処理するのに十分でない場合には、＜Ｃi，Ｇj＞の組に対してサーバＳkの残りの容量が使用され、この組の割り当てられていない部分が反復プロセスに再挿入される。
【００６７】
この反復組合せ動作を説明するために、三人の顧客、三つの領域、および三人のサーバを含む環境の一例について説明する。この環境の一例は、図５に示すように、分類されたリスト、ｃi，ｕi,j，ｓｄｅｌk，ｎｄｅｌj,kおよびｓkとなると仮定しよう。最初に、すでに説明したように、最も小さいｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）値は、左の四つのリストの各々における一番上の項をとり、それぞれ他のリスト内で比較可能な項の最も小さいものを発見することにより、選択される。
【００６８】
それ故、最初のリストでは一番上の項が選択されうる。この例の場合には、その項はｃ2である。ｃ2の選択の意味は、残りの各リストｕi,j、ｓｄｅｌk、およびｎｄｅｌj,k内で比較することができる項がｉ＝２を持たなければならないことである。本発明の好適な実施形態の場合には、ｃiリスト内の一番上の項が、最初に選択された場合には、比較できる項を発見するプロセスは、ｃi→ｕi,j→ｎｄｅｌj,k→ｓｄｅｌkの順序で、リストからリストへ移動する。それ故、リストｕi,jにおいては、比較できる項は、ｉ＝２を含む一番上のｕi,jの組、すなわち、ｕ2,3である。ｕ2,3を選択すると、残りの各リスト内の比較できる項に追加の制約条件が追加され、ｓｄｅｌk＋ｎｄｅｌj,kは、ｉ＝２およびｊ＝３を持たなければならない。リストｎｄｅｌj,kにおいては、比較できる項は、ｊ＝３を含む一番上のｎｄｅｌj,k、すなわち、ｄｅｌ3,3である。ｎｄｅｌ3,3を選択すると、残りの各リスト内の比較できる項に追加の制約条件が追加され、ｓｄｅｌkは、ｋ＝３またはｓｄｅｌ3を持たなければならない。これらの比較できる項ｃ2、ｕ2,3、ｎｄｅｌ3,3、およびｓｄｅｌ3（参照番号５２参照）から三つの文字（２，３，３）を使用して、ｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）に対する値を計算することができる。
【００６９】
第二のリスト（ｕ３、１）内の一番上の項に対して、この同じプロセスが反復して行われる。本発明の好適な実施形態の場合には、ｕｉ，ｊリスト内の一番上の項が最初に選択された場合には、比較できる項を発見するプロセスは、ｕｉ，ｊ→ｎｄｅｌｊ，ｋ→ｓｄｅｌｋ→ｃｉの順序で、リスト間を移動し、その結果、比較できる項は、ｃ３、ｕ３，１、ｎｄｅｌ１，１およびｓｄｅｌ１となる（参照番号５４参照）。これらの比較できる項から三つの文字（３，１，１）を使用して、ｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）に対する値を計算することができる。他の実施形態の場合には、比較できる項を発見するためのプロセスは、ｕｉ，ｊ→ｎｄｅｌｊ，ｋ→ｃｉ→ｓｄｅｌｋの順序で、またはｕｉ，ｊ→ｃｉ→ｎｄｅｌｊ，ｋ→ｓｄｅｌｋの順序でリスト間を移動することができる。
【００７０】
第三のリスト（ｎｄｅｌ１，１）内の一番上の項に対して、この同じプロセスが反復して行われる。本発明の好適な実施形態の場合には、ｎｄｅｌｊ，ｋリスト内の一番上の項が最初に選択された場合には、比較できる項を発見するプロセスは、ｎｄｅｌｊ，ｋ→ｓｄｅｌｋ→ｕｉ，ｊ→ｃｉの順序で、リスト間を移動し、その結果、比較できる項は、ｃ３、ｕ３，１、ｎｄｅｌ１，１およびｓｄｅｌ１となる（参照番号５８参照）。この比較できる項が、偶然、比較できる項の第二のグループと同じものであることに留意されたい。これらの比較できる項から三つの文字（３，１，１）を使用して、ｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）に対する値を計算することができる。他の実施形態の場合には、比較できる項を発見するためのプロセスは、ｎｄｅｌｊ，ｋ→ｕｉ，ｊ→ｓｄｅｌｋ→ｃｉの順序で、またはｎｄｅｌｊ，ｋ→ｕｉ，ｊ→ｃｉ→ｓｄｅｌｋの順序でリスト間を移動することができることに留意されたい。
【００７１】
最後に、第四のリスト（ｓｄｅｌ３）内の一番上の項に対して、この同じプロセスが反復して行われる。本発明の好適な実施形態の場合には、ｓｄｅｌｋリスト内の一番上の項が最初に選択された場合には、比較できる項を発見するプロセスは、ｓｄｅｌｋ→ｎｄｅｌｊ，ｋ→ｕｉ，ｊ→ｃｉの順序でリスト間を移動し、その結果、比較できる項は、ｃ２、ｕ２，３、ｎｄｅｌ３，３およびｓｄｅｌ３となる（参照番号５６参照）。この比較できる項が、偶然、比較できる項の第一のグループと同じものであることに留意されたい。これらの比較できる項から三つの文字（２，３，３）を使用して、ｕｉ，ｊ×ｃｉ×（ｓｄｅｌｋ＋ｎｄｅｌｊ，ｋ）に対する値を計算することができる。
【００７２】
次に、組合された遅延値が最も小さい三文字が識別される。上記例について説明を続けると、三文字＜２，３，３＞および＜３，１，１＞に対する、ｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）の組合せ遅延値が、それぞれ、１０単位および５単位である場合には、三文字（３，１，１）が選択される。その結果、サーバＳ1には、領域Ｇ1から個々のＣ3への負荷が割り当てられ、特定のａi,j,k値が三文字＜３，１，１＞に割り当てられる。特定の組合せ遅延値に、ａi,j,k値を割り当てた結果は、特定の領域内の特定のサーバへの特定の顧客の割当てとなる。
【００７３】
サーバＳ1が、すべての割り当てられた負荷を処理するだけの十分な負荷容量を持っている場合には、ａi,j,k値は最大（＝１．０）になり、ＡＯＲＴiは最小になり、小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）に対して大きなａi,j,k値を割り当てるという目標が達成される。その後で、この割当てを考慮に入れて、ｃi値およびｕi,j値が再計算される。例えば、領域Ｇ1から顧客Ｃ3へのすべての負荷を考慮に入れたので、ｕ3,1の値はゼロであり、それ故、ｕ3,1が、ｕi,jリストから除去される。サーバ顧客Ｃ3に対する負荷の中のあるものを考慮に入れたので、ｃ3の値は小さくなる。最初の割当てにもかかわらず、ｓｄｅｌkおよびｎｄｅｌj,kが変化しないことに留意されたい。何故なら、これらは一定であると仮定しているからである。
【００７４】
サーバＳ１が、割り当てられたすべての負荷を処理するのに十分な負荷容量を持っていない場合には、ａｉ，ｊ，ｋ値は、ゼロと１との間のある値として計算される。特に、ＡＯＲＴｉが計算される。その後で、サーバＳｉの残りの容量が、領域Ｇ１から顧客Ｃ３への負荷の中のあるものを処理するために割り当てられる。その結果、ｓ１の値はゼロになり、そのため、ｓ１はｓｋリストから除去される。さらに、領域Ｇ１から顧客Ｃ３への負荷の中のあるものを考慮に入れたので、ｕ３，１とｃ３の値は小さくなる。
【００７５】
これらの割当てが行われ、ｃi，ｕi,jおよびｓkの値が再度計算されると、ｃi，ｕi,jおよびｓkのリストが再分類される。各リスト内の一番上の項に対する、比較できる項を発見するプロセスが反復して行われ、最も小さい値を持つ三文字＜Ｃi，Ｇj，Ｓk＞が識別され、サーバ負荷が割り当てられ、ａi,j,k値およびＡＯＲＴ値が計算される。この反復プロセスは、すべての領域Ｇiからすべての顧客Ｃiへのすべての負荷が、可能な限り、サーバＳkに割り当てられるまで反復して行われる。
【００７６】
上記例は、ｓｋリストを考慮に入れなかったことに留意されたい。しかし、本発明の好適な実施形態の場合には、リスト内の比較できる項を発見するプロセス内に分類したｓｋリストを含めることにより、負荷バランスを考慮に入れることができる。好適な実施形態の場合には、上記のリスト間の順位のいずれかを実行することにより比較できる項を発見するプロセスは、順序の一番後にリストｓｋを含めることができる。
【００７７】
＜データの移動＞
上記説明は、すべてのミラー・サーバが、エンドユーザが要求したコンテンツのコピーを含んでいるという仮定に基づいて行った。しかし、要求されたコンテンツを持たない特定のミラー・サーバからコンテンツを取り出すために、エンドユーザが割り当てられる場合に、ある割当てが行われると仮定しよう。通常、このような割当ては行うべきではない。しかし、その割当てが、すべて全応答時間を短縮する結果になる場合で、要求したコンテンツをミラー・サーバにコピーすることができる場合には、このような割当ては価値がある。データのコピーまたは移動は、ペナルティを表し、そのため、データの移動を必要とする割当ては、必要な場合にだけ行うべきである。要求されたデータを持たないサーバへの割当ての数を最小にするために、本発明の好適な実施形態の場合には、下記のものを含む別なリストを作成することができる。
・分類されていない＜Ｃi，Ｓk＞の組（すなわち、顧客Ｃiのコンテンツが、サーバＳk内に記憶される顧客マッピングおよびサーバ・マッピング）
【００７８】
＜Ｃi，Ｓk＞の組のリストは分類されていないで、上記リストは、顧客ＣiのコンテンツがサーバＳk内に記憶されるすべての＜Ｃi，Ｓk＞だけを表わす。最小の組合せ遅延を表わす三文字＜Ｃi，Ｇj，Ｓk＞が、上記のように識別された場合には、割り当てられた三文字が、決して、要求されたコンテンツを含んでいないミラー・サーバに割り当てられている顧客の負荷にならないようにこのリストが参照される。
【００７９】
反復プロセスが解を発見できない場合には、（すなわち、適当なサーバを発見できなかった場合には）、最も小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）を持つ、適当な候補（三文字＜Ｃi，Ｇj，Ｓk＞）が選択され、顧客ＣiのデータがサーバＳkに移動する。好適な実施形態の場合には、サーバＳkへのデータ移動に関連する時間ペナルティの程度を知ることができる。それ故、最も小さなｕi,j×ｃi×（ｓｄｅｌk＋ｎｄｅｌj,k）を持つ適当な候補（三文字＜Ｃi，Ｇj，Ｓk＞）を選択する場合には、最も小さなペナルティを持つサーバＳkを選択することができる。
【００８０】
＜応答時間の推定＞
上記の式が示すように、本発明の好適な実施形態の発見的アルゴリズムは、特定のミラー・サーバにアクセスしていて、所与の地理的位置に位置するエンドユーザが観察したサーバ遅延ｓｄｅｌｋ、およびネットワーク遅延ｎｄｅｌｊ，ｋの長さを知らなければならない。あるミラー・サーバが、エンドユーザの要求を処理に掛かる時間であるサーバ遅延は、ミラー・サーバ自身から直接決定することができる。何故なら、ミラー・サーバは、コンテンツ配送システムの一部であるので、サーバの遅延の測定は比較的簡単である。
【００８１】
ネットワーク遅延の測定はもっと難しい。コンテンツ配送システムは、重要な各位置の機械にアクセスしないので、エンドユーザの応答時間は、通常、直接測定することはできない。しかし、ネットワーク遅延は、ミラー・サーバが維持するサーバ・ログを使用して推定することができる。遠隔のエンドユーザが、特定のミラー・サーバからコンテンツを要求した場合には、ユーザとサーバとの間で一連のメッセージがやりとりされ、これらのメッセージのタイミングが、サーバ・ログに記憶される。これらのメッセージのタイミングは、全応答時間を推定するのに使用される。
【００８２】
＜入手可能なログ＞
ミラー・サーバから入手することができるサーバ・ログには二つのタイプがある。一方のタイプは、ＴＣＰログと呼ばれ、他方のログはＨＴＴＰログと呼ばれる。各タイプのログは、異なる一組の情報を発生する。
【００８３】
＜ＴＣＰログの使用＞
ＴＣＰログは、ミラー・サーバと、直接往復遅延を含む接続を通しての、すぐ上流に位置するクライアント／プロキシ／エンドユーザとの間の接続の特性を推定するために使用することができる。説明の都合上、システムは、ミラー・サーバおよびエンドユーザを含み、エンドユーザのウェブ・ブラウザは、ミラー・サーバとの接続をすでに設定しているものと仮定する。ＴＣＰログは、接続確立時間を含む二つの変数を記憶しているので、ＴＣＰログから直接往復遅延およびバイト当り遅延を抽出することができる。
【００８４】
本発明の実施形態の場合には、直接往復遅延は、下記式により定義することができる。
ｔｃｏｎ＿ｅｓｔ−ｔａｃｋ＿ｓｅｎｄ＝Δｒｉｍｍ
ここで、（１）ｔｃｏｎ＿ｅｓｔは、ミラー・サーバが、接続確立メッセージを受信する時間（接続が確立される時間）であり、（２）ｔａｃｋ＿ｓｅｎｄは、ミラー・サーバが、クライアントから受信した接続要求メッセージに応えて受信通知メッセージを送信する時間であり、（３）Δｒｉｍｍは、サーバと直接上流の構成要素との間の往復遅延である。ｔｃｏｎ＿ｅｓｔおよびｔａｃｋ＿ｓｅｎｄの両方は、ＴＣＰログ内に記憶されるので、Δｒｉｍｍは、容易に計算することができる。
【００８５】
さらに、本発明の実施形態の場合には、接続パラメータΔｒimm、および特定のメッセージ内の各バイトに関連する遅延である、バイト当りの遅延を示す定数αを推定するために下記式を使用することができる。この場合、ｔdata_send（ｈ）は、データのｈ番目のバイトが、送信された時間であり、ｔack_receive（ｋ）は、ｋ番目の（ｋ≧ｈ）バイトに対する受信通知を受信した時間である。
【００８６】
ＴＣＰログは、データのｈ番目のバイトが送信された時間、およびｋ番目のバイトの受信通知を受信した時間を記憶しているので、バイト当りの遅延αを決定するために、Δｒimmと一緒にこれらの記憶している値を上記式に挿入することができる。ＴＣＰ流れ制御機構により、通常、α値は、通信中一定でないことに留意されたい。同様に、Δｒimmも、接続が行われている間変動する場合がある。しかし、一回の接続中に送信される受信通知の数が多いので、時間の経過中の接続の一般的な行動を示す統計的に有意な値を収集することができる。
【００８７】
上記例の説明を引き続いて行うが、この説明は例示としてのものに過ぎない。図６に示すように、ＴＣＰログは、データの１００番目のバイトが時点５において送信されたこと、データの２００番目のバイトが時点７において送信されたこと、データの３００番目のバイトが時点８において送信されたこと、データの４００番目のバイトが時点９において送信されたことを示すものと仮定しよう。さらに、ＴＣＰログは、１００番目のバイトの受信通知を時点１０で受信したこと、２００番目のバイトの受信通知を時点１５で受信したこと、３００番目のバイトの受信通知を時点３０で受信したこと、４００番目のバイトの受信通知を時点３１で受信したことを示すものと仮定しよう。
【００８８】
ｈおよびｋの任意の二つのペアをチェックすることによって、バイト当りの遅延を推定することができる。上記例について説明を続けるが、一方の入力は、データの１００番目のバイトが時点５において送信されたという事実であり（参照番号６０参照）、他方の入力は、２００番目のバイトの受信通知を時点１５で受信したという事実である（参照番号６２参照）、ＴＣＰログからの二つの入力を使用すれば、バイト当りの遅延を計算することができる。しかし、データの同じ１００バイトのデータ送信時間、および受信通知受信時間（ｈ＝ｋ）は、比較できないことに留意されたい。何故なら、上記比較を行っても、ネットワークの遅延に関する情報しか入手できないからである。遅延に対するメッセージの影響の大きさを知るには、二つの異なるバイト送信を比較しなければならないからである。
【００８９】
上記例の場合には、ｈ＝１００、ｋ＝２００、（ｋ−ｈ）＝１００、ｔack_recive（ｋ）＝１５、およびｔdata_send（ｈ）＝５である。Δｒimmは分かっているので、αの値は、上記式ｔack_receive（ｋ）−ｔdata_send（ｈ）＝Δｒimm＋α×（ｋ−ｈ）から決定することができる。αに対する異なる値も、ｈおよびｋの種々のペアに対して計算される。好適な実施形態の場合には、α値を平均化することもできるし、最後に計算したα値をバイト当りの遅延として選択することもできる。
【００９０】
図７は、本発明の実施形態の上記計算例のグラフである。ｔack_receive（ｋ）−ｔdata_send（ｈ）が示すように（参照番号６４参照）、データのｈ番目のバイトの送信とデータのｋ番目のバイトの受信通知の受信までの間の経過時間の比較は、往復遅延情報Δｒimmにバイト遅延の（ｋ−ｈ）単位を加えたものを含む。参照番号６６が付いている時間は、α×（ｋ−ｈ）に等しく、一方、Δｒimmは、参照番号６８および７０がついている二つの時間周期で表わされる。
【００９１】
上記の応答時間の推定方法、および下記の応答時間の推定方法は、必ずしも、全応答時間を最短にするための最適サーバ負荷分配の決定の際だけの使用に限定されない。本発明の他の実施形態の場合には、本明細書に記載する応答時間を推定するための方法は、ネットワークの性能を測定のような他の目的に対しても使用することができるが、これに限定されない。
【００９２】
＜ＨＴＴＰログの使用＞
すでに説明したように、本発明の実施形態の場合には、応答時間をＨＴＴＰログを使用して推定することもできる。三つのタイプのＨＴＴＰ接続がある。すなわち、非永続接続、永続接続、およびパイプラインとの永続接続である。非永続接続を使用する場合には、対象物が要求される度に、接続が開き、要求が送信され、情報が受信され、その後で、接続が閉じられる。上記接続は永続接続ではない。それ故、対象物が移送される度に、新しい接続を開かなければならない。永続接続の場合には、接続が開き、複数の対象物に対する要求が送信され、要求された情報が受信され、最後に接続が閉じられる。上記接続はすべての対象物を受信し終るまで閉じられない。パイプラインとの永続接続の場合には、接続が開き、一つの対象物に対する要求が送信されるが、その対象物を受信する前に、さらに、複数の対象物への要求が送信される。それ故、上記複数の要求は、同じ接続内でパイプラインされる。
【００９３】
＜非永続接続＞
非永続接続に対するミラー・サーバ・ログは、下記の情報を含むことができる。
【表１】
0003546850.tif 000014
【００９４】
クライアント（エンドユーザ）とミラー・サーバとの間にプロキシ・サーバが存在する場合があるので、サーバ−クライアント往復遅延を推定するのに下記式を使用することができないことを理解されたい。
ｔｃｏｎ＿ｅｓｔ＿ｒｅｃ−ｔｃｏｎ＿ｅｓｔ＿ｓｅｎｄ
【００９５】
プロキシ・サーバが、エンドユーザとミラー・サーバとの間に存在している場合には、エンドユーザはプロキシ・サーバに要求を行い、その後で、プロキシ・サーバが、ミラー・サーバに要求を行う。要求された情報が、ミラー・サーバにより検索されると、ミラー・サーバは、上記情報をプロキシ・サーバに返送し、その後で、プロキシ・サーバは、上記情報をエンドユーザに返送する。それ故、一つの非永続接続のログからでは、往復遅延を推定することはできない。ｔｒｅｑ＿ｒｅｃ−ｔｃｏｎ＿ｅｓｔ＿ｓｅｎｄは殆どゼロであり、送信遅延とは無関係であり、また、接続は明示の接続終了メッセージを持っていないからである。
【００９６】
しかし、本発明の実施形態の場合には、二つの非永続接続の間の時間は、往復遅延を推定するために使用することができない。エンドユーザのウェブ・ブラウザが、その間に遅延がない状態で一つのページ内に二つの連続している対象物ｏｉおよびｏｉ＋１を要求したと仮定した場合には、下記式のようになる。
ｔｃｏｎ＿ｒｅｑ＿ｒｅｃ（ｉ＋１）−ｔｒｅｓｐ＿ｓｅｎｄ＿ｅｎｄ（ｉ）＝Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔこの式は、ミラー・サーバが、ｉ番目の要求に対して上記対象物を返送した時間、ｔｒｅｓｐ＿ｓｅｎｄ＿ｅｎｄ（ｉ）と、ミラー・サーバが、次の（ｉ＋１）番目の対象物に対する接続要求を受信した時間との間の時間を表わす。この時間は、本質的に、第一の要求の終わりから第二の要求の開始時間までの時間である。
【００９７】
エンドユーザとミラー・サーバとの間にプロキシ・サーバが存在する場合でも、クライアントが非永続接続を使用している限り、上記式による往復遅延の推定は正確であることに留意されたい。さらに、クライアントが（パイプラインでない）永続接続を使用しているが、プロキシ・サーバが、接続を複数の非永続接続に分割する場合には、平均Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔは、クライアントとサーバとの間の往復遅延の合理的な推定値を供給する。しかし、クライアント（または、中間プロキシ・サーバ）が、同時非永続接続を使用している場合には、Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔは、二つの連続している接続の間の遅延により推定することはできない。
【００９８】
＜永続接続＞
永続接続的な、非パイプラインタイプの永続接続に対するサーバ・ログは、下記情報を含むことができる。
【表２】
0003546850.tif 000015
【００９９】
本発明の実施形態の場合には、クライアントとサーバ間の往復遅延を推定するために、下記式を使用することができる。
ｔcon_close_rec−ｔresp_send_end（ｌａｓｔ）＝Δｒserver,client
または、もっと一般的に、下記式を使用することができる。
ｔreq_rec（ｊ＋１）−ｔresp_send_end（ｊ）＝Δｒserver,client
【０１００】
永続接続に対する往復遅延の推定は、非永続接続に対する往復遅延の推定に非常によく似ているが、通常、もっと正確である。非永続接続の場合には、同じクライアント・ブラウザが、間に遅延がない状態で、一つのページ内に、二つの連続している対象物を要求したと仮定する必要がある。永続接続を使用した場合には、その特定の接続内のすべての要求が、一つのページ内の連続している対象物に対する同じクライアント・ブラウザからのものであり、その間に他の遅延がないことが分かっている。
【０１０１】
＜パイプラインを使用する永続接続＞
永続接続パイプラインタイプの接続のサーバ・ログは、パイプライン・タイプでない永続接続に類似している。それ故、本発明の実施形態の場合には、クライアントとサーバとの間の往復遅延は、依然として下記式により推定することができる。
ｔｃｏｎ＿ｃｌｏｓｅ＿ｒｅｃ−ｔｒｅｓｐ＿ｓｅｎｄ＿ｅｎｄ（ｌａｓｔ）＝
Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔ
【０１０２】
永続パイプラインタイプ接続を使用した場合には、複数の要求は、通常、重畳していて、入手できる時間情報だけが、最後の要求、ｔｒｅｓｐ＿ｓｅｎｄ＿ｅｎｄ（ｌａｓｔ）である。その後で、最後の要求を使用して、上記永続接続に類似の方法により計算を行うことができる。すべてのウェブ・ブラウザが、接続オフ・メッセージを送信し、そのため、永続接続パイプラインタイプの接続を使用する場合には、往復遅延時間を推定するために、上記式をいつでも使用することができないことに留意されたい。さらに、永続パイプライン・タイプ接続で、最後の要求を使用した場合でも、必要なすべてのものは、往復遅延時間の一つのサンプルであることにも留意されたい。それ故、この状況において使用することができるデータ・ポイントが一つしかない場合でも、それで十分である。
【０１０３】
＜一回のＨＴＴＰ接続中に、クライアントが観察した往復遅延の推定＞
上記各節においては、本発明の実施形態の推定往復遅延時間の計算について説明した。しかし、上記発見的アルゴリズムを使用するためには、クライアントが観察した全応答時間を推定しなければならない。この全応答時間は、往復遅延時間およびミラー・サーバが要求を処理するために必要なサーバ遅延を含む。ＨＴＴＰログから入手した情報を使用して、接続の性質による、異なる技術により、クライアント・ソフトウェアが観察した応答時間を推定することができる。
【０１０４】
非永続接続を使用した場合、本発明の実施形態の場合には、サーバの応答時間は下記式により推定することができる。
【数３１】
0003546850.tif 000016
【０１０５】
上記最初の項は、サーバがそのプロセスに関連した時間（サーバ遅延）を表わす。後者の項は、往復遅延、すなわち、（サーバが接続要求を受信する前であって、サーバが最後のバイトを送信した後で）クライアントが観察した二つのネットワーク遅延を表わす。
【０１０６】
パイプライン・タイプでない永続接続を使用する場合、本発明の実施形態の場合には、サーバの応答時間は、下記式により推定することができる。
【数３２】
0003546850.tif 000017
【０１０７】
（括弧内の）上記第一の項は、そのプロセスに、サーバが関連した時間（サーバ遅延）を示す。エンドユーザが観察した応答時間を発見するために、接続確立中のネットワーク遅延を加算しなければならないし、また、接続を終了中のネットワーク遅延を差し引かなければならない。
【０１０８】
図８は、本発明の実施形態の上記式を表わすグラフである。サーバ遅延（ｔｃｏｎ＿ｃｌｏｓｅ＿ｒｅｃ−ｔｃｏｎ＿ｒｅｑ＿ｒｅｃ）（参照番号７２参照）を接続確立中のネットワーク遅延Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔ／２（参照番号７４参照）に加算する場合で、接続終了中のネットワーク遅延をΔｒｓｅｒｖｅｒ，ｃｌｉｅｎｔ／２（参照番号７６参照）から差し引く場合には、エンドユーザが見る全応答時間（参照番号７８参照）を推定することができる。上記式においては、参照番号７４および７６で表わす遅延は、実際には打ち消し合わないが、他の実施形態の場合には、計算した全応答時間が、唯一の推定値であるので、打ち消し合うと仮定することができる。
【０１０９】
パイプラインを使用する永続接続の場合には、本発明の実施形態により、パイプラインを使用しない永続接続と類似の方法により、下記式を使用して全応答時間を推定することができる。
ｔｃｏｎ＿ｃｌｏｓｅ＿ｒｅｃ−ｔｃｏｎ＿ｒｅｑ＿ｒｅｃ
【０１１０】
＜ページ検索中にクライアントが観察した応答時間の推定＞
ページの検索は、ＨＴＭＬ文書の検索、およびその後の上記文書内の一組の対象物の検索からなる。このプロセスは、単一または複数のＨＴＴＰ接続で実行することができる。ＨＴＭＬ文書のコンテンツは分かっているので、ブラウザがどの対象物を要求することができるかも分かっている。それ故、サーバ・ログを使用して、ユーザは、すべての対象物が送信される時間を決定することができる。サーバ・ログおよび上記の往復遅延推定値を使用して、クライアントが観察した全応答時間を測定することができる。
【０１１１】
しかし、プロキシ・サーバまたはクライアント自身のキャッシュに、いくつかの対象物がキャッシュされるために、ページ内のすべての対象物に対する要求が、ミラー・サーバに到着しない場合には、応答時間の推定は重要な問題である。新しい接続／対象物要求がこの制限周期中にミラー・サーバに到着しない場合には、クライアントが、すでにＨＴＭＬ文書内に残りの対象物をすでに持っていると仮定できるように制限周期を確立しなければならない。クライアントが、対象物要求の間ムダに過ごしていないと仮定した場合には、上記制限時間を下記式のように確立することができる。
制限＝Δｒｓｅｒｖｅｒ，ｃｌｉｅｎｔ
【０１１２】
本発明の実施形態の場合には、所与のページ内のある対象物に対する最後の要求がサーブされた後で、制限単位の時間が経過し、他の要求を受信しなかった場合には、全応答時間推定プロセスを終了させることができ、クライアントに全ページが供給されたものとみなすことができる。すなわち、ある対象物がキャッシュ内に記憶されたか、プロキシ・サーバ内に記憶された場合には、その対象物に対する要求は、けっしてミラー・サーバにより受信されない。推定プロセスは、その要求に対して無制限に待機すべきではない。何故なら、その要求はけっして受信されないからである。それ故、プロセスが、往復遅延時間に等しい長さの時間待機し、任意の対象物に対する要求を受信しなかった場合には、その対象物に対するその要求は、キャッシュまたはプロキシ・サーバにより、すでにサーブされたものと見なすことができる。
【０１１３】
キャッシュまたはプロキシ・サーバ内に対象物が存在しない場合には、ミラー・サーバからある対象物を取り出すために、往復遅延時間より長い時間の間待機すべきではないことに留意されたい。それ故、特定の対象物に対して、往復遅延時間以上の間待機しないということは、プロセスは、本質的に、ミラー・サーバが、その対象物に対する要求を処理するのに要する時間を考慮に入れていることになる。それ故、待機時間を、エンドユーザまたはクライアントが観察した推定応答時間内に含めることができる。
【０１１４】
それ故、本発明の実施形態は、コンテンツ配送システムのユーザが観察した全応答時間を最も短くする割当てを使用して、要求を行っているエンドユーザと同じ領域、または他の領域内で、エンドユーザをミラー・サーバに再転送するためのシステムおよび方法を提供する。本発明の実施形態は、また、負荷容量を考慮に入れながら、ミラー・サーバの負荷のバランスをとる割当てを使用することによって、エンドユーザをミラー・サーバに再転送するためのシステムおよび方法を提供する。
【０１１５】
さらに、本発明の実施形態は、コンテンツ配送システムのユーザが観察した全応答時間を最も短くする割当てを使用して、エンドユーザをミラー・サーバに再転送するためのシステムおよび方法を提供する。この場合、新しいミラー・サーバの追加、または顧客コンテンツ・プロバイダのサービスの終了によるリソースが増加しても、負荷バランス制限が守られている限り、負荷の再分配を生じない。さらに、本発明の実施形態の場合には、全応答時間が、指定のしきい値以下に維持されている場合に限って、新しい顧客コンテンツ・プロバイダが追加され、負荷または現在の顧客に対する変更があっても、全応答時間は、指定のしきい値を超えるほど大きく変化しない。
＜関連出願への相互参照＞
本発明の実施形態は、２０００年８月３１日付の「ウェブ・コンテンツへのアクセスに対する応答時間を最も短くするためのインテリジェント負荷の分配」という名称の、米国特許仮出願第６０／２３０，５６４号の優先権を主張する。上記出願の内容は、引用によって本明細書の記載に援用する。
【図面の簡単な説明】
【図１】エンドユーザ（クライアント・ブラウザ）が、複数のゲートウェイを通して、他の領域内に位置するコンテンツ・プロバイダ・サーバからコンテンツを要求する従来のコンテンツ配送ネットワークである。
【図２】エンドユーザと同じ領域内に位置するミラー・サーバからコンテンツを要求するために、エンドユーザ（クライアント・ブラウザ）が再度割り当てられる従来のコンテンツ配送ネットワークである。
【図３】全応答時間を最も短くする割当てを使用して、エンドユーザと同じ領域、または他の領域内に位置するミラー・サーバからコンテンツを要求するために、特定の領域内のエンドユーザ（クライアント・ブラウザ）が再度割り当てられる本発明の好適な実施形態のコンテンツ配送ネットワークである。
【図４】あるしきい値以下のサーバ負荷の直線性を示す。
【図５】本発明の実施形態のミラー・サーバにエンドユーザを割り当てるための発見的アルゴリズムの一例である。
【図６】あるバイトのデータが、クライアント・ブラウザに送信された時間、およびあるバイトのデータの受信通知をクライアント・ブラウザから受信した時間を示すＴＣＰログ内に記憶している情報の一例を示すタイムラインである。
【図７】本発明の実施形態のバイト当りの遅延を推定するための図６のＴＣＰ情報の使用方法を示すグラフである。
【図８】本発明の実施形態によりエンドユーザが観察した全応答時間を推定するためのＨＴＴＰ情報の使用方法を示すグラフである。
【符号の説明】
１２…ミラー・サーバ
１４…ワイド・エリア・ネットワーク
１６…エンドユーザＡ
１８…コンテンツ・プロバイダ・サーバ
２０…ネットワーク
２２…要求
２６…ゲートウェイ
【図１】
0003546850.tif 000036
【図２】
0003546850.tif 000037
【図３】
0003546850.tif 000038
【図４】
0003546850.tif 000039
【図５】
0003546850.tif 000040
【図６】
0003546850.tif 000041
【図７】
0003546850.tif 000042
【図８】
0003546850.tif 000043