Method and system for a real-time bandwidth allocation scheduler for media delivery

• US 6,947,388 B1
• Filed: 10/20/1999
• Issued: 09/20/2005
• Est. Priority Date: 10/20/1999
• Status: Expired due to Term

• Current Assignee: Hulu LLC (The Walt Disney Company)
• Original Assignee: International Business Machines Corporation
• Inventors: Wagner, Marcus
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/421,806
• Time in Patent Office: 2,162 Days
• Field of Search: 370/252, 370/465, 370/468, 370/310.1, 370/230, 370/227, 370232-235, 370/238, 370/260, 370/338, 370/345, 370/346, 370/347, 370/352, 370/353, 370/348, 370/395.1, 370/395.21, 370/395.41, 37039542-39543, 370/473, 370/498
• US Class Current: 370/252
• CPC Class Codes: H04B 7/18595 Arrangements for adapting broadband applications to satellite systems
• CPC Class Codes: H04H 20/74 of satellite networks
• CPC Class Codes: H04J 3/1682 Allocation of channels according to the instantaneous demands of the users, e.g. concentrated multiplexers, statistical multiplexers
• CPC Class Codes: H04N 21/2385 Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16

Abstract

The present invention provides a method and system for providing a bandwidth allocation scheduler for media delivery. The present invention includes determining an available bandwidth for file transmission for a time interval, and allocating at least a portion of the available bandwidth to at least one file transmission task, wherein a different amount of the available bandwidth may be allocated to each of the at least one file transmission tasks. The bandwidth allocation scheduler in accordance with the present invention comprises a set of program segments that provides fast, deterministic real-time scheduling for the allocation of bandwidth for file transmissions. It allows the bandwidth allocated to a delivery to vary according to the amount of bandwidth available. A different amount of bandwidth may be allocated to each individual file transmission task. Higher priority transmissions may be allocated bandwidth before allocation to lower priority file transmissions. The maximum bit rate of the slowest addressed receiver may be considered in allocating the bandwidth. Moreover, the customer can choose between different allocation strategies. Thus, the bandwidth allocation scheduler in accordance with the present invention reduces waste in bandwidth in media delivery, which in turn reduces costs for a customer.

Claims

1. A method for media delivery in a network, comprising the steps of:

(a) determining an available bandwidth for file transmission for a time interval, comprising the steps of;

(a1) updating a total available bandwidth for the time interval, comprising the steps of;

(a1i) reading from a plurality of database tables a plurality of live-video stream (LVS) jobs to begin during the time interval,

(a1ii) allocating bandwidth to the plurality of LVS jobs not yet allocated bandwidth, and

(a1iii) recording the allocated bandwidth to the plurality of LVS jobs in the plurality of database tables, and

(a2) checking for the available bandwidth for file transmission for the time interval, comprising the steps of;

(a2i) updating a global step function (GSF),

(a2ii) determining if enough bandwidth is available for file transmissions,

(a2iii) sending an indication if there is not enough bandwidth available for file transmission, and

(a2iv) finding a bandwidth strip which begins at a current time, fits under the GSF, has at least a minimum amount of bandwidth that must be allocated to a file transmission task, and does not extend, in the X/time-direction, beyond a latest delivery time (LDT) of the at least one transmission task; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth.

2. The method of claim 1, wherein the finding step (a2iv) comprises the step of:

(a2ivA) finding the bandwidth strip that extends in an X/time-direction from a current time to no more than a maximum transmission duration, and in a Y/bandwidth-direction from zero to no more than a value of the GSF at any X/time value spanned by the bandwidth strip;

(a2ivB) determining if an area of the bandwidth strip is no smaller than a predetermined area;

(a2ivC) indicating not enough bandwidth for file transmission if the area of the largest found bandwidth strip is smaller than the predetermined area, or is not within a plurality of pre-determined boundary conditions; and

(a2ivD) returning a size limitation for the at least one file transmission task if the area of the bandwidth strip is smaller than the predetermined area.

3. A method for media delivery in a network, comprising the steps of:

(a) determining an available bandwidth for file transmission for a time interval; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth, comprising the steps of;

(b1) setting an upper bound on an amount of bandwidth to a smaller of the available bandwidth and a maximum bit rate of a plurality of receivers,

(b2) gathering data for the at least one file transmission task, the gathered data including a size of the at least one file transmission task,

(b3) determining an allocation strategy selected by a customer,

(b4) computing an overhead for the at least one file transmission task, wherein the computing step (b4) comprises the steps of;

(b4i) computing a total transmission overhead for the at least one file transmission task, and

(b4ii) converting the task size and the total transmission overhead into an area,

(b5) allocating the portion of the available bandwidth based on the upper bound, the size of the at least one transmission task, the computed overhead, and the allocation strategy selected by the customer, and

