FL 4 Kommunikayionssystem
what is the purpose of automatic repeat request ARQ
• Purpose : to provide a service that delivers packets
– in order
– without errors
– without duplications
what are the basic elements of automatic repeat request ARQ
• Basic elements of ARQ:
– Error-detecting code with high error coverage, e.g., a Cyclic Redundancy Check (CRC) code
– Timeout mechanisms
– ACKs (positive acknowledgments)
– and sometimes NAKs (negative acknowledgments)
what is the first attempt in the transmitter for a ARQ protocal
Transmitter
1. Accept SDU from layer above
2. Create frame by adding header and error-detection bits
3. Transmit frame using the service of the layer below and start a timeout timer
4. If timer expires, retransmit frame (i.e., repeat step 3)
5. If ACK is received go to Step 1
first attempt for reciever for ARQ protocal
Receiver
1. Wait for new frame
2. Check received frame for errors
3. If no errors are detected:
– Deliver SDU to layer above
– Send ACK to transmitter
4. If errors are detected: discard frame
5. Go to Step 1
finite state machine(fsm) for First Attempt ARQ Protocol TRANSMITTER and RECIEVER
1.
SDU arrives from layer above
1. Create and store frame in memory. 2. Transmit frame 3. Start timer 4. Stop accepting new SDUs
2.
Timer expires 1. Retransmit frame. 2. Reset and start time
3.
Erroneous ACK arrives 1. Retransmit frame Error-free ACK arrives 2. Reset and start timer
4.
Error-free ACK arrives 1. Stop timer 2. Remove frame from memory 3. Start accepting new SDUs
and
reciever:
1. Error-free frame arrives. 1. Extract SDU and deliver to layer above 2. Send ACK
2. Erroneous frame arrives 1. Discard frame
what happends when you loose ACK
Lost ACKs lead to duplicate SDU delivery
how does short time look like
A too-short time-out leads to
– duplicate SDUs delivery
– possibly lost SDUs
what is the main idea between sequence numbers
Main idea
– Transmitter enumerates transmitted frames with sequence numbers
– Receiver includes the sequence number of received frames in the ACK frame
Both the transmitter and receiver maintains state variables to keep track of the transmitted and received frames
common example of state variables sequent number
– Transmitter state variable = sequence number of last frame that has been sent
– Receiver state variable = sequence number of the frame to be expected next
• In practice, sequence numbers must be reused to limit overhead, i.e., the sequence number should fit into a relative small number of bits
stop and wait state variables
The transmitter maintains a binary (1-bit) state variable
S last = sequence number of last transmitted frame
last transmitted information frame: Slast | SDU | CRC
stop and wait state variables
The receiver maintains a binary (1-bit) state variable
R next = sequence number of next expected frame=
1, last correct received frame had sequence number 0
= 0, last correct received frame had sequence number 1
ACK frame: Rnext | CRC = want frame Rnext = acknowledge frame with Slast = Rnext ⊕ 1
• The receiver accepts a frame with sequence number Slast only if Slast = Rnext
what is the ready state for stop and wait ARQ transmitter
Initialize sequence number Slast = 1 (first transmitted SDU has Slast = 0)
• Ready state
– Await SDU from upper layer
– Update sequence number Slast = Slast ⊕ 1
– Start timer, transmit frame with sequence number Slast
– Go to blocking state
what is the blocking state of stop and wait ARQ transmitter
Blocking state
– Do not accept new SDUs from upper layer
– If timer expires, reset timer and retransmit frame
– Upon reception of ACK frame
• if error detected or wrong sequence number (Rnext ≠ Slast ⊕ 1), ignore ACK
• if no errors detected and correct sequence number (Rnext = Slast ⊕ 1), go to ready state
stop and wait ARQ reciever
Initialize sequence number Rnext = 0
Ready state
• Await arrival of a frame
– if errors are detected, discard frame
– if no errors are detected, extract the sequence number Slast
• if sequence number is the expected one, i.e., Slast = Rnext
– deliver SDU to upper layer
– update sequence number Rnext = Rnext ⊕ 1
– send ACK with sequence number Rnext
• if sequence number is the not expected one, i.e., Slast ≠ Rnext
– discard frame
– retransmit ACK with sequence number Rnext
stop and wait fsm
SDU arrives from layer above
1. Set Slast = Slast ⊕ 1
2. Create and store frame with Slast
3. Start timer
4. Transmit frame
Timer expires
1. Retransmit frame
2. Reset and start timer
Arrival of error-free ACK
1. Stop timer
2. Remove frame from memory
Arrival of erroneous ACK or ACK with Rnext = Slast ⊕ 1 with Rnext ≠ Slast ⊕ 1
1. Retransmit frame
2. Reset and start timer
stop and wait fsm
Arrival of error-free frame with Slast = Rnext
1. Extract SDU and deliver to layer above
2. Set Rnext = Rnext ⊕ 1
3. Send ACK with Rnext
Arrival of erroneous frame or frame with Slast ≠ Rnext
1. Discard frame
2. Send ACK with Rnext
efficency of stop and wait
Consider an ARQ-protocol in Layer n
• Layer-n service provides error-free transmission of n-SDUs
• The effective data rate of the service, i.
R eff = number of bits in one SDU / avergare bme to transmit one SDU