Queueing system topologies with limited flexibility

We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. Applications in content replication in data centers, skill-based routing in call centers, and flexibl...

Full description

Bibliographic Details
Main Authors: Tsitsiklis, John N., Xu, Kuang
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Association for Computing Machinery (ACM) 2014
Online Access:http://hdl.handle.net/1721.1/90978
https://orcid.org/0000-0003-2658-8239
_version_ 1826209100616171520
author Tsitsiklis, John N.
Xu, Kuang
author2 Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
author_facet Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Tsitsiklis, John N.
Xu, Kuang
author_sort Tsitsiklis, John N.
collection MIT
description We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. 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 (robustness) and diminishing queueing delay (performance) are jointly achievable even under very limited flexibility (d(n) l n). In particular, when d(n) gg ln n , a family of random-graph-based interconnection topologies is (with high probability) capable of stabilizing all admissible arrival rate vectors (under a bounded support assumption), while simultaneously ensuring a diminishing queueing delay, of order ln n/ d(n), as n-> ∞. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed partial matchings on the connectivity graph.
first_indexed 2024-09-23T14:17:16Z
format Article
id mit-1721.1/90978
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T14:17:16Z
publishDate 2014
publisher Association for Computing Machinery (ACM)
record_format dspace
spelling mit-1721.1/909782022-09-28T19:46:21Z Queueing system topologies with limited flexibility Tsitsiklis, John N. Xu, Kuang Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Tsitsiklis, John N. Xu, Kuang We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. 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 (robustness) and diminishing queueing delay (performance) are jointly achievable even under very limited flexibility (d(n) l n). In particular, when d(n) gg ln n , a family of random-graph-based interconnection topologies is (with high probability) capable of stabilizing all admissible arrival rate vectors (under a bounded support assumption), while simultaneously ensuring a diminishing queueing delay, of order ln n/ d(n), as n-> ∞. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed partial matchings on the connectivity graph. National Science Foundation (U.S.) (Grant CMMI-1234062) MIT-Xerox Fellowship Program 2014-10-20T13:09:43Z 2014-10-20T13:09:43Z 2013-06 Article http://purl.org/eprint/type/ConferencePaper 01635999 http://hdl.handle.net/1721.1/90978 John N. Tsitsiklis and Kuang Xu. 2013. Queueing system topologies with limited flexibility. SIGMETRICS Perform. Eval. Rev. 41, 1 (June 2013), 167-178. https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1145/2494232.2465757 ACM SIGMETRICS Performance Evaluation Review Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain
spellingShingle Tsitsiklis, John N.
Xu, Kuang
Queueing system topologies with limited flexibility
title Queueing system topologies with limited flexibility
title_full Queueing system topologies with limited flexibility
title_fullStr Queueing system topologies with limited flexibility
title_full_unstemmed Queueing system topologies with limited flexibility
title_short Queueing system topologies with limited flexibility
title_sort queueing system topologies with limited flexibility
url http://hdl.handle.net/1721.1/90978
https://orcid.org/0000-0003-2658-8239
work_keys_str_mv AT tsitsiklisjohnn queueingsystemtopologieswithlimitedflexibility
AT xukuang queueingsystemtopologieswithlimitedflexibility