Module 2

Data link Layer - Design issues

Functions of the Data Link Layer

 Provide service interface to the network layer with

following responsibilities

1) Framing :The data link layer needs to pack bits into

frames, so that each frame is distinguishable from
another.

2) Physical Addressing: Adding physical address of source

and destination (next hop).

3) Error Control : Dealing with transmission errors.

4) Flow Control :Regulating data flow so that slow receivers

are not swamped by fast senders
Relationship between packets and frames.
Framing

The data link layer needs to pack bits into frames, so

that each frame is distinguishable from another.
Various methods used for framing are:

i. Character Count

ii. Flag bytes with byte stuffing

iii. Flag bytes with bit stuffing

iv. Physical layer coding violation

Character Count

This framing method uses a field in a header to specify the

number of characters in the frame.

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

Flag bytes

 If the count is garbled destination will go out of

synchronization and will be unable to locate the start of the
next frame.

• For resynchronization after an error can be resolved by

having each flag byte at the start and end of the frame.

• Flag bytes is the process of adding one special byte as both

the starting and ending delimiter.
 What is byte stuffing?

 If the flag byte’s pattern occurs in the data.

 To solve this problem DLL insert a special byte (ESC) just

before the accidental flag byte in the data.

 This technique is called byte stuffing.

 Next problem can be if escape byte pattern occurs in the data.

To solve this problem DLL stuffed another ESC byte just
before this byte in the data.
Flag bytes with byte stuffing

Byte stuffing is the process of adding 1 extra byte whenever

there is a flag or escape character in the text.
Byte stuffing and unstuffing
Flag bytes with bit stuffing

 Main problem with byte stuffing is that byte is of fixed

character size i.e it assumes character size to be 8 bits
and thus can’t handle heterogeneous environment.

 Therefore arbitrary number of bits can be taken as flag.

 Here each frame begins and ends with a special bit

pattern 01111110 which is representing the flag.
Flag bytes with bit stuffing

 Bit stuffing is the process of adding one extra 0 if 011111 is

encountered in data, so that the receiver does not mistake
the pattern 0111110 for a flag.
 What is MAC Address or Physical Address

 The MAC address (an acronym for Media Access Control) is

an identifier for devices.

 It is a 48-bit identifier consisting of 6 hexadecimal blocks that

uniquely corresponds to a network card or device.

 It is also called as the physical address.

 It is unique for every device being used.

 The MAC address is only significant on the LAN to which a

device is connected, and it is not used or retained in the data
stream once packets leave that network.
 Error Control

 Data can be corrupted during transmission. For reliable

communication error must be detected and corrected.

 Error Detection and Correction are implemented either at the

data link layer or the transport layer of the OSI model
 Types of Error(s)

 Single-Bit Error : when only one bit in the data unit has
changed.

 Single bit errors are the least likely type of errors in serial
data transmission because the noise must have a very short
duration which is very rare.

 However this kind of errors can happen in parallel

transmission.
 Types of Error(s)

 Burst Error : when 2 or more bits in the data unit have changed.

 Burst errors does not necessarily mean that the errors occur in
consecutive bits, the length of the burst is measured from the first
corrupted bit to the last corrupted bit.

 Burst error is most likely to happen in serial transmission since the

duration of noise is longer than the duration of a bit.
 Error Detection

 Error detection techniques decides whether the received data is

correct or not without having a copy of the original message.

 Error detection uses the concept of redundancy, which means

adding extra bits for detecting errors at the destination.
 Error Detection

 Mainly four types of redundancy checks are used in data

communications
1) Vertical Redundancy Check(VRC)
2) Longitudinal Redundancy Check(LRC)
3) Cyclical Redundancy Check(CRC)
4) Checksum
 Vertical Redundancy check(VRC)

 VRC is often called as Parity Check. A parity bit is added to every

data unit so that the total number of 1s(including the parity bit)
becomes even for even-parity check or odd for odd-parity check.

 VRC can detect all single-bit errors. It can detect multiple-bit or

