TCP - Suporte UFRJ

Transmission Control Protocol
(TCP)
TCP
Serviço orientado a conexão
Baseado em fluxo (stream):
– Seqüência de bytes não estruturada
Confiável
Detecção e correção de erros
Controle de fluxo
Controle de congestionamento
TCP
Segmentos
– Fluxo de dados tratado como uma seqüência de
bytes divididos em segmentos
– Cada segmento é encapsulado dentro de um
datagrama IP
– Tamanho máximo do segmento: MSS
Números de Seqüência
– Bytes no fluxo de dados são numerados
seqüencialmente
TCP
Confiabilidade
– Reconhecimento Positivo (ACK) com
Retransmissão
– Utiliza Piggybacking no reconhecimento
– Retransmissão baseada em time-out
Comportamento do TCP
Usa o conceito de janela deslizante
Sempre que um pacote é recebido no destino, um
ACK é retornado, confirmando os bytes recebidos
corretamente e em seqüência
– ACK carrega a indicação do próximo byte esperado
Sempre tenta incrementar a banda ofertada,
aumentando o tamanho da janela de transmissão à
medida que recebe confirmações (ACKs)
– Controle de Fluxo
– Controle de Congestionamento
Seqüenciamento e ACKs
Funcionamento do TCP
Sempre que um pacote é transmitido, um time-out é
disparado
Quando ACK do pacote chega, time-out é cancelado
Quando um pacote é perdido, mas os pacotes
subseqüentes chegam ao destino, ACKs de mesmo
valor são gerados e recebidos como ACK duplicados
A chegada de três ACKs duplicados força a retx do
pacote perdido, cancelando o estouro do time-out
(Fast Retransmit)
Cenários de retransmissão
ACK 120
ACK 120 dup
Perda do ACK e
retx por time-out
Temporização prematura,
ACK duplicado
Cenários de retransmissão
ACK cumulativo
Fast Retransmit
Host A
Send Seg 1
Send Seg 2
Start Timer
Send Seg 3
Send Seg 4
Receive ACK 2
Send Seg 5
Receive ACK 2 Dup #1
Receive ACK 2 Dup #2
Host B
Receive Seg 1
Send ACK 2
Receive Seg 3
Send ACK 2
Receive Seg 4
Send ACK 2
Receive Seg 5
Send ACK 2
Receive ACK 2 Dup #3
Retx Seg 2
Cancel timer
Receive Seg 2
Send ACK 6
Receive ACK 6
Send Seg 6
Controle de Fluxo
• lado receptor da conexão TCP possui um buffer de recepção
processos de aplicação
podem ser lentos para ler
o buffer
Controle de fluxo
• Transmissor não deve
esgotar os buffers de
recepção enviando dados
rápido demais
• Serviço de speed-matching:
encontra a taxa de envio
adequada à taxa de vazão da
aplicação receptora
Controle de Fluxo: como funciona
RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead]
RcvWindow informado nos segmentos enviados pelo receptor
Transmissor limita os dados não confirmados ao RcvWindow
– Garantia contra overflow no buffer do receptor
Parâmetros de Controle do TCP
Controle de fluxo
– Advertised Receiver Window Size (rcvwnd)
Enviado nos segmentos gerados pelo receptor para o
transmissor (ACK ou dados)
Indica a quantidade máxima de bytes que o receptor
ainda pode receber (disponibilidade de buffers na
recepção)
O transmissor não deve nunca transmitir bytes não
confirmados acima deste valor, exceto dados urgentes
Detecção de Congestionamento
Assume que pacotes são raramente corrompidos por
erros e sempre que uma perda ocorre, o TCP
assume isso como indício de congestionamento
Congestionamento é detectado por time-out ou
recepção de acks duplicados
Usa mecanismo de feedback, reduzindo a janela de
transmissão face a indícios de congestionamento
Reação a Perda
A perda eventual de um pacote, sentida pela
recepção de três ACKs duplicados, força a
retransmissão antecipada do pacote e redução da
oferta de tráfego à metade
O estouro de um time-out indica um forte
congestionamento (perda de pacotes em rajada) e
força a conexão TCP a reiniciar com oferta de banda
mínima e retx do pacote
Parâmetros de Controle do TCP
Controle de transmissão
– Congestion window (cwnd)
Janela que indica os bytes que podem ser transmitidos
– Threshold
Parâmetro que afeta crescimento de cwnd
Controle do TCP
Janelas e ACKs referenciados em termos de bytes e
usam unidades do tamanho máximo de segmento
– Maximum segment size (MSS)
MSS limitado pelo MTU (maximum transmission unit)
para evitar fragmentação
– Procedimentos de MTU discovery
Em qualquer instante, a janela de transmissão
(txwnd) = mín {rcvwnd, cwnd}
Inicialização
Advertised Receiver Window Size (rcvwnd)
Limitada pelo buffer de recepção no destino
Valor inicial Informado na abertura da conexão TCP
(SYN)
Congestion window (cwnd)
Inicializada com 1 (MSS bytes)
Threshold
Inicializado em 65535 bytes
Estados de Operação do TCP
Slow Start
Congestion Avoidance
Slow Start e Congestion
Avoidance
Slow Start
– Inicia com cwnd =1 (MSS)
– Incrementa cwnd de 1 MSS a cada ack recebido, ou seja, duplica a
cada RTT, crescendo exponencialmente até alcançar threshold, e
entrando em congestion avoidance
– Em slow start, temos cwnd < threshold
cwnd
threshold 8
4
2
1
RTT
2RTT
3RTT
4RTT
5RTT
6RTT
7RTT tempo
Slow Start (Partida Lenta)
hospedeiro A
RTT
Cnwd = 1
Cnwd = 2
hospedeiro B
um segme
nto
RTT
dois segm
entos
Cnwd = 3
Cnwd = 4
quatro seg
mentos
tempo
Slow Start e Congestion
Avoidance
Congestion Avoidance
– A partir daí aumenta linearmente, incrementando de 1 (MSS) a cada
RTT, ou seja, ao receber um ack incrementa cwnd de 1/cnwd
Incremento de cwnd pode não ser suficiente para permitir o envio de um
pacote naquele instante
– Em congestion avoidance, cwnd ≥ threshold
cwnd
12
11
10
9
threshold 8
4
2
1
RTT
2RTT
3RTT
4RTT
5RTT
6RTT
7RTT tempo
Comportamento do TCP
Vazão ocorre em dente de serra
três acks
duplicados
Congestion
window
Kbytes
Time-out
threshold
threshold
threshold
threshold
slow
start
Referência
threshold
congestion
avoidance
slow
start
tempo
congestion
avoidance
– RFC2001, TCP Slow Start, Congestion Avoidance, Fast
Retransmit, and Fast Recovery Algorithms, Janeiro 1997
Comportamento do TCP
Vazão num dado instante = txwnd/ RTT
Quando ocorre perda com redução da janela de
transmissão, threshold é sempre colocado na metade do
valor da janela que existia antes da deteção da perda
– No caso de ack duplicado, nova janela é metade da anterior, ou
seja, reinicia com valor igual ao threshold e entra-se em congestion
avoidance (cwnd ≥ threshold)
– No caso de time-out, nova janela é colocada em 1 MSS e entra-se
em slow start
Threshold inicial: 65535 bytes
Vazão Inicial
Slow start inicial e assuma RTT = 100 ms
Ao final do slow start, se não houvesse perda, o TCP
atingiria uma vazão de 64 kbytes/100 ms = 5 Mbps
Este ponto seria atingido em 6 RTTs ou 1,6 s de
transmissão
Esta é a meta inicial de oferta de tráfego do TCP
Na Internet, dificilmente se consegue esta taxa de
tráfego
Congestionamento em
Roteadores
Comportamento Internet: o tráfego nos roteadores
chega em rajadas
Na falta de buffers e com fila FIFO no roteador,
descarte simultâneo ocorre em conexões TCP
compartilhando o gargalo
Conseqüências:ocorre sincronização global
– As sessões TCP reagem ao mesmo instante reduzindo a
banda e crescem novamente de forma simultânea
– Tráfego no enlace oscila, utilização média do link diminui,
causando ineficiência
RTO (Time-out de Retx)
Se o time-out for menor do que o RTT real na rede,
haverá retransmissão desnecessária
Se o time-out for muito grande em relação ao real,
em caso de congestionamento severo, a reação a
este congestionamento será mais lenta, pois
dependerá do time-out.
Cálculo do RTO
Nas fórmulas abaixo
– M é o RTT instantâneo
– A é o valor estimado do RTT
– D é o valor estimado da variação do RTT (jitter)
A cada ACK recebido, pode-se calcular M, que é o tempo entre
o envio de um pacote e o recebimento do ACK correspondente
A ← 0,875 *A + 0,125*M
D ← 0,75*D + 0,25 * (|M - A|)
RTO = A + 4D
Inicialmente, A = 0, D = 0 e M é igual ao RTT medido pelas
primitivas iniciais de SYN (estabelecimento da conexão)
Exemplo de estimativa do RTT
Cenário Esperado
O cálculo de RTO espera que a variação de RTT
(jitter) seja grande na rede
Caso RTT tenha pequenas variações apenas num
tempo longo, RTO tende a se aproximar do RTT
instantâneo
– Tempo de propagação grande e pequenas filas nos hops
intermediários leva a este cenário
– Nestas condições, qualquer atraso repentino na chegada de
um ACK acarreta estouro do RTO
Camada de Transporte (Kurose)
• 3.1 Serviços da camada de transporte
• 3.2 Multiplexação e demultiplexação
• 3.3 Transporte não orientado à conexão: UDP
• 3.4 Princípios de transferência confiável de dados
• 3.5 Transporte orientado à conexão: TCP
• Estrutura do segmento
• Transferência confiável de dados
• Controle de fluxo
• Gerenciamento de conexão
• 3.6 Princípios de controle de congestionamento
• 3.7 Controle de congestionamento do TCP
Gerenciamento de conexão TCP
TCP transmissor estabelece conexão com o receptor
antes de trocar segmentos de dados
Inicializar variáveis e informar parâmetros
– Números de seqüência
– Buffers, controle de fluxo (ex. RcvWindow)
– MSS desejável
Cliente: iniciador da conexão
– Socket clientSocket = new Socket(“hostname","port
number");
Servidor: chamado pelo cliente
– Socket connectionSocket = welcomeSocket.accept();
Abertura de conexão: three way
handshake
Passo 1: cliente envia TCP SYN ao servidor
Passo 2: servidor responde com segmento SYNACK
Passo 3: cliente confirma o SYNACK recebido
– Especifica número de seqüência inicial
– Opcionalmente informa o MSS, obrigando a outra ponta a não enviar
segmento maior que esse valor indicado
– Caso o MSS não seja anunciado, a outra ponta pode assumir o valor
default de 536 bytes
–
–
–
–
Confirma e o SYN recebido
Aloca buffers
Especifica o número de seqüência inicial do servidor
Opcionalmente informa o MSS, obrigando a outra ponta a não enviar
segmento maior que esse valor indicado
– Caso o MSS não seja anunciado, a outra ponta pode assumir o valor
default de 536 bytes
Three way handshake
Host A
Host B
SYN seq=x MSS=256
SYN seq=x MSS=256
SYN seq=y ACK=x+1 MSS=1460
SYN seq=y ACK=x+1 MSS=1460
seq=x+1 ACK=y+1
seq=x+1 ACK=y+1
Interface serial
MTU = 296
Ethernet v2
MTU = 1500
Host A usará o MSS = 256 por causa do MTU local
Host B usará o MSS = 256 anunciado pelo Host A por ser mais restritivo
•
Pode evitar problemas em conexões como Velox que limitam o tamanho do pacote
Estados de abertura
Fechando a conexão TCP
Fechando uma conexão:
cliente fecha o socket:
clientSocket.close();
Passo 1: o cliente envia o segmento
TCP FIN ao servidor
Passo 2: servidor recebe FIN,
responde com ACK. Fecha a
conexão, envia FIN
Passo 3: cliente recebe FIN,
responde com ACK.
• Entra “espera temporizada”
- vai responder com ACK a FINs
recebidos
Passo 4: servidor, recebe ACK.
Conexão fechada
Nota: com uma pequena
modificação, pode-se manipular
FINs simultâneos
Estados de fechamento
Gerenciamento de conexão TCP
Estados do cliente
Estados do servidor
Estados do cliente
Estados do servidor
Estrutura do segmento TCP
ACK: campo de ACK
é válido
URG: dados urgentes
(pouco usado)
PSH: pede a entrega
imediata dos dados para a
aplicação (pouco usado)
RST, SYN, FIN:
(comandos de aborta,
criação e término)
Internet checksum
(como no UDP)
contagem por
bytes de dados
(não segmentos!)
número de bytes o
receptor está
pronto para aceitar
aponta para o
último byte de
dados urgentes
Pseudo header para cálculo do checksum
MSS
cabeçalho TCP
dados TCP
MSS
cabeçalho IP
dados IP
datagrama IP
MTU
cabeçalho enlace
dados do enlace
CRC
quadro da camada de enlace
MSS = MTU – 20 bytes (cabeçalho TCP) – 20 bytes (cabeçalho IP)
para não haver fragmentação do datagrama IP
MSS default mínimo = 536 bytes, porque qualquer rede deve suportar
pelo menos um datagrama IP de 576 bytes
Cenário Problemático
MTU=1500
A
MTU=1500
MTU=1500 MTU=256
MTU=256 MTU=1500
R1
A
R2
SYN <MSS 1460>
SYN <MSS 1460>
Fragmentação ocorrerá entre R1 e R2.
Como evitar isso?
– Path MTU Discovery Protocol: encontrar MTU mínimo numa rota
Envia pacotes de controle de tamanho cada vez maior, com a indicação de não
fragmentar (ICMP don’t fragment no cabeçalho IP)
Quando uma rota não pode repassar o pacote sem fragmentar, pacote de erro é
retornado (ICMP can’t fragment)
Inicia com o menor entre os MSS trocados
Por questão de desempenho, evitar o MSS default de 536 bytes, pois
não ajuda a encontrar um melhor valor (= MTU mínimo – 40 bytes)
Adicional
PUSH flag
URGENT flag
– Implementações BSD Unix ignoram o PUSH recebido porque
normalmente nunca atrasam a entrega de dados para a aplicação
– APIs podem não fornecer as possibilidades de setar o bit PUSH
– Ponteiro aponta para o último byte de dados urgente
– Bit URGENT setado indica que o estado urgente foi iniciado e não
exatamente quando iniciou
– Depende de implementação o manuseio do flag
Receive Window
– Um novo valor de rcvwnd no receptor pode ser repassado à fonte
num pacote de ACK, a qualquer instante durante uma sessão TCP
– Dados urgentes podem eventualmente ser enviados com rcwnd=0
Comportamento Adicional do
TCP
Nas implementações, para minimizar tráfego,
ACKs são atrasados e um único ACK pode
confirmar dois pacotes recebidos
corretamente
– Nas implementacões, o ACK indica o próximo
byte esperado, confirmando todos os anteriores
Algoritmo de Nagle
Especialmente em sessões interativas (TELNET)
pode haver a troca de datagramas mínimos com
muito overhead na rede
Com Nagle, procura-se bufferizar dados e somente
enviar quando da recepção de segmentos
(confirmações ou dados) na direção reversa
Similarmente, confirmações são enviadas apenas
quando podem pegar carona em dado
Todavia, o envio de segmentos acumulando vários
caracteres teclados pode gerar desconforto na
movimentação brusca do mouse em terminais X
ACK atrasado pelo SO
Algoritmo de Nagle
ACK aguarda envio do
dado da aplicação,
otimizando o uso da banda
Aguarda novo toque do
teclado para enviar ACK,
otimizando o uso da banda
ACK aguarda envio do
dado da aplicação,
otimizando o uso da banda
Aguarda novo toque do
teclado para enviar ACK,
otimizando o uso da banda
Dificuldades
Sempre incrementa a alocação de banda e,
conseqüentemente, a possibilidade de
congestionamento
Retransmissões frente a congestionamento só
realimentam o processo de degradação
Vazão prejudicada quando perdas devido ao meio
são interpretadas como congestionamento
– Ambiente de redes sem fio (redes wireless)
Quando RTT é elevado (ex.: satélite), realimentação
é lenta e retx gera ineficiência
– Usar FEC é solução
TCP throughput
Qual é o throughout médio do TCP como uma função
do tamanho da janela e do RTT?
– Ignore a partida lenta
Seja W o tamanho da janela quando ocorre perda
– Para janela = W, throughput = W/RTT
– Logo após a perda
janela cai para W/2
throughput vai para W/2RTT
Throughout médio: 0,75 W/RTT
Futuro do TCP
Exemplo: segmento de 1500 bytes, RTT de 100 ms, deseja 10
Gbps de throughput
Requer janela = 83.333 para os segmentos em trânsito
Throughput em termos da taxa de perda:
1.22⋅ MSS
RTT L
Requerida taxa de perda L bem baixa (L = 2·10-10) para
alcançar 10 Gbps!
São necessárias novas versões de TCP para alta velocidade!
Eqüidade do TCP
Objetivo de eqüidade: se K sessões TCP compartilham o
mesmo enlace do gargalo com largura de banda R, cada uma
deve ter taxa média de R/K
Por que o TCP é justo com conexões
com RTT semelhante?
Duas sessões competindo pela banda:
–
–
O aumento aditivo fornece uma inclinação de 1, quando a vazão aumenta
Redução multiplicativa diminui a vazão proporcionalmente
•perda: reduz janela por um fator de 2
•prevenção de congestionamento:
aumento aditivo
•perda: reduz janela por um fator de 2
•prevenção de congestionamento :
aumento aditivo
Eqüidade
Eqüidade e UDP
– Aplicações multimídia normalmente não usam TCP, pois
não querem a taxa estrangulada pelo controle de
congestionamento
– Em vez disso, usam UDP
Trafega áudio/vídeo a taxas constantes, toleram perda de
pacotes
– área de pesquisa: TCP amigável
Eqüidade e conexões TCP paralelas
– Web browsers podem abrir conexões paralelas com servidor
– Exemplo: enlace de taxa R suportando 9 conexões TCP;
Nova aplicação pede 1 conexão TCP, obtém taxa de R/10
Nova aplicação pede 11 conexões TCPs, obtém R/2!
Falta de Eqüidade com TCP
Congestionamento afetando muitas ( > 100)
conexões TCP pode levar a ineqüidade na captura
da banda
– Conexões com RTT menor reagem mais rápido às perdas
e estabelecem equilíbrio num ponto com vazão maior
– Referência: R. Morris, TCP Behavior with Many Flows,
IEEE International Conference on Networks, Outubro
1997
TCP: modelagem de latência
Quanto tempo demora para receber um objeto de um servidor Web
após enviar um pedido?
Ignorando o congestionamento, o atraso é influenciado por:
• Estabelecimento de conexão TCP
• Atraso de transferência de dados
• Partida lenta
Notação, hipóteses:
• Suponha um enlace entre cliente e servidor com taxa de dados R
• S: MSS (bits)
• O: tamanho do objeto (bits)
• Não há retransmissões (sem perdas e corrupção de dados)
Tamanho da janela:
• Primeiro suponha: janela de congestionamento fixa, W segmentos
• Então janela dinâmica, modelagem partida lenta
Janela de congestionamento fixa (1)
Primeiro caso:
WS/R > RTT + S/R
o ACK para o primeiro
segmento na janela retorna
antes do valor de janela dos
dados enviados esgotar
Canal fica ocupado durante
todo o tempo de transmissão
do objeto
Produto banda versus atraso
(PBD) = WS/R
•
atraso = 2RTT + O/R
Janela de congestionamento fixa (2)
Segundo caso:
•
WS/R < RTT + S/R
•
espera pelo ACK após enviar
a janela de dados
•
•
•
Espera: S/R + RTT - WS/R
Seja K o número de janelas
que cobrem o objeto
(K-1) esperas ocorrerão
atraso = 2RTT + O/R
+ (K-1)(S/R + RTT - WS/R)
WS/R
TCP Modelagem de latência:
partida lenta (1)
Agora suponha que a janela cresce de acordo com os procedimentos
da fase partida lenta
Vamos mostrar que a latência de um objeto de tamanho O, do ponto
de vista do cliente, é:
Latency = 2 RTT +
O
S
S

+ P  RTT +  − ( 2 P − 1)
R
R
R

em que P é o número de vezes que o TCP fica bloqueado no servidor
P = min{Q, K −1}
Q é o número de vezes que o servidor ficaria bloqueado se o objeto
fosse de tamanho infinito
K é o número de janelas que cobrem o objeto
Explicação
RTT para abrir conexão
RTT para requisitar o objeto
Do ponto de vista do transmissor, cada janela
com espera gera um atraso de (RTT + S/R)
Na 1a janela o tempo útil de tx é S/R
Na 2a janela o tempo útil de tx é 2 S/R
Na 3a janela o tempo útil de tx é 4 S/R
Na P-ésima janela o tempo útil de tx é 2P-1 S/R
Após P janelas o tempo útil de tx já transmitido
do objeto é ( 1 + 2 + 22+...+2P-1) S/R = 2P -1
(soma de P termos da PG)
Então, após P(RTT + S/R) (tempo gasto nas
janelas com espera), ainda faltam transmitir
O/R - (2P -1 ) S/R do objeto
Total: 2RTT + O/R + P(RTT + S/R)- (2P -1 ) S/R
TCP modelagem de latência:
partida lenta (2)
Lembre que K = número de janelas que cobrem um objeto
Como calculamos o valor de K?
K = min{k : 20 S + 21 S + L+ 2k −1 S ≥ O}
= min{k : 20 + 21 + L+ 2k −1 ≥ O / S}
O
= min{k : 2 −1 ≥ }
S
O
= min{k : k ≥ log2 ( +1)}
S
O 

= log2 ( +1)
S


k
O cálculo do número Q, de inatividade por objeto de tamanho
infinito,é similar.
TCP modelagem de latência: partida
lenta (3)
Componentes do atraso:
• 2 RTT para estabelecimento de
conexão e requisição
• O/R para transmitir um objeto
• Servidor com períodos inativos
devido à partida lenta
Servidor inativo:
P = min{K-1,Q} vezes
Exemplo:
• O/S = 15 segmentos
• K = 4 janelas, pois 2**4 >15
• Q = 2 (se o objeto fosse infinito)
• P = min{K-1,Q} = 2
Servidor inativo P = 2 tempos
Modelagem HTTP
• Presuma que uma página Web consista em:
• 1 página HTML de base (de tamanho O bits)
• M imagens (cada uma de tamanho O bits)
• HTTP não persistente:
• M + 1 conexões TCP nos servidores
• Tempo de resposta = (M + 1) O/R + (M + 1) 2RTT + soma dos
períodos de inatividade
• HTTP persistente:
• 2 RTT para requisitar e receber o arquivo HTML de base
• 1 RTT para requisitar e receber M imagens
• Tempo de resposta = (M + 1)O/R + 3RTT + soma dos períodos de
inatividade
• HTTP não persistente com X conexões paralelas
• M/X (supondo inteiro), representa o # de vezes que temos que
transferir as imagens usando as X conexões em paralelo.
• 1 conexão TCP para o arquivo de base
• Tempo de resposta = (M/X + 1) O/R + (M/X + 1) 2RTT + soma dos
períodos de inatividade
Tempo de resposta HTTP (em segundos)
RTT = 100 ms, O = 5 Kbytes, M = 10 e X = 5
20
18
16
14
12
non-persistent
persistent
parallel non-persistent
10
8
6
4
2
0
28 Kbps 100 Kbps 1 Mbps 10 Mbps
Em baixa taxa, tempo de transmissão do objeto domina e desempenho próximo
Em alta taxa, conexões persistentes e conexões paralelas oferecem
desempenho melhor e similar
Tempo de resposta HTTP (em segundos)
RTT =1 s, O = 5 Kbytes, M=10 and X=5
70
60
50
40
non-persistent
persistent
parallel non-persistent
30
20
10
0
28 Kbps
100 Kbps
1 Mbps
10 Mbps
Para RTT longo, o tempo de resposta é dominado pelo estabelecimento TCP e
atrasos na partida lenta (objetos ainda pequenos)
Conexões persistentes agora oferecem a melhor performance
Importante, particularmente em redes com produto banda x atraso grande.
Resumo
Princípios por trás dos serviços da camada de transporte:
–
–
–
–
Multiplexação/demultiplexação
Transferência de dados confiável
Controle de fluxo
Controle de congestionamento
• Instanciação e implementação na Internet
– UDP
– TCP
A seguir:
– Saímos da “borda” da rede (camadas de aplicação e de
transporte)
– Vamos para o “núcleo” da rede
Variações de TCP
Cabeçalho TCP
Options
Fast Retransmit
Ao receber três ACKs duplicados, a cwnd é reduzida
pela metade, sendo este valor salvo no ssthresh.
O pacote “perdido” é retransmitido e transmissor fica
esperando a chegada do ACK confirmando o pacote
retransmitido
Após a chegada do ACK confirmando o pacote retx,
a cwnd volta a ter o tamanho salvo no ssthresh e o
algoritmo de congestion avoidance é executado
Fast Retransmit: bloqueio
Numa operação tradicional, ao reduzir após a perda
a janela pela metade, o TCP fica bloqueado sem
transmitir novos pacotes aguardando o ACK do
pacote retransmitido, pois todos os pacotes na janela
CWND já foram transmitidos e estão aguardando
confirmação
Comportamento do TCP
cwnd=8,<1,2,3,4,5,6,7,8>
ACK 1
ACK 1 dup
ACK 1 dup
ACK 1 dup
ACK 1 dup
Fast Retransmit
1
2
3
X
5
7
4
6
8
1
ACK 1 dup
Recupera a perda do
pacote 1 em um RTT
ssthresd= 4,
cwnd=8,<1,2,3,4,5,6,7,8>
ACK 9
Congestion Avoidance
ssthresd= 4, cwnd= 4,
<9,10,11,12>
9
10
11
12
Ocorre rajada ao
final da fase de
recuperação, ruim!
Melhoria: Fast Recovery
Executado junto com Fast Retransmit após receber três ACKs
duplicados
Aumenta o cwnd de 1 a cada chegada de ACK duplicado
durante a fase de recuperação, enquanto aguarda a chegada
do ACK referente ao pacote retransmitido (após RTT)
Possibilita a transmissão de novos segmentos e não ficar
apenas bloqueado e inativo com uma janela que só contém
segmentos já transmitidos
Após a chegada do ACK confirmando o pacote retx, a cwnd
volta a ter o tamanho salvo no ssthresh e o algoritmo de
congestion avoidance é executado
Fast Recovery
cwnd=8,<1,2,3,4,5,6,7,8>
ACK 1
1
2
3
ACK 1 dup
ACK 1 dup
ACK 1 dup
Fast Retransmit,
ssthresd= 4,
cwnd= 8
ACK 1 dup
cwnd=8+1=<1,2,3,4,5,6,7,8,9>
ACK 1 dup
cwnd=9+1=<1,2,3,4,5,6,7,8,9,10>
ACK 1 dup
cwnd=10+1=<1,2,3,4,5,6,7,8,9,10,11>
ACK 1 dup
cwnd=11+1=<1,2,3,4,5,6,7,8,9,10,11,12>
Congestion Avoidance
ssthresd= 4,
cwnd= 4,<9,10,11,12>
X
4
5
6
7
1
8
9
10
11
12
ACK 9
Confirma 1
cwnd= 4 = <9,10,11,12>
ACK 10
cwnd= 4+1/4 = <10,11,12,13>
ACK 11
cwnd=4+2/4 =<11,12,13,14>
13
14
ACK 12
cwnd=4+3/4=<12,13,14,15>
15
ACK 13
cwnd= 4+1 = <13,14,15,16,17>
Recupera a perda do
pacote 1 em um RTT
16
17
Evita rajada ao
final da fase de
recuperação!
Tipos de TCP
Tahoe
Reno
New Reno
SACK
Existem algumas outras variações propostas: Vegas, Westwood.
Tahoe
Primeira proposta de implementação do TCP, baseada no
algoritmo de controle de congestionamento proposto por Van
Jacobson.
– Presentes os algoritmos Slow Start e Congestion Avoidance.
– Retx ocorre apenas por time-out
Conhecida como Tahoe NoFR (no Fast Retransmit)
Melhorias feitas nesta implementação incluíram nela o
algoritmo Fast Retransmit. Por isso, algumas bibliografias
trazem tal algoritmo associado a esta implementação.
Reno
Alteração ao Tahoe proposta por Jacobson, acrescentando o
algoritmo fast retransmit e fast recovery.
Problemas com Reno
Múltiplas perdas de pacotes numa mesma janela
– Remetente só detecta perdas consecutivas de pacotes, quando
tiver recebido o ACK da primeira retransmissão
TCP sai de fast recovery e, logo em seguida, retx o segundo
pacote perdido, entrando em congestion avoidance
A recuperação do próximo pacote perdido pode acontecer
por time-out, forçando a entrada em slow start
Fato acima ocorrendo múltiplas vezes acarreta em reduções
múltiplas do threshold e cwnd, podendo levar o desempenho
a níveis extremamente baixos
Reno com múltiplas perdas
ACK 1
cwnd=8,<1,2,3,4,5,6,7,8>
1
2
3
4
5
ACK 1 dup
ACK 1 dup
Fast Retransmit,
ssthresd= 4,
cwnd= 8
ACK 1 dup
cwnd=8=<1,2,3,4,5,6,7,8>
ACK 1 dup
cwnd=8+1=<1,2,3,4,5,6,7,8,9>
ACK 1 dup
cwnd=9+1=<1,2,3,4,5,6,7,8,9,10>
ACK 1 dup
cwnd=10+1=<1,2,3,4,5,6,7,8,9,10,11>
Congestion Avoidance
ssthresd= 4,
cwnd= 4,<2,3,4,5>
Fast Retransmit
ssthresd= 2,
cwnd= 4,<2,3,4,5>
Congestion Avoidance
ssthresd= 2,
cwnd= 2,<12,13>
Confirma 1
cwnd= 4 = <2,3,4,5>
cwnd=4+1/4 =<2,3,4,5>
cwnd=4+2/4 =<2,3,4,5>
cwnd=4+3/4 =<2,3,4,5>
cwnd= <2,3,4,5>
ACK 2
7
X
X
6
8
1
9
10
11
O fato de ter transmitido durante a
recuperação permitiu a recepção
dos três ACKs duplicado, caso
contrário sairia por time-out e
entraria em slow start
ACK 2 dup
ACK 2 dup
ACK 2 dup
2
ACK 12
cwnd= <12,13>
Recupera a perda do
pacote 1 em um RTT
12
13
Recupera a perda do
pacote 2 em um RTT
New Reno
É a alteração proposta para solucionar o problema de múltiplas
perdas de pacotes na mesma janela, mostrado no RENO
– RFC 2582 – The New-Reno Modification to TCP’s Fast Recovery
Algorithm, 1999
Ao entrar na fase de fast recovery pela recepção de três ACKs
duplicados, a retransmissão rápida ocorre
O algoritmo só passará para a fase de congestion avoidance,
quando for recebido um ACK que confirme todos os pacotes
enviados até o momento da retransmissão rápida
– Difere do Reno, que entra em congestion avoidance, tão logo um
ACK que confirme a retransmissão seja recebido
ACK parcial
É todo aquele ACK que confirma pacotes ainda
não confirmados dentro da janela do remetente,
mas não termina a fase do Fast Recovery, pois
não confirma todos os pacotes da janela
O recebimento de um ACK parcial causa a
retransmissão do próximo pacote esperado pelo
receptor, que necessariamente está na janela
original do transmissor
– Se não estivesse, este ACK não seria parcial!
ACK parcial
É necessariamente uma resposta a um pacote
retransmitido durante a fase de Fast Recovery
ACks parciais só ocorrerão quando perdas múltiplas na
janela ocorrerem
Reação do New Reno a ACK parcial
– Janela de congestionamento é incrementada de um (por ter
chegado um ACK) e reduzida de um valor igual à soma do
tamanho de todos os novos pacotes que acabaram de ser
confirmados
– Esta reação tem como objetivo fazer com que ao final do Fast
Recovery a quantidade de pacotes não confirmados esteja em
torno de ssthresh, pois, deste modo, não ocorrerá uma rajada de
envio de pacotes, quando começar o congestion avoidance.
New Reno
Cada ACK parcial recebido (RTT segundos após retx)
confirma uma nova perda na janela de transmissão
Após retx provocada pelo ACK parcial, demora mais RTT até
descobrir próxima perda ocorrida na janela
Como não se sai de Fast Recovery com o recebimento
apenas de ACKs parciais, o problema das múltiplas
reduções da janela foi resolvido.
O NewReno é a única implementação além do SACK,
apresentada abaixo, que retransmite um pacote devido ao
recebimento de um único ACK - neste caso um ACK parcial.
New Reno com múltiplas perdas
ACK 1
cwnd=8,<1,2,3,4,5,6,7,8>
1
2
3
4
5
ACK 1 dup
ACK 1 dup
Fast Retransmit,
ssthresd= 4,
cwnd= 8
ACK 1 dup
cwnd=8=<1,2,3,4,5,6,7,8>
ACK 1 dup
cwnd=8+1=<1,2,3,4,5,6,7,8,9>
ACK 1 dup
cwnd=9+1=<1,2,3,4,5,6,7,8,9,10>
ACK 1 dup
cwnd=10+1=<1,2,3,4,5,6,7,8,9,10,11>
ACK 2 parcial
Confirma 1
cwnd= 11+1-1= <1,2,3,4,5,6,7,8,9,10,11>
cwnd=11+1 =<1,2,3,4,5,6,7,8,9.10,11,12>
ACK 2 dup
ACK 2 dup
cwnd=12+1 =<1,2,3,4,5,6,7,8,9.10,11,12,13>
ACK 2 dup
cwnd=13+1 =<1,2,3,4,5,6,7,8,9.10,11,12,13,14>
7
X
X
6
8
1
9
10
11
2
12
13
Recupera a perda dos
pacotes 1 e 2 em dois RTTs
na fase de recuperação, sem
correr o risco de dar time-out
14
ACK 12
Congestion Avoidance
ssthresd= 4,
cwnd= 4,<12,13,14,15>
cwnd= <12,13,14,15>
15
Após recuperação, entra em
CA com cwnd = ssthresd = 4,
após ter transmitido 14
segmentos e evitado rajadas
SACK
Opção usada no início da conexão (os pacotes com
bit SYN setado) para declarar que ambas as partes
estão habilitadas para trabalhar com SACK.
SACK
Opção usada durante a
conexão, para informar
ao remetente os
números de seqüência
que formam os limites
dos blocos de bytes
fora de ordem que
foram recebidos com
sucesso.
Exemplo SACK
Suponha: pacotes 1, 2, 3, 4, 5, 6 e 7 enviados, mas 2 e 6 perdidos
–
Números de seqüência sejam respectivamente
<0-1499> para o pacote 1
<1500-2999> para o pacote 2
<3000-4499> para o pacote 3 e assim sucessivamente.
Ao receber o pacote 1:
Ao receber o pacote 3, fora de ordem:
Ao receber o pacote 4:
Na chegada do pacote 5:
Ao chegar o pacote 7:
–
–
–
–
–
Receptor envia ACK 1500 (normal)
Receptor envia ACK 1500 com opção SACK = [left=3000, right=4500] (confirma o
último byte mais 1).
Envia ACK 1500 com opção SACK = [left= 3000, right=6000] (confirmando pacotes 3 e
4 recebidos com sucesso)
Envia ACK 1500 com opção SACK = [left=3000, right=7500]
Envia ACK 1500 com SACK = [left=3000, right=7500], [left=9000, right=10500]
SACK
Resolve o problema inerente ao Reno e ao New-Reno de só
perceber no máximo uma perda por RTT
Toda vez que o receptor receber um pacote fora de ordem,
ele deve enviar um pacote ACK com o campo de opções
SACK, contendo a informação de quais segmentos foram
recebidos com sucesso
De possa da informação do SACK, o transmissor pode
retransmitir os segmentos que faltam no receptor,
retransmitindo um ou mais pacotes da janela de transmissão
New Reno com múltiplas perdas e
SACK
cwnd=8,<1,2,3,4,5,6,7,8>
Indica que não só o
pacote 1 se perdeu,
mas também o 2
Fast Retransmit,
ssthresd= 4,
cwnd= 8
ACK 1
ACK 1 dup, sack=[3]
ACK 1 dup, sack= [3-4]
ACK 1 dup,sack=[3-5]
cwnd=8=<1,2,3,4,5,6,7,8>
ACK 1 dup, sack=[3-6]
cwnd=8+1=<1,2,3,4,5,6,7,8,9>
ACK 1 dup, sack=[3-7]
cwnd=9+1=<1,2,3,4,5,6,7,8,9,10>
ACK 1 dup, sack=[3-8]
cwnd=10+1=<1,2,3,4,5,6,7,8,9,10,11>
Confirma 1
ACK 2 parcial, sack=[3-8]
cwnd= 11+1-1= <1,2,3,4,5,6,7,8,9,10,11>
ACK 9
Congestion Avoidance
ssthresd= 4,
cwnd= 4,<9,10,11,12>
1
2
3
4
5
cwnd= <9,10,11,12>
ACK 10
cwnd=4+1/4= <10,11,12,13>
ACK 11
cwnd=4+2/4= <11,12,13,14>
ACK 12
cwnd=4+3/4= <12,13,14,15>
ACK 13
cwnd=4+1= <13,14,15,16,17>
7
X
X
6
8
1
2
9
10
11
12
13
14
15
16
17
Recupera a perda dos
pacotes 1 e 2 em um RTT na
fase de recuperação, sem
correr o risco de dar time-out
Após recuperação, entra em
CA com cwnd = ssthresd = 4,
após ter transmitido 11
segmentos e evitado rajadas
Implementações
SO
FreeBSD 3.5.1
FreeBSD 4.2
FreeBSD 4.3
FreeBSD 4.4
FreeBSD 4.5
Windows 98
Windows 2000
RedHat 7.2
Moraru, B., Copaciu, F., Lazar, G., Dobrota, V. – Practical Analysis
of TCP Implementations: Tahoe, Reno, NewReno, 2003
TCP Implementation
Reno
Reno
NewReno
NewReno
NewReno
TahoeNoFR (sem Fast
Retransmit)
TahoeNoFR (sem Fast
Retransmit)
NewReno
Implementações
SO
TCP Implementation
FreeBSD 5.2
Reno
Linux 2.6
NewReno
Windows XP
TahoeNoFR
Trabalho Final de Curso 2004
–
SACK permitted
SACK+
SACK
SACK-
PESQUISA SOBRE AS CARACTERÍSTICAS DAS
IMPLEMENTAÇÕES DO TCP, Sergio Cosme Noronha Cardoso Filho
e Vitor Veneza Quimas Macedo
Desempenho
Caso Ideal
Tempos Aproximados (s)
CL10_CL10
4,45
XP_BSD
4,65
BSD_CL10
4,95
BSD_BSD
4,95
BSD_XP
5,25
CL10_BSD
5,7
XP_CL10
6,45
CL10_XP
6,5
XP_XP
6,65
TCP ECN
TCP operando com notificação
explícita de congestionamento
Explicit Congestion Notification
Sistema de filas ativos nos roteadores podem marcar
pacotes IP ao invés de descartá-los, evitando a
retransmissão de segmentos e consumo de banda
Isso só será feito se a camada de transporte nas
duas pontas for capaz de reagir aos pacotes
marcados como reagiria em caso de descarte
– TCP-ECT (ECN capable)
Bits de marcação nos cabeçalhos de IP e TCP
RFC-3168, The Addition of ECN to IP, 2001
Eventos
A
Reage como se
detetada uma perda:
• reduz cwnd à metade
• entra em CA com
cwnd=ssthresd
IP ECT
R
Fila de saída
congestionada
IP CE
TCP ECN-ECHO
B
CE pede redução
de vazão
ECN-ECHO repassa
aviso ao transmissor
TCP ECN-ECHO
TCP CWR
Envia CWR
confirmando que
reduziu a vazão
TCP ECN-ECHO
Reenvia ECN-ECHO
até confirmação
Pára de gerar
ECN-ECHO
IP
TRANSPORTE
MSG
64
64 K
K
64
64 K
K
64
64 K
K
REDE
VERSION
64
64 K
K
IHL
TYPE OF SERVICE
DF MF
IDENTIFICATION
TIME TO LIVE
TOTAL LENGTH MAX 64 K
PROTOCOL
OFFSET 8 bytes
HEADER CHECKSUM
SOURCE
DESTINATION
OPTIONS
Campo Type of Service (TOS)
– Serve para marcar os pacotes com diferentes prioridades e outras
funções (ECN)
ECN no IP
Campo ECN formado pelos bits 6 e 7 do campo TOS do IPv4,
que corresponde ao octeto de classe de tráfego no IPv6
0
1
2
3
4
5
6
7
+---------+---------+---------+---------+---------+---------+---------+---------+
|
Campo DS
|
Campo
|
| DSCP (code point para serviços diferenciados) |
ECN
|
+---------+---------+---------+---------+---------+---------+---------+---------+
Campo ECN
0
0
Not-ECT
0
1
ECT
1
0
ECT
1
1
CE
– Bits 6 e 7 anteriormente definidos pela RFC-2481 ficam alterados
– Uso de 2 bits garante robustez e evita comportamento errado de
implementações de roteadores ou receptores TCP
ECN no TCP
Cabeçalho TCP normal
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|
|
| U | A| P | R| S | F |
| Header Length |
Reservado
| R | C| S | S | Y | I |
|
|
| G | K| H | T | N | N |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
Cabeçalho TCP para ECN
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|
|
| C| E| U | A| P | R| S | F |
| Header Length |
Reservado | W | C | R | C | S | S | Y | I |
|
|
| R| E| G | K| H | T | N | N |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
– ECE: ECN-Echo
– CWR: Congestion Reply
Termos Básicos
Bandwidth (largura de banda) em Hz
Data rate (taxa) em bps
Throughput (vazão) em bps
Goodput
– É a faixa espectral de um enlace ou canal de comunicação
carregando sinais (historicamente ciclos/s)
– É taxa de transmissão conseguida através do uso de alguma
codificação, onde um símbolo do código pode ser transmitido em
um ciclo e carregar vários bits de informação
– É a taxa útil de entrega de bits em ordem de um transmissor para
um receptor, sendo menor ou igual à taxa de transmissão.
Transmitir em alta taxa com codificação mais complexa num canal
com alta interferência pode não maximizar a vazão, pois
retransmissões irão ocorrer.
– Vazão em condições de eqüidade.
Artigo na Web Interessante
How much bandwidth is enough?
–
Alexander B. Cannara, PhD
09.13.2006
Rating: -4.24- (out of 5)
http://searchnetworking.techtarget.com/tip/0
,289483,sid7_gci1214212,00.html
Foca nos problemas de performance devido
a configurações inadequadas de TCP e
congestionamento em rede
Referências para TCP
Stevens, W. Richard, TCP/IP Illustrated, Volume 1 The Protocols, AddisonWesley, 576 páginas, 1994
RFC-793, Transmission Control Protocol, 1981
RFC-1323, RCP Extensions for High Performance, 1992
RFC-2001, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast
Recovery Algorithms, 1997
RFC-2018, TCP Selective Acknowledgement Options,1996
RFC-2581, TCP Congestion Control, 1999
RFC-3168, The Addition of Explicit Congestion Notification (ECN) to IP, 2001
RFC-3360, Inappropriate TCP Resets Considered Harmful, 2002
RFC-3390, Increasing TCP's Initial Window, 2002
RFC-3449, TCP Performance Implications of Network Path Asymmetry, 2002
RFC-3481, TCP over Second (2.5G) and Third (3G) Generation Wireless
Networks, 2003