Transient Analysis

Approximation by the conditional mean bandwidth. In this paper, the state information upon which we condition will be either the current level of each source or the current level and age (current time) in that level of each source. No state from the within level process is assumed. Conditional on that state information, we can compute the probability that each source will be in each possible level at any time in the future, from which we can calculate the conditional mean and variance of the aggregate required bandwidth by adding.

The Lindeberg-Feller central limit theorem (CLT) for non-identically-distributed summands can be applied to generate a normal approximation characterized by the conditional mean and conditional variance; see p. 262 of Feller [13]. For the normal approximation we must check that the aggregate is not dominated by only a few sources.

Let B(t) denote the (random) aggregate required bandwidth at time t, and let I(0) denote the (known deterministic) state information at time 0. Let (B(t) | I(0)) be a random variable with the conditional distribution of B(t) given the information I(0). By the CLT, the normalized random variable  

$$\displaystyle\frac{(B(t)\vert I(0))-E(B(t)\vert I(0))}{\sqrt{Var (B(t)\vert I(0))}}$$ (2)

is approximately normally distributed with mean 0 and variance 1 when the number of sources is suitably large.

Since the conditional mean alone tends to be very descriptive, we use the approximation  

$$(B(t)\vert I(0)) \approx E(B(t)\vert I (0))~,$$ (3)

which could be justified by a (weaker) law of large numbers instead of the CLT. We will show that the conditional mean in (3) can be efficiently computed, so that it can be used for real-time control. From (2), we see that the error in the approximation (3) is approximately characterized by the conditional standard deviation $\sqrt {Var (B(t)\vert I(0))}$.We also will show how to compute this conditional standard deviation, although the required computation is more difficult. If there are n sources that have roughly equal rates, then the conditional standard deviation will be $O( \sqrt n )$,while the conditional mean is O(n).

Given that our approximation is the conditional mean, and given that our state information does not include the state of the within-level variation process, the within-level variation process plays no role because it has zero mean. Let i index the source. Since the required bandwidths need not have integer values, we index the level by the integer j, $1 \leq j \leq J_i$, and indicate the associated required bandwidths in the level by b_jⁱ. Hence, instead of (1), the required bandwidth for source i can be expressed as  

$$B^i (t) = b_{L^i (t)}^i + W_{L_i (t)} (t)~, \quad t \ge 0~.$$ (4)

Let P_jk⁽ⁱ⁾ (t| x) be the probability that the source-i level process is in level k at time t given that at time 0 it was in level j and had been so for a period x (i.e., the age or elapsed level holding time at time 0 is x). If ${\bf j}\equiv (j_1 , \ldots , j_n )$ and ${\bf x}\equiv (x_1 , \ldots , x_n )$ are the vectors of levels and ages of the n source level processes at time 0, then the state information is $I(0) = ( {\bf j}, {\bf x}) = (j_1 , \ldots , j_n ; x_1 , \ldots , x_n )$and the conditional aggregate mean is  

$$E(B(t) \vert I (0)) \equiv M(t \vert {\bf j}, {\bf x}) = \su... ...sum_{k_i = 1}^{J_i} P_{j_i k_i}^{(i)} (t\vert x_i ) b_{k_i}^i~.$$ (5)

From (5), we see that we need to compute the conditional distribution of the level, i.e., the probabilities P_jk⁽ⁱ⁾ (t|x), for each source i. In this section we show how to compute these conditional probabilities. We consider a single source and assume that its required bandwidth process is a semi-Markov process (SMP). (We now have no within-level variation process.) We now omit the superscript i. Let L(t) and B(t) be the level and required bandwidth, respectively, at time t as in (4). The process $\{L(t):t \geq 0 \}$ is assumed to be an SMP, while the process $\{B(t):t \geq 0 \}$is a function of an SMP, i.e., B(t) = b_L(t), where b_j is the required bandwidth in level j. If $b_j \ne b_k$ for $j \ne k$, then $\{B(t):t \geq 0 \}$ itself is an SMP, but if b_j = b_k for some $j \ne k$, then in general $\{B(t):t \geq 0 \}$ is not an SMP.

Laplace transform analysis. Let A(t) be the age of the level holding time at time t. We are interested in calculating  

$$P_{jk}(t\vert x) \equiv P(L(t) = k\vert L(0) = j, A(0) = x)$$ (6)

as a function of j, k, x, and t. The state information at time is the pair (j, x). Let P be the transition matrix of the DTMC governing level transitions and let F_jk(t) be the holding-time cdf given that there is a transition from level j to level k. For simplicity, we assume that F^c_jk(t)=1 - F_jk(t) > 0 for all j, k, and t, so that all positive x can be level holding times. Let P(t|x) be the matrix with elements P_jk(t|x) and let $\hat{P}(s\vert x)$ be the Laplace transform (LT) of P(t|x), i.e., the matrix with elements that are the Laplace transforms of P_jk(t|x) with respect to time, i.e.,  

