Recovery from Congestion in Steady State

For capacity planning, it is useful to consider the time required to recover from a high-congestion event, as well as the likelihood of the high-congestion event. The likelihood of a high-congestion event in steady state can be estimated using a large deviation principle (LDP) approximation. The well-known Chernoff bound (e.g. see [7]) gives an upper bound to the stationary tail probabilities of the aggregate level process, even for finitely many sources. By Chebychev's inequality, for all $\theta\gt$,

$${\bf P}[L(t)\ge x]\le e^{-\theta x}{\bf E}[e^{\theta L(t)}] ... ...eta L_i(t)}] =e^{-\theta x}\prod_i\sum_jp^i_j e^{\theta b^i_j},$$ (38)

where bⁱ_j is the required bandwidth and pⁱ_j is the steady-state probability of level j in source i, as in (31). Thus,  

$${\bf P}[L(t)\ge x]\le e^{- I(x)},\quad{\rm where}\quad I(x)=... ...eft(\theta x - \sum_i\log\sum_jp^i_j e^{\theta b^i_j}\right)~.$$ (39)

It can be shown [7] that such bounds are asymptotically tight (have a large deviation limit) as the number of sources increases provided the spectrum of behavior of individual sources is sufficiently regular, yielding the exponential approximation  

$$P(L(t) \geq x) \approx e^{-I(x)}~.$$ (40)

Finding the rate function I will in general require numerical solution of the variational expression (42). It can be shown that the RHS of (42) is a concave function of $\theta$, and under mild conditions it is differentiable also. Hence the supremum is achieved at the unique solution $\theta$ to the Euler-Lagrange equation  

$$x= \sum_i\left(\frac{\sum_j b^i_j p^i_j e^{\theta b^i_j}} {\sum_{j'} p^i_{j'} e^{\theta b^i_{j'}}}\right).$$ (41)

Generally, it is not difficult to numerically determine the supremum in (42) by location of the solution to (44).
Example 6.1 In special cases the variational problem can be solved explicitly. This is possible in the case of n homogeneous two-level sources. Here we have bⁱ_j=b_j with $j\in\{1,2\}$, $0\le b_1 < b_2$ and p₁+p₂=1. For this case,

with y(x)=p₁(x-b₁)/(p₂(b₂-x)) for $b_1 \leq x \leq b_2$ and $I(x)=+\infty$ elsewhere.

We now show how to estimate the time to recover from the high-congestion event, where the high-congestion event is a large initial bandwidth x. We understand recovery to occur when the aggregate bandwidth is again less than or equal to the capacity c. In applications, we suggest examining the function of aggregate bandwidth giving both the probability of reaching that level and the recovery time from that level to assess whether or not capacity is adequate to meet demand.

We assume that recovery occurs when the aggregate bandwidth drops below a level c, where x > c > m, with x being the initial level and m being the steady-state mean. Given that we know the current level of each level process, we know that the remaining holding time (and also the age) is distributed according to the level-holding-time stationary-excess distribution in (32). We use the LDP to approximate the conditional distribution of the level process for each source (in steady state). The idea is to perform the appropriate change of measure (tilting) corresponding to the rare event.

Given that $P( \sum_{i=1}^n B^i \ge x) \approx e^{-I(x)}$for I(x) in (42), the LDP approximation is  

$$P(B^i = b_j^i \vert \sum_{i=1}^n B^i \ge x) \approx \bar{p}_... ...i \theta^\ast}}{\sum_{k=1}^{J_i} p_k^i e^{b_k^i \theta^\ast}}~,$$ (42)

where $\theta^\ast$ yields the supremum in (42). Put another way, comparing (47) with (44) we see that $\theta^*$ is chosen to make the expectation of $\sum_iB_i$ equal to x under the distribution $\bar{p}$.In the homogeneous case, equality in (47) in the limit as the number of sources increases is due to the conditional limit theorem of Van Campenhout and Cover [21]. The limit can be extended to cover suitably regular heterogeneity in the bⁱ_j, e.g., finitely many types of source.

We thus approximate the conditional bandwidth process by

for $\bar{p}_j^i$ in (4.3) which has Laplace transform  

$$\sum_{i=1}^n \sum_{j=1}^{J_i} \bar{p}_j^i \sum_{k=1}^{J_i} b_k^i \hat{P}_{jk} (s)~.$$ (43)

The Laplace transform $\hat{P}_{jk} (s)$ in (49) was derived in Theorem 4.1. We can numerically invert it to calculate the conditional mean as a function of time. We then can determine when E(B(t)|B(0) = x) first falls below c. In general, this conditional mean need not be a decreasing function, so that care is needed in the definition, but we expect it to be decreasing for suitably small t because the initial point B(0) is unusually high.