Stability of linear EDF networks with resource sharing

Massoulié and Roberts [34] introduced resource sharing networks, commonly called bandwidth sharing models, to model congestion control problems for Internet flows. In such systems, flows, corresponding to continuous transfers of elastic documents, are being transmitted, requiring simultaneous service at all nodes along their routes. Various service protocols for resource sharing networks have been proposed. Some of the most popular of them are proportional fairness, originating in a work of Kelly [23], and more general \(\alpha \)-fair policies, introduced by Mo and Walrand [36].

A natural problem in the theory of queueing systems with simultaneous resource possession is their stability when the average load placed on each resource is less than its capacity. Assuming exponentially distributed document sizes, de Veciana, Lee and Konstantopoulos [11] showed stability of weighted max-min fair and proportionally fair policies. Bonald and Massoulié [7] obtained a counterpart of these results for weighted \(\alpha \)-fair protocols. Massoulié [33] established stability of a fluid model for a resource sharing system with exponential arrival and document sizes, incorporating additional routing. This allowed him to show stability of stochastic resource sharing networks when file sizes have phase-type distributions. More recently, Gromoll and Williams [18] proposed a fluid model associated with a stochastic resource sharing network with generally distributed interarrival times and document sizes, working under a fairly general bandwidth sharing discipline. Under mild assumptions, they showed that rescaled measure-valued processes corresponding to a sequence of such networks are tight and any weak limit point of this sequence is almost surely a fluid model solution. This, together with stability of fluid models for weighted \(\alpha \)-fair policies in linear and tree networks established by Gromoll and Williams [17], may be used to infer stability of the corresponding stochastic systems. The interested reader is referred to [18] for more references regarding stability results for generalized bandwidth sharing policies.

Verloop, Borst and Núñez Queija [40] investigated linear, strictly subcritical resource sharing networks with Poisson arrivals and generally distributed document sizes, working under the Shortest Remaining Processing Time (SRPT) and Least Attained Service (LAS) scheduling. They found that such systems may be unstable and, moreover, for networks with sufficiently many nodes, instability may arise at arbitrarily low traffic loads. From a broader perspective, they have observed that a linear network topology “appears already sufficiently rich to exhibit many of the qualitative phenomena that may occur for general network topologies and route structures”. Having said this, we must also admit that there are service disciplines making the underlying linear strictly subcritical resource sharing networks stable, while being unstable for some other network topologies, for example, UFOS (Utilization First, Output Second), introduced by Harrison et al. [21]. In any case, the results of [40] indicate that it is worthwhile to understand stability phenomena in linear networks with resource sharing as an important first step in the analysis of systems with more complex topologies.

Recent years have brought a rapidly increasing demand for real-time services, in which jobs have specific timing requirements. Examples of such services include voice and video transmission, manufacturing systems, where the orders have due dates, real-time control systems and tracking systems. Another important class of applications arises in medical scheduling problems, like organ allocation or prioritizing admissions to emergency rooms.

There are several possible reactions of a real-time system to deadline misses. In this paper, we will focus on the case of soft deadlines in which lateness is permitted and the jobs completed after their deadlines are used.

A natural service protocol for real-time systems is Earliest Deadline First (EDF), in which the job with the shortest remaining lead time, i.e., the difference between its deadline and the current time, is selected for service. A definition of the preemptive EDF policy for a resource sharing network with soft deadlines and arbitrary topology was given by Kruk [26]. In order to describe the contents of the latter paper, for each element i from the set \(\mathbf{I}\) of available routes of the network, each time \(t\ge 0\) and each \(s\in \mathbb {R}\), let \(Y_i(t,s)\) denote the cumulative idleness by time t with regard to transmission of flows with lead times at time t not greater than s. The main result of Kruk [26] was to show that, under mild distributional assumptions, the preemptive EDF resource sharing protocol minimizes \(\sum _{i\in \mathbf{I}} Y_i\) with respect to the pointwise functional inequality. (The latter relation is a partial ordering, according to which, for functions f, g of two variables t, s, we have \(f\le g\) if and only if \(f(t,s)\le g(t,s)\) for all arguments t and s.) One may wonder whether the above (or a similar) minimality result may be used to show stability of the corresponding EDF networks. While this idea looks attractive, we have not been able to obtain any results along this line. Related optimality properties of the EDF protocol were studied by Liu and Layland [32], Panwar and Towsley [38, 39], Moyal [37], Kruk et al. [31], Atar et al. [3], in the context of single-server systems, and by Baruah [4], who investigated resource sharing networks with hard deadlines.

