A new competitive ratio for network applications with hard performance guarantees

Network applications in highly mobile systems need to employ online algorithms that do not rely on precise predictions about future events. In order to meet hard performance guarantees in the presence of unknown future events, common practice is to add redundancy to the systems. In this paper, we define a new competitive ratio that reflects the amount of redundancy needed to ensure some given performance guarantees. We study two special applications, namely, online job allocations in cloud computing and online scheduling in delayed mobile offloading, and propose online algorithms for each of them. We prove that our algorithms are optimal. By comparing our algorithms with commonly used other policies, we also show that our policies need much less redundancy than those commonly used policies to provide the same degree of performance guarantees.