|
1
|
- 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
|
|
2
|
- Emin Gabrielyan
- Switzernet Sŕrl and EPFL
- emin.gabrielyan@switzernet.com
- emin.gabrielyan@epfl.ch
|
|
3
|
- 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
|
|
4
|
- A file can be chopped into equally sized source packets
- Digital fountain code can generate an unlimited number of different
checksum packets
|
|
5
|
- 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
|
|
6
|
- 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
|
|
7
|
- However the visibility of a car is fragmented and is arbitrary due to:
- Tunnels
- Whether conditions
- Underground parking
|
|
8
|
- 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)
|
|
9
|
- 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:
|
|
10
|
- Time diversity: if full data for information recovery is not collected
at the present period of time…
|
|
11
|
- 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
|
|
12
|
- 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
|
|
13
|
- Time diversity: that was keystone for application of FEC in off-line
streaming
- Is useless for real-time streaming
|
|
14
|
- 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
|
|
15
|
- Buffering time is a scalar value – easy to imagine along an ax
- Path diversity depends on the underlying routing topology …
|
|
16
|
- Intuitively we imagine the path diversity ax as shown:
|
|
17
|
- Intuitively we imagine the path diversity ax as shown:
- The single path routing does not interest us and we remove it from our
study
|
|
18
|
- 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
|
|
19
|
- 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
|
|
20
|
- 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
|
|
21
|
- 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
|
|
22
|
- 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
|
|
23
|
- 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]
|
|
24
|
- 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]
|
|
25
|
- 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
|
|
26
|
- 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 0<t<1
- We assume Reed-Solomon code
- And compute accordingly the needed FEC block length = FECt
|
|
27
|
- 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
|
|
28
|
- 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
|
|
29
|
- 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
|
|
30
|
- 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)
|
|
31
|
- 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
|
|
32
|
- 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%
|
|
33
|
- 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
|
|
34
|
- 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
|
|
35
|
- 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
|
|
36
|
|
Notes
