論文

査読有り
2014年1月

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

IEICE Transactions on Communications
  • Abu Hena Al Muktadir
  • ,
  • Eiji Oki

97-B
1
開始ページ
87
終了ページ
104
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1587/transcom.E97.B.87
出版者・発行元
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

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 lLP 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.

リンク情報
DOI
https://doi.org/10.1587/transcom.E97.B.87
DBLP
https://dblp.uni-trier.de/rec/journals/ieicet/MuktadirO14
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000330554100011&DestApp=WOS_CPL
URL
http://search.ieice.org/bin/summary.php?id=e97-b_1_87
URL
https://dblp.uni-trier.de/db/journals/ieicet/ieicet97b.html#MuktadirO14
ID情報
  • DOI : 10.1587/transcom.E97.B.87
  • ISSN : 0916-8516
  • eISSN : 1745-1345
  • DBLP ID : journals/ieicet/MuktadirO14
  • Web of Science ID : WOS:000330554100011

エクスポート
BibTeX RIS