untitled

Chapter 3 Transport Layer A note on the use of these ppt slides: We re making these slides freely available to all (faculty, students, readers). They re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Thanks and enjoy! JFK/KWR All material copyright 1996-2002 J.F Kurose and K.W. Ross, All Rights Reserved Computer Networking: A Top Down Approach Featuring the Internet, 2 nd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2002. Transport Layer 3-1 Chapter 3: : : : UDP: TCP: TCP Transport Layer 3-2 Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP : TCP UDP transport logical end-end transport transport Transport Layer 3-3 Transport Layer 3-4 : : : 12 12 = = = = = : TCP : UDP best-effort IP : transport logical end-end transport transport Transport Layer 3-5 Transport Layer 3-6 1

Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP : transport = socket P3 = process P1 P1 transport : P2 P4 transport link link link host 1 host 2 host 3 Transport Layer 3-7 Transport Layer 3-8 IP IP IP 32 bits TCP/UDP DatagramSocket mysocket1 = new DatagramSocket(99111); DatagramSocket mysocket2 = new DatagramSocket(99222); UDP UDP UDP IP Transport Layer 3-9 Transport Layer 3-10 DatagramSocket serversocket = new DatagramSocket(6428); P3 client IP: A SP: 9157 DP: 6428 SP: 6428 DP: 9157 P3 server IP: C SP: 6428 DP: 5775 SP: 5775 DP: 6428 P1P1 Client IP:B TCP : IP IP 4 TCP HTTP Transport Layer 3-11 Transport Layer 3-12 2

Chapter 3 P3 client IP: A SP: 9157 DP: 80 SP: 80 DP: 9157 P3 P4 server IP: C SP: 80 DP: 5775 SP: 5775 DP: 80 P1P1 Client IP:B 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-13 Transport Layer 3-14 UDP: User Datagram Protocol [RFC 768] UDP:, UDP may be: UDP UDP UDP UDP DNS SNMP UDP Length, in bytes of UDP segment, including header 32 bits UDP Transport Layer 3-15 Transport Layer 3-16 UDP : : : 16 : UDP NO YES Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-17 Transport Layer 3-18 3

rdt_send(): deliver_data(): rdt (rdt: reliable data transfer) Transport Layer 3-19 udt_send(): rdt rdt_rcv(): Transport Layer 3-20 : (rdt) (FSM: finite state machines) : state 1 event actions state 2 Rdt1.0: : call from above packet = make_pkt(data) udt_send(packet) sender call from below rdt_rcv(packet) extract (packet,data) deliver_data(data) receiver Transport Layer 3-21 Transport Layer 3-22 Rdt2.0: UDP : : acknowledgements (ACKs): negative acknowledgements (NAKs): NAK Ack, NAK rdt2.0 (rdt1.0): (ACK, NAK) rdt2.0: FSM snkpkt = make_pkt(data, checksum) call from above isack(rcvpkt) ACK or NAK isnak(rcvpkt) corrupt(rcvpkt) udt_send(nak) call from below notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) Transport Layer 3-23 Transport Layer 3-24 4