(b6) recording the available bandwidth remaining after the allocation in a plurality of database tables.

4. A method for media delivery in a network, comprising the steps of:

(a) determining an available bandwidth for file transmission for a time interval; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth, comprising the steps of;

(b1) setting an upper bound on an amount of bandwidth to a smaller of the available bandwidth and a maximum bit rate of a plurality of receivers,

(b2) gathering data for the at least one file transmission task, the gathered data including a size of the at least one file transmission task,

(b3) determining an allocation strategy selected by a customer,

(b4) computing an overhead for the at least one file transmission task,

(b5) allocating the portion of the available bandwidth based on the upper bound, the size of the at least one transmission task, the computed overhead, and the allocation strategy selected by the customer, wherein the allocating step (b5) comprises the steps of;

(b54i) determining if the at least one file transmission task can be completed before a deadline,

(b5ii) returning an error if the at least one file transmission task can not be completed before the deadline,

(b5iii) allocating a lowest possible bandwidth strip to meet the deadline to the at least one file transmission task if the bandwidth allocation strategy is Minimum Possible Bandwidth,

(b5iv) allocating a highest possible bandwidth strip to meet the deadline if the bandwidth allocation strategy is Maximum Possible Bandwidth,

(b5v) determining if the allocating step (b5iv) completed successfully,

(b5vi) returning an error if the allocating step (b5iv) did not complete successfully, and

(b5vii) setting the allocated bandwidth and duration of allocation in the task data if the allocating step (b5iv) completed successfully,

(b6) recording the available bandwidth remaining after the allocation in a plurality of database tables.

5. A method for media delivery in a network, comprising the steps of:

(a) determining an available bandwidth for completion of a file transmission for a time interval, wherein the time interval is a current time plus a maximum duration for a completion of at least one file transmission task;

(b) allocating at least a portion of the available bandwidth to complete the at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth; and

(c) freeing any allocated available bandwidth unused by a complete transmission of the at least one file transmission task, comprising;

(c1) updating a global step function (GSF), wherein the GSF represents a total maximum bandwidth available in the network in the time interval for completion of the file transmission;

(c2) constructing a payback strip from the portion of the available bandwidth allocated to the at least one file transmission task;

(c3) adding the payback strip to the GSF; and

(c4) recording an available bandwidth remaining after the adding step (c3) in a plurality of database tables.

6. A method for media delivery in a network, comprising the steps of:

(a) determining an available bandwidth for file transmission for a time interval;

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth; and

(c) freeing any allocated available bandwidth unused by a transmission of the at least one file transmission task, comprising the steps of;

(c1) updating a global step function (GSF),

(c2) constructing a payback strip from the portion of the available bandwidth allocated to the at least one file transmission task, comprising the steps of;

(c2i) finding an expiration time corresponding to the at least one file transmission task in the plurality of database tables, and

(c2ii) constructing the payback strip that extends in an X/time-direction until the expiration time and in a Y/bandwidth direction from zero to the portion of the available bandwidth allocated to the at least one file transmission task,

(c3) adding the payback strip to the GSF, and

(c4) recording an available bandwidth remaining after the adding step (c3) in a plurality of database tables.

13. The method of claim 6, wherein the at least one file transmission task is scheduled back-to-back when duration of allocations are known when the allocations are made.

14. The method of claim 6, wherein the allocation of the available bandwidth to the at least one file transmission task is varied as a polynomial in time.

7. A computer readable medium with program instructions for media delivery in a network, the instructions for:

(a) determining an available bandwidth for file transmission for a time interval, comprising the instructions for;

(a1) updating a total available bandwidth for the time interval, comprising the instructions for;

(a1i) reading from a plurality of database tables a plurality of live-video stream (LVS) jobs to begin during the time interval,

(a1ii) allocating bandwidth to the plurality of LVS jobs not yet allocated bandwidth, and

(a1iii) recording the allocated bandwidth to the plurality of LVS jobs in the plurality of database tables, and

(a2) checking for the available bandwidth for file transmission for the time interval, comprising the steps of;

(a2i) updating a global step function (GSF),

(a2ii) determining if enough bandwidth is available for file transmissions,

(a2iii) sending an indication if there is not enough bandwidth available for file transmission, and

(a2iv) finding a bandwidth strip which begins at a current time, fits under the GSF, has at least a minimum amount of bandwidth that must be allocated to a file transmission task, and does not extend, in the X/time-direction, beyond a LDT of the at least one transmission task; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth.

8. The medium of claim 7, wherein the finding instruction (a2iv) comprises the instructions for:

(a2ivA) finding the bandwidth strip that extends in an X/time-direction from a current time to no more than a maximum transmission duration, and in a Y/bandwidth-direction from zero to no more than a value of the GSF at any X/time value spanned by the bandwidth strip;

(a2ivB) determining if an area of the bandwidth strip is no smaller than a predetermined area;

