JP2001223749A

JP2001223749A - パケット分類エンジン

Info

Publication number: JP2001223749A
Application number: JP2000378432A
Authority: JP
Inventors: Andrew T Hebb; テー．ヘブアンドリュー; Sanjay G Cherian; ジー．チェリアンサンジェイ
Original assignee: Ascend Communications Inc
Current assignee: Ascend Communications Inc
Priority date: 1999-12-13
Filing date: 2000-12-13
Publication date: 2001-08-17
Anticipated expiration: 2020-12-13
Also published as: CA2326939C; EP1128609A3; CA2326939A1; DE60026676D1; EP1128609A2; US6587463B1; DE60026676T2; EP1128609B1; JP3734704B2

Abstract

(57)【要約】（修正有）【課題】パケットフィルタリングを行うために高速の
パケット分類を提供する、ネットワーク装置内のパケッ
ト処理ロジックを提供する。【解決手段】パケット分類装置は、規則メモリと判定
基準メモリと制御ロジックとを備える。制御ロジック
が、パケット分類要求に応答し、規則メモリからの規則
メモリエントリを検索し、その規則メモリエントリ内の
判定基準メモリポインタによって特定される判定基準メ
モリエントリを検索し、さらにその判定基準メモリエン
トリ内の値と、その分類要求に含まれる対応する値にお
いて、規則メモリエントリ内の演算子によって規定され
る演算を実行する。この手順は、終了条件が見出される
まで、一連の規則メモリエントリに対して繰り返され、
パケット分類結果が、その分類演算子の結果を反映し
て、パケット分類結果が生成される。この結果は、分類
結果に基づいて適切な動作を行うために、パケットプロ
セッサに供給される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ通信ネット
ワークの分野に関する。

【０００２】

【従来の技術】データ通信ネットワークでは、交換器の
ようなネットワーク装置を用いて、パケットをネットワ
ーク内にルーティングする。各交換器は典型的には多数
の回線インタフェースを有し、各インタフェースは、異
なるネットワークセグメントに接続される。所与の回線
インタフェースにおいてパケットが受信されるとき、転
送ロジックは、そのパケットがどの回線インタフェース
から送信されるべきかを判定し、そのパケットは適当な
出力回線インタフェースに移送されて、ネットワーク内
の行先に向けて送出される。

【０００３】交換器のようなネットワーク装置において
は、パケットフィルタリングを実行することが知られて
いる。パケットフィルタリングを用いて、トラフィック
モニタ及びセキュリティ目的のような、種々のネットワ
ーク管理を行うことができる。フィルタリング判定基準
はネットワーク管理者によって確立され、フィルタリン
グ動作を実行する交換器或いは他の装置に提供される。
交換器によって受信されたパケットは、その特性が任意
の確立されたフィルタについての判定基準に適合するか
否かを判定するために検査される。１つ或いは複数のフ
ィルタのための判定基準を満足するパケットの場合、そ
のフィルタに関連する所定の動作が実行される。例え
ば、ある状況下では、所与のネットワークノードから発
信するパケットは、ネットワーク内に転送されずに破棄
されることが望ましい場合もある。パケットソースアド
レスが、そのパケットが破棄されるべきであるノードの
アドレスである特定の値に正確に一致するという判定基
準を有するフィルタを定義することができる。そのフィ
ルタに関連する動作は、パケットを破棄することであ
る。ソースアドレスがこの判定基準を満足するパケット
を受信するとき、そのパケットは、通常通りに転送され
ずに破棄される。

【０００４】パケットをフィルタリングするために用い
る場合がある、多数の異なる種類の判定基準が存在す
る。これらの判定基準は、厳密な一致と、範囲検査、す
なわちパケット内の値がある範囲内の値に入るか否かの
検査とを含む。ソースアドレス、行先アドレス、ポート
識別子、サービスタイプ等のような多数のパケットパラ
メータを判定基準として用いることができる。実用的に
するためには、パケットフィルタリングプロセスによっ
て、そのフィルタが、これらの判定基準と他の判定基準
からなる異なる組み合わせを用いて、柔軟に定義されな
ければならない。

【０００５】パケットフィルタリングに固有の複雑さの
ため、この処理は従来から、パケットフィルタリングを
サポートする交換器或いは他のネットワーク装置内のソ
フトウエアにおいて、広範に或いは排他的に実行されて
きた。しかしながら、ソフトウエア系のフィルタリング
は、高いパケット転送性能が要求されるときに欠点を露
呈する。例えば、従来のシステムは回線速度で信頼性の
ある（robust）パケットフィルタリングを実行できなか
ったため、ネットワーク管理者は、ネットワーク応答性
とネットワークセキュリティとの間でトレードオフを余
儀なくされており、問題となっていた。

【０００６】

【発明が解決しようとする課題】本発明によれば、パケ
ットフィルタリングを行うために高速のパケット分類を
提供する、ネットワーク装置内のパケット処理ロジック
が開示される。その分類装置のアーキテクチャは、複雑
なフィルタ判定基準の定義において実質的な柔軟性を提
供する。十分に高い速度でロバストフィルタリングを実
行し、パケット転送性能が低下するのを避けることがで
きる。

【０００７】

【課題を解決するための手段】パケット分類装置は、規
則メモリと判定基準メモリとを備える。１つのタイプの
規則メモリエントリは、判定基準メモリエントリに対す
る演算子及びポインタを含む。演算子は、ＥＱＵＡＬ
（厳密な一致）或いはＬＥＳＳＴＨＡＮのような、実
行されることになる比較演算を定義する。判定基準メモ
リエントリは、比較の一方の辺の被比較数として用いら
れる１つ或いは複数の値を含み、受信したパケットから
の対応する値は、比較の他の辺に現れる。例えば、判定
基準メモリからの１つの被比較数は、ソースアドレスを
表す。この値は、受信したパケットのソースアドレスフ
ィールド内に現れる値と比較される。

【０００８】制御ロジックはパケット分類要求に応答し
て、規則メモリからの規則メモリエントリを検索し、規
則メモリエントリにおいて判定基準メモリポインタによ
って識別された判定基準メモリエントリを検索し、判定
基準メモリエントリの値及び分類要求に含まれる対応す
る値において、規則メモリエントリの演算子によって規
定される演算を実行する。この手順は、一定の終了条件
が満たされるまで、一連の規則メモリエントリに対して
繰返し行われ、その結果、その分類演算の結果を反映し
て、パケット分類結果が生成される。この結果はパケッ
トプロセッサに提供され、その分類結果に基づいて適当
な動作が行われる。

【０００９】

【発明の実施の形態】本発明の他の態様、特徴及び利点
は、以下の詳細な説明において開示される。

【００１０】図１には、ネットワーク交換器１０が、各
ネットワークセグメント１４に接続される多数の回線イ
ンタフェース１２を備えるものとして示される。回線イ
ンタフェース１２は、パケット転送のための回線インタ
フェース１２の間の接続部を提供するために用いられる
交換器構造部１６に接続される。交換器構造部１６の動
的な構成を含む、交換器１０の全動作は、交換器制御部
１８によって制御される。一般に、種々のネットワーク
セグメント１４は異なるタイプからなる場合がある。例
えば、ネットワークセグメント１４のうちのあるもの
は、ＯＣ−３／ＳＴＭ−１及びＯＣ−１２／ＳＴＭ−４
のような種々の標準的なシグナリング速度のうちの任意
の速度で動作する光学的なリンクであり得る。ネットワ
ークセグメント１４の他のものは、例えば同軸ケーブル
を用いて、種々のフォーマットの信号を搬送する非光学
的なリンクであってもよい。

【００１１】言うまでもなく、各回線インタフェース１
２は、接続される特定のタイプのネットワークセグメン
ト１４で動作するために設計される。各回線インタフェ
ース１２の主なタスクは、取り付けられたネットワーク
セグメント１４から受信したパケット或いはフレーム
を、他の回線インタフェース１２に取り付けられたネッ
トワークセグメント１４上で転送するために、交換器構
造部１６を介して別の回線インタフェース１２に転送す
ることと、取り付けられたネットワークセグメント１４
上で転送するために、交換器構造部１６を介して他の回
線インタフェース１２からパケットを受信することであ
る。

【００１２】図２は、１つのタイプの回線インタフェー
ス１２の構造を示す。このインタフェースは、４つの個
別の光インタフェースポートを含み、各ポートは、物理
的な入力／出力及びフレーム処理回路２０と、転送エン
ジン２２とを備える。転送エンジン２２は、交換器構造
部インタフェースロジック２４に接続され、インタフェ
ースロジック２４は図１の交換器構造部１６とのインタ
フェースを構成する。また転送エンジンは、回線インタ
フェースＩ／Ｏプロセッサ（ＩＯＰ）２６とのインタフ
ェースも構成する。タイミング制御ロジック２８及びＤ
Ｃパワー回路３０も備えられる。

