Optimization of distributed tunnel rerouting in a computer network with path computation at an intermediate node
First Claim
Patent Images
1. A method, comprising:
- determining a set of two or more tunnels traverse a particular link of an intermediate node, wherein the particular link of the intermediate node extends from the intermediate node;
in response to determining the set of two or more tunnels traverse the particular link of the intermediate node, computing, at the intermediate node, reroute paths for the set of tunnels, the computed reroute path for each tunnel extending from a respective head-end node of the tunnel to a respective tail-end node of the tunnel and not including the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node adjacent to the particular link;
determining an order in which the set of tunnels are to be rerouted to result in the computed reroute paths; and
informing respective head-end nodes of the computed reroute paths and of timestamps corresponding to the order in which the set of tunnels are to be rerouted on the computed reroute paths, wherein the respective head-end nodes are adapted to reroute their respective tunnels over the computed reroute paths at times substantially equal to the timestamps in response to determining the particular link has failed.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, an intermediate node computes paths for a set of tunnels that do not include a particular link (e.g., and possibly a scaled-down bandwidth for each tunnel), considering all of the tunnels of the set. The intermediate node informs head-end nodes of the tunnels of the computed paths (e.g., and scaled bandwidth) and/or a time to reroute the tunnels.
-
Citations
18 Claims
-
1. A method, comprising:
-
determining a set of two or more tunnels traverse a particular link of an intermediate node, wherein the particular link of the intermediate node extends from the intermediate node; in response to determining the set of two or more tunnels traverse the particular link of the intermediate node, computing, at the intermediate node, reroute paths for the set of tunnels, the computed reroute path for each tunnel extending from a respective head-end node of the tunnel to a respective tail-end node of the tunnel and not including the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node adjacent to the particular link; determining an order in which the set of tunnels are to be rerouted to result in the computed reroute paths; and informing respective head-end nodes of the computed reroute paths and of timestamps corresponding to the order in which the set of tunnels are to be rerouted on the computed reroute paths, wherein the respective head-end nodes are adapted to reroute their respective tunnels over the computed reroute paths at times substantially equal to the timestamps in response to determining the particular link has failed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. An intermediate node, comprising:
-
one or more network interfaces adapted to communicate with one or more head-end nodes; at least one network interface from which extends a particular link; one or more processors adapted to execute one or more processes; and a memory adapted to store a rerouting process executable by each processor, the rerouting process when executed operable to;
i) determine a set of two or more tunnels traverse the particular link which extends from the at least one network interface, ii) in response to determination the set of two or more tunnels traverse the particular link which extends from the at least one network interface, compute reroute paths for the set of tunnels, the computed reroute paths for each tunnel to extend from a respective head-end node of the tunnel to a respective tail-end node of the of the tunnel and to not include the particular link, the computed reroute path for each tunnel computed by consideration of each of the tunnels of the set and application of a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node, iii) determine an order in which the set of tunnels are to be rerouted to result in the computed reroute paths, and iv) inform respective head-end nodes of the computed reroute paths and of timestamps corresponding to the order in which the set of tunnels are to be rerouted on the computed reroute paths, wherein the respective head-end nodes are adapted to reroute their respective tunnels over the computed reroute paths at times substantially equal to the timestamps in response to determination the particular link has failed. - View Dependent Claims (15, 16, 17)
-
-
14. A method, comprising:
-
determining, at an intermediate node, a set of two or more tunnels traverse a particular link of the intermediate node, wherein the particular link of the intermediate node extends from the intermediate node; in response to determining the set of two or more tunnels traverse the particular link of the intermediate node, computing, at the intermediate node, reroute paths for the set of tunnels that do not include the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node connected to the particular link; determining an order in which the set of tunnels are to be rerouted to result in the computed reroute paths; and informing, by the intermediate node, a head-end node of each of the tunnels of a timestamp corresponding to a respective tunnel to indicate the order in which the set of tunnels are to be rerouted, wherein the head-end nodes are adapted to reroute their respective tunnels over their own computed reroute paths at a time substantially equal to the timestamp in response to an inability to use the particular link.
-
-
18. An intermediate node, comprising:
-
one or more network interfaces configured to communicate with one or more head-end nodes; at least one network interface from which extends a particular link; one or more processors configured to execute one or more processes; and a memory configured to store a rerouting process executable by the one or more processors, the rerouting process when executed operable to; determine a set of two or more tunnels traverse the particular link which extends from the at least one network interface, response to determination the set of two or more tunnels traverse the particular link which extends from the at least one network interface, compute reroute paths for the set of tunnels that do not include the particular link to reroute around the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node, determine an order in which the set of tunnels are to be rerouted to result in the computed reroute paths, and inform a head-end node of each of the tunnels of the set of a timestamp associated with a respective tunnel, the timestamp to indicate when the head-end node is to attempt to reroute the respective tunnel over its own computed reroute path to have the set of tunnels rerouted in the determined order.
-
Specification