(57)【特許請求の範囲】
【請求項１】
パケットの識別子の一部を識別子データとして、フィルタリングテーブルの前記識別子データから算出されるアドレスに格納しておき、
到着パケットの識別子が、その一部から得られる前記フィルタリングテーブルの前記アドレスに格納されるデータと一致するか否かにより、前記到着パケットを通過させるか破棄するかを決定するパケットのフィルタリング方法において、
前記フィルタリングテーブルを多段構成とし、
前記各フィルタリングテーブルの占有メモリ空間は同一とし、
到着パケットの識別子がある段のフィルタリングテーブルの該到着パケットの識別子から得られるアドレスに格納されるデータと一致しないときは、前記アドレスに固定長を加えることで次の段のフィルタリングテーブルにおいて該到着パケットが参照すべき次アドレスを算出し、前記次アドレスに格納されるデータと一致するか否かを検査し、
到着パケットの識別子が、該識別子から得られるアドレスに格納されるデータと一致するまで、前記検査をフィルタリングテーブルの段を歩進させながら繰り返すことを特徴とする、パケットのフィルタリング方法。
【請求項２】
隣接する２つの段のフィルタリングテーブルのアドレスは該テーブルのもつアドレスの数より大きな数だけ離れている、請求項１記載のパケットのフィルタリング方法。
【請求項３】
前記フィルタリングテーブルの前記アドレスは前記到着パケットの前記識別子の所定の桁により与えられる、請求項１記載のパケットのフィルタリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットのフィルタリング方法に関するものである。
【０００２】
【従来の技術】
従来の一般的なパケットフィルタリング技術では、パケットが持つユニークな識別子を利用し、
▲１▼破棄（フィルタリング）すべきパケットの識別子を全てデータベース（フィルタリングテーブル）に登録し、パケット到着時に、到着パケットの識別子をフィルタリングテーブルと照合した上で、フィルタリングテーブル上に同一識別子が存在する場合に、到着パケットを破棄するという方法か、あるいは逆に、
▲２▼破棄しないパケットの識別子を全てデータベース（フィルタリングテーブル）に登録し、パケット到着時に、到着パケットの識別子をフィルタリングテーブルと照合した上で、フィルタリングテーブル上に同一識別子が存在する場合にのみ、到着パケットをフィルタリング回路を通過させる
という方法があった。
【０００３】
図１にパケットフィルタリングのイメージを示す。
【０００４】
しかしながら▲１▼の技術では、排除すべきパケット（の識別子）の種別が多くなると、また▲２▼の技術では通過させるべきパケット（の識別子）の種別が多くなると、データベースの規模が肥大化するため、識別子の照合処理に時間を要し、フィルタリング速度が低下するという問題があった。
【０００５】
このフィルタリング速度の低下を防ぐために、フィルタリングテーブルを全て照合するのではなく、
▲３▼識別子の一部を用いて照合範囲を限定し、照合処理速度を高める
という技術も既に存在する、例えばＣＡＭ(Content Addressable Memory)がある。
【０００６】
基本的にＣＡＭは、データ内容からアドレスを発生させ、該当データの存在の有無を示すビットのみが格納される。これにより該当データの存在の有無は判定できるが、データ値の取りうる値が広い場合、発生するアドレス空間も広くなり、たとえ１ビット幅であるにせよ、広大なメモリ空間を必要とする。
【０００７】
この▲３▼の技術においては、識別子の一部を用いて、フィルタリングテーブルでのデータ（識別子）の存在を示すビットが格納される番地（アドレス）を算出する。パケットが到着した際には、識別子の一部を見ればフィルタリングテーブル上のアドレスが算出できるため、そのアドレスに格納されたデータ（識別子）の存在を示すビットを用いて照合が行われる。
【０００８】
この▲３▼の技術では、データ格納アドレスの算出にユニークな識別子の、一部を使用して照合する範囲を限定するため、全てのフィルタリングテーブルを参照・照合する▲１▼、▲２▼の技術と比較して照合処理速度は高まる。ある「識別子の一部」からデータ格納アドレスを得る方法には算出式を用いるが、この算出式には単一の「識別子の一部」から得られるデータ格納アドレスは一つであることが必要である。
【０００９】
上述の▲３▼の技術のＣＡＭにおいては、識別子の存在を示す情報量としては１ビットしか使用しないものの識別子情報の全体を用いたのではデータ範囲が広すぎるため、必然的に膨大なアドレス空間、即ち膨大なメモリ空間が要求されるという問題があった。
【００１０】
また、照合条件である「識別子の一部」が同一で、残りの識別子構成部が異なる複数の識別子が存在する場合、これらの識別子から算出されるデータ格納アドレスは同一であり、識別子の存在のみを示す１ビットしか格納されないため、１つの識別子しかフィルタリングデータベースに登録できず、残りの識別子についてはフィルタリングアルゴリズム上判定不能になるという問題があった。
【００１１】
図２に▲３▼のフィルタリング技術の概要を示す。
【００１２】
図２ではフィルタリングテーブルで識別子の一部（実施例では下３桁）を識別子を格納するアドレスに用いる。
【００１３】
入力パケット▲１▼の場合は、識別子の一部から得られるフィルタリングテーブル内のアドレス(003)にデータが存在しないため、パケットはフィルタリングを通過し出力する。
【００１４】
入力パケット▲２▼の場合は、識別子の一部から得られるフィルタリングテーブル内のアドレス(002)にデータが存在し、かつデータが一致するためパケットは破棄する。
【００１５】
入力パケット▲３▼の場合は、識別子の一部から得られるフィルタリングテーブル内のアドレス(002)にデータが存在するが、データが一致しないため、フィルタリング動作を決定不能である。
【００１６】
この「識別子の一部」のパケット間での衝突率、すなわち「識別子の一部」が同じである複数のパケットをフィルタリングテーブルに登録する必要が発生する確率、を減ずるためには統計的に、照合範囲（識別子の一部）を拡大すれば良いが、フィルタリングテーブル上のデータ格納アドレスの算出に「識別子の一部」を用いる都合、必然的にデータ格納アドレス空間も拡大され、結果としてフィルタリングテーブルの規模が大きくなるという問題もあった。
【００１７】
【発明が解決しようとする課題】
本発明は、フィルタリングテーブルの規模をあまり大きくさせずに衝突率を改善することを目的とする。
【００１８】
【課題を解決するための手段】
本発明は、フィルタリングテーブルを多段構成（第一テーブル、第二テーブル、第三テーブル、…）とし複数のフィルタリングテーブルを用いたデータ登録と照合処理に工夫をしたもので、その特徴は、
パケットの識別子の一部を識別子データとして、フィルタリングテーブルの前記識別子データから算出されるアドレスに格納しておき、
到着パケットの識別子が、その一部から得られる前記フィルタリングテーブルの前記アドレスに格納されるデータと一致するか否かにより、前記到着パケットを通過させるか破棄するかを決定するパケットのフィルタリング方法において、
前記フィルタリングテーブルを多段構成とし、
前記各フィルタリングテーブルの占有メモリ空間は同一とし、
到着パケットの識別子がある段のフィルタリングテーブルの該到着パケットの識別子から得られるアドレスに格納されるデータと一致しないときは、前記アドレスに固定長を加えることで次の段のフィルタリングテーブルにおいて該到着パケットが参照すべき次アドレスを算出し、前記次アドレスに格納されるデータと一致するか否かを検査し、
到着パケットの識別子が、該識別子から得られるアドレスに格納されるデータと一致するまで、前記検査をフィルタリングテーブルの段を歩進させながら繰り返すパケットのフィルタリング方法にある。
【００１９】
好ましくは、隣接する２つの段のフィルタリングテーブルのアドレスは該テーブルのもつアドレスの数より大きな数だけ離れている。
【００２０】
好ましくは、前記フィルタリングテーブルの前記アドレスは前記到着パケットの前記識別子の所定の桁により与えられる。
【００２１】
【発明の実施の形態】
本発明のアルゴリズムにおいて多段構成された各テーブルは、データ格納空間上で固定長だけ離れている。フィルタリングテーブルに識別子を登録する際には、まず最初のテーブルに登録を行い、「識別子の一部」が同一で、残りの識別子構成部が異なる識別子をフィルタリングテーブルに登録する必要が発生した時には、次のテーブルに登録を行う。
【００２２】
なおここから先の説明では、登録された識別子は、破棄すべきパケットの識別子であることとする。
【００２３】
図３に本発明の処理の一例を示す流れ図を示す。この流れ図はフィルタリングテーブルが二段構成の場合の流れ図であり、二つのフィルタリングテーブルには、破棄すべきパケットの識別子を格納しているものとする。
【００２４】
パケット到着時(30)には、到着パケットの「識別子の一部」を用いて第一テーブル内のデータ格納アドレスを算出し(31)、識別子を照合する(32)。
【００２５】
第一テーブルの照合の結果「データなし」と判定されたときは、その識別子を含むパケットはフィルタリング回路を通過させ、回路から出力される(37)。
【００２６】
第一テーブルの照合の結果「データ一致」と判定されたときは、その識別子を含むパケットを破棄する(33,38)。
【００２７】
第一テーブルの照合の結果「データ不一致」と判定されたときは、次に第二テーブル内のデータ格納アドレスを得た上で識別子を照合する(34,35)。
【００２８】
第二テーブルは第一テーブルから、データ格納アドレス空間上で固定長だけ離れているため、例えば「識別子の一部」からデータ格納アドレスを算出した結果にこの固定長を加算すれば、第二テーブル上の照合すべきデータ格納アドレスが算出可能である。
【００２９】
第二テーブルの照合の結果「データなし」と判定されたときは(35)、その識別子を含むパケットはフィルタリング回路を通過させ、回路から出力される(37)。
【００３０】
第二テーブルの照合の結果「データ一致」と判定されたときは(36)、その識別子を含むパケットを破棄する(38)。
【００３１】
第二テーブルの照合の結果「データ不一致」と判定されたときは、次に第三テーブル内のデータ格納アドレスを得た上で識別子を照合する。
【００３２】
このように、各テーブルにデータが存在するものの、どのデータも到着パケットの識別子と一致しないときは、後段のテーブルヘ照合処理を進め、最後のテーブルにおいて照合の結果「データなし」または「データ不一致」と判定されたときに、その識別子を含むパケットはフィルタリング回路を通過させ、回路から出力される。
【００３３】
図４に本発明の処理の一例を示す。こちらもフィルタリングテーブルが二段構成の場合の例であり、二つのフィルタリングテーブル（図４（Ａ））には、破棄すべきパケットの識別子を格納しているものとする。またデータ格納アドレスは、パケットの識別子（全１０桁）のうち、下位３桁を使用するものとし、二つのフィルタリングテーブルはアドレス空間上で2000だけ離れているものとする。このとき、第一テーブルにおけるデータ格納アドレスの算出方法は、パケットの識別子の下位３桁を抽出し、それをデータ格納アドレスとするものであり、また第二テーブルでは、第一テーブルのアドレスに2000を加算したものである。
【００３４】
次に図４（Ｂ）によりフィルタリング動作を説明する。
▲１▼第一テーブル照合の結果、第一テーブル内のアドレス(003)にデータ（識別子）が存在しない場合（入力パケット▲１▼）には、パケットはフィルタリングされず、フィルタリング回路から出力される。
▲２▼第一テーブル照合の結果、第一テーブル内のアドレス(000)にデータが存在し、かつデータが一致した場合（入力パケット▲２▼）には、パケットは破棄される。
▲３▼第一テーブル照合の結果、第一テーブル内のアドレス(001)にデータが存在し、かつデータが一致しなかった場合には、第一テーブルのデータ格納アドレスに2000を加算することで第二テーブル上のデータ格納アドレス(2001)を得、第二テーブルでの照合が行われる。
第二テーブル照合の結果、アドレス(2001)にデータが存在しないか、またはデータが一致しなかった場合（入力パケット▲３▼）、パケットはフィルタリングされず、フィルタリング回路から出力される。
▲４▼識別子の一部から得られる第一テーブル内のアドレス(004)にデータが存在するが不一致のためアドレスに2000を加算(2004)して第二テーブルで照合する。
第二テーブルでの照合の結果、アドレス(2004)にデータが存在し、かつデータが一致した場合（入力パケット▲４▼）、パケットは破棄される。
【００３５】
本発明ではこのように非常に簡単に実施可能である。
【００３６】
【発明の効果】
識別子の大きさをｍbit（正の整数）、照合処理に使用する「識別子の一部」の大きさをｎbit（ｍ≧ｎが成立する正の整数）とすると、▲３▼の技術で必要なフィルタリングテーブルの規模は、ｍ・２ｎbitである。
【００３７】
また本発明で必要なフィルタリングテーブル（複数テーブル）の規模は、多段構成されたテーブルの数をｋ（正の整数）とすると、ｋ・ｍ・２ｎbitである。
【００３８】
ここで衝突率は、▲３▼の従来技術においては、同一の「識別子の一部」を持ち異なる「残りの識別子構成部」を持つパケットが二つ存在すれば十分であることから２−ｎである。また本発明における衝突率は、同一の「識別子の一部」を持ち異なる「残りの識別子構成部」を持つパケットがｋ＋１個存在するときフィルタリングが不能になるため、（２−ｎ）ｋすなわち２−ｋｎとなる。
【００３９】
従来の▲３▼の技術における衝突率を、本発明における衝突率の２−ｋｎにまで低減するためには、「識別子の一部」の大きさをｋｎbitにまで拡大する必要があり、その時のフィルタリングテーブルに必要な規模はｍ・２ｋｎbitである。
【００４０】
従って本発明によれば、フィルタリングテーブルが▲３▼の従来技術と同一規模ならば、衝突率を２−ｎ−２−ｋｎだけ減ずる効果がある。また衝突率が一定ならば、フィルタリングテーブルの規模をｍ・２ｋｎ−ｋ・ｍ・２ｎbitだけ減らすことが可能であり、ｎ＝log２ｋ／（ｋ−１）が成り立つ、［ｋ＝２、ｎ＝１］以外ではフィルタリングテーブルの規模縮小に効果がある。
【００４１】
図５に、フィルタリングテーブルが二段構成の場合の本発明のアルゴリズムの効果の例を示す。曲線（ａ）は本発明（フィルタリングテーブルが二段構成の場合）による衝突率を、従来の技術（▲３▼）の衝突率で除したもの（各々のフィルタリングテーブルの規模は同一）、および曲線（ｂ）は本発明（フィルタリングテーブルが二段構成の場合）に必要なフィルタリングテーブルの規模（bit）を、従来の技術（▲３▼）に必要なフィルタリングテーブルの規模（bit）で除したもの（各々の衝突率は同一）を示す。本発明が、衝突率とフィルタリングテーブルの規模の両方に大きな効果があることがわかる。
【図面の簡単な説明】
【図１】パケットフィルタリングの説明図である。
【図２】従来のフィルタリング技術の概要である。
【図３】本発明の処理の一例を示す流れ図である。
【図４】本発明の処理の一例である。
【図５】本発明のアルゴリズムの効果の例を図示したものである。
【図１】
0003757882.tif 000002
【図２】
0003757882.tif 000003
【図３】
0003757882.tif 000004
【図４】
0003757882.tif 000005
【図５】
0003757882.tif 000006