Job assignment in large-scale service systems with affinity relations

DOI10.1007/S11134-019-09633-YMaRDI QIDQ2297809zbMATH OpenOpenAlexWikidataFDO

Authors Ellen Cardinaels, Sem Borst, Johan S. H. van Leeuwaarden

Publication date 20 February 2020

Published in Queueing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

load balancingnetwork topologyjob schedulingfluid limitstochastic coupling

Mathematics Subject Classification ID

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)

Abstract: We consider load balancing in service systems with affinity relations between jobs and servers. Specifically, an arriving job can be allocated to a fast, primary server from a particular selection associated with this job or to a secondary server to be processed at a slower rate. Such job-server affinity relations can model network topologies based on geographical proximity, or data locality in cloud scenarios. We introduce load balancing schemes that allocate jobs to primary servers if available, and otherwise to secondary servers. A novel coupling construction is developed to obtain stability conditions and performance bounds using a coupling technique. We also conduct a fluid limit analysis for symmetric model instances, which reveals a delicate interplay between the model parameters and load balancing performance.

Recommendations

• scientific article; zbMATH DE number 4172728
• Comparing job allocation schemes where service demand is unknown
• Staffing large-scale service systems with distributional uncertainty
• Multi-objective Large-Scale Staff Allocation
• scientific article; zbMATH DE number 679866
• Assignment of a job load in a distributed system: A multicriteria design method
• Asymptotically optimal staffing of service systems with joint QoS constraints
• Analysis of job assignment with batch arrivals among heterogeneous servers
• Search and the Efficient Assignment of Workers to Jobs

Cites work

• scientific article; zbMATH DE number 3852171 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3207495 (Why is no real title available?)
• A simple dynamic routing problem
• Dynamic and equilibrium behavior of controlled loss networks
• Heavy traffic resource pooling in parallel-server systems
• Large loss networks
• Loss Networks
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMS
• On the stability of a partially accessible multi-station queue with state-dependent routing
• Optimality of the shortest line discipline
• Point processes and queues. Martingale dynamics
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Sample Path Criteria for Weak Majorization
• Sample path methods in the control of queues
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• The Effect of Increasing Routing Choice on Resource Pooling
• The equilibrium states of large networks of Erlang queues
• Universality of power-of-\(d\) load balancing in many-server systems

Cited in

(4)

• Power-of-two sampling in redundancy systems: the impact of assignment constraints
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Stochastic non-bipartite matching models and order-independent loss queues
• Comparing job allocation schemes where service demand is unknown

This page was built for publication: Job assignment in large-scale service systems with affinity relations

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