P2P网络中的网络编码

我不想撒谎，随着我对P2P网络中文件共享研究的深入，写我的周日刊物变得越来越难。我几乎把我醒着的所有时间都花在写这篇文章上，到一天结束的时候，我已经没有更多的脑力来开始写这些文章中的一篇了。幸运的是，我在一个如此令人兴奋的领域工作，以至于我总是可以选择一周来一直在探索的事情之一，然后开始写下它。这本出版物就是这样，我将在这里分享我对P2P网络中的网络编码方案的兴奋之情。

网络编码是一种网络技术，它对传输的数据进行编码和解码，以增加网络吞吐量、减少延迟并使网络更加健壮。在网络编码中，对数据应用代数算法来累积各种传输。接收到的传输在其目的地被解码，并且数据的原始形式被恢复。这些代数算法可能会带来一些开销，但它允许我们在传输中做一些很酷的事情，比如使用不同的路径发送不同的片段，这样只要接收器获得最小数量的片段，它就可以重建原始数据。

网络编码已经在很多通信领域中被证明是有用的：无线网状网络、消息传递网络、存储网络、多播流网络以及许多其他场景，在这些场景中需要将相同的数据传输到多个目的地节点，包括文件共享对等网络。网络编码方案在对等网络上的应用可能是具有挑战性的，但幸运的是，许多人已经“玩弄”了它，所以为了我的研究，它们值得进行更深入的研究。

在我们开始讨论业务之前，让我们先用一个简单的示例来说明网络编码的好处。请看下图中的网络拓扑。假设S想要向R1和R2发送两条消息<；a>；和<；b>；。S有两个对等连接，因此它选择并行传输这两条消息，每条链路一条。A和C通过它们的所有链路广播它们的数据包，导致网络泛滥。R1通过路径S-A-R1接收消息<；a>；，而R2通过S-C-R2接收消息<；b>；。问题出现在B-D链路上。B将几乎同时接收数据包<；a&>和<；b&>；，因此它必须选择首先转发哪一个。如果选择转发<；A&>，R2将比B早一个时隙完成这两个消息的接收，反之亦然，如果B选择先转发<；b&>(分别参见右图和左图)。

因此，S试图通过其链路传播其消息的转发，以尝试负载平衡和并行化它们的传输，但是由于网络的底层拓扑结构，在B-D链路中形成了一个瓶颈，该瓶颈迫使消息最终被顺序转发(而不是S最初的意图，即并行化负载)。更甚的是，在这种情况下，R1接收消息两次，R2接收消息两次，导致重复消息、冗余和带宽浪费。

但别担心，这就是网络编码的用武之地！如果当B几乎同时接收<；a>；和<；b>；时，它会对这两个消息应用简单的代数算法(例如XOR)，以便能够同时转发这两个消息，该怎么办？他将能够发送新的分组<；c>；=<；a>；异或(XOR)；b>；，而不是必须按顺序发送一条又一条消息。B将此消息转发给D，而D将组播<；c&>到R1和R2。现在，R1和R2分别具有<；a>；和<；c>；和<；b&>；和<；c>；和<；b&>；=<；c>；XOR<；a>；和<；a>；=<；c>；XOR<；b>；和<；a>；=<；c>；和<；a>；=<；c>；XOR<；b>；和<；a>；=<；c>；

使用这一简单的方案，在一个时隙中减少了传递两个消息所需的时间，同时从网络中删除了重复的消息，从而更有效地利用了带宽。瞧啊！这个简单的技巧允许我们有效地将两个消息并行发送到其目的地，并避免底层的瓶颈。

当然，这是一个非常简单的例子。在更复杂的场景中，使用更复杂的网络拓扑，在网络中实现这些优势所需的操作要高级得多。这些“高级技术”中最常用的一些例子是，例如，随机线性网络编码(RLNC)和矢量网络编码。在RLNC中，传出分组是原始分组的线性组合，因此每个编码分组包含数据加系数。RLNC可以以分布式方式应用，其中每个节点可以独立且随机地从伽罗瓦域(GF)中选择系数。GF对印刷机非常有用

