软件定义网络探测技术综述

李俊强,陈 悦，韩 晗，王 晨，胡讯沛，张鑫刚，虞红芳

(1.电子科技大学 信息与通信工程学院， 成都 611731；2.国家计算机网络应急技术处理协调中心， 北京 100000)

软件定义网络(software defined networking，SDN)是针对传统网络的缺陷而提出的一种新型网络架构。2009年，美国MIT主办的《技术评论》网站将SDN技术评选为年度十大前沿技术之一[1]。自此，SDN技术开始被学术界和工业界广泛关注，得到了迅速发展。SDN最大的特点就是将控制平面和数据平面分离，让2个平面具有松耦合度，同时可以通过软件编程来对网络资源进行集中控制。

由于控制平面和数据平面的分离以及网络配置具有的定制化、精细化等特点，使得SDN具有跟传统网络不一样的时间特征和行为特征。传统网络下的探测技术并不能直接移植到SDN网络，需要开展面向SDN网络的新探测技术。本文主要介绍的是基于SDN网络的探测，这对深入理解SDN网络架构、提升SDN网络性能以及增强SDN安全性能有重要作用。

具体来讲，在SDN中，网络策略(如访问控制列表、防火墙规则)，网络应用(如负载均衡)，新型的防御机制(如移动目标防御)均可以通过SDN交换机上的流表来实现。对于攻击者而言，如果能探测出网络中节点之间的流表规则，就可以制定出有针对性的攻击策略，进而对网络实施进一步的攻击。同样，对于防御者来说，需要做的也是通过SDN探测来发现自身存在的安全隐患和漏洞，从而在遭受攻击之前提前进行防范，以此达到防御威胁的目的。

需要注意的是，与网络探测很相似的一个概念是网络测量，但它们之间有一定的差别。网络探测的原理是指通过探测主机主动发送探测包来探测出网络的内部信息，类似于网络测量中的主动测量。而且，在进行网络探测前，探测方是不知道网络内部情况的，把探测的网络当做一个“黑盒”来处理。因此，探测的环境是站在攻击者或者说“黑客”的角度来进行的，探测者无法直接对探测网络内部的设备进行操作。如果想获取这个网络的信息，只能根据网络的理论知识找到相应的漏洞从而进行探测。

目前针对SDN的探测才刚刚起步，相关的论文、资料还比较少。通过对现有的资料进行整理，从3个方面对现在的SDN探测技术进行综述，分别是：SDN网络类型探测、SDN流表规则探测、SDN流表容量探测。

1 SDN简介

1.1 SDN架构

SDN架构与传统网络架构最大的不同就是控制平面与转发平面分离，让其具有低耦合度。而在传统网络下，无论是2层交换设备交换机，还是3层交换设备路由器，都同时具有转发平面和控制平面。因此，可以说SDN架构是一种大的创新。

ONF(open networking foundation，开发网络基金会)从用户角度出发定义的SDN架构如图1所示。该SDN架构分为3层：应用层、控制层和基础设施层。除了这3个层次之外，还包括连接它们之间通信的接口：北向接口和南向接口。北向接口是指连接控制层与应用层之间的接口，南向接口是指连接控制层与基础设施层的接口。其中，北向和南向是相对于控制器而言的，这也能够说明SDN架构的核心就是控制器。值得一提的是，目前北向接口还没有统一的标准，而南向接口已经有了统一的标准协议OpenFlow。

基础设施层位于SDN架构的最底层，它是由不同的网络设备组成的。这里的网络设备主要是进行数据转发功能的设备，比如交换机或者路由器。但在SDN网络中，这些设备统称为SDN交换机。与传统网络不同的是，这些交换设备只有数据转发功能，并没有控制功能。基础设施层之上的是控制层，它可以提供整个网络的全局视图。由于处于整个架构的中间，它既要负责为应用层提供服务接口，也需要处理基础设施层的数据转发工作。应用层位于最上层，其包括各自不同功能的SDN应用，例如：安全服务、网络管理和策略实现。

ONF提出的SDN架构以及OpenFlow标准，目前得到了广泛的应用和支持，极大地促进了SDN的发展。

