陈静怡， 冯 伟， 吴 杰

(复旦大学计算机应用技术系，上海200433)

0 引 言

由于互联网上大量相同或相似的内容被网络边缘的用户多次请求，造成了数据在网络上的重复传输，导致了大量的冗余流量，不但消耗网络带宽，而且降低了互联网的效率。随着存储设备容量不断扩大，运算设备性能不断提高、价格不断降低，在互联网引入网内存储设施，使网络具有记忆功能已经成为可能，具有存储功能的互联网能够实现网络冗余流量消除技术，它记录网络上传输的数据，识别被重复传输的数据，从而消除冗余传输，起到减少网络流量、提高网络性能的作用。代理缓存[1]、CDN[2]、CNF[3]等都属于网络冗余流量消除技术的范畴。其中，与协议无关的网络冗余流量消除技术运行在网络层或传输层，存储设备中的缓存对象为数据包。最早的协议无关网络冗余流量消除技术由Spring等人于2000年提出，运行于一对路由器之间，后常被用于消除ISP或局域网与商业网之间的连接链路或者数据中心与其备份数据库之间的连接链路上的重复字节传输[4]。2008年，Anand等人提出了把Spring等人的方法整合到整个互联网的所有路由器中[5]，这样，协议无关的网络冗余流量消除技术将被作为一项基础服务而运用到所有的点到点(即路由器到路由器)数据包传输中。此后，Anand等人又对其中的指纹运算方法和解码位置做了优化[6-7]，使得运用于全网的协议无关网络冗余流量消除算法有更快的速度，而且更适合于全网范围运用。2010年，Anand等人发表了关于端到端冗余流量消除的论文[8]，这篇论文基于这样一个理论：75%拥有相同片段的两个数据包具有相同的源地址和目的地址，即来自同一对网络上的端点。他们选择 SAMPLEBYTE指纹选择算法和最大匹配算法来实现端到端冗余流量消除，但是这样会大量占用服务器端的内存空间。在本篇论文中，论述了一种新的指纹选择算法：贪婪指纹选择算法，配合以块匹配算法，能够减少服务器端和用户终端的内存消耗，并且冗余消除的有效性与Anand等人的算法相近。

1 端到端冗余流量消除技术的目标

端到端冗余流量消除技术与传统的网络层冗余流量消除技术相比，把一部分的计算量转移到用户终端，因此在设计算法时，要着重考虑用户终端的性能限制，尽量减少用户终端的计算量和空间占用。因此，端到端冗余流量消除技术的目标为：

(1)在用户终端处能够方便的解码数据包：用户终端可能是智能手机、笔记本电脑、PAD等设备，这些设备受限于电池容量和计算能力。因此在设计算法时应尽量把计算集中在高性能的服务器端，而使得用户终端能够方便的解码被编码的数据包。尽量少的占用用户终端的计算资源。

(2)在服务器端能快速的编码：服务器端需要把检测出拥有重复传输片段的数据包经行编码：去除曾经传输过的数据包片段，并以小的结构体代替，用以告诉用户终端从曾经发送过的哪个数据包中恢复被去除的数据包片段。服务器端需要同时编码和多个用户终端之间传输的数据包，因此编码算法需要足够快速，以不至于造成数据包的延迟发送。

(3)在两端都应尽量减少内存的占用：服务器端要分别记录和大量用户终端之间的数据，每一个用户终端都要在服务器端的内存中占有一定的空间，而在用户终端，内存受限于所使用的物理机器性能。因此在两端都必须尽量减少内存的使用，设计合理的数据结构和算法使得所占用的内存尽量的小是端到端冗余流量消除技术必须考虑的一点。

2 算法设计