【００１３】各転送エンジン２２は、接続される物理Ｉ
／Ｏブロック２０と交換器構造部インタフェース２４と
の間の双方向データパスを提供する。受信されたパケッ
トは、図１の交換器構造部１６を介して別の回線インタ
フェース１２に転送するために、多数の固定サイズのＡ
ＴＭ型のセルにセグメント化される。交換器構造部イン
タフェース２４を介して交換器構造部１６から受信され
たセルは、接続される物理Ｉ／Ｏブロック２０への転送
を行うために、パケットに再構成される。

【００１４】ＩＯＰ２６は、バックグラウンド機能、す
なわちパケット毎には実行されない、パケットの転送を
サポートする機能を実行する汎用プロセッサである。Ｉ
ＯＰ２６によって実行される１つの機能は、図１の交換
器制御部１８からパケット転送情報及びパケットフィル
タリング情報を受信し、転送エンジン２２にその情報を
分配することである。この処理は以下に記載される。

【００１５】図３は、転送エンジン２２のブロック図を
示す。着信セグメント化−再構成（ＳＡＲ）論理ブロッ
ク４０は、図２の物理Ｉ／Ｏブロック２０から交換器構
造部１６へのデータパスを提供し、発信ＳＡＲ論理ブロ
ック４２は、交換器構造部１６から各物理Ｉ／Ｏブロッ
ク２０へのデータパスを提供する。各ＳＡＲ４０、４２
は、セグメント化機能及び再構成機能を実行する際に用
いられる各制御メモリ４４、４６と、各パケットメモリ
４８、５０に接続される。

【００１６】ＳＡＲ装置４０、４２はともに、６４ビッ
トＰＣＩバス５４を介して、パケットヘッダ分配器（Ｐ
ＨＤ）特定用途向け集積回路（ＡＳＩＣ）５２に接続さ
れる。以下に詳細に記載するように、ＰＨＤＡＳＩＣ
５２は、ＰＣＩバス５４と個別の６４ビットバス５６と
の間のＦＩＦＯキューインタフェースを提供する。バス
５６は、ＰＨＤＡＳＩＣ５２を転送プロセッサ（Ｆ
Ｐ）５８及び転送プロセッサメモリ６０と接続する。ま
たＰＨＤＡＳＩＣ５２は、個別のバス６２によって図
２のＩＯＰ２６にも接続される。

【００１７】図４は、図３のＰＨＤ５２の構造を示す。
１組の受信キュー、すなわちＲＸキュー６４は、ＦＰ５
８に向かうパケットヘッダ及び他の情報を一時的にバッ
ファリングするために用いられる。図のように、ＲＸキ
ュー６４は４つあり、２つが高優先度のトラフィック用
であり、残りの２つは低優先度のトラフィック用であ
る。高優先度トラフィックの一例は、約束された速度
（committed rate）のような、高品質のサービス（ＱＯ
Ｓ）保証（High Quality of Service guarantee）を有
するトラフィックである。低優先度のトラフィックは、
最善努力（best-efforts）のような、低いＱＯＳ保証し
かもたないか、或いは全く保証がないトラフィックであ
る。各優先度レベルの場合に、着信ＳＡＲ４０から生じ
るトラフィック用の１つのキュー（「０」を付される）
と、発信ＳＡＲ４２から生じるトラフィック用の別のキ
ュー（「１」を付される）とが存在する。１組の送信キ
ュー、すなわちＴＸキュー６６は、ＦＰ５８からＳＡＲ
４０、４２に向かうパケットヘッダ及び他の情報を一時
的にバッファリングするために用いられる。ルーティン
グ及び分類エンジン６８は、ＦＰ５８に代わって、経路
探索及び種々のパケットフィルタリング検査を実行す
る。パケットフィルタリング動作は以下に記載される。
ルーティング及び分類エンジン６８は、信号線６９を介
してキュー６４、６６から状態情報を受信し、以下のよ
うにして、ＦＰ５８においてこの情報を利用できるよう
にする。

【００１８】転送エンジン２２の全動作が、図３及び図
４を参照して記載されるであろう。パケットは、図２の
関連する物理層回路２０から着信ＳＡＲ４０によって受
信され、パケットメモリ４８に記憶される。着信ＳＡＲ
４０は、パケットヘッダを、ＰＨＤ５２内の適当なＲＸ
キュー６４の１つに転送する。ＦＰ５８はＰＨＤ５２を
ポーリングしてキュー状態を判定するとともに、適宜Ｒ
Ｘキュー６４からのパケットヘッダを検索する。ヘッダ
処理の一部として、ＦＰ５８は、ルーティング及び分類
要求において、各ヘッダからの一定の情報要素を、ルー
ティング及び分類エンジン６８に送出する。ルーティン
グ及び分類エンジン６８は、その要求内のヘッダ要素に
対する経路探索及び種々のパケットフィルタリング検査
を実行し、これらの検査の結果を、結果キュー（以下に
記載する）に入れる。ＦＰ５８は、結果キューから経路
探索及び分類結果を取得し、これらの結果を用いて、そ
のパケットのための新しいヘッダを作成する。その新し
いヘッダは、セグメント化した後にパケットが転送され
ることになる内部回路を特定する情報とともに、ＴＸキ
ュー６６の１つを介してＰＨＤ５２に返送される。着信
ＳＡＲ４０は新しいヘッダを検索し、受信したパケット
のペイロード部分とともにそのヘッダをパケットメモリ
４８に入れ、新しいパケットをセグメント化し、その結
果として生成されたセルを、ＦＰ５８によって特定され
た内部回路上にある図１の交換器構造部１６に転送す
る。

【００１９】発信方向では、発信ＳＡＲ４２が図１の交
換器構造部１６からパケットを受信し、これらのパケッ
トを再構成してパケットメモリ５０に入れる。パケット
ヘッダはＰＨＤ５２に送出され、ＦＰ５８によってＰＨ
Ｄ５２から検索される。大部分のパケットの場合、経路
探索及びフィルタリング検査は、着信処理中に既に行わ
れているため、これらの動作は繰返し行われない。しか
しながらプロトコルによっては、着信及び発信の両方の
場合に探索及びフィルタリングを必要とするため、これ
らの動作は、ルーティング及び分類エンジン６８ととも
に、ＦＰ５８によって任意選択的に実行される。妥当な
場合には、ＦＰ５８は、セグメント化された発信パケッ
トが受信される内部回路の同一性に一部基づいて、その
パケットのための新しいヘッダを作成する。この新しい
ヘッダは、送信回路情報とともに、ＰＨＤ５２に書き込
まれる。ＰＨＤ５２は、新しいヘッダを、発信ＳＡＲ４
２に転送する。発信ＳＡＲ４２は、この新しいヘッダを
パケットペイロードとともにパケットメモリ５０に入
れ、そのパケットを、図２の関連する物理層インタフェ
ース２０に送信する。

【００２０】図５はルーティング及び分類エンジン６８
の構造を示す。図３のＦＰ５８からの要求は、１つの要
求キュー７０に入れられ、１つの結果キュー７２におい
て結果が返送される。各キュー７０及び７２は、１６個
までの要求／結果エントリを保持する。ルート探索エン
ジン（ＲＬＥ）７４は、典型的にはヘッダに含まれる行
先アドレス（ＤＡ）に基づいて、経路探索を実行する。
パケット分類エンジン（ＰＣＥ）７６は、パケットヘッ
ダに含まれる特定の情報に基づいて、パケットフィルタ
リング検査を実行する。ＰＣＥ７６の動作が以下に詳細
に記載される。入力ＦＩＦＯバッファ７８は、要求キュ
ー７０と、ＲＬＥ７４及びＰＣＥ７６それぞれとの間に
配置され、出力ＦＩＦＯバッファ８０は、ＲＬＥ７４及
びＰＣＥ７６それぞれと、結果キュー７２との間に配置
される。ＦＩＦＯ７８及び８０は、ＲＬＥ７４によって
実行される処理と、ＰＣＥ７６によって実行される処理
との間を分割する手段を提供する。マルチプレクサ８１
によって、ＦＰ５８は、結果キュー７２、或いは要求キ
ュー７０、結果キュー７２及び図４の信号線６９上に現
れる状態情報からの状態を含む状態情報のいずれかを読
み出すことができるようになる。これらのエントリの構
造が以下に記載される。

