STATISTICAL TIME DIVISION MULTIPLEXING

STATISTICAL TIME DIVISION MULTIPLEXING

Characteristics

In a synchronous time-division multiplexer, it is generally the case that many of the

time slots in a frame are wasted. A typical application of a synchronous TDM

involves linking a number of terminals to a shared computer port. Even if all terminals

are actively in use, most of the time there is no data transfer at any particular

terminal.

An alternative to synchronous TDM is statistical TDM, also known as asynchronous

TDM and intelligent TDM. The statistical multiplexer exploits this common

property of data transmission by dynamically allocating time slots on demand.

As with a synchronous TDM, the statistical multiplexer has a number of I10 lines

on one side and a higher-speed multiplexed line on the other. Each I10 line has a

buffer associated with it. In the case of the statistical multiplexer, there are n 110

lines, but only k, where k < n, time slots available on the TDM frame. For input,

the function of the multiplexer is to scan the input buffers, collecting data until a

frame is filled, and then send the frame. On output, the multiplexer receives a frame

and distributes the slots of data to the appropriate output buffers.

Because statistical TDM takes advantage of the fact that the attached devices

are not all transmitting all of the time, the data rate on the multiplexed line is less

than the sum of the data rates of the attached devices. Thus, a statistical multiplexer

can use a lower data rate to support as many devices as a synchronous multiplexer.

Alternatively, if a statistical multiplexer and a synchronous multiplexer both use a

link of the same data rate, the statistical multiplexer can support more devices.

Figure 7.14 contrasts statistical and synchronous TDM. The figure depicts four

data sources and shows the data produced in four time epochs (to, t1, t2, t3). In the

case of the synchronous multiplexer, the multiplexer has an effective output rate of

four times the data rate of any of the input devices. During each epoch, data are collected

from all four sources and sent out. For example, in the first epoch, sources C

and D produce no data. Thus, two of the four time slots transmitted by the multiplexer

are empty.

In contrast, the statistical multiplexer does not send empty slots if there are

data to send. Thus, during the first epoch, only slots for A and B are sent. However,

the positional significance of the slots is lost in this scheme. It is not known ahead

of time which source's data will be in any particular slot. Because data arrive from

and are distributed to I10 lines unpredictably, address information is required to

assure proper delivery. As a result, there is more overhead per slot for statistical

TDM as each slot carries an address as well as data.

The frame structure used by a statistical multiplexer has an impact on performance.

Clearly, it is desirable to minimize overhead bits to improve throughput.

Generally, a statistical TDM system will use a synchronous protocol such as HDLC.

Within the HDLC frame, the data frame must contain control bits for the multiplexing

operation. Figure 7.15 shows two possible formats. In the first case, only one

source of data is included per frame. That source is identified by an address. The

length of the data field is variable, and its end is marked by the end of the overall

frame. This scheme can work well under light load, but is quite inefficient under

heavy load.

A way to improve efficiency is to allow multiple data sources to be packaged

in a single frame. Now, however, some means is needed to specify the length of data

for each source. Thus, the statistical TDM subframe consists of a sequence of data

fields, each labeled with an address and a length. Several techniques can be used to

make this approach even more efficient. The address field can be reduced by using

relative addressing. That is, each address specifies the number of the current source

relative to the previous source, modulo the total number of sources. So, for example,

instead of an 8-bit address field, a 4-bit field might suffice.

Another refinement is to use a two-bit label with the length field. A value of

00,01, or 10 corresponds to a data field of one, two, or three bytes; no length field

is necessary. A value of 11 indicates that a length field is included.

Performance

FCS

We have said that the data rate of the output of a statistical multiplexer is less than

the sum of the data rates of the inputs. This is allowable because it is anticipated

that the average amount of input is less than the capacity of the multiplexed line.

The difficulty with this approach is that, while the average aggregate input may be

less than the multiplexed line capacity, there may be peak periods when the input

