
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.

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.E94B
No.6
pp.16301639 Publication Date: 2011/06/01
Online ISSN: 17451345
DOI: 10.1587/transcom.E94.B.1630
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Fundamental Theories for Communications Keyword: quality of service, backbone network, optimization problem, NPcomplete, approximation algorithm,
Full Text: PDF(2.6MB)>>
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 NPcomplete 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 wellknown models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.

