Local Restoration With Multiple Spanning Trees in Metro Ethernet Networks

Ethernet is becoming a preferred technology to be extended to metropolitan area networks (MANs) due to its low cost, simplicity, and ubiquity. However, current Ethernet lacks a fast failure recovery mechanism as it reconstructs the spanning tree after the failure is detected, which commonly requires tens of seconds. Some fast failure-handling methods based on multiple spanning trees have been proposed in the literature, but these approaches are either centralized or require periodic message broadcasting over the entire network. In this paper, we propose a local restoration mechanism for metro Ethernet using multiple spanning trees, which is distributed and fast and does not need failure notification. Upon failure of a single link, the upstream switch locally restores traffic to preconfigured backup spanning trees. We propose two restoration approaches, connection-based and destination-based, to select backup trees. We formulate the tree preconfiguration problem that includes working spanning tree assignment and backup spanning tree configuration. We prove that the preconfiguration problem is NP-complete and develop an integer linear programming model. We also develop heuristic algorithms for each restoration approach to reduce the computation complexity. To evaluate the effectiveness of our heuristic algorithms, we carry out the simulation on grid and random networks. The simulation results show that our heuristic algorithms have comparable performance close to the optimal solutions, and both restoration approaches can efficiently utilize the network bandwidth to handle single link failures.