(a2ivC) indicating not enough bandwidth for file transmission if the area of the largest found bandwidth strip is smaller than the predetermined area, or is not within a plurality of pre-determined boundary conditions; and

(a2ivD) returning a size limitation for the at least one file transmission task if the area of the bandwidth strip is smaller than the predetermined area.

9. A computer readable medium with program instructions for media delivery in a network, the instructions for:

(a) determining an available bandwidth for file transmission for a time interval; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth, comprising the instructions for;

(b1) setting an upper bound on an amount of bandwidth to a smaller of the available bandwidth and a maximum bit rate of a plurality of receivers,

(b2) gathering data for the at least one file transmission task, the gathered data including a size of the at least one file transmission task,

(b3) determining an allocation strategy selected by a customer,

(b4) computing an overhead for the at least one file transmission task, wherein the computing instruction (b4) comprises the steps of;

(b4i) computing a total transmission overhead for the at least one file transmission task, and

(b4ii) converting the task size and the total transmission overhead into an area,

(b5) allocating the portion of the available bandwidth based on the upper bound, the size of the at least one transmission task, the computed overhead, and the allocation strategy selected by the customer, and

(b6) recording the available bandwidth remaining after the allocation in a plurality of database tables.

10. A computer readable medium with program instructions for media delivery in a network, the instructions for:

(a) determining an available bandwidth for file transmission for a time interval; and

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth, comprising the instructions for;

(b1) setting an upper bound on an amount of bandwidth to a smaller of the available bandwidth and a maximum bit rate of a plurality of receivers,

(b2) gathering data for the at least one file transmission task, the gathered data including a size of the at least one file transmission task,

(b3) determining an allocation strategy selected by a customer,

(b4) computing an overhead for the at least one file transmission task,

(b5) allocating the portion of the available bandwidth based on the upper bound, the size of the at least one transmission task, the computed overhead, and the allocation strategy selected by the customer, wherein the allocating instruction (b5) comprises the instructions for;

(b54i) determining if the at least one file transmission task can be completed before a deadline,

(b5ii) returning an error if the at least one file transmission task can not be completed before the deadline,

(b5iii) allocating a lowest possible bandwidth strip to meet the deadline to the at least one file transmission task if the bandwidth allocation strategy is Minimum Possible Bandwidth,

(b5iv) allocating a highest possible bandwidth strip to meet the deadline if the bandwidth allocation strategy is Maximum Possible Bandwidth,

(b5v) determining if the allocating step (b5iv) completed successfully,

(b5vi) returning an error if the allocating step (b5iv) did not complete successfully, and

(b5vii) setting the allocated bandwidth and duration of allocation in the task data if the allocating step (b5iv) completed successfully, and

(b6) recording the available bandwidth remaining after the allocation in a plurality of database tables.

11. A computer readable medium with program instructions for media delivery in a network, the instructions for:

(a) determining an available bandwidth for completion of a file transmission for a time interval, wherein the time interval is a current time plus a maximum duration for a completion of at least one file transmission task;

(b) allocating at least a portion of the available bandwidth to complete the at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth;

(c) freeing any allocated available bandwidth unused by a complete transmission of the at least one file transmission task, comprising;

(c1) updating a global step function (GSF), wherein the GSF represents a total maximum bandwidth available in the network in the time interval for completion of the file transmission;

(c2) constructing a payback strip from the portion of the available bandwidth allocated to the at least one file transmission task;

(c3) adding the payback strip to the GSF; and

(c4) recording an available bandwidth remaining after the adding step (c3) in a plurality of database tables.

12. A computer readable medium with program instructions for media delivery in a network, the instructions for:

(a) determining an available bandwidth for file transmission for a time interval;

(b) allocating at least a portion of the available bandwidth to at least one file transmission task, wherein each of the at least one file transmission task may be allocated a different amount of the available bandwidth; and

(c) freeing any allocated available bandwidth unused by a transmission of the at least one file transmission task, comprising the instructions for;

(c1) updating a global step function (GSF),

(c2) constructing a payback strip from the portion of the available bandwidth allocated to the at least one file transmission task, comprising the instructions for;

(c2i) finding an expiration time corresponding to the at least one file transmission task in the plurality of database tables, and

(c2ii) constructing the payback strip that extends in an X/time-direction until the expiration time and in a Y/bandwidth direction from zero to the portion of the available bandwidth allocated to the at least one file transmission task,

(c3) adding the payback strip to the GSF, and

(c4) recording an available bandwidth remaining after the adding step (c3) in a plurality of database tables.

15. The medium of claim 12, wherein the at least one file transmission task is scheduled back-to-back when duration of allocations are known when the allocations are made.

16. The medium of claim 12, wherein the allocation of the available bandwidth to the at least one file transmission task is varied as a polynomial in time.