TCP Review - University of Calgary in Alberta

TCP Review - University of Calgary in Alberta

TCP Review Carey Williamson Department of Computer Science University of Calgary Credit: Most of this content was provided by Erich Nahum (IBM Research) Transmission Control Protocol (TCP) Connection-oriented, point-to-point protocol: Connection establishment and teardown phases Phone-like circuit abstraction (application-layer view) One sender, one receiver Called a reliable byte stream protocol General purpose (for any network environment) Originally optimized for certain kinds of transfer: Telnet (interactive remote login) FTP (long, slow transfers) Web is like neither of these! 2 TCP Protocol (contd) socket layer application writes data TCP send buffer

application reads data TCP receive buffer data segment socket layer ACK segment Provides a reliable, in-order, byte stream abstraction: Recover lost packets and detect/drop duplicates Detect and drop corrupted packets Preserve order in byte stream, no message boundaries Full-duplex: bi-directional data flow in same connection Flow and congestion control: Flow control: sender will not overwhelm receiver Congestion control: sender will not overwhelm the network

Sliding window flow control Send and receive buffers Congestion control done via adaptive flow control window size 3 The TCP Header 32 bits Fields enable the following: Uniquely identifying each TCP connection (4-tuple: client IP and port, server IP and port) Identifying a byte range within that connection Checksum value to detect corruption Flags to identify protocol state transitions (SYN, FIN, RST) Informing other side of your state (ACK) source port # dest port # sequence number acknowledgement head not U A Pnumber R S Frcvr window size len used checksum

ptr urgent data Options (variable length) application data (variable length) 4 Establishing a TCP Connection Client sends SYN with initial sequence number (ISN = X) Server responds with its own SYN w/seq number Y and ACK of client ISN with X+1 (next expected byte) Client ACKs server's ISN with Y+1 The 3-way handshake X, Y randomly chosen All modulo 32-bit arithmetic client server connect() SYN ( (

SYN Y) + listen() port 80 X) (X ACK +1) ACK ( Y+1) time accept() read() 5 Sending Data socket layer application writes data TCP send buffer

application reads data data segment ACK segment TCP receive buffer socket layer Sender TCP passes segments to IP to transmit: Keeps a copy in buffer at send side in case of loss Called a reliable byte stream protocol Sender must obey receiver advertised window Receiver sends acknowledgments (ACKs) ACKs can be piggybacked on data going the other way Protocol allows receiver to ACK every other packet in attempt to reduce ACK traffic (delayed ACKs) Delay should not be more than 500 ms (typically 200 ms) Well later see how this causes a few problems 6 Preventing Congestion Sender may not only overrun receiver, but may also overrun intermediate routers: No way to explicitly know router buffer occupancy, so we need to infer it from packet losses Assumption is that losses stem from congestion in the network

(i.e., an intermediate router has no more buffers available) Sender maintains a congestion window (called cwnd or CW) Never have more than CW of un-acknowledged data outstanding (or RWIN data; min of the two) Successive ACKs from receiver cause CW to grow. How CW grows depends on which of 2 phases TCP is in: Slow-start: initial state. Grows CW quickly (exponentially). Congestion avoidance: steady-state. Grows CW slowly (linearly). Switch between the two when CW > slow-start threshold 7 Congestion Control Principles Lack of congestion control would lead to congestion collapse (Jacobson 88). Idea is to be a good network citizen. Would like to transmit as fast as possible without loss. Probe network to find available bandwidth. In steady-state: linear increase in CW per RTT. After loss event: CW is halved. This general approach is called Additive Increase and Multiplicative Decrease (AIMD). Various papers on why AIMD leads to network stability. 8 Slow Start Loss occurs OR

CW > slow start threshold Then switch to congestion avoidance If we detect loss, cut CW in half Exponential increase in window size per RTT sender receiver RTT Initial CW = 1. After each ACK, CW += 1; Continue until: one segm ent two segm ents four segm ents time 9

Congestion Avoidance Until (loss) { after CW packets ACKed: CW += 1; } ssthresh = CW/2; Depending on loss type: SACK/Fast Retransmit: CW/= 2; continue; Course grained timeout: CW = 1; go to slow start. (This is for TCP Reno/SACK: TCP Tahoe always sets CW=1 after a loss) 10 How are losses recovered? What if packet is lost (data or ACK!) Coarse-grained Timeout: sender receiver Seq=9 some period of time Event is called a retransmission timeout (RTO) RTO value is based on estimated round-trip time (RTT) RTT is adjusted over time using exponential weighted moving

average: RTT = (1-x)*RTT + (x)*sample (x is typically 0.1) First done in TCP Tahoe timeout Sender does not receive ACK after 2, 8 b y X t es da ta =100 ACK loss Seq=9 2, 8 b y te s data =100 ACK time

lost ACK scenario 11 Fast Retransmit Receiver expects N, gets N+1: sender receiver Immediately sends ACK(N) This is called a duplicate ACK Does NOT delay ACKs here! Continue sending dup ACKs for each subsequent packet (not N) ACK 3000 SEQ=300 0 SEQ=400 X 0 SEQ=500 0 SEQ=600 0 Sender gets 3 duplicate ACKs:

Infers N is lost and resends 3 chosen so out-of-order packets dont ACK 3000 ACK 3000 ACK 3000 trigger Fast Retransmit accidentally Called fast since we dont need to wait for a full RTT Introduced in TCP Reno , size=100 0 SEQ=300 0, size=10 00 time 12 Other Loss Recovery Methods Selective Acknowledgements (SACK): Returned ACKs contain option w/SACK block Block says, "got up N-1 AND got N+1 through N+3" A single ACK can generate a retransmission New Reno partial ACKs:

New ACK during fast retransmit may not ACK all outstanding data. Ex: Have ACK of 1, waiting for 2-6, get 3 dup acks of 1 Retransmit 2, get ACK of 3, can now infer 4 lost as well Other schemes exist (e.g., Vegas) Reno has been prevalent; SACK now catching on 13 Connection Termination client server X) FIN( ACK(X close() +1) F IN( Y ) (Y ACK +1)

timed wait Either side may terminate a connection. ( In fact, connection can stay half-closed.) Let's say the server closes (typical in WWW) Server sends FIN with seq Number (SN+1) (i.e., FIN is a close() byte in sequence) Client ACK's the FIN with SN+2 ("next expected") time Client sends it's own FIN when ready Server ACK's client FIN as well with SN+1. closed 14 The TCP State Machine TCP uses a Finite State Machine, kept by each side of a connection, to keep track of what state a connection is in. State transitions reflect inherent races that can happen in the network, e.g., two FIN's passing each other in the network. Certain things can go wrong along the way, i.e., packets can be dropped or corrupted. In fact, machine is not

perfect; certain problems can arise not anticipated in the original RFC. This is where timers will come in, which we will discuss more later. 15 TCP Connection Establishment CLOSED CLOSED: more implied than actual, i.e., no connection LISTEN: willing to receive connections (accept call) SYN-SENT: sent a SYN, waiting for SYN-ACK SYN-RECEIVED: received a SYN, waiting for an ACK of our SYN ESTABLISHED: connection ready for data transfer server application calls listen() client application calls connect() send SYN LISTEN SYN_SENT receive SYN send SYN + ACK

receive SYN send ACK SYN_RCVD receive SYN & ACK send ACK receive ACK ESTABLISHED 16 TCP Connection Termination ESTABLISHED FIN-WAIT-1: we closed first, waiting for ACK of our FIN (active close) FIN-WAIT-2: we closed first, other side has ACKED our FIN, but not yet FIN'ed CLOSING: other side closed before it received our FIN TIME-WAIT: we closed, other side closed, got ACK of our FIN CLOSE-WAIT: other side sent FIN first, not us (passive close) LAST-ACK: other side sent FIN, then we did, now waiting for ACK

close() called send FIN receive FIN send ACK FIN_WAIT_1 receive ACK receive FIN send ACK of FIN FIN_WAIT_2 CLOSE_WAIT close() called send FIN CLOSING receive FIN receive ACK send ACK of FIN LAST_ACK TIME_WAIT receive ACK wait 2*MSL (240 seconds) CLOSED

17 Summary: TCP Protocol Protocol provides reliability in face of complex and unpredictable network behavior Tries to trade off efficiency with being "good network citizen (i.e., fairness) Vast majority of bytes transferred on Internet today are TCP-based: Web Email Peer-to-peer (Napster, Gnutella, FreeNet, KaZaa, BitTorrent) Video streaming applications (Netflix, YouTube) Online social networks (Facebook, Twitter) Other emerging network applications 18

Recently Viewed Presentations

  • Quadrilaterals Polygons with four sides Types of Quadrilaterals

    Quadrilaterals Polygons with four sides Types of Quadrilaterals

    Quadrilaterals Polygons with four sides Types of Quadrilaterals Square: Quadrilateral with four equal sides and four right angles (90 degrees) Types of Quadrilaterals Rectangle: Quadrilateral with two pairs of equal sides and four right angles (90 degrees) Types of Quadrilaterals...
  • Terms to know…before play - Typepad

    Terms to know…before play - Typepad

    Oedipus—aka "ED" -main character, tragic hero…current King of Thebes because he solved the riddle of the Sphinx. Jocasta—Ed's wife and mother….she is the Queen of Thebes. Creon—Jocasta's brother—Ed's uncle AND brother-in-law (family tree is kind of tweaked… ) Teiresias—blind prophet—tries...
  • Public Speaking Skills Necessary for The Lector Two

    Public Speaking Skills Necessary for The Lector Two

    Cle-ar-pro-nun-ci-a-tion-of-words-so-that-o-thers-can-hear… Read a few paragraphs exaggerating your reading and grimacing as you speak. Then, read faster but still in syllables and making sure that you pronounce each of the letters in each word.
  • PowerPoint-Präsentation


    The luminous intensity distribution is . measured. and . checked. for compliance . after photometric stability. Depending on the lamp (function) [and on the light source technology used] the luminous intensity distribution is . additionally checked for compliance* at the...
  • Chapter 7 Consciousness - MCCC

    Chapter 7 Consciousness - MCCC

    In an average night's sleep - we go through about 5 sleep cycles The cycles continue throughout the night - stages 3 and 4 get shorter as the night progresses while REM and stage 2 gets longer * * *...
  • Human Factors in Traffic Safety Fall 2019 Important

    Human Factors in Traffic Safety Fall 2019 Important

    Risk Taking Behavior. Objective versus subjective risk. Sensation seeking (SS) individuals: relationship not established SS and risky driving. Risk homeostasis theory. Social Factors. Drivers are influenced by other drivers "culture of driving" Drivers are also influenced by passengers (family members...
  • Lecture #1 - Ira A. Fulton College of Engineering and Technology

    Lecture #1 - Ira A. Fulton College of Engineering and Technology

    Lab Lectures Preparation for ECEn 320 Lab Exercises Suggestions for a Productive Lab Experience Design Start early, come to lab prepared. Understand the assignment before you begin to code VHDL Design from your drawings-- have your block diagram in front...
  • RON: Resilient Overlay Networks

    RON: Resilient Overlay Networks

    RON: Resilient Overlay Networks David Andersen, Hari Balakrishnan, ... network of networks ISPs peer to forward packets ISP exchange route info using BGP The Internet is ill suited to mission-critical applications Commercial peer architecture Performance bottlenecks at peering points Ignores...