(57)【特許請求の範囲】
【請求項１】
プロキシ・キャッシュを選択する方法であって、
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成するステップと、
ＵＲＬのハッシュ値をアンカ・ハッシュ・パーティションにハッシュするステップと、
対応するアンカ・プロキシ・キャッシュを見つけるステップと、
前記プロキシＩＤアレイから付近の１つ以上のプロキシ・キャッシュを前記アンカ・プロキシ・キャッシュに加えることによってプロキシ・キャッシュ候補群を作成するステップと、
各ハッシュ・パーティションをプロキシ・キャッシュにマップするステップと、
少なくとも待ち時間の小さいものから前記候補群からプロキシ・キャッシュを選択するステップを含む、
方法。
【請求項２】
前記選択するステップは、少なくとも待ち時間が改善できるかを判断し、改善できる場合には、前記候補群からプロキシ・キャッシュを選択し、該プロキシ・キャッシュが過負荷か判断し、過負荷でなければ選択するステップを含む、請求項１記載の方法。
【請求項３】
前記マップするステップは、各ハッシュ・パーティションを１とＰとの間の数にハッシュするステップを含み、Ｐはプロキシ総数を表す、請求項１記載の方法。
【請求項４】
前記マップするステップは、
各プロキシについて、Ｎがハッシュ・パーティション総数、Ｐがプロキシ総数を表すとき、０と１との間のＮ／Ｐ個の乱数を生成するステップと、
生成されたＮ個の対応する乱数をソートすることによってプロキシ・リストを生成するステップと、
ソートされた前記プロキシ・リストをもとに各ハッシュ・パーティションを１つのプロキシに割当てるステップと、
を含む、請求項１記載の方法。
【請求項５】
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する前記ステップは、
共同プロキシ・キャッシュを持つプロキシＩＤアレイを作成するステップと、
各ハッシュ・パーティションを前記プロキシＩＤアレイのインデックスにマップするハッシュ・パーティション・セグメントを作成するステップと、
前記ハッシュ・パーティション・セグメントを所定回数複製するステップと、
を含む、請求項１記載の方法。
【請求項６】
プロキシ・キャッシュを選択する装置であって、
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する手段と、
ＵＲＬのハッシュ値をアンカ・ハッシュ・パーティションにハッシュする手段と、
対応するアンカ・プロキシ・キャッシュを見つける手段と、
前記プロキシＩＤアレイから付近の１つ以上のプロキシ・キャッシュを前記アンカ・プロキシ・キャッシュに加えることによってプロキシ・キャッシュ候補群を作成する手段と、
各ハッシュ・パーティションをプロキシ・キャッシュにマップする手段と、
少なくとも待ち時間の小さいものから前記候補群からプロキシ・キャッシュを選択する手段を含む、
装置。
【請求項７】
前記選択する手段は、少なくとも待ち時間が改善できるかを判断し、改善できる場合には、前記候補群からプロキシ・キャッシュを選択し、該プロキシ・キャッシュが過負荷か判断し、過負荷でなければ選択する手段を含む、請求項６記載の装置。
【請求項８】
前記マップする手段は、各ハッシュ・パーティションを１とＰとの間の数にハッシュする手段を含み、Ｐはプロキシ総数を表す、請求項６記載の装置。
【請求項９】
前記マップする手段は、
各プロキシについて、Ｎがハッシュ・パーティション総数、Ｐがプロキシ総数を表すとき、０と１との間のＮ／Ｐ個の乱数を生成する手段と、
生成されたＮ個の対応する乱数をソートすることによってプロキシ・リストを生成する手段と、
ソートされた前記プロキシ・リストをもとに各ハッシュ・パーティションを１つのプロキシに割当てる手段と、
を含む、請求項６記載の装置。
【請求項１０】
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する前記手段は、
共同プロキシ・キャッシュを持つプロキシＩＤアレイを作成する手段と、
各ハッシュ・パーティションを前記プロキシＩＤアレイのインデックスにマップするハッシュ・パーティション・セグメントを作成する手段と、
前記ハッシュ・パーティション・セグメントを所定回数複製する手段と、
を含む、請求項６記載の装置。
【請求項１１】
コンピュータに、プロキシ・キャッシュを選択させる、プログラムであって、該プログラムがコンピュータに、
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する機能と、
ＵＲＬのハッシュ値をアンカ・ハッシュ・パーティションにハッシュする機能と、
対応するアンカ・プロキシ・キャッシュを見つける機能と、
前記プロキシＩＤアレイから付近の１つ以上のプロキシ・キャッシュを前記アンカ・プロキシ・キャッシュに加えることによってプロキシ・キャッシュ候補群を作成する機能と、
各ハッシュ・パーティションをプロキシ・キャッシュにマップする機能と、
少なくとも待ち時間の小さいものから前記候補群からプロキシ・キャッシュを選択する機能を
実現させる、プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般には、クライアント・マシンとコンテンツ・サーバ間に位置するネットワーク・プロキシ・サーバ上のＷｅｂオブジェクトのキャッシングに関する。
【０００２】
【従来の技術】
近年、インターネット、特にＷｅｂ（World Wide Web）が急成長している。その結果、Ｗｅｂにアクセスするときのユーザ側の応答時間がますます問題になっている。
【０００３】
Ｗｅｂのパフォーマンスを上げる一般的方法は、クライアントとコンテンツ・サーバとの間にプロキシ・キャッシュ・サーバを配置することである。プロキシ・キャッシングでは、クライアント・リクエストのほとんどをプロキシ・キャッシュにより処理することができ、待ち時間が短縮される。インターネット上のネットワーク・トラフィックも、この方法により大幅に縮小することができ、ネットワークの混雑も大幅に緩和される。実際、ＩＢＭ、Sun Microsystems、Inktomi、Network Appliance、Akamai等、Ｗｅｂキャッシングのためのハードウェア、ソフトウェアの製品やソリューションを提供している企業は少なくない。こうした企業には、地理的に分散したデータセンターを共同Ｗｅｂキャッシングに使用している企業もある。すなわち、Ｗｅｂキャッシングを共同で行うため、地理的に分散した多数のプロキシを使用するケースが増えている。
【０００４】
Ｗｅｂキャッシングを共同で行うには、一般には調整役を務めるプロトコルが必要である。一連の共同プロキシ・キャッシュを管理調整するため、最近ハッシュ・ルーティングという方法が登場している。ハッシュ・ルーティングの例として、キャッシュ・アレイ・ルーティング・プロトコル（ＣＡＲＰ）、コンシステント・ハッシング（consistent hashing）等がある。"Cache Array Routing Protocol、v 1．0"（インターネット・ドラフト、http://www.ircache.net/Cache/ICP/carp.txt、１９９８年２月、V．Valloppillil、K．W．Ross）にＣＡＲＰのドラフトについての説明がある。"Hash-Routing for Collections Shared Web Caches"（IEEE Network Magazine、３７−４４ページ、１９９７年１１月、１２月、K．W．Ross）では、ＣＡＲＰ及び他のプロトコルのパフォーマンスが分析されている。"Web Caching with Consistent Hashing"（Proc．Of 8th International World Wide Web Conference、１２５−１３５ページ、１９９９年、D．Karger等）では、コンシステント・ハッシングのＷｅｂキャッシングへの応用が述べられている。
【０００５】
基本的にハッシングは、ＵＲＬスペース全体をキャッシュ間でパーティションに分け、１つの論理キャッシュを作成する。キャッシュはそれぞれ割当てられたパーティションに属するリクエストを賄う。リクエストは、対応するＵＲＬのハッシュ値をもとに対応するプロキシ・キャッシュに送られる。ハッシュ値とプロキシ・キャッシュＩＤのマッピングは、ブラウザによってか、またはドメイン・ネーム・サーバ（ＤＮＳ）によって行える。
【０００６】
地理的に分散したプロキシが共同Ｗｅｂキャッシングに使用される機会が増えている。例えば、Akamai、及びInktomi等の企業は、地理的に分散したデータ・センター上に存在するキャッシュ・サーバをＷｅｂキャッシングに使用している。その結果、地理的に遠いプロキシや過負荷状態にあるプロキシにハッシュされるリクエストについては、応答時間に影響が出る傾向がある。遠いプロキシは、ネットワーク待ち時間遅延が長くなる傾向がある。過負荷状態のプロキシは、たとえブラウザにどれほど近くても大きな遅延の原因にもなる。そのためユーザは、遠くのプロキシ・キャッシュや過負荷のプロキシ・キャッシュにハッシュされるＵＲＬリクエストについて、予想外に遅い応答時間を実感することがある。
【０００７】
【発明が解決しようとする課題】
共同Ｗｅｂキャッシングに対するハッシング・ベースの従来の方法は、ネットワーク待ち時間を考慮していない。地理的に遠いプロキシ・キャッシュへのハッシングまたは全プロキシ・キャッシュへのハッシュをネットワーク待ち時間に関わらず回避している。例えば、"Web Caching with Consistent Hashing"（Proc．Of 8th International World Wide Web Conference、１２５−１３５ページ、１９９９年）では、ユーザの地域がハッシュ値にエンコードされ、ブラウザによってその地域のＤＮＳに送られる。ＤＮＳはエンコードされたハッシュ値を同じ地域内のプロキシ・キャッシュＩＤにマップする。従ってリクエストは、地理的に近い領域にあるプロキシによってのみ処理される。これは、地域内のプロキシ・キャッシュが同じ地域内から発生したリクエストを全て適切に処理できる場合は十分効果的であるが、地域間で作業負荷に偏りがある場合、ある領域のプロキシは過負荷になり、他の領域のプロキシは負荷不足になることがある。その結果、プロキシ間の共同の程度が地理的条件によって制限される。
【０００８】
一方、リクエストは地理的条件にかかわらず、連携する全てのプロキシ・キャッシュに単純にハッシュすることができる。その場合、地理的に分散した連携するキャッシュ全ての間で負荷のバランスを取りやすくなる。ただし、地理的距離によるネットワーク待ち時間遅延は考慮されない。また"ホット・スポット"も考慮されない。"ホット・スポット"は、短時間の間に多大な需要、またはＷｅｂサイトやＷｅｂページにアクセスするユーザの数に関して短い"スパイク"があるＷｅｂサイトまたはＷｅｂページとして定義される。ホット・スポットが存在するとき、ホット・スポットへの参照は全て同じプロキシにハッシュされている。そのため、ホット・スポットを処理するプロキシはたちまち過負荷状態になる。
【０００９】
従って、ハッシング・ベースのＷｅｂキャッシングに伴う待ち時間の問題に配慮する必要がある。具体的には、地理的に分散したプロキシ・キャッシュ間の共同Ｗｅｂキャッシングに待ち時間に対応したハッシングを提供する必要がある。
【００１０】
【課題を解決するための手段】
少なくとも１つの本発明の好適な実施例に従って、共同Ｗｅｂキャッシングに関するハッシング・ベースの方法に伴う前記の待ち時間の問題が解決される。ここでは、地理的に分散したプロキシ・キャッシュ間で共同Ｗｅｂキャッシングを行うため、待ち時間に対応したハッシングのシステム及び方法を考慮する。
【００１１】
本発明の実施例では、ＵＲＬリクエストが全てのプロキシにハッシュされる。ただし、リクエストのターゲット・プロキシを選択する際、待ち時間遅延及び過負荷の可能性のあるプロキシを考慮する。本発明の実施例では、リクエストは最初にアンカ・ハッシュ・パーティションにハッシュされる。ハッシュ・パーティションはそれぞれ、地理的に分散したプロキシの１つにマップされる。次に、選択アルゴリズムにより、アンカ・ハッシュ・パーティションに隣接した少数のハッシュ・パーティションの中からプロキシが選択される。この選択は、ネットワーク待ち時間を短縮し、過負荷のプロキシの作成を避けることを基準にして行われる。
【００１２】
【発明の実施の形態】
図１は、本発明の実施例に従い、分散したプロキシ・キャッシュ間のＷｅｂキャッシングをサポートするネットワーク・システムを示す。クライアント・マシン１０１、１０２とコンテンツ・サーバ１０７、１０８との間のインターネットにプロキシ・キャッシュ・サーバ１０５、１０６が配置される。インターネットにはドメイン・ネーム・サーバ（ＤＮＳ）１０３、１０４もあり、論理ホスト名を物理ＩＰアドレスにマップするため使用される。コンテンツ・サーバ１０７、１０８と同様、プロキシ・キャッシュ１０５、１０６は通常、メイン・メモリとディスクを含む巨大なストレージ・スペースを持つ高性能サーバ・コンピュータ・システムである。例えばＩＢＭのＳＰ／２、ＲＳ／６０００サーバやＰＣサーバは、プロキシ・キャッシュ・サーバ、コンテンツ・サーバの両方として使用することができる。一方クライアント・マシン１０１、１０２は通常はＰＣまたはワークステーションである。
【００１３】
プロキシ・キャッシュ・サーバ、プロキシ・キャッシュ、プロキシ・サーバ、プロキシといった呼び名は、本発明の開示内容に関しては相互に置き換えられる用語として使用している。これらの用語は全てクライアント・マシン１０１、１０２とコンテンツ・サーバ１０７、１０８間のインターネット１００でＷｅｂオブジェクトをキャッシュするコンピュータ・システムを表す。それらの間でプロキシ・キャッシュ１０５、１０６を地理的に遠い場所に配置することができる。いくつかはローカル・クラスタ内に配置できる。ただし、あるクラスタを他のクラスタから地理的に離れた場所に配置してもよい。例えば、プロキシ・キャッシュのクラスタはカリフォルニア州サンノゼに、プロキシ・キャッシュの他のクラスタはニューヨークに配置することができる。
【００１４】
クライアント・マシン１０１、１０２のユーザは、インターネット１００を通してコンテンツ・サーバ１０７、１０８に格納された情報にアクセスする。プロキシ・キャッシュ１０５、１０６が配置されているとき、クライアント・リクエストは最初に、コンテンツ・サーバ１０７、１０８ではなくプロキシ・キャッシュ１０５、１０６に送られる。要求されたオブジェクトがプロキシ・キャッシュ１０５、１０６で見つかった場合、オブジェクトはプロキシ・キャッシュ１０５、１０６から直接クライアント・マシン１０１、１０２に返される。一方、要求されたオブジェクトがプロキシ・キャッシュ１０５、１０６で見つからない場合、リクエストはコンテンツ・サーバ１０７、１０８に転送される。
【００１５】
通常、ネットスケープ・コミュニケーションズ社のネットスケープ・ナビゲータやマイクロソフト社のインターネット・エクスプローラ等のブラウザ・ソフトウェアは、クライアント・マシン１０１、１０２で動作する。クライアント・マシンのユーザは通常、http://www.ibm.com等のＵＲＬをブラウザのアドレス・フィールドに指定してＷｅｂサイトにアクセスする。ハッシングをベースにした共同Ｗｅｂキャッシングの場合、このようなＵＲＬは、ハッシュ値を計算するために用いられ、ハッシュ値はプロキシの１つにマップされる。ＵＲＬのプロキシ・キャッシュ・サーバへのハッシングは、クライアント・マシンのブラウザ・ソフトウェアにより行える。その場合、プロキシの論理ホスト名は通常ブラウザによって用いられる。この論理名は、ネットワークのＤＮＳにより物理ＩＰアドレスにマップする必要がある。これに代えて、ブラウザ・ソフトウェアがＵＲＬをハッシュ値に変換し、ハッシュ値をＤＮＳに送るだけでもよい。そこで、ハッシュ値からプロキシの物理ＩＰアドレスへのマッピングがＤＮＳにより行われる。ターゲット・プロキシのＩＰアドレスが識別されると、リクエストがターゲット・プロキシに送られる。要求されたオブジェクトがプロキシ・キャッシュでローカルに見つかった場合、オブジェクトはプロキシから直接クライアント・マシンに返される。他の場合、リクエストはプロキシ・キャッシュによりコンテンツ・サーバに転送される。
【００１６】
ハッシュ値から共同プロキシ群間のプロキシ・キャッシュへのマッピングは、好適にはＤＮＳにより行われる。これは、共同プロキシ・キャッシュの変更をＤＮＳによって管理する方が効率的だからである。ＤＮＳは、ネットワークから削除したりネットワークに追加したりできる。このような変更をインターネットのクライアント・マシンの各々に適用することは困難である。ただし理論上は、クライアント・マシンのブラウザ・ソフトウェアによりマッピングを行うことができる。その場合、これは一般に物理ＩＰアドレスではなく論理ホスト名で行われる。その場合でもブラウザは論理プロキシ名を物理ＩＰアドレスにマップするためＤＮＳに送る。従って、待ち時間対応ハッシングはＤＮＳにより実行するのが望ましい。ブラウザは、ハッシュ値を計算し、共同プロキシ・キャッシュの１つのＩＰアドレスにマップするためＤＮＳに送るだけである。
【００１７】
図２は、本発明の実施例に従った待ち時間対応ハッシングをサポートするＤＮＳシステムを示す。ＤＮＳシステム（図１の１０３、１０４）は、ＣＰＵ２００、ディスク２０２、及びダイナミックＲＡＭ（ＤＲＡＭ）メモリ２０１を含むコンピュータ・システムである。ＤＮＳサーバはインターネットに接続される。
【００１８】
待ち時間対応ハッシング２０４に関連するＤＮＳロジックは、ディスク２０２に格納された実行可能プログラム・ロジックである。これをメモリ２０１にロードして、ハッシュ値から共同プロキシ・キャッシュ群のプロキシのＩＰアドレスへのマッピングを実行することができる。
【００１９】
正規のＤＮＳロジック２０３はまた、ディスク２０２に格納された実行可能プログラム・ロジックであり、メモリ２０２にロードして他のＤＮＳ機能を実行することもできる。
【００２０】
待ち時間対応ハッシング・ロジック２０４の主な機能モジュールは、候補識別モジュール２０５（詳細は図５）、ターゲット選択モジュール２０６（詳細は図８）、及びローカル収集モジュール２０７である。
【００２１】
図３は、一連のプロキシ・キャッシュ間で待ち時間対応ハッシングをサポートするＤＮＳによる標準動作を示すフローチャートである。リクエストが入ると、システムは最初、リクエストが待ち時間対応ハッシングに関連するかどうかを確認する（３０１）。関連しない場合、システムは正規のＤＮＳ機能を実行する（３０３）。関連する場合、システムは最初に一連のプロキシ・キャッシュ候補３０２を識別する。このプロキシ・キャッシュ候補群から、待ち時間遅延及び負荷状態を考慮した後にプロキシを選択する（３０４）。
【００２２】
図４は、本発明の実施例に従った待ち時間対応ハッシングの例を示す。ハッシュ値スペースは多数のハッシュ・パーティション４０２に分けられる。ＵＲＬハッシュ値はそれぞれパーティションの１つに分類される。ハッシュ・パーティションはそれぞれプロキシＩＤ４０１にマップされる。例えば、ａ、ｄ、ｇ、ｂ、ｅ、ｈ、．．．はハッシュ・パーティションにマップされたプロキシの識別子である。一例として、ＵＲＬ  ｕ１  ４０６及びｕ２  ４０７が、それぞれプロキシａ及びｈに対応するハッシュ・パーティションにハッシュされているとする。待ち時間を考慮しない場合、ＵＲＬ  ｕ１はプロキシａに、ＵＲＬ  ｕ２はプロキシｈにそれぞれハッシュされる。しかし、待ち時間を考慮すると、ハッシュ値スペースで最初にプロキシ候補として付近にある他の２つのプロキシが識別される。次に、４０５で指定された待ち時間遅延が調べられ、待ち時間遅延が最小のプロキシが選択される。その結果、ＵＲＬ  ｕ１のターゲット・プロキシとしてプロキシａ、ＵＲＬ  ｕ２のターゲット・プロキシとしてプロキシｃが選択される。
【００２３】
図５は、本発明の実施例に従って、図２の候補識別モジュール２０５のフローチャートを示す。候補識別モジュール２０５は、ＵＲＬから検索されたハッシュ値に対して一連のプロキシ・キャッシュ候補を識別するモジュールである。ハッシュ値は、クライアント・マシンからアクセスできるので、好適にはクライアント・マシン（図１の１０１、１０２）のブラウザ・ソフトウェアにより計算される。５０１で、クライアント・マシンからの所定のハッシュ値は最初、アンカ・ハッシュ・パーティションにマップされる。これは、可能なハッシュ値を所定数のパーティションに分けることによって簡単に行える。アンカ・パーティションは従って、ハッシュ・パーティションの境界に対してハッシュ値を確認することによって識別することができる。アンカ・ハッシュ・パーティションが識別されると、５０２で、１つ以上の付近のハッシュ・パーティションをアンカ・ハッシュ・パーティションに加えることによって、候補になるハッシュ・パーティション群が形成される。付近のハッシュ・パーティションは、アンカ・ハッシュ・パーティションよりもハッシュ値が大きいか小さい、または一定数大きいか小さいパーティションである。ハッシュ・パーティションが循環データ構造として扱われることは理解されよう。つまり、ハッシュ値が最大のパーティションは順番が最後になり、ハッシュ値が最小のパーティションの次になる。最後に５０３で、ハッシュ・パーティション候補群がプロキシ候補群にマップされる。これらのプロキシ候補は、ターゲット選択モジュール（図２の２０６）により調べられ、待ち時間遅延と負荷状態をもとにターゲット・プロキシが見つけられる。
【００２４】
各ハッシュ・パーティションに最初、プロキシのＩＰアドレスが割当てられている場合、３０２でプロキシ・キャッシュ候補群にハッシュ・パーティション候補群をマップすることがかなり簡単になることは理解されよう。例えば簡単なルックアップで十分である。ハッシュ・パーティションにプロキシ・キャッシュを割当てる方法は様々である。各パーティションを１乃至Ｐの整数にハッシュするという単純な方法も考えられる。ここでＰはプロキシ・キャッシュの総数である。数はそれぞれプロキシ・キャッシュを表す。ハッシュ・パーティション総数が十分多いとき、これらのハッシュ・パーティションは全てのプロキシ・キャッシュ間に多少とも均等に分散される。また、最初にプロキシ・キャッシュ毎に、０乃至１の間でＮ／Ｐの乱数を生成することもできる。ここでＮはハッシュ・パーティション総数、Ｐはプロキシ・キャッシュ総数である。Ｎ／Ｐ乱数はそれぞれ、対応する同じプロキシＩＤに関連付けられる。従って生成される乱数合計はＮ、うちＮ／Ｐ個が１つのプロキシＩＤに関連付けられる。次に、これらＮ個の乱数がソートされてリストが作成される。そこで、ソートされたリストの各乱数に関連付けられたプロキシＩＤを各ハッシュ・パーティションに割当てることができる。
【００２５】
Ｗｅｂオブジェクトをキャッシュするため世界各地に設立されるデータセンターが増えると、分散した共同プロキシ・キャッシュを地理的に分散したクラスタと見ることができることは理解されよう。各クラスタ内には、１つ以上のサーバを配置することができる。更にプロキシ・キャッシュ・サーバの数はクラスタ毎にかなり違っていてもよい。その場合、特別なマッピングによりターゲット選択モジュール（図２の２０６）が、閉じた地域内のＵＲＬリクエストに対応するプロキシを簡単に見つけることができる。
【００２６】
図６は、その場所が地理的に分散したクラスタと見ることのできるプロキシへのハッシュ・パーティションの間接マッピングを示すフローチャートである。Ｍ個のクラスタがあるとする。クラスタのプロキシ・キャッシュ数はＣｊ、ｊ＝１、２、．．．、Ｍと表す。６０１で最初、２レベル・ラウンドロビン法により、間接マッピングでプロキシＩＤアレイが作成される。すなわち、最初にクラスタが選択され、選択されたクラスタ内からプロキシ・キャッシュが選択されるが、これは全てラウンドロビン方式である。つまり選択されたクラスタ毎にプロキシ・キャッシュが一度に１つずつ選択されていき、キャッシュが尽きるまでこの操作が繰り返される。このプロキシＩＤアレイの総数はＭ*ＬＣＭｃである。ＬＣＭｃはＣｊ、ｊ＝１、２、．．．、Ｍの最小公倍数である。次に６０２で、ハッシュ・パーティション・セグメントが作成され、各パーティションに、６０１で作成されたプロキシＩＤアレイのインデックスが割当てられる。Ｐｊは、プロキシＩＤアレイにプロキシＩＤが出現する回数を表す。プロキシＩＤはそれぞれ、ハッシュ・パーティション・セグメントのＬＣＭｐ個のハッシュ・パーティションにマップされる。ＬＣＭｐはＰｊ、ｊ＝１、２、．．．、Ｍの最小公倍数である。その場合、ハッシュ・パーティション・セグメントの大きさはＬＣＭｐ*ΣＰｊ、ｊ＝１、２、．．．、Ｍである。プロキシＩＤアレイにプロキシｊがＰｊ回出現し、プロキシｊのインデックスでマップされるハッシュ・パーティションの総数はＬＣＭｐなので、インデックスはそれぞれセグメントのＬＣＭｐ／Ｐｊ個のハッシュ・パーティションに割当てられる。ハッシュ・パーティション・セグメントが構成された後、６０３で、ハッシュ・パーティション・セグメントが一定回数複製され、ハッシュ・パーティション全体が構成される。
【００２７】
前記の間接マッピング法の理解を助けるため、図７に、２つの地域クラスタ内にある５つのプロキシ・キャッシュへのハッシュ・パーティションのマッピング例を示す。１つには２つのプロキシ・キャッシュ７０１があり、もう１つには３つのプロキシ・キャッシュ７０２がある。プロキシａ、ｂは第１クラスタにあり、プロキシｃ、ｄ、ｅは第２クラスタにある。プロキシＩＤアレイを作成するには、２と３の最小公倍数は６なので合計１２の要素が必要である。プロキシＩＤアレイ７０３は次に、ラウンドロビン方式でクラスタ毎にプロキシを選択することによって構成される。プロキシＩＤアレイのインデックスも示してある。ハッシュ・パーティション・セグメント７０４は、プロキシＩＤアレイのインデックスをハッシュ・パーティションに割当てることによって構成される。プロキシａ、ｂはプロキシＩＤアレイにそれぞれ３回現れ、プロキシｃ、ｄ、ｅはそれぞれ２回現れるので、ハッシュ・パーティション・セグメントのサイズは６*５＝３０である（ＬＣＭｐ＝６、ΣＰｊ＝５）。更にプロキシａはプロキシＩＤアレイに３回現れ、そのインデックスは０、４及び８である。インデックスはそれぞれ２つのハッシュ・パーティションに割当てられる（６／３＝２）。従って最初の２つのパーティションにはインデックス０、次の２つにはインデックス４が割当てられ、次の２つにはインデックス８が割当てられる。同様に、プロキシｃはプロキシＩＤアレイに２回現れ、インデックスは１及び７である。従って３つのハッシュ・パーティションにインデックス１が、別の３つのパーティションにインデックス７が割当てられる。
【００２８】
間接マッピング法は、各クラスタに処理能力の異なるプロキシ・キャッシュがある場合について簡単に一般化できることも理解されよう。Ｒｊは、クラスタｊのプロキシ・キャッシュの相対処理能力を示す。ハッシュ・バケット・セグメントの総サイズはＬＣＭｐ*ΣＰｊＲｊになる。前記の図７の例では、第１クラスタのプロキシ・キャッシュの能力が、第２クラスタの２倍であるとき、ハッシュ・パーティション・セグメントのサイズは６*（２*２＋３*１）＝４２である。その場合、４つのハッシュ・パーティションにインデックス０、別の４つのハッシュ・パーティションにインデックス４が割当てられ、また別の４つにインデックス８が割当てられる。
【００２９】
間接マッピングでは、アンカ・プロキシが識別されると、候補群がプロキシＩＤアレイ内の付近のプロキシから選択されることも理解されよう。その場合、サイズＭの候補群は、各クラスタからの少なくとも１つのプロキシ・キャッシュＩＤを含む。Ｍはクラスタ総数である。その結果、間接マッピングにより、どのようなリクエストについても地理的に近接したプロキシ・キャッシュが見つかる可能性が大きくなる。
【００３０】
図８は、本発明の実施例に従ったターゲット選択モジュール２０６（図２）のフローチャートである。変数ｗは、候補識別モジュール２０５（図２）により識別されたプロキシ・キャッシュ候補群のサイズを示す。ターゲット・プロキシ・キャッシュは最初、候補群からの第１プロキシとして設定される（８０１）。
【００３１】
選択モジュールは、ｗ個のプロキシ候補が全て調べられるまで、プロキシ・キャッシュ候補それぞれをループする（８０２）。全てのプロキシ・キャッシュ候補を調べ、リクエストをハッシュする場合は待ち時間遅延を改良できるかどうかを確認する（８０４）。改良できる場合、プロキシ候補が更に調べられ、現在過負荷の状態かどうかが確認される（８０５）。過負荷ではない場合、プロキシ候補は新しいターゲットになる（８０６）。過負荷のとき、選択モジュールは、候補群の残りから次のプロキシ・キャッシュ候補を調べる（８０７）。全てのプロキシ候補が調べられた後、最後のターゲット・プロキシ・キャッシュが返される（８０３）。
【００３２】
待ち時間を改良する基準として最小応答時間を使用できることも理解されよう。また応答時間が所定時間だけ良好な場合を除いて、アンカ・プロキシ・キャッシュを優先する結果になる割引応答時間（discounted response time）をもとにしてもよい。
【００３３】
図９は、本発明の実施例に従ってプロキシ・キャッシュ候補が過負荷かどうか（図８の８０５）を判定するフローチャートである。負荷収集モジュール２０７（図２）は、プローブ・メッセージを共同プロキシ・キャッシュそれぞれに定期的に送り、使用状態を確認するとする。そのようなプロキシ使用状態が維持され、平均使用率及び使用率が最大のキャッシュの使用率を計算することができる。U_maxを、共同プロキシの中で使用率が最大のプロキシ・キャッシュ・サーバの使用率、U_meanを平均使用率とする。OVERLOADをプロキシ・キャッシュ・サーバに関して過負荷とみなされる所定定数（例えば８０％）とする。プロキシ・キャッシュ・サーバの使用率が少なくともU_meanであり、U_maxが少なくともOVERLOADのとき（９０１）、プロキシは過負荷であるとみなされる（９０３）。一方、U_maxがOVERLOAD未満のとき（９０２）、プロキシは使用率が少なくとも（１＋delta）*U_meanの場合にのみ過負荷とみなされる（９０３）。deltaは定数、例えば20%である。数量deltaは、好適には過負荷の発生とみなされる前に平均使用率U_meanに許容可能な差異を与えるため用いられる。十分有用な標準delta値は２０％であるが、基本的には０と１との間の任意の値が許容範囲であり、deltaとして使用することができる。
【００３４】
９０１、９０２のいずれの条件も真ではないとき、プロキシは過負荷とみなされない（９０４）。
【００３５】
使用率が最大のプロキシ・キャッシュ・サーバの使用率は、全てのプロキシ・キャッシュ・サーバ間の負荷の不均衡を示すことがあることも理解されよう。システム全体の不均衡が大きいとき、つまりU_maxが大きい場合、新しいリクエストをプロキシ・キャッシュにハッシュすることに慎重になる必要がある。従ってプロキシ・キャッシュ・サーバは、その使用率がU_meanに達した場合は過負荷とみなされる。一方、システム全体が比較的均衡が取れている、つまりU_maxが小さいとき、新しいリクエストをプロキシ・キャッシュにハッシュすることに"積極的"になる必要がある。その場合、プロキシ・キャッシュ・サーバは、その使用率がU_meanよりも所定量だけ大きくなるまで過負荷とみなされない。負荷収集モジュール２０７（図２）は、全ての共同プロキシ・キャッシュの使用状態を定期的に収集する他に、クライアント・マシン１０１、１０２（図１）と共同プロキシ・キャッシュ１０５、１０６（図１）間の待ち時間遅延を維持する。この待ち時間遅延は、ほとんどが地理上の距離に依存し、また動的ネットワーク・トラフィックにも依存する。待ち時間遅延もまた定期的に更新される。
【００３６】
本発明は、少なくとも１つの現在の好適実施例に従って、所与のＵＲＬに関連する情報をもとに、そのＵＲＬのプロキシ・キャッシュ候補群を示す識別子、及び少なくとも待ち時間をもとに候補群からプロキシ・キャッシュを選択するセレクタを含むことは理解されたい。識別子とセレクタは、ともに、適切なソフトウェア・プログラムが実行される汎用コンピュータに実装することができる。また、ＩＣ（Integrated Circuit）やＩＣの一部に実装することもできる。従って本発明は、ハードウェア、ソフトウェア、またはその組み合わせに実装可能と理解されるべきものである。
【００３７】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００３８】
（１）プロキシ・キャッシュを選択する方法であって、
所与のＵＲＬに関連する情報をもとに該ＵＲＬのプロキシ・キャッシュ候補群を識別するステップと、
少なくとも待ち時間をもとに前記候補群からプロキシ・キャッシュを選択するステップと、
を含む、方法。
（２）前記選択ステップは、少なくとも待ち時間と負荷状態をもとに前記候補群からプロキシ・キャッシュを選択するステップを含む、前記（１）記載の方法。
（３）前記識別ステップは、
前記ＵＲＬをアンカ・ハッシュ・パーティションにハッシュするステップと、
付近の１つ以上のパーティションを前記アンカ・ハッシュ・パーティションに加えることによってハッシュ・パーティション候補群を形成するステップと、
各パーティションをプロキシ・キャッシュにマップするステップと、
を含む、前記（１）記載の方法。
（４）前記識別ステップは、
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成するステップと、
前記ＵＲＬをアンカ・ハッシュ・パーティションにハッシュするステップと、
対応するアンカ・プロキシ・キャッシュを見つけるステップと、
前記プロキシＩＤアレイから付近の１つ以上のプロキシ・キャッシュを前記アンカ・プロキシ・キャッシュに加えることによってプロキシ・キャッシュ候補群を形成するステップと、
を含む、前記（１）記載の方法。
（５）前記選択ステップは、少なくとも最小応答時間をもとに前記プロキシ候補群からプロキシ・キャッシュを選択するステップを含む、前記（１）記載の方法。
（６）前記選択ステップは、割引応答時間が所定量だけ良好な場合を除いて、少なくとも前記アンカ・プロキシ・キャッシュを優先する結果になる該割引応答時間をもとにして前記プロキシ候補群からプロキシ・キャッシュを選択するステップを含む、前記（１）記載の方法。
（７）前記選択ステップは、少なくともプロキシ・キャッシュ・サーバが過負荷ではない状態をもとにして前記プロキシ候補群からプロキシ・キャッシュを選択するステップを含む、前記（１）記載の方法。
（８）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより大きいパーティションを含む、前記（３）記載の方法。
（９）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより小さいパーティションを含む、前記（３）記載の方法。
（１０）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより大きいパーティション及び前記アンカ・パーティションより小さいパーティションの両方を含む、前記（３）記載の方法。
（１１）前記マッピング・ステップは、各ハッシュ・パーティションを１とＰとの間の数にハッシュするステップを含み、Ｐはプロキシ総数を表す、前記（３）記載の方法。
（１２）前記マッピング・ステップは、
各プロキシについて、Ｎがハッシュ・パーティション総数、Ｐがプロキシ総数を表すとき、０と１との間のＮ／Ｐ個の乱数を生成するステップと、
生成されたＮ個の対応する乱数をソートすることによってプロキシ・リストを生成するステップと、
ソートされた前記プロキシ・リストをもとに各ハッシュ・パーティションを１つのプロキシに割当てるステップと、
を含む、前記（３）記載の方法。
（１３）プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する前記ステップは、
共同プロキシ・キャッシュを持つプロキシＩＤアレイを形成するステップと、
各ハッシュ・パーティションを前記プロキシＩＤアレイのインデックスにマップするハッシュ・パーティション・セグメントを作成するステップと、
前記ハッシュ・パーティション・セグメントを所定回数複製するステップと、
を含む、前記（４）記載の方法。
（１４）プロキシ・キャッシュを選択するシステムであって、
所与のＵＲＬに関連する情報をもとに該ＵＲＬのプロキシ・キャッシュ候補群を識別する識別子と、
少なくとも待ち時間をもとに前記候補群からプロキシ・キャッシュを選択するセレクタと、
を含む、システム。
（１５）前記セレクタは、少なくとも待ち時間と負荷状態をもとに前記候補群からプロキシ・キャッシュを選択するようにされた、前記（１４）記載のシステム。
（１６）前記識別子は、
前記ＵＲＬをアンカ・ハッシュ・パーティションにハッシュし、
付近のパーティションを前記アンカ・ハッシュ・パーティションに加えることによってハッシュ・パーティション候補群を形成し、
各パーティションをプロキシ・キャッシュにマップする、
ようにされた、前記（１４）記載のシステム。
（１７）前記識別子は、
プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成し、
前記ＵＲＬをアンカ・ハッシュ・パーティションにハッシュし、
対応するアンカ・プロキシ・キャッシュを見つけ、
前記プロキシＩＤアレイから付近のプロキシ・キャッシュを前記アンカ・プロキシ・キャッシュに加えることによってプロキシ・キャッシュ候補群を形成するようにされた、前記（１４）記載のシステム。
（１８）前記セレクタは、少なくとも最小応答時間をもとに前記プロキシ候補群からプロキシ・キャッシュを選択するようにされた、前記（１４）記載のシステム。
（１９）前記セレクタは、割引応答時間が所定量だけ良好な場合を除いて、少なくとも前記アンカ・プロキシ・キャッシュを優先する結果になる該割引応答時間をもとにして前記プロキシ候補群からプロキシ・キャッシュを選択するようにされた、前記（１４）記載のシステム。
（２０）前記セレクタは、少なくともプロキシ・キャッシュ・サーバが過負荷ではない状態をもとにして前記プロキシ候補群からプロキシ・キャッシュを選択するようにされた、前記（１４）記載のシステム。
（２１）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより大きいパーティションを含む、前記（１６）記載のシステム。
（２２）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより小さいパーティションを含む、前記（１６）記載のシステム。
（２３）前記付近のパーティションは、ハッシュ値が前記アンカ・パーティションより大きいパーティション及び前記アンカ・パーティションより小さいパーティションの両方を含む、前記（１６）記載のシステム。
（２４）前記識別子は、各ハッシュ・パーティションを１とＰとの間の数にハッシュするようにされ、Ｐはプロキシ総数を表す、前記（１６）記載のシステム。
（２５）前記識別子は、マッピングにおいて、
各プロキシについて、Ｎがハッシュ・パーティション総数、Ｐがプロキシ総数を表すとき、０と１との間のＮ／Ｐ個の乱数を生成し、
生成されたＮ個の対応する乱数をソートすることによってプロキシ・リストを生成し、
ソートされた前記プロキシ・リストをもとに各ハッシュ・パーティションを１つのプロキシに割当てる、
ようにされた、前記（１６）記載のシステム。
（２６）前記識別子は、プロキシＩＤアレイへのハッシュ・パーティションの間接マッピングを作成する際、
共同プロキシ・キャッシュを持つプロキシＩＤアレイを形成し、
前記プロキシＩＤアレイのインデックスに各ハッシュ・パーティションをマップするハッシュ・パーティション・セグメントを作成し、
前記ハッシュ・パーティション・セグメントを所定回数複製する、
ようにされた、前記（１７）記載のシステム。
（２７）マシンで読取り可能であり、プロキシ・キャッシュを選択する方法のステップを実行するために該マシンにより実行可能な命令のプログラムを明確に具体化したプログラム・ストレージ・デバイスにおいて、該方法のステップは、
所与のＵＲＬに関連する情報をもとに該ＵＲＬのプロキシ・キャッシュ候補群を識別するステップと、
少なくとも待ち時間をもとに前記候補群からプロキシ・キャッシュを選択するステップと、
を含む、ストレージ・デバイス。
【図面の簡単な説明】
【図１】Ｗｅｂキャッシングをサポートするネットワーク・システムを示す図である。
【図２】待ち時間対応ハッシングをサポートするＤＮＳシステムを示す図である。
【図３】一連のプロキシ・キャッシュ間で待ち時間対応ハッシングをサポートするＤＮＳによる動作を示す図である。
【図４】待ち時間対応ハッシングを示す図である。
【図５】図２の候補識別モジュールのフローチャートである。
【図６】その場所を地理的に分散したクラスタとみなすことのできるプロキシへのハッシュ・パーティションの間接マッピングを示すフローチャートである。
【図７】地理的に分散した２つのクラスタ内にある５つのプロキシ・キャッシュへのハッシュ・パーティションのマッピングを示す図である。
【図８】図２のターゲット選択モジュールのフローチャートである。
【図９】プロキシ・キャッシュ候補が過負荷かどうかを（図８に簡単に述べているように）判定するフローチャートである。
【符号の説明】
１００  インターネット
１０１、１０２  クライアント・マシン
１０３、１０４  ドメイン・ネーム・サーバ（ＤＮＳ）
１０５、１０６  プロキシ・キャッシュ・サーバ
１０７、１０８  コンテンツ・サーバ
２００  ＣＰＵ
２０１  ＤＲＡＭメモリ
２０２  ディスク
２０３  ＤＮＳロジック
２０４  待ち時間対応ハッシング
２０５  候補識別モジュール
２０６  ターゲット選択モジュール
２０７  負荷収集モジュール
４０１  プロキシＩＤ
４０２  ハッシュ・パーティション
４０６  ＵＲＬ  ｕ１
４０７  ＵＲＬ  ｕ２
７０１、７０２  プロキシ・キャッシュ
【図１】
0003697162.tif 000002
【図２】
0003697162.tif 000003
【図３】
0003697162.tif 000004
【図４】
0003697162.tif 000005
【図５】
0003697162.tif 000006
【図６】
0003697162.tif 000007
【図７】
0003697162.tif 000008
【図８】
0003697162.tif 000009
【図９】
0003697162.tif 000010