0 引言

开放式最短路径优先(Open Shortest Path First, OSPF)协议^[1-3]作为内部网关协议，采用层次化路由，因其收敛速度快，工程较为成熟，在大型的电力通信网络中应用广泛^[4-6]。同时OSPF将整个网络划分成若干区域，主干区域都会与其他区域交互大量的各种信息，其中包括调度信息、路由信息、用户的用电信息等^[7-8]。由于OSPF协议根据每条链路的权重，采用最短路径(Dijkstra)算法，因此会出现多个路由器同时选择一条链路权重较好的链路，而当这些路由器选择了这条链路并路由时，则会导致这条链路的流量过大；又由于每条链路的带宽是固定的，故在该链路上会产生拥塞，甚至丢包。电力通信网中流量均衡是提高电力通信网服务质量的前提，也是提高电力通信网稳定性的必要因素，因此本文致力于解决在电力通信网中的流量不均衡问题。

在OSPF协议上，Fortz等^[9]提出如何确定权重向量的问题，使得在网络流量为一个确定的值时，区域内的链路不会出现流量过载，而且此时的网络性能最好, 并证明这是一个完全的NP问题。Su等^[10]通过在流量矩阵中人为设定链路权值从而达到流量均衡，在这个基础上，Sridharan等^[11]提出基于链路剩余容量的启发式算法和动态获得权重的启发式路由算法；但是并不能很好地解决边界路由器上的流量不均衡问题，而且这些权值都需要人为预先设定。虽然文献[12-13]致力于利用已知的流量需求和带宽，设置边界路由器的残桩域的门限，动态地选择较好的一个边界路由器作为这个区域的边界路由器；这样既可以很好地避免链路拥塞，又可以保证不频繁切换区域边界路由器(Area Border Route, ABR)，但是没有考虑流量分流的问题。

目前在电力通信网中存在以下两个关键问题：

1) 区域边界流量不均衡。在电力通信网中，边界路由器负责区域间流量的发送。在OSPF协议中，一般按照带宽作为衡量权重，使得边界路由器流量不均衡，导致某些区域边界路由器(ABR)成为瓶颈。在可靠的电力通信网中，一般会采用更换路由器的方式，这样下一个路由器又会由于负载过重而崩溃。在不止一个边界路由器的情况下，也会出现频繁切换ABR，导致整个电力通信网络不稳定。

2) 电力通信网内部流量不均衡。在一个区域内部，由于某条链路的链路权值小，导致频繁地使用这条链路，致使链路两端的路由器负载过重，同时还会存在一些节点上没有负载的情况。整个区域或者网络会因为这种流量的分配不均衡导致网络拥塞或者是丢包，需要频繁地切换选择新的路径来维持整个网络的运行。

本文为很好地解决这两个问题提出“两级优化”算法，改进了传统的OSPF协议，定义为TSO-OSPF(Two-Step Optimized OSPF)协议。在TSO-OSPF协议中，本文的两级优化算法指的是先解决在每个区域内的流量不均衡问题，再考虑解决边界路由器的流量不均衡问题。首先，在解决每个区域内的流量不均衡问题时，本文采用最大流最小化的思想，考虑带宽利用率和时延的综合因素给整个网络带来的影响，将它们加入到链路权值中进行计算，将流量按照新的权值进行分流，以保证区域内的负载均衡。其次，本文考虑解决边界路由器的流量不均衡问题。由于边界路由器承担着连接区域的流量的分配，所以本文按照新定义的权值和区域内流量的分布，给边界路由器动态的分配流量，并通过实验部分验证采用TSO-OSPF协议可以使整个网络达到高效负载均衡。

1 模型与问题 1.1 OSPF流量模型

在OSPF区域中，所有的路由器被称之为节点。如图 1，整个电力通信网被抽象成图G(N, L)，其中整个网络有N个节点，L条链路。从节点i到节点j有一条链路为L_ij，其中e_ij代表流经此链路的流量。从节点j流经节点i的流量，即由节点j进入节点i的流量$E_{ji}^{{\rm{in}}} = \sum {{e_{ji}}} $。从节点i流出至节点k的流量为$E_{ik}^{{\rm{out}}} = \sum {{e_{ik}}} $。节点i和节点j之间的链路代价记为C_ij，那么，在这种情况下节点i在流量q下所能获得流量记为U_i(q)。同时考虑到在链路上有丢包现象，因此除了进出的流量之外，还会损失一部分流量为E_i^loss，由i节点流出的流量所到达的节点的集合为M_i。

