Differences between revisions 11 and 13 (spanning 2 versions)
Revision 11 as of 2015-04-10 15:46:03
Size: 5156
Editor: lukisi
Comment:
Revision 13 as of 2015-07-20 20:42:29
Size: 7748
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:
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. L'obiettivo del presente documento è definire cosa si intende con il termine ''percorsi disgiunti'' e delineare l'algoritmo per la scelta di tali percorsi.

== Definizione ==
Ricordiamo che 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.
Line 10: Line 13:
=== Considerazioni sulla mappa gerarchica ===
Va considerato il motivo per cui si evita di memorizzare percorsi non disgiunti. Assumiamo che il nodo ''n'' conosce alcuni percorsi per raggiungere il nodo ''v''. Il migliore di essi passa per alcuni nodi, tra cui il nodo ''h''. Supponiamo che un messaggio inviato tramite questo percorso fallisce. Supponiamo che il nodo ''v'' sia ancora vivo. Supponiamo che il punto dove il messaggio fallisce è il nodo ''h''. Il nodo ''n'' può provare con un altro dei percorsi che conosce. Ma di tutti gli altri percorsi che ''n'' conosce, quelli che passano per ''h'' falliranno ugualmente. Da questa osservazione si desume che un approccio vantaggioso per risparmiare memoria (e banda, e cpu, e tempi di convergenza) rinunciando al minor numero possibile di informazioni utili sia quello di evitare di memorizzare altri percorsi che passano per molti punti comuni ad un percorso già noto.

Questa argomentazione ha significato fintanto che si considera un percorso come sequenza di nodi. Quando si passa a considerare un percorso come sequenza di gruppi di nodi, l'argomentazione va rivista. Infatti due percorsi ''p1'' e ''p2'' che passano per lo stesso gruppo di nodi ''g'' (specialmente se il gruppo contiene molti nodi) potrebbero essere in realtà in gran parte (o anche del tutto) disgiunti, cioè passare per nodi in gran parte diversi. Quindi, se una trasmissione da ''n'' verso ''v'' attraverso ''p1'' fallisce in uno dei nodi di ''g'', un successivo tentativo da parte di ''n'' attraverso ''p2'' potrebbe riuscire.

Quali informazioni ha il nodo ''n'' relativamente ad un percorso ''p'' verso ''v'' che passa per ''g''? Oltre a sapere che passa per ''g'' sa anche l'identificativo dell'arco attraverso il quale entra in ''g'' e dell'arco attraverso il quale esce da ''g''. Si conviene, dunque, che per i due percorsi ''p1'' e ''p2'' il passaggio per ''g'' vada considerato come "comune" solo se entrambi gli archi di ingresso in ''g'' e di uscita da ''g'' sono identici in ''p1'' e ''p2''.
Line 11: Line 21:
Occorre da subito considerare che il nodo ''n'', quando sceglie i percorsi da mantenere in memoria e quelli da scartare, 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. Inoltre ''n'' vuole mantenere per ogni destinazione ''d'' almeno 1 percorso per ogni diverso fingerprint di ''d'' che gli viene segnalato.
Line 42: Line 54:
    * Per ogni g-nodo ''g2'' ∈ ''p2'' (esclusa la destinazione):     * Per ogni g-nodo ''g2'' (con arco di ingresso ''a_in~-,,g2,,-~'' e arco di uscita ''a_out~-,,g2,,-~'') ∈ ''p2'' (esclusa la destinazione):
Line 44: Line 56:
     * Se g2 ∈ p1:      * Se g2 ∈ p1 '''e''' con arco di ingresso ''a_in~-,,g2,,-~'' e arco di uscita ''a_out~-,,g2,,-~'':
Line 51: Line 63:
 * Il nodo ''n'' sostituisce l'insieme ''O~-,,d,,-~'' con ''R~-,,d,,-~''.

Modulo QSPN - Percorsi disgiunti

L'obiettivo del presente documento è definire cosa si intende con il termine percorsi disgiunti e delineare l'algoritmo per la scelta di tali percorsi.

Definizione

Ricordiamo che 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.

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

Considerazioni sulla mappa gerarchica

Va considerato il motivo per cui si evita di memorizzare percorsi non disgiunti. Assumiamo che il nodo n conosce alcuni percorsi per raggiungere il nodo v. Il migliore di essi passa per alcuni nodi, tra cui il nodo h. Supponiamo che un messaggio inviato tramite questo percorso fallisce. Supponiamo che il nodo v sia ancora vivo. Supponiamo che il punto dove il messaggio fallisce è il nodo h. Il nodo n può provare con un altro dei percorsi che conosce. Ma di tutti gli altri percorsi che n conosce, quelli che passano per h falliranno ugualmente. Da questa osservazione si desume che un approccio vantaggioso per risparmiare memoria (e banda, e cpu, e tempi di convergenza) rinunciando al minor numero possibile di informazioni utili sia quello di evitare di memorizzare altri percorsi che passano per molti punti comuni ad un percorso già noto.

Questa argomentazione ha significato fintanto che si considera un percorso come sequenza di nodi. Quando si passa a considerare un percorso come sequenza di gruppi di nodi, l'argomentazione va rivista. Infatti due percorsi p1 e p2 che passano per lo stesso gruppo di nodi g (specialmente se il gruppo contiene molti nodi) potrebbero essere in realtà in gran parte (o anche del tutto) disgiunti, cioè passare per nodi in gran parte diversi. Quindi, se una trasmissione da n verso v attraverso p1 fallisce in uno dei nodi di g, un successivo tentativo da parte di n attraverso p2 potrebbe riuscire.

Quali informazioni ha il nodo n relativamente ad un percorso p verso v che passa per g? Oltre a sapere che passa per g sa anche l'identificativo dell'arco attraverso il quale entra in g e dell'arco attraverso il quale esce da g. Si conviene, dunque, che per i due percorsi p1 e p2 il passaggio per g vada considerato come "comune" solo se entrambi gli archi di ingresso in g e di uscita da g sono identici in p1 e p2.

Operazioni di scelta dei percorsi

Occorre da subito considerare che il nodo n, quando sceglie i percorsi da mantenere in memoria e quelli da scartare, 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. Inoltre n vuole mantenere per ogni destinazione d almeno 1 percorso per ogni diverso fingerprint di d che gli viene segnalato.

Ogni volta che il nodo n finisce di rielaborare i percorsi di uno o più messaggi 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 g2 (con arco di ingresso a_ing2 e arco di uscita a_outg2) ∈ p2 (esclusa la destinazione):

          • total_hops += floor ( 1.5 * sqrt ( num ( g2 ) ) ).

          • Se g2 ∈ p1 e con arco di ingresso a_ing2 e arco di uscita a_outg2:

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

  • Il nodo n sostituisce l'insieme Od con 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)