burst errors only the total number of errors is odd.
 Longitudinal Redundancy check(LRC)

 Blocks of bits are organized in table(rows and columns) and parity

bit is calculated for each column (as LRC) which is then appended
with data during transmission by the sender machine.

 On the receiver side bit by bit parity computation is done i.e the
parity of each column is calculated individually.
LRC Performance

 LCR increases the likelihood of detecting burst errors.

 It detects all burst errors up to length n (number of columns)

 If two bits in one data units are damaged and two bits in the
same positions in another data unit are also damaged, the LRC
checker will not detect an error.
 Cyclical Redundancy Check(CRC)

 CRC is based on binary division.

 The redundancy bits are the remainder derived by dividing the

data unit by a predetermined divisor. to uses modular-2 division.
Process followed in CRC Generator

1) A string with n number of zeroes are appended to the data unit.

The number n is one less than the number of bits in the
predetermined divisor which is n+1 bits.

2) Newly elongated data unit is divided by the divisor using a

process called binary division. The remainder resulting from this
division is the CRC.

3) The CRC of n bits derived in step 2 replaces the appended 0s at

the end of data unit as redundant data.

4) The data with CRC redundant bits are then transmitted on the
link to the receiver.
 CRC Generator

 Here data is 100100 with divisor as 1101.

 CRC Detector

 The receiver then divides the incoming data unit (with redundant
CRC bits) by the same divisor to find out, if there is no remainder,
specifies that there was no error and non-zero remainder specifies
data was changed during transmission.
 CRC Generator

 CRC generator(divisor) is most often represented not as a string of

1s and 0s, but as an algebraic polynomials.
CRC Performance

 CRC is very effective error detection method.

 CRC can detect all burst errors that affect an odd number of bits.

 CRC can detect all burst errors of length less than or equal to the
degree of the polynomial.

 CRC can detect with a very high probability burst errors of

length greater than the degree of the polynomial.
Checksum

 Checksum is used by the higher layer protocols is also based on

the concept of redundancy.

 The sender with the checksum generator does the following:

i. Firstly, it subdivides the data unit into equal segments K of n bits.

ii. These segments are then added together using one’s complement
arithmetic in such a way that the total is also n bits long.
iii. The total (sum) is then complemented and appended to the end of
the original data unit as redundancy bits called the checksum
field.
iv. This extended data unit is transmitted across the network
Checksum Checker

The receiver with the checksum checker does the following:

a) It subdivides the data unit into same length segments of n bits

b) These segments are added and then complement the result

c) If the result is all zeros the data is without any error and accepted
otherwise the data with errors is rejected by the receiver.

d) This extended data unit is transmitted across the network.

Checksum
Checksum Example

For example Original data : 10101001 00111001

10101001
00111001
--------------
11100010 Sum
00011101 Checksum
Data send : 10101001 00111001 00011101
Received data : 10101001 00111001 00011101
10101001
00111001
00011101
---------------
11111111 Sum
00000000 Complement
 Checksum Performance

 The checksum detects all errors involving an odd number of bits.

 It detects most errors involving an even number of bits.

 If one or more bits of a segment are damaged and the

corresponding bit or bits of opposite value in a second segment are
also damaged, the sums of those columns will not change and the
receiver will not detect a problem.
 Error Handling

Errors can be handled in two ways:

i. when an error is discovered, receiver can have the sender
retransmit the entire data unit.

ii. The receiver can use an error-correcting code, which automatically

corrects certain errors.

a) Error correcting codes are more sophisticated than error detection

codes and require more redundancy bits.

b) The secret of error correction is to locate the invalid bit or bits,

theoretical it is possible to correct any binary code errors, but the
number of bits required to correct a multiple bit or burst error is so
high that in most cases it is inefficient to do so.
Error Correction

d) For this reason, most error correction is limited to few number of

bits.

e) To correct an error, the receiver reverses the value of the altered

bit. To do so, it must know which bit is in error.

f) To correct single-bit error in an ASCII code (with 7 bits) needs to

