WO2011064810A1

WO2011064810A1 - Method and apparatus for dynamically adapting the number of retransmissions

Info

Publication number: WO2011064810A1
Application number: PCT/JP2009/006299
Authority: WO
Inventors: Luis Loyola; Horacio Sanson
Original assignee: SkillUpJapan Corp
Current assignee: Allm Inc
Priority date: 2009-11-24
Filing date: 2009-11-24
Publication date: 2011-06-03
Anticipated expiration: 2012-05-24
Also published as: JP2012504352A; JP5117512B2

Abstract

The present invention provides a method and apparatus to allow a transmitting apparatus to dynamically adjust the number of retransmissions for different type of packets. The method comprises steps of classifying properties of each packet, assigning a retransmission limit number to each packet based on the classified properties, and retransmitting each packet according to the assigned retransmission limit number.

Description

METHOD AND APPARATUS FOR DYNAMICALLY ADAPTING THE NUMBER OF RETRANSMISSIONS

This invention relates to communication systems, and, more particularly, to a method for dynamically adapting the number of retransmissions of real time (time sensitive) media data in best effort communication systems and to an apparatus using the same.

1. Field of the Invention
The exponential growth of multimedia real-time streaming applications over the Internet is expected to stress the Internet infrastructure as it is today due to the limitations of the current transport protocols such as the transport control protocol (TCP) and the user datagram transport protocol (UDP) to handle the traffic generated by those applications.

UDP sends data packets without any guarantees or feedback on their arrival and the application is in charge of detecting and dealing with data packet losses. Furthermore, it lacks any flow or congestion control mechanisms against high-bit rate multimedia traffic applications that can potentially overload the Internet up to unacceptable levels of congestion.

TCP has feedback and retransmission methods to detect and recover from packet losses caused by channel impairments and congestion. It also provides congestion and flow control that reduces the risk of network collapse in situations of high-bandwidth load. With TCP, the transmitter assigns an increasing sequence number to each packet before transmission and the receiver uses these sequences numbers to inform the transmitter either which packets were lost using negative acknowledgements (NACK) or what packets were received using either selective acknowledgements (SACK) or simple acknowledgements (ACK).

Once the transmitter knows what data packets were lost, it can retransmit the lost packets to the receiver. If any of the retransmitted packets gets lost, the transmitter will, in principle, retransmit until all packets arrive at the final destination. Each retransmission adds an accumulated delay of at least one end-to-end round trip time (RTT) to each subsequent data packet that is considered very harmful for real time media such as audio and video real-time streams. Furthermore, real-time applications have time constraints that determine the useful time span of each media data packet after which any transmission or retransmission becomes a waste of network resources as the media packet is no longer useful for the receiver. A real-time video stream is a typical example of such real time media, where each media packet comprises a video picture. If the picture playback time has already expired there is no benefit in transmitting or retransmitting any of the packets related to that picture to the receiver.

Because of the accumulated delay and the potential waste of resources due to unnecessary retransmissions caused by reliable transport protocols, it is common practice to use unreliable transport protocols like UDP for real time applications such as video and audio streaming. But depending on the communications channel characteristics and the properties of the stream to be transported, the unreliable nature of UDP may result in very low quality perception at the receiver side due to high packet losses. For example, in a highly congested network or in wireless environments with high packet losses an unreliable transport protocol may be unable to deliver enough video pictures of the stream to provide an acceptable video quality at the receiver side.

Therefore, retransmissions are useful to recover from packet losses caused by channel impairments and network congestion, though, unnecessary retransmissions can result into accumulated delay and wasted network resources that deteriorate the perceived quality of real time media streaming applications.

2. Description of the Related Art
Retransmission based packet loss recovery methods for non real time data are well studied and patented.

For example, a framework for streaming media retransmission based on layered media is disclosed by Matthew Podolsky, et al. (Matthew Podolsky, Martin Vetterli and Steven McCanne, Limited Retransmission Of Real-Time Layered Multimedia, 2nd IEEE Workshop on Multimedia Signal Processing, 1998). In this paper, signals of streaming media are divided into layers according to their priorities, and retransmission of each layers are decided according to their priorities. As a result, a time-invariant policy, which does not change as layers approach their expiration, is concluded as the best transmission policy.

