A coding-aware reliable route design scheme for instantaneous recovery

Abu Hena Al Muktadir () and Eiji Oki ()
Additional contact information
Abu Hena Al Muktadir: The University of Electro-Communications
Eiji Oki: The University of Electro-Communications

Telecommunication Systems: Modelling, Analysis, Design and Management, 2016, vol. 62, issue 3, No 2, 495-509

Abstract: Abstract This paper proposes a coding-aware reliable route design scheme to tackle any single link failure for the traffic demands of all possible source destination pairs in a network. Instantaneous recovery is ensured in the proposed scheme by employing network coding (NC) based $$1+1$$ 1 + 1 protection technique. The proposed scheme considers all possible source destination pairs by creating N scenarios with k sources and a common destination (kSD) according to a given traffic matrix with unequal demands. Each of the N nodes in the network is chosen as the common destination and k nodes, where $$2\le k\le N-1$$ 2 ≤ k ≤ N - 1 , among the remaining ones are the sources. We prove that optimum coding-aware $$1+1$$ 1 + 1 protection route design in kSD scenarios is an NP-hard problem. The proposed scheme tackles this intractable problem by choosing either two or three sources out of k sources at a time according to the largest effective gain first policy, and then routing is assigned to the selected 2SD or 3SD scenario by using our developed mathematical models. We compare the total path costs of NC based $$1+1$$ 1 + 1 protection for all possible source destination pairs, obtained by our proposed scheme, with that of the conventional $$1+1$$ 1 + 1 protection technique (without NC). Numerical results observes that 7–16 % of resource saving is achieved in our examined networks. Computation time, example scenarios, and other solution approaches for the proposed scheme are also discussed.

Keywords: Route design; Network coding; NP-hard; Instantaneous recovery; Integer linear programming (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11235-015-0089-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:telsys:v:62:y:2016:i:3:d:10.1007_s11235-015-0089-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11235

DOI: 10.1007/s11235-015-0089-3

Access Statistics for this article

Telecommunication Systems: Modelling, Analysis, Design and Management is currently edited by Muhammad Khan

More articles in Telecommunication Systems: Modelling, Analysis, Design and Management from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().