1.2 学术界前沿研究方向

1.2.1 SDN研究方向

学术界对于SDN的研究分类大都与其体系结构相对应，如参考文献[11, 12]主要从数据平面、控制平面和应用场景3个方面进行分析。在基础设施层，由于SDN将复杂的控制平面剥离，因此该层上的研究方向较为有限，主要包括交换机处理流程的设计与实现、转发规则对交换机流表的高效利用，以及交换机流表正确性的验证等。在控制层，研究工作主要包括单点控制器设计、集群控制器架构、控制器接口和模型设计、控制器部署位置、控制器的分布式系统特性、控制器安全等。在应用层，研究方向可以分为网络安全、服务质量、负载均衡、流量工程等，以及在企业网、校园网、数据中心、无线网络、广域网等不同场景下的应用。

1．数据平面

作为基础设施层的核心元素——交换机，其主要功能是匹配和转发网包。基于硬件的实现方式，转发性能高、功耗低，但可扩展性差；而基于网络处理器或通用处理器的实现方式，转发性能较硬件实现方式低一两个数量级，但是具备非常强的灵活性。因此，交换机处理流程的设计和实现，主要是在上述两者之间进行折中。同时，基于OpenFlow的SDN交换机流表匹配宽度远超传统交换机，在保证成本功耗的前提下，同样容量的存储芯片可支持的流表数目大幅下降，如何提高交换机流表利用率就成为转发规则相关研究的另一问题。

（1）交换机设计

由于新的网络应用和网络协议不断出现，SDN交换机需要支持更多协议格式的网包解析。以支持OpenFlow的SDN交换机为例，其所需解析的网包包头域的数量已经由1.0版的12个增加到1.4版的41个，而且这个过程远未停止。因此，学术界认为应当将交换机的包头解析功能设计成可配置式的，而不依赖于特定的网络协议。同时，当前不少SDN应用以流水线的方式解析网包[13]，未来SDN交换机需要支持在多表上串行或并行查询的灵活配置。除了网包解析过程之外，未来SDN交换机对网包处理的操作也要考虑扩展性，除了经典的转发、丢弃、限速、打标等操作，还需要支持对网包包头任意域的修改，以及匹配过程中变量修改的相关操作。来自OpenFlow研究团队的P4[14]和来自华为公司的POF[15]是该方向的突出成果。两者几乎在同一时间提出，所不同的是P4面向的是基于芯片的实现方式，而POF是基于网络处理器的方案。通过对匹配域、流水查找、网包操作等交换机处理网包的主要任务进行进一步拆分，并以可灵活配置、拼接的方式实现，未来SDN交换机相比OpenFlow交换机能够更快地实现新的应用需求。

（2）流表优化

由于OpenFlow交换机流表数目的限制，SDN控制程序难以在大规模的网络环境中静态部署全部的表项。如果采用动态部署的方式，则流表与交换机之间的通信性能直接受到交换机控制平面CPU能力的限制：一方面，带宽指标难以达到数据平面的量级，另一方面，延时也会受到控制器性能和控制网络状态的影响。DevoFlow[16]的工作从数据中心流量特性的角度出发，针对性地对流量进行优化。在实际数据中心网络中，导致网络拥塞的流量可能只占10%，而这些流量占总流量大小的90%，被称为大象流（Elephant Flow），其余流量被称为老鼠流（Mice Flow）。DevoFlow通过定期采样统计流量，检测大象流并对其进行标记，之后集中对这些流量采用动态负载均衡、多路径等流量工程技术进行优化。

此外，在SDN架构中，由于控制平面和数据平面在物理上进行了分离，控制平面向数据平面的多个交换机上部署规则时，会存在延时和不一致的问题：部分交换机上已部署了新的规则，而其他交换机上仍然保留着原有的规则。Reitblatt等人在“Abstractions for Network Update”[17]一文中提出采用分布式系统设计中经典的两阶段提交方式来更新规则，并通过给数据包打标签的方式来标识新旧规则的版本。具体来说，在第一阶段，控制器向拟更新的交换机发送消息，以确定完成对应旧规则的处理，并对处理完成的交换机进行规则的更新；在第二阶段，等待所有更新的交换机返回更新成功的消息，否则取消该更新操作。Katta则在“Incremental Consistent Updates”[18]一文中将上述过程拆分为多轮进行，每一轮都采用两阶段提交的方式进行更新。

