Managing network routes from a central server

• US 8,792,374 B1
• Filed: 12/07/2011
• Issued: 07/29/2014
• Est. Priority Date: 12/07/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jain, Sushant, Kumar, Alok, Wanderer, James M., Raghuraman, Anand, Mandal, Subhasree, Singh, Arjun, Siganporia, Aspi Homi, Venkata, Subbaiah Naidu Kotla
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Ganguly, Sumitra
• Application Number:
  US13/314,015
• Time in Patent Office: 965 Days
• Field of Search: 370/252, 370/389, 709/220, 709/221, 709/238
• US Class Current: 370/252
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

Embodiments are directed towards managing network routes using a centralized service on behalf of a network of a plurality of forwarding devices. The centralized service develops a global view of the network based on information from the forwarding devices. The centralized service computes changes to the routing policy for each of the nodes. The centralized service then generates an operational command schedule that is distributed to the forwarding devices using a “make before break” sequence to ensure that transient black holes do not happen as the new routing policy is being implemented.

Claims

1. A network device, comprising:

a memory device that is configured to store data; and

a processor that is operative on the data to perform actions, including;

receiving state information from each forwarding device within a plurality of forwarding devices within a defined network;

determining a network demand for each of the plurality of forwarding devices within the defined network;

determining a set of paths between source-destination pairs of forwarding devices within the plurality of forwarding devices;

for each forwarding device in the plurality of forwarding devices;

determining from the set of paths a desired state, and

determining differences between the received state information and the desired state;

defining an operational command schedule based on the determined differences, the operational command schedule being arranged in a sequence that makes a completed new path structure before breaking an existing path structure between forwarding devices; and

transmitting each operational command, within the operational command schedule based on the arranged sequence, to one or more of the forwarding devices, wherein the one or more forwarding devices are instructed to inhibit implementation of a received operational command until receiving an indication that the new path structure is usable.

2. The network device of claim 1, wherein making a completed new path structure before breaking an existing path structure further comprises monitoring feedback from each forwarding device to ensure that any element within a new path structure that a new element within the new path structure depends upon is acknowledged as installed prior to employing the new path structure.

3. The network device of claim 1, wherein the network device further marks each transmitted operational command as invalid for use until the network device receives an indication from each forwarding device affected by the transmitted operational commands that the operational command is successfully implemented by the forwarding device;

and

when each affected forwarding device has indicated that the operational command is successfully implemented, then the network device further transmits a new command indicating that the new path structure determined by the operational command is useable.

4. The network device of claim 1, wherein the operational command schedule is configured to generate a per forwarding device routing table, the routing table including information about selected destination devices that is useable to tag packets with a tunnel tag.

5. The network device of claim 4, wherein the routing table is further useable by a forwarding device to determine whether a destination device is undefined within the routing table, such that the forwarding device is directed to employ another routing table for routing a packet to the destination device that is undefined within the routing table.

6. The network device of claim 1, wherein the network device employs at least a sequence identifier associated with each transmitted operational command such that forwarding devices are instructed to not implement a received operational command having a sequence identifier that is determined to be prior to another sequence identifier associated with an other operational command.

7. The network device of claim 1, wherein transmitting of an operational command is performed using at least one of a remote procedure call (RPC), or a Extensible Markup Language (XML) message, a Java Remote Method Invocation, or a Common Object Request Broker Architecture (CORBA) message.

8. A system, comprising:

a first network infrastructure having a plurality of forwarding devices therein; and

a network device having a processor that is configured to perform actions, including;

receiving state information from each forwarding device within the first network infrastructure;

determining a network demand for each of the plurality of forwarding devices;

determining a set of paths between source-destination pairs of forwarding devices within the plurality of forwarding devices;

for each forwarding device in the plurality of forwarding devices;

determining from the set of paths a desired state, and

determining a difference between the received state information and the desired state; and

defining an operational command schedule based on the determined difference, the operational command schedule being arranged in a sequence that makes a completed new path structure before breaking an existing path structure between, forwarding devices; and

transmitting each operational command, within the operational command schedule based on the arranged sequence, to one or more of the forwarding devices, wherein the one or more forwarding devices are instructed to inhibit implementation of a received operational command until receiving an indication that the new path structure is usable.

9. The system of claim 8, wherein the network device employs at least a sequence identifier associated with each transmitted operational command such that forwarding devices are instructed to inhibit implementation of a received operational command having a sequence identifier that is determined to be prior to another sequence identifier associated with another operational command.

10. The system of claim 8, wherein the operational command schedule is configured to generate a per forwarding device routing table, the routing table including information about selected destination devices that is useable to tag packets with a tunnel tag.

11. The system of claim 8, wherein making a completed new path structure before breaking an existing path structure further comprises monitoring feedback from each forwarding device to ensure that any element within a new path structure that a new element within the new path structure depends upon is acknowledged as installed prior to employing the new path structure.

12. The system of claim 8, wherein the system further comprises:

a second network infrastructure having a plurality of other forwarding devices therein; and

the network device being further configured to perform actions, including managing centralized path information for the second network infrastructure by performing the steps of claim 8 for the other forwarding devices within the second network infrastructure.

13. The system of claim 8, wherein the first network infrastructure further comprises a controller device that communicates information about the forwarding devices to the network device and communicates the operational commands to the plurality of forwarding devices.

14. The system of claim 8, wherein a sequence identifier is associated with each operational command, the sequence identifier being used to prevent out of order operational commands from being implemented by a forwarding device.

15. A non-transitory computer-readable storage device having computer-executable instructions stored thereon such that when the storage device is accessed by a computing device, the instructions are executable by the computing device to perform actions, comprising:

receiving state information from each forwarding device within a plurality of forwarding devices within a defined network;

determining a network demand for each of the plurality of forwarding devices within the defined network;

determining a set of paths between source-destination pairs of forwarding devices within the plurality of forwarding devices;

for each forwarding device in the plurality of forwarding devices;

determining from the set of paths a desired state, and

determining differences between the received state information and the desired state;

defining an operational command schedule based on the determined differences, the operational command schedule being arranged in a sequence that makes a completed new path structure before breaking an existing path structure between forwarding devices; and

transmitting each operational command, within the operational command schedule based on the arranged sequence, to one or more of the forwarding devices, wherein a sequence identifier is associated with each operational command, the sequence identifier being used to prevent out of order operational commands from being implemented by a forwarding device.

16. The computer-readable storage device of claim 15, wherein the network device further determines whether an operational command is successfully implemented within a respective forwarding device based on receiving a success indicator, and until each element within a route table that a dependent element within the route table depends upon is successfully implemented any op commands associated with the dependent element are not transmitted.

17. The computer-readable storage device of claim 15, wherein defining the operational command schedule is performed using a dependency graph to determine which operational command is to be transmitted before at least one other operational command.

18. The computer-readable storage device of claim 15, wherein the new path structure is implemented within a forwarding device'"'"'s routing table and includes information about a tunnel, a tunnel group, and a flow group mapping.

19. The computer-readable storage device of claim 15, wherein the one or more forwarding devices are instructed to not implement a received operational command having a sequence identifier that is determined to be prior to another sequence identifier associated with another operational command.

20. The computer-readable storage device of claim 15, wherein the operational command schedule is configured to generate a per forwarding device routing table, the routing table including information about selected destination devices that is useable to tag packets with a tunnel tag.