AAAI Publications, Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Planning the Transformation of Network Topologies
Young Yoon, Nathan Robinson, Vinod Muthusamy, Hans-Arno Jacobsen, Sheila A. McIlraith

Last modified: 2012-07-15


Refining a network topology is an important network management technique. Nevertheless, determining the appropriate steps to transform a network from one topology to another, in a way that minimizes service disruptions, has received little attention. This is a critical problem since service disruptions can be particularly harmful and costly for networks hosting mission-critical services. In this paper, we introduce the incremental network transformation (INT) problem and explore this problem in the context of automated planning. We define two metrics to measure the quality of generated transformation plans, one of which is amenable to classical propositional planning. We find that while state-of-the-art domain-independent planning techniques are effective at finding high-quality solutions for small problem instances, they cannot scale to solve realistically sized INT instances. To address the shortcomings of existing approaches, we developed a number of domain-dependent planners that use novel domain-specific heuristics. We empirically evaluated our planners on a wide range of synthetic network topologies. Our results illustrate that our automated planning inspired techniques are effective on realistically sized INT problems. We envision that our approach could eventually provide a compelling addition to the arsenal of techniques employed by network practitioners to support network refinement with minimal disruption to running services.


incremental network transformation; topology reconfiguration; automated planning; encoding

Full Text: PDF