IEICE TRANSACTIONS on Communications
Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure
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.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E94-B No.6 pp.1630-1639
- Publication Date
- 2011/06/01
- Publicized
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.E94.B.1630
- Type of Manuscript
- PAPER
- Category
- Fundamental Theories for Communications
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nozomu KATAYAMA, Takeshi FUJIMURA, Hiroyoshi MIWA, Noriaki KAMIYAMA, Haruhisa HASEGAWA, Hideaki YOSHINO, "Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure" in IEICE TRANSACTIONS on Communications,
vol. E94-B, no. 6, pp. 1630-1639, June 2011, doi: 10.1587/transcom.E94.B.1630.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E94.B.1630/_p
Copy
@ARTICLE{e94-b_6_1630,
author={Nozomu KATAYAMA, Takeshi FUJIMURA, Hiroyoshi MIWA, Noriaki KAMIYAMA, Haruhisa HASEGAWA, Hideaki YOSHINO, },
journal={IEICE TRANSACTIONS on Communications},
title={Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure},
year={2011},
volume={E94-B},
number={6},
pages={1630-1639},
abstract={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.},
keywords={},
doi={10.1587/transcom.E94.B.1630},
ISSN={1745-1345},
month={June},}
Copy
TY - JOUR
TI - Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure
T2 - IEICE TRANSACTIONS on Communications
SP - 1630
EP - 1639
AU - Nozomu KATAYAMA
AU - Takeshi FUJIMURA
AU - Hiroyoshi MIWA
AU - Noriaki KAMIYAMA
AU - Haruhisa HASEGAWA
AU - Hideaki YOSHINO
PY - 2011
DO - 10.1587/transcom.E94.B.1630
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E94-B
IS - 6
JA - IEICE TRANSACTIONS on Communications
Y1 - June 2011
AB - 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.
ER -
English
