This paper deals with IP traffic engineering (TE) for multipath selection in MPLS network domains. A centralized and a distributed virtual-flow routing algorithms are proposed, which aggregate IP flows entering the MPLS domain, and optimally partition them among virtual flows that are forwarded on multiple paths. The routing algorithms dynamically select multiple label switched paths (LSPs), taking into account the available bandwidth of links in the network in order to balance the traffic load and avoid network congestion due to bottleneck. The virtual-flow multipath routing problem is formulated as a multicommodity network flow (MCNF) problem, and is solved by implementing on-line the Dantzig-Wolfe decomposition method, which is proven to converge to the optimal solution through an iterative procedure that divides the difficult global optimization problem into a tractable subproblem. The proposed centralized (VFMA-C) and distributed (VFMA-D) virtual-flow multipath algorithms implement a dynamic preventive scheme for congestion control by optimally distributing aggregated IP data flows, according to their quality of service (QoS) requirements, among the most under-utilized links in the MPLS network. The proposed multipath algorithms are shown to outperform singlepath routing solutions such as the constraint shortest path first (CSPF) and the bandwidth-based shortest path (BSPR) routing algorithms, and to achieve the performance targets by means of extensive simulation experiments.

Keywords

MPLS networks, multi-path routing, quality of service (QoS), load-balancing.