数据流特征感知的交换机流表智能更新方法
针对软件定义计算机网络(SDN)中交换机流表匹配率低的问题，提出了数据流特征感知的交换机流表智能更新方法。首先，论述流表项的生存超时时间timeout对数据包匹配的影响，并且分析比较基于先进先出(FIFO)、近期最少使用(LRU)等一般方法存在的不足;其次，根据流表项的生存时间和数据流的特征密切相关的思想，利用基于隐马尔可夫模型(HMM)的深度流检测(DFI)技术对数据流进行分类;最后，根据流表资源和控制器计算资源状况，实现对不同类型数据流流表项的智能更新。采用校园数据中心网络行为数据的模拟实验表明，与流表更新的一般方法相比，智能方法能使流表匹配率提高5%以上，对SDN交换机的管理有实际意义。
0引言
软件定义网络(Software Defined Network， SDN)作为一种新的架构，利用分层的思想将控制平面和数据平面分离，为网络的部署和配置提供了极大的灵活性和可扩展性。然而当前的SDN网络只能对L2～L4层的信息进行识别，控制器在制定流表项的timeout值时，将所有的数据流同等对待，导致交换机中流表的匹配成功率只有不到20%[1]，极大地增加了控制器的负担，降低了网络的整体性能。为了提高流表的匹配率，提高数据传输和消息包的转发效率，学者开展了许多研究。Kim等[2]通过在交换机中增加缓存的方式，来存放因为硬超时时间hard_timeout时间到达而被删除的频繁匹配的流表项，以此来提高流表的匹配率，但本质上只是增加了流表的容量;同时流表项在缓存中的匹配速率相比三态内存寻址寄存器(Ternary Content Addressable Memory，TCAM)，性能要差很多。Zhu等[3]在控制器中增加一个缓存模块来记录流表项的到期时间，将流表项被再次安装的时间和到期时间的差值作为流表项的更新依据，但这个过程对软超时时间idle_timeout的动态更新存在只增不减的弊端。Kannan等[1]和Kim等[4]都是通过预测的方式，提前将最近一段时间内不会被匹配的流表项删除，预留流表空间给即将到来的数据流。前者通过马尔可夫模型来预测流表项中各个状态间的转换关系，据此来动态修改流表项中的idle_timeout值;后者通过预测数据包之间的到达时间间隔，删除近期不会被匹配的流表现达到预留空间的目的。Zhang等[5]提出将流表的工作方式类比为排队系统，将流表模型化为状态依赖的排队模型，并借助排队论定量地分析了hard_timeout对流截断次数和阻塞概率的影响。上述文献都是通过修改timeout值来提高流表的匹配率，但都没有将控制器的处理能力作为动态修改timeout值的制约因素。Liang等[6]将控制器单位时间内能够处理的packetin请求数作为约束条件，以满足该条件的最小idle_timeout值作为最终结果，从而实现满足控制器处理能力情况下，最大限度地提高流表匹配率的目的，但该过程假设所有数据流都具有相同分布参数，没有考虑不同数据流类型间的特征差异。在SDN网络中增加数据流类型感知技术方面，Jarschel等[7]在控制器中增加深度包检测(Deep Packet Inspection，DPI)模块，将数据流的前10个数据包发送给控制器进行检测，从众多数据流类型中检测出YouTube视频流，但DPI方法需要消耗较大的系统资源，且维护成本高，特别是对加密的网络流量无法识别，然而当前网络环境中加密数据流越来越多，这大大限制了DPI的应用范围。Qazi等[8]在控制器中增加了机器学习模块来识别应用流类型，对排名前40的安卓应用类型有94%的准确率，这避免了无法识别加密数据流的问题;同时减小了检测过程对系统性能的影响。何中阳等[9]使用隐马尔可夫模型(Hidden Markov Model，HMM)作为流类型识别方法，HMM相比其他方法具有特征库小，能够更快速地识别数据流类型的特点。
总之，目前针对流表的更新问题采用的方法，主要是寻找流表的匹配规律，来动态的更新timeout值，从而提高流表的匹配率，但还没有文献综合利用数据流类型信息和网络资源使用情况来更新流表。显然，流表项的生存时间和数据流的特征密切相关，因此本文结合不同数据流类型的特征差异，探索交换机流表的智能更新方法。
1SDN交换机的流表结构
1.1SDN工作原理
SDN将传统路由器中的控制平面和数据平面分离，通过集中式的控制平面实现网络的控制，整个SND网络由三部分组成：1)数据平面。由网络转发设备组成，负责数据包的转发操作。2)控制平面。负责对网络的集中控制，主要负责转发决策的制定。3)应用平面。由运行于控制器之上的应用程序组成，用户可以根据需要编写满足应用需求的应用程序。数据平面和控制平面之间的通信接口称为南向接口，大都采用OpenFlow协议。图1为数据平面和控制平面的关联和交互原理，控制平面掌握着网络全局信息，数据包在数据平面进行转发，一切转发决策都由控制平面制定，而所有的转发决策消息在交换机中都以流表项的形式存在。在当前的OpenFlow交换机中，为了保证数据包的快速匹配操作，使用TCAM来存储流表项。然而，TCAM的价格昂贵，而且能耗大，因此交换机中使用的TCAM容量都比较小，所能存储的流表项数目有限，因此，数据平面和控制平面之间需要通过packetin、flowmod和packetout等交互信息，为网络中的数据流提供数据转发服务。
1.2流表结构
在交换机中，控制器发出的命令，待执行的数据转发操作等，即软件定义网络的相关内容存放在交换机的流表中。流表中有一个或多个流表项，每个流表项的主要组成部分如图2所示。其中：匹配域是流表进行匹配的关键字段，匹配域和优先级唯一指定一个流表项，计数器用于统计数据流量的相关信息，指令集指示数据包匹配该流表项后的动作，超时时间包括idle_timeout和hard_timeout，前者表示在idle_timeout时间段内没有数据包匹配的流表项会被删除，后者表示从流表项安装开始经过hard_timeout时间后，流表项就会被删除，不管是idle_timeout还是hard_timeout，其值为0均表示流表项不会因为该超时时间被删除。
图3为传输数据包进入OpenFlow交换机后的匹配过程。首先由数据包解析模块解析得到数据包的头部，然后将数据包头部信息跟流表中的流表项进行匹配，流表的匹配工作是基于数据包的头部进行的，若有对应的匹配项，对数据包的处理按匹配流表项的动作集进行;若流表中没有匹配的流表项，如图1所示中的过程②和过程③，将通过packetin事件将数据包发送给控制器，控制器以flowmod的形式给传输路径上的所有交换机下发新流表项，但对于地址解析协议(Address Resolution Protocol， ARP)等出现数量很少的数据包，控制器仅以packetout消息通知交换机该如何转发数据包，不安装流表项。对packetin事件的响应，本文主要考虑flowmod消息。
由数据包的匹配过程可知，若交换机流表中一直没有匹配的流表项，交换机将会不断地向控制器发送packetin请求消息，给控制器造成很大的负担。由timeout字段的含义可知，在不考虑控制器对流表项进行删除的情况下，它决定了流表的更新策略，因此，如何合理地制定流表项的timeout值对数据包转发性能有很大的影响。本文重点研究idle_timeout值对流表匹配率的影响。如图4所示，其中Tpmin和Tpmax分别表示该数据包序列到达时间间隔的最小和最大值。当idle_timeout值设置得过小(Tpmax)时，虽然此时只产生一次packetin请求，但该数据流对应的流表项一直占用着流表资源。
理想情况为idle_timeout值等于Tpmax，此时数据流中除了第一个数据包会触发packetin请求消息，其余数据包都可以匹配该流表项而直接进行转发操作，且该流表项不会过多地占用流表资源。但是，交换机中的流表资源毕竟有限，且网络传输中包括音频流、视频流和普通文本流，每个数据流不可能都有相同的Tpmax值。针对上诉问题，本文的目的是根据不同数据流类型特征，在控制器处理能力范围内，最大限度地利用流表资源，提高流表的匹配率。
1.3交换机流表性能评价指标
为了评价交换机中，流表设计和配置，以及动态调整等方面性能的好坏，通常采用识别率、识别效率、数据包匹配率和流表利用率等多个评价指标，本文主要关心数据包类型的识别率，以及流表项动态调整后数据包匹配性能的好坏。
定义1识别率。识别率表示数据流被正确识别的概率，即被识别为正确的数据流类型数占总数据流数的比率。假设记ptu表示识别率，numtrue表示系统能够准确识别出的数据流数，numall表示总数据流数，则识别率可以用公式表示如下：
ptu=numtrue/numall×100%
显然，识别率越高说明分类效果越好，能够根据需求进行正确的转发和决策的数据流数越多。
定义2数据包匹配率。数据包匹配率是指到达交换机的数据包，在流表中能够找到匹配的流表项的数目占到达交换机的总数据包数的比率。假设记numma表示到达交换机的数据包能够在流表中找到匹配的流表项的数量，则匹配率pma计算公式如下：
pma=numma/numall×100%
匹配率越高说明流表的置换效果越好，需要给控制器发送的packet_in消息数目越少，因而能够减轻控制器的工作负担，提高数据包转发速率。
2流表更新的一般方法
OpenFlow标准协议通常采用置换算法和流表超时机制对流表进行更新。置换算法让控制器通过主动地向下层的OpenFlow交换机，发送流表删除消息来删除流表项，当交换机流表资源满负载时，对流表资源进行管理;流表超时机制则是通过控制OpenFlow交换机中流表项的timeout值，当某个超时计时器生效时，流表项会被删除，让出空间安装存放新的流表项。下面将阐述流表更新的两个算法。
2.1基于先进先出的置换算法
基于先进先出(First In First Out， FIFO)的置换算法因其实现简单，置换效率高，因此SDN初期常使用该算法作为流表置换算法。该算法的实质为：总是选择在流表中停留时间最长的流表项进行置换，即最先安装的流表项，最先从流表中删除。本文进一步将FIFO的置换算法和hard_timeout值相结合，此时idle_timeout值为0。由于hard_timeout超时引起的流表项删除，在超时计时器到期时删除相应的流表项即可，此处本文主要考虑由于流表溢出引起的置换操作。假设每个流表项对应的hard_timeout值随时间递减，则hard_timeout值越小表示该流表项越早安装。完善后算法的伪代码描述如下。
算法1中，通过函数findLeastHardTimeout寻找流表中当前hard_timeout值最小的流表项进行置换，即使该流表项当前正被数据包频繁地匹配，这会导致之后到达的数据包触发packetin请求消息，降低流表匹配率的同时，增加了控制器的处理负担;并且，该算法是基于hard_timeout超时机制进行更新，灵活性较差，对于网络中数据传输时间参差不齐的数据包，不能很好地满足传输需求。
2.2基于近期最少使用的置换算法
基于近期最少使用(Least Recently Used， LRU)的置换算法根据最近一段时间数据流匹配情况对流表项进行置换，更加符合实时的、连续的数据流环境。该算法与每个流表项最后匹配数据包的时间有关，基于已经很久没有被匹配的流表项可能在未来很长一段时间内也不会被匹配的局部性原理。本文进一步将LRU的置换算法和idle_timeout相结合，二者本质上都是对最近未使用的流表项进行删除，但idle_timeout相比LRU算法更为灵活，将它们结合在一起可以方便地实现流表的更新。假设每个流表项对应的idle_timeout值随时间递减，一旦有匹配的数据包到达，该流表项对应的idle_timeout值将被重置，当idle_timeout值等于0时，该流表项即被删除，因此当前idle_timeout值最小的流表项即为最近未使用时间最久的流表项。完善后算法的伪代码描述如下。
算法2中，函数addFlowEntry以(key，value)对的形式存储流表项，且根据timeouts值和数据包所属数据流类型dataType设置流表项的idle_timeout值，对于本节流表更新的一般方法而言，所有idle_timeout为相同的固定值。函数findLeastIdleTimeout寻找流表中当前idle_timeout值最小的流表项并将其置换出去，该置换算法能够避免FIFO中删除最近频繁匹配流表项的缺点，但也存在弊端，比如idle_timeout值一旦设定，不能在满足网络资源约束条件下动态修改，且没有考虑不同数据流类型间的特征差异。
3流表更新的深度智能感知方法
流表中流表项的生存时间和数据流特征密切相关，但在第2章阐述的流表更新的一般方法中，流表的更新没有利用数据流类型信息，而且更新策略中的timeout值一旦设置，不管网络数据传输状况如何都不再改变，这极大地降低了交换机中流表的匹配率和网络整体性能。本文认为在L2～L4层网络信息的基础上，增加数据流特征信息区分音频流、视频流和普通文本流等数据流类型，从而为不同流类型数据包的流表项制定不同的timeout值，能够在满足控制器处理能力的情况下，最大限度地利用流表资源，从而提高流表的匹配率。
3.1数据流类型特征统计
为了分析数据流特征，本文将数据流建模成典型的ON/OFF模型。其中：ON状态表示各个数据包的传输时间X1，X2，…，Xi，…，Xn，OFF状态表示数据包到达的时间间隔Y1，Y2，…，Yi，…，Yn，如图5所示。
考虑到数据流特征和数据流类型信息密切相关，根据消息传输的实际情况，本文将数据流分为音频流、视频流和普通文本流。为了分析这3种数据流类型的特征差异，本文从网络中随机抓取各种类型的数据流信息。从抓取的数据中，可以方便地获取数据包到达时间间隔和数据包长度信息。图6～7为数据包到达时间间隔和数据包长度的概率密度分布，图6(a)、(b)和(c)依次表示音频流、视频流和普通文本流数据包到达时间间隔的概率密度分布情况。由图6可知，音频流和视频流数据包到达的时间间隔普遍都远小于1s，但音频流相对视频流而言，数据包到达时间间隔的波动相对大一些，而普通文本流数据包到达的时间间隔参差不齐，大至几十秒，小至几十毫秒。图6(e)、(f)和(g)7(a)、(b)和(c)分别表示音频流、视频流和普通文本流数据包长度的概率密度情况，可见这3种数据流类型的数据包长度分布存在显著的差异。
3.2数据流类型感知方法
本文采用的数据流类型感知方法是一种基于行为的流量识别技术，根据一条流的多个数据包之间呈现的某种统计规则进行识别。具体地说，本文使用基于HMM的深度流检测(Deep Flow Inspection， DFI)技术对数据流进行识别[9]。由3.1节的分析可知，可以利用数据包到达的时间间隔和数据包长度信息作为区分音频流、视频流和普通文本流的依据。
3.2.1数据流感知模型
HMM是一个双重随机过程：其一是马尔可夫链，它是基本的随机过程，描述状态的转移;另一个是观测值在各状态中的分布概率，它描述状态和观测值之间的统计对应关系。数据流类型本身就是一种双重随机过程，数据包的外部特征是可观察的序列，而它们是按照数据流类型规则(隐含的状态)进行通信。HMM可以用五元组λ={N，M，π，A，B}表示，其中：
①N表示隐藏状态的数量，状态的集合表示为X={s1，s2，…，sN}，并用qt表示t时刻的状态，qt∈X;
②M表示每个状态中可以观察到的符号数，标记各个观察符号为V={v1，v2，…，vM}，观察序列O={o1，o2，…，oT}，T为观察序列的长度，ot∈V;
③状态转移概率分布A={aij}，这里aij=P{qt+1=sj|qt=si}(1≤i， j≤N)，其中0≤aij≤1，∑N1aij=1;
④数据包特征的概率分布B=[bj(k)]，表示数据流类型sj输出相应数据包特征的概率，其中bj(k)=P{ot=vk|qt=sj}(1≤j≤N，1≤k≤M);
⑤初始状态分布π=[πi]，πi=P{q1=si}，1≤i≤N。
HMM由两类状态N、M和3类概率π，A和B组成，可将其简写为λ={π，A，B}。本文中，主要利用HMM对数据流进行分类，将数据流分为音频流(s1)、视频流(s2)和普通文本流(s3)3种类型，隐藏状态的集合表示为X={s1，s2，s3}，且将数据包大小和包到达时间间隔作为识别数据流类型的特征参数。
3.2.2模型参数评估
对感知模型建模之后，首先需要对音频流、视频流和普通文本流对应的模型参数进行评估，将它们对应的模型分别记为λ1、λ2和λ3。因为3种数据流类型参数评估方法和过程相同，所以本文统一用模型λ进行讨论，并使用BaumWelch算法进行模型参数评估[10]。
在评估过程的初始，π、A、B三个参数只要在满足模型基本条件下进行随意的选取，在整个模型评估过程中会进行迭代修正。BaumWelch重估公式表示为：
根据选取的观察序列O和初始模型λ={π，A，B}，由重估公式(1)～(3)求得一组新参数i，ij和j(X)，即得到一个新的模型=(，，)，可以证明P(O/)>P(O/λ)，即由重估公式得到的比λ在表示观察序列O方面要好。重复上述过程，逐步改进模型参数，直到P(O/)收敛，此时的即为所求模型。由上述过程，便可求得3种数据流类型对应的模型λ1、λ2和λ3。
3.2.3感知模型分类
3.3流表项智能更新策略
由于流表项timeout值的制定，直接影响流表中流表项数目和单位时间内控制器需要处理的packetin请求数。为了能够在控制器处理能力范围内，实现流表资源的最大利用率，流表智能更新策略首先对流表资源和控制器计算资源设定阈值参数，再根据当前的流表项数目和控制器单位时间内需要处理的packetin请求数所处的阈值范围，对idle_timeout值进行动态调整，从而实现流表的智能更新。
3.3.1更新参数的计算
3.3.2流表智能更新算法
为了提高流表匹配率，流表智能更新算法主要基于以下思想对idle_timeout值进行更新：1)流表资源充裕的情况下，尽量增大idle_timeout值;2)流表资源比较匮乏时，根据控制器计算资源情况减小idle_timeout值。
图78反映了流表资源和控制器计算资源间的相互关系，当entryNum和pktinNum处在不同阈值区域时，采取不同的更新操作。将两类资源通过3个阈值进行划分的目的，是为了将资源利用率“过低”“刚好”“过高警告”和“过高”4种状态都反映出来。图78中“++”表示利用式(4)求得的tpktin对idle_timeout进行“+「tpktin”操作，“+”表示进行“+1”操作，“--”表示利用式(5)求得的tmatch对idle_timeout进行“-「tmatch”操作，“-”表示“-1”操作，空白区域表示不采取任何措施。该算法的具体伪代码描述如下。
4模拟实验
本文使用真实的数据中心网络行为数据作为测试数据，该数据来源于文献[11]的作者分别从校园数据中心网络EDU1和EDU2获得的UNIV1和UNIV2数据集，经作者授权可从http：//～处下载。数据中心EDU2比EDU1规模大，其中EDU1具有500台服务器和22台交换机，EDU2具有1093台服务器和36台交换机，它们均为校园提供Email、Web请求和音视频流等服务，因此数据集UNIV1和UNIV2均为包含音频流、视频流和普通文本流的混合数据流数据。这些数据原本是用于分析在数据包和数据流级别上的传输特性对链路利用率、阻塞和丢包率等的影响，从而为数据中心网络进行科学管理提供依据。通过比较相同时间内收集到的数据包数可知，数据中心EDU2中单位时间内交换机需要处理的请求数远多于EDU1，因此从UNIV1和UNIV2数据集中选取数据进行实验，也能够分析比较本文描述的3种算法对两种不同规模校园数据中心网络的影响。
本文使用floodlight和mininet搭建SDN网络环境，从而将上文描述的3种算法对交换机流表更新性能的影响进行测定[2]。实验过程中分别从UNIV1和UNIV2数据集中选取5组数据作为实验测试数据，每个数据包含数据包到达时间、源地址、目的地址和数据包长度等信息，本文将具有相同源地址和目的地址的数据包视为同一数据流，按时间序列模拟数据包的到达。表1为3种数据流类型的识别率，结果表明本文的分类算法能够达到90%以上的分类准确率。
视频流音频流普通文本流
这3个列名与第1列的数据项重复，是否表达正确?请明确。三种方法体现在哪里?回复：问题3：表格没有写错，分别表示三种数据流类型，该表格是为了说明各个数据流之间识别的概率，视频流到视频流的概率为0.9513，表示视频流被正确识别为视频流的概率为95.13%，视频流到音频流的概率表示视频流被错误识别为音频流的概率，依次类推……
实验过程中idle_timeout的初值设置为5s，该值为NOX控制器中的默认值，流表容量Tmax为1500，控制器单位时间能够处理的packetin请求数Pmax为30000[12]，hard_timeout初值设置为10s[13]，流表的智能更新周期T设置为2s，该值不至于让控制器负担过重，同时能达到相对好的实验效果，流表容量的阈值参数ftc={800，1200，1400}，单位时间内packetin请求数阈值集合pktin={15000，24000，27000}，这些阈值参数的设置是通过多次实验得到的经验值。
图89为流表匹配率分布情况，分别为使用UNIV1和UNIV2中的部分数据集进行测试的实验结果，其中FIFO、LRU和IFTUA(Intelligent Flow Table Update Arithmetic)分别表示本文描述的3种算法。由图89可知，UNIV1实验数据组中，FIFO的匹配率总体上要高于LRU的匹配率，这是因为FIFO在hard_timeout时间内始终占据流表资源，在数据流数目相对较少的情况下，能够更加充分地利用流表资源。UNIV2实验数据组中，单位时间内的数据流数目相比UNIV1要大很多，流表资源相对匮乏，该情况下LRU算法相比FIFO算法能更加灵活地对流表项进行置换，因此能够达到更高的匹配率。本文提出的流表智能更新算法能够根据数据流类型信息和网络资源状况对timeout值进行动态调整，兼具FIFO和LRU的优点，因此匹配率始终高于流表更新的一般方法。
5结语
本文针对当前OpenFlow交换机中存在的流表匹配率低的问题，首先详细地阐述了交换机中流表项结构、数据包的匹配过程以及timeout值对数据包匹配的影响，进而对流表更新的一般方法进行了总结;其次基于流表项的生存时间和数据流的特征密切相关的思想，对不同数据流类型的特征作了分析，并利用基于HMM的DPI算法对数据流进行分类;最后根据当前流表资源和控制器计算资源状况对不同类型数据流的timeout值进行动态调整，实现在控制器处理能力范围内，最大限度地利用流表资源。对真实的数据中心网络行为数据的模拟实验表明，本文提出的流表智能更新算法相比流表更新的一般方法，综合利用数据流类型信息和网络资源情况来更新流表，能够有效地提高流表的匹配率。尽管如此，本文还是存在一些不足，比如仅仅将数据流分为三大类，在接下来的研究中，可以进一步将数据流进行更细的划分，从而对流表项的更新实现更细粒度的控制。
作者：姜立立 曾国荪丁春玲 来源：计算机应用 2016年7期