Traveling repairman problem for optical network recovery to restore virtual networks after a disaster

摘要

Virtual networks mapped over a physical network can suffer disconnection and/or outage due to disasters. After a disaster occurs, the network operator should determine a repair schedule and then send repairmen to repair failures following the schedule. The schedule can change the overall effect of a disaster by changing the restoration order of failed components. In this study, we introduce the traveling repairman problem to help the network operator make the schedule after a disaster. We measure the overall effect of a disaster from the damage it caused, and we define the damage as the numbers of disconnected virtual networks, failed virtual links, and failed physical links. Our objective is to find an optimal schedule for a repairman to restore the optical network with minimum damage. We first state the problem; then a mixed integer linear program (MILP) and three heuristic algorithms, namely dynamic programming (DP), the greedy algorithm (GR), and simulated annealing (SA), are proposed. Finally, simulation results show that the repair schedules using MILP and DP results get the least damage but the highest complexity; GR gets the highest damage with the lowest complexity, while SA has a good balance between damage and complexity.