Esbel Tomás Valero Orellananbcgib.uesc.br/nbcgib/files/R-I/Redes-I-Aula-05.pdf · 2013-04-12 · Redes de Computadores - I A Camada de Enlace de Dados Esbel Tomás Valero Orellana

Redes de Computadores - I

A Camada de Enlace de Dados

Esbel Tomás Valero Orellana

[email protected], [email protected]

Curso de Ciência da Computação - UESC

Camada de Enlace de Dados – p. 1/44

Introdução

Objetivo : Estudar diferentes algoritmos que permitamuma comunicação eficiente e confiável entre doiscomputadores adjacentes no nível da camada de enlace dedados

Adjacentes⇒ fisicamente conectadas por um canalque funciona como um fio⇒ os bits são entregues naordem

Analissaremos aqui:1. questões de projeto da camada2. natureza dos erros, deteção e correção3. alguns protocolos4. exemplos de alguns protocolos desta camada


Questões de Projeto



funções implementadas nesta camada:1. interface de serviços à camada de rede2. lidar com erros de transmissão3. regular o fluxo de dados

Recebe pacotes e encapsula em quadros.

Serviços oferecidos à camada de rede1. Serviço sem conexão e sem confirmação2. Serviço sem conexão com confirmação3. Serviço orientado a conexões com confirmação



Serviço sem conexão e sem confirmação: enviaquadros independentes sem esperar confirmação derecebimento. Apropriado para canais com taxa deerros muito baixa ou para trafego em tempo real(dados atrasados causam mais problemas que dadosperdidos).

Serviço sem conexão com confirmação: cada quadroé confirmado individualmente. Util em canais nãoconfiáveis. (questão de otimização).

Serviço orientado a conexões com confirmação: seestabelece uma conexão entre as partes antes detransferir os dados. Os quadros são enumerados e acamada garante que cada quadro será entregue



Enquadramento

CabeçalhoCampo decarga util Final

Pacote

CabeçalhoCampo decarga util Final

Pacote

A camada de enlace de dados é responsável pordetetar e corregir erros no fluxo de dados resevidos dacamada física

A divição do fluxo de bits em quadros é uma tarefacomplicada.



Inserir intervalos de tempo entre os quadros

Dada a difuculdade de utilizar o tempo:1. Contagem de caracteres2. Bytes de flags, com isnserção de bytes3. Flags iniciais e finais, com incerção de bits4. Violação da codificação da camada física



Contagem de caracteres:

2 3 7 6 2 7 94433

2 3 6 2 7 9 843

37 5 3 8 12

Qantidade de caracteres

Quadro 1 Quadro 2 Quadro 3 Quadro 4

4 37 7 4 35 12

Quadro 1 Quadro 2 Quadro 3 Quadro 4

Contagem errada



Bytes de flags, com isnserção de bytes:



Este esquema, com algumas modificações, é utilizadono protocolo PPP

Este esquema está limitado pelo fato de utilizarcaracteres de 8 bits o que deixa de forma sistemas decodificação como o UNICODE

Se faz necessário um esquema que permita o uso decaracteres de tamanho arbitrário

Flags iniciais e finais, com incerção de bits: Cadaquadro começa e termina com um padrão de bits:01111110



Exemplo0110111111111111111100100111111001101111101111101111101001001111110

A inserção de bits permite delimitar corretamente osquadros

Violação da codificação da camada física: utiliza asparticularidades da codificação utilizada no meio físico

Muitas vezes utiliza-se uma combinação do método decontagem de caracteres com um dos outros métodos



Em serviços orientados a conexão confiável como tercerteza de que todos os quadros serão entregues nacamada de rede de destino?

feedback do receptor sobre o estado no final da linha:Envio de quadros de controle

introdução de timers na camada de enlace de dados

numeração seqüencial dos quadros

Controle de fluxo de dados

controle de fluxo baseado em feedback

controle de fluxo baseado na velocidade (não utilizadona camada de enlace de dados)


