A heuristic routing algorithm with erasure correcting code based instantaneous recovery technique

This paper proposes a heuristic routing algorithm to design routes for all possible source destination pairs by provisioning erasure correcting code based instantaneous recovery technique with optimal traffic splitting, which was addressed for a source destination pair in a prior work. We consider a static routing problem in networks having the coding capability. When the links in a network have finite capacities, assigning routing for all possible source destination pair by using this instantaneous recovery technique are mutually dependent, and this issue was not addressed. For the route designing purpose, one need to check routing for exponential number of traffic splitting number combinations. If the number of combinations to be considered, which equals the multiplication of each individual maximum possible traffic splitting numbers of all pairs considered, becomes extremely large obtaining a routing solution within a practical time is not possible. In order to achieve a routing solution within a practical time, the proposed heuristic algorithm gives highest priority to the pair either with the largest cost or with the largest resource saving effect. For all source destination pairs the total path costs of implementing erasure correcting code based instantaneous recovery technique, and conventional 1+1 protection technique are computed. Almost 20% resource saving w.r.to 1+1 protection is achieved in our examined networks.