# Ligação de dados

Tramas, deteção de erros com CRC, retransmissão com ARQ e controlo de fluxo.

Página: https://resumos.rgo.pt/cadeiras/rc/ligacao-de-dados/

A camada física entrega bits; a camada de ligação de dados entrega **tramas** entre vizinhos diretos, com princípio, fim e garantia de que o conteúdo chegou intacto ou então volta a pedir-se. É o contrato “do próximo salto”, usado em cada cabo e em cada troço de rádio da rede.

## Delimitar e proteger a trama

O recetor precisa de saber onde começa e acaba cada trama. A técnica comum é reservar sequências especiais como delimitadores e fugir dessas sequências quando aparecem nos dados (**bit stuffing**): depois de cinco uns seguidos, o emissor insere um zero extra, e o recetor remove-o. Assim o delimitador nunca aparece por acidente dentro dos dados.

Uma trama típica junta os delimitadores ao cabeçalho, aos dados e ao CRC calculado no exemplo abaixo:

![Estrutura da trama do exemplo: delimitador, cabeçalho, dados 1010, CRC 011, delimitador.](https://resumos.rgo.pt/cadeiras/rc/ligacao-de-dados/figura-1.svg)

Proteger significa detetar erros. O mecanismo de trabalho é o **CRC** (verificação de redundância cíclica): o emissor divide os dados por um gerador acordado e cola o resto à trama; o recetor repete a divisão e só aceita a trama se o resto der zero. Todo o cálculo é feito bit a bit com ou-exclusivo, sem empréstimos nem transportes.

Segue um exemplo completo. Dados `1010`, gerador `1011` (grau 3, por isso três bits de CRC). Acrescenta três zeros aos dados: `1010000`. Divide por `1011`:

*   Primeiros quatro bits `1010`; começa por 1, faz ou-exclusivo com `1011` e dá `0001`; desce o zero seguinte e fica `0010`.
*   Começa por 0, não faz nada; desce o zero seguinte e fica `0100`.
*   Começa por 0, não faz nada; desce o último zero e fica `1000`.
*   Começa por 1, faz ou-exclusivo com `1011` e dá `0011`. Acabaram os bits: o CRC é `011`.

A trama transmitida é `1010011`. Confirma: dividir `1010011` por `1011` dá resto zero, por isso o recetor aceita. Se um bit se corromper pelo caminho, o resto deixa de dar zero e a trama é descartada. O CRC não corrige, só acusa, e fá-lo muito bem: com um gerador decente, erros de rajada curtos são sempre apanhados.[1](https://resumos.rgo.pt/cadeiras/rc/ligacao-de-dados/#user-content-fn-rajada)

Refaz a divisão do exemplo com o programa. Ele percorre os bits da esquerda para a direita, faz ou-exclusivo com o gerador sempre que o bit atual é 1, e imprime `CRC: 011`:

```python
dados = [1, 0, 1, 0]
gerador = [1, 0, 1, 1]
resto = dados + [0] * 3
for i in range(len(resto) - len(gerador) + 1):
    if resto[i] == 1:
        for j in range(len(gerador)):
            resto[i + j] ^= gerador[j]
print("CRC:", "".join(str(b) for b in resto[-3:]))
```

[Vídeo: How do CRCs work?](https://www.youtube.com/watch?v=izG7qT0EpBw)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=izG7qT0EpBw)

## ARQ: pedir outra vez

Descartar não chega; alguém tem de voltar a pedir. Os protocolos **ARQ** numeram as tramas e usam confirmações (**ACK**): o recetor confirma o que chegou bem, e o emissor retransmite o que não foi confirmado dentro de um temporizador. O **stop-and-wait** envia uma trama e para à espera do ACK; o **go-back-N** e a **retransmissão seletiva** mantêm várias tramas em voo e só repetem as que falharam.

O stop-and-wait mostra o custo da espera. Uma trama de 1000 bits a 1 Mbps demora 1 ms a transmitir; se a ida e volta (**RTT**) for 20 ms, a ligação passa 1 ms a trabalhar e 20 ms à espera. A utilização é $1 / (1 + 20)$, menos de 5 por cento. Em ligações longas ou rápidas, parar à espera é um luxo, e é por isso que os protocolos reais usam janelas de várias tramas.

## Controlo de fluxo

O emissor também não pode afogar o recetor. O **controlo de fluxo** limita quantas tramas podem estar em voo sem confirmação: a **janela deslizante** do emissor avança à medida que chegam ACKs, e o tamanho da janela é negociado com a capacidade do recetor. É uma ideia simples com uma consequência importante: a janela limita o débito máximo a $\text{janela} / RTT$, por muito rápida que seja a ligação. Vais reencontrar esta fração no [controlo de congestionamento](https://resumos.rgo.pt/cadeiras/rc/ligacao-de-dados/transporte-e-aplicacoes/), onde o limite passa a ser a rede em vez do recetor.

## Lista de verificação do projeto da camada 2

O trabalho laboratorial pede um protocolo de ligação de dados a funcionar. Antes de entregar, confirma:

1.  As tramas têm delimitadores e o recetor rejeita tramas partidas.
2.  O CRC é calculado e verificado nos dois lados, com um caso de teste que corrompe um bit de propósito.
3.  Há retransmissão com temporizador e números de sequência, sem duplicar entregas.
4.  O relatório mostra uma medição de utilização (como a do stop-and-wait acima) e explica o que limita o débito.

## Notas de rodapé

1.  A garantia exata depende do gerador: um CRC de grau $r$ apanha todas as rajadas de comprimento até $r$ e quase todas as mais longas. Ver Tanenbaum e Wetherall, Computer Networks, capítulo da camada de ligação de dados. [Voltar](https://resumos.rgo.pt/cadeiras/rc/ligacao-de-dados/#user-content-fnref-rajada)