3.4 Sliding Window protocols

Remember conventions DA, NA, DB, NB

Full duplex.
Data frames and ack frames going in same direction.
Tell difference using "kind" field in header.

Piggybacking

Instead of sending ack frame on its own, if there is an outgoing data frame in the next short interval, attach the ack to it (using "ack" field in header).
Better use of bandwidth. Ack is only a few bits (here 1 bit). Costly to have to construct an entire frame for it.

If no data frame going out after timeout, just send ack frame on its own.
Q. Can't just wait for next data frame to send ack. Why not?

Sliding Window protocols

Frames have sequence number 0 to maximum 2ⁿ - 1 (n bit field).
At any moment, the sender maintains a list of sequence numbers it is permitted to send - these fall within the sending window. These are frames sent-but-no-ack and frames not-yet-sent.
When new packet from Network layer comes in to send, it is given highest no, and upper edge of window advanced by 1.
When ack comes in, lower edge of window advanced by 1.

Receiver has receiving window - the frames it is permitted to accept.

Sliding window size 1. Sequence nos. 0 to 7.
(a) At start. Receiver waits for 0.
(b) Sender sends 0.
(c) Receiver receives 0. Waits for 1.
(d) Sender got ack for 0. Hasn't got 1 from its Network layer yet.

More complex Data Link layer, as more freedom about the order in which it sends and receives frames.
Sender may have n unacknowledged frames at any time (window size n).
Needs n buffers to hold them all for possible re-transmit.
If window grows to its maximum size, DA must shut off NA.
This is all hidden from NB - still receives packets in exact same order.

Sender window might grow as it receives more frames to send and still has ones un-ack'ed.
Starts with nothing to send, then NA gives it frames to send.
Later, window may shrink as frames are ack-ed and NA has no more.
Receiver window constant size.
Receiver window size 1 means will only accept them in order.
Size n means will receive out of order (e.g. receive later ones after earlier frame is lost)
and then must buffer them before sending to NB (must send to NB in order).
e.g. DB has buffers to receive frames 0..7
Receives 1..7 in varying orders. Still waiting on 0. Can't send frames to NB yet.
0 got lost and was re-sent. Eventually gets 0.
Can now send all of 0..7 to NB
and re-use these slots.
e.g. consider frames numbered 0..7 but DB only has 2 buffers
Currently the sliding window is over 4,5
If get 4 can send it to NB and move window to 5,6
If get 5 have to wait for 4, then send both, and advance window to 6,7

3.4.1 - 1-bit Sliding Window

Window size 1. Stop-and-wait. Must get ack before can send next frame.

Both machines are sending and receiving. Combined in one loop here.
Let us assume one goes first.
If both start simultaneously, get problem - see later.

If one goes first, only one of them has the yellow block outside the main loop:

1-bit Sliding Window

Look at section to "handle inbound stream":
If got frame, inc(expected), then later ack(1-expected) (ack last frame).
Ack always = (1-expected).

Look at section to "handle outbound stream":
If got ack for what I'm trying to send, go on to next.
Else simply re-send it.

My acks responding to my inbound stream are being piggybacked onto my outbound stream.
Similarly, my inbound stream contains acks relating to my outbound stream.

Example

Figure (a) below:

A trying to send its frame 0 to B.
B trying to send its frame 0 to A.

