a23

Information about a23

Published on September 12, 2007

Author: Altoro

Source: authorstream.com

Content

Capillary Multi-Path Routing for reliable Real-Time Streaming with FEC:  Capillary Multi-Path Routing for reliable Real-Time Streaming with FEC GSA Pizza Research Talk by Emin Gabrielyan Friday, May 12, 2006 at 12:15 in INM 202 École Polytechnique Fédérale de Lausanne (EPFL) Switzerland Capillary Multi-Path Routing for Real-Time Streaming with Forward Error Correction:  Capillary Multi-Path Routing for Real-Time Streaming with Forward Error Correction Emin Gabrielyan Switzernet Sàrl and EPFL [email protected] [email protected] Structure of my talk:  Structure of my talk The advantages of packet level Forward Error Correction (FEC) in Off-line streaming of large data Difficulties arising in application of packet level FEC in Real-time streaming Proposed solutions Off-line streaming of a file on the example of Digital Fountain Codes:  Off-line streaming of a file on the example of 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 Digital Fountain Codes:  Digital Fountain Codes It is sufficient to collect almost as many checksum packets as there were source packets – and the file can be recovered Like with a water fountain: to fill your cup, you need to collect just a sufficient number of drops – no matter which drops Application: Large file delivery over satellite link:  Application: Large file delivery over satellite link For example delivery of recurrent update of GPS maps to thousands of vehicles There is no feedback channels Reception may require continuous visibility of 24 hours Arbitrary visibility loss pattern:  Arbitrary visibility loss pattern However the visibility of a car is fragmented and is arbitrary due to: Tunnels Whether conditions Underground parking Raptor codes in satellite transmission:  Raptor codes in satellite transmission Solution: broadcasting with digital fountain code If reception is interrupted – no problem, the missing packets will be collected later A digital fountain code example, called Raptor code, is designed in EPFL and is used in 3G mobile networks (MBMS) Unrestricted receiver buffering time:  Unrestricted receiver buffering time The benefice of off-line applications from FEC codes is spectacular Commonly: no need of immediate forwarding of the received information to the the user Reliable Off-line applications using FEC rely on Time Diversity: Time diversity:  Time diversity Time diversity: if full data for information recovery is not collected at the present period of time… Real-time streaming:  Real-time streaming In off-line streaming the data can be hold in the receiver buffer But in real-time streaming the receiver is not permitted to keep data too long in the playback buffer Long failures on a single path route:  Long failures on a single path route If the failures are transient and fragmental FEC can be useful If a failure or a full congestion lasts longer than the playback buffering time of the receiver, no FEC can protect the communication Real-time streaming – time diversity?:  Real-time streaming – time diversity? Time diversity: that was keystone for application of FEC in off-line streaming Is useless for real-time streaming Applicability of FEC in Real-Time streaming:  Reliable Off-line streaming Reliable real-Time streaming Applicability of FEC in Real-Time streaming Time diversity Playback buffer limit Real-time streaming Lost packets can be compensated by packets received at another period of time (buffering time scale) But they can be also received via another path (path diversity scale) Which can make application level FEC efficient also for real-time streaming Path diversity:  Path diversity Buffering time is a scalar value – easy to imagine along an ax Path diversity depends on the underlying routing topology … Path diversity ax:  Path diversity ax Intuitively we imagine the path diversity ax as shown: zero Path diversity Only multi-path patterns:  Only multi-path patterns Intuitively we imagine the path diversity ax as shown: The single path routing does not interest us and we remove it from our study zero Path diversity Capillary routing:  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 routing patterns of increasing path diversity = Layer of Capillary Routing Capillary routing - introduction:  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 Capillary routing – first layer:  Capillary routing – first layer Capillary routing is constructed 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 Capillary routing – second layer:  Capillary routing – second layer At the second layer identify the bottleneck links of the first layer These are the links whose load cannot be further reduced Then minimize the flow of all remaining links, except the bottleneck links of the first layer Capillary routing – algorithm:  Capillary routing – algorithm Identify the bottlenecks of the second layer …and at the third layer reduce the maximal load of all remaining links, except the bottlenecks of the first and second layers Repeat this iteration until all links of the communication path are enclosed in bottlenecks of the constructed layers Network samples:  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] Capillary routing examples:  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] Weak static and strong dynamic FEC:  Weak static and strong dynamic FEC To evaluate a multi-path routing pattern for real-time streaming we assume an application model, where the sender: Uses a small static amount of FEC codes to combat weak losses and Dynamically added FEC packets to combat strong failures Constant weak FEC codes:  Constant weak FEC codes We assume an application streaming the media with a little constant static number of FEC packets for combating weak failures Such that the real-time streaming constantly tolerates weak packet loss rate 0andlt;tandlt;1 We assume Reed-Solomon code And compute accordingly the needed FEC block length = FECt Strong dynamic FEC codes:  Packet Loss Rate = 3% Packet Loss Rate = 30% Strong dynamic FEC codes When the packet loss rate observed at the receiver below the tolerable limit t (let’s say 5%) the sender transmits at its usual rate But when the packet loss rate exceeds the tolerable limit, the sender increases the FEC block size by adding more redundant packets Overall number of redundant packets:  Overall number of redundant packets Assume a uniform probability of frequency of link failures Bigger the number of underlying links higher the total rate of link failures (shall we use shortest path routing then?) But we also must try to minimize the number of highly loaded links Redundancy Overall Requirement:  Redundancy Overall Requirement The overall amount of dynamically added extra 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 ROR - equation:  ROR - equation This routing coefficient is computed according the above equation, where FECr(l) is the FEC transmission block size in case of the complete failure of link l FECt is the default streaming FEC block size (tolerating weak failures) ROR coefficient:  ROR coefficient Smaller the ROR coefficient of the multi-path routing pattern, better is the choice of multi-path routing 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 capillarization ROR as a function of capilarization:  ROR as a function of capilarization 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% ROR rating over 200 network samples:  ROR rating over 200 network samples ROR function of the routing’s capillarization computed on several sets of network samples Each set contains 25 network samples Network samples are obtained from random walk MANET Almost in all cases path diversity obtained by capillary routing algorithm reduces the overall amount of FEC packets Conclusions (1 of 2):  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 By studying a wide range of routing topologies we have shown that a proper choice of multi-path routing can make FEC extremely efficient We introduced capillary routing algorithm offering steadily diversifying patterns We introduce ROR – a method for rating a routing pattern by a single scalar value Conclusions (2 of 2):  Conclusions (2 of 2) In general: the path diversity increases the communication footprint and the overall failure rate of the underlying links It may also increase the overall number of FEC packets required for protection of communication However the routing patterns built by capillary routing algorithm decrease substantially the overall amount of required FEC packets Thank you !:  Thank you ! Questions ?

