高速网络UDP流超时策略研究

赵小欢， 夏靖波， 朱长虹

（1.空军工程大学 信息与导航学院，陕西 西安 710077；2.中国人民解放军95429部队，云南 昆明 650200）

高速网络UDP流超时策略研究

赵小欢1， 夏靖波1， 朱长虹2

（1.空军工程大学 信息与导航学院，陕西 西安 710077；2.中国人民解放军95429部队，云南 昆明 650200）

随着社交网络、在线视频、电子商务、即时通信及微博等新兴业务的不断涌现及迅速发展，网络中UDP流量的比例及特性均发生了较大变化。文章通过对现有的流超时策略进行分析，指出其适用于UDP流量时存在的局限及不足，针对实际UDP网络流特性展开研究，并提出了一种UDP流区分更新的流超时策略（DUToS）。实验结果证明，DUToS算法能够更好地适用于UDP流量，有效改善了网络流量测量的性能。

高速网络；UDP数据流；流超时策略；区分更新超时策略（DUToS）

随着网络链路速率的提高，在流量测量系统中采集并分析全部的数据包信息变得不切实际，同时由于数据包级的流量测量缺乏高层业务信息，在许多情况下数据包级流量测量无法满足网络管理的需求。基于此，文献［1］提出了基于IP流的被动网络测量方式，并将网络IP流定义为符合特定流规范和超时约束的一系列数据包的集合。目前使用最广泛的流规范是五元组（源IP、源端口、目的IP、目的端口、协议）规范，超时约束是将超过一定时间不活动的流定义为已终结流，以便更加有效地利用测量系统的资源。

随着Internet的不断发展，社交网络、在线视频、电子商务、即时通信及微博等多种新兴业务不断涌现，并迅速占据互联网中主流应用位置，同时一些传统的主流应用（如网络新闻、电子邮件等）使用率不断降低［2］，互联网流量在组成和性质上都有了较大的改变。通过对网络中的IP流分析发现，Internet中TCP、UDP和ICMP 3种流量在包（packet）级别和流（flow）级别一直以来都占据着绝对优势，但由于UDP在实时性上优于TCP，随着网络主流应用的转变，UDP流量在Internet中的作用越来越重要。互联网数据分析合作组织（CAIDA）通过研究数条美国至瑞典间骨干链路在2002—2009年的流量数据后指出，随着一些新兴应用趋于选择UDP作为传输层协议，观测到的链路中UDP流量相对于TCP流量在流、数据包和字节上的比例都有显著增加［3］。

由于目前的流超时策略大部分是针对全部IP流或TCP流，较少有专门针对UDP流的超时策略，针对近年来网络流量特别是UDP流量特性的变化，本文分析了现有的流超时策略适用于UDP流量时存在的局限和不足，结合MAWI提供的packet traces分析近年来网络中UDP流的特性变化，并提出了一种UDP流区分更新的流超时策略，最后通过实验进行了分析及验证。

1 网络流超时策略分析

流超时设置是为了平衡海量流量和有限存储之间的矛盾，尽快将已结束的流从有限缓存中删除。理想情况下流超时设置得越短，过期流被淘汰得越快，但过短的超时设置可能会导致包间隔时间较长的流被截断成为若干短流，造成包间关系及其更高层次信息分析的丢失，因此流超时研究需要根据具体的网络流量特性，寻求性能与消耗的平衡。文献［1］将流超时阀值分别设置为2is（i＝1，2，…，11）对观测traces进行组流实验，得出主干网IP流超时阀值以64s为宜。该超时策略采用固定超时，未对不同种类、不同特性的IP流区分对待，在一些异常情况下必然会出现测量结果的偏差，另一方面，随着网络流量的不断变化，64s的固定超时对于目前的网络流是否合适值得怀疑，文献［4］指出，目前的数据流超时间隔取值为16s可达到理想的效果。