In this paper, we consider linear resource sharing networks with renewal arrival streams and generally distributed document sizes. Upon arrival to the network, a flow on each route is assigned a soft random deadline drawn from a distribution associated with this route. Assuming mild conditions on the model stochastic primitives, we show that a strictly subcritical network of this type is stable under the preemptive EDF service policy. This result is in sharp contrast to instability of strictly subcritical linear networks under the SRPT protocol established in [40]. Indeed, there is a deep relation between the EDF and SRPT scheduling strategies. Their similarity was first noticed (at least to our knowledge) by Bender, Chakrabarti and Muthukrishnan [5] and then, more explicitly, by Down, Gromoll and Puha [14], who investigated fluid limits for SRPT queues using an auxiliary process similar to the one introduced by Doytchinov, Lehoczky and Shreve [15] in the context of heavy traffic analysis for EDF queues. In fact, in Sect. 8 of our paper, we apply our main result, together with an idea of Bender, Chakrabarti and Muthukrishnan [5], to propose a stable regularization of the SRPT protocol for linear resource sharing networks.

The main idea of our stability proof is to verify the condition given in Theorem 3.1 of Dai [9] (see (10), to follow) which, roughly speaking, states that after a sufficiently long time, the expected size of the system state is small in comparison to the size of the initial condition as the former gets large. In the literature, this criterion is usually checked by proving stability of the corresponding fluid model, as was originally suggested by Dai [9]. Here, we choose an alternative way, proving Dai’s condition (10) directly for the underlying queueing system, without using fluid model analysis as an intermediate step. Our argument is based on two crucial ingredients. The first one, presented in Sect. 5, is an investigation of some general properties of the workload process in linear resource sharing networks. This part of the analysis requires only a very mild assumption on the service protocol, and hence it is applicable to a broad range of disciplines as long as the network is linear. The main result of this section states that in the strictly subcritical case, after a time proportional to the size of the initial condition, the workload on all the “local routes” of the network, requiring only a single resource, is small. The question is whether or not the workload on the “long route”, requiring the cooperation of all the system resources, is also small at the same time. In the case of the preemptive EDF protocol, the answer is affirmative, thanks to a current lead time estimate presented in Sect. 4, stating that the smallest of the lead times of flows on the “long route” is close to the smallest of the lead times of flows on the “local routes”. This excludes the possibility of congestion on the “long route” without at least one of the “local” ones being congested as well. While such an estimate cannot be expected to hold for disciplines other than EDF, we hope that the main idea of our approach will turn out to be useful also for asymptotic analysis of linear resource sharing networks with other service protocols.

To make the above analysis rigorous, it is necessary to overcome several difficulties. First, in order to model an EDF queueing system, the lead times of individual flows or some equivalent information must be stored. In the preemptive case, considered in this paper, the number of partially transmitted flows is unbounded and their residual service times must be stored as well. This calls for modeling the network evolution in an infinite-dimensional state space. Since the original analysis of Dai [9] was constrained to head-of-the-line (HL) disciplines (i.e., such that at any time at most one customer in each class has been partially served), one must proceed carefully, adjusting Dai’s [9] approach to preemptive EDF networks which do not enjoy the HL property. Furthermore, in the stability analysis for our system, different (infinite-dimensional) initial states have to be considered. Some of them are statistically “atypical” in various ways, for example they may have very “irregular” structure of initial lead times, or some service times “abnormally” large. Consequently, any statistical regularity in the system’s behavior may, in general, be observed only after all the initial flows leave the network. Finally, the partially served flows are difficult to analyze, so it is necessary to show that, in some sense, their influence on the system’s asymptotics is negligible. We accomplish the latter task in Sect. 6, showing a suitable state space collapse result which is, in a sense, a counterpart of “crushing lemmas” used in the heavy traffic analysis of “conventional” EDF queueing systems (see, for example, [15]).

