Probabilistic forwarding of coded packets on networks

Topic_abstract: “Motivated by applications in sensor networks and the Internet of Things (IoT), we look into energy efficient broadcast mechanisms on distributed networks. We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has $k$ data packets to broadcast. The source encodes the $k$ data packets into $n \ge k$ coded packets. This encoding is such that any node in the network which receives at least some $k$ out of the $n$ coded packets will be able to retrieve the original $k$ data packets. The source transmits the $n$ coded packets to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability $p$. In our formulation, it suffices that a large fraction of the network nodes receives the broadcast. We say that a “near-broadcast” occurs, when the expected fraction of nodes that receive at least $k$ of the $n$ coded packets is close to $1$. The forwarding probability $p$ is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. We initially examine, how this minimum forwarding probability, and correspondingly, the expected total number of packet transmissions varies with the number of coded packets $n$. We further analyze the probabilistic forwarding of coded packets on two specific network topologies: binary trees and square grids. For trees, our analysis shows that for fixed $k$, the expected total number of transmissions increases with $n$. This indicates that there is no advantage of coding along with probabilistic forwarding on trees in terms of the total number of transmissions in the network. On the other hand, on grids, a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. The theory of site percolation is used to explain this behaviour on the grid. Other well-connected network topologies also exhibit similar behaviour as that of the grid which will also be discussed.”