Search for: All records

Researchers have developed a novel model inspired by quantum switches to address the complexities of matching requests for entangled qubits in a discrete-time system. The study examines two types of arrivals: requests for entangled qubits between nodes and qubits supplied by nodes, which are subject to decoherence over time. Unlike classical queueing models, this system features server-less multiway matching and correlated abandonments, posing unique analytical challenges. By applying a max-weight policy, the researchers characterized the system’s stability using a two-time-scale fluid limit to account for qubit abandonments. They demonstrated that the max-weight policy is throughput optimal, outperforming nonidling policies under certain conditions. Intriguingly, the study revealed counterintuitive behavior: The longest request queue may grow temporarily, even in a stable system. These findings offer new insights into managing quantum-inspired systems with practical constraints, opening avenues for further research into quantum network optimization. 

We consider a load-balancing system composed of a fixed number of single-server queues operating under the well-known join-the-shortest queue policy and where jobs/customers are impatient and abandon if they do not receive service after some (random) amount of time. In this setting, we characterize the centered and appropriately scaled steady-state queue-length distribution (hereafter referred to as limiting distribution) in the limit as the abandonment rate goes to zero at the same time as the load either converges to one or is larger than one. Depending on the arrival, service, and abandonment rates, we observe three different regimes of operation that yield three different limiting distributions. The first regime is when the system is underloaded, and its load converges relatively slowly to one. In this case, abandonments do not affect the limiting distribution, and we obtain the same exponential distribution as in the system without abandonments. When the load converges to one faster, we have the second regime, where abandonments become significant. Here, the system undergoes a phase transition, and the limiting distribution is a truncated Gaussian. Further, the third regime is when the system is heavily overloaded, and so, the queue lengths are very large. In this case, we show that the limiting distribution converges to a normal distribution. To establish our results, we first prove a weaker form of state space collapse by providing a uniform bound on the second moment of the (unscaled) perpendicular component of the queue lengths, which shows that the system behaves like a single-server queue. We then use exponential Lyapunov functions to characterize the limiting distribution of the steady-state queue-length vector. Funding: This work was supported by the National Science Foundation [Grants CMMI-2140534 and EPCN-2144316]. 

This paper studies the input-queued switch operating under the MaxWeight algorithm when the arrivals are according to a Markovian process. We exactly characterize the heavy-traffic scaled mean sum queue length in the heavy-traffic limit, and show that it is within a factor of less than 2 from a universal lower bound. Moreover, we obtain lower and upper bounds that are applicable in all traffic regimes and become tight in the heavy-traffic regime. We obtain these results by generalizing the drift method recently developed for the case of independent and identically distributed arrivals to the case of Markovian arrivals. We illustrate this generalization by first obtaining the heavy-traffic mean queue length and its distribution in a single-server queue under Markovian arrivals and then applying it to the case of an input-queued switch. The key idea is to exploit the geometric mixing of finite-state Markov chains, and to work with a time horizon that is chosen so that the error due to mixing depends on the heavy-traffic parameter. 

This paper studies the Heavy Traffic (HT) joint distribution of queue lengths in an Input-queued switch (IQ switch) operating under the MaxWeight scheduling policy. IQ switchserve as representative of SPNs that do not satisfy the socalled Complete Resource Pooling (CRP) condition, and consequently exhibit a multidimensional State Space Collapse (SSC). Except in special cases, only mean queue lengths of such non-CRP systems is known in the literature. In this paper, we develop the Transform method to study the joint distribution of queue lengths in non-CRP systems. The key challenge is in solving an implicit functional equation involving the Laplace transform of the HT limiting distribution. For the general n x n IQ switch that has n2 queues, under a conjecture on uniqueness of the solution of the functional equation, we obtain an exact joint distribution of the HT limiting queue-lengths in terms of a non-linear combination of 2n iid exponentials. 

In general, obtaining the exact steady-state distribution of queue lengths is not feasible. Therefore, we focus on establishing bounds for the tail probabilities of queue lengths. We examine queueing systems under Heavy Traffic (HT) conditions and provide exponentially decaying bounds for the probability P(∈q > x), where ∈ is the HT parameter denoting how far the load is from the maximum allowed load. Our bounds are not limited to asymptotic cases and are applicable even for finite values of ∈, and they get sharper as ∈ - 0. Consequently, we derive non-asymptotic convergence rates for the tail probabilities. Furthermore, our results offer bounds on the exponential rate of decay of the tail, given by -1/2 log P(∈q > x) for any finite value of x. These can be interpreted as non-asymptotic versions of Large Deviation (LD) results. To obtain our results, we use an exponential Lyapunov function to bind the moment-generating function of queue lengths and apply Markov's inequality. We demonstrate our approach by presenting tail bounds for a continuous time Join-the-shortest queue (JSQ) system. 

We study optimal pricing in a single server queue when the customers valuation of service depends on their waiting time. In particular, we consider a very general model, where the customer valuations are random and are sampled from a distribution that depends on the queue length. The goal of the service provider is to set dynamic state dependent prices in order to maximize its revenue, while also managing congestion. We model the problem as a Markov decision process and present structural results on the optimal policy. We also present an algorithm to find an approximate optimal policy. We further present a myopic policy that is easy to evaluate and present bounds on its performance. We finally illustrate the quality of our approximate solution and the myopic solution using numerical simulations.