Apparatus and method for media transmission bandwidth control using bandwidth estimation

• US 9,106,787 B1
• Filed: 05/09/2011
• Issued: 08/11/2015
• Est. Priority Date: 05/09/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Holmer, Stefan, Fahlberg Lundin, Henrik
• Primary Examiner(s): Bailey, Frederick
• Assistant Examiner(s): Mahmud, Farhan
• Application Number:
  US13/103,181
• Time in Patent Office: 1,555 Days
• Field of Search: 375/240.01, 370/252
• US Class Current: 1/1
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence
• 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 7/12 Systems in which the television signal is transmitted via one channel or a plurality of parallel channels, the bandwidth of each channel being less than the bandwidth of the television signal H04N7/24 takes precedence

Abstract

A system, apparatus, and method for estimating available bandwidth for transmitting a media stream over a network, the media stream having a plurality of frames. One method includes receiving some of the plurality of frames, each frame of the plurality of frames having a inter-frame size differential and an inter-arrival time differential, detecting 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 estimating an available bandwidth based on the detected change and using a processor.

Claims

1. A method for determining, by a receiving station, an estimated available bandwidth for transmitting a media stream over a network from a transmitting station to the receiving station, the method comprising:

receiving a plurality of frames from the media stream at the receiving station;

determining an inter-arrival time differential d for each frame from the plurality of frames, the inter-arrival time differential d_i, for a current frame i calculated as the difference between a network transmission time of the current frame i and a network transmission time of a previous frame i-1 according to d_i=(t_i−

t_i-1)−

(T_i−

T_i-1), wherein

t_i, is a receive time, at the receiving station, of the current frame i,

t<sub>i−

1</sub> is a receive time, at the receiving station, of the previous frame i-1 that immediately precedes the current frame i,

T_i, is a timestamp of the current frame i, and

T<sub>i−

1</sub> is a timestamp of the previous frame i-1;

determining an inter-frame size differential dL for each frame from the plurality of frames, the inter-frame size differential dL_i, for the 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 according to dL_i=L_i−

L<sub>i−

1</sub>, wherein

L_iis the frame size of frame i, and

L<sub>i−

1</sub> is the frame size of frame i-1;

determining an estimated function by an adaptive filter that uses the inter-arrival time differential d for each frame from the plurality of frames and the inter-frame size differential dL for each frame from the plurality of frames as inputs, the estimated function having a slope C_i<sup>−

1</sup> and an offset m_i, wherein the slope C_i<sup>−

1</sup> represents an inverse capacity of the network with respect to the plurality of frames and the offset m_i represents a deviation from a steady-state condition with respect to the plurality of frames; and

determining the estimated available bandwidth based on a comparison between the offset m_i and one or more thresholds.

2. The method of claim 1, wherein determining the estimated available bandwidth comprises:

determining the estimated available bandwidth by increasing a previously determined estimated available bandwidth if a network over-use has not yet been detected during transmission of the media stream.

3. The method of claim 2, wherein determining the estimated available bandwidth further comprises:

detecting a network over-use if the offset m_i exceeds an over-use threshold for at least one of a first pre-determined number of seconds or a first pre-determined number of frames; and

determining the estimated available bandwidth based on a fraction of a bitrate of the media stream when the network over-use is detected.

4. The method of claim 3, wherein determining the estimated available bandwidth further comprises:

detecting a network under-use if the offset m_i is less than an under-use threshold for at least one of a second pre-determined number of seconds or a second pre-determined number of frames; and

determining the estimated available bandwidth as equal to the previously determined estimated available bandwidth.

5. The method of claim 4, wherein determining the estimated available bandwidth further comprises:

detecting a return to a steady-state range from a previously detected network under-use when the offset m_i exceeds the under-use threshold; and

determining the estimated available bandwidth as a maximum bitrate of the media stream measured during the previously detected network under-use.

6. The method of claim 5, wherein determining the estimated available bandwidth further comprises:

determining the estimated available bandwidth by increasing a previously determined estimated bandwidth if the return to the steady-state range was previously detected.

7. The method of claim 6, wherein determining the estimated available bandwidth further comprises:

limiting the determined estimated available bandwidth to a maximum value equal to 150% of the bitrate of the media stream.

8. The method of claim 1, further comprising:

sending the determined estimated available bandwidth to a transmitting station.

9. The method of claim 8, further comprising:

