Method for policy matching using a hybrid TCAM and memory-based scheme

• US 20050262294A1
• Filed: 05/05/2004
• Published: 11/24/2005
• Est. Priority Date: 05/05/2004
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bitar, Nabil
• Application Number:
  US10/839,057
• Publication Number:
  US 20050262294A1
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

The invention defines a TCAM-Memory hybrid scheme that: (1) enables achieving high search rates unattainable with memory-based search alone, and (2) accommodates a large number of policies that cannot be achieved using TCAMs alone. In one exemplary embodiment of the hybrid scheme, an index of the head of an action list based on a fast TCAM search is first determined and then every action in the action list is extracted by memory reference as the actions are organized in the action list. If read latency becomes an issue, every action entry can contain the reference for two or more actions as required to be able to do back-to-back read as opposed to sequential read, reducing the latency problem. Assuming a best match, the TCAM can be configured to return a memory pointer to the head of an action list. Actions are daisy-chained in a strict order in memory and are applied to the packet in the same order. The ability to daisy-chain actions based on one rule saves classification rule entries in expensive TCAMs. This scheme avoids the alternative of having the action itself being returned as a result of the rule match, as this leads to an increase in the number of rules and in the number of searches required per packet.

Claims

1. A method for implementing a policy matching scheme for a computer system including TCAM memory, said method comprising:

providing a policy matching system having a rule database, a rule action list and an action database;

linking actions in a daisy-chain fashion based on a single rule so as to save classification entries.

2. The method of claim 1, wherein said action database includes an action ID, Action index and a next action pointer.

3. The method of claim 2, wherein a location and meaning of the action index are interpreted in the context of the action ID.

4. The method of claim 1, wherein rule types for the rule database are selected from the group consisting of:

IP classification, MPLS classification based on an incoming MPLS label, Ethernet classification, Point to point protocol over Ethernet (PPPoE) classification, and Layer 2 tunneling protocol classification.

5. The method of claim 1, wherein actions for said rule types are selected from the group consisting of:

Filter or Drop packet, IP meter, Mark the IP packet, MPLS policy based forwarding, ATM or MPLS policy based forwarding, and Tracing.

6. The method of claim 1, wherein different rules can share actions by pointing to a same action memory.

7. A method of reducing the number of TCAM rules for policy matching systems using a hybrid TCAM and memory-based methodology, said method comprising:

determining an index for a head of an action list based on a TCAM search;

.

performing each action it eh action list by memory reference as the actions are organized.

8. The method of claim 7, wherein an action entry includes a reference for two or more actions, thereby enabling back-to-back read operations.

9. A method for implementing a policy matching scheme for packets in a network element of a communications network, said method comprising:

configuring a TCAM memory in said network element to return a memory pointer to a head of an action list after determining a best match;

linking actions in an order in memory; and

applying said actions to a packet in a same order as in memory.

10. The method of claim 9, wherein an action includes an action ID, action index and a next action pointer.

11. The method of claim 10, wherein a location and meaning of the action index are interpreted in the context of the action ID.

12. The method of claim 9, wherein rule types for the rule database are selected from the group consisting of:

IP classification, MPLS classification based on an incoming MPLS label, Ethernet classification, Point to point protocol over Ethernet (PPPoE) classification, and Layer 2 tunneling protocol classification.

13. The method of claim 9, wherein actions for said rule types are selected from the group consisting of:

Filter or Drop packet, IP meter, Mark the IP packet, MPLS policy based forwarding, ATM or MPLS policy based forwarding, and Tracing.

14. The method of claim 9, wherein an action entry includes a reference for two or more actions, thereby enabling back-to-back read operations.