A Framework for throughput and stability analysis of a DS-cdma
network[^1]

Vladimir Marbukh and Nader Moayeri

National Institute of Standards and Technology

100 Bureau Drive, Stop 8920, Gaithersburg, MD 20899-8920 USA

PH: 301-975-2235 FAX: 301-590-0932

e-mail: marbukh@nist.gov, moayeri@nist.gov

[Abstract]{.underline} - We propose a framework for throughput and
stability analysis of a Direct Sequence Code Division Multiple Access
(DS-CDMA) network. Given chip rate, processing gains, packet structure,
coding scheme, and the characteristics of the wireless channel, we
derive a system of non-linear fixed point equations for the sustainable
link bit rates. The dimension of this system is equal to the number of
network nodes receiving transmissions from other nodes. Generally, this
non-linear system may have multiple locally stable solutions which
indicates a possible instability of the DS-CDMA network because the
persistent link bit rates may depend on the initial link loads. As an
example, we consider throughput and stability of the reverse link in a
cellular system, i.e., from mobiles to the base station. A reverse link
is described by a single fixed point equation regardless of the number
of mobiles.

# Introduction {#introduction .First-Level-Heading}

The major obstacle for applying a methodology of queueing networks \[1\]
to performance evaluation of a Direct Sequence Code Division Multiple
Access (DS-CDMA) network lies in assigning bit service rates to the
network links. In a DS-CDMA network transmission from a node $i$ to a
node $j$ is seen as interference by transmissions from any node $n$ to
any node $k$, such that $(n,k) \neq (i,j)$, and consequently, reduces
the bit service rates for links $(n,k)$. This interaction introduces
*positive feedback* into the system, i.e., temporary congestion in any
part of the network caused by fluctuations in the incoming traffic or
the wireless channel quality, reduces the network throughput around the
congested area, which in turn increases the congestion, etc. This
mechanism may be responsible for spreading local congestion into a
larger portion of the network.

In this paper we propose a simple aggregated framework for analyzing
these kinds of problems. Given chip rate, processing gains, packet
structure, coding scheme, and characteristics of the wireless channel,
the model allows one to estimate the sustainable link bit rates and
assess the stability of a DS-CDMA network. The sustainable link bit
rates are determined by the stable solutions of the system of non-linear
fixed point equations. The number of equations is equal to the number of
network nodes receiving transmissions from other nodes. This system has
a unique globally stable solution under light and heavy traffic
conditions. However, for moderate incoming traffic the corresponding
system may have multiple locally stable solutions describing persistent
lightly loaded and congested network modes. This phenomenon indicates a
possible instability of the DS-CDMA network. The network stays in the
lightly loaded or congested mode for a long time depending on the
initial load. Note that this phenomenon is similar to the unstable
behavior of some other multiple access algorithms, such as ALOHA \[1\].
The instability of a reverse link in DS-CDMA for data transmission was
also discussed in \[2\].

The paper is organized as follows. Section 2 describes a queueing model
of a link in a DS-CDMA network. Section 3 uses a simple model for
calculating the packet error probability. Section 4 derives a system of
fixed point equations that determine the link utilization in a DS-CDMA
network. Section 5 analyses the throughput and stability of the reverse
link: from mobiles to the base station. A reverse link is described by a
single fixed point equation regardless of the number of mobiles.

# Queueing model of ds-cdma {#queueing-model-of-ds-cdma .First-Level-Heading}

Fig. 1 presents a queueing model of a link $(i,j)$in a packet-based,
DS-CDMA network.

![](media/image1.wmf){width="3.1166666666666667in"
height="2.3361111111111112in"}

For simplicity we assume that packets have fixed length-
$L\lbrack\text{bits}\rbrack$. Node $i$generates traffic to node$j$at an
average rate $\lambda_{\text{ij}}\lbrack\text{bits}\text{/sec}\rbrack$.
This traffic enters a buffer of size
$B_{\text{ij}}\lbrack\text{packets}\rbrack$, if buffer space is
available. Traffic from the buffer is transmitted at the constant rate

\(1\) ${\hat{c}}_{\text{ij}} = \frac{R^{c}}{N_{\text{ij}}}$,