Detecção e Correção deErros


Detecção e Correção de Erros

As principais fontes de erros estão hoje nascomunicações em linhas de par trançado analógicas ena comunicação sem fio

Os erros acontecem com mais freqüência em grandesvolumes (rajadas) do que isoladamente: elesacontecem mais espaçadamente mas são maisdifíceis de corrigir

Utiliza-se então:1. códigos de detecção de erros2. códigos de correção de erros



palavra de código : m bits de dados, r bits de verificação (ouredundantes), tamanho da palavra n = m + r.distância de Hamming : número de posições de bits em queduas palavras de código diferem entre si.Dada uma palavra de código e um algoritmo de verificação

teremos 2m mensagens diferentes

nem todas as 2n palavras são usadas

na lista de palavras de código válida a menor distânciade Hamming entre duas palavras caracteriza adistância da Hamming do código



Para detectar d erros precisa-se de um código dedistância d + 1

Para corregir d erros precisa-se de um código dedistância 2d + 1

Exemplo de correção: código com um único bit deparidade permite detetar apenas erros isolados

Um código com m bits de mensagem e r bits deverificação que permita a correção de todos os errossimples deve satisfazer que m + r + 1 < 2r



Método de correção de erros de Hamming:

os bits da palavra de código sõ numeradosconsecutivamente de esquerda para direita

os bits que são potencias de 2 são bits de verificação

cada bit de verificação força a paridade de umdeterminado conjunto de bits

Exemplo:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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


Método de Hamming

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

1 V 2 V3 1+2 4 V5 1+4 6 2+47 1+2+4 8 V9 1+8 10 2+811 1+2+8 12 4+813 1+4+8 14 2+4+815 1+2+4+8


Método de Hamming

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

1 1 2 1 4 1 8 03 1 3 1 5 0 9 05 0 6 1 6 1 10 07 1 7 1 7 1 11 19 0 10 0 12 1 12 111 1 11 1 13 1 13 113 1 14 0 14 0 14 015 1 15 1 15 1 15 1

O erro está no bit→ 8 + 2 = 10


Método de Hamming

Para permitir que o método de Hamming permita corregirerros em rajada

uma sequência de k palabras é organizada em umamatriz, uma palavra por linha

os dados são transmitidos uma coluna de cada vez

no receptor a matris é reconstruida uma coluna decada vez

se ocorrer um erro em rajada de extensão menor ouigual a k no máximo um bit de cada palavra é afetadoe o método de haming conseguira corregir o erro.


Método de Hamming


Métodos de Detecção de Erros

Nos meios com baixa taxa de erros as técnicas dedetecção de erros são mais eficientes.

Um bit de paridade pode ser suficiente para detectarerros issolados. No entanto quandoa acontecem errosem rajada este método tem 50% de chances dedescubrir o fato

Um método alternatiovo pode ser montar ema matrizde n bits de largura e k bits de altura de dados. Um bitde paridade é determinado para cada coluna e fixadoà matriz como a última linha

Este método permite detectar uma rajada de erros deaté n bits.


Métodos de Detecção de Erros

Código polinomial ou código de redundância cíclica CRC.


Protocolos de Enlace deDados


Protocolos Elementares

Analizaremos inicialmente três protocolos com diferentesgraus de complexidade implementados dob as seguinteshipôtesis

Os processos da camada física, da camada de enlacee da camada de rede são independentes.

A máquina A quer mandar um fluxo grande de dados àmáquina B utilizando um serviço confiável, orientado aconexão

As máquinas estão livres de panes

Cada pacote aceito pela camada de enlace éencapsulado em um quadro

O receptor somente se ocupa de esperar quadrosCamada de Enlace de Dados – p. 25/44


Na máquina A:

A camada de enlace pega um pacote da camada deredevoid from_network_layer(packet * p);

Monta o quadro com o pacote acrescido deinformações de controle no cabeçalho.

O quadro é entregue à camada físicavoid to_physical_layer(frame * s);

