4. Otimização
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.
4.1 Watts-Strogatz
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.
4.2 Kleinberg
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.
4.3 Solução Distribuída
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.