where $R^{c}$ is the chip rate of the system and $N_{\text{ij}}$ is the
processing gain for the transmission from node $i$ to node$j$.
Transmission rate (1) is also the peak bit service rate provided by link
$(i,j)$. Due to interference, only a fraction of packets transmitted
from node $i$ to node$j$ is accepted at node$j$ as received correctly
(i.e. without errors, or with an acceptable number of bit errors). These
packets leave the system as successfully delivered. Let
$1 - G_{\text{ij}}$ be the probability that a transmitted packet is
successfully delivered. Packet error probability$G_{\text{ij}}$ depends
on the bit energy-to-noise ratio, coding scheme, etc. and is discussed
in the next section. Some packets that are received with an unacceptable
number of bit errors are retransmitted. We model this feature of the
system assuming that each packet received with unacceptable number of
bit errors is retransmitted with probability $\Omega_{\text{ij}}$ or
leaves the system with probability $1 - \Omega_{\text{ij}}$. We assume,
for the purpose of computing throughputs, that $G_{\text{ij}}$ and
$\Omega_{\text{ij}}$ remain constant regardless of how many times a
packet is transmitted until it is either received with an acceptable
number of errors or it leaves the system. We also assume that a packet
stays in the buffer until it leaves the system.

The link queueing performance can be characterized by the probability
that a packet is delivered successfully and by the probability
distribution of the delay for successfully delivered packets. Note that
delay depends on scheduling discipline for fresh and retransmitted
packets. Due to retransmissions, performance evaluation of a link in
presence of bursty traffic is not a simple task even if the
probabilities $G_{\text{ij}}$ are fixed. The major problem is that
retransmissions from node $i$ to node$j$ are jointly statistically
dependent for different origin destination pairs $(i,j)$. This leads to
a strong statistical correlation among different queues in a DS-CDMA
network. It can be shown that temporary congestion, and consequently
packet delays and buffer overflows tend to occur synchronously at
different nodes of a DS-CDMA network. A performance analysis of the
resulting collection of interacting systems shown on Fig. 1 is an
unrealistic task. Note that attempts to analyze performance of each
session separately assuming that packet error
probabilities$G_{\text{ij}}$ are constant, in effect, eliminates
statistical multiplexing and significantly underestimates the system
ability to handle multimedia traffic.

This paper is limited to throughput analysis of a DS-CDMA network in the
case of infinitely large buffers: $B_{\text{ij}} = \infty$. It is easy
to see that given $G_{\text{ij}}$, the average clearing rate for traffic
backlogged on a link $(i,j)$ is:

( 2)
$c_{\text{ij}} = {\hat{c}}_{\text{ij}}(1 - \Omega_{\text{ij}}G_{\text{ij}})$.

Since retransmissions introduce additional packet delays, for real-time
traffic with very stringent delay requirements no retransmission is
allowed ($\Omega_{\text{ij}} = 0$), and the clearing rate is constant
and equal to the peak service rate:
$c_{\text{ij}} = {\hat{c}}_{\text{ij}}$. For non real-time traffic with
very loose delay requirements, there is no restrictions on the number of
retransmissions ($\Omega_{\text{ij}} = 1$) and the average clearing rate
is: $c_{\text{ij}} = {\hat{c}}_{\text{ij}}(1 - G_{\text{ij}})$.

# packet error probability {#packet-error-probability .First-Level-Heading}

The packet error probability $G_{\text{ij}}$ is a decreasing function of
the bit energy-to-interference ratio
$(\frac{E_{b}}{I_{0}})_{\text{ij}}$:

\(3\)
$G_{\text{ij}} = G_{\text{ij}}\lbrack(\frac{E_{b}}{I_{0}})_{\text{ij}}\rbrack$.

The bit energy-to-interference ratio is:

\(4\)
$(\frac{E_{b}}{I_{0}})_{\text{ij}} = \frac{N_{\text{ij}}P_{\text{ij}}\xi_{\text{ij}}}{\sigma_{j}^{2} + \sum_{n \neq j}^{}\xi_{\text{nj}}\sum_{k:(n,k) \neq (i,j)}^{}{P_{\text{nk}}\delta_{\text{nk}}}}$,

where $P_{\text{ij}}$ is the transmission power from node $i$ to node
$j$, $\xi_{\text{ij}}$ is the power attenuation factor from node $i$ to
node $j$, $\delta_{\text{nk}} = 1$ if node $n$transmits to node $k$ and
$\delta_{\text{nk}} = 0$otherwise, and $\sigma_{j}^{2}$ is the average
power of the background noise at node $j$.

The packet error probabilities $G_{\text{ij}}$ depend on the bit
energy-to-interference ratio $(\frac{E_{b}}{I_{0}})_{\text{ij}}$, as
well as wireless channel quality, packet structure, and coding scheme.
In this section we derive an expression for the packet error probability
$G_{\text{ij}}$ under the following assumptions:

-   perfect interleaving, i.e., all bit errors in the packet are jointly
    statistically independent,

