log(n) sucessores, onde "n" é o tamanho da rede em número de nodos ativos (i.e., nodos que ainda não saíram da rede);floor(log_2(n)) sucessores no sentido horário;(id+2^i)mod 2^m iniciando com i=0, onde m é o número de bits para armazenar a maior chave.
Por exemplo, a figura abaixo exemplifica uma DHT válida, onde, o nodo id=10 possui a seguinte tabela de rotas com 3 entradas {14,20,29}, pois como o tamanho da DHT é n=9, então floor(log_2(9))=3. Álem disso o maior identificador é 52, então precisamos de m=6. A tabela é calculada a seguir:
| i | id+2^i | succ |
|---|---|---|
| 0 | 11 | P14 |
| 1 | 12 | P14 |
| 2 | 14 | P14 |
| 3 | 18 | P20 |
| 4 | 26 | P29 |
Outros exemplos podem ser vistos aqui:
- http://wwarodomfr.blogspot.com.br/2008/09/chord-routing.html
- https://www.cs.cmu.edu/~dga/15-744/S07/lectures/16-dht.pdf
Armazenamento de chaves
O armazenamento segue os seguintes critérios:
- Em nossa DHT, os nodos armazenam e gerenciam apenas chaves;
- Os nodos armazenam as chaves "K" mais próximas de seus identificadores "P" obedecendo o seguinte critério:
P-1 < K <=P. No exemplo, o nodoid=1armazena qualquer chave com k={53, ..., 1}, o nodoid=10armazena qualquer chave com k={2, ..., 10}, e assim por diante; - A saída de um nodo acarreta transferir suas respectivas chaves para seu nodo sucessor com identificador mais próximo. Por ex., caso o nodo
id=10decida sair da rede, suas chaves são transferidos para o nodoid=14. Neste caso o nodoid=14armazenaria qualquer chave com k={2, ..., 14}; - As operações permitidas, são: lookup de chave (L), e inclusão de chaves (I);
- A operação lookup obedece o seguinte critério: quando um nodo "P" faz o lookup de uma chave "K", ele deve enviar a requisição de lookup para o nodo P+1 em sua tabela de rotas que tiver o identificador mais proximo da chave. O nodo P+1 faz o mesmo até descobrir o identificador do nodo que armazena a chave; No exemplo, considere que o nodo
id=10com tabela de rotas {14,20,29} faz um lookup pela chave "50". O nodoid=10deve enviar o pedido ao nodo com identificador mais próximo da chave, ou seja, o nodoid=29e assim por diante. De acordo com a figura acima, o lookup pela chave "50" passaria pela rota {29,45,52}; - Não existe replicação de dados e não existe exclusão de chaves;
Entrada:
A entrada deve ser feita pela entrada padrão (stdin). O arquivo é formado por uma sequência de linhas, onde cada linha representa uma operação chegando. Cada linha tem até 4 campos: o primeiro campo é o tempo em que a operação foi realizada (timestamp). O segundo é a operação que será realizada. O terceiro campo é o identificador do nodo que realiza a operação. O quarto camplo é a chave de armazenamento (somente para operações I, e L). A ordem das operações é feita pelo timestamp, pois representa a DHT funcionando ao longo do tempo.
Saída:
A saída deve ser feita pela saída padrão (stdout). A escrita na saída deve acontecer toda vez que for lida uma operação lookup (X L X X). O arquivo será composto por uma sequência de linhas. Uma linha para cada escalonamento. Cada linha tem 4 campos separados por espaço (um único espaço entre cada par de campos). O primeiro campo é o timestamp da operação. O segundo campo é a operação a ser identificada: lookup (L) ou tabela de rotas (T) . O terceiro campo pode ser a chave de lookup (para operação L) ou o identificador do nodo (para operação T). E o quarto campo é a rota realizada pela operação lookup (para operação L) ou tabela de rota (para operação T). A saida será ordenada pela sequencia de campos.
IMPORTANTE: após a operação L (que ira imprimir a rota do lookup), a sequencia de saidas T imprime todos os nodos ativos e suas fingers para mostrar o estado da rede. Por exemplo, apos a saida "7 L 18 {14,20}" temos 3 saidas T, sendo uma para cada nodo ativo.
Exemplo de arquivos com uma entrada e uma saída válida:
| Entrada | Saída |
|
1 E 4 -
2 E 10 -
3 I 10 18
4 E 20 -
5 E 14 -
6 S 4 -
7 L 10 18
8 E 1 -
9 E 56 -
10 I 1 50
11 S 56 -
12 E 52 -
13 L 10 50
|
7 L 18 {14,20}
7 T 10 {14}
7 T 14 {20}
7 T 20 {10}
13 L 50 {20,52}
13 T 1 {10,20}
13 T 10 {14,20}
13 T 14 {20,52}
13 T 20 {52,14}
13 T 52 {1,10}
|
Requisitos mínimos:
O trabalho deve ser implementado de forma que possa ser compilado e executado nas servidoras de computação do Departamento de Informática.
O nome do executável deve ser mydht.
Não deve ter nenhuma opção de linha comando.
O que deve ser entregue:
Além dos arquivos fonte, deve acompanhar um makefile e um relatório com no máximo 2 páginas contendo a documentação sintetizada do sistema implementado. Qualquer particularidade deve estar descrita neste texto, como: algoritmo de detecção de ciclo em grafo.
Para compilar será usado o comando make (sem nenhum parâmetro), portanto preparem o Makefile para fazer isso mesmo que o programa seja implementado em linguagens interpretadas (e.g., Java).
Para testar será executado um script como o abaixo.