文献［5］基于TCP分组的应用层协议分析流大小和最大报文间隔之间的关系得到流大小与报文间隔的经验条件概率分布，采用PGAT算法结合经验分布设置多个超时阀值。然而，实时网络流应用层协议识别本身就是一项非常困难的工作，PGAT算法只适用于少量可快速识别的业务流，同时PGAT算法主要适用于长流，不适用于包含大量短流的UDP流量。

文献［6］通过分析流吞吐量和包间隔方差系数间的关系，提出一种自适应的流超时算法MBET，MBET算法为每个流都维护一个独立的超时，初始超时值设置为最大，随着观测值的变化，流超时值维持不变或以2的指数形式递减。MBET算法能够自适应于流的变化，但主要针对长流，并且超时阀值一旦变小就不能再增加。

文献［7－8］提出了2层自适应超时策略TSAT和动态超时策略DToS，2种算法采用固定超时、协议分析、定期扫描及MBET等多种策略结合，极大地提高了系统资源利用率，但算法需要根据流的统计特性设置参数，并没有专门针对UDP流量特性进行优化调整。文献［9］针对UDP流的流超时策略，将流超时时限设置为6个值，通过支持向量机算法实现对UDP流超时阀值的分类，但由于UDP流中存在大量的短流，这些短流特别是单报文流的流量属性特征严重不足，短流采用机器学习算法容易发生分类错误。

目前各种流超时策略研究的一个主要方向是在保证组流精度的前提下，根据流量的具体特性优化流超时策略，以降低系统的资源消耗，但各种流超时策略大部分是以网络中的全部流量作为研究对象，而不同协议产生的流量在流特性上具有较大的差异，这些流超时策略适用于UDP流时会导致性能下降；同时，不同于TCP流量具有明显的协议标识，可用来判断流的开始和终结，无连接特性的UDP流量更需要通过流超时策略判断流的起止，因此有必要结合UDP流的具体流量特性，进一步优化UDP流超时策略。

2 UDP流特性分析

MAWI提供的一条跨太平洋骨干链路2011年8月1日trace中流量分布情况［10］见表1所列。

表1 MAWI网络流量

trace中共包含1 680 971条IP流，其中TCP、UDP、ICMP 3种流分别占到总流数量的31.32%、51.88%、16.27%，其他流仅占到总流数量的0.53%；共有数据报文15 214 334个，其中TCP、UDP、ICMP报文分别占到总报文数量的80.43%、15.89%、3.38%，其 他 报 文 数 比 例 为0.3%。由表1可以看出，相对于文献［11］，随着网络的不断发展变化，骨干链路中UDP流量的流数量和报文数量都有了明显的增长。

网络IP流流长分布和流持续时间分布都具有比较明显的重尾现象，文献［1］提出的64s固定超时基本上能够满足全部IP流的流超时需要，但对于大多数流长较小、流持续时间较短的流来说，64s的超时设置浪费了较多的时间和空间资源。为了进一步优化流超时策略的资源配置，有必要根据IP流的不同特性动态调整超时策略。

trace－20110801的流长和流持续时间的累积分布函数如图1所示。

图1 流长与流持续时间CDF分布图

由图1可以看出，尽管4种流分布都表现出明显的重尾现象，但不同流的流长和流持续时间的重尾程度并不相同。流长在10以内的流分别占到总流数、TCP流数、UDP流数、ICMP流数的95.79%、94.37%、98.84%、98.91%，而流持续时间在1s以内的流分别占到总流数、TCP流数、UDP 流 数、ICMP 流 数 的 51.71%、36.12%、86.44%、70.77%。

对于UDP流而言，短流的比例特别高，流长在1、2、3、6、10以内的流分别占到 UDP总流数的 84.41%、92.12%、94.94%、98.05%、98.84%，当发生DDoS等网络攻击时，网络中的单报文流的比例会进一步增加［12］，对于单报文流超时阀值的优化能够极大地节约系统资源消耗。在识别单报文UDP流的基础上，单报文流超时阀值越小越好，单报文流超时策略可以等价于单报文UDP流的识别问题。同时，在整个UDP流持续周期内，流持续时间在1、2、4、8、16、32、64s以内的流分别占到总流数的86.44%、86.87%、88.82%、92.87%、95.20%、96.54%、98.39%，显然，绝大部分 UDP流的持续时间都远小于64s，64s的超时阀值为大部分UDP流流持续时间的数十到数千倍，UDP流超时阀值具有较大的优化空间。

trace－20110801中不同长度UDP流的平均流持续时间和平均报文间隔时间如图2所示。

从图2可以看出，对于平均流持续时间而言，UDP短流的持续时间较短，而不同长度UDP长流的持续时间波动较大；就UDP流平均报文间隔时间而言，流长处于2～100中的流平均报文间隔时间及波动较大，如在UDP流长为24处，大约平均每隔15s才传输1个报文，长流的平均报文间隔时间较小，特别是对于流长为103～105的流速率更为稳定。

图2 UDP流持续时间分布图

3 区分更新超时策略（DUToS）设计

通过对UDP流量特性分析可知，UDP流中单报文流的比例极高，若按照64s的固定流超时设置，这些单报文流将极大地浪费系统资源；同时由于长流的平均报文间隔时间及波动均较小，对于这些长流，可以通过观测前期报文间隔值预测以后报文间隔值来设置UDP流超时阀值。为了精确设置各种UDP流的超时阀值，首先需要初步统计新出现UDP流的信息，为此系统创建一个新流特性统计空间（New Flow Statistics Extraction Module，简称NFSEM）来提取 UDP流长信息，NFSEM采用双链表数据结构，链表数目固定，采用LRU淘汰策略更新流，同时为了防止NFSEM被长流占满及部分流占用NFSEM过长时间，对于流长大于10的UDP流将会强制被淘汰到流超时空间（Timeout Module，简称TM）。

TM统计UDP流的信息，对不同长度的流采用3种不同的流超时策略，分别在3个子空间long－flow－space、short－flow－space和singlepacket－flow－space中实现。

DUToS原理如图3所示，算法描述为：

（1）当一个UDP报文到来时，通过哈希方式查找UDP报文对应的流地址，若UDP流位于NFSEM中，则进入步骤（2）；若UDP流位于TM中，则进入步骤（3）；否则进入步骤（4）。

（2）更新NFSEM 中对应UDP流信息，将UDP流放入链表头部，若UDP流长大于10，则将该UDP流从NFSEM中淘汰至TM中，进入步骤（5）。

（3）更新TM中对应的UDP流信息，进入步骤（5）。

（4）判断NFSEM中链表是否已被占满，若链表未满，则将新到UDP流放入链表头部，否则，将链表尾部UDP流淘汰至TM中，并将新到UDP流放入链表头部，进入步骤（5）。

（5）判断UDP流长，若UDP流长为1，将UDP流放入 TM 的single－packet－flow－space区间，按照先入先出FIFO策略淘汰过期流；若UDP流长处于［2，L）区间，将流放入 TM 的short－flow－space区间，按照MBET策略淘汰过期流；若UDP流长处于L［，＋∞）区间，将流放入TM的long－flow－space区间，通过SVM预测设置流超时阀值。

图3 DUToS原理

对于单报文UDP流，DUToS并没有固定时间以淘汰旧流，而是通过空间受限的FIFO缓存不断更新过期流，这样做具有以下优点：①FIFO策略巧妙地将流识别与流淘汰结合，每次淘汰的流是最可能终结的单报文流，具有较高的准确率；②FIFO策略能够自适应于网络中单报文流速率的变化，以每秒产生上万个UDP单报文流为例，若FIFO包含10 000个表项，则平均每个单报文流被淘汰的时间不到1s，在DDoS攻击等网络异常情况下，FIFO缓存能够更快地淘汰过期单报文流，算法具有较高的鲁棒性。

