Algoritmo

L'algoritmo implementato si ispira a quello descritto in draft-bryan-sipping-p2p-02, che a sua volta si basa sul protocollo Chord con SIP come protocollo di trasporto dei messaggi. Visto che la versione corrente dell'Internet Draft non e' pensata per un utilizzo reale (spiegarne i motivi sarebbe troppo lungo; chi e' veramente interessato puo' chiedere alla comunita' P2P SIP community), questo algoritmo prova a risolvere alcuni problemi aperti in modo nuovo.

Finger Table

I nodi SIPDHT mantengono una finger table che e' abbastanza diversa da quella dei nodi Chord. Le principali differenze sono:

la numerazione dei finger parte da 0 invece che da 1. E' piu' che altro una convenzione arbitraria, piu' vicina alla programmazione C;
ogni nodo e' autorativo dell'intervallo [ID_pred,ID), dove ID e' l'identificativo del nodo e ID_pred e' quello del suo predecessore (i.e. un nodo non e' autoritativo sul proprio identificativo ma lo e' sull'identificativo del proprio predecessore);
l'URL della i^esima posizione identifica il nodo (conosciuto) che occupa la posizione nell'anello piu' vicina all'inizio dell'intervallo. Algrebricamente parlando, e' il nodo per il quale la seguente funzione ritorna il valore piu' piccolo:
d(x) = |ID + 2ⁱ - ID_x|_{MOD 2^N},
dove ID e' l'identificativo locale, ID_x quello del nodo x e N il numero dei fingers (i.e. il numero di bit dei valori ritornati dalla funzione di hash).

Ricerca

Dato che la tabella di finger di SIPDHT e' diversa da quella di Chord anche l'algoritmo di ricerca e' stato rivisto. Il concetto e' comunque lo stesso:

search(KEY) if KEY in [ID_pred, ID) then local_search(KEY) for i in [0, N - 1) if KEY in [ID, ID + 2ⁱ) then forward_request(finger_i) forward_request(finger_{N - 1})

Mantenimento

Il vantaggio maggiore rispetto a Chord che e' derivato da questi cambiamenti e' la riduzione dei messaggi scambiati per mantere aggiornata la finger table. Infatti, mentre i nodi Chord devono effettuare una query per ogni entry della tabella a ogni stabilizzazione, i nodi SIPDHT possono popolarla usando solo le informazioni ricevute dal loro successore.

Le informazioni significative per riempire la finger table sono le URL dei nodi attivi, inserite nella entry che meglio gli si addice (se esiste). Percio' partendo dal fatto che la precisione della finger table dipende dal numero di nodi conosciuti, ogni nodo puo' decidere il bilanciamento dello scambio di messaggi e cercare in modo piu' efficente. Ovviamente la scelta fatta da un singolo nodo impatta sull'intera DHT.

Prestazioni

Le prestazioni di SIPDHT possono essere misurate in termini di numero di messaggi scambiati e nel migliore dei casi (i.e. quando per ogni stabilizzazione sono scambiati logN messaggi), ogni operazione comporta la spedizione di un messaggio in piu' rispetto a Chord. Questo sembra dovuto al fatto che ogni ricerca per essere completata deve raggiungere il predecessore del nodo autoritativo.

NOTA: queste considerazioni sono empiriche.