Adaptive Redundancy Overall Need (ARON)

Strictly defined ARON is the sum of all FEC overheads demanded from the sender for the compensation of sequential losses of all sub-flows carried by each individual link in the footprint of the communication path. The critical links of the path carrying the entire traffic are ignored, since the FEC required for the compensation of a failure of such links would be infinite. We assume that all routing schemes that are subject of comparisons are smart enough to delegate the load from a critical route over other links, if of course the network topology makes it possible. Thus our comparisons cannot contain a really bad routing sample which is following a single path route on a link when alternate multiple path routes are possible, and if the link is really critical by the network topology, then without a risk of affecting the comparison results such a link can be removed from all suggested routings in order to compare their remaining portions. We do not therefore study the advantage of the multiple path strategies versus single path routing, as in [Qu04], [Ma04], [Nguyen03], but we rather measure the advantageousness of routing within the scope of multi-path approaches.

If the failure periodicity is the same for all links such that any single link fails approximately every s seconds, if the observation duration (or the duration of the communication) is T and the duration of a single failure is d, then is the total failure time of any single link during the observation period.

Let M be the initial number of original media packets to be delivered to the receiver by the transmission blocks. Let be the needed size (number of packets) of the transmission block, under percent of random losses in the network (observed at the receiver) for maintaining the required QoS. Let L be the set of links laying on the communication path, and let be the load of a link under the present routing scheme. Let the percentage of recoverable losses, be the level of the tolerance permanently maintained in the media stream (even if there are no observed losses, good for bursty loss environment). The equation for ARON then looks as follows:

If we know the ARON of the given routing, we can deduce the number of redundant packets that the sender will be obliged to transmit in order to compensate all arbitrary network failures during the call duration T. We need also to know the periodicity and the duration of an individual link failure and the block transmission rate B (the block transmission rate is supposed to stay constant, while the packet transmission rate may periodically rise due to temporary increase of the number of redundant packets in the block). The number of redundant packets (the formula below) gives a practical meaning to the routing parameter ARON, but we assumed here a single link failure at a time [] (e.g. short link down-time and long link up-time).

as a function from the network’s random loss probability p may vary depending on the type of the encoder, the number of the media packets in the block (the buffering time) and the requirement for QoS.

We can imagine a pseudo “real-time” file transmission application in which the reception must be maintained at a constant rate and the file transfer must be accomplished within the time of the file size over the reception rate. Thus to ensure the reception at the maximal downlink rate through a lossy network the sender must transmit at a variable rate compensating thus the arbitrary losses arising in different network locations. This could be needed for synchronous updates of multiple stations of limited downlink bandwidth or a common problem of a last kilometer bottleneck for the internet user watching a one way video [Nguyen02].

Files are chopped into packets and transmitted by a spread route over the network possibly experiencing a faulty link, which is the same as the communication via an erasure channel with a random loss pattern, since the routers allocate the packets to the outgoing links randomly (according to the routing pattern). The theoretically rateless random linear fountain code [MacKay05], or the practical LT code [Luby02], or the improved Raptor code [Shokrollahi04], all reach in the file transfer application the Shannon capacity universally for any loss pattern (LT and Raptor codes with the decoding failure probability of , but lower in the recent versions of Raptor). We can maintain the constant receive rate by maintaining the packet transmission variable rate at , where p is the current random loss probability. At the same time the above cited fountain codes ensure the successful decoding (with a very little overhead) because they are simultaneously near-optimal for any erasure channel. Thus the routing parameter ARON for a file transfers application using at the sender a rateless universal fountain code (video chopped into files or very large blocks) and maintaining at the receiver constant reception rate (the bottleneck of the last kilometer), is computed by the following equation:

Let us compute the value of ARON for two routing examples over the same network shown in the figure below, where a is the sending node and b is the receiving node. Let the constant part of the tolerance of the media stream in this example be 0.1, i.e. the media stream (without additional adaptive tolerance demanded from the receiver) permanently survives the loss of up to 10%.

According to the first routing, shown in the figure below, the flow is evenly split over two paths and . The ARON of this routing is equal to 3.2.

	link		load	redundancy need
	a	b	0.5	0.8
	a	c	0.5	0.8
	d	b	0.5	0.8
	c	d	0.5	0.8
	c	e	0	0
	e	d	0	0

The second routing is similar to the first one except that it is slightly refined by breaking the load on the link across itself and the two-link alternate path . The ARON of this new routing is 3, which is lower the ARON of the previous routing and therefore the new routing is FEC friendlier and is more advantageous.

	link		load	redundancy need
	a	b	0.5	0.8
	a	c	0.5	0.8
	d	b	0.5	0.8
	c	d	0.25	0.2
	c	e	0.25	0.2
	e	d	0.25	0.2