Patent Description:
Voice over IP (Internet Protocol) corresponds to technologies that permit audio streams to be transmitted over IP networks, such as the internet. Similar technologies can be used to transmit video streams. The audio and/or video streams are transmitted as packets using a transport layer protocol such as RTP (realtime transport protocol), and may pass through various transmission mediums, such as wired or wireless connections, and through network hardware such as routers.

Network congestion occurs when one or more elements in the network, such as one or more routers, receive a higher bitrate than they are capable of handling. This leads to packets being queued then dropped, and degrading the quality of the transmitted audio and/or video stream. Once network congestion has been identified, a solution for improving performance is to reduce the packet transmission bitrate over the network, thereby reducing packet loss.

However, there is a technical difficulty in detecting the presence of congestion in a network. Indeed, a relatively high level of lost packets itself is not a good indication of congestion as there can be other reasons for packets being lost, such as the wireless network interfaces, and Ethernet packet collisions. In such a case, reducing the transmission rate will not improve the packet loss rate. Furthermore, depending on the bitrate of streams being transmitted and the design of a router through which the streams pass, the router may retain packets for several tenths of a second before deciding to transmit them or to drop them. Thus the occurrence of lost packets is a very belated symptom of congestion.

There is thus a need in the art for a method and circuit for detecting network congestion.

French patent application published as <CIT> relates to a synchronisation source for transmitting synchronisation information by a packet network.

International patent application published as <CIT> relates to a method and arrangement for employing media layer adaptation in a wireless communication of media in data packets from a sending node to a receiving node.

It is an aim of embodiments of the present description to at least partially address one or more problems in the prior art.

According to one aspect, there is provided a method for detecting congestion in a packet-switched network comprising: estimating, by a receiver, a transmission clock rate of one or more packets of a media stream received by the receiver, each packet comprising a timestamp generated based on the transmission clock rate, the transmission clock rate being estimated based on the timing of a plurality n of received packets and the timestamps associated with said n packets and estimating the transmission clock rate comprises estimating a clock rate ratio between the transmission clock rate and the clock rate at the receiver based on the following model of the reception time tk of a packet k: <MAT> where Tk is the clock used to generate the timestamp, and Oe is an estimate of an origin value of the timestamps, and the reception time tk is predicted using an adaptive filtering technique based on a recursive least squares algorithm or on a Kalman filter algorithm; comparing the estimated transmission clock rate with a threshold; and detecting congestion in the network based on said comparison.

According to one embodiment, estimating the transmission clock rate is performed in response to the reception of each packet of the media stream received by the receiver.

According to one embodiment, the threshold is a fixed level.

According to one embodiment, the threshold is calculated based on an average of a plurality of previous estimates of the transmission clock rate.

According to one embodiment, the method further comprises, in response to detecting congestion: estimating available bandwidth based on at least a detected bitrate of the media stream; and transmitting a first bitrate limitation request to a transmitter transmitting the media stream to request that the transmission bitrate is reduced.

According to one embodiment, the first bitrate limitation request is to reduce the bitrate to a level of between <NUM> and <NUM> percent lower than the estimated available bandwidth.

According to one embodiment, the method further comprises: calculating, by the receiver, a new estimate of the transmission clock rate based on one or more further packets received after transmission of the first bitrate limitation request; and determining from the new estimate that the network is no longer congested, and in response transmitting to the transmitter a second bitrate limitation request.

According to one embodiment, the second bitrate limitation request is to increase the bitrate to a level of between <NUM> and <NUM> percent lower than the estimated available bandwidth.

