TCP2Transport Layer vs. Network Layer• Provide logical communicationbetween app’ processes• Transport protocols run in end systems • Transport vs. network layer services:– network layer• data transfer between end systems– transport layer• data transfer between processes • relies on, enhances, network layer services applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicallogical end-end transport3Transport Layer Services and Protocolsr Transport servicesm multiplexing/demultiplexingm flow controlm reliable data transferm congestion/rate controlr Transport protocols in the Internetm UDPm TCPInternet Protocol (IP)• Packets may be delivered out‐of‐order• Packets may be lost• Packets may be duplicated 4Transmission Control Protocol (TCP)• Reliable ordered delivery• Implements congestion avoidance and control• Reliability achieved by means of retransmissions if necessary• End‐to‐end semantics– Acknowledgements sent to TCP sender confirm delivery of data received by TCP receiver– Ack for data sent only after data has reached receiver5TCP Basics• Cumulative acknowledgements• An acknowledgement ack’s all contiguously received data• TCP assigns byte sequence numbers• For simplicity, we will assign packet sequence numbers• Also, we use slightly different syntax for acks than normal TCP syntax– In our notation, ack i acknowledges receipt of packets through packet i6Cumulative Acknowledgements• A new cumulative acknowledgement is generated only on receipt of a new in‐sequence packet740 39 3738353341 40 383935 3736343634idata ackiDelayed Acknowledgements• An ack is delayed until– another packet is received, or– delayed ack timer expires (200 ms typical)• Reduces ack traffic840 39 3738353341 40 383935 37New ack not producedon receipt of packet 36,but on receipt of 37Duplicate Acknowledgements• A dupack is generated whenever an out‐of‐order segment arrives at the receiver940 39 3738363442 41 394036 36Dupack(Above example assumes delayed acks)On receipt of 38Duplicate Acknowledgements• Duplicate acks are not delayed• Duplicate acks may be generated when– a packet is lost, or– a packet is delivered out‐of‐order (OOO)1040 39 3837363441 40 373936 36DupackOn receipt of 38Number of dupacks depends on how much OOO a packet is1140 39 3837363441 40 373936 36Dupack42 41 394036 36 38New AckNew AckNew AckNew Ack34New AckDupackNew AckWindow Based Flow Control• Sliding window protocol• Window size minimum of– receiver’s advertised window ‐ determined by available buffer space at the receiver– congestion window ‐ determined by the sender, based on feedback from the network122 3 4 5 6 7 8 9 10 11 131 12Sender’s windowAcks received Not transmittedWindow Based Flow Control132 3 4 5 6 7 8 9 10 11 131 12Sender’s window2 3 4 5 6 7 8 9 10 11 131 12Sender’s windowAck 5Ack Clock• TCP window flow control is “self‐clocking”• New data sent when old data is ack’d• Helps maintain “equilibrium”14Window Based Flow Control• Congestion window size bounds the amount of data that can be sent per round‐trip time• Throughput <= W / RTT15Ideal Window Size• Ideal size = delay * bandwidth– delay‐bandwidth product• What if window size < delay*bw ?– Inefficiency (wasted bandwidth)• What if > delay*bw ?– Queuing at intermediate routers• increased RTT due to queuing delays– Potentially, packet loss16How does TCP detect a packet loss?• Retransmission timeout (RTO)• Duplicate acknowledgements17Detecting Packet Loss Using Retransmission Timeout (RTO)• At any time, TCP sender sets retransmission timer for only one packet• If acknowledgement for the timed packet is not received before timer goes off, the packet is assumed to be lost• RTO dynamically calculated18Retransmission Timeout (RTO) calculation• RTO = mean + 4 mean deviation– Standard deviation σ : σ2= average of (sample –mean)2– Mean deviation δ = average of |sample –mean|– Mean deviation is more conservative: δ >= σ • Large variations in the RTT increase the deviation, leading to larger RTO19Timeout Granularity• RTT is measured as a discrete variable, in multiples of a “tick”• 1 tick = 500 ms in many implementations• smaller tick sizes in more recent implementations (e.g., Solaris)• RTO is at least 2 clock ticks20Exponential Backoff• Double RTO on each timeout21PackettransmittedTime‐out occursbefore ack received,packet retransmittedTimeout interval doubledT1T2 = 2 * T1Fast Retransmission• Timeouts can take too long– how to initiate retransmission sooner?• Fast retransmit22Detecting Packet Loss Using DupacksFast Retransmit Mechanism • Dupacks may be generated due to– packet loss, or– out‐of‐order packet delivery• TCP sender assumes that a packet loss has occurred if it receives three dupacksconsecutively2312 8 7910113 dupacks are also generated if a packetis delivered at least 3 places beyond itsin‐sequence locationFast retransmit useful only if lower layers deliver packets“almost ordered” ‐‐‐‐ otherwise, unnecessary fast retransmitCongestion Avoidance and ControlSlow Start• initially, congestion window size cwnd = 1 MSS (maximum segment size)• slow start phase ends when window size reaches the slow‐start threshold• cwnd grows exponentially with time during slow start– factor of 1.5 per RTT if every other packet ack’d– factor of 2 per RTT if every packet ack’d– Could be less if sender does not always have data to send24Congestion Avoidance• On each new ack,• cwnd increases linearly with time during congestion avoidance– 1/2 MSS per RTT if every other packet ack’d– 1 MSS per RTT if every packet ack’d252602468101214012345678Time (round trips)Congestion Window size(segments)Slow startCongestionavoidanceSlow start thresholdExample assumes that acks are not delayedCongestion Control• On detecting a packet loss, TCP sender assumes that network congestion has occurred• On detecting packet loss, TCP sender drastically reduces the congestion window• Reducing congestion window reduces amount of data that can be sent per RTT– throughput may decrease27Congestion Control ‐‐ Timeout• On a timeout, the congestion window is reduced to the initial value of 1 MSS• The slow