chapter-3-data-link-layer.ppt

computer network ppt

1. Data Link Layer

2. Data link Layer Design Issues
Services interface to the network layer.
Framing
Dealing with transmission errors.(Error Control)
Regulating the flow of data so that slow receivers
are not swamped by fast senders.(Flow Control)

3. Functions of the Data Link Layer
Relationship between packets and
frames.

4. Services to Network Layer
Transferring data between network
layers of machines

5. Types of Services
1. Unacknowledged Connectionless Service.
2. Acknowledged connectionless Service.
3. Acknowledged connection-oriented Service.

6. Services
Unacknowledged connectionless service
Real-time traffic, e.g., speech, video
Most LANs, such as Ethernet
Acknowledged connectionless service
Useful over unreliable channels
Each frame sent individually acknowledged
e.g., wireless systems, e.g. 802.11 (WiFi)

7. Services
Acknowledged connection-oriented
service
Guarantees
Each frame sent is received without error
All frames sent are received in right order
Three phases:
Connection establishment
Variables and counters initialization
Frame transmission
Connection release
Variables, buffers, resources freed up

8. Framing
Fact
Raw bit stream delivered by physical layer is
not error free
Data link layer detects/corrects errors
Framing
Computing checksum
Handling error if any

9. Framing
Approaches
1)Character Count.
2)Flag bytes with byte stuffing.
3)Starting and ending flags, with bit stuffing.

10. Character Count
A field in header specifies number of characters in a
frame.
Problem?

11. Example
The following character encoding is used in a data link protocol:
A: 01000111;
B: 11100011;
FLAG: 01111110;
ESC: 11100000
Show the bit sequence transmitted (in binary) for the four-character
frame: A B ESC FLAG
When Character countframing method is used:
Answer
00000101 01000111 11100011 11100000 01111110

12. Flag Bytes with Byte Stuffing
A frame delimited by flag bytes
Four examples of byte sequences before and after stuffing

13. Byte Stuffing / Character Stuffing
A serious problem may easily happen that the flag byte's
bit pattern occurs in the data.
One way to solve this problem is to have the sender's data
link layer insert a special escape byte (ESC) just before
each ''accidental'' flag byte in the data.
The data link layer on the receiving end removes the
escape byte before the data are given to the network
layer.
This technique is called byte stuffing or character stuffing.
Thus, a framing flag byte can be distinguished from one in
the data by the absence or presence of an escape byte
before it.

14. Example
The following character encoding is used in a data link protocol:
A: 01000111;
B: 11100011;
FLAG: 01111110;
ESC: 11100000
Show the bit sequence transmitted (in binary) for the four-character
frame: A B ESC FLAG
When Flag bytes with byte stuffing framing method is used:
Answer
01111110 01000111 11100011 11100000 11100000
11100000 01111110 01111110

15. Flag Bits with Bit Stuffing
Each frame begins and ends with special bit pattern (flag
byte): 01111110
Problem: 6 consecutive 1s in data
Solution: Bit Stuffing: inserting a 0 after 5 consecutive 1s
Original Data
After
Stuffing
After received
and destuffed

16. Example
The following character encoding is used in a data link protocol:
A: 01000111;
B: 11100011;
FLAG: 01111110;
ESC: 11100000
Show the bit sequence transmitted (in binary) for the four-
character frame: A B ESC FLAG
When Starting and ending flag bytes, with bit stuffingframing
method is used:
Answer
011111100100011111010001 11110000 0 011111010
0111110

17. Exercises
The following character encoding is used in a data link protocol:
A: 11010101; B: 10101001; FLAG: 01111110; ESC: 10100011
Show the bit sequence transmitted (in binary) for the five-character
frame: A ESC B ESC FLAG
when each of the following framing methods are used:
(a) Flag bytes with byte stuffing.
(b) Starting and ending flag bytes, with bit stuffing.
ANSWER:
a) 01111110110101011010001110100011 10101001
1010001110100011101000110111111001111110
b) 01111110 11010101 10100011 10101001 10100011
011111010 0111110

18. Exercises
1.Given the output after byte-stuffing:
FLAG A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D F FLAG.
What is the original data?
ANSWER:
A B ESC C ESC FLAG FLAG D F
2.Given the output after byte-stuffing:
FLAG A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D FLAG.
What is the original data?
ANSWER:
A B ESC C ESC FLAG FLAG D
3.A bit string, 0111101111101111110, needs to be transmitted at
the data link layer. What is the string actually transmitted after
bit stuffing?
ANSWER:
The output is 011110111110011111010

