Apparatus and method for media transmission bandwidth control using bandwidth estimation

Description

TECHNICAL FIELD

The present invention relates in general to media encoding and decoding.

BACKGROUND

An increasing number of applications today make use of digital media for various purposes including, for example, remote business meetings via video conferencing, high definition video entertainment, video advertisements, and sharing of user-generated videos. As technology is evolving, users have higher expectations for media quality and, for example, expect high resolution video even when transmitted over communications channels having limited bandwidth.

To permit transmission of digital media streams while limiting bandwidth consumption, a number of video compression schemes have been devised, including formats such as VPx, promulgated by Google, Inc. of Mountain View, California, and H.264, a standard promulgated by ITU-T Video Coding Experts Group (VCEG) and the ISO/TEC Moving Picture Experts Group (MPEG), including present and future versions thereof. H.264 is also known as MPEG-4 Part 10 or MPEG-4 AVC (formally, ISO/TEC 14496-10).

One type of media transmission includes real-time encoding and transmission, in which the receiver of a media stream decodes and renders media data (i.e. video frames) as it is received. For example, in a real-time video implementation, if video is encoded at a bitrate greater than the available bandwidth of the networks over which it is to be transmitted, portions of the encoded video stream may not be able to be received and decoded by the receiver in real-time.

SUMMARY

Disclosed herein are embodiments of methods and apparatuses for determining an estimated available bandwidth.

Included in the disclosed embodiments is a method for determining an estimated available bandwidth for transmitting a media stream over a network, the media stream having a plurality of frames. The method includes receiving some of the plurality of frames, determining an inter-arrival time differential d for each of the received frames, the inter-arrival time differential d_i for a current frame i calculated using a formula d_i=(t_i−t_i−1)−(T_i−T_i−1), wherein: t_i is a receive time of a current frame i, t_i−1 is a receive time of a previous frame i−1 that immediately precedes the current frame i, T_i is a timestamp of the current frame i, and T_i−1 is a timestamp of the previous frame i−1, determining an inter-frame size differential dL for each of the received frames, the inter-frame size differential dL_i for a current frame i calculated as the difference between a frame size of the current frame i and a frame size of the previous frame i−1, determining an estimated function having a slope C_i⁻¹ and an offset m_i based on at least some of the inter-arrival time differentials and inter-frame size differentials, and determining the estimated available bandwidth based on a comparison between the offset m_i and one or more thresholds.

Included in the disclosed embodiments is a method for regulating a bitrate of a media stream encoded by a transmitting station based on an estimated available bandwidth determined by a receiving station, the media stream having a plurality of frames. The method includes receiving some of the plurality of frames by the receiving station, the received frames each having an inter-arrival time differential and a inter-frame size differential, estimating an offset m_i of the inter-arrival time differential, detecting an available bandwidth over-use if the offset m_i is greater than a positive threshold, detecting an available bandwidth under-use if the offset m_i is less than a negative threshold, determining the estimated available bandwidth based on whether there is a detected over-use or under-use using a processor, and regulating the bitrate of the encoded media stream by sending the estimated available bandwidth to the transmitting station.

Included in the disclosed embodiments is a method for estimating available bandwidth for transmitting a media stream over a network, the media stream having a plurality of frames. The method includes receiving some of the plurality of frames, each frame of the plurality of frames having an inter-frame size differential and an inter-arrival time differential, detecting if at least some of the inter-arrival time differentials are outside of a steady-state range using at least some of the inter-frame size differentials, and estimating an available bandwidth based on the detection using a processor.

Included in the disclosed embodiments is a computing device for estimating available bandwidth for transmitting a media stream over a network, the media stream having a plurality of frames. The computing device includes a memory and a processor configured to execute instructions stored in the memory to: receive some of the plurality of frames, each frame of the plurality of frames having an inter-frame size differential and an inter-arrival time differential, detect whether at least some of the inter-arrival time differentials are outside of a steady-state range using at least some of the inter-frame size differentials, and estimate an available bandwidth based on the detection.

Included in the disclosed embodiments is a computing device for estimating available bandwidth for transmitting a media stream over a network, the media stream having a plurality of frames. The computing device includes a RTP receiver configured to receive frames of a media stream from a network, each frame having an inter-arrival time differential and an inter-frame size differential, an adaptive filter configured to determine an estimated function of inter-arrival time differential and inter-frame size differential for the received frames, the estimated function having a slope and an offset, an over-use detector configured to detect an over-use or under-use of the network based on a comparison between the offset and one or more pre-determined thresholds, and a remote rate-control configured to determine an estimated available bandwidth based on the detection of an over-use or under-use by the over-use detector.

These and other embodiments will be described in additional detail hereafter.

BRIEF DESCRIPTION OF THE DRAWINGS

The description herein makes reference to the accompanying drawings wherein like reference numerals refer to like parts throughout the several views, and wherein:

FIG. 1 is a schematic of a media encoding and decoding system;

FIG. 2 is a diagram of a video stream;

FIG. 3 is a diagram of a bandwidth estimating system within the media encoding and decoding system of FIG. 1;

