Haste: Practical Online Network Coding in a Multicast Switch是我大三暑假时完成的论文，被IEEE INFOCOM 2010接受。论文全文以及slides可以在我的主页homepage.fudan.edu.cn/~syang上找到。

这篇论文介绍了如何在交换机上使用网络编码提高组播的吞吐率。同时，该文摒弃了传统的随机线性编码而给出了只使用异或运算的Haste算法，将解码延迟从O(N)降低到了0，同时将解码复杂度从O(N²)/包降低到了O(1)。最后该文展示了一个硬件仿真平台，能够在一台PC机上模拟交换机处理真实的UDP数据包，并能进行不编码调度，随机线性码或者Haste算法。其仿真结果表明使用Haste能够有效提高交换机的吞吐率。

下面给出一个简单的例子介绍网络编码如何提高交换机吞吐率。

 

上图是一个支持多播的交换机的介绍。一个数据包可以同时被多个输出端口接受。

但是一个输入端口不能同时发送两个不同的数据包

一个输出端口也不能同时接受两个不同的数据包。

有了以上这些限制，我们考虑下图这样的数据包传输。蓝色和黄色的数据包从输入1发送到所有输出端口。红色，黑色，灰色数据包从输入端口2分别到输出端口1，2，3。这样几个数据包若不使用网络编码，需要4个时间单位才能完成。

但是我们可以令绿色等于黄色+蓝色，如下图所示。

输出端口1可以通过绿色减去黄色获得蓝色，输出端口2可以通过绿色减去蓝色获得黄色。这样一来，这样几个数据包就能在3个时间单位内完成传输了。

对于更大规模的交换机，传统的网络编码采取的是随机线性码，即令E_i = C_i1P₁ + C_i2P₂ + C_i3P₃ + ... + C_inP_n。其中P是数据包，C是随机选取的系数，E是编码后的数据包。这样，收集齐n个线性无关的编码后的数据包，就可以通过解方程的形式计算出原来的数据包。这样做的一个致命缺点是解方程的复杂度很大，并且在收齐第n个包之前，前面n - 1个数据包都是无用的，会造成较大的延迟。

Haste的特点是采用了机会编码，其仅使用异或运算。编码的数据为e = P1 xor P2 xor P5 xor P7, 如果一个输出端口已解出P1, P5, P7，那么P2 = e xor P1 xor P5 xor P7。我们通过一种随机的顺序来选取数据包，假设随机后的顺序为Pi1, Pi2, Pi3.. Pin。首先令e = Pi1。然后我们进行循环j，若e xor Pij能够被所有的输出端口解码（i.e. p1 xor p2 xor p3能够被解码当且仅当该端口至少收到p1,p2,p3中的两个），那么令e = e xor Pij。这样，我们保证所有的数据包都是能够被立即解码的。关于该算法的分析和进一步优化可以参考论文。

下面这个图展示了在硬件仿真平台下测试的吞吐率的结果（更多实验结果可以参考论文）。传统的网络编码性能有所下降，这是因为使用软件实现传统网络编码有巨大的计算量，实验的CPU不能承受。事实上，最新的使用GPU进行随机线性网络编码也仅能实现不到300MBps的吞吐率，而交换机的吞吐率都是上G的。Haste，由于其轻量的计算复杂度（O（1）/包），能够实际地运用在交换机上。

如果对该论文有什么不明白的，或者有进一步的建议，欢迎与我联系。

转载本文请联系原作者获取授权，同时请注明本文来自杨双科学网博客。
链接地址：https://wap.sciencenet.cn/blog-441887-319862.html

上一篇：我的个人科研博客介绍
下一篇：对未来的小小理想