Chapter 3 Transport Layer 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...

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!) 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 Computer Networking: A.For a revision history, see the slide note for this page Top-Down Approach Thanks and enjoy! JFK/KWR 8th edition Jim Kurose, Keith Ross All material copyright 1996-2020 Pearson, 2020 J.F Kurose and K.W. Ross, All Rights Reserved ١ Transport layer: overview :Our goal understand principles ▪ learn about Internet transport ▪ behind transport layer :layer protocols :services UDP: connectionless transport multiplexing, TCP: connection-oriented reliable demultiplexing transport reliable data transfer TCP congestion control flow control congestion control ٢ 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 services and protocols application transport ▪ network provide logical communication mobile network data link physical between application processes national or global ISP l og running on different hosts ica l en transport protocols actions in end ▪ d -e :systems nd local or tra sender: breaks application messages regional ISP n sp into segments, passes to network layer ort home network content receiver: reassembles segments into provider network datacenter messages, passes to application layer application transportnetwork network ▪ data link two transport protocols available physical to Internet applications enterprise network TCP, UDP ٤ Transport vs. network layer services and protocols network layer: logical ▪ communication between hosts transport layer: logical ▪ communication between processes relies on, enhances, network layer services ٥ Transport Layer Actions :Sender application is passed an application- ▪ application app. msg layer message transport determines segment ▪ TThh transport app. msg header fields values network (IP) creates segment ▪ network (IP) link passes segment to IP ▪ link physical physical ٦ Transport Layer Actions :Receiver application receives segment from IP ▪ application checks header values ▪ transport transport app. msg extracts application-layer ▪ message network (IP) network (IP) demultiplexes message ▪ link up to application via link socket physical Th physical app. msg ٧ Two principal Internet transport protocols application transport TCP: Transmission Control Protocol ▪ mobile network network data link physical reliable, in-order delivery national or global ISP l og congestion control ica l en flow control d -e connection setup nd local or ▪ tra UDP: User Datagram Protocol regional ISP n sp ort unreliable, unordered delivery home network content provider no-frills extension of “best-effort” IP network datacenter application transportnetwork :services not available ▪ network data link physical delay guarantees bandwidth guarantees enterprise network ٨ 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 ٩  HTTP server client application application HTTP msg transport transport network transport network link network link physical link physical physical ١٠  HTTP server client application application HTTP msg transport Ht HTTP msg transport network transport network link network link physical link physical physical ١١  HTTP server client application application HTTP msg transport Ht HTTP msg Hnnetwork Ht HTTP msg transport transport network link network link physical link physical physical ١٢  HTTP server client application application transport transport network transport network link network link physical link physical physical Hn Ht HTTP msg ١٣  HTTP server client1 client2 application P-client1 P-client2 application transport transport network transport network link network link physical link physical physical ١٤ Multiplexing/demultiplexing :multiplexing at sender :demultiplexing at receiver handle data from multiple use header info to deliver sockets, add transport header received segments to correct (later used for demultiplexing) socket application application P1 P2 application socket P3 transport P4 process transport network transport network link network link physical link physical physical ١٥ How demultiplexing works host receives IP datagrams ▪ bits 32 each datagram has source IP # source port # dest port address, destination IP address each datagram carries one other header fields transport-layer segment each segment has source, application destination port number data (payload) host uses IP addresses & port ▪ numbers to direct segment to appropriate socket TCP/UDP segment format ١٦ Connectionless demultiplexing when receiving host receives :UDP segment checks destination port # in segment directs UDP segment to socket # with that port when creating datagram to ▪ send into UDP socket, must IP/UDP datagrams with same dest. specify port #, but different source IP destination IP address addresses and/or source port # destination port numbers will be directed to same socket at receiving host ١٧  Connectionless demultiplexing: an example DatagramSocket serverSocket = new DatagramSocket DatagramSocket mySocket2 DatagramSocket mySocket1 = = new DatagramSocket ;(6428) ;new DatagramSocket (5775) ;(9157) application application P1 application P3 P4 transport transport transport network network link network link physical link physical physical source port: 6428 ? :source port dest port: 9157 ? :dest port source port: 9157 ? :source port dest port: 6428 ? :dest port ١٨ Connection-oriented demultiplexing TCP socket identified by ▪ server may support many ▪ :4-tuple :simultaneous TCP sockets source IP address each socket identified by its source port number own 4-tuple dest IP address each socket associated with dest port number a different connecting client demux: receiver uses all ▪ four values (4-tuple) to direct segment to appropriate socket ١٩ Connection-oriented demultiplexing: example application application P4 P5 P6 application P1 P2 P3 transport transport transport network network link network link physical link physical physical server: IP address B host: IP source IP,port: B,80 host: IP dest IP,port: A,9157 source IP,port: C,5775 address address dest IP,port: B,80 A 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 ٢٠ 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 ٢١ UDP: User Datagram Protocol no frills,” “bare bones” Internet“ ▪ ?Why is there a UDP transport protocol no connection ▪ establishment (which can best effort” service, UDP“ ▪ add RTT delay) :segments may be simple: no connection state ▪ lost at sender, receiver delivered out-of-order to app small header size ▪ :connectionless ▪ no congestion control ▪ no handshaking between UDP UDP can blast away as fast as ▪ sender, receiver !desired each UDP segment handled can function in the face of ▪ independently of others congestion ٢٢ 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 ▪ ٢٣ UDP: User Datagram Protocol [RFC 768] ٢٤ UDP: Transport Layer Actions SNMP client SNMP server application application transport transport (UDP) (UDP) network (IP) network (IP) link link physical physical ٢٥ UDP: Transport Layer Actions SNMP client SNMP server :UDP sender actions application is passed an application- ▪ application SNMP msg layer message transport determines UDP segment ▪ UDPhtransport UDP h SNMP msg (UDP) header fields values (UDP) network (IP) creates UDP segment ▪ network (IP) link passes segment to IP ▪ link physical physical ٢٦ UDP: Transport Layer Actions SNMP client SNMP server :UDP receiver actions application receives segment from IP ▪ application checks UDP checksum ▪ transport transport SNMP msg header value (UDP) (UDP) extracts application-layer ▪ network UDPh SNMP(IP) msg message network (IP) demultiplexes message ▪ link link up to application via physical socket physical ٢٧ UDP segment header bits 32 # 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 ٢٨ 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) ٢٩ UDP checksum Goal: detect errors (i.e., flipped bits) in transmitted segment :sender :receiver treat contents of UDP ▪ compute checksum of received ▪ segment (including UDP header fields) as sequence of 16-bit segment integers check if computed checksum ▪ checksum: addition (one’s ▪ :equals checksum field value complement sum) of segment Not equal - error detected content Equal - no error detected. But maybe checksum value put into UDP ▪.… errors nonetheless? More later checksum field ٣٠ Internet checksum: an example example: add two 16-bit integers 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 sum 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 checksum 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 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: http://gaia.cs.umass.edu/kurose_ross/interactive * ٣١ !Internet checksum: weak protection example: add two 16-bit integers 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 Even though numbers have sum 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 changed (bit checksum 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 flips), no change !in checksum ٣٢ 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 ٣٤  Principles of reliable data transfer sending receiving process process application data data transport reliable channel reliable service abstraction ٣٥  Principles of reliable data transfer sending receiving sending receiving process process process process application data data application data data transport transport reliable channel sender-side of receiver-side reliable service abstraction reliable data of reliable data transfer protocol transfer protocol transport network unreliable channel reliable service implementation ٣٦ Principles of reliable data transfer sending receiving process process application data data transport sender-side of receiver-side Complexity of reliable data reliable data of reliable data transfer protocol transfer protocol transfer protocol will depend (strongly) on characteristics of transport network unreliable channel (lose, unreliable channel corrupt, reorder data?) reliable service implementation ٣٧ Principles of reliable data transfer sending receiving process process application data data transport sender-side of receiver-side Sender, receiver do not know reliable data of reliable data transfer protocol transfer protocol the “state” of each other, e.g., ?was a message received transport unless communicated via a ▪ network unreliable channel message reliable service implementation ٣٨  Reliable data transfer protocol (rdt): interfaces rdt_send(): called from above, deliver_data(): called by rdt (e.g., by app.). Passed data to to deliver data to upper layer deliver to receiver upper layer sending receiving process process ()rdt_send data data ()deliver_data sender-side data receiver-side implementation of implementation of rdt reliable data packet rdt reliable data transfer protocol transfer protocol ()udt_send Header data Header data ()rdt_rcv unreliable channel udt_send(): called by rdt rdt_rcv(): called when packet to transfer packet over Bi-directional communication over arrives on receiver side of unreliable channel to receiver unreliable channel channel ٣٩ 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 state state 1 event uniquely determined by 2 next event actions ٤٠ 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) sender call from above packet = make_pkt(data) receiver call from extract (packet,data) udt_send(packet) below deliver_data(data) ٤١ 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 ▪ ٤٢ 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 wait sender sends one packet, then waits for receiver response ٤٣ 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 Λ call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) ٤٤ rdt2.0: FSM specification rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) && rdt_rcv(rcvpkt) isNAK(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 Λ call from receiver below Note: “state” of receiver (did the receiver get my message correctly?) isn’t known to sender unless rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) somehow communicated from receiver to sender deliver_data(data) !that’s why we need a protocol ▪ udt_send(ACK) ٤٥ 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 Λ call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) ٤٦ 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 Λ call from receiver below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) ٤٧ !rdt2.0 has a fatal flaw what happens if ACK/NAK :handling duplicates ?corrupted sender retransmits current pkt ▪ sender doesn’t know what ▪ if ACK/NAK corrupted !happened at receiver sender adds sequence number ▪ can’t just retransmit: possible ▪ to each pkt duplicate receiver discards (doesn’t ▪ deliver up) duplicate pkt stop and wait sender sends one packet, then waits for receiver response ٤٨ 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 above NAK 0 udt_send(sndpkt) rdt_rcv(rcvpkt) rdt_rcv(rcvpkt) notcorrupt(rcvpkt) && && notcorrupt(rcvpkt) && isACK(rcvpkt) isACK(rcvpkt) && Λ Λ 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) ٤٩ 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) && (corrupt(rcvpkt) rdt_rcv(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) from 0 from 1 && 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) ٥٠ rdt2.1: discussion :sender :receiver seq # added to pkt ▪ must check if received ▪ ?two seq. #s (0,1) will suffice. Why▪ packet is duplicate must check if received ACK/NAK ▪ state indicates whether 0 or 1 is corrupted # expected pkt seq twice as many states ▪ note: receiver can not know ▪ state must “remember” whether if its last ACK/NAK received “expected” pkt should have seq # of 0 OK at sender or 1 ٥١  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 NAK: ▪ retransmit current pkt As we will see, TCP uses this approach to be NAK-free ٥٢ 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 ( isACK(rcvpkt,1) call 0 from ACK above 0 udt_send(sndpkt) sender FSM fragment rdt_rcv(rcvpkt) notcorrupt(rcvpkt) && isACK(rcvpkt,0) && && rdt_rcv(rcvpkt) || corrupt(rcvpkt)) Λ (has_seq1(rcvpkt) Wait for receiver FSM from 0 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) ٥٣ 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 ٥٤ 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 receiver must specify seq # of packet being ACKed use countdown timer to interrupt after “reasonable” amount ▪ of time timeout ٥٥ 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 ٥٦ 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 Λ Λ 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) && rdt_rcv(rcvpkt) || corrupt(rcvpkt) ) sndpkt = make_pkt(1, data, checksum) ( isACK(rcvpkt,0) udt_send(sndpkt) start_timer Λ ٥٧ 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 pkt1 send pkt1 pkt1 send pkt1 rcv pkt1 X ack1 loss send ack1 rcv ack1 send pkt0 pkt0 rcv pkt0 timeout pkt1 ack0 send ack0 resend pkt1 rcv pkt1 ack1 send ack1 rcv ack1 send pkt0 pkt0 no loss (a) rcv pkt0 ack0 send ack0 packet loss (b) ٥٨ rdt3.0 in action sender receiver send pkt0 pkt0 rcv pkt0 ack0 send ack0 rcv ack0 send pkt1 pkt1 rcv pkt1 ack1 send ack1 X loss timeout pkt1 resend pkt1 rcv pkt1 (detect duplicate) ack1 send ack1 rcv ack1 send pkt0 pkt0 rcv pkt0 ack0 send ack0 ACK loss (c) ٥٩ 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 ٦٠ 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 ▪ timeout(n): retransmit packet n and all higher seq # packets in window ٦١ ▪ 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 ٦٢ Go-Back-N in action sender window (N=4) sender receiver 876543210 send pkt0 876543210 send pkt1 receive pkt0, send ack0 876543210 send pkt2 Xloss receive pkt1, send ack1 876543210 send pkt3 (wait) ,receive pkt3, discard 876543210 rcv ack0, send pkt4 send ack1(re) 876543210 rcv ack1, send pkt5 ,receive pkt4, discard send ack1(re) ignore duplicate ACK ,receive pkt5, discard send ack1(re) pkt 2 timeout 876543210 send pkt2 876543210 send pkt3 876543210 send pkt4 rcv pkt2, deliver, send ack2 876543210 send pkt5 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 ٦٣ Selective repeat receiver individually acknowledges all correctly received ▪ packets buffers packets, as needed, for eventual in-order delivery to upper layer sender times-out/retransmits individually for unACKed packets ▪ sender maintains timer for each unACKed pkt sender window ▪ N consecutive seq #s limits seq #s of sent, unACKed packets ٦٤ Selective repeat: sender, receiver windows ٦٥ Selective repeat: sender and receiver sender receiver :data from above packet n in [rcvbase, rcvbase+N-1] if next available seq # in window, ▪ send ACK(n) ▪ send packet out-of-order: buffer ▪ :timeout(n) in-order: deliver (also deliver ▪ resend packet n, restart timer ▪ buffered, in-order packets), advance window to next not-yet- :ACK(n) in [sendbase,sendbase+N] received packet mark packet n as received ▪ packet n in [rcvbase-N,rcvbase-1] if n smallest unACKed packet, ▪ advance window base to next ACK(n) ▪ # unACKed seq :otherwise ignore ▪ ٦٦ Selective Repeat in action sender window (N=4) sender receiver 876543210 send pkt0 876543210 send pkt1 876543210 send pkt2 receive pkt0, send ack0 876543210 send pkt3 Xloss receive pkt1, send ack1 (wait) ,receive pkt3, buffer 876543210 rcv ack0, send pkt4 send ack3 876543210 rcv ack1, send pkt5 ,receive pkt4, buffer record ack3 arrived send ack4 ,receive pkt5, buffer pkt 2 timeout send ack5 876543210 send pkt2 876543210 (but not 3,4,5) 876543210 ,rcv pkt2; deliver pkt2 876543210 pkt3, pkt4, pkt5; send ack2 ?Q: what happens when ack2 arrives ٦٧ 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 ▪ ٦٨ TCP: overview RFCs: 793,1122, 2018, 5681, 7323 :point-to-point ▪ cumulative ACKs ▪ one sender, one receiver :pipelining ▪ :reliable, in-order byte steam ▪ TCP congestion and flow control "no “message boundaries set window size :full duplex data ▪ :connection-oriented ▪ bi-directional data flow in same handshaking (exchange of control connection messages) initializes sender, MSS: maximum segment size receiver state before data exchange :flow controlled ▪ sender will not overwhelm receiver ٦٩  TCP segment structure bits 32 # source port # dest port segment seq #: counting ACK: seq # of next expected sequence number bytes of data into bytestream byte; A bit: this is an ACK (not segments!) acknowledgement number length (of TCP header) head not len used C EUAP R SF receive window flow control: # bytes Internet checksum checksum Urg data pointer receiver willing to accept options (variable length) C, E: congestion notification TCP options application data sent by RST, SYN, FIN: connection data management application into (variable length) TCP socket ٧٠ TCP sequence numbers, ACKs outgoing segment from sender :Sequence numbers # source port # dest port sequence number byte stream “number” of acknowledgement number rwnd first byte in segment’s data checksum urg pointer window size :Acknowledgements N seq # of next byte expected from other side sender sequence number space cumulative ACK sent sent, not- usable not ACKed yet ACKed but not usable yet sent Q: how receiver handles out-of- (”in-flight“) order segments outgoing segment from receiver # source port # dest port A: TCP spec doesn’t say, - up sequence number acknowledgement number to implementor A rwnd checksum urg pointer ٧١ TCP sequence numbers, ACKs Host A Host B User types‘C’ Seq=42, ACK=79, data = ‘C’ host ACKs receipt of‘C’, echoes back ‘C’ Seq=79, ACK=43, data = ‘C’ host ACKs receipt of echoed ‘C’ Seq=43, ACK=80 simple telnet scenario ٧٢ TCP Sender (simplified) event: data received from event: timeout application retransmit segment that ▪ caused timeout # create segment with seq ▪ restart timer ▪ seq # is byte-stream number ▪ of first data byte in segment event: ACK received start timer if not already ▪ running if ACK acknowledges ▪ previously unACKed segments think of timer as for oldest unACKed segment update what is known to be ACKed expiration interval: TimeOutInterval start timer if there are still unACKed segments ٧٣ TCP Receiver: ACK generation [RFC 5681] Event at receiver TCP receiver action arrival of in-order segment with delayed ACK. Wait up to 500ms expected seq #. All data up to ,for next segment. If no next segment expected seq # already ACKed send ACK arrival of in-order segment with immediately send single cumulative expected seq #. One other ACK, ACKing both in-order segments segment has ACK pending arrival of out-of-order segment ,immediately send duplicate ACK. #.higher-than-expect seq indicating seq. # of next expected byte Gap detected arrival of segment that immediate send ACK, provided that partially or completely fills gap segment starts at lower end of gap ٧٤ 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 Seq=100, 20 bytes of data timeout timeout 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 ٧٥ 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 ٧٦ TCP fast retransmit Host A Host B TCP fast retransmit if sender receives 3 additional Seq=92 ACKs for same data (“triple Seq=1 , 8 byte s of da ta 00, 20 duplicate ACKs”), resend unACKed bytes of data # segment with smallest seq X likely that unACKed segment ▪ =100 ACK lost, so don’t wait for timeout =100 timeout A C K =100 ACK C K =100 Receipt of three duplicate ACKs A indicates 3 segments received Seq=100, 20 bytes of data after a missing segment – lost !segment is likely. So retransmit ٧٧ 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 ▪ ٧٨ TCP flow control application Q: What happens if network process Application removing layer delivers data faster than data from TCP socket application layer removes buffers TCP socket ?data from socket buffers receiver buffers TCP code Network layer delivering IP datagram payload into TCP IP socket buffers code from sender receiver protocol stack ٧٩ TCP flow control application Q: What happens if network process Application removing layer delivers data faster than data from TCP socket application layer removes buffers TCP socket ?data from socket buffers receiver buffers TCP code Network layer delivering IP datagram payload into TCP IP socket buffers code from sender receiver protocol stack ٨٠ TCP flow control application Q: What happens if network process Application removing layer delivers data faster than data from TCP socket application layer removes buffers TCP socket ?data from socket buffers receiver buffers TCP code receive window flow control: # bytes receiver willing to accept IP code from sender receiver protocol stack ٨١ TCP flow control application Q: What happens if network process Application removing layer delivers data faster than data from TCP socket application layer removes buffers TCP socket ?data from socket buffers receiver 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 ٨٢ TCP flow control TCP receiver “advertises” free buffer ▪ space in rwnd field in TCP header to application process RcvBuffer size set via socket options (typical default is 4096 bytes) RcvBuffer buffered data many operating systems autoadjust rwnd free buffer space RcvBuffer sender limits amount of unACKed ▪ TCP segment payloads (“in-flight”) data to received rwnd guarantees receive buffer will not ▪ TCP receiver-side buffering overflow ٨٣ 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 options receive window (typical default is 4096 bytes) many operating systems autoadjust RcvBuffer sender limits amount of unACKed ▪ (“in-flight”) data to received rwnd guarantees receive buffer will not ▪ overflow TCP segment format ٨٤ 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: ESTAB connection state: ESTAB :connection variables :connection Variables seq # client-to-server seq # client-to-server server-to-client server-to-client rcvBuffer size rcvBuffer size at server,client at server,client network network = Socket clientSocket Socket connectionSocket = ;newSocket("hostname","port number") ;()welcomeSocket.accept ٨٥ Agreeing to establish a connection :way handshake-2 Q: will 2-way handshake Let’s talk ?always work in network ESTAB ESTAB OK variable delays ▪ retransmitted messages (e.g. ▪ req_conn(x)) due to message loss message reordering ▪ choose x req_conn(x) ESTAB can’t “see” other side ▪ acc_conn(x) ESTAB ٨٦  way handshake scenarios-2 choose x req_conn(x) ESTAB acc_conn(x) ESTAB data(x+1) accept ACK(x+1) data(x+1) connection x completes !No problem ٨٧ way handshake scenarios-2 choose x req_conn(x) ESTAB retransmit acc_conn(x) req_conn(x) ESTAB req_conn(x) connection client x completes server terminates forgets x ESTAB acc_conn(x) Problem: half open connection! (no client) ٨٨  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 ٨٩ 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 ٩٠ 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 ٩١ 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 control: !a top-10 problem ▪ too many senders, sending too fast flow control: one sender too fast for one receiver ٩٢ Approaches towards congestion control :End-end congestion control no explicit feedback from ▪ network congestion inferred from ▪ ACKs data data ACKs observed loss, delay approach taken by TCP ▪ ٩٣ Approaches towards congestion control Network-assisted congestion :control explicit congestion info routers provide direct feedback ▪ to sending/receiving hosts with data data ACKs flows passing through congested ACKs router may indicate congestion level or ▪ explicitly set sending rate TCP ECN ▪ ٩٤ 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 ٩٥ TCP congestion control: AIMD approach: senders can increase sending rate until packet loss ▪ (congestion) occurs, then decrease sending rate on loss event Additive Increase Multiplicative Decrease increase sending rate by 1 cut sending rate in half at maximum segment size every each loss event RTT until loss detected AIMD sawtooth TCP sender Sending rate behavior: probing for bandwidth time ٩٦ TCP AIMD: more Multiplicative decrease detail: sending rate is Cut in half on loss detected by triple duplicate ACK (TCP Reno) ▪ Cut to 1 MSS (maximum segment size) when loss detected by ▪ timeout (TCP Tahoe) ٩٧ TCP slow start Host A Host B when connection begins, ▪ increase rate exponentially one segm :until first loss event ent RTT initially cwnd = 1 MSS two segm ents double cwnd every RTT done by incrementing cwnd four segm ents for every ACK received summary: initial rate is ▪ slow, but ramps up time exponentially fast ٩٨ TCP: from slow start to congestion avoidance Q: when should the exponential ?increase switch to linear X A: when cwnd gets to 1/2 of its.value before timeout :Implementation variable ssthresh ▪ on loss event, ssthresh is set to ▪ 1/2 of cwnd just before loss event /Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive * ٩٩ Chapter 3: summary principles behind transport ▪ :Up next :layer services leaving the network ▪ multiplexing, demultiplexing “edge” (application, reliable data transfer transport layers) flow control ”into the network “core ▪ congestion control two network-layer ▪ :chapters data plane control plane ١٠٠