On-line resources allocation for Asynchronous Transfer Mode networks with rerouting

This paper presents an application we developed for France Telecom R&D to solve a difficult real-life network problem. The problem takes place in an Asynchronous Transfer Mode network administration context and consists in planning demands of connection over a period of 1 year. A new demand is accepted if both bandwidth and Quality of Service requirements are satisfied. Demands are not known prior to the assignment and must be performed on-line according to their arrival. Moreover, the acceptance or the rejection of a demand must be decided within a given time of 1 min. First, we look for a route satisfying the new demand. In case of failure, we try to reroute some already accepted connections in order to satisfy this new demand. Rerouting has been modelled as a Weighted Constraint Satisfaction Problem (WCSP) and solved by VNS/LDS + CP, a hybrid method well suited for solving WCSPs in on-line contexts. Experiments show that our rerouting enables to accept an average of 67% of demands that would be rejected otherwise.