论文阅读六：软件定义网络中基于Q-学习的负载均衡算法

名词解释：

Q-learning Load Balance, QLLB：基于Q-学习的负载均衡算法

Link Layer Discovery Protocol, LLDP：链路层发现协议

摘要：针对SDN的负载均衡问题，为使网络的资源分配更加合理，防止网络拥塞，设计了一种基于 Q-学习的负载均衡( Q-learning Load Balance，QLLB) 算法，可根据网络环境自行作出决策，避免网络拥塞，实现网络资源的合理分配。与最短路径算法Dijkstra、蚁群算法进行的性能对比结果表明，QLLB 算法有效实现了负载均衡，使得各个链路的带宽利用率更加平均，吞吐量分别提升了约 8% 和 2% ，可有效提升网络性能。

0 引言

针对以上问题，文章将Q-学习引进到负载均衡算法中，提出了基于Q-学习的负载均衡QLLB算法，能够实现自主对网络环境进行学习，综合考虑时延和带宽等因素做出决策，避免某一链路流量过多导致负载失衡，从而提高网络的服务质量。

1 系统模型

将控制器内部划分为链路感知模块、链路测试模块、Q-学习模块以及流表下发模块。

链路感知模块：获取网络拓扑和链路信息，通过下发LLDP报文和广播包给交换机之后将控制器需要的信息回传给控制器，保证信息的及时性，使用定时触发或当网络拓扑信息发生改变时再次触发。LLDP包和广播包含了交换机的相关信息和源/目的端口等信息。

链路测量模块：针对网络的服务质量要求对关键的性能指标参数如带宽和时延进行测量，然后进行预处理，最后将这些数据作为强化学习模块的输入；用互信息法确定时延。链路测量模块内部分为带宽测量模块和时延测量模块。

假设整个网络共有n条链路，表示为： $\small l=\left \{ l_{1},l_{2},...,l_{n-1} \right \}$ 。设某一条链路 $\small l_{j}$ 两端的交换机为 $\small S_{1}$ 、 $\small S_{2}$ ，SDN控制器通过将一个包含LLDP的数据包发送到 $\small S_{1}$ ，随后转发到 $\small S_{2}$ ，交换机通过记录发送数据包的时间戳与接收来自 $\small S_{2}$ 的Packet-in报文记录的时间戳可获得 $\small S_{1}$ 转发报文到 $\small S_{2}$ 的时延 $\small D_{1}$ 。同理可获得 $\small S_{2}$ 转发报文到 $\small S_{1}$ 的时延 $\small D_{2}$ 。由于 $\small D_{1}$ 和 $\small D_{2}$ 包含了控制器和交换机之间的时延，需要通过echo报文测试得到控制器与交换机 $\small S_{1}$ 、 $\small S_{2}$ 之间的时延，分别记录为 $\small D^{'}_{1}$ 和 $\small D^{'}_{2}$ 。最终获得链路 $\small l_{j}$ 的时延，计算公式如下：

$\small D_{l_{j}}=\frac{1}{2}\left ( D_{1}+D_{2}-D^{'}_{1}-D^{'}_{2} \right )$

每条链路的已用带宽可以根据统计一段时间间隔 $\small T$ 内端口接收到的数据字节总数 $\small b_{rx}$ 以及传输的字节总数 $\small b_{tx}$ ，则链路 $\small l_{j}$ 的已用带宽计算公式如下：

$\small B_{l_{j}}^{used}=\frac{b_{rx}+b_{tx}}{T}$

因此假设 $\small B$ 为链路的总带宽，链路 $\small l_{j}$ 的可用带宽为：

$\small B_{l_{j}}=B-B_{l_{j}}^{used}$

Q-学习模块：根据交换机传输报文的有关统计特性，采用Q-学习的算法计算得到转发的最佳路径: 首先获取链路测量模块所测得的链路带宽和时延作为输入，采用QLLB 算法学习网络的各条链路的实时状况，并且根据交换机接收的报文的源地址和目的地址求得一条最佳转发路径，最后结合链路感知模块所获得的网络拓扑，制定交换机的流表。

