软件定义网络技术(SDN, software defined networking)为流量工程、服务质量优化等提供了一种更好的解决途径.在全网范围内对时变的动态流量进行准确和及时的测量，能够有效支持故障诊断、攻击检测、流量工程、负载均衡等.然而，流量测量面临的一个主要挑战是网络流量巨大，对于当前的流量规模和链路速率，可能会同时存在数百万条并发的数据流，导致测量系统无法为这些流同时维护状态信息. NetFlow^[1]、sFlow^[2]等提出的采样测量方法存在误差较高等问题，Mai等^[3]的分析结果表明，采样方法所导致的偏差会明显影响网络攻击检测的准确性.

研究显示，网络中大量的流为小流，少数流为大流，并且绝大部分流量分布集中在这些少量的大流中^[4].这里的大流是指在一个测量时间段内传输的报文或者字节数量超过一定数量的流.因此，快速测量以识别大流对于整个工作具有至关重要的作用.针对SDN环境下的大流检测问题，ProgME提出了一种可编程流量测量体系结构，能够针对用户定义的流量集合收集统计数据^[5].为了支持多种流量测量任务，Elastic Sketch^[6]提出了一种弹性动态的sketch模型，并能够对其进行动态配置，以提升流量测量的灵活性.为了避免对交换机架构的修改，Moshref^[7]和Harrison^[8]等分别提出了运行于不同商业交换机上的流量测量方案，Moshref等^[9]提出了一种在测量过程中优化使用OpenFlow交换机流表资源的方法. Xing等^[10]初步讨论了将采样和流表测量相结合进行测量的可行性和如何优化测量流表项的问题，并未研究如何高效地进行流量采样的问题.笔者提出一种SDN流量采样与流表测量相结合的两阶段大流检测机制，一方面，能够基于粗粒度的流量采样技术在源地址或目的地址等维度上以聚合的方式快速高效地寻找出疑似大流；另一方面，针对这些疑似大流，采用在OpenFlow交换机中加载测量流表的方式进行细粒度的监测，从而能够有效压缩OpenFlow交换机中的测量流表项，以较高的精度测量网络中的大流，并且不需要修改现有交换机的实现方法，方便在网络中进行部署.

1 两阶段大流检测机制

OpenFlow为每条流提供了分组、字节、持续时间3种类型的统计计数器.集中式控制器通过周期性地向各个交换机发送Read-State消息来获取这些计数器的最新值以及网络状态信息等.理论上，通过在存储器中为每条流增加一个测量表项，网络管理员可以实现对每条流的大小、分组数等信息的统计，然而，一方面这种测量将极大地消耗宝贵的三态内容寻址存储器(TCAM, ternary content addressable memory)资源；另一方面，频繁的查询会对交换机和控制器带来极大的开销.受TCAM资源的约束，为每条流建立一个测量流表项并不现实，需要设计相应的优化方案.

1.1 两阶段检测机制设计

采样是进行高速网络流量测量的一个通用解决方案，但采样率对测量精度会产生重要影响.若采用读取OpenFlow交换机流表方式进行测量时，又会受制于OpenFlow交换机的资源限制.例如，通常情况下，sFlow检测系统每秒能够处理约100万条流，而POX控制器每秒仅能够处理约3万条流^[11].因此若利用sFlow技术进行粗粒度的大流检测，随后再利用流表测量机制对检测结果进行细粒度处理，则可以实现两者优势互补，有效提升大流检测的精度.基于此，笔者提出一种采样和流表读取相结合的两阶段动态大流检测机制SampleFlow.

在SampleFlow中，为了准确地测量出网络内的大流，首先通过sFlow采样机制对流量进行采样，并将发现的疑似大流结果上报至SDN控制器；其次，控制器根据寻找出的疑似大流向相应的交换机下发测量流表项对疑似大流进行流测量，进而准确发现网络中的大流.上述通过两阶段的采样和读流表操作，能够有效解决采样率影响测量精度、流表测量导致TCAM测量流表空间严重膨胀等问题.

由于网络中大流的数量只占整个流数量的很小一部分，能够通过SampleFlow第1阶段的疑似大流检测过程的流数目相对于原始流数目非常有限，有效降低了第2阶段需要在交换机加载的测量流表.尽管采样会带来一定的误差，但通过适当降低判别阈值，允许一定的误判，而尽量减少漏判，进而在第2阶段的测量中实现准确的测量.

1.2 基于sFlow采样的疑似大流检测

