ON ABILITY OF A COMMUNICATION CHANNEL TO ACCOMMODATE MULTIMEDIA TRAFFIC

V. Marbukh\
Wireless Communications Technologies Group\
National Institute of Standards and Technology\
100 Bureau Drive, Stop 8920\
Gaithersburg, MD 20899-8920

# Abstract

The throughput of a communication system serving bursty multimedia
traffic can be characterized by the admission region: all possible sets
of multimedia sources the system can accommodate given the sources
statistical characteristics and Quality of Service ($\text{QoS}$)
requirements. Since throughput depends on the system resources
(bandwidth and buffering space) as well as the resource management
strategies, it is natural to define the system capacity as the upper
limit on the admission region over all physically feasible strategies.
This paper estimates the capacity of a buffered communication channel
serving multimedia traffic with $\text{QoS}$ requirements on the maximum
allowable traffic delay and loss. The buffer is assumed large enough to
make the channel capacity the limiting resource. Given the set of
multimedia sources within the system capacity, the paper also discusses
the scheduling disciplines that provide the required $\text{QoS}$.

# 1. Introduction

Emerging multimedia networks will statistically multiplex bursty
multimedia traffic sources with vastly different statistical
characteristics and Quality of Service ($\text{QoS}$) requirements. In
presence of multimedia traffic, different classes of resource (bandwidth
and buffer space) management strategies can be compared on the basis of
the admission region. The admission region represents all possible sets
of multimedia sources the system can accommodate with the corresponding
strategies, given the system resources, and $\text{QoS}$ requirements.
We consider a single buffered communication channel serving multimedia
traffic with $\text{QoS}$ requirements on maximum allowable cell loss
probability and delay. Due to limited paper space we assume that the
buffer is large enough to make the channel capacity (not the buffering
space) the limiting resource. This situation is typical for wireless
communication. We assume that $J$ Classes of Service ($\text{CoS}$) are
statistically multiplexed through a large buffer on a communication link
with a constant bit rate $C$. $\text{CoS}$$j$ includes $K_{j}$ identical
sources with the following $\text{QoS}$ requirements:

\(1\) $L_{j} \leq L_{j}^{\text{max}}$, $d_{j} \leq d_{j}^{\text{max}}$

where $L_{j}$ and $d_{j}$ are the traffic loss probability and delay
respectively. Given the scheduling discipline $S$ and $\text{QoS}$
requirements (1), the admission region $A(S)$ represents all possible
sets of multimedia users $K = (K_{1},\text{.}\text{.},K_{J}) \in A(S)$
the system can accommodate. We assume the buffer management strategy
which accepts all arriving traffic into the buffer and drops a cell of
class $j$ from the buffer once the cell current delay exceeds the limit
$d_{j}^{\text{max}}$ to prevent wasting the channel capacity on an
outdated traffic. Obviously, this buffer management strategy is optimal
in terms of maximizing the admission region for a sufficiently large
buffer but can be improved for small buffers.

It is natural to define the system capacity region as the upper limit of
the admission region $A(S)$ over all scheduling disciplines $S$:

(2) $A = \underset{S}{}A(S)$

Assuming that the statistical properties of the sources are known, the
paper approximates the capacity region (2) as a function of the channel
bit rate $C$ and $\text{QoS}$ requirements (1):
$A = Α(C;\gamma_{1}^{\text{max}},\text{.}\text{.},\gamma_{J}^{\text{max}};d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}})$.
The paper also discusses scheduling disciplines $S$ which closely
approach the capacity region (1). We consider the following large
deviations asymptotic regime: $C \rightarrow \infty,$
$L_{j}^{\text{max}} \rightarrow 0,$ $d_{j}^{\text{max}} = O(1)$,
$\gamma_{j}^{\text{max}} = - (\text{log}L_{j}^{\text{max}})/C = O(1)$.
It is known \[1\] that under this regime the statistical properties of
the sources can be characterized by the effective bandwidths:

\(3\)
$\alpha_{j}(s,t) = \frac{1}{\text{st}}\text{log}E\left\{ \text{exp}\lbrack\text{sx}_{\text{jk}}(t)\rbrack \right\}$

where$x_{\text{jk}}(t)$is the amount of traffic generated by a source
$k$ of class $j$ during time interval $\lbrack 0,t)$. We assume that
processes $x_{\text{jk}}(t)$ have stationary increments and are jointly
statistically independent for
$k = 1,\text{.}\text{.},K_{j},j = 1,\text{.}\text{.},J\text{.}$ The
average rate of a source of class $j$ is
$\lambda_{j} = \text{lim}_{s \rightarrow + 0}\alpha_{j}(s,t)$.