2．控制平面

（1）控制器设计实现

控制层是整个SDN架构的核心。控制器也可称为网络操作系统，是SDN控制层研究的一个主要内容。NOX[19]是首个OpenFlow控制器，它在OpenFlow协议的基础上进行了封装，提供了基于网络事件触发的编程模型，以及应用模块动态加载与组合的运行机制，并支持多种开发语言。NOX给出了OpenFlow控制器的原型，后续的单机控制器均参考了NOX的实现。MOX-MT[20]针对NOX单线程处理方式造成的处理性能过低，改进了网络收发模块，并对处理中的冗余环节进行了优化，实现了多线程的事件处理。ONIX[21]首次提出了分布式SDN控制器，并系统地对SDN的编程模型及API进行了阐述。ONIX控制器中维护了一个网络信息库（Network Information Base, NIB），该库中保存了有关节点、链路、拓扑等信息的全局网络视图，并综合采用分布式散列表（Distributed Hash Table, DHT）和事务型数据库等多种手段来更新视图；基于该视图，ONIX抽象出多类API，用于管理网络状态。Kandoo[22]是一个层次化的分布式SDN控制器框架，它根据网络状态变更事件产生的频率，设计了本地控制器和根控制器两种类型，分别用于处理高频率、局部的网络状态变更事件和低频率、全局的网络状态变更事件。ONOS[23]是来源于学术界的最新网络操作系统，以AT&T公司的中心局的数据中心化重构（Central Office Re-architectured as Data Center, CORD）项目为支撑进行孵化。该网络操作系统提供高可扩展性、高可靠性及高稳定性，实现了运营商级SDN控制器平台的特征。

（2）编程模型

Frenetic[24]在NOX的基础上实现了声明性的网络状态查询框架。它向上以类似SQL格式的语句定义设备状态查询需求，向下将高层的查询需求转换成OpenFlow控制指令，下放到OpenFlow交换机上。T. L. Hinrich提出了基于网流级别的网络策略管理语言FML[25]。由于访问控制、地址转换、策略路由等不同应用场景的策略描述不尽相同，而不同厂商设备在策略配置模式上的差异更加恶化了上述情况，因此，FML被设计成以一种统一、细粒度的策略描述来取代当前不同的策略定义方式。为了解决FML只能处理静态网络策略的局限，Procera[26]基于函数响应式编程（Functional Reactive Programming, FRP）实现了动态网络策略的描述方式，该方式能够方便、直观地表述和实现网络策略中与时间变化相关的特性，因而能够较好地适应诸如SDN等动态变化的网络环境。

3．应用场景

SDN由于其高度灵活的可编程性，在网络领域的大量应用场景中得以部署测试。校园网环境是OpenFlow/SDN最早提出的应用场景，包括Ethane的访问控制、Resonance的网络准入[27]等。在数据中心，PSwitch[28]/SIMPLE[29]侧重利用SDN技术解决中间设备的部署问题，VMware NSX团队则完整展示了其基于SDN的网络虚拟化平台方案[30]，包括数据平面和控制平面的设计。在数据中心互联方面，来自于Google公司的B4和来自于Microsoft公司的SDWAN[31]则是代表工作。控制器通过SDN获取全局信息，并采用ECMP 技术来保证流量动态平衡，使得链路的利用率达到60%～100%。在无线领域，OpenRadio[32]借鉴了SDN数据平面和控制平面分离的思想，将无线网络设计分为处理平面和决策平面，并引入了针对无线网络设备的可编程接口。BeHop[33]利用SDN技术解决密集WiFi覆盖的问题，其部署的原型系统承载了真实用户的流量，实现了终端在多种网络之间的灵活切换，并为不同网络节点设置白黑名单进行接入控制。

