Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery

Abu Hena Al MUKTADIR; Eiji OKI

doi:10.1587/transcom.E97.B.87

Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery

Abu Hena Al MUKTADIR, Eiji OKI

Full Text Views

0

Share
Cite this

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 small-scale and medium-scale networks, but fails to support large-scale 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 large-scale networks. Numerical results show that our strategies achieve almost double the resource saving effect than the conventional minimal-cost routing policy in the examined medium-scale and large scale networks.

Publication: IEICE TRANSACTIONS on Communications Vol.E97-B No.1 pp.87-104

Publication Date: 2014/01/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.E97.B.87

Type of Manuscript: PAPER

Category: Internet

Authors

Abu Hena Al MUKTADIR
The University of Electro-Communications
Eiji OKI
The University of Electro-Communications

Keyword

routing, network coding, 1+1 protection, integer linear programming, heuristic algorithm

Cite this

Copy

Abu Hena Al MUKTADIR, Eiji OKI, "Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery" in IEICE TRANSACTIONS on Communications, vol. E97-B, no. 1, pp. 87-104, January 2014, doi: 10.1587/transcom.E97.B.87.
Abstract: 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 small-scale and medium-scale networks, but fails to support large-scale 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 large-scale networks. Numerical results show that our strategies achieve almost double the resource saving effect than the conventional minimal-cost routing policy in the examined medium-scale and large scale networks.
URL: https://globals.ieice.org/en_transactions/communications/10.1587/transcom.E97.B.87/_p

Copy

@ARTICLE{e97-b_1_87,
author={Abu Hena Al MUKTADIR, Eiji OKI, },
journal={IEICE TRANSACTIONS on Communications},
title={Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery},
year={2014},
volume={E97-B},
number={1},
pages={87-104},
abstract={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 small-scale and medium-scale networks, but fails to support large-scale 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 large-scale networks. Numerical results show that our strategies achieve almost double the resource saving effect than the conventional minimal-cost routing policy in the examined medium-scale and large scale networks.},
keywords={},
doi={10.1587/transcom.E97.B.87},
ISSN={1745-1345},
month={January},}

Copy

TY - JOUR
TI - Optimum Route Design in 1+1 Protection with Network Coding for Instantaneous Recovery
T2 - IEICE TRANSACTIONS on Communications
SP - 87
EP - 104
AU - Abu Hena Al MUKTADIR
AU - Eiji OKI
PY - 2014
DO - 10.1587/transcom.E97.B.87
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E97-B
IS - 1
JA - IEICE TRANSACTIONS on Communications
Y1 - January 2014
AB - 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 small-scale and medium-scale networks, but fails to support large-scale 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 large-scale networks. Numerical results show that our strategies achieve almost double the resource saving effect than the conventional minimal-cost routing policy in the examined medium-scale and large scale networks.
ER -