Adaptive importance sampling in routing and wavelength assignment problem

Dynamic routing and wavelength assignment in all-optical networks is a well-known problem for which many reasonably well working heuristic algorithms have been proposed in the literature. The problem can be also approached in the Markov decision process (MDP) framework. Due to the huge size of the state space only heuristic algorithms are viable in practice. However, so called first policy iteration can be used to enhance the performance of any given (standard) policy. In some cases the improvement can be considerable. For the first policy iteration one needs to estimate so called relative values of states, which are defined as the expected difference in future rewards/costs between two states. The relative values can be estimated by short simulations starting the system from a given state. As the blocking probability in network is usually very low this leads to a problem where rare events must be estimated. Also, depending on the system's current state some arrival realisations are more likely to cause blockings than others. An adaptive importance sampling method is proposed to overcome these difficulties.