See also Flow Control. The purpose of ARQ requests is for:

• flow control
• error recovery (including error detection)

There are 2 types:

• Stop and Wait (for program 3 predesign)
• Sliding Window
  • Go-back-N ARQ
  • Selective Repeat ARQ (for program 3 actual design)

Stop and Wait

Assuming that we are transmitting data in one direction, we acknowledge (ACK) from the other direction. Provides for both flow control and error recovery.

The algorithm is:

1. The sender sends the data
2. The sender waits for an ACK from the reciever.

Summary of Stop and Wait

Often times you either don't need to send a lot, or you don't want to overwhelm your devices:

• Advantages:
  • Little overhead
  • Simple (not complex). You only have to buffer one piece of data at a time.
• Disadvantages:
  • It's slow (a lot of busy waiting)
  • The line is busy while a lot of data is sent from the sender (you'll also thrash your buses, if a bunch of devices use the same wire as a bus).
• Solution:
  • We were only having one buffer for received packets, ..., so more buffers?
  • We could wait to ACK until the whole packet is received?
  • The real solution: send more data

Sliding Window Flow Control

The goal here is to all for multiple frames to be on the wire at the same time. If all goes well the sender is simultaneously receiving ACKs while it is sending data and will never have to stop sending to wait on ACKs.

Sliding windows on its is only for flow control. We will cover error recovery techniques later.

The advantage is obvious that we can make the Throughput higher doing this.

In Stop and Wait we block on the ACK. In Sliding Window, we are not blocking on the ACK and only using it to see if we need to resend our data or not.

Other Comments - Sliding Windows

ACK5 is saying that data5 was gotten, but you have no information on the other data's. Often we want ACK to mean something specifically. Receiver Ready (RR) is the an accumulative ACK instead.

For example, saying RR7 means that I'm waiting on 7, but that 0-6 are all good. Another example, if you get data 0,1,2,5,6,7,8, you can't RR8! At best you can RR3.

The nice thing about it being cumulative is that you never have to resend any RR's. If you send data7 (after 0-6 are good) and it doesn't go through then you get RR6 (but you already sent that, so you don't need to resend it).

Packet Flow Diagram - Sliding Windows

Here we want to be realistic with our buffer size. We call this buffer size the window size, or the number of frames that can be send and not yet ACK'ed before the sender must stop sending. It's defined for at least the sender, but often you'll want it to be the same for the receiver.

The sender must be able to buffer an entire window's worth of data.

Data gets deleted from the buffer once an RR arrives that covers it.

Sliding Window Process

Sender's window has some window size (buffer size). We limit the number of un-ACK'ed frames.

There's gonna be 3 variables:

1. Lower Edge of Window
2. Upper Edge of Window
3. Current Frame

Error Handling in Sliding Windows

We'll need to both detect and correct errors. The types of errors we may see is:

• Bit errors (a 0 was supposed to be a 1 or vice versa, use a Internet Checksum or a CRC)
• Missing data (the size is lower, a bit was corrupted)
• Out of order (handle getting getting say RR4 before RR3)

In our sliding window example, we'll look at two error recovery techniques via:

• Go-back-N ARQ
• Selective-Repeat ARQ

As a sneak peak, we have Forward Error Correct (FEC) where:

• We need to detect there was an error
• This technique adds additional information to the data to fix the error on the receiving side
• Ex: Hamming Codes, Reed-Solomon Code, Parity
• May be used at the physical layer in both wireless and fiber connections.

Determining if there is an Error

How can the receiver detect if there was an error? It can:

• do bit error detection (CRC/Internet Checksum)
• out of order/missing data

Now how can the sender detect the error?

• Timer (timeout for each data)
• NACK (negative acknowledgement, to acknowledge errors)
• If the sending side sees duplicate ACKs (ie: RR3, RR3, RR3) for 3 or more, then try to resend it. Namely, the receiver will be sending these for each new packet successfully received.

Sliding Windows - How to recover from an Error

1. First, detect an error (previously discussed)
2. Recover from the error
   1. Go-back-N ARQ
   2. Selective Repeat ARQ