Granted Patent B2

US 7,383,338 · App. 11/445,568 · Granted Jun 3, 2008

Abstract

Claims (66)

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

a server device operative to store and deliver content having a fixed duration;

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:

describing a control variable which represents a target flow rate of content from the server device to each client device, the target flow rate equal to or greater than a minimum flow rate, wherein the minimum flow rate is a non-increasing function of time obtained by dividing the content not yet delivered by remaining playtime, which 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;

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;

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; and

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.

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

3. The system of claim 2 , wherein the flow regulator is configured to deliver the modulated flow rate of content in response to a control variable.

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

5. The system of claim 4 , 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.

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

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

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

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

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

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

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.

8. The system of claim 7 , wherein the call acceptance module is configured to accept a call based upon an initial value of the control variable.

9. The system of claim 1 , wherein the system apportions a given total flow rate among a plurality of sessions for clients by:

computing a sum of minimum flow rate constraints for each session;

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

computing a difference between the given total flow rate and a sum of the flow rate minima;

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

if the factor exceeds 1, setting the flow rate to the maximum flow rate; and

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

10. The system of claim 9 , wherein the clients are distinguished by their cost of service and bandwidth is apportioned to clients iteratively, the amount apportioned to each client in a cost category is the amount remaining from prior allocations to clients in higher cost categories.

11. The system of claim 1 , wherein the system is a video-on-demand system.

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

a server device operative to store and deliver content having a fixed duration

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

a flow regulator configured to deliver content at a 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 bandwidth manager that controls the delivery of content by performing the following steps:

describing a control variable which represents the target flow rate of content from the server device to each client device, the target flow rate equal to or greater than a minimum allowed flow rate, wherein the minimum allowed flow rate is a non-increasing function of time obtained by dividing the content not yet delivered by remaining playtime, which 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;

prescribing bandwidth to all clients based upon a value of the control variables that satisfies the minimum allowed flow rate and a maximum allowed flow rate, and wherein the minimum and maximum allowed flow rates exploit the available server capacity to force early delivery of content to client buffers; and

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 an entire session.

13. The system of claim 12 , wherein a target flow rate commitment to a new client results in a reduced flow rate to existing clients.

14. The system of claim 12 , wherein a cessation of flow rate to a client results in an increased flow rate to remaining clients.

15. The system of claim 12 , wherein a reduction in a flow rate commitment to an ongoing client session causes increased flow rate to other clients.

16. The system of claim 12 , further comprising a flow envelope, which is shaped to favor higher paying customers by committing additional bandwidth to the higher paying customers if additional bandwidth is available.

17. The system of claim 16 , wherein lower paying customers are afforded additional bandwidth at a reduced flow rate as compared to the higher paying customers.

18. The system of claim 12 , wherein the minimum allowed flow constraint is set higher according to the quality of service for higher paying customers.

19. The system of claim 12 , further comprising a flow optimizer, the flow optimizer configured to modulate the target flow rate of the flow regulator in order to optimize an aggregate flow of content to ensure that all required content will be available to each client when needed.

20. The system of claim 12 , wherein the flow regulator is configured to deliver the targeted flow rate of content in response to the control variable, which varies over time.

21. The system of claim 12 , wherein the call acceptance module is configured to accept a call based upon an initial value of the control variable.

22. The system of claim 12 , wherein the clients are distinguished by their cost of service and bandwidth is apportioned to clients iteratively, the amount apportioned to each client in a cost category is the amount remaining from prior allocations to clients in higher cost categories.

23. The system of claim 12 , wherein the system apportions a given total flow rate among a plurality of sessions for clients by:

computing a sum of minimum allowable flow rate constraints for each session;

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

computing a difference between the given total flow rate and a sum of the flow rate minima;

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

if the factor exceeds 1, setting the flow rate to the maximum allowed client flow rate; and

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

24. The system of claim 12 , wherein the target client flow rate is constrained from below or to a non-decreasing function of time that starts at some multiple of the average consumption rate, which multiple equals or exceeds one.

25. The system of claim 24 , wherein the constraint on target client flow rate may increase within the bounds of admission capacity.

26. The system of claim 12 , wherein the system is a video-on-demand system.

Assignments (10)