图1 基于OpenFlow的SDN架构

1.2 OpenFlow协议

OpenFlow的概念最早是由斯坦福大学的Nick McKeown教授等于2008年4月提出。OpenFlow将控制逻辑从网络设备盒子中分离出来，供研究者对其进行任意的编程从而实现其创新的网络拓扑、协议，而无需改动网络设备本身。OpenFlow的提出得到各界的广泛关注，目前成为SDN南向接口协议的主流标准之一。

2009年12月31日，OpenFlow v1.0正式发布。作为协议的第1个规范标准，OpenFlow v1.0中的很多思想都非常重要，是OpenFlow后续版本的重要基础。

OpenFlow v1.0中有3个核心组成部分：流表、安全通道和OpenFlow协议。其整体架构如图2所示。流表负责数据包的高速查询和转发，相当于传统网络中的转发表；安全通道提供一个安全的数据传输通道，方便OpenFlow交换机与控制器进行安全可靠的通信；OpenFlow协议是控制器与OpenFlow交换机进行通信的标准，它在安全通道进行传输，其定义的通信消息类型有3种：Asynchronous、Controller-to-switch、Symmetric。其中，Asynchronous消息由OpenFlow交换机发起，用来将网络事件或交换机状态变化更新到控制器；Controller-to-switch消息由控制器发起，用来管理或获取OpenFlow交换机的状态；Symmetric消息可由交换机或者控制器发起。基于这3种消息类型，控制器与交换机之间的通信便可以有序进行。

图2 OpenFlow的整体架构

OpenFlow协议作为一种重要的南向接口协议，它的作用就是让网络设备的数据转发功能与控制功能进行分离。为了实现这一目标，OpenFlow使用了流表这个结构。在传统网络设备中，数据链路层和网络层其各自的转发依据分别为MAC地址表和IP地址路由表。而在OpenFlow中，流表将传统网络中的所有转发表进行了整合。因此，其支持的协议字段更加丰富。

流表的结构如图3所示。流表由3部分组成：包头域、计数器、动作。包头域相当于传统网络中的数据包头，负责记录源、目的主机的IP地址、MAC地址等等信息。计数器用于统计匹配数据包个数，方便流量流量监管；动作的作用是告知匹配到数据包后应该进行的动作，分为必备动作和可选动作。必备动作是指所有OpenFlow交换机默认支持的，可选动作是指部分交换机支持的动作。必备动作有两种：转发和丢弃；可选动作有3种：转发、排队和修改域。

包头域计数器动作

图3 流表的结构

1.3 SDN探测的挑战

随着SDN的迅速发展，它的安全问题受到了越来越多的研究者关注。而SDN探测是研究SDN安全问题中不可或缺的一部分。一般来说，要想发动一次成功的攻击，先决条件就是探测出目标网络的相关信息，因此SDN探测的重要性是不言而喻的。

由于SDN中控制平面与数据平面分离的特性，使得SDN具有跟传统网络不一样的时间特征和行为特征。传统网络下的探测技术并不能直接移植到SDN网络，需要开展面向SDN网络的新探测技术。总的来说，在SDN环境下进行探测存在如下的许多挑战：

1) 如何提高探测的精度，例如在探测路径上可能存在多台交换机，如何确定探测信息的实际拥有者。

2) 如何降低探测的开销，使用较小的探测代价获得对多个匹配字段的较精确的探测结果。

3) 如何减少不稳定因素，如多次探测可能会改变流表内容等情况，因时延抖动、网络拥塞等偶然因素可能影响探测和分析结果。

2 SDN网络类型探测

在软件定义网络中，SDN网络类型探测是指探测所属网络是否为SDN网络。许多的研究者都提出了自己的探测方法。

2.1 SDN Scanner方法

Shin S等[2]首次提出了一种基于时间的指纹识别方法，以确定目标网络是否为SDN。由于在SDN中，控制平面与数据平面分离，因此当数据平面收到不知道如何处理的数据包时，数据平面通常会向控制平面进行相应的请求以获得相应的处理方法。利用这个关键属性便可以确定目的网络是否使用SDN/OpenFlow交换机，最终判断出网络类型。

