Joint network and task scheduling

• US 9,940,175 B2
• Filed: 03/31/2016
• Issued: 04/10/2018
• Est. Priority Date: 03/31/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: He, Ting, Le, Thai Franck, Munir, Ali, Raghavendra, Ramya
• Primary Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US15/087,079
• Publication Number:
  US 20170286180A1
• Time in Patent Office: 740 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

Techniques for network state-aware and network scheduling policy-aware task scheduling are provided. In one aspect, a method for scheduling tasks in a distributed computing network includes the steps of: collecting a pool of candidate resources in the distributed computing network for performing a given one of the tasks; predicting a performance of each of the candidate resources in performing the given task based on both i) a state and ii) a scheduling policy of the distributed computing network; and selecting a best candidate resource for the given task based on the performance. A system for scheduling tasks in a distributed computing network is also provided which includes a task scheduler; and a network scheduler, wherein the task scheduler is configured to schedule the tasks in the distributed computing network based on both i) the state and ii) the scheduling policy of the distributed computing network.

Claims

1. A method for scheduling tasks in a distributed computing network, comprising the steps of:

collecting a pool of candidate resources in the distributed computing network for performing a given one of the tasks;

predicting a performance of each of the candidate resources in performing the given task based on both i) network state and ii) a scheduling policy of the distributed computing network; and

selecting a best candidate resource for the given task based on the performance,

wherein the performance is predicted based on a flow completion time (FCT), and wherein for a current flow of size s and link bandwidth of B, FCT(s)=(total #bytes transmitted upon completing s)/B.

2. The method of claim 1, wherein candidate resources comprise servers, virtual machines, or containers.

3. The method of claim 1, further comprising the step of:

using delay scheduling to provide multiple candidate resources to serve as the pool of candidate resources.

4. The method of claim 1, wherein the predicting step comprises the steps of:

hypothetically placing the given task on a given one of the candidate resources; and

analyzing a schedule of the distributed computing network.

5. The method of claim 1, wherein the FCT for the given task varies based on both the network state and the scheduling policy of the distributed computing network.

6. The method of claim 1, wherein the selecting step further comprises the step of:

selecting the best candidate resource that minimizes the FCT for the given task given both the network state and the scheduling policy of the distributed computing network.

7. The method of claim 1, wherein the state of the distributed computing network comprises sizes of all active flows in the distributed computing network.

8. The method of claim 1, wherein the scheduling policy of the distributed computing network is selected from the group consisting of:

fair share, first in first out, shortest flow first, and least attained service first.

9. The method of claim 1, further comprising the step of:

migrating at least one existing task on the best candidate resource for the given task to another one of the candidate resources.

10. The method of claim 9, wherein the existing task has a lower priority than the given task.

16. The system of claim 10, wherein the FCT varies for the given task based on both the network state and the scheduling policy of the distributed computing network.

11. A system for scheduling tasks in a distributed computing network, the system comprising a memory coupled with a processor device, the memory embodying instructions that, when executed by the processor device, cause the processor device to implement:

a task scheduler; and

a network scheduler,

wherein the network scheduler is configured to provide a network state and a scheduling policy of the distributed computing network to the task scheduler, and wherein the task scheduler is configured to schedule the tasks in the distributed computing network based on both i) the network state and ii) the scheduling policy of the distributed computing network, wherein the task scheduler is further configured to;

collect a pool of candidate resources in the distributed computing network for performing a given one of the tasks;

predict a performance of each of the candidate resources in performing the given task based on both i) the network state and ii) the scheduling policy of the distributed computing network; and

select a best candidate resource for the given task based on the performance, wherein the performance is predicted based on a FCT, and wherein for a current flow of size s and link bandwidth of B, FCT(s)=(total #bytes transmitted upon completing s)/B.

12. The system of claim 11, wherein the task scheduler is further configured to:

use delay scheduling to provide multiple candidate resources to serve as the pool of candidate resources.

13. The system of claim 11, wherein the task scheduler is further configured to:

hypothetically place the given task on a given one of the candidate resources; and

analyze a schedule of the distributed computing network.

14. The system of claim 11, wherein the task scheduler is further configured to:

migrate at least one existing task on the best candidate resource to another one of the candidate resources.

15. The system of claim 14, wherein the existing task has a lower priority than the given task.

17. A computer program product for scheduling tasks in a distributed computing network, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:

collect a pool of candidate resources in the distributed computing network for performing a given one of the tasks;

predict a performance of each of the candidate resources in performing the given task based on both i) network state and ii) a scheduling policy of the distributed computing network; and

select a best candidate resource for the given task based on the performance,

wherein the performance is predicted based on a FCT, and wherein for a current flow of size s and link bandwidth of B, FCT(s)=(total #bytes transmitted upon completing s)/B.