Forwarding tree having multiple bit and intermediate bit pattern comparisons
First Claim
1. A method comprising:
- identifying a key within a network packet;
traversing nodes of a forwarding tree within a network device by testing two or more path control bits within the key per each of the traversed nodes, wherein values of the two or more path control bits in the key determine a path traversed along the tree, wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits in accordance with a hierarchy defined by the forwarding tree, wherein the value of the primary path control bit determines which of the at least two secondary path control bits to test within the key, and wherein each of the secondary path control bits is expressed as an offset from the primary path control bit; and
taking an action on the packet based on next hop data associated with an end node of the traversed path.
1 Assignment
0 Petitions
Accused Products
Abstract
Principles of the invention are directed to techniques for allowing a router forwarding packets within a computer network to perform two or more forwarding tree decisions per memory access. The router may implement forwarding information in the form of a radix tree having a number of nodes, and received packets may contain keys identifying a packet destination. The router may traverse the tree by testing two or more path control bits within the key per each of the traversed nodes. The values of the path control bits in the key determine the path traversed along the tree. The router also stores intermediate bit patterns at each node and tests intermediate bits in the key to determine whether a particular node is the best match to the routing prefix contained in the key, thereby eliminating a need to backtrack up the tree.
-
Citations
34 Claims
-
1. A method comprising:
-
identifying a key within a network packet; traversing nodes of a forwarding tree within a network device by testing two or more path control bits within the key per each of the traversed nodes, wherein values of the two or more path control bits in the key determine a path traversed along the tree, wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits in accordance with a hierarchy defined by the forwarding tree, wherein the value of the primary path control bit determines which of the at least two secondary path control bits to test within the key, and wherein each of the secondary path control bits is expressed as an offset from the primary path control bit; and taking an action on the packet based on next hop data associated with an end node of the traversed path. - View Dependent Claims (2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18)
-
-
6. A method comprising:
-
identifying a key within a network packet; traversing nodes of a forwarding tree within a network device by testing a primary path control bit, testing at least one of two secondary path control bits, and testing at least one of the four tertiary path control bits, per each of the traversed nodes, wherein values of the primary path control bits, the secondary path control bits, and the tertiary path control bits in the key determine a path traversed along the tree; and taking an action on the packet based on next hop data associated with an end node of the traversed path. - View Dependent Claims (7)
-
-
14. A method comprising:
-
identifying a key within a network packet; traversing nodes of a forwarding tree within a network device, wherein each of the nodes specifies a primary path control bit, and at least one secondary path control bit, wherein the secondary path control bit is expressed as an offset from the primary path control bit, and wherein traversing the nodes of the forwarding tree comprises; testing a bit of the key corresponding to the specified primary path control bit; and testing a bit of the key corresponding to the specified secondary path control bit when the bit corresponding to the primary control bit is zero.
-
-
19. A method comprising:
-
identifying a key within a network packet; traversing nodes of a forwarding tree within a network device, wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits s0 and s1, wherein each of the secondary path control bits is expressed as an offset from the primary path control bit, and wherein traversing nodes of the forwarding tree comprises; testing a bit of the key corresponding to the specified primary path control bit; testing a bit of the key corresponding to the specified secondary path control bit s0 when the bit corresponding to the primary control bit is zero; and testing a bit of the key corresponding to the specified secondary path control bit s1 when the bit corresponding to the primary control bit is one.
-
-
20. A device comprising:
-
an input port for receiving a network packet containing a key; a packet-forwarding engine that traverses nodes of a forwarding tree by testing two or more path control bits in the key per each of the traversed nodes, wherein values of the two or more path control bits in the key determine a path traversed along the tree, wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits in accordance with a hierarchy defined by the forwarding tree, wherein the value of the primary path control bit determines which of the at least two secondary path control bits to test within the key, and wherein each of the secondary path control bits is expressed as an offset from the primary path control bit; and one or more output ports for forwarding the packet according to a forwarding next hop associated with an end node of the traversed path. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A computer-readable medium comprising instructors for causing a programmable processor to:
-
identify a key within a network packet; traverse nodes of a forwarding tree within a network packet by testing two or more path control bits within the key per each of the traversed nodes, wherein values of the two or more path control bits in the key determine a path traversed along the tree, wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits in accordance with a hierarchy defined by the forwarding tree, wherein the value of the primary path control bit determines which of the at least two secondary path control bits to test within the key, and wherein each of the secondary path control bits is expressed as an offset from the primary path control bit; and forward the packet according to a forwarding next hop associated with an end node of the traversed path. - View Dependent Claims (34)
-
Specification