# US 2017/0286180 A1 · Joint Network and Task Scheduling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286180 A1
- Document ID: US20170286180A1
- Status: Published application
- Kind: A1
- Application number: 15/087,079
- Filed: 2016-03-31
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Ting He; Thai Franck Le; Ali Munir; Ramya Raghavendra
- Web page: https://patentgrep.com/patent/US20170286180A1

## CPC

- G06F 9/5088: {involving task migration}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- 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)}
- 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)}
- G06F 2209/501: Performance criteria
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

The method of claim 1, wherein the performance is predicted based on a flow completion time (FCT).

### Claim 6 (depends on 5)

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

### Claim 7 (depends on 5)

The method of claim 5, wherein for a current flow of size s and link bandwidth of B, FCT(s)=(total #bytes transmitted upon completing s)/B.

### Claim 8 (depends on 5)

The method of claim 5, 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.

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 11)

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

### Claim 13

A system for scheduling tasks in a distributed computing network, the system comprising:
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 state and ii) the scheduling policy of the distributed computing network.

### Claim 14 (depends on 13)

The system of claim 13, 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) a 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.

### Claim 15 (depends on 14)

The system of claim 14, wherein the task scheduler is further configured to:
use delay scheduling to provide multiple candidate resources to serve as the pool of candidate resources.

### Claim 16 (depends on 14)

The system of claim 14, 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.

### Claim 17 (depends on 14)

The system of claim 14, 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.

### Claim 18 (depends on 17)

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

### Claim 19 (depends on 14)

The system of claim 14, wherein the performance is predicted based on a FCT which varies for the given task based on both the network state and the scheduling policy of the distributed computing network.

### Claim 20

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) a 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.
