RELIABLE EVENT BROADCASTER WITH MULTIPLEXING AND BANDWIDTH CONTROL FUNCTIONS

• US 20070180119A1
• Filed: 01/24/2007
• Published: 08/02/2007
• Est. Priority Date: 01/31/2006
• Status: Active Grant

• Current Assignee: DIRECTV, LLC (AT&T, Inc.)
• Original Assignee: Roundbox, Inc. (AT&T, Inc.)
• Inventors: Liu, Xiaofeng, Valloppillil, Vinod, Villanueva, Edgar, Khivesara, Amit, Mataga, Peter, Torkelson, Cary
• Granted Patent: US 8,149,771 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• 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/2475 for supporting traffic characterised by the type of applications
• 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/803 Application aware
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/828 Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A system, apparatus, and method for transmitting data in a broadcast mode to multiple devices operating in a network. The invention enables the efficient utilization of bandwidth while providing a desired level of quality of service for the applications executing on the devices that utilize the broadcasted data. The invention utilizes a set of bandwidth constraints in combination with a set of heuristics and rules for the allocation and re-allocation of bandwidth among multiple applications in a manner that minimizes the impact on the quality of service metrics of importance to the affected applications when contention exists for the network resources. The present invention implements processes to cause the quality of service provided to each application to degrade smoothly, with certain priorities and guarantees being maintained. The present invention also provides event segmentation and reassembly functions for applications, and includes reliability mechanisms to increase the ability to provide data to client devices that have not been actively receiving for significant periods of time.

Claims

1. A method of allocating bandwidth of a communications system among multiple applications using the communications system to transfer data, comprising:

determining a value for the aggregate bandwidth B_A available to all applications;

determining a first bandwidth limit B₁ for each application, wherein B₁ represents a minimum guaranteed bandwidth limit;

determining a second bandwidth limit B₂ for each application, wherein B₂ represents an expected bandwidth limit that is not less than the first bandwidth limit;

determining a relative priority level for each application, wherein the relative priority level has a value P_i, and, P<sub><

i</sub> represents all priority levels less than P_i, and P<sub>>

i</sub> represents all priority levels greater than P_i;

wherein the bandwidth limits satisfy the relationships

the sum of B₁ for all applications does not exceed B_A, and

for each relative priority value, P_i, the sum of B₂ for each application at priority level P_i plus the sum of B₁ for each application at priority P<sub><

i</sub> does not exceed B_A; and

allocating bandwidth to each of the applications, wherein the bandwidth allocation satisfies the relationship that the sum of bandwidth allocated to all applications does not exceed B_A.

2. The method of claim 1, further comprising:

determining a desired bandwidth D for each application, and further, wherein allocating bandwidth to each of the applications satisfies the relationships

the sum of bandwidth allocated to all applications does not exceed B_A;

each application is allocated at least the lower of D and B₁;

each application at priority P_i whose D is not less than B₂ is not allocated less than B₂, unless each application at priority P<sub>>

i</sub> has been allocated no more than B₂; and

each application at priority P_i is not allocated less than D, unless each application at priority P<sub>>

i</sub> has been allocated no more than D.

3. The method of claim 1, wherein determining a first bandwidth limit B₁ a second bandwidth limit B₂, and a desired bandwidth D for each application further comprises for each application:

determining an expected level of quality of service (QoS) for the application;

converting the expected level of QoS into an equivalent value for B₂ for the application; and

converting B₁ and D into QoS values relative to B₂ for the application.

4. The method of claim 1, further comprising:

determining a desired level of quality of service (QoS) for one of the multiple applications; and

adjusting the bandwidth allocated to the one of the multiple applications without providing notification to that application, wherein the bandwidth adjustment is performed so that

if the application is currently under utilizing its allocated bandwidth it is provided less bandwidth only if doing so does not affect the application'"'"'s desired QoS;

if the application is currently over utilizing its allocated bandwidth it is provided additional bandwidth, where the additional bandwidth is sufficient to maintain the application'"'"'s desired QoS; and

