Protocolos das redes mesh
Um dos padrões mais populares para ilustrar a arquitetura de uma rede é o modelo Open Systems Interconnection (OSI), desenvolvido pelo International Standards Organization. O modelo OSI, especifica um conjunto de funções da rede, agrupado em camadas, conforme se pode observar na Figura 8.
A combinação das camadas da arquitetura da rede definem a funcionalidade de uma rede wireless, mas a implementação de uma rede wireless é feita apenas nas camadas inferiores do modelo.
Camada física
A camada física é a camada mais baixa no modelo OSI e refere-se ao próprio meio físico no qual a comunicação ocorre. Pode ser um cabo de cobre, fibra ótica, ondas de rádio ou qualquer outro meio capaz de transmitir sinais. As redes wireless usam as ondas de rádio, propagando o seu sinal pelo meio físico, que é o ar. A Figura 9 mostra o espectro disponível de frequências para a banda b/g da norma 802.11, onde se pode observar que os canais 1, 6 e 11 não interferem entre si.
A maioria dos modelos de routers em uso atualmente, têm a capacidade de transmitir o sinal usando múltiplos canais. Numa rede constituída por vários dispositivos que utilizem só um canal, a comunicação é half-duplex. Isto quer dizer que esses dispositivos não podem transmitir e receber um sinal simultaneamente. Assim a largura de banda transmitida é reduzida significativamente. Além disso quando um nó transmite, todos os outros nós têm que escutar e não podem transmitir, senão causariam uma colisão. Num ambiente constituído por dispositivos com capacidade de transmitir o sinal usando múltiplos canais, cada nó pode sintonizar a sua interface rádio em diferentes canais e assim aumentar a capacidade de transmissão. Essa capacidade de transmissão, ainda pode ser melhorada em ambientes com dispositivos constituídos por múltiplas interfaces rádio, com capacidade de transmissão usando múltiplos canais.
Camada de acesso ao meio
Esta camada assegura o acesso ao meio, assim como controla a sincronização entre duas entidades. Exemplos de protocolos de usados para o acesso ao meio são Ethernet, Token Ring, ATM e os vários protocolos wireless 802.11 a/b/g/n, etc.
Nas redes wireless, esse controlo envolve a coordenação do acesso ao meio que é o ar, assim como a correção dos erros que possam ocorrer quando os dados são propagados desde a origem para o destino. Nas WMNs, os melhoramentos realizados nos tradicionais protocolos de contenção, normalmente não são suficientes para melhorar a eficiência e a equitatividade no acesso ao meio. Os protocolos tradicionais de acesso ao meio são limitados. Por exemplo, dispositivos com múltiplas interfaces rádio que usam múltiplos canais para a transmissão do sinal, trazem novos problemas à atribuição de canais e ao acesso ao meio. Rádios Multiple Input and Multiple Output (MIMO) foram propostos para incrementar a capacidade das WMNs, de forma a mitigar a falta de equitatividade no acesso ao meio.
Camada de rede
Os protocolos de roteamento para redes mesh têm de ser concebidos tendo em mente os desafios da comunicação rádio. As ligações wireless e a topologia de uma rede mesh são intrinsecamente instáveis. Os dispositivos da rede podem-se ligar e desligar, a largura de banda varia e as ligações muitas vezes falham com a consequente perda de pacotes.
Um protocolo de routing deve ser resiliente contra os erros de routing mesmo que as mensagens do protocolo cheguem atrasadas ou sejam perdidas. A largura de banda disponível e o desempenho dos nós mesh são limitados e não devem ser desperdiçados com decisões de protocolo e com tráfego de cabeçalhos. Há algum tempo atrás só existiam alguns (poucos) protocolos de routing que se podiam utilizar na prática para redes mesh, como por exemplo Optimized Link State Routing Protocol (olsr). Atualmente existe um leque variado de protocolos e implementações mesh e algumas dessas implementações encontram-se disponíveis nos pacotes de instalação de OpenWRT, um sistema operativo linux usado em routers para encaminhamento de tráfego. A maioria dos protocolos de routing mais recentes (BABEL, Better Approach To Mobile Adhoc Networking - BATMAN, B.a.t.M.a.n –eXperimental - BMX, version 6 - BMX6) encarregam-se de manter as tabelas de routing IPv4 e IPv6 em cada nó mesh adicionando, atualizando e removendo rotas. Estes protocolos mesh usam routing com base em IP. São protocolos mesh que utilizam a camada 3 do modelo OSI. O protocolo batman-adv é um protocolo relativamente novo que funciona na segunda camada do modelo OSI. Logo é um protocolo mesh de camada 2.
Para as camadas superiores (incluindo IP), batman-adv faz com que toda a rede mesh se apresente como um switch, onde todas as conexões são locais. O protocolo batman-adv é transparente para as camadas superiores do modelo OSI. Isto simplifica a configuração da rede mesh, uma vez que é possível usar Dynamic Host Configuration Protocol (dhcp), multicast dns (mDNS) or MAC bridging conjuntamente com batman-adv. batman-adv é um módulo do kernel do sistema operativo linux, que já está incorporado nas distribuições oficiais. Seguidamente far-se-á uma descrição mais pormenorizada de alguns protocolos de routing utilizados nas redes mesh. Poder-se-á consultar uma lista de protocolos de routing adhoc mais extensa e divida por tipos.
Batman
O protocolo Better Approach To Mobile Adhoc Networking (BATMAN) é um protocolo proativo para determinar rotas multi-hop em redes adhoc móveis. O desenvolvimento do protocolo BATMAN começou no RFC 3626, que não era completamente funcional em cenários práticos, particularmente onde existe uma larga distribuição de nós e em ambientes onde ocorriam falhas, nomeadamente de ligações ou de nós que por algum motivo ficavam inacessíveis. A aproximação desenvolvida pelo BATMAN consiste em espalhar o conhecimento dos melhores caminhos para o destino, pelos nós participantes. Nessa abordagem, cada nó percebe e mantém a informação acerca do “melhor próximo salto” (best next hop) em direção a todos os outros nós, o que evita conhecimento desnecessário acerca da totalidade da topologia e reduz a sinalização do cabeçalho.
Algoritmo: Cada nó envia mensagens da sua origem para informar os nós vizinhos da sua existência. Estas mensagens são denominadas de OriGinator Message (OGM). Os vizinhos, por sua vez, retransmitem os OGMs para informar os seus próprios vizinhos acerca da existência do nó, e por aí adiante. A rede é inundada com esses pequenos pacotes que contêm o endereço do nó original, o endereço do nó que está a retransmitir e um número de sequência que define o período de duração desses pacotes – Time To Live (TTL). Cada nó retransmite o OGM uma única vez, só se receber do nó considerado o melhor salto (best hop), o sinal para iniciar a transmissão. Assim a rede mesh é seletivamente inundada de mensagens OGMs. A descoberta de rotas e a seleção de vizinhos depende do número e da fiabilidade dos OGMs recebidos. Os números de sequência servem para se perceber o quanto a informação se encontra atualizada na rede, pois qualquer mensagem recebida com um número de sequência inferior ao número de sequência recebido na mensagem anterior é deitada ao lixo. Os nós podem alterar o TTL dos seus OGMs de forma a limitar o número de saltos que as mensagens podem atravessar. Isto é útil para os nós pertencentes ao backbone, cujas funções consistem em assegurar a melhor conetividade e cobertura possíveis. Normalmente o backbone é constituído pelos nós centrais da rede, que costumam estar ligados ao terminal da rede e que prolongam esse terminal até onde for possível, sendo depois a propagação do sinal feita por nós da rede mesh.
O protocolo BATMAN ultrapassa os outros protocolos, em quase todas as métricas de desempenho, devido à sua conceção simplista. Ao não recolher mais informação do que a que efetivamente pode usar, e ao obter apenas informações acerca dos seus vizinhos, os nós podem calcular rotas de uma maneira mais eficiente. O cabeçalho de routing é significativamente menor do que por exemplo, o do olsr, o que evidencia que aproximações complexas às vezes conduzem a um menor desempenho.
O protocolo BATMAN, inicialmente foi lançado como um protocolo clássico de camada 3 OSI (L3), que utiliza pacotes User Datagram Protocol (udp) para trocar informação sobre routing. Mais tarde, uma extensão BATMAN ADVanced (batman-adv) foi desenvolvida para trabalhar na camada 2 (L2) OSI. Esta versão emula uma ponte Ethernet (Ethernet bridge), de modo que todos os nós pareçam estar ligados diretamente e todos os protocolos que operam no topo dessa camada não estejam conscientes da natureza multi-hop da rede subjacente. Os princípios de funcionamento do batman-adv são idênticos ao BATMAN clássico, com as adaptações para tratamento dos endereços da camada 2 (L2), em vez dos endereços IP. Em vez de o deamon, utilizado na versão original do BATMAN, funcionar no espaço do utilizador (user space), funciona no espaço do kernel (kernel space), evitando assim o custo de copiar pacotes de e para o espaço do utilizador. batman-adv encapsula todo o tráfego que entra e sai funcionando como um switch entre todos os nós. Neste momento o protocolo suporta bridging e roaming de clientes não-mesh. Atualmente o batman-adv (L2) é incluído no kernel do sistema operativo linux como um módulo. Para usá-lo apenas basta carregá-lo e pode-se controlá-lo através da ferramenta “batctl”.
OLSR
O Optimized Link State Routing (olsr) é um protocolo proativo para redes móveis adhoc. Inclui um número de otimizações cujo objetivo é reduzir o custo da propagação de informação na rede. Em particular para cada nó existe um subconjunto de vizinhos, chamados de Multi Point Relays (MPR), cuja função é reduzir retransmissões duplicadas na mesma região.
Algoritmo: Cada nó escolhe o seu conjunto de MPRs entre os seus vizinhos que estão à distância de um salto de maneira a conseguirem dar cobertura até dois saltos de distância, usando esses mesmos MPRs selecionados. olsr impõe que existam ligações bidirecionais para cada um desses nós. Cada nó pertencente à rede, periodicamente, difunde para a rede informação dos seus vizinhos selecionados como MPRs, que se encontram à distância de um salto. Ao receber esta lista de seleção de MPRs, cada nó calcula ou atualiza as suas rotas. A rota é então uma sequência de saltos através de MPRs.
De maneira a detetar ligações bidirecionais com os vizinhos, cada nó envia, periodicamente, mensagens hello, que contêm a lista de vizinhos e o estado da sua ligação. As mensagens hello contêm a lista de endereços com quem o nó tem uma ligação bidirecional, assim como a lista dos vizinhos que consegue “ouvir”. O conteúdo dessas mensagens permite cada nó conhecer a existência dos seus vizinhos até dois nós e a seleção dos seus MPRs, que também são indicados nas mensagens hello, e construir a sua própria tabela de seleção de MPRs. Cada nó difunde mensagens de controlo específicas chamadas de Topology Control (TC), de maneira a construir a tabela de encaminhamento (routing). As mensagens TC são enviadas periodicamente pelos nós de modo a declarar o conjunto de MPRs selecionados (se a lista de MPRs estiver vazia, a mensagem não é enviada). As mensagens TC são utilizadas para manter as tabelas de topologia para cada nó.
Uma vez que se trata de um protocolo de routing proativo, não existe um atraso quando é necessário descobrir uma rota. Embora o cabeçalho de routing seja maior do que o cabeçalho de um protocolo reativo, isso não implica que o cabeçalho aumente com o número de rotas em uso. Rotas por omissão e rotas existentes podem ser injetadas no sistema. Para que a informação esteja atualizada são utilizados valores de tempo e de validação da informação. O olsr assume que a ligação está válida e a funcionar se um número de mensagens TC foi recebido recentemente.
Existem algumas extensões para caracterizar a qualidade da ligação, como por exemplo OLSRd (deamon) que é frequentemente usado nos routers com distribuições linux e que foi vulgarmente chamado de Radio-Aware olsr. Esta extensão foi incluída no draft da norma 802.11s e foi influenciada pelo Hazy-Sighted Link State (HSLS).
O protocolo olsr produz imensa informação, o que pode causar alguma inconsistência relativamente aos estados das ligações, principalmente devido a perda de pacotes, o que origina a propagação de dados acerca de rotas que possivelmente não são usadas. Também o protocolo requer uma determinada energia para calcular os caminhos ótimos na rede, assim como provoca uma quantidade bastante grande de cabeçalhos de routing devido às mensagens de Topology Control (TC), que consomem demasiados recursos de largura de banda.
Na tentativa de resolver algumas das limitações aqui referidas, foi criado o projeto OLSR-NG. No olsr original, assim como neste novo projeto OLSR-NG, no cálculo das rotas é usado o algoritmo de Dijkstra, sendo que para o olsr original é utilizada a fórmula O(n²), enquanto no OLSR-NG é utilizada a fórmula O(n*(log(n)), onde O representa o pior caso possível em notação matemática e n representa o número de nós, o que se reflete num menor número de cálculos para OLSR-NG.
AODV
O Ad-hoc On-demand Distance Vector (AODV) é um protocolo reativo que cria e mantém rotas só quando são solicitadas. Em cada nó, na tabela de routing, é armazenada informação acerca do próximo router (next hop) para o destino desejado e um número de sequência recebido desse mesmo destino, preservando a informação atualizada.
Algoritmo: Tipos de mensagens do AODV são: Route REQuests (RREQ), Route REPlies (RREP) e Route ERRors (RERR). Quando solicitada, a descoberta da rede é feita através de uma mensagem RREQ difundida pelos vizinhos que possam reencaminhar essa mensagem ao destino desejado. Cada nó que recebe o pedido incrementa a métrica de saltos (hops) e atualiza a sua própria tabela. Entradas que não sejam usadas na tabela de routing são removidas após um certo tempo. Quando uma ligação falha, é devolvido ao nó transmissor um erro de routing e o processo repete-se. Os nós reagem às quebras de ligação e às mudanças de topologia, oportunamente. Se uma ligação falha, um erro de routing é enviado ao nó transmissor. Assim o protocolo AODV notifica o conjunto de nós afetados, de maneira a que esses nós possam invalidar as rotas onde conste essa ligação perdida. O AODV é um protocolo loop free, ou seja, os pacotes não deambulam indefinidamente pela rede. O AODV oferece uma rápida convergência quando a topologia de rede muda, como por exemplo quando um nó se move, evitando o problema de Bellman-Ford - “counting to infinity”. O AODV possibilita que o routing seja dinâmico, regenerador e com alcance de múltiplos saltos (multi-hop) entre nós móveis numa rede adhoc. Protocolos reativos como AODV tendem a reduzir os cabeçalhos das mensagens usados para controlo de tráfego, embora isso acarrete o custo de um incremento da latência quando procura novas rotas.
OFLSR
O protocolo Optimized Fish-eye Link State Routing (OFLSR) combina dois protocolos existentes: olsr e Fish-eye State Routing (FSR).
O protocolo olsr já foi abordado anteriormente. O protocolo FSR pertence à classe de protocolos adhoc proativos, também denominados de table-driven protocols, cujos mecanismos têm por base o protocolo Link State Routing usado nas redes com fio. Esse protocolo tenta minimizar o cabeçalho usando a técnica de olho-de-peixe (fish-eye). Os intervalos das atualizações sobre o estado da ligação para os nós mais distantes são mais longos do que para os nós que se encontram na vizinhança, tendo como referência o olho-de-peixe (área circular à volta de um determinado nó). Assim, o protocolo FSR origina uma boa diferenciação entre zonas de redes adhoc móveis e suporta altas taxas de mobilidade.
O protocolo olsr origina uma quantidade grande de cabeçalhos de routing devido ao encaminhamento da mensagens Topology Control (TC), sendo que o protocolo OLFSR limita este fluxo de mensagens TC, adotando a técnica de olho-de-peixe, uma vez que a fonte apenas precisa de saber rotas aproximadas para os destinos mais longínquos. Com a redução do tamanho das mensagens do estado das ligações, o desempenho do protocolo OFLSR poderá ser melhorado.
DSR
O protocolo Dynamic Source Routing (DSR) é um protocolo simples e eficiente concebido especificamente para ser usado em redes adhoc sem fios (wireless) multi-hop de nós móveis, pertencente à classe de protocolos reativos. O protocolo DSR permite que a rede se auto-organize e auto-configure, sem a necessidade da existência de uma administração de infraestrutura da rede. O DSR usa IP routing, ou seja, todos os pacotes enviados usam o protocolo DSR que contém a lista completa dos nós que os pacotes têm de atravessar.
Existem dois mecanismos principais: descoberta de rotas e manutenção de rotas, que trabalhando em conjunto permitem que os nós descubram e mantenham rotas para vários destinos da rede. Quando é solicitada uma operação de entrega de pacotes, o cabeçalho de routing dos pacotes é ajustado automaticamente para que sejam alteradas só as mudanças necessárias nas rotas em uso, de maneira a que os pacotes sejam entregues. O protocolo permite que sejam encontrados múltiplos caminhos para o destino, no entanto permite ao nó emissor que selecione a rota com base em alguns critérios, tais como o balanceamento da carga, o que permite o controlo das rotas usadas para envio dos pacotes.
Este protocolo evita a necessidade de atualização da informação das rotas nos nós intermediários, assim como reduz o cabeçalho de controlo, eliminando as mensagens periódicas de atualização de tabelas e guardando em memória a informação disponibilizada pelos outros nós. O atraso na configuração das conexões é maior do que nos protocolos proativos (table-driven). O protocolo DSR tem um bom desempenho em ambientes estáticos e de baixa mobilidade, mas o desempenho degrada-se rapidamente com o incremento da mobilidade. O cabeçalho de routing é proporcional ao tamanho do caminho, devido ao mecanismo de routing utilizado no DSR.
BMX6
O protocolo BatMan eXperimental version 6 (BMX6) é baseado no código do BATMAN 0.3 (L3), mas agora na versão 6 foi totalmente reescrito. Inicialmente foi uma extensão do BATMAN mantido por Axel Neumann, com alguns melhoramentos no algoritmo de routing. É provavelmente o protocolo mais parecido com o BATMAN original, uma vez que usa pacotes udp para a descoberta de vizinhos declinando a ideia do estado de ligação. Alguns extras foram desenvolvidos, como por exemplo uma pequena mensagem embutida que permite enviar qualquer informação para o resto dos nós usando os mesmos OGMs. Pode-se caracterizar o protocolo BMX6 como sendo proativo, ou seja, mantém e atualiza a tabela de routing periodicamente, distribuindo informação pela rede que é uma rede loop-free e utiliza o algoritmo Destination-Sequenced Distance-Vector (DSDV). Os nós não sabem a topologia inteira da rede, mas apenas o vizinho que oferece melhores condições para um destino específico.
Como o seu antecessor BATMAN, o BMX6 envia periodicamente pacotes OGMs para os vizinhos, que contêm o endereço do destinatário, normalmente a cada meio segundo. A mensagem flui pela rede, e graças a este reencaminhamento, um nó fica a conhecer a existência de todos os participantes da rede mesh. BMX6 não usa como identificador dos nós os endereços IP. Em vez disso usa identificadores globais Secure Hash Algorithm (SHA), baseados em SHA2, encriptados, e usa pequenos identificadores locais para representar os nós e interfaces relacionadas na rede mesh. Como resultado disto o cabeçalho é bastante reduzido devido ao impacto marginal que o tamanho do endereço IP acarreta.
Uma característica interessante que o BMX6 apresenta é uma extensão (plug-in), de nome SMS. Esta extensão usa os pacotes de routing para transmitir qualquer informação de um nó para toda a rede. A propagação funciona, mesmo que não exista caminho para os dados. Ainda que a rede WiFi esteja sujeita a más condições, como por exemplo ruído, distância entre nós, etc, os dados serão propagados. O funcionamento consiste na clonagem de um ou mais ficheiros enviados por um nó para todos os outros nós. Todos os nós podem proceder da mesma forma. O funcionamento é simples, tendo cada nó duas diretorias localizadas em /var/run/bmx6/sms/send e /var/run/bmx6/sms/rcvd. Os ficheiros colocados na pasta send serão clonados para todos os outros nós, que os receberão na pasta rcvd. Esta funcionalidade está a ser utilizada para gerar informação quanto ao posicionamento da rede no mapa, e pensa-se que poderá servir para outros propósitos como por exemplo estatísticas, captive portals, filtragem de MACs, etc.
BABEL
O protocolo BABEL é um protocolo proativo baseado no protocolo de routing distance vector. Este protocolo é mais recente do que olsr e BATMAN. Foi concebido com base no Destination-Sequenced Distance-Vector routing (DSDV). A técnica de utilizar números de sequência é replicada do protocolo DSDV de maneira a prevenir uma contagem até ao infinito dos pacotes que circulam na rede. O BABEL também adota o Enhanced Interior Gateway Routing Protocol (EIGRP) – protocolo que permite prevenir os loops (voltas) de routing e assim, rapidamente, consegue convergir caminhos livres de loops (loop-free path). O protocolo BABEL utiliza a métrica Expected Transmission Count (ETX – utiliza a taxa de perda de pacotes para determinar o melhor caminho), utilizada também pelo protocolo olsr. Este protocolo tem como característica principal a otimização do mecanismo de transmissão. Para isso, utiliza um histórico para selecionar rotas. Se aconteceram problemas em determinadas rotas, que tenham inviabilizado o uso dessas mesmas rotas, poderá optar por outros caminhos que apresentem a mesma qualidade de ligação. Assim, será escolhida uma rota que já tenha sido utilizada com sucesso em detrimento de outra rota alternativa. O protocolo BABEL executa uma atualização reativa e força um pedido de informação de routing quando deteta que uma ligação a um dos seus vizinhos preferidos falhou. Num estudo publicado, onde foram realizados testes de consumo de energia, testes de atraso (delay), testes de perdas de pacotes, testes de cabeçalhos e testes de percentagem de pacotes fora de ordem, sendo os protocolos comparados AODV, olsr, BATMAN (L2) e BABEL, verificou-se que o protocolo BABEL apresentou os melhores resultados, tendo o melhor desempenho comparativamente aos outros protocolos.
HWMP
O Hybrid Wireless Mesh Protocol (HWMP) é o protocolo por omissão das WMNs. A norma IEEE 802.11s apresenta um tipo de topologia de rede chamado Mesh Basic Service Set (MBSS).
MBSS pode ter os seguintes três tipos de entidades: uma estação mesh (Mesh station), que se trata de uma normal estação 802.11s com funcionalidades acrescidas de descoberta de rotas e encaminhamento de pacotes; um ponto de acesso mesh, que é uma estação mesh que providencia conectividade aos utilizadores finais; e um portal mesh que interconecta a WMN com outras redes diferentes de 802.11, como por exemplo 802.3. A norma 802.11s especifica o HWMP que funciona na camada MAC, como sendo o protocolo obrigatório para a seleção de caminhos/rotas. Algoritmo: Os nós podem usar dois modos de operação e podem construir uma árvore de caminhos a pedido (On-demand-Mode) ou proativamente. O On-demand-Mode é baseado no protocolo AODV, como já vimos anteriormente funciona na camada MAC. Neste caso existem três pacotes de controlo diferentes: Path REQuest (PREQ), Path REPly (PREP) e Path ERRor (PERR), sendo o seu funcionamento em tudo análogo ao AODV. Quando um nó quer enviar informação, envia PREQ para toda a rede. Cada PREQ tem um número de sequência (análogo a situações já descritas anteriormente), que permite que os nós percebam se se trata de uma mensagem antiga ou recente. Os nós intermediários que recebem o PREQ criam ou atualizam o caminho para a fonte, dependendo desse número de sequência; se não existir caminho, simplesmente reencaminham o pedido até que este chegue ao destino. Quando o caminho se encontra estabelecido, guarda-o na memória e os subsequentes PREQs não são reencaminhados durante algum tempo. Quando o destinatário recebe o PREQ, envia um PREP via unicast de volta para o nó n.
No modo proativo de construção da árvore, um dos nós funciona como ROOT (raiz), neste caso nó r. O nó r periodicamente envia para toda a rede PREQs. O campo de endereço desses PREQs é um endereço broadcast (difundido para toda a rede), assim todos os nós que recebem os PREQs, enviam um PREP para o nó r. Desta forma é construída uma árvore proativa e o nó r tem a tabela de routing preenchida com todos os possíveis destinos da rede.
No modo híbrido, tanto os componentes proativos como os reativos concorrem no seu funcionamento. Extensões do HWMP permitem escolher qualquer métrica de routing ou combinação de métricas. O on-demand routing oferece uma grande flexibilidade em redes que variam de topologia. Já a árvore construída proativamente é muito eficiente em redes mesh fixas. A combinação de ambos faz com que o HWMP seja apropriado para uma variedade de diferentes configurações de rede. A métrica usada por omissão é baseada na métrica airtime, que é similar á métrica ETX, já referida anteriormente. Pode-se combinar com outras métricas para se obter melhor desempenho.
O on-demand routing no HWMP permite que os nós rapidamente obtenham rotas para novos destinos. Não obriga a que rotas para destinos que não apresentem comunicação ativa sejam mantidas. Para a descoberta de rotas, o on-demand routing utiliza um método para limitar o excesso de pacotes de routing, denominado de algoritmo expanding ring search. São utilizados os tipos de mensagens já vistos anteriormente no protocolo AODV – Route REQuests (RREQ), Route REPlies (RREP) e Route ERRors (RERR) – para as definições de rotas. No que concerne à manutenção de rotas é utilizado também o tipo de mensagens Route ERRors (RERR). Todos os nós da rede possuem e mantêm o número de sequência de destino, o que garante loop-freedom de todas as rotas relativamente a esse nó específico. Os pontos de acesso Mesh monitorizam as ligações e podem alterar as ligações usando RERRs, evitando a recontrução da árvore. A perda de ligação provoca também um RERR, o que faz com que os nós decidam/selecionem outros caminhos de recurso.
SHWMP
O HWMP é vulnerável a vários tipos de ataques, pelo que foi proposta uma versão Secured Hybrid Wireless Mesh Protocol (SHWMP) como sendo a versão segura do HWMP, isto é, uma extensão de segurança da norma 802.11s. O SHWMP opera de uma forma similar ao HWMP, mas usa extensões de criptografia de maneira a assegurar autenticidade e integridade nas mensagens de routing e previne manipulação não autorizada nos campos de informação de routing. É uma forma robusta de segurança contra ataques e providencia uma taxa maior de entrega de pacotes quando comparado com o tradicional HWMP. Tendo em conta o sistema de troca de chaves existente na norma 802.11s (os nós possuem uma chave e uma palavra-passe para se autenticarem e reconhecerem), evita-se uma sobrecarga de troca de chaves. Os campos mutáveis e os não mutáveis na mensagem de routing são identificados, protegendo-se a parte não mutável através de encriptação de chave simétrica. É utilizada a abordagem Merkle-Tree (árvores de dispersão ou árvores de Merkle – transformam a chave numa sequência de caracteres encriptados) para autenticar a informação mutável. Uma vez que só executa operações com chaves simétricas, a computação torna-se eficiente.
Comparação de protocolos
O protocolo de routing é provavelmente o componente mais importante de uma rede mesh. Quando se gere um pequeno grupo de nós, torna-se uma tarefa simples e transparente, uma vez que a rede funciona relativamente bem, independentemente do protocolo utilizado. Atualmente a maioria das redes utilizam protocolos como Border Gateway Protocol (BGP) ou Open Shortest Path First (OSPF), que serão provavelmente uma boa escolha para ambientes estáticos, principalmente devido à sua simplicidade e estabilidade. Contudo, nos cenários atuais, e principalmente na próxima geração de redes, a rede estará em constante mutação e os protocolos estáticos não são adequados para estes casos. É necessário um protocolo mais complexo. Outras métricas, para além do número de saltos, devem ser tidas em consideração, como por exemplo a perda de pacotes, saturação dos caminhos, qualidade das ligações, etc.
A pergunta óbvia é: qual o protocolo a adotar? É difícil selecionar um protocolo, uma vez que alguns protocolos encontram-se em constante desenvolvimento e mudam frequentemente. Muitos deles nasceram em ambientes de hackers onde os seus criadores os desenvolveram apenas por gozo ou para poderem manter as suas próprias redes. Atualmente um dos protocolos mais estáveis é o olsr, provavelmente devido ao RFC que já tem quase dez anos, o que faz com que a implementação esteja bastante “madura”. Mas essa maturidade também se poderá considerar em vias de desatualização, uma vez que as redes e os aparelhos mudaram bastante. Os protocolos BABEL e BATMAN são protocolos relativamente novos e foram concebidos para redes comunitárias. Apresentam características interessantes baseadas na experiência das pessoas das comunidades. A escolha do protocolo deve ser bem ponderada, pois significa que a rede dependerá sempre dele. Se as pessoas que os desenvolvem decidirem deixar de os desenvolver (porque a partir de um dado momento se torna um produto comercial e fechado ou porque apenas se desinteressam e abraçam novos desafios) fará com que a rede fique desatualizada, obsoleta e obrigará à mudança de sistema em cada nó. Se porventura algum nó se encontrar num local de difícil acesso ou mesmo inacessível, poderá acontecer que não possa ser alterado. Estas são algumas das considerações a ter em conta na seleção do protocolo.
Alguns estudos, testes e publicações podem ajudar nessa escolha, embora os critérios para a diferenciação possam sempre ser discutíveis. Apresenta-se aqui algumas considerações.
Tanto o protocolo AODV como OFLSR funcionam bem nas WMNs com pouca carga de tráfego. O protocolo AODV deixa de ser escalável à medida que a carga aumenta. Por outro lado, OFLSR proporciona um melhor desempenho em termos de taxa de entrega de pacotes, débito, latência e cabeçalhos de routing debaixo de diferentes condições de tráfego e mobilidade. A implementação atual do “rascunho” corrigido da norma 802.11s pelo open802.11s (open-source) e pelo batman-adv (L2) em ambientes estáticos evidencia que batman-adv apresenta melhor desempenho onde open802.11s apresenta instabilidade. Contudo open802.11s recupera mais rapidamente, em caso de falha de nó. O batman-adv tem alguma dificuldade em restabelecer a comunicação depois de uma interrupção abrupta. Alguns resultados confirmam que o cabeçalho do olsr é maior do que o do BATMAN. O BATMAN atinge o maior nível de estabilidade e de entrega de pacotes, enquanto BABEL oferece a maior largura de banda em ambiente multi-hop e o menor tempo de reparação de rotas em caso de falha. Tanto o BATMAN como BABEL apresentam melhor desempenho que olsr, em várias métricas examinadas.
Outro estudo sugere que olsr e BATMAN são similares. Estudos teóricos sugerem que BATMAN supera olsr em quase todas as métricas de desempenho, devido à sua aproximação simplista, no entanto ainda será necessário aprofundar os testes, para se poder provar essa ideia. Em redes adhoc multi-hop, o cabeçalho de routing existente nos protocolos tem um largo impacto no débito da rede. O protocolo BABEL proporciona um alto débito em redes pequenas, no entanto tem de ser melhor testado em redes maiores. Testes realizados com BABEL criam algum incentivo na prossecução do estudo de BABEL, uma vez que este protocolo apresenta um desempenho bastante interessante. Muitos estudos indicam que os sistemas híbridos apresentam um melhor desempenho quando comparados com sistemas não híbridos . O protocolo híbrido HWMP é bastante escalável para WMNs. Já o SHWMP, que envolve cálculos de encriptação de chaves simétricas, supera o HWMP.
Wireles Battlemesh
Anualmente acontece um evento denominado de “Wireless Battlemesh”, que pretende juntar pessoas de todo o mundo para testar o desempenho de diferentes protocolos usados em redes adhoc, tais como BABEL, BATMAN, BMX, olsr e routing estático. É um torneio com caráter social, onde além de se testarem os protocolos na tentativa de se aferir qual será o melhor, aproveita-se para testar novas implementações, ferramentas, drivers, scripts e hardware, entre outras coisas descritas em Battlemesh
Battlemesh IV – Espanha - 2011
O cenário de testes consistiu num total de 33 nós (routers), distribuídos por um grande complexo (aproximadamente 2000 metros quadrados), com as seguintes especificações:
Hardware: Fonera 2100 e Fonera 2200 Um rádio 2.4 Ghz (802.11bg) Uma porta Fast Ethernet OpenWRT como sistema operativo.
O teste é feito debaixo de más condições, porque todos os routers usam o mesmo canal, o hardware não é poderoso (são usados cinco protocolos em cada nó, o que faz com que o CPU esteja sempre ocupado) o rádio/antena foi concebido para uso interno (indoor), a ligação entre nós afastados é má. Contudo estas condições nem são uma menos valia, pois assim obriga os protocolos a demonstrarem as suas melhores funcionalidades.
Os testes foram de um nó para todos os outros nós, conforme se pode ver na Figura 10.
Desde o nó central foram realizadas as seguintes provas:
1. 50 pings com um intervalo de 0,1 ms de maneira a obter o Address Resolution Protocol (ARP) dos seus vizinhos. 2. 5 testes de 20 pings com um intervalo de 0,2 ms para o nó de destino.
Foram realizados um total de 3 testes, identificados pela hora de início:
1. T519 (05:19) 2. T630 (06:30) 3. T744 (07:44)
Conforme se pode constatar, cada teste demorou cerca de uma hora a ser concluído. Os protocolos foram divididos em dois diferentes grupos:
A: Babel, olsr, BMX6 B: Batman, Batman-adv
O número de nós que constituem o cenário do grupo B é de 25 (em vez dos 33 nós que constituem o grupo A), porque não estão a usar a interface Ethernet.
Resultados
Na Tabela 1 são apresentados o número total de nós vistos por cada protocolo.
Como foram criados dois grupos (A e B), foi necessário comparar os protocolos em função da percentagem de nós vistos a partir do nó central, conforme apresentado na Tabela 2.
O número de nós vistos a partir do nó central é ilustrado na Figura 11.
Na Tabela 3 são apresentados os valores percentuais relativamente à taxa de sucesso de pings bem sucedidos por cada protocolo (um ping bem sucedido significa que houve uma resposta de pelo menos um ping em vinte pedidos, valor de cada teste).
Na figura 12, pode-se observar o resultado de pings bem sucedidos
Na Tabela 4 são apresentados os valores de latência por protocolo. Os valores são apresentados em milisegundos.
Os resultados referentes à latência, podem ser visualizados na Figura 13:
Conclusões
Não é completamente clara a conclusão acerca destes testes. Apenas fornece uma ideia sobre o funcionamento dos protocolos de roteamento. Mais tipos de provas são necessários para se chegar a conclusões relevantes, como por exemplo a utilização de um protocolo de transporte persistente como Transmission Control Protocol (TCP), que tente que os pacotes sejam entregues, uma vez que neste teste foram usados pacotes Internet Control Message Protocol (ICMP).
Outra observação pertinente pode ser feita relativamente às WMNs. Efetivamente nestes testes não foi considerada a mobilidade, o cenário é estático e muitos dos protocolos implementados apresentam características interessantes para ambientes móveis.
Contudo algumas considerações podem ser retiradas. Tendo em conta que foram criados dois grupos de protocolos e que foi utilizado como meio de comparação os valores percentuais dos testes realizados, verifou-se que no teste de nós vistos a partir do nó central, BMX6 e batman-adv tiveram os melhores resultados, cada qual no seu grupo. A percentagem de nós detetados para cada um é de 82% e 89%, respetivamente, sendo bastante mais elevada que a dos outros protocolos. Também quanto à comunicação entre nós parece ser bastante estável, verificando-se a percentagem de 99% para BMX6 e de 97% para batman-adv (são deduzidas da prova de pings bem sucedidos).
Temos de ter em conta que o cenário não é dos mais fáceis e estes números são a prova que estes protocolos têm uma boa implementação e que conseguem operar em más condições. E não se deve esquecer o olsr nem o BABEL. Os números de olsr estão perto de BMX6 e atrás já foi referido que BABEL é bastante rápido e eficiente a recuperar de quebras de ligações e a encontrar rotas alternativas rapidamente, assim como apresenta algumas extensões bastante interessantes, como por exemplo “SMS”.
Os protocolos que apresentam resultados mais interessantes do ponto de vista de desempenho e de continuidade no futuro próximo são os protocolos que se encontram em constante evolução, com imensas pessoas a colaborar a partir de toda a parte do mundo, usando para isso as mailing lists que estão disponibilizadas na internet. Para se poder participar basta fazer um registo e pode-se trocar informações ou colocar dúvidas e participar na conceção de código..
Tendo em conta que:
- Existe uma comunidade interessada e que trabalha diariamente no seu desenvolvimento;
- O projeto é amplamente divulgado e já faz parte das distribuições oficiais do sistema operativo linux e também do firmware OpenWRT;
- É um protocolo inovador quanto à filosofia de routing, nomeadamente por ser um protocolo de camada 2 OSI, que utiliza endereços MAC para ligar a rede mesh, e que permite utilizar todas as aplicações da camada 3 OSI, de uma forma transparente optou-se por escolher o protocolo batman-adv como protocolo a utilizar.