A heuristic routing algorithm for network coding aware 1+1 protection route design for instantaneous recovery

This paper proposes a heuristic routing algorithm to design instantaneous recovery protection routes for all possible source destination pairs by provisioning network coding (NC) based 1+1 protection technique. We consider a static routing problem in networks where each node has the coding capability, and the exact traffic demand matrix is given. In the proposed heuristic algorithm a network with N nodes is divided into N scenarios, where each node is chosen as the common destination and k nodes among the remaining ones are the sources, where 2 ≤ k ≤N-1. By dividing the network into several scenarios with k sources and a common destination (k S D), all the possible source destination pairs, according to the given traffic matrix, are considered. It was reported that a mathematical programming approach to determine NC based 1+1 protection routes for any kSD scenario is an intractable problem for large k values. In the proposed heuristic algorithm we tackle 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. The largest effective gain first policy ensures the best possible resource saving for each of the selected 2SD or 3SD scenario. We compare the total path costs of NC based 1+1 protection for all possible source destination pairs, obtained by our proposed heuristic algorithm, with that of the conventional 1+1 protection technique (without NC). Numerical results observes that almost 15% resource saving is achieved in our examined networks.