资源评估论文：网络流量能源消耗评估范文

作者：脱立恒倪宏刘学单位：中国科学院研究生院中国科学院声学研究所国家网络新媒体工程技术研究中心

冗余流量消除

RTE通常包括以下4个步骤。

（1）冗余数据探测。加速器使用数据块选择算法选出数据包中的数据块，通过指纹算法计算每个数据块的指纹，然后进行指纹匹配。

（2）指纹匹配。将计算出的指纹与加速器缓存中已经存储的历史指纹进行比对，比对成功，对数据片段编码；未比对成功，将指纹、数据块或数据包存入加速器缓存中，供下次指纹匹配使用。

（3）编码。使用短的元数据编码冗余数据块，如：<O,P>，其中O表示冗余块在缓存中的偏移位置，P表示该数据块在数据包中的起始位置。

（4）解码。接收端加速器根据发送端插入的元数据，对元数据进行解码。

在RTE算法过程中，块选择算法决定冗余数据块的选取效率，以下对比不同块选择算法的特点：FIXED算法固定每p（p为目标抽样周期）个字节从数据包中选取一个数据块，对于数据包内容的微小变化不健壮，通常不被使用；MODP算法使用哈希函数（rabinhash）计算Rabin指纹（RabinFingerprint，RF）计算连续w字节长数据块的指纹f，选择f=0modp的数据块作为检测片段，该算法可能导致选出的数据块过疏或过密分布，如字节连续相同的数据片段；MAXP算法选择每p个字节中，单个字节数值最大的字节为起点的w字节长的数据块，具有稳定抽样率，但该算法倾向选择第一字节值较大的数据块，当该类型数据块的冗余率较低时，算法将无法获得冗余率高的数据块；SAMPLEBYTE算法使用一个256项查找表，256项索引分别与字节的256个值对应，每一项的查找结果r∈{0,1}，1代表该索引对应的字节值被选中为标识，0代表该索引对应的字节值不被选中，查找表中固定k个字节值被选为标识。

SAMPLEBYTE算法分析数据包时，逐个字节扫描，如果扫描到的字节对应字节值的查找结果为1，则以该字节所在位置为起点，选出数据块，该字节称为该块的标识。计算选中数据块的指纹，按照RTE的处理步骤继续处理。一旦选中某个数据块，则以标识所在位置为起点，跳过p/2个字节重新开始SAMPLEBYTE算法。

SAMPLEBYTE使用离线算法统计训练数据，得到固定k=8个标识，分别为0、32、48、101、105、115、116、255。文献[2]指出，在p=32时，系统可获得吞吐量和字节节省间更好的平衡，之后的研究[7-8]多以该抽样率作为理论抽样目标。如果网络数据包中所有字节值均匀分布，则SAMPLEBYTE对数据块抽样率为8/256，但网络数据包中字节值非均匀分布，导致SAMPLEBYTE过抽样或低抽样。

基于动态查找表的网络冗余流量消除算法

1动态查找表更新算法

由以上分析得出，抽样率与标识个数以及标识在数据包中出现概率有关，RTE效率与选择哪些标识有关，为了动态跟踪抽样率，同时选择合适的标识，需要实时跟踪网络数据变化。为了获得精确的抽样率，实时统计网络数据包中不同字节值的出现概率，以便调整查找表Llpt中标识的个数；为了获得高的冗余数据检测效率，实时统计以不同字节值为标识的数据段的冗余频率，以数据块冗余出现频率高的字节值为基础，预测下阶段哪些标识对于提取冗余数据块更加有效。式(1)表示，选中的所有标识的抽样率小于等于1/p，式(2)表示，在式(1)限制条件下，选择使得不同字节值开头的数据段的冗余概率和最大的字节值作为查找表的标识。冗余概率和最大的标识，选择出的数据块的冗余率越高，RTE效率越高。该选择标识的过程转化为背包问题，本文使用贪心算法（greedy）求解该问题。按照不同字节值的冗余概率降序排列，选择使得总的抽样率接近1/p的字节值作为标识。

2以不同字节值开头的数据块的修正冗余频率计算方法

DYNATABLE统计不同字节值在数据包中出现概率，方法是，在使用RF算法计算指纹的过程中，实时记录不同字节值A出现的次数MA，用该次数比该段时间数据总长度，即为出现概率。

以不同字节值开头的数据块的冗余频率，统计上比较难，如果按每字节滑动统计所有数据块，可以获得以不同字节值开头的数据块的冗余频率，但在进行RTE时，每次选中数据块后，需要跳过S长数据片段，以防止数据块的过抽样，此时，按每字节滑动统计的数据块冗余频率将不再准确。所以需要对按每字节滑动统计的冗余数据块的冗余频率统计方法进行修正。假设在按字节滑动统计的过程中，以字节A开头的前后2个冗余数据块的距离为L，后一个数据块能否被选出，与距离前一个以A开头的数据块的距离有关，前后2个数据块的距离L<S时，如果前一个数据块被选中，在跳过S的过程中，后一个数据块将被跳过，该重复数据块处理流程如图1所示。

