(id+2^i)mod 2^m iniciando com i=0, onde m é o número de bits para armazenar a maior chave.
Figura retirada do artigo original [1]
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=0armazena qualquer chave com k={4, ..., 0}, ja o nodoid=3armazena as chaves com k={2, 3}, 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=0decida sair da rede, suas chaves são transferidos para o nodoid=1. Neste caso o nodoid=1armazenaria qualquer chave com k={4,..., 1}; - 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=3com os seguintes sucessores {0,0,0} faz um lookup pela chave "1". O nodoid=3deve enviar o pedido ao nodo com identificador mais próximo da chave, ou seja, o nodoid=0que faz o mesmo até que a chave seja encontrada. De acordo com a figura acima, o lookup pela chave "1" passaria pela rota {0,1}; - 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.
$ ./mydht < teste.in > teste.out $ diff teste.sol teste.outOnde
teste.in é o arquivo de entrada do teste e teste.sol é o esperado como saída.Caso o teste seja positivo (não imprime nada) será analisado o código fonte e o relatório.
Os fontes também devem ser comentados para uma possível análise (e.g., Javadoc).
Forma de entrega:
O trabalho deve ser empacotado em um arquivo login.tar.gz, onde "login" é uma string com o login do aluno nas servidoras do DInf. Ao descompactar este arquivo deverá ser criado um diretório de nome "login" que conterá todos os demais arquivos. O make e o script acima deverão funcionar dentro deste diretório (não em subdiretórios).
Este arquivo deve ser enviado por e-mail ao endereço do professor com o assunto "CI701-trab2 " (exatamente). IMPORTANTE: Minha caixa de email usa o assunto do email como filtro.
Equipe:
O trabalho é individual.