Chapter 4: Data Link Layer

Undergraduate Program
School of Electrical and Computer Engineering
Overview

• Introduction

• Error control

• Flow (Data-Link) Control

• Framing

• Flow and error control

• Noiseless and noisy channels

• Media Access Control

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 3
 Recap
• Data Link Layer: responsible for moving data(frame) between two
adjust nodes.

App. header Data PDU = protocol data unit

Application Layer
Tras. header PDU Segment Application Layer
Transport Layer
Transport Layer
Network Layer
Netw. header PDU Packet Network Layer
Data Link Layer
Network Layer Network Layer Data Link Layer
Physical Layer Data Link PDU
Header Layer Tailor Frame
Data Link Layer Physical Layer
Physical Layer Physical Layer

1001001

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 4
Recap
• Error Control
• The need for redundant bits
• Error detection
• Error correction

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 5
Data Link control

• Deals with design and procedures for communication

between two adjacent nodes
• Framing

• Error control

• Flow control

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 6
 Framing
• Data link layer breaks up large block of data (from upper layer) into
many blocks (frames)
• Frame = Header + Network layer PDU + Trailer
• In packet switched networks, a block of data called is exchanged between nodes
and not bit streams.
• Size of frame:
• Buffer size (memory) limitation
• The longer the transmission, the more likely that there will be an error
• With smaller frames, errors are detected sooner, and a smaller amount of
data needs to be retransmitted

Node A Node B

0101001001011010010

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 7
 Cont.… Framing
• The beginning and end of each frame must be recognizable

• Framing types
• Fixed size
• no need for defining the boundaries of the frames (the size is used as a
delimiter)
• Variable size
• end and beginning of the next frame has to be defined
• Could be Bit-oriented or Byte (character)-oriented

001001001011010010

• Start and end tag : 0010

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 8
Framing – Bit-oriented protocol
• Bit-oriented protocols
• Views the frames as a collection of bits.
• e.g. Flag pattern 01111110

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 9
 Bit-stuffing and framing error
• Framing error : starting/ending to read a sequence of data at the wrong
point.

001001001011010010

• Bit stuffing: inserting non-information extra bits into data to be

transferred, breaking the data sequence and helping with
synchronization

001001000011010010

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 10
High-level data link control (HDLC)
• The most important and widely used data link control protocol
developed by ISO
• Is an extension of Cisco’s proprietary standard
• It is bit-oriented framing protocol

• All frames have a common format

Header PDU Trailer

• Flag (beginning /ending sequence): fields delimit the frame at both ends
with the unique pattern 01111110
• Address Field: The address field identifies the secondary station that
transmitted or is to receive the frame

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 11
Cont.… (HDLC: frame structure )
• Control Field: HDLC defines three types of frames, each with a
different control field format
• Information frames (I frame): carry the data to be transmitted for the
user and flow and error control data, using the ARQ mechanism, are
piggybacked
• Supervisory frames (S frame): essential for error control and flow
control, provide the ARQ mechanism when piggybacking is not used
• Unnumbered frames (U frame):provide supplemental link control
functions
I-frame 1’st bit 0
U-frame 1’st two bits 11
S-frame 1’st two bits 10

• Information/Body Field: The information field is data from the

network layer and is present only in I-frames
• Frame Check Sequence Field : The frame check sequence
(FCS) of CRC is an error detecting code

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 12
Cont.… (HDLC)
• Basic configuration:
• Station/node types
• Primary –responsible for controlling the operation of the link (sends
commands)
• Secondary -operates under the control of the primary station (sends
responses)
• Combined –combines the features of primary and secondary

• HDLC operation
• consists of the exchange of I-frames, S-frames, and U-frames between two
stations
• Involves three phases
• Initialization
• signals the other side that initialization is requested, specifies which of the data transfer
modes, specifies whether 3-or 7-bit sequence numbers are to be used
• Data transfer,
• Disconnect

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 13
Cont.… (HDLC)
• Data transfer modes
• Normal response mode (NRM) –The primary may initiate data
transfer to a secondary, but a secondary may only transmit data in
response to a command from the primary

• Asynchronous balanced mode (ABM) -Either combined station may

initiate transmission without receiving permission from the other
combined station

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 14
Framing – Character-oriented protocol
• Character oriented
• Each frame is view as a collection of characters (bytes) rather than
bits.
• 1-byte flag is added at the beginning and the end of a frame
• Flag –special character

• Point to point protocol (Reading assignment!)

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 15
Overview

• Introduction

• Error control

• Flow (Data-Link) Control

• Framing

• Flow and error control

• Noiseless and noisy channels

• Media Access Control

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 17
Flow Control
• Flow control
• Regulates the flow of data from a sender
• Speed matching mechanism between two nodes
• Avoids Buffer fill up and overflow

• The receiver node needs to inform the sender before its memory limits
are reached to stop or slow down the transmission from the sender

Flow
Control
Protocols

Noiseless Noisy
channels channels

Stop-and- Selective
Simplest Stop-and- Go-back-
wait repeat
protocol wait ARQ N-ARQ
protocol ARQ

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 18
Protocols: Noiseless channels
• Simplex protocol
• It assumes that the sender and receiver are always ready to process data,
and that the channel is ideal and can't go wrong.

• No frames are lost, duplicated or corrupted

• No flow or error control

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 19
Protocols: Noiseless channels
• Stop-and-wait flow control
• Facilitates a unidirectional data flow without error controlling concept.
• Frame by frame acknowledgment is required from the receiver

• Limitation:
• problems with data/ack lost:- waiting for ack. for unlimited time, the next frame
will not be sent
• problems with ack delay:- ack. received in different time

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 20
Protocols: Noisy channels
• Error control
• Keeping a copy of sent frames and retransmitting the frame when
the timer expires
• Numbering frames using sequence numbers
• Acknowledgment message (positive and negative)

• Stop-and-wait automatic repeat request

• Transmit then wait for an acknowledgment
• Two error could occur
• Damaged frame arrived
• Damaged acknowledgment
• There will be a timeout interval (max. waiting time for ack.)

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 21
Stop-and-wait ARQ
• A field is added to the data frame to
hold the sequence number of that
frame

• The sequence numbers are based on

modulo-2 arithmetic

• The acknowledgment number

indicates the sequence number of the
next frame expected

• Simplest, but inefficient mechanism

• One frame at a time
• Poor utilization of bandwidth

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 22
Go-back-N ARQ
• Principle
• send several frames before receiving acknowledgment
• keep a copy of these frames until the acknowledgments arrive
• the sequence numbers are modulo 2𝑚 where 𝑚 is the size of the
sequence number field in bits
• Sliding window-range of sequence numbers that is the concern of the
sender and receiver
• Two windows: a send window (how many frame to send before waiting for
ack.) and a receive window
• The maximum send window size is limited to 2𝑚 − 1

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 23
Cont.… (Go-back-N ARQ)
• Cumulative acknowledgments
• Sliding-window flow control
• Receiver
• No errors occur: acknowledges using RR (receive
ready)
• Error detected: sends a negative ACK REJ (reject)

• Sender
• Damaged frame: the receiver sends a REJ 𝑖 when
an out of order frame is received → the sender must
transmit frame 𝑖 and all subsequent frames

• Damaged RR: if the sender timer expires and the

receiver returns neither an RR nor a REJ the sender
transmits an RR frame that includes a bit known as
the P bit (or resends all outstanding frames)

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 24
Selective-reject ARQ
• The only frames retransmitted are those that receive a
negative ACK (SREJ)
• Minimizes amount of retransmission
• Only the damaged frame is resent
• The receive window is the same size as the send window
• The send window maximum size can be 2𝑚 − 1

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 25
Cont.… (Selective-reject ARQ)

• More efficient than go-back-N (minimizes the amount of

retransmission)

• But, the receiver needs buffer large enough to save post-

SREJ frames until the frame in error is retransmitted

• Receiver needs a logic for reinserting that frame in the

proper Sequence and the transmitter, too, requires more
complex logic to be able to send a frame out of sequence

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 26
Piggybacking

• A technique called piggybacking is used to improve the

efficiency of the bidirectional protocols

• When a frame is carrying data from A to B, it can also carry

control information about arrived (or lost) frames from B

• when a frame is carrying data from B to A, it can also carry

control information about the arrived (or lost) frames from A

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 27
Overview

• Introduction

• Error control

• Flow (Data-Link) Control

• Media Access Control

• Random access protocol

• Controlled access protocol

• Channelized access protocol

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 29
Multiple access
• Multiple-access protocol coordinates access to a shared
link
• Such protocols are essential to avoid collusion or crosstalk

• Data link layer

• Upper sublayer - responsible for data link control
• lower sublayer - responsible for resolving access to the shared
media

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 30
Random Access
• In random access or contention methods, no station is superior to
another station and none is assigned the control over another

• Pure ALOHA
• A simple protocol, initially developed for Wireless LAN
• Principle:
• Each station sends a frame whenever it has a frame to send
• 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
resends the frame

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 31
Cont... (Pure ALOHA)
• Procedure for pure ALOHA protocol

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 32
Cont... (Pure ALOHA)
• Vulnerable time

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 33
Slotted ALOHA
• The time of the shared channel is divided into discrete time intervals
called slots
• Transmission is allowed in the beginning of the time slots

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 34
Carrier Sense Multiple Access (CSMA)
• Stations sense the medium before trying to use it – “sense before
transmit”
• CSMA can reduce the possibility of collision, but it cannot eliminate it
• The channel sensing can result in

• Vulnerable time

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 35
 CSMA
• What should a station do if the channel
is busy?
• 1-persistent
• If medium is idle –transmit
• If the medium is busy- continue to
listen until the channel is sensed idle
• Non-persistent
• If medium is idle –transmit
• If the medium is busy - wait a random
amount of time and then sense the
medium again
• P-persistent
• It applies in slotted channels
• If the medium is busy - continue to
listen until the channel is idle
• If the medium is idle - transmit with
probability p, and delay one time unit
with probability 1-p

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 36
CSMA with Collision Detection (CSMA/CD)
• Procedure:
• Monitors the medium
• If free, transmit and monitor transmission
• If busy, defer
• If a collision occurs during transmission, stop transmitting.
• Send a jamming signal

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 37
CSMA/CD
• Collision detection – energy level
• zero level - the channel is idle
• Normal level - a station has successfully captured the channel and is
sending its frame
• Abnormal level - collision and the level of the energy is twice the normal
level

• The throughput of CSMA/CD is greater than that of pure or slotted ALOHA

1
• CDMA/CD Efficiency = 𝑇𝑝
; 𝑇𝑝 = propagation time ; 𝑇𝑡 = transmission time (>=2* 𝑇𝑝 )
1+6.44
𝑇𝑓

• The efficiency decreases with distance

• Widely used access control protocol in LAN (Ethernet)

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 38
CSMA with Collision Avoidance (CSMA/CA)
• In a wired network, the received signal has
almost the same energy as the sent signal
• Either the length of the cable is short or there
are repeaters that amplify the energy between
the sender and the receiver

• In a wireless network, much of the sent energy

is lost in transmission
• The received signal has very little energy -
collision may add only 5 to 10 percent
additional energy

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 39
Overview

• Introduction

• Error control

• Flow (Data-Link) Control

• Media Access Control

• Random access protocol

• Controlled access protocol

• Channelized access protocol

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 40
Controlled access
• Reservation
• In the reservation method, a station needs to make a reservation
before sending data
• If there are N stations in the system, there are exactly N
reservation minislots
• When a station needs to send a data frame, it makes a reservation
in its own minislot

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 41
Cont.… (Controlled access)
• Polling:
• Stations -primary station and secondary stations
• All data exchanges must be made through the primary device
• The primary device controls the link; the secondary devices follow
its instructions
• Select -whenever the primary device has something to send
• Poll -the primary station ask (poll) each device in turn if it has
anything to send

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 42
Cont.… (Controlled access)
• Token Passing
• Rely upon the establishment of
a physical or logical ring
• stations relay frames in a
prearranged sequence which
gives the appearance that the
stations are arranged as
though they form a ring
• Upon initialization of the
network a single token is
created
• The token circulates around
each station on the ring in turn
• A station wishing to transmit a
frame waits for the token to
arrive at its node

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 43
Channelization
• Channelization is a multiple-access method in which the available
bandwidth of a link is shared in time, frequency, or through code,
between different stations
• Frequency-division multiple access (FDMA)
• The available bandwidth is divided into frequency bands
• Each station is allocated a band to send its data
• Time-division multiple access (TDMA)
• Stations share the bandwidth of the channel in time
• Each station is allocated a time slot during which it can send data
• Code-division multiple access (CDMA)
• In CDMA, one channel carries all transmissions simultaneously
• Each station is assigned a code, which is a sequence of numbers called
chips
• Orthogonal sequences
• Each sequence is made of 𝑁 elements, where 𝑁 is the number of stations
• If we multiply two equal sequences, element by element, and add the results, we get 𝑁
• If we multiply two different sequences, element by element, and add the results, we get 0

Sem. II, 2023/24 Data communication and Computer networks - Ch. 4 – Datalink layer 44