Transport Layer: TCP Principles and Pipelining Efficiency

This lecture delves into the Transport Layer, focusing on TCP principles and efficiency through pipelining. Topics covered include addressing, multiplexing/demultiplexing, UDP, reliable data transfer, flow control, and congestion control. The concept of pipelined ack-based error control protocols is explored, highlighting sender and receiver interactions, increased utilization, and different forms of error control mechanisms like Go-Back-N and selective repeat.

• Transport Layer
• TCP
• Efficiency
• Pipelining
• Error Control

ashep Follow

Uploaded on Apr 13, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Course on Computer Communication and Networks Lecture 5 Chapter 3; Transport Layer, Part B EDA344/DIT 423, CTH/GU Based on the book Computer Networking: A Top Down Approach, Jim Kurose, Keith Ross, Addison-Wesley. 1 Marina Papatriantafilou Transport layer part2: TCP

2. Roadmap Transport layer services in Internet Addressing, multiplexing/demultiplexing Connectionless, unreliable transport: UDP principles of reliable data transfer Efficiency perspective Next lecture: connection-oriented transport: TCP reliable transfer flow control connection management TCP congestion control 2 Marina Papatriantafilou Transport layer part2: TCP

3. Pipelined ack-based error-control protocols pipelining: sender allows multiple, in-flight , yet-to-be-acknowledged pkts range of sequence numbers must be increased buffering at sender and/or receiver 3 Marina Papatriantafilou Transport layer part2: TCP

4. Pipelining: increased utilization sender receiver first packet bit transmitted, t = 0 last bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK last bit of 2ndpacket arrives, send ACK last bit of 3rdpacket arrives, send ACK RTT RTT = Round Trip Time = 2 * Tpropagation ACK arrives, send next packet, t = RTT + L / R 3-packet pipelining increases stop&wait utilization by a factor of 3! 3L / R RTT + L / R .0024 30.008 U sender = = 0.00081 = 4 Marina Papatriantafilou Transport layer part2: TCP

5. Pipelined protocols: ack-based error control two generic forms (i.e. ack + book-keeping policies) to deal with lost data: go-Back-n selective repeat 5 Marina Papatriantafilou Transport layer part2: TCP

6. Go-Back-n sender window of up to N, consecutive unack ed pkts allowed receiver Ack last correctly received pkt ACK(n): ACKs all pkts up to, including seq # n - cumulative ACK may receive duplicate ACKs timer for oldest in-flight pkt timeout(n): retransmit packet n and all higher seq # pkts in window 6 Marina Papatriantafilou Transport layer part2: TCP

7. https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw /content/interactiveanimations/go-back-n-protocol/index.html GBn in action sender receiver sender window (N=4) send pkt0 send pkt1 send pkt2 send pkt3 (wait) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 receive pkt0, send ack0 receive pkt1, send ack1 Xloss receive pkt3, discard, (re)send ack1 rcv ack0, send pkt4 rcv ack1, send pkt5 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 receive pkt4, discard, (re)send ack1 receive pkt5, discard, (re)send ack1 ignore duplicate ACK pkt 2 timeout send pkt2 send pkt3 send pkt4 send pkt5 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 rcv pkt2, deliver, send ack2 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 7 Marina Papatriantafilou Transport layer part2: TCP

8. Selective repeat: sender, receiver windows receiver individually acknowledges received pkts buffers pkts for eventual in- order delivery to upper layer sender only resends pkts for which ACK not received Requires timer for each unACKed pkt 8 Marina Papatriantafilou Transport layer part2: TCP

9. https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/contenthttps://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content /interactiveanimations/selective-repeat-protocol/index.html Selective repeat in action sender receiver sender window (N=4) send pkt0 send pkt1 send pkt2 send pkt3 (wait) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 receive pkt0, send ack0 receive pkt1, send ack1 Xloss receive pkt3, buffer, send ack3 rcv ack0, send pkt4 rcv ack1, send pkt5 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 receive pkt4, buffer, send ack4 receive pkt5, buffer, send ack5 record ack3 arrived 0 1 2 3 4 5 6 7 8 pkt 2 timeout send pkt2 record ack4 arrived record ack5 arrived 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2 Q: what happens when ack2 arrives? 10 Marina Papatriantafilou Transport layer part2: TCP

10. Roadmap Transport layer services in Internet Addressing, multiplexing/demultiplexing Connectionless, unreliable transport: UDP principles of reliable data transfer Efficiency perspective: pipelined protocols & error control through go-back-n, selective-repeat Sequence numbers Next: connection-oriented transport: TCP reliable transfer flow control connection management TCP congestion control 11 Marina Papatriantafilou Transport layer part2: TCP

