Chapter 3: Data Link Layer

0
 Contents
(1) Functions of the data link layer
(2) Framing
(3) Error control
(3.1) Error detection
(3.2) Error correction
(4) Flow control
(5) Definitions
(6) Elementary data link protocols
(7) Sliding window protocols
(8) Example data link protocol - PPP

1
Placement of Data Link Layer Protocol

2
 (1) Functions

• Providing service interface to the network

layer via Frames
• Dealing with transmission errors
• Regulating data flow
•Slow receivers not swamped by fast senders

3
(1) Functions

4
(2) Framing
 A function of the data link layer.
 Provides a way for a sender to transmit a set
of bits that are meaningful to the receiver.
 Frames have headers and/or trailer that
contain information such as the source and
the destination addresses of the frame, error-
checking codes.

5
 (2.1) Frame
• A frame is a digital data transmission unit
in computer networking and telecommunication
systems.
•A frame is a simple container for a single network
packet in a packet switched systems,.
• A frame is a repeating structure supporting time-
division multiplexing in other telecommunications
systems.
•The data link layer packs the bits into frames.
• Takes the packets from the Network Layer and
encapsulates them into frames.
6
(2.2) Problems in Framing

 Detecting start of the frame: by looking out for

special sequence of bits that marks the beginning of
the frame i.e. SFD (Starting Frame Delimeter).
 How do station detect a frame: Every station listen
to link for SFD pattern through a sequential circuit. If
SFD is detected, sequential circuit alerts station.
Station checks destination address to accept or reject
frame.
 Detecting end of frame: When to stop reading the
frame. Use EFD (Ending Frame Delimeter)
7
(2.3) Types of Framing

1. Fixed size – Here no need to provide boundaries to

the frame, length of the frame itself acts as delimiter.
• Drawback: It suffers from internal fragmentation
if data size is less than frame size
• Solution: Padding

8
(2.3) Types of Framing

2. Variable size – Here EFD is needed to define end of

frame as well as SFD in beginning of next frame to
distinguish. This can be done in two ways:
• Length field – We can introduce a length field in the frame
to indicate the length of the frame. Used in Ethernet. The
problem with this is that sometimes the length field might
get corrupted .
• End Delimeter (ED) – We can introduce an ED(pattern) to
indicate the end of the frame. Used in Token Ring. The
problem with this is that ED can occur in the data. This can
be solved by Character/Byte Stuffing.

9
(2.3.1) Character Count

A character stream (a) Without errors.

(b) With one error.
10
 (2.3.2) Byte Stuffing

(a) A frame delimited by flag bytes.

(b) Four examples of byte sequences before and
after stuffing.
11
 (2.3.3) Bit Stuffing

(a) The original data.

