SDN控制器部署中的可靠性优化研究

毛明，陈庶樵，崔世建

（国家数字交换系统工程技术研究中心，河南郑州450002）

软件定义网络（SDN）将传统网络结构中的控制层和转发层解耦，其将所有转发设备与一个逻辑集中的控制器相连接。为避免网络规模不断扩大引起的单点失效，向分布式控制结构发展成为OpenFlow广域网部署的趋势，其中控制层多控制器的部署问题是SDN设计中的一个关键环节。提出基于控制路径连通度的控制器部署方案来最大化SDN控制器部署的可靠性，并使用3种不同的算法对比控制器部署性能。仿真结果表明，该方案可以在可接受时延范围内提升部署SDN控制器的可靠性。

SDN；控制器部署；可靠性优化；控制路径

中图分类号： TN911；TP393.0

文献标识码： A

DOI： 10.16157/j.issn.0258-7998.2017.03.027

中文引用格式： 毛明，陈庶樵，崔世建. SDN控制器部署中的可靠性优化研究[J].电子技术应用，2017，43(3)：108-111，115.

英文引用格式： Mao Ming，Chen Shuqiao，Cui Shijian. The research on reliability optimization in SDN controller placement[J].Application of Electronic Technique，2017，43(3)：108-111，115.

0 引言

软件定义网络(Software Defined Networking，SDN)的核心思想在于控制层和转发层的分离，OpenFlow[1]协议为实现其倡导的网络控制提供可编程接口，能够极大简化网络管理工作。随着SDN网络应用规模的扩大，这种集中工作模式很可能成为其在WAN中的瓶颈点[2]。为提升网络扩展性、可靠性，多控制器部署的思路逐渐受到较多的关注。

多控制器的部署问题可以归纳为：给定一个网络拓扑，需要多少个控制器能够满足网络需求，以及如何为这些控制器寻找最优位置进行部署。文献[3，4]中明确将确定控制器数量及位置的问题定义为控制器部署问题（Controller Placement Problem，CPP）。通过文中分析可以看到，现有研究方向都在向优化目标的选择集中，因此控制器部署问题是一个NP难问题。

本文提出故障场景度量值的概念来寻求控制器部署的解决方案，将节点间控制路径连通度作为实施控制器放置的首要指标。

1 相关工作

目前对于CPP的研究主要集中在两个方向进行：基于时延优化和基于可靠性优化。基于时延优化主要利用聚类思想来部署控制器及其交换机集合。该部署思想目前主要有基于平均时延、最坏情况时延[5]等部署方法。基于可靠性优化的控制器部署研究集中于控制层，主要围绕三方面展开：(1)路径可靠性[6]；(2)节点可靠性[7]；(3)负载均衡[8]。也有研究从多目标整合优化的角度来进行基于可靠性部署问题的研究[9]。

针对SDN的可靠性研究分为数据层可靠性和控制层可靠性两方面：(1)数据层可靠性：SHARMA S等人[10]利用OpenFlow1.1协议的故障转移机制来实现数据层的故障恢复，提出并评估两种不同的复原方式的性能。(2)控制层可靠性：控制层可靠性研究分为控制器及其控制路径两部分。控制器的可靠性是指应对控制器故障的可靠性保证，这类可靠性可以通过提升控制器自身的可靠性（如使用更加可靠的硬件）或使用多个备份控制器的方式得到改善[10]。

现有OpenFlow广域网部署可由两种网络类型来实现：带内网络（in-band networks）和带外网络（out-of-band networks），如图1、图2所示。在带内网络中，OpenFlow流能够共享常规网络流的相同路径。在基于OpenFlow的广域网中使用带内部署更加合理。根据OpenFlow1.3.2协议，控制器到交换机的通信路径实际上取决于IP路由协议。在广域网中，通常每一对设备之间具备多条可用路径，当前路径失效时，其他路径能够快速取代并传输OpenFlow信息。因此增强OpenFlow控制通道的多路性能够提升OpenFlow广域网的恢复能力。