According to a further aspect, there is provided a receiver for receiving a media stream transmitted over a packet-switched network, the receiver being configured to: estimate a transmission clock rate of one or more packets of a media stream received by the receiver, each packet comprising a timestamp generated based on the transmission clock rate, the transmission clock rate being estimated based on the timing of a plurality n of received packets and the timestamps associated with said n packets and the receiver is configured to estimate the transmission clock rate by estimating a clock rate ratio between the transmission clock rate and the clock rate at the receiver based on the following model of the reception time tk of a packet k: <MAT> where Tk is the clock used to generate the timestamp, and Oe is an estimate of an origin value of the timestamps, and the reception time tk is predicted using an adaptive filtering technique based on a recursive least squares algorithm or on a Kalman filter algorithm; compare the estimated transmission clock rate with a threshold; and detect congestion in the network based on said comparison.

The foregoing and other features and advantages will become apparent from the following detailed description of embodiments, given by way of illustration and not limitation with reference to the accompanying drawings, in which:.

Throughout the following description, example embodiments are described based on packet transmission using RTP Realtime Transport Protocol), for example defined in the standard IETF RFC3550. However, it will be apparent to those skilled in the art that the techniques described herein could be applied to other packet transmission protocols. The term "around" is used herein to designate a range of +/- <NUM> percent of the value in question.

<FIG> schematically illustrates a packet transmission system <NUM> according to an example embodiment. The system <NUM> comprises a transmitter (TRANSMITTER) <NUM> and a receiver (RECEIVER) <NUM> coupled via a network (NETWORK) <NUM> represented by a cloud. The transmitter <NUM> is capable of transmitting an audio and/or video stream to the receiver <NUM> via the network <NUM>. Throughout the following description, the term "media stream" will be used to designate a stream comprising packets of audio and/or video data. Of course, the transmitter <NUM> may also be capable of receiving a media stream from the receiver <NUM>, but for ease of description, communications in only one direction will be described herein.

The transmitter <NUM> and receiver <NUM> are each for example communications devices, such as mobile telephones, smart phones, tablet or laptop computers, or the like, adapted to communicate with the network <NUM> via one or more wired or wireless links. Alternatively, each of the transmitter <NUM> and receiver <NUM> could be a laptop computer or personal computer (PC) coupled to the network <NUM> via a wired network such as a LAN (local area network) or via a wireless network such as a wireless LAN.

The network <NUM> is for example a packet-switched network, for example comprising the internet, and includes routers for directing packets through the network, as known by those skilled in the art.

In some embodiments, the transmitter <NUM> is adapted to transmit the media stream to the receiver <NUM> in the form of packets using a transport layer protocol such as RTP. The effective transmission bitrate, in other words the rate at which data is successfully transmitted over the network, is a function of the transmission bitrate, the latency between the end points, and the packet loss rate.

<FIG> schematically illustrates part of the receiver <NUM> of <FIG> in more detail according to an example embodiment. The receiver <NUM> for example comprises an input interface (I/P) <NUM> for receiving packets from the network <NUM>, and for providing suitable demodulation and conversion, depending on the particular transmission interface via which the packets are received.

An output of the input interface <NUM> is coupled to a timing analysis module (TIMING ANALYSIS) <NUM>, which for example provides estimates Re of a transmission clock rate of the transmitted data, as described in more detail below. The transmission clock rate for example corresponds to the rate at which a timestamp of each packet is incremented. The transmission clock rate is thus not the same as the transmission bitrate, the latter being a measure of the quantity of data transmitted by the receiver during a given period, which can for example be adjusted by varying the level of compression of the audio or video stream. In some embodiments, the module <NUM> also provides estimates Oe of an origin of timestamps of the data packets. The module <NUM> for example comprises a buffer (BUFFER) <NUM> for buffering the received data packets.

Each data packet for example comprises a header including a timestamp, which is for example an RTP timestamp. The RTP protocol is for example described in more detail in the publication by <NPL>), the contents of which is for example incorporated herein to the extent permitted by the law. The timestamp is for example a <NUM> bit value, and for example indicates the value of the RTP clock at the sampling instant of a first sample in the RTP data packet.

