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

• US 7,334,044 B1
• Filed: 06/25/1999
• Issued: 02/19/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): ZIA, SYED
• Application Number:
  US09/344,688
• Time in Patent Office: 3,161 Days
• Field of Search: 709/223, 709/226, 709/231, 709/203, 709/232, 709/233, 709/234, 370/352, 370229-238, 370254-258, 370/386, 370/400, 370/401, 370/422, 370428-429, 370/477, 370486-490, 370/468, 725105-106, 725/114, 725/118
• 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 is disclosed for call and/or connection acceptance control and the optimal delivery of multimedia (audio/video) data over networks. This method involves the establishment and monitoring of certain criteria which may be used to maximize the number of simultaneous clients without sacrificing quality-of-service for already-connected clients. Methods are disclosed for maximizing total throughput as well as maximum charge models for different levels of service. The disclosed methods solve these optimization problems by expanding on linear-program techniques in manners geared towards multimedia content delivery over networks and many variations suitable for varying business models are disclosed.

Claims

1. A method for optimal multimedia content delivery over networks from a server to one or more clients, comprising:

delineating a state variable that represents a data rate for delivery of multimedia content having a fixed duration and, wherein an initial data rate is equal to or greater than a minimum flow rate, and wherein the minimum flow rate ensures that all required content will be available to each client when needed, and a subsequent data rate, which is equal to or less than a real-time rate of play back of the multimedia content;

delineating a set of conditions which represent time-varying constraints on the data rate of said multimedia content said conditions including;

(1) the total data rate for all clients does not exceed the maximum throughput of the server or network, whichever is least;

(2) the data rate from server to client does not exceed the maximum data rate for the client;

(3) the data rate of the client will never overflow a client buffer;

(4) the server will never underflow; and

(5) the data rate from the server will never be less than the client'"'"'s minimum data rate, and wherein the minimum data rate is a non-increasing function of time obtained by dividing the content not yet delivered by the remaining play time;

delineating a cost function which represents the value of a proposed solution;

performing periodic computations in compliance with conditions (1)-(5) to obtain a state value that maximizes said cost function; and

periodically adjusting the data rate to each client to maintain an optimal solution over a given period of time.

2. A method as in claim 1, wherein said conditions further include

(6) the current maximum client data rate is given by the minimum of:

the stored initial maximum client data rate;

the data rate required to fill the remaining client buffer during the current of said periodic computations;

the data rate required to complete the delivery of said multimedia content;

the client data rate never exceeds said current maximum client data rate; and

whereby said current maximum client data rate is periodically recomputed to maintain an optimal solution over a given period of time.

3. A method as in claim 2, wherein:

said cost function represents maximal throughput and is given by the sum of said client data rates for all active clients.

4. A method as in claim 2, wherein:

said cost function represents maximal charge and is given by the sum for all active clients of said client data rates times the client'"'"'s cost of service.

5. A method as in claim 3 for bandwidth allocation for delivery of multimedia data from server to one or more clients over a network, comprising the steps of:

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

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

initializing current flow rate for each client as said minimum flow rate and summing said flow rate into total server flow rate; and

allocating remaining server bandwidth to remaining clients until they each saturate or no bandwidth remains.

6. A method as in claim 5 wherein said step of allocating remaining server bandwidth to remaining clients comprising:

sorting the list of clients according to said flow rate range;

determining equally-allocated remaining server bandwidth if allocated evenly to all remaining unprocessed clients;

determining the range of remaining client bandwidth as given by the difference between said maximum flow rate and said minimum flow rate;

determining saturation by comparing said equally-allocated remaining server bandwidth and said range of remaining client bandwidth, and allocating the lesser of these two amounts to each remaining client flow rate; and

whereby allocating flow to remaining clients based upon the sorted client range flow rates and determining allocation of remaining server bandwidth based upon a comparison of saturation of server versus saturation of each client maximizes allocation of total bandwidth for maximal flow rate to maximum number of clients.