There is a connection between our results and stability theory for switched networks. In contrast to the systems discussed above, generalized switches are packet level models in which time is discrete and processing a task takes exactly one time unit. This considerably simplifies the analysis, since the current state of a switch is fully characterized by the finite dimensional vector of queue lengths, any scheduling policy for it is HL and there are no partially transmitted packets there. A natural service discipline for a generalized switch is the Longest Queue First (LQF) algorithm, selecting the set of served links iteratively, in a way somewhat similar to EDF and SRPT, but according to the queue lengths rather than lead times or residual service times. In a seminal paper, Dimakis and Walrand [13] showed stability for a class of LQF systems satisfying the local pooling condition (which is true for linear networks) and, under mild assumptions on stochastic arrivals, also for some more general network topologies, for which a suitable rank condition holds. The main ideas of their analysis were to use the maximal queue length as a Lyapunov function for the underlying Markov chain and to combine diffusion-scale properties of the sample paths with the fluid limit framework. Accordingly, their proof techniques are notably different from the ones used in this paper, in which the dynamics of the underlying Markov process are more complicated, even for relatively simple network topologies. The network graphs satisfying local pooling under primary interference constraints were characterized by Birand et al. [6].

Stability theory for resource sharing networks is clearly related to stability problems for “conventional” multiserver, multiclass queueing networks. The fundamental difference between these two types of systems is that flows in a bandwidth sharing network need access to all the resources on their routes simultaneously, while customers of a multiclass queueing network visit different servers along their routes in succession. However, there are also some important similarities. The results from the theory of multiclass queueing networks which are of greatest relevance to this paper, in addition to [9], are the works by Bramson [8] and Kruk [24]. The former shows stability of general strictly subcritical multiclass EDF networks without preemption, while the latter contains the corresponding result for preemptive, strictly subcritical EDF networks with fixed customer routes. In both those papers, convergence of the fluid-scaled sample paths of the network performance processes to fluid limits, satisfying the corresponding fluid model equations, together with stability of the resulting fluid model, were used to prove stability of the stochastic EDF networks under consideration. The results of [24] may be generalized to strictly subcritical, preemptive EDF networks with Markovian routing, although such a generalization seems to be nontrivial. This paper is devoted to preemptive EDF resource sharing systems, so our analysis is more akin to the one presented in [24]. In particular, our proof of state space collapse from Sect. 6 resembles the proof of the corresponding result from [24].

Finally, let us mention a growing body of literature devoted to scaling limits for “conventional” EDF networks. The case of a single-server, single customer class queue is relatively well understood by now. Fluid limits for such systems with hard deadlines and no preemption, under various distributional assumptions, were investigated by Decreusefond and Moyal [12], Atar, Biswas and Kaspi [1], and, recently, Atar, Biswas, Kaspi and Ramanan [3]. Heavy traffic limits for preemptive EDF queues with soft deadlines were provided by Doytchinov, Lehoczky and Shreve [15], and the corresponding analysis for EDF queues with reneging was given by Kruk, Lehoczky, Shreve and Ramanan [31]. The accuracy of the heavy traffic approximation from [15] was investigated by Kruk, Lehoczky and Shreve [27, 28]. There are also a few results concerning multistation EDF systems. Atar, Biswas and Kaspi [2] developed fluid limits for a many-server EDF queue. The heavy traffic analysis of [15] was extended to multiclass feedforward EDF networks by Yeung and Lehoczky [42], and to some acyclic EDF networks by Kruk, Lehoczky, Shreve and Yeung [29]. Developing a fully satisfactory heavy traffic theory for general multiclass, multiserver EDF queueing networks appears to be mathematically challenging, since, as was pointed out by Kruk [25], such networks typically exhibit unconventional heavy traffic behavior. Counterparts of the above-mentioned results for resource sharing EDF networks are still to be developed.