determine which of the seven bits has changed i.e there are 8
different states required and for this it seems to have three-bit
redundancy code(000-111) to indicate location of error.

g) If error occurs in the redundancy bits themselves. i.e 7 bits data

plus 3 redundant bits equals to 10 bits.
Single Bit Error Correction

 Number of redundancy bits required

Let data bits = m= 7
Redundancy bits = r =4
Total message sent = m+r =11
The value of r must satisfy the following relation:
2r ≥ m+r+1
16>=12
Hamming Code

 A technique developed by R. W. Hamming known as Hamming

code provides a practical solution

 For example, for value of m as 7 bit (ASCII), the smallest r value as

4 (redundancy bits) is calculated using the relationship between
data and redundancy bits.
m + r + 1 ≤ 2r
7 + 4 +1 ≤ 16

 These bits are placed in positions that are powers of 2.

Hamming Code

 In hamming code each redundancy bit r is the VRC bit for the
combination of data bits as given below:-
r1 = bits 1, 3, 5, 7, 9, 11
r2 = bits 2, 3, 6, 7, 10, 11
r4 = bits 4, 5, 6, 7
r8 = bits 8, 9, 10, 11

 For redundancy bits calculation consider the binary representation

of each bit position.

a) The r1 bit is calculated using all bit position whose binary

representation includes 1 in the rightmost position.
b) The r2 bit is calculated using all bit position whose binary
representation includes 1 in the second position and so on
Hamming Code
Hamming Code
 Hamming Code

 For example, if the data bits are 1001101 and even parties for
various bit combinations are calculated and positioned to give 11 bit
code as shown below
 Hamming Code

 In case the number 7 bit has been changed from 1 to 0.

 The receiver takes the transmission and recalculates four new

VRCs using the same sets of bits by the sender
Hamming Code

 This step gives us the binary number 0111 (number 7 in decimal).

 The receiver can reverse its value and correct the error.
 Flow Control

 Flow control refers to a set of procedures used to restrict

the amount of data that the sender can send before
waiting for acknowledgment.

 The flow of data must not be allowed to overwhelm the

receiver.

 Any receiving device has a limited speed at which it can

process incoming data and a limited memory called a
buffer reserved for storing incoming data until they are
processed.
 Module 2
Data link Layer - Protocols
 Data Link Layer Protocols

 Now let us see how the data link layer can combine framing, flow
control, and error control to achieve the delivery of data from one
node to another.

 Following protocols have been developed for effective

communication at data link layer.
 Protocols – For Noiseless channel

 Communication channel is assumed to be an ideal noiseless

channel in which no frames are lost, duplicated, or corrupted.

 Two protocols have been developed for this type of channel.

i. Unrestricted simplex protocol

ii. Stop & wait protocol

 The protocols are normally implemented in software by using one

of the common programming languages.
Unrestricted Simplex Protocol

 Following assumption are considered for unrestricted

simplex protocol
a) Communication channel is a noiseless ideal channel
b) Data is transmitted in one direction only.
c) Processing time can be ignored.
d) Both the transmitting and receiving network layers are
always ready.
e) Infinite buffer space is available

 With these non realistic conditions the design of the

simplest protocol does not require any flow or error control
The design of the simplest protocol with no flow or error control
Sender-site algorithm for the simplest protocol

Receiver-site algorithm for the simplest protocol

Flow diagram for the unrestricted simplex protocol
Stop & Wait Protocol

 For stop & wait protocol following assumption were considered

a) Communication channel is a noiseless ideal channel
b) Data is transmitted in one direction only.

 And following assumption were dropped

a) Receiver processes the incoming data quickly and the
processing time can be ignored.
b) Infinite buffer space is available.

 Hence the design of the stop & wait protocol requires flow
control, but no error control is required.
 Stop & Wait Protocol

 In stop & wait method of flow control, the sender sends one frame
and waits for an acknowledgment before sending the next frame.

 The receiver after processing the frame and passing it to network