2 故障场景模型描述

本文的优化目标在于合理选取控制器的部署位置，具备限制同时故障发生数的能力，在失效场景中控制路径减少的情况下，使失联节点数最小化，从而保证系统可靠性。将网络拓扑模型化为G(V，E)，其中V表示节点设备，E表示节点间的网络链路，文中符号参数定义如表1所示。

2.1 故障场景度量值建模

在故障场景fk中，为便于实验分析，使用平均链路失效概率来衡量该故障场景的整体失效概率。

遍历所有可能的故障场景，寻找使式(3)具有最小值的节点i作为控制器部署位置，此时能够确保节点i对控制路径具有最低的故障发生概率。

式（4）～式（7）是约束条件。式（4）是故障场景度量值的取值范围；式（5）表示控制器处于活跃状态时，ci取值为1，否则为0；式（6）表示在故障场景fk中该节点与所有节点路径连通度小于设定阈值，则fk(Ci)为1，否则为0；式（7）表示出现故障fk时，其所有的链路失效概率取值在0～1之间；式（8）表示首先为每个控制器分配r个交换机，如果有剩余，再根据节点连通度大小将其分配给某个控制器。

2.2 基于路径连通度的域内交换机选取策略

本文考虑寻找节点连通度最大的节点作为交换机集合来增强该控制器的控制路径连通效能。

定义1 控制路径连通度。选定每个控制器放置节点后，优先选取与控制器节点路径连通度最大的前r个交换机作为该控制器域内交换机集合。用控制器部署位置与节点间不相交路径平均数定义路径连通度，表示如下：

设定路径连通度阈值mthre，当节点路径连通度小于mthre时，即认为节点间连通度不足。

2.3 控制路径选取策略

所有路径具有相同失效概率时，为提高流运转效率，应寻找最大剩余带宽路径，选择该路径作为首要控制路径并将其他路径作为备份路径。

定义2 最大剩余带宽路径。式（10）实现选择节点a与节点b之间最大剩余带宽路径p，如下所示：

路径的带宽容量取决于组成该路径链路中的最小带宽链路，如下式所示：

路径p剩余带宽Bres(p)由路径p可用带宽减去已占用带宽Bal(p)求得：

3 控制器部署算法

本节设计基于贪婪的控制器放置算法实现控制器部署。便于与现有的随机放置算法和Survivor[6]方法进行对比。

3.1 基于贪婪的控制器放置算法

基于贪婪的控制器放置算法(Greedy-Based Controller Placement，GBCP)使用聚类思想寻找控制器及其域内管控节点集合。在完成所有迭代后，如果存在剩余节点，通过计算剩余节点与各个控制器之间的连通性关系，再将其分配至各个控制器域。

基于贪婪的控制器放置算法（GBCP）：

输入：G=(V，E)，控制器数m，故障场景集合F；

输出：C，Su。

(1)i=0，V1=V

(2)for u in V1

(3)计算u在所有已知可能的故障场景F中的f(Ci)，并升序排序；

(4)选择具有最小f(Ci)的节点u（如有多个相同的节点，则随机选择），加入控制器集合C中；

(5)通过式(9)选取出与节点u连通度最大的前r个点作为该控制域内的交换机集合Su；

(6)把节点u和集合Su内的所有节点从集合V1中移除；

(7)i=i+1

(8)if i<m：返回以上for循环；

(9)else if i=m：

(10)if V1≠φ：

(11)for v in V1

(12)计算v 和集合C中各控制器的连通性关系，并将其分配至连通度最大的控制器域中；

(13)end for

(14)end for

3.2其他算法介绍

该两种方案是现有的用来获取m个控制器位置实现控制器部署的实施方案。

（1）随机放置算法（random）：该算法是随机地在所有可能的V个节点中选取m个位置作为控制器部署节点。

