Desvendando o TCP

Reinaldo Penno Filho <reinaldo@co.rnp.br>

Rede Nacional de Ensino e Pesquisa (RNP)

Introdução
Round trip time variance estimation
Karn's clamped retransmit backoff
Slow start
Congestion avoidance
Fast retransmit e fast recovery
Conclusão
Referências bibliográficas

Em outubro de 1986, a Internet experimentou o primeiro de uma série de fenômenos que ficaram conhecidos como "colapsos de congestionamento". Durante este período, a taxa de dados entre o Lawrence Berkeley Laboratory e a UC Berkeley (sites separados por 400 metros e dois hops) caiu de 32 Kbps para 40 bps. Van Jacobson e outros ficaram fascinados por essa queda brusca de um fator maior que 1.000 na taxa de transmissão e embarcaram na investigação do problema.

Palavras chaves: TCP, Congestion Avoidance, Fast Retransmit, Fast Recovery, Slow-Start, Round Trip Time.

Pré-requisito: Conhecimento básico de TCP e o funcionamento de um protocolo de janela deslizante.

Introdução

Desde aquela época, oito novos algoritmos foram incluídos no TCP:

round-trip-time variance estimation
exponential retransmit timer backoff
slow-start
more agressive receiver ack policy
dynamic window sizing on congestion
Karn's clamped retrasmit backoff
fast retransmit
fast recovery

Este artigo procura dar uma breve descrição dos algoritmos acima listados. Para uma visão mais aprofundada o leitor deve consultar as referências dadas no final deste artigo.

Notadamente, o fluxo, em uma conexão TCP, deveria obedecer ao princípio da conservação de pacotes. E, se este princípio fosse obedecido, colapsos devido ao congestionamento seria uma exceção ao invés da regra. Logo, controle de congestionamento significa encontrar as causas da violação do princípio da conservação e consertá-las.

Round trip time variance estimation

Fundamental para o mecanismo de timeout e retransmissão é a estimativa do tempo total de transmissão de ida e volta (RTT - round trip time) em uma determinada conexão. Como esta estimativa muda com o tempo, devido a mudanças de rotas e padrões de tráfego, o TCP deve monitorar estas mudanças e modificar o tempo de timeout apropriadamente.

Primeiramente, o TCP deve monitorar o RTT entre o envio de um segmento com um número de seqüência determinado e o recebimento da sua confirmação. A especificação original do TCP atualizava a estimativa do RTT (chamada de R) usando o filtro passa-baixo.

R <- aR + (1-a) M

onde a é o fator de atenuação com o valor recomendado de 0,9. Este valor do RTT é atualizado toda vez que uma nova medida é feita. Noventa porcento de cada nova estimativa é derivada da anterior e 10% desta nova medida.

Devido a este método com atenuação, que muda a medida que o RTT muda, a RFC793 recomenda que o valor do timeout de retransmissão (RTO) seja

RTO = RB

onde B é o fator variacional do atraso com o valor recomendado de 2.

Jacobson ([Jacobson 88]) detalha os problemas com essa abordagem. Basicamente, ela não consegue se adaptar a flutuações muito altas no RTT, causando retransmissões desnecessárias. Como ele mesmo nota, retransmissões desnecessárias aumentam ainda mais a carga na rede, quando ela já está sobrecarregada. Para a área de redes, é o equivamente a, num incêndio, se colocar gasolina no fogo.

O que se faz necessário é monitorar a variância nas medidas do RTT, em adição ao mecanismo que faz as estimativas atenuadas. Calculando o RTO baseado, tanto na média, quanto na variância, provê uma resposta muito melhor às altas flutuações no RTT, do que calcular o RTO como somente uma constante vezes a média.

Como descrito por Jacobson, o desvio médio é uma boa aproximação do desvio padrão, só que mais fácil de calcular. Isto leva-nos a seguinte série de equações que são aplicadas a cada nova medida do RTT:

Err = RTT - A

A<-A + g Err

D <- D + h ( | Err | - D )

RTO = A + 4D

