Transcript EE 3760 chapter 7

Data Link Control:
Controlling the reliable flow of information on a data link
Based on Chapter 7 of William Stallings, Data and
Computer Communication, 7th Ed.
Kevin Bolding
Electrical Engineering
Seattle Pacific University
Seattle Pacific University
Data Link Control
No. 1
Data Link Control
S
R
• Issues when sending data over a link:
• Flow control
• Avoid overflowing buffers or link capacity
• Error detection
• Detect any time any data is in error
• Inform a higher-level protocol of the error
• Reliable delivery
• Error control, re-try
• Lost packet detection, re-send
• Quality of Service
• Guaranteed minimum bit rate or maximum latency
Seattle Pacific University
Data Link Control
No. 2
Flow Control
• Ensure that receiver’s
buffers don’t overflow
S
R
• Basic issues
• How is acknowledgement
time
handled?
• How do we know if a frame
is lost?
• Flow diagrams
• Time from top to bottom
• Data from left to right
• Acks from right to left
Seattle Pacific University
Data Link Control
No. 3
Stop-and-Wait
• Always wait for an ack
before sending the next
frame
• Simple, easy
S
R
• Reasons for lack of Ack
• Receiver buffer overflow
• Data error detected
• Receiver glitch (no ack)
• Ack had problems on the
time
source until ack is received
• Retransmit after a timeout
timeout
• Errors/Lost Data
• Keep a copy of frame at
way back
Seattle Pacific University
Data Link Control
No. 4
Propagation speeds:
Vacuum: 3.0 x 108 m/s
Optical fiber: 2.0 x 108 m/s
Copper: 2.0 x 108 m/s
Stop-and-Wait Issues
•
Time to send a frame depends on
length of frame, distance of link, L,
and propagation speed in medium
• Time for frame = bit-time x bits +
L/(propagation speed)
• Ex: 10km F.O. link, 1Gbps:
10 km Fiber Link, 1Gbps
Transmission time = 50ms
S 1b
• 1 bit: 1ns + 50ms = 50.001ms
• 10kbit: 10ms + 50ms = 60ms
1ns
S
• 60kbit: 60ms + 50ms = 110ms
•
Must wait for ack between
frames
• Total time = frame time + link
time + ack time + link time
• Stop-and-wait requires:
• Short links
• Long frames
Seattle Pacific University
R
R
10kb
10ms
S
10kb
60kb total - 50kb in transit
60ms
Stop-and-Wait adds twice the link
time overhead to every frame
Data Link Control
No. 5
R
Sliding Windows
S
Sender
8 7 6 5 4 3 2 1
Receiver
8 7 6 5 4 3 2 1
• With Stop-and-Wait, we can
have only one outstanding
frame
• A Sliding Window allows
R
multiple outstanding (un-acked)
frames
• Multiple frames can be on the S
medium at the same time
• Example: Sliding window of
size 4
• Can send up to 4 frames
before having to wait
• Much better utilization of
medium
• Possible to combine acks
Seattle Pacific University
R
Sender 2 1 4 3 2 1 4 3 2 1
Receiver
2 1 4 3 2 1 4 3 2 1
Data Link Control
No. 6
Error Detection
• Detection of errors requires redundancy
• Parity bits
• 1 parity bit can detect a single bit error
• Multiple parity bits can provide error correction
• Hamming codes
• 3 parity bits can provide single bit error correction for
8 data bits
• Cyclic Redundancy Checks provide more efficient
error detection
• Use n redundant bits per frame
• Treat all bits in the frame as a binary number
• Result should be evenly divisible by some
predetermined number, P
Seattle Pacific University
Data Link Control
No. 7
Auto Repeat Requests (ARQ)
• Simple Stop-and-Wait
• If sender doesn’t get ack, resends frame
• If only ack was lost, results in duplicate frame received
• Assign frame numbers (modulo-2 counter will do)
• Go-Back-N ARQ
• Used with sliding-window protocols
• Ack may be an ACK or REJ for a specific frame
number
• When REJ received, resend the rejected frame and all
subsequent frames
• If sender times out (no ACK), it sends a special wakeup call (ACK with the p-bit set)
Seattle Pacific University
Data Link Control
No. 8
Real Data-Link Protocols
• HDLC - High-Level Data Link Control
• ISO standard, used in many links
• Basis for most other data-link protocols
• HDLC Frame Format
Flag
Addr
Control
Data
FCS
Flag
8
8
8-16
var
16-32
8
Flag - bit pattern (01111110) that marks beginning/end of frame
Note: Bit Stuffing
Addr - Destination address
11111  111110
Control - Type of message, sequence number, control info
Data - The data - variable in length
FCS - Frame Check Sequence - CRC
Seattle Pacific University
Data Link Control
No. 9