-   all bit errors are discovered, and

-   a packet is accepted if the number of erroneous bits does not exceed
    threshold $l_{\text{ij}}^{} = \alpha_{\text{ij}}L$ where threshold
    $\alpha_{\text{ij}}$ is a constant depending on the error correction
    coding scheme used at node $j$ for packets received from node $i$.

> Under these assumptions, the number of bit errors in the packet is
> described by the binomial distribution \[3\] and the packet error
> probability is:

\(5\)
$G_{\text{ij}} = \sum_{l = l_{\text{ij}}^{} + 1}^{L}{\frac{L!}{l!(L - l)!}g_{\text{ij}}^{l}(1 - g_{\text{ij}})^{L - l}}$,

where $g_{\text{ij}}$is the bit error probability for a transmission
from node $i$to node$j$. Since typically a packet consists of a large
number of bits, we can approximate the binomial distribution (5) by the
normal distribution assuming that

\(6\) $L \rightarrow \infty$

and

\(7\)
$\eta_{\text{ij}} = \frac{\alpha_{\text{ij}} - g_{\text{ij}}}{\sqrt{g_{\text{ij}}(1 - g_{\text{ij}})}}L_{\text{ij}}^{\frac{1}{2}}$

is constant. Under (6)-(7) the packet error probability (5) takes the
following form \[3\]:

\(8\)
$G_{\text{ij}} = \frac{1}{\sqrt{2\pi}}\int_{\eta_{\text{ij}}}^{\infty}{e^{- \frac{x^{2}}{2}}\text{dx}}$.

Typically, the packet error probability is small, and formula (8) can be
simplified further \[3\]:

$G_{\text{ij}} \approx \frac{1}{\sqrt{2\pi}}\frac{e^{- \frac{\eta_{\text{ij}}^{2}}{2}}}{\eta_{\text{ij}}}$
as $\eta_{\text{ij}} \rightarrow \infty$.

The bit error probability $g_{\text{ij}}$ is a decreasing function of
the bit energy-to-interference ratio
$(\frac{E_{b}}{I_{0}})_{\text{ij}}$:

\(9\)
$g_{\text{ij}} = g_{\text{ij}}\lbrack(\frac{E_{b}}{I_{0}})_{\text{ij}}\rbrack$.

It is usually assumed that

\(10\)
$g_{\text{ij}} = e^{- \beta_{\text{ij}}\lbrack(\frac{E_{b}}{I_{0}})_{\text{ij}}\rbrack}$

where parameter$\beta$ characterizes the asymptotic coding gain. Fig. 2
shows the normalized average clearing rate
$\frac{c_{\text{ij}}}{{\hat{c}}_{\text{ij}}}$ as a function of the bit
energy-to-interference ratio $(\frac{E_{b}}{I_{0}})$ for different
retransmission probabilities
$\Omega = \Omega_{1} < \Omega_{2} < \Omega_{3}$.

![](media/image2.wmf){width="3.122916666666667in"
height="2.671527777777778in"}

# fixed point equations for the link utilization {#fixed-point-equations-for-the-link-utilization .First-Level-Heading}

Formula (2) gives the average clearing rate for a link$(i,j)$ as a
function of the bit energy-to-interference ratio
$(\frac{E_{b}}{I_{0}})_{\text{ij}}$:
$c_{\text{ij}} = c_{\text{ij}}\lbrack(\frac{E_{b}}{I_{0}})_{\text{ij}}\rbrack$.
The average utilization of link $(i,j)$is:

\(11\)
$\rho_{\text{ij}} = \text{min}\left\{ 1,\frac{\lambda_{\text{ij}}}{E\left\{ c_{\text{ij}}\lbrack(\frac{E_{b}}{I_{0}})_{\text{ij}}\rbrack \right\}} \right\}$,

where $E\left\{ \text{.} \right\}$denotes mathematical expectation. In
this section we derive approximate fixed point equations for the average
link utilization based on the following approximations. First, we assume
that the clearing rate averaged over bit energy-to-interference ratio
can be approximately replaced by the clearing rate as a function of the
average bit energy-to-interference ratio:

\(12\)
$$$\rho_{\text{ij}} \approx {\overset{\sim}{\rho}}_{\text{ij}} = \text{min}\left\{ 1,\frac{\lambda_{\text{ij}}}{c_{\text{ij}}\lbrack E\left\{ (\frac{E_{b}}{I_{o}})_{\text{ij}} \right\}\rbrack} \right\}$.

Obviously,