$$\hat{P}_{jk} (s\vert x) = \int^{\infty}_0 e^{-st} P_{jk} (t\vert x) dt.$$ (7)

We will derive an expression for $\hat{P}(s\vert x)$. For this purpose, let G_j be the holding-time cdf in level j, unconditional on the next level, i.e.,  

$$G_j (x) = \sum_k P_{jk} F_{jk} (x)~.$$ (8)

For any cdf G, let G^c be the complementary cdf, i.e. G^c (x) = 1-G(x). Also let  

$$H_{jk}(t\vert x) = \frac{P_{jk}F_{jk}(t + x)}{G^c_j(x)} \quad \mbox{and}~~G_j(t\vert x) = \sum_k H_{jk}(t\vert x)$$ (9)

for G_j in (8). Then let $\hat{h}_{jk}(s\vert x)$ and $\hat{g}_j(s\vert x)$be the associated Laplace-Stieltjes transforms (LSTs), i.e.,  

$$\hat{h}_{jk}(s\vert x) = \int^{\infty}_0 e^{-st} dH_{jk}(t\v... ...~\hat{g}_j(s\vert x) = \int^{\infty}_0 e^{-st} dG_j(t\vert x)~.$$ (10)

Let $\hat{h}(s\vert x)$ be the matrix with elements $\hat{h}_{jk}(s\vert x)$.Let $\hat{q}(s)$ be the matrix with elements $\hat{Q}_{jk}(s)$, where  

$$Q_{jk}(t) = P_{jk}F_{jk}(t) \quad \mbox{and}~~ \hat{q}_{jk}(s) = \int^{\infty}_0 e^{-st} dQ_{jk}(t)~.$$ (11)

Let $\hat{D}(s\vert x)$ and $\hat{D}(s)$ be the diagonal matrices with diagonal elements  

$$\hat{D}_{jj} (s\vert x) \equiv [1- \hat{g}_j (s\vert x) ]/s,\qquad \hat{D}_{jj} (s) \equiv [1- \hat{g}_j (s)]/s~,$$ (12)

where $\hat{g}_j (s)$is the LST of the cdf G_j in (8).

Theorem 6812

 The transient probabilities for a single SMP source have the matrix of Laplace transforms  

$$\hat{P}(s\vert x) = \hat{D}(s\vert x) + \hat{h}(s\vert x) \hat{P}(s\vert)~,$$ (13)

where  

$$\hat{P}(s\vert) = (I - \hat{q}(s))^{-1} \hat{D}(s).$$ (14)

Proof. In the time domain, condition on the first transition. For $j \ne k$,

$$P_{jk}(t\vert x) = \sum_l \int^t_0 dH_{jl}(u\vert x) P_{lk}(t-u\vert)~,$$

so that

$$\hat{P}_{jk}(s\vert x) = \sum_l \hat{h}_{jl}(s\vert x) \hat{P}_{lk}(s\vert),$$

while

$$P_{jj}(t\vert x) = G^c_j(t\vert x) + \sum_l \int^t_0 dH_{jl}(u\vert x) P_{lj}(t-u\vert)~,$$

so that

$$\hat{P}_{jj}(s\vert x) = \frac{1 - \hat{g}_j(s\vert x)}{s} + \sum_l h_{jl}(s\vert x) \hat{P}_{lj} (s\vert).$$

Hence, (13) holds. However, P(t|0) satisfies a Markov renewal equation, as in Section 10.3 of Çinlar [5], i.e., for $j \ne k$,

$$P_{jk}(t\vert) = \sum_l \int^t_0 dQ_{jl}(u)P_{lk}(t - u\vert... ...c_j(t) + \sum_l \int^{\infty}_0 dQ_{jl}(u) P_{lj}(t - u\vert)~,$$

so that

P(t|0) = D(t) + Q(t) * P(t|0)

where * denotes convolution, and (14) holds.

To compute the LT $\hat{P}(s\vert)$, we only need the LSTs $\hat{f}_{jk}(s)$ and $\hat{g}_j (s)$ associated with the basic holding-time cdf's F_jk and G_j. However, to compute $\hat{P}(s\vert x)$, we also need to compute $\hat{D}(s\vert x)$ and $\hat{h}(s\vert x)$, which require computing the LSTs of the conditional cdf's H_jk(t|x) and G_j(t|x) in (9). The LSTs of these conditional cdf's are often easy to obtain because some cdf's inherit their structure upon conditioning. For example, this is true for phase-type, hyperexponential and Pareto distributions. Moreover, other cdf's can be approximated by hyperexponential or phase-type cdf's; see Asmussen, Nerman and Olsson [2] and Feldmann and Whitt [12]. If the number of levels is not too large, then it will not be difficult to compute the required matrix inverse (I - q(s))^-1 for all required s. Note that, because of the probability structure, the inverse is well defined for all complex s with $\mbox{Re}(s) \gt 0$. To illustrate with an important simple example, we next give the explicit formula for an on-off source.

Example 2.1. Suppose that we have an on-off source, i.e., so that there are two states with transition probabilities P₁₂ = P₂₁ = 1 and holding time cdf's G₁ and G₂. From (9) or by direct calculation,  

$$\begin{array} {r@{\;}l} \hat{P}(s\vert) &\equiv \left( \be... ... \hat{g}_1(s))& 1 - \hat{g}_2(s)\end{array}\right)~.\end{array}$$ (15)

Suppose that the levels are labeled so that the initial level is 1. Note that all transitions from level 1 are to level 2. Hence when considering the matrix $\hat{h}(s\vert x)$in (10) it suffices to consider only the element $\hat{h}_{12} (s\vert x)$.Since  

$$H_{12}^c (t\vert x) = G_{1}^c (t\vert x) = \displaystyle\fra... ...{g}_{1} (s\vert x) = \int_0^\infty e^{-st} dG_{1} (t\vert x) ~.$$ (16)

Since P₁₁ (t|x) = 1- P₁₂ (t|x), it suffices to calculate only P₁₂(t|x). Hence, in this context  

$$\hat{P}_{12} (s\vert x) = \displaystyle\frac{\hat{g}_{1} (s\vert x) (1- \hat{g}_2 (s))}{s(1- \hat{g}_1 (s) \hat{g}_2 (s))} ~.$$ (17)

We now determine the mean, second moment, and variance of the bandwidth process of a general multi-level source as a function of time. It is elementary that

We can calculate m_j(t|x) and s_j(t|x) by a single inversion of their Laplace transforms, using  

$$\hat{m}_j(s\vert x) \equiv \int^{\infty}_0 e^{-st} m_j(t\ver... ...quad \hat{s}_j(s\vert x) = \sum_k \hat{P}_{jk}(s\vert x) b^2_k.$$ (18)

To properly account for the within-level variation process when it is present, we should add its variance in level j, say w_j(t,x), to v_j(t,x), but we need make no change to the mean M_j(t,x). We anticipate that W_j(t,x) will tend to be much less than v_j(t,x) so that w_j(t,x) can be omitted; but it could be included.

Finally, we consider the aggregate bandwidth associated with n sources. Again let a superscript i index the sources. The conditional aggregate mean and variance are  

$$M(t\vert{\bf j}, {\bf x}) \equiv E(B(t)\vert I(0)) = \displaystyle\sum^n_{i = 1} m^i_{j_i} (t\vert x_i)$$ (19)

and  

$$V(t\vert{\bf j}, {\bf x}) \equiv Var (B(t)\vert I(0)) = \dis... ...\sum^n_{i = 1} [v^i_{j_i} (t\vert x_i)+w^i_{j_i}(t\vert x_i)],$$ (20)

where ${\bf j}= (j_1, \ldots, j_n)$ is the vector of levels and ${\bf x}= (x_1, \ldots, x_n)$ is the vector of elapsed holding times for the n sources with the single-source means and variances as in (18) and (20).

It is significant that we can calculate the conditional aggregate mean at any time t by performing a single inversion. We summarize this elementary but important consequence as a theorem.

Theorem 6869

The Laplace transform of the n-source conditional mean aggregate required bandwidth as a function of time is  

$$\hat{M}(s\vert{\bf j}, {\bf x}) \equiv \displaystyle\int^{\i... ...m_{k_i = 1}^{J_i} \hat{P}^{(i)}_{j_ik_i} (s\vert x_i) b_{k_i}~,$$ (21)

where the single-source transform $\hat{P}^{(i)}_{j_ik_i}(s\vert x_i)$ is given in Theorem 2.1.

Unlike for the aggregate mean, for the aggregate variance we evidently need to perform n separate inversions to calculate vⁱ_ji (t|x_i) for each i and then add to calculate $V(t\vert{\bf j}, {\bf x})$ in (23). (We assume that the within-level variances wⁱ_ji(t|x_i), if included, are specified directly). Hence, we suggest calculating only the conditional mean on line for control, and occasionally calculating the conditional variance off line to evaluate the accuracy of the conditional mean.