Anonimato - FreeNet

A velocidade em uma rede Freenet é altamente dependente da distância entre o nó do usuário e o nó contendo o arquivo desejado. Como não existe um sistema centralizado, operações como buscas precisam ser capazes de encontrar sozinhos caminhos eficientes e curtos através da rede. Adiciona-se ao problema a necessidade da transferência e armazenamento dos dados em todos os nós intermediários, que não só aumentam o atraso como o consumo do espaço útil da rede proporcionalmente ao tamanho do caminho.

Busca-se então construir uma rede que minimiza a distância média entre quaisquer dois nós. Os algoritmos para realizar essa tarefa estão descritos a seguir.

O primeiro modelo mais simples que busca construir uma rede com propriedades de pequeno mundo foi proposta por Dundan J. Watts e Steven Strogatz em 1998.

Procedimento:

1) Posiciona-se cada um dos N nós em um anel;

2) Liga-se cada nó com os K acima e K abaixo, K é um inteiro par.

Anel com N = 10 e K = 2

3) Substitui-se cada ligação segundo uma probabilidade β e para um nó escolhido com probabilidade uniforme, e evitando laços e ligações repetidas.

Rede mundo pequeno com N = 10, K = 2 e β > 0

O procedimento 2 garante a formação de fortes agrupamentos locais, onde todos os nós são vizinhos imediatos ou próximos. Quanto maior o K, maior o número de vizinhos cada nó possui e maior os agrupamentos locais.

O procedimento 3 cria vínculos entre esses agrupamentos, reduzindo drasticamente os caminho médios. O β define o número de vínculos, de modo que β = 1 a rede se torna aleatória, e β = 0 uma estrutura em anel sem atalhos.

Rede aleatória ou β = 1

A maior restrição do modelo para o uso desejado no entanto é que ela considera a quantidade de nós N fixa, dificultando a expansão da rede.

O modelo de Kleinberg é fundamentalmente similar ao de Watts-Strogatz com agrupamentos locais e adição de forma probabilística de atalhos para agrupamentos distantes. Nesse modelo no entanto, a probabilidade de um atalho ocorrer entre dois nós em uma grade de k dimensões e n nós é dada por:

Nessa fórmula a distância d se refere à distância de Manhattan, ou seja, a distância entre dois nós é a soma do módulo da diferença entre os dois pontos em cada dimensão.

Essa rede tem a propriedade de um algoritmo guloso que busca sempre minimizar a distância entre nós. Desta forma, uma busca entre nós precisará de O(log²(n)) saltos.

Exemplo de rede de Kleinberg e uma busca gulosa partindo do nó vermelho até o azul

O problema dessa rede em aplicações distribuídas como a Freenet no entanto é que o nó não necessariamente conhece a sua posição na grade ou a de seus vizinhos, impossibilitando essa forma de roteamento.

A solução criada por Oskar Sandberg para descobrir caminhos parte do pressuposto que a rede segue o modelo de Kleinberg em que a probabilidade da formação de uma ligação entre dois nós é inversamente proporcional a distância entre os dois nós. Em outras palavras, ligações entre nós próximos são muito mais prováveis que entre nós distantes.

O cálculo para se achar estatisticamente a configuração mais provável usando a máxima verossimilhança foi provado não ser capaz de ser computado em tempo polinomial, de forma ser impossível se determinar qualquer rede suficientemente grande.

A solução alternativa proposta por Sandberg usa a distribuição da probabilidade da posição do nó a partir de suas ligações e um algoritmo do tipo Markov Chain Monte-Carlo chamado Metropolis-Hastings para reconstruir as distâncias entre os nós da rede. Esse algoritmo partindo de um nó qualquer consegue convergir para a distribuição das posições da rede.

próximo