对于UDP长流的超时设置，为便于实现，将长流超时阀值分别设置为｛｛2｝，｛4｝，｛8｝，｛16｝，｛32｝，｛64｝｝，则 UDP流报文间隔时间被划分为6个区间｛（0，2），［2，4），［4，8），［8，16），［16，32），［32，64）｝，此时长流超时阀值设置问题就转换为多类分类问题。不同于传统的支持向量机需要寻求最优分类面来最小化分类误差，网络流超时阀值的设置是有偏的（即流超时阀值大于报文间隔值能够接受，流超时阀值小于报文间隔值，即使是略小于报文间隔值都是不能接受的）。

为了确保UDP流不被截断，将流超时阀值｛｛2｝，｛4｝，｛8｝，｛16｝，｛32｝，｛64｝｝对应的报文间隔区间重新调整为（0，2－ε1），［2－ε1，4－ε2），［4－ε2，8－ε3），［8－ε3，16－ε4），［16－ε4，32－ε5），［32－ε5，64）。同时，基于实时性的考虑，DUToS算法并不对长流中的每个UDP报文时间间隔进行预测，而是每隔T个报文预测1次，或者当上次预测值α与当前报文间隔值β的绝对差大于t1，或者当前超时阀值To与报文间隔值β的差值小于t2时，DUToS算法重新预测并更新预测值α和UDP流超时阀值To。

4 实验分析与结果

为了验证DUToS的性能，将本文提出的DUToS与 PGAT 算法［5］、TSAT 算法［7］与 MSVM算法［9］进行比较，定义评价指标为：

其中，true－count为trace中真实包含的流数；generated－count为采用各种超时算法测得的流数；unshorten－count为采用各种超时策略后真实的流数中未被截断的流数；extra－time为UDP流最后一个报文到来至流被淘汰期间持续的时间。

为了增加对比性，选用MAWI提供的同一条链路1999年3月21日、2009年3月30日和2011年8月1日3组trace作为测试数据，DUToS算法参数ε1＝ε2＝ε3＝ε4＝ε5＝1，L＝20，T＝50，t1＝t2＝0.2，短流采用的 MBET淘汰方式参数见文献［7］，实验结果见表2所列。

表2 各种流超时策略效果对比

从表2可以看出，PGAT算法适用于UDP流量时在gr、ir、mft 3个指标上表现均不理想，主要是因为PGAT算法通过识别流对应的应用协议来判断流超时阀值，而通过分析3组trace发现，UDP流量的端口分布在0～65 535整个区间上具有较高的随机性，难以简单地识别出UDP流对应的应用层协议。MSVM算法对于trace－2009和trace－2011的gr和ir的准确率较低，这是由于trace－2009和trace－2011中UDP短流特别是单报文流的比率很高，MSVM算法在预测流量属性特征不足的单报文流时，误差必然增加。

相对而言，TSAT和DUToS在流产生率gr和流完整率ir的准确率较高，但DUToS算法的流超时均值mft要明显低于TSAT算法，这意味着DUToS算法对于已终结流的淘汰速度高于TSAT算法。

对trace－2011采用不同流超时策略时系统需要维护的活跃UDP流数量随时间的变化情况如图4所示，从图4可以看出，由于对比例占到UDP流总数84.41%的单报文流采用了优化处理，在整个测量周期内，DUToS需要维护的活跃UDP流数量明显低于其他算法，由于系统占用系统资源与活跃流数量成正比，因此DUToS需要的计算和存储资源是最少的。

图4 不同超时策略维护活跃UDP流数

5 结束语

随着骨干网络链路速率的进一步提升，提高组流效率已经成为基于粒度的网络行为分析亟待解决的问题之一。针对网络中UDP流量的增长变化，本文详细分析了UDP流的流量特性，在此基础上提出了针对不同长度的流采用不同更新方式的区分更新流超时策略（DUToS），该策略对单报文流采用空间受限方式淘汰过期流，对于短流采用MBET策略淘汰过期流，对于长流采用SVM方法预测包间隔来设置流超时值。实验结果验证了DUToS更加适合于UDP流量，策略在流产生率、流完整率、流超时均值3个指标上均有较好的表现，并且在对同一组UDP流量进行组流时，DUToS占用的系统资源远低于其他方法需要占用的资源。

