Jumping Fluid Models and Delay Stability of Max-Weight Dynamics Under Heavy-Tailed Traffic

1. Introduction

We say that a random variable is light-tailed if moments of order $2+ϵ$ are finite for some $ϵ>0$; otherwise, we say that it is heavy-tailed. We study queueing networks that operate under the max-weight (MW) scheduling policy for the case in which some queues receive heavy-tailed traffic, whereas some other queues receive light-tailed traffic; our motivation stems from the fact that heavy-tailed processes are often natural models of the inputs to computer and communications networks (Foss et al. 2011). Queues that receive heavy-tailed traffic are naturally delay unstable, that is, they incur infinite expected delay as an immediate consequence of the Pollaczek–Khintchine formula. However, it is also known that, because of the relatively complex max-weight dynamics, some of the queues that receive light-tailed traffic may also end up delay unstable.¹ Our aim is to develop conditions that determine whether any particular queue is delay stable or not.

This problem is studied extensively (Markakis 2013; Markakis et al. 2014, 2018; Nair et al. 2015), and a necessary condition for delay stability is given in Markakis et al. (2014, 2018). In particular, Markakis et al. (2018) consider the associated fluid model, initialized at zero, except for a positive initial condition at some queue that receives heavy-tailed arrivals. If another queue happens to eventually become positive under that fluid model, one can then conclude that the latter queue is delay unstable. This result leads to the natural question whether this condition is also sufficient, that is, whether delay stability is guaranteed when any such fluid trajectory (with a positive initialization at any single one of the queues that receive heavy-tailed traffic) keeps the queue of interest at zero level. Such a sufficiency result might appear plausible because, in models involving heavy-tailed random variables, large fluctuations are often the consequence of a single abnormally large value in the underlying heavy-tailed random variables (Pakes 1975, Veraverbeke 1977, Anantharam 1989, Asmussen 1996, Durrett 1980, Foss et al. 2011).

1.1. Our Contributions

We start in Section 3 by showing that the aforementioned possible sufficiency result does not hold. We accomplish this by providing a fairly simple example in which a large arrival at any single heavy-tailed queue does not cause a certain queue of interest to grow, but a combination of two large arrivals, at two different heavy-tailed queues, can result in large backlogs at the queue of interest. We also provide necessary and sufficient conditions for delay stability in that particular example, and then provide intuition for a possible more general result. Interestingly, delay instability manifests itself only when the tail exponents (defined precisely in Section 2.2) of the heavy-tailed arrival processes lie in a specific range. As a consequence, we need to take these exponents explicitly into account, something that traditional fluid models cannot do.

We then generalize, by developing general and tight (necessary and sufficient) conditions for delay stability, in terms of deterministic fluid-like models in which there can be multiple jumps (in different queues and possibly at different times) at the heavy-tailed queues.

Our conditions are not easy to test computationally, but this seems unavoidable: because the conditions are necessary and sufficient, the complexity of testing them reflects the intrinsic complexity of testing delay stability. On the positive side, our conditions

1. Provide a conceptual understanding of the mechanism that results in delay instability.

2. Can be checked in special cases, for instance, for the example in Section 3; see Section 5.3.

On the technical side, our general conditions involve a small but technically crucial reformulation of the delay stability problem. To understand the underlying issue, note that fluid models do not always lead to definite conclusions when the underlying system is marginally stable but are generally effective when used to analyze “robust” properties. For this reason, we consider a network with given nominal arrival rates and focus on robust stability. Namely, we ask whether a certain queue is delay stable for all arrival processes with given tail exponents and for all (possibly time-varying) arrival rates that lie in some open ball around the nominal ones. When the problem is framed that way, definitive necessary and sufficient conditions for (robust) delay stability become possible. Furthermore, with this formulation, it is only the nominal arrival rates and the tail exponents that matter as opposed to the details of the distribution of the input traffic.

Finally, earlier works Markakis (2013) and Markakis et al. (2018) show that Lyapunov functions with certain structural properties can be used to certify delay stability. But it was not known whether this methodology is “complete,” that is, whether delay stability can always be established through a suitable Lyapunov function. Our results make progress in this direction, for the case of “very heavy” tails, that is, when there exists some $\gamma >0$ for which arriving traffic moments of order $1+\gamma$ are infinite but γ can be arbitrarily small. For this regime, we derive some necessary and sufficient conditions for delay stability: we show that a Lyapunov function of a special kind can be used to certify delay stability together with a partial converse.

1.2. Related Works on Multiple Big Jumps

As already mentioned, in several systems that involve heavy-tailed random variables, large fluctuations are the consequence of a single large jump in the underlying heavy-tailed variables. However, this is not always the case. There are known systems that have small fluctuations under a single large jump, and large deviations can only arise as a consequence of multiple jumps in heavy-tailed random variables with suitable timing. Early examples are studied in Jelenković and Momčilović (2003) and Zwart et al. (2004) for a single-buffer system with multiple on/off input processes with heavy-tailed periods. Furthermore, Foss and Korshunov (2012) provide conditions on the finiteness of moments of queue sizes in a multiserver G/G/s queue and show the special effects caused by multiple jumps. Perhaps the closest work to ours that demonstrates the necessity of multiple big jumps is Chen et al. (2019), who propose a rare-event simulation technique to estimate the probability of rare events in stochastic systems that receive heavy-tailed inputs. As an application, they consider a queuing network with fixed fluid services and fixed routing in which each queue receives independent heavy- or light-tailed exogenous arrivals. They characterized the tail exponent of the queues in terms of a knapsack-type constraint that involves the sum of numbers of large jumps in the different inputs that are required to make the queue of interest large, in which the sum is weighted by the tail exponents of the corresponding inputs. Such a knapsack-type constraint also appears in our bounds, and the tail exponent fully determines the delay stability/instability of the queue of interest. Thus, our results parallel those in Chen et al. (2019) but for a different setting. The main differences are that our network operates under the more complex max-weight scheduler, and our assumptions allow for non–independent and identically distributed (i.i.d.) arrival processes. Furthermore, our proof techniques are very different from those in Chen et al. (2019); it would be interesting to explore whether the techniques in Chen et al. (2019) can be used to obtain alternative proofs for our setting (Theorem 1).

1.3. Outline

The rest of the paper is organized as follows. We start in the next section with the details of our model and some definitions. In Section 3, we discuss an example that provides insights on the ways that arrival rates and tail exponents affect delay stability and demonstrate that criteria based on traditional fluid models are inadequate for the purpose of deciding delay stability. In Section 4, we introduce a fluid-like model, which we call the jumping fluid (JF) model and underlies our main result, the necessary and sufficient conditions for (robust) delay stability that we present in Section 5. In Section 6, we study the power of Lyapunov functions for our problem. In Sections 7–9, we provide the proofs of our results. As the proofs are quite involved, they are presented as a sequence of lemmas with the proofs of the lemmas provided in Appendices B and C. We discuss the results and directions for future research in Section 10. Finally, in Appendix A, we explore alternative definitions of robust stability and corresponding variants of our jumping fluid conditions and explain why they are unlikely to yield sharp necessary and sufficient conditions.

1.4. Notation

We collect here some notational conventions to be used throughout the paper. We use boldface symbols to denote vectors and ordinary font to denote scalars. For any vector v, we use v_i to denote its ith component and $|\mathbf{v}|$ to denote the sum $|v_1|+\cdots +|v_n|$. We also use the notation ${[\mathbf{v}]}^{+}$ to denote the vector with components $\max \{0,v_i\}$. Finally, we let e_j stand for the jth unit vector.

We use ${\mathbb{R}}_{+}$ and ${\mathbb{Z}}_{+}$ to denote the sets of nonnegative reals and nonnegative integers, respectively. Furthermore, for a vector v, we write $\mathbf{v}⪰\mathbf{0}$ (respectively, $\mathbf{v}\succ \mathbf{0}$) to indicate that all components are nonnegative (positive). For any set S, we denote its convex hull by $\text{conv}(S)$.

Throughout, $\Vert ·\Vert$ stands for the Euclidean norm. Sometimes, we use the alternative notation $d(\mathbf{x},\mathbf{y})$ in place of $\Vert \mathbf{x}-\mathbf{y}\Vert .$ We also let $d(\mathbf{x},S)$ be the distance of a vector $\mathbf{x}$ from a set S, that is, $d(\mathbf{x},S)={\inf }_{\mathbf{y}\in S}\Vert \mathbf{x}-\mathbf{y}\Vert$. We finally use $\mathrm{𝟙}(·)$ to denote the indicator function and $\log$ to denote the natural logarithm.

For any time function $\mathbf{x}(·)$ that is right-continuous with left limits, $(d\mathbf{x}/dt)(t)$ or $\dot{\mathbf{x}}(t)$ stand for the right derivative of $\mathbf{x}(t)$ with the implicit assumption that it exists, and $\mathbf{x}(t^{-})$ stands for ${\lim }_{\tau \uparrow t}\mathbf{x}(\tau )$.

2. The Model

2.1. Network Model and the Max-Weight Policy

We consider a switched network that operates in discrete time. For simplicity and ease of presentation, we restrict ourselves to single-hop networks. However, our results are easily generalized to multihop networks of the type considered in Sharifnassab et al. (2020).

The network consists of $\mathcal{\ell }$ queues that buffer incoming packets (or jobs). For any $t\in {\mathbb{Z}}_{+}$, we let $\mathbf{Q}(t)$ be a nonnegative vector whose jth component is the length of the jth queue at time t. Packets arrive to the queues according to a nonnegative stochastic vector arrival process, $\mathbf{A}(·)$. In particular, $A_j(t)$ stands for the exogenous arrival to the jth queue at time t. We assume that the random variables $A_j(t)$, for different j and t, are independent. We refer to $\mathbb{E}[\mathbf{A}(t)]$ as the arrival rate vector at time t.

At each time t, the amount of service received by the queues is a nonnegative vector $\mathit{\mu }(t)$, which is chosen by a scheduler from a finite set $\mathcal{M}$ of possible service vectors. The queue lengths then evolve according to

As in Sharifnassab et al. (2020), we assume throughout the paper that, for any $\mathit{\mu }\in \mathcal{M}$, the set $\mathcal{M}$ also contains all vectors that result from setting some entries of $\mathit{\mu }$ to zero. This assumption is naturally valid in most contexts.

We focus exclusively on the popular MW scheduling policy,

which is known to have favorable stability properties (Tassiulas and Ephremides 1992): whenever there exists a policy under which the queues remain stable, MW results in stable queues. More specifically, let us consider the set $\overline{\mathcal{M}}$, defined as the convex hull, $\text{conv}(\mathcal{M})$, of the set of all possible service vectors, which is the so-called capacity region of the network. For the case of i.i.d. arrivals and under common stochastic assumptions, it is known that, if the arrival rate vector lies in the interior of the capacity region, then MW results in stable queues; conversely, if the arrival rate vector lies outside the capacity region, the queues are unstable under every scheduling policy (Tassiulas and Ephremides 1992).

2.2. Light- and Heavy-Tailed Arrivals

In this section, we present some definitions related to the tails of the arrival process distributions.

To any nonnegative random variable X, we associate a tail exponent, defined as the value of γ at which $\mathbb{E}[X^{1+\gamma }]$ switches from finite to infinite:

As an example, consider a continuous random variable whose probability density function $f(·)$ satisfies

where c, γ, k, and x₀ are positive constants. Such a distribution has a tail exponent equal to γ.

For an i.i.d. arrival process, a tail exponent is unambiguously defined as the tail exponent of the marginal distribution at an arbitrary time. However, once we bring robustness into the picture, we are led to consider arrival processes with nonidentically distributed $\mathbf{A}(t)$. To any arrival process $A_j(·)$, we associate a tail exponent, γ_j, defined as the largest value of γ such that $A_j(t)$ is dominated by some nonnegative random variable X with tail exponent γ for all times t:

Here, the term “dominates” refers to stochastic dominance: a random variables X dominates a random variable Y if $\mathbb{P}(X>a)\ge \mathbb{P}(Y>a)$ for all $a\in \mathbb{R}$. We say that $A_j(·)$ is heavy-tailed if ${\gamma }_j\le 1$ and light-tailed otherwise. Note that this definition of a heavy-tailed process is aimed to capture the boundedness of variance of the input distribution and differs from the conventional definition of heavy-tailed random variables, which requires subexponential decay of tail probabilities (Nair et al. 2020). The tail behavior of the different arrival processes is summarized by the vector $\mathit{\gamma }=({\gamma }_1,\dots ,{\gamma }_{\mathcal{\ell }})$.

We note that, as long as $\mathbb{E}[A_j(t)]\le \overline{\mu }$ for some constant $\overline{\mu }$ and for all times t, the tail exponent γ_j is well-defined and lies in the range $[0,\infty ]$. Indeed, suppose that ${\lambda }_j(t)=\mathbb{E}[A_j(t)]\le \overline{\mu }$ for some finite constant $\overline{\mu }$ and for all t. Consider a random variable X with probability density function $f_X(x)=(\overline{\mu }/x^2)\hspace{0.17em}\mathrm{𝟙}(x\ge \overline{\mu })$. The Markov inequality implies that

In particular, X dominates $A_j(t)$ for all t. Furthermore, $\mathbb{E}[X^{1+\gamma }]<\infty$, for every $\gamma <0$. Thus, γ_j is at least as large as any negative number, which implies that ${\gamma }_j\ge 0$.

Conversely, if ${\gamma }_j>0$, then $\mathbb{E}[A_j(t)]$ is finite and bounded as a function of t. We finally note that γ_j may be infinite; this is the case for bounded or, more generally, exponential-type distributions.

2.3. Robust Delay Stability

As already mentioned, we are interested in the question of delay stability under the MW policy in the presence of heavy-tailed arrivals. Given a set of arrival processes, we say that queue m is delay stable if, starting from $\mathbf{Q}(0)=0$, we have ${\sup }_t\mathbb{E}[Q_m(t)]<\infty$.

The arrival rates and the tail exponents do not provide enough information to decide whether we have delay stability or even stability. For example, there is sometimes indeterminacy on the boundary of the capacity region. Furthermore, a tail exponent of ${\gamma }_j=1$ is compatible with $\mathbb{E}[A_j^2(t)]$ being either finite or infinite, and this may be critical as far as delay stability is concerned (cf. the Pollaczek–Khintchine formula). These difficulties, all related to indeterminacy at certain boundaries, can be circumvented by focusing on a robust version of delay stability that incorporates two distinct elements.

1. We require delay stability for all arrival process distributions with given tail exponents. This allows us to focus on conditions that involve the tail exponents and ignore other details of these distributions.

2. We require delay stability for all arrival rates, possibly time-varying, in the vicinity of a given nominal rate. This allows us to avoid issues of indeterminacy when the arrival rate lies at a threshold between delay stability and instability.

Definition 1

(Robust Delay Stability). Let us fix a network with $\mathcal{\ell }$ nodes and a set $\mathcal{M}$ of possible service vectors. We consider a tail exponent vector $\mathit{\gamma }$ with components in $[0,\infty ]$ and a nominal arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$.

1. Given some $\delta \ge 0$, an arrival process $\mathbf{A}(·)$ belongs to the class ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$ if

   1. The random variables $A_j(t)$, for different j and t, are independent and have finite means.

   2. For every j, the tail exponent of the process $A_j(·)$ is γ_j.

   3. For every $t\ge 0$, we have $\Vert \mathbb{E}[\mathbf{A}(t)]-{\mathit{\lambda }}^{*}\Vert \le \delta$.

2. For $m\in \{1,\dots ,\mathcal{\ell }\}$, we say that queue m is robustly delay stable (RDS) if there exists some $\delta >0$ such that queue m is delay stable for all arrival processes in the class ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$.

3. A Counterexample and the Insufficiency of Fluid Models

In this section, we discuss a simple example with the following features:

1. Similar to existing examples, heavy-tailed arrivals to some queues can cause delay instability at a queue that receives light-tailed traffic.

2. Tight criteria for delay instability need to take into account the values of the tail exponents. In particular, criteria that are based on traditional fluid models cannot be conclusive because they do not involve the tail exponents.

3. Delay instability may emerge from coordinated large arrivals at multiple heavy-tailed queues.

Consider the three-queue network in Figure 1. The set of possible service vectors $\mathcal{M}$ is such that, at any time slot, up to two queues can be served, each with rate one, but not all three queues can be served simultaneously. Thus, at each time step, the MW policy chooses two queues with the largest backlogs and serves each one of them with rate one.

The third queue receives deterministic arrivals with $A_3(t)=\lambda <1$ for all $t\ge 0$ so that ${\gamma }_3=\infty$. The other two queues receive heavy-tailed traffic with a density of the form (4) and tail exponent $\gamma \in (0,1)$ and with rate 0.5; that is, $\mathbb{E}[A_1(t)]=\mathbb{E}[A_2(t)]=0.5$.

The total arrival rate is $1+\lambda$, which is less than two, and the network is stable in the conventional sense. The first two queues are automatically delay unstable because they receive heavy-tailed arrivals. However, the third queue can be either delay stable or delay unstable, depending on the values of λ and γ. In what follows, we provide an informal discussion of the different cases.

Case 1

($0.5<\lambda <1$). In this case, queue 3 is delay unstable through a scenario similar to those considered in earlier works (Markakis et al. 2014). Intuitively, because of its heavy-tailed arrivals, Q₁ occasionally receives large inputs. When that happens, with $A_1(t_0)$ being large at some time $t_0>0$, Q₁ becomes and stays largest for some time. During that time, the MW policy keeps serving Q₁, while the remaining service capacity is split between Q₂ and Q₃. Because $\lambda >0.5$, the sum of the arrival rates to Q₂ and Q₃ exceeds the aggregate service rate to these two queues over a time interval of duration $\mathrm{\Omega }(A_1(t_0))$. Thus, Q₂ and Q₃ build up to size $\mathrm{\Omega }(A_1(t_0))$. Because $\gamma <1$, we have $\mathbb{E}[A_1^2(t)]=\infty$, and using this property, it can be shown that $\mathbb{E}[Q_3(t)]$ grows unbounded.

The intuition behind this argument is captured by an existing criterion from Markakis et al. (2014) that examines certain trajectories $\mathbf{q}(·)$ of a corresponding fluid model (also called fluid trajectories). In that fluid model, the arrival processes are replaced by deterministic flows with the same rates. The initial conditions are $q_h(0)=1$ for some heavy-tailed queue (in our example, h = 1 or h = 2) and $q_j(0)=0$ for $j\ne h$. (Because of symmetry, we only need to consider the case in which h = 1.) Let us say that the “zero fluid” (ZF) condition holds if the solution to the fluid model (known to be unique for the MW policy) keeps $q_3(·)$ at zero. According to the criterion in Markakis et al. (2014), the failure of the ZF condition certifies the delay instability of queue 3. This is indeed the case here: starting with the initial conditions $\mathbf{q}(0)=(1,0,0)$, it can be verified that, for small positive times t, we have $q_3(t)=(\lambda -0.5)t/2>0$.

In summary, for this particular case, we have delay instability, and this is correctly predicted by the failure of the ZF condition and available results.

Case 2

($0<\lambda <0.5$ and $\gamma >0.5$). In this case, queue 3 turns out to be delay stable (in fact, robustly delay stable). This is a consequence of our general result in Section 5.

For this case, the fluid model initialized at $\mathbf{q}(0)=(1,0,0)$ satisfies $q_3(t)=0$ for all positive times, and the ZF condition holds. In particular, the ZF condition is “aligned” with delay stability. Observations of this nature lead to the question whether the ZF condition can be used as a certificate of delay stability (Markakis et al. 2018). However, this is not the case as we discuss next.

Case 3

($0<\lambda <0.5$ and $\gamma \le 0.5$). In this case, the ZF condition holds, similar to Case 2. However, queue 3 turns out to be delay unstable; this follows from the proof² of our main result, Theorem 1.

We summarize here the underlying intuition. When $\gamma \le 0.5$, there is considerable probability that both queues 1 and 2 receive large inputs within a certain time interval. More concretely, for large values of M, there is probability $\mathrm{\Omega }(1/M)$ that both Q₁ and Q₂ receive aggregate arrivals of size at least 3M within the time interval $[0,M]$. If this happens, both Q₁ and Q₂ become large enough so that Q₃ receives no service during the interval $[M,2M]$. As a result, $Q_3(2M)\ge \lambda M$ with probability $\mathrm{\Omega }(1/M)$. One can then use this fact to show that, as t increases, $\mathbb{E}[Q_3(t)]$ grows unbounded, and queue 3 is delay unstable.

In summary, the presence or absence of delay stability depends on the tail exponents in a nontrivial manner. Furthermore, the ZF condition cannot discriminate between Cases 2 and 3 and, thus, cannot account for the different outcomes (delay stability in Case 2, delay instability in Case 3). In fact, the same obstacle arises with any other criterion that relies on traditional fluid models because fluid models do not take the tail exponents into account. In order to make progress, we need to consider the probability that large inputs (or jumps) may arrive within a certain time interval as a function of the tail exponents (the probability is larger when the tail exponents are smaller). Furthermore, as illustrated by Case 3, we may have to consider the effect of “coordinated” large jumps at more than one queue within the same time interval. This is accomplished by the model in the next section: it is still in the spirit of traditional fluid models except that it allows for jumps along the heavy-tailed flows, subject to a “budget” on allowed jumps as determined by the tail exponents.

4. Jumping Fluid Models

In this section, we introduce a generalization of the fluid model that allows for jumps along certain coordinates. We proceed by first defining a traditional fluid model and then modifying it.

4.1. The Fluid Model

A fluid model is a deterministic continuous-time dynamical system that replaces the arrival process with a fluid stream of arrivals and updates queue lengths along max-weight drifts. The literature provides a few, somewhat different but equivalent, definitions of the fluid model (Shah and Wischik 2012, Markakis et al. 2018), which typically involve differential equations with boundary conditions. Here, we adopt an equivalent but somewhat simpler definition³ from Sharifnassab et al. (2020).

Recall the definition of $\mathcal{M}$ as the set of all possible service vectors. For any $\mathbf{x}\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$, we define

which is the set of all possible service vectors that, for the given x, attain the maximum in the definition of the MW policy; see (2). We also let

Furthermore, given an arrival rate vector $\mathit{\lambda }⪰\mathbf{0}$ and any $\mathbf{x}\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$, we let

which is the set of candidate drifts when the queue length vector is x.

For the definitions that follow, recall our convention that $\dot{\mathbf{q}}(t)$ denotes the right derivative of $\mathbf{q}(·)$ with respect to time at time t.

Definition 2

(Fluid Trajectories). Let us fix a network with $\mathcal{\ell }$ nodes, a set $\mathcal{M}$ of possible service vectors, and an arrival rate vector $\mathit{\lambda }⪰\mathbf{0}$. A fluid trajectory corresponding to $\mathit{\lambda }$ is a nonnegative, continuous, and right-differentiable $\mathcal{\ell }$-dimensional function $\mathbf{q}(·)$ that satisfies the differential inclusion

$$\dot{\mathbf{q}}(t)\in {\overline{\mathcal{D}}}_{\mathit{\lambda }}(\mathbf{q}(t)),\hspace{1em}\hspace{1em}\forall t\ge 0.$$(9)

Given some $\mathit{\lambda }⪰\mathbf{0}$ and $\mathbf{q}(0)⪰\mathbf{0}$, there always exists a unique (and nonnegative) fluid trajectory $\mathbf{q}(·)$ corresponding to $\mathit{\lambda }$ and initialized at $\mathbf{q}(0)$ (Markakis et al. 2018, Sharifnassab et al. 2020).

