UNIT-II

DATA LINK LAYER

The Data-link layer is the second layer from the bottom in the OSI (Open System
Interconnection) network architecture model. It is responsible for the node-to-node
delivery of data. Its major role is to ensure error-free transmission of information. DLL
is also responsible to encode, decode and organize the outgoing and incoming data.
This is considered the most complex layer of the OSI model as it hides all the
underlying complexities of the hardware from the other above layers.

Sub-layers of Data Link Layer:

The data link layer is further divided into two sub-layers, which are as follows:

Logical Link Control (LLC):

This sub layer of the data link layer deals with multiplexing, the flow of data among
applications and other services, and LLC is responsible for providing error messages
and acknowledgments as well.

Media Access Control (MAC):

MAC sub layer manages the device’s interaction, responsible for addressing frames,
and also controls physical media access.
The data link layer receives the information in the form of packets from the Network
layer; it divides packets into frames and sends those frames bit-by-bit to the underlying
physical layer.

Functions of the Data-link Layer:

1. Framing: The packet received from the Network layer is known as a frame inthe
Data link layer. At the sender’s side, DLL receives packets from the Network layer
and divides them into small frames, then, sends each frame bit-by-bit tothe
physical layer. It also attaches some special bits (for error control and addressing)
at the header and end of the frame. At the receiver’s end, DLL takes bits from the
Physical layer organize them into the frame, and sends them to the Network layer.

2. Addressing: The data link layer encapsulates the source and destination’s MAC
address/ physical address in the header of each frame to ensure node-to-node
delivery. MAC address is the unique hardware address that is assigned to the device
while manufacturing.
 3. Error Control: Data can get corrupted due to various reasons like noise,
attenuation, etc. So, it is the responsibility of the data link layer, to detect the error
in the transmitted data and correct it using errordetection and
correction techniques respectively. DLL adds error detection bits into the frame’s
header, so that receiver can check received data is correct or not.

4. Flow Control: If the receiver’s receiving speed is lower than the sender’s sending
speed, then this can lead to an overflow in the receiver’s buffer and some frames
may get lost. So, it’s the responsibility of DLL to synchronize the sender’s and
receiver’s speeds and establish flow control between them.

5. Access Control: When multiple devices share the same communication channel
there is a high probability of collision, so it’s the responsibility of DLL to check
which device has control over the channel and CSMA/CD and CSMA/CA can be
used to avoid collisions and loss of frames in the channel.

Data Link Layer Protocols

Traditionally 2 protocols have been defined for the data-link layer to deal with flow and error
control:

1. Simple Protocol and

2. Stop-and-Wait Protocol.

The behavior of a data-link-layer protocol can be better shown as a finite state machine (FSM). An
FSM is a machine with a finite number of states (Figure 11.6).

The machine is always in one of the states until an event occurs. Each event is associated with 2
reactions:

Defining the list (possibly empty) of actions to be performed.

Determining the next state (which can be the same as the current state).

One of the states must be defined as the initial state, the state in which the machine starts when it
turns on.
Simplest Protocol

Assumptions:
The protocol has no flow-control or error-control.
The protocol is a unidirectional protocol (in which frames are traveling in only one direction). The
receiver can immediately handle any frame it receives.

Design

At Sender
The data-link-layer gets data from its network-layer makes a frame out of the data and sends the
frame.

At Receiver
The data-link-layer
receives a frame from its physical layer extracts data from the frame and delivers the data to its
network-layer.
Data-link-layers of sender & receiver provide transmission services for their network-layers.
Data-link-layers use the services provided by their physical layers for the physical transmission of
bits.
FSMs
Two main requirements:

The sender-site cannot send a frame until its network-layer has a data packet to send. The receiver-
site cannot deliver a data packet to its network-layer until a frame arrives.
These 2 requirements are shown using two FSMs. Each FSM has only one state, the ready state.
Here is how it works (Figure 11.8):

Here is how it works (Figure 11.8):

At Sending Machine

The sending machine remains in the ready state until a request comes from the process in the network
layer.
When this event occurs, the sending machine encapsulates the message in a frame and sends it to the
receiving machine.
2) At Receiving Machine

The receiving machine remains in the ready state until a frame arrives from the sending machine.
When this event occurs, the receiving machine encapsulates the message out of the frame and
delivers it to the process at the network layer.

Example 3.6
Stop & Wait Protocol

This uses both flow and error control.

