Optimized Link State Routing Daemon

OLSR é um protocolo do router para redes de dados sem fio móveis do tipo adhoc.

olsr significa em inglês Optimized Link State Routing Protocol.

Utilizando firmware específico para tal é possível criar uma rede olsr e colocar automaticamente endereços IP a computadores via dhcp para computadores portáteis/laptops que estão perto de um router como por exemplo o linksys wrt54g, sendo assim possível navegar pela internet usando a tecnologia WiFi. Para poder usar o dhcp, necessita-se reservar um bloco de números IP. Usando esta "configuração básica", não é necessário para um computador portátil ter o olsr instalado. O router linksys wrt54gl passa a funcionar como um gateway para o laptop/computador portátil e é responsável pela tradução do tráfego de dados que gera o computador portátil.

Rede Mesh com OLSR

A maioria das redes wireless funcionam em modo de infra-estrutura, ou seja, consiste de um ponto de acesso wireless em algum lugar (com um rádio funcionando em modo master), ligado a uma linha dsl ou algum outro tipo de rede cabeada de larga escala. Num hotspot deste tipo, o ponto de acesso wireless usualmente age como uma estação master, distribuindo o acesso internet aos seus clientes, que funcionam em modo cliente. Esta topologia é semelhante a um serviço celular GSM. Os telefones móveis ligam-se a uma estação base—sem a presença desta estação, os mesmos não podem comunicar entre si. Se pretender passar dados para o seu amigo sentado à sua frente numa mesa, o seu telemóvel envia os dados para uma estação base do seu operador, que pode estar a três quilómetros de distância, e este, então, envia os dados para o telefone do seu amigo.

Da mesma forma, placas wireless em modo cliente não se podem comunicar directamente. Clientes por exemplo, dois laptops numa mesma mesa precisam de usar um ponto de acesso wireless como um ponto de passagem (relay). Qualquer tráfego entre os clientes ligados a um ponto de acesso wireless tem que ser enviado duas vezes. Se o cliente A e o C se tentarem comunicar, o cliente A envia os dados para o ponto de acesso wireless B, e então o ponto de acesso wireless retransmitirá os dados para o cliente C. Uma simples transmissão pode ter a velocidade de 600 KByte/s (isto é aproximadamente a máxima velocidade que você alcança com um 802.11b) no nosso exemplo, como os dados tem que ser repetidos pelo ponto de acesso wireless para alcançar o alvo, a velocidade efectiva entre dois clientes será de apenas 300 KByte/s.

No modo adhoc não existe uma relação hierárquica master-cliente. Os nós podem comunicar entre si directamente, desde que estejam ao alcance dos seus interfaces wireless. Assim, neste exemplo, ambos os computadores poderiam atingir a velocidade plena de transmissão de dados trabalhando em modo adhoc, em circunstâncias ideais. A desvantagem do modo adhoc é que os clientes não repetem o tráfego destinado a outros clientes. No exemplo do ponto de acesso wireless, os dois clientes A e C podem não estar ao alcance um do outro, mas podem comunicar entre si desde que ambos estejam ao alcance do ponto de acesso wireless. Como padrão, nós adhoc não repetem dados, mas podem fazê-lo se aplicarmos roteamento. As redes mesh são baseadas na estratégia de que cada nó em modo mesh actua como um repetidor para estender a cobertura da rede wireless. Quanto mais nós, melhor a cobertura de rádio e maior o alcance da nuvem mesh.

Existe um ponto negativo considerável que mencionaremos agora. Caso o dispositivo utilize apenas um interface de rádio, a capacidade de largura de banda é significativamente reduzida a cada vez que o tráfego é repetido por nós intermediários no caminho entre A e B. Haverá também interferências na transmissão, uma vez que os nós partilham o mesmo canal. Assim, redes adhoc de baixo custo podem fornecer boa cobertura de rádio nos últimos quilómetros de uma rede wireless comunitária, ao custo de velocidade; especialmente se a densidade dos nós e a potência de transmissão for alta.

Se uma rede adhoc consiste de apenas alguns poucos nós que estão constantemente ligados, não se deslocam e tem sempre links estáveis de rádio ou seja, uma longa lista de "se"; então é possível configurar tabelas de roteamento para cada nó, manualmente. Infelizmente, essas condições raramente existem no mundo real. Os nós podem falhar; dispositivos com wireless circulam por todos os lados e a interferência pode afectar links de rádio a qualquer momento. E ninguém quer ficar a actualizar manualmente tabelas de roteamento a cada vez que um novo nó integra a rede.

