(57)【要約】【課題】コンピュータ・ネットワークにおいてリソースを複製すること。【解決手段】ネットワークにおける起点サーバのクライアントによってなされたリソース・リクエストは、リフレクタ機構によってインターセプトされ、リピータと称される他のサーバに反射される。リフレクタは、１組の可能性のあるリピータの中から最良のリピータを選択して、クライアントをその選択された最良のリピータに再方向付けする。次に、クライアントは、その選択された最良のリピータをリクエストする。リソースは、可能であれば書き換えられ、その中に含まれるリソース識別子の少なくともいくつかを、起点サーバの代わりにリピータを指定する修正されたリソース識別子と交換する。【選択図】図１
2008090826.tif 000002
【特許請求の範囲】
【請求項１】
複数のリピータ・サーバから構成されたリピータ・サーバ・ネットワークを含むコンピュータ・ネットワーク・システムの中のサーバがリクエストを処理する方法であって、前記リピータ・サーバ・ネットワークのサブスクライバは１又は複数の起点サーバを介して情報を公開し、前記複数のリピータ・サーバの中の少なくとも一部は前記起点サーバにおいて入手可能な情報の一部又は全部を複製する、方法において、
情報に対するリクエストを取得するステップと、
取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報に対するリクエストであるかどうかを判断するステップと、
取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報に対するリクエストであると判断される場合には、前記情報を提供することを試みるステップと、
取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報以外の情報に対するリクエストであると判断される場合には、前記リクエストを拒絶するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記判断は、前記リピータ・サーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づいていることを特徴とする方法。
【請求項３】
請求項１記載の方法において、前記判断は、前記リクエストをするのに用いられたＵＲＬに含まれる起点サーバの名称に少なくとも部分的に基づいていることを特徴とする方法。
【請求項４】
請求項２又は請求項３のいずれかの請求項に記載の方法において、
ＨＴＴＰホスト・ヘッダの中の情報を用いて、前記リピータ・サーバのアドレスを指定するのに用いられた名称を判断するステップを含むことを特徴とする方法。
【請求項５】
請求項１記載の方法において、
前記リクエストがサブスクライバから提供される情報に対するリクエストであるときには、
リクエストされた情報がリピータ・サーバにおいてローカルにキャッシュされているかどうかを判断し、前記判断に少なくとも部分的には基づいて、前記リクエストされた情報がローカルにキャッシュされている場合には、前記リクエストされた情報をリトリーブするステップと、
前記リクエストされた情報がローカルにキャッシュされていないと判断されるときには、前記サブスクライバの起点サーバから又はピア・キャッシュから前記リクエストされた情報を取得するステップと、
を更に含むことを特徴とする方法。
【請求項６】
請求項５記載の方法において、
前記リクエストされた情報を取得したら、前記情報をローカルにキャッシュするステップを更に含むことを特徴とする方法。
【請求項７】
請求項６記載の方法において、
前記リクエストされた情報を含む返答を構築するステップと、
リクエストしている側のクライアントに前記返答を送信するステップと、
を更に含むことを特徴とする方法。
【請求項８】
請求項７記載の方法において、
トランザクションに関する詳細を記録するステップを更に含むことを特徴とする方法。
【請求項９】
請求項８記載の方法において、前記詳細は、
（ａ）現在の時間、（ｂ）リクエストしている側のアドレス、（ｃ）リクエストされたユニフォーム・リソース・ロケータ（ＵＲＬ）、（ｄ）生成された応答のタイプ、（ｅ）前記リクエストはリピータ・サーバによって前記キャッシュから与えられたのかどうか、（ｆ）前記リクエストは、キャッシュを満たした後で、リピータ・サーバによって与えられたのかどうか、（ｇ）無効がペンディングであるリクエストが、リピータ・サーバによって与えられたかどうか、（ｈ）前記リソースを与えるように要求された時間を示す継続時間、そして、（ｉ）前記リソースを与えるのに用いられる帯域幅、の中の１又は複数を含むことを特徴とする方法。
【請求項１０】
複数のリピータ・サーバから構成されたリピータ・サーバ・ネットワークを含むコンピュータ・ネットワーク・システムの中のサーバがリクエストを処理する方法であって、前記リピータ・サーバ・ネットワークのサブスクライバは１又は複数の起点サーバを介して情報を公開し、前記複数のリピータ・サーバの中の少なくとも一部は前記起点サーバにおいて入手可能な情報の一部又は全部を複製する、方法において、あるリピータ・サーバが、
（Ａ）情報に対するリクエストをクライアントから取得するステップと、
（Ｂ）取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報に対するリクエストであるかどうかを、（ａ）前記リピータ・サーバのアドレスを指定するのに用いられた名称と、（ｂ）取得されたリクエストを行うのに用いられたＵＲＬに含まれる起点サーバの名称との少なくとも一方に少なくとも部分的には基づいて判断するステップと、
（Ｃ）取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報に対するリクエストであると判断されるときには、
（Ｃ１）リクエストされた情報がローカルにキャッシュされていると判断される場合には、前記リクエストされた情報をリトリーブするステップと、
（Ｃ２）リクエストされた情報がローカルにキャッシュされていないと判断される場合には、
（Ｃ２１）前記リクエストされた情報を、起点サーバから又はピア・キャッシュから取得するステップと、
（Ｃ２２）前記リクエストされた情報を、ローカルにキャッシュするステップと、
（Ｃ３）前記リクエストされた情報を含む応答を構築するステップと、
（Ｃ４）前記応答を、前記リクエストをしているクライアントに送信するステップと、
（Ｄ）取得されたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報以外の情報に対するリクエストであると判断されるときには、前記リクエストを拒絶するステップと、
（Ｅ）トランザクションに関する詳細を記録するステップと、
を含むことを特徴とする方法。
【請求項１１】
複数のリピータ・サーバから構成されたリピータ・サーバ・ネットワークを含むコンピュータ・ネットワーク・システムの中のサーバがリクエストを処理する方法であって、前記リピータ・サーバ・ネットワークのサブスクライバは１又は複数の起点サーバを介してリソースを公開する、方法において、
前記リピータ・サーバ・ネットワークを構成する前記複数のリピータ・サーバの中の少なくとも一部が、前記起点サーバの一部において入手可能な情報の一部又は全部を複製するステップと、
情報に対するリクエストを受け取ると、受け取られたリクエストが前記リピータ・サーバ・ネットワークの既知のサブスクライバから提供される情報に対するリクエストであるかどうかを判断するステップと、
受け取られたリクエストが前記リピータ・サーバ・ネットワークの既知のサブスクライバから提供される情報に対するリクエストであると判断されるときには、前記情報を与えるステップと、
受け取られたリクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報以外の情報に対するリクエストであるときには、前記リクエストを拒絶するステップと、
を含むことを特徴とする方法。
【請求項１２】
請求項１１記載の方法において、前記判断は、前記リピータ・サーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づいていることを特徴とする方法。
【請求項１３】
請求項１１記載の方法において、前記判断は、前記リクエストをするのに用いられたＵＲＬに含まれる起点サーバの名称に少なくとも部分的に基づいていることを特徴とする方法。
【請求項１４】
請求項１２又は請求項１３のいずれかの請求項に記載の方法において、
前記リピータ・サーバは、ＨＴＴＰホスト・ヘッダの中の情報を用いて、前記リピータ・サーバのアドレスを指定するのに用いられた名称を判断することを特徴とする方法。
【請求項１５】
請求項１１記載の方法において、
前記リクエストがサブスクライバから提供される情報に対するリクエストである場合には、
リクエストされた情報がローカルにキャッシュされている場合には、リクエストされたリソースを前記キャッシュからリトリーブし、それ以外の場合には、リクエストされた情報を起点サーバから又はピア・キャッシュから取得するステップを更に含むことを特徴とする方法。
【請求項１６】
請求項１５記載の方法において、
前記リクエストされた情報を取得する際には、前記情報をローカルにキャッシュするステップを更に含むことを特徴とする方法。
【請求項１７】
請求項１５記載の方法において、
前記リクエストされた情報を含む返答を構築するステップと、
リクエストしている側のクライアントに前記返答を送信するステップと、
を更に含むことを特徴とする方法。
【請求項１８】
請求項１７記載の方法において、
トランザクションに関する詳細を記録するステップを更に含むことを特徴とする方法。
【請求項１９】
請求項１８記載の方法において、前記詳細は、
（ａ）現在の時間、（ｂ）リクエストしている側のアドレス、（ｃ）リクエストされたユニフォーム・リソース・ロケータ（ＵＲＬ）、（ｄ）生成された応答のタイプ、（ｅ）前記リクエストは、リピータ・サーバによって前記キャッシュから与えられたかのかどうか、（ｆ）前記リクエストは、キャッシュを満たした後で、リピータ・サーバによって与えられたのかどうか、（ｇ）無効がペンディングであるリクエストがリピータ・サーバによって与えられたのかどうか、（ｈ）前記リソースを与えるのに要求された時間を示す継続時間、そして、（ｉ）前記リソースを与えるのに用いられる帯域幅、の中の１又は複数を含むことを特徴とする方法。
【請求項２０】
請求項１、請求項１０又は請求項１１の中の任意の請求項に記載の方法において、サブスクライバは、少なくとも１つの起点サーバを介してリソースを公開することを特徴とする方法。
【請求項２１】
システムであって、
複数のリピータ・サーバから構成されたリピータ・サーバ・ネットワークであって、このリピータ・サーバ・ネットワークの複数のサブスクライバをサポートし、前記サブスクライバは１又は複数の起点サーバを介して前記リピータ・サーバ・ネットワークにリソースを公開する、リピータ・サーバ・ネットワークを備えており、
前記リピータ・サーバの少なくとも一部は、前記起点サーバの少なくとも一部において入手可能な情報の一部又は全部を複製し、
コンテンツに対するクライアントのリクエストは、前記コンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理され、
リソースに対する前記リピータ・サーバ・ネットワークへのリクエストは、前記リピータ・サーバ・ネットワークのサブスクライバから提供されるリソースに対するリクエストでない場合には、拒絶されることを特徴とするシステム。
【請求項２２】
請求項２１記載のシステムにおいて、前記リピータ・サーバ・ネットワークを構成するリピータ・サーバは複数の名称を用いてアドレスを指定することが可能であり、リクエストが既知のサブスクライバから提供されるリソースに対するリクエストであるかどうかの判断は、前記リピータ・サーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づいていることを特徴とするシステム。
【請求項２３】
請求項２１記載のシステムにおいて、リクエストが既知のサブスクライバから提供されるリソースに対するリクエストであるかどうかの判断は、前記リクエストをするのに用いられたＵＲＬの中の起点サーバ名に少なくとも部分的に基づいていることを特徴とするシステム。
【請求項２４】
請求項２２又は請求項２３のいずれかの請求項に記載のシステムにおいて、前記リピータ・サーバは、ＨＴＴＰホスト・ヘッダの中の情報を用いて、前記リピータ・サーバのアドレスを指定するに用いられた名称を判断することを特徴とするシステム。
【請求項２５】
請求項２１記載のシステムにおいて、サブスクライバは、少なくとも１つの起点サーバを介してファイルを公開する企業であることを特徴とするシステム。
【請求項２６】
複数の企業が１又は複数の起点サーバを介してリソースを公開するシステムであって、
複数のリピータ・サーバから構成されたリピータ・サーバ・ネットワークであって、このリピータ・サーバ・ネットワークの中の前記リピータ・サーバの少なくとも一部は、前記起点サーバの少なくとも一部において入手可能な情報の一部又は全部を複製する、リピータ・サーバ・ネットワークと、
前記リピータ・サーバ・ネットワークに加入してサブスクライバとなっている複数の企業と、
を含んでおり、前記リピータ・サーバ・ネットワークになされたリソースに対するリクエストは、前記リクエストが前記リピータ・サーバ・ネットワークのサブスクライバから提供されるリソースに対するリクエストではない場合には、拒絶されることを特徴とするシステム。
【請求項２７】
（ａ）複数の起点サーバと（ｂ）少なくとも１つのリピータ・サーバ・ネットワークを構成する複数のリピータ・サーバとを含み、前記リピータ・サーバの少なくとも一部は前記起点サーバにおいて入手可能な情報の一部又は全部を複製し、コンテンツに対するクライアントからのリクエストはリクエストされたコンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理されるコンピュータ・ネットワークの中のサーバがリクエストを処理する方法であって、
１つのリピータ・サーバに複数の名称を割り当てるステップと、
情報に対してリクエストがなされると、前記リピータ・サーバのアドレスを指定するのに用いられた名称を判断するステップと、
前記判断に少なくとも部分的に基づいて、前記名称が既知のサブスクライバに対応する場合には前記リクエストされた情報を与えることを試み、前記名称が既知のサブスクライバに対応しない場合には前記リクエストされた情報を与えないステップと、
を含むことを特徴とする方法。
【請求項２８】
請求項２７記載の方法において、ＨＴＴＰホスト・ヘッダにおける情報を用いて前記リピータ・サーバのアドレスを指定するのに用いられた名称を判断するステップを更に含むことを特徴とする方法。
【請求項２９】
（ａ）複数の起点サーバと（ｂ）少なくとも１つのリピータ・サーバ・ネットワークを構成する複数のリピータ・サーバとを含み、前記リピータ・サーバの少なくとも一部は前記起点サーバにおいて入手可能な情報の一部又は全部を複製し、コンテンツに対するクライアントからのリクエストは、前記コンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理されるコンピュータ・ネットワークの中のサーバがリクエストを処理する方法であって、
リソースに対するリクエストを取得するステップと、
取得されたリクエストが既知のサブスクライバから提供されるリソースに対するリクエストでない場合には、前記リクエストを拒絶し、
それ以外の場合には、前記リクエストされたリソースを含む返答を構築して、前記返答を与えるステップと、
を含むことを特徴とする方法。
【請求項３０】
請求項２９記載の方法において、
前記リクエストされたリソースは、あるリピータ・サーバによって、ある起点サーバから取得され、
前記リピータ・サーバは、当該リピータ・サーバ自体のアドレスを指定するのに用いられた名称に基づいて、前記リクエストを処理するのにどの起点サーバを用いるべきかを判断することを特徴とする方法。
【請求項３１】
請求項２９記載の方法において、
前記リクエストされたリソースは、あるリピータ・サーバによって、ある起点サーバから取得され、
前記リピータ・サーバは、ＨＴＴＰホスト・ヘッダにおける情報に基づいて、前記リクエストを処理するのにどの起点サーバを用いるべきかを判断することを特徴とする方法。
【請求項３２】
（ａ）複数の起点サーバと（ｂ）少なくとも１つのリピータ・サーバ・ネットワークを構成する複数のリピータ・サーバとを含み、前記リピータ・サーバの少なくとも一部は前記起点サーバにおいて入手可能な情報の一部又は全部を複製し、コンテンツに対するクライアントからのリクエストは、前記コンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理されるコンピュータ・ネットワークの中のサーバがリクエストを処理する方法であって、
１つのリピータ・サーバに複数の名称を割り当てるステップと、
情報に対するリクエストをリピータ・サーバが受信すると、前記リピータ・サーバのアドレスを指定するのに用いられた名称を少なくとも用いて、リクエストされている情報が前記リピータ・サーバ・ネットワークのサブスクライバから提供される情報であるかどうかを確認するステップと、
を含むことを特徴とする方法。
【請求項３３】
（ａ）複数の起点サーバと（ｂ）少なくとも１つのリピータ・サーバ・ネットワークを構成する複数のリピータ・サーバとを含み、前記リピータ・サーバの少なくとも一部は前記起点サーバの少なくとも一部において入手可能な情報の一部又は全部を複製し、コンテンツに対するクライアントからのリクエストは、前記コンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理されるコンピュータ・ネットワークの中のサーバがリクエストを処理する方法であって、
リソースに対するリクエストをクライアントから取得するステップと、
取得されたリクエストが既知のサブスクライバから提供されるリソースに対するリクエストであると判断される場合には、
リクエストされたリソースがローカルにキャッシュされているかどうかを判断し、前記判断に少なくとも部分的に基づいて、前記リクエストされたリソースが前記リピータ・サーバのキャッシュの中にある場合には、前記リクエストされたリソースをリトリーブするステップと、
リクエストされたリソースがローカルにキャッシュされていないと判断されるときには、前記リクエストされたリソースを前記起点サーバ又はピア・キャッシュから取得することを試みるステップと、
を含んでおり、前記リピータ・サーバは、前記リピータ・サーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づいて、どの起点サーバを用いるべきかを判断し、
この発明は、更に、取得されたリクエストが既知のサブスクライバから提供されるリソース以外のリソースに対するリクエストであると判断される場合には、前記リクエストを拒絶するステップを含むことを特徴とする方法。
【請求項３４】
システムであって、
（ａ）複数の起点サーバと、
（ｂ）少なくとも１つのリピータ・サーバ・ネットワークを構成する複数のリピータ・サーバであって、前記リピータ・サーバの少なくとも一部は前記起点サーバの少なくとも一部において入手可能な情報の一部又は全部を複製し、コンテンツに対するクライアントからのリクエストは前記コンテンツが与えられるように前記リピータ・サーバ・ネットワークによって処理され、これらのリピータ・サーバの少なくとも１つは、
（ｉ）情報に対するリクエストを取得し、
（ｉｉ）前記リクエストが前記リピータ・サーバ・ネットワークの既知のサブスクライバからのリクエストであるかどうかを判断し、
（ｉｉｉ）前記リクエストが既知のサブスクライバからのものであると判断されると、前記リクエストされた情報を与えることを試みるように構成されプログラムされた複数のリピータ・サーバと、
を備えていることを特徴とするシステム。
【請求項３５】
請求項３４記載のシステムにおいて、前記リピータ・サーバは、更に、
前記リクエストされた情報がローカルにキャッシュされているかどうかを判断し、
前記判断に基づいて、前記リクエストされたリソースがローカルにキャッシュされている場合には、前記リクエストされたリソースをリトリーブし、
前記リクエストされたリソースがローカルにキャッシュされていないと判断されるときには、リクエストされたリソースを起点サーバから又はピア・キャッシュから取得することを試みるように構成されプログラムされていることを特徴とするシステム。
【請求項３６】
請求項３５記載のシステムにおいて、前記リピータ・サーバの一部には複数の名称を割り当てることが可能であり、前記リピータ・サーバは、更に、
前記リピータ・サーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づいてどの起点サーバを用いるべきかを判断するように構成されプログラムされていることを特徴とするシステム。
【請求項３７】
請求項３５記載のシステムにおいて、前記リピータ・サーバは、更に、
前記リクエストをするのに用いられたＵＲＬの中の起点サーバ名に少なくとも部分的に基づいて、どの起点サーバを用いるべきかを判断するように構成されプログラムされていることを特徴とするシステム。
【請求項３８】
プロセッサを含むサーバであって、前記プロセッサは、
（ｉ）複数の起点サーバにおいて入手可能な情報の一部又は全部を複製し、
（ｉｉ）情報に対するリクエストを取得し、
（ｉｉｉ）取得されたリクエストが、このサーバを含むリピータ・サーバ・ネットワークの既知のサブスクライバから提供される情報に対するリクエストであるかどうかを判断し、
（ｉｖ）前記リクエストが前記リピータ・サーバ・ネットワークの既知のサブスクライバから提供される情報に対するリクエストであると判断されるときには、前記情報を与えるように構成されプログラムされていることを特徴とするサーバ。
【請求項３９】
請求項３８記載のサーバにおいて、更に、
このサーバのアドレスを指定するのに用いられた名称に少なくとも部分的に基づき、前記リクエストが既知のサブスクライバから提供される情報に対するリクエストであるかどうかを判断するようにプログラムされていることを特徴とするサーバ。
【請求項４０】
請求項３８記載のサーバにおいて、更に、
前記リクエストをするのに用いられたＵＲＬの中の起点サーバ名に少なくとも部分的に基づいて、前記リクエストが既知のサブスクライバから提供される情報に対するリクエストであるかどうかを判断するようにプログラムされていることを特徴とするサーバ。
【請求項４１】
請求項３９又は請求項４０のいずれかの請求項に記載のサーバにおいて、前記サーバは、ＨＴＴＰホスト・ヘッダの中の情報を用いてアドレスを指定するのに用いられた名称を判断することを特徴とするサーバ。
【請求項４２】
請求項３８記載のサーバにおいて、更に、
前記リクエストが既知のサブスクライバから提供されるリソースに対するリクエストであると判断される場合には、リクエストされた情報がローカルにキャッシュされているかどうかを判断し、前記判断に部分的に基づいて、前記リクエストされた情報がローカルにキャッシュされている場合には、前記リクエストされた情報をリトリーブし、
前記リクエストされた情報がローカルにキャッシュされていないと判断されるときには、前記リクエストされている情報を起点サーバから又はピア・キャッシュから取得するようにプログラムされていることを特徴とするサーバ。
【請求項４３】
請求項４２記載のサーバにおいて、更に、
前記リクエストされた情報を取得する際には、前記情報をローカルにキャッシュするようにプログラムされていることを特徴とするサーバ。
【請求項４４】
請求項４３記載のサーバにおいて、更に、
前記リクエストされた情報を含む返答を構築し送信するようにプログラムされていることを特徴とするサーバ。
【請求項４５】
請求項４４記載のサーバにおいて、更に、
トランザクションに関する詳細を記録するようにプログラムされていることを特徴とするサーバ。
【請求項４６】
請求項４５記載のサーバにおいて、前記詳細は、
現在の時間、リクエストしている側のアドレス、リクエストされたユニフォーム・リソース・ロケータ（ＵＲＬ）、そして、生成された応答のタイプの中の１又は複数を含むことを特徴とするサーバ。
【発明の詳細な説明】
【発明の属する技術分野】
【０００１】
本発明は、コンピュータ・ネットワークにおけるリソース（resource）の複製（replication）に関する。
【従来の技術】
【０００２】
インターネットなど地球規模のコンピュータ・ネットワークの出現により、情報を取得する方法は、全く新しく異なったものとなっている。今日では、インターネットのユーザは、世界のどこからでも情報にアクセス可能であって、その際に、ユーザあるいは情報のどちらについても、現実の位置は問題にならない。ユーザは、単に、情報に対するネットワーク・アドレスを知り、そのアドレスをネットワーク・ブラウザなどの適切なアプリケーション・プログラムに提供することによって、情報を得ることができる。
【０００３】
インターネットの人気が急速に高まるにつれて、ネットワーク全体に課せられるトラフィックの負担が重くなってきている。要求されている課題（例えば、よりよいアクセス可能性や、より高速な通信リンクなど）を解決することは、単に、供給側への負担を増加させることに過ぎない。インターネット・ウェブ・サイト（ここでは、「パブリッシャ」（publishers）と称する）は、増大し続ける帯域幅の必要性に対応し、負荷の動的な変化に配慮し、遠隔地、特に海外で閲覧しているクライアントのためにパフォーマンスを向上させなければならない。また、ライブ・オーディオやビデオなど、コンテンツが豊富なアプリケーションに対応することによって、問題が更に悪化している。
【０００４】
基本的な帯域幅増加の必要性に対応するために、ウェブ・パブリッシャは、典型的には、インターネット・サービス・プロバイダ（ＩＳＰ）から追加的な帯域幅を使用できるように契約することになる。その際には、ＩＳＰからパブリッシャの位置までのより大きな又は追加的な「パイプ」又はチャネルという形態をとるか、ＩＳＰのリモート・ホスティング・サーバ集合体においてより大きな帯域幅を取得するという形態をとるかのいずれかである。しかし、このような増加は、パブリッシャが必要とする程には細かな対応がなされるとは限らないし、多くの場合、リード・タイムのために、パブリッシャのウェブ・サイトの能力が、要求されるものよりも劣ったものとなることがある。
【０００５】
更に深刻な帯域幅増大の課題に対応するために、パブリッシャは、より複雑であり費用も要する特別な解決策を講じる場合もある。最も一般的な必要性に対する解決策である容量の増大のためには、一般に、ハードウェア・リソースとサイトのコンテンツとを複製し、帯域幅リソースを複製する。しかし、これらの解決策は、実現して運用するのが困難でありコストも要する。結果として、最も大きな規模をもつようなパブリッシャでなければそのような余裕はない。というのは、そのようなパブリッシャだけが、多くの顧客（及びウェブ・サイトのヒット）に対してそのようなコストを転嫁できるからである。
【０００６】
複製及びミラーリング（mirroring）を促進するために、多数の解決策が講じられてきている。一般には、これらの技術は、単一のウェブ・サイトによる利用に関して設計されているのであって、その技術の構成要素が多くのウェブ・サイトによって同時に共有されることを可能にするという特徴は備えていない。
【０００７】
解決策の機構によっては、ミラー・サーバを更新された状態に維持することに役立つ複製ソフトウェアを提供するものがある。このような機構は、ファイル・システムの完全なコピーを作ることによって動作するのが一般的である。そのようなシステムの１つとして、ファイル・システムの複数のコピーを透過的に同期状態に維持するように動作するものがある。また別のシステムとして、変更のあったファイルを明瞭かつ規則的にコピーする機構を提供するものもある。データベース・システムは、複製が特に困難であるが、その理由は、データベースは常に変化しているからである。データベースの複製を可能にするような機構もいくつか存在する。しかし、それを達成する標準的なアプローチといったものは存在しない。プロキシ・キャッシュを提供しているいくつかの企業は、そのようなものを、複製ツールと称している。しかし、プロキシ・キャッシュは、パブリッシャではなくクライアントに代わりに動作するのであるから、別のものである。
【０００８】
ウェブ・サイトが複数のサーバによって維持されている場合には、負荷がこれら複数のサーバの間で適切に配分され均衡することが保証されるようにすることが目標である。ドメイン・ネーム・サーバ・ベースのラウンド・ロビン式のアドレス分配では、異なるクライアントは異なるミラーに方向付けられることになる。
【０００９】
別の解決策である負荷均衡化では、各サーバにおける負荷を考慮して（様々な方法で測定される）、特定のリクエストをどのサーバが処理すべきであるかを選択する。
負荷バランサは、様々な技術を用いて、リクエストを適切なサーバにルーティングする。これらの負荷均衡化技術のほとんどが、各サーバは元のウェブ・サイトの正確な複製であることを要求する。負荷バランサは、クライアントと候補となるミラー・サーバとの間の「ネットワーク距離」を考慮しない。
【００１０】
クライアントのプロトコルが容易には変更されないと仮定すると、リソースを複製して分散させることには主な問題が２つ存在する。第１に、リソースのどのコピーを用いるべきかをいかにして選択するかである。すなわち、あるリソースに対するリクエストが１つのサーバに向かってなされたときに、そのサーバ（又は、そのデータ）の複製の選択をいかにして行ったらよいかという問題である。我々は、この問題を「ランデブ（rendezvous）問題」と称することにする。クライアントを離れた複数のミラー・サーバにおいて会わせる方法は多数存在する。これらの技術は、負荷バランサと同様に、リクエストを適切なサーバにルーティングしなければならない。しかし、その決定を下す際に、ネットワークのパフォーマンスと幾何学的構成（トポロジ）とを考慮する点で負荷バランサとは異なっている。
【００１１】
多数の企業が、ネットワーク・トラフィックの優先順位を決定しフィルタリングを行うことによってネットワーク・パフォーマンスを向上させる製品を提供している。プロキシ・キャッシュは、クライアント集合体（client aggregators）が人気のあるリソースのコピーをエンド・ユーザの近くに記憶することによってネットワーク・リソースの消費を減少させる方法を提供する。クライアント集合体の１つとしては、ブラウザを動作させている多数のクライアントをインターネットに接続させるインターネット・サービス・プロバイダやそれ以外の組織がある。クライアント集合体は、プロキシ・キャッシュを用いることによって、ウェブ・コンテンツをこれらのブラウザに提供するのに必要となる帯域幅を減少させる。しかし、伝統的なプロキシ・キャッシュは、ウェブ・パブリッシャではなく、ウェブ・クライアントに代わって動作されている。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
プロキシ・キャッシュは、最も人気のあるリソースをすべてのパブリッシャから記憶する。しかし、これは、合理的なキャッシュ効率を達成するには、プロキシ・キャッシュが非常に大きくなければならないことを意味する。（キャッシュ効率（efficiency）は、既にキャッシュされているリソースに対するリクエストの数をリクエストの総数で除算した値として定義される。）
プロキシ・キャッシュは、リソースと共に運ばれるリソースがいつ複製されるべきかを決定するキャッシュ制御ヒントに依存する。これらのヒントは予言的なものであって、必ずしも正確でないことも多いために、プロキシ・キャッシュが陳腐化している（stale）データを与えることも多い。従って、多くの場合に、プロキシ・キャッシュのオペレータは、自らのプロキシに、これらのヒントを無視することによってキャッシュの効率を高めるように指示する。そうすることによって、キャッシュが陳腐化したデータを提供する頻度が多くなる場合にもそうである。
【００１３】
プロキシ・キャッシュによって、クライアントの活動はパブリッシャから見えなくなる。リソースがいったんキャッシュされると、パブリッシャとしては、そのリソースがキャッシュからどのくらいの頻度でアクセスされたのかを知る方法をもたないことになる。
【課題を解決するための手段】
【００１４】
本発明は、コンピュータ・ネットワークの中のサーバが、選択されたリソースに対するリクエストを処理する際に、それらのリクエストを処理する別のサーバ（「リピータ」）を決定することによって、リクエストの処理をオフロードする方法を提供する。リピータの選択は、可能性のあるリピータに関する情報に基づいて動的に行うことができる。
【００１５】
リクエストされたリソースが他のリソースへの参照を含む場合には、これらの参照のいくつか又はすべてを、リピータへの参照と交換することができる。
従って、ある側面においては、本発明は、コンピュータ・ネットワークにおいてリソース・リクエストを処理する方法である。第１に、クライアントが、起点サーバ（origin server）から特定のリソースに対するリクエストを行う。このリクエストには、特定のリソースに対するリソース識別子が含まれる。リソース識別子は、時には、起点サーバの指示を含むこともある。起点サーバに到着するリクエストが、常に起点サーバの指示を含むとは限らない。というのは、リクエストは起点サーバに送られているのであって、起点サーバを指定していることは必要ないからである。リフレクタと称され、起点サーバと同じ位置にある機構が、クライアントから起点サーバへのリクエストをインターセプトし、このリクエストを反射すべきか、それともローカルに処理すべきかを決定する。リフレクタは、リクエストをローカルに処理すると決定する場合には、そのリクエストを起点サーバに送る。そうでない場合には、リクエストを処理する「最良の」リピータを選択する。リクエストが反射される場合には、クライアントは、リピータを指定する修正されたリソース識別子を与えられる。
【００１６】
クライアントは、リフレクタから修正されたリソース識別子を受け取り、その修正されたリソース識別子において指定されているリピータに特定のリソースをリクエストする。
リピータは、クライアントのリクエストを受け取ると、リクエストされたリソースをクライアントに返送することによって応答する。リピータは、リソースのローカルなコピーを有している場合には、そのコピーを返送する。有していない場合には、リクエストを起点サーバに送ってリソースを取得し、そのリソースのローカルなコピーをセーブすることによって、それ以後のリクエストに対応できるようにする。
【００１７】
リクエストを処理する適切なリピータのリフレクタによる選択は、多くの方法で行うことができる。好適実施例では、その選択は、第１に、ネットワークを「コスト・グループ」に予め分割し、そして、クライアントがどのコスト・グループの中に存在するかを判断することによって、なされる。次に、ネットワークの中の複数のリピータから、１組のリピータが選択されるが、この１組に含まれるリピータは、クライアントが存在しているコスト・グループに対して低いコストを有するようになっている。最小のコストを決定するために、テーブルが維持され、定期的に更新されて、各グループと各リピータとの間のコストが定義される。次に、この１組に含まれるリピータが１つ、好ましくはランダムに、最良のリピータとして選択される。
【００１８】
特定のリクエストされたリソース自体が他のリソースの識別子を含みうる場合には、リソースは、（クライアントに提供される前に）書き換えられることがある。特に、このリソースは書き換えられることによって、その中に含まれるリソース識別子の少なくともいくつかを、起点サーバの代わりにリピータを指定する修正されたリソース識別子と交換する。この書き換え（rewriting）プロセスの結果、クライアントは、特定のリクエストされたリソースの中の識別子に基づいて他のリソースをリクエストするときには、これらのリクエストを選択されたリピータに対して直接に行い、リフレクタと起点サーバとを完全にバイパスする。
【００１９】
リソースの書き換えは、リフレクタによって実行されなければならない。ただし、リピータが互いに「同等（peer）」であり、リピータを指定する書き換えられたリソース識別子を含むリソースのコピーを作るような場合には、リピータによって行われることも可能である。
【００２０】
好適実施例では、ネットワークはインターネットであり、リソース識別子はインターネット上のリソースを指定するユニフォーム・リソース・ロケータ（ＵＲＬ）であり、修正されたリソース識別子はリピータを指定し（後にステップＢ３において説明されるように）起点サーバを指示するＵＲＬである。修正されたリソース識別子は、リディレクト（ＲＥＤＩＲＥＣＴ）メッセージを用いて、クライアントに提供される。リフレクタがリクエストを「反射」しているときにだけ、ＲＥＤＩＲＥＣＴメッセージを用いて修正されたリソース識別子が提供されることに注意すべきである。
【００２１】
別の側面では、本発明は、起点サーバと、それに関連するリフレクタを有する少なくともいくつかの起点サーバと、複数のリピータとを備えたコンピュータ・ネットワークである。
【００２２】
本発明の上述した及びそれ以外の目的及び効果は、添付の図面を参照しながら以下の詳細な説明を考慮することによって、明らかになるはずである。添付の図面では、すべての図面を通じ、同じ構成要素には同じ参照番号が付されている。
【発明の実施の形態】
【００２３】
大要
図１には、本発明によるネットワーク環境１００の一部が示されており、サーバ（ここでは、起点サーバ１０２）における機構（リフレクタ１０８、後で詳述する）が、多数の部分的に複製されたサーバすなわちリピータ１０４ａ、１０４ｂ及び１０４ｃを維持し、トラッキングしている。各リピータ１０４ａ、１０４ｂ及び１０４ｃは、起点サーバ１０２において入手可能な情報とネットワーク１００の他の起点サーバにおいて入手可能な情報の一部又はすべてを複製する。リフレクタ１０８は、「コンタクト」リピータとして知られている特定のリピータ（図１に示されているシステムでは、「リピータＢ」１０４ｂ）に接続されている。好ましくは、各リフレクタは、そのコンタクトである１つのリピータとの接続を維持し、各リピータは、そのマスタ・リピータである特別のリピータ（例えば、図１では、リピータ１０４ａ、１０４ｂ及び１０４ｃに対するリピータ１０４ｍ）との接続を維持する。
【００２４】
従って、リピータは、起点サーバ１０２の部分的又は希薄なミラーをこの起点サーバの分散されたコヒーレント・キャッシュを実現することによって維持する専用のプロキシ・サーバと考えることができる。リピータは、複数の起点サーバの（部分的な）ミラーを維持することができる。いくつかの実施例では、ネットワーク１００はインターネットであり、リピータは、クライアントのＨＴＴＰ（ハイパーテキスト・トランスファ・プロトコル）及びＦＴＰ（ファイル・トランスファ・プロトコル）リクエストに応答して、起点サーバによって提供される選択されたリソースのミラーリングを行う。
【００２５】
クライアント１０６は、ネットワーク１００を介して、起点サーバ１０２に接続し、更に、１つ又は複数のリピータ１０４ａなどにも接続することがありうる。
起点サーバ１０２とは、リソースが生じるサーバである。更に一般的には、起点サーバ１０２は、クライアント１０６からのリクエストに応答してリソースを提供する任意のプロセス又はプロセスの集合である。起点サーバ１０２は、任意の既製（off-the-shelf）のウェブ・サーバでありうる。好適実施例では、起点サーバ１０２は、典型的には、アパッチ（Apache）サーバや、ネットスケープ・コミュニケーションズ・コーポレーション社TMのサーバなどである。
【００２６】
クライアント１０６は、エンド・ユーザに代わって起点サーバ１０２からリソースをリクエストするプロセッサである。クライアント１０６は、典型的には、ユーザ・エージェント（例えば、ネットスケープ・コミュニケーションズ社のナビゲータTM）又はユーザ・エージェントのためのプロキシである。リフレクタ１０８やリピータ１０４ａ、１０４ｂなど以外の構成要素は、一般的に入手可能なソフトウェア・プログラムを用いて実現することができる。特に、本発明は、任意のＨＴＴＰクライアント（例えば、ウェブ・ブラウザ）、プロキシ・キャッシュ、ウェブ・サーバと共に機能する。更に、リフレクタ１０８は、完全に、データ・サーバ１１２（例えば、ウェブ・サーバ）の中に一体化することができる。これらの構成要素は、拡張機構（いわゆる、アドイン・モジュールなど）を用いて緩やかに一体化するか、又は、サービス構成要素を特にリピータをサポートするように修正することによって緊密に一体化することができる。
【００２７】
起点サーバ１０２において生じるリソースは、静的又は動的でありうる。すなわち、リソースは固定されていることもありうるし、特にリクエストに応答して起点サーバ１０２によって作成されることもありうる。ここで、「静的」及び「動的」という用語は相対的なものであることに注意すべきである。というのは、静的なリソースが、何らかの規則的な（長い場合もあるが）期間で変化することもありうるからである。
【００２８】
クライアント１０６から起点サーバ１０２へのリソース・リクエストは、リフレクタ１０８によってインターセプトされ、リフレクタ１０８は、与えられたリクエストに対して、そのリクエストを、起点サーバ１０２に与えるか、又は、ネットワーク１００内のいずれかのリピータ１０４ａ、１０４ｂなどに向けて条件的に反射する。すなわち、クライアント１０６による起点サーバ１０２へのリクエストの性質に応じて、リフレクタ１０８は、そのリクエストをローカルに（起点サーバ１０２において）処理するか、又は、複数のリピータの中から１つ（好ましくは、そのジョブにとって最良のリピータ）を選択して、リクエストをその選択されたリピータに向けて反射する。換言すると、リフレクタ１０８は、クライアント１０６によってなされた起点サーバ１０２からのリソースに対するリクエストを、起点サーバ１０２によってローカルに処理されるようにするか、又は、最良のリピータ１０４ａ、１０４ｂなどに向けて透過的（transparently）に反射する。最良のリピータという概念と、最良のリピータが選択される態様については、後で詳細に説明する。
【００２９】
リピータ１０４ａ、１０４ｂなどは、クライアントのリクエストを処理することによってここで説明するようにパフォーマンスを向上させコストを低下させるのに用いられる中間的（intermediate）なプロセッサである。リピータ１０４ａ、１０４ｂなどの内部には、起点サーバ１０２に代わってリソースをクライアント１０６まで送る任意のプロセス又はプロセスの集合が存在する。リピータは、起点サーバ１０２との不必要なトランザクションを回避するのに用いられるリピータ・キャッシュ１１０を含みうる。
【００３０】
リフレクタ１０８は、通常であれば直接に起点サーバ１０２に送られるリクエストをインターセプトする機構であり、好ましくは、ソフトウェア・プログラムである。図面では別個の構成要素として示されているが、リフレクタ１０８と起点サーバ１０２とは、例えばデータ・サーバ１１２などの特定のシステム上の同じ位置に存在するのが典型的である。後述するように、リフレクタ１０８は、起点サーバ１０２の一部となる「プラグイン」モジュールでもありうる。
【００３１】
図１には、本発明によるネットワークの一部だけが示されている。完全な動作ネットワークは、任意の数のクライアント、リピータ、リフレクタ及び起点サーバから構成される。リフレクタはリピータ・ネットワークと通信し、ネットワーク内のリピータは相互に通信する。
ユニフォーム・リソース・ロケータ
コンピュータ・ネットワークの中のそれぞれの場所は、一般に一連の名前又は数字として特定することができるアドレスを有する。情報にアクセスするためには、その情報のアドレスを知らなければならない。例えば、インターネットの一部であるワールド・ワイド・ウェブ（「ウェブ」）上では、情報のアドレス位置が提供される態様は、ユニフォーム・リソース・ロケータ（ＵＲＬ）に標準化されている。ＵＲＬは、ネットワーク上でのリソース（情報、データ・ファイルなど）の位置を特定する。
【００３２】
ＵＲＬという概念は、ハイパーテキスト・ドキュメントが用いられる際には、更に有用になる。ハイパーテキスト・ドキュメントとは、そのドキュメント（文書）自体の内部に、そのドキュメント自体又はそれ以外のドキュメントへのリンク（ポインタ又は参照）を含むようなドキュメントである。例えば、オンラインでの法律リサーチ・システムでは、それぞれの判例（ケース、事件）をハイパーテキスト・ドキュメントとして与えることができる。他の判例を引用するときには、それらへのリンクを提供することができる。このようにすれば、ある１つの判例を読んでいる人間は、引用リンクをたどることによって、引用されている判例の適切な部分を読むことが可能となる。
【００３３】
一般的にインターネットにおいて、そして、特にワールド・ワイド・ウェブでは、ドキュメントを、ハイパーテキスト・マークアップ・ランゲージ（ＨＴＭＬ）と称される標準化された形式を用いて作成することができる。ＨＴＭＬでは、ドキュメントは、同じドキュメントの別のセクションや他のドキュメントへのリンクを含むデータ（テキスト、イメージ、サウンドなど）から構成されている。これらのリンクは、一般に、ＵＲＬとして提供されており、相対的又は絶対的な形式を有することができる。相対的なＵＲＬとは、ＵＲＬの中の、そのリンクを含むドキュメントに対するものと同じ部分を単純に削除したものである。ここでリンクとは、（同じドキュメントへのリンクがなされている場合の）ドキュメントのアドレスなどである。一般に、ブラウザ・プログラムは、現在のドキュメントからの対応する部分を用いてＵＲＬの欠けている部分を補足し、それによって、登録されたドメイン・ネームのすべてを含む完全なＵＲＬを形成する。
【００３４】
ハイパーテキスト・ドキュメントは、他のドキュメントへのリンクをいくつでも含むことが可能であり、これら他のドキュメントは、それぞれが、世界の別の地域にある別のサーバに存在していてもかまわない。例えば、あるドキュメントが、ロシア、アフリカ、中国、オーストリアに存在するドキュメントへのリンクを含んでいてもよい。特定のクライアントにおいてそのドキュメントを見ているユーザは、任意のリンクを透過的に（すなわち、リンクされているドキュメントが実際にはどこに存在するのかを知ることなく）たどることが可能である。従って、あるリンクをたどるコスト（時間、金銭又はリソース配分という点での）は、他のリンクと比較して非常に大きなものとなりうる。
【００３５】
ＵＲＬは、一般に、次のような形式を有する（詳細については、T. Berners-Lee et al., Uniform Resource Locators (URL), Network Working Group, Request for Comments: 1738, Category: Standard Track, December 1994, located at 「http://ds.internic.net/rfc/rfc1738.txt」を参照のこと。これについては、この出願において援用する。）：scheme://host[:port]/url-path
ここで、scheme（スキーム、方式）とは、file（ローカル・システム上のファイルの場合）、ftp（アノニマスＦＴＰファイル・サーバ上のファイルの場合）、http（ウェブ・サーバ上のファイルの場合）、telnet（テルネット・ベースのサービスへの接続の場合）などのシンボルである。これ以外のスキームを用いることもできるし、新たなスキームもしばしば追加されることがある。ポート番号はオプショナルであって、何も提供されていない場合には、システムが、デフォルトのポート番号（スキームに依存する）を用いる。host（ホスト）フィールドは、特定のコンピュータに対する特定のネットワーク・アドレスへのマップを与える。url-path（ＵＲＬ経路）は、ホスト・フィールドにおいて特定されるコンピュータに対するものである。url-pathは、典型的には、しかし必ずそうであるというのではないが、ウェブ・サーバ・ディレクトリの中のファイルの経路名である。
【００３６】
例えば、次に、「www.uspto.gov」におけるコンピュータ上の経路A/B/CにおけるファイルFを識別するＵＲＬを掲げる：
http://www.uspto.gov/A/B/C/F
このＵＲＬによって特定されるファイルＦ（リソース）にアクセスするためには、ユーザのコンピュータ（すなわち、クライアント・コンピュータ）上で動作しているプログラム（例えば、ブラウザ）は、第１に、ホスト名によって特定されるコンピュータ（すなわち、サーバ・コンピュータ）を見つけなければならない。すなわち、プログラムは、「www.uspto.gov」というサーバを見つけなければならない。そうするために、プログラムは、ドメイン・ネーム・サーバ（ＤＮＳ）にアクセスし、ＤＮＳにホスト名（「www.uspto.gov」）を提供する。ＤＮＳは、ドメイン名からアドレスを引き出すある種の集中的なディレクトリとして機能する。「www.uspto.gov」という名前に対応する（遠隔サーバ）コンピュータが存在するとＤＮＳが判断する場合には、ＤＮＳは、プログラムにそのサーバ・コンピュータに対する実際のコンピュータ・ネットワーク・アドレスを提供する。インターネットでは、これは、インターネット・プロトコル（又は、ＩＰ）アドレスと称され、"123.345.456.678"という形式を有している。ユーザの（クライアント）コンピュータ上のプログラムは、次に、この実際のアドレスを用いて遠隔（サーバ）コンピュータにアクセスする。
【００３７】
プログラムは、遠隔コンピュータ「www.uspto.gov」上のＨＴＴＰサーバ（ウェブ・サーバ）への接続を開き、この接続を用いて、リクエスト・メッセージをこの遠隔コンピュータに（ＨＴＴＰスキームを用いて）送る。このメッセージは、典型的には、リクエストされたリソースであるA/B/C/DというＵＲＬ経路を含むＨＴＴＰのＧＥＴリクエストである。ＨＴＴＰサーバは、このリクエストを受信し、それを用いてA/B/C/DというＵＲＬ経路によって特定されるリソースにアクセスする。サーバは、リソースを同じ接続を介して返送する。
【００３８】
このように、通常は、起点サーバにおけるＨＴＴＰクライアントのウェブ・リソースに対するリクエストは、次のように処理される（図２を参照）。ただし、これは、リフレクタ１０８がインストールされていないプロセスの説明である。
【００３９】
Ａ１．クライアントにおけるブラウザ（例えば、ネットスケープ社のナビゲータ）は、ユーザからリソース識別子（すなわち、ＵＲＬ）を受け取る。
Ａ２．ブラウザは、リソース識別子からホスト（起点サーバ）名を抽出し、ドメイン・ネーム・サーバ（ＤＮＳ）を用いて、対応するサーバのネットワーク（ＩＰ）アドレスを探す。更に、ブラウザは、存在するのであれば、ポート番号を抽出し、又は、デフォルトのポート番号を用いる（ｈｔｔｐリクエストに対するデフォルトのポート番号は８０である）。
【００４０】
Ａ３．ブラウザは、サーバのネットワーク・アドレスとポート番号とを用いて、クライアント１０６とホストすなわち起点サーバ１０２との間に接続を確立する。
Ａ４．クライアント１０６は、次に、この接続を介して、リクエストされたリソースを識別する（ＧＥＴ）リクエストを送る。
【００４１】
Ａ５．起点サーバ１０２は、リクエストを受け取り、
Ａ６．対応するリソースを見つける、又は、構成する。
Ａ７．次に、起点サーバ１０２は、クライアント１０６に向けて、リクエストされたリソース（又は、リソースが入手不可能である場合には、何らかの形式のエラー・インジケータ）を含む応答を返送する。この応答は、リクエストがクライアントから受け取られたのと同じ接続を介して、クライアントに送られる。
【００４２】
Ａ８．クライアント１０６は、起点サーバ１０２から応答を受け取る。
この基本モデルには、多くの変形例が存在する。例えば、ある変形例では、クライアントにリソースを提供するのではなく、起点サーバが、クライアントに、別の名前によってリソースを再度リクエストするように命じることができる。そうするためには、Ａ７において、サーバ１０２は、クライアント１０６に対して、別の名前を指示する新たなＵＲＬを含むＲＥＤＩＲＥＣＴ（再方向付け）と称される応答を返送する。次に、クライアント１０６は、通常はユーザによる介入なしにシーケンス全体を反復するが、今回は、新たなＵＲＬによって識別されるリソースをリクエストする。
システム動作
本発明では、リフレクタ１０８が、効果的に、通常のウェブ・サーバや起点サーバ１０２の代わりをする。リフレクタ１０８は、起点サーバのＩＰアドレスとポート番号とを引き継ぐことによって、これを行う。このようにして、クライアントは、起点サーバ１０２への接続を試みるときに、実際にはリフレクタ１０８に接続する。次に、起点ウェブ・サーバ（又は、起点サーバ１０２）は、異なるネットワーク・アドレスの、又は、ＩＰアドレスは同一であるがポート番号が異なるリクエストを受け取らなければならない。このように、本発明を用いる際には、上のＡ３ないしＡ７において言及されているサーバは、リフレクタ１０８である。
【００４３】
起点サーバのネットワーク・アドレスをそのままにして、リフレクタを別のアドレス又は別のポートで動作させることも可能であることに注意すべきである。このようにすると、リフレクタは、起点サーバに送られたリクエストをインターセプトすることなく、特別にリフレクタに向けられたリクエストを送ることができる。従って、その通常の動作を中段させることなく、システムを試験し構成することができる。
【００４４】
リフレクタ１０８は、以下のようにプロセスをサポートする（図３を参照のこと）：リクエストを受信すると、
Ｂ１．リフレクタ１０８は、リクエストを解析して、リクエストを反射すべきかどうかを判断する。そうするために、まず、リフレクタは、送り手（クライアント１０６）がブラウザであるのかリピータであるのかを判断する。リピータから生じたリクエストは、起点サーバ１０２によってローカルに処理されなければならない。この判断は、既知のリピータ・ネットワーク（ＩＰ）アドレスのリストにおける送り手のネットワーク（ＩＰ）アドレスを探すことによってなされる。あるいは、この判断は、情報をリクエストに付着させて、そのリクエストが特定のリピータからであるということを指示することによって行うことができる。又は、リピータは、通常のクライアントのために用いられるもの以外の特別のポートからリソースをリクエストできる。
【００４５】
Ｂ２．リクエストがリピータからでない場合には、リフレクタは、テーブル（ルール・ベースと称される）の中でリクエストされたリソースを探して、リクエストされたリソースが「反復（再生）可能である」かどうかを判断する。この判断に基づいて、リフレクタは、リクエストを反射する（下のＢ３）か、又は、リクエストをローカルに処理する（下のＢ４）。
【００４６】
ルール・ベースは、正規表現（regular expression）と関連する属性とのリストである。（正規表現は、コンピュータ・サイエンスの分野において広く知られている。その使用に関する小さな参考図書リストが、Aho, et al., "Compilers, Principles, techniques and tools", Addison-Wesley, 1986, pp. 157-158にある。）与えられたリクエストに対するリソース識別子（ＵＲＬ）は、それを各正規表現とシーケンシャルに整合させることによって、ルール・ベースにおいて求められる。第１の一致によって、そのリソースに対する属性が、すなわち、反復可能であるのかローカルであるのかが、識別される。ルール・ベースにおいて一致が存在しない場合には、デフォルトの属性が用いられる。各リフレクタはそれ自身のルール・ベースを有しており、それは、リフレクタのオペレータによって手動で構成される。
【００４７】
Ｂ３．リクエストを反射するには（リクエストをローカルに処理する場合はＢ４である）、図４に示されているように、リフレクタは、そのリクエストを反射する宛先である最良のリピータを、次に詳細を述べるように、決定する（Ｂ３−１）。次に、リフレクタは、選択されたリピータにおける同じリソースを識別する新たなリソース識別子（ＵＲＬ）を、（リクエストされたＵＲＬと最良のリピータとを用いて）作成する。
【００４８】
反射ステップは、元のリソースのＵＲＬと選択されたリピータの識別子とを含むＵＲＬを１つ作成する。特別の形式のＵＲＬが作成されて、この情報を与える。これは、次のようにして新たなＵＲＬを作成することによってなされる。
【００４９】
Ｄ１．リピータ名、スキーム、起点サーバ名及び経路が与えられた場合に、新たなＵＲＬを作成する。スキームがhttpである場合には、好適実施例は、次のフォーマットを用いる：
http://<repeater>/<server>/<path>
用いられる形式がhttp以外である場合には、好適実施例は、次のフォーマットを用いる：
http://<repeater>/<server>/@proxy=<scheme>@<path>
また、リフレクタは、MIMEタイプをリクエストに付着させ、リピータがそのMIMEタイプに結果を提供するようにさせることができる。これは有用であるが、その理由は、（FTPなどの）多くのプロトコルは、MIMEタイプをリソースに付着させる方法を提供しないからである。フォーマットは、次の通りである。
http://<repeater>/<server>@proxy=<scheme>:<type>@/<path>
このＵＲＬは、リピータによって受信されるときに解釈される。
【００５０】
リフレクタは、次に、この新たなＵＲＬを含むＲＥＤＩＲＥＣＴ応答を、リクエスト側のクライアントに送る（Ｂ３−３）。このHTTP REDIRECTコマンドによって、リフレクタがブラウザにＵＲＬを１つ送ることが可能になり、リクエストが再度試みられる。
【００５１】
Ｂ４．リクエストをローカルに処理するために、リクエストが、リフレクタによって、起点サーバ１０２に送られる（「与えられる」）。このモードでは、リフレクタは、逆プロキシ・サーバとして機能する。起点サーバ１０２は、通常モードでリクエストを処理する（Ａ５−Ａ７）。次に、リフレクタは、リクエストへの起点サーバの応答を取得する。そして、この応答を検査し、リクエストされたリソースがHTMLドキュメントであるかどうか、すなわち、リクエストされたリソースがそれ自身でリソース識別子を含むものであるかどうかを判断する。
【００５２】
Ｂ５．リソースがHTMLドキュメントである場合には、リフレクタは、以下で説明するように、その中のリソース識別子を修正することによって、HTMLドキュメントを書き換える。次に、おそらくは書き換えによって修正されたこのリソースは、リクエスト側のクライアント１０６に宛てた応答の中で返送される。
【００５３】
リクエスト側のクライアントがリピータである場合には、リフレクタは、起点サーバが応答に付着させたすべてのキャッシュ制御修正要素（modifiers）をディセーブルする。これらのディセーブルされたキャッシュ制御修正要素は、後にコンテンツがリピータから与えられたときに、再度イネーブルされる。この機構によって、起点サーバが、リピータにおけるキャッシュの動作に影響を与えることなく、通常のプロキシ・キャッシュにおいてリソースがキャッシュされることを防止することが可能となる。
【００５４】
Ｂ６．リクエストが反射されるのかローカルに処理されるのか、現在時間などのトランザクションに関する詳細、リクエスト側のアドレス、リクエストされたＵＲＬ、発生された応答のタイプなどが、リフレクタによってローカルなログ・ファイルに書き込まれる。
【００５５】
ルール・ベースを用いることによって、リソースを選択的に反射することが可能となる。特定のリソースが有効に反射され得ない（従って、反射されるべきでない）ことの理由は複数存在する。例えば、次の通りである：
リソースが各リクエストに対して一意的に構成されている。
【００５６】
リソースが、いわゆるクッキーに依存している（ブラウザは、異なるドメイン名を有するリピータにクッキーを送ることはない）
リソースが、クライアント上で動作しサービスへの接続を望む（Javaアプレットなどの）プログラムである（Javaは、サービスがそのアプレットを提供したのと同じマシンで動作することを要求する）。
【００５７】
更に、リフレクタ１０８は、あるネットワーク・アドレスからのリクエスト（例えば、リフレクタ自身と同じローカル・エリア・ネットワーク上のクライアントからのリクエストなど）が決して反射されないように構成することもできる。また、リフレクタは、後に説明するように、リフレクタが与えられた集合体情報率（aggregate information rate）を超えているという理由で、リクエストを反射しないように選択することもできる。
【００５８】
反射されたリクエストは、リピータがそのリクエストを受信し処理するときに、そのリピータにおいて自動的にミラーリングされる。
上述した反射プロセスと以下で説明するキャッシング・プロセスとを組み合わせることによって、反復可能なリソースが選択されたリフレクタまで移動されてミラーリングがなされ、反復可能でないリソースについてはミラーリングがなされないようなシステムが効果的に得られる。
別のアプローチ
起点サーバ名を反射されたＵＲＬの中に配置することは、一般的にいって、優れた方法であるが、美的な理由や、（例えば、クッキーの場合には）技術的な理由から、望ましくないとも考えられる。
【００５９】
リピータ名とサーバ名との両方をＵＲＬに含ませることを不要にすることも可能である。その代わりに、名前の「ファミリ」を与えられた起点サーバに対して作成して、それぞれの名前が当該サーバによって用いられるリピータの中の１つを識別するようにすることができる。
【００６０】
例えば、www.example.comが起点サーバである場合には、３つのリピータに対する名前を次のように作成することができる：
wr1.example.com
wr2.example.com
wr3.example.com
最初のwr1.example.comという名前は、リピータ１に対するエイリアス（alias）であり、これは、wr1.anotherExample.comや、wr1.example.eduなどの他の名前によっても知られている。
【００６１】
リピータは、どの名前をもって宛先とされるかを決定することができる場合には、この情報を（リピータのエイリアス名を起点サーバ名と関連させるテーブルと共に）用いて、どの起点サーバが宛先になっているかを決定することができる。例えば、リピータ１がwr1.example.comという宛先を有する場合には、起点サーバはwww.example.comであり、wr1.anotherExample.comという宛先である場合には、起点サーバはwww.anotherExample.comである。
【００６２】
リピータは、どのエイリアスによって宛先とされるかを決定する２つの機構を用いることができる。
１．それぞれのエイリアスを、異なるＩＰアドレスと関連付けることができる。しかし、不運なことに、この解決策ではうまくいかない。というのは、ＩＰアドレスは現時点では数が少なく、必要となるＩＰアドレスの数が、起点サーバとリピータとの積として増加するからである。
【００６３】
２．リピータは、リクエストのHTTPヘッダにおける「host:」タグを検査することによって、用いられているエイリアス名を判断することを試みることができる。しかし、不運なことに、依然として用いられている古いブラウザの中には、リクエストにhost:タグを付着させないものがある。リフレクタは、そのようなブラウザを識別することが必要となり（ブラウザの識別子は各リクエストの一部である）、この形式の反射が回避される。
リピータはいかにしてリクエストを処理するか
ブラウザは、ＲＥＤＩＲＥＣＴ応答（Ｂ３で作成される）を受信すると、新たなリソース識別子（ＵＲＬ）を用いてリソースに対するリクエストを再発行する（Ａ１−Ａ５）。新たな識別子は起点サーバではなくてリピータを参照するので、ブラウザは、リソースに対するリクエストを、次のように、図５に示されているように、リクエストを処理するリピータに送る。
【００６４】
Ｃ１．最初に、リピータは、リクエストを解析して、リクエストしている側のクライアントのネットワーク・アドレスとリクエストされている側のリソースの経路とを判断する。経路には、起点サーバ名が含まれている（Ｂ３との関係で上述した）。
【００６５】
Ｃ２．リピータは、内部テーブルを用いて、起点サーバが既知の「サブスクライバ」（subscriber、加入者）に属することを確認する。サブスクライバとは、１つ又は複数の起点サーバを介してリソースを公にする（パブリッシュする）存在（例えば、企業）である。サブスクライバであるのならば、リピータ・ネットワークを用いることが許される。後に掲げるサブスクライバのテーブルには、リフレクタをサブスクライバにリンクするのに用いられる情報が含まれている。
【００６６】
リクエストが既知のサブスクライバからのリソースに対するものではない場合には、リクエストは拒否される。リクエストを拒否するためには、リピータは、リクエストされたリソースは存在しないことを指示する応答を返送する。
【００６７】
Ｃ３．次に、リピータは、リクエストされたリソースがローカルにキャッシュされているかどかを判断する。リクエストされたリソースがリピータのキャッシュの中にある場合には、検索される。他方で、リクエストされたリソースの有効なコピーがリピータのキャッシュの中には存在しない場合には、リピータは入ってくるＵＲＬを修正して、それを処理する元のリフレクタに直接に宛てるリクエストを作成する（Ｂ１−Ｂ６の場合と同様）。元のリフレクタへのこのリクエストはリピータからのものであるから、リフレクタは、常に、リクエストを反射するのではなく、リクエストされたリソースを返送する（リフレクタは、リピータからのリクエストを常にローカルに処理することに注意すべきである）。リピータがリソースを起点サーバから得た場合には、リピータは、そのリソースをローカルにキャッシュする。
【００６８】
リソースがローカルにキャッシュされない場合には、キャッシュは、その「同等（ピア：peer）のキャッシュ」に質問を発して、リフレクタ／起点サーバからリソースをリクエストする前に、又は、それと同時に、それらのキャッシュの中の１つがそのリソースを含んでいないかどうかを調べる。ピア・キャッシュが制限された時間周期（好ましくは、１秒の数分の１）の間に肯定的な回答をする場合には、リソースはそのピア・キャッシュから検索される。
【００６９】
Ｃ４．次に、リピータは、リクエストされたリソース（キャッシュから、又は、起点サーバから検索されたもの）を含む応答を構成し、その応答をリクエストしている側のクライアントに送る。
【００７０】
Ｃ５．関連するリフレクタ、現在の時間、リクエストしているもののアドレス、リクエストされているＵＲＬ、発生された応答のタイプなど、トランザクションに関する詳細は、リピータにおけるローカルなログ・ファイルに書き込まれる。
【００７１】
図２の下側の列は、ステップＡ１におけるＵＲＬが何を識別するかに応じて、起点サーバ、リフレクタ、リピータを意味する。
最良のリピータの選択
リフレクタ１０８は、リクエストを反射すると決定する場合には、そのリクエストを処理する最良のリピータを選択しなければならない（ステップＢ３−１を参照）。この選択は、次に説明する最良リピータ選択（ＢＲＳ）機構によって行われる。
【００７２】
ＢＲＳの目的は、クライアントのネットワーク・アドレスだけが与えられている場合に、そのクライアントのための適切なリピータを、迅速かつ発見的（ヒューリスティック）に選択することである。適切なリピータは、あまりに大きな負荷を負担しているものであってはならないし、ネットワーク的な尺度から判断してクライアントから離れすぎていてもいけない。ここで用いられる機構は、特定のコンパクトで予め計算されたデータに依存して、迅速に結論を下している。他方で、適切なリピータを選択するのに、動的な方法を用いることもできる。
【００７３】
ＢＲＳは、３つの予め計算されたテーブルに依存している。すなわち、グループ縮小テーブル、リンク・コスト・テーブル、負荷テーブルである。これらの３つのテーブル（後で説明される）は、オフラインで計算され、リピータ・ネットワークにおけるそのコンタクトによって各リフレクタにダウンロードされる。
【００７４】
グループ縮小テーブルは、すべてのネットワーク・アドレスを１つのグループの中に配置する。その目的は、１つのグループの中のアドレスが相対的なコストを共有することによって、条件が変動する場合であっても同じ最良のリピータを有するようにすることである（すなわち、あるグループのメンバーの間では、ＢＲＳは不変である）。
【００７５】
リンク・コスト・テーブルは二次元の行列であり、この行列によって、各リピータと各グループとの間の現在のコストが特定される。最初に、１つのリピータと１つのグループとの間のリンク・コストが、以下で説明するように、当該リピータと当該グループとの間の「正規化（ノーマライズ）されたリンク・コスト」として定義される。時間が経過すると、このテーブルは、当該リピータと当該グループのメンバーとの間での送信に関する相対的なコストをより正確に反映する測定値を用いて更新される。リンク・コスト・テーブルのフォーマットは、<Group ID><Group ID><link cost>であり、ここで、グループＩＤはＡＳメンバーとして与えられる。
【００７６】
負荷テーブルは、各リピータにおける現在の負荷を識別する一次元のテーブルである。リピータの容量は異なりうるので、負荷は、あるリピータが追加的な仕事を引き受ける能力を表す値である。各リピータは、好ましくは１分に１回程度の一定の間隔で、その現在の負荷を中央のマスタ・リピータに送る。マスタ・リピータは、負荷テーブルをネットワーク内の各リフレクタに、コンタクト・リピータを介してブロードキャストする。
【００７７】
リフレクタは、使用が割り当てられているリピータだけに対する負荷テーブルにおいて提供された存在である。リピータのリフレクタへの割当ては、マスタ・リピータにおけるリピータ・ネットワーク・オペレータによって集中的に実行される。この割当てによって、与えられたリフレクタのサービス・レベルを修正することが可能となる。例えば、非常にアクティブなリフレクタは多くのリピータを用いる可能性があるが、比較的アクティブでないリフレクタは非常に少数のリピータしか用いないこともありうる。
【００７８】
これ以外の方法によって選択的なリピータ・サービスをサブスクライバに提供するようにテーブルを構成することも可能である。例えば、ヨーロッパやアジアなど、特定の地理的な地域の中のクライアント向けのものなどが考えられよう。
負荷の測定
現在論じている好適実施例では、リピータ負荷は、２つの数値に関して測定される。すなわち、
１．時間間隔当たりにリピータによって受信されるリクエスト数（ＲＲＰＴ）
２．時間間隔当たりにリピータによって送信されるバイト数（ＢＳＰＴ）
これらの数値のそれぞれに対して、最大の容量設定がなされる。最大の容量とは、リピータが完全にロードされていると考慮されるような点を意味する。ＲＲＰＴ容量が高ければ、より高速なプロセッサであることを意味する。他方で、ＢＳＰＴ容量が高ければ、より幅の広いネットワーク・パイプを意味する。この形式での負荷の測定では、与えられたサーバは、反復タスクの専用であるであると仮定されている。
【００７９】
各リピータは、短い時間間隔の間に受信したリクエストの数と送信されたバイト数とを集計することによって、その現在のＲＲＰＴ及びＢＳＰＴを規則的に計算する。これらの測定値は、各数値に関するリピータの負荷を決定するのに用いられる。リピータの負荷がその構成された容量を超える場合には、警告メッセージがリピータ・ネットワークの管理者に送られる。
【００８０】
これらの２つの現在の負荷成分を組み合わさると、現在の総負荷を示す１つの値が得られる。同様に、２つの最大容量成分を組み合わせると、全体としての最大容量を示す１つの値が得られる。これらの成分の組み合わせ方法は次の通りである。
【００８１】
現在負荷＝Ｂ×現在のＲＲＰＴ＋（１−Ｂ）×現在のＢＳＰＴ
最大負荷＝Ｂ×最大ＲＲＰＴ＋（１−Ｂ）×最大ＢＳＰＴ
ここでのファクタＢは０から１までの値であるが、これによって、ＲＲＰＴ及びＢＳＰＴの相対的な重み（ウェイト）の調整が可能となり、それによって、処理パワー又は帯域幅いずれかを考慮することができる。
【００８２】
全体としての現在の負荷と全体としての最大の負荷との値は、各リピータからマスタ・リピータに周期的に送られ、すべてのリピータに対する負荷の全体を概略を与える負荷テーブルに集計される。負荷テーブルにおける変化は、各リフレクタに自動的に配分される。
【００８３】
好適実施例ではリピータ負荷に関して２次元の数値を用いているが、負荷に関する別の数値を用いることは自由である。
リンク・コストと負荷との合成
ＢＲＳは、適格なそれぞれのリピータからのクライアントを処理するコストを計算する。このコストは、候補であるリピータの使用可能な容量と、当該リピータと当該クライアントとの間のリンクのコストとを組み合わせることによって計算される。リンク・コストは、単にリンク・コスト・テーブルを参照することによって計算される。
【００８４】
コストを計算する公式は次の通りである。
スレショルド＝Ｋ＊最大負荷
容量＝ｍａｘ（最大負荷−現在負荷，ｅ）
容量＝ｍｉｎ（容量，スレショルド）
コスト＝リンク・コスト＊スレショルド／容量
上の公式において、ｅは非常に小さな数（イプシロン）であり、Ｋは初期値が０．５に設定されているチューニング・ファクタ（tuning factor）である。この公式によれば、その容量が構成可能なスレショルドより小さくなると、あるリピータに関するコストは、Ｋによって定義される速度で増加する。
【００８５】
候補となるリピータそれぞれのコストが与えられると、ＢＲＳは、最良のスコアのデルタ・ファクタ内にあるすべてのリピータを選択する。この組の中から、結果をランダムに選択する。
【００８６】
デルタ・ファクタによって、スコアが同じときに、ＢＲＳが１つのリピータを反復的に選択することが回避される。負荷とリンク・コストとに関して得られる情報は時間経過と共に正確さが低下するので、一般に、このような要件が課せられるのである。このファクタは、調整可能である。
最良リピータ選択手段（ＢＲＳ）
ＢＲＳは、次のように動作する。図６を参照のこと。
【００８７】
クライアント・ネットワーク・アドレスと上述した３つのテーブルが与えられているとする。
Ｅ１．グループ縮小テーブルを用いて、クライアントがどのグループの中に存在するかを判断する。
【００８８】
Ｅ２．リンク・コスト・テーブルと負荷テーブルとにおける各リピータに対して、そのリピータの合成コストを次のようにして決定する。
Ｅ２ａ．リピータに対する最大及び現在の負荷を（負荷テーブルを用いて）決定する。
【００８９】
Ｅ２ｂ．リピータとクライアント・グループとの間のリンク・コストを決定する。
Ｅ２ｃ．既に述べた方法で、合成コストを決定する。
Ｅ３．コストが最小であるリピータの小さな組を選択する。
【００９０】
Ｅ４．この組からランダムなメンバーを選択する。
好ましくは、ＢＲＳ処理の結果が、リフレクタ１０８におけるローカル・キャッシュに維持される。従って、最良のリピータが与えられたクライアントに対して（すなわち、与えられたネットワーク・アドレスに対して）最近決定された場合には、その最良のリピータを、再度決定されることなくして、迅速に再利用することができる。上述した計算は統計的に予め計算されているテーブルに基づくので、テーブルが変化しなければ、最良のリピータを再度決定することは必要ない。
グループ縮小及びリンク・コスト・テーブルの決定
ＢＲＳ処理において用いられるグループ縮小テーブルとリンク・コスト・テーブルとは、ここでネットマップ（NetMap）と称する独立の手順によって作成され、規則的に更新される。ネットマップの手順は、必要に応じて複数のフェーズ（後述する）を実行することによって、行われる。
【００９１】
グループという用語は、ＩＰ「アドレス・グループ」を意味するものとして用いられている。
リピータ・グループという用語は、１つのリピータのＩＰアドレスを含む１つのグループを意味する。
【００９２】
リンク・コストという用語は、２つのグループの間でデータを伝送するための統計的に決定されたコストを意味する。ここでの好適な実現例では、これは、それらの間のそれぞれの経路に沿ったリンクのコストの総和の最小値である。ここで第１に考察しているリンク・コストは、グループとリピータ・グループとの間のリンク・コストである。
【００９３】
相対リンク・コストという用語は、あるグループから任意のリピータ・グループへのリンク・コストの最小値をリピータ・グループへの各リンク・コストから減算することによって計算される、同じグループに対する他のリンク・コストに対するリンク・コストを意味する。
【００９４】
コスト・セットという用語は、最良リピータの選択に関して同等なグループの組を意味する。すなわち、使用できる情報が与えられると、同じリピータが、その中のどれに対しても選択されることになる。
【００９５】
ネットマップ手順では、まず、入力ファイルを処理して、グループ・レジストリと称される内部データベースを作成する。これらの入力ファイルは、グループ、グループの中のＩＰアドレス、グループの間のリンクを記述しており、例えば、公的に入手可能なインターネット・ルーティング・レジストリ（ＩＲＲ）データベース、ＢＧＰルータ・テーブル、インターネットの周囲の様々な地点にあり公的に入手可能なツール（トレースルート（traceroute）など）を用いてデータ経路をサンプリングするプローブ・サービスなど様々なソースを含んでいる。この処理が終了すると、グループ・レジストリは、それ以後の処理に用いられる本質的な情報を含むことになる。すなわち、（１）各グループの識別子、（２）与えられたグループにおけるＩＰアドレスの組、（３）情報が移動する経路を指示するグループの間のリンクの存在、（４）データを与えられたリンクを介して送るコスト、である。
【００９６】
次に、グループ・レジストリ・ファイルに対して、以下のプロセスが実行される。
リピータ・グループのリンク・コストの計算
ネットマップ手順では、各リピータ・グループとグループ・レジストリの中の各グループとの間のデータ伝送に対する「リンク・コスト」が計算される。この全体のリンク・コストは、２つのグループの間の任意の経路の最小コストとして定義されており、ただし、１つの経路のコストは、その経路における個々のリンクのコストの総和に等しい。以下に掲げるリンク・コスト・アルゴリズムは、#562 from ACM Journal Transactions on Mathematical Software: 「Shortest Path from a Specific Node to All Other Nodes in a Network」 by U. Pipe, ACM TOMS 5 (1980) pp. 450-455, http://www.netlib.org/toms/562のアルゴリズムと本質的に同一である。
【００９７】
この処理では、リピータ・グループという用語は、リピータのＩＰアドレスを含むグループを意味している。グループ・レジストリが２つのグループの間にリンクが存在しないことを指示している場合には、あるグループは、別のグループに隣接している。
【００９８】
各ターゲット・リピータ・グループＴに対して、
・Ｔとそれ自身との間のリンク・コストをゼロに初期化する。
・Ｔと１つおきのグループとの間のリンク・コストを無限大に初期化する。
【００９９】
・ターゲット・リピータ・グループＴから等しい距離にあるグループを含むリストＬを作成する。
・リストＬを初期化して、ターゲット・リピータ・グループＴ自身だけを含むようにする。
【０１００】
・リストＬが空ではないときには、
・リストＬのメンバーに隣接するものから構成される空のリストＬ’を作成する。
・リストＬの中の各グループＧに対して、・前記Ｇに隣接する各グループＮに対して、
・コストとは、ＴとＧとの間のリンク・コストと、ＧとＮとの間のリンク・コストとの和を意味するものとする。
【０１０１】
ＴとＧとの間のコストは、アルゴリズムの先行する工程において決定されている。ＧとＮとの間のリンク・コストは、グループ・レジストリから得られる。
・コストがＴとＮとの間のリンク・コストよりも小さい場合には、
・ＴとＮとの間のリンク・コストを、コストと設定する。
【０１０２】
・まだ加算されていない場合には、ＮをＬ’に加える。
・ＬをＬ’に設定する。
コスト・セットの計算
コスト・セットとは、最良のリピータ選択という点で同等であるグループの組である。すなわち、使用可能な情報が与えられた場合に、それらの任意のものに対して、同じリピータが選択されることになる。
【０１０３】
グループＧの「コスト・プロファイル」とは、この出願では、Ｇと各リピータとの間のコストの組と定義される。一方のプロファイルにおける値が他方のプロファイルにおける対応する値と一定量だけ異なる場合には、２つのコスト・プロファイルは、等しいと称される。
【０１０４】
あるクライアント・グループが知られている場合には、最良リピータ選択のアルゴリズムは、グループに関する情報に対するコスト・プロファイルに依存する。２つのコスト・プロファイルが等しい場合には、ＢＲＳアルゴリズムは、与えられているいずれのプロファイルに対しても、同じリピータを選択する。
【０１０５】
次に、コスト・セットは、等しいコスト・プロファイルを有するグループの組である。
この方法の有効性は、例えば、１つのリピータからグループＡに至るすべての経路が他のグループＢを通過するような場合に理解することができる。これらの２つのグループは、等しいコスト・プロファイルを有している。その理由は、グループＡに対して最良であるリピータは、どのようなものであっても、２つのグループの間にどのような経路を設けるかとは無関係に、グループＢにとっても最良となるからである。
【０１０６】
コスト・プロファイルを正規化することによって、等しいコスト・プロファイルを同一にすることができる。正規化されたコスト・プロファイルとは、最小のコストの値がゼロであるようなコスト・プロファイルである。正規化されたコスト・プロファイルは、そのプロファイルにおける最小のコストを見つけて、その値をプロファイルにおける各コストから減算することによって計算される。
【０１０７】
次のアルゴリズムを用いて、コスト・セットが計算される。
・各グループＧに対して、
・Ｇに対する正規化されたコスト・プロファイルを計算する。
【０１０８】
・正規化されたコスト・プロファイルが同じコスト・セットを探す。
・そのようなセットが見つかった場合には、既存のコスト・セットにＧを加算する。
・見つからない場合には、Ｇだけを含む計算された正規化されたコスト・プロファイルを有する新たなコスト・セットを作成する。
【０１０９】
コスト・セットを見つけるアルゴリズムでは、ハッシュ・テーブル（hash table）を用いて、所望のコスト・セットが既に存在しているかどうかを判断するために要する時間を短縮する。ハッシュ・テーブルは、Ｇのコスト・プロファイルから計算されたハッシュ値を用いる。
【０１１０】
次に、各コスト・セットには、一意的なコスト・セット・インデクス番号が付せられる。そして、コスト・セットを直接的な方法で用いることによって、リンク・コスト・テーブルを発生させる。このテーブルは、各コスト・セットから各リピータマスタ・デバイスのコストを与えてくれる。
【０１１１】
次に述べるように、グループ縮小テーブルは、すべてのＩＰアドレスをこれらのコスト・セットの中の１つに写像（マップ）する。
ＩＰマップの構築
ＩＰマップは、ＩＰアドレスのレンジをリンク・コスト・テーブル・キーに写像する記録から構成されるソートされたリストである。ＩＰマップのフォーマットは、次の通りである。
<base IP address><max IP address><Link Cost Table key>
ここで、ＩＰアドレスは、現在は、３２ビットの整数によって表される。エントリは、ベース・アドレスを下降し、等しいベース・アドレスの間では最大のアドレスを上昇し、等しいベース・アドレス及び最大アドレスの間ではリンク・コスト・テーブル・キーを上昇することによって、ソートがなされる。レンジは重複しうることに注意すべきである。
【０１１２】
ネットマップ手順は、以下のようにして、ＩＰアドレス・レンジとコスト・セット番号との間の写像を含む中間（intermediate）ＩＰマップを発生させる。
・各コスト・セットＳに対して、
・Ｓにおける各ＩＰアドレス・レンジに対して、
・Ｇにおける各ＩＰアドレス・レンジに対して、
・（低いアドレス、高いアドレス、Ｓのコスト・セット番号）というトリプルをＩＰマップに加算する。
【０１１３】
次に、ＩＰマップ・ファイルが、ベース・アドレスを下降し、等しいベース・アドレスの間では最大のアドレスを上昇し、等しいベース・アドレス及び最大アドレスの間ではコスト・セット番号を上昇することによって、ソートがなされる。ベース・アドレス及び最大アドレスのためのソートの順序によって、グループ縮小テーブルを構築して重なり合うエントリに対する適切な結果を生じさせるための時間が最小化される。
【０１１４】
最後に、ネットマップ手順は、ソートされたＩＰマップを処理することによって、グループ縮小テーブルを生じさせる。グループ縮小テーブルは、ＩＰアドレス（レンジによって特定される）をコスト・セット番号の中に写像する。ＩＰマップ・ファイルの特別な処理が、重なり合っているアドレス・レンジを検出し、隣接するアドレス・レンジを合併してグループ縮小テーブルのサイズを最小化するのに、必要となる。
【０１１５】
アドレス・レンジ・セグメントの順序付きのリストが維持され、各セグメントは、ベース・アドレスＢとコスト・セット番号Ｎとから構成され、ベース・アドレスＢによってソートされている。（セグメントの最大アドレスは、次のセグメントのベース・アドレスから１を減じた値である。）
次のアルゴリズムが用いられる。
【０１１６】
・要素[-infinity((), NOGROUP],[+infinity((), NOGROUP]を有するリストを初期化する。
・ソートされた順序で(b,m,s)から構成されるＩＰマップにおける各エントリに対して、
・(b,m,s)を、リストに挿入する（ＩＰマップ・エントリは、形式（低いアドレス、高いアドレス、Ｓのコスト・セット番号）を有していることに注意すべき）
・予約されたＬＡＮアドレス・レンジ(b,m)のそれぞれに対して、
・(b,m,LOCAL)をリストに挿入する。
【０１１７】
・アドレスaにおける各リピータに対して、
・リストに(a, a, REPEATER)を挿入する。
・順序付きのリストにおける各セグメントＳに対して、
・Ｓを同じコスト・セットを有するそれ以降のセグメントと合併させる。
【０１１８】
・Ｓのベース・アドレスからのベース・アドレスを用いてグループ縮小テーブル・エントリを作成する。
・最大アドレス＝次のセグメントのベースから１を減算した値
・グループＩＤ＝Ｓのコスト・セット番号
予約されたＬＡＮアドレス・レンジは、地球規模のインターネット・アドレスとしては現れることはないＬＡＮによって用いられるように予約されたアドレス・レンジである。LOCALというのは、他のどれとも異なっている特別のコスト・セット・インデクスであり、レンジが、決して反射されてはならないクライアントへ写像されることを示している。REPEATERは、他のどれとも異なっている特別のコスト・セット・インデクスであり、アドレス・レンジが、リピータへ写像されることを示している。NOGROUPは、他のどれとも異なっている特別のコスト・セット・インデクスであり、アドレスのこのレンジが、既知の写像を有していないことを示している。
【０１１９】
(B,M,N)が与えられると、エントリを、次のようにして順序の付いたアドレス・リストに挿入する。
ABがB以下であるような最後のセグメント(AB,AN)を見つける。
【０１２０】
ABがBよりも小さい場合には、(AB,AN)の後に新たなセグメント（B,N）を挿入する。
YBがM以下であるような最後のセグメント(YB,YN)を見つける。
XBがBよりも大きくYBよりも小さいような任意のセグメント(XB,NOGROUP)を、(XB,N)と交換する。
【０１２１】
YNがNでなく、YNがNOGROUPか、又はYBがB以下である場合には、
(ZB,ZN)を(YB,YN)の次のセグメントとする。
M+1がZBよりも小さい場合には、(ZB,ZN)の前に新たなセグメント(M+1,YN)を挿入する。
【０１２２】
(YB,YN)を(YB,N)と交換する。
HTMLリソースの書き換え
図３（Ｂ５）を参照しながら既に説明したように、リフレクタ又はリピータが、それ自身でリソース識別子（例えば、HTMLリソース）を含むリソースを与えるときには、そのリソースは、リソースに現れる反復可能なリソースのリソース識別子（URL）を予め反射するように修正（書き換え）られる。書き得ることによって、ブラウザは、リクエストされたリソースによって識別される反復可能なリソースをリクエストするときには、起点サーバまで戻らずに、それをリピータから取得することができる。しかし、リクエストされたリソースによって識別される反復不可能なリソースをリクエストするときには、起点サーバまで直接行くことになる。この最適化がない場合には、ブラウザは、起点サーバにおいてすべてのリクエストを作成する（起点サーバにおけるトラフィックを増加させ、起点サーバからのはるかに多くの再方向付けを必要とする）か、又は、リピータにおいてすべてのリクエストを作成する（このために、リピータが、キャッシュされることが不可能であったリソースを冗長的にリクエストし、コピーすることによって、そのリソースを提供するオーバヘッドを増加させる）ことになる。
【０１２３】
書き換えによって、リピータが選択されていることが要求される（最良リピータ選択との関係で上述した）。書き換えには、いわゆるBASEディレクティブが用いられる。BASEディレクティブによって、HTMLが別のベース・サーバを識別することが可能になる。（ベース・アドレスは、通常は、HTMLリソースのアドレスである。）
書き換え（rewriting）は、次のように実行される。
【０１２４】
Ｆ１．BASEディレクティブが、HTMLリソースの最初に加えられるか、又は、必要に応じて修正される。通常は、ブラウザは、相対的なURLをデフォルトのベース・アドレス、すなわち、遭遇するHTMLリソース（ページ）のURLに対するものと解釈する。加えられたBASEアドレスは、元々リソースを与えたリフレクタにおいて、リソースを特定する。これは、処理されていない相対的なURL（JavascriptTMプログラムによって発生されるものなど）は、リフレクタに対するものと解釈されることになる。このBASEアドレスがない場合には、ブラウザは、相対的なアドレスをリピータ名と組み合わせて、リピータによって要求される形式を有さないURLが得られることになる（既にステップＤ１において説明した）。
【０１２５】
Ｆ２．書き換え手段（rewriter）は、埋め込まれたイメージやアンカーなど、URLを含むディレクティブを識別する。書き換え手段は、リフレクタにおいて動作している場合には、これらのディレクティブを識別するためには、HTMLファイルをパージングする必要がある。リピータにおいて動作している場合には、書き換え手段は、各URLの位置を識別する予め計算された情報（ステップＦ４におけるHTMLファイルの中に存在する）にアクセスしうる。
【０１２６】
Ｆ３．書き換えるべきリソースにおいて遭遇される各URLに対しては、書き換え手段は、URLが反復可能であるかどうかを判断しなければならない（ステップＢ１−Ｂ２におけるように）。URLは、反復可能でない場合には、修正されない。他方で、URLは、反復可能である場合には、修正されて選択されたリピータを意味することになる。
【０１２７】
Ｆ４．すべてのURLが識別及び修正された後で、リソースがリピータに与えられる場合には、テーブルが、そのリソースにおいて遭遇される各URLの位置及びコンテンツを識別するリソースの最初に追加される。（このステップは、リピータにおけるHTMLリソースのパージングを不要とする最適化である。）
Ｆ５．いったんすべての変化が識別されると、新たな長さがリソース（ページ）に対して計算される。この長さは、リソースの処理に先だって、HTMLヘッダに挿入される。
【０１２８】
XMLとして知られているHTMLの拡張が、現在、開発されている。URLの書き換えプロセスは、XMLの場合と類似しており、リソースをパージングし埋め込まれたURLを識別する機構にいくらかの差異が存在する。
HTMLでないプロトコルの処理
本発明は、HTMLとは異なるプロトコル、例えば、ファイル・トランスファ・プロトコル（FTP）やオーディオ／ビデオ・ストリーム・プロトコルなどのプロトコルによって処理されるリソースへの参照（reference）を反映することも可能としている。しかし、多くのプロトコルは、リクエストの再方向付けを行う能力を備えていない。しかし、HTMLページに埋め込まれたURLを書き換えることによって、リクエストが実際に行われる前に、参照を再方向付けすることは可能である。上述のアルゴリズムへの以下の修正は、この性能をサポートするのに用いられる。
【０１２９】
Ｆ４では、サーバが協動して動作している起点サーバ、すなわち、いわゆるコサーバ（co-server）の構成可能なテーブルに現れる場合には、書き換え手段は、それらのサーバに対する書き換えを行う。リフレクタ・オペレータは、このテーブルを、FTPサーバ及びそれ以外のサーバを含むように定義することができる。HTMLでないリソースを参照する書き換えられたURLは、次のような形式を有する。
http://<repeater>/<origin server>@proxy=<scheme>[:<type>]@/resource
ここで、<scheme>というのは、ftpなどのサポートされたプロトコル名である。URLフォーマットは、Ｂ３に示されている形式に代わるものである。
【０１３０】
Ｃ３では、リピータは、到着するリクエストの中に埋め込まれたプロトコルを探す。プロトコルが存在し、リクエストされたリソースがまだキャッシュしていない場合には、リピータは、デフォルトのHTMLプロトコルの代わりに選択されたプロトコルを用いて、それを処理しキャッシュの中に記憶するときにリソースをリクエストする。
システムの構成及び管理
以上で述べた処理に加えて、リピータ・ネットワークは、システム構成及びネットワーク管理のための様々な機構を要求する。これらの機構のいくつかを次に述べる。
【０１３１】
リフレクタのために、そのオペレータは、パブリッシング（公開）動作を実行することによってリピータ・キャッシュを同期させることができる。リピータ・キャッシュを同期状態に維持するプロセスは、以下で説明される。パブリッシングは、リソース又はリソースの集合に変化があったことを示す。
【０１３２】
リピータ及びリフレクタは、様々なタイプのログ処理に参加する。リピータにおいて収集されたログの結果は、収集され、リフレクタにおいて収集されたログと合併される。これについても以下で説明する。
サブスクライバのリピータ・ネットワークへの追加
新たなサブスクライバがネットワークに追加されるときには、サブスクライバに関する情報が、マスタ・リピータにおいてサブスクライバ・テーブルに入れられ、ネットワークの中のすべてのリピータまで運ばれる。この情報には、サブスクライバに属するサーバに対する関係集合体情報率（Committed Aggregate Information rate = CAIR）と、サブスクライバに属するサーバによって用いられうるリピータのリストとが含まれる。
リフレクタのリピータ・ネットワークへの追加
新たなリフレクタは、ネットワークに追加されると、好ましくは、リピータのサブスクライバ識別子を含む安全に暗号化された証明を用いて、単にそれ自身をコンタクト・リピータに接続させ、それ自身をコンタクト・リピータに対して公表する。
【０１３３】
コンタクト・リピータは、リフレクタ・ネットワーク・アドレスがこのサブスクライバに対して許可されているかどうかを判断する。許可されている場合には、コンタクト・リピータは、接続を受け入れ、すべての必要なテーブルを用いてリフレクタを更新する（どのテーブルが更新されていないかは、バーション番号を用いて判断する）。
【０１３４】
リフレクタは、この時間の間にリクエストを処理するが、そのテーブルがすべて現在のものになるまで、イネーブルされない（リクエストを反射することを許可されない）。
リピータ・キャッシュの同期状態での保持
リピータ・キャッシュは、リソースへの変化はリフレクタによって識別され、すべてのリピータ・キャッシュに告知がなされ、単一のトランザクションにおいてその変化が受け入れられるという意味で、コヒーレントである。
【０１３５】
変化したリソースの識別子だけがリピータに送信され、その識別子が用いられて、リピータにおける対応するキャッシュされているリソースが効果的に無効化される。このプロセスは、変化のあったリソースのコンテンツを各リピータにブロードキャストするよりも、はるかに効率的である。
【０１３６】
リピータは、次にリクエストを受けたときに、新たに修正されたリソースをロードする。
リソースの変化は、リフレクタにおいて、オペレータによって手動で、又は、ファイルがサーバにインストールされるときにスクリプトによって、又は、変化検出機構（例えば、規則的に変化をチェックする別個のプロセスなど）を介して自動的に、識別される。
【０１３７】
リソースの変化により、リフレクタは、「無効化」メッセージをそのコンタクト・リピータに送り、コンタクト・リピータは、メッセージをマスタ・リピータに送る。この無効化メッセージには、変化の生じたリソース識別子（又は、リソース識別子のパターンを識別する正規表現）のリストが含まれている。（正規表現を用いて、ディレクトリやサーバ全体が無効化される。）リピータ・ネットワークは、２フェーズのコミット・プロセスを用いて、すべてのリピータが与えられたリソースを正確に無効化することが保証される。
【０１３８】
無効化プロセスは、次のようにして行われる。
マスタが、フェーズ１の無効化リクエストをすべてのリピータにブロードキャストして、無効化されるべきリソースの組を記述するリソース及び正規表現を指示する。
【０１３９】
各リピータは、フェーズ１のメッセージを受け取ると、まず、リソース識別子又は正規表現を、無効化まで、リソース識別子のリストの中に配置する。
進行している無効化リストの中にある任意のリクエストを受けているリソースは、キャッシュから与えられることはできない。これによって、キャッシュが、無効化の告知を受けていないピア・キャッシュからリソースをリクエストすることが回避される。このようにしてリソースがリクエストされる場合には、新たに無効化されたリソースを、同じであるが現時点では既に古くなったデータと交換することができる。
【０１４０】
次に、リピータは、そのキャッシュの中の各リソースのリソース識別子を、リストの中のリソース識別子及び正規表現と比較する。
それぞれの一致は、それに古いというマークを付しキャッシュからオプションで削除することによって、無効化される。これは、そのリソースに対する将来のリクエストによって、リフレクタからリソースの新たなコピーが検索されることを意味する。
【０１４１】
リピータは、無効化を完了すると、肯定応答をマスタに返送する。マスタは、すべてのリピータが無効化リクエストに対する肯定応答を与えるまで待機する。
リピータは、与えられた期間内に肯定応答をしない場合には、マスタ・リピータから切断される。再度接続されるときには、そのキャッシュの全体を消去するように命じられるので、一貫性の問題は生じないことになる。（キャッシュ全体の消去を回避するために、マスタは、実行されたすべての無効化のログを、日付ごとにソートされた形態で保持し、再度接続されたリピータが成功裡に無効化を終了した最後の時以後に無効化されたファイルだけを消去することもできる。現に考察している好適実施例では、リピータが切断されることはめったにないと考えられるので、このような動作は行われていない。）
すべてのリピータが無効化を肯定応答（又は、タイムアウト）すると、リピータは、すべてのリピータにフェーズ２の無効化リクエストをブロードキャストする。これによって、リピータは、対応するリソース識別子と正規表現とを無効化までリストから削除する。
【０１４２】
別の実施例では、無効化リクエストは拡張されて、「サーバ・プッシュ」が許容される。そのリクエストにおいては、無効化プロセスのフェーズ２が終了した後で、無効化リクエストを受け取っているリピータは、直ちに、無効化されたリソースの新たなコピーがそのキャッシュの中に配置されることを要求する。
ログ及びログ処理
ウェブ・サーバの活動ログは、ウェブ・サイトにおける活動をモニタする際に基本的である。本発明は、リフレクタにおける活動をリピータにおける活動と組み合わせることによって作成される合併ログを用い、それによって、単一の活動ログが起点サーバにおいて得られて、このログが任意のリピータにおいてそのサイトに代わって行われたすべてのウェブ・リソースのリクエストを示す。
【０１４３】
この合併されたログは、標準的な処理ツールによって、あたかもローカルに発生されたかのように処理することができる。
周期的な間隔で、マスタ・リピータ（又は、その代理のもの）が、各リピータからログを収集する。収集されたログは合併され、リソース識別子とタイムスタンプとによってソートされ、リフレクタごとに日付付きのファイルに記憶される。あるリフレクタに対する合併されたログは、そのリフレクタの代理をするすべてのリピータの活動を表している。周期的に、リフレクタのオペレータによって構成されるように、リフレクタは、マスタ・リピータに接触して、その合併されたログをリクエストする。そして、それらのログをダウンロードし、リフレクタ自身がローカルに維持しているログと合併させ、タイムスタンプを用いてソートする。結果は、リピータと当該リフレクタとに代わるすべての活動を表現する合併されたログである。
【０１４４】
活動ログは、リフレクタがリフレクタのオペレータによってそうするように構成されている場合には、リピータ・ネットワークにとって重要な情報を用いてオプションで拡張されることがある。特に、「拡張されたステータス・コード」は、次のようなそれぞれのリクエストに関する情報を指示している。
【０１４５】
１．リクエストがリフレクタによってローカルに処理された。
２．リクエストは、リピータに反射された。＊
３．リクエストは、リフレクタによって、リピータに与えられた。＊
４．複製可能でないリソースに対するリクエストがリピータによって与えられた。＊
５．リクエストがリピータによってキャッシュから与えられた。
【０１４６】
６．リクエストがキャッシュを満たした後でリピータによって与えられた。
７．無効化を求めるリクエストがリピータによって与えられた。
（＊の付された活動は、リクエストの中間的な状態を表し、通常は、最終的な活動ログには現れない。）
更に、活動ログは、継続時間と、拡張された正確なタイムスタンプとを含む。継続時間のために、リソースを処理するのに必要な時間と、用いられた帯域幅と、与えられた時間においてパラレルに処理されたリクエストの数と、それ以外の極めて有用な情報とを解析することが可能になる。拡張された正確なタイムスタンプによって、活動ログを正確に合体させることが可能となる。
【０１４７】
リピータは、ネットワーク・タイム・プロトコル（ＮＴＰ）を用いて同期のとれているクロックを維持する。リフレクタは、ＮＴＰを用いるか、時間バイアスを計算して、そのコンタクト・リピータに関するほぼ正確なタイムスタンプを提供することができる。
関係する集合体情報率の強制
リピータ・ネットワークは、すべてのリピータによって与えられたサブスクライバに代わって処理される集合体率（aggregate rate）をモニタして制限する。この機構は、次の利点を有している。
【０１４８】
１．リピータ・サービスに価格を付ける手段を提供する。
２．リピータにおける容量を評価して予約する手段を提供する。
３．込み合っているサイトのクライアントが他のサイトへのアクセスを制限することを防止する手段を提供する。
【０１４９】
それぞれのサブスクライバにとっては、「スレショルド集合体情報率（TAIR）」は、マスタ・リピータにおいて構築され維持される。このスレショルドは、コミット比率とは必ずしも限らず、価格付けの方針によって、複数のコミット比率である場合もありうる。
【０１５０】
各リピータが、リソースを与えるそれぞれのリフレクタの情報比率成分を、リクエストが運ばれるごとにそのリフレクタに代わって送信されるバイト数を記録することによって、周期的に（典型的には、１分間に約１回）測定する。このようにして作られたテーブルは、１周期ごとに１回マスタ・リピータに送られる。マスタ・リピータは、それぞれのリピータからのテーブルを統合して、そのリフレクタのためにリソースを提供するすべてのリピータに関して各リピータの測定された情報を加算し、各リフレクタに対する「測定された集合体情報比率（MAIR）」を決定する。
【０１５１】
あるリフレクタに対するMAIRがそのリフレクタに対するTAIRよりも大きい場合には、MAIRは、マスタによって、すべてのリピータと対応するリフレクタとに送信される。
リフレクタは、リクエストを受け取ると、最も近い時点で計算されたMAIRがそのTAIRよりも大きいかどうかを判断する。大きい場合には、リフレクタは、リクエストをローカルに処理することによって（Ｂ２において）、反射を抑制すべきかどうかを確率的に決定する。反射を抑制する確率は、MAIRとCAIRとの差の指数関数として増加する。
【０１５２】
ピーク周期の間にリクエストをローカルに処理すると、ローカルな起点サーバに負担を与えることになるが、このサブスクライバが共有されているリピータ・ネットワークからの配分された帯域幅よりも多くを取ることを防止できる。
【０１５３】
リピータは、与えられたサブスクライバに対するリクエストを受け取ると（Ｃ２において）、サブスクライバがスレショルド集合体情報比率の近くで動作しているかどうかを判断する。そうであるならば、リピータは、リクエストを再方向付けしてリフレクタに戻すことによって、その負荷を減少させるべきかどうかを確率的に決定する。この確率は、リフレクタの集合体情報比率がその限度に近づくにつれて、指数的に増加する。
【０１５４】
リクエストがリフレクタに反射されて戻されると、特別のキャラクタ・ストリングがリソース識別子に付属されることによって、受け取っている側のリフレクタは、それを再度反射させることを試みることはない。現在のシステムでは、このストリングは、次のような形式を有している。
Src=overload
リフレクタは、このストリングの試験をＢ２で行う。
【０１５５】
上述した集合体情報比率を制限する機構は、かなり粗いものである。この機構は、クライアントとのセッションのレベルで、そして、最良でも、リソースへの個々のリクエストのレベルでの制限を行う（クライアントはいったん与えられたリピータに向かって反射されているので、書き換えプロセスは、そのリピータに帰ってくるクライアントを保持するような傾向にある）。リピータにおいてTAIRの限度を強制する、より目の細かい（more fine-grained）機構は、他のサブスクライバが帯域幅を求めて競合しているときに、多忙なサブスクライバの帯域幅消費を減少させるように動作する。
【０１５６】
目の細かい機構は、データ「速度形成」の形式である。これによって、応答がクライアントに送られているときに、リソース・データを接続にコピーする機構が拡張される。出力チャネルがリクエストが受信されたときに確立されると、リピータは、チャネルはどのサブスクライバのために動作しているのかをＣ２で識別し、また、チャネルと関連するデータ・フィールドにサブスクライバを記録する。「書き込み」動作がチャネルに対してなされるたびに、Metcred出力システムは、最初に、与えられたサブスクライバに対して上で計算されたMAIR及びTAIRの現在の値を検査する。MAIRがTAIRよりも大きい場合には、この機構は、書き込み動作を実行する前に、しばらく停止する。この停止時間の長さは、MAIRがTAIRを超える大きさに比例する。この停止時間によって、他のリソースを他のクライアントにおそらくは他のサブスクライバに代わって送るというタスクがそのようなデータを送る機会を有する。
リピータ・ネットワークの弾性
リピータ・ネットワークは、リピータ又はネットワーク接続が故障するときに回復する能力を有している。
【０１５７】
リピータは、マスタ・リピータに接続されていない限り、動作することはできない。マスタ・リピータは、他のリピータと、リピータの負荷、集合体情報比、サブスクライバ及びリンク・コストを含む重要な情報を交換している。
【０１５８】
マスタが故障すると、「継続」プロセスによって、他のリピータがマスタの役割をマスタに代わって行い、ネットワークの全体が動作状態に維持されることが保証される。マスタが故障し、又は、マスタへの接続がネットワークの問題によって故障する場合には、そのマスタとの通信を試みている任意のリピータが、TCP/IPからの指示によって、又は、それがマスタに送った規則的な「心拍」メッセージからタイムアウトすることによって、その故障を見つけることができる。
【０１５９】
任意のリピータは、そのマスタから切断されるときには、その「継続リスト」と称される構成可能なファイルに基づいて一連の潜在的なマスタへの再接続を試みる。
リピータは、マスタへの接続に成功するまで、継続して、リスト上の各システムを試す。このプロセスにおいて、それ自身の名前に至る場合には、マスタの役割を代行して、他のリピータからの接続を受け入れる。リストの最上部にはないリピータがマスタになる場合には、「一時的なマスタ」を称されている。
【０１６０】
ネットワーク分割は、リピータの２つのグループのそれぞれにマスタを選択させることになる。分割が訂正されると、年上の方のマスタがネットワークを担当することが必要である。従って、リピータは、一時的なマスタであるときには、継続リストにおいてそれ自身よりも上位にある任意のマスタへの再接続を規則的に試みる。成功する場合には、それに接続されているすべてのリピータから直ちに切断する。継続リストを再度試みる時には、より年上のマスタ・リピータに接続する。
【０１６１】
データの損失を回避するために、一時的マスタは、構成上の変更を受け入れず、ログ・ファイルの処理も行わない。これらのタスクを行うためには、その継続リストを手動で修正することによって、それ自身が基本マスタであるとの告知を受けなければならない。各リピータは、その継続リストを定期的にリロードして、誰がマスタであるのかに関するその考えを変更すべきかどうかを決定する。
【０１６２】
リピータは、マスタから切断される場合には、マスタに再接続するときにそのキャッシュを再び同期させなければならない。マスタは、最近のキャッシュの無効化のリストを維持し、リピータに、切断されていたので処理することができなかったすべての無効化を送ることができる。このリストが何らかあの理由で使用できない場合には（例えば、リフレクタがあまりに長い時間切断されていたなど）、リフレクタは、そのキャッシュの全体を無効化しなければならない。
【０１６３】
リフレクタは、リピータに接続されていなければ、リクエストを反射することを許されない。リフレクタは、負荷及びリンク・コスト・テーブル、現在の集合体情報率などの重要な情報に関しては、そのコンタクト・リピータに依存している。リピータに接続されていないリフレクタは、リクエストを継続的に受信してそれらをローカルに処理することができる。
【０１６４】
リフレクタは、リピータの故障やネットワークの障害のためにリピータとの接続を失う場合には、リピータへの接続を試みる限り、動作を継続する。
リフレクタは、リピータへの接続を試みるたびに、リピータ・ネットワークを表すドメイン・ネームが与えられると、ＤＮＳを用いて、１組の候補となるリピータを識別する。接触が成功するまでは、リフレクタは、すべてのリクエストをローカルに処理する。リフレクタがリピータに接続すると、リピータは、別のリピータへの接触のためにそれを告知することができる。これにより、リピータ・ネットワークは、どの個別的なリピータもあまりに多くのコンタクトを有することはないことを保証することができるようになる。
【０１６５】
接触がなされると、リフレクタは、そのテーブルのバージョン番号をそのコンタクト・リピータに提供する。そして、リピータは、どのテーブルが更新されるべきであるかを決めて、適切な更新をリフレクタに送る。すべてのテーブルの更新が終了すると、リピータは、リフレクタに、リクエストの反射をすることができることを告知する。
リピータ内部でのプロキシ・キャッシュの使用
リピータは、任意のプロキシ・キャッシュをその内部の成分として用いることができるように意図的に設計されている。これが可能である理由は、リピータがHTMLリクエストを受け取って、それらをプロキシ・キャッシュによって認識される形態に変換するからである。
【０１６６】
他方で、標準的なプロキシ・キャッシュへのいくつかの修正が、最適化としてなされている。これには、特に、リソースを便宜的に無効化する能力、キャッシュの割当て（quotas）をサポートする能力、プロキシ・キャッシュからピータを介してリクエスト側まで通過する際に各リソースの厳密なコピーを作成することを防止する能力などが含まれる。
【０１６７】
好適実施例では、プロキシ・キャッシュは、Ｃ３を実現するために用いられる。プロキシ・キャッシュは、１つ又は複数のリピータだけによって用いられるための専用である。プロキシ・キャッシュからリソースを要求する各リピータは、入ってくるリソース・リクエストからプロキシ・リクエストを構築する。サーバに対する通常のHTMLのGETリクエストは、URLの経路名の部分だけを含む。すなわち、スキームとサーバ名は、明らかになっていない。（リピータに対するHTML GETリクエストでは、URLの経路名部分には、リクエストが作られる起点サーバの名前が含まれる。これについては上述した。）しかし、プロキシ・エージェントであるGETリクエストは、URLの全体を取る。従って、リピータは、それが受け取るURLの経路部分から、URLの全体を含むプロキシ・リクエストを構築しなければならない。特に、入ってくるリクエストは、次のような形式を有する。
GET/<origin server>/<path>
そして、リピータは、次の形式のプロキシ・リクエストを構築する。
GET http://<origin server>/<path>
そして、入ってくるリクエストが
GET<origin server>@proxy=<scheme>:<type>@/<path>
という形式を有する場合には、リピータは、次の形式のプロキシ・リクエストを構築する。
GET <scheme>://<origin server>/<path>
キャッシュ制御
HTMLは、キャッシュ制御ディレクティブと称されるディレクティブを含み、このディレクティブは、キャッシュに、付属のリソースがキャッシュされうるかどうか、されうるのであれば、いつそれが失効するのかを指示するのに用いられる。ウェブ・サイトの管理者は、ウェブ・サイトと構築して、適切なディレクティブを付着させる。しばしば、管理者は、あるページがどのくらいの期間新鮮な状態でありうるのかを知らず、キャッシュが古くなったデータを処理するのを回避することを試みる短期の消滅時間を定義しなければならない。多くの場合には、ウェブ・サイトの管理者は、そうでなければキャッシュの存在によってマスクされてしまうことになるリクエスト（又は、ヒット）を受信するためだけの目的で、短期の消滅時間を指示する。これは、この分野では、キャッシュ・バスティング（cache-busting）として知られている。キャッシュのオペレータによってはキャッシュ・バスティングという表現は不適切であると考える場合もあるが、この情報に依存している広告業者はそれを不可避的であると考えている。
【０１６８】
リソースがリピータに記憶されると、そのキャッシュ・ディレクティブは、リピータによって無視される。その理由は、リピータは、明確な無効化イベントを受け取り、いつリソースが古くなるかを判断するからである。プロキシ・キャッシュがリピータにおけるキャッシュとして用いられるときには、関連するキャッシュ・ディレクティブは、一時的にディセーブルされる。しかし、これらのキャッシュ・ディレクティブは、リソースがキャッシュからクライアントへ与えられ、キャッシュ制御の方針（あらゆるキャッシュ・バスティングを含む）が効を奏すると、再度イネーブルされる。
【０１６９】
本発明は、リピータの内部のプロキシ・キャッシュがキャッシュ制御ディレクティブを受け取ることを回避させると同時にこれらのディレクティブがリピータから与えられることを許容する機構を含んでいる。
【０１７０】
リフレクタは、リソースをＢ４においてリピータに与えるときには、すべてのキャッシュ・ディレクティブを、リピータのプロキシ・キャッシュによって無視される修正されたディレクティブと交換する。これは、"wr-"などの明確なストリングをHTMLタグの最初に予め固定するしておくことによってなされる。従って、"expire"は"wr-expire"となり、"cache-control"は"wr-cache-control"となる。これによって、プロキシ・キャッシュ自体がディレクティブを受けることは回避される。リピータがＣ４においてリソースを与え、リクエストしている側のクライアントが別のリピータではないときには、"wr-"で始まるHTMLタグを探して、"wr-"を削除すればよい。こうすることにより、リソースを検索しているクライアントがディレクティブを受けることが可能となる。
リソースの再有効化
起点サーバがサービスを受けるたびに相談を受けている限りは、リソースがキャッシュされうるような場合がいくつか存在する。ある場合には、リソースに対するリクエストは、いわゆる「クッキー」に付着される。起点サーバには、リクエストを記録するクッキーが与えられなければならず、キャッシュされたリソースが与えられているのかそうでないのかかが、判断される。別の場合には、リソースに対するリクエストは、認証ヘッダ（ユーザＩＤ及びパスワードを用いてリクエストしているものを識別する）に付着される。リソースに対する新たなリクエストは、起点サーバにおいて試験されなければならず、それによって、リクエストしているものがリソースへのアクセスの認証を得ているのかどうかが確認される。
【０１７１】
HTML1.1の仕様では、"Must-Revalidate"（再有効化が必要）というタイトルの応答ヘッダが定義されている。これによって、起点サーバが、リクエストが受け取られるたびにプロキシ・キャッシュにリソースを再有効化するように命令することが可能となる。通常は、この機構は、リソースがまだ新鮮であるかどうかを判断するのに用いられる。本発明では、Must-Revalidateによって、起点サーバに、そうでなければリピータから与えられるリクエストを有効化するように依頼することが可能になっている。
【０１７２】
リフレクタのルール・ベースは、どのリソースが反復可能であるが与えられるたびに再有効化が必要であるかを判断する情報を含んでいる。そのようなリソースのそれぞれに対して、Ｂ４において、リフレクタは、Must-Revalidateのヘッダを付着させている。リクエストがMust-Revalidateというヘッダのマークが付いているキャッシュされたリソースを求めてリピータに来るたびに、そのリクエストは、リクエストされたリソースが与えられる前に有効化のためにリフレクタに送られる。
キャッシュ割当て（Cache Quotas）
リピータのキャッシュ成分は、クライアントを当該リピータに反射するサブスクライバの間で共有されている。サブスクライバが記憶装置に対して公平なアクセスをすることを可能にするために、キャッシュを、割当てをサポートするように拡張することができる。
【０１７３】
通常は、プロキシ・キャッシュは、ディスク空間スレショルドＴを用いて構築されている。Ｔバイトを超えるバイトがキャッシュに記憶されるときには常に、キャッシュは、消去すべきリソースを探そうと試みる。
【０１７４】
典型的には、キャッシュは、「最も遠い時点で用いられた（least-recently-used = LRU）」アルゴリズムを用いて、どのリソースを削除すべきかを判断する。より複雑なキャッシュでは、別のアルゴリズムも用いられる。キャッシュは、複数のスレショルド値をサポートしている。例えば、到達されると、優先順位の低い背景プロセスがキャッシュからアイテムを削除させるという下側（lower）のスレショルドや、到達されると、十分な空のディスク空間が確保されるまでリソースが削除されることを防止する上側（higher）のスレショルドなどである。
【０１７５】
２つのサブスクライバＡ及びＢがキャッシュを共有し、サブスクライバＡのリソースの方がサブスクライバＢのリソースよりもある時間間隔の間にはアクセスが多い場合には、新たなリクエストが到達するときには、Ｂのリソースの方が少なくキャッシュの中に存在するようになる。Ａの振る舞いのために、Ｂのリソースはリクエストされるときに決してキャッシュされていないことがありうる。本発明では、このような振る舞いは望ましくない。この問題に対応するために、本発明は、リピータにおけるキャッシュを拡張して、キャッシュ割当てをサポートしている。
【０１７６】
キャッシュは、各サブスクライバによって用いられる空間の量をＤSに記録し、各サブスクライバに対する構成可能なスレショルドＴSをサポートしている。
リソースがキャッシュに加えられるとき（Ｃ３において）は常に、値Ｄｓはリソースを提供するサブスクライバに対して更新される。ＤｓがＴｓより大きい場合、キャッシュは、サブスクライバＳに関連するそれらのリソースの中から、除去するリソースを発見するように試みる。キャッシュは、各サブスクライバに対して別々の領域に有効に分割する。
【０１７７】
元のスレッショルドＴは依然として維持される。各サブスクライバのために保持されていたセグメントの和がキャッシュに保持されていた全スペースよりも小さいとき、残りの領域は「共通」として、サブスクライバ間の競争に供される。
【０１７８】
この機構は、前述の存在するプロキシ・キャッシュを修正することによって実行されるか、プロキシ・キャッシュが少なくとも外部プログラムがキャッシュ内のリソースのリストを取得してキャッシュから所与のリソースを除去することを可能にする場合には、プロキシ・キャッシュを修正することなく実行可能となる、ことは注目される。
リピータからの書き換え
リピータがリソースに対するリクエストを受けると、そのプロキシ・キャッシュは、ピア・キャッシュが要求されたリソースを含むか否かを判定するように構成することができる。そうである場合、プロキシ・キャッシュは、ピア・キャッシュからそのリソースを取得する。それは、起点サーバ（リフレクタ）から取得するよりも早くすることができる。しかし、この結果、ピア・キャッシュから取り出された書き換えHTMLリソースは間違ったリピータを識別することになるであろう。従って、ピア・キャッシュを共働させることを可能にするために、リソースは、そのリピータにおいて書き換えられることが望ましい。
【０１７９】
リソースがリピータに対して書き換えられるとき、特別のタグがそのリソースの始めに配置される。リプライを構成するとき、リピータはそのタグを調べ、更なる書き換えが必要であることをそのリソースが示しているか否かを判定する。そうである場合、リピータは、古いリピータに対する参照を新しいリピータに対する参照を置換することによって、リソースを修正する。
【０１８０】
リソースが別のリピータのプロキシ・キャッシュに提供されるとき、この書き換えを実行することのみが必要になる。
リピータ・サイド・インクルード
起点サーバは各リクエストに対するカスタム・リソースを構成する場合がある（例えば、リクエストするクライアントの履歴に基づいて広告を挿入するとき）。そのような場合、そのリソースは、反復（再生）されるのではなくローカル的に提供されなければならない。一般的に、カスタム・リソースは、カスタム情報とともに、テキスト及び他の反復可能なリソースに対する参照を含んでいる。
【０１８１】
テキスト・リソース及びありうる１つ又は複数のイメージ・リソースからの「ページ」をアセンブルするプロセスは、HTMLによって向けられたウエブ・ブラウザによって実行される。しかし、HTMLを使用して、ブラウザにテキスト又は別個のリソースからのディレクティブを使用してページをアセンブルさせることは不可能である。従って、カスタム・リソースは、そうでなければ反復可能な大量の静的テキストを含むことを余儀なくされることが多い。
【０１８２】
このような生じうる非効率性を解消するために、リピータは、「リピータ・サイド・インクルード(repeater side include)」と呼ばれる特別のディレクティブを認識する。このディレクティブは、反復可能なリソースとローカル・リソースの組合せを使用して、リピータがカスタム・リソースをアセンブルすることを可能にする。このようにして、静的テキストは反復可能にすることができ、そのためには特別のディレクティブをリフレクタによってローカル的に提供するだけでよいことになる。
【０１８３】
例えば、リソースＸは、大きなテキスト・アーティクルが続く広告バナーを選択するカスタム・ディレクティブから構成することが可能である。このリソースを反復可能にするためには、ウエブ・サイト管理者は、第２のリソース、Ｙを出してそのバナーを選択しなければならない。リソースＸは、そのアーティクルとともに、リソースＹを識別するリピータ・サイド・インクルード・ディレクティブを含むように修正しなければならない。リソースＹが作成され、アド（ａｄ）バナーを選択するカスタム・ディレクティブのみを含む。ここで、リソースＸは反復可能となり、比較的小さいリソースＹのみが反復可能でなくなる。
【０１８４】
リピータがリプライを構成するとき、提供されているリソースがHTMLリソースであるか否かを決定し、そうである場合、それをリピータ・サイド・インクルード・ディレクティブについて走査する。各ディレクティブは、URLを含み、それをリピータが解明し、そのディレクティブの場所に置き換える。リソース全体は、その最終的サイズを決定するために、それが提供される前にアセンブルされなければならない。それは、そのサイズがリソースの前のリプライ・ヘッダに含まれるからである。
【図面の簡単な説明】
【０１８５】
【図１】本発明によるネットワーク環境の一部を示している。
【図２】本発明の動作の流れ図である。
【図３】本発明の動作の流れ図である。
【図４】本発明の動作の流れ図である。
【図５】本発明の動作の流れ図である。
【図６】本発明の動作の流れ図である。
【図１】
2008090826.tif 000003
【図２】
2008090826.tif 000004
【図３】
2008090826.tif 000005
【図４】
2008090826.tif 000006
【図５】
2008090826.tif 000007
【図６】
2008090826.tif 000008