一种改进CARE业务流估计算法

1、一种改进CARE业务流估计算法主动队列管理（AQM是近年来端到端拥塞控制研究中的一个热点。它的主要技术目标是在减小排队时延的同时保证较高的吞吐量，确保拥塞控制机制的稳定性，提高资源分配的公平性和对网络动态变化的自适应性，最终实现QoSa制1。准确的业务流估计是AQMI制中实现QoS的基本保证。通用业务流估计算法的最基本思想是基于数据包的估计方法。该方法从队列中随机取出一个数据包与新的数据包进行比较，如果新数据包和队列中的数据包是属于同一个业务流，那么就认为该业务流是活动的；否则就认为队列中数据包所属的业务流是不活动的。准确估计的业务流数目为中间设备部署解决方案提供了一定的参考依据2,3,对于中

2、间设备实现QoSa制具有很大意义。通用的业务流估计方法对于决定数据包的丢弃率是非常有效可行的，然而这种通用的方法对于数据包数量不确定的网络就不能适用。针对这些不足，文献4提出一种更加简单有效的算法FNE该算法名t持一个zombie列表，这个列表保存着到达数据包的历史。一旦到达的数据包与zombie列表中随机取得的数据包相匹配，就称为命中（hit）；否则称为丢失（loss）。如果命中则zombie列表中该记录不会改变；否则该记录就会更新为当前新数据包的内容。FNE算法的实现是通过采集当前的命中比率Rhit和失效比率Rloss来计算当前业务流的数目。相比公平队列机制的通用业务流估计算法来说，FNE

3、算法在减少延迟的情况下保持资源的高利用率，并且容易实现。文献5提出基于CR模型的业务流估计算法CARE其主要思想是：首先获取数据包，并将其存储在数据列表结构中；再根据数据包ID标志的次数构建一个频率数据集合；最后利用jackknifeestimator6来估计业务流的总数目。相对通用算法来说，该算法的空间利用率高、算法复杂度低。但是，FNE算法和CARE#法均存在一些缺点。FNE算法在算法开销方面比较大；而对参数的依赖性比较大，参数配置不合理会导致估计结果产生误差。1CAR尊法业务流估计算法CAREE勺基本原理是通过CR莫型进行标记和构建频率数据集合，应用Burnham等人6提出的genera

4、lizedjackknifeestimator原理来计算业务流数目。其中，CR模型7最开始是用于估计野生动物或者濒危物种的数量。其基本过程就是将首次捕获(capture)的动物做上标记后释放，在足够时间间隔后再次捕获(recapture)；基于jackknifeestimator原理8，根据再次捕获的带有标记的动物数目来估计当前动物的数目。CR模型的主要优点是不需要获取所有的动物，仅仅根据捕获部分标记动物数目就可以比较准确地估计整个动物的数目。2 3数据列表长度的影响增加估计次数可以提高估计的准确度。但是如果不改变估计次数，而单纯增加数据列表长度同样会获取到比较充分的数据。在固定估计次数增加数

5、据列表长度的情况下，业务流估计值是逐渐增加的。但是数据列表长度超过一定数值以后，估计值开始逐渐偏离真实业务流数目。因此，虽然增加数据列表长度有利于提高估计的准确度，但是不能任意地无限增加。因为选择合适的数据列表便能够获取到具有代表性的数据，就足以获得比较准确的估计，冗余的数据信息只能造成数据的重复，不会明显提高估计值的准确度。要寻找最合适的区间来保证在该区间范围内估计的业务流数目与真实业务流数目接近。3改进CAR弟法通过以上对CAR弟法的研究，得出一些基本结论。但是针对CARE!法存在的缺点，尤其是区分水平值对估计结果的影响，修改CAR弟法的估计过程，提出了一种改进的CAREJk务流估计算法。

6、3 .1改进CAR漠法的基本原理改进CAREJT法同样也是基于MhCR模型通过jackknifeestimator机制来进行估计的。但是CAR漠法中人为设定区分水平值对估计结果造成了一定的影响。对此笔者修改了CAREH法的估计过程，通过不断地递归来逐渐逼近真实业务流数目。算法估计过程首先假设估计次数为真实业务流的一半进行估计得到第一个估计值S1o但是这次估计仅仅是在假设情况下计算的结果，所以需要调整估计次数再次进行估计，通过递归得到稳定的结果，选取第n次的结果作为最终的业务流估计数目。总之，改进的CARET法的基本原理就是在递归过程中不断修正估计次数来满足条件，最后得到稳定的估计结果。改进的C