Related presentations


Other presentations created by Altoro

Robot Different Types
07. 01. 2008
0 views

Robot Different Types

guzman
18. 04. 2008
0 views

guzman

PublicFinancevsPubli cChoice
13. 04. 2008
0 views

PublicFinancevsPubli cChoice

2779JacobFrenkel
10. 04. 2008
0 views

2779JacobFrenkel

Chapter 02 Warming the Earth
07. 04. 2008
0 views

Chapter 02 Warming the Earth

ElectronicRetailersA ssociation9
27. 03. 2008
0 views

ElectronicRetailersA ssociation9

mining
26. 03. 2008
0 views

mining

Austria
21. 03. 2008
0 views

Austria

poc presentationv ny
28. 09. 2007
0 views

poc presentationv ny

PPT Jon Sigurdson
12. 10. 2007
0 views

PPT Jon Sigurdson

Workshop Wintersport
12. 10. 2007
0 views

Workshop Wintersport

2006 2007 Calender
06. 09. 2007
0 views

2006 2007 Calender

Protein for Athletes
06. 09. 2007
0 views

Protein for Athletes

lecture 18 bread fermentation
04. 10. 2007
0 views

lecture 18 bread fermentation

ustman
09. 11. 2007
0 views

ustman

Slavery
11. 12. 2007
0 views