rdt2.0: rdt2.0: snkpkt = make_pkt(data, checksum) call from above ACK or NAK isnak(rcvpkt) corrupt(rcvpkt) udt_send(nak) snkpkt = make_pkt(data, checksum) call from above ACK or NAK isnak(rcvpkt) corrupt(rcvpkt) udt_send(nak) isack(rcvpkt) call from below isack(rcvpkt) call from below notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) Transport Layer 3-25 Transport Layer 3-26 rdt2.0 rdt2.1: ACK/NAKs ACK/NAK ACK/NAK ACK/NAK : ACK/NAK stop and wait rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt) ( corrupt(rcvpkt) isnak(rcvpkt) ) sndpkt = make_pkt(0, data, checksum) call 0 from above ACK or NAK 1 ACK or NAK 0 ( corrupt(rcvpkt) isnak(rcvpkt) ) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt) call 1 from above sndpkt = make_pkt(1, data, checksum) Transport Layer 3-27 Transport Layer 3-28 rdt2.1: ACK/NAKs rdt2.1: (corrupt(rcvpkt) sndpkt = make_pkt(nak, chksum) not corrupt(rcvpkt) && has_seq1(rcvpkt) sndpkt = make_pkt(ack, chksum) notcorrupt(rcvpkt) && has_seq0(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack, chksum) (corrupt(rcvpkt) sndpkt = make_pkt(nak, chksum) 0 from below 1 from below notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack, chksum) not corrupt(rcvpkt) && has_seq0(rcvpkt) sndpkt = make_pkt(ack, chksum) Transport Layer 3-29 : (0,1) ACK/NAK : 01 ACK/NAC Transport Layer 3-30 5

rdt2.2: NAK rdt2.2: FSM ACK rdt2.1 NAK ACK ACK ACK NAK Transport Layer 3-31 (corrupt(rcvpkt) has_seq1(rcvpkt)) sndpkt = make_pkt(0, data, checksum) call 0 from above 0 from below ACK 0 sender FSM fragment receiver FSM fragment notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack1, chksum) ( corrupt(rcvpkt) isack(rcvpkt,1) ) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,0) Transport Layer 3-32 rdt3.0: : (data, ACK) ACK : ACK : : ACK ACK ACK : rdt3.0: rdt_rcv(rcvpkt) call 0from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,1) stop_timer timeout start_timer ( corrupt(rcvpkt) isack(rcvpkt,0) ) sndpkt = make_pkt(0, data, checksum) start_timer Wait for ACK1 Wait for ACK0 call 1 from above sndpkt = make_pkt(1, data, checksum) start_timer ( corrupt(rcvpkt) isack(rcvpkt,1) ) timeout start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,0) stop_timer rdt_rcv(rcvpkt) Transport Layer 3-33 Transport Layer 3-34 rdt3.0: rdt3.0: Transport Layer 3-35 Transport Layer 3-36 6

rdt3.0 rdt3.0: stop-and-wait rdt3.0 : 1 Gbps 15 ms, 1KB : first packet bit transmitted, t = 0 last packet bit transmitted, t = L / R sender receiver T transmit = L (packet length in bits) R (transmission rate, bps) = U sender = L / R RTT + L / R =.008 30.008 8kb/pkt 10**9 b/sec = 8 microsec = 0.00027 RTT ACK arrives, send next packet, t = RTT + L / R first packet bit arrives last packet bit arrives, send ACK U sender : 30ms 1KB -> 1 Gbps33kB/sec U sender = L / R RTT + L / R =.008 30.008 = 0.00027 Transport Layer 3-37 Transport Layer 3-38 : ACK : first packet bit transmitted, t = 0 last bit transmitted, t = L / R RTT ACK arrives, send next packet, t = RTT + L / R sender receiver first packet bit arrives last packet bit arrives, send ACK last bit of 2 nd packet arrives, send ACK last bit of 3 rd packet arrives, send ACK! 2: go-back-n, selective repeat Transport Layer 3-39 U sender = 3 * L / R RTT + L / R =.024 30.008 = 0.0008 Transport Layer 3-40 Go-Back-N : k N, ACK ACK(n): n n ACK ACK timeout(n): n Transport Layer 3-41 GBN: base=1 nextseqnum=1 rdt_rcv(rcvpkt) && corrupt(rcvpkt) 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) timeout start_timer Wait udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) udt_send(sndpkt[nextseqnum-1]) notcorrupt(rcvpkt) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer Transport Layer 3-42 7

GBN: FSM default expectedseqnum=1 Wait sndpkt = make_pkt(expectedseqnum,ack,chksum) rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ack,chksum) expectedseqnum++ GBN ACK: ACK ACK Expectedseqnum : -> ACK Transport Layer 3-43 Transport Layer 3-44 : ACK ACK ACK N ACK Transport Layer 3-45 Transport Layer 3-46 : timeout(n): n ACK(n)[sendbase,sendbase+N]: n n ACK ACK n[rcvbase, rcvbase+n-1] ACK(n) : : n[rcvbase-n,rcvbase-1] ACK(n) : Transport Layer 3-47 Transport Layer 3-48 8

: : : 0, 1, 2, 3 = 3 (a) : Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-49 Transport Layer 3-50 socket door TCP: RFCs: 793, 1122, 1323, 2018, 2581 : : TCP writes data TCP send buffer segment reads data TCP receive buffer socket door : MSS: maximum segment size : ( ) : Transport Layer 3-51 TCP URG: () ACK: ACK PSH: () RST, SYN, FIN: ( ) Internet (UDP) 32 bits source port # dest port # sequence number acknowledgement number head not UA P len used R S F Receive window checksum Urg data pnter Options (variable length) data (variable length) (!) Transport Layer 3-52 TCP ACK TCP : ACK: ACK : : TCP RFC User types C host ACKs receipt of echoed C Host A Host B Seq=42, ACK=79, data = C Seq=79, ACK=43, data = C Seq=43, ACK=80 simple telnet scenario host ACKs receipt of C, echoes back C time : TCP RTT RTT : : RTT? SampleRTT: ACK SampleRTT RTT Transport Layer 3-53 Transport Layer 3-54 9