O harware de transmissão calcula a acrecenta o totalde verificação ao final do quadro



Na máquina B:

A camada de enlace de dados aguardavoid wait_for_event(event_type * event);

O harware calcula o total de verificação do quadro(evento cksum_err )

A camada de enlace é informada (eventoframe_arrival ) e pega o quadro da camada física

void from_physical_layer(frame * r);

Extrai o pacote do quadro e entrega à camada de redevoid to_network_layer(packet * p);



1 / * determina tamanho máimo de pacotes em bytes * /2 #define MAX_PKT 10243 / * tipo booleano * /4 typedef enum {false, true} boolean;5 / * númers de confirmação em sequência * /6 typedef unsigned int seq_nr;7 / * definição de pacote * /8 typedef struct{9 unsigned char data[MAX_PKT];

10 } packet;11 / * definição do tipo de quadro * /12 typedef enum {data, ack, nak} frame_kind;13 / * quadros da camada * /14 typedef struct {15 frame_kind kind; //que tipo de quadro16 seq_nr seq; //número de sequência17 seq_nr ack; //número de confirmação18 packet info; //pacote da camada de rede19 };



Para ativar e desativar o timer (evento timeout )void start_timer(seq_nr k);

void stop_timer(seq_nr k);

Para ativar e desativar o time auxiliarvoid start_ack_timer(void);

void stop_ack_timer(void);

Para habilitar ou não a camada de redevoid enable_network_layer(void);

void disable_network_layer(void);

Para incrementar o número de sequência#define inc(k) if (k<MAX_SEQ) k=k+1; else k=0



Protocolo sem restrições

Dados apenas em um sentido

As camadas de rede estão sempre prontas

Ignoramos o tempo de processamento

O espaço no buffer é infinito

O canal de de comunicação não perde quadros nem édanificado

Maquina A Maquina B

Canalde

Comunicaçao



1 typedef enum {frame_arraival} event_type;2 #include "protocol.h"3 void sender1(void)4 {5 frame s; / * quadro enviado * /6 packet buffer; / * pacote enviado * /7 while(true){8 from_network_layer(&buffer);9 s.info = buffer;

10 to_physical_layer(s);11 }12 }13 void receiver1(void)14 {15 frame r;16 event_type event; / * nÃ£o usado * /17 while(true){18 wait_for_event(&event);19 from_physical_layer(&r);20 to_network_layer(&r.info);21 }22 }



Protocolo stop-and-wait




O canal de de comunicação não perde quadros nem édanificado

O buffer no receptor não é infinito e requer um ∆t parareceber quadro e transferir o pacote para a camada derede.



1 typedef enum {frame_arraival} event_type;2 #include "protocol.h"3 void sender2(void)4 {5 frame s; / * quadro enviado * /6 packet buffer; / * pacote enviado * /7 event_type event;8 while(true){9 from_network_layer(&buffer);

10 s.info = buffer;11 to_physical_layer(s);12 wait_for_event(&event);13 }14 }15 void receiver2(void)16 {17 frame r,s;18 event_type event; / * nÃ£o usado * /19 while(true){20 wait_for_event(&event);21 from_physical_layer(&r);22 to_network_layer(&r.info);23 to_physical_layer(&s);24 }25 }



Um canal com ruido




O buffer no receptor não é infinito e requer um ∆t parareceber quadro e transferir o pacote para a camada derede.

Os quadros podem ser danificados o perdidos nocanal de comunicação.



Se faz necessário:

inclusão de um timer que gere um evento timeout

inclussão de um número de sequência no cabeçalhode cada quadro enviado.

Para protocolos simples um número de sequência de umbit (o ou 1) é suficiente.

1 #define MAX_SEQ 12 typedef enum {frame_arraival, cksum_err, timeout} event_ type;3 #include "protocol.h"4