Através do uso de protocolos de roteamento que, automaticamente, mantém tabelas de roteamento individuais em cada nó envolvido, podemos evitar estes problemas. Protocolos populares de roteamento do mundo por cabos (como o OSPF) não funcionam bem neste ambiente porque não são projectados para lidar com ligações intermitentes ou topologias que mudam rapidamente.

Roteamento mesh com olsrd

O Optimized Link State Routing Daemon (olsr) traduz-se por serviço de roteamento optimizado para estado de ligação é uma aplicação de roteamento desenvolvida para funcionar em redes wireless. É um projecto de código aberto com suporte a Mac OS X, Windows 98, windows 2000, XP, Vista, linux, FreeBSD, OpenBSD e NetBSD. olsrd está disponível para pontos de acesso que usam (ou podem usar) o linux, como a família dos linksys, asus, accesscube ou pocket pcs executando o familiar sistema operativo linux e sendo também padrão para os kits metrix executando o pyramid. O olsrd pode trabalhar com vários interfaces de rede e ser estendido através de plugins. Suporta o protocolo ipv6 e é activamente desenvolvido e usado em redes comunitárias em todo o mundo. Note que existem muitas implementações do Optimized Link State Routing, que começou como uma proposta para o IETF escrita no INRIA de França.

A implementação do olsrd começou como uma tese de mestrado de Andreas Toennesen na UniK University. Com base na experiência prática de redes comunitárias livres, o serviço de roteamento foi modificado. O olsrd difere, hoje, significativamente de seu projecto original, pois passou a incluir um mecanismo chamado Link Quality Extension (extensão de qualidade de linha) que mede a perda de pacotes entre os nós e calcula as rotas levando em conta esta informação. Esta extensão quebra a compatibilidade com os serviços de roteamento que seguem a especificação original do INRIA. O olsrd pode ser configurado para que se comporte de acordo com a especificação do IETF que não possui esta funcionalidade mas não há razão para desactivar o Link Quality Extension, a não ser que a compatibilidade com outras implementações seja necessária.

Teoria com OLSR

Depois que o olsrd está em execução por algum tempo, um nó sabe da existência de todos os outros nós da nuvem mesh e quais podem ser usados para rotear tráfego para eles. Cada nó mantém uma tabela de roteamento cobrindo toda a rede mesh. Este tratamento dado ao roteamento mesh é chamado de roteamento pro-activo (proactive routing). Por outro lado, algoritmos de roteamento reactivo (reactive routing) procuram rotas apenas quando é necessário o envio de dados para um nó específico. Há prós e contras para o roteamento pro-activo e existem muitas outras ideias sobre a forma de se implementar roteamento mesh que valeriam a pena mencionar.

A maior vantagem do roteamento proativo é que você sabe quais são os nós que compõem a rede, não precisando esperar que rotas sejam encontradas. Uma maior sobrecarga do protocolo e maior utilização de processamento são algumas das desvantagens. Em Berlim, a comunidade Freifunk administra uma nuvem mesh onde o olsrd tem que administrar mais de 100 interfaces. A média de carga de cpu, causada pelo olsrd de um linksys wrt54g, executado a 200 MHz, é de 30% na rede mesh de Berlim. Há claramente um limite na capacidade de escala de um protocolo pro-activo dependendo de quantos interfaces são utilizados e da frequência de actualização das tabelas de roteamento. A manutenção de rotas numa nuvem mesh estática dá menos trabalho do que numa onde os nós mudam constantemente de lugar, uma vez que, no primeiro caso, as tabelas de roteamento necessitam ser actualizadas com menor frequência.

Mecanismo OLSR

Um nó executando o olsrd está, constantemente, enviando mensagem de broadcast 'Hello' (Olá) em intervalos de tempo determinados, de forma que os vizinhos possam detectar sua presença. Cada nó faz a estatística de quantos 'Hellos' foram perdidos ou recebidos de cada vizinho obtendo, desta maneira, informações sobre a topologia e qualidade do link para os nós da vizinhança. A informação obtida sobre a topologia é transmitida como mensagens de controle de topologia (Topology Control, ou TC messages) e encaminhada pelos vizinhos que o olsrd escolheu para serem retransmissores multiponto. O conceito de retransmissores multiponto (multipoint relays) é uma ideia nova em roteamento pro-activo que surgiu com o projecto do olsr. Se cada nó retransmite a informação de topologia que recebeu, uma sobrecarga desnecessária é gerada. Tais transmissões são redundantes se um nó tem muitos vizinhos. Assim, um nó olsrd decide quais vizinhos, que são retransmissores multiponto favoráveis, irão encaminhar as mensagens de controle de topologia.

