基于数学模型的网络优化方法研究赵鹏 通信一团技术室摘 要 为了提高网络链路的利用率，解决网络传输中的最大流问题，该文利用建立数学模型的方法来求解网络的传输路径，研究了基于路径的网络优化方法。

该方法能够极大地提高网络的链路利用率，从而降低网络的拥塞，使得网络的性能得到较大改善。

关键词 网络优化 最大流 数学模型1 引言随着网络技术的进步和人们对多媒体综合业务需求，传统的数据网络逐渐转向多媒体网络，在这过程中，除了相关服务以外，我们还面临许多极具战性的网络设计和优化问题。

网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着网络优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。

在计算机网络优化设计中，各条链路的容量分配和各节点间的路由选择是两个重要问题。

在给定网络拓扑结构和各节点间传输流量的条件下，如何确定各条链路的容量大小和选择各节点间的最佳路由，使整个网络成本费用最低并能满足规定的性能指标呢？许多网络优化的文献，研究针对CDMA 网络、GPRS 网络、GSM 网络、PHS 网络等具体网络在投入运行后，对网络进行参数采集、数据分析，找出影响网络质量的原因，通过技术手段或参数调整使网络达到最佳运行状态，涉及到交换网络技术、无线参数、小区参数配置、信令和设备技术等方面。

本文针对目前许多网络传输链路和网络设备没有得到充分利用，从而影响网络性能的问题，利用网络优化方法从理论上进行分析，研究了用于提高网络链路利用率的基于路径的网络优化方法，该方法能够充分地利用网络链路进行流量传输，从而改善网络的整体性能。

2 网络优化理论很多情况下可以将网络优化问题转化成数学问题进行研究和分析。

