System and method for routing around failed links

• US 8,942,085 B1
• Filed: 05/23/2012
• Issued: 01/27/2015
• Est. Priority Date: 05/23/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pani, Ayaskant, Singh, Arjun
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): LOO, JUVENA W
• Application Number:
  US13/478,707
• Time in Patent Office: 979 Days
• Field of Search: 370216-228
• US Class Current: 370/225
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A multi-stage network may include a first stage having a first plurality of switches, a second stage having a second plurality of switches, and a number of links between the first and second stages. A controller in communication with the first plurality of switches and the second plurality of switches may determine a priority path to be utilized by each switch in sending information and a fallback path. If the priority path includes a failed link, the controller implements in one or more of the switches the fallback path for sending the information. The fallback path may, for example, cause the information to be transmitted through a peer router.

Claims

1. A multi-stage network, comprising:

a first stage comprising a first plurality of switches;

a second stage comprising a second plurality of switches;

a number of links between the first plurality of switches and the second plurality of switches; and

a controller in communication with the first plurality of switches and the second plurality of switches, the controller predetermining for each of the second plurality of switches a priority path to be utilized in sending information and a fallback path;

wherein, if a given switch along the priority path includes a failed link, the controller is configured to implement in the given switch the fallback path for sending the information; and

wherein the given switch is configured to impose an upper bound on a number of times any fallback path is used for sending the information.

2. The multi-stage network of claim 1, wherein if the given switch is one of the second plurality of switches, the fallback path from the given switch leads to a peer switch in the second plurality of switches.

3. The multi-stage network of claim 2, further comprising:

a third stage comprising a third plurality of switches;

wherein the fallback path from the given switch to the peer switch routes through one of the third plurality of switches.

4. The multi-stage network of claim 2, wherein if the peer second stage switch includes a failed link, the controller is further configured to implement a second fallback path in the peer switch.

5. The multi-stage network of claim 1, wherein in implementing the fallback path the controller performs load balancing.

6. The multi-stage network of claim 1, wherein:

at least the given switch includes a flow table;

the controller programs the flow table to include the priority path and the fallback path; and

the priority path has priority over the fallback path.

7. The network of claim 6, wherein in implementing the fallback path, the priority path is removed from the flow table.

8. A method for routing information through a multi-stage network including a first stage comprising a first plurality of switches, a second stage comprising a second plurality of switches, and a number of links between the first plurality of switches and the second plurality of switches, the method comprising:

predetermining for at least one of the second plurality of switches a priority path to be utilized in sending information;

predetermining for the at least one of the second plurality of switches a fallback path;

determining whether a link along the priority path is down;

if the link along the priority path is down, implementing the fallback path for sending the information; and

imposing an upper bound on a number of times any fallback path is used for sending the information.

9. The method of claim 8, wherein implementing the fallback path comprises rerouting the information to a peer switch in the second plurality of switches.

10. The method of claim 9, wherein implementing the fallback path comprises rerouting the information through another switch in a higher stage of the network.

11. The method of claim 8, wherein implementing the fallback path comprises removing the priority flow from a flow table in the at least one of the second plurality of switches.

12. A network switch, comprising:

a flow table, the flow table including a priority flow and a fallback flow, each of the priority flow and the fallback flow indicating a logical next hop for information matching a corresponding key;

a processor; and

a memory in communication with the processor, the memory storing instructions executable by the processor to;

send information through the network using the priority flow;

determine whether a link to the logical next hop in the priority flow is down;

if the link to the logical next hop in the priority flow is down, reconfigure the flow table to send the information through the network using the fallback flow; and

set an upper boundary on a number of times the information is sent through the network using fallback flows.

13. The switch of claim 12, wherein the logical next hop in the fallback flow is another network switch in a same tier of the network.

14. The switch of claim 12, wherein the memory further comprises instructions to encapsulate the information sent through the network using the fallback flow.

15. The switch of claim 12, wherein the memory further comprises instructions to:

receive second information, wherein the second information has been encapsulated by another network switch;

decapsulate the second information; and

forward the second information towards its destination based on the flow table.

16. The switch of claim 15, wherein the memory further comprises instructions to:

determine a number of times the second information has been decapsulated by any switch in the network;

identify an upper boundary that has been set on the number of time the second information can be decapsulated; and

discard the packet in response to determining that the determined number of times the second information has been decapsulated equals the upper boundary.