Fault-Tolerance of Capillary Multi-Path
Routing for Real-Time Multimedia Streaming with Forward Error Correction
|
EPFL and Switzernet Sàrl emin.gabrielyan@switzernet.com |
Roger D. Hersch Swiss Federal Institute of Technology
– EPFL rd.hersch@epfl.ch |
Packetized communications over Internet behave like erasure channels and the erasure resilient FEC codes can be applied to combat packet losses. For numerous packetized off-line applications, erasure resilient codes yield spectacular results. Raptor code makes possible satellite broadcasts of voluminous updates of GPS maps to millions of motor vehicles at arbitrary fragmental visibility without a feed-back channel [1]. In a film industry the film footage can be delivered over lossy Internet across many thousands of miles, thanks to LT codes [2]. Off-line streaming benefits from application of FEC because, contrary to real-time streaming, the sender is not obliged to deliver in time “fresh” packets of a very short life time and the buffer size is not a concern. With limited buffering time, FEC can only mitigate short granular failures. Many studies reported weak or negligible improvements from application of FEC to real-time streaming [3], [4], [5] and [6].
FEC however can be a mean for achieving fault-tolerance also in real-time streaming, but other dimensions, replacing the long buffering time must be exploited. Studies stressing the poor FEC efficiency always assumed that the media stream follows a single path. There is an emerging body of a literature demonstrating the applicability of FEC in real-time streaming, if combined with path diversity [7], [8], [9] and [10]. These studies are stressing the advantageousness of the path diversity being compared only with single path routing approach and the considered multi-path routing patterns are simple and are limited to only two alternative paths or in the best case to a sequence of parallel and serial links. The multi-path routing topologies, so far, were not regarded as a space of solutions and a ground for searching FEC-friendly patterns. In this paper we present a comparative study across a wide range of multi-path routing patterns. Single path routing, being considered as too hostile is excluded from our comparison system.
As means for achieving multi-path routing we propose capillary routing, seeking to minimize the impact of individual link failures to the media stream. The capillary routing is built layer by layer, providing at each layer a different routing pattern. In the first layer the alternative paths are discovered by minimizing the maximal loads of all links. Further equilibration is obtained by minimizing in the second layer the maximal load of all links, but now without the bottlenecks of the first layer’s routing. The solution of the second layer leads to the sub-routes and the sub-bottlenecks of the second layer. The successive layers are constructed similarly until the entire footprint of the flow is discovered. Contrary to the shortest path or max-flow routing capillary routing has only one solution. A flow traversing a large network with hundreds of nodes may have hundreds of capillary routing layers.
The friendliness
of a routing is measured with an imaginary application employing end-to-end
adaptive FEC for combating link failures. The FEC block, carrying a fixed
number of source media packets (10 or 20 in our measurements), has a variable
size, which is a function of the percentage of packet losses p reported by the receiver. The FEC(p)
function is computed assuming Reed-Solomon code taking into account the desired
decoding failure probability (
in our example). Most
of real-time streaming applications already tolerate a certain constant level
of packet losses (e.g. about 9% for VOIP). The permanent tolerance can be also obtained
or increased by incorporating a constant amount of FEC. If the loss rate p measured at the receiver is about to
exceed the critical tolerable level, the sender increases its transmission rate,
by sending according to the FEC(p) function a sufficient surplus of redundancy.
Adjustable FEC in real-time streaming was already proposed by several authors [11], [12], [5], [3] and [4]. Although the proposed end-to-end adaptive FEC
mechanism is not aware of the underlying routing and is implemented entirely at
the application level, the friendliness of the routing pattern is measured by
the total amount of the failure recovery adaptive redundancy needed from the
sender during the communication time, i.e. by Adaptive Redundancy Overall Need
(ARON); see the equation.
Here,
L is the set of all links in the
communication path, the percentage 
of recoverable losses
is the level of the tolerance permanently maintained by the media stream, and r(l)
is the load of a link 
under the routing pattern
(note that a temporary congestion or a failure of one of the links produces
random losses, corresponding to the portion of the traffic being still routed
toward this faulty link).
By computing the ARON ratings of capillary
routing layers we show that by capillarization of the flow (i.e. by recursively
spreading and equilibrating the sub-flows of the main flow) the routing pattern
becomes much friendlier toward FEC. Multi-path routing similarly to buffering
can significantly burst the efficiency of FEC. The chart of Fig.1 shows on 300 network samples (divided in 7
groups) the decrease of the average ARON cost as the capillary routing layer
increases. The three curves correspond to the static tolerance levels of 5.4%,
6.6% and 7.8%. The network samples are obtained from a random walk Mobile
Ad-hoc Network (MANET) with 115 nodes.
[1] A. Shokrollahi, “Raptor codes”, ISIT’04, Jun
27 - Jul 2, p 36
[2] M. Luby, “LT codes”, FOCS’02, Nov 16-19, pp
271-280
[3] I. Johansson, T. Frankkila, P. Synnergren,
“Bandwidth efficient AMR operation for VoIP”, Speech Coding 2002, IEEE
Workshop, Oct 6-9, pp 150-152
[4] Y. Huang, J. Korhonen, Y. Wang, “Optimization
of Source and Channel Coding for Voice Over IP”, ICME’05, Jul 06, pp 173-176
[5] C. Padhye, K. J. Christensen, W.
[6] E. Altman, C. Barakat, V. M. Ramos, “Queueing
analysis of simple FEC schemes for IP telephony”, INFOCOM’01, Vol. 2, Apr 22-26,
pp 796-804
[7] Q. Qu, I. V. Bajic, X. Tian, J. W. Modestino, “On the effects of
path correlation in multi-path video communications using FEC over lossy packet
networks”, GLOBECOM’04, Vol. 2, Nov 29 - Dec 3, pp 977-981
[8] T. Thongpook, “Load balancing of adaptive zone
routing in ad hoc networks”, TENCON’04, Vol. B, Nov 21-24, pp 672-675
[9] R. Ma, J. Ilow, “Regenerating nodes for real-time transmissions in
multi-hop wireless networks”, LCN’04, Nov. 16-18, pp 378-384
[10] T. Nguyen, P. Mehra, A. Zakhor, “Path diversity
and bandwidth allocation for multimedia streaming”, ICME’03 Vol. 1, Jul 6-9, pp 663-672
[11] S. Kang, D. Loguinov, “Impact of FEC overhead
on scalable video streaming”, NOSSDAV’05, Jun 12-14, pp 123-128
[12] Y. Xu, T. Zhang, “An adaptive redundancy
technique for wireless indoor multicasting”, ISCC’00, Jul 3-6, pp 607-614