Least FEC Routing

 

2006-05-09

EG

 

Introduction:

 

We assume a streaming media over a multi-path routing; where the sender adaptively increases its transmission rate each time there is a failure of a link in the communication footprint. We assume that the transmission blocks carry a large number of packets and that the sender uses a capacity approaching codes (such as LDPC or Raptor). Therefore in order to combat packet loss rate p the sender needs to increase its transmission rate by a factor of about  with a very little excess of packets which we ignore in this context. According to a given routing pattern a link l carries  portion of the traffic. Assuming a uniform probability of failures for links, Redundancy Overall Requirement (ROR), defined in this case as follows:

 

…is the proportionality coefficient of the number of redundant packets that the sender will need to transmit during the streaming session in order to completely protect the communication.

 

Different multi-path routing patterns result in different ROR coefficients. In the animated figure below, we present the least FEC routing between a pair of nodes in a random walk Mobile Ad-hoc Network (MANET):

 

The routing is found via Linear Programming (LP) model, by replacing each physical link by several virtual links of increasing cost. Larger the number of virtual links heavier the LP model is, but also more accurate the computed routing pattern will be. The chart below shows how the ROR coefficient of the routing pattern decreases as the number of virtual links increases in the model:

[xls]

 

Files and Folders:

 

-         randomwalk.txt is an AMPL script for generating the random walk MANET samples and storing the data in an MDB database

-         shortestpath.txt is an AMPL model generating the shortest path route

-         diagramshp.txt is an AMPL script visualizing the MANET with shortest path routing

-         least-FEC-routing.txt is an AMPL model for building the least FEC routing pattern

-         diagramfec.txt is an AMPL script for visualizing the MANET with least FEC routing pattern

-         slideshow.txt generates PDF and GIF files from PS files previously built by the diagram scripts

-         ZIP file of this web site

 

See also capillary routing:

 

-         Capillary Routing papers

-         Capillary Routing download pages

 

 

*   *   *