摘要
对网络流的频数进行测量能够为现代高速网络管理提供极为重要的决策依据.现有的测量模型往往为每个计数器分配较大的长度,从而避免大流的计数值溢出计数范围.但是真实网络流存在偏斜分布的特性,绝大部分网络流都是小流,仅有少部分流是大流.由于占用了大量存储资源的计数器在大部分情况下只存储了小流,导致现有策略存在内存浪费、不适应分布不均匀的真实数据的弊端.为此本文提出了一种基于“双向计数器”的网络流频数测量模型AS(Arena Sketch). AS将内存空间划分为块,并引入“竞争机制”为网络流自适应地分配内存块.具体而言,双向计数器由两个指纹域和一个计数域构成,大流能够在指纹域保留自己的流标签信息,而越大的流能够竞争到越多的内存块用于记录其频数.一旦在指纹域保留签失败,就将所有内存块视作独立的计数器,重新构建二维计数器数组,组成经典紧凑数据摘要Count-Min Sketch,该流则被作为小流在CountMin Sketch近似记录.AS既消除了大流的溢出风险,也尽可能多地记录了小流,仿真实验表明,该测量模型在逐流频数测量任务和过阈值流频数测量任务中均达到了比先前工作更高的精度和更低的存储消耗.
Network flow frequency measurement is a fundamental task in high-speed network management.Existing measurement solutions often use fixed-size counters,whose size must be large enough to avoid overflow for any flow with an extremely large frequency.Nevertheless,most flows are small in size,leading to unignorable waste of memory space.To address this problem,we propose a bidirectional counter-based measurement model called Arena Sketch.Arena Sketch divides memory space into blocks and introduces a novel competition mechanism to adaptively allocate blocks according to the actual frequencies of flows.Specifically,a bidirectional counter consists of two fingerprint fields and a counting field.Large flows can store their flow label information in the fingerprint fields,and larger flows can seize more blocks to record their frequencies.Once the label retention in the fingerprint field fails,all the blocksare treated as counters and reformed to classical Count-Min Sketch.And the flow is approximately recorded as a small flow by the Count-Min Sketch.Thus,Arena sketch eliminates the risk of overflow for large flows and records as many small flows as possible.The simulation experiments show that Arena sketch achieves higher accuracy and lower memory usage than prior work in both the per-flow frequency measurement task and the heavy hitter measurement task.
作者
钟唯磊
杜扬
孙玉娥
黄河
ZHONG Weilei;DU Yang;SUN Yue;HUANG He(School of Computer Science and Technology,Soochow University,Suzhou 215006,China;School of Rail Transportation,Soochow University,Suzhou 215131,China;Key Laboratory of Embedded System and Service Computing(Tongji University),Ministry of Education,Shanghai 201804,China)
出处
《小型微型计算机系统》
CSCD
北大核心
2024年第6期1504-1511,共8页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(62072322,62202322,U20A20182)资助
同济大学嵌入式系统与服务计算教育部重点实验室开放课题项目(ESSCKF2022-05)资助
江苏省自然科学基金项目(BK20210706)资助
江苏省博士后科研项目(2021K165B)资助。
关键词
高速网络
频数估计
自适应测量
流量测量
high-speed network
frequency estimation
adaptive measurement
traffic measurement