For example, it is assumed that the timestamp T of each packet transmitted by the transmitter <NUM> is defined as follows: <MAT> where O is the origin of the timestamps, which is for example initiated at a random value, and is then constant during a given media transmission, R is the transmission clock rate, for example equal to the RTP clock rate associated with the media stream, and t is the media time, for example corresponding to the clock count of the transmitter <NUM>, or the system time used during the generation of video packets. As a typical example, the RTP clock rate, and thus the transmission clock rate, for a video stream defined in <NUM>/<NUM><NUM> of a second, and for an audio stream is equal to the audio sampling rate, which is for example equal to <NUM>, although many other values would be possible. As an example, a first packet of an audio stream could have a timestamp equal to the origin O, and may contain <NUM> samples. A subsequent packet of the audio stream would then have a timestamp equal to O+<NUM>.

On the receiver side, expression <NUM> above still holds, except the origin O is unknown, and while the theoretical value of the transmission clock rate R is known, in practise this value can be shifted slightly with respect the theoretical value. Indeed, the receiver <NUM> is generally distant from the transmitter <NUM>, and may not be precisely synchronized by external mechanisms such as the NTP (network time protocol) or by a GPS (global positioning system) device. In the case of audio streams, the time reference used for the transmission is the one employed by the sampling device, such as the analog to digital converter of the transmitter <NUM>, whose actual sampling rate may differ slightly, as a result of hardware manufacturing constraints, from the sampling rate of the rendering device, such as the digital to analog converter of the receiver <NUM>. This results in clock skew between the transmitter <NUM> and the receiver <NUM>, which is generally under five percent, but which should generally be taken into account by the receiver <NUM> in order to ensure correct playback.

The receiver <NUM> for example observes RTP packets arriving at timestamps T according to the following model: <MAT> where Oe is the estimate of the origin O of the timestamps in expression <NUM> above, Re is the estimate of the transmitter's transmission clock rate R in expression <NUM> above, and t is the local media time at the receiver.

For example, the timing analysis module <NUM> is configured to estimate the transmission clock rate Re based on timing data associated with one or more received packets. For example, the timing analysis module estimates the transmission clock rate Re based on the local media time t at the receiver <NUM>, and the timestamp of a plurality of received packets. As one example not covered by the appended claims, a relatively approximate estimation could be achieved based on a packet having a timestamp T1 received at a time t1 and a packet having a timestamp T2 received at a time t2, by computing (T1-T2)/(t1-t2). The timing analysis module <NUM> for example assumes a linear relationship between the local receiver media time t and the timestamps of the received packets.

The values of Re and Oe are for example updated in response to the reception of each new packet. Furthermore, so that the transmission clock rate estimates fall significantly when network congestion occurs, the calculation of the estimate for example involves a "forgetting factor", such that the timing data associated with older packets is either not considered or it is given less weight. For example, the estimate is calculated based on the timing data of a limited number of the latest packets received. Alternatively, calculating the estimate involves weighting timing data associated with more recent packets with a higher weight than the timing data associated with older packets.

Of course, while, in a non-claimed embodiment, the transmission clock rate estimate is an estimate Re of the transmission clock rate at the transmitter, according to the embodiments of the present disclosure, the transmission clock rate estimate is represented in the form of a ratio Ce between the clock rates of the transmission and reception clocks. An example of a method of estimating the ratio Ce between the clock rates of the transmission and reception clocks will be described in more detail below with reference to <FIG>.

Referring again to <FIG>, the data packets are for example provided from the module <NUM> to a decoder (DECODER) <NUM>. The decoder <NUM> decodes, using a system clock (SYSTEM CLK), the audio and/or video packets based on the particular audio and/or video compression standard applied to the media stream, and generates a decoded audio and/or video stream. In some embodiments, the audio stream is processed by a sound card (SOUND CARD).

As illustrated in <FIG>, the timing analysis module <NUM> for example provides the estimates Re of the transmission clock rate of the packets to a rate control circuit (RATE CONTROL) <NUM>.

