Advanced Computer Network Review(5)——COPE

本文参考资料来自：
1.论文原文《XORs in The Air: Practical Wireless Network Coding》(SIGCOMM’06)
2.课程演示文稿

根据复习提纲，对于COPE应该弄懂以下几个问题：
1.理解butterfly网络
2.理解COPE的编码算法
3.理解COPE的一个实例

全文的一个核心是利用了异或(XOR)运算的一个特点，即$a\oplus b\oplus b=a$，即原始值经过两次异或某一个相数值后会变成原来的值，这是本文使用的编码技术的一个根本原理。

---

1.理解Butterfly网络
文中抛出Butterfly网络是为了说明网络编码(network encoding)技术确实对提升网络吞吐率有切实的好处。何谓网络编码技术？文中给出的解释如下：

网络编码技术允许路由器在转发数据包之前混合各个数据包中的信息内容

Butterfly网络的示意图如下：

限制和条件如下：
1.S1想把ai送至R1和R2，S2也想把bi送至R1和R2
2.任何链路上一个时刻只能发送一条信息

如果不使用网络编码技术，那么中间链路就会成为瓶颈链路。因为一个时刻只能有一条信息经过链路，那么S1向R2的发送动作和S2向R1的发送动作就会挤在中间的链路上，一共等两个单位时间才可以全部通过中间链路(逐一通过中间链路)。

但是如果使用了网络编码技术(这里特指使用异或运算将多个数据包混合的情况)，就可以在中间瓶颈链路上传送$a\oplus b$的混合数据包(一个单位时间)，此混合数据包到达R1和R2之后，再和来自两条边缘链路的数据包进行异或运算完成解包。

这个Butterfly网络的小例子相当于对本文做了一个引入，让人们相信网络编码技术确实可以有效地改进网络吞吐率和性能。

---

2.理解COPE的编码算法
COPE就是一种专用于无线网状网络的编码技术，它主要结合了三个核心技术：
2.1 Opportunistic Listening

我不知道这里的Opportunistic Listening如何恰如其分地翻译出来(机会主义监听？笑)。传统的无线网络通信分析中往往将无线网络中的广播特性有意屏蔽掉，而是抽象成简单的点到点通信来简化分析。

但COPE反其道而行之，不仅要直面无线链路的广播特性，还要利用这样的广播特性来让各个网络设备之间互通有无。道理也很简单，既然使用网络编码技术来混合数据包，就得确保接收者可以将原始数据包成功解码出来，这时候发送者必须得知道接收者(下一跳)已经持有的数据包情况。

这就是通过opportunistic listening来实现的，COPE中将各个节点的监听模式设置为混杂模式，此模式下节点将接收任何监听到的数据包，从而获悉什么节点拥有什么数据包的信息。不仅如此，各个节点之间还要发送广播消息来告知邻居自己在本地持有的数据包。

所以我们看到，COPE中使用了两种方式：

• 将设备设置为混杂模式
• 发送广播消息来互通有无

来努力地让各个节点能够及时掌握其它邻居节点持有的数据包信息，从而为后期的编码过程提供足够的决策信息。

但是也应该看到，这个过程是opportunistic的，尽管努力去做，但是还是不能保证此时获得的信息就一定是完备无误的，关于为什么，接着往下看。

2.2 opportunistic coding
在一个节点本地将数据包混合，其可能的组合是很多的，那么最终应该选择哪一种方案呢，文中直接了当地给出了编码的目标：

maximize the number of native packets delivered in a single transmission, while ensuring that each intended nexthop has enough information to decode its native packet

翻译过来，我们追求的点有两个：

• 确保下一跳路由器有足够的信息来进行解包
• 在满足上述情况的基础上，尽可能混合更多的包

一个节点要做出混合包的最终决策，就得必须掌握邻居节点持有哪些包，掌握了邻居节点持有情况之后就可以从中选择一个能够混合最多数据包的策略。这里就引入了一个自然而然的问题，那就是如何确定的知道邻居点有哪些包呢？

其实在2.1部分提出的两个方法就是做这个事情的，但是它还不是完备的。因为网络有时会有严重拥塞的情况发生，这时邻居节点广播过来的报文可能会被堵在网络中。如果本地节点没有接收到邻居节点持有数据包的最新消息，就会导致它做出一个非最优甚至是无法解包的决策失误。

2.3 Learning Neighbor State
那如何缓解上述的情况呢，一个字，猜！

其实在无线网络中，路由器始终动态地观察着网络中所有链路的质量，链路的质量有不同的评价指标，但常用的评价指标是成功交付的概率(说白了就是不丢包不出错的问题，这不是废话吗:)，越容易成功交付，链路质量越高，代价越小。

COPE在无法确定邻居节点是否有具体的数据包时，它就默认此邻居拥有数据包的概率为此数据包的上一跳和其邻居之间链路的成功交付概率。有点绕，但也不用特别细究，就当作某一个概率值吧，这个信息会被节点认为是邻居拥有某一数据包的概率，这在后面的算法中会用到。

下面就可以看看编码算法的细节了！

2.4 Dive into Packet Coding Algorithm

编码算法的设计中遵循了三个要义：

• 绝不延迟转发来等待混合机会

如果当前要转发的数据包没有混合机会，则直接转发，而绝不被动等待到有混合机会出现再转发。

• 混合时优先选择长度相近的包

混合长度接近的包会更加节省网络带宽，但是如果真的没有长度相近的包，那么把长度较短的数据包填充之后再和长数据包混合也是没问题的。

• COPE永远不会将下一跳相同的两个包混合

这个也是很显然的，因为这样做的话下一跳没法解包，所以混合数据包的机会一定分布在下一跳不同的数据包之间。

为了更加高效地完成混合数据包的决策，COPE在实现时为每个邻居节点引入了一对虚通道专门用来存放下一跳不是当前邻居的数据包。一对儿是因为虚通道的引入还考虑了长度，小于100bytes的数据包被分在一个队列中，剩下的长数据包放在另一个队列中，这样做可以更快地找到长度合适的可以混合的包。

其他的设计考量包括包的乱序，这个COPE通过一个模块来保证数据的有序到达，按下不表。最后就是尽可能地确保邻居有尽可能高的概率可以完成解包工作，这个我们上面已经提到了，对于能够确定邻居拥有的包，这个概率就是1，对于不能确定邻居是否拥有的包，就通过链路质量去猜，这个概率显然<1。我们设置一个阈值G(e.g 0.8)，在执行混合包的动作前，算算如果混合了这个包，会不会使得解出包的概率P小于这个阈值，从而决定要不要混这个包。

写到这里，可以引出完整的算法了：

写到这里，突然觉得上面那个例子没必要讲了(它太简单了)…偷个懒吧:)
感谢陪伴我的《贝加尔湖畔》
Love & Peace, Good Night!