Unit 3:

Data link layer: Error Detection and Correction, Framing, flow and error control, Protocols - Noiseless channels (Simplest, Stop and Wait)
and Noisy channels (Stop and Wait and Piggy Backing).

Multiple Access Protocols. Random Access-ALOHA, CSMA.

Wired LANs-IEEE standards, wireless LANs-Bluetooth, Cellular Telephony .

1. Multiple Access Protocols.

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.
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
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.

2. Random Access Protocols.

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 tests the state of the medium.
 In a random access method, each station has the right to the medium without being
controlled by any other station.
 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).
 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.)

Department of Computer Applications, NSS College Rajakumari 1

  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.)
 If more than one station tries to send, there is an access conflict-collision-and the
frames will be either destroyed or modified.
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.
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.
The idea is that each station sends a frame whenever it has a frame to send.
Since there is only one channel to share, there is the possibility of collision between frames
from different stations.
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.
Pure ALOHA has a second method to prevent congesting the channel with retransmitted
frames. After a maximum number of retransmission attempts ( Kmax' ) a station must give up
and try later.

Department of Computer Applications, NSS College Rajakumari 2

 The time-out period is equal to the maximum possible round-trip propagation delay, which is
twice the amount of time required to send a frame between the two most widely separated
stations (2 x Tp)' The back-off time TB is a random value that normally depends on K (the
number of attempted unsuccessful transmissions). The formula for TB depends on the
implementation. One common formula is the binary exponential back-off. In this
method, for each retransmission, a multiplier in the range 0 to 2K - 1 is randomly chosen and
multiplied by Tp (maximum propagation time) or Trr (the average time required to send out
a frame) to find TB' Note that in this procedure, the range of the random numbers increases
after each collision. The value of Kmax is usually chosen as 15.
Vulnerable time Let us find the length of time, the vulnerable time, in which there is a
possibility of collision. We assume that the stations send fixed-length frames with each
frame taking Tfr to send.

Vulnerable time, during which a collision may occur in pure ALOHA, is 2 times the frame
transmission time.
Pure ALOHA vulnerable time= 2 x Tfr

Throughput Let us call G the average number of frames generated by the system during
one frame transmission time. Then it can be proved that the average number of successful
transmissions for pure ALOHA is S = G x e-2G. The maximum throughput Smax is 0.184, for
G = 1. In other words, if one-half a frame is generated during one 2 frame transmission time
(in other words, one frame during two frame transmission times), then 18.4 percent ofthese
frames reach their destination successfully. This is an expected result because the vulnerable
time is 2 times the frame transmission time. Therefore, if a station generates only one frame
in this vulnerable time (and no other stations generate a frame during this time), the frame
will reach its destination successfully.

 The throughputfor pureALOHA is S =G x e-2G.

 The maximum throughput Smax =0.184 when G=(1/2).

SlottedALOHA
Pure ALOHA has a vulnerable time of 2 x Tfr. This is so because 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 Tfr s and force the
station to send only at the beginning of the time slot. Figure shows an example of frame
collisions in slotted ALOHA.

Department of Computer Applications, NSS College Rajakumari 3

 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. However, the vulnerable time is now reduced to one-half,
equal to Tfr
 Vulnerable time for slotted ALOHA is one-half that of pure ALOHA.
 SlottedALOHA vulnerable time =Tfr
Throughput It can be proved that the average number of successful transmissions for
slotted ALOHA is S = G x e-G. The maximum throughput Smax is 0.368, when G = 1. In
other words, if a frame is generated during one frame transmission time, then 36.8 percent of
these frames reach their destination successfully. This result can be expected because the
vulnerable time is equal to the frame transmission time. Therefore, if a station generates only
one frame in this vulnerable time (and no other station generates a frame during this time),
the frame will reach its destination successfully.
 The throughputfor slottedALOHA is S =: G x e-G.
 The maximum throughputSmax == 0.368 when G=1.

