
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Traffic Engineering with Constrained Multipath Routing in MPLS Networks
Youngseok LEE Yongho SEOK Yanghee CHOI
Publication
IEICE TRANSACTIONS on Communications
Vol.E87B
No.5
pp.13461356 Publication Date: 2004/05/01
Online ISSN:
DOI:
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Network Keyword: traffic engineering, multipath routing, load balancing, optimization, LP, MPLS,
Full Text: PDF(595.8KB)>>
Summary:
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 loadsplitting ratios by taking bandwidth, the route constraints or policies into consideration, have not been much touched. In this paper, we formulate the constrained multipathrouting problems with the objective of minimizing the maximum of link utilization, while satisfying bandwidth, the maximum hop count, and the notpreferred node/link list in Linear Programming (LP). Optimal solutions of paths and loadsplitting 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 loadsplitting ratios satisfying the given constraints. The proposed algorithm is applied to MultiProtocol 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.

