New diversity coding design algorithms for link failure recovery in communication networks

Diversity coding is a form of network coding for link failure recovery in communication networks. Since it employs coding, there is no feedback signaling, and that feature makes it very fast. Previously, we have employed this basic technique and linear programming to come up with fast link failure recovery systems that also have small extra capacity. One approach, Diversity Coding Tree, employs mixed integer programming and results in very fast restoration. Another approach is called Coded Path Protection, and employs integer linear programming and has the advantage of small extra capacity. This latter technique is based on former work that considers a communication network as consisting of bidirectional links. However, employing coding on bidirectional links results in larger restoration times than the former technique. In this paper, we develop an improved version of our former techniques. This new technique employs a mixed integer linear programming formulation and results in restoration times as fast as Diversity Coding Tree with reduced extra capacity.