第 1 章 绪论
1.1 研究背景和意义
云计算[1]、大数据应用[2]和物联网[3]自动化网络平台的持续增加的线上服务需求已经使得传统网络架构濒临崩溃。随着如此网络服务前所未有的增长，网络工业不断的改变传统架构。开放网络基金[4]（Open Networking Foundation, ONF）提出了支持网络编程和自动化网络管理的软件定义网络（Software Defined Network, SDN）。这种网络模式通过分离转发与控制功能、移除每层功能改进的阻碍等方式促进了网络创新。SDN 也是构成下一代网络的关键技术[5]。它通过集中的控制器提供了整个网络的实时信息，促进了使用开放和可编程的转发设备。SDN 架构如图 1.1 所示。
计算机导论论文怎么写
控制层，又称为中间层，由基于软件的 SDN 控制器构成。该层控制和管理底层数据平面设备并且根据每种网络策略定义流量规则。控制层可以由单个控制器，或者分布式且逻辑集中的多个控制器构成。控制器之间使用东、西向接口来交换控制器域之间的网络信息。文献 [8] 表示，东向接口用于 SDN 控制器之间的信息交换，而西向接口则是用于交换 SDN 控制器与传统分布式控制器之间的信息交换。
............................
1.2 国内外研究现状
自 CPP 被正式提出以后，不同的网络指标被引入 CPP 以满足不同的 SDN 控制器部署需求。与传统网络相比，SDN 通过交换流表来转发数据包是 SDN 的最大特色。交换机中的流表通过控制器下发，交换机与控制器间会进行频繁 Packet_in 和P acket_out 通信。因此控制器与交换机的时延是最重要的 CPP 指标[14–39]。部署多台控制器后，SDN 被划分为多个子域，每个子域由一台控制器管理。多台控制器间需要统一 SDN 中所有链路及节点的信息。为了保证 SDN 控制器之间的一致性，控制器与控制器间也需要进行通信。因此，控制器间的时延也是关键 CPP 指标[14–25]。此外，部署成本[18]，网络容错性[31]，路径失效概率[30]等，也是常见的 CPP 指标。本节将从网络规模，优化指标，是否是 Pareto 最优，求解方法四个方面对控制器放置的研究现状进行总结，如表 1.1 所示。
从应用的网络规模上看，仅有文献 [13, 21] 的应用场景是中型 SDN。文献 [13]首次将 CPP 建模为多目标优化问题，文献 [13] 之后的 CPP 几乎均被建模成多目标优化问题，不再是文献 [10] 那样仅仅考虑 C2S。同时，文献 [13] 首次提出在 CPP 的多目标优化问题中使用 Pareto 最优边界作为优化目标。但是文献 [13] 的作者提出的控制器放置算法是蛮力法，当网络规模扩大之后，蛮力法的求解时间过长，因此局限于中型 SDN。而文献 [21] 则是首次将 SDN 控制器放置的成本作为考虑因素。
.........................
第 2 章 问题描述与数学模型
2.1 多控制器放置问题描述
SDN 中的控制器放置问题是一个 NP-hard 问题[10]。SDN 中的控制器放置位置存在两种模式，一种是 in-band，另一种是 out-band。in-band 的放置模式，控制器放置在固有的交换机节点上，且使用交换机与交换机之间的固有链路作为控制器之间以及控制器与交换机之间的通信链路。out-band 的部署模式则是为 SDN 控制器重新建立放置节点，以及铺设控制器间和控制器与交换机之间的通信链路。对于小型或者无线的 SDN，尚可采用 out-band 的放置模式，但是对于大型 SDN，out-band 的放置模式大大提高了 SDN 控制器的放置成本，且不便于维护。因此，对于大规模的 SDN，通常采用 in-band 的放置模式[58]。此外，控制器一旦确定了放置位置，一般来说无法再改变。
在确定控制器放置位置后，需要为每一台交换机分配归属控制器，每一台交换机的归属控制器集合构成了控制器与交换机的映射关系。在每一个控制域中，交换机都通过该控制器上传和下发流表，而控制器之间的通信则是通过东西向接口完成。一般来说，决定交换机的归属控制器采用路径最短原则，这样可以大大减少控制器与交换机的通信时延。其次，还有基于图论中的网络属性，首先划分子网，然后再确定交换机位置的放置方法。尽管映射关系可以通过 SDN 中的交换机迁移操作改变，但是会带来的额外的通信开销，降低系统的稳定性[59]。
.........................
2.2 优化模型
优化问题可以定义为在既定约束条件下，寻找一种情况使得选择的目标函数的值最大或者最小。一个带约束条件的优化问题的数学表达如下所示[60]：
计算机导论论文参考
通常来说，目标函数 F 以及约束条件 g 和 h 可以具备不同的属性，如非线性，非凸性和不可微性，变量可以是连续的也可以是离散的。因此，由公式 (2.1) 至 2.4 所定义的优化问题可以变得相当复杂。
....................
第 3 章 基于萤火虫算法的控制器放置算法 ....................................... 15
3.1 启发式算法 ....................................... 15
3.1.1 启发式算法的起源 ....................................... 15
3.1.2 基于群体的启发式算法的设计准则 ................................................ 16
第 4 章 萤火虫算法的改进及对比算法 .............................................. 23
4.1 动态参数的优化 ........................................ 23
4.1.1 动态光吸引度 R (t) ................................... 23
4.1.2 动态吸引因子 q (t) ................................. 24
第 5 章 实验及分析 ................................... 35
5.1 实验设置 .................................... 35
5.1.1 开发环境及拓扑信息 ......................... 35
5.1.2 对比算法参数设置 ..................................... 37
第 5 章 实验及分析
5.1 实验设置
5.1.1 开发环境及拓扑信息
开发环境为 windows 10 professional(64 bit)，处理器使用 intel(R) Core(TM) i5-7300HQ [email protected]，16.00G 内存，所有求解算法与模型均使用 Python 编程语言实现。
从 The Internet Topology Zoo 中随机挑选了 7 个 WAN 拓扑以及 Internet2 NetworkAdvanced Layer 2/3 Service 拓扑作为仿真实例[65, 66]。根据节点的经纬度计算节点间的距离，单位为 m，考虑到数据包的传输时延包括传播时延，处理时延，传输时延，故将信息在链路中的传输速度设置为光速的三分之二，2 × 108m/s[29, 33, 35]。8 个拓扑的相关参数如表 5.1 所示：
计算机导论论文参考
..........................
第 6 章 总结与展望
SDN 采用控制、转发分离的架构，采用集中控制器的控制层，提供可编程的开放接口，解决了传统计算机网络的硬件不开放、无法编程等问题。然而对于大规模SDN，放置单一控制器无法满足对整个网络管理的功能，且容易出现单点故障问题，同时会造成部分交换机与控制器之间的时延太高，影响 SDN 的服务质量。大规模SDN 需要放置多台控制器构成逻辑集中的分布式控制层。为了获得合理的控制器放置方案，本文基于改进的萤火虫算法设计控制器放置算法。
（1）提出了面向节点时延和控制器负载的多控制器放置问题的数学模型。从拓扑信息的数学表达、控制器综合时延定义以及控制器负载约束三个方面设计了控制器放置问题的数学模型。为数学分析和算法设计提供了基础。
（2）设计了基于萤火虫算法的多控制器放置方法。设计了萤火虫算法求解问题的向量，设计了萤火虫的目标函数以及萤火虫算法求解控制器放置问题的约束条件。从而在有限的时间内获取控制器综合时延低且控制器负载均衡的控制器放置方案。
（3）对萤火虫算法进行了改进。一方面，采用迭代的动态光吸引度、吸引因子、随机参数优化萤火虫算法全局搜索能力和后期收敛精度；另一方面，采用粒子群优化算法对基于萤火虫算法的多控制器放置算法的静态参数进行优化。从而在有限的时间内获取综合传输时延更低、控制器复杂更加均衡的控制器放置方案。
在真实的 WAN 拓扑将改进的 FA、FA 以及其余四种算法进行对比，实验结果表明，改进的 FA 求解的控制器放置方案的综合传输时延的均值、方差和控制器负载方差的结果最优，且算法的时间消耗处于可接受的范围内，验证了本文所提的基于改进 FA 的控制器放置方案的有效性，为推动 SDN 的有效落地提供了坚实的理论基础。
参考文献（略）