Redes de computadores/Transmissão de dados confiável

Transferência confiável de dados

Dentre todos os problemas que existem para a implementação de redes de computadores, podemos dizer que a transferência confiável de dados é um dos principais. Essa tarefa ainda é mais complexa, pois a implementação do Protocolo de transferência confiável de dados é feita em um canal confiável, porém possui a camada de rede logo abaixo: um canal não confiável. Por exemplo: o TCP é um protocolo de transferência de dados confiável implementado sobre uma camada de rede fim-a-fim não confiável (IP).

Tranferência Confiável de dados (Fonte: Rede de Computadores e a Internet, 3ª Edição, James F. Kurose)

A figura do link acima ilustra como é implementado o serviço de transferência confiável de dados. Os pacotes são enviados do remetente ao destinatário vindo das camadas superiores até as inferiores. O protocolo de transferência confiável de dados é implementado na camada de transporte. rdt é a sigla para Reliable Data Transfer que significa transferência confiável de dados. Na figura, rdt_send() é chamada vinda da camada superior, (ex., pela aplicação). Passa dados para entregar à camada superior recetora. udt_send()é chamada pela entidade de transporte, para transferir pacotes para o recetor através do canal não confiável. rdt_rcv()é chamada pela entidade da camada inferior quando o pacote chega ao lado recetor do canal e deliver_data()é chamada pela entidade de transporte para entregar dados para camada superior.

Consideraremos apenas o caso de transferência unidirecional de dados, ou seja, do lado do remetente ppara o lado do destinatário. Os diagramas utilizados para a exemplificação dos protocolos utilizam máquinas de estados finitos (FSM) para especificar o protocolo transmissor e o recetor. É definido que estado é quando neste “estado” o próximo estado fica unicamente determinado pelo próximo evento.

FSM

A figura acima ilustra a abordagem FSM.

rdt1.0: Transferência confiável de dados sobre canais perfeitamente confiáveis

Primeiro é considerado um caso mais simples, na qual não há erro de bits na transmissão e também não há perdas de pacotes. As FSMs são separadas para transmissor e receptor na qual transmissor envia dados para o canal subjacente receptor lê os dados do canal subjacente. Como não a erro de bits ou perdas de pacotes o papel do remetente é simplesmente aguardar o pedido de envio da camada superior e enviar o pacote, voltando ao seu estado de espera de nova solicitação. O lado do destinatário fica em estado de espera de chegada de pacotes da camada inferior, recebe os dados, extrai e os envia para a camada superior.

RDT1.0

A figura acima ilustra a especificação da FSM do protocolo em questão.

rdt2.0: Canal com erros de bit

Já o rdt2.0 prevê envio de dados que podem chegar com erros ou corrompidos. Para solucionar tal problema, é implementado o conceito de resposta pelo destinatário ao remetente. Dessa forma o protocolo usa como resposta reconhecimento positivo (ACK) e reconhecimento negativo (NAK). Nos reconhecimentos (ACKs)o destinatário avisa explicitamente ao remetente que o pacote foi recebido corretamente e nos reconhecimentos negativos (NAKs)o destinatário avisa explicitamente ao remetente que o pacote tem erros. Quando o remetente recebe um NAK ele faz o reenvio do pacote.

RDT2.0

A figura acima ilustra a especificação da FSM do protocolo em questão.

rdt2.1: Solução para ACKs/NAKs perdidos

O rdt2.1 é uma versão que soluciona um problema que pode acontecer no rdt2.0 e na qual este não soluciona. Trata-se do sequenciamento dos pacotes e dos reconhecimentos positivos e negativos emitidos pelo destinatário. Dessa forma é evitado a transferência desnecessária de arquivos (duplicidade) e confusões em determinar para qual pacote foi enviado o reconhecimento.

RDT2.1 REMETENTE

RDT2.1 DESTINATÁRIO

As figuras acima ilustram a especificação da FSM do protocolo em questão. Notamos que agora o remetente e o destinatário possui duas vezes a mais o número de estados.

