Random Linear Network Coding
Random Linear Network Coding (RLNC) is a technique where intermediate network nodes mix packets together instead of just forwarding them.
Traditional networking: you send packets, routers forward them unchanged, receiver reassembles. If a packet is lost, you retransmit that specific packet.
RLNC: the source encodes data as k packets. Each transmitted packet is a random linear combination of the original k packets (over a finite field). Intermediate nodes can create new combinations from what they receive. The destination needs any k linearly independent combinations to decode the original data.
where are random coefficients and are the original packets.
Why this matters:
Resilience. You don’t need specific packets - any k independent combinations work. Packet loss doesn’t require retransmitting that particular packet, just sending more coded packets until you have enough.
Efficiency in multicast. With multiple receivers at different loss rates, the source doesn’t need to track who’s missing what. Just keep sending coded packets until everyone has enough.
Intermediate nodes can help. Routers can combine packets they’ve received, adding redundancy where the network needs it without coordinating with the source.
The tradeoff is computation - encoding and decoding require matrix operations. And the finite field size matters: too small and you risk linear dependence, too large and the overhead increases.
RLNC shows up in wireless networks, content distribution, and anywhere you’re dealing with lossy channels or multicast. The idea of mixing data in transit rather than preserving individual packets is a useful shift in thinking.