Aula 5 - Cama de Enlace (Cont.)

Prévia do material em texto

Redes de Computadores 
Prof. Me. Anderson Bessa da Costa 
 
 
 
Aula 05 
Cama de Enlace (Cont.) 
Falamos sobre quais são os meios físicos: par 
trançado (categoria 3, categoria 5), cabo coaxial, 
cabo de fibra ótica .. 
 
Codificação: como conectar dois blocos de 
montagem de modo que os bits possam ser 
transmitidos de um nó para o outro? 
-  NRZ 
-  NRZI 
-  Codificação Manchester 
-  Codificação 4B/5B 
Camada Física 
Na última aula .. 
Gerencia a transmissão, transporta quadro de bits, 
detecta e opcionalmente corrige os erros de 
transmissão; 
-  a cadeia de bits enviada ao nível de enlace é 
organizada em conjuntos de bits denominados 
quadros; 
 
Vimos como fazer o enquadramento: BISYNC, PPP, 
DDCMP, HDLC 
 
Detecção de Erros: bit paridade, paridade 
bidimensional, checksum, CRC 
Camada de 
Enlace 
Na última aula .. 
Continuação da Camada de 
Enlace ... 
n  Transmissão Confiável 
n  Protocolo Parar e Esperar 
n  Protocolo Janela Deslizante 
TRANSMISSÃO CONFIÁVEL 
 
Transmissão Confiável 
n  Quadros as vezes são modificados 
enquanto estão em trânsito .. 
n  Mesmo quando os códigos de correção 
de erro são utilizados, alguns erros são 
sérios demais para serem corrigidos; 
n  Como resultado, alguns quadros com 
erros terão de ser descartados; 
Transmissão Confiável 
n  Um protocolo no nível de enlace que 
deseje oferecer quadros de modo 
confiável precisa recuperar-se de 
a l guma fo rma desses quad ros 
descartados (perdidos); 
Transmissão Confiável 
n  Isto é feito por meio de uma combinação de 
dois mecanismos fundamentais: 
n  confirmação (ACK – acknowledgement) 
n  pequeno quadro de controle que um protocolo envia de 
volta ao seu par, dizendo que recebeu um quadro 
anterior; 
n  timeout 
n  se o emissor não receber uma confirmação depois de um 
período de tempo razoável, então ele retransmite o 
quadro original. Essa quantidade de tempo razoável é 
chamada de timeout (ou tempo limite); 
Transmissão Confiável 
n  A estratégia geral de usar confirmações 
e timeouts para implementar a entrega 
confiável é chamado de solicitação 
automática de repetição (normalmente 
abreviada de ARQ – Automatic Repeat 
Request); 
Transmissão Confiável 
n  Veremos os seguintes protocolos ARQ: 
n  Protocolo Parar e Esperar; 
n  Protocolo Janela Deslizante; 
PROTOCOLO PARAR E 
ESPERAR 
n  Ideia do protocolo parar e esperar 
n  Depois de transmitir um quadro, o 
emissor aguarda por um ACK antes 
de transmitir o próximo quadro; 
n  Se o ACK não chegar até um tempo 
l i m i t e ( t i m e o u t ) , o e m i s s o r 
retransmite o quadro original; 
Protocolo Parar e Esperar 
Linha do tempo mostrando quatro cenários diferentes para o algoritmo 
parar e esperar. (a) O ACK é recebido antes que o timeout se esgote; (b) o 
quadro original é perdido; (c) o ACK é perdido; (d) o timeout é disparado 
muito cedo. 
n  Se o ACK é perdido ou atrasado: 
n  O timeout do emissor se esgota e então é retransmitido o 
quadro original, mas o receptor irá pensar que este é o 
próximo quadro, uma vez que ele corretamente recebeu e 
confirmou (ACK) o primeiro quadro; 
n  Como resultado, cópias duplicadas do quadro irão ser 
entregues; 
n  Como resolver? 
n  Utilize 1 bit como sequência 
n  Quando o emissor retransmitir o quadro 0, o receptor 
poderá determinar que está vendo uma segunda cópia do 
quadro 0, ao invés de ver a primeira cópia do quadro 1, e 
então pode ignorar (o receptor ainda irá confirmar – ACK -, 
no caso do primeiro ACK ter sido perdido); 
Protocolo Parar e Esperar 
Linha do tempo para o protocolo parar e esperar 
com número de sequência de 1 bit 
n  O emissor tem apenas um quadro 
pendente no enlace por vez 
n  Isto está muito longe da capacidade do 
enlace 
n  Considere um enlace de capacidade de 
transmissão de 1.5 Mbps com um 
tempo de ida e volta de 45 ms (RTT – 
Round Trip delay Time) 
Protocolo Parar e Esperar 
n  Considere um enlace de capacidade de transmissão 
de 1.5 Mbps com um tempo de ida e volta de 45 ms 
(RTT – Round Trip Delay Time) 
n  O enlace tem um retardo x largura de 67.5Kb ou 
aproximadamente 8KB; 
n  Uma vez que o emissor pode enviar apenas um quadro por 
RTT e assumindo o quadro de tamanho 1KB 
n  Taxa de Envio Máximo 
n  Bits por quadro ÷ Tempo por quadro = 1024 × 8 ÷ 0.045 = 182 Kbps 
Ou 1/8 da capacidade total to enlace 
n  Para usar a capacidade total do enlace, o emissor deve 
transmitir 8 quadros antes de esperar por um ACK; 
Protocolo Parar e Esperar 
PROTOCOLO JANELA 
DESLIZANTE 
Protocolo Janela Deslizante 
Linha de tempo para o algoritmo 
de janela deslizante 
n  Emissor atribui um número de sequência denotado 
como SeqNum para cada quadro 
n  Assuma que é possível crescer infinitamente 
n  Emissor mantém três variáveis 
n  Sending Window Size (SWS) – Tamanho da Janela de Envio 
n  Limite superior do número de quadros pendentes (sem receber ACK) 
que o emissor pode transmitir 
n  Last Acknowledgement Received (LAR) – Últ ima 
Confirmação Recebida 
n  Número de sequência do último ACK recebido 
n  Last Frame Sent (LFS) - Último Quadro Enviado 
n  Número de sequência do último quadro enviado 
Protocolo Janela Deslizante 
n  Emissor também mantém as seguintes invariantes 
 LFS – LAR ≤ SWS 
Janela Deslizante do Emissor 
Protocolo Janela Deslizante 
n  Quando um ACK chega 
n  o emissor move o LAR para direita, permitindo então o 
emissor enviar mais um quadro 
n  Além disso, o emissor associa o timeout com 
cada quadro que transmite 
n  Ele retransmite o quadro se acontece timeout antes de 
receber o ACK 
n  Observe que o emissor precisa manter 
em buffer até SWS quadros 
n  pois precisa estar preparado para retransmiti-los até que 
sejam confirmados 
Protocolo Janela Deslizante 
n  Receptor mantém três variáveis: 
n  Receiving Window Size (RWS) – Tamanho da 
Janela de Recepção 
n  Limite superior do número de quadros for a de ordem que o 
receptor aceitará 
n  Largest Acceptable Frame (LAF) – Maior Quadro 
Aceitável 
n  Número de sequência do maior quadro aceitável 
n  Last Frame Received (LFR) – Último Quadro 
Recebido 
n  Número de sequência do último quadro recebido 
Protocolo Janela Deslizante 
n  Receptor também mantêm as seguintes invariantes 
 LAF – LFR ≤ RWS 
Janela Deslizante no Receptor 
Protocolo Janela Deslizante 
n  Quando um quadro com número de sequência 
SeqNum chega, o que o receptor faz? 
n  Se SeqNum ≤ LFR ou SeqNum > LAF 
n  Descarta (o quadro está fora da janela receptora) 
n  Se LFR < SeqNum ≤ LAF 
n  Agora o receptor precisa decidir ou não se envia um ACK 
Protocolo Janela Deslizante 
n  Seja SeqNumToAck 
n  Denota o maior número de sequência ainda não 
confirmado, tal como todos os quadros com 
número de sequência menor ou igual ao 
SeqNumToAck foram recebidos; 
n  O recep to r con f i rma o quadro do 
SeqNumToAck mesmo se pacotes com 
sequências mais altas chegaram 
n  Esta acumulação é dita acumulativa 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  O receptor então altera os valores 
n  LFR = SeqNumToAck and adjusts 
n  LAF = LFR + RWS 
 
Por exemplo, suponha LFR = 5 e RWS = 4 (ou 
seja, o último ACK que o receptor enviou foi 
para o número de sequência 5) 
⇒  LAF = 9 
 
Se quadros 7 e 8 chegarem, eles irão ser 
armazenados no buffer porque eles estão 
dentro do limite da janela receptor 
 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  Mas nenhum ACK será enviado até o 
quadro 6 ter chegado 
n  Quadros 7 e 8 estão fora de ordem 
n  Quadro6 chega (está atrasado pois foi 
perdido na primeira vez e teve de ser 
retransmitido) 
n  Agora o receptor confirma o Quadro 8 e 
aumenta o LFR para 8 e LAF para 12 
n  Problemas: 
n  Quando ocorre o timeout, a quantidade de 
dados em trânsito diminui 
n  Uma vez que o emissor é incapaz de avançar a sua 
janela 
 
n  Quando ocorre perda de pacote, este 
esquema não mais mantêm o enlace cheio 
n  Quanto mais tempo leva para notar que ocorreu uma 
perda de pacote, mais severo o problema se torna 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  Como melhorar: 
n  Negative Acknowledgement (NAK) 
n  Additional Acknowledgement 
n  Selective Acknowledgement 
n  Negative Acknowledgement (NAK) 
n  Receptor envia um NAK para o quadro 6 
quando o quadro 7 chega (como no 
exemplo anterior) 
n  Entretanto isto é desnecessário uma vez que o 
mecanismo de timeout do emissor irá ser suficiente para 
identificar esta situação 
 
n  Additional Acknowledgement 
n  Receptor envia um ACK adicional para o quadro 5 
quando o quadro 7 chega 
n  Emissor utiliza um ACK duplicado como um indicativo de perda 
de quadro 
 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  Selective Acknowledgement 
n  Receptor irá confirmar exatamente aqueles 
quadros que não foram recebidos, ao invés 
do número de quadros maior 
n  Receptor irá confirmar os quadros 7 e 8 
n  Emissor saberá que o quadro 6 foi perdido 
n  Emissor poderá manter o enlace cheio (complexidade 
adicional) 
Como selecionar o tamanho da janela? 
n  SWS é fácil de calcular 
n  Retardo × Largura 
n  RWS pode ser qualquer coisa 
n  Dois cenários comuns 
n  RWS = 1 
n  Nenhum buffer no lado do receptor para quadros 
que cheguem fora de ordem 
n  RWS = SWS 
n  O emissor pode armazenar quadros que o 
emissor transmite 
Não faz sentido RWS > SWS 
 POR QUÊ? 
Protocolo Janela Deslizante 
 
n  Número de Sequência Finito 
n  Número de sequência do quadro é especificado no 
campo do cabeçalho 
n  Tamanho finito 
n  3 bit: oito possíveis números de sequência: 0, 1, 2, 3, 4, 5, 6, 7 
n  É necessário para conseguir armazenar todas 
as possibilidades 
Protocolo Janela Deslizante 
n  Como distinguir entre diferentes encarnações 
do mesmo número de sequência? 
n  Número de possíveis número de sequência 
devem ser maior que o número de quadros 
pendentes permitidos 
n  Parar e Esperar: 1 quadro pendente 
n  2 números de sequência distintos (0 e 1) 
n  Seja MaxSeqNum a quantidade de números de 
sequência disponíveis 
n  SWS + 1 ≤ MaxSeqNum 
n  Isto é suficiente? 
Protocolo Janela Deslizante 
 SWS + 1 ≤ MaxSeqNum 
 
n É suficiente? 
n Depende do RWS 
n Se RWS = 1, então suficiente 
n Se RWS = SWS, então não é 
suficiente 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  Por exemplo, temos 8 números de 
sequência 
 0, 1, 2, 3, 4, 5, 6, 7 
 RWS = SWS = 7 
 
 Emissor envia 0, 1, …, 6 
 Receptor recebe 0, 1, … ,6 
 Receptor confirma 0, 1, …, 6 
 ACK (0, 1, …, 6) são perdidos 
 Emissor retransmite 0, 1, …, 6 
 Receptor está aguardando 7, 0, …., 5 
Para evitar isto, 
 Se RWS = SWS 
 
 SWS < (MaxSeqNum + 1)/2 
Protocolo Janela Deslizante 
n  Atende três diferentes objetivos 
n  Confiabilidade 
n  Preservar a ordem 
n  Cada quadro tem um número de sequência 
n  O receptor garante que não irá passar um 
quadro para o próximo nível do protocolo até 
que já tenha passada todos os quadros de 
número menor 
 
 
Protocolo Janela Deslizante 
Protocolo Janela Deslizante 
n  Quadro de Controle 
n  Receptor é capaz de “sufocar” o emissor 
n  Controla o emissor de “enchurrar” o receptor de dados 
n  Transmitir mais dados que o receptor é capaz de 
processar 
Interconexão de Redes Locais 
n  Ethernet 
ETHERNET 
Ethernet 
n  Tecnologia de redes locais mais bem-
sucedida dos últimos 20 anos; 
n  D e s e n v o l v i d o e m 1 9 7 0 , p e l o s 
pesquisadores no Xerox Palo Alto Research 
Center (PARC); 
Ethernet 
n  É uma rede de múltiplo acesso; 
n  Um conjunto de nós envia e recebe quadros por 
um enlace compartilhado; 
Ethernet 
n  Como mediar o acesso a um meio 
comparti lhado de forma justa e 
eficiente? 
n  Acesso Múltiplo por Detecção de Portadora Com 
Detecção de Colisão - CSMA/CD – Carrier Sense 
Multiple Access with Collision Detect); 
n  Detecção de Portadora: Todos os nós podem 
distinguir entre um enlace ocioso e ocupado; 
n  Detecção de Colisão: Um nó escuta enquanto 
transmite, e portanto pode detectar quando um quadro 
que ele está transmitindo interferiu;