rdt2.2: Uso somente de ACKs

O rdt2.2 possui a mesma funcionalidade do rdt2.1, porém usando somente ACKs. Ao invés de enviar NAK, o destinatário envia um ACK para o último pacote recebido sem erro incluindo explicitamente o número de sequência do pacote sendo reconhecido. O recebimento de ACKs duplicados no remetente resulta na mesma ação do NAK, ou seja, a retransmissão do pacote corrente. Dessa forma nota-se uma maior simplicidade no FSM com relação ao rdt2.1

Protocolo rdt3.0

O que vimos até agora foi:

• Rdt1.0: um protocolo sobre um canal perfeitamente confiável;
• Rdt2.2: um protocolo mais real, onde há erro de bits.

Porém, há uma outra situação que normalmente ocorre em uma transferência de arquivos e que precisa ser tratada: a perda de pacotes. Implementaremos então um mecanismo para detetar um pacote perdido e retransmiti-lo. Tal mecanismo consiste da utilização de um temporizador de contagem regressiva que será acionado ao enviar cada pacote do remetente ao destinatário.

Uma ilustração do mecanismo apresentado é a seguinte:

• um pacote pkt0 é enviado ao remetente, e o temporizador relativo a esse pacote é acionado.
• pkt0 chega ao destinatário e este envia o ACK0.
• se ACK0 chegar ao remetente, o temporizador de pkt0 é parado e será enviado o pkt1. Porém, caso o temporizador chegue a 0 antes do ACK0 ser recebido, pkt0 é reenviado, e os passos anteriores são novamente repetidos.

Utilizando o temporizador, nem o remetente nem o destinatário conseguem identificar o que houve com o pacote enviado. Ele pode ter sido perdido, a resposta ACK pode ter sido perdida, ou simplesmente houve lentidão na rede, o que fez com que o temporizador zerasse antes do recebimento do pacote ou do ACK. A última situação resulta em pacotes duplicados, porém o protocolo rdt2.2 já corrige tal problema.

Transferência confiável de dados utilizando paralelismo

Com a utilização do protocolo rdt3.0 já são corrigidos os principais problemas que ocorrem em uma transferência de dados. Resta-nos agora melhorarmos seu desempenho.

Por ser do tipo pare-e-espere o protocolo rdt3.0 envia apenas um pacote por vez, e só envia o próximo quando receber a confirmação de recebimento do mesmo. Introduziremos então o conceito de paralelismo. Serão enviados vários pacotes sequencialmente(apesar do nome indicar, os pacotes não são enviados ao mesmo tempo), mesmo sem a receção dos pacotes anteriores. Isso implica em maiores números de sequência e na utilização de buffers do lado remetente, e também do lado destinatário no caso da repetição seletiva, para mais de um pacote.

Serão apresentados dois protocolos que utilizam a ideia de paralelismo,Go-Back-N e Repetição Seletiva.

Protocolo Go-Back-N

Para solucionar os problemas causados pelo comportamento pare e espere dos protocolos anteriores, foi desenvolvido o protocolo Go-Back-N. Este permite o envio de um determinado número de pacotes sem que os anteriores tenham sido reconhecidos. Para um melhor entendimento vamos analisar a seguinte figura:

É definido um número de pacotes que podem ser enviados sem que seja necessário aguardar pelo reconhecimento de cada um deles. Esta quantidade de pacotes pode ser vista como uma "janela". Na figura, os pacotes pretos são pacotes que foram corretamente enviados e já receberam reconhecimento (receberam o ACK do destinatário). Os pacotes azuis são pacotes que já foram enviados, mas ainda não foram reconhecidos, e os pacotes verdes são os próximos pacotes a serem enviados, já que ainda estão dentro dos limites da janela. Os pacotes vermelhos estão fora do limite da janela, logo não podem ser enviados ainda.

Nextseqnum é o número de sequência do próximo pacote a ser enviado. O pacote base é o pacote não reconhecido com número de sequência mais antigo. Quando este pacote for reconhecido, a janela irá se deslocar para a direita no espaço de números de sequência dos pacotes, permitindo o envio de outros pacotes. A janela "desliza", e com isso o protocolo Go-Back-N é também denominado protocolo de janela deslizante.

O lado remetente deve ser capaz de responder a 3 situações:

• Dados recebidos da camada de cima

Antes de criar e enviar um pacote, o protocolo deve verificar se há espaço na janela. Se não houver, os dados serão devolvidos, podendo ser enviados apenas quando um espaço for liberado;

• Recebimento de um ACK

Receber um ACK com número de sequência n indica ao remetente que todos os pacotes com número de sequência até n (inclusive) foram recebidos corretamente pelo destinatário, e assim a janela desliza. O pacote com número de sequência n+1 se torna a base;

• Esgotamento de temporização

É usado um temporizador para o pacote base. Se um ACK chegar antes do temporizador se esgotar, ele é reiniciado para o pacote seguinte. Se ele se esgotar, todos os pacotes que foram enviados mas que ainda não foram reconhecidos são reenviados.

O lado destinatário, ao receber um pacote com número de sequência n, que está na ordem esperada, envia um ACK correspondente e entrega os dados à camada superior. Caso o pacote recebido não esteja na ordem, ele será descartado e será reenviado um ACK para o último pacote recebido corretamente.

Esta característica garante que os pacotes sejam recebidos em ordem, mas descarta pacotes recebidos corretamente. Se por um lado isto gera um prejuízo na necessidade de retransmissão de dados (que ainda podem ser perdidos, gerando mais retransmissões), existe uma vantagem importante nesta opção: a simplicidade nos buffers do destinatário. Não será preciso armazenar pacotes fora de ordem, mas apenas o número de sequência esperado para o próximo pacote.

As figuras a seguir, retiradas do livro Computer Networking: A Top-Down Approach Featuring the Internet, de James F. Kurose e Keith W. Ross, 3ª edição, mostram as FSM do lado remetente e do destinatário, e a operação geral do protocolo, respetivamente.

Repetição Seletiva

O protocolo o Go-Back-N ou (GBN) resolveu um problema de vital importância para a transferência de dados, que é a questão do aproveitamento e da utilização do canal. Com o GBN há envio de mais de um pacote sem a obrigatoriedade de confirmação de recebimento do pacote anterior, ou seja, ele enche o canal com pacotes, N pacotes (um numero finito), tendo assim um melhor aproveitamento do canal, da largura de faixa do canal. Porém a forma como foi feito o GBN existem ainda algumas questões que prejudicam a transferência eficiente de dados. Estas questões são: o tamanho da janela grande e/ou o produto entre atraso e largura de faixa também grande. Pensemos sobre a janela, que é o mesmo conceito de janela do GBN. Vamos supor uma janela de tamanho para 100 pacotes. Se houver qualquer erro, pode ser perda do pacote enviado ou perda do ACK enviado pelo destinatário, terá que ser reenviado o pacote. O problema surge do fato que todos os pacotes posteriores ao que foi perdido terão de ser também reenviados. Se houver erro no 10º pacote, todos os 90 restantes juntamente com o 10º terão de ser reenviados, ou seja, haverá muitos reenvios desnecessários, tendo desta forma uma utilização também ineficiente, apesar de já ter melhorado. Imagine agora uma janela com 1000 pacotes! Quanto maior a janela, mais o problema se agrava. Se, também, o canal contiver uma taxa de erros alta, implica em maiores repetições. Como sabemos, os canais reais não transmitem sem erros. Por mais que o canal seja confiável e com baixa taxa de erros, esses erros existirão!

A repetição seletiva veio justamente melhorar esta questão. Agora, como o próprio nome sugere, não haverão reenvios desnecessários. Apenas será retransmitido o pacote que tiver algum problema. Com isto há um bom ganho de tempo nas transferências de dados. Analisemos agora a visão que tanto o remetente quanto o destinatário têm da janela, primeiramente para o remetente:

Em verde podemos ver os pacotes que foram enviados e seus ACK’s já foram recebidos. Em amarelo são os que foram enviados, mas ainda não chegou a resposta (recebimento do ACK). Em azul são os pacotes que foram autorizados a serem enviados, mas ainda não foram. Em branco são os pacotes que ainda não foram autorizados ao envio. Veja que alguns pacotes já tiveram confirmação de recebimento mesmo que pacotes anteriores ainda não tenham sido confirmados. Isto é uma grande diferença da janela do GBN, e é justamente a isso que veio a Repetição Seletiva, permitir que o destinatário reconheça pacotes fora de ordem, possibilitando assim retransmissões somente dos arquivos com algum problema.

Como no GBN, os pacotes à medida que são recebidos da camada superior recebem um número de sequência. Se este número estiver dentro da janela, então este pacote pode ser enviado, que são justamente os pacotes em azul. Ao ser enviado sua classificação muda para amarelo, e finalmente ao receber confirmação de recebimento por parte do destinatário o pacote passa a ser classificado como verde. Ao receber o ACK do pacote, se o pacote estiver no início da janela, então a janela pula uma ou mais posições à frente conforme os pacotes posteriores forem verdes ou não.

Outra questão é quanto ao problema da perca de pacotes. Para isto é usado temporização, só que na repetição seletiva, cada pacote tem de ter sua própria temporização, uma vez que só será retransmitido o pacote perdido.

Agora analisemos o destinatário. Os pacotes em lilás já foram recebidos, veja que eles estão fora de ordem, uma vez que existem pacotes anteriores ainda não recebidos. Esta é mais uma diferença, e uma causa da repetição seletiva. Esses pacotes ficarão em buffer no destinatário. Em cinza temos os pacotes que são aguardados, mas ainda não recebidos. Em azul são pacotes aceitáveis, que também são aguardados por estarem dentro da janela. Em branco são os pacotes não utilizados por estarem fora da janela. Como já dito, os pacotes já recebidos mas fora de ordem ficam armazenados em buffer. Ao receber um pacote e este pacote sendo o primeiro da janela, ele será enviado à camada superior juntamente com aqueles que já foram recebidos anteriormente e estão em sequência com este primeiro. Então a janela desliza à direita por um numero de pacotes igual á quantidade de pacotes que foram à camada superior. Em caso de o destinatário receber um pacote com número de sequência anterior ao número de inicio da janela (rcv_base), ou seja, pacote já recebido, mesmo assim será necessário o envio de um ACK para que o remetente possa movimentar sua janela à frente. Este fato pode ocorrer devido à perca do ACK, pois desta forma o remetente nunca receberá confirmação e então reenviará o pacote, mas o pacote já foi recebido pelo destinatário, porém o remetente não sabe disso, e por isso ele deve reenviar o ACK.

Na figura acima temos um exemplo de transmissão com a repetição seletiva. São enviados 4 pacotes (pkt0, pkt1, pkt2, pkt3). Porém o pacote pkt2 é perdido e só chegam ao destinatário os pacotes pkt0, pkt1 e pkt3. O destinatário recebe normalmente os três pacotes que chegaram, os armazena em buffer e envia seus respetivos ACK’s. O remetente recebe confirmação para os pacotes pkt0 e pkt1 e envia então os pacotes pkt4 e pkt5. Nesse ponto o tempo de vida do pacote pkt2 se esgota e então ele é reenviado. Os pacotes pkt4 e pkt5 são recebidos, armazenados em buffer e o destinatário envia seus ACK’s. Só então o pacote pkt2 é recebido. Agora então, como pkt2 está no inicio da janela ele é enviado para a camada superior juntamente com pkt3, pkt4 e pkt5 que estavam em buffer e na sequência de pkt2. É então enviado o ACK respctivo a pkt2 (ACK2).