Method for policy matching using a hybrid TCAM and memory-based scheme
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14)
-
Specification