Tabela de encaminhamento dinâmico (Dynamic Routing Table - DRT)

O DRT é um novo conceito utilizado na tecnologia de enxame para manter conexões ponto-a-ponto (P2P). Nesta abordagem, os membros do grupo estabelecem um gráfico de nós, cada um identificado por um hash único, e estes nós devem estar interligados.

Por conseguinte, necessitamos de um quadro estrutural que cumpra os seguintes objetivos

1. Maximiza o número de nós ligados em qualquer altura.

2. Minimiza os tempos de transmissão de mensagens.

3. Reduz o número de ligações entre pares.

4. Requer recursos computacionais mínimos.

Foram propostas várias soluções para atingir estes objetivos:

1. Cada nó está ligado ao nó seguinte, o que resulta em apenas ‘N’ ligações. No entanto, esta abordagem não é eficiente para a transmissão de mensagens, uma vez que a mensagem tem de atravessar todos os pares um a um.

2. Cada nó está ligado a todos os outros nós, o que resulta em ligações ‘N x N’. Esta configuração é eficaz para a transmissão de mensagens, mas exige mais recursos. Esta opção será selecionada para a primeira versão.

3. Uma solução alternativa é apresentada no artigo intitulado [Maximizing the Coverage of Roadmap Graph for Optimal Motion Planning](https://www.hindawi.com/journals/complexity/2018/9104720/), que oferece uma cobertura ideal de planejamento de movimento, mas exige cálculos computacionais significativos.

4. Utilizar o algoritmo DHT (Distributed Hash Table) para a tabela de encaminhamento, que aborda efetivamente os quatro pontos e já é utilizado pelo Jami na sua implementação UDP.

Além disso, para otimizar o número de soquetes, um soquete será alocado por um ConnectionManager para permitir a multiplexação de soquetes com um hash específico. Isso significa que, se houver necessidade de transmitir vários arquivos e participar de um bate-papo com alguém, apenas um soquete será utilizado.

Definições

Anotações:

• n: identificador do nó

• N: número de nós na rede

• b: parâmetro de configuração

Termos e conceitos:

• Mobile node / nó móvel: alguns dispositivos na rede podem estabelecer uma conetividade dinâmica, permitindo-lhes ligar-se e desligar-se rapidamente para otimizar a utilização da bateria. Em vez de manter um socket ponto-a-ponto dedicado com estes dispositivos, o protocolo opta por utilizar sockets existentes, se disponíveis, ou baseia-se em notificações push para transmitir informações. Esses nós são marcados com um sinalizador dedicado no protocolo.

• Bucket: esta classe é utilizada para manipular e armazenar ligações e para gerir o estado dos nós (em ligação, conhecidos, móveis). Os nós conhecidos são utilizados quando a ligação com um nó fica offline.

• Routing table / tabela de encaminhamento: ele é empregado para organizar os compartimentos, permitindo a busca dos nós mais próximos e estabelecendo o vínculo entre o gerenciador de enxames e a DRT (tabela de roteamento distribuído).

• Swarm manager / gestor de enchames: este componente é responsável pela gestão da lógica interna e pelo controlo da distribuição das ligações na rede.

• Swarm protocol / protocolo enxame: é utilizado para o intercâmbio de dados entre pares. Podem ser trocados os seguintes tipos de dados:

  • Pedido (por exemplo, FIND): Query | num | nodeId

  • Resposta (por exemplo, FOUND): Query | nodes | mobileNodes

  • Mensagem: Version | isMobile | Request or Response

Comparação de algoritmos

Chord

Numa rede Chord, cada nó está associado a uma chave única calculada utilizando as funções de hash SHA-1 ou MD5. Os nós estão organizados num anel por ordem crescente, e cada nó mantém uma tabela de encaminhamento que armazena informações sobre os nós mais próximos. Cada entrada i na tabela de encaminhamento contém nós com chaves tais que \(hash = (n + 2i - 1) mod 2^m\), onde m representa o número de bits na chave.

Cada nó tem conhecimento dos seus sucessores e predecessores na rede Chord.

Para recuperar dados, um nó envia um pedido ao seu sucessor imediato. Se o nó possuir a chave necessária, responde; caso contrário, reencaminha o pedido para o seu próprio sucessor.

Ao adicionar um novo nó à rede, o nó transmite mensagens aos outros nós para atualizar as suas tabelas de encaminhamento e garantir uma integração adequada.

Se um nó ficar offline, deve atualizar a sua tabela de encaminhamento para reencaminhar o tráfego através de outros nós disponíveis.

A distância entre dois nós é: \(d(n1,n2,) = (n1-n2) mod 2b`\)

O tamanho da tabela de encaminhamento é: \(log{N}\)

O número de saltos para obter um valor é: \(log{N}\)

Fontes: (Stoica, Morris, Karger, Kaashoek & Balakrishnan, 2001). (Liben-Nowell, Balakrishnan & Karger, 2002).

Pastry

Numa rede Pastry, cada nó está associado a um identificador de 128 bits gerado a partir de uma função de hashing. O Pastry é normalmente usado com endereços IP, e os nós são organizados num anel com ordem crescente. A tabela de encaminhamento é dividida em segmentos, tipicamente determinados por \(128 / 2b\), onde \(b\) é tipicamente definido como 4, e os endereços IP são colocados dentro destes segmentos.

Quando uma mensagem tem de ser transmitida a um nó folha, é enviada diretamente para o destinatário pretendido. Se a mensagem não se destinar a um nó folha, a rede tenta localizar o nó mais próximo e reencaminha os dados para esse nó para posterior transmissão.

A distância é: \(d(n1,n2,) = (prefix(n1) - prefix(n2)) mod 2b\)

Tamanho da tabela de encaminhamento: \((2b - 1)log{_2}{N}\)

Número de saltos para obter um valor: \(log{_2}{N}\)

onde b é geralmente 2.

Fontes: Tirée de Castro, Druschel, Hu, Rowstron (2002, p.3)21

Kademlia

Este algoritmo é utilizado pelo BitTorrent e pelo Ethereum. Neste esquema, é atribuído a cada nó um identificador de 160 bits e os nós podem ser organizados num anel por ordem crescente. Os dados são armazenados nos nós mais próximos. No entanto, a tabela de encaminhamento emprega uma estrutura de árvore binária com k-buckets (onde k representa o número de nós em cada bucket) para armazenar informações sobre os nós mais próximos.

Quando um nó se liga à DHT (Distributed Hash Table), tenta preencher a tabela de encaminhamento, inserindo os nós descobertos nos buckets apropriados. Se um bucket ficar cheio, um nó pode ser ignorado se estiver demasiado distante; no entanto, se o bucket representar o mais próximo disponível, será dividido em dois para acomodar o novo nó. Quando um novo nó é adicionado, a sua tabela de encaminhamento é consultada para obter informações sobre os nós mais próximos.

Para obter um valor específico, um nó envia um pedido ao nó mais próximo com o hash correspondente.

A distância é \(d(n1, n2,) = n1 XOR n2\)

Tamanho da tabela de encaminhamento: \(K \times log{_2}{N}\)

Número de saltos: \(log{_2}{N}\)

onde b é geralmente 1.

Implementação

Ao iniciar o Jami, cada conversa inicia a criação de sua tabela de roteamento. A etapa inicial é estabelecer contato com um primeiro nó para iniciar a sincronização com outros nós. Esse processo é conhecido como “bootstrapping” e consiste em duas partes principais.

A primeira parte envolve a recuperação de todos os dispositivos conhecidos numa conversa. Isto é conseguido através da verificação de certificados conhecidos no repositório ou da verificação da presença de determinados membros na DHT (Distributed Hash Table). Se já existir uma ligação TCP com qualquer dispositivo na conversação, esta será utilizada. Além disso, os nós conhecidos são injetados na tabela de encaminhamento. Se nenhuma ligação for bem sucedida, tentaremos encontrar novos dispositivos efetuando um pedido “GET” na DHT para obter dispositivos para cada membro.

A tabela de encaminhamento é posteriormente atualizada sempre que ocorre um evento num nó.

Durante as atualizações da tabela de encaminhamento, o componente tentará estabelecer ligações com novos nós, se necessário. A decisão de estabelecer ligação a novos nós é determinada pelas seguintes condições: - Para o bucket mais próximo, uma tentativa de conexão é feita se \((maxSize(Bucket) - connected nodes - connecting nodes) > 0\). - Para os outros buckets, uma conexão é iniciada se \((maxSize(Bucket) - connecting nodes) > 0\).

A distinção está no fato de que, no caso do compartimento mais próximo, o objetivo é tentar dividir os compartimentos, se necessário, enquanto compensa as desconexões em outros compartimentos. Isso é essencial para manter o conhecimento dos nós mais próximos.

Após a ligação a um novo nó, é enviado um pedido “FIND” para descobrir novos identificadores nas proximidades e identificar todos os nós móveis. Posteriormente, é enviado um pedido “FIND” de dez em dez minutos para manter a tabela de encaminhamento atualizada.

A classe principal responsável por este processo na base de código é o SwarmManager, e a fase de arranque é tratada na secção de conversação.

Arquitetura

Análise de desempenho

Ferramentas

Para validar a implementação e o desempenho do componente DRT, desenvolvemos várias ferramentas localizadas em daemon/tests/unitTest/swarm, including swarm_spread, bootstrap, entre outras.

Para interpretar os resultados, utilizamos as seguintes ferramentas:

• gcov para a análise da cobertura dos testes.

• ASan para verificar se há fugas de memória e transbordamentos de heap.

• gdb para depuração de estruturas internas.

Embora o foco principal seja nos testes unitários, para a análise de desempenho, contamos com o swarm_spread para avaliar vários aspetos, incluindo:

• O número de saltos necessários para a transmissão da mensagem.

• O número de mensagens recebidas por nó.

• Determinação das mensagens máximas e mínimas recebidas por cada nó.

• Cálculo das iterações necessárias para transmitir uma mensagem a todos os nós.

• Medição dos tempos de receção de mensagens.

Resultados

Trabalho futuro

1. Limite de tamanho de bucket dinâmico para obter um tamanho de bucket diferente consoante o tamanho da tabela de encaminhamento

2. Declinação de algumas ligações para acelerar um pouco a transmissão