Computing long-term schedules for data transfers over a wide area network

Patent metadata

Field	Value
Publication number	US-10693812-B2
Application number	US-201916251495-A
Country	US
Kind code	B2
Filing date	Jan 18, 2019
Priority date	Mar 14, 2014
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

Various technologies pertaining to scheduling network traffic in a network are described. A request to transfer data from a first computing device to a second computing device includes data that identifies a volume of the data to be transferred and a deadline, where the data is to be transferred prior to the deadline. A long-term schedule is computed based upon the request, wherein the long-term schedule defines flow of traffic through the network over a relatively long time horizon. A short-term schedule is computed based upon the long-term schedule, where devices in the network are configured based upon the short-term schedule.

First claim

What is claimed is:

1. A method comprising:
receiving a request to transfer data of an amount from a first computing device in a network to a second computing device in the network, the request comprising:
an identifier of the second computing device;
an identifier of the amount of the data to be transferred from the first computing device to the second computing device; and
a time in the future, wherein the transfer of the data of the amount from the first computing device to the second computing device is to be completed prior to the time in the future;

based upon the request, computing a schedule for transferring the data of the amount from the first computing device to the second computing device, wherein:
the schedule identifies a first sub-amount of the data that is to be transmitted over a link in the network during a first window of time; and
the schedule identifies a second sub-amount of the data that is to be transmitted over the link in the network during a second window of time, wherein the first sub-amount of the data is different from the second sub-amount of the data, and further wherein the schedule is computed such that the amount of the data will be transferred from the first computing device to the second computing device prior to the time in the future specified in the request when the schedule is adhered to;

computing a second schedule based upon the schedule, wherein the second schedule covers a third window of time that is prior to the first window of time and the second window of time, and further wherein the second schedule comprises a routing table that is to be transmitted to a network infrastructure device in the network, wherein the second schedule is computed such that the amount of the data will be transferred from the first computing device to the second computing device prior to the time in the future specified in the request when the network infrastructure device forwards data according to the routing table;
transmitting the routing table to the network infrastructure device in the network; and
transferring the data from the first computing device to the second computing device based upon the schedule and the second schedule.

2. The method of claim 1 , wherein the first window of time and the second window of time are adjacent to one another in time.

3. The method of claim 1 , wherein the first window of time and the second window of time are non-overlapping.

4. The method of claim 1 , wherein the first window of time and the second window of time have equivalent lengths.

5. The method of claim 1 , further comprising:
setting a price for the transfer of the amount of data, wherein the price for the transfer of the amount of data is based upon:
the amount of the data; and
the time in the future specified in the request.

6. The method of claim 1 , wherein the third window of time is less than an aggregate of the first window of time and the second window of time.

7. The method of claim 1 , further comprising:
subsequent to computing the schedule, receiving a second request to transfer second data of a second amount from a third computing device in the network to a fourth computing device in the network;
based upon the second request, recomputing the schedule to generate a recomputed schedule; and
transferring the data from the first computing device to the second computing device based upon the recomputed schedule.

8. The method of claim 7 , wherein the second request comprises:
an identifier of the fourth computing device;
an identifier of the second amount of the second data to be transferred from the third computing device to the fourth computing device; and
a second time in the future, wherein the transfer of the second data of the second amount from the third computing device to the fourth computing device is to be completed prior to the second time in the future, wherein the second amount of the second data will be transferred from the third computing device to the fourth computing device prior to the second time in the future specified in the second request when the recomputed schedule is adhered to.

9. The method of claim 8 , wherein the second time in the future is different from the time in the future.

10. The method of claim 1 , wherein the schedule is computed based upon a network graph, wherein the network graph comprises a first edge that represents the link during the first window of time and a second edge that represents the link during the second window of time, wherein the first link has a first weight assigned thereto that is indicative of available capacity of the link during the first window of time, and further wherein the second edge has a second weight assigned thereto that is indicative of available capacity of the link during the second window of time.

11. A computing system comprising:
a processor; and
memory storing instructions that, when executed by the processor, cause the processor to perform acts comprising:
computing a schedule based upon a request to transfer data from a first computing device in a network to a second computing device in the network, wherein the request comprises:
an identifier of the second computing device;
an indication of an amount of the data that is to be transferred from the first computing device to the second computing device; and
a time in the future, wherein the data is to be transferred from the first computing device to the second computing device prior to the time in the future specified in the request, wherein:
the schedule identifies a first sub-amount of the data that is to be transmitted over a link in the network during a first window of time; and
the schedule identifies a second sub-amount of the data that is to be transmitted over the link in the network during a second window of time, wherein the first sub-amount of the data is different from the second sub-amount of the data, and further wherein the schedule is computed such that the amount of the data will be transferred from the first computing device to the second computing device prior to the time in the future specified in the request when the schedule is adhered to;

computing a second schedule based upon the schedule, wherein the second schedule covers a third window of time that is prior to the first window of time and the second window of time, and further wherein the second schedule comprises a routing table that is to be transmitted to a network infrastructure device in the network, wherein the second schedule is computed such that the amount of the data will be transferred from the first computing device to the second computing device prior to the time in the future specified in the request when the network infrastructure device forwards data according to the routing table;
transmitting the routing table to the network infrastructure device; and
transmitting the data from the first computing device to the second computing device based upon the schedule and the second schedule.

12. The computing system of claim 11 , the acts further comprising:
subsequent to computing the schedule, recomputing the schedule to generate a recomputed schedule based upon a second request to transfer second data of a second amount from a third computing device in the network to a fourth computing device in the network; and
transferring the data from the first computing device to the second computing device based upon the recomputed schedule.

13. The computing system of claim 11 , wherein the second window of time is longer than the first window of time.

14. The computing system of claim 11 , wherein the schedule comprises:
a first sub-schedule that

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kandula Srikanth
• Menache Ishai
• Schwartz Roy

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L49/254 Primary

  Centralised controller, i.e. arbitration or scheduling · CPC title

• H04W72/12

  Wireless traffic scheduling · CPC title

• H04L12/00 Primary

  Data switching networks (interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00) · CPC title

• H04L67/1078

  Resource delivery mechanisms · CPC title