Joint Bandwidth Allocation and Path Selection in WANs with Path Cardinality Constraints

In this paper, we study the joint bandwidth allocation and path selection problem, which is an extension of the well-known network utility maximization (NUM) problem, via solving a multi-objective minimization problem under path cardinality constraints. Specifically, such a problem formulation captures various types of objectives including proportional fairness, average delay, as well as load balancing. In addition, in order to handle the "unsplittable flows", path cardinality constraints are added, making the resulting optimization problem quite challenging to solve due to intrinsic non-smoothness and nonconvexity. Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem. However, we provide a novel solution framework based on the linearized alternating direction method of multipliers (LADMM) to split the original problem with coupling terms into several subproblems. We then derive that these subproblems, albeit nonconvex nonsmooth, are actually simple to solve and easy to implement, which can be of independent interest. Under some mild assumptions, we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point. Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various base-lines.