A comunicação entre as camadas de Rede e de Enlace é feita através de primitivas de

serviço (request, indication, response e confirm) da interface entre as duas camadas, como
definidas na parte relativa à apresentação do modelo OSI. Um esquema permitindo
demonstrar o modo de utilização das primitivas é mostrado na figura [Link]. Neste esquema,
representa-se nas extremidades a camada de Rede, caracterizada pelos dois sistemas
envolvidos no diálogo (no caso, A e B, que são as entidades pares) e no centro as camadas de
Enlace (de A e B), que tornam a comunicação transparente para as camadas de rede
envolvidas.
Os deslocamentos verticais das primitivas representam o tempo decorrido entre as
ocorrências destas (por exemplo, no caso das primitivas request e indication, o tempo
decorrido entre o envio da primeira pela camada de Rede do sistema A e a recepção da
segunda pela camada de Rede do sistema B).

camada de rede camada de enlace camada de rede

request
indication

response
confirm

sistema A sistema B

Figura [Link] - Primitivas de serviço trocadas entre as camadas de Rede e de Enlace.

b) O conceito de quadro
Para que o serviço seja oferecido à camada de Rede, a camada de Enlace utiliza-se dos
serviços fornecidos pela camada Física que, como já foi descrito na parte precedente, é
responsável da transmissão de bits de um ponto a outro na rede de comunicação, sendo que o
conjunto de bits transmitido pode sofrer distorções produzindo erros de transmissão. Uma
conseqüência típica pode ser que o número de bits recebidos seja inferior ao número de bits
enviados ou os valores de alguns bits podem ter sido modificados.
Com o objetivo de permitir um controle de erro eficiente, a camada de Enlace
decompõe as mensagens em porções menores denominadas quadros, aos quais são
adicionados códigos especiais de controle de erro. Desta forma, o receptor pode verificar se o
código enviado no contexto de um quadro indica ou não a ocorrência de erros de transmissão
e ele pode, assim, tomar as providências necessárias para evitar as conseqüências devido
àquele erro.

51
 A definição e delimitação dos quadros pode obedecer a diferentes políticas. Uma
possível política a adotar pode ser, por exemplo, a contagem de caracteres. Nesta política, é
introduzido um caracter especial que indica o número de caracteres compondo o quadro.
Deste modo, a nível da camada de Enlace do receptor, basta que a entidade leia este caracter e
em seguida conte o número de caracteres para definir o tamanho do quadro. O inconveniente
desta técnica, no entanto, é que o caracter que define o tamanho do quadro pode ser deturpado
durante a transmissão, o que significa que o receptor vai ler erroneamente os quadros
transmitidos. A figura [Link] ilustra este problema.
Uma técnica melhor, que apresenta uma solução a este problema, consiste na adição de
seqüências especiais de caracteres de modo a representar o início e fim da transmissão de um
quadro.

contadores de caracteres

(a) 5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6

quadro1 (5 car.) quadro2 (5 car.) quadro3 (8 car.)

erro con tador de caracteres

(b) 5 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6

Figura [Link] - Seqüência de caracteres: (a) sem erro; (b) com erro.

A figura [Link] ilustra um caso relativo a esta técnica, onde a seqüência de caracteres
DLE (Data Link Escape) e STX (Start of TeXt) é inserida para representar o início de um
quadro e a seqüência DLE e ETX (End of TeXt) para representar o fim do quadro. Esta técnica
apresenta, ainda, um ponto de vulnerabilidade: se, dentro do texto, uma seqüência de bits
coincide com uma das seqüências de caracteres citada (dado que os bits podem assumir
qualquer combinação de valores), a entidade receptora na camada de Enlace pode ser
“enganada” por esta seqüências e, assim, interpretar erroneamente o quadro.
A solução a este problema vem através da introdução, pela entidade de Enlace
emissora, de um caracter DLE adicional a cada vez que, em uma seqüência de bits da parte de
dados, aparecer um byte que coincidir com um caracter DLE. Desta forma, basta à entidade de
dados receptora eliminar os caracteres DLE dos dados antes de emiti-los à camada de Rede.
Isto vai permitir então, às entidades receptoras de Enlace, fazer a distinção entre as seqüências
delimitadoras de quadro (DLE-STX e DLE-ETX) das seqüências «acidentais» nos dados. Os
caracteres DLE introduzidos a nível dos dados são denominados caracteres de transparência.
Esta técnica de delimitação de quadros é utilizada em protocolos simples de comunicação
serial orientados à caracter.

