(57)【要約】【課題】コンテンツ配信ネットワーク（ＣＤＮ）向きのいくつかの抑止メカニズムを提供すること。【解決手段】これらには、ハッシュベース要求ルーティング・スキームおよびサイト割り振りスキームが含まれる。ハッシュベース要求ルーティング・スキームは、正当な要求と偽りの要求とを区別するための方法を提供する。このメカニズムを使用すると、アタッカーは、サイト・コンテンツがｎ個のＣＤＮキャッシュからサービスされるとき、ＣＤＮホスト・サイトを犠牲にするためにＯ（ｎ２）の量のトラフィックを生成することを必要とされる。これらの修正がなければ、アタッカーはサイトを停止させるためにＯ（ｎ）のトラフィックのみを生成しなければならない。サイト割り振りスキームは、ＣＤＮホスト・ウェブ・サイトの間に十分な分離を提供して、１つのウェブ・サイトに対する攻撃が他のサイトを使用不可能にすることを防止する。
2005535021.tif 000002
【特許請求の範囲】
【請求項１】
分散サービス妨害攻撃に対するコンテンツ配信ネットワーク（ＣＤＮ）の回復力を向上させるための方法であって、
ソース・アドレスをクライアントから受信するステップと、
前記ソース・アドレスがサーバーで受け入れられることを検証するステップと、
前記ソース・アドレスが前記サーバーで受け入れられる場合、より高いレベルのサービスを前記クライアントに提供するステップとを含む方法。
【請求項２】
前記ソース・アドレスがサーバーで受け入れられることを検証するステップは、
前記ソース・アドレスおよびサイト・アドレスをハッシュしてサーバーｉｄを得るステップと、
前記サーバーｉｄを前記ソース・アドレスに送信するステップと、
クライアント・ソース・アドレスおよび要求されたサイト・アドレスを含むクライアント要求を前記サーバーで受信するステップと、
前記クライアント・ソース・アドレスおよび前記要求されたサイト・アドレスをハッシュして、第２のサーバーｉｄを得るステップと、
前記第２のサーバーｉｄが、接続された前記サーバーを識別するかどうかを判断するステップとを含む、請求項１に記載の方法。
【請求項３】
より高いレベルのサービスを前記クライアントに提供するステップは、クライアント要求を標準キューに挿入するステップを含む、請求項１に記載の方法。
【請求項４】
前記ソース・アドレスが前記サーバーで受け入れられない場合、クライアント要求を低優先順位キューに挿入するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記低優先順位キュー内の要求がドロップされる、請求項４に記載の方法。
【請求項６】
前記低優先順位キューがフルであるとき、前記ドロップされた要求がドロップされる、請求項５に記載の方法。
【請求項７】
より高いレベルのサービスを前記クライアントに提供するステップは、クライアント要求をマルチレベル優先順位キューのｉ番目のレベル（ｉは前記サーバーでの前記クライアントの優先順位レベル）に挿入するステップを含む、請求項１に記載の方法。
【請求項８】
前記要求されたサイト・アドレスは前記サーバーで、前記クライアントによって前記サーバーに接続するために使用された宛先アドレスに基づいて決定される、請求項２に記載の方法。
【請求項９】
前記ＣＤＮで使用されるハッシング関数は、ルーターとサーバーの間で共有された秘密鍵を使用する鍵付きハッシング関数である、請求項２に記載の方法。
【請求項１０】
前記ハッシング関数は定期的に更新される、請求項９に記載の方法。
【請求項１１】
所定の時間間隔中に、前記ソース・アドレスの検証において、古いハッシング関数および更新されたハッシング関数が認められる、請求項１０に記載の方法。
【請求項１２】
ウェブ・サイトをコンテンツ配信ネットワーク内のサーバーに割り振るための方法であって、
各々が、ウェブ・サイトへのサーバーの割り振りをマッピングするための２進ベクトルを含む割り振りベクトルを複数の各ウェブ・サイトに対して提供するステップと、
サーバーへのウェブ・サイトの最適な割り振りを、指定されたリソース制約を使用して決定するステップと、
前記割り振りベクトルを、前記決定された最適な割り振りを反映するように構成するステップとを含む方法。
【請求項１３】
サーバーへのウェブ・サイトの最適な割り振りを決定するステップは、複数のｎビット・２進ベクトルを所定の数のサーバーに対して、各ｎビット２進ベクトルが等しいハミング重みを有するように、かつ、前記ｎビット２進ベクトルの間のペアワイズ・ハミング距離が最大値になるように、生成するステップを含む、請求項１２に記載の方法。
【請求項１４】
サーバーへのウェブ・サイトの最適な割り振りを決定するステップは、複数のｎビット２進ベクトルを所定の数のサーバーに対して、各ｎビット２進ベクトルが等しいハミング重みを有するように、かつ、前記ｎビット２進ベクトルの間のペアワイズ・ハミング距離が所定の値になるように、生成するステップを含む、請求項１２に記載の方法。
【請求項１５】
マシンによって可読であり、分散サービス妨害攻撃に対するコンテンツ配信ネットワーク（ＣＤＮ）の回復力を向上させるための方法の各ステップを実行するために前記マシン上で実行可能な命令のプログラムを有形に実施する、プログラム・ストレージ・デバイスであって、前記方法の各ステップは、
ソース・アドレスをクライアントから受信するステップと、
前記ソース・アドレスがサーバーで受け入れられることを検証するステップと、
前記ソース・アドレスが前記サーバーで受け入れられる場合、より高いレベルのサービスを前記クライアントに提供するステップとを含む、プログラム・ストレージ・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にコンピュータ・ネットワークに関し、より詳細には、分散サービス妨害攻撃に対するコンテンツ配信ネットワークの回復力を向上させるための技術に関する。
【背景技術】
【０００２】
インターネット・サーバーに対する分散サービス妨害（ＤＤｏＳ）攻撃の検出および防止の問題は、最近、ネットワーキング・リサーチ・コミュニティから、また、主にこれらのタイプの攻撃と闘うために設立された新しい会社の間で、かなりの関心を引いてきている。これらの攻撃は通常、ネットワークまたはサーバーを偽りの要求パケットによりフラッディングし、ネットワークまたはサーバーを、正当な要求を処理するためには使用不可能にする。パフォーマンスおよび可用性がインターネット・サービスの間で重要な差別化要因である時代に、このようなダウンタイムは実質的な財務上の損失を招く結果となる。セキュリティの問題についての認識が増しているにもかかわらず、サービス妨害攻撃は重要な問題であり続けている。最近のコンピュータ・セキュリティ・インスティテュート（Computer Security Institute）の調査によれば、例えば、自らのサイトがＤｏＳ攻撃（例えば、ＴＣＰ  ＳＹＮフラッド）の犠牲者となったことがあることを示す回答者の数は、２０００年の２７％から２００１年には３８％に上昇した。
【０００３】
今日までのＤＤｏＳ攻撃に対抗する作業の大部分は、アタッカーが帯域幅およびサーバー・リソースを比較的容易にオーバーランすることができる、単一の集中サーバーのロケーションまたはウェブ・サイトを目標にする攻撃に焦点を置いてきた。今日のインターネット・アーキテクチャでは、しかし、多数の大容量サイトが分散されており、いくつかのデータ・センター内でコンテンツを複製しているか、あるいはコンテンツ配信サービス・プロバイダ（ＣＤＳＰ）を使用してコンテンツを配信している。例えば、メディア・マトリックス（Media Matrix）により報告された、インターネット上で最もトラフィックの多いサイトのトップ２０の中で少なくとも１５のサイトが、アカマイ（Akamai）、デジタル・アイランド（DigitalIsland）またはスピーデラ（Speedera）など、ＣＤＳＰを使用している。また、大容量サイトはＤＤｏＳ攻撃の目標である可能性が高いことも明白である。２０００年２月には、例えば、相次ぐ高度なＤＤｏＳ攻撃がいくつかの有名なサイトを停止させ、これらのサイトにはヤフー（Yahoo）、イーベイ（Ebay）、アマゾン・ドット・コム（Amazon.com）、ＣＮＮおよびバイ・ドット・コム（Buy.com）が含まれ、そのほとんどは現在ＣＤＳＰを使用してコンテンツを配信している。
【０００４】
よりよいパフォーマンスを約束することに加えて、ＣＤＳＰはしばしば、それらがＤＤｏＳ攻撃に対して増大した回復力を提供することができると主張する。コンテンツ配信ネットワーク（ＣＤＮ）は本当に、ＤＤｏＳ攻撃からのある保護を、その本質的に分散された性質によって提供するが、ＣＤＮの共有サーバー・インフラストラクチャはまた脆弱性にもなり得る。単一のＣＤＮホスト・ウェブ・サイトに対する攻撃は、ＣＤＳＰによってホストされたカスタマー・サイトの多数（または全部）に影響を及ぼす可能性がある。慎重なサイト割り振り戦略がなければ、ＣＤＮによって提供された冗長性およびレプリケーションは、すべてのホストされたカスタマーのために制限された保護を提供する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の様々な実施形態によれば、コンテンツ配信ネットワーク（ＣＤＮ）向きのサービス妨害攻撃への抑止メカニズムが提供される。これらには、ハッシュベース要求ルーティング・スキームおよびサイト割り振りスキームが含まれる。ハッシュベース要求ルーティング・スキームは、正当な要求と偽りの要求とを区別するための方法を提供する。このメカニズムを使用すると、アタッカーは、サイト・コンテンツがｎ個のＣＤＮキャッシュからサービスされるとき、ＣＤＮホスト・サイトを犠牲にするためにＯ（ｎ２）の量のトラフィックを生成することを必要とされる。これらの修正がなければ、アタッカーはサイトを停止させるためにＯ（ｎ）のトラフィックのみを生成しなければならない。サイト割り振りスキームは、ＣＤＮホスト・ウェブ・サイトの間に十分な分離を提供して、１つのウェブ・サイトに対する攻撃が他のサイトを使用不可能にすることを防止する。２進符号に基づいた割り振り戦略を使用すると、その割り当てられたサーバーを使用不可にするいかなる個々のウェブ・サイトに対する攻撃の成功も、ＣＤＮによってホストされた他のウェブ・サイトをも停止させることはないという保証を提供することができる。
【課題を解決するための手段】
【０００６】
本発明の様々な実施形態では、分散サービス妨害攻撃に対するコンテンツ配信ネットワークの回復力を向上させるための方法が提供される。この方法によれば、ソース・アドレスがクライアントから受信され、次いでこのソース・アドレスが検証されて、それがサーバーで受け入れられることが保証される。このソース・アドレスが受け入れられる場合、より高いレベルのサービスがクライアントに提供される。
【０００７】
ソース・アドレスがクライアントに属するという検証には、ハッシュベース技術を使用することが含まれる場合があり、これにおいて、ソース・アドレスおよびサイト・アドレスがハッシュされてサーバーｉｄが得られ、サーバーｉｄはソース・アドレスに送信される。サーバーが、クライアント・ソース・アドレスおよび要求されたサイト・アドレスを含むクライアント要求を受信するとき、これらの値がハッシュされて、第２のサーバーｉｄが得られる。次いで、このサーバーｉｄがサーバーを識別するかどうかについての判断が行われる。
【０００８】
すべてのＣＤＮサーバーがカスタマー・サイト全体をホストするとは限らないとき、クライアント・ソース・アドレスおよび宛先サイト・アドレスが使用されて、サーバーでのクライアントの要求の受け入れが判断される。本発明は、サイト情報をクライアントの要求においてクライアント・ソース・アドレスと共に伝達するための方法を提供する。要求されたサイト・アドレスをサーバーで、クライアントによってサーバーに接続するために使用された宛先アドレスに基づいて決定することができる。
【０００９】
より高いレベルのサービスが提供されるクライアントからの要求を、標準キューに挿入することができ、クライアントからの残りの要求を低優先順位キューに挿入することができる。標準キュー内の要求には、低優先順位キュー内の要求より上の優先順位が与えられる。低優先順位キュー内の要求をドロップさせることができる。
【００１０】
加えて、多数の優先順位レベルを提供することができる。この場合、クライアントからの要求がマルチレベル優先順位キューのｉ番目のレベルに挿入され、ただしｉはサーバーでのクライアントの優先順位レベルである。
【００１１】
ＣＤＮで使用されるハッシング関数を、ルーターとサーバーの間で共有された秘密鍵を使用する鍵付きハッシング関数にすることができる。これらのハッシング関数を定期的に更新することができる。所定の時間間隔中に、ソース・アドレスの検証において、古いハッシング関数および更新されたハッシング関数を認めることができる。
【００１２】
本発明の様々な実施形態によれば、ウェブ・サイトをコンテンツ配信ネットワーク内のサーバーに割り振るための方法も提供される。割り振りベクトルが複数のウェブ・サイトに対して提供され、各割り振りベクトルは、ウェブ・サイトへのサーバーの割り振りをマッピングするための２進ベクトルを含む。サーバーへのウェブ・サイトの最適な割り振りは、指定されたリソース制約を使用して決定され、割り振りベクトルは次いで、決定された最適な割り振りを反映するように構成される。
【００１３】
符号化理論の結果を使用して、最適な割り振りベクトルを決定することができる。例えば、複数のｎビット２進ベクトルを所定の数のサーバーに対して、各ｎビット２進ベクトルが等しいハミング重みを有するように、かつ、複数のｎビット２進ベクトルの間のペアワイズ・ハミング距離が最大値になるように、生成することができる。サーバーの数が知られている場合、所与のハミング距離のための最適な割り振りは、複数のｎビット２進ベクトルを所定の数のサーバーに対して、各ｎビット２進ベクトルが等しいハミング重みを有するように、かつ、複数のｎビット２進ベクトルの間のペアワイズ・ハミング距離が所定の値になるように生成することによって、決定することができる。
【００１４】
本発明のこれらおよび他の態様、特徴および利点は、以下の好ましい実施形態の詳細な説明から明らかとなり、これは添付の図面と関連して読まれるべきである。
【発明を実施するための最良の形態】
【００１５】
本発明は、コンテンツ配信ネットワーク（ＣＤＮ）に適した抑止メカニズムの開発に焦点を合わせる。本発明の様々な実施形態によれば、ＣＤＮに固有の機能を利用することによって、アタッカーの仕事を著しくより困難にする技術が提供され、これらの機能はすなわち、クライアント要求を最も適切なＣＤＮサーバーにダイレクトする要求ルーティング・システム、および、ウェブ・サイト・コンテンツを共有ＣＤＮサーバーに割り当てるポリシーである。共有ＣＤＮコンテンツ・サービング・インフラストラクチャの回復力を向上させ、またＣＤＮホスト・ウェブ・サイトの間に十分な分離を提供して、１つのウェブ・サイトに対する攻撃が他のサイトを使用不可能にすることを防止する、様々なメカニズムが開示される。
【００１６】
本発明は、ＤＤｏＳ攻撃に対して著しくより高い回復力を提供し、ウェブ・サイトの可用性を向上させ、アタッカーがその目的をＣＤＮ環境内で達成することをはるかにより困難にする。さらに、なおあるレベルの保護を提供する間にＣＤＮのパフォーマンスを最適化しようと試みるのではなく、個々のウェブ・サイトに対する攻撃が他のＣＤＮホスト・サイトに影響を及ぼさないことを保証するサイト割り振りスキームに焦点が置かれる。この手法は、この保証を保持すると同時にまた、残りのサイトについて可能な限りパフォーマンスの低下を小さくすることである。
【００１７】
図１を参照すると、コンテンツ配信ネットワーク（ＣＤＮ）１００は、複数のＣＤＮサーバーを含み、これはＣＤＮサーバー１２０などであり、複数の地域内に分散される。図１に示すように、ＣＤＮ地域１１０などのＣＤＮ地域は、ＣＤＮサーバーのグループを含む。地域を任意に定義することができるが、これらの地域は通常、あるトポロジー的または地理的有意性を有する。ＩＳＰネットワークまたは自律システムのセット内に配置されたサーバーを、例えば、単一のＣＤＮ地域の一部にすることができる。
【００１８】
各ＣＤＮサーバーは共有され、それにおいて、各ＣＤＮサーバーはコンテンツを多数のコンテンツ・プロバイダ（すなわち、ＣＤＳＰのカスタマー）からサービスすることができる。またオリジン・サーバーもあり、これは、特定のコンテンツ・プロバイダのためのコンテンツの信頼できるソースとしての機能を果たす。このモデルは、多数のサイトに渡って複製されるいかなるウェブベース・コンテンツまたはアプリケーションにも適用可能である。
【００１９】
オペレーションでは、クライアント１４０はＣＤＮサーバーからのコンテンツに、最初に要求ルーター１３０などの要求ルーターに接続することによってアクセスし、要求ルーター１３０は（透過的に）クライアント１４０を適切な地域キャッシュにダイレクトする。要求ルーターは論理的にこれらのキャッシュから分離するが、要求ルーターを物理的に同じ場所に配置することができる。要求ルーターの分散は通常、ＣＤＮのサイズによって決まる。例えば、ＣＤＮが非常に幅広い分散を有する場合、要求ルーターをあらゆる地域内に配置することができる。要求ルーターはその決定をクライアントＩＰアドレスに、場合によっては、ネットワークまたは候補サーバーの状態について、あるいは要求されているコンテンツについての他の情報と共に、基づかせることができる。実際には、要求ルーターをＤＮＳサーバーまたはウェブ・サーバーにすることができ、このサーバーは、クライアントがネーム・レゾリューション要求またはクライアント要求をそれぞれ行うとき、近接キャッシュを選択する。クライアントが要求ルーターに接続する方法については考察しない。しかし、多数のＣＤＮはＤＮＳをこのために使用する。
【００２０】
本発明は、フラッディング・タイプの攻撃に焦点を合わせ、この攻撃は、アタッカーが犠牲者サイトを非常に大量のネットワーク・トラフィックにより圧倒して、このサイトを、ユーザー要求にサービスするためには事実上使用不可能にしようと試みるものである。
【００２１】
大規模なＤＤｏＳ攻撃を開始するために、アタッカーは最初に、ネットワークに接続された多数の地理的に分散されたマシンに進入して打倒しなければならない。次いで、障害が起きたマシンは、攻撃トラフィックを生成するために使用されるか、あるいは、攻撃の真の起点を隠すためのリフレクターとして使用される。ホストに障害を起こし、攻撃ツールをインストールするプロセスはしばしば自動化され、このプロセスを単一のホスト上で数分で行うことができる。障害が起きたホストはそれ自体が、さらに他のホストを走査して打倒するために使用される可能性があるので、何千ものホストで１時間以内に障害が起こる可能性がある。複数の攻撃側ホストが、ターゲット・ウェブ・サイトをホストするＣＤＮについてのある情報（例えば、ＣＤＮサーバーのアドレス）を知るために使用される場合、複数のホストはこの情報を、攻撃の過程において交換することができる。
【００２２】
しばしば、アタッカーは、攻撃の真の起点を隠してその効果を増すために、攻撃パケット内のソースＩＰアドレスをスプーフするようになる。真のＩＰアドレスを使用することで攻撃のソースが明らかとなり、既存のスキームによって攻撃のソースに遡ることができるようになる。また、ＩＰアドレスのセットからのパケットの急増を検出し、続いてそのトラフィックをブロックすることは、ステートフル・パケット・フィルタリングを使用して大いに実現可能である。最初に我々は、アタッカーがソースＩＰアドレスをＩＰアドレス・スペース全体から均一に選択すると仮定する。しかし、以下で、アタッカーがアドレスをより慎重に選択しようと試みる場合、我々のスキームの効果が損なわれないことを示す。
【００２３】
ＨＴＴＰプロトコルはＴＣＰを使用するので、ＣＤＮサーバーのフラッディングはＴＣＰ  ＳＹＮフラッド攻撃の特殊な場合である。ＴＣＰ  ＳＹＮフラッド攻撃に対する多数の防御的手段が提案され、配備されている。いくつかの対抗手段が潜在的な攻撃の目標上に配備され、これらの対抗手段は、ＴＣＰ  ＳＹＮパケットをランダムにドロップすること、ＴＣＰ接続を確立するために許可された期間を短縮すること、部分的に確立されたＴＣＰ接続を保持するキューの長さを増すこと、およびシステム・メモリ・サイズを増すことなどである。速度制限およびトラフィック・シェーピングなど、他の手法はネットワーク・ルーター上に配備される。これらのすべての対抗手段は、攻撃目標での過負荷を防止する際に有効であるが、これらの対抗手段は、悪意的ＴＣＰ  ＳＹＮパケットと、突然のイベントによってトリガーされた多数の正当なＴＣＰ  ＳＹＮパケットとを区別することができない。以下で明らかになるように、本発明は過負荷を防止するだけでなく、ＣＤＮサーバーに向けられた悪意的要求と正当な要求との有効な区別も提供する。
【００２４】
本発明のよりよい理解を促進するために、我々は最初に、ウェブ・サイトの相対的回復力を定量化するための単純なメトリックを考察する。直観的に我々は、アタッカーが、サイトＢを停止させるために必要とされるよりも、サイトＡを停止させるためにより多くのトラフィックを送信する必要がある場合、サイトＡがサイトＢよりも回復力に富むという。したがって、別のサイトＢとの比較におけるサイトＡの相対的回復力を、以下のように定義する。
【００２５】
サーバーの回復力：サーバーＢを使用不可能にするためよりも、サーバーＡを使用不可能にするためにｋ倍多くの攻撃トラフィックが必要とされる場合、サーバーＡはサーバーＢよりｋ倍多く回復力に富み、ただし、使用不可能性は、サーバーＡおよびＢについて等しく定義される。
【００２６】
より正確には、我々がＣＤＮを、オリジン・サーバーの全コンテンツを複製するｎ個のサーバーのネットワークとして見なすとき、ＣＤＮは、単一のサーバーを停止させるために必要とされるよりも、すべてのｎ個のキャッシュを停止させるためにｎ倍多くの攻撃トラフィックを要するので、単一のサーバーと比較してＯ（ｎ）の回復力を提供することを示すことは簡単である。
【００２７】
我々の第２のメトリックは、同じＣＤＮによってホストされた別のサイトに対する攻撃からの、サイトの分離または保護の度合いを定量化する。例えば、２つの独立したウェブ・サイトＡおよびＢをホストするＣＤＮを考察する。理想的には、サイトＡに対するＤＤｏＳ攻撃は、サイトＢのパフォーマンスまたは可用性にまったく影響を及ぼすべきではない。これは、これら２つのサイトがいかなる共通サーバーも共有しないときに当てはまる。しかし実際には、複数のウェブ・サイトが共有サーバーによって、これらのサーバーから十分なスループット・パフォーマンスを達成するためにホストされる。したがって、ホストされたウェブ・サイトのパフォーマンス要件および保護のバランスを取ることが重要である。特に、重要な目的は、各サイトをホストするサーバーの数を最大化し、それらの間の分離のレベルを保証することである。
【００２８】
分離のレベルを定量化する１つの方法は、対象のサイトによって共有されていないサーバーの数をカウントすることである。より正確には、いかなる２つのサイトの間の分離の度合いも、以下のように定義することができる。
【００２９】
分離の度合い：ｗｉおよびｗｊは２つの独立したウェブ・サイトを示すものとし、ｓｉ＝｛ｓ１，．．．，ｓｌ｝および
【００３０】
【数１】
2005535021.tif 000003
は、ｗｉおよびｗｊに割り振られたＣＤＮサーバーのセットをそれぞれ示すものとする。ｗｉおよびｗｊの間の分離の度合いを、ｍｉｎ（｜ｓｉ−ｓｊ｜，｜ｓｊ−ｓｉ｜）となるように定義する。
【００３１】
以下に示すように、各サイトに等しい数のサーバーが割り当てられると過程すると、次いで２つのサイトの間の分離の度合いは単に
【００３２】
【数２】
2005535021.tif 000004
であり、ただし、ｄは非結合キャッシュの数を示す。
【００３３】
次に、ハッシュベース要求ルーティングと呼ばれる新規なアルゴリズムを提示し、これは、スプーフされたＩＰアドレスを使用してＤＤｏＳ攻撃に対するＣＤＮの回復力を著しく向上させることができる。ハッシュベース要求ルーティングの主な考えは、正当なソースＩＰアドレスを有する要求を、スプーフされたソースＩＰアドレスを有する要求とは異なるように処理して、ＣＤＮが過負荷にされるときに正当な要求にサービスする間に、攻撃パケットの大部分が優先的にドロップされるようにすることである。この目的は、ＣＤＮに固有の機能の１つ、すなわち、要求ルーティング・システムを利用することによって達成される。このハッシュベース要求ルーティング・スキームは、正当な要求をまったく抑制することなく、攻撃トラフィックの大部分をブロックする。より正確には、あるウェブ・サイトにサービスするｎ個のサーバーがあるとき、攻撃トラフィックの
【００３４】
【数３】
2005535021.tif 000005
の割合がサーバーによってドロップされるようになる。このようにして、我々は、サーバー・リソースが主として、攻撃下でも正当な要求にサービスするために利用されて、それによりＣＤＮの生存性を著しく向上させることを保証することができる。
【００３５】
ハッシュベース要求ルーティング・アルゴリズムは、大部分のＣＤＮが要求ルーティング・システムをそれらのサービス・インフラストラクチャの一部として使用するという事実に基づいており、クライアントが、ＣＤＮによってホストされたウェブ・サイトにアクセスすることを望むとき、クライアントは最初にローカルの要求ルーターに接続して、接続するべきＣＤＮサーバーのＩＰアドレスを発見する。一般に、要求ルーティング・システムは、クライアントによって感じられる応答時間を最適化するように、あるいは、ＣＤＮサーバーでのロード・バランシングを行うように試みる。我々のアーキテクチャでは、ハッシュベース要求ルーティングは、正当な要求と、スプーフされたＩＰアドレスを有する潜在的攻撃トラフィックとを区別する目的に適う。この目的は、ルーターとＣＤＮサーバーの間で共有された秘密鍵を使用する単一の鍵付きハッシングによって達成される。
【００３６】
図２を参照して、ハッシュベース要求アルゴリズムのオペレーションを例示する。クライアントがウェブ・サイトにアクセスすることを望むとき、クライアントは最初に要求をローカルの要求ルーターに送信して、接続するべきＣＤＮサーバーのアドレスを発見する（ステップ１）。クライアントはその地域内のいかなる要求ルーターにも接続することができる。次に、要求ルーターは、ウェブ・サイトおよびクライアントのソースＩＰアドレスに基づいて、ハッシュ関数Ｈを使用してＣＤＮサーバーを選択し、ハッシュ関数ＨはＣＤＮサーバーと共に秘密で共有される（ステップ２）。単純な均一ハッシュ関数を使用することができる。例えば、Ｈ：ウェブ・サイトｘＩＰアドレス→サーバー・アドレスである。すなわち、いかなる所与の（ウェブ・サイト、ＩＰアドレス）ペアも同様に、いかなるサーバー・アドレスにもハッシュする可能性がある。
【００３７】
次に、要求ルーターは、接続するべきＣＤＮサーバーのアドレスにより応答する（ステップ３）。アタッカーは、スプーフされたアドレスを使用して、ＩＰアドレスとサーバーの間のマッピングを発見することはできず、これは、この応答がクエリーに含まれたソース・アドレスに送信され戻されるからであることに留意されたい。すなわち、アタッカーは、障害が起きたホストのＩＰアドレスについてのマッピングしか発見することができず、これらのマッピングは、使用可能なＩＰアドレス・スペース全体と比較して、比較的小さい。
【００３８】
要求ルーターからの応答を受信した上で、クライアントは、要求をサーバーにサーバー・アドレスと共に送信する（ステップ４）。ＣＤＮサーバーがこの要求を受信するとき、ＣＤＮサーバーは、共有ハッシュ関数Ｈを使用して、要求内の（ソース・アドレス、ウェブ・サイト）ペアがそれ自体のアドレスにハッシュするかどうかを確かめるためにチェックする。
【００３９】
ハッシュ値がそれ自体のアドレスにマッチする場合、サーバーは要求を「標準」サービス・キューに挿入し、そうでない場合、サーバーは要求を「低優先順位」サービス・キューに挿入し、このキューは、異常なルーティングまたはいずれかの一時的な矛盾により誤ってダイレクトされたパケットを吸収するために少量のバッファしか有していない（ステップ５）。「標準」サービス・キュー内の要求は常に「低優先順位」サービス・キューより前にサービスを受け、「標準」キューが空であるときにのみ、「低優先順位」サービス・キューがサービスを受ける。
【００４０】
要求がサーバーによって処理された後、要求された目的物がクライアントに戻される（ステップ６）。要求ルーターとサーバーの間のＨの整合性が維持されると仮定する一般的な場合に、正当な要求は「低優先順位」サービス・キューに挿入されるようにならないことに留意されたい。
【００４１】
このとき、アタッカーがソース・アドレスを、ＩＰアドレスをＩＰアドレス・スペース全体からランダムに選択することによって、スプーフすると仮定する。我々の均一ハッシュ関数Ｈの仮定から、統計的には合計の攻撃トラフィックのわずか
【００４２】
【数４】
2005535021.tif 000006
の割合のみがサーバーでのテストをパスするようになり、標準サービス・キューに挿入されるようになる。攻撃トラフィックの他の
【００４３】
【数５】
2005535021.tif 000007
の割合はテストに失敗するようになり、低優先順位キューに入れられるようになる。低優先順位キューは、誤ってダイレクトされたパケットなど、まれな出来事を処理するために限られた量のバッファしか有していないので、大部分の攻撃トラフィックは静かにドロップされるようになる。したがって、サーバーの貴重なリソースは、攻撃トラフィックによって無駄にされるようにならない。
【００４４】
アタッカーの立場から、これは、サーバーを停止させるためにより多くの攻撃トラフィックを生成しなければならないことを意味する。より正確には、我々のハッシュベース要求ルーティング・メカニズムに基づいたフィルタリングを有する単一のＣＤＮサーバーを停止させるために、そのフィルタリングがないサーバーを停止させるために必要とされるよりも、事実上、Ｏ（ｎ）倍多くの攻撃トラフィックを要する。１つの地域内で協調しているｎ個のこのようなサーバーがあるので、すべてのｎ個のサーバーを同時に停止させてサイトを完全に使用不可能にするために、アタッカーは、単一のサーバーによってホストされたサイトを停止させるために必要とされるよりも、合計でＯ（ｎ２）倍多くの攻撃トラフィックを生成する必要がある。すなわち、ハッシュベース要求ルーティング・アルゴリズムは、ｎ個のサーバーを有するＣＤＮに、シングル・サーバー・サイトと比較して、Ｏ（ｎ２）の回復力を保証する。
【００４５】
真のソースＩＰアドレスを有する膨大な数の要求によりサイトを圧倒しようと試みることは、攻撃のソースを明らかにするので、アタッカーにとって効果がないと判断されるべきであることを想起されたい。また、ステートフル・パケット・フィルタリングは、ＩＰアドレスのセットからのトラフィック内の急増を検出することによって、効果的に攻撃ストリームをブロックすることができる。したがって、アタッカーは、サイトを攻撃中であるとき、ソースＩＰアドレスをスプーフしなければならなくなる。実際には無限の数の候補ハッシュ関数があり、これらの関数は、例えば、あるＩＰアドレスへのサーバーの隣接性または各サーバーの負荷レベルなど、いかなるネットワーク・レベルの情報にも基づかないことを想起されたい。したがって、実際には、アタッカーがマッピングを推測してインテリジェントにＩＰアドレスをスプーフすることは不可能である。
【００４６】
本明細書で説明したスキームは、攻撃による過負荷に対して、単にユーザーの関心が急増する場合とは異なるように反応することを理解されたい。攻撃の場合、理想的には、サーバーは、いかなるアクションも取ることなく着信パケットを無視するべきである。他方では、過負荷の場合、サーバーは、例えば応答時間の増大などのパフォーマンス低下を犠牲にして、すべてのユーザー要求に、到着した順序でサービスしようと試みるべきである。本発明は、攻撃パケットの大部分をドロップし、攻撃パケットのわずかな割合のみがサーバーによって実際に処理されることを可能にすることによって、理想的な動作にほぼ従うが、過負荷の場合は、すべての要求が標準キューに入れられ、最終的に、到着した順序でサーバーによってサービスされるようになる。
【００４７】
フォールト・トレランスおよびロード・バランシングのために、要求ルーターは、複数のサーバー・アドレスによりクライアントの要求に応答することができる。ＤＮＳのように、サーバーの１つが障害により、期待されたサービスを提供することができないとき、クライアントは他のサーバーに接続して目的物を得ようと試みることができる。同時に、応答において接続するためのプライマリ・サーバーをランダム化することによって、単一のサーバーを過負荷にする可能性を減らすことができる。しかし、この方法は、ハッシュベース要求ルーティング・メカニズムの効果に悪影響を及ぼし、これは、このとき単一のＩＰアドレスが多数のサーバーでのテストにパスするようになるからである。したがって、スプーフされたＩＰアドレスを有する攻撃トラフィックがサーバーのハッシュベース・フィルタリングを通過する可能性は、より高くなる。
【００４８】
より正確には、要求ルーターが｛サーバー１，サーバー２，．．．，サーバーｎ｝により、クライアントｘによるウェブ・サイトについてのクエリーに応答する場合、ｘから発信するトラフィックは、リスト内のすべてのｋ個のサーバーで受け入れられなければならない。ｋ個のランダムに選択されたサーバーが各ＩＰアドレスに関連付けられると仮定すると、各サーバーは、ｋ倍多くのアドレスを前述のように正当であるとして受け入れなければならない。ＤＤｏＳ攻撃に関しては、サーバーでのハッシュベース・フィルタリングはこのとき攻撃トラフィックの
【００４９】
【数６】
2005535021.tif 000008
の割合を、このトラフィックの
【００５０】
【数７】
2005535021.tif 000009
の割合の代わりに受け入れる。これは事実上、ハッシュベース要求ルーティング・スキームの回復力をＯ（ｎ２）から
【００５１】
【数８】
2005535021.tif 000010
に悪化させる。
【００５２】
この問題に対処する１つの方法は、サーバーｉｄへのＩＰアドレスの優先順位付き関連付けを有し、可能なときは常にクライアントをプライマリ・サーバーに最初に接続させることである。例えば、アドレスｘについて、サーバー１がプライマリ・サーバーであり、サーバー２がセカンダリであるなどと仮定する。この場合、クライアントｘは最初にサーバー１に接続して目的物を検索しなければならない。サーバー１が使用可能でないときにのみ、クライアントはサーバー２およびリスト内の他のサーバーを順番に試すことができる。サーバーで、我々は、アドレスのセットの異なるタイプの優先順位付き関連付けを作成する。各サーバーは、ｋ＋１レベルを有する優先順位キューを有し、ただし、レベル１は最高の優先順位であると仮定する。パケットの優先順位クラスを、パケットのソース・アドレスに対するサーバーのランクとなるように定義するものとする。サーバーが優先順位クラスｉにおけるアドレスから来るパケットを受信するとき、サーバーはこのパケットを優先順位キュー内のｉ番目のレベルに挿入する。パケットがプロファイル外のアドレスからのものである場合、このパケットは最低の優先順位キューに入れられる。このようにして、サーバーは第１の優先順位アドレスからのパケットを最高の優先順位により処理し、それにより応答時間を最適化する。
【００５３】
実際には、ｋの値は小さくなり、例えばｋ＝２または３となり、優先されたオペレーションのために少量の追加のオーバーヘッドのみが必要となるが、実用的な目的のために必要な冗長性を提供する。
【００５４】
理論上、アタッカーは、その制御下の障害が起きたホストについてのマッピングしか発見することができないが、実際には、アタッカーは他のＩＰアドレスについてのマッピングを、様々なチャネルを介して、例えば、ネットワーク・リンク上の要求ルーターから出て来る応答を盗聴することによって知ることができる。アタッカーはすべての応答を取り込むための、もしくはプローブ・パケットを送信するための、リソースまたは時間を有していない場合があるが、この知るプロセスを、分散された方法で並列に行うこともできることを考慮すると、アタッカーは攻撃の過程において、あるいはフル・スケールの攻撃を開始する前でも、マッピングの大部分を発見する可能性がある。この問題に対処するため、我々は、共有ハッシュ関数Ｈをある間隔の後に定期的に更新し、以前の間隔でアタッカーによって知られたマッピングを無効にすることができる。
【００５５】
詳細には、ＣＤＮサービス・プロバイダはＨのセットを要求ルーターおよびサーバーに先験的に配信する。この「プロビジョニング」により、ＣＤＮサーバーおよび要求ルーターは、攻撃の過程において、ハッシュ関数Ｈを独立して更新することができる。ハッシュ関数Ｈを更新中であるとき、要求ルーターとサーバーの間のハッシュ関数が矛盾する期間が存在する可能性がある。この問題には、「ハンド・オフ」期間を可能にすることによって容易に対処することができ、この時間中に、古いマッピングおよび新しいマッピングが共に認められる。この追加されたレベルの保護により、アタッカーがハッシュ関数Ｈを発見することは著しくより困難になる。
【００５６】
このとき、いずれか１つのサイトに対する攻撃の影響を分離することを目的として、ウェブ・サイトを異なるＣＤＮサーバーに割り振るための様々な戦略を概説する。理想的には我々は、同じＣＤＮによってサービスされている他のサイトが攻撃下にある場合でも、サイトの応答時間およびスループットの低下が可能な限り小さくなるような、サーバーへのサイトの割り振りを望む。割り振り戦略は以下の２つの矛盾する目標に対処するべきであり、これらの目標はすなわち、（１）各ウェブ・サイトについて、サイトにサービスするための多数のＣＤＮサーバーを有することを望むこと、および（２）ウェブ・サイトのいずれかのペアについて、一方がＤＤｏＳの目標である場合、他方は可能な限り最小限のサービスの損失を経験するべきであることである。
【００５７】
第１の目標は、ＣＤＮによってホストされたいかなるサイトのスループットをも最大化し、第２の目標は、ウェブ・サイトをいかなる他のサイトに対する攻撃からも分離させる。このような割り振り戦略は、前述の要求ルーティング・アルゴリズムと組み合わせられるとき、ウェブ・サイトを停止させようと試みるアタッカーによって必要とされる労力、または、ＣＤＮによって同時にホストされた別のウェブ・サイトを攻撃することによって必要とされる労力を、実質的に増す。直観的に、使用可能なキャッシュの大きい割合を、２つの異なる各サイトに割り振ることは、両方のサイトをホストする複数のサーバーにおいて大きいオーバーラップを強制する。このように、あるサイトをホストする複数のサーバーを停止させる攻撃はまた、他のサイトについての大きいサービスの損失をも副次的に引き起こす。したがって、割り振り戦略は、サイトをサーバーに割り当てる際に両方の要件のバランスを取らなければならない。
【００５８】
以下の用語は、サーバー割り振り戦略の問題を形式的に示す。
【００５９】
ＳをＣＤＮサーバーのセットとし、Ｗを、Ｓ内のサーバーに割り振るウェブ・サイトのセットとする。各サイトにつき、ｗ∈Ｗは長さ｜Ｓ｜の２進ベクトルを形成し、ｗがサーバーｉに割り振られる場合、ビットｉが設定される。この｜Ｓ｜の長さのビットのベクトルは、サイトに対する割り振りベクトルと呼ばれる。
【００６０】
標準の用語に従って、２進ベクトルのハミング重みは、ベクトル内の１の数であるように定義される。このように、サイトの割り振りベクトルのハミング重みは、このウェブ・サイトのためのコンテンツをサービスするＣＤＮサーバーの数を表す。これにより、上記の要件を以下のように言い換えることができる。
【００６１】
（１）各サイトの割り振りベクトルは、可能な限り大きいハミング重みを有すること。
【００６２】
（２）いずれか２つのウェブ・サイトｗ１およびｗ２について、ｗ１にサービスするがｗ２にサービスしない（およびその逆の）サーバーの数は可能な限り大きいこと、すなわち、ｓ１およびｓ２がそれぞれ割り振りベクトルｗ１およびｗ２である場合、２進ベクトルのハミング重み
【００６３】
【数９】
2005535021.tif 000011
および
【００６４】
【数１０】
2005535021.tif 000012
は可能な限り大きいこと。
【００６５】
すべてのウェブ・サイトが等しく処理される制限的な場合、すなわち、割り振りベクトルｓ１およびｓ２が等しいハミング重みを有するとき、以下のようになる。
【００６６】
ハミング重み
【００６７】
【数１１】
2005535021.tif 000013
【００６８】
【数１２】
2005535021.tif 000014
【００６９】
ベクトルのハミング重み
【００７０】
【数１３】
2005535021.tif 000015
は、ベクトルｓ１とｓ２の間のハミング距離と呼ばれる。したがって、この制限的な場合、我々は、大きいハミング重みを有するサイトに対する割り振りベクトル、および、我々が複数のベクトルの間の可能な限り大きいハミング距離を有するという制約を発見することを望む。固定数のＣＤＮサーバーが与えられると、割り振り戦略には、可能な限り大きいウェブ・サイトの集まりに対処するために十分な柔軟性がなければならない。したがって、サイト割り振りの問題を以下のように示すことができる。
【００７１】
ＣＤＮサーバーの数ｎが与えられると、我々は、それぞれ長さｎの多数の２進ベクトルを、各ベクトルがそれぞれ正確にｈのハミング重み（可能な限り大きい）を有するように、かつ、複数のベクトルの間のペアワイズ・ハミング距離ｄが可能な限り大きいように、列挙するための効率的なアルゴリズムを望む。
【００７２】
このようなアルゴリズムは順次、このようなｎビット・ベクトルを生成し、これらのベクトルを、各ウェブ・サイトに対する割り振りベクトルとして割り当てることができる。次いで、このアルゴリズムは、各ウェブ・サイトが可能なｎ個内からのｈ個のＣＤＮサーバーによってサービスされることを保証する。特定のサイトに対応するサーバーがすべて、サービス妨害攻撃により動作不能にされる場合、他のいかなるサイトも、少なくとも
【００７３】
【数１４】
2005535021.tif 000016
のサーバーによってサービスされることが保証される。したがって、このような割り振りの下では、各ウェブ・サイトは使用可能な容量の
【００７４】
【数１５】
2005535021.tif 000017
を利用し、いずれか１つのウェブ・サイトが停止させられるときに結果として生じるサービスの損失は、多くとも
【００７５】
【数１６】
2005535021.tif 000018
１００パーセントである。
【００７６】
以前に述べた要件から、パラメータｈおよびｄを可能な限り大きくし、すべてのウェブ・サイトをカバーするために十分なベクトルを存在させることが望ましくなる。次に、我々が対処することができる合計数のウェブ・サイトｍを最大化すると共に、ｈおよびｄを最大化しようと試みる、一般的な割り振り方法を概説する。後に、ｍについて固定の値が与えられ、他のパラメータｈおよびｄを最適化することを望む場合など、他の可能性を考察する。
【００７７】
本発明では、割り振り戦略は符号化理論からの結果の適応であり、この符号化理論は、複数のベクトルの間で保証されたハミング距離を有する（必ずしも同じハミング重みを有するとは限らない）多数の２進ベクトルを生成するための、効率的なアルゴリズムの研究である。形式的には、長さｎおよび最小距離ｄの符号は、いずれか２つのベクトルの間のハミング距離が少なくともｄであるような、長さｎの２進ベクトルの集まりである。符号を割り振りベクトルに変換するための様々なアルゴリズムが提示される。我々の考察では、実際の符号の詳細なしに、一般的な構成を概説する。
【００７８】
一般に、すべての符号語が正確に固定ハミング重みを有する、多数のベクトルを有する符号を定義することは、符号化理論において困難な問題である。定数ハミング重み符号語を生成するために存在する少数の符号は、定数重み符号と呼ばれ、一般に、少ない（通常は、符号の長さにおける多項式）数の符号語のみを生じる。より多数のウェブ・サイトに対処するため、我々は、任意の符号を取り、それらの符号を除去して、我々の仕様に適合する２進ベクトルを生じるアルゴリズムを検討する。割り振り戦略での我々の最初のカットは、以下の単純なアルゴリズムである。
【００７９】
アルゴリズム１：大きい最小距離ｄを有する長さｎの符号を定める。ハミング重みｈの十分な符号語があるように、パラメータｈを選択する。割り振りベクトルを列挙するための単純な戦略は、正確にｈのハミング重みを有するすべての２進ベクトルを生成し、符号語である、すなわち、符号に属するベクトルのみを出力することである。
【００８０】
このアルゴリズムの説明では、我々はｄまたはｈについて特定の値を定めていないことに留意されたい。これを行うために、我々は最初に、パラメータｄを定める符号のファミリーからの符号を定める。我々が符号または符号のファミリーを定めた後、これは、符号内のベクトルのハミング重みにおける分布を定義する。次いで、パラメータｈは、このハミング重みの分布に基づいて少なくともｍ個のウェブ・サイトについての割り振りを有するように選択される。
【００８１】
パラメータｈおよびｄについてよい値を発見するほかに、我々はまた、符号語を列挙するための明示的構成および効率的アルゴリズムを有する符号を使用することも望む。符号語を識別するための容易なアルゴリズムを有する、特によい符号のクラスは、線形符号のクラスである。これには、リード・ソロモン符号など、他の分野において多数の応用例を有するいくつかの符号が含まれる。
【００８２】
我々は線形符号を、線形部分空間を形成する長さｎのベクトルのセットとなるように定義し、すなわち、ｃ１およびｃ２が符号語である場合、
【００８３】
【数１７】
2005535021.tif 000019
は符号語である。（ｎ，ｋ，ｄ）線形符号は、最小距離ｄを有する長さｎの線形符号であり、線形部分空間の次元はｋである。このような線形符号は、生成行列と呼ばれるｋｘｎの２進行列Ｇによって定義され、符号語のセットはｘｘＧによって得られ、ただし、ｘは長さｋのすべての２進ベクトルの範囲に渡る。
【００８４】
この考察で使用する線形符号についてのいくつかの基本的事実を想起されたい。最初に、線形符号は、任意のハミング重みを有する符号語を生じる。線形符号に属する語を生成するためのアルゴリズムは簡単であり、すなわち、長さｋのベクトルを順次列挙し、生成行列Ｇによって乗算する。別法として、線形符号はまたそのシンドローム行列Ｃによっても定義され、このシンドローム行列Ｃは（ｎ−ｋ）ｘｎの２進行列であり、ｘｘＣＴ＝０である場合にのみ、長さｎの語ｘはこの符号に属する。これを使用して、割り振りベクトルを発見するための我々の次の改良点は、以下の通りである。
【００８５】
アルゴリズム２：大きい最小距離ｄを有する（ｎ，ｄ，ｋ）線形符号を定める。次いで、ハミング重みｈのすべての２進ベクトルを組織的に生成し、ｘｘＣＴ＝０であるような語ｘのみを保持する。別法として、長さｋのベクトルｙを列挙し、符号語をｙｘＧとして生成し、ハミング重みｈを有する符号語のみを保持することができる。
【００８６】
再度、前述のように、パラメータｄおよびｈは、最初に、ｄを定義するための線形符号のファミリーを定めることによって選択される。符号が定められた後、この符号内でハミング重みｈを有する符号語の数を最大化するように、ｈが選択される。
【００８７】
いくつかの実際の符号およびそれらが生じるパラメータについての詳細を提供する前に、割り振りベクトルを符号から得るためのもう１つの一般的なスキームを説明する。このスキームでは、ｈの任意の値を選択するのではなく、我々は、ｈに対する特によい値に焦点を合わせようと試みる。ｈに対して大きすぎる値を選択する場合、ハミング重みｈのベクトルは少数しかなく、よってハミング重みｈの符号語は少数しかないことに留意されたい。また、ｈに対して大きすぎる値を選択することは、最大距離（大きくともｎ−ｈとなる可能性がある）は小さくなるであろうことを含意する。他方では、ｈに対して小さすぎる値を選択する場合、各ウェブ・サイトは多くともｈ個のＣＤＮサーバーによってサービスされ、したがって容量が無駄にされる結果となる。この観点から、ｈに対する特に有望な値は
【００８８】
【数１８】
2005535021.tif 000020
である。これは、それに対して最大数の２進ベクトルがあり、よって潜在的に多数の符号語がある値である。このｈの選択では、以下の技術を使用することができ、この技術は、符号の長さに関して少々無駄であるが、正確なハミング重みの語を生じる。
【００８９】
アルゴリズム３：最小距離ｄを有する長さｎの符号Ｃを定める。修正された符号Ｃ’を、各符号語ｃ∈ＣについてＣ’が２ｎの長さの語を含み、
【００９０】
【数１９】
2005535021.tif 000021
であるように、定義する。
【００９１】
修正された符号Ｃ’では、そのように生成された各符号語は長さ２ｎを有する。さらに、修正された符号における各符号語は、正確にｎ（符号の長さの半分）の重みを有し、Ｃ’における語の最小距離は少なくとも２ｄである。これは、いずれかの符号を使用して
【００９２】
【数２０】
2005535021.tif 000022
による定数ハミング重みの語を生じるための手早い方法である。Ｃの候補としてよい符号を選択する場合、このアルゴリズムは多数の割り振りベクトルを生じ、これは、Ｃにおける各符号語が次いで割り振りベクトルに変換されるからである。
【００９３】
これらのアルゴリズムは、符号を、ＣＤＮサーバーへのウェブ・サイトのための割り振り戦略に変換するための、一般的な方法である。よい符号を、上記で概説した構成につなげることで、よい割り振り戦略が生じる。我々はまた、同意義が他の方向に有効であり、すなわち、いかなる割り振り戦略も符号に変換することができることにも注目する。ｍ個の各ウェブ・サイトを、ｎ個内からのｈ個のＣＤＮサーバーに割り振り、攻撃下にないウェブ・サイトが、そのＣＤＮサーバーの少なくともｆの割合をなお動作中にすることが保証されるようにするための戦略を有した場合、割り振りベクトルは、少なくともｍ個の符号語を有する、ｎの長さの定数重み符号（重みｈ）および最小距離２ｆｈを形成する。この同意義は、あるパラメータを有する割り振り戦略が可能であるかどうかを検討するために有用であり、すなわち、ｈに対する値および距離ｄが与えられると、そのような符号において可能な最大数の符号語を（ｎの小さい値に対して）リストする、いくつかのテーブルがある。
【００９４】
このとき、異なるパラメータに対して実際の値を使用して、割り振りを実際にどのように実行することができるかの一例を考察する。我々が考察する例は、１００個のウェブ・サイトをＣＤＮによってホストされるようにし、いかなるときも、攻撃下にないウェブ・サイトがＣＤＮ内の３個のサーバーによってサービスされるという保証を有する場合である。言い換えると、この問題は、ｍ＝１００かつ最小距離ｄ＝６が与えられると、我々はｎおよびｈに対する最適な値を発見することを望むということである。
【００９５】
最初のステップは、それに対して距離ｄ＝６かつ少なくともｍ＝１００個の符号語を有する符号がある、ｎの最小値を発見することである。標準のテーブルを調べると、ｎに対する最小の可能な値は１５であることがわかるであろう。
【００９６】
最初の割り振り戦略は、ハミング重み８および長さｎ＝１６を有する約１２８個の符号語を生じる、非常に専門化された非線形符号を使用することである。これにより、難解な非線形符号を使用したかなり最適な割り振り戦略が得られる。
【００９７】
もう１つの割り振り戦略を、リード・ソロモン符号をアルゴリズム２で使用して得ることができる。我々が使用する特定のリード・ソロモン符号は、長さｎ＝２１で、ｄの距離＝５であり、５１２個の符号語を生じるものである。各ハミング重みの符号語の数を検査して、我々は、符号語の分布が重み１０および１１で最大化されることを発見する。我々はｈ＝１１を選択し、１２６個の符号語を生じる重み１１の符号語のみを選択する。これらの定数重み語では、距離（均一でなければならない）は実際には６であり、我々が必要とするパラメータに一致する。
【００９８】
わずかに最適さに欠けるが簡単である割り振りは、アルゴリズム３を使用して符号Ｃを、長さ１５および距離３のハミング符号となるように選択することである。ハミング符号はとても単純なエンコード・アルゴリズム、および、多数であるが３の距離しか有さない符号語を有する。我々が選択したパラメータでは、ハミング符号は２０４８個の符号語を有する。この符号をアルゴリズム３につなげると、容易に実施可能な割り振り戦略が得られ、ただしｎ＝３０であり、各ウェブ・サイトは少なくとも１５個のＣＤＮサーバーに割り当てられる。最適ではないが、この符号は多数の符号語を生じ、それにより、必要とされる場合により多くのウェブ・サイトに拡張するための柔軟性が得られる。
【００９９】
我々は、割り振りにおけるトレードオフを例示するためにこれらの符号を選択した。最適な符号は一般に、複雑なエンコード・アルゴリズムを有して非線形となる傾向がある。リード・ソロモン符号など、符号についての簡単な選択により、わずかに最適さに欠けるｎの値が得られる。符号およびｎを定めた後、ｈに対する最適な値は約
【０１００】
【数２１】
2005535021.tif 000023
となる傾向がある。この例で使用した符号は、多数の可能な選択のうちの少数に過ぎない。
【０１０１】
次に、異なるシナリオ、すなわち、パラメータｍ、ｈおよびｄの異なるクラスについて対処する、いくつかの可能な割り振り戦略を論じ、それらの割り振り戦略が提供することができる保証を列挙する。本明細書で提示する事例は、たくさんのパラメータを表し、決して排他的であるように意味されないことを理解されたい。表１は、本明細書で提示した符号を使用するサイト割り振り戦略を要約する。
【０１０２】
【表１】
2005535021.tif 000024
【０１０３】
我々が考察する第１の事例は、ウェブ・サイトの数ｍがＣＤＮサーバーの数ｎと比較して小さいときである。ｍが（２ｎ−２）より小さい事例では、我々はアダマール符号のサブセットを使用し、ＣＤＮサーバーの回復力において非常によい保証を得ることができる。アダマール符号は
【０１０４】
【数２２】
2005535021.tif 000025
の線形符号であり、２ｎ個の符号語を含む。ｎが２のべき乗であるとき、１つだけ除いて全部の行が正確に
【０１０５】
【数２３】
2005535021.tif 000026
のものを有するように、アダマール符号を再帰的に構成することができる。したがって、この構成により、
【０１０６】
【数２４】
2005535021.tif 000027
のハミング重みをそれぞれ有する２ｎ−２個の２進ベクトルを、最小のペアワイズ距離が
【０１０７】
【数２５】
2005535021.tif 000028
であるように、構成することができる。これを割り振りベクトルのセットとして使用すると、各サイトを
【０１０８】
【数２６】
2005535021.tif 000029
個のサーバーに割り当てることができ、別のウェブ・サイトをホストするすべてのサーバーがＤＤｏＳ攻撃により使用不可能になる場合でも、常に少なくとも
【０１０９】
【数２７】
2005535021.tif 000030
個のサーバーによってサイトがサービスされるようになるという保証を有することができる。したがって、この割り当ては、５０％に過ぎないサービスの損失を有するようになることを保証する。ｍの小さい値では、したがって、ＣＤＮの回復力において非常によい保証を得ることができる。
【０１１０】
パラメータの最適化のほかに、我々は、割り振りベクトルの効率的な構成を有することを望む。大きい最小距離、および、符号語を構成するための効率的なアルゴリズムを有する非常に汎用的なよい符号のクラスは、リード・ソロモン符号である。リード・ソロモン符号は通常、大きいアルファベットに対して最良のパラメータを生じるが、ここで我々は、これらの符号の２進バージョンにのみ焦点を合わせる。リード・ソロモン符号は、以下のパラメータを有する線形符号である。すなわち、ｓ≦ｒ≦ｑであるようないずれかの整数ｑ、ｒおよびｓについて、
【０１１１】
【数２８】
2005535021.tif 000031
のリード・ソロモン符号がある。パラメータを慎重に選択し、上述のアルゴリズム３の技術を使用して、ｎが与えられると、リード・ソロモン符号を使用して、少なくとも
【０１１２】
【数２９】
2005535021.tif 000032
である最小距離を有する、指数関数的な数
【０１１３】
【数３０】
2005535021.tif 000033
の符号語を列挙することができ、ただしｃ１およびｃ２は定数である。このように、他のウェブ・サイトが攻撃下にあり、それらのサイトがホストされるＣＤＮサーバーを動作不能にするときでも、サービスにおいてｌｏｇ（ｎ）係数ドロップを超えるものを被るウェブ・サイトがなくなることを保証することができる。サービス保証におけるｌｏｇ（ｎ）係数ドロップが高い間、そのように得られる割り振りアルゴリズムは容易に実施可能である。
【０１１４】
少数のウェブ・サイトの場合によい割り振り戦略を生じるアダマール符号のように、よい割り振り戦略に変換することができるいくつかの他の符号がある。しかし、より高度な符号化方法を使用する間には注意するべきであり、これは通常、より高度な符号化技術はエンコードのための複雑なアルゴリズムを有し、最良のパラメータはｎの大きい値について得ることができるからである。よいパラメータを生じる１つのこのような符号のファミリーは、ジュステセン符号である。これらの符号を上述のアルゴリズム３につなげると、各ウェブ・サイトが
【０１１５】
【数３１】
2005535021.tif 000034
個のＣＤＮサーバーに割り振られる、指数関数的な数の割り振りベクトルを生じる、割り振りアルゴリズムが得られ、そこで我々は、攻撃下にないウェブ・サイトは、別のウェブ・サイトが攻撃下にある場合でも、多くともサービスの（小さい）定係数損失しか被らないようになることを、保証することができる。
【０１１６】
これまで、異なる範囲のパラメータに対してよい結果を生じる少数の符号の例に基づく割り振り戦略を列挙した。実際には、選択される実際の符号は完全に、パラメータｎ、ｍの実際の値、ならびに、ｈおよびｄに対する所望の値によって決まる。割り振りベクトルに変換するための符号を発見するための最初のステップは、実現可能性を調査することである。例えば、ｎに対して特定の値が与えられると、ｄの様々な値についての符号語の数のための上限についてのテーブルに、ｎの小さい値のためのこれらの限界をリストする標準のテーブルを使用して、アクセスすることができる。これにより、ｄの異なる値に対して割り振ることができるウェブ・サイトの最大数が直接得られる。同様に、ｎのより大きい値では、いずれかの符号の距離における一般的な上限を使用して、所与のｎおよびｍのある値を除くことができる。値の特定の選択がこれらの境界によって除外されないからということだけで、所与のパラメータに対する符号を発見することができることを含意しないことに留意されたい。
【０１１７】
これまで、単一のサービスのクラスがあるとき、すなわち、すべてのウェブ・サイトが等しく扱われるときの事例のみを考察した。割り振りの回復力から符号の距離への間の直接の関係は、割り振りベクトルのハミング重みが同じであるときにのみ可能である。実際には、ＣＤＮを構築中である間、我々は、差別化されたサービスのレベルを提供するために多数のサービスのレベルを必要とする場合がある。
【０１１８】
サービスのｋのレベルを扱うため、割り振り問題は、ｋ個のセットの２進ベクトルＳ１，．．．，Ｓｋを発見することの１つとなり、ただし、各セットは同じハミング重みのベクトルを含んで、任意のセットに属するいかなる２つのベクトルｕおよびｖについても、我々はこれらのベクトルのハミング重み
【０１１９】
【数３２】
2005535021.tif 000035
および
【０１２０】
【数３３】
2005535021.tif 000036
が可能な限り大きいことを必要とするようにする。この要件は前述と同じであるが、式のハミング重み
【０１２１】
【数３４】
2005535021.tif 000037
ハミング重み
【０１２２】
【数３５】
2005535021.tif 000038
ハミング重み
【０１２３】
【数３６】
2005535021.tif 000039
はもはや有効ではない。すなわち、回復力はもはや距離とは直接関係がない。このように、割り振りアルゴリズムはもはや、符号の構成を直接使用することができない。非常に簡単に描くとき、我々はなお、符号を使用した多数のサービスのクラスについての割り振りを発見することがきる。最初に、我々は符号語を微調整して、符号のハミング距離が、我々の望む分離プロパティにおける保証を生じるようにしなければならない。これを達成するためのいくつかの可能な方法があり、ここで我々は非常に基本的なスキームを概説する。
【０１２４】
符号語を微調整して十分な分離を得るための最初の基本的方法は、以下の通りである。すなわち、ｎの長さの符号語を２ビットのブロックに分割し、各２ビット・ブロックを５ビット・ブロックにエンコードし、これを、残りの３ビットを使用して、２ビット・ブロックのハミング重み（０、１または２）をそれぞれ３番目、４番目または５番目のビットにおける１によって記録することによって行う。この微調整では、２つの２ビット・ブロックｘおよびｙがゼロでないハミング距離を有する場合、ベクトル
【０１２５】
【数３７】
2005535021.tif 000040
および
【０１２６】
【数３８】
2005535021.tif 000041
は共に少なくとも１のハミング重みを有し、ただし、ｘ’およびｙ’はｘおよびｙの微調整されたバージョンである。したがって、２つのｎビット・ベクトルｕおよびｖが少なくともｄのハミング距離を有する場合、それらの微調整されたバージョンｕ’およびｖ’は少なくとも
【０１２７】
【数３９】
2005535021.tif 000042
の分離を有する。微調整されたバージョンは、
【０１２８】
【数４０】
2005535021.tif 000043
の長さを有する。これは非常に基本的なスキームであり、距離ｄの符号語を、少なくとも
【０１２９】
【数４１】
2005535021.tif 000044
の分離を有する２進ベクトルに変換するものである。しかし、ブローアップはかなり大きく、符号の長さは著しく上昇する。符号の長さを拡張することによって、類似の方法で符号を、回復力に富む割り振りに変換する、いくつかの他のスキームがある。例えば、距離ｄのリード・ソロモン符号の長さを２倍にし、わずかな微調整を使用することによって、我々は、ｄの分離保証を提供する２進ベクトルを得ることができる。
【０１３０】
符号語を微調整して、分離においてよい保証を提供するベクトルを得るための、このようなスキームを使用して、制限された事例についてのアルゴリズムに類似した割り振り戦略を定義することができる。この方法は類似であり、すなわち、十分な距離を有する符号Ｃを選択し、十分な分離を有する２進ベクトルを得るために微調整する。重みｈ１，．．．，ｈｋの値を、これらのハミング重みを有する微調整された符号において十分な語があるように、選択する。重みｈ１，．．．，ｈｋを有する符号語の異なるセットは、異なるレベルのサービスに対する割り振りベクトルを定義する。前述のように、実際の重みの選択は符号の選択によって決まる。サービス・レベルの数、すなわちｋの値、および、異なるサービスのレベルにおいて必要とされた差別化の量は、ハミング重みの選択において追加の制約を課す。しかし、最初によい符号を選択し、符号語を割り振りベクトルに変換する一般的な戦略は、この設定において同様にうまくいく。
【０１３１】
上述のハッシュベース要求ルーティング・アルゴリズムは、クライアントＩＰアドレスを地域内のＣＤＮサーバーに一意にマップするハッシュ関数に基づいて、偽りのパケットと正当なパケットとを区別する。しかし、サイト割り振りアルゴリズムの導入により、この要求ルーティング・アルゴリズムはクライアントをＣＤＮサーバー識別子に、クライアントのアドレス、および、クライアントがアクセスすることを望むウェブ・サイトにも基づいて、マップしなければならない。これは、ハッシュ関数を各カスタマー・ウェブ・サイトに対して導入することによって、実施することができる。それでも、ハッシュベース要求ルーティングの効果は低下される場合があり、これは、ＣＤＮサーバーが、要求されているサイトを指示しないパケット（例えば、ＴＣＰ  ＳＹＮパケット）を受信するとき、どのハッシュ関数を適用するべきであるかを知らない場合である。
【０１３２】
我々が強制的にクライアントに、接続を確立するために最初のＳＹＮを送信中であるときにどのサイトが要求されているかをＣＤＮサーバーに通知させることができる場合、我々はこの問題に対処することができる。１つの単純な方法は、要求ルーターによって戻されたＩＰアドレス内のサイト情報をエンコードすることである。具体的には、要求ルーターは、そのネットワーク部分がＣＤＮサーバーの真のネットワーク・アドレスを含むが、ホスト部分は（サイト、サーバーｉｄ）のエンコードを含む、アドレスにより応答する。
【０１３３】
例えば、サイトＡにとって接続するべきＣＤＮサーバーが１９２．１９．１．１３である場合、要求ルーターは１９２．１９．２１２．９により応答することができ、ここでネットワーク・アドレス１９２．１９．０．０／１６は同じであるが、アドレスのホスト部分２１２．９は、サイトＡおよびサーバーｉｄについてのエンコードされた情報である。クライアントが初期ＳＹＮパケットを送信するとき、このパケットは、ＣＤＮサーバー・クラスターがある１９２．１９．０．０／１６サブネットにルーティングされるようになる。エントリー・ポイントで、スイッチ（例えば、高速ＮＡＴボックスまたはレイヤ４スイッチ）を使用して、このパケットは正しいサーバーにスイッチされ、このスイッチは通常、複数のＣＤＮサーバーに渡ってロード・バランシングを実行する。このスキームでは、スイッチはパケットをＣＤＮサーバーへ、（サイト、サーバーｉｄ）エンコードに基づいて転送し、サーバーはハッシュ関数を計算して、そのパケットが正当であるかどうかを判断することができる。別法として、ＣＤＳＰは、ハッシング機能性をスイッチと同じ場所に配置して、偽りのパケットをより早期にフィルタリングして除くことができる。このスキームは、クライアントに透過的であることにおいて魅力的であるが、サーバーの少数のクラスターを各地域内に配置するＣＤＳＰに適用可能である。
【０１３４】
本発明の例示的実施形態を本明細書で、添付の図面を参照して説明したが、本発明はこれらの厳密な実施形態に限定されないこと、および、様々な他の変更および修正は、本発明の範囲または精神から逸脱することなく、当業者によってその中において影響を受ける可能性があることを理解されたい。
【図面の簡単な説明】
【０１３５】
【図１】例示的コンテンツ配信ネットワークを例示する図である。
【図２】本発明の一実施形態によるハッシュベース要求ルーティング技術を示す図である。
【図１】
2005535021.tif 000045
【図２】
2005535021.tif 000046
【国際調査報告】
2005535021.tif 000047