The rate control circuit <NUM> is for example adapted to detect when congestion occurs in the network based at least on the estimates Re. In some embodiments, if network congestion is detected, the rate control circuit <NUM> is adapted to generate and transmit to the transmitter <NUM>, via an output interface (O/P) <NUM>, one or more bitrate requests (REQ) defining a maximum transmission bitrate to be used for the transmission of future packets in order to stop the congestion. For example, the request is for the transmitter to reduce its maximum transmission bitrate by between <NUM> and <NUM> percent.

While the timing analysis module <NUM>, the decoder <NUM>, and the rate control circuit <NUM> have been illustrated as separate hardware circuits in <FIG>, it will be apparent to those skilled in the art that one or more of these blocks could be implemented in software by instructions executed by a processing device.

<FIG> schematically illustrates the transmitter <NUM> of <FIG> in more detail according to an example embodiment. As illustrated, the transmitter <NUM> for example comprises an encoder (ENCODER) <NUM>, which receives an audio and/or video stream (AUDIO AND/OR VIDEO). For example, the audio and/or video streams may be captured by a microphone and/or video camera of or coupled to the transmitter <NUM> (not illustrated in the figures). The encoder <NUM> for example encodes the audio and/or video streams to generate media packets P.

The media packets P are for example provided to a transmission interface (TRANSMISSION INTERFACE) <NUM>, which transmits the media packets to the receiver <NUM> of <FIG>.

The encoder <NUM> for example receives the request signal (REQ) from the receiver indicating a maximum transmission bitrate to be used for the encoded audio and/or video streams, and adjusts the bitrate accordingly. For example, in the case of an audio stream, the encoder <NUM> decreases the transmission bitrate by applying a stronger compression to the raw audio stream, and increases the transmission bitrate by applying a weaker compression to the raw audio stream. For example, the encoder <NUM> uses a variable bitrate audio codec, such as the Opus codec, standardized by the Internet Engineering Task Force (IETF) as RFC <NUM>, or the AMR (adaptive multi rate) codec based on the ITU (international telecommunication union) standard. In the case of a video stream, the encoder <NUM> for example adjusts the transmission bitrate by modifying the quality factor applied during the video encoding, or by increasing or decreasing the frame rate and/or the image resolution.

<FIG> is a flow diagram representing operations in a method of estimating the origin Oe of the timestamps and clock rate ratio Ce between the transmission and reception clock rates according to an example embodiment. These operations are for example performed by a processing device of the timing analysis circuit <NUM>. The ratio Ce for example corresponds to Re/Trec, where Trec is the clock rate at the receiver.

In an operation <NUM>, it is determined whether a new packet has been received. When a packet is received, operations <NUM> to <NUM> are performed to estimate the parameters Ce and Oe. This method is for example an iterative method, each iteration corresponding to a new packet. The method converges to relatively precise estimates of Ce and Oe after several iterations.

The estimation of the parameters Ce and Oe for example uses an RLS algorithm based on the Kalman algorithm, applied to a model y(k) that assumes an ideal transmission. The RLS algorithm is for example based on a model y of the form: <MAT> where θ is an unknown parameters vector, and ϕT(k) is a regressions vector. The RLS algorithm can be expressed as follows: <MAT> <MAT> where λ is a forgetting factor of between <NUM> and <NUM>, P(k) is a gain matrix, and can be expressed as P(k)ϕ(k) = K(k), where K(k) is the Kalman matrix gain.

To estimate the parameters Ce and Oe, the following model is for example used, in which y(k) is the timestamp Tk of the received packet: <MAT> where tk is the local reception time at the receiver of packet k.

In a case in which the transmission delay is constant, and the clocks are perfectly aligned, the packets will be emitted and received at a constant rate, and the following relation holds true: <MAT>.

The parameters θ(k) and ϕ(k) of the RLS algorithm are for example defined as follows: <MAT>.

In operation <NUM>, a difference is calculated between the timestamp Tk of the received packet and an estimation of the timestamp based on previous estimates of Ce and Oe, for example based on the formula: Tk - (Cek-<NUM>tk + Oek-<NUM>).