Slavery

The Model Hockey Program
06. 09. 2007
0 views

The Model Hockey Program

WAWF Deployment Review
07. 11. 2007
0 views

WAWF Deployment Review

soybeans2007
07. 11. 2007
0 views

soybeans2007

Association HEP Training
06. 09. 2007
0 views

Association HEP Training

Portion Distortion
12. 09. 2007
0 views

Portion Distortion

compositae2006r
07. 12. 2007
0 views

compositae2006r

The Cold War and Domino Theory
19. 12. 2007
0 views

The Cold War and Domino Theory

nelson NATO
25. 12. 2007
0 views

nelson NATO

Fri 04 Killar
29. 12. 2007
0 views

Fri 04 Killar

Oslo 1
02. 01. 2008
0 views

Oslo 1

fruit diseases05
04. 01. 2008
0 views

fruit diseases05

HARRY S TRUMAN
28. 12. 2007
0 views

HARRY S TRUMAN

hayek45
12. 09. 2007
0 views

hayek45

ETC 2004 10 25
06. 09. 2007
0 views

ETC 2004 10 25

CT303 NetworkingDevices
28. 12. 2007
0 views

CT303 NetworkingDevices

IDIS
10. 12. 2007
0 views

IDIS

lect04Slides
14. 12. 2007
0 views

lect04Slides

missions
24. 02. 2008
0 views

missions

360
12. 09. 2007
0 views

360

3 4apr07 SDD Chief
29. 11. 2007
0 views

3 4apr07 SDD Chief

Talk EX8 6
12. 03. 2008
0 views

Talk EX8 6

LoD
24. 12. 2007
0 views

LoD

Roch Stuart
24. 02. 2008
0 views

Roch Stuart

sp10002 3
19. 02. 2008
0 views

sp10002 3

FY2006TourismMediaPl an
10. 10. 2007
0 views

FY2006TourismMediaPl an

Thompson
12. 09. 2007
0 views

Thompson

SMI Innov
17. 06. 2007
0 views

SMI Innov

Salvo Presentation
17. 06. 2007
0 views

Salvo Presentation

SALTO Inclusion 2005
17. 06. 2007
0 views

SALTO Inclusion 2005

athletics
17. 06. 2007
0 views

athletics

JohnBare 11sept07
04. 12. 2007
0 views

JohnBare 11sept07

pizza talk 2006
12. 09. 2007
0 views

pizza talk 2006

Selectividad2007
17. 06. 2007
0 views

Selectividad2007

Phil Borgeaud final
06. 09. 2007
0 views

Phil Borgeaud final

Chelsie and Samantha
02. 11. 2007
0 views

Chelsie and Samantha

PLVol1
26. 11. 2007
0 views

PLVol1

ACHA Rules of Emphasis 8 12 06
06. 09. 2007
0 views

ACHA Rules of Emphasis 8 12 06

Renuka Ramnath
12. 09. 2007
0 views

Renuka Ramnath

Overview of Japan Steel Industry
09. 10. 2007
0 views

Overview of Japan Steel Industry

the10mostbeautifulsu rahs
02. 10. 2007
0 views

the10mostbeautifulsu rahs

prez2
21. 11. 2007
0 views

prez2

PlanningMinorityComm unities
26. 02. 2008
0 views

PlanningMinorityComm unities

PPT for recruits 03 2
06. 09. 2007
0 views

PPT for recruits 03 2

siklejog2
17. 06. 2007
0 views

siklejog2

Amuse Promotional materials
12. 10. 2007
0 views

Amuse Promotional materials

GDSv15Training
03. 01. 2008
0 views

GDSv15Training