Abstract
High-availability seamless redundancy (HSR) protocol provides a zero failover time protection applicable to any Ethernet topology. HSR is also capable of tolerating multiple simultaneous failures, which further promotes the application of packet-based Ethernet protection. Deploying HSR in mesh networks may incur a significant unnecessary cost if not designed carefully. This paper addresses the problem of minimizing the cost of HSR mesh networks given a network availability constraint. We first develop an enumeration-based method to find the optimal design. However, due to the NP-hard complexity of the problem, this is limited to only small networks. Hence, a novel two-step heuristic algorithm is proposed. The algorithm first searches a design of an initial mesh topology compliant with HSR survivability conditions, and then an evolution process takes place to find a modification of the initial topology that satisfies the required availability. The simulation results show that our heuristic algorithm achieves a comparable performance close to optimal while being computationally scalable.