Protocolo Go-Back-N

Em um protocolo Go-Back-N (GBN), o remetente é autorizado a transmitir múltiplos pacotes (se disponíveis) sem esperar por um reconhecimento, mas fica limitado a ter não mais do que algum número máximo permitido, N, de pacotes não reconhecidos. Nesta seção, descreveremos o protocolo GBN com detalhes. Mas antes de continuar a leitura, convidamos você para se divertir com o applet GBN (incrível!) no Companion site Web.

A Figura 3.19 mostra a visão que o remetente tem da faixa de números de sequência em um protocolo GBN.

Se definirmos base como o número de sequência do mais antigo pacote não reconhecido e nextseqnum como o menor número de sequência não utilizado (isto é, o número de sequência do próximo pacote a ser enviado), então quatro intervalos na faixa de números de sequência poderão ser identificados. Os números de sequência no intervalo [0,base-1] correspondem aos pacotes que já foram transmitidos e reconhecidos. O intervalo [base,nextseqnum-1] corresponde aos pacotes que foram enviados, mas ainda não foram reconhecidos. Os números de sequência no intervalo [nextseqnum,base+N-1] podem ser usados para pacotes que podem ser enviados imediatamente, caso cheguem dados vindos da camada superior. Finalmente, números de sequência maiores ou iguais a base+N não podem ser usados até que um pacote não reconhecido que esteja pendente seja reconhecido (especificamente, o pacote cujo número de sequência é base).

Como sugere a Figura 3.19, a faixa de números de sequência permitidos para pacotes transmitidos mas ainda não reconhecidos pode ser vista como uma ‘janela’ de tamanho N sobre a faixa de números de sequência. À medida que o protocolo opera, essa janela se desloca para a frente sobre o espaço de números de sequência. Por essa razão, N é frequentemente denominado tamanho de janela e o protocolo GBN em si, protocolo de janela deslizante (sliding-window protocol). É possível que você esteja pensando que razão teríamos, em primeiro lugar, para limitar o número de pacotes pendentes não reconhecidos a um valor N. Por que não permitir um número ilimitado desses pacotes? Veremos na Seção 3.5 que o controle de fluxo é uma das razões para impor um limite ao remetente. Examinaremos outra razão para isso na Seção 3.7, quando estudarmos o controle de congestionamento do TCP.

Na prática, o número de sequência de um pacote é carregado em um campo de comprimento fixo no cabeçalho do pacote. Se k for o número de bits no campo de número de sequência do pacote, a faixa de números de sequência será então [0,2k 2 1]. Com uma faixa finita de números de sequência, toda a aritmética que envolver números de sequência deverá ser feita usando aritmética de módulo 2k . (Em outras palavras, o espaço do número de sequência pode ser imaginado como um anel de tamanho 2k , em que o número de sequência 2k 2 1 é imediatamente seguido pelo número de sequência 0.) Lembre-se de que rdt3.0 tem um número de sequência de 1 bit e uma faixa de números de sequência de [0,1]. Vários problemas ao final deste capítulo tratam das consequências de uma faixa finita de números de sequência. Veremos na Seção 3.5 que o TCP tem um campo de número de sequência de 32 bits, onde os números de sequência do TCP contam bytes na cadeia de bytes, em vez de pacotes.

As figuras 3.20 e 3.21 descrevem uma FSM estendida dos lados remetente e destinatário de um protocolo GBN baseado em ACK, mas sem NAK.

Referimo-nos a essa descrição de FSM como FSM estendida porque adicionamos variáveis (semelhantes às variáveis de linguagem de programação) para base e nextseqnum; também adicionamos operações sobre essas variáveis e ações condicionais que as envolvem. Note que a especificação da FSM estendida agora está começando a parecer um pouco com uma especificação de linguagem de programação. [Bochman, 1984] fornece um excelente levantamento sobre extensões adicionais às técnicas FSM, bem como sobre outras técnicas para especificação de protocolos baseadas em linguagens.

O remetente GBN deve responder a três tipos de eventos:

• Chamada vinda de cima. Quando rdt_send() é chamado de cima, o remetente primeiramente verifica se a janela está cheia, isto é, se há N pacotes pendentes não reconhecidos. Se a janela não estiver cheia, um pacote é criado e enviado e as variáveis são adequadamente atualizadas. Se estiver cheia, o remetente apenas devolve os dados à camada superior — uma indicação implícita de que a janela está cheia. Presumivelmente, a camada superior então teria de tentar outra vez mais tarde. Em uma implementação real, o remetente muito provavelmente teria colocado esses dados em um buffer (mas não os teria enviado imediatamente) ou teria um mecanismo de sincronização (por exemplo, um semáforo ou uma flag) que permitiria que a camada superior chamasse rdt_send() somente quando as janelas não estivessem cheias.
• Recebimento de um ACK. Em nosso protocolo GBN, um reconhecimento de pacote com número de sequência n seria tomado como um reconhecimento cumulativo, indicando que todos os pacotes com número de sequência até e inclusive n tinham sido corretamente recebidos no destinatário. Voltaremos a esse assunto em breve, quando examinarmos o lado destinatário do GBN.
• Um esgotamento de temporização. O nome ‘Go-Back-N’ deriva do comportamento do remetente em relação a pacotes perdidos ou demasiadamente atrasados. Como no protocolo pare e espere, um temporizador é usado para recuperar a perda de dados ou reconhecer pacotes. Se ocorrer o esgotamento da temporização, o remetente reenvia todos os pacotes que tinham sido previamente enviados mas que ainda não tinham sido reconhecidos. Nosso remetente da Figura 3.20 usa apenas um único temporizador, que pode ser imaginado como um temporizador para o mais antigo pacote já transmitido mas que ainda não foi reconhecido. Se for recebido um ACK e ainda houver pacotes adicionais transmitidos mas ainda não reconhecidos, o temporizador será reiniciado. Se não houver nenhum pacote pendente não reconhecido, o temporizador será desligado.

