MODULE 2
The Data Link Layer
Introduction
Introduction
• OSI layer – 2nd layer
• Functionality – error free
transfer of data frames
• Purpose – transfer blocks
of data without error b/w
2 adjacent machines
• Adjacent machines
connected by
communication media –
coaxial cable, optical fibre
or satellites
Data Link Layer Design issues
• Functionality
• Providing service to n/w layer
• Dealing with transmission errors
• Flow control
– Slow receivers
– Fast senders
• Error Control
Function :Services provided to the network layer
Services
• Unacknowledged connectionless service
– No ACK
– No connection establishment
– Frame lost-not recovered
• Acknowledged connectionless service
– Relaible
– No connection establishment
– ACK
• Acknowledged connection-oriented service
– Connection established
– Each frame numbered
– order
Framing
Bits
Node A Adaptor Adaptor Node B
Frames
• Bit stream is not guaranteed to be error free
• DLL detect and correct errors
Framing
Methods
• Character count
• Flag bytes with byte stuffing
• Starting and ending flags with bit stuffing
Byte count/character count
Problem – synchronization at the destination
Byte count/character count
• Header – specify the number of bytes in frame
• DLL at destination – byte count – end of frame
Problem
• Byte count – transmission error
• Unable to locate the correct start of next frame
• Destination cannot send back frame to source as it
does not know the start of retransmission
Flag byte stuffing
Solves the problem of synchronization, resynchronization
ESC character/byte after each “accidental” flag byte
Bit-oriented Approach
• Views frame as collection of bits
• Bit-oriented protocol is used here
• SDLC(Synchronous data link control)
• HDLC(high-level data link control) protocol
– Special pattern :01111110 is used for distinguishing both the
beginning and the end of a frame.
8 16 16 8
Beginning Header Body CRC Ending
sequence sequence
– Problem: special pattern appears in the Body
– Solution: bit stuffing
• sender: insert 0 after five consecutive 1s
• receiver: delete 0 that follows five consecutive 1s
* CRC-Cyclic Redundancy Check
Bit stuffing
Error Detection
Error Detection
• Bits can get corrupted on transmissions
• How to detect, and if possible, correct them
• Error detection techniques:
– Parity bit
– Internet checksum
– Cyclic redundancy check (CRC)
Single-Bit error
Original Data 1 0 0 0 1 0 0 1
Data Received 1 0 0 0 01 0 0 1
Burst –Error
(More than one bit error)
Original Data 1 0 0 0 1 0 0 1
Data Received 1 10 0 0 1
0 01 0 1
Burst Error (length)=5 bits
Parity Bit
• Simplest of all techniques
• Single parity bit
• Two dimensional parity:
– Arrange the data in a 2D matrix
– Take the parity along each row and row column
– Send the data with the parity bits
One Dimensional Parity
• Even parity
Ex : 1) 1011010 (7-bit code)
10110100 (8-bit code)
• Odd parity
Ex : 1) 1011010 (7-bit code)
10110101 (8-bit code)
• Single bit error
Two Dimensional Parity
•Even parity bits
0101001 1
1101001 0
1011110 1
Data
0001110 1
42-bit msg
0110100 1
1011111 0
Parity
1111011 0
byte
Internet Checksum
Problem:
Suppose the following block of 16 bits is
to be sent using a checksum of 8 bits.
10101001 00111001 → message data
Example 7
Suppose the following block of 16 bits is to be sent using a
checksum of 8 bits.
10101001 00111001
The numbers are added using one’s complement
10101001
00111001
------------
Sum 11100010
Checksum 00011101 (1’s complement of the sum)
The pattern sent is 10101001 00111001 00011101
Example 8
Now suppose the receiver receives the pattern sent in Example 7
and there is no error.
10101001 00111001 00011101
When the receiver adds the three sections, it will get all 1s, which,
after complementing, is all 0s and shows that there is no error.
10101001
00111001
00011101
Sum 11111111
Complement 00000000 means that the pattern is OK.
Example 9
Now suppose there is a burst error of length 5 that affects 4 bits.
10101111 11111001 00011101
When the receiver adds the three sections, it gets
10101111
11111001
00011101
Partial Sum 1 11000101
Carry 1
Sum 11000110
Complement 00111001 the pattern is corrupted.
Cyclic Redundancy Check
• Let k be the degree of some divisor polynomial
– e.g., C(x) = x3 + x2 + 1
C(x) → Generator or divisor
k=3
• Represent n-bit message as n-1 degree polynomial
– e.g., MSG=10011010 as M(x) = x7 + x4 + x3 + x1
– xk-1 , xk-2 , xk-3 , xk-4 ,xk-5 ……xk-8
• Add k bits of redundant data to an n-bit message
– want k << n
– Corresponds to polynomial M(x) xk
CRC (cont)
• Divide C(x) to M(x) xk using modulo 2 division
– xy
– No carriers, no borrowers
• If error, to get the original data transmitted
– Subtract the remainder from M(x) xk using modulo 2
subtraction
10.10 A polynomial
10.11 A polynomial representing a divisor
Problem
Msg : 1 0 0 1 0 0
C(x) :x3 + x2 + 1
Dataword Remainder
Final Codeword 1 0 0 1 0 0 001
10.9 Binary division in CRC checker at receiver computer
ELEMENTARY DATA LINK PROTOCOLS
ELEMENTARY DATA LINK PROTOCOLS
• Unrestricted simplex protocol
• Simplex stop and wait protocol
• Simplex protocol for a noisy channel
1. UNRESTRICTED SIMPLEX PROTOCOL
• Data are transmitted in one direction
• Both transmitting and receiving network layers are always
ready
• Processing time required for the receiver is ignored
• Finite buffer space available
• Channel b/w the data link layers never damages or loses
frames
UNRESTRICTED SIMPLEX PROTOCOL (Contd.)
• Protocol consists of 2 distinct procedures
– Sender – DLL of source machine
– Receiver – DLL of destination machine
• No sequence number, No ACK, No MAX_SEQ
• Only one event possible – frame_arrival
UNRESTRICTED SIMPLEX PROTOCOL (Contd.)
Sender
– Infinite loop ,pump data out into the line as fast as possible
• 3 actions
– Go fetch a packet from NL
– Construct an frame
– Send frame on its way
• There is no error or flow control
UNRESTRICTED SIMPLEX PROTOCOL (Contd.)
Receiver
– Wait for something to happen
• When frame arrives
– Wait_for_event returns or sets frame_arrival
– Call to from_physical_layer removes newly arrived frame from
hardware buffer, receiver (DL) can get it
– Data portion passed on to NL
– DL waits for next frame
Problem
• Sender floods receiver with data at faster rate
2 SIMPLEX STOP-AND WAIT PROTOCOL
• Sender sends one frame waits for ACK before proceeding
• Bidirectional
SIMPLEX STOP-AND WAIT PROTOCOL (Contd.)
• Sending device keeps a copy of last frame transmitted until it
receives an ACK for that frame
– Keeping a copy allows sender to retransmit lost or
damaged frames until they are received correctly
• If no ACK for error - retransmit the frame
• For sender and receiver – a timer is set
Both data frames and ACK numbered alternately 0 and 1
Sequence
Number:1-bit Sender Receiver
sequence no.
3. SIMPLEX PROTOCOL FOR A NOISY CHANNEL
• Communication channel that makes error
• Frames may be either damaged or lost – so use checksum
Problem
• Distinguishing a frame that is seen for the first time from a
retransmission
Solution
• Put a sequence no. for each arriving frame at the header
• m, m+1, m+2…..
• PAR (positive acknowledgement with retransmission)
• ARQ (Automatic Repeat Request)
SIMPLEX PROTOCOL FOR A NOISY CHANNEL (Contd.)
• Sender remembers seq. no. of next frame to send --
next_frame_to_send
• Receiver remembers seq. no. of next frame expected –
frame_expected
• After transmitting a frame and starting the timer (see diagram in
next slide)
• Sender
– An ACK frame arrives undamaged – fetches next frame from DL
– Advances seq. no.
– ACK lost, Timer expires – seq. no. is not changed
SIMPLEX PROTOCOL FOR A NOISY CHANNEL
Receiver
• Seq. no. checked – if duplicate, if damaged - not accepted
• Otherwise a ACK is generated
• Duplicates and damaged frames are not passed to NL of
receiver
Sliding Window Protocols
SLIDING WINDOW PROTOCOLS
• Window is defined as “the
number of frames to be sent
without ACK.” Sender Receiver
• pipelining
• Piggybacking
• Better use of available BW.
…
• ACK
– Cumulative
– Negative
…
– Selective
SLIDING WINDOW ARQ
• GO-BACK-n ARQ
• SELECTIVE-REPEAT ARQ
Next frame to sent is seq no. 6 but frame 2 ACK is not received
SO it will go back to the frame no. 2 which is the starting
frame of current window
Frames from 2 to 5 from the current window are retransmitted
from the sender .Receiver will ignore frame 4 and 5 which is
retransmitted
END OF MODULE-2
