Camada de Ligação de Dados

A Camada de Ligação de Dados (Data Link)

O objetivo desta camada é tratar da transferência de dados numa rede local entre dois dispositivos - entre um host e um router ou entre dois routers - pertencentes à mesma rede, ou seja, trata-se de como os dispositivos falam diretamente uns com os outros.

Serviços da camada

Esta camada oferece diferentes serviços:

Framing e acesso a Links:

• Encapsula o datagrama numa trama - nome dado a um pacote nesta camada, adicionando cabeçalho e trailer;
• Protocolo MAC (Medium Access Control) para aceder ao meio compartilhado; São usados endereços MAC nos cabeçalhos de tramas para identificar a origem e o destino, apenas dentro da mesma rede.

Entrega confiável entre nós adjacentes:

• Soluções semelhantes às adotadas na camada de transporte;
• Raramente usado em links com baixa taxa de erros de bits (e.g. fibra óptica). Já os links sem fio (e.g. Wi-Fi), têm taxas de erro altas.

Deteção de erros:

• Deteta erros causados por atenuação de sinal e ruído;
• O recetor pode detetar a presença de erros, sinalizando o remetente para reenviar ou descartando a trama.

Correção de erros:

• Para além de detetar, o recetor pode identificar e corrigir erros de bits sem recorrer ao reenvio.

Controlo de fluxo:

• Ajustar o ritmo entre os nós adjacentes que enviam e recebem.

Links half-duplex e full-duplex:

• Half-duplex: É possível transmitir para os dois sentidos, mas só num sentido de cada vez.
• Full-duplex: É possível transmitir para os dois sentidos ao mesmo tempo.

Terminologia

• Nós / Nodes - hosts e routers (ou seja, quem comunica);
• Ligações / Links - Canais de comunicação que conectam nós adjacentes ao longo do caminho de comunicação. Por exemplo, links por fio, links sem fio, LANs, etc.
• Trama / Frame - Pacote da camada de Ligação de Dados. Encapsula um datagrama.

Usando a terminologia, o objetivo desta camada é

transferir datagramas de um nó para o nó fisicamente adjacente num link.

Endereços MAC

A camada de ligação de dados está implementada na NIC - interface de rede de cada host, que liga diretamente aos buses de hardware.

Nesta camada, são usados endereços MAC. Um exemplo de um endereço MAC é o seguinte: A1:B2:C3:24:55:F1.
Cada placa de rede tem um endereço MAC associado, que é como se fosse um identificador específico do dispositivo (como, por exemplo, o número de Cartão de Cidadão é para as pessoas).

Estes endereços têm propósitos diferentes dos endereços IP: os endereços MAC têm um propósito mais local enquanto que os endereços IP têm um contexto mais geográfico.
O que cria esta distinção é o facto de os endereços MAC serem intrínsecos das placas de rede, ou seja, são como uma fingerprint; Já os endereços IP podem ser alterados facilmente e é possível ser construído um sistema e uma divisão hierárquica da sua distribuição, através das máscaras de rede.

Para um dado endereço MAC, os três primeiros bytes identificam o fabricante enquanto que os os três últimos bytes identificam o equipamento.

Nestes endereços também é possível ser feito um broadcast, fazendo-o para o endereço FF:FF:FF:FF:FF:FF. Ao enviar um pacote para esse endereço, esse pacote será reencaminhado para todos os hosts da rede local.

Protocolo ARP - Address Resolution Protocol

Um router recebe um pacote por IP de algum lado. Como é que ele é entregue ao host certo?

O router precisa de saber o endereço MAC correspondente ao endereço IP recebido.
Para tal, usa-se o protocolo ARP (Address Resolution Protocol):

1. O router faz um ARP Request, ou seja, um broadcast, enviando para o endereço FF:FF:FF:FF:FF
   a pergunta: "Quem tem este endereço IP?"
2. O host com o endereço IP responde com o seu endereço MAC.

De forma a não se estarem sempre a repetir estes pedidos, os hosts guardam numa tabela (tabela ARP), o mapeamento entre endereço IP e endereço MAC - (endereçoIP, endereçoMAC, TTL).

Deteção de Erros de Transmissão