This paper is organized as follows. In Sect. 2 we define a stochastic model for a linear EDF resource sharing network. Section 3 contains our main result and the rest of the paper is devoted to its proof. In Sect. 4 we provide essential current lead time estimates. Section 5 is devoted to investigation of the workload dynamics in linear resource sharing networks. In Sect. 6, we estimate the time of transmission completion for all the initial flows and we show that after this time state space collapse holds. Section 7 contains the proof of the main result. Section 8 concludes.

Our stochastic model of a linear EDF resource sharing network consists of the following: the network topology, stochastic primitives, the service protocol and performance processes describing the time evolution of the system. These are defined below.

In this section, after the definition of a suitable Markov process describing the evolution of an EDF resource sharing network, we state our main result, Theorem 1, and provide a sketch of its proof. The details of the proof will be presented in Sects. 4–7.

The aim of this section is to prove Proposition 3, stating that after all the initial flows are fully transmitted in a linear EDF resource sharing network, the current lead time on route \(J+1\) is close to the minimum of the current lead times on routes \(1,\ldots ,J\). This excludes the possibility of having a large workload on route \(J+1\), while all other routes are almost empty, and therefore it provides a key ingredient of our stability argument. The proof of Proposition 3, given in Sect. 4.2, is somewhat involved. Therefore, to aid the reader, in Sect. 4.1 we show a corresponding result for a linear FISFO network. The proof for the latter case uses the same ideas as the general one from Sect. 4.2, while being notably simpler. The arguments presented in this section are pathwise, requiring no distributional assumptions on the model stochastic primitives.

Throughout this section, we use the notation introduced in Sect. 2.5.

In this section, we investigate properties of the workload process in linear resource sharing networks. The results presented here do not depend on the service protocol, and hence, they are fairly general. We do assume, however, the following weak form of non-idleness: for any \(t\ge 0\) and any route \(i=1,\ldots ,J\), if \(Q_i(t)>0\), then the sum of the transmission rates on the routes i and \(J+1\) at time t equals 1. (Recall that we have assumed the unit maximal service rate for every resource.) This “weak non-idleness” assumption, mathematically expressed by Eqs. (52)–(54), is clearly satisfied by the EDF service protocol described in Sect. 2.5, but it also holds for any other “reasonable” policy in a linear network.

The main results of this section are Lemmas 13 and 14. Lemma 13 shows that there exists a route \(\hat{i} \in \{1,\ldots ,J\}\) such that, after a time proportional to the “norm” of the initial condition, the workload on this route asymptotically dominates the workloads on other routes belonging to the set \(\{1,\ldots ,J\}\). Lemma 14 provides an upper bound for the time at which a route chosen from \(\{1,\ldots ,J\}\) becomes empty in a strictly subcritical network. Along the way, we establish a simple comparison result for the Skorokhod map on \(\mathbb {R}_+\) (Lemma 11).

We first introduce some auxiliary performance processes. The cumulative transmission time on route \(i\in \mathbf{I}\) by time t will be denoted by \(T_i(t)\). Note that \(T_i(t)=\int _0^t r_i(s) ds\), where \(r_i(s)\) is the transmission rate on route i at time s. Then the available bandwidth for routes \(i\in \{1,\ldots ,J\}\) is defined asThe netput for each route \(i\in \{1,\ldots ,J\}\) is given byThis is the total time necessary to complete the transmission of all the flows which are present on this route at time t if it has never been empty prior to time t. Because route i might have been empty, the actual time necessary to complete the transmission of all the flows which are present on route \(i\in \{1,\ldots ,J\}\) at time t equalswhereis the Skorokhod map on \([0,\infty )\). It is well-known (see, for example, [30], Definition 1.1) that, for a given \(\psi \in \mathbf {D}[0,\infty )\), the functionssatisfy

