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

• US 10,218,639 B2
• Filed: 03/14/2014
• Issued: 02/26/2019
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kandula, Srikanth, Menache, Ishai, Schwartz, Roy
• Primary Examiner(s): Hussain, Tauqir
• Assistant Examiner(s): Grijalva Lobos, Boris D
• Application Number:
  US14/210,538
• Publication Number:
  US 20150264135A1
• Time in Patent Office: 1,810 Days
• CPC Class Codes: H04L 41/50 Network service management, e.g. ensuring proper service fulfilment according to agreements
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/72 using reservation actions during connection setup
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 67/1078 Resource delivery mechanisms
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

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.

Claims

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 method of claim 1, further comprising:

receiving an indication that at least one link in the network is down; and

computing the long-term schedule based upon the indication that the at least one link in the network is down.

13. A controller computing device comprising:

at least one processor; and

memory that stores instructions that, when executed by the at least one processor, cause the at least one processor to perform acts comprising;

receiving a plurality of data transfer requests, each data transfer request comprising;

an identity of a volume of data that is to be transferred; and

a deadline that identifies a respective time, each data transfer request being a request to transfer data over a network that comprises a plurality of network infrastructure devices, each data transfer request to be completed prior to the respective time identified in the deadline;

computing a long-term schedule based upon the plurality of data transfer requests, the long-term schedule covers a first time window that includes a plurality of time units, the long-term schedule defines flow of traffic through the network for each time unit in the plurality of time units;

computing a short-term schedule based upon the long-term schedule, the short-term schedule covers a second time window that is shorter than the first time window and occurs prior to the first time window; and

causing respective routing tables to be transmitted to the plurality of network infrastructure devices based upon the short-term schedule, wherein the plurality of network infrastructure devices route data packets in the network based upon the routing tables.

14. The computing device of claim 13, wherein computing the long-term schedule comprises executing a mixed packing and covering algorithm.

15. The computing device of claim 13, wherein the long-term schedule and the short-term schedule are adjacent to one another in time.

16. The computing device of claim 13, wherein the plurality of time units have a uniform time duration.

17. The computing device of claim 13, the acts further comprising receiving a map of the network that identifies devices in the network and links between the devices, the long-term schedule computed based upon the map of the network.

18. The computing device of claim 13, the acts further comprising:

generating a price schedule based upon the long-term schedule; and

exposing the price schedule to requesters of data transfers.

19. The computing device of claim 13, the acts further comprising:

receiving a map of the network; and

constructing a network graph based upon the map of the network, the map of the network comprising a plurality of nodes that are respectively representative of the plurality of network infrastructure devices, the network graph comprises a plurality of instances of the map of the network for the plurality of future time units, respectively, and wherein the long-term schedule is computed based upon the network graph.

20. A computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a request to transfer data from a first device in a network to a second device in the network, the request comprising;

an identity of the second device;

an indication of a volume of the data to be transferred from the first device in the network to the second device in the network; and

a deadline that identifies a time, wherein the transfer of the data from the first device to the second 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 time window, the first time window includes a plurality of time units, wherein the long-term schedule defines, for each time unit in the plurality of time units, flow of traffic through the network, and further wherein the long-term schedule is computed to facilitate completion of the transfer of the data from the first device to the second device prior to the time identified in the deadline;

based upon the long-term schedule, computing a short-term schedule that covers a second window of time that includes fewer time units than the first window of time, the second window of time is prior to the first window of time, the short-term schedule computed to facilitate completion of the transfer of the volume of the data from the first device to the second 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 based upon the routing table.