Ligação de dados

Uma trama transporta um pacote entre equipamentos vizinhos. O recetor precisa de identificar onde começa e acaba e de verificar se deteta erros; delimitar, detetar e recuperar são operações diferentes. Ethernet descarta tramas com erros detetados, enquanto outros protocolos acrescentam confirmações, ACK, e recuperação por retransmissão, ARQ.

Delimitação e stuffing

Uma trama pode indicar comprimento, usar delimitadores especiais ou assinalar limites na codificação física. Com flag de início e fim, os dados nunca podem parecer flags.

No byte stuffing, precede bytes especiais com escape e transforma-os segundo a regra do protocolo. No bit stuffing de HDLC, o emissor insere um zero depois de cinco uns consecutivos entre flags, incluindo o CRC, e o recetor remove esse zero. O stuffing acontece depois de formar o conteúdo protegido e sai antes de o verificares.

Exemplo. Com flags 01111110, a sequência interior 01111110 nunca pode viajar como está, pois seria lida como limite. Se os dados contiverem cinco uns seguidos, por exemplo ...011111..., o emissor insere um zero: ...0111110.... O recetor, entre flags, remove o zero que se seguir a cinco uns. Cinco uns seguidos de zero no canal representam assim dados, não o fim da trama.

Não uses diretamente a dimensão do ficheiro para calcular o tempo de transmissão: inclui cabeçalhos, controlo de erros e escapes. Num byte stuffing, a sobrecarga depende dos bytes efetivamente presentes, não de uma percentagem universal.

Paridade, checksum e CRC

A paridade simples deteta qualquer número ímpar de alterações, mas falha com dois. Uma checksum soma unidades segundo um algoritmo. Um CRC interpreta bits como coeficientes de um polinómio binário e divide módulo 2, isto é, somar e subtrair são XOR sem transportes.

Para gerador $G$ de grau $r$, acrescenta $r$ zeros à mensagem $D$, divide $D\,2^r$ por $G$ e coloca o resto de $r$ bits no fim. $D\,2^r$ representa deslocar os bits da mensagem $r$ posições para a esquerda, não multiplicar números numa divisão decimal. A palavra transmitida fica divisível por $G$.

Exemplo próprio. Mensagem 1101, gerador 1011 de grau 3. Acrescentamos três zeros e alinhamos o primeiro 1 do gerador com o primeiro 1 ainda por eliminar:

  1101000
⊕ 1011000
= 0110000
⊕ 0101100
= 0011100
⊕ 0010110
= 0001010
⊕ 0001011
= 0000001

O resto já tem menos de quatro bits significativos, por isso a divisão termina. Escrevemo-lo com três bits, 001, e transmitimos 1101001.

Calcular bit a bit com registos

Um circuito pode fazer a mesma divisão enquanto os bits chegam. Cada registo guarda um bit do resto; os bits entram à direita, em C0, e avançam para a esquerda a cada passo, enquanto o bit que sai de C2 volta às ligações XOR. Para 1011, isto é, $x^3+x+1$, há XOR à entrada de C1 e de C0; se o retorno for 0, o XOR mantém o bit, e se for 1, troca-o.

Na geração, entram a mensagem e três zeros, e no fim os registos contêm 001. Na verificação, entra a palavra recebida completa, mensagem seguida do CRC, sem acrescentar zeros; altera um bit da trama e acompanha o resto. O circuito começa sempre a zero; esta demo mostra a divisão dos slides, sem as convenções adicionais de CRC usadas por protocolos concretos.

Resto zero não prova ausência de erro. Um erro múltiplo do gerador passa despercebido. Uma rajada vai do primeiro ao último bit alterado, incluindo bits corretos intermédios. Um CRC de grau $r$ com termo constante 1 deteta rajadas até $r$; outras garantias dependem do polinómio e do comprimento. A aproximação $2^{-r}$ exige um modelo de erros adequado.

