YouTube Facebook Twitter
Apostilas Artigos Tutoriais Aulas Vídeos Blog Ferramentas de Rede Fórum Downloads Colabore Fale Conosco
» artigos
:: Controle de Congestionamento

Cleiton Ferreira em 25/05/2008

 

Resumo

Em [AND04] é apresentado todos os conceitos da camada de transporte: o protocolo TCP e UDP, modelos de serviço e segmentação do TCP, cabeçalho do TCP, UDP e os pseudocabeçalhos TCP e UDP, gerenciamento de conexão, máquinas de estado finita e políticas de transmissão do TCP. É apresentado um algoritmo (SQM-Response) que utiliza as mensagens ICMP SQM para melhorias no controle de congestionamento no TCP.

Atualmente utiliza-se apenas a perda de pacotes como indicador de um congestionamento e a taxa de transmissão de segmentos é abaixada para evitar mais congestionamento. O TCP torna-se ineficiente em termos de desempenho utilizando essas características mencionadas acima. Com isso, vários autores indicam a Notificação Explícita de Congestionamento (ECN) como o melhor tipo de controle para melhorar o desempenho do TCP.

01. Controle de Congestionamento

O controle de congestionamento nas redes de computadores foi proposto inicialmente por Van Jacobson em 1997 [RFC 2001 e revisada em RFC 2581] e é importante devido ao fato de que host emissores e receptores serem de potências variadas, com isso, um buffer de receptor pode ter sua capacidade esgotada por um emissor mais veloz.

O controle de congestionamento continua a ser desenvolvido (item mais desenvolvido em informática), a fim de melhorar a performance das redes evitando a subutilização e a superutilização.

Atualmente quatro algoritmos governam o controle de congestionamento de redes com protocolo TCP: Slow-Start, Congestion Avoidance (ajustam a taxa de transmissão para evitar o congestionamento), Fast Retransmit e Fast Recovery (Detectam a perda de segmentos e ajustam a taxa de transmissão: Reno).

01.01 Slow-Start e Congestion Avoidance

No estabelecimento da conexão, o TCP começa a enviar segmentos com o tamanho de 1 ou 2 o MSS (Maximum Segmento Size) aumentando gradativamente caso o envio seja bem sucedido. Esse valor será guardado em CWND (Congestion Window – Janela de Congestionamento) que será sempre a medida dinâmica da capacidade de transmissão de dados da rede, enquanto que em RWND (Size Window Receive) é a capacidade de o receptor receber dados do transmissor. O tamanho inicial de CWND (IW - Initial Window) é tradicionalmente 1 MSS, mas novas propostas utilizam IW = 4*MSS.

A cada chegada de um ACK não duplicado CWND += 1*SMSS (Size Window Sender) , isso até que CWND seja menor que o limitante (SSTHRESH - Slow-Start Threshold). Este algoritmo é chamado de Slow-Start, algoritmo de partida lenta, dessa forma a transmissão dos dados se dá de forma exponencial durante o período que CWND é menor que o limitante.

Quando CWND ultrapassa o valor do limite, a transmissão se dá de forma linear, num processo chamado de Congestion Avoidance onde a CWND é aumentada de 1*FSS (Full Segment Size – Representa o maior tamanho de um segmento transmitido) a cada ciclo de transmissão e confirmação dos pacotes (O RTT - Round Trip Time - depende do ciclo mencionado anteriormente e do Timeout com base no "Algoritmo de Karn").

01.01.01 Inferência de Perda de Segmentos por Timeout

Após uma transmissão de segmento, o TCP aciona um temporizador de retransmissão e guarda uma cópia dos octetos enviados em uma fila de retransmissão. Quando um ACK não duplicado chega no emissor o segmento é retirado da fila de retransmissão, caso o ACK seja duplicado o segmento mais velho na fila é retransmitido e o temporizador tem seu tempo dobrado (Time Backoff) e novamente iniciado.

O temporizador (conforme sugestão o temporizador inicializar-se com 3 segundos) é calculado dinamicamente em função da média e da variância do RTT [RFC 2988], sendo assim é capaz de acompanhar o comportamento da rede nesse intervalo de tempo.

Sempre quando houver estouro do temporizador por um segmento que não foi recebido, o TCP deve ajustar seus parâmetros de congestionamento para evitar mais perdas. Ou seja, o CWND recebe 1*FSS e o limitante assume o maior valor entre o (FlightSize/2) e (2*SMSS) [RFC 2581]. (FlightSize: Somatório dos segmentos enviado sem recebimento de ACK)

Janela de Congestionamento do TCP (Slow-Start/Congestion Avoidance)[AND04]

01.02 Fast Retransmit e Fast Recovery (Reno)

Além da perda de pacotes, o TCP utiliza os algoritmos Fast Retransmit e Fast Recovery (RFC 2581) para agilizar a recuperação de dados. Em determinadas situações a espera de um ACK pode resultar numa espera do RTO muito grande, com isso, o receptor deve enviar um ACK-Duplicado toda vez que chegar um octeto com número de seqüência maior que o esperado.

Para um transmissor uma chegada de ACK-Duplicado pode ser 3 eventos: indicação de perda de segmento, reodernamento dos pacotes na rede e replicação dos dados na rede. Quando o transmissor recebe 3 ACK-Duplicados deve retransmitir o segmento pedido (Fast Retransmit) e acionar o algoritmo Fast Recovery. O segmento não é enviado no primeiro ACK-Duplicado porque ainda não é uma indicação de perda de pacotes.

Vern Paxson demonstrou que a espera por 3 ACK-Duplicados é a melhor medida pois deixa de retransmitir segmentos numa escala de 2,5:1 enquanto perde a oportunidade de 30 % dos envios de segmentos.

Ao entrar em Fast Recovery o TCP ajusta o limitante para o maior entre (flightSize/2) ou (2*SMSS). Enquanto a janela de congestionamento é ajustada para (limitante + 3*SMSS) no chamado "Inflação Artificial".

Durante o Fast Recovery cada ACK-Duplicado recebido incrementa a janela de congestionamento de (1*SMSS), neste momento se o tamanho da janela de congestionamento e o tamanho da janela do receptor permitirem o transmissor envia outro segmento.

Quando o receptor recebe um ACK confirmando a chegada do segmento enviado no início do Fast Recovery, o TCP ajusta a janela de congestionamento "Deflação da Janela" e sai do Fast Recovery voltando ao Slow-Start e ao Congestion Avoidance. Caso esse ACK não chegue é permanecido no Fast Recovery até ao estouro do RTO e retornando no Slow-Start.

Janela de Congestionamento do TCP (Fast Retransmit e Fast Recovery)[AND04]

01.03 TCP NewReno

TCP NewReno é um algoritmo de congestionamento idealizado por Reno, Sally Floyd e Tom Henderson em abril de 1999 (RFC 2582). Sua construção visualizou a solução da perda de múltiplos segmentos e a ocorrência de múltiplos Fast Retransmit.

Estando em Fast Recovery, após a retransmissão do segmento perdido, o TCP espera por confirmação dos segmentos enviados antes do TCP transmissor entrar em Fast Recovery ou parte desse segmento "ACK-Parcial". O algoritmo NewReno considera que os ACK-Parciais são mais perdas de segmentos e reenvia-los e ajusta a janela de congestionamento conforme abaixo.

01.03.01 Seqüência do Fast Retransmit / Fast Recovery no NewReno

 

1) Send high = $primeiro ISN (Send high: possui a responsabilidade de resolver o problema de múltiplos Fast Retransmit; ISN : número de seqüência)

2) Ao receber 3 ACK-Duplicados (Não em Fast Recovery)

