Scalable State Space Search with Structural-Bottleneck Heuristics for Declarative IT System Update Automation

Takuya KUWAHARA  Takayuki KURODA  Manabu NAKANOYA  Yutaka YAKUWA  Hideyuki SHIMONISHI  

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)
orchestration,  task planning,  system update automation,  automated planning,  change management,  model-based engineering,  declarative provisioning,  network function virtualization,  

Full Text: FreePDF

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.