Forwarding tree having multiple bit and intermediate bit pattern comparisons

• US 7,903,658 B1
• Filed: 03/26/2009
• Issued: 03/08/2011
• Est. Priority Date: 11/08/2005
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kireeti, Kompella, Frailong, Jean-Marc, Sindhu, Pradeep
• Primary Examiner(s): Sam; Phirin
• Application Number:
  US12/411,964
• Time in Patent Office: 712 Days
• Field of Search: None
• US Class Current: 370/392
• 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/74591 using content-addressable memories [CAM]

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.

Claims

1. 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, by testing two or more path control bits within the key per each of the traversed nodes, including 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, wherein values of the two or more 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.

2. The method of claim 1,

wherein each of the traversed nodes stores data specifying a pattern, and

wherein traversing the nodes of the tree further comprises testing one or more bits of the key in addition to the path control bits for equality to the pattern.

3. The method of claim 2, wherein the pattern indicates whether subsequent nodes of the forwarding tree provide a better match for the key relative to a current node being traversed.

4. The method of claim 2, further comprising terminating the traversal of the forwarding tree at an internal node when the pattern fails to match the bits of the key.

5. The method of claim 1, wherein traversing nodes of a forwarding tree comprises testing three or more path control bits within the key per each of the traversed nodes, wherein values of the three or more path control bits in the key determine a path traversed along the tree.

6. The method of claim 5,

wherein the three or more path control bits per each of the traversed nodes comprise a primary path control bit, two secondary path control bits, and four tertiary path control bits, and

wherein testing the path control bits comprises testing the primary path control bit, testing at least one of the secondary path control bits, and testing at least one of the tertiary path control bits, per each of the traversed nodes.

7. The method of claim 6,

wherein each of the traversed nodes stores data specifying a pattern,

wherein traversing the nodes comprises testing one or more bits of the key in addition to the path control bits for equality to the pattern, and

wherein the one or more bits include bits surrounding the primary path control bit, the secondary path control bits, and the tertiary path control bits.

8. The method of claim 1, wherein taking an action on the packet comprises forwarding the packet according to the next hop data.

9. The method of claim 1, wherein taking an action on the packet comprises:

accessing the next hop data associated with the end node to select a next hop; and

forwarding the packet to an output port based on the selected next hop.

10. The method of claim 1, wherein the end node is a leaf node.

11. The method of claim 1, wherein the end node is an internal node.

12. The method of claim 1,

wherein testing the bit of the key corresponding to the specified secondary path control bit comprises:

testing the bit of the key corresponding to the specified secondary path control bit when the bit corresponding to the primary control bit is zero.

13. The method of claim 1, wherein each node comprises a plurality of secondary path control bits.

14. The method of claim 1, wherein secondary path control bit is expressed as an offset from the primary path control bit.

15. The method of claim 1, wherein each node includes a type field that indicates a type of the node.

16. The method of claim 1, further comprising storing the forwarding information in the form of a radix tree.

17. The method of claim 16, further comprising storing the radix tree in the form of one of more tables or link lists.

18. The method of claim 1,

wherein each of the traversed nodes specifies a primary path control bit and at least two secondary path control bits s0 and s1, 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.

19. The method of claim 18, wherein each of the secondary path control bits is expressed as an offset from the primary path control bit.

20. The method of claim 1,

wherein each of the traversed nodes specifies a primary path control bit, and at least two secondary path control bits,

wherein the nodes specify the primary path control bit and the secondary path control bits in accordance with a hierarchy defined by the forwarding tree, and

wherein the value of each of the tested bits determines the subsequent secondary bit to test along the hierarchy.

21. The method of claim 20, wherein each of the secondary path control bits is expressed as an offset from the primary path control bit.

37. The method of claim 1, wherein at least one of the nodes is linked to at least three child nodes of the at least one node in the forwarding tree.

22. 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, and wherein at least one of the nodes is linked to at least three child nodes of the at least one node in the forwarding tree; 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.

23. The device of claim 22,

wherein each of the traversed nodes stores data specifying a pattern, and

wherein the packet-forwarding engine tests one or more bits of the key other than the path control bits for equality to the pattern.

24. The device of claim 23, wherein the pattern indicates whether subsequent nodes of the forwarding tree provide a better match for the key relative to a current node being traversed.

25. The device of claim 23, wherein the packet-forwarding engine terminates the traversal of the forwarding tree at an internal node when the pattern fails to match the bits of the key.

26. The device of claim 22, wherein the packet-forwarding engine:

accesses next hop data associated with the end node to select the next hop, and forwards

the packet to one of the output ports based on the selected next hop.

27. The device of claim 22, wherein the end node is a leaf node.

28. The device of claim 22, wherein the end node is an internal node.

29. The device of claim 22,

wherein each of the nodes specifies a primary path control bit, and at least one secondary path control bit, and

wherein the packet-forwarding engine:

tests a bit of the key corresponding to the specified primary path control bit; and

tests a bit of the key corresponding to the specified secondary path control bit when the bit corresponding to the primary control bit is zero.

30. The device of claim 22, wherein each node includes a type field that indicates a type of the node.

31. The device of claim 22, wherein the device comprises a network router.

32. The device of claim 22, wherein the device comprises a firewall, a session border controller, or a virtual private network (VPN) device.

33. The device of claim 22, wherein the forwarding information comprises a radix tree.

34. The device of claim 22, wherein the forwarding information comprises a table or a link list.

35. A computer-readable medium comprising instructions for causing a programmable processor to:

identify a key within a network packet;

traverse nodes of a forwarding tree within a network packet, wherein each of the nodes specifies a primary path control bit, and at least one secondary path control bit, by testing two or more path control bits within the key per each of the traversed nodes, including 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, wherein values of the two or more path control bits in the key determine a path traversed along the tree; and

forward the packet according to a forwarding next hop associated with an end node of the traversed path.

36. The computer-readable medium of claim 35,

wherein each of the traversed nodes stores data specifying a pattern, and

wherein the instructions cause the processor to test one or more intermediate bits of the key other than the path control bits for equality to the pattern.