7、AR漠法伪代码如下：从整体上看，改进的CARET法相对于CARET法估计出的结果更加接近实际业务流数目。另外随着真实业务流的增加，CARE算法的估计值与实际业务流误差越来越大。尤其是当业务流的数目超过50以后，在第七次实验实际业务流为60的情况下，CARE算法估计出的流数目为33,误差为45%,而改进的CARET法估计出的流数目为61，误差仅为1；在第八次实验实际业务流为80的情况下，CARE#法估计出白流数目为34,误差为57.5%,而改进的CARET法估计出白流数目为72,误差为10%。八次实验CARET法的平土匀误差为26.5%改进CARET法的平均误差为1.6%。所以相比CARET法来

8、说，改进的CARET法在估计业务流数目上误差更小。本文还选取美国应用网络研究国家实验室9的被动测量和分析工作组10的权威被动测量数据来比较两种算法的性能。PMAf在为高级网络提供协作性的服务支持。它采用OC3com攵据搜集系统，包括专门的群机系统、装有FOREATMcards和opticalsplitters,在HPC网络中设置多个测量点被动测量Internet数据，采集ATM的数据流。本文使用的数据来自测量点TXS11。TXS站点位于TexasUniversitiesGigaPOPatRiceUniversity，每经过3h采集一次数据，每天采集八次数据。其提供的数据格式为TSHH每个报文长

9、度44Byte。TSH数据格式包含整个IP报头和TCP报头的内容。该实验采集测量数据时间为2006年5月21日0时2006年5月27日24时，设定业务流的最长存在时间为20ms。TXS测量点一周的数据包和实际业务流的结果如图2所示。从图2中可以大致看出，TXS站点实际数据包一周的平均数目为15000，而业务流数目基本上保持在8000，并且基本在每天的18时以后数据包数量开始增加达到当天最大值。在得到TXS测量点5月21日5月27日一周实际业务流分析结果后，在每个采样时段分别实施改进的CARE1法和CAR漠法来估计业务流数目。通过分析实际业务流，其结果如图3所示。图3横坐标以d为单位起始于5月2

10、1日0时，终止于5月27日24时；纵坐标为业务流数目。5月21日5月24日期间由于实际业务流相对较少，基本保持在8000，所以两种算法估计的业务流数目与真实业务流接近，但是改进的CARE!法还是比CARET法更加接近实际业务流数目。虽然在估计小数值业务流方面改进的CARET法超过CARET法，但是在估计大数值业务流方面改进的CARET法更加具有优势，误差相对更小。例如在5月26日9时实际业务流为12995,改进的CARET法估计的业务流为12456,误差仅为4.14%,CARET法估计的业务流为9849,误差为2442%；在5月26日18时实际业务流为12236，改进的CARE古计的业务流为1

11、0584,误差为13.5%CARET法估计的业务流为9885，误差为192%；在5月27日3时实际业务流数目为14316,而改进的CAREf法估计业务流数目为14013,误差仅仅为2.11%CARET法估计的业务流为10784,误差为24.67%相比较而言，改进的CAREf法无论在估计数值方面还是在误差方面的分析结果均优于CAREf法。通过分析以上结果，说明在大型中间路由设备上部署改进的CARET法来进行业务流分析不仅是可行的而且更加具有实际意义。对图3中的数据进行分析得到两种算法的误差分析表如表1所示。4 结束语CAREk务流估计算法是基于CR模型利用jackknifeestimator原理

12、来估计业务流的算法。分别对CARmT法造成影响的区分水平值、估计次数、数据列表长度三个参数进行比较分析。首先，区分水平值是估计业务流的关键，对估计结果的选取有很大的影响。选择不同的区分水平值，可能导致估计的结果产生很大的差异。通过实验研究CARET法得知：如果估计次数T超过真实业务流的N/2,那么区分水平E与真实业务流N比值的取值区间为0.1,0.3。其次，在数据列表长度与估计次数比率恒定的情况下，CARET法的估计数目随着估计次数的增加而逐渐接近真实业务流数目。最后，在估计次数不变、增加数据列表长度的情况下，估计值是不断增加的。在研究CARET法的估计过程中，提出一种改进的CAR漠法。该算法运用递归的方法通过不断修正估计次数进行估计并且得到了稳定的估计结果。