CSMA.
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."
Carrier-sense multiple access (CSMA) is a media access control (MAC) protocol in which a node
verifies the absence of other traffic before transmitting on a shared transmission medium, such as
an electrical bus or a band of the electromagnetic spectrum.
A transmitter attempts to determine whether another transmission is in progress before initiating a
transmission using a carrier-sense mechanism. That is, it tries to detect the presence of a carrier
signal from another node before attempting to transmit. If a carrier is sensed, the node waits for the
transmission in progress to end before initiating its own transmission. Using CSMA, multiple nodes
may, in turn, send and receive on the same medium. Transmissions by one node are generally
received by all other nodes connected to the medium.
Variations on basic CSMA include addition of collision-avoidance, collision-detection and collision-
resolution techniques.

Department of Computer Applications, NSS College Rajakumari 4

CSMA can reduce the possibility of collision, but it cannot eliminate it. Because, stations are
connected to a shared channel (usually a dedicated medium). 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. Because of the delay a station may sense the medium and find it
idle only because the first bit sent by another station has not yet been received.
Suppose at time t1 station B senses the medium and finds it idle, so it sends a frame. At time
t2 (t2> tI) station C senses the medium and finds it idle because, at this time, the first bits
from station B have not reached station C. Station C also sends a frame. The two signals
collide and both frames are destroyed.
Vulnerable Time
The vulnerable time for CSMA is the propagation time Tp . This 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 sense the medium as
busy and will refrain from sending.

Persistence Methods
Variations of CSMA use different algorithms to determine when to initiate transmission onto
the shared medium. A key distinguishing feature of these algorithms is how aggressive or
persistent they are in initiating transmission. A more aggressive algorithm may begin
transmission more quickly and utilize a greater percentage of available bandwidth of the
medium. This is typically at the expense of increased likelihood of collision with other
transmitters.
Three methods have been devised for the stations to follow when it finds the channel is buzy
or idle.
 the 1-persistent method,
 the nonpersistent method, and
 the p-persistent method.
1-Persistent
1-persistent CSMA is an aggressive transmission algorithm. When the transmitting node is
ready to transmit, it senses the transmission medium for idle or busy. If idle(channel is free
because no other station is transmitting), then it transmits immediately. If busy, then it senses
the transmission medium continuously until it becomes idle, then transmits the message
(a frame) unconditionally (i.e. with probability=1). In case of a collision, the sender waits for
a random period of time and attempts the same procedure again. 1-persistent CSMA is used
in CSMA/CD systems including Ethernet. This method has the highest chance of collision
because two or more stations may find the line idle and send their frames immediately.
Department of Computer Applications, NSS College Rajakumari 5
Nonpersistent
Non persistent CSMA is a non-aggressive transmission algorithm. When the transmitting
node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then
it transmits immediately. If busy, then it waits for a random period of time (during which it
does not sense the transmission medium) before repeating the whole logic cycle (which
started with sensing the transmission medium for idle or busy) again. This approach reduces
collision, results in overall higher medium throughput but with a penalty of longer initial
delay compared to 1–persistent. Thus this method reduces the efficiency of the network
because the medium remains idle(since stations are not sensing the medium during the
waiting period) when there may be stations with frames to send .

p-Persistent
The p-persistent method is used if the channel has time slots with a slot duration equal to or
greater than the maximum propagation time.
The p-persistent approach combines the advantages of the other two strategies. It reduces the
chance of collision and improves efficiency.

Department of Computer Applications, NSS College Rajakumari 6

If the station finds the line idle it follows these steps:
1. With probability p, the station sends its frame.
2. With probability q = 1 - p, the station waits for the beginning of the next time slot
and checks the line again.
a. If the line is idle, it goes to step 1.
b. If the line is busy, it acts as though a collision has occurred and uses the back-off
procedure.

