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

• US 6,850,965 B2
• Filed: 06/26/2001
• Issued: 02/01/2005
• Est. Priority Date: 11/17/1998
• Status: Expired due to Term

• Current Assignee: Musicqubed Innovations LLC (Ascend Innovation Management, LLC)
• Original Assignee: Burstcom Incorporated (Burst.com)
• Inventors: Allen, Arthur Douglas
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): NGUYEN, THU HA T
• Application Number:
  US09/893,364
• Publication Number:
  US 20020029274A1
• Time in Patent Office: 1,316 Days
• Field of Search: 709/203, 709/226, 709/233, 709/234, 370/232, 370/239, 370/389, 370/468
• US Class Current: 709/203
• 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 is disclosed. The method begins by prescribing a control variable which represents a target flow rate from the server device to each client device. Next, time-varying constraints on the flow rate of the content are determined. A cost function of the control variable for each client is determined. The cost function corresponds to a maximized value of the control variable. Finally, bandwidth is prescribed to each client based upon the value of the control variable maximized by the cost function. In this respect, the method achieves optimal allocation of bandwidth between the server and the respective clients.

Claims

1. 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 comprising the steps of:

a) prescribing a control variable which represents a target flow rate of content from the server device to each client device by;

i) forming a hyperplane of control variables that aggregate to a maximum allowed aggregate flow rate;

ii) computing a first vector of minimum allowed client flow rates;

iii) computing a second vector of maximum allowed client flow rates;

iv) determining a multi-dimensional shape of which an interior diagonal spans the first and second vectors; and

v) finding a solution of control variables at a point of intersection between the diagonal and the hyperplane;

b) determining time-varying constraints on the target flow rate of the content;

c) 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

d) prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function.

2. The method of claim 1 wherein step (d) comprises performing periodic computations to update the value of the control variable such that the bandwidth can be continuously allocated to each client.

3. The method of claim 2 wherein a new client is accepted by:

i) determining an admission capacity of the bandwidth;

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

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

4. The method of claim 3 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.

5. The method of claim 4 wherein the minimum allowed value of the control variable is initialized to an average consumption rate.

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

7. The method of claim 4 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:

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

ii) determining at each time in the sequence of future step changes a 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;

iii) 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;

iv) 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.

8. The method according to claim 7 wherein the method of accepting a new client further comprises:

i) partitioning available bandwidth into partitions representing a prescribed service charge;

ii) 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;

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

iv) 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

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

9. The method of claim 8 wherein the method of accepting a new client further comprises:

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

ii) determining for each time in the sequence of future times, a future worst-case value for a 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

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

10. The method of claim 3 wherein step (b) comprises determining time-varying constraints wherein:

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

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

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

iv) a flow rate to the client stops when the content is exhausted; and

v) a flow rate from the sever will never be less than the client'"'"'s minimum allowed flow rate which may vary over time and may be zero.

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

i) a client flow rate ceiling;

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

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

12. The method of claim 11 wherein:

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

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

iii) the client buffer will never underflow until the content is fully consumed at the average consumption rate.

13. The method of claim 12 wherein the minimum client flow rate is a product of a constant content flow rate from the client to the server that causes a 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.

14. The method of claim 13 wherein the minimum client flow rate is initialized to the average consumption rate.

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

16. The method of claim 13 further comprising the step of calculating the minimum client flow rate periodically.

17. 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.

18. The method of claim 17 wherein:

step (a) comprises;

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

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

iii) 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

step (d) comprises;

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

ii) 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.

19. The method of claim 1 wherein step (v) comprises finding a solution of control variables at the second vector if there is no point of intersection between the diagonal and the hyperplane.

20. The method of claim 1 wherein step (a) comprises:

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

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

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

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

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

vi) 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.

21. The method of claim 1 wherein:

step (a) comprises;

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

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

iii) 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

step (d) comprises;

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

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

22. 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.

23. The method of claim 1 wherein the maximized value of the control variable can be determined by:

i) determining a maximum and minimum flow rate for each client;

ii) determining a range between the maximum and minimum flow rates in order to find a flow rate range;

iii) determining available bandwidth by finding the difference between an aggregate flow capacity and a sum of the minimum flow rate;

iv) determining a flow variable by dividing the unused bandwidth by the flow rate range;

v) prescribing the control variable to be the minimum flow rate added to the flow rate range if a flow variable is less than one or prescribing the control variable to be the minimum flow rate added to the flow rate range corrected by a flow variable if the flow variable is greater than one such that the control variable is easily calculated for each client.

24. The method of claim 1 wherein at least one session is a session bundle and:

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

2) the maximum flow constraint is the least of

     1) the sum of the maximum individual flow rate constraints of each session and

     2) the flow capacity of the channel shared among the bundled sessions; and

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

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

26. A system for allocating bandwidth between a server device and at least one client device, the system comprising:

a call acceptance module operative to receive an incoming request for service;

a flow regulator configured to deliver content at a modulated target flow rate, the content being delivered between the server device and a respective client device when a call is accepted by the call acceptance module; and

a flow optimizer configured to modulate the target flow rate of the flow regulator in order to optimize an aggregate flow of content by performing the following procedure;

a) prescribing a control variable which represents a target flow rate of content from the server device to each client device by

i) forming a hyperplane of control variables that aggregate to a maximum allowed aggregate flow rate;

ii) computing a first vector of minimum allowed client flow rates;

iii) computing a second vector of maximum allowed client flow rates;

iv) determining a multi-dimensional shape of which an interior diagonal spans the first and second vectors; and

v) finding a solution of control variables at a point of intersection between the diagonal and the hyperplane;

b) determining time-varying constraints on the target flow rate of the content;

c) 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

d) prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function.

27. The system of claim 26 wherein the flow optimizer is configured to modulate the flow rate of the flow regulator in order to optimize charges for the content.

28. The system of claim 26 wherein the flow optimizer is configured to determine a control variable which corresponds to an optimized flow rate.

29. The system of claim 28 wherein the flow optimizer is configured to generate a cost function of the control variable that corresponds to a maximized value of the control variable.

30. The system of claim 26 wherein the flow regulator is configured to deliver the modulated flow rate of content in response to the control variable.

31. The system of claim 30 wherein the call acceptance module is configured to accept a call based upon a value of the control variable.

32. The system of claim 26 wherein the flow optimizer is configured to determine a maximized value of the control variable by:

i) determining a maximum and minimum flow rate for each client;

ii) determining a range between the maximum and minimum flow rates in order to find a flow rate range;

iii) determining unused bandwidth by finding the difference between an aggregate flow capacity and a sum of the minimum flow rate;

iv) determining a flow variable by dividing the unused bandwidth by the flow rate range;

v) prescribing the control variable to be the minimum flow rate added to the flow rate range if the flow variable is less than one or prescribing the control variable to be the minimum flow rate added to the flow rate range corrected by the flow variable if the flow favorable is greater than one such that the control variable is easily calculated for each client.

33. 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 comprising the steps of:

a) prescribing a control variable which represents a target flow rate from the server to each client device based upon the amount of buffer of the client by;

i) forming a hyperplane of control variables that aggregate to a maximum allowed aggregate flow rate;

ii) computing a first vector of minimum allowed client flow rates;

iii) computing a second vector of maximum allowed client flow rates;

iv) determining a multi-dimensional shape of which an interior diagonal spans the first and second vectors; and

v) finding a solution of control variables at a point of intersection between the diagonal and the hyperplane;

b) determining time-varying constraints on the flow rate of the content;

c) determining a cost function of the control variables for all clients in response to a size of the client'"'"'s buffer wherein the cost function represents an aggregate flow rate and is a sum of all flow rates for all clients; and

d) prescribing bandwidth to all clients based upon a value of the control variables that maximize the cost function.