A distância mínima de um código é a menor distância de Hamming entre duas palavras válidas, isto é, o menor número de bits diferentes. Um código de distância d deteta até d−1 alterações e, com descodificação apropriada, pode corrigir até $\lfloor(d-1)/2\rfloor$ alterações; isto não significa que qualquer verificador CRC faça essa correção.

Na paridade bidimensional, há verificações por linha e coluna. Um erro isolado pode ser localizado na interseção das verificações que falham, mas quatro erros nos cantos de um retângulo mantêm as paridades e podem passar despercebidos.

A deteção não corrige a trama. O recetor descarta-a ou pede uma retransmissão conforme o protocolo.

Stop-and-Wait e o bit alternado

O emissor envia uma trama e espera confirmação. Se o temporizador expirar, retransmite, porque um ACK ausente não distingue trama perdida de ACK perdido.

Números 0 e 1 impedem entregar duas vezes uma retransmissão. Se o recetor já entregou 0, volta a confirmá-lo sem entregar de novo e espera 1.

Define a convenção antes de seguir um traço. Aqui RR(n) significa «estou pronto para receber a trama n». Depois de receber 0 corretamente, o recetor envia RR(1). Outros enunciados podem confirmar explicitamente a última trama recebida, mudando a numeração do ACK.

O diagrama acompanha o emissor, com mais dados para enviar após cada confirmação. Um timeout mantém o bit da trama; só a confirmação esperada permite avançar. Cada envio reinicia o temporizador.

Eficiência sem perdas

Se a trama leva $t_f=L/R$ a transmitir, a propagação num sentido é $t_p$, e o ACK leva $t_a$, o ciclo sem processamento é $t_f+2t_p+t_a$. A utilização para Stop-and-Wait é:

$$U=\frac{t_f}{t_f+2t_p+t_a}.$$

Com $L=8000$ bits, $R=1$ Mbit/s, $t_p=20$ ms e ACK desprezável, $t_f=8$ ms e $U=8/48=1/6$. Se só 7600 bits forem dados úteis, o débito útil é $7600/0{,}048\approx158333$ bit/s.

Uma janela de $W$ tramas permite várias em trânsito. Sob estas mesmas hipóteses, a fração ideal de tempo com transmissões úteis é $U=\min(1,Wt_f/(t_f+2t_p+t_a))$. Com $W=6$, a ligação pode ficar ocupada continuamente. Com perdas, retransmissões e temporizadores reais, esta expressão já não basta.

Go-Back-N e Selective Repeat

Propriedade	Go-Back-N	Selective Repeat
Trama fora de ordem	Habitualmente descartada	Guardada dentro da janela
Confirmações	Cumulativas	Individuais ou seletivas
Retransmissão	Trama em falta e posteriores pendentes	Só tramas em falta
Memória no recetor	Menor	Maior, reordena antes de entregar
Limite usual com $m$ bits	$W\le2^m-1$	$W\le2^{m-1}$ para janelas iguais

Traço. O emissor envia 0, 1, 2 e 3. A trama 1 perde-se. Em Go-Back-N, o recetor entrega 0 e descarta 2 e 3. O emissor retransmite 1, 2 e 3 quando o protocolo o determinar. Em Selective Repeat, o recetor guarda 2 e 3 e, ao chegar 1, pode entregar 1, 2 e 3 por ordem.

Com dois bits, os números são 0, 1, 2 e 3. Considera Selective Repeat com janela três. O emissor envia 0, 1 e 2; o recetor entrega-os e avança, mas todas as confirmações se perdem.

Ponta	Janela após a perda dos ACKs	Estado
Emissor	0, 1, 2	Ainda espera confirmação, pode repetir 0
Recetor	3, 0, 1	Já entregou 0, 1 e 2, aceita números da janela nova

Uma repetição de 0 pertence à janela atual do recetor e pode parecer dados novos. O emissor não avançou; foi o recetor que avançou antes de as confirmações chegarem. Com janela dois, depois de entregar 0 e 1, o recetor espera 2 e 3, que não se sobrepõem à janela antiga, e a condição $2W\le2^m$ separa as duas janelas. Pressupõe ainda que tramas antigas não sobrevivem indefinidamente a várias voltas da numeração.