FIG. 4 is a flow chart of a method of determining an estimated available bandwidth for transmitting an encoded video stream across a network by a receiving station;

FIG. 5 is an exemplary scatter plot illustrating the inter-arrival time differential and inter-frame size differential of received frames at a steady-state and an estimated function thereof;

FIG. 6 is an exemplary scatter plot illustrating the inter-arrival time differential and inter-frame size differential of received frames during an over-use condition and an estimated function thereof;

FIG. 7 is a state diagram of rate control states used within the method of FIG. 4; and

FIG. 8 is an exemplary graph illustrating the estimated offset, estimated available bandwidth, encoded video stream bitrate, and rate control state within the method of FIG. 4;

FIG. 9 is an exemplary plot illustrating the determination of the increase factor used to calculate the estimated available bandwidth during the increase rate control state; and

FIG. 10 is a flow chart of a method of regulating the bitrate of an encoded video stream by a transmitting station.

DETAILED DESCRIPTION

FIG. 1 is a diagram of an encoder and decoder system 10 for media streams. As used herein, a media stream can include a video stream, an audio stream, a combined video and audio stream, or any other multimedia bitstream. Any description herein related to a specific type of media stream, such as a video stream, can be also applied to other types of media streams.

An exemplary transmitting station 12 may be, for example, a computer having an internal configuration of hardware including a processor such as a central processing unit (CPU) 14 and a memory 16. CPU 14 can be a controller for controlling the operations of transmitting station 12. The CPU 14 is connected to memory 16 by, for example, a memory bus. Memory 16 may be random access memory (RAM) or any other suitable memory device. Memory 16 can store data and program instructions which are used by the CPU 14. Other suitable implementations of transmitting station 12 are possible.

A network 28 connects transmitting station 12 and a receiving station 30 for transmission of an encoded media stream. Specifically, the media stream can be encoded by an encoder in transmitting station 12 and the encoded media stream can be decoded by a decoder in receiving station 30. Network 28 may, for example, be the Internet, which is a packet-switched network. Network 28 may also be a local area network (LAN), wide area network (WAN), virtual private network (VPN), or any other means of transferring the media stream from transmitting station 12.

The transmission of the encoded media stream can be accomplished using a real-time protocol, such as the real-time transport protocol (RTP) standard as promulgated by the Internet Engineering Task Force (IETF). Control of the transmission can be accomplished using the real-time transport control protocol (RTCP) defined in the RTP standard. For example, the RTCP can allow a transmitting station and receiving station to share information regarding network congestion and available bandwidth.

