Optimal Near-Hitless Network Failure Recovery Using Diversity Coding

Link failures in wide area networks are common and cause significant data losses. Mesh-based protection schemes offer high capacity efficiency but they are slow, require complex signaling, and instable. Diversity coding is a proactive coding-based recovery technique which offers near-hitless (sub-ms) restoration with a competitive spare capacity requirement with respect to other techniques. In this thesis, an optimal algorithm is developed for pre-provisioning of the static traffic using both systematic and non-systematic diversity coding. A Mixed Integer Programming (MIP) formulation is developed for systematic diversity coding which requires many fewer integer variables and constraints than similar optimal coding-based formulations. In all scenarios, diversity coding results in smaller restoration time, higher transmission integrity, and much reduced signaling complexity than the existing techniques in the literature at the expense of slightly lower capacity efficiency than Shared Path Protection (SPP) and p-cycle protection. The drawbacks of the earlier implementations of diversity coding are the low scalability and restricted coding structure. To overcome these, a simple column generation-based design algorithm and a novel advanced diversity coding technique to achieve near-hitless recovery over large networks are proposed. The design framework consists of two parts: a main problem and sub problem. Simulation results over large networks with arbitrary topologies suggest that both the novel coding structure and the novel design algorithm lead to higher capacity efficiency for near-hitless recovery. Moreover, this thesis presents a bidirectional coding-based scheme, named Coded Path Protection (CPP). In addition to a systematic approach of building valid coding structures, this paper presents an optimal and simple capacity placement and coding group formation algorithm. The algorithm converts the sharing structure of any solution of an SPP technique into a coding structure with minimum extra capacity. Simulation results confirm that the CPP is significantly faster than both SPP and Shared Link Protection (SLP) and more capacity efficient than SLP. This thesis also investigates the dynamic provisioning of the traffic on-demand. In dynamic provisioning, an Integer Linear Programming (ILP)-based optimal algorithm covers both of the systematic and non-systematic diversity coding. The performance of proposed dynamic provisioning technique is similar to that of pre-provisioning.