Fast spanning tree reconnection mechanism for resilient Metro Ethernet networks

Abstract

The low cost, high transmission rate and ubiquity of current Ethernet lead to the possibility of bringing Ethernet into Metropolitan Area Networks (MANs). However, the traditional spanning tree based Ethernet protocol does not meet the requirement for MANs in terms of network resilience, despite the advancement of Ethernet standardization and commercialization. In this paper, we propose a fast spanning tree reconnection (FSTR) mechanism for Metro Ethernet networks to handle single link failure. Upon failure of a link on a spanning tree, a distributed failure recovery protocol is activated to reconnect the broken spanning tree using a reconnect-link. We present the details of the protocol, including failure notification and forwarding table reconfiguration procedures. The pre-configuration of the reconnect-links to reconnect each spanning tree is formulated as an integer linear programming (ILP) problem. We prove that the pre-configuration problem is NP-complete. We develop an efficient algorithm based on 2-edge connectivity augmentation that can achieve close approximation to the optimal solutions. The numerical results of FSTR mechanism on different network topologies show its features of efficiency and fast recovery. © 2011 Elsevier B.V. All rights reserved.