11. Selective repeat: Sequence numbers receiver window (after receipt) sender window (after receipt) pkt0 pkt1 pkt2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 example: seq # s: 0, 1, 2, 3 window size=3 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt3 0 1 2 3 0 1 2 X 0 1 2 3 0 1 2 pkt0 will accept packet with seq number 0 duplicate data accepted as new in (b) (a) no problem receiver can t see sender side. receiver behavior identical in both cases! something s (very) wrong! Q:what relationship between seq # size and window size to avoid problem in (b)? pkt0 pkt1 pkt2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 X X X 0 1 2 3 0 1 2 timeout retransmit pkt0 pkt0 0 1 2 3 0 1 2 will accept packet with seq number 0 (b) oops! 12 Marina Papatriantafilou Transport layer part2: TCP

12. Question What do Ack s achieve besides reliability? Flow control: receiver can ack its receiving capacity i.e. avoid swamping the receiver Flow control: Sender/receiver (ie network edge) issue: S cares to not overwhelm R 13 Marina Papatriantafilou Transport layer part2: TCP

13. Ack-based pipelining => error-control & flow control at the same time!!! sender receiver first packet bit transmitted, t = 0 last bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK last bit of 2ndpacket arrives, send ACK last bit of 3rdpacket arrives, send ACK RTT ACK arrives, send next packet, t = RTT + L / R Flow control: Sender/receiver problem; S cares to not overwhelm R 3b-14 Marina Papatriantafilou Transport layer part2: TCP

14. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-15 Marina Papatriantafilou Transport layer part2: TCP

15. TCP: Overview RFCs: 793,1122,1323, 2018, 5681 point-to-point & full duplex data: one sender, one receiver bi-directional data flow in same connection MSS: maximum segment size connection-oriented, reliable, in-order byte steam: Needs handshaking (exchange of control msgs); inits sender & receiver state before data exchange Flow&error control: ack-based, pipelined: (+ extra) congestion control: sender will not flood network application writes data application reads data socket door socket door TCP TCP send buffer receive buffer segment 16 Marina Papatriantafilou Transport layer part2: TCP

16. TCP segment structure 32 bits URG: urgent data (generally not used) counting by bytes of data (not segments!) source port # dest port # sequence number acknowledgement number head len used ACK: ACK # valid not receive window U A P R S F PSH: push data now (generally not used) # bytes rcvr willing to buffer (flow control) checksum Urg data pointer RST, SYN, FIN: connection estab (setup, teardown commands) options (variable length) application data (variable length) Internet checksum (as in UDP) 3-17 Marina Papatriantafilou Transport layer part2: TCP

17. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-18 Marina Papatriantafilou Transport layer part2: TCP

18. TCP seq. numbers, ACKs outgoing segment from sender source port # sequence number acknowledgement number dest port # rwnd sequence numbers: number of first byte in segment s data checksum window size N acknowledgements: seq # of next byte expected from other side cumulative ACK sender sequence number space sent ACKed usable but not yet sent sent, not- yet ACKed ( in- flight ) not usable incoming segment to sender source port # sequence number acknowledgement number A dest port # rwnd checksum 3-19 Marina Papatriantafilou Transport layer part2: TCP

19. TCP seq. numbers, ACKs Always ack next in-order expected byte Host B Host A 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 example scenario Based on telnet msg exchange 3-20 Marina Papatriantafilou Transport layer part2: TCP

20. TCP: cumulative Ack - retransmission scenarios Host B Host B Host A Host A SendBase=92 Seq=92, 8 bytes of data Seq=92, 8 bytes of data Seq=100, 20 bytes of data Seq=100, 20 bytes of data timeout ACK=100 timeout X ACK=100 ACK=120 ACK=120 Seq=92, 8 bytes of data SendBase=100 Seq=120, 15 bytes of data SendBase=120 ACK=120 SendBase=120 Cumulative ACK (Premature) timeout 3-21 Marina Papatriantafilou Transport layer part2: TCP

21. TCP ACK generation [RFC 1122, RFC 5681] TCP Receiver action Event Delayed ACK. Wait max 500ms for next segment then send ACK in-order segment arrival, no gaps, everything else already ACKed immediately send single cumulative ACK in-order segment arrival, no gaps, one delayed ACK pending send (duplicate) ACK, indicating seq. # of next expected byte out-of-order segment arrival higher-than-expect seq. # gap detected 3b-22 Marina Papatriantafilou Transport layer part2: TCP

22. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-23 Marina Papatriantafilou Transport layer part2: TCP

