On Randomized Network Coding

TLDR

Randomized network coding for multicasting over networks, where nodes independently choose linear mappings, was first analyzed for acyclic delay‑free networks, yielding exponentially decreasing error‑probability bounds based on algebraic network coding and network flow theory. The study extends previous error‑probability results to networks with cycles and delay, and derives a tighter bound for acyclic networks based on connection feasibility in a related unreliable‑link problem. The authors analyze randomized network coding where each node independently selects random linear mappings over a field, and they relate the error probability to a connection‑feasibility problem in a network with unreliable links. They derive a success‑probability bound for randomized network coding in link‑redundant networks with unreliable links, expressed as a function of link‑failure probability and redundancy level.

Abstract

We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links over some field. This approach was first described in [3], which gave, for acyclic delay-free networks, a bound on error probability, in terms of the number of receivers and random coding output links, that decreases exponentially with code length. The proof was based on a result in [2] relating algebraic network coding to network flows. In this paper, we generalize these results to networks with cycles and delay. We also show, for any given acyclic network, a tighter bound in terms of the probability of connection feasibility in a related network problem with unreliable links. From this we obtain a success probability bound for randomized network coding in link-redundant networks with unreliable links, in terms of link failure probability and amount of redundancy.