Os dados, por diversos motivos, podem sofrer erros de transmissão, fazendo com que um ou mais bits venham trocados.
Para detetar esses erros, existem várias formas:

Bit de Paridade

É uma forma antiga de detetar erros.
No fim da transmissão, era acrescentado um bit que dependia do número de bits totais da mensagem:

• Se o número de bits fosse par, colocava-se um 0;
• Se o número de bits fosse ímpar, colocava-se um 1.

Não é uma forma muito boa pois não deteta um número par de erros.

CRC - Cyclic Redundancy Check

Muito usado atualmente. É feita uma operação matemática, usando divisão de polinómios.

Para tal, usa-se um polinómio gerador $G(x)$ de grau $n$ juntamente com uma mensagem de $m$ bits, que é vista como um polinómio $M(x)$ de grau menor que $M$.

A computação do CRC é feita da seguinte forma:

1. Calcula-se o dividendo $D(x) = x^n \times M(x)$, ou seja, faz-se um shift para a esquerda de $M(x)$ de $n$ unidades;
2. O divisor é $G(x)$;
3. Converte-se o dividendo e o divisor em bits (Por exemplo, se $G(x) = x^3 + x^2 + 1$, este passa a $1101$);
4. Faz-se a divisão $D(x) \div G(x)$. A divisão é feita à mão, como se fosse uma divisão normal - a única diferença é que estão a ser usados bits, ou seja, é feita a diferença binária;
5. Desta divisão, resulta o resto $R(x)$;
6. É enviada a mensagem $T(x) = x^n \times M(x) + R(x)$, onde o $+$ representa a concatenação.

Um erro será detetado se a mensagem recebida não for divisível por $G(x)$.

O video seguinte explica como aplicar o algoritmo:

Este algoritmo é facilmente implementado em hardware, usando registos de desvio.

Colisões de broadcast

Quando é feito um broadcast FF:FF:FF:FF:FF:FF, este é partilhado por todos os membros da rede.
Isto implica que o canal possa sofrer colisões muito facilmente, bastando que um nó receba dois ou mais sinais ao mesmo tempo.

Protocolos Multiple Access Control - algoritmos distribuídos que determinam como é que os nós partilham um canal, ou seja, quando é que um dado nó pode transmitir.

Existem vários protocolos que implementam o acesso de formas diferentes:

Particionamento de canal fixo:

• Dividir o canal em "pedaços" menores (intervalos de tempo, frequências, códigos, etc.);
• Alocar um pedaço para o nó para uso exclusivo.

Alocação dinâmica ("um de cada vez"):

• Os nós tomam a vez (mas os nós com mais dados para enviar podem transmitir com mais frequência);
• Poll / seleção;
• Passagem de um token.

Acesso Aleatório:

• O canal não é dividido, logo permite colisões;
• É possível recuperar das colisões.

Particionamento de canal fixo

FDMA - Frequency Division Multiple Access

Neste tipo de particionamento, o espetro de canal é dividido em faixas de frequência. Assim, é atribuída a cada estação uma faixa de frequência fixa, mas o tempo de transmissão não utilizado nas faixas de frequência não é aproveitado.

Similar à FDM de Circuit Switching.

TDMA – Time Division Multiple Access

O acesso ao canal é feito em rondas. É atribuído a cada host uma fatia temporal em cada ronda. Também aqui, o tempo não utilizado não é aproveitado.

Similar à TDM de Circuit Switching.

CDMA – Code Division Multiple Access

Cada utilizador tem acesso à frequência completa, durante todo o tempo.
São usados diferentes códigos para distinguir os utilizadores.

Particionamento de canal fixo

Neste tipo de particionamento, o canal é fixo e é antes feita uma divisão por regras de ordenação dos hosts.

Alocação dinâmica

Poll / Select

Um computador central controla a atividade dos outros.

Token Passing

Um token que dá a permissão de transmissão é passado entre os hosts.
Quando um host acaba de transmitir, passa o token para outro host.

Esta medida não é ideal se não existir muito tráfego, pois existe dependência que os hosts transmitam mensagens.

Acesso aleatório

