Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay

DOI10.1214/15-SSY179zbMATH Open1356.60150arXiv1502.05786MaRDI QIDQ2956541FDOQ2956541

Authors: Arpan Mukhopadhyay, A. Karthik, Ravi R. Mazumdar 

Publication date: 18 January 2017

Abstract: We consider the job assignment problem in a multi-server system consisting of $N$ parallel processor sharing servers, categorized into $M$ ($llN$) different types according to their processing capacity or speed. Jobs of random sizes arrive at the system according to a Poisson process with rate $Nlambda$. Upon each arrival, a small number of servers from each type is sampled uniformly at random. The job is then assigned to one of the sampled servers based on a selection rule. We propose two schemes, each corresponding to a specific selection rule that aims at reducing the mean sojourn time of jobs in the system. We first show that both methods achieve the maximal stability region. We then analyze the system operating under the proposed schemes as $Noinfty$ which corresponds to the mean field. Our results show that asymptotic independence among servers holds even when $M$ is finite and exchangeability holds only within servers of the same type. We further establish the existence and uniqueness of stationary solution of the mean field and show that the tail distribution of server occupancy decays doubly exponentially for each server type. When the estimates of arrival rates are not available, the proposed schemes offer simpler alternatives to achieving lower mean sojourn time of jobs, as shown by our numerical studies.

Full work available at URL: https://arxiv.org/abs/1502.05786

Recommendations

• Choosing among heterogeneous server clouds
• Asymptotic independence of queues under randomized load balancing
• Analysis of job assignment with batch arrivals among heterogeneous servers
• Managing Queues with Heterogeneous Servers
• Persistent-idle load-distribution

zbMATH Keywords

stabilityasymptotic independencepropagation of chaosmean field limitprocessor sharingrandomized job assignment

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic network models in operations research (90B15)

Cited In (10)

• Computational Science and Its Applications – ICCSA 2004
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems
• Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems
• Analysis of job assignment with batch arrivals among heterogeneous servers
• Choosing among heterogeneous server clouds
• On the impact of job size variability on heterogeneity-aware load balancing
• Exploiting data locality to improve performance of heterogeneous server clusters
• Throughput and delay optimality of power-of-\(d\) choices in inhomogeneous load balancing systems
• Mean-field fluctuations at diffusion scale in threshold-based randomized routing for processor sharing systems and applications

This page was built for publication: Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2956541)