Algoritmi per la risoluzione di range query multidimensionali

Il processo di risoluzione di range query multidimensionali descritto nel capitolo 6 si basa su due algoritmi principali:

• l’algoritmo per il calcolo della Z-region envelope tra due chiavi derivate α e β, descritto nella sezione 6.2.1

• l’algoritmo per il calcolo delle coordinate geometriche degli iper-quadranti resti- tuiti dall’algoritmo precedente descritto nella sezione 6.2.2.

Codice 7.3 – Algoritmo per il calcolo della ZRegion envelope compresa tra due chiavi derivate alpha e beta

1 calculateZRegion(key alpha, key beta){

2 /* si calcolano le codifiche binarie delle chiavi alpha e beta su n*k bit */

3 alphaBin = getBinaryRepresentation(alpha); 4 betaBin = getBinaryRepresentation(beta); 5 currentAlphaPrefix = null;

6 currentBetaPrefix = null;

7 /* si calcola (se esiste) un prefisso comune tra le due chiavi

8 commonPrefix = getKeysCommonPrefix(alphaBin,betaBin);

9 /* se il prefisso comune ha lunghezza maggiore del numero di attributi significa che le */

10 /* due chiavi derivate possiedono almeno un quadrante in comune */

11 if(commonPrefix.length > n)then{

12 /* si calcola il numero di gruppo di n bit in comune tra le due chiavi */

13 groupsCount = commonPrefix/n;

14 /* si trova il quadrante minimo che contiene entrabe le chiavi derivate */

15 minHQuad = getDigitsFromTo(alphaBin,0,groupsCount*n);

16 /* e si aggiunde ai quadranti in output che formano la Z-Region compresa tra le chiavi */

17 output.add(minHQuad);

18 /* si setta il prefisso corrente sia di alpha che di beta al valore dell’iper-quadrante minimo comune */

19 currentAlphaPrefix = minHQuad; 20 currentBetaPrefix = minHQuad; 21 }elsegroupsCount = 0;

22 /* si scorrono i bit di alpha e beta a gruppi di n alla volta */

23 for(i=(groupsCount*n); i<alphaBin.length; i=i+n){

24 /* si esaminano i successivi n bit della chiave alpha */

25 examAlpha = getDigitsFromTo(alphaBin,i,i+n);

26 /* e si aggiungono in output tutti gli iper-quadranti maggiori dell’iper-quadrante

27 /* formato dal prefisso corrente e dai bit in esame di alpha */

28 output.add(calculateHQuadsGreaterThan(currentAlphaPrefix + examAlpha)); 29 /* si esaminano i successivi n bit della chiave alpha */

30 examBeta = getDigitsFromTo(betaBin,i,i+n);

31 /* e si aggiungono in output tutti gli iper-quadranti minori dell’iper-quadrante

32 /* formato dal prefisso corrente e dai bit in esame di beta */

33 output.add(calculateHQuadsSmallerThan(currentBetaPrefix + examBeta));

34 /* si aggiornano i prefissi correnti di alpha e beta aggiungendovi i bit appena esaminati */

35 currentAlphaPrefix = currentAlphaPrefix + examAlpha; 36 currentBetaPrefix = currentBetaPrefix + examBeta; 37 }

38 /* al termine si aggiungono alla lista degli iper-quadranti compresi tra le chiavi derivate */

39 /* alpha e beta (output), le stesse chiavi derivate alpha e beta */

40 output.add(alphaBin); 41 output.add(betaBin); 42 }

Codice 7.4 – Algoritmo per la conversione del navigation code di un iper- quadrante nelle coordinate geometriche che lo definiscono

