Storing and searching a hierarchy of policies and associations thereof of particular use with IP security policies and security associations

• US 20060074899A1
• Filed: 11/13/2005
• Published: 04/06/2006
• Est. Priority Date: 07/09/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nagaraj, Ashwath, Kwok, Henry Kin-Chuen, Enderwick, Thomas Jeffrey
• Granted Patent: US 7,493,328 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 63/164 at the network layer
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

Mechanisms for storing and searching a hierarchy of policies and associations thereof are disclosed which may be particularly useful for implementing security protocols, such as, but not limited to Internet Protocol security (IPsec). For example, a hierarchy of policies is stored in a search priority order in an associative memory, with each association of a particular policy stored higher in the search priority than its associated policy and after any other policy. Therefore, a lookup operation on the associative memory will identify a matching association, if one, else its matching policy. A match of a policy instead of an association may result in a corresponding association being added in the appropriate location. For IPsec implementations, the lookup word is typically derived from the packet, with this packet being typically processed based on the identified policy or association.

Claims

1. A method for processing packets based on a hierarchy of policies, the method comprising:

performing a lookup operation on a plurality of associative memory entries of an associative memory based on a lookup word derived from a packet in order to identify a lookup result, the associative memory entries corresponding to a plurality of policies of the hierarchy of policies and a plurality of associations corresponding to said policies, wherein the associative memory is configured to identify the highest-priority, in a predetermined priority ordering, associative memory entry of the associative memory entries matching the lookup word, with said policies programmed into said associative memory entries such that said hierarchy of the policies matches said predetermined priority ordering of the associative memory entries, with each associative memory entry corresponding to a particular association of the plurality of associations being programmed into said associative memory entries prior to, in said predetermined priority ordering, the associative memory entry corresponding to the particular association'"'"'s policy of said policies and after any associative memory entry corresponding to another of said policies higher in said hierarchy of policies; and

processing the packet based on the lookup result.

2. The method of claim 1, comprising in response to identifying that said highest-priority matching entry corresponds to a particular policy of said policies and not to one of said associations, adding an associative memory entry corresponding to the particular policy to said associative memory entries;

wherein said added associative memory entry is programmed into said associative memory entries prior to, in said predetermined priority ordering, the associative memory entry corresponding to the particular policy and after any associative memory entry corresponding to another of said policies higher in said hierarchy of policies.

3. The method of claim 2, wherein each of the associative memory entries is a ternary content-addressable memory entry.

4. The method of claim 2, wherein all of said associative memory entries are searched in parallel based on the lookup word.

5. The method of claim 2, wherein each of said policies corresponds to an Internet Protocol security policy, and each of said associations corresponds to an Internet Protocol security association.

6. The method of claim 1, wherein each of the associative memory entries is a ternary content-addressable memory entry.

7. The method of claim 1, wherein all of said associative memory entries are searched in parallel based on the lookup word.

8. The method of claim 1, wherein each of said policies corresponds to an Internet Protocol security policy, and each of said associations corresponds to an Internet Protocol security association.

9. An apparatus for processing packets based on a hierarchy of policies, the apparatus comprising:

a plurality of associative memory entries of an associative memory, the associative memory entries being programmed to correspond to a plurality of policies of the hierarchy of policies and a plurality of associations corresponding to said policies, wherein the associative memory is configured to identify the highest-priority, in a predetermined priority ordering, associative memory entry of the associative memory entries matching a lookup word, with said policies programmed into said associative memory entries such that said hierarchy of the policies matches said predetermined priority ordering of the associative memory entries, with each associative memory entry corresponding to a particular association of the plurality of associations being programmed into said associative memory entries prior to, in said predetermined priority ordering, the associative memory entry corresponding to the particular association'"'"'s policy of said policies and after any associative memory entry corresponding to another of said policies higher in said hierarchy of policies; and

a packet processing mechanism for initiating a lookup operation on the plurality of associative memory entries based on the lookup word derived from a packet in order to identify a lookup result, and to process the packet based on the lookup result.

10. The apparatus of claim 9, wherein the packet processing mechanism is configured to, in response to identifying that said highest-priority matching entry corresponds to a particular policy of said policies and not to one of said associations, cause an associative memory entry corresponding to the particular policy to be added to said associative memory entries;

wherein said added associative memory entry is programmed into said associative memory entries prior to, in said predetermined priority ordering, the associative memory entry corresponding to the particular policy and after any associative memory entry corresponding to another of said policies higher in said hierarchy of policies.

11. The apparatus of claim 10, wherein each of said policies corresponds to an Internet Protocol security policy, and each of said associations corresponds to an Internet Protocol security association.

12. The apparatus of claim 9, wherein each of the associative memory entries is a ternary content-addressable memory entry.

13. The apparatus of claim 9, wherein all of said associative memory entries are searched in parallel based on the lookup word.

14. The apparatus of claim 9, wherein each of said policies corresponds to an Internet Protocol security policy, and each of said associations corresponds to an Internet Protocol security association.

15. The apparatus of claim 9, comprising means for adding, in response to identifying that said highest-priority matching entry corresponds to a particular policy of said policies and not to one of said associations, an associative memory entry corresponding to the particular policy to said associative memory entries;

wherein said added associative memory entry is programmed into said associative memory entries prior to, in said predetermined priority ordering, the associative memory entry corresponding to the particular policy and after any associative memory entry corresponding to another of said policies higher in said hierarchy of policies.

16. The apparatus of claim 15, wherein each of said policies corresponds to an Internet Protocol security policy, and each of said associations corresponds to an Internet Protocol security association.

17. The apparatus of claim 15, wherein each of the associative memory entries is a ternary content-addressable memory entry.