Ashfiqua T. Connie, et al., utilized Stream Control Transmission Protocol (SCTP) to transmit data-partitioned H.264 video (Ashfiqua T. Connie, Panos Nasiopoulos, Yaser P. Fallah and Victor C.M. Leung, SCTP-based transmission of data partitioned H.264 video, 4th International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems, Vancouver, 2008). In this paper, different priority or reliability levels are set for different data partitions of H.264 video. As a result, this paper revealed that SCTP-based transmission of data partitioned H.264 video brings better result for picture quality.

Further, by utilizing SCTP, video packet retransmission, allocation of bandwidth after R-D optimization and intelligent use of receiver feedback reports are designed by Antonios Argyriou, et al. (Antonios Argyriou, A Novel End-to-End Architecture for H.264 Video Streaming over the Internet, Journal of Telecommunication Systems, vol. 28, 2005).

SUMMARY OF THE INVENTION

1. Technical Problem
As mentioned above, retransmissions for packet loss recovery in real time media transmissions have been studied recently, but no prior work has dealt with dynamically adapting the number of retransmissions of real time media according to the difference of media type and the changing conditions of the network channel being deployed.

2. Solution to Problem
An object of the present invention is to provide a method and apparatus to allow a transmitting apparatus to dynamically adopt the number of retransmissions for packets with different properties.

A first aspect of the present invention for achieving above object is characterized by a retransmission method, which is used in a transmitting apparatus for transmission of packets of real-time data with different properties, comprising steps of
classifying properties of each packet,
assigning a retransmission limit number to each packet based on the classified properties, and
retransmitting each packet according to the assigned retransmission limit number.

In a second aspect of the invention, the method as in the first aspect characterized in that the retransmission method comprising steps of
estimating a status of the network being deployed, and
in the step of assigning the retransmission limit number, the retransmission limit number is assigned to each packet based on the classified properties and the estimated status of the network.

A third aspect of the invention for achieving above object is characterized by a transmitting apparatus for transmitting packets of real-time data with different properties, comprising
a controlling unit for classifying the properties of each packet, and assigning a retransmission limit number to each packet based on the classified properties, and
a transmitting unit for retransmitting each packet according to the assigned retransmission limit number.

In a fourth aspect of the invention, the apparatus as in the third aspect, characterized in that the controlling unit estimates a status of a network being deployed, and assigns the retransmission limit number to each packet based on the classified properties and the estimated status of the network.

3. Advantageous Effects of Invention

Therefore according to the present invention, effective retransmission of real time data can be realized, since retransmission limit numbers corresponding to the respective properties of each packet are assigned to each packet so that retransmission numbers can be dynamically adapted to each packet with different characteristics.

Fig. 1 is a functional block chart illustrating transmitting apparatus according to an embodiment of the present invention and the receiving apparatus for receiving real-time data via the network. Fig. 2 is an example of a retransmission policy being set within the range of estimated bandwidth. Fig. 3 is an example with probability of arrival of I, P and B frames from H.264 video codec after m retransmissions. Fig. 4 is a flow chart showing an example of the retransmission method performed in the transmitting apparatus in the embodiment.

Fig. 1 is a functional block chart illustrating transmitting apparatus according to the embodiment of the present invention and the receiving apparatus for receiving real time data via the network. The transmitting apparatus 100 according to the embodiment of the present invention transmits real-time data, such as video and audio, to the receiving apparatus 110 via the network. For example, the transmitting apparatus 100 can be implemented as a network streaming server and the receiving apparatus 110 can be implemented as a client in the network. Usually, a streaming server sends real-time multimedia data packets to at least one multimedia client.

The transmitting apparatus 100 comprises a transmitting unit 101 and a controlling unit 102 for controlling the transmitting unit 101. The controlling unit 102 comprises a classifier unit 103 for classifying packets into classes of different priority groups according to their contained media type, a network status estimating unit 104 for estimating the status of the network being deployed, and a retransmission limit number assigning unit 105 for assigning a retransmission limit number for each packet based on the class of each packet classified by the classifier unit 103. Preferably, retransmission limit number assigning unit 105 assigns a retransmission limit number for each packet based also on the network status estimated by the network status estimating unit 104. The transmitting unit 101 retransmits each packet up to a retransmission limit number assigned by the retransmission limit number assigning unit 105.