Neste tipo de particionamento, não existe qualquer divisão do canal nem coordenação, ou seja, quando um nó tem um pacote para enviar, envia-o imediatamente à rate máxima.

Os protocolos que seguem este particionamento indicam como detetar colisões bem como recuperar delas:

ALOHA

Foi criado na Universidade de Hawaii (daí o seu nome).
É um protocolo simples que não tem sincronização.
Existe uma colisão se duas ou mais tramas se sobrepuserem, sendo programada uma retransmissão para um instante futuro aleatório.

Slotted ALOHA

É igual ao protocolo anterior, mas o tempo é dividido em slots temporais do mesmo tamanho.
Os nós só podem começar a transmitir no início de um slot.

CSMA - Carrier Sense Multiple Access

Baseia-se em não causar interrupções:

• Se o canal estiver calado, transmite a trama inteira;
• Se o canal estiver ocupado, adia a transmissão.

Contudo, ainda podem existir colisões devido ao tempo de propagação, o que implica que toda a transmissão de um pacote tenha que ser descartada.

CSMA/CD - CSMA com Deteção de Colisões

É uma versão aprimorada do protocolo anterior que consegue detetar colisões mais rapidamente. Ao ser detetada uma colisão, as transmissões são imediatamente abortadas, reduzindo a ocupação do canal.

Resumo dos protocolos

Particionamento de canal fixo:

• Eficientes com uma carga alta e constante de todos os nós;
• Ineficientes em cargas baixas ou desequilibradas.

Alocação dinâmica ("um de cada vez"):

• Compartilham o canal de forma eficiente e justa em cargas altas;
• Baixa carga: ineficiente, pois os nós ativos precisam de esperar pelos nós com pouca ou sem atividade para "passarem a vez";

Acesso Aleatório:

• Eficientes em carga baixa porque apenas um único nó pode utilizar o canal num dado momento;
• Carga alta: sobrecarga de colisão.

IEEE 802.3 - Ethernet

O IEEE 802.3 é um standard que introduz a tecnologia de LAN cablada chamada Ethernet.
Existem várias topologias de rede:

Topologias de rede

• Bus - um cabo principal partilhado por vários computadores. Todos os hosts ouvem todos os hosts e está muito sujeito a colisões.

• Estrela - No lugar da ligação ser feita a um fio, é antes feita a uma tomada na parede. As tomadas nas paredes são ligações que se ligam todas a um armário onde estão equipamentos de rede usados para espalhar o tráfego.
  Inicialmente usavam-se hubs, dispositivos que apenas repetem o sinal para todas as portas (basicamente, fazem sempre broadcast);
  Depois, surgiram os switches/bridges, que encaminham o tráfego para a porta certa (são "inteligentes").

Frames de rede

Na camada de Ligação de Dados (layer 2), os pacotes são chamados de Frames/Tramas e têm o seguinte formato:

Onde,

• Preâmbulo - Usado para sincronizar as clock rates dos emissor e recetor;
• Endereços - Endereços MAC do emissor e do recetor;
• Tipo - Indica o protocolo da camada superior (Ex. IP);
• Data - Dados a serem transmitidos;
• CRC - Checks para correção de erros.

Algoritmos de comunicação

A Ethernet básica tem alguns problemas:

• Connectionless - Não existe o conceito de conexão, como visto anteriormente com o paradigma Datagram;
• Instável - A NIC de recebimento não envia ACKs ou NACKs para a NIC de envio, o que implica que um fluxo de datagramas transmitidos pela camada de rede possa ter lacunas (datagramas perdidos). Contudo, se a aplicação estiver a usar o TCP, as lacunas serão preenchidas.

Para colmatar isso, foi criado o seguinte algoritmo:

Algoritmo CSMA/CD - Carrier Sense Multiple Access (with Collision Detection)

1. A NIC recebe o datagrama da camada de rede e cria uma trama;
2. Se o canal estiver livre (esperam-se 96 tempos de bit), a NIC inicia a transmissão da trama;
   Se o canal estiver ocupado, aguarda até que o canal esteja livre e logo de seguida, transmite;
