Unit 2_ Flow & Error Control in computer networks

cn

1. Flowcontrol:Itisasetofproceduresthattellsthe
senderhowmuchdataitcantransmitbeforeitmust
waitforanacknowledgementfromthereceiver.
Receiverhasalimitedspeedatwhichitcanprocess
incomingdataandalimitedamountofmemoryin
whichtostoreincomingdata.
Receivermustinformthesenderbeforethelimitsare
reachedandrequestthatthetransmittertosendfewer
framesorstoptemporarily.
Sincetherateofprocessingisoftenslowerthanthe
rateoftransmission,receiverhasablockofmemory
(buffer)forstoringincomingdatauntiltheyare
processed.
Praveen kumar 8

2. Therearetwoprotocolsusedinflowcontrol
1.StopandWaitProtocol
2.SlidingWindowProtocol
Praveen kumar 9

3. 1.StopandWaitProtocol:
Sourcetransmitsframe.Destinationreceivesframeand
replieswithacknowledgement(ACK).
SourcewaitsforACKbeforesendingnextframe.
Senderkeepsacopyofthelastframeuntilitreceivesan
acknowledgement.
Foridentification,bothdataframesandacknowledgements
(ACK)framesarenumberedalternatively0and1.
Senderhasacontrolvariablethatholdsthenumberofthe
recentlysentframe.(0or1)
Receiverhasacontrolvariablethatholdsthenumberofthe
nextframeexpected(0or1).
Senderstartsatimerwhenitsendsaframe.IfanACKisnot
receivedwithinaallocatedtimeperiod,thesenderassumes
thattheframewaslostordamagedandretransmitit.
Praveen kumar 10

4. 1.StopandWaitProtocol:
ReceiversendonlypositiveACKiftheframeisintact.
ACKnumberalwaysdefinesthenumberofthenextexpected
frame.
Praveen kumar 11

5. Instop-and-wait,atanypointintime,thereisonlyone
framethatissentandwaitingtobeacknowledged.
Thisisnotagooduseoftransmissionmedium.
Toimproveefficiency,multipleframesshouldbein
transitionwhilewaitingforACK.
Praveen kumar 12

6. 2.SlidingWindowProtocol:
Thismethodallowsthesendertotransmitaspecific
numberofframeswithoutreceivingpositive
acknowledgementsforindividualframes.
ACKincludesnumberofnextframeexpected.
Inthisprotocoleachoutboundframecontainsa
sequencenumber.
Ifnbitsareallocatedthesequencenumberrange
from0to2
n
-1.
Ex:Ifa3bitnumberisusedthesequencenumbers
wouldrangefrom0to7.
Thesenderandreceivermaintainawindow.
Praveen kumar 13

7. Praveen kumar 14

8. Example of Sliding Window Protocol:
Praveen kumar 15

9. SendercansenduptoWframesbeforeworrying
aboutACKs.
SenderkeepsacopyoftheseframesuntiltheACKs
arrive.
Praveen kumar 16

10. Errorcontrolisimplementedinsuchawaythatevery
timeanerrorisdetected,anegativeacknowledgement
isreturnedandthespecificframeisretransmitted.
Thisprocessiscalledautomaticrepeatrequest.
Errorcontrolinthedatalinklayerisbasedonautomatic
repeatrequest,whichistheretransmissionofdamaged
orlostdata.
ReceiversendspositiveACKifaframearrivedsafe
andinorder.
Therearetwoprotocolsusedinerrorcontrol
 1.StopandWaitARQProtocol
2.GoBackNProtocol
 3.SelectiveRepeatARQ/SelectiveRejectARQ
Praveen kumar 17

11. 1.StopandWaitARQProtocol:
Thesenderkeepsacopyofthelastframetransmitteduntilit
receivesanacknowledgementforthatframe.
Keepingacopyallowsthesendertoretransmitlostor
damagedframesuntiltheyarereceivedcorrectly.
Ifanerrorisdiscoveredintransit,aNAKframeisreturnedto
tellthesendertoretransmitthelastframesent.
Thesendershouldwaituntilitreceivesanackforthelast
frametransmittedbeforeittransmitsnextframe.
Ifanexpectedackisnotreceivedwithinthesender’stimer
expires,thesenderassumesthatthelastdataframewaslost
andretransmitit
Whiletransmittingaframetherecanbethreesituations
 i.Damagedframe
 ii.Lostdataframe
 iii.Lostacknowledgement
Praveen kumar 18

12. i.Damagedframe:Whentheframecontainserror,
receiverreturnsNAKframeandsenderretransmits
thelastframe
Praveen kumar 19

13. ii.Lostdataframe:Iftheframeisnotreceived,the
receivercannotacknowledgeit.Thesenderwaitsforan
ACK/NAKuntilitstimerexpires.
Itretransmitsthelastdataframe,restartitstimerand
waitsforanACK.
Praveen kumar 20

14. iii.Lostacknowledgement:Thesenderwaitsforack
untilitstimerexpires.Ifackisnotreceivedbeforethe
sender’stimergetexpiresthesenderretransmitsthe
lastframe.
Praveen kumar 21

15. 2.GoBackNProtocol:
WecansenduptoWframesbeforeworryingabout
ACKs.
WekeepacopyoftheseframesuntiltheACKsarrive.
Iftheframesaredamaged/outoforder,receiveris
silentanddiscardallsubsequentframesuntilit
receivestheoneitisexpecting.
Thesilenceofthereceivercausesthetimerofthe
unacknowledgedframetoexpire.
Thenthesenderresendsallframes,beginningwiththe
onewiththeexpiredtimer.
Praveen kumar 22

