A Fast Heuristic Algorithm for Minimizing Congestion in the MPLS Networks

• 作者: Chengwen Jiao Mingming Zhu Suixiang Gao Wenguo Yang Yinben Xia
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: MPLS-Network k-Splittable Flow Minimum CONGESTION HEURISTIC Algorithm
• 年，卷（期）: 2014,（8）
• 页码范围: 294-302
• 页数: 9页
• 分类号: O1

摘要

In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.