1. \(\phi (t)=\psi (t)+\eta (t) \ge 0\) for every \(t\ge 0\),

2. \(\eta \) is nondecreasing on \([0,\infty )\), \(\eta (0)\ge 0\) and \(\int _0^\infty \mathbb {I}_{[\phi (s)>0]} d\eta (s)=0\), where, by convention, \(\eta (0-)=0\).

Moreover, the pair \((\phi ,\eta )\) given by (55) is the only element of \(\mathbf {D}[0,\infty )\times \mathbf {D}[0,\infty )\) enjoying the above two properties. In what follows, the pair \((\phi , \eta )\) defined by (55) is said to solve the Skorokhod problem on \([0,\infty )\) for \(\psi \).

Let G be the set of elementary events \(\omega \in \varOmega \) for which By the strong law of large numbers, \(\mathbf {P}(G)=1\).

To proceed further, let \(x^n\in S\) be a sequence of initial states, with the corresponding initial workloads (total transmission times) \(w^n = (w^n_i)_{i\in \mathbf{I}}\) and residual interarrival times \(r^n = (r^n_i)_{i\in \mathbf{I}}\), such thatfor some \(\overline{r}=(\overline{r}_i)_{i\in \mathbf{I}}\in [0,1]^I\), \( \overline{w}=(\overline{w}_i)_{i\in \mathbf{I}}\in [0,1]^I\). By (58) and (61), on G uniformly on compacts (u.o.c.) in t (see Lemma 4.2 in [9]). Also, by (59) and the functional strong law of large numbers, for every \(i\in \mathbf{I}\), we have the convergenceu.o.c. in \(t\ge 0\) on the set G.

The following simple lemma shows that both the initial lead times of the incoming flows and their interarrival times become negligible under fluid scaling.

The proof of the first statement of this lemma is the same as the proof of Lemma 4.1 in [24]. The proof of the second one follows by a similar argument.

For \(i\in \mathbf{I}\) and \(t\ge 0\), we defineBy (61)–(63), for each i, on the set G,u.o.c. in \(t\ge 0\), or, equivalently,u.o.c. in \(t\ge 0\). Next, for \(t\ge 0\), define By (65)–(66), (68)–(70) and Lipschitz continuity of \(\varGamma _0\) with respect to the supremum norm (see, for example, [41], Lemma 13.5.1), for \(i=1,\ldots ,J\), we havewhere and the latter convergence is u.o.c. in \(t\ge 0\) on the set G.

In this section, we provide an upper bound for the time of transmission completion of all the initial flows (Lemma 15). We also show that after this time, the workload on any route is approximately equal to a fixed multiple of the corresponding queue length, thus establishing state space collapse (Proposition 4).

Recall the set G from Sect. 5 (see, in particular, (58)–(60)) and the random variable \(\mathfrak {T}\) defined by (29)–(31).

The following proposition, which may be of independent interest, is an analog of Proposition 6.1 in [24]. The main ideas of the proofs of these two results are also similar.

This follows immediately from the estimates (96).

Consider a linear, strictly subcritical, preemptive EDF resource sharing network, with stochastic primitives satisfying (1)–(5). Letwithwhere \(\tau _0\), \(\tau _1\) are as in (80) and (89), respectively. We will show that (10) holds and thus, by Proposition 1, the network is stable. If (10) is false, there exist \(\epsilon >0\) and a sequence \(x^n\in S\) with \(|x^n|\rightarrow \infty \) such thatWithout loss of generality (extracting a subsequence if necessary), we can assume that the sequence \(x^n\) satisfies (61).