onde A é o RTT atenuado (uma estimativa da média) e D é o desvio padrão atenuado. Err é a diferença entre o último valor medido e a estimativa corrente. Tanto A como D são usados para calcular o próximo valor do timeout de retransmissão (RTO). O ganho g é igual a 1/8 (0,125). O ganho para o desvio é igual a h e tem valor 0,25. Quanto maior o ganho para o desvio, maior será o RTO em resposta às mudanças do RTT. As variáveis A e D são inicializadas com os valores 0 e 3 respecitvamente.

Karn's clamped retransmit backoff

Um problema ocorre quando um pacote é retransmitido. Supondo que um pacote é transmitido e um timeout ocorre. Neste caso, o RTO sofre um recuo exponencial como mostrado na seção anterior, o pacote é retransmitido com um RTO maior, e uma confirmação é recebida. Esse ACK corresponde a primeira transmissão ou a segunda? Isto é chamado de problema de ambiguidade da retransmissao.

Karn e Patridge ([Karn e Patridge]) especificam que, quando um timeout e retransmissão ocorrem, não se pode atualizar a estimativa do RTT quando a confirmação do dado retransmitido finalmente chega. Isto ocorre porque não se sabe a que segmento o ACK corresponde. Talvez a primeira transmissao tivesse sofrido um atraso, mas não descartada, ou talvez o ACK da primeira transmissão estivesse retido em algum lugar da rede.

Além disso, sabendo que o dado foi retransmitido, e o recuo exponencial foi aplicado ao RTO, reusa-se este RTO para a próxima transmissão Um novo RTO é calculado somente quando uma confirmação de um segmento que não foi retransmitido é recebida.

Slow start

Antigas implementações do TCP começavam uma conexão injetando múltiplos segmentos na rede, até o limite permitido pea janela anunciada pelo receptor. Enquanto isto não acarreta problemas quando os dois nós estão na mesma LAN, se existem roteadores e diversos enlaces entre a origem e destino, estes podem vir a acontecer. Algum roteador intermediário pode ficar sem espaço de buffer ou aplicar alguma política de descarte de pacotes. Em [Jacobson 1988], é mostrado como isto pode reduzir drasticamente o desempenho de uma conexão TCP.

O algoritmo para evitar isto é chamado de slow start. Seu mecanismo é baseado na observação que a taxa que novos pacotes devem ser injetados na rede deve ser a mesma em que as confirmações (ACK) são enviadas pelo outro destino.

O slow start requer que outra janela seja mantida pelo TCP emissor: a janela de congestionamento, chamada cwnd. Quando uma nova conexão é estabelecida com outro host na rede, a janela de congestionamento é inicializada com um segmento, ou seja, o tamanho do segmento anunciado pelo nó oposto (tipicamente 536 ou 512 bytes). Toda vez que um novo ACK é recebido, a janela de congestionamento é incrementada de um segmento. A cwnd é mantida em bytes, mas o slow start sempre a incrementa em segmentos. O emissor pode transmitir até o mínimo entre a janela de congestionamento e a janela anunciada pelo receptor. A janela de congestionamento é o controle de fluxo imposto pelo emissor, enquanto a janela anunciada é controle de fluxo imposto pelo receptor.

O emissor começa transmitindo um segmento e esperando pelo ACK correspondente. Quando este ACK é recebido, a janela de congestionamento é incrementada de um para dois, e dois segmentos podem ser mandados. Quando cada um destes dois segmentos for confirmado, a janela de congestionamento é aumentada para quatro. Isto provê uma aumento exponencial.

Em um determindado momento a capacidade da Internet será alcançada, e um roteador intermediário começará a descartar pacotes. Isto diz ao emissor que a janela de congestionamento ficou muito grande.

Congestion avoidance

Se as estimativas de RTT e RTO estiverem em boa forma, é possível afirmar, com grande certeza, que, se o cronômetro de retransmissão expirar (timeout), um pacote foi perdido. Pacotes se perdem na rede por duas razões: são danificados em trânsito, ou a rede está congestionada e, em algum lugar, não há buffer suficiente. Na maioria dos enlaces, a perda de pacotes devido a danificação dos dados é rara (<< 1%). Logo, é muito provável que a perda de um pacote seja conseqüência direta de congestionamento na rede.