（2）Survivor：该方法通过明确考虑路径多样性从而增强节点连通性；在控制器部署中增加容量感知机制，主动避免控制器的过载问题；通过控制器容量的备用剩余容量实现故障恢复机制。

4 性能评估

为方便实验，设定每个实验场景中所有链路具有相同的链路失效概率，因此实验中使用链路失效概率来量化故障场景度量值。

在Internet 2、RNP、GEANT、GOODNET、ARPANET19719等网络拓扑实施如下实验内容：（1）使用GBCP部署方法，计算出控制器数目变化与控制路径损失率的关系；设定所有路径故障概率都为0.05；（2）在GBCP部署方法得到最佳控制器数目时，通过平均路径失效概率的变化，观察各部署方案的网络拓扑中控制路径的损失情况；（3）对比使用本文提出的部署方案，每个网络拓扑中部署不同数目的控制器对应时延变化情况。

图3是控制器数目与控制路径损失率之间的对应关系，其中m/n表示控制器数目m与交换机节点数目n之间的比率。分析发现，以上5种实验拓扑的曲线变化具有相似的特征，并且m的取值在0.073n～0.164n之间具有最佳的控制路径可靠性。这是因为尽管广域网中通常需要较多的控制器来保证可靠性，但控制器数目不断地增加又会造成控制器与交换机之间的路径连通度降低，控制路径损失也相应地增加。因此实际网络拓扑中的控制器部署需谨慎选择控制器的数目。

在实验（1）中已经获知，GBCP的部署方案在每个网络拓扑中都有相似的性能表现，因此仅选取Internet 2(m=0.122n)测试3种部署方法得到的路径失效概率与控制路径损失率的关系。图4是路径失效概率与控制路径损失率之间的关系。随着路径失效概率的上升，控制路径损失率也呈现增加的趋势；相同路径失效概率时，Survivor控制路径损失率始终最低，random最高。在路径失效概率为0.1时，random控制路径损失率高达54%。相比随机放置算法，使用最大路径连通效能的部署方案能够降低路径损失率，提升控制路径可靠性。

现有研究表明，每个控制器在200 ms时限内可以保证流安装时间的一致性[11]。实验（1）在5种拓扑进行实验的同时，对其相应时延情况也做了统计。图5、图6分别是控制器数目变化与平均时延[3]和最坏情况时延[3]的关系。控制器数取值在区间（0.073n，0.164n）之间时，平均时延最大值为18 ms，最坏情况时延最大值为83 ms。文中基于可靠性优化的控制器部署方案选取最优控制器数目后所产生的时延仍然在控制器可承受的性能范围内，从而保证SDN网络在基于可靠性进行控制器部署时不受时延约束。

5 结语

本文利用最大化控制路径可靠性的思想来解决SDN中的控制器部署问题。使用故障场景度量值的方法来保证控制路径失效率最小化，并权衡可靠性与时延的关系。通过使用不同的放置算法进行实验，得到以下结论：控制器部署的性能取决于使用的控制器部署方法；必须合理选择控制器数目；基于可靠性优化得到的最优控制器部署，其产生的时延在控制器响应时间限制范围内。

参考文献

[1] GUDE N，KOPONEN T，PETTIT J，et al.NOX：towards an operating system for networks[J].Acm Sigcomm Computer Communication Review，2008，38(3)：105-110.

[2] TOOTOONCHIAN A，GANJALI Y.HyperFlow：a distributed control plane for OpenFlow[C].Internet Network Management Conference on Research on Enterprise NETWORKING，Washington，DC，2010.USENIX Association，2010.

[3] HELLER B，SHERWOOD R，MCKEOWN N.The controller placement problem[J].Acm Sigcomm Computer Communication Review，2013，42(4)：7-12.

[4] UL HUQUE M T I，JOURJON G，GRAMOLI V.Revisiting the controller placement problem[C].IEEE，Conference on Local Computer Networks，Clearwater，Florida，USA，2015.IEEE Computer Society，2015：450-453.

