Action based termination of multidimensional lookup

• US 7,317,723 B1
• Filed: 02/03/2004
• Issued: 01/08/2008
• Est. Priority Date: 02/03/2004
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Guru, Parthibhan Parama
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): ROBERTS, BRIAN S
• Application Number:
  US10/771,673
• Time in Patent Office: 1,435 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A technique classifies packets in a manner that enables the number of lookup operations performed when classifying a data packet to be reduced. A lookup operation is performed to identify a set of rules and a set of actions associated with the data packet. If the action is the same for all the rules represented in the set of rules, the data packet is classified in accordance with the action and further lookup operations are not performed. Otherwise, a next-level lookup operation is performed and the process is repeated. This process continues for successive levels until either a level is reached where the packet is classified or a final level is reached. If a final level is reached, an action is performed based on the results of the lookup operation at the final level.

Claims

1. A method for classifying a data packet in accordance with one or more rules wherein the data packet contains a packet header that is used to classify the packet, the method comprising the steps of:

dividing the packet header into a plurality of sections;

for each section, performing a lookup operation to acquire a set of rules and a set of actions associated the section, wherein the set of rules represents one or more rules associated with the section and the set of actions contains an action for each rule represented in the set of rules;

for a particular section, determining if each action in the set of actions indicates the same action for all the rules represented in the set of rules associated with the section; and

if so, classifying the data packet based on the action indicated in the set of actions for the particular section.

2. A method as defined in claim 1 comprising the steps of:

determining if the lookup operation performed is a final lookup operation; and

if so, classifying the data packet according to the results of the lookup operation.

3. A method as defined in claim 2 wherein the final lookup operation yields a results table index.

4. A method as defined in claim 3 comprising the step of:

using the results table index to identify an action that is used to classify the data packet.

5. A method as defined in claim 1 comprising the step of:

for the particular section, if each action in the set of actions is not the same, performing a next-level lookup operation to identify a set of rules and a set of actions associated with a next level of classification.

6. A method as defined in claim 1 wherein the acquired set of rules is represented as a rule bitmap and the identified set of actions is represented as an action bitmap.

7. A method as defined in claim 6 comprising the steps of:

for each section, using a value associated with the section to index a first-level lookup table to acquire an equivalence set index associated with the section; and

using the equivalence set index to acquire a first-level rule bitmap and a first-level action bitmap associated with the section.

8. A method as defined in claim 7 comprising the steps of:

determining if the acquired action bitmap indicates the same action for all rules represented in the rule bitmap; and

if so, classifying the packet based on the action indicated in the acquired action bitmap.

9. A method as defined in claim 7 comprising the step of:

determining if the acquired action bitmap indicates the same action for all rules represented in the rule bitmap; and

if not, performing a next-level lookup operation.

10. A method as defined in claim 1 comprising the steps of:

applying values associated with the sections to first-level lookup tables to acquire equivalence set indices associated with the section;

generating a next-level lookup table index using the equivalence set indices;

applying the next-level lookup table index to a next-level lookup table to acquire a next-level lookup table entry;

determining if the next-level lookup table entry is empty; and

if so, generating a next-level lookup table entry and a next-level equivalence set entry associated with the next-level lookup table index.

11. An apparatus for classifying a data packet in accordance one or more rules, using a hierarchy of lookup tables, the hierarchy comprising a first level and one or more successive levels, the data packet containing a packet header that is used to classify the packet, the apparatus comprising:

a memory coupled to the processor and configured to hold the hierarchy of lookup tables; and

a processor adapted to (i) divide the packet header into a plurality of sections, (ii) perform a lookup operation for each section in a first-level lookup table associated with the first level to acquire a set of rules and a set of actions associated with the rules for the section, (iii) determine if the action specified for each rule in the set of rules is the same, (iv) and if so, classifying the packet according to the action.

12. An apparatus as defined in claim 11 wherein the processor is configured to perform a next-level lookup operation if the action specified for each rule in the set of rules is not the same.

13. An apparatus as defined in claim 11 wherein the processor is configured to determine if the lookup operation is a final lookup operation and if so, classify the data packet according to the results of the lookup operation.

14. An apparatus as defined in claim 11 wherein the acquired set of rules is represented as a rule bitmap and the identified set of actions is represented as an action bitmap.

15. An apparatus as defined in claim 14 wherein the processor is configured to, for each section, acquire an equivalence set index associated with the section and use the equivalence set index to index an equivalence set to acquire a rule bitmap and action bitmap associated with the section.

16. An apparatus as defined in claim 15 wherein the processor is configured to determine if the acquired action bitmap indicates the same action for all rules represented in the rule bitmap and if so, classify the packet based on the action indicated in the identified action bitmap.

17. An apparatus as defined in claim 15 wherein the processor is configured to determine if the identified action bitmap indicates the same action for all rules represented in the rule bitmap and if not, perform a next-level lookup operation.

18. An intermediate node comprising:

means for dividing the packet header into a plurality of sections;

means for performing a lookup operation to acquire a set of rules and a set of actions associated with each section, wherein the set of rules represents one or more rules associated with a section and the set of actions contains an action for each rule represented in the set of rules;

means for determining, for each section, if each action in the set of actions indicates the same action for all the rules represented in the set of rules associated with the section; and

means for classifying the data packet based on the action indicated in the set of actions for the particular section if the action is the same.

19. An intermediate node as defined in claim 18 comprising:

means for determining if the lookup operation performed is a final lookup operation; and

means for classifying the data packet according to the results of the lookup operation if the lookup operation performed is the final lookup operation.

20. A computer readable medium encoded with computer executable instructions:

dividing a packet header, contained in a data packet that is used to classify the data packet, into a plurality of sections;

for each section, performing a lookup operation to acquire a set of rules and a set of actions associated the section, wherein the set of rules represents one or more rules associated with the section and the set of actions contains an action for each rule represented in the set of rules;

for a particular section, determining if each action in the set of actions indicates the same action for all the rules represented in the set of rules associated with the section; and

if so, classifying the data packet based on the action indicated in the set of actions for the particular section.