Recall the set G from Sect. 5. We will show that on G, (11) holds.

Arguing as in the proof of Lemma 4.3a in [9], one can show thatLet \(L_+(t)\) denote the positive part of the greatest lead time of a flow in the system at time t. By (99), we have \(\gamma >1\), so the lead times at time \( \gamma |x^n|\) of initial flows in the system starting from state \(x^n\) are negative. This, together with Lemma 12, implies thatBy (86), (99)–(100) and the fact that \(\overline{w}_i\le 1\) for all \(i\in \mathbf{I}\), we haveUsing Proposition 4 with \(T= \gamma \), together with the relations (102)–(103), we reduce the proof of (11) to showing the convergence (12) on the set G.

If (12) is false, there exist \(\omega \in G\), \(\eta \in (0,1)\) and a subsequence of the sequence \(x^n\) (still denoted by \(x^n\) for convenience) such that for every n By (61), (66), (76) and Lemma 12 with \(T=\gamma \), there exists \(n_1(\omega )\) such that, for all \(n\ge n_1(\omega )\), By Lemma 15, there exists \(n_2(\omega )\) such that, for all \(n\ge n_2(\omega )\), (90) holds. This, together with Proposition 3, (100) and (108)–(109), implies that, for \(n\ge n_1(\omega ) \vee n_2(\omega )\) and \(t\in [C|x^n|,\gamma |x^n|]\),Using Lemma 14 with C given by (100), for \(i=1,\ldots ,J\), we find \(n_0(i,\omega )\) such that (87) holds for all \(n\ge n_0(i,\omega )\), with \(\delta =\delta (\overline{w})\) given by (86). Fix \(n\ge n_1(\omega ) \vee n_2(\omega ) \vee \max _{i=1,\ldots ,J} n_0(i,\omega )\) and let \(\hat{i}=\hat{i}^n(\omega ) \in \tilde{\mathbf{I}}^n_{\max }(\omega )\) be as in Lemma 13. By (104) and Lemma 14, with C given by (100), we have \( \sigma ^n_{\hat{i}}(\omega ) <\gamma \). The definition of \(\sigma ^n_{\hat{i}}\) implies that \(\overline{W}^n_{\hat{i}}(\sigma ^n_{\hat{i}} ) =0\). LetWe have just shown that the set on the right-hand side of (111) is nonempty, so \(\hat{\sigma }\) is well-defined. Moreover, (111) implies \(\overline{W}^n_{\hat{i}}(\hat{\sigma }-)=0\). Thus, by (76) and (107),By (79) and (100), \(\tau (\overline{w}) \le \tau _0 \le C-1\), where \(\tau (\overline{w})\) is given by (77), so Lemma 13 implies thatBy definition, \(\hat{\sigma } \ge C\), so the relations (112)–(113) implyUsing (76), (107) and (114), we arrive at the estimateHowever, for \(i\in \mathbf{I}\),so (109) and (115) implyBy Corollary 1 with \(T=\gamma \) we see that (100), (106), (108), (111) and (116) imply(Here and below, \(a^n_i(\hat{\sigma })\) denotes \(a^n_i(\hat{\sigma })(\omega )=a^n_i(\hat{\sigma }^n(\omega ))(\omega )\)). The right-hand side of (117) is less than 1 and \(\hat{\sigma } \ge C \ge 4\), where the last inequality follows from (89), (100). Hence, (95) (with \(T=\gamma \)), (117) and the inequality \(\overline{r}_i\le 1\) imply thatOur next goal is to estimate \(C^{x^n}_i(\hat{\sigma }|x^n|)\) from below for \(i=1,\ldots ,J\). We consider two cases. If \(Q^{x^n}_i(\hat{\sigma }|x^n|)=0\), then, by (8) and (64) (with \(T=\gamma \)),If \(Q^{x^n}_i(\hat{\sigma }|x^n|)>0\), then, recalling from the proof of Proposition 4 that each flow that arrived at route i before \(a^n_i(\hat{\sigma })-\mathcal {L}_n\) has already been fully transmitted by time \(\hat{\sigma }|x^n|\), and using nonnegativity of initial lead times for arriving customers, we getBy (119)–(120), with the help of (108)–(109) and (118), we obtainThis, together with (110), shows thatLet k be a flow on route \(J+1\) at time \(\hat{\sigma }|x^n|\) in the system starting from the state \(x^n\). By (90) and (100), the are no initial customers at time \(\hat{\sigma }|x^n|\) if the elementary event \(\omega \) occurs and henceThus, by (64), (108) and (122), for any such flow k,The latter bound, together with (65)–(66) and (106), implies thatAdding the bounds (116) and (123), we getIf \(\gamma =\hat{\sigma }\), then (124) immediately implieswhich contradicts (105).

