(57)【特許請求の範囲】
【請求項１】
プロセッサと前記プロセッサに通信可能に接続されたメモリとを含むデータ処理モジュールを含み、前記データ処理モジュールは、冗長性除去（ＲＥ）処理機能のセットをサポートするように構成され、前記データ処理モジュールは、
第１のパケット・クラスに関連する第１のパケットに対して、一又は複数のＲＥ処理機能を含む第１のＲＥ処理機能のセットを実行し、
第２のパケット・クラスに関連する第２のパケットに対して、一又は複数のＲＥ処理機能を含む第２のＲＥ処理機能のセットを実行し、
前記第１のＲＥ処理機能のセットと前記第２のＲＥ処理機能のセットとは異なる
ように構成される、装置。
【請求項２】
前記データ処理モジュールは、ＲＥ符号化モジュールまたはＲＥ復号モジュールを含む、請求項１に記載の装置。
【請求項３】
前記データ処理モジュールは、複数のデータ処理モジュールのうちの１つであり、前記プロセッサは、
前記第１のパケットの前記第１のパケット・クラスに関連する前記複数のデータ処理モジュールの順序付きリストを判定し、
前記複数のデータ処理モジュールの前記順序付きリスト内の前記データ処理モジュールの位置に基づいて、前記第１のＲＥ処理機能を判定する
ように構成される、請求項１に記載の装置。
【請求項４】
前記プロセッサは、前記第１のパケット内に含まれる情報に基づいて、前記第１のパケットの前記第１のパケット・クラスに関連する前記複数のデータ処理モジュールの前記順序付きリストを判定するように構成される、請求項３に記載の装置。
【請求項５】
前記データ処理モジュールは、
前記データ処理モジュールが前記複数のデータ処理モジュールの前記順序付きリスト内の最初の位置にあるという判定に基づいて、
前記第１のパケットを前記データ処理モジュールに関連するコンテンツ・ストアに格納し、
前記データ処理モジュールに関連する前記コンテンツ・ストアおよび前記データ処理モジュールに関連する指紋テーブルを使用して、前記第１のパケットについてＲＥ符号化機能を実行する
ように構成される、請求項３に記載の装置。
【請求項６】
前記データ処理モジュールは、
前記データ処理モジュールが、前記複数のデータ処理モジュールの前記順序付きリスト内の最初の位置以外の位置にあるという判定に基づいて、
前記データ処理モジュールに関連するコンテンツ・ストアに前記第１のパケットを格納せずに、前記データ処理モジュールに関連する前記コンテンツ・ストアおよび前記データ処理モジュールに関連する指紋テーブルを使用して、前記第１のパケットについてＲＥ符号化機能を実行する
ように構成される、請求項３に記載の装置。
【請求項７】
前記データ処理モジュールは、
前記データ処理モジュールが、前記複数のデータ処理モジュールの前記順序付きリスト内の最後の位置以外の位置にあるという判定に基づいて、
前記データ処理モジュールに関連するコンテンツ・ストアに前記第１のパケットを格納せずに、前記コンテンツ・ストアを使用して、前記第１のパケットについてＲＥ復号機能を実行する
ように構成される、請求項３に記載の装置。
【請求項８】
前記データ処理モジュールは、
前記データ処理モジュールが、前記複数のデータ処理モジュールの前記順序付きリスト内の最後の位置にあるという判定に基づいて、
前記データ処理モジュールに関連するコンテンツ・ストアを使用して、前記第１のパケットについてＲＥ復号機能を実行し、
前記第１のパケットを前記データ処理モジュールに関連する前記コンテンツ・ストアに格納する
ように構成される、請求項３に記載の装置。
【請求項９】
プロセッサとメモリとを含み、冗長性除去（ＲＥ）処理機能のセットをサポートするように構成されたデータ処理モジュールで、
第１のパケット・クラスに関連する第１のパケットに対して、一又は複数のＲＥ処理機能を含む第１のＲＥ処理機能のセットを実行し、
第２のパケット・クラスに関連する第２のパケットに対して、一又は複数のＲＥ処理機能を含む第２のＲＥ処理機能のセットを実行し、
前記第１のＲＥ処理機能のセットと前記第２のＲＥ処理機能のセットとは異なる、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には通信ネットワークに関し、排他的ではなくより具体的には、通信ネットワークでの冗長性除去の提供に関する。
【背景技術】
【０００２】
多くの企業が、クラウドベースのサービスの採用を目指しつつある。多くの企業にとって、ミドルボックスは、企業ネットワークの重要なコンポーネントの１つである。したがって、複数のクラウド・プロバイダおよびサード・パーティ・サービス・プロバイダが、クラウド内のサービスとして（または仮想機器として）ミドルボックスを提供している。一般的に使用されているミドルボックスの１タイプが、広域ネットワーク（ＷＡＮ）最適化ミドルボックス（ＷＡＮ最適化が通常は冗長性除去（ＲＥ：Ｒｅｄｕｎｄａｎｃｙ  Ｅｌｉｍｉｎａｔｉｏｎ）機能を含むことを考慮して、ＲＥミドルボックスと称する場合もある）である。一般に、ＷＡＮ最適化ミドルボックスは、トラフィック内の重複するコンテンツを抑制し、帯域幅節約を提供すると同時にアプリケーション性能を改善することもできる。ある企業のＷＡＮ最適化ミドルボックスを、その企業とクラウドとの間、または分散設定でその企業によって使用される２つのクラウド・サイトの間に展開することができる。多くの場合に、ウェブ・サーバのようなアプリケーションと同様に、ＷＡＮ最適化ミドルボックスのプロバイダまたはユーザがトラフィック需要に従ってコストがかかる、そのようなＷＡＮ最適化ミドルボックスのためのペイ・パー・ユース（ｐａｙ−ｐｅｒ−ｕｓｅ）能力を有することが望ましい。企業によるクラウドベースのサービスの採用が増え続けるにつれて、より大量のトラフィックを処理するためにＷＡＮ最適化ミドルボックスをスケーリングできることが望ましくなりつつある。
【発明の概要】
【課題を解決するための手段】
【０００３】
従来技術のさまざまな欠点は、冗長性除去ミドルボックスをスケーリングする実施形態によって対処される。
【０００４】
一実施形態では、装置は、プロセッサとプロセッサに通信可能に接続されたメモリとを有するデータ処理モジュールを含み、データ処理モジュールは、受け取られたパケットのパケット・クラスに基づいて複数の冗長性除去（ＲＥ）処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定するように構成される。
【０００５】
一実施形態では、方法は、プロセッサとメモリとを含むデータ処理モジュールで、複数の冗長性除去（ＲＥ）処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定するステップを含み、判定するステップは、受け取られたパケットのパケット・クラスに基づく。
【０００６】
一実施形態では、装置は、プロセッサとプロセッサに通信可能に接続されたメモリとを有するデータ処理モジュールを含み、データ処理モジュールは、分散ハッシュ・テーブル（ＤＨＴ）のうちでデータ処理モジュールに関連する部分に基づいて、受け取られたパケットについて冗長性除去（ＲＥ）処理機能を実行するように構成される。
【０００７】
一実施形態では、装置は、プロセッサおよびプロセッサに通信可能に接続されたメモリを有するデータ処理モジュールを含み、データ処理モジュールは、パケットの冗長性除去（ＲＥ）処理を実行するために少なくとも１つの他のデータ処理モジュールと協力するように構成される。
【０００８】
本明細書の教示は、添付図面に関連して以下の詳細な説明を検討することによって、たやすく理解することができる。
【図面の簡単な説明】
【０００９】
【図１】冗長性除去（ＲＥ）機能をサポートする例示的なクラウドベースの通信システムを示す高レベル・ブロック図である。
【図２】最大一致（ｍａｘ−ｍａｔｃｈ）ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す図である。
【図３】最大一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す図である。
【図４】３つの符号器を有する例示的なＲＥ符号化ミドルボックスおよび３つの復号器を有する例示的なＲＥ復号ミドルボックスの異なる処理ステージにまたがるＲＥ機能の例示的な分散を示す図である。
【図５】チャンク一致（ｃｈｕｎｋ−ｍａｔｃｈ）ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す図である。
【図６】チャンク一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す図である。
【図７】ＤＨＴベースの最大一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す図である。
【図８】ＤＨＴベースの最大一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す図である。
【図９】ＤＨＴベースのチャンク一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す図である。
【図１０】ＤＨＴベースのチャンク一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す図である。
【図１１】ＲＥをサポートするパケットの処理の方法の一実施形態を示す図である。
【図１２】本明細書で説明される機能を実行する際の使用に適するコンピュータを示す高レベル・ブロック図である。
【発明を実施するための形態】
【００１０】
理解を容易にするために、可能な場合には、複数の図面に共通する同一の要素を指定するのに、同一の符号を使用した。
【００１１】
一般に、冗長性除去（ＲＥ）能力は、通信ネットワーク内でＲＥミドルボックスをスケーリングするために提供される。
【００１２】
少なくともいくつかの実施形態では、ＲＥ能力は、ＲＥの処理をスケーリングすると同時に、ＲＥがＲＥミドルボックス・インスタンスの一部またはすべてのコンテンツ履歴を使用することを可能にする。その結果、ＲＥ能力の少なくともいくつかの実施形態は、ＲＥミドルボックスのストレージ能力と処理能力との両方を効果的にスケーリングする。
【００１３】
本明細書では主に、クラウドベースの通信システム内でのＲＥ能力の提供（たとえば、広域ネットワーク（ＷＡＮ）を介するクラウド・サイトの間の通信に関する）の文脈で図示され、説明されるが、ＲＥ能力のさまざまな実施形態を、冗長性除去が必要であるか望ましい可能性がある他のタイプの通信システム内で利用することができることに留意されたい。
【００１４】
図１に、冗長性除去（ＲＥ）機能をサポートする例示的なクラウドベースの通信システムの高レベル・ブロック図を示す。
【００１５】
図１に示されているように、クラウドベースの通信システム１００は、広域ネットワーク（ＷＡＮ）１２０を介して通信できる第１のクラウド・サイト１１０１および第２のクラウド・サイト１１０２（集合的にクラウド・サイト１１０）を含む。クラウド・サイト１１０は、ＷＡＮ  １２０を介するクラウド・サイト１１０の間のデータの転送のさまざまな態様を最適化するためのＷＡＮ最適化をサポートするように構成される。ＷＡＮ最適化の一部として、クラウド・サイト１１０は、第１のクラウド・サイト１１０１から第２のクラウド・サイト１１０２へのＷＡＮ  １２０を介するデータの転送における冗長性を除去するためにＲＥ機能をサポートするように構成される（しかし、クラウド・サイト１１０が、その代わりにまたはやはり、第２のクラウド・サイト１１０２から第１のクラウド・サイト１１０１へのＷＡＮ  １２０を介するデータの転送のさまざまな態様を最適化するためにＷＡＮ最適化をサポートするように構成され得ることを理解されたい）。より具体的には、第１のクラウド・サイト１１０１は、ＲＥ符号化ミドルボックス１１２Ｅを含み、第２のクラウド・サイトは、ＲＥ復号ミドルボックス１１２Ｄを含む。ＷＡＮ  １２０は、クラウド・サイト１１０の間のデータの伝搬をサポートするのに適切な任意のタイプの通信ネットワークとすることができる。
【００１６】
一般に、ＷＡＮ最適化機能は、通常、冗長性除去（ＲＥ）機能ならびに他のタイプの機能を含む。異なるＷＡＮ最適化解決策は、ＲＥ機能性が実施される形において異なる可能性があるが、基本的なＲＥ方法論は、ほとんどの場合に類似する。一般に、ＲＥは、それぞれ冗長データの転送を減らしまたは除去する形でデータ・アイテムを符号化し、復号するように構成された符号化ミドルボックスおよび復号ミドルボックスを含むＲＥミドルボックスの対を使用して提供される。データ・アイテムは、パケット、パケットの一部（本明細書ではチャンクと称する場合もある）など、ならびにそのさまざまな組合せを含むことができることに留意されたい。
【００１７】
一般に、符号化ミドルボックスは、オリジナル・パケットを受信し、オリジナル・パケットを符号化された（より小さい）パケットに符号化し、符号化されたパケットをネットワークを介して伝搬させる。符号化ミドルボックスは、通常、２つの構造すなわち、指紋テーブルおよびコンテンツ・ストアを維持する。指紋テーブルは、コンテンツ・ストア内のコンテンツ（たとえば、パケット、パケットの一部など）をポイントする指紋を含む。コンテンツ・ストアは、符号化ミドルボックスで受信されたコンテンツを格納する（たとえば、新しいコンテンツは、到着時に格納され、より古いコンテンツは、より新しいコンテンツのための場所をあけるために追い出される。指紋テーブルは、コンテンツがコンテンツ・ストアに追加され、コンテンツ・ストアから追い出される時に、それに従って調整される。符号化ミドルボックスを、最大一致ＲＥ、チャンク一致ＲＥ、または任意の他の適切なＲＥ方式をサポートするように構成することができる。
【００１８】
最大一致ＲＥでは、一般的に言って、オリジナル・パケットの最大の一致する領域が、一致する領域より小さい符号化された領域によって置換され、これによって、オリジナル・パケットをより小さくする。指紋が、指紋アルゴリズムに基づいて（たとえば、ラビン指紋法（Ｒａｂｉｎ  ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ）または任意の他の適切なタイプの指紋アルゴリズムを使用して）パケットごとに計算される。指紋は、オリジナル・パケットから選択される。指紋の選択は、ある種の判断基準（たとえば、値サンプリングまたは類似物）に基づくものとすることができる。オリジナル・パケットからの選択された指紋が指紋テーブルに含まれるかどうかを判定するために、選択された指紋を使用するルックアップが、指紋テーブル内で実行される。一致が指紋テーブル内で見つかる場合には、コンテンツ・ストア内の対応する格納されたパケットが、取り出され、オリジナル・パケットと格納されたパケットとの間の最大一致が識別されるまで、オリジナル・パケットと格納されたパケットとの間の一致する領域が、比較（たとえば、バイトごとの比較）を介して展開される。最大一致が識別された後に、オリジナル・パケットの一致する領域は、符号化された領域（たとえば、コンテンツ・ストアからの格納されたパケットの１つへのポインタおよび一致する領域のサイズを含むシム・ヘッダ（ｓｈｉｍ  ｈｅａｄｅｒ））によって置換される。
【００１９】
チャンク一致ＲＥでは、一般的に言って、オリジナル・パケットのチャンクが、チャンクより小さい符号化された領域によって置換され、これによってオリジナル・パケットをより小さくする。オリジナル・パケットは、チャンクに分割され、チャンクは、コンテンツ・ストアに格納される。指紋テーブルは、コンテンツ・ストア内のチャンクをポイントするハッシュを含む。指紋が、オリジナル・パケットから選択される。指紋の選択は、ある種の判断基準（たとえば、値サンプリングまたは類似物）に基づくものとすることができる。オリジナル・パケットからの選択された指紋が指紋テーブルに含まれるかどうかを判定するために、選択された指紋を使用するルックアップが、指紋テーブル内で実行される。一致が指紋テーブル内で見つかる場合には、オリジナル・パケットの一致する領域／チャンクが、符号化された領域（たとえば、コンテンツ・ストアからの格納されたチャンクの１つへのポインタおよび一致する領域／チャンクのサイズを含むシム・ヘッダ）によって置換される。チャンク一致ＲＥでは、比較ベースの展開は、一致が指紋テーブル内で見つかる時に実行されない。
【００２０】
一般に、復号ミドルボックスは、符号化されたパケットを受信し、符号化されたパケットからオリジナル・パケットを再構成する。復号ミドルボックスは、符号化ミドルボックス上で維持されるコンテンツ・ストアに類似するコンテンツ・ストアを有する（たとえば、最大一致ＲＥでパケットを格納し、チャンク一致ＲＥでチャンクを格納するなど）。符号化された領域（本明細書では符号化キーと称する場合もある）を含む符号化されたパケットが、復号ミドルボックスで受信される時に、符号化された領域は、符号化された領域をオリジナル・コンテンツ（すなわち、符号化ミドルボックスによってオリジナル・パケットから除去され、符号化された領域に置換されたコンテンツ）に置換することによって、オリジナル・パケットを再構成するのに使用される。符号化された領域は、オリジナル・コンテンツを取り出すために復号ミドルボックスのコンテンツ・ストア内でルックアップを実行するのに使用され、符号化された領域は、その後、オリジナル・パケットが再形成されるように、オリジナル・コンテンツによって置換される。
【００２１】
ＲＥミドルボックスでは、さまざまなデータ構造を、メモリまたはディスク内で維持することができる。少なくともいくつかの場合に、高性能のために、データ構造は、メモリ内でのみ維持される。用語「ストレージ・モジュール」は、本明細書では、ＲＥミドルボックスのためにそのようなデータ構造を維持する際の使用に適する任意のタイプのストレージを指すために使用され得る（たとえば、メモリ、ディスクなど、ならびにそのさまざまな組合せ）。
【００２２】
本明細書で説明されるように、そのようなＲＥミドルボックスを、クラウド・設定内の仮想機器として実施することができるが、仮想機器として実施されたそのようなＲＥミドルボックスのスケーリングは、簡単ではなく、さらに、仮想機器として実施されたそのようなＲＥミドルボックスのスケーリングに対する負荷平衡化ベースの手法は、通常はうまく働かない。上で注記したように、ＲＥ能力の少なくともいくつかの実施形態は、ＲＥミドルボックスのストレージ能力および処理能力の効果的なスケーリングを提供する。
【００２３】
一実施形態では、ＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄは、ＷＡＮ  １２０を介するデータの転送用のＲＥ機能を提供することに関係するストレージ能力および処理能力のスケーリングをサポートするように構成される。最大一致ＲＥのＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄの例示的実施形態を、それぞれ図２および図３に関して図示し、説明する。チャンク一致ＲＥのＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄの例示的実施形態を、それぞれ図５および図６に関して図示し、説明する。
【００２４】
主にＲＥ処理ミドルボックスが２つのクラウド・サイトの間の通信を最適化するために利用される実施形態に関して図１に図示され、説明されるが、ＲＥ処理ミドルボックスを、さまざまな他の要素の間（たとえば、企業とクラウド・サイトとの間、ユーザとクラウド・サイトとの間、無線通信システム内の無線アクセス・ネットワーク（ＲＡＮ）とコア・ネットワーク（ＣＮ）との間など、ならびにそのさまざまな組合せ）の通信を最適化するために利用することもできることに留意されたい。
【００２５】
一実施形態では、ＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄは、最大一致ＲＥ能力をサポートするように構成される。これを、図２、３、および４に関して図示し、説明する。
【００２６】
図２に、最大一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す。より具体的には、図２は、最大一致ＲＥのためのＲＥ符号化ミドルボックス１１２Ｅの例示的実施形態（ＲＥ符号化ミドルボックス２００Ｅと表される）を示す。
【００２７】
ＲＥ符号化ミドルボックス２００Ｅは、クラシファイヤ２１０、分類−符号器マッピング・テーブル２１１、複数の符号器２１２１〜２１２Ｎ（集合的に符号器２１２）、およびマージャ２１５を含む。符号器２１２１〜２１２Ｎは、それぞれ、複数のコンテンツ・ストア２１３１〜２１３Ｎ（集合的にコンテンツ・ストア２１３）および複数の指紋テーブル２１４１〜２１４Ｎ（集合的に指紋テーブル２１４）を含む。
【００２８】
クラシファイヤ２１０は、符号器２１２のそれぞれと通信するように構成される。マージャ２１５も、符号器２１２のそれぞれと通信するように構成される。符号器２１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、符号器２１２１は、符号器２１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の符号器２１２が、任意の他の符号器２１２と直接（すなわち、他の符号器２１２をトラバースせずに）、または、符号器２１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【００２９】
ＲＥ符号化ミドルボックス２００Ｅは、パケットが、クラシファイヤ２１０によって分類され、その後、クラシファイヤ２１０によって判定されるパケットのパケット・クラスに基づいて、異なる形で符号器２１２によって処理される（たとえば、符号器２１２の異なるサブセットによって処理される、符号器２１２の異なる順序を使用して符号器２１２によって処理されるなど、ならびにそのさまざまな組合せ）ように構成される。
【００３０】
クラシファイヤ２１０は、パケットを受け取り、受け取られたパケットの分類を判定する。ＲＥ符号化ミドルボックス２００Ｅは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ２１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ符号化ミドルボックス２００Ｅによってサポートされるパケット・クラスのセットは、ＲＥ復号ミドルボックス１１２Ｄによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ２１０は、分類−符号器マッピング・テーブル２１１に従って、分類されたパケットを符号器２１２に供給する。
【００３１】
分類−符号器マッピング・テーブル２１１は、パケット・クラスのそれぞれについて、符号器２１２がそのパケット・クラスのパケットを符号化するのに使用されるそれぞれの形へのパケット・クラスのマッピングを指定する。所与のパケット・クラスについて、符号器２１２がパケット・クラスのパケットを符号化するのに使用される形は、符号器リストとして指定され、符号器リスト内の符号器２１２の順序は、符号器２１２が所与のパケット・クラスに分類された各パケットに作用する順序を指定する。たとえば、例示的な分類−符号器マッピング・テーブル２１１は、第１のパケット・クラス（第１クラス）が符号器２１２の第１の順序付け（例示として、符号器２１２１、符号器２１２２、以下、符号器２１２Ｎまで下付きの数値の順）にマッピングされ、第２のパケット・クラス（第２クラス）が符号器２１２の第２の順序付け（例示として、符号器２１２２、符号器２１２３、以下、符号器２１２Ｎまで下付きの数値の順、その後に最終的に符号器２１２１）にマッピングされ、以下、第Ｎのパケット・クラス（第Ｎクラス）が符号器２１２の第Ｎの順序付け（例示として、符号器２１２Ｎ、符号器２１２Ｎ−１、以下、符号器２１２１まで下付きの逆の数値の順）にマッピングされるなどを示す。主に特定の個数のパケット・クラスおよび符号器２１２の使用（およびパケット・クラスの個数が符号器２１２の個数と等しい場合）に関して図示され、説明されるが、より少数またはより多数のパケット・クラスまたは符号器２１２を使用することができることに留意されたい（また、パケット・クラスの個数と符号器２１２の個数との間の１対１関係が要求されないことを理解されたい）。主に分類−符号器マッピング・テーブル２１１が符号器２１２のそれぞれからアクセス可能な単一のテーブルである実施形態に関して図示され、説明されるが、分類−符号器マッピング・テーブル２１１のＮ個のコピーを、それぞれ符号器２１２１〜２１２Ｎに格納することができることに留意されたい。
【００３２】
クラシファイヤ２１０は、受け取られたパケットを符号化するのに使用すべき符号器２１２のセットを判定するのに分類−符号器マッピング・テーブル２１１を使用する。たとえば、受け取られたパケットのパケット・クラスを判定した後に、クラシファイヤ２１０は、受け取られたパケットを符号化するのに使用すべき符号器２１２のセットを判定するために、分類−符号器マッピング・テーブル２１１へのキーとして、判定されたパケット・クラスを使用することができる。上で説明したように、分類−符号器マッピング・テーブル２１１は、パケット・クラスごとに、符号器２１２がパケットの符号化のためにパケットを処理する順序を示す符号器２１２の順序を指定する。クラシファイヤ２１０は、パケット・クラスの符号器リスト内の最初の符号器２１２にパケットを供給する前に、パケット内でパケットのパケット・クラスをマークする。一実施形態では、クラシファイヤ２１０は、パケット内に、分類−符号器マッピング・テーブル２１１から判定されるパケット・クラスの符号器リストを含めることによって、パケット内でパケット・クラスをマークする（これによって、符号器リストがパケット自体からたやすく使用可能なので、パケット・クラスの符号器リスト内の符号器２１２が分類−符号器マッピング・テーブル２１１へのルックアップを実行する必要が防がれる）。一実施形態では、クラシファイヤ２１０は、分類−符号器マッピング・テーブル２１１へのキーとして符号器リスト内の各符号器２１２によって使用され得るパケット・クラス識別子を用いてパケットをマークすることによって、パケット内でパケット・クラスをマークする。そのような実施形態では、現在の符号器２１２は、パケットについてどのＲＥ機能を実行すべきかを知り、パケットが供給されなければならない次のノード（たとえば、次の符号器２１２またはマージャ２１５）を判定することもできるように、パケット・クラスの符号器リスト内のそれ自体の位置を判定する。
【００３３】
符号器２１２は、それぞれ、最大一致ＲＥの複数のＲＥ符号化機能をサポートするように構成される。各符号器２１２によってサポートされるＲＥ符号化機能は、（１）指紋の計算、（２）指紋ルックアップの実行、（３）一致する領域の展開、および（４）コンテンツ・ストア（例示として、それぞれのコンテンツ・ストア２１３）へのパケットの格納を含む。主に、符号器２１２のそれぞれが４つのリストされたＲＥ復号機能のそれぞれを実行するように構成される実施形態に関して図示され、説明されるが、少なくともいくつかの実施形態で、符号器２１２のうちの１つまたは複数を、リストされたＲＥ符号化機能のうちのより少数または他のＲＥ符号化機能をサポートするように構成することができることに留意されたい。
【００３４】
符号器２１２は、分類−符号器マッピング・テーブル２１１内で指定されるパケット・クラスに関連する符号器リスト内のその位置に基づいて、どのＲＥ符号化機能をパケット・クラスのパケットについて実行すべきかを知るように構成される。
【００３５】
パケット・クラスのパケットについて符号器２１２によって実行されるＲＥ符号化機能は、符号器２１２がパケット・クラスの符号器リスト内の最初の符号器２１２またはパケット・クラスの符号器リスト内の後続の符号器２１２のどちらであるのかに依存する。一実施形態では、符号器２１２は、符号器リスト内の最初の符号器２１２がパケット・クラスの所与のパケットの４つのＲＥ符号化機能のそれぞれを実行する責任を負い、符号器リスト内の後続の符号器２１２のそれぞれが符号器リスト内のより前の符号器２１２によってマッチングされず展開されない指紋の指紋ルックアップの実行および一致する領域の展開の責任を負うように構成される。上で注記したように、各符号器２１２は、パケット自体から（たとえば、クラシファイヤ２１０が、分類−符号器マッピング・テーブル２１１へのルック・アップに基づいてパケットに符号器リストを追加する場合）または分類−符号器マッピング・テーブル２１１へのルック・アップを介して（たとえば、クラシファイヤ２１０によってパケット内に含められたパケット・クラス識別子に基づいて）所与のパケット・クラスの符号器リスト内のその位置を判定することができる。パケット・クラスの符号器リスト内の最初の符号器２１２は、そのパケット・クラスに関連するものとしてマークされたパケットを受け取った時に、パケットの指紋（符号器リスト内の最初の符号器２１２ならびに符号器リスト内の１つまたは複数の後続の符号器２１２によって使用される計算された指紋のリストとして維持される）を計算し、パケットをそれに関連するコンテンツ・ストア２１３に格納し、それに関連する指紋テーブル２１４内で指紋ルックアップを実行し、指紋一致が見つかる時に、パケット内の一致した指紋の一致する領域を符号化し、一致した指紋を計算された指紋のリストから除去し、符号化されたパケットおよび計算された指紋の更新されたリストをパケット・クラスの符号器リスト内の次の符号器２１２に渡す。パケット・クラスの符号器リスト内の各後続の符号器２１２（すなわち、パケット・クラスの符号器リスト内の最初の符号器２１２を除くすべての符号器）は、符号器リスト内の以前の符号器２１２から符号化されたパケットを受け取り、それに関連する指紋テーブル２１４内で指紋ルックアップを実行し、指紋一致が見つかる時に、パケット内の一致した指紋の一致する領域を符号化し、一致した指紋を計算された指紋のリストから除去し、符号化されたパケットおよび計算された指紋の更新されたリストをパケット・クラスの符号器リスト内の次の符号器２１２に渡す。符号器リスト内の最後の符号器２１２は、パケット・クラスの符号器リスト内の後続符号器２１２としての機能を実行した後に、符号化されたパケットをマージャ２１５に供給する。
【００３６】
マージャ２１５は、符号器２１２から符号化されたパケットを受け取り、符号化されたパケットを伝搬させる（たとえば、それを介して符号化されたパケットをＲＥ復号ミドルボックス１１２Ｄに配送できるＷＡＮ  １２０を介して）。
【００３７】
この形で、ＲＥ符号化機能を、さまざまな符号器２１２にまたがって分散させる（したがって、負荷平衡化する）ことができ、同様に、ＲＥ符号化機能に関連する格納および処理を、さまざまな符号器２１２にまたがって分散させる（したがって、負荷平衡化する）ことができる。パケットは、分類され、異なるパケット・クラスについて符号器２１２の異なるリスト内の最初の符号器として動作する符号器２１２の異なるものに供給されるので、パケットの格納は、それぞれ、符号器２１２のコンテンツ・ストア２１３にまたがって分散される。同様に、パケットは、分類され、異なるパケット・クラスについて符号器２１２の異なるリスト内の最初の符号器として動作する符号器２１２の異なる１つに供給されるので、ＲＥに使用される指紋の維持は、それぞれ符号器２１２の指紋テーブル２１４にまたがって分散される。パケットは、分類され、異なるパケット・クラスについて符号器２１２の異なるリストに基づいて異なる順序で後続符号器として動作する符号器２１２に供給されるので、指紋を符号化された領域と置換するためのパケットの処理は、それぞれ符号器２１２にまたがって分散される。この形でＲＥ符号化ミドルボックス２００Ｅを構成することのさまざまな利益は、図４を参照することによってよりよく理解することができる。
【００３８】
図３に、最大一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す。より具体的には、図３は、最大一致ＲＥのＲＥ復号ミドルボックス１１２Ｄの例示的実施形態（ＲＥ復号ミドルボックス３００Ｄと表される）を示す。
【００３９】
図３のＲＥ復号ミドルボックス３００Ｄは、図２のＲＥ符号化ミドルボックス２００Ｅに類似する形で動作するように構成され、ＲＥ復号ミドルボックス３００Ｄは、ＲＥ符号化ミドルボックス２００Ｅによって実行されるＲＥ符号化機能に相補的なＲＥ復号機能を実行する。
【００４０】
ＲＥ復号ミドルボックス３００Ｄは、クラシファイヤ３１０、分類−復号器マッピング・テーブル３１１、複数の復号器３１２１〜３１２Ｎ（集合的に復号器３１２）、およびマージャ３１５を含む。復号器３１２１〜３１２Ｎは、それぞれ複数のコンテンツ・ストア３１３１〜３１３Ｎ（集合的にコンテンツ・ストア３１３）を含む。
【００４１】
クラシファイヤ３１０は、復号器３１２のそれぞれと通信するように構成される。マージャ３１５も、復号器３１２のそれぞれと通信するように構成される。復号器３１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、復号器３１２１は復号器３１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の復号器３１２が、任意の他の復号器３１２と直接（すなわち、他の復号器３１２をトラバースせずに）、または、復号器３１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【００４２】
ＲＥ復号ミドルボックス３００Ｄは、パケットが、クラシファイヤ３１０によって分類され、その後、クラシファイヤ３１０によって判定されるパケットのパケット・クラスに基づいて、異なる形で復号器３１２によって処理される（たとえば、復号器３１２の異なるサブセットによって処理される、復号器３１２の異なる順序を使用して復号器３１２によって処理されるなど、ならびにそのさまざまな組合せ）ように構成される。
【００４３】
クラシファイヤ３１０は、パケットを受け取り、受け取られたパケットの分類を判定し、それぞれ、パケット内の受け取られたパケットの分類をマークする。ＲＥ復号ミドルボックス３００Ｄは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ３１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ復号ミドルボックス３００Ｄによってサポートされるパケット・クラスのセットは、ＲＥ符号化ミドルボックス１１２Ｅによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ３１０は、分類−符号器マッピング・テーブル３１１に従って、分類されたパケットを復号器３１２に供給する。
【００４４】
分類−復号器マッピング・テーブル３１１は、パケット・クラスのそれぞれについて、復号器３１２がそのパケット・クラスのパケットを復号するのに使用されるそれぞれの形へのパケット・クラスのマッピングを指定する。所与のパケット・クラスについて、復号器３１２がパケット・クラスのパケットを復号するのに使用される形は、復号器リストとして指定され、復号器リスト内の復号器３１２の順序は、復号器３１２が所与のパケット・クラスに分類された各パケットに作用する順序を指定する。一実施形態では、パケット・クラスごとに、復号器リスト内の復号器３１２の順序は、ＲＥ符号化ミドルボックス２００Ｅの分類−符号器マッピング・テーブル２１１内で指定される符号器リストの符号器２１２の順序の逆である。たとえば、図３の例示的な分類−復号器マッピング・テーブル３１１は、第１のパケット・クラス（第１クラス）が復号器３１２の第１の順序付け（例示として、復号器３１２Ｎ、復号器３１２Ｎ−１、以下、復号器３１２１まで下付きの数値の順）にマッピングされ、第２のパケット・クラス（第２クラス）が復号器３１２の第２の順序付け（例示として、復号器３１２Ｎ−１、復号器３１２Ｎ−２、以下、復号器３１２１まで下付きの数値の順、その後に最終的に復号器３１２Ｎ）にマッピングされ、以下、第Ｎのパケット・クラス（第Ｎクラス）が復号器３１２の第Ｎの順序付け（例示として、復号器３１２１、復号器３１２２、以下、復号器３１２Ｎまで下付きの数値の順）にマッピングされるなどを示す。主に特定の個数のパケット・クラスおよび復号器３１２の使用（およびパケット・クラスの個数が復号器３１２の個数と等しい場合）に関して図示され、説明されるが、より少数またはより多数のクラスまたは復号器３１２を使用することができることに留意されたい（また、パケット・クラスの個数と復号器３１２の個数との間の１対１関係が要求されないことを理解されたい）。主に分類−復号器マッピング・テーブル３１１が復号器３１２のそれぞれからアクセス可能な単一のテーブルである実施形態に関して図示され、説明されるが、分類−復号器マッピング・テーブル３１１のＮ個のコピーを、それぞれ復号器３１２１〜３１２Ｎに格納することができることに留意されたい。
【００４５】
クラシファイヤ３１０は、受け取られたパケットを復号するのに使用すべき復号器３１２のセットを判定するのに分類−復号器マッピング・テーブル３１１を使用する。たとえば、受け取られたパケットのパケット・クラスを判定した後に、クラシファイヤ３１０は、受け取られたパケットを復号するのに使用すべき復号器３１２のセットを判定するために、分類−復号器マッピング・テーブル３１１へのキーとして、判定されたパケット・クラスを使用することができる。上で説明したように、分類−復号器マッピング・テーブル３１１は、パケット・クラスごとに、復号器３１２がパケットの復号のためにパケットを処理する順序を示す復号器３１２の順序を指定する。クラシファイヤ３１０は、パケット・クラスの復号器リスト内の最初の復号器３１２にパケットを供給する前に、パケット内でパケットのパケット・クラスをマークする。一実施形態では、クラシファイヤ３１０は、パケット内に、分類−復号器マッピング・テーブル３１１から判定されるパケット・クラスの復号器リストを含めることによって、パケット内でパケット・クラスをマークする（これによって、復号器リストがパケット自体からたやすく使用可能なので、パケット・クラスの復号器リスト内の復号器３１２が分類−復号器マッピング・テーブル３１１へのルックアップを実行する必要が防がれる）。一実施形態では、クラシファイヤ３１０は、分類−復号器マッピング・テーブル３１１へのキーとして復号器リスト内の各復号器３１２によって使用され得るパケット・クラス識別子を用いてパケットをマークすることによって、パケット内でパケット・クラスをマークする。そのような実施形態では、現在の復号器３１２は、パケットについてどのＲＥ機能を実行すべきかを知り、パケットが供給されなければならない次のノード（たとえば、次の復号器３１２またはマージャ３１５）を判定することもできるように、パケット・クラスの復号器リスト内のそれ自体の位置を判定する。
【００４６】
復号器３１２は、それぞれ、最大一致ＲＥの複数のＲＥ復号機能をサポートするように構成される。各復号器３１２によってサポートされるＲＥ復号機能は、（１）符号化キーの復号、（２）符号化キーによって識別されるパケットのルックアップの実行、（３）符号化キーによって識別されたパケットの対応する諸部分による符号化キーの置換、および（４）コンテンツ・ストア（例示として、それぞれのコンテンツ・ストア３１３）へのパケットの格納を含む。主に、復号器３１２のそれぞれが４つのリストされたＲＥ復号機能のそれぞれを実行するように構成される実施形態に関して図示され、説明されるが、少なくともいくつかの実施形態で、復号器３１２のうちの１つまたは複数を、リストされたＲＥ復号機能のうちのより少数または他のＲＥ復号機能をサポートするように構成することができることに留意されたい。
【００４７】
復号器３１２は、分類−復号器マッピング・テーブル３１１内で指定されるパケット・クラスに関連する復号器リスト内のその位置に基づいて、どのＲＥ復号機能をパケット・クラスのパケットについて実行すべきかを知るように構成される。
【００４８】
パケット・クラスのパケットについて復号器３１２によって実行されるＲＥ復号機能は、復号器３１２がパケット・クラスの復号器リスト内の最初の復号器３１２、パケット・クラスの復号器リスト内の中間の復号器３１２、またはパケット・クラスの復号器リスト内の最後の復号器３１２のどちらであるのかに依存する。一実施形態では、復号器３１２は、復号器リスト内の最初の復号器３１２が第１のＲＥ復号機能（すなわち、符号化キーの復号）を実行する責任を負い、復号器リスト内の復号器３１２のそれぞれが第２および第３のＲＥ復号機能（すなわち、符号化キーによって識別されるパケットのルックアップの実行および符号化キーによって識別されたパケットの対応する諸部分による符号化キーの置換）を実行する責任を負い、復号器リスト内の最後の復号器３１２が第４のＲＥ復号機能（すなわち、コンテンツ・ストアへのパケットの格納）を実行する責任を負うように構成される。上で注記したように、各復号器３１２は、パケット自体から（たとえば、クラシファイヤ３１０が、分類−復号器マッピング・テーブル３１１へのルック・アップに基づいてパケットに復号器リストを追加する場合）または分類−復号器マッピング・テーブル３１１へのルック・アップを介して（たとえば、クラシファイヤ３１０によってパケット内に含められたパケット・クラス識別子に基づいて）所与のパケット・クラスの復号器リスト内のその位置を判定することができる。パケット・クラスの復号器リスト内の最初の復号器３１２は、そのパケット・クラスに関連するものとしてマークされたパケットを受け取った時に、受け取られたパケット内に含まれる符号化キーのそれぞれ（たとえば、パケットのＲＥベースの符号化中にＲＥ符号化ミドルボックス１１２Ｅによってそこに置かれた）を識別し、復号する。パケット・クラスの復号器リスト内の最初の復号器３１２は、次に、そのコンテンツ・ストア３１３を使用して符号化キーのそれぞれのルックアップを実行し、一致するパケットがそれに関して最初の復号器３１２のコンテンツ・ストア３１３内で識別される符号化キーごとに、受け取られたパケット内の符号化キーを、最初の復号器３１２のコンテンツ・ストア３１３から識別された格納されたパケットの対応する部分に置換する。パケット・クラスの復号器リスト内の最初の復号器３１２は、次に、受け取られたパケットおよび残りの符号化キー（すなわち、最初の復号器３１２が処理できなかった符号化キー）をパケット・クラスの復号器リスト内の２番目の復号器３１２に渡す。パケット・クラスの復号器リスト内の２番目の復号器３１２は、そのコンテンツ・ストア３１３を使用して残りの符号化キー（最初の復号器３１２から受け取られた）のそれぞれについてルックアップを実行し、一致するパケットがそれに関して２番目の復号器３１２のコンテンツ・ストア３１３内で識別される符号化キーごとに、受け取られたパケット内の符号化キーを、２番目の復号器３１２のコンテンツ・ストア３１３から識別された格納されたパケットの対応する部分に置換する。パケット・クラスの復号器リスト内の２番目の復号器３１２は、次に、受け取られたパケットおよび残りの符号化キー（すなわち、最初および２番目の復号器３１２が処理できなかった符号化キー）をパケット・クラスの復号器リスト内の３番目の復号器３１２に渡す。パケットは、パケット・クラスの復号器リスト内の最後の復号器３１２に達するまで、この形で処理され、渡され続ける。パケット・クラスの復号器リスト内の最後の復号器３１２は、そのコンテンツ・ストア３１３を使用して残りの符号化キー（最後の直前の復号器３１２から受け取られた）のそれぞれについてルックアップを実行し、一致するパケットがそれに関して最後の復号器３１２のコンテンツ・ストア３１３内で識別される符号化キーごとに、受け取られたパケット内の符号化キーを、２番目の復号器３１２のコンテンツ・ストア３１３から識別された格納されたパケットの対応する部分に置換する。したがって、パケット・クラスの復号器リスト内の最後の復号器３１２による受け取られたパケットの処理の後に、完全なパケット（すなわち、パケットのＲＥベースの符号化中にＲＥ符号化ミドルボックス１１２Ｅによって符号化される前のオリジナル・パケット）が復元される。パケット・クラスの復号器リスト内の最後の復号器３１２は、パケットをそのコンテンツ・ストア３１３に格納する。パケット・クラスの復号器リスト内の最後の復号器３１２は、回復されたパケットをマージャ３１５に供給する。
【００４９】
マージャ３１５は、復号されたパケットを復号器３１２から受け取り、復号されたパケットを伝搬する。
【００５０】
この形で、ＲＥ復号機能を、さまざまな復号器３１２にまたがって分散させる（したがって、負荷平衡化する）ことができ、同様に、ＲＥ復号機能に関連する格納および処理を、さまざまな復号器３１２にまたがって分散させる（したがって、負荷平衡化する）ことができる。たとえば、パケットは、分類され、異なるパケット・クラスについて復号器３１２の異なるリスト内の最初の復号器として動作する復号器３１２の異なるものに供給されるので、受け取られたパケットの符号化キーの処理は、それぞれ復号器３１２にまたがって分散される。たとえば、パケットは、分類され、異なるパケット・クラスについて復号器３１２の異なるチェーンに供給されるので、パケットの格納は、それぞれ復号器３１２のコンテンツ・ストア３１３にまたがって分散される。たとえば、パケットの格納が、復号器３１２にまたがって分散されるので、パケットの符号化キーを格納されたパケットのコンテンツに置換するためのパケットの処理も、復号器３１２にまたがって分散される。この形でのＲＥ復号ミドルボックス３００Ｄを構成することのさまざまな利益は、図４を参照することによってよりよく理解することができる。
【００５１】
図４に、３つの符号器を有する例示的なＲＥ符号化ミドルボックスおよび３つの復号器を有する例示的なＲＥ復号ミドルボックスの異なる処理ステージにまたがるＲＥ機能の例示的な分散を示す。
【００５２】
本明細書で説明されるように、ＲＥ符号化ミドルボックス２００Ｅは、ＲＥ処理を複数の符号器２１２にまたがって分割し、効果的に大きいメモリを使用する。最大一致ＲＥでは、パケットごとに実行すべきＲＥ符号化機能は、（１）指紋の計算、（２）指紋ルックアップの実行、（３）一致する領域の展開、および（４）コンテンツ・ストアへのパケットの格納を含む。
【００５３】
第１および第４のＲＥ符号化機能に関して、一実施形態で、第１および第４の機能が、所与のパケット・クラスのノードのリストの最初のノードだけに割り当てられることに留意されたい。各パケット・クラスが、符号器２１２のランダムな置換を含み、クラシファイヤ２１０がパケットをすべてのパケット・クラスの間で均等に分割するという仮定が行われる場合に、高い確率で、各符号器２１２は、第１および第４のＲＥ符号化機能のほぼ等しい責任を有する。したがって、第１および第４のＲＥ符号化機能は、複数の符号器２１２にまたがって均等に分割されるはずである。
【００５４】
第３のＲＥ符号化機能に関して、第３のＲＥ符号化機能も、符号器２１２にまたがって自動的に分割されることに留意されたい（たとえば、単純なラウンドロビン・ポリシでは、パケットは、符号器２１２のすべての間でほぼ均等に格納され、したがって、一致する領域も符号器２１２のすべての間でほぼ均等に分割される高い尤度がある）。一実施形態では、クラシファイヤ２１０を、符号器２１２のそれぞれの間での均等な分割を強制するように構成された１つまたは複数のポリシを使用するように構成することができる。
【００５５】
しかし、第２のＲＥ符号化機能に関して、指紋ルックアップ機能を、符号器２１２の間で分割することができないことに留意されたい。しかし、他の３つのＲＥ符号化機能が符号器２１２の間で分割され、インメモリ指紋ルックアップが、他のＲＥ符号化機能と比較して相対的に安価であることを考慮すると、指紋ルックアップが符号器２１２の間で均等には分割されない場合に、重大な悪影響はない。
【００５６】
その結果、各符号器２１２は、すべてのステージでいくつかのＲＥ符号化機能を実行しつつある。これが、図４に示されており、例示的な分散４１０は、３つの符号器（符号器１、符号器２、および符号器３と表される）を有するＲＥ符号化ミドルボックス２１２Ｅの例示的実施態様の異なる処理ステージにまたがるＲＥ符号化機能の分散を示す。ＲＥ符号化ミドルボックス２１２Ｅの例示的実施態様は、赤、青、および緑と表された３つのパケット・クラスをサポートし、赤パケット・クラスは、第１の符号器リスト（符号器１、符号器２、符号器３）を有し、青パケット・クラスは、第２の符号器リスト（符号器２、符号器３、符号器１）を有し、緑パケット・クラスは、第３の符号器リスト（符号器３、符号器１、符号器２）を有する。例示的な分散４１０のステージ１では、符号器１は、指紋を計算し、パケットを格納し、赤パケットの指紋ルックアップを実行し、符号器２は、指紋を計算し、パケットを格納し、青パケットの指紋ルックアップを実行し、符号器３は、指紋を計算し、パケットを格納し、緑パケットの指紋ルックアップを実行する。例示的な分散４１０のステージ２では、符号器１は、緑パケットの残りの指紋の指紋ルックアップを実行し、符号器２は、赤パケットの残りの指紋の指紋ルックアップを実行し、符号器３は、青パケットの残りの指紋の指紋ルックアップを実行する。例示的な分散４１０のステージ３では、符号器１は、青パケットの残りの指紋の指紋ルックアップを実行し、符号器２は、緑パケットの残りの指紋の指紋ルックアップを実行し、符号器３は、赤パケットの残りの指紋の指紋ルックアップを実行する。例示的な分散４１０について、各符号器が、パケットごとに一致を見つけるためにその指紋テーブルへのルックアップを実行するので、ＲＥのために使用される有効なメモリが、すべての符号器２１２で使用可能なメモリの合計であることがわかる。
【００５７】
本明細書で説明するように、ＲＥ復号ミドルボックス３００Ｄは、複数の復号器３１２にまたがってＲＥ処理を分割し、効果的に大きいメモリを使用する。最大一致ＲＥでは、パケットごとに実行すべきＲＥ復号機能は、（１）符号化キーの復号、（２）符号化キーによって識別されたパケットのルックアップの実行、（３）符号化キーによって識別されたパケットの対応する部分による符号化キーの置換、および（４）コンテンツ・ストアへのパケットの格納を含む。ＲＥ復号が、ＲＥ符号化に似た形でスケール・アップされる（したがって、そのようなスケーリングの詳細な説明は、簡潔さのために省略される）ことを理解されたい。
【００５８】
その結果、各復号器３１２は、すべてのステージでいくつかのＲＥ復号機能を実行しつつある。これが、図４に示されており、例示的な分散４２０は、３つの復号器（復号器１、復号器２、および復号器３と表される）を有するＲＥ復号ミドルボックス２１２Ｄの例示的実施態様の異なる処理ステージにまたがるＲＥ復号機能の分散を示す。ＲＥ復号ミドルボックス２１２Ｄの例示的実施態様は、赤、青、および緑と表された３つのパケット・クラスをサポートし、赤パケット・クラスは、第１の復号器リスト（復号器３、復号器２、復号器１）を有し、青パケット・クラスは、第２の復号器リスト（復号器１、復号器３、復号器２）を有し、緑パケット・クラスは、第３の復号器リスト（復号器２、復号器１、復号器３）を有する。例示的な分散４２０のステージ１では、復号器３は、符号化キーを復号し、赤パケットのパケット・ルックアップを実行し、復号器１は、符号化キーを復号し、青パケットのパケット・ルックアップを実行し、復号器２は、符号化キーを復号し、緑パケットのパケット・ルックアップを実行する。例示的な分散４２０のステージ２では、復号器２は、符号化キーを復号し、赤パケットのパケット・ルックアップを実行し、復号器３は、符号化キーを復号し、青パケットのパケット・ルックアップを実行し、復号器１は、符号化キーを復号し、緑パケットのパケット・ルックアップを実行する。例示的な分散４２０のステージ３では、復号器１は、符号化キーを復号し、赤パケットのパケット・ルックアップを実行し、その後、赤パケットを格納し、復号器２は、符号化キーを復号し、青パケットのパケット・ルックアップを実行し、その後、青パケットを格納し、復号器３は、符号化キーを復号し、緑パケットのパケット・ルックアップを実行し、その後、緑パケットを格納する。
【００５９】
１つまたは複数の追加の特徴を提供して、ＲＥ符号化機能またはＲＥ復号機能の提供に関する処理およびメモリのスケーリングをさらに制御することができることに留意されたい。
【００６０】
一実施形態では、それぞれＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄの使用に起因する第１のクラウド１１０１および第２のクラウド１１０２内での帯域幅使用量の潜在的な増加（たとえば、各パケットが、ＲＥ符号化ミドルボックス２００Ｅの各符号器２１２およびＲＥ復号ミドルボックス３００Ｄの各復号器３１２をトラバースするように向けられる場合）は、使用される帯域幅の量またはスケーリングされたメモリのサイズを変更するために適合される１つまたは複数の同調可能パラメータを使用して制御され得る。たとえば、４つのＲＥミドルボックスを使用して、メモリに関する２のスケーリング係数を提供することができると同時に、ネットワーク・トラフィックは、ＲＥミドルボックスのうちの２つを通って流れることだけを許される。他のレベルのスケーリングをサポートすることができることを理解されたい。
【００６１】
一実施形態では、データ・プロセッサ（たとえば、ＲＥ符号化ミドルボックス２００Ｅの場合に符号器２１２、ＲＥ復号ミドルボックス３００Ｄの場合に復号器３１２）を動的に追加し、除去する能力を提供することができる。この実施形態では、新しいデータ・プロセッサが追加される時に、新しいデータ・プロセッサは、トラフィックの受信を開始し、したがって、ＲＥ機能を実行する際の使用のためにパケットをそのコンテンツ・ストアに追加し始める。この実施形態では、既存のデータ・プロセッサが除去される時に、データ・プロセッサのコンテンツ・ストアを、捨てることができ、あるいは、残りのデータ・プロセッサの一部またはすべてにまたがって分散させることができる。
【００６２】
一実施形態では、ブルーム・フィルタを使用して、ディスク・ルックアップを減らすことができる。比較的大きいコンテンツ・ストアについて、関連する指紋テーブルが、メモリに収まらない可能性があることに留意されたい。その場合に、指紋テーブルの少なくとも一部は、ディスク上で維持されなければならないはずである。これは、ディスク・ルックアップ動作がメモリ・ルックアップ動作と比較して高価なので、望ましくない。したがって、一実施形態では、ブルーム・フィルタを活用して、ディスク・ルックアップを減らすことができる。ハッシュ・テーブルとは異なって、ブルーム・フィルタは、空間効率のよいデータ構造であり、メモリに収まる可能性がある。指紋が存在する場合は、ブルーム・フィルタ・ルックアップが成功するが、指紋が存在しない場合に、ブルーム・フィルタ・ルックアップがそれでも成功する可能性がある（たとえば、偽陽性の場合）。したがって、ブルーム・フィルタは、偽陽性の確率が低いことを保証するために、正しく構成されなければならない。この形で、指紋が指紋テーブルに存在する時にルックアップがディスクに向かうことを高い確率で保証することが可能になる。指紋が存在する時には、対応する一致する領域が判定される。前に論じたように、一致展開機能は、符号器２１２にまたがってほぼ均等に分割される。したがって、そのようなブルーム・フィルタを使用することによって、ディスクＩ／Ｏ動作のバランスを、符号器２１２の間でとることができる。
【００６３】
一実施形態では、ＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄは、チャンク一致ＲＥ能力をサポートするように構成される。これを、図５および６に関して図示し、説明する。
【００６４】
図５に、チャンク一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す。より具体的には、図５は、チャンク一致ＲＥに関するＲＥ符号化ミドルボックス１１２Ｅの例示的実施形態（ＲＥ符号化ミドルボックス５００Ｅと表される）を示す。
【００６５】
チャンク一致ＲＥ手法が、パケットのチャンク（パケットではなく）が格納され、ＲＥ符号化に使用されることを除いて、図２および図３に関して図示し、説明した最大一致ＲＥ手法に類似することに留意されたい。したがって、チャンク一致ＲＥに関するＲＥ符号化ミドルボックス５００Ｅは、最大一致ＲＥに関するＲＥ符号化ミドルボックス２００Ｅに類似する。
【００６６】
ＲＥ符号化ミドルボックス５００Ｅは、クラシファイヤ５１０、分類−符号器マッピング・テーブル５１１、複数の符号器５１２１〜５１２Ｎ（集合的に符号器５１２）、およびマージャ５１５を含む。符号器５１２１〜５１２Ｎは、それぞれ、複数のコンテンツ・ストア５１３１〜５１３Ｎ（集合的にコンテンツ・ストア５１３）、複数の指紋テーブル５１４１〜５１４Ｎ（集合的に指紋テーブル５１４）、および複数のハッシュ領域マッピング・テーブル５１６１〜５１６Ｎ（集合的にハッシュ領域マッピング・テーブル５１６）を含む。
【００６７】
クラシファイヤ５１０は、符号器５１２のそれぞれと通信するように構成される。マージャ５１５も、符号器５１２のそれぞれと通信するように構成される。符号器５１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、符号器５１２１は、符号器５１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の符号器５１２が、任意の他の符号器５１２と直接（すなわち、他の符号器５１２をトラバースせずに）、または、符号器５１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【００６８】
一般に、図５のクラシファイヤ５１０、分類−符号器マッピング・テーブル５１１、符号器５１２、およびマージャ５１５の構成／動作は、それぞれ図２のクラシファイヤ２１０、分類−符号器マッピング・テーブル２１１、符号器２１２、およびマージャ２１５の構成／動作に類似する。しかし、符号器５１２は、クラシファイヤ５１０によって分類されたパケットを格納するように構成されるのではなく、クラシファイヤ５１０によって分類されたパケットをチャンクに分割し、チャンクを（それからチャンクが生成されたパケットではなく）符号器５１２のコンテンツ・ストア５１３に格納するように構成される。一実施形態では、所与のパケット・クラスのパケットについて、所与のパケット・クラスの符号器リスト内の最初の符号器５１２が、パケットをチャンクに分割する責任を負う。パケットのチャンクを、符号器５１２によって任意の適切な形で処理することができる。
【００６９】
一実施形態（図５に示された）では、チャンクの格納および処理の責任が、ハッシュ領域に基づいて符号器５１２にまたがって分割される。
【００７０】
一実施形態では、各符号器５１２１〜５１２Ｎは、それぞれハッシュ領域を割り当てられる。一実施形態では、最初の符号器５１２１は、ハッシュ領域［０．０−ａ］を割り当てられ、２番目の符号器５１２２は、ハッシュ領域［ａ−ｂ］を割り当てられ、以下同様に、最後の１つ前の符号器５１２Ｎ−１は、ハッシュ領域［（ｎ−２）−（ｎ−１）］を割り当てられ、最後の符号器５１２Ｎは、ハッシュ領域［（ｎ−１）−１．０］を割り当てられる。３つのハッシュ領域が、単に例示であり、任意の適切なサイズの任意の適切な個数のハッシュ領域を符号器５１２に割り当てることができることに留意されたい。主に、符号器５１２が単一のハッシュ領域だけを割り当てられる実施形態に関して図示され、説明されるが、１つまたは複数の符号器５１２が、複数のハッシュ領域を割り当てられ得ることに留意されたい。
【００７１】
一実施形態では、符号器５１２は、（１）チャンクについて計算されたハッシュが符号器５１２に割り当てられたハッシュ領域内に含まれる場合に、符号器５１２がチャンクを格納し、（２）チャンクが符号器５１２に割り当てられたハッシュ領域内に含まれる関連するハッシュを有する場合に、符号器５１２がチャンクのルックアップを実行するように構成される。
【００７２】
一実施形態では、ハッシュ領域の責任を負う符号器５１２へのハッシュ領域のマッピングは、ハッシュ領域マッピング・テーブル５１６１〜５１６Ｎ内で維持される（すなわち、各符号器５１２が、どのハッシュ領域がどの符号器５１２にマッピングされるのかを示す情報を有する）。主に、ハッシュ領域の責任を負う符号器５１２へのハッシュ領域のマッピングが、それぞれ符号器５１２１〜５１２Ｎ上で実施されるＮ個のハッシュ領域マッピング・テーブル５１６１〜５１６Ｎを使用して維持される実施形態に関して図示され、説明されるが、ハッシュ領域の責任を負う符号器５１２へのハッシュ領域のマッピングを、符号器５１２のそれぞれからアクセス可能な単一のハッシュ領域マッピング・テーブルを使用して、または符号器５１２のそれぞれのサブセットからアクセス可能な複数のハッシュ領域マッピング・テーブルを使用して、維持することができることに留意されたい。
【００７３】
ＲＥ符号化ミドルボックス５００Ｅの動作は、ＲＥ符号化ミドルボックス５００Ｅで受信される時にパケットがＲＥ符号化のために処理される形を考慮することによって、最もよく理解することができる。クラシファイヤ５１０は、パケットを関連するパケット・クラスに分類する。クラシファイヤ５１０は、分類−符号器マッピング・テーブル５１１からクラシファイヤ５１０によって判定されたパケット・クラスについて指定された符号器リスト内の最初の符号器５１２にパケットを供給する。最初の符号器５１２は、パケットをチャンクに分割する。最初の符号器５１２は、チャンクのそれぞれについてそれぞれのハッシュを計算する。最初の符号器５１２は、最初の符号器５１２に割り当てられたハッシュ領域内に含まれるハッシュを有するすべてのチャンクについて指紋ルックアップを実行する。最初の符号器５１２は、最初の符号器５１２に割り当てられたハッシュ領域内に含まれるハッシュを有するチャンクごとにパケットの符号化を実行する（すなわち、最初の符号器５１２がそれに関して責任を負うチャンクごとに見つかった指紋一致ごとに、パケットの一致するチャンクが、関連する符号化キーに置換される）。その後、最初の符号器５１２は、パケットが供給される次の符号器５１２を選択する。最初の符号器５１２は、（１）パケットの残りのチャンクのハッシュ（すなわち、最初の符号器５１２によって識別されたが、最初の符号器５１２がそれに関して責任を負うハッシュ領域の外に含まれる１つまたは複数のハッシュ）、（２）ハッシュ領域の責任を負う符号器５１２へのハッシュ領域のマッピング（最初の符号器５１２のハッシュ領域マッピング・テーブル５１６内で指定される）、および（３）パケット・クラスの符号器リスト（パケット自体の中で指定されるか、分類−符号器マッピング・テーブル５１１から入手可能）に基づいて、パケットが提供される次の符号器５１２を選択する。たとえば、最初の符号器５１２は、（１）パケットの残りのハッシュのうちの１つまたは複数の責任を負う１つまたは複数の他の符号器５１２を識別するために、パケットの残りのハッシュを使用してそのハッシュ領域マッピング・テーブル５１６を検索し（パケットの残りのハッシュは、最初の符号器５１２によって計算されたが最初の符号器５１２がそれに関して責任を負うハッシュ領域の外に含まれるハッシュである）、（２）パケット・クラスの符号器リストに基づいて１つまたは複数の他の符号器５１２から次の符号器５１２を選択することができる。たとえば、最初の符号器５１２は、パケット・クラスの符号器リスト上で次の、識別された他の符号器５１２を選択することができる。次に、次の符号器５１２は、（１）次の符号器５１２に割り当てられたハッシュ領域内に含まれるハッシュを有するチャンクごとにパケットの符号化を実行し、（２）パケットが伝搬される次の要素（別の符号器５１２またはマージャ５１５）を判定する。パケットの符号化は、パケットが完全に符号化され、マージャ５１５に供給されるまで、この形で継続される。ハッシュ領域マッピング・テーブル５１６の使用が、パケットに符号器５１２のすべてを通過させる必要をなくすことができ（たとえば、符号器５１２の一部が、パケットのチャンクのいずれにも適用可能ではない関連するハッシュ領域を有する場合）、これによって、パケットを符号化するための帯域幅使用量の削減をもたらすことに留意されたい。前述の説明は、複数の符号器５１２がパケットを符号化するのに使用されると仮定する（パケットを符号化するための複数の符号器５１２の使用を例示するために）が、あるパケットが、最初の符号器５１２によって完全に符号化され、最初の符号器５１２からマージャ５１５に直接渡されることが可能であることに留意されたい。
【００７４】
たとえば、３つの符号器５１２１〜５１２３を有するＲＥ符号化ミドルボックス５００Ｅの場合を検討されたい。この例では、ハッシュ領域を、符号器５１２１（ハッシュ領域０．０〜０．３）、符号器５１２２（ハッシュ領域０．３〜０．６）、および符号器５１２３（ハッシュ領域０．６〜１．０）のように符号器５１２に割り当てることができる。この例では、符号器５１２１は、０．０〜０．３ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納し、符号器５１２２は、０．３〜０．６ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納し、符号器５１２３は、０．６〜１．０ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納する。したがって、ＲＥ動作のバランスを、３つの符号器５１２にまたがってとることができる。
【００７５】
この形で、チャンク・ルックアップおよびチャンク格納を、ハッシュ領域を適当に分割することによって、任意の適切な形で（たとえば、均等に、ほぼ均等に、または任意の他の適切な形で）符号器５１２にまたがって分散させることができる。
【００７６】
一実施形態では、ハッシュ領域を、動的に監視し、再構成することができる。これを、チャンク・ルックアップおよびチャンク格納が符号器５１２にまたがって分散されたままになることを保証する形で実行することができる。一実施形態では、チャンク・ハッシュが異なるハッシュ領域内に含まれる形に関する統計（たとえば、ハッシュ領域上の負荷）が維持され、そのような統計に基づいて、ハッシュ領域を動的に再構成することができる。動的再構成は、符号器５１２に割り当てられたハッシュ領域のサイズを変更すること、ハッシュ領域を組み合わせること、ハッシュ領域を分割すること、１つまたは複数の符号器５１２を除去し、ハッシュ領域を再割り当てすること、１つまたは複数の符号器５１２を追加し、ハッシュ領域を再割り当てすることなど、ならびにそのさまざまな組合せを含むことができる。
【００７７】
一実施形態では、ＲＥ符号化ミドルボックス５００Ｅへ／からの符号器５１２の動的な追加または除去をサポートすることができる。新しい符号器５１２がＲＥ符号化ミドルボックス５００Ｅに追加される時および既存の符号器がＲＥ符号化ミドルボックス５００Ｅから除去される時に、ＲＥ符号化ミドルボックス５００Ｅの既存の符号器５１２のうちの１つまたは複数のハッシュ領域を変更することができる。たとえば、ＲＥ符号化ミドルボックス５００Ｅが、それぞれ［０．０−０．２５］、［０．２５−０．５０］、［０．５０−０．７５］、および［０．７５−１．０］のハッシュ領域を有する４つの符号器５１２を含み、新しい符号器５１２が追加される場合に、新しい符号器５１２に、［０．２−０．２５］、［０．４５−０．５０］、［０．７０−０．７５］、および［０．９５−１．０］のハッシュ領域のそれぞれの責任を割り当てることができる（すなわち、既存の符号器のそれぞれの既存のハッシュ領域の小さい部分の責任だけを引き受ける）。たとえば、ＲＥ符号化ミドルボックス５００Ｅが、それぞれ［０．０−０．２５］、［０．２５−０．５０］、［０．５０−０．７５］、および［０．７５−１．０］のハッシュ領域を有する４つの符号器５１２を含み、［０．７５−１．０］のハッシュ領域の責任を負う４番目の符号器５１２が、ＲＥ符号化ミドルボックス５００Ｅから除去される場合に、最初の符号器５１２に、ハッシュ領域［０．７５−０．８３］の責任を割り当てることができ、２番目の符号器５１２に、ハッシュ領域［０．８４−０．９２］の責任を割り当てることができ、３番目の符号器５１２に、ハッシュ領域［０．９３−１．０］の責任を割り当てることができる。前述の例が、単に例示であり、より洗練されたポリシを、符号器５１２へのハッシュ領域の分散を制御するために適用することができることに留意されたい。
【００７８】
一実施形態（明瞭さのために省略されている）では、チャンクの格納および処理の責任が、ハッシュ領域を使用せずに符号器５１２にまたがって分割される。一実施形態では、所与のパケットの各チャンクは、パケットをチャンクに分割する符号器５１２（すなわち、パケットのパケット・クラスに関連する符号器リスト内の最初の符号器５１２）のコンテンツ・ストア５１３に格納される。一実施形態では、ハッシュ領域が使用されないので、各パケットは、チャンクのそれぞれのハッシュをパケットのＲＥ符号化のために符号器５１２によってチェックできるように、パケットのパケット・クラスの符号器リスト内の符号器５１２のそれぞれをトラバースすることを要求される。
【００７９】
図６に、チャンク一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す。より具体的には、図６は、チャンク一致ＲＥのＲＥ復号ミドルボックス１１２Ｄの例示的実施形態（ＲＥ復号ミドルボックス６００Ｄと表される）を示す。
【００８０】
チャンク一致ＲＥ手法が、パケットのチャンク（パケットではなく）が格納され、ＲＥ符号化に使用されることを除いて、図２および図３に関して図示し、説明した最大一致ＲＥ手法に類似することに留意されたい。したがって、チャンク一致ＲＥのＲＥ復号ミドルボックス６００Ｅは、最大一致ＲＥのＲＥ復号ミドルボックス３００Ｄに類似する。
【００８１】
さらに、図６のＲＥ復号ミドルボックス６００Ｄが、図５のＲＥ符号化ミドルボックス５００Ｅに類似する形で動作するように構成され、ＲＥ復号ミドルボックス６００Ｄは、ＲＥ符号化ミドルボックス５００Ｅによって実行されるＲＥ符号化機能に相補的なＲＥ復号機能を実行することに留意されたい。
【００８２】
ＲＥ復号ミドルボックス６００Ｄは、クラシファイヤ６１０、分類−復号器マッピング・テーブル６１１、複数の復号器６１２１〜６１２Ｎ（集合的に復号器６１２）、およびマージャ６１５を含む。復号器６１２１〜６１２Ｎは、それぞれ、複数のコンテンツ・ストア６１３１〜６１３Ｎ（集合的にコンテンツ・ストア６１３）および複数のハッシュ領域マッピング・テーブル６１６１〜６１６Ｎ（集合的にハッシュ領域マッピング・テーブル６１６）を含む。
【００８３】
クラシファイヤ６１０は、復号器６１２のそれぞれと通信するように構成される。マージャ６１５も、復号器６１２のそれぞれと通信するように構成される。復号器６１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、復号器６１２１は復号器６１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の復号器６１２が、任意の復号器６１２と直接（すなわち、他の復号器６１２をトラバースせずに）、または、復号器６１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【００８４】
一般に、図６のクラシファイヤ６１０、分類−復号器マッピング・テーブル６１１、復号器６１２、およびマージャ６１５の構成／動作は、それぞれ図３のクラシファイヤ３１０、分類−復号器マッピング・テーブル３１１、復号器３１２、およびマージャ３１５の構成／動作に類似する。しかし、復号器６１２は、クラシファイヤ６１０によって分類されたパケットを格納するように構成されるのではなく、クラシファイヤ６１０によって分類されたパケットをチャンクに分割し、チャンクを（それからチャンクが生成されたパケットではなく）復号器６１２のコンテンツ・ストア６１３に格納するように構成される。一実施形態では、所与のパケット・クラスのパケットについて、所与のパケット・クラスの復号器リスト内の最初の復号器６１２が、パケットをチャンクに分割する責任を負う。パケットのチャンクを、復号器６１２によって任意の適切な形で処理することができる。
【００８５】
一実施形態（図６に示された）では、チャンクの格納および処理の責任が、ハッシュ領域に基づいて復号器６１２にまたがって分割される。
【００８６】
一実施形態では、各復号器６１２１〜６１２Ｎは、それぞれハッシュ領域を割り当てられる。一実施形態では、最初の復号器６１２１は、ハッシュ領域［０．０−ａ］を割り当てられ、２番目の復号器６１２２は、ハッシュ領域［ａ−ｂ］を割り当てられ、以下同様に、最後の１つ前の復号器６１２Ｎ−１は、ハッシュ領域［（ｎ−２）−（ｎ−１）］を割り当てられ、最後の復号器６１２Ｎは、ハッシュ領域［（ｎ−１）−１．０］を割り当てられる。これらのハッシュ領域が、単に例示であり、任意の適切なサイズの任意の適切な個数のハッシュ領域を復号器６１２に割り当てることができることに留意されたい。主に、各復号器６１２が単一のハッシュ領域だけを割り当てられる実施形態に関して図示され、説明されるが、１つまたは複数の復号器６１２が、複数のハッシュ領域を割り当てられ得ることに留意されたい。
【００８７】
一実施形態では、復号器６１２は、（１）チャンクについて計算されたハッシュが復号器６１２に割り当てられたハッシュ領域内に含まれる場合に、復号器６１２がチャンクを格納し、（２）チャンクが復号器６１２に割り当てられたハッシュ領域内に含まれる関連するハッシュを有する場合に、復号器６１２がチャンクのルックアップだけを実行するように構成される。
【００８８】
一実施形態では、ハッシュ領域の責任を負う復号器６１２へのハッシュ領域のマッピングは、ハッシュ領域マッピング・テーブル６１６１〜６１６Ｎ内で維持される（すなわち、各復号器６１２が、どのハッシュ領域がどの復号器６１２にマッピングされるのかを示す情報を有する）。主に、ハッシュ領域の責任を負う復号器６１２へのハッシュ領域のマッピングが、それぞれ復号器６１２１〜６１２Ｎ上で実施されるＮ個のハッシュ領域マッピング・テーブル６１６１〜６１６Ｎを使用して維持される実施形態に関して図示され、説明されるが、ハッシュ領域の責任を負う復号器６１２へのハッシュ領域のマッピングを、復号器６１２のそれぞれからアクセス可能な単一のハッシュ領域マッピング・テーブルを使用して、または復号器６１２のそれぞれのサブセットからアクセス可能な複数のハッシュ領域マッピング・テーブルを使用して、維持することができることに留意されたい。
【００８９】
ＲＥ復号ミドルボックス６００Ｄの動作は、パケットがＲＥ復号ミドルボックス６００Ｄで受信される時にＲＥ復号のために処理される形を考慮することによって、最もよく理解することができる。クラシファイヤ６１０は、パケットを関連するパケット・クラスに分類する。クラシファイヤ６１０は、分類−復号器マッピング・テーブル６１１からクラシファイヤ６１０によって判定されたパケット・クラスについて指定された符号器リスト内の最初の復号器６１２にパケットを供給する。最初の復号器６１２は、パケット内に含まれる符号化キーを復号する。符号化キーは、復号器６１２のうちの１つまたは複数のコンテンツ・ストア６１３に格納されたパケットのチャンクに関連する。符号化キーは、ＲＥ符号化ミドルボックス１１２Ｅによって計算されたチャンクのハッシュとすることができる。最初の復号器６１２は、最初の復号器６１２に割り当てられたハッシュ領域内に含まれるそれぞれのハッシュを有するチャンクのそれぞれについて、そのコンテンツ・ストア６１３へのルックアップを実行する。最初の復号器６１２は、（１）最初の復号器６１２に割り当てられたハッシュ領域内に含まれるそれぞれのハッシュを有するチャンクのそれぞれの符号化キーを（２）最初の復号器６１２に割り当てられたハッシュ領域内に含まれるそれぞれのハッシュを有するチャンクのそれぞれの符号化キーに対応するチャンクに置換することによって、パケットの復号を実行する。その後、最初の復号器６１２は、パケットが供給される次の復号器６１２を選択する。最初の復号器６１２は、（１）パケットの残りの符号化キーのハッシュ（すなわち、最初の復号器６１２によって識別されたが、最初の復号器６１２がそれに関して責任を負うハッシュ領域の外に含まれる１つまたは複数のハッシュ）、（２）ハッシュ領域の責任を負う復号器６１２へのハッシュ領域のマッピング（最初の復号器６１２のハッシュ領域マッピング・テーブル６１６内で指定される）、および（３）パケット・クラスの復号器リスト（パケット自体の中で指定されまたは分類−復号器マッピング・テーブル６１１から入手可能）に基づいて、パケットが供給される次の復号器６１２を選択する。たとえば、最初の復号器６１２は、（１）パケットの残りのハッシュのうちの１つまたは複数の責任を負う１つまたは複数の他の復号器６１２を識別するために、パケットの残りのハッシュを使用して、そのハッシュ領域マッピング・テーブル６１６を検索し（パケットの残りのハッシュは、最初の復号器６１２によって計算されたが最初の復号器６１２がそれに関して責任を負うハッシュ領域の外に含まれるハッシュである）、（２）パケット・クラスの復号器リストに基づいて１つまたは複数の他の復号器６１２から次の復号器６１２を選択することができる。たとえば、最初の復号器６１２は、パケット・クラスの復号器リスト上で次の、識別された他の復号器６１２を選択することができる。次に、次の復号器６１２は、（１）次の復号器６１２に割り当てられたハッシュ領域内に含まれるハッシュを有するチャンクごとにパケットの復号を実行し、（２）パケットが伝搬される次の要素（別の復号器６１２またはマージャ６１５）を判定する。パケットの復号は、パケットが完全に復号されるまで、この形で継続される。ハッシュ領域マッピング・テーブル６１６の使用が、パケットが復号器６１２のすべてを通過する必要を無くし（たとえば、復号器６１２の一部が、パケットのチャンクのいずれにも適用可能ではない関連するハッシュ領域を有する場合）、これによって、パケットを復号するための帯域幅使用量の削減をもたらすことに留意されたい。前述の説明は、複数の復号器６１２がパケットを復号するのに使用されると仮定する（パケットを復号するための複数の復号器６１２の使用を例示するために）が、あるパケットが、最初の復号器６１２によって完全に復号され、最初の復号器６１２からマージャ６１５に直接渡されることが可能であることに留意されたい。
【００９０】
たとえば、３つの復号器６１２１〜６１２３を有するＲＥ復号ミドルボックス６００Ｄの場合を検討されたい。この例では、ハッシュ領域を、復号器６１２１（ハッシュ領域［０．０〜０．３］）、復号器６１２２（ハッシュ領域［０．３〜０．６］）、および復号器６１２３（ハッシュ領域［０．６〜１．０］）のように復号器６１２に割り当てることができる。この例では、復号器６１２１は、［０．０〜０．３］ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納し、復号器６１２２は、［０．３〜０．６］ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納し、復号器６１２３は、［０．６〜１．０］ハッシュ領域内のハッシュを有するチャンクだけについてハッシュ・ルックアップを実行し、ハッシュを格納する。したがって、ＲＥ動作のバランスを、３つの復号器６１２にまたがってとることができる。
【００９１】
この形で、チャンク・ルックアップおよびチャンク格納を、ハッシュ領域を適当に分割することによって、任意の適切な形で（たとえば、均等に、ほぼ均等に、または任意の他の適切な形で）復号器６１２にまたがって分散させることができる。
【００９２】
図５のＲＥ符号化ミドルボックス５００Ｅに関して説明したように、図６のＲＥ復号ミドルボックス６００Ｄは、追加の管理機能（たとえば、ハッシュ領域の動的な監視および再構成、ＲＥ復号ミドルボックス６００へ／からの復号器６１２の動的な追加もしくは除去など、ならびにそのさまざまな組合せ）をサポートすることができる。
【００９３】
一実施形態（明瞭さのために省略されている）では、チャンクの格納および処理の責任が、ハッシュ領域を使用せずに復号器６１２にまたがって分割される。一実施形態では、ハッシュ領域が使用されないので、各パケットは、パケットのチャンクのそれぞれのハッシュをパケットのＲＥ復号のために復号器６１２によってチェックできるように、パケットのパケット・クラスの復号器リスト内の復号器６１２のそれぞれをトラバースすることを要求される。
【００９４】
一実施形態では、ＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄは、それぞれＲＥ符号化機能およびＲＥ復号機能を実行するために分散ハッシュ・テーブル（ＤＨＴ：Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ）を活用するように構成される。一般に、ＤＨＴは、ハッシュ・テーブルに似たルックアップ機能および格納機能を提供する分散データ構造であり、任意の参加するノードは、キーに関連する値を効率的に取り出すことができる。さらに、ＤＨＴは、一般に、多数のノードに良好にスケーリングし、ノードの追加／除去を比較的簡単に処理することができる。
【００９５】
ＤＨＴベースの最大一致ＲＥ手法は、符号器２１２の指紋テーブル２１３が符号器２１２にまたがるＤＨＴとして維持され、同様に、復号器３１２の指紋テーブル３１３が復号器３１２にまたがるＤＨＴとして維持されることを除いて、図２および図３に関して図示され、説明された最大一致ＲＥ手法に類似する。最大一致ＲＥに関してＤＨＴを活用するためのＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄの構成を、それぞれ図７および８に関して図示し、説明する。
【００９６】
図７に、ＤＨＴベースの最大一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す。
【００９７】
ＤＨＴベースの最大一致ＲＥのＲＥ符号化ミドルボックス７００Ｅは、最大一致ＲＥのＲＥ符号化ミドルボックス２００Ｅに類似する。
【００９８】
ＲＥ符号化ミドルボックス７００Ｅは、クラシファイヤ７１０、複数の符号器７１２１〜７１２Ｎ（集合的に符号器７１２）、およびＤＨＴ  ７１４を含む。符号器７１２１〜７１２Ｎは、それぞれ、複数のコンテンツ・ストア７１３１〜７１３Ｎ（集合的にコンテンツ・ストア７１３）を含む。ＲＥ符号化ミドルボックス７００Ｅは、マージャ（明瞭さのために図７から省略されている）をも含む。
【００９９】
クラシファイヤ７１０は、符号器７１２のそれぞれと通信するように構成される。符号器７１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、符号器７１２１は、符号器７１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の符号器７１２が、任意の他の符号器７１２と直接（すなわち、他の符号器７１２をトラバースせずに）、または、符号器７１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【０１００】
クラシファイヤ７１０は、パケットを受け取り、受け取られたパケットの分類を判定する。クラシファイヤ７１０は、パケット・クラスに基づいて、パケットを格納し、指紋を計算する責任を符号器７１２に割り当てる（たとえば、符号器７１２１は、第１クラスのパケットを格納し、指紋を計算する責任を負い、符号器７１２２は、第２クラスのパケットを格納し、指紋を計算する責任を負い、以下同様であり、符号器７１２Ｎは、第Ｎクラスのパケットを格納し、指紋を計算する責任を負う）。ＲＥ符号化ミドルボックス７００Ｅは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ７１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ符号化ミドルボックス７００Ｅによってサポートされるパケット・クラスのセットは、ＲＥ復号ミドルボックス１１２Ｄによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ７１０は、パケット・クラスに基づく符号器７１２への責任の割当に従って、分類されたパケットを符号器７１２に供給する。
【０１０１】
ＤＨＴ  ７１４は、パケット・ポインタへの指紋のマッピングを指定する。ＤＨＴ  ７１４内では、所与の指紋のパケット・ポインタは、パケットを取り出すために符号器７１２によって使用され得る情報を含む。パケット・ポインタは、パケット格納位置情報（すなわち、パケットが格納されている符号器７１２を識別する）およびパケット識別子情報（すなわち、パケットが格納されている符号器７１２内のパケットのパケット識別子）を含む。これが、図７に示されており、図７では、第１の指紋（ＦＰ１）は、符号器１：ＩＤ１と表される第１パケット・ポインタを関連付けられ（すなわち、ＦＰ１に関連するパケットは、符号器７１２１に格納されたパケット識別子ＩＤ１を有するパケットである）、第２の指紋（ＦＰ２）は、符号器１：ＩＤ２と表される第２パケット・ポインタを関連付けられ（すなわち、ＦＰ２に関連するパケットは、符号器７１２１に格納されたパケット識別子ＩＤ２を有するパケットである）、第３の指紋（ＦＰ３）は、符号器２：ＩＤ１と表される第３パケット・ポインタを関連付けられ（すなわち、ＦＰ３に関連するパケットは、符号器７１２１に格納されたパケット識別子ＩＤ１を有するパケットである）、などである。
【０１０２】
クラシファイヤ７１０は、パケットを受け取り、クラシファイヤ７１０によって判定されたパケットのパケット・クラスに基づいて符号器７１２のうちの１つ（すなわち、そのパケット・クラスについて割り当てられた主符号器７１２）にパケットを供給する。クラシファイヤ７１０がパケットを供給する主符号器７１２は、パケットを格納し、パケットの指紋を計算する責任を負う。主符号器７１２は、計算された指紋のそれぞれについて、どの符号器７１２が計算された指紋のパケットを格納しつつあるのかを識別し、計算された指紋のパケットを格納しつつある符号器７１２のコンテンツ・ストア７１３内のパケットのパケット識別子を判定するために、ＤＨＴ  ７１４内で指紋ルックアップを実行する。主符号器７１２は、主符号器７１２のコンテンツ・ストア７１３にローカルに格納されたパケットに関連するものとして識別されたすべての指紋のパケットのＲＥ符号化を実行する。その後、主符号器７１２は、主符号器７１２によって計算された指紋に基づいて、パケットがＤＨＴ  ７１４から識別された他の符号器７１２のそれぞれによってさらに処理され得るように、パケットを伝搬させる。
【０１０３】
一実施形態では、パケットは、他の符号器７１２に直列に伝搬される。一実施形態では、主符号器７１２は、パケットを処理する各符号器７１２が、それにパケットを提供すべき次の符号器７１２をパケット自体から直接識別できるように、ＤＨＴ  ７１４から主符号器７１２によって判定されたパケット・ポインタのリストをパケット内に含める。主符号器７１２は、パケットを次の符号器７１２に伝搬させる。次の符号器７１２は、パケットを受け取り、そのコンテンツ・ストア７１３をポイントする各パケット・ポインタを識別するためにパケット内に含まれるパケット・ポインタのリストを解析し、パケットの対応する領域を符号化するのに識別されたパケット・ポインタを使用する。最大一致ＲＥを使用する格納されたパケットの一致する領域に基づく受け取られたパケットの領域の符号化は、少なくとも図２の説明から理解される。その後、次の符号器７１２は、パケットが提供される次の要素（たとえば、パケット内に含まれるパケット・ポインタのリストから判定される別の符号器７１２または、符号器７１２がパケットのＲＥ符号化のためにパケットを処理する最後の符号器である場合にはマージャ）を識別する。パケットの符号化は、パケットが完全に符号化され、マージャに供給されるまで、この形で継続される。
【０１０４】
第１の指紋に関するパケットの一致する領域の展開中に、一致する領域が、第２の指紋に関連するパケットの領域をカバーすると判定される場合に、第２の指紋のポインタを、パケットの符号化中に無視することができることに留意されたい。この場合に、指紋が、現在パケットを処理しつつある符号器７１２のコンテンツ・ストア７１３内で維持されるパケットに関連する場合に、現在そのパケットを処理しつつある符号器７１２は、受け取られたパケットについて計算され、受け取られたパケット内に埋め込まれた指紋のリスト内の次の指紋を無視することができる。同様に、この場合に、指紋が、後続の符号器７１２（すなわち、現在パケットを処理しつつある符号器７１２以外の符号器）のコンテンツ・ストア内で維持されるパケットに関連する場合に、後続の符号器７１２は、受け取られたパケットについて計算され、受け取られたパケット内に埋め込まれた指紋のリスト内の指紋を無視することができる。１つのそのような実施形態では、その指紋を、受け取られたパケット内に含まれる指紋のリストから除去し、これによって、受け取られたパケットをＲＥ符号化する時のその指紋の使用を防ぐことができる。
【０１０５】
パケットの直列符号化の前述の説明は、複数の符号器７１２がパケットを符号化するのに使用されると仮定する（パケットを符号化するための複数の符号器７１２の使用を例示するために）が、パケットが主符号器７１２によって完全に符号化され、主符号器７１２からマージャに直接渡されることが可能であることに留意されたい。
【０１０６】
一実施形態では、パケットは、他の符号器７１２に並列に伝搬される。他の符号器７１２は、パケットの符号化を判定するために処理を実行するが、パケットの符号化を実際には実行しない。そうではなく、他の符号器７１２のそれぞれは、パケットの符号化での使用に適合されたパケット符号化情報を判定し、パケット符号化情報を主符号器７１２に供給する。主符号器７１２は、パケット符号化情報を他の符号器７１２から受け取り、他の符号器７１２からのパケット符号化情報に基づいてパケットを符号化する（たとえば、主符号器７１２によって計算される指紋のすべてに関する関連する符号化キーとの一致する領域の置換を含むパケット符号化を実行する）。他の符号器７１２のうちの１つによって判定されるパケット符号化情報は、他の符号器７１２がそのコンテンツ・ストア７１３内に関連するパケットを格納する指紋ごとに、指紋に関連する一致する領域の一致する領域符号化情報を含む。一致する領域符号化情報は、指紋に関する一致する領域の長さと、一致する領域が突き止められたパケット内の位置（たとえば、一致する領域オフセット情報）とを含む。その後、主符号器７１２は、受け取られたパケットのＲＥ符号化を実行するのに、受け取られたパケットの指紋のそれぞれの一致する領域長さ値および一致する領域オフセット値を使用することができる。その後、主符号器７１２は、符号化されたパケットをマージャに供給する。
【０１０７】
パケットを他の符号器７１２に並列に供給し、パケットの一致する領域のすべてに関する実際のパケット符号化を実行するように主符号器７１２を構成することによって、主符号器７１２が、すべての一致する領域を展望し、帯域幅節約を最大にする形で（他の符号器７１２のそれぞれでの処理オーバーヘッドを増やすことを犠牲にして）一致する領域を比較することができることに留意されたい。
【０１０８】
主に、主符号器７１２がパケットの指紋を計算する唯一の符号器７１２である実施形態に関して図示され、説明されるが、少なくとも１つの実施形態では、指紋の計算を、複数の符号器７１２によって（または符号器７１２のそれぞれによってさえ）実行することができることに留意されたい。これは、他の符号器７１２が、パケットのＲＥ符号化のためにパケットを直列にまたは並列に処理する場合に使用することができる。
【０１０９】
そのような実施形態では、符号器７１２のうちの異なる符号器が、パケットのパケット・クラスに基づいて、異なるパケットのＲＥ符号化機能の異なるセットを実行する。
【０１１０】
ＤＨＴベースの最大一致ＲＥ手法が、クラシファイヤ７１０のポリシに基づいてさまざまな符号器７１２にわたって計算および格納を分散させることを可能にすると同時に、ＤＨＴ  ７１４が、指紋のルックアップおよび挿入の負荷平衡化を提供することに留意されたい。ここで、ＤＨＴ  ７１４が負荷平衡化を提供するので、ノード順序トラバーサルの置換は、負荷平衡化のために必要ではない。
【０１１１】
図８に、ＤＨＴベースの最大一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す。
【０１１２】
ＤＨＴベースの最大一致ＲＥのＲＥ復号ミドルボックス８００Ｄは、最大一致ＲＥのＲＥ復号ミドルボックス３００Ｄに類似する。
【０１１３】
図８のＲＥ復号ミドルボックス８００Ｄは、図７のＲＥ符号化ミドルボックス７００Ｅに類似する形で動作するように構成され、ＲＥ復号ミドルボックス８００Ｄは、ＲＥ符号化ミドルボックス７００Ｅによって実行されるＲＥ符号化機能に相補的なＲＥ復号機能を実行する。
【０１１４】
ＲＥ復号ミドルボックス８００Ｅは、クラシファイヤ８１０、複数の復号器８１２１〜８１２Ｎ（集合的に復号器８１２）、およびＤＨＴ  ８１４を含む。復号器８１２１〜８１２Ｎは、それぞれ、複数のコンテンツ・ストア８１３１〜８１３Ｎ（集合的にコンテンツ・ストア８１３）を含む。ＲＥ復号ミドルボックス８００Ｅは、マージャ（明瞭さのために図８から省略されている）をも含む。
【０１１５】
クラシファイヤ８１０は、復号器８１２のそれぞれと通信するように構成される。復号器８１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、復号器８１２１は、復号器８１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の復号器８１２が、任意の他の復号器８１２と直接（すなわち、他の復号器８１２をトラバースせずに）、または、復号器８１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【０１１６】
クラシファイヤ８１０は、パケットを受け取り、受け取られたパケットの分類を判定する。クラシファイヤ８１０は、パケット・クラスに基づいて、パケットを格納し、符号化キー・ルックアップを実行する責任を復号器８１２に割り当てる（たとえば、復号器８１２１は、第１クラスのパケットを格納し、符号化キー・ルックアップを実行する責任を負い、復号器８１２２は、第２クラスのパケットを格納し、符号化キー・ルックアップを実行する責任を負い、以下同様であり、復号器８１２Ｎは、第Ｎクラスのパケットを格納し、符号化キー・ルックアップを実行する責任を負う）。ＲＥ復号ミドルボックス８００Ｅは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ８１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ復号ミドルボックス８００Ｄによってサポートされるパケット・クラスのセットは、ＲＥ符号化ミドルボックス１１２Ｅによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ８１０は、パケット・クラスに基づく復号器８１２への責任の割当に従って、分類されたパケットを復号器８１２に供給する。
【０１１７】
ＤＨＴ  ８１４は、パケット・ポインタへの符号化キーの、格納されたパケットへのマッピングを指定する。ＤＨＴ  ８１４内では、所与の符号化キーのパケット・ポインタは、受け取られたパケットの符号化キーを格納されたパケットからのコンテンツに置換する際の使用のためにパケットを取り出すのに復号器８１２によって使用され得る情報を含む。パケット・ポインタは、格納されたパケットのパケット格納位置情報（すなわち、パケットが格納されている復号器８１２を識別する）およびパケット識別子情報（すなわち、パケットが格納されている復号器８１２内の格納されたパケットのパケット識別子）を含む。これが、図８に示されており、図８では、第１符号化キー（ＥＫ１）は、復号器１：ＩＤ３と表される第１パケット・ポインタを関連付けられ（すなわち、ＥＫ１に関連するパケットは、復号器８１２１に格納されたパケット識別子ＩＤ３を有するパケットである）、第２符号化キー（ＥＫ２）は、復号器１：ＩＤ４と表される第２パケット・ポインタを関連付けられ（すなわち、ＥＫ２に関連するパケットは、復号器８１２１に格納されたパケット識別子ＩＤ４を有するパケットである）、第３符号化キー（ＥＫ３）は、復号器２：ＩＤ２と表される第３パケット・ポインタを関連付けられ（すなわち、ＥＫ３に関連するパケットは、復号器８１２２に格納されたパケット識別子ＩＤ２を有するパケットである）、などである。
【０１１８】
クラシファイヤ８１０は、パケットを受け取り、クラシファイヤ８１０によって判定されたパケットのパケット・クラスに基づいて復号器８１２のうちの１つ（すなわち、そのパケット・クラスについて割り当てられた主復号器８１２）にパケットを供給する。クラシファイヤ８１０がパケットを供給する主復号器８１２は、パケットについて符号化キールックアップを実行する責任を負う。主復号器８１２は、受け取られたパケットの符号化キーのそれぞれについて、どの復号器８１２が符号化キーのパケットを格納しつつあるのかを識別し、符号化キーのパケットを格納しつつある復号器８１２のコンテンツ・ストア８１３内のパケットのパケット識別子を判定するために、ＤＨＴ  ８１４内で符号化キー・ルックアップを実行する。主復号器８１２は、主復号器８１２のコンテンツ・ストア８１３にローカルに格納されたパケットに関連するものとして識別されたすべての符号化キーのパケットのＲＥ復号を実行する。その後、主復号器８１２は、主復号器８１２によって識別された符号化キーに基づいて、パケットがＤＨＴ  ８１４から識別された他の復号器８１２のそれぞれによってさらに処理され得るように、パケットを伝搬させる。
【０１１９】
一実施形態では、パケットは、他の復号器８１２に直列に伝搬される。一実施形態では、主復号器８１２は、パケットを処理する各復号器８１２が、それにパケットを提供すべき次の復号器８１２をパケット自体から直接識別できるように、ＤＨＴ  ８１４から主復号器８１２によって判定されたパケット・ポインタのリストをパケット内に含める。主復号器８１２は、パケットを次の復号器８１２に伝搬させる。次の復号器８１２は、パケットを受け取り、そのコンテンツ・ストア８１３をポイントする各パケット・ポインタを識別するためにパケット内に含まれるパケット・ポインタのリストを解析し、パケットの対応する領域を復号するのに識別されたパケット・ポインタを使用する。最大一致ＲＥを使用する受け取られたパケットの領域の復号は、少なくとも図３の説明から理解される。その後、次の復号器８１２は、パケットが提供される次の要素（たとえば、パケット内に含まれるパケット・ポインタのリストから判定される別の復号器８１２または、復号器８１２がパケットのＲＥ復号のためにパケットを処理する最後の復号器である場合にはマージャ）を識別する。パケットの復号は、パケットが完全に復号され、マージャに供給されるまで、この形で継続される。パケットのＲＥ復号を実行する最後の復号器８１２は、復号されたパケットをそのコンテンツ・ストア８１３に格納する。パケットの直列復号の前述の説明が、複数の復号器８１２がパケットを復号するのに使用されることを仮定する（パケットを復号するための複数の復号器８１２の使用を例示するために）が、パケットが、主復号器８１２によって完全に復号され、主復号器８１２からマージャに直接渡されることが可能であることに留意されたい。
【０１２０】
一実施形態では、パケットは、他の復号器８１２に並列に伝搬される。他の復号器８１２は、パケットの復号を判定するために処理を実行するが、パケットの復号を実際には実行しない（すなわち、復号器８１２は、符号化キーを、符号化キーによって示されるパケットの対応する部分に置換しない）。そうではなく、他の復号器８１２のそれぞれは、パケットの復号での使用に適合されたパケット復号情報を判定し、パケット復号情報を主復号器８１２に供給する。主復号器８１２は、パケット復号情報を他の復号器８１２から受け取り、他の復号器８１２からのパケット復号情報に基づいてパケットを復号する（たとえば、主復号器８１２によって識別される符号化キーのすべてに関する格納されたパケットの関連する一致する領域との符号化キーの置換を含むパケット復号を実行する）。他の復号器８１２のうちの１つによって判定されるパケット復号情報は、他の復号器８１２がそのパケット・ストア８１３内に関連するパケットを格納する符号化キーごとに、パケット内の符号化キーを置換するのに使用されるコンテンツを含む。その後、主復号器８１２は、パケットのＲＥ復号を実行するのに、パケットの指紋のそれぞれについて受け取られたコンテンツを使用することができる。その後、主復号器８１２は、符号化されたパケットをマージャに供給する。主に、主復号器８１２がパケットを他の復号器８１２に並列に伝搬させ、他の復号器８１２がパケット復号情報を主復号器８１２に返す実施形態に関して図示され、説明されるが、少なくとも１つの実施形態では、主復号器８１２が、パケット自体以外の情報を他の復号器８１２に伝搬させるように構成され（たとえば、他の復号器８１２によって処理されるそれぞれの符号化キーまたは類似物）、他の復号器８１２が、パケット復号情報を主復号器８１２に返すことに留意されたい。
【０１２１】
主に、主復号器８１２がパケットの符号化キーを識別する唯一の復号器８１２である実施形態に関して図示され、説明されるが、少なくとも１つの実施形態では、符号化キーの識別を、複数の復号器８１２によって（または復号器８１２のそれぞれによってさえ）実行することができることに留意されたい。これは、他の復号器８１２が、パケットのＲＥ復号のためにパケットを直列にまたは並列に処理する場合に使用することができる。
【０１２２】
そのような実施形態では、復号器８１２のうちの異なる復号器が、パケットのパケット・クラスに基づいて、異なるパケットのＲＥ復号機能の異なるセットを実行する。
【０１２３】
ＤＨＴベースの最大一致ＲＥ手法が、クラシファイヤ８１０のポリシに基づいてさまざまな復号器８１２にわたって計算および格納を分散させることを可能にすると同時に、ＤＨＴ  ８１４が、符号化キー・ルックアップの負荷平衡化を提供することに留意されたい。ここで、ＤＨＴ  ８１４が負荷平衡化を提供するので、ノード順序トラバーサルの置換は、負荷平衡化のために必要ではない。
【０１２４】
ＤＨＴベースのチャンク一致ＲＥ手法は、符号器５１２の指紋テーブル５１３およびハッシュ領域マッピング・テーブル５１６が、符号器５１２にまたがるＤＨＴとして維持され、同様に、復号器６１２の指紋テーブル６１３およびハッシュ領域マッピング・テーブル６１６が、復号器６１２にまたがるＤＨＴとして維持されることを除いて、図５および６に関して図示され、説明されたチャンク一致ＲＥ手法に類似する。チャンク一致ＲＥのＤＨＴを活用するためのＲＥ復号ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄの構成を、それぞれ図９および１０に関して図示し、説明する。
【０１２５】
図９に、ＤＨＴベースのチャンク一致ＲＥのＲＥ符号化ミドルボックスの例示的実施形態を示す。
【０１２６】
ＤＨＴベースのチャンク一致ＲＥのＲＥ符号化ミドルボックス９００Ｅは、チャンク一致ＲＥのＲＥ符号化ミドルボックス５００Ｅに類似する。
【０１２７】
ＲＥ符号化ミドルボックス９００Ｅは、クラシファイヤ９１０、複数の符号器９１２１〜９１２Ｎ（集合的に符号器９１２）、およびＤＨＴ  ９１４を含む。ＲＥ符号化ミドルボックス９００Ｅは、マージャ（明瞭さのために図９から省略されている）をも含む。
【０１２８】
クラシファイヤ９１０は、符号器９１２のそれぞれと通信するように構成される。符号器９１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、符号器９１２１は、符号器９１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の符号器９１２が、任意の他の符号器９１２と直接（すなわち、他の符号器９１２をトラバースせずに）、または、符号器９１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【０１２９】
クラシファイヤ９１０は、パケットを受け取り、受け取られたパケットの分類を判定する。クラシファイヤ９１０は、パケット・クラスに基づいて、チャンク計算の責任を符号器９１２に割り当てる（たとえば、符号器９１２１は、第１クラスのチャンク計算の責任を負い、符号器９１２２は、第２クラスのチャンク計算の責任を負い、以下同様であり、符号器９１２Ｎは、第Ｎクラスのチャンク計算の責任を負う）。ＲＥ符号化ミドルボックス９００Ｅは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ９１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ符号化ミドルボックス９００Ｅによってサポートされるパケット・クラスのセットは、ＲＥ符号化ミドルボックス１１２Ｅによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ９１０は、パケット・クラスに基づく符号器９１２への責任の割当に従って、分類されたパケットを符号器９１２に供給する。
【０１３０】
ＤＨＴ  ９１４は、チャンクへの指紋のマッピングを指定する。ＤＨＴ  ９１４では、チャンクの指紋は、チャンクにマッピングされるチャンクのハッシュである。言い替えると、チャンク自体が、ＤＨＴ  ９１４内で維持される。これが、図９に示されており、図９では、チャンク１の第１の指紋（ＦＰ１）（チャンク１のハッシュである）が、チャンク１にマッピングされ、チャンク２の第２の指紋（ＦＰ２）（チャンク２のハッシュである）が、チャンク２にマッピングされ、チャンク３の第３の指紋（ＦＰ３）（チャンク３のハッシュである）が、チャンク３にマッピングされるなどである。
【０１３１】
クラシファイヤ９１０は、パケットを受け取り、クラシファイヤ９１０によって判定されたパケットのパケット・クラスに基づいて符号器９１２のうちの１つにパケットを供給する。符号器９１２は、そのパケットのチャンクを計算する。符号器９１２は、パケットのチャンクの指紋を計算する。符号器９１２は、ＤＨＴ  ９１４を使用して、パケットのチャンクの指紋ルックアップおよび挿入を実行する。符号器９１２は、パケットのチャンクの指紋ルックアップに基づいて、パケットのＲＥ符号化を実行する。符号器９１２は、符号化されたパケットをマージャに供給する。
【０１３２】
そのような実施形態では、符号器９１２のうちの異なる符号器が、パケットのパケット・クラスに基づいて、異なるパケットのＲＥ符号化機能を実行する。
【０１３３】
ＤＨＴベースのチャンク一致ＲＥ手法が、クラシファイヤ９１０のポリシに基づいてさまざまな符号器９１２にわたって計算および格納を分散させることを可能にすると同時に、ＤＨＴ  ９１４（より大きいハッシュ・テーブルを提供する）が、指紋のルックアップおよび挿入の負荷平衡化を提供することに留意されたい。
【０１３４】
図１０に、ＤＨＴベースのチャンク一致ＲＥのＲＥ復号ミドルボックスの例示的実施形態を示す。
【０１３５】
ＤＨＴベースのチャンク一致ＲＥのＲＥ復号ミドルボックス１０００Ｄは、チャンク一致ＲＥのＲＥ復号ミドルボックス６００Ｄに類似する。
【０１３６】
図１０のＲＥ復号ミドルボックス１０００Ｄは、図９のＲＥ符号化ミドルボックス９００Ｅに似た形で動作するように構成され、ＲＥ復号ミドルボックス１０００Ｄは、ＲＥ符号化ミドルボックス９００Ｅによって実行されるＲＥ符号化機能に相補的なＲＥ復号機能を実行する。
【０１３７】
ＲＥ復号ミドルボックス１０００Ｄは、クラシファイヤ１０１０、複数の復号器１０１２１〜１０１２Ｎ（集合的に復号器１０１２）、およびＤＨＴ  １０１４を含む。ＲＥ復号ミドルボックス１０００Ｄは、マージャ（明瞭さのために図１０から省略されている）をも含む。
【０１３８】
クラシファイヤ１０１０は、復号器１０１２のそれぞれと通信するように構成される。復号器１０１２は、お互いと通信するように構成され、主にお互いと直列に通信するものとして図示されるが（例示として、復号器１０１２１は、復号器１０１２２と通信し、以下同様であり、また、反対の順序で通信する）、少なくともいくつかの実施形態では、任意の復号器１０１２が、任意の他の復号器１０１２と直接（すなわち、他の復号器１０１２をトラバースせずに）、または、復号器１０１２の図示の順序をトラバースせずに間接的に、通信することができることに留意されたい。
【０１３９】
クラシファイヤ１０１０は、パケットを受け取り、受け取られたパケットの分類を判定する。クラシファイヤ１０１０は、パケット・クラスに基づいて、チャンク計算の責任を復号器１０１２に割り当てる（たとえば、復号器１０１２１は、第１クラスのチャンク計算の責任を負い、復号器１０１２２は、第２クラスのチャンク計算の責任を負い、以下同様であり、復号器１０１２Ｎは、第Ｎクラスのチャンク計算の責任を負う）。ＲＥ復号ミドルボックス１０００Ｄは、任意の適切な判断基準に基づくものとすることができる任意の適切な個数およびタイプのパケット・クラスをサポートすることができる。たとえば、クラシファイヤ１０１０による受け取られたパケットの分類を、ラウンドロビンの形で、パケットのパケット・サイズに基づく負荷平衡化を使用してなどで実行することができる。一実施形態では、ＲＥ復号ミドルボックス１０００Ｄによってサポートされるパケット・クラスのセットは、ＲＥ符号化ミドルボックス１１２Ｅによってサポートされるパケット・クラスのセットと同一である。クラシファイヤ１０１０は、パケット・クラスに基づく復号器１０１２への責任の割当に従って、分類されたパケットを復号器１０１２に供給する。
【０１４０】
ＤＨＴ  １０１４は、チャンクへの符号化キーのマッピングを指定する。ＤＨＴ  １０１４では、チャンクの符号化キーは、チャンクにマッピングされるチャンクのハッシュである。一実施形態では、チャンク自体が、ＤＨＴ  １０１４内で維持される。これが、図１０に示されており、図１０では、チャンク１の第１の符号化キー（ＥＫ１）（チャンク１のハッシュである）が、チャンク１にマッピングされ、チャンク２の第２の符号化キー（ＥＫ２）（チャンク２のハッシュである）が、チャンク２にマッピングされ、チャンク３の第３の符号化キー（ＥＫ３）（チャンク３のハッシュである）が、チャンク３にマッピングされるなどである。
【０１４１】
クラシファイヤ１０１０は、パケットを受け取り、クラシファイヤ１０１０によって判定されたパケットのパケット・クラスに基づいて復号器１０１２のうちの１つにパケットを供給する。パケットの符号化された領域について、復号器１０１２は、符号化されたパケット内の符号化キーを識別することと、ＤＨＴ  １０１４からチャンクを取り出すのに符号化キーを使用することと、符号化キーをＤＨＴ  １０１４から取り出されたチャンクに置換することとによって、パケットを復号する。パケットの符号化されていない部分について、復号器１０１２は、パケットの符号化されていない部分のチャンクのハッシュを計算し、チャンクをＤＨＴ  １０１４に挿入する（たとえば、チャンクごとに、符号化キーとしてのチャンクのハッシュと符号化キーにマッピングされたチャンク自体とを含むレコードを挿入することによって）。復号器１０１２は、復号されたパケットをマージャに供給する。
【０１４２】
そのような実施形態では、復号器１０１２のうちの異なる符号器が、パケットのパケット・クラスに基づいて、異なるパケットのＲＥ復号機能を実行する。
【０１４３】
ＤＨＴベースのチャンク一致ＲＥ手法が、クラシファイヤ１０１０のポリシに基づいてさまざまな復号器１０１２にわたって計算および格納を分散させることを可能にすると同時に、ＤＨＴ  １０１４（より大きいハッシュ・テーブルを提供する）が、符号化キーのルックアップおよび挿入の負荷平衡化を提供することに留意されたい。
【０１４４】
主にチャンク自体がＤＨＴ  １０１４に格納される実施形態に関して図示され、説明されるが、少なくとも１つの実施形態では、ＤＨＴ  １０１４が、関連するチャンクの格納位置（たとえば、チャンクを格納する復号器１０１２の識別子およびチャンクを格納する復号器８１２内のチャンクの識別子に関して指定される）への符号化キーのマッピングを格納することができることに留意されたい。
【０１４５】
ここで図１に戻ると、図２〜図１０から、ＲＥ符号化ミドルボックス１１２Ｅが、さまざまな要素（たとえば、クラシファイヤ、符号器、およびマージャ、ならびに、いくつかの場合に他の要素）を含み、同様に、ＲＥ復号ミドルボックス１１２Ｄが、さまざまな要素（たとえば、クラシファイヤ、復号器、およびマージャ、ならびに、いくつかの場合に他の要素）を含むことがわかる。ＲＥ符号化ミドルボックス１１２ＥおよびＲＥ復号ミドルボックス１１２Ｄを、集合的にＲＥ処理ミドルボックス１１２と称する場合がある（したがって、ＲＥ符号化ミドルボックス１１２Ｅの符号器およびＲＥ復号ミドルボックス１１２Ｄの復号器を、集合的にＲＥデータ・プロセッサまたはＲＥデータ処理モジュールと称する場合がある）。ＲＥ処理ミドルボックス１１２の要素を、クラウド・サイト１１０内で任意の適切な形で実施することができる。たとえば、ＲＥ処理ミドルボックス１１２のクラシファイヤ、ＲＥデータ・プロセッサのそれぞれ、およびマージャを、仮想計算機（ＶＭ）を使用して実施することができる。たとえば、クラシファイヤ、ＲＥデータ・プロセッサのそれぞれ、およびマージャを、それぞれのＶＭを使用して、ＶＭのうちの１つまたは複数が複数の要素（たとえば、複数のＲＥデータ・プロセッサ）を提供するように構成されるＶＭのセットを使用しなどで実施することができる。たとえば、ＶＭを、ブレード・サーバの同一の中央処理装置（ＣＰＵ）上で、同一のブレード・サーバの複数のＣＰＵ上で、同一のスイッチの複数のブレード・サーバにまたがって分散された複数のＣＰＵ上で、複数のスイッチの複数のブレード・サーバにまたがって分散された複数のＣＰＵ上でなど、ならびにそのさまざまな組合せで実施することができる。したがって、そのような要素の間の通信を、クラウド環境内での使用に適切な任意の形でサポートすることができる（たとえば、複数の要素が同一のＣＰＵ上で実施される時の１つのＣＰＵ内の内部通信、要素が同一のブレード・サーバの異なるＣＰＵにまたがって実施される時の１つのブレード・サーバ内だが複数のＣＰＵにまたがる内部通信、要素が異なるブレード・サーバのＣＰＵにまたがって実施される時の同一のスイッチのブレード・サーバの間の通信、要素が異なるスイッチのＣＰＵにまたがって実施される時のクラウド・サイトのスイッチの間の通信など、ならびにそのさまざまな組合せ）。
【０１４６】
主に、ＲＥデータ処理モジュールによって使用されるさまざまなデータ構造がＲＥデータ処理モジュール内に格納される実施形態に関して本明細書に図示され、説明されるが、少なくともいくつかの実施形態では、ＲＥデータ処理モジュールのうちの１つまたは複数のデータ構造のうちの１つまたは複数を、１つまたは複数のＲＥデータ処理モジュールの外部に格納することができることに留意されたい。たとえば、そのようなデータ構造は、コンテンツ・ストア、指紋テーブル、ハッシュ領域マッピング・テーブルなどを含むことができる。したがって、ＲＥデータ処理モジュールによって使用されるさまざまなデータ構造がＲＥデータ処理モジュール内に格納されることを示す本明細書の図示および説明は、ＲＥデータ処理モジュールのデータ構造の情報が関連するＲＥデータ処理モジュールからアクセス可能である（たとえば、内部的にまたはメモリ、ディスク、もしくは任意の他の適切なストレージ・モジュールからそのような情報を取り出す任意の適切な機構を介して）実施形態をも表すことができる。
【０１４７】
図１１に、ＲＥをサポートするパケットの処理の方法の一実施形態を示す。
【０１４８】
方法１１００は、クラシファイヤ、ＲＥデータ・プロセッサのセット（１つまたは複数のＲＥデータ・プロセッサの使用を含むことができる）、およびマージャによって実行されるステップを含む。
【０１４９】
方法１１００が、図２〜１０のいずれかに関して図示され説明されたさまざまな機能を実施する一般的な方法を表すことを理解されたい。
【０１５０】
主に、直列に実行されるものとして本明細書で図示され、説明されるが、方法１１００のステップを、同時にまたは図１１に示されたものとは異なる順序で実行することができることに留意されたい。
【０１５１】
ステップ１１０５では、方法１１００が開始される。
【０１５２】
ステップ１１１０では、クラシファイヤが、パケットを受信する。パケットは、ＲＥ符号化ミドルボックスまたはＲＥ復号ミドルボックスで受信される。ＲＥ符号化ミドルボックスの場合には、クラシファイヤは、適当なソース（たとえば、別のネットワーク、ネットワーク要素、ユーザ・デバイスなど）からパケットを受信する。ＲＥ復号ミドルボックスの場合には、クラシファイヤは、ネットワークを介してＲＥ符号化ミドルボックスからパケットを受信する。
【０１５３】
ステップ１１１５では、クラシファイヤが、パケットのパケット・クラスを判定する。
【０１５４】
ステップ１１２０（いくつかの実施形態で実行されない可能性があるオプションのステップ）では、クラシファイヤが、パケット内でパケットのパケット・クラスをマークする。これは、パケットを処理するのに使用されるＲＥデータ・プロセッサの順序付けを用いてパケットにマークすることを含むことができる。
【０１５５】
ステップ１１２５では、クラシファイヤが、パケットをＲＥデータ・プロセッサのセットに伝搬させる。これが、パケットをＲＥデータ・プロセッサのうちの１つに供給すること、パケットの複数の部分をＲＥデータ・プロセッサのうちの複数に供給すること、パケットの複数のコピーをＲＥデータ・プロセッサのうちの複数に供給することなど、ならびにそのさまざまな組合せを含むことができることに留意されたい。
【０１５６】
ステップ１１３０では、ＲＥデータ・プロセッサのセットが、パケットを受け取る。これが、ＲＥデータ・プロセッサのうちの１つによるパケットの受取、ＲＥデータ・プロセッサのうちの複数によるパケットの複数の部分の受取、ＲＥデータ・プロセッサのうちの複数によるパケットの複数のコピーの受取など、ならびにそのさまざまな組合せを含むことができることに留意されたい。
【０１５７】
ステップ１１３５では、ＲＥデータ・プロセッサのセットが、パケットのパケット・クラスに基づいてＲＥに関してパケットを処理する。このステップを、ＲＥデータ・プロセッサのうちの１つまたは複数によって実行できることに留意されたい。さらに、ＲＥデータ・プロセッサが、パケットまたはパケットの諸部分を交換できることに留意されたい。
【０１５８】
ステップ１１４０では、ＲＥデータ・プロセッサのセットが、パケットをマージャに伝搬させる。
【０１５９】
ステップ１１４５では、マージャが、ＲＥデータ・プロセッサのセットからパケットを受け取る。
【０１６０】
ステップ１１５０では、マージャが、パケットを転送する。ＲＥ符号化ミドルボックスの場合に、マージャは、ネットワークを介してＲＥ復号ミドルボックスに向かってパケットを転送する。ＲＥ復号ミドルボックスの場合に、マージャは、適当な宛先（たとえば、別のネットワーク、ネットワーク要素、ユーザ・デバイスなど）に向かってパケットを転送する。
【０１６１】
ステップ１１５５では、方法１１００が終了する。
【０１６２】
上で注記したように、方法１１００は、全体的に、図２〜１０のいずれかに関して図示され、説明されたさまざまな機能を実施する方法を表す。したがって、図２〜１０のいずれかに関して図示され、説明されたいずれかの機能または機能の組合せを、任意の適切な個数またはタイプのプロセスを使用して実施することができる。そのような実施形態では、図２〜１０のいずれかに関して図示され、説明された１つまたは複数の機能を提供するプロセスを、プロセッサおよびメモリを使用して実施することができ、メモリは、プロセッサによって実行される時にプロセッサにそれらの機能を実行させる命令を格納する。
【０１６３】
図１２に、本明細書で説明される機能を実行する際の使用に適するコンピュータの高レベル・ブロック図を示す。
【０１６４】
コンピュータ１２００は、プロセッサ１２０２（たとえば、中央処理装置（ＣＰＵ）または他の適切なプロセッサ）およびメモリ１２０４（たとえば、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）など）を含む。
【０１６５】
コンピュータ１２００は、協力するモジュール／プロセス１２０５を含むこともできる。協力するプロセス１２０５を、メモリ１２０４にロードし、プロセッサ１２０２によって実行して、本明細書で議論される機能を実施することができ、したがって、協力するプロセス１２０５（関連するデータ構造を含む）を、コンピュータ可読記憶媒体、たとえば、ＲＡＭメモリ、磁気または光学的なドライブまたはディスケットなどに格納することができる。
【０１６６】
コンピュータ１２００は、１つまたは複数の入出力デバイス１２０６（たとえば、ユーザ入力デバイス（キーボード、キーパッド、マウスなど）、ユーザ出力デバイス（ディスプレイ、スピーカなど）、入力ポート、出力ポート、受信器、送信器、１つまたは複数のストレージ・デバイス（たとえば、テープ・ドライブ、フロッピ・ドライブ、ハード・ディスク・ドライブ、コンパクト・ディスク・ドライブなど）など、ならびにそのさまざまな組合せ）を含むこともできる。
【０１６７】
図１２に示されたコンピュータ１２００が、本明細書で説明される機能的要素または本明細書で説明される機能的要素の諸部分を実施するのに適する全般的なアーキテクチャおよび機能性を提供することを理解されたい。たとえば、コンピュータ１２００は、ＲＥ符号化ミドルボックス１１２Ｅ、ＲＥ符号化ミドルボックス１１２Ｅの一部、ＲＥ復号ミドルボックス１１２Ｄ、ＲＥ復号ミドルボックス１１２Ｄの一部、図２〜１０のいずれかのクラシファイヤ、図２〜１０のいずれかの符号器または復号器、図２〜１０のいずれかのマージャなど、ならびにそのさまざまな組合せのうちの１つまたは複数を実施するのに適する全般的なアーキテクチャおよび機能性を提供する。
【０１６８】
本明細書で図示され、説明される機能を、ソフトウェアで（たとえば、特殊目的コンピュータおよび類似物を実施するために汎用コンピュータ上で実行される（たとえば、１つまたは複数のプロセッサによる実行を介して）１つまたは複数のプロセッサ上のソフトウェアの実施態様を介して）実施することができ、またはハードウェアで（たとえば、汎用コンピュータ、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、または任意の他のハードウェア同等物を使用して）実施することができることを理解されたい。
【０１６９】
本明細書でソフトウェア方法として議論されるステップの一部を、ハードウェア内で、たとえばさまざまな方法ステップを実行するためにプロセッサと協力する回路網として実施することができることが企図されている。本明細書で説明される機能／要素の諸部分を、コンピュータ・プログラム製品として実施することができ、ここで、コンピュータ命令は、コンピュータによって処理される時に、本明細書で説明される方法または技法が呼び出されるか他の形で提供されるようにコンピュータの動作を適合させる。発明的方法を呼び出す命令を、固定媒体または取り外し可能媒体に格納し、放送媒体または他の信号担持媒体内のデータ・ストリームを介して送信し、または命令に従って動作するコンピューティング・デバイス内のメモリ内に格納することができる。
【０１７０】
さらに、本明細書で使用される時に、用語「ｏｒ（または）」は、そうではないと示される（たとえば、「ｏｒ  ｅｌｓｅ（または、そうではなく）」または「ｏｒ  ｉｎ  ｔｈｅ  ａｌｔｅｒｎａｔｉｖｅ（または、代替案では）」）場合を除いて、非排他的な「ｏｒ」を指す。
【０１７１】
さまざまな実施形態の諸態様は、特許請求の範囲で指定される。さまざまな実施形態の上記および他の態様は、次の番号付きの条項で指定される。
【０１７２】
１．プロセッサとプロセッサに通信可能に接続されたメモリとを含むデータ処理モジュールを含み、データ処理モジュールは、
受け取られたパケットのパケット・クラスに基づいて複数の冗長性除去（ＲＥ）処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定する
ように構成される、装置。
【０１７３】
２．データ処理モジュールは、ＲＥ符号化モジュールまたはＲＥ復号モジュールを含む、条項１に記載の装置。
【０１７４】
３．データ処理モジュールは、パケットのパケット・クラスに関連する複数のデータ処理モジュールのうちの１つであり、プロセッサは、受け取られたパケットのパケット・クラスに基づいて複数のＲＥ処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定するために、
パケットのパケット・クラスに関連する複数のデータ処理モジュールの順序付きリストを判定し、
複数のデータ処理モジュールの順序付きリスト内のデータ処理モジュールの位置に基づいて、複数のＲＥ処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定する
ように構成される、条項１に記載の装置。
【０１７５】
４．プロセッサは、受け取られたパケット内に含まれる情報に基づいて、パケットのパケット・クラスに関連する複数のデータ処理モジュールの順序付きリストを判定するように構成される、条項３に記載の装置。
【０１７６】
５．データ処理モジュールは、
データ処理モジュールが複数のデータ処理モジュールの順序付きリスト内の最初の位置にあるという判定に基づいて、
受け取られたパケットをデータ処理モジュールに関連するコンテンツ・ストアに格納し、
データ処理モジュールに関連するコンテンツ・ストアおよびデータ処理モジュールに関連する指紋テーブルを使用して、受け取られたパケットについてＲＥ符号化機能を実行する
ように構成される、条項３に記載の装置。
【０１７７】
６．データ処理モジュールは、
データ処理モジュールが、複数のデータ処理モジュールの順序付きリスト内の最初の位置以外の位置にあるという判定に基づいて、
データ処理モジュールに関連するコンテンツ・ストアに受け取られたパケットを格納せずに、データ処理モジュールに関連するコンテンツ・ストアおよびデータ処理モジュールに関連する指紋テーブルを使用して、受け取られたパケットについてＲＥ符号化機能を実行する
ように構成される、条項３に記載の装置。
【０１７８】
７．データ処理モジュールは、
データ処理モジュールが、複数のデータ処理モジュールの順序付きリスト内の最後の位置以外の位置にあるという判定に基づいて、
データ処理モジュールに関連するコンテンツ・ストアに受け取られたパケットを格納せずに、コンテンツ・ストアを使用して、受け取られたパケットについてＲＥ復号機能を実行する
ように構成される、条項３に記載の装置。
【０１７９】
８．データ処理モジュールは、
データ処理モジュールが、複数のデータ処理モジュールの順序付きリスト内の最後の位置にあるという判定に基づいて、
データ処理モジュールに関連するコンテンツ・ストアを使用して、受け取られたパケットについてＲＥ復号機能を実行し、
受け取られたパケットをデータ処理モジュールに関連するコンテンツ・ストアに格納する
ように構成される、条項３に記載の装置。
【０１８０】
９．データ処理モジュールは、
データ処理モジュールが複数のデータ処理モジュールの順序付きリスト内の最初の位置にあるという判定基づいて、
パケットを複数のチャンクに分割し、
データ処理モジュールに関連するコンテンツ・ストアおよびデータ処理モジュールに関連する指紋テーブルを使用してチャンクの少なくとも一部についてＲＥ符号化機能を実行する
ように構成される、条項３に記載の装置。
【０１８１】
１０．複数のデータ処理モジュールは、それに関連するそれぞれの複数のハッシュ領域を有し、データ処理モジュールは、
チャンクのうちの１つのハッシュがデータ処理モジュールのハッシュ領域内に含まれるという判定に基づいて、データ処理モジュールに関連するコンテンツ・ストアおよびデータ処理モジュールに関連する指紋テーブルを使用してチャンクのうちの１つについてＲＥ符号化機能を実行する
ように構成される、条項９に記載の装置。
【０１８２】
１１．前記データ処理モジュールは、最初のデータ処理モジュールであり、複数のデータ処理モジュールは、それに関連するそれぞれの複数のハッシュ領域を有し、最初のデータ処理モジュールは、
チャンクのうちの１つのハッシュが最初のデータ処理モジュールのハッシュ領域の外に含まれるという判定に基づいて、複数のデータ処理モジュールの２番目のデータ処理モジュールのハッシュ領域およびチャンクのうちの１つのハッシュに基づいて最初のデータ処理モジュールから２番目のデータ処理モジュールに向かってパケットを伝搬させる
ように構成される、条項９に記載の装置。
【０１８３】
１２．最初のデータ処理モジュールは、
チャンクのうちの１つのハッシュが２番目のデータ処理モジュールのハッシュ領域内に含まれるという判定に基づいて、２番目のデータ処理モジュールを選択する
ように構成される、条項１１に記載の装置。
【０１８４】
１３．データ処理モジュールは、最初のデータ処理モジュールであり、複数のデータ処理モジュールは、それに関連するそれぞれの複数のハッシュ領域を有し、最初のデータ処理モジュールは、
最初のデータ処理モジュールのハッシュ領域の外に含まれるハッシュを有する複数のチャンクのそれぞれについて、データ処理モジュールのうちで、チャンクのハッシュをカバーする関連するハッシュ領域を有するデータ処理モジュールを識別し、
複数のデータ処理モジュールの順序付きリストに基づいて、識別されたデータ処理モジュールのうちの１つを選択する
ように構成される、条項９に記載の装置。
【０１８５】
１４．データ処理モジュールは、最初のデータ処理モジュールであり、最初のデータ処理モジュールは、
最初のデータ処理モジュールが、複数のデータ処理モジュールの順序付きリスト内の最初の位置以外の位置にあるという判定に基づいて、
複数のデータ処理モジュールの２番目のデータ処理モジュールからパケットおよびパケットの少なくとも１つのチャンクを受け取り、
データ処理モジュールに関連するコンテンツ・ストアおよびデータ処理モジュールに関連する指紋テーブルを使用してパケットの少なくとも１つのチャンクについてＲＥ符号化機能を実行する
ように構成される、条項３に記載の装置。
【０１８６】
１５．データ処理モジュールは、
データ処理モジュールが、複数のデータ処理モジュールの順序付きリスト内の最初の位置にあるという判定に基づいて、
受け取られたパケット内に含まれる各符号化キーを復号する
ように構成される、条項３に記載の装置。
【０１８７】
１６．データ処理モジュールは、
データ処理モジュールに関連するコンテンツ・ストアを使用して、受け取られたパケットの少なくとも１つの符号化キーについてＲＥ復号機能を実行する
ように構成される、条項３に記載の装置。
【０１８８】
１７．複数のデータ処理モジュールは、それに関連するそれぞれの複数のハッシュ領域を有し、データ処理モジュールは、
受け取られたパケットの符号化キーについて、符号化キーに関連するチャンクのハッシュを判定し、
符号化キーに関連するチャンクのハッシュがデータ処理モジュールのハッシュ領域内に含まれるという判定に基づいて、データ処理モジュールに関連するコンテンツ・ストアを使用してチャンクについてＲＥ復号機能を実行する
ように構成される、条項３に記載の装置。
【０１８９】
１８．データ処理モジュールは、最初のデータ処理モジュールであり、最初のデータ処理モジュールは、
受け取られたパケットの符号化キーについて、符号化キーに関連するチャンクのハッシュを判定し、
符号化キーに関連するチャンクのハッシュが最初のデータ処理モジュールのハッシュ領域の外に含まれるという判定に基づいて、複数のデータ処理モジュールの２番目のデータ処理モジュールのハッシュ領域および符号化キーに関連するチャンクのハッシュに基づいて、パケットを最初のデータ処理モジュールから２番目のデータ処理モジュールに向かって伝搬させる
ように構成される、条項３に記載の装置。
【０１９０】
１９．最初のデータ処理モジュールは、
チャンクのハッシュが２番目のデータ処理モジュールのハッシュ領域内に含まれるという判定に基づいて、２番目のデータ処理モジュールを選択する
ように構成される、条項１８に記載の装置。
【０１９１】
２０．データ処理モジュールは、最初のデータ処理モジュールであり、複数のデータ処理モジュールは、それに関連するそれぞれの複数のハッシュ領域を有し、最初のデータ処理モジュールは、
最初のデータ処理モジュールのハッシュ領域の外に含まれるそれぞれの複数のハッシュを有する複数のチャンクのそれぞれについて、データ処理モジュールのうちでチャンクのハッシュをカバーするハッシュ領域を有するデータ処理モジュールを識別し、
複数のデータ処理モジュールの順序付きリストに基づいて、識別されたデータ処理モジュールのうちの１つを選択する
ように構成される、条項３に記載の装置。
【０１９２】
２１．プロセッサとメモリとを含むデータ処理モジュールで、複数の冗長性除去（ＲＥ）処理機能のうちのどれを受け取られたパケットについて実行すべきかを判定するステップを含み、判定するステップは、受け取られたパケットのパケット・クラスに基づく、方法。
【０１９３】
２２．プロセッサとプロセッサに通信可能に接続されたメモリとを含むデータ処理モジュールを含み、データ処理モジュールは、
分散ハッシュ・テーブル（ＤＨＴ）のうちでデータ処理モジュールに関連する部分に基づいて、受け取られたパケットについて冗長性除去（ＲＥ）処理機能を実行する
ように構成される、装置。
【０１９４】
本発明の教示を組み込んださまざまな実施形態を、本明細書で詳細に示し、説明したが、当業者は、これらの教示を組み込む多数の他の変更された実施形態をたやすく考案することができる。
【図１】
0005989242.tif 000002
【図２】
0005989242.tif 000003
【図３】
0005989242.tif 000004
【図４】
0005989242.tif 000005
【図５】
0005989242.tif 000006
【図６】
0005989242.tif 000007
【図７】
0005989242.tif 000008
【図８】
0005989242.tif 000009
【図９】
0005989242.tif 000010
【図１０】
0005989242.tif 000011
【図１１】
0005989242.tif 000012
【図１２】
0005989242.tif 000013