Congestion avoidance e slow start são algoritmos independentes com objetivos diferentes. Mas, quando ocorre congestionamento, baixa-se a taxa de transmissão de pacotes na rede, e então invoca-se o slow start para recomeçar o processo de aumento da janela e taxa de transmisão.

O congestion avoidance e o slow start requerem que duas variáveis seja monitoradas para cada conexão: a janela de congestionamento, cwnd , e a janela limite para o algoritmo slow start, ssthresh. O algoritmo combinado funciona da seguinte maneira:

Durante a inicialização de uma conexão, a cwnd é igual a um segmento e a ssthresh, a 65536 bytes;
A rotina de emissão do TCP sempre envia o mínimo entre a cwnd e a janela anunciada pelo receptor;
Quando ocorre congestionamento (indicada por timeout ou o recebimento de ACKs duplicados), metade do valor atual da janela de transmissão (o mínimo entre a cwnd e a janela anuciada pelo receptor) é armazenado em ssthresh. Além disso, se o congestionamento foi causada por timeout, a cwnd passa a valer um segmento (ou seja, slow-start);
Quando novos dados forem confirmados pelo nó destino, a cwnd é aumentada, mas a maneira como isto é feito depende se está sendo feito o slow-start ou o congestion avoidance.

Se a cwnd for menor ou igual a ssthresh, o TCP está em slow start; caso contrário, ele está realizando o congestion avoidance. O slow start prossegue até que a janela de transmissão do TCP esteja com metade do tamanho de quando ocorreu o congestionamento (guarda-se metade do valor da janela que causou problema no passo 3), e, então, passa-se para a fase de congestion avoidance.

O slow start faz a cwnd começar valendo um segmento e ser incrementada de um segmento toda vez que um ACK é recebido. Como mencionado anteriormente, isto abre a janela exponencialmente: um segmento é enviado, então dois, quatro, e assim por diante. O congestion avoidance, por sua vez, faz com que a cwnd seja incrementada por segsize*segsize/cwnd toda vez que um ACK for recebido, onde segsize é o tamanho do segmento (segsize e cwnd são mantidos em bytes).

Isto faz com que a cwnd tenha um aumento linear, comparado com o aumento exponencial do slow start. O aumento da cwnd deve ser de, no máximo, um segmento a cada round-trip time (independente de quantos ACKs sejam recebidos neste RTT), enquanto que o slow start incrementa a cwnd baseado no número de ACKs recebidos em um RTT.

Fast retransmit e fast recovery

Modificações no algoritmo de congestion avoidance foram propostas em 1990 [Jacobson 1990b]. Antes de descrever a mudança, note que o TCP é obrigado a gerar uma confirmação imediata (um ACK duplicado) quando um segmento fora de ordem é recebido. A finalidade deste ACK duplicado é indicar ao emissor que um segmento foi recebido fora de ordem e qual o número de seqüência esperado.

Partindo do fato que não se sabe se um ACK duplicado foi causado por um segmento perdido ou somente uma reordenação de segmentos, espera-se que um pequeno número de ACKs duplicados sejam recebidos antes que qualquer atitude seja tomada. É assumido que, se for somente uma reordenação de segmentos, só serão recebidos um ou dois ACKS duplicados antes do segmento fora de ordem alcançar o destino e ser processado, o que implicará em um novo ACK.

Se três ou mais ACKS duplicados forem recebidos em seguida, é um forte indício que um segmento foi perdido. O TCP realiza, então, a retransmissão imediata do que aparenta ser o segmento perdido, sem esperar que o cronômetro de retransmissão expire (timeout). Este é o algoritmo de fast retransmit. Em seguida, congestion avoidance, e não slow start, é feito. Este é o algoritmo de fast recovery.

A razão pela qual não se faz slow start nesse caso é que o recebimento de ACKs duplicados diz mais do que simplesmente um segmento foi perdido. Sabe-se que o destino só pode gerar ACKs duplicados quando outro segmento for recebido, isto é, o segmento deixou a camada física e está no buffer do destino. Logo, ainda temos dados trafegando entre os dois nós. Então, não é aconselhavel reduzir o fluxo abruptamente usando o slow start.