Assume that \(\gamma >\hat{\sigma }\). By (111), we have \(\overline{W}^n_{\hat{i}}(t)(\omega )>0\) for all \(t\in (\hat{\sigma },\gamma ]\). Consequently the resource \(\hat{i}\) transmits with unit rate on the time interval \((\hat{\sigma }|x^n|,\gamma |x^n|]\) if the elementary event \(\omega \) occurs, and henceThis, in turn, together with (65)–(66), (106), (116) and (123), impliesFor \(i\in \{1,\ldots ,J\}\), \(i\ne \hat{i}\), by (76), (113), (107) and (126), we getFinally, the estimates (126)–(127) yieldwhich contradicts (105). We have proved (12), and hence (11).

Armed with (11), arguing similarly as in the last paragraph of the proof of Theorem 3.1 in [24], we getwhich contradicts (101). \(\square \)

In this paper, we have shown stability of linear, strictly subcritical resource sharing networks under the preemptive EDF service protocol. The main idea of the proof was to verify Dai’s condition (10) on the growth of the expected “norm” of the performance process as the initial condition gets large. To this end, we used a direct argument, based on the current lead time estimate from Sect. 4 and properties of the workload process in linear resource sharing networks established in Sect. 5. Our approach does not require fluid model analysis, for which the above-mentioned Dai’s criterion was originally introduced. This seems to indicate that in some situations it might be simpler to establish (10) by a direct analysis of the original queueing system, instead of showing convergence to an appropriate fluid model and investigating its asymptotic properties. The above strategy has already been applied in [24], yielding a concise stability proof for a fairly general family of multiclass queueing networks with reneging. The analysis of this paper illustrates the applicability of this approach in a more complicated setting of EDF resource sharing networks.

Our results are readily applicable to the following regularization (in our context, stabilization) of the SRPT service protocol, based on an idea of Bender, Chakrabarti and Muthukrishnan [5]. For \(i \in \mathbf{I}\), letwhere C is a large positive constant.¹ It is intuitively clear that, for large C, the EDF service discipline in a network satisfying (128) assigns priorities to flows in a way similar to SRPT, at least as long as the waiting times of these flows are not too large. On the other hand, our Theorem 1 implies that every preemptive, linear, strictly subcritical EDF resource sharing network satisfying (1)–(4), (128) is stable. In contrast, some of these networks are known to be unstable under the SRPT protocol [40]. This indicates that exchanging SRPT for its EDF proxy with lead times (128) has a strong long-term smoothing effect on the transmission times of large flows, alleviating their “unfair” discriminatory treatment by SRPT and ultimately resulting in network stability. More general size-based (or rather size-related) scheduling disciplines may be constructed by replacing (128) withwhere \(f_i: \mathbb {R}\rightarrow \mathbb {R}_+\), \(i\in \mathbf{I}\), are given deterministic Borel functions. Theorem 1 assures stability of the corresponding preemptive, linear, strictly subcritical EDF resource sharing networks subject to (1)–(4), (129), provided that \(\mathbf {E}f_i(v_{i,1}) < \infty \) for \(i\in \mathbf{I}\). Note that if the functions \(f_i\) in (129) are decreasing, EDF gives preferential treatment to larger flows, thus potentially increasing the corresponding queue lengths.