受路由策略的约束，不同的流可能会经过不同的转发设备，如图 1所示.假设网络中共有4条流t₁、t₂、t₃、t₄，根据路由约束，经过交换机S₁、S₂、S₃、S₄的流集合分别为{t₁, t₂}、{t₂, t₄}、{t₂, t₃}、{t₃, t₄}，此时若在每个交换机处都进行采样，则t₁、t₂、t₃、t₄被采样的次数分别为1、3、2、2，冗余采样率为100%.事实上，若仅在S₁和S₄处进行采样，即可保证每条流恰好被采样1次，相对在所有位置进行全采样的方式能够有效节约测量资源.

综上，在进行流量采样的过程中，如何合理确定采样点是一个需要解决的问题.对此，利用控制器具有全网流量路由信息这一特点，结合路由信息进行采样点部署的决策，达到优化采样设计的目标.假设网络中共有m台可以进行采样的交换机S={s₁, s₂, …, s_m}和k条流T={t₁, t₂, …, t_k}，矩阵A为1个k×m的布尔矩阵，代表流t_i是否经过交换机s_j.

对于A中的任一元素a_ij，其值满足式(1)的约束：

$ {a_{ij}} = \left\{ \begin{array}{l} 1, 若流{t_i}经过交换机{s_j}\\ 0, 否则 \end{array} \right. $

(1)

以图 1所示的具有4台交换机和4条流的网络为例，其路由矩阵A具有如下形式：

$ \mathit{\boldsymbol{A}}\left\{ {\begin{array}{*{20}{c}} 1&0&0&0\\ 1&1&1&0\\ 0&0&1&1\\ 0&1&0&1 \end{array}} \right\} $

(2)

式(2)表示流1经过交换机1；流2经过交换机1、2、3等，而测量点的选择问题本质上就是在上述m台交换机中选择能够覆盖全部流的最小化交换机集合，以降低测量耗费.

上述问题可以抽象为集合覆盖问题：从1个k行、m列的0-1矩阵A_k×m中选出若干列，使得其中具有1的行覆盖所有的行，并能够使得这一过程中的代价最小.因此，该问题可以建模为

$ \min \sum\limits_{j = 1}^m {{\beta _j}{x_j}} $

(3)

$ {\rm{s.t.}}\;\;\sum\limits_{j = 1}^m {{a_{ij}}{x_{ij}} \ge 1, i = 1, 2, \cdots , k} $

(4)

$ \sum\limits_{{s_j} \in \rm{\mathbf {S}}} {{a_{ij}} \ge 1} $

(5)

$ {x_j} = \left\{ \begin{array}{l} 1, 若交换机{s_j}被选择为采样点\\ 0, 否则 \end{array} \right. $

(6)

其中β_j代表选择交换机S_j作为采样点所需要的耗费，约束条件(4)确保每条流都至少被1台交换机所采样，约束条件(5)表示每条流至少经过1台交换机，否则无法完成采样任务，约束条件(6)说明x_j是一个0-1变量，代表是否选择交换机S_j作为采样点.该问题是一个典型的NP完全问题，需要设计相应的启发式算法进行求解.对此，基于0-1分支定界的思想，提出一种采样点选择的启发式求解算法，如算法1所示.

算法1   基于分支定界的采样点选择

输入: OpenFlow交换机集合S, 流路由矩阵A

输出:采样点集合W

1 W=Ø, k=0, queue=NULL;

2 g=gain(W, A);

3 node=(W, k, g);

4 queue.add(node);

5 while (true)

6  node = get_first(queue);

7   if node is empty

8   break;

9  end if

10   k=node.k+1;

11  for each sw in S-node.s

12    TS = node.s∪{sw};

13    g = gain(TS, A)

14    if (TS, k, g) in queue or g < gain.min_bound(k)

15     continue; //剪枝

16    elseif g > gain.max

17     W=TS;

18   end if

19    node = (TS, k, g);

20    queue.add(node);

21  end for

22 end while

23 return W

在算法1中的第1行，首先初始化最终采样点集合W、选择的采样点数目k、结点队列queue，在算法第2~4行计算当前所选择采样点获得的收益值，构造结点，并将结点加入状态空间树(用队列保存状态结点).第5~22行循环进行采样点的选择，其中在每次选择1个新的交换机sw后，第13行计算其收益，若小于最小收益下界，则进行剪枝；否则，若大于当前收益，则更新W集合，最终返回所选择的采样点集合.

确定采样点之后，每台采样交换机上的sFlow代理对经过的分组按照预设的采样率进行采样，并将采样到的分组信息发送至sFlow采集器.如图 2所示，sFlow采集器针对所有采样到的流维护1个哈希表HT，假设某一采样分组p具有流标识id_p，且f_i=Hash(id_p)，则在收到该分组后，sFlow采集器将判断f_i是否已经在哈希表HT内，若是，则sFlow采集器将HT[f_i]的值增加volume(p)；否则，其将创建一个新的初始数值为volume(p)的表项HT[f_i].一旦HT[f_i]的数值超过预定的疑似大流阈值，则sFlow采集器将立即发送流标识id_p到SDN控制器，并标志该流为正在被SDN控制器测量的疑似大流.

在大流检测过程中，假阳性和假阴性是2个广泛使用的评价指标，前者代表检测结果中的误判情况，而后者表明了检测结果中的漏判情况.本步骤的主要目标是找出疑似大流，因此漏判比误判具有相对更严重的后果，后者可以在流表测量阶段进行过滤，只是会带来一定的流表空间浪费，而前者将直接导致测量结果的错误.因此，在疑似大流的判定过程中，通过引入一个松弛因子λ来适当降低疑似大流的判断阈值，容许一些误判，并随后在流表测量中将误判流排除.

1.3 基于流表查询的大流检测机制

在完成疑似大流的检测后，sFlow采集器将所检测到的疑似大流发送给SDN控制器，SDN控制器根据接收到的疑似大流向相应的OpenFlow交换机下发测量流表项开启测量任务，并随后读取这些测量流表项，从而获得每条测量流的实际流量数据，据此检测出真正的大流及其流量值等. 图 3给出了大流检测机制的示意，其中加载测量规则过程中，控制器根据sFlow采集器所上报的疑似大流信息生成测量规则，并按照一定的策略^[10]加载到相应的OpenFlow交换机上.而读取测量数据则是由控制器周期性地从交换机处读取最新的流量测量数据，进而通过流量值判断出真正的大流.

算法2给出了SampleFlow大流检测机制的总体流程.

算法2  SampleFlow大流检测算法

输入: OpenFlow交换机集合S, 流路由矩阵A，采样率r，疑似/真实大流阈值γ/γ′，测量流表分发策略Φ

输出:大流标识及其测量值矩阵M

1 W=Ø, M=Ο; //W为采样点集合

2 N=Ø, j=0;  //N为上报的疑似大流集

3获取sFlow采样点集合W; //算法1

4在采样点W处依照采样率r进行sFlow采样;

5 while (true) //采样开始

6  更新采样流集合F及测量值HT;

7  for each f_i in F //F为采样流集合

8    if HT(f_i)≥γ //流f_i测量值超出阈值

9     N=N∪{f_i};

10    end if

11   end for

12  为疑似大流F生成相应测量流表项;

13   Vol=ReadState.obtain(F); //读测量流表项

14   for each f_i in F

15    if Vol(f_i)≥γ′

16      M[j][0]=f_i, M[j]^[1]=Vol(f_i), j=j+1;

17    end if

18  end for

19 end while//采样结束

20 return M

在基于流表查询的大流检测机制中，流表空间资源是OpenFlow交换机最宝贵的资源，每台交换机的TCAM资源非常有限，而SampleFlow首先利用相对充裕的静态随机存取存储器(SRAM, static random access memory)资源来过滤出疑似大流，从而有效降低了对TCAM资源的消耗，并且解决了仅采用sFlow测量带来的高误差率问题.

2 试验评价及分析

笔者分别在sFlow采集器和POX控制器上实现了SampleFlow的采样点选择、测量流表项分配以及最终的大流识别等模块，并利用仿真和因特网实际测量数据从不同方面对其性能进行分析.

场景1  采样点选择算法性能分析

为了验证SampleFlow在确定采样点方面的有效性，实现了随机和最大结点介数(max # of OD)2种采样点选择算法.前者随机进行采样点选择，后者则始终选择介数(网络中经过该结点的流数目)最大的点为采样点，当能够覆盖网络中所有的流时，算法终止.

首先利用Abilene的网络和流量数据^[12]进行性能评估，为了便于讨论，这里假设在每台OpenFlow交换机上进行采样的代价相同.此外，选取采样点数量和冗余流数量2个指标来对算法的性能进行评价，其中采样点数量代表为了实现网络中流的全覆盖，至少需要在多少个结点进行采样.冗余流数量则代表在测量过程中有多少额外的冗余测量.

图 4所示为在不同规模的流数目情况下，为了实现流采样的全覆盖，用3种算法得到的最小采样点数目的变化趋势.可以看出，在Abilene拓扑中，随着流数目的增加，所需要的采样点数目也呈现增加的趋势(随机选择算法的波动相对较大)，但SampleFlow算法得到的采样点数目始终优于另外2种算法，表明SampleFlow能够以相对更小的代价实现流采样.这是因为SampleFlow算法采取的是一种启发式的类贪心机制，它存在一个针对当前阶段采样备选节点的筛选过程，在每一轮的选择中通过利用分支定界的思想来不断剔除那些效益较差的节点，从而获得总体效益较优的最终结果.相比之下，随机选取和节点介数最大策略在理论和实践上都没有体现出一种相对稳定的“去差选优”趋势，尤其对于随机选取策略，其本身的随机性更是给该方法带来了较大的不确定性.因此，SampleFlow算法在采样点选择方面有着更好的优越性，能够以较小的代价实现流采样.

图 5所示为基于3种算法所选择的采样点进行采样测量时冗余测量流所占的比例，可以发现，SampleFlow算法冗余流的比例相对最低.这样的实验结果符合预期，因为SampleFlow算法的采样点选择模块优化了各个采样点在网络流特征方面的代表能力，从而显著降低了整个测量系统的工作冗余度.

由于Abilene网络拓扑只包含12个路由器结点，规模相对较小，笔者进一步又利用Brite拓扑生成器^[13]生成100个结点的网络拓扑，且拓扑中的网络流量定义为源和目的节点对(OD, origin destination)之间的流量，路由按照最短路规则进行路由选择.

图 6所示为在不同规模的流数目情况下全覆盖采样所需的最小采样点数目变化趋势.可以看出，在Brite生成的拓扑中，SampleFlow算法得到的采样点数目同样始终优于另外2种算法，进一步验证了SampleFlow在采样点选择方面的有效性.

图 7示出了在Brite生成的网络拓扑中，基于3种算法所选择的采样点进行采样测量时冗余测量流所占的比例，可以发现SampleFlow算法所得到的冗余流比例相对最低.此外，随着网络规模的扩大，SampleFlow与其他2种方案之间的差距也就变得愈加明显，而这种现象产生的原因在于采样巧合性地对网络系统带来的影响会随着规模的扩大和结构的复杂而逐渐减弱，故而在仿真实验环境中，SampleFlow算法展现出更加明显的性能优势.

综合本部分的试验结果可以发现，无论对于真实网络拓扑及流量数据，还是仿真网络拓扑及流量数据，SampleFlow的采样点选择机制均能够得到相对好的结果.

场景2   SampleFlow大流检测精度分析

对于sFlow采集器上报的疑似大流，SampleFlow中SDN控制器通过直接读取OpenFlow交换机中对应测量流表项的计数器获取流的真实大小，因此所检测出的大流一定为网络中真实的大流，而不存在误判现象，亦即其结果的假阳性为0.另一方面，在sFlow采样阶段，可能会有一些真正的大流因采样误差而被过滤，导致无法被检测出，会存在漏判的可能，存在一定的假阴性.因此，在测量精度评价方面，应以假阴性指标对SampleFlow进行评价.

实验以因特网应用数据分析中心(CAIDA, center for applied internet data analysis)测量数据集^[14]为基础，这里大流定义为发送数据量超过1MB的流.对于sFlow采样方法，分别以0.01~0.05不同的采样率进行流量采样，然后基于采样结果推断每条流的大小，并找出那些大于1MB的流作为检测出的大流.

在SampleFlow中，其第1阶段同样采用类似的采样方法，但为了减小漏判率，笔者以不同的松弛因子λ放松对大流检测标准的约束，分别以0.9、0.8和0.7倍于1MB的流判断为疑似大流，随后在第2阶段的流表测量方法中再从这些疑似大流内检测出真正的大流.整个网络中OpenFlow交换机总的TCAM可用流表空间设置为1000.这种松弛判断方法不适合于仅采用sFlow采样的机制，因为其会带来较高的误判率，而sFlow无法消除这种误判.

图 8所示为SampleFlow方法和仅采用sFlow采样方法得到的大流检测精度对比情况，可以看出，在同样的采样率设置下，具有最大松弛度(λ最小)的SampleFlow方法其检测精度也最高.然而，随着检测标准中松弛度的增加，也会带来TCAM资源消耗的同步增加.因此，在选择λ时，需要结合测量精度的要求和测量资源的限制进行合理折中.此外，大流检测的精度同样随着采样率的增加而增加.

3 结束语

快速、准确地识别出网络中的大流对于网络管理和网络安全具有重要意义，然而，当前无论是采样机制还是流表测量机制都存在一些问题.笔者针对SDN大流检测问题，提出了一种基于采样和流表查询的两阶段方法SampleFlow. SampleFlow首先通过粗粒度的采样方法寻找出网络内的疑似大流，随后通知SDN控制器对这些疑似大流采样流表测量的方法进行细粒度监测，从而找出真正的大流.由于网络中大流在数量上仅占总的流数很少的一部分，这一方法相对于直接测量有效降低了对OpenFlow交换机TCAM资源的耗费，同时又解决了直接采样方法所存在的精度不高等问题.实验结果显示，SampleFlow能够有效提升大流检测的精度，降低TCAM资源的耗费.此外，SampleFlow可以直接基于现有OpenFlow的工作逻辑实现，具有良好的扩展性.在下一步工作中，拟研究混合SDN网络环境中的大流快速检测机制，并考虑将其应用至具体的流量工程中.