The paper is organized as follows. Section 2 conjectures the
distributional version of the Little theorem. Section 3 approximates the
capacity region in a case of uniform loss and $\text{CoS}$ specific
delay requirements: $L_{j} \leq L^{\text{max}},$
$d_{j} \leq d_{j}^{\text{max}}$. Section 4 approximate the capacity
region in a case of $\text{CoS}$ (1). Finally, section 5 illustrates our
results in a case of $J = 2$ classes of service and Brownian traffic
sources.

# 2. The Conservation Laws 

In a case of uniform $\text{QoS}$ requirements
$L_{j} \leq L^{\text{max}}$, $d_{j} \leq d^{\text{max}}$, the
corresponding capacity region
$A^{u}(C,\gamma^{\text{max}},d^{\text{max}})$ can be realized with the
First In First Out ($\text{FIFO}$) scheduling. It is known \[1\] that
the boundary of this region $\partial A^{u}$ is closely approximated by
an appropriately chosen linear hyperplane. Following \[2\]-\[3\], we may
pick a point $\overset{\sim}{K}$ on $\partial A^{u}$ and obtain the
tangent hyperplane to $\partial A^{u}$ which tauches $\partial A^{u}$ at
$\overset{\sim}{K}$:

\(4\)
$\sum_{j}^{}K_{j}e_{j}(\gamma^{\text{max}},d^{\text{max}},\overset{\sim}{K}) = C$

where a parameter $e_{j}(\gamma,T,K)$ can be justifiably called the
effective rate of a source of class $j$. The effective rates
$e_{j}(\gamma,T,K)$ depend on the traffic mixture $K$ and can be
calculated if the effective bandwidths (3) are known \[1\].

Consider a system that statistically multiplexes a traffic mixture
$K = (K_{1},\text{.}\text{.},K_{J})$ on a channel of capacity $C$
through an infinite buffer. Assuming that scheduling discipline treats
all sources of the same class equally, let $D_{j} = D_{j}(\gamma,K)$ and
$b_{j} = b_{j}(T,K)$ be given by
$\text{Pr}\left\{ d_{\text{jk}} \geq D_{j} \right\} = e^{- C\gamma}$ and
$b_{j} = E\lbrack\beta_{\text{jk}}|\beta_{\Sigma} \geq \text{TC}\rbrack$
where $d_{\text{jk}}$ and $\beta_{\text{jk}}$ are the delay and backlog
respectively for a traffic generated by a source $k$ of class $j$, and
$\beta_{\Sigma} = \sum_{}^{}\beta_{\text{jk}}$ is the total backlog.
Given a traffic mixture $K$ and a pair ($\gamma,T$) such that

\(5\)
$\text{Pr}\text{ob}\left\{ \beta_{\Sigma} \geq \text{TC} \right\} = e^{- C\gamma}$

we conjecture the following inequality:

\(6\)
$e_{j}(\gamma,T,K)E\lbrack d_{\text{jk}}|d_{\text{jk}} \geq D_{j}(\gamma,K)\rbrack \geq b_{j}(T,K)$

for any scheduling discipline. This inequality can be interpreted as a
distributional version of the Little theorem \[4\]. If
$\sum_{}^{}{K_{j}\lambda_{j}} < C$, $\gamma \rightarrow 0$, then
$e_{j}(T,\gamma,K) \rightarrow \lambda_{j}$, $D_{j} \rightarrow 0$,
$b_{j} \rightarrow 0$ and, as a result, (6) reduces to the Little
theorem:
$\lambda_{j}E\lbrack d_{\text{jk}}\rbrack = E\lbrack\beta_{\text{jk}}\rbrack$.
Inequality (6) also holds if the traffic mixture includes only identical
sources. In this particular case equality in (6) can be realized with
the First In First Out ($\text{FIFO}$) scheduling discipline. There is a
number of arguments which can be put forward to suggest that (6) holds
(at least approximately) in a general case and the boundaries in (6) can
be closely approached for all $j = 1,\text{.}\text{.},J$ simultaneously
with the Earliest Due Date scheduling discipline
$\text{EDD}(D_{1},\text{.}\text{.},D_{J})$ \[5\].

