A simple method for balancing network utilization and quality of routing

Applegate and Cohen (2003) computational complexity design demand oblivious routing schemes that achieve low oblivious ratio with no or approximate knowledge of traffic demands. We investigate the quality of oblivious routing with respect to path dispersion, which is concerned with the number of paths; and path variation, which is concerned with how far the paths are from the shortest paths and the variation of path lengths. The results show the dispersion and the variation are high in general. We propose a penalty method to improve the quality of oblivious routing. The penalty method strikes a good balance between the conflicting objectives of minimizing the oblivious ratio and optimizing the quality of oblivious routing. Moreover, we apply the simple penalty method to the problem of minimizing the maximum link utilization given a traffic matrix. With the penalty method, we can achieve almost the same maximum link utilization, and improve the quality of routing to almost perfect, i.e. one or two paths that are very close to the shortest paths between each pair of nodes.