2.1) if ( seq do ACK > send higth)
then entrar em Fast Recoverylimitante = (flightSize/2 > 2*MSS)? flightSize/2: 2*MSSrecover = maior seqüencial transmitido (possui a responsabilidade de resolver o problema da perda de múltiplos segmentos na mesma janela de congestionamento)

2.2) if ( seq do ACK <= send higth)

then ignorar esses ACKs e não entrar em Fast Recovery

3) Retransmitir o segmento e ajustar a janela de congestionamento para (limitante + 3*MSS)

4) Para cada ACK-Duplicado, somar (1*MSS) na janela de congestionamento

5) Transmitir um novo segmento se permito por RWND e a janela de congestionamento.

6) Where ( ACK não duplicado recebido )

6.1) if ( this.ACK confirmar todos os dados inclusive o recover )
then janela de congestionamento = (limitante < (fligthSize atual + 1*MSS))?limitante:(fligthSize atual+1*MSS) || ou valor de limitante do passo 1.
6.2) if (this.ACK == ACK Parcial)
then retransmitir o segmento solicitado neste ACKjanela de congestionamento = - Somatório dos dados confirmados pelo ACK e + 1*MSSenviar novo segmento se a janela de congestionamento e o RWND permitirem.Para o primeiro ACK-Parcial , recomeçar RTO.

7) Se expirar o tempo do contador RTO, send higth recebe o maior número de seqüência transmitido e sair do Fast Recovery.

8) Retornar ao passo 4 acima.

 

Utilizando a Deflação Parcial visa manter uma quantidade de dados boa no término do algoritmo Fast Recovery, isto evita a rajada de dados .

01.04 Reconhecimento Seletivo – SACK

Devido a falta de informação específica nos ACKs, o TCP só pode inferir em um segmento de cada vez. Quando há perda de mais de um segmento a retransmissão fica lenta e ocorre muitos reenvios.

O TCP origem quando recebe um ACK-Duplicado não sabe qual segmento realmente foi perdido. Essa informação tem como objeto apenas informar que um segmento chegou fora de ordem (Reconhecimento Cumulativo).

O SACK (Reconhecimento Seletivo) foi proposto por Matt Mathis et al. (RFC 2018), com o objetivo de solucionar o reconhecimento cumulativo. A proposta foi que o receptor enviasse no ACK a informação dos segmentos já recebidos, dando uma maior chance ao TCP origem de inferir nos envios dos segmentos perdidos. Essas informações de dados de recebimentos de segmentos são preenchidas em 32 bits no cabeçalho TCP ao invés de deslocamento de janela.

01.04.01 Estratégia de Informação

O SACK utiliza o campo "Options" do cabeçalho TCP para transportar as informações sobre os segmentos recebidos. No estabelecimento da conexão o campo SYN contém a informação de "SACK-Permited" informando que a origem está habilitada a receber informações do tipo SACK. O campo SACK-Permited possui dois campos (Figura abaixo):

1) O king que contém o tipo de opção =4 que significa a capacidade de transmitir e operar com SACK.

2) O length é o tamanho total do campo SACK-Permited.

Enquanto o receptor estiver recebendo segmentos na ordem certa, ele não utiliza a idéia do SACK (envia ACK convencional). Caso receba um segmento fora de ordem armazenará os segmentos em um bloco contíguo e informará ao emissor o seqüencial desses dados pelo campo Options do TCP. No campo Acknowledgement Number envia o número de seqüência recebido + 1, ou seja, o SACK não altera o valor desse campo no TCP. Complementando o SACK estará em funcionamento apenas em ACKs do tipo Duplicado ou Parcial.

O receptor ao enviar um ACK com o uso do SACK informa o maior número possível de blocos contíguos já recebidos. Quando um segmento repetido chega ao receptor, este deve enviar um ACK do tipo D-SACK (Duplicate-SACK) informando o número de seqüência desse octeto e o número do ultimo + 1.

