Chapter Four

Data Link Layer

– Understand the 2nd Layer (Data link layer) of OSI model

– Study the design principles for the layer

– Services the layer provides to the above layer

– Flow control mechanisms that are implemented

– Error detection techniques that can be applied

– Error correction mechanisms

2
 Introduction
• The second layer in OSI reference model is called the data link layer
• The data link layer has a number of specific functions it can carry out.
• These functions include:
– Providing a well-defined service interface to the network layer.
– Regulating the flow of data so that slow receivers are not swamped
by fast senders.
– Dealing with transmission errors.

3
 Introduction
• To accomplish these goals:
– Takes the packets it gets from the network layer and
encapsulates them into frames for transmission
– Each frame contains
• frame header,
• payload field for holding the packet,
• frame trailer

4
Services Provided to the Network Layer
• The principal service is transferring data from the network layer on
the source machine to the network layer on the destination
machine
• Three services that are commonly provided are:
– Unacknowledged connectionless service.
• The source machine send independent frames to the
destination machine without having the destination machine
acknowledge them
• If a frame is lost due to noise on the line, no attempt is made
to detect the loss or recover from it in the data link layer
• Appropriate when:
– the error rate is very low so that recovery is left to higher
layers
– appropriate for real-time traffic, such as voice, in which
late data are worse than bad data
5
– Acknowledged connectionless service.
• Each frame sent is individually acknowledged
• The sender knows whether a frame has arrived correctly. If
it has not arrived within a specified time interval, it can be
sent again
• For wireless
– Acknowledged connection-oriented service.
• The source and destination machines establish a
connection before any data are transferred
• Each frame sent over the connection is numbered, and the
data link layer guarantees that each frame sent is indeed
received exactly once
• Three way handshake 6
 Fragmentation
• One of the tasks of data link layer

• The fragment is called frame

• Why?

– The buffer size of the receiver may be limited.

– With smaller frames, errors are detected sooner, and a

smaller amount of data needs to be retransmitted.

– To prevent monopoly of a shared medium by one station

• Where is the DATA??

• Three approaches to find frame:

– Character oriented framing

– Length counts - fixed length

– Bit oriented protocols (flags)

8
 Framing

A character stream. (a) Without errors. (b) With one error.

9
 Framing (2)

(a) A frame delimited by flag bytes.

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
11
memory after destuffing.
 Flow control
• assuring that a transmitting entity does not overwhelm a

receiving entity with data

– Slow receivers not swamped by fast senders

• it is an end-to-end mechanism for regulating traffic between

• Different methods

• Stop-and-Wait Flow Control

• Sliding-Window Flow Control 12

• Source transmits frame

• Destination receives frame and replies with

acknowledgement

• Source waits for ACK before sending next frame

• Only one frame can be in transit at a time

• Destination can stop flow by not sending ACK

• Works well for a few frames

• Allow multiple frames to be in transit

• Receiver has buffer W long

• Transmitter can send up to W frames without ACK

• Each frame is numbered

• ACK includes number of next frame expected

• Sequence number bounded by size of field (k)

– Frames are numbered modulo 2k

• Efficient

– Many frames can be in transit 14

 When an electro magnetic signal flows from one point to

another, several things can change its shape and timing

 If the signal is carrying encoded binary data, such changes

can alter the meaning of the data

Error in data communication

15
Causes of Error

 Attenuation: any reduction in the strength of a signal

 Delay Distortion: different propagation speeds of signals at

different frequencies

 Noise: additional signals inserted between transmitter and receiver

16
Types of error
 Single bit error

 only one bit in a data unit (byte, character, packet, ...) has

changed

 Burst error

 2 or more bits in the data unit have changed

 What shall be done to effect good communication?

• Eliminate causes---Impossible!

• Detect and Correct  Solution 17

 Redundancy: adding additional bits that help in checking

errors

 Two redundancy schemes exist

• Trivial: sending every data unit more than once

• Systematic: appending shorter group of bits drawn from

the data systematically

18
Error Detection (Cont…)
 Two Methods
• Parity bit
• Cyclic Redundancy Check (CRC)

19
 Parity Bit
• Parity
 a redundant bit, called a parity bit, is added to
every data unit so that the total number of 1s in
the unit (including the parity bit) becomes even
(or odd for odd-parity); this method can detect all
single-bit errors; it can detect burst errors only if
the total number of errors in each data unit is odd
– Even number of bit errors goes undetected

20
Cyclic Redundancy Check (CRC)
 based on binary division

 the CRC is appended to the end of a data unit so that

the resulting data unit becomes exactly divisible by a

second, predetermined binary number

21
CRC (Cont…)
• append  a string of n 0s in to the data unit ( n = divisor bits # –1)

• divide result by the divisor using binary division

• remainder of division becomes the CRC

• replace the appended 0s with CRC

• Send data (original + CRC)

• Receiver divides the whole data by divisor

‾ If remainder ,ERROR

‾ Otherwise  NO ERROR
22
23
24
 Error Control
• Detection and correction of errors

– Lost frames

– Damaged frames

• Automatic repeat request

– Error detection

– Positive acknowledgment

– Retransmission after timeout

– Negative acknowledgement and retransmission

 Positive acknowledgment (ACK) for successfully received

packets

 Retransmission can be made if:

• Time expires (lost or corrupted)

• Received in error (NAK)

 Popular ARQ protocols are: Stop-and-wait, Selective Repeat

and Go-Back-N 26
Stop-and-wait ARQ (SWA)
 Next packet is sent after previous packet acknowledgment

 Retransmission if time expires

 Numbered only to identify corresponding data packet and

ACK

 Reasons for retransmission

• Damaged packets

• Lost packets

• Lost acknowledgment 27
Normal operation

28
Lost frame
29
Lost ack

30
Delayed ack

31
 Go-Back-N ARQ
 Continuous packet transmission like SRA

 Unlike SRA Out of order packets are discarded

 Time out packet and packets following are retransmitted

 Unlike SRA no buffering

 Like SWA no re-sequencing overhead

32
 Go-Back-4: 4 frames are outstanding; so go back 4

fr fr fr fr fr fr fr fr fr fr fr fr fr fr time
0 1 2 3 4 5 6 3 4 5 6 7 8 9
A

B
A A A Out-of-sequence frames A A A A A A
C C C C C C C C C
K K K K K K K K K
1 2 3 error 4 5 6 7 8 9

ACKing next frame expected

33
 Selective Repeat ARQ (SRA)
 Continuously transmission packets

 Packets are assigned sequence number

 Arrival of packets can be in any order

 Packets are buffered before delivery

 Increases data transfer rate compared to SWA

 Retransmission for

• Damaged packets

• Lost packets
34
• Lost acknowledgments
 fr fr fr fr fr fr fr fr fr fr fr fr fr fr time
0 1 2 3 4 5 6 2 7 8 9 10 11 12
A

B A A N A A A A A A A A A
C C A C C C C C C C C C
K K K K K K K K K K K K
1 2 2 2 2 2 7 8 9 1 1 1
error 0 1 2

35