1.2.2 NFV研究方向

在NFV方面，除了ETSI的NFV技术白皮书外，目前还缺乏相关综述性质的学术文章，但是可以网络中间设备为主题进行分类综述：网络中间设备的机制实现及其策略管理。

网络中间设备机制实现的相关研究可以分为系统架构和管理接口两个主要研究方向。前者主要包括中间设备逻辑功能模块的设计，以及如何充分利用硬件平台的处理资源构建模块间的处理流程；后者主要包括如何设计中间设备的互操作接口，将设备提供的功能开放出去，以实现中间设备在其他应用系统中的集成。

1．中间设备系统架构

由于逻辑功能处理的复杂性，早期中间设备的实现方式大都基于特定的硬件平台，对造成系统处理瓶颈的模块进行加速。随着x86通用处理平台性能的飞速提升，以及NFV需求的日益强烈，近年来的研究工作集中于如何在通用或开放标准处理平台上对中间设备的系统架构进行重构，引入模块化以消除功能冗余。CoMB[34]和OpenGate[35]是这方面工作的代表。

（1）CoMB

该工作主要解决如何在通用处理平台上构建独立形式的中间设备。首先， CoMB将中间设备的逻辑功能从物理硬件中解耦出来，并且对多种类型中间设备的逻辑功能进行归纳整理，抽象出共性的功能模块，消除由于功能堆叠造成的处理冗余。其次，CoMB将上述功能模块重新映射到通用处理平台上，并在映射时考虑利用多种方式的并行实现，对每个功能模块的处理进行加速。最后，CoMB还引入了逻辑上集中的控制器来管理所有的中间设备，以实现全网范围内中间设备资源利用率的提升及处理流量在时间和空间上的负载均衡。

CoMB的系统架构和软件架构如图1-4所示。CoMB将中间设备的功能模块分为网包捕获、连接维护和应用处理3层。在网包捕获层，CoMB利用网卡中的网包分类功能，将进入系统的流量根据其后续操作的不同进行分类，并分发到对应不同处理核心的硬件队列中。在连接维护层，CoMB在完成网包必要的完整性校验后将其重组成网流，并对网流的应用层协议进行解析，根据流表将网流导入到不同的检测引擎中。在应用处理层，CoMB分别实现了基于Click平台插件和基于独立进程的两类检测引擎，并且在多核平台上实现了并行和流水两种处理方式。

（2）OpenGate

该工作主要解决如何在开放标准硬件平台上利用开放源码软件构建集群式中间设备的问题。首先，OpenGate提出了基于开放标准的先进通信计算架构（Advanced Telecom Computing Architecture, ATCA）硬件平台，并借鉴OpenFlow开放网络架构的设计思想，利用开源网络软件构建集群式中间设备的设计。其次，OpenGate根据系统的功能需求，将集群式中间设备的模块划分为3类：网络处理、服务处理和控制处理，分别利用高速多核网络处理器、分布式高性能服务器集群和系统处理逻辑集中控制，重点解决中间设备的前端、后端和整体管理3个方面的优化。最后， OpenGate针对网络安全的应用场景，实现了同时支持20Gb/s状态检测和8Gb/s深度检测的高性能安全网关。

OpenGate的系统架构和软件架构如图1-5所示。OpenGate的所有功能模块通过内部网络接口，同时接入到系统的数据平面和控制平面网络上。其中，网络处理模块作为整个集群的前端，还提供外部网络接口处理系统的输入/输出。数据平面和控制平面网络分别为多个功能模块提供无阻塞的高速和低速数据交换通道。在网络处理模块，OpenGate完成网络L2、L3的处理以及基于网包包头的状态检测，并利用独立的快速通道和硬件支持的协处理器，分别保证前端处理的高性能和后端处理的加速优化。在服务处理模块，OpenGate完成基于网包载荷的深度检测，并在用户态利用多核处理器对检测引擎进行多线程加速优化。在控制处理模块，OpenGate负责整个集群系统的配置管理与模块状态监控。

