(57)【要約】【課題】エントリを動的に追加していったときに、エントリの圧縮および伸長を行う方法および装置を提供すること。【解決手段】フローテーブルのエントリに基づき、フロー識別を行うパケット中継装置におけるエントリ圧縮伸長方法において、新たに登録する新規パターンがエントリのフロー識別パターンに対しインクリメンタルパターンであるか判定し、インクリメンタルパターンであった場合、エントリのマスクパターンを変更する。【選択図】図１
2008167340.tif 000002
【特許請求の範囲】
【請求項１】
フロー識別の対象となるパケットのパターンが記述されたフローテーブルのエントリに基づきフロー識別を行うパケット中継装置におけるエントリ圧縮伸長方法において、
前記フローテーブルに新たに登録する新規パターンが前記エントリのフロー識別パターンに対し差分が１ビットであるインクリメンタルパターンであるか判定するステップと、
前記新規パターンがインクリメンタルパターンであった場合、フロー識別において前記フロー識別パターンに対するドントケアビットの位置を示す前記エントリのマスクパターンを変更するステップと、
前記新規パターンがインクリメンタルパターンでなかった場合、前記新規パターンを前記フローテーブルにエントリとして追加登録するステップと、
を備えるエントリ圧縮伸長方法。
【請求項２】
前記フローテーブルに登録されたエントリの数があらかじめ定められた値以上になったときに、
前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
残ったエントリをソートするステップと、
ソートした順番に再登録を指示するステップと、
をさらに備えることを特徴とする請求項１記載のエントリ圧縮伸長方法。
【請求項３】
前記新規パターンを前記フローテーブルにエントリとして追加登録するステップにおいて、
登録可能な残りのエントリ数を一定時間あたりのエントリの登録速度で除算するステップと、
除算により算出した値があらかじめ定められた条件を満たした場合、
前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
残ったエントリをソートするステップと、
ソートした順番に再登録を指示するステップと、
をさらに備えることを特徴とする請求項１記載のエントリ圧縮伸長方法。
【請求項４】
前記フローテーブルの前記エントリから特定のパターンを削除するときに、
該パターンが圧縮されたエントリにある場合には、該パターンをフロー識別に用いないことを示すフラグを含むエントリを登録するステップ
をさらに備えることを特徴とする請求項１乃至３のいずれか１項に記載のエントリ圧縮方法。
【請求項５】
圧縮されたエントリに含まれるエントリ数が１になった場合に、
該圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
をさらに備えることを特徴とする請求項４記載のエントリ圧縮伸長方法。
【請求項６】
フロー識別の対象となるパケットのパターンが記述されたフローテーブルのエントリに基づきフロー識別を行うパケット中継装置において、
新規パターンを前記フローテーブルに登録する時に前記新規パターンが前記エントリのフロー識別パターンに対し差分が１ビットであるインクリメンタルパターンであるかどう
か判定するインクリメンタルパターン判定手段と、
インクリメンタルパターンであると判定された場合に、前記フローテーブルのエントリに対し圧縮を行うエントリ圧縮伸長手段と、
を備えることを特徴とするパケット中継装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントリの圧縮伸長方法およびエントリの圧縮伸長を行う装置に関する。
【背景技術】
【０００２】
従来よりネットワークにおいて、パケットに対し、フィルタリングやQoS（Quality of Service）を行うパケット中継装置がある。これらのパケット中継装置では、装置内に保持されたテーブルに記載された情報とパケットとを比較し、条件に一致した場合に所定の処理を行っている。
【０００３】
図１７は、従来のパケット中継装置のブロック図である。
パケット中継装置１７０１は、パケット受信部１７０２、パケット解析部１７０３、パケットフロー識別部１７０４、パケットフィルタリング処理部１７０５、パケット中継処理部１７０６、トラフィック管理処理部１７０７、パケット送信部１７０８、パケットバッファ部１７０９、ＣＰＵ処理部１７１０を備える。
【０００４】
パケットフロー識別部１７０４は、フロー識別の対象となるパケットが持つパターンが記述されたフローテーブル１７１１を備える。
ＣＰＵ処理部１７１０は、フロー識別対象パターン登録削除部１７１２を備える。
【０００５】
パケット受信部１７０２は、ネットワークに接続された回線１７００からパケットを受信する。
パケット解析部１７０３は、受信したパケットのパケットヘッダを解析し、パケット種別（どの情報がパケットのどの位置にあるか）を特定する。
【０００６】
パケットフロー識別部１７０４は、パケット解析部１７０３で得た情報とＣＰＵ処理部１７１０により設定されたフローテーブルに基づき、パケット中継装置１７０１でそのパケットがどのような処理をされるべきパケットかを特定する。すなわち、フロー識別を行う。例えば、パケットフィルタリングやQoSの適用するパケットを特定する。
【０００７】
パケットフィルタリング処理部１７０５は、パケットフロー識別部１７０４から得た情報を元に、不必要なパケットの廃棄を行う。
パケット中継処理部１７０６は、ＣＰＵ処理部１７１０から得た情報から送信先を特定する処理や、パケットフロー識別部１７０４の識別結果からＣＰＵ処理部１７１０へパケットをコピー送信する判断をする等の処理を行う。
【０００８】
トラフィック管理処理部１７０７は、パケットフロー識別部１７０４の識別結果に対応してQoSを提供する等、優先制御および帯域制御を管理する。
パケット送信部１７０８は、パケットを回線に送信する。
【０００９】
パケットバッファ部１７０９は、送信回線が輻輳している場合、QoSの提供などのため、パケットを滞留させる。
ＣＰＵ処理部１７１０は、ハード中継処理できないパケットのソフト中継処理および経路情報管理やフロー識別情報管理などのテーブル管理処理を行う。
【００１０】
フロー識別対象パターン登録削除部１７１２は、ユーザからの指示に基づき、パケットフロー識別部１７０４のフローテーブルの内容を更新する。
図１８は、従来のパケット中継装置のパケットフロー識別部の詳細な図である。
【００１１】
パケットフロー識別部１７０４は、受信したパケット１８０１がどのようなパケットであるかを判別するためのテーブル（フローテーブル）１７１１を備えている。
フローテーブル１７１１は、ＣＰＵ処理部１７１０により設定される。フローテーブル１７１１の項目としては、パケットと比較するためのフロー識別パターン、フロー識別パターンのドントケアビットを指定するマスクパターン、比較位置を示すオフセット情報、パケットの種別を示すパケット種別、および後の処理でどのような処理が行われるべきパケットかを識別するためのフローＩＤなどがある。
【００１２】
パケットフロー識別部１７０４は、フロー識別パターンと受信したパケットが一致するかどうか調べる。一致した場合は、そのフロー識別パターンに対応するフローＩＤをパケットに付加し、パケットフィルタリング処理部１７０５に出力する。
【００１３】
パケットフロー識別部１７０４以降の処理部においては、パケットに付されたフローＩＤに基づき、どのような処理を行うかを判断する。
上記のようなパケット中継装置においては、ユーザがフィルタリングやQoSの対象となるパケットのパターンをあらかじめＣＰＵ処理部１７１０からフローテーブル１７１１に登録していた。そして、パケットフィルタリング処理部１７０５やパケット中継処理部１７０６等でフローＩＤに対応した処理していた。
【００１４】
この場合、エントリ登録数の上限や、マスクパターンを用いた登録エントリの圧縮は、ユーザがパターンの登録時に静的に考慮可能である。
また、上記のようにフィルタリング等の対象とするパターンをあらかじめ登録できる場合の他に、ウィルスに感染したパソコンを持ち込んだ場合など、フィルタリング等の対象となるパターンをあらかじめ登録できない場合がある。
【００１５】
図１９は、あらかじめ対象となるパターンを登録できない場合の従来のパケット中継装置のブロック図である。
図１９のパケット中継装置は、図１７のパケット中継装置に比べ、フロー識別対象パターン登録削除部１７１２の代わりにフロー識別対象パターン検出登録削除部１７１３を備える点が異なる。
【００１６】
図１９のパケット中継装置では、ＣＰＵ処理部１７１０がトラフィック管理処理部１７０７からパケット１７１４を受信し、該パケット１７１４をチェックする。そして該パケット１７１４が一定の条件を満たしている場合、例えば該パケット１７１４が怪しい動作をしている場合は、該パケット１７１４のパターンをフィルタリング対象として、パケットフロー識別部１７０４のフローテーブル１７１１に登録する。
【００１７】
このようにあらかじめパターンを登録できないパケット中継装置においては、パケットフロー識別部のフローテーブルのエントリが動的に追加登録または削除されていく。
特許文献１には、外部からのアクセスがあった際に、所定の設定に基づいてフィルタリングし、外部からの不正なアクセスを防止するネットワークアクセス制御方法および装置が記載されている。
【特許文献１】特開２００３−８６６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、従来のパケット中継装置では、フィルタリング等の対象となるパターンをエントリとしてテーブルに動的に追加登録していく場合、エントリの圧縮を行っていないため、すぐにエントリ登録数の上限に達してしまうという問題があった。
【００１９】
本発明は上記問題を鑑みてなされたもので、エントリを動的に追加および削除していったときに、エントリの圧縮および伸長を行う方法および装置を提供することである。
【課題を解決するための手段】
【００２０】
本発明は、上記課題を解決するため、下記のような構成を採用した。
すなわち、本発明の一態様によれば、本発明のエントリ圧縮伸長方法は、フロー識別の対象となるパケットのパターンが記述されたフローテーブルのエントリに基づきフロー識別を行うパケット中継装置におけるエントリ圧縮伸長方法において、新たに登録する新規パターンが前記エントリのフロー識別パターンに対し差分が１ビットであるインクリメンタルパターンであるか判定するステップと、前記新規パターンがインクリメンタルパターンであった場合、フロー識別において前記フロー識別パターンに対するドントケアビットの位置を示す前記エントリのマスクパターンを変更するステップと、前記新規パターンがインクリメンタルパターンでなかった場合、前記新規パターンを前記フローテーブルにエントリとして追加登録するステップと、を備えることを特徴とする。
【００２１】
また、本発明のエントリ圧縮伸長方法は、前記フローテーブルに登録されたエントリの数があらかじめ定められた値以上になったときに、前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、残ったエントリをソートするステップと、ソートした順番に再登録を指示するステップと、をさらに備えることが望ましい。
また、本発明のエントリ圧縮伸長方法は、前記新規パターンを前記フローテーブルにエントリとして追加登録するステップにおいて、登録可能な残りのエントリ数を一定時間あたりのエントリの登録速度で除算するステップと、算出した値があらかじめ定められた条件を満たした場合、前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、前記伸長したエントリのうち、解除パターンを示すエントリおよび該解除パターンに対応するエントリを削除するステップと、残ったエントリをソートするステップと、ソートした順番に再登録を指示するステップと、をさらに備えることが望ましい。
【００２２】
また、本発明のエントリ圧縮伸長方法は、前記フローテーブルの前記エントリから特定のパターンを削除するときに、該パターンが圧縮されたエントリにある場合には、該パターンをフロー識別に用いないことを示すフラグを含むエントリを登録するステップと、をさらに備えることが望ましい。
【００２３】
また、本発明のエントリ圧縮伸長方法は、圧縮されたエントリに含まれるエントリ数が１になった場合に、該圧縮されているエントリを伸長するステップと、解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップとをさらに備えることが望ましい。
【発明の効果】
【００２４】
本発明によれば、フロー識別の対象となるパターンを大量に保持することが可能となる。
【発明を実施するための最良の形態】
【００２５】
図１は、本発明の第１の実施に形態に係るパケット中継装置のブロック図である。
パケット中継装置１０１は、ＬＡＮやＷＡＮ等のネットワーク間に配置され、パケットフィルタリングやQoSの提供等を行う。
【００２６】
パケット中継装置１０１は、パケット受信部１０２、パケット解析部１０３、パケット
フロー識別部１０４、パケットフィルタリング処理部１０５、パケット中継処理部１０６、トラフィック管理処理部１０７、パケット送信部１０８、パケットバッファ部１０９、およびＣＰＵ処理部１１０を備え、各構成部はバスにより接続される。
【００２７】
パケットフロー識別部１０４は、フローテーブル１１１を備える。フローテーブル１１１には、フロー識別の対象となるパケットが持つパターンが記述される。
ＣＰＵ処理部１１０は、動的エントリ圧縮伸長部１１２およびフロー識別対象パターン検出登録削除部１１３を備える。
【００２８】
本発明の第１の実施の形態に係るパケット中継装置１０１の構成は、従来のパケット中継装置と比べて、ＣＰＵ処理部１１０にさらに動的エントリ圧縮伸長部１１２を備える点が異なる。そして、フローテーブル１１１へのエントリの登録や削除は、動的エントリ圧縮伸長部１１２を介して行われるため、エントリの圧縮または伸長を行うことが出来る。
【００２９】
パケット受信部１０２は、ネットワークに接続された回線１００からパケットを受信する。
パケット解析部１０３は、受信したパケットのパケットヘッダを解析し、パケット種別（どの情報がパケットのどの位置にあるか）を特定する。
【００３０】
パケットフロー識別部１０４は、パケット解析部１０３で得た情報とＣＰＵ処理部１１０によりフロー識別の対象となるパケットが持つパターンが記述されたパケットフロー識別部１０４内のフローテーブル１１１に基づき、パケット中継装置１０１でそのパケットがどのような処理をされるべきパケットかを特定する。例えば、パケットフィルタリングやQoSの適用可否を判断する。
【００３１】
パケットフィルタリング処理部１０５は、パケットフロー識別部１０４から得た情報を元に、不必要なパケットの廃棄を行う。
パケット中継処理部１０６は、ＣＰＵ処理部１１０から得た経路情報から送信先を特定する処理や、パケットフロー識別部１０４の識別結果に基づいて、ＣＰＵ処理部１１０へパケットをコピー送信するか否かの判断をする等の処理を行う。
【００３２】
トラフィック管理処理部１０７は、パケットフロー識別部１０４の識別結果に対応したQoSを提供する等、優先制御および帯域制御を管理する。また、パケットをフロー識別対象パターン検出登録削除部にコピー送信する。
【００３３】
パケット送信部１０８は、パケットを回線に送信する。
パケットバッファ部１０９は、送信回線が輻輳している場合、QoSの提供などのため、パケットを滞留させる。
【００３４】
ＣＰＵ処理部１１０は、ハード中継処理できないパケットのソフト中継処理、および経路情報管理やフロー識別情報管理などのテーブル管理処理を行う。
動的エントリ圧縮伸長部１１２は、フローテーブルのエントリの圧縮、伸長、登録、および削除を行う。
【００３５】
フロー識別対象パターン検出登録削除部１１３は、トラフィック管理処理部１０７から受信したパケットをチェックして、特定のパターンをフィルタリング等の対象とするか判断し、動的エントリ圧縮伸長部に特定のパターンの登録または削除を指示する。
【００３６】
図２は、ＣＰＵ処理部１１０のブロック図である。  
フロー識別対象パターン検出登録削除部１１３は、セキュリティ処理部２０１を備え、
動的エントリ圧縮伸長部１１２は、パターン登録処理部２０２、平均エントリ登録速度測定部２０３、登録エントリ数管理部２０４、エントリ削除処理部２０５、削除タイマ値更新部２０６、エントリ圧縮伸長処理部２０７、ミラーテーブル管理部２０８を備える。また、パターン登録処理部２０２は、インクリメンタルパターン判定部２０９を備える。
【００３７】
セキュリティ処理部２０１は、受信したパケットに対し種々のセキュリティチェックを実施し、特定のパターンを持つパケットのフロー識別（エントリ登録）およびフロー識別解除（エントリ削除）を判断する。
【００３８】
パターン登録処理部２０２およびインクリメンタルパターン判定部２０９は、セキュリティ処理部３０１から得た特定のパターンについて、フローテーブル１１１に登録済みのエントリのフロー識別パターンに対しインクリメンタルパターンであるかを判定し、インクリメンタルパターンであれば該特定のパターンの圧縮登録指示をエントリ圧縮伸長処理部２０７に対して行い、そうでなければ通常の登録指示を行う。インクリメンタルパターンとは、あるパターンに対し、差分が１ビットであるパターンである。
【００３９】
圧縮登録指示をした場合は、削除タイマ値更新部２０６に対し、削除タイマ値の更新を指示する。
通常の登録指示をした場合は、登録エントリに対し削除タイマ値を新規に設定し、さらに平均エントリ登録速度測定部２０３および登録エントリ数管理部２０４に対し、エントリを登録したことを通知する。
【００４０】
平均エントリ登録速度測定部２０３は、単位時間あたりの登録エントリ数を管理し、残エントリ数÷平均エントリ登録速度の値が、指定された閾値未満となった場合に、テーブル内のエントリを圧縮する指示をエントリ圧縮伸長処理部２０７に出す。なお、残エントリ数はフローテーブルが保持可能なエントリ数から現在登録されているエントリ数を引いたものであり、平均エントリ登録速度は、単位時間あたりのフローテーブルへのエントリの登録数である。
【００４１】
登録エントリ数管理部２０４は、登録エントリ数を管理し、登録エントリ数が指定された閾値以上となった場合に、テーブル内のエントリを圧縮する指示をエントリ圧縮伸長処理部２０７に出す。また、フロー識別の対象としないことを示す解除パターンについても圧縮を行う。
【００４２】
エントリ削除処理部２０５は、セキュリティ処理部２０１および削除タイマ値更新部２０６から指定されたエントリに対する削除を指示する。また、登録エントリ数管理部２０４に対しエントリを削除したことを通知する。
【００４３】
削除タイマ値更新部２０６は、エントリの登録時に指定された初期値にタイマを設定し、タイマが更新されることなく、タイマが満了した場合にエントリ削除処理部２０５へ該当する登録エントリの削除を指示する。削除タイマ値の初期値への更新は、インクリメンタルパターンの圧縮登録時や、エントリ圧縮時に実施される。また削除タイマ値により削除がされないようにすることも可能である。
【００４４】
エントリ圧縮伸長処理部２０７は、インクリメンタルパターンの登録指示をパターン登録処理部２０２から受けた場合、登録エントリ数管理部２０４または平均エントリ登録速度測定部２０３からエントリ圧縮指示を受けた場合に、フローテーブル１１１と同様の内容をもつミラーテーブルを用いて圧縮エントリを作成し、圧縮エントリの登録および圧縮により不要になったエントリの削除を実施する。
【００４５】
またエントリ圧縮伸長処理部２０７は、エントリ削除処理部２０５からの削除指示を受けたときに、圧縮エントリ内のパターンの削除の場合には、エントリの項目の解除フラグが１であるエントリを追加するが、解除パターン数が圧縮されているエントリ数−１となる場合には、圧縮エントリを伸長し、解除フラグが１である解除パターン（→定義なし）および解除パターンに対応するエントリを削除する。解除パターンに対応するエントリとは、解除パターンと同じフロー識別パターンを持つエントリである。
【００４６】
ミラーテーブル管理部２０８は、パケットフロー識別部１０４にあるフローテーブルと同じ内容のミラーテーブルを持つ。
図３は、本発明の第１の実施の形態に係るフローテーブルの例を示す図である。
【００４７】
上述の通り、フローテーブル１１１はパケットフロー識別部１０４内にあり、パケットフロー識別部１０４はフローテーブル１１１とパケット解析部１０３からの情報により、フロー識別を行う。
【００４８】
フローテーブルの項目としては、フロー識別パターン、マスクパターン、比較位置（オフセット）情報、パケット種別、フローＩＤ、圧縮エントリ数、解除パターン数、削除タイマ値、解除フラグがある。
【００４９】
フロー識別パターンには、通常、特定の処理を行いたいパケットが有するパターンが記載される。フローテーブル１１１においては、フロー識別パターンとしてＭＡＣアドレスが記載されており、１行目のエントリ（第１エントリ）のフロー識別パターンとして00000e000001、２行目のエントリ（第２エントリ）のフロー識別パターンとして00000e000002が記載されている。尚、フローテーブル４０１においては、それぞれの値は１６進数で表示されている。以下の説明において、説明を簡単にするため、00000e000001および00000e000002の上位１１桁を省略し、それぞれ1および2と表示することもある。そして1および2を２進数に変換し、それぞれ0001および0010と表示することもある。
【００５０】
マスクパターンには、フロー識別パターンに対してドントケアビット（don't care bit）の位置を指定するパターンが記載される。すなわち任意の論理値をとることが可能なビットの位置が指定される。
【００５１】
本発明の第１の実施の形態においては、マスクパターンのうち０の位置のビットがドントケアビットとなる。フローテーブル１１１においては、１行目のエントリ（第１エントリ）のマスクパターンとしてffffffffffff、２行目のエントリ（第２エントリ）のマスクパターンとしてfffffffffffeが記載されている。fを２進数にすると、1111であるためドントケアビットの指定はない。そこで、説明を簡単にするため、上位１１桁を省略すると、第１エントリのマスクパターンはfであり、第２エントリのマスクパターンはeである。そしてfおよびeを２進数で表示すると、それぞれ1111および1110となる。
【００５２】
第１エントリのマスクパターンはすべて1のため、ドントケアビットの指定はない。
一方、第２エントリのマスクパターンはe、すなわち1110であるため、最下位ビットがドントケアビットになる。第２エントリのフロー識別パターンは2、すなわち0010であるため、最下位ビットがドントケアビットであることを考慮すると、0010および0011がフロー識別パターンに登録されているのと同様の状態となり、これら２つのパターンがフロー識別の対象となる。すなわち、フロー識別パターンが0010と0011のエントリが圧縮されている。このように、マスクパターンを使用することによって、複数のエントリを１つのエントリに圧縮することができ、メモリを節約することが出来る。
【００５３】
比較位置（オフセット）情報には、フロー識別パターンと比較する受信パケットの比較
位置が記載される。図３のフローテーブル１１１においては、比較位置（オフセット）情報として０が記載されている。これはパケットの先頭と比較することを示している。すなわち、イーサネットフレームの構造に基づくパケットの場合、宛先のＭＡＣアドレスと比較することを意味する。例えば、比較位置（オフセット）情報として６が記載されていた場合は、フロー識別パターンとパケットの送信元ＭＡＣアドレスとを比較することになる。
【００５４】
パケット種別には、パケットの種別が記載される。フローテーブル１１１においては、ＴＡＧ無し、ＩＰが記載されている。実施の形態においては、フロー識別パターンと受信パケットの比較位置（オフセット）情報の位置と比較するが、例えばＭＡＣアドレスではなく、ＩＰアドレスと比較したい場合、ＴＡＧの有無によって比較位置が４バイトずれてしまうという問題がある。そこで、ＴＡＧの有無情報、プロトコル情報を検出条件に加えることで、正しく検出できるようにしている。
【００５５】
フローＩＤには、パケット中継装置においてパケットを識別するためのＩＤが記載される。フローＩＤは、後段の処理においてパケットの種類を識別するためにパケットに付加される情報である。
【００５６】
圧縮エントリ数には、そのエントリに圧縮されているエントリの数が記載される。フローテーブル１１１において、第１エントリの圧縮エントリ数は０である。これは、圧縮されているエントリが無いためである。圧縮されているエントリがないことを示すのに０の代わりに１を用いても良い。
【００５７】
上記の通り、第２エントリにはフロー識別パターンが0010と0011の２つのエントリが圧縮されて登録されている。従って、第２エントリの圧縮エントリ数は２となる。
解除パターン数には、圧縮されて登録されているエントリのうち、解除されたパターンの数が記載される。解除されたパターン（解除パターン）とは、フロー識別の対象としないパターンである。
【００５８】
削除タイマ値には、エントリが削除されるまでのタイマ値が記載される。エントリの登録後、一定時間経過すると、通常、そのエントリのフロー識別パターンを持つパケットは、送信されて来なくなるため、そのエントリは不要となる。そのため、本発明の第２の実施の形態においては、削除タイマ値を設定し、タイマ値が満了したら、そのタイマ値が設定されたエントリを削除する。
【００５９】
フローテーブル１１１において、第１エントリの削除タイマ値はfffffff0、第２エントリの削除タイマ値はffffffffとなっている。
本発明の第１の実施の形態においては、削除タイマ値の設定時にffffffffを設定し、タイマ値を減算していく。例えば、タイマ値を減算していき00000001となった場合に、タイマ満了と判断する。また、タイマ値に00000000を設定した場合には、タイマ値によるエントリの削除を行わないようにしても良い。
【００６０】
解除フラグには、０または１が記載される。これは、そのエントリがフロー識別の対象であるかそうでないかを判断するためのものである。本発明の第１の実施の形態においては、フローテーブルの上部に登録されたエントリが優先されるため、解除フラグが１のエントリが上部にあれば、該エントリのフロー識別パターンと同一のフロー識別パターンを持つエントリが下部にあっても、そのフロー識別パターンはフロー識別の対象とならない。
【００６１】
図４は、本発明の第１の実施の形態に係るパケット中継装置の処理の流れを示すフロー
チャートである。
パケット中継装置が１パケットを受信した場合の動作を述べる。
【００６２】
ステップＳ４０１において、パケット受信部１０２はパケットを受信する。
ステップＳ４０２において、パケット解析部１０３は受信したパケットのパケットヘッダを解析し、パケット種別（どの情報がパケットのどの位置にあるか）を特定する。
【００６３】
ステップＳ４０３において、パケットフロー識別部１０４はパケット解析部１０３で得た情報とＣＰＵ処理部１１０から得た情報から、パケット中継装置１０１でそのパケットがどのような処理をされるべきパケットかを特定する。例えば、パケットフィルタリングやQoS(Quality of Service) の適用可否を判断する。尚、パケットフロー識別部１０４の処理の詳細については後述する。
【００６４】
ステップＳ４０４において、パケットフィルタリング処理部１０５は、パケットフロー識別部１０４から得た情報を元にフィルタリング処理、すなわち不必要なパケットの廃棄を行う。尚、パケットフローフィルタリング処理部１０５の処理の詳細については後述する。
【００６５】
ステップＳ４０５において、パケット中継処理部１０６は、ＣＰＵ処理部１１０から得た情報から送信先を特定する処理や、パケットフロー識別部１０４の識別結果からＣＰＵ処理部１１０へ、パケットをコピー送信する判断をする等の処理を行う。
【００６６】
ステップＳ４０６において、トラフィック管理処理部１０７は、パケットフロー識別部１０４の識別結果に対応したQoSを提供する等、優先制御および帯域制御を管理する。また、パケット送信部１０８およびＣＰＵ処理部１１０へパケットを送信する。尚、ＣＰＵ処理部１１０におけるパケットの処理については後述する。
【００６７】
ステップＳ４０７において、パケット送信部１０８は、パケットを送信する。
次にステップＳ４０３におけるパケットフロー識別部１０４の処理の詳細について説明する。
【００６８】
図５は、本発明の第１の実施の形態に係るパケット中継装置のパケットフロー識別部の処理の流れを示すフローチャートである。
ステップＳ５０１において、パケット解析部１０３からパケットおよび解析情報を受信する。
【００６９】
ステップＳ５０２において、パケット解析部１０３で解析されたパケット種別ごとにＣＰＵ処理部１１０から指定されたフロー識別パターンに一致するかどうかを判定する。
ステップＳ５０３において、一致する場合はステップ５０４に進み、一致しない場合は終了する。
【００７０】
ステップＳ５０４において、一致したエントリのフローＩＤを装置内情報に追加し、パケットフィルタリング処理部１０５に通知する。フローＩＤは以降、フィルタリング処理や帯域制御、優先制御処理のためのパケット識別に用いられる。
【００７１】
次にステップＳ４０４におけるパケットフィルタリング処理部１０５の処理の詳細について説明する。
図６は、本発明の第１の実施の形態に係るパケット中継装置のパケットフィルタリング処理部の処理の流れを示すフローチャートである。
【００７２】
ステップＳ６０１において、パケットフィルタリグ処理部１０５は、パケットフロー識別部１０４からパケットおよび装置内情報（フローＩＤを含む）を受信する。
ステップＳ６０２において、パケットに付されたフローＩＤを参照して該パケットが廃棄対象か判定し、廃棄対象だった場合はステップＳ６０３に進み、そうでない場合は終了する。
【００７３】
ステップＳ６０３において、パケットを廃棄する。
次にステップＳ４０６において送信されたパケットを受信したＣＰＵ処理部１１０の処理について説明する。
【００７４】
図７は、本発明の第１の実施の形態に係るパケット中継装置のＣＰＵ処理部の処理の流れを示すフローチャートである。
ステップＳ７０１において、ＣＰＵ処理部１１０はトラフィック管理処理部１０７から送信されたパケットを受信する。
【００７５】
ステップＳ７０２において、セキュリティ処理部２０１は、受信したパケットに対して種々のセキュリティチェックを行い、特定のパターンを持つパケットに対し、フィルタリングの対象とすべきパケットかどうかを判定する。セキュリティチェックの方法としては、パケットが使用するポート番号等から判断するなど任意の方法が用いられ、従来より様々な方法が知られている。
【００７６】
ステップＳ７０３において、フィルタリング対象となるパケットが持つ特定のパターンの登録削除処理を行う。
次にステップＳ７０３の登録削除処理の詳細について説明する。
【００７７】
図８は、登録削除処理の詳細なフローチャートである。
ステップＳ８０１において、登録処理の場合はステップＳ８０２に進み、そうでない場合、すなわち削除処理の場合はステップＳ８１５に進む。
【００７８】
ステップＳ８０２において、登録するパターン（新規パターン）がインクリメンタルパターンであるかを判定する。インクリメンタルパターンであるかの判定処理については後述する。
【００７９】
ステップＳ８０３において、新規パターンがインクリメンタルパターンである場合には、ステップＳ８０４に進み、そうでない場合にはステップＳ８０７に進む。
ステップＳ８０４において、エントリの圧縮登録処理を行う。尚、エントリの圧縮登録処理についての詳細は後述する。
【００８０】
ステップＳ８０５において、削除タイマ値更新部２０６はエントリの削除タイマ値を更新する。
ステップＳ８０６において、エントリのマスクパターンより圧縮されているエントリ数を求め、圧縮エントリ数を更新する。
【００８１】
ステップＳ８０７において、通常の登録処理を行う。すなわち、フローテーブルにフロー識別パターンとして新規パターンを持つエントリを追加する。
ステップＳ８０８において、削除タイマ値更新部２０６は登録したエントリの削除タイマ値を設定する。
【００８２】
ステップＳ８０９において、登録エントリ数管理部２０４は登録エントリ数を現在フローテーブルに登録されているエントリ数に更新する。
ステップＳ８１０において、登録エントリ数管理部２０４は、エントリの圧縮を行うかどうかを判定する。具体的には、登録エントリ数管理２３０４は、登録エントリ数があらかじめ定められた値（登録数閾値）以上の場合は、圧縮登録を行うためステップＳ８１３に進み、そうでない場合はステップＳ８１１に進む。
【００８３】
図９は、圧縮処理判定の例を説明するための図である。
図９において、例えば、メモリテーブル９０１は登録可能なエントリの総数が２０であるとする。メモリテーブル９０１において、斜線部分は既にエントリが登録されていることを示し、白色部分はエントリが登録されていないことを示す。ここでは、９個のエントリが登録されている。また、登録数閾値は１０とする。
【００８４】
この場合、新たなエントリが登録されると、エントリの登録数は１０となり、登録数閾値以上となるため、登録エントリ数管理部２０４は登録エントリの圧縮を行う（ステップＳ８１３に進む）と判断する。このように、一定数以上のエントリが登録されると登録エントリの圧縮処理を行う。
【００８５】
ステップＳ８１１において、平均エントリ登録速度測定部２０３は、単位時間あたりのエントリの登録数（平均エントリ登録速度）を計測する。
ステップＳ８１２において、平均エントリ登録速度測定部２０３は、エントリの圧縮を行うかどうかを判定する。具体的には、平均エントリ登録速度測定部２０３は、残エントリ数（総エントリ数−現在登録されているエントリ数）を平均エントリ登録速度で割った値（登録余裕度）を求め、あらかじめ定められた値（閾値）と比較する。
【００８６】
登録余裕度が、閾値未満の場合はステップＳ８１３に進み、閾値以上の場合は終了する。
例えば、閾値は５とし、平均エントリ登録速度は１秒あたりの登録数とする。そして、登録エントリがない状態で、１秒あたり４エントリが登録されると、登録余裕度は、残エントリ数÷平均エントリ登録速度＝１６÷４＝４となる。よって、閾値未満であるので、平均エントリ登録速度測定部２０３は登録エントリの圧縮を行う（ステップＳ８１３に進む）と判断する。また、登録エントリがない状態で、１秒あたり１エントリの速度で４エントリが登録されると、登録余裕度は、１６÷１＝１６となる。よって、閾値以上であるので、平均エントリ登録速度測定部２０３は登録エントリの圧縮を行わないと判断する。このように、残エントリ数に対し、単位時間あたりの登録エントリ数が増加した場合に、登録エントリの圧縮処理を行う。
【００８７】
ステップＳ８１３において、ミラーテーブル管理部２０８に保持されているエントリの伸長を行う。尚、エントリの伸長処理の詳細については後述する。
ステップＳ８１４において、ステップＳ８１３で伸長したエントリのソートを実施する。ソートは、オフセット情報、パケット種別、フローＩＤ、および解除フラグが共通の値を持つエントリ同士で行われ、フロー識別パターンが昇順にソートされる。そしてソートされた順番で、エントリの登録依頼処理を行い、ステップＳ８０２に進む。圧縮エントリの伸長やソートは、ＣＰＵ処理部のミラーテーブル管理部２０８のテーブルを用いて行われる。再登録後、ミラーテーブル管理部２０８のテーブルの内容がパケットフロー識別部１０４のフローテーブルに書き込まれる。
【００８８】
ステップＳ８１５において、要求された識別フローパターンを含むエントリの削除処理を行う。尚、削除処理の詳細については後述する。
次にステップＳ８０２のインクリメンタルパターン判定処理について説明する。
【００８９】
図１０は、インクリメンタルパターン判定処理の詳細なフローチャートである。
ステップＳ１００１において、フローテーブルに登録する新規パターンと既に登録されている登録済みエントリのフロー識別パターンとを比較する。ここで、ステップＳ８０２から来た処理の場合は、最近の登録エントリを比較対象とし、ステップＳ８１４から来た処理に場合は、登録されている全てのエントリを比較対象とする。
【００９０】
ステップＳ１００２において、両者のマスクパターンが一致していればステップＳ１００３に進み、一致していなければステップＳ１００５に進む。また、新規パターンには、ドントケアビットはないため、新規パターンのマスクパターンは全て１である。従って、登録済みエントリのマスクパターンが全て１であるかどうかで判断しても良い。すなわち登録済みエントリのマスクパターンが全て１の場合はステップＳ１００３に進み、そうでない場合はステップＳ１００５に進む。
【００９１】
ステップＳ１００３において、新規パターンと登録済みエントリのフロー識別パターンとの差分が１ビットである場合、ステップＳ１００４に進み、そうでない場合ステップＳ１００５に進む。
【００９２】
ステップＳ１００４において、新規パターンはインクリメンタルパターンであると判断される。
ステップＳ１００５において、新規パターンは非インクリメンタルパターンであると判断される。
【００９３】
例として、新規パターン0001を登録する場合を説明する。新規パターンには、ドントケアビットに指定するビットがないので、そのマスクパターンは1111である。登録済みのエントリのフロー識別パターンおよびマスクパターンをそれぞれ0000および1111とする。以下の説明において、簡単のためにフロー識別パターンとマスクパターンをまとめて、フロー識別パターン（マスクパターン）と表現する。
【００９４】
ステップＳ１００２において、両者のマスクパターンを比較すると、共に1111である。従ってステップＳ１００３に進む。
ステップＳ１００３において、新規パターン0001と登録済みエントリのフロー識別パターン0000を比較すると、下位１桁目のビットのみが異なる。すなわち、差分が１ビット（１ビット変化）である。従って、ステップＳ１００４進み、新規パターン0001はインクリメンタルパターンであると判断される。
【００９５】
次に例として、新規パターン0101を登録する場合を説明する。新規パターンには、ドントケアビットに指定するビットがないので、そのマスクパターンは1111である。登録済みのエントリのフロー識別パターンおよびマスクパターンをそれぞれ0000および1111とする。
【００９６】
ステップＳ１００２において、両者のマスクパターンを比較すると、共に1111である。従ってステップＳ１００３に進む。
ステップＳ１００３において、新規パターン0101と登録済みエントリのフロー識別パターン0000を比較すると、下位１桁目と３桁目のビットが異なる。すなわち、差分が２ビット（２ビット変化）である。従って、ステップＳ１００５進み、新規パターン0011は非インクリメンタルパターンであると判断される。
【００９７】
次にステップＳ８０３の圧縮登録処理について説明する。
図１１は、圧縮登録処理の詳細なフローチャートである。
ステップＳ１１０１において、ステップＳ１００１で比較対象とした登録済みエントリのフロー識別パターンと登録要求されたパターンとの差分の位置のビットをドントケアビ
ットに指定するように、該登録済みエントリのマスクパターンを変更する。
【００９８】
ステップＳ１１０２において、マスクパターンを変更したエントリ、すなわち圧縮したエントリのフロー識別情報と１つ前のエントリのフロー識別情報とを比較する。
ステップＳ１１０３において、圧縮したエントリのマスクパターンと１つ前のエントリのマスクパターンを比較する。それらが一致していればステップ１１０４に進み、一致していなければ終了する。
【００９９】
ステップＳ１１０４において、圧縮したエントリの識別パターンと１つ前のエントリのフロー識別情報との差分が１ビットであればステップ１１０５に進み、そうでなければ終了する。
【０１００】
Ｓ１１０５ステップにおいて、差分の位置のビットをドントケアビットに指定するように１つ前のエントリのマスクパターンを更新する。
図１２は、圧縮エントリ伸長処理の詳細なフローチャートである。
【０１０１】
ステップＳ１２０１において、伸長するエントリのマスクパターンの０の位置を検出する。
ステップＳ１２０２において、フロー識別パターンのマスクパターンの０の位置に対応する位置（すなわち、ドントケアビットの位置）を「２の“マスクパターンの０の個数乗”」個の伸長パターン（００…０から１１…１まで、すなわちマスクパターンの０の個数桁のパターンにおける０と１の全ての組み合せ）に伸長する。
【０１０２】
例として、フロー識別パターンが00000e000004、マスクパターンがfffffffffffcのエントリを伸長する場合を説明する。
簡単のため、フロー識別パターンおよびマスクパターンの上位１１桁の表示を省略して説明する。フロー識別パターンおよびマスクパターンは4およびcなので、それぞれ２進数で表すと0100と1100となる。
【０１０３】
ステップＳ１２０１において、マスクパターンの０の位置を検出すると、マスクパターンは1100なので下位１桁目と２桁目が該当する。
ステップＳ１２０２において、フロー識別パターンのドントケアビットの位置を２の０の個数乗個の伸長パターンに伸長する。すなわち、フロー識別パターン0100の下位１桁目と２桁目のビットを00、01、10、11に伸長する。これによりフロー識別パターンは、0100、0101、0110、0111の４つのパターンに伸長される。すなわち１６進数で全ての桁を表示すると、フロー識別パターンが00000e000004、マスクパターンがfffffffffffcのエントリはフロー識別パターンが00000e000004、00000e000005、00000e000006、00000e000007の４つのエントリに伸長される。尚、伸長されたエントリのマスクパターンはffffffffffffである。
【０１０４】
図１３は、削除処理の詳細なフローチャートである。
ステップＳ１３０１において、フロー識別に用いないパターンである解除パターンが圧縮エントリ内にあるか判定し、圧縮エントリ内にある場合はステップＳ１３０２に進み、圧縮されたエントリ内に無い場合は、ステップＳ１３０６に進む。
【０１０５】
ステップＳ１３０２において、解除パターンをフローテーブルに追加する。このとき、解除パターンは、フロー識別に用いるパターンを含むエントリの上部に追加される。
ステップＳ１３０３において、解除パターンを含んでいたエントリの解除パターン数を更新する。具体的には解除パターン数に１を加える。
【０１０６】
ステップＳ１３０４において、解除パターンを更新したエントリの圧縮エントリ数から解除パターン数を引いた値を求める。その値が１より大きいときは、ステップＳ１３０５に進み、１以下のときはステップＳ１３０７に進む。
【０１０７】
ステップＳ１３０５において、登録エントリ数管理部は登録エントリ数を更新する。
ステップＳ１３０６において、フローテーブルに登録されているエントリから、解除パターンに対応するエントリを削除する。
【０１０８】
ステップＳ１３０７において、圧縮エントリの伸長処理を行う。
ステップＳ１３０８において、解除フラグが１のエントリと該エントリに対応するエントリ（すなわち、解除フラグが０のエントリで各種情報（フロー識別パターンや比較位置（オフセット）情報など）と解除フラグが１のエントリの各種情報とが一致するエントリ）を削除する。
【０１０９】
ステップＳ１３０９において、伸長したエントリの解除パターン数を更新する。具体的には、解除パターン数を０にする。
次にタイマ満了によるエントリの削除について説明する。
【０１１０】
図１４は、削除タイマ値更新部の一部の処理の流れを示すフローチャートである。
ステップＳ１４０１において、削除タイマ値更新部２０６は、各エントリの削除タイマ値を減算する。
【０１１１】
ステップＳ１４０２のおいて、タイマが満了したかを判定する。すなわち、削除タイマ値が所定の値になったかを判定する。例えば、削除タイマ値を減算していき、削除タイマ値が00000001になったら満了したと判定する。タイマ満了と判定した場合はステップＳ１４０３に進み、そうでない場合はステップＳ１４０１に戻る。
【０１１２】
ステップＳ１４０３において、削除タイマ値更新部２０６は、タイマが満了したエントリをフローテーブルから削除するようにエントリ削除処理部２０５に指示を行う。
次に実際に登録、削除、圧縮、および伸長を行った場合の例について説明する。
【０１１３】
図１５Ａ、Ｂ、およびＣは、フローテーブルの例を示す図である。
現在、フローテーブル１５０１には、フロー識別バターン、マスクパターン、比較位置（オフセット）情報、パケット種別、フローＩＤ、圧縮エントリ数、解除パターン数、削除タイマ値、解除フラグがそれぞれ、00000e000001、ffffffffffff、0、ＴＡＧ無し，IP、3、0、0、ffffffffffff、0のエントリが登録されている。ここでは、ＭＡＣ  ＤＡ（Destination Address）が登録されている例を示す。フローＩＤ＝３は、装置内で廃棄対象となるパケットであることを示す。
【０１１４】
ここで新たにフロー識別パターンが00000e000002と00000e000003であるパターンを登録すると、フローテーブル１５０２のようになる。
00000e000002を登録する時、00000e000002は00000e000001に対して圧縮できるか、すなわちインクリメンタルパターンであるか判定される（ステップＳ８０２）。
【０１１５】
第１行目のエントリのフロー識別パターン00000e000001と第２行目のエントリのフロー識別パターン00000e000002およびそれぞれのマスクパターンを比較する（ステップＳ１００１）。
【０１１６】
両者のマスクパターンは共にffffffffffffなので一致している（ステップＳ１００２）
以下の説明のおいて、各フロー識別パターンの上位１１桁は共通しているため、省略し
て表示することもある。第１行目および第２行目のエントリのフロー識別パターン1および2をそれぞれ２進数で表すと、0001および0010となる。これらを比較すると、下位１桁目と２桁目のビットが異なっている。従って、差分は２ビットである。よって、非インクリメンタルパターンであると判定され（ステップＳ１００５）、通常の登録処理が行われる（ステップＳ８０７）。
【０１１７】
また、00000e000003を登録する時、00000e000003は00000e000002に対して圧縮できるか、すなわちインクリメンタルパターンであるか判定される（ステップＳ８０２）。
同様にインクリメンタルパターン判定処理が行われる。2および3をそれぞれ２進数で表すと、0010および0011となるため、下位１桁目のビットのみが異なる。従って、差分は１ビットであり、インクリメンタルパターンであると判定される（ステップＳ１０００４）。
【０１１８】
00000e000003はインクリメンタルパターンであるため、圧縮登録処理（ステップＳ８０４）が行われ、フローテーブル１５０３に示されるように圧縮登録される。すなわち、第２行目のエントリのマスクパターンがfffffffffffe、圧縮エントリ数が２に変更される。また、削除タイマ値も新たに設定される。
【０１１９】
次に00000e000004、00000e000005、00000e000006、および00000e000007を登録する場合、同様にインクリメンタルパターン判定処理や圧縮登録処理等が行われ、フローテーブル１５０４のようになる。
【０１２０】
次にフロー識別パターンが00000e000004および00000e000005のエントリを削除する場合を説明する。これらの識別パターンが圧縮エントリ内にあるか判定すると（ステップＳ１３０１）、フローテーブル１５０４の３行目のエントリ00000e000004(fffffffffffc)内にあるため、解除パターンとして00000e000004および00000e000005がフローテーブルに登録される（ステップＳ１３０２）。すなわち、これらはフローテーブルの上部に登録され、解除フラグは１となっている。そして、３行目のエントリの解除パターン数の更新（ステップＳ１３０３）や圧縮エントリ数の更新（ステップＳ１３０５）が行われ、フローテーブル１５０５のようになる。
【０１２１】
さらにフローパターンが00000e000007のエントリを削除すると、上記と同様の処理が行われ、解除パターンとして00000e000007がフローテーブルに登録され（ステップＳ１３０２）、テーブル１５０６のようになる。
【０１２２】
そして、圧縮エントリ数−解除パターン数を計算すると（ステップＳ１３０４）、４−３＝１となるため、圧縮エントリ伸長処理（ステップＳ１３０７）が行われ、フローテーブル１５０７のようになる。さらに、解除パターン（第１行目から第３行目までのエントリ）の削除および該解除パターンに対応するエントリ（第６行目、第７行目、および第９行目のエントリ）の削除が行われる（ステップ１３０８）。解除パターン数の更新（ステップ１３０９）が行われた後、フローテーブル１５０８のようになる。
【０１２３】
次にフロー識別パターンが00000e000000であるパターンを登録すると、通常登録処理（ステップＳ８０７）され、フローテーブル１５０９にようになる。この時、圧縮処理判定（ステップＳ８１０またはＳ８１２）において、圧縮処理を行うと判定されると、圧縮エントリの伸長処理（ステップＳ８１３）が行われ、昇順にソートされ（ステップＳ８１４）、フローテーブル１５１０のようになる。
【０１２４】
そして、ソートされたエントリを昇順に再度、登録処理を行う。すると、フローテーブルの第１行から第４行までのエントリが圧縮され、フローテーブル１５１１に示されるよ
うに１つのエントリに圧縮される。
【０１２５】
このように、動的にエントリを追加や削除をした場合にも、エントリの圧縮や伸長を動的に行うことにより、多くのパターンを登録することが出来る。
図１６は、本発明の第２の実施に形態に係るパケット中継装置のブロック図である。
【０１２６】
第２の実施に形態に係るパケット中継装置１０１は、第１の実施に形態に係るパケット中継装置と同様にパケット受信部１０２、パケット解析部１０３、パケットフロー識別部１０４、パケットフィルタリング処理部１０５、パケット中継処理部１０６、トラフィック管理処理部１０７、パケット送信部１０８、パケットバッファ部１０９、およびＣＰＵ処理部１１０を備え、各構成部はバスにより接続される。
【０１２７】
パケットフロー識別部１０４は、フローテーブル１１１を備える。
ＣＰＵ処理部１１０は、動的エントリ圧縮伸長部１１２およびフロー識別対象パターン検出登録削除部１１３を備える。
【０１２８】
第２の実施に形態に係るパケット中継装置１０１の構成は、パケットフィルタリング処理部１０５がフィルタリングテーブル１１４を備え、パケットフィルタリング処理部１０５が動的エントリ圧縮伸長部１１２と接続している点が第１の実施の形態に係るパケット中継装置と異なる。
【０１２９】
フィルタリングテーブル１１４には、フローテーブル１１１と同様にパケットフィルタリング等の対象となるパケットのパターンが記述されている。また、動的エントリ圧縮伸長部１１２により、フィルタリングテーブル１１４のエントリの登録、削除、圧縮、および伸長が行われる。そして、パケットフィルタリング処理部１０５においても、フィルタリングテーブル１１４のエントリに基づき、どのような処理をされるべきパケットかを特定する。
【０１３０】
このようにパケットフロー識別部１０４およびパケットフィルタリング処理部１０５の両方でパケットの特定を行うことにより、二段階のフィルタリング処理が可能となる。
以上説明したことを概観すれば本発明は以下のような構成を備えるものである。
【０１３１】
（付記１）フロー識別の対象となるパケットのパターンが記述されたフローテーブルのエントリに基づきフロー識別を行うパケット中継装置におけるエントリ圧縮伸長方法において、
前記フローテーブルに新たに登録する新規パターンが前記エントリのフロー識別パターンに対し差分が１ビットであるインクリメンタルパターンであるか判定するステップと、
前期新規パターンがインクリメンタルパターンであった場合、フロー識別において前記フロー識別パターンに対するドントケアビットの位置を示す前記エントリのマスクパターンを変更するステップと、
前記新規パターンがインクリメンタルパターンでなかった場合、前記新規パターンを前記フローテーブルにエントリとして追加登録するステップと、
を備えるエントリ圧縮伸長方法。
（付記２）前記フローテーブルに登録されたエントリの数があらかじめ定められた値以上になったときに、
前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
残ったエントリをソートするステップと、
ソートした順番に再登録を指示するステップと、
をさらに備えることを特徴とする付記１記載のエントリ圧縮伸長方法。
（付記３）前記新規パターンを前記フローテーブルにエントリとして追加登録するステップにおいて、
登録可能な残りのエントリ数を一定時間あたりのエントリの登録速度で除算するステップと、
除算により算出した値があらかじめ定められた条件を満たした場合、
前記登録されたエントリのうち、圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
残ったエントリをソートするステップと、
ソートした順番に再登録を指示するステップと、
をさらに備えることを特徴とする請求項１記載のエントリ圧縮伸長方法。
（付記４）前記フローテーブルの前記エントリから特定のパターンを削除するときに、
該パターンが圧縮されたエントリにある場合には、該パターンをフロー識別に用いないことを示すフラグを含むエントリを登録するステップと、
をさらに備えることを特徴とする付記１乃至３記載のいずれか１項に記載のエントリ圧縮方法。
（付記５）
圧縮されたエントリに含まれるエントリ数が１になった場合に、
該圧縮されているエントリを伸長するステップと、
解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除するステップと、
をさらに備えることを特徴とする付記４記載のエントリ圧縮伸長方法。
（付記６）
エントリが登録されている時間を計測し、前記登録されている時間があらかじめ定められた値以上になった場合に該エントリを削除するステップ、
をさらに備えることを特徴とする付記１乃至５記載のいずれか１項に記載のエントリ圧縮方法。
（付記７）フロー識別の対象となるパケットのパターンが記述されたフローテーブルのエントリに基づきフロー識別を行うパケット中継装置において、
新規パターンを前記フローテーブルに登録する時に前記新規パターンが前記エントリのフロー識別パターンに対し差分が１ビットであるインクリメンタルパターンであるかどうか判定するインクリメンタルパターン判定手段と、
インクリメンタルパターンであると判定された場合に、前記フローテーブルのエントリに対し圧縮を行うエントリ圧縮伸長手段と、
を備えることを特徴とするパケット中継装置。
（付記８）前記フローテーブルに登録されているエントリ数を管理する登録エントリ数管理手段をさらに備え、
前記登録エントリ数管理手段は、登録されているエントリ数があらかじめ定められた値以上になったときに、前記エントリの圧縮指示を行うことを特徴とする付記７記載のパケット中継装置。
（付記９）前記フローテーブルに登録されるエントリの単位時間あたりの登録速度を測定する平均エントリ登録速度測定手段をさらに備え、
前記平均エントリ登録速度測定手段は、登録可能な残りのエントリ数を前記単位時間あたりの登録速度
で除算し、その値に基づきエントリの圧縮を指示することを特徴とする請求子７または８記載のパケット中継装置。
（請求項１０）前記エントリ圧縮伸長手段は、エントリの圧縮エントリ数が１の場合に、該エントリを伸長し、解除パターンを示すエントリおよび前記伸長したエントリのうち該解除パターンに対応するエントリを削除すことを特徴とする付記７乃至９のいずれか１項
に記載のパケット中継装置。
（請求項１１）
エントリの登録されている時間を測定する削除タイマ値更新手段をさらに備え、
前記削除タイマ値更新部は、エントリの登録されている時間が一定時間以上になった場合に、該エントリの削除を指示することを特徴とする付記７乃至１０のいずれか１項に記載のパケット中継装置。
【図面の簡単な説明】
【０１３２】
【図１】本発明の第１の実施の形態に係るパケット中継装置のブロック図である。
【図２】ＣＰＵ処理部のブロック図である。
【図３】本発明の第１の実施の形態に係るフローテーブルの例を示す図である。
【図４】本発明の第１の実施の形態に係るパケット中継装置の処理の流れを示すフローチャートである。
【図５】本発明の第１の実施の形態に係るパケット中継装置のパケットフロー識別部の処理の流れを示すフローチャートである。
【図６】本発明の第１の実施の形態に係るパケット中継装置のパケットフィルタリング処理部の処理の流れを示すフローチャートである。
【図７】本発明の第１の実施の形態に係るパケット中継装置のＣＰＵ処理部の処理の流れを示すフローチャートである。
【図８】登録削除処理の詳細なフローチャートである。
【図９】圧縮処理判定の例を説明するための図である。
【図１０】インクリメンタルパターン判定処理の詳細なフローチャートである。
【図１１】圧縮登録処理の詳細なフローチャートである。
【図１２】圧縮エントリ伸長処理の詳細なフローチャートである。
【図１３】削除処理の詳細なフローチャートである。
【図１４】削除タイマ更新部の処理の一部の流れを示すフローチャートである。
【図１５Ａ】フローテーブルの例を示す図。
【図１５Ｂ】フローテーブルの例を示す図。
【図１５Ｃ】フローテーブルの例を示す図。
【図１６】本発明の第２の実施の形態に係るパケット中継装置のブロック図である。
【図１７】従来のパケット中継装置のブロック図である。
【図１８】従来のパケット中継装置のパケットフロー識別部の詳細な図である。
【図１９】従来のパケット中継装置のブロック図である。
【符号の説明】
【０１３３】
１００    回線
１０１    パケット中継装置
１０２    パケット受信部
１０３    パケット解析部
１０４    パケットフロー識別部
１０５    パケットフィルタリング処理部
１０６    パケットバッファ部
１０７    パケット中継処理部
１０８    パケット送信部
１０９    トラフィック管理処理部
１１０    ＣＰＵ処理部
１１１    フローテーブル
１１２    動的エントリ圧縮伸長部
１１３    フロー識別対象検出登録削除部
１１４    フィルタリングテーブル
２０１    セキュリティ処理部
２０２    パターン登録処理部
２０３    平均エントリ登録速度測定部
２０４    登録エントリ数管理部
２０５    エントリ削除処理部
２０６    削除タイマ値更新部
２０７    エントリ圧縮伸長処理部
２０８    ミラーテーブル管理部
２０９    インクリメンタルパターン判定部
９０１    メモリテーブル
１７００    回線
１７０１    パケット中継装置
１７０２    パケット受信部
１７０３    パケット解析部
１７０４    パケットフロー識別部
１７０５    パケットフィルタリング処理部
１７０６    パケットバッファ部
１７０７    パケット中継処理部
１７０８    パケット送信部
１７０９    トラフィック管理処理部
１７１０    ＣＰＵ処理部
１７１１    フローテーブル
１７１２    フロー識別対象パターン登録削除部
１７１３    フロー識別対象パターン検出登録削除部
１７１４    パケット
【図１】
2008167340.tif 000003
【図２】
2008167340.tif 000004
【図３】
2008167340.tif 000005
【図４】
2008167340.tif 000006
【図５】
2008167340.tif 000007
【図６】
2008167340.tif 000008
【図７】
2008167340.tif 000009
【図８】
2008167340.tif 000010
【図９】
2008167340.tif 000011
【図１０】
2008167340.tif 000012
【図１１】
2008167340.tif 000013
【図１２】
2008167340.tif 000014
【図１３】
2008167340.tif 000015
【図１４】
2008167340.tif 000016
【図１５Ａ】
2008167340.tif 000017
【図１５Ｂ】
2008167340.tif 000018
【図１５Ｃ】
2008167340.tif 000019
【図１６】
2008167340.tif 000020
【図１７】
2008167340.tif 000021
【図１８】
2008167340.tif 000022
【図１９】
2008167340.tif 000023