説明

パケット分類器、パケット分類方法、及びパケット分類プログラム

【課題】パケット分類器において、不要なメモリアクセスの発生を未然に防止し、消費電力を削減すること。
【解決手段】パケット分類器は、コマンド入力ブロックと、複数のルール比較ブロックとを備える。コマンド入力ブロックは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成する。複数のルール比較ブロックは、管理下のルールにおけるフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされる。検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。コマンド入力ブロックは、検索キー、新規ルール、あるいは既存ルールを参照することによって、選択グループに属するルール比較ブロックにだけ入力コマンドを入力する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、パケット分類(Packet Classification)に関する。
【背景技術】
【0002】
パケット分類は、ネットワーク上のルータやスイッチにおいて、パケットを「フロー」と呼ばれる一連の属性をもつパケット列に分類するための重要な技術である。パケット分類は、個々のフローに対するQoS(Quality of Service)の提供や、ファイヤウォール(Firewall)等のセキュリティといった、付加的な価値をもつネットワークアプリケーションの実現に重要な役割を果たす。
【0003】
パケット分類では、パケットのヘッダに含まれている1つ以上のフィールドを用いて、「ルール」が定義される。ルールは、「フィルタ」と呼ばれることもある。ルールは、例えば、パケットのIP(Internet Protocol)ヘッダに定義されている送信元IPアドレス、宛先IPアドレス、プロトコル番号に加え、TCP(Transmission Control Protocol)/UDP(User Datagram Protocol)ヘッダに定義されている送信ポート番号、宛先ポート番号といった複数のヘッダフィールドによって定義される。このようにルールが複数のヘッダフィールドを用いて定義されている場合のパケット分類は、特に、Multi−Field Packet Classificationと呼ばれる。
【0004】
通常、このようなルールは複数個定義される。パケットが到着すると、そのパケットヘッダからルールの定義に用いられているフィールド値が抽出される。抽出されたフィールド値の組が複数個のルールと比較され、どのルールにマッチするか判定されることにより、パケットがフローに分類される。ここで、到着したパケットのヘッダから抽出されたフィールド値の組を「検索キー」と呼ぶ。また、一般的には、各ルールに対して、優先度(Priority)とアクション(Action)とが定義される。検索キーが複数個のルールのうち、2つ以上のルールにマッチする場合には、優先度がより高いルールが選択される。また、アクションには、そのルールにマッチした場合に到着パケットをどのように扱うか(例えば、廃棄する、1番のポートに送信する等)が定義される。
【0005】
また、ルールにおける各フィールドに対しては、ある特定の値として定義されるExact Match、上位の複数ビットは特定されるが下位の数ビットはワイルドカード(wildcard)‘*’を用いて不定として定義されるPrefix Match、2つのある特定の値の範囲として定義するRange Match、個々のビット単位にワイルドカードを指定して定義されるWildcard Matchといった手法が用いられる。例えば、8bitのフィールドを考えた場合、“00110101”のように特定値として指定されるものがExact Match、“0011****”のように、“0011”の4bitから始まる値として指定されるものがPrefix Match、[3−64]のように8bitのフィールドが10進数で考えた際に3から64の範囲に入っていればよいとするものがRange Match、“0**10*01”のようにビット単位でワイルドカードが使用できるものがWildcard Matchである。
【0006】
このようなMulti−Field Packet Classification技術に関して、ルールセットの大容量化とリンク速度の向上により、高速なルータやスイッチにおいてこれをいかに高速に処理させるかが1つの技術的な課題となっている。例えば、単純な手法として、ルールセットに含まれる全てのルールを優先度順にリストで管理し、リストの先頭(優先度が高いルール)から1つずつ順番に比較を行うリニアサーチ(Linear Search)が考えられる。しかし、このような手法では、最悪ルールセットに含まれる全てのルールとの一致比較処理が必要となり、パケット分類処理にかかる時間が非常に大きくなってしまうという問題がある。このため、現状、高速なパケット分類処理を実現するためにTernary Content Addressable Memory(TCAM)を基にした手法が用いられることが多い。
【0007】
しかしながら、TCAMはコストが高く、消費電力や回路規模も大きいといった問題が存在する。また、Range Matchを用いた場合には、そのルールをPrefix Matchを用いたルールに分割する必要があるため、ルール数が増加してしまうといった問題もある。
【0008】
その一方で、TCAMの高コスト、高消費電力の問題を回避すべく、より低コスト、低消費電力なStatic Random Access Memory(SRAM)やDynamic Random Access Memory(DRAM)を用いた様々なMulti−Field Packet Classification手法が提案されている。
【0009】
例えば、非特許文献1では、「決定木(Decision Tree)」を用いた手法が提案されている。決定木を用いた手法では、全てのルールに対してマッチングを行うのではなく、当該検索キーがマッチする可能性のある少数のルールに対してのみマッチングを行う。これにより、検索処理に要する時間が短縮される。決定木を用いた手法について図1〜図3を用いて簡単に説明する。
【0010】
図1は、それぞれ4bit長である2つのフィールドX、Yを用いて定義されたR0からR15までの16個のルールからなるルールセットの例を示している。フィールドX、Yは、例えば、送信元IPアドレスや送信元ポート番号等、実際のパケットヘッダフィールドに相当する。なお、フィールドXは、2進数で表記されており、‘*’はワイルドカードを示している。また、フィールドYは、Range Matchで表記されており、“[a:b]”のa、bはそれぞれ下限値、上限値(10進数表記)を示している。また、ここでは、各ルールに付与される優先度とアクションについては省略している。
【0011】
図2は、図1で示されたルールセットを、フィールドX、Yの2軸から成る2次元空間上で表している。図中のX軸、Y軸上の数は、それぞれ10進数で表記してある。決定木を用いた手法によれば、図2に示されるような多次元空間を複数の次元に着目して分割する。そして、分割領域内に存在するルール数がある閾値以下になるまで領域分割を繰り返すことにより、決定木が構築される。ここで、分割された領域で管理されるルール群を「ルールリスト」と呼ぶ。
【0012】
図3は、図1で示されたルールセットに対して構築された決定木の一例を示している。なお、図3で示される決定木では、分割領域内のルール数の閾値は2に設定されている。図3に示されるように、まず、全空間がX方向とY方向のそれぞれに2分割される。つまり、全空間(X、Y)=([0:15]、[0:15])が、領域0([0:7]、[0:7])、領域1([0:7]、[8:15])、領域2([8:15]、[0:7])、及び領域3([8:15]、[8:15])の4つの領域に分割される。また、それぞれの領域で管理されるルールリストは、[R7、R8、R9、R11](領域0)、[R0、R6、R9、R10、R11、R12](領域1)、[R1、R2、R3、R4、R5、R13、R14](領域2)、[R10、R14、R15](領域3)となる。各領域には、まだ閾値である2よりも多いルールが管理されているため、それぞれの領域について、閾値以下のルール数になるまでさらに領域分割を行う。図3に示される例では、全空間は最終的に22の領域に分割されている。なお、決定木を構築するアルゴリズムについては、非特許文献1や非特許文献2に記載されているため、ここでは省略する。
【0013】
パケット分類を行う場合には、検索キーを参照しながら決定木を辿っていき、辿り着いた葉ノードで管理されている閾値数以下のルールの全てに対してマッチングが行われる。例として、検索キーがX=0111、Y=1001となるパケットに対するパケット分類を考える。図3に示される決定木では、根ノードにおいて全空間が上記4つの領域に分割されており、当該パケットは、それら4つの領域のうち、領域1([0:7]、[8:15])に属することが分かる。続いて、領域1のノードでは、更に、空間がX方向とY方向のそれぞれに2分割されている。つまり、領域1が、領域10([0:3]、[8:11])、領域11([0:3]、[12:15])、領域12([4:7]、[8:11])、及び領域13([4:7]、[12:15])に4分割されている。当該パケットは、このうち領域12に属することが分かる。更にその領域12は4分割されており、当該パケットは、領域122([6:7]、[8:9])に属することが分かる。そして、その領域122で管理されている2つのルールR9、R10に対してマッチングが実施され、マッチしたルールが選択される。なお、本例では、当該パケットがルールR9、R10の両方にマッチするため、図3では省略している各ルールに付与された優先度に応じて、ルールが選択される。
【0014】
以上に説明されたような決定木を用いた手法によれば、領域分割の結果、同じルールが複数の分割領域で管理される可能性があり、これは以下「ルールの複製」と参照される。例えば、図3では、R7やR9等のルールが複製されている。ルールの複製が発生した場合、複製されたルールそのもの、あるいは、複製されたルールに対するアドレス値を管理するためのメモリ容量が増加し、見た目上、実際のルールセットよりも多くのルールを扱うことになる。つまり、ルールの複製は、決定木におけるデータ量の増加を招く。
【0015】
ルールの複製を抑制するため、非特許文献3で開示されているような手法が提案されている。非特許文献3では、複数の決定木を用意し、決定木毎に領域分割に用いるフィールド(次元)を使い分けることにより、異なる決定木を構築する。そして、各ルールは、ルールの複製が発生しないいずれかの決定木において管理する。決定木の数には上限があるため、いずれの決定木においても複製が発生しない場合には、例えば最後の決定木にて当該ルールは管理されることになるが、複数の決定木を用いることによってルールの複製を防止することができる。なお、非特許文献3の方式は、非特許文献2と同様、ハードウェアがパイプライン処理を用いてパケット分類を実施する方式として提案されている。
【0016】
また、特許文献1では、パケットのタイプと、そのパケットタイプに依存して存在する複数のパケットフィールド値から成るルールとの組み合わせを単一の分類規則テーブル(ルールテーブル)で管理するパケット分類器が開示されている。パケットタイプをインデックスとして利用することにより、様々なパケットタイプに対するルールを同一のテーブルを用いて管理することができる。
【先行技術文献】
【特許文献】
【0017】
【特許文献1】特開2006−20317号公報
【非特許文献】
【0018】
【非特許文献1】Sumeet Singh、Florin Baboescu、George Varghese、Jia Wang、“Packet Classification Using Multidimensional Cutting”、Proceedings of the ACM SIGCOMM 2003 Conference on Applications、Technologies、Architectures、and Protocols for Computer Communications、2003年、pp.213−224
【非特許文献2】Weirong Jiang、 Viktor K. Prasanna、“Large−Scale Wire−Speed Packet Classification on FPGAs”、Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays、2009年、pp.219−228
【非特許文献3】Weirong Jiang、 Viktor K. Prasanna、Norio Yamagaki、“Decision Forest: A Scalable Architecture for Flexible Flow Matching on FPGA”、Proceedings of 2010 International Conference on Field Programmable Logic and Application、2010年、pp.394−399
【発明の概要】
【発明が解決しようとする課題】
【0019】
上記の関連技術に記載されているようなパケット分類器によれば、検索キーに一致するルールの検索が行われる場合に、全ての決定木において検索処理が実行される。しかしながら、このことは、パケット分類器の消費電力の無用な増加を招く。それは、各ノードにおいて領域分割に用いるフィールドは複数の決定木で異なっており、入力された検索キーと一致するルールが存在する可能性が無い決定木においても、検索処理が実行されてしまうからである。検索処理では、必要な情報をメモリから読み出すといった処理が行われるため、パケット分類器の消費電力がいたずらに増加してしまう。
【0020】
本発明の1つの目的は、パケット分類器において、不要なメモリアクセスの発生を未然に防止し、消費電力を削減することができる技術を提供することにある。
【課題を解決するための手段】
【0021】
本発明の1つの観点において、パケット分類に用いられるルールを管理するパケット分類器が提供される。各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義される。パケット分類器は、コマンド入力ブロックと、複数のルール比較ブロックとを備える。コマンド入力ブロックは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成する。複数のルール比較ブロックの各々は、1以上のルールを管理し、上記入力コマンドに応じた処理を実行する。複数のルール比較ブロックは、管理下のルールにおける1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。コマンド入力ブロックは、検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力する。
【0022】
本発明の他の観点において、パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法が提供される。各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義される。本発明に係るパケット分類方法は、(A)パケット分類器が、複数のルール比較ブロックを提供するステップ、を含む。ここで、複数のルール比較ブロックの各々は、1以上のルールを管理し、入力コマンドに応じた処理を実行するように構成される。入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドである。複数のルール比較ブロックは、管理下のルールにおける1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けさる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。本発明に係るパケット分類方法は、更に、(B)検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力するステップと、(C)選択ルール比較ブロックにおいて、入力コマンドに応じた処理を実行するステップと、を含む。
【0023】
本発明の更に他の観点において、コンピュータによって実行され、当該コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムが提供される。各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義される。パケット分類器は、コマンド入力ブロックと、複数のルール比較ブロックとを備える。コマンド入力ブロックは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成する。複数のルール比較ブロックの各々は、1以上のルールを管理し、上記入力コマンドに応じた処理を実行する。複数のルール比較ブロックは、管理下のルールにおける1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。コマンド入力ブロックは、検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力する。
【発明の効果】
【0024】
本発明によれば、パケット分類器において、不要なメモリアクセスの発生を未然に防止し、消費電力を削減することが可能となる。
【図面の簡単な説明】
【0025】
【図1】図1は、ルールセットの一例を示す概念図である。
【図2】図2は、図1で示されたルールセットがフィールドX、Yの2軸から成る2次元空間上に配置された場合を示す概念図である。
【図3】図3は、図1で示されたルールセットに対する決定木の一例を示す概念図である。
【図4】図4は、本発明の第1の実施の形態に係るパケット分類器の構成を示すブロック図である。
【図5】図5は、第1の実施の形態に係るパケット分類器の各ルール比較ブロックが管理するルールの概念図である。
【図6】図6は、第1の実施の形態に係るパケット分類器の各ルール比較ブロックが決定木で実現される場合の構成を示すブロック図である。
【図7】図7は、第1の実施の形態における決定木ノード処理ブロックと決定木の各ノードとの対応関係を示す概念図である。
【図8】図8は、第1の実施の形態に係る決定木処理ブロックの決定木ノード処理ブロックの構成を示すブロック図である。
【図9】図9は、第1の実施の形態に係る決定木処理ブロックのエントリ数カウントブロックの構成を示すブロック図である。
【図10】図10は、第1の実施の形態におけるルール処理ブロックと決定木の各葉ノードのルールリストに含まれるルールとの対応関係を示す概念図である。
【図11】図11は、第1の実施の形態に係る決定木処理ブロックのルール処理ブロックの構成を示すブロック図である。
【図12】図12は、第1の実施の形態に係るコマンド入力ブロックの構成を示すブロック図である。
【図13】図13は、第1の実施の形態におけるコマンド入力ブロックのコマンド出力情報記憶ブロックが記憶するコマンド出力情報を示す概念図である。
【図14】図14は、第1の実施の形態におけるコマンドの構成例を示す概念図である。
【図15】図15は、第1の実施の形態におけるLOOKUP処理を示すフローチャートである。
【図16】図16は、ステップA2の処理を示すフローチャートである。
【図17】図17は、ステップB1の処理を示すフローチャートである。
【図18】図18は、第1の実施の形態におけるノード情報の構成例を示す概念図である。
【図19】図19は、第1の実施の形態におけるアドレス算出方法を説明するための図である。
【図20】図20は、ステップB3の処理を示すフローチャートである。
【図21】図21は、第1の実施の形態におけるエントリ情報の構成例を示す概念図である。
【図22】図22は、第1の実施の形態におけるINSERT処理を示すフローチャートである。
【図23】図23は、ステップA4の処理を示すフローチャートである。
【図24】図24は、ステップB4の処理を示すフローチャートである。
【図25】図25は、ステップA5の処理を示すフローチャートである。
【図26】図26は、ステップA7の処理を示すフローチャートである。
【図27】図27は、第1の実施の形態におけるDELETE処理を示すフローチャートである。
【図28】図28は、ステップA9の処理を示すフローチャートである。
【図29】図29は、ステップA10の処理を示すフローチャートである。
【図30】図30は、ステップB8の処理を示すフローチャートである。
【図31】図31は、第1の実施の形態に係るパケット分類器の第2の構成例における各ルール比較ブロックの構成を示すブロック図である。
【図32】図32は、第1の実施の形態の第2の構成例におけるLOOKUP処理を示すフローチャートである。
【図33】図33は、ステップA12の処理を示すフローチャートである。
【図34】図34は、第1の実施の形態の第2の構成例におけるINSERT処理を示すフローチャートである。
【図35】図35は、ステップA13の処理を示すフローチャートである。
【図36】図36は、第1の実施の形態の第2の構成例におけるDELETE処理を示すフローチャートである。
【図37】図37は、第1の実施の形態の第3の構成例におけるINSERT処理のステップA14の処理を示すフローチャートである。
【図38】図38は、本発明の第2の実施の形態に係るパケット分類器の構成を示すブロック図である。
【図39】図39は、第2の実施の形態に係るコマンド入力ブロックの構成を示すブロック図である。
【図40】図40は、第2の実施の形態におけるコマンド入力ブロックのコマンド出力情報記憶ブロックが記憶するコマンド出力情報を示す概念図である。
【図41】図41は、本発明の第3の実施の形態に係るパケット分類器の構成を示すブロック図である。
【図42】図42は、第3の実施の形態におけるINSERT処理を示すフローチャートである。
【図43】図43は、ステップA15の処理を示すフローチャートである。
【図44】図44は、ステップA18の処理を示すフローチャートである。
【図45】図45は、本発明の第4の実施の形態に係るパケット分類器の構成を示すブロック図である。
【発明を実施するための形態】
【0026】
添付図面を参照して、本発明の実施の形態を説明する。
【0027】
1.第1の実施の形態
1−1.概要
図4は、本発明の第1の実施の形態に係るパケット分類器1の構成を示すブロック図である。パケット分類器1は、パケット分類に用いられる複数のルールを管理する。各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義される。更に、本実施の形態に係るパケット分類器1は、入力コマンドに応じて、エントリの動的更新(新規ルールの追加、既存ルールの削除)を自動的に行う。
【0028】
本実施の形態において、パケット分類器1は、ハードウェア回路により実現される。より詳細には、図4に示されるように、パケット分類器1は、1個以上のルール比較ブロック2(2−1〜2−N:Nは1以上の整数)、エントリ追加対象決定ブロック3、コマンド入力ブロック4、及び結果出力ブロック5を備えている。また、パケット分類器1には入力データ6が入力され、パケット分類器1からは出力データ7が出力される。
【0029】
入力データ6は、パケット分類器1が実行すべき処理に依存する。パケット分類器1が実行する処理としては、(1)検索キーにマッチするルールを検索する処理(以下、「LOOKUP処理」と参照される)、(2)新規ルール(新規エントリ)を追加する処理(以下、「INSERT処理」と参照される)、及び(3)既存ルール(既存エントリ)を無効化する処理(以下、「DELETE処理」と参照される)、(4)パケット分類器1に含まれるメモリや設定レジスタ等へ予め設定値を書き込むConfiguration処理、が挙げられる。ここで、Configuration処理は初期化時に行われ、パケット分類器1に含まれる各ブロック内に備えられた設定レジスタやメモリへ構成に関わる値を設定することである。以下では、LOOKUP処理、INSERT処理、DELETE処理に関してのみ説明する。入力データ6は、処理種別を示す種別データと、当該処理で用いられるデータとを含む。LOOKUP処理の場合、入力データ6は、LOOKUP処理を示す種別データと、検索キーとを含む。INSERT処理の場合、入力データ6は、INSERT処理を示す種別データと、追加すべき新規ルールとを含む。DELETE処理の場合、入力データ6は、DELETE処理を示す種別データと、無効化すべき既存ルールとを含む。
【0030】
コマンド入力ブロック4は、入力データ6を受け取り、その入力データ6に応じた入力コマンドを作成する。入力データ6と同様に、入力コマンドは、処理種別を示す種別データと、当該処理で用いられるデータとを含む。LOOKUP処理の実行を指示する検索コマンドは、LOOKUP処理を示す種別データと、検索キーとを含む。INSERT処理の実行を指示する挿入コマンドは、INSERT処理を示す種別データと、追加すべき新規ルールとを含む。DELETE処理の実行を指示する削除コマンドは、DELETE処理を示す種別データと、無効化すべき既存ルールとを含む。
【0031】
コマンド入力ブロック4は、生成した入力コマンドを、ルール比較ブロック2に入力する。ここで、コマンド入力ブロック4は、入力コマンドを、必ずしも全てのルール比較ブロック2−1〜2−Nに入力するわけではなく、複数のルール比較ブロック2−1〜2−Nのうち必要なもの(選択ルール比較ブロック)だけに入力する。具体的には、LOOKUP処理時には、コマンド入力ブロック4は、検索キーにマッチするルールを管理している可能性があるルール比較ブロック2に対してのみ、入力コマンドを入力する。INSERT処理時には、コマンド入力ブロック4は、新規ルールを管理する可能性があるルール比較ブロック2に対してのみ、入力コマンドを入力する。DELETE処理時には、コマンド入力ブロック4は、削除すべき既存ルールを管理している可能性があるルール比較ブロック2に対してのみ、入力コマンドを入力する。より詳細については後述する。
【0032】
ルール比較ブロック2−1〜2−Nは、パケット分類に用いられる複数のルールを、ある方針に従って分散的に管理する。ここでは、単一のルールは、複製が発生しないように、ルール比較ブロック2−1〜2−Nのうちいずれか1つによって管理されるとする。例えば、複数のルール比較ブロック2−1〜2−Nのそれぞれが、パケット分類に用いられる複数の決定木を構成することが考えられる。この場合、複数の決定木は、非特許文献3に記載されている手法と同様に、ルールの複製が生じないように構成される。つまり、各ルールは、当該ルールの複製が生じない決定木において管理される。言い換えれば、単一のルールは、複数の決定木のうちいずれか1つの決定木における単一の葉ノードでのみ管理される。
【0033】
各ルール比較ブロック2は、1以上のルールを管理する。そして、各ルール比較ブロック2は、コマンド入力ブロック4から入力された入力コマンドに応じて、LOOKUP処理、INSERT処理、あるいはDELETE処理を実行する。尚、複数のルール比較ブロック2−1〜2−Nは、同時並列に各処理を実行することができる。
【0034】
<LOOKUP処理>
ルール比較ブロック2は、検索コマンドに応じて、LOOKUP処理を実行する。具体的には、ルール比較ブロック2は、自身が管理するルール群に対して、検索キーがいずれかのルールにマッチするか否かを判定する。検索キーにマッチするルール(以下、マッチルールと呼ぶ)が存在する場合、当該ルール比較ブロック2は、当該マッチルールを結果出力ブロック5に通知する。検索キーが複数のルールにマッチする場合、当該ルール比較ブロック2は、複数のマッチルールのうち最も優先度の高いルールを結果出力ブロック5に通知する。一方、検索キーにマッチするルールが存在しない場合、当該ルール比較ブロック2は、マッチルールが存在しなかったことを結果出力ブロック5に通知する。結果出力ブロック5は、各ルール比較ブロック2から検索結果を受け取り、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック5は、その選択結果を示す出力データ7を、LOOKUP処理の最終結果として出力する。
【0035】
<INSERT処理>
ルール比較ブロック2は、挿入コマンドに応じて、INSERT処理を実行する。具体的には、まず、各ルール比較ブロック2は、新規ルールを自身で管理すべきかを判定する。例えば、ルール比較ブロック2が決定木を用いて構成されている場合、自身の決定木に追加してもルールの複製が発生しないか、つまり、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得るかどうかを判定する。ルールの複製が発生してしまう場合、当該ルール比較ブロック2は、新規ルールの追加対象とはならない。一方、新規ルールを自身で管理しても良いと判定した場合、当該ルール比較ブロック2は「エントリ追加対象候補」となる。例えば、ルール比較ブロック2が決定木を用いて構成されている場合、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得ると判定された場合に、当該ルール比較ブロック2は「エントリ追加対象候補」となる。また、この際、当該単一の葉ノードは「追加対象葉ノード」となる。
【0036】
実際にエントリが追加されるエントリ追加対象のルール比較ブロック2は、上記エントリ追加対象候補の中から選ばれる。そのエントリ追加対象を選ぶのが、エントリ追加対象決定ブロック3である。図4に示されるように、このエントリ追加対象決定ブロック3は、複数のルール比較ブロック2−1〜2−Nの各々に接続されている。そして、エントリ追加対象決定ブロック3は、各ルール比較ブロック2から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。
【0037】
例えば、各エントリ追加対象候補は、当該ルール比較ブロック2が管理している有効なルールのエントリ数をエントリ追加対象決定ブロック3に通知する。この際、例えば、各エントリ追加対象候補が、ルールを管理するメモリ領域を当該ルール比較ブロック2内でさらに細分化して管理している場合には、新規ルールを追加すべきルール管理エリアで既に管理されている有効なルールのエントリ数を通知しても良い。例えば、ルール比較ブロック2が決定木を用いて構成されている場合、追加対象葉ノードが管理している有効なルールのエントリ数を通知する。そして、エントリ追加対象決定ブロック3は、各エントリ追加対象候補から受け取った有効エントリ数を参照し、所定のポリシーに従って、エントリ追加対象を選択する。例えば、エントリ追加対象決定ブロック3は、当該有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。この場合、複数のルール比較ブロック間でのルール数の偏りが抑えられ、好適である。
【0038】
エントリ追加対象決定ブロック3は、エントリ追加対象の選択結果を各ルール比較ブロック2に通知する。具体的には、エントリ追加対象決定ブロック3は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック2に対してルール追加処理の不実行を指示する。そして、エントリ追加対象であるルール比較ブロック2は、新規ルールを、自身の管理するルールリストに追加する。
【0039】
このようにして、INSERT処理が実行される。結果出力ブロック5は、複数のルール比較ブロック2−1〜2−Nから処理結果を受け取り、INSERT処理の最終結果を示す出力データ7を出力する。
【0040】
<DELETE処理>
ルール比較ブロック2は、削除コマンドに応じて、DELETE処理を実行する。具体的には、各ルール比較ブロック2は、削除対象である既存ルールが自身で管理されているか否かを判定する。当該既存ルールが自身で管理されている場合、当該ルール比較ブロック2は「エントリ削除対象」となる。また、ルール比較ブロック2が決定木を用いて構成されている場合、削除対象である既存ルールが管理されている葉ノードは「削除対象葉ノード」となる。エントリ削除対象であるルール比較ブロック2は、当該既存ルールを無効化する。
【0041】
このようにして、DELETE処理が実行される。結果出力ブロック5は、複数のルール比較ブロック2−1〜2−Nから処理結果を受け取り、DELETE処理の最終結果を示す出力データ7を出力する。
【0042】
<グループ選択処理>
上述の通り、本実施の形態によれば、コマンド入力ブロック4は、入力コマンドを、複数のルール比較ブロック2−1〜2−Nのうち必要なもの(選択ルール比較ブロック)だけに入力する。図5を参照して、この処理について説明する。
【0043】
本実施の形態によれば、複数のルール比較ブロック2−1〜2−Nは、複数のグループにグループ分けされる。ここで、グループ分けの基準は、ルールを管理するために着目するパケットヘッダフィールドの組み合わせの種類である。より具体的に、例えば、各ルール比較ブロック2が決定木によって構成されている場合、それぞれのルール比較ブロック2を構成する決定木の領域分割に用いているヘッダフィールドの組み合わせの種類である。また、それ以外に、ワイルドカードが含まれないパケットヘッダフィールドの組み合わせの種類でも良い。このような管理を行うことで、一般的にルールは全て同じパケットヘッダフィールドの組み合わせで定義されるが、異なる複数の組み合わせで定義されるルールを同一のパケット分類器で管理することも可能となる。
【0044】
例えば、Typeフィールドが0x0800(IP version4を意味する)の場合、ルールには、送信元MACアドレス、宛先MACアドレス、TypeといったLayer2(以下、L2)までのプロトコルに関するヘッダフィールドに加え、送信元IPアドレス、宛先IPアドレス、プロトコル番号等の上位レイヤのヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック2は、第1グループに分類される。図5の例では、第1グループは、ルール比較ブロック2−6〜2−Nを含んでいる。
【0045】
また、Typeフィールドが0x8100(IEEE 802.1Q VLANタグフレームを意味する)の場合、ルールには、送信元MACアドレス、宛先MACアドレス、TypeといったL2までのプロトコルに関するヘッダフィールドに加え、VLAN IDやVLAN PriorityといったVLANまでのヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック2は、第2グループに分類される。図5の例では、第2グループは、ルール比較ブロック2−4、2−5を含んでいる。
【0046】
また、Typeフィールドが上記のもの以外の場合、ルールには、送信元MACアドレス、宛先MACアドレス、TypeといったL2までのプロトコルに関するヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。この場合、この場合、このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック2は、第3グループに分類される。図5の例では、第3グループは、ルール比較ブロック2−1〜2−3を含んでいる。
【0047】
このように、複数のルール比較ブロック2−1〜2−Nは、ルールを管理するために着目するヘッダフィールドの組み合わせの種類に応じて、複数のグループにグループ分けされる。例えば、L2までのプロトコルに関するヘッダフィールド、送信元IPアドレス、宛先IPアドレス、プロトコル番号等の上位レイヤのヘッダフィールドで定義されたルールが、L2までのプロトコルに関するヘッダフィールドを用いて管理される場合、第3グループに分類される。同様に、例えば、L2までのプロトコルに関するヘッダフィールド、VLAN IDやVLAN PriorityといったVLANまでのヘッダフィールドで定義されたルールが、L2までのプロトコルに関するヘッダフィールドを用いて管理される場合も、第3グループに分類される。このような複数のグループのうち入力コマンドが入力されるべきグループは、「選択グループ」である。LOOKUP処理の場合、選択グループは、検索キーにマッチするルールを管理している可能性があるグループである。INSERT処理の場合、選択グループは、新規ルールを管理する可能性があるグループである。DELETE処理の場合、削除対象の既存ルールを管理している可能性があるグループである。
【0048】
本実施の形態によれば、コマンド入力ブロック4は、選択グループに属するルール比較ブロック2(以下、「選択ルール比較ブロック2」と参照される)にだけ入力コマンドを入力し、それ以外のルール比較ブロック2には入力コマンドを入力しない。従って、入力コマンドに応じた処理は、選択ルール比較ブロック2においてのみ実行されることになる。その結果、パケット分類器1における不要な電力消費が削減される。
【0049】
尚、コマンド入力ブロック4は、複数のグループのうちどれが選択グループかを、検索キーやルール(新規ルール、削除ルール)を参照することによって判定可能である。例えば、MACヘッダに含まれるTypeフィールドや、IPヘッダに含まれるプロトコルフィールド等、パケットの構成が判断できるヘッダフィールドに基づいて、選択グループを識別することができる。図5で示された例では、MACヘッダに含まれるTypeフィールドがグループ毎に異なっている。従って、コマンド入力ブロック4は、検索キーあるいはルールから抽出されるTypeフィールドを「識別情報」として用いることによって、選択グループを識別することができる。
【0050】
例えば、図5で示された例において、検索キーのTypeフィールドが0x8100である場合、選択グループは第2グループと第3グループであり、コマンド入力ブロック4は、選択ルール比較ブロック2−1〜2−5だけに検索コマンドを入力する。検索キーのTypeフィールドが0x0800である場合、選択グループは第1グループと第3グループであり、コマンド入力ブロック4は、選択ルール比較ブロック2−1〜2−3、2−6〜2−Nだけに検索コマンドを入力する。検索キーのTypeフィールドがそれ以外の場合、選択グループは第3グループであり、コマンド入力ブロック4は、選択ルール比較ブロック2−1〜2−3だけに検索コマンドを入力する。
【0051】
以上に説明されたように、本実施の形態によれば、コマンド入力ブロック4は、検索キーやルール(新規ルール、削除ルール)を参照することによって、選択グループを識別する。そして、コマンド入力ブロック4は、選択グループに属する選択ルール比較ブロック2にだけ入力コマンドを入力し、それ以外のルール比較ブロック2には入力コマンドを入力しない。従って、入力コマンドに応じた処理は、選択ルール比較ブロック2においてのみ実行されることになる。その結果、パケット分類器1における不要なメモリアクセスの発生が未然に防止され、消費電力が削減される。
【0052】
なお、本実施の形態に係るパケット分類器1は、例えば、スイッチやルータ等のネットワーク装置内や、サーバの拡張カードやオンボードで搭載されるNIC(Network Interface Card)内に配備される。この場合、パケット分類器1は、制御ブロックと接続される。その制御ブロックは、到着したパケットのヘッダを解析する機能、当該パケットヘッダから検索キーを抽出する機能、その検索キーを用いたLOOKUP処理をパケット分類器1に実行させる機能を有する。更に、制御ブロックは、外部から指定される新規ルールを追加するINSERT処理をパケット分類器1に実行させる機能、及び外部から指定される既存ルールを削除するDELETE処理をパケット分類器1に実行させる機能を有する。パケット分類器1は、処理に応じた入力データ6を制御ブロックから受け取り、出力データ7を制御ブロックに出力する。
【0053】
1−2.第1の構成例
次に、本実施の形態に係るパケット分類器1の構成例を更に詳しく説明する。上記のルールの管理ができれば、ルール比較ブロック2はどのようなルール管理機構、及び検索処理を実行しても良い。以下では、典型的な例として、各ルール比較ブロック2が決定木を用いて実現される場合の構成を説明する。
【0054】
図6は、本実施の形態に係るパケット分類器1の各ルール比較ブロック2の構成を示すブロック図である。以下では、この場合のルール比較ブロックを決定木処理ブロックとも参照する。図6に示されるように、決定木処理ブロック2は、決定木パイプラインブロック20、エントリ数カウントブロック21、及びルールパイプラインブロック22を備えている。コマンド入力ブロック4から決定木処理ブロック2に入力されるデータは、入力データ23である。決定木処理ブロック2から結果出力ブロック5に出力されるデータは、出力データ24である。決定木処理ブロック2とエントリ追加対象決定ブロック3との間でやりとりされるデータは、入出力データ25である。
【0055】
決定木パイプラインブロック20は、パイプライン処理により決定木の探索を行う。具体的には、決定木パイプラインブロック20は、決定木の深さ(段数)Hと同じ段数の決定木ノード処理ブロック200−1〜200−Hを備えている。図7に示されるように、決定木ノード処理ブロック200−i(i=1、2、・・・、H)は、決定木の根ノードから深さj(j=0、1、・・・、H−1)のノードに対応しており、当該ノードに関する処理を行う。これら決定木ノード処理ブロック200−1〜200−Hを用いることによって、決定木パイプラインブロック20は、決定木の根ノードから葉ノードに向けて1ノードずつ探索処理を実行していく。好適には、1クロックサイクル毎に、決定木の1つのノードを辿る処理が実行される。
【0056】
図8は、本実施の形態に係る決定木ノード処理ブロック200の構成を示すブロック図である。図8に示されるように、決定木ノード処理ブロック200は、子ノード決定ブロック2000及びノード情報記憶ブロック2001を備えている。
【0057】
ノード情報記憶ブロック2001は、メモリやレジスタ等の記憶媒体により構成され、ノード情報を記憶する。ノード情報は、根ノードから見て同じ深さにある全てのノードの各々に関して、当該ノードにおける領域分割情報、つまり当該ノードによって管理される子ノード(分割領域)に対する情報を示す。
【0058】
決定木ノード処理ブロック200は、前段の決定木ノード処理ブロック200から入力データ2002を受け取る。但し、決定木ノード処理ブロック200−1は、コマンド入力ブロック4から入力データ2002(=入力データ23)を受け取る。入力データ2002は、各処理に応じたコマンドと、ノード情報記憶ブロック2001へのアクセスに用いられるアドレス値を含んでいる。前段の決定木ノード処理ブロック200からの入力データ2002は、更に、後述される「有効ビット長」の情報も含んでいる。
【0059】
子ノード決定ブロック2000は、入力データ2002を受け取り、その入力データ2002で指定されているアドレス値を参照してノード情報記憶ブロック2001からノード情報を読み出す。そして、子ノード決定ブロック2000は、ノード情報、有効ビット長及びコマンドに基づいて、当該ノードの子ノードのノード情報が記憶されているアドレス値を算出する。また、子ノード決定ブロック2000は、有効ビット長を更新する。アドレス値の算出や有効ビット長の更新に関しては、後に詳しく説明される。出力データ2003は、入力データ2002に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。子ノード決定ブロック2000は、その出力データ2003を、次段の決定木ノード処理ブロック200に出力する。
【0060】
最終段の決定木ノード処理ブロック200−Hに関しては、次の通りである。LOOKUP処理あるいはDELETE処理の場合、子ノード決定ブロック2000によって算出されるアドレス値は、ルールパイプラインブロック22のルール処理ブロック220のエントリ記憶ブロック2201(後述される)へのアクセスに用いられるアドレス値である。決定木ノード処理ブロック200−Hは、出力データ2003をルール処理ブロック220−1に出力する。また、INSERT処理の場合、子ノード決定ブロック2000によって算出されるアドレス値は、エントリ数カウントブロック21のエントリ数記憶ブロック211(後述される)へのアクセスに用いられるアドレス値である。出力データ2004は、入力データ2002に含まれていたコマンドと算出されたアドレス値を含む。子ノード決定ブロック2000は、その出力データ2004を、エントリ数カウントブロック21に出力する。
【0061】
エントリ数カウントブロック21は、決定木の全ての葉ノードに関して、管理されている有効なルールのエントリ数を葉ノード毎に管理する。尚、エントリ数カウントブロック21による処理は、決定木の深さHに相当する処理サイクルにおいて実行される。
【0062】
図9は、本実施の形態に係るエントリ数カウントブロック21の構成を示すブロック図である。図9に示されるように、エントリ数カウントブロック21は、カウント処理ブロック210及びエントリ数記憶ブロック211を備えている。
【0063】
エントリ数記憶ブロック211は、メモリやレジスタ等の記憶媒体により構成され、エントリ数情報を記憶する。エントリ数情報は、決定木の各葉ノードによって管理されている有効なルールのエントリ数を示す。
【0064】
INSERT処理の場合、カウント処理ブロック210は、決定木パイプラインブロック20の決定木ノード処理ブロック200−Hから入力データ212(=上述の出力データ2004)を受け取る。その入力データ212は、挿入コマンド、及びエントリ数記憶ブロック211へのアクセスに用いられるアドレス値を含む。カウント処理ブロック210は、そのアドレス値を参照して、エントリ数記憶ブロック211から追加対象葉ノードに関するエントリ数情報(有効エントリ数)を読み出す。そして、カウント処理ブロック210は、読み出した有効エントリ数を示す出力データ216を、上述のエントリ追加対象決定ブロック3に出力する。
【0065】
また、カウント処理ブロック210は、エントリ追加対象決定ブロック3から入力データ216を受け取る。その入力データ216が「決定木への新規ルールの追加」を指定している場合、カウント処理ブロック210は、上記追加対象葉ノードに関する有効エントリ数に“1”を加算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。更に、カウント処理ブロック210は、出力データ214を、ルールパイプラインブロック22のルール処理ブロック220−1に出力する。その出力データ214は、挿入コマンドと、ルール処理ブロック220−1のエントリ記憶ブロック2201(後述される)へのアクセスに用いられるアドレス値を含む。
【0066】
DELETE処理の場合、カウント処理ブロック210は、ルールパイプラインブロック22のルール処理ブロック220−Bから入力データ213を受け取る。カウント処理ブロック210は、その入力データ213で指定されるアドレス値を参照して、エントリ数記憶ブロック211から削除対象葉ノードに関するエントリ数情報(有効エントリ数)を読み出す。そして、カウント処理ブロック210は、当該有効エントリ数から“1”を減算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。更に、カウント処理ブロック210は、DELETE処理の完了を示す出力データ215を、出力データ24として結果出力ブロック5に出力する。
【0067】
ルールパイプラインブロック22は、パイプライン制御によりルール処理(LOOKUP、INSERT、DELETE)を行う。具体的には、ルールパイプラインブロック22は、各葉ノードにおいて管理可能な最大ルール数(ルールリストのサイズ)Bと同じ段数のルール処理ブロック220−1〜220−Bを備えている。図10に示されるように、ルール処理ブロック220−i(i=1、2、・・・、B)は、当該葉ノードのルールリストに含まれるルールj(j=1、2・・・、B)に対応付けられており、当該ルールjに関するルール処理を実行する。これらルール処理ブロック220−1〜220−Bを用いることによって、ルールパイプラインブロック22は、葉ノードのルールリストに含まれる各ルールに対してルール処理を実行する。好適には、1クロックサイクル毎に、1つのルールに対するルール処理が実行される。
【0068】
図11は、本実施の形態に係るルール処理ブロック220の構成を示すブロック図である。図11に示されるように、ルール処理ブロック220は、比較更新処理ブロック2200及びエントリ記憶ブロック2201を備えている。
【0069】
エントリ記憶ブロック2201は、メモリやレジスタ等の記憶媒体により構成され、エントリ情報を記憶する。エントリ情報は、当該ルールが有効か無効かを示す有効フラグ、ルールID、ルール等を含む。
【0070】
LOOKUP処理あるいはDELETE処理の場合、ルール処理ブロック220−1は、決定木パイプラインブロック20の決定木ノード処理ブロック200−Hから入力データ2202(=上述の出力データ2003)を受け取る。入力データ2202は、各処理に応じたコマンドと、エントリ記憶ブロック2201へのアクセスに用いられるアドレス値を含んでいる。
【0071】
INSERT処理の場合、ルール処理ブロック220−1は、エントリ数カウントブロック21から入力データ2203(=上述の出力データ214)を受け取る。入力データ2203は、挿入コマンドと、エントリ記憶ブロック2201へのアクセスに用いられるアドレス値を含んでいる。入力データ2203は、これ以降、上記入力データ2202と同様に扱われる。
【0072】
比較更新処理ブロック2200は、入力データ2202を受け取り、その入力データ2202で指定されているアドレス値を参照してエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、読み出したエントリ情報に基づいて、コマンドに応じたルール処理を実行する。ルール処理の詳細は後述される。また、比較更新処理ブロック2200は、受け取った入力データ2202を出力データ2204として、次段のルール処理ブロック220に出力する。
【0073】
ルール処理ブロック220−2〜220−Bの各々は、前段のルール処理ブロック220から入力データ2202(=上述の出力データ2204)を受け取る。比較更新処理ブロック2200による処理は、上記と同じである。尚、DELETE処理の場合、最終段のルール処理ブロック220−Bの比較更新処理ブロック2200は、出力データ2204の代わりに出力データ2205(=上述の入力データ213)をエントリ数カウントブロック21に出力する。出力データ2205の内容は、出力データ2204と同じである。
【0074】
図12は、本実施の形態に係るパケット分類器1のコマンド入力ブロック4の構成を示すブロック図である。図12に示されるように、コマンド入力ブロック4は、出力先分析ブロック40、コマンド出力情報記憶ブロック41、コマンド出力ブロック42、及びルール比較ブロック2−1〜2−Nのそれぞれへ入力コマンドを出力するための出力43−1〜43−Nを備えている。
【0075】
コマンド出力情報記憶ブロック41は、「識別情報」と「選択ルール比較ブロック」との対応関係を示すコマンド出力情報を保持している。図13は、そのコマンド出力情報の一例を概念的に示している。「識別情報」は、例えば、MACヘッダのTypeフィールドである。出力先データはNビットデータ(N=ルール比較ブロック2−1〜2−Nの数)であり、それぞれのビットがルール比較ブロック2−1〜2−Nと対応付けられている。ビット値が‘0’であれば、当該ルール比較ブロック2は選択ルール比較ブロックではない。一方、ビット値が‘1’であれば、当該ルール比較ブロック2は選択ルール比較ブロックである。つまり、「選択ルール比較ブロック」は、Nビットの出力先データの中のビット‘1’で表されている。なお、INSERT処理時の新規ルールや、DELETE処理時の削除ルール等では、ルールの定義上、Typeフィールドといったヘッダフィールドがワイルドカードで定義されていたりする場合がある。その場合には、全てのルール比較ブロック2が選択ルール比較ブロックとなる。
【0076】
出力先分析ブロック40は、外部からパケット分類器1に入力された上述の入力データ6を受け取る。出力先分析ブロック40は、LOOKUPの場合は検索キー、INSERTの場合は新規ルール、DELETEの場合は削除ルールから、「識別情報」を抽出する。この識別情報は、例えば、MACヘッダのTypeフィールドである。そして、出力先分析ブロック40は、抽出された識別情報とコマンド出力情報(図13)を参照することによって、選択ルール比較ブロック2を認識する。出力先分析ブロック40は、コマンドと当該処理で用いるデータ、及びコマンド出力先の情報をコマンド出力ブロック42に出力する。
【0077】
コマンド出力ブロック42は、受け取ったコマンド情報に、内部処理で用いるフラグ等のデータを付与したものを、装置内コマンドとする。そして、コマンド出力ブロック42は、コマンド出力先の情報に従って、その装置内コマンドを選択ルール比較ブロック2に出力する。この際、コマンド出力ブロック42は、コマンド情報とそのコマンド情報が有効であるかを示すイネーブル信号を各ルール比較ブロック2に出力する方法が考えられる。この場合、コマンド出力ブロック42は、全てのルール比較ブロック2にコマンド情報を出力しながら、コマンド出力情報記憶ブロック41から読み出した出力先データの各ビットを、各ルール比較ブロック2に対するイネーブル信号として利用することもできる。
【0078】
図14は、装置内コマンドの構成例を示す概念図である。コマンド部分は、処理種別、終了フラグ、及び結果フラグを含んでいる。例えば、2ビットデータである処理種別は、“00”であればLOOKUP処理、“01”であればINSERT処理、“10”であればDELETE処理を示す。終了フラグは、‘0’であれば未終了、‘1’であれば終了を示す。結果フラグは、エントリの追加、削除を行った場合に、‘1’に設定される。尚、終了フラグと結果フラグについては、INSERT処理及びDELETE処理においてのみ参照され、それらの利用方法については後述する。また、装置内コマンドの後半部分には、検索キー(LOOKUP処理)、追加される新規エントリ(INSERT処理)、あるいは、削除される既存エントリ(DELETE処理)が格納される。なお、装置内コマンドの構成例はこれに限定されることはない。特に、終了フラグや結果フラグといった内部処理用のデータのビット幅をより多く用いることで、内部の処理状況を柔軟に把握することが可能となる。
【0079】
ここで、上記新規エントリや削除エントリ等のエントリ(ルール)は、Prefix Match、Range Match、Wildcard Matchを考慮すると様々な表現形態が考えられる。例えば、検索キー長と同じ長さのデータ列A、Bを用意し、Prefix MatchやWildcard Matchの場合には、Aに対象データ、Bにマスクビットデータを割り当て、Range Matchの場合には、Aに下限値、Bに上限値を割り当てる方法が考えられる。この場合、ルールのエントリ長は検索キー長の2倍となる。これらを考慮し、装置内コマンドの後半部分においては、LOOKUP処理時の検索キーと、INSERT、DELETE処理時の追加・削除エントリの長さが異なることを許容する。なお、追加エントリの場合には、その優先度も指定される。
【0080】
次に、本実施の形態に係るパケット分類器1の動作を詳しく説明する。
【0081】
<LOOKUP処理>
まず、LOOKUP処理を説明する。図15は、本実施の形態におけるLOOKUP処理を示すフローチャートである。
【0082】
ステップA1:
パケット分類器1に、入力データ6が入力される。その入力データ6は、LOOKUP処理を示す種別データと、被検索対象パケットから抽出された検索キーとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて、上述したように選択ルール比較ブロック2を決定し、装置内コマンド(ここでは、検索コマンド)を生成する。そして、コマンド入力ブロック4は、生成した装置内コマンドを、選択ルール比較ブロック2に対して一斉に出力する。
【0083】
ステップA2:
コマンド入力ブロック4から検索コマンドを受け取ると、ルール比較ブロック2は、ルール一致比較処理を実行する。具体的に、ルール比較ブロック2が決定木で実現された決定木処理ブロック2の場合、図16に示すルール一致比較処理を行う。図16は、決定木処理ブロック2におけるステップA2の処理を示すフローチャートである。
【0084】
ステップB1:
決定木処理ブロック2は、ルール一致比較処理として、指定された検索キーを用いて、自身の決定木を辿る処理を実行する。図17は、ステップB1の処理を示すフローチャートである。
【0085】
ステップC1:
決定木を辿る処理は、決定木の根ノードから開始する。そのため、まず、現在の処理ノードが、決定木の根ノードに設定される。具体的には、挿入コマンドが、決定木パイプラインブロック20の初段の決定木ノード処理ブロック200−1に入力される。
【0086】
ステップC2:
子ノード決定ブロック2000は、処理種別がLOOKUPであることを確認した上で、ノード情報記憶ブロック2001からノード情報を読み出す。
【0087】
図18は、ノード情報の構成例を示す概念図である。ノード情報は、当該ノードにおける領域分割情報である。図18に示されるように、ノード情報は、フィールド識別子(フィールドID)とその分割数(k)のC個のペア、及びベースアドレスを含んでいる。ここで、Cは決定木の1ノードにおける領域分割に用いることができるフィールドの最大数である。フィールドIDは、検索キーやルールを構成するフィールド毎に予め決められている。また、各フィールドの範囲は、2分割されるとし(kは自然数)、分割数kはその指数を表す。例えば、既出の図1〜図3の例のように、フィールドX、Yの各々の範囲が2分割される場合、フィールドXの分割数kは1であり、フィールドYの分割数kも1である。尚、kの最大数は予め決められている。ベースアドレスは、当該ノードの子ノードのノード情報が格納されている記憶領域の最小アドレス値を示す。より詳細には、ベースアドレスは、当該ノードの子ノードのノード情報が格納されている次段の決定木ノード処理ブロック200のノード情報記憶ブロック2001における最小アドレス値であり、当該ノードの全ての子ノードのノード情報は、このベースアドレスから連続する記憶領域に格納されている。
【0088】
ステップC3:
子ノード決定ブロック2000は、読み出したノード情報、検索キーの各フィールドのビット列、及び有効ビット長に基づいて、次段の子ノードのノード情報が格納されている記憶領域のアドレス値を算出する。具体的には、次のようにして次段のアドレス値は算出される(図19も参照されたい)。
【0089】
例えば、ノード情報として、2つのフィールドに関する分割情報(フィールドID、分割数)=(0001、01)、(0100、11)とベースアドレス=00001000が設定されているとする。検索キーにおいては、フィールドID=0001のフィールド値が“0101”、フィールドID=0100のフィールド値が“0110”であり、それぞれの有効ビット長が3、4であったとする。ここで、有効ビット長とは、各フィールドのビット列に対し、領域分割に用いる下位ビットからの長さに相当する。つまり、フィールド値のうち、有効ビット長で指定された長さをもつ下位ビットからのビット列が参照される。フィールドID=0001に関して説明する。有効ビット長が3であることから、フィールド値の下位3ビット“101”を参照する。そして、分割数k=1であるため、有効ビットの上位1ビットを参照し、‘1’を得る(図19参照)。同様に、フィールドID=0100に関しては、有効ビット長が4、分割数kが3であることから、“011”を得る。これらを連結した“1011”に対して、ベースアドレス“00001000”が加算される。その結果得られる“00010011”が、次段の子ノードのノード情報が格納されている記憶領域のアドレス値である。
【0090】
ステップC4:
続いて、子ノード決定ブロック2000は、入力された有効ビット長から分割数kを減算することによって、有効ビット長を更新する。上記の例では、フィールドID=0001の有効ビット長が3−1=2に、フィールドID=0100の有効ビット長が4−3=1に更新される。尚、決定木ノード処理ブロック200−1には有効ビット長が入力されないが、その場合の有効ビット長は、予め各フィールドのフィールド長として設定されているものとする。それ以降の決定木ノード処理ブロック200に対しては、前段の決定木ノード処理ブロック200から有効ビット長が入力される。
【0091】
ステップC5、C6:
次に、子ノードが葉ノードであるか否かが判定される。具体的には、決定木ノード処理ブロック200−Hが処理するノードの子ノードが葉ノードであるため(図7参照)、処理する決定木ノード処理ブロック200が自動的に判別すればよい。
【0092】
次ノードが葉ノードではない場合(ステップC5;No)は、決定木ノード処理ブロック200−i(i=1、2、・・・、H−1)の場合に相当する。その決定木ノード処理ブロック200−iは、次段の決定木ノード処理ブロック200−(i+1)に出力データ2003を出力する(ステップC6)。その出力データ2003は、入力データ2002に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。そして、処理はステップC2に戻り、次段のノードが処理ノードとなる。
【0093】
次ノードが葉ノードである場合(ステップC5;Yes)は、決定木ノード処理ブロック200−Hの場合に相当する。この場合、ステップB1が終了する。
【0094】
ステップB2:
ステップB1が終了すると、決定木ノード処理ブロック200−Hは、ルールパイプラインブロック22のルール処理ブロック220−1に、算出したアドレス値とコマンドを含む出力データ2003を出力する。
【0095】
ステップB3:
続いて、ルールパイプラインブロック22が、検索キーとルールリスト中の各ルールとの比較(マッチング処理)を行う。図20は、ステップB3の処理を示すフローチャートである。
【0096】
ステップD1:
マッチング処理は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220−1から処理を開始する。
【0097】
ステップD2:
比較更新処理ブロック2200は、処理種別がLOOKUPであることを確認した上で、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。
【0098】
図21は、エントリ情報の構成例を示す概念図である。エントリ情報は、当該ルールが有効であるかを示す有効フラグ、ルールID、ルール、優先度を含んでいる。ルールに対応するアクションを同時に記憶する場合には、アクションを加えても良い。ここでは、アクションは本パケット分類器1とは異なる場所で管理されており、本パケット分類器1によって検索を行った後に、当該ルールIDを用いることによりアクションが取得されるとする。なお、図21のエントリ情報の構成例では、ルールIDを含んでいるが、これをエントリ情報には含まず、例えば、処理を行った決定木処理ブロックのID、葉ノードのID、ルールリストの順序等からルールIDを生成しても良い。より具体的には、処理を行った決定木処理ブロック2−i(i=1、2、・・・、N)のi、決定木処理ブロック2−iで辿り着いた葉ノードのIDであるj、ルール処理ブロック220−k(k=1、2、・・・、B)のkを2進数で連結したものをルールIDとして参照することが可能である。
【0099】
ステップD3、D4:
ルールが有効である場合(ステップD3;Yes)、比較更新処理ブロック2200は、検索キーと読み出したルールとの比較を行う。この比較方法については、例えば、非特許文献2に開示されている。
【0100】
ステップD5、D6:
検索キーがルールにマッチした場合(ステップD5;Yes)、比較更新処理ブロック2200は、当該ルールの優先度と現在のマッチルールの優先度を比較する。ここで、現在のマッチルールとは、前段のルール処理ブロック220までにマッチしたルールのうち、最も優先度が高いルールを意味する。一方、現在のルール処理ブロック220において比較に用いられたルールは、比較ルールと参照される。
【0101】
ステップD7、D8:
比較ルールの優先度の方が大きかった場合(ステップD7;Yes)、比較更新処理ブロック2200は、比較ルールを新たな現在のマッチルールに設定する。その後、処理は、ステップD9に進む。
【0102】
ステップD9、D10、D11:
現在のルールが、ルールリスト中の最後のルールか否かが判定される。具体的には、ルール処理ブロック220−i(i=1、2、・・・、B−1)が処理を実行している場合、それは最後のルールではない(ステップD9;No)。この場合、そのルール処理ブロック220−iは、次段のルール処理ブロック220−(i+1)に、アドレス値とコマンドを含む出力データ2204を出力する(ステップD10)。そして、処理はステップD2に戻り、ルールリスト中の次のルールに対するマッチング処理が実行される。
【0103】
尚、読み出したルールが有効で無い場合(ステップD3;No)、及び、検索キーがルールにマッチしない場合(ステップD5;No)、更に、比較ルールの優先度がマッチルールの優先度よりも小さかった場合(ステップD7;No)にも、処理はステップD9に進む。
【0104】
現在のルールがルールリスト中の最後のルールである場合、つまり、処理がルール処理ブロック220−Bで行われた場合(ステップD9;Yes)、ルール処理ブロック220−Bは、マッチルールのルールIDと優先度、及びコマンドを、結果出力ブロック5に出力する(ステップD11)。そして、ステップB3が終了する。なお、マッチルールが存在しない場合には、マッチルールが存在しなかったことを示す信号を出力するが、例えば、ルールIDのビット値が全て1であるような特値を出力することで、マッチルールが存在しなかったことを示すこともできる。
【0105】
ステップA3:
結果出力ブロック5は、複数の決定木処理ブロック2−1〜2−Nから検索結果を受け取る。結果出力ブロック5は、マッチルールの優先度同士を比較し、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック5は、その選択結果を示す出力データ7として、例えば、最高優先度であったマッチルールのルールIDを、LOOKUP処理の最終結果として出力する。このとき、マッチルールが存在しなかった場合には、上述した特値のルールIDを出力することで、マッチルールが存在しなかったことを示すことができる。
【0106】
<INSERT処理>
次に、INSERT処理を説明する。図22は、本実施の形態におけるINSERT処理を示すフローチャートである。
【0107】
ステップA1:
パケット分類器1に、入力データ6が入力される。その入力データ6は、INSERT処理を示す種別データと、追加される新規ルールとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて、上述したように選択ルール比較ブロック2を決定し、装置内コマンド(ここでは、検索コマンド)を生成する。そして、コマンド入力ブロック4は、生成した装置内コマンドを、選択ルール比較ブロック2に対して一斉に出力する。
【0108】
ステップA4:
コマンド入力ブロック4から検索コマンドを受け取ると、ルール比較ブロック2は、当該ブロックにおいてルールの複製が発生するかを確認する。具体的には、ルール比較ブロック2が決定木で実現された決定木処理ブロック2の場合、図23に示すルールの複製有無確認処理を行う。図23は、決定木処理ブロック2におけるステップA4の処理を示すフローチャートである。
【0109】
ステップB4:
コマンド入力ブロック4から挿入コマンドを受け取ると、決定木処理ブロック2は、指定された新規ルールを用いて、自身の決定木を辿る処理を実行する。図24は、ステップB4の処理を示すフローチャートである。
【0110】
ステップC1:
まず、LOOKUP処理の場合と同様に、現在の処理ノードが、決定木の根ノードに設定される。
【0111】
ステップC7:
子ノード決定ブロック2000は、処理種別がINSERTであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合(ステップC7;Yes)、処理はステップC5に進む。一方、終了フラグが‘0’である場合(ステップC7;No)、処理はステップC2に進む。
【0112】
ステップC2:
LOOKUP処理の場合と同様に、子ノード決定ブロック2000は、ノード情報記憶ブロック2001からノード情報を読み出す。
【0113】
ステップC8:
子ノード決定ブロック2000は、読み出したノード情報、新規ルールの各フィールドのビット列、及び有効ビット長に基づいて、ルールの複製が発生するか否か判定する。ルールの複製が発生するか否かは、アドレス値の算出を行う際に、ワイルドカードが含まれるか否かで判断することができる。
【0114】
例えば、ノード情報として、2つのフィールドに対する領域分割情報(フィールドID、分割数)=(0001、01)、(0100、11)とベースアドレス=00001000が設定されていたとする。追加対象ルールにおいては、フィールドID=0001、フィールドID=0100の各フィールドに対して、(フィールド値、マスクビット列)が、(“0101”、“1111”)、(“0110”、“1111”)のように設定されており、それぞれの有効ビット長が3、4であったとする。なお、マスクビット列は各ビットが‘1’であれば有効、‘0’であれば無効、つまり、ワイルドカードとして扱うものとする。この場合、両フィールドともに、ワイルドカードは含まれていないため、ルールの複製は発生しないことが分かり、LOOKUP時のステップC3と同様に、次の子ノードのアドレス値を算出することができる。一方、同様のノード情報、有効ビット長に対して、追加対象ルールにおけるフィールドID=0001、フィールドID=0100の各フィールドの(フィールド値、マスクビット列)が、(“0101”、“1111”)、(“0110”、“1100”)のように設定されている場合を考える。この場合、マスクビット列を考慮すると、各フィールド値はそれぞれ、“0101”、“01**”となる。ノード情報を元に子ノードのアドレス値を算出しようとすると、それぞれの有効ビット長が3、4であることから、フィールドID=0001に対して、下位3ビット“101”の上位1ビットを参照し、‘1’を得る。一方、フィールドID=0100のフィールドに対しては、有効ビット長が4、分割数が3であることから、“01*”を得る。この結果、子ノードの分割領域を示すビット列にワイルドカードが含まれ、これは、ルールの複製が発生することを意味する。なお、フィールド値がRange Matchとして設定されている場合、下限値と上限値の有効ビット長に相当するビット列に対し、参照するビット列が共に同じ値であるか否かで判断できる。例えば、上記の例において、フィールドID=0001が下限値0000、上限値0011として設定されていたとする。有効ビット長が3であることから、下限値、上限値の下位3ビットの“000”と“011”を参照する。分割数が1であることから、各有効ビット長の先頭ビットを参照し、共に‘0’であることから、領域分割を行ってもルールの複製が発生しないと判断できる。一方、フィールドID=0001が下限値0000、上限値0111が設定されている場合には、参照ビットが‘0’と‘1’であるため、ルールの複製が発生すると判断できる。
【0115】
ステップC9、C10:
ルールの複製が発生する場合(ステップC9;Yes)、当該決定木処理ブロック2は、エントリ追加対象候補とはならない。この場合、子ノード決定ブロック2000は、コマンドの終了フラグを‘1’に設定する。その後、処理はステップC5に進む。
【0116】
ステップC3、C4:
一方、ルールの複製が発生しない場合(ステップC9;No)、LOOKUP処理の場合と同様に、次段のアドレス値の算出(ステップC3)及び有効ビット長の更新(ステップC4)が行われる。その後、処理はステップC5に進む。
【0117】
ステップC5、C6:
LOOKUP処理の場合と同様に、ステップC5、C6が実施される。つまり、次ノードが葉ノードではない場合(ステップC5;No)は、決定木ノード処理ブロック200−i(i=1、2、・・・、H−1)は、次段の決定木ノード処理ブロック200−(i+1)に出力データ2003を出力する(ステップC6)。そして、処理はステップC7に戻り、次段のノードが処理ノードとなる。一方、次ノードが葉ノードである場合(ステップC5;Yes)は、ステップB4が終了する。
【0118】
ステップB5:
ステップB4が終了すると、決定木ノード処理ブロック200−Hは、算出したアドレス値とコマンドを含む出力データ2004を、エントリ数カウントブロック21に出力する。
【0119】
ステップB6:
エントリ数カウントブロック21のカウント処理ブロック210は、決定木ノード処理ブロック200−Hから入力データ212(=上述の出力データ2004)を受け取る。カウント処理ブロック210は、処理種別がINSERTであることを確認した上で、終了フラグを参照する。終了フラグが‘0’の場合、当該決定木処理ブロック2は、エントリ追加対象候補である。この場合、カウント処理ブロック210は、入力されたアドレス値を用いて、エントリ数記憶ブロック211から追加対象葉ノードに関するエントリ数情報(有効エントリ数)を読み出す。そして、カウント処理ブロック210は、読み出した有効エントリ数を示す出力データ216を、エントリ追加対象決定ブロック3に出力する。
【0120】
一方、終了フラグが‘1’の場合、当該決定木処理ブロック2は、エントリ追加対象候補ではない。この場合、カウント処理ブロック210は、処理終了信号をエントリ追加対象決定ブロック3に出力する。あるいは、カウント処理ブロック210は、有効エントリ数を最大値に設定し、その有効エントリ数をエントリ追加対象決定ブロック3に通知してもよい。
【0121】
ステップA5:
エントリ追加対象決定ブロック3は、決定木処理ブロック2から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図25は、ステップA5の処理を示すフローチャートである。
【0122】
ステップE1、E2、E3:
エントリ追加対象決定ブロック3は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る(ステップE1)。次に、エントリ追加対象決定ブロック3は、有効エントリ数がルールリストの最大数B(リストサイズ)を下回っているものがあるか否か確認する(ステップE2)。有効エントリ数がリストサイズを下回っているものが無い場合(ステップE2;No)、エントリ追加対象決定ブロック3は、エントリ追加対象は存在しないと判断する(ステップE3)。
【0123】
ステップE4、E5:
一方、有効エントリ数がリストサイズを下回っているものがある場合(ステップE2;Yes)、エントリ追加対象決定ブロック3は、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する(ステップE4)。その後、エントリ追加対象決定ブロック3は、各決定木処理ブロック2にエントリ追加の可否を通知する(ステップE5)。例えば、エントリ追加対象決定ブロック3は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック2に対してルール追加処理の不実行を指示する。なお、ここでは有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。
【0124】
ステップA6:
エントリ追加対象である決定木処理ブロック2のエントリ数カウントブロック21は、追加対象葉ノードに関する有効エントリ数に“1”を加算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。それ以外の決定木処理ブロック2のエントリ数カウントブロック21は、コマンドの終了フラグを‘1’に設定する。
【0125】
ステップA7:
続いて、ルールパイプラインブロック22は、ルールの追加処理を行う。図26は、ステップA7の処理を示すフローチャートである。
【0126】
ステップD12:
各決定木処理ブロック2のエントリ数カウントブロック21は、アドレス値と挿入コマンドを含む出力データ214を、ルールパイプラインブロック22のルール処理ブロック220−1に出力する。
【0127】
ステップD13:
ルールの追加処理は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220−1から処理を開始する。
【0128】
ステップD14:
比較更新処理ブロック2200は、処理種別がINSERTであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合(ステップD14;Yes)、処理はステップD9に進む。一方、終了フラグが‘0’である場合(ステップD14;No)、処理はステップD2に進む。
【0129】
ステップD2:
LOOKUP処理の場合と同様に、比較更新処理ブロック2200は、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。
【0130】
ステップD3、D15:
ルールが有効ではない場合(ステップD3;No)、当該エントリ(すなわち、空きエントリ)に新規ルールを書き込むことができる。この場合、比較更新処理ブロック2200は、エントリ情報中のルール情報を新規ルールのものに書き換え、且つ、有効フラグを‘1’に設定し、エントリ記憶ブロック2201に書き込む。さらに、比較更新処理ブロック2200は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’(追加成功)に設定する。その後、処理はステップD9に進む。
【0131】
ステップD16:
ルールが有効である場合(ステップD3;Yes)、当該エントリに新規ルールを書き込むことは許されない。この場合、そのルール処理ブロック220−iは、次段のルール処理ブロック220−(i+1)に、アドレス値とコマンドを含む出力データ2204を出力する。そして、処理はステップD14に戻り、ルールリスト中の次のルールに対する処理が実行される。
【0132】
ステップD9:
LOOKUP処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合(ステップD9;No)、処理は上記ステップD16に進む。一方、最後のルールの場合(ステップD9;Yes)、ルール処理ブロック220−Bは、現在のコマンドを、結果出力ブロック5に出力する(ステップD17)。そして、ステップA7が終了する。
【0133】
ステップA8:
結果出力ブロック5は、複数の決定木処理ブロック2−1〜2−Nからコマンドを受け取る。結果出力ブロック5は、受け取ったコマンド内の結果フラグを参照して、新規ルールが追加されたか、又は追加されなかったかを確認する。そして、結果出力ブロック5は、その結果を示す出力データ7を、INSERT処理の最終結果として出力する。
【0134】
ここで、INSERT処理の最終結果として、新規ルールを追加した箇所を示すエントリIDを出力することが挙げられる。エントリIDは、上述したエントリ情報にルールIDを含まない場合のルールID生成手法と同様、エントリ追加対象となった決定木処理ブロックのID、葉ノードのID、ルールリスト順序等からエントリIDを生成することができる。このとき、新規ルールを追加できる空き領域が無く、新規ルールを追加できなかった場合には、それを示す信号を出力することでルールの追加ができなかったことを示すことができるが、例えば、エントリIDを全て‘1’とした特値として出力することで、ルールの追加ができなかったことを示す信号を省くこともできる。また、INSERT処理では、各々1ビットから成る終了フラグと結果フラグを用いて処理を行ったが、終了フラグのビット幅を増やし、例えば、ルールの複製が発生したことが要因で処理を終了したことや、当該葉ノードのルールリストに空きが無かったことが要因で処理を終了したこと等、処理を終了した要因を表現させることができる。このような終了フラグを参照することで、INSERT処理の最終結果として、新規ルールを追加できなかった場合にその要因も最終結果として出力することができる。
【0135】
<DELETE処理>
次に、DELETE処理を説明する。図27は、本実施の形態におけるDELETE処理を示すフローチャートである。
【0136】
ステップA1:
パケット分類器1に、入力データ6が入力される。その入力データ6は、DELETE処理を示す種別データと、削除される既存ルールとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて、上述したように選択ルール比較ブロック2を決定し、装置内コマンド(ここでは、検索コマンド)を生成する。そして、コマンド入力ブロック4は、生成した装置内コマンドを、選択ルール比較ブロック2に対して一斉に出力する。
【0137】
ステップA9:
コマンド入力ブロック4から削除コマンドを受け取ると、各ルール比較ブロック2は、当該ブロックにおいてルールの複製が発生するかを確認する。具体的には、ルール比較ブロック2が決定木で実現された決定木処理ブロック2の場合、図28に示すルールの複製有無確認処理を行う。図28は、決定木処理ブロック2におけるステップA9の処理を示すフローチャートである。
【0138】
ステップB4:
INSERT処理時と同様、コマンド入力ブロック4から削除コマンドを受け取ると、決定木処理ブロック2は、指定された削除ルールを用いて、自身の決定木を辿る処理を実行する。
【0139】
ステップB7:
ステップB4が終了すると、決定木ノード処理ブロック200−Hは、ルールパイプラインブロック22のルール処理ブロック220−1に、算出したアドレス値とコマンドを含む出力データ2003を出力し、ステップA9を終了する。
【0140】
ステップA10:
ルールパイプラインブロック22は、ルールの削除処理を行う。図29は、ステップA10の処理を示すフローチャートである。
【0141】
ステップB8:
ルールパイプラインブロック22は、ルールの削除処理として、対象エントリの削除を行う。図30は、ステップB8の処理を示すフローチャートである。
【0142】
ステップD1:
ステップB8は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220−1から処理を開始する。
【0143】
ステップD18:
比較更新処理ブロック2200は、処理種別がDELETEであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合(ステップD18;Yes)、処理はステップD9に進む。一方、終了フラグが‘0’である場合(ステップD18;No)、処理はステップD2に進む。
【0144】
ステップD2、D3:
LOOKUP処理の場合と同様に、比較更新処理ブロック2200は、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。ルールが無効である場合(ステップD3:No)、当該エントリは削除対象ではない。この場合、処理はステップD9に進む。一方、ルールが有効である場合(ステップD3;Yes)、処理はステップD19に進む。
【0145】
ステップD19:
比較更新処理ブロック2200は、読み出したルールと、削除対象として指定されたルールとを比較する。つまり、比較更新処理ブロック2200は、削除対象として指定されているルールが、読み出したルールにマッチするか否かを判定する。ここでは、両者が完全に一致するか否かが判定される。不一致の場合(ステップD5;No)、処理はステップD9に進む。一方、完全一致の場合(ステップD5;Yes)、処理はステップD20に進む。
【0146】
ステップD20:
比較更新処理ブロック2200は、エントリ情報中の有効フラグを‘0’に設定し、エントリ記憶ブロック2201に書き込む。これにより、当該エントリ(ルール)は無効化される。この処理が既存ルールの削除に相当する。更に、比較更新処理ブロック2200は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’(削除成功)に設定する。その後、処理はステップD9に進む。
【0147】
ステップD9、D16:
LOOKUP処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合(ステップD9;No)、ルール処理ブロック220−iは、次段のルール処理ブロック220−(i+1)に、アドレス値とコマンドを含む出力データ2204を出力する(ステップD16)。そして、処理はステップD18に戻り、ルールリスト中の次のルールに対する処理が実行される。一方、現在のルールがルールリスト中の最後のルールである場合(ステップD9;Yes)、ステップB8は終了する。
【0148】
ステップB9:
ステップB8が完了すると、ルール処理ブロック220−Bは、アドレス値とコマンドを含む出力データ2205を、エントリ数カウントブロック21に出力する。
【0149】
ステップB10:
エントリ数カウントブロック21のカウント処理ブロック210は、ルール処理ブロック220−Bから入力データ213(=上述の出力データ2005)を受け取る。カウント処理ブロック210は、処理種別がDELETEであることを確認した上で、終了フラグ及び結果フラグを参照する。終了フラグ及び結果フラグが共に‘1’である場合、カウント処理ブロック210は、入力されたアドレス値を用いて、エントリ数記憶ブロック211から削除対象葉ノードに関するエントリ数情報(有効エントリ数)を読み出す。そして、カウント処理ブロック210は、当該有効エントリ数から1を減算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。
【0150】
ステップA11:
最後に、カウント処理ブロック210は、コマンドを含む出力データ215を結果出力ブロック5に出力する。結果出力ブロック5は、決定木処理ブロック2−1〜2−Nのそれぞれから受け取ったコマンド内の結果フラグを参照して、ルールが削除されたか、又は削除されなかったかを確認する。そして、結果出力ブロック5は、その結果を示す出力データ7を、DELETE処理の最終結果として出力する。
【0151】
ここで、DELETE処理の最終結果として、INSERT処理時の新規ルール追加箇所のエントリIDと同様、削除ルールを追加した箇所を示すエントリIDを出力することが挙げられる。この際、削除ルールが何らかの理由で管理ルールに存在しなかった場合には、削除ルールが存在しなかったことを示す信号や、エントリIDを全て‘1’とした特値として出力することで、削除ルールが存在しなかったことを示すことができる。
【0152】
1−3.第2の構成例
次に、本実施の形態に係るパケット分類器1の第2の構成例を説明する。第2の構成例では、各ルール比較ブロック2が、決定木ではなく、リスト形式でルールを管理する。それ以外の構成は第1の構成例と同じであり、重複する説明は適宜省略される。
【0153】
図31は、第2の構成例における各ルール比較ブロック2の構成を示すブロック図である。以下では、この場合のルール比較ブロック2をリニアサーチブロックとも参照する。図31に示されるように、リニアサーチブロック2は、エントリ数カウントブロック21及びルールパイプラインブロック22を備えている。つまり、リニアサーチブロック2は、図6で示された決定木処理ブロック2から決定木パイプラインブロック20が省かれた構成を有している。コマンド入力ブロック4からリニアサーチブロック2に入力されるデータは、入力データ23である。リニアサーチブロック2から結果出力ブロック5に出力されるデータは、出力データ24である。リニアサーチブロック2とエントリ追加対象決定ブロック3との間でやりとりされるデータは、入出力データ25である。
【0154】
エントリ数カウントブロック21の構成は、図9で示されたものと同一であるため詳細な説明を省略する。但し、エントリ数記憶ブロック211には、決定木の各葉ノードによって管理されている有効なルールのエントリ数ではなく、当該リニアサーチブロック2で管理されている有効なルールのエントリ数を保持している。ここで、後述するが、リニアサーチブロック2のルールパイプラインブロック22内の各ルール処理ブロック220は、1つのルールを保持する。従って、ルールリストはB個のルールをリスト(ルール処理ブロック220)で接続した構成になるため、このルールリストに含まれる有効なルールのエントリ数としては1つの値を保持すれば良い。なお、各ルール処理ブロック220において、複数のルールを管理することで、1つのリニアサーチブロック2で複数のルールリストを管理するように見せることも可能であるが、それらは1つのルールリストを管理するリニアサーチブロック2が複数存在する場合と何ら変わりない。このため、以降では、各リニアサーチブロック2は1つのルールリストのみを管理することを前提とする。
【0155】
ルールパイプラインブロック22の構成及びルール処理ブロック220の構成も、第1の構成例の場合と同じである。但し、上述したように、エントリ記憶ブロック2201では、1つのルールのみが管理される。
【0156】
上述したように、エントリ数カウントブロック21のエントリ数記憶ブロック211、及びルール処理ブロック220のエントリ記憶ブロック2201は、第1の構成例とは異なり、1つの有効エントリ数、及び1つのルールのみを管理できれば良い。このため、メモリで実現することも可能ではあるが、ワード数等の制約により記憶媒体が無駄になるような場合には、レジスタで実現することが望ましい。
【0157】
なお、本構成の場合も第1の構成例と同様に、例えば、MACヘッダのTypeフィールドの値によって、装置内コマンドの出力先を決定することになる。
【0158】
次に、本構成におけるパケット分類器1の動作について説明する。但し、以下では、第1の構成例における動作と異なる点のみを説明し、同じ動作を行う点については詳細な説明を省略する。
【0159】
<LOOKUP処理>
まず、LOOKUP処理を説明する。図32は、第2の構成例におけるLOOKUP処理を示すフローチャートである。図32を参照すると、第2の構成例におけるLOOKUP処理は、第1の構成例の動作におけるステップA2がステップA12に置き換わったものである。その他の動作は全て第1の構成例における動作と変わりないため、詳細な説明を省略する。
【0160】
ステップA12:
コマンド入力ブロック4から検索コマンドを受け取るとルール比較ブロック2は、ルール一致比較処理を実行する。図33は、リニアサーチブロック2におけるステップA12の処理を示すフローチャートである。
【0161】
図33を参照すると、ステップA12は、第1の構成例におけるステップB3を実行することが分かる。本構成例では、ルール比較ブロック2が単一のルールリストで構成されるため、LOOKUP処理時には、直接先頭のルール処理ブロック220−1から順に検索キーとルールとの比較処理を実行していけば良い。また、第1の構成例における動作時と異なり、決定木を辿る際のアドレス計算等も不要である。本構成例におけるLOOKUP処理時では、アドレスは明示的に指定可能である。
【0162】
<INSERT処理>
次に、INSERT処理を説明する。図34は、第2の構成例におけるINSERT処理を示すフローチャートである。図34を参照すると、第2の構成例におけるINSERT処理は、第1の構成例の動作におけるステップA4がステップA13に置き換わったものである。その他の動作は全て第1の構成例における動作と変わりないため、詳細な説明を省略する。
【0163】
ステップA13:
コマンド入力ブロック4からINSERTコマンドを受け取ると、ルール比較ブロック2は、当該ブロックにおいてルールの複製が発生するかを確認する。本構成例の場合、ルール比較ブロックは決定木で構成されていないため、ルールの複製は発生しない。このため、図35に示すルールの複製有無確認処理を行う。図35は、リニアサーチブロック2におけるステップA13の処理を示すフローチャートである。
【0164】
ステップB11:
エントリ数カウントブロック21のカウント処理ブロック210は、コマンド入力ブロック4からコマンドを受け取る。カウント処理ブロック210は、エントリ数記憶ブロック211から当該リニアサーチブロック2の有効エントリ数を読み出す。そして、カウント処理ブロック210は、読み出した有効エントリ数を示す出力データ216を、エントリ追加対象決定ブロック3に出力する。
【0165】
本ステップ以降は、第1の構成例と同様の動作であるため、詳細な説明は省略する。
【0166】
<DELETE処理>
次に、DELETE処理を説明する。図36は、第2の構成例におけるDELETE処理を示すフローチャートである。図36を参照すると、第2の構成例におけるDELETE処理は、第1の構成例の動作におけるステップA9が除かれたものである。その他の動作は全て第1の構成例における動作と変わりないため、詳細な説明を省略する。
【0167】
1−4.第3の構成例
次に、本実施の形態に係るパケット分類器1の第3の構成例について説明する。第3の構成例では、第1の構成例におけるルール比較ブロック2(決定木処理ブロック2)と、第2の構成例におけるルール比較ブロック2(リニアサーチブロック2)が混在する。この場合、ルール比較ブロック2−1〜2−NにおけるM個が第1の構成例におけるルール比較ブロック2(決定木処理ブロック2)であり、残りN−M個が第2の構成例におけるルール比較ブロック2(リニアサーチブロック2)である。
【0168】
但し、本実施の形態に係るパケット分類器1は、パイプライン処理によるハードウェア実装を想定している。そのため、第1の構成におけるルール比較ブロック2のパイプライン段数と、第2の構成におけるルール比較ブロック2のパイプライン段数を合わせておいた方がより効率的である。第1の構成におけるルール比較ブロック2は、H個の決定木ノード処理ブロック200と、1個のエントリ数カウントブロック21、B個のルール処理ブロック220を備えている。一方、第2の構成におけるルール比較ブロック2は、1個のエントリカウントブロック21と、B個のルール処理ブロック220を備えている。例えばLOOKUP処理の場合、第1の構成におけるルール比較ブロック2のパイプライン段数がH+B段になるのに対し、第2の構成におけるルール比較ブロック2のパイプライン段数はB段となる。この不一致を防ぐため、第3の構成においては、第2の構成におけるルール比較ブロック2を用いる際には、H+B個のルール処理ブロック220を備えることが望ましい。これにより、LOOKUP処理を基準として考えた場合に、パイプライン段数が一致することになり、より効率的な処理が可能となる。
【0169】
上記以外の構成については、第1、第2の構成例と同様であるため、詳細な説明は省略する。
【0170】
次に、本構成におけるパケット分類器1の動作について説明する。但し、LOOKUP処理、DELETE処理については、各ルール処理ブロック2において、第1の構成における動作、あるいは、第2の構成における動作を実行すれば良いため、詳細な説明を省略する。以下では、より効率的なルール管理が可能となるよう、INSERT処理における動作について説明する。
【0171】
<INSERT処理>
第3の構成例におけるINSERT処理は、第1及び第2の構成例の動作とほぼ同様である。ルール比較ブロック2、エントリ追加対象決定ブロック3以外のブロックについては、全く変わりはないため、詳細な説明を省略する。
【0172】
ルール比較ブロック2は、その構成が第1の構成例におけるルール比較ブロック2である場合、第1の構成例における動作を実行する。ルール比較ブロック2は、その構成が第2の構成例におけるルール比較ブロック2である場合、第2の構成例における動作を実行する。
【0173】
第3の構成例におけるINSERT処理においては、上記の第1及び第2の構成例におけるステップA5(エントリ追加対象のルール比較ブロック2を決定する処理)が、次に説明されるステップA14に置き換えられる。
【0174】
ステップA14:
エントリ追加対象決定ブロック3は、ルール比較ブロック2から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図37は、ステップA14の処理を示すフローチャートである。
【0175】
ステップE1、E6:
エントリ追加対象決定ブロック3は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る(ステップE1)。次に、エントリ追加対象決定ブロック3は、第1の構成例のルール比較ブロック2のうち、有効エントリ数がルールリストの最大数B(リストサイズ)を下回っているものがあるか否か確認する(ステップE6)。有効エントリ数がリストサイズを下回っているものが無い場合(ステップE6;No)、処理はステップE8に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合(ステップE6;Yes)、処理はステップE7に進む。
【0176】
ステップE7:
エントリ追加対象決定ブロック3は、第1の構成例のルール比較ブロック2のうち、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。その後、処理は、ステップE5に進む。
【0177】
ステップE8:
エントリ追加対象決定ブロック3は、第2の構成例を用いているルール比較ブロック2のうち、有効エントリ数がルールリストの最大数H+B(リストサイズ)を下回っているものがあるか否か確認する。有効エントリ数がリストサイズを下回っているものが無い場合(ステップE8;No)、処理はステップE3に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合(ステップE8;Yes)、処理はステップE9に進む。
【0178】
ステップE3:
エントリ追加対象決定ブロック3は、エントリを追加できるルール比較ブロック2は存在しないと判断する。その後、処理は、ステップE5に進む。
【0179】
ステップE9:
エントリ追加対象決定ブロック3は、第2の構成例のルール比較ブロック2のうち、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。その後、処理は、ステップE5に進む。
【0180】
ステップE5:
エントリ追加対象決定ブロック3は、各ルール比較ブロック2にエントリ追加の可否を通知する。例えば、エントリ追加対象決定ブロック3は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外のルール比較ブロック2に対してルール追加処理の不実行を指示する。なお、ここでは有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。
【0181】
本ステップ以降は、第1、第2の構成例と同様の動作であるため、詳細な説明は省略する。
【0182】
なお、上記の動作からも分かるように、INSERT処理の場合には、第2の構成例のルール比較ブロック2は、ステップA14を実行するまで、パイプラインが停止した状態になり、ステップA14を実行後にパイプラインが再開する。第1の構成例のルール比較ブロック2は、ステップA14を実行するまでに、既にパイプライン段数としてH段を実行し終わっているため、INSERT処理時にのみ、各ルール比較ブロック2におけるパイプラインの処理タイミングが異なってしまう。しかしながら、第1の構成例のルール比較ブロック2にルールを追加する場合は、第2の構成例のルール比較ブロック2にはルールは決して追加されないため、第2の構成例のルール比較ブロック2のステップA14以降の動作は無視しても良い。一方、第2の構成例のルール比較ブロック2にルールを追加する場合は、第1の構成例のルール比較ブロック2におけるステップA14以降の動作は無視しても良い。どちらの動作を無視しても良いかは、結果出力ブロック5に各ルール比較ブロック2からの処理結果が入力された際に、判断することできる。
【0183】
また、本構成例におけるINSERT処理では、第1の構成例のルール比較ブロック2にルールを追加することを優先している。これは、第2の構成例のルール比較ブロックは単なるルールリストであるため、有効エントリ数がルールリストに満たない場合、必ずルールを追加することが可能となる。一方、第1の構成例のルール比較ブロック2は、決定木を用いているため、ルールの複製が生じる可能性がある。このため、可能な限り第1の構成例のルール比較ブロック2へのルール追加を優先することによって、効率的なルール管理を実現している。
【0184】
2.第2の実施の形態
図38は、本発明の第2の実施の形態に係るパケット分類器8の構成を示すブロック図である。図38を参照すると、第2の実施の形態におけるパケット分類器8は、第1の実施の形態におけるパケット分類器1におけるコマンド入力ブロック4をコマンド入力ブロック9に、入力データ6を入力データ10に置き換えたものである。その他の構成は、第1の実施の形態におけるパケット分類器1と同様であるため、詳細な説明は省略する。
【0185】
図39は、コマンド入力ブロック9の構成を示すブロック図である。図39を参照すると、コマンド入力ブロック9は、第1の実施の形態におけるコマンド入力ブロック4における出力先分析ブロック40を出力先分析ブロック44に、コマンド出力情報記憶ブロック41をコマンド出力情報記憶ブロック45に置き換えたものである。出力先分析ブロック44には、外部からパケット分類器8への入力データ10が入力される。本構成の場合、各ルール比較ブロック2においては、ワイルドカードを含むヘッダフィールドの種類によって、装置内コマンドの出力先を決定することになる。
【0186】
図40は、コマンド出力情報記憶ブロック45が記憶するコマンド出力情報を示す概念図である。本実施の形態によれば、「識別情報」は、フィールド分析データである。より詳細には、フィールド分析データは、ルールを構成するヘッダフィールド数と等しいビット幅で構成されており、各ビットが各フィールドと対応付けられている。フィールドにワイルドカードが含まれる場合、当該フィールドに対応づけられたビットは‘0’となる。一方、フィールドにワイルドカードが含まれない場合、当該フィールドに対応付けられたビットは‘1’となる。すなわち、本実施の形態では、「識別情報」は、複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である。出力先データは、第1の実施の形態の場合と同じである。
【0187】
出力先分析ブロック44は、外部からパケット分類器1に入力された入力データ10を受け取る。出力先分析ブロック44は、LOOKUPの場合は検索キー、INSERTの場合は新規ルール、DELETEの場合は削除ルールから、上記の「識別情報」を抽出する。そして、出力先分析ブロック44は、抽出された識別情報とコマンド出力情報を参照することによって、選択ルール比較ブロック2を認識する。その他は、第1の実施の形態と同じである。
【0188】
ここで、新規ルールや削除ルールについては、第1の実施の形態と同様の表現形式で表現することによって、各フィールドにワイルドカードが含まれるか否かを判断することができる。一方、LOOKUP時の検索キーの場合は、到着パケットによっては、ルールで定義されたフィールドが存在しない場合が考えられる。これに対応するため、入力データ10としては、検索キーの各フィールドが定義されていない、すなわち、到着パケットには当該フィールド値が存在しないことを示すための1ビットの信号を用いる。これは、すなわち、コマンド出力情報におけるフィールド分析データと同様のものであり、外部の制御ブロック等で生成されるものとする。
【0189】
あるいは、ルールの表現形式と同様、マスクビットを用いて検索キーを定義しても構わない。この場合、出力先分析ブロック44は、入力データ10として検索キーを受け取った場合、マスクビットを基にフィールド分析データと同様のものを生成する。
【0190】
その他の構成は、第1の実施の形態におけるコマンド入力ブロック4と同様であるため、詳細な説明は省略する。
【0191】
尚、第2の実施の形態には、第1の実施の形態におけるパケット分類器1のルール比較ブロック2の3種類の構成例が適用できる。
【0192】
本実施の形態によれば、第1の実施の形態と同じ効果が得られる。
【0193】
3.第3の実施の形態
図41は、本発明の第3の実施の形態に係るパケット分類器11の構成を示すブロック図である。図41を参照すると、第3の実施の形態におけるパケット分類器11は、第1の実施の形態におけるパケット分類器1におけるエントリ追加対象決定ブロック3をエントリ追加対象ブロック12、結果出力ブロック5を結果出力ブロック13に置き換え、さらにエントリ追加対象ブロック12から結果出力ブロック13へ出力信号を加えたものである。その他の構成は、第1の実施の形態におけるパケット分類器1と同様であるため、詳細な説明は省略する。
【0194】
尚、第3の実施の形態には、第1の実施の形態におけるパケット分類器1のルール比較ブロック2の3種類の構成例が適用できる。
【0195】
次に、本実施の形態に係るパケット分類器11の動作を説明する。
【0196】
本実施の形態におけるパケット分類器11の動作は、INSERT時の動作のみ第1の実施の形態と異なる。このため、以下ではINSERT時の動作において、第1の実施の形態と異なる点のみを説明し、その他については詳細な説明を省略する。なお、LOOKUP時の動作、及びDELETE時の動作については、第1の実施の形態における動作と同様であるため、こちらも詳細な説明は省略する。
【0197】
図42は、本実施の形態におけるINSERT時の処理を示すフローチャートである。図42を参照すると、本実施の形態におけるINSERT時の処理は、第1の実施の形態におけるINSERT時の処理(図22)におけるステップA5をステップA15に、ステップA8をステップA17に置き換え、ステップA15とステップA6の間にステップA16を加えた点が異なる。これ以外の動作については、全て第1の実施の形態におけるINSERT時の処理と同様であるため、以下では、ステップA15、ステップA16、ステップA17の動作について説明する。
【0198】
ステップA15:
エントリ追加対象決定ブロック12は、ルール処理ブロック2から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図43は、ステップA15の処理を示すフローチャートである。
【0199】
ステップE1、E2:
エントリ追加対象決定ブロック12は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る(ステップE1)。次に、エントリ追加対象決定ブロック12は、各エントリ追加対象候補のうち、有効エントリ数がルールリストの最大数B(リストサイズ)を下回っているものがあるか否か確認する(ステップE2)。有効エントリ数がリストサイズを下回っているものが無い場合(ステップE2;No)、処理はステップE3に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合(ステップE2;Yes)、処理はステップE4に進む。
【0200】
ステップE3、E10:
エントリ追加対象決定ブロック12は、エントリを追加できるルール比較ブロック2は存在しないと判断する(ステップE3)。この場合、エントリ追加対象決定ブロック12は、エントリ追加対象のルール比較ブロック2が存在しなかったことを意味する信号を、結果出力ブロック13に通知する(ステップE10)。そして、ステップA15の処理は終了する。
【0201】
ステップE4、E11:
エントリ追加対象決定ブロック12は、有効エントリ数がリストサイズを下回っているものの中で、有効エントリ数が最小のものをエントリ追加対象ルール比較ブロックとして決定する(ステップE4)。その後、エントリ追加対象決定ブロック12は、エントリ追加対象ルール比較ブロックにのみ、エントリ追加許可を出力する(ステップE11)。この時、エントリ追加対象以外のルール比較ブロック2には、何ら信号は出力されない。そして、ステップA15の処理は終了する。
【0202】
ステップA16:
ステップA15において、エントリ追加対象のルール比較ブロック2が存在したかによって以降の処理が異なる。エントリ追加対象のルール比較ブロック2が存在した場合(ステップA16;Yes)、エントリ追加許可を受け取ったエントリ追加対象のルール比較ブロック2は、第1の実施の形態におけるINSERT時の動作と同様に、ステップA6、ステップA7の処理を実行する。その後、処理はステップA17に進む。一方、エントリ追加対象のルール比較ブロック2が存在しなかった場合(ステップA16;No)、処理はそのままステップA17に進む。
【0203】
ステップA17:
結果出力ブロック13がエントリ追加対象のルール比較ブロック2からコマンドを受け取った場合、結果出力ブロック13は、受け取ったコマンド内の結果フラグを参照して、新規ルールが追加されたか、又は追加されなかったかを確認する。そして、結果出力ブロック13は、その結果を示す出力データ7を、INSERT処理の最終結果として出力する。
【0204】
一方、結果出力ブロック13がエントリ追加対象決定ブロック12から、エントリ追加対象のルール比較ブロック2が存在しなかったことを意味する信号を受け取る場合もある(ステップE10)。この場合、結果出力ブロック13は、新規ルールの追加に失敗したことを示す出力データ7を、INSERT処理の最終結果として出力する。
【0205】
なお、第1の実施の形態におけるINSERT処理時の動作と同様、新規ルールを追加できた場合の最終結果として、ルールを追加した箇所を示すエントリIDを出力することが挙げられる。エントリIDやその他の情報を最終結果として出力する方法については、第1の実施の形態におけるINSERT処理時の動作と同様であるため、説明を省略する。
【0206】
また、上記では有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。
【0207】
上記では、第1の実施の形態における第1の構成例のINSERT処理に対する変更点を説明した。但し、第1の実施の形態における第2の構成例のINSERT処理に対しても、本実施の形態を適用可能である。具体的には、図34で示された第2の構成例のINSERT処理において、ステップA5をステップA15に、ステップA8をステップA17に置き換え、ステップA15とステップA6の間にステップA16を加える。
【0208】
同様に、第1の実施の形態における第3の構成例のINSERT処理に対しても、本実施の形態を適用可能である。この場合は、ステップA14をステップA18に、ステップA8をステップA17に置き換え、ステップA18とステップA6の間にステップA16を加える。図44は、ステップA18の処理を示すフローチャートである。上記と同様に、エントリ追加対象のルール比較ブロック2が存在しなかった場合、ステップE3の後にステップE10が実行される。一方、エントリ追加対象のルール比較ブロック2として、第1あるいは第2の構成例のルール比較ブロック2が選択された場合、ステップE11が実行される。
【0209】
また、本実施の形態と第2の実施の形態の組み合わせも可能である。
【0210】
本実施の形態によれば、既出の実施の形態と同じ効果が得られる。更に、次のような効果も得られる。
【0211】
第1、第2の実施の形態では、エントリ追加対象のルール比較ブロック2でないブロックに対しても、エントリ追加対象決定ブロック12からエントリ追加不可の返信がある。この場合、メモリアクセスは行われないが、コマンドだけは順次パイプラインを受け渡されていく。つまり、パイプラインレジスタが起動するため、この電力は消費される。しかし、本実施の形態では、エントリ追加対象のルール比較ブロック2以外のブロックに対しては、何らコマンドを返信しない。従って、エントリ追加対象以外のルール比較ブロック2のパイプラインレジスタは起動しない。よって、その分だけ消費電力を削減することが可能となる。
【0212】
4.第4の実施の形態
次に、本発明の第4の発明を実施するための最良の形態について図面を参照して詳細に説明する。
【0213】
図45は、本発明の第4の実施の形態に係るパケット分類器の構成を示すブロック図である。第4の実施の形態では、コンピュータがソフトウェアプログラムを実行することによりパケット分類処理が実現される。具体的には、本実施の形態に係るパケット分類器は、プログラム処理装置14とパケット分類プログラム15を備えている。プログラム処理装置14は、サーバやPC等のホストのCPUにより実現される。パケット分類プログラム15は、プログラム処理装置14によって実行されるコンピュータプログラムであり、プログラム処理装置14の動作を制御する。プログラム処理装置14は、パケット分類プログラム15を実行することにより、既出の実施の形態で説明されたパケット分類器1、あるいは、パケット分類器8、あるいは、パケット分類器11の機能を備えることができる。
【0214】
なお、パケット分類プログラム15は、コンピュータ読み取り可能な記録媒体に記録されていてもよい。
【0215】
プログラム処理装置14として、複数のCPUコアを有するマルチコアプロセッサ(さらには、より多くのCPUコアを有するメニーコアプロセッサ)を用いてもよい。その場合、それぞれのCPUコアに、コマンド入力ブロック4、ルール比較ブロック2−1〜2−N、エントリ追加対象決定ブロック3、結果出力ブロック5、さらには、ルール比較ブロック2を構成する各決定木ノード処理ブロック200、エントリ数カウントブロック21、ルール処理ブロック220等の処理を実行させることにより、より高速な処理が可能となる。
【0216】
本実施の形態によれば、既出の実施の形態と同じ効果が得られる。
【0217】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【0218】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【0219】
(付記1)
パケット分類に用いられるルールを管理するパケット分類器であって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が1以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類器。
【0220】
(付記2)
付記1に記載のパケット分類器であって、
前記選択グループは、前記検索キー及びルールから抽出される識別情報に基づいて識別可能であり、
前記コマンド入力ブロックは、前記識別情報と前記選択ルール比較ブロックとの対応関係を示すコマンド出力情報を保持し、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールから前記識別情報を抽出し、前記抽出された識別情報と前記コマンド出力情報を参照することによって、前記選択ルール比較ブロックを識別する
パケット分類器。
【0221】
(付記3)
付記2に記載のパケット分類器であって、
前記識別情報は、前記検索キー及びルールに含まれる所定のフィールドの値である
パケット分類器。
【0222】
(付記4)
付記2に記載のパケット分類器であって、
前記検索キー及びルールは、複数のフィールドを含み、
前記識別情報は、前記複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である
パケット分類器。
【0223】
(付記5)
付記1乃至4のいずれか一項に記載のパケット分類器であって、
前記複数のルール比較ブロックに接続されたエントリ追加対象決定ブロックを更に備え、
単一のルールは、複製が発生しないように、前記複数のルール比較ブロックのうちいずれか1つによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身によって管理され得るかどうかを判定し、
前記新規ルールが自身によって管理され得る場合、当該選択ルール比較ブロックはエントリ追加対象候補であり、
前記エントリ追加対象決定ブロックは、前記新規ルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、
前記選択されたエントリ追加対象は、前記新規ルールを、自身が管理するルールリストに追加する
パケット分類器。
【0224】
(付記6)
付記5に記載のパケット分類器であって、
前記複数のルール比較ブロックは、パケット分類に用いられる複数の決定木のそれぞれを構成し、
単一のルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、
前記新規ルールが単一の葉ノードによって管理され得る場合、当該選択ルール比較ブロックは前記エントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、
前記エントリ追加対象は、前記新規ルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加する
パケット分類器。
【0225】
(付記7)
付記6に記載のパケット分類器であって、
前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、
前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択する
パケット分類器。
【0226】
(付記8)
付記5に記載のパケット分類器であって、
前記複数のルール比較ブロックの各々は、リスト形式でルールを管理する
パケット分類器。
【0227】
(付記9)
パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法であって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類方法は、
(A)前記パケット分類器が、複数のルール比較ブロックを提供するステップと、
ここで、
前記複数のルール比較ブロックの各々は、1以上のルールを管理し、入力コマンドに応じた処理を実行するように構成され、
前記入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドであり、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
(B)前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを出力するステップと、
(C)前記選択ルール比較ブロックにおいて、前記入力コマンドに応じた処理を実行するステップと
を含む
パケット分類方法。
【0228】
(付記10)
コンピュータによって実行され、前記コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムであって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が1以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類プログラム。
【符号の説明】
【0229】
1 パケット分類器
2 ルール比較ブロック
3 エントリ追加対象決定ブロック
4 コマンド入力ブロック
5 結果出力ブロック
8 パケット分類器
9 コマンド入力ブロック
11 パケット分類器
12 エントリ追加対象決定ブロック
13 結果出力ブロック
14 プログラム処理装置
15 パケット分類プログラム
20 決定木パイプラインブロック
21 エントリ数カウントブロック
22 ルールパイプラインブロック
40 出力先分析ブロック
41 コマンド出力情報記憶ブロック
42 コマンド出力ブロック
44 出力先分析ブロック
45 コマンド出力情報記憶ブロック
200 決定木ノード処理ブロック
210 カウント処理ブロック
211 エントリ数記憶ブロック
220 ルール処理ブロック
2000 子ノード決定ブロック
2001 ノード情報記憶ブロック
2200 比較更新処理ブロック
2201 エントリ記憶ブロック

【特許請求の範囲】
【請求項1】
パケット分類に用いられるルールを管理するパケット分類器であって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が1以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類器。
【請求項2】
請求項1に記載のパケット分類器であって、
前記選択グループは、前記検索キー及びルールから抽出される識別情報に基づいて識別可能であり、
前記コマンド入力ブロックは、前記識別情報と前記選択ルール比較ブロックとの対応関係を示すコマンド出力情報を保持し、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールから前記識別情報を抽出し、前記抽出された識別情報と前記コマンド出力情報を参照することによって、前記選択ルール比較ブロックを識別する
パケット分類器。
【請求項3】
請求項2に記載のパケット分類器であって、
前記識別情報は、前記検索キー及びルールに含まれる所定のフィールドの値である
パケット分類器。
【請求項4】
請求項2に記載のパケット分類器であって、
前記検索キー及びルールは、複数のフィールドを含み、
前記識別情報は、前記複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である
パケット分類器。
【請求項5】
請求項1乃至4のいずれか一項に記載のパケット分類器であって、
前記複数のルール比較ブロックに接続されたエントリ追加対象決定ブロックを更に備え、
単一のルールは、複製が発生しないように、前記複数のルール比較ブロックのうちいずれか1つによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身によって管理され得るかどうかを判定し、
前記新規ルールが自身によって管理され得る場合、当該選択ルール比較ブロックはエントリ追加対象候補であり、
前記エントリ追加対象決定ブロックは、前記新規ルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、
前記選択されたエントリ追加対象は、前記新規ルールを、自身が管理するルールリストに追加する
パケット分類器。
【請求項6】
請求項5に記載のパケット分類器であって、
前記複数のルール比較ブロックは、パケット分類に用いられる複数の決定木のそれぞれを構成し、
単一のルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、
前記新規ルールが単一の葉ノードによって管理され得る場合、当該選択ルール比較ブロックは前記エントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、
前記エントリ追加対象は、前記新規ルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加する
パケット分類器。
【請求項7】
請求項6に記載のパケット分類器であって、
前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、
前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択する
パケット分類器。
【請求項8】
請求項5に記載のパケット分類器であって、
前記複数のルール比較ブロックの各々は、リスト形式でルールを管理する
パケット分類器。
【請求項9】
パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法であって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類方法は、
(A)前記パケット分類器が、複数のルール比較ブロックを提供するステップと、
ここで、
前記複数のルール比較ブロックの各々は、1以上のルールを管理し、入力コマンドに応じた処理を実行するように構成され、
前記入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドであり、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
(B)前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを出力するステップと、
(C)前記選択ルール比較ブロックにおいて、前記入力コマンドに応じた処理を実行するステップと
を含む
パケット分類方法。
【請求項10】
コンピュータによって実行され、前記コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムであって、
各ルールは、パケットヘッダに含まれる1以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が1以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記1以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate

【図44】
image rotate

【図45】
image rotate


【公開番号】特開2012−239048(P2012−239048A)
【公開日】平成24年12月6日(2012.12.6)
【国際特許分類】
【出願番号】特願2011−106914(P2011−106914)
【出願日】平成23年5月12日(2011.5.12)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】