4.2. Adding the Jumps

We now introduce JF trajectories. Given a vector $\mathbf{n}=(n_1,\dots ,n_{\mathcal{\ell }})$ of nonnegative integers, an ϵ-JF$(\mathbf{n})$ trajectory is a fluid trajectory with jumps with n_j positive jumps in its jth component, allowing for ϵ-changes in the arrival rate $\mathit{\lambda }$. More concretely, we have the following definition.

Definition 3

(ϵ-Jumping Fluid Trajectories). Let us fix a network with $\mathcal{\ell }$ nodes and a set $\mathcal{M}$ of possible service vectors. We are given an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$, a nonnegative integer vector n, and some $ϵ\ge 0$. An ϵ-JF$(\mathbf{n})$ trajectory corresponding to ${\mathit{\lambda }}^{*}$ is a nonnegative $\mathcal{\ell }$-dimensional function $\mathbf{q}(·)$, which is right-continuous with left limits and right-differentiable initialized with $\mathbf{q}(t)=\mathbf{0}$ for all t < 0 and with the following properties:

1. Each component $q_j(·)$ has n_j points of discontinuity.

2. If $q_j(·)$ has a discontinuity at some time t, then $q_j(t)>q_j(t^{-})$.

3. For every $t\ge 0$,

   $$\dot{\mathbf{q}}(t)\in {\overline{\mathcal{D}}}_{\mathit{\lambda }(t)}(\mathbf{q}(t)),$$(10)
   for some nonnegative function $\mathit{\lambda }(·)$ that is right-continuous and piecewise constant with finitely many points of discontinuity and satisfies $\Vert \mathit{\lambda }(t)-{\mathit{\lambda }}^{*}\Vert \le ϵ$ for all t.

Finally, an ϵ-JF(n) trajectory with⁴ ${\mathit{\gamma }}^T\mathbf{n}={\sum }_{j=1}^{\mathcal{\ell }}{\gamma }_j{n}_j\le 1$, is called an ϵ-JF($\mathit{\gamma }$) trajectory.

Note that we allow jumps at time zero, in which case $\mathbf{q}(0)\ne \mathbf{0}$. Note also that, if ϵ = 0 and jumps can only happen at time zero, then an ϵ-JF trajectory is just a fluid trajectory with the jumps of the JF trajectory determining the initial conditions of the fluid trajectory.

More generally, an ϵ-JF trajectory consists of a concatenation of fluid trajectories over the intervals in which $\mathit{\lambda }(·)$ stays constant together with a finite number of jumps. For this reason, once the jump times, jump sizes, and function $\mathit{\lambda }(·)$ are specified, the results for fluid models extend and establish the existence and uniqueness of the ϵ-JF(n) trajectory.

Our next definition formalizes the requirement that a certain queue must stay at zero under all ϵ-jumping fluid trajectories.

Definition 4

(JF Conditions). Let us fix a network with $\mathcal{\ell }$ nodes and a set $\mathcal{M}$ of possible service vectors. We are given an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$ and a particular queue, m, of interest.

1. Given a vector $\mathit{\gamma }$ with components in $[0,\infty ]$ and some $ϵ\ge 0$, we say that the ϵ-JF$(\mathit{\gamma })$ condition holds for queue m and ${\mathit{\lambda }}^{*}$ if, for every ϵ-JF($\mathit{\gamma }$) trajectory corresponding to ${\mathit{\lambda }}^{*}$ and every $t\ge 0$, we have $q_m(t)=0$.

2. Given a vector $\mathit{\gamma }$ with components in $[0,\infty ]$, we say that the robust jumping fluid condition (RJF($\mathit{\gamma }$)) holds for queue m and ${\mathit{\lambda }}^{*}$ if there exists some $ϵ>0$ such that the ϵ-JF$(\mathit{\gamma })$ condition holds for queue m and ${\mathit{\lambda }}^{*}$.

Note the restriction on the number of jumps in terms of the tail exponents: the heavier the arrival processes (i.e., the smaller the tail exponents γ_j), the larger the number n_j of jumps that we allow. As an example, if ${\gamma }_1\le 1$ and queue 1 is the only heavy-tailed queue, then we allow up to $\lfloor 1/{\gamma }_1\rfloor$ jumps at queue 1 and no jumps at the other queues.

5. Main Result

Our main result provides a necessary and sufficient condition for robust delay stability in terms of JF trajectories. The proof is given in Sections 7 and 8.

Theorem 1.

Let us fix a network with $\mathcal{\ell }$ nodes; a set $\mathcal{M}$ of possible service vectors; an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$; a particular queue, m, of interest; and a vector $\mathit{\gamma }$ of tail exponents with components in $(0,\infty ]$. The queue m is RDS if and only if the RJF$(\mathit{\gamma })$ condition holds for queue m and ${\mathit{\lambda }}^{*}$.

5.1. Some Intuition

We provide here a high-level explanation of our result. Some more refined intuition is provided by the proof outlines in Sections 7.1 and 8.1.

Let M be a large constant. We say that the stochastic process $A_j(t)$ has a jump whenever it is larger than (approximately) M. Let N_j be the number of jumps of $A_j(t)$ during the interval $[0,M]$ and let $\mathbf{N}=(N_1,\dots ,N_{\mathcal{\ell }})$. It turns out that, for any nonnegative integer vector n, the probability that the event $\mathbf{N}=\mathbf{n}$ scales (approximately) like $M^{-{\mathit{\gamma }}^T\mathbf{n}}$. The latter quantity is “significant” (in the sense that it makes an unbounded contribution to certain expected values) if and only if ${\mathit{\gamma }}^T\mathbf{n}\le 1$. Thus, over an interval of length M, we can focus on sample paths for which the realized vector n of jump counts satisfies ${\mathit{\gamma }}^T\mathbf{n}\le 1$ and examine whether such sample paths can cause the queue of interest to become large. We then argue that these sample paths are well-approximated by the ϵ-JF(n) trajectories involved in the ϵ-JF$(\mathit{\gamma })$ condition.

5.2. Remarks

We continue with some remarks on the scope of our result.

5.2.1. Heavy-Tailed Queues.

If queue m is heavy-tailed, that is, ${\gamma }_m\le 1$, then the condition ${\mathit{\gamma }}^T\mathbf{n}\le 1$ allows n to be the mth unit vector. With such a vector n, we can have an ϵ-JF(n) trajectory with a positive jump in the mth component, resulting in a positive value of $q_m(t)$. Thus, the RJF($\mathit{\gamma }$) condition does not hold, and queue m is not RDS. This is just a variation of the well-known fact that a queue with heavy-tailed arrivals is not delay stable.

5.2.2. Unstable Systems.

Theorem 1 makes no stability assumptions. For unstable (or marginally stable) systems, some components of ϵ-JF trajectories can grow arbitrarily large. On the other hand, these components do not necessarily have a substantial effect on the queue, m, of interest. As long as the mth component of all ϵ-JF trajectories stays at zero, queue m is RDS.

5.2.3. Comparison with the ZF Condition.

If ${\gamma }_j>1/2$ for all j, then an ϵ-JF trajectory can have at most one jump. For stable systems, the RJF condition boils down to a robust version of the ZF condition introduced in Section 3. In other words, for this case, a robust version of the ZF condition is a necessary and sufficient condition for robust delay stability. On the other hand, because the (robust version of) the ZF condition is strictly weaker than the RJF condition, it does not provide necessary and sufficient conditions for general $\mathit{\gamma }$.

5.2.4. The Light-Tailed Case.

Suppose that ${\gamma }_j>1$ for all j so that all arrival processes are light-tailed. In this case, no jumps are allowed, and the RJF condition boils down to considering ordinary fluid trajectories with slightly perturbed arrival rates. We have the following possibilities:

1. If ${\mathit{\lambda }}^{*}$ is in the interior of the capacity region $\overline{\mathcal{M}}$, then $\mathbf{0}$ is in the interior of ${\overline{\mathcal{D}}}_{{\mathit{\lambda }}^{*}}(\mathbf{0})={\mathit{\lambda }}^{*}-\overline{\mathcal{M}}$. It then turns out that $\mathbf{0}$ is an attracting fixed point of the fluid dynamics, the RJF condition holds, and we have RDS for all queues. This is in line with existing results (e.g., see theorem 4.5 of Georgiadis et al. 2006).

2. If ${\mathit{\lambda }}^{*}$ is on the boundary or outside the capacity region and, similar to our earlier discussion of unstable systems, queue m could be either RDS or non-RDS, depending on whether (perturbed) fluid trajectories cause q_m to become positive or not.

5.2.5. The Case of Zero Tail Exponents.

Our definitions in Sections 2 and 4 are formulated for a nonnegative vector $\mathit{\gamma }$. However, our result is restricted to the case in which this vector is positive. We comment on the reasons for this.

When ${\gamma }_j=0$, we are dealing with an arrival process for which $\mathbb{E}[A_j(t)]$ is finite, whereas $\mathbb{E}[A_j{(t)}^{1+\gamma }]$ may be infinite for every $\gamma >0$. Our proofs involve, at certain places, a division by γ_j and break down if ${\gamma }_j=0$. It is not clear whether a similar result is possible when some of the tail exponents are zero.

5.2.6. Computational Issues.

As already hinted in the introduction, checking the RJF condition algorithmically appears to be a hard computational problem, amenable only to impractical Tarski-like elimination algorithms. In one possible simplification, we might just consider ϵ-JF trajectories with ϵ = 0 so that $\mathit{\lambda }(t)={\mathit{\lambda }}^{*}$ for all times t. However, this would still leave the indeterminacy of the jump times and sizes to be reckoned with. Even worse, a restriction to this limited class of trajectories does not seem to lead to necessary and sufficient conditions for any suitably modified notion of stability. See Appendix A.2 for further discussion. A related question is whether we could, without loss of generality, require all the jumps to occur at the same time, for example, at time zero, thus eliminating the need to consider all possible values of the jump times. Unfortunately, this is not the case: there exist examples in which ϵ-JF trajectories can drive a queue m to a positive value, but this can happen only if we allow the jumps to occur at different times; see Appendix A.5 for an example.

5.3. Our Example, Revisited

On the positive side, Theorem 1 elucidates the precise mechanism that leads to delay instability through a coordination of multiple abnormally large arrival vectors at possibly different times and queues. Furthermore, it allows us to analyze simple problems, such as the one discussed in Section 3, which we do next.

Recall the network of three queues in Section 3, in which $\mathit{\gamma }=(\gamma ,\gamma ,\infty )$. For γ in the range $(0,0.5]$, consider a jumping fluid trajectory $\mathbf{q}(·)$ with $\mathbf{n}=(1,1,0)$ in which both q₁ and q₂ undergo unit jumps at time 0. With this trajectory, q₃ immediately starts to grow positive. Because ${\mathit{\gamma }}^T\mathbf{n}=2\gamma \le 1$, it follows that the RJF$(\mathit{\gamma })$ condition fails to hold. Theorem 1 then establishes that queue 3 is not robustly delay stable.

On the other hand, when γ is in the range $(0.5,1]$, the constraint ${\mathit{\gamma }}^T\mathbf{n}\le 1$ allows at most one jump in either q₁ or q₂. Without loss of generality, we can assume that this jump takes place at time 0. It turns out that the fluid trajectories that start from either $\mathbf{q}(0)=(1,0,0)$ or $\mathbf{q}(0)=(0,1,0)$ keep $q_3(·)$ at zero if and only if $\lambda \le 0.5$. Therefore, for γ in range $(0.5,1]$ and also taking robustness into account, queue 3 is RDS if and only if $\lambda <0.5$.

6. Robust Delay Stability via Lyapunov Functions