Conclusão

O TCP é baseado nas RFCs 793 e 2001. A RFC793 é considerada o padrão e foi escrita por [Postel 1981]. Os algoritmos discutidos acima foram incorporados a partir de 1986 e estão sumarizados na RFC 2001 [Stevens 1997].

Na época da confecção deste artigo, foi compilado e instalado o tcpdump para monitar pacotes TCP na rede e com isso refazer as experiências mostradas em [Stevens 1994], na esperança de ver os algoritmos acima em ação. Os seguintes sistemas foram testados: Solaris 2.5, AIX 4.1.4, FreeBSD 2.2.2, Linux 96 e Windows 95. Algumas obervações seguem.

Poucos sistemas operacionais (mesmo comerciais) implementam corretamente as RFCs padrão do TCP;
Os que implemetam com mais fidelidade os algoritmos mencionados acima são o FreeBSD e o Solaris 2.5;
O Windows 95 sequer implementa as RFCs originais do IP e do TCP corretamente, o mesmo acontecendo em relação aos algoritmos da RFC2001;
O AIX 4.1.4 implementa os algoritmos acima com algumas variações proprietárias (não poderia esperar outra coisa da IBM);
O Linux 96 surpreendeu. Implementa perfeitamente alguns algoritmos mais avançados mas, assim como outros, deixa a desejar no simples algoritmo de exponential timer backoff;
Durante todos os dias de monitoramento nao foi detectada nenhuma janela de transmissão, em nenhum dos sistemas, maior que 16K (o máximo, teoricamente, seria 65K), apesar do link do Núcleo da Coordenação com o PoP-RJ(2Mbps) não estar nem perto da saturação.

Os algoritmos que foram discutidos podem parecer "cabeludos", mas o mais complicado deles tem 10 linhas de código, e o mais simples, 3. Aqueles que não acreditaram e ainda estão fazendo caras e bocas, estão convidados a dar uma lida nas referências.

Deve ter ficado claro que o TCP é uma mãe em redes de alto desempenho é um carrasco em redes congestionadas. Nas primeiras, sua janela de transmissão será incrementada exponencialmente, e, ainda que ocorram retransmissões aqui e ali, o TCP se recupera bem.

Já em uma rede congestionada, toda vez que acontecer perda de segmentos por timeout, a janela de transmissão será imediatamente reduzida a um segmento e o slow start será acionado.

Isto significa que é melhor ter roteadores com grande capacidade de memória, pois eventualmente processarão todos os pacotes (levando em conta o limite de timeout, claro), do que aplicar algum mecanismo de descarte. O motivo é simples, atraso implica em fast retransmit e fast recovery; descarte (timeout) em slow start.

Referências bibliográficas

W.R. Stevens, "TCP/IP Illustrated, Volume 1: The Protocols", Addison-Wesley, 1994

W.R. Stevens, "TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms", Network Working Group, RFC 2001, NOAO, January, 1997

Jacobson, V. Congestion avoidance and control. In Proceedings of SIGCOMM '88 (Stanford, CA, Aug. 1988), ACM

Jacobson, V. 1990a. "Modified TCP congestion Avoidance Algorithm", April 30, 1990, end2end-interest mailing list (Apr.)

Jacobson, V. 1990b. "Berkeley TCP Evolution from 4.3-Tahoe to 4.3-Reno", Proceedings of the Eighteenth Internet Engineering Task Force, p.365 (Sept.), University of British Columbia, Vancouver, B.C.

Postel, J. B., ed. 1981 "Transmission Control Protocol", RFC 793, 85 pages (Sept.)

Postel J., "Internet Protocol", STD 5, RFC 791, USC/Information Sciences Institute, September 1981.

Karn, P. and Patridge, C. "Improving Round-Trip Time Estimates in Reliable Transport Protocols, "Computer Communication Review, vol. 17, no. 5, pp. 2-7 (Aug.)