Data Communications and Networking

Multiple Access
In the previous part we discussed data link control, a mechanism which provides a
link with reliable communication. In the protocols we described, we assumed that there is
an available dedicated link (or channel) between the sender and the receiver. This
assumption may or may not be true. If, indeed, we have a dedicated link, as when we
connect to the Internet using PPP as the data link control protocol, then the assumption is
true and we do not need anything else.
On the other hand, if we use our cellular phone to connect to another cellular
phone, the channel (the band allocated to the vendor company) is not dedicated. A person
a few feet away from us may be using the same channel to talk to anybody else.
We can consider the data link layer as two sublayers. The upper sublayer is
responsible for data link control, and the lower sublayer is responsible for resolving
access to the shared media. If the channel is dedicated, we do not need the lower
sublayer. Figure 1 shows these two sublayers in the data link layer.

Figure 1: Data link layer divided into two functionality-oriented sublayers

The upper sublayer that is responsible for flow and error control is called the
logical link control (LLC) layer; the lower sublayer that is mostly responsible for
multiple-access resolution is called the media access control (MAC) layer.
When nodes or stations are connected and use a common link, called a multipoint
or broadcast link, we need a multiple-access protocol to coordinate access to the link. The
problem of controlling the access to the medium is similar to the rules of speaking in an
assembly. The procedures guarantee that the right to speak is upheld and ensure that two

1
Data Communications and Networking

people do not speak at the same time, do not interrupt each other, do not monopolize the
discussion, and so on.
The situation is similar for multipoint networks. Many formal protocols have been
devised to handle access to a shared link. We categorize them into three groups. Protocols
belonging to each group are shown in Figure 2.

Figure 2: Taxonomy of multiple-access protocols discussed in this part

1. RANDOM ACCESS
In random access or contention methods, no station is superior to another station
and none is assigned the control over another. No station permits, or does not permit,
another station to send. At each instance, a station that has data to send uses a procedure
defined by the protocol to make a decision on whether or not to send. This decision
depends on the state of the medium (idle or busy). In other words, each station can
transmit when it desires on the condition that it follows the predefined procedure,
including the testing of the state of the medium.
Two features give this method its name. First, there is no scheduled time for a
station to transmit. Transmission is random among the stations. That is why these
methods are called random access. Second, no rules specify which station should send
next. Stations compete with one another to access the medium. That is why these
methods are also called contention methods.
In a random access method, each station has the right to the medium without
being controlled by any other station. However, if more than one station tries to send,

2
Data Communications and Networking

there is an access conflict--collision--and the frames will be either destroyed or modified.

To avoid access conflict or to resolve it when it happens, each station follows a procedure
that answers the following questions:

 When can the station access the medium?

 What can the station do if the medium is busy?
 How can the station determine the success or failure of the transmission?
 What can the station do if there is an access conflict?

The random access methods we study in this part have evolved from a very
interesting protocol known as ALOHA, which used a very simple procedure called
multiple access (MA). The method was improved with the addition of a procedure that
forces the station to sense the medium before transmitting. This was called carrier sense
multiple access. This method later evolved into two parallel methods: carrier sense
multiple access with collision detection (CSMA/CD) and carrier sense multiple access
with collision avoidance (CSMA/CA). CSMA/CD tells the station what to do when a
collision is detected. CSMA/CA tries to avoid the collision.

ALOHA
ALOHA, the earliest random access method, was developed at the University of
Hawaii in early 1970. It was designed for a radio (wireless) LAN, but it can be used on
any shared medium.
It is obvious that there are potential collisions in this arrangement. The medium is
shared between the stations. When a station sends data, another station may attempt to do
so at the same time. The data from the two stations collide and become garbled.

Pure ALOHA
The original ALOHA protocol is called pure ALOHA. This is a simple, but
elegant protocol. The idea is that each station sends a frame whenever it has a frame to
send. However, since there is only one channel to share, there is the possibility of
collision between frames from different stations. Figure 4.3 shows an example of frame
collisions in pure ALOHA.

3
Data Communications and Networking

Figure 3: Frames in a pure ALOHA network

There are four stations (unrealistic assumption) that contend with one another for
access to the shared channel. The figure shows that each station sends two frames; there
are a total of eight frames on the shared medium. Some of these frames collide because
multiple frames are in contention for the shared channel. Figure 3 shows that only two
frames survive: frame 1.1 from station 1 and frame 3.2 from station 3. We need to
mention that even if one bit of a frame coexists on the channel with one bit from another
frame, there is a collision and both will be destroyed.

