Network routing using indirect next hop data

• US 9,391,873 B1
• Filed: 02/06/2015
• Issued: 07/12/2016
• 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
• Application Number:
  US14/616,484
• Time in Patent Office: 522 Days
• US Class Current: 1/1
• 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 hardware of a packet forwarding engine 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 each of the leaf nodes stores a first data pointer and a second data pointer that each point to respective data structures that are external to the forwarding tree, wherein the external data structure pointed to by the first pointer specifies a primary next hop and the external data structure pointed to by the second pointer specifies a backup next hop;

forwarding packets with the packet forwarding engine to the primary next hop for at least one of the leaf nodes of the forwarding tree;

in response to a network event, with the packet forwarding engine and for the at least one of the leaf nodes, marking the first data pointer as inactive to promote the second data pointer that defines the backup next hop to a data pointer that defines a new primary next hop; and

forwarding packets with the packet forwarding engine to the new primary next hop.

2. The method of claim 1, wherein forwarding packets with the packet forwarding engine to the new primary next hop comprises:

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

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

traversing, based at least on the set of bits of the key, the forwarding tree within the network device; and

selecting, responsive the first data pointer being marked inactive, the external data structure pointed to by the second pointer to determine the next hop for the packets.

3. The method of claim 1, further comprising:

forwarding, based on the next hop specified by the selected external data structure, the packets to a particular interface port of the network device that is coupled to the network link so as to forward the packet.

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

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

communicating, with the routing engine, the forwarding tree and the data structures that are external to the forwarding tree to the packet forwarding engine.

6. The method of claim 5, wherein marking the first data pointer as inactive to promote the second data pointer that defines the backup next hop to a data pointer that defines a new primary next hop is performed by the hardware within the packet forwarding engine without intervention of the routing engine.

7. A network device comprising:

a packet forwarding engine having hardware 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 each of the leaf nodes stores a first data pointer and a second data pointer that each point to respective data structures that are external to the forwarding tree, wherein the external data structure pointed to by the first pointer specifies a primary next hop and the external data structure pointed to by the second pointer specifies a backup next hop,

wherein the packet forwarding engine is configured to;

initially forward packets to the primary next hop for at least one of the leaf nodes of the forwarding tree;

in response to a network event, mark the first data pointer of the at least one leaf node as inactive to promote the second data pointer that defines the backup next hop to a data pointer that defines a new primary next hop;

forward packets to the new primary next hop.

8. The network device of claim 7, wherein the packet forwarding engine is configured to:

receive, at the network device, the packets to be routed through a network;

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

traverse, based at least on the set of bits of the key, the forwarding tree within the network device; and

select, responsive the first data pointer being marked inactive, the external data structure pointed to by the second pointer to determine the next hop for the packets.

9. The network device of claim 7, wherein the packet forwarding engine selects a particular interface port of the network device to which to forward the packets based on the next hop specified by the selected external data structure.

10. The network device of claim 7, wherein the forwarding tree comprises a radix tree.

11. The network device of claim 7, further comprising:

one or more processors;

a routing engine executed by the one or more processors, the routing engine configured to maintain routing information representative of a topology of a network,

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 communicates the forwarding tree and the data structures to the packet forwarding engine.

12. The network device of claim 11, wherein the packet forwarding engine marks the first data pointer as inactive to promote the second data pointer without intervention of the routing engine.