为了证明这种攻击的可行性，笔者设计了一种名为SDN Scanner的SDN网络类型探测工具进行验证。该工具的总体探测思路是：通过构造不同的数据包，将其发送到网络当中，如果该数据包是交换机中没有出现的类型，交换机无法对其匹配，便会将其发送给控制器；反之，如果出现过，则交换机可以直接转发。假设前一个过程经过的时间为T1、后一个过程为T2，那么可以通过收集T1和T2的值，然后对T1和T2的值进行区分进而判断该网络是否为SDN网络。SDN Scanner的具体工作流程如图4所示，其探测步骤如下:

1) 首先，SDN Scanner构造具有不同头部的数据包。每一次将2个(或更多)特定的数据包发送到目标网络。

2) 其次，收集每个数据包的响应时间。SDN Scanner判定第1个数据包的响应时间T1，第2个数据包的响应时间为T2。

3) 然后，SDN Scanner将此次循环更新，重新构造具有不同头部的数据包，重复前两步的过程。

4) 最后，当循环的次数到达指定值时，退出扫描。

图4 SDN Scanner探测流程

2.2 指纹探测法

在Shin S等第1次提出SDN网络类型探测可行性的基础上，不久Bifulco R等[3]在真实的网络测试平台上实施了指纹攻击。通过利用2个特征的信息，即RTT值和交换分组的分组对分散度，可以非常精确地判断出SDN交换机是否与SDN控制器进行了交互，从而以极大的概率成功对SDN网络进行指纹攻击。

笔者使用的实验平台如图5所示。整个测试平台由3个NEC PF5240[4]OpenFlow交换机组成，它们通过100 Mbit/s数据通道连接到数据平面。传统的数据中心网络通常由3层交换机组成：接入层、汇聚层和核心层[5]。每个数据包经过数据中心时，通常由每一层中的至多1个交换机处理，即每个数据包在数据中心的网络中遍历(最多)3个跃点。因此，这3个交换机便可以大致模拟在实际数据中心数据包的处理过程。测试平台的交换机与Floodlight v0.9控制器连接，该控制器在具有6核Intel Xeon L5640 2.26 GHz CPU和24 GB RAM的计算机上运行。传统以太网交换机桥接OpenFlow交换机，然后和控制器进行连接。为了模拟控制信道上的实际网络负载，Bifulco R等将交换机的控制接口限制为100 Mbit/s。接着，通过在AMD Athlon双核处理器3800+机器上运行的防火墙，使用100 Mbit/s链路将SDN网络连接到Internet。最后，搭建了遍布全球的20个远程客户端，使得整个系统更具有真实性。

图5 实验平台结构

通过部署，Bifulco R等收集到了很多真实的SDN数据信息。结果表明：通过利用来自交换分组的分组对分散度的信息，对SDN网络的指纹攻击能极大的概率成功。例如，攻击者可以正确识别探测包是否在3个交换机上触发规则安装，准确度为98.54%。而且，这种指纹探测精度仅受到路径上需要配置的SDN交换机数量的轻微影响。因此，尽管搭建的环境只有3个OpenFlow交换机，结果仍具有代表性。

2.3 细粒度指纹探测法

Minjian Zhang等[6]提出了一种细粒度指纹探测方法，并没有采用先前的两种粗粒度的方案，具体地说，并不是简单地通过构造数据包然后研究网络中是否触发与控制器的交互来判断网络类型，而是通过确定SDN中流规则的匹配域来进行判断。首先根据SDN的基本特征，提出了获取匹配字段信息的方法，并在模拟和物理环境中进行了实验。

Minjian Zhang等假设在同一个SDN网络中有2个主机，一个主机作为发送者向另一个主机发送数据包。

1) 接收方接收到数据包的情况

① 交换机已经安装了相应的流规则，因此，报文成功匹配规则，交换机直接转发该报文。

② 交换机未找到匹配项，因此它会将此数据包发送给控制器。控制器分析该数据包并在交换机上安装相应的规则来处理此流表。

