Network routing using indirect next hop data

• US 8,953,626 B2
• Filed: 09/09/2013
• Issued: 02/10/2015
• Est. Priority Date: 10/19/2001
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Primary Examiner(s): MEW, KEVIN D
• Application Number:
  US14/021,928
• Publication Number:
  US 20140010114A1
• Time in Patent Office: 519 Days
• Field of Search: 370/389, 370/392, 370/400, 370/408, 370428-429, 709238-239, 709/242, 709/245
• US Class Current: 370/408
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

A router maintains routing information including (i) route data representing destinations within a computer network, (ii) next hop data representing interfaces to neighboring network devices, and (iii) indirect next hop data that maps a subset of the routes represented by the route data to a common one of the next hop data elements. In this manner, routing information is structured such that routes having the same next hop use indirect next hop data structures to reference common next hop data. In particular, in response to a change in network topology, the router need not change all of the affected routes, but only the common next hop data referenced by the intermediate data structures. This provides for increased efficiency in updating routing information after a change in network topology, such as link failure.

Claims

1. A method comprising:

storing, within a network device, a forwarding tree that includes a set of hierarchically arranged nodes, wherein the set of nodes includes a root node, a plurality of intermediate nodes, and a plurality of leaf nodes, wherein the leaf nodes store data pointers to data structures that are external to the forwarding tree, wherein the data structures store next hop data, and wherein at least two of the leaf nodes each include a corresponding data pointer that points to a same one of the data structures that is external to the forwarding tree;

receiving a network update packet at the network device, wherein the network update packet comprises network update information; and

updating network routes for future packets by modifying the next hop data in the data structures that are external to the forwarding tree without modifying the forwarding tree, wherein modifying the next hop data includes changing a specific next hop identified by the same data pointer that is included in the at least two of the leaf nodes so as to alter routes defined by the at least two of the leaf nodes of the forwarding tree without altering data stored within the leaf nodes.

2. The method of claim 1, further comprising:

receiving, at the network device, a packet to be routed through a network;

identifying a key within the packet, wherein the key includes a set of bits that identify a network destination for the packet; and

traversing, based at least on the set of bits of the key, the forwarding tree within the network device, to a particular one of the leaf nodes of the forwarding tree.

3. The method of claim 2, further comprising:

upon traversing the forwarding tree and reaching the particular leaf node of the forwarding tree, using a respective data pointer stored within the particular leaf node to identify a respective one of the data structures that is external to the forwarding tree, wherein the data structures that are external to the forwarding tree store next hop data and the respective one of the data structures defines a particular next hop for the packet, the particular next hop being associated with a particular network device coupled to the network device via a network link; and

forwarding the packet to a particular interface port of the network device that is coupled to the network link so as to forward the packet to the particular next hop defined by the respective one of the data structures that is external to the forwarding tree.

4. The method of claim 1, wherein the forwarding tree comprises a radix tree.

5. The method of claim 1, further comprising:

storing, within each of the leaf nodes, a first data pointer to the data structures that are external to the forwarding tree, wherein the first pointer defines a primary next hop; and

storing, within each of the leaf nodes, a second data pointer to the data structures that are external to the forwarding tree, wherein the second data pointer defines a backup next hop.

6. The method of claim 5, further comprising routing packets to the backup next hop for at least one of the leaf nodes in response to a network event.

7. The method of claim 5, further comprising:

initially routing packets to the primary next hop for at least one of the leaf nodes; and

in response to a network event, re-routing the packets to the backup next hop for the at least one of the leaf nodes.

8. The method of claim 1, further comprising:

storing routing information within a routing engine of the network device;

generating the forwarding tree and the data structures that are external to the forwarding tree based on the routing information; and

storing the forwarding tree and the data structures that are external to the forwarding tree within a packet forwarding engine associated with the network device.

9. The method of claim 8, further comprising:

updating the network routes for the future packets by modifying the next hop data in the data structures in response to receiving updates of the routing information in the routing engine.

10. The method of claim 8, further comprising:

updating the forwarding tree and modifying the next hop data in the data structures in response to receiving the updates of the routing information.

