Differences between revisions 9 and 10
Revision 9 as of 2015-03-09 17:55:01
Size: 5136
Editor: lukisi
Comment:
Revision 10 as of 2015-04-08 12:37:36
Size: 5134
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 43: Line 43:
     * ''total_hops'' += floor ( 1.5 * sqrt ( num ( ''hg2'' ) ) ).      * ''total_hops'' += floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).
Line 45: Line 45:
      * ''common_hops'' += floor ( 1.5 * sqrt ( num ( ''hg2'' ) ) ).       * ''common_hops'' += floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).

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 ( g2 ) ) ).

          • Se g2 ∈ p1:
            • common_hops += floor ( 1.5 * sqrt ( num ( g2 ) ) ).

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