The analysis of this paper sheds some light on the stability issue of more general strictly subcritical linear resource sharing networks, working under protocols satisfying the mild “weak non-idleness” assumption of Sect. 5. Recall that, by Lemmas 13, 14 and Remark 2, for each such network with initial state \(x^n\), there is a random time \(\hat{\sigma }\), bounded by a constant \(\gamma \), such that (14) holds. If (14) implies (15), then the argument given in Sect. 7 shows thatFor many service disciplines, it is possible to show state space collapse, analogous to the one given by our Proposition 4. In the case of such protocols, (130) implies \(|Q^{x^n}(\gamma |x^n|)|=o(|x^n|)\), and consequently (11), which in turn, by a variant of Theorem 3.1 in [9], ensures that the system is stable. Therefore, the validity of the implication (14) \(\Rightarrow \) (15) is, in many cases, sufficient for network stability. It is plausible that the latter implication may be proved for some service disciplines other than EDF. A trivial example is a protocol under which flows on the long route \(J+1\) have priority over flows on other routes. We believe that a number of interesting applications of the above methodology, in addition to the EDF case investigated in this paper, may be given. This should be a subject of future research.

Another natural future research direction is the development of fluid and heavy traffic approximations of critically loaded linear EDF resource sharing networks. We believe that the estimate (51) will play a key role in this analysis.

Finally, it is desirable to show stability for a sufficiently rich class of more general (not necessarily linear) EDF networks with resource sharing. This clearly requires new tools and ideas, which are beyond the scope of this paper. Note that for a resource sharing queueing system with general topology, the maximal potential stability region must be defined in terms of the so-called network utilization rather than the “bottleneck utilization” \(\max _{j\in \mathbf{J}} \rho _j\). Indeed, as was discussed in detail by Gurvich and Van Mieghem [19, 20], such systems typically exhibit unavoidable bottleneck idleness. (Compare also Definition 2.1 of the stability region in [6] and the notion of a feasible arrival rate vector in [13].) We hope that a suitable counterpart of the inequality (51) holds for some more general networks, for example those satisfying the local pooling condition, and that it will turn out to be a key ingredient of the proof of the corresponding extension of Theorem 1.

It is likely that some EDF resource sharing networks which do not satisfy the local pooling condition are unstable. In this context, let us consider an example, provided by Dimakis and Walrand [13], of a strictly subcritical six-cycle packet level model with a deterministic arrival of a single packet to each queue in every time slot, which is unstable under LQF with the “unbiased” random tie-breaking rule. If the initial queue lengths are all equal, LQF for this particular system coincides with FISFO, so the corresponding FISFO (and hence EDF) system is also unstable. However, it is easy to see that if the tie-breaking rule for this network is changed so that a “big match” (i.e., a triple of queues) is always selected for simultaneous service if possible, then the system is actually stable as long as it is strictly subcritical. Hence, the above-mentioned network instability is due to a suboptimal choice of the tie-breaking rule rather than the service protocol. Nevertheless, it is plausible that an example of an EDF resource sharing network which is unstable under any tie-breaking rule may be constructed along this line (perhaps by replacing the six-cycle by a larger cyclic graph). Interestingly, Dimakis and Walrand [13] have observed that if there is any randomness in the packet arrivals, then the six-cycle system is actually stable, even with the “unbiased” random tie-breaking rule, as long as it is strictly subcritical. However, in the presence of any randomness, either in the arrivals (implied, for example, by each of our conditions (2)–(3)), or in the transmission times, LQF no longer coincides with FISFO (EDF), so the relation between their stability regions is not clear. These issues should be subject to future research.