1+N Protection in Polynomial Time: A Heuristic Approach
Source: Iowa State University
The generalized 1+N protection, protects N unicast connections by a single Steiner tree connecting all end points of the connections. By sending network coded packets on the protection Steiner tree in parallel with the working traffic, 1+N is able to recover from any single link failure without enduring the delay from switching to the backup path. Optimal cost provisioning and 1+N protection of a given set of connections is an NP-hard problem comprising of three NP-hard sub-problems: partitioning of the connections, finding edge disjoint primary paths and Steiner tree protection circuit for the subset of connections in each partition.