exceeds capacity.

The solution to this problem is to include a buffer in the multiplexer to hold

temporary excess input. Table 7.6 gives an example of the behavior of such systems.

We assume 10 sources, each capable of 1000 bps, and we assume that the average

input per source is 50% of its maximum. Thus, on average, the input load is

5000 bps. Two cases are shown: multiplexers of output capacity 5000 bps and

7000 bps. The entries in the table show the number of bits input from the 10 devices

each millisecond and the output from the multiplexer. When the input exceeds the

output, backlog develops that must be buffered.

There is a trade-off between the size of the buffer used and the data rate of

the line. We would like to use the smallest possible buffer and the smallest possible

data rate, but a reduction in one requires an increase in the other. Note that we are

not so much concerned with the cost of the buffer-memory is cheap-as we are

with the fact that the more buffering there is, the longer the delay. Thus, the tradeoff

is really one between system response time and the speed of the multiplexed

line. In this section, we present some approximate measures that examine this

trade-off. These are sufficient for most purposes.

Let us define the following parameters for a statistical time-division multiplexer:

N = number of input sources

K = data rate of each source, bps

M = effective capacity of multiplexed line, bps

a = mean fraction of time each source is transmitting, 0 < a < 1

K M = - = ratio of multiplexed line capacity to total maximum input NR

In the above, we have defined M taking into account the overhead bits introduced

by the multiplexer. That is, M represents the maximum rate at which data bits

can be transmitted.

The parameter K is a measure of the compression achieved by the multiplexer.

For example, for a given data rate M, if K = 0.25, there are four times as

many devices being handled as by a synchronous time-division multiplexer using

the same link capacity. The value of K can be bounded:

A value of K = 1 corresponds to a synchronous time-division multiplexer, as the

system has the capacity to service all input devices at the same time. If K < a, the

input will exceed the multiplexer's capacity.

Some results can be obtained by viewing the multiplexer as a single-server

queue. A queuing situation arises when a "customer" arrives at a service facility

and, finding it busy, is forced to wait. The delay incurred by a customer is the time

spent waiting in the queue plus the time for the service. The delay depends on the

pattern of arriving traffic and the characteristics of the server. Table 7.7 summarizes

results for the case of random (Poisson) arrivals and constant service time. This

model is easily related to the statistical multiplexer:

Figure 7.16 gives some insight into the nature of the trade-off between system

response time and the speed of the multiplexed line. It assumes that data are being

transmitted in 1000-bit frames. ~ a r t t ao)f the figure shows the average number of

frames that must be buffered as a function of the average utilization of the multiplexed

line. The utilization is expressed as a percentage of the total line capacity.

Thus, if the average input load is 5000 bps, the utilization is 100 percent for a line

capacity of 5000 bps and about 71 percent for a line capacity of 7000 bps. Part (b)

of the figure shows the average delay experienced by a frame as a function of utilization

and data rate. Note that as the utilization rises, so do the buffer requirements

and the delay. A utilization above 80 percent is clearly undesirable.

Note that the average buffer size being used depends only on p, and not

directly on M. For example, consider the following two cases:

In both cases, the value of p is 0.8 and the mean buffer size is 2.4. Thus, proportionately,

a smaller amount of buffer space per source is needed for multiplexers

that handle a larger number of sources. Figure 7.16b also shows that the average

delay will be smaller as the link capacity increases, for constant utilization.

So far, we have been considering average queue length, and, hence, the average

amount of buffer capacity needed. Of course, there will be some fixed upper

bound on the buffer size available. The variance of the queue size grows with utilization.

Thus, at a higher level of utilization, a larger buffer is needed to hold the

backlog. Even so, there is always a finite probability that the buffer will overflow.

Figure 7.17 shows the strong dependence of overflow probability on utilization.

This figure, plus Figure 7.16, suggest that utilization above about 0.8 is undesirable.