(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory
after de-stuffing.
12
(2.3.4) Physical Layer Coding Violation
Used only when physical medium contains some
redundancy
 1: high-low
 0: low-high
high-high and low-low are used for delimiting frames

13
 (3) Error Control
 Thetechnique of detecting and correcting
blocks of data during communication.

 Errorcontrol in data link layer is the process

of detecting and correcting data frames that
have been corrupted or lost during
transmission.

14
(3) Error Control
 Acknowledgements: A special acknowledgment
(ACK) frame that the receiver returns to the sender
indicating the correct receipt of a frame. In some
systems, the receiver also returns a negative
acknowledgment (NACK) for incorrectly-received
frames.
 Timers: Retransmission timers are used to resend
frames if an ACK or NACK is lost.
 Sequence Numbers: Retransmissions introduce the
possibility of duplicate frames. Sequence numbers in
each frame can distinguish between new frames and
old copies. 15
(3) TYPES OF ERRORS
• Single bit error : only one bit of data unit is changed
from 1 to 0 or from 0 to 1.

• Burst error : two or more bits in data unit are changed

from 1 to 0 from 0 to 1. It is not necessary that only
consecutive bits are changed. The length of burst
error is measured from first changed bit to last
changed bit

16
(3.1.1) Error-Detecting Codes
• Cyclic redundancy check (CRC) : A technique in which a
certain number of check bits, often called a checksum, are
appended to the message being transmitted.
• The receiver can determine whether or not the check bits
agree with the data, to ascertain with a certain degree of
probability whether or not an error occurred in transmission
• The CRC is based on polynomial arithmetic, in particular, on
computing the remainder of dividing one polynomial in
GF(2) (Galois field with two elements) by another.
• Can be easily implemented with small amount of hardware
• Shift registers
• XOR (for addition and subtraction)

17
(3.1.1) Error-Detecting Codes
• The divisor in a cyclic code is normally called the generator
polynomial or simply the generator G(x).
• It should have at least two terms.
• The coefficient of the term x0 should be 1.
• It should not divide xt + 1, for t between 2 and n − 1.
• It should have the factor x + 1
• Sending Process:
1. Multiply Message [M(x)] by xn
2. Divide xnM(x) by G(x)
3. Ignore the quotient and keep the reminder C(x)
4. Prepare and send F(x) = xnM(x)+C(x)
• Receiving Process:
1. Receive F’(x)
2. Divide F’(x) by G(x)
3. Accept if remainder is 0, reject otherwise 18
(3.1.2) Error-Detecting Codes

Calculation of the
polynomial code
checksum.

19
 (3.1.3) Error-Detecting Codes

Popular generator polynomials are:

CRC-8: G(x) = x8 + x2 + x +1.

CRC-12: G(x) = x12 + x11 + x3 + x2 + x +1.
CRC-16: G(x) = x16 + x15 + x2 + 1.
CRC-32: G(x) = x32 + x26 + x23 + x22 + x16 + x12 +
x11 + x11 + x8 + x7 + x5 + x4 + x2 + x +1.
CRC-CCITT : G(x) = x16 + x12 + x5 + 1.

20
 (3.2.1) Error-Correcting Codes
Hamming code: A set of error-correction codes that
can be used to detect and correct the errors that can
occur when the data is transmitted or stored from the
sender to the receiver.
Redundant bits – Extra binary bits that are generated
and added to the information-carrying bits of data
transfer to ensure that no bits were lost during the data
transfer.
The number of redundant bits = 2^r ≥ m + r + 1 where,
r = redundant bit, m = data bit
Suppose the number of data bits is 7, then the number of
redundant bits = 2^4 ≥ 7 + 4 + 1
Thus, the number of redundant bits= 4 21
 (3.2.2) Error-Correcting Codes
Parity bits – A bit appended to a data of binary bits to
ensure that the total number of 1’s in the data is even or
odd. Parity bits are used for error detection. There are
two types of parity bits:
 Even parity bit
 Odd Parity bit

The Hamming Code is simply the use of extra parity

bits to allow the identification of an error.

22
(3.2.3) Hamming code Algorithm
 Write the bit positions starting from 1 in binary form (1, 10,
11, 100, etc).
 All the bit positions that are a power of 2 are marked as parity
bits (1, 2, 4, 8, etc).
 All the other bit positions are marked as data bits.
 Each data bit is included in a unique set of parity bits, as
determined its bit position in binary form.
a. Parity bit 1 covers all the bits positions whose binary
representation includes a 1 in the least significant
position (1, 3, 5, 7, 9, 11, etc).
b. Parity bit 2 covers all the bits positions whose binary
representation includes a 1 in the second position from
the least significant bit (2, 3, 6, 7, 10, 11, etc).
23
(3.2.4) Hamming code Algorithm (ctd.)
c. Parity bit 4 covers all the bits positions whose binary
representation includes a 1 in the third position from
the least significant bit (4–7, 12–15, 20–23, etc).
d. Parity bit 8 covers all the bits positions whose binary
representation includes a 1 in the fourth position from
the least significant bit bits (8–15, 24–31, 40–47, etc).
e. In general, each parity bit covers all bits where the bitwise
AND of the parity position and the bit position is
non-zero.
 Since we check for even parity set a parity bit to 1 if the total
number of ones in the positions it checks is
odd.
 Set a parity bit to 0 if the total number of ones in the positions
it checks is even.
24
 (3.2.5) Hamming Code Example
20 21 22 23

contains data bits

contains parity bits

For ‘H’ (ASCII 1001000) we have

20 21 22 23
1 0 0 1 0 0 0

Parity bits will be:

20 = 0 21 = 0 22 = 1 23 = 0
25
 (3.2.6) Hamming Code Example

Use of a Hamming code to correct burst errors

26
(4) Flow Control
• …………

27
 (4) Flow Control
• the process of managing the rate of data transmission
between two nodes to prevent a fast sender from
overwhelming a slow receiver. (So that Receiver does not
lose data)
• Important because it is possible for a sending computer
to transmit information at a faster rate than the
destination computer can receive and process it.
• This can happen if the receiving computers have a heavy traffic
load in comparison to the sending computer,
• or if the receiving computer has less processing power than the
sending computer.

28
 (5) Protocol Definitions

Continued →

Some definitions needed in the protocols to follow.

These are located in the file protocol.h.
29
Protocol
Definitions
(ctd.)

Some definitions
needed in the
protocols to follow.
These are located in
the file protocol.h.
30
(6) Elementary Data Link Protocols

• An Unrestricted Simplex Protocol

• A Simplex Stop-and-Wait Protocol
• A Simplex Protocol for a Noisy Channel

31
(6.1) Unrestricted Simplex Protocol
• Data is transmitted in one direction only.
• The sender (A) and receiver(B) hosts are always ready.
• Infinite buffer space is available.
• Processing time can not be accounted.
• No transmission error occur.

32
(6.1)
Unrestricted
Simplex
Protocol

33
(6.2) Simplex Stop-and-Wait Protocol
• Sender (A) sends one frame and waits for acknowledgement
(ACK) from the receiver (B).
• After receiving ACK arrives, the sender sends the next frame.

34
(6.2)
Simplex
Stop-and-
Wait
Protocol

35
(6.3)A Simplex Protocol for a Noisy Channel

What if ACK frame is lost or damaged?

36
(6.3)A Simplex Protocol for a Noisy Channel

37
(6.3)A Simplex Protocol for a Noisy Channel

38
 (6.3)A Simplex Protocol for a Noisy Channel

A positive
acknowledgement
with retransmission
protocol.
Continued → 39
(6.3) A Simplex Protocol for a Noisy Channel (ctd.)

A positive acknowledgement with retransmission protocol.

40
 (7) Sliding Window Protocols

 A One-Bit Sliding Window Protocol

 A Protocol Using Go Back N
 A Protocol Using Selective Repeat

41
 (7) Sliding Window Protocols (2)

A sliding window of size 1, with a 3-bit sequence number.

(a) Initially.
(b) After the first frame has been sent.
(c) After the first frame has been received.
(d) After the first acknowledgement has been received.

42
(7.1.1) A One-Bit Sliding Window Protocol

Continued → 43
(7.1.2) A One-Bit Sliding Window Protocol (ctd.)

44
 (7.1.3) A One-Bit Sliding Window Protocol

 Two scenarios for protocol 4. (a) Normal

case. (b) Abnormal case. The notation is (seq, ack,
packet number). An asterisk indicates where a
network layer accepts a packet. 45
>1bit Sliding Window

46
>1-bit Sliding Window

47
>1-bit Sliding Window

48
N-bit Sliding Window

49
50
51
RR0
/RNR0

52
53
Size of Window ?

54
Size of Window ?

2n -1

55
 Piggybacking?

Piggybacking is a method of attaching

acknowledgment to the outgoing data Frame.

56
 (7.2.1) A Protocol Using Go Back N

Pipelining and error recovery. Effect on an error when

(a) Receiver’s window size is 1.
(b) Receiver’s window size is large.

57
(7.2.2)
Sliding
Window
Protocol Using
Go Back N

Continued → 58
(7.2.3) Sliding Window Protocol Using
Go Back N

Continued → 59
(7.2.4) Sliding Window Protocol Using Go
Back N

Continued → 60
(7.2.5) Sliding Window Protocol Using Go
Back N

61
(7.2.6) Sliding Window Protocol Using Go
Back N
 Simulation of multiple timers in software.

62
(7.3.1) A Sliding Window Protocol Using Selective Repeat

Continued → 63
(7.3.2) A Sliding Window Protocol Using Selective Repeat

Continued → 64
(7.3.3) A Sliding Window Protocol Using Selective Repeat

Continued → 65
(7.3.4) A Sliding Window Protocol Using Selective Repeat

66
 (7.3.5) A Sliding Window Protocol Using Selective Repeat

(a) Initial situation with a window size seven.

(b) After seven frames sent and received, but not acknowledged.
(c) Initial situation with a window size of four.
(d) After four frames sent and received, but not acknowledged.

67
(8) HDLC

68
(9) PPP
 Point - to - Point Protocol (PPP) is a communication
protocol of the data link layer that is used to transmit
multiprotocol data between two directly connected
(point-to-point) computers.
 It is a byte - oriented protocol that is widely used in
broadband communications having heavy loads and high
speeds.
 Since it is a data link layer protocol, data is transmitted
in frames.
 It is also known as RFC 1661.
◦ Read RFC 1661: http://www.faqs.org/rfcs/rfc1661.html

69
(9.1) Components of PPP
 Link Control Protocol (LCP) − Responsible for
establishing, configuring, testing, maintaining and
terminating links for transmission. It also imparts
negotiation for set up of options and use of features by
the two endpoints of the links.
 Authentication Protocols (AP) − These protocols
authenticate endpoints for use of services. The two
authentication protocols of PPP are −
◦ Password Authentication Protocol (PAP)
◦ Challenge Handshake Authentication Protocol
(CHAP)

70
(9.1) Components of PPP
 Network Control Protocols (NCPs) − These protocols are
used for negotiating the parameters and facilities for the network
layer. For every higher-layer protocol supported by PPP, one NCP is
there. Some of the NCPs of PPP are −
◦ Internet Protocol Control Protocol (IPCP)
◦ OSI Network Layer Control Protocol (OSINLCP)
◦ Internetwork Packet Exchange Control Protocol (IPXCP)
◦ DECnet Phase IV Control Protocol (DNCP)
◦ NetBIOS Frames Control Protocol (NBFCP)
◦ IPv6 Control Protocol (IPV6CP)

71
(9.1) Components of PPP

72
(9.2) PPP – Frame Format
 The PPP full frame format for
unnumbered mode operation.

73
 (9.2) PPP Frame Format
 Flag − 1 byte that marks the beginning and the end of the frame. The
bit pattern of the flag is 01111110.
 Address − 1 byte which is set to 11111111 in case of broadcast.
 Control − 1 byte set to a constant value of 11000000.
 Protocol − 1 or 2 bytes that define the type of data contained in the
payload field.
 Payload − This carries the data from the network layer. The maximum
length of the payload field is 1500 bytes. However, this may be
negotiated between the endpoints of communication.
 FCS − It is a 2 byte or 4 bytes frame check sequence for error
detection. The standard code used is CRC (cyclic redundancy code)

74
(9.3) PPP Frame Format

75
 (9.3) PPP Frame Format
 Byte Stuffing in PPP Frame − Byte stuffing is used is
PPP payload field whenever the flag sequence appears in
the message, so that the receiver does not consider it as
the end of the frame.
 The escape byte, 01111101, is stuffed before every byte
that contains the same byte as the flag byte or the escape
byte.
 The receiver on receiving the message removes the escape
byte before passing it onto the network layer.

76