This paper introduces the service migration problem and formalize, it in the competitive analysis framework. For a single-server setting, we present a randomized online algorithm MIX and a deterministic online algorithm CEN that achieve a competitive ratio of in the worst case, i.e., without any knowledge of the future demand, where is the substrate size. The competitive ratio of MIX and CEN is almost optimal in the sense that we can prove that there does not exist any online algorithm whose competitive ratio is smaller than W. We describe how a standard dynamic program can be used to compute very general optimal offline solutions. To complement the formal analysis, we report on our simulation results in different settings. These results indicate that our algorithms adapt well to moderate request dynamics and correlation. The competitive ratio may grow slower in the network size on average than predicted by our formal analysis.
You are here: Home / ieee projects 2014 / A Study on Online Service Migration from a Competitive Analysis Perspective