Imagine A's timeout is too short. A repeatedly times out and sends multiple copies to B, all with seq=0, ack=1.
When first one of these gets to B, it is accepted. Set expected=1. B sends its frame, seq=0, ack=0.
All subsequent copies of A's frame rejected since seq=0 not equal to expected. All these also have ack=1.
B repeatedly sends its frame, seq=0, ack=0. But A not getting it because it is timing out too soon.
Eventually, A gets one of these frames. A has its ack now (and B's frame). A sends next frame and acks B's frame.

Conclusion: Could get wasted time, but provided a frame can eventually make it through, no infinite loop, and no duplicate packets to Network layer. Process will complete.

Notation (seq, ack, packet)
Asterisk - delivered to Network layer.

Problem

Figure (b) above:

Problem if both send initial packet at same time.

A sends 0,1
B sends 0,1
B gets 0,1 (got 0, but no ack of my 0)
B unnecessarily re-sends 0,0
A gets 0,1 (got 0, but no ack of my 0)
A unnecessarily re-sends 0,0
B gets 0,0 (already have 0, nothing to pass to NB, but this is good ack of my 0)
B sends 1,0
A gets 0,0 (already have 0, nothing to pass to NA, but this is good ack of my 0)
A sends 1,0
B gets 1,0 (got 1, but no ack of my 1)
B unnecessarily re-sends 1,1
A gets 1,0 (got 1, but no ack of my 1)
A unnecessarily re-sends 1,1
B gets 1,1 (already have 1, nothing to pass to NB, but this is good ack of my 1)
B sends 0,1
....

In (a), each frame brings a new packet for the Network layer and there are no duplicates.
In (b) half the frames contain duplicates (nothing to send to Network layer), even though there are no transmission errors.

Still, the protocol will complete eventually.

3.4.2 - Multiple un-ack-ed frames

Sometimes transmission time plus ack time is very long.
Can't have stop-and-wait.
Must have multiple un-ack-ed frames in progress at any time.

Example:
50 kbps satellite. 500 msec (0.5 sec) round trip delay.
Using above protocol to send 1000 bit frames. At t=0 send first frame.
Send 50,000 bits/sec. Takes 1/50 sec to send the full frame. At t=20 msec frame is sent.
Not until t=520 does ack come back.
i.e. Sender was blocked for 500/520 = 96.15 percent of the time.
96 percent of bandwidth not used.

Solution:
Sender can transmit up to w frames without ack.
Chosen to fill the time up until first ack comes back.
e.g. In example, choose w=26. By time it finishes sending 26 frames, at t= 20 . 26 = 520, the first ack comes back.
Can send one more. Then second ack will come back. And so on.
Need window size 26.

Pipelining - fill the channel with data to maximise line utilisation.
Cost: more buffers for un-ack-ed frames.

Notation

Need large window if:
1. either: Bandwidth b bits/sec is large (takes little time to send one frame, or small window of frames, waiting rest of time)
2. or: Round-trip delay R sec is large (need to fill time)
If b large, exhaust small window even if R moderate.
If R large, exhaust small window even if b moderate.
Could say need large window if the product b R is large
Say frame size = L bits.
Time to transmit 1 frame is L/b sec
In stop-and-wait, busy for L/b, idle for R
If L/b < R, then busy less than 1/2 the time.
i.e. If L < b R
Again, need pipelining when b R large.
In general, with stop-and-wait, busy for this fraction of time:
(L/b) / ((L/b)+R)
= L / (L + bR)

Handling errors: "Go back n" and "Selective repeat"

What if frame in middle of sequence is lost? Large numbers of succeeding frames arrive at receiver before sender knows there was error with lost frame.

DB must hand packets to NB in sequence. If any out of sequence, must buffer them (or discard them) while it waits for next in sequence for NB.

Go back n (GBN)

(a) below

Receiver B window size = 1
Discard all frames after error
No ack - they will eventually get re-sent
Can be lot of re-sends
Wastes lot of bandwidth if error rate high.

DA needs buffers in memory to hold frames waiting for ack (might need to re-transmit them).

See sample code p.1 and p.2.
In this code we have flow control - we enforce no more than MAX_SEQ un-ack-ed frames - DA disables and enables NA.

Acks may get lost/damaged. "ack n" is interpreted by A as "ack everything up to n".
Each frame has its own timer. Easy to simulate multiple timers in software.

Error recovery in pipelining.

Selective repeat (SR)

(b) above

Receiver B window size = n
Good frames after error are buffered (because can't send them to Network Layer NB yet, can't get rid of them)
Bad frame 2 times out and is re-sent.
At a timeout, sender A only sends the oldest un-ack-ed frame, not a sequence.

Or (in figure) B sends a Negative Ack (NAK) to provoke a re-send of frame 2 instead of waiting for timeout - may improve performance. If you know it will timeout, why wait?
Notice B doesn't ack 3-5 while it is buffering them.
It sends back "Ack 1" which means "Everything ok up to and including 1".
Once 2 gets through, B can send a whole bunch (2-5) to NB layer and can then jump to "Ack 5" ("Everything ok up to and including 5")

This scheme (what am I ack'ed up to, and just re-send oldest un-ack-ed at a time)
is a simpler scheme than having to keep a table of mixed acks and naks:
ack 23, nak 24, ack 25, ack 26, nak 27, ...
If NAK is lost, timeout will re-send anyway.

DB needs buffers in memory to hold frames that can't be delivered to NB yet.

See sample code p.1 and p.2.
Sender window starts at 0 and grows depending on what NA sends it.
Receiver window = constant max size (all frame numbers). In each slot is a bit saying if the slot is full (arrived) or empty.

Comparison

Use GBN or SR?
If errors low, might use GBN.
If errors high, might use SR.
If bandwidth cheap, might use GBN.
If bandwidth costly, might use SR.
If memory costly at B, might use GBN.
If memory cheap at B, might use SR.

Numbering frames

Set aside n bits for frame number.
There will be 2ⁿ distinct frame numbers, running 0 ... 2ⁿ - 1.
Then loop round - re-use 0 ... 2ⁿ - 1 again.

Lost frames

Must make sure that no more than 2ⁿ - 1 frames are un-ack-ed at any point,
not 2ⁿ frames (even though there are 2ⁿ distinct frame numbers).

Why?
Consider 3 bit frame number, where frames numbered 0..7 (8 distinct numbers)

8 un-ack-ed frames bad:
transmit 8 frames numbered 0..7
If received ok, will get ack=7
If error, will get ack=7 too! (Ack up to last ok frame)
Next transmission 8 frames 0..7
ack=7 comes back
is that ack-ing the new batch, or just re-ack-ing the old?
7 un-ack-ed frames ok:
If transmit 7 frames 0..6
If error, ack=7
If received, ack=6
Then transmit 7 frames 7,0..5
If error, ack=6
If received, ack=5
...

Lost acks

In fact, it's worse than that, if we consider SR with buffers for incoming out-of-sequence frames and the issue of lost acks.

Consider transmit of 0..6
B acks these, sends 0..6 to NB, clears buffers, and moves its window to 7,0,..5
But acks are lost!
A transmits original 0 again
B regards this as 0 of new batch. B hasn't seen 7 yet so acks up to 6.
A receives ack=6 so figures entire old batch got through.
A advances its window and transmits 7,0..5
7 accepted by B which then passes new 7 and old (duplicate) 0 to NB.
Error.

Solution

Solution: receiver's new window should not overlap at all with old window.
Maximum size: Half the range.

B advances to 4..7
If continues getting 0..3 it knows these are re-sends and ignores them (keeps ack-ing though, since acks are obviously not getting through).
Once it gets 4..7 it knows acks have got through and now 0..3 are safe numbers to re-use again.

What timeout?

Too short ("tight") - unnecessary re-transmits. B got it the first time. We didn't give it time to tell us.
Too long ("loose") - unnecessary delay after error.

Sometimes the link is predictable and time to transmit and ack is near-constant. Then timeout can be set to near-optimum value.

If link not predictable, it is more difficult to set it.
If acks piggybacked, then if lots of reverse traffic they will come quickly. In periods of low reverse traffic, each ack will time out first looking for reverse traffic before it is sent alone, so acks may come more slowly.