[5] 姚琳元，陈颖，宋飞，等.基于时延的软件定义网络快速响应控制器部署[J].电子与信息学报，2014(12)：2802-2808.

[6] MULLER L F，OLIVEIRA R R，LUIZELLI M C，et al.Survivor：An enhanced controller placement strategy for improving SDN survivability[C].IEEE Global Communications Conference，2014：1909-1915.

[7] ZHANG Y，BEHESHTI N，TATIPAMULA M.On resilience of split-architecture networks[C].Global Telecommunications Conference(GLOBECOM 2011)，2011，2011：1-6.

[8] GUO Z，SU M，XU Y，et al.Improving the performance of load balancing in software-defined networks through load variance-based synchronization[J].Computer Networks，2014，68(11)：95-109.

[9] LANGE S，GEBERT S，ZINNER T，et al.Heuristic approaches to the controller placement problem in large scale SDN networks[J].IEEE Transactions on Network & Service Management，2015，12(1)：1.

[10] SHARMA S，STAESSENS D，COLLE D，et al.Enabling fast failure recovery in OpenFlow networks[C].International Workshop on the Design of Reliable Communication Networks，Drcn，2011.Krakow，Poland，2011：164-171.

[11] ABBAS G.Network survivability[M].Springer US，2006.

性能提升 25 倍！字节开源高性能 C++ JSON 库 sonic-cpp

sonic-cpp 是由字节跳动 STE 团队和服务框架团队共同研发的一款面向 C++ 语言的高效 JSON 库，极致地利用当前 CPU 硬件特性与向量化编程，大幅提高了序列化反序列化性能，解析性能为 rapidjson 的 2.5 倍。sonic-cpp 在字节内部上线以来，已为抖音、今日头条等核心业务，累计节省了数十万 CPU 核心。近日，我们正式对外开源 sonic-cpp，希望能够帮助更多开发者。

Github 地址：https://github.com/bytedance/sonic-cpp

1. 为什么自研 JSON 解析库

在字节跳动，有大量的业务需要用到 JSON 解析和增删查改，占用的 CPU 核心数非常大，所对应的物理机器成本较高，在某些单体服务上JSON CPU 占比甚至超过 40%。因此，提升 JSON 库的性能对于字节跳动业务的成本优化至关重要。同时，JSON 解析库几经更新，目前业界广泛使用的 rapidjson 虽然在性能上有了很大的改进，但相较于近期一些新的库（如 yyjson 和 simdjson），在解析性能方面仍有一定的劣势。

图 1.1 yyjson、simdjson 和 rapidjson 解析性能对比https://github.com/ibireme/yyjson

yyjson 和 simdjson 虽然有更快的 JSON 解析速度，但是都有各自的缺点。simdjson 不支持修改解析后的 JSON 结构，在实际业务中无法落地。yyjson 为了追求解析性能，使用链表结构，导致查找数据时性能非常差。

图1.2 yyjson 数据结构；图片来源自：https://github.com/ibireme/yyjson

基于上述原因，为了降低物理成本、优化性能，同时利用字节跳动已开源 GoJSON 解析库 sonic-go 的经验和部分思路，STE 团队和服务框架团队合作自研了一个适用于 C/C++ 服务的 JSON 解析库 sonic-cpp。

sonic-cpp 主要具备以下特性：

高效的解析性能，其性能为 rapidjson 的 2.5 倍。解决 yyjson 和 simdjson 各自的缺点，支持高效的增删改查。基本上支持 json 库常见的所有接口，方便用户迁移。在字节跳动商业化广告、搜索、推荐等诸多中台业务中已经大规模落地，并通过了工程化的考验。

2. sonic-cpp 优化原理

sonic-cpp 在设计上整合了 rapidjson ，yyjson 和 simdjson 三者的优点，并在此基础上做进一步的优化。在实现的过程中，我们主要通过充分利用向量化（SIMD）指令、优化内存布局和按需解析等关键技术，使得序列化、反序列化和增删改查能达到极致的性能。