23. Q: how to set TCP timeout value? application transport network link physical segment longer than end-to-end RTT but that varies!!! too short timeout: premature, unnecessary retransmissions too long: slow reaction to loss network link physical application transport network link physical application transport network link physical application transport network link physical segment 24 Marina Papatriantafilou Transport layer part2: TCP

24. TCP round trip time, timeout estimation EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT exponential weighted moving average: influence of past sample decreases exponentially fast typical value: = 0.125 RTT: gaia.cs.umass.edu to fantasia.eurecom.fr 350 RTT: gaia.cs.umass.edu to fantasia.eurecom.fr RTT (milliseconds) 300 250 RTT (milliseconds) 200 sampleRTT EstimatedRTT 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 DevRTT = (1- )*DevRTT + time (seconnds) time (seconds) SampleRTT Estimated RTT *|SampleRTT-EstimatedRTT| (typically, = 0.25) TimeoutInterval = EstimatedRTT + 4*DevRTT safety margin Marina Papatriantafilou Transport layer part2: TCP 3-25

25. TCP fast retransmit (RFC 5681) time-out can be long: long delay before resending lost packet Host B Host A IMPROVEMENT: detect lost segments via duplicate ACKs Seq=92, 8 bytes of data Seq=100, 20 bytes of data X TCP fast retransmit ACK=100 timeout ACK=100 if sender receives 3 duplicate ACKs for same data ACK=100 Seq=100, 20 bytes of data resend unacked segment with smallest seq # likely that unacked segment lost, so don t wait for timeout Implicit NAK! Q: Why need at least 3? 3b-26 Marina Papatriantafilou Transport layer part2: TCP

26. Q: Is TCP stateful or stateless? 27 Marina Papatriantafilou Transport layer part2: TCP

27. Is it possible to have reliable transfer over UDP? 28 Marina Papatriantafilou Transport layer part2: TCP

28. reliable transfer over UDP? add reliability at application layer application-specific error recovery But best to: not reinvent TCP on top of UDP i.e.. if you need TCP, use TCP i.e..: it is best to have protocol definitions and implementations for types of services needed (so that they are reused and not need to be implemented by each user separately and from scratch) 29 Marina Papatriantafilou Transport layer part2: TCP

29. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-30 Marina Papatriantafilou Transport layer part2: TCP

30. Connection Management before exchanging data, sender/receiver handshake : agree to establish connection + connection parameters application application connection state: ESTAB connection variables: seq # client-to-server server-to-client rcvBuffer size at server,client connection state: ESTAB connection Variables: seq # client-to-server server-to-client rcvBuffer size at server,client network network Socket clientSocket = newSocket("hostname","port number"); Socket connectionSocket = welcomeSocket.accept(); 3-31 Marina Papatriantafilou Transport layer part2: TCP

31. Setting up a connection: TCP 3-way handshake client state server state LISTEN choose init seq num, x send TCP SYN msg SYNSENT SYN=1, Seq=x choose init seq num, y send TCP SYN/ACK msg, acking SYN Reserve buffer SYN RCVD SYN=1, Seq=y ACK=1; ACKnum=x+1 received SYN/ACK(x) server is live; send ACK for SYN/ACK; this segment may contain client-to-server data ESTAB ACK=1, ACKnum=y+1 received ACK(y) indicates client is live ESTAB Transport Layer 3-32 Marina Papatriantafilou Transport layer part2: TCP

32. TCP: closing a connection client state server state ESTAB ESTAB clientSocket.close() FIN=1, seq=x FIN_WAIT_1 can no longer send but can receive data CLOSE_WAIT ACK=1; ACKnum=x+1 can still send data wait for server FIN_WAIT_2 close LAST_ACK FIN=1, seq=y can no longer send data TIME_WAIT ACK=1; ACKnum=y+1 timed wait (typically 30s) CLOSED simultaneous FINs can be handled CLOSED RST: alternative way to close connection immediately, when error occurs 3-33 Marina Papatriantafilou Transport layer part2: TCP

33. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-34 Marina Papatriantafilou Transport layer part2: TCP

34. TCP flow control application process application might remove data from TCP socket buffers . application OS TCP socket receiver buffers what if slower than TCP is delivering (i.e. slower than sender is sending) TCP code IP code flow control receiver controls sender, so sender won t overflow receiver s buffer by transmitting too much, too fast from sender receiver protocol stack 3-35 Marina Papatriantafilou Transport layer part2: TCP

35. TCP flow control to application process buffered data RcvBuffer receiver advertises free buffer space through rwnd value in header RcvBuffer size set via socket options (typical default 4 Kbytes) OS can autoadjust RcvBuffer free buffer space rwnd TCP segment payloads receiver-side buffering sender limits unacked ( in-flight ) data to receiver s rwnd value s.t. receiver s buffer will not overflow source port # sequence number acknowledgement number A dest port # To sender rwnd checksum 3-36 3-36 Marina Papatriantafilou Transport layer part2: TCP

36. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-37 Marina Papatriantafilou Transport layer part2: TCP

37. Question: Difference between congestion control and flow control? Congestion control = Avoid congesting the network Congestion is network-core issue in contrast to flow-control, which is sender-receiver (i.e. network edge) issue 38 Marina Papatriantafilou Transport layer part2: TCP

38. Principles of congestion control congestion: informally: many sources sending too much data too fast for network to handle Manifestations? lost packets (buffer overflow at routers) long delays (queueing in router buffers) 39 Marina Papatriantafilou Transport layer part2: TCP

39. Distinction between flow control and congestion control Fig. A. Tanenbaum Computer Networks Need for congestion control Need for flow control 40 Marina Papatriantafilou Transport layer part2: TCP

40. Causes/costs of congestion original data: in throughput: out Host A output link capacity: R link buffers Host B Recall queueing behaviour + losses Losses => retransmissions => even higher load R/2 delay out in R/2 in R/2 reality Ideal per-connection throughput: R/2 (if 2 connections) 41 Marina Papatriantafilou Transport layer part2: TCP

41. Approaches towards congestion control end-end congestion control: no explicit feedback from network congestion inferred from end-system observed loss, delay network-assisted congestion control: routers collaborate for optimal rates + provide feedback to end-systems eg. a single bit indicating congestion explicit rate for sender to send at 3-42 Marina Papatriantafilou Transport layer part2: TCP

42. Roadmap Transport Layer transport layer services multiplexing/demultiplexing connectionless transport: UDP principles of reliable data transfer connection-oriented transport: TCP reliable transfer Acknowledgements Retransmissions Connection management Flow control and buffer space Congestion control Principles TCP congestion control 3b-43 Marina Papatriantafilou Transport layer part2: TCP

43. TCP congestion control: additive increase multiplicative decrease (AIMD) end-end control (no network assistance), sender limits transmission How does sender perceive congestion? loss = timeout or 3 duplicate acks TCP sender reduces rate (Congestion Window) then cwnd RTT rate ~~ bytes/sec Additive Increase: increase cwnd by 1 MSS every RTT until loss detected Multiplicative Decrease: cut cwnd in half after loss To start with: slow start additively increase window size . until loss occurs (then cut window in half) congestion window size cwnd: TCP sender AIMD saw tooth behavior: probing for bandwidth time 3-44 Marina Papatriantafilou Transport layer part2: TCP

44. TCP Slow Start Host B Host A when connection begins, increase rate exponentially until first loss event: initially cwnd = 1 MSS double cwnd every ack of previous batch done by incrementing cwnd for every ACK received summary: initial rate is slow but ramps up exponentially fast then, saw-tooth RTT time 3-45 Marina Papatriantafilou Transport layer part2: TCP

45. TCP cwnd: from exponential to linear growth + reacting to loss Reno: loss indicated by timeout or 3 duplicate ACKs: cwnd is cut in half; then grows linearly Non-optimized: loss indicated by timeout: cwnd set to 1 MSS; then window slow start to threshold, then grows linearly Implementation: variable ssthresh (slow start threshold) on loss event, ssthresh = *cwnd 3-46 Marina Papatriantafilou Transport layer part2: TCP

46. TCPs throughput (Fast recovery - Reno) Session s experience 3-47 Marina Papatriantafilou Transport layer part2: TCP

47. 2 problems, joint solution: limit the rate of the sender! (or How many windows does a TCP s sender maintain? ) rwnd cwnd cwnd, rwnd Fig. A. Tanenbaum Computer Networks Need for congestion control Need for flow control 48 Marina Papatriantafilou Transport layer part2: TCP

48. TCP combined flow-ctrl, congestion ctrl windows sender sequence number space Min{cwnd, rwnd} TCP sending rate: send min {cwnd, rwnd} bytes, wait for ACKS, then send more last byte ACKed last byte sent sent, not- yet ACKed ( in- flight ) sender limits transmission: LastByteSent- LastByteAcked < Min{cwnd, rwnd} cwnd is dynamic, function of perceived network congestion, rwnd dymanically limited by receiver s buffer space 49 Marina Papatriantafilou Transport layer part2: TCP

49. TCP Fairness fairness goal: if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/K TCP connection 1 bottleneck router capacity R TCP connection 2 3-50 Marina Papatriantafilou Transport layer part2: TCP

50. Q: Can a TCP implementation deviate from the Congestion-Control standard? 51 Marina Papatriantafilou Transport layer part2: TCP

Load More ...