In p-persistent CSMA, the letter “p” refers to the probability that a node having
communications traffic to send will start transmitting in a specific period of time following
the end of a received prior transmission. This is also referred to as the transmission
probability, with values ranging from 0 to 1. A system in which a node having traffic to send
always starts transmitting immediately once the prior transmission ends is an instance of 1-
persistent CSMA, indicating there is a 100% chance that an immediate transmission will take
place when a channel becomes idle. Waiting a random time before transmitting represents p-
persistent CSMA, which is intended to reduce the probability of transmission collisions by
giving different nodes different times at which they are permitted to start transmitting based
on the transmission probability “p”. Each node with traffic to send waits a random or pseudo-
random time before starting to transmit. The statistical distribution of the wait times is
determined by the value of the transmission probability, 'p'. As each node waits, it monitors
the channel. If it detects the start of another node's transmission before its own transmission
time arrives, it cancels or reschedules its own transmission so as to prevent the collision of
multiple transmissions on the shared medium that would otherwise occur.

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 finished its job. But if there is a collision the frame is sent
again.
Minimum Frame Size
For CSMA/CD to work, we need a restriction on the frame size. Before sending the last bit of
the frame, the sending station must detect a collision, if any, and abort the transmission. This
is so because the station, once the entire frame is sent, does not keep a copy of the frame and
Department of Computer Applications, NSS College Rajakumari 7
does not monitor the line for collision detection. Therefore, the frame transmission time
Tfr must be at least two times the maximum propagation time Tp. To understand the
reason, let us think about the worst-case scenario. If the two stations involved in a collision
are the maximum distance apart, the signal from the first takes time Tp to reach the second,
and the effect of the collision takes another time Tp to reach the first. So the requirement is
that the first station must still be transmitting after 2Tp.
Energy Level
We can say that the level of energy in a channel can have three values: zero, normal, and
abnormal. At the zero level, the channel is idle. At the normal level, a station has successfully
captured the channel and is sending its frame. At the abnormal level, there is a collision and
the level of the energy is twice the normal level. A station that has a frame to send or is
sending a frame needs to monitor the energy level to determine if the channel is idle, busy, or
in collision mode.
Throughput
The throughput of CSMA/CD is greater than that of pure or slotted ALOHA. The maximum
throughput occurs at a different value of G and is based on the persistence method
and the value of p in the p-persistent approach. For 1-persistent method the maximum
throughput is around 50 percent when G =1. For nonpersistent method, the maximum
throughput can go up to 90 percent when G is between 3 and 8.

Differences between ALOHA protocol and CSMA/CD

The first difference is the addition of the persistence process. We need to sense the channel
before we start sending the frame by using one of the persistence processes (nonpersistent, I-
persistent, or p-persistent). The second difference is the frame transmission. In ALOHA, we
first transmit the entire frame and then wait for an acknowledgment. In CSMA/CD,
transmission and collision detection is a continuous process. The third difference is the
sending of a short jamming signal that enforces the collision in case other stations have not
yet sensed the collision.

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

In a wired network in a collision, the detected signal energy is almost double. We need to
avoid collisions on wireless networks because they cannot be detected. Carrier sense multiple
access with collision avoidance (CSMAlCA) was invented for this network. Collisions are
avoided through the use ofCSMA/CA's three strategies: the interframe space(IFS), the
contention window, and acknowledgments.

Interframe Space (IFS)

First, collisions are avoided by deferring transmission even if the channel is found idle. 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. Even though the channel may appear idle when it is
sensed, a distant station may have already started transmitting. The distant station's signal has
not yet reached this station. The IFS time allows the front of the transmitted signal by the
distant station to reach this station. 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 (described next). The IFS
variable can also be used to prioritize stations or frame types. For example, a station that is
assigned a shorter IFS has a higher priority.

Contention Window

Department of Computer Applications, NSS College Rajakumari 8

The contention window is an amount of time divided into slots. A station that is ready to send
chooses a random number of slots as its wait time. The number of slots in the window
changes according to the binary exponential back-off strategy. This means that it is set to one
slot the first time and then doubles each time the station cannot detect an idle channel after
the IFS time.

Acknowledgment
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
can guarantee that the receiver has received the frame.

Department of Computer Applications, NSS College Rajakumari 9