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

• US 20050010612A1
• Filed: 07/09/2003
• Published: 01/13/2005
• 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 6,988,106 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 items are disclosed which may be particularly useful for implementing security policies and security associations, such as, but not limited to Internet Protocol security (IPsec). A hierarchy of items is stored in a search priority order. Multiple element definitions and groups of elements are identified. Representations of the element definitions and elements are stored in a prioritized searchable data structure in decreasing search priority such that representations of each particular element definition is stored after representations of a set of particular elements associated with the particular element definition and before representations of lower priority element definitions and their associated elements. The element definitions may include Internet Protocol security policies and the elements may include Internet Protocol security associations. The searchable data structure may include an associative memory or a plurality of associative memory entries.

Claims

1. A method for storing a hierarchy of items in a search priority order, the method comprising:

identifying a plurality of element definitions and a plurality of groups of elements; and

storing representations of the plurality of element definitions and elements of the plurality of groups of elements in a prioritized searchable data structure in decreasing search priority such that representations of each particular element definition of the plurality of element definitions is stored after representations of a set of particular elements of the plurality of groups of elements associated with said particular element definition and before representations of lower priority element definitions of the plurality of element definitions and their associated elements in the plurality of groups of elements.

2. The method of claim 1, wherein the plurality of element definitions includes Internet Protocol security policies and the plurality of groups of elements includes Internet Protocol security associations.

3. The method of claim 2, wherein the searchable data structure includes an associative memory or a plurality of associative memory entries.

4. The method of claim 1, wherein the searchable data structure includes an associative memory or a plurality of associative memory entries.

5. A method for maintaining a data structure, the method comprising:

identifying an ordered list of Internet Protocol security policies;

programming ordered associative memory entries associated with the ordered list of Internet Protocol security policies;

programming corresponding context memory entries associated with the ordered list of Internet Protocol security policies;

performing an associative memory lookup operation on said ordered associative memory entries based on a received packet to identify a particular associative memory entry location;

performing a lookup operation on the context memory based on the particular associative memory entry location to identify a particular Internet Protocol security policy, of the ordered list of Internet Protocol security policies; and

adding a particular security association entry based on the received packet to said ordered associative memory entries, the particular security association entry corresponding to the particular Internet Protocol security policy, and the particular security association entry being added to said ordered associative memory entries prior to the particular associative memory entry location and after other security policy entries of said ordered list of Internet Protocol security policies located prior to the particular associative memory entry location.

6. The method of claim 5, wherein said adding the particular security association entry includes expanding a partition allocated for entries in an associative memory corresponding to the particular Internet Protocol security policy and its associated security association entries

7. The method of claim 6, wherein said expanding a partition includes redistributing free space to multiple partitions in the associative memory.

8. An apparatus for searching entries of an associative memory, the apparatus comprising:

the associative memory;

a programming mechanism coupled to the associative memory; and

a mechanism for generating lookup words to the associative memory based on which the associative memory performs a lookup operation;

wherein the programming mechanism is configured to store representations of a plurality of element definitions and elements of a plurality of groups of elements in the associative memory in decreasing search priority such that representations of each particular element definition of the plurality of element definitions is stored after representations of a set of particular elements of the plurality of groups of elements associated with said particular element definition and before representations of lower priority element definitions of the plurality of element definitions and their associated elements in the plurality of groups of elements.

9. The apparatus of claim 8, wherein the plurality of element definitions includes Internet Protocol security policies and the plurality of groups of elements includes Internet Protocol security associations.

10. The apparatus of claim 9, wherein the programming mechanism includes means for updating the associative memory with new security associations associated with the plurality of security policies.

11. The apparatus of claim 9, wherein the programming mechanism includes an update mechanism for updating the associative memory with new security associations associated with the plurality of security policies.

12. An apparatus for storing a hierarchy of items in a search priority order, the apparatus comprising:

means for identifying a plurality of element definitions and a plurality of groups of elements, and

means for storing representations of the plurality of element definitions and elements of the plurality of groups of elements in a prioritized searchable data structure in decreasing search priority such that representations of each particular element definition of the plurality of element definitions is stored after representations of a set of particular elements of the plurality of groups of elements associated with said particular element definition and before representations of lower priority element definitions of the plurality of element definitions and their associated elements in the plurality of groups of elements.

13. The apparatus of claim 12, wherein the plurality of element definitions includes Internet Protocol security policies and the plurality of groups of elements includes Internet Protocol security associations.

