|
Size: 4514
Comment:
|
Size: 5111
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
| L'obiettivo del modulo QSPN è che i nodi scoprano e memorizzino per ogni destinazione fino a ''n'' rotte disgiunte preferendo le più veloci. | L'obiettivo del modulo QSPN è permettere ad ogni nodo ''n'' di reperire e mantenere per ogni destinazione ''d'' fino a ''max_paths'' percorsi disgiunti, che siano i più rapidi. Inoltre ''n'' vuole mantenere per ogni destinazione ''d'' e per ogni proprio vicino ''v'', almeno 1 percorso, se esiste, indipendentemente dal valore di max_paths e dalle regole di disgiunzione, verso ''d'' che non contiene ''v'' tra i suoi passaggi. Infine ''n'' vuole mantenere per ogni destinazione ''d'' almeno 1 percorso per ogni diverso fingerprint di ''d'' che gli viene segnalato. |
| Line 4: | Line 4: |
| === Esempio 1 === Sia il nostro nodo A e la destinazione G. Siano note le rotte: |
Si definisce ''rapporto di hops comuni'' tra due percorsi ''p'' e ''q'' verso la stessa destinazione, dove ''p'' è il percorso meno costoso dei due, il rapporto tra il numero di singoli nodi comuni nei due percorsi e il numero di singoli nodi nel percorso ''p''. In questo computo non va inclusa la destinazione. Se il rapporto è inferiore ad una certa costante ''max_common_hops_ratio'', oppure se il percorso ''p'' è un diretto vicino e quindi il denominatore sarebbe 0, allora si dice che il percorso ''q'' è disgiunto dal percorso ''p''. Si consideri che i percorsi sono composti da g-nodi. Di ogni g-nodo ''g'' abbiamo una approssimazione del numero di nodi al suo interno ''num(g)''. Se un percorso passa per un g-nodo per arrivare alla destinazione, questo non significa che percorra tutti i nodi al suo interno. Come "stima" del numero di nodi che effettivamente quel percorso prevede prendiamo ''floor ( 1.5 * sqrt ( num ( g ) ) )''. == Operazioni di scelta dei percorsi == Ogni volta che il nodo ''n'' finisce di processare un messaggio ETP, si trova con un numero di percorsi per alcune destinazioni, oltre a quelli che erano già nella sua mappa. Sia ''O~-,,d,,-~'' la lista dei percorsi noti al nodo ''n'' per raggiungere la destinazione ''d''. Sia ''V~-,,n,,-~'' la lista dei vicini di ''n''. In questo documento vediamo come il nodo ''n'' decida quali percorsi mantenere nella propria mappa e quali scartare. Per prima cosa il nodo ''n'' ordina per costo crescente i percorsi in ''O~-,,d,,-~''. Per ogni percorso ''p'' in ''O~-,,d,,-~'', per ogni g-nodo ''h'' in ''p'' (esclusa la destinazione, da ora non lo ripeto più), il nodo ''n'' verifica di avere ''h'' come destinazione possibile nella sua mappa e ne reperisce il numero di nodi al suo interno. Se ''h'' non è presente nella sua mappa allora rimuove ''p'' da ''O~-,,d,,-~''. Poi ''n'' prosegue con questo algoritmo: * Il nodo ''n'' prepara un insieme vuoto ''F~-,,d,,-~''. * Il nodo ''n'' prepara un insieme vuoto ''R~-,,d,,-~''. * Il nodo ''n'' prepara un insieme vuoto ''V~-,,nd,,-~''. * Per ogni vicino ''v'' ∈ ''V~-,,n,,-~'': * ''n'' calcola il massimo distinto g-nodo di ''v'' per ''n'' e lo mette in ''V~-,,nd,,-~''. * Inizia un ciclo ''c1'' per ogni percorso ''p1'' ∈ ''O~-,,d,,-~'': * Se ''p1''.cost = ''dead'': * Esci dal ciclo ''c1''. * ''obbligatorio'' = False. * Se ''p1''.fingerprint ∉ ''F~-,,d,,-~'': * ''obbligatorio'' = True. * ''p1''.fingerprint viene inserito in ''F~-,,d,,-~''. * Per ogni g-nodo ''g'' ∈ ''V~-,,nd,,-~'': * Se ''g'' ∉ p1: * Rimuove ''g'' da ''V~-,,nd,,-~''. * ''obbligatorio'' = True. * Se ''obbligatorio'': * ''p1'' viene inserito in ''R~-,,d,,-~''. * Altrimenti-Se ''R~-,,d,,-~''.size < ''max_paths'': * ''inserire'' = True. * Inizia un ciclo ''c2'' per ogni percorso ''p2'' ∈ ''R~-,,d,,-~'': * ''total_hops'' = 0. * ''common_hops'' = 0. * Per ogni g-nodo ''g2'' ∈ ''p2'': * ''total_hops'' += floor ( 1.5 * sqrt ( num ( ''hg2'' ) ) ). * Se g2 ∈ p1: * ''common_hops'' += floor ( 1.5 * sqrt ( num ( ''hg2'' ) ) ). * Se ''total_hops'' > 0 AND ''common_hops'' / ''total_hops'' > ''max_common_hops_ratio'': * ''inserire'' = False. * Esci dal ciclo ''c2''. * Se ''inserire'': * ''p1'' viene inserito in ''R~-,,d,,-~''. === Esempio === Portiamo a semplice esempio una rete con un solo livello. Sia il nostro nodo A, l'unico vicino B, e la destinazione G. Impostiamo ''max_common_hops_ratio=0.7''. Siano noti i percorsi: |
| Line 13: | Line 59: |
| Prima ordino le rotte (come già fatto sopra) in base al costo. | Prima ordino i percorsi (come già fatto sopra) in base al costo. |
| Line 15: | Line 61: |
| La prima rotta è presa per diritto. | Il primo è preso per diritto. |
| Line 17: | Line 63: |
| La seconda rotta, per decidere se è sufficientemente disgiunta, la devo confrontare solo con la prima. Il confronto si fa con il "rapporto di hops comuni". Esso è il rapporto tra il numero di nodi in comune nelle due rotte e il numero totale di nodi nella rotta più veloce. | Il secondo, per decidere se è sufficientemente disgiunto, lo devo confrontare solo con il primo. Il "rapporto di hops comuni" in questo caso è 1/2, quindi il secondo percorso viene preso. |
| Line 19: | Line 65: |
| In questo caso è 1/2. | Il terzo percorso va confrontato con tutti i precedenti presi, quindi il primo e il secondo. Il rapporto con il primo è 1/2, con il secondo 1/2. |
| Line 21: | Line 67: |
| Se il rapporto è inferiore ad una costante k tra 0 e 1 (oppure se il denominatore è 0) le rotte sono da considerarsi disgiunte. Supponiamo k=0.7. | Quindi il terzo è preso. |
| Line 23: | Line 69: |
| Nel nostro caso la seconda rotta è presa. | Il quarto percorso nel rapporto con il secondo ha 2/2. Quindi non viene preso. |
| Line 25: | Line 71: |
| La terza rotta va confrontata con tutte le precedenti prese, quindi la prima e la seconda. Il rapporto con la prima è 1/2, con la seconda 1/2. Quindi la terza è presa. La quarta rotta nel rapporto con la seconda ha 2/2. Quindi non viene presa. La quinta rotta va ora confrontata con le tre precedenti prese. Anche qui, il rapporto con la seconda è 2/2, quindi non viene presa. === Esempio 2 === Sia il nostro nodo A e la destinazione H. Siano note le rotte: * BCDE 65 (AB=15, BC=15, CD=15, DE=15, EH=5) * BCFE 85 (AB=15, BC=15, CF=25, FE=25, EH=5) * G 100 (AG=50, GH=50) * GFE 120 (AG=50, GF=40, FE=25, EH=5) Prima ordino le rotte (come già fatto sopra) in base al costo. La prima rotta è presa per diritto. La seconda ha ratio 3/4 con la prima quindi viene scartata. La terza va confrontata solo con la prima, ha ratio 0/4 quindi viene presa. La quarta va confrontata con la prima e con la terza, ha rispettivamente 1/4 e 1/1 quindi per via della terza viene scartata. === Esempio 3 - valutazione di un ETP === La situazione iniziale è quella dell'esempio precedente, ma la descriviamo meglio. Il nodo A conosce il costo dell'arco AB e il costo delle path da B verso H. Non sa ad esempio che DE=15 e FE=25. Quindi, in riferimento alle rotte per H passanti per B, sa: * AB=15 * BCDEH=50 => ABCDEH=65 * BCFEH=70 => ABCFEH=85 Analogamente C sa che: * CD=15 * DEH=20 => CDEH=35 * CF=25 * FEH=30 => CFEH=55 Supponiamo ora che il costo del link CF si riduce a 4. Cioè il link è migliorato. C aggiorna le sue rotte e scopre un cambiamento. Ora CFEH=34. C prepara un ETP con le sue rotte aggiornate tra cui CFEH=34 e l'ETP raggiunge B. B scopre che CFEH=34; sapendo che BC=15 ora ha una rotta aggiornata che è BCFEH=49. B prepara un ETP con le sue rotte aggiornate tra cui BCFEH=49 e l'ETP raggiunge A. Cosa deve fare A quando arriva questo ETP? A vede la rotta BCFEH=49. A cerca le rotte verso H nella sua mappa e trova che aveva già la rotta BCFEH, che costava 70. Può quindi aggiornarla. . '''''Nota''': Oltre alle variazioni nel costo di una rotta, un ETP può trasportare altre informazioni da divulgare, come il cambio del fingerprint del g-nodo o del numero di nodi contenuti.'' . '''''Nota''': Qui A potrebbe decidere che la variazione è di poca importanza (ad esempio se il costo della rotta cambia poco in percentuale o se il numero di nodi nel g-nodo cambia poco in percentuale) e, per mantenere basso il traffico delle informazioni, non aggiornare questi dati nella sua mappa. Questa decisione però è vietata se ci sono informazioni cruciali come il cambio di fingerprint del g-nodo.'' Ora A riordina la mappa: cioè per tutte le destinazioni, fra cui anche H, ordina tutte le rotte che conosce dalla più veloce a scendere, applica l'eliminazione delle rotte non disgiunte come descritto sopra, mantiene un massimo di ''n'' rotte e rimuove le altre. Alla fine deve valutare se la sua mappa rispetto a H è cambiata: se ci sono rotte nuove, o non ci sono rotte che prima c'erano, o alcune rotte hanno cambiato il costo. Le rotte nuove o con costo aggiornato (magari dead) vanno a popolare un nuovo set di rotte R. Alla fine, se R ≠ ∅, A produce un ETP con R, la lista di hop attraversati dall'ETP ricevuto da B più l'ID di A. Il nuovo ETP viene inviato a tutti i vicini tranne B. |
Il quinto percorso va ora confrontato con i tre precedenti presi. Anche qui, il rapporto con il secondo è 2/2, quindi non viene preso. |
Modulo QSPN - Percorsi disgiunti
L'obiettivo del modulo QSPN è permettere ad ogni nodo n di reperire e mantenere per ogni destinazione d fino a max_paths percorsi disgiunti, che siano i più rapidi. Inoltre n vuole mantenere per ogni destinazione d e per ogni proprio vicino v, almeno 1 percorso, se esiste, indipendentemente dal valore di max_paths e dalle regole di disgiunzione, verso d che non contiene v tra i suoi passaggi. Infine n vuole mantenere per ogni destinazione d almeno 1 percorso per ogni diverso fingerprint di d che gli viene segnalato.
Si definisce rapporto di hops comuni tra due percorsi p e q verso la stessa destinazione, dove p è il percorso meno costoso dei due, il rapporto tra il numero di singoli nodi comuni nei due percorsi e il numero di singoli nodi nel percorso p. In questo computo non va inclusa la destinazione. Se il rapporto è inferiore ad una certa costante max_common_hops_ratio, oppure se il percorso p è un diretto vicino e quindi il denominatore sarebbe 0, allora si dice che il percorso q è disgiunto dal percorso p.
Si consideri che i percorsi sono composti da g-nodi. Di ogni g-nodo g abbiamo una approssimazione del numero di nodi al suo interno num(g). Se un percorso passa per un g-nodo per arrivare alla destinazione, questo non significa che percorra tutti i nodi al suo interno. Come "stima" del numero di nodi che effettivamente quel percorso prevede prendiamo floor ( 1.5 * sqrt ( num ( g ) ) ).
Operazioni di scelta dei percorsi
Ogni volta che il nodo n finisce di processare un messaggio ETP, si trova con un numero di percorsi per alcune destinazioni, oltre a quelli che erano già nella sua mappa. Sia Od la lista dei percorsi noti al nodo n per raggiungere la destinazione d. Sia Vn la lista dei vicini di n. In questo documento vediamo come il nodo n decida quali percorsi mantenere nella propria mappa e quali scartare.
Per prima cosa il nodo n ordina per costo crescente i percorsi in Od.
Per ogni percorso p in Od, per ogni g-nodo h in p (esclusa la destinazione, da ora non lo ripeto più), il nodo n verifica di avere h come destinazione possibile nella sua mappa e ne reperisce il numero di nodi al suo interno. Se h non è presente nella sua mappa allora rimuove p da Od.
Poi n prosegue con questo algoritmo:
Il nodo n prepara un insieme vuoto Fd.
Il nodo n prepara un insieme vuoto Rd.
Il nodo n prepara un insieme vuoto Vnd.
Per ogni vicino v ∈ Vn:
n calcola il massimo distinto g-nodo di v per n e lo mette in Vnd.
Inizia un ciclo c1 per ogni percorso p1 ∈ Od:
Se p1.cost = dead:
Esci dal ciclo c1.
obbligatorio = False.
Se p1.fingerprint ∉ Fd:
obbligatorio = True.
p1.fingerprint viene inserito in Fd.
Per ogni g-nodo g ∈ Vnd:
Se g ∉ p1:
Rimuove g da Vnd.
obbligatorio = True.
Se obbligatorio:
p1 viene inserito in Rd.
Altrimenti-Se Rd.size < max_paths:
inserire = True.
Inizia un ciclo c2 per ogni percorso p2 ∈ Rd:
total_hops = 0.
common_hops = 0.
Per ogni g-nodo g2 ∈ p2:
total_hops += floor ( 1.5 * sqrt ( num ( hg2 ) ) ).
- Se g2 ∈ p1:
common_hops += floor ( 1.5 * sqrt ( num ( hg2 ) ) ).
Se total_hops > 0 AND common_hops / total_hops > max_common_hops_ratio:
inserire = False.
Esci dal ciclo c2.
Se inserire:
p1 viene inserito in Rd.
Esempio
Portiamo a semplice esempio una rete con un solo livello. Sia il nostro nodo A, l'unico vicino B, e la destinazione G. Impostiamo max_common_hops_ratio=0.7. Siano noti i percorsi:
- BC 150 (AB=50, BC=50, CG=50)
- BD 160 (AB=50, BD=55, DG=55)
- BEF 170 (AB=50, BE=50, EF=35, FG=35)
- BED 180 (AB=50, BE=50, ED=25, DG=55)
- BDEF 190 (AB=50, BD=55, DE=15, EF=35, FG=35)
Prima ordino i percorsi (come già fatto sopra) in base al costo.
Il primo è preso per diritto.
Il secondo, per decidere se è sufficientemente disgiunto, lo devo confrontare solo con il primo. Il "rapporto di hops comuni" in questo caso è 1/2, quindi il secondo percorso viene preso.
Il terzo percorso va confrontato con tutti i precedenti presi, quindi il primo e il secondo. Il rapporto con il primo è 1/2, con il secondo 1/2.
Quindi il terzo è preso.
Il quarto percorso nel rapporto con il secondo ha 2/2. Quindi non viene preso.
Il quinto percorso va ora confrontato con i tre precedenti presi. Anche qui, il rapporto con il secondo è 2/2, quindi non viene preso.