数据教程课件chapter8flowcontrol

1、1chapter eightflow control2flow controlerror detection and error correction are not enoughreceiver drops a packet when errors detectedreceiver cant correct errors in some packetsreceiver never receives a packetsolution: retransmit lost or corrupt packetsalso called arq (automatic-repeat-request) pro

2、tocolsuseful for communicating non-delay-sensitive data, e.g. web pages, files, email, even playback videocan incur too much delay for interactive audio/videoflow control (2)how does sender know a packet has been received properly?analogy: send a package by mail. how do i know it got there? certifie

3、d mail sends back a receipt. in some protocols, acknowledgements are sent by receiver back to sender confirming receipt of a packetwhen an acknowledgment doesnt arrive, then retransmitsenderreceiver1011000got it!flow control (3)the communication channel canlose packets (link layer and network layer)

4、delay packets (network layers)reorder packets (network layers)both the packet and the ack can be lostsenderreceiver1011000got it!flow control (4)if the packet is lost, at what point does the protocol retransmit? after a timeoutif the ack is lost, at what point does the protocol retransmit?after the

5、same timeoutsenderreceiver1011000got it!flow control (5)how does receiver know that sender got its acknowledgment?sender increments sequence number to #6 when acknowledgement #5 arrives. when receiver sees packet #6, it knows acknowledgement #5 made itsequence #s are also useful to send many packets

6、 at oncesenderreceiver0100110#6got #6flow control(6) to detect when a packet needs to be retransmitted, arq protocols must use both:acknowledgements, andtimeouts, sequence numbers:sender labels packets with themfor certain protocols, a sender can infer correct reception of the acknowledgement for a

7、packet with a lower sequence numberclickclicknextacks and nakstypes of acknowledgmentsacks positive acknowledgements = “ive received these packets”cumulativeselectivenaks negative acknowledgements = “i have not received these packets”acks are more prevalent than nakssenderreceiver0100110#6got #6got

8、roundtrip time, “” means “much greater than” lets approximate roundtrip time rtt = 2*( max propagation delay)example: if satellite link has prop. delay of 120 ms each way, then rtt = 240 ms. if timeout=1 min 240 ms, then send too slowly.if timeout is too short, then retransmit unnecessarily“too shor

9、t” means timeout roundtrip timeexample: if timeout = 1 ms rttsenderreceiverframeacknext frameacktimeoutperiodrtttimetimestop-and-wait protocol (2)if a timeout occurs before receiving an ack, the sender retransmits the frame.timesenderreceiverframeframeacktimeoutperiodorstop-and-wait protocol (3)if a

10、 timeout occurs before receiving an ack, the sender retransmits the frame.timesenderreceiverframeframeacktimeoutperiodstop-and-wait protocol (4)want timeout = rtt to avoid spurious retransmissions of a frame/packettimesenderreceiverframeframeackrttackunnecessary retransmissiontimeoutstop-and-wait pr

11、otocol (5)label each packet and ack with the proper sequence # to avoid confusion at receiver and sendersenderreceiverframe #1ack #1frame #2ack #2timeoutperiodrtttimetimeprotocol efficiency channel utiliation: the percentage of time the channel is transferring data frames (i.e. not including ack fra

12、mes) effective data rate: the actual number of data bits (as opposed to the raw bit rate) sent per unit of time parameters: r - transmission rate s - signal speed d - distance between sender and receiver t - time to create one frame f - number of bits in a data frame n - number of data bits in a fra

13、me a - number of bits in an acknowledgment time to send a frame to the receiver is t + f/r + d/s time to send an acknowledgment to the sender is t + a/r + d/sprotocol efficiency (cont.) for unrestricted and stop-and-wait protocols the elapsed time between sending two consecutive frames unrestricted:

14、 t+f/r stop and wait: (t+f/r+d/s) + (t+a/r+d/s) = 2(t+d/s) + (f+a)/r the channel utilization unrestricted: 100*(f/r)/(t+f/r) stop and wait:100*(f/r+d/s)/(2(t+d/s)+(f+a)/r) effective data rate unrestricted: n/(t+f/r) stop and wait :n/(2(t+d/s)+(f+a)/r)example assumptions: r - 10 mbps or 10 bits per s

15、ec s - 200 meters per sec d - 200 meters t - 1 sec f - 200 bits n - 160 bits a - 40 bitsexample (cont.) the channel utilization unrestricted: 100*(f/r)/(t+f/r) = 95% stop and wait: 100*(f/r+d/s)/(2(t+d/s)+(f+a)/r) = 75% effective data rate unrestricted: n/(t+f/r) = 7.6 mbps stop and wait n/(2(t+d/s)

16、+(f+a)/r) = 5.7 mbpsproblem with stop-and-waitonly one outstanding packet at a time = waste of link bandwidthexample: 1.5 mbps link with rtt 45 ms = a delay*bandwidth product = 1.5mbps*45ms=67.5 kb 8 kb. “pipe size” if frame size = 1 kb, then use only 1/8 of bandwidthsenderreceiverframe #1ack #1fram

17、e #2ack #2rtttimetime30designing efficient flow control protocolsalready seen one way to improve efficiency: choose timeout wiselyanother way to improve efficiency: “keep the pipe full” with new data packets and necessary retransmissionsstop-and-waitgo-back-nselective repeat protocol (srp)“keep the

18、pipe full”during one rtt, send n packetsexample: 1.5 mbps link with rtt 45 ms = a delay*bandwidth product = 67.5 kb 8 kb. “pipe size”if frame size = 1 kb, and n=3, then can have 3 outstanding packets, 3/8 of bw, and triple bandwidth utilization!senderreceiverrtttimetimeframe #1frame #2frame #3ack #3

19、ack #2ack #1go-back-n sliding window protocolmaintain a sliding window at both sender and receiver of unacknowledged packetssend window size (sws)at sender: lar (last ack received), lfs (last frame sent)sliding window:when ack #(lar+1) arrives, slide lar and lfs to rightlfs lar = sws retransmit enti

20、re windowlarlfsswsgo-back-n sliding window protocol (2)at receiver:maintain a receive window size (rws)at receiver: laf (largest acceptable frame), lfr (last frame received)sliding window:when frame arrives, keep it if its within windowif frame #(lfr+1) arrives, then slide window to right (increment

21、 lfr and laf)send back cumulative ack = lfr+1, laf lfr inefficientsome packets are retransmitted even though theyve already arrived at receiversolution: acknowledge each packet individually, or selectively, rather than cumulativelyselective repeat protocol (srp)selective acks sent by receiver identi

22、fy specifically which frame(s) have been received correctly in our example, the ack would contain info that only packets #7 and #10 have already arrived at receiversender only retransmits packets #6, #8,#9 and #11, and avoids resending #7 and #10“sliding” window in srp actually becomes much more complicat