
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery
Abu Hena Al MUKTADIR Eiji OKI
Publication
IEICE TRANSACTIONS on Communications
Vol.E97B
No.1
pp.87104 Publication Date: 2014/01/01
Online ISSN: 17451345
DOI: 10.1587/transcom.E97.B.87
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Internet Keyword: routing, network coding, 1+1 protection, integer linear programming, heuristic algorithm,
Full Text: PDF(1.7MB)>>
Summary:
1+1 protection provides instantaneous proactive recovery from any single link failure by duplicating and sending the same source data onto two disjoint paths. Other resource efficient recovery techniques to deal with single link failure require switching operations at least at both ends, which restrict instantaneous recovery. However, the 1+1 protection technique demands at least double network resources. Our goal is to minimize the resources required for 1+1 protection while maintaining the advantage of instantaneous recovery. It was reported that the network coding (NC) technique reduces resource utilization in 1+1 protection, and in order to determine an optimum NC aware set of routes that minimizes the required network resources for 1+1 protection, an Integer Quadratic Programming (IQP) formulation has already been addressed. Solving an IQP problem requires large amount of memory (cannot be determined exactly) and special algorithms by the mathematical programming solver. In this paper our contributions consist of two parts. First, we formulate the optimization problem, corresponding to the IQP model, as an Integer Linear Programming (ILP) formulation, which is solvable by any linear programming solver, and so its memory and time requirements are smaller. However, the presented ILP model works well in smallscale and mediumscale networks, but fails to support largescale networks due to excessive memory requirements and calculation time. Second, to deal with these issues, a heuristic algorithm is proposed to determine the best possible NC aware set of routes in largescale networks. Numerical results show that our strategies achieve almost double the resource saving effect than the conventional minimalcost routing policy in the examined mediumscale and large scale networks.

