Towards Planning the Transformation of Overlays

Abstract

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.