It is obvious that we need to resend the frames that have been destroyed during
transmission. The pure ALOHA protocol relies on acknowledgments from the receiver.
When a station sends a frame, it expects the receiver to send an acknowledgment. If the
acknowledgment does not arrive after a time-out period, the station assumes that the
frame (or the acknowledgment) has been destroyed and resends the frame.
A collision involves two or more stations. If all these stations try to resend their
frames after the time-out, the frames will collide again. Pure ALOHA dictates that when
the time-out period passes, each station waits a random amount of time before resending
its frame. The randomness will help avoid more collisions. We call this time the back-off
time.

4
Data Communications and Networking

Pure ALOHA has a second method to prevent congesting the channel with
retransmitted frames. After a maximum number of retransmission attempts, a station
must give up and try later.

Slotted ALOHA
In Pure ALOHA there is no rule that defines when the station can send. A station
may send soon after another station has started or soon before another station has
finished. Slotted ALOHA was invented to improve the efficiency of pure ALOHA.
In slotted ALOHA we divide the time into slots of the average time required to send out a
frame, and force the station to send only at the beginning of the time slot. Figure 4.4
shows an example of frame collisions in slotted ALOHA.

Figure 4.4: Frames in a slotted ALOHA network

Because a station is allowed to send only at the beginning of the synchronized

time slot, if a station misses this moment, it must wait until the beginning of the next time
slot. This means that the station which started at the beginning of this slot has already
finished sending its frame. Of course, there is still the possibility of collision if two
stations try to send at the beginning of the same time slot. Now, you can compare the
number of received frames in the pure ALOHA and slotted ALOHA and then decide
which one in more efficient!

5
Data Communications and Networking

Carrier Sense Multiple Access (CSMA)

To minimize the chance of collision and, therefore, increase the performance, the
CSMA method was developed. The chance of collision can be reduced if a station senses
the medium before trying to use it. Carrier sense multiple access (CSMA) requires that
each station first listen to the medium (or check the state of the medium) before sending.
In other words, CSMA is based on the principle "sense before transmit" or "listen before
talk."

CSMA can reduce the possibility of collision, but it cannot eliminate it. The
possibility of collision still exists because of propagation delay; when a station sends a
frame, it still takes time (although very short) for the first bit to reach every station and
for every station to sense it. In other words, a station may sense the medium and find it
idle, only because the first bit sent by another station has not yet been received.

The vulnerable time for CSMA is the propagation time, which is the time needed
for a signal to propagate from one end of the medium to the other. When a station sends a
frame, and any other station tries to send a frame during this time, a collision will result.
But if the first bit of the frame reaches the end of the medium, every station will already
have heard the bit and will not send its own frame.

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

The CSMA method does not specify the procedure following a collision. Carrier
sense multiple access with collision detection (CSMA/CD) augments the algorithm to
handle the collision.
In this method, a station monitors the medium after it sends a frame to see if the
transmission was successful. If so, the station is finished. If, however, there is a collision,
the frame is sent again.
To better understand CSMA/CD, let us look at the first bits transmitted by the two
stations involved in the collision. Although each station continues to send bits in the
frame until it detects the collision, we show what happens as the first bits collide. In
Figure 5, stations A and C are involved in the collision.

6
Data Communications and Networking

Figure 5: Collision of the first bit in CSMA/CD

At time tl, station A has executed its persistence procedure and starts sending the
bits of its frame. At time t2, station C has not yet sensed the first bit sent by A. Station C
executes its persistence procedure and starts sending the bits in its frame, which
propagate both to the left and to the right. The collision occurs sometime after time t2.
Station C detects a collision at time t3 when it receives the first bit of A's frame. Station
C immediately (or after a short time, but we assume immediately) aborts transmission.
Station A detects collision at time t4 when it receives the first bit of C's frame; it also
immediately aborts transmission. The throughput of CSMA/CD is greater than that of
pure or slotted ALOHA.

Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

The basic idea behind CSMA/CD is that a station needs to be able to receive
while transmitting to detect a collision. The probability of collision to be happened with
CSMA/CD is reduced, but it still exits. We need to avoid collision on networks because
sometimes it cannot be detected (especially in wireless networks). Carrier sense multiple
access with collision avoidance (CSMA/CA) was invented for this purpose. Collisions
are avoided through the use of CSMA/CA's three strategies: the interframe space, the
contention window, and acknowledgments. With this method when an idle channel is
found, the station does not send immediately. It waits for a period of time called the
interframe space or IFS. If after the IFS time the channel is still idle, the station can send,
but it still needs to wait a time equal to the contention time. The contention time is an

7
Data Communications and Networking

amount of time divided into slots. A station that is ready to send chooses a random
number of slots as its wait time. With all these precautions, there still may be a collision
resulting in destroyed data. In addition, the data may be corrupted during the
transmission. The positive acknowledgment and the time-out timer can help guarantee
that the receiver has received the frame.