19. Error Control
Using acknowledgement
Positive-If the sender receives a positive acknowledgement
about a frame, it knows the frame has arrived safely.
Negative-On the other hand, a negative acknowledgement
means that something has gone wrong, and the frame must be
transmitted again.
Problem: In some cases, sender waits for
acknowledgement forever if a frame is lost for ever.
Solution: Timer
Problem: Duplicate transmission (receiver will accept the
same frame two or more times)
Solution: Sequence number

20. Positive Acknowledgement
Sender sends a message, waits for
acknowledgement from receiver, and
then sends next message

21. Reliability and Acknowledgement
Case 1: no error
SenderReceiver
Time Data
Ack.
Case 2: data lost
Sender Receiver
Time Data
Data
Ack.
X
Timeout
Timeout and retransmission

22. Reliability and Acknowledgement
Case 4: ack. lost
Sender Receiver
Time Data
Data
Ack.
X
Timeout
New problem? Duplicate
Solution: Sequence number
Case 3: data error
Sender Receiver
Time Data
Data
Ack.
Error
Timeout
Timeout and retransmission

23. Flow Control
Needed
Problem
When frames are transmitted faster than
receiver can accept, frames will be lost
Solution
Flow control by feedback mechanism
The protocol contains well-defined rules
about when a sender may transmit the
next frame

24. Introduction
Transmission impairments (errors)
Attenuation
Loss of energy as signal propagates
Delay Distortion
Components travel at different speeds
Noise
Unwanted energy from other sources

25. Attenuation, distortion, and noise
Delay
Distortion
Attenuation
Noise
©The McGraw-Hill Companies, Inc., 2004

26. Types of Errors

27. Single-bit error

29. Burst error

30. Error Correcting/Detecting Codes
Error correction
Referred to as forward error correction
Detect and correct error
Error detection
Detect error and request retransmission
Redundancy added to message
Codeword (nbits)
message + redundancy
(mbits) (rbits)
n= m+ r
Code rate = m /n

31. Error Correcting/Detecting Codes
Where are error correction/detection
used?
Correcting: physical layer and higher layers
Detecting: data link, network, and
transport
Error correcting or error detecting?
Circumstances, application, etc.

32. Error-Correcting Codes
Hamming codes (our focus)
Binary convolution codes
GSM mobile phone system, satellite
communication, 802.11
Reed-Solomon codes
DSL, data over cable, satellite communications
CDs, DVDs, Blue-ray disks
Low-density parity check codes
Digital video broadcasting, 10 Gbps Ethernet,
power-line networks, 802.11

33. Hamming Distance
The number of bit positions in which
two codewords differ is called the
Hamming distance .
Its significance is that if two codewords
are a Hamming distance ‘d’ apart, it will
require ‘d’ single-bit errors to convert
one into the other

34. Error Correction
Hamming Code
Linear systematic block code
For m-bit message we need r-bit redundancy, where
(m +r + 1) 2
r
Why?
Redundancy bits are placed in position of 2’s power
Example: If m = 7, then r= 4

35. Hamming Code Example
7-bit data word "0110101“(d -data bits, p -parity bits)

36. Combination
p1 : bits 1, 3, 5, 7, 9, 11..
p2 : bits 2,3,6,7,10,11..
p4 : bits 4,5,6,7..
p8 : bits 8,9,10,11..

37. Hamming Code Example (Cont.)
•Assume the final bit gets corrupted and turned from 1 to 0
•Flag each parity bit as 1 when the even parity check fails

38. Hamming Code Example
How to construct codeword
message: m = 7 bits
1. find r using the formula r = 4
2. place data bits in codeword
3. calculate P bits: even parity
P1+1+0+0+0+1 P1 = 0
Sum should be even
P2+1+0+0+0+1 P2 = 0
P4+0+0+0 P4 = 0
P8+0+0+1 P8 = 1

39. Hamming Code Example (Cont’d)
How to correct error and retrieve message
1. compute syndrome similar to codeword
construction error position
2. flip the bit in the error position
3. remove P bits from codeword
Example of an (11, 7) Hamming code correcting a single-bit error

40. Use of a Hamming code to correct burst errors.

41. Error-Detecting Codes
Parity
Checksums
Internet
Cyclic Redundancy Checks (CRCs)
They are all linear systematic block
code

