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

计算机与现代化 ›› 2014, Vol. 0 ›› Issue (1): 71-76.

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

四川大学计算机（软件）学院，四川成都610065

收稿日期:2013-08-19 出版日期:2014-01-20 发布日期:2014-02-10
作者简介: 罗宇（1989-），男，四川眉山人，四川大学计算机（软件）学院硕士研究生，研究方向：计算机网络与通信系统; 吕光宏（1963-），男，四川成都人，教授，研究方向：光网络，通信网络。

Link Weight Programming Algorithm Based on Robustness

College of Computer (Software), Sichuan University, Chengdu 610065, China

Received:2013-08-19 Online:2014-01-20 Published:2014-02-10

摘要/Abstract

摘要：

在IP网络中，链路权重规划是流量工程中的重要问题。为了优化网络流量并实现负载均衡，针对业务量矩阵的不确定性，依据鲁棒性理论提出一个链路权重规划的MIP模型。该模型使用Γ模型描述业务量矩阵的不确定集，通过表示扰动程度的参数Γ实现了对

鲁棒性的调节，在此基础上求得不确定集中最差情况下的最优解。实验结果表明，与传统的链路权重规划方法以及新出现的MRC规划模型相比较，该算法可降低最大链路利用率，分别达到了40%和20%。

关键词: , 不确定流量矩阵, 鲁棒性, 权重规划, MIP模型, &Gamma, 模型

Abstract:

For IP networks, the link weight planning is an important issue of traffic engineering. In order to optimize the network traffic and achieve load balancing and against the unknown traffic matrix, this article proposes a

link weight programming MIP model based on the robustness theory. This model applies the Γ_model to describe uncertainty set of traffic matrix, and regulates the robustness by the parameter Γ which indicates the extent of disturbance,

on this base, obtains the optimal solution in the worst-case of uncertain set. Through the experiment in American Abilene network, the proposed algorithm can reduce the maximum link utilization 40 percent and 20 percent respectively when

comparing with traditional link weight planning methods and the emerging MRC programming model.

Key words: uncertain traffic matrix, robust, weight planning, MIP model, Γ_model

罗宇,吕光宏. 基于鲁棒性的链路权重规划算法[J]. 计算机与现代化, 2014, 0(1): 71-76.

LUO Yu, LYU Guang-hong. Link Weight Programming Algorithm Based on Robustness[J]. Computer and Modernization, 2014, 0(1): 71-76.

参考文献

［1］ Karas P, Pioro M. Optimization problems related to the assignment of admini strative weights in the IP networks’ routing protocols［C］// Proc. of the 1st PGTS’2000. 2000:185-192.
［2］ Fortz B, Rexford J, Thorup M. Traffic engineering with traditional IP routing protocols［J］. IEEE Commun.Mag., 2002,40(10):118-124.
［3］ Gunnar A, Abrahamsson H, Sderqvist M． Performance of traffic engineering in operational IP-networks: An experimental study［C］// Proceedings of the 5th IEEE International Workshop on IP Operations and Management. 2005:202-

211. 
［4］ Altn A, Fortz B, mit H. Oblivious OSPF routing with weight optimization under polyhedral demand uncertainty［J］. Networks, 2012, 60(2):132-139.
［5］ Altn A, Fortz B, Thorup M. Intra-domain trafc engineering with shortest pathrouting protocols［J］. Annals of Operations Research, 2013,204(1):65-95.
［6］ Steven S W Lee, Tseng P-K, Chen A . Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet［J］. Future Generation Computer Systems, 2012,28(2):437-445.
［7］ Tomaszewski A, Pióro M, Dzida M, et al. Optimization of administrative weights in IP networks using the branch-and-cut approach［C］// Proceedings of the 2nd International Network Optimization Conference (INOC 2005). 2005:393-400.


［8］ Ben-Ameur W, Kerivin H. Routing of uncertain traffic demands［J］. Optimization and Engineering, 2005,6(3):283-313.
［9］ Altn A, Belotti B, Pnar H. OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty［J］. Optimization and Engineering, 2010,11(3):395-422.
［10］Altn A, Fortz B, mit H. Oblivious OSPF routing with weight optimization under polyhedral demand uncertainty［J］. Networks, 2012,60(2):132-139.
［11］Cheng Xiao-mei, Wang Sheng, Wang Xiong. Optimizing link weight in OSPF routing［C］// IEEE 34th Conference on Local Computer Networks. 2009:20-23.
［12］Koster A M C A, Kutschka M, Raack C. On the robustness of optimal network designs［C］// IEEE International Conference on Communications. 2011:49-54.
［13］杨华为,王洪波,等. 最小割多路径路由算法［J］. 软件学报, 2012,23(8):2115-2129.
［14］SNDlib. Library of Test Instances for Survivable Fixed Telecommunication Network Design［DB/OL］. http://sndlib.zib.de/home.action, 2013-08-19.

[1]	赵晨阳, 薛涛, 刘俊华. 基于改进Stable Diffusion的时尚服饰图案生成[J]. 计算机与现代化, 2024, 0(12): 15-23.
[2]	王晓航1, 李永杰1, 余雷1, 范萧2. 一种利用复合事件概率运算解决负信息抑制最大化问题的方法[J]. 计算机与现代化, 2024, 0(12): 24-33.
[3]	万兵1, 2, 3, 赵文涛4, 潘多涛1, 赵峥韬2, 3, 孙朝阳2, 3, 俞建成2, 3. 无人帆船半物理仿真测试系统设计[J]. 计算机与现代化, 2024, 0(12): 91-99.
[4]	李德友1, 2, 余劲松弟1, 2, 魏丹丹1, 2, 罗源1, 2, 佟瑞菊3. 面向格网化立方体元数据的抽象树模型[J]. 计算机与现代化, 2024, 0(11): 1-6.
[5]	张昆1, 张永伟1, 吴永城1, 张笑文2, 翟世臣2. 基于大模型的设备故障知识图谱自动构建方法[J]. 计算机与现代化, 2024, 0(11): 46-53.
[6]	陈宇航1, 杨勇1, 帕力旦·吐尔逊1, 樊小超1, 任鸽1, 刁宇峰2. 融合句法特征与语义特征的作文自动评分方法[J]. 计算机与现代化, 2024, 0(11): 64-69.
[7]	张宇1, 2, 黎靖1, 2, 马铭1, 2, 王众祥1, 2, 孙妍1, 2. YOLOLW:一个新的轻量级目标检测模型[J]. 计算机与现代化, 2024, 0(11): 91-98.
[8]	王聪1, 杨文娟1, 丁兴旺2. 基于多模态信息融合的历史档案资源聚合模型[J]. 计算机与现代化, 2024, 0(10): 120-126.
[9]	齐俊1, 2, 曲睿婷2, 教传铭2, 周巧妮2, 郭彦良3, 覃文军3. 基于知识图谱增强大语言模型双碳领域服务[J]. 计算机与现代化, 2024, 0(09): 8-14.
[10]	张惠楠1, 张强1, 孙红霞2. 基于改进时序胶囊网络的油藏生产动态分析模型[J]. 计算机与现代化, 2024, 0(09): 15-19.
[11]	李进1, 魏艳龙1, 薛红新2, 梁海坚2. 基于LSTM-SIR-EAKF的流感样病例预测[J]. 计算机与现代化, 2024, 0(09): 38-44.
[12]	赵盾1, 佘学兵2, 邬昌兴3. 基于BERT-BiLSTM-CRF党建领域命名实体识别[J]. 计算机与现代化, 2024, 0(09): 91-94.
[13]	杨绍祖1, 2, 王海程1, 2, 吴金雅1, 2, 马纪颖1, 2. 基于STAGCN-Informer时空组合模型的风电功率预测方法[J]. 计算机与现代化, 2024, 0(07): 13-20.
[14]	李璐, 朱焱. 基于知识提示微调的事件抽取方法[J]. 计算机与现代化, 2024, 0(07): 36-40.
[15]	黄文栋, 王怡凡. 基于模态类别的多模态信息处理与融合综述[J]. 计算机与现代化, 2024, 0(07): 47-62.