52
 (a) DLE STX A B DLE C DLE ETX

(b) DLE STX A B DLE DLE C DLE ETX

Figura [Link] - (a) Dados enviados pela camada de Rede com seqüências de delimitação; (b)
idem, com introdução dos caracteres de transparência.

Uma técnica muito utilizada e definida mais particularmente para a utilização em redes
de comunicação é aquela em que os quadros são delimitados por uma seqüência de bits
particular, mas desta vez dissociados da codificação de caracteres. A seqüência 01111110 é
freqüentemente adotada para representar a delimitação dos quadros.
De maneira análoga à utilização dos caracteres de transparência da técnica anterior,
bits de transparência são introduzidos a nível da parte de dados para evitar a confusão, por
parte do receptor, com os delimitadores de quadro (esta técnica também é conhecida como
"bit-stuffing"). Assim, no receptor, a cada vez que 5 bits “1” consecutivos são detectados na
parte de dados, um bit 0 é adicionado após a seqüência. Do lado do receptor, a cada vez que
ocorrer uma seqüência de 5 bits “1” consecutivos de dados seguidos de um bit 0, este último
será eliminado da parte de dados. A figura [Link] ilustra a aplicação desta técnica. Em [Link]
(a) são apresentados os dados originais e, em [Link](b), os mesmos dados com a introdução
dos bits de transparência.

(a) 0 1 1 0 1 1 1 1 1 1 1 1 0 1

(b) 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1

bit de transparência

Figura [Link] - (a) dados originais; (b) dados com adição do bit de transparência

[Link]. O controle de erros

Os erros que podem ocorrer sobre os suportes de transmissão tem como causas os mais
diversos fenômenos físicos, como por exemplo, o ruído térmico, provocado pela agitação dos
elétrons nos cabos de cobre. Outro fenômeno importante são os ruídos impulsivos causados
pelo chaveamento de relês ou outros dispositivos eletromecânicos.
Verifica-se entretanto que, independentemente do fenômeno causador de erro, estes
tendem a gerar normalmente verdadeiros pacotes de erros (error bursts) e não erros simples.

53
Isto pode ter um aspecto positivo, uma vez que, num conjunto relativamente grande de bits,
um menor número de pacotes vai conter erros. Por outro lado, os erros agrupados em pacotes
são mais difíceis de modelizar e de detectar.
O controle de erros de transmissão é uma das funções mais importantes asseguradas
pela camada de enlace (usualmente implementado na subcamada LLC).
Os protocolos de controle de erro são caracterizados, em geral, pela definição de um
quadro de controle, correspondente a um reconhecimento positivo ou negativo. Caso a
entidade emissora receba um reconhecimento positivo de um quadro previamente enviado, ela
entende que aquele foi corretamente recebido.
Por outro lado, se ela recebe um reconhecimento negativo, ficará ciente de que o
quadro foi mal transmitido e que, neste caso, ele deverá ser retransmitido.
Ainda, se, por uma intensidade relativamente forte de ruído, o quadro inteiro não é
recebido pela entidade destinatária, esta não vai reagir ao quadro emitido e a entidade
emissora corre o risco de esperar indefinidamente pelo reconhecimento. I isto é evitado pela
adição de temporizadores, estabelecendo assim um tempo máximo de espera pelo
reconhecimento, antes da retransmissão (time-out). O tempo de espera deve ser determinado
em função dos atrasos relativos à transmissão dos quadros de modo que os quadros de
reconhecimento, se existentes, cheguem antes do esgotamento da temporização.
Deste modo, se o quadro ou o reconhecimento são perdidos, a temporização será
esgotada, podendo provocar a retransmissão do quadro. Neste caso, é possível que o quadro
seja aceito mais de uma vez pela camada de Enlace e transmitido à camada de Rede, causando
uma duplicação de quadros. Para evitar este problema, deve-se introduzir um mecanismo de
distinção dos quadros a fim de que o receptor possa separar os quadros duplicados de seus
originais.
Existem praticamente duas técnicas para o tratamento de erros. A primeira consiste na
introdução, a nível dos quadros, de informações suficientemente redundantes que permitam ao
receptor reconstituir os dados enviados a partir da informação recebida. A segunda técnica
consiste em adicionar unicamente um conjunto de informações redundantes o suficiente para
que o receptor possa detectar a ocorrência de um erro (sem corrigi-lo) e requisitar a
retransmissão do quadro. A primeira técnica é denominada código corretor de erros e a
segunda código detetor de erros.
Uma palavra de código de comprimento igual a n bits é composta de um número m de
bits de dados e um número r de bits de controle (n = m + r). Dadas duas palavras de código,
por exemplo, 10001001 e 10110001, é possível determinar de quantos bits elas diferem (no
caso do exemplo, elas diferem de 3 bits). Isto pode ser feito efetuando um “ou exclusivo”
entre as duas palavras e contando o número de bits "1" do resultado. A este número é dado o
nome de Distância de Hamming. Se a distância de Hamming entre duas palavras é d, serão
necessários d erros simples para transformar uma palavra em outra.

54
 A parte de dados da palavra de código pode ter até 2m valores diferentes. Devido à
forma com que os r bits de controle são calculados, nem todos os 2n valores possíveis para a
palavra de código são efetivamente utilizados. Sendo conhecida a técnica de cálculo dos bits
de controle, é possível fazer uma lista de todas as palavras de código válidas. Pode-se agora
verificar entre as palavras desta lista quais as que apresentam a menor distância de Hamming.
Esta será a distância de Hamming do código como um todo.
A propriedade de um código ser detetor ou corretor depende da sua distância de
Hamming. Para que seja possível detectar d erros numa palavra, é necessário que o código
tenha uma distância de Hamming de d+1. Isto porque é impossível que d erros possam
transformar uma palavra de código em outra palavra de código autorizada.
Por outro lado, para que seja possível corrigir d erros, a distância de Hamming do
código deverá ser de 2d + 1. Neste caso, mesmo que d erros simples ocorram, a palavra de
código continua ainda mais próxima da palavra transmitida.
Assim, fica claro que um código corretor de erros precisa ter palavras válidas mais
diferentes entre si do que as usadas com um código apenas detetor de erros.
Veremos a seguir exemplos de ambas as técnicas.

a) Os códigos de correção de erro (forward error control)

Os códigos corretores são utilizados para as transmissão de dados em casos
particulares como, por exemplo, quando os canais são unidirecionais ou quando é impossível
ou indesejável requisitar a retransmissão de um quadro.
Um exemplo extremamente simplificado de código corretor de erros pode ser visto a
seguir, sendo este composto de apenas 4 palavras de código: 0000000000, 0000011111,
1111100000 e 1111111111.
Este código apresenta uma distância de Hamming de 5, o que significa que ele pode
corrigir até 2 erros em cada palavra de código. Se o receptor detecta uma palavra de código
igual a 0000000111, ele é capaz de reconhecer a palavra original como sendo 0000011111,
pois esta é a palavra válida mais próxima da recebida. Por outro lado, se um erro triplo ocorre,
modificando, por exemplo, a palavra 0000000000 em 0000000111, o receptor será incapaz de
corrigi-lo.
Um código corretor de erros bastante usado na prática foi proposto pelo próprio
Hamming em 1950. Este código só pode corrigir erros simples, de 1 bit. Nele, o número
mínimo de bits de controle é dado por (m + r + 1) 2r, onde m é o número de bits de dados e
r o número de bits de controle. No código de Hamming, cada palavra é composta por uma
mistura de bits de dados e de controle, numerados da esquerda para a direita (assim, o bit 1 é o
primeiro da esquerda). Todos os bits que são potências de 2 (1, 2, 4, 8, 16, etc...) são usados
como bits de controle e os demais (3, 5, 6, 7, 9, 10, etc...) são usados como bits de dados
(figura [Link]).

