Min-min edge-disjoint path pairs with constraints on common nodes

Finding edge-disjoint path pairs has been recognized as a vital issue in terms of the fault tolerance and survivability of networks. In many practical scenarios, in order to reduce standby and restart energy consumption and improve data transmission efficiency, we need to consider a constraint to control the delay difference of data transmission on each common node of two edge-disjoint paths. Meanwhile, a large number of common nodes tend to cause data congestion and increase the probability that faulty common nodes break two edge-disjoint paths. Based on these, we propose the problem of finding min-min edge-disjoint path pairs under the constraints of delay difference and the number of common nodes. To address the problem, we discretize each node according to its all processing time intervals to construct an equivalent problem in an auxiliary time digraph with delay division node sets. Then, we design conflicting node exclusion (CoNE) algorithm, a heuristic algorithm, using divide-and-conquer strategy on the conflicting node set. Finally, through extensive simulations, comparing with other related algorithms, we show that CoNE is significantly effective in large-scale networks.