Cost-aware networking over heterogeneous data channels

• US 20070171915A1
• Filed: 01/26/2006
• Published: 07/26/2007
• Est. Priority Date: 01/26/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Chandra, Ranveer, Thekkath, Chandramohan, Murty, Rohan
• Granted Patent: US 7,751,317 B2
• Time in Patent Office: Days
• US Class Current: 370/395.210
• 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 heterogeneus transmission interfaces comprising 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.

2. The method of claim 1 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.

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

4. The method of claim 3 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 the most aggressive transmission interface and ending with the least aggressive transmission interface.

5. The method of claim 1 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 comprising the heterogeneous network.

6. The method of claim 5 wherein the bandwidth capacity of the unified transmisson interface is a sum of the bandwidths of the distinct actual transmission interfaces.

7. The method of claim 1 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 the objective constraint.

8. The method of claim 1 further comprising a pre-procesing step, 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 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.

9. The method of claim 8 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.

10. The method of claim 9 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.

11. The method of claim 10 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.

12. The method of claim 10 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 yeilds a transmission scehdule that fails to meet any of the deliver-by deadlines then suspending applying the linear programming technique to less aggressive bin configurations.

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

14. The method of claim 1 further comprising reapplying the linear programming techniques to determine the cost-optimized transmission schedule each time one or more parameters associated with transmission environment changes.

15. The method of claim 14 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.

16. The method of claim 1 further comprising shortening one or more of the deliver-by deadlines prior to determining the cost-optimized transmission schedule.

17. The method of claim 1 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 heterogeneus transmission interfaces by the allocated amount prior to determining the cost-optimized transmission schedule.

18. A computer system for scheduling transmission of data in a cost-aware manner over one or more network interfaces of a network having a set of heterogeous network interfaces, 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 transmision 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.

19. The system of claim 18 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 the earliest deliver-by deadline being scheduled first.

20. The system of claim 19 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 the most aggressive interface being scheduled first.

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

22. The system of claim 18 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 bandwith is not available for scheduling.

23. The system of claim 18 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.

24. The system of claim 23 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.

25. The system of claim 23 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.

26. At least one computer readable medium useful in conjunction with a computer comprising at least one processor and a memory, the computer readable medium having stored thereon computer executable instructions for performing a method of scheduling transmision of data over a heterogeneous network in a cost-aware manner, the method comprising:

receiving data blocks for transmission correspondingly associated with data indicative of deliver-by deadlines;

receiving data indicating bandwidth capacity currently available over one or more heterogeneus transmission interfaces of the network;

receiving transmission costs data corresponding to the transmission interfaces of the network; and

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.