【００２１】図６は、図５の要求キュー７０を介してＰ
ＣＥ７６及びＲＬＥ７４に渡されるルーティング及び分
類要求の構造を示す。その要求のサイズは、４つの６４
ビットワードである。種々のフィールドが以下に定義さ
れる。

【表１】

【００２２】上記の表に示されるように、個別の２組の
分類検査のための規定があり、１つは「ＰＣＥＲｏｏ
ｔ０」を付されるアドレスで開始し、もう１つは「ＰＣ
ＥＲｏｏｔ１」で開始する。これらの個別の開始アドレ
スの重要性が以下に記載される。

【００２３】上記のように、その要求の適切なフィール
ドが、図５のＲＬＥ７４及びＰＣＥ７６のための各入力
ＦＩＦＯ７８に供給される。Ｒｅｑ．ＩＤ及びＩＰ．Ｄ
ｅｓｔ．Ａｄｄｒのようなフィールドのうちのいくつか
は、ＲＬＥ７４及びＰＣＥ７６の両方に供給される。他
のフィールドは一方にのみ供給される。特にＰＣＥにル
ーティングされるフィールドの使用法が以下に記載され
る。

【００２４】図７及び図８は、図４のルーティング及び
分類エンジン６８から読み出される２つの異なるタイプ
のエントリの各構造を示す。図７は、図５の結果キュー
７２から得られ、分類サーチの結果を搬送する結果エン
トリを示す。図８は、図３のＦＰ５８に状態情報を搬送
するために用いられる状態エントリを示す。

【００２５】図７に示される結果エントリのフィールド
は以下のように定義される。

【表２】

【００２６】図８に示される状態エントリのフィールド
は以下のように定義される。

【表３】

【００２７】ルーティング及び分類エンジン６８の全体
的な動作が、図５〜図８を参照して以下に記載される。
図３のＦＰ５８は、探索及び分類要求を、要求キュー７
０に書き込む。要求が要求キュー７０の先頭に達すると
き、その要求からの種々の情報要素は、ＲＬＥ７４及び
ＰＣＥ７６のための各入力ＦＩＦＯ７８に同時に書き込
まれる。ＲＬＥ７４及びＰＣＥ７６は独立して各要求の
個別の部分において動作し、一般に、異なる時間で、所
与の要求に対する各処理動作を終了する。これらの動作
の結果が、出力ＦＩＦＯ８０に書き込まれる。所与のパ
ケットに対する両方の結果の組が、出力ＦＩＦＯ８０の
先頭に達したとき、１つの組み合わされた結果が、結果
キュー７２に書き込まれる。その組み合わされた結果は
ＦＰ５８によって読み出され、それを用いてＦＰ５８
は、上記のように、図３のＳＡＲ４０及び４２のための
新しいパケットヘッダ及び回路情報を作成する。

【００２８】より詳細には、ＦＰ５８は、バッチ形式で
ルーティング及び分類エンジン６８を用いる。要求キュ
ー７０内に十分な空間があるとき、一連の要求、１）４
つの結果エントリ、２）３つの結果エントリと後続する
１つの状態エントリ、３）２つの結果エントリと後続す
る２つの状態エントリ、４）１つの結果エントリと後続
する３つの状態エントリ、５）４つの状態エントリが存
在する。

【００２９】一般にＦＰ５８は、結果キュー７２が空に
なるまで、読出しコマンドを発行し、１つ或いは複数の
状態エントリが結果ブロックに含まれるときには必ず、
空であると推定される。その後ＦＰ５８は、ルーティン
グ及び分類エンジン６８が次の要求のバッチを処理して
いる間に、その結果を用いる。ＦＰ５８は、ＲＬＥ７４
及びＰＣＥ７６がビジーで保持され、キュー７０及び７
２と、ＦＩＦＯ７８及び８０とがオーバーフローするの
を防ぐように、状態情報を用いて要求の流れを管理す
る。

【００３０】例示される実施形態では、読み出すことが
できる状態エントリは１つしか存在せず、結果ブロック
内に多数の状態エントリが存在する場合には、この１つ
のエントリに対して何度も読出しが行われたことを表す
ことに留意されたい。別の実施形態では、例えば統計情
報を収集するために、或いは他のバックグラウンド処理
を行うために、第２〜第４の状態エントリにおいて付加
的な低優先度の情報を供給することが有用な場合もあ
る。

【００３１】結果に状態情報を付加する１つの重要な利
点は、ＦＰバス５６を用いる際の効率が改善されること
である。ＦＰ５８が結果の読出しコマンドを発行すると
きはいつでも、有効な結果情報或いは有効な状態情報の
いずれかが返送される。さらに、結果ブロックはバース
ト形式で返送され、読出しに関するオーバーヘッドを低
減できるようにする。またＦＰ５８は、１つの読出しト
ランザクションにおいてＲＬＥ７４及びＰＣＥ７６キュ
ーのついての情報と、ＲＸキュー６４及びＴＸキュー６
６についての情報とを取得する。

【００３２】図９は、図５のＰＣＥ７６の構造を示す。
フィルタ及び結合子（以下に記載する）を表すデータ
は、規則メモリ（ＲＭ）８２及び判定基準メモリ（Ｃ
Ｍ）８４に記憶される。ＣＭ８４は、３つの一般的にア
ドレス指定されたメモリＣＭ０８６、ＣＭ１８８及び
ＣＭ２９０を備える。３つの比較論理ブロック９２、
９４及び９６は、判定基準メモリ８６、８８及び９０に
それぞれ関連する。アドレス指定及び制御ロジック９８
は、図５の要求キュー７０から受信した要求を復号化し
て、ＲＭ８２及びＣＭ８４のためのアドレスを生成し、
各要求によって要求されるような多数の規則を通して配
列され、図５の結果キュー７２に渡される結果を生成す
る。またそのアドレス指定及び制御ロジック９８は、図
３のＩＯＰ２６に対するインタフェースも形成し、ＩＯ
Ｐ２６によってＲＭ８２及びＣＭ８４を読出し及び書込
みできるようにする。バストランシーバ１００は、ＩＯ
Ｐ２６とＲＭ８２及びＣＭ８４との間の必要なデータパ
スを提供する。ＡＮＤゲート１０２は、比較論理ブロッ
ク９２、９４及び９６からの対応するＭＡＴＣＨｎ出力
が全て真であるとき、１つのＭＡＴＣＨ信号を与える。

【００３３】パケットフィルタリングのための規則の組
は典型的には、ネットワーク管理ステーション（ＮＭ
Ｓ）によって発信されるが、特定された流れに基づいて
ＦＰ５８によって動的に割り当てることもできる。以下
の情報の一部或いは全部が、フィルタのためにＮＭＳ或
いはＦＰ５８によって供給される。その情報は、マスク
を有するＩＰ行先アドレス、マスクを有するＩＰソース
アドレス、ＩＰプロトコル識別子、ＴＣＰ／ＵＤＰソー
スポート及び行先ポート識別子、サービス識別子のＩＰ
タイプ及びマスク、種々のフラグである。そのパケット
がフィルタ判定基準と一致するか否かを判定するため
に、フィルタからの種々の情報要素が、受信された各パ
ケットからの対応する要素と比較される。一致する場合
には、パケットがその行先に向けて進めるようにする動
作のような、いくつかのデフォルト動作が典型的には行
われる。

【００３４】従来通りに、パケットフィルタは、線形に
サーチされる比較の組からなる順序付けされたリストと
して表される。ＰＣＥ７６では、フィルタ要素は、判定
基準（比較値）及び規則（リスト自体及び各比較のため
に用いられる演算子）に分割される。この規則と判定基
準の分離は、個別の規則メモリ（ＲＭ）８２及び判定基
準メモリ（ＣＭ）８４を使用する際に反映される。メモ
リ８２及び８４は各機能のために個別に最適化され、そ
の結果、効率及び性能が改善される。また、ＣＭ８４内
のエントリは、ＲＭ８２内の多数の規則によって参照さ
れることができ、さらに記憶効率が高められる。

【００３５】ＲＭ８２は、規則メモリエントリのアレイ
を含み、各エントリは２つのタイプのうちの１つであり
得る。第１のタイプは、１組の演算子と、対応するフィ
ルタのための被比較数を記憶するＣＭ８４の行へのポイ
ンタとを含む。第２のタイプは、別の規則メモリエント
リへのポインタを含む。これらのエントリを用いて、順
次サーチされる１組の規則において、不連続のセグメン
ト間でジャンプを行う。例示される実施形態では、ＲＭ
８２は１６Ｋまでのエントリを含むことができる。