updating the determined estimated available bandwidth based on a measure of packets lost while transmitting the media stream.

10. The method of claim 9, wherein updating the determined estimated available bandwidth comprises:

determining a send-side estimated available bandwidth based on a previously determined send-side estimated available bandwidth, wherein;

the send-side estimated available bandwidth is an increase of the previously determined send-side estimated available bandwidth if the measure of packets lost is less than a first packet loss threshold,

the send-side estimated available bandwidth is a decrease of the previously determined send-side estimated available bandwidth if the measure of packets lost is greater than a second packet loss threshold, and

the send-side estimated available bandwidth is otherwise equal to the previously determined send-side estimated available bandwidth; and

updating the determined estimated available bandwidth as the send-side estimated available bandwidth, the updated estimated available bandwidth limited by at least one of an upper bound equal to the determined estimated available bandwidth or a lower bound defined using TCP Friendly Rate Control.

11. The method of claim 10, further comprising:

determining a target bitrate using the updated estimated available bandwidth; and

encoding the media stream using the target bitrate before transmitting the media stream.

12. The method of claim 1, wherein the media stream is transmitted over the network using RTP and the determined estimated available bandwidth is sent using RTCP.

13. A method of regulating a bitrate of a media stream encoded by a transmitting station based on an estimated available bandwidth of a network determined by a receiving station, the method comprising:

receiving a plurality of frames from the media stream by the receiving station, the plurality of frames each having an inter-arrival time differential d_i and an inter-frame size differential dL_i, the inter-arrival time for each frame given by d_i=(t_i−

t<sub>i−

1</sub>)−

(T_i−

T<sub>i−

1</sub>), wherein

t_i is a receive time of a current frame i,

t<sub>i−

1</sub> is a receive time of the previous frame i-1 that immediately precedes the current frame i,

T_i is a timestamp of the current frame i, and

T<sub>i−

1</sub> is a timestamp of the previous frame i-1, and

the inter-frame size differential for each frame given by dL_i=L_i−

L<sub>i−

1</sub>, wherein

L_i is the frame size of frame i, and

L_i−

is the frame size of frame i-1;

estimating a relationship between the inter-arrival time differential and the inter-frame size differential by an adaptive filter that uses the inter-arrival time differential d_i for each frame from the plurality of frames and the inter-frame size differential dL_i for each frame from the plurality of frames as inputs and determines a function having a slope C_i<sup>−

1</sup> and an offset m_i wherein the slope C_i<sup>−

1</sup> represents an inverse capacity of the network with respect to the plurality of frames and the offset m_i represents a deviation from a steady-state condition with respect to the plurality of frames;

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.

14. The method of claim 13, wherein determining the estimated available bandwidth comprises:

determining the estimated available bandwidth based on an increase of a previously determined estimated available bandwidth if neither an over-use or an under-use is detected.

15. The method of claim 13, wherein determining the estimated available bandwidth comprises:

determining the estimated available bandwidth based on a decrease of a bitrate of the transmitted media stream if an over-use is detected or if an over-use was previously detected and an under-use has not been detected after the over-use detection.

16. The method of claim 13, wherein determining the estimated available bandwidth comprises:

determining the estimated available bandwidth by maintaining the estimated available bandwidth at a constant value if an under-use is detected, the constant value defined as an estimated available bandwidth previously determined just prior to the under-use detection.

17. The method of claim 13, wherein regulating the bitrate of the encoded media stream comprises:

sending the estimated available bandwidth to the transmitting station;

determining a bitrate for encoding at least some subsequent frames of the media stream using the estimated available bandwidth; and

encoding the at least some subsequent frames of the media stream using the determined bitrate.

18. A method for estimating, at a receiving station, available bandwidth for transmitting a media stream over a network from a transmitting station to the receiving station, the method comprising:

receiving a plurality of frames from the media stream at the receiving station, each frame of the plurality of frames having an inter-frame size differential dL_i and an inter-arrival time differential d_i, the inter-arrival time for each frame given by d_i=(t_i−

t<sub>i−

1</sub>)−

(T_i−

T<sub>i−

1</sub>) , wherein

t_i is a receive time, at the receiving station, of a current frame i,

t<sub>i−

1</sub> is a receive time, at the receiving station, of the previous frame i-1 that immediately precedes the current frame i,

T_i, is a timestamp of the current frame i, and

T<sub>i−