Resolver traços

Regista após cada evento: base da janela, próximo a enviar, pendentes, próxima esperada e dados entregues. Distingue chegar, ser confirmado e ser entregue, porque um duplicado pode ser confirmado sem ser entregue.

Calcula o tempo de timeout a partir da transmissão e do caminho do ACK, com a margem definida no enunciado. Um temporizador demasiado curto cria retransmissões inúteis; um demasiado longo atrasa a recuperação. Quando o enunciado inclui perdas probabilísticas, usa as hipóteses dadas, em vez de multiplicar uma eficiência sem perdas por um fator arbitrário.

Terminar uma transferência finita

A eficiência anterior descreve um fluxo prolongado. Num bloco curto, o arranque, a última janela incompleta e o instante pedido fazem diferença: receber o último bit não é receber o último ACK.

Considera dez tramas iguais, janela de três, transmissão de 2 ms por trama e propagação de 4 ms por sentido. Não há perdas, processamento nem duração de ACK; cada trama recebe confirmação imediata, cumulativa. O primeiro ACK chega em $2+2\times4=10$ ms, depois chegam os seguintes espaçados de 2 ms. Os timeouts não expiram.

Tramas, numeradas pela ordem de envio	Inícios no emissor	Fins no recetor	ACKs no emissor
1, 2, 3	0, 2, 4 ms	6, 8, 10 ms	10, 12, 14 ms
4, 5, 6	10, 12, 14 ms	16, 18, 20 ms	20, 22, 24 ms
7, 8, 9	20, 22, 24 ms	26, 28, 30 ms	30, 32, 34 ms
10	30 ms	36 ms	40 ms

Entre 6 e 10 ms, o emissor espera porque já tem três tramas pendentes. À chegada de cada ACK, liberta uma posição e envia a próxima. A décima começa aos 30 ms, termina de sair aos 32, chega inteira aos 36 ms e fica confirmada aos 40 ms.

A utilização prolongada seria $3\times2/10=0,6$. Dividir os vinte milissegundos de transmissão por 0,6 daria 33,33 ms, que não corresponde a nenhum dos dois instantes finais. Para um bloco finito, segue as transmissões e confirmações, incluindo a última janela.

A variante RR, REJ e SREJ

Nesta variante de Go-Back-N, a primeira trama fora de sequência desencadeia REJ(n), que pede a trama esperada n e a repetição das posteriores pendentes. As seguintes fora de ordem são descartadas sem repetir o mesmo REJ. Um timeout pode desencadear um pedido de RR para obter o estado do recetor. Num traço, segue a máquina de estados indicada no enunciado.

Em Selective Repeat, SREJ(n) pede apenas a trama n; RR(n) confirma o bloco contínuo até n−1. Isto permite confirmações cumulativas juntamente com rejeições seletivas. A tabela anterior descreve a família de protocolos; esta variante usa confirmação cumulativa com RR e rejeição seletiva com SREJ. Piggybacking inclui a confirmação em tramas de dados da direção contrária, reduzindo mensagens de controlo, mas exigindo gerir quando enviar uma confirmação sem dados para aproveitar.

Eficiência com erros

Define $a=t_p/t_f$, erro de trama independente com probabilidade $p_e$ e ACK de duração desprezável. Uma tentativa de sucesso tem probabilidade $1-p_e$. O número de tentativas A tem distribuição geométrica, $P(A=k)=p_e^{k-1}(1-p_e)$ e $E[A]=1/(1-p_e)$.

No Stop-and-Wait em que cada tentativa ocupa o mesmo ciclo:

$$U_{SW}=\frac{1-p_e}{1+2a}.$$