【００３６】ＣＭ８４は、３つの個別のメモリＣＭ０
８６、ＣＭ１８８及びＣＭ２９０にセグメント化さ
れ、例示される実施形態では、各メモリは４Ｋまでのエ
ントリを含むことができる。ＣＭ８４の機構は、ＩＰパ
ケット分類において固有の階層を利用する。一定のフィ
ールド上でのフィルタリングは通常、同様に他のフィー
ルドに基づくフィルタリングを伴うので、個別のメモリ
ＣＭ０、ＣＭ１及びＣＭ２内にどのフィールドが記憶さ
れるかを限定することが望ましい。これらの限定によっ
て、さらに記憶効率が高められる。大部分の一般的にフ
ィルタリングされたフィールド、ソースアドレス及び行
先アドレスは、３つの全てのメモリＣＭ０８６、ＣＭ
１８８及びＣＭ２９０においてサポートされる。以
下に記載するように、他のフィールドは、ＣＭ１８８
及び／またはＣＭ２９０においてのみサポートされ
る。このアーキテクチャは、ＣＭ８４内の空間を割り当
てることができる自由度を最大限にすると同時に、効果
的な並列サーチを可能にする。ＣＭ８４の構造及び使用
法は、より詳細に以下に記載される。

【００３７】図１０は、規則メモリエントリとも呼ばれ
る、図９のＲＭ８２内のエントリの構造を示す。各３９
ビットエントリは、１ビットのタイプフィールドを有す
る。このフィールドが１の場合には、エントリのビット
１３〜０は、ＲＭ８２内の別の位置へのポインタ、すな
わち別の規則メモリエントリへのポインタを含む。この
フィールドが０である場合には、そのエントリはフィル
タ検査を実行するための情報を含む。この場合には、ビ
ット１１〜０は、検査のためのオペランドが見出され
る、ＣＭ８４の行のアドレスを含んでおり、ビット３５
〜１２は、その要求からの、各オペランド及びフィール
ドにおいて実行される動作の符号化ビットを含む。これ
らの動作は以下に詳細に記載される。ビット３６は、例
えば範囲検査を実行するための複合規則を形成するため
に用いられるキャリービットである。キャリービットが
０である場合には、その規則はそれ単独で評価される。
キャリービットが１である場合には、その規則は、次の
規則も真と評価する場合にのみ、真と評価する。ビット
３７は、要求の一部として検査される規則の列の最後に
到達したことを示す終了（Done）ビットである。

【００３８】判定基準演算子フィールドは、８つの３ビ
ット論理演算子コードを含む。各演算子コードは、その
要求及び判定基準メモリエントリから選択される対応す
る被比較数において実行される演算を規定する。判定基
準メモリエントリのフィールドが以下に記載される。被
比較数に対する判定基準演算子ビットの割当ては、以下
の通りである。３５〜３３ＣＭ０ＳＡ／ＤＡフィールド３２〜３０ＣＭ１プロトコルフィールド２９〜２７ＣＭ１ソースポートフィールド２６〜２４ＣＭ１ＳＡ／ＤＡ或いはＤＰフィールド２３〜２１ＣＭ２プロトコルフィールド２０〜１８ＣＭ２ＴＯＳ或いはマスクフィールドを有するＴＯＳ１７〜１５ＣＭ２ソースポート或いはマスクフィールドを有するフラグ１４〜１２ＣＭ１ＳＡ／ＤＡ或いはＳＰ或いはＤＰフィールド

【００３９】演算子コードは実行される比較を規定して
おり、その場合、要求からの被比較数は演算子の左側に
あり、判定基準メモリエントリからの被比較数は右側に
ある。例えば、演算子が「＞」である場合には、評価さ
れる式は、（要求データ＞判定基準データ）である。演
算子コードは以下の通りである。０００Ｇｒｅａｔｅｒｔｈａｎ（〜より大きい）００１Ｌｅｓｓｔｈａｎ（〜より小さい）０１０Ｅｑｕａｌ（〜に等しい）０１１ＮｏｔＥｑｕａｌ（〜に等しくない）１ｘｘＤｏｎ‘ｔｃａｒｅ（未定義、すなわち被比較数値に関わらず強制的に真）

【００４０】判定基準演算子を用いて、以下に記載する
ように、比較論理ブロック９２、９４及び９６内のロジ
ックを構成する。

【００４１】図１１は、図９のＣＭ０８６におけるエ
ントリの構造を示す。各エントリは、３８ビット長であ
る。１つのビット、すなわち、ビット３７を用いて、そ
のエントリのための２つの可能な構成を、３２ビットソ
ースアドレス（ＳＡ）か、或いは３２ビット行先アドレ
ス（ＤＡ）のいずれかとして区別する。ビット３１〜０
は、対応するフィルタによって必要とされるＳＡ或いは
ＤＡ値を含む。ビット３６〜３２は、エントリ内のＳＡ
／ＤＡと、その要求のＳＡ／ＤＡとの間の比較の範囲を
制限するために用いられる５ビットの符号化されたマス
ク値を含む。マスクの使用法は以下に詳細に記載され
る。

【００４２】図１２は、図９のＣＭ１８８内のエント
リの構造を示す。各エントリは４７ビット長である。ビ
ット４６〜４５に示されるように、４つの異なる構成を
取り得る。ＰＴＣＬフィールドは、４つの全ての構成に
おいてＩＰプロトコルを特定する。構成２及び３の１６
ビットのＳＰ及びＤＰはそれぞれ、ソースポート識別子
及び行先ポート識別子を表す。ビット３６〜３２の内容
は、構成２及び３では未定義である。

【００４３】図１３は、図９のＣＭ２９０内のエント
リの構造を示す。各エントリは５１ビット長である。ビ
ット５０〜４８に示されるように、８つの異なる構成を
取り得る。構成２〜７のＴＯＳフィールドは、サービス
のＩＰタイプを特定する。構成３〜７では、ＴＯＳマス
クフィールドは、以下のように、ＴＯＳ比較の範囲を限
定するために用いられる８ビットマスクを含む。８ビッ
トＦＬＡＧＳフィールドは、ＴＣＰ／ＵＤＰパケットか
らの対応するビットに対して比較されるフラグ値を含
む。８ビットＦＬＡＧＭＳＫフィールドは、以下のよ
うに、ＦＬＡＧＳ比較の範囲を限定するために用いられ
る。

【００４４】図１４は、比較論理ブロック９２、９４及
び９６の全般的な構造を示す。２つ以上の比較器ロジッ
ク１０４−１、．．．１０４−ｎのブロックを用いて、
多数の比較を平行して実行し、その場合に、各比較は、
要求の所与のフィールドと判定基準メモリエントリの対
応するフィールドとの間で行われる。ＣＭ０８６の場
合の比較ロジック９２では、例えば、２つの比較器論理
ブロック１０４が用いられ、１つは要求のソースアドレ
スフィールド用であり、もう１つは要求の行先アドレス
フィールド用である。ＣＭ１８８の場合の比較ロジッ
ク９４は、ソースアドレス、行先アドレス、ＩＰプロト
コル、ソースポート及び行先ポートのための比較器論理
ブロック１０４を含む。ＣＭ２９０の場合の比較ロジ
ック９６は、ソースアドレス、行先アドレス、ＩＰプロ
トコル、ソースポート、行先ポート、マスクのないサー
ビスタイプ、マスクのあるサービスタイプ及びフラグの
ための比較器論理ブロック１０４を含む。

【００４５】比較器論理ブロック１０４からの出力は、
ＮＯＴＥＱＵＡＬ（〜と等しくない：≠）、ＥＱＵＡ
Ｌ（〜と等しい：＝）、ＬＥＳＳＴＨＡＮ（〜より小
さい：＜）及びＧＲＥＡＴＥＲＴＨＡＮ（〜より大き
い：＞）のための指示を含む。これらの信号は、ＤＯ
Ｎ'ＴＣＡＲＥ機能を実施するために用いられる論理
「１」とともに、各セレクタ１０６−１、．．．１０６
−ｎの入力に供給される。セレクタ１０６は、制御入力
として、演算子タイプ規則メモリエントリから演算子を
受信する。これらの演算子は、上記のように、規則メモ
リエントリのビット３５〜１２内に存在する。

