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...

ver descrição completa

Detalhes bibliográficos
Principais autores: Tsitsiklis, John N., Xu, Kuang
Outros Autores: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Formato: Artigo
Idioma:en_US
Publicado em: Association for Computing Machinery (ACM) 2014
Acesso em linha:http://hdl.handle.net/1721.1/90978
https://orcid.org/0000-0003-2658-8239
Descrição
Resumo: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.