Packet classification search device and method

• US 6,718,326 B2
• Filed: 08/10/2001
• Issued: 04/06/2004
• Est. Priority Date: 08/17/2000
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Uga, Masanori, Shiomoto, Kohei
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/927,284
• Publication Number:
  US 20020023080A1
• Time in Patent Office: 970 Days
• Field of Search: 707/3, 707/6, 707/7, 370/389, 370/392, 370/401, 370/412, 709/220-225, 711/108
• US Class Current: 1/1
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A packet classification search device and method are implemented which are capable of searching rules of packet classification having very long search bit width at high speed while using a CAM which has a limited bit width. The fields of rules of packet classification are grouped into groups, and the grouped fields of each rule are stored along with search related information (except for the initial group) and number of searches information in a CAM. The next number of searches information (if further groups exist which must be searched), comparison related information, and actions related to packets (if further groups exist which must be searched, directing searching again, while if no further groups exist which must be searched, actions for packet classification) are stored in a search result storage device. By doing this it is made possible to search with the bit width of the group unit.

Claims

1. A packet classification search device which, based upon fields included in packets which are used to classify the flow of said packets, searches through a rule table comprising a plurality of rules which combine said fields and actions to be performed in relation to packets of which the flow is classified by said fields, and determines actions to be performed in relation to said packets, comprising:

a content addressable memory which combines and stores grouped fields which have been grouped from fields included in said rules into a plurality of groups determined in advance, and number of searches information and search related information which respectively show the groups and the rules to which said grouped fields are related;

a search result storage device which stores, in correspondence to said combinations which are stored in said content addressable memory, actions which are to be performed when combinations of grouped fields, number of searches information and search related information that have been inputted to said content addressable memory are found in said content addressable memory, and comparison related information which show the rules to search when next searching in said content addressable memory; and

;

a processing device which;

extracts said fields from packets which have been inputted and generates said grouped fields;

inputs into said content addressable memory and searches said number of searches information and said search related information which show the groups and rules which should be searched, and said grouped fields which correspond to said groups;

obtains said actions and said comparison related information which are stored in said search result storage device in correspondence to combinations which have been searched in said content addressable memory; and

, until the details of the actions which are to be performed as said actions upon said packets are obtained, again inputs to said content addressable memory said number of searches information which shows the groups which should next be searched, said grouped fields which correspond to said groups, and said comparison related information which has been obtained, and performs said searching again.

2. A packet classification search device according to claim 1, wherein said processing device groups said fields which are included in the rules in said rule table and generates said grouped fields;

generates said number of searches related information, said search related information, and said comparison related information based upon the rules and the groups which are related to the grouped fields which have been generated, and, along with combining said number of searches information, said search related information, and said grouped fields which have been generated and storing them in said content addressable memory, combines and stores in said search result storage device said comparison related information which has been generated and said actions which are included in the rules which said comparison related information shows.

3. A packet classification search device according to claim 2, wherein said processing device allocates group numbers to said groups in advance as number of searches information in order to identify said groups, and combines and stores in said content addressable memory said grouped fields and said group numbers which have been allocated to groups to which said grouped fields are related.

4. A packet classification search device according to claim 2, wherein said processing device determines, for each rule, a rule number for identifying said rules as said search related information and said comparison related information;

in relation to the group which is initially to be the subject of search for a packet which has been inputted, combines and stores in said content addressable memory said grouped fields and said search related information which is set by data which matches any rule number; and

, in relation to the groups other than said group which is initially to be the subject of search, combines and stores in said content addressable memory said grouped fields and said rule numbers which have been allocated to rules to which said grouped fields are related.

5. A packet classification search device according to claim 4, wherein said processing device:

when the next group which is required for searching the content addressable memory in relation to said combinations stored in said content addressable memory exists, combines and stores in said search result storage device the rule numbers which are allocated to the rules which should be searched when next searching said content addressable memory, and actions which direct searching said content addressable memory again; and

, when the next group which is required for searching the content addressable memory in relation to said combinations does not exist, stores in said search result storage device the actions which are to be performed upon packets which are inputted.

6. A packet classification search device according to claim 2, wherein said processing device, when grouping said fields which are included in said rules, determines whether or not there is a possibility that the plurality of grouped fields which are related to the same group may match to specified data, and, if there is a possibility of such matching, for said grouped fields with the exception of the grouped field among said plurality of grouped fields whose range is the narrowest, generates and adds to said rule table a new rule which has the same contents as those of said grouped field of which the range is the narrowest as the contents of said grouped fields for which there is a possibility of matching, and which has the same contents as the rule to which said grouped fields are related as the grouped fields other than the grouped fields for which there is a possibility of matching and as the action, and stores information in said content addressable memory and in said search result storage device based upon a rule table to which said new rule has been added.