55
 b its d e c o n tr

1 2 3 4 5 6 7 8 9 10 11

b its d e d a d o s

Figura [Link] - Palavra de código de 11 bits, com 7 bits de dados e 4 de controle

Um determinado bit de dados k tem sua paridade controlada pelos bits de controle que
fazem parte da expansão de k em potências de 2 (isto é, cuja soma é igual a k). Por exemplo, o
bit de dados 3 é controlado pelos bits 1 e 2, o bit 5 pelos bits 1 e 4, o bit 6 pelos bits 2 e 4, o
bit 11 pelos bits 1, 2 e 8, etc.
Os bits de controle são calculados de forma que um OU-exclusivo (XOR) entre eles e
o bit de dados que estes controlam sempre é par. Por exemplo:

(Bit de dados 3) XOR (Bit de Controle 1) XOR (Bit de controle 2) = 1.

Quando uma palavra de código é recebida, a unidade receptora inicializa um contador

em zero. Em seguida, a paridade de cada bit de controle é verificada. Se uma delas não estiver
correta, o número do bit de controle onde o erro foi detectado é adicionado ao contador. Se o
contador estiver em zero no final do processo, assume-se que não houve erro (ou, ao menos,
nada foi detectado). Se o contador não estiver em zero, o seu valor indica o número do bit
errado, que pode então ser corrigido por simples inversão, sem necessidade de retransmissão!
Para exemplificar, suponha que queremos transmitir o texto "Hamming code" entre
dois computadores. Adotou-se palavras de código com 7 bits de dados, de forma que o
número mínimo de bits de controle é 4. As palavras de código a transmitir são mostradas na
tabela abaixo:

Caracter Código ASCII Código de Hamming

H 1001000 00110010000
a 1100001 10111001001
m 1101101 11101010101
m 1101101 11101010101
i 1101001 01101011001
n 1101110 01101010110
g 1100111 11111001111
0100000 10011000000

56
 c 1100011 11111000011
o 1101111 00101011111
d 1100100 11111001100
e 1100101 00111000101

b) Os códigos de detecção de erro (feedback error control)

O exemplo mais simples de código detetor de erros é o controle de paridade. Ele é
baseado na adição de 1 bit de paridade à cada palavra de código enviada, obtido por meio de
um OU-exclusivo (XOR) dos bits que compõem a palavra. Por exemplo: para a seqüência
00100110, o bit de paridade vale 1 (0 xor 0 xor 1 xor 0 xor 0 xor 1 xor 1 xor 0 = 1, paridade
impar). Logo, o emissor envia a seqüência 001001101, que inclui o bit de paridade no final.
O receptor, por seu turno, realiza independentemente uma operação OU-exclusivo
sobre os bits que vão sendo recebidos (isto é, calcula a paridade novamente) e compara o
resultado obtido com o último bit enviado (que é o bit de paridade calculado pelo emissor); se
houver diferença, houve erro de transmissão (isto é, algum bit foi distorcido). No entanto, se
um número par de bits foi distorcido, o método não é capaz de detectar o erro. Assim, o bit de
paridade permite detectar unicamente erros simples.
Uma variante melhorada deste método é a paridade longitudinal, conhecida como BSC
(Block Sum Check), usada para o conjunto de palavras de código que compõem um quadro.
Aqui, além de acrescentar um bit de paridade para cada palavra, é calculada uma palavra
completa adicional, da forma mostrada no exemplo seguinte:

caracter ASCII binário bit paridade

‘R’ 52H 01010010 1
‘E’ 45H 01000101 1
‘D’ 44H 01000100 0
‘E’ 45H 01000101 1
BSC 00010110 1

A palavra BSC é enviada no final do quadro, após as palavras que fazem parte dos
dados a enviar. O receptor, a exemplo da técnica de paridade simples, calcula o BSC dos
dados a medida que são recebidos e compara o resultado com a última palavra enviada (que é
o BSC calculado pelo emissor); se houver diferença, houve erro de transmissão. Nesta
variante, erros que não foram detectados pela paridade simples provavelmente serão
detectados pela paridade longitudinal. Esta técnica é largamente utilizada em protocolos de
rede mais simples, mas tem uma eficiência limitada.
Um método de detecção de erros ainda melhor e largamente utilizado em redes locais é
a definição de um código polinomial, também denominado CRC (cyclic redundancy code).

57
Nos códigos polinomiais, considera-se que os bits de uma cadeia de caracteres são os
coeficientes de um polinômio, coeficientes estes, capazes de assumir apenas dois valores: 0 ou
1. Assim, um bloco de k bits é visto como uma série de coeficientes de um polinômio de k
termos, indo de xk-1 a x0. Por exemplo, a palavra 110001 contém 6 bits e representa o
polinômio x5 + x4 + 1 (coeficientes contados da direita para a esquerda).
A utilização de códigos de detecção polinomiais é baseada na escolha de um código
especial que caracteriza um polinômio gerador G(x). Uma exigência em relação a este
polinômio é que os bits mais significativo e menos significativo (correspondendo,
respectivamente aos coeficientes de mais alta ordem e de mais baixa ordem do polinômio)
sejam de valor 1. A técnica consiste em adicionar a um bloco de dados (caracterizando um
polinômio M(x)) um conjunto de bits de controle de modo que o quadro (dados + bits de
controle) seja divisível por G(x). Na recepção, a entidade de Enlace efetua a divisão dos bits
compondo o quadro pelo polinômio gerador. Caso o resto seja diferente de zero, é
caracterizada então a ocorrência de um erro de transmissão.
O Algoritmo básico para o cálculo do CRC é o seguinte:
Seja r o grau do polinômio gerador G(x); acrescentar r bits a zero no final da
r
mensagem a enviar, obtendo o polinômio x .M(x) ;
r
executar a divisão em módulo-2 do polinômio resultante x .M(x) por G(x);
r
Subtrai em módulo-2 o resto da divisão acima do polinômio x .M(x)
Resultado: quadro a transmitir com FCS

Vamos ilustrar o cálculo do CRC por meio de um exemplo:

Seja o Frame de dados a transmitir: M(x) = 11100110
Tomemos como polinômio gerador: G(x) = 11001 = x 4+x3+1
O Frame com acréscimo do zeros fica: xr.M(x) = 11100110 0000

r
A divisão do polinômio x .M(x) por G(x) é ilustrada a seguir:

1 0 1 1 0 1 1 0
1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0
1 1 0 0 1
0 0 1 0 1 1
0 0 0 0 0
0 1 0 1 1 1
1 1 0 0 1
0 1 1 1 0 0
1 1 0 0 1
0 0 1 0 1 0

58
 0 0 0 0 0