Note que os retransmissores multiponto são escolhidos para o propósito de encaminhamento de mensagens TC. A carga de trabalho é roteamento considerando todos os nós disponíveis. Há outros dois tipos de mensagens no olsr que anunciam informação; quando um nó oferece um gateway para outras redes (mensagens HNA) ou quando o mesmo possui vários interfaces (mensagens MID). Não existe muito a dizer sobre estas mensagens, a não ser que elas existem. Mensagens HNA tornam o olsrd bastante conveniente quando é feita a ligação com a internet através de um dispositivo móvel. Quando um nó mesh é movido de um lado a outro, ele irá detectar gateways para outras redes, escolhendo aquele para o qual existe a melhor rota. Entretanto, o olsrd não é infalível. Se um nó anuncia que é um gateway para a internet o que ele não é, seja porque nunca foi ou porque está desligado no momento os demais nós acreditarão nesta informação. Este pseudo-gateway é um buraco negro. Para contornar este problema, um plugin para gateway dinâmico foi escrito. Este plugin irá automaticamente detectar, no gateway, se ele está realmente ligado e se o link ainda está activo. Caso contrário, o olsrd suspende o envio de falsas mensagens HNA. É altamente recomendável instalar e utilizar este plugin, ao invés de activar estaticamente mensagens HNA.

Resultados práticos com OLSR

O olsrd implementa roteamento baseado em IP em uma aplicação no espaço do utilizador à instalação relativamente fácil. Pacotes de instalação estão disponíveis para OpenWRT, accesscube, Mac OS X, Debian GNU/linux e Windows. O olsr é componente padrão do Metrix Pyramid. Caso tenha que compilar a partir do código-fonte, primeiro leia a documentação que está presente na distribuição do programa. Caso tudo esteja configurado correctamente, o que você tem a fazer é executar o olsr.

Antes de mais nada, certifique-se de que cada nó tem um endereço IP único, designado de forma estática, para cada interface utilizada na rede mesh. Não é recomendado (e também não é prático) usar dhcp em uma rede mesh baseada em IP. Um pedido de dhcp não será respondido por um servidor dhcp se o solicitante precisar passar por vários hops para chegar até ele, e aplicar a retransmissão de dhcp através de uma rede mesh é virtualmente impraticável. Esta questão poderia ser resolvida com o uso de ipv6, uma vez que ele permite espaço suficiente para a geração de endereços IP únicos a partir do endereço mac de cada interface envolvida (como sugerido em "IPv6 Stateless Address Autoconfiguration in large mobile adhoc networks" de K. Weniger e M. Zitterbart, 2002).

Uma página wiki, onde cada pessoa interessada possa escolher um endereço ipv4 para cada interface onde o serviço olsr esteja a ser executado, pode servir muito bem a esse propósito. Não há maneira fácil de automatizar o processo se o IPv4 for utilizado. O endereço de broadcast deve ser 255.255.255.255 para as interfaces mesh em geral, como uma convenção. Não há razão para configurar o endereço de broadcast explicitamente, uma vez que o olsrd pode ser configurado para sobrescrever o endereço de broadcast por este convencionado. Deve-se certificar, apenas, que as configurações são as mesmas em todos os lugares. O olsrd pode encarregar-se disto. Quando um arquivo de configuração olsrd é preparado e distribuído, esta funcionalidade deve estar activa para evitar confusões do tipo "por que os outros nós não conseguem ver a minha máquina?!?". Agora vamos configurar o interface wireless. \

Aqui fica á um exemplo de comando de configuração de uma placa wireless com o nome wlan0 em ambiente linux:

iwconfig wlanO essid olsr.org mode ad-hoc channel 10 rts 250 frag 256

