Summary: The canonical multi-path network utility maximization (NUM) model which is extended directly from the single-path NUM has been studied widely in the literature. Most of the previous approaches do not specify the case of subflows on paths with different characteristics. Moreover, the transport protocol derived from the canonical multi-path NUM exhibits flappiness in the subflows because of the non-strictly convexity of the optimization problem. This paper introduces a modified multi-path NUM model and proposes a novel approach to overcome the mentioned issues. Using Jensen’s inequality, the multi-path NUM is approximated to a strictly convex and separable problem which can be solved efficiently by dual-based decomposition method. The algorithm successively solving a sequence of approximation problems is proven to converge at the global optimum of the original problem. Moreover, considering the separable form of the approximation utility and the dual-based nature of the proposed algorithm, the reverse engineering frameworks of the current TCPs are used to develop a series of multi-path TCPs that are compatible with corresponding regular single-path TCPs.