Week 6

TCP Receiver Event/ACK Generation

Event at Receiver

1. Arrival of in-order segment with expected sequence #:

   • All data up to expected sequence number has already been acknowledged.

2. Arrival of in-order segment with expected sequence #:

   • One other segment has an ACK pending.

3. Arrival of out-of-order segment with a higher-than-expected sequence #:

   • A gap is detected in the sequence numbering.

4. Arrival of segment that partially or completely fills the gap.

TCP Receiver Actions

1. Delayed ACK:

   • Waits up to 500 ms for the next segment to arrive.

   • If no segment arrives, an ACK is sent immediately.

2. Immediately send cumulative ACK:

   • Acknowledges all in-order segments received so far.

3. Immediately send duplicate ACK:

   • This indicates the sequence number of the next expected byte.

4. Immediate ACK for segments that start at the lower end of a gap:

   • This is valid if the segment begins from the next byte expected.

Receiver Buffer

• Accept packets within the receiver window of 212 bytes.

TCP Congestion Control

Congestion Detection

• Congestion is detected via a "loss event," which can be defined as:

  1. A timeout.

  2. Three duplicate ACKs.

Rate Adjustment

• The TCP sender reduces the transmission rate (congestion window) after detecting a loss event.

• Rate adjustment methods include:

  • Slow Start: Gradually increasing the congestion window to discover the proper sending rate.

  • Congestion Avoidance: Utilizing the Additive Increase Multiplicative Decrease (AIMD) model, adjusting conservatively after timeout events.

• Note: Packet loss is associated with congestion.

Congestion Window (cwnd)

Definition

• The congestion window limits how much data can be in transit.

Computation

• Effective Window (EffectiveWindow):
  $ext{EffectiveWindow} = ext{MaxWindow} - ( ext{LastByteSent} - ext{LastByteAcked})$

• MaxWindow:
  $ext{MaxWindow} = ext{min}( ext{cwnd}, ext{rwnd})$

• Last sent and acknowledged sequence numbers:

  • LastByteAcked: The sequence number of the last acknowledged byte.

  • LastByteSent: The sequence number of the last byte sent by the sender.

Bandwidth Measurement

• Monitor the effective rate of transmission:

  • $ext{Effective Rate} = ext{min(rwnd,cwnd)}/ ext{RTT}$

  • Measured in bytes/sec.

Self-Clocking

• In conditions where a large window is in effect, ACKs self-clock the data transfer rate according to the bottleneck link's capabilities.

• Observation:

  • The spacing of received ACKs is determined by the bandwidth of the bottleneck.

TCP: Slow Start

Objective

• Discover the appropriate sending rate rapidly during the initiation of traffic on a new connection or after a congestion event (like a timeout).

Mechanism

• Initial Congestion Window (cwnd):

  • Set to $1 ext{ MSS}$ (Maximum Segment Size).

• Increment cwnd:

  • Increase by 1 MSS for each acknowledged segment.

• Continue until reaching the slow-start threshold (ss_thresh).

• Packet loss detection: Causes slow down in congestion increases.

Slow Start Illustration

• The congestion window (cwnd) size grows rapidly:

  • It doubles with each received ACK until reaching a threshold (ss_thresh).

  • Example Sequence:

    • $ext{cwnd} = 1 ext{ MSS}$, then $ext{cwnd} = 2 ext{ MSS}$, then $ext{cwnd} = 4 ext{ MSS}$, escalating quickly with every acknowledged segment received.

Congestion Avoidance (After Slow Start)

• Trial and error methodology continues to react to the changing network conditions.

• Aims to probe for additional bandwidth while aggressively cutting back the congestion window (cwnd) if congestion is detected.

TCP Multiplicative Decrease & Additive Increase (AIMD)

Mechanism

• Multiplicative Decrease:

  • Cuts the cwnd in half after a loss event.

• Additive Increase:

  • Increases the cwnd by 1 MSS for each round-trip time (RTT) without losses.

Reason for AIMD

• Ensures that multiple TCP connections share bandwidth fairly.

  • In context: Two competing sessions utilizing the Additive Increase (AI) method yield a slope of 1 for the increase, while the Multiplicative Decrease (MD) halves the available throughput to appropriately handle congestion events, fostering fair use of bandwidth across sessions.

AIMD Example 221

• Provided as graphical representation demonstrating two connections each trying to utilize network bandwidth optimally.

AIMD Sharing Dynamics

Observations

• No congestion results in rates increasing one packet/RTT for every RTT, while in congestion, the rate decreases by a factor of 2, ensuring fair share utilization of bandwidth.

Example of Slow Start + Congestion Avoidance

Illustration

• An illustrative timeline of the growth of the congestion window illustrates how it responds to conditions:

  • Values represented in terms of MSS (max segment size):

  • Example:

    • $cwnd = 1$, then $cwnd = 2$, continuing to increase until the threshold or loss is detected.

Responses to Congestion (Loss)

Algorithms

• Algorithms developed for TCP responses include:

  • TCP Tahoe

  • TCP Reno

  • TCP Vegas: Research-focused on utilizing timing of ACKs to prevent loss.

  • TCP SACK: Future developments involving selective ACK.

TCP Reno

Characteristics

• Upon timeout:

  • ss_thresh is cut in half, and cwnd is set to 1MSS, leading exiting to slow start phase.

• Implements fast retransmit and fast recovery upon receiving three duplicate ACKs, allowing retransmission of the presumed lost segment without entering slow start again.

Fast Recovery

Overview

• Following a fast retransmit, the cwnd is adjusted as such:

  • $ext{cwnd} = ext{cwnd}/2$, starting congestion avoidance at this new cwnd rather than reverting to 1MSS as in Tahoe logic.

• After a timeout:

  • Sets ss_thresh = cwnd/2 and cwnd = 1MSS, leading again back to slow start mode.

Fast Retransmit and Fast Recovery

• Slow Start is typically employed only once per session, concerning it strictly if no timeouts occur.

• In a steady theoretical state, the cwnd oscillates around the ideal window size derived from conditions, illustrating TCP's overarching control strategy.

Summary of TCP Event Responses (1)

• Overview of states and actions corresponding to TCP responses, detailing transitions between slow start and congestion avoidance.

Summary of TCP Concepts (2)

Key Areas

1. Multiplexing and demultiplexing.

2. Error detection and recovery: Utilize Internet checksum (including pseudo-headers).

3. Flow Control, Congestion Control, and Transmission Efficiency via sliding windows and AIMD mechanisms.

4. Distinguish between various algorithms and protocols related to TCP mechanisms.

Outline of Network Layer Functions

• Sending segments from host to host, encompassing both encapsulation into datagrams and delivery to the transport layer within router architectures.

• Critical examinations include forwarding table methodologies, IP protocols, and connection management concepts.

IPv4 Addressing

Definition

• Unique 32-bit number relevant to a host or router interface, typically represented using dotted-quad notation (e.g., 200.23.16.5).

• Router interfaces generally feature multiple connections, facilitating clear delineation of access points in the networking landscape.