Fine Two-Phase Routing with Traffic Matrix

This paper proposes an IP finely-distributed load- balanced routing scheme based on two-phase routing over shortest paths, where the traffic matrix is given. It is called the fine two-phase routing (F-TPR) scheme. In F-TPR, traffic is distributed from a source node to intermediate nodes more finely, compared to the original TPR. F-TPR determines the distribution ratios to intermediate nodes for each source-destination node pair independently. To determine an optimum set of the distribution ratios, a linear programming (LP) formulation is derived. We compare the F-TPR scheme against the TPR scheme and the sophisticated traffic engineering (TE) scheme of multi-protocol label switching (MPLS-TE). Numerical results show that F-TPR greatly reduces the network congestion ratio compared to TPR. In addition, F-TPR provides almost the same network congestion ratio as that of MPLS-TE, the difference is surprisingly less than 0.1% for various experimented network topologies.