论文部分内容阅读
摘 要：互联网作为20世纪发展最为迅速的技术之一，已经成为现代信息社会最重要的基础设施，成为国家进步和社会发展的重要支柱。本文针对现有数据包抽样算法小流估计误差大的缺陷，提出一种新的数据包抽样算法。该算法根据到达数据包所属流大小的估计值设置包抽样率，使得大流所含数据包抽样率低，小流所含数据包抽样率高。理论分析和实验结果均表明，与已有算法相比，该算法具有更高的准确性和良好的扩展性，更适合于工程应用。
关键词：流量测量；流量抽样；大流识别；数据包抽样
中图分类号：TP393.06
1 数据包公平抽样概述
互联网规模的不断壮大，使得全面地理解、掌握网络运行行为、预测网络未来的发展、监控、管理互联网越来越难。互联网的复杂化致使人们对这样一个日益信赖的信息基础设施，依然知之甚少。在当前高速网络链路条件下，传统的全数据测量方式已不再适用。为了实现线速测量，对于每个数据包，能允许的平均处理时间越来越小，如果使用专用的硬件实现流量测量，代价极大。为了降低代价，提高可扩展性，流量缩減是有效的方法。抽样是其中最有效的方法之一。然而，由于网络数据流流量分布的不均匀性，常用的均匀随机抽样和固定周期抽样却无法完整地保留数据流级的流量信息，如并发流数目、流长分布等等。但是，网络安全检测、网路入侵检测和业务流分类等需要完整数据流级信息的应用而言，均匀随机抽样抽取了占网络流总数很小那部分大流，而占网络流总数很大的那部分小流却有很多无法被抽取。这种情况下，公平抽样被提出，是指通过牺牲大流的数据分组抽样率以换取更高的小流数据分组抽样率。
简单、高效、准确地测量是深入理解网络基本特性、掌握网络行为规律的基础，而网络流量测量作为网络测量的重要组成部分，通常以数据包为处理单元进行操作。在每个数据包到来时需要进行一次处理，因此，数据采集的计算复杂度与网络数据包到达的频率PPS（packets per second，每秒分组数）成正比。随着带宽的增加，数据包到达频率越来越高，使得单位数据包的处理时间越来越短，处理难度越来越大，这就要求网络流量测量设备具有更高的能力去处理每个数据包。在这种情况下，通过抽样选择部分有代表性的数据进行处理，是高速网络流量测量的一个解决方案。1993年，Claffy提出将抽样方法用于网络流量测量中，以估计数据包大小和到达间隔。在此之后，抽样成为高速网络流量测量的基本方法之一。当前应用最广泛的抽样方法是均匀随机抽样和系统抽样。均匀随机抽样以固定概率p对任意数据包进行抽样。系统抽样以固定的间隔抽取对象，在选择抽取第一个对象后，每隔N个对象选择下一个对象。Cisco将抽样机制应用于Netflow中，成为当前网络设备中应用最广泛的流量采集技术之一。
由于网络中的流具有“重尾分布”的特性，随机抽样等传统的抽样方法会丢失大量小流信息，正是在这一背景下，研究人员提出了“公平抽样”，其基本思想是牺牲少量大流数据包的抽样率，提升小流数据包的抽样率。比较经典的算法为SGS算法（sketch guided sampling），通过设置包抽样比为该数据包所属流的当前流量的递减函数，与传统抽样方法相比，SGS算法较好地保证了数据流之间公平性，但仍然存在小流估计误差大的缺点。本章正是针对这一缺陷，提出一种新的用于流大小估计的算法，我们称之为EstFlows算法。
2 EstFlows算法原理
设置一块缓存用于存储流记录，当有数据包到来时，查看缓存中是否存在对应的流记录，若存在，则以概率p（s）抽取该数据包并更新流记录；否则，抽取该数据包，创建新的记录。考虑到缓存溢出时的特殊情况，在查找流记录之前，加入了缓存是否已满的判断语句。
公平抽样的出发点是以牺牲少量大流数据包的抽样率换取小流数据包的抽样率，从而提高小流的估计准确度。因此，数据包的抽样概率应设定为一随数据包数目增加而递减的函数，本章定义为p（s）=1/（1+（εs）2），其中ε为平均评估误差。
该抽样函数与SGS方法所使用的抽样函数相比，随着数据包的增加，函数值，即抽样率下降的更快，进一步降低了大流数据包抽样时消耗的资源，用于小流数据包的抽样，提高了小流估计的准确性。
3 理论分析
网络流量测量中通常使用时间复杂度、空间复杂度、内存访问次数和准确性四个指标衡量算法的优劣。时间复杂度和内存访问次数直接关系到算法的处理速度，决定了算法是否满足实际应用的需求，尤其在当前的高速网络链路中，显得尤为重要。现在的半导体技术是否能达到算法的要求，空间复杂度是很重要的一个指标，是工程应用的基础。
3.1 时间复杂度
当一个数据包到达时，首先查看流缓存中是否存在相应的流记录，本章采用hash方案，计算复杂度为O（1）。在此之后的操作包括流记录的更新和新建等，都是有限常数次指针操作，其计算复杂度为O（1），因此该方法处理一个数据包所需时间为O（1）。
3.2 空间复杂度
由于EstFlow算法中每个流的第一个数据包都会被抽取，因此，该算法所需存储空间的大小就是测量时间段内流的数目，因而也是确定不变的，即为流记录缓存的大小。假设R为链路速率（单位为字节每秒），b为数据包平均大小；n为每流平均数据包数，则在时间t内到达的流个数，也即所需流记录缓存大小为M=[t/（bn）]R。
3.3 内存访问次数
访问存储器次数，是影响一个算法能否处理高速网络数据的重要因素之一。本章算法中，每个数据包到达时，查找是否存在相应的流记录，采用hash表存储，需访问存储器1次。如果没有相应的流记录，则新建，此时，需要访问存储器2次，包括写操作和指针。否则，则丢弃该数据包。因此，每个数据包需要访问内存的次数最多为3次，最少为1次。
3.4 实现的考虑 EstFlow算法中，流记录缓存最多需要访问内存3次。当前的半导体技术中，SRAM的访问速度可以达到2-4ns。假定采用访问速度为3ns的SRAM，最坏情况下EstFlow算法需要9ns处理一个数据包。在OC-192链路上，设满速率传输包长为40字节的数据包，则包到达间隔为32ns。因此，MFEPS算法完全可以满足OC-192链路的要求。
4 实验验证
准确性是测量的基本要求，本章使用测量误差的标准差来衡量算法流量估计的准确性。定义如下：假设在测量周期内，链路上共有N条并发流Fi（1≤i≤N），Fi的流量大小为fi（1≤fi≤M），fi的估计值为 。
令 ，Ej={ei|f=j}（j∈[1，M]），定义流量大小为i的数据流的测量误差的标准差为 。
实验所用数据相关信息如表1所示。
图1是我们对实验数据分析所得，横轴表示流从小到大的顺序，纵轴表示流的大小。为了有更直观的显示效果，我们只选取了放大后的部分曲线。可以发现，大流数量少，但包含流量多，而小流数量多，包含流量小，即满足“重尾分布”特性，这是符合前人的研究成果的。
表1 实验数据
Data Link type rate Measurement interval
Trace OC192 10Gbit/s 4800s
图1 实验数据分析图
图2为分别取ε=0.5和ε=0.2时EstFlow算法和SGS算法用于流量估计时的测量误差标准差。可以发现，在ε=0.5时，EstFlow算法的标准差低于SGS方法，且在流大小为15000左右时，近乎相等。在ε=0.2时，两种算法的标准差基本相同，在流大小为15000时，基本相同。综合来看，对于小流来说，EstFlow算法的标准误差低于SGS算法更为明显，这恰恰验证了前文抽样率的变化，即和SGS算法相比，EstFlow算法降低了大流的数据包抽样率，提升了小流估计的准确性。
（a）ε=0.5
（b）ε=0.2
图2 流量估计误差标准差
5 结束语
本章针对SGS算法的缺点，提出了一种用于网络中流大小估计的算法—EstFlow算法。该算法设定数据包的抽样概率为一随数据包个数增加而递减的函数，以达到数据流之间的公平抽样。和已有的SGS算法相比，EstFlow算法进一步降低了大流数据包的抽样概率，提高小流估计的准确性。通过理论分析和实验验证，EstFlow算法能够满足10Gbit/s链路的测量需要，同时具有较高的准确性，且易于实现，更适合工程应用。下一步的主要工作是根据不同的业务需求，有针对性地采用不同方法进行流量测量。
参考文献：
[1]Claffy K C，Polyzos G C，Braun H W.Application of sampling methodologies to network traffic characterization[J].ACM SIGCOMM Computer Communication Review，1993（04）：194-203.
[2]Hu C，Liu B，Wang S，et al.ANLS：Adaptive Non-Linear Sampling Method for Accurate Flow Size Measurement[J].Communications，IEEE Transactions on，2012（03）：789-798.
[3]Bhatia S，Kumar A，Fiuczynski M E，et al.Lightweight，high-resolution monitoring for troubleshooting production systems[C]//Proceedings of the 8th USENIX conference on Operating systems design and implementation.USENIX Association，2008：103-116.
[4]董永吉，陈庶樵，刘强.网络自适应公平分组抽样算法研究[J].计算机工程与设计，2010（02）：270-274.
[5]Kumar A，Xu J.Sketch guided sampling–using on-line estimates of flow size for adaptive data collection[C]//Proc.IEEE Infocom.2006.
[6]Grieco L A，Barakat C.An analysis of packet sampling in the frequency domain[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference.ACM，2009：170-176.
[7]張进，邬江兴，钮晓娜.空间高效的数据包公平抽样算法[J].
作者简介：夏靖波（1963-），男，河北秦皇岛人，教授，博士后，主要从事军事通信网络规划、军事通信网络管理技术研究。
作者单位：西安工业大学，西安 710021
关键词：流量测量；流量抽样；大流识别；数据包抽样
中图分类号：TP393.06
1 数据包公平抽样概述
互联网规模的不断壮大，使得全面地理解、掌握网络运行行为、预测网络未来的发展、监控、管理互联网越来越难。互联网的复杂化致使人们对这样一个日益信赖的信息基础设施，依然知之甚少。在当前高速网络链路条件下，传统的全数据测量方式已不再适用。为了实现线速测量，对于每个数据包，能允许的平均处理时间越来越小，如果使用专用的硬件实现流量测量，代价极大。为了降低代价，提高可扩展性，流量缩減是有效的方法。抽样是其中最有效的方法之一。然而，由于网络数据流流量分布的不均匀性，常用的均匀随机抽样和固定周期抽样却无法完整地保留数据流级的流量信息，如并发流数目、流长分布等等。但是，网络安全检测、网路入侵检测和业务流分类等需要完整数据流级信息的应用而言，均匀随机抽样抽取了占网络流总数很小那部分大流，而占网络流总数很大的那部分小流却有很多无法被抽取。这种情况下，公平抽样被提出，是指通过牺牲大流的数据分组抽样率以换取更高的小流数据分组抽样率。
简单、高效、准确地测量是深入理解网络基本特性、掌握网络行为规律的基础，而网络流量测量作为网络测量的重要组成部分，通常以数据包为处理单元进行操作。在每个数据包到来时需要进行一次处理，因此，数据采集的计算复杂度与网络数据包到达的频率PPS（packets per second，每秒分组数）成正比。随着带宽的增加，数据包到达频率越来越高，使得单位数据包的处理时间越来越短，处理难度越来越大，这就要求网络流量测量设备具有更高的能力去处理每个数据包。在这种情况下，通过抽样选择部分有代表性的数据进行处理，是高速网络流量测量的一个解决方案。1993年，Claffy提出将抽样方法用于网络流量测量中，以估计数据包大小和到达间隔。在此之后，抽样成为高速网络流量测量的基本方法之一。当前应用最广泛的抽样方法是均匀随机抽样和系统抽样。均匀随机抽样以固定概率p对任意数据包进行抽样。系统抽样以固定的间隔抽取对象，在选择抽取第一个对象后，每隔N个对象选择下一个对象。Cisco将抽样机制应用于Netflow中，成为当前网络设备中应用最广泛的流量采集技术之一。
由于网络中的流具有“重尾分布”的特性，随机抽样等传统的抽样方法会丢失大量小流信息，正是在这一背景下，研究人员提出了“公平抽样”，其基本思想是牺牲少量大流数据包的抽样率，提升小流数据包的抽样率。比较经典的算法为SGS算法（sketch guided sampling），通过设置包抽样比为该数据包所属流的当前流量的递减函数，与传统抽样方法相比，SGS算法较好地保证了数据流之间公平性，但仍然存在小流估计误差大的缺点。本章正是针对这一缺陷，提出一种新的用于流大小估计的算法，我们称之为EstFlows算法。
2 EstFlows算法原理
设置一块缓存用于存储流记录，当有数据包到来时，查看缓存中是否存在对应的流记录，若存在，则以概率p（s）抽取该数据包并更新流记录；否则，抽取该数据包，创建新的记录。考虑到缓存溢出时的特殊情况，在查找流记录之前，加入了缓存是否已满的判断语句。
公平抽样的出发点是以牺牲少量大流数据包的抽样率换取小流数据包的抽样率，从而提高小流的估计准确度。因此，数据包的抽样概率应设定为一随数据包数目增加而递减的函数，本章定义为p（s）=1/（1+（εs）2），其中ε为平均评估误差。
该抽样函数与SGS方法所使用的抽样函数相比，随着数据包的增加，函数值，即抽样率下降的更快，进一步降低了大流数据包抽样时消耗的资源，用于小流数据包的抽样，提高了小流估计的准确性。
3 理论分析
网络流量测量中通常使用时间复杂度、空间复杂度、内存访问次数和准确性四个指标衡量算法的优劣。时间复杂度和内存访问次数直接关系到算法的处理速度，决定了算法是否满足实际应用的需求，尤其在当前的高速网络链路中，显得尤为重要。现在的半导体技术是否能达到算法的要求，空间复杂度是很重要的一个指标，是工程应用的基础。
3.1 时间复杂度
当一个数据包到达时，首先查看流缓存中是否存在相应的流记录，本章采用hash方案，计算复杂度为O（1）。在此之后的操作包括流记录的更新和新建等，都是有限常数次指针操作，其计算复杂度为O（1），因此该方法处理一个数据包所需时间为O（1）。
3.2 空间复杂度
由于EstFlow算法中每个流的第一个数据包都会被抽取，因此，该算法所需存储空间的大小就是测量时间段内流的数目，因而也是确定不变的，即为流记录缓存的大小。假设R为链路速率（单位为字节每秒），b为数据包平均大小；n为每流平均数据包数，则在时间t内到达的流个数，也即所需流记录缓存大小为M=[t/（bn）]R。
3.3 内存访问次数
访问存储器次数，是影响一个算法能否处理高速网络数据的重要因素之一。本章算法中，每个数据包到达时，查找是否存在相应的流记录，采用hash表存储，需访问存储器1次。如果没有相应的流记录，则新建，此时，需要访问存储器2次，包括写操作和指针。否则，则丢弃该数据包。因此，每个数据包需要访问内存的次数最多为3次，最少为1次。
3.4 实现的考虑 EstFlow算法中，流记录缓存最多需要访问内存3次。当前的半导体技术中，SRAM的访问速度可以达到2-4ns。假定采用访问速度为3ns的SRAM，最坏情况下EstFlow算法需要9ns处理一个数据包。在OC-192链路上，设满速率传输包长为40字节的数据包，则包到达间隔为32ns。因此，MFEPS算法完全可以满足OC-192链路的要求。
4 实验验证
准确性是测量的基本要求，本章使用测量误差的标准差来衡量算法流量估计的准确性。定义如下：假设在测量周期内，链路上共有N条并发流Fi（1≤i≤N），Fi的流量大小为fi（1≤fi≤M），fi的估计值为 。
令 ，Ej={ei|f=j}（j∈[1，M]），定义流量大小为i的数据流的测量误差的标准差为 。
实验所用数据相关信息如表1所示。
图1是我们对实验数据分析所得，横轴表示流从小到大的顺序，纵轴表示流的大小。为了有更直观的显示效果，我们只选取了放大后的部分曲线。可以发现，大流数量少，但包含流量多，而小流数量多，包含流量小，即满足“重尾分布”特性，这是符合前人的研究成果的。
表1 实验数据
Data Link type rate Measurement interval
Trace OC192 10Gbit/s 4800s
图1 实验数据分析图
图2为分别取ε=0.5和ε=0.2时EstFlow算法和SGS算法用于流量估计时的测量误差标准差。可以发现，在ε=0.5时，EstFlow算法的标准差低于SGS方法，且在流大小为15000左右时，近乎相等。在ε=0.2时，两种算法的标准差基本相同，在流大小为15000时，基本相同。综合来看，对于小流来说，EstFlow算法的标准误差低于SGS算法更为明显，这恰恰验证了前文抽样率的变化，即和SGS算法相比，EstFlow算法降低了大流的数据包抽样率，提升了小流估计的准确性。
（a）ε=0.5
（b）ε=0.2
图2 流量估计误差标准差
5 结束语
本章针对SGS算法的缺点，提出了一种用于网络中流大小估计的算法—EstFlow算法。该算法设定数据包的抽样概率为一随数据包个数增加而递减的函数，以达到数据流之间的公平抽样。和已有的SGS算法相比，EstFlow算法进一步降低了大流数据包的抽样概率，提高小流估计的准确性。通过理论分析和实验验证，EstFlow算法能够满足10Gbit/s链路的测量需要，同时具有较高的准确性，且易于实现，更适合工程应用。下一步的主要工作是根据不同的业务需求，有针对性地采用不同方法进行流量测量。
参考文献：
[1]Claffy K C，Polyzos G C，Braun H W.Application of sampling methodologies to network traffic characterization[J].ACM SIGCOMM Computer Communication Review，1993（04）：194-203.
[2]Hu C，Liu B，Wang S，et al.ANLS：Adaptive Non-Linear Sampling Method for Accurate Flow Size Measurement[J].Communications，IEEE Transactions on，2012（03）：789-798.
[3]Bhatia S，Kumar A，Fiuczynski M E，et al.Lightweight，high-resolution monitoring for troubleshooting production systems[C]//Proceedings of the 8th USENIX conference on Operating systems design and implementation.USENIX Association，2008：103-116.
[4]董永吉，陈庶樵，刘强.网络自适应公平分组抽样算法研究[J].计算机工程与设计，2010（02）：270-274.
[5]Kumar A，Xu J.Sketch guided sampling–using on-line estimates of flow size for adaptive data collection[C]//Proc.IEEE Infocom.2006.
[6]Grieco L A，Barakat C.An analysis of packet sampling in the frequency domain[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference.ACM，2009：170-176.
[7]張进，邬江兴，钮晓娜.空间高效的数据包公平抽样算法[J].
作者简介：夏靖波（1963-），男，河北秦皇岛人，教授，博士后，主要从事军事通信网络规划、军事通信网络管理技术研究。
作者单位：西安工业大学，西安 710021