if additional bandwidth is provided to the application, that bandwidth is allocated from one or more other applications that are under utilizing their respective bandwidths, wherein the one or more applications each have an associated desired level of quality of service (QoS), and the one or more applications are provided less bandwidth only if doing so does not affect the one or more application'"'"'s desired QoS.

5. The method of claim 1, further comprising:

determining a level of quality of service (QoS) associated with an application; and

providing data regarding a change in the level of QoS to the application.

6. An apparatus for delivering data to a plurality of client devices over a communications network, comprising:

a registration element configured to register an application, the application providing data to be delivered to the client devices;

a bandwidth allocation element configured to allocate bandwidth of the communications network to the application;

a communications network formatting element configured to format the provided data for transport over the communications network; and

a communications network control element configured to provide the formatted data to the communications network for transport over the communications network.

7. The apparatus of claim 6, wherein the registration element registers a plurality of applications, and further, wherein the bandwidth allocation element is configured to allocate the communications network bandwidth to the plurality of applications.

8. The apparatus of claim 7, wherein the bandwidth allocation element is configured to allocate the communications network bandwidth to the plurality of applications by executing a bandwidth allocation process, the bandwidth allocation process comprising

determining a value for the aggregate bandwidth B_A available to all applications;

determining a first bandwidth limit B₁ for each application, wherein B₁ represents a minimum guaranteed bandwidth limit;

determining a second bandwidth limit B₂ for each application, wherein B₂ represents an expected bandwidth limit that is not less than the first bandwidth limit;

determining a relative priority level for each application, wherein the relative priority level has a value P_i, and, P<sub><

i</sub> represents all priority levels less than P_i, and P<sub>>

i</sub> represents all priority levels greater than P_i;

wherein the bandwidth limits satisfy the relationships

the sum of B₁ for all applications does not exceed B_A, and

for each relative priority value, P_i, the sum of B₂ for each application at priority level P_i plus the sum of B₁ for each application at priority P<sub><

i</sub> does not exceed B_A; and

allocating bandwidth to each of the applications, wherein the bandwidth allocation satisfies the relationship that the sum of bandwidth allocated to all applications does not exceed B_A.

9. The method of claim 8, further comprising:

determining a desired bandwidth D for each application, and further, wherein allocating bandwidth to each of the applications satisfies the relationships

the sum of bandwidth allocated to all applications does not exceed B_A;

each application is allocated at least the lower of D and B₁;

each application at priority P_i whose D is not less than B₂ is not allocated less than B₂, unless each application at priority P<sub>>

i</sub> has been allocated no more than B₂; and

each application at priority P_i is not allocated less than D, unless each application at priority P<sub>>

i</sub> has been allocated no more than D.

10. The method of claim 8, wherein determining a first bandwidth limit B₁ a second bandwidth limit B₂, and a desired bandwidth D for each application further comprises for each application:

determining an expected level of quality of service (QoS) for the application;

converting the expected level of QoS into an equivalent value for B₂ for the application; and

converting B₁ and D into QoS values relative to B₂ for the application.

11. The method of claim 7, further comprising:

determining a desired level of quality of service (QoS) for one of the multiple applications; and

adjusting the bandwidth allocated to the one of the multiple applications without providing notification to that application, wherein the bandwidth adjustment is performed so that

if the application is currently under utilizing its allocated bandwidth it is provided less bandwidth only if doing so does not affect the application'"'"'s desired QoS;

if the application is currently over utilizing its allocated bandwidth it is provided additional bandwidth, where the additional bandwidth is sufficient to maintain the application'"'"'s desired QoS; and

if additional bandwidth is provided to the application, that bandwidth is allocated from one or more other applications that are under utilizing their respective bandwidths, wherein the one or more applications each have an associated desired level of quality of service (QoS), and the one or more applications are provided less bandwidth only if doing so does not affect the one or more application'"'"'s desired QoS.

12. The method of claim 6, further comprising:

determining a level of quality of service (QoS) associated with the application; and

providing data regarding a change in the level of QoS to the application.

13. The apparatus of claim 6, wherein the formatted data is broadcast over the communications network.

14. An apparatus for receiving data transported over a communications network intended for an application executing on the apparatus, comprising:

a registration element configured to register the application;

a data assembly element configured to process data received from the communications network, the data assembly element producing an event from one or more data packets;

a cache configured to store the received data; and

a scheduling element configured to determine when to provide the event to the application.

15. The apparatus of claim 14, wherein the received data has been broadcast over the communications network.

16. The apparatus of claim 14, wherein the scheduling element is configured to provide the event to the application after determining that all data required for the event has been received and placed into a desired order.

17. A system for the delivery of data over a communications network to a client application, comprising:

a server apparatus comprising

a registration element configured to register a server application, the server application providing data to be delivered to the client application;

a bandwidth allocation element configured to allocate bandwidth of the communications network to the server application;

a communications network formatting element configured to format the provided data for transport over the communications network; and

a communications network control element configured to provide the formatted data to the communications network for transport over the communications network; and

a client device comprising

a registration element configured to register the client application;

a data assembly element configured to process data received from the communications network, the data assembly element producing an event from one or more data packets;

a cache configured to store the received data; and

a scheduling element configured to determine when to provide the event to the client application.

18. The system of claim 17, further comprising:

a communications network configured to transport data between the server apparatus and client device.

19. The system of claim 17, wherein the data is broadcast over the communications network.

20. The system of claim 17, wherein the communications network is a wireless network.

21. The system of claim 17, wherein the server apparatus registration element registers a plurality of applications, and further, wherein the bandwidth allocation element is configured to allocate the communications network bandwidth to the plurality of applications.

22. The apparatus of claim 21, wherein the bandwidth allocation element is configured to allocate the communications network bandwidth to the plurality of applications by executing a bandwidth allocation process, the bandwidth allocation process comprising

determining a value for the aggregate bandwidth B_A available to all applications;

determining a first bandwidth limit B₁ for each application, wherein B₁ represents a minimum guaranteed bandwidth limit;

determining a second bandwidth limit B₂ for each application, wherein B₂ represents an expected bandwidth limit that is not less than the first bandwidth limit;

determining a relative priority level for each application, wherein the relative priority level has a value P_i, and, P<sub><

i</sub> represents all priority levels less than P_i, and P<sub>>

i</sub> represents all priority levels greater than P_i;

wherein the bandwidth limits satisfy the relationships

the sum of B₁ for all applications does not exceed B_A, and

for each relative priority value, P_i, the sum of B₂ for each application at priority level P_i plus the sum of B₁ for each application at priority P<sub><

i</sub> does not exceed B_A; and

allocating bandwidth to each of the applications, wherein the bandwidth allocation satisfies the relationship that the sum of bandwidth allocated to all applications does not exceed B_A.

23. The method of claim 22, further comprising:

determining a desired bandwidth D for each application, and further, wherein allocating bandwidth to each of the applications satisfies the relationships

the sum of bandwidth allocated to all applications does not exceed B_A;

each application is allocated at least the lower of D and B₁;

each application at priority P_i whose D is not less than B₂ is not allocated less than B₂, unless each application at priority P<sub>>

i</sub> has been allocated no more than B₂; and

each application at priority P_i is not allocated less than D, unless each application at priority P<sub>>

i</sub> has been allocated no more than D.

24. The method of claim 22, wherein determining a first bandwidth limit B₁ a second bandwidth limit B₂, and a desired bandwidth D for each application further comprises for each application:

determining an expected level of quality of service (QoS) for the application;

converting the expected level of QoS into an equivalent value for B₂ for the application; and

converting B₁ and D into QoS values relative to B₂ for the application.

25. The method of claim 21, further comprising:

determining a desired level of quality of service (QoS) for one of the multiple applications; and

adjusting the bandwidth allocated to the one of the multiple applications without providing notification to that application, wherein the bandwidth adjustment is performed so that

if the application is currently under utilizing its allocated bandwidth it is provided less bandwidth only if doing so does not affect the application'"'"'s desired QoS;

if the application is currently over utilizing its allocated bandwidth it is provided additional bandwidth, where the additional bandwidth is sufficient to maintain the application'"'"'s desired QoS; and

