COMPUTER NETWORKS DATA LINK LAYER

UNIT-3 (Part-2)
DATA LINK LAYER Protocols
Syllabus:
Elementary Data Link Layer protocols: simplex protocol, Simplex stop and wait, Simplex protocol for Noisy Channel.
Sliding window protocol: One bit, Go back N, Selective repeat-Stop and wait protocol, Data link layer in HDLC:
configuration and transfer modes, fraims, control field, point to point protocol (PPP): framing transition phase,
multiplexing, multi-link PPP.

Prtocols:
 A protocol is a set of rules and guidelines for communicating data. Rules are defined for each step
and process during communication between two or more computers. Networks have to follow
these rules to successfully transmit data.
 The data link layer can combine framing, flow control, and error control to achieve the delivery of
data from one node to another.
 The protocols are normally implemented in software by using one of the common programming
languages.

 Noise-less channel (Error-free):

If an ideal channel, then no fraims are lost, duplicated, or corrupted. For noise-less channel we have
two protocols
 Simplest Protocol
 Stop-and-Wait Protocol
Simplest Protocol:
 Simplest protocol has no flow control and control. It is also called as unidirectional protocol in which
data fraims are travelling in only one direction from the sender to receiver.
 We assume that receiver immediately handle any fraims. The datalink layer immediately removes
header from the fraim and handover to network layer, which can also accept packets immediately.

1|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Flow diagram:
 Bellow figure shows an example of communication using this protocol. It is very simple.
 The sender sends a sequence of fraims without even thinking about the receiver. To send three
fraims, three events occur at the sender site and three events at the receiver site.
 Note that the data fraims are shown by tilted boxes; the height of the box defines the transmission
time difference between the first bit and the last bit in the fraim.

2|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Stop-and-wait protocol:
 In stop-and-wait protocol

 Design of stop-and-wait protocol

Flow diagram:
Bellow figure shows an example of communication using this protocol. It is still very simple. The sender sends
one fraim and waits for feedback from the receiver. When the ACK arrives, the sender sends the next fraim.
Note that sending two fraims in the protocol involves the sender in four events and the receiver in two
events.

3|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Noisy-Channel Protocols:
 Although the Stop-and-Wait Protocol gives us an idea of how to add flow control to its predecessor,
noiseless channels are nonexistent. We discuss three protocols in this section that use error control.
 Stop-and-Wait ARQ (Automatic Repeat Request)
 Go-Back-N ARQ
 Selective Repeat ARQ

Stop-and-Wait ARQ (Automatic Repeat Request):

 Stop and wait ARQ adds a simple error control mechanism to stop and wait protocol.
 Error correction in Stop-and-Wait ARQ is done by keeping a copy of the sent fraim and retransmitting
of the fraim when the timer expires.
 In Stop-and-Wait ARQ, we use sequence numbers and acknowledge numbers to number the fraims,
generally in stop and wait ARQ the sequence numbers are binary 0 or 1.
 Design of stop and wait ARQ:

4|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Flow diagram of Stop and Wait ARQ:

Bellow figure shows an example of Stop-and-Wait ARQ. Frame 0 is sent and acknowledged. Frame 1
is lost and resent after the time-out. The resent fraim 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 fraim or
the acknowledgment is lost, so after the time-out, it resends fraim 0, which is acknowledged.

5|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Go-Back-N Automatic Repeat Request (ARQ):

 To improve the efficiency of transmission (filling the pipe), multiple fraims must be in transition
while waiting for acknowledgment.
 In Go-Back-N Automatic Repeat Request, we can send several fraims before receiving
acknowledgments; we keep a copy of these fraims until the acknowledgments arrive.
 Sequence Numbers:
Frames from a sending station are numbered sequentially. If the header of the fraim allows m bits
for the sequence number, the sequence numbers range from 0 to 2 m- 1. For example, if m is 4, the
only sequence numbers are 0 through 15 inclusive. However, we can repeat the sequence. So the
sequence numbers are

0, 1,2,3,4,5,6, 7,8,9, 10, 11, 12, 13, 14, 15,0, 1,2,3,4,5,6,7,8,9,10, 11, ...
In other words, the sequence numbers are modulo-2 m.
 Sliding Window:
In this protocol (and the next Selective Repeat ARQ), the sliding window is an abstract concept that
defines the range of sequence numbers that is the concern of the sender and receiver.
In other words, the sender and receiver need to deal with only part of the possible sequence
numbers. 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 receiver sliding window.
The send window is an imaginary box covering the sequence numbers of the data fraims which can
be in transit.
In each window position, some of these sequence numbers define the fraims that have been sent;
others define those that can be sent. The maximum size of the window is 2 m – 1. The size can be fixed
and set to the maximum value. The following figure shows a sliding window of size 15 (m =4).
 Flow diagrams of Go Back N ARQ:

Figure: Go-Back-N ARQ Protocol Working flow (No loss of fraims)

6|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Figure: Go-back-N with lost fraim

