End-to-End adaptive FEC

As a reference for the real-time streaming application we take the most widely used example: voice over IP. The driving motivation for transporting real-time voice over IP networks (apart the uniformity, fluidity and manageability aspects) is the significant cost savings achievable by eliminating or bypassing the circuit-switched TDM telephony infrastructure. Although use of VOIP is currently weak, the wide penetration of the packetized voice with possibly complete replacement of TDM technologies is practically inevitable.

Most frequent failures, congestions caused by the bursty traffic, are not supposed to be considered as link outages, since most of routers maintain QoS and the tiny VOIP stream must not suffer from the HTTP bursts, which are often less important from the user point of view, but may consume 25 to 50 times more bandwidth. The IP telephony service provider (ITSP) however often is different from the internet service provider (ISP, usually the former monopolist of the ex-ante regime providing internet via ADSL employing the last kilometer infrastructures) and the packets of the ITSP most of the time do not have particular priority in the network of the ISP. The bandwidth consumed by IP Telephony VOIP stream (using the high complexity codecs) with all IP, UDP and RTP header overheads is as low as 16 to 20 Kbps (the pure voice payload bandwidth is as low as 5.3, 6.3 or 8 kbps, the recently standardized AMR has 4.75 kbps mode). The average ADSL capacity is of 600 Kbps to 1 Mbps for the downstream and the forth of it for the upstream. The end user will have therefore absolutely no objection if, due to a short failure somewhere in internet, the IP telephony voice call application will be capable to temporarily burst its transmission rate several times saving thus the voice call from dropping. [Huang05] presented an implementation doubling the media packets at high losses and reported good results in practice. With a spread multi-path routing the need of a bit rate increase would be much fewer. As a reaction to failures arbitrarily occurring at different places in the network, the ability of a voice software or hardware (e.g. of a SIP phone) to periodically increase its transmission rate, maintaining the speech quality constantly at the high level during the phone conversation, will be highly appreciated and the bandwidth is not a concern. In the present study we therefore assume that all links have a sufficiently large capacity compared with the bandwidth of a media stream.

The cooperativeness or friendliness of a routing toward FEC is simpler of all to measure based on the satisfaction level of a realistic application employing end-to-end adaptive FEC. In the spread routing, at the node which has multiple outgoing links, the router randomly allocates the packets of the incoming queue to the outgoing links (according the load distribution pattern of the routing). Losses at the receiver, occurring due to temporary congestions or failures of network links have therefore a random pattern. All links of our model have an equal probability, frequency and duration of failure. Before the triggering of any failure detection and recovery mechanism, a failure of a link laying on the communication path, produces, according the portion of the traffic being still routed toward the faulty route, random losses, observed finally at the receiver. The media stream of the application is equipped with a constant tolerance t to certain level of losses (). If the losses measured at the receiver are exceeding the critical level the receiver demands the sender via a feed-back channel injecting into network an extra redundancy. Either the feed-back loop is assumed negligibly short compared with the duration of a failure of a link or the usual constant tolerance of the media to random losses is high enough to leave a sufficient time to the feedback loop, without a risk of too many damages to the usability of the media stream. The sender must add to its further transmission a sufficient quantity of redundancy to compensate the new losses signaled by the receiver, thus continuing to maintain the communication constantly at the required level of quality. The sender must compute the redundancy need as a function from the percentage of losses p observed by the receiver in the stream of incoming packets. Such an end-to-end feedback based adaptive FEC mechanism is not aware of the routing and is implemented entirely on the end nodes in the application level.

Implementation of this method in practice was proposed by several authors: [Kang05] proposed to adjust the amount of FEC based on packet loss information under dynamically changing network environment, [Xu00] proposed to dynamically combine FEC with automatic repeat request. [Padhye00] proposed to slowly tune the amount of FEC considering the history of losses measured after decoding. [Johansson02] and [Huang05] proposed to apply to packet switched network the mode adaptation scheme of Adaptive Multi-Rate (AMR) codec, adopted as the standard speech codec by 3GPP. If the network is lossy, source coding is reduced and channel coding is increased and, inversely, if the streaming is lossless the source coding is increased and a weak FEC is used.

FEC can be added to the media stream in one of the following three ways. In media specific FEC methods, the redundant information is generated using a different lower bit rate encoding algorithm than the algorithm used to encode the original packet (e.g. using the eight modes of AMR). Media specific schemes piggyback information about the present period with later packets [Padhye00], [Altman01], [Johansson02]. In a similar method, but without multimode media source encoder, i.e. abstracting from the media, packets can be extended to carry one or more duplicates of previously produced samples or their XOR products (or another form of their redundancy). While the two above methods are extending the packets of the stream in size, according the third method the redundant packets (representing a number of original packets) are extending the stream in quantity, inserting the redundant packets in the stream [Huang05], [Nguyen03]. In our model we use the third method. The following arguments are in favor of injecting the redundant packets into the stream. By adding packets of identical size we do not (or almost do not) influence on the packet loss rate (which can be a function from the link BER and the packet size or from the queue policy of routers), and thus we do not need to model individual links and routers to adjust this change. A practical advantage of adding the redundant packets without modifying the stream of original packets (using a systematic erasure resilient FEC code) is the possibility of a full transparency on the media application layer. The redundant packets can be generated and decoded back into media packets (or dropped if no media packet of the block is lost) on the edge routers (usually the NAT router of the user), leaving this process completely transparent for the media application.

Although the proposed adaptive FEC application is not aware of the underlying network topology and the routing, we define the aggregate effort of adaptive redundancy demanded from the sender by the receiver during the whole communication time as an evaluation measure of the friendliness and the advantageousness of the underlying network routing toward the tolerance. Fewer is the overall amount of the encoder’s redundancy effort demanded by the receiver to the sender, higher is the rating of the routing toward the tolerance of the communication (assuming that the routing suggestions are measured under the identical pattern of network link failures). The so defined encoder’s aggregate effort, called henceforth Adaptive Redundancy Overall Need (ARON), is the easily measurable scalar value characterizing the friendliness of the entire underlying routing (toward FEC). Any collection of routing suggestions can be sorted by their advantageousness toward tolerance, simply by measuring and comparing their ARON values.