以一个区域的其中一个节点i为例，本文发现一个固有的性质：流入i的总流量和i节点本身产生的流量的总和等于从i节点流出的流量和E_ij^loss的总和。对于每个节点有这样的性质，对于整个区域这个性质依然成立，在全电力通信网中这个性质也依然成立。这个性质可以用在流量均衡的问题的解决上。从广义上说，流量均衡指的是每个节点不会有过量的流量，也不会有过小的流量，而且在每个节点所要消耗的代价是均衡的，因此这个性质是使电力通信网流量均衡的标准。

1.2 OSPF问题描述

在划分区域的OSPF区域中，如图 2所示，会出现以下两种情况，这两种情况的出现会严重影响整个电力通信网的可靠性和稳定性，同时也会使电力通信网的总体性能下降。

情况1  选定ABR1和ABR2作为区域M1的暂定边界路由器，ABR6和ABR7作为区域M3的暂定边界路由器，假设ABR7 ↔ ABR1的流量需求是50 Mb/s，ABR6 ↔ ABR1的流量需求是100 Mb/s，ABR7 ↔ ABR2的流量需求是200 Mb/s，ABR6 ↔ ABR2的流量需求是100 Mb/s。在M1区域，传统的OSPF协议根据带宽这个链路权值会选择ABR1路由器为边界路由器。但是，当ABR6 ↔ ABR1和ABR7 ↔ ABR1实际流量在增大时，ABR1将会不堪重负，因带宽不足导致丢包。此时如果选择ABR2作为最终的边界路由器，不会因为带宽不足而丢包；但是如果ABR2后面有且仅有一个路由器承担下一跳(详见情况2) 则又会因为路由器的带宽容量满足不了实际的流量而丢包。所以在动态分配边界路由器时应考虑4个因素：带宽利用率、链路质量、流量进出的均衡以及时延。

情况2  如图 2所示，在M2区域中，选定边界路由器ABR5，同时ABR3是连通另一个区域的边界路由器，假设ABR5→ R1的流量需求是80 Mb/s，ABR3→ R1的流量需求是160 Mb/s，但是R1的流量容量是160 Mb/s。当ABR6和ABR3产生流量，并通过R1路由给下一条进行路由的情况下，R1会因为带宽不足，160 Mb/s的带宽无法承担以180 Mb/s的流量速度进行路由，从而发生丢包现象。通常研究会认为这是有关最大流的问题，一般解决方法是多协议标签交换(Multi-Protocol Label Switching，MPLS)流量工程将最大流分解，在源和目的节点之间预留出许多微分支，如果遇到最大流，则把流量往微分支上分解；但是这并不适应流量情况变化快的网络，即当流量不稳定，突然增大时，微分支的链路将不能满足流量需求，且微分支的链路质量不一定好，这样会大大增加丢包率，增加时延。

针对这两种情况，本文最终要达到在时延和丢包率比较小的情况下，整个电力通信网流量均衡的效果。

2 算法描述 2.1 解决思路

为改进情况1和情况2，本文提出了基于“两级优化”算法的TSO-OSPF协议。本研究发现两种情况下，针对区域内部路由器或者是边界路由器都存在流量不均衡问题，因此，在TSO-OSPF协议中，本文先统一解决区域内所有链路的流量不均衡问题。首先，将其抽象成一个最大流的最小化问题，这样先保证没有本质的“内忧”；其次，最大流的最小化的约束条件发生变化，传统的OSPF遵循的约束代价是带宽的大小，即考虑到带宽的代价，本文需要考虑的代价是综合代价。其次考虑解决边界路由器的动态分配选择的问题，这个问题也将会考虑最大流的最小化问题以及传输代价和带宽利用率等因素的影响。

2.2 方法描述