In addition to classifying frame properties, the classifier unit 103 can also set the priority of each frame. Here, the priority can be a predetermined value for each media type (e.g. encoding format).

Representative example of real-time data for streaming applications is video data encoded with an MPEG video codec such as MPEG-4 or H.264/AVC. The MPEG based encoders can achieve high compression rates thanks to a compression technique called motion compensation. When using motion compensation, similar sections between pictures are encoded and stored once in an Intra Frame (I frame), and only the motion differences (i.e. motion vectors) that indicates the change in direction and distance of these similar sections have translated between the I frame and subsequent pictures are encoded and stored as Predicted (P frame) or Bi-predicted (B frame) pictures.

The difference between P and B frames is that P frames only contain motion vectors referencing previous I or P frames, while B frames contain motion vectors referencing previous and posterior I or P frames. At the decoder, the I frame is self contained, which means that all information needed to decode it is contained within itself and subsequent P and B frames are decoded using the previously decoded I and P frames and the motion vectors.

Due to this motion compensation technique, I frames are usually an order of magnitude larger in size than P and B frames and have a more important role at the decoder. For example, the quality degradation caused by a lost I frame propagates to all subsequent P and B frames that depend on the lost I frame for motion compensation and similarly the degradation caused by a lost P frame propagates to all subsequent P and previous B frames that depend on the lost P frame for motion compensation.

Therefore, for the video data encoded by MPEG4 and H.264/AVC, comprising I, P and B frames, the classifier unit 103 sets descending priorities for I, P and B, respectively.

The classifier unit 103 can also read the whole data size in Megabytes of the message (e.g. a picture or a frame) being split into packets. Large messages are split into larger number of packets, and their loss probability is higher than that of smaller messages. Thus, the data size of the frame is an important factor to set the retransmission limit number.

Table 1 shows an example of the resulting classification groups and priority setting performed by the classifier unit 103 for H.264/AVC data. Given that there are three frames A-C contained in a media packet, the classifier unit 103 classifies the frame property of frame A as I frame, and set its priority high.

The network status estimating unit 104 estimates network status, such as, available bandwidth of the network being deployed, packet error rate, round trip time (RTT), and MTU (Maximum Transmission Unit).

For example, the network status estimating unit 104 estimates the available bandwidth of the communication path during the transmission of the next message stored in the transmission buffer (not shown). The estimation may be based on weighted average of past values or other statistical estimation techniques that use past values in a mathematical-progression fashion. The bandwidth estimation can be performed by observing the movement of the transmission buffer, or in the case of transport protocols that support congestion control (like TCP or reliable SCTP), the bandwidth can be estimated by tracking the congestion window and the round trip time.

In another example, the network status estimating unit 104 may monitor the network conditions of each receiving client using functions provided by the SCTP socket API (Application Programming Interface) or the operating system kernel API. Accordingly, the network status estimating unit 104 collect information of packet loss ratio, round trip times and MTU sizes for each client channel that receives the multimedia data packets.

The retransmission limit number assigning unit 105 assign a number corresponding to each media type to each media packet. Moreover, the retransmission limit number assigning unit 105 can assign a retransmission limit number to each packet according to the priority being set by the classifier unit 103. As mentioned above, the classifier unit 103 can read the whole data size of the message being split into packets. Thus, the retransmission limit number assigning unit 105 can also assign a retransmission limit number to each packet according to the data size of each frame classified by the classifier unit 103.

The retransmission limit number assigning unit 105 can assign retransmission limit numbers so as to limit the retransmission data size within the range of the available bandwidth estimated by the network status estimating unit 104. For example, in H.264/AVC streaming, when the channel has plenty of available bandwidth, the retransmission limit number assigning unit 105 will assign the retransmission policy {3, 2, 1} which means the packets of I frame being retransmitted up to three times, the packets of P frame being retransmitted twice, and the packets of B frame being retransmitted once. This policy guarantees a very high probability of reception for all media-type messages. On the contrary, a retransmission policy {2, 2, -1} will ensure a relatively high probability of reception of packets of I and P frames while all packets originated from B frames are being dropped from the transmission buffer before being transmitted. The point of this idea is to sacrifice some packets from B frames with low priority to give more space to packets of I and P frames, which have a higher impact on the perceived quality at the receiver side.

