Granted Patent B2

US 9,055,086 · App. 13/338,636 · Granted Jun 9, 2015

Abstract

Claims (62)

1. A data transfer manager for managing data transfer from a datacenter configured to communicate over at least one link, comprising:

a scheduler device comprising at least one processor, the scheduler device being configured to schedule a plurality of jobs for communicating data from the datacenter, the scheduler device,

determines a minimum bandwidth requirement of the plurality of jobs, respectively,

determines a maximum bandwidth limit of the plurality of jobs, respectively, and

determines a flex parameter of the plurality of jobs, respectively, the flex parameter indicates how much allocated bandwidth can vary between adjacent data transfer periods for the respective one of the plurality of jobs;

wherein

the scheduler device assigns a deadline to the plurality of jobs, respectively, the assigned deadlines respectively indicating whether there can be any delay in communicating the data of the respective one of the plurality of jobs over the at least one link;

a non-pre-emptible job is a job that has to be allocated at least some bandwidth in a next scheduled data transfer period;

a pre-emptible job is a job that can go without any allocated bandwidth in the next scheduled data transfer period; and

the scheduler schedules the plurality of jobs in the next scheduled data transfer period by

giving priority to any non-re-emptible jobs of the plurality of jobs over any pre-emptible jobs of the plurality of jobs, and

giving priority among non-pre-emptible jobs of the plurality of jobs in an increasing order of flex parameter then in an increasing order of assigned deadline for jobs having the same flex parameter and then in a decreasing order of job size for jobs having the same flex parameter and the same assigned deadline.

2. The data transfer manager of claim 1 , wherein the scheduler schedules any pre-emptible jobs of the plurality of jobs by giving priority among the pre-emptible jobs in increasing order of the deadline and in increasing order of the flex parameter for jobs having the same deadline.

3. The data transfer manager of claim 2 , wherein

the scheduler determines whether there is excess capacity available after the non-pre-emptible jobs have been scheduled; and

the scheduler schedules any pre-emptible jobs in the next scheduled data transfer period if there is excess capacity.

4. The data transfer manager of claim 1 , wherein

the scheduler determines whether an available capacity during the next data transfer period is sufficient to schedule all of the non-pre-emptible jobs; and

the scheduler increases an amount of capacity if the available capacity is insufficient to schedule all of the non-pre-emptible jobs.

5. The data transfer manager of claim 1 , wherein

the scheduler determines an estimated capacity required for non-pre-emptible jobs of the plurality of jobs for each scheduled data transfer period;

the scheduler determines an actual capacity used by non-pre-emptible jobs in each data transfer period;

the scheduler determines a prediction error based on a difference between the estimated capacity and the actual capacity for each data transfer period; and

the scheduler reserves an amount of capacity slack for a next scheduled data transfer period based on the prediction error.

6. The data transfer manager of claim 5 , wherein

the scheduler maintains a list of prediction errors over a selected time; and

the scheduler determines the amount of capacity slack for the next scheduled data transfer period based on a selected percentile of the list of prediction errors.

7. The data transfer manager of claim 5 , wherein

the scheduler determines an average of prediction errors over a selected time; and

the scheduler determines the estimated capacity based on the average.

8. The data transfer manager of claim 7 , wherein the scheduler determines the average as a weighted average wherein the most recent prediction error is more heavily weighted than older prediction errors.

9. A method of managing data transfer from a datacenter configured to communicate over at least one link, comprising

using a scheduler comprising at least one processor for:

determining a minimum bandwidth requirement of a plurality of jobs, respectively,

determining a maximum bandwidth limit of the plurality of jobs, respectively, and

determining a flex parameter of the plurality of jobs, respectively, the flex parameter indicates how much allocated bandwidth can vary between adjacent data transfer periods for the respective one of the plurality of jobs;

assigning a deadline to the plurality of jobs, respectively, the assigned deadlines respectively indicating whether there can be any delay in communicating the data of the respective one of the plurality of jobs over the at least one link;

wherein

a non-pre-emptible job is a job that has to be allocated at least some bandwidth in a next scheduled data transfer period;

a pre-emptible job is a job that can go without any allocated bandwidth in the next scheduled data transfer period; and

the method comprises scheduling the plurality of jobs in the next scheduled data transfer period by

giving priority to any non-re-emptible jobs of the plurality of jobs over any pre-emptible jobs of the plurality of jobs, and

giving priority among non-pre-emptible jobs of the plurality of jobs in an increasing order of flex parameter then in an increasing order of assigned deadline for jobs having the same flex parameter and then in a decreasing order of job size for jobs having the same flex parameter and the same assigned deadline.

10. The method of claim 9 , comprising scheduling any pre-emptible jobs of the plurality of jobs by giving priority among the pre-emptible jobs in increasing order of the deadline and in increasing order of the flex parameter for jobs having the same deadline.

11. The method of claim 10 , comprising

determining whether there is excess capacity available after the non-pre-emptible jobs have been scheduled; and

scheduling any pre-emptible jobs in the next scheduled data transfer period if there is excess capacity.

12. The method of claim 9 , comprising

determining whether an available capacity during the next data transfer period is sufficient to schedule all of the non-pre-emptible jobs; and

increasing an amount of capacity if the available capacity is insufficient to schedule all of the non-pre-emptible jobs.

13. The method of claim 9 , comprising

determining an estimated capacity required for non-pre-emptible jobs of the plurality of jobs for each scheduled data transfer period;

determining an actual capacity used by non-pre-emptible jobs in each data transfer period;

determining a prediction error based on a difference between the estimated capacity and the actual capacity for each data transfer period; and

reserving an amount of capacity slack for a next scheduled data transfer period based on the prediction error.

14. The method of claim 13 , comprising

maintaining a list of prediction errors over a selected time; and

determining the amount of capacity slack for the next scheduled data transfer period based on a selected percentile of the list of prediction errors.

15. The method of claim 13 , comprising

determining an average of prediction errors over a selected time; and

determining the estimated capacity based on the average.

16. The method of claim 15 , comprising determining the average as a weighted average wherein the most recent prediction error is more heavily weighted than older prediction errors.

Assignments (10)