(57)【要約】着信するパケットを識別するための方法。本方法は、フィールドのパターンに関連づけられるデータベースを保持することを含む。ここで、フィールドはネットワーク・アドレスであることが可能である。データベースは、各パターンを一意の数値識別子にマッピングすることによって形成されることが可能である。一意の数値識別子の数はパターンの数に等しく、各一意の数値識別子のサイズは実質的に各パターンのフィールドより小さい。データベースはさらに、各パターンに関連づけられるべき一意の数値識別子のうちの１つまたは複数の範囲を決定することによって展開されることが可能である。各パターンの範囲は、最小の一意の数値識別子及び最大の一意の数値識別子を境界とすることが可能である。また本方法は、着信するパケットのフィールドを使用してそのフィールドに関連づけられる識別子を決定することを含む。ここで、上記関連づけられる識別子は上記一意の数値識別子のうちの１つに等しい。上記関連づけられる識別子は次に上記パターンの範囲のうちの１つまたは複数にマッチされることが可能であり、これで本方法は着信するパケットをどのように処理するかを決定することができる。  【選択図】  図３
2007507915.tif 000002
【特許請求の範囲】
【請求項１】
着信するパケットを分類するための方法であって、
フィールドの１つまたは複数のパターンに関連づけられるデータベースを保持することを含み、上記データベースは、
各パターンを一意の数値識別子にマッピングすることによって作られ、上記一意の数値識別子の数はパターンの数に等しく、各一意の数値識別子のサイズは実質的に各パターンのフィールドより小さく、
各パターンに関連づけられるべき一意の数値識別子のうちの１つまたは複数の範囲を決定することによって作られ、上記範囲は最小の一意の数値識別子と最大の一意の数値識別子とによって制限され、
上記着信するパケットのフィールドを使用してそのフィールドの関連識別子を決定することを含み、上記関連識別子は上記一意の数値識別子の１つに等しく、
上記着信するパケットのフィールドに割り当てられる関連識別子を上記範囲のうちの１つまたは複数にマッチさせることと、
上記マッチングの行為を基礎として上記着信するパケットを如何にして処理するかを決定することを含む方法。
【請求項２】
上記パターンのフィールド及び上記着信するパケットのフィールドはネットワーク・アドレスである請求項１記載の方法。
【請求項３】
上記着信するパケットは２つ以上のフィールドを有し、上記着信するパケットのフィールドを使用して関連識別子を決定する行為は上記着信するパケットのフィールドの各々について実行される請求項１記載の方法。
【請求項４】
上記関連識別子が異なる一意の数値識別子によって制限される範囲の１つにマッチすると、上記範囲内の上記一意の数値識別子間の優先順位を決定することと、最も高い優先順位を選択して処理することをさらに含む請求項１記載の方法。
【請求項５】
上記データベースは木である請求項１記載の方法。
【請求項６】
上記各数値識別子のサイズはｌｏｇ２Ｎより大きい最大の整数に等しく、Ｎは一意のパターンの数である請求項５記載の方法。
【請求項７】
上記木は上記パターンの深さ優先２進トラバーサルを使用して作られる請求項５記載の方法。
【請求項８】
上記着信するパケットのフィールドを使用して関連識別子を決定することは、最長プレフィックスマッチング（ＬＰＭ）プロセスを使用することを含む請求項１記載の方法。
【請求項９】
上記フィールドの１つまたは複数のパターンに関連づけられる第２のデータベースを保持することと、
上記第２のデータベースを上記データベースに交換することをさらに含む請求項１記載の方法。
【請求項１０】
上記着信するパケットのフィールドを使用して関連識別子を決定することはアドレス可能メモリを使用して上記関連識別子をルックアップすることを含む請求項１記載の方法。
【請求項１１】
上記データベースは木を構築することによって作られ、上記木の葉は、
ルート・リーフに対応する最上位ビットを選択することと、
上記パターンのうちの１つのフィールドのうちの１つを左から右へパースし、チャイルド・リーフを作ることによって作られる請求項１記載の方法。
【請求項１２】
パケットの分類において使用するフィールド・パターンのデータベースを作成するための方法であって、
各パターンを一意の数値識別子にマッピングすることを含み、上記一意の数値識別子の数は上記パターンの数に等しく、各一意の数値識別子のサイズは実質的に各パターンのフィールドより小さく、
各パターンに関連づけられるべき一意の数値識別子のうちの１つまたは複数の範囲を決定することを含み、上記範囲は最小の一意の数値識別子と最大の一意の数値識別子とによって制限される方法。
【請求項１３】
上記パターン・フィールドを基礎として上記データベースを作成するための木を構築することをさらに含む請求項１２記載の方法。
【請求項１４】
各パターンをマッピングすることは、上記一意の数値識別子のうちの１つを上記木の各終端ノードへ関連づけることを含む請求項１３記載の方法。
【請求項１５】
着信するパケットを分類するための装置であって、
フィールドの１つまたは複数のパターンに関連づけられるデータベースを備え、上記データベースは、
各パターンを一意の数値識別子にマッピングすることによって作られ、上記一意の数値識別子の数はパターンの数に等しく、各一意の数値識別子のサイズは実質的に各パターンのフィールドより小さく、
各パターンに関連づけられるべき一意の数値識別子のうちの１つまたは複数の範囲を決定することによって作られ、上記範囲は最小の一意の数値識別子と最大の一意の数値識別子とによって制限され、
上記着信するパケットのフィールドを使用してそのフィールドの関連識別子を決定するための手段を備え、上記関連識別子は上記一意の数値識別子のうちの１つに等しく、
上記着信するパケットのフィールドに割り当てられる関連識別子を上記範囲のうちの１つまたは複数にマッチさせるための手段と、
上記マッチングの行為を基礎として上記着信するパケットを如何にして処理するかを決定するための手段とを備える装置。
【請求項１６】
パケット分類のためのシステムであって、
着信するパケットの、フィールドを含むパケット・ヘッダを受信するためと、上記フィールドへ関連識別子を割り当てるためのプリプロセッサと、
第１のメモリ・デバイスとを備え、上記第１のメモリ・デバイスは第１のバイナリ・パターン集合を含み、
第２のメモリ・デバイスを備え、上記第２のメモリ・デバイスは第２のバイナリ・パターン集合を含み、
第３のメモリ・デバイスを備え、上記第３のメモリ・デバイスは上記第１及び第２のバイナリ・パターン集合の一方を上記着信するパケットのフィールドへ割り当てられる関連識別子へ適用するための命令を含み、
上記命令を上記フィールドへ適用して上記フィールドを上記第１のバイナリ・パターン集合または第２のバイナリ・パターン集合におけるパターンのうちの１つへマッチさせるプロセッサを備えるシステム。
【請求項１７】
上記フィールドはネットワーク・アドレスである請求項１６記載のシステム。
【請求項１８】
第４のメモリ・デバイスをさらに備え、上記第４のメモリ・デバイスは上記プロセッサから受信されるマッチされたパターンに対応する結果を含む請求項２６記載のシステム。
【請求項１９】
１つまたは複数のマッチされたパターン間の優先順位を決定するための手段をさらに備える請求項２６記載のシステム。
【請求項２０】
パケット分類のための方法であって、
着信するパケットのパケット・ヘッダを受信することを含み、上記パケット・ヘッダはフィールドを含み、
上記フィールドへ関連識別子を割り当てることと、
第１のバイナリ・パターン集合と第２のバイナリ・パターン集合とを保持することと、
上記第１及び第２のバイナリ・パターン集合の一方を上記着信するパケットのフィールドへ割り当てられる関連識別子へ適用することと、
上記着信するパケットのフィールドを上記第１のバイナリ・パターン集合または第２のバイナリ・パターン集合におけるパターンのうちの１つにマッチさせることを含む方法。
【請求項２１】
パケット分類のための装置であって、
（ａ）複数の処理エレメントを含むプロセッサ・アレイを備え、各処理エレメントは、（ｉ）プログラムされた関係演算を実行することによって、着信するパケットから導出される分類レコードを、実施されるべきルールに関連づけられる１つまたは複数のパターンと比較し、かつ（ｉｉ）上記処理エレメントのうちの２つ以上によって共用されるシフト・レジスタ内の状態情報を捕捉するように構成され、
（ｂ）処理エレメント集合に関する演算を中断して上記処理エレメント集合の演算を再開させる命令デコーダと、
（ｃ）上記シフト・レジスタからの状態情報から最上位の優先性を決定する少なくとも１つの優先順位エンコーダと、
（ｄ）読取り及び書込みケイパビリティに関してアドレス指定されるレコード・メモリとを備え、書込みは同時に処理される幾つかのパケットのうちのどれがパケット分類のための装置へ提出されているかを指示するように実行され、かつ読取りは同時に処理される全てのパケットからどの１つまたは複数のビットがプロセッサ・アレイへ供給されるべきかを指示するように実行される装置。
【請求項２２】
上記プログラムされた関係演算は等しい、小さいか等しい、及び大きいか等しい、の演算を含む請求項２１記載の装置。
【請求項２３】
（ｉ）上記同時に処理されるパケットのうちのどの１つまたは複数のビットが上記プロセッサ・アレイによって調べられるべきかを選択し、かつ（ｉｉ）上記選択された１つまたは複数のビットがどのようにして上記パターンのうちの１つまたは複数と比較されるべきかを決定するための命令を含む命令メモリをさらに備える請求項２１記載の装置。
【請求項２４】
上記命令メモリにおける命令は分類プログラムであり、上記分類プログラムは上記分類プログラムを連続する命令の部分集合に分割する命令をさらに含み、上記連続する命令の部分集合の各々は上記分類プログラムによって定義されるルールの部分集合を表す請求項２３記載の装置。
【請求項２５】
上記ルールの部分集合ペア間には優先順位のついた関係が存在する請求項２４記載の装置。
【請求項２６】
上記レコード・メモリは、上記優先順位エンコーダからの結果が続いて上記分類プログラムによって精査され得るように、上記分類プログラムの実行中に書き直しが可能である請求項２４記載の装置。
【請求項２７】
上記結果は上記優先順位エンコーダによって決定される通りのカレント最優先マッチを含む請求項２６記載の装置。
【請求項２８】
上記レコード・メモリ内の分類レコードのうちの１つから選択される１つまたは複数のビットは、上記分類レコードのうちの１つまたは複数へ適用する上記分類プログラム内の命令の部分集合を決定することができる請求項２４記載の装置。
【請求項２９】
上記選択される１つまたは複数のビットはプログラムされた制御下で選択される請求項２８記載の装置。
【請求項３０】
上記分類プログラムは継目なしに更新されることが可能である請求項２８記載の装置。
【請求項３１】
上記分類プログラムの効果的なサイズは増大され得る請求項２８記載の装置。
【請求項３２】
着信する単一のパケットに適用される処理エレメントの数はスケーリングされ得る請求項２８記載の装置。
【請求項３３】
同時に処理されるパケットの数はスケーリングされ得る請求項２８記載の装置。
【請求項３４】
分類プログラムの選択に使用されるパケット・ビットの数はスケーリングされ得る請求項２８記載の装置。
【請求項３５】
上記装置の複数のインスタンスは、上記装置の第１のインスタンスが上記装置の第２のインスタンスへ供給されるようにカスケードされる請求項２８記載の装置。
【請求項３６】
上記装置の複数のインスタンスは、上記装置の第１のインスタンスが上記装置の第２のインスタンスへ供給されるようにカスケードされる請求項２１記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してパケットを分類する方法とシステムに関し、より特定的には、パケットを効率的に分類するこのような方法とシステムに関する。
【背景技術】
【０００２】
パケットの分類は、高度なネットワーク・アプリケーションにおいてセキュリティ及びサービスの質（ＱｏＳ）の保証を提供する上で必要な前駆作業である。パケットは、パケット交換ネットワーク上で伝送される情報片である。データに加えて、パケットは、上記パケットがどこへ配信されるべきであるかを明記する宛先アドレスと、多くの場合、それがどこを起点とするかを指示するソース・アドレス（このアドレス情報は、典型的には「パケット・ヘッダ」に含まれる）とを含む。概してパケットの分類は、ネットワーク内で他のパケットとは異なる処理をされるべきパケットを濾波し、次にこれらのパケットを規定された方法で処理することに関連する。
【０００３】
パケット分類子は、ルータ、スイッチ及びこれらに類似するデバイスにおいて、パケットの濾波及び処理という機能を実行するために使用される。パケット分類子はルーティングされるべきパケットを受信し、これらをシステム管理者によって保持されるリストと比較する。マッチングが成立すれば、そのパケットは規定された方法で処理される。
【０００４】
パケットの分類における一般的要件は、ルータがパケット・ヘッダ内の情報を基礎としてパケットを分類することである。パケット・ヘッダは、ソース及び宛先アドレス、プロトコル、フラグ及びサービス・タイプ等の様々な情報を含む幾つかのフィールドを含む。パケットは、ルールによって規定されるフローと呼ばれる等価クラスに分類される。例えば、フローは、プレフィックス・ビットで始まるソース・アドレスＳ及びＴＣＰでありかつウェブ・トラフィックのサーバ・ポートへ送られるべきプロトコルを有するパケットの集合である可能性もある。各フローは、それに関連づけられる追加の処理命令を有することが可能である。命令の例には、パケットを特定の待ち行列へ送ること、パケットをドロップすること、またはパケットをコピーすることが含まれる。
【０００５】
パケットの分類は、１０ギガビット／秒のイーサネット（登録商標）・ネットワークにおいて１５００万パケット／秒に近い速度で実行されなければならない。最悪のシナリオにおける典型的なパケット分類子の場合、各パケットは、結果の決定より前に各ルールと比較されなければならない。「Ｎ」個のルールを所与とすると、結果的にパケット分類子によって毎秒１５×Ｎ百万もの比較が実行されなければならないことになる。現時点で、Ｎは典型的にはほぼ１０００である。しかしながら、インターネットに対する需要はさらに複雑になることから、将来的にＮは１００，０００に近づく可能性もある。このような大量のルールは、典型的なパケット分類子において毎秒１．５兆もの比較を必要とする。さらに、パケットの分類に使用される比較は非自明であり、複数のヘッダ・フィールドに渡る同一性及び範囲のチェックより成る。
【発明の開示】
【課題を解決するための手段】
【０００６】
本発明の一実施形態は、着信するパケットを分類するための方法である。このような方法は、例えばＩＰｖ４またはＩＰｖ６パケット・マッチングにおいて使用されることが可能である。本方法は、フィールドのパターンに関連づけられるデータベースを保持することを含む。ここで、上記フィールドはネットワーク・アドレスであることが可能である。本発明のある態様によれば、上記データベースは木データ構造で保持されることが可能である。上記データベースは、各パターンを一意の数値識別子へマッピングすることによって形成されることが可能である。一意の数値識別子の数はパターンの数に等しく、各一意の数値識別子のサイズは実質的に各パターンのフィールドより小さい。上記データベースはさらに、各パターンに関連づけられるべき一意の数値識別子のうちの１つまたは複数の範囲を決定することによって展開されることが可能である。上記各パターンの範囲は、最小の一意の数値識別子及び最大の一意の数値識別子を境界とすることが可能である。また本方法は、着信するパケットのフィールドを使用してそのフィールドに関連づけられる識別子を決定することを含む。ここで、上記関連づけられる識別子は上記一意の数値識別子のうちの１つに等しい。上記関連づけられる識別子は次に上記パターンの範囲のうちの１つまたは複数にマッチされることが可能であり、これで本方法は着信するパケットをどのように処理するかを決定することができる。
【０００７】
本発明の別の実施形態は、上記第１の実施形態の方法に一意に適合する、パケットを分類するための装置である。この実施形態では、複数の単純な処理エレメントがプログラムされた制御下でパケットの分類演算を実行するように編成されかつ制御される。この実施形態の１つのケイパビリティは、数値範囲の演算を有効化すること、即ち、あるフィールドが数値的に２つの目標値の間に存在すると決定することにある。
【０００８】
本発明のさらに別の実施形態は、着信するパケットの分類レコードにおけるデータを使用して、分類レコードに直接印加される分類プログラム・セグメントを選択するメカニズムを提供する。このメカニズムは、２つの特徴を有する。第１に、これは、第１のバイナリ・パターン集合と第２のバイナリ・パターン集合とを保持することを特徴とする。この実施形態では、両バイナリ・パターン集合の一方が演算の間にパケットの分類に使用されることが可能であり、もう一方のバイナリ・パターン集合はシステム管理者によって更新されることが可能である。次に、２つのバイナリ・パターン集合は、パターンの継目のない更新をもたらすために切換されることが可能である。第２に、これは、パケット・ヘッダまたは分類レコードに含まれるデータに関連して分類プログラムのセグメントを選択することを特徴とする。
【０００９】
本発明の他の実施形態は、上述の方法を実行するように構成されたシステムを特徴とする。
【発明を実施するための最良の形態】
【００１０】
Ａ．パケットの分類方法
本発明の実施形態は、ネットワークにおける効率的なパケットの分類をもたらす。本発明は、長いフィールド（ネットワーク・アドレス等）をより短い数値識別子にマッピングし直すことによって比較数を最小限に抑える方法を使用する。数値識別子は、比較において全フィールドの代わりに使用される。必要な演算数の減少をてこ入れすることにより、電力及びコストは節約されることが可能であり、パケット分類子のフットプリントのサイズは所定数のルールに関して縮小されることが可能である。
【００１１】
本発明のある態様によれば、パケットを分類するための方法とシステムが提供される。この実施形態において、パケット分類子は実施されるべきルールセットを保持する。各ルールは、それに包含されるフィールドのパターンを保有する。フィールド（アドレス等）は、着信するパケットのパケット・ヘッダ内に発見されるアドレスとマッチされることが可能である。ある実施形態では、分類識別子と呼ばれる一意の数値識別子は、実施されるべきルールセットにおけるフィールドの各々を識別するために使用される。分類識別子は、ルールセット内に包含されるパターンの数に従って割り当てられる（即ち、各パターンには一意の分類識別子が割り当てられる）。従って、ルール内に保持され得る「Ｎ」個のパターンを所与とすれば、Ｎ個の分類識別子が割り当てられる。特に、各分類識別子の割当ては、ルールに関連づけられる（１つまたは複数の）アドレスから導出されるが、これについては後に詳述する。ある実施形態において、上記フィールドはネットワーク・アドレスである可能性があるが、本発明はネットワーク・アドレス関連のアプリケーションに限定されるものではない。
【００１２】
図１ａは、本発明のこの実施形態のオペレーションを描いたブロック図である。図１ａに示す実施形態では、パターンにおけるアドレス・プレフィックス間の割当て及び一意に割り当てられる数値識別子を供給する第１のデータベースが保持される。ブロック５は、これを示す。ある実施形態においては、このデータベースは木データ構造を使用して実装されることが可能である。次に、各パターンにはそのパターンに対応する一意の数値識別子の範囲が割り当てられる。
【００１３】
また、独立したデータ構造も保持され、このデータ構造は、着信するパケットのパケット・ヘッダの独立した各フィールド（アドレス等）に関連の識別子を供給するために使用される。ブロック１０は、この行為を示す。この行為は、それ自体、パケット分類の前処理ステップであると考えることができる。
【００１４】
次に、着信するパケットの関連の識別子は、第１のデータベースにおいてパターンに割り当てられた範囲と比較される。関連の識別子がこれらの範囲のうちの１つまたはそれ以上の範囲内にあれば、優先順位の計算モジュールを使用してどのルールを実施するかを決定することができる。図１ａのブロック１５は、関連の識別子とパターンの範囲とのこの比較行為を示す。着信するパケットがマッチすれば、これは図１ａのブロック２０が示すように適宜処理される。
【００１５】
１．パターンのリマッピング
図１ａに関して述べたように、各パターンの一意の数値識別子を有するデータベースが形成される。分類識別子とも呼ばれる一意の数値識別子は、着信するパケットとルールとのマッチングに使用される。パケット分類子は、ルールセット内で発見されるＮ個のアドレス（即ちパターン）に関心を示すだけでよい。本発明のこの実施形態では、分類識別子の各々を表すために必要なビット数はｌｏｇ２Ｎより大きい最大の整数に等しい。分類の対象となる共通フィールドは、ＩＰｖ４宛先及びソース・アドレス・フィールド及びＩＰｖ６宛先及びソース・アドレス・フィールドである。これらのアドレスのサイズ範囲は、長さ３２ビット（ＩＰｖ４）乃至１２８ビット（ＩＰｖ６）である。従って、典型的なパケット分類子は、概して各ルール比較に際して３２ビット（例えばＩＰｖ４）を比較する。しかしながら本発明のこの実施形態では、パケット分類子はｌｏｇ２Ｎビットの比較しか行わない。これにより、比較計算を大幅に節約できることになる。
【００１６】
（ルータ及びスイッチにおける）典型的な分類アプリケーションでは、着信するパケットの宛先アドレスは、そのパケットが次にどこへ送られるべきかを決定する調査を必要とする。この調査を達成するためのメカニズムは、本実施形態をパターンの一意の分類識別子を決定するように構築するメカニズムである。このように着信するパケットの宛先アドレスの調査に使用されるメカニズムとしては、良く知られている上記木等のソフトウェア・データ構造及びＴＣＡＭ等のハードウェア・メカニズムを含む多くが存在する。さらに、ルータ及びスイッチはソース・アドレスの妥当性チェックを実行することが多く、これは概して、宛先アドレスの場合と同様のルックアップを必要とする。
【００１７】
一例として、パケット分類子が１０２４個のルールより成るデータベースを保持していると仮定する。このルール・データベースは、各ルールにつき１つで最大１０２４個の異なるアドレス・プレフィックスを保有することができる。このルール・データベースにおけるネットワーク・アドレスの長さに関わりなく、データベースはアドレス・プレフィックスの各々を単に「０乃至１０２３」と呼ぶことができる。即ち、各アドレス・プレフィックスに１つの数が割り当てられる。これらのネットワーク・アドレスの各々に言及する場合に必要なビット数は、１０である（即ち２∧１０＝１０２４）。
【００１８】
演算の間、一意に選択される１０ビットの数（関連識別子と呼ぶ）は宛先アドレスのルックアップ構造における着信パケットの宛先プレフィックスに関連づけられる。ソース・アドレスのルックアップ構造に関しても、同じ作業が行われる。ＩＰｖ４アドレスの場合、必要なビット比較数は６４ビットから２０ビットにまで下がり、４４ビットという大幅な利得になる。ＩＰｖ６アドレスの場合、必要な比較数は２５６ビットから２０ビットまで下がる。
【００１９】
イーサネット（登録商標）・ネットワークにおける現行の１５００万パケット／秒に近い帯域幅速度の場合、Ｎ＝１０２４ルール及びＮ＝１０２４パターンであれば、典型的なパケット分類子は毎秒約１５０億の分類を実行しなければならない。各分類は、通常は宛先及びソース・アドレスを含む幾つかのフィールド上で実行される。（例えば）ＩＰｖ４宛先及びソース・アドレスにおいて調査されるべき個々のビット数は各々３２ビット、または合計６４ビットである。しかしながら、本発明によるこの実施形態を使用する場合、Ｎ＝１０２４ルール及びＮ＝１０２４パターンであれば、１ルール当たりの比較は６４ビットから２０ビットに低減される。これは、これらの重要なフィールド全体でほぼ６８％の利得を表す。ＩＰｖ６の場合、利得は約９２％（２５６アドレス・ビットから２０ビットへ）になる。
【００２０】
次に、分類識別子がパターンに割り当てられるプロセスについて説明する。ルールセット（即ちパターン）に含まれるアドレスには、このプロセスを使用して分類識別子が割り当てられる。さらに、着信するパケットのパケット・ヘッダ内に発見されるアドレスは、ルックアップ手順を使用して関連識別子に関連づけられる。まず、分類識別子をルールセット内に含まれるアドレスに割り当てることができるプロセスについて説明する。本明細書を通じて、ルールセット内に含まれるアドレスを「パターン」と称し、着信するパケットのパケット・ヘッダ内に含まれるアドレスを「ストリング」と称する。
【００２１】
ユーザがルールセットを定義した後、ルールセット内の各パターンに一意の数値識別子を割り当てるデータベースが形成される。一意の数値識別子の長さは、各パターンの長さより短い。ある実施形態では、データベースはルールセットのパターンを使用して形成される木である。木は、着信するパケットに対してパケット分類子の任意のオペレーションが開始されるより前に生成される。
【００２２】
図１ｂは、本発明のある態様による、パターンを使用するデータベースの形成に使用され得る１つのプロセスを示すブロック図である。本プロセスにおける最初のステップ１８５において、ユーザ（例えばネットワーク・マネージャ）はルールセットを定義する。各ルールは、それに包含される１つのパターン（例えばネットワーク・アドレス）を有する。次のステップ１９０では、ルール内に発見される一意のパターンの合計数が決定される。最後のステップ１９５では、パターンの各々が一意の数値識別子にマッピングされる。この一意の数値識別子の割当ては、パターンの２進列を基礎として行われる。一意の数値識別子の各々の長さは、ｌｏｇ２Ｎより大きい最小の整数以下である。但し、Ｎはルールセットにおける一意のパターンの数である。
【００２３】
図２ａは、各パターンに３ビットを有する４つのパターンを有する木の生成を示す。図２ａは、下記のパターン、即ち、
００１
０１０
１１１
０１１
の木を描いたものである。
【００２４】
本プロセスは、２進決定木を使用する。各パターンは、左から右へ（即ち最上位ビットから先に）解析される。ノード１００、１１０、１２０、１３０、１４０及び１５０はボックスで表されている。ノード内の数字は、分類識別子である。ノードは、意志決定経路１０５、１１５、１２５、１３５、１４５及び１５５によって互いに接続される。各意志決定経路は、関連の２進数を有する。木は左から右へ順次生成され、最低値を有するパターンで始まって最高値を有するパターンで終わる。例えば、最初の意志決定経路は、適用可能であれば左側でルート・ノードから子ノードへ分岐する。この意志決定経路は、全てのパターンについて「０」に等しい最上位ビットに関連づけられる。従って、「０」で始まる全てのパターンはこの意志決定経路をトラバースすることになる。ノードは、トラバーサルの前にはそれらに関連づけられる分類識別子を保有しない。最低数値を有するパターンは、木をトラバースする最初のものである。
【００２５】
図２ａにおけるノード１００は、最初のビットの決定点を表す。最初のビットが「０」であれば、パターンは、関連づけられた「０」を有する意志決定経路１０５をトラバースする（パターン「００１」、「０１０」及び「０１１」の場合がこれである）。予想パターンの最初のビットが「１」であれば、パターンは意志決定経路１５５をトラバースする（パターン「１１１」の場合がこれである）。パターン終端にならないノードには、分類識別子「０」が割り当てられる。「０」を有するノードは、ルールセット内のどのパターンにも対応しない。図２ａの例では、「００１」が木をトラバースする最初のパターンである。パターン「００１」はトップ・ノード１００で始まり、このノードはパターン・トラバーサルの終端にはならないことから、ノード１００には分類識別子「０」が割り当てられる。パターン「００１」の最初のビットは「０」であることから、上記パターンは意志決定経路１０５をトラバースする。
【００２６】
ノード１１０には、パターン「００１」がノード１１０で終わらないことから分類識別子「０」が割り当てられる。先の意志決定ステップに従って、パターン「００１」は意志決定経路１１５をトラバースしてノード１２０で終わる。１つの子ノードを有する親ノードは説明の都合で除去され、親の意志決定経路はこの省略を反映している点は留意されるべきである。従って、意志決定経路１１５は、関連づけられる２進列「０１」を有する。パターン「００１」は、ノード１２０でビット切れとなって終わる。従ってノード１２０には、パターン「００１」を一意に識別する分類識別子「１」が割り当てられる。
【００２７】
残りのパターンのうちで最小である次のパターン「０１０」についても、同様のトラバーサルが発生する。パターン「０１０」は、ノード１００、１１０及び１４０を介してトラバースし、ノード１３０で終わる。従って、ノード１３０には分類識別子「２」が割り当てられる。同様のトラバーサルは、全てのパターンに分類識別子が割り当てられるまで網羅的に発生する。例えばパターン「０１１」は、ノード１００、１１０及び１４０をトラバースしてノード１５０で終わる。従って、ノード１５０には分類識別子「３」が割り当てられる。最後に、パターン「１１１」がノード１００を介してトラバースし、ノード１６０で終わる。従って、ノード１６０には分類識別子「４」が割り当てられる。
【００２８】
図２ａの例では、Ｎ＝４である。先に述べたように、これらの４つのアドレスを称するために必要とされるビット数は、ｌｏｇ２Ｎビットである。従ってこの例では、４つのルールを称するために必要とされるビットは僅か２つである。さらに、Ｎ＝４であることから、図２ａの木に関連づけられる一意の分類識別子は４つ存在する。
【００２９】
図２ｂは、ＩＰｖ４アドレスから導出される次の４つのパターン、
１２８．０．０．０／８＝０ｂ１０００００００
１４４．０．０．０／８＝０ｂ１００１００００
１２８．０．０．０／１２＝０ｂ１０００００００．００００
１２８．１９２．０／１０＝０ｂ１０００００００．１１
に関して分類識別子が割当てられて構築された木を描いたものである。
【００３０】
これらのパターンは、各３２ビットＩＰアドレスのサブネット・マスクを表す。例えば、１２８．０．０．０／８のパターンは、このアドレスの最初の８ビット（即ち「１０００００００」）である。同様に、１４４．０．０．０／８のパターンはこのアドレスの最初の８ビット（即ち「１００１００００」）である。
【００３１】
図２ａの例の場合のように、図２ｂの実施形態の分類識別子も、パターンを表す２分木（即ち、各ノードが共通の列プレフィックスを表す木）の予め順序づけされた深さ優先トラバーサルにおいて順次割り当てられることが可能である。図２ｂにおいて、ノード内の数字は分類識別子であり、エッジはそれらをトラバースする部分列（２進列）でラベリングされている。木は、どのパターンにも関連づけられない分岐点である中間ノードを保有する可能性がある。パターンに関連づけられるノードは、「終端」ノードと呼ばれる。
【００３２】
図２ｂでは、分類識別子「０」を割り当てられた、子ノードを１つしか持たないノードは説明を簡略にするために省略されている。省略された意志決定経路に関連づけられる２進数は、親の意志決定経路に吸収されている。例えば、意志決定経路２２５における「０００００」列の代わりに、意志決定経路２２５は、各々が「０」分類識別子を有しかつ各々が意志決定経路の各々に関連づけられる「０」を有する連続する５つのノードによって表されることも可能である。
【００３３】
木データ構造の構築後、これは、各パターンに適切な分類識別子を割り当てるためにトラバースされる。トラバースの方法は、周知の深さ優先トラバーサル・アルゴリズムであってもよい。このトラバーサルは、ルール・マッチングにおけるアドレスの叙述の曖昧さを除くメカニズムを提供し、かつ各パターンに関する分類識別子の範囲のチェックを有効化する幾つかのメカニズムを見込んでいる。
【００３４】
図２ｂに表される木の予め順序づけされた深さ優先トラバーサルの実行は、以下で詳述する通りに進行する。トラバーサルは本質的に、木の終端ノードを列挙する。
【００３５】
ルート・ノード（２０５）は終端ノードではなく、よってこれには数字「０」が割り当てられる。ルート・ノードの子ノードの集合が決定され、この集合は規約により０、１つまたは２つの要素を保有する。これが２つの要素を保有するとき、最初の要素はこれら２つの要素のうちの数字の少ない方である。図２ｂでは、ルート・ノードの唯一の子ノードがノード２１５である。これは終端ノードではなく、よって数字「０」が割り当てられる。
【００３６】
ノード２１５の子集合は、ノード２２０及び２５０を含む。訪問されるのは、この集合の「最初の」要素（ノード２２０）である。ノード２２０は終端ノードでありかつ最初に遭遇されるノードであり、よってこれには数字「１」が割り当てられ、次にその子集合（ノード２３０及び２４０）が調査される。
【００３７】
ノード２３０はノード２２０の子のうちの最初のノードであり、かつノード２３０は終端ノードである。これは遭遇される第２の終端ノードであることから、これには数字「２」が割り当てられる（これは深さ優先トラバーサルにおいて遭遇される第２の終端ノードであることが指示される）。ノード２３０は子を持たず、よってこの経路は終わる。
【００３８】
ノード２４０はノード２２０の子のうちの２番目のノードであり、かつ同じく終端ノードである。これは遭遇される第３の終端ノードであることから、これには数字「３」が割り当てられる。ノード２４０は子を持たず、よってこの経路は終わる。
【００３９】
ノード２１５に戻ると、その子のうちの２番目のノードはさらに列挙されなければならない。ノード２１５の２番目の子はノード２５０であり、これは遭遇される第４の終端ノードであることから「４」が割り当てられる。
【００４０】
図２ｂの例では、Ｎ＝４である。これらの４つのアドレスを称するために必要とされるビット数はｌｏｇ２Ｎビット、または２ビットである。さらに、Ｎ＝４であることから、図２ｂに示すパターンに関連づけられる一意の分類識別子は４つ存在する。
【００４１】
ＩＰアドレスは、他のアドレス内に含まれる場合もある。これは、ルールセットのパターンにおいても発生する。図２ｂの例では、ＩＰアドレス１２８．０．０．０／１２及び１２８．１９２．０．０／１０は１２８．０．０．０／８内に含まれる。これを反映させるために、各パターンの範囲が決定されかつ表にされる。各パターンに割り当てられる分類識別子は、この範囲内に包含されなければならない。さらに、子ノードの分類識別子は、このパターン範囲内に包含されなければならない。
【００４２】
これらの基準は、パターン範囲を決定する下記の方法を使用することによって満たされる。パターンに割り当てられる分類識別子は、パターン範囲の下限となるように選定される。上限は、その下の最大分類識別子（即ち、その下の子ノード）である。これは、分類識別子がより特定的なパターンに対応するとしても（例えば、パターン内の他のフィールドがマッチしなくても）、一般的なパターンの下のより特定的なパターンも一般的なパターンにマッチすることを保証する。
【００４３】
図３は、図２ｂの集合例における各パターンの分類識別子範囲を示す。図３を参照すると、パターン範囲３１０は１乃至３の範囲を包含することが示されている。図２ｂを再度参照すると、パターン範囲３１０は親ノード（それ自体）２２０及びその子ノード２３０、２４０の分類識別子を含むことが分る。パターン範囲３２０、３３０及び３４０は、個々の範囲に関連づけられるノードがそこから分岐する子ノードを持たないことから、１つの分類識別子の範囲を有する。故に、上記ノードの分類識別子は上限及び下限の双方である。範囲が決定されると、パケット分類子が動作する準備が整う。
【００４４】
範囲は、着信するパケットの列が２つ以上のルールに当てはまるかどうかを決定するために使用される。従って、パターンの各々に１つの範囲が割り当てられる場合、上記範囲は上記パターンに割り当てられる分類識別子だけでなくその子ノードの分類識別子も含むことが重要である可能性がある。先の実施形態は、分類識別子を関連パターンの範囲の下限として使用するが、分類識別子がパターンの範囲の上限であることを不可能にするものは何もない。この機能性を獲得するスキームは何れも、本発明の範囲内にある。
【００４５】
下記のコードは、実行されると木を分類識別子で列挙するために使用されることが可能である。但しこのコードは例示的なものであり、このような木は他のコードまたは方法を使用することによっても生成されることが可能である。
【００４６】
・トラバーサル開始前：currentClsId＝０，  nextClsId＝１，  visitRoot（）
・ノードがパターンに符合しなければ：push（currentClsId），  node．ClsId＝currentClsId，  visitChildren（node），  currentClsId＝pop（）
・その他：push（currentClsId），  currentClsId＝nextClsId，  nextClsId＝nextClsId＋１，  node．ClsId＝currentClsId，  visitChildren（node），  currentClsId＝pop（）。
【００４７】
２．パケット分類演算
再度図１ａを参照して、パケットを分類する１つの方法をさらに詳しく説明する。図１ａにおける最初のステップ５は、データベース内の一意の各パターンの一意の数値識別子を有するデータベースを保持することを含む。特には、先に述べたように、データベースはマッチされるべき長々としたパターン（例えば本例ではアドレス）のアレイを含む可能性がある。データベースは、パターン・アレイに対応するより短い一意の数値識別子の対応するアレイを、各パターンにつき１つの一意の数値識別子で保持する。例えば、データベース・パターンのアレイは下記のアレイ、即ち１２８．０．０．０／８、１２８．０．０．０／１２、１２８．１９２．０．０／１０及び１４４．０．０．０／８より成ると仮定する。データベースはアレイの番号を付け替えてこれらのパターンを各々１、２、３及び４と称し、これらを新たなアレイに格納する。新たなアレイの要素は、「一意の数値識別子」または「分類識別子」と呼ばれる。一意の各数値識別子は、それが導出されたもとのパターンを暗に参照し直す。先の項目Ａ．１は、このようなパターン・アレイの生成をより詳しく論じている。さらには、先に述べたように、各パターンの分類識別子範囲が決定される。
【００４８】
パケットがパケット分類子の入口に到達するとき、上記パケットはアドレス情報を含むパケット・ヘッダを含んでいる。この実施形態のオペレーションでは、着信するパケットはプリプロセッサによって受信され、パケット・ヘッダはここでパケットから剥ぎ取られ、パケット・ヘッダ内に包含されるネットワーク・アドレスが識別される。次に、第２のデータベースをトラバースすることにより関連識別子をヘッダ内のネットワーク・アドレスの各々に関連づける試みが行われる。これは、図２ａまたは図２ｂに関連して先に論じたものと同様に行われる場合もあるが、そうである必要はない。ある実施形態では、プリプロセッサは最長プレフィックスマッチ（ＬＰＭ）を実行して各ネットワーク・アドレスへの関連識別子の割当てを試行する。
【００４９】
従って、図１ａにおける第２のステップ１０は、着信するパケットのアドレス（即ちソース及び宛先アドレス）を使用する第２のデータベースのトラバーサルである。この第２のデータベースは、一意の数値識別子のフィールド・パターンへの割当てを実行するために使用された構造に類似するものである場合も、そうでない場合もある。この第２のメカニズムは、先に述べたメカニズムによる、着信するパケットの適切なパケット・フィールドとパターンへ割り当てられる一意の数値識別子との関連づけを有効化するどんなメカニズムにあってもよい。言い替えれば、「関連識別子」は着信するパケットの各フィールド（即ち、ある例ではソース及び宛先アドレス）に割り当てられる。この第２のデータベースは、木またはリスト等のソフトウェア・データ構造及びターナリ・コンテンツ・アドレッサブル・メモリ（ＴＣＡＭ）等のハードウェア・メカニズムを含むことが可能であるが、これらに限定されない。従って、関連識別子とパケット・ヘッダのフィールドとの関連づけは、幾つかのメカニズムを使用して実行されることが可能である。
【００５０】
図１ａにおける第３のステップ１５は、パターンの各々に関連づけられる値の範囲を使用して、着信するパケットのネットワーク・アドレスに割り当てられる関連識別子を１つまたは複数のパターンにマッチングさせることを含む。着信するパケットに割り当てられる関連識別子が１つまたは複数のパターン範囲内に存在すれば、マッチングが成立する。次には、入力される列に関連づけられる関連識別子が各パターンの範囲に照らして試験される（下限≦分類識別子≦上限）。例えば、図３を参照すると、ネットワーク・アドレスに割り当てられた関連識別子が「３」であれば、このネットワーク・アドレスは範囲３１０及び３４０の中にある。従って、このネットワーク・アドレスはパターン１２８．０．０．０／８及び１２８．１９２．０．０／１０に関連づけられるルールにマッチングする。この例では、ネットワーク・アドレスは２つ以上のルールにマッチングする。次には、ルールのうちのどれが実施されるかを決定するために、優先順位の計算を実行することができる。この優先順位の計算は、ネットワーク・アドレスとは別にパケット・ヘッダ内の情報を使用することが可能であり、または別の実施形態では、どのルールが優先性を有するかをユーザが決定することも可能である。
【００５１】
最後のステップ２０は、マッチングされたパターンに従ってパケットを処理することを含む。即ち、マッチングされたパターンに関連づけられるルールがパケット分類子にパケットをドロップするように命令すれば、パケットはドロップされる。
【００５２】
Ｂ．分類識別子ハードウェア
図４は、本発明のある態様によるパケット分類子の一実施形態を描いたものである。破線は、パケット分類子の分類エンジン４００を囲んでいる。図４のこの実施形態は、先に述べたパケットの分類方法を実行するために使用されることが可能である。先に概説した方法の実施には、他のハードウェア実装も使用されることが可能である。
【００５３】
図４を参照すると、分類エンジン４００は、マッチング処理ユニット４４０と、プログラム（テンプレート）４１０と、パターン集合４２０、４３０とを含む。マッチング処理ユニット４１０は、テンプレート４１０から受信されるオペレーションを実行する。分類エンジン４００のテンプレート４１０はユーザの要件によって定義され、マッチング処理ユニット４４０によって実行されるべき演算のリストを保持する。テンプレート４１０は分類レコードのフォーマットを符号化し、実行されるべき演算を上記分類レコードに格納する。テンプレート４１０は、ユーザによってより高位のコードでプログラムされてコンパイルされるルール（図示されていない）で構成される。分類レコードは、パケット・ヘッダのスナップショットであってもよい。分類レコードの目的の１つは、オペランドをマッチング処理ユニット４４０へ送ることである。
【００５４】
パターン・メモリ４２０、４３０は、特定のシステム構成のパターンを格納する。ソフトウェア・ドライバ（図示されていない）は、所与のルールセットに関して分類エンジン４００のテンプレート４１０にパターン・メモリを設定する。分類エンジン４００には、パターンの継目のない更新を有効化するためにパターンＡ４２０及びパターンＢ４３０である２つのパターン・メモリが保持される。ＡまたはＢパターン４２０、４３０の一方は、任意の所定時間にマッチング処理ユニット４４０への供給を行えるように使用されることが可能である。これは、他方のパターン４２０、４３０がプロセッサ・インタフェースを介して更新されることを可能にする。更新が行われると、プロセッサは分類エンジン４００に集合の切換を命令することができる。
【００５５】
オペレーションにおいて、プリプロセッサ４５０は分類レコードをマッチング処理ユニット４４０へ送る。分類レコードは、典型的には、例えばアドレス等のフィールドを含むパケット・ヘッダ情報を含む。テンプレート４１０から命令を受信すると、マッチング処理ユニット４４０は分類レコード内の指定されたフィールドをＡパターン４２０と比較し、分類結果をポストプロセッサ４６０へ送る。後処理コンポーネント４６０は、所定のパターン４２０、４３０の所定のヘッダに関してマッチング処理ユニット４４０が決定した最優先ルールを符号化する。要約すれば、パケットはプリプロセッサ４５０によって受信される。次にパケットは分類エンジン４００内のパターンとマッチングされ、マッチしたパケットは次にポストプロセッサによりマッチしたパターンに関連づけられるルールに従って処理される。
【００５６】
１．分類レコード
分類レコードは、着信するパケットのパケット・ヘッダからプリプロセッサ４５０によって生成される。１２８ビットを有する例示的な分類レコード５００を、図５に示す。分類レコード５００内の２つのフィールドは、ハードウェア実装にとって重要である。Ｒビット５１０はＡ／Ｂセレクタ・ビットであり、分類レコード５００へ印加される命令セットを制御するために使用される。図５の分類レコード５００は、ＴＣＰ／ＩＰ分類用に構成される。このフォーマットは、ＩＰ及びＴＣＰパケット・ヘッダから抽出されるフィールドに渡る７の分類を規定する。図６はフォーマットされていない１２８ビット分類レコードの一例であり、ユーザの指定に従ってフォーマットされることが可能である。図６の陰のフィールドは、アプリケーション・データが存在してもよい分類レコード内の場所を示す。図６は、図５の空の分類レコード５００を示している。
【００５７】
分類レコードがフォーマットされると、様々なフィールド上でサポートされるオペレーションが決定される。図７は、図５に描いた分類レコード５００のルール・テンプレートの一例を概説するものである。図７は、規格ＴＣＰ／ＩＰヘッダ及び分類レコード５００によって使用されるテンプレートが如何にして生成され得るかを示す１つの特定的な実施形態である。フィールド７１０は、分類レコード内の７フィールドのうちのどれがオペランドであるかを選択する。フィールド７１０は、ＴＣＰ／ＩＰパケット・ヘッダ内に発見される共通フィールドをリストする。例えば、ＳＡはソース・アドレスを表す。ＤＡは、宛先アドレスの頭字語である。プロトコルは、そのパケット自体の内部でどのプロトコルが使用されるかを表す（例えばＴＣＰ）。ＴＯＳは、サービスのタイプの略語である。ＳＰは「ソース・ポート」を、ＤＰは「宛先ポート」を表す。ＴＣＰＣｔｒｌは通信制御プロトコルの制御フィールドである。
【００５８】
演算７２０は、オペランド上で実行されるべき演算を指す。一般的な演算には、同一性、非同一性、大きい、小さい、範囲及びマスクされる同一性のチェックが含まれる可能性がある。同一性のチェックは、フィールド内のビットがパターンと同一であるかどうかを調べる。非同一性のチェックは、フィールドがパターンにマッチしないかどうかを調べる。大きい、のチェックは、フィールドは指定された数（即ちパターン）より大きいかどうかを調べる。小さい、のチェックは、フィールドがパターンより小さいかどうかを調べる。マスクされる同一性のチェックは、予備的なステップであることを除けば同一性テストと同様である。マスクされる同一性のチェックは、まず第１のパターンでビット単位のブールＡＮＤ演算を実行し、その後第２のパターンで同一性を調べる。演算範囲のチェックは、大きい、及び小さい、の演算の組合わせである。これは、フィールドが２つのパターンの間にあるかどうかを調べる。
【００５９】
図７を参照すると、「ヘッダ・ビットの＃」７３０は分類ヘッダ内の７のフィールドのサイズを指す。例えば、ＴＣＰ／ＩＰｖ４は３２ビットのソース及び宛先アドレスを使用する。ＩＰアドレスは通常、小数点で分離された４バイト（各々が８ビットを有する）で略して表される。各バイトは、１２８．１９２．０．１のように０から２５５までの数字を表す。「パターン・ビットの＃」７４０は、演算７２０を実行するために必要とされるパターン・ビット数を指す。
【００６０】
図７において「注記」７５０と記されている欄は、欄７４０の個々のパターン・ビットが個々の比較演算７２０においてどのように適用されるかをユーザに明らかにするために使用される。例えば、あるルールが分類レコード内のＳＡフィールドに対して「マスクされる同一性」を実行すれば、６４ビット（７４０から）、即ちマスクに３２ビット及び同一性に３２ビット、が必要とされる。注記７５０欄内の対応する行７７２は、これを説明している。例えば、分類レコード内の３ビット長さ（「１０１」）である仮想フィールドに対してマスクされる同一性が実行されれば、比較演算を完了するために６ビットが必要である。この例では、フィールドは「１０１」であり、第１のパターンは「１１０」でありかつ第１のフィールドは「１００」であり、第２のパターンは「１１０」である。マスクされる同一性の機能性ごとに、Ｆはビット単位のブール演算においてｍでＡＮＤされる。結果は、「１００」（「１０１」ＡＮＤ「１００」）である。この結果は、「１１０」であるｎにマッチしない（等しくない）。
【００６１】
行７５８において、対応する注記７７８はユーザに、ソース・ポート・フィールドに演算「範囲」を実行するためには３２ビットが必要であることを知らせる。演算「範囲」は、あるオペランド（例えばＳＡフィールド７５８）が２つの数字の間にあるかどうかを調べる。範囲は、（例えば）ソース・ポート・フィールド７５８に対して実行されるべき上限（長さ１６ビット）及び下限（長さ１６ビット）を必要とする。
【００６２】
２．分類結果
分類エンジン４００がマッチの結果に到達すると、分類結果と呼ばれるこの結果は分類レコードへ書き込まれる。図８に示すように、分類エンジンは分類レコードの下位の１５ビットを分類結果８１０で上書きする。図８を参照すると、陰のフィールド８２０は分類エンジン４００へ送られる分類レコードに関連して変更されない。
【００６３】
図９は、分類結果９００のフォーマットを示す。分類結果９００は、３つのフィールド、即ちＭ９１０、セット９２０及びフィルタ９３０を含む。Ｍフィールド９１０はシングルビット・フィールドであり、マッチが発生しているか（セット時）否か（クリア時）を示す。
【００６４】
セット・フィールド９２０は、５ビット長さである。セット・フィールド９２０は、どのフィルタ・セットがマッチしているかを示す。フィルタ・セットは、（この例示的な説明では）５１２ルール以下のグループである。フィルタ・セットは、ルール・セパレータと呼ばれるテンプレート内の特殊命令によって分離される。
【００６５】
パケット分類子のこの実施形態は、ルールのデータベースを保持する。ルールは、パケットがパケット分類子に到達するとルールが予め決められた順序で適用されるように、ルール・データベース内のネットワーク・マネージャ（またはプロトコル）によって優先順位を付けられる。従って、パケット・ヘッダが２つ以上のルールにマッチすれば、最も高い優先順位を有するルールが適用される。
【００６６】
フィルタ・フィールド９３０は、この実施形態では９ビット長さである。フィルタ・フィールド９３０は、優先順位の調停結果を報告するために使用されることが可能である。例えば、分類エンジンが着信するパケットに関連づけられる関連識別子を１つまたは複数のルールにマッチさせると、優先順位の問題が発生する。（ネットワーク・マネージャによって設定される構成ごとの）分類エンジンは、着信するパケットにどのフィルタが適用されるべきかを決定する。フィルタ・フィールド９３０は優先順位の決定結果であり、マッチした（もしあれば）最も高い優先順位のフィルタを指示する。
【００６７】
３．命令セット
図１０を参照すると、この命令セットはテンプレートとＲビットで指定されるパターン・セットとの組合わせである。本実施形態では、分類エンジンの命令サイズは５２２ビットである。命令メモリは、分類プログラムの継目のない更新を可能にするためにミラーされる。言い替えれば、第２の命令セット及びパターン・セットは分類エンジン内に重複して保持される。これは、ユーザが両セットの何れかを使用不能にして、サービスを中断することなく変更を実装することを可能にする。
【００６８】
図１０は、命令のフォーマットを示す。命令１０００は、３つのフィールドを有する。命令１０００は、Ｏｐｃｏｄｅフィールド１０１０、ＨｅａｄｅｒＢｉｔＳｅｌフィールド１０２０及びパターン・フィールド１０３０を含む。Ｏｐｃｏｄｅフィールド１０１０は、実行されるべき演算を示す３ビットのｏｐコードを指す。
【００６９】
一般的な演算子の幾つかは、「フィールド・セパレータ」、「小さいか等しい」、「大きいか等しい」、「等しい」、「ルール・セパレータ」、「優先順位より下位か等しい」、「優先順位より上位か等しい」及び「優先順位に等しい」を含む。
【００７０】
ヘッダ・ビット選択（ＨｅａｄｅｒＢｉｔＳｅｌ）フィールド１０２０は、分類レコードから命令のオペランドの１つのソースとして１ビットを選択する。５１２のパターン・ビットの各々は第２のオペランドのソースとして供給され、１ビットは同時に比較される５１２個のフィルタの各々に対応する。
【００７１】
４．合成演算子
演算子は、この基本セットからの他の演算子を合成することが可能であり、特定のアプリケーションにとってこれが有益である可能性がある。例えば、ブール「ＯＲ」命令は命令：大きいか等しい（ＧＥ）によってＯＲされるべきビットを選択するヘッダ・ビット選択（ＨｅａｄｅｒＢｉｔＳｅｌ）と合成されることが可能である。但し、連続するＯＲ命令のパターンは、必ず全て１であるパターンを有するシーケンス内の最後のＯＲ命令を除いて全てゼロである。
【００７２】
本実施形態の分類エンジンは、幾つかの理由で、パケットの分類に使用されるターナリ・コンテンツ・アドレッサブル・メモリ（ＴＣＡＭ）より本質的に優れていると言える。特に、ブール論理「ＯＲ」演算子を表記する能力は、ＴＣＡＭでは複数のＴＣＡＭエントリを使用せずに行うことができない。また、あらゆるビットに１つを適用しなければならないこととは対照的に、フィールドにマスクを適用する能力はパターン・メモリのより効率的な使用をもたらす。さらに本実施形態は、範囲をサポートする優れた能力を有する。例えば、ルールセットにおいて一般的なポート式は「１０２３より大きい」。このポート式を組み込むルールをＴＣＡＭ上に実装すれば、６つのＴＣＡＭエントリが必要になる。
【００７３】
５．分類プログラムの構成（テンプレート）
図１２は、分類プログラムの一般的な構成を示す。テンプレート１２１０は、上記テンプレートのルール・セパレータ命令に先行しかつこれを含む命令のｏｐコード及びヘッダ・ビット選択（ＨｅａｄｅｒＢｉｔＳｅｌ）フィールドのシーケンスによって定義される。ルール・セパレータ命令は、フィルタ・セットの境界を定義する。同じテンプレートで表現され得る全てのフィルタはこのフィルタ・セットに分類され、そのパターンに関連してリファインされる。テンプレートは、１つが５１２個までの異なるフィルタに適用される。１つのテンプレートは、３８４個の命令より成る大型のものであったり、３２個の命令より成る小型のものであったりする。
【００７４】
６．フィールドの圧縮
経路転送を宛先プレフィックスまたはＤＭＡＣアドレスに関連づけるタスクは特殊な（限定された）形式の分類であり、これは典型的には、分類エンジンによってサポートされる高度Ｎタプル分類の部分集合である。本発明の別の実施形態では、先に項目Ａで説明したようなフィールドの圧縮が実装される。項目Ａで説明した原理は、パケット分類子が分類されるべきフィールドのフィールド圧縮を利用することを可能にし、かつシステムによってサポートされるルールの潜在的な数を増大させるメカニズムを提供する。項目Ａで説明した技術は、網羅性のためのフィールド圧縮に適用されるものとして概説される。
【００７５】
プロセッサは、（例えば、ある実施形態における最長プレフィックスマッチにおいて）そのルックアップ機能を実行するにつれて、分類レコードを関連識別子でポピュレートする。ＩＰｖ４アドレスの場合、分類レコードにおける（即ち関連識別子の）必要な表現は６４ビットから２０ビットにまで下がり、４４ビットという大幅な利得になる。ＭＡＣアドレスの場合、分類レコードにおける必要な表現は９６ビットから２０ビットにまで下がり、７６ビットというさらに大幅な利得になる。またＩＰｖ６アドレスの場合、必要な表現は２５６ビットから２０ビットまで下がる。この置換は、フィールドの圧縮と呼ばれる。
【００７６】
図１３は、ソース及び宛先プレフィックス・アドレスのフィールドが圧縮された７のＩＰｖ４分類レコードの一例を示す。図１３の陰の範囲１３２０を参照すると、５０ビットがこの構成では不確定のままである。これらの５０ビットは、分類のための追加フィールドを供給するために使用されることが可能である。
【００７７】
図１４は、Ｌ２ブリッジ・フレーム上のＬ３−４分類を規定する１１タプル・イーサネット（登録商標）・フレーム分類レコードの一例を示す。Ｔ（タイプ）ビットを追加することにより、イーサネット（登録商標）の分類レコードは、他者との区別化を行うこのタイプ・ビットを有するＩＰｖ４レコードと同一であると仮定されることが可能である。この技術は、ルールのコンパイルを単純化する際に有益である。
【００７８】
７．最適化
テンプレートに対しては、テンプレート・サイズのデータ依存縮小をもたらすために幾つかの最適化を実行することができる。同じヘッダ・ビットのＬＥ（小さいか等しい）命令のパターンとＧＥ（大きいか等しい）命令のそれとが等価であれば、このペアは同じパターンを有するＥＱ（等しい）命令によって置換されてもよい。ＬＥ命令に関連づけられるパターンが全て１であれば、このＬＥ命令は除外されてもよい。ＧＥ命令に関連づけられるパターンが全てゼロであれば、このＧＥ命令は除外されてもよい。全てゼロのパターン・ビットを有するＭＡＳＫ命令が存在すれば、ＭＡＳＫ及びその対応するＤＡＴＡ命令は除外されることが可能である。
【００７９】
これらの最適化は、分類プログラム・テンプレートの供給されるパターンに関する単純な変換を有効化する。テンプレートのサイズが縮小されるにつれて、追加のテンプレート命令は有効化される。これは次に、さらに多くのフィルタが指定されることを有効化する。但し、ルールの任意の順序づけは、概してこのような最適化を有効化しない。従ってこれは、上述の最適化のうちの１つが適応され得る可能性を増大させる何らかの経験則の適用を必要とする可能性がある。
【００８０】
８．分類エンジンのアーキテクチャ
下記の実装は、本発明の一実施形態に使用されることが可能である。但し、本発明のアーキテクチャの範囲はこの実施形態に限定されない。図１５を参照すると、ブロック図はパケット分類エンジン１６００の主要なコンポーネントを示している。コンポーネントには、コントローラ１６１０と、命令メモリ１６２０と、１つまたは複数のパターン・メモリ１６３０と、命令デコーダ１６４０と、ヘッダ・アレイ１６５０と、プロセッサ・アレイ１６６０と、結果メモリ１６７０と、優先順位エンコーダ１６８０とが含まれる。
【００８１】
プリプロセッサ（図示されていない）は着信するパケットの分類レコードをフォーマットし、上記分類レコードの幾つかのフィールドをヘッダ・アレイ１６５０へ書き込む。ヘッダ・アレイ１６５０へ書き込まれるフィールドの数は、パケット分類子のパケット処理速度を決定する。例えば、毎秒２０００万パケットのパケット処理速度は、５０ナノ秒毎に少なくとも１つの分類レコードが処理されなければならないことを要求する。３２個の分類レコードを所与とすると、プロセッサ・アレイは全てのレコードの並行処理に１６００ナノ秒を費やす可能性がある。４ナノ秒のクロック・サイクル時間を所与とすると、命令は各分類レコードに４００個まで適用されてもよい。ヘッダ・アレイ内に維持されるレコードの数が増えるにつれて、各レコードに適用されてもよい命令の数も増える。
【００８２】
命令メモリ１６２０及びパターン・メモリ１６３０は、共通のコントローラ１６１０（例えばカウンタ）によってアドレス指定される。命令は、ヘッダ・ビット数及びｏｐコードより成る。ヘッダ・ビットは、ヘッダ・アレイ１６５０により適切な数のビットをプロセッサ・アレイ１６６０へ提示するために使用される。ｏｐコードは、ヘッダ・アレイ１６５０からのカレント・ヘッダ・データ・ビットと併せたデータ・メモリからのカレント・ルール・データ・ビットに関連して、各処理エレメントがどのアクションをとるかを決定する。以下、図１５に示すブロック図の主要なコンポーネントについて説明する。
【００８３】
ａ．コントローラ
コントローラ１６１０は、データ・パス・エレメントのタイミングを供給する。これは、命令の合計数を法として計数する命令ポインタを保持する。このポインタは、命令メモリ１６２０及びパターン・メモリ１６３０をアドレス指定するために使用される。またコントローラは、ヘッダのコンテキストが命令シーケンスの始まりで適宜切換されるようにヘッダ・アレイ１６５０のタイミングも管理する。
【００８４】
ｂ．命令及びパターン・メモリ
命令メモリ１６２０及びパターン・メモリ１６３０は、この実施形態ではスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）から成る。ある実施形態では、コントローラ１６１０によって共通のアドレスが供給される。アドレス指定されたロケーションにおけるデータは読み取られ、命令デコーダ１６４０及びヘッダ・アレイ１６５０へ送られる。本実施形態では、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）等の他のＲＡＭデバイスに置換されてもよい。
【００８５】
ｃ．命令デコーダ
命令デコーダ１６４０は、プロセッサ・アレイ１６６０向けに適切な制御信号が生成されるように、命令メモリ１６２０から受信される命令の復号を担当する。関連の制御信号は、後述するプロセッサ・アレイ構成を示す図１７に示されている。
【００８６】
ｄ．ヘッダ・アレイ
図１６は、ヘッダ・アレイ１７００の構成を示す。分類レコードは、ヘッダ・アレイ１６５０へ単一サイクルで書き込まれる。各ヘッダから、単一のヘッダ・ビットがカレント命令の制御下で同時に読み取られる。このようにして、ヘッダ・アレイ１６５０は転置メモリとして行動する。ヘッダ・アレイのコンテンツは、分類プログラムにおいてヘッダのカレント集合に適用する命令の部分集合を決定するために使用されることが可能である。このような選択は決定されている、またはプログラマブルであることが可能であり、これは、分類プログラムの継目のない更新を有効化しかつ分類プログラムのサイズを効果的に増やすことができる。
【００８７】
ｅ．プロセッサ・アレイ
図１７を参照すると、プロセッサ・アレイ１６６０の構成１８００は処理するヘッダ数と同数の行と並行処理されるルール数と同数の列とを有する。これは、要件に依存して何千もの処理エレメント１８５０（ＰＥ）より成る可能性がある。単一のサイクルにおいて、各処理エレメント１８５０はパターン・メモリから１ビット、（命令による指図通りに）ヘッダ・アレイから適切な１ビット及び上記ルール及びヘッダ・ビット間で求められるマッチを示すコマンドを受信する。
【００８８】
処理エレメント１８５０は、図１８における状態図に描かれているような４状態有限状態機械（ＦＳＭ）である。図１８の状態フローには示されていないが、有限状態機械１８５０（図１７）は命令デコーダ１６４０によって指令される通りに１８６０で中断されることが可能である。この中断は、クロック・ゲーティングによって、または次の状態論理においてアクティブに達成されることが可能であり、前者は最終的により少ない全体論理に繋がる。
【００８９】
新たなルール信号１８７０がアサートされると、列全体のマッチ状態１９１０はシフト・レジスタ（図示されていない）へロードされ、有限状態機械１８５０はマッチ状態へリセットされる。後続のサイクルでは、シフト・レジスタはこれらの結果を、マッチを配信する優先順位エンコーダ１６８０へシフトする。これは、シフト・レジスタが完全にフラッシュされるまであらゆるサイクル上で各ヘッダ（行）のベクトル１８１０をシフトする。
【００９０】
ｆ．優先順位エンコーダ
優先順位エンコーダは、マッチ・ベクトルに設定される最も高い優先順位のエレメントを識別し、結果を結果メモリへ書き込む。
【００９１】
先に詳述したパケット分類子は、様々な実装に使用されることが可能である。ある実装において、これは、デバイスの１つのインスタンスがデバイスの別のインスタンスへの供給に使用されるようにカスケードされることが可能である。
【００９２】
大きい／小さい、前／後、右／左、頂部／底部、上／下及び水平／垂直は説明の便宜を図るためのものであって、本発明を限定するもの、またはそのコンポーネントを任意の１つの関係性、位置または空間的位置決めに限定するものではない。添付の図面におけるコンポーネントの全ての大きさは、本発明の範囲を逸脱することなく、本発明の実施形態の潜在的設計及び意図された使用に伴って変化してもよい。
【００９３】
本発明をその幾つかの実施形態を参照して説明したが、当業者には、本発明の精神及び範囲を逸脱することなく行われてもよい様々な変更が理解されるであろう。従って、本発明は図面に指示されかつ明細書で説明されたものに限定されず、専ら添付の請求の範囲に指示されている通りのものである。
【図面の簡単な説明】
【００９４】
【図１ａ】本発明の一実施形態の機能を示すブロック図である。
【図１ｂ】図１ａの実施形態に関連して使用されることが可能なデータベースの生成を示すブロック図である。
【図２ａ】本発明の一実施形態に従って構成される木のブロック図である。
【図２ｂ】本発明の一実施形態に従って構成される第２の木のブロック図である。
【図３】図２の木の終端ノードに対応するパターン範囲を示す表である。
【図４】本発明の一実施形態による分類エンジンを描いたブロック図である。
【図５】ＴＣＰ／ＩＰ分類レコードの一例を描いたブロック図である。
【図６】フォーマットされていない１２８ビット分類レコードを示すブロック図である。
【図７】図５の分類レコードから導出された表である。
【図８】分類レコードへの結果の書き直しを示すブロック図である。
【図９】分類レコードのフォーマットを示すブロック図である。
【図１０】命令フォーマットを描いたブロック図である。
【図１１】優先順位マシン状態を表す追加フィールドを伴う分類結果のブロック図である。
【図１２】例示的な分類プログラム構成を示す表である。
【図１３】フィールド圧縮を有する分類レコードのブロック図である。
【図１４】フィールド圧縮を有する分類レコードの別の実施形態のブロック図である。
【図１５】本発明による分類エンジンの一実施形態を示すフローチャートである。
【図１６】分類エンジンの図１５に描かれたヘッダ・アレイ構成のブロック図である。
【図１７】分類エンジンの図１５に示されたプロセッサ・アレイ構成のブロック図である。
【図１８】図１７に示された最終状態マシンの最終状態図のフローチャートである。
【図１ａ】
2007507915.tif 000003
【図１ｂ】
2007507915.tif 000004
【図２ａ】
2007507915.tif 000005
【図２ｂ】
2007507915.tif 000006
【図３】
2007507915.tif 000007
【図４】
2007507915.tif 000008
【図５】
2007507915.tif 000009
【図６】
2007507915.tif 000010
【図７】
2007507915.tif 000011
【図８】
2007507915.tif 000012
【図９】
2007507915.tif 000013
【図１０】
2007507915.tif 000014
【図１１】
2007507915.tif 000015
【図１２】
2007507915.tif 000016
【図１３】
2007507915.tif 000017
【図１４】
2007507915.tif 000018
【図１５】
2007507915.tif 000019
【図１６】
2007507915.tif 000020
【図１７】
2007507915.tif 000021
【図１８】
2007507915.tif 000022