14. The apparatus of claim 13, wherein the searchable data structure includes an associative memory or a plurality of associative memory entries.

15. The apparatus of claim 12, wherein the searchable data structure includes an associative memory or a plurality of associative memory entries.

16. The apparatus of claim 15, wherein said means for storing includes means for splitting a range into a plurality of entries.

17. An apparatus for maintaining a data structure based an ordered list of Internet Protocol security policies, the apparatus comprising:

means for programming ordered associative memory entries associated with the ordered list of Internet Protocol security policies;

means for programming corresponding context memory entries associated with the ordered list of Internet Protocol security policies;

means for performing an associative memory lookup operation on said ordered associative memory entries based on a received packet to identify a particular associative memory entry location;

means for performing a lookup operation on the context memory based on the particular associative memory entry location to identify a particular Internet Protocol security policy of the ordered list of Internet Protocol security policies; and

means for adding a particular security association entry based on the received packet to said ordered associative memory entries, the particular security association entry corresponding to the particular Internet Protocol security policy, and the particular security association entry being added to said ordered associative memory entries prior to the particular associative memory entry location and after other security policy entries of said ordered list of Internet Protocol security policies located prior to the particular associative memory entry location.

18. The apparatus of claim 17, wherein said means for adding the particular security association entry includes means for expanding a partition allocated for entries in an associative memory corresponding to the particular Internet Protocol security policy and its associated security association entries

19. The apparatus of claim 18, wherein said means for expanding a partition includes redistributing free space to multiple partitions in the associative memory.

20. The apparatus of claim 17, wherein said means for expanding the partition includes means for getting space from neighboring partitions.

21. The apparatus of claim 17, wherein said means for expanding the partition includes means for feeing another starving partition.

22. The apparatus of claim 17, wherein said means for adding the particular security association entry includes means for splitting the security association entry into a plurality of associative memory entries of said ordered associative memory entries.

23. A computer-readable medium containing computer-executable instructions for performing steps for maintaining a data structure based an ordered list of Internet Protocol security policies, said steps comprising:

programming ordered associative memory entries associated with the ordered list of Internet Protocol security policies;

programming corresponding context memory entries associated with the ordered list of Internet Protocol security policies;

performing an associative memory lookup operation on said ordered associative memory entries based on a received packet to identify a particular associative memory entry location;

performing a lookup operation on the context memory based on the particular associative memory entry location to identify a particular Internet Protocol security policy of the ordered list of Internet Protocol security policies; and

adding a particular security association entry based on the received packet to said ordered associative memory entries, the particular security association entry corresponding to the particular Internet Protocol security policy, and the particular security association entry being added to said ordered associative memory entries prior to the particular associative memory entry location and after other security policy entries of said ordered list of Internet Protocol security policies located prior to the particular associative memory entry location.

24. The computer-readable medium of claim 23, wherein said adding the particular security association entry includes expanding a partition allocated for entries in an associative memory corresponding to the particular Internet Protocol security policy and its associated security association entries

25. The computer-readable medium of claim 24, wherein said expanding a partition includes redistributing free space to multiple partitions in the associative memory.

26. An apparatus for maintaining entries of an associative memory based an ordered list of Internet Protocol security policies, the apparatus comprising:

the associative memory including ordered associative memory entries associated with the ordered list of Internet Protocol security policies;

a programming mechanism coupled to the associative memory;

a mechanism for generating lookup words to the associative memory based on which the associative memory performs a lookup operation to identify a particular associative memory entry location;

a context memory for performing lookup operations based on the particular associative memory entry location to identify a particular Internet Protocol security policy of the ordered list of Internet Protocol security policies;

wherein the programming mechanism is configured to add a particular security association entry based on the received packet to said ordered associative memory entries, the particular security association entry corresponding to the particular Internet Protocol security policy, and the particular security association entry being added to said ordered associative memory entries prior to the particular associative memory entry location and after other security policy entries of said ordered list of Internet Protocol security policies located prior to the particular associative memory entry location.

27. The apparatus of claim 26, wherein the programming mechanism expands a partition allocated for entries in an associative memory corresponding to the particular Internet Protocol security policy and its associated security association entries

28. The apparatus of claim 26, wherein the programming mechanism redistributes free space to multiple partitions in the associative memory.

29. The apparatus of claim 26, wherein the programming mechanism is further configured to split a range corresponding to the particular security association entry into a plurality of associative memory entries.