Method of performing table lookup operation with table index that exceeds cam key size
In a packet switching device or system, such as a router, switch, combination router/switch, or component thereof, a method of and system for performing a table lookup operation using a lookup table index that exceeds a CAM key size is provided. Multiple CAM accesses are performed, each using a CAM key derived from a subset of lookup table index, resulting in one or more CAM entries. One or more matching table entries are derived from the one or more CAM entries resulting from the multiple CAM accesses.
1. A method of making a classification or forwarding decision for a packet comprising:
performing a first content addressable memory (CAM) access to a first CAM system, the first CAM system comprising a CAM and an associated random access memory (RAM), wherein performing the first CAM access is via a first CAM key derived from a first portion of the packet, resulting in one or more first matching entries, each of the one or more first matching entries including a content portion obtainable from the associated RAM of the first CAM system;
performing a second CAM access to a second CAM system, the second CAM system comprising a CAM and an associated RAM, wherein performing the second CAM access is via a second CAM key derived from a second portion of the packet different than the first portion of the packet, resulting in one or more second matching entries, each of the one or more second matching entries including a content portion obtainable from the associated RAM of the second CAM system; and
determining the classification or forwarding decision for the packet responsive to the content portion of each of the one or more first and second matching entries,
wherein the content portion of each of the one or more first and second matching entries comprises a compressed form of one or more indicators of the one or more classification or forwarding decisions.
2. The method of claim 1 , wherein the predetermined content portion of each of the one or more first and second matching entries comprises a bit map.
3. The method of claim 2 , wherein the determining comprises logically combining the bit maps for each of the one or more first and second matching entries, resulting in a composite bit map from which the classification or forwarding decision for the packet is derived.
4. The method of claim 3 , wherein the determining further comprises applying the composite bit map as an index to a memory holding an array of possible forwarding or classification decisions.
5. The method of claim 4 , wherein the determining further comprises applying a priority resolution scheme to the composite bit map.
6. The method of claim 1 , wherein the one or more indicators of the one or more classification or forwarding decisions include types indicating route, drop, central processing unit (CPU) copy, redirect, learn, egress minor, and ingress minor.
7. The method of claim 1 , wherein the one or more indicators in compressed form represent Access Control List (ACL) types.
8. The method of claim 1 , wherein the determining further comprises decompressing the one or more indicators for each of the one or more first and second matching entries.
9. The method of claim 1 , wherein the first and the second CAM systems are different.
10. The method of claim 1 , wherein the first and the second CAM systems are the same.
11. The method of claim 10 , wherein the first and the second CAM keys are of different types.
12. The method of claim 11 , wherein the first and the second CAM keys are of different types as indicated by a type field included in each.
13. The method of claim 12 , wherein the one or more first matching CAM entries and the one or more second CAM entries are of different types as indicated by a type field in the key portion of each.
14. The method of claim 1 further comprising:
performing one or more additional CAM accesses, to the first, the second, or an additional CAM system, resulting in one or more additional matching CAM entries, each additional matching CAM entry having a content portion retrieved from associated RAM; and
determining the classification or forwarding decision for the packet responsive to the content portion of each of the one or more first, second, and additional matching CAM entries.
15. The method of claim 1 , wherein the first CAM key comprises one or more first packet fields, and the second CAM key comprises one or more second packet fields, each distinct from the one or more first packet fields.
16. The method of claim 1 , wherein the first and the second CAM keys are each smaller than a maximum allowable CAM key size applicable to the first and the second CAM systems.
17. A system for making a classification or forwarding decision for a packet comprising:
a buffer for storing the packet;
a first logic, coupled to the buffer, for deriving a first content addressable memory (CAM) key from a first portion of the packet and a second CAM key from a second portion of the packet different than the first portion of the packet;
a first CAM system, comprising a CAM and an associated random access memory (RAM), for performing a first CAM access via the first CAM key, resulting in one or more first matching entries, each of the one or more first matching entries including a content portion obtainable from the associated RAM of the first CAM system;
a second CAM system, comprising a CAM and an associated RAM, for performing a second CAM access via the second CAM key, resulting in one or more second matching entries, each of the one or more second matching entries including a content portion obtainable from the associated RAM of the second CAM system; and
a second logic, coupled to the first and the second CAM systems, for determining the classification or forwarding decision for the packet responsive to the content portion of each of the one or more first and second matching entries,
wherein the content portion of each of the one or more first and second matching entries comprises a compressed form of one or more indicators of the one or more classification or forwarding decisions.
18. The system of claim 17 , wherein the predetermined content portion of each of the one or more first and second matching entries comprises a bit map.
19. The system of claim 18 , wherein the second logic is operable to logically combine the bit maps for each of the one or more first and second matching entries to form a composite bit map, and derives the classification or forwarding decision for the packet from the bit map.
20. The system of claim 18 , wherein the second logic is operable to apply the composite bit map as an index to a memory holding an array of possible forwarding or classification decisions.
21. The system of claim 20 , wherein the second logic is operable to apply a priority resolution scheme to the composite bit map.
22. The system of claim 17 , wherein the one or more indicators of the one or more classification or forwarding decisions include types indicating route, drop, central processing unit (CPU) copy, redirect, learn, egress minor, and ingress mirror.
23. The system of claim 17 , wherein the one or more indicators in compressed form represent Access Control List (ACL) types.
24. The system of claim 17 , wherein the second logic is operable to decompress the one or more indicators for each of the one or more first and second matching entries.
25. The system of claim 17 , wherein the first and second CAM systems are different.
26. The system of claim 17 , wherein the first and second CAM systems are the same.
27. The system of claim 26 , wherein the first and second CAM keys are of different types.
28. The system of claim 27 , wherein the first and second CAM keys are of different types as indicated by a type field included in each.
29. The system of claim 28 , wherein the one or more first matching CAM entries and the one or more second CAM entries are of different types as indicated by a type field in the key portion of each.
30. The system of claim 28 , further comprising an additional CAM system, having a CAM and an associated RAM, to perform one or more additional CAM accesses resulting in one or more additional matching CAM entries, each of the one or more additional matching CAM entries including a content portion retrieved from the associated RAM,
wherein the second logic is operable to determine the classification or forwarding decision for the packet responsive to the content portion of each of the one or more first, second, and additional matching CAM entries.
31. The system of claim 16 , wherein the first logic is operable to derive the first CAM key from one or more first packet fields, and is operable to derive the second CAM key from one or more second packet fields, each distinct from the one or more first packet fields.
32. The system of claim 16 , wherein the first logic is operable to set the first and second CAM keys to sizes that are each smaller than a maximum allowable CAM key size applicable to the first and second CAM systems.
33. The system of claim 19 , wherein the second logic is operable to logically combine the bit maps via a logical AND operation.