Redes estruturadas
Pares
e
recursos
são
organizados seguindo algoritmos e critérios
específicos.
Possuem protocolos que garantem que qualquer nó possa encaminhar
uma
busca a outro nó que tenha o arquivo desejado. Esse protocolo
normalmente é um DHT (Distributed
Hash
Tables) , que atribui a posse de cada arquivo a um
par. O DHT também é usado para indexar os arquivos
e buscas.
DHT
São uma classe de sistemas distribuídos descentralizados que provém um serviço de busca parecida com a de uma tabela de hash: pares (key,value) são armazenados no DHT e qualquer nó pode recuperar o valor associado a cada chave. A responsabilidade por manter o mapa das chaves até os valores é distribuída entre os nós de modo que uma mudança no grupo de nós cause uma interrupção mínima. Isso permite que o DHT funcione para uma grande escala de nós com estes chegando, saindo e falhando continuamente.
Ele foi criado para reunir as vantagens dos sistemas de buscas do Napster e da Gnutella. No Napster, ao entrar na rede, cada nó enviava ao servidor central uma lista dos arquivos que possuia. O servidor, então se encarregava de fazer as buscas no seu banco de dados. Era muito eficiente, mas tornava o Napster vulnerável à ataques judiciais, pois permitia provar que a rede guardava e direcionava arquivos ilegais. A Gnutella usava um modelo de inundação no qual, quando a busca era feita, todas as máquinas conectadas à rede recebiam uma mensagem solicitando o determinado arquivo. Esse método era muito menos eficiente, pois tornava a comunicação lenta. Era preciso criar um sistema que tivesse a mesma eficiência do Napster, mas que fosse descentralizado. Um problema do DHT é que ele só realiza buscas pelo nome exato do arquivo ao invés de usar palavras-chave.
Estrutura do DHT:
Existe um keyspace abstrato, que corresponde a um conjunto de strings de 128 ou 160 bits. Um esquema de partição do keyspace divide a posse deste entre os nós participantes.Uma rede sobreposta conecta os nós, permitindo que qualquer um possa encontrar o dono de uma certa chave. Para armazenar um arquivo no DHT, faz-se o hash do nome do arquivo, produzindo uma chave k de 128 ou 160 bits. Uma mensagem put(k,data) é enviada de nó em nó pela rede sobreposta até chegar ao nó ao qual foi delegada a posse da chave k na partição do keyspace. Esse nó guarda a chave e os dados. Para buscar o arquivo, basta fazer o hash do nome do arquivo para gerar a chave k e a mensagem get(k). Essa mensagem também é enviada de nó em nó até chegar naquele que possui k, que responderá enviando os dados.
Os DHTs usam um variante de hashing consistente (no qual uma pequena alteração no nome não altera significativamente o hash) que utiliza uma função f(k1, k2) que define uma distância abstrata entre k1 e k2, que não tem a ver com a distância geográfica nem com o tempo de latência. Cada nó recebe um identificador (ID). Se um nó recebe um ID x, ele recebe todas as chaves km para as quais x é o ID mais próximo (por exemplo, o Chord, um dos protocolos DHT mais usados, usa um círculo no sentido horário), que é calculado por f(km,x).
A escolha de quem possuirá k varia, mas todos tem um princípio básico: será escolhido um nó que tenha k em seu ID ou que tenha ligação com um nó que tenha o ID mais parecido com k. è utilizado, então, um algoritmo para encontrar esse nó. Esse tipo de roteamento é chamado key-based routing.
DHT
São uma classe de sistemas distribuídos descentralizados que provém um serviço de busca parecida com a de uma tabela de hash: pares (key,value) são armazenados no DHT e qualquer nó pode recuperar o valor associado a cada chave. A responsabilidade por manter o mapa das chaves até os valores é distribuída entre os nós de modo que uma mudança no grupo de nós cause uma interrupção mínima. Isso permite que o DHT funcione para uma grande escala de nós com estes chegando, saindo e falhando continuamente.
Ele foi criado para reunir as vantagens dos sistemas de buscas do Napster e da Gnutella. No Napster, ao entrar na rede, cada nó enviava ao servidor central uma lista dos arquivos que possuia. O servidor, então se encarregava de fazer as buscas no seu banco de dados. Era muito eficiente, mas tornava o Napster vulnerável à ataques judiciais, pois permitia provar que a rede guardava e direcionava arquivos ilegais. A Gnutella usava um modelo de inundação no qual, quando a busca era feita, todas as máquinas conectadas à rede recebiam uma mensagem solicitando o determinado arquivo. Esse método era muito menos eficiente, pois tornava a comunicação lenta. Era preciso criar um sistema que tivesse a mesma eficiência do Napster, mas que fosse descentralizado. Um problema do DHT é que ele só realiza buscas pelo nome exato do arquivo ao invés de usar palavras-chave.
Estrutura do DHT:
Existe um keyspace abstrato, que corresponde a um conjunto de strings de 128 ou 160 bits. Um esquema de partição do keyspace divide a posse deste entre os nós participantes.Uma rede sobreposta conecta os nós, permitindo que qualquer um possa encontrar o dono de uma certa chave. Para armazenar um arquivo no DHT, faz-se o hash do nome do arquivo, produzindo uma chave k de 128 ou 160 bits. Uma mensagem put(k,data) é enviada de nó em nó pela rede sobreposta até chegar ao nó ao qual foi delegada a posse da chave k na partição do keyspace. Esse nó guarda a chave e os dados. Para buscar o arquivo, basta fazer o hash do nome do arquivo para gerar a chave k e a mensagem get(k). Essa mensagem também é enviada de nó em nó até chegar naquele que possui k, que responderá enviando os dados.
Os DHTs usam um variante de hashing consistente (no qual uma pequena alteração no nome não altera significativamente o hash) que utiliza uma função f(k1, k2) que define uma distância abstrata entre k1 e k2, que não tem a ver com a distância geográfica nem com o tempo de latência. Cada nó recebe um identificador (ID). Se um nó recebe um ID x, ele recebe todas as chaves km para as quais x é o ID mais próximo (por exemplo, o Chord, um dos protocolos DHT mais usados, usa um círculo no sentido horário), que é calculado por f(km,x).
A escolha de quem possuirá k varia, mas todos tem um princípio básico: será escolhido um nó que tenha k em seu ID ou que tenha ligação com um nó que tenha o ID mais parecido com k. è utilizado, então, um algoritmo para encontrar esse nó. Esse tipo de roteamento é chamado key-based routing.