流表下发模块：根据Q-学习模块输出的转发路径以及链路感知模获取的网络拓扑确定每个交换机的转发端口，并且和路由信息封装成流表，然后将相应的流表下发给与之对应的交换机。

2 QLLB负载均衡算法设计

Q-学习算法：强化学习是一类算法，不断地尝试完全随机的操作，每一个操作都会得到一个反馈，通过反馈来调整下一跳，最后得到最优解决方案。Q-学习是一种无模型的离策略求Q值的算法，而且Q值表是迭代的，更适合于分析概率随机的数据。

QLLB算法原理：使用对数值迭代的方式求出最优解。一个新的数据包处于有限的马尔科夫过程的网络环境中，当交换机选择下一跳的交换机时，网络环境的状态会发生改变，此时该策略会得到当前网络实时情况的一个反馈值，即奖励函数值。反馈值越大，下一次执行该策略的概率就越大。在 $\small t$ 时刻，交换机选择下一跳到达的交换机，数据包从 $\small S_{t}$ 传到 $\small S_{t+1}$ ，系统给出反馈值表示为:

$\small r\left ( t \right )=r\left ( S_{t},S_{t+1} \right )$

其中 $\small S_{t}$ 为当前数据包所在的交换机， $\small S_{t+1}$ 表示数据包下一跳到达的交换机。

Q-学习算法使用数值迭代求得最优值函数，Q矩阵的推导公式如下：

$\small Q_{k+1}^{*}\left ( S,{S}' \right ) \leftarrow \sum_{{S}'}^{}P\left ( {S}' | S\right ) \ \left [ r\left ( S,{S}' \right ) +\gamma max \ Q_{k}^{*}\left ( S,{S}' \right )\right ]$

其中 $\small {S}'$ 为下一状态的交换机， $\small \gamma$ 是折扣因子， $\small Q$ 表示的是在数据包到达 $\small S$ 时能够获得的最大期望收益， $\small r\left ( S,{S}' \right )$ 是立即获得的收益， $\small \gamma max \ Q_{k}^{*}\left ( S,{S}' \right )$ 是未来折扣收益。折扣因子趋于0说明决策考虑更多的是当前行为的奖励值，趋近1说明下一步行为的奖励值占比比较大。

QLLB算法的基本流程如下：其中Q矩阵为二维数组，行参数表示当前状态，列参数表示下一个状态，数组里的值表示当前状态到下一状态的Q值。当Q矩阵里的Q值趋于不变时，Q矩阵收敛。

QLLB算法参数：以带宽利用率、吞吐率、吞吐量和时延作为主要参数。文章设置的奖励函数采用链路带宽和时延结合的方式，每当选择到一条可用带宽大、时延小的链路时，其奖励值就会增大，下一次选择链路的时候就会优先选择奖励值大的，从而形成正反馈，因此可以优化吞吐量和流量分配。奖励函数公式如下：

$\small r=\left [ \alpha \cdot B_{l_{j}}^{{}'} +\beta \cdot \left ( 1- D_{l_{j}}^{{}'} \right )\right ]\cdot \zeta$

其中 $\small B_{l_{j}}^{{}'},D_{l_{j}}^{{}'}$ 分别表示链路 $\small j$ 归一化后的可用带宽和时延； $\small \alpha$ 为带宽权重系数， $\small \beta$ 为时延权重系数， $\small \alpha$ 和 $\small \beta$ 和为1； $\small \zeta$ 为归一化后的放大倍数。因为时延和奖励值负相关，所以归一化后用1减去值得到：

$\small r=\left [ \alpha \cdot \frac{B_{l_{j}}-B_{l_{j}min} }{B_{l_{j}max}-B_{l_{j}min}}+\beta \cdot \left ( 1- \frac{D_{l_{j}}- D_{l_{j}min}}{D_{l_{j}max}-D_{l_{j}min}}\right )\right ]\cdot \zeta$