端到端冗余流量消除技术的算法设计包括服务器端算法设计和用户终端算法设计。服务器端负责缓存曾经发送过的数据包于数据包库中，并对当前要发送的数据包与数据包库中的包进行比对，检测出其中的重复片段，并对数据包进行编码后发送，编码后的数据包指出了哪一片段由于曾经发送过而从数据包中去除。用户终端收到数据包后对其进行解码，还原被去除的数据包片段，并缓存此数据包，用于下次可能的解码操作。服务器端的编码可能只是告诉用户终端，从曾经发送过的哪个数据包的哪个位置开始恢复当前的数据包，所以客户端只是简单的解码包和缓存包，而大量的比对运算都发生在服务器端，这样能满足端到端冗余流量消除技术的设计要求。

在服务器端对数据包的编码可以分为两步：

(1)代表指纹选择：在数据包的重复检测中，每一个数据包都由多个指纹来代表，数据包之间的比对实际是能代表数据包的指纹之间的比对。每一个数据包可以由多个指纹来代表，每个指纹能代表数据包中的某一个固定长度的片段，所有数据包的代表指纹形成了代表指纹库。然而，数据包的众多片段每个都能产生一个指纹，显然不可能把所有的指纹都存入代表指纹库，如何从指纹中选择一些来代表整个数据包，选出的指纹应有代表性，这是代表指纹选择算法的要求。下文中描述了5种指纹选择算法，每个都在有效性和计算量上有所差别。

(2)匹配：匹配算法利用当前数据包的代表指纹与代表指纹库中的指纹做比对，如果在代表指纹库中有相匹配的指纹，表示服务器端曾经传输过相似数据包给客户端，两个数据包中的相同片段由匹配的代表指纹来表征。下文中的两个匹配算法在内存占用和有效性上有所差别。

2.1 指纹选择算法

指纹选择算法中参数w表示指纹算法的输入字符串的字节数，w字节的字符串能产生一个指纹，如果一个数据包的负荷部分长度为L个字节，那么总共能产生L-w+1个指纹，数据包与数据包之间的比对实际是数据包的指纹与数据包的指纹之间的比对，w是数据包之间能被检测到的重复字节的最小长度，通常w被定在12字节到64字节之间。一个数据包的L-w+1个指纹不能全部存储在内存中，否则，随着数据包负荷部分的增大，指纹的数量也呈线性增长，所以必须要从L-w+1个备选指纹中选取1/p*(L-w+1)个指纹作为数据包的“代表指纹”，选出的代表指纹首先用于和指纹库中的指纹做比对，然后被存入指纹库，用于以后的指纹比对操作。服务器端的指纹库(见图1)中缓存的就是这些代表指纹，而对于那些没有被选中的(p-1)/p*(L-w+1)个指纹则直接丢弃，其中p表示代表指纹的选择率。一个数据包能有多个代表指纹，而一个代表指纹只代表一个数据包。代表指纹的选择必须有代表性，能够尽量多的检测出两个数据包之间的相同片段。

图1 服务器端缓存结构

2.1.1 MODP

早期的协议无关的网络冗余消除算法中指纹的选择都使用MODP算法，它基于Rabin移位指纹算法。MODP首先对数据包负荷中的所有w个连续的字节做移位指纹算法，即每w个连续的字节计算指纹之后右移一个字节继续对w个连续的字节做移位指纹。对于最后得到的所有L-w+1个指纹，如果模p余0则被选为代表指纹，被选为代表指纹的概率为1/p。这样选择指纹的好处是当一个内容被少量的增加、删除或修改之后，拆分成数据包在网络上传输，路由器选择的代表指纹总是相同的，不会因为数据在整个内容中位置的改变而改变。但是MODP算法也有3个缺点：①必须对每w个字节都计算一次指纹，即使是那些没有被选为代表指纹的指纹。②代表指纹的选择是基于参数p的，造成了数据包中被选中的代表指纹数量不平均，代表指纹在数据包中的位置分布不平均。③能被检测出的重复字节集中于那些其指纹模p余0的字节，而对于其他重复字节则无法检测。

2.1.2 MAXP

