Cost-aware networking over heterogeneous data channels

• US 7,751,317 B2
• Filed: 01/26/2006
• Issued: 07/06/2010
• Est. Priority Date: 01/26/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Murty, Rohan Narayan, Chandra, Ranveer, Thekkath, Chandramohan A.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US11/342,147
• Publication Number:
  US 20070171915A1
• Time in Patent Office: 1,622 Days
• Field of Search: 370/230, 370/252, 370/395.4, 709/226, 718/102
• US Class Current: 370/230
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/788 Autonomous allocation of resources
• CPC Class Codes: H04L 47/826 Involving periods of time

Abstract

Disclosed herein are scheduling techniques for transmitting time-critical data in a cost-aware manner over a network comprising a plurality of heterogeneous transmission interfaces. The scheduling problem is formulated as a linear programming problem with the deliver-by deadlines of the various data blocks as hard constraints and minimizing cost set as an objective (soft) constraint. The problem is simplified by assuming data blocks with the earliest deadlines should be scheduled first and the most aggressive interfaces should be used first. To formulate the linear programming problem, the time domain is divided into bins and various bin-level schedules are enumerated for switching the transmission of the data over various transmission interfaces. The linear programming techniques are applied to the various bin configurations and the least costly of the resulting transmission schedule is selected for submission to a switching layer.

Claims

1. A computer-implemented method of transmitting data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data to be transmitted configured as data blocks correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneous transmission interfaces to the network for transmitting the data blocks;

receiving transmission cost data correspondingly associated with the one or more heterogeneous interfaces of the network;

based on the delivery-by deadlines, the available bandwidth capacity and the transmission costs, applying linear programming techniques to determine a cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs; and

causing the data to be transmitted according to the cost-optimized transmission schedule, wherein the transmission schedule specifies an order of transmission of the data blocks as starting with a data block with an earliest deliver-by deadline and ending with a data block with a latest deadline, and wherein the transmission schedule further specifies an order of use of the one or more of the transmission interfaces available for data transmission as starting with a most aggressive transmission interface and ending with a least aggressive transmission interface.

2. A computer-implemented method of transmitting data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data to be transmitted configured as data blocks correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneous transmission interfaces to the network for transmitting the data blocks;

receiving transmission cost data correspondingly associated with the one or more heterogeneous interfaces of the network;

based on the delivery-by deadlines, the available bandwidth capacity and the transmission costs, applying linear programming techniques to determine a cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs; and

causing the data to be transmitted according to the cost-optimized transmission schedule, wherein the one or more transmission interfaces available for transmitting data comprises a unified transmission interface derived based on some combination of actual distinct transmission interfaces to the heterogeneous network.

3. The method of claim 2 wherein the bandwidth capacity of the unified transmission interface is a sum of the bandwidths of the distinct actual transmission interfaces.

4. A computer-implemented method of transmitting data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data to be transmitted configured as data blocks correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneous transmission interfaces to the network for transmitting the data blocks;

receiving transmission cost data correspondingly associated with the one or more heterogeneous interfaces of the network;

based on the delivery-by deadlines, the available bandwidth capacity and the transmission costs, applying linear programming techniques to determine a cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs; and

causing the data to be transmitted according to the cost-optimized transmission schedule, wherein applying linear programming techniques comprises applying Simplex linear programming algorithm to solve for the cost-optimized transmission schedule based on setting the deliver-by deadlines as hard constraints of the algorithm and minimizing transmission cost as an objective constraint.

5. The method of claim 4 further comprising

shortening one or more of the deliver-by deadlines prior to determining the cost-optimized transmission schedule.

6. The method of claim 4 further comprising

allocating a selected amount of bandwidth for a dedicated transmission and reducing the bandwidth capacity currently available for scheduling transmission over the one or more heterogeneous transmission interfaces by the allocated amount prior to determining the cost-optimized transmission schedule.

7. The method of claim 4 wherein the transmission schedule comprises units of time indicating a duration of time for which the one or more of the transmission interfaces are to be used for transmitting the data.

8. The method of claim 4 wherein the transmission schedule specifies an order of transmission of the data blocks as staffing with a data block with an earliest deliver-by deadline and ending with a data block with a latest deadline.

9. A computer-implemented method of transmitting data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data to be transmitted configured as data blocks correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneous transmission interfaces to the network for transmitting the data blocks;

receiving transmission cost data correspondingly associated with the one or more heterogeneous interfaces of the network;

pre-processing comprising by;

dividing a time domain over which the linear programming techniques are to be applied into a plurality of time bins;

deriving a plurality of bin configurations comprising bin-level schedules for switching of transmission between the one or more transmission interfaces; and