In an operation <NUM>, the estimate of the parameters Ce and Oe are updated using the RLS algorithm, and in particular using the following equations, which are based on the difference calculated in operation <NUM>: <MAT> <MAT> where P is the gain matrix, which is for example a two-by-two matrix having a top row of values P<NUM> and P<NUM>, and a bottom row of values P<NUM> and P<NUM>.

In an operation <NUM>, the gain matrix is for example updated as follows: <MAT> where ak = λ + (P<NUM>tk + P<NUM>)tk + (P<NUM>tk + P<NUM>), and λ is a forgetting factor of between <NUM> and <NUM>.

The method then for example returns to operation <NUM> ready for the reception of a subsequent packet.

The values of the parameters Ce and Oe, as well as of the gain matrix P, are for example initialized at the start of a given transmission of an audio and/or video stream. The value of Ce can be expected to be in the range [<NUM>-<NUM>] with a high level of confidence, as the transmission and reception clock rates should be calibrated relatively well with each other. The parameter Oe could however take any value, because the origin of the timestamps is chosen randomly by the emitter. It can therefore take several iterations in order for the value of Oe to settle to a relatively precise estimate. The parameters Ce, Oe and P are thus for example initialized as follows: <MAT>.

The forgetting factor λ is for example set to a value of between <NUM> and <NUM>, such that the estimate Ce shifts as network conditions change.

<FIG> is a graph illustrating, by dots, an example of the media time t that packets having timestamps T are received by the receiver in a case in which no congestion detection or correction is performed. A dashed curve in <FIG> has a gradient representing the transmission clock rate estimates Re based on the reception time of the packets.

<FIG> is a graph showing a curve representing the estimates Re of the transmission clock rate based on the packets received in the example of <FIG>.

With reference to both <FIG>, until a time t<NUM>, the gradient of the dashed curve in <FIG> is relatively linear. The corresponding transmission clock rate estimates, which are for example based on an estimation of the linear relationship between the time t and the received timestamps T, are also relatively stable following a few initial oscillations, and converge to a level <NUM> at or close to the true transmission clock rate R.

However, at the time t<NUM>, network congestion occurs. The present inventors have found that network congestion causes the estimates of the transmission clock rate to tail off. Thus the gradient of the dashed curve in <FIG> reduces significantly, and the curve in <FIG> drops significantly below the level <NUM>. At a time t<NUM>, the router in the network at which the network congestion occurs for example drops packets, leading to a discontinuity in the timestamps received. This for example causes the transmission clock rate estimates to increase again. However, the congestion in the network is still present, and thus the gradient of the dashed curve in <FIG> remains low after the time t<NUM>, and the transmission clock rate estimates tail off again.

According to the embodiments described herein, the rate control circuit <NUM> of <FIG> is for example adapted to detect when the transmission clock rate estimates Re drop significantly, for example to a level of less than a threshold TH. In some embodiments, congestion is only detected when the estimates Re fall below the threshold TH for a minimum time duration Tc, where Tc is for example a duration of between <NUM> and <NUM>. In some embodiments, the threshold TH is a constant level based on a theoretical value of R. For example, the threshold TH is equal to F*Rtheoretical, where Rtheoretical is a theoretical level of R, equal in one example to <NUM> in the case of an audio stream, and F is a factor equal to less than <NUM>, and for example equal to between <NUM> and <NUM> percent, corresponding to a factor of between <NUM> and <NUM>. Alternatively, the threshold TH could be a dynamically changing threshold based on one or more previous estimates Re.

A method of detecting and correcting congestion over a network will now be described in more detail with reference to <FIG>.

<FIG> is a flow diagram illustrating operations in a method of detecting and stopping congestion in a network.

<FIG> is a state diagram representing states of the rate control module <NUM> according to an example embodiment.