7. A method as in claim 4 for bandwidth allocation for delivery of multimedia data from server to one or more clients over a network, comprising the steps of:

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

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

sorting the list of clients according to said flow rate range;

initializing current flow rate for each client as said minimum flow rate and summing said flow rate into total server flow rate; and

allocating remaining server bandwidth to remaining clients such that lower paying clients receive bandwidth only if higher paying ones are saturated.

8. A method as in claim 7 wherein said step of allocating remaining server bandwidth to remaining clients comprises the steps of:

for each remaining unprocessed client;

determining equally-allocated remaining server bandwidth if allocated evenly to all remaining unprocessed clients;

determining the range of remaining client bandwidth as given by the difference between said maximum flow rate and said minimum flow rate;

determining saturation by comparing said equally-allocated remaining server bandwidth and said range of remaining client bandwidth, and allocating the lesser of these two amounts to each remaining client flow rate; and

whereby allocating flow to remaining clients based upon the sorted client range flow rates and determining allocation of remaining server bandwidth based upon a comparison of saturation of server versus saturation of each client maximizes allocation of total bandwidth for maximal flow rate to maximum number of clients.

15. The method of claim 1, wherein the data rate ensures that all required content will be available to each client when needed.

16. The method of claim 1, further comprising ceasing delivery of the multimedia content to the at least one client when the content not yet delivered is equal to zero.

17. The method of claim 1, further comprising accepting a new client by:

determining an admission capacity of the bandwidth;

admitting a prospective client if the clients minimum allowed value of the state 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.

9. A method for connection acceptance control for delivery of multimedia data from server to one or more clients over a network, comprising the steps of:

determining server swing capacity given by the difference between the total server bandwidth and the sum of the minimum flow rates of all currently-connected clients receiving multimedia data having a fixed duration, wherein the minimum flow rate for each client is expressed as a non-increasing function of time obtained by dividing data not vet delivered by remaining play time, and wherein the minimum flow rate ensures that all required data will be available to each client when needed; and

allocating server bandwidth for each prospective client which will fit without server bandwidth saturation, as determined by comparing an average data play rate of each prospective client with the remaining bandwidth, represented by said server swing capacity, available to the server.

10. A method as in claim 9 wherein said remaining bandwidth available to the server is given by said server swing capacity.

11. A method as in claim 10 wherein said remaining bandwidth available to the server is give by said server swing capacity less a server flow safety margin, thereby allowing server capacity to be subsequently lowered by up to the safety margin without requiring load shedding, and without affecting client sessions in process.

12. A method as in claim 9 wherein said step of allocating server bandwidth for each prospective client which will fit without server bandwidth saturation comprises:

allocating server bandwidth to each prospective client sequentially until a prospective client is located in which said average data play rate exceeds said server swing capacity.

13. A method as in claim 9 wherein said step of allocating server bandwidth for each client which will fit without server bandwidth saturation comprises:

allocating server bandwidth to each prospective client sequentially for each client which can be activated without server bandwidth saturation.

14. A method for bandwidth allocation for delivery of multimedia data from a server to one or more clients over a network, the method comprising:

storing multimedia data on at least one server, the multimedia data having a fixed duration;

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

storing a sequence of data representing scheduled bandwidth changes for the at least one server;

determining a maximum flow rate and a minimum flow rate for each of the one or more clients at the present time, the determination of the minimum flow rate being based on a non-increasing function of time obtained by dividing multimedia data not yet delivered by remaining play time, and wherein the minimum allowed flow rate ensures that all required multimedia data will be available to each client when needed;

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

sorting the list of clients according to said flow rate range;

initializing current flow rate for each client as said minimum flow rate and summing said flow rate into total server flow rate; and

allocating remaining server bandwidth to remaining clients.

18. The method of claim 14, further comprising ceasing delivery of the multimedia data to the at least one client when the data not yet delivered is equal to zero.

19. The method of claim 14, further comprising accepting a new client by:

determining an admission capacity of the bandwidth;

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

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