$(\frac{E_{b}}{I_{0}})_{\text{ij}} \geq (\frac{E_{b}}{I_{o}})_{\text{ij}}^{}$

where

$(\frac{E_{b}}{I_{o}})_{\text{ij}}^{} = \frac{N_{\text{ij}}P_{\text{ij}}\xi_{\text{ij}}}{\sigma_{j}^{2} + \sum_{n \neq j}^{}\xi_{\text{nj}}\sum_{k \neq n}^{}{P_{\text{nk}}\delta_{\text{nk}}}}$.

We also make the following two approximations:

\(13\)
$E\left\{ (\frac{E_{b}}{I_{0}})_{\text{ij}} \right\} \approx E\left\{ (\frac{E_{b}}{I_{o}})_{\text{ij}}^{} \right\}$

\(14\)
$E\left\{ (\frac{E_{b}}{I_{o}})_{\text{ij}}^{} \right\} \approx {\overline{(\frac{E_{b}}{I_{o}})}}_{\text{ij}}$,

where

\(15\)
${\overline{(\frac{E_{b}}{I_{o}})}}_{\text{ij}} = \frac{N_{\text{ij}}P_{\text{ij}}\xi_{\text{ij}}}{\sigma_{j}^{2} + \sum_{n \neq j}^{}\xi_{\text{nj}}\sum_{k \neq n}^{}{P_{\text{nk}}E\left\{ \delta_{\text{nk}} \right\}}}$.

It can be shown that all three approximations (12)-(14) are valid for
large networks where each received signal is a superposition of
transmissions by a large number of nodes. Combining (12)-(14) and taking
into account that

( 16) $E\left\{ \delta_{\text{nk}} \right\} = \rho_{\text{nk}}$,

we obtain the following system of equations:

\(17\)
${\overset{\sim}{\rho}}_{\text{ij}} = \text{min}\left\{ 1,\frac{\lambda_{\text{ij}}N_{\text{ij}}}{R^{c}(1 - \Omega_{\text{ij}}{\overset{\sim}{G}}_{\text{ij}})} \right\}$

\(18\)
${\overset{\sim}{G}}_{\text{ij}} = G_{\text{ij}}\lbrack{\overline{(\frac{E_{b}}{I_{o}})}}_{\text{ij}}\rbrack$

\(19\)
${\overline{(\frac{E_{b}}{I_{o}})}}_{\text{ij}} = \frac{N_{\text{ij}}P_{\text{ij}}}{\sigma_{j}^{2} + \sum_{n \neq j}^{}\xi_{\text{nj}}\sum_{k \neq n}^{}{P_{\text{nk}}{\overset{\sim}{\rho}}_{\text{nk}}}}$.

Substituting expression (19) for
${\overline{(\frac{E_{b}}{I_{o}})}}_{\text{ij}}$ into the right-hand
side of (18), and then substituting the resulting expression (18) for
${\overset{\sim}{G}}_{\text{ij}}$ into the right-hand side of (17), we
obtain a system of $M$fixed point equations for $M$average link
utilization ${\overset{\sim}{\rho}}_{\text{ij}}$, where $M$is the number
of links in the network. It is possible to reduce the dimension $M$of
this system. Let us introduce the average power $P_{k}^{+}$ received by
node $k$as a result of transmissions by all other nodes $n \neq k$:

\(20\)
$P_{k}^{+} = \sum_{n \neq k}^{}{\xi_{\text{nk}}\sum_{j \neq n}^{}{P_{\text{nj}}{\overset{\sim}{\rho}}_{\text{nj}}}}$,

and rewrite equations (17)-(19) as follows:

\(21\)
$P_{k}^{+} = \sum_{n \neq k}^{}{\xi_{\text{nk}}\sum_{j \neq n}^{}{P_{\text{nj}}\text{min}\left\{ 1,\frac{\lambda_{\text{nj}}N_{\text{nj}}}{R^{c}(1 - \Omega_{\text{nj}}{\overset{\sim}{G}}_{\text{nj}})} \middle| \middle| \right\}}}$

\(22\)
${\overset{\sim}{G}}_{\text{nj}} = G_{\text{nj}}(\frac{N_{\text{nj}}P_{\text{nj}}\xi_{\text{nj}}}{\sigma_{j}^{2} + P_{j}^{+}})$,

forming a system of $K$ fixed point equations for $K$unknowns (20),
where $K$ is the number of nodes in the network receiving transmissions
from other nodes. Once this system is solved, the average link
utilization ${\overset{\sim}{\rho}}_{\text{ij}}$ can be calculated using
(12). Note that typically $K\text{<<}M$and it is much easier to solve
the system (21)-(22) than the system (17)-(19). In the next section we
consider a case of reverse link from mobiles to the base station where
$K = 1$.