We will use (5)-(6) to derive upper bounds on the capacity region under
the large deviations asymptotic regime when
$E\lbrack d_{\text{jk}}|d_{\text{jk}} \geq D_{j}\rbrack \rightarrow D_{j}$,
and consequently, (5)-(6) take the following form:

\(7\) $D_{j}e_{j}(\gamma,T,K) \geq b_{j}$ where
$T = \frac{1}{C}\sum_{j}^{}{K_{j}b_{j}}$

**3. The Capacity Region for Uniform Losses**

Combining (4) with (7) we obtain the following system:

\(8\) $\sum_{j \in J}^{}{K_{j}D_{j}e_{j}(\gamma,T,K) \geq \text{CT}}$

\(9\) $\sum_{j \in J}^{}K_{j}e_{j}(\gamma,T,K) = C$

for any subset $J \subseteq \left\{ 1,2,\text{.}\text{.},J \right\}$.
Solving (9) for $T$ and then substituting this $T$ into (8) we obtain a
region (a simplex exterior) ${\overset{\sim}{R}}_{J}(K,C)$ in a
parameter space $(\gamma,D_{1},\text{.}\text{.},D_{J})$. Intersection of
these regions
$\overset{\sim}{R}(K,C) = intersect{\overset{\sim}{R}}_{J}(K,C)$ for all
subsets $J \subseteq \left\{ 1,\text{.}\text{.},J \right\}$

upper bounds the attainable $\text{QoS}$ region
$R(K,C)$$= \left\{ \gamma,D_{1},\text{.}\text{.},D_{J} \right\}$ in a
case of uniform loss probabilities:
$\gamma_{1} = \text{.}\text{.} = \gamma_{J} = \gamma$. Our hypotheses
are that region $\hat{R}(K,C)$ in fact closely approximates region
$R(K,C)$: $R(K,C) \simeq$$\overset{\sim}{R}(K,C)$, and the $\text{QoS}$
region can be closely approached with the
$\text{EDD}(d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}})$
scheduling discipline.

Consider a case of uniform loss and service specific delay requirements:
$L_{j} \leq L^{\text{max}}$, $d_{j} \leq d_{j}^{\text{max}}$,
$j = 1,\text{.}\text{.},J$. Without loss of generality assume the
$\text{CoS}$ are arranged according to the stringency of the
$\text{QoS}$ requirements:
$d_{1}^{\text{max}} \leq d_{2}^{\text{max}} \leq \text{.}\text{.} \leq d_{J}^{\text{max}}$.
All traffic mixtures $K$ for which the attainable $\text{QoS}$ region
(8)-(9) contains the $\text{QoS}$ parameters $L_{i} = L^{\text{max}}$,
$d_{i} = d_{i}^{\text{max}}$,
$i \in \left\{ 1,\text{.}\text{.},j \right\}$ form the following region:
$U_{j} = \left\{ K_{i}|\sum_{i \leq j}^{}K_{i}e_{i}(\gamma^{\text{max}},T_{j},K_{1},\text{.}\text{.},K_{j}) \leq C \right\}$
where $T_{j} = T_{j}(K_{1},\text{.}\text{.},K_{j})$ is the solution to
the following fixed point equation:
$T_{j} = \frac{1}{C}\sum_{i \leq j}^{}{K_{i}d_{i}^{\text{max}}e_{i}(\gamma^{\text{max}},T_{j},K_{1},\text{.}\text{.},K_{j})}$.
Regions $U_{j}$, and, consequently, their
intersection$$$U = intersectU_{j}$, $j = 1,\text{.}\text{.},J$ upper
bound the capacity region (2) in a case of uniform losses

\(10\)
$A(C,\gamma^{\text{max}},d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}}) \subseteq U$

Upper bound (10) is obtained by considering the attainable $\text{QoS}$
regions (8)-(9) for $J$ subsets $\left\{ 1,\text{.}\text{.},j \right\}$,
$j = 1,\text{.}\text{.},J$ of the set of services
$\left\{ 1,\text{.}\text{.},J \right\}$. It can be shown that applying
conservation laws to *all possible* subsets of the set of services
$\left\{ 1,\text{.}\text{.},J \right\}$ *would not produce a tighter
upper bound* on the capacity region than (10). We expect that the
intersection $U$, in fact, closely approximates the capacity region (2)
for uniform losses:

\(11\)
$A(C,\gamma^{\text{max}},d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}}) \simeq U$

and that the capacity region (11) can be closely approached with the
$\text{EDD}(d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}})$
scheduling.