从根本上讲，优化问题包含三个基本要素：决策变量集合或向量：nR x ∈（本文，x 代表在一条或多条路径上的流量） 目标函数R R x f n→:)(一组约束条件g(x)和h(x)，用来定义x 的范围。

解决优化问题实际上就是找出一个点x*，使得f(x)最大化或最小化。

典型的网络优化问题包含找出一组路由和该路由上的流量值以便达到最大或最小化目标函数的目的。

目标函数可以代表最大链路利用率、平均延迟或其他指标。

基于路径的问题首先要计算出网络流可能流经的路径，要最大限度的利用网络链路，同时路径上的流量不能超过链路容量。

对于基于路径的网络优化问题可以简单表示成： max f(x)s.t.∑∈=Pp pb xA j i u xPj i ij p∈∀≤∑∈),( ),(0≥xx p 为路径p 上的数据流，b 为要传输的流量，u ij 为弧（i,j ）上的容量，A 代表网络中弧的集合，P 为源点——目的点之间路径的集合。

3 基于数学模型的网络优化方法3.1 最大流问题的研究在现实网络中，如图1所示的网络结构是很常见的。

当从源点向目的点传输流量时，如何充分利用整个网络资源，达到要求的服务质量是我们要考虑的事情。

传统的IP 网络是通过路由算法找到一条按某种算法达到的最优路径，如，RIP ，OSPF 等。

图1 进行研究的网络拓扑结构图中每条弧上的数字代表了相应链路的可用链路容量，单位为Mbps 。

从路由器1到路由器有多条路径：path1：1→2→3→6；path2：1→2→5→6；path3：1→4→5→6； path4：1→4→3→6；path5：1→2→3→5→6；⋅⋅⋅⋅⋅⋅我们要研究的是在多条路径的条件下，通过分析选取合适路径，使得所有源点与目的点之间的流量达到最大。

首先，建立网络的数学模型。

令g(V ，A)代表网络，V 代表网络中的节点集合，A 代表链路集合，s k 代表第k 条路径的源点，t k 代表第k 条路径的目的点，f k 代表第k 条路径的传输流量，K 为所有路径的编号集合，x ij 为弧（i ，j ）上的流量，u ij 为弧（i ，j ）的容量上界。

运用关联矩阵b Nx =进行分析，其中，向量b k = {b i k }，⎪⎩⎪⎨⎧==+=其他如果果 0t i -s i 如 k k k k ki f f b那么，对于我们要研究的最大流问题可以用数学模型描述为：∑∈K k k f max （1）s.t. K k b Nx kk∈∀= （2）∑∈∈∀≤Kk ij k ijA j i u x),( （3）A j i K k x k ij ∈∀∈∀≥),( , 0 （4）该情况下的最大流问题一般来讲是一种大规模线性规划问题，可以直接采用线性规划、整数规划等方法求解。

图1中假定网络有两个源点和目的点，第一条源点——目的点从路由器1到路由器6，第二条源点——目的点从路由器2到路由器5。

网络的关联矩阵为： N= ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----------100100000011001100000110001010001110010000000111010000000011相应的两个源点和目的点的b 为T f f b ]- 0 0 0 0 [111=，T f f b ]0 - 0 0 0[222=，其中，T 表示转置，0,21≥f f 。

求解公式（1）、（2）、（3）、（4）所确定的线性规划。

则Nx = b 可表示为：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----------ii i i ii i ii i i if f x x x x x x x x x x 000010010000001100110000011000101000111001000000011101000000001156454336352524231412 其中，i=1，2。

对于第一条源点——目的点的1ij x 记为x ij ，将第二条源点——目的点的2ij x 记为y ij 。

经过简化，得到下面的线性规划：)max (21f f +s.t. x 12+x 14=f 1；x 23+x 24+x 25-x 12=0；1 2 3 4 5 6 x 12 x 14 x 23 x 24 x 25 x 35 x 36 x 43 x 45 x 56x 35+x 36-x 23-x 43=0； -x 14-x 24+x 43+x 45=0； -x 45-x 25-x 35+x 56=0； -x 36-x 56=-f 1； y 12+y 14=0；y 23+y 24+y 25-y 12=f 2； y 35+y 36-y 23-y 43=0； -y 14-y 24+y 43+y 45=0； -y 45-y 25-y 35+y 56=-f 2； -y 36-y 56=0； x 12+y 12<=2； x 14+y 14<=7； x 23+y 23<=4； x 24+y 24<=4； x 25+y 25<=3； x 35+y 35<=1； x 36+y 36<=2； x 43+y 43<=1； x 45+y 45<=5； x 56+y 56<=4； x ij ，y ij >=0。

得到：Mbps f f 11)max (21=+；f 1=3Mbps ；f 2=8Mbps ；x 12=2Mbps ；x 14=1Mbps ；x 23=2Mbps ；x 36=2Mbps ；x 45=1Mbps ；x 56=1Mbps ； y 23=1Mbps ；y 24=4Mbps ；y 25=3Mbps ；y 35=1Mbps ；y 45=4Mbps ；其余为0。

从上面的求解结果可以看出，对于图1中的网络： 从路由器1到路由器6的路径为：x 12＋x 23＋x 36即，1→2→3→6，带宽为2Mbps ； x 14＋x 45＋x 56即，1→4→5→6，带宽为1Mbps 。

从路由器2到路由器5的路径为： y 23＋y 35即，2→3→5，带宽为1Mbps ； y 24＋y 45即，2→4→5，带宽为4Mbps ； y 25即，2→5，带宽为3Mbps 。

由此可以看出，从路由器1到路由器6链路带宽最高可达3Mbps ，从路由器2到路由器5链路带宽最高可达8Mbps 。

在此基础上采用MPLS 的ER-LSP 技术可以将流量安排到各条计算出的路径上。

图2 最大流问题链路利用的结果分析如果利用求解网络中两点间最短路径的Dijkstra 算法，求解最短路径优先协议下，在相同网络中的两个同样的传输，效果会怎样呢？同样先对问题进行数学描述，然后求解计算网络的最短路径，在此不再进行详细说明。

通过计算得到：从路由器1到路由器6的最短路径为1→4→5→6，带宽为4Mbps ；从路由器2到路由器5的最短路径为2→5，带宽为3Mbps 。

利用Dijkstra 算法计算得到的两条路径的带宽总共为7Mbps ，而利用上述算法计算得到的路径带宽总共为11Mbps ，明显由于7Mbps 。

这是因为OSPF 协议仅仅使用了一条最优路径，而上述算法中利用MPLS 协议可以充分利用网络的所有可能的路径，从而使得网络的链路资源得到最大的利用率。

图3为两种算法的链路利用率对比；图中蓝色的实线代表本文算法求出的链路带宽，粉红色的虚线为Dijkstra 算法求得的链路带宽，绿色的波浪线为链路可用带宽；x 轴依次代表x12，x14，x23，x24，x25，x35，x36，x43，x45，x56；y 轴代表带宽（单位：Mbps ）。

由图中可以看出，使用本文所用的算法能够使各条链路得到充分利用，极大的提高了链路利用率，从而能够减小网络的拥塞现象，改善网络的性能。

而Dijkstra 算法使得部分链路未得到充分利用。

1234567812345678910图3 两种算法链路利用率对比在目前网络信息高度膨胀，网络传输过程中出现大量的拥塞情况而言，本文的算法能够保证网络的链路得到充分利用，从而提高网络的整体性能，使网络得到优化。

然而该算法也存在一个明显的弱点，即将数据流过于分散到各条链路上。

由于分流就不可避免地造成分组的失序，这对音频和视频流的传输是不合适的。

对于音频和视频流的传输应尽可能的减少分流，在传输某一特定流时应该充分利用所使用的链路。

3.2 流量集中传输对源点——目的点之间的路径进行选择，从而实现流量集中传输。

方法为：（1）将用上述算法求出的路径按照带宽从大到小排列为p 1，p 2，... ，p n （假定共有n 条路径）；（2）判断如果p i带宽大于流量时，路径p i能够满足对流量的传输要求，则选择p i；（3）如果p i的链路带宽小于流量时，选择该路径作为流量传输的路径之一；（4）再对路径p i＋1进行判断，...，直到能够满足流量的传输需求。