Content addressable memory with automated learning
View Patent ↗A Content Addressable Memory (CAM) architecture is disclosed wherein at least part of an access key is unconditionally written to a CAM memory location. This unconditional writing is performed while accessing a set of CAM memory locations for the purposes of matching the access key. This writing is performed regardless of whether a match to the access key is found.
1. A content addressable memory (CAM) comprising:
a first plurality of storage locations to store a plurality of rules;
a second plurality of storage locations associated with and coupled to said first plurality of storage locations to store either a plurality of contexts correspondingly associated with the rules or a plurality of pointers correspondingly pointing to the corresponding contexts stored outside the CAM, wherein whether the second plurality of storage locations to store the plurality of contexts or the plurality of pointers is determined according to a quantity of context information to be stored;
first write logic coupled to said first plurality of storage locations to unconditionally write a new rule to a selected one of said first plurality of storage locations while accessing said first plurality of storage locations for one or more full or partial match of an access key, the access key being a subset of a datagram; and
second write logic to write either a new context associated with the new rule, or a pointer to a new context associated with the new rule, into a selected one of the second plurality of storage locations, the new context being created in response to a partial match of the access key against one of said first plurality of storage locations.
2. The CAM of claim 1 wherein said selected one of said first plurality of storage locations is determined from a next available storage indicator.
3. The CAM of claim 1 wherein said first write logic further comprises a valid bit.
4. The CAM of claim 1 wherein said second write logic further comprises a valid bit.
5. The CAM of claim 4 wherein said valid bit is set upon said writing of said pointer to an execution context.
6. The CAM of claim 5 wherein said execution context contains information on one or more of a flow information and a processor assignment.
7. A Network Integrated Circuit comprising:
a content addressable memory (CAM) structure including a first plurality of storage locations to store a plurality of rules and a second plurality of storage locations associated with said first plurality of storage locations to store either a plurality of contexts correspondingly associated with the rules or a plurality of pointers correspondingly pointing to the corresponding contexts stored outside the CAM, wherein whether the second plurality of storage locations to store the plurality of contexts or to store the plurality of pointers is determined according to a quantity of context information to be stored;
a network processor coupled to the CAM structure; and first write logic coupled to said first plurality of storage locations to unconditionally write a new rule to a selected one of said first plurality of storage locations while accessing said first plurality of storage locations for one or more full or partial match using an access key that is a subset of a datagram;
wherein said network processor is configured to create and store a new context associated with the new rule in the CAM structure or a pointer to a new context associated with the new rule if the new context is created outside of the CAM, in response to a partial match of the access key against one of said first plurality of storage locations.
8. The Network Integrated Circuit of claim 7 wherein the CAM structure supports multiple protocols.
9. The Network Integrated Circuit of claim 7 where the network processor includes second write logic coupled to said second plurality of storage locations to write a pointer to an execution context to an associated one of said second plurality of storage locations at a subsequent point in time to said access.
10. The Network Integrated Circuit of claim 7 wherein said selected one of said first plurality of storage locations is determined from a next available storage indicator.
11. The Network Integrated Circuit of claim 7 wherein said first write logic further comprises a valid bit.
12. The Network Integrated Circuit of claim 9 wherein said second write logic further comprises a valid bit.
13. The Network Integrated Circuit of claim 12 wherein said valid bit is set upon said writing of said pointer to said execution context.
14. The Network Integrated Circuit of claim 9 wherein said execution context includes information selected from one or more of a flow information and a processor assignment.
15. An apparatus comprising:
a switching fabric including a plurality of ingress/egress points to switch datagrams received through mediums coupled to the ingress/egress points; and
a network integrated circuit including:
a content addressable memory (CAM) structure including a first plurality of storage locations to store a plurality of rules and a second plurality of storage locations associated with said first plurality of storage locations to store either a plurality of contexts correspondingly associated with the rules or a plurality of pointers correspondingly pointing to a plurality of corresponding contexts stored outside the CAM, wherein whether the second plurality of storage locations to store the plurality of contexts or a plurality of pointers correspondingly pointing to the corresponding contexts stored outside the CAM is determined according to a quantity of context information to be stored;
a memory to store context information; and
first write logic coupled to said first plurality of storage locations to unconditionally write a new rule to a selected one of said first plurality of storage locations while accessing said first plurality of storage locations for one or more full or partial match using an access key that is a subset of a datagram; and
a network processor coupled to the CAM structure and the memory configured to create and store a new context associated with the new rule in the memory, or a pointer to a new context if the new context is created outside of the CAM, in response to a partial match of the access key against one of said first plurality of storage locations.
16. The networking apparatus of claim 15 wherein the CAM structure further includes second write logic coupled to said second plurality of storage locations to write a pointer to an execution context to a corresponding one of said second plurality of storage locations at a subsequent point in time to said access.
17. The networking apparatus of claim 15 wherein said selected one of said first plurality of storage locations is determined from a next available storage indicator.
18. The networking apparatus of claim 15 wherein said first write logic further comprises a valid bit.
19. The networking apparatus of claim 16 wherein said second write logic further comprises a valid bit.
20. The networking apparatus of claim 19 wherein said valid bit is set upon said writing of said pointer to said execution context.
21. The networking apparatus of claim 16 wherein said execution context includes information selected from one or more of a flow information and a processor assignment.
22. The networking apparatus of claim 15 wherein associated indices of said second plurality of storage location operate as context pointers.
23. A method comprising:
responsive to receipt of an access key that is a subset of a datagram, writing unconditionally at least a portion of a rule to a selected one of a first plurality of storage locations in a content addressable memory (CAM) structure;
accessing, while said writing unconditionally, the first plurality of storage locations for a full or a partial match using the access key; and
creating and storing a new context or a pointer to a new context into a selected one of a second plurality of locations associated with and coupled to said first plurality of storage locations to point to the new context if the new context is created outside of the CAM in response to a partial match against one of said first plurality of storage locations, wherein whether the new context or a pointer to the new context is to be stored in the selected one of the second plurality of locations is determined according to a quantity of the new context.
24. The method as defined in claim 23 further comprising:
determining said selected one of the first plurality of storage locations from a next available storage indicator.
25. The method as defined in claim 24 further comprising:
adjusting said next available storage indicator to point to a free storage location in the first plurality of storage locations.