Probabilistic Forwarding Over Networks: To Code Or Not To Code?
Prof. Navin Kashyap
Indian Institute of Science
Consider a network (i.e., a connected graph) with a large number of nodes, one of which is distinguished as a source node. The source node has a fixed number, k, of data packets to be broadcast to all nodes in the network. The k data packets are encoded into n >= k coded packets (using an MDS code over a large enough field), such that any k of the n coded packets are sufficient to recover the original k data packets. The source transmits all n packets to its one-hop neighbours. Thereafter, the nodes follow a probabilistic forwarding protocol: Each node, upon receiving a particular coded packet for the first time, forwards it to all its one-hop neighbours only with a certain probability p. This probabilistic forwarding happens independently across all nodes and packets. We declare such a probabilistic forwarding protocol to be useful if the expected fraction of network nodes that receive at least k of the n coded packets is at least 1-\delta for some small \delta > 0.
We would of course like to operate the protocol at the smallest value of the probability p that makes the protocol useful, as this would minimize the expected total number of transmissions across all network nodes. It turns out that the amount of redundancy, n-k, introduced by the coding scheme significantly influences this minimum expected number of transmissions. Simulation results indicate that over network topologies that are tree-like, the introduction of redundancy in the form of coding is not beneficial; but over topologies that are well-connected, the introduction of some (but not too much) redundancy can significantly reduce the expected total number of transmissions needed. We describe our preliminary analysis of this phenomenon.
This talk is based on work with B.R. Vinay Kumar and Roshan Antony.
Navin Kashyap received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1995, the M.S. degree in Electrical Engineering from the University of Missouri-Rolla in 1997, and the M.S. degree in Mathematics and the Ph.D. degree in Electrical Engineering from the University of Michigan, Ann Arbor, in 2001. From November 2001 to November 2003, he was a postdoctoral research associate at the University of California, San Diego. From 2004 to 2010, he was on the faculty of the Department of Mathematics and Statistics at Queen's University, Kingston, Ontario, Canada. In January 2011, he joined the Department of Electrical Communication Engineering at the Indian Institute of Science, where is currently a Professor. His research interests lie primarily in the application of combinatorial and probabilistic methods in information and coding theory. Prof. Kashyap served on the editorial board of the IEEE Transactions on Information Theory during the period 2009-2014. He is at present an Associate Editor for the SIAM Journal on Discrete Mathematics. He has been appointed as a Distinguished Lecturer of the IEEE Information Theory Society for 2017-2018.