Method for connection acceptance control and rapid determination of optimal multi-media content delivery over networks

• US 7,346,688 B2
• Filed: 06/02/2006
• Issued: 03/18/2008
• Est. Priority Date: 11/17/1998
• Status: Expired due to Fees

• Current Assignee: Musicqubed Innovations LLC (Ascend Innovation Management, LLC)
• Original Assignee: Burst.com
• Inventors: Allen, Arthur
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US11/445,991
• Publication Number:
  US 20060224768A1
• Time in Patent Office: 655 Days
• Field of Search: 709223-224, 709/203, 709/219, 709/226, 709/229, 709231-234, 370/468, 370/254, 370/232, 370236-237, 370/389, 370/397, 370/399, 370/463
• US Class Current: 709/226
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/741 Holding a request until resources become available
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/765 triggered by the end-points
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/752 adapting media to network capabilities
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/62 : Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04N 21/23805 : Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/2381 : Adapting the multiplex stream to a specific network, e.g. an Internet Protocol [IP] network transmission of MPEG streams over ATM H04L12/5601
• 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
• CPC Class Codes: H04N 21/2396 : characterized by admission policies admission control, resource allocation in open networks H04L12/5692; arrangements for network security using user profiles for access control H04L63/102; access security in wireless networks H04W12/08
• CPC Class Codes: H04N 21/2401 : Monitoring of the client buffer
• CPC Class Codes: H04N 21/2402 : Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/26216 : involving the channel capacity, e.g. network bandwidth admission control, resource allocation in open networks H04L12/5692; flow control in packet networks H04L47/10; establishing a schedule or organising the servicing of application requests taking into account QoS H04L67/61
• CPC Class Codes: H04N 21/2662 : Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/47202 : for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6377 : directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/643 : Communication protocols network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP], H04L65/65
• CPC Class Codes: H04N 21/658 : Transmission by the client directed to the server

Abstract

A method of bandwidth allocation for delivery of stored digital content from at least one server device to at least one client device by way of a network. The method includes the steps of: describing a control variable which represents a target flow rate of content from the server device to each client device; determining time-varying constraints on the target flow rate of the content; determining a cost function of the control variables for all clients, wherein the cost function represents an aggregate flow rate and is a sum of all flow rates for all clients; and prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function comprising performing periodic computations to update the value of the control variable such that the bandwidth can be continuously allocated to each client.

Claims

1. A method of bandwidth allocation for stored digital content, the method comprising the steps of:

storing digital content on at least one server device, the digital content having a payload and a play duration; and

delivering the digital content from the at least one server device to at least one client device upon demand of the at least one client device by way of a network having a defined bandwidth, and wherein the digital content is available for playback upon client request, the delivery of digital content from the at least one server device to the at least one client device comprising;

describing a control variable which represents a target flow rate of digital content from the server device to each client device, and wherein the target flow rate ensures that all required digital content will be available to each client when needed;

determining time-varying constraints on the target flow rate of the digital content, and wherein the time-varying constraints for the digital content for each client device further comprises evaluating;

payload of the digital content not yet delivered; and

remaining play duration of the digital content;

determining a cost function of the control variables for all clients, wherein the cost function represents an aggregate flow rate and is a sum of all flow rates for all clients; and

prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function comprising performing periodic computations to update the value of the control variable such that the bandwidth can be continuously allocated to each client;

ceasing delivery of digital content to the at least one client device when the payload of the digital content not yet delivered is equal to zero; and

accepting a new client by;

determining an admission capacity of the bandwidth;

admitting a prospective client if the clients minimum allowed value of the control variable is less than the admission capacity; and

wherein a client admitted for service is guaranteed to have sufficient content flow over the entire session.

2. The method of claim 1, wherein the admission capacity equals a server swing capacity reduced by a predetermined safety margin which may be zero, the swing capacity equaling a difference between a server flow capacity and a sum of a minimum allowed flow rate for all clients.

3. The method of claim 2, wherein the minimum allowed value of the control variable is initialized to an average consumption rate, and wherein the average consumption rate equal to the total payload divided by the total play duration.

4. The method of claim 2, wherein the minimum allowed value of the control variable is initialized to the average consumption rate multiplied by a factor greater than one.

5. The method of claim 2, wherein the server flow capacity varies in a step-wise function over time according to a predetermined schedule and the method of accepting a new client further comprises:

determining a sequence of future step changes of server flow capacity;

determining at each time in the sequence of future step changes the value for a future worst swing case capacity, the worst case swing capacity being obtained from the server flow capacity at the time by subtracting an extrapolated present minimum allowed flow rate for all active clients that are potentially active in the future;

admitting a prospective client if a minimum allowed value of the control variable is less than a capacity obtained from the sequence and a present capacity; and

whereby a new client can be admitted without compromising the service to existing clients in the presence of previously scheduled server flow capacity changes and all clients accumulate content in their buffers to the extent of their respective buffer capacity.

6. The method according to claim 5, wherein the method of accepting a new client further comprises:

partitioning the available bandwidth into partitions representing a prescribed service charge;

determining a maximum-minimum capacity for a service charge to be the maximum allowed sum of all minimum allowed flow rates for all clients incurring an equal or lesser service charge, the maximum-minimum capacity equaling the sum of bandwidth allocations for all service charges less than or equal to the service charge;

determining a service-charge-specific swing capacity for a given service charge as the difference between the maximum-minimum capacity for the service charge and the sum of all minimum allowed flow rates for all clients incurring the service charge or a lesser service charge;

determining the server swing capacity to be the server flow capacity minus a margin and minus the sum of the minimum allowed flow rate for all clients; and

determining the service-charge-specific capacity to be the least of the server swing capacity and the charge specific swing capacity.

7. The method of claim 6, wherein the method of accepting a new client further comprises:

determining the sequence of future times of step changes to server flow capacity over a proposed consumption period;

determining for each time in the sequence of future times, the future worst-case value for the service-charge-specific capacity, the worst case value being obtained by using the extrapolated present minimum allowed flow rate of all presently active clients that are potentially active at the time in the future; and

admitting a client incurring a given service charge if the minimum flow rate of the client is less than the capacity obtained from the sequence and the present service-charge-specific capacity.

8. The method of claim 3, wherein the step of determining time-varying constraints further comprises determining time-varying constraints wherein:

an aggregate flow rate for all clients does not exceed a predetermined server flow capacity;

a flow rate from the server to the client does not exceed a maximum allowed flow rate for the client;

a flow rate to the client will never cause a buffer of the client to overflow; and

a flow rate from the server will never be less than a minimum allowed flow rate, which may vary over time and may be zero.

9. The method of claim 8, wherein the maximum allowed flow rate to the client is given by the minimum of one selected from the following:

a client flow rate ceiling;

a flow rate required to fill the client buffer before the next periodic computation; and

a flow rate required to complete the delivery of the content before the next periodic computation.

10. The method of claim 8, wherein, for one or more clients, the client flow rate ceiling is set equal to the minimum allowed flow rate, causing a bounding segment, which constrains the flow target of any affected client, to shrink to a single point.

11. The method of claim 8, wherein the minimum allowed client flow rate descends in a series of one or more steps, starting from an initial flow rate that exceeds the average consumption rate.

12. The method of claim 8, wherein for one or more clients, flow rate ceiling is set equal to the minimum allowed client flow rate, causing a bounding segment, which constrains the flow target of any affected client, to shrink to a single point.

13. The method of claim 8, wherein target flow rates are recomputed whenever a new client is admitted.

14. The method of claim 8, wherein the target flow rates are recomputed whenever a minimum allowed client flow rate undergoes a step change.

15. The method of claim 8, wherein the minimum allowed client flow rate may step up over time to the extent of available admission capacity, such that no existing sessions are compromised.

16. The method of claim 9, wherein:

the minimum allowed client flow rate cannot increase over time, but may decrease such that the initial value of the control rate is no less than the average consumption rate;

the control variable for the client is always greater than or equal to the current minimum allowed client flow rate; and

the client buffer will never underflow.

17. The method of claim 9, wherein the minimum client flow rate is initialized to the average consumption rate.

18. The method of claim 9, wherein the minimum client flow rate is initialized to the average consumption rate multiplied by a factor greater than one.

19. The method of claim 9, further comprising the step of calculating the minimum client flow rate periodically.

20. The method of claim 9, further comprising the step of calculating the maximum client flow rate periodically.

21. The method of claim 20, wherein the step of describing the control variable comprises:

computing the sum of the minimum allowed flow rates to all active clients;

computing the sum of the flow rate ranges for all active clients;

