JP3757882B2 - Packet filtering method - Google Patents
Packet filtering method Download PDFInfo
- Publication number
- JP3757882B2 JP3757882B2 JP2002067061A JP2002067061A JP3757882B2 JP 3757882 B2 JP3757882 B2 JP 3757882B2 JP 2002067061 A JP2002067061 A JP 2002067061A JP 2002067061 A JP2002067061 A JP 2002067061A JP 3757882 B2 JP3757882 B2 JP 3757882B2
- Authority
- JP
- Japan
- Prior art keywords
- identifier
- filtering
- packet
- address
- data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、パケットのフィルタリング方法に関するものである。
【０００２】
【従来の技術】
従来の一般的なパケットフィルタリング技術では、パケットが持つユニークな識別子を利用し、
▲１▼破棄（フィルタリング）すべきパケットの識別子を全てデータベース（フィルタリングテーブル）に登録し、パケット到着時に、到着パケットの識別子をフィルタリングテーブルと照合した上で、フィルタリングテーブル上に同一識別子が存在する場合に、到着パケットを破棄するという方法か、あるいは逆に、
▲２▼破棄しないパケットの識別子を全てデータベース（フィルタリングテーブル）に登録し、パケット到着時に、到着パケットの識別子をフィルタリングテーブルと照合した上で、フィルタリングテーブル上に同一識別子が存在する場合にのみ、到着パケットをフィルタリング回路を通過させる
という方法があった。
【０００３】
図１にパケットフィルタリングのイメージを示す。
【０００４】
しかしながら▲１▼の技術では、排除すべきパケット（の識別子）の種別が多くなると、また▲２▼の技術では通過させるべきパケット（の識別子）の種別が多くなると、データベースの規模が肥大化するため、識別子の照合処理に時間を要し、フィルタリング速度が低下するという問題があった。
【０００５】
このフィルタリング速度の低下を防ぐために、フィルタリングテーブルを全て照合するのではなく、
▲３▼識別子の一部を用いて照合範囲を限定し、照合処理速度を高める
という技術も既に存在する、例えばＣＡＭ(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）で除したもの（各々の衝突率は同一）を示す。本発明が、衝突率とフィルタリングテーブルの規模の両方に大きな効果があることがわかる。
【図面の簡単な説明】
【図１】パケットフィルタリングの説明図である。
【図２】従来のフィルタリング技術の概要である。
【図３】本発明の処理の一例を示す流れ図である。
【図４】本発明の処理の一例である。
【図５】本発明のアルゴリズムの効果の例を図示したものである。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a packet filtering method.
[0002]
[Prior art]
Conventional general packet filtering technology uses a unique identifier of a packet,
(1) When all identifiers of packets to be discarded (filtered) are registered in the database (filtering table), and when the packet arrives, the identifier of the arrival packet is checked against the filtering table, and the same identifier exists in the filtering table. Or, discard the incoming packet, or conversely,
(2) All the identifiers of packets that are not discarded are registered in the database (filtering table), and when a packet arrives, the identifier of the arriving packet is checked against the filtering table and arrives only when the same identifier exists in the filtering table. There was a method of passing a packet through a filtering circuit.
[0003]
FIG. 1 shows an image of packet filtering.
[0004]
However, in the technique (1), when the types of packets (identifiers) to be eliminated increase, and in the technique (2), the types of packets (identifiers) to be passed increase, the scale of the database increases. Therefore, there is a problem that it takes time for the identifier collation process and the filtering speed decreases.
[0005]
To prevent this slowdown in filtering speed, instead of matching all the filtering tables,
{Circle around (3)} There is already a technique for limiting the collation range using a part of the identifier and increasing the collation processing speed, for example, CAM (Content Addressable Memory).
[0006]
Basically, the CAM generates an address from the data contents and stores only a bit indicating the presence or absence of the corresponding data. As a result, the presence / absence of the corresponding data can be determined. However, when the data value can take a wide range, the generated address space becomes wide, and a large memory space is required even if it is 1 bit wide.
[0007]
In the technique (3), a part of the identifier is used to calculate an address (address) in which a bit indicating the presence of data (identifier) in the filtering table is stored. When a packet arrives, an address on the filtering table can be calculated by looking at a part of the identifier, and therefore, collation is performed using a bit indicating the presence of data (identifier) stored at the address.
[0008]
In the technique (3), all filtering tables are referred to and collated in order to limit the collation range using a part of the unique identifier for calculating the data storage address. Compare processing speed increases compared to technology. A calculation formula is used as a method for obtaining a data storage address from a certain “part of identifier”, but this calculation formula requires one data storage address obtained from a single “part of identifier”. It is.
[0009]
In the CAM of the above technique (3), although only 1 bit is used as the amount of information indicating the presence of an identifier, the data range is too wide if the entire identifier information is used. That is, there is a problem that a huge memory space is required.
[0010]
In addition, when there are a plurality of identifiers having the same collation condition “part of identifiers” and different remaining identifier components, the data storage addresses calculated from these identifiers are the same, and only the presence of the identifier exists. Therefore, there is a problem that only one identifier can be registered in the filtering database, and the remaining identifiers cannot be determined by the filtering algorithm.
[0011]
FIG. 2 shows an outline of the filtering technique (3).
[0012]
In FIG. 2, a part of the identifier (the last three digits in the embodiment) is used as an address for storing the identifier in the filtering table.
[0013]
In the case of the input packet (1), since no data exists at the address (003) in the filtering table obtained from a part of the identifier, the packet passes through the filtering and is output.
[0014]
In the case of the input packet {circle over (2)}, data exists at the address (002) in the filtering table obtained from a part of the identifier, and the data matches, so the packet is discarded.
[0015]
In the case of the input packet (3), data exists at the address (002) in the filtering table obtained from a part of the identifier, but the filtering operation cannot be determined because the data does not match.
[0016]
In order to reduce the collision rate between packets of this “part of identifier”, that is, the probability that a plurality of packets having the same “part of identifier” need to be registered in the filtering table, statistically, The collation range (part of the identifier) may be expanded, but the convenience of using “part of the identifier” for calculation of the data storage address on the filtering table, inevitably the data storage address space is expanded, and as a result, the filtering table There was also a problem that the scale of the would increase.
[0017]
[Problems to be solved by the invention]
An object of the present invention is to improve the collision rate without enlarging the size of the filtering table.
[0018]
[Means for Solving the Problems]
In the present invention, the filtering table has a multi-stage configuration (first table, second table, third table,...) And has been devised for data registration and collation processing using a plurality of filtering tables.
A part of the identifier of the packet is stored as an identifier data at an address calculated from the identifier data of the filtering table,
In the packet filtering method for determining whether to pass or discard the arrival packet depending on whether or not the identifier of the arrival packet matches the data stored in the address of the filtering table obtained from a part thereof,
The filtering table has a multi-stage configuration,
The occupied memory space of each filtering table is the same,
When the identifier of the arrival packet does not match the data stored in the address obtained from the identifier of the arrival packet in the filtering table of a certain stage, the arrival packet is added to the address in the filtering table of the next stage by adding a fixed length to the address. Calculates the next address to be referred to, and checks whether or not it matches the data stored in the next address,
In the packet filtering method, the inspection is repeated while stepping through the steps of the filtering table until the identifier of the arrival packet matches the data stored at the address obtained from the identifier.
[0019]
Preferably, the addresses of the filtering tables of two adjacent stages are separated by a number larger than the number of addresses of the tables.
[0020]
Preferably, the address of the filtering table is given by a predetermined digit of the identifier of the arrival packet.
[0021]
DETAILED DESCRIPTION OF THE INVENTION
Each table configured in multiple stages in the algorithm of the present invention is separated by a fixed length in the data storage space. When registering an identifier in the filtering table, first register in the first table, and when it is necessary to register an identifier with the same "part of the identifier" and different identifier components in the filtering table, Register in the next table.
[0022]
In the following description, it is assumed that the registered identifier is an identifier of a packet to be discarded.
[0023]
FIG. 3 is a flowchart showing an example of the processing of the present invention. This flowchart is a flowchart when the filtering table has a two-stage configuration, and it is assumed that identifiers of packets to be discarded are stored in the two filtering tables.
[0024]
When the packet arrives (30), the data storage address in the first table is calculated using “part of the identifier” of the arrival packet (31), and the identifier is collated (32).
[0025]
If it is determined that there is no data as a result of the collation of the first table, the packet including the identifier is passed through the filtering circuit and output from the circuit (37).
[0026]
When it is determined as “data match” as a result of the collation of the first table, the packet including the identifier is discarded (33, 38).
[0027]
If it is determined as “data mismatch” as a result of the collation of the first table, the identifier is collated after obtaining the data storage address in the second table (34, 35).
[0028]
Since the second table is separated from the first table by a fixed length in the data storage address space, for example, if this fixed length is added to the result of calculating the data storage address from “part of the identifier”, the second table The data storage address to be collated can be calculated.
[0029]
When it is determined that there is no data as a result of the collation in the second table (35), the packet including the identifier is passed through the filtering circuit and output from the circuit (37).
[0030]
When it is determined as “data match” as a result of the collation in the second table (36), the packet including the identifier is discarded (38).
[0031]
When it is determined as “data mismatch” as a result of the collation of the second table, the identifier is collated after obtaining the data storage address in the third table.
[0032]
As described above, when there is data in each table but none of the data matches the identifier of the arrival packet, the collation processing proceeds to the subsequent table, and the result of collation in the last table is “no data” or “data mismatch”. The packet including the identifier passes through the filtering circuit and is output from the circuit.
[0033]
FIG. 4 shows an example of the processing of the present invention. This is also an example of a case where the filtering table has a two-stage configuration, and it is assumed that identifiers of packets to be discarded are stored in the two filtering tables (FIG. 4A). The data storage address uses the lower three digits of the packet identifier (all 10 digits), and the two filtering tables are separated by 2000 in the address space. At this time, the calculation method of the data storage address in the first table is to extract the lower three digits of the packet identifier and use it as the data storage address. In the second table, the address of the first table is 2000. Is added.
[0034]
Next, the filtering operation will be described with reference to FIG.
(1) If there is no data (identifier) at the address (003) in the first table as a result of the first table collation (input packet (1)), the packet is not filtered and output from the filtering circuit. .
(2) As a result of the first table collation, when data exists at the address (000) in the first table and the data match (input packet (2)), the packet is discarded.
(3) If there is data at the address (001) in the first table and the data does not match as a result of the first table collation, 2000 is added to the data storage address of the first table. The data storage address (2001) on the second table is obtained and collation is performed on the second table.
As a result of the second table collation, if the data does not exist at the address (2001) or the data does not match (input packet (3)), the packet is not filtered and output from the filtering circuit.
(4) Data exists at the address (004) in the first table obtained from a part of the identifier, but because of the mismatch, 2000 is added to the address (2004) and collated with the second table.
As a result of the collation in the second table, when data exists at the address (2004) and the data match (input packet (4)), the packet is discarded.
[0035]
In the present invention, this can be implemented very easily.
[0036]
【The invention's effect】
If the size of the identifier is mbit (a positive integer) and the size of “part of the identifier” used for the collation process is nbit (a positive integer that satisfies m ≧ n), it is necessary for the technique (3). The size of the filtering table is m · 2 n bits.
[0037]
The scale of the filtering tables (plural tables) necessary in the present invention is k · m · 2 n bits, where k is a positive integer.
[0038]
Here, in the conventional technique of (3), the collision rate is 2 −n because it is sufficient that there are two packets having the same “part of identifier” and different “remaining identifier components”. It is. The collision rate in the present invention is (2 −n ) k, that is, 2 because the filtering becomes impossible when there are k + 1 packets having the same “part of identifier” and different “remaining identifier components”. -Kn .
[0039]
In order to reduce the collision rate in the conventional technique (3) to 2- kn , which is the collision rate in the present invention, it is necessary to expand the size of “part of the identifier” to knbit. The required scale for the filtering table is m · 2 kn bits.
[0040]
Therefore, according to the present invention, if the filtering table has the same scale as the prior art (3), there is an effect of reducing the collision rate by 2- n- 2- kn . If the collision rate is constant, the size of the filtering table can be reduced by m · 2 kn −k · m · 2 n bits, and n = log 2 k / (k−1) holds, [k = Other than 2, n = 1], it is effective in reducing the size of the filtering table.
[0041]
FIG. 5 shows an example of the effect of the algorithm of the present invention when the filtering table has a two-stage configuration. Curve (a) is obtained by dividing the collision rate according to the present invention (when the filtering table has a two-stage configuration) by the collision rate of the conventional technique (3) (the size of each filtering table is the same), and the curve (B) is obtained by dividing the size (bit) of the filtering table necessary for the present invention (when the filtering table has a two-stage configuration) by the size (bit) of the filtering table necessary for the conventional technique (3). (Each collision rate is the same). It can be seen that the present invention has a great effect on both the collision rate and the size of the filtering table.
[Brief description of the drawings]
FIG. 1 is an explanatory diagram of packet filtering.
FIG. 2 is an overview of a conventional filtering technique.
FIG. 3 is a flowchart showing an example of processing of the present invention.
FIG. 4 is an example of processing according to the present invention.
FIG. 5 illustrates an example of the effect of the algorithm of the present invention.
Claims (3)
到着パケットの識別子が、その一部から得られる前記フィルタリングテーブルの前記アドレスに格納されるデータと一致するか否かにより、前記到着パケットを通過させるか破棄するかを決定するパケットのフィルタリング方法において、
前記フィルタリングテーブルを多段構成とし、
前記各フィルタリングテーブルの占有メモリ空間は同一とし、
到着パケットの識別子がある段のフィルタリングテーブルの該到着パケットの識別子から得られるアドレスに格納されるデータと一致しないときは、前記アドレスに固定長を加えることで次の段のフィルタリングテーブルにおいて該到着パケットが参照すべき次アドレスを算出し、前記次アドレスに格納されるデータと一致するか否かを検査し、
到着パケットの識別子が、該識別子から得られるアドレスに格納されるデータと一致するまで、前記検査をフィルタリングテーブルの段を歩進させながら繰り返すことを特徴とする、パケットのフィルタリング方法。A part of the identifier of the packet is stored as an identifier data at an address calculated from the identifier data of the filtering table,
In the packet filtering method for determining whether to pass or discard the arrival packet depending on whether or not the identifier of the arrival packet matches the data stored in the address of the filtering table obtained from a part thereof,
The filtering table has a multi-stage configuration,
The occupied memory space of each filtering table is the same,
When the identifier of the arrival packet does not match the data stored in the address obtained from the identifier of the arrival packet in the filtering table of a certain stage , a fixed length is added to the address to add the arrival packet in the filtering table of the next stage Calculates the next address to be referred to, and checks whether or not it matches the data stored in the next address,
A packet filtering method characterized by repeating the inspection while stepping through the steps of the filtering table until an identifier of an arrival packet matches data stored at an address obtained from the identifier.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002067061A JP3757882B2 (en) | 2002-03-12 | 2002-03-12 | Packet filtering method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002067061A JP3757882B2 (en) | 2002-03-12 | 2002-03-12 | Packet filtering method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003273918A JP2003273918A (en) | 2003-09-26 |
| JP3757882B2 true JP3757882B2 (en) | 2006-03-22 |
Family
ID=29198571
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002067061A Expired - Lifetime JP3757882B2 (en) | 2002-03-12 | 2002-03-12 | Packet filtering method |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3757882B2 (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8195705B2 (en) | 2001-12-11 | 2012-06-05 | International Business Machines Corporation | Hybrid search memory for network processor and computer systems |
| JP3784054B2 (en) * | 2002-06-10 | 2006-06-07 | インターナショナル・ビジネス・マシーンズ・コーポレーション | Method and recording medium for rearranging MAC addresses |
| JP5206441B2 (en) * | 2009-01-21 | 2013-06-12 | 沖電気工業株式会社 | Packet identification apparatus, method and program |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS554605A (en) * | 1978-06-26 | 1980-01-14 | Fujitsu Ltd | Address decoding system |
| JPS61148556A (en) * | 1984-12-24 | 1986-07-07 | Hitachi Ltd | Control code detector of communication |
| JPS61201516A (en) * | 1985-03-05 | 1986-09-06 | Nec Corp | Pattern detection circuit |
| JPS622317A (en) * | 1985-06-27 | 1987-01-08 | Toshiba Corp | Multilevel comparison and coincidence detecting circuit |
| JPH01103341A (en) * | 1987-10-16 | 1989-04-20 | Nec Corp | Address detecting circuit |
| US5530806A (en) * | 1994-12-15 | 1996-06-25 | At&T Corp. | Method and apparatus for storing and retrieving routing information in a network node |
| JP3545858B2 (en) * | 1995-12-01 | 2004-07-21 | 株式会社東芝 | Network connection device and information search device |
| JP3520709B2 (en) * | 1997-03-13 | 2004-04-19 | 三菱電機株式会社 | Network address search method |
| JP2000022736A (en) * | 1998-07-06 | 2000-01-21 | Nec Eng Ltd | Routing entry search system, search method therefor, and recording medium recording control program therefor |
| JP3216630B2 (en) * | 1999-06-09 | 2001-10-09 | 日本電気株式会社 | Communication control device |
| JP2001326679A (en) * | 2000-05-15 | 2001-11-22 | Fujitsu Ltd | Information device, table search device, table search method, and recording medium |
| JP2002016638A (en) * | 2000-06-29 | 2002-01-18 | Mitsubishi Electric Corp | Routing information search device and computer-readable recording medium storing routing information search control data |
| JP3779619B2 (en) * | 2002-01-11 | 2006-05-31 | 日本電信電話株式会社 | Packet transfer device, network, program, and recording medium |
-
2002
- 2002-03-12 JP JP2002067061A patent/JP3757882B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2003273918A (en) | 2003-09-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7904642B1 (en) | Method for combining and storing access control lists | |
| US10091137B2 (en) | Apparatus and method for scalable and flexible wildcard matching in a network switch | |
| US20030204703A1 (en) | Multi-pass hierarchical pattern matching | |
| JP7170905B2 (en) | Traffic classification method and apparatus | |
| JP2010506322A (en) | Improvements to pattern detection | |
| US10218643B2 (en) | Apparatus and method for scalable and flexible access control list lookup in a network switch | |
| CN101848248B (en) | Rule searching method and device | |
| US7403526B1 (en) | Partitioning and filtering a search space of particular use for determining a longest prefix match thereon | |
| US12184544B1 (en) | Data compression for LPM in TCAM | |
| CN117539925A (en) | A data processing method, device, medium and equipment | |
| CN108664518B (en) | Method and device for realizing table look-up processing | |
| US7305519B1 (en) | Error protection for associative memory entries and lookup operations performed thereon | |
| US6687715B2 (en) | Parallel lookups that keep order | |
| JP3757882B2 (en) | Packet filtering method | |
| US9305115B1 (en) | Method and apparatus for reducing power consumption during rule searches in a content search system | |
| EP4704380A1 (en) | Method and apparatus for policy matching | |
| US10795580B2 (en) | Content addressable memory system | |
| US10091074B2 (en) | Hardware acceleration architecture for signature matching applications for deep packet inspection | |
| CN112187636A (en) | ECMP route storage method and device | |
| US12432211B2 (en) | Interleaved exact-match lookup table for multiple packet processing applications in a network device | |
| US7277438B2 (en) | Fast flexible range checking | |
| US20030223417A1 (en) | Method of processing data packets | |
| Ahmadi et al. | Modified collision packet classification using counting bloom filter in tuple space. | |
| CN114050997B (en) | Method and system for processing packets according to table lookup | |
| CN100396057C (en) | High-speed Packet Detection Method Based on Stateful Filtering Engine |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050201 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050301 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050415 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20051206 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20051219 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 3757882 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090113 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100113 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110113 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110113 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120113 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130113 Year of fee payment: 7 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |