A novel Lagrangian-relaxation to the minimum cost multicommodity flow problem and its application to OSPF traffic engineering

被引：11
|
作者：
Rétvári, G [1 ]
Bíró, JJ [1 ]
Cinkler, T [1 ]
机构：
[1] Univ Budapest, Dept Telecommun & Media Informat, High Speed Networks Lab, QoSIT Lab, H-1117 Budapest, Hungary
来源：
ISCC2004: NINTH INTERNATIONAL SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS, VOLS 1 AND 2, PROCEEDINGS | 2004年
关键词：
D O I：
10.1109/ISCC.2004.1358664
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The Minimum Cost Multicommodity Flow problem plays a central role in today's operations research theory with applications ranging from transportation and logistics to telecommunications network routing. In this paper, we introduce a novel Lagrangian-relaxation technique, which, given an initial feasible solution, can solve the minimum cost multicommodity flow problem as a sequence of single-commodity flow problems. Our methodology is best suited for OSPF traffic engineering, because it can rapidly improve a given path set towards approximate optimality while simultaneously provides the link Weights, which implement the paths as shortest paths.
引用
收藏
页码：957 / 962
页数：6
相关论文
共 27 条
123