Lyapunov functions are a powerful tool for the stability analysis of queueing networks (Tassiulas and Ephremides 1992, Bertsimas et al. 2001, Maguluri et al. 2016), for example, in throughput optimality proofs for the MW policy (Tassiulas and Ephremides 1992, Neely 2010). Markakis (2013) and Markakis et al. (2018) provide a sufficient condition for delay stability based on a class of piecewise linear Lyapunov functions and use it to derive a sharp characterization of delay stability for a special class of networks, namely, networks with disjoint schedules. Nevertheless, the Lyapunov approach in Markakis (2013) and Markakis et al. (2018) has some drawbacks: (a) the condition provided therein is, in general, only sufficient for delay stability; (b) it does not take into account the tail exponents even though they play an essential role in delay stability as already discussed in Sections 3 and 5.3; (c) the Lyapunov functions considered are piecewise linear, which is perhaps inadequate for the purpose of tight delay stability conditions.

In this section, we explore the power of Lyapunov functions for the case in which the tail exponents of the heavy-tailed queues may be arbitrarily close to zero so that the RJF condition allows an arbitrarily large number of jumps.

For the remainder of this section, we assume that queues $1,\dots ,h$ can be heavy-tailed, where $h<\mathcal{\ell }$, whereas the remaining queues are light-tailed. Formally, we consider the set Γ of tail coefficients, defined by

We also fix an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$ and a light-tailed queue m > h of interest.

Definition 5

(Special Lyapunov Function). For any $ϵ>0$, we say that a function $V:{\mathbb{R}}_{+}^{\mathcal{\ell }}\to {\mathbb{R}}_{+}$ is a special ϵ-Lyapunov function if

1. V is Lipschitz continuous with Lipschitz constant one.

2. $\dot{V}(\mathbf{q}(t))\le -ϵ$ whenever $V(\mathbf{q}(t))>0$ for all fluid trajectories $\mathbf{q}(·)$ corresponding to arrival rate ${\mathit{\lambda }}^{*}$.

3. We have $V(\mathbf{0})=0$. Furthermore, if $q_m>0$, then $V(q_m)>0$.

4. V is nonincreasing along the coordinates associated with heavy-tailed queues; that is, for $j=1,\dots ,h$, for any $\mathbf{q}\in {\mathbb{R}}_{+}^n$, and any $\alpha >0$, we have $V(\mathbf{q}+\alpha {\mathit{e}}_j)\le V(\mathbf{q})$, where ${\mathit{e}}_j$ is the jth unit vector.

Special ϵ-Lyapunov functions as defined are quite similar to the functions considered in theorem 2 of Markakis et al. (2018). However, in contrast to Markakis et al. (2018), our special Lyapunov functions need not be piecewise linear. Our next result establishes a strong connection between the ϵ-JF$(\mathit{\gamma })$ condition and the existence of special ϵ-Lyapunov functions. The proof is given in Section 9.

Theorem 2.

For any $ϵ>0$, there exists a special ϵ-Lyapunov function if and only if the ϵ-JF$(\mathit{\gamma })$ condition holds for every $\mathit{\gamma }\in \mathrm{\Gamma }$.

The special ϵ-Lyapunov functions constructed in the proof of Theorem 2 are not piecewise linear. We do not know whether Theorem 2 remains valid if we restrict to piecewise linear functions.

Combining Theorems 1 and 2, we can establish a strong connection between robust delay stability and special ϵ-Lyapunov functions. In what follows, we say that queue m is ϵ-RDS$(\mathit{\gamma })$ if it is delay stable under all arrival processes in the class ${\mathcal{A}}_{ϵ}(\mathit{\gamma };{\mathit{\lambda }}^{*})$ in Definition 1(a).

Corollary 1.

Let us fix a network with $\mathcal{\ell }$ nodes, a set $\mathcal{M}$ of possible service vectors, an arrival vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$, the number h of heavy-tailed queues, and a light-tailed queue m > h.

1. If there exists a special ϵ-Lyapunov function for some $ϵ>0$, then queue m is RDS for all tail exponents $\mathit{\gamma }\in \mathrm{\Gamma }$.

2. Suppose that there exists some $ϵ>0$ such that, for all $\mathit{\gamma }\in \mathrm{\Gamma }$, queue m is ϵ-RDS$(\mathit{\gamma })$. Then, there exists an ϵ-special Lyapunov function.

The proof is provided in Section 9.3. We conjecture that Corollary 1(b) can be strengthened to provide a converse to part (a).

Hypothesis 1.

If queue m is RDS for all tail exponents $\mathit{\gamma }\in \mathrm{\Gamma }$, then for some $ϵ>0$, there exists a special ϵ-Lyapunov function.

If Hypothesis 1 is true, we have a tight characterization: a queue is RDS for all tail exponents $\mathit{\gamma }\in \mathrm{\Gamma }$ if and only if there exists a special ϵ-Lyapunov function that testifies to this. Establishing the conjecture appears to be difficult. Technically it amounts to reversing the order of the quantifiers in the clause “there exists $ϵ>0$ such that, for all $\mathit{\gamma }\in \mathrm{\Gamma }\dots$” in Corollary 1(b) and showing equivalence with the statement “for every $\mathit{\gamma }\in \mathrm{\Gamma }$, there exists some $ϵ>0$…”

Our Lyapunov-based results are relevant to the case in which nothing is known about the tail exponents of the heavy-tailed queues other than the fact that they are positive. On the other hand, Lyapunov functions are unlikely to provide useful characterizations of robust delay stability for specific values of the tail exponents because there is no apparent way of accounting for the number of jumps through Lyapunov functions.

7. Proof of the “if” Direction of Theorem 1 (RJF$\Rightarrow$RDS)

In this section, we provide the proof of the “if” direction of Theorem 1, that is, that the RJF condition implies RDS.

Throughout this section, we consider a network with $\mathcal{\ell }$ nodes and a set $\mathcal{M}$ of possible service vectors. We fix an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$; a particular queue, m, of interest; a vector $\mathit{\gamma }$ of tail exponents with components in $(0,\infty ]$; and some $ϵ>0$ for which the ϵ-JF$(\mathit{\gamma })$ condition holds for ${\mathit{\lambda }}^{*}$ and queue m. Our goal is to establish robust delay stability for queue m.

The proof is organized in a sequence of lemmas whose proofs are collected in Appendix B. However, before proceeding to the formal arguments, it is helpful to provide an overview of the proof.

7.1. Outline of the Proof

Let us fix an arbitrary time T. We aim at upper bounds for the probability $\mathbb{P}(Q_m(T)\ge M)$ as M gets large. As long as these bounds are a summable function of M and independent of T it follows that $\mathbb{E}[Q_m(T)]$ is finite and a bounded function of T, which is our goal. Let us now fix some M and keep it fixed throughout except for the end of the proof.

The proof relies on various probabilistic bounds as well as on deterministic properties of the MW dynamics. Let us start with the probabilistic part, which is focused on showing that the stochastic system mostly follows the deterministic fluid dynamics except for certain jumps caused by the heavy tails of the arrival processes. We define a threshold for what constitutes a jump and then develop a probabilistic bound on the numbers of jumps. A difficulty here is that, if we use a fixed threshold and because T is arbitrary, a bound on the number of jumps is not possible. We handle this issue by using a threshold θ_t that increases almost linearly as we move further to the past of the form

This is for some positive constant η to be defined later. At any time $t\le T$ and for any index j, we say that $A_j(t)$ is a jump if $A_j(t)>{\theta }_t$. Ignoring logarithmic factors, we show that the jump probability $\mathbb{P}(A_j(t)>{\theta }_t)$ is of order at most $1/{(M+T-t)}^{1+{\gamma }_j^{\prime }}$, where ${\gamma }_j^{\prime }$ is slightly smaller than the tail exponent γ_j. By summing over t and after some elementary calculations, we then obtain that $\mathbb{P}(N_j=n_j)$ is of order at most $1/M^{n_j{\gamma }_j^{\prime }}$, where N_j is the number of jumps of the jth arrival process during the interval $[0,T]$. Then, a further calculation shows that, if $\mathbf{N}=(N_1,\dots ,N_{\mathcal{\ell }})$, then $\mathbb{P}({\mathit{\gamma }}^T\mathbf{N}>1)$ is of order at most $1/M^{\beta }$ for some constant $\beta \in (1,2)$ and is, therefore, a summable function of M; see Lemma 1.

We then consider stochastic fluctuations in the arrival process other than jumps. We argue that they average out so that the cumulative arrival process follows its fluid counterpart. We refer to this as the “small fluctuations event,” and show that it occurs with probability at least $1-\mathcal{\ell }/M^2$; see (21) and Lemma 3.

Having completed the probabilistic analysis, we then switch to deterministic (sample path) considerations. Let $W(\mathbf{n})$ be the set of all points q that can be reached by some ϵ-JF$(\mathbf{n})$ trajectory (see Definition 6). As a first step, we exploit some special properties of the MW dynamics and show that $W(\mathbf{n})$ is ϵ-attracting; that is, any fluid trajectory that starts outside $W(\mathbf{n})$ moves toward that set with rate at least ϵ (Lemma 4). We then consider a “nice” sample path, that is, a sample path for which the small fluctuations event occurs and for which the realized vector of jump counts n satisfies ${\mathit{\gamma }}^T\mathbf{n}\le 1$. (As discussed earlier, nice sample paths have probability $1-O(M^{-\beta })$ with $\beta >1$.) Our deterministic analysis, outlined in the next paragraph, shows that any such sample path stays within O(M) distance from the set $W(\mathbf{n})$. Because ${\mathit{\gamma }}^T\mathbf{n}\le 1$, the ϵ-JF($\mathit{\gamma }$) condition implies that any point in $W(\mathbf{n})$ satisfies q_m = 0. Thus, for nice sample paths, we have $Q_m(T)=O(M)$, and therefore, $\mathbb{P}(Q_m(T)\ge M)$ is of order at most $1/M^{\beta }$ for the constant $\beta \in (1,2)$ mentioned earlier. This readily implies a uniform upper bound on $\mathbb{E}[Q_m(T)]$.

The analysis of the dynamics under nice sample paths has two parts. We first study the dynamics between jumps: we rely on the small fluctuations event and then make use of a result from Sharifnassab et al. (2020, theorem 4) to ensure that small fluctuations in the arrivals result into comparably small changes in the resulting stochastic trajectory; cf. Lemma 5. Second, to understand what happens at jump times, we recall that the jump vectors n associated to nice sample paths satisfy ${\mathit{\gamma }}^T\mathbf{n}\le 1$. Such vectors n are allowed in ϵ-JF($\mathit{\gamma }$) trajectories, and therefore, the jumps cannot take the ϵ-JF(n) trajectory away from $W(\mathbf{n})$. This implies that a nice sample path stays “close” to an ϵ-JF(n) trajectory and, therefore, has a “small” Q_m.

7.2. Sensitivity of Max-Weight Dynamics

The proof for both directions of the theorem requires fairly precise bounding of the fluctuations of the stochastic trajectories. To this effect, we rely heavily on a fluctuation bound for the MW dynamics established in Sharifnassab et al. (2020).

Theorem 3

(Sharifnassab et al. 2020, theorem 2). Fix a network (i.e., the number of nodes and the set $\mathcal{M}$ of possible service vectors) operating under the MW policy and let $\mathbf{Q}(·)$ be the corresponding queue length stochastic process. There exists a (deterministic) constant $C\ge 1$ such that, for any arrival rate vector $\mathit{\lambda }⪰\mathbf{0}$, any $\mathbf{q}(0)⪰\mathbf{0}$, any $t\ge 0$, and any sample path, if $\mathbf{q}(0)=\mathbf{Q}(0)$, then

$$\Vert \mathbf{Q}(t)-\mathbf{q}(t)\Vert \le C\left(1+\Vert \mathit{\lambda }\Vert +\underset{k<t}{\max }\Vert {\displaystyle \sum _{\tau =0}^k(}\mathbf{A}(\tau )-\mathit{\lambda })\Vert \right),$$(12)

where $\mathbf{q}(·)$ is the fluid trajectory corresponding to $\mathit{\lambda }$ initialized at $\mathbf{q}(0)$.