Normally, the receiver has limited storage-space.
If the receiver is receiving data from many sources, the receiver may be overloaded with frames &
discard the frames.
To prevent the receiver from being overloaded with frames, we need to tell the sender to slow down.

Design

At Sender

The sender
sends one frame & starts a timer keeps a copy of the sent-frame and waits for ACK-frame from the
receiver (okay to go ahead).
Then,
1) If an ACK-frame arrives before the timer expires, the timer is stopped and the sender sends the
next frame.

Also, the sender discards the copy of the previous frame.

2) If the timer expires before ACK-frame arrives, the sender resends the previous frame and restarts
the timer

At Receiver

To detect corrupted frames, a CRC is added to each data frame. When a frame arrives at the receiver-
site, the frame is checked.
If frame’s CRC is incorrect, the frame is corrupted and discarded.
The silence of the receiver is a signal for the sender that a frame was either corrupted or lost.
FSMs

Here is how it works (Figure 11.11):

Sender States

Sender is initially in the ready state, but it can move between the ready and blocking state.

Ready State: When the sender is in this state, it is only waiting for a packet from the network layer.
If a packet comes from the network layer, the sender creates a frame, saves a copy of the frame, starts
the only timer and sends the frame. The sender then moves to the blocking state.

Blocking State: When the sender is in this state, three events can occur:
If a time-out occurs, the sender resends the saved copy of the frame and restarts the timer.
If a corrupted ACK arrives, it is discarded.
If an error-free ACK arrives, the sender stops the timer and discards the saved copy of the frame. It
then moves to the ready state.

Receiver

The receiver is always in the ready state. Two events may occur:
If an error-free frame arrives, the message in the frame is delivered to the network layer and an ACK
is sent.
If a corrupted frame arrives, the frame is discarded.
Example

3.7.2.3 Sequence and Acknowledgment Numbers

• Q: How to deal with corrupted-frame?

Ans: If the corrupted-frame arrives at the receiver-site, then the frame is simply discarded.

• Q: How to deal with lost-frames?

Ans: If the receiver receives out-of-order data-frame, then it means that frames were lost. .’. The lost-
frames need to be resent.
Problem in Stop and Wait protocols:

There is no way to identify a frame.

The received-frame could be the correct one, or a duplicate, or a frame out of order.
Solution:
1) Use sequence-number for each data frame.
2) Use Acknowledgment-number for each ACK frame.

Sequence Numbers

Frames need to be numbered. This is done by using sequence-numbers. A sequence-number field is

added to the data-frame.

Acknowledgment Numbers
An acknowledgment-number field is added to the ACK-frame. Sequence numbers are 0, 1, 0, 1, 0,
1,..
The acknowledgment numbers can also be 1, 0, 1, 0, 1, 0, …
The acknowledgment-numbers always announce the sequence-number of the next frame expected by
the receiver.
For example,
If frame-0 has arrived safely, the receiver sends an ACK-frame with acknowledgment-1 (meaning
frame-1 is expected next).
Example

Piggybacking

A technique called piggybacking is used to improve the efficiency of the bidirectional protocols. The
data in one direction is piggybacked with the acknowledgment in the other direction.
In other words, when node A is sending data to node B, Node A also acknowledges the data received
from node B.
High-level Data Link Control (HDLC)
High-level Data Link Control (HDLC) is a group of communication protocols of the data link layer for
transmitting data between network points or nodes. Since it is a data link protocol, data is organized into
frames. A frame is transmitted via the network to the destination that verifies its successful arrival. It is a
bit - oriented protocol that is applicable for both point - to - point and multipoint communications.

Transfer Modes
HDLC supports two types of transfer modes, normal response mode and asynchronous balanced
mode.
 Normal Response Mode (NRM) − Here, two types of stations are there, a primary station
that send commands and secondary station that can respond to received commands. It is
used for both point - to - point and multipoint communications.
  Asynchronous Balanced Mode (ABM) − Here, the configuration is balanced, i.e. each
station can both send commands and respond to commands. It is used for only point - to -
point communications.

HDLC Frame
HDLC is a bit - oriented protocol where each frame contains up to six fields. The structure
varies according to the type of frame. The fields of a HDLC frame are −
 Flag − It is an 8-bit sequence that marks the beginning and the end of the frame. The bit
pattern of the flag is 01111110.

 Address − It contains the address of the receiver. If the frame is sent by the primary station,
