Data Link Layer

Introduction
● Main functions of the data link layer are
● Data link control and
● Media access control.
 Data Link Control(DLC)
● Data link control deals with the design and
procedures for communication between two
adjacent nodes: node­to­node communication.

● Data link control functions include framing and

flow and error control. Framing determines
how to organize the bits that are carried by
the physical layer.
Framing
● Data transmission in the physical layer
means moving bits in the form of a signal
from the source to the destination. The
physical layer provides bit synchronization to
ensure that the sender and receiver use the
same bit durations and timing.
● The data­link layer, on the other hand, needs
to pack bits into frames, so that each frame
is distinguishable from another.
● Framing in the data­link layer separates a
message from one source to a destination
by adding a sender address and a
destination address. The destination address
defines where the packet is to go; the sender
address helps the recipient acknowledge the
receipt.
● If the whole message is packed in one frame,
it makes flow and error control difficult.
● Moreover, when a message is carried in one
large frame, even a single bit error would
need retransmission of the whole frame.
● When a message is divided into smaller
frames, a single bit error affects only that
frame.
Frame Size
● Frames can be of fixed or variable size.
● In fixed­size framing, there is no need for
defining the boundaries of the frames; the size
itself can be used as a delimiter.
● In variable­size framing, mostly used in local­
area networks, there is a need to define
boundaries of the frames.
● Two approaches used for this purpose are
character­oriented approach and a bit­oriented
approach.
Character­Oriented Framing
● In character­oriented (or byte­oriented)
framing, data to be carried are 8­bit
characters from a coding system such as
ASCII.
● The header, which normally carries the
source and destination addresses and other
control information, and the trailer, which
carries error detection redundant bits, are
also multiples of 8 bits.
● To separate one frame from the next, an 8­
bit (1­byte) flag is added at the beginning
and the end of a frame. The flag, composed
of protocol­dependent special characters,
signals the start or end of a frame.
● Character­oriented framing can be used
when text is exchanged by the data­link
layers.
● The flag could be selected to be any
character not used for text communication.
● When other types of information such as
graphs, audio, and video are used for
communication; any character used for the
flag could also be part of the information.
● In such cases, if the receiver encounters this
pattern in the middle of the data, it thinks it
has reached the end of the frame.
● To fix this problem, a byte­stuffing strategy
was added to character­oriented framing.
Byte Stuffing
● In byte stuffing (or character stuffing), a
special byte is added to the data section of
the frame when there is a character with the
same pattern as the flag. The data section is
stuffed with an extra byte. This byte is
usually called the escape character (ESC)
and has a predefined bit pattern. Whenever
the receiver encounters the ESC character, it
removes it from the data section and treats
the next character as data, not as a
delimiting flag.
● Byte stuffing by the escape character allows the
presence of the flag in the data section of the frame.
However, if the text contains one or more escape
characters followed by a byte with the same pattern
as the flag, the receiver removes the escape
character, but keeps the next byte, which is
incorrectly interpreted as the end of the frame. To
solve this problem, the escape characters that are
part of the text must also be marked by another
escape character. In other words, if the escape
character is part of the text, an extra one is added
to show that the second one is part of the text.
Bit­Oriented Framing
● In bit­oriented framing, the data section of a frame
is a sequence of bits to be interpreted by the upper
layer as text, graphic, audio, video, and so on.
● In addition to headers and trailers, a delimiter is
needed to separate one frame from the other.
● Most protocols use a special 8­bit pattern flag,
01111110, as the delimiter to define the beginning
and the end of the frame.
● If the flag pattern appears in the data, the
receiver should be able to identify that this is
not the end of the frame.
● To do this, 1 single bit is stuffed (instead of 1
byte) to prevent the pattern from looking like
a flag. The strategy is called bit stuffing.
● In bit stuffing, if a 0 and five consecutive 1 bits
are encountered, an extra 0 is added. This extra
stuffed bit is eventually removed from the data
by the receiver. Note that the extra bit is added
after one 0 followed by five 1s regardless of the
value of the next bit. This guarantees that the
flag field sequence does not inadvertently
appear in the frame.
Bit Stuffing
Flow Control
● Flow control coordinates the amount of data
that can be sent before receiving an
acknowledgment.
● Flow control is a set of procedures that tells
the sender how much data it can transmit
before it must wait for an acknowledgment
from the receiver. The flow of data must not
be allowed to overwhelm the receiver.
● Each receiving device has a block of
memory, called a buffer, reserved for storing
incoming data until they are processed. If the
buffer begins to fill up, the receiver must be
able to tell the sender to halt transmission
until it is once again able to receive.
Error Control
● Error control at the data link layer refers to
methods of error detection and retransmission.
● It allows the receiver to inform the sender of any
frames lost or damaged in transmission and
coordinates the retransmission of those frames
by the sender.
● At the data link layer, any time an error is
detected in an exchange, specified frames are
retransmitted. This process is called automatic
repeat request (ARQ).
Taxonomy of Protocols
Simplest
Noiseless
Channels
Stop and
Wait

Protocols Stop­and­
Wait ARQ

Noisy Go­Back­N
Channels ARQ
Selective
Repeat
ARQ
Simplest Protocol
● The Simplest Protocol is the one that has no
flow or error control.
● It is a unidirectional protocol in which data
frames are traveling in only one direction­
from the sender to receiver.
● We assume that the receiver can
immediately handle any frame it receives
with a processing time that is small enough
to be negligible.
● The data link layer of the receiver
immediately removes the header from the
frame and hands the data packet to its
network layer, which can also accept the
packet immediately.
● In other words, the receiver can never be
overwhelmed with incoming frames.
Stop­and­Wait Protocol
● If data frames arrive at the receiver site faster
than they can be processed, the frames must
be stored until their use.
● Normally, the receiver does not have enough
storage space, especially if it is receiving data
from many sources. This may result in either the
discarding of frames or denial of service.
● To prevent the receiver from becoming
overwhelmed with frames, the sender must be
informed to slow down.
● There must be feedback from the receiver to
the sender.
● In the Stop­and­Wait Protocol, the sender
sends one frame, stops until it receives
confirmation from the receiver, and then
sends the next frame.
● The communication is unidirectional for data
frames, but auxiliary ACK frames (simple
tokens of acknowledgment) travel from the
other direction.
FSM for Stop­and­Wait Protocol
 Sender States
● The 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:
a. If a time­out occurs, the sender resends the
saved copy of the frame and restarts the timer.
b. If a corrupted ACK arrives, it is discarded.
c. 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:
a. If an error­free frame arrives, the message
in the frame is delivered to the network
layer and an ACK is sent.
b. If a corrupted frame arrives, the frame is
discarded.
Flow Diagram
Stop­and­Wait ARQ
● The Stop­and­Wait Automatic Repeat Request
(Stop­and­Wait ARQ), adds a simple error
control mechanism to the Stop­and­Wait
Protocol.
● To detect and correct corrupted frames, we
need to add redundancy bits to our data frame.
When the frame arrives at the receiver site, it is
checked and if it is corrupted, it is silently
discarded.
● The detection of errors in this protocol is shown
by the silence of the receiver.
● To handle lost frames, the Stop­and­Wait
ARQ numbers the frames.
● When the receiver receives a data frame
that is out of order, this means that frames
were either lost or duplicated.
● The corrupted and lost frames need to be
resent in this protocol.
● To handle these frames, the sender keeps a
copy of the sent frame. At the same time, it
starts a timer. If the timer expires and there is
no ACK for the sent frame, the frame is resent,
the copy is held, and the timer is restarted.
● Since the protocol uses the stop­and­wait
mechanism, there is only one specific frame
that needs an ACK even though several
copies of the same frame can be in the
network.
● Since an ACK frame can also be corrupted
and lost, it too needs redundancy bits and a
sequence number.
● The ACK frame for this protocol has a
sequence number field.
● In this protocol, the sender simply discards a
corrupted ACK frame or ignores an out­of­
order one.
●
Frame 0 is sent and acknowledged. Frame 1 is lost and resent after the time-
out. The resent frame 1 is acknowledged and the timer stops. Frame 0 is
sent and acknowledged, but the acknowledgment is lost. The sender has no
idea if the frame or the acknowledgment is lost, so after the time-out, it
resends frame 0, which is acknowledged.
Go­Back­N ARQ
● To improve the efficiency of transmission,
multiple frames must be in transition while
waiting for acknowledgment.
● In Go­Back­N ARQ protocol, we can send
several frames before receiving
acknowledgments; we keep a copy of these
frames until the acknowledgments arrive.
Sliding Window
● The sliding window is an abstract concept
that defines the range of sequence numbers
that is the concern of the sender and
receiver.
● The range which is the concern of the
sender is called the send sliding window; the
range that is the concern of the receiver is
called the receive sliding window.
● The send window is an imaginary box
covering the sequence numbers of the data
frames which can be in transit. In each
window position, some of these sequence
numbers define the frames that have been
sent; others define those that can be sent.
The diagram shows a sliding window of size
15 (m =4).
● The window at any time divides the possible
sequence numbers into four regions.
● The first region, from the far left to the left wall of
the window, defines the sequence numbers
belonging to frames that are already acknowledged.
The sender does not keep copies of them.
● The second region, colored in orange defines the
range of sequence numbers belonging to the
frames that are sent and have an unknown status.
The sender needs to wait to find out if these frames
have been received or were lost. These frames are
called outstanding frames.
● The third range, white in the figure, defines
the range of sequence numbers for frames
that can be sent; however, the
corresponding data packets have not yet
been received from the network layer.
● Finally, the fourth region defines sequence
numbers that cannot be used until the
window slides.
Send window for Go­Back­N ARQ
●
● The receive window makes sure that the
correct data frames are received and that
the correct acknowledgments are sent.
● The size of the receive window is always I.
The receiver is always looking for the arrival
of a specific frame.
● Any frame arriving out of order is discarded
and needs to be resent.
Receive Window Size of Go­Back­N
ARQ
 Acknowledgment

● The receiver sends a positive acknowledgment

if a frame has arrived safe and sound and in
order.
● If a frame is damaged or is received out of
order, the receiver is silent and will discard all
subsequent frames until it receives the one it is
expecting.
● The silence of the receiver causes the timer of
the unacknowledged frame at the sender site
to expire.
● This, in turn, causes the sender to go back and
resend all frames, beginning with the one with
the expired timer.
● The receiver does not have to acknowledge
each frame received. It can send one
cumulative acknowledgment for several frames.
● For example, suppose the sender has already
sent frame 6, but the timer for frame 3 expires.
This means that frame 3 has not been
acknowledged; the sender goes back and
sends frames 3, 4,5, and 6 again.
Window size of Go­Back­N
ARQ
Acknowledgement is lost
Frame is lost
Selective Repeat ARQ
● In Go­Back­N ARQ, the receiver does not
need to buffer out­of­order frames; they are
simply discarded.
● However, this protocol is very inefficient for a
noisy link. In a noisy link a frame has a
higher probability of damage, which means
the resending of multiple frames.
● This resending uses up the bandwidth and
slows down the transmission.
● For noisy links, there is another mechanism
that resends only the frame that is damaged.
This mechanism is called Selective Repeat
ARQ.
● It is more efficient for noisy links, but the
processing at the receiver is more complex.
Selective Repeat ARQ
●
Window size in Selective­
Repeat ARQ
● One main difference is the number of timers.
Here, each frame sent or resent needs a
timer, which means that the timers need to
be numbered (0, 1,2, and 3).
● NAK indicates that a particular frame was
not received.
● The three protocols mentioned above are
unidirectional ­ data frames flow in only one
direction although control information such
as ACK and NAK frames can travel in the
other direction.
● In real life, data frames are normally flowing
in both directions: from node A to node B
and from node B to node A. This means that
the control information also needs to flow in
both directions.
● 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.
● Piggybacking saves bandwidth.
HDLC
● High­level Data Link Control
● Bit­oriented protocol
● Support both
● Point­to­point links
● Multipoint links
Normal Response Mode
● "NRM" mode
● Station configuration is unbalanced.
● Used in both point­to­point and multi­point link
Asynchronous Balanced Mode
● "ABM"
● Supports only point­to­point links
● Each station is both primary and secondary
 HDLC Frames

● HDLC defines three types of frames: information

frames(I­frames), supervisory frames (S­frames),
and unnumbered frames (U­frames).
● Each type of frame serves as an envelope for the
transmission of a different type of message.
● I­frames are used to transport user data and
control information relating to user
data(piggybacking).
● S­frames are used only to transport control
information.
● U­frames are reserved for system management i.e.
HDLC Frames
● Information frame (I­frame)

● Supervisory frame (S­frame)

Frame Check Sequence
(error detection code)

● Unnumbered frame (U­frame)

 HDLC Fields
Flag field. The flag field is an 8­bit sequence with the bit
pattern 01111110 that identifies both the beginning and the
end of a frame and serves as a synchronization pattern for
the receiver.
Address field. This field contains the address of the
secondary station. If a primary station created the frame, it
contains a to address. If a secondary creates the frame, it
contains a from address. An address field can be 1 byte or
several bytes long, depending on the needs of the network.
One byte can identify up to 128 stations. If the address field
is only 1 byte, the last bit is always a 1. If the address is
more than 1 byte, all bytes but the last one will end with 0;
only the last will end with 1.
● Control field. The control field is a 1­ or 2­
byte segment of the frame used for flow and
error control.
● Information field. The information field
contains the user's data from the network
layer or management information.
● FCS field. The frame check sequence (FCS)
is the HDLC error detection field. It can
contain either a 2­ or 4­byte ITU­T CRC.
Control Field Format

● N(S) – Frame sequence number

● N(R) – Ack sequence number
● P/F
● Poll (Frame is sent from primary → secondary)
● Final (secondary → primary)
Control fields for I­Frame
● I­frames are designed to carry user data
from the network layer. In addition, they can
include flow and error control information
(piggybacking).
● The subfields in the control field are used to
define these functions.
● The first bit defines the type. If the first bit of
the control field is 0, this means the frame is
an I­frame.
Control Fields for S­frame
● Supervisory frames are used for flow and error
control whenever piggybacking is either impossible
or inappropriate. S­frames do not have information
fields.
● With 2 bits, we can have four types of S­frames, as
described below:
● Receive ready (RR). If the value of the code subfield is
00, it is an RR S­frame. This kind of frame acknowledges
the receipt of a safe and sound frame or group of frames.
In this case, the value N(R) field defines the
acknowledgment number.
● Receive not ready (RNR). If the value of the
code subfield is 10, it is an RNR S­frame.
This kind of frame is an RR frame with
additional functions. It acknowledges the
receipt of a frame or group of frames, and it
announces that the receiver is busy and
cannot receive more frames. It acts as a kind
of congestion control mechanism by asking
the sender to slow down. The value of NCR)
is the acknowledgment number.
● Reject (REJ). If the value of the code subfield is 01, it
is a REJ S­frame. This is a NAK frame, that can be
used in Go­Back­N ARQ to improve the efficiency of
the process by informing the sender, before the
sender time expires, that the last frame is lost or
damaged.
● Selective reject (SREJ). If the value of the code
subfield is 11, it is an SREJ S­frame. This is a NAK
frame used in Selective Repeat ARQ. Note that the
HDLC Protocol uses the term selective reject instead
of selective repeat. The value of N(R) is the negative
acknowledgment number.
U­Frames
● Unnumbered frames are used to exchange
session management and control
information between connected devices.
● Unlike S­frames, U­frames contain an
information field, but one used for system
management information, not user data.
U­Frame Codes
Connect and disconnect
example
Example of Piggybacking with error
PPP (Point­to­Point Protocol)
● Point­to­Point Protocol at the data link layer
● Byte­oriented protocol
 PPP Services

PPP defines the format of the frame to be exchanged between

devices.
PPP defines how two devices can negotiate the establishment
of the link and the exchange of data.
PPP defines how network layer data are encapsulated in the
data link frame.
PPP defines how two devices can authenticate each other.
PPP provides multiple network layer services supporting a
variety of network layer protocols.
PPP provides connections over multiple links.
PPP provides network address configuration. This is particularly
useful when a home user needs a temporary network address
to connect to the Internet.
Limitations of PPP
● PPP does not provide flow control. A sender can send
several frames one after another with no concern
about overwhelming the receiver.
● PPP has a very simple mechanism for error control. A
CRC field is used to detect errors. If the frame is
corrupted, it is silently discarded; the upper­layer
protocol needs to take care of the problem. Lack of
error control and sequence numbering may cause a
packet to be received out of order.
● PPP does not provide a sophisticated addressing
mechanism to handle frames in a multipoint
configuration.
PPP Frame Format

● Escape byte: 01111101

● A PPP frame starts and ends with a 1­byte
flag with the bit pattern 01111110.
● Control field uses HDLC's U­frame format
● No flow or error control
● Payload field. This field carries either the
user data or other information. The data field
is a sequence of bytes with the default of a
maximum of 1500 bytes. The data field is
byte stuffed if the flag byte pattern appears
in this field. Because there is no field
defining the size of the data field, padding is
needed if the size is less than the maximum
default value or the maximum negotiated
value.
PPP Transition States
● Dead. In the dead phase the link is not being
used.
● Establish. When one of the nodes starts the
communication, the connection goes into
this phase. In this phase, options are
negotiated between the two parties. If the
negotiation is successful, the system goes to
the authentication phase (if authentication is
required) or directly to the networking phase.
● Authenticate. The authentication phase is
optional; the two nodes may decide, during
the establishment phase, not to skip this
phase. However, if they decide to proceed
with authentication, they send several
authentication packets. If the result is
successful, the connection goes to the
networking phase; otherwise, it goes to the
termination phase.
● Network. In the network phase, negotiation
for the network layer protocols takes place.
PPP specifies that two nodes establish a
network layer agreement before data at the
network layer can be exchanged. The
reason is that PPP supports multiple
protocols at the network layer. If a node is
running multiple protocols simultaneously at
the network layer, the receiving node needs
to know which protocol will receive the data.
● Open. In the open phase, data transfer
takes place. When a connection reaches this
phase, the exchange of data packets can be
started. The connection remains in this
phase until one of the endpoints wants to
terminate the connection.
● Terminate. In the termination phase the
connection is terminated. Several packets
are exchanged between the two ends for
house cleaning and closing the link.
PPP uses another set of other protocols to establish the link,
authenticate the parties involved, and carry the network layer data.
Three sets of protocols are defined to make PPP powerful: the Link
Control Protocol (LCP), two Authentication Protocols (APs), and
several Network Control Protocols (NCPs).
● The Link Control Protocol (LCP) is
responsible for establishing, maintaining,
configuring, and terminating links. It also
provides negotiation mechanisms to set
options between the two endpoints. Both
endpoints of the link must reach an
agreement about the options before the link
can be established.
Authentication Protocols
● Authentication plays a very important role in
PPP because PPP is designed for use over dial­
up links where verification of user identity is
necessary.
● Authentication means validating the identity of
a user who needs to access a set of resources.
● PPP has created two protocols for
authentication: Password Authentication
Protocol and Challenge Handshake
Authentication Protocol. These protocols are
used during the authentication phase.
PAP packets encapsulated in
a PPP frame
PAP The Password Authentication Protocol
(PAP) is a simple authentication procedure
with a two­step process:
1. The user who wants to access a system sends an
authentication identification (usually the user name)
and a password.
2. The system checks the validity of the identification
and password and either accepts or denies
connection.
When a PPP frame is carrying any PAP packets, the
value of the protocol field is OxC023. The three PAP
packets are authenticate­request, authenticate­ack,
and authenticate­nak.
The first packet is used by the user to send the user
name and password.
The second is used by the system to allow access.
The third is used by the system to deny access.
CHAP packets encapsulated in a
PPP frame
● The Challenge Handshake Authentication
Protocol (CHAP) is a three­way hand­
shaking authentication protocol that provides
greater security than PAP.
● In this method, the password is kept secret;
it is never sent online.
1. The system sends the user a challenge packet
containing a challenge value, usually a few bytes.
2. The user applies a predefined function that takes the
challenge value and the user's own password and
creates a result. The user sends the result in the
response packet to the system.
3. The system does the same. It applies the same
function to the password of the user (known to the
system) and the challenge value to create a result. If the
result created is the same as the result sent in the
response packet, access is granted; otherwise, it is
denied.
CHAP is more secure than PAP, especially if the system
continuously changes the challenge value.