Minimizing the Maximum Link Utilization in Multicast Multi-Commodity Flow Networks

In this letter, we first formulate the network coded multicast multi-commodity flow model to minimize the maximum link utilization (MLU). Due to the effects of multipath and network coding, the obtained MLU can serve as a fundamental lower bound in traffic engineering. We then present a dual-dual decomposition approach whereby the original problem can be decomposed into a series of minimum-cost flow subproblems with only one centralized computation. The subproblems can be efficiently solved in a parallel or distributed manner. Numerical experiment is finally given to validate the effectiveness of the proposed approach.