Differences between revisions 7 and 9 (spanning 2 versions)
Revision 7 as of 2015-02-26 22:13:14
Size: 4514
Editor: lukisi
Comment:
Revision 9 as of 2015-03-09 17:55:01
Size: 5136
Editor: lukisi
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. <<TableOfContents(4)>>
Line 4: Line 4:
=== Esempio 1 ===
Sia il nostro nodo A e la destinazione G. Siano note le rotte:
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 ''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), 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'' (esclusa la destinazione):
     * ''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 61:
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 63:
La prima rotta è presa per diritto. Il primo è preso per diritto.
Line 17: Line 65:
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 67:
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 69:
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 71:
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 73:
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), 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 vVn:

    • n calcola il massimo distinto g-nodo di v per n e lo mette in Vnd.

  • Inizia un ciclo c1 per ogni percorso p1Od:

    • 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 gVnd:

      • 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 p2Rd:

        • total_hops = 0.

        • common_hops = 0.

        • Per ogni g-nodo g2p2 (esclusa la destinazione):

          • 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.

Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti (last edited 2016-04-08 17:00:59 by lukisi)