42. Error-Detecting Codes
Parity bit
Added to data so that number of 1 bits in
codeword is
Even (even parity)
Odd (odd parity)
E.g., ASCII of ‘H’ is 1011010, its codeword
is
________ if even parity is used
________ if odd parity is used
10110100
10110101

43. Use Parity to Detect Burst Errors
Organize a block into (kx n) matrix
One parity for each column
one row of parities at the bottom
Transmit one row at a time
Can detect burst errors of length n

44. Interleaving of parity bits to detect a
burst error
Example

45. Error-Detecting Code -CRC
Bit stream is treated as polynomial w/
coefficients 0 and 1
Example:
data: 10100111
polynomial:
degree = 7
Modulo 2 arithmetic is used
Example: 1001101111110000
[phone] -10100110
01010001 01010110
XOR1
257
 xxxx

46. CRC generator and checker

48. Error-Detecting Code -CRC
Use generator polynomial G(x) to calculate
checksumR(x)
Frame: P(x) generator: G(x)
degree of G(x) = d
Transmitted: checksummedframeP(x)·x
d
+ R(x)
It’s guaranteed that P(x)·x
d
+ R(x) is
divisible by G(x)!!G(x)
R(x)
Q(x)
G(x)
xP(x)
d



49. Error-Detecting Code -CRC
Receiver
Divides checksummed frame by G(x)
If remainder is zero
No error, CRC is removed
Otherwise
Error, the frame is discarded

50. Generator:1
4
xx
CRC -
Example
0 0

51. Generator:1
4
xx
CRC -
Example
0 0
1
Received 0 0 1 0
0
0
0
0
0
0
0
0
0 0
1 0
0
1 0 ≠ 0 
Frame discarded
Error during transmission

52. CRC –Example 1
1001
1101
1000
1101
1011
1101
1100
1101
1000
1101
1101
k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial
101
1101Remainder
m mod c
10011010000 Message plus k
zeros
Result:
Transmit message
followed by
remainder:
10011010101
G(x) = x
3
x
2
1 = 1101 Generator
P(x) = x
7
x
4
x
3
x = 10011010 Message

53. Example 1 CRC Checking (No Errors)
1001
1101
1000
1101
1011
1101
1100
1101
1101
1101
1101
k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial
0
1101Remainder
m mod c
10011010101 Received
message, no
errors
Result:
CRC test is passed
G(x) = x
3
x
2
1 = 1101 Generator
P(x) = x
10
x
7
x
6
x
4
x
2
1 = 10011010101 Received Message

54. Example 1:CRC Checking (With Errors)
1000
1101
1011
1101
1101
1101
1101
k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial
0101
1101
Remainder
m mod c
10010110101 Received
message
Result:
CRC test failed
Two bit errors
G(x) = x
3
x
2
1 = 1101Generator
P(x) = x
10
x
7
x
5
x
4
x
2
1 = 10010110101Received Message

55. Example 2 Calculating CRC

56. Example 2 :Checking CRC

57. Exercise
For G=110011 and P=11100011, find the CRC
or
For P(x)=x
7
+x
6
+x
5
+x+1, G(x)=x
5
+x
4
+x+1 calculate CRC.

58. CRC Properties
Single error detection
Double error detection w/ carefully
chosen G(x)
Odd number error detection if (x + 1) is
a factor of G(x)
Detect burst error length rfor rcheck
bits
Can be implemented in hardware using
simple shift register circuit

59. •CRC-8 (for ATM header):
x
8
+ x
2
+ x + 1
•CRC-32 (for LANs):
x
32
+ x
26
+ x
23
+ x
22
+ x
16
+ x
12
+ x
11
+
x
10
+ x
8
+ x
7
+ x
5
+ x
4
+ x
2
+ x + 1
•CRC-16-(for Bluetooth, etc.):
x
16
+ x
12
+ x
5
+ 1
Standard CRC Examples

60. Elementary Data Link Protocols
Key Assumptions
Network, data link, and physical layers are
independent processes communicating by
sending messages
Machine A wants to send a long stream of
data to machine B over a reliable,
connection-oriented service

61. Implementation of Physical, Data
Link, and Network Layers

62. Data Structures and Primitives

63. Data Structures and Primitives

64. Data Structures and Primitives