11. The method of claim 8, further comprising storing a copy of the routing information in the routing engine and the packet forwarding engine.

12. A network device comprising:

a routing component that stores a forwarding tree that includes a set of hierarchically arranged nodes, wherein the set of nodes includes a root node, a plurality of intermediate nodes, and a plurality of leaf nodes, wherein the leaf nodes store data pointers to data structures that are external to the forwarding tree, wherein the data structures store next hop data, and wherein at least two of the leaf nodes each include a corresponding data pointer that points to a same one of the data structures that is external to the forwarding tree; and

one or more inbound ports that receive a network update packet at the network device, wherein the network update packet comprises network update information,

wherein in response to receiving the network update packet, the routing component updates network routes for future packets by modifying the next hop data in the data structures that are external to the forwarding tree without modifying the forwarding tree, wherein modifying the next hop data includes changing a specific next hop identified by the same data pointer that is included in the at least two of the leaf nodes so as to alter routes defined by the at least two of the leaf nodes of the forwarding tree without altering data stored within the leaf nodes.

13. The network device of claim 12, wherein the one or more inbound ports receive a packet to be routed through a network, and wherein the routing component:

identifies a key within the packet, wherein the key includes a set of bits that identify a network destination for the packet;

traverses, based at least on the set of bits of the key, the forwarding tree within the network device, to a particular one of the leaf nodes of the forwarding tree.

14. The network device of claim 13,

wherein, upon traversing the forwarding tree and reaching the particular leaf node of the forwarding tree, the routing component uses a respective data pointer stored within the particular leaf node to identify a respective one of the data structures that is external to the forwarding tree, wherein the data structures that are external to the forwarding tree store next hop data and the respective one of the data structures defines a particular next hop for the packet, the particular next hop being associated with a particular network device coupled to the network device via a network link, and

wherein the routing component forwards the packet to a particular interface port of the network device that is coupled to the network link so as to forward the packet to the particular next hop defined by the respective one of the data structures that is external to the forwarding tree.

15. The network device of claim 12, wherein the forwarding tree comprises a radix tree.

16. The network device of claim 12, wherein the routing component:

stores, within each of the leaf nodes, a first data pointer to the data structures that are external to the forwarding tree, wherein the first pointer defines a primary next hop; and

stores, within each of the leaf nodes, a second data pointer to the data structures that are external to the forwarding tree, wherein the second data pointer defines a backup next hop.

17. The network device of claim 12, wherein the routing component:

initially routes packets to the primary next hop for at least one of the leaf nodes; and

in response to a network event, re-routes the packets to the backup next hop for the at least one of the leaf nodes.

18. The network device of claim 12, further comprising:

a packet forwarding engine,

wherein the routing component generates the forwarding tree and the data structures that are external to the forwarding tree based on the routing information, and stores the forwarding tree and the data structures that are external to the forwarding tree in the packet forwarding engine,

wherein the routing component updates the network routes for the future packets by modifying the next hop data in the data structures of the packet forwarding engine in response to receiving updates of the routing information in the routing component.

19. The network device of claim 18, wherein the routing component:

updates the forwarding tree and modifies the next hop data in the data structures in response to receiving the updates of the routing information.

20. A non-transitory computer-readable medium comprising executable instructions that upon execution in a network device, cause the network device to:

store, within a network device, a forwarding tree that includes a set of hierarchically arranged nodes, wherein the set of nodes includes a root node, a plurality of intermediate nodes, and a plurality of leaf nodes, wherein the leaf nodes store data pointers to data structures that are external to the forwarding tree, wherein the data structures store next hop data, and wherein at least two of the leaf nodes each include a corresponding data pointer that points to a same one of the data structures that is external to the forwarding tree;

receive a network update packet at the network device, wherein the network update packet comprises network update information; and

update network routes for future packets by modifying the next hop data in the data structures that are external to the forwarding tree without modifying the forwarding tree, wherein modifying the next hop data includes changing a specific next hop identified by the same data pointer that is included in the at least two of the leaf nodes so as to alter routes defined by the at least two of the leaf nodes of the forwarding tree without altering data stored within the leaf nodes.