③ 交换机未找到相应的流规则，同样交换机会与控制器进行交互。控制器指示交换机转发数据包，而不是下发相应的流表。

在情况②和情况③中，数据包从发送方到接收方的时间明显长于情况①，因为该过程触发了控制器和交换机之间的交互。

① 如果流表中没有相应的规则，交换机将要求控制器决定处理该数据包。如果控制器未向交换机提供转发指令或流规则，则数据包将丢失。

② 交换机根据相应的规则丢弃数据包。

③ 由于网络拥塞或其他偶然原因，数据包丢失。

笔者在上述分析的基础上设计了指纹探测匹配字段的方案。假设发送者和接收者在同一网络(LAN)上并且能够正常地相互通信，忽略偶然情况(2-c)。对于给定的头字段，以特定的时间间隔发送具有相同头部值的多个数据包。

在接收方接收到所有数据包的情况下，通过分析发送到接收之间的时间长短来确定该报头字段是否是匹配字段。通过不同时间之间的差异可以区分出1)中①～③三种情况，便可以推断出交换机对同一数据流的报文采取了不同的动作。所以这个头部字段是匹配字段。

在所有数据包都无法到达接收方的情况下，便可以推断出交换机对给定字段中具有不同值的不同流采取了不同的操作。所以，该头部字段是匹配字段，因为在发送这组测试数据之前，这对主机是可以相互通信的。

2.4 方案对比

Shin S等[2]的研究暗示了指纹识别SDN网络的可行性。然而，他们的研究并不是基于真实的网络世界进行评估的，也没有提供任何量化指纹探测精确度的指标。就连作者自己也在论文当中提到：“我们提供了这种攻击的第一次可行性研究，并希望激发SDN安全领域的进一步研究。”

在Shin S等[2]的方案下，Bifulco R等在现实世界的测试平台上实施了这种探测，而且精度也达到了98%。但是，他们的方法需要在每个测试流程之前清除交换机中的流表，这在真正的实践中，攻击者往往很难做到。而且他们的工作也没有考虑到流规则失效、优先级不同的处理情况。所以他们的工作往往是一种验证。

盐胁迫会抑制植物的生长发育。当土壤含盐量过高时，会严重影响冰叶日中花的生理生化反应，造成其减产，甚至导致植株死亡。

Minjian Zhang等[6]的研究又更进了一步，实现了一种细粒度指纹攻击方法。通过对流表的匹配字段进行探测来确定某网络是否为SDN网络。但是其方法也有一定的局限性，作者仅仅使用了1个或2个OpenFlow交换机进行实验。但是真实的网络中拓扑结构并不是这么简单，因此真正应用到现实网络中还需要进一步的工作。

3 SDN流表规则探测

SDN网络中，流规则是最关键的部分，它确保网络单元在任何网络入口以适当细粒度控制流量和部署策略，网络策略的实现细节同样会在流规则中体现。因此，若能探测并推断网络中节点间的流规则，就可制定出有针对性的攻击策略。

3.1 INSPIRE方法

针对流表规则探测，Po-Ching Lin等[7]提出一种“INSPIRE”(INferring SDN by probIng and rule extraction)方法来发现SDN的流规则，这种方法的设计思路来源于防火墙规则探测[8-9]。

INSPIRE方法包括4个步骤:

1) 时延值的获取。获取方式是通过探测主机主动发送一个探测包给目的主机。其中，探测包的源IP地址是虚假的，但是与目的IP地址共存于同一个子网中。同时探测包的有效载荷中需要包含一个发送的时间戳，这样时间差就等于接收的时间减去有效载荷中的发送时间。而流表的下发方式有两种：主动与被动两种模式。主动式的数据包的处理时间将会比被动式的更短，因为在主动模式下控制器已经提前下发了对应流表。通过这个时间差可以帮助推断一条流规则是否存储在交换机流表中。

2) 构建探测包。探测包的构造方法来源于传统网络中防火墙规则探测的构造数据包的方法，作用是通过构造少量的探测包就能达到较高的探测精度。文中，作者选择使用线扫描法。这种方法能在一个大的区块中快速发现规则，将会产生比分裂合并法更多的探测包，减少了数据集中的因网络拥塞而产生的异常值。