这是不需要动脑筋的，但是在P2P网络中，没有一台服务器可以下载我们想要的所有内容，我们需要询问网络并发现存储组成所需内容的不同部分的对等点。因此，用于选择和传输片段的算法显著影响网络中文件共享的性能。在某些情况下，我们甚至可能面临无法下载全部内容的事实，因为一篇文章要么非常罕见，要么在网络上不可用。

最酷的是，在网络编码的帮助下，P2P文件共享中的一个常见问题可以被部分颠覆，因为前面提到的这个问题可以被部分颠覆。与分发原始数据片段不同，对等体共享编码片段，其中每个编码片段是原始片段的线性组合。以这种方式，请求者对等体不需要请求特殊的数据片段，因为所有编码片段对对等体的益处几乎相等。网络中的对等点可以盲目地从其他对等点下载编码片段，而不必太担心这是否是他正在寻找的。当拥有足够数量的编码片段时，可以重建原始文件。使用该方案，避免了最罕见的片段问题，并且潜在地减少了文件的下载时间。这是一个很好的例子，说明了网络编码在P2P环境中是如何受益的。

你们中的许多人可能会想，“但是这种网络编码技术非常类似于块存储中擦除编码方案的使用，对吗？”您是完全正确的，这两个领域是相连的，并且共享它们的许多基础，但对我来说，网络编码不仅仅是存储中的擦除编码。与其只关注存储内容的智能方式以提高未来的传输效率，还可以动态应用网络编码技术，这样，即使片段以原始格式存储，没有任何“花哨”的编码技术，PATH中的对等点也可以足够智能地组合和积累接收的片段，以尝试和改进内容的传输，并更有效地利用带宽(参见上面的示例)。

将网络编码应用于P2P网络并不简单，而且会带来一些计算开销方面的损失。这篇很棒的论文的摘录很好地说明了这种开销，它展示了如果使用得很天真，网络编码会对BitTorrent节点造成什么影响：

使用网络编码时，编码的片段是分布的，而不是原始片段。由于系数是随片段一起接收的，因此必须对照对等点已接收的所有先前系数集对其进行测试，以检查新片段是否包含任何先前未知的信息。如果接收到的编码片包含有益信息，则称其为创新的；否则，将丢弃该编码片。此外，使用网络编码在接收到足够的片段之后解码文件的计算量更大。BitTorrent中的文件解码非常简单。每一块都要单独检查验证，然后直接存储在硬盘上，反之，网络编码中的解码过程要等到收到所有需要的块后才能进行。因此，解码文件需要求解许多线性方程。随着文件大小的增加，求解这些方程的成本也会增加。例如，下载一个被分割为1000个片段的3 GB文件，每个接收节点上所需的磁盘读取操作为3000 GB。同时，BitTorrent系统只需要写入3 GB的数据。

因此，尽管网络编码可能令人兴奋，但将其应用于无法提前计划网络动态的非结构化网络可能并不像看起来那么容易。

在出版之初我就告诉过你，我找不到时间写这些出版物，但事实是，一旦我开始写我喜欢的话题，我就停不下来了。这篇文章的初稿长达3.500多字。在它的第一个版本中，我甚至用例子介绍了迄今为止在P2P网络中使用的五种类型的网络编码技术，但我不得不克制自己，不让每个人都感到无聊。我认为这对今天的网络编码来说是绰绰有余的。如果你们中的许多人对这个主题表现出兴趣，我可以拿回那份很长的草稿，写一篇“P2P网络中的网络编码，第二部分”。

我真的希望你和我一样对P2P网络中的网络编码的想法感到兴奋，希望这本出版物能给你带来很多想法(希望你能与我分享这些想法，以帮助我进行研究)。当然，如果我最终使用了这些网络编码方案中的任何一个，我会让您知道并与您分享结果：)同时，我强烈推荐这篇文章(这是我撰写本文时的主要参考文献)。下周见！