MAXP指纹选择算法把数据包负荷中的每p个字节分为一段，p个字节中数值最大的一个字节被选出，对由这个字节起始的w个字节做指纹算法(指纹算法可能是SHA-1、RSA算法、Jenkins哈希算法等)。MAXP算法克服了MODP算法的3个缺点：首先MAXP算法不必对每w个字节进行一次指纹算法，而只需对那些被选择的w个字节做指纹算法，减少了运算量；其次，MAXP算法平均在每p个字节中选择一个代表指纹，使得代表指纹在整个数据包负荷中基本是均匀分布的，而且每个数据包负荷都根据自己的字节长度拥有相应数量的代表指纹；最后，代表指纹的选择依据具有一定的相对性，与绝对的值p无关，因此能检测出的重复片段并不局限于某些字节。实验表明MAXP算法不但克服了MODP算法的一些缺点，而且其对冗余流量检测的有效性却并不差于MODP。

2.1.3 FIXED

MODP和MAXP算法的共同缺点是它们的计算量都相对较大：MODP算法需要对每w字节都计算指纹，MAXP算法需要在每p字节长度中计算数值最大的字节，但他们的优点是都根据一定长度数据块片段的数值来选择其代表指纹。FIXED算法弥补了MODP和MAXP的缺点：选择数据包负荷中的第p个字节，第2p个字节，第3p个字节…作为指纹运算的起始字节，指纹的选择只和位置有关，而和数值无关。尽管FIXED方法速度快，但是由于代表指纹的选择与数据包的内容(数值)无关，所以对于文件细微的插入、删除和修改，它都无法检测出重复数据，使得其有效性不如MODP和MAXP。

2.1.4 SAMPLEBYTE

上述3种代表指纹选择算法，其中MAXP和MODP算法对于传输内容的细微修改有很好的健壮性，但是运算量较大，而FIXED算法与传输内容无关，但是运算量小。SIMPLEBYTE算法结合了上述3种方法各自的优点。SIMPLEBYTE算法事先有一张256项的查找表，每个不同的字节对应一项，查找的结果或为1，或为0，表中值为1的项的数量应为256/p。算法依次把数据包负荷中的字节在查找表中查找，如果当前字节的值为1，那么从这个字节起始的w个字节将作为指纹运算的输入，其结果为一个代表指纹，然后从此字节开始跳过p/2个字节继续依次把字节按查找表中查找，直到数据包末尾。SIMPLEBYTE运算量小，只需做线性的查找工作，而根据实验可知其有效性与MAXP和MODP相当。

2.1.5 贪婪指纹选择算法

贪婪指纹选择算法在SAMPLEBYTE算法的基础之上做了改进：当由SAMPLEBYTE算法选出的代表指纹在指纹库中有匹配的指纹时(如图2所示)，即指纹p1与指纹库中已经存在的某个指纹相同，表示片段1在曾将的某个数据包中已经被传送过，则把数据包中匹配片段的下一片段(片段2)也做指纹算法，其得到的指纹p2也作为代表指纹(见图2)。

图2 贪婪指纹选择算法

如果p2也和指纹库中的某个指纹匹配，则片段3也将被做指纹运算，并被选为代表指纹，以此类推(如图3所示)。贪婪指纹选择算法基于这样一个思想：两个数据包中的某一片段是相同的，那么他们各自的下一片段也很有可能是相同的。这样选择出来的代表指纹能更大限度的检测出重复，而且使得代表指纹不局限于SAMPLEBYTE查找表，代表指纹的选择更具有平均性。在贪婪指纹选择算法中，指纹选择率p可能小于其实际值。

图3 贪婪指纹选择算法伪代码

2.2 匹配算法

2.2.1 最大匹配算法

选出代表指纹后，服务器端把每一个代表指纹都和指纹库中的指纹做比对，如果有相同的指纹存在于指纹库中，表示最近发送的数据包与当前数据包有相同的数据片段，相同部分的长度至少为w字节。把相同部分逐字节的往左和往右拓展，最终相同部分的数据被从当前数据包中去除，并以{相同数据起始位置，相同数据长度}2个属性组成的短记号代替。