2.1 向量化优化（SIMD)

单指令流多数据流（Single Instruction Multiple Data，缩写：SIMD ）是一种采用一个控制器来控制多个处理器，同时对一组数据中的每一个数据分别执行相同的操作，从而实现空间上的并行性技术。例如 X86 的 SSE 或者 AVX2 指令集，以及 ARM 的 NEON 指令集等。sonic-cpp 的核心优化之一，正是通过利用 SIMD 指令集来实现的。

2.1.1序列化优化

从DOM内存表示序列化到文件的过程中，一个非常重要的过程是做字符串的转义，比如在引号前面添加转义符\。比如，把This is "a" string 序列化成 "This is \"a\" string" ，存放在文件。常见的实现是逐个字符扫描，添加转义。

比如 cJson 的实现：https://github.com/DaveGamble/cJSON/blob/master/cJSON.c#L902

sonic-cpp 则通过五条向量化指令，一次处理 32 个字符，极大地提高了性能。

序列化过程如下：

通过一条向量化 load 指令，一次读取 32 字节到向量寄存器 YMM1；YMM1 和另外 32 字节（全部为“）做比较，得到一个掩码(Mask)，存放在向量寄存器 YMM2；再通过一条 move mask 指令，把 YMM2 中的掩码规约到 GPR 寄存器 R1；最后通过指令计算下 R1 中尾巴 0 的个数，就可以得到”的位置。

但如果没有 AVX512 的 load mask 指令集，在尾部最后一次读取 32 字节时，有可能发生内存越界，进而引起诸如 coredump 等问题。sonic-cpp 的处理方式是利用 Linux 的内存分配以页为单位的机制，通过检查所要读取的内存是否跨页来解决。只要不跨页，我们认为就算越界也是安全的。如果跨页了，则按保守的方式处理，保证正确性，极大地提高了序列化的效率。

具体实现见 sonic-cpp 实现:https://github.com/bytedance/sonic-cpp/blob/master/include/sonic/internal/quote.h#L256

2.1.2反序列化优化

在 JSON 的反序列化过程中，同样有个非常重要的步骤是解析数值，它对解析的性能至关重要。比如把字符串"12.456789012345" 解析成浮点数 12.456789012345。常见的实现基本上是逐个字符解析。见 Rapidjson 的实现：https://github.com/Tencent/rapidjson/blob/v1.1.0/include/rapidjson/reader.h#L1133

sonic-cpp 同样采用 SIMD 指令做浮点数的解析，实现方式如下图所示。

和序列化向量化类似，通过同样的向量指令得到小数点和结束符的位置，再把原始字符串通过向量减法指令，减去'0', 就得到真实数值。

当我们确定了小数点和结束符的位置，以及向量寄存器中存放的 16 个原始数值，通过乘加指令把他们拼成最终的 12456789012345和指数 12。

针对不同长度的浮点数做 benchmark 测试，可以看到解析性能提升明显。

但我们发现，在字符串长度相对比较小（少于 4 个）的情况下，向量化性能反而是劣化的，因为此时数据短，标量计算并不会有多大劣势，而向量化反而需要乘加这类的重计算指令。

通过分析字节跳动内部使用 JSON 的特征，我们发现有大量少于 4 位数的短整数，同时我们认为，浮点数位数比较长的一般是小数部分，所以我们对该方法做进一步改进，整数部分通过标量方法循环读取解析，而小数部分通过上述向量化方法加速处理，取得了非常好的效果。流程如下，具体实现见sonic-cpp ParseNumber 实现:https://github.com/bytedance/sonic-cpp/blob/master/include/sonic/dom/parser.h#L382

2.2 按需解析

在部分业务场景中，用户往往只需要 JSON 中的少数目标字段，此时，全量解析整个 JSON 是不必要的。为此，sonic-cpp 中实现了高性能的按需解析接口，能根据给定的 JsonPointer（目标字段的在 JSON 中的路径表示）解析 JSON 中的目标字段。在按需解析时，由于JSON 较大，核心操作往往是如何跳过不必要的字段。如下：

