High speed routing using compressed tree process

• US 6,067,574 A
• Filed: 05/18/1998
• Issued: 05/23/2000
• Est. Priority Date: 05/18/1998
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Tzeng, Hong-Yi
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): EDELMAN, BRADLEY E
• Application Number:
  US09/080,557
• Time in Patent Office: 736 Days
• Field of Search: 707/101, 707/3, 709/238, 709/230, 709/247
• US Class Current: 709/247
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. 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.

2. 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.

3. A method according to claim 2 wherein said pages are equal size pages.

4. 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.

5. 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.

7. 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.

8. A method according to claim 4 wherein said interface information is stored in an array.

6. 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.

9. 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.

10. 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.