We actually use the following variant of Theorem 3, which allows for different initial conditions. The proof is given in Appendix B.1.

Theorem 4.

Under the same assumptions as in Theorem 3 except that we allow for $\mathbf{Q}(0)$ and $\mathbf{q}(0)$ to be different and for the same constant C, we have

$$\Vert \mathbf{Q}(t)-\mathbf{q}(t)\Vert \le \Vert \mathbf{Q}(0)-\mathbf{q}(0)\Vert +C\left(1+\Vert \mathit{\lambda }\Vert +\underset{k<t}{\max }\Vert {\displaystyle \sum _{\tau =0}^k(}\mathbf{A}(\tau )-\mathit{\lambda })\Vert \right).$$

7.3. Arrival Process and Jumps

We now return to the formal proof. Recall that, throughout this section, we fix the network, ${\mathit{\lambda }}^{*}⪰\mathbf{0}$ and the tail exponents ${\gamma }_j\in (0,\infty ]$. We assume that the ϵ-JF$(\mathit{\gamma })$ condition holds for ${\mathit{\lambda }}^{*}$, queue m, and some $ϵ>0$. We fix some positive integers M and T; these remain fixed throughout except for the end of the proof and for some additional assumptions that M is “large enough.”

We consider an arrival process $\mathbf{A}(·)$ in the class ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$ introduced in Definition 1 with $\delta =\gamma ϵ/20C$, where C is the constant in Theorem 4 and

In particular,

Our goal is to derive an upper bound on $\mathbb{P}({\mathbf{Q}}_m(T)\ge M)$ that holds uniformly for every arrival process $\mathbf{A}(·)$ in ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$, every T, and every large enough M. This is then used to conclude that the RDS property holds.

Because we assume that the tail exponents are nonzero, we have $\gamma >0$. Furthermore, in order to simplify the proof, it is convenient to assume that

Claim 1.

The assumption $\gamma \le 1$ can be made without loss of generality.

Proof.

Given a system, call it S, consider a new system $S\prime$ in which we add one more queue, queue 0, with ${\gamma }_0<1$, which does not interact with the others; for example, for any allowed service vector $\mathit{\mu }$ in system S, we introduce a corresponding service vector $(1,\mathit{\mu })$ in system $S\prime$. This way, the dynamics of queues $1,\dots ,\mathcal{\ell }$ are the same in the two systems S and $S\prime$. It follows that, for $m\ge 1$, queue m is RDS in system S if and only if it is RDS in system $S\prime$. Furthermore, because of the lack of interaction, the RJF condition for queue m holds in system S if and only if it holds in system $S\prime$.

Once we prove the result for the case $\gamma \le 1$, we apply it to system $S\prime$ and obtain the equivalence of RDS and RJF for the latter system. Based on this discussion, this also establishes the equivalence of RDS and RJF for the original system S. □

We define some more constants:

$$\overline{\mu }=1+\underset{\mathit{\mu }\in \mathcal{M}}{\max }\Vert \mathit{\mu }\Vert +\Vert {\mathit{\lambda }}^{*}\Vert +ϵ,$$(16)

and

$$\eta =\frac{8000\hspace{0.17em}{C}^2{\mathcal{\ell }}^2\overline{\mu }}{{(\gamma ϵ)}^2}.$$(17)

Having fixed M, T, and η, we finally define θ_t as in (11).

For $j=1,\dots ,\mathcal{\ell }$ and $t=0,\dots ,T-1$, we say that t is a jump time for $A_j(·)$ if $A_j(t)>{\theta }_t$. For any j and any $\tau \in [0,T)$, we let $N_j(\tau )$ be the (random) number of jumps in $A_j(·)$ that occur during $[0,\tau ]$ and also define the corresponding vector $\mathbf{N}(\tau )=(N_1(\tau ),\dots ,N_{\mathcal{\ell }}(\tau ))$. To simplify notation and as long as T is fixed, we use N and N_j to refer to $\mathbf{N}(T-1)$ and $N_j(T-1)$, respectively. Note that, with this definition, $\mathbf{N}=\mathbf{N}(T-1)$ includes all jumps that can affect $\mathbf{Q}(T)$.

We consider the event

$${\mathcal{E}}^{\text{jump}}(T,M)=\{{\mathit{\gamma }}^T\mathbf{N}\le 1\}.$$(18)

We argue that it occurs with high probability.

Let F be the set of all $\mathit{n}⪰\mathbf{0}$ such that $1<{\mathit{\gamma }}^T\mathit{n}\le 2$. If F is empty, then whenever ${\mathit{\gamma }}^T\mathit{n}>1$, we must have ${\mathit{\gamma }}^T\mathit{n}>2$. If F is nonempty, it has finitely many elements, which implies that the minimum ${\min }_{\mathit{n}\in F}{\mathit{\gamma }}^T\mathit{n}$ is attained and its value is greater than one. In either case, we obtain that there exists a constant $\beta >1$ such that

$$\text{if} {\mathit{\gamma }}^T\mathit{n}>1, \text{then} {\mathit{\gamma }}^T\mathit{n}\ge {\beta }^3.$$(19)

Without loss of generality, we can take β to satisfy $1<\beta <2$. In the next lemma, we show the probability that ${\mathit{\gamma }}^T\mathit{N}>1$ decays at least as fast as $1/M^{\beta }$.

Lemma 1.

There exists a constant $M_1\ge 0$ independent of T such that, if $M\ge M_1$, then

$$\mathbb{P}({\mathcal{E}}^{\text{jump}}(T,M))=\mathbb{P}({\mathit{\gamma }}^T\mathbf{N}\le 1)\ge 1-M^{-\beta }.$$

The proof is given in Appendix B.2 and relies on the intuition that the probability of a jump in the jth arrival process scales at most as $M^{-{\gamma }_j}$ (approximately), which then implies that the probability of the event $\{\mathbf{N}=\mathbf{n}\}$ scales at most as $M^{-{\mathit{\gamma }}^T\mathbf{n}}$ (approximately).

7.4. Fluctuations of the Arrival Process

We now study the remaining fluctuations of the cumulative arrival processes after we exclude the jumps. We begin with a concentration inequality for the sum of independent random variables. The proof of our next lemma is given in Appendix B.3 and is essentially a reformulation of the Bernstein inequality; see, for example, (1.21) in appendix 1 of Anthony and Bartlett (2009).

Lemma 2.

Suppose that $X_1,\dots ,X_n$ are independent random variables that satisfy $X_i\in [0,b]$ and $\mathbb{E}[X_i]\le \overline{\lambda }$ for some $b,\overline{\lambda }>0$. Let $Y=X_1+\cdots +X_n$. Then, for any $z\ge 0$,

$$\mathbb{P}(|Y-\mathbb{E}\left[Y\right]|>z)\le 2\exp \left(-\frac{z^2}{2b\hspace{0.17em}(\overline{\lambda }n+z/3)}\right).$$(20)

We consider the truncated process ${\mathbf{A}}^{*}(t)=\min \{\mathbf{A}(t),{\theta }_t\}$, where the minimum is taken component-wise. We define the small fluctuations event

where C is the constant in Theorem 4.

Lemma 3.

There exists a constant $M_2\ge 0$ independent of T such that, if $M\ge M_2$, then $\mathbb{P}({\mathcal{E}}^{\text{fluc}}(T,M))\ge 1-\mathcal{\ell }\hspace{0.17em}{M}^{-2}$.

The proof is somewhat long but straightforward. It relies on the concentration inequality in Lemma 2 and is given in Appendix B.4.

7.5. Deterministic Analysis of the Dynamics

We start with some definitions. It is useful to recall here that ϵ-JF trajectories start at zero just before time 0 but can become nonzero at time 0 or later because of jumps or unstable drifts.

Definition 6.

For any nonnegative integer vector n, we define $W(\mathbf{n})$ as the set of all points in ${\mathbb{R}}_{+}^{\mathcal{\ell }}$ that can be reached by some ϵ-JF$(\mathbf{n})$ trajectory.

Because ϵ-JF trajectories are by definition nonnegative, $W(\mathbf{n})$ is a subset of ${\mathbb{R}}_{+}^{\mathcal{\ell }}$. Note that the set $W(\mathbf{n})$ depends on ϵ, but because ϵ is held fixed, we suppress this dependence from our notation.

Definition 7

(ϵ-Attracting and ϵ-Invariant Sets).

1. A subset W of ${\mathbb{R}}_{+}^{\mathcal{\ell }}$ is ϵ-attracting if every fluid trajectory $\mathbf{q}(·)$ corresponding to ${\mathit{\lambda }}^{*}$ and initialized at some arbitrary $\mathbf{q}(0)⪰\mathbf{0}$ satisfies

   $$\frac{d}{dt}d(\mathbf{q}(t),W)\le -ϵ,$$(22)
   whenever $\mathbf{q}(t)\notin W$.

2. A subset W of ${\mathbb{R}}_{+}^{\mathcal{\ell }}$ is ϵ-invariant if, for any $\mathit{\lambda }⪰\mathbf{0}$ that satisfies $\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \le ϵ$ and any fluid trajectory $\mathbf{q}(·)$ corresponding to $\mathit{\lambda }$ and initialized at some arbitrary $\mathbf{q}(0)\in W$, we have $\mathbf{q}(\tau )\in W$ for all $\tau \ge 0$.

We observe that if W is ϵ-attracting and $0\le t_0<t_1$, then every fluid trajectory satisfies

$$d(\mathbf{q}(t_1),\hspace{0.17em}W)\le \max \{0,\hspace{0.17em}d(\mathbf{q}(t_0),\hspace{0.17em}W)-(t_1-t_0)ϵ\}.$$(23)

It can be shown that an ϵ-attracting set is ϵ-invariant, but we do not need this fact. We are interested instead in the converse statement, that every ϵ-invariant set is ϵ-attracting, which we then apply to the set $W(\mathbf{n})$; this is the subject of the next lemma.

Lemma 4.

1. Every ϵ-invariant set is ϵ-attracting.

2. For any $\mathbf{n}\in {\mathbb{Z}}_{+}^{\mathcal{\ell }}$, the set $W(\mathbf{n})$ in Definition 6 is ϵ-invariant and, a fortiori, ϵ-attracting.

The proof is given in Appendix B.5 and relies on the intuition that, for an ϵ-invariant set W, ϵ-perturbations of ${\mathit{\lambda }}^{*}$ cannot take the trajectories away from W. This means that there must be a drift toward W that locally counteracts such perturbations. The nonexpansive property of the max-weight dynamics then enables us to extend this local counteraction result into the desired global attraction property.

Let us fix a sample path of the arrival process. For any $t\in [0,T)$, let $\mathbf{n}(t)$ be the realized value of $\mathbf{N}(t)$, that is, $\mathbf{n}(t)$ is the vector with the realized number of jumps in the process $\mathbf{A}(·)$ up to time t (see the paragraph preceding (18)). With a bit of abuse of notation, we let

$$W(t)=W(\mathbf{n}(t-1)).$$(24)

(The reason for the t – 1 term on the right-hand side is that we want to compare $W(·)$ and $\mathbf{Q}(·)$, but $\mathbf{Q}(t)$ is only affected by jumps that happen before time t.)

7.6. Some More Intuition

The general idea is to show that $\mathbf{Q}(·)$ stays close to the set $W(·)$ so that we can ultimately exploit the fact that q_m = 0 for every $\mathbf{q}\in W(T)$. There are two parts to the argument:

1. If, at a certain time, $Q_j(t)$ has a jump (i.e., a large increase), the set W(t) expands along the jth coordinate, and so the distance between $\mathbf{Q}(t)$ and W(t) does not increase.

2. In between jumps, $\mathbf{Q}(t)$ follows the fluid trajectory, plus some fluctuations, within the range allowed by Lemma 3. These fluctuations get “eliminated” because the fluid trajectory is attracted to W(t) (Lemma 4). Note that (21) allows for larger fluctuations in the far past (see the term $M+T-t_0$); however, for fluctuations in the far past, the motion in the direction of W(t) happens for a longer time period, enough to eliminate them. This explains the choice of the threshold θ_t in (11); the logarithmic term in the denominator is included for technical reasons.

