The stability of join-the-shortest-queue models with general input and output processes

We re-visit the global - relative to control policies - stability of multiclass queueing networks. In these, as is known, it is generally insufficient that the nominal utilization at each server is below 100%. Certain policies, although work conserving, may destabilize a network that satisfies the nominal-load conditions; additional conditions on the primitives are needed for global stability (stability under any work-conserving policy). The global-stability region was fully ...

We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fi...

Recent development of peer-to-peer (P2P) services (e.g. streaming, file sharing, and storage) systems introduces a new type of queue systems that receive little attention before, where both job and server arrive and depart randomly. Current study on these models focuses on the stability condition, under exponential workload assumption. This paper extends existing result in two aspects. In the first part of the paper we relax the exponential workload assumption, and study the ...

A matching queue is described via a graph $G$ together with a matching policy. Specifically, to each node in the graph there is a corresponding arrival process of items which can either be queued, or matched with queued items in neighboring nodes. The matching policy specifies how items are matched whenever more than one matching is possible. Motivated by the increasing theoretical interest in such matching models, we investigate the question of (in)stability of matching queu...

We consider a GI/G/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has $c$ identical servers and can accommodate the maximal number of $K$ jobs. If a newly arriving job finds the full primary queue, it joins the orbit. The original primary jobs arrive to the system according to a renewal process. The jobs have general i.i.d. service times. A job in front of the orbit queue retries to ent...

The paper contains a discussion on a number of open problems in queueing theory. Some of them are known for decades, some are more recent. They relate to stability and to rare events. There is an idea to prepare a special issue of QUESTA on open problems, and this text may be considered as a prospective contribution to that. The choice of open problems reflects the author's own interests, and should not be taken as suggesting that these are the only, or even most important pr...

We study networks of interacting queues governed by utility-maximising service-rate allocations in both discrete and continuous time. For {\em finite} networks we establish stability and some steady-state moment bounds under natural conditions and rather weak assumptions on utility functions. These results are obtained using direct applications of Lyapunov-Foster-type criteria, and apply to a wide class of systems, including those for which fluid limit-based approaches are no...

Motivated by application in wireless networks, cloud computing, data centers etc, Stochastic Processing Networks have been studied in the literature under various asymptotic regimes. In the heavy-traffic regime, the steady state mean queue length is proved to be $O(\frac{1}{\epsilon})$ where $\epsilon$ is the heavy-traffic parameter, that goes to zero in the limit. The focus of this paper is on obtaining queue length bounds on prelimit systems, thus establishing the rate of c...

We establish a unified analytical framework for load balancing systems, which allows us to construct a general class $\Pi$ of policies that are both throughput optimal and heavy-traffic delay optimal. This general class $\Pi$ includes as special cases popular policies such as join-shortest-queue and power-of-$d$, but not the join-idle-queue (JIQ) policy. In fact, we show that JIQ, which is not in $\Pi$, is actually not heavy-traffic delay optimal. Owing to the significant fle...

Modern processing networks often consist of heterogeneous servers with widely varying capabilities, and process job flows with complex structure and requirements. A major challenge in designing efficient scheduling policies in these networks is the lack of reliable estimates of system parameters, and an attractive approach for addressing this challenge is to design robust policies, i.e., policies that do not use system parameters such as arrival and/or service rates for makin...