1</sub> is a timestamp of the previous frame i-1, and the inter-frame size differential for each frame given by dL_i=L_i−

L<sub>i−

1</sub>, wherein

L_i is the frame size of frame i, and

L<sub>i−

1</sub> is the frame size of frame i-1;

determining an estimated function by an adaptive filter that uses the inter-arrival time differential for each frame from the plurality of frames and the inter-frame size differential for each frame from the plurality of frames as inputs, the estimated function having a slope C_i<sup>−

1</sup> and an offset m_i, wherein the slope C_i<sup>−

1</sup> represents an inverse capacity of the network with respect to the plurality of frames and the offset m_i represents a deviation from a steady-state condition with respect to the plurality of frames;

determining a steady-state range using the slope C_i<sup>−

1</sup> of the estimated function and at least one pre-determined threshold value;

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.

19. The method of claim 18, wherein estimating the available bandwidth comprises:

if the estimated function is within the steady-state range;

identifying a previously estimated available bandwidth, and

estimating the available bandwidth by increasing the previously estimated available bandwidth.

20. The method of claim 18, wherein estimating the available bandwidth comprises:

if the estimated function is greater than the steady-state range;

identifying a bitrate of the media stream, and

estimating the available bandwidth as a percentage of the bitrate.

21. The method of claim 18, wherein estimating the available bandwidth comprises:

if the estimated function is less than the steady-state range;

identifying a previously estimated available bandwidth, and

estimating the available bandwidth as the previously estimated available bandwidth.

22. A computing device for estimating available bandwidth for transmitting a media stream over a network, the computing device comprising:

a memory; and

a processor configured to execute instructions stored in the memory to;

receive a plurality of frames from the media stream, each frame of the plurality of frames having an inter-frame size differential dL_i and an inter-arrival time differential d_i, the inter-arrival time for each frame given by d_i=(t_i−

t<sub>i−

1</sub>)−

(T_i−

T<sub>i−

1</sub>) , wherein

t_i is a receive time of a current frame i,

t<sub>i−

1</sub> is a receive time of the previous frame i-1 that immediately precedes the current frame i,

T_i is a timestamp of the current frame i, and

T_i−

is a timestamp of the previous frame i-1, and

the inter-frame size differential for each frame given by dL_i =L_i−

L<sub>i−

1</sub>, wherein

L_i is the frame size of frame i, and

L<sub>i−

1</sub> is the frame size of frame i-1;

determine an estimated function by an adaptive filter that uses the inter-arrival time differential d for each frame from the plurality of frames and the inter-frame size differential dL for each frame from the plurality of frames as inputs, the estimated function having a slope C_i<sup>−

1</sup> and an offset m_i, wherein the slope C_i<sup>−

1</sup> represents an inverse capacity of the network with respect to the plurality of frames and the offset m_i represents a deviation from a steady-state condition with respect to the plurality of frames;

determine a steady-state range using the slope C_i<sup>−

1</sup> of the estimated function and at least one pre-determined threshold value;

detect whether at least some of the inter-arrival time differentials are outside of the steady-state range using at least some of the inter-frame size differentials; and

estimate an available bandwidth based on the detection.

23. A computing device for estimating available bandwidth for transmitting a media stream over a network, the computing device comprising:

an RTP receiver configured to receive a plurality of frames from the media stream over the network, each frame having an inter-arrival time differential d_i and an inter-frame size differential dL_i, the inter-arrival time for each frame given by d_i=(t_i−

t<sub>i−

1</sub>)−

(T_i−

T<sub>i−

1</sub>) , wherein

t_i is a receive time of a current frame i,

t<sub>i−

1</sub> is a receive time of the previous frame i-1 that immediately precedes the current frame i,

T_i is a timestamp of the current frame i, and

T<sub>i−

1</sub> is a timestamp of the previous frame i-1, and

the inter-frame size differential for each frame given by dL_i=L_i−

L<sub>i−

1</sub>, wherein

L_i is the frame size of frame i, and

L<sub>i−

1</sub> is the frame size of frame i-1;

an adaptive filter configured to determine an estimated function of a relationship between the inter-arrival time differential and the inter-frame size differential based on inter-arrival time differential and inter-frame size differential for the plurality of 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.

24. The computing device of claim 23, wherein the slope of the estimated function represents an inverse capacity of the network with respect to the plurality of frames and the offset represents a deviation from a steady-state condition with respect to the plurality of frames.