空间高效的数据包公平抽样算法

数据包公平抽样通过牺牲长流的包抽样率以换取更高的短流包抽样率,因而比均匀随机包抽样更能保证数据流之间的公平性.现有的公平抽样算法sgs(sketchguidedsampling)存在空间效率低、短流估计误差大的问题.提出了一种空间高效的数据包公平抽样算法sefs(space-efficientfairsampling).sefs算法的新颖之处在于采用多解析度抽样统计器对数据流流量作近似估计,各个统计器由d-left哈希表实现.采用在oc-48和oc-192骨干网采集的真实流量数据,在数据流流量测量以及长流检测的应用背景下,对sefs算法和sgs算法的性能进行了比较.实验结果表明,与sgs算法相比,sefs算法在空间复杂度降低65%的前提下,仍具有更高的估计精度.特别是对于占网络数据流绝大多数的短流而言,sefs算法估计精度高的优势更为明显.