7.7. The Distance from the Invariant Set

Given times that satisfy $0\le t_0<t_1\le T$, we say that the interval (t₀, t₁) is jump-free if $A_j(\tau )\le {\theta }_{\tau }$ for all j and all $\tau \in (t_0,t_1)$. Note that the initial time t₀ and the end time t₁ are allowed to be jump times. Let $M_3\ge 1$ be a constant, independent of T, such that, for any $M\prime \ge M_3$,

Lemma 5.

Suppose that $M\ge M_3$ and fix times that satisfy $0\le t_0<t_1\le T$. Consider a sample path under which the event ${\mathcal{E}}^{\text{fluc}}(T,M)$ occurs and the interval (t₀, t₁) is jump-free. Then,

$$d(\mathbf{Q}(t_1),\hspace{0.17em}W(t_1))\le \max \{0,\hspace{0.17em}d(\mathbf{Q}(t_0),\hspace{0.17em}W(t_0))-(t_1-t_0)ϵ\}+\frac{ϵ\gamma }{6}\hspace{0.17em}(M+T-t_0).$$(26)

Note that the lemma also applies when $t_1=t_0+1$ so that the set of integers in (t₀, t₁) is empty. The proof, which is given in Appendix B.6, relies on the sensitivity bound in Theorem 4 and the fact that $W(t_0)$ is ϵ-attractive. The first term on the right-hand side reflects the fact that a fluid trajectory is attracted to $W(·)$ during the jump-free interval; the second term reflects the effect of the smaller fluctuations during the interval (t₀, t₁).

We then apply Lemma 5 and use strong induction on t for $t\le T$ to establish the next lemma. Its proof is given in Appendix B.7.

Lemma 6.

Suppose that $M\ge M_3$. Consider a sample path under which the events ${\mathcal{E}}^{\text{jump}}(T,M)$ and ${\mathcal{E}}^{\text{fluc}}(T,M)$ occur. Then, $d(\mathbf{Q}(T),W(T))\le Mϵ/2$.

7.8. Bounding $\mathbb{E}[{\mathbf{Q}}_m(t)]$

Let $\overline{M}=\max \{M_1,M_2,M_3\}$, where M₁, M₂, and M₃ are the constants in Lemma 1, Lemma 3, and (25), respectively. Because these constants are independent of T, the constant $\overline{M}$ is also independent of T.

Let us consider some $M\ge \overline{M}$ and a sample path under which the events ${\mathcal{E}}^{\text{jump}}(T,M)$ and ${\mathcal{E}}^{\text{fluc}}(T,M)$ occur. In particular, we have ${\mathit{\gamma }}^T\mathbf{n}\le 1$, where n is the realized value of N, that is, the vector with the number of jumps until time T – 1 for that particular sample path. The ϵ-JF($\mathit{\gamma }$) condition, which we assume to hold, implies that every ϵ-JF(n) trajectory with ${\mathit{\gamma }}^T\mathbf{n}\le 1$ keeps q_m at zero, and therefore, every vector $\mathbf{q}\in W(T)$ has q_m = 0. Consequently, for every sample path in ${\mathcal{E}}^{\text{jump}}(T,M)\cap {\mathcal{E}}^{\text{fluc}}(T,M)$, we have

where the second inequality follows from Lemma 6. Therefore, for any $M\ge \overline{M}$, we havewhere the first inequality follows from (27) and the union bound and the second inequality is due to Lemmas 1 and 3. Because β is by definition greater than one, the formula $\mathbb{E}[Q_m(T)]={\int }_0^{\infty }\mathbb{P}(Q_m(t)>M)\hspace{0.17em}dM$ implies that $\mathbb{E}[Q_m(T)]$ is bounded above by a constant that does not depend on T. Furthermore, note that this bound applies uniformly to all processes in the class ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$ for $\delta =\gamma ϵ/20C$ (see (14)). This shows that queue m is robustly delay stable and completes the proof of the first direction of Theorem 1.

8. Proof of the Reverse Direction of Theorem 1 (RDS$\Rightarrow$ RJF)

In this section, we prove the reverse (“only if”) direction of Theorem 1, that is, that RDS implies that the ϵ-JF$(\mathit{\gamma })$ condition holds for some $ϵ>0$. The proof is organized in a sequence of lemmas whose proofs are collected in Appendix C.

We actually prove the contrapositive and start by assuming that, for every $ϵ>0$, there exists an ϵ-JF$(\mathbf{n})$ trajectory ${\mathbf{q}}^{ϵ}(·)$ with ${\mathit{\gamma }}^T\mathbf{n}\le 1$ and such that ${\mathbf{q}}_m^{ϵ}(t)>0$ at some positive time t.

We keep ${\mathit{\lambda }}^{*},\hspace{0.17em}\mathit{\gamma }$, and ϵ fixed throughout the proof and show that there exists an arrival processes in the class ${\mathcal{A}}_{ϵ}(\mathit{\gamma };{\mathit{\lambda }}^{*})$ for which queue m is not delay stable. Because ϵ can be arbitrarily small, this implies that there exists no δ such that queue m is delay stable for all arrival processes in the class ${\mathcal{A}}_{\delta }(\mathit{\gamma };{\mathit{\lambda }}^{*})$, and therefore, queue m is not RDS. However, before proceeding to the formal arguments, we overview informally the key ideas in the proof.

8.1. Outline of the Proof

The main idea is to construct a certain arrival process $\mathbf{A}(·)$ in the class ${\mathcal{A}}_{ϵ}(\mathit{\gamma };{\mathit{\lambda }}^{*})$, whose arrival rate is a time-scaled version of the piecewise constant rate $\mathit{\lambda }(·)$ associated with the ϵ-JF(n) trajectory. We then use the bounded sensitivity property of the MW dynamics (Theorem 4) to show that the resulting process $\mathbf{Q}(·)$ tracks a suitably scaled (by a factor of T) version of the ϵ-JF trajectory ${\mathbf{q}}^{ϵ}(·)$ with substantial probability. In particular, $\mathbf{Q}(T)$ is (with substantial probability) comparable to $T{\mathbf{q}}^{ϵ}(1)$, leading to a large value of $\mathbb{E}[Q_m(T)]$. This part of the argument capitalizes on the fact that the number of jumps of the ϵ-JF(n) trajectory is limited by the condition ${\mathit{\gamma }}^T\mathbf{n}\le 1$.

On the technical side, the tracking result involves two separate arguments:

1. Whenever the ϵ-JF(n) trajectory has a jump, at some time τ, there is substantial probability that the stochastic process also has a jump at some time near the scaled counterpart, $T\tau$, of τ; see Lemma 8.

2. In between jump times of the ϵ-JF(n) trajectory, we use concentration inequalities to show that there is a fairly large probability that the stochastic process stays close to its fluid counterpart.

8.2. Jumps of the ϵ-JF(n) Trajectory

We fix a network with $\mathcal{\ell }$ nodes; a set $\mathcal{M}$ of possible service vectors; an arrival rate vector ${\mathit{\lambda }}^{*}⪰\mathbf{0}$; a particular queue, m, of interest; and a vector $\mathit{\gamma }$ of tail exponents with components in $(0,\infty ]$. We also fix some $ϵ>0$ and assume that the ϵ-JF($\mathit{\gamma }$) condition fails to hold.

We start with a few elementary observations, namely, that the ϵ-JF(n) trajectories of interest can be taken, without loss of generality, through scaling and perturbations, to have some convenient properties that allow us to simplify subsequent notation and arguments. The proof is given in Appendix C.1.

Lemma 7.

If the ϵ-JF($\mathit{\gamma }$) condition fails to hold, then there exists some $\mathbf{n}⪰\mathbf{0}$ with ${\mathit{\gamma }}^T\mathbf{n}\le 1$ and an ϵ-JF(n) trajectory ${\mathbf{q}}^{ϵ}(·)$ with the following properties:

1. $q_m^{ϵ}(1)>0$.

2. The times at which ${\mathbf{q}}^{ϵ}(·)$ is discontinuous (the jump times) all belong to the open interval (0, 1).

3. At each jump time, exactly one of the components of ${\mathbf{q}}^{ϵ}(·)$ is discontinuous.

4. The arrival rate associated to ${\mathbf{q}}^{ϵ}(·)$ satisfies ${\inf }_t{\lambda }_j(t)>0$ for all j.

For the rest of the proof, we fix an ϵ-JF(n) trajectory with the properties in Lemma 7, together with the associated vector n and rate function $\mathit{\lambda }(·)$. We define $n=n_1+\cdots +n_{\mathcal{\ell }}$, which is the total number of jumps.⁵

We define ${\mathrm{\Theta }}_0=0,\hspace{0.17em}{\mathrm{\Theta }}_{n+1}=1$, and for $k=1,\dots ,n$, let Θ_k be the kth jump time. In particular,

We use j_k to refer to the queue at which the kth jump occurs and a_k to refer to the size of the kth jump. In particular, at time Θ_k, for $k=1,\dots ,n,\hspace{0.17em}{q}_j(·)$ is continuous for every $j\ne j_k$, and

8.3. Defining Certain Constants

As in (16), we define

Moreover, similar to (13), we let

By arguing as in Claim 1, we can and do assume, without loss of generality, that $\gamma \le 1$. We then define a positive constant

and also let

(In case n = 0, the last term inside the brackets is taken to be zero.)

8.4. Defining the Stochastic Arrivals

Let us fix some constants $t_0\ge 0$ and T > 0 and keep them fixed until the end of the proof in Section 8.7. In this section, we define a stochastic arrival process over an interval of the form $[t_0,t_0+T)$, thus constructing what we call an episode of the overall process. Later, in Section 8.7, we concatenate multiple episodes to construct the stochastic process over the entire timeline $[0,\infty )$.

Consider the arrival rate function $\mathit{\lambda }(·)$ of the ϵ-JF(n) trajectory; in particular, $\Vert \mathit{\lambda }(t)-{\mathit{\lambda }}^{*}\Vert \le ϵ$. The arrival rate vector for the stochastic process during the episode is a time-scaled (by a factor of T) and shifted (by t₀) version of $\mathit{\lambda }(·)$. More concretely, we let

Clearly,

Furthermore, it follows from Lemma 7(d) that ${\inf }_t{\overline{\lambda }}_j(t)>0$ for every j.

We now digress to introduce certain constants that are used to specify the exact form of the distribution of the arrival processes. For any $\alpha >0$, we let

where $\overline{\mu }$ is defined in (30). Then, for any $\alpha >0$, we have

Definition 8

(Arrivals During an Episode). Given T > 0 and $t_0\ge 0$, we define the arrival process over the interval $t\in [t_0,t_0+T)$ (which we call an episode) as follows:

1. If ${\gamma }_j=\infty$, then $A_j(t)={\overline{\lambda }}_j(t)$ (deterministically).

2. If ${\gamma }_j<\infty$, then $A_j(t)$ is a random variable with probability density function

   $$f_{A_j(t)}(x)=\frac{{\overline{\lambda }}_j(t)}{\sigma ({\gamma }_j)}·x^{-(2+{\gamma }_j)}\hspace{0.17em}\log \hspace{0.17em}(x+1)\mathrm{𝟙}\left(x\ge \overline{\mu }\right)+\left(1-\frac{{\overline{\lambda }}_j(t)\sigma (1+{\gamma }_j)}{\sigma ({\gamma }_j)}\right)\delta (x),$$(38)
   where $\mathrm{𝟙}(·)$ denotes the indicator function, $\delta (·)$ is Dirac’s delta function, and $\sigma (·)$ is as defined in (36).

3. The $A_j(t)$ for different j and t are independent.

We refer to $\{\mathbf{A}(t):t\in [t_0,t_0+T)\}$ as an episode-adjusted arrival process.

