论文标题
网络上编码数据包的概率转发
Probabilistic Forwarding of Coded Packets on Networks
论文作者
论文摘要
我们考虑通过通过无声通信链接连接的节点网络广播信息的方案。网络中的源节点具有一些数据包可供广播。它以$ n $编码数据包的方式编码这些数据包的方式使网络中的任何节点在$ n $编码数据包中接收到任何$ k $的任何节点都将能够检索所有原始的数据包。来源将$ n $编码的数据包传输给其单跳邻居。网络中的所有其他节点都遵循一个概率转发协议，其中它以一定的概率$ p $将先前未受欢迎的数据包转发给所有邻居。我们说，如果收到至少收到$ n $ n $编码数据包的$ k $的预期节点的预期分数接近$ 1 $，则来自来源的信息将经历``近广播''。选择了转发概率$ p $，以最大程度地减少近距离广播所需的预期传输总数。我们研究给定的$ k $，这种最低转发概率和相关的预期数据包传输总数因$ n $而变化。我们专门分析了两个网络拓扑上编码数据包的概率转发：二进制树和方格网格。对于树木，我们的分析表明，对于固定的$ K $，预期的传输总数随$ n $而增加。另一方面，在网格上，明智的$ n $选择大大减少了近乎广播所需的预期传输总数。在其他良好连接的网络拓扑（如随机几何图和随机常规图）中也观察到类似于网格的行为
We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has some data packets to broadcast. It encodes these data packets into $n$ coded packets in such a way that any node in the network that receives any $k$ out of the $n$ coded packets will be able to retrieve all the original 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$. We say that the information from the source undergoes a ``near-broadcast'' if 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 study how, for a given $k$, this minimum forwarding probability and the associated expected total number of packet transmissions varies with $n$. We specifically analyze the probabilistic forwarding of coded packets on two 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$. On the other hand, on grids, a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. Behaviour similar to that of the grid is also observed in other well-connected network topologies such as random geometric graphs and random regular graphs
