07 -Transport Layer07 Transport LayerTransport Layer3-1rdt3.0: channels with errors andlossNew assumption: Approach: sender waits punderlying channel can also lose packets (data or ACKs)pp“reasonable” amount of time for ACK retransmits if no ACK or ACKs) checksum, seq. #, ACKs, retransmissions will be of help but not enoughretransmits if no ACK received in this time if pkt (or ACK) just delayed (not lost):of help, but not enoughQ: how to deal with loss?(not lost): retransmission will be duplicate, but use of seq. #’s already handles this# s already handles this receiver must specify seq # of pkt being ACKedi td tiTransport Layer3-2 requires countdown timerrdt3.0 in action (alternating-bit tl)protocol)Transport Layer3-3Question 1Quest on Transport Layer3-4rdt3.0 in action (alternating-bit tl)protocol)Transport Layer3-5Performance of rdt3.0fm f . rdt3.0 works, but performance stinks,pf example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet: U sender: utilization – fraction of time sender busy sending1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link1KB pkt every 30 msec 33kB/sec thruput over 1 Gbps link network protocol limits use of physical resources!Transport Layer3-6rdt3.0: stop-and-wait operation.ppfirst packet bit transmitted t = 0sender receiverfirst packet bit transmitted, t = 0last packet bit transmitted, t = L / Rfirst packet bit arrivesRTTfirst packet bit arriveslast packet bit arrives, send ACKACK arrives send nextACK arrives, send next packet, t = RTT + L / RTransport Layer3-7Pipelined protocolsppPipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pktsbeacknowledged pkts range of sequence numbers must be increased buffering at sender and/or receiver Two generic forms of pipelined protocols: go-Back-N, Transport Layer3-8selective repeatPipelining: increased utilizationpgfirst packet bit transmitted, t = 0sender receiverltbitt ittdtL/RRTTlast bit transmitted, t = L / Rfirst packet bit arriveslast packet bit arrives send ACKRTT last packet bit arrives, send ACKACK arrives, send next ktt RTT L/Rlast bit of 2ndpacket arrives, send ACKlast bit of 3rdpacket arrives, send ACKpacket, t = RTT + L / RIncrease utilizationb f t f 3U sender =.02430.008 =0.0008 3 * L / R RTT + L / R =by a factor of 3Transport Layer3-9RTT + L / RGo-Back-N (GBN)GoBackN (GBN)Sender:k-bit seq # in pkt headerk-bit seq # in pkt header “sliding window” of up to N, consecutive unack’ed pkts allowedACK(n): -“cumulative ACK”ACK(n): cumulative ACK may receive duplicate ACKs (see receiver) timer for each in-flight pktti t( )t it kt d ll hi h # kt i i dTransport Layer3-10timeout(n):retransmit pkt n and all higher seq # pkts in windowGBN: ReceiverACK-only: always send ACK for correctly-received pkt with highest inorderseq #with highest in-orderseq # may generate duplicate ACKs need only remember expectedseqnum (the lowest seqnum yet to be received )seqnum yet to be received.) out-of-order pkt: discard (don’t buffer) -> no receiver buffering!R k h h h d #Re-ACK pkt with highest in-order seq #Transport Layer3-11GBN – packet 3 not received at ireceiver Sender Sent packets 0 to 7•Not yet ACKed•Not yet ACKed Can send 8 to 13 ReceiverReceived 0 –2 45 Received 0 –2, 4,5 • For 0 - 2 , send ACK 0 – 2• For 4,5, send ACK 2•Discard 4 and 5 (and •Discard 4 and 5 (and higher) SenderReceive ACK 0-2 and 2 more Receive ACK 02, and 2 more ACK 2s. Timeout for ACK 3 • Resend 3 – 7.Transport Layer3-12GBN –ACK 3 is lostGBN ACK 3 s lost Sender Sent packets 0 to 7• Not yet ACKed Can send 8 to 13 Receiver Received 0 -5• For 0 - 5 , send ACK 0 –5 Sender Receives ACK 0-2, and ACK 4-5A th t 3 l Assumes that 3 was also correctly received at sender (cumulative ACK)Transport Layer3-13GBN –window slides at senderGBN w ndow sl des at senderSender receives Sender receives ACK 0 and ACK 1 Window slides by 2yTransport Layer3-14Question 3Quest on 3Transport Layer3-15Selective Repeat (SR)p() receiver individuallyacknowledges all correctly id kreceived pkts buffers pkts, as needed, for eventual in-order delivery to upper layer sender only resends pkts for which ACK not receivedsender timer for each unACKed pktsender timer for each unACKed pkt sender window N consecutive seq #’s again limits seq #s of sent, unACKed pktsTransport Layer3-16Selective repeat: sender receiver windowsSelective repeat: sender, receiver windowsTransport Layer3-17Selective repeatdata from above :senderf if next available seq # is in window, send pkttimeout(n):0 1 2 3 4 5 6 7 8 9 10 11 12 13timeout(n): resend pkt n, restart timerACK(n) in [sendbase,sendbase+N]: mark pkt n as received if n smallest unACKed pkt, advance window base to advance window base to next unACKed seq # Transport Layer3-18Selective repeatpkt n in [rcvbase, rcvbase+N-1]receiverp send ACK(n) out-of-order: bufferinorder: deliver (also 4 5 6 7 8 9 10 11 1213 0 1 2 3in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pktnext notyetreceived pktpkt n in [rcvbase-N,rcvbase-1] ACK(n) otherwise: ignore Transport Layer3-19Selective repeat:dilemmadilemmaExample: seq #’s: 0, 1, 2, 3 window size=3 receiver sees no difference in two scenarios!scenarios! incorrectly passes duplicate data as new in (a)in (a)Q: what relationship bt # i Transport Layer3-20between seq # size and window
View Full Document