【００４６】セレクタ１０６の各出力は別のセレクタ１
０８に供給され、セレクタは、判定基準メモリエントリ
からの構成ビットに基づいて、セレクタ１０６の出力の
種々の組み合わせの中から選択を行う。例えば、ＣＭ０
の場合の比較ロジック９２では、構成セレクタ１０８
は、判定基準メモリエントリのビット３７の値に基づい
て、ＳＡ比較結果とＤＡ比較結果との間で選択を行う。
他の比較論理ブロック９４及び９６内の構成セレクタ１
０８も同様に動作する。構成セレクタ１０８からの出力
信号ＭＡＴＣＨは、その要求内のデータが、各判定基準
メモリ８６、８８或いは９０からの判定基準を満足する
か否かを示す。図９に示されるように、比較ブロック９
２、９４及び９６からのＭＡＴＣＨ出力はＡＮＤゲート
１０によって互いにＡＮＤを取られ、分類動作を制御す
るために、アドレス指定及び制御ロジック９８に１つの
ＭＡＴＣＨ指示を与える。

【００４７】図１５は、比較器論理ブロック１０４の全
般的な構造を示す。ＥＱＵＡＬ比較器１１０は、２つの
被比較数が等しいか否かを判定し、ＬＥＳＳＴＨＡＮ
比較器１１２は、被比較数の一方が他方の被比較数より
小さいか否かを判定し、ＧＲＥＡＴＥＲＴＨＡＮ比較
器１１４は、被比較数の一方が他方の被比較数より大き
いか否かを判定する。ＥＱＵＡＬ比較１１０からの出力
は、インバータ１１６によって反転され、ＮＯＴＥＱ
ＵＡＬ指示が得られる。

【００４８】各比較器１１０、１１２及び１１４への入
力は、ＣＭ８４からの被比較数（「ＣＭ被比較数」とし
て示される）及び要求からのおそらくマスクされた被比
較数（ＲＥＱ被比較数として示される）である。マスク
処理ロジックが、関連するマスクを有するフィールドの
ために用いられる。ＡＮＤゲート１１８は、ビット毎に
マスク処理を実施する。ＦｌａｇｓＭａｓｋの場合と
同様に、マルチビットマスク（「ＣＭマスク」として示
される）が直接用いられる場合があり、或いはＳＡ／Ｄ
Ａマスクの場合と同様に、復号化されるか、又はエキス
パンダロジック１２０により拡張される場合もある。エ
キスパンダロジック１２０は、５ビットの符号化された
マスク値によって示されるように、多数の後続のビット
位置におおいて０を有し、その他の場所では１を有する
３２ビット値を生成する。例えば、マスク値が、１０進
の１１に等価な２進の０１０１１である場合には、復号
化されたマスクは、先行する２１ビット位置において１
を有し、後続の１１ビット位置で０を有する１６進のＦ
ＦＦＦＦ８００である。このマスクは、ＳＡ／ＤＡの最
上位２１ビットのみが比較結果に作用することを示す。

【００４９】パケット分類エンジン（ＰＣＥ）７６の動
作は、全般に以下のように進む。１．ＲＭ８２及びＣＭ８４が図２のＩＯＰ２６によって
初期化される。これは、動的な割当て、或いはネットワ
ーク管理ステーション（ＮＭＳ）（以下に記載する）の
いずれかによって、電源投入時、及び動作中に行われ
る。２．ＦＰ５８によって提示されるパケット分類要求が、
図５の要求キュー７０から検索される。３．ＲＭ８２が、その要求のルート０アドレスの内容に
よって索引付けされ、そのサーチの第１の規則メモリエ
ントリを検索する。そのエントリがポインタタイプであ
る場合には、検索されたエントリ内の規則メモリアドレ
スに対して、このステップが繰り返される。このステッ
プは、何度も繰り返すことができる。４．検索された規則メモリエントリが演算子タイプであ
る場合には、判定基準メモリエントリが、規則メモリエ
ントリ内のＣＭアドレスにより規定される位置において
検索される。ＣＭ８４からの選択された被比較数が、規
則メモリエントリ内の演算子に従って、対応する要求の
フィールドと比較される。上記のように、種々のフィー
ルドがマスクされる場合がある。５．１に設定されたＤＯＮＥビットが到達するか、或い
は一致条件が見出される（すなわち比較演算の結果が真
になる）まで、規則メモリアドレスが１だけインクリメ
ントされる。ある規則は、ＣＡＲＲＹビットを設定する
場合もあり、それは、一致が宣言される前に、次の規則
も真であると評価することを要求している。６．サーチにおいて遭遇する任意の規則メモリエントリ
が、ポインタタイプのエントリである場合には、判定基
準メモリエントリではなく、別の規則メモリエントリを
指している。この場合、逐次的な規則評価が継続され、
指示される規則メモリエントリで開始される。７．要求のルート０アドレスで一旦開始されると、上記
プロセスが実行される。ルート０に関連するフィルタで
ＤＯＮＥが到達する場合には、ルート１アドレスで開始
して、そのプロセスは繰り返される。一致が見出される
場合には、その結果は、その一致がルート０か、ルート
１規則を用いて見出されたことを示す。８．一致を見出すか、或いはルート１サーチにおいてＤ
ＯＮＥを見出すことによって、サーチが終了するとき、
結果が、フィルタリング検査の結果を示す結果キュー７
２に書き込まれる。その結果は、最後に検査された規則
のアドレスを含み、一致が見出されたか否かを含んでい
る。一致が見出された場合には、そのアドレスは、その
結果に適した動作を開始する、動作テーブルに索引付け
するためのＦＰ５８によって用いられる。例えば、その
一致が、ある一定の値より小さいＤＡを有する全てのパ
ケットが入ることになることを示す規則の場合には、そ
の動作テーブルは、パケットが意図的に廃棄されるよう
になるルーチンを指している。

【００５０】上記のように、ＣＭ８４は、種々の異なる
構成において用いることができる。３つのメモリＣＭ０
８６、ＣＭ１８８及びＣＭ２９０はそれぞれ、異
なる構成を実現するための異なるモードにおいて用いる
ことができる。以下の真理値テーブルは判定基準メモリ
８６、８８及び９０の種々の構成モードを用いて実行す
ることができる種々の比較を提供する。「１」は、所与
の構成モードを用いて比較を実行できることを示してお
り、「０」は、比較を実行できないことを示している。

【表４】

【００５１】従って例えば、ＳＡ比較は、ＣＭ０−０、
ＣＭ１−０及びＣＭ２−０の任意のものを用いて実行す
ることができる。ＦＬＡＧＳ比較は、ＣＭ２−４〜ＣＭ
２−７の任意のものを用いて実行することができる。種
々の構成モードの任意のものを用いて所与の比較を実行
するための能力は、ＣＭ８４を編成する際に所望の自由
度を提供し、それにより効率が高められる。判定基準メ
モリ空間の割当ては、以下に詳細に記載される。

【００５２】判定基準メモリ構成情報を符号化する種々
の方法を用いることにより、別の実施形態において、記
憶効率を高めることができる場合もある。例示される実
施形態では、各判定基準メモリエントリのための構成メ
モリを格納するために、３０ビットが用いられることに
留意されたい。これらの３０ビットは、規則メモリエン
トリ内の演算子コードの２４ビットと、ＣＭ０エントリ
の１ビットと、ＣＭ１エントリの２ビットと、ＣＭ２エ
ントリの３ビットとを含む。この方式により、ＣＭ０、
ＣＭ１及びＣＭ２内の復号化が簡単になる。しかしなが
ら、判定基準メモリエントリのための被比較数及び演算
子の全ての実現可能な構成の数は、約３．３×１０⁶で
あり、従って２２ビットのみを用いて表すことができ
る。従って例えば、演算子及び被比較数情報が復号化さ
れる各規則メモリエントリにおいて、１つの２２ビット
構成フィールドを用いることができる場合もある。しか
しながら、そのような実施形態によって必要とされる復
号化は、各構成ビットとＣＭ８４の各セクションとの間
の一対一の対応関係の欠如により、例示される実施形態
よりも、一般的に、より複雑になる。

【００５３】図１６は、パケットフィルタリング情報が
図１の交換器１０において管理され、利用される方法を
示す。一般に、パケットフィルタリング情報の情報源
は、ネットワーク管理ステーション（ＮＭＳ）であり、
典型的には図１の交換器１０から離れて配置される。Ｎ
ＭＳは、簡易ネットワーク管理プロトコル（ＳＮＭＰ）
のような、ネットワーク管理プロトコルを用いて、図１
の交換器制御部１８内に存在する中央演算装置（ＣＰ）
と通信を行う。ＣＰは、ＮＭＳからフィルタリング情報
を受信し、その情報を分配するために、各回線インタフ
ェース１２のＩＯＰ２６に応答することができる。さら
に、ＣＰは不揮発（ＮＶ）記憶装置においてその情報を
保持し、ＮＭＳが利用できないときに、交換器１０が動
作できるようにする。