**4. The Capacity Region in a General Case**

First, consider a \"homogeneous \"case when the traffic mixture consists
only of sources of the same class $j$: $K_{i} = 0,i \neq j$. Given the
$\text{QoS}$ requirements (1), the corresponding capacity region
$Α_{j}^{h}(C,\gamma_{j}^{\text{max}},d_{j}^{\text{max}})$ is
$K_{j} \leq K_{j}^{\text{max}} = C/e_{j}^{h}(C,\gamma_{j}^{\text{max}},d_{j}^{\text{max}})$
where $e_{j}^{h}$ is the corresponding \"homogeneous\" effective rate.
Consider all pairs $(\gamma,d)$ for which: $Α_{j}^{h}(C,\gamma,d)$=
$Α_{j}^{h}(C,\gamma_{j}^{\text{max}},d_{j}^{\text{max}})$, or,
equivalently,

\(12\) $e_{j}^{h}(C,\gamma,d)$=
$e_{j}^{h}(C,\gamma_{j}^{\text{max}},d_{j}^{\text{max}})$

Equation (12) describes the trade-off between the $\text{QoS}$
requirements on loss $(\gamma)$and delay $(d)$ in a homogeneous case:
$K_{i} = 0,i \neq j$. Assuming that this trade-off holds in a
heterogeneous case, when a mixture of different services is multiplexed
on the channel, one may try to approximate the heterogeneous capacity
region as follows:

\(13\)
$A(C;\gamma_{1}^{\text{max}},\text{.}\text{.},\gamma_{J}^{\text{max}};d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}}) \simeq$

$A(C;\gamma;d_{1},\text{.}\text{.},d_{J})$

where region $A(C;\gamma;d_{1},\text{.}\text{.},d_{J})$ is approximated
according to (11), and
$d_{j} = d_{j}(\gamma;\gamma_{j}^{\text{max}},d_{j}^{\text{max}})$ are
determined by (12) for some $\gamma$. After implementing this procedure
for general traffic sources the resulting approximate capacity region
will depend on the arbitrary parameter $\gamma$ since the trade-off
between the loss and delay depends on the traffic mixture. However, for
Brownian traffic sources \[1\] the effective rate is
$e_{j}(\gamma,d) = \lambda_{j} + \frac{\sigma_{j}^{2}}{2}\frac{\gamma}{d}$,
equation (12) takes the following form:
$\frac{d}{\gamma} = \frac{d_{j}^{\text{max}}}{\gamma_{j}^{\text{max}}}$
and, consequently, the right-hand side of approximation (12) is
independent of the parameter $\gamma$. Arrange services as follows:
$\omega_{1} \leq \text{.}\text{.} \leq \omega_{J}$, where
$\omega_{j} = \frac{d_{j}^{\text{max}}}{\gamma_{j}^{\text{max}}}$. Using
(11)-(13) we can approximate the capacity region in a case of
$\text{QoS}$ requirements (1) and Brownian traffic sources as follows:

\(14\)
$A(C;\gamma_{1}^{\text{max}},\text{.}\text{.},\gamma_{J}^{\text{max}};d_{1}^{\text{max}},\text{.}\text{.},d_{J}^{\text{max}}) \simeq$$\underset{j = 1}{\overset{J}{intersect}}U_{j}$

where regions $U_{j}$ are as follows:
$\left\{ K_{i}|\sum_{i}^{}K_{i}\lambda_{i} + \frac{1}{2\chi_{j}}\sum_{i}^{}{K_{i}\sigma_{i}^{2}} \leq C,i = 1,\text{.}\text{.},j \right\}$
and $\chi_{j}$ are easily obtained from the following quadratic
equations:

$\chi_{j} = \frac{1}{C}\sum_{i \leq j}^{}{K_{i}\omega_{i}\lambda_{i} + \frac{1}{2{C\chi}_{j}}\sum_{i \leq j}^{}{K_{i}\omega_{i}\sigma_{i}^{2}}}$

We expect that for Brownian sources approximation (14) is in fact an
identity and for general traffic sources (14) closely approximates the
capacity region. We also expect that for Brownian (arbitrary) sources
the capacity region can be realized (closely approached) with the
scheduling discipline
$S(\gamma_{1}^{\text{max}},\text{.}\text{.},\gamma_{J}^{\text{max}};\omega_{1}^{\text{max}},\text{.}\text{.},\omega_{J}^{\text{max}})$.
This discipline can be interpreted as a generalization of the
$\text{EDD}$ with service $j$ specific time scale:
$t \rightarrow \tau_{j} = t/\gamma_{j}^{\text{max}}$ and assuming that
service $j$ specific deadline with respect to the time scale $\tau_{j}$
is $\omega_{j}^{\text{max}}$.

