Computer Networking: A Top-Down Approach Chapter 3 PDF

Chapter 3 Transport Layer A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your nee...

Chapter 3 Transport Layer A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and 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) that you mention their source (after all, we’d like people to use our book!) Computer  If you post any slides 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. Networking: A Top- For a revision history, see the slide note for this page. Down Approach Thanks and enjoy! JFK/KWR 8th edition Jim Kurose, Keith Ross All material copyright 1996-2023 Pearson, 2020 J.F Kurose and K.W. Ross, All Rights Reserved Transport Layer: 3-1 Transport layer: overview Our goal:  understand  learn about Internet principles behind transport layer protocols: transport layer UDP: connectionless services: transport multiplexing, TCP: connection-oriented demultiplexing reliable transport reliable data transfer TCP congestion control flow control congestion control Transport Layer: 3-2 Transport layer: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP  Principles of congestion control  TCP congestion control  Evolution of transport-layer functionality Transport Layer: 3-3 Transport services and protocols application transport  provide logical mobile network network data link physical communication between national or global ISP l og application processes ica  running transport on different hosts le protocols actions in end nd systems: -en sender: breaks application messages dt local or regional ra n into segments, passes to network ISP sp layer home network content ort receiver: reassembles segments into provider network messages, passes to application layer datacenter application network transport network  two transport protocols data link physical available to Internet enterprise applications network TCP, UDP Transport Layer: 3-4 Transport vs. network layer services and protocols household analogy: 12 kids in Ann’s house sending letters to 12 kids in Bill’s house:  hosts = houses  processes = kids  app messages = letters in envelopes  transport protocol = Ann and Bill who demux to in-house siblings  network-layer protocol = postal service Transport Layer: 3-5 Transport vs. network layer services and protocols household analogy:  transport layer: 12 kids in Ann’s house sending communication letters to 12 kids in Bill’s between processes house: relies on, enhances,  hosts = houses  processes = kids network layer services  app messages = letters in envelopes  network layer:  transport protocol = Ann and communication Bill who demux to in-house between hosts siblings  network-layer protocol = postal service Transport Layer: 3-6 Transport Layer Actions Sender: application  is passed an app. msg application application-layer  determines message segment TT hh app. msg transport transport header fields values  creates segment network network (IP)  passes segment to IP (IP) link link physical physical Transport Layer: 3-7 Transport Layer Actions Receiver: application  receives segment application  from IP header values checks app. transport  extracts application- transport msg layer message network (IP)  demultiplexes network message up to (IP) link link application via socket physical physical Th app. msg Transport Layer: 3-8 Two principal Internet transport protocols application transport  TCP: Transmission Control mobile network network data link physical Protocol national or global ISP l og reliable, in-order delivery ica le congestion control nd flow control -en dt local or connection setup regional ra n  UDP: User Datagram Protocol ISP sp home network content unreliable, unordered delivery ort provider network no-frills extension of “best-effort” IP datacenter application network transport network  services not available: data link physical delay guarantees enterprise bandwidth guarantees network Transport Layer: 3-9 Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP  Principles of congestion control  TCP congestion control  Evolution of transport-layer functionality Transport Layer: 3-10 Multiplexing/demultiplexing multiplexing as demultiplexing as receiver: sender: handle data from multiple use header info to deliver sockets, add transport received segments to correct header (later used for socket demultiplexing) application application P1 P2 application socket P3 transport P4 process transport network transport network link network link physical link physical physical Transport Layer: 3-11  HTTP server client application application HTTP msg H HTTP transport t msg Hnetwork nHt HTTP transport transport msg HnH t HTTP network link network msg physical link link physical physical HnHt HTTP msg Transport Layer: 3-12  Q: how did transport layer know to deliver message to Firefox browser process rather then Netflix process or Skype process? client application application HTTP HTTP msg H t HTTP transport msg msg transport network transport network link network link physical link physical physical Transport Layer: 3-13  ? de-multiplexing  application ? transport de-multiplexing Demultiplexing multiplexing  application transport multiplexing Multiplexing How demultiplexing works  host receives IP 32 bits datagrams source port # dest port # each datagram has source IP address, destination IP other header fields address each datagram carries one application transport-layer segment data each segment has source, (payload) destination port number  host uses IP addresses & TCP/UDP segment format port numbers to direct segment to appropriate socket Transport Layer: 3-22 Connectionless demultiplexing Recall: when receiving host  when creating socket, receives UDP segment: must specify host-local checks destination port port #: # in segment DatagramSocket mySocket1 new DatagramSocket(12534); = directs UDP segment to socket with that port #  when creating datagram to send into IP/UDP datagrams with UDP socket, must same dest. port #, but specify different source IP destination IP address addresses and/or source destination port # port numbers will be directed to same socket at Transport Layer: 3-23 Connectionless demultiplexing: an example mySocket = socket(AF_INET,SOCK_DGRAM) mySocket.bind(myaddr,6428); mySocket = mySocket = socket(AF_INET,SOCK_STREAM) socket(AF_INET,SOCK_STREAM) mySocket.bind(myaddr,9157); mySocket.bind(myaddr,5775); application application P1 application P3 P4 transport transport transport network network link network link physical link physical physical B D source port: 6428 source port: ? dest port: 9157 dest port: ? A C source port: 9157 source port: ? dest port: 6428 dest port: ? Connection-oriented demultiplexing  TCP socket  server may support identified by 4- many simultaneous tuple: TCP sockets: source IP address each socket identified source port number by its own 4-tuple dest IP address each socket associated dest port number  demux: receiver with a different connecting client uses all four values (4-tuple) to direct segment to appropriate socket Transport Layer: 3-25  Connection-oriented demultiplexing: example application application P4 P5 P6 application P1 P2 P3 transport transport transport network network link network link physical link physical server: physical IP address B host: IP source IP,port: B,80 host: IP address dest IP,port: A,9157 source IP,port: C,5775 address A dest IP,port: B,80 C source IP,port: A,9157 dest IP, port: B,80 source IP,port: C,9157 dest IP,port: B,80 Three segments, all destined to IP address: B, dest port: 80 are demultiplexed to different sockets Transport Layer: 3-26 Summary  Multiplexing, demultiplexing: based on segment, datagram header field values  UDP: demultiplexing using destination port number (only)  TCP: demultiplexing using 4-tuple: source and destination IP addresses, and port numbers  Multiplexing/demultiplexing happen at all layers Transport Layer: 3-27 Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP  Principles of congestion control  TCP congestion control  Evolution of transport-layer functionality Transport Layer: 3-28 UDP: User Datagram Protocol  “no frills,” “bare bones” Why is there a Internet transport protocol UDP?  no connection  “best effort” service, UDP establishment (which segments may be: can add RTT delay) lost  simple: no connection state at sender, delivered out-of-order to receiver app  small header size  connectionless: no handshaking between  no congestion control UDP sender, receiver  UDP can blast away as each UDP segment fast as desired! handled independently of  can function in the face others of congestion Transport Layer: 3-29 UDP: User Datagram Protocol  UDP use:  streaming multimedia apps (loss tolerant, rate sensitive)  DNS  SNMP  HTTP/3  if reliable transfer needed over UDP (e.g., HTTP/3):  add needed reliability at application layer  add congestion control at application layer Transport Layer: 3-30 UDP: User Datagram Protocol [RFC 768] Transport Layer: 3-31 UDP: Transport Layer Actions SNMP client SNMP server application application transport transport (UDP) (UDP) network (IP) network (IP) link link physical physical Transport Layer: 3-32 UDP: Transport Layer Actions SNMP client UDP sender actions: SNMP server application  is passed an SNMP application application-layer msg transport  determines message UDP transport UDP UDPhh SNMP (UDP) segment header (UDP) msg  creates fields values UDP segment network network (IP)  passes segment to IP (IP) link link physical physical Transport Layer: 3-33 UDP: Transport Layer Actions SNMP client UDP receiver SNMP server application  receives segment actions: application  checks from IP UDP transport transport SNMP checksum header (UDP)  value extracts application- (UDP) msg UDPh SNMP(IP) network layer message network msg  demultiplexes (IP) link message up to link physical application via socket physical Transport Layer: 3-34 UDP segment header 32 bits source port # dest port # length checksum application length, in bytes of data UDP segment, (payload) including header data to/from UDP segment format application layer Transport Layer: 3-35 UDP checksum Goal: detect errors (i.e., flipped bits) in transmitted segment 1st number 2nd number sum Transmitted: 5 6 11 Received: 4 6 11 receiver-computed checksum = sender-computed checksum (as received) Transport Layer: 3-36 Internet checksum Goal: detect errors (i.e., flipped bits) in transmitted segment sender: receiver:  treat contents of UDP  compute checksum of segment (including UDP received segment header fields and IP addresses) as sequence  check if computed checksum of 16-bit integers equals checksum field value:  checksum: addition not equal - error detected (one’s complement sum) equal - no error detected. But of segment content maybe errors nonetheless?  checksum value put More later …. into UDP checksum field Transport Layer: 3-37 Internet checksum: an example example: add two 16-bit integers 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 sum 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 checksum 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 Note: when adding numbers, a carryout from the most significant bit needs to be added to the result * Check out the online interactive exercises for more examples: h ttp://gaia.cs.umass.edu/kurose_ross/interactive/ Transport Layer: 3-38 Internet checksum: weak protection! example: add two 16-bit integers 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 Even though numbers have sum 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 changed (bit flips), no checksum 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 change in checksum! Transport Layer: 3-39 Summary: UDP  “no frills” protocol: segments may be lost, delivered out of order best effort service: “send and hope for the best”  UDP has its plusses: no setup/handshaking needed (no RTT incurred) can function when network service is compromised helps with reliability (checksum)  build additional functionality on top of UDP in application layer (e.g., HTTP/3) Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP  Principles of congestion control  TCP congestion control  Evolution of transport-layer functionality Transport Layer: 3-41  Principles of reliable data transfer sending receivin process g application dat process dat transport a a reliable channel reliable service abstraction Transport Layer: 3-42  Principles of reliable data transfer sending receivin sending receivin process g process g application dat process dat application dat process dat transport a a transport a a reliable channel sender-side of receiver-side reliable service reliable data of reliable transfer data transfer abstraction protocol protocol transport network unreliable channel reliable service implementation Transport Layer: 3-43 Principles of reliable data transfer sending receivin process g application dat process dat transport a a sender-side of receiver-side Complexity of reliable reliable data transfer of reliable data transfer data transfer protocol protocol protocol will depend (strongly) on transport network characteristics of unreliable channel unreliable channel (lose, reliable service corrupt, reorder data?) implementation Transport Layer: 3-44 Principles of reliable data transfer sending receivin process g application dat process dat transport a a sender-side of receiver-side reliable data of reliable Sender, receiver do not transfer data transfer know the “state” of each protocol protocol other, e.g., was a transport network message received? unreliable channel  unless communicated reliable service via a message implementation Transport Layer: 3-45  Reliable data transfer protocol (rdt): interfaces rdt_send(): called from deliver_data(): called above, (e.g., by app.). by rdt to deliver data Passed data to deliver to upper layer to receiver upper layer sending receivin process g rdt_send() dat process dat a a deliver_data() sender-side data receiver-side implementation implementation of rdt reliable packet of rdt reliable data transfer data transfer protocol protocol udt_send() Heade dat Heade dat rdt_rcv() r a r a unreliable channel udt_send(): called by rdt_rcv(): called when rdt Bi-directional communication packet arrives on to transfer packet over over unreliable channel receiver side of channel unreliable channel to Transport Layer: 3-46 Reliable data transfer: getting started We will:  incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)  consider only unidirectional data transfer but control info will flow in both directions!  use finite state machines (FSM) to specify sender, receiver event causing state transition actions taken on state transition state: when in this “state” next state stat state uniquely e event determined by 2 1 actions next event Transport Layer: 3-47 rdt1.0: reliable transfer over a reliable channel  underlying channel perfectly reliable no bit errors no loss of packets  separate FSMs for sender, receiver: sender sends data into underlying channel receiver reads data from underlying channel Wait for rdt_send(data) Wait for rdt_rcv(packet) call from receiver sender above packet = make_pkt(data) call from extract (packet,data) udt_send(packet) below deliver_data(data) Transport Layer: 3-48  rdt2.0: channel with bit errors  underlying channel may flip bits in packet checksum (e.g., Internet checksum) to detect bit errors  the question: how to recover from errors? How do humans recover from “errors” during conversation Transport Layer: 3-49 rdt2.0: channel with bit errors  underlying channel may flip bits in packet checksum to detect bit errors  the question: how to recover from errors? acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors sender retransmits pkt on receipt of NAK stop and sender wait sends one packet, then waits for receiver response Transport Layer: 3-50 rdt2.0: FSM specifications rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && Wait for Wait for isNAK(rcvpkt) sender call from ACK or udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) above NAK udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for L call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-51 rdt2.0: FSM specification rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && Wait for Wait for isNAK(rcvpkt) sender call from ACK or udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) above NAK udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for L call from receiver below Note: “state” of receiver (did the rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) receiver get my message correctly?) isn’t extract(rcvpkt,data) known to sender unless somehow deliver_data(data) communicated from receiver to sender udt_send(ACK)  that’s why we need a protocol! Transport Layer: 3-52 rdt2.0: operation with no errors rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && Wait for Wait for isNAK(rcvpkt) sender call from ACK or udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) above NAK udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for L call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-53 rdt2.0: corrupted packet scenario rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && Wait for Wait for isNAK(rcvpkt) sender call from ACK or udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) above NAK udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for L call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-54 rdt2.0 has a fatal flaw! what happens if ACK/NAK handling duplicates: corrupted?  sender retransmits current  sender doesn’t know what pkt if ACK/NAK corrupted happened at receiver!  sender adds sequence  can’t just retransmit: number to each pkt possible duplicate  receiver discards (doesn’t deliver up) duplicate pkt stop and wait sender sends one packet, then waits for receiver response Transport Layer: 3-55 rdt2.1: sender, handling garbled ACK/NAKs rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || Wait for Wait for isNAK(rcvpkt) ) call 0 from ACK or NAK 0 udt_send(sndpkt) above rdt_rcv(rcvpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && && notcorrupt(rcvpkt) isACK(rcvpkt) && isACK(rcvpkt) L L Wait for Wait for ACK or call 1 from rdt_rcv(rcvpkt) NAK 1 above && (corrupt(rcvpkt) || isNAK(rcvpkt) ) rdt_send(data) udt_send(sndpkt) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) Transport Layer: 3-56 rdt2.1: receiver, handling garbled ACK/NAKs rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && rdt_rcv(rcvpkt) && (corrupt(rcvpkt) (corrupt(rcvpkt) sndpkt = make_pkt(NAK, chksum) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) udt_send(sndpkt) Wait for Wait for rdt_rcv(rcvpkt) && 0 from 1 from rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && below below not corrupt(rcvpkt) && has_seq1(rcvpkt) has_seq0(rcvpkt) sndpkt = make_pkt(ACK, chksum) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) Transport Layer: 3-57 rdt2.1: discussion sender: receiver:  seq # added to pkt  must check if received  two seq. #s (0,1) will packet is duplicate state indicates whether 0 suffice. Why? or 1 is expected pkt seq  must check if received # ACK/NAK corrupted  note: receiver can not  twice as many states know if its last ACK/NAK state must “remember” received OK at sender whether “expected” pkt should have seq # of 0 or 1 Transport Layer: 3-58  rdt2.2: a NAK-free protocol  same functionality as rdt2.1, using ACKs only  instead of NAK, receiver sends ACK for last pkt received OK receiver must explicitly include seq # of pkt being ACKed  duplicate ACK at sender results in same action as As we NAK: retransmit will see, current TCP uses pkt this approach to be NAK-free Transport Layer: 3-59 rdt2.2: sender, receiver fragments rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || Wait for Wait for ACK isACK(rcvpkt,1) ) call 0 from above 0 udt_send(sndpkt) sender FSM fragment rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) rdt_rcv(rcvpkt) && && isACK(rcvpkt,0) (corrupt(rcvpkt) || L has_seq1(rcvpkt)) Wait for receiver FSM 0 from udt_send(sndpkt) below fragment rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt) Transport Layer: 3-60 rdt3.0: channels with errors and loss New channel assumption: underlying channel can also lose packets (data, ACKs) checksum, sequence #s, ACKs, retransmissions will be of help … but not quite enough Q: How do humans handle lost sender-to-receiver words in conversation? Transport Layer: 3-61 rdt3.0: channels with errors and loss Approach: sender waits “reasonable” amount of time for ACK  retransmits if no ACK received in this time  if pkt (or ACK) just delayed (not lost): retransmission will be duplicate, but seq #s already handles this!  use countdown timer to interrupt after “reasonable” receiver must specify seq # of packet being ACKed amount of time timeout Transport Layer: 3-62 rdt3.0 sender rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer Wait for Wait call 0 from for above ACK0 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt,1) && notcorrupt(rcvpkt) stop_timer && isACK(rcvpkt,0) stop_timer Wait Wait for for call 1 from ACK1 above rdt_send(data) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer Transport Layer: 3-63 rdt3.0 sender rdt_send(data) rdt_rcv(rcvpkt) && sndpkt = make_pkt(0, data, checksum) ( corrupt(rcvpkt) || udt_send(sndpkt) isACK(rcvpkt,1) ) rdt_rcv(rcvpkt) start_timer L L Wait for Wait for timeout call 0 from ACK0 udt_send(sndpkt) above start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt,1) && notcorrupt(rcvpkt) stop_timer && isACK(rcvpkt,0) stop_timer Wait Wait for timeout for call 1 from udt_send(sndpkt) ACK1 above start_timer rdt_rcv(rcvpkt) rdt_send(data) L rdt_rcv(rcvpkt) && sndpkt = make_pkt(1, data, checksum) ( corrupt(rcvpkt) || udt_send(sndpkt) isACK(rcvpkt,0) ) start_timer L Transport Layer: 3-64 rdt3.0 in action sender receiver sender receiver send pkt0 pkt0 send pkt0 pkt0 rcv pkt0 rcv pkt0 ack0 send ack0 ack0 send ack0 rcv ack0 rcv ack0 send pkt1 pkt1 send pkt1 pkt1 rcv pkt1 X loss ack1 send ack1 rcv ack1 send pkt0 pkt0 rcv pkt0 timeout ack0 send ack0 resend pkt1 pkt1 rcv pkt1 ack1 send ack1 rcv ack1 send pkt0 pkt0 (a) no loss rcv pkt0 ack0 send ack0 (b) packet loss Transport Layer: 3-65 rdt3.0 in action sender receiver sender receiver send pkt0 pkt0 rcv pkt0 send pkt0 pkt0 send ack0 ack0 rcv pkt0 rcv ack0 ack0 send ack0 send pkt1 pkt1 rcv ack0 rcv pkt1 send pkt1 pkt1 send ack1 rcv pkt1 ack1 ack1 send ack1 X timeout loss resend pkt1 pkt1 rcv pkt1 timeout resend pkt1 pkt1 rcv ack1 (detect duplicate) rcv pkt1 pkt0 send ack1 (detect duplicate) send pkt0 ack1 send ack1 ack1 rcv pkt0 rcv ack1 rcv ack1 send ack0 send pkt0 pkt0 (ignore) ack0 rcv pkt0 ack0 send ack0 pkt1 (c) ACK loss (d) premature timeout/ delayed ACK Transport Layer: 3-66 Performance of rdt3.0 (stop-and-wait)  U sender: utilization – fraction of time sender busy sending  example: 1 Gbps link, 15 ms prop. delay, 8000 bit packet time to transmit packet into channel: L 8000 bits Dtrans = R = =8 microsecs 10 bits/sec 9 Transport Layer: 3-67 rdt3.0: stop-and-wait operation sender receiver first packet bit transmitted, t = 0 first packet bit arrives RTT last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R Transport Layer: 3-68 rdt3.0: stop-and-wait operation sender receiver L/R L/R Usender= RTT+ L / R.008 RTT = 30.008 = 0.00027  rdt 3.0 protocol performance stinks!  Protocol limits performance of underlying infrastructure (channel) Transport Layer: 3-69 rdt3.0: pipelined protocols operation pipelining: sender allows multiple, “in-flight”, yet-to-be- acknowledged packets range of sequence numbers must be increased buffering at sender and/or receiver Transport Layer: 3-70 Pipelining: increased utilization sender receiver first packet bit transmitted, t = 0 last bit transmitted, t = L / R first packet bit arrives RTT last packet bit arrives, send ACK last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK ACK arrives, send next packet, t = RTT + L / R 3-packet pipelining increases utilization by a factor of 3! U 3L / R.0024 sender = = = 0.00081 RTT + L / R 30.008 Transport Layer: 3-71 Go-Back-N: sender  sender: “window” of up to N, consecutive transmitted but unACKed pkts k-bit seq # in pkt header  cumulative ACK: ACK(n): ACKs all packets up to, including seq # n on receiving ACK(n): move window forward to begin at n+1  timer for oldest in-flight packet Transport Layer: 3-72  Go-Back-N: receiver  ACK-only: always send ACK for correctly-received packet so far, with highest in-order seq # may generate duplicate ACKs need only remember rcv_base  on receipt of out-of-order packet: can discard (don’t buffer) or buffer: an implementation decision re-ACK pkt with highest in-order seq # Receiver view of sequence number space: received and ACKed … … Out-of-order: received but not ACKed rcv_base Not received Transport Layer: 3-73 Go-Back-N in action sender window (N=4) sender receiver 012345678 send pkt0 012345678 send pkt1 send pkt2 receive pkt0, send ack0 012345678 send pkt3 Xloss receive pkt1, send ack1 012345678 (wait) receive pkt3, discard, 012345678 rcv ack0, send (re)send ack1 012345678 pkt4 rcv ack1, send receive pkt4, discard, pkt5 (re)send ack1 ignore duplicate ACK receive pkt5, discard, (re)send ack1 pkt 2 timeout 012345678 send pkt2 012345678 send pkt3 012345678 send pkt4 rcv pkt2, deliver, send ack2 012345678 send pkt5 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 Transport Layer: 3-74 Selective repeat: the approach  pipelining: multiple packets in flight  receiver individually ACKs all correctly received packets buffers packets, as needed, for in-order delivery to upper layer  sender: maintains (conceptually) a timer for each unACKed pkt timeout: retransmits single unACKed packet associated with timeout maintains (conceptually) “window” over N consecutive seq #s limits pipelined, “in flight” packets to be within this window Transport Layer: 3-75 Selective repeat: sender, receiver windows Transport Layer: 3-76 Selective repeat: sender and receiver sender receiver data from above: packet n in [rcvbase,  if next available seq # in rcvbase+N-1] window, send packet  send ACK(n) timeout(n):  out-of-order: buffer  resend packet n, restart  in-order: deliver (also timer deliver buffered, in-order ACK(n) in [sendbase,sendbase+N- packets), advance window 1]: to next not-yet-received  mark packet n as received packet  if n smallest unACKed packet n in [rcvbase- packet, advance window N,rcvbase-1] base to next unACKed seq #  ACK(n) otherwise:  ignore Transport Layer: 3-77 Selective Repeat in action sender window (N=4) sender receiver 012345678 send pkt0 012345678 send pkt1 012345678 send pkt2 receive pkt0, send ack0 012345678 send pkt3 Xloss receive pkt1, send ack1 (wait) receive pkt3, buffer, 012345678 rcv ack0, send send ack3 012345678 pkt4 rcv ack1, send receive pkt4, buffer, pkt5 record ack3 arrived send ack4 receive pkt5, buffer, pkt 2 timeout send ack5 012345678 send pkt2 012345678 (but not 3,4,5) 012345678 rcv pkt2; deliver pkt2, 012345678 pkt3, pkt4, pkt5; send ack2 Q: what happens when ack2 arrives? Transport Layer: 3-78 Selective repeat: sender window (after receipt) receiver window (after receipt) 0123012 pkt0 pkt1 0123012 a dilemma! 0123012 0123012 pkt2 0123012 0123012 example: 0123012 pkt3 X  seq #s: 0, 1, 2, 3 (base 4 counting) 0123012 pkt0 will accept packet  window size=3 (a) no problem with seq number 0 0123012 pkt0 0123012 pkt1 0123012 0123012 pkt2 X 0123012 X 0123012 X timeout retransmit pkt0 0123012 pkt0 will accept packet with seq number 0 (b) oops! Transport Layer: 3-79 Selective repeat: sender window (after receipt) receiver window (after receipt) 0123012 pkt0 pkt1 0123012 a dilemma! 0123012 0123012 pkt2 0123012 0123012 example: 0123012 pkt3 X  seq #s: 0, 1, 2, 3 (base 4 counting)  receiver 0123012 pkt0 will accept packet can’t see  window size=3 (a)sender no problem side with seq number 0  receiver behavior identical in 0both 1 2 3 0 1cases! 2 pkt0  0something’s Q: what relationship is 123012 0(very) pkt1 1 2 3 0 1 2 wrong! pkt2 0123012 0123012 X needed between X 0123012 sequence # size and timeout X window size to avoid retransmit pkt0 0123012 pkt0 problem in scenario (b)? will accept packet with seq number 0 (b) oops! Transport Layer: 3-80 Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management  Principles of congestion control  TCP congestion control Transport Layer: 3-81 TCP: overview RFCs: 793,1122, 2018, 5681, 7323  point-to-point:  cumulative ACKs one sender, one receiver  pipelining:  reliable, in-order byte TCP congestion and flow steam: control set window size no “message boundaries"  connection-oriented: handshaking (exchange of  full duplex data: bi-directional data flow in control messages) initializes sender, receiver state same connection MSS: maximum segment before data exchange size  flow controlled: sender will not overwhelm receiver Transport Layer: 3-82  TCP segment structure 32 bits source port # dest port # segment seq #: ACK: seq # of next sequence number counting bytes of data expected byte; A bit: into bytestream (not this is an ACK acknowledgement number segments!) length (of TCP header) head not len usedC E U A P R S F receive window flow control: # Internet checksum checksum Urg data pointer bytes receiver willing to accept options (variable length) C, E: congestion notification TCP options application data sent by RST, SYN, FIN: data application connection management (variable length) into TCP socket Transport Layer: 3-83 TCP sequence numbers, ACKs outgoing segment from sender Sequence numbers: source port # dest port # byte stream “number” sequence number acknowledgement number rwnd of first byte in checksum urg pointer segment’s data window size Acknowledgements: N seq # of next byte expected from other sender sequence number space side sent sent, not- usable not cumulative ACK ACKed yet ACKed but not usable Q: how receiver handles (“in-flight”) yet sent out-of-order segments outgoing segment from receiver A: TCP spec doesn’t source port # dest port # sequence number say, - up to acknowledgement number A rwnd implementor checksum urg pointer Transport Layer: 3-84 TCP sequence numbers, ACKs Host A Host B User types‘C’ Seq=42, ACK=79, data = ‘C’ host ACKs receipt of‘C’, echoes back Seq=79, ACK=43, data = ‘C’‘C’ host ACKs receipt of echoed ‘C’ Seq=43, ACK=80 simple telnet scenario Transport Layer: 3-85 TCP round trip time, timeout Q: how to set TCP Q: how to estimate RTT? timeout value?  SampleRTT:measured time  longer than RTT, but RTT from segment transmission varies! until ACK receipt ignore retransmissions  too short: premature  SampleRTT will vary, want timeout, unnecessary retransmissions estimated RTT “smoother” average several recent  too long: slow reaction to measurements, not just segment loss current SampleRTT Transport Layer: 3-86 TCP round trip time, timeout EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT  exponential weighted moving average (EWMA)  influence of past sample decreases RTT: gaia.cs.umass.edu to fantasia.eurecom.fr exponentially fast 350 RTT: gaia.cs.umass.edu to fantasia.eurecom.fr  typical value:  = 0.125 RTT (milliseconds) 300 250 RTT (milliseconds) 200 sampleRTT 150 EstimatedRTT 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time (seconnds) time Estimated RTT SampleRTT Transport Layer: 3-87 (seconds) TCP round trip time, timeout  timeout interval: EstimatedRTT plus “safety margin” large variation in EstimatedRTT: want a larger safety margin TimeoutInterval = EstimatedRTT + 4*DevRTT estimated RTT “safety margin”  DevRTT: EWMA of SampleRTT deviation from EstimatedRTT: DevRTT = (1-)*DevRTT + *|SampleRTT-EstimatedRTT| (typically,  = 0.25) * Check out the online interactive exercises for more examples: h ttp://gaia.cs.umass.edu/kurose_ross/interactive/ Transport Layer: 3-88 TCP Sender (simplified) event: data received from event: timeout application  retransmit segment  create segment with seq # that caused timeout  seq # is byte-stream  restart timer number of first data byte in segment event: ACK received  start timer if not already  if ACK acknowledges running previously unACKed think of timer as for oldest unACKed segment segments expiration interval: update what is known to TimeOutInterval be ACKed start timer if there are still unACKed segments Transport Layer: 3-89 TCP Receiver: ACK generation [RFC 5681] Event at receiver TCP receiver action delayed ACK. Wait up to 500ms arrival of in-order segment with expected seq #. All data up for to next segment. If no next segment, expected seq # already ACKed send ACK immediately send single cumulative arrival of in-order segment with expected seq #. One other ACK, ACKing both in-order segments segment has ACK pending immediately send duplicate ACK, arrival of out-of-order segment higher-than-expect seq. #. indicating seq. # of next expected byte Gap detected arrival of segment that immediate send ACK, provided that segment starts at lower end of gap partially or completely fills gap Transport Layer: 3-90 TCP: retransmission scenarios Host A Host B Host A Host B SendBase=92 Seq=92, 8 bytes of data Seq=92, 8 bytes of data timeout timeout Seq=100, 20 bytes of data ACK=100 X ACK=100 ACK=120 Seq=92, 8 bytes of data Seq=92, 8 SendBase=100 bytes of data send cumulative SendBase=120 ACK for 120 ACK=100 ACK=120 SendBase=120 lost ACK scenario premature timeout Transport Layer: 3-91 TCP: retransmission scenarios Host A Host B Seq=92, 8 bytes of data Seq=100, 20 bytes of data ACK=100 X ACK=120 Seq=120, 15 bytes of data cumulative ACK covers for earlier lost ACK Transport Layer: 3-92 TCP fast retransmit Host A Host B TCP fast retransmit if sender receives 3 additional ACKs for same Se q= 9 2, 8 by Seq= data tes of data (“triple duplicate 100, 2 0 byt e s of X data ACKs”), resend unACKed segment with smallest 100 seq # ACK= timeout  likely that unACKed ACK =100 segment lost, so don’t wait ACK =100 for timeout ACK =100 Receipt of three duplicate ACKs indicates 3 Seq=100, 20 bytes of data segments received after a missing segment – lost segment is likely. So retransmit! Transport Layer: 3-93 Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management  Principles of congestion control  TCP congestion control Transport Layer: 3-94 TCP flow control application Q: What happens if Application process network layer delivers removing data from TCP socket buffers data faster than TCP socket application layer receiver buffers removes data from socket buffers? TCP code Network layer delivering IP datagram payload IP into TCP socket code buffers from sender receiver protocol stack Transport Layer: 3-95 TCP flow control application Q: What happens if Application process network layer delivers removing data from TCP socket buffers data faster than TCP socket application layer receiver buffers removes data from socket buffers? TCP code Network layer delivering IP datagram payload IP into TCP socket code buffers from sender receiver protocol stack Transport Layer: 3-96 TCP flow control application Q: What happens if Application process network layer delivers removing data from TCP socket buffers data faster than TCP socket application layer receiver buffers removes data from socket buffers? TCP code receive window flow control: # bytes receiver willing to IP accept code from sender receiver protocol stack Transport Layer: 3-97 TCP flow control application Q: What happens if Application process network layer delivers removing data from TCP socket buffers data faster than TCP socket application layer receiver buffers removes data from socket buffers? TCP flow control code receiver controls sender, so sender won’t overflow IP code receiver’s buffer by transmitting too much, too fast from sender receiver protocol stack Transport Layer: 3-98 TCP flow control  TCP receiver “advertises” free buffer space in rwnd field in to application process TCP header RcvBuffer size set via socket RcvBuffer buffered data options (typical default is 4096 bytes) many operating systems auto- rwnd free buffer space adjust RcvBuffer  sender limits amount of TCP segment payloads unACKed (“in-flight”) data to received rwnd TCP receiver-side buffering  guarantees receive buffer will not overflow Transport Layer: 3-99 TCP flow control flow control: # bytes receiver willing to accept  TCP receiver “advertises” free buffer space in rwnd field in TCP header RcvBuffer size set via socket receive window options (typical default is 4096 bytes) many operating systems auto- adjust RcvBuffer  sender limits amount of unACKed (“in-flight”) data to received rwnd  guarantees receive buffer will not overflow TCP segment format Transport Layer: 3-100 TCP connection management before exchanging data, sender/receiver “handshake”:  agree to establish connection (each knowing the other willing to establish connection)  agree on connection parameters (e.g., starting seq #s) application application connection state: connection state: ESTAB ESTAB connection variables: connection Variables: seq # client-to- seq # client-to- server server server-to-client server-to-client rcvBuffer size rcvBuffer size network at server,client at network server,client Socket clientSocket = Socket connectionSocket = newSocket("hostname","port number"); welcomeSocket.accept(); Transport Layer: 3-101 Agreeing to establish a connection 2-way handshake: Q: will 2-way handshake Let’s talk always work in network? ESTAB OK  variable delays ESTAB  retransmitted messages (e.g. req_conn(x)) due to message loss choose x  message reordering req_conn(x) ESTAB  can’t “see” other side acc_conn(x) ESTAB Transport Layer: 3-102  2-way handshake scenarios choose x req_conn(x) ESTAB acc_conn(x) ESTAB data(x+1) accept data(x+1 ACK(x+1) ) connection x completes No problem! Transport Layer: 3-103 2-way handshake scenarios choose x req_conn(x) ESTAB retransmit acc_conn(x) req_conn( x) ESTAB req_conn(x) connection client x completes server terminat forgets x es ESTAB acc_conn(x) Problem: half open connection! (no Transport Layer: 3-104 client) 2-way handshake scenarios choose x req_conn(x) ESTAB retransmit acc_conn(x) req_conn( x) ESTAB data(x+1) accept data(x+1 retransmit ) data(x+1) connection x completes server client terminat forgets x es req_conn(x) ESTAB data(x+1) accept data(x+1 ) Problem: dup data  TCP 3-way handshake Server state serverSocket = socket(AF_INET,SOCK_STREAM) Client state serverSocket.bind((‘’,serverPort)) serverSocket.listen(1) clientSocket = socket(AF_INET, SOCK_STREAM) connectionSocket, addr = serverSocket.accept() LISTEN clientSocket.connect((serverName,serverPort)) LISTEN choose init seq num, x send TCP SYN msg SYNSENT SYNbit=1, Seq=x choose init seq num, y send TCP SYNACK msg, acking SYN SYN RCVD SYNbit=1, Seq=y ACKbit=1; ACKnum=x+1 received SYNACK(x) ESTAB indicates server is live; send ACK for SYNACK; this segment may contain ACKbit=1, ACKnum=y+1 client-to-server data received ACK(y) indicates client is live ESTAB Transport Layer: 3-106 A human 3-way handshake protocol 1. On belay? 2. Belay on. 3. Climbing. Transport Layer: 3-107 Closing a TCP connection  client, server each close their side of connection send TCP segment with FIN bit = 1  respond to received FIN with ACK on receiving FIN, ACK can be combined with own FIN  simultaneous FIN exchanges can be handled Transport Layer: 3-108 Chapter 3: roadmap  Transport-layer services  Multiplexing and demultiplexing  Connectionless transport: UDP  Principles of reliable data transfer  Connection-oriented transport: TCP  Principles of congestion control  TCP congestion control  Evolution of transport-layer functionality Transport Layer: 3-109 Principles of congestion control Congestion:  informally: “too many sources sending too much data too fast for network to handle”  manifestations: long delays (queueing in router buffers) packet loss (buffer overflow at routers)  different from flow control! congestion  a top-10 problem! control: too many senders, sending too fast flow control: one sender too fast for one receiver Transport Layer: 3-110 Causes/costs of congestion: scenario 1 original data: lin throughput: lout Simplest scenario: Host A  one router, infinite buffers infinite shared output link buffers  input, output link two flows capacity: R R R  no retransmissions needed Host B R/2 Q: What lout delay happens as throughput: arrival rate lin approaches lin R/2 lin R/2 maximum per-connection large delays as R/2? throughput: R/2 arrival rate line approaches capacity Transport Layer: 3-111 Causes/costs of congestion: scenario 2  one router, finite buffers  sender retransmits lost, timed-out packet application-layer input = application-layer output: lin = lout transport-layer input includes retransmissions : l’in lin Host A lin : original data l'in: original data, plus lout retransmitted data R R Host B finite shared output link buffers Transport Layer: 3-112 Causes/costs of congestion: scenario 2 Idealization: perfect knowledge R/2  sender sends only when router buffers lout available throughput: Host A lin : original data lin copy l'in: original data, plus lout R/2 retransmitted data free buffer space! R R Host B finite shared output link buffers Transport Layer: 3-113 Causes/costs of congestion: scenario 2 Idealization: some perfect knowledge  packets can be lost (dropped at router) due to full buffers  sender knows when packet has been dropped: only resends if packet known to be lost Host A lin : original data copy l'in: original data, plus retransmitted data no buffer space! R R Host B finite shared output link buffers Transport Layer: 3-114 Causes/costs of congestion: scenario 2 Idealization: some perfect R/2 knowledge “wasted” lout capacity due to  packets can be lost (dropped at router) due retransmissions to full buffers throughput: when sending  sender knows when packet has been