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

• US 7,827,301 B2
• Filed: 06/02/2006
• Issued: 11/02/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
• Primary Examiner(s): ZIA, SYED
• Application Number:
  US11/445,579
• Publication Number:
  US 20060224666A1
• Time in Patent Office: 1,614 Days
• Field of Search: None
• US Class Current: 709/233
• 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/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/826 Involving periods of time
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• 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/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/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 for bandwidth allocation for delivery of multimedia data from at least one server to one or more clients over a network. The method includes the steps of: determining a maximum flow rate and a minimum flow rate for each client; determining a flow rate range for each client as given by the difference between the maximum flow rate and the minimum flow rate; sorting the one or more clients according to the flow rate range; initializing a current flow rate for each client as the minimum flow rate and summing the flow rate into total server flow rate; establishing remaining server bandwidth; and allocating the remaining server bandwidth to clients, based upon the sorted client'"'"'s flow rate ranges.

Claims

1. A method for bandwidth allocation for delivery of multimedia data from at least one server to clients over a network, the method comprising:

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

determining a flow rate range for each client, the flow rate range being the difference between the maximum flow rate and the minimum flow rate;

sorting the clients according to the flow rate range respectively associated with each client;

initializing a current flow rate for each client as the minimum flow rate respectively associated with each client;

summing the flow rate for each client into a total server flow rate;

establishing remaining server bandwidth based on the total server flow rate; and

allocating the remaining server bandwidth to one or more of the clients based upon the flow rate ranges of the sorted clients.

2. The method of claim 1, wherein allocating the remaining server bandwidth comprises:

determining a portion of the remaining server bandwidth equal to the remaining server band width divided by the number of unprocessed clients, the unprocessed clients being clients having a current flow rate equal to the initialized flow rate; and

allocating an amount of the remaining server bandwidth to a client, the amount equal to the lesser of the determined portion of the remaining server bandwidth and the flow rate range of that client, wherein the determining of the portion and the allocating of the amount are performed individually for each client in sequence according to the flow rate respectively associated with each client.

3. The method of claim 1, further comprising sorting the clients according to categories of service corresponding to payment rates.

4. The method of claim 3, wherein allocating the remaining server bandwidth comprises:

determining a portion of the remaining server bandwidth equal to the remaining server band width divided by the number of unprocessed clients, the unprocessed clients being clients having a current flow rate equal to the initialized flow rate; and

allocating an amount of the remaining server bandwidth to a client, the amount equal to the lesser of the determined portion of the remaining server bandwidth and the flow rate range of that client, wherein the determining of the portion and the allocating of the amount are performed individually for each client in sequence according to the flow rate respectively associated with each client

determining saturation by comparing the equally allocated remaining bandwidth and the range of client bandwidth and allocating the lesser of these two to each client flow rate.

5. The method of claim 1, wherein allocating the remaining server bandwidth is further based upon a comparison of saturation of server versus saturation of each client in order to maximize allocation of total bandwidth for a maximal flow rate to a maximum number of clients.

6. The method of claim 1, wherein allocating the remaining server bandwidth comprises allocating remaining server bandwidth to remaining clients such that lower paying clients receive bandwidth when higher paying clients are saturated.

7. The method of claim 1, wherein allocating the remaining server bandwidth comprises:

determining a portion of the remaining server bandwidth equal to the remaining server band width divided by the number of unprocessed clients, the unprocessed clients being clients having a current flow rate equal to the initialized flow rate; and

allocating an amount of the remaining server bandwidth to a client, the amount equal to the lesser of the determined portion of the remaining server bandwidth and the flow rate range of that client, wherein the determining of the portion and the allocating of the amount are performed individually for each client in sequence according to the flow rate respectively associated with each client, and wherein allocating flow to clients is based upon a comparison of saturation of server versus saturation of each client that maximizes allocation of total bandwidth for maximal flow rate to a maximum number of clients.

8. The method of claim 1, wherein the minimum flow rate for each client is expressed as a non-increasing function of time.

9. The method of claim 8, wherein the minimum flow rate is obtained by dividing content not yet delivered by remaining play time.

10. A method for connection acceptance control for delivery of multimedia data from server to clients over a network, the method comprising:

determining a minimum flow rate for each client;

determining server swing capacity, the server swing capacity being the difference between total server bandwidth and a summation of the minimum flow rate of each client; and

allocating server bandwidth to each client without achieving server bandwidth saturation, the server bandwidth saturation being determined by comparing an average data play rate of each client with remaining bandwidth available to the server.

11. The method of claim 10, wherein the remaining bandwidth available to the server is equal to the server swing capacity.

12. The method of claim 10, wherein the remaining bandwidth available to the server is equal to the server swing capacity minus a server flow safety margin.

13. The method of claim 12, wherein allocating the server bandwidth for each client without achieving server bandwidth saturation includes allocating server bandwidth to each client sequentially until a client has an average data play rate that exceeds the server swing capacity.

14. The method of claim 13, wherein allocating the server bandwidth for each client without achieving server bandwidth saturation further includes allocating server bandwidth to clients sequentially for each client that can be activated without achieving server bandwidth saturation.

15. The method of claim 14, further comprising storing a sequence of data representing scheduled bandwidth changes for the server.

16. The method of claim 10, 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.