Verifique que a placa de rede wireless foi configurada de modo a permitir uma ligação adhoc para outros nós da mesh dentro do alcance directo (single hop). Certifique-se de que o interface se junta ao mesmo canal wireless, adhoc para outros nós da mesh dentro do alcance directo (single hop). Certifique-se de que o interface se junta ao mesmo canal wireless, use o mesmo nome de rede ESSID (Extended Service Set IDentifier) e tenha o mesmo Cell-ID que todos os outras placas de rede wireless usadas na construção da rede mesh. Muitas placas de rede wireless, ou seus respectivos drivers, não são compatíveis com o padrão 802.11 para redes adhoc e podem falhar miseravelmente na ligação com uma célula. Podem ser incapazes de se ligar a outros dispositivos na mesma tabela, mesmo que estejam configurados com o canal e nome de rede correctos. Podem até confundir outras placas de rede que se comportam de acordo com o padrão ao criar seu próprio Cell-ID no mesmo canal, como o mesmo nome de rede. Placas de rede WiFi feitos pela Intel que se encontram com os notebooks Centrino são notórias por este tipo de comportamento.

Você pode verificar isto com o comando iwconfig, quando usar o GNU/ linux. Aqui está o resultado numa máquina:

wlan0 IEEE 802.11b ESSID:"olsr.org" Mode:Ad-Hoc Frequency:2.457 GHz Cell: 02:00:81:1E:48:10 Bit Rate:2 Mb/s Sensitivity=1/3
Retry min limit:8 RTS thr=250 B Fragment thr=256 B Encryption key:off Power Management:off
Link Quality=1/70 Signal level=-92 dBm Noise level=-100 dBm Rx invalid nwid:0 Rx invalid crypt:28 Rx invalid frag:0 Tx excessive  
retries:98024 Invalid misc:117503 Missed beacon:0

É importante configurar o limite (threshold) do parâmetro Request to Send (RTS; solicitação para envio) para uma rede mesh. Existirão colisões no canal de rádio entre as transmissões de nós no mesmo canal wireless e o RTS atenuará isto. RTS/CTS adicionam um handshake antes da transmissão de cada pacote, garantindo que o canal está livre. Isto adiciona uma sobrecarga, mas aumenta o desempenho no caso de nós escondidos e nós escondidos são o padrão em uma rede mesh. Este parâmetro configura o limite do menor pacote (em bytes) para o qual o nó envia um RTS. O limite (threshold) RTS deve ser menor que o tamanho do pacote IP (IP Packet) e que o limite de fragmentação (fragmentation threshold) aqui configurado para 256; de outra forma, será desabilitado. O TCP é muito sensível a colisões, então é importante manter o RTS ligado.

A fragmentação permite a divisão de um pacote IP em fragmentos menores, transmitidos no meio de comunicação. Isto adiciona sobrecarga mas, num ambiente com muito ruído, acaba por diminuir a incidência de erros e permite que os pacotes atravessem picos de interferência. Redes mesh possuem bastante ruído pois todos os seus nós usam o mesmo canal e, por causa disto, as transmissões interferem umas com as outras. Este parâmetro (Fragment thr) configura o tamanho máximo que um pacote deve ter, antes de ser dividido e enviado em uma rajada (burst). Um valor igual ao tamanho máximo do pacote IP (IP packet size) desabilita o mecanismo de fragmentação, desta forma, Fragment thr deve ser menor que o IP packet size. A configuração do limite de fragmentação é recomendada.