1 void sender3(void)2 {3 seq_nr next_frame_to_send;4 frame s; / * quadro enviado * /5 packet buffer; / * pacote enviado * /6 event_type event;78 next_frame_to_send = 0;9

10 from_network_layer(&buffer);11 while(true){12 s.info = buffer;13 s.seq = next_frame_to_send;14 to_physical_layer(s);15 start_timer(s.seq);16 wait_for_event(&event);17 if(event == frame_arrival){18 from_physical_layer(&s);19 if(s.ack == next_frame_to_send){20 stop_timer(s.ack);21 from_network_layer(&buffer);22 inc(next_frame_to_send);23 }24 }25 }26 }



1 void receiver3(void)2 {3 seq_nr frame_expected;4 frame r,s;5 event_type event;67 frame_expected = 0;8 while(true){9 wait_for_event(&event);

10 if(event == frame_arrival){11 from_physical_layer(&r);12 if (r.seq == frame_expected){13 to_network_layer(&r.info);14 inc(frame_expected);15 }16 s.ack = 1 - frame_expected;17 to_physical_layer(&s);18 }19 }20 }


Protocolos de Janela Deslizante

Protocolos de janela deslizantes : Mantém um conjunto denúmeros de sequência agrupados em: a janela detransmissão e a janela de recepção.

Necessidade de transmitir dados em ambos sentidos

Optimização dos circuitos utilizando apenas um paradados em ambos sentidos (fullduplex)

Técnica de superposição (piggybacking ) que retarda oenvio da confirmação para anexar a mesma nopróximo quadro de dados.

O protocolo deve entregar os pacotes à camada derede na mesma ordem em que foram entregues àcamada de enlace.



1 #define MAX_SEQ 12 typedef enum {frame_arraival, cksum_err, timeout} event_ type;3 #include "protocol.h"4 void protocolo4(void){5 seq_nr next_frame_to_send, frame_expected;6 frame r, s; packet buffer;7 event_type event;8 next_frame_to_send = frame_expected = 0;9 from_network_layer(&buffer);

10 s.info = buffer; s.seq = next_frame_to_send;11 s.ack = 1 - frame_expected;12 to_physical_layer(s); start_timer(s.seq);13 while(true){14 wait_for_event(&event);15 if(event == frame_arrival){16 from_physical_layer(&r);17 if(r.ack == frame_expected){18 to_network_layer(r.info);19 inc(frame_expected);}20 if (r.ack == nest_frame_to_send) {21 stop_timer(r.ack);22 from_network_layer(&buffer);23 inc(next_frame_to_send); } }24 s.info = buffer; s.seq = next_frame_to_send;25 s.ack = 1 - frame_expected;26 to_physical_layer(s); start_timer(s.seq); } }





Até agora supomos que o tempo para o pacote ir e aconfirmação chegar é insignificante

Exemplo: Canal de satélite de 50 kbps com retarde deida e volta de 500 ms enviando 1.000 bits.

... ...t=0 t=20ms t=40ms t=240ms t=260ms t=280ms t=500ms t=520ms t=540ms

O transmissor esteve bloqueado por mais de 90% dotempo



Permitir que o transmissor envie uma determinadaquantidade de quadros antes de bloquear (no exemploanterior o transmissor poderia mandar até 26quadros).

Necessário quando o produto da largura de bandapelo retardo é grande.

num canal de bbits/s que transmite quadros de l bitscom um retardo de R sgundos: u = l/(l + bR)

Que acontece se um quadro for danificado ou perdido?



Estratégia de go back n

Janela de recepção de tamanho 1: o receptor descartae não envia qualquer confirmação após um quadrodanificado:



Estratégia retransmissão seletiva

Os quadros que chegam após o quadro danificado sãoarmazenados no buffer

Geralmente se envia uma confirmação negativa


Documents

Esbel Tomás Valero Orellananbcgib.uesc.br/nbcgib/files/R-I/Redes-I-Aula-05.pdf · 2013-04-12 · Redes de Computadores - I A Camada de Enlace de Dados Esbel Tomás Valero Orellana