2.2.1 传统实现

JSON 是一种半结构化数据，往往有嵌套 object 和 array。目前，实现按需解析主要有两种方法：递归下降法和两阶段处理。递归下降法，需要递归下降地“解析”整个 JSON，跳过所有不需要的 JSON 字段，该方法整体实现分支过多，性能较差；两阶段处理需要在阶段一标记整个 JSON token 结构的位置，例如,}]等，在阶段二再根据 token 位置信息，线性地跳过不需要的 JSON 字段，如按需查找的字段在 JSON 中的位置靠前时，该方法性能较差。

2.2.2 sonic-cpp 实现

sonic-cpp 基于 SIMD 实现了高性能的单阶段 的按需解析。在按需解析过程中，核心操作在于如何跳过不需要的 JSON object 或 array。sonic-cpp 充分利用了完整的 JSON object 中 左括号数量必定等于右括号数量 这一特性，利用 SIMD 读取 64 字节的 JSON 字段，得到左右括号的 bitmap。进一步，计算 object 中左括号和右括号的数量，最后通过比较左右括号数量来确定 object 结束位置。具体操作如下：

经过全场景测试，sonic-cpp 的按需解析明显好于已有的实现。性能测试结果如下图。其中，rapidjson-sax 是基于 rapidjson 的 SAX 接口实现的，使用递归下降法实现的按需解析。simdjson 的按需解析则是基于两阶段处理的方式实现。Normal，Fronter，NotFoud 则分别表示，按需解析时，目标字段在 JSON 中的位置居中，靠前或不存在。不过，使用 sonic-cpp 和 simdjson 的按需解析时，都需要保证输入的 JSON 是正确合法的。

2.2.3 按需解析扩展

sonic-cpp 利用 SIMD 前向扫描，实现了高效的按需解析。在字节跳动内部，这一技术还可以应用于两个 JSON 的合并操作。在合并 JSON 时，通常需要先解析两个 JSON，合并之后，再反序列化。但是，如果两个 JSON 中需要合并的字段较少，就可以使用按需解析思想，先将各个字段的值解析为 raw JSON 格式，然后再进行合并操作。这样，能极大地减少 JSON 合并过程中的解析和序列化开销。

2.3 DOM 设计优化

2.3.1节点设计

在 sonic-cpp 中，表示一个 JSON value 的类被称作 node。node 采用常见的方法，将类型和 size 的信息合为一个，只使用 8 字节，减少内存的使用。对于每个 node，内存上只需要 16 字节，布局更紧凑，具体结构如下：

2.3.2DOM树设计

sonic-cpp 的 DOM 数据结构采用类似于 rapidjson 的实现，可以对包括 array 或 object 在内的所有节点进行增删查改。

在 DOM 的设计上，sonic-cpp 把 object 和 array 的成员以数组方式组织，保证其在内存上的连续。数组方式让 sonic-cpp 随机访问 array 成员的效率更高。而对于 object，sonic-cpp 为其在 meta 数据中保存一个 map。map 里保存了 key 和 value 对应的 index。通过这个 map，查找的复杂度由 O(N) 降到 O(logN)。sonic-cpp 为这个 map 做了一定的优化处理：

按需创建： 只在调用接口时才会生成这个 map，而不是解析的时候创建。使用 string_view 作为 key： 无需拷贝字符串，减少开销。

2.3.3内存池

sonic-cpp 提供的内存分配器默认使用内存池进行内存分配。该分配器来自 rapidjson。使用内存池有以下几个好处：

避免频繁地 malloc。DOM 下的 node 只有 16 byte，使用内存池可以高效地为这些小的数据结构分配内存。避免析构 DOM 上的每一个 node，只需要在析构 DOM 树的时候，统一释放分配器的内存即可。

Object 内建的 map 也使用了内存池分配内存，使得内存可以统一分配和释放。