Reconfiguring a topology is an important management technique to sustain high efficiency and robustness of an overlay. But, the problem of transforming the overlay from an old topology to a newly refined topology, at runtime, has received relatively little attention. The key challenge is to minimize the disruption that can be caused by topology transformation operations. Excessive disruption can be costly and harmful and thus it may hamper the decision to migrate to a better topology. To address this issue, we solve a problem of finding an appropriate sequence of steps to transform a topology that incurs the least service disruption. We refer to this problem as an incremental topology transformation (ITT) problem. The ITT problem can be formulated as an automated planning problem and can be solved with numerous off-the-shelf planning techniques. However, we found that state-of-the-art domain-independent planning techniques did not scale to solve large ITT problem instances. This shortcoming motivated us to develop a suite of planners that use novel domain-specific heuristics to guide the search for a solution. We empirically evaluated our planners on a wide range of topologies. Our results illustrate that our planners offer a viable solution to a diversity of ITT problems. We envision that our approach could eventually provide a compelling addition to the arsenal of techniques currently employed by the administrators of distributed overlay networks.

In this paper we revisit the problem of generating query plans using AI automated planning with a view to leveraging significant recent advances in state-of-the-art planning techniques. Our efforts focus on the specific problem of cost-based join-order optimization for conjunctive relational queries, a critical component of production-quality query optimizers. We characterize the general query-planning problem as a delete-free planning problem, and query plan optimization as a context-sensitive cost-optimal planning problem. We propose algorithms that generate high-quality query plans, guaranteeing optimality under certain conditions. Our approach is general, supporting the use of a broad suite of domain-independent and domain-specific optimization criteria. Experimental results demonstrate the effectiveness of AI planning techniques for query plan generation and optimization.