Mecanismos ARQ e seus desempenhos esperados

Mecanismos ARQ (Automatic Repeat Request) servem para implementar Controle de erros em protocolos de comunicação. Esse serviço tem por objetivo garantir a entrega de PDUs no destino. Os mecanismos ARQ se baseiam na identificação de PDUs por números de sequência, no envio de confirmações de PDUs recebidas, na definição de tempos máximos de espera por confirmação (timeout) e por fim em retransmissões de PDUs extraviadas ou corrompidas. Os mecanismos ARQ conhecidos são:

Stop-and-Wait (Pare-e-Espere): só transmite a próxima PDU quando receber uma confirmação (ACK) da última PDU enviada. Retransmite a última PDU enviada se um tempo máximo de espera pelo ACK (ou timeout) for excedido.
Go-Back-N: transmite até N PDUs sem receber confirmação, quando então espera os ACK antes de enviar mais PDUs. Caso exceda o timeout de uma das PDUs enviadas, retransmite todas as PDUs a partir da PDU não confirmada. Esse mecanismo usa janela deslizante para controlar o envio das PDUs.
Selective Repeat: transmite até N PDUs sem receber confirmação, quando então espera os ACK antes de enviar mais PDUs. Caso exceda o timeout de uma das PDUs enviadas, retransmite somente essa PDU.

Na discussão a seguir será assumido que os mecanismos ARQ são utilizados em protocolos de enlace. Assim, daqui em diante as PDUs serão denominadas quadros.

Um mecanismo ARQ deve tratar corretamente diferentes tipos de erros, tais como:

Perda de quadro de dados (inclui quadro de dados recebido com erros e assim descartado).
Perda de quadro ACK
Quadro ACK atrasado, fazendo com que ocorra um timeout de espera por confirmação e consequente retransmissão

A rigor Stop-and-Wait ARQ já provê controle de erros, porém tem o potencial de causar uma baixa utilização do meio de transmissão. Os outros mecanismos, Go-Back-N e Selective Repeat, buscam melhorar o aproveitamento do meio, e assim estão também relacionados com o controle de fluxo. O serviço de controle de fluxo tem duas motivações principais:

Evitar que um transmissor mais rápido sobrecarregue um receptor
Melhorar o aproveitamento do meio de transmissão, quando há necessidade de confirmação de quadros e o meio apresentar um atraso de propagação significativo.

Desempenho do Stop-and-wait

O mecanismo Stop-and-wait apresenta desempenho que depende de seus parâmetros e de características físicas do enlace. Para avaliar seu desmepenho, deve-se determinar qual a taxa efetiva de transmissão que pode ser obtida. A taxa efetiva é definida com a razão entre quantidade de bits transmitidos (contidos em um ou mais quadros) e o tempo que foi necessário para que sejam entregues no destino. Quadros são considerados entregues somente quando o transmissor obtém uma confirmação do receptor. Isto não é a mesma coisa que a taxa de bits nominal do enlace, pois essa taxa informa o tempo que o transmissor leva para transmitir cada bit pelo meio de transmissão (ou melhor, o inverso de quanto tempo dura cada bit no meio). A taxa efetiva pode ser calculada descobrindo-se qual é a utilização do meio de transmissão. A utilização é um valor entre 0 e 1 que informa quanto tempo o meio foi de fato utilizado (i.e. quanto tempo o transmissor de fato precisou para transmitir um ou mais quadros), comparado com o tempo total necessário para fazer a entrega desses quadros. Por exemplo, se o transmissor levou 1 segundo para transmitir um quadro, e depois ficou 1 segundo esperando até receber a confirmação do receptor, a utilização será de 0.5 (o transmissor usou o meio durante 1 segundo, mas o tempo total para entregar o quadro foi de 2 segundos). Assim, as informações necessárias para calcular o desempenho do Stop-and-wait são:

Taxa nominal de transmissão, ou taxa de bits ( $B$ ): razão entre quantidade de bits que saem do transmissor e o tempo que leva para que saiam.
Tempo de transmissão ( $A_{t}$ ): tempo gasto pelo transmissor para transmitir um quadro. É o tempo gasto desde quando o primeiro bit do quadro começa a sair do transmissor, até quando o último bit termina de sair. Esse tempo depende da quantidade de bits transmitidos (F) e da taxa de bits nominal do meio (B): $A_{t}=F/B$
Atraso de propagação ( $A_{p}$ ): tempo gasto pelo sinal para se propagar desde o transmissor até o receptor. Independe da quantidade de bits transmitidos, pois é uma característica física do meio.
Outros atrasos ( $A_{o}$ ): outros atrasos envolvidos durante a entrega do quadro
Tempo de envio ( $A_{e}$ ): tempo necessário para que um quadro seja totalmente transmitido do transmissor até o receptor: $A_{e}=A_{t}+A_{p}$
Tempo de entrega (A): tempo necessário para que um quadro seja entregue no receptor, i.e. desde o instante em que o quadro começa a ser transmitido até quando o reconhecimento chega ao transmissor:
$A=A_{t}+2A_{p}+A_{t_{ACK}}+A_{o}$
Utilização do meio (U): razão entre o tempo em que o meio foi de fato usado pelo transmissor para transmitir o quadro, e o tempo total necessário para que o quadro seja considerado entregue:
$U={\frac {A_{t}}{A}}={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}+A_{o}}}$
Taxa efetiva de transmissão (E): a taxa de bits percebida pelo transmissor para fazer a entrega de quadros: $E=B\cdot U$
Timeout ( $T_{o}$ ): tempo máximo de espera por um reconhecimento.

O mecanismo ARQ Stop-and-wait é eficaz no controle de erros. Isto significa que ele garante que um quadro seja entregue no destino. Ser eficaz no controle de erros não significa ser eficiente. Se o atraso de propagação for da ordem de grandeza do atraso de transmissão, a utilização do meio se reduz significativamente. Por exemplo, se o atraso de propagação for metade do de transmissão:

$U={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}={\frac {A_{t}}{A_{t}+2A_{t}/2+A_{t_{ACK}}}}={\frac {A_{t}}{2A_{t}+A_{t_{ACK}}}}<{\frac {1}{2}}$

Já se esses dois atrasos forem iguais:

$U={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}={\frac {A_{t}}{A_{t}+2A_{t}+A_{t_{ACK}}}}={\frac {A_{t}}{3A_{t}+A_{t_{ACK}}}}<{\frac {1}{3}}$

E assim, quanto maior for o atraso de propagação, pior será a utilização do meio de transmissão. A raiz do problema está no tempo em que o meio deixa de ser usado por causa do atraso de propagação. Isto também quer dizer que uma certa quantidade de quadros poderia ser transmitida enquanto não chega a confirmação do primeiro quadro. Essa melhoria no ARQ se chama controle de fluxo, pois visa regular a quantidade de quadros que podem ser enviados de acordo com a capacidade do meio de transmissão e do sistema destino. O ARQ mais simples que implementa uma forma de controle de fluxo se chama Go-back-N.

Mecanismo ARQ Go-Back-N

Go-back-N transmite até uma certa quantidade de quadros, sem ainda ter recebido uma confirmação do primeiro quadro enviado. À medida que as confirmações forem recebidas, novos quadros podem ser enviados. Esse mecanismo está ilustrado na figura abaixo:

Figura 1: uma possível sequência de transmissão com Go-back-N

Para controlar a quantidade de quadros enviados usa-se a técnica de janela deslizante. A janela é o conjunto de quadros transmitidos e ainda não confirmados, e que precisam ser lembrados para caso seja necessário retransmiti-los. Assim, sempre que um novo quadro é transmitido aumenta-se o tamanho da janela em uma unidade, e quando um quadro é confirmado diminui-se o tamanho da janela em ao menos uma unidade. Há um tamanho máximo para a janela, que corresponde à quantidade máxima de quadros que podem ser transmitidos sem ter ainda uma confirmação de entrega. Esse tamanho máximo de janela é de grande importância para a eficiência do Go-back-N, pois tem influência direta na utilização máxima que pode ser obtida do meio de transmissão.

