The Data Link Layer
Chapter 3
Data Link Layer Design Issues
• Network layer services
• Framing
• Error control
• Flow control
Packets and Frames
Relationship between packets and frames.
Network Layer Services
(a) Virtual communication. (b) Actual communication.
Possible Services Offered
1. Unacknowledged connectionless service.
2. Acknowledged connectionless service.
3. Acknowledged connection-oriented service.
Framing Methods
1. Byte count.
2. Flag bytes with byte stuffing.
3. Flag bits with bit stuffing.
4. Physical layer coding violations.
Framing
A byte stream. (a) Without errors. (b) With one error.
Framing (Cont…)
a) A frame delimited by flag bytes.
b) Four examples of byte sequences before and after byte
stuffing.
Framing (Cont…)
Bit stuffing. (a) The original data. (b) The data as they appear on
the line. (c) The data as they are stored in the receiver’s memory after
destuffing.
Error-Correcting Codes
1. Repetition code
2. Hamming codes.
3. Binary convolutional codes.
4. Reed-Solomon codes.
5. Low-Density Parity Check codes.
Repetition code
Each binary digit repeat
three times and take best 2
out of 3
Repetition code (Cont…)
if more than 1 error occurs
for a 3-bit block, we get the wrong answer
Hamming Code
Given by R.W. Hamming
Easy to implement
7-bit hamming code is used commonly
Data bits
Parity bits: Extra bits with the data bits that is sent to detect the error
For 7 bit hamming code 4 data bits and 3 parity bits is used
2^n, where {n=0,1,…,r} is the position of the parity bits
Hamming Code
Hamming Code
Hamming Code
Hamming Code
Elementary Data Link Protocols
• Utopian Simplex Protocol
• Simplex Stop-and-Wait Protocol (Error-Free Channel)
• Simplex Stop-and-Wait Protocol (Noisy Channel)
Elementary Data Link Protocols (Cont…)
...
Some definitions needed in the protocols to follow. These
definitions are located in the file protocol.h.
Elementary Data Link Protocols (Cont…)
...
Some definitions needed in the protocols to follow. These
definitions are located in the file protocol.h.
Elementary Data Link Protocols (Cont…)
Some definitions needed in the protocols to follow. These
definitions are located in the file protocol.h.
Utopian Simplex Protocol
...
A utopian simplex protocol.
Utopian Simplex Protocol (Cont…)
A utopian simplex protocol.
Simplex Stop-and-Wait Protocol
...
A simplex stop-and-wait protocol.
Simplex Stop-and-Wait Protocol (Cont…)
A simplex stop-and-wait protocol.
Simplex Stop-and-Wait Protocol (Cont…)
Sliding Window Protocols
Sliding Window Protocols (Cont…)
...
A positive acknowledgement with retransmission protocol.
Sliding Window Protocols (Cont…)
...
A positive acknowledgement with retransmission protocol.
Sliding Window Protocols (Cont…)
A positive acknowledgement with retransmission protocol.
One-Bit Sliding Window Protocol
...
A 1-bit sliding window protocol.
One-Bit Sliding Window Protocol (Cont…)
...
A 1-bit sliding window protocol.
One-Bit Sliding Window Protocol (Cont…)
A 1-bit sliding window protocol.
One-Bit Sliding Window Protocol (Cont…)
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
Protocol Using Go-Back-N
Protocol Using Go-Back-N
Pipelining and error recovery. Effect of an error when
(a) receiver’s window size is 1
Protocol Using Go-Back-N (Cont…)
Pipelining and error recovery. Effect of an error when
(b) receiver’s window size is large.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
...
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
A sliding window protocol using go-back-n.
Protocol Using Go-Back-N (Cont…)
Simulation of multiple timers in software. (a) The queued
timeouts (b) The situation after the first timeout has expired.
Protocol Using Selective Repeat
Protocol Using Selective Repeat
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
...
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
A sliding window protocol using selective repeat.
Protocol Using Selective Repeat (Cont…)
a) Initial situation with a window of size7
b) After 7 frames sent and received but not acknowledged.
c) Initial situation with a window size of 4.
d) After 4 frames sent and received but not acknowledged.
End
Chapter 3