1 bit sliding window protocol with Go back n and selective repeat

Posted By on September 22, 2014


Download PDF
Piggybacking
Framing and its methods

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.

 

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.

 
Piggybacking
Framing and its methods

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com