Traffic Engineering with Constrained Multipath Routing in MPLS Networks

Youngseok LEE  Yongho SEOK  Yanghee CHOI  

IEICE TRANSACTIONS on Communications   Vol.E87-B   No.5   pp.1346-1356
Publication Date: 2004/05/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
traffic engineering,  multipath routing,  load balancing,  optimization,  LP,  MPLS,  

Full Text: PDF(595.8KB)>>
Buy this Article

A traffic engineering problem in a network consists of setting up paths between the edge nodes of the network to meet traffic demands while optimizing network performance. It is known that total traffic throughput in a network, or resource utilization, can be maximized if a traffic demand is split over multiple paths. However, the problem formulation and practical algorithms, which calculate the paths and the load-splitting ratios by taking bandwidth, the route constraints or policies into consideration, have not been much touched. In this paper, we formulate the constrained multipath-routing problems with the objective of minimizing the maximum of link utilization, while satisfying bandwidth, the maximum hop count, and the not-preferred node/link list in Linear Programming (LP). Optimal solutions of paths and load-splitting ratios found by an LP solver are shown to be superior to the conventional shortest path algorithm in terms of maximum link utilization, total traffic volume, and number of required paths. Then, we propose a heuristic algorithm with low computational complexity that finds near optimal paths and load-splitting ratios satisfying the given constraints. The proposed algorithm is applied to Multi-Protocol Label Switching (MPLS) that can permit explicit path setup, and it is tested in a fictitious backbone network. The experiment results show that the heuristic algorithm finds near optimal solutions.