Behaviors and effectiveness of rerouting: a study

Rerouting has been used in traffic management to perform dynamic load balancing. The aim of rerouting is to reassign the path/bandwidth allocations of current traffic trunks in a network in order to minimize the probability of blocking future resource requests. We investigate how the effectiveness of rerouting can be affected by the characteristic of the underlying network topology. We established baseline measures through two resource allocation algorithms: a shortest distance path algorithm (SDP), that represents the best common practice without rerouting, and a global rerouting algorithm that is based on a provably ε-optimal algorithm for the multi-commodity flow problem. We propose two rerouting algorithms based on the basic SDP algorithm that selects for rerouting either from traffic trunks with the same source-destination pairs (local rerouting) or from all traffic trunks (global rerouting). The effectiveness of rerouting is highly related to the average node degree. As the connectivity of a graph increases, rerouting tends to be more effective. However, rerouting does not always perform better when connectivity is increased. Significant performance improvement only occurs within a relatively small range of connectivities when a rerouting algorithm is able to find alternative paths and SDP cannot. Furthermore, local rerouting is sufficient to exploit most of the benefits of rerouting and it is not necessary to utilize much more computationally intensive global rerouting algorithms. Finally, we investigate the rerouting frequency vs. blocking trade-off and show that for local rerouting, the best performance can be achieved by a rerouting frequency of only 30%.