研究意义当前，高速网络流的实时测量面临着存储资源稀缺的挑战，难以满足海量流式数据的实时存储需求。现有研究大多采用存储资源共享技术，将估计器置于高速片上缓存中，但这种方法引入了难以消除的噪声，导致中小规模流的估算精度不高。为了实现高速网络流的实时测量，网关或路由器需要以极快的速度处理数据包，但当前的存储资源，如静态随机存取存储器 (SRAM)，成本昂贵且规模受限，难以满足超高存储需求。另外，由于高速网络流的规模分布极不均衡，大多数流为极小流，对这些流进行准确测量实际意义有限，但却占用了大量存储空间。现有研究将不同流的信息混杂存储在一起，以提高片上存储的利用率，但这种方法增加了噪声并且使得中小流难以达到可接受的估计精度。因此，设计一种能够高效地滤除对实际应用意义较小的超小流，并控制超大流的资源占用，从而实现低存储成本的高精度流大小测量，对于实时网络流量测量具有重要意义。
本文工作针对上述问题，本文研究设计一种能够根据流大小自适应调节所占用存储空间的Sketch 结构，使其能够高效地滤除小于给定阈值的流，即滤除对实际应用意义较小的超小流，并控制超大流过多资源占用，从而获得低存储成本的高精度流大小测量机制。所设计的自适应Sketch首先利用可逆计数器以极小的空间代价实现对绝大多数极小流的高效滤除，大幅降低海量噪声小流对网络测量的影响；然后，设计了一组采样频率逐层递减的采样计数器，实现对不同规模流的自适应采样，保证不同规模的流均被高精、低开销地测量，从而满足不同规模流的差异化测量需求。通过在真实网络数据集上的测试发现，基于自适应Sketch所提出的流大小估计器在极低的片上存储开销下实现了对大流的精确估计，特别地，针对中小规模流的大小估计，其相对于同类方法展现出了更低的平均相对误差水平。
本文的主要创新点如下：
(1) 创新性地提出了一种能根据流大小自适应分配存储空间的自适应Sketch技术。该技术利用可逆计数器高效滤除高速网络中的海量噪声小流，并利用由一组采样频率逐层递减的采样计数器实现对不同规模流的自适应采样，以尽可能小的存储代价满足不同规模流对估计区间和估计精度的要求。
(2) 提出了一个高效的高速网络流大小估计器，利用所设计的自适应Sketch实现了实时的噪声小流滤除和自适应流量抓取，结合概率分析实现了低存储、计算开销的高精度每流估计。
图1 自适应 Sketch 的结构与示例实验结果本文实验使用 2019年CAIDA监听的匿名流量数据作为流大小估计的测试数据，该测试数据共包括147M个数据包，486K条流。本文与经典算法Count-Min和virtual HyperLogLog (vHLL)进行对比。实验结果表明自适应Sketch方法在流大小估计上，相对于同类方法具有更优的估计精度。
图2 自适应Sketch算法与其他测量算法的比较研究团队
卜霄菲：沈阳师范大学软件学院
黄河, 王兆杰, 吴晓灿：苏州大学计算机科学与技术学院
孙玉娥：苏州大学轨道交通学院
文章下载
卜霄菲，黄河，孙玉娥，王兆杰，吴晓灿. 基于自适应 Sketch 的高速网络流大小测量机制. 中国科学：信息科学, 2024, doi: 10.1360/SSI-2023-0294
链接：https://www.sciengine.com/SSI/doi/10.1360/SSI-2023-0294
