基于鲁棒性的链路权重规划算法

２０１４年第１期　计算机与现代化　ＪＩＳＵＡＮＪＩ　ＹＵ　ＸＩＡＮＤＡＩＨＵＡ　总第２２１期　文章编号：１００６－２４７５（２０１４）０１－００７１－０６　基于鲁棒性的链路权重规划算法　罗宇，吕光宏　（四川大学计算机（软件）学院，四川成都６１００６５）　摘要：在ＩＰ网络中，链路权重规划是流量工程中的重要问题。为了优化网络流量并实现负载均衡，针对业务量矩阵的不　确定性，依据鲁棒性理论提出一个链路权重规划的ＭＩＰ模型。该模型使用ｒ模型描述业务量矩阵的不确定集，通过表示　扰动程度的参数ｒ实现了对鲁棒性的调节，在此基础上求得不确定集中最差情况下的最优解。实验结果表明，与传统的　链路权重规划方法以及新出现的ＭＲＣ规划模型相比较，该算法可降低最大链路利用率，分别达到了４０％和２０％。　关键词：不确定流量矩阵；鲁棒性；权重规划；ＭＩＰ模型；Ｆ模型　中图分类号：ＴＰ３９３　文献标识码：Ａ　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６－２４７５．２０１４．０１．０１７　Ｌｉｎｋ　Ｗｅｉｇｈｔ　Ｐｒｏｇｒａｍｍｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｒｏｂｕｓｔｎｅｓｓ　ＬＵＯ　Ｙｕ，ＬＹＵ　Ｇｕａｎｇ—ｈｏｎｇ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ（Ｓｏｆｔｗａｒｅ），Ｓｉｃｈｕａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ　６１００６５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｆｏｒ　ＩＰ　ｎｅｔｗｏｒｋｓ，ｔｈｅ　ｌｉｎｋ　ｗｅｉｇｈｔ　ｐｌａｎｎｉｎｇ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｉｓｓｕｅ　ｏｆ　ｔｒａｆｆｉｃ　ｅｎｇｉｎｅｅｒｉｎｇ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｔｒａｆｆｉｃ　ａｎｄ　ａｃｈｉｅｖｅ　ｌｏａｄ　ｂａｌａｎｃｉｎｇ　ａｎｄ　ａｇａｉｎｓｔ　ｔｈｅ　ｕｎｋｎｏｗｎ　ｔｒａｆｆｉｃ　ｍａｔｉｒｘ，ｔｈｉｓ　ａｒｔｉｃｌｅ　ｐｒｏｐｏｓｅｓ　ａ　ｌｉｎｋ　ｗｅｉｇｈｔ　ｐｒｏｇｒａｍｍｉｎｇ　ＭＩＰ　ｍｏｄｅｌ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒｏｂｕｓｔｎｅｓｓ　ｔｈｅｏｒｙ．Ｔｈｉｓ　ｍｏｄｅｌ　ａｐｐｌｉｅｓ　ｔｈｅ　Ｆｍｏｄｅｌ　ｔｏ　ｄｅｓｃｒｉｂｅ　ｕｎｃｅｒｔａｉｎｔｙ　ｓｅｔ　ｏｆ　ｔｒａｆｆｉｃ　ｍａｔｒｉｘ，ａｎｄ　ｒｅｇｕｌａｔｅｓ　＿ｈｅ　ｒｏｂｕｓｔｎｅｓｓ　ｂｙ　ｔｈｅ　ｐａｒａｍｅｔｅｒｔ　Ｆ　ｗｈｉｃｈ　ｉｎｄｉｃａｔｅｓ　ｔｈｅ　ｅｘｔｅｎｔ　ｏｆ　ｄｉｓｔｕｒｂａｎｃｅ，ｏｎ　ｔｈｉｓ　ｂａｓｅ，ｏｂｔｉｎｓ　ｔｈｅ　ｏｐｔｉａｍａｌ　ｓｏｌｕｔｉｏｎ　ｉｎ　ｔｈｅ　ｗｏｌ￣ｔ—ｅａｓｅ　ｏｆ　ｕｎｃｅｒｔａｉｎ　ｓｅｔ．Ｔｈｒｏｕｇｈ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｉｎ　Ａｍｅｒｉｃａｎ　Ａｂｉｌｅｎｅ　ｎｅｔｗｏｒｋ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｈｍ　Ｃａｔｎ　ｒｅｄｕｃｅ　ｔｈｅ　ｍａｘｉ—　ｍｕｍ　ｌｉｎｋ　ｕｔｉｌｉｚａｔｉｏｎ　４０　ｐｅｒｃｅｎｔ　ａｎｄ　２０　ｐｅｒｃｅｎｔ　ｒｅｓｐｅｃｔｉｖｅｌｙ　ｗｈｅｎ　ｃｏｍｐａｒｉｎｇ　ｗｉｔｈ　ｔｒａｄｉｔｉｏｎａｌ　ｌｉｎｋ　ｗｅｉｇｈｔ　ｐｌａｎｎｉｎｇ　ｍｅｔｈｏｄｓ　ａｎｄ　ｔｈｅ　ｅｍｅｒｇｉｎｇ　ＭＲＣ　ｐｒｏｇｒａｍｍｉｎｇ　ｍｏｄｅ１．　Ｋｅｙ　ｗｏｒｄｓ：ｕｎｃｅｒｔｉｎ　ｔａｒａｆｆｉｃ　ｍａｔｒｉｘ；ｒｏｂｕｓｔ；ｗｅｉｇｈｔ　ｐｌａｎｎｉｎｇ；ＭＩＰ　ｍｏｄｅｌ；Ｆｍｏｄｅｌ　—０　引　言　随着互联网的发展，不断出现的新应用在给用户　最简单的链路权重设置方法是把网络中的链路权重　都设为１，Ｃｉｓｃｏ…提议将链路权值设置为与链路带宽　成反比，而Ｆｏｒｔｚ　剖提出通过优化ＩＰ网络链路的权重　带来全新体验的同时也刺激了互联网流量的增长，使　得计算机通信网络受到的压力越来越大。这促使网　络运营商不断扩大对网络硬件的投入，以满足客户对　性能的需求。但是，简单的扩大链路带宽并不是解决　问题的根本办法，因为网络中部分链路出现拥塞的同　时有相当一部分链路却被空闲不用，只有通过网络的　调节和控制功能使流量分布更加合理，才能有效地解　决这一问题。　目前，大部分ＩＰ网络设备在局域网内都采用　ＯＳＰＦ路由协议。在此路由协议的基础上，对网络流　量的控制主要通过链路权重的调节来实现，因此网络　权重的设置问题成为流量工程一个专门的研究方向。　收稿日期：２０１３４３８．１９　可提高网络的服务能力高达５０％，从而更好地实现　负载均衡。为此有众多的学者提出了自己的看法，如　Ａｌｔｍ和Ｆｏｒｔｚ　Ｂ＿２剖提出了链路权重规划的意义和基　本方法；Ｓｔｅｖｅｎ　Ｓ．Ｗ．Ｌｅｅ　从节能的角度出发提出一　个整数线性规划模型，并提出拉格朗日松弛和的谐波　系列启发式算法来求解；Ｔｏｍａｓｚｅｗｓｋｉｌ　将分支切割　法运用到问题中也取得了良好效果。　如今网络的需求瞬息万变，业务流量变化莫测，　这给链路权重的规划造成了极大的困难，因此在不确　定流量矩阵的情况下，链路权重规划的研究非常重　要，国际上不少人在这方面做出了贡献，如Ｂｅｎ—　Ａｍｅｕｒ和Ｋｅｒｉｖｉｎ　提出了在简单ＯＳＰＦ路由协议（没　作者简介：罗宇（１９８９．），男，四川眉山人，四川大学计算机（软件）学院硕士研究生，研究方向：计算机网络与通信系统；吕光　宏（１９６３－），男，四川成都人，教授，研究方向：光网络，通信网络。　７２　计算机与现代化　２０１４年第１期　有ＥＭＣＰ规则）下，针对多面体不确定集的链路权重　规划问题的求解；Ａｌｔｍ等人在文献［９］中针对多面体　不确定集，以最小化最大链路利用率为目标，建立了　一个求解支持ＥＭＣＰ规则的ＯＳＰＦ路由协议网络下　链路权重规划的ＭＩＰ模型，并验证了模型的可行性；　在文献［１Ｏ］中针对ＭＩＰ模型无法适应大网络的缺　点，使用Ｈｏｓｅ模型来定义多面的不确定集，并使用禁　忌搜索算法提出了２种不同的启发式算法，分别为　ＣＭ和ＬＭ算法，这２种算法分别以链路的负载情况　与代价情况为优化目标。　国内的相关研究较少，电子科技大学程小梅　提出了一个ＭＲＣ模型，它把Ｈｏｓｅ模型与Ｐｉｐｅ模型　结合起来描述业务矩阵的不确定集，应用鲁棒性的理　论，求出当前集合下最大的链路利用率，并以最小化　这个链路利用率为目的进行链路权重优化，为了解决　计算复杂度问题还提出了启发式算法来找到近视解。　目前的方法都有一个共同点就是鲁棒性为不可调的，　即当一些实际的参数（如业务量的最大值、节点流入　和流出的业务量）一旦确定，求解结果的鲁棒性也就　确定，没有一个用于对鲁棒性进行调节的参数，这样　往往导致不确定集对于实际的描述受限，求解比较　“保守”并不够优秀。因此，本文使用ｒ模型定义不　确定集，依据鲁棒性理论提出一个新的在不确定流量　矩阵下求解Ｉ：ｌ　ｅ　Ｐ网络链路权重规划的模型，该模型可　＝　以通过调整参数ｒ的值来反映决策者对网络情况的　ｋｓ　＝　ｅ　埚　判断，同时反映求解结果的鲁棒性，这样更加符合实　Ｖ　际的情况。在Ａｂｉ∈　Ｖ　ｌｅｎｅ网络实际流量的测试中，该算　法与传统的算法相比，可降低４０％的最大链路利用　ｋ　∈　率；与ＭＲＣ模型相比，可降低２０％的最大链路利　Ｋ　用率。　１　网络链路权重规划　１．１不考虑不确定业务下的求解模型　首先，定义网络Ｇ（Ｖ，Ｅ），Ｖ表示网络中的节点　集合，Ｅ表示网络中单向链路的集合且有ｅ∈Ｅ，ｉ（ｅ）　表示链路ｅ的起点，ｊ（ｅ）表示链路ｅ的终点，Ｃ　表示　链路ｅ的容量，ｗ。表示链路ｅ的权重…ｒ表示节点ｓ　和ｔ之间的最短距离；然后，定义业务Ｋ表示网络中　所有业务的集合且有ｋ∈Ｋ，ｓ　，ｔ　∈Ｖ，ｄ　表示节点ｓ　到节点ｔ　的业务　ｋ的流量大小；最后，使用　表示业　务ｋ的信息量经过链路ｅ的部分，ｘ　表示ｅ链路上的　流量，ｚ表示各个链路的剩余带宽中的最小值。以最　大化最小链路剩余带宽为目标建立一个简单的ＩＰ网　络规划模型：　ｍａｘ　ｚ　（１）　ｓ．ｔ．ｘ　＋ＺＣ　ｃ　，Ｖｅ∈Ｅ　（２）　（３）　∑Ｋｄ　－－Ｘｅ￣Ｖ　ｅ　Ｅ　（４）　ｕ。ｔ一　０，Ｖｅ∈Ｅ，ｔ∈Ｖ，Ｖｋ∈Ｋ，ｔ　＝ｔ　（５）　１一Ｌｌｅｔ≤ｒｊ（　）ｔ＋Ｗ。一ｒｉ（ｅ）ｔ＜－（１一Ｕ。ｔ）Ｍ，Ｖ　ｅ∈Ｅ，ｔ∈Ｖ　（６）　０≤ｙ　。　ｔ一　１一ｕ　，Ｖ　ｅ∈Ｅ，ｔ∈Ｖ，Ｖｋ∈Ｋ，ｔ　＝ｔ　（７）　ｗ　≥１　（８）　ｘ，Ｙ，ｆ，ｒ　０　（９）　ｘ∈Ｚ　ｌ　ｌ　（１０）　其中，Ｍ为常数，相对于权重的取值为极大值；Ｕ　为　二进制变量，当链路ｅ在以节点ｔ为目的的最短路上　时，Ｕ。　＝１，否则为ｕ。　＝Ｏ；ｙｋｉ（ｅ１　表示以节点ｔ为目的节　点的业务在ｉ到ｔ的所有等价最短路出口链路上分得　的平均负载量。　式（２）为链路容量约束，定义了最大链路利用率　的含义；式（３）则保证业务流量守恒原则；式（４）表示　链路上流量与业务流量大小的关系；式（５）表示当链　路ｅ上业务ｋ的流量　＞０时，链路ｅ一定在业务ｋ　的终点ｔ　的最短路径上，即ｕ　＝１，反之不成立；式　（６）表示ＯＳＰＦ协议的约束，即业务量总是在最短路　径上；式（７）表示ＥＣＭＰ流量约束，对于业务ｋ，当Ｕ　＝ｌ时，业务在当前链路的分配流量　等于业务量对　于多条最短路的均分值ｙ　，从而保证每条被选为　最短路的出链路承载的流量都相等，反之，则分配流　量　为０。　此模型中的业务矩阵Ｋ是确定的，但是实际中　的业务量矩阵是不确定的。　１．２不确定业务量矩阵　对于不确定的业务量矩阵Ｋ，需要建立一个模型　来描述该矩阵的集合Ｄ，常见的建模方式就是Ｈｏｓｅ　模型。它描述了业务量矩阵的“行和”和“列和”的上　界。另外Ｐｉｐｅ模型给出的是业务量矩阵每一单元的　上界。　ｄ　ａ　为了更加符合网络的实际情况，本文使用ｒ　模型＿】　，它定义了任意节点对的业务在不同时间的　均值和上界，即ｄ　∈［ｄ　，ｄ　＋ａ　］，其中ｄ　和ａ　分别　表示业务ｋ在不同时间的均值和最大的扰动值。在　实际的ＩＰ网络中，对于同一个业务ｋ，其流量的大小　在不同的时间是不同的，但是这个值也是在一定的范　围波动。同时出现峰值的业务个数也是有限的　，　因此定义一个变量　表示某个业务ｋ在不同时间的　扰动程度，如式（１１）：　１１　：　∈Ｅｏ，１１　（１１）　ｎ　再引入一个参数ｒ表示同时出现峰值的业务个数：　２０１４年第１期　∑ｋ　Ｋ　＜ｒ　罗宇等：基于鲁棒性的链路权重规划算法　（１２）　７３　的情况，但是解也相对保守；反之ｒ越小，表示网络　当Ｆ＝０时，业务矩阵变为确定的流量矩阵；而　波动越平稳，各个业务同时出现峰值的几率低，得到　当Ｆ＝Ｊ　Ｋ　Ｉ时表示为最差的情况，即所有业务都到达　的解能适应的不同业务的情况较少，得到的解也相对　峰值的情况，因此可以通过条件参数ｒ来完成对不　激进。这样就能根据不同的环境以及相关的经验数　确定集的调节。　据调整ｒ值，从而得出更好的权重设置方式。　相对于ＭＲＣ模型无法调整鲁棒性，该模型适应　１．３求解模型　实际网络流量的能力大大提高，同时该模型是一个　式（４）表示链路上的流量等于这条链路上业务　Ｐ的模型，因此可以使用数学规划软件（如ＣＰＬＥＸ　的流量和，但是由于业务矩阵不确定，因此需要找到　ＭＩ　合适的Ｘ　，使之满足不确定集中最坏情况下的链路流　等）直接进行计算，以计算出精确值。量，如式（１３）：　ｍ…ａｘ［　∑Ｋｄ　］　ｅ，ＶｅＥＶ　（１３）　依据ｒ模型，使用ｄ　和ａ　来描述实际的业务量　ｄ　，业务量只考虑比均值大的情况，则式（１３）可转化　为式（１４）：　＋　ｍａｘ　Ｚ　ｃ，ＶｅｅＥ　ｗｈｅｒｅ，Ｄｒ＝｛Ｔ１　Ｅ　Ｒ　：ｒｌ　≤１，ｋ　Ｅ　Ｋ　ａｎｄ．　，　ｒ｝　（１４）　式（１４）并不是一个线性规划问题，不便于求解，　因此将问题细化，对于任意的链路ｅ单独考虑，进行　对偶化得：　ｍａｘ　Ｋ∈＾　ｍｉｎ（Ｆｒｒ　＋　∑ＫＫ∈Ａｐ　　）　ｓ．ｔ．ｒ甘ｓ．ｔ．１『。＋Ｐ　－＞－Ｘｌ　ａ　，ｋ∈Ｋ　．　１　￡　０，Ｐ　，盯　０，ｋ∈Ｋ　（１５）　由对偶的原理可将式（１５）转化为如下约束：　∑Ｋｄ　＋Ｆ＇ｒｒ　＋　∑Ｋｐ　＜ｘ　，ＶｅｅＥ　（１６）　。＋Ｐ　２　Ｔ１　ｄ　，ｋ∈Ｋ　（１７）　Ｐ　，竹　≥ｏ，ｋ∈Ｋ　（１８）　这样可以使用式（１６）～式（１８）替代基础模型中的　式（４），就可以得到可调节鲁棒陛的链路权重规划模型：　ｍａｘ　ｚ　（１９）　Ｓ．ｔ．Ｘ　＋ＺＣ。　ｃ。，Ｖｅ∈Ｅ　（２０）　ｆ　１，ｉ＝ｓ　ｊ　）（　一　）　｛－１，ｉ＝　Ｖｉ　Ｖ，ｋ　Ｋ（２１）　∑Ｋｄ　＋ｒ订　ｋ∑Ｋｐｋｅ　ｅ，Ｖｅ　Ｅ（２２）　一耵　＋ａ　一Ｐ　，Ｖ　ｅ∈Ｅ，ｋ∈Ｋ（２３）　ｕ　一　≥０，Ｖ　ｅ∈Ｅ，ｔ∈Ｖ，Ｖｋ∈Ｋ，ｔ　＝ｔ　（２４）　１一Ｕｅｔ　ｒｊ（　）　＋ｗ　一ｒｉ（ｅ）ｔ≤（１一ｕ。ｔ）Ｍ，Ｖｅ∈Ｅ，ｔ∈Ｖ（２５）　０＜ｙ　。、　一　１一ｕ　，Ｖ　ｅ∈Ｅ，ｔＥＶ，Ｖｋ∈Ｋ，ｔ　＝ｔ　（２６）　Ｗ。　１　（２７）　ｘ，Ｙ，ｆ，ｒ≥０（２８）　ｘ　Ｅ　Ｚ　Ｉ　Ｉ　（２９）　该模型可以通过调节ｒ值，来反映决策者对于　当前实际的网络环境的分析，以及网络业务量流量波　动性的评估。ｒ越大，表示网络流量波动越大，各个　业务量同时出现峰值的几率高，得到的解能适应更多　２实验结果与分析　为了能更好地测试链路权重设置算法的性能，参　考杨华为　等人的方法，将权重规划算法的结果设　置到实际的网络拓扑中，并用实际的流量进行模拟测　试，以验证计算结果与模拟测试结果之间的关系，更　加能说明算法的性能。模拟测试的具体步骤如下：　步骤１　按照权重规划的结果设置链路的权重；　步骤２通过ＥＣＭＰ路由算法计算所有ＯＤ对间　的路径集合；　步骤３初始化所有链路负载为０；　步骤４读取一个未使用流量矩阵数据；　步骤５选择ＯＤ对，将流量均分后放到ＯＤ对　的所有路径上；　步骤６　当前流量矩阵数据存在未加载项，则跳　到步骤５；　步骤７统计所有链路，输出最大链路负载；　步骤８标记当前流量矩阵为已使用，判断是否　存在未使用的流量矩阵，若是则跳到步骤３，否则就　结束。　本实验采用美国Ａｂｉｌｅｎｅ网络为测试的网络拓　扑，流量采用２００４年５月份的流量数据。首先验证　新模型求解的精准性，然后分析不同ｒ值对求解结　果的影响，最后比较新模型和其他方法（Ｕｎｉｔ、ＩｎＣａｐ　以及ＭＣＲ）的性能。　实验采用美国Ａｂｉｌｅｎｅ网络实际的流量数据＿ｌ　：流　量数据如表１所示，基本的网络拓扑数据如图１所示。　表１实验网络数据表　图１美国Ａｂｉｌｅｎｅ网络拓扑结构　７４　计算机与现代化　２０１４年第１期　耵．ｊ，　ｉ，＾ｙｉ，ｄ　，ａ　网络中除了节点２、节点６间链　路的带宽为２．５Ｇｂｐｓ以外，其余链路的带宽均为　１０Ｇｂｐｓ。业务量矩阵以２００４年５月采集的流量矩阵　为基础，分别依据Ｐｉｐｅ模型、Ｈｏｓｅ模型以及ｒ模型的　思想设计出可行的竹　１１ｉ，＾ｙｉ，ｄ　，ａ　等不确定业务量　矩阵相关的量。使用这些量来模拟一个不确定业务　量矩阵的集合，并完成问题的求解。　实验１　实验的目的是验证模型求解的精准性，　即验证模型是否求解出了不确定集中“最坏”情况下　的流量分布以及对应的最优的链路权重设置。本实　验使用一个近视“穷举”的方法来确定“精确解”，测　试时随机产生一个流量矩阵，其中ｒ对流量为峰值，　而其他流量为均值，使用这种方法去寻找满足条件的　不确定集中可能的“最坏”情况下的流量矩阵，然后将其　带人确定业务流量的链路权重规划模型中计算出网络　中的最大链路利用率，当测试的数目足够大时，可以认　为这个值直该达到或者十分接近精确值。就可以用来　与模型求解结果进行比较，验证模型求解的精准Ｉ生。　ｒ取值［１，６０］，得到６０个不同的不确定集。模　型使用ｃ＋＋和ＣＰＬＥＸ　１２．５，并在相对误差０．１％的　情况下分别计算出６Ｏ种不同的结果。测试在任意一　个不确定集中随机产生１０组１００００个业务量矩阵进　行测试，取各组最大链路利用率的最大值作为这个不　确定集下的测试结果。　图２模型求解值与测试值的对比　由图２可见，测试值与模型计算值的求解结果很　接近，当Ｆ＝０或者Ｆ　５７时，两者的结果已经完全　相等，因此本文提出的模型求解结果精度很高。　随之ｒ的不断增大，模型求解和测试值的最大　链路利用率越来越大，可见求得的解也就越来越保　守。这是由于在一定范围内，随着ｒ的不断增大，相　同其他参数下的不确定集也在增大，因此求得集合下　最坏情况下的最大链路利用率也会增加。　但是，当ｒ超过３８时，模型求解值将不随ｒ的　增加而增加；当测试值在ｒ超过５７时，不再随Ｉ１的　增加而增加。这是因为当ｒ达到一定值时，不确定　集中最坏的情况已经在之前就出现了，之后随着ｒ　的增加，不确定集在变大，但是其中求解的最坏情况　并没有变化，此时将求得模型的最保守解。在这个网　络拓扑以及相应的ｒ模型参数下５５．９４％的最大链　路利用率就是模型求解的最保守解。　两种方式的转折点不同是，因为测试时，流量矩　阵是随机产生的，因此找到不确定集中的最坏情况是　有概率性的，而模型通过数学公式求解，没有概率性，　因此模拟测试的转折点ｒ值比模型求解的大。　实验２实验主要验证参数ｒ对算法性能的影　响。ｒ取值［０，５０］，使用ｃ＋＋和ＣＰＬＥＸ　１２．５，并在　相对误差０．１％的情况下分别计算出５０种不同的结　果。这样就得到了模型求解的最大链路利用率，以及　由实际流量模拟测试得到最大链路利用率的比较，如　图３所示。　（ｂ）Ｆ∈［２０，５０１　图３不同ｒ对模型求解与模型测试的影响　原理上模型求解的就应该是最差情况下的最大　链路利用率，即实际测试的结果一定要比模型求解的　值要小，但是如图３（ａ）所示，当ｒ比较小时，模拟测　试的结果与模型求解结果没有明显的关系，这是因为　当ｒ比较小时，表示决策者比较激进并认为网络流　２０１４年第１期　罗宇等：基于鲁棒性的链路权重规划算法　ｌｏ０　９０　８Ｏ　７５　量的扰动并不剧烈，但是实际的网络并不是这样，这　就导致所求的解并不是最优的，即求得的解不能反映　实际的情况，会出现个别超过限制的情况；当ｒ的取　７０　值达到或者超过实际的扰动情况（依据式（１２）计算　出测试数据的ｒ值为１９时，如图３（ｂ）所示，模拟测　试的结果将不会超过模型求解的最大链路利用率，而　只是在这个值下浮动，这个解比较保守。这就体现了　算法使用的ｒ模型对实际情况的模拟更加灵活，决　策者对现实情况的估计将以这样一个参数来反映，当　鬓６０　幕５０　４ｏ　羔３０　２０　１０　Ｏ　决策者比较保守时就可以适当提高ｒ的取值，以一　定的性能为代价换取结果的适应能力，即出现实际情　况比预计情况更差的可能性降低，如图３（ｂ）所示，实　际值都在模型求解值以下。相反如果决策者比较激　进就可以适当降低ｒ的取值，这样的结果会比较好，　但是出现实际情况比预计情况更差的可能性就比较　高。如图３（ａ）所示，有部分模拟结果比模型求解值　还要高的情况比较多。　实验３为了验证本文提出的模型性能，将本文　提出的方法与其他方法进行比较：　Ｕｎｉｔ：所有链路的权重为１。　ＩｎＣａｐ（ｉｎｖｅｒｓｅ　ｃａｐａｃｉｔｙ）：按照Ｃｉｓｃｏ的建议，每条　链路的权重与链路的带宽成反比。　ＭＣＲ：文献［８］中提出的链路权重规划模型。　ｍｏｄｅ＿２０：本文提出的算法，设置参数Ｆ＝２０。　其中，ＭＣＲ和ｍｏｄｅ＿２０都是使用ｃ＋＋和ＣＰＬＥＸ在设　置相对容忍度为０．１％的情况下进行计算。以一个　月的数据进行模拟测试，由于数据量较大，分别以天、　小时、５分钟为时间间隔分别计算一个月、１天和３小　时的最大链路利用率进行比较。结果如图４所示。　由图４可以看出，当最大链路利用率比较低（如　图４（ｂ）中３到１０小时和图４（ａ）中的月末的３天，最　大链路利用率低于１５％）时，各个算法的结果差异很　小，没有明显的优势。这是因为此新算法是针对网络　负载比较高的情况而设计的，当网络流量少的时候效　果就不明显，此时网络负载比较轻。　当最大链路利用率比较高（传统方法的最大链　路利用率高于５０％）时，ＩｎＣａｐ算法明显好于Ｕｎｉｔ，因　为ＩｎＣａｐ算法让流量尽量走带宽较大的链路；ＭＲＣ　算法比传统的算法也有较大的改善；而本文提出的新　算法却远远优于传统的链路权重设置方法，也优于　ＭＲＣ算法，尤其是在链路负载最严重（传统方法的最　大链路利用率高于８０％）时，新算法相对于Ｕｎｉｔ和　ＩｎＣａｐ减少最大链路负载分别超过５０％和４０％，相对　于ＭＲＣ也减少了最大链路负载２０％，由此可见新算　法在降低网络最大链路负载上的优势很明显。　（ａ）以天为单位的结果比较　（ｂ）以小时为单位的１天数据的比较　（ｅ）以５分钟为单位３小时的数据比较　图４不同算法在不同时间最大链路利用率比较　３　结束语　本文首先研究ＯＳＰＦ路由协议的原理，提出一个　在确定业务量矩阵下网路链路权重规划模型，该模型　是一个可用线性规划工具（如ＣＰＬＥＸ）直接求解的　ＭＩＰ模型；研究了不确定流量矩阵的定义问题，在　Ｈｏｓｅ、Ｐｉｐｅ等模型中依据实际网络流量的情况，选取　ｒ模型表述不确定的流量矩阵，并通过ｒ值实现对不　确定集中鲁棒性的定义与调节，这样使得模型能更加　容易模拟现实当中的不确定流量矩阵。其次，依据鲁　棒性理论将两者结合在一起，提出一个新的网络链路　权重规划求解模型，该模型可以通过调节参数ｒ来　实现对求解结果鲁棒性的调节，使得结果更加符合实　７６　计算机与现代化　２０１４年第１期　际需要。　实验表明，本文提出的新模型的结果比传统的链　路权重设置方法降低最大链路利用率达到了４０％，　相对与ＭＲＣ模型的结果也降低了２０％左右的最大　链路利用率，可见本文提出的算法在最小化最大链路　利用率方面的优势。通过对不同ｒ值的求解分析，　可知不同的ｒ值，对应于不同的扰动性，也进一步确　定了不确定集的大小。解的适应性随着ｒ的增加而　增加，同时解的保守程度也相应增加，实际结果将取　决于决策者对实际问题的判断。　［５］　Ａｌｔｌｎ　Ａ，Ｆｏｒｔｚ　Ｂ，Ｔｈｏｒｕｐ　Ｍ．Ｉｎｔｒａ—ｄｏｍａｉｎ　ｔｒａｆｉｆｃ　ｅｎｇｉｎｅｅｒ－　ｉｎｇ　ｗｉｔｈ　ｓｈｏｒｔｅｓｔ　ｐａｔｈｍｕｔｉｎｇ　ｐｒｏｔｏｃｏｌｓ［Ｊ］．Ａｎｎａｌｓ　ｏｆ　Ｏｐｅｒ－　ａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，２０１３，２０４（１）：６５－９５．　［６］Ｓｔｅｖｅｎ　Ｓ　Ｗ　Ｌｅｅ，Ｔｓｅｎｇ　Ｐ－Ｋ，Ｃｈｅｎ　Ａ．Ｌｉｎｋ　ｗｅｉｇｈｔ　ａｓｓｉｇｎ—　ｍｅｎｔ　ａｎｄ　ｌｏｏｐ．ｆｒｅｅ　ｒｏｕｔｉｎｇ　ｔａｂｌｅ　ｕｐｄａｔｅ　ｆｏｒ　ｌｉｎｋ　ｓｔａｔｅ　ｒｏｕ－　ｔｉｎｇ　ｐｒｏｔｏｃｏｌｓ　ｉｎ　ｅｎｅｒｇｙ・ａｗａｒｅ　ｉｎｔｅｒｎｅｔ［Ｊ］．Ｆｕｔｕｒｅ　Ｇｅｎｅｒａ－　ｔｉｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２０１２，２８（２）：４３７４４５．　［７］Ｔｏｍａｓｚｅｗｓｋｉ　Ａ，Ｐｉ６ｒｏ　Ｍ，Ｄｚｉｄａ　Ｍ，ｅｔ　１．Ｏｐｔａｉｍｉｚａｔｉｏｎ　ｏｆ　ａｄｍｉｎｉｓｔｒａｔｉｖｅ　ｗｅｉｇｈｔｓ　ｉｎ　ＩＰ　ｎｅｔｗｏｒｋｓ　ｕｓｉｎｇ　ｔｈｅ　ｂｒａｎｃｈ．．ａｎｄ－－　ｃｕｔ　ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｎｅｔｗｏｒｋ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｃｏｎｆｅｒｅｎｃｅ（ＩＮＯＣ　２００５）．２００５：　３９３－４００．　虽然新算法有如上优点，但是也有其局限性。例　如模型为ＭＩＰ模型，求解的复杂度很高，暂时无法适　应更大规模的网络权重规划问题，因此后期可以针对　复杂度提出一些改进的方式。　参考文献：　『８］　Ｂｅｎ　Ａｍｅｕｒ　Ｗ，Ｋｅｒｉｖｉｎ　Ｈ．Ｒｏｕｔｉｎｇ　ｏｆ　ｕｎｃｅｒｔａｉｎ　ｔｒａｆｉｆｃ　ｄｅ．　ｍａｎｄｓ［Ｊ］．Ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　Ｅｎ￣ｎｅｅｉｒｎｇ，２００５，６（３）：　２８３－３１３．　［９］　Ａｈｍ　Ａ，Ｂｅｌｏｔｔｉ　Ｂ，Ｐｍａｒ　Ｈ．ＯＳＰＦ　ｒｏｕｔｉｎｇ　ｗｉｔｌｌ　ｏｐｔｉｍａｌ　ｏｂｌｉｖｉｏｕｓ　ｐｅｒｆｏｒｍａｎｃｅ　ｒａｔｉｏ　ｕｎｄｅｒ　ｐｏｌｙｈｅｄｒａｌ　ｄｅｍａｎｄ　ｕｎｃｅｒ－　ｔａｉｎｔｙ［Ｊ］．Ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，１１（３）：　３９５－４２２．　［１］　Ｋａｒａｓ　Ｐ，Ｐｉｏｒｏ　Ｍ．Ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ　ｒｅｌａｔｅｄ　ｔｏ　ｔｈｅ　ａｓ—　ｓｉｇｎｍｅｎｔ　ｏｆ　ａｄｍｉｎｉ　ｓｔｒａｔｉｖｅ　ｗｅｉｇｈｔｓ　ｉｎ　ｔｈｅ　ＩＰ　ｎｅｔｗｏｒｋｓ’　『１０］Ａｌｔｌｎ　Ａ，Ｆｏｒｔｚ　Ｂ，ｔ￣ｍｉｔ　Ｈ．Ｏｂｌｉｖｉｏｕｓ　ＯＳＰＦ　ｒｏｕｔｉｎｇ　ｗｉｔｈ　ｗｅｉｇｈｔ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｕｎｄｅｒ　ｐｏｌｙｈｅｄｒａｌ　ｄｅｍａｎｄ　ｕｎｃｅｒｔａｉｎｔｙ　ｒｏｕｔｉｎｇ　ｐｒｏｔｏｃｏｌｓ『Ｃ　１／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　ｓｔ　ＰＧＴＳ’２０００．　２０Ｏ０：１８５—１９２．　［２］　Ｆｏｒｔｚ　Ｂ，Ｒｅｘｆｏｒｄ　Ｊ，Ｔｈｏｒｕｐ　Ｍ．Ｔｒａｆｉｃ　ｅｎｇｉｎｅｅｒｉｎｇ　ｗｉｔｈ　［Ｊ］．Ｎｅｔｗｏｒｋｓ，２０１２，６０（２）：１３２．１３９．　［１１］Ｃｈｅｎｇ　Ｘｉａｏ—ｍｅｉ，Ｗａｎｇ　Ｓｈｅｎｇ，Ｗａｎｇ　Ｘｉｏｎｇ．Ｏｐｔｉｍｉｚｉｎｇ　ｌｉｎｋ　ｗｅｉｇｈｔ　ｉｎ　ＯＳＰＦ　ｒｏｕｔｉｎｇ［ｃ］／／ＩＥＥＥ　３４ｔｈ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｌｏｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ．２００９：２０－２３．　ｔｒａｄｉｔｉｏｎａｌ　ＩＰ　ｍｕｔｉｎｇ　ｐｒｏｔｏｃｏｌｓ［Ｊ］．ＩＥＥＥ　Ｃｏｍｍｕｎ．Ｍａｇ．，　２００２，４０（１０）：１１８－１２４．　『３］　Ｇｕｎｎａｒ　Ａ，Ａｂｒａｈａｍｓｓｏｎ　Ｈ，Ｓ￣ｄｅｒｑｖｉｓｔ　Ｍ．Ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｒａｆｆｉｃ　ｅｎ￣ｎｅｅｉｒｎｇ　ｉｎ　ｏｐｅｒａｔｉｏｎａｌ　ＩＰ—ｎｅｔｗｏｒｋｓ：Ａｎ　ｅｘｐｅｒｉｍｅｎ—　ｔａｌ　ｓｔｕｄｙ『Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　ＩＥＥＥ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　ＩＰ　Ｏｐｅｒａｔｉｏｎｓ　ａｎｄ　Ｍａｎａｇｅｍｅｎｔ．２Ｏ０５：２０２—２１１．　［１２］Ｋｏｓｔｅｒ　Ａ　Ｍ　Ｃ　Ａ，Ｋｕｔｓｃｈｋａ　Ｍ，Ｒａａｃｋ　Ｃ．Ｏｎ　ｔｈｅ　ｒｏｂｕｓｔ．　ｎｅｓｓ　ｏｆ　ｏｐｔｉｍａｌ　ｎｅｔｗｏｒｋ　ｄｅｓｉｎｓ［ｃ］／／ＩｇＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．２０１　１：４９－５４．　［１３］杨华为，王洪波，等．最小割多路径路由算法［Ｊ］．软件　学报，２０１２，２３（８）：２１１５・２１２９．　［１４］ＳＮＤｌｉｂ．Ｌｉｂｒａｒｙ　ｏｆ　Ｔｅｓｔ　Ｉｎｓｔａｎｃｅｓ　ｏｒｆ　Ｓｕｒｖｉｖａｂｌｅ　Ｆｉｘｅｄ　Ｔｅｌ—　ｅｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｎｅｔｗｏｒｋ　Ｄｅｓｉｎ［ＤＢ／ＯＬ］．ｈｔｇｔｐ：／／ｓｎ￣ｉｂ．　ｚｉｂ．ｄｅ／ｈｏｍｅ．ａｃｔｉｏｎ，２０１３－０８—１９．　ｆ４］　Ａｈｌｎ　Ａ，Ｆｏｒｔｚ　Ｂ，１３ｍｉｔ　Ｈ．Ｏｂｌｉｖｉｏｕｓ　ＯＳＰＦ　ｒｏｕｔｉｎｇ　ｗｉｔｈ　ｗｅｉｇｈｔ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｕｎｄｅｒ　ｐｏｌｙｈｅｄｒａｌ　ｄｅｍａｎｄ　ｕｎｃｅｒｔａｉｎｔｙ　［Ｊ］．Ｎｅｔｗｏｒｋｓ，２０１２，６０（２）：１３２—１３９．　（上接第７０页）　参考文献：　［１］宋晗，陈宗基，孔繁峨．驾驶员辅助系统的辅助级别判　定［Ｊ］．系统仿真学报，２００９，２１（１）：２０８－２１２．　『２］Ｐａｒａｓｕｒａｍａｎ　Ｒ．Ｔｈｅｏｒｙ　ａｎｄ　Ｄｅｓｉｇｎ　ｏｆ　Ａｄａｐｔｉｖｅ　Ａｕｔｏｍａｔｉｏｎ　ｉｎ　Ａｖｉａｔｉｏｎ　Ｓｙｓｔｅｍ　ｌ　Ｍ　１．Ｗａｒｍｉｎｓｔｅｒ，ＰＡ：Ｎａｖａｌ　Ａｉｒ　Ｄｅ—　ｖｅｌｏｐｍｅｎｔ　Ｃｅｎｔｅｒ，１９９２．　［３］　王阔天．多无人机监督控制系统的人机动态功能分配　研究［Ｄ］．长沙：国防科学技术大学，２００９．　［４］Ｃｏｏｋ　Ｃ，Ｃｏｒｂｒｉｄｇｅ　Ｃ，Ｍｏｒｇｎ　Ｃ，ｅｔａ　１．Ｉａｎｖｅｓｔｉｇａｔｉｎｇ　ｍｅｔｈ—　ｏｄｓ　ｏｆ　ｄｙｎａｍｉｃ　ｆｕｎｃｔｉｏｎ　ａｌｌｏｃｍｉｏｎ　ｆｏｒ　ｎａｖａｌ　ｃｏｍｍａｎｄ　ａｎｄ　［７］　王鹏程，李为民．基于模糊集理论和Ｄ．Ｓ证据推理的空　袭目标识别［Ｊ］．现代防御技术，２００５，３３（５）：８．１０，４１．　［８］李伟生，王宝树．基于模糊逻辑和Ｄ．Ｓ证据理论的一种　态势估计方法［Ｊ］．系统工程与电子技术，２００３，２５　（１０）：１２７８—１２８０，１２９８．　［９］　李海英，冯冬，宋建成．中压真空断路器的模糊．证据理论　在线状态评估模型［Ｊ］．高压电器，２０１３，４９（１）：４０－４５．　［１Ｏ］王肖霞．冲突证据合成规则的研究［Ｄ］．太原：中北大　学，２００７．　［１１］Ｗｉｎｇ　Ｄ　Ｊ，Ｃｏｔｔｏｎ　Ｗ　Ｂ．Ａｕｔｏｎｏｍｏｕｓ　Ｆｌｉｇｈｔ　Ｒｕｌｅｓ：Ａ　Ｃｏｎ—　ｃｅｐｔ　ｏｆｒ　Ｓｅｌｆ－ｓｅｐａｒａｔｉｏｎ　ｉｎ　Ｕ．Ｓ．Ｄｏｍｅｓｔｉｃ　Ａｉｍｐａｃｅ［Ｒ］．　Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ：　ＮＡＳＡ／ＴＰ＿２Ｏ１１＿２１７ｌ７４；Ｌ－２００５８；　ＮＦ１６７６Ｌ一１２８３０，ＮＡＳＡ，２０１　１．　ｃｏｎｔｒｏｌ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｕｍａｎ　Ｉｎｔｅｒｆａｃｅｓ　ｉｎ　Ｃｏｎｔｒｏｌ　Ｒｏｏｍｓ，Ｃｏｃｋｐｉｔｓ　ａｎｄ　Ｃｏｍｍａｎｄ　Ｃｅｎｔｒｅｓ．１９９９：　３８８．３９３．　［５］Ｐａｒａｓｕｒａｍａｎ　Ｒ，Ｓｈｅｒｉｄａｎ　Ｔ　Ｂ，Ｗｉｃｋｅｎｓ　Ｃ　Ｄ．Ａ　ｍｏｄｅｌ　ｏｆｒ　ｔｙｐｅｓ　ａｎｄ　ｌｅｖｅｌｓ　ｏｆ　ｈｕｍａｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｗｉｔｈ　ａｕｔｏｍａｔｉｏｎ　ｆ　Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ　Ｐａｒｔ　Ａ：Ｓｙｓｔｅｍｓ　ａｎｄ　Ｈｕｍａｎｓ，２０００，３０（３）：２８６—２９７．　［６］　Ｃｏｙｅ　Ｄｅ　Ｂｒｔｍｅｌｉｓ　Ｔ，Ｌｅ　Ｂｌａｙｅ　Ｐ，Ｂｏｎｎｅｔ　Ｐ，ｅｔ　ａ１．Ｄｉｓｔａｎｃｅ　ｍｉｓｓｉｏｎ　ｍａｎａｇｅｍｅｎｔ　ｎｄ　ａｄｙｎａｍｉｃ　ａｌｌｏｃａｔｉｏｎ　ｏｆ　ｆｕｎｃｔｉｏｎｌ　Ｃ　ｌ／／　Ｈｕｍａｎｓ　Ｏｐｅｒａｔｉｎｇ　Ｕｎｍａｎｎｅｄ　Ｓｙｓｔｅｍｓ　Ｃｏｎｆｅｒｅｎｃｅ．２０Ｏ８．　［１２］谭源泉，李怡，张柯．基于模糊集与证据理论的敌我识　别新方法［Ｊ］．电波科学学报，２０１２，２７（３）：５７８－５８２．　［１３］江桥辉，王汝凉，刘志平．基于模糊集与改进证据理论　的目标识别［Ｊ］．广西师范学院学报：自然科学版，　２００９，２６（２）：８３—８６，１０１．　［１４］肖利平，杨嘉伟．一种基于模糊理论与Ｄ．Ｓ证据理论的　红外小目标与诱饵识别算法［Ｊ］．红外技术，２００５，２７　（３）：２４０—２４４．