stop and wait

kk

1. FLOW AND ERROR CONTROL

2. FLOW AND ERROR CONTROL
Themostimportantresponsibilitiesofthedatalink
layerareflowcontrolanderrorcontrol.Collectively,
thesefunctionsareknownasdatalinkcontrol.
Flow Control
Error Control
Topics discussed in this section:

3. Flow control refers to a set of procedures
used to restrict the amount of data
that the sender can send before
waiting for acknowledgment.
Note

4. Error control in the data link layer is
based on automatic repeat request,
which is the retransmission of data.
Note

5. PROTOCOLS
Nowletusseehowthedatalinklayercancombine
framing,flowcontrol,anderrorcontroltoachievethe
deliveryofdatafromonenodetoanother.The
protocolsarenormallyimplementedinsoftwareby
usingoneofthecommonprogramminglanguages.To
makeourdiscussionslanguage-free,wehavewritten
inpseudocodeaversionofeachprotocolthat
concentratesmostlyontheprocedureinsteadof
delvingintothedetailsoflanguagerules.

6. Taxonomy of Flow and error control protocols

7. NOISELESS CHANNELS
Letusfirstassumewehaveanidealchannelinwhich
noframesarelost,duplicated,orcorrupted.We
introducetwoprotocolsforthistypeofchannel.
Simplest Protocol
Stop-and-Wait Protocol
Topics discussed in this section:

8. Itisverysimple.Thesendersendsasequenceofframes
withouteventhinkingaboutthereceiver.Tosendthree
frames,threeeventsoccuratthesendersiteandthree
eventsatthereceiversite.Notethatthedataframesare
shownbytiltedboxes;theheightoftheboxdefinesthe
transmissiontimedifferencebetween
thefirstbitandthelastbitintheframe.
Simplest Protocol

9. Figure 1 Flow diagram for Simplest Protocol

10. AlgorithmSender-site algorithm for the simplest protocol

11. Algorithm Receiver-site algorithm for the simplest protocol

12. Itisstillverysimple.Thesendersendsoneframeand
waitsforfeedbackfromthereceiver.WhentheACK
arrives,thesendersendsthenextframe.
Stop-and-wait protocolworks under the assumption
that the communication channel isnoiselessand
transmissions areerror-free.
Working:
•The sender sends data to the receiver.
•The sender stops and waits for the acknowledgment.
•The receiver receives the data and processes it.
•The receiver sends an acknowledgment for the above
data to the sender.
•The sender sends data to the receiver after receiving
the acknowledgment of previously sent data.
•The process is unidirectional and continues until the
sender sends theEnd of Transmission (EoT)frame
Stop and Wait Protocol

13. Figure 2 Flow diagram for Example 11.2
Notethatinfigure2,sendingtwoframesin
theprotocolinvolvesthesenderinfourevents
andthereceiverintwoevents.

14. AlgorithmSender-site algorithm for Stop-and-Wait Protocol

15. Algorithm Receiver-site algorithm for Stop-and-Wait Protocol

16. NOISY CHANNELS
AlthoughtheStop-and-WaitProtocolgivesusanidea
ofhowtoaddflowcontroltoitspredecessor,noiseless
channelsarenonexistent.Wediscussthreeprotocols
inthissectionthatuseerrorcontrol.
Stop-and-Wait Automatic Repeat Request
Go-Back-N Automatic Repeat Request
Selective Repeat Automatic Repeat Request
Topics discussed in this section:

17. Error correction in Stop-and-Wait ARQ is
done by keeping a copy of the sent
frame and retransmitting of the frame
when the timer expires.
Note

18. In Stop-and-Wait ARQ, we use sequence
numbers to number the frames.
The sequence numbers are based on
modulo-2 arithmetic.
Note

19. In Stop-and-Wait ARQ, the
acknowledgment number always
announces in modulo-2 arithmetic the
sequence number of the next frame
expected.
Note

20. Stop-and-Wait ARQ
1.Itprovidesbotherrorcontrolandflowcontrol
2.ErrorcontrolinstopandwaitARQisdonebykeepinga
copyofframeuntilitreceivesaacknowledgement
3.Senderstartatimerwhenitsendaframe.IfACKisnot
receivedwithintheallocatedtimeperiod,thesender
assumethattheframewaslostordamageandresent
it.
4.ReceiversendanACKtosenderifitreceivesaframe
correctly.
5.ACKnumberalwaysdefinethenumberofthenext
expectedframe.
Stop and wait ARQ = Stop and wait + Time out + Sequence
Number (Data) + sequence number (ACK))
1.

21. Stop-and-Wait ARQ
For identification, both data frames and
acknowledgements (ACK) frames are numbered
alternatively 0 and 1.
Sender has a control variable (S) that holds
the number of the recently sent frame. (0 or
1)
Receiver has a control variable ® that holds
the number of the next frame expected (0 or
1).

22. Figure3showsanexampleofStop-and-WaitARQ.
Frame0issentandacknowledged.Frame1islostand
resentafterthetime-out.Theresentframe1is
acknowledgedandthetimerstops.Frame0issentand
acknowledged,buttheacknowledgmentislost.The
senderhasnoideaiftheframeortheacknowledgment
islost,soafterthetime-out,itresendsframe0,whichis
acknowledged.
Stop-and-Wait ARQ

23. Figure 3 Flow diagram for Example 11.3

24. Disadvantage of Stop-and-Wait
•
In stop-and-wait, at any point in time, there is only one frame that is sent
and waiting to be acknowledged.
•
This is not a good use of transmission medium.
•
To improve efficiency, multiple frames should be in transition while
waiting for ACK.
•
Two protocol use the above concept,
–
Go-Back-N ARQ
–
Selective Repeat ARQ