Em Selective Repeat, a expressão simplificada para a fração de entregas úteis é $E_{SR}=(1-p_e)\min(1,W/(1+2a))$. Mede débito útil normalizado, não ocupação física do canal: com janela saturada, as retransmissões podem manter o canal ocupado a 100% enquanto as entregas descem. Para Go-Back-N, a repetição de tramas posteriores aumenta o desperdício:

$$U_{GBN}=\begin{cases} \frac{1-p_e}{1+2ap_e},&W\ge1+2a,\\ \frac{W(1-p_e)}{(1+2a)(1-p_e+Wp_e)},&W<1+2a. \end{cases}$$

Exemplo. a=2, W=5 e $p_e=0{,}1$. Stop-and-Wait: 0,9/5=0,18. Selective Repeat: 0,9. Go-Back-N: $0{,}9/(1+4\times0{,}1)\approx0{,}6429$. Para obter débito de dados, multiplica ainda por R e pela fração útil da trama. Estes modelos não incluem todos os pormenores de timeout, perda de ACK ou correlação de erros.

Recuperação por salto e de extremo a extremo

ARQ por salto repete só onde houve perda, mas exige memória e controlo nesse salto. ARQ de extremo a extremo recupera nas pontas e pode repetir trabalho anterior. Podem coexistir, como Wi-Fi com TCP.

Num modelo ideal com K ligações iguais de capacidade C, perdas independentes p por ligação e retransmissão sem outras limitações, temos $C_{salto}=C(1-p)$ e $C_{extremos}=C(1-p)^K$. Para K=5 e p=0,1, dão 0,9C e 0,59049C. A diferença cresce com o número de saltos e as perdas. Não aplica estes valores automaticamente a TCP real, que também depende de janela, RTT, congestionamento e temporizadores.

Combinar BER, janela e redundância

Um problema pode pedir várias decisões sobre a mesma ligação. Resolve primeiro tempo e janela, depois erro de trama e só no fim débito útil. O exemplo seguinte usa Selective Repeat ideal, com ACK desprezável e erros independentes.

Dados: $R=4$ Mbit/s, $L=4000$ bits de dados por trama, propagação num sentido de 50 ms, BER $p_b=5\times10^{-5}$ e seis bits de sequência. A janela máxima usual é $W=2^{6-1}=32$.

1. Tempo de transmissão: $t_f=L/R=1$ ms. A razão $a=t_p/t_f=50$.
2. Sem erros: $U_0=\min(1,32/(1+2\times50))=32/101\approx0{,}316832$. O débito é 1,267327 Mbit/s, porque toda a trama contém dados neste exemplo.
3. Erro de trama: $p_e=1-(1-p_b)^{4000}\approx0{,}181273$. BER não é FER: basta um dos 4000 bits falhar.
4. Com erros: $U=(1-p_e)U_0\approx0{,}259399$, logo o débito útil é $RU\approx1{,}037594$ Mbit/s.
5. Janela para ocupar a ligação sem erros: $W\ge1+2a=101$. Selective Repeat precisa de pelo menos oito bits, pois sete só permitem janela 64 e oito permitem 128. Aumentar a janela não elimina a perda de capacidade causada pelos erros.

Agora compara duas codificações corretoras FEC. Acrescentam redundância para corrigir certos erros sem pedir outra transmissão. Uma acrescenta 10% de bits e deixa FER 0,08. Outra acrescenta 30% e deixa FER 0,03. Estas FER são dados do problema depois da correção. Mantém a janela 32 e os 4000 bits úteis.

Débito útil com FEC

Codificação	Bits transmitidos	$t_f$	Utilização $U$	Fração útil	Débito útil
Sem redundância	4000	1 ms	0,259399	1	1,037594 Mbit/s
Mais 10%	4400	1,1 ms	0,320317	$4000/4400$	1,164787 Mbit/s
Mais 30%	5200	1,3 ms	0,398342	$4000/5200$	1,225666 Mbit/s

Em cada linha, recalcula $a$ com o novo tempo e usa $D_{\text{útil}}=RU\times L_{dados}/L_{transmitido}$. A redundância ocupa a ligação e aumenta cada trama. A segunda codificação ganha nestes dados; com outras FER residuais, a ordem pode mudar.