A intenção do D-SACK é fornecer mais informação ao TCP de origem para que ele possa presumir os pacotes não recebidos e os duplicados, melhorando seus parâmetros de transmissão e seu desempenho.

Do lado do transmissor, toda informação vinda na proposta do SACK, servirá de base para inferir nos segmentos que serão retransmitidos, não ocorrendo retransmissões indevidas melhorando o desempenho do protocolo.

01.05 TCP Vegas

Em 1994, Lawrence Brakmo, Sean Malley e Larry Peterson, propuseram o TCP Vegas. Sua proposta visava melhor o desempenho do algoritmo de Reno de 40 a 70%. Na verdade, nenhuma referencia a essa implementação foi encontrada, e não se têm registros de implementação do Algoritmo de Vegas no TCP atual.

Enfim, a proposta do algoritmo TCP Vegas visa proporcionar ao TCP uma maior taxa de transferência de dados e diminuir a perda de segmentos na rede em períodos de congestionamento.

01.05.01 Retransmissão de segmentos

O RTT é calculado enviando um segmento ao destino e esperando o seu ACK e com isso calcula-se o RTT com base no round-trip. Logo o TCP Vegas é mais preciso que o TCP de Reno por usar a Granulação de Clock.

A janela de congestionamento é diminuída a cada perda de segmento e é feita apenas uma vez na janela de dados. Essas técnicas visam garantir que o TCP não baixe sua taxa de transmissão e com isso evita a diminuição do desempenho do protocolo.

01.05.02 Controle de Congestionamento do TCP Vegas

O TCP Vegas faz o controle de congestionamento comparando a taxa de transferência de dados esperada (TxEsperada) e a taxa efetivamente medida (TxMedida) a cada RTT. Comparam-se as duas de forma "pró-ativa" e altera-se o valor da janela de congestionamento.

Durante o Slow-Start, o TCP Vegas admite um aumento exponencial do RTT apenas uma vez. O valor da janela de congestionamento dobra de uma só vez (Karn). Esses valores alimentam os cálculos da TxEsperada e da TxMedida, e quando a TxMedida se torna menor que a TxEsperada o TCP Vegas deixa de executar o Slow-Start para executar o Congestion Avoidance.

01.06 Algoritmo SQM-Response

O algoritmo SQM-Response utiliza as mensagem SQL(Source Quench) com uma forma adicional para o controle de congestionamento. As mensagens ICMP, são avaliadas como mecanismos de notificação explicita do congestionamento (ECN) em redes que utilizam qualidade de serviço. Este algoritmo ainda não foi implementado em soluções do TCP e com isso não o abordaremos com ênfase.

02. Conclusão do Autor

Demonstrou a arquitetura do protocolo TCP e UDP bem como as suas características. Demonstrou os algoritmos de congestionamento de redes, com suas facilidades e defeitos.

Propôs o algoritmo SQM-Response que utiliza as mensagens ICMP SQM para enviar dados para o transmissor e receptor. Comparando os resultados de testes, o SQM-Response teve um ganho de desempenho em vários cenários, respeitando as metas do início do trabalho e habilitando-o para uma implementação no TCP.

03. Análise Crítica

Observando as implementações dos algoritmos de congestionamento de redes, constatamos que um bom trabalho nessa área está sendo feito. Essa observação também acha importante o desenvolvimento de ferramentas para as aplicações de redes de computadores. Num futuro, não muito longe, necessitaremos muito das redes de computadores, com isso, quanto mais evoluído estiver este tema, melhor será para as pessoas que usam as redes de computadores para enviar dados de todas as formas.

04. Referencias

[AND04]

Andrade, R.(2004) Algoritmo SQM-Response para Controle de Congestionamento do TCP em Redes com QoS. Universidade Federal de Pernambuco (UFPE) - Centro de Informática.

© www.projetoderedes.com.br - Termos e Condições de Uso