Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure

Nozomu KATAYAMA  Takeshi FUJIMURA  Hiroyoshi MIWA  Noriaki KAMIYAMA  Haruhisa HASEGAWA  Hideaki YOSHINO  

Publication
IEICE TRANSACTIONS on Communications   Vol.E94-B    No.6    pp.1630-1639
Publication Date: 2011/06/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E94.B.1630
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
Keyword: 
quality of service,  backbone network,  optimization problem,  NP-complete,  approximation algorithm,  

Full Text: PDF>>
Buy this Article


Summary: 
When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable as possible, i.e., minimizing the difference in hop length between the original flow and the rerouted flow is important for network reliability. Therefore, network service providers need a method for designing networks that stabilizes the flow hop length and maintains connectivity during a link or node failure with limited investment cost. First, we formulate the network design problem used for determining the set of links to be added that satisfies the required constraints on flow hop length stability, connectivity, and node degree. Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. Evaluation of the performance of these algorithms by using 39 backbone networks of commercial ISPs and networks generated by two well-known models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.