基于包性质的局域网冗余数据消除技术分析

潘有顺 王开建

(1.茅台学院公共基出部，贵州 遵义563000) (2.茅台学院酿酒工程自动化系，贵州 遵义563000)



基于包性质的局域网冗余数据消除技术分析

潘有顺1王开建2

(1.茅台学院公共基出部，贵州 遵义563000) (2.茅台学院酿酒工程自动化系，贵州 遵义563000)

局域网已经在当前企事业单位信息化建设中扮演了一个重要的角色。但是在其通信过程中有大量的冗余数据存在，占用了带宽，降低了效率。论文通过分析数据包的性质，针对局域网提出了一种基于包性质的冗余数据消除技术。它将独立与共享缓存机制相结合，利用冗余阈值对低容量数据包进行过虑处理。

局域网；冗余数据；冗余消除；冗余数据消除技术

0 引言

在网络通信过程中，学者们通过对通信数据的研究分析，发现用户在使用网络传递的信息中有大量的冗余数据存在。冗余数据不仅占用了网络软硬件资源，而且降低了整个网络的通信性能。学者Breslau[1]等人提出网络中 Web 对象数据被再次访问的机率与其过去被访问的次数成正比。如：代理缓存、Web 缓存、CDN、Ditto、CNF等。它们都属于对象冗余消除技术范畴。其中Web 缓存是应用最广泛的对象冗余消除技术。它采用访问数据对象在时间方面的局部性原理，通常布置在离用户终端较近区域，将用户访问过的数据对象进行缓存并对其设置一定的缓存期与替换算法。若有再次访问这些对象的请求时，Web缓存会直接响应这一请求。虽然对象冗余消除技术在很大程度上减少了网络中冗余数据无效传输，降低了网络通信流量，实现了降低网络访问延迟，达到节省网络资源的目的。但是它还是存在一定的局限性。首先它必须建立在特定网络应用层协议基础上，只能减少应用这些协议中的冗余数据；其次是冗余数据的粒度在KB之上，冗余精准度不高。包冗余消除技术主要工作在网络的传输层或者网络层。针对对象冗余消除技术不足，Spring 等学者在2000年首次提出包冗余消除技术[2]。它不依赖于网络协议，更关注数据包中连续冗余字节流，冗余精度高，在一定程度上能够消除网络通信中字节级别的冗余数据，进一步提升了冗余消除能力。后来，Anand 等学者[3]改进了Spring 的冗余消除技术，使其应用到到互联网中，冗余消除能力更强，在更大程度上减少网络通信的冗余数据流量。Agarwal 等学者结合了Spring和Anand冗余消除技术的优点，提出了基于静态查找表的冗余数据消除技术[4]，更进一步提高了网络冗余数据的消除水平。但是，包冗余消除技术使用共享缓存机制，无法区别冗余数据性质(如冗余数据用户与数据功能)，冗余消除能力还有提升空间。

1 传统包冗余消除技术

当前学者们的研究热点主要关注包冗余消除技术。总结学者们的研究成果，得出一个完整包冗余消除技术的工作过程中三个核心技术[5]，如图1所示。

1.1 建立备份库与指纹库。服务器从自己的缓存中划出两个空间建立备份库与指纹库。备份库用于将以往发送出的数据块进行缓存。服务器首先将待发送数据包的数据载荷进行分块处理，按一定算法计算出每一数据块所对应的指纹，然后再按指纹采样算法从这些指纹抽取出有代表性指纹缓存到指纹库中，使得每一个数据块都有一个代表性指纹与其对应。用户端缓存中备份库，它通过同步机制与服务器端备份库内容保持一致。

1.2 指纹采样。服务器对当前将要发送给用户的数据包按第一步骤中的指纹计算算法与指纹采样算法计算出数据块的代表指纹。

1.3 指纹匹配。将当前数据块的代表指纹与服务器端指纹库中的代表指纹按一定匹配算法进行匹配比较。若匹配成功，也就是服务器端的备份库中存在与相同当前数据块，从而识别出这一冗余数据。服务器对这一冗余数据块编码为简易冗余标识，最后将带有冗余标识载荷的简易数据包并发送给用户端。若匹配不成功，则把当前代表指纹和与其对应的数据块依次缓存到服务器端备份库与指纹库中，并发送。

图1 包冗余消除技术工作过程图