From (37), we obtain $\sigma ({\gamma }_j)/\sigma (1+{\gamma }_j)\ge \overline{\mu }\ge {\overline{\lambda }}_j(t)$, where the last inequality is due to (30) and (35). Therefore, the coefficient of the delta function is nonnegative, and we have a well-defined distribution. It is also easy to verify that ${\int }_0^{\infty }{f}_{A_j(t)}(x)\hspace{0.17em}dx=1$. Furthermore, from (35), $\overline{{\lambda }_j}(t)$ is bounded above. It follows that each $A_j(t)$ is dominated by a random variable ${\overline{A}}_j$ with tail exponent γ_j, and consequently, the process also has tail exponent γ_j. Moreover, $\mathbb{E}[A_j(t)]={\int }_0^{\infty }x\hspace{0.17em}{f}_{A_j(t)}(x)\hspace{0.17em}dx={\overline{\lambda }}_j(t)$. Therefore, using again (35), we have $\Vert \mathbb{E}[\mathbf{A}(t)]-{\mathit{\lambda }}^{*}\Vert \le ϵ$, for all $t\in [t_0,t_0+T)$. In particular, the process $\mathbf{A}(·)$ belongs to the class ${\mathcal{A}}_{ϵ}(\mathit{\gamma };{\mathit{\lambda }}^{*})$ as desired.

8.5. Probabilistic Analysis

We aim to show that, during an episode and with significant probability, the queue vector process $\mathbf{Q}(·)$ stays close to a scaled version of the ϵ-JF trajectory, that is, that

To accomplish this, we consider each interval of the form $[t_0+{\mathrm{\Theta }}_{k}T,t_0+{\mathrm{\Theta }}_{k+1}T)$ for $k=0,1,\dots ,n$ and show that there is a substantial probability that the arrival process we have defined has the following properties: (a) as long as k > 0, it has a jump in a small segment in the beginning of the interval, and (b) it has small fluctuations in the rest of the interval. We define events that capture these two properties.

For $k=1,\dots ,n$, let ${\mathbf{B}}_k$ be the cumulative arrival vector over the interval $[t_0+{\mathrm{\Theta }}_{k}T,t_0+{\mathrm{\Theta }}_{k}T+dT)$, that is,⁶

We let ${\mathcal{E}}_k^{\text{jump}}$ be the event that ${\mathbf{B}}_k$ emulates the jump in ${\mathbf{q}}^{ϵ}(·)$ at time Θ_k scaled by T, that is,

where j_k is defined as the index of the queue at which the kth jump takes place and d is the constant defined in (33).

Lemma 8.

There exist $\psi \in (0,1)$ and ${\overline{T}}_1>0$ such that, if $T\ge \overline{T_1}$, then for $k=1,\dots ,n$ and for the episode-adjusted arrival process over an episode $[t_0,t_0+T)$, we have $\mathbb{P}({\mathcal{E}}_k^{\text{jump}})\ge \psi T^{-{\gamma }_{j_k}}\hspace{0.17em}\log \hspace{0.17em}T$.

The proof is given in Appendix C.2.

Recall now that the function $\mathit{\lambda }(·)$ driving the trajectory ${\mathbf{q}}^{ϵ}(·)$ is piecewise constant with a finite number of pieces. We use r to denote the number of such pieces. We then proceed to define certain small fluctuation events. For $k=0,1,\dots ,n$, we let ${\mathcal{E}}_k^{\text{fluc}}$ be the event that the cumulative fluctuations of $\mathbf{A}(·)$ over the interval $[t_0+{\mathrm{\Theta }}_{k}T+dT,t_0+{\mathrm{\Theta }}_{k+1}T)$ are small, that is,

Lemma 9.

There exists a ${\overline{T}}_2\ge 0$ such that, if $T\ge {\overline{T}}_2$, then for $k=0,1,\dots ,n$ and for the episode-adjusted process over an episode $[t_0,t_0+T)$, we have $\mathbb{P}({\mathcal{E}}_k^{\text{fluc}})\ge 1/2$.

The proof is given in Appendix C.3.

Note that each one of the events ${\mathcal{E}}_k^{\text{jump}}$ for $k=1,\dots ,n$ and ${\mathcal{E}}_k^{\text{fluc}}$ for $k=0,\dots ,n$ is determined by the arrival process during a particular interval and all of these intervals are disjoint. Thus, the independence assumption on the arrival process implies that all of these events are independent. Therefore, if $T\ge \max \{{\overline{T}}_1,{\overline{T}}_2\}$, then

where the first inequality follows from Lemmas 8 and 9. The second inequality is because $n\ge 1$ and (without loss of generality) $\log T\ge 1$. The third inequality is due to $n\gamma ={\sum }_{j=1}^{\mathcal{\ell }}{n}_j\gamma \le {\sum }_{j=1}^{\mathcal{\ell }}{n}_j{\gamma }_j\le 1$ so that $n\le 1/\gamma$ together with the fact $\psi \le 1$ (see Lemma 8). The last inequality is again because ${\mathit{\gamma }}^T\mathbf{n}\le 1$.

8.6. $\mathbb{E}[Q_m]$ is Large at the End of an Episode

We are now ready to argue that, if the events ${\mathcal{E}}_1^{\text{jump}},\dots ,{\mathcal{E}}_n^{\text{jump}}$ and ${\mathcal{E}}_0^{\text{fluc}},\dots ,{\mathcal{E}}_n^{\text{fluc}}$ occur, then, over an episode $[t_0,t_0+T)$, the process $\mathbf{Q}(·)$ stays close to the suitably scaled ϵ-JF trajectory. As a consequence, the value of Q_m at the end of the episode becomes of order cT, where $c=q_m^{ϵ}(1)>0$ as in (32). This argument is entirely deterministic. It is carried out in the course of the proof of the next lemma (in Appendix C.4) and relies on the sensitivity bound in Theorem 4.

Lemma 10.

There exists a ${\overline{T}}_3\ge 0$ such that, if $T\ge {\overline{T}}_3$, then the following holds. If a sample path of the episode-adjusted process over the episode $[t_0,t_0+T)$ satisfies the events ${\mathcal{E}}_1^{\text{jump}},\dots ,{\mathcal{E}}_n^{\text{jump}}$ and ${\mathcal{E}}_0^{\text{fluc}},\dots ,{\mathcal{E}}_n^{\text{fluc}}$ and if $\Vert \mathbf{Q}(t_0)\Vert \le cT/5$, then $Q_m(t_0+T)\ge cT/2$.

Let $\rho ={(\psi /2)}^{1/\gamma }/4$ and $\overline{T}=\max \{2,{\overline{T}}_1,{\overline{T}}_2,{\overline{T}}_3\}$, where ${\overline{T}}_1,\hspace{0.17em}{\overline{T}}_2$, and ${\overline{T}}_3$ are the constants in Lemmas 8–10, respectively. We note that all of these constants, ${\overline{T}}_1,\hspace{0.17em}{\overline{T}}_2,\hspace{0.17em}{\overline{T}}_3$, and therefore $\overline{T}$ as well, are defined in terms of general parameters and properties of the particular ϵ-JF trajectory and are deterministic. Lemma 10 and (42) imply that, for an episode $(t_0,t_0+T)$ with $T\ge \overline{T}$ and initialized so that $\Vert \mathbf{Q}(t_0)\Vert \le cT/5$, we have

which implies that

8.7. Concatenating Episodes over the Entire Timeline

So far, we have defined and studied an arrival process over an episode $[t_0,t_0+T)$. We now concatenate a sequence of such episodes of increasing duration, which defines an arrival process over an infinite timeline.

We define times $T_0,T_1,T_2,\dots ,$ and arrival processes for the intervals $[T_i,T_{i+1})$, recursively, as follows. We let $T_0=0$ and $T_1=\overline{T}$, where $\overline{T}$ is defined in the last paragraph of Section 8.6. We also let $\mathbf{A}(·)$ for $t\in [T_0,T_1)$ be the corresponding episode-adjusted process as in Definition 8. Suppose now that we have defined T_i for some $i\ge 1$ as well as the arrival process for $t\in [0,T_i)$. We then let

Finally, we define the arrival process over the episode $[T_i,T_{i+1})$ to be the corresponding episode-adjusted process. With this recursion, the arrival process is now well-defined for all times $t\ge 0$.

Note that $\mathbb{E}[\Vert \mathbf{Q}(T_i)\Vert ]\le \mathbb{E}\left[{\sum }_{t=0}^{T_i-1}\Vert \mathbf{A}(t)\Vert \right]={\sum }_{t=0}^{T_i-1}\mathbb{E}[\Vert \mathbf{A}(t)\Vert ]\le T_i\mathcal{\ell }(\Vert {\mathit{\lambda }}^{*}\Vert +ϵ)<\infty$. This guarantees that all T_i are finite and we have an infinite number of episodes. Moreover, note that, for $i=1,2,\dots$, we have $T_{i+1}\ge 2T_i$. As a result, $T_i\ge 2^{i-1}\overline{T}$, and also,

where the last inequality is because $T_i\ge 2^{i-1}\overline{T}\ge 2^i$.

We define the event

and use the Markov inequality to obtainwhere the second inequality is due to (45).

Recall now that Inequality (44), which is about an episode of length T, makes use of the assumption $\Vert \mathbf{Q}(t_0)\Vert \le cT/5$, where t₀ is the start time of the episode. According to (47), this assumption is satisfied at the start time of the episode $[T_i,T_{i-1})$ with probability at least 1/2. By interpreting (44) as a statement about conditional expectations and with t₀ and $t_0+T$ replaced by T_i and $T_{i+1}$, respectively, we obtain

where the last inequality follows from (46). Therefore, $\mathbb{E}[Q_m(T_i)]$ grows unbounded as i increases. Consequently, under the arrival process that we constructed, queue m is not delay stable. This conclusion is obtained for any positive choice of ϵ, no matter how small, and establishes that queue m is not RDS. This completes the proof of the second direction of Theorem 1.

9. Proof of Theorem 2

9.1. Proof of the First Direction

Let us fix some $ϵ>0$. To establish one direction of the result, we assume that the ϵ-JF$(\mathit{\gamma })$ condition holds for every $\mathit{\gamma }\in \mathrm{\Gamma }$. We show that there exists a special ϵ-Lyapunov function.

Let $\mathcal{N}$ be the set of all nonnegative integer vectors n such that n_j = 0 for j > h; that is, we allow arbitrarily many jumps at the heavy-tailed queues and no jumps at the light-tailed ones. As in Definition 6, for any nonnegative integer vector n, let $W(\mathbf{n})$ be the set of all points in ${\mathbb{R}}_{+}^{\mathcal{\ell }}$ that are reachable by ϵ-JF$(\mathbf{n})$ trajectories. Let $W={\displaystyle {\cup }_{\mathbf{n}\in \mathcal{N}}W}(\mathbf{n})$ and consider a Lyapunov function $V(·)$ equal to the distance from W, that is, $V(\mathbf{x})=d(\mathbf{x},W)$, for any $\mathbf{x}\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$. We show that this Lyapunov function has the desired properties.

The distance function is clearly Lipschitz continuous with a Lipschitz constant equal to one, which implies the first property in the definition of special ϵ-Lyapunov functions.

For the second property, Lemma 4(b) applies and shows that each set $W(\mathbf{n})$ is ϵ-invariant. It can be seen that the union, W, of the ϵ-invariant sets $W(\mathbf{n})$ is also ϵ-invariant. It then follows from Lemma 4(a) that W is ϵ-attracting. This proves the second property in Definition 5.