3. Se a NIC transmitir a trama inteira sem detetar outra transmissão: sucesso;
4. Se a NIC detetar outra transmissão enquanto estiver transmitindo, houve uma colisão:
   • aborta e envia um sinal de interferência, avisando todos que houve uma colisão;
5. Depois de abortar, a NIC entra em retrocesso exponencial:
   • Depois da m-ésima colisão, a NIC escolhe um número $K$ aleatoriamente em $\{0,1,2,…,2^m-1\}$;
   • A NIC aguarda $K \times 512$ tempos de bit de transmissão; Depois, retorna ao Passo 2.

Este algoritmo procura, através de deteção de colisões, minimizar as colisões seguintes, pois todos os intervenientes são avisados que houve uma colisão e "ordenados" a parar, "reestabelecendo a ordem".
Contudo, quando existe muito tráfego, existem de qualquer forma muitas colisões.

Switches

Ao contrário dos hubs, apresentados anteriormente, os switches (comutadores, em português) são inteligentes - se um host A falar com um host B, o switch aprende a sua localização, ou seja, fica a saber que o host A está na sua porta X.

Desta forma, são permitidas várias ligações em simultâneo e as colisões mencionadas anteriormente são reduzidas.

Para isso, o switch tem uma Switching Table - Sempre que existir uma nova transmissão, o switch constrói uma switching table onde regista um mapeamento de quem transmitiu e de onde (de que interface) veio essa transmissão.
(Não confundir com uma forwarding table)

São guardadas entradas do tipo: (Endereço MAC, interface do _switch_, TTL), onde TTL representa o tempo até esta entrada deixar de ser válida.

Sempre que o switch quer enviar algo para um host, verifica primeiro se existe uma entrada válida na tabela com o endereço de destino:

• Se estiver, envia para a interface associada.
• Se não estiver, faz flooding - a mensagem é repetida em todas as interfaces (à exceção da que enviou a trama) - neste caso, funciona como um hub.

Interligar switches

É possível interligar switches, ou seja, a um switch estar ligado outro switch, que por sua vez está ligado a um terceiro switch, e assim por diante.
Por exemplo:

Ou seja, numa interface de um switch podem existir várias interfaces (correspondentes às interfaces dos switches "filho").

Considerado o flooding apresentado anteriormente, eis um exemplo de uma transmissão onde o switch ainda não tem nenhuma entrada na switching table:

Falta de redundância

E se alguém cortar a ligação entre dois dos switches?
Todos os hosts ligados ao switch "filho" ficam desconectados. Para resolver isso, pode-se introduzir alguma redundância.

Considerando a interligação mostrada anteriormente, uma forma de a adicionar seria a seguinte:

Porém, adicionar redundância traz um problema grave - quando é feito flooding, é criado um loop na rede. Mais grave ainda, devido a não existir forma de identificar se uma trama é uma repetição ou uma trama nova, este loop fica na rede para sempre!

Por exemplo, considerando uma switching table vazia,

• Se S4 fizer flooding, irá enviar uma trama para S1, S2 e S3;
• Por conseguinte, S1, S2 e S3 irão fazer flooding para S2, S1 e S3, e S2, respetivamente;
• Os switches que já receberam a trama não conseguiram distingui-la e portanto, voltam a fazer flooding, incluindo os switches que já o fizeram...

Para resolver isto, a redundância necessita de estar desligada logicamente, ou seja, a ligação física (o cabo), está ligada, mas o switch desativa a porta até esta ser necessária.

Para decidirem quais os melhores caminhos a usar e que interfaces desligar, os switches precisam de um algoritmo para os descobrir.
Como o esboço da rede final é, pensando em grafos, uma árvore (cada nó só está ligado uma vez), é lhe dado o nome de STP (Spanning Tree Protocol).

STP - Spanning Tree Protocol

Ideias Gerais

É necessário, então, identificar uma árvore na topologia - as interfaces que constituem essa árvore ficam ligadas enquanto que as restantes ficam desligadas (até ser necessário).

Para este algoritmo funcionar, são necessárias as seguintes ideias:

• Bridge ID - Cada switch é identificado por um endereço constituído por 2 bytes que representam a prioridade e 6 bytes que são o endereço MAC do switch. Por exemplo, 8000.AA:BB:CC:DD:EE:FF é o ID do switch com endereço MAC AA:BB:CC:DD:EE:FF e com uma prioridade de 0x8000.
• Root Bridge - Switch que é o nó inicial da árvore. É o switch com o menor Bridge ID (ou seja, a prioridade serve para "forçar" um switch a ser a root bridge e os seus sucessores).
• Root Port - Porta que, num dado switch, é responsável pelo envio/receção de frames para/da root bridge - são o caminho em direção ao root bridge (daí Root Port, "porta para o root").
• Designated Bridge - Switch que, num dado segmento de rede, é responsável por enviar/receber as tramas da rede para/da root bridge.
• Designated Port - Porta da Designated Bridge por onde passa o tráfego para/da root bridge.

Vale notar que:

• Root Port não está relacionado com a root bridge.
• Para um dado segmento de rede, onde podem estar computadores, impressoras, etc., estes enviam tráfego para o switch, sendo essa porta a Designated Port. O switch por sua vez, envia o tráfego pela Root Port, que aponta na direção da root bridge. Ou seja, o tráfego "flui" de Designated Ports para Root Ports.
• Cada rede terá uma root bridge, cada switch (exceto a root bridge, que não tem nenhuma) terá apenas uma Root Port, cada segmento de rede terá apenas uma Designated Port e as restantes portas ficarão inativas.
• Cada switch tem um custo para chegar à root bridge, que é igual à soma dos custos de todas as portas que transmitem em direção à root bridge (Root Ports).
• As restantes portas que não são usadas são as portas que são desativadas, ou seja, a árvore é definida pelas portas não bloqueadas.

BPDUs - Bridge Protocol Data Units

Para ser possível identificar todos os elementos mencionados anteriormente, os switches têm que, de alguma forma, comunicar entre si.
Para o fazerem, e para trocarem a informação necessária, os switches enviam BPDUs (Bridge Protocol Data Units), que contêm a seguinte informação:

(ID do Root Bridge, Custo até Root Bridge, ID de quem enviou a BPDU, ID da porta que originou a BPDU)

Vale notar que o Custo até Root Bridge é igual à soma dos custos de todas as arestas que levam à root bridge.

Estas BPDUs são enviadas, em norma, em intervalos de 2 segundos.

Quando um switch é ligado, o algoritmo STP é usado para identificar a root bridge, sendo enviadas BPDUs com o BridgeID do novo switch.
Este, até receber BPDUs, assume ser a root bridge. Porém, quando receber uma BPDU, este verá o BridgeID da root bridge:

• Se esse BridgeID for menor que o dele, o switch aceita que esse BridgeID é a root bridge e deixa de assumir ser ele a root bridge;
• Se esse BridgeID for maior que o dele, então ele continua a assumir ser a root bridge. Quando os outros switches receberem o seu BridgeID, estes verão que é menor que os deles, então atualizarão a sua root bridge.

Algoritmo

Devido à complexidade e nuances do algoritmo, este será explicado com um exemplo:

(ID do Root Bridge, Custo até Root Bridge, ID de quem enviou a BPDU, ID da porta que originou a BPDU)

(5, 2, 20, 22)

(5, 2, 20, 22), sw X
(5, 1, 30, 31), sw Y
(5, 1, 10, 12), sw W
(5, 1, 10, 13), sw W

(-, -, 30, 31), sw Y
(-, -, 10, 12), sw W
(-, -, 10, 13), sw W

(-, -, -, 12), sw W
(-, -, -, 13), sw W

20: (5, 2, 20, 22)
40: (5, 2, 40, 43)

Ciclos temporários e perda de conectividade

Quando existir uma mudança na topologia de rede (por ex., um switch é removido ou uma nova root bridge é introduzida), poderá:

• existir uma perda temporária de conectividade, pois uma porta anteriormente bloqueada e que deve ser ativa pode ainda não ter passado a ativa;
• existir ciclos temporários, pois uma porta anteriormente ativa e que deve ser bloqueada ainda não ter passado a bloqueada.

Para minimizar a probabilidade de ciclos temporários, os switches devem esperar algum tempo antes de trocarem uma porta de um estado bloqueado para um estado ativo.