在TSO-OSPF协议中，要使得整个M_i区域内的流量达到负载均衡，那么首先要考虑的是区域内最大流的问题，之前会用保留微分支的方法来解决负载不均衡问题，也只适用于每个区域内部。现在本文整体考虑流量的问题。采用微分支的目的在于将最大流分流，减小最大的流量，使得流量均衡，但分支只能减小流量，不能准确地说明最大流的分流是有效的，因此本文使用“最大流最小化”，保证了分流的有效性。同时在解决“最大流最小化”这个问题所利用的约束条件和权值本文给予了新的调整。考虑到一个简化分析，如图 3所示。

对于每一个节点都呈图 3的属性，由于丢包损失的流量远小于其他的流量，因此这里不考虑由于丢包损失的流量。根据1.1节中提到的流量性质，针对i节点，所有的进入i节点的流量加上自身产生的流量应等于最终从i节点流出的流量，即：

$ \sum {E_{ij}^{{\rm{in}}}} + {E_i} = E_{jk}^{{\rm{out}}}{\rm{ + }}E_{ij}^{{\rm{loss}}} $

在流量为q的前提下目标函数可表示为：

$ {U_{{\rm{area}}}}\left( q \right) = \mathop {\max }\limits_{i < N} \sum\limits_{j \in {M_i}}^{} {E_{ij}^{{\rm{out}}}} $

式子表示在M_i区域，先找到有通过流量最大的节点j，将这个节点的流最小化，从而使整个区域负载均衡。

目标：最小化U_area(q)。

初始条件：$ \sum\limits_{k \in {M_i}} {E_{jk}^{{\rm{out}}}} > 0, \forall i \in N, \forall j \in {M_i};\sum\limits_{j \in {M_i}} {E_{ij}^{{\rm{in}}} + {E_i}} = \sum\limits_{k \in {M_i}} {E_{jk}^{{\rm{out}}}{\rm{ + }}E_{ij}^{{\rm{loss}}}}, \forall i \in N, \forall j \in {M_i}$。其中决策变量为e_ij。

但是在TSO-OSPF协议中，本文还考虑一个约束条件U′_area(q)函数。在均衡流量时同时考虑U′_area(q)的影响，换句话说，本文使用了最大流最小化的思想，但是又不完全按照节点的流量来分流，而是在考虑达到min(U′_area(q))的最优解。$W_{i(q)}^j = \alpha /B(i, j) + \beta *T(i, j)$，其中链路利用率记为B(i, j)，记录i到j的传输时延记为T(i, j)，它是包长除以带宽得到的结果，W_i(q)^j指的是每条链路的权重。在W_i(q)^j下，为达到流量的均衡，最小化U′_area(q)值，这样每个节点到最后都会达到负载均衡状态。

本文将一个NP问题转换成了有初始条件、约束条件和最终目标的一个线性规划问题。按照这种初始条件下，按照U_area(q)均衡流量同时考虑U′_area(q)。其中TSO-OSPF协议的参数的设置是根据具体的需求可以调整，为了达到整体最优的效果，本文进行多次的实验确定系数，最终确定$W_{i(q)}^j = \alpha /B(i, j) + \beta *T(i, j)$。这时U′_area(q)的值从整体来说最小效益最高。这样在TSO-OSPF协议中，每个节点的流量是动态均衡的，这个均衡不止是流量的均衡，而是考虑到当前的带宽利用率以及时延的情况下，综合均衡节点的流量。

2.3 算法描述

在2.2节中本文抽象出来一个最小化区域中最大流的方法同时利用约束条件得到较好的结果。除此之外，TSO-OSPF协议需要考虑的是一个全区最优的解。本文抽象出来了一个最大流最小化的新权值的问题，从而保证流量均衡的算法。这个算法是全局适用的，但是还要考虑OSPF区域划分的情况。如果用上述2.2节的算法进行均衡整体的流量，那么会带来的问题是传统OSPF大多面临的问题:交换信息过于庞大，所以在TSO-OSPF协议中，应该继续考虑边界节点的负载均衡。

1) 从一个节点i出发，去遍历此节点的所有邻居节点集合{Q_i}，根据当前的已知因素计算节点i到邻居集合中每个节点的权值$W_{i(q)}^{{Q_{ij}}}$，不明确的$W_{i(q)}^{{Q_{ij}}}$是无穷大。比较$W_{i(q)}^{{Q_{ij}}}$并排序，从最优的链路权值开始，结合目前此节点的流量试图加入流量过大的节点的部分流量，并更新这个节点的流量。