Note that every $\mathbf{n}\in \mathcal{N}$ satisfies the inequality ${\mathit{\gamma }}^T\mathbf{n}\le 1$ for some $\mathit{\gamma }\in \mathrm{\Gamma }$. Because the ϵ-JF$(\mathit{\gamma })$ condition holds for every $\mathit{\gamma }\in \mathrm{\Gamma }$, it follows that every ϵ-JF(n) trajectory with $\mathbf{n}\in \mathcal{N}$ satisfies $q_m(t)=0$ for all t. Hence, q_m = 0 for all $\mathbf{q}\in W$. Furthermore, because $\mathbf{0}\in W$, we have $V(\mathbf{0})=0$. This establishes the third property in Definition 5.

Finally, W is closed under jumps along coordinates associated with heavy-tailed arrivals. Therefore, $V(·)$ is nonincreasing along those directions, and the fourth property in Definition 5 follows. Thus, $V(·)$ has all the required properties of special ϵ-Lyapunov functions. This completes the proof of one direction of the theorem.

9.2. Proof of the Reverse Direction

We continue with the proof of the reverse direction. We fix some $ϵ>0$ and assume that there exists a special ϵ-Lyapunov function $V(·)$ and let $W=\{\mathbf{x}\in {\mathbb{R}}_{+}^{\mathcal{\ell }}|V(\mathbf{x})=0\}$. The argument rests on the ϵ-invariance of W, which, in turn, relies on some properties of the MW dynamics that we discuss next.

For any $\mathit{\lambda },\mathbf{x}\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$, let

where $\mathbf{q}(·)$ is the fluid trajectory corresponding to arrival rate $\mathit{\lambda }$ and initialized with $\mathbf{q}(0)=\mathbf{x}$. In view of (9), we have ${\mathit{\xi }}_{\mathit{\lambda }}(\mathbf{x})\in {\overline{\mathcal{D}}}_{\mathit{\lambda }}(\mathbf{x})$. Moreover, it is shown in lemma 2(a) of Sharifnassab et al. (2019) that ${\mathit{\xi }}_{\mathit{\lambda }}(\mathbf{x})$ has the minimum norm among all vectors in ${\overline{\mathcal{D}}}_{\mathit{\lambda }}(\mathbf{x})$, that is,

Here, the minimizer is unique.

Given a closed and convex set $\mathcal{A}\subset {\mathbb{R}}^{\mathcal{\ell }}$ and a point $\mathbf{x}\in {\mathbb{R}}^{\mathcal{\ell }}$, we denote by ${\pi }_{\mathcal{A}}(\mathbf{x})$ the projection of x on $\mathcal{A}$, defined as the point in $\mathcal{A}$ that is closest to x. With this terminology, ${\mathit{\xi }}_{\mathit{\lambda }}(\mathbf{x})$ is the projection ${\pi }_{{\overline{\mathcal{D}}}_{\mathit{\lambda }}(\mathbf{x})}(\mathbf{0})$ of the zero vector on the set ${\overline{\mathcal{D}}}_{\mathit{\lambda }}(\mathbf{x})$.

In what follows, we also make use of an elementary property of projections: if $\mathcal{A}$ is a closed convex set, b is some vector, and $\mathcal{B}=\mathcal{A}+\mathbf{b}$, then

As a consequence of this, for any ${\mathit{\lambda }}_1,\hspace{0.17em}{\mathit{\lambda }}_2$, and x in ${\mathbb{R}}_{+}^{\mathcal{\ell }}$,

where the second equality is becauseand the inequality follows from (50).

Lemma 11.

The set W is ϵ-invariant.

Proof.

Because V is a special ϵ-Lyapunov function, it is Lipschitz continuous with Lipschitz constant one. Let $\mathit{\lambda }\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$ be such that $\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \le ϵ$ and consider fluid trajectories $\mathbf{q}(·)$ and $\mathbf{p}(·)$ corresponding to arrival rates $\mathit{\lambda }$ and ${\mathit{\lambda }}^{*}$, respectively, initialized with the same nonnegative vector $\mathbf{q}(0)=\mathbf{p}(0)\notin W$. Then,

$$\begin{array}{ll}\dot{V}(\mathbf{q}(t)){|}_{t=0}\hfill & =\underset{\delta \downarrow 0}{\lim }\frac{V(\mathbf{q}(\delta ))-V(\mathbf{q}(0))}{\delta }\hfill \\ \hfill & =\underset{\delta \downarrow 0}{\lim }\frac{V(\mathbf{p}(\delta ))+V(\mathbf{q}(\delta ))-V(\mathbf{p}(\delta ))-V(\mathbf{q}(0))}{\delta }\hfill \\ \hfill & \le \underset{\delta \downarrow 0}{\lim }\frac{[V(\mathbf{p}(\delta ))+\Vert \mathbf{q}(\delta )-\mathbf{p}(\delta )\Vert ]-V(\mathbf{q}(0))}{\delta }\hfill \\ \hfill & =\underset{\delta \downarrow 0}{\lim }\left(\frac{V(\mathbf{p}(\delta ))-V(\mathbf{p}(0))}{\delta }+\frac{\Vert \mathbf{q}(\delta )-\mathbf{p}(\delta )\Vert }{\delta }\right)\hfill \\ \hfill & \le \underset{\delta \downarrow 0}{\lim }\left(\frac{V(\mathbf{p}(\delta ))-V(\mathbf{p}(0))}{\delta }+\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \right)\hfill \\ \hfill & =\dot{V}(\mathbf{p}(t)){|}_{t=0}+\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \hfill \\ \hfill & \le -ϵ+ϵ\hfill \\ \hfill & =0,\hfill \end{array}$$(52)

where the first inequality is because V has a Lipschitz constant equal to one, the third equality is due to $\mathbf{q}(0)=\mathbf{p}(0)$, and the second inequality follows from (51). The last inequality follows from the second property of special ϵ-Lyapunov functions in Definition 5 and the assumption $\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \le ϵ$.

This argument shows that, for any $\mathit{\lambda }\in {\mathbb{R}}_{+}^{\mathcal{\ell }}$ with $\Vert \mathit{\lambda }-{\mathit{\lambda }}^{*}\Vert \le ϵ$ and for any fluid trajectory $\mathbf{q}(·)$ corresponding to arrival rate $\mathit{\lambda }$, the distance from the set W cannot increase. In particular, if $\mathbf{q}(·)$ is initialized with $\mathbf{q}(0)\in W$, it must stay in W. Therefore, using the terminology in Definition 7, W is ϵ-invariant. □

From the third property in the definition of special ϵ-Lyapunov functions, we have $V(\mathbf{0})=0$ and, therefore, $\mathbf{0}\in W$. Thus, every ϵ-JF(n) trajectory starts in W. From the fourth property in the definition of special ϵ-Lyapunov functions, W is closed with respect to positive jumps along the coordinates associated with heavy-tailed arrivals. Using also Lemma 11 for the times between jumps, we see that, for any $\mathbf{n}\in \mathcal{N}$, every ϵ-JF(n) trajectory stays in W. Equivalently, for any $\mathit{\gamma }\in \mathrm{\Gamma }$, every ϵ-JF($\mathit{\gamma }$) trajectory stays in W. Finally, employing again the third property of special ϵ-Lyapunov functions, we have q_m = 0 for all $\mathbf{q}\in W$. This implies that $q_m(t)=0$ for all ϵ-JF$(\mathit{\gamma })$ trajectories $\mathbf{q}(·)$ with $\mathit{\gamma }\in \mathrm{\Gamma }$ and all $t\ge 0$. This establishes the ϵ-JF$(\mathit{\gamma })$ condition for all $\mathit{\gamma }\in \mathrm{\Gamma }$ and completes the proof of Theorem 2.

9.3. Proof of Corollary 1

For part (a), fix some $ϵ>0$ and suppose that there exists a special ϵ-Lyapunov function. Theorem 2 implies that the ϵ-JF($\mathit{\gamma }$) condition holds for every $\mathit{\gamma }\in \mathrm{\Gamma }$. It then follows from Theorem 1 that queue m is RDS for every $\mathit{\gamma }\in \mathrm{\Gamma }$.

For part (b), we fix some $ϵ>0$ and assume that queue m is ϵ-RDS for all $\mathit{\gamma }\in \mathrm{\Gamma }$. In particular, queue m is RDS, and Theorem 1 implies that the $ϵ\prime$-JF($\mathit{\gamma }$) condition holds for some $ϵ\prime >0$. However, a close inspection of the proof of the reverse part of Theorem 1 reveals that we can in fact choose $ϵ\prime$ to be the same as ϵ. Thus, the ϵ-JF($\mathit{\gamma }$) condition holds, and Theorem 2 implies that there exists a special ϵ-Lyapunov function.

10. Discussion

In this section, we summarize some key points and conclude with a few open questions.

10.1. Framing and Results

We have addressed the problem of delay stability for a class of queueing networks that operate under the max-weight scheduling policy when some arrival processes are heavy-tailed and some are light-tailed. The overall purpose was to develop conditions for delay stability in terms of fluid-like models. However, as illustrated by the example in Section 3, delay instability can be the result of multiple coordinated large jumps. The probabilities of such large jumps are, in turn, affected by the tail exponents of the arrival processes. Given that traditional fluid models are oblivious to the tail exponents, we introduce JF models, a generalization that allows for jumps along the coordinates associated with heavy-tailed flows subject to a budget on the number of jumps with the budget being determined by the tail exponents.

At the same time, it became clear that tight conditions for delay stability that do not depend on the details of the arrival distributions are only possible under a suitable robust formulation with respect to both the arrival rates and the arrival process distributions. With a careful choice of definitions, we were finally able to establish necessary and sufficient conditions for robust delay stability in terms of ϵ-JF models.

In Section 3, we also discuss a related, so-called ZF condition. The ZF condition essentially examines fluid trajectories that start at zero and involve a single jump and leads to a necessary condition for delay stability (Markakis et al. 2018), but the question whether it can also form the basis for a sufficient condition was open. Our results show that, in order to obtain necessary and sufficient conditions, we need to examine a richer set of trajectories that involve multiple jumps.

Finally, earlier works (Markakis 2013, Markakis et al. 2018) show that Lyapunov functions with certain structural properties can yield sufficient conditions for delay stability. But it was not clear if and when delay stability is equivalent to the existence of such Lyapunov functions. Our results make progress toward establishing the completeness of such a Lyapunov-based methodology for the regime in which the heavy-tailed flows can have arbitrarily small tail exponents.

Our RJF condition is difficult to test for general networks. In some sense, this reflects the intrinsic complexity of the (robust) delay stability problem. The Lyapunov-based condition also appears to be hard to test for general networks.

10.2. Alternative Formulations

Given the complexity of the RJF condition, it is natural to inquire about simpler alternatives. For example, is it possible to obtain tight delay stability results (without robustness) if we consider JF models with a constant rate $\mathit{\lambda }(·)$? In the same spirit, can we restrict to the case in which all jumps in ϵ-JF models take place at the same time? Might it be easier to consider concrete arrival processes instead of focusing on delay stability for all arrival processes with given exponents?

For all three of these questions, the answer is negative. We discuss such variations and related (counter)examples in Appendix A.

10.3. Open Problems

We collect here a few open problems and possible future research directions.

1. Can the results be generalized to other scheduling policies, for example, MW-α policies (Neely 2010), an extension of the MW policy considered in this paper, or more generally to other stochastic networks whose stability has been studied using fluid models? One obstacle here is that our main result relies heavily on a particular fluctuation bound, which is established specifically for the MW dynamics (Sharifnassab et al. 2020). However, progress may be possible if we rely on alternative stochastic bounding techniques.

2. Can we identify some special classes of networks for which our criteria (either the RJF condition or the Luyapunov-based condition) can be tested in polynomial time?

3. Is the RJF condition, which involves time-varying $\mathit{\lambda }(t)$ with $\mathit{\lambda }(t)\approx {\mathit{\lambda }}^{*}$ equivalent to a similar condition in which we only consider ϵ-JF trajectories with time-invariant $\mathit{\lambda }(t)=\mathit{\lambda }$ with $\mathit{\lambda }\approx {\mathit{\lambda }}^{*}$? See Appendix A for further discussion and some conjectures.