【００５４】ＣＰからＩＯＰ２６に送出されるフィルタ
リング情報は、（１）それぞれ受信したパケットに適用
することができる少数の判定基準を規定するフィルタ
と、（２）結合子、すなわち交換器１０内の種々のポー
ト及び／または回路と異なるフィルタのグループを関連
付ける情報と、（３）フィルタとの関連を有し、フィル
タ判定基準が満たされる場合に実行される動作とを含
む。

【００５５】動作時に、ＩＯＰ２６が初期化されると
き、ＣＰは、ＮＶ記憶装置からの現存するフィルタリン
グテーブルと結合データベースとを検索し、各回線イン
タフェース１２のＩＯＰ２６にそれをダウンロードす
る。ＮＭＳがフィルタ及び結合子を追加、削除或いは変
更するとき、新しい情報をＣＰに渡すためにＳＮＭＰ動
作要求を発行する。次に、ＣＰはその変更を各ＩＯＰ２
６に通知する。

【００５６】ＩＯＰ２６は、ＣＰからフィルタリング情
報を検索し、フィルタ、結合子及び動作のローカルコピ
ーを作成してメモリに格納する。ＩＯＰ２６は、ＣＰが
新しい情報を送出する場合には必ず、これらのローカル
コピーを更新する。ＩＯＰ２６は、種々のフィルタの場
合に行うことができる種々の動作のテーブルを用いて、
図２２の各転送エンジン２２内のＦＰメモリ６０をプロ
グラミングする。またＩＯＰ２６は、フィルタ及び結合
子に対応するＲＭエントリ及びＣＭエントリを作成し、
これらのエントリを用いて、ＰＣＥ７６（図５）のＲＭ
８２及びＣＭ８４（図９）をプログラミングする。ＩＯ
Ｐ２６がＣＰから新しいフィルタリング情報を受信する
場合には必ず、必要に応じてＲＭ及びＣＭエントリが追
加、削除或いは変更される。

【００５７】ＦＰ５８は、ＰＣＥ７６の支援によりパケ
ットを処理するための役割を果たす。ＩＯＰ２６によっ
て供給される情報を用いるとき、ＦＰ５８は、ルート０
及びルート１アドレスに対する、それぞれ受信したパケ
ットのポート及び回路識別のマップを作成し、これらの
アドレスを用いてＰＣＥ要求を作成し、その要求を要求
キュー７０（図５）を介してＰＣＥ７６に書き込む。上
記のように、一般にＦＰ５８は、可能ならば多数の要求
からなるバーストを書き込むことによって、バッチ形式
でＰＣＥ７６を動作させようと試みる。ＰＣＥは上記の
ようにその要求を処理する。ＦＰ５８は結果を取得する
ためにＰＣＥ７６をポーリングし、その結果は上記のよ
うにブロックでＰＣＥ７６によって返送される。各結果
において一致が示される場合、その結果からのＰＣＥ一
致アドレスは、そのパケットがどの動作を行うかを確認
するためにＩＯＰ２６によって確立される動作テーブル
への索引として用いられる。その後ＦＰ５８は、指示さ
れる動作を実行する。

【００５８】上記のように、ＲＭ８２及びＣＭ８４で
は、性能を高めるために１つのＩＣ上に実装されるメモ
リは比較的小さい。これらのメモリ内の限られた空間が
効率的に管理されることは重要である。ＩＯＰ２６は、
フィルタ判定基準のためのＣＭ８４内の空間の割当て、
及び規則セットのためのＲＭ８２内の空間の割当てを行
う役割を果たす。これらの動作は順次以下に記載され
る。

【００５９】フィルタは、２つのタイプのうちの１つ、
すなわち独立型か、複合型のいずれかとすることができ
る。独立型フィルタは、１つの規則のみを用いて実現す
ることができる。複合型フィルタは多数の規則を必要と
する。種々のタイプの複合型フィルタを構成することが
できるが、例示される実施形態で用いられる複合型フィ
ルタは、範囲フィルタのみである。範囲フィルタは、あ
る範囲の上限を検査するために１つの規則を、その範囲
の下限を検査するための別の規則を必要とする。従っ
て、フィルタを加える際の第１のステップは、そのフィ
ルタが独立型フィルタ、範囲フィルタのいずれであるか
を決定することである。そのフィルタが独立型フィルタ
である場合には、１つの判定基準メモリ構成のみが必要
とされるのに対して、範囲フィルタの場合には２つの構
成が必要とされる。その後、ＣＭ８４の内容がサーチ、
かつ／または評価され、ＣＭ８４においてそのフィルタ
を最もよく表現する方法を決定する。一旦構成が選択さ
れれば、そのフィルタ情報は、ＣＭ８４への更新情報と
して追加される。これらのプロセスは、以下に詳細に記
載される。

【００６０】所与のフィルタを実現するために用いるこ
とができる判定基準メモリエントリの種々のタイプの構
成がある。これらは、判定基準メモリ８６、８８及び９
０のうちのいずれが用いられるかによって、７つのＣＭ
構成に編成される、以下の表は、ＣＭ構成に従って編成
される、より一般的に用いられる構成タイプのうちのい
くつかを示す。

【表５】

【００６１】ＣＭ構成は、リソース消費の観点から、最
も高価なものから最も安価なものまでランク付けされ
る。多くのフィルタの場合、種々の構成のうちの任意の
構成を用いることができるが、その目標は、最も安価、
すなわち「最低限の」構成を用いて、メモリの使用効率
を最大限にすることである。例えば、（ＳＡ、ＳＡＭ
ａｓｋ）比較のみを必要とするフィルタは、任意のＣＭ
構成を用いて実装することができ、その最低限の構成は
（ＣＭ０）である。別の例としては、（ＳＡ、ＳＰ及び
ＰＴＣＬ）を必要とするフィルタは、４つの構成（ＣＭ
０、ＣＭ１）、（ＣＭ０、ＣＭ２）、（ＣＭ１、ＣＭ
２）、（ＣＭ０、ＣＭ１、ＣＭ２）のいずれかを用いて
実装することができ、その最低限の構成は（ＣＭ０、Ｃ
Ｍ１）である。

【００６２】最低限の構成は、その最低限利用可能な構
成をサーチする際の開始点として用いられる。最低限の
構成が利用可能な場合には、それが用いられる。そうで
ない場合には、利用可能な構成が見つかるまで、順次、
より高価な構成が考慮される。上記の例では、その構成
は以下の順序、すなわち（ＣＭ０、ＣＭ１）、（ＣＭ
０、ＣＭ２）、（ＣＭ１、ＣＭ２）及び（ＣＭ０、ＣＭ
１、ＣＭ２）の順にサーチされる。構成サーチは、一群
のリンクされた空き判定基準メモリ位置のリストを利用
し、各リストは、１つの行、例えば（ＣＭ０）、（ＣＭ
０、ＣＭ１）等において特定の空き列の組を表す。フィ
ルタによって必要とされる比較のタイプに基づいて、Ｉ
ＯＰ２６は、利用可能なエントリで最初のものを検索す
る所定のシーケンスで、全ての適切なリストをサーチす
る。

【００６３】選択される判定基準メモリ構成が、所与の
フィルタのために最低限必要とされる構成より大きい場
合には、残りの部分は、他のフィルタによって利用可能
である。従って上記の例では、（ＣＭ０、ＣＭ１）のみ
が必要とされるときに、構成（ＣＭ０、ＣＭ１、ＣＭ
２）が用いられる場合には、（ＣＭ２）の１ユニット
は、他のフィルタによって利用可能である。

【００６４】一旦ある構成が選択されたなら、フィルタ
の種々の要素が、ＣＭ８４の種々のセクションに割り当
てられる。（ＳＡ、ＳＰ及びＰＴＣＬ）を必要とするフ
ィルタの例で説明を続けると、構成（ＣＭ０、ＣＭ１）
が選択されるものと仮定すれば、ＳＡ及びＳＡＭａｓ
ｋはＣＭ０に割り当てられ、ＳＰ及びＰＴＣＬはＣＭ１
に適切に割り当てられる。この割当ては、上記テーブル
からの構成タイプ３＿１に対応する。ＣＭ０８６はモ
ード０において構成され、ＣＭ１８８はモード２にお
いて構成される。一旦割当てが終了すれば、ＣＭ８４の
ためのエントリ（或いは範囲フィルタのためのエント
リ）が生成される（図１１〜図１３及びそれに付随する
説明を参照されたい）。また、対応する規則メモリエン
トリに対する判定基準演算子（ビット３５〜１２）のた
めのデータも生成される（図１０及びそれに付随する説
明を参照されたい）。規則メモリエントリの残りは、以
下に説明するフィルタ結合中に生成される。

