CS 118 Spring 2014Chapter 3 outlineRdt1.0: reliable transfer over a reliable channelrdt2.0: channel has errors - perfect ACK/NAKrdt2.1: sender, handles garbled ACK/NAKsrdt2.2: NAK free versionrdt3.0 sender- channel has pkt lossesPerformance of rdt3.0rdt3.0: stop-and-wait operationPipelined protocolsPipelining: increased utilizationGo-Back-NGBN: sender extended FSMGBN: receiver extended FSMGBN in actionSelective RepeatSelective repeat: sender, receiver windowsSelective repeat in actionSelective repeat: dilemmaTransport Layer 3-1CS 118 Spring 2014Chpt 3 - Section 3BTransport Layer 3-2Chapter 3 outline3.1 Transport-layer services3.2 Multiplexing and demultiplexing3.3 Connectionless transport: UDP3.4 Principles of reliable data transfer3.5 Connection-oriented transport: TCPsegment structurereliable data transferflow controlconnection management3.6 Principles of congestion control3.7 TCP congestion controlTransport Layer 3-3Rdt1.0: reliable transfer over a reliable channelunderlying channel perfectly reliableno bit errorsno loss of packetsseparate FSMs for sender, receiver:sender sends data into underlying channelreceiver read data from underlying channelWait for call from abovepacket = make_pkt(data)udt_send(packet)rdt_send(data)extract (packet,data)deliver_data(data)Wait for call from belowrdt_rcv(packet)senderreceiverTransport Layer 3-4rdt2.0: channel has errors - perfect ACK/NAKWait for call from abovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)rdt_rcv(rcvpkt) && isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) && isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) && corrupt(rcvpkt)Wait for ACK or NAKWait for call from belowsenderreceiverrdt_send(data)Transport Layer 3-5rdt2.1: sender, handles garbled ACK/NAKsWait for call 0 from abovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)Wait for ACK or NAK 0udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isNAK(rcvpkt) )sndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)rdt_send(data)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isNAK(rcvpkt) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) Wait for call 1 from aboveWait for ACK or NAK 1Transport Layer 3-6rdt2.2: NAK free versionWait for call 0 from abovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) Wait for ACK0sender FSMfragmentWait for 0 from belowrdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK1, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt))udt_send(sndpkt)receiver FSMfragmentTransport Layer 3-7rdt3.0 sender- channel has pkt lossessndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)Wait for ACK0rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,1) )Wait for call 1 from abovesndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,0) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) stop_timerstop_timerudt_send(sndpkt)start_timertimeoutudt_send(sndpkt)start_timertimeoutrdt_rcv(rcvpkt)Wait for call 0from aboveWait for ACK1rdt_rcv(rcvpkt)Transport Layer 3-8Performance of rdt3.0rdt3.0 works, but performance stinksexample: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:Ttransmit=8kb/pkt10**9 b/sec= 8 microsecU sender: utilization – fraction of time sender busy sendingL (packet length in bits)R (transmission rate, bps)=1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps linknetwork protocol limits use of physical resources!Transport Layer 3-9rdt3.0: stop-and-wait operationfirst packet bit transmitted, t = 0sender receiverRTT last packet bit transmitted, t = L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send next packet, t = RTT + L / RTransport Layer 3-10Pipelined protocolsPipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pktsrange of sequence numbers must be increasedbuffering at sender and/or receiverTwo generic forms of pipelined protocols: go-Back-N, selective repeatTransport Layer 3-11Pipelining: increased utilizationfirst packet bit transmitted, t = 0sender receiverRTT last bit transmitted, t = L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send next packet, t = RTT + L / Rlast bit of 2nd packet arrives, send ACKlast bit of 3rd packet arrives, send ACKIncrease utilizationby a factor of 3!Transport Layer 3-12Go-Back-NSender:k-bit seq # in pkt header“window” of up to N, consecutive unack’ed pkts allowedACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”may receive duplicate ACKs (see receiver)timer for each in-flight pkttimeout(n): retransmit pkt n and all higher seq # pkts in windowTransport Layer 3-13GBN: sender extended FSMWaitstart_timerudt_send(sndpkt[base])udt_send(sndpkt[base+1])…udt_send(sndpkt[nextseqnum-1])timeoutrdt_send(data) if (nextseqnum < base+N) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ }else refuse_data(data)base = getacknum(rcvpkt)+1If (base == nextseqnum) stop_timer else start_timerrdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base=1nextseqnum=1rdt_rcv(rcvpkt) && corrupt(rcvpkt) Transport Layer 3-14GBN: receiver extended FSMACK-only: always send ACK for correctly-received pkt with highest in-order seq #may generate duplicate ACKsneed only remember expectedseqnumout-of-order pkt: discard (don’t buffer) -> no receiver buffering!Re-ACK pkt with highest in-order seq #Waitudt_send(sndpkt)defaultrdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(expectedseqnum,ACK,chksum)udt_send(sndpkt)expectedseqnum++expectedseqnum=1sndpkt = make_pkt(expectedseqnum,ACK,chksum)Transport Layer 3-15GBN inactionTransport Layer 3-16Selective Repeatreceiver individually acknowledges all correctly received pktsbuffers pkts, as needed, for eventual in-order
View Full Document
Unlocking...