Controle de Congestionamento

Modulo 3 · Aula 3 ~20 min de leitura Nivel: Intermediario

Video da aula estara disponivel em breve

Controle de fluxo vs. controle de congestionamento

Controle de fluxo protege o receptor de ser sobrecarregado. Controle de congestionamento protege a rede de ser sobrecarregada. São mecanismos diferentes que coexistem no TCP — a janela efetiva de envio é sempre o mínimo entre as duas.

Diagrama

Controle de fluxo:            Controle de congestionamento:
  Remetente <--> Receptor       Remetente <--> Rede
  "Nao envie mais rapido        "Nao envie mais rapido
   do que EU consigo ler"        do que a REDE aguenta"

  Mecanismo: rwnd (receiver     Mecanismo: cwnd (congestion
  window) anunciada pelo         window) estimada pelo
  receptor no header TCP         remetente

  Janela efetiva = min(rwnd, cwnd)

AIMD: Additive Increase, Multiplicative Decrease

O princípio fundamental do controle de congestionamento TCP é o AIMD. É matematicamente provado que AIMD converge para uma alocação justa (fair) de bandwidth entre múltiplos fluxos TCP compartilhando o mesmo link:

Additive Increase: enquanto não há congestionamento, aumenta a janela (cwnd) linearmente — +1 MSS por RTT
Multiplicative Decrease: quando detecta congestionamento (perda de pacote), reduz cwnd pela metade

Por que AIMD e não AIAD? Se ambos os fluxos reduzissem aditivamente (AIAD), a diferença entre eles nunca diminuiria — fluxos injustos permaneceriam injustos. Com redução multiplicativa, a diferença entre fluxos converge para zero ao longo do tempo. Esta é a propriedade de fairness do AIMD.

Diagrama

cwnd
  ^
  |         /\
  |        /  \        /\
  |       /    \      /  \        /\
  |      /      \    /    \      /  \
  |     /        \  /      \    /    \
  |    /          \/        \  /      \
  |   /                      \/        \
  |  /
  | /
  +──────────────────────────────────────> tempo

  /  = additive increase (linear, +1 por RTT)
  \  = multiplicative decrease (cwnd /= 2 em perda)

  O padrao "dente de serra" e a assinatura visual do AIMD.

Fases do controle de congestionamento TCP

1. Slow Start (inicio lento)

Comeca com cwnd = 1 MSS e dobra a cada RTT (crescimento exponencial). Continua ate atingir o ssthresh (slow start threshold).

2. Congestion Avoidance (evitar congestionamento)

Apos atingir ssthresh, o crescimento muda para linear (+1 MSS por RTT). E a fase "additive increase" do AIMD.

3. Deteccao de perda

Timeout: perda grave. cwnd volta a 1 MSS, ssthresh = cwnd/2. Reinicia slow start.
3 ACKs duplicados: perda leve (fast retransmit). cwnd /= 2, ssthresh = cwnd. Vai para congestion avoidance.

Diagrama

cwnd
  ^
  |                              ssthresh
  |                        .......:....
  |                  .....´       :   \
  |              ...´             :    \  3 dup ACKs
  |          ...´                 :     \  (cwnd /= 2)
  |       ..´                    :      |
  |    ..´                       :     /  Congestion
  |  .´  Slow Start              :    /   Avoidance
  | ´    (exponencial)           :   /    (linear)
  |´                             :  /
  +──────────────────────────────:──────> tempo
                                 ^
                            ssthresh

TCP Reno vs. TCP Cubic

Referencia

TCP Reno (classico):
  - Slow start + AIMD
  - Apos 3 dup ACKs: cwnd /= 2 (fast recovery)
  - Apos timeout: cwnd = 1 MSS
  - Recuperacao lenta em links de alta capacidade

TCP Cubic (padrao do Linux desde 2006):
  - Funcao cubica em vez de linear para cwnd
  - Mais agressivo em descobrir capacidade disponivel
  - Melhor em links de alta largura de banda e alta latencia (BDP grande)
  - W(t) = C * (t - K)^3 + Wmax
    onde K = (Wmax * B / C)^(1/3), B = fator de reducao

TCP BBR (Google, 2016):
  - Model-based: estima bandwidth e RTT da rede
  - Nao usa packet loss como sinal de congestionamento
  - Melhor performance em links com buffer bloat

Python

