NETWORK ROUTING USING INDIRECT NEXT HOP DATA
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
-
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.
-
Specification