Transcript Document
Fault-Tolerance of Capillary Multi-Path Routing for RealTime Multimedia Streaming with Forward Error Correction Emin Gabrielyan Switzernet Sàrl and Swiss Federal Institute of Technology (EPFL) [email protected] 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 1 Fault-Tolerance of Capillary Multi-Path Routing for RealTime Multimedia Streaming with Forward Error Correction ICTTA 2006 – 2nd IEEE International Conference on Information & Communication Technologies: from Theory to Applications April 24 - 28, 2006, Umayyad Palace, Damascus, Syria 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 2 Off-line streaming Digital Fountain Codes A file can be chopped into equally sized source packets … … … Digital fountain code can generate an unlimited number of different checksum packets of the size of the source packets 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 3 Off-line streaming Digital Fountain Codes … … … It is sufficient to collect almost as many checksum packets as there are source packets in the file – and the file can be recovered 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 4 Off-line streaming Digital Fountain Codes Exactly like in a fountain: you need to collect just a sufficient number of drops to fill your cup 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 5 Off-line streaming Application of large file transmission through a lossy network Delivery of a large data file to a motor vehicle through a satellite broadcast channel without a feedback – for example a recurrent updates of GPS maps 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 6 Off-line streaming Reliable data file transmission through a satellite channel As far as the car is permanently visible by the satellite there are no problems 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 7 Off-line streaming However the visibility of a car is usually fragmented and is arbitrary due to: Tunnels Whether conditions Underground parking 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 8 Off-line streaming Reliable data file transmission with digital fountain code - carousel One of the solutions is to broadcast the file in a carousel, so if the reception of the file is interrupted the car can retry it at the next go 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 9 Off-line streaming Large file transmission with carousel However with a sufficiently large file the probability that there will be interruption at every go is very high – there is a risk that the car never receives its file 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 10 Off-line streaming Large file broadcast with digital fountain code With digital fountain code everything is easy. The car just needs to collect a sufficient number of drops (any of transmitted checksum packets) to recover the file 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 11 Off-line streaming Digital fountain codes: Raptor Codes: satellite broadcast, MBMS in 3G communications Amin Shokrollahi, “Raptor codes”, International Symposium on Information Theory 2004, ISIT’04 LT codes: film footage transmission (Hollywood) Michael Luby, “LT codes”, Symposium on Foundations of Computer Science 2002, FOCS’02 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 12 Off-line streaming – unlimited buffering The benefice of off-line applications from FEC codes is spectacular The common thing in all off-line streaming applications: there is no hurry in receiving a piece of information and passing it further to the user Off-line applications using FEC employ Time Diversity: 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 13 Off-line streaming Time diversity: if data for information recovery is not collected at the present period of time… The remaining data can be collected later 2006-04-25 Later… ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan And later… 14 Real-time streaming In off-line streaming the receiver is permitted to hold data in a practically unlimited playback buffer In real-time streaming the situation is different: the fresh packets have a limited life time and must be delivered to the user ASAP 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 15 Real-time streaming In real-time streaming the receiver is not permitted to keep data too long in the playback buffer 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 16 Real-time streaming Several authors reported that: In real-time streaming FEC is applicable if the packet loss rate is below 5% Efficiency of FEC can be improved if combined with retransmissions FEC is not efficient during bursts The side effect from application of FEC (that is increase of congestion rates) is stronger than the improvements 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 17 Real-time streaming – references on application of FEC Several references on poor effect of FEC in real-time streaming : Ingemar Johansson, Tomas Frankkila, Per Synnergren, “Bandwidth efficient AMR operation for VoIP”, Speech Coding 2002 (FEC is efficient if losses are below 5%) Yicheng Huang, Jari Korhonen, Ye Wang, “Optimization of Source and Channel Coding for Voice Over IP”, Multimedia and Expo 2005, ICME’05 (combine FEC with retransmissions) Chinmay Padhye, Kenneth J. Christensen, Wilfrido Moreno, “A new adaptive FEC loss control algorithm for voice over IP applications”, Performance Computing and Communications Conference 2000, IPCCC’00 (not efficient during bursts) Eitan Altman, Chadi Barakat, Victor M. Ramos, “Queueing analysis of simple FEC schemes for IP telephony”, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies INFOCOM 2001 (not efficient for real-time streaming at all) 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 18 Real-time streaming versus Off-line streaming - résumé Application of FEC may result in slight performance … due to limited playback buffer In any case it is clear that: If a failure or a full congestion lasts longer than the playback buffer limit, even an infinite amount of redundant FEC packets cannot save the communication Failure time 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan Playback buffer 19 Real-time streaming – time diversity? Time diversity: that was turning FEC into a powerful method in off-line streaming Is useless for real-streaming 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 20 Real-Time streaming Playback buffer limit Reliable realTime streaming Path diversity Real-time streaming 2006-04-25 Data lost at the present period of time can be received at another period of time (buffering time scale) But it can be also received via another path (path diversity scale) All previous studies stressing the poor FEC performance assumed that the real-time communication follows a single path route Reliable Off-line streaming Time diversity ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 21 Path diversity Path diversity Buffering time is a scalar value – easy to imagine along an ax Path diversity depends on the multi-path routing topology … Time diversity 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 22 Path diversity Intuitively we imagine the path diversity ax as shown: zero Path diversity Single path routing 2006-04-25 Multi-path routing Multi-path routing Multi-path routing ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 23 Path diversity ax Single path routing 2006-04-25 zero There are already other studies showing that in real-time streaming FEC becomes applicable when an extra path is added to the single path Intuitively we imagine the path diversity ax as shown: The single path routing does not interest us and we remove it from our study Path diversity Multi-path routing Multi-path routing Multi-path routing ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 24 Applicability of FEC in twopath routes - references Qi Qu, Ivan V. Bajic, Xusheng Tian, James W. Modestino, “On the effects of path correlation in multi-path video communications using FEC over lossy packet networks”, GLOBECOM’04 Tawan Thongpook, “Load balancing of adaptive zone routing in ad hoc networks”, TENCON 2004 Rui Ma, Jacek Ilow, “Reliable multipath routing with fixed delays in MANET using regenerating nodes”, LCN’03 Rui Ma, Jacek Ilow, “Regenerating nodes for real-time transmissions in multi-hop wireless networks”, LCN'04 (coding at each intermediary node) Thinh Nguyen, Avideh Zakhor, “Protocols for distributed video streaming”, Image Processing 2002 (streaming from multiple servers) Thinh Nguyen, P. Mehra, Avideh Zakhor, “Path diversity and bandwidth allocation for multimedia streaming”, ICME’03 (transmission with Reed-Solomon codes via shortest path and an alternative – possibly corelated path) 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 25 Capillary routing As a method for obtaining multi-path routing patterns of various path diversity we relay on capillary routing algorithm For any given network and pair of nodes it produces layer by layer several multi-path routing patterns of increasing path diversity Path diversity = Layer of Capillary Routing 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 26 Capillary routing - introduction Capillary routing is constructed layer by layer First it offers a simple multi-path routing pattern At each successive layer it recursively spreads out the individual sub-flows of the previous layer The path diversity develops as the layer number increases 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 27 Capillary routing – definition Reduce the maximal load of all links 2006-04-25 Capillary routing is discovered by an iterative LP process First take the shortest path flow and minimize the maximum load of all links This will split the flow over a few main parallel routes ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 28 Capillary routing – second layer Reduce the load of the remaining links 2006-04-25 At the second layer identify the bottleneck links of the first layer …and minimize the flow of all links, except the bottleneck links of the first layer ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 29 Capillary routing – min-flow vs max-flow This LP formulation is completely valid, but is numerically instable We use another mathematically equivalent LP model to achieve the same results without numerical instabilities 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 30 Network samples The network samples for applying capillary routing are obtained from a random walk MANET Nodes are moving in a rectangular area If the nodes are sufficiently close and are within the range of the coverage there is a link between the nodes [diagram] 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 31 Capillary routing examples Here is an example of capillary routing on a small random walk ad-hoc network with 9 nodes [diagram] An example of capillary routing on a larger network with 130 nodes [diagram] 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 32 Redundancy Overall Requirement (ROR) To evaluate how good a given multipath routing pattern is for real-time streaming we measure the amount of adaptive FEC codes that the sender needs to transmit in order to combat non-simultaneous failures of all individual links in the given multi-path routing 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 33 ROR – static FEC We assume an application streaming the media with a little constant static tolerance for combating weak failures source packets redundant packets FEC block 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 34 source packets redundant packets ROR – static FEC FEC block The real-time streaming constantly tolerates packet loss rate 0<t<1 The FEC block length is FECt We assume Reed-Solomon MDS code 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 35 ROR – static FEC When the packet loss rate observed at the receiver exceeds the tolerable limit t … … the sender increases the FEC block size by adding more redundant packets and increasing the transmission rate 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 36 Redundancy Overall Requirement The overall amount of FEC packets during communication time is proportional: to the usual packet transmission rate of the sender to the duration of communication to the single link failure rate to the single link failure time and to a coefficient characterizing the given multi-path routing pattern 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 37 ROR - equation FECr (l ) ROR 1 lL | t r ( l ) 1 FECt This routing coefficient is computed according the above equation, where FECr(l) is the FEC transmission block size in case of the failure of link l FECt is the usual FEC block size of the real-time streaming 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 38 ROR coefficient Smaller the ROR coefficient of the multipath routing pattern, better the multi-path routing is suited for real-time streaming For a given pair of nodes, by measuring the ROR coefficient of different layers of the capillary routing – we can evaluate the benefice from the capilarization 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 39 ROR as a function of capilarization Average ROR rating 60 55 50 45 40 35 30 25 20 15 10 5 0 3.3% 3.9% 4.5% 5.1% 6.3% 7.5% capillarization 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan Here is ROR as a function of the capillarization level It is an average function over 25 different network samples (obtained from MANET) The constant tolerance of the streaming is 5.1% Here is ROR function for a stream with a static tolerance of 4.5% Here are ROR functions for static tolerances from 3.3% to 7.5% 40 ROR rating over 200 network samples 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan ROR function of the routing’s capillarization computed on several sets of network samples Except a few pathological cases capillarization of the routing results in reduction of overall FEC codes needed from the sender during the communication 41 Conclusions (1 of 2) Commercial real-time streaming applications do not relay on packet level FEC, since even heavy FEC cannot protect communication against a long failure on a single path Recent studies have shown applicability of FEC in real-time streaming if the media is streamed via two paths By studying a wide range of routing topologies we have shown that a proper choice of multi-path routing can make FEC extremely efficient 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 42 Conclusions (2 of 2) We introduced capillary routing algorithm offering steadily diversifying patterns We introduce ROR – a method for rating a routing pattern by a single scalar value Capillary routing can be applicable: 2006-04-25 to ad-hoc or sensor networks to mobile networks where the wireless content can be streamed to and from user via multiple base stations or to the public lossy internet (directly or with relay nodes) ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 43 Thank you ! Fault-Tolerance of Real-Time Streaming with Capillary Routing and FEC Emin Gabrielyan [email protected] Switzernet Sàrl and Swiss Federal Institute of Technology (EPFL) 2006-04-25 ICTTA 2006 – Capillary routing with FEC - Emin Gabrielyan 44