it contains the address (s) of the secondary station (s). If it is sent by the secondary station,
it contains the address of the primary station. The address field may be from 1 byte to
several bytes.

 Control − It is 1 or 2 bytes containing flow and error control information.

 Payload − This carries the data from the network layer. Its length may vary from one
network to another.

 FCS − It is a 2 byte or 4 bytes frame check sequence for error detection. The standard code
used is CRC (cyclic redundancy code)
Types of HDLC Frames
There are three types of HDLC frames. The type of frame is determined by the control field of
the frame −
 I-frame − I-frames or Information frames carry user data from the network layer. They also
include flow and error control information that is piggybacked on user data. The first bit of
control field of I-frame is 0.

 S-frame − S-frames or Supervisory frames do not contain information field. They are used
for flow and error control when piggybacking is not required. The first two bits of control
field of S-frame is 10.

 U-frame − U-frames or Un-numbered frames are used for myriad (a very large number of)
miscellaneous functions, like link management. It may contain an information field, if
required. The first two bits of control field of U-frame is 11.
Multiple Access Protocol- ALOHA, CSMA,
CSMA/CA and CSMA/CD
Data Link Layer
The data link layer is used in a computer network to transmit the data between two devices or
nodes. It divides the layer into parts such as data link control and the multiple access
resolution/protocol. The upper layer has the responsibility to flow control and the error control in
the data link layer, and hence it is termed as logical of data link control. Whereas the lower sub-
layer is used to handle and reduce the collision or multiple access on a channel. Hence it is termed
as media access control (MAC) or the multiple access resolutions.
What is a multiple access protocol?
When a sender and receiver have a dedicated link to transmit data packets, the data link control is
enough to handle the channel. Suppose there is no dedicated path to communicate or transfer the
data between two devices. In that case, multiple stations access the channel and simultaneously
transmit the data over the channel. It may create collision and cross talk. Hence, the multiple access
protocol is required to reduce the collision and avoid crosstalk between the channels.

Following are the types of multiple access protocol that is subdivided into the different process as:

‘A. Random Access Protocol

In this protocol, all the station has the equal priority to send the data over a channel. In random
access protocol, one or more stations cannot depend on another station nor any station control
another station. Depending on the channel's state (idle or busy), each station transmits the data
frame. However, if more than one station sends the data over a channel, there may be a collision
or data conflict. Due to the collision, the data frame packets may be lost or changed. And hence,
it does not receive by the receiver end.

Following are the different methods of random-access protocols for broadcasting frames on the
channel.

o Aloha
o CSMA
o CSMA/CD
 o CSMA/CA

ALOHA Random Access Protocol

It is designed for wireless LAN (Local Area Network) but can also be used in a shared medium
to transmit data. Using this method, any station can transmit data across a network simultaneously
when a data frameset is available for transmission.

Aloha Rules

1. Any station can transmit data to a channel at any time.

2. It does not require any carrier sensing.
3. Collision and data frames may be lost during the transmission of data through multiple
stations.
4. Acknowledgment of the frames exists in Aloha. Hence, there is no collision detection.
5. It requires retransmission of data after some random amount of time.

Pure Aloha

Whenever data is available for sending over a channel at stations, we use Pure Aloha. In pure
Aloha, when each station transmits data to a channel without checking whether the channel is idle
or not, the chances of collision may occur, and the data frame can be lost. When any station
transmits the data frame to a channel, the pure Aloha waits for the receiver's acknowledgment. If
it does not acknowledge the receiver end within the specified time, the station waits for a random
amount of time, called the bakeoff time (Tb). And the station may assume the frame has been lost
or destroyed. Therefore, it retransmits the frame until all the data are successfully transmitted to
the receiver.
As we can see in the figure above, there are four stations for accessing a shared channel and
transmitting data frames. Some frames collide because most stations send their frames at the same
time. Only two frames, frame 1.1 and frame 2.2, are successfully transmitted to the receiver end.
At the same time, other frames are lost or destroyed. Whenever two frames fall on a shared channel
simultaneously, collisions can occur, and both will suffer damage. If the new frame's first bit
enters the channel before finishing the last bit of the second frame. Both frames are completely
finished, and both stations must retransmit the data frame.

Slotted Aloha

