SDN网络中交换机动态迁移问题建模
基于SDN交换机迁移问题，将SDN系统定义为，这仅仅是指交换机和控制器这两个集合，只要能够改变交换机和控制器之间的连接关系，就可以实现控制器之间的的负载均衡。和分别指交换机集合和控制器集合。是指交换机集合中的交换机，是控制器集合中的控制器。交换机的数量表示为，和控制器的数量表示为。将交换机对于控制器的流请求设置为，表示为交换机对于控制器的流量请求。交换机和控制器之间的连接关系定义为，这是一个二进制数值，取值为或者。为1时设置为连接到控制器，为0时设置为交换机未连接到控制器。连接到控制器的交换机数量定义为。如下所示表1是交换机迁移的相关标号。
1
表1 交换机迁移的相关标号
变量
含义
核心控制节点或者控制器
普通交换机
重要交换机
交换机的总数目
控制器的总数目
交换机与控制器之间的连接关系
连接到控制器的交换机数量
连接到控制器的重要交换机数量
控制器连接的所有交换机的流请求
所有控制器所连交换机的平均负载
链接的外设
普通，重要交换机或其他网络设备
(1)
(2)
(3)
(4)
式(1)表示连接到控制器的交换机数量定义为。式(2)表示连接到控制器的重要交换机数量定义为。式(3)表示控制器上的负载定义为从其连接的所有交换机的流请求总和。式(4)表示所有控制器所连交换机的平均负载。
切换迁移算法的优化目标是平衡控制器的负载，如(5)式所示，使控制器的负载均衡度最小化。为了得到优化解，一些约束是交换机迁移问题所固有的，即延迟约束、二元约束和代数约束。
(5)
： (6)
(7)
(8)
(9)
(10)
延迟约束：从控制器到交换机的延迟定义为，如(6)所示，控制器到交换机的最大延迟的最小值必须小于阈值。(7)表示成本限制:迁移的交换机的数量被定义为迁移成本，它被标记为e最大值必须小于阈值。用式(8)表示二进制约束:一个交换机只连接到一个专用控制器。该控制器在公式(9)中表示代数约束:在SDN中连接到控制器的交换机总数等于。式（10）表示在SDN中连接到控制器的重要交换机的总数等于。交换机的迁移过程如图1所示，交换机从控制域划分到控制域，从控制器迁移到控制器，实现控制器负载均衡。
图1 交换机的迁移过程
3 SDN中交换机重要性等级的划分
3.1 交换机重要性划分的因素
交换机集合描述为：。其中，到分别表示实验环境下的台交换机，整个网络中交换机重要性程度并不相同，因此不同重要性的交换机的迁移优先性不同，为了表示出整个网络环境下出现的交换机情况，考虑以下两个方面进行交换机重要性等级的划分：
(1)
交换机连接的节点度数（即所连接的链路数目，把交换机当做节点，节点与网络中其它节点之间的关联边总数为的度数）。
(2) 交换机连接的链路数目中是否包含关键链路。
通过以上两个因素将交换机进行重要
性等级分化，划分成重要交换机和普通交换机两种类型交换机。
3.2 交换机连接的关键链路数的计算
根据网络拓扑图的拓扑结构度量指标节点度数，来计算出交换机连接的关键链路数。
在SDN网络中，控制器与交换机之间的连接，以及交换机与交换机之间的连接，因此交换机所连接的链路可能不止一条，通过网络拓扑图的拓扑结构度量指标节点度数，将计算出复杂网络拓扑中某个节点拥有相邻节点的数目，即节点关联边的数目，即可得出每个交换机连接的关键链路。
3.3 衡量交换机的重要性参数
每个交换机连接的节点度数的多少代表着交换机重要程度的不同，将控制器和交换机连接的拓扑结构的度量指标节点度数作为衡量交换机重要程度的重要参数，设拓扑结构度量指标节点度数用来表示，则连接交换机的回报函数为：
（11）
上式表示交换机的重要程度，越大，则表示交换机越重要。交换机重要性参数值越大，代表交换机重要性程度越高。只是一个参数，根据实际情况来定，没有实际意义。根据特定的网络拓扑结构图，本课题将定义交换机的重要程度门限值为。门限值的具体值由实际情况而定。
(1)
当交换机重要性参数小于等于门限值时，则该交换机为普通交换机，对于普通交换机，主要考虑dijkstra算法进而引入迁移代价，从而实现负载均衡，由于普通交换机的重要程度对迁移影响程度为，因此不再考虑它。
(2)
当交换机重要性参数大于门限值时，该交换机为重要交换机，值越大，交换机重要性程度越高。对于重要交换机的迁移，不仅要考虑迁移代价，而且更应考虑重要交换机的安全性。基于保证交换机的安全，确保同一核心控制器下连接的重要交换机数量最小化，迁移交换机时将重要交换机迁移到不同的控制器下。
4 基于Q－learning的动态交换机迁移算法
4.1 基于Q－learning动态交换机迁移算法相关元素定义
应用Q-learning算法的感知管理特性[12]，需要对相关的一些要素进行确定，并动态选择系统性能指标的最优化动作。
一个强化学习系统不仅只有智能体和环境，还有四个基本的元素：策略，值函数，回报函数和环境模型（非必需）[4]。下面对应用Q－learning算法所要确定的几个重要因素进行说明。
4.1.1 状态空间定义
智能体合理选择动作的基础是先划分状态空间，对于SDN控制器负载均衡算法来说，状态空间应该是所有控制器构成的集合，即基于Q-learning算法的SDN状态空间是由每个控制器构成状态集合。
4.1.2 动作空间定义
对于基于Q-learning算法的SDN控制器负载均衡算法，所有交换机到核心控制器的连接作为动作空间。每一次迁移每个状态只能选择一个动作。所以在控制器结构中，根据就近原则，设置结构中有个交换机和个控制器，预先随机把个交换机分配给个核心控制器管理，随后依据Q-learning算法进行迁移。
(1) 如果交换机为普通交换机，引入迁移代价的概念，即当需要迁移的时候，采用dijkstra算法(狄克斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题)，即使交换机负载很小的时候，它也并不会迁移到较远的核心控制器的管理之下。
(2) 如果交换机为重要交换机时，首先根据根据dijkstra 算法和网络拓扑图的拓扑结构度量指标节点度数求出Q值最大的控制器，如果Q值最大的控制器只有一个，则进行交换机的连接，如果Q值最大的控制器有多个，则选择连接重要交换机数目最少的控制器进行连接。
4.1.3 回报函数
回报函数是指智能体在与环境的不断交互中，环境对智能体动作的好坏产生的一种评价[4]。控制器从动作集合中选择某一动作之后，网络环境会对这个动作做出评价，给予一个奖励值并发生状态转移。控制器从某个动作得到的回报函数值越大，那么之后控制器再次选择该动作的概率就会增加。从某个动作得到的回报函数值越小，那么之后控制器再次选择该动作的概率就会减少。基于回报函数的设计，希望分配给每个核心控制器的重要交换机的数目最小化，回报函数如下(12)表示为：
(12)
式中:在状态动作下， 表示单个交换机的负载; 是指标号为的核心控制器下所有交换机的负载总和。为衡量该交换机重要程度的重要性参数。该值越大，交换机重要性程度越大，回报函数越大。为一个参数，越大，代表交换机重要程度对于回报函数影响越大。回报函数越大，迁移可能性越大。
4.1.4 搜索策略
在Q-learning算法中我们定义一个值函数，表示我们在状态下执行动作获得的未来奖励，并进行迭代运算继续优化函数。有了这个函数就可以很方便的进行决策，从而采取值最高的动作，用公式表示为：
(13)
其中（13）式表示一种策略，策略即为在某个状态下选择动作的规则，如果最大值对应的控制器只有一个，则会采取值最高的动作作为最优策略，如果最大值对应的控制器为多个，则会采取采取值最高并且所连接所有控制器中连接重要交换机最少的动作作为最优策略。
4.1.5 Q值更新
Q-learning算法的核心思想就是采用数值迭代求解方法来逼近最优值，在Q-learning学习过程当中，通过迭代计算来逼近最优值函数，预先设置了一个的矩阵，初始化矩阵并把初始值都设定为相同值，设定为0。当Q-learning算法运行第一次的时候，根据dijkstra 算法，首先计算出每个交换机分别到核心控制器的最短距离(其中表示标号为的交换机到标号为1的核心控制器的最短距离，依次类推)。然后根据网络拓扑图的拓扑结构度量指标节点度数，求出SDN控制器系统的关键链路，进而计算出有关每个交换机重要程度的重要性参数。结合以上两点以及回报函数进行值的更新，即表示的是最大折扣未来奖励，公式如下：
(14)
(15)
其中，分别表示控制器当前的状态和动作，和分别表示当前状态的下一个状态及采取的下一个动作，学习参数为折扣系数，取值。学习参数趋于0，表示控制器决策更多的是考虑当前行为的奖励值，学习参数如果趋于1表示控制器决策会同时考虑到未来行为的奖励值。算法中的系数指的是学习效率，用于控制旧的值和新的值之间的差异程度，如果等于0，那么函数就没有迭代，如果等于1，那它就是一个贝尔曼方程。在当前状态和当前动作下：为在智能体获得的即时回报(reward)；为系统将会转入的下一状态；为状态下可采取的动作；为智能体总计期望回报的预计值。为下一个状态的所有可能动作的最大奖励值。
4.2 基于Q-learning的动态交换机迁移算法
Q-learning算法思想应用在SDN控制器负载均衡问题中，根据Q-learning算法思想定义SDN控制器系统中的状态空间，动作空间，策略函数，回报函数以及值函数。进而基于Q-learning算法来实现SDN控制器负载均衡。
基于Q-learning的迁移管理流程如下：
(1) 设置参数，，以及矩阵中的环境奖励值；
(2)
初始化值矩阵。（为网络中控制器的个数，为网络中交换机的个数），初始化矩阵所有的值全为0；
(3)
对交换机进行重要性的等级划分。根据交换机重要性程度参数，将交换机分为重要交换机和普通交换机；
(4)
检查控制器负载状况。若局部控制域内流量得不到处理或者处理能力严重过剩时，系统将自动查找阵；
(5)
随机选择一个状态，设置当前状态等于初始状态，从当前状态开始根据搜索策略算法选择连接交换机数量最少并且具有最大值的动作。在表，每一个竖列有个值。根据算法得出距离相近的两个核心控制器，并选取具有最大Q值的状态作为当前交换机的激活状态，并将slaver交换机迁移到与相应的核心控制的管理下，并记录在每个周期内发生迁移的交换机总个数以及迁移的重要交换机的总个数；
(6)
计算即时回报函数值。对于一个周期内的slaver交换机的负载，用每个slaver交换机的负载除以在该周期内每个核心控制器下所有交换机的总负载的比值以及的值作和，得出；
(7)
更新值。当在状态下，选择动作后得到的值，如果在此状态下值比原二维矩阵中的相应位置值大，则更新。反之则不进行更新；
(8)
进行交换机迁移。选择阵中每列具有最大值的状态作为下一个状态，如果最大的值还是当前位置的，则交换机不发生迁移，反之则迁移；同时更新状态的下一状态；
(9)
重复执行以上步骤直到状态成为目标状态。
{
}
c
(
)
,1;,,0,1
j
ijij
CC
ibijb
Î
“=”Î
å
1
c
N
CSS
j
NN
=
=
å
1
C
N
CZSZS
j
NN
=
=
å
ij
d
D
T
E
T
S
N
ZS
N
1
S
B
i
S
A
2
C
1
C
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
控制域A控制域B
控制器
交换机
S1
C2C1
控制域A
控制域B
S1
C2
C1
a.迁移前
b.迁移后
{
}
123
,,,,
N
SSSSS
=
L
1
S
N
S
n
i
i
i
p
(
)
1,2,,
K
Rpkn
a
==
L
K
R
K
R
a
h
T
h
T
K
R
0
K
R
Cj
h
T
K
R
{
}
1234
,,,
SCCCC
=
n
m
n
m
(
)
,
rsa
(
)
,
rsa
(
)
(
)
(
)
(
)
O r d i n a r y switch
,
Important switch
1,,
j
j
Si
Si
C
Si
K
Si
C
L
L
rsa
L
hR
L
kLn
ì
ï
ï
ï
=
í
ï
+
ï
ï
î
=
å
å
j
S
a
Si
L
j
Si
C
L
å
j
K
R
K
R
h
h
(
)
,
rsa
{
}
s
(
)
,
Qsa
S
(
)
,
aij
Q
Q
Q
(
)
(
)
(
)
,
,
,
a,=argmax,argmin
ZSj
ij
ij
aij
SSCC
ijQsaab
ÎÎ
æö
æö
ç÷
Ç
ç÷
ç÷
ç÷
èø
èø
å
S
(
)
,
aij
Q
S
N
Q
(
)
,
aij
Q
Q
(
)
,
aij
Q
(
)
,
Qsa
mn
´
Q
Q
{
}
c
{
}
1234
,,,
xXXXX
lllll
=
1
X
l
x
Q
(
)
,
Qsa
(
)
(
)
(
)
,,,
max
a
QsarsaQsa
g
¢
¢¢
=+
(
)
(
)
(
)
(
)
(
)
,,
,,,
max
a
QsaQsa
rsaQsaQsa
lg
¢
=
éù
¢¢
++-
êú
ëû
S
a
s
¢
C
N
a
¢
S
g
[
]
0,1
g
g
l
Q
Q
S
ij
f
a
(
)
,
Rsa
ss
¢
Î
a
¢
s
¢
(
)
,
Qsa
(
)
‘
”
max,
a
Qsa
g
h
R
i
Q
[
]
,
mn
Qsa
´
m
n
K
R
Q
Q
Q
n
Q
j
dijkstra
S
(
)
,
rsa
K
hR
(
)
,
rsa
Q
S
a
Q
Q
ij
b
Q
Q
Q
Q
Q
S
S
¢
S
0
1
ij
b
i
S
j
c
ij
b
i
S
j
C
CS
N
Ci
i
S
zi
S
{
}
,
sc
S
N
C
N
ij
b
CS
N
CZS
N
CS
L
j
L
i
S
,
ij
CSij
SSCC
Nb
ÎÎ
=
å
{
}
s
,
zjj
CZSij
SSCC
Nb
ÎÎ
=
å
i
CSijij
SS
Lbf
Î
=
å
1
j
CS
CC
LL
m
Î
=
å
CS
N
CZS
N
CS
L
(
)
1
1
:min
m
CS
j
objectLL
m
=
–
å
.
St
(
)
(
)
minmax
ijD
dT
£
E
eT
<