5 Selective Reject Design

Overview of Things for P3

We'll be using the ARQ Protocol#Sliding Window Flow Control via UDP.

Steps for the assignment (for future reference):

#todo/school : Implement the ARQ Protocol#Sliding Window Process in a library. Try to use structs so you can have a flag to dictate valid/invalid data. It must be an array though (see tip #21) and has a MAX_SIZE via tip #10 📅 2025-02-24
Handle PDU - Protocol Data Unit formats for both sending and recieving data, similar to how it was handled in program 2. Note you need a sequence number so design the PDU via tip #8, and use #9 to calc
- Make PDU formats for the specific packets too, such as RR/SREJ via tip #11
Handle logic of state diagram (where we need to wait for a certain amount to receive as much RRs/SREJs before poll()-ing for a non-zero amount of time (often just 1000ms)). A helpful summary is seen on tip #33, and the state diagrams in this document will try to use the 10-time rule described in tips #16 through #20.
- Start just with sending simple non-data packets (ex: RR/SREJ/Filename packets)
- Then upgrade to data packets (this is really where Sliding Window will be used)
Handle using Internet Checksum!
Handle multiprocessing (see tip #31, but essentially this is using fork() to setup your processes on the server. See also 12 - More on Flow Control#P3 Sliding Windows Protocol). It's worth it to do since it's 25% of the grade for some reason (and is pretty easy to implement once the rest of the program actually works), but save this for last.

By: Brian Mere (12pm lab section)

Part 1: Design Questions

1-1: Packet Flow (setup)

Below I'll make some packet flow diagrams detailing the following scenarios for connection establishment and then filename exchange.

a. No packets lost (so flow from sending filename/response packet and first few data packets)

b. Packet with the filename is lost going from rcopy to server

c. The file name response packet sent by server to rcopy is lost.

d. First two packets sent by the server are lost.

e. After filename exchange and you start to send data, what happens if the entire first window of data is lost?

f. After filename exchange and you start to send data what happens if an entire window of data is lost?

1-2: Packet Flow (use)

What follows is packet flow diagrams for the use phase of the connection.

a. Normal flow - nothing lost (no errors in data or flow control packets)

b. One data packet lost in a window size of 3 (include how its recovered)

c. Multiple packets lost in a window (look at both sequential packets being lost and non-sequential packets being lost)

Sequential:

and non-sequential:

d. RR lost for packet 2

e. Multiple RR's lost (ex: RR2 and RR3)

f. SREJ is lost

g. Entire window of data being lost

h. Entire window of RR's being lost:

## 1-3: Scenarios

Looking at the previous two sections, there are situations where one would have a closed window (other than a small window size), mainly because the sender times out on a SREJ or RR and thus must resend RDP2. This visually occurs in the packet diagrams when there's a big break in the server sending out the data packets (because it has a closed window), which shows up in situations:

Setup (never happens)
- Not in (a) (normal data operations, so the window will only partially be filled at times)
- Not in (b) (the window is only used for the data part)
- Not in (c) (same as the previous answer)
- Not in (d) (only one packet of the window gets buffered, since it's sent out of order, so no matter your window size it isn't filled)
- Not in (e) (since the first window is lost, so you just have to resend via the timer. There is no need to buffer as no data arrives out of order).
- Not in (f) (since now the situation is on the rcopy side)
Use
- Not in (a) (normal data operations)
- Yes in (b) (you start to buffer d2, and d3, since you didn't get d1, and will continue to start buffering many data packets since you are now out of order and the server hasn't realized)
- Yes in (c) (both sequential and non-sequential, as once the data packet is lost we start buffering the other packets. If the data packet is lost later in the order the window is more opened, and vice versa).
- No in (d) (the lost RR is ignored by future RR's)
- No in (e) (depends on the number I guess, but it's similar to the previous answer)
- Yes in (f) (the server will not know of the SREJ so then it will timeout as rcopy won't send a RR in anticipation, and thus the server will likely fill up the buffer with extra data packets like in the example)
- No in (g) (since the entire window is lost, we just have 4 Stop and Wait Design Process again, but now the packet is a set of WINDOW_SIZE packets)
- No in (h) (similar argument the previous)

1-4: Handling Out-of-Order Frame/Sequence Numbers

To handle the cases of when the server or rcopy get different sequence numbers, we've outlined how the design will handle this.

a. Data frame number is a duplicate of one you have already received.

Scenario: This is impossible. Assume for contradiction that it did happen, that server just sent say dn which rcopy got while it had sequence number n already. Then the last data sent was dn, since at the very least it got packets d(n-1) ... d(n-1-W) where W is the window size (ie: we could've buffered dn until we got an earlier packet we were waiting for), but then the sequence number was some number less than n itself. Thus either:

The sequence number is less than n
The server duplicated sending dn, which must've been caused by some RRn call by rcopy but that can't happen since the sequence number for rcopy is n!

Answer: since this can't happen, we don't have to worry!

b. Data frame number is greater than the one you expected but is still in your window size.

Scenario: This is the common buffering technique used in the Sliding Window process. Namely, rcopy may get data frames out of order, for example d0 d2 d3 (lost d1) so then we must buffer d2, d3 and thus we got a frame number greater than the current sequence number 1.

Answer: As the scenario implies:

buffer up to a window's size of data packets (ex: d2, d3 in our scenario)
SREJ the lowest sequence number that didn't make it (in our scenario, d1)
Wait for the data packet again, otherwise if the timer fails do SREJ on the same packet.
Once you get the data packet, pop all the sequence numbers in our buffer until we are missing one and repeat sending SREJ. (ex: you'd pop all sequence numbers in our scenario since they are in sequential order)
Once the buffer is clear, then you can send RRn for that highest sequence in our buffer (ex: RR3 in our scenario)

c. Data frame number is the one you are expecting but you have already received frames with higher numbers

Scenario: Very similar to the last process, this can occur in say getting rcopy with d0 d2 d3 like in the last example. You expected d0 but then you got frames with higher numbers too!

Answer: If they go in sequential order, accept them and send the right RR message of the highest number in the ascending sequence. If there's a gap, then you must buffer the remaining di's and SREJ with the sequence number of the missing data packet. Once you get it, then you can continue going up the sequence of data packets.

1-5: Example of Running the Sliding Window Process

We'll walk through some hand-written examples of doing the Sliding Window Process.:

For all of these assume WINDOW_SIZE = 3!

a. Send frame 0, 1, 2 and then receive RR1, RR3, send frame 3 and 4.

Frame Number	0	1	2	3	4	5	6
(initial)	L,C			U
Send frame 0	L	C		U
Send frame 1	L		C	U
Send frame 2	L			C,U
Recv `RR1`		L		C	U
Recv `RR3`				L,C			U
Send frame 3				L	C		U
Send frame 4				L		C	U
b. Send frame 0, 1, receive `RR1`, send frames 2, 3, receive `SREJ 2`, resend 2, receive `RR4`

Frame Number	0	1	2	3	4	7
(initial)	L,C			U
Send frame 0	L	C		U
Send frame 1	L		C	U
Receive `RR1`		L	C		U
Send frame 2		L		C	U
Send frame 3		L			C,U
Receive `SREJ2`		L	C		U
Resend frame 2		L		C	U
Receive `RR4`					L,C	U

Notice that at the last RR4 that current had to move at least with L (it can't be behind L).

1-6: More Examples of Sliding Window

Assume your program receives data frames 1,2,3,4,5 and then receives frame 7 and 8 and then frames 10, 11 and 12 (some recovered packet(s) is/are needed to make this work).

Draw a packet flow diagram of your solution using a window size of 3. Discuss how your implementation will handle this situation.

How are RR’s and SREJ’s sent? What packets are sent/resent?

Here:

We will SREJ6 and SREJ9 and if we get the data packet free the whole buffer (otherwise we may get timed out RDP2 packets and then we'd free the buffer).
We'll RR in order up until the missing packet, where the RR's will shoot up one entire window!

My implementation will handle this situation by sending RDP packets when getting SREJ from rcopy, which sends it once it notices packets out of order (which it also starts to buffer).

The packets that are not normally sent (duplicated) are d6 and d9, precisely only the missing packets (which is desirable).

1-7: Quick Sliding Window Examples

We'll be using the notation $(b, c, u)$ to indicate (bottom, current, upper) for the values of our sliding window.

a. With a window size of 5: sender sends d1-3, sender receives RR2, sends d4-6, receives RR6, sender sends packets d7 d8, receives SREJ7, sender sends d7, d9, d10

Step	Current State in $(b, c, u)$ notation
Sends `d1-3`	$(1, 4, 6)$
Receives `RR2`	$(2, 4, 7)$
Sends `d4-6`	$(2, 7, 7)$
Receives `RR6`	$(6, 7, 11)$
Sends `d7-8`	$(6, 9, 11)$
Receives `SREJ7`	$(6, 7, 11)$
Sends `d7, d9-10`	$(6, 11, 11)$
b. With a window size of 5: sender sends data packets 1-5, sender receives nothing and timeouts, sender resends packet 1, sender receives RR 6, sender sends 6, 7, 8, 9

Step	$(b, c, u)$
Sends `d1-5`	$(1, 6, 6)$
Times Out	$(1, 1, 6)$
Resends `d1`	$(1, 2, 6)$
Receives `RR6`	$(6, 6, 11)$
Sends `d6-9`	$(6, 10, 11)$
c. With a window size of 5: sender sends data packets 1-5, sender receives RR 3, sender receives SREJ 3, sender resends packet 3, sender receives RR 6, sender sends 6, 7, 8, sender receives SREJ 6

Step	$(b, c, u)$
Sends `d1-5`	$(1, 6, 6)$
Receives `RR3`	$(3, 6, 9)$
Receives `SREJ3`	$(3, 3, 9)$
Sends `d3`	$(3, 4, 9)$
Recieves `RR6`	$(6, 6, 11)$
Sends `d6-8`	$(6, 9, 11)$
Receives `SREJ6`	$(6, 6, 11)$

1-8: Tear-down Phase Design

We'll look at packet-flow diagrams describing how to handle the last packet of the file (the tear-down part):

a. Last data packet is lost

b. Whatever packet you are using to tell the data receiver that the file is done, that packet is lost.

c. RR for the last data packet is lost

(see (b))

d. The 2nd and 5th data packet from the end is lost (so the final data packet gets there but the one before that does not... and the one 4 before that does not). Use WINDOW_SIZE=7.