def simulate_tcp_reno(bandwidth_mss, loss_events, total_rtts=50):
    """Simula controle de congestionamento TCP Reno.
    bandwidth_mss: capacidade do link em MSS
    loss_events: lista de RTTs onde ocorre perda"""

    cwnd = 1            # Janela de congestionamento (em MSS)
    ssthresh = 64       # Slow start threshold
    phase = "slow_start"
    history = []

    for rtt in range(total_rtts):
        if rtt in loss_events:
            # Perda detectada: multiplicative decrease
            ssthresh = max(cwnd // 2, 2)
            cwnd = ssthresh      # Fast recovery (3 dup ACKs)
            phase = "cong_avoid"
        elif phase == "slow_start":
            cwnd *= 2            # Crescimento exponencial
            if cwnd >= ssthresh:
                phase = "cong_avoid"
        else:
            cwnd += 1            # Crescimento linear

        cwnd = min(cwnd, bandwidth_mss)
        history.append((rtt, cwnd, phase))
        print(f"RTT {rtt:3d}: cwnd={cwnd:3d} MSS  ssthresh={ssthresh:3d}  [{phase}]")

    return history

# Simula: link de 100 MSS, perdas nos RTTs 20 e 35
simulate_tcp_reno(100, loss_events=[20, 35], total_rtts=45)

Fairness e Bandwidth-Delay Product

O BDP (Bandwidth-Delay Product) é a quantidade de dados "em trânsito" no link — o produto da capacidade do link pelo RTT. Para máxima utilização, a janela de congestionamento deve ser igual ao BDP:

Diagrama

BDP = Bandwidth × RTT

Exemplo:
  Link de 100 Mbps, RTT de 50 ms
  BDP = 100 × 10^6 × 50 × 10^-3 = 5.000.000 bits = 625 KB

  Para utilizar 100% do link, cwnd deve ser >= 625 KB
  Em MSS de 1460 bytes: cwnd >= 428 MSS

Fairness (índice de Jain):
  Se N fluxos compartilham um link de capacidade C,
  cada um deveria receber C/N.

  Índice de Jain = (Σxi)² / (N × Σxi²)
  = 1.0 → perfeita fairness
  = 1/N → máxima injustiça

  AIMD garante convergência para fairness = 1.0
  ao longo do tempo (prova matemática).

Bufferbloat

Bufferbloat ocorre quando buffers excessivamente grandes em roteadores aumentam a latencia sem melhorar o throughput. Pacotes ficam parados em filas gigantes em vez de serem descartados (o que sinalizaria congestionamento ao TCP).

Paradoxo do buffer Buffers maiores previnem perda de pacotes, mas causam latencia enorme. Buffers menores mantêm latencia baixa, mas podem causar mais perdas. A solucao moderna e Active Queue Management (AQM) — algoritmos como CoDel que descartam pacotes antes do buffer encher.

No harness.os

Diagrama

Controle de Congestionamento TCP    Analogia harness.os
──────────────────────────────     ──────────────────────────────────
cwnd (congestion window)            Token budget por sessao
ssthresh                            Limite antes de reduzir agentes
Slow start                         Sessao comeca com poucos agentes
Congestion avoidance                Cresce linearmente o paralelismo
Packet loss = congestion signal     Token budget esgotado = signal
AIMD                                Adiciona agentes gradualmente,
                                    reduz pela metade se budget estoura

Cenario concreto:
  Orchestrator spawna 1 agente (slow start)
  Agente completa rapido? Spawna 2 (exponencial)
  2 completam? Spawna 4
  Atingiu ssthresh (ex: 4 agentes)? Cresce +1 por vez
  Budget estourou? Reduz para 2 agentes (multiplicative decrease)
  Token timeout? Volta a 1 agente (reset)

Backpressure:
  Muitos agentes concorrentes --> Neon connection pool saturado
  --> Queries ficam em fila (bufferbloat!)
  --> Aumenta latencia de todas as sessoes
  --> Solucao: limitar agentes concorrentes (cwnd para agentes)

Resumo

Controle de congestionamento protege a rede; controle de fluxo protege o receptor
AIMD: cresce linear, diminui pela metade — garante convergência justa entre fluxos (prova matemática)
Slow start: crescimento exponencial até ssthresh
Congestion avoidance: crescimento linear após ssthresh
BDP (Bandwidth-Delay Product): cwnd deve ser >= BDP para utilização máxima do link
TCP Cubic (Linux default) é mais eficiente que Reno em links de alto BDP
Bufferbloat: buffers grandes aumentam latência sem melhorar throughput — AQM (CoDel) é a solução

Homework

Exercício 1: Projete um mecanismo de controle de congestionamento para orchestração de agentes harness.os.

Defina o equivalente de cwnd (quantos agentes em paralelo)
Defina o sinal de congestionamento (timeout? token budget esgotado? erro de Neon?)
Implemente AIMD: como cresce o número de agentes? Como reduz?
Simule: 10 tasks, budget de 100K tokens. Quantos agentes em paralelo é ótimo?

Exercício 2: Use a função simulate_tcp_reno() para simular um link de 200 MSS com perdas nos RTTs 15, 30 e 45. Trace o gráfico cwnd vs RTT e identifique as fases (slow start, congestion avoidance, fast recovery).

Exercício 3: Calcule o BDP para três cenários: (a) Wi-Fi doméstico (50 Mbps, RTT 5ms), (b) link intercontinental (1 Gbps, RTT 100ms), (c) link satelital (10 Mbps, RTT 600ms). Em qual cenário TCP Reno tem mais dificuldade? Por quê?

Exercício 4: Pesquise TCP BBR do Google. Compare com TCP Cubic em termos de: como detecta congestionamento, como estima bandwidth disponível, e em quais cenários BBR tem vantagem.

Verifique seu entendimento

No AIMD, o que acontece quando o TCP detecta congestionamento via 3 ACKs duplicados?

cwnd volta a 1 MSS e reinicia slow start
cwnd e reduzida pela metade e entra em congestion avoidance
cwnd dobra para tentar superar o congestionamento
A conexao TCP e encerrada e reaberta

Verifique seu entendimento

Um link tem bandwidth de 1 Gbps e RTT de 100ms. Qual é o BDP e quantos MSS (1460 bytes) a janela precisa ter para utilização máxima?

BDP = 100 KB, cwnd = 68 MSS
BDP = 1 MB, cwnd = 685 MSS
BDP = 12.5 MB (1 Gbps × 100ms = 100 Mbits = 12.5 MB), cwnd ~ 8562 MSS
BDP = 100 Gbps, cwnd = 1 MSS

Verifique seu entendimento

Por que AIMD garante fairness entre múltiplos fluxos TCP, enquanto AIAD (Additive Increase, Additive Decrease) não garante?

AIMD é mais rápido que AIAD
Redução multiplicativa diminui proporcionalmente — quem usa mais perde mais, convergindo as taxas; redução aditiva mantém a diferença constante
AIAD não funciona com TCP, apenas com UDP
Não há diferença — ambos garantem fairness

Aula anterior 3.2 TCP Proxima aula 4.1 IP e Enderecamento