Pre-Computation of Backup Topologies in Computer Networks

• US 20160026542A1
• Filed: 07/22/2014
• Published: 01/28/2016
• Est. Priority Date: 07/22/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: VASSEUR, Jean-Philippe, HUI, Jonathan
• Granted Patent: US 9,317,378 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

In one embodiment, a method includes: receiving, at a device of a computer network, a request to build at least part of a backup directed acyclic graph (BDAG) of backup devices for routing traffic within the computer network in case of a power outage, the request comprising at least one requirement specifying to use a device remaining powered after the power outage as a backup device; and in response to receiving the request: identifying a set of backup devices, each of the backup devices fulfilling the at least one requirement; selecting a backup device from the set of backup devices; and synchronizing the device with the backup device according to a backup operation strategy received from the backup device.

Claims

1. A method comprising:

receiving, at a device of a computer network, a request to build at least part of a backup directed acyclic graph (BDAG) of backup devices for routing traffic within the computer network in case of a power outage, the request comprising at least one requirement specifying to use a device remaining powered after the power outage as a backup device; and

in response to receiving the request;

identifying a set of backup devices, each of the backup devices fulfilling the at least one requirement;

selecting a backup device from the set of backup devices; and

synchronizing the device with the backup device according to a backup operation strategy.

2. The method of claim 1, wherein said backup operation strategy comprises defining a link capacity and a unicast schedule allocated by the backup device to the device for routing the traffic in case of a power outage.

3. The method of claim 1, wherein identifying comprises reading an indicator that indicates whether the backup device is expected to be affected by the power outage.

4. The method of claim 3, wherein the indicator further indicates how the backup device is expected to be affected by the power outage.

5. The method of claim 4, wherein the indicator indicates that a backup device has a remaining lifetime after the power outage that is more than a threshold value.

6. The method of claim 1, wherein identifying comprises reading a time-length value (TLV) that indicates at least one of:

an estimated remaining lifetime after the power outage;

or an electrical distribution feeder.

7. The method of claim 6, wherein the TLV indicates that a backup device has a remaining lifetime that is more than a threshold value and/or indicates that the backup device has not a same distribution feeder as the device.

8. The method of claim 1, further comprising:

receiving a traffic policy to use for routing the traffic to the selected backup device, the traffic policy specifying how to reduce the traffic routed to the selected backup device in case of the power outage.

9. The method of claim 8, wherein the traffic policy specifies at least one of:

a particular type of traffic accepted by the selected backup device;

or an amount of traffic accepted by the selected backup device.

10. The method of claim 1, wherein the receiving, identifying, selecting and synchronizing steps are performed by a plurality of devices within the computer network to build the BDAG for routing traffic within the computer network in case of the power outage.

11. A method comprising:

receiving, at a backup device of a computer network, an estimate of an amount and a pattern of traffic that will be routed from one device of the network to the backup device in case of a power outage;

computing a backup operation strategy for the backup device, the backup operation strategy defining a link capacity and a unicast schedule allocated by the backup device to the one device for routing the traffic in case of the power outage; and

synchronizing the backup device with the one device using the computed operation backup strategy.

12. The method of claim 11, wherein the backup device is selected as a backup device for both the one device and at least one additional device;

and wherein the backup operation strategy of the backup device defines a link capacity and a unicast schedule allocated by the backup device to each of the one device and the at least one additional device.

13. The method of claim 12, further comprising:

computing an overall amount of traffic expected to be received at the backup device in case of the power outage;

defining a traffic policy for the backup device, the traffic policy specifying how to reduce the traffic routed to the selected backup device in case of the power outage; and

applying the traffic policy if a backup device capacity is less than the computed overall amount of expected traffic.

14. The method of claim 13, wherein the traffic policy specifies at least one of:

a particular type of traffic accepted by the backup device;

or an amount of traffic accepted by the backup device for each of the one device and the at least one additional device.

15. A method comprising:

receiving, at a path computation element (PCE), information identifying a set of backup devices for one device of a computer network that received a request to build a backup directed acyclic graph (BDAG), the request comprising at least one requirement specifying to use a device remaining powered after the power outage as a backup device, and wherein, each backup device of the set of backup devices fulfills the at least one requirement;

selecting one backup device from the set of backup devices;

computing a backup operation strategy using a traffic matrix and collision domains of the computer network, the backup operation strategy defining a link capacity and a unicast schedule allocated by the selected backup device to the one device for routing the traffic in case of a power outage; and

sending the computed backup operation strategy to the selected backup device for later synchronization with the one device.

16. The method of claim 15, wherein the receiving, selecting, computing and sending steps are performed for a plurality of devices within the computer network to build the BDAG for routing traffic within the computer network in case of the power outage.

17. The method of claim 16, wherein one backup device is selected by the PCE for one device and at least one additional device;

and wherein the computed backup operation strategy defines a link capacity and a unicast schedule allocated by the one backup device to each of the one device and the at least one additional device.

18. The method of claim 17, further comprising:

computing an overall amount of traffic received at each of the selected one backup device in case of power outage using the traffic matrix and the collision domains;

defining a traffic policy specifying how to reduce the traffic routed to each of the selected one backup device; and

sending the traffic policy to each of the selected one backup device, the traffic policy being applied if one of the selected one backup device capacity is less than the computed overall amount of traffic.

19. The method of claim 18, wherein the traffic policy specifies at least one of:

a particular type of traffic accepted by the backup device;

or an amount of traffic accepted by the backup device.

20. The method of claim 15, wherein the PCE is located at a root device of the BDAG.

21. An apparatus, comprising:

one or more network interfaces to communicate with one or more devices of a computer network;

a processor coupled to the one or more network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed being operable to;

receive a request to build at least a part of a backup directed acyclic graph (BDAG) for routing traffic within the computer network in case of a power outage, the request comprising at least one requirement specifying to use a device remaining powered after the power outage as a backup device; and

in response to the received request;

identify a set of backup devices, each backup device of the set of backup devices fulfilling the at least one requirement;

select a backup device from the set of backup devices; and

synchronize with the backup device according to a backup operation strategy received from the backup device.

22. An apparatus, comprising:

one or more network interfaces to communicate with one or more devices of a computer network;

a processor coupled to the one or more network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed being operable to;

receive an estimate of an amount and a pattern of traffic that will be routed from one device of the network in case of a power outage;

compute a backup operation strategy, the backup operation strategy defining a link capacity and a unicast schedule allocated to the one device for routing the traffic in case of the power outage; and

synchronizing with the one device using the computed operation backup strategy.

23. An apparatus, comprising:

one or more network interfaces to communicate with one or more devices of a computer network;

a processor coupled to the one or more network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed being operable to;

receive information identifying a set of backup devices for one device of a computer network that received a request to build a backup directed acyclic graph (BDAG), the request comprising at least one requirement specifying to use a device remaining powered after the power outage as a backup device, and wherein, each backup device of the set of backup devices fulfills the at least one requirement;

select one backup device from the set of backup devices;

compute a backup operation strategy using a traffic matrix and collision domains of the computer network, the backup operation strategy defining a link capacity and a unicast schedule allocated by the selected backup device to the one device for routing the traffic in case of a power outage; and

send the computed backup operation strategy to the selected backup device for later synchronization with the one device.