if additional bandwidth is provided to the application, that bandwidth is allocated from one or more other applications that are under utilizing their respective bandwidths, wherein the one or more applications each have an associated desired level of quality of service (QoS), and the one or more applications are provided less bandwidth only if doing so does not affect the one or more application'"'"'s desired QoS.

26. The method of claim 17, further comprising:

determining a level of quality of service (QoS) associated with the server application; and

providing data regarding a change in the level of QoS to the server application.

27. A method of distributing data to multiple client devices over a communications network, comprising:

registering an application to provide data to the client devices;

allocating bandwidth of the communications network to the application;

processing data provided by the application for transport over the communications network;

transporting the processed data over the communications network;

wherein for each client device, the method comprises

registering a client application with the client device;

receiving the data after transport over the communications network;

caching the data in a storage medium;

scheduling delivery of the data; and

providing the data to the client application.

28. The method of claim 27, wherein transporting the processed data over the communications network further comprises broadcasting the data over the communications network.

29. The method of claim 27, wherein the communications network is a wireless network.

30. The method of claim 27, wherein registering an application to provide data to the client devices further comprises registering a plurality of applications, and further, wherein allocating bandwidth of the communications network to the application further comprises allocating the communications network bandwidth to a plurality of applications by executing a bandwidth allocation process, the bandwidth allocation process comprising

determining a value for the aggregate bandwidth B_A available to all applications;

determining a first bandwidth limit B₁ for each application, wherein B₁ represents a minimum guaranteed bandwidth limit;

determining a second bandwidth limit B₂ for each application, wherein B₂ represents an expected bandwidth limit that is not less than the first bandwidth limit;

determining a relative priority level for each application, wherein the relative priority level has a value P_i, and, P<sub><

i</sub> represents all priority levels less than P_i, and P<sub>>

i</sub> represents all priority levels greater than P_i;

wherein the bandwidth limits satisfy the relationships

the sum of B₁ for all applications does not exceed B_A, and

for each relative priority value, P_i, the sum of B₂ for each application at priority level P_i plus the sum of B₁ for each application at priority P<sub><

i</sub> does not exceed B_A; and

allocating bandwidth to each of the applications, wherein the bandwidth allocation satisfies the relationship that the sum of bandwidth allocated to all applications does not exceed B_A.

31. The method of claim 30, further comprising:

determining a desired bandwidth D for each application, and further, wherein allocating bandwidth to each of the applications satisfies the relationships

the sum of bandwidth allocated to all applications does not exceed B_A;

each application is allocated at least the lower of D and B₁;

each application at priority P_i whose D is not less than B₂ is not allocated less than B₂, unless each application at priority P<sub>>

i</sub> has been allocated no more than B₂; and

each application at priority P_i is not allocated less than D, unless each application at priority P<sub>>

i</sub> has been allocated no more than D.

32. The method of claim 30, wherein determining a first bandwidth limit B₁ a second bandwidth limit B₂, and a desired bandwidth D for each application further comprises for each application:

determining an expected level of quality of service (QoS) for the application;

converting the expected level of QoS into an equivalent value for B₂ for the application; and

converting B₁ and D into QoS values relative to B₂ for the application.

33. The method of claim 30, further comprising:

determining a desired level of quality of service (QoS) for one of the multiple applications; and

adjusting the bandwidth allocated to the one of the multiple applications without providing notification to that application, wherein the bandwidth adjustment is performed so that

if the application is currently under utilizing its allocated bandwidth it is provided less bandwidth only if doing so does not affect the application'"'"'s desired QoS;

if the application is currently over utilizing its allocated bandwidth it is provided additional bandwidth, where the additional bandwidth is sufficient to maintain the application'"'"'s desired QoS; and

if additional bandwidth is provided to the application, that bandwidth is allocated from one or more other applications that are under utilizing their respective bandwidths, wherein the one or more applications each have an associated desired level of quality of service (QoS), and the one or more applications are provided less bandwidth only if doing so does not affect the one or more application'"'"'s desired QoS.

34. The method of claim 27, further comprising:

determining a level of quality of service (QoS) associated with the application; and

providing data regarding a change in the level of QoS to the application.