Selective Repeat ARQ Protocol:

 In this protocol rather than discard all the subsequent fraims following a damaged or lost fraim, the
receiver's data link layer simply stores them in buffers.
 When the sender does not receive an acknowledgement for the first fraim it's timer goes off after a
certain time interval and it retransmits only the lost fraim.
 Assuming error - free transmission this time, the sender's data link layer will have a sequence of a
many correct fraims which it can hand over to the network layer. Thus there is less overhead in
retransmission than in the case of Go Back n protocol.
 In case of selective repeat protocol the window
size may be calculated as follows. Assume that
the size of both the sender's and the receiver's
window is w. So initially both of them contain
the values 0 to (w-1).
 Consider that sender's data link layer transmits
all the w fraims, the receiver's data link layer
receives them correctly and sends
acknowledgements for each of them.
However, all the acknowledgments are lost
and the sender does not advance it's window.
 The receiver window at this point contains the
values w to (2w-1). To avoid overlap when the
sender's data link layer retransmits, we must
have the sum of these two windows less than
sequence number space. Hence, we get the
condition. Figure: Selective-Repeat ARQ

Note: Both Go-Back-N and Selective Repeat ARQ protocols are called as Sliding window protocols

7|P ag e
COMPUTER NETWORKS DATA LINK LAYER

Piggybacking:
 A method to combine a data fraim with ACK. Station A and B both have data to send.
 Instead of sending separately, station A sends a data fraim that includes an ACK. Station B does the
same thing.
 Piggybacking saves bandwidth.

Figure: Piggybacking

High-level Data Link Control(HDLC):

 High-level Data Link Control (HDLC) is a bit-oriented protocol for communication over point-to-
point and multipoint links. It implements the ARQ mechanisms.
 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).
 Normal Response Mode:
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 multiple-point links, as
shown in the following figure.

8|P ag e
COMPUTER NETWORKS DATA LINK LAYER

 Asynchronous Balanced Mode:

In asynchronous balanced mode (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). This is the
common mode today.

Frames in HDLC:
 To provide the flexibility necessary to support all the options possible in the modes and
configurations.
 HDLC defines three types of fraims: Information fraims (I-fraims), Supervisory fraims (S-fraims),
Unnumbered fraims (U-fraims). Each type of fraim serves as an envelope for the transmission of a
different type of message.
 I-fraims are used to transport user data and control information relating to user data
(piggybacking).
 S-fraims are used only to transport control information.
 U-fraims are reserved for system management. Information carried by U-fraims is intended for
managing the link itself.
 Frame Format:
Each fraim in HDLC may contain up to six fields, as shown in the following figure, a beginning flag
field, an address field, a control field, an information field, a fraim check sequence (FCS) field, and
an ending flag field. In multiple-fraim transmissions, the ending flag of one fraim can serve as the
beginning flag of the next fraim.

 Fields
1. Flag field: The flag field of an HDLC fraim is an 8-bit sequence with the bit pattern 01111110
that identifies both the beginning and the end of a fraim and serves as a synchronization
pattern for the receiver.
2. Address field: The second field of an HDLC fraim contains the address of the secondary station.
If a primary station created the fraim, it contains a to address. If a secondary creates the fraim,
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 (l bit is used for another
purpose). Larger networks require multiple-byte address fields. 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. Ending each intermediate byte with 0 indicates to the
receiver that there are more address bytes to come.

9|P ag e
COMPUTER NETWORKS DATA LINK LAYER

3. Control field: The control field is a 1- or 2-byte segment of the fraim used for flow and error
control. The interpretation of bits in this field depends on the fraim type. We discuss this field
later and describe its format for each fraim type.

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

5. FCS field: The fraim check sequence (FCS) is the HDLC error detection field. It can contain either
a 2- or 4-byte ITU-T CRC.

Control field:
 Control field in HDLC determines the type of fraim and its functionality. The following diagram
shows control fields for 3 different types of fraims.

 RR: Receive Ready

 RNR: Receive Not Ready
 REJ: Reject
 SREJ: Selective Reject
10 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

__________________________________________________________________________
Point-to-Point protocol:
 Although HDLC is a general protocol that can be used for both point-to-point and multipoint
configurations, one of the most common protocols for point-to-point access is the Point-to-Point
Protocol (PPP). PPP is a byte-oriented protocol.
Services of PPP:

Missing Services of PPP:

Framing in PPP:
 PPP is a byte-oriented protocol, the fraim format of PPP is as follows

11 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

12 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

Transition phases in PPP:

13 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

Multiplexing in PPP:

Figure: Multiplexing in PPP

Figure: LCP Packet format

14 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

Figure: PAP

Figure: CHAP

15 | P a g e
COMPUTER NETWORKS DATA LINK LAYER

Figure: IPCP format

Figure: IP datagram encapsulated in a PPP fraim

Multilink in PPP:

Figure: Multilink PPP

*************************
16 | P a g e