Se uma trama tem FER $p_e$ e são permitidas no máximo duas tentativas independentes, a probabilidade de entrega é $1-p_e^2$. Isto mede sucesso até ao limite, não utilização nem débito. «Uma retransmissão» permite duas tentativas, a original e a repetição.

Do CRC da teoria ao BCC do laboratório

O CRC da teoria divide por XOR e deteta erros. O Lab 1 atual usa outro mecanismo, o BCC: BCC1 é A XOR C sobre endereço e controlo, BCC2 é o XOR de todos os bytes de dados, e o recetor confirma a igualdade.

O byte stuffing da porta série escapa 7E como 7D 5E e 7D como 7D 5D, calculado depois do BCC. O código-base abre a porta com O_NONBLOCK durante a configuração e depois retira essa flag; a leitura passa a bloqueante, com VMIN=1 e VTIME=0, por isso não existe um timeout de leitura de 0,1 s nessa configuração.

A API atual é llOpenTx, llOpenRx, llSend, llReceive, llCloseTx e llCloseRx; a API llopen, llwrite, llread e llclose aparece num documento complementar com outra interface, não no código-base de 2026/27. O relatório de eficiência arquivado indica 2025/2026 e também não descreve a edição atual.

Estado da receção no Lab 1

Para abrir a ligação, uma SET do emissor usa os bytes 7E 03 03 00 7E: flag, endereço, controlo, BCC1=03 XOR 03, flag. A UA correspondente usa 7E 03 07 04 7E. O recetor não deve procurar apenas os cinco bytes numa leitura: a biblioteca lê byte a byte e pode receber flags repetidas ou uma trama incompleta.

Byte aceite	Estado acumulado	Próximo campo esperado
7E	Início reconhecido	Endereço
03	Endereço guardado	Controlo
03	SET reconhecida	BCC1
00	Cabeçalho verificado	Flag final
7E	SET completa	Pode responder UA

Se o BCC1 estiver errado, ignora a trama sem agir sobre um controlo não verificado. O temporizador do emissor recupera a ausência de UA. Se a SET chegar de novo porque a UA se perdeu, o protocolo deve voltar a responder, permitindo que as duas pontas completem a abertura.

Durante a transferência, a ligação transporta tanto START e END como pacotes de dados da aplicação em tramas I, sem interpretar nomes, tamanhos ou campos da aplicação. Um duplicado pode voltar a receber RR, mas os seus dados não podem voltar a ser entregues.

Para testar, compara o ficheiro recebido com o original e depois introduz perdas em cada sentido. Cortar apenas Rx→Tx permite observar ACKs perdidos e duplicados, e o ficheiro final deve continuar igual. Sem recetor, o emissor deve terminar por falha ao esgotar o limite configurado, em vez de ficar a tentar indefinidamente. O guião atual também pede testes com ruído e interrupção temporária; a emulação ajuda a testar o protocolo, mas a demonstração docente usa portas série reais.

Passo	CRC da lição	BCC do Lab 1
Entrada	Mensagem mais r zeros	Endereço, controlo e dados
Conta	Divisão módulo 2	XOR de bytes
Verificação	Resto zero	BCC recalculado igual ao recebido

Simular uma perda na janela

Escolhe onde se perde uma das cinco tramas e compara a recuperação. O modelo usa janela de cinco e quatro bits de sequência, uma perda de dados e ACK sem perdas. Ignora propagação e temporizadores, porque mostra estado e retransmissões, não duração real.

Com perda de I(2), Go-Back-N precisa de oito transmissões de dados no modelo: as cinco iniciais e as repetições 2, 3 e 4. Selective Repeat precisa de seis: repete apenas 2, aproveitando 3 e 4 guardadas. Se a perda for a última trama, ambos repetem apenas essa trama; a vantagem depende de onde ocorre a perda e de quanto já foi enviado.