网络编码

网络编码是一种通过中继节点对接收到的信息进行编码来达到提高多播网络容量的技术。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出网络编码的概念。

在右图的网络拓扑中，s节点试图向${\displaystyle t_1,t_2}$组播两条消息x,y。设每条消息占用的带宽为1，每个节点之间的网络带宽也为1，那么每个节点之间只能同时传输一条消息。线路cd上会需要同时传输x,y，这在一般的传输方案中是行不通的，所以需要网络编码在c处将x,y异或，合成一条消息然后发送。

假设网络是有向的，执行线性网络编码时每个节点收到所有连入线路的数据后，再执行编码，然后把数据从连出线路发出。新的数据包括执行线性编码所用的系数以及合成后的数据。

例如组播源发送三条封包，${\displaystyle p_1=1}$，${\displaystyle p_2=2}$，${\displaystyle p_3=3}$。封包经过一系列的中间节点，目标节点收到的封包是${\displaystyle ((5,8,1),24),((2,3,7),29),((9,6,5),36)}$。目标节点对下列矩阵求解，可得${\displaystyle p_1,p_2,p_3}$的值。

或

随机线性网络编码可以取得更好的组播传输速率，较为实用。在实际网络中，节点会将来自连入线路的封包缓存起来，当节点需要发送封包时再将缓存的封包执行网络编码，然后发出。

例如节点A有2个上游节点X,Y，X向A发送了封包${\displaystyle ((2,2,1),2x_1+2x_2+x_3)}$(${\displaystyle 2x_1+2x_2+x_3}$是数据体，（2,2,1）是对数据体执行线性编码时所用的系数）,Y向A发送了封包${\displaystyle ((1,5,4),x_1+5x_2+4x_3)}$。当A需要发送数据时，便把缓存的这两个封包取出来，随机选择2个系数（如2和1），获得新的数据体${\displaystyle (2x_1+2x_2+x_3)\times <!--\; \times \; -->2+(x_1+5x_2+4x_3)\times <!--\; \times \; -->1=5x_1+9x_2+6x_3}$和新的合成系数${\displaystyle (2,2,1)\times <!--\; \times \; -->2+(1,5,4)\times <!--\; \times \; -->1=(5,9,6)}$。所以A就把合成后的数据体${\displaystyle 5x_1+9x_2+6x_3}$连同合成系数(5,9,6)，向下游节点发送出去。