Decoding Probability in Random Linear Network Coding with Packet Losses

We focus on a network where n sources send data to k destinations, through m≥ n relay nodes employing random linear network coding. The coefficients used to encode the data packets are extracted from a Galois field of size q. Unlike previous work, we consider that the relay nodes may not receive some packets due to link failures. This implies that a destination may be unable to successfully decode the received data packets due to both missing packets at the relays and linearly dependent coefficient vectors. In this scenario, we compute the exact probability of successful decoding at a destination node and we show the impact of the system parameters on the performance. In particular, our study highlights the fact that the network coding scheme behaves as an erasure correcting code, whose erasure correcting capability is determined by the number of available relays.