Data Link Layer-Flow and Error Control
Hello will continue our discussion on Computer Networks and Internet Protocol, in lastfew lectures we are discussing on data link layer 2 in the OSI, also in important layer,Ialso in TCP/IP. So, we have looked into ethernet and different other features of layer 2and today we will see something on Flow and Error Control.You will find similarity or between the flow and error control, what you have studied intransport layer or in the transport layer phenomenon, where it in transport layer, it takescare of the end to end process right that process a process in system 1 is process P, insystem 1 talking to process Q in system 2 and there is a process to processcommunication. Where as in this case we have a hop to hop communication right that inlayer 2 hop to hop this is system connected to a to a nearby switch.So, it is that hop connectivity is there, you also and has to you know that that a particularethernet frame or has a source address, destination MAC address and the payload whichis getting from the higher layer right and with other things like error checking, preamble(Refer Time: 01:44) type of things. So, what is important, when we communicatespecially these days, when you have switched network switch full duplex networks andthings that the to, how this error and flow control mechanism are handled in thisscenarios right. So, will take a overall overview of the work flow and error control and asI am again repeating that the overall mechanism is conceptually is similar to that whatwe have seen in the transport layer, but here at the we are doing at the data link layer.
(Refer Slide Time: 02:30)
So, flow control coordinates amount of the data that can be sent before receiving theacknowledgement right.So, what is there? Whenever I am sending a data to somebody right so, after sending Iam expecting acknowledgement, the data is received or not to resend. So, what flowcontrol coordinates the amount of how much data, you can send before receiving theacknowledgement type of things, every bitwise byte wise, kilobyte wise or chunk wiseand whatever the things right. Flow control is a set of procedure that tells the sender, howmuch data it can transmit before, it must wait for an acknowledgement from the receiverright.So, that is a mechanism it says that you say I say, that you sent every packet of so muchthings or every frame and get a acknowledgement send and explain, what I say that yousent 5 frames wait for the 5 acknowledgement and type of things I say 5 frame issequence and then wait for the last the maximum acknowledgement thing that all will bethere. So, it is say mechanism, it is a procedure, it is a protocol, it is a overall procedureneed to be there. Receiver has a limited speed at which, it can process incoming data anda limited amount of memory in which store the incoming data. So, what we see that thereceiver it is basically receiving it is a speed at the limited speed (Refer Time: 04:00) orat a speed it can receive.
It can store some of data type of things. Receiver must inform the sender, before thelimits are reached and request that transmitter to send fewer frames or stop temporarilyright. So, if it is overall with the data, it should must sender the sender that 2 thing, it ishungry of the data, it is basically dearth of the data as the sender to send more or if it isoverwhelm in the data, it should say that the stop sending and or at a reduced rate (ReferTime: 04:33) right. So, this all are has to be through a procedure, which is primarily aflow control mechanisms right.Since the rate of processing is often slower than, the rate of transmission receiver hasblock of memory or buffer for storing the incoming data, until they are processed right.In general the rate of processing with more high speed things are coming up. So, rate ofprocessing the data is often slower than, the rate of transmission. So, usually you areoverwhelming with that data. So, receiver has to maintain a buffer or a memory block,where the data can be incoming data can be stored and processed like whatever is in thestore and forward it store the data process the data and type of things, but there is a thatis a limit for the buffer also that, how much you can, it is not a indefinite buffer, you cango on storing indefinite time right. So, that is a restriction on the how much buffer, youcan store the data and type of things.(Refer Slide Time: 05:48)
So, on the other hand so, one aspects of a ethernet or layer 2, the data link layer is tohave a mechanism for flow control right otherwise, faithful communication at expected
rate etcetera, will be difficult to maintain unless, there is a flow control mechanismwhich manages the flow. So, that is that is one important thing, other in aspects of thething the error control. The data is sent from the receiver sender to the receiver, receiverdoes not reach it, received it or while sending the acknowledgement, acknowledgementis lost or delayed sometimes it is not lost, it is delay it corrupted and type of things comeup into the things. So, that is only important to the how to over all control the error inthis layer 2 transmission.So, error control includes both error detection and error correction right, it allowsreceiver to inform the sender, if the frame is lost or damaged during the transmission andcoordinate the retransmission of those frames by sender right. So, it allows us receiver toinform the sender that whether the frame is lost or damaged during the transmission andcoordinates the retransmission of those frames by the sender. If there is a lost of frame,damaged of the frame that should be retransmission, error control in the data link layer isbased on a concept of ARQ or automatic repeat request right, whenever there is a error isdetected specified frames are retransmitted right. So, it is a automatic repeat request. So,it is requesting for a automatic repeat of the things. So, that is a mechanisms which isthere.(Refer Slide Time: 07:42)
So, error and flow control mechanism as you might have seen earlier also. So, one is thestop and wait mechanism and Go-Back-N ARQ mechanism, selective repeat mechanism.
So, these are the 3 predominant mechanisms, which is followed or which is deployed inthe layer 2 of our standard local area network implementations.(Refer Slide Time: 08:16)
So, in case of stop and wait it is pretty straight forward, sender keeps a copy of the lastframe, until it receives a acknowledgement right. So, sender keeps a things for theidentification both frames and the acknowledgment are numbered alternatively 0 and 1so, 01, 01, 01 and type of things right. So, once the frame is sender the 0,acknowledgement comes as a 1 sender frame as 1 acknowledgement comes as 0 andalternatively goes on right.So, the receiver on receiving the acknowledgement it gets the thing that it is (Refer Time:08:56) successfully transmitted. The sender has a control variable S and holds thenumber of the recently sent frame 0 or 1 right. So, control variable takes care of thethings, the receiver as a control variable R and holds the number of the next frameexpected 0 or 1 right. Sender start a timer, when it says the frame if an acknowledgementis not received within a allocated time period or within the threshold period or within thetimeout period, the sender assume that the frame was lost or damaged and resends itright. Receiver sends only positive acknowledgement, if the frame is intactacknowledgement number always defines the number of the next expected frame right.So; that means, you see here the acknowledgement 1 means the next expected frame is 1acknowledgement, 0 is the expected frame is with the is of the sequence 0 and type of
thing. So, this is a very simple mechanism, but it this allows for this flow and errorcontrol rate. So, frame 0 is send acknowledgement send back as 1 on receiving thethings, it asks for the frame 1 is sent, acknowledgement send as a 0 and so on so forth.So, alternatively 0 1 0 1 things will go.(Refer Slide Time: 10:28)
Stop and wait ARQ lost acknowledgement frame, there is a there is a acknowledgementframe is lost right. So, when receiver receives a damaged frame, it discards it and keepthe value keeps the value of R. In this case, if receive the damaged frame and discards itand keep the R equal to 1, after the timer at the sender expires, another copy of the 1 issent right. So, it once within the time limit, the sender does not receive theacknowledgement, it will send the another that frame 1 is retransmitted to the receivermeans sender to receiver right.
(Refer Slide Time: 11:13)
So, this is a sorry, it is a lost frame right. So here, it is a lost acknowledgement frame. So,frame this is lost acknowledgement frame. So in this case, if the sender receives adamage acknowledgement in discards it right. So, the sender gets acknowledgement,which is a damaged one and it discards it and how it is identifying? Because you youmean the format we are FCS right frame checks sequence is there that CRC (Refer Time:11:52) 32 and so on so forth. It can it is able to find out, the there is a error or not, whenthe timer of the sender expire, the sender retransmit the frame 1 right. Receiver alreadyreceives the frame 1 expecting to received frame 0 therefore, discards the second copy offrame 1 right because, it is already received the frame 1 found it faithfully and, butreceived again frame 1. So, it discards the second copy because, it is expecting a frame 0right. So, that way it goes on means, it handles that lost acknowledgement. So, even theacknowledgement is lost in the retransmission phase, it can basically detected.
(Refer Slide Time: 12:42)
Stop and wait, delayed acknowledgement frame. So, happen that acknowledgement issent, but it is delayed right acknowledgement can be delayed at the receiver or due tosome problem right. It is received after the timer for the frame 0 has expired sendertransmitted a copy of the frame 0; however, R equal to 1 means, the receiver expect tosee a frame 1 right. So, receiver discards the duplicate frame 0 right. Previously whatwas there?That it has a duplicate 1, because of that acknowledgement problem here the, there is adelayed acknowledgement and the sender thinks that the frame has lost, it will retransmitthe frame again and it discards the frame 0. The frame 0 twice transmitted discards the 0sender receives 2 acknowledgement, it discards the second acknowledgement if thesender is 2 acknowledgement because, the actual delayed 1 then, the now actual 1 andthen it discards the second acknowledgment.
(Refer Slide Time: 13:57)
There is a concept of piggybacking right. Now because, this both sending the data andacknowledgement are eating away space. So, when we have a both communication, bothside communication like station AB, both have data to send then the a method tocombine data frame with acknowledgement, the data frame itself carry theacknowledgement.So, the acknowledgement frame piggyback on the data frame instead of sendingseparately station a sends the data frame that includes an acknowledgement. Station Bdoes the same thing, piggybacking saves bandwidth right. So, instant otherwise thisacknowledgement frames should have been another channel right; however, small it maybe it requires some bandwidth to transmit right. So, this piggyback on the other means onthe data, which are send across the across A and B.
(Refer Slide Time: 14:59)
Disadvantage of stop and wait. In stop and wait, any point of time there is only 1 framethat is sent right and waiting to be both the acknowledgement. So, it is sent waiting forthe acknowledgement still the timeout and type of things right. This is not a good way ofutilising the transmission media so, that is a when the media keeping the media underutilised or not utilised for a longer time is not acceptable. So, there are 2 protocol is oneis Go-Back-N, another is Selective Repeat ARQ, Go-Back-N ARQ and Selective RepeatARQ, which are which are used to take care of these underutilised bandwidth or that theproblem
Data Link Layer: Flow and Error Control - Part 2
So, Go-Back-N ARQ, we can send up to W frames before the worrying about theacknowledgement, send that W frames, we keep a copy of these frames until theacknowledgement receives. This procedure requires additional features to be added in thestop and stop and wait ARQ right. So, which bunch of frames are same in and the copyof kept instead of waiting that every acknowledgement, this the acknowledgement iscoming it is goes on reconciliation or what we say that, goes on acknowledging theframes are if the acknowledgement not received and send retransmission required so andso forth.(Refer Slide Time: 16:32)
So, as we have a bunch of frame, there is not 1 sending and receiving and type of thing.So in this case, what we require is a sequence number right, frames from a sender arenumbered sequentially, we need to set the limit since, we need to include the sequencenumber of each frame in the header, set a limit. So, if the header frame allows m bits forthe sequence number.The sequence number range is 2, the power 0 2, the power m minus 1 right or m equal to3, sequence number is 1, 2, 3, 4, 5, 6, 7 right or this is the sequence number, we arehaving we can expect the sequence, we can repeat the sequence number of that thosethings right. So, it is 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7 and so on so forth. So, thesequence number can be repeated on the means on a regular basis.
(Refer Slide Time: 17:36)
So, from the sending, send the sliding window at the sending a to hold the outstandingframes, until they are acknowledged, we use the concept of a window right, becauseunless this is acknowledged that has to hold right. We cannot discards those that thesender ends, size of the window is at most 2 the power of m minus 1, where m is thenumber of bits in the sequence number right. If there are 3 bit 2 to the power 3 minus 1type of things.Size of the window can be variable, how much? That all depends on the data rate (ReferTime: 18:14) type of things; the windows slides to include new unsent frames whencorrect acknowledgement are received right. So, the window slides to include newunsent frames like here, this ones the acknowledgement 0, 1 is it slides to send the nextthings. So, up to 4 received, it slides again and go on like that.
(Refer Slide Time: 18:39)
At the receiving window, size of the receiving window is always 1 for this protocol right.Receiving window always looking for a specific frame to arrive in the specific order. So,whether it is sliding or not at the sender end, receiving is waiting for that specific numberof frames, may be in the sequence to wait for the in a specified order right.Any frame arising out of order is discarded and need to be retransmitted right in a framearising due to say, monthly path, delay, etcetera. So, will be out of order (Refer Time:19:16). Receiver window slides as. So, this is the receiver window slide shown in thefigure, the receiver is waiting for frame 0, in figure 1 and then 1, it is received slides tothe waiting for frame 1.
(Refer Slide Time: 19:34)
Control variable, sender has 3 variable S, SF and SL. So, 1 is the end of methods that iswhat we say first frame, last frame and S is the currently send frame. So, right receiverhas only 1 variable R to hold the sequence number of the frame, it expects to receive. So,it is expecting 0 to receive it will be on that things, if the sequence number is the same asthe value of R.The frame is accepted otherwise rejected. So, the if things received as 0 as it is waitingfor the 0, then it is accepted otherwise things are rejected.(Refer Slide Time: 20:14)
Acknowledgement as we see plays important role right that how the acknowledgement isthere receiver sends positive ACK if a frame arrived safe and in a order; that means, it iscorrect and in order. If the frames are damaged out of order receiver silent and discardsall subsequent frames until it receives the one it is expecting. So, it is instead of it isexpecting 1 instead of 1, it is receiving 2 3 etcetera, it discards all frames right then thesender resends all the frames beginning with the 1, which has expired timer for example,suppose the sender has frame 6, but the timer for the frame 3 expires then, the sender goback and sends the frame 3, 4, 5, 6, this is called Go-Back-N ARQ. The receiver does nothave to acknowledge each frame received, it can send 1 accumulate cumulativeacknowledgement for several frames that is also possible.(Refer Slide Time: 21:12)
So, this is the Go-Back-N ARQ, sender keeps track of the outstanding frames that are anupdates the variables and windows at the acknowledge arrives right.
(Refer Slide Time: 21:33)
And in case of a lost frame. Frame say in this case, frame 2 is lost, when the receiverreceives frame 3 discards frame 3, it is expecting 2 as we are discussing. So, it hasexpecting, 2 here and receive 3 instead of 2 discards. The timer from the 2 expire and thesender side and sender sends frame 2 and 3, go back to N, that is go back to 2, in thiscase.(Refer Slide Time: 22:01)
Go back to Go-Back-N ARQ damage, lost, delayed acknowledgement. If theacknowledgement is damaged or lost, we can have 2 situations, if the next
acknowledgement arrives before the expiry of any timer, there is no need forretransmission of the frames because, the acknowledgement are cumulative in thisprotocol. So, it is a cumulative. So, that is the next acknowledgement there is no (ReferTime: 22:30) of retransmission if a AKC 1 sorry, ACK 1, ACK 2, ACK 3 are lost. ACK 4covers them if it arrives before the timer expires, then its a its a cumulative thing. If ACK4 arrives after the time out, the last frame of all the frames after that are resent right,receiver never resends an acknowledgement. So, receiver never resends anacknowledgement, it is only 1, it is sends a delayed acknowledgement also triggers theresending. So, a delayed acknowledgement is also in the case of a is like a damage or lostand it triggers a resending of the frames.(Refer Slide Time: 23:12)
So, on the sender side Go Back N ARQ. The size of the window must be less than 2power m, size of the receiver is always 1, if is equal to 2 the size is 2 to the power 2minus 1 is 3. So, figure compares the window size of 3 and 4 that how things will bethere accepts as a first frame in the next cycle and error and so, it goes on looking at thethings right. So though, there is a lot of frames are lost, it has got erroneously got thethings erroneously 0 and it is expecting this 0 and mistaking to the 0 and which iserroneously accepted, where is in this case, if there is a loss, it is it is expecting 2 and butat the 3 correctly discarded. So, is not received a 0. So, it is correctly discarded right. So,it is also that window size plays role in this sort of scenarios.
(Refer Slide Time: 24:26)
Selective repeat ARQ sender and receiver windows, this is another ARQ mechanisms.So, Go-Back-N ARQ simplifies process of the receiver side right, receiver only keepstrack of only 1 variable right and there is no need of buffer out of order frames andsimply discard the things, if anything out of the frame coming, in case of a Go-Back-NARQ, then you just simply discard the thing. So, was the thing right; however, inselective repeat ARQ only damage frames are resent; more bandwidth efficient, but morecomplex at the processing in the it means selective repeat; that means, you are notdiscarding, in case of go back N in for finding 1 out of water, discard everything afterthat, but in selective repeat you are not discarding all you are only discarding, which areerroneous or damage frames and type of things right you are you. So, selectivelyrequesting resend from the sender for the selective frames. It sends, it defines a negativeacknowledgement pr NAK to report the sequence number of a damaged frame, beforethe timer expires. So, it sends a negative acknowledgement or NAK right.So here, instead of in the case of Go-Back-N, what we have seen there are this is SF, SLand S was there and whereas, here we R F and R L that cannot be accepted framereceived and acknowledged right out of that things, which are received andacknowledged here frames acknowledged, frames awaiting acknowledgement is afterthat right.
(Refer Slide Time: 26:33)
So, in selective repeat ARQ, lost frame 0 and 1 are accepted, when the received acceptedwhen receive because, they are in the range specified by the receiver window of theframe 3 (Refer Time: 26:47).So, it is within the receiver window size. So, it is 0 and 1 are accepted, when receivedbecause they are in the range of the (Refer Time: 26:58) right. Receiver sends a receiversends a NAK2 to show that the frame 2 has not been received right and sender theresends only frame 2 and it accept and it is accepted as it is the range of the windowright. So this, a range of the window matters much. So, if it is within the range of thewindow. So and then there you receive a NAK of request repeat or selective repeat of aparticular frame, then it is resend by the sender.
(Refer Slide Time: 27:35)
So, again selective repeat ARQ is the sender windows, window again plays a importantrole, size of the sender and receiver window must be at most half that 2 to the power m;that means, m is equal to 2. So, size will be 2 to the power 2 by 2 2 so window size is 3an all acknowledgement as lost sender sends duplicate frame 0 right like in other case,also if it is window size is greater than 2 to their m minus 1; that means, to your mdivided by 2 then, I can receive accept this 1 though, it was damaged, I accept thiserroneously accepted, where as if it is within that thing, that it is correctly discarded bythe receiver.So, window size 3, all acknowledgement has lost. Sender sends duplicate frames 0windows of the receiver expect receive frame part of the windows accept the 0 and thefirst frame of the next cycle. So, it is a error. So, it is accepted in a erroneous mannerright. So, what we see here, in this sort of flow and error control mechanisms. So, thesender receiver with help of acknowledgement, in case of the first 1 stop and wait it iseverything is acknowledged, every frame to individually acknowledged, but in go backN what we have seen that, the receiver has only 1 pointer, where as a bunch of thing,bunch of frames can be send from the receiver from the sender end. And it also send acumulative acknowledgement has a option of sending cumulative acknowledgement inrepeat ARQ selective repeat ARQ.
So, in case of go back N, if there is a error everything after that need to retransmittedwhere as the mechanism is the NAKs mechanism has a better utilization of thebandwidth when is a repeat ARQ, they need it sends only those selective frames whichhas damaged or erroneous things like that right. And in both the cases what will ask 2cases, what your seen this window size plays an important role right, otherwise you mayerroneously accept something right, if the window size is not properly maintain. So, thatis important for things, this flow and error control mechanism over and above tries tohave provide a better utilization or better flow mechanisms within the things.So, you have a better utilization of the bandwidth or provide a better quality of servicefor this mechanisms right. So, this is the overall flow and error control mechanism. So,with this we look we conclude the our basic flow and error control mechanism in thedata to data link layer and also we see that this provides, say this helps us in providing abetter utilization of the bandwidth right. There is 2 issues are there 1 is the bandwidth isnot available right, you have a 10 Mbps and more data to be you have a higherbandwidth, but due to in proper utilization, you may not be exploiting that in a properway.So, in subsequent lecture will see other aspect of the things, there are several data linklayer or switching aspect those things. We will be looking at which also which are someof things in also have linkage with higher level network layer phenomenon. So, that willsee in the subsequent lecture or on this particular series of lecture will be looking at. So,let us conclude today.Thank you.