实际选择中，前一个数据块被选中也存在一定概率，其与更前面的数据块的选择有关，但针对后一个数据块，其距离前一个数据块的距离L越大，意味着离更前面的数据块距离越大，被选中的概率越大；前后2个以A开头的数据块距离L≥S时，后一数据块肯定能被选中，即后一个数据块对以A开头的数据块冗余频率贡献为（此函数记为contribute）：累加各个冗余频率贡献得到以不同字节值开头的数据块的修正冗余频率CA。利用布隆滤波器（BloomFilter，BF)能快速判断某个元素是否属于集合特点，在统计以不同字节值A开头的数据块的修正冗余频率时，将指纹放入布隆滤波器实现的集合GA中。

3DYNATABLE算法流程

综上，DYNATABLE算法如下：输入参数：tpkt为数据包指针，w为数据段长度，N为数据总长度，且N>w，i为临时变量

4布隆滤波器设计

BF的参数设计对统计的效率至关重要。BF由一个长度m的二进制向量和q个随机映射函数组成，它将输入元素通过映射，映射到二进制向量的q个比特位上，并将比特位置1，检测某输入元素是否已经存在的过程是计算该元素的映射，如果q个映射比特位全部置1，说明元素已经存在，否则，元素不存在。BF可以保证所有已经插入过的元素肯定能被检测出，但存在一定的误识别率p(FalsePositiveRate,FPR)。设存入元素个数为n，则p与m、q、n关系为:为保证计算高效性，选q=2，BF存储的最大元素个数为6n=10。为使FPR控制在p≤1%，由公式(4)得出，二进制向量长度m应取20Mb。

5256-LSA缓存替换算法

SAMPLEBYTE中使用FIFO（FirstInFirstOut)的缓存替换算法，Halepovic等提出使用LSA（LeastSavingswithAging）缓存替换策略。由于DYNABYTE算法实时动态更新查找表，当查找表中标识发生变化时，已被替换出的标识对应的数据块将不可能再命中，LSA算法无法迅速替换出该部分数据块。DYNABYTE将缓存拆分成256份，每份缓存对应一个字节值，不同数据块存入其标识对应的缓存中，当查找表发生变化时，被替换出的标识的缓存将不被再次访问。

实验与仿真

本节讨论DYNATABLE的实验及仿真结果。实验设备为DELLR710服务器，配置为16核CPU、4G内存、500G硬盘，操作系统为CentOS5.5。虽然DYNATABLE为RTE提供动态的查找表，对查找表更新与块选择算法是相互独立的，DYNATABLE的查找表更新算法和块选择算法分别采用2个独立进程完成。DYNATABLE查找表更新进程更新查找表后，将其更新到共享内存区，同时通知块选择算法进程实时更新查找表。

1实验数据

为了准确对比不同块选择算法的效率，抓取表1中4种情况的流量作为分析数据。抓取数据总流量大小为130.6GB。

2缓存替换算法

实验中分别使用LSA和256-LSA这2种缓存替换策略，对4段跟踪数据进行分析，结果如表2所示。由表2可见，256-LSA缓存替换方法比LSA替换方法的字节节省率R提高约20%。以下实验中，均使用256-LSA缓存替换策略。

3抽样率

用DT代表DYNATABLE算法，FX代表FIXED算法，MX代表MAXP算法，MD代表MODP算法，SB代表SAMPLEBYTE算法，图2显示了5种算法的实际抽样率变化情况，其中FIXED和MAXP的抽样率相对比较稳定，MODP抽样率过高，SAMPLEBYTE的抽样率较低。DYNATABLE算法能够动态调整抽样率，使抽样率在目标抽样率附近波动。

4字节节省

表3和图3对比了5种算法的字节节省率，字节节省率定义为冗余消除后传输字节数与冗余消除前的字节数的比值。DYNATABLE算法带来了更高的字节节省率，对于A、B、D，DYNATABLE比MAXP平均提高16.1%，对于C，DYNATABLE比SAMPLEBYTE提高38.8%。

5运行时间

表4同时统计了5种算法处理每Gb数据的CPU运行时间。DYNATABLE的查找表更新算法和块选择算法分别独立运行，表中DYNATABLE算法的CPU时间乘以2表示取查找表更新算法的CPU运行时间和块选择算法的CPU运行时间中的较大值，再对CPU运行时间加倍。CPU时间消耗包括，计算指纹、缓存查找和插入等操作开销。块选择算法的计算量主要集中在对缓存的查找和插入操作；DYNATABLE的查找表更新算法，计算量集中在数据块的查找或插入BF集合，通过实验，DYNATABLE的查找表更新算法和块选择算法的运行时间基本相当。DYNATABLE增加计算量，但并未减小处理数据的吞吐量。

结论

本文提出了一种基于动态查找表的RTE算法（DYNATABLE），该算法实时统计网络数据中以不同标识开头的数据块冗余率，选取冗余率高的标识，动态更新查找表，以选取更多的冗余数据块，在网络数据传输时，获得高的字节节省；在统计以不同标识开头的数据块冗余率时，使用布隆滤波器存储已出现的数据块的指纹，缩短算法运行时间；DYNATABLE算法中使用256-LSA缓存替换算法更新缓存，提高缓存命中率。通过仿真实验，DYNATABLE在不减少数据处理吞吐量的条件下，有效提高网络数据传输中的字节节省，提高广域网传输效率。