Patent US6067574A successfully refreshed from Google Patents.
US6067574A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High speed routing using compressed tree process
Assignee: Nokia of America Corp
•
Filing: 1998-05-18
•
Granted: 2000-05-23
•
Expires: 2018-05-18
Abstract
Abstract A router uses the destination address of its incoming packets to decide the proper outgoing interfaces by searching among all of the stored prefixes for the prefix which has the longest match when compared to the destination address in the packet. Prefix trees are employed to represent the set of prefixes to be searched and high-speed, longest prefix matches are performed. An efficient data structure compresses any prefix tree structure so that the number of memory accesses needed to find the longest prefix for any address depends only on the length of the prefix rather than on the number of stored prefixes. Illustratively, only four, 64-bit memory accesses are required to find the longest prefix match for each IPv4 address in the worst case, while only 3 Mbytes are required to store a 128K-entry routing table.
Inventors
- 👤 Hong-Yi Tzeng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 13:05
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06T; G06T9/00; G06T9/40; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
101 words
A method for searching a routing table for routes corresponding to an input string derived from an internet protocol prefix, comprising: a) fetching a compressed tree of pages in memory corresponding to internet protocol address prefixes according to a code which identifies whether a node (i) represents a valid prefix; (ii) has descendent nodes; and (iii) is a descendent node corresponding to a 1 or to a zero in a predetermined bit position of the prefix; b) decompressing the fetched page to construct the original prefix tree; and c) searching the decompressed tree to identify the longest prefix matching said string.
Claim 2
Independent Claim
101 words
A method for searching a routing table for routes corresponding to an input string derived from an internet protocol prefix, comprising: a) fetching a compressed tree of pages in memory corresponding to internet protocol address prefixes according to a code which identifies whether a node (i) represents a valid prefix; (ii) has descendent nodes; and (iii) is a descendent node corresponding to a 1 or to a zero in a predetermined bit position of the prefix; b) decompressing the fetched page to construct the original prefix tree; and c) searching the decompressed tree to identify the longest prefix matching said string.
Claim 3
Independent Claim
174 words
A method of compressing a prefix tree to reduce the number of memory accesses required to look up the interface corresponding to a prefix of an Internet Protocol address, comprising: a) assigning to an array of pages in memory a string of codes to identify an ordered selection of prefix tree nodes; said selection comprising a subtree beginning at the root node of the prefix tree and including nodes having a predetermined order of descent from said root until all nodes rooted at said root node have been included; b) associating with a first page of said array a pointer to a subsequent page containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; c) associating with said first page of said array a pointer to the interface information corresponding to the first valid prefix stored in said first page; and d) repeating steps (b) and (c) for each remaining page of said array.
Claim 4
Independent Claim
174 words
A method of compressing a prefix tree to reduce the number of memory accesses required to look up the interface corresponding to a prefix of an Internet Protocol address, comprising: a) assigning to an array of pages in memory a string of codes to identify an ordered selection of prefix tree nodes; said selection comprising a subtree beginning at the root node of the prefix tree and including nodes having a predetermined order of descent from said root until all nodes rooted at said root node have been included; b) associating with a first page of said array a pointer to a subsequent page containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; c) associating with said first page of said array a pointer to the interface information corresponding to the first valid prefix stored in said first page; and d) repeating steps (b) and (c) for each remaining page of said array.
Claim 5
Dependent Claim
13 words
A method according to claim 2 wherein said pages are equal size pages.
Claim 6
Dependent Claim
33 words
A method according to claim 3 wherein said ordered selection selects the nodes having an equal degree of descent ("In-Order, Breadth-First") from said root node before selecting any node of more remote degree.
Claim 7
Dependent Claim
42 words
A method according to claim 3 wherein said ordered selection selects the nodes identified by a particular bit value and having successively increasing degree of remoteness ("In-Order, Depth-First") from said root node before selecting any node identified by a different bit value.
Claim 8
Independent Claim
235 words
A method of compressing a prefix tree to reduce the number of memory accesses required to look up the interface corresponding to a prefix of an Internet Protocol address, comprising: a) assigning to an array of pages in memory a string of codes to identify an ordered selection of prefix tree nodes; said selection comprising a subtree beginning at the root node of the prefix tree and including nodes having a predetermined order of descent from said root node until said page is filled or until all nodes rooted at said root node have been included; wherein each of said nodes in said selection has no more than two descendents and wherein each such code identifies whether a node (i) represents a valid prefix; (ii) has descendent nodes; and (iii) is a descendent node corresponding to a 1 or to a zero in a predetermined bit position of the prefix; b) associating with a first page of said array a pointer to a subsequent page containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; c) associating with said first page of said array a pointer to the interface information corresponding to the first valid prefix stored in said first page; and d) repeating steps (b) and (c) for each remaining page of said array.
Claim 9
Independent Claim
235 words
A method of compressing a prefix tree to reduce the number of memory accesses required to look up the interface corresponding to a prefix of an Internet Protocol address, comprising: a) assigning to an array of pages in memory a string of codes to identify an ordered selection of prefix tree nodes; said selection comprising a subtree beginning at the root node of the prefix tree and including nodes having a predetermined order of descent from said root node until said page is filled or until all nodes rooted at said root node have been included; wherein each of said nodes in said selection has no more than two descendents and wherein each such code identifies whether a node (i) represents a valid prefix; (ii) has descendent nodes; and (iii) is a descendent node corresponding to a 1 or to a zero in a predetermined bit position of the prefix; b) associating with a first page of said array a pointer to a subsequent page containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; c) associating with said first page of said array a pointer to the interface information corresponding to the first valid prefix stored in said first page; and d) repeating steps (b) and (c) for each remaining page of said array.
Claim 10
Dependent Claim
43 words
A method according to claim 3 wherein said pointer to the next page is incremented according to the number of the subtree's immediate external descendents and wherein said pointer to said interface information is incremented by the number of the subtree's valid prefixes.
Claim 11
Dependent Claim
15 words
A method according to claim 4 wherein said interface information is stored in an array.
Claim 12
Dependent Claim
149 words
A prefix tree rapidly searchable for interface information corresponding to a prefix of an Internet Protocol address, comprising: a) a memory having an array of pages each comprising a subtree beginning at a root node; said subtree including a bit string identifying whether each node thereof (i) represents a valid prefix; (ii) has descendent nodes; and (iii) which descendent node, if present, corresponds to a 1 or to a zero in a predetermined bit position of the prefix; b) a first pointer associated with each such page pointing to a subsequent page of said array containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; and c) a second pointer associated with said page pointing to interface information corresponding to the first valid prefix stored in said first page.
Claim 13
Dependent Claim
149 words
A prefix tree rapidly searchable for interface information corresponding to a prefix of an Internet Protocol address, comprising: a) a memory having an array of pages each comprising a subtree beginning at a root node; said subtree including a bit string identifying whether each node thereof (i) represents a valid prefix; (ii) has descendent nodes; and (iii) which descendent node, if present, corresponds to a 1 or to a zero in a predetermined bit position of the prefix; b) a first pointer associated with each such page pointing to a subsequent page of said array containing a string of codes to identify a similarly ordered selection of the remaining nodes of said prefix tree beginning at a descendent of an egress node of said subtree; and c) a second pointer associated with said page pointing to interface information corresponding to the first valid prefix stored in said first page.
Claim 14
Independent Claim
96 words
A method for searching a routing table for routes corresponding to an input string derived from an internet protocol prefix, comprising: a) decompressing a compressed tree page containing an ordered selection of prefix tree nodes corresponding to internet protocol address prefixes pursuant to a code which identifies whether each of said nodes (i) represents a valid prefix, (ii) has descendant nodes and is a descendent node corresponding to a "1" or to a "0" in a predetermined bit position of the prefix; and b) searching the decompressed tree to identify the longest prefix matching said string.
Claim 15
Independent Claim
96 words
A method for searching a routing table for routes corresponding to an input string derived from an internet protocol prefix, comprising: a) decompressing a compressed tree page containing an ordered selection of prefix tree nodes corresponding to internet protocol address prefixes pursuant to a code which identifies whether each of said nodes (i) represents a valid prefix, (ii) has descendant nodes and is a descendent node corresponding to a "1" or to a "0" in a predetermined bit position of the prefix; and b) searching the decompressed tree to identify the longest prefix matching said string.
References Cited (Backward Citations)
US5781772A
Cited
US5268686A
Cited
US5737732A
Cited
US5592666A
Cited
US5864859A
Cited
US5946679A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-23 | 2003-11-22 | 2004-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-23 | 2007-11-22 | 2008-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-23 | 2011-11-22 | 2012-05-23 | $7700.00 | Window Closed / Lapsed |