In the context of multimedia transmission over the Internet or over Local Area Networks (LAN), a multimedia data server must deliver one or more data streams (of video type, audio type, or text type such as sub-titles, etc.) to one or more clients.
These clients receive and consume these data, for example by playing the video and the audio, progressively as they are received. The expression multimedia “streaming” is used.
These multimedia streams are constituted by data such as images, portions or slices of images or samples of sounds a characteristic of which is to have a limited useful life, that is to say that these data must imperatively be received and processed by the receiving peripheral before a certain time limit. This time limit corresponds to the time at which the item of data is required to be displayed or played by the client. Beyond that time limit, the data becomes useless and is purely and simply ignored by the client.
To limit the rate of the data and so obtain rates compatible with that of the underlying network, these various data streams are generally compressed, for example, for video, in accordance with the MPEG 2 or MPEG 4 part 2 or H.264 compression standards and for example, for audio, in accordance with the AMR, G.711, G.722.1, AAC compression standards. These are lossy compression standards: the compression is very efficient, but the stronger it is, the more the item of multimedia data is degraded.
Increasing amounts of equipment available for the general public meet this definition and are capable of sending such data streams: this is the case for camcorders, photographic cameras, video surveillance cameras, home video servers, TV receivers, computers and telephones. The multimedia streams (video, audio, text) intended to be sent may be stored and compressed in advance on the sending apparatus or on the contrary be captured, compressed and sent over a communication network to a receiving apparatus.
These multimedia streams are transmitted over communication networks constituted by interconnection nodes (routers, switching devices, etc.) in order to convey the data packets coming from source devices to recipient devices. They share these networks with other data streams (for example Internet browsing, a video game, the transfer of a file to a printer, etc.). All these data stream are liable to create congestion on the communication networks when they pass via the same network link of insufficient capacity. The excess packets generally end up being rejected by the interconnection node situated at the input to the link.
The structure of the network is not known by the sending and receiving devices. Similarly, the streams present do not know each other and their number and their behavior may be very variable over time.
Conventionally, the servers and the clients use communication protocols implementing control mechanisms in order to avoid continuously losing a high quantity of data in case of congestion. They make it possible to detect the appearance of a congestion phenomenon on the basis of the packet losses and they act on the transmission rate of the data stream in order to reduce it or to increase it so as to be compatible with the overall bandwidth of the network.
Congestion control mechanisms generally implemented in IP networks are of TFRC (TCP Friendly Rate Control, IETF RFC3448) or AIMD (Additive Increase/Multiplicative Decrease, IETF RFC2581) type.
For example, the AIMD mechanism makes it possible to equitably share the available bandwidth between all the data streams: each competing stream obtains an equal share on average. AIMD is based on the use of a sliding window, termed congestion window. The size of this window determines the maximum quantity of data that the server is authorized to send immediately over the network without having to await the next acknowledgement.
The TCP protocol doubles the size of the congestion window at each RTT (Round-Trip Time) that is to say at each acknowledgement, when the congestion window is less than the slow-start threshold, and then it increases the window by one data segment for each RTT (congestion avoidance phase). If a congestion loss arises, the congestion window is reduced by half. This algorithm makes it possible to probe the available bandwidth until a loss of packets is obtained indicating a congestion on the network. A congestion loss is generally described as corresponding to a timeout or to the reception of three duplicated packets.
The congestion control mechanism thus makes it possible to reduce the traffic heaviness on the network and thus to reduce the number of congestion errors. However, it does make it possible to be totally free therefrom.
The impact of an error on a multimedia stream may be very great. This is because, due to the compression, an error in a part of a stream will propagate into the other parts of the stream. For example, if an image slice is lost, the image will of course have an incorrect part, but due to the compression by motion compensation carried out by modern video coders (MPEG standards), the following images will also be affected. It is thus important to attempt to correct these errors.
The most common technique consists of asking for the lost packets again. However, this technique cannot be used for the case where the stream is transmitted with strong time constraints, that is to say when the data must be received before a maximum time limit and if that time limit is short compared to the communication time between the client and the server (RTT). The maximum time limit is for example linked to the point in time for display of the image which is set by the display cadence of the images at the client. It is thus necessary to have recourse to a predictive method of error correction.
Predictive methods consist of coding the multimedia data and of sending them in such a manner that certain parts can be lost with a small impact on the quality of the media received and decoded.
A conventional predictive error correction method consists of creating redundancy packets, which are sent in addition to the packets of the multimedia stream. If one of the multimedia data packets is absent, the receiver may use the redundancy packets to re-create the missing packets. The redundancy packets may be created for example using XOR operations or with Reed-Solomon codes.
Another predictive method for limiting the impact of the errors consists of changing the coding of the multimedia stream, to reduce the dependency between the data. It is possible for example to reduce the number of macroblocks in an image that uses coding by motion prediction. Thus, an error is less visible since it has little chance of propagating to the following images.
In both these cases, a considerable difficulty consists in evaluating the necessary level of redundancy. This is directly linked to the error level in the network. On the one hand, if the rate of redundancy is less than the real error rate of the network, some errors will be unable to be corrected or will have a high impact. On the other hand, if the redundancy rate is too great, the server transmits information that is of no use. The available rate for the item of multimedia data is thus reduced, which forces it to be compressed more and thus degrades its quality. It is thus important to estimate the error rate as precisely as possible.
Transmission errors may have several causes: problems of physical transmission (for example, radio interference during a wireless transmission) or congestion errors. The invention is solely concerned with this second type of error.
The congestion error rate depends on several parameters: the behavior of the sender of the data (its own data may create congestions) and, furthermore, the behavior of the other data streams using the same network (the data of the other streams may also create congestions).
In a system in which no a priori knowledge about the network and about the behavior of the other streams is available, the prior art provides no method of determining the rate of correction to implement.
The invention seeks to predict the future rates of congestion errors during the transmission of the next packets of a multimedia stream to enable good adjustment of the predictive methods of error correction.
In a paper entitled “Real-Time Packet Loss Prediction based on End-to-End Delay Variation” published in IEEE Transactions on Network and Service Management, vol. 2, no. 1, November 2005, L. Roychoudhuri et al. describe a system which uses the measurements of the transmission times of the data packets to calculate a probability of error, in order to calculate a level of error correction to apply to the data to send. This system has in particular the drawback of not taking into account the impact of other streams passing over the network.
USPTO Backgrounds
USPTO Backgrounds