It can be shown that the region $U_{j}$ can be closely approximated by
an appropriately chosen simplex:

$\left\{ K_{i}|\sum_{i}^{}K_{i}e_{\text{ji}}^{} \leq C,K_{i} \geq 0,i = 1,\text{.}\text{.},j \right\}$,
and, consequently, the capacity region (13) can be approximated by the
$J$-dimensional polyhedron:

$\left\{ K_{j}|\sum_{i \leq j}^{}K_{i}e_{\text{ji}}^{} \leq C,K_{j} \geq 0,\overset{}{}j = 1,\text{.}\text{.},J \right\}$.
This approximation is consistent with theoretical and simulation results
for specific scheduling disciplines \[6\]-\[7\].

**5. Example: Two Classes of Service, Brownian Traffic Sources**

As an example consider a case of $J = 2$ classes of service, and
Brownian traffic sources. We use the same notations as in the previous
section and assume that $\omega_{1} \leq \omega_{2}$. Fig. 1 shows
regions $U_{1}$, $U_{2}$ and their intersection
$A = U_{1}intersectU_{2}$ in the following three cases: (a)
$\frac{\omega_{2}}{\omega_{1}} = 1$, (b)
$1 < \frac{\omega_{2}}{\omega_{1}} < \delta$, and (c)
$\frac{\omega_{2}}{\omega_{1}} > \delta$ where

\(15\) $\delta = 2(1 + 2\frac{\lambda_{1}\omega_{1}}{\sigma_{1}^{2}})$

Figure 1: Schematic view of the capacity region in a case of two classes
of service.

If $\frac{\omega_{2}}{\omega_{1}} = 1$, then the capacity region
$A = U_{2} \subset U_{1}$ has linear boundary since this case in effect
is a case of uniform $\text{QoS}$ requirements. If
$1 < \frac{\omega_{2}}{\omega_{1}} < \delta$, then still
$A = U_{2} \subset U_{1}$, but the capacity region has non-linear
boundary. If $\frac{\omega_{2}}{\omega_{1}} > \delta$ then
$U_{2} ⊄ U_{1}$, and the boundary ($\text{DCB}$) of the capacity region
$A$ contains a linear segment ($\text{DC}$). The trapezoidal shape of
the capacity region in a case $\frac{\omega_{2}}{\omega_{1}} > \delta$
indicates that even when the system is serving the maximum possible
number of high priority sources of class $1$, the channel still has
enough residual capacity to accommodate certain number of sources of
class $2$ as low priority. Examination of (15) shows that this is
possible if the high priority sources are burty and the difference in
the $\text{QoS}$ requirements for different services is sufficiently
large to allow for a squeezing of the low priority traffic between the
bursts of the high priority traffic.

**References**

1.  F.P. Kelly, \"Notes on effective bandwidth,\" *Stochastic Networks*,
    F.P. Kelly, S. Zachary, I. Ziedins, Eds., Oxford: Clarendon Press,
    1996, pp. 141-68.

2.  J.Y. Hui, *Switching and Traffic Theory for Integrated Broadband
    Networks*, Boston, MA: Kluwer, 1990.

3.  F.P. Kelly, \"Effective bandwidth at multi-type queues,\" *Queueing
    Syst*., vol. 9, pp. 5-15, 1991.

4.  W. Whitt, \"A review of $L = \lambda W$,\" *Queueing Systems*, vol.
    9, 1991, pp. 235-68.

5.  S.S Panwar, D. Towsley, and J.K. Wolf, \"Optimal scheduling policies
    for a class of queues with customer deadlines to the beginning of
    service,\" *J. Ass. Comput. Mach*., pp. 832-844, 1988.

6.  A.W. Berger and W. Whitt, \"Extending the effective bandwidth
    concept to networks with priority classes,\" *IEEE Comm. Magazine*,
    vol. 36, no.8, Aug. 1998, pp.78-83.

7.  A.I. Elwalid and D. Mitra, \"Analysis, approximations and admission
    control of a multi-service multiplexing system with priorities,\"
    *Proc. IEEE INFOCOM\'95*, pp. 463-72, 1995