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 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 ( 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 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:

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