【００６５】フィルタが削除されるとき、削除されるフ
ィルタに用いられるＣＭ構成は再利用できるようにな
る。より大きな構成にすることができる場合には、利用
可能な構成が連結される。これは、上記のように全体と
して、或いは部分的に後に用いることができる。例え
ば、１ユニットの（ＣＭ０）が、フィルタの削除によっ
て空きになり、同じ行のＣＭ８４において１ユニットの
（ＣＭ１）が利用可能である場合には、１ユニットの
（ＣＭ０、ＣＭ１）が形成される。

【００６６】上記のように、ＩＯＰ２６は、フィルタの
「結合」を表す規則の組、すなわち論理ポート或いは回
路と１つ或いは複数のフィルタの組との間の関係を保持
するための役割も果たす。このプロセスはＲＭ８２の割
当て及びプログラミングを含む。結合子が追加されると
き、追加される結合子のサイズが最初に評価される。そ
のサイズは、論理ポート或いは回路、及び範囲フィルタ
及び非範囲フィルタの混合体で用いられるフィルタの数
により決定される。一旦結合子のサイズがわかれば、Ｒ
Ｍ８２内の空間が割り当てられる。例示される実施形態
では、規則メモリ空間は、そのサイズが２の累乗である
セグメントに割り当てられる。結合子に割り当てられる
まで、空きセグメントは各空きリスト上に保持され、削
除された結合子からのセグメントは、再利用するために
空きリストに戻される。個々にリンクされたリストを用
いて、そのセグメントは互いに連結される。例えば、各
空きリストは、同じサイズからなる割り当てられていな
いセグメントの個々にリンクされたリストである。各結
合子は、一般に異なるサイズのセグメントからなる個々
にリンクされたリストである。

【００６７】２１個の規則メモリエントリを必要とする
結合子を考慮する。この結合子の場合、サイズ１６、
４、２及び２のセグメントが割り当てられることが好ま
しい。１６エントリのセグメントは、１５の規則と、４
エントリセグメントへのポインタとを格納する。４エン
トリセグメントは、３つの規則と、２エントリセグメン
トの１つへのポインタとを格納し、２エントリセグメン
トは、１つの規則と、他の２エントリセグメントへのポ
インタとを格納する。最後のセグメントは２つの規則を
格納する。割当て中に、所望のサイズのセグメントが利
用できない場合には、より大きなセグメントが利用され
る。セグメント内の未使用の空間は単に未使用のまま残
されることができるか、或いは別法では、判定基準メモ
リ構成の割当ての場合に上で説明したのと同様にして、
他の結合子に割り当てるために利用することができる。

【００６８】一旦メモリ割当てが終了すれば、ＲＭ８２
のためのエントリが作成され、ＲＭ８２に書き込まれ
る。このプロセスの間に、各演算子タイプの規則は、そ
の規則で用いられることになる対応する判定基準メモリ
エントリのアドレスでプログラミングされ、その演算子
は、規則／判定基準の対によって表されるフィルタに基
づく適当な値でプログラミングされる。その規則は、フ
ィルタが検査されることになる所望のシーケンスに従っ
て、ＲＭ８２において論理シーケンスに配列される。Ｒ
Ｍ８２のセグメント内では、その規則は逐次的に配列さ
れる。多数のセグメントに及ぶ結合子の場合、そのセグ
メントは、規則が所望のシーケンスで評価されるよう
に、互いに連結される。

【００６９】パケット分類に関係する種々の装置及び方
法が記載されてきた。本発明は主にインターネットプロ
トコル（ＩＰ）パケット或いはメッセージを参照して記
載されてきたが、記載された技術は、他のタイプのメッ
セージの場合でも用いられることは明らかであろう。ま
た、ここで開示された本発明の概念から逸脱することな
く、上記の技術に対する他の変更形態及びその変形形態
が実現可能であることは当業者には明らかであろう。従
って本発明は、添付の請求の範囲及びその精神によって
のみ制限されるものと見なされるべきである。

【００７０】

【発明の効果】上記のように本発明によれば、パケット
フィルタリングを行うために高速のパケット分類を提供
する、ネットワーク装置内のパケット処理ロジックを実
現することができる。

【図面の簡単な説明】

【図１】本発明によるパケット分類エンジンを組み込ん
だネットワーク交換器のブロック図である。

【図２】図１のネットワーク交換器における回線インタ
フェースのブロック図である。

【図３】図２の回線インタフェース上のパケット転送エ
ンジンのブロック図である。

【図４】図３の転送エンジン内のパケットヘッダ分配器
の特定用途向け集積回路（ＡＳＩＣ）のブロック図であ
る。

【図５】図４のパケットヘッダ分配器ＡＳＩＣ内のルー
ティング及び分類エンジンのブロック図である。

【図６】図５のルーティング及び分類エンジンに渡され
るルーティング及び分類要求の構造図である。

【図７】図５のルーティング及び分類エンジンによって
供給されるルーティング及び分類結果の構造図である。

【図８】図５のルーティング及び分類エンジンによって
供給される状態指示の構造図である。

【図９】図５のルーティング及び分類エンジン内のパケ
ット分類エンジン（ＰＣＥ）のブロック図である。

【図１０】図９のパケット分類エンジン内の規則メモリ
エントリの構造図である。

【図１１】図９のパケット分類エンジン内の第１の判定
基準メモリエントリの構造図である。

【図１２】図９のパケット分類エンジン内の第２の判定
基準メモリエントリの構造図である。

【図１３】図９のパケット分類エンジン内の第３の判定
基準メモリエントリの構造図である。

【図１４】図９のパケット分類エンジン内の判定基準メ
モリのバンクに対する比較論理ブロックのブロック図で
ある。

【図１５】図１４の比較論理ブロックにおいて用いられ
る比較器論理ブロックのブロック図である。

【図１６】図１の交換器内の種々の処理構成要素によっ
て、パケットフィルタリング情報が如何に作成され、分
配され、用いられるかを示す図である。

【符号の説明】

１０ネットワーク交換器１２回線インタフェース１４ネットワークセグメント１６交換器構造部１８交換器制御部２０物理Ｉ／Ｏ及びフレーム処理回路２２転送エンジン２４交換器構造部インタフェース２６ＩＯＰ２８タイミング制御部３０ＤＣパワーコンバータ及び分配器４０着信ＳＡＲ４２発信ＳＡＲ４４、４６制御メモリ４８、５０パケットメモリ５２パケットヘッダ分配装置（ＰＨＤ）５４ＰＣＩバス５６ＦＰバス５８転送プロセッサ（ＦＰ）６０ＦＰメモリ６４Ｒｘキュー６６Ｔｘキュー６８ルーティング及び分類エンジン６９信号線７０要求キュー７２結果キュー７４ルート探索エンジン（ＲＣＥ）７６パケット分類エンジン（ＰＣＥ）７８ＩＮＦＩＦＯ８０ＯＵＴＦＩＦＯ８２規則メモリ（ＲＭ）８４、８６、８８、９０判定基準メモリ（ＣＭ）９２、９４、９６比較論理ブロック９８アドレス指定及び制御ロジック１００バストランシーバ１０２ＡＮＤゲート１０４比較論理ブロック１０６セレクタ１０８構成セレクタ１１０ＥＱＵＡＬ比較器１１２ＬＥＳＳＴＨＡＮ比較器１１４ＧＲＥＡＴＥＲＴＨＡＮ比較器１１６インバータ１１８ＡＮＤゲート１２０エキスパンダロジック

───────────────────────────────────────────────────── フロントページの続き (72)発明者サンジェイジー．チェリアンアメリカ合衆国 03033 ニューハンプシャー，ブルックリン，マックスウェルドライヴ６

Claims

【特許請求の範囲】

