收稿日期! !"#$%"$%"!! 修回日期! !"#$%"&%!#))基金项目! 国家,,('- 计划资助项目"!""+>>"#>'$(#
作者简介!李海莉"#+,*%#$女$河南洛阳人$硕士研究生$主要研究方向为网络流量测量 "5DU?/UKU3#('4567#!史梦琳"#+,!%#$河南平顶山人$
讲师$ 主要研究方向为软件工程!张震"#+,&%#$男$山东济宁人$讲师$主要研究方向为宽带信息网络!宫阳阳"#+,,%#$男$河南濮阳人$硕士研究
生$主要研究方向为网络安全!郭威"#++"%#$男$北京人$硕士研究生$主要研究方向为芯片设计!王雨"#+*&%# $男$河南许昌人$讲师$主要研究方
向为宽带信息网4
一种基于流数约减的非线性公平采样算法
!
李海莉
#
! 史梦琳
!
! 张)震
#
! 宫阳阳
#
! 郭)威
#
! 王)雨
#
"#4国家数字交换系统工程技术研究中心$ 郑州 $&"""!! !4郑州电力高等专科学校$ 郑州 $&""""#
摘)要! 针对现有采样算法存在可扩展性和公平性差的问题$提出一种基于流数约减的非线性公平采样算法
"/2/JE?WDV/?GB/7JU?01L/BD2 60 GD2I5?01VU6F0I7LDGB$ >S9%\SC# & >S9%\SC算法首先采用均匀抽样的方法对要
统计流数进行约减$获得样本流集合!然后$对属于样本流集合的分组采用非线性的方法进行公平采样$实现控
制统计流数目的同时保证统计流信息的准确性& 仿真表明$与 >CR9" /2/JE?WD060%U?0D/GB/7JU?01# 算法相比$
>S9%\SC算法大幅降低了存储开销$同时$将算法的公平性提高了 ("c& 算法具有良好的可扩展性和公平性&
关键词! 流量测量! 均匀抽样! 非线性! 公平抽样
中图分类号! =8'+')))文献标志码! >)))))文章编号! #""#%'(+&"!"#&#"(%#,!(%"$
26?!#"4'+(+ @A4?BB04#""#%'(+&4!"#&4"(4"&"
>2/JE?WDV/?GB/7JU?01L/BD2 60 GD2I5?01VU6F0I7LDGB
R?h/?U?
#
! 9K?<D01U?0
!
! PK/01PKD0
#
! [601O/01-/01
#
! [I6eD?
#
! e/01OI
#
"#GP,/'#$,2I'%'/,2JV'/5"'$% J*6/)3K$%'$)).'$% ;7)5"$#2#%'5,2?)6),.5" !)$/).! L")$%O"#4 $&""" !! !"'$,% !GL")$%O"#4 K2)5/.'5:#V).
!#22)%)! L")$%O"#4 $&""""! !"'$,#
!"#$%&'$$ 9?05DJGDBD0EB/7JU?017DEK62BK/WDEKDBK6GE567?01B6V060%B5/U/L?U?E-/02 U6FV/?G0DBB! EKDJ/JDGJG6J6BD2 /0
/U16G?EK75/UUD2 >S9%\SC4>EV?GBE! >S9 %\SCGD2I5D2 EKDVU6F0I7LDGBL-IB?01EKDI0?V6G7B/7JU?01/02 16E/B/7JUDVU6F
BDE4=KD0! EKDJ/5HDEBLDU601D2 E6EKDB/7JUDVU6FBDEFDGDB/7JUD2 V/?GU-F?EK EKD060%U?0D/G7DEK62B4=KD7DEK62 560EG6UUD2
EKDVU6F0I7LDGBE6/556I0E/02 1I/G/0EDD2 EKD/55IG/5-6VEKD?0V6G7/E?60 6VVU6FB4M67J/GD2 F?EK >CR9! EKDB?7IU/E?60
2D760BEG/EDBEK/EEKD>S9%\SC/U16G?EK7B/WDBU/G1D/76I0E6V7D76G-6WDGKD/24>EEKDB/7DE?7D! >S9%\SC?7JG6WDBEKD
V/?G0DBBL-("c! /02 K/BLDEEDGB5/U/L?U?E-/02 V/?G0DBB4
()* +,%-#$ EG/VV?57D/BIGD7D0E% I0?V6G7B/7JU?01% 060%U?0D/G% V/?GB/7JU?01
!
)引言
网络流量测量将流量的各项指标量化!直观地描述当前网
络流量的组成成分!反映网络当前的运行状况!在流量计费)流
量识别) 故障检测和网络安全等应用中起着极其重要的作用&
由于网络上数据的增长速度远远超过存储器性能提高的速度!
而目前没有容量大且速度快的存储器能够处理当前网络上的
高速海量数据
!因此!对流量进行统计成为一个巨大难题& 为
了能够获知网络上的各种统计信息!通过抽样对数据进行压缩
是高速网络实时测量的一项重要手段& 传统的静态抽样算法
以等概率 E对链路上的数据包进行采样!能很好地保存包级流
量信息!流信息统计的准确性随流的增大而提高!即小流的统
计信息准确性低!大流的统计信息准确性高& 考虑到网络的动
态性!为合理利用存储和带宽资源!文献'# Y$( 分别针对不同
的资源
!自适应地改变抽样概率& 这些算法虽然提高了资源的
利用率!但却没有从根本上克服静态抽样算法对小流抽样准确
度低的缺陷!导致并发流数目)流长分布等的流级统计信息不
完整& 同时目前流量测量的研究主要集中在大流检测
'& Y*(
上!
更加忽视小流的统计& 研究表明
',(
!网络上 ,"c的流为小流&
当前网络上的 9OCSU662 和 ZZ69 攻击多是由单个或几个数据
包组成的小数据流!对小流统计准确性的缺失导致系统没能及
时发现网络异常事件!从而引起网络运行故障& 因此!在准确
统计大流用于统计计费的同时!提高小流抽样的准确性!对于
网络安全和网络异常检测有着非常重要的作用&
提高数据流之间的公平性!需要提高小流抽样的准确性&
文献'+(首次提出了牺牲大流抽样率并提高小流抽样率的基
于图的抽样算法" BHDE5K 1I?2D2 B/7JU?01! 9[9# & 其思想是通
过建立一个抽样概率是流大小减函数的数学模型
!数据包的抽
样率由其所属流的大小决定而不再是一个提前设置好的固定
值!以实现对不同大小的流统计准确性基本一致& 9[9 算法采
取哈希方法近似估计流大小!进而决定分组的抽样概率& 哈希
算法自身具有较强的冲突性!导致小流大小的估计存在严重误
差
!使得小流的统计结果误差较大!并没有真正实现流信息统
计的公平性
& 针对流大小估计的问题!文献'#" Y#'( 分别提
出了相应的算法!但是估计值本身就存在一定误差!对抽样结
果的准确性影响更大& 文献'#$( 提出了非线性自适应的抽样
算法
"/2/JE?WD060%U?0D/GB/7JU?01! >CR9#!基本思想是分组的
抽样概率随包所属数据流当前计数器计数值的增大而降低&
第 '! 卷第 ( 期
!"#& 年 ( 月)
计 算 机 应 用 研 究
>JJU?5/E?60 \DBD/G5K 6VM67JIEDGB
;6U]'! C6](
QI04!"#&