formulating the deliver-by deadlines as hard constraints for applying the linear programming techniques according to the bin configurations;

based on the delivery-by deadlines, the available bandwidth capacity and the transmission costs, applying linear programming techniques to determine a cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs; and

causing the data to be transmitted according to the cost-optimized transmission schedule.

10. The method of claim 9 wherein applying the linear programming technique to determine a cost-optimized transmission schedule comprises:

applying the linear programming techniques to each bin configuration for determining a bin-level cost-optimized transmission schedule; and

comparing the bin-level cost-optimized transmission schedule of the various bin configurations and selecting least costly one of the bin-level cost-optimized transmission schedules as the cost-optimized transmission schedule for transmitting the data over the heterogeneous network.

11. The method of claim 10 further comprising enumerating the bin configurations wherein the number of different bin configurations enumerated is based at least in part on the number of the transmission interfaces available for transmitting data.

12. The method of claim 11 wherein applying the linear programming techniques to each bin configuration comprises:

applying the linear programming until determining a first bin configuration that yields a transmission schedule that meets the deliver-by deadlines; and

selecting for further analysis a next bin configuration that is less aggressive than the first bin configuration to determine the cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs.

13. The method of claim 11 wherein applying the linear programming techniques to each bin configuration comprises applying the linear programming techniques starting with the most aggressive bin configuration and if the most aggressive bin configuration yields a transmission schedule that fails to meet any of the deliver-by deadlines then suspending applying the linear programming technique to less aggressive bin configurations.

14. The method of claim 13 further comprising extending the failed deliver-by deadlines and re-applying the linear programming techniques.

15. A computer-implemented method of transmitting data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data to be transmitted configured as data blocks correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneous transmission interfaces to the network for transmitting the data blocks;

receiving transmission cost data correspondingly associated with the one or more heterogeneous interfaces of the network;

based on the delivery-by deadlines, the available bandwidth capacity and the transmission costs, applying linear programming techniques to determine a cost-optimized transmission schedule that meets the deliver-by deadlines while minimizing transmission costs;

reapplying the linear programming techniques to determine the cost-optimized transmission schedule each time one or more parameters associated with transmission environment changes; and

causing the data to be transmitted according to the cost-optimized transmission schedule.

16. The method of claim 15 wherein the changes to the parameters comprises one or more of new data blocks to be delivered, new deliver-by deadlines, the changes to the data indicating bandwidth capacity and changes to the transmission cost data.

17. A computer system for scheduling transmission of data in a cost-aware manner over a set of one or more heterogeneous network interfaces of a network, the system comprising:

memory for storing computer executable instructions; and

at least one processor operable in conjunction with the instructions stored in the memory to determine a cost-optimized schedule for transmitting the data over the network by performing the following;

receiving data blocks to be transmitted over the network, the data blocks being correspondingly associated with deliver-by deadlines;

receiving data indicative of bandwidth available for use in the data transmission;

receiving data indicative of transmission costs correspondingly associated with the one or more of the network interfaces; and

applying linear programming techniques using the deliver-by deadlines as hard constraints and minimizing the transmission costs as objective constraints to determine the cost-optimized schedule.

18. The system of claim 17 wherein the linear programming techniques are applied with a schedule constraint requiring that the data blocks be scheduled for transmission in the order of their respective deliver-by deadlines with the data block with an earliest deliver-by deadline being scheduled first.

19. The system of claim 18 wherein the linear programming techniques are applied with a schedule constraint requiring that the network interfaces be scheduled for use in transmission in order of their respective speed with a most aggressive interface being scheduled first.

20. The system of claim 17 further operable for reapplying linear programming techniques to determine cost-optimized schedule upon determining a change in transmission environment.

21. The system of claim 17 further operable for receiving notice that at least a portion of the bandwidth available for use in the data transmission is reserved for data of high priority and upon receiving the notice being further operable for determining a new cost-optimized transmission schedule by assuming that the reserved portion of the bandwidth is not available for scheduling.

22. The system of claim 17 further operable for pre-processing prior to applying the linear programming techniques, the pre-processing comprising:

dividing a time domain over which the linear programming techniques are to be applied into a plurality of time bins;

deriving a plurality of bin configurations comprising bin-level schedules for switching of transmission between the available network interfaces; and

expressing the hard constraints for applying the linear programming techniques according to the bin configurations.

23. The system of claim 22 further operable for applying the linear programming techniques to each of the bin configurations to determine a cost-optimized schedule for that bin configuration and selecting least costly one of the cost-optimized schedules correspondingly associated with the bin configurations.

24. The system of claim 22 wherein the bins are derived based at least in part on the deliver-by deadlines and the bin configurations depend on the number of available network interfaces.