Uma vez que um endereço IP válido e uma máscara de rede são atribuídos, e a interface wireless está ligada, o arquivo de configuração do olsrd deve ser alterado de maneira que o OLSRd encontre e use a interface na qual deve trabalhar. Para o Mac OS X e Windows existe um bom interface gráfico para a configuração e monitorização do serviço. Infelizmente, isto é uma tentação para utilizadores que não têm conhecimento suficiente façam coisas estúpida como anunciar buracos negros. EM [[[bsd] e no linux, o arquivo de configuração olsrd.conf precisa ser manipulado com um editor de textos.

Handshake traduz-se, literalmente, por "sacudida de mãos". É o tradicional cumprimento de apertar as mãos de alguém. Neste caso, é um "comportamento" do protocolo na transmissão de dados. Antes de enviar qualquer coisa, que deve ter o tamanho mínimo definido pelo threshold (no caso, 256 bytes), o lado que vai transmitir envia um sinal RTS, Request to Send, ou seja, pede permissão para enviar dados. Caso o canal esteja livre, ele receberá como resposta um sinal CTS, Clear to Send, ou "livre para enviar". Atendidas estas condições, a transmissão de dados inicia-se. O tradutor conseguiu executar o Radio Mobile nma distribuição linux Mint Elyssa (baseada no Ubuntu Hardy), usando o Wine versão 0.9.59 ou superior. Provavelmente, qualquer distribuição que aceite esta, ou qualquer outra versão mais recente do Wine, deve servir ao propósito. Os problemas com as legendas dos botões, descritos no texto, não foram sentidos.

Configuração olsrd.conf

Disponível em olsrd.conf.

Usando OLSR em Ethernet em vários interfaces

Não é necessário ter um interface wireless para testar ou usar o olsrd ainda que seja para isto que o olsrd tenha sido projectado. O olsr pode ser usado em qualquer placa de rede. Interfaces wireless não têm que funcionar sempre no modo adhoc para formar uma rede mesh quando um nó da mesh tem mais do que uma interface. Para links dedicados, pode ser uma boa opção tê-los executados em modo infra-estrutura. Muitas placas de rede wireless e os seus drivers apresentam problemas em modo adhoc, mas funcionam bem no modo de infra-estrutura porque todos esperam que ao menos isto funcione bem. O modo adhoc ainda não tem muitos utilizadores, assim, a implementação do mesmo foi feita de forma descuidada por muitos fabricantes. Com o aumento da popularidade de redes mesh, a situação dos drivers está melhorando hoje.

Plugins OLSR

Uma boa quantidade de plugins está disponível na página oficial do [OLSR]]d. Para uma lista completa deles. Aqui apresentamos apenas um pequeno tutorial para o plugin de visualização de topologia de rede olsrd_dot_draw. Com frequência, é muito bom para o entendimento de uma rede mesh ter a capacidade de exibir a topologia da rede de forma gráfica. O plugin olsrd_dot_draw gera a topologia da rede em formato de pontos na porta TCP 2004. As ferramentas graphviz podem então ser usadas para desenhar os gráficos.

Instalando o plugin OLSR dot_draw

Compile os plugins olsr separadamente e instale-os. Para carregar o plugin adicione as seguintes linhas ao olsrd.conf. O parâmetro "accept" especifica qual host é aceite para ver a informação de topologia (actualmente, apenas um) e, por padrão, é "localhost" (o computador local). O parâmetro "port" especifica a porta TCP. Feito isto, reinicie o olsr e verifique se você obtém uma saída na porta TCP 2004.

telnet localhost 2004

Após algum tempo, deve começar a ver alguma saída de texto e pode salvar/gravar a saída das descrições gráficas e executar as ferramentas dot ou neato do pacote graphviz para obter as imagens. Bruno Randolf escreveu um pequeno script em perl, que obtém continuamente a informação de topologia do olsrd e a exibe graficamente, utilizando as ferramentas graphviz e imagemagick.

Instale os seguintes pacotes no seu computador:

• Graphviz
• ImageMagick
• Olsr topology view

Para instalar este software na sua distribuição linux veja como instalar software em Linux

Você pode, agora, executar o script com ./olsr-topology-view.pl e verificar a actualização da topologia praticamente em tempo real.

Diagnóstico de problemas com OLSR

Desde que as placas wireless se possam "ver" directamente uma à outra através dos seus rádios; executar um "ping" irá funcionar, quer o olsrd esteja sendo executado ou não. Isto funciona porque a grande máscara de rede (255.255.255.255) faz de cada nó um link local, colocando de lado questões de roteamento no nível do primeiro "hop" (local). Esta é a primeira coisa a ser verificada se algo parece não estar de acordo com o esperado. A maior parte das dores de cabeça que as pessoas têm com wireless em modo adhoc são causadas pelo facto de que o modo adhoc em placas de rede e drivers é implementado de forma descuidada. Se não for possível "pingar" os nós directamente quando eles estão ao alcance um do outro, é mais provável que exista um problema na placa de rede ou driver, ou as configurações da sua rede estão erradas. Se as máquinas se conseguem "pingar" uma a outra, mas o olsrd não encontra as rotas, então os endereços IP, máscaras de rede e endereço de broadcast devem ser verificados. Finalmente, você está executando uma firewall? Verifique se você não está bloqueando a porta udp 698.

Links externos

• Página Oficial (em Inglês)
• Optimized Link State Routing Protocol (em Inglês)
• OLSR-NG (em Inglês)
• HIPERCOM (em Inglês)
• Configuração de um serviço olsrd.conf no Fórum_da_Comunidade

Editor

--Cmsv 15h38min de 30 de novembro de 2009 (GMT)