With reference to both <FIG>, initially, the rate control module <NUM> is for example in a normal state (NORMAL) <NUM>. In an operation <NUM>, a packet is for example received, which for example triggers a congestion detection process. Alternatively, the congestion detection process could be triggered in another fashion, for example periodically.

In an operation <NUM>, an estimate Re of the transmission clock rate is for example calculated as described above, based for example on timing data associated with one or more received packets.

In an operation <NUM>, it is determined whether the estimated transmission clock rate Re indicates the presence of congestion. For example, congestion is detected if the following condition holds for more than a minimum duration Tc: <MAT> where, as mentioned above, F is a factor for example equal to between <NUM> and <NUM>, and Rtheoretical is the theoretical transmission clock rate.

If in operation <NUM> congestion is not detected, the normal operation continues, as represented by a box <NUM> in <FIG>, and by an arrow <NUM> in <FIG>.

If however congestion is found to be present in operation <NUM>, a congestion detected state (CONGESTION DETECTED) <NUM> of <FIG> is entered, and in a subsequent operation <NUM> of <FIG>, the bitrate request signal REQ is for example transmitted to the transmitting circuit <NUM>. For example, as indicated above, the bitrate request is based on the measured bandwidth Be of the communications channel between the transmitter <NUM> and receiver <NUM>, which for example provides an estimate of the available bandwidth. For example, the bandwidth Be is measured by calculating the bitrate of the media stream received by the receiver <NUM>. The bitrate request is for example for a bitrate corresponding to between <NUM> and <NUM> percent less that the measured bandwidth Be, and for example at around <NUM> percent less than the measured bandwidth Be.

A congestion present state (CONGESTION PRESENT) <NUM> of <FIG> is then for example entered, and in this state, new congestion detection operations are for example performed. In particular, in an operation <NUM>, a new estimate Re of the transmission clock rate is for example calculated, and in an operation <NUM>, it is determined whether congestion is present, for example based on the same test as applied in operation <NUM>. This is represented by an arrow <NUM> in <FIG>.

The operations <NUM> and <NUM> are for example repeated until congestion is no longer detected. For example, congestion is no longer considered to be present if the value of Re is equal to or exceeds the threshold TH, for example if: <MAT>.

The state then for example transitions to a congestion resolved state (CONGESTION RESOLVED) <NUM> in <FIG>, and in an operation <NUM>, a new bitrate request is for example transmitted to the transmitter <NUM> to increase the transmission bitrate with respect to the requested reduced bandwidth. For example, the new bitrate request is based on the previously measured bandwidth Be, and is for example between <NUM> and <NUM> percent lower than the measured bandwidth Be, and for example <NUM> percent lower. The state then for example transitions back to the normal state <NUM> of <FIG>, represented by the box <NUM> in <FIG>.

An advantage of initially requesting a large reduction in the transmission bitrate when congestion is detected is that this permits the congested router to recover by sending the pending packets that were previously buffered and which are causing the congestion. Once the receiver observes that the congestion has been resolved, the transmission bitrate can be increased to a level closer to available bandwidth estimated when congestion occurred.

Claim 1:
A method for detecting congestion in a packet-switched network (<NUM>) comprising:
estimating, by a receiver (<NUM>), a transmission clock rate, Re, of one or more packets of a media stream received by the receiver, each packet comprising a timestamp generated based on the transmission clock rate, R, wherein the transmission clock rate, Re, is estimated based on the timing of a plurality n of received packets and the timestamps associated with said n packets and estimating the transmission clock rate, Re, comprises estimating a clock rate ratio, Ce, between the transmission clock rate and the clock rate at the receiver based on the following model of the reception time tk of a packet k: <MAT>
where Tk is the timestamp, and Oe is an estimate of an origin value of the timestamps, and the reception time tk is predicted using an adaptive filtering technique based on a recursive least squares, RLS, algorithm or on a Kalman filter algorithm;
comparing the estimated transmission clock rate, Re, with a threshold, TH; and
detecting congestion in the network based on said comparison.