（3）其他相关工作

除了上述两个代表工作之外，RouteBricks[36]是早期在通用处理平台上实现高性能网络设备的优秀成果。虽然该工作的目标是实现每秒Tb计的处理性能的基于网包粒度的无状态转发方案，与中间设备基于网流粒度的有状态转发有所不同，但是该方案中的不少手段已在后续的多种网络设备实现中得到广泛应用。xOMB[37]与CoMB的工作最为相近，它侧重于解决独立形式中间设备的可编程性与可扩展性，较少涉及全网范围内多个中间设备的协同与优化。LiveSec[38]和FlowStream[39]提出了一种基于OpenFlow交换机与硬件设备或虚拟机相结合的中间设备实现方案，虽然该方案能够保证中间设备检测能力的横向扩展以及多种检测功能的灵活组合，但是由于不少检测功能需要根据网流中部分网包的载荷进行应用级别的协议解析或网流合并，因此该方案受OpenFlow匹配模型的限制，有其特定的局限性。FRESCO[40]提出了一种基于OpenFlow控制器应用的网络安全中间设备实现方案与编程平台，该方案将检测功能通过编写成运行在OpenFlow控制器上的应用来实现，虽然能利用OpenFlow完善的网包包头匹配能力和控制器丰富的编程接口，从而实现安全检测功能的快速开发，但它仍然面临与FlowStream方案相同的局限性。

2．中间设备管理接口

随着SDN和NFV应用日益普遍，早期中间设备的硬件盒子静态连接的部署方式越来越难以适应网络拓扑的动态改变。中间设备提供的功能必须能够通过编程接口开放出去，供其他子系统调用或集成。根据是否对传统中间设备进行更改，中间设备管理接口的相关研究工作可以分为基于传统中间设备的管理集成和基于开放功能中间设备的管理集成两类，而PLayer[28]和SDMBN[41]分别是这两类工作的代表。

（1）PLayer

该工作为解决数据中心中间设备部署所面临的挑战，提出了引入策略感知的交换层作为中间设备的接入方案。该交换层由多个策略感知的交换机PSwitch组成，多个PSwitch可以根据运维人员制定的策略生成多种所需的逻辑拓扑连接。PLayer遵循了如下两个设计原则。

1）将连通性与策略相分离：不同中间设备检测功能的组合顺序由策略显式给定，而不是由其在转发路径上的位置顺序决定。

2）将中间设备移出物理网络路径：与终端节点接入方式相同，中间设备同样在数据中心网络边界接入，并利用流量牵引将需要检测的流量按照策略指定的顺序导引到对应的中间设备上。

在控制平面，PLayer通过定义在网包包头域上的策略，制定不同流量在数据中心中流经中间设备的顺序，并自动将上述策略根据物理网络拓扑转换成PSwitch上的转发规则；在数据平面，PSwitch接收并部署来自控制器转换后的转发规则，能够在不对中间设备进行更改的前提下，完成基于策略的转发功能。

从上述PLayer的工作原理可以看出，该工作的设计思想与OpenFlow一脉相承于4D[2]；并且在如图1-6所示的具体实现上，两者也有非常多的相似之处。OpenFlow相比PLayer明确提出了交换机控制平面与数据平面相分离的设计原则，定义了交换机逻辑功能的规格说明，并对控制器与交换机之间的命令格式进行了协议化。因此，基于PLayer的中间设备管理集成方案有着与基于OpenFlow的方案相同或相似的局限性。此外，针对数据中心中间设备部署的特定场景，PLayer还有如下不完善的地方。

1）不支持某条特定的检测流量多次流经同一个中间设备。

2）未考虑对中间设备多租用的支持。

3）中间设备仍采用静态部署方式，流量牵引会导致额外的带宽和延时开销。

4）以网流为粒度进行策略管理仍然较为复杂。

（2）SDMBN

