4.2 Query Esatte
4.2.4 Query Esatte: protocollo
Lo spazio degli attributi di VoRaQue viene mappato su un diagramma di Voronoi. In questo modo, ogni nodo viene rappresentato come un punto nello spazio bi-dimensionale. Supponiamo che un utente U richieda al sistema di risolvere la seguente richiesta:
Q = {R|xQ = 128 ∧ yQ = 300} (4.1)
4.2 Query Esatte
che rappresenta la query Q che ricerca la risorsa R di coordinate (128, 300). Da un punto di vista geometrico, la query esatta viene rappresentata come un punto nello spazio degli attributi. Quest’ultimo può coincidere con le coordinate di un peer oppure può giacere all’interno di una regione di Voronoi. Di conseguenza, l’obiettivo di una query esatta è individuare il punto corrispondente nello spazio e restituire una risposta positiva se coincide esattamente con le coordinate di un peer, negativa altrimenti.
Il nodo N di coordinate (xN, yN) è un match per la query Q se vale la seguente
condizione:
xQ = xN ∧ yQ = yN
In caso contrario occorre verificare se il punto definito da Q appartiene alla regione di N . Per eseguire questo test basta applicare la proprietà dei diagrammi di Voronoi, ovvero, un punto q fa parte della cella pi se e solo se dist(q, pj) > dist(q, pi) per ogni
pj con i 6= j. In altre parole deve valere la seguente condizione:
dist(Q, P ) < dist(Q, V )∀V ∈ V oronoiN eighbours(P )
Ciò significa che la distanza euclidea tra Q e P è più piccola della distanza che separa Q da qualunque vicino di P .
L’algoritmo che viene eseguito da ogni nodo che riceve una query esatta è derivato da queste osservazioni. Se un nodo P riceve una query esatta confronta le proprie coordinate per verificare se è un match per la query. In caso contrario confronta la distanza della query da se stesso e dai propri vicini. Se si individua come nodo a distanza minima significa che la query non ha soluzione.
Per esempio, osservando la figura 4.4 possiamo notare che la query Q non ha esito positivo, in quanto il punto che definisce giace nella regione di Voronoi del nodo P ma non combacia con quest’ultimo.
Iniziamo la descrizione del protocollo con la procedura per la risoluzione di una query esatta: per la trattazione considereremo l’overlay network formata dai nodi ri-
VoRaQue: algoritmi e procolli
Figura 4.4: Rappresentazione geometrica della query esatta Q.
portati in figura 4.5. La procedura inizia con la sottomissione della richiesta 4.1 da parte di un utente connesso alla rete tramite il nodo N .
Prima di inoltrare il messaggio, VoRaQue verifica se le coordinate del nodo coinci- dono con il punto definito dalla query. In caso affermativo è il match per Q e la risposta viene restituita all’utente senza la necessità di inviare alcun pacchetto sulla rete. In ca- so negativo, si verifica se il punto giace nella regione di Voronoi di N . Se quest’ultimo test restituisce esito positivo, non vi è alcun match per la richiesta, ma otteniamo la sua risoluzione senza dover inoltrare il messaggio ad alcun vicino. In caso negativo, N non è in grado di restituire una risposta alla query Q4, quindi l’applicazione costruisce un
messaggio di tipo ExactMSG contenente le coordinate del punto da individuare nella rete.
Questo pacchetto viene inviato ad un nodo che viene selezionato secondo una
4Quando viene utilizzata la dicitura il “nodo è in grado di risolvere la query”, significa che il punto
definito dalla query o coincide con le coordinate del nodo oppure appartiene alla sua regione. In altre parole significa che almeno uno dei due test che il peer deve eseguire ogni volta riceve un messaggio di tipo ExactMSG, da esito positivo.
4.2 Query Esatte
Figura 4.5: Situazione iniziale.
strategia greedy: il destinatario è il peer le cui coordinate minimizzano la distanza eu- clidea con il punto definito dalla richiesta e appartiene all’insieme deiVoronoiNeigh- bours o CloseNeighbours del nodo che sta elaborando la query.
Tutte le operazioni sopra descritte vengono applicate da qualsiasi peer che riceve un messaggio di tipo ExactMSG finché non viene raggiunto il nodo in grado di risol- vere la query. Quest’ultimo (nodo P di figura 4.5) si preoccupa di restituire la risposta al nodo richiedente tramite il messaggio di tipo ReplyExactMSG inserendo le sue co- ordinate se è un match per Q, altrimenti non viene immesso nessun valore nel payload. Nella figura seguente abbiamo un esempio relativo alla risoluzione di una query Q.
In figura 4.6 le regioni di Voronoi in giallo rappresentano i VoronoiNeighbours, quelle in verde sono sia VoronoiNeighbours che CloseNeighbours. In figura 4.6a il nodo N invia la richiesta di ExactMSG al vicino N1 poiché le coordinate di N1mini-
mizzano la distanza euclidea con il punto Q. In figura 4.6b N1 invia la query a N2 in
quanto risulta essere il nodo più vicino alla destinazione.
VoRaQue: algoritmi e procolli
Figura 4.6: Risoluzione di query esatta.
Figura 4.7: Simulazione di una risoluzione di query esatta.
4.2 Query Esatte
punto Q non coincide con le sue coordinate ma appartiene alla sua regione di Voronoi. Quindi, costruisce un messaggio di ReplyExactMSG, contenente una risposta negativa, che viene inviato direttamente al richiedente (figura 4.7b).
Durante l’esecuzione del routing greedy, può accadere che il Time-To-Live rag- giunga il valore zero senza che il pacchetto sia giunto al nodo in grado di risolvere la query. In questo caso, il peer che interrompe la propagazione della query, costruisce un messaggio di tipo ExpiredTTL e lo invia al nodo che ha generato la richiesta per informare l’utente che è necessario aumentare il valore del TTL per raggiungere la destinazione. Utilizzare un TTL personalizzabile permette al protocollo di essere più adattabile alle esigenze dell’utente.
VoRaQue: algoritmi e procolli