The efficient execution of data center jobs that require simultaneous use of different resource types is of critical importance. When processing capacity is the crucial resource for jobs execution, the locution multiserver jobs is used, where the term server indicates processors or CPU cores providing processing capacity. Each multiserver job carries a requirement expressed in number of servers it requires to run, and service duration. Achieving efficient execution of multiserver jobs relies heavily on effective scheduling of jobs on the existing servers. Several schedulers have been proposed, aimed at improving resource utilization, at the cost of increased complexity. Due to the limited availability of theoretical results on scheduler behavior in the case of multiserver jobs, data center schedulers are often designed based only on managers' experience. In this paper, aiming to expand the understanding of the multiserver job schedulers' performance, we study Small Shuffle (SMASH) schedulers, a class of nonpreemptive, service time oblivious, window-based multiserver job scheduling algorithms that strike a balance between simplicity and efficient resource utiliza tion, while allowing performance evaluation in simpler settings. SMASHimplies only a marginal increase in complexity compared to FIFO, yet it delivers substantial performance improvements for multiserver jobs. Depending on the system parameters, SMASH can nearly double the system's stability region with respect to FIFO, leading to significantly lower response times across a broad region of loads. Moreover, the magnitude of this improvement scales with the chosen window size, allowing performance to be tuned to the system's operating conditions. We first study the capacity of SMASH with analytical tools in simple settings, then we investigate the performance of SMASH and other schedulers with simulations under more realistic workloads, designed with parameters derived from measurements of real data centers. Results show that SMASH offers a very good compromise between performance and complexity.

The Multiserver Job Queuing Model (MJQM) is a queuing system that plays a key role in the study of the dynamics of resource allocation in data centers. The MJQM comprises a waiting line with infinite capacity and a large number of servers. In this paper, we look at the limiting case in which the number of servers is infinite. Jobs are termed “multiserver” because each one is characterized by a resource demand in terms of number of simultaneously used servers and by a service duration. Job classes are defined by collecting all jobs that require the same number of servers. Job service times are independent and identically distributed random variables whose distributions depend on the class of the job. We consider the case of only two job classes: “small” jobs use a fixed number of servers, while “big” jobs use all servers in the system. The service discipline is First-In First-Out (FIFO). This means that if the job at the Head-of-Line (HOL) cannot enter service because the number of free servers is not sufficient to meet the job requirement, it blocks all subsequent jobs, even if there are sufficient free servers for them. Despite its importance, only few results exist for the MJQM, whose analysis is challenging, especially because the MJQM is not work-conserving. This implies that even the stability region of the MJQM is known only in special cases. In a previous work, we obtained a closed-form stability condition for MJQM with big and small jobs under the assumption of exponentially distributed service times for small jobs. In this paper, we compute the stability condition of MJQM with an infinite number of servers processing big and small jobs, considering different distributions of the service times of small jobs. Simulations are used to support the analytical results and to investigate the impact of service time distributions on the average job waiting time before saturation.

Datacenters comprise a variety of resources (processors, memory, input/output modules, etc.) that are shared among requests for the execution of computing jobs submitted by datacenter users. Jobs differ in their frequency of arrivals, demand for resources, and execution times. Resource sharing generates contention, especially in heavily loaded systems, that must therefore implement effective scheduling policies for incoming jobs. The First-In First-Out (FIFO) policy is often used for batch jobs, but may produce under-utilization of resources, in terms of wasted servers. This is due to the fact that a job that requires many resources can block jobs arriving later that could be served because they require fewer resources. The mathematical construct often used to study this problem is the Multiserver Job Queuing Model (MJQM), where servers represent resources which are requested and used by jobs in different quantities. Unfortunately, very few explicit results are known for the MJQM, especially at realistic system loads (i.e., before saturation), and hardly any considers the case of non-exponential service time distributions. In this paper, we propose the first exact analytical model of the non-saturated MJQM in case of two classes of customers with service times having 2-phase Coxian distribution. Our analysis is based on the matrix geometric method. Our results provide insight into datacenter dynamics, thus supporting the design of more complex schedulers, capable of improving performance and energy consumption within large datacenters.

Modern data centers feature an extensive array of cores that handle quite a diverse range of jobs. Recent traces, shared by leading cloud data center enterprises like Google and Alibaba, reveal that the constant increase in data center services and computational power is accompanied by a growing variability in service demand requirements. The number of cores needed for a job can vary widely, ranging from one to several thousands, and the number of seconds a core is held by a job can span more than five orders of magnitude. In this context of extreme variability, the policies governing the allocation of cores to jobs play a crucial role in the performance of data centers. It is widely acknowledged that the First-In First-Out (FIFO) policy tends to underutilize available computing capacity due to the varying magnitudes of core requests. However, the impact of the extreme variability in service demands on job waiting and response times, that has been deeply investigated in traditional queuing models, is not as well understood in the case of data centers, as we will show. To address this issue, we investigate the dynamics of a data center cluster through analytical models in simple cases, and discrete event simulations based on real data. Our findings emphasize the significant impact of service demand variability, both in terms of requested cores and service times, and allow us to provide insight for enhancing data center performance. In particular, we show how data center performance can be improved thanks to the control of the interplay between service and waiting times through the assignment of cores to jobs.

Datacenters comprise large quantities of processors, memory, and input/output modules. These resources are shared among requests (jobs) submitted by datacenter users. Jobs differ in their frequency of arrivals, demand for resources, and execution times. Resource sharing generates contention, especially in heavily loaded systems, that must therefore implement effective scheduling policies for incoming jobs. The First-In First-Out (FIFO) policy is often used for batch jobs, but may produce under-utilization of resources, in terms of wasted servers. This is due to the fact that a job that requires many resources can block jobs arriving later that could be served because they require fewer resources. The mathematical construct often used to study this problem is the Multiserver Job Queuing Model (MJQM), where servers represent resources which are requested and used by jobs in different quantities. Unfortunately, very few explicit results are known for the MJQM, especially at realistic system loads (i.e., before saturation). In this paper, we propose the first exact analytical model of the non-saturated MJQM in case of two classes of customers with exponentially distributed service times and an arbitrary number of identical servers. Our analysis is based on the matrix geometric method. Our results provide insight into datacenter dynamics, thus supporting the design of more complex schedulers, capable of improving performance and energy consumption within large datacenters.