3) 聚类和分类。在探测过程完成后，INSPIRE将会对探测包进行分类。对于捕获到的报文，分为主动式和被动式两类，基于接收时间和发送时间的差值即时延值来进行K-Means聚类。如果该探测路径上有n个交换机，后者将会被划分为n个子类。每个交换机都会触发Packet-in，所以总时延取决于多少个交换机会与控制机进行交互。

4) 流规则的推测。INSPIRE使用Apriori算法来推断出流规则。该算法是一种挖掘关联规则的频繁项集算法，它的主要任务就是设法发现事物之间的内在联系。该算法统计头部字段的出现频率的同时搜寻高频度出现的头部字段的组合来当做流规则的一部分。该算法在字段组合的出现概率低于预先设定的值或者没有更多的字段可以组合时，就会退出。

3.2 SDNMap方法

对于OpenFlow流表具体字段的探测上，Stefan Achleitner等[10]提出了一种方法，并基于此方法设计了一个开源的工具SDNMap。下面介绍其中部分字段的探测方法。

3.2.1 MAC地址的探测

SDNMap会先产生一个探测包，使用TCP报文或者ICMP报文，其中源MAC地址头部是虚假的。

在目的主机接收到探测报文后，会先寻找源IP地址对应的MAC地址，如果查询到，则在其本地缓存中生成带有MAC目标地址的探测答复消息，并发送回源主机。反之，便会发送一个ARP请求报文来解析收到的源IP地址。如果收到回复，目的主机会更新其本地ARP缓存中的条目，并将探测应答包发送回源主机。

在收到探测应答或ARP请求数据包后，扫描器就可以推测出MAC源地址字段并未用于将探测数据包发送到目标主机。如几次没收到，则重复该过程。如多次没有收到，则推出源MAC地址被用作将数据包传送到目标主机的匹配标准。

如图6中的消息3、4和5所示，首先向目标主机发送应答消息，该消息将其探测主机的IP地址的高速缓存条目更新为虚构的MAC地址。之后，发送一个正确的探测请求数据包到目的地。到达后，目的主机会查找与接收到的IP源地址对应的MAC地址。目的主机会将探测回复消息发送给请求者。如果在SDNMap主机处接收到探测回复数据包，得出结论：在传输规则匹配过程中，目的MAC地址未被用作传送数据包的标准。如在定义的超时时限后没有收到回复数据包，SDNMap会断定流规则使用了正确的MAC目的地址标准来传输数据包。

3.2.2 IP地址的探测

IP地址的探测过程如图7所示。首先探测主机会发送一个探测报文，其中IP源地址是虚假的。收到探测报文后，目的主机无法查找到该IP地址对应的MAC地址，于是发送一个ARP请求报文给探测主机。若几次未收到ARP请求数据包，则重复该过程。若仍没有收到，则得出结论：流规则将匹配特定IP源地址的数据包，具有虚假IP源地址的数据包将不会传送到目的地主机。

图6 探测MAC地址的步骤

图7 探测IP地址的步骤

在接收到上述过程中的ARP请求报文后，SDNMap将发送一个ARP应答消息，告诉目的主机该虚假IP地址对应的MAC地址。这时会触发目的主机生成一个回复数据包，该数据包信息包括探测主机虚假的IP地址和目的主机的IP地址，这样就能够出探测出目的主机的IP地址。

如果接收到1个探测回复数据包，则它会得出结论：IP目的地址不被用作流规则匹配域的一部分。如果在多次尝试后没有收到回复数据包，SDNMap会得出结论，匹配过程需要正确的IP目的地址，控制器会依据该字段执行“转发” “丢弃”还是其他动作。

3.2.3 协议和端口的探测

SDNMap根据不同协议的特点来对各种协议类型的报文是否会被转发进行判别。确定ARP报文是否会被转发，通过发送一个ARP请求的数据包来判断。确定ICMP报文是否会被转发，通过发送一个ICMP请求报文，看是否收到ICMP应答报文来进行判断。探测TCP，UDP数据包和其端口的做法是：探测方发送一个UDP数据包至目的主机的指定端口，如果随后收到ICMP端口不可达的错误消息，就表明该数据包是UDP报文但是该端口是关闭的；否则，表明该端口是开放的。

3.3 方案对比

INSPIRE方法的缺点是探测的信息不够全面，能够探测出的流表字段较少。而且，局限性较大，因为它是假定探测主机和目的主机的权限都能获取到。这在实际探测或者攻击环境中很难做到。该方案的优点是推理的准确性很高，原作者经过仿真测试，结果表明准确率高达98.41%。

SDNMap方法的优点是可以推测出流规则具体的字段，比如MAC地址、IP地址等，而且相比于INSPIRE方法，它并不需要同时获取探测主机和目的主机的权限，只需要能够获取到探测主机权限即可，而且精度也非常高。但是其也存在一定的缺点：首先，SDNMap探测开销一般较大，是通过暴力方式构造探测包，这样导致整个工具包使用效率较低；其次，SDNMap探测的信息不够全面和精细，探测流表的字段数也较少；最后，该方法无法保证探测包响应能够顺利到达源主机，具有一定的局限性。

4 流表容量探测

SDN/OpenFlow交换机的流表容量是一个容易被忽略的网络参数，然而流表容量在SDN网络安全问题中也是重要的一环。流表容量问题已在许多以前的工作中提出过[11-13],他们都指出了交换机流表内存的限制以及潜在的可扩展性和安全性问题。

由于硬件和软件的限制，SDN网络的OpenFlow交换机一般都具有流表容量的限制。具体而言，大多数商用SDN/OpenFlow交换机的流表容量有限，从数百到数千[14]。当流表中的流表项数目达到上限，交换机和控制器之间就会进行交互，对流表进行相应操作来维持SDN网络交换机的正常工作，而这个事件也可以被用户捕捉到，通过观察该事件，用户可以推断交换机的流表容量和流表使用情况。J.Leng等[15]提出了一种针对SDN/OpenFlow网络的推理攻击模型，这是SDN领域的首次针对流表容量的探测。

4.1 探测模型

在传统网络中，交换机和路由器是自治的，这意味着可以在本地维护其路由表而无需与外部设备交互。但由于SDN/OpenFlow的分离性质，维护交换机流表需要交换机和控制器之间的频繁交互，使攻击者可以利用感知的性能变化来推断SDN网络的内部状态。

SDN交换机上的流表匹配过程如下：① 首先查找流表以搜索与数据包匹配的流表项，若存在直接执行该流表项的动作；② 若不存在相匹配的流表项，则与控制器交互，下发新流表；③ 在插入新流表之前，首先检查流表状态是否有足够的空间。当流表已满，就需要控制器和交换机之间的额外交互来移除某些现有的流条目以为新生成的流表项腾出空间。这3种情况中，当流表中存在匹配时，处理时间最短; 当流表中没有匹配且流表未满时，由于交互下发新流表规则，处理时间会更长; 当流表中没有匹配且流表满时，处理时间最长，因为必须额外再执行流表替换操作。因此，作为直接受处理时间影响的网络参数，探测包的RTT可以用作流表状态和流表项状态的指示符。

首先需要确定RTT的阈值，如图8所示。图中的2个子图表示2个协作线程，x轴表示数据包，y轴表示每个探测包的RTT。首先，在上层线程中，生成一个包含特定源目IP，源目MAC的数据包，称之为Pkt1。将Pkt1发送到目标OpenFlow交换机并将相应的RTT记录为T2。由于Pkt1是一个新的数据包，OpenFlow交换机中没有相应的流表项。在时间跨度TS1之后，再次将Pkt1发送到目标OpenFlow交换机并将相应的RTT记录为T1。如果正确选择TS1(流表没有因超时而被删除)，则刚下发的与Pkt1匹配的流表项应该仍然存在于OpenFlow交换机中。接着，在下层线程中，不断地生成Pkt2、Pkt3…Pktn数据包，每个数据包都有不同的源目IP、MAC组合，并以TS2的时间间隔发送到目标OpenFlow交换机。刚开始OpenFlow交换机中流表还有存储空间，因此记录的RTT将与T2或T1大致相同。继续生成和发送数据包，直到观察到RTT的突然增加，这表明流表已满。然后在上线程中，再次发送Pkt1并将RTT记录为T3。为了提高精度，可以重复这个过程，并使用T1、T2和T3的平均值作为最终结果。