［1］Claffy K C，Braun H W，Polyzos G C.A parameterizable methodology for Internet traffic flow profiling［J］.IEEE Journal on Selected Areas in Communications，1995，12（8）：1481－1494.

［2］中国互联网络信息中心（CNNIC）.第30次中国互联网络发展状 况 调 查 统 计 报 告 ［EB／OL］.［2012－07－23］.http：／／www.cnnic.cn／.

［3］CAIDA.Analyzing UDP usage in Internet traffic［EB／OL］.［2010－01－14］.http：／／www.caida.org／rersearch／traffic－analysis／tcpudpratio／.

［4］王 远，丁 伟，龚 俭.TCP数据流超时研究［J］.厦门大学学报：自然科学版，2007，46（2）：192－195.

［5］Wang Junfeng，Li Lei，Sun Fuchun，et al.A probabilityguaranteed adaptive timeout algorithm for high－speed network flow detection［J］.Computer Networks，2005，48（2）：215－233.

［6］Ryu B，Cheney D，Braun H W.Internet flow characterization：adaptive timeout strategy and statistical modeling［C］／／Workshop on Passive and Active Measurement（PAM），2001：95－105.

［7］周明中，龚 俭，丁 伟.网络流超时策略研究［J］.通信学报，2005，26（4）：88－93.

［8］周明中，龚 俭，丁 伟.高速网络中基于流速测度的动态超时策略［J］.软件学报，2006，17（10）：2141－2151.

［9］Cai Jing，Zhang Zhibin，Zhang Peng.An adaptive timeout strategy for profiling UDP flows［C］／／2010First International Conference on Network and Computing，2010：44－48.

［10］MAWI Working Group.WIDE traffic archive［EB／OL］.［2011－09－03］.http：／／mawi.wide.ad.jp／.

［11］Zhang Y，Breslau L，Paxson V，et al.On the characteristics and origins of Internet flow rates［C］／／Proc of the ACM SIGCOMM 2002，2002：309－322.

［12］叶 震，施伟伟.基于TCP＿IP报头分析和主动测试的DDoS攻击响应机制［J］.合肥工业大学学报：自然科学版，2010，33（3）：363－367.

Research on UDP flow timeout strategy in high－speed network

ZHAO Xiao－huan1， XIA Jing－bo1， ZHU Chang－hong2

（1.College of Information and Navigation，Air Force Engineering University，Xi’an 710077，China；2.Troop 95429of The People’s Liberation Army，Kunming 650200，China）

With the continuous emergence and rapid development of social network，online video，e－commerce，instant message，micro－blogging，etc.，great changes have taken place in the percentage and property of UDP traffic on the Internet.By the analysis of the state－of－the－art flow timeout strategies，their deficiencies and shortcomings are pointed out when applied in UDP traffic.Then，a differentiated updating timeout strategy（DUToS）for profiling UDP flows is proposed based on the analysis of the property of real UDP flows.Experimental results show that the algorithm of DUToS is more suitable for UDP traffic and can effectively improve the performance of network traffic measurement system.

high－speed network；UDP flow；flow timeout strategy；differentiated updating timeout strategy（DUToS）

TP393

A

1003－5060（2013）02－0176－06

10.3969／j.issn.1003－5060.2013.02.011

2012－08－24；

2012－10－16

陕西省自然科学基金重点资助项目（2012JZ8005）；全军军事学研究生课题资助项目（2010XXXX－488）

赵小欢（1984－），男，湖北枣阳人，空军工程大学博士生；

夏靖波（1963－），男，河北秦皇岛人，博士，空军工程大学教授，博士生导师.

（责任编辑 闫杏丽）