Apparatus and method for routing data packets through a communications network

• US 6,553,002 B1
• Filed: 08/29/1997
• Issued: 04/22/2003
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: Severns, Christine E., Gunderson, Marlon, Bremer, Clark
• Primary Examiner(s): Martin-Wallace, Valencia
• Assistant Examiner(s): Nguyen, Kim T.
• Application Number:
  US08/921,189
• Time in Patent Office: 2,062 Days
• Field of Search: 370/400, 370/392, 370/408, 370/351, 370/254, 370/255, 370/256, 370/389, 370/401, 370/404
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A method and apparatus for determining the next router that a data packet is transmitted to on its way to a destination host by traversing a routing table using a hardware search engine and a unique search tree. The step of traversing each node in the search tree takes only one memory cycle, decreasing in half the time it takes to search a routing table and thus forward data packets on a system of computer networks. This is accomplished by storing the decision bit for each node in its parent node rather than in the node itself The apparatus may use a hardware search engine to search the routing table.

Claims

1. An apparatus for determining a path through a network between a source location and a destination location, the path having a plurality of intermediate locations between the source location and the destination location, the source location and each intermediate location having an address and having a memory for storing a routing table used to determine the address of a next location in a dynamically varying path between the source location and the destination location, the routing table being stored as a search tree having parent nodes and child nodes, the search tree terminating in a plurality of leaf nodes, the parent node and child node providing information relating to the address of a leaf node which stores information relating to the address of a next location in the predetermined path, the apparatus comprising:

a memory for storing routing table, each node of the search tree corresponding to a portion of the address of the destination location, such that a sequence of nodes traversed in traveling from a parent node to a child node relates to corresponding sequence of bits in the destination address;

means for processing, in one memory cycle, information at a parent node of the search tree to reach a child node that is in the branch from the parent node to the leaf storing address information related to a next location in the predetermined path, the information at the parent node comprising a decision bit and an address of a child node, the child node comprising a left node descriptor and a right node descriptor each storing a decision bit and a address of a next child node in the branch from the parent node to the leaf, the decision bit in the parent node used to determine whether the address stored in the right node descriptor or the left node descriptor of the child node is the address of the node in the branch between the child node and the leaf; and

means for processing information stored in the leaf to determine the address of a next location.

2. The apparatus of claim 1, wherein said search tree comprises a compressed radix tree.

3. The apparatus of claim 2, wherein the means for processing in one memory cycle information at a parent node of the radix tree to reach the leaf containing information used to determine the address of a next location, comprises:

a first engine for processing the decision bit stored in a bit position field of a parent node to determine whether the next child node is defined by the address stored in the right node descriptor or the left node descriptor of the child node, the next child node being in the branch between the parent node and the leaf; and

a second engine for receiving instructions from the first engine for accessing node descriptor information in the memory and information stored in the leaf.

4. The apparatus of claim 2, further comprising a microprocessor for processing information in a head node of the radix tree and for transmitting a start signal to the first engine to execute a sequence of instructions to determine the address of a next location.

5. The apparatus of claim 1, further comprising a route stack for storing the address of a parent node having an attached route, wherein when the means for processing in one memory cycle information at the parent node determines that an attached route field in the parent node indicates that the parent node has an attached route that may contain information relating to an alternate next location, the address of the parent node is stored on the route stack so that if the information stored in the leaf does not contain an address of next in the path between the source location and the destination location, the parent node having an attached route can be processed to determine the address of an alternate next location.

6. The apparatus of claim 1, wherein the means for processing information stored in the leaf comprises a bit mask for masking bits in the address of the destination location and means for comparing a result of so masking to the address information related to the next intermediate location.

7. The apparatus of claim 1, wherein the address information related to a destination location conforms to one of Internet Protocol version 4 and Internet Protocol version 6.

8. The apparatus of claim 1, wherein the information related to a next location is an index into a nexthop table correlates the indices in the nexthop table to addresses of locations.

9. A method for determining a path through a network between a source location and a destination location, the path having a plurality of intermediate locations between the source location and the destination location, each location having an address and having a memory for storing a routing table used to determine the address of a next location in a dynamically varying path between the source location and the destination location, the routing table being stored as a radix tree having parent nodes and child nodes, the radix tree terminating in leaves, the parent nodes and child nodes providing information relating to the address of a leaf which stores information relating to the address of a next location in the predetermined path, the method comprising:

(a) processing in one memory cycle information at a parent node of the radix tree to reach a child node that is in the branch from the parent node to the leaf storing address information related to a next location in the dynamically varying path, each node of the radix tree corresponding to a portion of the address of the destination location, such that the sequence of nodes traversed in traveling from a parent node to a child node relates to a corresponding sequence of bits in the destination address, the information at the parent node comprising a decision bit and an address of a child node, the child node comprising a left node descriptor and right node descriptor each storing a decision bit and an address of a next child node in the branch from the parent node to the leaf, the decision bit in the parent node used to determine whether the address stored in the right node descriptor or the left node descriptor is the address of the next node in the branch between a child node and the leaf;

(b) repeating step (a) until the child node is a leaf; and

(c) processing information stored in the leaf to determine the address of a next location.

10. The method of claim 9, further comprising:

storing the address of a parent node if an attached field in the parent node indicates that the parent node has an attached route that may contain information relating to an alternate next location;

retrieving the address of the parent node stored on the route stack if the information stored in the leaf does not contain a valid address of a next location in the path between the source location and the destination location; and

processing the address of the parent node on the route stack having an attached router to determine the address of an alternate next location.

11. The method of claim 9, wherein the information related to a next location is an index into a nexthop table which correlates the indices in the nexthop table to addresses of locations.

12. A memory for storing data for access by an application program being executed on a data processing system for determining a next location in a network between a source location and a destination location, the data being stored in a search tree having a plurality of nodes in a hierarchical relationship, the nodes arranged in a first, second and third levels, the first, second and third levels comprising:

a first level data structure, accessed in one memory cycle, representing a first level node of the search tree including a pointer field to a node in the second level of the search tree, a bit position field for determining one of a right branch and a left branch in the second level of the search tree and an error checking field for determining that the other first level fields most likely contain valid data;

a second level the data structure, representing a second level node of the search tree including a right branch descriptor and a left branch descriptor, each accessed in one memory cycle, the right branch descriptor and left branch descriptor each having a pointer field to a node in the third level of the search tree, a bit position field for determining one of a right branch and a left branch from the node in the third level of the search tree, and an error checking field for determining that the other second level fields most likely contain valid data; and

a third level data structure, representing a third level node of the search tree that can function as the second level data structure.

13. The memory of claim 12, wherein each second level node contains a node descriptor field having a bit position field and a pointer field, the pointer field storing the address of a next third level node in the branch from the second level node and the bit position field used for specifying a decision bit that determines which bit in a search key is used to determine the next third level node taken on the branch from a second level node to a third level node.

14. The memory of claim 13, wherein the decision bit in each node corresponds to one bit of an address of the destination location, and wherein the nodes traversed on the path from a first level node to a third level node correspond to a sequence of bits comprising a portion of the destination address.

15. The memory of claim 14, wherein a lowest level node in the tree comprises a leaf node that contains information relating to the address of the next location.

16. The memory of claim 12, wherein a node that is not a leaf node further comprises an address for an alternate route from the source location to the destination location.