Fig. 2 is an example of the retransmission policy assigned by the retransmission limit number assigning unit 105, based on the estimated available bandwidth and priority. Given that the estimated available bandwidth is not enough for the optimum retransmission policy {3, 2, 1}. Therefore, the retransmission limit number assigning unit 105 limits the retransmission of the packets with least important media type (B frames). As a result, the packets from I frames are retransmitted a maximum of three times, the packets of P frames are retransmitted maximum twice and packets of B frames are not transmitted..

The retransmission limit number assigning unit 105 can set the retransmission limit number by using a probability model based on packet error rate, for example. This probability model illustrated in Fig. 3 for H.264/AVC data is derived from the following equations.

Given that each I, P and B frame is split into n segments of MTU sized packets before transmission, and p stands for the characteristic packet error ratio of the end-to-end path. Then, the loss probability of any of the n segments belonging to an I, P or B frame at the receiver is:

After the first transmission of either an I, P or B frame, the expected number of lost segments due to channel impairments is np. In the case where all these segments are retransmitted, the probability of arrival at the receiver of any of these retransmitted segments is given by:

Similarly, after the second retransmission, np² segments of the frame are expected to be lost, thus, after a second retransmission for the lost segments, the probability of any of these segments being lost comes to:

Therefore, the probability of single segment of an I, P or B frame not arriving at the receiver after m retransmissions is given by:

Assuming the existence of a memoryless channel, individual segment losses are independent between retransmissions and thus the loss probability of a single segment of an I, P or B frame being retransmitted m + 1 times can be approximated as:

And the probability of all segments of an I, P or B frame being successfully received after m + 1 transmissions (i.e. m retransmissions), and therefore, the probability of the whole frame being successfully received is then:

Curves for probabilities of successful transmission of I, P, B frames of video data encoded with MPEG-4 or H.264/AVC are shown in Fig. 3. Various retransmission limit numbers in the range of 0 to 3 are assigned to the packets with different frame properties by the retransmission limit number assigning unit 105. The respective curves in Fig.3 represent the relationship between packet error rate and probability of successful NAL reception, for respective cases where I = 0, P = 0, B = 0, I = 1, and P = 1. Curves corresponding to the result of assigning other retransmission limit numbers, such as, I = 2 or 3, or P = 2 or 3, and B = 1, 2, or 3 are distributed in clumps within the hatched area in Fig. 3.

The probability of data reception is evaluated by estimating the probability of reception of a NAL unit. The curve showing the worst result corresponds to the case where the retransmission limit number for I frames is set to null (I = 0). The second worst result corresponds to the case where the retransmission limit number for P frames is set to zero (P = 0).

A desirable reception probability can dynamically be determined based on network status being estimated by the network status estimating unit 104. In order to maintain excellent image quality of H.264 video, the desirable reception probability for packets of I frames is 1, i.e., packets of I frames are not being lost, in an ideal case. On the other hand, packets of P or B frames are allowed to be lost according to the available bandwidth of the network being deployed. Given that the reception probability above 0.8 is set for B and P frames, the retransmission limit number assigning unit 105 assign retransmission limit number B = 0, under the situation where the packet error rate of the channel being deployed is less than 0.02; and retransmission limit number P = 1, under the situation where the packet error rate is less than 0.07. In this way, the retransmission limit number assigning unit 105 dynamically adapt the retransmission limit number required to guarantee a high probability of arrival, for example, threshold value 0.8 in Fig. 3.

Fig. 4 is a flow chart showing an example of the retransmission method performed in the transmitting apparatus in the embodiment. Here, video data, encoded with MPEG4 or H.264/AVC, including I, P and B frames, is transmitted. The network between the transmitting apparatus 100 and the receiving apparatus 110 may consist of a variety of network links, such as optical fiber, copper lines and wireless connections.

