Redes mesh e grafos

Hilton Garcia Fernandes

As redes sem fio do tipo mesh (a expressão em português "redes sem fio em malha" não tem sido usada no Brasil) [1] conectam entre si pontos de acesso (AP) [2] diretamente por rádio, evitando assim a necessidade de conexões cabeadas e ampliando a cobertura da rede sem fio para não apenas um AP, mas vários.

O conceito é muito amplo, mas normalmente é aplicado apenas a redes sem fio locais, as chamadas WLAN, principalmente do tipo Wi-Fi [3].

Os computadores clientes de um AP sem conexão direta à Internet podem obter essa conexão através de um outro AP que a possua, pelo processo chamado de hopping, ou pulo: o AP sem conexão com a Internet repassa os pacotes de informação para aquele que a possui. Depois, o AP conectado repassa os pacotes da resposta da Internet para aquele AP que sem conexão direta, que por sua vez, repassa ao cliente que solicitou a conexão.

As redes sem fio em malha podem ser estudadas de várias formas. Uma das mais interessantes, com certeza é a via dos grafos [4].

A teoria dos grafos é baseada em conceitos simples e poderosos. Um grafo pode ser simplesmente descrito como um conjunto de objetos que se conecta em pares. Os objetos são chamados vértices (ou nós) e as conexões entre eles são chamadas arestas.

Em termos das redes mesh, cada AP seria um nó e cada conexão entre eles seria uma aresta. Grafos que modelam redes mesh podem ser considerados não dirigidos, pois se há conexão de um primeiro AP para um segundo, com certeza há do segundo para o primeiro.

Grafos podem ser conexos, quando de um nó é possível chegar a qualquer outro, mesmo que seja necessário passar por mais de uma aresta. Grafos com o mínimo de arestas necessário para serem conexos são chamados árvores [5]. Em termos matemáticos, se n é o número de nós de uma árvore, o número de arestas dela será n - 1.

Ora, redes mesh têm como propriedade interessante a tolerância a falhas. Em outras palavras, isto significa que há vários caminhos entre um AP e outro. Por exemplo, entre um AP sem conexão com a Internet e outro conectado. Se um dos caminhos não for mais possível, haverá outra alternativa, eventualmente menos rápida, mas ainda assim capaz de permitir o acesso à Internet.

Por isso, uma rede mesh tem que ter mais do que o mínimo de conexões possível, para que haja redundância em pelo menos uma conexão. Ou seja: nestes termos, a rede mesh do grafo mencionado teria que ter pelo menos n arestas. Uma rede totalmente conectada [6] é uma rede com
n*(n - 1)/2
conexões, o que não é viável para redes maiores.

Outro ponto que favorece a qualidade de uma rede mesh é que a quantidade de conexões seja o melhor distribuída possível, sem que um único nó contenha todas conexões redundantes -- pois este nó será um ponto de falha da rede; se ele cair, cairá parte importante da rede. O número de conexões de um dado nó é chamado grau desse nó.

O programa descstat.g [7] calcula estatísticas básicas dos nós de um dado grafo -- uma das mais importantes é chamada coeficiente de variação [8], e mede a disparidade dos graus dos vértices de um grafo. Idealmente, o coeficiente de variação seria zero para uma rede onde todos nós tivessem o mesmo número de conexões.

O programa connect.g [9] avalia se um dado grafo é ou não conexo. No caso de redes mesh, identifica se todos pontos da rede se vêem ou não.

Tanto descstat.g [7] quanto connect.g [9] foram escritos usando-se o ambiente de programação gvpr, desenvolvido por Emden R. Gansner, disponível no pacote graphviz [10], um Software Livre poderoso, flexível e muito usado para visualização de grafos.

Referências

[1] Wireless mesh network

[2] Wireless access point

[3] Wi-Fi

[4] Teoria dos grafos

[5] Árvore (teoria dos grafos)

[6] Fully-connected network

[7] descstat.g

[8] Coeficiente de variação

[9] connect.g

[10] graphviz