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

• US 7,747,748 B2
• Filed: 01/07/2005
• Issued: 06/29/2010
• Est. Priority Date: 11/17/1998
• Status: Expired due to Fees

• Current Assignee: Musicqubed Innovations LLC (Ascend Innovation Management, LLC)
• Original Assignee: Democrasoft Incorporated
• Inventors: Allen, Arthur Douglas
• Primary Examiner(s): Nguyen, Thu Ha T
• Application Number:
  US11/031,416
• Publication Number:
  US 20050120131A1
• Time in Patent Office: 1,999 Days
• Field of Search: 709/219, 709/231, 709/203, 709/220, 709/223, 709/224, 709/226, 370/236, 370/397, 370/254, 370/468, 370232-235
• 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/823 Prediction of resource usage
• 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:

prescribing a control variable which represents a target flow rate from the server device to each client device of a stored digital content having a fixed duration;

prescribing a maximum allowed flow rate from the server device to each client device, wherein the maximum allowed flow rate is set equal to a minimum allowed flow rate, and wherein the minimum allowed flow rate is a non-increasing function of time obtained by dividing the digital 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 flow rate of the content;

determining a cost function of the control variables for all clients; and

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

2. The method of claim 1 wherein the minimum allowed flow rate starts at an initial flow rate that exceeds the average consumption rate.

3. The method of claim 1 wherein the minimum allowed client flow rate decreases in a series of steps.

4. The method of claim 3 wherein the series of steps starts from an initial flow rate that exceeds an average consumption rate.

5. The method of claim 4, further comprising re-computing the target flow rates when a new client device is admitted.

6. The method of claim 5, wherein a new client device is accepted by:

determining an admission capacity of the bandwidth;

admitting the new client device if the client device'"'"'s minimum allowed value of the control variable is less than the admission capacity; and

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

7. The method of claim 3, further comprising reevaluating the control variable whenever the minimum allowed client flow rate undergoes a step change.

8. The method of claim 4, further comprising re-computing the target flow rates when the minimum allowed flow rate for a client device undergoes a step change.

9. The method of claim 1 wherein the minimum allowed client flow rate increases in steps to an available admission capacity.

10. The method of claim 9 wherein the minimum allowed flow rate starts at an initial flow rate that exceeds the average consumption rate.

11. The method of claim 1, further comprising reevaluating the control variables on a periodic basis.

12. The method of claim 11 wherein the periodic basis is at least once a second.

13. The method of claim 1, further comprising reevaluating the control variable whenever a new client device is admitted.

14. The method of claim 1, wherein the minimum allowed client flow rate steps up over time to an extent of available admission capacity, such that no existing sessions are compromised.

15. The method of claim 1, wherein the client device is a video-on-demand system.

16. The method of claim 1, wherein the server device simultaneously serves the stored digital content to a plurality of client devices, and wherein the stored digital content is viewed and played back at each client device.

17. The method of claim 1, wherein the control variable further comprises:

determining optimal delivery rates to each client device and determining whether new client devices may be accepted without diminishing the quality of service to existing client devices.

18. The method of claim 1, further comprising:

sorting each client device by flow rate range;

establishing remaining server bandwidth, wherein the remaining server bandwidth is calculated by subtracting the minimum allowed flow rate of each client device from total bandwidth; and

allocating remaining server bandwidth to each client device.

19. The method of claim 18, further comprising allocating remaining server bandwidth evenly to each client device.

20. The method of claim 18, further comprising allocating remaining server bandwidth to higher paying client devices.