We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In queueing theory it is commonly assumed that the customer arrival process is a Poisson process. Some recent empirical studies (see, for example, [4] for references) suggest, however, that arrival processes may exhibit overdispersion, i.e., the variance of the number of arrivals in an interval is larger than the corresponding mean. This has triggered research on queueing systems with overdispersed input.
The focus of the present paper is on infinite-server queues with, as input process, a doubly stochastic process, also known as a Cox process. Such a process can be seen as a Poisson process in which the rate is not a constant; instead, the rate process \(\{\Lambda (t), t \in {{\mathbb {R}}}\}\) itself is a (nonnegative) stochastic process. As an immediate consequence of the law of total variance, Cox processes indeed are overdispersed. Before describing the main contributions of the present paper, we first provide a brief account of the existing literature in this area.
Advertisement
Literature In [7], the arrival process of the infinite-server queues is a Cox process in which the arrival rate is a shot-noise process. More specifically, the jumps of the shot-noise process occur according to a homogeneous Poisson process and are i.i.d. (independent and identically distributed) with a general distribution, and between jumps, the shot-noise process decays exponentially fast. The main object of study in [7] is a feedforward network of infinite-server queues, and the main result is the joint transform of the shot-noise-driven arrival rates and the numbers of customers in the queues.
Infinite-server queues are also studied in [2] and [8], but the arrival process there is a Hawkes process, the so-called self-exciting process—jumps in the shot-noise process in turn increase the intensity of the occurrence of the jumps. Daw and Pender [2] present several interesting motivating examples. They consider deterministic jump sizes in the shot-noise process and study in particular the Hawkes/Ph/\(\infty \) and Hawkes/D/\(\infty \) queues, obtaining detailed expressions for moments and autocovariances. Koops et al. [8] allow generally distributed jump sizes. For the case of exponentially distributed service times, the joint Laplace and z-transform of the Hawkes intensity and the number of customers is characterized via a partial differential equation, and that PDE is exploited to obtain recursive expressions for (joint) moments of the Hawkes intensity and the number of customers. For the case of generally distributed service times, the Hawkes process is viewed as a branching process, which allows expressing the z-transform of the number of customers in terms of the solution of a fixed-point equation.
Main goals and results In this paper we aim to develop a general framework for the study of infinite-server queues with, as input, a quite general Cox process and to provide an exact analysis of networks of such queues. The modeling framework of [7] is extended in several ways; in particular, the shot-noise process is multivariate and not driven by a compound Poisson process, but by a Lévy subordinator. The class of Lévy subordinators not only contains compound Poisson processes, but also, for example, linear drifts and Gamma processes (where the latter process has the notable property that it exhibits infinitely many jumps in any time interval of positive length).
The main results of the paper are compact, elegant, transform expressions for joint distributions of arrival rates and numbers of customers, and properties of the departure processes, which reveal an interesting generalization of the classical results for the number-of-customers process and the departure process in the M/G/\(\infty \) queue. While large parts of the paper are quite technical, we also try to make clear why a detailed analysis of this complicated network is possible. In a nutshell, crucial for the analysis are the following convenient properties: (i) Lévy processes have stationary and independent increments, (ii) in a shot-noise process with exponential decay, all shots simultaneously decay at the same exponential rate, independently of each other, and (iii) in (a network of) infinite-server queues, all customers move through the queues independently, without interfering with each other.
Advertisement
Motivation Our motivation for this study is threefold. (i) We started studying queues with Coxian input as a framework naturally allowing the incorporation of overdispersion. (ii) When we realized that a detailed analysis of an isolated infinite-server queue with Coxian input is possible, we were motivated to develop a very general framework for studying networks of infinite-server queues with a multivariate Coxian input process that is of great generality but still allows a detailed exact analysis. Together with product-form networks and linear stochastic fluid networks (cf. [6]) these are some of the rare examples of queueing networks for which one can obtain the joint distribution of key performance measures. (iii) Finally, while infinite-server queues with overdispersed input have various applications, we were in particular inspired by Web server applications. Consider the number of simultaneous visitors to a popular Web site or online video [11, 12]. While the arrival process of visitors to the Web site may well be a Poisson process, its rate may jump up due to some (external) event, then decay gradually, only to jump up again because of another event. Such an example formed one of the motivations for [2, 7, 8], which all study infinite-server queues with an overdispersed arrival process.
Cox input processes driven by a multivariate Lévy subordinator are quite relevant for the above-mentioned example of a Web site with a visit rate that jumps up because of a certain event and subsequently decays again. They allow one to take into account multiple, possibly related, events that affect the visit rate of the Web site. Those events could occur instantaneously (the Lévy subordinator being a compound Poisson process), but there might also, for example, be a linear (fluid) component.
Since we also consider networks of infinite-server queues, we can also model the situation in which a visitor to a Web site, after a while, clicks in order to move to another Web site.
Organization of the paper In Sect. 2 we introduce the multivariate shot-noise process and we describe distributional properties of this process. Section 3 studies a single infinite-server queue with, as input process, the above-described Cox process. The general case of a network of infinite-server queues is dealt with in Sect. 4. Each of these three sections starts with a brief overview of related known results: the one-dimensional shot-noise process (Sect. 2.1), the classical M/G/\(\infty \) queue (Sect. 3.1), and a tandem network of M/G/\(\infty \) queues (Sect. 4.1). Section 5 contains some conclusions and suggestions for further research.
2 Multivariate shot-noise
In this preliminary section, we first briefly introduce shot-noise (Sect. 2.1) and define multivariate shot-noise and its stationary version (Sect. 2.2), then we recall some basic facts on Poisson random measures (Sect. 2.3), and we conclude in Sect. 2.4 with describing distributional properties of the multivariate shot-noise process.
2.1 Shot-noise processes
We start our exposition by describing the classical shot-noise process \(\{X(t), t \ge 0 \}\), as follows: This process increases according to a compound Poisson process \(\{J(t), t \ge 0\}\) with jump rate c of the Poisson jump process \(\{N(t), t \ge 0\}\) and independent, identically distributed upward jumps \(B_1,B_2,\dots \) with Laplace–Stieltjes transform \(\beta (\cdot )\); see Fig. 1.
Fig. 1
The rate X(t) as a function of time t
×
In between jumps, the process decreases with a state-dependent rate rX(t). Possible representations are hence, with \(T_1,T_2,\dots \) denoting the jump epochs of the compound Poisson process,
alternatively, \(X(\cdot )\) is the unique solution of the stochastic integral equation
$$\begin{aligned} X(t) = X(0) + \sum _{j=1}^{N(t)} B_j - r \int _0^t X(s) \mathrm{d}s, ~~~~ t \ge 0. \end{aligned}$$
(2)
2.2 Definition of multivariate shot-noise
After having defined the classical shot-noise process, we now describe the generalized version of the shot-noise process that we work with in this paper.
Let \({{\varvec{X}}}(\cdot )\) be a (generalized) d-dimensional multivariate shot-noise process, which is defined as follows: Let \({\varvec{J}}(\cdot )\) be a d-dimensional subordinator, i.e., a d-dimensional Lévy process which is non-decreasing in all components. Examples of such non-decreasing Lévy processes include linear drifts, compound Poisson processes and Gamma processes (but, obviously, not Brownian motion). We define the exponent of \({\varvec{J}}(\cdot )\) by \(-\eta (\cdot )\); it satisfies, for \({\varvec{\alpha }}\in \mathbb {R}_+^d\) and with \('\) denoting transposition,
Also, let \(Q=(q_{ij})\) be a \((d\times d)\)-matrix with nonnegative diagonal and non-positive off-diagonal entries, and with all eigenvalues having strictly positive real parts. An example of such a matrix is \(Q=(I-P')D\), where D is a positive diagonal matrix and P is a substochastic matrix satisfying \(P^n\rightarrow 0\) as \(n\rightarrow \infty \). A detailed motivation for studying this setting is provided in [6, Section 4].
We now introduce, for \({\varvec{X}}(0)\) componentwise strictly positive and independent of \({\varvec{J}}(\cdot )\), the multivariate shot-noise process through
The cumulative external input to station i is \(X_i(0)+J_i(t)\), the internal input rate from station i to station j is \(\sum _{j\ne i}q_{ij}X_j(t)\), and the output rate (some of which goes to other stations, while the rest leaves the system) is \(q_iX_i(t)\), where \(q_i=-q_{ii}\ge 0\). The reason for the above assumption that the eigenvalues of Q have a strictly positive real part is that it ensures that all the coordinates of the matrix \(e^{-Qt}\) vanish as \(t\rightarrow \infty \) and thus, from (3), it follows that the effect of each arriving particle vanishes as well.
The process \({\varvec{X}}(\cdot )\) is Markovian and strictly positive (i.e., never hits or crosses any of the axes). Moreover, it has a unique stationary/ergodic/limiting distribution. This limiting distribution is identical to that of
So far we have considered \({\varvec{J}}(t)\) for positive values of t, but we can extend \({\varvec{J}}(\cdot )\) to the whole real line (with \({\varvec{J}}(0)={\varvec{0}}\)). It follows directly that
is a stationary process satisfying the same conditions that \({\varvec{X}}\) does, that is, relations (3) and (4). From here on we assume that \({\varvec{X}}={\varvec{X}}^*\).
In Sect. 3 we shall consider an infinite-server queue with as arrival process a non-homogeneous Poisson process with arrival rate function \(\Lambda (t) = {\varvec{a}}'{\varvec{X}}(t)\) at time t. But first, in the next subsection, we review some well-known properties and results for Poisson random measures. We need those properties and results in order to provide an elegant treatment of the transforms of the arrival process and numbers of customers in networks of infinite-server queues with Coxian arrivals. In Sect. 2.4 we already demonstrate that by deriving an expression for the d-dimensional Laplace–Stieltjes transform (LST) of \(\mathbf{X}\).
2.3 Properties of Poisson random measures
Readers who are not familiar with Poisson random measures are referred to, for example, Chapter 6 of Çinlar [1]. To proceed, we first recall that a Poisson random measure N on some measurable space \(({\mathbb {X}},{\mathscr {G}})\) is a random measure having the property that, for every pairwise disjoint \(A_1,\ldots ,A_n\in {{\mathscr {G}}}\), the random variables \(N(A_1),\ldots ,N(A_n)\) are independent with \(N(A_i)\sim \text {Poisson}(\mu (A_i))\), where \(\mu (A)={{\mathbb {E}}}N(A)\) is assumed to be \(\sigma \)-finite. When \(\mu (A)\) is 0 or \(\infty \) then N(A) is defined to be almost surely 0 or \(\infty \), respectively. We note that it is well known that N is a Poisson random measure with a (\(\sigma \)-finite) mean measure \(\mu \) if and only if for any \({{\mathscr {G}}}\)-measurable \(f:\mathbb {X}\rightarrow \mathbb {R}_+\) we have that (cf. [1, Thm. 2.9 on p. 252]),
Observe that \({{\mathbb {E}}}\int f(s)\,N(\mathrm{d}s)=\int f(s)\, \mathrm{d}\mu (s)\) (which holds even if N is not Poisson). Finally, it is also known, and actually easy to check (first for indicators, then simple functions, etc.), that if \(f_1(\cdot )\) and \(f_2(\cdot )\) are nonnegative \({{\mathscr {G}}}\)-measurable, then
Clearly, when \(\int f_1(s)\mathrm{d}\mu (s),\,\int f_2(s)\mathrm{d}\mu (s)\), and \(\int f_1(s)f_2(s)\mathrm{d}\mu (s)\) are all finite, then this is equivalent to
Let \({\varvec{\varrho }}=(\varrho _i)\) be the mean rate of growth of the subordinator \({\varvec{J}}(\cdot )\), that is, \(\varrho _i:=c_i+\int _{\mathbb {R}_+^d}x_i\nu (\mathrm{d}{\varvec{x}})\). We can also write \(\varrho _i=c_i+\int _{\mathbb {R}_+}x_i\nu _i(\mathrm{d}x_i)\), using the notation
It is also well known (see, for example, Chapter 4 of [13]) that there exists a Poisson random measure \(N(\cdot ,\cdot )\) on \(\mathbb {R}\times \mathbb {R}_+^{d}\) (equipped with its Borel \(\sigma \)-field) with mean measure \(\ell \otimes \nu \), where \(\ell \) is Lebesgue measure, such that
where \({\varvec{x}}=(x_1,\ldots ,x_d)'\). This property entails that if we take \(f_1(s,{\varvec{x}})=\sum _{i=1}^d g_i(s)x_i\) and \(f_2(s,{\varvec{x}})=\sum _{i=1}^d h_i(s)x_i\), then we can immediately conclude that for each Borel \({\varvec{g}},{\varvec{h}}:\mathbb {R}\rightarrow \mathbb {R}_+^d\) the following three identities hold:
provided that the corresponding variances \(\int _{\mathbb {R}}{\varvec{g}}(s)'\Sigma {\varvec{g}}(s)\mathrm{d}s\) and \(\int _{\mathbb {R}}{\varvec{h}}(s)'\Sigma {\varvec{h}}(s)\mathrm{d}s\) are both finite. With \(\sigma _{ij}\) denoting the (i, j)th coordinate of \(\Sigma \), it also holds that
where \(\nu _{ij}\) is the (i, j)th marginal measure associated with \(\nu \) (i.e., the Lévy measure associated with the (i, j)th coordinate of \({\varvec{J}}(\cdot )\)).
2.4 Distributional properties of multivariate shot-noise
Combining (5) with the powerful identity (8), we immediately obtain the following
Proposition 2.1
The d-dimensional Laplace–Stieltjes transform of \({\varvec{X}}\) is given by
In the usual manner, moments can be found from the LST. The first moment takes the following form: With \({\varvec{\nabla }}\eta ({\varvec{0}})\) the vector of first derivatives,
We now identify the covariance matrix of \({\varvec{X}}\). From (9) it follows, as was also shown in [6, Thm. 5.2], that the covariance matrix of \({\varvec{X}}\) is given by
The next objective is to find an expression for the covariance between \({\varvec{X}}(t)\) and \({\varvec{X}}(t+h)\), again bearing in mind that we started the process at \(-\infty .\) Now, clearly
Denote (for \(h\ge 0\)) by \(\Sigma _h\) a matrix of which the (i, j)th entry is \({{\mathbb {C}}}\mathrm{ov}({X_i(t),X_j(t+h)})\). It now follows from (9) that, by taking \({\varvec{g}}(s):=\mathrm{e}^{-Q'(t-s)}x\) and \({\varvec{h}}(s):=\mathrm{e}^{-Q'(t+h-s)}y\),
In fact, employing the method of proof of [6, Thm. 5.2], \(\Sigma _h\) is the unique solution of this equation.
Remark 2.3
In the one-dimensional case, letting \(\sigma ^2\) and q denote the one-dimensional versions of the matrices \(\Sigma \) and Q, respectively, we conclude that the covariance between X(t) and \(X(t+h)\) is given by \(\frac{1}{2}\mathrm{e}^{-qh}\sigma ^2/q\).
3 Single infinite-server queue with a Cox input process
We consider an infinite-server queue in which, conditioned on \({\varvec{J}}(\cdot )\), the arrival process is a non-homogeneous Poisson process with rate function \(\Lambda (t)={\varvec{a}}'{\varvec{X}}(t)\) at time t, where \({\varvec{a}}\in \mathbb {R}_+^d\). It is throughout assumed that service times are i.i.d. and are independent of \({\varvec{J}}(\cdot )\) (hence also of \({\varvec{X}}(\cdot )\)) and the arrival process. The service times have distribution function \(F(\cdot )\) and complementary distribution function \({\bar{F}}(\cdot )\), and in addition we define \(F(s,t):=F(t)-F(s)\) for \(s<t\).
In this section, we start by reminding the reader of some well-known results concerning the classical M/G/\(\infty \) queue (Sect. 3.1), subsequently we derive, for the infinite-server queue with a Cox input process, the transform of queue lengths at various time epochs jointly with the numbers of arrivals in various time intervals (Sect. 3.2), and we conclude, in Sect. 3.3, with several calculations yielding moments as well as the joint steady-state transform of the number of customers in the infinite-server queue and the arrival rate.
3.1 The M/G/\(\infty \) queue
In this subsection we consider the classical M/G/\(\infty \) queue with fixed arrival rate \(\lambda \) and generic service time B. It is well known [3] that the number of customers L(t) at time t, starting with \(L(0)=0\), is Poisson distributed with mean
This is easily seen by observing that the number of arrivals in [0, t] is Poisson(\(\lambda t\)), that different customers do not interact and that, given that there were n arrivals in [0, t], the arrival epochs were independent and uniformly distributed on [0, t]. So the Poisson arrival process is thinned, and the number of customers still present at t follows a Poisson distribution. Thus, the generating function of L(t) immediately follows:
The pleasing properties of non-interfering customer behavior and of the uniformly distributed arrival epochs also quickly lead to elegant results for joint distributions of customer numbers at various epochs. Another well-known result about the M/G/\(\infty \) queue, going back to Mirasol [10], is that in stationarity the departure process of the queue also is Poisson. We now study the question of how these results change in the setting of the Cox input process.
3.2 Transform of queue lengths and numbers of arrivals
Our first objective is to derive the transform of queue lengths at various points in time, jointly with the number of arrivals in corresponding intervals.
To this end, we consider \(n\in {{\mathbb {N}}}\) time intervals, say \((t_0,t_1]\) up to \((t_{n-1},t_n]\) (where it is assumed that \(t_{i-1}<t_{i}\) for \(i=1,\ldots ,n\)). Our goal is to establish the joint transform of the queue lengths \(L_i\) at each of the \(t_i\) and the numbers of arrivals \(A_i\) in each of the intervals \((t_{i-1},t_i]\), i.e., we shall compute the transform, for \({\varvec{w}}\in {{\mathbb {R}}}^{n+1}\) and \({\varvec{z}}\in {{\mathbb {R}}}^n\),
Notice that a job arriving in the interval \((t_{i-1},t_i]\) contributes to \(A_i\) (and does not contribute to any of the other \(A_j\)) and potentially contributes to \(L_i\) up to \(L_n.\) More precisely, supposing that the job arrives at \(s\in (t_{i-1},t_i]\), with probability \({F}(t_j-s,t_{j+1}-s)\) it contributes to \(L_i\) up to \(L_j\), for \(j\in \{i,\ldots ,n\}\) and defining \(t_{n+1}:=\infty \). Conditional on \(\Lambda (\cdot )=\lambda (\cdot )\) this concerns a Poisson contribution with parameter
$$\begin{aligned} \int _{t_{i-1}}^{t_i} \lambda (s) {F}(t_j-s,t_{j+1}-s)\,\mathrm{d}s; \end{aligned}$$
conditional on \(\Lambda (\cdot )=\lambda (\cdot )\) all these contributions are independent. In addition, we recall that the probability-generating function (evaluated in z) of a Poisson random variable with parameter \(\lambda \) equals \(\exp (\lambda (z-1))\). Combining the above elements, we obtain
Representation (15) generally holds, i.e., for any nonnegative arrival rate process \(\Lambda (\cdot )\). For the case of multivariate shot-noise, however, the expression can be made more explicit. To this end, we substitute (cf. (6))
Interestingly, the above result directly enables us to describe the distribution of the number of departures in all intervals. Let \(D_i\) be the number of departures in \((t_{i-1},t_i]\). Then we would like to evaluate
With \(w_1({\varvec{v}}) := v_1,\)\(w_i({\varvec{v}}):=v_{i+1}/v_i\) for \(i\in \{1,\ldots ,n-1\}\) and \(w_n({\varvec{v}}):= v_n^{-1},\) we thus find the following result.
Let L(t) be the number of customers present at time t. In this subsection we compute (i) the mean and variance of L(0), (ii) the joint transform of \(\Lambda (0)\) and L(0), and (iii) the covariance between L(0) and L(t) for some \(t>0.\) As before, we assume that the process started at \(-\infty \), so that it displays stationary behavior at time 0 (and consequently at t as well). In principle, (factorial) moments can be derived by differentiating \(\Psi ({\varvec{w}},{\varvec{z}})\) suitably often and plugging in \({\varvec{w}}={\varvec{1}}\) and \({\varvec{z}}={\varvec{1}}\), but elegant direct arguments can be given, as we show now.
We first introduce some notation. Define \(\beta \) as the mean service time:
The density of the residual service time \(B_\mathrm{e}\) is given by \(f_\mathrm{e}(s):= {\bar{F}}(s)/\beta .\)
3.4 \(\circ \) Mean and variance of \(\Lambda (0)\) and L(0)
It is easily checked that \({{\mathbb {E}}}\,\Lambda (0)=\lambda := {\varvec{a}}'\,Q^{-1}\,{\varvec{\varrho }}\) and \({{\mathbb {V}}}\mathrm{ar}\,\Lambda (0)={\varvec{a}}'\,\Sigma _0\,{\varvec{a}}\). We therefore now concentrate on the mean and variance of L(0).
Let \({{\mathscr {P}}}(\mu )\) denote a Poisson random variable with parameter \(\mu \). It is straightforward that
Now we move to computing \({{\mathbb {V}}}\mathrm{ar}\,L(0)\). Due to the fact that L(0) is mixed Poisson, we have that \({{\mathbb {V}}}\mathrm{ar}(L(0)\,|\,{\varvec{J}})={{\mathbb {E}}}(L(0)\,|\,{\varvec{J}})\) and thus \({{\mathbb {E}}}\,{{\mathbb {V}}}\mathrm{ar}(L(0)\,|\,{\varvec{J}})={\mathbb E}\,L(0)=\lambda \beta \). Using the law of total variance, (16), (18) and (9),
Expression (19) can be substantially simplified, which we do later in this section. Observe that \({{\mathbb {V}}}\mathrm{ar}\, L(0) \ge {{\mathbb {E}}}\, L(0)\), reflecting the fact that Coxian arrival rates lead to overdispersed arrival processes; see, for example, [4, 7].
3.5 \(\circ \) Joint transform of \(\Lambda (0)\) and L(0)
Here the goal is to determine \({{\mathbb {E}}}\,\mathrm{e}^{-v\Lambda (0)}\,w^{L(0)} .\) By arguments similar to those used in Sect. 3,
It is possible to apply this joint transform to the computation of moments of L(0) and \(\Lambda (0)\), as well as their mixed moments, but lower moments can typically be computed by direct arguments. The mean and variance of \(\Lambda (0)\) and L(0) have been identified above. We therefore now focus on the covariance between \(\Lambda (0)\) and L(0). Since \({{\mathbb {E}}}[\Lambda (0)\,|\,{\varvec{J}}]=\Lambda (0)\) (as \({\varvec{X}}(\cdot )\) is a functional of \({\varvec{J}}(\cdot )\)), and since \(B_{\mathrm{e}}\) is independent of J, we find
where we employ the fact that the covariance matrix between \({\varvec{X}}(t)\) and \({\varvec{X}}(t+h)\), which is the same as that between \({\varvec{X}}(t-h)\) and \({\varvec{X}}(t)\), is given by \(\Sigma _h=\Sigma _0\,\mathrm{e}^{-Q'h}\).
3.6 \(\circ \) Covariance between L(0) and L(t)
The starting point is the law of total covariance:
We evaluate the two terms separately. The first term can be rewritten as follows: Let \(C_1(t)\) denote the number of customers that arrive before time 0 and depart in (0, t]; \(C_2(t)\) is the number of customers that arrive before time 0 and depart after t; finally, \(C_3(t)\) is the number of customers that arrive in (0, t] and depart after t. Evidently, due to the conditional independence of these three quantities,
where the last equality is due to the fact that the conditional distribution of \(C_2(t)\) given \({\varvec{J}}\) is Poisson. Thus, with \(F_\mathrm{e}(\cdot )\) denoting the distribution function of \(B_\mathrm{e}\) and \({\bar{F}}_\mathrm{e}(\cdot )\) the corresponding complementary distribution function,
As \({\varvec{J}}\) has independent increments, when considering the covariance between \({{\mathbb {E}}}[L(0)\,|\,{\varvec{J}}]\) and \({\mathbb E}[L(t)\,|\,{\varvec{J}}]\), we can restrict ourselves to integrating over \(s>0\) only; more concretely,
As it turns out, the last formula (as well as (19)) may be simplified, as follows: Let \(B_{\mathrm{e},1}\) and \(B_{\mathrm{e},2}\) be two i.i.d. copies of \(B_\mathrm{e}\). Recalling (12) and denoting \(x^+:=x\vee 0\) and \(x^-:=-x\wedge 0=(-x)^+\), (20) can be rewritten as
In particular, when \(t=0\), (21) provides us with a simplified expression for \({{\mathbb {V}}}\mathrm{ar}\,L(0)\). The density of \(B_{\mathrm{e},1}-B_{\mathrm{e},2}\) is clearly symmetric around zero and is given by
Since \(f_\mathrm{e}(\cdot )=\beta ^{-1}{\bar{F}}(\cdot )\) is non-increasing on \([0,\infty )\), this implies that \(g(\cdot )\) is unimodal.
We end this subsection by considering the one-dimensional case. Since both \(h(x):=\mathrm{e}^{-q|x|}\) (\(q>0\)) and g(x) are symmetric and unimodal (around zero), it follows by [15] that so is their convolution. Alternatively, this follows also from [5] as \(h(\cdot )\) is also log-concave. This implies that
is unimodal with a mode at zero, hence non-increasing on \([0,\infty )\), and thus so is \(R(\cdot )\). A similar result holds if \({\varvec{a}}\) is an eigenvector associated with a real-valued (positive) eigenvalue q of \(Q'\) since then \({\varvec{a}}'\,\Sigma _0\,\mathrm{e}^{-Q'|x|}\,{\varvec{a}}={\varvec{a}}'\,\Sigma _0\,{\varvec{a}}\, \mathrm{e}^{-q|x|}\). However, in general, even though \({\varvec{a}}'\,\Sigma _0\,\mathrm{e}^{-Q'|x|}\,{\varvec{a}}\) is a symmetric function, it is not clear if it is decreasing on \([0,\infty )\) or if it is log-concave. However, since it vanishes as \(|x|\rightarrow \infty \), it is clear that R(t) vanishes as \(t\rightarrow \infty \).
4 The network case
In this section we consider networks of infinite-server queues with a Cox input process. There are n queues, with the arrival rate of queue k being a non-homogeneous Poisson process with rate function \(\Lambda _k(t)={\varvec{a}}_k'{\varvec{X}}(t)\). This is the same as defining the vector of arrival processes to be \({\varvec{\Lambda }}(t)=A{\varvec{X}}(t)\) for some matrix A with rows \({\varvec{a}}_k'\). The \({\varvec{X}}(t)\) process is the same multivariate shot-noise process as before. Notice that in this construction the arrival processes at the various queues are potentially dependent.
Define by \(p_{km}(t)\) the probability that a job entering at queue k at time 0 is at queue m at time t; likewise, \(p_{k0}(t)\) is the probability that a job entering at queue k at time 0 has left the network by time t. In the case of exponentially distributed service times and probabilistic routing, these \(p_{km}(t)\)’s can be computed more explicitly (relying on the machinery developed for phase-type distributions).
Before studying the joint queue length distribution in the network (Sect. 4.2) and presenting an example (Sect. 4.3), we briefly remind the reader of the structure of the joint queue length distribution in the case of two M/G/\(\infty \) queues in tandem (Sect. 4.1). This helps sharpen our intuition and will make it easier to digest and understand the results of Sect. 4.2.
4.1 Two M/G/\(\infty \) queues in tandem
Consider a model of two M/G/\(\infty \) queues 1, 2 in series, with arrival rate \(\lambda \) at queue 1, generic service time \(B_i\) at queue i, \(i=1,2\), and all customers moving from queue 1 to 2 before leaving the system. Queue 2 has no external arrivals. The same concepts that were underlying the results mentioned in Sect. 3.1 (see, in particular, (14)) quickly lead to the following expression for the generating function of the joint distribution of the two queue lengths \(L_1(t),L_2(t)\):
We focus on analyzing the stationary joint queue length distribution. In principle, virtually all quantities studied in the previous section can be derived again, at the expense of introducing rather heavy notation.
In this section, we let \(K_m\) denote the stationary queue length at node \(m\in \{1,\ldots ,n\}\). Our objective is to compute the joint probability-generating function
Using the same arguments as in the previous section, we conclude that \(K_m\) has a mixed Poisson distribution. More precisely, \(K_m\) has a Poisson distribution with (random) parameter
In this illustrative example we consider a two-node tandem system in which the service times at both nodes are exponential with parameter \(\kappa >0.\) We assume for ease that there is only input at the first queue and that all customers move from the first queue to the second queue. It is immediate that, for \(t\geqslant 0\),
Assume for ease that \(d=1\) (i.e., one-dimensional shot-noise). We choose \(a_1=1\) (whereas \(a_2=0\), as we assumed no external input to the second queue). As a consequence, we have that \(\Lambda _1(t) = X(t)\) and \(\Lambda _2(t) =0\), where X(t) can be represented as
It is easy to obtain moments of \(K_1\) and \(K_2\) from (24) and (25) by differentiation with respect to \(w_1\) and \(w_2\), respectively. In particular, straightforward algebra yields
Similar calculations can be performed for considerably more general networks. Application of Thm. 4.1 requires (i) expressions for the matrix exponential of \(Q'\) and (ii) expressions for \(\pi _k(s\,|\,{\varvec{w}})\) (and therefore for \(p_{km}(s)\)) for \(s\geqslant 0\). To this end, evaluate, using common techniques from linear algebra, the matrix exponential of \(Q'\); this can be done relying on standard computer algebra. Assuming the eigenvalues of Q to have multiplicity 1 (where we note that higher multiplicities can be dealt with too, but require some additional care), we thus obtain a matrix whose entries are weighted sums of exponentials. Likewise, if the service times are of phase type, then the probabilities \(p_{km}(s)\) can be written in terms of (specific entries of) a matrix exponential, and therefore (again under mild conditions) also as a weighted sum of exponentials. It thus follows that the integrand \(\mathrm{e}^{-Q'(s-r)}\,\pi _{{k}}(s\,|\,{\varvec{w}})\) is a mixture of exponentials (in s) and can be integrated by elementary calculus. This allows the computation of the (mixed) moments pertaining to the stationary queue lengths.
We now return to our tandem example. Suppose that \(J(\cdot )\) corresponds to a Gamma process [9, Section 1.2.4] with (without loss of generality) rate and shape parameters both equal to 1, i.e.,
A similar procedure yields the probability-generating function of the second queue, but the resulting expressions are slightly more complicated.
5 Conclusions and suggestions for further research
In this paper we have considered a network of infinite-server queues where the input process is a Cox process that allows much modeling flexibility; the arrival rate is represented as a linear combination of the components of a multivariate generalized shot-noise process. We have derived various distributional properties of the multivariate shot-noise process, subsequently exploiting them to obtain the joint transform of the numbers of customers, at consecutive time epochs, in an infinite-server queue with, as input process, such a Cox process. We have also derived the joint steady-state transform of the vectors of arrival rate and queue length, as well as their means and covariance structure, and we have studied the departure process from the queue. Finally, we extended our analysis to the setting of a network of infinite-server queues, allowing the arrival processes at the various queues to be dependent Cox processes.
In a follow-up study [14] we investigate several related aspects. Specifically, (i) we develop a recursive scheme that allows us to obtain higher-order moments of \((\Lambda (t),L(t))\), (ii) we derive asymptotics of the queue length process, under assumptions regarding the tail behavior of the shot-noise process, (iii) we study the heavy-traffic behavior of the queue length process, and (iv) we obtain several numerical results for means, variances and correlations; this includes a numerical exploration of the sensitivity of various performance metrics with respect to the service time distribution. It could also be investigated to what extent the assumption of exponential decay in the shot-noise process can be relaxed.
Acknowledgements
OK’s work has been supported by Israel Science Foundation (Grant Number 1647/17) and the Vigevani Chair in Statistics. The research of OB and MM is partly funded by the NWO Gravitation Programme Networks (Grant Number 024.002.003) and an NWO Top Grant (Grant Number 613.001.352).
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
