Chapter 11: Outline
11.1 DLC SERVICES
11.2 DATA-LINK LAYER PROTOCOLS
11.3 HDLC
11.4 PPP
Chapter 11: Objective
❑ The first section discusses the general services provided by the
DLC sub layer.
❑ Describes describes framing and two types of frames used in this
sub layer, discusses flow and error control, also explains DLC
protocol can be either connectionless or connection-oriented..
❑ The second section discusses some simple and common data-link
protocols that are implemented at the DLC sub layer.
❑ Describes the Simple Protocol and then explains the Stop-and-
Wait Protocol.
Chapter 11: Objective (continued)
❑ The fourth section discusses PPP, a very common protocol for
point-to-point access.
❑ It first introduces the services provided by the protocol & also
describes the format of the frame in this protocol.
❑ Then describes the transition mode in the protocol using an FSM.
11-1 DLC SERVICES
⮚The data link control (DLC) deals with procedures
for communication between two adjacent nodes no
matter whether the link is dedicated or broadcast.
Data link control functions include framing and flow
and error control.
⮚Discuss framing, or how to organize the bits that
are carried by the physical layer.
⮚Discuss flow and error control.
Framing
⮚The data-link layer needs to pack bits into frames, so
that each frame is distinguishable from another.
⮚ Our postal system practices a type of framing.
⮚The simple act of inserting a letter into an envelope
separates one piece of information from another; the
envelope serves as the delimiter.
⮚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.
11.6
Framing
⮚Whole message can be placed in a single frame, but
that is not done because frame can be very large
making Flow Control and Error Control very
inefficient.
⮚When message is carried in one large frame, even
single bit error would require the retransmission of
the whole frame.
⮚When message is divided into small frames, single
bit error affect only that small frame.
FrameSize
⮚Frame can be i) fixed size
ii) Variable size.
⮚In fixed size framing, no need to define the frame
boundaries. Size itself can be treated as a delimiter.
Eg: ATM frames of fixed size called cells.
⮚In variable size framing, we need to define the frame
boundaries to identify beginning and end of the frame.
⮚Two approaches are used for this purpose
i) Character-oriented Framing
ii) Bit-oriented Framing.
Character-oriented Framing
■Data to be carried are 8-bit characters from coding
system such as ASCII.
■Header carries source, destination address along with
some control information.
■Trailer carries error detection or correction redundant
bits, are multiples of 8 bits.
■To separate one frame from other, a 1byte flag is
added to the beginning and end of frame.
■The flag, composed of protocol dependent special
characters which signals start or end of the frame.
A frame in a character-oriented protocol
Character-oriented Framing
■ Was popular only when text was exchanged by the DLL.
■ Flag used, could be selected as any character which is not
used for text communication. As we send now other types of
information such graphs, audio and video, the pattern used for
flag could be the part of information.
■ If receiver encounters this pattern in the middle of the data,
thinks it has reached the end of frame.
■ Solution is byte-stuffing strategy was added in this approach.
Byte stuffing and unstuffing
Character-oriented Framing
■In byte stuffing, a special byte is added to the data
section of the frame when there is a character with the
same pattern as that of the flag.
■i.e Data section is stuffed with a special extra byte
called escape character. This approach presents
another problem in data communication.
■The universal coding systems, unicode, in use today,
have 16 or 32 bit characters that conflict with 8-bit
characters.
■Therefore, next approach is used
Bit-oriented Framing
■ Data section of a frame is a sequence of bits to be interpreted
by the upper layer as text, graphs, video and so on.
■ Delimiter used to separate one frame from another and used
in the beginning and end of frame is 8-bit pattern
flag(01111110).
■ Flag can create same problem. If flag pattern in present in the
frame, need to inform the receiver that , this is data portion of
the frame, not end of frame.
■ This strategy is called bit stuffing.
■ In bit stuffing, if a 0 and five consecutive 1 bits are
encountered, an extra 0 bit added .
■ Which is removed from the data by the receiver.
A frame in a bit-oriented protocol
Bit stuffing and unstuffing
Flow and Error Control
⮚ Data Communication requires at least two devices
working together, one to send and other to receive.
⮚For communication and exchange of information, a
good coordination is must.
⮚Most important responsibilities of DLL are Flow
Control and Error Control.
⮚These functions together are called data link control.
Flow control at the data link layer
Flow control
■When an entity produces items and another entity
consumes them, there should be balance between
them.
■If items produced faster or slower compared the rate
at which it is consumed in faster/slower rate, the
systems becomes less efficient.
■Flow Control is to prevent the data items at the
consumer sites.
■In DC at DLL, we need 4 entities N/W & DLL at
sending and receiving nodes.
■DLL at sending pushes frames towards the DLL in
receiving nodes.
Flow control
■ If the receiving node cannot deliver the frames in the same
rate to the N/W Layer, it becomes overwhelmed with the
frames.
■ FC mechanism should send the feedback to the sending
device to stop or slow down the transmission of frames.
■ At sending and receiving nodes, buffers are used at DLL.
■ A buffer is a set of memory locations that can hold packets at
the sender and receiver.
■ FC communication occur by sending signals from consumer to
producer.
■ When buffer is full, it informs sender at DLL to stop pushing
frames.
Example 111.1
The above discussion requires that the consumers
communicate with the producers on two occasions: when
the buffer is full and when there are vacancies.
If the two parties use a buffer with only one slot, the
communication can be easier.
Assume that each data-link layer uses one single memory
slot to hold a frame.
When this single slot in the receiving data-link layer is
empty, it sends a note to the network layer to send the next
frame.
Error control (EC)
■Since Underlying physical N/w is not fully reliable,
EC is required at the DLL to prevent receiving node
from delivering corrupted packets to its N/W Layer.
■EC at DLL is implemented using one of the following
methods
i) If frame is corrupted, it is silently discarded; if it is
not corrupted, packet is delivered N/W layer.
ii) If frame is corrupted, it is silently discarded; if it is
not corrupted, an acknowledgment is sent to the
sender.
Combination of Error control & Flow control
i) Error Control & Flow Control can be combined.
ii) An Acknowledgment that is sent for flow control
can also be used for error control to send the sender
the packet has arrived uncorrupted.
iii) Lack of Acknowledgment means that there is a
problem in the sent frame.
Connectionless and Connection-Oriented
⮚A DLC protocol can be either connectionless or
connection-oriented.
Connectionless Protocol:
⮚Frames are sent from one node to another without
any relationship between the frames, each frame is
independent.
⮚Connectionless means there is no connection
between the frames.
⮚Frames are not numbered and there is no sense of
ordering.
Eg: Most of DLL protocols for LANs are
connectionless protocols.
Connection-oriented Protocol
■ A logical connection should be established between the two
nodes (Setup phase).
■ All frames that are related to each other are transmitted
(Transfer phase)
■ A Logical connection is terminated(teardown phase).
■ Frames are numbered and sent in order.
■ If they are not received in order, the receiver needs to wait
until all frames belonging to the same set are received and
then deliver them in order to Network Layer.
🡪 Rare in wired LANs, but we can see them in some PPP
protocols, wireless LANs & WANs.
11-2 DATA-LINK LAYER PROTOCOLS
•Traditionally four protocols have been defined for the data-
link layer to deal with flow and error control:
Simple, Stop-and-Wait, Go-Back-N, and Selective-Repeat.
Although the first two protocols still are used at the data-
link layer, the last two have disappeared.
The behavior of DLL protocols can be better shown as a
finite state machine( FSM)
Finite State Machines
■A FSM is thought of as a machine with a finite
number of states.
■A machine is always in one of the state until an event
occurs.
■Each event is associated with two reactions
i) Defining the list of actions to be performed
ii)Determining the next state(Which can be same as
current state).
▪ One of the state must be defined as the initial state,
the state in which machine starts when turns on.
FSMs
FSMs
■Machine with three states.
■There are only 3 possible events and 3 actions.
■Machine starts with state1.
🡪 If event1 occurs, the machine performs action 1 & 2
& enters in to state2.
🡪 When machine is in state2, two events may occur.
🡪 If event 2 occurs, the machine perform action3 and
remains in the same state.
🡪 If event 3 occurs, machine performs no action, but
moves to state 1.
Simple Protocol
⮚ First protocol is a simple protocol with neither flow
nor error control.
⮚ We assume that the receiver can immediately handle
any frame it receives.
⮚In other words, the receiver can never be overwhelmed
with incoming frames.
⮚Figure below shows the layout for this protocol.
⮚DLL at sender gets a packet from N/W Layer, makes a
frames out of it and sends the frame.
⮚DLL at the receiver side, extracts the packet from the
frame and delivers the packet to its N/W layer.
Simple protocol
FSM for the simple protocol
Example 11.2
Figure below shows an example of communication using
this protocol. It is very simple.
The sender sends frames one after another without even
thinking about the receiver.
Flow diagram for Example 11.2
Stop-and-Wait Protocol
⮚Second protocol is called the Stop-and-Wait protocol, which
uses both flow and error control.
⮚In this protocol, the sender sends one frame at a time and
waits for an acknowledgment before sending the next one.
⮚To detect corrupted frames, we need to add a CRC to each
data frame.
⮚When a frames arrives at the receiver site, it is checked, if
its CRC is incorrect, the frame is incorrect & silently
discarded.
⮚Silence is an alert to the sender that frame is corrupted or
lost.
Stop-and-Wait Protocol (Continued)
⮚Every time sender sends a frame, it starts a timer and if ack.
arrives before timer expires, timer is stopped and next frame is
transmitted.
⮚If timer expires before ack., frame is retransmitted because
sender assumes that frame is corrupted or lost.
⮚This means that Sender needs to keep a copy of the sent
frame until he receives the ack.
⮚When the corresponding acknowledgment arrives, the sender
discards the frame and send the next frame if it is ready
Stop-and-wait Protocol
FSM for the stop-and-wait protocol
FSM for the stop-and-wait protocol
■ At sender side:
The sender is initially in the ready state, but it can move between
the ready state and blocking state
i) Ready state: It is waiting for a packet from the N/W layer.
🡪Sender creates a copy of the frame, starts the timer and sends
the frame. The sender moves to the blocking state.
ii)Blocking state: 3 events occur
a) if time out occurs, sender resends the saved copy of the frame and starts
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 & moves to ready state.
FSM for the stop-and-wait protocol
At receiver side:
⮚ The receiver is always in ready state. The two events
may occur
a) If an error free frame arrives, message in the frame is
delivered to the network layer and ACK is sent.
b) If a corrupted frame arrives, the frame is discarded.
Example 11.3
In the figure below first frame is sent and acknowledged.
The second frame is sent, but lost. After time-out, it is
resent.
The third frame is sent and acknowledged, but the
acknowledgment is lost.
The frame is resent. However, there is a problem with this
scheme.
The network layer at the receiver site receives two copies of
the third packet, which is not right.
Discuss how to correct this problem using sequence
numbers and acknowledgment numbers.
Flow diagram
Example 11.4
Figure below shows how adding sequence numbers and
acknowledgment numbers can prevent duplicates.
The first frame is sent and acknowledged. The second
frame is sent, but lost.
After time-out, it is resent.
The third frame is sent and acknowledged, but the
acknowledgment is lost. The frame is resent.
Flow diagram
Piggybacking
⮚The two protocols we discussed in this section are
designed for unidirectional communication, in which
data is flowing only in one direction although the
acknowledgment may travel in the other direction.
⮚Protocols have been designed in the past to allow
data to flow in both directions.
⮚However, to make the communication more
efficient, the data in one direction is piggybacked with
the acknowledgment in the other direction.
11.3 HDLC
■ High-level Data Link Control (HDLC) is a bit-
oriented protocol for communication over point-
to-point and multipoint links.
■ It implements the Stop-and-Wait protocol we
discussed earlier. Although this protocol is more a
theoretical issue than practical, most of the
concept defined in this protocol is the basis for
other practical protocols such as PPP
11.46
11.3.1 Configurations and Transfer
Modes
HDLC provides two common transfer modes that
can be used in different configurations: normal
response mode (NRM) and asynchronous
balanced mode (ABM).
In normal response mode (NRM), the station
configuration is unbalanced. We have one primary
station and multiple secondary stations. A primary
station can send commands; a secondary station
can only respond. The NRM is used for both point-
to-point and multipoint links, as shown in Figure
11.14.
11.47
11.48
In ABM, the configuration is balanced. The link is
point-to-point, and each station can function as a
primary and a secondary (acting as peers), as
shown in Figure 11.15.
This is the common mode today.
11.49
11.3.2 Framing
To provide the flexibility necessary to support all the
options possible in the modes and configurations,
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 data-link user data and control
information relating to user data (piggy backing).
S-frames are used only to transport control
information.
U-frames are reserved for system management.
Information carried by U-frames is intended for
managing the link itself.
11.50
Each frame in HDLC may contain up to six fields, as
shown in Figure 11.16: a beginning flag field, an
address field, a control field, an information field, a
frame check sequence (FCS) field, and an ending
flag field.
In multiple-frame transmissions, the ending flag of
one frame can serve as the beginning flag of the
next frame.
11.51
Let us now discuss the fields and their use in
different frame types.
❑ Flag field. This field contains synchronization
pattern 01111110, which identifies both the
beginning and the end of a frame.
❑ 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
station creates the frame, it contains a from
address. The address field can be one byte or
several bytes long, depending on the needs of the
network.
11.52
❑ Control field. The control field is one or two bytes
used for flow and error control.
❑ Information field. The information field contains the
user’s data from the network layer or management
information. Its length can vary from one network to
another.
❑ FCS field. The frame check sequence (FCS) is the
HDLC error detection field. It can contain either a 2- or
4-byte CRC.
11.53
The control field determines the type of frame and defines
its functionality. So let us discuss the format of this field in
detail.
The format is specific for the type of frame, as shown in
Figure 11.17
11.54
Control Field for I-Frames
■ 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. The next 3
bits, called N(S), define the sequence number of the
frame. Note that with 3 bits, we can define a sequence
number between 0 and 7. The last 3 bits, called N(R),
correspond to the acknowledgment number when
piggybacking is used.
■ The single bit between N(S) and N(R) is called the P/F bit.
The P/F field is a single bit with a dual purpose. It has
meaning only when it is set (bit = 1) and can mean poll or
final. It means poll when the frame is sent by a primary
station to a secondary (when the address field contains the
address of the receiver). It means final when the frame is
11.55 sent by a secondary to a primary (when the address field
Control Field for S-Frames
■ Supervisory frames are used for flow and error control
whenever piggybacking is either impossible or inappropriate.
■ S-frames do not have information fields. If the first 2 bits of
the control field are 10, this means the frame is an S-frame.
■ The last 3 bits, called N(R), correspond to the
acknowledgment number (ACK) or negative acknowledgment
number (NAK), depending on the type of S-frame.
■ The 2 bits called code are used to define the type of S-frame
itself.
11.56
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 of the
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
acknowl edges 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 N(R) is the acknowl
edgment number.
11.57
❑ Reject (REJ). If the value of the code subfield is 01, it is an REJ S-frame.
This is a NAK frame, but not like the one used for Selective Repeat ARQ. It is
a NAK that can be used in Go-Back-N ARQ to improve the efficiency of the
process by informing the sender, before the sender timer expires, that the last
frame is lost or damaged. The value of N(R) is the negative acknowledgment
number.
❑ 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
11.58
Control Field for U-Frames
■ Unnumbered frames are used to exchange session
management and control information between connected
devices.
■ U-frames contain an information field, but one used for
system management information, not user data. As with S-
frames, however, much of the information carried by U-
frames is contained in codes included in the control field.
■ U-frame codes are divided into two sections: a 2-bit prefix
before the P/ F bit and a 3-bit suffix after the P/F bit.
Together, these two segments (5 bits) can be used to create
up to 32 different types of U-frames.
11.59
11-4 Point to Point Protocol (PPP)
⮚One of the most common protocols for point-to-point
access is the Point-to-Point Protocol (PPP).
⮚Today, millions of Internet users who need to connect their
home computers to the server of an Internet service provider
use PPP.
⮚To control and manage the transfer of data, there is a need
for a point-to-point protocol at the data-link layer. PPP is by
far the most common.
Services
•The designers of PPP have included several services
to make it suitable for a point-to-point protocol, but
have ignored some traditional services to make it
simple.
Services provided by Point-point protocol
Defines
1. format of the frame to be exchanged between the devices.
2. How two devices can negotiate the establishment of the link
and the exchange of data.
3. How N/W layer data are encapsulated in the data link frame.
4. How two devices can authenticate each other.
5. Provides Multiple N/W services supporting a variety of N/W
Layer protocols.
6. Connection over multiple links is provided by new version of
PPP.
7. N/W address configuration. Useful when a home user needs
temporary N/W address to connect to Internet
Services not provided by ppp
■PPP does not provide flow control. Sender can
send frames one after another w/o concerning
about overwhelming receivers buffer.
■Simple mechanism for error control. A CRC
field is used to detect errors. If frame is
corrupted , frame is silently discarded. Upper
Layer protocol need to take care of this.
■Does not provide addressing mechanism to
handle frames in a multipoint configuration.
Framing
PPP frame
format
Framing
⮚PPP uses a character-oriented (or byte-oriented) frame.
Figure below shows the format of a PPP frame. PPP is a
byte oriented protocol
Flag:🡪 A PPP frame starts and ends with a one byte flag
with the bit pattern 0111110. The flag is treated as a
byte.
Address:🡪 The address field is constant value and set to
11111111(broadcast address)
Control🡪 The field is set to a constant value 11000000.
PPP doe not provide FC and limited EC. Two parties can
negotiate and omit this byte.
Framing
Protocol🡪 defines what is being carried in the data field either
user data or other information.
Default size is 2 bytes, two parties can negotiate to use only 1
byte.
Payload field🡪 carries use data or other info.
Data field is a sequence of bytes with the default of maximum of
1500 bytes, But can be changed during negotiation.
The data field is byte stuffed if the flag byte pattern appears in
the 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/negotiated value.
FCS:🡪 FCS is simply a 2/4 byte standard CRC
Byte stuffing
■In PPP flag is byte. The flag byte need to be escaped
whenever it appears in the data section of the frame.
■The escape byte is 01111101 , which means that every
time the flag like pattern appears in the data, this
extra byte is stuffed to tell the receiver the next byte
is not a flag.
■ PPP is a byte-oriented protocol using byte
stuffing with the escape byte 01111101.
Transition Phases
⮚A PPP connection goes through phases which can be
shown in a transition phase diagram.
Transition phases
Transition phases
Dead: In this phase link is not used. There is no active
carrier and line is quiet.
Establish: When one of the node starts communication,
connection goes into establish phase. Options are
negotiated between two parties.
If negotiation is successful, system goes to
authentication phase or directly to networking phase.
Link control packet are used in this phase.
Authenticate: Two nodes can negotiate and skip this
phase as it is optional. If not to skip, authentication
packets are used.
Transition phases
Network: Negotiation for the network layer
protocols takes place. PPP specifies that two
nodes establish a N/W agreement before data
at the N/w can be exchanged.
PPP supports multi protocols at N/W Layer.
If a node is running multi protocol
simultaneously at the N/W Layer, receiving
node needs to know which protocol will
receive the data.
Transition phases
Open: Data transfer takes place.
When a connection reaches this phase,
exchange of data packets takes place
Connections remains in this phase until one of
the endpoints wants to terminate the
connection
Terminate: Connection is terminated. Several
packets are exchanged b/w the two ends for
house cleaning and closing of the link