Um controle com janela deslizante precisa que se numerem os quadros sequencialmente, de forma a representar a ordem em que foram enviados. Assim, quadros fora de ordem não são aceitos no destino (ao menos no caso do Go-back-N). Por razões de praticidade, a quantidade de números de sequência necessária para o Go-back-N é igual ao tamanho máximo da janela + 1. Por exemplo, se o tamanho máximo da janela for 3, são necessários no mínimo 4 números de sequência (ex: 0 a 3). Se a quantidade de números de sequência for igual ao tamanho da janela, pode ocorrer um erro no controle de erros do mecanismo (tente descobrir que erro seria esse ...). A figura abaixo ilustra um exemplo em que se fazem transmissões de quadros com janela de tamanho máximo 3 (a janela a cada instante é destacada em amarelo, e os números correspondem aos números de sequência dos quadros):

Note que, assim como no Stop-and-wait, os quadros de reconhecimentos indicam qual o próximo quadro a ser aceito pelo destino. Além disso, o Go-back-N aceita reconhecimentos cumulativos. Quer dizer, se houver três quadros na janela de transmissão, e for recebido um reconhecimento relativo ao segundo quadro, o transmissor considera que tanto o primeiro quanto o segundo quadro foram recebidos com sucesso. Isto é possível pois nesse ARQ o receptor aceita apenas quadros em ordem.

Desempenho do Go-back-N

Mas qual deve ser a utilização do meio de transmissão com o Go-back-N ? Para responder a essa questão devem-se considerar duas situações:

