For full text search please use the '?' prefix. e.g. ? Onboarding

Tcp

TCP

  • point-to-point / reliable / in-order byte stream / pipelined: sliding windows
  • full duplex data: bi-directional data flow
  • connection-oriented: handshaking (exchange of control messages) initializes sender & receiver state before data exchange
  • Both sides have buffers
  • Flow Control
  • Congestion Control

connection and tear down

  • establish: setup state before exchanging data segements
    • step1: send SYN segment and specifies initial seq#, no data
    • why random sn? an earlier incarnation of the same connection can interfere with a later one
    • step2: server respond with SYNACK segment, allocates buffers and specifies initial seq#
    • step3: replies with ACK, may contain data
    • if host receive with SYN to a closed port, responds with a RST segments
  • teardown: free up state
    • step1: send TCP FIN to server
    • step2: server responds with ACK and closed, send FIN
    • step3: client receives FIN, replies with ACK , wait
    • why? possible ACK lost
    • Client may open the same connection again (same pair of port #s (Private))
    • then Receives FIN from earlier incarnation of connection
    • so Immediately initiate closing of the later incarnation
    • Step 4: server receives ACK, closes connection

RDT

  • TCP creates RDT service on top of IP’s unreliable service
    • Pipelined segments
    • Cumulative acks
    • Retransmission timer
  • Retransmissions are triggered by:
    • timeout events
    • duplicate acks
  • Initially, we consider simplified TCP sender:
    • ignore duplicate acks
    • ignore flow control, congestion control
    • assume RTT is estimated somehow
  • SN : byte stream “number” of first byte in segment’s data
  • ACKs: seq # of next byte expected from other side
    • cumulative ACK: acknowledges bytes up to the first missing byte in the stream
  • Data received from app:
    • Create segment
    • seq# is byte-stream number of first data byte in segment
    • Send, if allowed by congestion & flow-control
    • start timer if not already running (think of timer as for oldest unacked segment)
    • expiration interval: TimeOutInterva
  • Timeout:
  • retransmit segment that caused timeout
  • restart timer
  • ACK received:
    • If acknowledges previously unACKed segments
    • update what is known to be ACKed
    • start timer if there are outstanding segments
  • fast retransmit
    • If segment is lost, there will likely be many duplicate ACKs
    • If sender receives 3 duplicate ACKs, it supposes that segment after ACKed data was lost: resend segment before timer expires： voodoo constant

From Reliable_data_transfer
Go to text →

RDT

possible failure

bit-errors, lossy, duplicate delivery , out-of-order delivery

methods

  • checksums: bit error
  • receiver feedback: bit error, ACK/NACK， Cumulative acknowledgments(I have received all packets with sequence numbers up to but not including sn.) allow acknowledgment of numerous packets at a time. They can be useful in pipelined protocols. 可能lost
  • retransmission : Sender sends another copy of segment, detect loss and allows for duplicate seg
  • sequence numbers : Distinguish between old and new, Gaps let receiver detect lost segment, find duplicate packets，restoring the transmitted order. have to be a bounded # bits
  • timer expiration: Segment or receiver feedback is lost (sender: Resends a packet after a timer fires. Sends a new packet after an acknowledgment (positive) arrives.)
  • window:Control sending of multiple segments, allow for reuse of sequence numbers, also allow for pipeling segments

protocols

Stop-n-Wait

  • Simplest Protocol that will handle bit errors and segment loss
    • use: checksum, ack, sn, timers
    • 1 bit for sequence number
    • 为了解决checksum返回的时候有问题。可能ack会lost。带来的问题就是可能重复发几次。所以需要seq num
    • 计时发送，看指定时间能否达到response, 没seq num. 接收者不能知道是否是重发。LOST ACK和lost segment对于发送方式一样的

Go Back N

  • sliding window: A mechanism to control multiple, in-flight segments without overwhelming receiver, Sender is allowed to transmit N segments without waiting for an ACK
  • “window” of up to N, consecutive unACKed segments allowed
  • Sets a timer for each in-flight segment
  • timeout(n): retransmit segment n and all higher seq# segments in window
  • sender:
    • Sender places a k-bit seq# in header
    • “window” of up to N, consecutive unACKed segments allowed
    • Sets a timer for each in-flight segment
    • timeout(n): retransmit segment n and all higher seq# segments in window
    • ACK(n): ACKs all segments up to, including seq# n (Cumulative ACK)
  • receiver: ACK-only: always send ACK for correctly-received segment with highest in-order seq, Receipt of out-of-order segment just discard and send with highest in-order seq
    • May generate duplicate ACKs
    • Why discard segs received out-of-order： Don’t want to buffer them, going to be re-sent anyway
  • A single segment error can cause many segments to be retransmitted

Selective Repeat

  • Receiver individually ACKs all correctly received segments
  • Buffers segs for eventual in-order delivery
  • Sender only resends segments for which ACK not received
  • Sets timer for each segment
  • Sender window of N consecutive seq#s
  • Limits seq # s of sent, but unACKed segs
  • issues: both side have varying view, receiver window移动了，但是发送端没收到ack， 会重传。
  • sequence number的space至少是2^k 个，k是window的大小

Flow control

  • mission: Sender won’t overflow the receiver’s buffer by transmitting too much, too fast

    • matching the send rate to the receiving app’s drain rate
    • operation:

  • mechanism

    • RcvWindow = RcvBuffer - [ LastByteRcvd - LastByteRead ] (assume discard out of order)
    • Receiver advertises spare room by including value of RcvWindow in ACK segment
    • Gives sender permission to send this much

  • congwin: how much data allowed in-flight at any time, >= LastByteSent-LastByteAcked

    • rate = congwin/RTT

  • sender perceive congestion: timeout / 3 duplicate ACKs

  • self-clocking nature: use ACK to trigger its increase in congestion window size

  • interaction of various phases

    • When CongWin is below Threshold, window grows exponentially (slow-start phase)
    • When CongWin is above Threshold, window grows linearly (congestion-avoidance phase)
    • When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold. Window grows linearly
    • When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS. Enters slow-start phase

  • slow start

    • start with MSS = 1, increase exponentially, done by increasing CongWin by 1MSS for every ACK received
    • With Slow Start, no bandwidth wasted on retransmission
    • end: first lost event

  • congestion avoidance

    • start: first lost event
      • cut CongWin in half after a loss event
      • Continue probing for usable bandwidth
    • Reno: after 3 dup, cancel slow start, cut half CongWin, grows linearly
      • after timeout, set ssthrehold to half, skip ss, fast recovery.
      • fast retransmit: after 3 dup
    • Tahoe: after loss event, congwin set to 1, enter slow start

  • how TCP sets timeout values.

    • longer than RTT.
    • too short, premature timeout, unnecessary retransmissions
    • too long, slow reaction to segment loss
    • need to measure RTT for baseline