The slotted Aloha is designed to overcome the pure Aloha's deficiency because pure Aloha has a
very high possibility of frame hitting. In slotted Aloha, the shared channel is divided into a fixed
time interval called slots. So that, if a station wants to send a frame to a shared channel, the frame
can only be sent at the beginning of the slot, and only one frame is allowed to be sent to each slot.
And if the stations are unable to send data to the beginning of the slot, the station will have to wait
until the beginning of the slot for the next time. However, the possibility of a collision remains
when trying to send a frame at the beginning of two or more station time slot.
CSMA (Carrier Sense Multiple Access)

It is a carrier sense multiple access based on media access protocol to sense the traffic on a
channel (idle or busy) before transmitting the data. It means that if the channel is idle, the station
can send data to the channel. Otherwise, it must wait until the channel becomes idle. Hence, it
reduces the chances of a collision on a transmission medium.

CSMA Access Modes

1-Persistent: In the 1-Persistent mode of CSMA that defines each node, first sense the shared
channel and if the channel is idle, it immediately sends the data. Else it must wait and keep track
of the status of the channel to be idle and broadcast the frame unconditionally as soon as the
channel is idle.

Non-Persistent: It is the access mode of CSMA that defines before transmitting the data, each
node must sense the channel, and if the channel is inactive, it immediately sends the data
Otherwise, the station must wait for a random time (not continuously), and when the channel is
found to be idle, it transmits the frames.

P-Persistent: It is the combination of 1-Persistent and Non-persistent modes. The P-Persistent

mode defines that each node senses the channel, and if the channel is inactive, it sends a frame
with a P probability. If the data is not transmitted, it waits for a (q = 1-p probability) random time
and resumes the frame with the next time slot.

O- Persistent: It is an O-persistent method that defines the superiority of the station before the
transmission of the frame on the shared channel. If it is found that the channel is inactive, each
station waits for its turn to retransmit the data.
CSMA/ CD

It is a carrier senses multiple access/ collision detection network protocol to transmit data
frames. The CSMA/CD protocol works with a medium access control layer. Therefore, it first
senses the shared channel before broadcasting the frames, and if the channel is idle, it transmits a
frame to check whether the transmission was successful. If the frame is successfully received, the
station sends another frame. If any collision is detected in the CSMA/CD, the station sends a jam/
stop signal to the shared channel to terminate data transmission. After that, it waits for a random
time before sending a frame to a channel.

CSMA/ CA

It is a carrier sense multiple access/collision avoidance network protocol for carriertransmission

of data frames. It is a protocol that works with a medium access control layer. When a data frame
is sent to a channel, it receives an acknowledgment to check whether the channel is clear. If the
station receives only a single (own) acknowledgments, that means the data frame has been
successfully transmitted to the receiver. But if it gets two signals (its own and one more in which
the collision of frames), a collision of the frame occurs in the shared channel. Detects the collision
of the frame when a sender receives an acknowledgment signal.

Following are the methods used in the CSMA/ CA to avoid the collision:

Interframe space: In this method, the station waits for the channel to become idle, and if it gets
the channel is idle, it does not immediately send the data. Instead of this, it waits for some time,
and this time period is called the Interframe space or IFS. However, the IFS time is often used
to define the priority of the station.

Contention window: In the Contention window, the total time is divided into different slots. When
the station/ sender is ready to transmit the data frame, it chooses a random slot number of slots as
wait time. If the channel is still busy, it does not restart the entire process, except that it restarts
the timer only to send data packets when the channel is inactive.

Acknowledgment: In the acknowledgment method, the sender station sends the data frame to the
shared channel if the acknowledgment is not received ahead of time.
B. Controlled Access Protocol
It is a method of reducing data frame collision on a shared channel. In the controlled access
method, each station interacts and decides to send a data frame by a particular station approved by
all other stations. It means that a single station cannot send the data frames unless all other stations
are not approved. It has three types of controlled access: Reservation, Polling, and Token
Passing.

1). Reservation

Whenever we travel from a train or an airplane, the first thing we do is to reserve our seats,
similarly here a station must make a reservation first before transmitting any data-frames.

This reservation in Computer Network timeline consists of two kinds of periods:

1. Reservation interval of a fixed time duration

2. Data transmission period of variable frames

Consider there are 4 stations then the reservation intervals are divided into 4 slots so that each
station has a slot. Means if n number of stations are there then n slot will be allotted.

Now let us assume that these 4 stations are 4 friends, now is friend-1 speaks in his slot-1 then no
other friend can speak at this time. Similarly, if station-1 transmits a 1-bit data-frame in slot-1
then at that time no other station can transmit its data-frames and they must wait for their time
slot. After all the slots have transmitted and checked then each station knows which station now
wishes for transmission.

The biggest advantage of this method is since all stations agree on which station is next to
transmit then there are no possible collisions.

The illustration below shows a scenario with five stations with a five-slot reservation frame.
here, in the time interval station 1,3,4 are the only stations with reservations and in the second
interval station-1 is the only station with a reservation.
2). Polling

In a computer network there is a primary station or controller and all other stations are
secondary, the primary station sends a message to each station. The message which is sent by the
primary station consists of the address of the station which is selected for granting access.

The point to remember is that all the nodes receive the message but the addressed one responds
and sends data in return, but if the station has no data to transmit then it sends a message
called Poll Reject or NAK (negative acknowledgment).

But this method has some drawbacks like the high overhead of the polling messages and high
dependence on the reliability of the primary station.

Whenever the primary station wants to recieve the data, it asks the secondary stations present in
its channel, this method is polling. In the first diagram, we see that primary station asks station A
if it has any data ready for transmission, since A does not have any data queued for transmission
it sends NAK (negative acknowledgement), and then it asks station B, since B has data ready for
transmission, so it transmits the data and in return recieves acknowledgement from primary
station.
In the next case, if primary station wants to send data to the secondary stations, it sends a select
message, and if the secondary station accepts the request from the primary station, then it sends
back an acknowledgement and then primary station transmits the data and in return receives an
acknowledgement.

3). Token Passing

In computer networks a token is a special bit pattern that allows the token possessing system to
send data or we can say that a token represents permission to transmit data. The token circulation
around the table (or a network ring) is in a predefined order. A station can only pass the token to
its adjacent station and not to any other station in the network. If a station has some data queued
for transmission it cannot transmit the data until it receives the token and makes sure it has
transmitted all the data before passing on the received token.

This method has some drawbacks like duplication of token or sometimes the token is damaged or
lost during the circulation, or sometimes if we introduce a new station or remove an existing
station from the network, this leads to a huge disturbance, which should be taken care of so that
the efficiency of the method is not affected.

The performance of a token ring is governed by 2 parameters, which are delay and throughput.

Delay is a measure of the time; it is the time difference between a packet ready for transmission
and when it is transmitted. Hence, the average time required to send a token to the next station is
a/N.

Throughput is a measure of the successful traffic in the communication channel.

In the diagram below when station-1 posses the token it starts transmitting all the data-frames
which are in it's queue. Now after transmission, station-1 passes the token to station-2 and so on.
Station-1 can now transmit data again, only when all the stations in the network have transmitted
their data and passed the token.
C. Channelization Protocols
It is a channelization protocol that allows the total usable bandwidth in a shared channel to be
shared across multiple stations based on their time, distance and codes. It can access all the stations
at the same time to send the data frames to the channel.

Following are the various methods to access the channel based on their time, distance and codes:

1. FDMA (Frequency Division Multiple Access)

2. TDMA (Time Division Multiple Access)
3. CDMA (Code Division Multiple Access)

FDMA

It is a frequency division multiple access (FDMA) method used to divide the available bandwidth
into equal bands so that multiple users can send data through a different frequency to the sub
channel. Each station is reserved with a particular band to prevent the crosstalk between the
channels and interferences of stations.
TDMA

Time Division Multiple Access (TDMA) is a channel access method. It allows the same frequency
bandwidth to be shared across multiple stations. And to avoid collisions in the shared channel, it
divides the channel into different frequency slots that allocate stations to transmit the data frames.
The same frequency bandwidth into the shared channel by dividing the signal into various time
slots to transmit it. However, TDMA has an overhead of synchronization that specifies each
station's time slot by adding synchronization bits to each slot.

CDMA

The code division multiple access (CDMA) is a channel access method. In CDMA, all stations
can simultaneously send the data over the same channel. It means that it allows each station to
transmit the data frames with full frequency on the shared channel at all times. It does not require
the division of bandwidth on a shared channel based on time slots. If multiple stations send data to
a channel simultaneously, their data frames are separated by a unique code sequence. Each station
has a different unique code for transmitting the data over a shared channel. For example, there are
multiple users in a room that are continuously speaking. Data is received by the users if only two-
person interact with each other using the same language. Similarly, in the network, if different
stations communicate with each other simultaneously with different code language.