DHT circular

Consideraremos agora organizar os pares em um círculo. Nessa disposição circular, cada par rastreia apenas seu sucessor imediato (módulo 2n ). Um exemplo desse círculo é exibido na Figura 2.27(a). Nesse exemplo, n é novamente 4 e há os mesmos oito pares do exemplo anterior. Cada par está ciente apenas de seu sucessor imediato; por exemplo, o par 5 sabe o endereço IP e o identificador do par 8, mas não sabe necessariamente nada sobre quaisquer outros pares no DHT. Essa disposição circular dos pares é um caso especial de uma rede sobreposta. Em uma rede sobreposta, os pares formam uma rede lógica abstrata que reside acima da rede de computadores “inferior” que consiste de enlaces físicos, roteadores e hospedeiros. Os enlaces em uma rede sobreposta não são físicos, mas enlaces virtuais entre duplas de pares. Na rede de sobreposição da Figura 2.27(a), há oito pares e oito enlaces sobrepostos; na sobreposição da Figura 2.27(b) há oito pares e 16 enlaces sobrepostos. Um único enlace de sobreposição normalmente usa muitas ligações físicas e roteadores físicos na rede inferior.

Usando a rede de sobreposição circular da Figura 2.27(a), suponha agora que o par 3 deseje determinar qual par no DHT é responsável pela chave 11 [para inserir ou para requisitar uma dupla (chave-valor)]. Usando a rede sobreposta circular, o par de origem (par 3) cria uma mensagem que pergunta “Quem é responsável pela chave 11?” e a envia a seu sucessor, o par 4. Sempre que um par recebe essa mensagem, como sabe o identificador de seu sucessor, pode determinar se é responsável (ou seja, mais próximo) pela chave em questão. Caso um par não seja responsável pela chave, ele simplesmente envia a mensagem a seu sucessor. Portanto, por exemplo, quando o par 4 recebe a mensagem perguntando sobre a chave 11, ele determina que não é responsável pela chave (porque seu sucessor está mais perto da dela), portanto, ele passa a mensagem a seu sucessor, ou seja, o par 5. Esse processo continua até que a mensagem chegue ao par 12, que determina que é o mais próximo da chave 11. A essa altura, o par 12 pode enviar uma mensagem de volta à origem, o par 3, indicando que é responsável pela chave 11.

O DHT circular oferece uma solução bastante elegante para reduzir a quantidade de informação sobreposta que cada par deve gerenciar. Em particular, cada par está ciente apenas de dois pares, seu sucessor imediato e seu predecessor imediato (por padrão, o par está ciente de seu predecessor, visto que este lhe envia mensagens). Porém, essa solução ainda introduz um novo problema. Embora cada par esteja ciente de dois pares vizinhos, para encontrar o nó responsável por uma chave (no pior das hipóteses), todos os N nós no DHT deverão encaminhar uma mensagem pelo círculo; N/2 mensagens são enviadas em média.

Assim, no projeto de um DHT, há uma troca entre o número de vizinhos que cada par tem de rastrear e o número de mensagens que o DHT precisa enviar para resolver uma única solicitação. Por um lado, se cada par rastrear todos os outros pares (sobreposições de malha), apenas uma mensagem será enviada por solicitação, mas cada par deverá rastrear N pares. Por outro lado, com um DHT circular, cada par está ciente apenas de dois pares, mas N/2 mensagens são enviadas em média para cada solicitação. Felizmente, podemos refinar nossos projetos de DHTs de forma que o número de vizinhos por par, bem como o número de mensagens por solicitação seja mantido em um tamanho aceitável. Um desses refinamentos é usar a rede sobreposta circular como fundação, mas adicionar “atalhos” de forma que cada par não apenas rastreie seu sucessor imediato, mas também um número relativamente pequeno de pares espalhados pelo círculo. Um exemplo desse DHT circular com alguns atalhos é demonstrado na Figura 2.27(b). Atalhos são usados para expedir o roteamento das mensagens de solicitação. Especificamente, quando um par recebe uma mensagem que solicita uma chave, ele encaminha a mensagem ao vizinho (vizinho sucessor ou um dos vizinhos via atalho) que está mais perto da chave. Assim, na Figura 2.27 (b), quando o par 4 recebe a mensagem solicitando a chave 11, ele determina que o par mais próximo (entre seus vizinhos) é seu vizinho no atalho 10 e então envia a mensagem diretamente ao par 10. Claramente, atalhos podem reduzir significativamente o número de mensagens usado para processar uma solicitação.

 A próxima questão natural é “Quantos vizinhos no atalho cada par deve ter, e quais pares devem ser esses vizinhos de atalho?” Essa pergunta recebeu atenção significativa da comunidade de pesquisa [Stoica, 2001; Rowstron, 2001; Ratnasamy, 2001; Zhao, 2004, Maymounkov, 2002; Garces-Erce, 2003]. De forma importante, demonstrou-se que o DHT pode ser projetado de forma que tanto o número de vizinhos como o número de mensagens por solicitação seja da ordem de log N, em que N é o número de pares. Esses projetos obtêm um compromisso satisfatório entre as soluções extremas de se usar topologias de sobreposição circular e de malha.

ATIVIDADE DE FIXAÇÃO