A coding-aware reliable route design scheme for instantaneous recovery

This paper proposes a coding-aware reliable route design scheme to tackle any single link failure for the traffic demands of all possible source destination pairs in a network. Instantaneous recovery is ensured in the proposed scheme by employing network coding (NC) based \(1+1\) protection technique. The proposed scheme considers all possible source destination pairs by creating N scenarios with k sources and a common destination (kSD) according to a given traffic matrix with unequal demands. Each of the N nodes in the network is chosen as the common destination and k nodes, where \(2\le k\le N-1\), among the remaining ones are the sources. We prove that optimum coding-aware \(1+1\) protection route design in kSD scenarios is an NP-hard problem. The proposed scheme tackles this intractable problem by choosing either two or three sources out of k sources at a time according to the largest effective gain first policy, and then routing is assigned to the selected 2SD or 3SD scenario by using our developed mathematical models. We compare the total path costs of NC based \(1+1\) protection for all possible source destination pairs, obtained by our proposed scheme, with that of the conventional \(1+1\) protection technique (without NC). Numerical results observes that 7–16 % of resource saving is achieved in our examined networks. Computation time, example scenarios, and other solution approaches for the proposed scheme are also discussed.