US6988106B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Strong and searching a hierarchy of items of particular use with IP security policies and security associations
Assignee: Cisco Technology Inc
•
Filing: 2003-07-09
•
Granted: 2006-01-17
•
Expires: 2023-07-09
Abstract
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.
Inventors
- 👤 Thomas Jeffrey Enderwick
- 👤 Henry Kin-Chuen Kwok
- 👤 Ashwath Nagaraj
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:16
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/16; H04L63/164; H04L45/00; H04L45/74; H04L45/745; H04L45/7453; H04L63/20
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
184 words
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.
Claim 2
Independent Claim
184 words
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.
Claim 3
Dependent Claim
39 words
The method of claim 1 , 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.
Claim 4
Dependent Claim
22 words
The method of claim 2 , wherein said expanding a partition includes redistributing free space to multiple partitions in the associative memory.
Claim 5
Independent Claim
194 words
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.
Claim 6
Independent Claim
194 words
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.
Claim 7
Dependent Claim
43 words
The apparatus of claim 4 , 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.
Claim 8
Dependent Claim
24 words
The apparatus of claim 5 , wherein said means for expanding a partition includes redistributing free space to multiple partitions in the associative memory.
Claim 9
Dependent Claim
21 words
The apparatus of claim 4 , wherein said means for expanding the partition includes means for getting space from neighboring partitions.
Claim 10
Dependent Claim
20 words
The apparatus of claim 4 , wherein said means for expanding the partition includes means for feeing another starving partition.
Claim 11
Dependent Claim
37 words
The apparatus of claim 4 , 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.
Claim 12
Dependent Claim
191 words
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.
Claim 13
Dependent Claim
191 words
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.
Claim 14
Dependent Claim
40 words
The computer-readable medium of claim 10 , 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.
Claim 15
Dependent Claim
23 words
The computer-readable medium of claim 11 , wherein said expanding a partition includes redistributing free space to multiple partitions in the associative memory.
Claim 16
Independent Claim
190 words
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.
Claim 17
Independent Claim
190 words
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.
Claim 18
Dependent Claim
34 words
The apparatus of claim 13 , 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.
Claim 19
Dependent Claim
20 words
The apparatus of claim 13 , wherein the programming mechanism redistributes free space to multiple partitions in the associative memory.
Claim 20
Dependent Claim
31 words
The apparatus of claim 13 , 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.
References Cited (Backward Citations)
US3648254A
Cited
US4296475A
Cited
US4791606A
Cited
US4996666A
Cited
US5440715A
Cited
US5404482A
Cited
US5339076A
Cited
US5383146A
Cited
US5684954A
Cited
US5450351A
Cited
US6047369A
Cited
US5428565A
Cited
US6041389A
Cited
US5978885A
Cited
US6069573A
Cited
US5841874A
Cited
US5956336A
Cited
US5802567A
Cited
US5852569A
Cited
US6038560A
Cited
US6307855B1
Cited
US6181698B1
Cited
US6199140B1
Cited
US6658002B1
Cited
US6389506B1
Cited
US6738862B1
Cited
US6081440A
Cited
US6137707A
Cited
US6651096B1
Cited
US6470332B1
Cited
US6175513B1
Cited
US6374326B1
Cited
US6526474B1
Cited
US6154384A
Cited
US6134135A
Cited
US6535951B1
Cited
US6240003B1
Cited
US6246601B1
Cited
US6658458B1
Cited
US6725326B1
Cited
US6567812B1
Cited
US6606681B1
Cited
US6862281B1
Cited
US6775737B1
Cited
US6715029B1
Cited
US6687144B2
Cited
US6871262B1
Cited
US6871265B1
Cited
US20030231631A1
Cited
US20040030803A1
Cited
US20040030802A1
Cited
US6717946B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-01-16 | 2009-07-18 | 2010-01-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-01-16 | 2013-07-18 | 2014-01-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-01-16 | 2017-07-18 | 2018-01-17 | $7700.00 | Window Closed / Lapsed |