【請求項１】パケット分類装置であって、パケット分類要求者によって処理されているパケットか
らの情報を含むパケット分類要求を受信するように動作
する入力インタフェースロジックと、規則メモリエントリを記憶するように動作する規則メモ
リであって、前記各規則メモリエントリが演算子と判定
基準メモリポインタとを含む、該規則メモリと、判定基準メモリエントリを記憶するように動作する判定
基準メモリであって、各判定基準メモリエントリが判定
基準を含むような該判定基準メモリと、前記パケット分類要求者にパケット分類結果を提供する
ように動作する出力インタフェースロジックと、前記受信したパケット分類要求に応答して、（ｉ）前記規則メモリからの規則メモリエントリを検索
し、（ｉｉ）前記検索した規則メモリエントリ内の前記判定
基準メモリポインタによって規定される位置において、
前記判定基準メモリからの判定基準メモリエントリを検
索し、（ｉｉｉ）前記検索した規則メモリエントリ内の前記演
算子によって規定される演算であって、前記演算が、前
記パケット分類要求からの前記パケット情報と、前記検
索した判定基準メモリエントリからの前記判定基準とに
基づいて実行されている、該演算を実行し、（ｉｖ）前記演算を実行した結果を反映するパケット分
類結果を生成するように動作する制御ロジックとを備え
るパケット分類装置。
【請求項２】前記規則メモリは、第１のタイプ及び第
２のタイプの両方の規則メモリエントリを記憶するよう
に動作し、前記各第１のタイプの規則メモリエントリは
演算子と判定基準メモリポインタとを含み、前記各第２
のタイプの規則メモリエントリは、規則メモリポインタ
を含み、前記制御ロジックは、前記受信したパケット分類要求に
応答して、（ｉ）前記検索した規則メモリエントリが前記第１のタ
イプのエントリ、前記第２のタイプのエントリのいずれ
であるかを判定し、（ｉｉ）前記検索した規則メモリエントリが前記第１の
タイプのエントリである場合には、前記判定基準メモリ
エントリを検索して、前記規定された演算を実行し、（ｉｉｉ）前記検索した規則メモリエントリが第２のタ
イプのエントリである場合には、前記第２のタイプのエ
ントリに含まれる前記規則メモリポインタによって規定
される位置において別の規則メモリエントリを検索し、
新しく検索された規則メモリエントリに対して、上記の
ステップを繰返し行い、（ｉｖ）全ての検索した第１のタイプのエントリによっ
て規定される各演算を実行した結果を反映するパケット
分類結果を生成するように動作する、請求項１に記載の
パケット分類装置。
【請求項３】前記制御ロジックはさらに、終了の指示
があるまで、さらに別の規則メモリエントリに対してス
テップ（ｉ）〜（ｉｉｉ）を繰返し行うように動作す
る、請求項１に記載のパケット分類装置。
【請求項４】前記終了の指示は、検索した規則メモリ
エントリ内のアサートされたＤＯＮＥビットである、請
求項３に記載のパケット分類装置。
【請求項５】前記終了の指示は、検索した規則メモリ
エントリ内の前記演算子により規定される条件を満足す
ることである、請求項３に記載のパケット分類装置。
【請求項６】前記さらに別の規則メモリエントリは、
前記規則メモリ内の連続した位置に順次アクセスするこ
とにより検索される、請求項３に記載のパケット分類装
置。
【請求項７】前記さらに別の規則メモリエントリは、
検索した規則メモリエントリに含まれる規則メモリポイ
ンタに規定される位置にアクセスすることにより検索さ
れる、請求項３に記載のパケット分類装置。
【請求項８】前記制御ロジックは、前記検索したパケ
ット分類要求に含まれる規則メモリアドレスに基づい
て、前記規則メモリエントリを検索するように動作す
る、請求項１に記載のパケット分類装置。
【請求項９】前記制御ロジックによって検索された前
記規則メモリエントリは、第１の規則メモリエントリで
あり、前記制御ロジックは、前記受信したパケット分類
要求に含まれる第１の規則メモリアドレスに基づいて、
前記第１の規則メモリエントリを選択するように動作
し、前記制御ロジックはさらに、前記受信したパケット
分類要求に同様に含まれる第２の規則メモリアドレスに
基づいて、第２の規則メモリエントリを選択し、前記第
２の規則メモリエントリに対してステップ（ｉ）〜（ｉ
ｉｉ）を繰返し行うように動作する、請求項１に記載の
パケット分類装置。
【請求項１０】前記規則メモリエントリは、前記規則
メモリエントリが、第２の規則メモリエントリとの複合
規則を形成する第１の規則メモリエントリであるか否か
を示すＣＡＲＲＹ指示子を含み、前記制御ロジックは、
前記パケット分類結果が、前記第１及び前記第２の規則
メモリエントリの両方に対する前記演算の結果を反映す
るように、前記第２の規則メモリエントリに対してステ
ップ（ｉ）〜（ｉｉｉ）を繰返し行い、ステップ（ｉ
ｖ）において前記パケット分類結果を生成するように動
作する、請求項１に記載のパケット分類装置。
【請求項１１】前記判定基準メモリエントリ内の前記
判定基準、及び前記要求内の前記情報は、ネットワーク
アドレスである、請求項１に記載のパケット分類装置。
【請求項１２】前記アドレスは行先アドレスである、
請求項１１に記載のパケット分類装置。
【請求項１３】前記各判定基準メモリエントリは、前
記判定基準メモリエントリが構成される方法を指示する
構成情報を含み、前記制御ロジックは、（ｉ）前記検索
した判定基準メモリエントリの前記構成情報を解釈し
て、前記判定基準メモリエントリ内の多数のフィールド
のうちのいずれが、前記演算において用いられるかを判
定し、（ｉｉ）前記判定された構成に基づいて、前記判
定基準メモリの適切なフィールドと、前記パケット分類
要求からの対応する情報のみを用いて、前記演算を実行
するように動作する、請求項１に記載のパケット分類装
置。
【請求項１４】前記各判定基準メモリエントリは、前
記判定基準メモリエントリが構成される方法を指示する
構成情報を含み、前記制御ロジックは、（ｉ）前記検索
した判定基準メモリエントリの前記構成情報を解釈し
て、前記パケット分類要求からのどの情報が、前記演算
において用いられるかを判定し、（ｉｉ）前記判定され
た構成に基づいて、前記パケット分類要求からの適切な
情報と、前記判定基準メモリ内の対応する情報のみを用
いて、前記演算を実行するように動作する、請求項１に
記載のパケット分類装置。
【請求項１５】前記判定基準メモリは主要部に編成さ
れて、前記各判定基準メモリエントリが前記種々の主要
部とそれぞれ関連する種々のフィールドを含むように
し、前記各フィールドは、前記判定基準メモリエントリ
に含まれる構成情報に従って種々のタイプの判定基準を
保持するように構成可能であり、前記制御ロジックは、
前記各主要部に対して、前記判定基準メモリエントリに
含まれる前記構成情報に基づいて、前記判定基準メモリ
エントリの前記各フィールドを用いる前記演算に用いる
ための、前記パケット分類要求からの情報を選択するよ
うに動作する、請求項１に記載のパケット分類装置。
【請求項１６】前記判定基準メモリは、前記各判定基
準メモリエントリが、ソースアドレス或いは行先アドレ
スのいずれかとして構成可能な第１のフィールドと、ソ
ースアドレス、行先アドレス、或いは１組のポート識別
子情報のいずれかとして構成可能な第２のフィールド
と、ソースアドレス、行先アドレス、１組のポート識別
子情報或いは１組のフラグ情報のいずれかとして構成可
能な第３のフィールドとを含むように、３つの主要部を
備える、請求項１５に記載のパケット分類装置。
【請求項１７】ハードウエアサーチエンジンにサーチ
判定基準を保持するために用いられる１組の判定基準メ
モリ内の空間を管理する方法であって、前記判定基準メモリの種々の構成の順序を保持する過程
であって、前記構成が前記各構成を用いて判定基準メモ
リエントリを記憶するために必要とされる判定基準メモ
リ記憶空間の総量に準じて順序付けされるような該保持
する過程と、前記種々の構成に従って判定基準メモリエントリを記憶
するための前記判定基準メモリ内の空間の利用可能性を
指示する１組のリストを保持する過程と、所与のサーチを実行するために、前記構成のいずれが、
前記サーチに必要とされる判定基準メモリエントリを記
憶する判定基準メモリ記憶空間の最低量しか必要としな
い最小構成であるかを判定する過程と、前記リストによって指示されるように、最小の利用可能
な構成をサーチする過程であって、前記最小構成で開始
し、最初の前記利用可能な最小構成が見つかるまで、判
定基準メモリ空間の消費が増加する順序に進行するよう
なサーチする過程と、前記サーチのために必要とされる前記判定基準メモリエ
ントリを記憶するために、前記最小の利用可能な構成を
割り当て、前記割り当てられた構成が利用可能でなくな
ることを示すために、利用可能性のリストを更新する過
程とを有する、方法。
【請求項１８】前記最小構成以外の構成が割り当てら
れる場合には、前記割り当てられた構成のうちの不要な
部分が、別の判定基準メモリエントリに割り当てること
ができる異なる構成として用いることができるか否かを
判定する過程と、前記異なる構成の前記利用可能性を示
すために前記利用可能性のリストを更新する過程とをさ
らに有する、請求項１７に記載の方法。