0 1 0 1 0 0
1 1 0 0 1
0 1 1 0 1 0
1 1 0 0 1
0 0 0 1 1 0
0 0 0 0 0
0 1 1 0
Para o exemplo acima, o resto R(x)= 0110 é a própria FCS. O Frame a transmitir é
dado por xr.M(x) - R(x) = 11100110 0110 (que corresponde ao frame original acrescido dos 4
bits de R(x)) .
Todas as operações descritas acima podem ser implementadas em hardware com
registradores de deslocamento e portas lógicas XOR.
Alguns exemplos de polinômios geradores freqüentemente adotados na detecção de
erros são:
CRC-12 = x12 + x11 + x3 + x2 + x1 + 1
CRC-16 = x16 + x15 + x2 + 1
CRC-CCITT = x16 + x12 + x5 + 1

Tomando-se o polinômio gerador da CCITT como exemplo, verificamos que é um

polinômio de ordem 16, de forma que serão acrescentados 16 bits de CRC em cada quadro.
Este polinômio é capaz de detectar:

todos os erros de paridade

todos os erros de 2 bits
todos os pares de erros de 2 bits cada
blocos de erros não excedendo 16 bits

Esta última técnica é bem mais eficiente que as anteriores, apesar de não ser infalível
(nenhuma delas é). Observe que os códigos detetores de erro não corrigem as palavras erradas
recebidas. Eles permitem apenas detectar a ocorrência do erro e o computador que recebe os
dados deve requerer uma retransmissão da palavra de código errada, ao contrário do que
ocorre com os códigos corretores !

[Link]. Análise de alguns protocolos de enlace

Os protocolos que analisaremos aqui vão permitir detectar uma série de problemas
relacionados ao controle de erros, que é a função mais importante a ser efetuada pela camada

59
de Enlace. A ordem de apresentação destes protocolos segue uma ordem de complexidade que
vai crescendo em função de novas hipóteses que levantaremos ao longo da análise. Nesta
análise, vamos considerar a comunicação entre entidades de comunicação situados em dois
sistemas distantes, denominados aqui A e B.
No primeiro caso, vamos supor que o suporte de comunicação utilizado permite uma
comunicação unidirecional apenas e que as camadas de Rede dos sistemas A e B estão sempre
prontas a enviar e receber dados, respectivamente. Ainda, neste caso, o canal de comunicação
é perfeito, ou seja, nenhum quadro é corrompido ou perdido. Assim, do lado do receptor, o
único evento possível é a recepção de quadros corretos. A figura [Link] ilustra a troca de
quadros entre as entidades localizadas nos sistemas A e B. Esta troca é realizada numa única
direção (de A para B), sem a ocorrência de perdas dada a consideração de que o canal de
comunicação é perfeito.
O segundo caso, indo do imaginário ao mais realista, leva em conta o fato de que a
camada de Rede do sistema receptor não tem capacidade de tratar os dados com a mesma
velocidade em que eles são gerados pela camada de Rede emissora. Por outro lado, a hipótese
de que o canal é perfeito e que os dados circulam numa única direção é ainda verdadeira.
O problema que se coloca, neste caso, é o de impedir que o emissor envie os quadros
numa velocidade superior àquela que o receptor pode consumi-los (tratá-los e retransmiti-los).
Uma forma de fazê-lo é estabelecer um mecanismo de temporização do lado do emissor de
modo a provocar um pequeno espaço de espera pelo tratamento do dado previamente enviado
antes do envio do seguinte. Esta solução não é, evidentemente, a melhor, uma vez que uma
má escolha do limite de espera pode conduzir a atrasos indesejáveis na comunicação.
A B

dados

dados

.
.
.
dados

Figura [Link] - Troca de quadros considerando um protocolo onde a comunicação é

unidirecional e sem corrupção nem perda de quadros.

Uma forma mais eficiente de fazê-lo é determinar uma maneira de informar ao

emissor, do estado corrente do receptor. Isto conduz à definição de quadros de
reconhecimento que serão enviados pelo receptor, após o tratamento do dado recebido, para
informar ao emissor que ele pode enviar o quadro de dados seguinte. Isto significa que, apesar
da comunicação ser considerada unidirecional, o canal conectando as duas camadas de Enlace

60