程序代做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