System and process for performing an exponentially weighted moving average on streaming data to establish a moving average bit rate

• US 20060126713A1
• Filed: 12/10/2004
• Published: 06/15/2006
• Est. Priority Date: 12/10/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Klemets, Anders E., Chou, Philip A., Huang, Cheng
• Granted Patent: US 7,543,073 B2
• Time in Patent Office: Days
• US Class Current: 375/225
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04N 21/23406 involving management of server-side video buffer
• 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/44004 involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/6373 for rate control , e.g. request to the server to modify its transmission rate flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/6379 directed to encoder , e.g. for requesting a lower encoding rate
• CPC Class Codes: H04N 21/6547 comprising parameters, e.g. for client setup

Abstract

A system and process for performing an exponentially weighted moving average on streaming data to establish a moving average bit rate of data units is presented. In general, the system or process computes, on a unit-by-unit basis, the product of the moving average bit rate computed for a data unit immediately prior to a unit under consideration and a first fractional weighting factor, added to the product of the instantaneous bit rate of the data unit under consideration and a second fractional weighting factor, wherein at least one fractional weighting factor is not a constant but instead based on the time between data units.

Claims

1. A computer-implemented process for performing an exponentially weighted moving average on streaming data being transmitted to a client from a server over a computer network to establish a moving average bit rate of data units, comprising performing the following process actions:

computing, on a data unit-by-unit basis, the product of the moving average bit rate computed for a data unit arriving immediately prior to a unit under consideration and a first fractional weighting factor, added to the product of the instantaneous bit rate of the data unit under consideration and a second fractional weighting factor, wherein at least one of the fractional weighting factors is not a constant but instead based on the time between the data units; and

establishing the results of the computation as the moving average bit rate of the data units.

2. The process of claim 1, wherein said first fractional weighting factor β

(k) for a data unit under consideration k is computed as

$\frac{{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(k-1\right)\right]}-{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(0\right)\right]}}{1-{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(0\right)\right]}}$

where α

is the reciprocal of a prescribed time constant, t(k) is the actual arrival time of the data unit under consideration, t(k−

1) is the actual arrival time of the data unit received immediately prior to the data unit under consideration, and t(0) is the arrival time of the first data unit of the streaming data, and wherein the instantaneous arrival rate r_a(k) of the data unit under consideration is computed as

$\frac{b<br><br>\left(k\right)}{t_a<br><br>\left(k\right)-t_a<br><br>\left(k-1\right)},$

where b(k) is the size of the data unit under consideration, and the second fractional weighting factor is one minus the first fractional weighting factor.

3. The process of claim 1, wherein said first fractional weighting factor is 1 and said second fractional weighting factor is

$\frac{\alpha }{}$

1 - ⅇ

- α

⁡

[ t ⁡

( k ) - t ⁡

( 0 ) ] ,

and is used whenever t(k)=t(k−

1).

4. The process of claim 1, wherein the data units of the streaming data are packets.

5. A computer-readable medium having computer-executable instructions for performing the process actions recited in claim 1.

6. The process of claim 1, wherein the process actions of computing and establishing are preformed by the client, and wherein the moving average bit rate refers to the moving average arrival rate of the data units.

7. The process of claim 1, wherein the process actions of computing and establishing are preformed by the server, and wherein the moving average bit rate refers to the moving average transmission rate of the data units.

8. A system for performing an exponentially weighted moving average on streaming data being transmitted to a client from a server over a computer network to establish a moving average bit rate of data units, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

compute, on a data unit-by-unit basis, the product of the moving average bit rate computed for a data unit immediately prior to a data unit under consideration and a first fractional weighting factor, added to the product of the instantaneous bit rate of the data unit under consideration and a second fractional weighting factor, wherein at least one fractional weighting factor is not a constant but instead based on the time between the data units.

9. The system of claim 8, wherein said first fractional weighting factor β

(k) for a data unit under consideration k is computed as

$\frac{{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(k-1\right)\right]}-{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(0\right)\right]}}{1-{\mathrm{e<br><br>}}^{-\mathrm{\alpha <br><br>}<br><br>\left[t<br><br>\left(k\right)-t<br><br>\left(0\right)\right]}}$

where α

is the reciprocal of a prescribed time constant, t(k) is the time stamp of the data unit under consideration, t(k−

1) is the time stamp of the data unit immediately prior to the frame under consideration, and t(0) is the time stamp of the first data unit of the streaming data, and wherein the instantaneous bit rate r_a(k) of the data unit under consideration is computed as

$\frac{b<br><br>\left(k\right)}{t_a<br><br>\left(k\right)-t_a<br><br>\left(k-1\right)},$

where b(k) is the size of the data unit under consideration, and second fractional weighting factor is one minus the first fractional weighting factor.

10. The system of claim 8, wherein said first fractional weighting factor is 1 and said second fractional weighting factor is

$\frac{\alpha }{}$

1 - ⅇ

- α

⁡

[ t ⁡

( k ) - t ⁡

( 0 ) ] ,

and is used whenever t(k)=t(k−

1).

11. The system of claim 8, wherein a data unit is defined as the amount of streaming data in a prescribed time period.

12. The system of claim 11, wherein the prescribed time period is one second such that the data unit rate is one data unit per second.

13. A computer-implemented process for performing an exponentially weighted moving average on streaming data being transmitted over a computer network to establish a moving average bit rate of data units, comprising:

a computing step for computing, on a data unit-by-unit basis, the product of the moving average bit rate computed for a data unit immediately prior to a unit under consideration and a first fractional weighting factor, added to the product of the instantaneous bit rate of the data unit under consideration and a second fractional weighting factor, wherein at least one fractional weighting factor is not a constant but instead based on the interval of time between data units; and

an establishing step for establishing the results of the computation as the moving average bit rate of the data units.