When transmitting apparatus 100 starts data transmission, the controlling unit 102 reads packets to be transmitted (step S401). Then, the classifier unit 103 classifies packets (step S402) into different priority classes or groups. In this time, the priority and the message data size can be classified by the classifier unit 103. Then, the network status estimation unit 104 estimates the network status (step S403). Here, the network status can be a change of an available bandwidth of the network.

Based on the classes classified by the classifier unit 103 and the available bandwidth estimated by network status estimating unit 104, the retransmission limit number assigning unit 105 assigns an appropriate retransmission limit number to each message coming out of the transport layer's transmission buffer (step S404). In this time, the retransmission limit number assigning unit 105 can dynamically tune the retransmission limit number based also on the size of each message. The size corresponds to the value of n, which stands for the number of segments for each frame, in the formula. A reverse operation of formula (1) using values of n, p (packet error rate of the end to end path being deployed), and the dynamically determined value of the probability of the whole frame being successfully received (value of P_m), gives a retransmission limit number m, as mentioned above. In other words, the retransmission limit number is calculated on the basis of the class of each packet and estimated network status.

Then, the controlling unit 102 encapsulates the media packet into transport message (step S405). Transmitting unit 101 transmits packets (step S406).

The controlling unit 102 determines whether ACKs for transmitted packets are detected or not (step S407). In the case where an ACK is detected, the controlling unit 102 terminates the transmission process of the corresponding packet. On the contrary, in the case where no ACK is detected, the controlling unit 102 determines whether the retransmission limit number assigned by the retransmission limit number assigning unit 105 to the corresponding packet has already been reached or not (step S408). In the case where the retransmission limit number has been reached, the controlling unit 102 terminates the transmitting process. On the other hand, if the retransmission limit number has not been reached, the controlling unit 102 controls the transmitting unit 101 to perform a new retransmission (step S409). Then, the controlling unit 102 determines whether an ACK for retransmitted data has been detected or not (step S407), and in the case where the ACK is detected, the controlling unit 102 terminates the transmission process. On the other hand, in the case where the ACK is not detected, the controlling unit 102 repeats the steps S408 and S409 until the ACK is detected or until the retransmission limit number has been reached, and then, terminates the transmission process.

In this way, the transmitting apparatus 100 and the retransmission method according to the present embodiment, the controlling unit 102 can adapt the retransmission number based on property of the data, since the controlling unit 102 controls the classifier unit 103 to classify the media type or class of each packet, and controls the transmitting unit 101 to retransmit data based on the result of the classification. Thus, the packet loss can be eliminated effectively. Moreover, the control unit 102 can adapt the retransmission number based on the priority of each media type, so the retransmission efficiency can be improved.

Moreover, available bandwidth in the network being deployed is effectively utilized and real-time data can be effectively transmitted, since the controlling unit 102 of the transmitting apparatus 100 controls the network status estimating unit 104 to estimate the network status and the retransmission limit number assigning unit 105 to assign retransmission limit numbers for each packet based on the estimated network status. Further, in the case where the data is successfully received, the retransmission is avoided so as to effectively utilize the available bandwidth in the network. This is particularly useful for real time data such as video, audio and timed text for which late arriving packets are likely to increase network congestion, delay and wasted bandwidth instead of enhancing the perceived quality at the receiver.

The above mentioned embodiment can be implemented without the Network status estimating unit 104. Accordingly, an efficient retransmission method is realized with lesser number of components and steps.

The present invention is not limited only to the above embodiments, but various changes and modifications can be made.

For example, instead of assigning the retransmission limit number based on I, P and B frames, it can be assigned according to the SVC layers' interdependencies. In this case, higher retransmission limit number can be assigned to lower layers, since losing a packet in the Nth layer affects all subsequent packets from all higher layers. Generally, H264/SVC encodes videos in several dependent layers. By adding/subtracting layers it is possible to obtain different versions of the same video with different spatial, temporal and quality characteristics. The lowest layer (base layer) is required to obtain a minimum quality and by adding additional layers is possible to increase any of the frame rate (temporal scalability), the resolution (spatial scalability), or the quality (quality scalability), or all three together.