# throughput and stability of the reverse link {#throughput-and-stability-of-the-reverse-link .First-Level-Heading}

In this section we consider the reverse link in a DS-CDMA network, where
$J$ mobiles transmit to the base station. The average power received at
the base station from all these transmissions is:

\(23\)
$P^{+} = \sum_{j}^{}{\xi_{j}P_{j}\text{min}\left\{ 1,\frac{\lambda_{j}N_{j}}{R^{c}(1 - \Omega_{j}{\overset{\sim}{G}}_{j})} \middle| \right\}}$,

where $P_{j}$ is the power transmitted by mobile $j$, $\xi_{j}$ is the
power attenuation factor from mobile $j$to the base station,
$\Omega_{j}$ is the retransmission probability for mobile $j$, and

\(24\)
${\overset{\sim}{G}}_{j} = G_{j}(\frac{N_{j}P_{j}\xi_{j}}{\sigma^{2} + P^{+}})$

is the packet error probability for mobile $j$. Substituting (24) into
the right-hand side of (23), we obtain a single equation for the average
power received at the base station from all mobiles $P^{+}$:

\(25\) $P^{+} = \phi(P^{+})$

regardless of the number of mobiles $J$. After solving equation (25),
the average uplink utilization from mobile $j$ to the base station can
be estimated as follows:

\(26\)
$\rho_{j} \approx {\overset{\sim}{\rho}}_{j} = \text{min}\left\{ 1,\frac{\lambda_{j}N_{j}}{R^{c}(1 - \Omega_{j}{\overset{\sim}{G}}_{j})} \right\}$.

In the particular case of $J$ identical mobiles transmitting data
traffic with very loose delay requirements: $\Omega_{j} = 1$,
$\xi_{j} = \xi$, $P_{j} = P$, $\lambda_{j} = \lambda$, $N_{j} = N$,
$G_{j} = G$, equations (23)-(24) reduce to the following system:

\(27\)
$\overset{\sim}{\rho} = \text{min}\left\{ 1,\frac{\theta}{1 - \overset{\sim}{G}} \right\}$

\(28\)
$\overset{\sim}{G} = G(\frac{\frac{N}{J}}{\sigma_{\text{eff}}^{2} + \overset{\sim}{\rho}})$,

where $\theta = \frac{N\lambda}{R^{c}}$ and
$\sigma_{\text{eff}}^{2} = \frac{\sigma^{2}}{\text{JP}\xi}$

![](media/image3.wmf){width="3.1222222222222222in"
height="2.328472222222222in"}

![](media/image4.wmf){width="3.1222222222222222in"
height="2.3229166666666665in"}

![](media/image5.wmf){width="3.1180555555555554in"
height="2.3229166666666665in"}

Substituting (28) into the right-hand side of (27) we obtain a following
fixed point equation:

\(29\) $\overset{\sim}{\rho} = \varphi(\overset{\sim}{\rho})$

Solution of this equation for light, moderate and heavy incoming traffic
is shown on Fig. 3a, 3b and 3c respectively. For light (heavy) incoming
traffic equation (29) has a unique globally stable solution
$\overset{\sim}{\rho} \ast 1$ ($\overset{\sim}{\rho} \ast 1$) shown by
thick dots on Fig.3. For moderate incoming traffic these two solutions
coexist as locally stable. This indicates bi-stability of the system.
Note that similar type of bi-stability has been observed in large-scale
wired networks \[4\].

# Acknowledgement {#acknowledgement .First-Level-Heading}

First author would like to thank Sri Kumar for useful discussions
related to the topic of this paper. Both authors gratefully acknowledge
Maarit Melvasalo for producing the plots and carrying out the
simulations for this paper.

references

(1) Bertsekas, D. and Gallager R., \"Data Networks,\" Prentice-Hall,
    1992.

(2) Honig, M.L. and Kim, J.B., \"Resource Allocation for Packet Data
    Transmission in DS-CDMA,\" *Proc. IEEE Globecom*, London, 1996.

(3) Papoulis, A., \"Probability, Random Variables, and Stochastic
    Processes,\" McGraw-Hill, 1991.

(4) Marbukh V., \"Loss Circuit Switched Communication
    Network-Performance Analysis and Dynamic Routing,\" *Queueing
    Systems*, 13(1993) 111-141.

[^1]: ^\*^ This work was supported by a grant from the NIST Advanced
    Technology Program (ATP)