有大量冗余数据存在主要原因是在通信过程中，传递的数据包中有若干相同的数据块[6]。这些冗余数据块就其本身来说有如下两个重要的性质：一是数据包用户性质。二是数据包功能性质。

因此，论文在此基础上，针对应用广泛局域网提出了一种基于包性质的冗余数据消除技术。通过实验，证明了该技术能够减少了CPU的占用时间，提高了网络数据冗余消除效率。

2 数据包性质分析与建模

2.1 数据包性质分析

在局域网里，服务器与用户通信的数据包中除了满载荷外，还有近50%的数据包仅有很少数据，甚至有的没有数据。比如：TCP 确认信息、ICPM控制信息及SSL和TLS安全协议等。这部分数据包中数据部分占整个数据包比例非常小，冗余数据也很少，包的大小在20字节至100字节不等。如果在服务器端对其进行同样的冗余消除过程，这样不但占用了服务器CPU的处理时间，而且冗余数据贡献量也很低，总体收益率很低。在论文中，对于这部分冗余收益率低的低容量数据包采取直接发送方式，无需进行冗余处理处理。

2.2 基于数据性质冗余消除技术的系统模型

在上述数据包性质分析的基础上，针对应用广泛的局域网，论文提出了一种基于包性质的冗余数据消除技术，其结构如图2所示：

图2 基于包性质的冗余数据消除技术结构图

服务器端缓存中分别建立三类空间——公共指纹库、用户指纹库和编码库，并根据冗余收益值动态调整每个用户指纹库与公共指纹库的空间大小。服务器端ROM程序存储器中存放一个判断程序。公共指纹库中存放多个用户共同使用的数据块指纹，用户指纹库中存放仅供此用户单独使用的数据块指纹。编码库用于存放数据块在用户数据块库中的位置编码。每个用户端缓存中分别建立数据块库。这些数据块库存放了用户请求访问过的以数据块为单位的信息。用户端定期将数据块库中数据块位置信息同步给服务器端的编码库。

2.3 指纹库中指纹位置动态调整

权值函数F(X)可以对服务器端指纹库中的代表指纹匹配情况进行一次综合评估。其评估原则要主要考虑两个因素——最近24小时匹配次数LSUM和累计匹配次数SUM。该权值被称作冗余收益值R(Z) ，其用来表征该代表指纹将来被再次匹配的机率。冗余收益值R(Z)是我们进行指纹位置动态调整的唯一依据。在理论上，冗余收益值R(Z)的模型如下：

R(Z)=F(LSUM/SUM)

(1)

其中，Z表示指纹库中的一个代表指纹。 从表达式(1)中，冗余收益值R(Z)最终结果取决于一个合适的权值函数F(X)。因此，选取正确权值函数F(X)显得十分重要。其实，考虑了指纹的匹配过程与LRFU算法的基本思想是一致的，所以采用的权值函数F(X)模型如下：

F(X)=(1/P)tX(P=5)

(2)

2.4 包性质的冗余数据消除技术工作过程

论文针对局域网通信提出的一种基于包性质的冗余数据消除技术。此技术主要包括如下四个步骤，如图3所示。

图3 基于包性质的冗余数据消除技术工作过程流程图

1)包容量判断。服务器端的判断程序比对将要发送给用户端的数据包容量与判断程序中冗余阈值R(论文结合局域网的通信流量分析，将R设置为640字节。管理员也可以根据需要进行调整。)。如果大于R，则进行下一步骤2)。反之，说明此数据包为冗余数据量低的数据包，服务器直接发送，无需进行冗余消除处理。

2)指纹采样。服务器端根据数据包的目的地址来识别对应的用户端。然后对这些数据包的载荷部分分块，并按一定的指纹计算算法和指纹采样算法计算出代表性指纹。论文比较关注指纹采样命中率，所以采用Winnowing算法采样数据块的代表指纹。

3)冗余识别。按一定指纹匹配算法，将步骤2)得到的用户数据块代表指纹分别与服务器端公共指纹库和该用户指纹库中的指纹进行比较匹配。如果匹配成功，则识别出这一冗余数据。服务器调用编码库对此数据块进行简易地冗余编码，最后将带有冗余编码数据包发送给用户端。同时根据冗余收益值R(Z)调整该指纹在用户指纹库中的排序。反之，则是将当前代表指纹存入服务器端的用户指纹库或者公共指纹库中。论文中采用的是块匹配算法。相对于最大匹配算法，它大大减少了在服务器端和用户端的缓存空间的占用。