TCP RTT : EstimatedRTT = (1- α)*estimatedrtt + α*samplertt 350 RTT: gaia.cs.umass.edu to fantasia.eurecom.fr : α = 0.125 RTT (milliseconds) 300 250 200 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time (seconnds) SampleRTT Estimated RTT Transport Layer 3-55 Transport Layer 3-56 TCP EstimtedRTT EstimatedRTT -> SampleRTT EstimatedRTT: DevRTT = (1-β)*DevRTT + β* SampleRTT-EstimatedRTT (, β = 0.25) : TimeoutInterval = EstimatedRTT + 4*DevRTT Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-57 Transport Layer 3-58 TCP : : 1 (ACK : TimeOutInterval : Ack: ACK ACK Transport Layer 3-59 NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) { switch(event) event: data received from above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } } /* end of loop forever */ TCP () : SendBase-1: ACK : SendBase-1 = 71; y= 73 73 y > SendBase ACK Transport Layer 3-60 10

TCP: TCP () Host A Host B Host A Host B Host A Host B Seq=92, 8 bytes data timeout SendBase = 100 time Seq=92, 8 bytes data X loss ACK=100 Seq=92, 8 bytes data ACK=100 ACK Sendbase = 100 SendBase = 120 SendBase = 120 Seq=92 timeout Seq=92 timeout time Seq=100, 20 bytes data ACK=100 ACK=120 Seq=92, 8 bytes data ACK=120 Transport Layer 3-61 SendBase = 120 timeout time Seq=92, 8 bytes data Seq=100, 20 bytes data X loss ACK=120 ACK=100 ACK Transport Layer 3-62 TCP ACK [RFC 1122, RFC 2581] ACK ACK ACK 500ms ACK ACK ACK ACK Transport Layer 3-63 ACK ACK ACK ACK : Transport Layer 3-64 : Chapter 3 event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } else { increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) { resend segment with sequence number y } 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP ACK ACK Transport Layer 3-65 Transport Layer 3-66 11

TCP TCP TCP : (TCP ) = RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead] RcvWindow ACK RcvWindow Transport Layer 3-67 Transport Layer 3-68 Chapter 3 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP TCP Recall: TCP TCP : Socket clientsocket = new Socket("hostname","port number"); : Socket connectionsocket = welcomesocket.accept(); : Step 1: TCP SYN Step 2: SYN SYNACK Step 3: SYNACK ACK Transport Layer 3-69 Transport Layer 3-70 TCP () TCP () : client closes socket: clientsocket.close(); Step 1: TCP FIN Step 2: server FINACK FIN close timed wait closed client FIN ACK FIN ACK server close Step 3: client FIN ACK FIN ACK Step 4: serverack : FIN closing timed wait closed client FIN ACK FIN ACK server closing closed Transport Layer 3-71 Transport Layer 3-72 12

TCP () Chapter 3 TCP client lifecycle TCP server lifecycle 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-73 Transport Layer 3-74 / : : : () () Host B Host A λ in : original data unlimited shared output link buffers λ out Transport Layer 3-75 Transport Layer 3-76 / Host A λ in : original data λ' in : original data, plus retransmitted data λ out / λ = λ (goodput) in out λ > λ in out λ out λ in Host B finite shared output link buffers Transport Layer 3-77 : λ in goodput Transport Layer 3-78 13

/ / : λ λ in in / H o s t A λ o u t Host A λ in : original data λ' in : original data, plus retransmitted data λ out H o s t B finite shared output link buffers Host B : Transport Layer 3-79 Transport Layer 3-80 : ATM ABR : : TCP : (SNA, DECbit, TCP/IP ECN, ATM) ABR: available bit rate: elastic service (RM: resource management): RM ( ) NI bit: CI bit: RM Transport Layer 3-81 Transport Layer 3-82 : ATM ABR Chapter 3 RM(ER: explicit rate) ER EFCI: 1 RMEFCI RMCI1 Transport Layer 3-83 3.1 3.2 3.3 : UDP 3.4 3.5 : TCP 3.6 3.7 TCP Transport Layer 3-84 14

