Link Weight Programming Algorithm Based on Robustness

Abstract

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

LUO Yu, LYU Guang-hong. Link Weight Programming Algorithm Based on Robustness[J]. Computer and Modernization.

References ［14］

［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-
21	1. 
［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]	QIAN Xiao-zhao, WANG Peng. Robust Defense Method for Graph Convolutional Neural Network [J]. Computer and Modernization, 2023, 0(01): 74-80.
[2]	WANG Jian-hua, RAN Yu-kun. Eye-movement Tracking Based on Deep Neural Network for Portable Devices [J]. Computer and Modernization, 2021, 0(08): 58-63.
[3]	GAO Guo-jing, LYU Qing-wen. Robust Medical Image Encryption Algorithm Based on Compound Chaos [J]. Computer and Modernization, 2021, 0(06): 107-112.
[4]	LI Wei-dong, XU Shu-kun, WANG Yun-ming. Analysis of New York Rail Transit Network Characteristics Based on Complex Network [J]. Computer and Modernization, 2021, 0(02): 94-99.
[5]	JIANGSu-ying. FractionalOrderControlBasedonImprovedPSOAlgorithmforHeatingSystem [J]. Computer and Modernization, 2018, 0(07): 39-.
[6]	GOU Xin-ke1，2，3， XU Gao-peng1，2，3. Research on Speech Recognition Robustness Based on Gabor Filtering [J]. Computer and Modernization, 2018, 0(05): 20-.
[7]	ZHANG Chan， FENG Guojun， XIAO Yunbo. Study on Indices of DCN Structural Robustness [J]. Computer and Modernization, 2016, 0(5): 55-60.
[8]	KE Jiang-sheng, NI Jian-jun, WU Liu-ying. An Improved Robust SLAM Algorithm [J]. Computer and Modernization, 2016, 0(2): 104-106,111.
[9]	CHEN Xue-song1, LI Hao-tian1, JIA Rui-cheng2, SUN Li-na2, BU Guang-long1. A Digital Audio Watermarking Algorithm Based on Chaotic Encrypting in DWT [J]. Computer and Modernization, 2014, 0(8): 46-49+74.
[10]	LU Jian, TU Guang-yi, WU Hai-yan. A Digital Watermarking Algorithm of Color Images Based on Surface Fitting [J]. Computer and Modernization, 2014, 0(7): 133-136.
[11]	ZHAI Teng-fei, LEI Hong, FENG Wen-sen. An AFM Image Leveling Algorithm Based on Robust Regression [J]. Computer and Modernization, 2014, 0(6): 88-93.
[12]	FAN Peng-fei;FAN Yong-hua;YU Yun-feng. H_∞/Mixed Sensitivity Controller Design for Airlaunched Cruise Missile [J]. Computer and Modernization, 2013, 1(7): 105-108.
[13]	LU Yang. ROPART：A Robust Network Partition Algorithm [J]. Computer and Modernization, 2013, 1(3): 67-70.
[14]	ZHANG Long;LI Hua-cong;HAN Xiao-bao. Novel e-modification Robust Adaptive Control for Aeroengine [J]. Computer and Modernization, 2012, 203(7): 72-74,8.
[15]	ZHAO Chun-li;WANG Ai-hui;. Precision Position Control for IPMC Artificial Muscle Based on Operator [J]. Computer and Modernization, 2012, 203(7): 68-71.