首页 | 官方网站   微博 | 高级检索  
     


An Efficient Algorithm for Global Path Optimization in MPLS Networks
Authors:Bal#xE;zs G#xE;bor J#xF;zsa  Zolt#xE;n Kir#xE;ly  G#xE;bor Magyar  #xC;ron Szentesi
Affiliation:(1) Traffic Analysis and Network Performance Laboratory, Ericsson Research, P.O. Box 107, H-1030 Budapest, Hungary
Abstract:This paper proposes an algorithm to solve the optimization of label switched paths (LSPs) in multiprotocol label switching (MPLS) networks. The underlying optimization problem in this task is the well-known unsplittable multicommodity flow problem equipped with practically relevant objective functions and specialized with hard technical requirements.The proposed heuristic algorithm is based on network flow theory. It incorporates iterative shortest path search and performs adaptive edge weight adjustments in order to successfully satisfy all the required traffic demands and to maximize user-defined objectives. The robust algorithm facilitates the incorporation of several strategic and optimization objectives and the fulfillment of certain hard technical requirements of the target problem domain as well. Novel features of the approach include a new adaptive path allocation/deallocation strategy based on the identification of bottleneck links, demand ordering and preprocessing phases, and a systematic path allocation control method.The efficiency of the method is empirically shown on randomly generated networks with practical sizes and topologies, and on a real-world IP (Internet Protocol) backbone network. The algorithm is able to successfully solve difficult problem instances comprising very large instances with 1000 nodes, 3500 edges and 999000 traffic demands. The computational tests demonstrate that the proposed approach can be efficiently applied to solve problem instances that embed MPLS specific hard technical requirements. Furthermore, it is shown that our algorithm offers significantly better performance than the straightforward adaptations of existing methods that were developed for related network optimization problems. Namely, our algorithm produces acceptable results quicker, it can solve problems that were not previously solvable, and it yields better results than the alternative methods. The extensive empirical tests demonstrate the combinatorial properties of the target problem and the performance aspects of the algorithm and its components as well.
Keywords:MPLS  path optimization  multicommodity flow  unsplittable
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号