School of Computing. Dublin City University.
My big idea: Ancient Brain
Data frames and ack frames going in same direction.
Tell difference using "kind" field in header.
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?
Receiver has receiving window - the frames it is permitted to accept.
More complex Data Link layer, as more freedom about the order in which it sends and receives frames.
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
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:
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.
|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.
|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.
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.
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.
In general, with stop-and-wait, busy for this fraction of time:
(L/b) / ((L/b)+R)
= L / (L + bR)
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.
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).
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.
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
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.
Consider 3 bit frame number, where frames numbered 0..7 (8 distinct numbers)
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.
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.
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.