Virtualization typically involves remapping physical resources (e.g., storage, memory, processors) into logical resources so that these computational resources can be shared in dynamic environments. The remapping process has an online component, in that requests arrive and the system responds. In traditional online problems, resources are thought of as irrevocably assigned. However, in virtualized environments, previously allocated resources can be reassigned or reallocated. This project formalizes how computational resources can be reallocated efficiently when there is some cost for the reallocation.
The project investigates the algorithmic complexity of reallocation problems arising from large-scale systems design, and especially reallocation algorithms that are universal with respect to reallocation-cost functions. The research plan addresses problems in memory and storage reallocation, scaleout and sharding in storage systems, reallocation for dynamic combinatorial and geometric structures (finite-element meshes, metric spaces), and classical online allocation problems (scheduling and bin packing). The aim of the project is three-fold: (1) to study the asymptotic performance of reallocation, (2) to obtain results that are universal with respect to a wide class of reallocation cost functions, and (3) to quantify the performance of known heuristics in widespread use.
The way computation works today, on laptops and desktops, in supercomputers and data centers, and in cloud computing, critically depends upon virtualization. Hardware trends (e.g., multicore, solid state disks) and software trends (e.g., data-centric computing) mean that virtualization is becoming even more prevalent. Reallocation algorithms have a large impact on the performance of virtualized systems. The algorithmic approach outlined in this project promises to improve the performance, scalability, and predictably of large systems. As such, this research show great promise for improving the general infrastructure of computing in the next decade.
Modern computers share resources between competing processes. Virtualualization is the name given to the set of techniques for resource sharing, and typically involves remapping physical resources (e.g., storage, memory, processors) into logical resources so that these computational resources can be shared in dynamic environments. The remapping process has an online component, in that requests arrive and the system responds. In traditional online problems, resources are thought of as irrevocably assigned. However, in virtualized environments, previously allocated resources can be reassigned or reallocated. This project formalizes the notation of how computational resources can be reallocated efficiently when there is some cost for the reallocation. The project investigates the algorithmic complexity of reallocation problems arising from large-scale systems design, and especially reallocation algorithms that are universal with respect to reallocation-cost functions. The research plan addresses problems in memory and storage reallocation, scaleout and sharding in storage systems, reallocation for dynamic combinatorial and geometric structures (finite-element meshes, metric spaces), and classical online allocation problems (scheduling and bin packing). One of the most challenging aspects of systems algorithmics is acurately modeling the cost of an operation on a complex and changing system. The approach taken in I/O intensive systems has been to produce algorithms that are universal with respect to system parameters. The project investigates ways to extend such an approach to resource reallocation problems. In this project we have (1) studied the asymptotic performance of reallocation algorithms, (2) obtained results that are universal with respect to a wide class of reallocation cost functions, and (3) evaluated new methods and methods in widespread use both theoretically and empirically.
