(57)【特許請求の範囲】
【請求項１】
複数の地域を含む網内で用いられる、これら地域間に情報のレプリカキャッシュを分配するための方法であって、前記の各地域が一つのルータ、一つのサーバ、および複数のユーザ端末を含み、前記ルータが前記サーバおよび前記複数のユーザ端末を前記網に接続し、この方法が、
前記網の第一の地域の第一のルータから前記網の第二の地域の複数のルータに向けて、前記情報の元コピーを格納する第一の地域の第一のサーバに向けられた複数のサービスリクエストの測定を前記複数のルータから指令する監視リクエストメッセージを送信するステップと、
前記第一のルータと関連するプロセッサを用いて、前記網内の複数のユーザ端末によって前記情報の前記元コピーに対してなされた前記リクエストの測度を確認するステップと、
前記プロセッサが、前記リクエストの測度に応答して、前記情報のレプリカコピーを格納するために前記網の別の地域の別のサーバへの最適な割当を計算し、そして、前記別の地域内のルータに向けて、前記情報の前記レプリカコピーをレプリカキャッシュとして格納するよう指令するメッセージを送信するステップとを含み、前記別の地域内のルータが、前記網内のキャッシュの分配の総コストを計算するコスト／ベニフィット分析を用いて選択され、そして、
前記最適な割当は、前記複数のユーザ端末とキャッシュの現存する分配との間で交換されるメッセージの帯域幅コストを最小化する、前記情報の元コピーのレプリカの分配であることを特徴とする方法。
【請求項２】
前記第一の地域内の前記プロセッサが、前記リクエストの測度に応答して、少なくとも一つの他の地域内のルータに向けて、前記ユーザ端末によってなされた前記リクエストを前記レプリカキャッシュに向けて転送するよう指令するメッセージを送信するステップをさらに含むことを特徴とする請求項１の方法。
【請求項３】
前記第一の地域内の前記プロセッサが、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記ルータを、コスト／ベニフィット分析を用いて選択するステップをさらに含むことを特徴とする請求項１の方法。
【請求項４】
前記第一の地域内の前記プロセッサが、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記ルータを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析が前記網内のキャッシュの分配の総コストを計算することを特徴とする請求項１の方法。
【請求項５】
前記第一の地域内の前記プロセッサが、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記ルータを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析がレプリカキャッシュを持たないことによって失われる機会のコストを計算することを特徴とする請求項１の方法。
【請求項６】
複数の地域を含む網内で用いられる、これら地域間に情報のレプリカキャッシュを分配するための方法であって、前記の各地域が一つのルータ、一つのサーバ、および複数のユーザ端末を含み、前記ルータが前記サーバおよび前記複数のユーザ端末を前記網に接続し、この方法が、
第一の地域の第一のルータから他の地域内の複数のルータに向けて、前記第一の地域内の第一のサーバに向けられた前記情報の配達を求める複数のユーザ端末からの複数のリクエストを監視するよう前記他のルータに指令する監視リクエストメッセージを送信するステップと、
前記第一のルータの所で、前記網内の複数のユーザ端末によって前記情報に対してなされたリクエストの測度を示す監視応答メッセージを前記他のルータから受信するステップと、
前記応答メッセージに応答して、前記他のルータの少なくとも一つに向けて、前記複数のユーザ端末と情報の現存する分配との間で交換されるメッセージの帯域幅コストを最小化する前記情報の最適分配として前記情報のコピーを格納するよう指令するメッセージを送信するステップとを含み、前記他のルータの少なくとも一つが、前記網内のキャッシュの分配の総コストを計算するコスト／ベニフィット分析を用いて選択されることを特徴とする方法。
【請求項７】
前記応答メッセージに応答して、前記少なくとも一つの他の地域内のルータに、前記第一のサーバに向けられたリクエストをレプリカキャッシュに向けて転送することを指令するメッセージを送信するステップをさらに含むことを特徴とする請求項６の方法。
【請求項８】
前記応答メッセージに応答して、前記第一のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含むことを特徴とする請求項６の方法。
【請求項９】
前記応答メッセージに応答して、前記第一のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析が前記網内のキャッシュの分配の総コストを計算することを特徴とする請求項６の方法。
【請求項１０】
前記応答メッセージに応答して、前記第一のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析がレプリカキャッシュを持たないことによって失われる機会のコストを計算することを特徴とする請求項６の方法。
【請求項１１】
複数の地域を含む網内で用いられる、これら地域間への情報のレプリカキャッシュの分配を最適化するための方法であって、前記の各地域が一つのルータ、一つのサーバ、および複数のユーザ端末を含み、前記ルータが前記サーバおよび前記複数のユーザ端末を前記網に接続し、この方法が、
前記網の第一の地域内の第一のルータの所で、情報の元コピーを格納する第一の地域内の第一のサーバに向けられたサービスリクエストメッセージを前記網内の複数のユーザから受信するステップと、
前記第一のルータから前記網内の第二の地域内の第二のルータに向けて、前記複数のユーザ端末から前記第一のサーバに向けられたサービスリクエストを監視するよう前記第二のルータに指令する監視リクエストメッセージを送信するステップと、
前記第一のルータの所で、前記第一のサーバに向けられたサービスリクエストの数を示す監視応答メッセージを前記第二のルータから受信するステップと、
前記第一のルータの所で、前記網の別の地域内の別のサーバ内に格納する前記情報のレプリカコピーの最適な割当を計算するステップと、
前記第一のルータから前記別のサーバに向けて、前記別のサーバに前記情報の前記レプリカコピーを格納させ、そして前記網の割当てられた下位の複数の地域内のユーザ端末にサービスを提供させる割当てメッセージを送信するステップとを含み、前記別のサーバが、前記網内のキャッシュの分配の総コストを計算するコスト／ベニフィット分析を用いて選択され、そして、
前記最適な割当は、前記複数のユーザ端末とキャッシュの現存する分配との間で交換されるメッセージの帯域幅コストを最小化する、前記情報の元コピーのレプリカの分配であることを特徴とする方法。
【請求項１２】
前記計算するステップが、前記別のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含むことを特徴とする請求項１１の方法。
【請求項１３】
前記計算するステップが、前記別のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析が前記網内のキャッシュの分配の総コストを計算することを特徴とする請求項１１の方法。
【請求項１４】
前記計算するステップが、前記別のサーバを、コスト／ベニフィット分析を用いて選択するステップをさらに含み、前記分析がレプリカキャッシュを持たないことによって失われる機会のコストを計算することを特徴とする請求項１１の方法。
【請求項１５】
複数の地域を含む網内で用いられる、これら地域間への情報のレプリカキャッシュの分配を最適化するための方法であって、前記の各地域が一つのルータ、一つのサーバ、および複数のユーザ端末を含み、前記ルータが前記サーバおよび前記複数のユーザ端末を前記網に接続し、この方法が、
前記網内の複数のユーザからのサービスリクエストメッセージを、情報の元コピーを格納する第一の地域内の第一のサーバに転送するステップと、
前記網の第二の地域内の第二のルータ所で、前記第一のサーバに向けられるサービスリクエストを監視するよう前記第二のルータに指令する前記第一のルータからの監視リクエストメッセージを受信するステップと、
前記第二のルータの所で、前記第一のサーバに向けられたサービスリクエストを監視するステップと、
前記第二のルータから前記第一のルータに向けて、前記第一のサーバに向けられたサービスリクエストの数を示す監視応答メッセージを送信するステップと、
前記第二のルータの所で、前記網の前記第二の地域内の第二のサーバで格納する前記情報のレプリカコピーの最適割当てを含む割当てメッセージを前記第一のルータから受信するステップと、
前記第二のサーバが、前記情報の前記レプリカコピーを格納し、そして前記網の割当てられた下位の複数の地域内のユーザ端末にサービスを提供するステップとを含むことを特徴とする方法。
【請求項１６】
複数の地域を含む網内で用いられる、これら地域間に情報のレプリカキャッシュを分配するためのシステムであって、前記の各地域が一つのルータ、一つのサーバ、および複数のユーザ端末を含み、前記ルータが前記サーバおよび前記複数のユーザ端末を前記網に接続し、このシステムが、
第一の地域内の第一のサーバと第一の複数のユーザ端末とを前記網に接続する、前記第一の地域内の第一のルータと、
前記第一の地域内の前記複数のユーザ端末によって前記情報に対してなされたリクエストの測度を確認する、前記第一のルータに接続されたプロセッサとを含み、
前記第一のルータが、前記リクエストの測度に応答して、少なくとも一つの他の地域内の第二のルータに向けて、前記情報のコピーをレプリカキャッシュとして格納するよう指令するメッセージを送信することを特徴とするシステム。
【請求項１７】
前記第一の地域内の前記第一のルータがさらに、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記第二のルータに向けて、前記ユーザ端末によってなされた前記リクエストを前記レプリカキャッシュに向けて転送するよう指令するメッセージを送信することを特徴とする請求項１６のシステム。
【請求項１８】
前記プロセッサがさらに、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記第二のルータを、コスト／ベニフィット分析を用いて選択することを特徴とする請求項１６のシステム。
【請求項１９】
前記プロセッサがさらに、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記第二のルータを、コスト／ベニフィット分析を用いて選択し、前記分析が前記網内のキャッシュの分配の総コストを計算することを特徴とする請求項１６のシステム。
【請求項２０】
前記プロセッサがさらに、前記リクエストの測度に応答して、少なくとも一つの他の地域内の前記第二のルータを、コスト／ベニフィット分析を用いて選択し、前記分析がレプリカキャッシュを持たないことによって失われる機会のコストを計算することを特徴とする請求項１６のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は電気通信、より詳細には、情報のレプリカキャッシュの網の多様な地域への分配を最適化するための方法および装置に関する。
【０００２】
【従来の技術】
インターネット上のメッセージトラヒックには生来的な冗長が存在し、このため、しばしば、バックボーン網上に過剰な負荷が生成される。インターネット上の幾つかのアプリケーションをキャッシュメモリ内に複製し、ウエブ代理を提供すれば、データ転送における幾らかの不要な複製動作を軽減することが可能となる。マルチカースティング法の実施は、分配の効率を向上するためのもう一つの技術である。マルチカースティング法においては、送信者は、同一のドキュメント、データ、あるいはメッセージを、通常は広い地域内の分散して存在する多数の受信者に分配する。
【０００３】
効率を向上させるために、マルチカーストドキュメントのコピーを各地域内の所定のサーバに配布し、ローカル的な配布は、そのサーバに委任するようなスキームを採用すると有益であるが、このレプリカキャッシュメカニズムには、効率的なツリー構築アルゴリズムが必要となる。この方法の幾つかの例が、既に、レプリカキャッシュの静的な分配に対してインターネットプロトコル内で用いられている。
【０００４】
【発明が解決しようとする課題】
現存のインターネット上にキャッシュを複製する方法では解決することが不可能な重要な問題が存在する。主な問題は、インターネットトラヒックが、時間および地域の両方において、動的に変化することである。例えば、一日の内のある時間帯はアクティブであるが（トラヒックの量が多いが）、他の時間帯はインアクティブ（トラヒックの量が少ない）地域が存在する。このために、網内に複製されたキャッシュの役割を果たすサーバを動的に割当て／再割当てするための方法が必要とされている。
【０００５】
【課題を解決するための手段】
本発明の一つの用途においては、網は、複数の地域を含み、各地域は一つのルータ、一つのサーバ、および複数のユーザ端末を持つ。各地域内のルータは、このサーバおよび複数のユーザ端末を網に接続する。本発明によると、情報のレプリカキャッシュの網の複数の地域への分配が使用パターンの変化に基づいて動的に最適化される。本発明のこの動作は、ここでは逆ツリー生成と呼ばれる。最初に、第一の地域内の単一のサーバが、情報の元コピーを格納する。この第一の地域内のルータは、網全域の複数のユーザからのこの元コピーを格納するサーバに向けられたサービスリクエストメッセージを受信する。
【０００６】
このルータ内あるいはこのルータと関連するプロセッサは、網の他の地域内の他のルータに向けて、それらルータに対して各地域内で観察される前記第一のサーバ内の元コピーに向けられた全てのサービスリクエストの数を監視（測定）することを求める監視リクエストメッセージを送信する。プロセッサは、このメッセージに応答して、他のルータからの前記第一のサーバに向けられたサービスリクエストの数を示す監視応答メッセージを受信する。
【０００７】
プロセッサは、監視応答メッセージを用いて情報のレプリカコピーの最適な割当てを計算し、これに基づいて、情報のレプリカコピーを格納すべき網内の少なくとも一つの新たなサーバを決定する。プロセッサは、次に、こうして割当てられた新たなサーバに向けて、レプリカ作成メッセージを送信する。サーバは、このレプリカ作成メッセージに基づいて情報のレプリカコピーを格納し、網の新たな割当てられたセットの地域内のユーザ端末にサービスを提供する。プロセッサは、さらに、網内の他のルータに向けて割当てメッセージを送信する。他のルータは、この割当てメッセージに基づいて、各自の地域からのトラヒックを、新に割当てられたサーバ、あるいは第一のサーバのいずれかに向けて転送する。
【０００８】
この要約（発明を解決するための手段）、図面の簡単な説明、詳細な説明（発明の実施の形態）および図面は、単に、本発明の一例を示すものであり、この明細書に由来する特許によって授与される排他的な権利の範囲を制限することを意図するものではなく、これら排他的な権利の範囲は、明細書の冒頭の特許請求の範囲によって定義されるものである。
【０００９】
【発明の実施の形態】
図１Ａ〜図１Ｅは、情報のレプリカキャッシュを自身のさまざまな地域に最適に分配するために網が自身を自動的に編成する際の一例としての網の一連のステージを示す。本発明のこの動作は、以降、逆ツリー生成と呼ばれる。示される一例としての網は、インターネットバックボーン網１０のまわりに構築された合衆国におけるインターネット網である。図１Ａは、網の編成における第一のステージを示す。この第一のステージにおいて、北東地域２０内のサーバ４０は、データセットのソール（元）コピーを格納するが、これが、網の全ての地域内のユーザによってアクセスされる。サーバ４０内のこのデータセットのコピーが、元情報キャッシュ“Ｐ”となる。このデータセットは、例えば、特定のインターネットウエブサイトに対する情報を表す。動作が安定している際は、網の全ての地域内のユーザからのサービスリクエストは、網のこの北東地域２０内のルータ３０の所に受信される。これらサービスリクエストは、サーバ４０内に格納されたデータセットの元キャッシュ“Ｐ”へのアクセスを求める。仮に、このデータセットが、人気のあるウエブサイトである場合、例えば、New York Timesのウエブサイト“www.nytimes.com ”を表す場合は、ルータ３０は、これらサービスリクエストを扱うために、常に極めて多忙な状態に置かれる。本発明は、ルータ３０上のサービスリクエストの負荷を、自動的にデータセットの一つあるいは複数のレプリカを網の遠隔地域内の新たなサーバに分配し、新たなルーティングテーブルを網内のルータに割当てることによって軽減することを目指す。これら新たなルーティングテーブルは、遠隔地域内のユーザから発信されたサービスリクエストを、これら新たなサーバに向けて転送し、これら新たなサーバが元のサーバ４０とサービスリクエストの負荷を共有することとなる。
【００１０】
図１の網１Ａは、複数の地域、すなわち：北東地域２０、北中央地域２２、北西地域２４、南東地域２６、南中央地域２８、および南西地域２９を含む。各地域は、それぞれ、ルータ３０、３２、３４、３６、３８、３９を含み、各ルータは、それぞれ、経路３０’、３２’、３４’、３６’、３８’、３９’によってバックボーン網１０に接続される。各地域は、それぞれ、サーバ４０、４２、４４、４６、４８、４９を含み、各サーバは、それぞれ、自身のルータによって、経路４０’、４２’、４４’、４６’、４８’、４９’に接続される。各地域は、それぞれ、複数のユーザ端末５０、５２、５４、５６、５８、５９を含み、各ユーザ端末は、それぞれ、自身のルータによって、経路５０’、５２’、５４’、５６’、５８’、５９’に接続される。各地域内において、自身のルータは、自身のサーバおよび自身の複数のユーザ端末を、それぞれ、リンク３０’、３２’、３４’、３６’、３８’、３９’によって、インターネットバックボーン網１０に結合する。図２Ｄは、北東地域２０内のサーバ４０がデータセットのソール（元）コピーを元キャッシュ“Ｐ”として格納し、これが網の全ての地域内のユーザによってアクセスされる図１Ａの網の元の編成に対する現存のルータテーブル３３４を示すが、現時点においては、ルータテーブル３３４が、網内の各ルータ３０、３２、３４、３６、３８、３９の所に格納されている。
【００１１】
図１Ｂは、情報のレプリカキャッシュをこれら地域間に最適に分配するために自身を編成する網の第二のステージを示す。このステージにおいては、最初に、ルータ３０あるいはルータ３０と関連するプロセッサは、バックボーン網１０に接続された他の全てのルータ３２、３４、３６、３８、３９に向けて、他のルータに対して自身の地域内で発信されたがサーバ４０内の元キャッシュに向けて転送されたサービスリクエストの数を監視（測定）するように求める監視リクエストメッセージを送信する。図２Ａは監視リクエストメッセージ２００の一例を示すが、このメッセージが、ルータ３０によって、バックボーン網１０に接続された他の全てのルータに送られる。監視リクエストメッセージ２００は、宛先ルータを指定するフィールド２０２、ソースルータを指定するフィールド２０４、および監視リクエストを指定するフィールド２０６を含み、このような監視リクエストメッセージが、網内の他の全てのルータ３２、３４、３６、３８、３９に向けて一斉に送信される。
【００１２】
図３は、ルータ３０のアーキテクチャを示す。網内の他の全てのルータ３２、３４、３６、３８、３９も類似するアーキテクチャを持つ。ルータ３０は、メモリ３０２を含むが、メモリ３０２は、システムバス３０４によって、網アダプタ３０８、ディスクドライブメモリ３０６、プロセッサ３１０、およびサーバインタフェース３１２に接続される。網アダプタ３０８は、ルータ３０を、経路３０’を通じて、バックボーン網１０に接続する。サーバインタフェース３１２は、ルータ３０を経路４０’を通じて、サーバ４０に接続する。インタフェース３１２は、また、ルータ３０を経路５０’を通じて、図１Ａのユーザ（端末）５０に接続する。
【００１３】
図３のメモリ３０２は、サービスリクエストメッセージバッファ３２２を格納するが、このバッファは、バックボーン網１０からおよびローカルユーザ５０からのサービスリクエストメッセージを受信し、これらリクエストメッセージは、処理のためにサーバ４０にパスされる。図３のメモリ３０２は、さらに、サービス応答メッセージバッファ３２４を格納するが、このバッファは、サーバ４０からのサービス応答メッセージを受信し、これらサービス応答メッセージは、バックボーン網１０あるいはローカルユーザ５０に転送される。
【００１４】
図３のメモリ３０２は、さらに、監視リクエストメッセージバッファ３２６を格納するが、このバッファは、図２Ａの監視リクエストメッセージ２００を格納する。この監視リクエストメッセージ２００は、メッセージ２００を発信するルータ３０内のバッファ３２６内において生成（構築）され、網アダプタ３０８によって、他のルータ３２、３４、３６、３８、３９に送信される。このステージが、ルータ３０がトラヒックを監視するリクエストを他のルータに一斉に送るところを示す図１Ｂに示される。ルータ３２、３４、３６、３８、３９は、自身の網アダプタ３０８を通じて監視リクエストメッセージ２００を受信する。このメッセージは、各ルータの監視リクエストメッセージバッファ３２６内に緩衝された後に読み出される。監視リクエストメッセージ２００は、サーバ４０内に元キャッシュ“Ｐ”として格納されているデータセットを識別する。監視リクエストメッセージ２００は、宛先ルータ３２、３４、３６、３８、３９に対して、自身が扱う全てのメッセージを監視することで、元キャッシュ“Ｐ”として格納されているデータセットへのアクセスを求めるサーバ４０に向けて転送されたサービスリクエストの数をカウントするように要請する。監視リクエストメッセージ２００は、さらに、宛先ルータ３２、３４、３６、３８、３９に対して、トラヒック値、すなわち、ある与えられた時間期間に渡ってのこれらサービスリクエストの累積カウントを送り返すように要請する。
【００１５】
図３のメモリ３０２は、さらに、トラヒック監視プログラム３２９を格納するが、このプログラムは、オペレーティングシステムプログラム３２０の制御下でランし、このインストラクションはプロセッサ３１０上で実行される。自身の網アダプタ３０８を通じて監視リクエストメッセージ２００を受信するルータ３２、３４、３６、３８、３９内において、このトラヒック監視プログラム３２９は、監視リクエストメッセージバッファ３２６内に緩衝された監視リクエストメッセージ２００を読み出し、図１Ｃに示すようなトラヒック監視動作を遂行する。各宛先ルータ３２、３４、３６、３８、３９内において、このトラヒック監視プログラム３２９は、自身が扱う全てのメッセージを監視し、元キャッシュ“Ｐ”として格納されたデータセットへのアクセスを求めるサーバ４０に向けて転送されたサービスリクエストの数をカウントする。発信ルータ３０内のトラヒック監視プログラム３２９も、ルータ３０自身の地域２０内のユーザ５０に対してこの監視動作を遂行する。各ルータ３０、３２、３４、３６、３８、３９内のトラヒック監視プログラム３２９は、監視リクエストメッセージ２００に応答して、トラヒック値、すなわち、ある時間期間に渡って累積された、転送されたサービスリクエストのカウントをルータ３０に送り返す。図３のメモリ３０２は、さらに、監視応答メッセージバッファ３２８を格納するが、このバッファは、こうして送り返される監視応答メッセージ２２０を格納する。監視応答メッセージ２２０は、宛先ルータを指定するフィールド２２２、ソースルータを指定するフィールド２２４、および監視応答、すなわち、そのルータの所で測定されたトラヒック値を指定するフィールド２２６を含む。この監視応答メッセージ２２０が、監視リクエストメッセージ２００に応答して、各ルータ３２、３４、３６、３８、３９によって発信ルータ３０に送り返される。
【００１６】
図３のメモリ３０２は、さらに、最適レプリカキャッシュ割当てプログラム３３０を格納するが、このプログラムは、オペレーティングシステムプログラム３２０の制御下でランし、このインストラクションはプロセッサ３１０上で実行される。図１Ｄの発信ルータ３０において、この最適レプリカキャッシュ割当てプログラム３３０は、元キャッシュ“Ｐ”として格納されたデータセットのレプリカの最適な分配を計算する。この計算は、各ルータ３２、３４、３６、３８、３９によって報告された各遠隔地域２２、２４、２６、２８、２９におけるトラヒック値、並びにルータ３０によって地域２０においてローカル的に測定されたトラヒック値に基づいて行なわれる。この最適レプリカキャッシュ割当てプログラム３３０については、図４に流れ図にて示される。
【００１７】
最適レプリカキャッシュ割当てプログラム３３０は、レプリカキャッシュを追加あるいは削除することのコスト（損）／ベニフィット（益）分析を遂行するアルゴリズムに基づく。このコスト／ベニフィット分析アルゴリズムについては、図５および図６に示される第二の網に適用する例との関連で後により詳細に説明する。最適レプリカキャッシュ割当てプログラム３３０は、このコスト／ベニフィット分析を網の遠隔地域からの更新されたトラヒック監視測定値に基づいて定期的に更新する。コスト／ベニフィット分析アルゴリズムは、ある地域にトラヒックの棄却閾値量が累積されたか否かを決定し、トラヒック量がこの棄却閾値を超えた場合は、新たなサーバ上にレプリカキャッシュを設定することが正当化される。コスト／ベニフィット分析アルゴリズムは、最小重みスパニングツリー分析(minimum weight spanning tree analysis) あるいはSteinerツリー分析(Steiner tree analysis)を用いてこの決定を行なう。最適レプリカキャッシュ割当てプログラム３３０は、次に、サービスリクエストの幾つかをこの新たなサーバ上のレプリカキャッシュに向けて転送することを要請する新たなルーティングテーブルを計算し、これを網内の各ルータに送る。図３のメモリ３０２は、さらに、現存のルータテーブル３３４および新たなルータテーブル３３６を格納するが、現存のルータテーブル３３４の一例が図２Ｄに示され、新たなルータテーブル３３６の一例が図２Ｅに示される。
【００１８】
図３のメモリ３０２は、さらに、割当てメッセージバッファ３３２を格納するが、ルータ３０は、このバッファ内に、図２Ｃに示されるような割当てメッセージ２１０を構築（生成）する。この割当てメッセージ２１０は、宛先ルータを指定するフィールド２１２、ソースルータを指定するフィールド２１４、およびコスト／ベニフィット分析アルゴリズムによって計算された新たなルーティング割当てを指定するフィールド２１６を含む。図２Ｆには、割当てメッセージ２１０の一例が示される。割当てメッセージ２１０のフィールド２１２は、宛先ルータ３２、３４、３６、３８、３９へのブロードカーストを指定する。フィールド２１４は、ソースルータをルータ３０として指定する。割当てフィールド２１６は、図２Ｅに示される一例としての新たなルータテーブル３３６を指定する。この割当てメッセージ２１０が、網内の全ての他のルータ３２、３４、３６、３８、３９に一斉に送られる。この割当てメッセージ２１０は、発信ルータ３０内にも使用のために格納される。次に、図２Ｇに示されるようなレプリカ作成メッセージ８０２が、例えば、ルータ３４に向けて、データセットのコピーをレプリカキャッシュ“Ａ”として地域２４内の新たなサーバ４４に提供するために送られる。このメッセージ８０２のフィールド２１２は宛先ルータ３４を指定し、フィールド２１４はソースルータをルータ３０として指定する。同様なレプリカ作成メッセージが、ルータ３０から、例えば、ルータ３８に向けて、データセットのコピーをレプリカキャッシュ“Ｂ”として地域２８内の新たなサーバ４８に提供するために送られる。
【００１９】
図１Ｅは、図１Ａの網に関して本発明の逆ツリー生成動作を遂行した後の、すなわち、ルータ３０によって、割当てメッセージ２１０が網内の他の全てのルータ３２、３４、３６、３８、３９に一斉に送信された後の状態を示す。また、図２Ｅは、この結果として網内に２つの追加のレプリカキャッシュが生成された図１Ｅの網の更新された編成に対する新たなルータテーブルを示す。レプリカキャッシュ“Ａ”は、地域２４内の新たなサーバ４４内に格納されたデータセットの新たなコピーであり、ルータ３４は、サーバ４４に向けられた全てのサービスリクエストを扱う。サーバ４４のサービス領域６０Ａは、北西地域２４および南西地域２９である。地域２４内のルータ３４および地域２９内のルータ３９は、図２Ｅに示すような新たなルータテーブル３３６によって制御され、データセットへのアクセスを求める地域２４および２９内で発信された全てのサービスリクエストは、サーバ４４上のレプリカキャッシュ“Ａ”に向けて転送される。レプリカキャッシュ“Ｂ”は、地域２８内の新たなサーバ４８内に格納されたデータセットの新たなコピーであり、ルータ３８は、サーバ４８に向けられた全てのサービスリクエストを扱う。サーバ４８のサービス領域６０Ｂは、北中央地域２２および南中央地域２８である。地域２２内のルータ３２および地域２８内のルータ３８は、図２Ｅに示すような新たなルータテーブル３３６によって制御され、データセットへのアクセスを求める地域２２および２８内で発信された全てのサービスリクエストは、サーバ４８上のレプリカキャッシュ“Ｂ”に向けて転送される。元キャッシュ“Ｐ”は、地域２０内の元のサーバ４０内に格納されたデータセットの現存のコピーであり、ルータ３０は、サーバ４０に向けられた全てのサービスリクエストを扱う。サーバ４０のサービス領域６０は、北東地域２０および南東地域２６である。地域２０内のルータ３０および地域２６内のルータ３６は、図２Ｅに示すような新たなルータテーブル３３６によって制御され、データセットへのアクセスを求める地域２０および２６内で発信された全てのサービスリクエストは、サーバ４０上の元キャッシュ“Ｐ”に向けて転送される。
【００２０】
図１Ｆは、自身を元キャッシュと変更されたサービス領域を持つ変更されたレプリカキャッシュを持つように定期的に再編成することで得られた結果としての網の状態を示す。図１Ｅにおいて、ルータ３０は、定期的に、バックボーン網１０に接続された全ての他のルータ３２、３４、３６、３８、３９に向けて、他のルータに対して自身の地域内から発信されたレプリカキャッシュ“Ａ”、レプリカキャッシュ“Ｂ”、あるいは元キャッシュ“Ｐ”のデータセットへのアクセスを求めるサービスリクエストの数を監視（測定）するように要請する監視リクエストメッセージ２００を送信する。ルータ３２、３４、３６、３８、３９は、自身のアダプタ３０８を介してこの監視リクエストメッセージ２００を受信し、これを監視リクエストメッセージバッファ３２６内に格納する。トラヒック監視プログラム３２９は、こうして監視リクエストメッセージバッファ３２６内に格納された監視リクエストメッセージ２００を読み出し、トラヒック監視動作を遂行する。各宛先ルータ３２、３４、３６、３８、３９内で、トラヒック監視プログラム３２９は、自身のルータが扱う全てのメッセージを監視し、それぞれ、元キャッシュ“Ｐ”、レプリカキャッシュ“Ａ”、あるいはレプリカキャッシュ“Ｂ”として格納されているデータセットへのアクセスを求めるサーバ４０、４４、あるいは４８に向けて転送されたサービスリクエストの数をカウントする。発信ルータ３０は、元キャッシュ“Ｐ”として格納されているデータセットのレプリカの最適な分配を計算するが、この計算は、ルータ３２、３４、３６、３８、３９によって報告された遠隔地域２２、２４、２６、２８、２９内のトラヒック値、並びに、ルータ３０によって地域２０においてローカル的に測定されたトラヒック値に基づいて行なわれる。図１Ｆは、ルータ３０によって、割当てメッセージ２１０が網内の他の全てのルータ３２、３４、３６、３８、３９に一斉に送信された後の図１Ｅの網の状態を示す。レプリカキャッシュ“Ａ”は、以前と同一のままで、地域２４内のサーバ４４内に格納されたデータセットのコピーである。ただし、ここでは、サーバ４４のサービス領域６０Ａ’は、変更され、北西地域２４および北中央地域２２となる。地域２４内のルータ３４および地域２２内のルータ３２は、新たなルータテーブルによって制御され、データセットへのアクセスを求める地域２４および２２内で発信された全てのサービスリクエストは、サーバ４４上のレプリカキャッシュ“Ａ”に向けて転送される。ここでは、レプリカキャッシュ“Ｂ”は削除され、代わりに、レプリカキャッシュ“Ｃ”が、地域２９内の新たなサーバ４９内にデータセットの新たなコピーとして格納されている。ルータ３９は、サーバ４９に向けられた全てのサービスリクエストを扱う。サーバ４９のサービス領域６０Ｃは、南西地域２９および南中央地域２８である。地域２９内のルータ３９および地域２８内のルータ３８は、新たなルータテーブルによって制御され、データセットへのアクセスを求める地域２９および２８内で発信された全てのサービスリクエストは、サーバ４９上のレプリカキャッシュ“Ｃ”に向けて転送される。元キャッシュ“Ｐ”は、地域２０内の元のサーバ４０内に格納されているデータセットの現存のコピーである。サーバ４０のサービス領域６０は、北東地域２０および南東地域２６である。地域２０内のルータ３０および地域２６内のルータ３６は、新たなルータテーブルによって制御され、データセットへのアクセスを求める地域２０および２６内で発信された全てのサービスリクエストは、サーバ４０上の元キャッシュ“Ｐ”に向けて転送される。このようにして、網は、動的に変化するトラヒックパターンを収容するために、自身を定期的に、元キャッシュおよび変更されたサービス領域を持つ変更されたレプリカキャッシュを持つように再編成する。
【００２１】
以下では、最適レプリカキャッシュ割当てプログラム３３０について図４の流れ図との関連で詳細に説明する。最適レプリカキャッシュ割当てプログラム３３０は、コスト／ベニフィット分析アルゴリズム４１５を用いるが、これは、一種の最小重みスパニングツリー分析であり、網内の全てのルータノードを接続するリンクから無向グラフが形成される。これらリンクは、網内の全てのルータを接続し、このグラフ全体に渡るツリーを形成するめたに、“スパニングツリー（全域木）”の名称を持つ。各リンクには、単位時間当たりのリクエストの数と関係するコスト値“Ｔ”を用いて重みを付けられる。ここで、コスト値“Ｔ”は、目標サーバ上の目標キャッシュ内に格納された与えられたサイズのデータセットを求めてリンク上を通過するリクエストの数を表す。つまり、“Ｔ”の値は、リンクの単位時間当たりのリクエストメッセージのトラヒック数を表す。全てのリンクに対する単位時間当たりのリクエストメッセージの総数は、帯域幅コストＣ［ＢＷ］として表され、現存のキャッシュの分配の総コトスＣ［Ｔ］は、この帯域幅コストＣ［ＢＷ］を要素として含む。最適レプリカキャッシュ割当てプログラム３３０は、総コストＣ［Ｔ］を最小にするようなデータセットを格納するレプリカキャッシュの分配方法を見つけだすことを目的とし、こうして、コスト／ベニフィット分析アルゴリズム４１５は、一種の最小重みスパニングツリー分析であることがわかる。
【００２２】
図４のステップ４０２は、現存のキャッシュの分配の総コストＣ［Ｔ］を計算することから開始される。リプリカキャッシュを格納するサーバを追加することの影響を評価するためにコスト関数が定義されるが、このコスト関数は、利用される資源、および様々なコストを考慮に入れる。これには、単一のサーバ（あるいは一連のサーバ）がオーバロードされ、サービスを受けることなく顧客が切断されることによって失われるオパチュニティコストも含まれる。
【００２３】
Ｃ［Ｔ］は総コストを表わし、Ｃ［ＢＷ］は帯域幅コストを表し、Ｃ［ＳＴＯ］はベース位置の所での格納コストを表し、Ｃ［ＲＥＰ］は単一のサーバにおけるレプリカ作成コストを表し、Ｃ［ＯＣ］はオパチュニティコストを表し、Ｃ［ＵＰ］は複製されたコピーが陳腐化するのみ防ぐための更新と関連する更新コストを表すものとすると、
Ｃ［Ｔ］＝Ｃ［ＢＷ］＋Ｃ［ＳＴＯ］＋Ｃ［ＲＥＰ］
＋Ｃ［ＯＣ］＋Ｃ［ＵＰ］
となる。
【００２４】
帯域幅コストＣ［ＢＷ］は、個々のリンク上に存在する単位時間当たりのリクエストの数の関数であり、単位時間当たりのリクエストの数に基づいて定められる比例定数と各リンク上に存在する単位時間当たりのリクエストの数の総数とを乗じた値とされる。帯域幅コストＣ［ＢＷ］の計算は、図５に示される一例としての網との関連で以下のように説明することができる。
【００２５】
図５は、８つのユーザローカルアクセスポイント１、２、３、４、５、６、７、８を、ユーザがサーバ４０上にソール（元）コピーの元キャッシュ“Ｐ”として格納されているデータセットにアクセスすることができるように接続する８つのルータａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈを持つ第二の網を示す。サーバ４０は、ルータ“ａ”によって、網内の他のルータｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈに接続される。ルータ“ａ”は、現在、サーバ４０上の元キャッシュ“Ｐ”内にデータセットの一部として格納されている１０ギガバイトファイルに向けられたリクエストを時間当たり１０００扱っている。本発明によると、逆ツリー生成法を用いて、網内のキャッシュが使用パターンの変化に応答して自動的に再編成される。このために、ルータ“ａ”は、定期的に、他のルータｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈに向けて、各網リンクがある期間、例えば、一時間当たりに扱うリクエストの数を監視（測定）することを要請する監視リクエストを一斉に送る。図５の第二の網に対する現存のルータテーブル３３４が図７Ａに示される。
【００２６】
この監視期間において、各ユーザローカルアクセスポイントは、サーバ４０上の元キャッシュ“Ｐ”内にデータセットの一部として格納されているこの１０ギガバイトファイルに向けられた量“Ｔ”に相当するリクエストを行なうが、この量“Ｔ”は、単位時間当たりのリクエストメッセージのトラヒック数を表す。具体的には、ユーザローカルアクセスポイント１は、サービスルータ“ｃ”によって、単位時間当たりに、Ｔ＝１２５に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと監視（測定）される。ユーザローカルアクセスポイント２は、サービスルータ“ｃ”によって、単位時間当たりに、Ｔ＝５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント３は、サービスルータ“ｄ”によって、単位時間当たりに、Ｔ＝２５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント４は、サービスルータ“ｅ”によって、単位時間当たりに、Ｔ＝２２５に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント５は、サービスルータ“ｆ”によって、単位時間当たりに、Ｔ＝５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント６は、サービスルータ“ｇ”によって、単位時間当たりに、Ｔ＝５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント７は、サービスルータ“ａ”によって、単位時間当たりに、Ｔ＝５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。ユーザローカルアクセスポイント８は、サービスルータ“ｂ”によって、単位時間当たりに、Ｔ＝２００に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つものと測定される。
【００２７】
各監視期間において、各網リンクは、サーバ４０上の元キャッシュ“Ｐ”内にデータセットの一部として内に格納されている１０メガビットファイルに向けられた量“Ｔ”に相当するリクエストをパスすることを監視（観測）される。図５のルータを相互接続する１１個の網リンクの状況は以下の通りである。ルータ“ａ”とルータ“ｂ”を接続する網リンク“ａ−ｂ”は、単位時間当たりに、Ｔ＝８５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｂ”とルータ“ｃ”を接続する網リンク“ｂ−ｃ”は、単位時間当たりに、Ｔ＝１７５に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｃ”とルータ“ｄ”を接続する網リンク“ｃ−ｄ”は、単位時間当たりに、Ｔ＝０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｄ”とルータ“ｅ”を接続する網リンク“ｄ−ｅ”は、単位時間当たりに、Ｔ＝０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｅ”とルータ“ｆ”を接続する網リンク“ｅ−ｆ”は、単位時間当たりに、Ｔ＝０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｆ”とルータ“ｇ”を接続する網リンク“ｆ−ｇ”は、単位時間当たりに、Ｔ＝５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｇ”とルータ“ａ”を接続する網リンク“ｇ−ａ”は、単位時間当たりに、Ｔ＝１００に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｄ”とルータ“ｈ”を接続する網リンク“ｄ−ｈ”は、単位時間当たりに、Ｔ＝２５０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｅ”とルータ“ｈ”を接続する網リンク“ｅ−ｈ”は、単位時間当たりに、Ｔ＝２２５に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｆ”とルータ“ｈ”を接続する網リンク“ｆ−ｈ”は、単位時間当たりに、Ｔ＝０に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。ルータ“ｈ”とルータ“ｂ”を接続する網リンク“ｈ−ｂ”は、単位時間当たりに、Ｔ＝４７５に相当するサーバ４０に向けられたリクエストメッセージのトラヒック数を持つ。
【００２８】
図５の網に対する帯域幅コストＣ［ＢＷ］が、図４のステップ４０２において、単位時間当たりのリクエスト数に基づいて定められた比例定数と、各リンク上の単位時間当たりのリクエストの総数との積として計算される。この例のような単位時間当たりのリクエスト数に対しては、メガビット当たりのコストは、０．１であるものと想定される。図５の１１個の網リンクに対する“Ｔ”の値の総和は、２１２５である。このために、ステップ４０２において、図５の網に対しては、帯域幅コストＣ［ＢＷ］は、２１２５として計算される（これは、２１２５リクエストと、リクエスト当たり１０メガビットと、メガビット当たりのコスト０．１を掛けた値である）。
【００２９】
次に、図４のステップ４０２において、Ｃ［ＳＴＯ］、すなわち、ベース位置における格納コストが計算される。この例では、この値は、５００とされる。次に、図４のステップ４０２において、Ｃ［ＲＥＰ］、すなわち、単一のサーバにおけるレプリカ作成コストが計算される。まだレプクカは作成されてないために、この値は、０である。次に、図４のステップ４０２において、Ｃ［ＯＣ］、すなわち、オパチュニティコストが計算される。市場調査から、失われたヒット当たりのオパチュニティコストは５であることが知られている。また、実験的な観測によると、時間当たりに失われるヒットの数は１００であることが知られている。こうして、Ｃ［ＯＣ］、すなわち、オパチュニティコストの値は、この例では、５００となる。次に、図４のステップ４０２において、Ｃ［ＰＵ］、すなわち、複製されたコピーをこれらが陳腐化しないように更新することと関連する更新コストが計算される。ここではまだレプリカの作成は行なわれてないために、この値は０である。こうして、図４のステップ４０２において、Ｃ［Ｔ］＝Ｃ［ＢＷ］＋Ｃ［ＳＴＯ］＋Ｃ［ＲＥＰ］＋Ｃ［ＯＣ］＋Ｃ［ＵＰ］が、２１２５＋５００＋０＋５００＋０＝３１２５の値を持つものとして計算される。
【００３０】
次に、図４のステップ４０４において、一つあるいは複数の宛先キャッシュの所に終端するリンクが、最も高いコストを持つリンクから最も低いコストを持つリンクの順番に分類される。図５の一例としての網では、こうして分類されるリンクの順番は、以下の通りである：
網リンク“ａ−ｂ”  Ｔ＝８５０
網リンク“ｇ−ａ”  Ｔ＝１００
【００３１】
次に、図４のステップ４０６において、ループが開始される。つまり、現存のキャッシュに終端する各リンク“Ｉ”に対してステップ４０８および４１０が遂行される。具体的には、ステップ４０８の入れ子ループにおいて発見されたリンク“Ｉ”に寄与する各ソース“Ｓ”に対して、ステップ４１０において、ソースの深さ（そのリンクに至る経路に沿ってのセグメント数）および重み（例えば、帯域幅寄与）が見つけられる。図５の網の場合は、ステップ４０６は、最も高いコストを持つリンク、すなわち、Ｔ＝８５０を持つ網リンク“ａ−ｂ”から開始される。
【００３２】
網リンク“ａ−ｂ”へのトラヒックのソースは、ルータｃ、ｄ、ｅ、ｈ、およびユーザローカルアクセスポイント８である。ステップ４０８において、入れ子ループが開始され、網リンク“ａ−ｂ”に寄与する各ソースに対して、ステップ４１０が遂行される。具体的には、ルータ“ｅ”の寄与については、ステップ４１０は、深さ（このリンクに至る経路に沿ってのセグメントの数）は、セグメントｅ−ｈ、セグメントｈ−ｂ、およびセグメントｂ−ａの３つであることを見つける。このため、ステップ４１０は、ルータ“ｅ”からの寄与は、ルータ“ｅ”からの単位時間当たりのリクエストの数Ｔ＝２２５に、深さ値３を乗じ、６７５であると計算する。もし、ルータ“ｅ”の網リンク“ａ−ｂ”への寄与を削除した場合は、６７５のコストが回避されることとなる。例えば、図５においては、サーバ４７が、ルータ“ｅ”に接続されているが、もし、サーバ４７を元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとした場合は、６７５のコストが回避できることとなる。ただし、このコストの回避は、サーバ４７内にデータセットを複製するのに要するコストと差し引き計算する必要がある。この差し引き計算は、後に説明されるように、ステップ４１４および４１６において遂行される。
【００３３】
ルータ“ｄ”の寄与については、ステップ４１０は、深さ（リンクａ−ｂに至る経路に沿ってのセグメント数）は、セグメントｄ−ｈ、セグメントｈ−ｂ、およびセグメントｂ−ａの３つであることを見つける。このため、ステップ４１０は、ルータ“ｄ”からの寄与は、ルータ“ｄ”からの単位時間当たりのリクエストの数Ｔ＝２５０に、深さ値３を乗じ、７５０であると計算する。もし、ルータ“ｄ”の網リンク“ａ−ｂ”への寄与が削除された場合は、７５０のコストが回避されることとなる。例えば、図５においては、サーバ４９が、ルータ“ｄ”に接続されているが、もし、サーバ４９を元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとした場合は、７５０のコストが回避できることとなる。ただし、このコストの回避は、サーバ４９内にデータセットを複製するのに要するコストと差し引き計算する必要がある。この差し引き計算は、後に説明されるように、ステップ４１４および４１６において遂行される。
【００３４】
ルータ“ｃ”の寄与については、ステップ４１０は、深さ（リンクａ−ｂに至る経路に沿ってのセグメント数）は、セグメントｃ−ｂ、およびセグメントｂ−ａの２つであることを見つける。このため、ステップ４１０は、ルータ“ｃ”からの寄与は、ルータ“ｃ”からの単位時間当たりのリクエストの数Ｔ＝１７５に、深さ値２を乗じ、３５０であると計算する。もし、ルータ“ｃ”の網リンク“ａ−ｂ”への寄与が削除された場合は、３５０のコストが回避されることとなる。例えば、図５においては、サーバ４８が、ルータ“ｃ”に接続されているが、もし、サーバ４８を元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとした場合は、３５０のコストが回避できることとなる。ただし、このコストの回避は、サーバ４８内にデータセットを複製するのに要するコストと差し引き計算する必要がある。この差し引き計算は、後に説明されるように、ステップ４１４および４１６において遂行される。
【００３５】
ルータ“ｈ”の寄与については、ステップ４１０は、深さ（リンクａ−ｂに至る経路に沿ってのセグメント数）は、セグメントｈ−ｂ、およびセグメントｂ−ａの２つであることを見つける。このため、ステップ４１０は、ルータ“ｈ”からの寄与は、ルータ“ｈ”からの単位時間当たりのリクエストの数Ｔ＝４７５に、深さ値２を乗じ、９５０であると計算する。もし、ルータ“ｈ”の網リンク“ａ−ｂ”への寄与が削除された場合は、９５０のコストが回避されることとなる。例えば、図５においては、サーバ４４が、ルータ“ｈ”に接続されているが、もし、サーバ４４を元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとした場合は、９５０コストが回避できることとなる。ただし、このコストの回避は、サーバ４４内にデータセットを複製するのに要するコストと差し引き計算する必要がある。この差し引き計算は、後に説明されるように、ステップ４１４および４１６において遂行される。
【００３６】
ユーザローカルアクセスポイント“８”の寄与については、ステップ４１０は、深さ（リンクａ−ｂに至る経路に沿ってのセグメント数）は、セグメントｂ−ａの１つであることを見つける。このため、ステップ４１０は、ユーザローカルアクセスポイント“８”からの寄与は、ユーザローカルアクセスポイントからの単位時間当たりのリクエストの数Ｔ＝２００に、深さ値１を乗じ、２００であると計算する。もし、ユーザローカルアクセスポイント“８”の網リンク“ａ−ｂ”への寄与が削除された場合は、２００のコストが回避されることとなる。例えば、図５においては、サーバ４６が、ルータ“ｂ”に接続されているが、もし、サーバ４６を元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとした場合は、８５０のコストが回避できることとなる。ただし、このコストの回避は、サーバ４６内にデータセットを複製するのに要するコストと差し引き計算する必要がある。この差し引き計算は、後に説明されるように、ステップ４１４および４１６において遂行される。
【００３７】
図５の網に対しては、ステップ４０５において開始されたループは、次に高いコストを持つリンク、すなわち、Ｔ＝１００を持つ網リンク“ｇ−ａ”に対して継続される。
【００３８】
次に、図４のステップ４１２において、ステップ４０６、４０８、４１０から決定された深さおよび重みに基づいて候補サーバノードについて評価される。図５の例の場合は、元キャッシュ“Ｐ”内のデータセットのレプリカキャッシュを格納することが可能な６つの候補サーバが存在する。サーバ４２は、ルータ“ｆ”によって網に接続される。サーバ４４は、ルータ“ｈ”によって網に接続される。サーバ４６は、ルータ“ｂ”によって網に接続される。サーバ４７は、ルータ“ｅ”によって網に接続される。サーバ４８は、ルータ“ｃ”によって網に接続される。サーバ４９は、ルータ“ｄ”によって網に接続される。
【００３９】
ステップ４１２は、上のステップ４０６、４０８、４１０によって遂行されたループの結果を用いる。サーバ４４が、元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとされた場合は、９５０のコストが回避されることとなる。サーバ４６が、元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとされた場合は、８５０のコストが回避されることとなる。サーバ４７が、元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとされた場合は、６７５のコストが回避されることとなる。サーバ４８が、元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとされた場合は、３５０のコストが回避されることとなる。サーバ４９が、元キャッシュ“Ｐ”内のデータセットに対するレプリカサーバとされた場合は、７５０のコストが回避されることとなる。これら結果を評価することで、ステップ４１２は、レプリカキャッシュに対する最良な候補は、ルータ“ｈ”に接続されたサーバ４４であることを決定する。
【００４０】
次に、図４のステップ４１４において、トライアルとしての新たな網トラヒックパターンが生成される。これは、以前は候補レプリカキャッシュサーバ付近のルータから元キャッシュサーバに向かうように転送されていた元キャッシュトラヒックを、候補サーバに転送するように指定することによって行なわれる。こうして、ステップ４１４において、トライアルとしての新たな網トラヒックパターンの総コストＣ［Ｔ］が計算される。
【００４１】
図６は、図５の網を、トライアルとしての新たな網トライアルパターンがサーバ４４上の候補レプリカキャッシュ“Ａ”と、サーバ４０上の元キャッシュ“Ｐ”に転送されるように変更することによって得られる網の状態を示す。ステップ４１４において、以前は候補レプリカキャッシュサーバ４４付近のルータｄ、ｅ、ｆから元キャッシュサーバ４０に向かうように転送されていたキャッシュトラヒックが、候補サーバ４４に向かうように指定される。次に、ステップ４１４において、図６の網のこのトライアルとしての新たな網トライアルパターンの総コストＣ［Ｔ］が計算される。
【００４２】
図６の網のトライアルとしての新たな網トラヒックパターンを扱うルータを相互接続する１１個の網リンクは、以下のようなトラヒックを持つ。つまり、ルータ“ａ”と“ｂ”を接続する網リンク“ａ−ｂ”は、サーバ４０に向かうＴ＝３７５に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｂ”と“ｃ”を接続する網リンク“ｂ−ｃ”は、サーバ４０に向かうＴ＝１７５に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｃ”と“ｄ”を接続する網リンク“ｃ−ｄ”は、Ｔ＝０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｄ”と“ｅ”を接続する網リンク“ｄ−ｅ”は、Ｔ＝０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｅ”と“ｆ”を接続する網リンク“ｅ−ｆ”は、Ｔ＝０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｆ”と“ｇ”を接続する網リンク“ｆ−ｇ”は、Ｔ＝０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｄ”と“ｈ”を接続する網リンク“ｄ−ｈ”は、レプリカキャッシュサーバ４４に向かうＴ＝２５０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｅ”と“ｈ”を接続する網リンク“ｅ−ｈ”は、レプリカキャッシュサーバ４４に向かうＴ＝２２５に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｆ”と“ｈ”を接続する網リンク“ｆ−ｈ”は、レプリカキャッシュサーバ４４に向かうＴ＝５０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持ち、ルータ“ｆ”と“ｂ”を接続する網リンク“ｈ−ｂ”は、Ｔ＝０に相当する単位時間当たりのリクエストメッセージのトラヒック数を持つ。
【００４３】
図４のステップ４１４において、図６の網に対する帯域幅コストＣ［ＢＷ］が、単位時間当たりのリクエスト数に基づいて定められた比例定数と、各リンク上の単位時間当たりのリクエストの総数の積として計算される。この例の単位時間当たりのリクエスト数に対しては、メガビット当たりのコストは、０．１であるものと想定される。図６の１１個の網リンクに対する“Ｔ”の値の総和は、１１２５であり、こうして、ステップ４１４において、図６の網に対する帯域幅コストＣ［ＢＷ］は、１１２５であるものと計算される。
【００４４】
次に、図４のステップ４１４において、Ｃ［ＳＴＯ］、すなわち、ベース位置における格納コストが計算される。この例では、この値は、５００とされる。次に、図４のステップ４１４において、Ｃ［ＲＥＰ］、すなわち、単一のレプリカキャッシュサーバ４４におけるレプリカ作成コストが計算される。この例では、メガビット当たりのレプリカ作成コスト（一日当たり）は、５０であると想定される。１０メガビットファイルに対しては、これは、５００に相当するレプリカ作成コストＣ［ＲＥＰ］となる。次に、図４のステップ４１４において、Ｃ［ＯＣ］、すなわち、オパチュニティコストが計算される。レプリカキャッシュ“Ａ”を追加することにより、データベースへのアクセスに対する全てのユーザリクエストが満たされることが期待されるために、オパチュニティコストに対するＣ［ＯＣ］の値は、この例では、０となる。次に、図４のステップ４１４において、Ｃ［ＵＰ］、すなわち、複製されたコピーを、これらを陳腐化させないために更新することと関連する更新コストが計算される。この例では、更新コストは、１００であると想定される。こうして、図４のステップ４１４は、Ｃ［Ｔ］＝Ｃ［ＢＷ］＋Ｃ［ＳＴＯ］＋Ｃ［ＲＥＰ］＋Ｃ［ＯＣ］＋Ｃ［ＵＰ］を、１１２５＋５００＋５００＋０＋１００＝２２２５の値を持つものとして計算する。
【００４５】
次に、図４のステップ４１６において、このトライアルとしての新たな網トラヒックパターンが、キャッシュの現存の分配より低い総コストＣ［Ｔ］を与えるか否か決定される。図６の網に対しては、ステップ４１６は、トライアルとしての新たなトラヒックパターンの総コストＣ［Ｔ］は、図５のキャッシュの現存の分配では３１２５であるのに対して、２２２５であり、より低い総コストを与えるものと決定する。こうして、ステップ４１６において、図６のトライアルとしての新たな網トラヒックパターンを実際に用い、網のルータに対する新たなルータ割当ての基礎となるべきことを決定する。
【００４６】
次に、図４のステップ４１８において、この新たな割当てが、本発明によるグループカースティングの原理に基づいて、全てのルータに一斉に送信される。図６の一例としての網においては、ルータ“ａ”が、図７Ｂに示すような新たなルータテーブル３３６を、ルータｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈに一斉に送信する。つまり、本発明の原理によると、宛先キャッシュの識別を選択的に提供する単一のルータテーブル３３６が、多数の網ルータに、ルーティング機能を遂行しているルータの識別に基づいて一斉に送られる。この割当てメッセージ２１０が、図８Ａに示される。この割当てメッセージ２１０は、宛先ルータを指定するフィールド２１２、ソースルータを指定するフィールド２１４、およびコスト／ベニフィット分析アルゴリズム４１５によって計算された新たなルーティング割当てを指定するフィールド２１２を含む。次に、図８Ｂに示すようなレプリカ作成メッセージ８０２が、ルータ“ａ”から、例えば、ルータ“ｈ”に向けて、新たなサーバ４４にデータセットのコピーをレプリカキャッシュ“Ａ”として提供するために送られる。この割当てメッセージ２１０のフィールド２１２は、宛先ルータとしてルータ“ｈ”を指定し、フィールド２１４は、ソースルータとしてルータ“ａ”を指定する。
【００４７】
図４のステップ４１８は、次に、ステップ４０２にループバックする。ただし、ステップ４０２へのループバックは、ステップ４２０において、ルータ３０によって、新たなトラヒック監視データが受信されるまで遅延することも可能である。次に、図７Ａの元の現存のルータテーブル３３４が破棄され、図７Ｂの新たなルータテーブル３３６が新たな現存のルータテーブルとなる。このようにして、図４の最適レプリカキャッシュ割当てプログラム３３０は、網内のトラヒックの分配を定期的に再評価することで、網をトラヒックパターンの変化に適応させる。
【００４８】
割当てプログラム３３０は、もはや不要となったレプリカキャッシュを網から削除する動作も行なう。例えば、トラヒックパターンが、図６に示されるパターンから変化したものと想定する。例えば、ユーザローカルアクセスポイント４からサーバ４４のレプリカキャッシュ“Ａ”に向かう単位時間当たりのリクエストメッセージのトラヒック数がＴ＝２５に変化し、ユーザローカルポイント３からサーバ４４のレプリカキャッシュ“Ａ”に向かう単位時間当たりのリクエストメッセージのトラヒック数がＴ＝５０に変化したものと想定する。ステップ４１２において、サーバ４４からレプリカキャッシュ“Ａ”を削除することに対するトレードフオが計算されるが、ステップ４１２は、レプリカキャッシュ“Ａ”が削除された場合のリンクｈ−ｂとリンクｂ−ａ上のトラヒックの増加は、Ｔ＝１５０であることを決定する。ステップ４１２は、また、レプリカキャッシュ“Ａ”の削除により、５００のレプリカ作成コストが節約されることを決定する。このために、ステップ４１２は、レプリカキャッシュが削除された場合は、正味で３５０の得となることを認識する。この場合、ステップ４１６において、レプリカキャッシュ“Ａ”を破棄することが決定され、次に、ステップ４１８において、この新たな割当てが網内の全てのルータに一斉に送信される。
【００４９】
本発明によると、逆ツリー生成法を用いて、網内のキャッシュが、使用パターンの変化に対応して動的に再編成される。これは、インターネットトラヒックが時間および地域の両方において動的に変化することう問題を解決する。一日の内のある時間帯はアクティブであるが（トラヒック数が多いが）、他の時間帯は全くインアクティブである（トラヒック数が少ない）地域が存在する。本発明はこの問題を、リプリカキャッシュ作成の決定を使用パターンの変化に基づいて動的に行なうことによって解決する。本発明は、レプリカキャッシュを追加する“発芽（grow）”決定と、これらを削除する“刈り込み（prune ）”決定を絶えず更新する。このため、動的に変化するコア位置にレプリカキャッシュサーバを持つ動的なツリーが得られる。つまり、結果的に、最小の重みを持つスパニングツリーが“オン・ザ・フライ”にて高速に構築される。レプリカキャッシュサーバの所に陳腐化したデータが蓄積するのを回避するために、各サーバは、サーバキャッシュ同期プロトコルなどのプロトコルを用いて絶えず（必要に応じて）更新される。
【００５０】
本発明の実施における一つの特徴は、ユーザが、ユーザに最も近い所に位置するレプリカキャッシュサーバにアクセスすることである。一つの実施例においては、ユーザは、最初に、ユーザの宛先ポイントに接続され、そのアプリケーションに対するツリー構造を見つけた後に、スパニングツリー内の最も適当なノードに向けて接続を設定する。一つの代替の実施例においては、各アプリケーションは、マルチカーストグループとして扱われ、そのグループに加わることを求めるユーザは、対応するグループカースト能力を持つルータにルートされる。グループカースト（ＧＣ）は、概念的には、マルチカーストと類似するが、ただし、反対の方向に機能する。グループカースト（ＧＣ）ルータは、更新されたルーティングテーブルを維持し、常時は、普通のルータとして機能し、新たな最小の重みのスパニングツリーの構築が開始されるとルーティングテーブル内の項目を更新する。
【００５１】
本発明は、レプリカキャッシュの分配を使用パターンの変化に基づいて動的に変更するための方法を提供する。本発明は、これを、逆ツリー生成法を用いて達成する。本発明は、レプリカキャッシュの分配を動的に最適化するに当たってアクセスの失敗のために失われた顧客のオパチュニティコストも用いる。
【００５２】
網ルータによって遂行される監視プロセスの追加の機能として、これらデータセット下部のアプリケーションに向けられたサーバヒット情報の収集を含むことも可能である。これは、キャッシュ内に格納されたデータセットの所有者による市場調査のために有益である。本発明の他の用途として、サーバの地域差を収容する地域的なアプリケーションも考えられる。例えば、新聞、公告、販売促進等の地域版をローカルサーバに掲載することも可能である。
【００５３】
本発明の様々な実施例が詳細に説明された。ただし、加えて、これら実施例に対する多くの修正および変更が、本発明の範囲および精神から逸脱することなく可能である。
【図面の簡単な説明】
【図１Ａ】自身を、３つのサービス領域が得られるように、一つの元キャッシュと、２つのレプリカキャッシュを持つように編成する一例としての網の一連の状態を示す図その１である。
【図１Ｂ】自身を、３つのサービス領域が得られるように、一つの元キャッシュと、２つのレプリカキャッシュを持つように編成する一例としての網の一連の状態を示す図その２である。
【図１Ｃ】自身を、３つのサービス領域が得られるように、一つの元キャッシュと、２つのレプリカキャッシュを持つように編成する一例としての網の一連の状態を示す図その３である。
【図１Ｄ】自身を、３つのサービス領域が得られるように、一つの元キャッシュと、２つのレプリカキャッシュを持つように編成する一例としての網の一連の状態を示す図その４である。
【図１Ｅ】自身を、３つのサービス領域が得られるように、一つの元キャッシュと、２つのレプリカキャッシュを持つように編成する一例としての網の一連の状態を示す図その５である。
【図１Ｆ】図Ｅの網を、自身を元キャッシュと、修正されたサービス領域を持つ修正されたレプリカキャッシュを持つように定期的に再編成した結果として得られる網の状態を示す図である。
【図２Ａ】図１Ａ〜１Ｅの一例としての網に対するルータ制御のためのメッセージフォーマットを示す図その１である。
【図２Ｂ】図１Ａ〜１Ｅの一例としての網に対するルータ制御のためのメッセージフォーマットを示す図その２である。
【図２Ｃ】図１Ａ〜１Ｅの一例としての網に対するルータ制御のためのメッセージフォーマットを示す図その３である。
【図２Ｄ】割当てメッセージを示す図である。
【図２Ｅ】図１Ｅの一例としての網に対するレプリカ作成メッセージを示す図である。
【図２Ｆ】一例としての割当てメッセージを示す図である。
【図２Ｇ】一例としてのレプリカ作成メッセージを示す図である。
【図３】図１Ａのルータのアーキテクチャを略図にて示す図である。
【図４】最適レプリカキャッシュ割当てプログラムを流れ図にて示す図である。
【図５】第二の例としての網の第一のステージの編成を示す図である。
【図６】図５の第二の例としての網の第二のステージの編成を示す図である。
【図７Ａ】図５の網編成に対するルータテーブルを示す図である。
【図７Ｂ】図６の網編成に対するルータテーブルを示す図である。
【図８Ａ】図６の第二の例としての網の第二のステージの編成に対する割当てメッセージを示す図である。
【図８Ｂ】図６の第二の例としての網の第二のステージの編成に対するレプリカ作成メッセージを示す図である。
【図１Ａ】
0004344024.tif 000002
【図１Ｂ】
0004344024.tif 000003
【図１Ｃ】
0004344024.tif 000004
【図１Ｄ】
0004344024.tif 000005
【図１Ｅ】
0004344024.tif 000006
【図１Ｆ】
0004344024.tif 000007
【図２Ａ】
0004344024.tif 000008
【図２Ｂ】
0004344024.tif 000009
【図２Ｃ】
0004344024.tif 000010
【図２Ｄ】
0004344024.tif 000011
【図２Ｅ】
0004344024.tif 000012
【図２Ｆ】
0004344024.tif 000013
【図２Ｇ】
0004344024.tif 000014
【図３】
0004344024.tif 000015
【図４】
0004344024.tif 000016
【図５】
0004344024.tif 000017
【図６】
0004344024.tif 000018
【図７Ａ】
0004344024.tif 000019
【図７Ｂ】
0004344024.tif 000020
【図８Ａ】
0004344024.tif 000021
【図８Ｂ】
0004344024.tif 000022