Capítulo 5: Camada de Enlace 5: Camada de Enlace 5a-1 Protocolos da Camada de Enlace 5: Camada de Enlace 5a-2 Serviços da Camada de Enlace Enquadramento e acesso ao enlace: encapsula datagrama num quadro incluindo cabeçalho e cauda, implementa acesso ao canal se meio for compartilhado, ‘endereços físicos’ são usados em cabeçalhos de quadros para identificar origem e destino de quadros em enlaces multiponto Entrega confiável: Pouco usada em fibra óptica, cabo coaxial e alguns tipos de pares trançados devido a taxas de erro de bit muito baixas. Usada em enlaces de rádio, onde a meta é reduzir erros evitando assim a retransmissão fim a fim. 5: Camada de Enlace 5a-3 Serviços da Camada de Enlace (mais) Controle de Fluxo: compatibilizar taxas de produção e consumo de quadros entre remetentes e receptores Detecção de Erros: erros são causados por atenuação do sinal e por ruído receptor detecta presença de erros receptor sinaliza ao remetente para retransmissão, ou simplesmente descarta o quadro em erro Correção de Erros: mecanismo que permite que o receptor localize e corrija o erro sem precisar da retransmissão 5: Camada de Enlace 5a-4 Implementação de Protocolo da Camada de Enlace Protocolo da camada de enlace é implementado totalmente no adaptador (p.ex., cartão PCMCIA). Adaptador tipicamente inclui: RAM, circuitos de processamento digital de sinais, interface do barramento do computador, e interface do enlace Operações de transmissão do adaptador: encapsula (coloca número de seqüência, info de realimentação, etc.), inclui bits de detecção de erros, implementa acesso ao canal para meios compartilhados, coloca no enlace Operações de recepção do adaptador: verificação e correção de erros, interrompe computador para enviar quadro para a camada superior, atualiza info de estado a respeito de realimentação para o remetente, número de seqüência, etc. 5: Camada de Enlace 5a-5 Detecção de Erros EDC= bits de Detecção e Correção de Erros (redundância) D = Dados protegidos por verificação de erros, podem incluir alguns campos do cabeçalho • detecção de erros não é 100% perfeita; • protocolo pode não identificar alguns erros, mas é raro • maior campo de EDC permite melhorar detecção e correção 5: Camada de Enlace 5a-6 Uso de Bits de Paridade Paridade de 1 Bit: Detecta erros em um único bit Paridade de Bit Bidimensional: Detecta e corrige em um único bit 5: Camada de Enlace 5a-7 Métodos de “Checksum” Checksum “Internet”: Remetente considera dados como compostos de inteiros de 16 bits; soma todos os campos de 16 bits (usando aritmética de complemento de um) e acrescenta a soma ao quadro; o receptor repete a mesma operação e compara o resultado com o checksum enviado com o quadro. Códigos de Redundância Cíclica (Cyclic Redundancy Codes): Dados considerados como a seqüência de coeficientes de um polinômio (D) É escolhido um polinômio Gerador, (G), (=> r+1 bits) Divide-se (módulo 2) o polinômio D*2r por G. Acrescenta-se o resto (R) a D. Observa-se que, por construção, a nova seqüência <D,R> agora é exatamente divisível por G 5: Camada de Enlace 5a-8 Exemplo de CRC 5: Camada de Enlace 5a-9 Implementação de CRC (cont) Remetente realiza em tempo real por hardware a divisão da seqüência D pelo polinômio G e acrescenta o resto R a D O receptor divide <D,R> por G; se o resto for diferente de zero, a transmissão teve erro Padrões internacionais de polinômios G de graus 8, 12, 15 e 32 já foram definidos A ARPANET utilizava um CRC de 24 bits no protocolo de enlace de bit alternado ATM utiliza um CRC de 32 bits em AAL5 HDLC utiliza um CRC de 16 bits 5: Camada de Enlace 5a-10 Enlaces e Protocolos de Múltiplo Acesso Três tipos de enlace: (a) Ponto-a-ponto (um cabo único) (b) Difusão (cabo ou meio compartilhado; p.ex., Ethernet, rádio, etc.) (c) Comutado (p.ex., E-net comutada, ATM, etc) Começamos com enlaces com Difusão. Desafio proncipal: Protocolo de Múltiplo Acesso 5: Camada de Enlace 5a-11 Protocolos de Controle de Acesso ao Meio (MAC) Protocolo MAC: coordena transmissões de estações diferentes a fim de minimizar/evitar colisões. Tem 3 classes: (a) Particionamento do Canal (b) Acesso Aleatório (c) “Revezamento” Meta: ser eficiente, justo, simples, descentralizado 5: Camada de Enlace 5a-12 Protocolos de Particionamento do Canal TDM (Multiplexação por Divisão de Tempo): canal dividido em N intervalos de tempo (“slots”), um para cada usuário; ineficiente com usuários de pouco demanda ou quando carga for baixa. FDM (Multiplexação por Divisão de Freqüência): freqüência subdividida; mesmos problemas de eficiência do TDM. 5: Camada de Enlace 5a-13 Particionamento do Canal com CDMA CDMA (Múltiplo Acesso por Divisão por Código): explora esquema de codificação de espectro espalhado - DS (Direct Sequence) ou FH (Frequency Hopping) “código” único associado a cada canal; ié, particionamento do conjunto de códigos Mais usado em canais de radiodifusão (celular, satélite, etc) Todos usuários compartilham a mesma freqüência, mas cada canal tem sua própria seqüência de “chipping” (ié, código) Seqüência de chipping funciona como máscara: usado para codificar o sinal sinal codificado = (sinal original) X (seqüência de chipping) decodificação: produto interno do sinal codificado e a seqüência de chipping (observa-se que o produto interno é a soma dos produtos componente-por-componente) Para fazer CDMA funcionar, as seqüências de chipping devem ser mutuamente ortogonais entre si (i.é., produto interno = 0) 5: Camada de Enlace 5a-14 CDMA: Codificação/Decodificação 5: Camada de Enlace 5a-15 CDMA: interferência entre dois remetentes 5: Camada de Enlace 5a-16 CDMA (cont) Propriedades do CDMA: protege usuários de interferência (inclusive a proposital) (usado desde a Segunda Guerra Mundial) protege usuários do “multipath fading” (interferência entre 2 trajetórias do mesmo sinal, p.ex. o direto e por reflexão) em rádio permite a “coexistência” de múltiplos usuários e suas transmissões simultâneas com um mínimo de interferência (se os códigos deles forem “ortogonais”) 5: Camada de Enlace 5a-17 Protocolos de Acesso Aleatório Uma estação transmite aleatoriamente (ié, sem coordenação a priori entre estações) ocupando toda a capacidade R do canal. Se houver “colisão” entre as transmissões de duas ou mais estações, elas retransmitem depois de espera aleatória. O protocolo MAC de acesso aleatório especifica como detectar colisões e como se recuperar delas (através de retransmissões retardadas, por exemplo) Exemplos de protocolos MAC de acesso aleatório: (a) SLOTTED ALOHA (b) ALOHA (c) CSMA e CSMA/CD 5: Camada de Enlace 5a-18 Slotted Aloha O tempo é dividido em slots de tamanho igual (= tamanho de um pacote cheio) uma estação com pacote para enviar o transmite no início do próximo slot se houver uma colisão (supõe-se realimentação pelo canal, p.ex. o receptor avisa o remetente da colisão), a origem retransmite o pacote a cada slot com probabilidade P, até conseguir sucesso. Slots com Sucesso (S), com Colisão (C), ou Vazios (E) S-ALOHA é eficiente na utilização do canal; é completamente descentralizado. 5: Camada de Enlace 5a-19 Eficiência de Slotted Aloha Se N estações tiverem pacotes para enviar, e cada uma transmite em cada slot com probabilidade p, a probabilidade S de uma transmissão com sucesso é: Para uma estação específica, S= p (1-p)(N-1) Para que qualquer uma das N estações consiga transmitir com sucesso num slot, S = N p (1-p)(N-1) Valor ótimo de P: P = 1/N Por exemplo, se N=2, S= .5 Para N muito grande temos S= 1/e (aproximadamente, 0,37) 5: Camada de Enlace 5a-20 ALOHA puro (sem slots) Slotted ALOHA requer sincronização dos slots Um versão mais simples, ALOHA puro, não requer slots Uma estação transmite sem aguardar o início de um slot A probabilidade de colisão aumenta (pacote pode colidir com outros pacotes transmitidos dentro de uma janela duas vezes o tamanho de S-Aloha) A vazão é reduzida pela metade, ié S= 1/(2e) 0,18 5: Camada de Enlace 5a-21 CSMA (Carrier Sense Multiple Access) CSMA: escuta antes de transmitir. Se detecta que o canal está sendo usado, adia transmissão. CSMA persistente: tenta novamente assim que o canal se tornar ocioso (isto pode provocar instabilidade) CSMA não persistente: tenta novamente depois de intervalo aleatório Note: colisões ainda podem ocorrer, pois duas estações podem detectar o canal ocioso ao mesmo tempo (ou, melhor, dentro de uma janela de “vulnerabilidade” = retardo ida e volta entre as duas estações envolvidas) No caso de colisão, é desperdiçado todo o tempo de transmissão do pacote 5: Camada de Enlace 5a-22 Colisões em CSMA 5: Camada de Enlace 5a-23 CSMA/CD (Detecção de Colisões) CSMA/CD: escuta o meio e faz adiamento como o CSMA. Entretanto, colisões detectadas rapidamente, em poucos “intervalos de bit”. Transmissão é então abortada, reduzindo consideravelmente o desperdício do canal. Tipicamente, é implementada retransmissão persistente Detecção de colisões é fácil em rede locais usando cabo (p.ex., E-net): pode-se medir a intensidade do sinal na linha, detectar violações do código, ou comparar sinais Tx e Rx Detecção de colisões não pode ser realizada em redes locais de rádio (o receptor é desligado durante transmissão, para evitar danificá-lo com excesso de potência) CSMA/CD pode conseguir utilização do canal perto de 100% em redes locais (se tiver baixa razão de tempo de propagação para tempo de transmissão do pacote) 5: Camada de Enlace 5a-24 Detecção de colisões em CSMA/CD 5: Camada de Enlace 5a-25 Protocolos MAC de “revezamento” Até aqui já vimos: Protocolos MAC de particionamento de canal (TDM, FDM e CDMA) podem compartilhar o canal eqüitativamente; porém, uma única estação não consegue usar toda a capacidade do canal Protocolos MAC de acesso aleatório permitem que um único usuário utilize toda a capacidade do canal; entretanto, eles não conseguem compartilhar o canal de maneira justa (de fato, é comum observar a captura do canal) Também existem protocolos de “revezamento”... 5: Camada de Enlace 5a-26 Protocolos MAC de “revezamento” Protocolos MAC de revezamento conseguem tanto justeza como acesso individual a toda a capacidade do enlace, ao custo de maior complexidade de controle (a) Polling: uma estação Mestre numa rede local “convida” em ordem as estações escravas a transmitir seus pacotes (até algum Máximo). Problemas: custo de Request to Send/Clear to Send, latência, ponto único de falha (Mestre) (b) Passagem de ficha de permissão: a ficha de permissão é passada seqüencialmente de estação a estação. É possível aliviar a latência e melhorar tolerância a falhas (numa configuração de barramento de fichas). Entretanto, procedimentos complexos para recuperar de perda de ficha, etc. 5: Camada de Enlace 5a-27 Tecnologias de Rede Local Protocolos MAC usados em redes locais, para controlar acesso ao canal Anéis de fichas: IEEE 802.5 (Token Ring da IBM), para sala de computação, ou rede departamental, até 16Mbps; FDDI (Fiber Distributed Data Interface), para rede de Campus ou Metropolitana, até 200 estações, em 100Mbps. Ethernet: emprega o protocolo CSMA/CD; 10Mbps (IEEE 802.3), Fast E-net (100Mbps), Gigabit E-net (1,000 Mbps); de longe a tecnologia mais popular de rede local 5: Camada de Enlace 5a-28