7. A packet classification search device according to claim 6, wherein said processing device, when grouping fields which are included in said new rule, sets the contents of said comparison related information which is stored in said search result storage device to be the same as the comparison related information which is stored in said search result storage device in correspondence to the grouped field which has the narrowest range.

8. A packet classification search device according to claim 6, wherein:

if the combination of said grouped fields, said number of searches information, and said search related information which has been inputted matches a plurality of combinations which are stored in said content addressable memory, said content addressable memory selects from among the physical addresses at which said plurality of combinations are stored and outputs as search result according to some predetermined standard;

and if, during searching after expanding and storing the rule table to which said new rule has been added in said content addressable memory and said search result storage device, the combination of said grouped fields, said number of searches information, and said search related information which have been inputted into said content addressable memory matches a plurality of combinations which are stored in said content addressable memory, said processing device inserts said new rule into said rule table so that said content addressable memory outputs as search result the physical address which contains the grouped field which has the narrowest range from among the grouped fields which are included in said plurality of combinations.

9. A packet classification search device according to claim 2, wherein said processing device determines whether or not, among the rules in said rule table, there are present a plurality of rules the ranges of whose fields mutually overlap, and, if such a plurality of rules are present, for those rules among said plurality of rules excluding certain rules which are determined in advance, obtains ranges which do not overlap by excluding the range of overlap from the range of fields which are included in said rules, generates new rules corresponding to said ranges which do not overlap and replace said plurality of rules with said new rules, and stores information in said content addressable memory and in said search result storage device based upon a rule table in which said rules have been replaced.

10. A packet classification search device according to claim 1, wherein said fields are grouped so that the sum of the bit widths of said number of searches information, said search related information, and said grouped fields which are stored at each physical address of said content addressable memory agrees with the bit width of said content addressable memory.

11. A packet classification search method, which, based upon fields included in packets which are used to classify the flow of said packets, searches through a rule table comprising a plurality of rules which combine said fields and actions to be performed in relation to packets of which the flow is classified by said fields, and determines actions to be performed in relation to said packets, comprising the steps of:

a step of providing a content addressable memory to combine and store grouped fields which have been grouped from fields included in said rules into a plurality of groups determined in advance, and number of searches information and search related information which respectively show the groups and the rules to which said grouped fields are related, and of providing a search result storage device which stores, in correspondence to said combinations which are stored in said content addressable memory, actions which are to be performed when combinations of grouped fields, number of searches information and search related information that have been inputted to said content addressable memory are found in said content addressable memory, and comparison related information which show the rules to search when next searching in said content addressable memory;

a step of extracting said fields from packets which have been inputted and generating said grouped fields;

a step of inputting into said content addressable memory and searching said grouped fields which correspond to said groups which are to be initially searched and number of searches information which designates said groups;

a step of obtaining said actions and said comparison related information which are stored in said search result storage device in correspondence to search results which have been outputted from said content addressable memory;

a step of, if the action which has been obtained shows re-searching of said content addressable memory, again inputting number of searches information which shows the groups which should next be searched, said grouped fields which correspond to said groups and search related information which has the same contents as said comparison related information which has been obtained to said content addressable memory and performing searching; and

a step of, if said actions show details of actions which are to be performed upon the packets which are inputted, terminating the searching of said content addressable memory and outputting said details of said actions.

12. A packet classification search method according to claim 11, further comprising:

a step of, when grouping said fields which are included in said rules, determining whether or not there is a possibility of a plurality of grouped fields which are related to the same group matching to specified data, and, if there is a possibility of such matching, for said grouped fields with the exception of the grouped field among said plurality of grouped fields which has the narrowest range, generating and inserting into said rule table a new rule which has the same contents as those of the grouped field which has the narrowest range as contents of the grouped fields for which there is a possibility of matching, and which has the same contents as the rule to which said grouped fields are related as the contents of the grouped fields other than said grouped fields for which there is a possibility of matching and as the action; and

a step of storing information in said content addressable memory and in said search result storage device based upon a rule table to which said new rule has been added.

13. A packet classification search method according to claim 11, further comprising:

a step of determining whether or not among the rules in said rule table there exist a plurality of rules of which the ranges of the fields which are included in said rules mutually overlap, and, if such a plurality of rules exist, for said rules among said plurality of rules with the exception of a previously determined rule, obtaining ranges in which there is no overlap by excluding the range of overlap from the range of fields which are included in said rules, and generating new rules which correspond to said range in which there is no overlap to replace said plurality of rules with said new rules; and

a step of storing information in said content addressable memory and in said search result storage device based upon a rule table into which said rules have been replaced.