layer sends a little dummy frame back to the sender which, in effect
gives the sender permission to transmit the next frame
Design of Stop-and-Wait Protocol
Sender-site algorithm for Stop-and-Wait Protocol
Receiver-site algorithm for Stop-and-Wait Protocol
Sliding Window Protocol

 Although the implementation of flow control in Stop-and-Wait

Protocol to its predecessor is in a simple way however, its main
disadvantage is its inefficiency with each frame send and
received waste the entire time needed to traverse the link
specifically if the distance is very long.

 To overcome this disadvantage sliding window method of flow

control is used. In this method sender can transmit several frames
before needing an acknowledgement.

 Frames can be sent one after another depending upon carrying

capacity of the link.
Sliding Window Protocol

 The receiver acknowledges after some number of frames with a single

ACK to confirm the receipt of multiple data frame.

 The sliding window provides imaginary window at both sender and

receiver. A window with size n can hold n frames with identification
number given to each frame as 0 to n-1.

 The sliding window of the sender shrinks from the left when frames of
data are sent, and the sliding window of the sender expands to the right
when acknowledgments are received.
Sliding Window Protocol

 Similarly the receiver also maintain a receiving window

corresponding to the set of frames it is permitted to accept.

 The sliding window protocols are bidirectional protocols and to

save bandwidth data frame and an ACK frame can be combined
into just one frame.

 The receiver instead of sending a separate control frame as ACK

waits until the network layer passes it the next packet and attach
its acknowledgement in the ack field of the outgoing frame.

 This technique of temporarily delaying the outgoing

acknowledgment so that it can be hooked to the next outgoing
data frame is known as piggybacking.
Piggybacking

 Bidirectional transmission : piggybacking

 As Stop-and-Wait we can use piggybacking to improve the

efficiency of bidirectional transmission . Each direction needs
both a sender window and a receiver window.
 Protocols – For Noisy channel

 Error control in the data link layer is implemented based

on ARQ (Automatic Repeat reQuest), which means
retransmission of data in three cases : damaged frames,
lost frame and lost acknowledgements.

 The sliding window protocols ARQ are of three types

that differ in the terms of efficiency, complexity and
buffer requirement.

1) Stop-and-Wait ARQ
2) Go-Back-N ARQ
3) Selective repeat ARQ
Stop-and-Wait ARQ Overview

 Stop-and-Wait ARQ is also known as one - bit sliding

window protocol with a maximum window size of 1.
 In such protocol sender keeps a copy of the last frame
transmitted until it receives an acknowledgement for
that frame.
 Sender waits for “reasonable” amount of time for
ACK.
 The Sender is equipped with a countdown timer. It
starts this timer when a packet is sent.
 If no ACK is received within the timeout period, the
sender then retransmit the copy of frame.
Stop-and-Wait ARQ Overview

 Problem is if frame ACK is just delayed and not lost:

Then retransmission of same frame will create duplicate frame.

 Thus sequence number is required on every frame packet and

receiver can check this sequence number. If the frame is of same
sequence number, the receiver will not accept it.

 Since there is only one frame two numbers : 0,1 are sufficient as its
sequence number.

 Receiver’s Ack number is what he is expected next hence

 After receiving Frame 0, it sends back ACK 1
 And after receiving Frame 1, it sends back ACK 0
Design of the Stop-and-Wait ARQ Protocol
One -bit sliding window Protocol
Drawback of stop & wait ARQ protocol

 Utilization factor = L/R / (RTT+L/R)

where RTT is Round Trip Time
 Example

Assume that, in a Stop-and-Wait ARQ system, the

bandwidth of the line is 1 Mbps, and 1 bit takes 20 ms
to make a round trip. If the system data frames are
1000 bits in length, what is the utilization percentage of
the link?
Solution

L = 1000 bits, R = 1Mbps, RTT = 20ms

Utilization = 1/ 21 = 4.8%

For this reason, for a link with a high bandwidth or long delay,
the use of Stop-and-Wait ARQ wastes the capacity of the link.
 Pipelining Technique : Improves the efficiency
of the transmission
sender receiver

first packet bit transmitted, t = 0

last bit transmitted, t = L / R

first packet bit arrives

