Efficient method for generating asset backup scheduling plans

Patent metadata

Field	Value
Publication number	US-11379313-B2
Application number	US-202017107728-A
Country	US
Kind code	B2
Filing date	Nov 30, 2020
Priority date	Nov 30, 2020
Publication date	Jul 5, 2022
Grant date	Jul 5, 2022

Abstract

An efficient method for generating asset backup scheduling plans. Within a data protection environment, at least two service level metrics may be observed—a recovery point object (RPO) and a recovery time objective (RTO). In order to meet acceptable values for these metrics, on par with established service level agreements, infrastructure employed throughout the data protection environment, as well as the scheduling of asset backup operations, tend to grow in complexity. To address service distributions potentially emerging from the aforementioned complexities, the disclosed method proposes a heuristic approach to generating asset backup scheduling plans, which consider factors such as backup device limitations, RPO violation minimization, asset usage, and asset prioritization.

First claim

What is claimed is:

1. A method for generating asset backup scheduling plans, comprising:
selecting a backup device;
identifying a set of assets assigned to the backup device;
initializing a backup scheduling plan using scheduling state for each asset in the set of assets;
generating a backup priority list comprising a number of entries matching a cardinality of the set of assets;
while the backup priority list comprises at least one entry, performing an iterative process, comprising:
selecting, from at least a subset of the set of assets represented in the at least one entry, a target asset based on at least one backup priority specified in the backup priority list;
identifying a set of backup scheduling options for the target asset;
selecting, for the target asset, a best-fit backup scheduling option from the set of backup scheduling options;
inserting the best-fit backup scheduling option for the target asset into, in order to update, the backup scheduling plan; and
updating the backup priority list.

2. The method of claim 1 , wherein the scheduling state for an asset of the set of assets comprises a set of forbidden time slots associated with the asset, an expected backup time for completing a backup operation targeting the asset, a next backup period specifying a maximum number of time slots between backup operations targeting the asset, and a deadline for triggering the backup operation targeting the asset.

3. The method of claim 2 , wherein the backup scheduling plan is further initialized using a set of tentative start time slots associated with each asset in the set of assets, wherein the set of tentative start time slots for the asset is determined using a set of available time slots associated with the asset and the expected backup time for completing the backup operation targeting the asset.

4. The method of claim 1 , wherein the target asset is associated with a highest backup priority amongst the at least one backup priority specified in the at least one entry of the backup priority list.

5. The method of claim 1 , wherein each backup scheduling option in the set of backup scheduling options for the target asset is defined using a start time slot, a stream identifier associated with one of an at least one incoming data stream available on the backup device, and a backup penalty.

6. The method of claim 5 , wherein selection of the best-fit backup scheduling option is at least based on a lowest value of the backup penalty.

7. The method of claim 6 , wherein selection of the best-fit backup scheduling option is further based on a latest start time slot should a plurality of backup scheduling options in the set of backup scheduling options be defined, at least in part, by the lowest value of the backup penalty.

8. The method of claim 1 , wherein updating the backup priority list, comprises:
moving a deadline for triggering a backup operation targeting the target asset from a previous time slot within the backup scheduling plan to a new time slot; and
modifying, based on the new time slot of the deadline, an entry representative of the target asset in the backup priority list,
wherein modifying the entry is one selected from a group consisting of updating a backup priority for the target asset specified in the entry and removing the entry from the backup priority list.

9. The method of claim 8 , wherein the new time slot for the deadline is positioned relative to a start time slot of the best-fit backup scheduling option and based on a next backup period associated with the target asset.

10. The method of claim 1 , further comprising:
after updating the backup priority list:
making a determination that the backup priority list comprises zero entries;
halting, based on the determination, the iterative process; and
providing the backup scheduling plan to the set of assets for implementation.

11. A non-transitory computer readable medium (CRM) comprising computer readable program code, which when executed by a computer processor, enables the computer processor to:
select a backup device;
identify a set of assets assigned to the backup device;
initialize a backup scheduling plan using scheduling state for each asset in the set of assets;
generate a backup priority list comprising a number of entries matching a cardinality of the set of assets;
while the backup priority list comprises at least one entry, perform an iterative process, comprising:
selecting, from at least a subset of the set of assets represented in the at least one entry, a target asset based on at least one backup priority specified in the backup priority list;
identifying a set of backup scheduling options for the target asset;
selecting, for the target asset, a best-fit backup scheduling option from the set of backup scheduling options;
inserting the best-fit backup scheduling option for the target asset into, in order to update, the backup scheduling plan; and
updating the backup priority list.

12. The non-transitory CRM of claim 11 , wherein the scheduling state for an asset of the set of assets comprises a set of forbidden time slots associated with the asset, an expected backup time for completing a backup operation targeting the asset, a next backup period specifying a maximum number of time slots between backup operations targeting the asset, and a deadline for triggering the backup operation targeting the asset.

13. The non-transitory CRM of claim 12 , wherein the backup scheduling plan is further initialized using a set of tentative start time slots associated with each asset in the set of assets, wherein the set of tentative start time slots for the asset is determined using a set of available time slots associated with the asset and the expected backup time for completing the backup operation targeting the asset.

14. The non-transitory CRM of claim 11 , wherein the target asset is associated with a highest backup priority amongst the at least one backup priority specified in the at least one entry of the backup priority list.

15. The non-transitory CRM of claim 11 , wherein each backup scheduling option in the set of backup scheduling options for the target asset is defined using a start time slot, a stream identifier associated with one of an at least one incoming data stream available on the backup device, and a backup penalty.

16. The non-transitory CRM of claim 15 , wherein selection of the best-fit backup scheduling option is at least based on a lowest value of the backup penalty.

17. The non-transitory CRM of claim 16 , wherein selection of the best-fit backup scheduling option is further based on a latest start time slot should a plurality of backup scheduling options in the set of backup scheduling options be defined, at least in part, by the lowest value of the backup penalty.

18. The non-transitory CRM of claim 11 , comprising computer readable program code to update the backup priority list, which when executed by the computer processor, enables the computer processor to:
move a deadline for triggering a backup operation targeting the target asset from a previous time slot within the backup scheduling plan to a new time slot; and
modify, based on the new time slot of the deadline, an entry representative of the target asset in the backup priority list,
wherein modifying the entry is one selected from a group consisting of updating a backup priority for the target asset specified in the entry and removing the entry from the backup priority list.

19. The non-transitory CRM of claim 18 , wherein the new time

Assignees

• Emc Ip Holding Co Llc

Inventors

• Barbalho Hugo De Oliveira
• Calmon Tiago Salviano
• Vera Sousa Eduardo

Classifications

• G06F11/1461 Primary

  Backup scheduling policy · CPC title

• G06F11/1464

  for networked environments · CPC title

• G06F11/1451

  by selection of backup contents · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title