Network routing using indirect next hop data

• US 8,532,127 B2
• Filed: 07/30/2010
• Issued: 09/10/2013
• Est. Priority Date: 10/19/2001
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Primary Examiner(s): MEW, KEVIN D
• Application Number:
  US12/847,735
• Publication Number:
  US 20100296517A1
• Time in Patent Office: 1,138 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 router, 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, 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, at the network router, 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;

traversing the forwarding tree within the network router, wherein traversing the forwarding tree includes testing the set of bits of the key with respect to different nodes of the set of nodes to traverse a path from the root node though the intermediate nodes to a particular one of the leaf nodes of the forwarding tree, wherein values of the tested bits in the key determine the path that is traversed through the forwarding tree to reach the particular one of the leaf nodes of the forwarding tree;

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 router via a network link;

forwarding the packet to a particular interface port of the network router 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;

receiving a network update packet at the network router, 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, wherein the forwarding tree comprises a radix tree.

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

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

5. The method of claim 3, 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.

6. The method of claim 1, further comprising:

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

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

7. The method of claim 6, 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.

8. The method of claim 6, 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.

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

10. A network router comprising:

a routing engine 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, 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 packet to be routed through a network, wherein the routing engine;

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

traverses the forwarding tree within the network router, wherein traversing the forwarding tree includes testing the set of bits of the key with respect to different nodes of the set of nodes to traverse a path from the root node though the intermediate nodes to a particular one of the leaf nodes of the forwarding tree, wherein values of the tested bits in the key determine the path that is traversed through the forwarding tree to reach the particular one of the leaf nodes of the forwarding tree;

upon traversing the forwarding tree and reaching the particular leaf node of the forwarding tree, 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 router via a network link;

forwards the packet to a particular interface port of the network router 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;

wherein the one or more inbound ports receive a network update packet at the network router, wherein the network update packet comprises network update information; and

wherein in response to the network update packet, the routing engine 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.

11. The network router of claim 10, wherein the forwarding tree comprises a radix tree.

12. The network router of claim 10, wherein the routing engine:

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.

13. The network router of claim 12, wherein the routing engine routes packets to the backup next hop for at least one of the leaf nodes in response to a network event.

14. The network router of claim 12, wherein the routing engine:

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.

15. The network router of claim 10, further comprising:

a packet forwarding engine,

wherein the routing engine 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.

16. The network router of claim 15:

wherein the routing engine 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 engine.

17. The network router of claim 16, wherein the routing engine:

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

18. The network router of claim 15, wherein both the routing engine and the packet forwarding engine maintain a copy of the routing information.

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

store, within the network router, 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, 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;

upon receiving, at the network router, a packet to be routed through a network,

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

traverse the forwarding tree within the network router, wherein traversing the forwarding tree includes testing the set of bits of the key with respect to different nodes of the set of nodes to traverse a path from the root node though the intermediate nodes to a particular one of the leaf nodes of the forwarding tree, wherein values of the tested bits in the key determine the path that is traversed through the forwarding tree to reach the particular one of the leaf nodes of the forwarding tree;

upon traversing the forwarding tree and reaching the particular leaf node of the forwarding tree, use 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 router via a network link;

forward the packet to a particular interface port of the network router 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; and

upon receiving a network update packet at the network router, wherein the network update packet comprises network update information,

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.