RTT last packet bit arrives, send ACK
nd
last bit of 2 packet arrives, send ACK
rd
last bit of 3 packet arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R

Increase utilization
by a factor of 3!

Utilization = 3*L/R / (RTT+L/R)

 Pipelined Protocols

 Pipelining improves the efficiency of the transmission.

 In these sliding window protocols N frames are sent and copy of these
frames(outstanding) is kept until the ACKs arrive.

 The receiver doesn't have to acknowledge each frame received . It can send
cumulative Ack for several frame.
 Pipelined Protocols

 Pipelining frames over an unreliable communication channel raises some

serious issues.

 In any frame in the middle of a long stream is damaged or lost.

 Large number of succeeding frames will arrive at the receiver then what
should the receiver do with these undamaged and correct frames

 Data link layer is required to hand over frames to network layer in

sequence or in proper order.

 Two basic approaches of sliding window protocols apply pipelining

available to deal with such errors are:
1) Go-Back-N ARQ
2) Selective Repeat ARQ
Go-Back-N ARQ Protocol

 In Go-Back-N ARQ sender starts the timer when the first

outstanding frame is sent.

 The receiver sends a positive ACK if a frame has been arrived

safe and in order.

 If a frame is damaged or out of order, the receiver is silent and

will discard all subsequent frames.

 When the timer of an unacknowledged frame at the sender site

is expired, the sender goes back and resend all frames,
beginning with the one with expired timer.(that is why this
protocol is called Go-Back-N ARQ)
 Example of Go-Back-N ARQ Protocol

 The sender has sent frame 0 to 6. Frame 0, 1and 2 were delivered undamaged
for which the receiver sends the acknowledgment.

 However frame 3 was lost hence no acknowledgment was sent for frame 3.
 Example of Go-Back-N ARQ Protocol

 Go-Back-N ARQ strategy correspond to a receive window of size [Link]

DLL refuses to accept any frame except the next one it is expecting,
frame 4 in this case.

 Sender timer finally expires, and the sender retransmitted all the frames
(3,4,5 and 6) because it does not know what is wrong.

 Frames 4,5 and 6 may have been arrived undamaged but they are
discarded because they are received out of order.
Go-Back-N ARQ Protocol : Problems

 For eventual in-order delivery to upper layer receiver discard

many good received (out-of-order) frames even if they have
arrived at the destination undamaged.

 Go-back-N ARQ approach thus wastes a lot of bandwidth as all

the packets will need to be retransmitted.

 This approach is very inefficient when if the error rate is very

high (as in high-speed network).

 Other strategy for handling errors when frames are pipelined is

called Selective Repeat ARQ.
Selective Repeat ARQ Protocol

1) Selective Repeat ARQ approach discards the bad frame but all
the good frames received after it are buffered. The receiver
individually acknowledges all correctly received frames.

2) When the sender timer goes out, only the oldest

unacknowledged frame is retransmitted.

3) If that packet arrives correctly the receiver can deliver in

sequence all the frames it has buffered.

4) Selective repeat ARQ strategy correspond to a receiver window

of size larger than 1 that requires a large memory space for
larger window.
Selective Repeat ARQ Protocol

1) Selective Repeat ARQ approach is combined with having a receiver

send a negative acknowledgement (NAK) when if detects an error.

2) NAK simulates retransmission of corresponding frame thus improving

its performance.
 Example of Selective Repeat ARQ Protocol

1) Frames 0, 1, 2, and 3 are sent. Frame 0 is received undamaged the receiver will
deliver this frame to network layer and ACK 1 is send back to the sender.

2) Next frame 1 is lost but frames 2 and 3 arrives undamaged, the receiver will not
discard the frames 2 and 3 rather store it in its buffer and meantime send NAK
for frame 1.

3) The sender after receiving NAK will retransmit only frame 1.

4) After a copy of frame 1 arrives undamaged the receiver can deliver frames 1 , 2
and 3 to the network layer and will then send ACK 4 for all frame received till
frame 3.
Selective Repeat ARQ Protocol