In questo paragrafo illustriamo le modalità con cui l’euristica sceglie la politica di lookup da utilizzare. Per fare questa valutazione vengono stimati i tempi di completamento del deployment nelle tre situazioni possibili e quindi viene scelta la politica di lookup più conveniente. Come precedentemente indicato il deployment è composto da due fasi principali: una eventuale fase di lookup e la successiva fase di distribuzione dei blocchi in rete. Nella valutazione del costo della lookup si stima il tempo necessario all’invio di tutti i pacchetti di lookup ed il tempo necessario a leggerne le risposte. In questo tempo si esclude il tempo necessario ad effettuare la verifica di presenza dei blocchi sui nodi in quanto si utilizza una struttura dati ad accesso veloce (hash).
Il costo della fase di distribuzione dei blocchi si calcola sommando il tempo necessario al committente per inviare i messaggi di avvio deployment (pacchetti di NewJob) al tempo necessario ai nodi rappresentanti per scambiarsi in modo distribuito i blocchi non inviati dal committente (in quanto presenti nelle loro cache).
Di seguito indichiamo alcune variabili usate successivamente nell’analisi di convenienza:
- p = probabilità di hit del generico blocco in una delle cache dei nodi, calcolata dinamicamente come descritto in seguito
- P(x) = (1-p)x definita come la probabilità di non trovare un blocco in
una delle cache di x nodi
- M = byte totali da inviare (somma dei byte che i nodi D devono ricevere, compresi quelli in cache)
- V = velocità di invio (in byte al secondo)
- Ta = tempo autenticazione e latenza della singola comunicazione - B = numero blocchi distinti da inviare
- S = dimensione in byte del singolo blocco
Lo spazio occupato da una chiave SHA1 è di 20 byte (le chiavi SHA1 sono di 160bit), la chiave viene però rappresentata da una stringa di esadecimali ed occupa pertanto 40 byte (questo in futuro potrebbe essere ottimizzato per risparmiare spazio).
Il pacchetto di NewJob è un pacchetto del protocollo di deployment della libreria che è inviato dal nodo Committente e che contiene le informazioni sui file da ricevere, nodi da cui prendere blocchi mancanti e blocchi da ricevere dal Committente.
Il pacchetto di lookup è un pacchetto che un nodo invia ad un altro nodo per verificare la presenza di alcuni blocchi nella cache del nodo destinatario, contiene pertanto una lista di chiavi uniche e la risposta allo stesso sarà un pacchetto contenente la lista di chiavi inerenti i blocchi trovati in cache, che naturalmente è un sottoinsieme della lista inviata. Qui si sarebbe potuta utilizzare un’ottimizzazione per risparmiare spazio facendo in modo che il pacchetto di risposta contenesse non le chiavi trovate, ma una maschera di bit rispetto alla richiesta fatta. Si lasciano ottimizzazioni del genere a future versioni della libreria.
Va considerato che sebbene le comunicazioni avvengano in parallelo queste non si concludono tutte contemporaneamente a causa di
piccoli ritardi casuali sulla rete (es. sporadici packet loss o sovraccarichi dei router) o a causa dei nodi che devono elaborare la risposta e che eseguono anche altre applicazioni estranee alla libreria. Statisticamente questi ritardi tendono ad aumentare con l’aumentare del numero di nodi da contattare e nella nostra formula di stima si è modellato questo ritardo ipotizzando che ogni nodo in più da contattare in più in parallelo causi mediamente un decimo di secondo di ritardo in più.
Da ricerche fatte si è visto che un modello analitico che calcoli esattamente questi ritardi non esiste in quanto i pacchetti attraversano sottoreti eterogenee (per ampiezza di banda, latenza, affidabilità) e quindi fuori dal controllo di chi invia; il problema diventa pertanto un problema di tipo combinatorio/probabilistico la cui formalizzazione esula dagli scopi di questa tesi.
La dimensione di un pacchetto di NewJob dipende da:
- spazio utilizzato per indicare le chiavi dei blocchi da ricevere per ricostruire ogni file = M/SD * 40
- spazio per indicare le chiavi dei blocchi unici da ricevere dagli altri nodi: B * (40+4) / D [4 byte per id nodo]
- spazio occupato dai blocchi che il committente deve inviare: BS/D * P(x) (si ipotizza che il committente invii solo i blocchi distinti, gli altri verranno scambiati in modo distribuito)
Il tempo di trasmissione di un pacchetto di New Job è pertanto 1/V * [40 * M/SD + 44 * B/D + BS/D * P(x)] + 1/10 =
1/DV * [40 * M/S + 44 * B + BS * P(x)] + 1/10
Il costo della lookup verso il singolo nodo è dato dal tempo impiegato ad inviare il pacchetto stesso di lookup più il tempo impiegato a leggerne la risposta (si considera nullo il tempo di verifica di presenza
Spazio occupato dalle chiavi dei blocchi distinti di cui si vuole
fare la lookup = B * 40
Spazio occupato dalle chiavi sopra menzionate e trovate in
cache = B * 40 * p
Il tempo di trasmissione di un pacchetto di lookup è pertanto = (40 * B) * (1 + p) / V + 1/10
Nel caso delle politiche 2 e 3 va però considerato che i blocchi non inviati dal committente, in quanto trovati nelle cache dei nodi grazie alla lookup, vanno comunque scambiati tra i nodi. Pertanto al tempo di lookup e di invio dei messaggi di NewJob va aggiunto anche questo. Lo spazio occupato dalle chiavi trovate nelle cache di x nodi è pari a B * S * (1- P(x))
Questi blocchi vengono scambiati in parallelo tra gli x nodi ad una velocità media di x volte V, pertanto il tempo per il loro scambio distribuito è (va sommato anche l’apporto di eventuali ritardi nel contattare x nodi): B * S * (1 - P(x)) * 1 / (x * V) + x / 10 - Costo Politica 1 (x=0, P(0) = 1) =
Ta + Costo pacchetti new job =
Ta + D * 1 / DV * [40 * M/S + 44 * B + BS * P(0)] + D/10 = Ta + 1/V * [40 * M/S + 44 * B + BS] + D/10
- Costo Politica 2 (x=D) =
Ta + CostoLookup + Ta + Costo pacchetti new job + Costo scambio distribuito blocchi trovati in cache =
Ta + D * (40 * B) * (1 + p) / V + D/10 + Ta + D * 1/DV * [40 * M/S + 44 * B + BS * P(D)] + D/10 + B * S * (1- P(D)) * 1 / (D * V) + D/10 = 2 * Ta + D/V * (40 * B) * (1 + p) + 2*D/10 + 1/V * [40 * M/S + 44 * B + BS * P(D)] + B * S * (1- P(D)) * 1 / (D * V) + D/10
- Costo Politica 3 (x=N) =
Ta + Costo lookup + Ta + Costo pacchetti new job =
Ta + N * (40 * B) * (1 + p) / V + N/10 + Ta + D * 1/DV * [40 * M/S + 44 * B + BS * P(N)] + D/10 + B * S * (1- P(N)) * 1 / (N * V) + N/10= 2 * Ta + N/V * (40 * B) * (1 + p) + (N+D)/10 + 1/V * [40 * M/S + 44 * B + BS * P(N)] + B * S * (1- P(N)) * 1 / (N * V) + N/10
La scelta su quale politica utilizzare verterà quindi su quella che stima un tempo di completamento inferiore.
Si sono fatte anche delle prove sperimentali per mettere in mostra i risultati di queste scelte in base alla quantità di dati da inviare e al numero di nodi destinatari e totali della griglia.
Tempi Politiche: D=10, N=20, Prob Hit = 1%
0 20 40 60 80 5 15 25 35 45 55 65 75
Megabyte per Nodo
Se co nd i Pol. 1 Pol. 2 Pol. 3 Fig. 4.3
Nel grafico sono riportate le curve relative ai tempi stimati per il deployment con ognuna delle tre politiche di lookup al variare della quantità di dati da
trasmettere ad ogni nodo. Il test si riferisce al deployment a 10 nodi destinatari (D=10) in una griglia composta da 20 rappresentanti (N=20) e
Tempi Politiche: D=50, N=100, Prob Hit = 1%
10 30 50 70 90 110 130 5 20 35 50 65 80 95 110 125 140Megabyte per Nodo
Se co nd i Pol. 1 Pol. 2 Pol. 3 Fig. 4.4
Nel grafico sono riportate le curve relative ai tempi stimati per il deployment con ognuna delle tre politiche di lookup al variare della quantità di dati da
trasmettere ad ogni nodo. Il test si riferisce al deployment a 50 nodi destinatari (D=50) in una griglia composta da 100 rappresentanti (N=100)
e con probabilità di hit nella cache del singolo nodo dell’1%.
Come si può notare dai grafici in una prima fase iniziale con pochi dati da inviare è sempre più conveniente la politica numero 1 che non paga l’overhead della lookup. Appena però i dati iniziano ad aumentare diventa più conveniente la politica numero 2 e immediatamente dopo la politica numero 3. In generale si è visto che le politiche statisticamente più utilizzate sono la 1 e la 3, la numero 2 viene utilizzata solo in pochi casi dato che il tempo per fare la lookup è poco dipendente dal numero di nodi a cui la si fa. Infatti le quantità di dati scambiati sono poche dato che vengono trasmessi in rete solo chiavi SHA1 e indici di nodi ed inoltre tutte le richieste di lookup vengono inviate in parallelo abbattendo il problema della latenza. Due fattori determinanti che favoriscono l’utilizzo della politica 3 sulla 1 o la 2 sono il numero di nodi totali e la probabilità di hit in cache.
Infatti all’aumentare del numero di nodi la probabilità di non trovare dei blocchi nelle cache decresce in modo esponenziale: P(x) = (1-p)x e in generale il Committente invia solo i blocchi non presenti nelle Cache dei nodi.
Infatti confrontando le figure 4.3 e 4.4 si nota come il divario dei tempi aumenta molto più velocemente nella figura 4.4 in quanto in tale test il numero dei nodi non destinatari è 50 in più dei destinatari, contro 10 del test di cui in figura 4.3