In one implementation, network 28 can include multiple network segments. For example, a transmission through the Internet can be routed through multiple network segments using routers that connect the network segments. The routers direct the transmission through a network path of appropriate network segments so that the transmission reaches its intended destination. Each network segment in the network path has an available bandwidth A, modeled with a fluid traffic model as follows:
A—C—X; wherein   (1)
C is the network segment capacity (i.e. the segment's maximum bandwidth); and X is the amount of cross-traffic on the network segment (i.e. the portion of the capacity that is already used).

The available bandwidth of the network path can be no larger than the smallest available bandwidth A_min of all of the network segments within the network path. Correspondingly, the maximum bandwidth, or capacity, of the network path is equal to the network segment having the smallest capacity C_min. The network path's available bandwidth A_min and capacity C_min may change over time based on changing network conditions. For example, a network segment's performance may be degraded, reducing its capacity and the capacity of the network path. In another example, cross traffic over one of the network segments may reduce the available bandwidth of the network path.

The available bandwidth is the maximum data size per time period that the network is able to transmit. A bitrate is the size of an encoded media stream or other data over time. Both the bandwidth and the bitrate can be measured in bits or bytes per second.

If the media stream being transmitted has a bitrate greater than the available bandwidth, portions of the media stream will be queued within the network. The queuing can result in delayed receipt of portions of the media stream by the receiving station 30 or may result in portions of the media stream being lost during transmission. Lost portions of the media stream may be resent by the transmitting station 12, however, the resent portions can be significantly delayed—and in some cases, the resent portions can be lost as well.

Receiving station 30, in one example, can be a computer having an internal configuration of hardware including a processor such as a central processing unit (CPU) 32 and a memory 34. CPU 32 is a controller for controlling the operations of transmitting station 12. CPU 32 can be connected to memory 34 by, for example, a memory bus. Memory 34 can be RAM or any other suitable memory device. Memory 34 stores data and program instructions which are used by CPU 32. Other suitable implementations of receiving station 30 are possible.

A display 36 configured to display a video stream can be connected to receiving station 30. Display 36 may be implemented in various ways, including by a liquid crystal display (LCD) or a cathode-ray tube (CRT). The display 36 can be configured to display a rendering of a video stream decoded by the decoder in receiving station 30.

Other implementations of the encoder and decoder system 10 are possible. In one implementation, additional components may be added to the encoder and decoder system 10. For example, a display or a video camera may be attached to transmitting station 12 to capture a video stream to be encoded. In another implementation, a transport protocol other than RTP may be used.

FIG. 2 is a diagram of a typical video stream 50 to be encoded and decoded. Video coding formats, for example, VP8 or H.264, provide a defined hierarchy of layers for video stream 50. Video stream 50 includes a video sequence 52. At the next level, video sequence 52 consists of a number of adjacent frames 54, which can then be further subdivided into a single frame 56. At the next level, frame 56 can be divided into a series of blocks 58, which can contain data corresponding to, for example, a 16×16 block of displayed pixels in frame 56. Each block can contain luminance and chrominance data for the corresponding pixels. Blocks 58 can also be of any other suitable size such as 16×8 pixel groups or 8×16 pixel groups.

FIG. 3 is a diagram 70 of a bandwidth estimating system within the media encoding and decoding system of FIG. 1. Portions of the bandwidth estimating implementation are implemented on the transmitting station 12, receiving station 30, and network 28. The diagram 70 includes stages configured to encode and transmit a real-time video stream from the transmitting station 12 to receiving station 30. The diagram 70 also includes feedback stages for estimating bandwidth configured to regulate the bitrate of the encoded real-time video stream based on an estimated available bandwidth.

A video stream 72 is input into the system. Video encoding 74 encodes the input video stream. Video encoding 74 produces an encoded video stream ata particular bitrate. The encoding can be performed using techniques such as inter-frame prediction. In inter-frame prediction, some frames (usually called P-frames) are each encoded as a residual signal that is determined using a difference between the frame being encoded and a reference frame. The difference can be determined using techniques such as motion compensation. I-frames are intra-predicted frames, and are encoded without using other frames. I-frames are typically larger than frames that are not intra-predicted (i.e. P-frames).

A RTP sender 76 packages encoded frames into packets conforming to the RTP protocol for transport. The packaging includes setting a timestamp for a packaged frame based on either the capture time (the time at which the frame was captured by, for example, a video camera) or the send time (the time at which the frame is packaged and sent). Packaged frames are transmitted in a RTP stream 78 of RTP packets over the network 28.

A RTP receiver 80 receives the RTP packets in the RTP stream 78, unpackages the encoded video stream from the RTP packets and transfers the encoded video stream to video receiver 82. Video receiver 82 decodes and renders the encoded video stream.

After receiving a frame of the encoded video stream, RTP receiver 80 sends the timestamp, encoded frame size, and the actual receive time (the time at which the frame arrived at RTP receiver 80) to receive-side control 86. Receive-side control 86 is included in bandwidth estimator 84. Receive-side control 86 is configured to determine an estimated available bandwidth for the RTP stream 78. Receive-side control 86 includes an adaptive filter 88, over-use detector 90, and remote rate-control 92.

The adaptive filter 88 determines an estimated function based on data points of the inter-arrival time differential and the inter-frame size differential of at least some of the frames that have been previously received. The estimated function includes a slope and an offset. The adaptive filter 88 and the determined estimated function will be described in more detail later. The over-use detector 90 uses a comparison of the offset of the estimated function and one or more thresholds to determine whether there is a network over-use or under-use. The over-use detector 90 will be described in more detail later.

The remote rate-control 92 determines an estimated available bandwidth for transmitting the RTP stream 78 over the network. The estimated available bandwidth is calculated based on the detection of network over-use or under-use by over-use detector 90. The remote rate-control 92 will be described in more detail later.

Once the estimated available bandwidth is determined, RTCP sender 94 is used to send the estimated available bandwidth to the transmitting station 12 via RTCP messages 96. The estimated available bandwidth is received by RTCP receiver 98 in an RTCP message. The RTCP receiver 98 extracts the estimated available bandwidth and passes it to send-side control 100. The send-side control calculates a send-side estimated available bandwidth that is bounded by the estimated available bandwidth determined by the receive-side control 86 and a value determined using the TCP throughput equation that is a part of TCP Friendly Rate Control (TFRC), promulgated by the Internet Engineering Task Force (IETF).

The bandwidth estimating system described above is only one possible implementation of the bandwidth estimating system. Other implementations are possible, including those that modify, add, or delete aspects of the system shown in FIG. 3. For example, an alternative implementation may not use the RTP and RTCP protocols and may instead use a different protocol. In another implementation, the bandwidth estimation system can be modified to estimate available bandwidth for other media streams, such as an audio stream.

When the encoding and transmission of a video stream is initialized, the bitrate of the video stream can be set to be within an expected available bandwidth of the network. The expected available bandwidth can be, for example, pre-determined or determined by either the transmitting or receiving station. One exemplary method of determining the expected available bandwidth includes performing a probe of the network. In this method, a burst of packets is sent to the receiving station by the transmitting station. The receiving station can then measure the incoming bitrate of the burst of packets to determine the expected available bandwidth. Other methods can also be used.

The actual available bandwidth A_min may change over time, resulting in an under-use or an over-use of the available bandwidth A_min of the network. Bandwidth estimator 84 is used to determine the estimated available bandwidth so that the bitrate of the encoded video stream can be optimized to the available bandwidth of the network. The bitrate can be optimized so that the encoded video stream takes up a majority of the available bandwidth (allowing for a higher quality video, since higher quality video generally requires a higher bitrate) and without taking up more than the available bandwidth so that transmission loss is controlled.

FIG. 4 is a flow chart of a method 110 of determining an estimated available bandwidth for transmitting an encoded video stream across a network 28 by receiving station 30. In one implementation, the method is carried out by the receive-side control 86. First, at stage 112, the receive-side control 86 receives information about a received frame. The information includes the transmitting station timestamp (which is either the send time or the capture time of the frame), the actual receive time of the frame, the size of the frame, and the position of the frame within the video stream.

Next, at stage 114, an estimated function is determined using adaptive filter 88. The estimated function is based on the inter-arrival time differential d and the inter-frame size differential dL of at least some of the frames that have been previously received and includes an estimated slope and offset. Use of the inter-frame size differential dL allows for a more accurate offset than only using the inter-arrival time differential without respect to frame size. The inter-arrival time differential d_i of a frame i is the difference in network transmission time of successive frames in the video stream, as defined by this formula:
d_i=t_i−t_i−1−(T_i−T_i−1); wherein   (1)
t_i is the receive time of frame i; t_i−1 is the receive time of a frame i−1 that immediately precedes the current frame I; T_i is the timestamp (send time or capture time) of frame i; and T_i−1 is the timestamp of frame i−1.

The inter-frame size differential dL_i for a frame i is the difference in frame size of successive frames in the video stream, as defined by this formula:
dL_i=L_i—Li−1; wherein   (2)
L_i is the frame size of frame i; and L_i−1 is the frame size of frame i−1.

In one exemplary implementation, the estimated function is estimated using a Kalman filter. To utilize a Kalman filter, the process of transmitting frames over the network is modeled. For any frame i, a model D_i of inter-arrival time d_i can be defined using the following formula:

D i = d ⁢ ⁢ L i C min + w i ; wherein ( 3 )
w_i is a sample from a stochastic process W for frame i.

In formula (3), the stochastic process W is a function of the capacity C_min, the current cross traffic X_i, and the current video stream bitrate R_i. W is modeled as a white Gaussian process with a variance of σ_w². If the current video stream bitrate R_i exceeds the current available bandwidth A_min (over-use condition), then w_i will have a mean greater than zero. Alternatively, if the current video stream bitrate R_i is less than the current available bandwidth, then w_i can have a mean less than zero for limited periods of time. Sample w_i can have a mean less than zero during a time period which the network is recovering from a over-use condition (under-use condition).

If the current video stream bitrate R_i is equal to or less than the current available bandwidth A_min and the network is not recovering from an over-use condition (steady-state condition), then the mean of w_i will be zero. The mean of w_i can be split out from the noise portion of w_i using formula (3) as follows:

D i = 1 C min , i ⁢ d ⁢ ⁢ L i + m i + v i ; wherein ( 4 )
C_min,i is the capacity C_min as measured for frame i; m_i is the mean of w_i for frame i; and v_i is the noise portion of w_i for frame i.

The estimated function with respect to C_min,i⁻¹ and m_i is modeled in a form usable by the Kalman filter using matrix θ_i for frame i as follows:

θ _ i = [ C min , i - 1 m i ] ( 5 )

The next values of θ_i+1 for the next frame i+1 can be modeled as follows:
θ_i+i= θ_i+ū_i; wherein   (6)
ū_i is a zero-mean white Gaussian process noise having a model covariance Q_i defined as:

Q i = E ⁢ { u _ i ⁢ u _ i T } ; wherein ( 7 )
E(x) signifies the mathematical expectation of random variable x, which is a weighted average of all possible values of x.

The model D_i can be restated in terms of θ_i as follows:
D_i= h_i^T θ_i+v_i; wherein   (8)
h_i^T is the transpose of h_i, h_i being defined as:

h _ i = [ d ⁢ ⁢ L i 1 ] ( 9 )

The matrix θ_i of the model is restated as an estimate {circumflex over (θ)}_i, which will be the output from the Kalman filter. The estimate {circumflex over (θ)}_i, is defined as:

θ ^ i = [ C ^ min , i - 1 m ^ i ] ; wherein ( 10 )
Ĉ_min,1⁻¹ is the estimated slope (i.e. inverse capacity) as determined at frame i; and {circumflex over (m)}_i is the estimated offset at frame i.

The estimate {circumflex over (θ)}_i is determined using the Kalman filter using the following estimation formula:
{circumflex over (θ)}_i={circumflex over (θ)}_i−1+z_i K_i; wherein   (11)
{circumflex over (θ)}_i−1 is the estimate of the previous frame i−1;
z_i is the measurement value, defined as:
z_i=d_i− h_i^T{circumflex over (θ)}_i−1; and   (12)
K_i is the Kalman Gain, defined as:

K _ i = P i - 1 ⁢ h _ i σ ^ v , i 2 + h _ i T ⁢ P i - 1 ⁢ h _ i ; wherein ( 13 )
P_i−1 is the error covariance previously determined for the previous frame i−1, the error covariance P_i for any frame i being defined as:
P_i=(1− K_i h_i^T)P_i−1+{circumflex over (Q)}_i; wherein   (14)
{circumflex over (Q)}_i is an estimated covariance of the zero-mean white Gaussian process noise ū_i, {circumflex over (Q)}_i, defined as:

Q ^ i = [ 30 1000 ⁢ f max × 10 - 10 0 0 30 1000 ⁢ f max × 10 - 2 ] ; ( 15 )
{circumflex over (σ)}_v,i² is the variance of v measured at frame i, defined as:
{circumflex over (σ)}_v,i²=β{circumflex over (σ)}_v,i−1²+(1−β)z_i²; wherein   (16)
β is defined as:

β = ( 1 - α ) 30 1000 ⁢ f max ; wherein ( 17 )
α is a filter constant, typically chosen from within the interval [0.001,0.1]; and
f_max is the highest rate at which frames have been captured within the last N frames, defined as:

f max = max ⁢ { 1 T i - T i - 1 , 1 T i - 1 - T i - 2 , … ⁢ , 1 T i - N - T i - N - 1 } ( 18 )

As shown in formula (12), the measurement value z_i, is defined using the inter-arrival time differential d_i, the inter-frame size differential dL_i, and the previous estimate {circumflex over (θ)}_i−1. Formula (12) is defined with the assumption that v_iis a random variable with samples drawn from a zero-mean white Gaussian process. In some cases, that assumption may be incorrect, so an outlier filter is used with the determination of z_i. If z_iis greater than 3√{square root over ({circumflex over (σ)}_v,i² )}when using formula (12), the value of z_iis replaced with 3√{square root over ({circumflex over (σ)}_v,i²)}. If z_i is less than −3√{square root over ({circumflex over (σ)}_v,i² )}when using formula (12), the value of z_iis replaced with −3√{square root over ({circumflex over (σ)}_v,i² )}. In other words, 3√{square root over ({circumflex over (σ)}_v,i² )}is the maximum value of z_i and −3√{square root over ({circumflex over (σ)}_v,i² )}is the minimum value of z_i. Other outlier filters may alternatively be used.

The Kalman Gain K_i as defined in formula (13) is a gain vector. The gain vector includes gain values for each of

C ^ min , i - 1
and {circumflex over (m)}_i. The gain values dictate the response time of the Kalman filter to incorporate changes in the input values d_i and dL_i, into the estimated values. The gain values incorporate the error covariance P_i−1 determined for the previous frame i−1 and a noise variance {circumflex over (σ)}_v,i² calculated as of frame i.

The error covariance P_i is determined using an estimated covariance {circumflex over (Q)}_i. The estimated covariance {circumflex over (Q)}_i is a matrix of values approximating the model covariance Q_i. In this case, position (1,1) of the matrix contains the estimated variance of C_min,i and position (2,2) of the matrix contains the estimated variance of m_i. The values shown reflect a greater expected variance for the offset m_i than slope C_min,i. The values are proportional to the frame rate of the video stream, as measured by f_max.

The disparity in variances reflects an assumption that a change in bandwidth usage as represented by the offset m_i is much more likely than a change in network capacity as represented by C_min,i. However, different implementations and circumstances may require different assumptions and different values within estimated covariance {circumflex over (Q)}_i. For example, in the case of a mobile network, the network capacity may vary quickly as compared to other networks. As the expected underlying network conditions change, the values within estimated covariance {circumflex over (Q)}_i can be modified using, for example, an iterative analytical process.

The definition of variance {circumflex over (σ)}_v,i² and estimated covariance {circumflex over (Q)}_i parameters each include factor f_max that is used to scale the parameters relative to frame rate over time. This scaling factor is included so that the Kalman filter responds within a similar number of frames of the video stream, regardless of the frame rate currently being used. The dynamic nature of this factor enables the Kalman filter to respond to dynamic changes in the video stream frame rate that may occur during real-time video encoding.

The above formulas (5)-(18) illustrate an exemplary implementation of a Kalman filter to estimate the slope and offset of an estimated function of the inter-arrival time differential and the inter-frame size differential of received frames. Other Kalman filter implementations and variations on the exemplary implementation are available. For example, formulas may be added, changed or omitted in alternative implementations. Furthermore, in alternative implementations, a different type of adaptive filter other than a Kalman filter may be used.

FIG. 5 is an exemplary scatter plot 130 illustrating the inter-arrival time differential and inter-frame size differential of received frames and an estimated function 140 thereof. The scatter plot 130 includes a y-axis corresponding to the inter-arrival time differential d and an x-axis corresponding to the inter-frame size differential dL of received frames. Frames are plotted on the scatter plot 130 using their associated d and dL values, including frame 132.

The scatter plot 130 includes three areas of plotted frames. Area 134 includes most of the plotted frames and is distributed about the origin of the plot. Area 134 primarily includes inter-predicted P-frames that do not come immediately after an I-frame. Area 136 includes frames having a larger inter-frame size differential dL. Area 136 primarily includes I-frames, which are typically larger than other frames within a video stream. Frames in area 136 generally will have larger inter-arrival time values than frames in other areas since the relatively increased size of the frames requires a corresponding relative increase in network transmission time.

Area 138 includes frames that have a smaller frame size than the immediately preceding frame. For example, area 138 can include P-frames that come immediately after an I-frame, since P-frames are typically smaller than I-frames. Frames in area 138 require relatively less network transmission time than the immediately preceding frame due to their relatively smaller size.

Estimated function 140 is an estimated function of the plotted frames. Estimated function 140 can be determined using a Kalman filter or other method as described above. In this example, the estimated function 140 has a zero-offset, showing the network in a steady-state condition.

Referring back to FIG. 4, at stage 116, network over-use or under-use is detected using over-use detector 90. The over-use detector 90 detects whether the network is in a steady-state, under-use, or over-use condition. The over-use detector 90 performs this detection based on the estimated offset {circumflex over (m)}_i, an over-use threshold γ₁, and an under-use threshold −γ₁. In other implementations, the over-use threshold and under-use threshold may be separately pre-determined.

An over-use indication exists when {circumflex over (m)}_i>γ₁, an under-use indication exists when {circumflex over (m)}_i<−γ₁ and otherwise, the network is in steady-state. However, an over-use or under-use is only detected by the over-use detector 90 if the associated indication is maintained for γ₂ milliseconds and γ₃ frames. This requirement filters out what would be false detections caused by brief spikes in offset {circumflex over (m)}_i. Alternative implementations may filter the over-use and under-use detection differently. In one example, an over-use or under-use is detected when one of γ₂ milliseconds or γ₃ frames is reached while an indication is maintained. In another example, there may be no filter, and an over-use or under-use is detected immediately once there is an over-use or under-use indication.

FIG. 6 is an exemplary scatter plot 150 illustrating the inter-arrival time differential and inter-frame size differential of received frames during an over-use condition and an updated estimated function 158 thereof. Scatter plot 150 is based on the plot 130 and also includes additional received frames 156, such as additional received frame 155. Scatter plot 150 includes plotted frames, such as frame 132 and illustrates estimated function 140 from plot 130 showing the previous steady-state condition. Updated estimated function 158 is an estimated function of the plotted frames including the additional received frames 156.

The additional received frames 156 have an increased inter-arrival time differential as compared to the previously received frames shown in plot 130. The increased inter-arrival time differentials results in a positive offset 160 in the estimated function 158. The positive offset 160 can result in an indication of over-use if the positive offset 160 value is greater than the threshold value.

Referring back to FIG. 4, at stage 118, the rate control state is determined and the estimated available bandwidth is determined. The method includes three rate control states: increase, decrease, and hold. The rate control state is used to determine the methodology used to determine the estimated available bandwidth.

FIG. 7 is a state diagram 170 of rate control states used within the method of FIG. 4. At the beginning of a video stream, the rate control state is initialized to the increase state 172. The estimated available bandwidth is increased when the rate control state is increase state 172. The rate control state can then transition to the decrease state 176 once an over-use condition is detected. The estimated available bandwidth is decreased when the rate control state is decrease state 176.

The rate control state then transitions to the hold state 180 once an under-use condition is detected. The estimated available bandwidth is maintained at a same value once the rate control state is set to hold state 180. Once the under-use condition ends, the rate control state transitions to increase state 172. The rate control state can transition back to hold state 180 from increase state 172 if another under-use condition is detected.

The rate control states and transitions described above are exemplary and may be different in some implementations. For example, the rate control state can be configured to transition from decrease state 176 to increase state 172, for example, after a certain amount of time has passed after an over-use condition ends and an under-use condition has not yet begun. Depending on the thresholds chosen to detect over-use and under-use, this may happen if there is a mild over-use of the network that does not cause a subsequent under-use.

In another example, the rate control state can be configured to transition to a temporary hold state similar to hold state 180 once an over-use or under-use is indicated but not yet detected. For example, if an over-use is indicated, the estimated available bandwidth will be held at a same value either until the over-use is detected (at which time the state would change to decrease state 176). Alternatively, if an under-use is indicated, the estimated available bandwidth will be held at a same value either until the under-use is detected (at which time the state would change to hold state 180).

FIG. 8 is an exemplary graph 200 illustrating the estimated offset, estimated available bandwidth, encoded video stream bitrate, and rate control state within the method of FIG. 4. The graph 200 includes an estimated offset plot 202, an encoded video stream bitrate plot 204, and an estimated available bandwidth plot 206. As explained previously, the rate control state starts in the increase state 172. The increase state is maintained for an initial increase state time period 208. During time period 208, the estimated available bandwidth Â_i is increased, and an encoded video stream bitrate R_i is shown to increase as a result of the increase of estimated available bandwidth Â_i. In this example, the estimated available bandwidth Â_i is maintained at a same value in a temporary hold state once an over-use is indicated at point 212. The estimated available bandwidth Â_i is increased using this formula:
Â_i=ηÂ_i−1; wherein   (19)
Â_i−1 is the previously determined estimated available bandwidth for the previous frame i−1; and η is an increase factor, defined using the function:

η ⁡ ( T r , i , σ ^ v , i 2 ) = 1.001 + B 1 + ⅇ q ⁡ ( r · T r , i - ( c 1 ⁢ σ ^ v , i 2 + c 2 ) ) ; wherein ( 20 )
T_t,i is the round-trip time at frame i; B is a pre-determined constant; q is a pre-determined constant; r is a pre-determined constant; c₁ is a pre-determined constant; and c₂ is a pre-determined constant.

FIG. 9 is an exemplary plot illustrating the determination of the increase factor η used to calculate the estimated available bandwidth Â_i during the increase rate control state. Exemplary plot 250 is a three-dimensional plot having axes for T_r,i, {circumflex over (σ)}_v,i², and η. In this implementation of the increase factor η, the values of η are based on the input values shown and these values selected for the pre-determined constants: B=0.0407, q=0.0025, r=0.85, c₁=−6.1524, and c₂=800. However, alternative values for the pre-determined constants may be used. Additionally, alternative formulas may be used to obtain the value of η. The range of values for η in some implementations may be different than the range shown.

Referring back now to FIG. 8, other implementations may increase the estimated available bandwidth Â_i in alternative ways. For example, Â_i can be increased using formula 19 with an offset. Alternatively, Â_i can be increased using any function of Â_i−1.

The increase of the estimated available bandwidth Â_i as shown above relies on an eventual over-use of the network to trigger a change to the decrease state 176. The encoded video stream bitrate R_i is a measurement of the video stream bitrate as it is arriving at the receiving station. In some cases, the estimated available bandwidth Â_i may increase to a value that exceeds a maximum bitrate that the transmitting station can encode for the video stream. To avoid divergence between the encoded video stream bitrate R_i and the estimated available bandwidth Â_i, Â_i is limited to a maximum value in this case, as shown by this formula:
Â_i=max(Â_i, 1.5R_i) ; wherein   (21)
R_i is measured using the formula:

R i = 1 t ⁢ ∑ j = 0 N t - 1 ⁢ L i - j ; wherein ( 22 )
t is a number of seconds defining the time window over which R_i will be measured; N_t is a number of frames received within t seconds of receipt of frame i; and L_i-j is the frame size of frame i-j.

At a first transition time 210, the rate control state changes to decrease state 176. The rate control state change is triggered by the estimated offset plot 202 exceeding the over-use threshold γ₁ at point 212 and maintaining above the over-use threshold γ₁ for an over-use threshold period 214. Over-use threshold period 214 can be defined based on a pre-determined number of seconds (γ₂ milliseconds), pre-determined number of frames (γ₃ frames), or both. The decrease state 176 is maintained for a decrease time period 216.

In this example, the decrease time period 216 includes a temporary hold state at the end of the period once an under-use is indicated at point 220. The plot 202 reflects a sudden change from an over-use condition to an under-use condition. In other examples and where there is not a sudden change, the decrease time period 216 may end once the over-use condition ends. In such a case, the estimated available bandwidth is decreased during decrease state 176. The estimated available bandwidth is decreased using the formula:
Â_i=αR_i; wherein   (23)
α is an fraction that is chosen from within an interval [0.8,0.95].

In some implementations, α can alternatively be chosen from outside of the stated interval.

At a second transition time 218, the rate control state changes to hold state 180. The rate control state change is triggered by the estimated offset plot 202 decreasing below the under-use threshold −γ₁ for an under-use threshold period 222. Under-use threshold period 222 can be defined based on γ₂ milliseconds, γ₃ frames, or both. Under-use threshold period 222 may alternatively use different values than those used to define over-use threshold period 214. The hold state is maintained for a hold time period 224. The hold time period 224 starts at second transition time 218 and ends when estimated offset plot 202 crosses above the under-use threshold. During the hold time period 224, estimated available bandwidth plot 206 is maintained at a same value. The encoded video stream bitrate plot 204 can fluctuate during this time as queued frames within the network are transmitted.

At a third transition time 226, the rate control state changes back to increase state 172. The estimated available bandwidth plot 206 is reset at the third transition time 226 based on the maximum encoded video stream bitrate R_max,i 228 during the hold time period 224. The determination of the estimated available bandwidth at the end of the hold time period 224 is defined in this formula:
Â_i=R_max,i =max{R_i,R_i−1, . . . , R_i−k}; wherein   (24)
k is the number of frames within the hold time period.

The R_max,i value is used to reset the estimated available bandwidth based on the premise that the actual available bandwidth will be equal to or greater than the maximum bitrate observed during the hold time period 224. The increase state 172 is then maintained for the remainder of the graph for a final increase time period 230. The next state after increase state 172 can be either hold state 180 or decrease state 176 depending on whether an under-use or an over-use condition is next detected.

Referring back to FIG. 4, once the estimated available bandwidth Â_i is determined as of frame i, it is sent to the transmitting station 12 in stage 120. Â_i can be sent via RTCP to the transmitting station 12 using RTCP sender 94 and RTCP messages 96. Â_i can be determined and sent at the same rate as the video stream or at a slower rate, for example, five times per second. Alternatively, Â_i can be determined for each frame, but transmitted as an aggregate for groups of frames at a lower rate than the frame rate. After Â_i is sent, method 110 ends.

FIG. 10 is a flow chart of a method 260 of regulating the bitrate of an encoded video stream by a transmitting station. In one implementation, the method is carried out by the send-side control 100. At stage 262, the receive-side estimated available bandwidth Â_i is received from the receiving station. The receiving can be done using RTCP messages 96 and RTCP receiver 98.

At stage 264, a send-side estimated available bandwidth Â_i^s is determined using the following formulas:
Â_i^s=1.05Â_i−1^s+1000, if p<2% ;   (25)
Â_i^s=Â_i−1^s, if 2% ≦p≦10%; and   (26)
Â_i^s=Â_i−1^s(1−0.5p), if p>10% ; wherein   (27)
Â_i−1^s is the send-side estimated available bandwidth for frame i−1; and
p is a measure of packet loss

The packet loss p is measured over the time between the current receipt of receive-side estimated available bandwidth Â_i and the last receipt of a receive-side estimated available bandwidth. The last receipt of the receive-side estimated available bandwidth may have occurred be one or more frames in the past. If the packet loss is less than two percent, the send-side estimated available bandwidth Â_i^s is increased relative to the last send-side estimated available bandwidth Â_i−1^s . If the packet loss is between two and ten percent, the send-side estimated available bandwidth Â_i^s is maintained at its previous value Â_i−1^s . If the packet loss is greater than ten percent, the send-side estimated available bandwidth Â_i^s is decreased from its previous value Â_i−1^s proportionately to the packet loss.

Alternatively, the determination of whether to use formula 25, 26, or 27 to determine the send-side estimated available bandwidth may be based on one or more pre-determined packet loss thresholds. For example an upper packet loss threshold may be used in place of the constant 10% value and a lower packet loss threshold may be used in place of the constant 2% value.

The send-side estimated available bandwidth Â_i^s is limited such that it does not exceed the receive-side estimated available bandwidth Â_i. It is further limited such that it is equal to or greater than a bandwidth calculated using the using the TCP throughput equation that is a part of the TCP Friendly Rate Control (TFRC) specification. The formulas for both limitations are defined below:
Â_i^s=min(Â_i,Â_i^s); and   (28)

A ^ i S = max ( A ^ i S , 8 ⁢ ⁢ s R ⁢ 2 ⁢ ⁢ bp 3 + ( 3 ⁢ ⁢ t RTO ⁡ ( 1 + 32 ⁢ ⁢ p 2 ) ⁢ p ⁢ 3 ⁢ ⁢ bp 8 ) ) ; wherein ( 29 )
s is an average packet size in bytes; R is a network round-trip time; b is a number of packets acknowledged by a single TCP acknowledgement; and t_RTO is the TCP retransmission timeout value in seconds.

Once the send-side estimated available bandwidth is determined and limited, at stage 266 the transmitting station encodes frames at a bitrate based on the send-side estimated available bandwidth using video encoding 74.

The above-described embodiments of encoding or decoding may illustrate some exemplary encoding techniques. However, in general, encoding and decoding as those terms are used in the claims are understood to mean compression, decompression, transformation or any other change to data whatsoever.

The embodiments of transmitting station 12 and/or receiving station 30 (and the algorithms, methods, instructions etc. stored thereon and/or executed thereby) can be realized in hardware, software, or any combination thereof including, for example, IP cores, ASICS, programmable logic arrays, optical processors, programmable logic controllers, microcode, firmware, microcontrollers, servers, microprocessors, digital signal processors or any other suitable circuit. In the claims, the term “processor” should be understood as encompassing any the foregoing, either singly or in combination. The terms “signal” and “data” are used interchangeably. Further, portions of transmitting station 12 and receiving station 30 do not necessarily have to be implemented in the same manner.

Further, in one embodiment, for example, transmitting station 12 or receiving station 30 can be implemented using a general purpose computer/processor with a computer program that, when executed, carries out any of the respective methods, algorithms and/or instructions described herein. In addition or alternatively, for example, a special purpose computer/processor can be utilized which can contain specialized hardware for carrying out any of the methods, algorithms, or instructions described herein.

Transmitting station 12 and receiving station 30 can, for example, be implemented on computers in a screencasting or a videoconferencing system. Alternatively, transmitting station 12 can be implemented on a server and receiving station 30 can be implemented on a device separate from the server, such as a hand-held communications device (i.e. a cell phone). In this instance, transmitting station 12 can encode content using an encoder into an encoded video signal and transmit the encoded video signal to the communications device. In turn, the communications device can then decode the encoded video signal using a decoder. Alternatively, the communications device can decode content stored locally on the communications device (i.e. no transmission is necessary). Other suitable transmitting station 12 and receiving station 30 implementation schemes are available. For example, receiving station 30 can be a personal computer rather than a portable communications device.

Further, all or a portion of embodiments of the present invention can take the form of a computer program product accessible from, for example, a computer-usable or computer-readable medium. A computer-usable or computer-readable medium can be any device that can, for example, tangibly contain, store, communicate, or transport the program for use by or in connection with any processor. The medium can be, for example, an electronic, magnetic, optical, electromagnetic, or a semiconductor device. Other suitable mediums are also available.

The above-described embodiments have been described in order to allow easy understanding of the present invention and do not limit the present invention. On the contrary, the invention is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims, which scope is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structure as is permitted under the law.