Fast IP packet classification with configurable processor

• US 7,227,842 B1
• Filed: 04/23/2002
• Issued: 06/05/2007
• Est. Priority Date: 04/24/2001
• Status: Expired due to Fees

• Current Assignee: Tensilica Incorporated
• Original Assignee: Tensilica Incorporated
• Inventors: Ji, Hongbin, Carchia, Michael
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): Cho; Hong Sol
• Application Number:
  US10/133,689
• Time in Patent Office: 1,869 Days
• Field of Search: 370/230, 370/230.1, 370/235, 370/389, 370/392
• US Class Current: 370/235
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

A novel solution for fast packet classification includes a novel data structure to store classifier rules which enables fast packet classification, which structure employs bitmaps for each field of the incoming packet for which classification is desired. A fast packet classification algorithm using the novel data structure allows the matching rule with the highest priority to be quickly obtained. A novel rule update algorithm allows new classifier rules to be added into the data structure incrementally. In one practical implementation of a classification engine employing the structures and algorithms of the present invention, a configurable processor with customized instructions is used to accelerate packet classification.

Claims

1. A packet classification method comprising:

receiving a packet;

matching, using a processor, a plurality of fields of the packet against N classification rules, the matching step including, for each field;

associating equivalent IDs with respective values of the field,

associating a respective bitmap with each equivalent ID, the bitmap providing an indication of a matching classification rule, and

determining the bitmap associated with a value of the field in the packet;

determining a possible range of values associated with a field of the packet to be matched;

identifying the possible range of values as a first rudimentary interval with associated endpoints;

parsing a packet classifying rule to determine a matching range associated with the field;

identifying upper and lower ends of the matching range;

comparing the upper and lower ends of the matching range with the endpoints associated with the first rudimentary interval;

creating up to two new rudimentary intervals based on a case result of the comparing step;

associating adjusted endpoints with each of the first and up to two new rudimentary intervals in accordance with the case result and the upper and lower ends so as to facilitate packet classification based on the possible range of values of the packet field including the matching range; and

preparing to forward the packet using the packet classifying rule.

2. A method according to claim 1, further comprising:

associating bitmaps with each of the first and up to two new rudimentary intervals, the bitmaps providing an indication of whether the rule is matched in that rudimentary interval of the field.

3. A method according to claim 1, further comprising:

parsing a new rule to determine a new matching range associated with the field;

identifying new upper and lower ends of the new matching range;

comparing the new upper and lower ends of the new matching range with the adjusted endpoints associated with the first and up to two new rudimentary intervals;

creating up to two additional rudimentary intervals based on a case result of the new comparing step; and

associating adjusted endpoints with certain of the rudimentary intervals in accordance with the case result and the new upper and lower ends.