Network Coding over Lossy Links

===============================

Network coding assumes that channels are error free. In practice, network links introduce errors,that become visible to end hosts as packet losses. Thus, the  implicit underlying assumption in network coding is that the errors are masked by an error correcting scheme. Removing this assumption opens a number of questions.

A natural question is, whether we should jointly optimize the network coding and error correcting schemes. Using information theoretica tools it is easy to see  ([Yeung et al], [Tuninetti et al. ISIT 2005]) that this is indeed so.

A different angle of looking at this problem is, given an established routing scheme over lossy links, how can we use network coding techniques to realize benefits in terms of delay and achievable throughput.

In networks where packets get dropped, two main approaches are employed today. The first and more traditional approach is automatic repeat request (ARQ) schemes that, although capable of achieving optimal rate given perfect, delay-free feedback, are often inhibited by lost or delayed acknowledgments.

The second approach that has recently emerged relies on packet-level forward error correcting (FEC) schemes such as Raptor codes {Shokrollahi et al.]. Fountain codes possess a property that makes them particularly suitable for packet-level coding---they are rateless.  This means that, rather than being designed for a fixed code rate, they output a block of coded packets of potentially-infinite length for a fixed block of message packets.  Thus, the rate of the code can be adapted in real-time to the time-varying conditions that are common in packet networks. Moreover, there avoid the delay associated with the use of feedback. Thus, when the physical medium makes establishing good feedback links difficult---as is often the case in wireless and satellite networks---or when the application is simply very demanding---as is often the case in real-time applications---using such codes is the clear strategy of choice over using automatic repeat request (ARQ). However, Fountain codes do not achieve the optimal throughput because coding is end-to-end: packets are encoded at the source and decoded at the destination, while intermediate nodes are only allowed to replicate and forward packets.

Applying ideas from network coding in this context, i.e., allowing intermediate nodes to also form linear combinations, allows to achieve both the optimal rate and avoid the feedback delay at the same time. To this end, rate-less coding schemes that utilize intermediate node processing were recently proposed in [Lun et al.] and further developed in [Pakzad et al.].

A short description of these schemes can be found: click here

Looking towards next generation communication networks, schemes that operate at a network or application layer and employ low complexity processing at intermediate nodes, seem to have the potential to significantly improve the network reliability andefficiency,  and help better exploit the network resources. Such schemes might use routing, coding (FEC), feedback (ARQ), and possible combinations, and offer benefits in terms of delay, throughput, and computational resources.