程序代做CS代考 Data Link Control Protocols – cscodehelp代写
Data Link Control Protocols
EE450: Introduction to Computer Networks Professor A. E450, USC, Zahid 1
Data Link Layer
Two physically connected devices: Host-Router, Router-Router, Router-
Host
Unit of data: frame
M
Ht M HnHt M
Ht
data link protocol
physical link
HlHnHt M frame
application
transport
M
network
link
network
link
physical
physical
EE450, USC, Zahid 2
Data Link Layer Services
Framing
Encapsulate packet into frame, adding header/trailer
Establish frame synchronization Error Detection & Control
Errors caused by signal attenuation, noise. Receiver detects presence of errors:
Receiver drops frame
Receiver requests retransmission (ARQ)
FlowControl
Ensuring the sender does not overwhelm the receiver
(i.e., preventing buffer overflow)
EE450, USC, Zahid 3
Frame Transmission Model
Source
Destination
Frame Transmission Time Frame Propagation Delay
ACK
ACK Transmission Time ACK Propagation Delay
ttran < tprop
ttran > tprop
EE450, USC, Zahid
4
Frame 1
Typical Frame Structure
We shall see that the above structure does not work in a Multipoint link (like in LANs)
EE450, USC, Zahid 5
Frame Synchronization
A special pattern, called a Flag (01111110) appears at the beginning and the end of the frame
Receiver hunts for flag sequence to synchronize Bit stuffing used to avoid confusion withdata
containing 01111110
0 inserted after every sequence of five 1s
If receiver detects five 1s it checks next bit
If 0, it is deleted
If 1 and seventh bit is 0, accept as flag
If sixth and seventh bits 1, sender is indicating abort
EE450, USC, Zahid 6
Bit Stuffing and un-Stuffing
EE450, USC, Zahid 7
Error Detection: Frame Check Sequence
Additional bits added by transmitter for error detection purposes at receiver
For every block of k bits, transmitter generates n bit sequence
Transmit k+n bits which is exactly divisible by some number
Receive divides frame by that number If no remainder, assume no error
If reminder, an error is detected
EE450, USC, Zahid 8
FCS Structure
EE450, USC, Zahid 9
Example of FCS (CRC)
EE450, USC, Zahid 10
FCS (error-free and w/errors)
EE450, USC, Zahid 11
FCS using Polynomials
EE450, USC, Zahid 12
Receiver Rules
If the reminder is not zero, then one or more bits are corrupted and the frame is rejected
If the remainder is 0, then No bits are corrupted or
Some bits are corrupted but the FCS decoder failed to detect them
EE450, USC, Zahid 13
Error Control Procedures
EE450, USC, Zahid 14
Flow Control Procedures
EE450, USC, Zahid 15
Stop and Wait ARQ
Source transmits a single frame at a time Wait for ACK
If
If
received frame damaged, discard it Transmitter has timeout timer
If no ACK within tout = timeout, retransmit frame
Transmitter buffers copy of frame until ACK is received
ACK damaged, transmitter will not recognize it
Transmitter will retransmit
Receiver gets two copies of frame and discards one. Use ACK0 (recv’d frame 1) and ACK1 (recv’d frame 0)
EE450, USC, Zahid 16
Stop & Wait ARQ
EE450, USC, Zahid 17
Link Utilization is Stop & Wait ARQ
Link Bandwidth: 1 Mbps
RTT: 20 msec
Frame Length: 1000 bits
BW x Delay Product = 20000 bits = 20 frames Sender can ONLY send 1 frame during RTT
Hence Link Utilization is 5% Really Bad!
EE450, USC, Zahid 18
Go-Back-N ARQ
Based on sliding window Protocol
If no error, ACK as usual with next frame
expected
Use window to control number of outstanding frames
If error, reply with rejection
Discard that frame and all future frames
until error frame received correctly
Transmitter must go back and retransmit that frame and all subsequent frames
EE450, USC, Zahid 19
Sending Window in Go-Back-N ARQ
EE450, USC, Zahid 20
Receiver Window in Go-Back-N ARQ
EE450, USC, Zahid 21
Window Size in Go-Back-N ARQ
EE450, USC, Zahid 22
Summary Notes for Go-Back-N ARQ
• In the Go-Back-N Protocol, the sequence numbers are modulo 2m, where m is the size of the sequence number field in bits.
• The send window can slide one or more slots when a valid acknowledgment arrives.
• In Go-Back-N ARQ, the size of the send window must be less than 2m; the size of the receiver window is always 1.
• The receive window of size 1. The window slides when a frame with no detected errors arrive; i.e. sliding occurs one slot at a time. Receiver will drop any out-of-order frames
EE450, USC, Zahid 23
Example: Un-reliable Channel
EE450, USC, Zahid 24
Selective Repeat (Reject) ARQ
Only rejected frames are retransmitted
Subsequent frames are accepted by the
receiver and buffered
Minimizes retransmission
Receiver must maintain large enough buffer
More complex transmitter
EE450, USC, Zahid 25
Sender Window fo SR ARQ
EE450, USC, Zahid 26
Receive Window for SR ARQ
EE450, USC, Zahid 27
SR ARQ Window Size
EE450, USC, Zahid 28
Summary Notes for SR ARQ
• In Selective Repeat ARQ, the size of the send window must be at most 2m-1; the size of the receiver window is usually (but not necessarily) the same as that of the sender window. Receiver will buffer any out-of-order frames
• Receiver can acknowledge frames that are out of sequence but it can’t pass them to the network layer. The sequence number of the ACK corresponds to the sequence number of the frame being acknowledged
EE450, USC, Zahid 29
Example of SR ARQ
EE450, USC, Zahid 30