该工作针对基于传统中间设备进行管理集成所面临的局限，借鉴交换设备开放编程接口的思想，提出了开放中间设备功能的解决思路。首先，SDMBN对中间设备状态根据其在运行过程中所扮演的角色进行分类，表1-1展示了4种状态类型的最终分类结果。以入侵防御系统为例，策略规则、连接表项、功能参数和统计信息分别是操作状态、支持状态、调优状态及监控状态的典型实例。其次，SDMBN对中间设备状态的访问设计了相应的编程接口，与大部分网络管理协议类似，控制器向中间设备的访问接口包括状态的增、删、查，中间设备向控制器的访问接口为状态的变更通知。SDMBN的设计较大程度地提升了中间设备的可编程性，其不仅开放了传统意义上的功能配置和统计信息编程接口，而且还抽象出对中间设备连接表等运行时关键信息的访问接口，使得该框架能够适应检测能力动态调整和检测功能在线热迁移等复杂应用场景，为更高级别的功能聚合提供了支持。

（3）其他相关工作

除了上述两个代表工作之外，SIMPLE在PLayer工作的基础上，采用OpenFlow技术手段，重点解决在有设备处理资源限制的条件下，数据中心中间设备的部署问题。此外，该工作还考虑到中间设备可能要对网包内容进行更改、同一类型多个中间设备之间负载均衡，以及特定检测流量可能多次进入某个中间设备等其他因素，针对性地引入了基于相似性度量的网流关联、基于在线和离线的整数线性规划，以及基于隧道标记的流量牵引对上述3个问题进行解决。Stratos[42]则将解决上述问题的手段扩展到基于虚拟机形式的中间设备上，根据网络拓扑和实时流量大小动态

调整虚拟化中间设备的部署位置，从而达到更好的负载均衡和更高的资源利用率。OpenNF[43]是SDMBN工作的延续，其扩展了后者提出的编程接口，以简化中间设备管理集成的复杂度，并且通过实际原型系统的搭建和评测验证了设计的合理性和有效性。DPIaaS[44]在上述两类工作的基础上更进一步，利用后者提供的控制手段，提出了将所有中间设备的深度检测模块提取出来，并抽象成服务，供多个中间设备共享，以在全网范围内提升中间设备整体的处理效率。

3．中间设备策略分析

本书中的“中间设备策略”特指面向网包包头的策略类型，它是由一组规则组成的集合。其中，每条规则指定了网包包头域上的匹配条件，以及对应的后续操作。这种类型的规则集合有别于面向网包载荷的规则集合，后者在处理逻辑上可以看作前者规则操作域的取值。例如，一条定义在网包源地址、目的地址、源端口、目的端口和传输层协议类型域上的经典五元组规则：＜0.0.0.0/0, 166.111.137.20/32, 0-65535, 80-80, 0x06/0xff, HTTP_SIG＞，指明了所有去往目的主机166.111.137.20的80端口的流量的后续操作是检测HTTP攻击特征的规则集。

中间设备策略处理的相关研究可以分为策略分析和策略分配两个主要研究方向。策略分析主要包括如何优化中间设备策略的表示，以及如何对已部署的单个或多个中间设备上的策略冲突进行检测；策略分配主要包括如何将在全局网络拓扑上定义的策略分配到网络中多个节点上进行分布式处理。

由于防火墙设备在传统网络中部署广泛，因此中间设备策略分析领域的研究工作大多集中于防火墙策略。防火墙策略的优化表示与冲突检测分别定位于策略部署前后的分析工作。这两类工作大都将防火墙策略用具备不同特性的树状结构表示，并在此基础上完成相应的后续分析处理。防火墙决策图（Firewall Decision Diagram, FDD）[45]和PolicyTree[46]分别是这两类工作的代表。

（1）FDD

Mohamed提出防火墙策略表示需要满足3个特性：一致性、完整性和紧密性，并设计了FDD对人工定义的原始防火墙策略进行优化，以满足上述3个特性要求。一致性是指每个网包不会匹配策略中两条不同操作的规则；完整性是指每个网包至少匹配策略中的一条规则；紧密性是指策略中不存在冗余的规则。FDD是一个有向无环的树状结构，除了同时满足树状数据结构和有向无环图的基本属性外，还具备如下特性。

