Content addressable memory with selectable mask write mode

Details Content addressable memory with selectable mask write mode Content addressable memory with selectable mask write mode

2001-10-31

2004-06-29

Sparks, Donald (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130, C709S238000

Reexamination Certificate

active

06757779

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to packet processing and more particularly to content addressable memory devices and systems.
BACKGROUND
Routers are devices that direct traffic in a network. Each router in the network has a route table that typically includes routing information to enable incoming packets to be forwarded or routed to their destination in the network. Some routers forward packets based only on the destination address indicated in the packet. Other, more complex, routers forward or route packets based on policies defined, for example, by a network administrator. The latter routing schemes are commonly referred to as policy-based routing.
Policy-based routing can enable packets to be forwarded or routed in a network based on any number of criteria, including the source of the packet, the destination of the packet, the cost of forwarding the packet through different routes or paths in the network, or the bandwidth available on different routes in the network. Policy-based routing can also be used to provide a certain Quality of Service (QOS) or Type of Service (TOS) to differentiated traffic in the network. For example, one or more of the various fields (e.g., the TOS bits) in the header of an Internet Protocol (IP) packet can be used by policy-based routers to forward EP packets in a network.
Each policy-based router implements a policy through the use of route maps that define how to forward the packet in the network. Each route map statement or policy statement contains one or more match clauses and a set clause. The match clauses are a series of conditions that are used to determine if an incoming packet satisfies a particular policy. If all of the match clauses of a policy statement are satisfied, the set clause specifies how the router should forward the packet in the network. If one of the match clauses of a particular policy statement is not satisfied, then the policy-based router investigates subsequent policy statements.
FIG. 1
shows exemplary processed policy information
100
of an incoming packet to a policy-based router. Policy information
100
includes several policy fields
102
including a destination address (DA) for the packet, a source address (SA) of the packet, protocol type (PTCL) such as those defined by for an EP packet header, TOS, and COST. Policy information
100
may be received by a policy-based router that implements a policy such as policy
200
shown in FIG.
2
. Policy
200
includes three separate policy statements
201
through
203
. If policy information
100
satisfies the match clause (i.e., the “if” clause) of one of the policy statements, the set clause (i.e., the “then” clause) of that policy statement determines routing information for the packet in the network. For example, if the destination address of the incoming packet is DA
1
, the source address is SA
1
, and the TOS field of the packet is TOS
1
, then routing information RI
2
should be selected.
A policy-based router can use a content addressable memory (CAM)-based system to implement a filtering or classification function to determine whether an incoming packet matches a policy statement.
FIG. 3
shows one example of a system
300
that implements policy-based routing using a ternary CAM
302
. The policy statements or policy words
201
-
203
are stored in separate rows in ternary CAM array
304
. A ternary CAM array is one that is able to mask entries in a CAM array on a bit-by-bit basis. Ternary CAM array
304
has rows of CAM cells
305
for storing policy field information, and corresponding rows of mask cells
310
for storing mask data. Routing information RI
0
-RI
2
is typically stored in an external memory
308
at addresses corresponding to those at which the respective policy words
201
-
203
are stored in ternary CAM array
304
. Each policy field that corresponds to a match clause for a given policy statement is unmasked by having its corresponding mask bits set, for example, to a logic zero. Conversely, each policy field that does not have a match clause for a given policy statement is masked by having its corresponding mask bits set, for example, to a logic one.
When an incoming packet is received by a policy-based router, it is processed to determine the policy field information. The processed policy field information is provided to system
300
as policy search key
307
. For each policy statement in CAM array
304
that matches the policy search key, the corresponding match line ML
0
-ML
N
will be asserted and provided to priority encoder
306
. In response to the match lines, priority encoder
306
outputs the address of the highest priority matching entry in CAM array
304
to HPM bus
312
. If there is more than one matching policy statement in CAM array
304
, priority encoder
306
determines that the highest priority matching policy statement is the one stored at the lowest logical address of CAM array
304
. For example, as shown in
FIG. 3
, if CAM array
304
is loaded with policy statement
203
at address zero (i.e., the lowest logical address), statement
202
at address one, and statement
201
at address
2
, and a policy search key of DA
1
, SA
1
, PTCL
1
, TOS
1
, COST
1
is provided to CAM array
304
, then each of policy statements
201
-
203
is identified as a match on match lines ML
0
-ML
2
, respectively. Priority encoder
306
outputs address zero on the HPM bus to select route information RI
2
from address zero in memory
308
.
Because priority encoder
306
determines the highest priority matching location based on predetermined logical address assignments, policy statements
201
-
203
are typically preordered or prioritized such that higher priority policy statements are stored in lower logical addresses of CAM array
304
than lower priority policy statements. A policy statement has a higher priority than another policy statement when the route information for the first policy statement is to be selected over the second policy statement even though both policy statements may match the policy search key (e.g., with masking). The prioritizing of the policy statements is typically performed by table management hardware and/or software, which adds overhead to the router. Further, when a policy is changed by adding a new policy statement that has a higher (or equal) priority than at least one of the policy statements already stored in CAM array
304
, the table management hardware and/or software often must reprioritize or reorder all or part of CAM array
304
. This is typically involves loading the CAM array with the new policy statement and reloading the CAM array with all the policy statements of equal or lower priority. This can add significant overhead to the router (e.g., delay and additional hardware and software) to change even just one policy statement in a given policy. If the CAM array is not loaded correctly, either upon initialization or upon change, addition or removal of a policy statement, an incorrect route may be selected from memory
308
.
SUMMARY
A CAM device having a programmable data storage width is disclosed. In one embodiment, the CAM device includes a CAM array arranged in rows of CAM cells, each row including a multiple row segments to store and compare data words that span one or more of the row segments according to a programmed data storage width. A priority index table is coupled to the plurality of rows of CAM cells to store priority numbers that indicate relative priorities of respective data words stored in the CAM array.
In one embodiment, the CAM device also includes write circuitry that includes a coding circuit and a select circuit. The coding circuit is adapted to receive a write data value and to convert the write data value into a coded value. In one embodiment, the coded value is a decoded value and the select circuit is responsive to a control signal to select either the decoded value or the write data value to be stored in the CAM array. In an alternative embodiment, the coded value is an encoded value and the select circuit is responsive

Affiliated with

Also associated with

Rating

Content addressable memory with selectable mask write mode does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content addressable memory with selectable mask write mode, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory with selectable mask write mode will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3364598