16. Forexample,supposethesenderhassentframe6,
butthetimerforframe3expires(i.e.frame3has
notbeenacknowledged),thenthesendergoesback
andsendsframes3,4,5,6again.ThusitiscalledGo-
Back-N-ARQ
Thereceiverdoesnothavetoacknowledgeeach
framereceived,itcansendonecumulativeACKfor
severalframes.
Whiletransmittingaframetherecanbethree
situations
 i.Damagedframe
 ii.Lostdataframe
 iii.Lostacknowledgement
Praveen kumar 23

17. •i.Damagedframe:Frame3isdamaged.
•Whenthereceiverreceivesframe4and5,itdiscards
frame4and5asitisexpectingframe3.
•Afterthetimerforframe3expiresatthesenderside,the
sendersendsframe3,4and5.
Praveen kumar 24

18. •ii.Lostdataframe:Frame2islost.
•Whenthereceiverreceivesframe3and4,itdiscards
frame3and4asitisexpectingframe2.
•Afterthetimerforframe2expiresatthesenderside,the
senderretransmitsframe2,3and4.

Praveen kumar 25

19. •iii.Lostacknowledgement:ACK3islost.
•Whenthereceiverreceivesframe0,1and2,itsendsACK
3forindicatingthatuptoframe2allframesare
successfullyreceivedandthenextexpectedframeis3.
•ButACK3islost.Afterthetimerforframe2expiresat
thesenderside,thesenderretransmitsframe0,2and2.

Praveen kumar 26

20. 3.SelectiveRepeatARQ/SelectiveRejectARQ:
•InSelectiveRepeatARQ,onlythedamagedframeis
resent.Morebandwidthefficient.
•ItdefinesanegativeACK(NAK)toreportthesequence
numberofadamagedframebeforethetimerexpires.
Praveen kumar 27

21. •Frames 0,1,3,4 and 5 are accepted when received.
•Receiver sends a NAK 2 to show that frame 2 is
damaged and then sender retransmits only frame 2.
Praveen kumar 28

22. Networksmustbeabletotransferdatafromone
devicetoanotherwithacceptableaccuracy.
Datacanbecorruptedduringtransmission.
Someapplicationsrequirethaterrorsbedetectedand
corrected.
Someapplicationscantolerateasmallleveloferror.
Forexample,randomerrorsinaudioorvideo
transmissionsmaybetolerable,butwhenwetransfer
text,weexpectaveryhighlevelofaccuracy.
Praveen kumar 29

23. TypesofErrors:
Single-BitError:
Thetermsingle-biterrormeansthatonly1bitofa
givendataunit(suchasabyte,character,orpacket)is
changedfrom1to0orfrom0to1.
Praveen kumar 30

24. BurstError:
Thetermbursterrormeansthat2ormorebitsinthe
dataunithavechangedfrom1to0orfrom0to1.
Praveen kumar 31

25. Redundancy:
Thecentralconceptindetectingorcorrectingerrorsis
redundancy.
Todetectorcorrecterrors,weneedtosendextra
(redundant)bitswithdata.
Theseredundantbitsareaddedbythesenderand
removedbythereceiver.
Theirpresenceallowsthereceivertodetectorcorrect
corruptedbits.
Typesofredundancychecks:
1.Verticalredundancycheck
2.Longitudinalredundancycheck
3.Cyclicredundancycheck
Praveen kumar 32

26. 1. Vertical redundancy check(VRC):
◦Appendasinglebitattheendofdatablocksuchthatthe
numberofonesiseven.
◦Even Parity (odd parity is similar)
0110011 01100110
0110001 01100011
◦VRC is also known as Parity Check
◦Performance: Detects all odd-number errors in a data block
Praveen kumar 33

27. 2. Longitudinal redundancy check(LRC):
Organizedataintoatableandcreateaparityforeach
column.
Assumethatiftheaboveblockhitbybursterror,when
thereceivercheckstheLRC,someofthebitsdonot
followevenparityruleandwholeblockisdiscarded.
1100010111010100101110011110110110101010
 BlockwillbediscardedduemismatchofLRC
Praveen kumar 34
11100111 11011101 00111001 10101001
11100111
11011101
00111001
10101001
10101010
11100111 11011101 00111001 10101001 10101010
Original Data LRC

28. 3.Cyclicredundancycheck(CRC):CRCismorepowerful
thanVRCandLRCindetectingerror.
Atthesendersidethedataunittobetransmittedis
dividedbypredetermineddivisorinordertoobtainthe
remainder.
ThisremainderiscalledCRC.
TheCRChasonebitlessthanthedivisor.
ThesenderappendsthisCRCtotheendofdataunit
suchthattheresultingdataunitbecomesexactly
divisiblebypredetermineddivisor.
Thatisremainderbecomeszero
Praveen kumar 35

29. Atthedestination,theincomingdataunit,thatisdata
+CRCisdividedbythesamenumber(predetermined
divisor).
Iftheremainderafterdivisioniszerothenthereisno
errorinthedataunitandreceiveracceptit.
Iftheremainderafterdivisionisnotzero,itindicates
thatthedataunithasbeendamagedintransitand
thereforeitisrejected.
Praveen kumar 36

30. Sender Side:
Praveen kumar 37

31. Receiver Side:
Praveen kumar 38