3.2.1 Jacobson's Algorithm: Step-by-Step

This algorithm calculates the Retransmission Timeout (RTO) by tracking mean RTT and variance.

Algorithmic Implementation:

#define G 0.125  // 1/8
#define H 0.25   // 1/4

void update_rto(TCP_Timer *t, double sample_rtt) {
    double error = sample_rtt - t->srtt;
    
    // Update Smoothed RTT (SRTT)
    t->srtt = t->srtt + G * error;
    
    // Update Mean Deviation (MDEV)
    t->mdev = t->mdev + H * (abs(error) - t->mdev);
    
    // Calculate Final RTO
    t->rto = t->srtt + 4 * t->mdev;
    
    // Bounds checking
    if (t->rto < 1000) t->rto = 1000; // Min 1s
    if (t->rto > 64000) t->rto = 64000; // Max 64s
}

3.2.2 Case Study: Jitter Handling

3.2.3 Karn's Algorithm Protocol

To solve Retransmission Ambiguity:

1. Condition: If a packet was retransmitted, IGNORE its ACK for RTT estimation.
2. Backoff: For every retransmission, $RTO = RTO imes 2$.
3. Reset: Only set $RTO$ back to the Jacobson value when a packet succeeds on the first attempt.

Karn's Logic Flow:

void send_packet(Packet *p) {
    p->sent_count++;
    if (p->sent_count > 1) {
        current_rto *= 2; // Binary Exponential Backoff
    }
    start_timer(p, current_rto);
}

void on_ack(Packet *p) {
    if (p->sent_count == 1) {
        update_jacobson_stats(p->rtt);
    } else {
        // Rule 1: Ignores sample
        // Rule 3: Maintain current_rto (don't reset yet)
    }
}

3.2.4 Microsecond Timers in Gigabit Networks

At 100Gbps, a single packet takes $approx 12ns$. Linux kernels use Tickless modes with CPU cycle counters (RDTSC) to achieve $1 mu s$ resolution for the Jacobson state machine.