TCP ( ) : LastByteSent-LastByteAcked CongWin rate = CongWin RTT Bytes/sec CongWin? = ACK TCP (CongWin) : AIMD Transport Layer 3-85 TCP AIMD : CongWin 24 Kbytes 16 Kbytes 8 Kbytes congestion window Long-lived TCP connection : RTT CongWin 1 MSS time Transport Layer 3-86 TCP TCP () CongWin = 1 MSS : MSS = 500 bytes & RTT = 200 msec = 20 kbps MSS/RTT RTT CongWin ACK CongWin : RTT Host A Host B one segment two segments four segments time Transport Layer 3-87 Transport Layer 3-88 ACK CongWin CongWin 1 MSS window : ACK ACK () : : CongWin : congestion window size (segments) CongWin 14 12 threshold 10 8 6 4 2 TCP 0 Tahoe TCP Reno 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Transmission round Transport Layer 3-89 Transport Layer 3-90 15

: TCP CongWin Threshold CongWin Threshold TCP : KTCP R R/K TCP connection 1 ACKThreshold CongWin/2 CongWin CongWin/2 CongWin 1 MSS TCP connection 2 bottleneck router capacity R Transport Layer 3-91 Transport Layer 3-92 TCP : R Connection 2 throughput Connection 1 throughput : : : : R Transport Layer 3-93 () UDP TCP UDP : : TCP friendly TCP Web : R 9 1TCP R/10 9 TCP R/2 Transport Layer 3-94 Q: Web : TCP : R S: MSS (bits) O: (bits) () : : W (1) : WS/R > RTT + S/R: ACK = 2RTT + O/R Transport Layer 3-95 Transport Layer 3-96 16

(2) : WS/R < RTT + S/R: ACK = 2RTT + O/R + (K-1)[S/R + RTT - WS/R] TCP : (1) : O S P S Latency = 2RTT + + P RTT (2 1) R + R R P TCP P = min{ Q, K 1} - Q - K Transport Layer 3-97 Transport Layer 3-98 TCP : (2) : 2 RTT O/R : P = min{k-1,q} : O/S = 15 K = 4 Q = 2 P = min{k-1,q} = 2 P=2 initiate TCP connection request object object delivered RTT time at client first window = S/R second window = 2S/R third window = 4S/R fourth window = 8S/R complete transmission time at server Transport Layer 3-99 TCP (3) S + RTT = ACK R k S 2 1 = k R S k S 2 1 + RTT = k R R O delay = + 2RTT + R + P p= 1 idletime P O S k 1 S = + 2RTT + [ + RTT 2 ] R k = 1 R R O S P S = + 2RTT + P[ RTT + ] (2 1) R R R p initiate TCP connection request object object delivered RTT time at client time at server first window = S/R second window = 2S/R third window = 4S/R fourth window = 8S/R complete transmission Transport Layer 3-100 TCP Delay Modeling (4) K = K 0 1 k K = min{ k : 2 S + 2 S + L+ 2 0 1 k = min{ k : 2 + 2 + L+ 2 1 k O = min{ k : 2 1 } S O = min{ k : k log2( + 1)} S O = log2( + 1) S 1 S O} O / S} Q Transport Layer 3-101 HTTP Web : 1 HTML ( O bits) M ( O bits) HTTP: M+1 TCP = (M+1)O/R + (M+1)2RTT + HTTP: 2 RTT HTML 1 RTT M = (M+1)O/R + 3RTT + HTTP X M/X 1 TCP M/X = (M+1)O/R + (M/X + 1)2RTT + Transport Layer 3-102 17

HTTP () RTT = 100 msec, O = 5 Kbytes, M=10 and X=5 20 18 16 14 12 10 8 6 4 2 0 28 Kbps 100 Kbps 1 Mbps 10 Mbps non-persistent persistent parallel nonpersistent Transport Layer 3-103 HTTP () RTT =1 sec, O = 5 Kbytes, M=10 and X=5 70 60 50 40 30 20 10 0 28 Kbps 100 Kbps 1 Mbps 10 Mbps non-persistent persistent parallel nonpersistent RTTTCP Transport Layer 3-104 Chapter 3: : UDP TCP Next: Transport Layer 3-105 18