computing the difference between the maximum allowed aggregate flow rate and the sum of the minimum;

computing a factor as the ratio of the difference over the sum of the ranges;

if the factor exceeds 1, the control variable is set to the maximum allowed client flow rate; and

if the factor is less than 1, computing the control variable by multiplying the client range by the factor and then adding the result to the minimum allowed client flow rate.

22. The method of claim 20, wherein:

the step of describing the control variable comprises;

determining the maximum allowed flow rate and minimum allowed flow rate for each client;

determining the flow rate range for each client as the difference between the maximum flow rate and the minimum flow rate; and

initializing the control variable for each client as said minimum allowed flow rate and summing the flow rate into a total server flow rate; and

the step of describing the control variable comprises;

computing remaining server bandwidth as the difference between the maximum server flow capacity and the total server flow rate; and

allocating remaining server bandwidth to remaining clients to the extent of their respective ranges.

23. The method of claim 20, wherein at least one session is a session bundle and:

the minimum flow constraint is computed as the sum of the minimum flow rate constraints for all bundled sessions;

the maximum flow constraint is the least of the sum of the maximum individual flow rate constraints of each session and the flow capacity of the channel shared among the bundled sessions; and

the target flow rate is computed for the session is apportioned among the bundled constituent sessions.

24. The method of claim 21, wherein the step of allocating remaining server bandwidth further comprises the clients receiving the bandwidth equally to the extent of their respective ranges.

25. The method of claim 23 wherein the bundled session is an advertisement.

26. The method of claim 16, wherein the minimum client flow rate is the product of the constant content flow rate from the client to the server that causes the last piece of content to be delivered at the last possible moment as the client buffer is being drained at the average consumption rate, with a factor greater or equal to one.

27. The method of claim 1 wherein the cost function represents an aggregate flow rate and is the sum of the flow rates for all clients.

28. The method of claim 1 wherein the cost function represents a service charge and is the sum of the client flow rates multiplied by the client'"'"'s cost of service.

29. The method of claim 28, wherein:

the step of describing the control variable comprises;

determining a maximum allowed flow rate and a minimum allowed flow rate for each client;

determining a flow rate range for each client as the difference between the maximum allowed flow rate and the minimum allowed flow rate; and

initializing a current flow rate for each client as the minimum allowed flow rate and summing the flow rate into the total server flow rate; and

the step of prescribing bandwidth comprises;

computing remaining server bandwidth as the difference between the maximum server flow capacity and the total server flow rate; and

allocating remaining server bandwidth to remaining clients wherein all clients with a given cost of service receive bandwidth equally to the extent of their respective ranges, and no client with a given cost of service being allocated bandwidth unless all clients with a higher cost of service have received their maximum possible allocation of bandwidth.

30. The method of claim 1, wherein the steps of prescribing a control variable, and determining a cost function of the control variables for all clients are performed based upon an amount of buffer of the client.

31. A method of bandwidth allocation for delivery of digital content from at least one server device to at least one client device by way of a network, the method comprising the steps of:

storing content from a live event into the at least one server device;

injecting a delay into the delivery of the digital content from the at least one server device to the at least one client device; and

delivering digital content from the at least one server device upon demand to the at least one client device such that the digital content is available for playback upon client request, and wherein bandwidth is allocated to the at least one client as follows;

describing a control variable which represents a target flow rate of content from the server device to each client device, and wherein the target flow rate ensures that all required content will be available to each client when needed;

determining time-varying constraints on the target flow rate of the content, and wherein the time-varying constraints for the digital content for each client device further comprises evaluating;

payload of the digital content captured from the live event and not yet delivered; and

play duration of the digital content captured from the live event and not vet delivered;

determining a cost function of the control variables for all clients, wherein the cost function represents an aggregate flow rate and is a sum of all flow rates for all clients; and

prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function comprising performing periodic computations to update the value of the control variable such that the bandwidth can be continuously allocated to each client.

32. The method of claim 31, wherein a new client is accepted by:

determining an admission capacity of the bandwidth;

admitting a prospective client if the clients minimum allowed value of the control variable is less than the admission capacity; and

wherein a client admitted for service is guaranteed to have sufficient content flow over the entire session.

33. The method of claim 31, wherein upon conclusion of the live event, storing the content from the live event for the balance of the admission window.

34. The method of claim 32, further comprising permitting new clients to view the live event starting from any point between the present and the event start time.