在最大匹配算法中，服务器端需要缓存每个完整的数据包，用以指纹匹配成功时能向左右拓展相同数据片段的长度，因此称为最大匹配算法。服务器端的内存分为两部分，一部分用以存储代表指纹，称为代表指纹库，另一部分用以存储数据包，称为数据包库。用户终端只需要缓存数据包，而不需要缓存指纹，服务器端的数据包库与用户终端的数据包库高度一致，因此服务器端只需要告诉用户终端被去除的数据片段在数据包库中的起始位置和长度，就能在用户终端还原数据包，大部分的计算量都在服务器端完成，简化了用户终端的操作。

2.2.2 块配算法

在块匹配算法中，检测出两个数据包中的相同数据片段后不需要向左右拓展相同部分的长度。指纹所代表的数据片段就被认为是检测出的一个完整的重复片段。因此，在服务器端不需要数据包库，只需要指纹库，而在用户终端也不需要数据包库，取而代之的是数据块库。服务器端需要知道每一个数据块在用户终端的数据块库中的什么位置，当检测到匹配的指纹时，只需要告诉用户终端从数据块库的什么位置还原数据包，每一个数据块的长度总是固定的w字节。

与最大匹配算法相比，块匹配算法大大减少了在服务器端和客户端的内存占用，但是重复检测的效果显然不如最大匹配算法。

在Anand等人的论文中他们考虑到算法的效果选择了最大匹配算法，但是这样服务器端为每个用户终端都需要建立一个数据包库，当用户数量巨大的时候，会大量的占用服务器端的内存。同样的，在用户终端，数据包库比数据块库占用更多的内存，当一个用户与多个服务器端建立连接，那么采用最大匹配算法的话会消耗更多的内存。

3 实 验

在实验中共模拟了2种指纹选择算法：SAMPLEBYTE和贪婪指纹选择算法，以及2种匹配算法：最大匹配算法和块匹配算法。其他 3种指纹选择算法由于已经被证明效果差于SAMPLEBYTE而不在实验考虑范围内。在本次实验中，我模拟并比较了3种端到端冗余流量消除算法：第1个采用SAMPLEBYTE作为指纹选择算法以及最大匹配作为匹配算法，第2个采用 SAMPLEBYTE作为指纹选择算法以及块匹配作为匹配算法，最后一个采用贪婪指纹选择算法以及块匹配算法。Anand等人在论文中采用了第4个算法，尽管第一个算法会在服务器端和用户终端占用大量的内存，而第2个算法由于其冗余消除的效果不理想而没有被采用。第3个算法用于和前两个算法做对比，以证明贪婪指纹选择算法的运用能够一定程度的弥补前两个算法的各自缺点。

实验参数选择：w为32字节；p为64；指纹算法选择Jenkins哈希算法，它可以产生很好的分布，输出为32个bit；SAMPLEBYTE查找表中第0、42、48、104项设为1，根据对实际数据包的分析，这4项在所有255个字符中出现的概率约为1/64，符合参数p的要求。在最大匹配算法中，预留给数据包库的内存大小为16MB，由于指纹选择率p为64(如果采用贪婪指纹选择算法，p会略小于其实际值，但为了实验的方便，在贪婪指纹选择算法中，仍然按照p=64来计算指纹库中代表指纹的大约个数)，16M/64=262144，所以整个数据包库产生的代表指纹约有262144个。如果把指纹库的内存大小预设为1.25M，那么每个指纹结构占用5字节，其中3个字节用以指向所代表的数据片段在数据包库中的位置(2^24=16M)，另外两个字节由于不足以表示一个完整的指纹，所以把指纹库的索引也作为指纹表示的一部分，索引用以表示指纹的前18位，后14位由剩下的2个字节表示，当两个指纹的前18位冲突时，则原来的指纹结构将被新的覆盖。在块匹配算法中，只留下了指纹库而不再需要数据包库，同时指纹库中的数据包偏移量字段也不再需要，因此指纹库的大小缩减到0.5MB，相比于最大匹配算法，服务器端为每个用户终端消耗的内存由65.25MB下降为0.5MB。