65. Unrestricted Simplex Protocol
Utopia protocol
Assumptions
Unidirectional data transmission
Transmitting/receiving network layers are
always ready
Processing time is ignored
Infinite buffer space
No errors

66. Unrestricted Simplex Protocol -Sender

67. Unrestricted Simplex Protocol -Receiver

68. Simplex Stop-and-Wait Protocol
Assumptions
Unidirectional data transmission
Transmitting/receiving network layers are
always ready
Finite processing speed
Finite buffer capacity
No errors
Problem: Sender sends too fast
Stop-and-wait
Senders sends one frame and then waits
for an acknowledgement before processing

69. Simplex Stop-and-Wait Protocol -Sender

70. Simplex Stop-and-Wait Protocol -Receiver

71. Protocol for noisy channel
Simplex PAR Protocol
For noisy channel
Positive acknowledgement with
retransmission (PAR)
Sender waits for a positive
acknowledgement before advancing to
the next data item
Also Known as ARQ (Automatic Repeat
reQuest)

72. PAR Protocol
Assumptions
Unidirectional data transmission
Transmitting/receiving network layers are
always ready
Finite processing speed
Finite buffer capacity
Errors, can be detected
Timer + sequence number
Size (i.e., # bits) of sequence number?

73. PAR Protocol –Sender

74. PAR Protocol –Sender (Cont’d)

75. PAR Protocol –Receiver

76. Sliding window protocols
Data Frame transmission
Unidirectional assumption in previous
elementary protocols
Not general
Full-duplex -approach 1
Two separate communication channels
Forward channel for data
Reverse channel for acknowledgement
Problems: 1. reverse channel bandwidth wasted
2. cost

77. Sliding Window Protocols
Full-duplex -approach 2
Same circuit for both directions
Data and acknowledgement are intermixed
How do we tell acknowledgement from data?
"kind" field telling data or acknowledgement
Approach 3
Attaching acknowledgement to outgoing data
frames
Piggybacking

78. Piggybacking
Temporarily delaying transmission of
outgoing acknowledgement so that they
can be hooked onto the next outgoing
data frame
Advantage: higher channel bandwidth
utilization
Complication:
How long to wait for a packet to piggyback?
If longer than sender timeout period then
sender retransmit
Purpose of acknowledgement is lost

79. Piggybacking
Solution for timing complexion
If a new packet arrives quickly
Piggybacking
If no new packet arrives after a receiver ack
timeout
Sending a separate acknowledgement
frame

80. Sliding Window Protocol
We are going to study three
bidirectional sliding window protocols
(max sending window size, receiving
window size)
One-bit sliding window protocol (1, 1)
Go back N (>1, 1)
Selective repeat (>1, >1)
Differ in efficiency, complexity, and
buffer requirements

81. Sliding Window Protocol
Each outbound frame contains an n-bit
sequence number
Range: 0 -MAX_SEQ (MAX_SEQ = 2
n
-1)
At any instance of time
Sender maintains a set of sequence
numbers of frames permitted to send
These frames fall within sending window
Receiver maintains a set of sequence
numbers of frames permitted to accept
These frames fall within receiving window

82. Sliding Window Protocol
Lower limit, upper limit, and size of two
windows need not be the same
Fixed or variable size
Requirements
Packets delivered to the receiver's network
layer must be in the same order that they
were passed to the data link layer on the
sending machine
Frames must be delivered by the physical
communication channel in the order in
which they were sent

83. Sending Window
Contains frames can be sent or have
been sent but not yet acknowledged –
outstanding frames
When a packet arrives from network
layer
Next highest sequence number assigned
Upper edge of window advanced by 1
When an acknowledgement arrives
Lower edge of window advanced by 1

84. Sending Window
If the maximum window size is n, n
buffers is needed to hold
unacknowledged frames
Window full (maximum window size
reached)
shut off network layer

85. Receiving Window
Contains frames may be accepted
Frame outside the window discarded
When a frame's sequence number
equals to lower edge
Passed to the network layer
Acknowledgement generated
Window rotated by 1

86. Receiving Window
Contains frames may be accepted
Always remains at initial size (different
from sending window)
Size
=1 means frames only accepted in order
>1 not so
Again, the order of packets fed to the
receiver’s network layer must be the
same as the order packets sent by the
sender’s network layer

87. Actually, 1-bit
sequence
number is
enough for
this example.
The purpose
of using 3-bit
is to
demonstrate
the idea of
sliding
window.
In many textbooks, an
array of boxes are used to
represent the window.
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.

89. One Bit Sliding Window Protocol
Sending window size = receiving
window size = 1
Stop-and-wait
Acknowledgement =
Sequence number of last frame
received w/o error*
Problem of sender and receiver send
simultaneously
*: some protocols define the acknowledgement to be the
sequence number expected to receive

90. (a)Case 1: Normal case. (b)Case 2: Abnormal case.
The notation is (seq, ack, packet number). An asterisk indicates
where a network layer accepts a packet.
Case 2: simultaneous startCase 1: normal case

91. Example:
50 Kbps bandwidth (satellite channel), 1000 bit frames, 500 msec round-
trip propagation delay
Sender
Receiver
first packet bit transmitted, t = 0
500
first packet bit arrives: 500/2=250
ACK arrives: 500+20=520
last packet bit transmitted, t = 20
500/2=250
500/2=250
1000 bits/50,000 bps=20 msec
Line utilization = 20/520=3.85% !! sender is blocked 96.15% of time !
Problem with stop and wait protocols

92. Pipelining
Solution for poor channel utilization:
Use larger frames, but the maximum size is limited by
the bit error rate of the channel. The larger the
frame, the higher the probability that it will become
damaged during transmission.
Allowing the sender to send more than 1 frame, w
frames send before blocking(Pipelining)
In Pipelining:
Sender does not wait for each frame to be ACK'ed. Rather it
sends many frames with the assumption that they will arrive.
Must still get back ACKs for each frame.
Provides more efficient use of transmit bandwidth, but error
handling is more complex.
Value of w? times equal to round-trip time,
For previous example, W=26 (Because 520/20=26)

93. Pipelining
In Pipelining:
Sender after sending the wthframe, will
get the ACK of first frame.
If error occurred:
What if 26 frames transmitted, and the second
has an error. Frames 3-26 will be ignored at
receiver side? Sender will have to retransmit.
What are the possibilities?
Two strategies as solutions (depends on
receive Window size)
Go-Back-N
Selective-Repeat

94. Go-Back-N
Go-Back-N:
Equivalent to receiver's window size = 1.
If receiver sees bad frames or missing
sequence numbers, subsequent frames are
discarded. No ACKs for discarded frames.

95. Go Back nProtocol
Receiver discards all subsequent frames
following an error one, and send no
acknowledgement for those discarded
Receiving window size = 1 (i.e., frames
must be accepted in the order they were
sent)
Sending window might get full
If so, re-transmitting unacknowledged frames
Wasting a lot of bandwidth if error rate is
high

96. Go Back nProtocol Implementation
Sender has to buffer unacknowledged
frames
Acknowledge nmeans frames n,n-1,n-2,
... are acknowledged (i.e., received
correctly) and those buffers can be
released
One timer for each outstandingframe in
sending window

97. Pipelining and error recovery. Effect of an error when (a) receiver's
window size is 1 and (b) receiver's window size is large

98. Selective-Repeat
Selective-Repeat:
Receiver's window size larger than one.
Store all received frames after the bad
one. ACK only last one received in
sequence.
Use NAK(Negative ACK) when an error detected:
checksum error or out of sequence

99. Select Repeat Protocol
Receiver stores correct frames following the
bad one
Sender retransmits the bad one after noticing
Receiver passes data to network layer and
acknowledge with the highest number
Receiving window > 1 i.e., any frame within
the window may be accepted and buffered
until all the preceding one passed to the
network layer
Might need large memory

100. Negative Acknowledgement (NAK)
SRP is often combined with NAK
When error is suspectedby receiver,
receiver request retransmission of a frame
Arrival of a damaged frame
Arrival of a frame other than the expected
Does receiver keep track of NAK?
What if NAK gets lost?

101. Selective Repeat with NAK

102. Select Repeat Protocol Implementation
Receiver has a buffer for each sequence
number within receiving window
Each buffer is associated with an
"arrived" bit
Check whether sequence number of an
arriving frame within window or not
If so, accept and store
Maximum window size = ? Can it be
MAX_SEQ ?

103. Select Repeat Protocol -Window Size
Problem is caused by new and old
windows overlapped
Solution
Window size=(MAX_SEQ+1)/2
E.g., if 4-bit window is used, MAX_SEQ = 15
window size = (15+1)/2 = 8
Number of buffers needed
= window size

104. Select Repeat Protocol
(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.