O atraso para receber o primeiro ACK é maior ou igual ao tempo de transmissão para enviar todos os quadros permitidos pelo tamanho máximo de janela: essa situação está mostrada na figura 1, que mostra uma sequência de transmissão. A utilização nesse caso será:
$U={\frac {N\cdot A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}$
O atraso para receber o primeiro ACK é menor que o tempo de transmissão de uma janela de tamanho máximo: nesse caso, a utilização é máxima (= 1), pois todo o atraso de propagação é aproveitado para enviar quadros.

Utilização do meio com Go-Back-N sujeito a erros

Quando ocorrem erros, o Go-Back-N precisa reenviar todos os quadros da janela de transmissão. Um erro pode acontecer em qualquer quadro da janela de transmissão, sendo que a partir do quadro perdido deve-se esperar um tempo equivalente ao timeout de espera por reconhecimento. Somente após esse timeout o transmissor voltará a transmitir, retransmitindo quadros a partir do quadro perdido. Assim a transmissão de quadros se compõe de conjuntos de quadros transmitidos com sucesso, intercalados por tempos de espera timeout devido a quadro perdido (i.e. não reconhecido). Para calcular a utilização do Go-Back-N sujeito a erros, algumas simplificações serão assumidas:

A sequência de quadros transmitidos para fins de análise será longa (idealmente infinita).
A sequência de transmissão será modelada como a transmissão sucessiva de conjuntos de quadros, que correspondem às janelas de transmissão.
Cada conjunto de quadros transmitidos será entendido como até N-1 quadros enviados com sucesso seguidos por um quadro perdido, ou N quadros enviados com sucesso. Quando acontece um erro, o transmissor fica bloqueado até que aconteça um timeout (prazo de espera pela chegada de reconhecimento).

Cada conjunto de quadros apresenta uma certa utilização, que depende do quadro que sofreu erro. A utilização de cada conjunto pode ser calculada da seguinte forma:

A utilização na ausência de erros: é a utilização já definida anteriormente, que será chamada de $U_{N}$ , sendo calculada com a equação:
$U_{N}=min(1,{\frac {NA_{t}}{A}})$
A utilização no caso da ocorrência de um erro: é a utilização resultante de uma sequência de transmissão em que após um certo número de quadros enviados com sucesso acontece um erro, e será chamada de $U_{j}$ . O índice j se refere a quantidade de quadros enviados com sucesso antes do erro, e varia de 0 a N-1. Essa utilização pode ser calculada com a equação:
$U_{j}=min(1,{\frac {jA_{t}}{T_{o}+jA_{t}}})$

... sendo que o parâmetro A corresponde ao atraso para recepção de um reconhecimento (i.e. $A=A_{t}+2A_{p}+A_{t_{ACK}}$ ), $A_{t}$ é o atraso de transmissão, $A_{p}$ é o atraso de propagação e $T_{o}$ é o timeout de espera por reconhecimento.

A utilização total depende da probabilidade de acontecer cada uma das possíveis utilizações, que variam de $U_{0}$ a $U_{N-1}$ . Assumindo-se que a probabilidade de um quadro ser entregue sem erro seja dada pela variável $P_{q}$ , as probabilidades para cada caso são (obs: janela de tamanho N):

Posição do erro	Probabilidade
1	$1-P_{q}$
2	$P_{q}(1-P_{q})$
3	$P_{q}^{2}(1-P_{q})$
N	$P_{q}^{N-1}(1-P_{q})$

O caso especial em que não ocorrem erros tem probabilidade $P_{q}^{N}$ .

Obs: a variável $P_{q}$ corresponde à probabilidade de que um quadro seja enviado com sucesso, e seu ACK seja recebido pelo transmissor. Ela pode ser calculada assim:

$P_{q}=(1-BER)^{L+L_{Ack}}$

... sendo L o tamanho do quadro em bits, e $L_{Ack}$ o tamanho do quadro ACK também em bits.

A utilização total pode ser calculada fazendo-se uma média ponderada das utilizações $U_{j}$ correspondentes a cada caso. Os pesos a serem usados são as probabilidades definidas acima. A expressão resultante para a utilização pode ser escrita da seguinte forma:

$U=P_{q}^{N}\cdot U_{N}+\sum _{j=0}^{N-1}P_{q}^{j}(1-P_{q})\cdot U_{j}$

A expressão acima se aplica tanto a casos em que a utilização na ausência de erros for 100% (i.e. U = 1), quanto menor que 100% (U < 1).

Selective Repeat

O ARQ Selective Repeat aceita receber quadros fora de ordem, pois o receptor mantém uma janela de recepção com o mesmo tamanho que a janela de transmissão. Assim, o receptor aceita um quadro se seu número de sequência estiver contido na janela de recepção atual. O limite inferior da janela de recepção avança quando chega um quadro com o primeiro número de sequência da janela. Quando o limite inferior da janela avança, os quadros correspondentes são passados para a camada superior. O receptor sempre envia ACKs com o número do quadro que está no início da janela de recepção.

O desempenho do Selective Repeat, na ausência de erros, é o mesmo do Go-Back-N.

Utilização do meio com Selective Repeat sujeito a erros (EM REVISÃO ...)

Na presença de erros, o ARQ Selective Repeat proporciona uma utilização melhor que Go-Back-N. Abaixo segue a utilização obtida com Selective Repeat para os possíveis cenários de erros:

Quando a utilização na ausência de erros for < 1

Quer dizer, $N\cdot A_{t}<A_{t}+2\cdot A_{p}+A_{t_{ACK}}$ . Nesse caso a utilização é a mesma do Go-Back-N:

$U=N\cdot A_{t}\cdot ({\frac {P_{F}}{A_{t}+2\cdot A_{p}+A_{t_{ACK}}}}+{\frac {1-P_{F}}{T_{o}+A_{t}+2\cdot A_{p}+A_{t_{ACK}}}})$

Quando a utilização na ausência de erros for = 1

Quer dizer, $N\cdot A_{t}\geq A_{t}+2\cdot A_{p}+A_{t_{ACK}}$

Há dois casos a analisar:

Timeout maior que o tempo para enviar uma janela completa:
$U=P_{F}+{\frac {N\cdot A_{t}\cdot (1-P_{F})}{T_{o}+A_{t}+2\cdot A_{p}+A_{t_{ACK}}}}$
Timeout menor que o tempo para enviar uma janela completa:
$U=P_{F}+{\frac {N\cdot (1-P_{F})}{N+1}}$

Desempenho ARQ

Índice