Transport Layer: Sliding Window Protocols
Welcome back to the course on Computer Network and Internet Protocols.So, in the last class we have discussed about this flow control and reliable data delivery protocols over the transport layer and we have looked into the details of the stop and waitflow control and reliable protocol; which we call as the stop and wait ARQ.And there we have see that this stop and wait protocol in case of stop and wait protocol,one major disadvantage is that, you can have only 1 packet outstanding in the networkand that is why you are not able to utilize the full capacity of the link. So, for every outgoing packet you have wait for the acknowledgement, unless you are receiving theacknowledgement, you will not be able to send the next packet.In case of the sliding window protocol we want to ensure a pipeline version of theprotocol where you can send multiple packets all together in a pipeline fashion. So, wewill look into the details of the sliding window protocol about how we can achieve thispipelining and at the same time you can receive the acknowledgement parallelly andaccordingly control your transmission rate.So, the broad idea is something like this if you look into this diagram you can see thatinitially I started sending 1 packets, here I am I have started sending 1 packets and once Ireceive the acknowledgement for that 1 packet, I increase my window size to send morepackets in parallel. So, here we are sending 3 packets in parallel, then again we haveincreased it to 4 packets and that way, you can push the packets parallelly in the networksuch that by following a mechanism, such that it does not exceed the capacity of thatparticularly link. So, let us look into different sliding window protocols in details.(Refer Slide Time: 02:13)So, the broad idea of a sliding window protocol is as follows, that each outboundsegment in the network, it contains a sequence number. So, the sequence number field isfrom starting from 0 to some maximum sequence number say for example, if you areusing a n bit sequence number, then the sequence number space can go from 0 to 2n-1.Now, the sender it maintains a set of sequence numbers corresponding to the frames it ispermitted to send. So this particular set of sequence number we call it as a sendingwindow, similarly, the receiver it maintains a set of frames which it is permitted toaccept, we call it as the receiver window or receiving window. So, let us look into anexample in details to clear this concept.(Refer Slide Time: 03:01)So, here in the sender side so, this bounding box is the sending window. So, what does itmean? So, this is the sending window here and this is the receiver window or thereceiving window. Now, the sender window indicates that well at a time you can sendframes or packets from 0 to 6 without waiting for the corresponding acknowledgement.So that means, you can send this frames in parallel. So, you can send a frame 0, thenimmediately you can send frame 1, then you can send frame 2 without waiting for thecorresponding acknowledgement.And the receiver window say that here the receiver window side is 1 2 3 4 5 6 7 so,receiver window says that well you can receive 7 frames all together and once you havereceived 7 frames, you will not be able to receive any further frame without sending backan acknowledgement. So, what happens here that well the sender keep on sending theframe and once the sender gets back an acknowledgement, so, here say in this examplethe sender has transmitted frame 0 followed by frame 1 followed by frame 2, it issending the frames in parallel without waiting for the acknowledgement, but wheneverthe receiver has received frames 0’s and 1’s it sends the acknowledgement for frame 0.Whenever, the receiver is sending the acknowledgement for frame 0, so, the sender whatit does that it shifts the sending window for 1 unit. So, it has already received theacknowledgement for this frame so, it does not bother about this frame anymore becausethis frame has correctly being transmitted. So, my sending window becomes from 1 to 7,once you have received acknowledgement for 0. Similarly, the receiver window also getshifted because you have already send a acknowledgement for frame 0; that means, thisframe 0 has correctly received and you do not bother about this frame anymore.Then you send the receiver sends the acknowledgement 1, so, once the sender receives aacknowledge 1, so, frame 1 has also been correctly transmitted it is able to know thatinformation. So, it sends it shifts the sending window for 1 again, now my currentsending window becomes 2 to 2 3 4 5 6 7 and again starts from 0. So, this is the repeatedsequence number. So, we will look into the relation between these windows size and thesequence numbers in the subsequent discussion.So, that is the idea of this sending window and the receiving window. So, the sendingwindow basically says that you can send that many number of frames without waiting foran acknowledgement. So, if you are if you have sent all the frames of your sendingwindow and you have not received an acknowledgement, you will not be able to sendany more frames any further until you are receiving an acknowledgement and you areshifting the frames to the right side. So, that is the broad idea about the sliding windowprotocol.(Refer Slide Time: 06:04)So, here is an example of a sliding window protocol with a 3 bit sequence number. So, ifyou have a 3 bit sequence number, that means, your sequence number space can be from0 to 23-1, that means, from 0 to 7. So, here is the sequence number from 0 to 7 so, say atthe sender side you have sent one frame. So, this is a example where we are using thissequence number field in a circular queue fashion. So, after sequence number 7 again thenext frame will be marked as sequence number 0 and we are considering as window sizeof 1.So, my window size is equal to 1, so window size of 1. So, the sender here it hastransmitted say 1 frame so, once this sender has transmitter 1 frame, the sender isblocked at that position. So, the receiver is expecting for receiving this frame 0, so, theinitially the sender has not transmitted any frame, but the receiver is expecting frame 0,receiver is expecting frame 0. Now, sender has transmitted say frame 0 and the sender isblocked here because my window size is 1 and sender is transmitting the frame, theframe is on the channel, receiver is still expecting frame 0, now say receiver has receivedframe 0. So, once receiver has received frame 0, receiver is expecting from frame 1 andreceiver has say send back the corresponding acknowledgement. So, theacknowledgement is there in the channel the sender is again blocked with the frame 0,because it has transmitted that. Once the sender receives that acknowledgement, so it hasnow at this position so, the sender is ready to send frame 1 and the receiver is at thispoint expecting from frame 1. So, a sliding window protocol window size 1 is somehowsynonymous to a stop and wait flow control algorithm, because for every individualframe you are waiting for the acknowledgement, but if you increase the window sizegradually you will get the feel of parallelism.So, if you make the window size 2 from 1: that means, you can send 2 frames in parallelwithout waiting for the acknowledgement. So, once you are you have sent 2 frames thenyou wait for the acknowledgement and in between if you receive an acknowledgement,you can slide the window. So, that from there the name sliding window comes, you canslide the window and you can send frame 3. So that way this entire sliding windowprotocol works.(Refer Slide Time: 08:43)So, let us look into that how the sliding window protocol work in a noisy channel. So, incase of a noisy channel, similar to the stop and wait protocol we also implementsimilarly a timeout mechanism. So, if you have transmitted data segment, if that segmentis getting lost or sometime the acknowledgement can also get lost. If the segment or thecorresponding acknowledgement get lost and you have already sent all the frames or allthe segments in your in your say, sending window, and you are waiting for theacknowledgement corresponds to that then, a timeout may occur.And if a timeout occurs then the question comes that which particular frame you willretransmit. So, the question comes that: how does this ARQ protocol will handle thetimeout? So, timeout occur means, the receiver was not able to receive the framecorrectly and in case of a sliding window protocol you have send the set of frames andfor those set of frames the receiver has not received the frames, either the frame has beenlost or the corresponding acknowledgement has been lost. So, the question comes thathow does sender will react to it this particular loss when a timeout has occurred in thenetwork.So, there are two different mechanism to handling this timeout, one mechanism is calledas go back N ARQ and the second mechanism is called a selective repeat ARQ. Now incase of an go back N ARQ if a particular segment say segment N is lost then, all thesegment starting from segment 0, so, here I am assuming that segment 0 is the start of thesliding window to segment N are retransmitted. So, in a broad way that all the frames,which are there in the current sliding window all those frames are retransmitted if there isa timeout.In case of the second methodology which is called as the selective repeat ARQ in case ofselective repeat ARQ, you only send the lost packet or you selectively transmitretransmit the packet which has been lost in the channel. Now, whenever we say that youneed to selectively transmit the lost packet or which has been not received by thereceiver or the corresponding acknowledgement has been lost and the sender has notreceived that acknowledgement.Then; obviously, there should be some mechanism to identify those packets because, thefirst mechanism there go back N ARQ is simple enough. If you are having a timeout; thatmeans, you have not received an acknowledgement and you are not receiving anacknowledgement means you retransmit all the frames, which are there in your windowyour current window. But, if you are going to selectively retransmitting the frame thenyou have to identify that which particular frame has been lost.So, for that we have one special type of acknowledgement which is there in selectiverepeat ARQ, we call them as the negative acknowledgement NAK or some time in TCPit calls selective acknowledgement or SACK. So, this negative acknowledgement NAKor SACK, they informs the sender about which packets need to be retransmitted; thatmeans, the receiver has not received those packets and it is expecting those packets.So, those information is passed to the sender with the help of the NAK packet or with thehelp of this SACK packets. So, this NAK and the SACK packets the negativeacknowledgement and the selective acknowledgement packets, it helps you to find outthat which particular packet is expected by the receiver and like that receiver has notreceived those packets and it retransmit only those packets. So, let us look into this twoprotocols in details the go back N ARQ and the selective repeat ARQ.(Refer Slide Time: 12:36)Well first let us look into this go back N ARQ so, this go back N ARQ the senderwindow implementation is something like this. So, here we maintain two differentpointer so, one is called the base pointer so, this base pointer is the pointer from whereyour current window starts. So, your current window starts from here so, this is pointingby the base pointer so, base pointer. So, this indicates that all the frames before this basepointer has been acknowledged.So, this frames has been already acknowledged. Well so, you have already receivedacknowledgement for this frames, now these are the frames in your current windows. So,this is the this is your current window so, the base pointer points to the start of thewindow and in this current window you can send multiple frames without waiting for theacknowledgement and assumed that you have sent up to this frames. So, this setupframes sorry so, not so, this set of frames has been transmitted.So, this next sequence number this is another pointer so, this next sequence numberpoints to the frame which you can send without waiting for the acknowledgement. So, upto this frame you have already sent and you are waiting for the acknowledgement forthese frames and then you can send this particular frame further without waiting foranymore acknowledgement.So, that way with the help of these three parameters the base pointer which points to thestarting of the current window, the next sequence number: the next sequence numberpoints to the frame which you can transmit without waiting for the acknowledgement andthe window size parameter: the window size parameter indicates that what is yourmaximum window size; you can maintain the sliding window at the sender sides senderside, for go back N ARQ.
Transport Layer: Sliding Window Protocols - Part 2
Now, here if your next sequence number if your next sequence number becomes equal toyour base plus window size: that means, you have transmitted all the frame. So, hereactually in this diagram, base plus window size plus 1 if it is like this so, if you the nextsequence number is pointing to this white frame; that means, it is out of your window,current window. So, you cannot transmit this frame unless you are receiving theacknowledgement for this frames which you have already transmitted.So, once you have received these frames so, you can shift the base pointer. So, if youreceived the acknowledgement for these 5 frames up to this frame then, you can shift thebase pointer from here to here and accordingly the window size becomes here to 5 moreframes up to here. So, you will be able to utilize this next sequence number to send moreframes in parallel.(Refer Slide Time: 15:52)OK, now the go back N ARQ mechanism in a noisy channel works in this way. So, youhave transmitted say frame 0, frame 1 and at this pointer the receiver has sentacknowledgement 0. So, you have transmitted frame 2 then, frame 3 when once you havereceived the acknowledgement 0 then; that means, you can reset the timer for 0.And you can send 3 because, it belongs to your current window size you transmit theframe 3 and then you received the acknowledgement number for 1 once you arereceiving the acknowledgement for 1 you can reset the timer for 1 and you can sendframe 4 because you have you have more provision to send more frames in the currentwindow and you transmit frame 4.Now, at this point say assume this acknowledgement from receiver gets lost. So, once theacknowledgement from receiver gets from this receiver gets lost so, you are keep onwaiting for getting this acknowledgement because, at this point you are full with yourcurrent sender window so, we are here assuming that my window size is 3. So, becausemy window size is 3 so, window size is equal to 3 because my window size is equal to 3,so you have already received acknowledgement for 0 and 1, but now you are you havetransmitted frame say transmitted frame 2, 3 and 4 and you are waiting for thecorresponding acknowledgement. And here this acknowledgement for 2 got lost, so thistimeout for 2 is running.So, after some time, this timeout will for 2 will occur. So, once this timeout for 2 willoccur, you retransmit all the frames here so, in case of go back N ARQ. So, in yourcurrent window you had the frame 2, 3 and 4. So, you again retransmit frame 2, frame 3and frame 4 and again then you can get the acknowledgement immediately foracknowledgement 2, acknowledgement 3 and acknowledgement 4 once, you are gettingthis 3 acknowledgement, acknowledgement 2 3 and 4 then you shift the window furtherfrom 2 3 4 to 5 6 7 so, by transmitting those frames. So, that way this entire go back NARQ protocol works and the broad idea is here that once this time out for 1 frameoccurs, then you retransmit all the frames which were there in your current window.(Refer Slide Time: 18:26)Well so, this is the implementation of the go back N ARQ so you are in the waiting stateinitially. So, you start with the base as 1 and the next sequence number 1. Now you aregoing to getting a call for reliable data send from the application layer. So, you checkwhether your next sequence number is less than base plus N, if your next sequencenumber is less than base plus N; that means, you are able to send more data. So, you sendthe packet with that particular sequence number, you construct the packet by appendingthat next sequence number along with the data and the checksum.So, that way you are constructing the packet and with this sequence number nextsequence number and then you are utilizing this unreliable channel at the network layerto transfer this protocol. Now, if your basis becomes equal to the next sequence numberyou start the timer and increment the next sequence number OK? So, that is the case andotherwise you refuse the data so, otherwise you refuse the data means from this else iscoming. So, if your next sequence number is greater than base plus N, that means, youare trying to transfer a frame - you are receiving a frame which is outside your currentwindow. So, if it is outside your current window you do not transmit that frame.Now, if a time out occurs you again start the timer and sent all the packets from base tonext sequence number minus 1. So, you transmit all the frames which are there in yourcurrent window. Now whenever you are getting a packet and that packet is not corrupted,in that case you are checking that what is the corresponding acknowledgement numberand you are updating the base pointer accordingly. So, you are updating the base pointeraccording to the acknowledgement number that you have received plus 1 so that means,if this is your window size and this was the base pointer, now you have receive theacknowledgement for this one. So once you have received acknowledgement for baseone this one, then you move the base pointer to your next frame. And if the packet iscorrupted, then you do not bother about that, you are again in the wait loop. So, that wayyou can implement this go back N ARQ mechanism.(Refer Slide Time: 20:46)Now, similarly at the receiver side the receiver side whenever it is receiving a packet thepacket is not corrupted and it has the sequence number which is equal to the expectedsequence number. So, you extract the packet deliver the data to the application, constructan acknowledgement with the expected sequence number and use the unreliable channelat the network layer to transfer the packets and implement your expected sequencenumber.And if the default case is you transmit that acknowledgement and otherwise you just waitit is expected sequence number you initiate the system with expected sequence number1. So, that is the way we implement the receiver at the receiver side for go back N ARQ.(Refer Slide Time: 21:41)Now, let us look into that what is the relation between the window size at the sequencenumber in case of go back N ARQ. Now, in case of go back N ARQ the frames that havebeen transmitted, but not yet acknowledgement acknowledged those frames we call asthe outstanding frames. Now assume that MAX sequence MAX SEQ MAX sequencethis your maximum sequence number. So, if MAX sequence is your maximum sequencenumbers then you have MAX sequence plus 1 distinct sequence numbers from 0 to up toMAX sequence. So, this is the available sequence number space which is there with you.So, if you are using say n bit sequence number then this MAX sequence is 2n-1. Well so,you have from 0 to 2n-1 is the your total sequence number space.Now, this maximum number of outstanding frames; assume that it is equal to the windowsize. So that means, your windows size is equal to max sequence. So, that as an examplein case of our go back N ARQ protocol what we try to ensure, we try to ensure that yourwindows size is equal to max sequence.(Refer Slide Time: 23:06)That means if you are using n bit sequence number then, your window size w will beequal to 2n-1. So, you can see that it is always 1 less than the total number of distinctsequence numbers that you have. So, for example, if your sequence numbers are some 0to 7; that means, you are using a 3 bit sequence numbers.So, you can have maximum number of outstanding frame equal to 7. So, your windowsize can be equal to 7 and it is not 8 so, you have 8 distinct sequence numbers here from0 to 7, but we are not making window size equal to 8 rather we are making window sizeequal to 7. So, let us see why so, let us see that why my window size is equal to maxsequence and not equal to max sequence plus 1 although I have max sequence plus 1distinct sequence numbers.(Refer Slide Time: 23:59)So, here is an example here I am taking an example, where your max sequence is equalto 3 and window size is equal to 4. So, max sequence equal to 3 means, you have 4different sequence number 0 1 2 and 3 and I am making window size equal to that. So, ifthat is the case now think of a scenario when you have you this is your current windowsize you have transferred frame 0. So, it has received frame 0 sent back theacknowledgement, but the acknowledgement is lost then, the sender has transmittedframe 1.So, it has already send the acknowledgements so the receiver has shifted its window. So,receiver has shifted its window and receiver has sent the acknowledgement 1, again thisacknowledgement got lost. The sender has transmitted frame 2 receiver has receive thisframe 2 shifted its receiving window size and it has transmitted the acknowledgementthat acknowledgement got lost, the sender has finally sent 3. So, the 3 has being receivedby the receiver so, receive has received that frame it has shifted the window and it hassent the acknowledgement again acknowledgement got lost.Now, here is a typical example, where the receiver has correctly received all the frames,but it was not able to send the acknowledgement, it has sent the acknowledgement, butall those acknowledgement got lost in the channel so, all this acknowledgement got lost.Now in this case, now the sender will experience a timeout because the sender has notNow, let us see the an example that when your max sequence is 3, but the window size isalso 3 and the window size is not 4. In that case, the sender has send 0 1 2 3 1 and 2because my window size is 3 you can send maximum up to 2 and then you have to waitfor an acknowledgement. Now in this case, if all the acknowledgement gets dropped so,you can see that the receiver is now expecting from frame 3 and the sender willretransmit frame 0 or better to say from 0 to frame 2. Now whenever the receiver issending the frame 0 to frame 2 the receiver will be able to correctly decode that these arenot the expected frame.So, it will be able to discard the wrong frames correctly and send an acknowledgement tothe sender saying that this frames I have received. So, it will be able to find out that wellthe sender has possibly not received the acknowledgement, it will retransmit thoseacknowledgement. If the sender gets back those acknowledgement, then the sender canshift the window further and start transmitting the data from frame 3. OK, now let us look into the selective repeat protocol. In case of selective repeat protocolwhat you can do that you can acknowledge intermediate frames and some frames mayremain unacknowledged. So, what we have seen that in this particular case in case ofselective repeat, you do not need to need to retransmit all the frames once there is atimeout, rather you selectively retransmit the frames. So, here in the sender window size;it may happen that well there are some intermediate frames here this had been same, butnot yet acknowledged, but the frames here this frames they got acknowledged so thisintermediate acknowledgements are there.Now in the receiver side the this is the receiver view of the window size, so the receiverit also has a base pointer, this base pointer points that well the receiver is expecting toreceive this particular frame. And, it has not received this frame and it has received allother frames which is received out of order because this particular frame has not beenreceived yet rather you have received this frames. So, this has received out of order soyou have put those frames in the buffer and send the acknowledgement for them.So, that is the view of window for the sender and the receiver where certain intermediatepackets got acknowledged and some of the packets that are not got acknowledged andthe packets which are not got acknowledged, that need to be retransmitted. So, this is theidea of the selective repeat ARQ.(Refer Slide Time: 30:04)So, you are transmitting frame 0, then you are transmitting frame 1, at this time you areyou have transmitted both frame 0’s and 1’s. So, here we use something called acumulative acknowledgement. So this cumulative acknowledgement says that well, onceyou are receiving an acknowledgement 2, that means, frame 0’s and 1’s have beenreceived correctly and you are expecting for frame 2.Now, assume that you have transmitted frame 2, once you have got thisacknowledgement the sender shifts the window, once the sender shift the window and ithas the transmitted frame 2 assume that that frame 2 got lost and then it is able to sendframe 3. So, it has transmitted frame 3 so, the receiver has received frame 3 once thereceiver has received frame 3 then it has received this frame out of order because it hasnot received frame 2, but it has received frame 3.So, it puts frame 3 in the buffer and sends a negative acknowledgement. So, let us see an example that why this holds true so, similar to the earlier case here youneed to remember that whenever you are sending certain frames, the sender can sendacknowledgement in between. So, negative acknowledgement in between. So, here thesender has sent so, I have taken an example where my MAX sequence is 3. So, if myMAX sequence is 3; that means, my earlier ideal window size should be equal to 2 to thepower if my max sequence is 3 then my window size should be equal to (3 + 1)/2; thatmeans, equal to 2, but here we are using a window size 3, 1 more than the actual it iswindow size that we should use.So, here we keep the window size as 2 so, if I am keeping window size as 2 then thesender sends 0 and 1 and waiting for the acknowledgement similarly all theacknowledgement got lost. So, it has sent frame 0 and 1 and so, it is expecting frame 2and 3, but if there is a time out here the sender retransmits frame 0. When the sender is retransmitting frame 0 it can correctly find out that it is expecting frame 2 and 3 not frame0 and 1 so, it can discard the frame correctly. So, we can see that particular confusionwhich was there that can get resolved if I using window size as max sequence plus 1 by2. So, here it is equal to 2 3 plus 1 by 2 equal to so, with this particular window size weare able to resolve this particular confusion. So, that is all about the sliding windowbased flow control algorithms, the go back N ARQ and selective repeat ARQ mechanismwhich helps you to send the packets in a pipeline fashion and at the same time helps youto resolve for loss. So, in the next class we’ll look into some other aspects performanceaspects of transport layer protocol and during the discussion of TCP we will see that howthis flow control algorithms are actually implemented in TCP type of protocol.So, thank you all for attending the class.
Log in to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Networks and Internet Protocol online course
Sign up to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Networks and Internet Protocol online course
Please enter you email address and we will mail you a link to reset your password.