VLANs - Virtual LANs

Existem switches que suportam o uso de VLANs (Virtual LANs), ou seja, permitem configurar redes virtuais para as suas portas.

As VLANs têm algumas vantagens:

• dividem a rede em partes, reduzindo o domínio de broadcast o que, consequentemente, aumenta a bandwidth pois as mensagens não são enviadas para portas desnecessárias;
• adicionam segurança, pois hosts em diferentes VLANs não conseguem comunicar entre si diretamente;

Para as VLANs poderem comunicar entre si, existem mecanismos de routing (pelos routers).

Redes Wireless

Falemos agora de redes Wireless (sem fios). Estas redes usam antenas para efetuar a comunicação entre hosts.

• Hosts Wireless - São tablets, telemóveis, computadores portáteis, etc. Estes dispositivos correm aplicações e podem estar fixos ou em movimento (e.g. telemóvel a andar num corredor).
• Base Station - Uma estação que é responsável por emitir pacotes de forma sem fios para hosts, fazendo a ligação com o resto da rede. Pode estar ligada por cabo (e.g. Access Point) ou pode transmitir para o resto da rede de uma forma wireless também.

Num sistema móvel, devido a frequências muito baixas, não conseguimos detetar colisões e, portanto, não conseguimos usar os algoritmos CSMA/CD vistos anteriormente. Por isso, são usados outros algoritmos.

Handoff - Se um host estiver em movimento e passar de um AP para outro, a comunicação consegue continuar, fazendo com o que o 1º AP passe a conexão (faça handover) para o outro AP.

Apesar de ter várias vantagens, como:

• Permitir comunicação em movimento;
• Permitir comunicação em sítios que é complicado ter rede cablada;
• Permitir fazer broadcasting;
• Ser mais conveniente para os utilizadores;
• Ter menos cabos e ser esteticamente mais bonito;
• ...

Estes sistemas têm várias desvantagens que influenciam a qualidade do sinal, como:

• Ambiente menos controlado, sendo mais subjetivo a interferências e ruído (frequências estandardizadas, usadas por outros hosts, bem como ruído de motores, microondas, ...);
• Velocidades de transmissão menores;
• Propagação em diferentes caminhos, chegando ao destino em timestamps diferentes.

Para além desses problemas, existe um mais grave: o problema do terminal escondido.
Considere a seguinte situação:

Neste caso, os dispositivos A e C desconhecem a existência um do outro, ou seja, os algoritmos de colisão de deteção apresentados não podem ser aplicados, pois estes dois dispositivos não se conseguem "ouvir" um ao outro para saberem que estão a emitir ao mesmo tempo.

Existem dois algoritmos que ajudam a resolver estes problemas:

CSMA/CA - Carrier sense multiple access (with collision avoidance)

Este algoritmo é bastante similar ao básico CSMA. O que difere dele é que, para além de esperar que o canal fique livre, ainda espera um tempo aleatório depois do canal se libertar, e esse tempo só é descontado quando o canal está livre.
Assim, o "sortudo" que teve o tempo menor começa a transmitir e os outros voltam a ficar à espera que o canal fique livre.

Depois de uma transmissão, o AP devolve um ACK para confirmar o sucesso da transmissão. Isto ajuda a resolver o problema do terminal escondido - porém não o resolve na totalidade pois podem haver tempos em que o início das transmissões coincide.

Para resolver isto, surgiu a variante com RTS-CTS.

CSMA/CA com RTS-CTS (Request-To-Send e Clear-To-Send)

Esta variante consiste numa reserva do canal - o emissor, em vez de começar a sua transmissão imediatamente, envia antes um pedido de reserva do canal.
Desta forma, o AP reserva-lhe o canal e dá-lhe um OK, fazendo broadcast de um CTS com a informação de quem vai emitir.
Assim, um outro host que não ouça o emissor, ouvirá certamente o AP e não irá transmitir.

Se tiver existido uma colisão nesse pedido, esta terá um impacto muito reduzido, pois foi apenas transmitido um pacote.

Exemplos dos algoritmos

De forma a explicar os algoritmos, seguem os seguintes exercícios: