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

Patent metadata

Field	Value
Publication number	US-10218639-B2
Application number	US-201414210538-A
Country	US
Kind code	B2
Filing date	Mar 14, 2014
Priority date	Mar 14, 2014
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

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 from a first computing device in a network to a second computing device in the network, the request comprises:
an identity of the second computing device;
an identity of a volume of data to be transferred from the first computing device to the second computing device in accordance with the request; and
a deadline, the deadline identifies a time, wherein the transfer of the data from the first computing device to the second computing device is to be completed prior to the time identified in the deadline;

responsive to receiving the request and based upon the request, computing a long-term schedule that covers a first window of time that includes a plurality of time units, the long-term schedule generated to facilitate completion of the transfer of the data from the first computing device to the second computing device prior to the time identified in the deadline, the long-term schedule identifies, for a time unit in the plurality of time units, at least one path in the network over which the data is to be transferred from the first computing device to the second computing device;
based upon the long-term schedule, computing a short-term schedule that covers a second window of time that occurs prior to the first window of time, the short-term schedule comprises fewer time units than the long-term schedule, the short-term schedule computed to facilitate completion of the transfer of the volume of the data from the first computing device to the second computing device prior to the time identified in the deadline, the short-term schedule comprising a routing table for a network infrastructure device in the network, the routing table identifies at least one device to which data received by the network infrastructure device is to be transferred; and
transmitting the routing table to the network infrastructure device, wherein the network infrastructure device transfers the data to the at least one device in accordance with the routing table.

2. The method of claim 1 , further comprising:
receiving a map of the network, the map of the network comprising a plurality of nodes that are respectively representative of devices in the network, the map of the network further comprising a plurality of edges that are representative of links between respective devices in the network; and
generating the long-term schedule based upon the map of the network.

3. The method of claim 2 , further comprising:
responsive to receipt of the map of the network, constructing a network graph that is representative of the network over the plurality of time units, the network graph comprises a plurality of instances of the map of the network that respectively correspond to the plurality of time units, the plurality of instances of the map of the network connected with one another by way of edges between nodes in the plurality of instances of the map of the network that represent common devices, and wherein the long-term schedule is generated based upon the network graph.

4. The method of claim 3 , further comprising, for the data transfer between the first computing device and the second computing device, constraining a number of paths represented in the network graph that can be used to transfer the data from the first computing device to the second computing device to a threshold number of potential paths, wherein generating the long-term schedule is based upon the threshold number of potential paths.

5. The method of claim 1 , further comprising:
receiving a plurality of requests for a respective plurality of data transfers between various computing devices in the network, the plurality of requests specifying a respective plurality of deadlines, the respective plurality of deadlines being different; and
generating the long-term schedule based upon the plurality of requests, the long-term schedule generated to facilitate completion of the data transfers between the various computing devices in the network prior to their respective plurality of deadlines.

6. The method of claim 1 , further comprising:
subsequent to transmitting the routing table to the network infrastructure device, receiving a second data transfer request to transfer second data from a third computing device in the network to a fourth computing device in the network, the second request comprising:
an identity of the fourth computing device;
an identity of a volume of data to be transferred from the third computing device to the fourth computing in accordance with the second request; and
a second deadline, the second deadline identifies a second time, wherein the transfer of the data from the third computing device to the fourth computing device is to be completed prior to the second time identified in the deadline, the second time being different from the first time;

responsive to receiving the second request and based upon the first request and the second request, computing a second long-term schedule that covers a third window of time that includes a second plurality of time units, the second long-term schedule generated to facilitate completion of the transfer of the data from the first computing device to the second computing device prior to the time identified in the deadline and to facilitate completion of the transfer of the second data from the third computing device to the fourth computing device prior to the second time identified in the second deadline, the long-term schedule identifies, for a second time unit in the second plurality of future time units, a first path in the network over which the data is to be transferred from the first computing device to the second computing device and a second path in the network over which the second data is to be transferred from the third computing device to the fourth computing device; and
based upon the second long-term schedule, generating a second short-term schedule that covers a fourth window of time that occurs prior to the third window of time, the second short-term schedule comprises fewer time units than the second long-term schedule, the second short-term schedule generated to facilitate completion of the transfer of the data from the first computing device to the second computing device prior to the time identified in the deadline and to facilitate completion of the transfer of the second data from the third computing device to the fourth computing device prior to the second time identified in the second deadline, the second short-term schedule comprising a second routing table for the network infrastructure device in the network; and
transmitting the second routing table to the network infrastructure device.

7. The method of claim 1 , wherein the long-term schedule is computed in parallel over multiple processor cores.

8. The method of claim 1 , further comprising:
assessing a charge to an owner of the data that is to be transferred from the first computing device to the second computing device based upon the volume of the data and the time identified in the deadline.

9. The method of claim 1 , further comprising dynamically adjusting prices to charge to owners of data that request data transfers over the network, wherein the prices are dynamically adjusted based upon the long-term schedule.

10. The method of claim 1 , further comprising exposing a pricing schedule to owners of data in computing devices in the network, the pricing schedule comprises prices that are based upon historic data transfers in the network.

11. The method of claim 1 , wherein computing the long-term schedule comprises executing a mixed packing and covering algorithm to compute the long-term schedule.

12. The me

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Kandula Srikanth
• Menache Ishai
• Schwartz Roy

Classifications

• H04L67/1078

  Resource delivery mechanisms · CPC title

• H04L47/72

  using reservation actions during connection setup · CPC title

• H04L47/127

  by using congestion prediction · CPC title

• H04L45/121 Primary

  by minimising delays · CPC title

• H04L47/781

  Centralised allocation of resources · CPC title