Protocolo Batman-adv
Uma vez que é necessário proceder à configuração do protocolo batman-adv, importa perceber melhor este protocolo quanto ao seu modo de funcionamento e de implementação, de uma maneira mais pormenorizada. O protocolo ao longo dos anos sofreu várias alterações e foi sujeito a variados testes. O núcleo do algoritmo evoluiu e neste momento encontra-se na IV geração. Seguidamente serão expostos alguns aspetos do protocolo escolhido sendo descrito como o batman-adv está estruturado quando configurado para uma rede mesh.
Estrutura Batman-adv
O protocolo batman-adv é um protocolo de routing de camada 2 e é implementado como módulo do kernel linux desde março de 2011. Encontra-se integrado numa camada entre a interface dos drivers da rede e a interface virtual da rede, que é usada pelas aplicações para comunicar através da rede mesh. Uma representação da implementação é apresentada na Figura 14. Os pacotes são entregues ao módulo batman-adv, quer através da interface virtual mesh, quer pela interface de rede. O módulo verifica o destino do pacote e reencaminha-o para o próximo melhor nó ou entrega-o na camada superior.
As camadas superiores à interface virtual nada precisam de saber acerca de batman-adv ou da rede mesh. Esta estrutura faz com que a inteira rede mesh atue como um switch virtual que transporta pacotes de uma interface virtual para outra interface virtual.
Envio de pacotes
De forma a poder ter conhecimento dos nós e dos hóspedes da rede, cada nó batman-adv mantém três tabelas:
originators – A tabela originator guarda informação acerca de cada nó da rede mesh e tanto é usada para routing de pacotes locais como para routing de pacotes a reencaminhar.
transtable_global – Guarda informação acerca dos hóspedes da rede e dos nós aos quais estão conectados, ou seja, nós de fim de rede. A transtable_global é consultada quando um pacote local é transmitido, de modo a encontrar uma conexão que leve o pacote ao seu destino.
transtable_local – Guarda informação dos hóspedes conectados ao próprio nó. A transtable_local é usada quando são enviados os OGMs para toda a rede, onde as entradas da tabela relativas a hóspedes são apensas ao OGM de maneira a informar a rede da existência desses hóspedes.
A interface virtual mesh é o local de entrada e saída para a rede mesh. Quando um pacote é transmitido através da interface, é entregue ao batman-adv como sendo uma trama MAC, cujo endereço da interface virtual é o endereço de origem. O destino pode ser uma interface virtual de outro nó, um hóspede ou um endereço de grupo (multicast ou broadcast). Os passos efetuados antes da transmissão dos pacotes encontram-se ilustrados na Figura 15.
Quando é solicitado o envio de pacote para um destino é escolhido o nó que oferece melhores condições de entrega. Então o pacote é construído quer com a informação original quer com a informação do nó que oferece melhores condições de entrega, antes de ser entregue ao driver do dispositivo para transmissão física.
Para reencaminhar o pacote, o protocolo batman-adv procura o endereço de destino na tabela transtable_global e encontra o nó que está conectado ao destino do pacote. O pacote batman-adv é construído com a informação original e com a informação adicional encontrada. Os pacotes que são enviados através da interface virtual (que podem ser enviados para uma camada superior, uma aplicação ou um nó noutra rede que esteja ligada através de uma ponte) são distinguidos dos pacotes que são reencaminhados na rede mesh. Durante esta secção, os pacotes enviados através da interface virtual são denominados de pacotes locais.
Reencaminhamento de pacotes
Os pacotes provenientes da rede mesh são recebidos pelos nós através de um dispositivo de rede e são processados como sendo pacotes batman-adv, isto no caso de o tipo de pacote de Ethernet condizer com o tipo de pacote batman-adv (0x4305). Se o campo da origem do pacote não condiz com o endereço do nó, o pacote é reencaminhado.
A aproximação é similar quando se transmitem pacotes locais, excepto no que diz respeito ao campo que identifica a origem, que já está construído. Para reencaminhar o pacote, é procurado o nó que oferece melhores condições e o pacote é transmitido.
Quando um pacote chega ao nó de destino, o cabeçalho batman-adv é retirado e é entregue na interface virtual. A interface pode estar ligada através de uma ponte e nesse caso o pacote pode ser transmitido para o hóspede conforme descrito anteriormente.
Tipos de pacotes
O protocolo batman-adv tem seis tipos de pacotes diferentes, que são usados para a descoberta da rede. O protocolo possui diferentes tipos de transporte de dados e uma ferramenta de visualização da rede. Cada tipo é sucintamente descrito aqui.
Pacote batman-adv – O pacote batman-adv, também conhecido como OGM, trata-se do pacote primário do protocolo batman-adv. É usado para a descoberta de nós e rotas na rede e cada nó na rede cria e difunde um OGM, num intervalo fixo de tempo. Conforme ilustrado na Figura 16, cada nó atualiza a sua tabela de routing e retransmite os pacotes OGMs, de maneira que os nós mais distantes também “aprendam” acerca do nó originário.
Os OGMs servem dois propósitos principais: anunciar a presença do nó, a possibilidade de esse nó anunciado servir como próximo salto no envio de pacotes e medir a qualidade da rota através do nó anunciado. Ambos serão descritos mais tarde nesta secção.
Os pacotes contêm a seguinte informação, acerca do nó originário e do nó seguinte:
- Endereço do nó originário – identifica o nó que criou o OGM.
- Número de sequência – usado para medir a qualidade da ligação e detetar pacotes duplicados.
- Transmissão de qualidade, em inglês, Transmit Quality (TQ) – descreve a qualidade da ligação da rota total para o nó originário.
- Endereço do nó antecessor que enviou o OGM – usado para descartar OGMs já enviados e novamente recebidos pelo nó recetor.
- Time To Live (TTL) – limita o número de nós que um OGM pode atravessar.
- Contagem Host Neighbour Announcement (HNA) – descreve o número de nós não-batman-adv (nós exteriores à rede) que podem ser alcançados através do nó originário. Informações acerca de cada HNA estão apensas ao OGM.
- Sinalização de Gateway – usada se o nó oferece uma conexão para outra rede.
Internet Control Message Packet – Os pacotes internet control message são usados para suportar um subconjunto de funções fornecidas pela versão IP de ICMP. Como o protocolo batman-adv opera na camada de ligação, os nós na rede nem sempre podem ser alcançados pelos seus endereços IP (por exemplo quando acontece uma falha num nó), assim o batman-adv suporta pedidos de ping, respostas e falhas.
Pacote Unicast – Pacotes unicast encapsulam dados unicast das camadas superiores. Um pacote unicast contém, em adição aos dados reais a transmitir (payload), o endereço de destino e o campo TTL.
Pacote Unicast fragmentar – Devido ao encapsulamento do payload feito pelo batman-adv, o comprimento dos pacotes unicast podem exceder a unidade máxima de transmissão – Maximum Transmission Unit (MTU) permitida para a ligação utilizada, e os pacotes têm de ser fragmentars e agregados no destino. Os pacotes unicast de fragmentação transportam partes do payload e têm um campo de sequência, que é necessário para agregar o pacote unicast original. Têm também um campo que se refere à origem do pacote e que serve para identificar a sequência e flags para sinalizar o fim da sequência.
Pacote Broadcast – Para suportar o envio de pacotes para toda a rede, e não apenas o envio para vizinhos que estejam ao alcance de um nó, os pacotes broadcast são reencaminhados. De maneira a evitar a duplicação de pacotes, os pacotes broadcast possuem um número de sequência, o endereço da origem e o TTL.
Pacote de visualização – O protocolo batman-adv suporta a visualização gráfica da rede. De maneira a obter-se a informação necessária para a visualização, um servidor pode ser iniciado num ou em mais nós na rede. Um servidor anuncia a sua presença através dos pacotes de visualização e cada nó reporta informação de volta para o servidor.
Descoberta de Nós
Como descrito anteriormente, todos os nós numa rede batman-adv transmitem periodicamente OGMs para todos os outros nós da rede. Quando um nó recebe um OGM, realiza os seguintes passos:
- Verifica se o remetente do OGM é ele próprio. Nesse caso o emissor é um vizinho direto e atualiza a tabela de routing de acordo com essa informação.
- Verifica se o campo “remetente anterior” (previous sender) é ele próprio. Se assim for, o OGM já foi processado e é descartado.
- Determina a origem do OGM. Se não existir na tabela de routing, então é criada.
- A classificação do nó originário do OGM é atualizada.
- Os campos da Transmission Quality (TQ) e do TTL são atualizados e o OGM é enviado outra vez.
Também são feitas verificações de maneira a evitar que os pacotes deambulem pela rede, assim como são feitas verificações para evitar duplicação de OGMs.
Estimativa de qualidade de ligação
De maneira a estimar a qualidade de ligação a um nó, a informação Transmission Quality (TQ) existente num OGM é mudada durante o caminho percorrido através da rede. A TQ descreve a probabilidade de um pacote chegar ao seu destino e é calculada conforme se descreve a seguir. O valor da qualidade de ligação é guardado numa sequência de 8 bits, cuja representação do valor se encontra entre 0 e 255, que permite aferir a granularidade da TQ, sem incrementar o tamanho do pacote.
Qualidade de receção – No cenário ilustrado na Figura 17(a), o nó B transmite OGMs que são recebidos no nó A, que calcula a qualidade de receção – Receive Quality. (RQ) do nó B. Para esse cálculo é usada uma janela deslizante de tamanho n (por omissão 128), onde o número de sequência dos últimos n OGMs é recordado. A TQ é então calculada como a percentagem dos OGMs recebidos.
Qualidade de eco – Quando o nó A envia o OGM, o nó B reenvia o OGM recebido, que chega novamente ao nó A – Figura 17(b). Analogamente a RQ, uma janela deslizante é usada para calcular a qualidade de eco – Echo Quality (EQ).
Qualidade de transmissão – A qualidade de transmissão é a probabilidade de um pacote enviado do nó A ser recebido corretamente no nó B – Figura 17(c). Uma vez que a EQ é a probabilidade de um pacote ser entregue corretamente desde o nó A para o nó B e desde o nó B de volta para o nó A, a qualidade de transmissão – Transmission Quality (TQ) pode ser definida em função de RQ e de EQ:
EQ = RQ . TQ TQ = EQ / RQ
Propagação de transmissão de qualidade
Para informar os outros nós da rede acerca da TQ para o nó A, o valor de TQ é adicionado ao OGM. A cada nó atravessado pelo OGM, a TQ global para o nó A é atualizada com os valores locais da TQ em relação ao último nó por onde passou o OGM, conforme ilustrado na Figura 18.
Selecão de rota
Enquanto alguns protocolos de routing calculam a inteira topologia de rede quando escolhem rotas, batman-adv guarda apenas a informação acerca de qual nó é o melhor para chegar ao nó desejado. Quando um pacote é recebido num nó, esse nó volta a escolher novamente o melhor nó para entregar o pacote no destino.
Um cenário de routing é ilustrado na Figura 19, onde o nó F transmite um pacote para o nó A. A única informação que o nó F possui acerca do nó A, são dois TQs globais: um através do caminho pelo nó D e outro através do caminho do nó E. Neste caso o caminho pelo nó D é melhor e o pacote é transmitido pelo nó D, que conhece apenas os TQs globais para o nó A através do nó B, nó C e nó E. Qualquer nó que seja selecionado terá de fazer a mesma escolha. Neste caso o nó C é escolhido, que por sua vez escolhe o caminho direto para o nó A.
Anúncio de hospede
Nos OGMs é incluído o anúncio de hóspedes alcançáveis através dos nós batman-adv, campo denominado de Host Neighbour Announcements (HNA). Como esses hóspedes nada sabem acerca do protocolo batman-adv, o nó que os alcança tem de informar a rede da existência desses vizinhos. Para isso é adicionada uma lista de endereços desses hóspedes ao OGM transmitido pelo nó batman-adv.
Um cenário simples é retratado na Figura 20, onde o nó A está conetado ao vizinho X e o nó C está conetado ao vizinho Y. Quando o nó A recebe um pacote do vizinho X, que é dirigido ao vizinho Y, sabe que o pacote tem de ser transmitido para o nó C da rede mesh.
Tratamento de ligacão assimétrica e atribuição de penalidade
De maneira a assegurar que as melhores ligações são escolhidas, um valor adicional é introduzido de forma a penalizar as ligações que têm uma pobre qualidade de receção – Receive Quality (RQ). Esta penalização de ligação assimétrica (fasym) é um valor ponderado e é determinado através da seguinte fórmula, onde RQ é a Receive Quality:
fasym = (100% -(100% -RQ)3)
Esta penalidade tem uma enorme influência no valor de TQ para ligações com grande taxa de perdas de pacotes e uma pequena influência em ligações com baixa taxa de perdas de pacotes. Um nó que usa o protocolo batman-adv só conhece o melhor nó (best next hop) para chegar a um destino e não a rota na sua totalidade. Assim, o nó não sabe quantos saltos fazem parte da rota. Em algumas redes poderá ser desejável escolher o caminho mais curto para o destino, ou seja, o que apresenta o menor número de saltos, de maneira a reduzir a latência e a poupar largura de banda. Por este motivo uma penalidade de salto (hop_penalty) foi também introduzida por cada salto que o OGM faz, decrescendo a TQ num determinado valor.
Ambas as penalizações são consideradas no cálculo do valor de TQ, cada vez que é recebida uma mensagem OGM. O valor final de TQ é calculado em função da seguinte fórmula:
TQ = TQreceived .TQlocal .fasym .hop_penalty
A Tabela 5 apresenta alguns dos atributos mais importantes e valores por omissão usados no protocolo batman-adv.
