US6633953B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Range content-addressable memory
Assignee: HyWire Ltd
•
Filing: 2001-02-07
•
Granted: 2003-10-14
•
Expires: 2021-02-07
Abstract
Abstract A method and apparatus for storing an associative key data set of associative elements representing a range, and an associated data set of associated elements, such that an associative element is extracted from memory in response to an input key, the range being represented by a lower boundary value and/or an upper boundary value, the method including: a) providing first and second storage areas for storing the respective data sets; b) ordering the associative elements according to priority precedence; c) storage a boundary value of each associative element in the first storage area in a location corresponding to this order, and d) storing each associated data set value in the second storage area in a location corresponding to the location of the associative element associated thereto.
Inventors
- 👤 Moshe Stark
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:22
CPC Classifications
G; G11; G11C; G11C15/00
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
234 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from said memory as valid data if an input key belongs to at least one of the associative elements, said range being represented by at least one of a lower boundary value and an upper boundary value associated with said range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) arranging the associative elements of said associative key data set and their corresponding associated data set in an order determined by a priority precedence; c) assigning a unique index for each associative element, representing an ordered location thereof; d) storing at least one boundary value of each associative element in said first storage area in a location that corresponds to said order, and e) storing each value of said associated data set in a location in said second storage area corresponding to the location of the associative element to which it is associated.
Claim 2
Independent Claim
234 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from said memory as valid data if an input key belongs to at least one of the associative elements, said range being represented by at least one of a lower boundary value and an upper boundary value associated with said range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) arranging the associative elements of said associative key data set and their corresponding associated data set in an order determined by a priority precedence; c) assigning a unique index for each associative element, representing an ordered location thereof; d) storing at least one boundary value of each associative element in said first storage area in a location that corresponds to said order, and e) storing each value of said associated data set in a location in said second storage area corresponding to the location of the associative element to which it is associated.
Claim 3
Dependent Claim
30 words
The method according to claim 1 , wherein each associative element of the associative elements of the key association data set is a ranges of consecutive values having semi-open/semi-closed boundaries.
Claim 4
Dependent Claim
28 words
The method according to claim 2 , wherein said range has a closed boundary as a lower boundary thereof, and an open boundary as an upper boundary thereof.
Claim 5
Dependent Claim
79 words
The method according to claim 3 , wherein values of said lower boundary and said upper boundary of said range are determined by k bits in a binary representation, and any value that is larger than all values contained in said range is represented by said open upper boundary consisting of k consecutive “0” bits, so as to imply an existence of a leftmost n-lost significant (k+1) th bit “1”, said most significant bit being omitted in said representation.
Claim 6
Dependent Claim
28 words
The method according to claim 2 , wherein said range has a closed boundary as an upper boundary thereof, and an open boundary as a lower boundary thereof.
Claim 7
Dependent Claim
19 words
The method according to claim 1 , wherein the ranges that correspond to different associative elements include non-overlapping ranges.
Claim 8
Dependent Claim
21 words
The method according to claim 1 , wherein the range represents a group of consecutive Classless Inter Domain Routing (CIDR) addresses.
Claim 9
Dependent Claim
85 words
The method according to claim 1 , wherein whenever ranges that correspond to different associative elements are overlapping ranges, seeking a match between an input key and a range by performing the following steps: i) arranging said ranges in their priority precedence order; ii) comparing said input key with the values within each range, and obtaining one or more match indications whenever said input key belongs to one or more ranges, and iii) selecting the match indication corresponding to the range having the highest priority.
Claim 10
Dependent Claim
28 words
The method according to claim 1 , further comprising the step of: (f) conducting a key search on the associative key data set, upon receiving the input key.
Claim 11
Dependent Claim
28 words
The method according to claim 9 , further comprising the step of: (g) extracting an associated data value from said associated data set, based on said key search.
Claim 12
Dependent Claim
43 words
The method according to claim 10 , further comprising the step of: (h) if no match between said input key and the associative key data set is found, outputting a no-match signal indicating that said associated data value from step (g) is invalid.
Claim 13
Dependent Claim
43 words
The method according to claim 10 , further comprising the step of: (h) if a match between said input key and the associative key data set is found, outputting a match signal indicating that said associated data value from step (g) is valid.
Claim 14
Dependent Claim
57 words
The method according to claim 9 , further comprising the step of: (g) if a plurality of matches between said input key and matching associative elements within the associative key data set is found, outputting a value of said associated data set corresponding to a matching associative element having a highest priority among said matching associative elements.
Claim 15
Dependent Claim
23 words
The method according to claim 1 , wherein associative elements having a higher priority are placed before associative elements having a lower priority.
Claim 16
Independent Claim
207 words
An apparatus for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to at least one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the apparatus comprising: at least one memory device including: i) a first storage area for storing said associative key data set, and ii) a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; wherein the associative elements of the associative key data set are arranged in an order determined by a priority precedence, and wherein at least one boundary value of each associative element is stored in said first storage area in a location that corresponds to said order, and wherein each value of said associated data set is stored in said corresponding storage location in said second storage area.
Claim 17
Independent Claim
207 words
An apparatus for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to at least one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the apparatus comprising: at least one memory device including: i) a first storage area for storing said associative key data set, and ii) a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; wherein the associative elements of the associative key data set are arranged in an order determined by a priority precedence, and wherein at least one boundary value of each associative element is stored in said first storage area in a location that corresponds to said order, and wherein each value of said associated data set is stored in said corresponding storage location in said second storage area.
Claim 18
Dependent Claim
18 words
The apparatus of claim 15 , wherein each of the associative elements includes a range of consecutive values.
Claim 19
Dependent Claim
20 words
The apparatus of claim 16 , wherein said range of consecutive values has a closed boundary and an open boundary.
Claim 20
Dependent Claim
78 words
The apparatus of claim 17 , wherein values of said lower boundary and said upper boundary of said range are determined by k bits in a binary representation, and any value that is larger than all values contained in said range is represented by said open upper boundary consisting of k consecutive “0” bits, so as to imply an existence of a leftmost most significant (k+1) th bit “1”, said most significant bit being omitted in said representation.
Claim 21
Dependent Claim
35 words
The apparatus of claim 15 , further comprising: circuitry for seeking, upon receiving a particular input key, at least one said associative element having a range of values that may contain said particular input key.
Claim 22
Dependent Claim
31 words
The apparatus of claim 15 , further comprising: circuitry for outputting associated data corresponding to the associative element having the highest priority of all associative elements containing a particular input key.
Claim 23
Dependent Claim
37 words
The apparatus of claim 15 , further comprising: circuitry for outputting a no-match signal indicating that associated data being output is invalid, if a particular input key is outside all ranges of the associative key data set.
Claim 24
Dependent Claim
40 words
The apparatus of claim 15 , further comprising: circuitry for outputting a match signal indicating that associated data being output is valid, if a particular input key is contained in an associative element belonging to the associative key data set.
Claim 25
Dependent Claim
21 words
The method according to claim 15 , wherein the range represents a group of consecutive Classless Inter Domain Routing (CIDR) addresses.
Claim 26
Independent Claim
204 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) arranging at least one boundary value of each associative element in said first storage area in a pre-determined order, such that each successive range is arranged in a monotonic order with respect to a previous range; c) assigning a unique index for each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 27
Independent Claim
204 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) arranging at least one boundary value of each associative element in said first storage area in a pre-determined order, such that each successive range is arranged in a monotonic order with respect to a previous range; c) assigning a unique index for each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 28
Dependent Claim
18 words
The method of claim 24 , wherein each of the associative elements includes a range of consecutive values.
Claim 29
Dependent Claim
20 words
The method of claim 25 , wherein said range of consecutive values has a closed boundary and an open boundary.
Claim 30
Dependent Claim
82 words
The method according to claim 26 , wherein values of said lower boundary and said upper boundary of said range of consecutive values are determined by k bits in a binary representation, and any value that is larger than all values contained in said range is represented by said open upper boundary consisting of k consecutive “0” bits, so as to imply an existence of a leftmost most significant (k+1) th bit “1”, said most significant bit being omitted in said representation.
Claim 31
Dependent Claim
24 words
The method according to claim 26 , wherein said range of consecutive values represents a group of consecutive Classless Inter Domain Routing (CIDR) addresses.
Claim 32
Dependent Claim
27 words
The method according to claim 24 , further comprising the step of: e) determining whether the input key belongs to an associative element of the associative elements.
Claim 33
Dependent Claim
36 words
The method according to claim 24 , further comprising the step of: e) processing the associative elements according to a pre-determined priority criterion, so as to convert the ranges of the associative elements to non-overlapping ranges.
Claim 34
Dependent Claim
55 words
The method according to claim 30 , wherein said processing includes truncating any overlapping portions from those ranges having lower priority, while maintaining with no change, for each set of overlapping portions, a single portion having the highest priority within said set of overlapping portions, so as to obtain an equivalent set of non-overlapping ranges.
Claim 35
Independent Claim
239 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from said memory as valid data if an input key belongs to one of the associative elements, said range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area, wherein each of the associative elements of the associative key data set includes a range of consecutive values; b) representing said range of consecutive values within said first storage area as at least one of a lower boundary value and an upper boundary value associated with the range, wherein at least one value of said values is selected from the group consisting of a closed boundary value and an open boundary value; c) assigning a unique index for each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 36
Independent Claim
239 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from said memory as valid data if an input key belongs to one of the associative elements, said range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area, wherein each of the associative elements of the associative key data set includes a range of consecutive values; b) representing said range of consecutive values within said first storage area as at least one of a lower boundary value and an upper boundary value associated with the range, wherein at least one value of said values is selected from the group consisting of a closed boundary value and an open boundary value; c) assigning a unique index for each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 37
Dependent Claim
36 words
The method according to claim 32 , further comprising the step of: e) processing the associative elements according to a pre-determined priority criterion, so as to convert the ranges of the associative elements to non-overlapping ranges.
Claim 38
Dependent Claim
16 words
The method according to claim 33 , wherein said processing is performed prior to step d).
Claim 39
Dependent Claim
49 words
The method according to claim 32 , further comprising the step of: e) arranging at least one boundary value of each associative element in said first storage area in a pre-determined order, such that each successive range is arranged in a monotonic order with respect to a previous range.
Claim 40
Dependent Claim
24 words
The method according to claim 32 , wherein said range of consecutive values represents a group of consecutive Classless Inter Domain Routing (CIDR) addresses.
Claim 41
Dependent Claim
79 words
The method according to claim 32 , wherein values of said lower boundary and said upper boundary of said range are determined by k bits in a binary representation, and any value that is larger than all values contained in said range is represented by said open upper boundary consisting of k consecutive “0” bits, so as to imply an existence of a leftmost most significant (k+1) th bit “1”, said most significant bit being omitted in said representation.
Claim 42
Independent Claim
216 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) eliminating overlapping of the ranges, according to at least one pre-determined priority criterion, so as to produce a set of non-overlapping ranges; c) storing said set of non-overlapping ranges within said first storage area as said associative key data set of associative elements, said key data set including at least one boundary value of each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 43
Independent Claim
216 words
A method for arranging and storing, in a memory, an associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element represents a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an input key belongs to one of the associative elements, the range being represented by at least one of a lower boundary value and an upper boundary value associated with the range, the method comprising: a) providing at least one memory device including a first storage area for storing said associative key data set and a second storage area for storing said associated data set, such that for each storage location in said first storage area there is a corresponding storage location in said second storage area; b) eliminating overlapping of the ranges, according to at least one pre-determined priority criterion, so as to produce a set of non-overlapping ranges; c) storing said set of non-overlapping ranges within said first storage area as said associative key data set of associative elements, said key data set including at least one boundary value of each associative element, and d) storing each value of said associated data set in said corresponding storage location in said second storage area.
Claim 44
Dependent Claim
16 words
The method according to claim 38 , wherein said processing is performed prior to step d).
Claim 45
Dependent Claim
49 words
The method according to claim 38 , further comprising the step of: e) arranging at least one boundary value of each associative element in said first storage area in a pre-determined order, such that each successive range is arranged in a monotonic order with respect to a previous range.
Claim 46
Dependent Claim
24 words
The method according to claim 38 , wherein the range of consecutive values represents a group of consecutive Classless Inter Domain Routing (CIDR) addresses.
Claim 47
Dependent Claim
79 words
The method according to claim 38 , wherein values of the lower boundary and the upper boundary of the range are determined by k bits in a binary representation, and any value that is larger than all values contained in the range is represented by the open upper boundary consisting of k consecutive “0” bits, so as to imply an existence of a leftmost most significant (k+1) th bit “1”, said most significant bit being omitted in said representation.
References Cited (Backward Citations)
US5920886A
Cited
US6237061B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-10-13 | 2007-04-14 | 2007-10-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-10-13 | 2011-04-14 | 2011-10-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-10-13 | 2015-04-14 | 2015-10-14 | $7700.00 | Window Closed / Lapsed |