1）每层内部节点对应策略的某个特定域，每个叶子节点对应策略操作域的某个特定取值。

2）某个特定从根节点到叶子节点的路径上不会出现对应域相同的多个节点。

3）内部节点的每条出边对应于该节点对应域上的多个特定整数区间，每个内部节点的所有出边对应的整数区间集合两两交集为空，所有并集为该节点对应域上的全集。

图1-7所示展示了一个二维FDD示例；示例中两个维度的取值全集均为[0, 9]，根节点对应第一维F0，第二层内部节点均对应第二维F1。

在FDD数据结构的基础上，通过对取值相同的叶子节点进行选择性的合并，可以达到防火墙策略的上述3个设计要求。此外，利用FDD数据结构，还可以对比多个防火墙策略之间的差异，从而找出策略定义中不明确的部分并对其进行修正。对防火墙策略的查询及部分冲突检测的功能也可以基于该结构来实现。

（2）PolicyTree

Ehab对独立式和分布式防火墙的策略冲突问题进行了系统性的研究，并提出了基于PolicyTree结构在策略部署后或增删规则时，对已有的策略冲突或可能产生的策略冲突进行检测的算法。首先，该工作将防火墙规则之间的关系划分为：完全分离、精确匹配、包含匹配、部分分离和相互关联5种类型。其次，基于上述规则关系、优先级关系和操作域取值的不同，该工作分别介绍了独立式防火墙的5种策略冲突类型（遮蔽异常、相关异常、泛化异常、冗余异常和无关异常）与分布式防火墙的4种策略冲突类型（遮蔽异常、欺骗异常、冗余异常和相关异常）。最后，该工作将防火墙策略表示成PolicyTree，并用代码逻辑描述和实现了策略冲突检测算法。表1-2和表1-3分别展示了防火墙规则关系、独立式防火墙策略冲突的分类和形式化描述。

从多维正交空间的角度来看，策略分析的主要工作侧重于结合规则操作域的取值，对规则网包包头域所代表的多维正交空间之间的集合关系进行分析。FDD和PolicyTree的树状结构本身就反映了策略对多维正交空间某种特定的分割方式。通过每层内部节点对多维正交空间进行无交叠的分割，树状结构消除了因空间交叠导致的规则之间优先级上的顺序依赖，减少了叶子节点所代表的子空间之间关系分析的复杂度。然而，这些数据结构在每层内部节点上仅对正交空间在某个特定维度上进行切分，不利于在策略变更频繁的应用场景中使用；而且这些数据结构没有直接提供其所代表的多维正交空间上的集合关系操作，一些工作直接用代码逻辑来实现策略分析，对上述分析手段的易用性和普适性造成了影响。

4．中间设备策略分配

在传统网络中，中间设备通常以独立硬件盒子的形式静态部署在网络边界上。中间设备策略的更新频率往往较低，而且其目标主要是负责对内部网络进行防护。同时，中间设备类型众多，而且相同类型但不同厂家的中间设备的功能差异性较大，难以实现集中、统一的管理。因此，相关研究工作主要集中于上一小节所描述的单台设备上的策略优化表示以及单台或多台设备之间的策略冲突检测，几乎没有涉及中间设备的策略分配问题。随着SDN技术的兴起，OpenFlow规范了交换设备的转发模型，全网范围内交换设备的策略可以根据应用场景的需要，由逻辑上集中的控制器进行灵活的分配。根据功能需求的不同，交换设备的策略分配算法可以分为转发策略与监控策略联合分配和基于转发策略的监控策略分配两类，而DIFANE[47]、vCRIB[48]和Palette[49]、One-Big-Switch[50]分别是这两类算法的代表。

（1）转发策略与监控策略联合分配

DIFANE提出了一种结合主动部署和被动部署两者优点的解决方案。首先， DIFANE在数据平面引入多个授权交换设备，并将控制器在控制平面上给交换设备配置规则的功能卸载给数据平面上的多个授权交换设备来完成。其次，DIFANE根据网络拓扑确定授权交换设备的位置，并将全局策略在多维正交空间上划分为与授权交换设备数量相同的多个不交叠策略子集。最后，DIFANE的控制器将全局策略的划分方式生成“分区规则”并预先配置到所有交换设备上，将多个策略子集生成“授权规则”并预先配置到对应的多个授权交换设备上。当网包经过交换设备没有命中有效规则时，“分区规则”会将网包重定向到该交换设备所属的授权交换设备；授权交换设备一方面根据“授权规则”对网包进行处理，另一方面生成“缓存规则”配置到网包所来的交换设备上。由于“缓存规则”的优先级要高于“分区规则”的优先级，因此后续网包会根据最新配置的“缓存规则”进行处理。DIFANE在对全局策略进行划分时，为了适应硬件交换机三态内容寻址存储器（Ternary Content Addressable Memory, TCAM）的查找特性，采用了等分空间切分的方法，并根据切分后的子空间对原始策略进行裁剪。总体上看，DIFANE综合采用全局策略分区和基于数据平面的规则被动部署，解决了大规模规则集在资源有限的硬件交换机上高效部署的问题。

vCRIB在DIFANE工作的基础上，将问题背景扩展到支持规则在软件交换设备上部署，并对DIFANE的全局策略划分方式进行优化，解决了云数据中心大规模策略管理的问题。首先，vCRIB采取了“面向源端”和“基于复制”的全局策略划分思路。前者保证了每个策略子集仅检测某个终端节点发送的流量，且所有策略子集在流量覆盖的有效空间上相互无交叠，从而极大地减轻了策略子集在后续调整及虚拟机迁移过程中的处理复杂度；后者基于对相邻源对应的策略子集相似度较高现象的观察，保证了策略划分时不会出现DIFANE中对策略进行裁剪造成的规则数目膨胀，而且方便了对多个策略子集进行合并。其次，vCRIB提出了基于背包问题建模和资源感知的策略子集分配算法。该算法实现了在保证网络节点资源限制的前提下，尽可能将相似的策略子集集中部署在相同的网络节点上。最后，vCRIB根据流量的变化对策略子集的部署结果进行微调，通过贪婪地选择当前负载最大的网络节点，并将其上的部分策略子集分散到相邻的网络节点上，以实现全网范围内资源利用率的提升和负载均衡。

（2）基于转发策略的监控策略分配

Palette针对大规模访问控制策略部署在网络接入交换设备上会导致其表项的负载过高，而核心交换设备表项较为富裕的问题，提出了将上述访问控制策略尽量分散到全网范围内的所有交换设备上，并且保证网络中每条路径上的节点全集或子集保存一份完整的全局访问控制策略。首先，Palette将全局访问控制策略按照位取值的不同或规则之间的相互依赖关系，迭代地划分为规则数目相近的多个不交叠策略子集。其次，Palette进行贪婪的网络节点选择，每次选择一个或多个网络节点部署策略子集，直到每条网络路径上都有所有策略子集的部署。图1-8展示了Palette上述的两步骤解决方案。

从对Palette策略分配过程的分析中可以看出，Palette在进行全局策略划分时没有考虑到网络流量空间的因素，因此可能会出现某条网络路径查询了与其不相关规则的情况，导致了处理资源的浪费。此外，Palette策略分配算法的性能与全网中最短路径的长度密切相关，导致该算法难以在最短路径长度较小的网络中充分利用所有交换设备的资源。One-Big-Switch工作改进了Palette算法设计中上述两个不完善的地方。首先，One-Big-Switch将网络中的所有路径分离出来，并在此基础上通过线性规划算法为每条路径分配其可用的硬件资源。其次，根据每条路径上各个交换设备为该路径分配的硬件资源，One-Big-Switch将与该路径相关的策略用多维正交空间中的单个超长方体以贪婪的方式进行划分，然后顺序部署在对应的交换设备上。最后，One-Big-Switch还根据规则操作域的取值，对需要丢弃的网络流量，在交换设备部署顺序上进行了优化，以减少网络带宽开销。