Behaviors and effectiveness of rerouting: A study

Abstract

Rerouting has been used in traffic management to perform dynamic load balancing. The aim of rerouting is to reassign path/bandwidth allocations of current traffic trunks in a network in order to minimize the probability of blocking future resource requests. In this work, we are interested in investigating how the effectiveness of rerouting can be affected by the characteristic of the underlying network topology. In order to evaluate the blocking performance achievable by rerouting, 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 multi-commodity flow problem. We proposed 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). Our results show that 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 like SDP-LR is able to find alternative paths and SDP cannot. Furthermore, local reroutng 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%. © 2005 IEEE.