For example, there are also scalable audio codecs like the MPEG-4 BSAC (Bit Sliced Arithmetic Coding) that encode the audio stream in a base layer and one or more enhanced layers. In a similar way to H.264/SVC, the more layers the user receives the better the perceived hearing quality but due to limited network resources it may not be possible to transmit all layers. Number of retransmissions may be assigned to each audio layer based on the interdependencies among them. In addition, as users demand for high definition video increases, it is expected that high quality audio with multiple channels (5.1 and 7.1) will follow. Such audio signals are composed of several audio streams (i.e. Left, Right, Center, LFE (Low Frequency Effect), Subwoofer) that can also be assigned priorities based on the contribution they give to the overall hearing experience or capabilities of the receiver (e.g. receiver with only stereo output).

For example, the method and apparatus of the present invention can be implemented using the partial reliable extension of the stream control transport protocol (PR-SCTP) that provides applications the ability to limit the number of retransmissions for each packet using three different retransmission policies. The timed policy (TTL: Time To Live) allows an application to assign an expiration time to each media packet after which the packet is considered unnecessary and no more retransmissions will be attempted. The max retransmission policy (RTX) allows an application to assign a retransmission limit number to each media packet after which no more retransmissions will be attempted. Finally, the buffer policy (BUF) allows an application to assign a buffer priority to each media packet that allows retransmission of packets based on receiver buffer availability. BUF is particularly useful for mobile multimedia terminals with low processing and storage capacity such as smart phones, car navigation systems and portable computers.

In an apparatus and a method employing PR-SCTP, as mentioned above, bandwidth availability and channel packet loss statistics are estimated using PR-SCTP and a retransmission PR-SCTP policy is assigned based on the result of the estimation and the size, bit-rate and priority of each media packet. For example, when transmitting real time video streams coded with any of the MPEG based coders, the transmitting entity can assign to each video picture a retransmission limit number that guarantees the highest probability of arrival based on each video picture size, channel MTU and the measured end-to-end packet loss rate.

Further, the streaming server can use combinations of the retransmission policies described above. For example, the transmitting apparatus can assign TTL of PR-SCTP for I frames and limit the retransmission limit number for P and B frames.

Further, other common transport protocols including but not limited to TCP, UDP and DCCP (Datagram Congestion Control Protocol) can also be extended to offer partial reliability similar to PR-STCP, and these extensions would make possible other embodiments of the present invention. Furthermore, new partial reliability policies suitable for other kinds of media, such as audio and text, can also be used in the above mentioned methods, in order to dynamically adapt the retransmission policy based on the media properties, channel characteristics, etc.

Further, the method and apparatus of the present invention can be implemented directly in a communication protocol stack such as the OSI (Open Systems Interconnection), IrDA (Infrared Data Association) and Bluetooth stacks. In such cases, the method and apparatus may be implemented directly in a new transport protocol resulting in a protocol similar to PR-SCTP in functionality. The method and apparatus according to the present invention can then be used on this new transport protocol to dynamically adapt the retransmission policy and limit the retransmission limit number for each media video and audio packet to be transmitted, taking in consideration the media properties and the current channel characteristics.

Claims

A retransmission method, which is used in a transmitting apparatus for transmission of packets of real-time data with different properties, comprising steps of
classifying properties of each packet,
assigning a retransmission limit number to each packet based on the classified properties,
retransmitting each packet according to the assigned retransmission limit number.
The method as in Claim 1, further comprising a step of
estimating a status of a network being deployed, wherein
the retransmission limit number is assigned to each packet based on the classified properties and the estimated status of the network, in the step of assigning the retransmission limit number.
A transmitting apparatus for transmitting packets of real time data with different properties, comprising

a controlling unit for classifying the properties of each packet, and assigning a retransmission limit number to each packet based on the classified properties, and
a transmitting unit for retransmitting each packet according to the assigned retransmission limit number.
The apparatus as in Claim 3, wherein the controlling unit of the apparatus estimates a status of a network being deployed, and assigns a retransmission limit number to each packet based on the classified properties and the estimated status of the network.