Differences between revisions 1 and 13 (spanning 12 versions)
Revision 1 as of 2014-11-27 09:45:41
Size: 4512
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 1: Line 1:
= Modulo QSPN - Rotte disgiunte =
L'obiettivo del modulo QSPN è che i nodi scoprano e memorizzino per ogni destinazione fino a ''n'' rotte disgiunte preferendo le più veloci.
= Modulo QSPN - Percorsi disgiunti =
<<TableOfContents(4)>>
Line 4: Line 4:
=== Esempio 1 ===
Sia il nostro nodo A e la destinazione G. Siano note le rotte:
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 ''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'' (con arco di ingresso ''a_in~-,,g2,,-~'' e arco di uscita ''a_out~-,,g2,,-~'') ∈ ''p2'' (esclusa la destinazione):
     * ''total_hops'' += floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).
     * Se g2 ∈ p1 '''e''' con arco di ingresso ''a_in~-,,g2,,-~'' e arco di uscita ''a_out~-,,g2,,-~'':
      * ''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,,-~''.
 * Il nodo ''n'' sostituisce l'insieme ''O~-,,d,,-~'' con ''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 74:
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 76:
La prima rotta è presa per diritto. Il primo è preso per diritto.
Line 17: Line 78:
La seconda rotta, per decidere se è sufficientemente disgiunta, la devo confrontare solo con la prima. Il confronto si fa con il "rapporto di disgiunzione". 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 80:
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 82:
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 84:
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 86:
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 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)