推荐星级：
- 1
- 2
- 3
- 4
- 5
软件定义网络中面向时延和负载的多控制器放置策略
资料介绍
在多控制器管理的软件定义网络(SDN)中,时延和负载是控制器放置问题(CPP)要考虑的重要因素.该文以降低控制器之间的传播时延、流请求的传播时延和排队时延、均衡控制器间负载为目标,提出一种控制器放置及动态调整的策略,其中包括用于初始控制器放置的负载均衡算法(BCRA)和遗传算法(GA),用于动态调整控制器负载的在线调整算法(ADOA).以上算法均考虑网络连通性.仿真结果表明:在初始控制器放置时,在保证流请求的传播时延、排队时延和控制器传播时延较低的情况下,BCRA部署在中小型网络中时,其负载均衡性能与GA相近且优于k-center和k-means算法;GA部署在大型网络中时,与BCRA,k-center和k-means算法相比,使得负载均衡率平均提高了49.7％.在动态情况下,与现有动态调整算法相比,ADOA可以保证较低排队时延和运行时间的同时,仍能使负载均衡参数小于1.54.
部分文件列表
| 文件名 | 大小 |
| 软件定义网络中面向时延和负载的多控制器放置策略.pdf | 1M |
部分页面预览
（完整内容请下载后查看）第41卷第8期
2019年8月
电 子 与 信 息 学 报
Vol. 41No. 8
Aug. 2019
Journal of Electronics & Information Technology
软件定义网络中面向时延和负载的多控制器放置策略
史久根
谢熠君*
孙
立
郭
胜
刘雅丽
(合肥工业大学计算机与信息学院 合肥 230009)
摘
要：在多控制器管理的软件定义网络(SDN)中，时延和负载是控制器放置问题(CPP)要考虑的重要因素。该
文以降低控制器之间的传播时延、流请求的传播时延和排队时延、均衡控制器间负载为目标，提出一种控制器放
置及动态调整的策略，其中包括用于初始控制器放置的负载均衡算法(BCRA)和遗传算法(GA)，用于动态调整控
制器负载的在线调整算法(ADOA)。以上算法均考虑网络连通性。仿真结果表明：在初始控制器放置时，在保证
流请求的传播时延、排队时延和控制器传播时延较低的情况下，BCRA部署在中小型网络中时，其负载均衡性能
与GA相近且优于k-center和k-means算法；GA部署在大型网络中时，与BCRA, k-center和k-means算法相比，使
得负载均衡率平均提高了49.7%。在动态情况下，与现有动态调整算法相比，ADOA可以保证较低排队时延和运
行时间的同时，仍能使负载均衡参数小于1.54。
关键词：软件定义网络；控制器放置；负载均衡；网络时延；动态调整
中图分类号：TP393.3
文献标识码：A
文章编号：1009-5896(2019)08-1869-08
DOI:
Multi-controller Placement Strategy Based on Latency and
Load in Software Defined Network
SHI Jiugen
XIE Yijun
SUN Li
GUO Sheng
LIU Yali
(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)
Abstract: In Software Defined Networks (SDN), latency and load are important factors for Controller
Placement Problem (CPP). To reduce the transmission latency between controllers, the propagation latency
and queuing latency of flow requests, and balance the controller load, a strategy on how to place and adjust the
controller is proposed. It mainly includes Genetic Algorithm (GA) and Balanced Control Region Algorithm
(BCRA) which are used to place the initial controller and one Algorithm of Dynamic Online Adjustment
(ADOA), that is an online adjusting algorithm in term dynamic controlling. The above algorithms are all based
on the network connectivity. The simulation results show that in initial controller placement situation, under
the premise of guaranteeing the lower propagation latency, queue latency and controller transmission latency of
flow request, when BCRA is deployed in small and medium-sized networks, its load balancing performance is
similar to that of GA and superior to k-center and k-means algorithm; When GA is deployed in large networks,
compared with BCRA, k-center and k-means, the load balancing rate increases averagely 49.7%. In the dynamic
situation, ADOA can guarantee lower queuing delay and running time, and can still make the load balance
parameter less than 1.54.
Key words: Software Defined Network (SDN); Controller placement; Load balancing; Network latency;
Dynamic adjustment
1
引言
SDN)作为一种新型的网络架构，其思想是将网络
的控制层与数据层解耦，从而利用集中式的控制器
对底层设备可编程化管理，进而实现对网络资源的
灵活调配。随着SDN的应用，带来了一些新的挑
战，如控制器放置问题(Controller Placement
Problem, CPP)：即给定一个网络，确定控制器的
数量及位置。
软件定义网络(Software Defined Network，
收稿日期：2018-11-20；改回日期：2019-04-09；网络出版：2019-04-23
*通信作者：谢熠君
基金项目：国家重大科学仪器设备开发专项(2013YQ030595)
Foundation Item: The National Major Scientific Instruments
Development Project (2013YQ030595)
Heller等人[]最先指出CPP是一个NP难题，以
万方数据
1870
电 子 与 信 息 学 报
第41 卷
平均时延和最大时延为指标，选择控制器位置，并
(1) 总时延。网络时延主要由传播时延，排队
指出一个随机选择的放置方案比最优方案会造成更 时延，处理时延和发送时延组成。对于广域网来
大的时延；Lange等人[]考虑控制器间时延，并提 说，传播时延、排队时延会从根本上影响网络的性
出一种适用于广域网的启发式放置算法；Zhang 能，因此本文定义控制器和交换机间的传播时延与
等人[]以提高网络可靠性、控制器负载均衡和控制 排队时延之和为总时延。
器的响应时间为目标，使用自适应细菌觅食优化算
法解决控制器初始放置问题。Jalili等人[]考虑了传
播时延和负载均衡，并提出遗传算法来解决控制器
最佳放置问题。Hu等人[]建立二进制整数模型，以
最小化网络能源消耗为目标提出遗传启发式算法。
但上述方案没有考虑控制器排队时延和动态调整负
载问题。对于网络的负载问题，Sallahi等人[]提出
了控制器放置模型，并且考虑了控制器间的差异性
及控制器间的连接问题；Jimenez等人[]仅考虑了
控制器管理的交换机数量和控制器的流量负载；
Yao等人[]假定交换机的请求流量为一个固定值，
提出单控制器和多控制放置方案，并给出了交换机
迁移的动态算法；文献[]利用控制器模块，一个控
制模块内放置多个控制器，根据每个交换机的负载
请求，动态调整控制模块内的控制器数量。但上述
方案，仅讨论了网络的动态调整，没有考虑控制器
间的传播时延和排队时延。对于控制器的排队时
延，Sood等人[]考虑传播时延和排队时延对网络性
能的影响，但并没有采用实际的拓扑图进行实验。
Wang等人[]考虑端到端的传播时延以及控制器排
队时延，提出聚簇网络划分算法来减少端到端的传
播时延，并放置多控制器来减少排队时延，但是没
有考虑负载均衡和动态调整问题。
(2) 控制器间传播时延。在部署多控制器的网
络中，控制器间需要通信来获得全局网络的视图，
因此减少控制器间的传播时延，有利于提高整个网
络的一致性。
(3) 负载均衡。在SDN中，控制器的负载越
大，则处理时间越久，从而造成控制器处理效率低
下。因而，均衡各个控制器的负载，会提高整个网
络的服务质量。
因此，本文考虑静态部署控制器时，在保证总
时延和控制器传播时延较低的同时，均衡各个控制
器的负载。动态调整负载时，保证较低的排队时延
和运行时间。
2.2 系统模型
用无向图G(V, E)表示SDN, V 表示网络中节点
集合，E表示网络中边的集合，n表示网络中节点
数量，D表示节点的度。假设在SDN中放置k个控
制器，则控制器集合表示为C = {i |i = 1, 2, •••, k}。
每个控制器i管理的交换机集合表示为CAi。那么将
网络划分为k个子网需要满足以下两个条件：
k
∪
V=
CAi, i = 1, 2, •••, k
(1)
i=1
CAi ∩ CAh = φ, i = h, i, h = 1, 2, •••, k
(2)
综上所述，大部分研究主要以传播时延和负载
均衡为目标来研究多控制器静态放置问题，然而多
控制器放置问题是一个多目标组合优化问题，故本
文在考虑传播时延和负载均衡的基础上，进一步考
虑控制器间的传播时延和排队时延对CPP的影响。
并针对这些目标，提出负载均衡算法(Balanced
Control Region Algorithm, BCRA)和遗传算法
(Genetic Algorithm, GA)用于解决多控制器静态放
置问题，在线动态调整算法(Algorithm of Dynamic
Online Adjustment, ADOA)用于解决网络动态负
载问题。
其中，式(1)表示所有子网的并集要覆盖整个网络，
式(2)表示子网间没有重叠的节点。
为进一步描述多控制器放置问题，本文做出以
下定义：
定义1 传播时延。传播时延主要分为两个部
分，(1)交换机到控制器间的传播时延(TCS)；
(2)控制器之间传播时延(TCC)。openflow交换机
的数据流在节点间传播时延TDi,j 之和与传输距离
di,j 成正比，vc表示数据在链路中的传输速度。即
Σ
1
di,j
TCSi =
TCCi =
•
, i ∈ C
(3)
(4)
|CAi|
vc
j∈CAi
本文的后续章节安排如下，第2节控制器放置
模型；第3节介绍控制器放置及动态调整算法；第
4节给出仿真实验；最后给出结束语。
Σ
1
•
di,h
, i ∈ C
|C|
vc
h∈C
2
控制器放置模型
式(3)表示控制器i所在子网的平均传播时延，式(4)
表示控制器i到其他控制器的平均传播时延。
定义2 排队时延Tq。控制器排队时延[–]是
2.1 问题描述
在SDN中，传播时延、排队时延和控制器负载
影响着网络性能。因此本文主要考虑以下3个方面： 指流量进入控制器后在输入队列中排队等待处理的
万方数据
全部评论(0)