Camada de Enlace de Dados - Questões de Projeto, Enquadramento, Controle de Fluxo e Erro

Capítulo 5 A Camada de Enlace de Dados Questões de Projeto da Camada de Enlace de Dados Enquadramento Controle de Fluxo Controle de Erro Detecção e correção de erros Protocolos de janela deslizante Exemplos de protocolos de enlace de dados A Camada de Enlace da Dados Neste capítulo estudaremos os princípios de projeto da segunda camada a camada de enlace de dados Nesse estudo trataremos de algoritmos que permitem uma comunicação eficiente e confiável entre dois computadores adjacentes no nível da camada de enlace de dados Por adjacentes queremos dizer que as duas maquinas estão fisicamente conectadas por meio de um canal de comunicação A Camada de Enlace da Dados Infelizmente os circuitos de comunicação produzem erros Além disso eles tem uma taxa de dados finita e há um retardo de propagação entre o momento em que o bit é enviado e o momento em que ele é recebido Essas limitações têm implicações importantes para a eficiência da transferência de dados Os protocolos usados para comunicações devem levar todos esses fatores em consideração Tais protocolos são o assunto deste capitulo Questões de Projeto da Camada de Enlace de Dados A camada de enlace de dados tem diversas funções entre as quais 1 Fornecer uma interface de serviço bem definida a camada de rede 2 Lidar com erros de transmissão 3 Regular o fluxo de dados de tal forma que receptores lentos não sejam atropelados por transmissores rápidos Questões de Projeto da Camada de Enlace de Dados Para alcançar esses objetivos a camada de enlace de dados recebe os pacotes da camada de rede e os encapsula em quadros para transmissão Cada quadro contém um cabeçalho header de quadro um campo de carga útil que conterá o pacote e um final trailer de quadro como mostra a Figura 1 Questões de Projeto da Camada de Enlace de Dados Figura 1 Relacionamento entre pacotes e quadros Questões de Projeto da Camada de Enlace de Dados O gerenciamento de quadros constitui o núcleo das atividades da camada de enlace de dados Muitos dos princípios que estudaremos aqui como o controle de erros e o controle de fluxo são encontrados em camadas superiores Isso ocorre porque a confiabilidade é um objetivo geral Porém independentemente do lugar onde elas são encontradas os princípios são quase idênticos Enquadramento A camada de enlace de dados dividi o fluxo de bits em quadros distintos calcula um pequeno valor chamado checksum soma de verificação para cada quadro e incluir essa soma de verificação no quadro quando ele é transmitido Quando um quadro chega a seu destino o checksum é calculado Enquadramento Se o checksum recém calculado for diferente do que está contido no quadro a camada de enlace de dados saberá que houve um erro e tomará providencias para lidar com ele por exemplo descartando o quadro com erro e possivelmente também enviando de volta um relatório de erros Enquadramento A divisão do fluxo de bits em quadros é mais difícil do que parece a primeira vista Um bom projeto deve tornar fácil para o receptor encontrar o início de novos quadros enquanto usa pouca largura de banda Aqui examinaremos três métodos 1 Contagem de caracteres 2 Bytes de flags com inserção de bytes 3 Flags iniciais e finais com inserção de bits Enquadramento O primeiro método de enquadramento que é a contagem de caracteres utiliza um campo no cabeçalho para especificar o numero de bytes do quadro Quando vê a contagem de bytes a camada de enlace de dados de destino sabe quantos bytes devem vir em seguida e conseqüentemente onde está o fim do quadro Essa técnica e mostrada na Figura 2a para quatro quadros de tamanhos 5 5 8 e 8 bytes respectivamente Enquadramento Figura 2 Um fluxo de caracteres a Sem erros b Com um erro Enquadramento O problema com esse algoritmo é que a contagem pode ser adulterada por um erro de transmissão Por exemplo se a contagem 5 no segundo quadro da Figura 2b se tornar 7 o destino perderá a sincronização e não será capaz de localizar o inicio do quadro seguinte Por essa razão o método de contagem de caracteres quase não é mais usado Enquadramento O segundo método de enquadramento que usa Bytes de flags com inserção de bytes contorna esse problema após um erro fazendo cada quadro começar e terminar com bytes especiais Normalmente o mesmo byte chamado byte de flag é usado como delimitador de inicio e de fim como mostra a Figura 3a na qual ele é representado por FLAG Enquadramento Figura 3 a Um quadro delimitado por bytes de flag b Quatro exemplos de seqüência de bytes antes e depois da inserção de bytes Enquadramento Dois bytes de flag consecutivos indicam o fim de um quadro e o início do próximo Assim se o receptor perder a sincronização ele poderá simplesmente procurar dois bytes de flag para encontrar o final do quadro atual e o início do seguinte Entretanto ainda existe um problema sério que precisamos resolver Enquadramento É bem possível que o byte de flag ocorra nos dados Essa situação ira interferir no enquadramento Uma forma de solucionar esse problema é fazer com que a camada de enlace de dados do transmissor inclua um caractere de escape especial ESC imediatamente antes de cada byte de flag acidental nos dados Assim o byte de flag de enquadramento pode ser distinguido daquele dos dados pela ausência ou presença de um byte de escape antes dele Enquadramento A camada de enlace de dados da extremidade receptora remove o byte de escape antes de entregar os dados a camada de rede Essa técnica é chamada inserção de bytes bit stuffing É claro que a próxima pergunta é o que acontecerá se um byte de escape ocorrer em uma posição intermediaria nos dados Nesse caso ele também será preenchido com um byte de escape Enquadramento No receptor o primeiro byte de escape é removido deixando o byte de dados seguinte que poderia ser outro byte de escape ou byte de flag Alguns exemplos são mostrados na Figura 3b Em todos os casos a seqüência de bytes entregue após a remoção dos bytes inseridos é exatamente igual a seqüência de bytes original Enquadramento Esse esquema de inserção de bytes é utilizado no protocolo PPP point to Point Protocol usado na camada de enlace Descreveremos o PPP mais adiante neste capitulo Enquadramento O terceiro método que usa Flags iniciais e finais com inserção de bits contorna uma desvantagem da inserção de bytes ou seja o fato de ela estar ligada ao uso de bytes de 8 bits O enquadramento também pode ser feito a nível de bits de modo que os quadros podem conter um número qualquer de bits compostos de unidades de qualquer tamanho Enquadramento Ele foi desenvolvido para o então muito popular protocolo de controle de enlace de dados de alto nível ou HDLC Highlevel Data Link Control Cada quadro começa e termina com um padrão de bits 01111110 um byte de flag Enquadramento Sempre que encontra cinco valores 1 consecutivos nos dados a camada de enlace de dados do transmissor insere um bit 0 no fluxo de bits que esta sendo enviado O USB Universal Serial Bus usa a inserção de bits Ao ver cinco bits 1 consecutivos sendo recebidos seguidos por um bit 0 o receptor remove automaticamente o bit 0 Enquadramento A inserção de bits assim como a inserção de bytes é completamente transparente para a camada de rede de ambos os computadores Se os dados do usuário contiverem o padrão de flag 01111110 esse flag será transmitido como 011111010 mas será armazenado na memória do receptor como 01111110 A Figura 4 mostra um exemplo de inserção de bits Enquadramento Figura 4 Inserção de bits a Os dados originais b Como os dados são exibidos na linha c Como os dados são armazenados na memória do receptor apos a remoção de bits Enquadramento Muitos protocolos de enlace de dados usam uma combinação desses métodos Um padrão comum usado para Ethernet e redes 80211 é fazer com que um quadro comece com um padrão bem definido chamado preâmbulo O preâmbulo é seguido por um campo de comprimento ou seja um contador no cabeçalho que é usado para localizar o final do quadro Controle de fluxo Outra questão de projeto importante que ocorre na camada de enlace de dados e também em camadas mais altas é aquela em que um transmissor quer enviar quadros mais rapidamente do que o receptor é capaz de aceitar O transmissor fica bombeando os quadros em alta velocidade até o receptor ser totalmente inundado Controle de fluxo Mesmo que a transmissão não contenha erros em um determinado ponto o receptor não será capaz de tratar os quadros a medida que eles chegam e começará a perder alguns deles São usadas duas abordagens para impedir que essa situação ocorra Controle de fluxo Na primeira chamada controle de fluxo baseado em feedback o receptor envia de volta ao transmissor informações que permitem ao transmissor enviar mais dados ou que pelo menos mostram ao transmissor qual a situação real do receptor Na segunda chamada controle de fluxo baseado na velocidade o protocolo tem um mecanismo interno que limita a velocidade com que os transmissores podem enviar os dados sem usar o feedback do receptor Controle de fluxo Neste capitulo estudaremos os esquemas de controle de fluxo baseado em feedback porque os esquemas baseados na velocidade nunca são utilizados na camada de enlace de dados Controle de erros Já para controle de erros há duas estratégias básicas para tratar os erros Ambas acrescentam informações redundantes aos dados enviados Controle de erros Uma estratégia é incluir informações redundantes suficientes para permitir que o receptor deduza quais foram os dados transmitidos utiliza códigos de correção de erros A outra é incluir apenas redundância suficiente para permitir que o receptor deduza que houve um erro mas não qual erro e solicite uma retransmissão utiliza códigos de detecção de erros Controle de erros O uso de códigos de correção de erros normalmente conhecido como correção adiantada de erros ou FEC Foward Error Correction A FEC é usada em canais com ruído porque as retransmissões podem ter erros tanto quanto a primeira transmissão Detecção e correção de erros Em canais altamente confiáveis como os de fibra é mais econômico utilizar um código de detecção de erros e simplesmente retransmitir o bloco com erro Porém em canais como enlaces sem fio que geram muitos erros é melhor adicionar redundância suficiente para que o receptor seja capaz de descobrir qual era o bloco transmitido originalmente Detecção e correção de erros Nem os códigos de correção de erros nem os códigos de detecção de erros podem lidar com todos os erros possíveis assim o código precisa ser forte o suficiente para lidar com os erros Detecção e correção de erros Há dois tipos de modelos O primeiro são aqueles que fazem surgir erros de único bit isolado E outro modelo consiste em erros que tendem a vir em rajadas em vez de isolados Os dois modelos importam na prática e possuem diferentes dilemas Detecção e correção de erros O fato de os erros acontecerem em rajadas tem vantagens e desvantagens em relação aos erros isolados de um único bit Uma vantagem é que os dados de computadores são sempre enviados em blocos de bits A desvantagem dos erros em rajada é que quando ocorrem são muito mais difíceis de corrigir que os erros isolados Vamos examinar os códigos de correção de erros e os códigos de detecção de erros Detecção e correção de erros Os códigos de detecção de erros normalmente são usados nas camadas de enlace rede e transporte Os códigos de correção e detecção de erros são matemática aplicada Assim não iremos detalhar os códigos Detecção e correção de erros Códigos de correção de erros Dentre os códigos de correção de erros se destacam Códigos de Hamming Códigos de convolução binário Códigos de ReedSolomon Detecção e correção de erros Todos esses códigos acrescentam redundância ás informações enviadas Um quadro consiste em m bits de dados ou seja de mensagens e de r bits redundantes ou seja verificação Em um código de bloco os r bits de verificação são calculados unicamente como uma função dos m bits de dados com os quais eles são associados como se os m bits fossem pesquisados em uma grande tabela para encontrar seus r bits de verificação correspondentes Detecção e correção de erros Em um código sistemático os m bits de dados são enviados diretamente com os bits de verificação em vez de ser codificados eles mesmos antes de ser enviados Em um código linear os r bits de verificação são calculados como uma função linear dos m bits de dados A operação Ou exclusivo XOR é uma escolha popular Isso significa que a codificação pode ser feita com operações como multiplicações de matrizes ou circuitos lógicos simples Detecção e correção de erros Considere que o tamanho total de um bloco seja n isto é n m r Descreveremos isso como código nm Uma unidade de n bits contendo bits de dados e verificação é conhecida como palavra de código de n bits A taxa de código ou simplesmente taxa é a fração da palavra de código que transporta informações não redundantes ou mn Detecção e correção de erros As taxas usadas na prática variam bastante Elas poderiam ser ½ para canal com ruído em que metade da informação recebida é redundante ou perto de 1 para canais de alta qualidade Dadas duas palavras de código que podem ser recebidas ou transmitidas é possível determinar quantos bits correspondentes diferem basta efetuar uma XOR entre as duas palavras de código e contar o numero de bits 1 no resultado Detecção e correção de erros Lembrando Por exemplo dadas duas palavras de código recebidas 10001001 e 10110001 é possível determinar quantos bits correspondentes diferem executando um XOR entre essas duas palavras Detecção e correção de erros O número de posições de bits em que duas palavras de código diferem entre si é chamado distância de Hamming Hamming 1950 Isso significa que se duas palavras de código estiverem a uma distância de Hamming igual a d uma da outra será necessário corrigir d erros de bits isolados para converter uma palavra na outra As propriedades de detecção e de correção de erros de um código dependem de sua distância de Hamming Detecção e correção de erros O primeiro método foi criado por Hamming 1950 Nos códigos de Hamming os bits da palavra de código são numerados consecutivamente da esquerda para direita 1º 2º e assim por diante Os bits na posições que são potências de 2 1º 2º 4º 8º 16º etc são bits de verificação Os outros 3º 5º 6º 7º 9º etc são preenchidos com os m bits de dados Detecção e correção de erros Por exemplo para transmitir a palavra de 7 bits Qual será a palavra código formada Começando preenchendo a palavra código com os bits de dados e os bits de verificação temos Detecção e correção de erros Assim termos uma palavra código de 11 bits com 4 bits de paridade Cada bit de verificação força a paridade de algum conjunto de bits a ser par ou impar Um bit pode ser incluído em vários cálculos de paridade Detecção e correção de erros Os bits de verificação são calculados para soma de paridade par para a mensagem 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 11 10 9 8 7 6 5 4 11 10 7 6 3 2 11 9 7 5 3 1 m m m P m m m P m m m m m P m m m m m P Detecção e correção de erros O motivo para a numeração muito cuidadosa dos bits de mensagem e verificação tornase aparente no processo de decodificação Para o processo de decodificação calculase o que se chama de resultados de verificação incluindo os valores dos bits de verificação recebidos Detecção e correção de erros Chamamos essa seqüência de k1 k2 k3 k4 Se os bits de verificação forem corretos então para somas de paridade par cada resultado de verificação deve ser zero Nesse caso a palavra de código é aceita como válida 11 10 9 8 4 7 6 5 4 3 11 10 7 6 3 2 2 11 9 7 5 3 1 1 m m m P K m m m P K m m m m m P K m m m m m P K Detecção e correção de erros Entretanto se os resultados de verificação não forem todos zeros um erro é detectado O conjunto de resultados de verificação forma a síndrome de erro que é usada para localizar e corrigir erros Supondo que foi recebido a seguinte palavra código 00101001001 Detecção e correção de erros Assim é calculado os bits de verificação k1 k2 k3 k4 5 1010 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 4 3 2 1 11 10 9 8 4 7 6 5 4 3 11 10 7 6 3 2 2 11 9 7 5 3 1 1 K K K K m m m P K m m m P K m m m m m P K m m m m m P K Detecção e correção de erros Isso significa que o 5º bit está incorreto que pode ser um bit de verificação ou de dados e o descarte dos bits de verificação geram a mensagem correta de um ASCII A Esse padrão pode ser visto para um código de Hamming 117 com 7 bits de dados e 4 bits de verificação mostrado na figura 5 Detecção e correção de erros Figura 5 Exemplo de código de Hamming 117 corrigindo um erro de um único bit Detecção e correção de erros Os códigos de Hamming são valiosas para entender os códigos de bloco porém a maioria das redes usa códigos mais fortes O segundo código que veremos é o código de convolução Este não é um código de bloco Em um código de convolução um codificador processa uma seqüência de bits de entrada e gera uma seqüência de bits de saída Detecção e correção de erros Não existe tamanho de mensagem e limite de codificação como em um código de bloco A saída depende dos bits de entrada atual e anterior ou seja o codificador tem memória O numero de bits anteriores do qual a saída depende é chamado comprimento de restrição k do código Detecção e correção de erros Os códigos de convolução são especificados em termos de sua taxa e comprimento de restrição Os códigos de convolução são muito usados em redes de comunicação por exemplo como parte do sistema de telefonia móvel GSM em comunicações por satélite e nas redes 80211 Como exemplo um código de convolução popular aparece na figura 6 Detecção e correção de erros Figura 6 O código de convolução binário da NASA usado no padrão 80211 Detecção e correção de erros Esse código é conhecido como código de convolução da NASA com r ½ e k 7 pois ele foi usado em missões espaciais a partir de 1977 e desde então ele tem sido bastante reutilizado por exemplo como parte do padrão 80211 Como 1 bit de entrada produz 2 bits de saída assim a taxa do código é ½ O estado interno é mantido em seis registradores de memória Detecção e correção de erros Toda vez que outro bit é inserido os valores dos registradores são deslocados para a direita Por exemplo se 111 for inserido e o estado inicial contiver zeros o estado interno escrito da esquerda para a direita se tornará 100000 110000 e 111000 após o primeiro o segundo e o terceiro bits ser inseridos Os bits de saída serão 11 seguidos de 10 e depois 01 Detecção e correção de erros São necessários sete deslocamentos para esvaziar uma entrada completamente de modo que ela não afete a saída O comprimento da restrição desse código é portanto k 7 Um código de convolução é decodificado encontrandose a seqüência de bits de entrada que tem maior probabilidade de ter produzido a seqüência observada de bits de saída que inclui quaisquer erros Detecção e correção de erros Para valores pequenos de k isso é feito com um algoritmo bastante usado desenvolvido por Viterbe Forney 1973 chamado algoritmo de Viterbe Detecção e correção de erros O terceiro tipo de código de correção de erro é o código Reed Solomom Assim como os códigos de Hamming os de ReedSolomom são códigos de blocos lineares e eles normalmente são sistemáticos Diferentemente dos códigos de Hamming que operam sobre bits individuais os códigos de ReedSolomom operam sobre m símbolos de bits Assim sua matemática é mais complicada Detecção e correção de erros Os códigos de ReedSolomom são definidos como polinômios Para símbolos de m bits as palavras de código possuem 2m 1 símbolos de comprimento Uma escolha popular é tornar m 8 de modo que os símbolos são bytes Uma palavra de código tem então 255 bytes de comprimento Código 255233 é bastante utilizado ele acrescenta 32 símbolos redundantes a 233 símbolos de dados Detecção e correção de erros A decodificação com correção de erros é feita com um algoritmo desenvolvido por Berlekamp e Massey que pode realizar com eficiência tarefa de ajuste para códigos de tamanho moderado Massey 1969 Eles são usados para Modems DSL comunicações por satélite Os códigos de ReedSolomom normalmente são usados em combinação com outros códigos como um código de convolução Detecção e correção de erros Códigos de detecção de erros Examinaremos três códigos de detecção de erros todos eles são códigos de blocos lineares e sistêmicos Paridade Soma de verificação checksums Verificações de redundância cíclica CRCs Detecção e correção de erros O código de detecção de erro que usa paridade acrescenta um único bit de paridade aos dados O bit de paridade é escolhido de modo que o número de bits 1 na palavra de código seja par ou impar Fazer isso é equivalente a calcular o bit de paridade par como operação XOR dos bits de dados Detecção e correção de erros Por exemplo quando 1011010 é enviado com paridade par é acrescentado um bit ao final para formar 10110100 Com paridade impar 1011010 passa a ser 10110101 Porém ele pode detectar erros de único bit Detecção e correção de erros Para oferece melhor proteção contra erros em rajadas podemos calcular os bits de paridade sobre dados em uma ordem diferente daquela em que os bits de dados são transmitidos Isso é chamado de entrelaçamento O entrelaçamento é uma técnica geral para converter um código que detecta ou corrige erros isolados em um código que detecta ou corrige erros em rajada Detecção e correção de erros Nesse caso calculamos um bit de paridade para cada uma das n colunas e enviamos todos os bits de dados como k linhas enviando as linhas de cima para baixo e os bits em cada linha da esquerda para direita da maneira normal Na última linha enviamos os n bits de paridade Um exemplo pode ser vista na figura 7 para n 7 e k 7 Detecção e correção de erros Figura 7 entrelaçamento de bits de paridade para detectar um erro em rajada Detecção e correção de erros Na figura 7 quando ocorre um erro em rajada de tamanho n 7 os bits que contém erro estão espalhados por diferentes colunas Um erro em rajada não implica que todos os bits estejam errados mas sim que pelo menos o primeiro e o último bits estão errados Na figura 7 4 bits foram invertidos por uma faixa de 7 bits No máximo 1 bit em cada uma das colunas será afetado de modo que os bits de paridade nessas colunas detectarão o erro Detecção e correção de erros O segundo tipo de código de correção de erro é o chamado Checksum O termo checksum é normalmente usado para indicar um grupo de bits de verificação associados a uma mensagem independentemente de como são calculados Um grupo de bits de paridade é um exemplo de checksum contudo existem outros checksum mais robustos Detecção e correção de erros O checksum normalmente é colocado no final da mensagem como complemento da função soma desse modo os erros podem se detectados somando a palavra inteira de código recebida tanto bits de dados como a soma de verificação Se o resultado for zero nenhum erro foi detectado Um exemplo de checksum é a soma de verificação de 16 bits da Internet usado em todos os pacotes da rede como parte do protocolo IP Detecção e correção de erros O terceiro método de detecção de erro é o código de redundância cíclica ou CRC Cyclic Redundancy Check também conhecido como código polinomial Os códigos polinomiais se baseiam no tratamento de seqüência de bits como representações de polinômios com coeficientes 0 e 1 apenas Um quadro de k bits é representado por um polinômio com k termos variando desde xk1 até x0 Detecção e correção de erros Dizemos que tal polinômio é de grau k 1 O bit de alta ordem mais a esquerda é o coeficiente de xk1 o bit seguinte e o coeficiente de xk 2 e assim por diante Por exemplo 110001 tem 6 bits portanto representa um polinômio de seis termos com os coeficientes 1 1 0 0 0 e 1 1x5 1x4 0x30x20x11x0 Detecção e correção de erros Quando o método do código polinomial é empregado o transmissor e o receptor devem concordar em relação a um polinômio gerador Gx antecipadamente Tanto o bit de mais alta ordem quanto o de mais baixa ordem do polinômio gerador devem ser iguais a 1 Detecção e correção de erros Para calcular o CRC de um quadro com m bits que corresponde ao polinômio Mx o quadro deve ter mais bits do que o polinômio gerador A idéia é acrescentar um CRC ao final do quadro de forma que o polinômio representado pelo quadro verificado pela soma seja divisível por Gx Detecção e correção de erros Quando obtiver o quadro verificado o receptor tentará dividilo por Gx A existência de um resto indica que houve um erro de transmissão Detecção e correção de erros O algoritmo para calcular o total de verificação é 1 Seja r o grau de Gx Acrescente r bits zero a extremidade de baixa ordem do quadro de modo que ele passe a conter m r bits e corresponda ao polinômio xrMx 2 Divida o string de bits correspondente a Gx pelo string de bits correspondente a xrMx utilizando a divisão de modulo 2 3 Subtraia o resto que tem sempre r ou menos bits do string de bits correspondente a xrMx utilizando a subtração de modulo 2 O resultado é o quadro verificado pela soma que deverá ser transmitido Chame o polinômio de Tx Detecção e correção de erros Como exemplo considere um quadro 1101011111 a ser transmitido usando o polinômio gerador Gx x4x1 De acordo com o algoritmo acrescentando os bits zeros ao quadro de acordo com o grau polinômio gerador teremos o quadro com os 4 zeros anexados 11010111110000 Passando para a forma polinomial x13 x12 x10 x8 x7 x6 x5 x4 0 Detecção e correção de erros Dividindo esse quadro pelo polinômio gerador teremos x13 x12 x10 x8 x7 x6 x5 x4 0 x4x1 x13 x12 x10 x9 x8 x7 x6 x5 x4 x3 x9x8x3 x2 x 0 0 0 x9 0 0 0 0 0 x3 x2 0 0 x2 x 0 0 0 Quociente descartado x9x8x3 x2 x 1100001110 Resto x 0 1 0 Detecção e correção de erros Agora retirando o resto de 11010111110000 teremos o quadro a ser transmitido 11010111110000 10 1101011110010 Detecção e correção de erros Dezenas de padrões de redes compreendem diversos CRCs incluindo praticamente todas as LANs por exemplo Ethernet 80211 e enlaces ponto a ponto por exemplo pacotes sobre SONET Certos polinômios se tornaram padrões internacionais O que é utilizado no IEEE 802 é x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x 1 Protocolos básicos de enlace de dados Na camada física na camada de enlace de dados e na camada de rede existem processos independentes que se comunicam pelo envio de mensagens Uma implementação comum aparece na figura 7 O processo da camada física e da camada de enlace de dados estarão funcionando em hardware dedicado chamado placa de Interface de rede ou NIC Network Interface Card Protocolos básicos de enlace de dados Figura 7 Implementação das camadas física de enlace de dados e de rede Protocolos básicos de enlace de dados O restante do processo da camada de enlace de dados e o processo da camada de rede atuam sobre a CPU principal como parte do sistema operacional com o software para o processo da camada de enlace tomando a forma de um driver de dispositivo Tratar as três camadas como processos separados torna a discussão conceitualmente mais clara e também enfatiza a independência das camadas Protocolos básicos de enlace de dados Como já mostrado na Figura 1 e repetido aqui Um quadro consiste em um pacote incorporado em algumas informações de controle no cabeçalho e em um checksum no final Figura 1 Relacionamento entre pacotes e quadros Protocolos básicos de enlace de dados Em seguida o quadro é transmitido a camada de enlace de dados da outra máquina Quando um quadro chega ao receptor o checksum é calculado Se o checksum estiver incorreto ou seja se houve um erro de transmissão a camada de enlace de dados será informada Protocolos básicos de enlace de dados Um quadro é composto por quatro campos kind seq ack e info os três primeiros contém informações de controle e o último contém os dados reais a serem transferidos Esses campos de controle são chamados coletivamente cabeçalho de quadro Protocolos básicos de enlace de dados O campo kind indica se há dados no quadro ou se há somente informações de controle Os campos seq e ack são usados para números de seqüência e confirmações respectivamente O campo info de um quadro de dados contém um único pacote o campo info de um quadro de controle não é usado Protocolos básicos de enlace de dados Antes de apresentar os protocolos de enlace de dados temos três direções do fluxo de dados Figura 8 Direção do fluxo de dados Protocolos básicos de enlace de dados Em situações práticas há necessidade de transmitir dados em ambos os sentidos Você pode obter uma transmissão de dados fullduplex definindo dois canais de comunicação distintos e usar cada um deles para um tráfego de dados simplex em diferentes sentidos Cada enlace é composto de um canal direto para dados e um canal reverso para confirmações Protocolos básicos de enlace de dados Em ambos os casos a capacidade do canal reverso é quase totalmente perdida Uma idéia melhor é usar o mesmo circuito para dados em ambos os sentidos O canal reverso normalmente tem a mesma capacidade do canal direto Protocolos básicos de enlace de dados Nesse modelo os quadros de dados enviados de A para B são misturados com os quadros de confirmação enviados de A para B Ao verificar o campo kind do cabeçalho de um quadro recebido o receptor pode identificar se o quadro é de dados ou de confirmação Protocolos básicos de enlace de dados Quando um quadro de dados chega a seu destino em vez de enviar imediatamente um quadro de controle separado o receptor espera até a camada de rede enviar o próximo pacote A confirmação é acrescentada ao quadro de dados que está sendo enviado por meio do campo ack do cabeçalho de quadro Protocolos básicos de enlace de dados A técnica de retardar temporariamente as confirmações e enviá las junto com o próximo quadro de dados é conhecida pelo nome de piggybacking pegar carona A principal vantagem do piggybacking em relação ao envio de quadros de confirmação distintos é a melhor utilização da largura de banda disponível para o canal Protocolos básicos de enlace de dados O campo ack do cabeçalho de quadro precisa de apenas alguns bits enquanto um quadro separado precisaria de um cabeçalho da confirmação e de um checksum Além disso um número menor de quadros enviados significa uma carga menor de processamento no receptor Na verdade a confirmação pega carona no próximo quadro de dados que estiver sendo enviado Protocolos de janela deslizante Os três protocolos seguintes são protocolos bidirecionais que pertencem a uma classe de protocolos identificados como protocolos de janela deslizante Os três apresentam diferenças em termos de eficiência complexidade e requisitos de buffer como discutiremos mais adiante Protocolos de janela deslizante Nesses protocolos como em todos os protocolos de janela deslizante cada quadro enviado contém um número de seqüência variando desde 0 até algum valor máximo Em geral o valor máximo é 2n 1 de forma que o número de seqüência caiba exatamente em um campo de n bits A essência de todos os protocolos de janela deslizante é o fato de que em qualquer instante o transmissor mantém um conjunto de números de seqüência correspondentes a quadros que ele pode enviar Protocolos de janela deslizante Dizemos que esses quadros estão reunidos na janela de transmissão Da mesma forma o receptor mantém uma janela de recepção correspondente ao conjunto de quadros que está apto a aceitar A janela do transmissor e a janela do receptor não precisam ter os mesmos limites superior e inferior ou o mesmo tamanho Protocolos de janela deslizante Em alguns protocolos essas janelas tem tamanho fixo mas em outros elas podem aumentar e diminuir a medida que os quadros são enviados e recebidos Os números de seqüência contidos na janela do transmissor representam quadros que foram enviados ou que podem ser enviados mas ainda não confirmados Sempre que chega um novo pacote da camada de rede ele recebe o próximo número de seqüência mais alto e o limite superior da janela é incrementada em uma unidade Protocolos de janela deslizante Quando uma confirmação é recebida o limite inferior é incrementada em uma unidade Dessa forma a janela mantém continuamente uma lista de quadros não confirmados A Figura 9 mostra um exemplo com um tamanho máximo de janela igual a 1 Protocolos de janela deslizante Figura 9 Uma janela deslizante de tamanho 1 com um número de seqüência de 3 bits aInicialmente b Depois que o primeiro quadro é enviado c Depois que o primeiro quadro é recebido d Depois que a primeira confirmação é recebida Protocolos de janela deslizante Inicialmente não há quadros pendentes portanto os limites inferior e superior da janela do transmissor são iguais mas a medida que o tempo passa a situação se desenvolve da maneira mostrada Diferentemente da janela do transmissor a janela do receptor sempre permanece em seu tamanho inicial incrementandose a mediada que o próximo quadro é aceito e entregue a camada de rede Protocolos de janela deslizante Um protocolo de janela deslizante de um bit Antes de abordarmos o caso geral vamos examinar primeiro um protocolo de janela deslizante com um tamanho máximo de janela igual a 1 Esse tipo de protocolo utiliza o stopandwait pois o transmissor envia um quadro e aguarda sua confirmação antes de enviar o quadro seguinte Quando esse ou qualquer quadro chega ao destino a camada de enlace de dados receptora verifica se ele é uma cópia Protocolos de janela deslizante Se o quadro for o esperado ele será repassado a camada de rede e a janela do receptor será deslocada para cima O campo de confirmação contém o número do último quadro recebido sem erro Se esse número estiver de acordo com o número de seqüência do quadro que o transmissor enviou ele poderá buscar o pacote seguinte em sua camada de rede Protocolos de janela deslizante Se o numero de seqüência for discordante o transmissor deve continuar tentando enviar o mesmo quadro Sempre que um quadro é recebido um outro quadro também é enviado de volta Até agora estávamos supondo implicitamente que o tempo de transmissão necessário para a chegada de um quadro até o receptor somado ao tempo de transmissão para o retorno da confirmação era insignificante Protocolos de janela deslizante Para certas situações o longo tempo de ida e volta pode ter implicações importantes para a eficiência da utilização da largura de banda Como exemplo considere um canal de satélite de 50 kbps com um retardo de propagação de ida e volta de 500 ms Vamos imaginar a tentativa de usar o protocolo de janela deslizante de um bit para enviar quadros de 1000 bits pelo satélite Protocolos de janela deslizante Em t 0 o transmissor começa a enviar o primeiro quadro Em t 20 ms o quadro já foi completamente enviado Até t 270 ms o quadro ainda não chegou completamente ao receptor e até t 520 ms na melhor das hipóteses a confirmação ainda não voltou ao transmissor sem nenhum tempo de espera no receptor e com um quadro de confirmação curto ms kbps bits transmissão de taxa e pa do tamanho tt 20 50 1000 cot Protocolos de janela deslizante Isso significa que o transmissor esteve bloqueado durante 500520 ou 96 do tempo isto é apenas 4 da largura de banda disponível foram utilizados É claro que a combinação de um longo tempo de trânsito alta largura de banda e pequeno comprimento de quadro é desastrosa em termos de eficiência Protocolos de janela deslizante Basicamente a solução está em permitir que o transmissor envie até w quadros antes do bloqueio e não apenas 1 Com uma escolha apropriada de w o transmissor será capaz de transmitir quadros continuamente pois as confirmações chegarão aos quadros anteriores antes que a janela se encha impedindo o bloqueio do transmissor Para achar um valor apropriado para w precisamos saber quantos quadros podem caber dentro do canal à medida que se propagam do transmissor ao receptor Protocolos de janela deslizante Essa capacidade é determinada pela largura de banda em bps multiplicada pelo tempo de trânsito em um sentido ou produto largura de bandaatraso do enlace BD Podemos definir w 2BD 1 Protocolos de janela deslizante Ou seja o dobro da largura de banda x atraso é o número de quadros que podem estar pendentes se o transmissor enviar quadros continuamente quando o tempo de ida e volta para receber uma confirmação for considerado O 1 é porque um quadro de confirmação não será enviado antes que um quadro completo seja recebido Protocolos de janela deslizante Para o enlace do exemplo com uma largura de banda de 50 kbps e tempo de trânsito unidirecional de 250 ms w 2 50 k 250 m 1 2125 1 26 quadros Protocolos de janela deslizante Suponha que o transmissor comece enviando o quadro como antes e transmita um novo quadro a cada 20 ms Quando ele tiver terminado de enviar 26 quadros em t 520 ms a confirmação para o quadro 0 terá acabado de chegar Depois disso as confirmações chegarão a cada 20 ms de modo que o transmissor sempre terá permissão para continuar assim que precisar Protocolos de janela deslizante Em outras palavras o tamanho máximo da janela do transmissor é 26 Podemos escrever a utilização como a fração de tempo em que o transmissor não está bloqueado Utilização do enlace BD w 12 Protocolos de janela deslizante Essa técnica de manter vários quadros pendentes é conhecida como pipelining Mas isso faz surgir algumas questões muito sérias Primeiro o que acontecerá se um quadro em meio a um longo fluxo for danificado ou perdido Um grande número de quadros sucessivos chegará ao receptor antes mesmo que o transmissor descubra que algo está errado Protocolos de janela deslizante Quando um quadro danificado chega ao receptor ele deve sem dúvida ser descartado No entanto o que o receptor deve fazer com todos os quadros corretos que o seguem Há duas estratégias básicas para lidar com erros na presença de pipelining ambas mostradas na Figura 10 Protocolos de janela deslizante Figura 10 Pipelining e recuperação de erros Efeito de um erro quando a o tamanho da janela receptora é igual a 1 e quando b o tamanho da janela receptora é grande Protocolos de janela deslizante Um protocolo que utiliza GOBACKN Em uma opção denominada gobackn o receptor simplesmente descarta todos os quadros subseqüentes e não envia qualquer confirmação desses quadros descartados Essa estratégia corresponde a uma janela de recepção de tamanho 1 O transmissor retransmitirá todos os quadros não confirmados em ordem começando pelo quadro danificado ou perdido Protocolos de janela deslizante Essa abordagem poderá desperdiçar uma grande quantidade de largura de banda se a taxa de erros for alta Na Figura 10 a vemos gobackn Figura 10 a Protocolo de janela deslizante GoBack N Protocolos de janela deslizante Protocolo de Janela Deslizante com Retransmissão seletiva selective repeat A outra estratégia geral para tratamento de erros denominase retransmissão seletiva selective repeat figura 10b Figura 10 b Protocolo de janela deslizante com retransmissão Seletiva Protocolos de janela deslizante Quando ela é utilizada um quadro incorreto recebido é descartado mas os quadros corretos recebidos depois dele são aceitos e inseridos no buffer Quando o transmissor chega ao timeout apenas o quadro não confirmado mais antigo é retransmitido Se esse quadro chegar corretamente o receptor poderá entregar a camada de rede em seqüência todos os quadros que armazenou no buffer Protocolos de janela deslizante Com freqüência a retransmissão seletiva corresponde a uma janela receptora maior que 1 Normalmente a retransmissão seletiva é combinada com a ação de fazer o receptor enviar uma confirmação negativa ou NAK Negative Acknowledgement ao detectar um erro por exemplo quando receber um erro de checksum ou um quadro fora de seqüência Protocolos de janela deslizante As NAKs estimulam a retransmissão antes de expirar o timer correspondente e desse modo melhoram o desempenho Esses dois enfoques alternativos são dilemas entre o uso eficiente de largura de banda e espaço no buffer da camada de enlace de dados Dependendo de qual recurso seja mais escasso um ou outro poderá ser usado Protocolos de janela deslizante Apesar de não armazenar no buffer os quadros recebidos após um quadro com erro o protocolo goback n não escapa totalmente ao problema do armazenamento em buffer Tendo em vista que um transmissor talvez seja obrigado a retransmitir todos os quadros não confirmados em um determinado momento no futuro ele deverá reter todos os quadros transmitidos até ter certeza de que eles foram aceitos pelo receptor Protocolos de janela deslizante Considere a situação a seguir com MAXSEQ 7 1 O transmissor envia quadros de 0 a 7 2 Uma confirmação com piggyback de carona para o quadro 7 volta ao transmissor 3 O transmissor envia mais oito quadros novamente com números de seqüência de 0 a 7 4 Agora chega outra confirmação com piggyback correspondente ao quadro 7 Protocolos de janela deslizante A questão é os oito quadros pertencentes ao segundo lote chegaram com sucesso ou todos eles se perderam a contagem descarta os quadros posteriores a um erro considerandoos perdidos Nos dois casos o receptor estaria enviando o quadro 7 como confirmação O transmissor não tem como saber disso Por essa razão o número máximo de quadros pendentes deve se restringir a MAXSEQ Protocolos de janela deslizante Quando uma confirmação chega para o quadro n os quadros n 1 n 2 e assim por diante também são confirmados de forma automática Esse tipo de confirmação é chamado confirmação cumulativa Essa propriedade é especialmente importante nos casos em que alguns dos quadros anteriores que representavam confirmações se perderam ou foram adulterados Protocolos de janela deslizante No protocolo de retransmissão seletiva tanto o transmissor quanto o receptor mantém uma janela de números de seqüência aceitáveis respectivamente O tamanho da janela do transmissor é medido a partir de 0 e atinge um número máximo prédefinido por outro lado a janela do receptor tem sempre um tamanho fixo e igual ao máximo pré definido Protocolos de janela deslizante O receptor tem um buffer reservado para cada número de seqüência dentro de sua janela fixa Associado a cada buffer há um bit arrived que informa se o buffer está cheio ou vazio Sempre que um quadro chega seu número de seqüência é verificado para confirmar se ele se enquadra na janela Protocolos de janela deslizante Se isso ocorrer e se o quadro ainda não tiver sido recebido ele será aceito e armazenado Imagine que haja um número de seqüência de 3 bits de modo que o transmissor tenha permissão para transmitir até sete quadros antes de ser obrigado a esperar por uma confirmação Inicialmente as janelas do transmissor e do receptor são semelhantes as da Figura 11a Protocolos de janela deslizante Figura 11 a Situação inicial com uma janela de tamanho sete b Depois que sete quadros são enviados e recebidos mas não confirmados c Situação inicial com uma janela de tamanho quatro d Depois que quatro quadros são enviados e recebidos mas não confirmados Protocolos de janela deslizante No momento o transmissor envia os quadros de 0 a 6 A janela do receptor permite que ele aceite qualquer quadro com número de seqüência entre 0 e 6 ambos inclusive Todos os sete quadros chegam corretamente assim o receptor os confirma e avança a janela para permitir a recepção de7 0 1 2 3 4 ou 5 como mostra a Figura 11b Todos os sete buffers são marcados como vazios Protocolos de janela deslizante Nesse ponto ocorre um problema e todas as confirmações são apagadas O protocolo deve operar corretamente apesar disso Mais tarde o transmissor entra em timeout e retransmite o quadro 0 Quando esse quadro chega ao receptor é feita uma conferência para ver se o quadro se ajusta a janela do receptor Protocolos de janela deslizante Infelizmente na Figura 11b o quadro 0 está dentro da nova janela e assim ele será aceito O receptor envia uma confirmação com piggyback para o quadro 6 pois os quadros de 0 a 6 foram recebidos O transmissor sabe que todos os quadros transmitidos chegaram realmente de forma correta portanto ele avança sua janela e envia imediatamente os quadros 7 0 1 2 3 4 e 5 O quadro 7 será aceito pelo receptor e seu pacote será repassado diretamente a camada de rede Protocolos de janela deslizante Logo depois a camada de enlace de dados receptora verifica se há um quadro 0 válido descobre que sim e repassa o pacote a camada de rede como se fosse um novo Conseqüentemente a camada de rede recebe um pacote incorreto e o protocolo falha A essência do problema é que depois que o receptor avançou a janela a nova faixa de números de seqüência válidos substituiu a antiga Protocolos de janela deslizante Consequentemente o próximo lote de quadros poderia ser formado por cópias se todas as confirmações se perderam ou de novos quadros se todas as confirmações foram recebidas O receptor não tem como distinguir esses dois casos A saída desse dilema reside em ter certeza de que depois que o receptor avança sua janela não há sobreposição entre esta e a janela original Protocolos de janela deslizante Para assegurar que não há sobreposição o tamanho máximo da janela deve ser no máximo igual a metade do intervalo dos números de seqüência como ocorre nas Figuras 11c e 11d Em geral o tamanho da janela para o protocolo será tamanho da janela MAXSEQ 12 Protocolos de janela deslizante Para números de seqüência de três bits temos MAXSEQ 23 1 7 tamanho da janela MAXSEQ 12 7 12 4 Apenas quatro quadros não confirmados devem estar pendentes em qualquer instante Protocolos de janela deslizante Dessa forma se o receptor só tiver aceito os quadros de 0 a 3 e avançado sua janela para aceitar os quadros de 4 a 7 ele poderá saber sem qualquer dúvida se os quadros subseqüentes são retransmissões 0 a 3 ou novos quadros 4 a 7 Conseqüentemente o número de buffers necessário é igual ao tamanho da janela assim nesse exemplo são necessários quatro buffers numerados de 0 a 3