图8 不同流表状态的RTT测量

得到RTT的阈值后，通过向交换机发送探测数据包，就可以依据T1、T2和T3这3个检测标志与得到的RTT进行比较，进而分析流表状态：当测量的RTT在T1附近时，可以推断流表中有相应的流表项; 当测量的RTT在T2左右时，可以推断流表中没有相应的流表项，流表不满; 当测量的RTT在T3附近时，可以推断出流表中没有相应的流条目，流表已满。

4.2 推测算法

推断流表容量的关键就在于流表变满时进行的流表替换操作，流表替换算法决定了SDN网络的内部状态转换，因此它是推理模型的重要组成部分。流表类似操作系统和Web代理服务器中的“缓存”，所以作者使用的流表替换算法是一些常见的缓存替代算法的变体，比如FIFO[16]，LRU[17]。

4.2.1 FIFO推测算法

FIFO算法的推测过程如下：通过生成并发送大量的探测数据包，每个探测包源目IP、MAC都不同，新插入的匹配流表项将其他用户的流表项推出流表。结合记录的插入流表项数目，就可以推断流表容量和流表使用情况。流表状态转换的过程如图9所示。

图9 FIFO推断原则

图9中：A表示流表在实验开始之前，OpenFlow交换机中其他用户的流表项数目；B表示开始发送生成的数据包，新的流表项被插入流表；灰色矩形表示新插入的流表项，新插入的流表项不断将其他用户的流表项推到FIFO队列的前面，在实验中，应当记录生成的数据包，包括它们的属性和序列号；C表示流表已经变满，此时，新下发的流表和其他用户的流表项相加，刚好填满整个流表；D表示检测到插入的1个流表项已被删除，这意味着现在流表中都是刚刚下发的流表项，没有来自其他用户的任何流表项。在时间点C和D分别记录发送的探测包数量：m和n，则流表容量C=n。A时刻即刚开始流表中的流表项数目为n-m，则流表使用率为(n-m)/n。

推测算法的主要误差来自其他用户在插入过程中插入的流表项。作者的假设是：流表项插入速度足够快，以便在实验期间，新插入的流表项全部来自作者的操作。但这只是理想模型，不是事实。忽略其他用户插入的可能的流表项将会使作者推测的流表容量略小于实际值。

4.2.2 LRU推测算法

LRU算法的实验原理与FIFO算法的实验原理有一些共同点，因为在这两种情况下都可以使用某些操作保持流表项保持在缓存队列的后面。但是，流表项维护过程存在差异。

FIFO算法的性质确保流表项的位置仅取决于插入它们的时间。与后面插入的流条目相比，前面插入的流条目肯定更接近缓存队列的前端。但是在LRU算法中，流表项的位置不仅取决于插入它们的时间，而且还取决于最后访问它们的时间。为了使流表项保持在缓存队列的后面，需要不断地访问先前插入的流表项。在维护过程中，每次插入一个新的流条目时，都需要访问所有先前插入的流条目一次，以将它们“提升”到缓存队列的后面。作者将这种过程称之为“滚动”维护过程。

LRU算法的可行性和误差分析与FIFO算法相似。由于忽略了其他用户在实验过程中插入的流项，所以推断出的流表使用和推断出的流表容量都略小于实际值。

5 结束语

本文通过对SDN网络类型探测、SDN流表规则探测、SDN流表容量探测进行详细的技术综述，来对目前的SDN探测技术做一个整理。面向SDN网络的探测技术才刚刚起步，之前的研究做了有益的探索，但仍然存在部分局限性，如何打破上述局限性，高效、准确、精细地探测SDN网络是未来的一个重要的研究方向。