Open Access
Scalable State Space Search with Structural-Bottleneck Heuristics for Declarative IT System Update Automation
-
Full Text Views
114
- Cite this
- Free PDF (2.1MB)
Summary :
As IT systems, including network systems using SDN/NFV technologies, become large-scaled and complicated, the cost of system management also increases rapidly. Network operators have to maintain their workflow in constructing and consistently updating such complex systems, and thus these management tasks in generating system update plan are desired to be automated. Declarative system update with state space search is a promising approach to enable this automation, however, the current methods is not enough scalable to practical systems. In this paper, we propose a novel heuristic approach to greatly reduce computation time to solve system update procedure for practical systems. Our heuristics accounts for structural bottleneck of the system update and advance search to resolve bottlenecks of current system states. This paper includes the following contributions: (1) formal definition of a novel heuristic function specialized to system update for A* search algorithm, (2) proofs that our heuristic function is consistent, i.e., A* algorithm with our heuristics returns a correct optimal solution and can omit repeatedly expansion of nodes in search spaces, and (3) results of performance evaluation of our heuristics. We evaluate the proposed algorithm in two cases; upgrading running hypervisor and rolling update of running VMs. The results show that computation time to solve system update plan for a system with 100 VMs does not exceed several minutes, whereas the conventional algorithm is only applicable for a very small system.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E102-B No.3 pp.439-451
- Publication Date
- 2019/03/01
- Publicized
- 2018/09/20
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.2018NVP0009
- Type of Manuscript
- Special Section PAPER (Special Section on Network Virtualization and Network Softwarization for Diverse 5G Services)
- Category
Authors
Takuya KUWAHARA
NEC
Takayuki KURODA
NEC
Manabu NAKANOYA
NEC
Yutaka YAKUWA
NEC
Hideyuki SHIMONISHI
NEC
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
Takuya KUWAHARA, Takayuki KURODA, Manabu NAKANOYA, Yutaka YAKUWA, Hideyuki SHIMONISHI, "Scalable State Space Search with Structural-Bottleneck Heuristics for Declarative IT System Update Automation" in IEICE TRANSACTIONS on Communications,
vol. E102-B, no. 3, pp. 439-451, March 2019, doi: 10.1587/transcom.2018NVP0009.
Abstract: As IT systems, including network systems using SDN/NFV technologies, become large-scaled and complicated, the cost of system management also increases rapidly. Network operators have to maintain their workflow in constructing and consistently updating such complex systems, and thus these management tasks in generating system update plan are desired to be automated. Declarative system update with state space search is a promising approach to enable this automation, however, the current methods is not enough scalable to practical systems. In this paper, we propose a novel heuristic approach to greatly reduce computation time to solve system update procedure for practical systems. Our heuristics accounts for structural bottleneck of the system update and advance search to resolve bottlenecks of current system states. This paper includes the following contributions: (1) formal definition of a novel heuristic function specialized to system update for A* search algorithm, (2) proofs that our heuristic function is consistent, i.e., A* algorithm with our heuristics returns a correct optimal solution and can omit repeatedly expansion of nodes in search spaces, and (3) results of performance evaluation of our heuristics. We evaluate the proposed algorithm in two cases; upgrading running hypervisor and rolling update of running VMs. The results show that computation time to solve system update plan for a system with 100 VMs does not exceed several minutes, whereas the conventional algorithm is only applicable for a very small system.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2018NVP0009/_p
Copy
@ARTICLE{e102-b_3_439,
author={Takuya KUWAHARA, Takayuki KURODA, Manabu NAKANOYA, Yutaka YAKUWA, Hideyuki SHIMONISHI, },
journal={IEICE TRANSACTIONS on Communications},
title={Scalable State Space Search with Structural-Bottleneck Heuristics for Declarative IT System Update Automation},
year={2019},
volume={E102-B},
number={3},
pages={439-451},
abstract={As IT systems, including network systems using SDN/NFV technologies, become large-scaled and complicated, the cost of system management also increases rapidly. Network operators have to maintain their workflow in constructing and consistently updating such complex systems, and thus these management tasks in generating system update plan are desired to be automated. Declarative system update with state space search is a promising approach to enable this automation, however, the current methods is not enough scalable to practical systems. In this paper, we propose a novel heuristic approach to greatly reduce computation time to solve system update procedure for practical systems. Our heuristics accounts for structural bottleneck of the system update and advance search to resolve bottlenecks of current system states. This paper includes the following contributions: (1) formal definition of a novel heuristic function specialized to system update for A* search algorithm, (2) proofs that our heuristic function is consistent, i.e., A* algorithm with our heuristics returns a correct optimal solution and can omit repeatedly expansion of nodes in search spaces, and (3) results of performance evaluation of our heuristics. We evaluate the proposed algorithm in two cases; upgrading running hypervisor and rolling update of running VMs. The results show that computation time to solve system update plan for a system with 100 VMs does not exceed several minutes, whereas the conventional algorithm is only applicable for a very small system.},
keywords={},
doi={10.1587/transcom.2018NVP0009},
ISSN={1745-1345},
month={March},}
Copy
TY - JOUR
TI - Scalable State Space Search with Structural-Bottleneck Heuristics for Declarative IT System Update Automation
T2 - IEICE TRANSACTIONS on Communications
SP - 439
EP - 451
AU - Takuya KUWAHARA
AU - Takayuki KURODA
AU - Manabu NAKANOYA
AU - Yutaka YAKUWA
AU - Hideyuki SHIMONISHI
PY - 2019
DO - 10.1587/transcom.2018NVP0009
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E102-B
IS - 3
JA - IEICE TRANSACTIONS on Communications
Y1 - March 2019
AB - As IT systems, including network systems using SDN/NFV technologies, become large-scaled and complicated, the cost of system management also increases rapidly. Network operators have to maintain their workflow in constructing and consistently updating such complex systems, and thus these management tasks in generating system update plan are desired to be automated. Declarative system update with state space search is a promising approach to enable this automation, however, the current methods is not enough scalable to practical systems. In this paper, we propose a novel heuristic approach to greatly reduce computation time to solve system update procedure for practical systems. Our heuristics accounts for structural bottleneck of the system update and advance search to resolve bottlenecks of current system states. This paper includes the following contributions: (1) formal definition of a novel heuristic function specialized to system update for A* search algorithm, (2) proofs that our heuristic function is consistent, i.e., A* algorithm with our heuristics returns a correct optimal solution and can omit repeatedly expansion of nodes in search spaces, and (3) results of performance evaluation of our heuristics. We evaluate the proposed algorithm in two cases; upgrading running hypervisor and rolling update of running VMs. The results show that computation time to solve system update plan for a system with 100 VMs does not exceed several minutes, whereas the conventional algorithm is only applicable for a very small system.
ER -
English
