Upper bound of network capacity and a static optimal packet routing strategy

• We propose a link-based formulation for a max-flow-min-cost (MFMC) problem.
• The upper bound of network capacity is obtained by solving the MFMC problem.
• We develop a static optimal routing strategy based on the MFMC problem.
• The strategy outperforms existing routing strategies.
• The strategy can achieve network capacity very close to its upper bound.

In this paper, we propose a max-flow-min-cost (MFMC) problem to obtain the upper bound of network capacity and develop an efficient packet routing strategy. The MFMC problem is formulated as two linear programs (LP). The optimal solutions of the two LPs are the upper bound of network capacity (i.e., maximum network flow rate) and an optimal packet flow pattern with minimum total free flow travel time under the maximum network flow rate, respectively. We also develop a static optimal routing strategy (SORS), which proportionally deliver packets along the path according to the optimal packet flow pattern. Simulation results indicate that the proposed SORS outperforms existing routing strategies in terms of both network capacity and traffic efficiency. Furthermore, the network capacity achieved by the SORS is very close to its upper bound.