网络数据包级重复数据删除算法的研究和实践

⃝⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 5（2019）131www.elsevier.com/locate/icte一种用于数据包级重复数据删除的尹明根大韩民国汉城国民大学计算机工程系接收日期：2018年4月18日;接受日期：2018年在线发售2018年摘要网络数据包上的冗余消除或去重需要大量的计算资源来通过检查每个数据包中的每个字节来找到重复内容的基本单元（称为块）在本文中，我们提出了第一个恒定时间分块算法，将每个数据包分成预定义数量的块，而不管数据包的大小。此外，我们提出了最佳的实施实践，通过选择分块，指纹和哈希表算法的最佳组合，数据包级重复数据删除。通过与实际流量的实验，我们确认，吞吐量提高了三倍，甚至与国家的最先进的计划。c2019韩国通信与信息科学研究所（KICS）。Elsevier B.V.的出版服务。这是一个开放获取CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：分块算法;数据包捕获;网络安全1. 介绍删除重复和重复数据（称为重复数据删除）被广泛用于节省存储空间和网络带宽[1，2]。在存储系统中，相同或相似文件的原始副本仅保存一份，并为每个副本分配索引。根据最近对文件级冗余的研究，Microsoft和EMC生产主存储系统和辅助存储系统中分别有50%和85%的数据是冗余的[2]。数据包级冗余消除技术可以为企业和大学访问链路以及连接繁忙Web服务器的链路提供平均15-60%的带宽节省在本文中，我们专注于在网络层中移除数据包上的冗余，即数据包级重复数据删除[1，3]，但主要思想可以应用于其他应用程序。数据 包级 重复 数据 删除 有两 个主 要应 用： 广域 网（WAN）优化[1，4]和数据包记录[3，5]。WAN优化是通过一对称为WAN加速器的网络设备实现的，它们可以在发送端减小数据包大小，并恢复减小的数据包电子邮件地址：mkyoon@kookmin.ac.kr。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2018.05.005在接收器侧。WAN加速器最初是在互联网接入线路不快、网络带宽稀缺的情况下开发的。然而，由于必须始终有效地利用网络带宽，因此该应用继续被广泛使用。来自发送方的传出数据包被分成多个块，并且在哈希表中查找块的哈希值（称为指纹）。如果在表中找到指纹，意味着该块已被重复，则其内容将被替换为比原始值小的哈希值和元数据（以字节为单位）。第二个应用程序是从网络线路捕获数据包，并将其保存在存储中，用于安全取证或网络管理[3，5]。由于现代高速网络传输大量数据包，因此需要相应的存储空间来保存所有捕获的数据包。最近的一项研究表明，重复数据删除可以显著减少蜂窝网络和互联网中数据包捕获所需的存储空间[3，5]。与WAN优化的情况一样，更新散列表以存储重复的块。请注意，可以恢复已消除重复数据的数据包，并且可以按照[3]中的说明构建哈希表。数据包级重复数据消除的基本思想是在数据包中找到重复的子部分（称为块），并将其替换为小于原始块的索引值2405-9595/c2019韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。132M. Yoon/ICT Express 5（2019）131=-Fig. 1. Chunking算法的比较。(a)固定大小的组块是快速的，但有边界移动的问题。(b)可变大小分块可以解决这个问题，但需要为每个字节进行一定量的计算（c）本文提出的恒定时间分块可以缓解这个问题，时间复杂度为O（1）;只有第一个和最后一个块分别被可变大小和反向分块识别，这留下了一个大的中间块c2。在尺寸上。因此，每个数据包应该首先被分成块。然后，应该尽可能多地用它们对应的索引具有挑战性的问题是如何有效地找到重复的子包。最先进的方案依赖于分块算法，该算法将每个数据包划分为不重叠的子部分，并识别要用索引值替换的重复块问题是分块是CPU密集型的，因为每个字节都需要一定量的计算[1，3，5]。时间复杂度为O（n），时间复杂度为O（n）。最近在[3]中提出了最好的数据包级重复数据删除方案，这是与本文最密切相关的工作，但其最大吞吐量约为每个CPU核心2 Gbps。在本文中，我们提出了一个新的分块算法，可以在一个恒定的时间，无论数据包的大小。据我们所知，这是第一个时间复杂度为O（1）的分块算法通过对真实数据的实验表明，该方案在保持去重效果的同时，显著提高了分块算法的处理速度;与现有方案相比，该方案的性能更好，分块、指纹和哈希表算法的最佳组合使处理速度提高了3倍以上。此外，我们强调，所提出的方案是基于软件的，因此可以实现为网络功能虚拟化在广泛的硬件设备，包括现代网络系统，服务器和商品PC。2. 恒时组块在本节中，我们提出了一种新的分块算法，它可以在恒定的时间内运行，而不管数据包的大小。到据我们所知，这是第一个 时间复杂度为O（1）我们首先解释当前的组块算法，然后详细介绍了所提出的计划。2.1. 现有的组块算法许多组块算法已经被研究和提出。它们可以分为两类，固定大小的组块和可变大小的分块，分别如图1（a）和（b）所示。在图中示出了两个类似的分组，表示为分组1和分组2，其中块表示为ci。请注意，第二个数据包前面有一个额外的字节通过这个简单的例子，我们比较了三种组块算法，包括所提出的方案。在固定大小分块中，数据包被分成多个相同大小的块。这种最简单的分块算法运行速度很快;然而，当在数据包的开头插入或删除少量字节时，它的效果很差，这被称为边界移位问题[1]。例如，在图1（a）中没有生成冗余块，因为第二分组的一个附加字符导致每个块与第一个块不同。固定大小的分块不考虑窗口的内容。我们将窗口大小表示为w; w 3和w 2分别用于固定大小组块和可变大小组块，如图所示。1.一、可变大小分块可以通过以基于内容的方式分割数据包来解决边界移位问题;滑动窗口贯穿整个数据包，同时计算每个窗口内的校验和。Rabin当校验和满足一定的概率条件时;例如，当校验和以三个连续的'0'位开始时，我们会发现块之间存在一个“0”。图1（b）显示了三个字符串a0a1，a5a6和a7a8满足条件。已经提出了各种分组级分块算法，并且可以在最近的调查论文[1]中找到它们的细节。2.2. 恒时组块我们观察到，到目前为止，所有的分块算法都对每个数据包中的每个字节执行一定量的校验和计算。虽然Rabin的滚动哈希函数是最广泛用于分块的，但它的效率不足以满足需要高速计算或在资源受限的环境中工作的应用程序。最近的组块算法提高了处理速度，但其时间复杂度仍为O（n）。这种缓慢的分块过程限制了数据包级重复数据消除的性能，甚至M. Yoon/ICT Express 5（2019）131133现有技术方案的最大吞吐量为每个CPU核心2 Gbps[3]。在本文中，我们提出了一个恒定的时间分块al-出租m的数据包级重复数据删除。我们称之为三向分块，因为每个数据包都被分成三个块。我们强调可以使用任何预定义数量的块而不是三个，这将使算法复杂度保持在恒定水平。然而，我们的实验与真实的互联网流量表明，三路分块是足够的，以实现良好的处理速度和重复数据删除效果。实验结果表明，在与[3]相同的计算环境中，所提出的三路分块方案的吞吐量达到每CPU核6 Gbps。流量冗余模式的观察促使我们研究并提出了三路分块算法。已知业务冗余具有很强的时间和空间局部性。相同的对象在客户端和服务器之间重复传输，例如，如在Web业务、P2P多媒体数据传输中所观察到的。在某些情况下，相同的对象简单地生成相同有效载荷的分组序列然而，通信协议通常可以插入某些类型的元数据，通常在通信协议的开始处，其可以消耗几个字节的时间信息、用户特定标签、会话id等，这导致仅具有少量字节的通过实验，我们通过观察Web流量和文件传输协议包证实了这一性质。三向分块的目标是有效地减轻边界移位问题，这主要是由数据包前端区域的少量字节引起的。数据包冗余模式的观察意味着，我们可以找到更多的重复内容周围的中心部分的数据包，而不是在开始和结束区域。我们可以在从两端移除第一个和最后一个块之后获得较大的中间块。如果两个数据包在有效载荷方面看起来相似，那么它们的中间块很可能具有相同的请注意，我们不能直接使用固定大小的组块，因为它肯定会导致边界移动问题。三路分块算法可以通过使用任何可变大小的分块算法来找到第一个和最后一个分块。例如，我们可以使用Rabin为了有效地找到最后一个块，我们提出了反向分块的新思想，其中滑动窗口从数据包中的最后w个字节开始并向后移动。与可变大小分块类似，反向分块为每个w字节的窗口计算校验和值，以找到块之间的字节数。注意，当在三向组块中找到第一个块时，反向组块就完成了我们观察到，任何可变大小的组块算法可以很容易地转换到它的反向版本，同时保持原来的计算效率。例如，众所周知，Rabin图1（c）显示了当窗口大小为2时，三路分块如何找到第一个和最后一个块。注意字符串0a1和7a8的值动态地为第一个和最后一个块创建两个分隔符。packet1和packet2都生成相同的中间块c2。因此，三向分块可以解决由数据包开始处的少量改变字节引起的边界移位问题。应该提到三向组块的局限性这个想法来自于对Web和文件传输等流行协议的启发式观察。我们通过使用真实的互联网流量的实验来验证其有效性，如下一节所述。然而，三向分块在传输相同的大对象时，如果修改了数据包的中间部分，则不能很好地用于网络协议。3. 实验在本节中，我们将提供实验结果，展示三向组块如何优于现有方案。 此外，最佳的实施实践的重复数据删除，找到最佳组合的分块，指纹，哈希表算法。我们确认，与[3]中报告的最佳数据包级去重引擎相比，三向分块的最佳实现将总吞吐量提高了三倍以上，同时保留了冗余消除效果。测量了两个评估指标，即以Gbps为单位的处理速度（吞吐量）和重复数据删除率（DER），如[3]中所报告的。DER被定义为以下大小的比率：将数据包中删除的部分恢复到原始数据包中。例如，DER为0.4意味着40%的数据包有效载荷被去重消除。吞吐量由一个CPU核心生成。我们在Intel Xeon E5-2630（两个2.6 GHz六核CPU）服务器上实现了[3]中报告的数据包记录应用程序，该服务器具有64 GB DDR3内存。该硬件与[3]中使用的硬件相同，用于确保吞吐量的公平比较。在2016年10月的一周内，来自校园网络的真实互联网流量被捕获并进行了重复数据删除，类似于[3]中使用的流量跟踪。大部分流量与Web服务器和文件传输协议相关。在第一组实验中，将三向组块与固定大小和可变大小组 块 算 法 进 行 了 比 较 。 RabinMD5 代 码 来 自 OpenSSLv1.0.1.e。使用链表管理哈希表冲突。我们将这三种算法分别表示为实 验 结 果 如 图 2 所 示 。 通 过 对 “ 可 变 大 小Rabin+LL+MD5”和“固定大小+LL+MD5”的比较从图中，我们确认，三向组块运行速度比固定大小的组块，其DER是一样高的可变大小的组块。小的块大小将导致可变大小方案具有大的134M. Yoon/ICT Express 5（2019）131图二、可 变 大小组块、固定大小组块和三向组块的比较。左边的图显示了以Gbps为单位的处理速度，右边的图比较了重复数据消除率（DER）。Rabinx轴表示（平均）块大小。图3.第三章。三 路分块方案的比较，具有不同的哈希生成选项（Rabin vs AE），指纹（MD5 vs SipHash）和哈希表（链表vs冲突容忍）。左边的图显示了以Gbps为单位的处理速度，右边的图比较了重复数据消除率（DER）。的x轴指示（平均）块大小。存储块值的开销。这解释了三向组块的处理速度随着平均组块大小的增加而略有下降，因为第一个组块和最后一个组块的大小这个大小可以在固定大小的组块中直接确定，而平均组块大小可以通过校准滑动窗口大小和在可变大小的组块中找到一个错误的概率来调整[1，3]。与三向分块不同，“可变大小Rabin+LL+MD5”和“固定大小+LL+MD5”的比率更少的块和MD5操作。请注意，三路方案需要恒定的处理时间，同时将数据包分为三个部分。由于中间部分的大小可能很小或很大，其校验和计算仍然需要不同的处理时间。在第二组实验中，我们找到了分块、指纹识别和哈希表生成的最佳组合。即使是最先进的方案[3]，每个CPU核心的最大吞吐量也只有2 Gbps在本实验中，我们找到了数据包级重复数据删除的最佳实践;此外，我们优化了三路分块，以实现超过6 Gbps的吞吐量。为此，我们尝试了一种替代算法，分块、指纹识别和哈希表生成。Rabin由于最近的一项研究表明MD5不适合数据包级指纹识别，其吞吐量较低[5]，因此我们将其替换为SipHash，SipHash是最近设计的用于检查短消息和数据包完整性的快速伪随机数生成函数[8]。此外，我们用[3]中报道的冲突容忍哈希表取代了链表哈希表。图3显示了第二次实验的结果。实现了四个不同版本的三向分块;第一个版本使用Rabin的滚动哈希来获得三个块，链表哈希表和MD5指纹。第二个版本使用AE分块，链表哈希表和MD5指纹。第三种方案使用AE分块、链表哈希表和SipHash进行指纹识别。最后的方案是结合AE分块、碰撞容忍哈希表和SipHash实现的。这四个版本显示了重复数据消除性能如何逐步提高我们确认，最终版本将吞吐量提高到高达6 Gbps，这是三倍的速度比在[3]中报道的最先进的方案产生的。M. Yoon/ICT Express 5（2019）1311354. 结论在本文中，我们提出了第一个恒定的时间分块算法的数据包级的数据重复数据删除分为三个不重叠的数据包大小无关的块。该算法在去除数据冗余的同时，大大提高了处理速度，节省了CPU资源此外，我们发现了分块、指纹和哈希表算法的最佳组合，与最先进的方案相比，处理速度提高了三倍以上致谢本研究由基础科学研究计划通过韩国国家研究基金会（ NRF ） 资 助 ， 由 科 学 部 ICT 未 来 规 划（2016R1A2B4009083）资助。利益冲突作者声明，本文中不存在利益冲突引用[1] Y. Zhang ， N. Ansari ， 论 与 协 议 无 关 的 数 据 冗 余 消 除 ， IEEECommun.监视器家教（2014年）。[2] W. Xia，Y. Zhou， H. Jiang，中国粘蝇D. Feng，Y.华岛，澳-地胡角Liu，Y. Zhang，FastCDC：一种用于数据去重的快速高效的内容定义分块方法，载于：USENIX年度技术会议论文集，2016年，第100页。101-114[3] S.- H. Shin，J.- M.郑，H。Kim，J. Lee，J.- H.金岛，智-地金，M。Yoon，PrIDE：一个独立于协议的数据包记录重复数据删除引擎，IEEE Netw。30（6）（2016）42-48.[4] N.T. Spring ， D.Wetherall ， A protocol-independent technique foreliminat- ing redundant network traffic，in：Proceedings of the ACMSIGCOMM，2000.[5] J.李，S. Lee，J. Lee，Y. Yi，K. Park，FloSIS：一个高度可扩展的网络流捕获系统，用于快速检索和存储效率，在：USENIX年度技术会议，2015年。[6] 作案手法李明，随机多项式指纹识别，计算机技术研究中心，北京，1981。[7] Y. Zhang，H. Jiang，中国粘蝇D.冯，W. Xia，M. Fu，F. Huang，Y.黄氏Y. Zhou，AE： 一种用于快速和带宽高效数据去重的非对称极值内容定义分块算法，见：IEEE INFOCOM会议记录，2015年。[8] J. - P. Aumasson，D.J. Bernstein，SipHash：a fast short-input PRF，in：International Conference on Cryptology in India，2012，pp. 489-508