As ações do destinatário no GBN também são simples. Se um pacote com número de sequência n for recebido corretamente e estiver na ordem (isto é, os últimos dados entregues à camada superior vierem de um pacote com número de sequência n – 1), o destinatário enviará um ACK para o pacote n e entregará a porção dos dados do pacote à camada superior. Em todos os outros casos, o destinatário descarta o pacote e reenvia um ACK para o pacote mais recente que foi recebido na ordem correta. Dado que os pacotes são entregues à camada superior um por vez, se o pacote k tiver sido recebido e entregue, então todos os pacotes com número de sequência menores do que k também terão sido entregues. Assim, o uso de reconhecimentos cumulativos é uma escolha natural para o GBN. 

Em nosso protocolo GBN, o destinatário descarta os pacotes que chegam fora de ordem. Embora pareça bobagem e perda de tempo descartar um pacote corretamente recebido (mas fora de ordem), existem justificativas para isso. Lembre-se de que o destinatário deve entregar dados na ordem certa à camada superior. Suponha agora que o pacote n esteja sendo esperado, mas quem chega é o pacote n 1 1. Como os dados devem ser entregues na ordem certa, o destinatário poderia conservar o pacote n 1 1 no buffer (salvá-lo) e entregar esse pacote à camada superior mais tarde, após ter recebido o pacote n. Contudo, se o pacote n for perdido, os pacotes n e n 1 1 serão ambos finalmente retransmitidos como resultado da regra de retransmissão do GBN no remetente. Assim, o destinatário pode simplesmente descartar o pacote n 1 1. A vantagem dessa abordagem é a simplicidade da manipulação de buffers no destinatário — o destinatário não precisa colocar no buffer nenhum pacote que esteja fora de ordem. Desse modo, enquanto o remetente deve manter os limites superior e inferior de sua janela e a posição de nextseqnum dentro dessa janela, a única informação que o destinatário precisa manter é o número de sequência do próximo pacote esperado conforme a ordem. Esse valor é retido na variável expectedseqnum mostrada na FSM destinatária da Figura 3.21. Evidentemente, a desvantagem de jogar fora um pacote recebido corretamente é que a retransmissão subsequente desse pacote pode ser perdida ou ficar truncada, caso em que ainda mais retransmissões seriam necessárias.

A Figura 3.22 mostra a operação do protocolo GBN para o caso de um tamanho de janela de quatro pacotes. Por causa da limitação do tamanho dessa janela, o remetente envia os pacotes de 0 a 3, mas, em seguida, tem de esperar que um ou mais desses pacotes sejam reconhecidos antes de prosseguir. E, à medida que cada ACK sucessivo (por exemplo, ACK0 e ACK1) é recebido, a janela se desloca para a frente e o remetente pode transmitir um novo pacote (pkt4 e pkt5, respectivamente). Do lado destinatário, o pacote 2 é perdido. Desse modo, verifica-se que os pacotes 3, 4 e 5 estão fora de ordem e, portanto, são descartados.

Antes de encerrarmos nossa discussão sobre o GBN, devemos ressaltar que uma implementação desse protocolo em uma pilha de protocolo provavelmente seria estruturada de modo semelhante à da FSM estendida da Figura 3.20. A implementação provavelmente também seria estruturada sob a forma de vários procedimentos que implementam as ações a serem executadas em resposta aos vários eventos que podem ocorrer. Nessa programação baseada em eventos, os vários procedimentos são chamados (invocados) por outros procedimentos presentes na pilha de protocolo ou como resultado de uma interrupção. No remetente, esses eventos seriam: (1) uma chamada pela entidade da camada superior invocando rdt_send(), (2) uma interrupção pelo temporizador e (3) uma chamada pela camada inferior invocando rdt_rcv() quando chega um pacote. Os exercícios de programação ao final deste capítulo lhe darão a chance de implementar de verdade essas rotinas em um ambiente de rede simulado, mas realista.

Salientamos que o protocolo GBN incorpora quase todas as técnicas que encontraremos quando estudarmos, na Seção 3.5, os componentes de transferência confiável de dados do TCP. Essas técnicas incluem a utilização de números de sequência, reconhecimentos cumulativos, somas de verificação e uma operação de esgotamento de temporização/retransmissão. 

ATIVIDADE DE FIXAÇÃO