Flexible queueing architectures

DOI10.1287/OPRE.2017.1620zbMATH Open1380.90093arXiv1505.07648OpenAlexW1519971520MaRDI QIDQ4598652FDOQ4598652

John N. Tsitsiklis, Kuang Xu

Publication date: 15 December 2017

Published in: Operations Research (Search for Journal in Brave)

Abstract: We study a multi-server model with $n$ flexible servers and $n$ queues, connected through a bipartite graph, where the level of flexibility is captured by the graph's average degree, $d_n$. Applications in content replication in data centers, skill-based routing in call centers, and flexible supply chains are among our main motivations. We focus on the scaling regime where the system size $n$ tends to infinity, while the overall traffic intensity stays fixed. We show that a large capacity region and an asymptotically vanishing queueing delay are simultaneously achievable even under limited flexibility ($d_{n}lln$). Our main results demonstrate that, when $d_{n}gglnn$, a family of expander-graph-based flexibility architectures has a capacity region that is within a constant factor of the maximum possible, while simultaneously ensuring a diminishing queueing delay for all arrival rate vectors in the capacity region. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed job-to-server assignments on the connectivity graph. For comparison, we also analyze a natural family of modular architectures, which is simpler but has provably weaker performance.

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

Recommendations

• Modeling and analysis of flexible queueing systems
• Dynamic Server Allocation for Queueing Networks with Flexible Servers
• Maximizing throughput in queueing networks with limited flexibility
• Maximizing Throughput in Queueing Networks with Limited Flexibility
• Multiple-server system with flexible arrivals

zbMATH Keywords

queueingasymptoticsflexibilityresource poolingdynamic matchingexpander graph

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Deterministic scheduling theory in operations research (90B35)

Cited In (10)

• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Process Flexibility for Multiperiod Production Systems
• Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems
• On the Optimal Design of a Bipartite Matching Queueing System
• Query batching optimization in database systems
• Dynamic Stochastic Matching Under Limited Time
• Concurrent expandable AMQs on the basis of quotient filters
• On the Capacity of Information Processing Systems
• Utilizing partial flexibility to improve emergency department flow: Theory and implementation
• Modeling and analysis of flexible queueing systems

This page was built for publication: Flexible queueing architectures

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