Large‐Scale Network‐Oriented Protection Algorithm Through Efficient Tree Granularity Brownian‐Like Motion

ABSTRACT In extensive and decentralized systems with numerous end‐to‐end communications, inadvertent disconnection can lead to the complete severance of the upper‐level applications. Reliable communication can be ensured by designating links as trunks. These trunks maintain connectivity even when a large number of nontrunk links are simultaneously severed. Due to the computational complexity of cut enumeration, prior algorithms are restricted to topologies with a limited number of vertices. To address this challenge, in order to efficiently search in the potential tree space containing all cuts, we search at the granularity of the tree in a tree space that is homomorphic to the cut space and effectively discover a large number of target cuts by combining with Brownian‐like motion. The found quasi‐trunk links are then filtered to select a minimal‐cost subset of trunk links, thereby guaranteeing the desired sustained connectivity. Experimental results demonstrate that the algorithm achieves a three‐order of magnitude acceleration compared to the optimal method in small topologies, with limited extra cost. In large topologies, our trunk assignment method exhibits resilience to at least 99.9% stochastic link failures within a reasonable execution time.