Search

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource demands (e.g. memory requirements) arrive over time and must be served by a cluster of servers. To improve throughput and delay, the scheduler can pack as many jobs as possible in each server, however the sum of the jobs’ resource demands cannot exceed the server’s capacity. Motivated by the increasing complexity of workloads in shared clusters, we consider a setting where jobs’ resource demands belong to a very large set of diverse types, or in the extreme case even infinitely many types, i.e. resource demands are drawn from a general unknown distribution over a possibly continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) type setting. We first characterize a fundamental limit on the maximum throughput in such setting. We then develop oblivious scheduling algorithms, based on Best-Fit and Universal Partitioning, that have low complexity and can achieve at least 1/2 and 2/3 of the maximum throughput respectively, without the knowledge of the resource demand distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we look at content placement in the high-dimensional regime: there are $$n$$ servers, and $${\mathrm {O}}(n)$$ distinct types of content. Each server can store and serve $${\mathrm {O}}(1)$$ types at any given time. Demands for these content types arrive and have to be served in an online fashion; over time, there are a total of $${\mathrm {O}}(n)$$ of these demands. We consider the algorithmic task of content placement: determining which types of content should be on which server at any given time, in the setting where the demand statistics (i.e., the relative popularity of each type of content) are not known a-priori, but have to be inferred from the very demands we are trying to satisfy. This is the high-dimensional regime because this scaling (everything being $${\mathrm {O}}(n)$$ ) prevents consistent estimation of demand statistics; it models many modern settings where large numbers of users, servers, and videos/webpages interact in this way. We characterize the performance of any scheme that separates learning and placement (i.e., which uses a portion of the demands to gain some estimate of the demand statistics, and then uses the same for the remaining demands), showing it is order-wise strictly suboptimal. We then study a simple adaptive scheme-which myopically attempts to store the most recently requested content on idle servers-and show it outperforms schemes that separate learning and placement. Our results also generalize to the setting where the demand statistics change with time. Overall, our results demonstrate that separating the estimation of demand, and the subsequent use of the same, is strictly suboptimal. [ABSTRACT FROM AUTHOR]