\tenrm
\magnification=\magstep1
\hoffset=1.0in
\voffset=0.7in
\centerline{CSMA MULTIHOP NETWORKS}
\centerline{Throughput Analysis}
\centerline{by Dr. Bob W. McGwier N4HY}
\bigskip
Amateur Radio uses packet radio in a broadcast mode and typically uses
omnidirectional antennas for transmission.  If the two ends of the data
transfer are not within communication range, we will use a digipeater. The
protocol we use for medium access control is carrier sensed multiple access
(CSMA) protocol.  Under CSMA, a terminal will not transmit if it hears a
transmission in its neighborhood.  In a multihop environment (digipeater)
such as ours, CSMA is subject to ``hidden transmitter'' interference.  This
is when two or more transmitters outside hearing range of each other key
up at the same time and interfere with one or more recipients of the two
or more packets being simultaneously transmitted.  We call this a
collision.  We could almost completely eliminate this problem with busy tone
multiple access (BTMA) protocol.
The ``almost completely'' in the previous sentence is caused by the finite
speed of light and the response time of the receiver bringing up the busy
tone.  BTMA has implicit in its nature seperate transmit and receive operation.
Several papers have appeared analyzing throughput in CSMA packet radio
networks.  The best papers and the most useful (not always the
same) are by Boorstyn and Kershenbaum and we include one of their papers
as our only reference as it contains the most complete set of references
and is the basis for the work described here.
They have introduced a continuous
time Markov Chain model which lends itself to numerical techniques for
finding the steady state response of moderate sized (100-200 nodes) networks.
This type of model allows for dependencies between non-adjacent nodes to be
modeled and analyzed.  The primary purpose of this paper is to introduce these
ideas to the amateur radio literature, to supply some rigor to Clark's
``But Wait There's More'' treatise, and hopefully give one more nudge to
do something about the problem.
$$\hbox{Our Packet Networks and CSMA}$$
\par
Our networks are made up of terminal node controllers (hereinafter TNC or
simply node) with radios for broadcasting packetized data over limited
distances (forget HF, that problem is enormously complicated).  In the most
general case, the source and destination nodes will not be able to hear
each other directly, and will digipeat through intermediate TNC's.  We
assume that the network topology and traffic requirements operate on a
time scale sufficiently long to establish steady state conditions.  We
assume an idealized AX25L2V2 model and completely neglect COSI, IP,
NET/ROM, or TEXNET and any point by point acks or dynamic routing these
systems may employ.
$$\hbox{The Packet Radio Markov Model}$$
\par
We make a restrictive model, which we hope will include only the effects
of CSMA and not the 2211 modems we all use.  Our model is
\par
1) Nodes schedule transmissions to neighbors, that is they can hear each
other,
according to a independent Poisson point processes.  The arrival times
of crashes on 75 meters on a summer night is modeled by a Poisson point
process quite well.
\par
2) Packet lengths are exponentially distributed and are generated independently
at each transmission.  This can be greatly relaxed but we will not do so here.
\par
3) The propagation delay between adjacent nodes is zero.\par
4) Under CSMA, we will begin our scheduled transmission if we are neither
sending or receiving or hearing a packet.\par
5) Nodes receive with perfect capture.  A bad assumption that allows us to
do the mathematics that follows.  This means if A transmits to B and then
during this transmission a neighbor of B, node C, begins to transmit,
node B still receives A's transmission.  Thus the collision only happens
if the recipient of C's packet can hear the A node transmission.  In this
case, C must retransmit.\par
6) Links are error free (2211's and MF-10's and OUR radios????). Again this
assumption is to allow ease of mathematical modeling and will result in
an over-estimate of the throughput.\par
7) Acks always make it and in zero time. (Chuckle Chuckle).
The obvious inadequacies of this model are clearly being VERY generous to
our physical links and are designed to ``single out'' the CSMA component
of the throughput of our networks.\par
$$\hbox{CSMA-Markov Chain Analysis}$$
Let $s_{ij}$ be the desired rate of transmission from Node i to Node j.
Let $i$ be a node, $N_i$ all the neighbors of $i$ and $N^*_i$ be $N_i$
and $i$.   Let $g_{ij}$ be the scheduled packet rates.  In order to achieve
$s_{ij}$, we must have $g_{ij}\ge s_{ij}$.  Let $P(A)$ be the probability
that all the nodes in a set $A$ are not transmitting at a random instant
(idle).
In the steady state, $P(A)$ represents a time average.  A scheduled packet
from $i$ to $j$ will be sucessful if it finds the system in a state whereby
both neighborhoods of $i$ and $j$ are idle.  Therefore, the important
quantity in determining the throughput will be $P(A)$.  Since Poisson
arrivals see time averages,
$${s_{ij}\over g_{ij}}= P(N_j \cup N_i)\eqno(1)$$
Let $g_i$ be the total shceduling rate out of node $i$ and let $1/\mu_i$
be the average length of packets generated by $i$.
$$g_i=\sum_{j\in N_i} g_{ij}\eqno(2)$$
The Markov model we choose has as its state the set of nodes transmitting.
Let $D$ be this active or busy set. $D^c$ is the idle node set.  The set
$D$ provides enough information about legal transitions which are either
completions of a transmission with exponential rates $\mu_i$ for $i \in D$
or new transmission rates $g_j$ for $j\not\in D$ and $j\not\in N_i,i\in D$.
The latter condition results from the CSMA zero propagation delay
assumption.\par
CSMA forces the nodes in $D$ to be unconnected.  Let $N_D$ denote the set of
all neighbors of nodes in $D$ and $D$ itself.  Let $D+j$, $D-i$ be independent
or unconnected sets formed by adding or subtracting a node from $D$.  Assume
that the network is stable for rates $g_i$ and $\mu_i$.  Then the steady-state
probabilities $Q(D)$ of states $D$ follow the global balance equations
$$\eqalign{\left( \sum_{j\in D}\mu_i + \sum_{j\not\in N_D}g_j\right) Q(D) &=
\sum_{i\in D}g_i Q(D-i)\cr
&+\,\sum_{j\not\in N_D}Q(D+j)\cr}.\eqno(3)$$
It follows that
$$Q(D)=\left(\pi_{i\in D} {g_i\over\mu_i}\right) Q(\phi).\eqno(4)$$
$Q(\phi)$ is the probability that all nodes are idle.  Normalizing this
to unit mass we get
$$Q(\phi)=\left[\sum_{\hbox{all } D}\prod_{i\in D}
{g_i\over\mu_i}\right]^{-1}.
\eqno(5)$$
For this Markov Chain to have a steady state the null transmitter state must
be positive recurrent $Q(\phi)>0$.  Finding all the independent sets $D$ for
equation 5 is an NP-complete problem.  There is a very clever algorithm
which allows the special structure of this formulation to be applied 
to networks of the size already mentioned.  To find the throughput, we
need the probabilities of being idle $P(A)$.  Clearly this is found by summing
$Q(D)$ over all $D$ that are contained completely in $A^c$ the compliment
of $A$.
$$P(A)=\sum_{D\subset A^c} Q(D)\eqno(6)$$
Let $$SP(B)=\sum_{D\subset B}\left(\prod_{i\in D}g_i/\mu_i\right),\quad
SP(\phi)\equiv 1.\eqno(7)$$
$$P(A)=SP(A^c)/SP(V)\eqno(8)$$
where $V$ is the set of all nodes.
Also
$${s_{ij}\over g_{ij}}={SP([N_i\cup N_j]^c)\over SP(V)}, j\in N_i.\eqno(9)$$
We solve (9) iteratively for the $g_{ij}$ and the throughput is identified
in the steady state under this model.  An analysis of the
very simple network with four nodes in a linear topology is accomplished
in several papers found in the bibliography in [1].
We used it to check out our program.
The results are somewhat astounding.  Given the four node linear topology with
our convenient assumptions we get that the max throughput in the network
occurs when the scheduling rate divided by the mean packet length
$g_1/\mu_1$=0.71.  This maximum throughput is 0.128 packets per second.
In a star topology with four legs and only five nodes in each leg the
mean maximum one-way throughput was 0.054 packets per second.  In a ring
with 5 nodes the max throughput is 0.100 packets per second.  As my
final run, I took a map of EASTNET done by Zwirko, K1HTV, and under generous
assumptions let the rate $s_{ij}$ correspond to 1200 bps and assumed the
mean packet length was 80 characters (a line).  Using the 40 most important
sites (subjective opinion) and going by word of mouth as to who had solid
links, I let the algorithm crunch for a while.
You are getting a maximum rate for each end to end requirement of 0.000534
packets/second.  With 40*39 identical requirements (neglecting the
W3IWI type choke points) this gives a network capacity of 0.833 packets
per second or 9 million characters per day.  This is of course awful.
The most general network that can be
analyzed by this technique is contained in the following \par
{\it Theorem}:  The product form throughput evaluation and the computational
procedure in Markovian CSMA networks with perfect capture and exponential
packet length hold for arbitrary packet length distributions having rational
Laplace transforms which need not be the same for all neighbors of a node.
The analysis depends on the average normalized scheduling rate of nodes,
independent of particular packet length distributions.\par
The bottom line is pretty clear.  We have been overly generous to the
network in that we neglected the real world of 0.08 bit/Hz modems run
through VERY poorly equalized radios and we didn't even clobber the returning
acks!!  We {\bf MUST} move to BTMA or some similar scheme before we grow any
larger.
\bigskip
\hangindent 0.2in
\noindent
[1] Boorstyn, R.R., et.al, ``Throughput Analysis in CSMA Packet Radio
Networks'', {\it IEEE Transactions on Communications}, Vol. COM-35, No.3,
March 1987.
\end