4)冗余解码。当用户端收到带有简易冗余编码的数据包时，对其中冗余标识进行解码，获得冗余数据块的位置信息，并根据此位置信息从自己的数据块库中还原出对应的数据块。完成了一次网络通信，最终达到网络通信过程包冗余消除的目的。

3 实验证明

实验环境选择了贵州省某高校的万兆主干链路互连网络，实验设备为三台DELL xeonE5-2600V3资源服务器与近1200用户终端节点。

3.1 实验数据分析

为了准确对比不同冗余消除技术在服务器端CPU占用时间和字节节约率两个方面差异， 我们抓取了某一天中三个时间段的用户对服务器访问的数据流量作为分析依据，如表1所示。

表1 实验数据统计

对于收集到的实验数据，我们经过分析研究发现在校园网中的不同类型服务数据产生的冗余贡献率(冗余贡献率=此服务类型的冗余数据量/所有服务类型的冗余数据总量)是不一样的。数据总量中近75%为下行数据量，其冗余消除贡献率较高，大约为85%。 在网络提供的应用服务中，数据量所占比例最大的是HTTP服务，其冗余消除贡献率也达到76%。具体分布情况如表2所示。

表2 冗余数据分布

3.2 CPU占用时间

在局域网中冗余数据处理过程中，起决定性作用的是服务器端。其CPU执行某一冗余数据消除技术进行通信过程的数据冗余处理。这一处理过程中的指纹计算、指纹采样、指纹编码、查找指纹和插入指纹等方面操作都要占用CPU处理时间。论文提出的基于包性质的冗余数据消除技术与冗余除技术分别运行于本实验环境，得出如下结果，如表3所示。

表3 三种冗余消除技术的CPU占用时间

从表3可以看出，论文提出的基于包性质的冗余数据消除技术在CPU占用时间方面表现出的优势是比较明显的。就其主要原因是论文的技术对于容量小于640B以下的数据包不进行冗余处理。

结语

目前冗余数据在网络中特别是在局域网中大量存在，严重影响了网络的通信效率。论文在研究当前协议无关的冗余数据消除技术的基础上，提出了一种基于包性质的冗余数据消除技术。该技术充分考虑局域网通信过程中数据包的用户性质与容量性质，设置了多用户的独立与共享缓存机制，建立了数据包容量的过滤阈值。这样不仅节约了缓存空间，而且还降低了网络设备处理能耗。实验结果表明，相对于现有的冗余消除技术，论文技术的冗余消除率比较好，改善了局域网通信效率，节约了带宽资源，在局域网中发挥了很大价值。

[1]Breslau L, Cao P, et al. Web caching and Zipf-like distributions: Evidence and implications. In: Proc. of the IEEE INFOCOM.1999.

[2]Spring N, Wetherall D. A protocal-independent technique for eliminating redundant network traffic. ACM SIGCOMM Computer Communication Review, 2000.

[3]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.

[4]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.

[5]AGARWALB， AKELLA A， ANAND A， et al． EndRE: an endsystem redundancy elimination service for enterprises[C].//NSDI 2010: Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation． Berkeley: USENIX Association， 2010: 419-432.

[6]唐海娜,林小拉,韩春静. 基于移动指针的数据流冗余消除算法[J].通信学报,2012(2)：7-14.

(责任编辑：王德红)

The Technique to Eliminate Redundant Data in LANs

Pan Youshun1Wang Kaijian2

(1.Department of pubic Fourdation,Moutai University, Zunyi 563000,Guizhou, China) (2.Department of Brewing Engineering Automation,Moutai University,Zunyi563000,Guizhou,China)

LAN has played an important role in the information construction of current enterprises. However there are always a lot of redundant data in the communication process occupying the bandwidth, resulting in efficiency reduction. A packet nature-based technique to eliminate redundant data in LANs is proposed in the paper by analyzing the nature of data packets. It could independently combine with the buffer sharing mechanism to filter low-capacity packets by means of redundancy threshold.

LAN， redundant data， redundancy elimination，redundant data eliminating technique

2016-09-10

1.潘有顺(1977.02～)，男，江苏淮安人，茅台学院公共基础部高级工程师，硕士。研究方向：计算机网络技术。 2.王开建(1955.08～)，女，天津人，茅台学院酿酒工程自动化系教授。研究方向：微电子技术、无线传感技术。

TP393.01

A

1673-9507(2016)06-0121-03