VFMAs, Virtual-flow Multipath Algorithms for MPLS

This paper deals with IP traffic engineering (TE) for multipath selection in MPLS networks. A centralized and a distributed 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 according to their quality of service (QoS) requirements. 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 complex optimization problem into a tractable subproblem. The proposed multipath algorithms are shown to outperform single-path routing solutions by means of extensive simulation experiments.