In cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently, there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input data sets or phenomena, such as failures and stragglers. To overcome these limitations, we designed Kraken, a system that allows to dynamically update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the applications but allows to modify reservations at runtime. Kraken achieves this through an online resource reservation scheme, which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations and a preliminary Hadoop prototype.

In multi-tenant cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input datasets or phenomena such as failures and stragglers. To overcome these limitations, we designed KRAKEN, a system that allows tenants to dynamically request and update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations.

Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network to their physical counterparts: essentially a graph embedding problem. However, existing embedding algorithms such as Oktopus and Proteus often ignore a crucial dimension of the embedding problem, namely data locality: the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data, in case of redundant storage, the algorithm should also optimize the replica selection. This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs, interestingly, our hardness results also hold in uncapacitated networks of small diameter.

It is well-known that without strict network bandwidth guarantees, application performance in multi-tenant cloud environments is unpredictable. While recently proposed systems support explicit bandwidth reservation mechanisms, they require the resource schedules to be announced ahead of time. We argue that this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to stragglers. We in this paper present KRAKEN, a system that allows tenants to dynamically request and update minimum resource guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme, and by optimally embedding and reconfiguring virtual networks.