2) 假设目前M_i区域的边界节点集合是{ABR_{area_Mi}}, 观测该集合中的节点的流量，并记录彼此之间的连接关系，同时测试每个接节点与其将要连接区域的连通性。将不连通的接节点删除。先找出边界节点中哪些节点的流量偏重，并且计算所有边界节点的$W_{i(q)}^{{Q_{ij}}}$。根据这个值并结合1) 中对区域内对流量的分配，调整链路的同时，找到最大的U′_area(q)，结合当前连通区域的边界节点的负载分流。当选择了U′_area(q)最大的节点，就将新增的流量加入到负载较小的节点上，按照这个最新的流量结合重新分配流量并更新U′_area(q)。

3) 在其余节点中，若流量有超过边界流量阈值的，按照2.2节的情况动态地处理。

① 若在{A_{area_t}}和{ABR_{area_i}}集合中只有极少量的节点流量负载过重，而且它们是这些节点中的核心节点，那么只能采用2) 中的核心算法，将其负载的流量均衡化。

② 若在{A_{area_i}}的{ABR_{area_i}}集合中只有极少数的边界路由器，例如只有一个或两个边界路由器，且有一个节点处于流量负载过重，这时需要尽量地调节两个候选的边界路由器作为边界路由器，更新U′_area(q)，动态地同时让两个边界路由器承担流量，按照目前的U′_area(q)和$W_{i(q)}^{{Q_{ij}}}$分配流量比例，并且选好边界路由器之后，就把这部分流量纳入到计算中，循环步骤1)~3)。

在上面算法的基础上借助OPNET和Matlab完成仿真实验。

3 实验 3.1 实验设置

本实验的仿真平台是基于Matlab和OPNET Modeler 14.5，并在此仿真平台上进行区域划分和TSO-OSPF及OSPF路由协议的仿真和计算。拓扑规模设定为100 km×100 km大小，取用芜湖市电力通信网作为网络拓扑，其中包括了44台路由器和54条有线链路，并分成了5层，每一层就是OSPF的一个区域。路由器间节点链接设置为100BaseT局域网链路，默认每个节点为3个100Base_TLAN逻辑子网的出口。本文在带宽为50 000 bit/s的情况下，取α=1, β=1的情况下对电力通信网路径(节点39至节点18) 的时延、流量变化和丢包率进行仿真。

3.2 实验结果及分析

从图 4可以看出，由于TSO-OSPF采用两级优化，动态调整区域内和区域间的流量，所以会比传统的OSPF的时延更小。

图 5描述了在既定路径上流量的变化趋势。可以看出当流量到达不同节点时，虚线表示的流量忽大忽小，很不均衡。TSO-OSPF由于采用了最大流的分流技术，将其转化成一个在多项式可解的问题，将最大流减小，因此，流出的流量比较均衡，有利于整个系统的稳定。

如图 6所示，在330 s时既定路径经过的节点13流量达到峰值，此时传统的OSPF丢包率也达到了峰值，即流量的突然增大的节点，丢包率也急剧增大。TSO-OSPF协议由于采用不同的可选路径，尽量避免了流量的堆积，这样在整个的过程中丢包率较传统的OSPF协议减小了10%左右。

表 1展示了TSO-OSPF协议和OSPF协议下，从既定路径(节点39到节点18) 的数据分析。从表 1中可以看出，在代价上由于传统的OSPF采用最短路径，所以路径代价比较小，但是在其他指标方面TSO-OSPF协议表现出了良好的性能。从流量的方差上看，显然TSO-OSPF协议比较稳定，结合图7可以看到流量是均衡的，而且还减小了时延，这样的变化会使得在小的丢包率的情况下，信息传递更快速。

4 结语

为了均衡电力通信网的流量，避免由于流量不均造成的路由器负载过重的现象，同时为了提高整个网络的效率，包括吞吐率、时延和丢包率3个方面，本文提出了两级优化算法的TSO-OSPF协议，将一个NP完全问题转化成在多项式时间内可解的算法，并优化配置了边界路由器。经实验与传统的OSPF协议进行对比，获得了很好的效果。