TCP Protocol

Try to combine Transport Layer#Go Back N (GBN) and Transport Layer#Selective ACK (SACK)
$\to$ Cumulative ACK and receiver buffering

Slow Start

• Every time a new ACK comes back, increase window size by 1
• $W$ is doubled every RTT (exponential)
• Goes until Slow Start Threshold ($SST$)

Congestion Avoidance

• Slow down the rate of increasing $W$ after Slow Start Threshold $SST$
• $C{W}^{\text{new}}=C{W}^{\text{old}}+1/\lfloor C{W}^{\text{old}}\rfloor$
• When packet loss happens, reset $CW=1$

Fast Recovery

• Quickly recover from DupACKs
• $SST=\lfloor \frac{CW}{2}\rfloor$
  $CW=SST$
  $CW=CW+3$

In summary, the TCP protocol goes from exponential first then linear

TCP State Diagram

TCP Saw-Tooth Behavior

Average TCP Throughput $=(\frac{N}{\text{RTT}}+\frac{N/2}{RTT})/2=0.75\frac{N}{RTT}$
where $N=RTT/maxTT$

TCP Timeout Management

TCP has a single timer to keep track of all timeouts

• ${\tau }_{\text{new}}=(\text{Alarm time}-\text{Current ACK time})+\mathrm{\Delta }(T_{\text{next}}-T_{\text{current}})$
• Update alarm duration to be ${\tau }_{\text{new}}$

RTO Estimation
Exponential Weighted Moving Average (EWMA)

RTO can be estimated as a function of the historical RTT + a safety function

• $RTO(t)=\text{Estimated RTT }\hat{R}(t)+4\cdot \text{Deviation of RTT }\hat{\mathrm{\Delta }}(t)$
  • $\text{Estimated RTT }\hat{R}(t)\propto \hat{R}(t-1)+(1-\alpha )m(t)$
    • $m(t)$ is the current RTT
    • $\alpha =0.8$
  • $\text{Deviation of RTT }\hat{\mathrm{\Delta }}(t)\propto \alpha \hat{\mathrm{\Delta }}(t-1)+(1-\alpha )(\hat{R}(t)-m(t))$
• 
• When estimating $\hat{R}(t)$ ignore dupACKs, and any stale ACKs that is left of $T_x$'s window base

Large $RTO$ means large $CW$
Large $RTO\to$ the network will get congested and transmitter will react slowly
Small $RTO\to$ network utilization is low since transmitter (SST) will react too quickly, even before the network get too congested

Packets to Bytes

TCP operates as a byte stream
uses MSS (maximum segment size) to separate segments of packets

TCP Flow Control

• Receiver buffer may fill up really fast
• Receiver $R_x$ TCP includes how much space is available in its socket buffer $B$ bytes (ACK includes this value)
• When $T_x$ TCP gets ACK, it decides to send $min\{B,CW\}$
  • $CW$ does not change, $CW$ keeps following the protocol

    This is because the receiver buffer could drain quickly, because the OS could switch thread and quickly handle the packets on terminal

TCP Fairness

Between TCP and UDP
UDP doesn't control congestion, so TCP would always cuts back (TCP being polite), the channel allocation is not fair

Between TCP and TCP

TCP Random Early Drop

Hack/Workaround for the network layer to give feedback to TCP about its queue size/congestion.
Network layer drops a random data packet from each flow, so that the router queue does not fill up above some threshold (say 60%).

TCP over Wireless

Bit Error Rate (BER) is the probability that bit will flip

• Wireless: ${10}^{-5}\to \frac{1}{100}$ packets corrupt (1 bit error every ${10}^5$ bits)
• Wired: ${10}^{-12}\to \frac{1}{\text{million}}$ packets corrupt

TCP must differentiate between wireless losses and congestion losses (at router) because

• If congestion loss then reduce $CW$
• Else if wireless loss then simply retransmit and don't change $CW$

TCP performs bad on wireless

• Retransmits congests the links
• TCP keeps going into congestion control

Solutions:
(Both violates the layer principles)

• Split TCP
• TCP snoop
  • Link layer is snooping into TCP header so that it can retransmit lost packets