INTRODUCTION TO DATA COMMUNICATION
transmitter and their are some buffers between the sources and the transmitter where data can be
Whenever the line is idle the transmitter can select a source and transmit data contained in its
buffer, together with addressing information. The transmitter faces two related questions: should
data be transmitted at all, and if so, from what source? Also, how should the fact that data is
being transmitted and the source identity be communicated to the receiver?
This formulation lacks an optimality criterion. Reasonable candidates would be to minimize
the expected number of overhead bits, or to minimize the expected delay suffered by the data.
Solutions to these questions are not easy, although attempts have been made by using queueing
and information theories  . Some understanding of the tradeoffs involved is possible.
Consider the policy known as synchronous time division multiplexing, where the transmitter divides
time in equal slots and scans all the buffers cyclically, transmitting data from a source only during
its assigned slots. No explicit address information is communicated to the receiver, but the system
causes unnecessarily long delays when they are many sources and traffic is light. Data waits for its
slot to come, while typically empty slots are being transmitted!
At the other extreme data could be sent in first come first served order, each being prefixed
with the explicit address of its source (essentially forming packets). This scheme results in small
delays in light traffic, but can be terrible in heavy traffic due to the effects of the addressing
From these examples it is clear that overhead information can be treated off for delay. This
was pointed out in . Further studies  have shown that protocols of the first type should be
used when the number M of sources is much smaller than the expected number of bits N waiting
in buffers. When M is much smaller than N the second type of protocol is excellent. What to do
in the intermediate region is not clear.
Let us now introduce a second problem that has generated much excitement recently. It is
known as the ALOHA channel problem, having originated in Hawaii. Again there are M sources
producing data and sharing a communication channel. The novelty is that no single device can
observe the state of all the buffers. Rather the sources can transmit whenever they wish and can
also observe the outcomes of all transmissions. These may be "idle" if no one transmits, "success",
or "collision" if more than one source transmit. All collided messages must be retransmitted. This
is a fair model of some radio and cable communication systems that are now in use.