1 convertHQuadToAttributesIntervals(HQuad hq,n,k){

2 /* si inizializzano gli intervalli relativi agli n attributi pari all’intervallo massimo */

3 /* n = numero di attributi (o dimensioni)

4 /* k = ordine della curva (massimo valore assumibile da ciascun attributo */

5 /* e pari a (2^k)-1 */

6 for(i=0; i<n; i++){

7 interval[i] = [0;(2^k)-1] 8 }

9 /* si scorrono tutti i bit che compongono la codifica binaria dell’iper-quadrante hq */

10 for(j=0; j<hq.size(); j++){

11 bitValue = getBitAtPosition(hq,j);

12 /* si ottiene l’indice dell’attributo relativo a tale bit j-esimo */

13 attribute = i mod (n-1);

14 /* se il bit ha valore zero, si divide a meta’ l’intervallo e si prende la parte sinistra */

15 if(bitValue = 0)then{

16 interval[attribute] = [0;(2^(k-1)-1]; 17 }

18 /* altrimenti si prende la parte destra */

19 else{

20 interval[attribute] = [2^(k-1);(2^k)-1]; 21 }

22 } 23 }

Risultati sperimentali

Questo capitolo `e formato da tre parti principali. Nella sezione 8.1 verr`a descritta

PlanetLab, la piattaforma da cui sono stati raccolti i dati reali utilizzati per i test.

Nella sezione 8.2 sar`a descritta la metodologia di definizione dei test effettuati ed

infine, nella sezione 8.3, verranno riportati i risultati sperimentati ottenuti dal sistema HASP.

8.1

PlanetLab

PlanetLab [43] `e una piattaforma aperta per lo sviluppo, il deployment e l’accesso a

servizi su scala mondiale mediante la rete Internet. La rete dei nodi PlanetLab `e, ad

oggi, composta da 1138 nodi distribuiti in 519 siti in tutto il mondo. Tale infrastruttura

`e utilizzata per l’esecuzione parallela di job che vengono schedulati quindi su nodi

localizzati su scala mondiale. Gli host che fanno parte della rete PlanetLab inviano periodicamente il loro stato ai server, in modo che essi possano controllare lo stato di congestione dei nodi della rete nel tempo e di conseguenza distribuire efficacemente il carico di lavoro sulle varie macchine. Ciascun server ricostruisce, ad intervalli di tempo regolari, a partire dai singoli stati dei nodi, lo stato globale della rete PlanetLab e ne

tiene traccia in opportuni file di log. Lo stato di ciascun nodo della rete PlanetLab `e

definito dai seguenti attributi:

• FreeSwap: il totale della memoria di swap libera

• CPUSys: percentuale di utilizzo della cpu da parte del kernel • CPUIdle: Idle time

• CPUuse: carico sulla cpu

• UPtime: tempo di vita dell’host

• Load: numero di processi in esecuzione sul processore negli ultimi 5 minuti

• MemPress: percentuale della capacit`a di allocare memoria

• MemInfo: percentuale di memoria libera • TXRate: misura della banda in uscita • RXRate: misura della banda in entrata

• LiveSlices: numero di macchine virtuali attive sul nodo

Nelle figure seguenti, dalla 8.1 alla 8.12, sono mostrate le distribuzioni dei valori di

ciascun attributo, ognuno nel range in cui `e definito. Ad esempio l’attributo CPUUser

`e definito nel range [0;100]. Notiamo come, mentre la distribuzione dei valori per

l’attributo freeSwap `e uniforme, per molti altri attributi i valori si concentrino sulla parte alta o bassa dell’intervallo. Per quanto riguarda l’attributo uptime, il grafico `e poco significativo poich`e l’attributo assume valori crescenti nel tempo ed `e molto probabile che non esistano due host con lo stesso valore per quell’attributo.

Figura 8.1 – Distribuzione dei valori dell’attributo freeSwap

Figura 8.3 – Distribuzione dei valori dell’attributo cpuSys

Figura 8.5 – Distribuzione dei valori dell’attributo cpuUse

Figura 8.7 – Distribuzione dei valori dell’attributo load

Figura 8.9 – Distribuzione dei valori dell’attributo memInfo

Figura 8.11 – Distribuzione dei valori dell’attributo RXRate

Figura 8.12 – Distribuzione dei valori dell’attributo liveSlices

In figura 8.13 `e mostrata la distribuzione delle chiavi derivate generate mediante la

0 e scegliendo un numero di attributi n=6 e un ordine della curva k =4.

Figura 8.13 – Distribuzione delle chiavi derivate generate mediante la curva Z- order utilizzando i dati reali di host connessi alla rete PlanetLab al tempo 0