4 实验结果

总共分析了从4个网站采集的TCP数据包，称为数据1到数据4。

(1)内存消耗

在服务器端，采用最大匹配所需的内存消耗是采用块匹配的130.5陪，在用户终端也达到了8倍(见表1)。最大匹配所需的内存远远大于块匹配算法，在服务器端如果用户数量增加，那么所消耗的内存也会急剧增加。

表1 冗余消除算法内存消耗

(2)冗余消除效果

3个端到端冗余流量消除算法各自的效果见表2。除了数据4外，其他3个数据中算法3结果都与算法1相接近。究其原因，从表2中可以看出，数据4的冗余消除量远远小于其他3个数据，当数据集中的冗余量较小时，可能大部分的冗余都高度分散，造成了贪婪指纹选择算法的设想前提不存在，因此引起效果下降，所以对于数据4，算法3的效果与算法2相接近。当数据包中的冗余量越大时，贪婪指纹选择算法的效果就越好。

表2 冗余消除算法

在实验中，算法3的服务器端内存消耗只有算法1的约1/130，其指纹库内存消耗也只有算法2/5，相信如果加大算法3的指纹库内存，使其与算法1的指纹库所消耗内存相同，那么算法3的效果应该会更好。

5 结束语

端到端冗余流量消除技术是当前的新兴研究领域，其属于协议无关的冗余流量消除技术，但是与以往的技术不同，其工作在传输层，并且把所有的运算量都放置在网络的边缘(服务器和用户终端)。

本文针对当前服务器端内存消耗巨大这一问题，提出了一种新的指纹选择算法：贪婪指纹选择算法。它认为两个数据包中相同片段的下一片段很有可能也是相同的，基于这一原理，下一片段的指纹也将被选为代表指纹。根据实验结果，贪婪指纹选择算法使得服务器端的内存消耗减少了约130倍，客户端的内存消耗也仅为原来的1/8，同时当数据集中的冗余量较大时，冗余消除的效果能达到原来的85%-88%，数据集中的冗余量越大，贪婪指纹算法带来的效果越好。如果加大服务器端的指纹库，则贪婪指纹选择算法的效果能更加接近于现有的端到端冗余流量消除算法。

[1]Squid.Squid web proxy cache[EB/OL].http://www.squid-cache.org/,2010.

[2]Pallis G,Vakali A.Insight and perspectives for content delivery networks[J].Communications of the ACM,2006,49(1):101-106.

[3]Liu H,Zhang Y,Raychaudhuri D.Performance evaluation of the"cache-and-forward(CNF)"networkformobile content delivery services[C].Dresden:International Conference on Communications Workshops,2009:1-5.

[4]IT Facts.WAN optimization revenues grow 16%[EB/OL].www.itfacts.biz/wan-optimization-market-to-grow-16/1205/,2004.

[5]Anand A,Gupta A,Akella A,et al.Packet caches on routers:the implications of universal redundant traffic elimination[J].ACM SIGCOMM Computer Communication Review,2008,38(4):219-230.

[6]Anand A,Sekar V,Akella A.SmartRE:An architecture for coordinated network-wide redundancy elimination[C].New York,NY,USA.Proceedings of the ACM SIGCOMM conference on Data communicatio,2009:87-98.

[7]Anand A,Muthukrishnan C,Akella A,et al.Redundant in network traffic:Findings and implications[C].New York,NY,USA:ACM Sigmetrics,2009:37-48.

[8]Aggarwal B,Akella A,Anand A,et al.EndRE:An end-system redundancy elimination service for enterprises[C].San Jos:USENIX Symposium on Networked Systems Design and Implementation,2010.