\documentclass[11pt]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{2mm}
\setlength{\columnseprule}{0.4pt}  

\usepackage{times}
\usepackage{psfig}
\usepackage{fancyheadings}

\begin{document}

\pagestyle{fancy}
\cfoot{TDM: \thepage}    

\title{Time-Division Multiplexing}

\author{Norman Matloff \\
\\
University of California at Davis
}

\date{May 24, 1999}

\maketitle

\section{Overview}

The term {\bf multiplexing}, in a computer networks context, refers to
the sharing of a point-to-point communications line.  In {\bf
frequency-division} multiplexing (FDM), the different sources attached
to the line send on different frequencies.  In {\bf time-division}
multiplexing (TDM), different sources transmit on the line at different
times.  The latter type of multiplexing will be our focus here.

\section{Synchronous TDM}

At one end of the point-to-point line we have n source nodes.  Messages from
these sources are {\bf multiplexed} onto the line: The n sources
continually send in {\bf Round Robin} fashion, meaning that they take
turns:  Source node 0 sends, then source node 1, then source node 2,...,
then source node n-1, then source node 0, then source node 1, and so on.
Each cycle of n transmissions (one from each source, starting with
source node 0) is called a {\bf frame}.  The hardware that does the
multiplexing is called, not surprisingly, a {\bf multiplexer}.

At the other end of the line there may be a host computer, in which
case the n sources are typically terminals.  Or there may be a 
{\bf demultiplexer} at the destination end, distributing the messages
from the n sources to n destination entities.

Each source sends the same amount of data---typically set at one byte or
one bit---per turn.  This way the destination end of the line knows
whose data is arriving at any given time.  If the unit of data is bytes,
for instance, then you know that any byte which arrives at time k, where
k mod n = 5, is from source node 5.

A specific example is the T1 lines which are common for long-distance
communication in North America.  Here n = 24 and the unit of data is
bytes.  Thus there should be $24 \times 8 = 192$ bits sent on the line
per frame.\footnote{Plus one more bit, to be described below.}  

We say that a T1 line consists of 24 {\bf channels} of one byte
each.\footnote{This is the analog of channels in FDM.  The frequency
spectrum for television, for instance, is divided into subranges called
channels, and these correspond to our household notion of TV channels.
In TDM, we are dividing time instead of frequency range.}  For instance,
the totality of all the third bytes from all frames---that is, all the
bytes sent by the third source---would be called channel 2 (the first
one being numbered 0).

Suppose a channel is used for voice transmission, sampled at regular
intervals and digitized.  The sample taken at any given time consists of
the numerical value of the loudness of the sound at that time, which we
represent as an 8-bit number, i.e. one byte.  Recall that the bandwidth
of human voice is about 4 KHz.  One can prove that this means we need
to sample at $2 \times 4,000 = 8,000$ times per second to accurately
capture the voice signal.  So, on a T1 line we must send 8,000 frames
per second, thus $8,000 \times 192$ or 1.54 million bits per second.

What if instead we use some or all of the channels to transmit data?
T1 lines are set up to send 7-bit sets instead of bytes, with the
eighth bit used for encoding control information.  Thus we are sending
56,000 bits per second on each channel.

However, since the clock at the source-end multiplexer will not exactly
match that of the destination end, some drift will occur between them.
Eventually the destination end will drift ahead of or behind the sources
by one entire bit's duration of time, resulting in reception of wrong
data.  Thus each frame has an extra bit for {\bf synchronization}
purposes, so that the two ends can synchronize their clocks at regular
intervals.  In T1 lines, then, this will be the 193rd bit in each
frame.  The totality of these bits is then called the {\bf control
channel}.  In it the transmitter will send the repeating pattern
101010101...  If the receiver receives a 0 on that channel when it
is expecting a 1, or vice versa, the receiver will know that it has,
literally, ``gone out of sync''; it will then have to look at several
subsequent frames for the 1010101... sequence before getting back on
track.

Each channel will operate its own HDLC process, independent of the
others, to set up sliding-window operations and so on, though of course
not for clock synchronization.

\section{Statistical TDM}

\subsection{Basic Structure}

The problem with synchronous TDM is that some source nodes may sometimes
have nothing to send; they simply are idle during turns when they have
nothing to send.  This of course wastes the line, which may be leased at
a very expensive rate.

{\bf Statistical} TDM remedies this by allowing a source node to skip
its turn in such a situation.  Each time a node has something to send,
it places the item on a first-in, first-out (FIFO) queue into the
multiplexer.  This approach makes better use of the line's bandwidth.
Of course we do pay a price, in the sense that each source now must
sent its source number in addition to the data, so that the receiver
on the other end of the line can determine who sent the data.  Thus
part of the line's capacity will be used for sending these source
numbers, which we did not have in the synchronous TDM case.

\subsection{Analysis}

(This material is adapted from {\it Data and Computer Communications},
by William Stallings, fourth edition, pub. by Macmillan, 1994, and {\it
Data Networks}, by Ulysses Black, pub. by Prentice Hall, 1989.)

Earlier we had presented statistical TDM as a way to make better use of
an existing line, but the principle also means that statistical TDM
allows us to get the same performance while using a slower line.  If it
is a phone line, the leasing cost will be cheaper.  Suppose each of our
n sources transmits (when it is transmitting) at a rate of r bits per
second.  In synchronous TDM, we would need a line of rate nr, but with
statistical TDM we can get by with a line of rate $m < nr$.  Assuming
the cost of the line is proportional to its bit rate, let k denote the
degree of cost savings, that is 

\begin{equation}
k = m/(nr), 
\end{equation}

where m is the bit rate of the cheaper line.  By definition, $k \le 1$.  

Let $\alpha$ denote the mean fraction of the time each source node
spends transmitting.\footnote{The word ``mean'' here alludes to the fact
that a given source node will have data to transmit at random times.
During some periods it will be transmitting continously, other times
sporadically.}  Then the mean number of bits per second put onto the
line will be $nr\alpha$, which must be less than or equal to m
(otherwise, the FIFO queue will grow to infinity).  So,

\begin{equation}
\alpha \le k \le 1
\end{equation}

One drawback of statistical TDM is that we have to set up buffer
space for the queue, which we would not have to do in the synchronous
case.  How much buffer space do we need?  To get an idea of this, let
us ask instead what the mean queue length would be if there were 
unlimited buffer space.

Assume that the basic unit sent out per turn for each station is one
bit.  So, the time needed per turn is a constant, specifically 1/m.
If the times between arrivals to the queue have an exponential
distribution, it can be shown that q, the mean number of bits in the
queue is

\begin{equation}
q = \rho + \frac{\rho ^ 2}{2 ( 1 - \rho )},
\end{equation}

where $\rho$ is the fraction of time the muliplexer is busy:

\begin{equation}
\rho = \frac{nr\alpha}{m}
\end{equation}

As can be seen by the above equation for q, as $\rho$ gets near 1,
the graph of q against $\rho$ begins to have an extremely steep slope.
That indicates that since we have only finite buffer space, a value of
$\rho$ near 1 will lead to either very large buffer requirements or
a high probability of buffer overflow resulting in lost bits.

Let w be the mean time a bit waits in the queue.  When a ``typical''
bit arrives at the queue, it will find, on average, q bits waiting
ahead of it.   Each of those q bits will take 

\begin{equation}
q \times {1 \over m}
\end{equation} 

time to transmit, so 

\begin{equation}
w = \frac{1}{m} ( \rho + \frac{\rho ^ 2}{2 (1 - \rho) } )
\end{equation}

So we can see that if $\rho$ is near 1, we will also have the problem
of long delays.

\end{document}