Differences between revisions 12 and 14 (spanning 2 versions)
Revision 12 as of 2015-04-23 20:43:14
Size: 5461
Editor: lukisi
Comment:
Revision 14 as of 2015-08-13 10:41:43
Size: 13041
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 12: Line 12:

=== Perché memorizzare diversi percorsi disgiunti ===
Quali motivi ci sono per un nodo di memorizzare diversi percorsi verso una destinazione?

==== Rimozione di uno o più percorsi ====
Supponiamo che il nodo ''n'' ha memorizzato 3 percorsi verso ''d''. Assumiamo anche che il nodo ''n'' per inviare pacchetti verso ''d'' usi sempre il migliore dei 3. A che serve avere in memoria anche gli altri 2?

Siano i percorsi:
 * ''p1'' composto da ''n'' → ''a'' → ''b'' → ''c'' → ''d''. Sia questo il migliore.
 * ''p2'' composto da ''n'' → ''x'' → ''y'' → ''z'' → ''d''.
 * ''p3'' composto da ''n'' → ''q'' → ''r'' → ''s'' → ''d''. Sia questo il peggiore.

Supponiamo ora che il collegamento tra i nodi ''b'' e ''c'' si interrompa. Il nodo ''b'' avverte ''a'' che questo percorso verso ''d'' non c'è più. Il nodo ''a'' avverte il nodo ''n'' che questo percorso verso ''d'' non c'è più.

Il nodo ''n'' si vede rimosso il percorso ''p1'', il migliore verso ''d'', cioè quello che usava sempre. Avendo esso in memoria altri percorsi che non hanno subito variazioni, non ha bisogno di attendere altri eventi né di iniziare altri processi esplorativi, ma subito conosce un altro percorso ''p2'' da usare per inviare pacchetti verso ''d''.

Ovviamente, per ragioni di memoria e di traffico, il nodo ''n'' non può né memorizzare né ritrasmettere tutti i percorsi possibili verso ''d'', ma solo fino ad un certo numero massimo. Vediamo allora perché preferire la memorizzazione di percorsi disgiunti.

Siano questi i percorsi noti a ''n'' verso ''d'':
 * ''p1'' composto da ''n'' → ''a'' → ''b'' → ''c'' → ''d''. Sia questo il migliore.
 * ''p2'' composto da ''n'' → ''x'' → ''b'' → ''c'' → ''d''.
 * ''p3'' composto da ''n'' → ''q'' → ''r'' → ''s'' → ''d''. Sia questo il peggiore.

Supponiamo ora che il collegamento tra i nodi ''b'' e ''c'' si interrompa. Il nodo ''b'' avverte ''a'' che questo percorso verso ''d'' non c'è più. Il nodo ''a'' avverte il nodo ''n'' che questo percorso verso ''d'' non c'è più.

Inoltre, il nodo ''b'' avverte ''x'' che questo percorso verso ''d'' non c'è più. Il nodo ''x'' avverte il nodo ''n'' che questo percorso verso ''d'' non c'è più.

In rapida successione, a motivo di un unico collegamento venuto a mancare, il nodo ''n'' si vede rimossi 2 dei suoi 3 percorsi verso ''n''. Questo evento risulta più probabile quando i percorsi tenuti in memoria non sono sufficientemente disgiunti.

==== Congestione di un percorso ====
Assumiamo che il lettore abbia una conoscenza di base del meccanismo implementato nel TCP per evitare la congestione di un percorso.

In presenza di un "collo di bottiglia" in un percorso, il meccanismo prevede che il nodo che origina la trasmissione individui in poco tempo quale sia la massima rapidità con cui può trasmettere pacchetti uno dopo l'altro. C'è da dire anche che nei moderni dispositivi di rete usati nelle dorsali di Internet il fenomeno del [[https://en.wikipedia.org/wiki/Bufferbloat|bufferbloat]] ostacola questo meccanismo, a discapito del buon funzionamento della rete.

Il meccanismo di ''congestion avoidance'' consiste essenzialmente nel segnalare in qualche modo al nodo originante il fatto che sta trasmettendo troppo in fretta. Questa segnalazione può arrivare fondamentalmente in due modi:
 * alcuni pacchetti sono stati scartati da un router perché li riceve troppo in fretta rispetto a quanto li possa ritrasmettere; quindi il nodo destinazione segnala al mittente che ha ricevuto il pacchetto "n+1" ma non il pacchetto "n".
 * un router segnala direttamente al mittente, prima che sia costretto a scartare i suoi pacchetti, che sta trasmettendo troppo in fretta.

Supponiamo che una versione aggiornata del protocollo TCP (o un altro protocollo del livello di trasporto) sia in grado di indicare al nodo mittente anche il punto in cui il collo di bottiglia si sta verificando.

Con questa informazione, se il nodo ha memoria di altri percorsi per raggiungere la destinazione ''d'' e di questi percorsi conosce i vari passaggi intermedi, il nodo ''n'' è in grado di scegliere con maggior efficienza quale percorso usare per i prossimi pacchetti.

Anche in questo caso è evidente che sia meglio per il nodo ''n'' non solo conoscere diversi percorsi, ma che siano tra loro più disgiunti possibile.

=== Considerazioni sulla mappa gerarchica ===
Abbiamo mostrato sopra che se due percorsi ''p1'' e ''p2'' hanno in comune un passaggio (ad esempio ... → ''b'' → ''c'' → ...) questo li rende poco disgiunti.

Questo è vero fintanto che si considera un percorso come sequenza di nodi, ma può non essere vero quando si passa a considerare un percorso come sequenza di gruppi di nodi. 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 il percorso ''p1'' da ''n'' verso ''d'' viene rimosso a causa della caduta di un collegamento tra due nodi interni a ''g'', il percorso ''p2'' potrebbe rimanere valido.

Quali informazioni ha il nodo ''n'' relativamente ad un percorso ''p'' verso ''d'' 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''.

Abbiamo già detto quale formula applichiamo al numero stimato di nodi presenti in ''g'' per stimare il numero di nodi interni a ''g'' che saranno toccati da un percorso ''p'' che "tocca" ''g''.

Consideriamo i due percorsi ''p'' e ''q'' verso ''d'', con ''p'' il percorso meno costoso. Supponiamo che entrambi contengano il passaggio in ''g''. Sia ''numpath ( g )'' il numero di nodi ottenuto con la suddetta formula come stima dei nodi toccati all'interno di ''g''.

Quando si calcola il rapporto di hops comuni tra ''p'' e ''q'', nel computo del numero di singoli nodi in ''p'' vi sommiamo ''numpath ( g )''. Invece nel computo del numero di singoli nodi comuni nei due percorsi procediamo in maniera diversa a seconda di questi casi:
 * Se in entrambi i percorsi ''p'' e ''q'' si entra in ''g'' attraverso l'arco ''a'' e se ne esce attraverso l'arco ''b'', allora vi sommiamo ''numpath ( g )''.
 * Se in entrambi i percorsi ''p'' e ''q'' si entra in ''g'' attraverso l'arco ''a'', ma se ne esce attraverso due archi distinti ''b1'' e ''b2'', allora vi sommiamo ''ceil (numpath ( g ) / 2)''.
 * Se nei percorsi ''p'' e ''q'' si entra in ''g'' attraverso due archi distinti ''a1'' e ''a2'', ma se ne esce attraverso lo stesso arco ''b'', allora vi sommiamo ''ceil (numpath ( g ) / 2)''.
 * Se nei percorsi ''p'' e ''q'' si entra in ''g'' attraverso due archi distinti ''a1'' e ''a2'' e se ne esce attraverso due archi distinti ''b1'' e ''b2'', allora vi sommiamo 0.
Line 47: Line 107:
    * Per ogni g-nodo ''g2'' ∈ ''p2'' (esclusa la destinazione):
     * ''total_hops'' += floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).
    * Per ogni g-nodo ''g2'' (con arco di ingresso ''a_in~-,,g2,,-~'' e arco di uscita ''a_out~-,,g2,,-~'') ∈ ''p2'' (esclusa la destinazione):
     * ''num_path_g2'' = floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).
     * ''total_hops'' += ''num_path_g2''.
Line 50: Line 111:
      * ''common_hops'' += floor ( 1.5 * sqrt ( num ( ''g2'' ) ) ).       * Se nel percorso p1 l'arco di ingresso in g2 è ''a_in~-,,g2,,-~'':
       * Se nel percorso p1 l'arco di uscita da g2 è ''a_out~-,,g2,,-~'':
        * ''common_hops'' += ''num_path_g2''.
       * Altrimenti:
        * ''common_hops'' += ceil (''num_path_g2'' / 2).
      * Altrimenti:
       * Se nel percorso p1 l'arco di uscita da g2 è ''a_out~-,,g2,,-~'':
        * ''common_hops'' += ceil (''num_path_g2'' / 2).
       * Altrimenti:
        * ''common_hops'' += 0.
Line 56: Line 126:
 * 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 ) ) ).

Perché memorizzare diversi percorsi disgiunti

Quali motivi ci sono per un nodo di memorizzare diversi percorsi verso una destinazione?

Rimozione di uno o più percorsi

Supponiamo che il nodo n ha memorizzato 3 percorsi verso d. Assumiamo anche che il nodo n per inviare pacchetti verso d usi sempre il migliore dei 3. A che serve avere in memoria anche gli altri 2?

Siano i percorsi:

  • p1 composto da nabcd. Sia questo il migliore.

  • p2 composto da nxyzd.

  • p3 composto da nqrsd. Sia questo il peggiore.

Supponiamo ora che il collegamento tra i nodi b e c si interrompa. Il nodo b avverte a che questo percorso verso d non c'è più. Il nodo a avverte il nodo n che questo percorso verso d non c'è più.

Il nodo n si vede rimosso il percorso p1, il migliore verso d, cioè quello che usava sempre. Avendo esso in memoria altri percorsi che non hanno subito variazioni, non ha bisogno di attendere altri eventi né di iniziare altri processi esplorativi, ma subito conosce un altro percorso p2 da usare per inviare pacchetti verso d.

Ovviamente, per ragioni di memoria e di traffico, il nodo n non può né memorizzare né ritrasmettere tutti i percorsi possibili verso d, ma solo fino ad un certo numero massimo. Vediamo allora perché preferire la memorizzazione di percorsi disgiunti.

Siano questi i percorsi noti a n verso d:

  • p1 composto da nabcd. Sia questo il migliore.

  • p2 composto da nxbcd.

  • p3 composto da nqrsd. Sia questo il peggiore.

Supponiamo ora che il collegamento tra i nodi b e c si interrompa. Il nodo b avverte a che questo percorso verso d non c'è più. Il nodo a avverte il nodo n che questo percorso verso d non c'è più.

Inoltre, il nodo b avverte x che questo percorso verso d non c'è più. Il nodo x avverte il nodo n che questo percorso verso d non c'è più.

In rapida successione, a motivo di un unico collegamento venuto a mancare, il nodo n si vede rimossi 2 dei suoi 3 percorsi verso n. Questo evento risulta più probabile quando i percorsi tenuti in memoria non sono sufficientemente disgiunti.

Congestione di un percorso

Assumiamo che il lettore abbia una conoscenza di base del meccanismo implementato nel TCP per evitare la congestione di un percorso.

In presenza di un "collo di bottiglia" in un percorso, il meccanismo prevede che il nodo che origina la trasmissione individui in poco tempo quale sia la massima rapidità con cui può trasmettere pacchetti uno dopo l'altro. C'è da dire anche che nei moderni dispositivi di rete usati nelle dorsali di Internet il fenomeno del bufferbloat ostacola questo meccanismo, a discapito del buon funzionamento della rete.

Il meccanismo di congestion avoidance consiste essenzialmente nel segnalare in qualche modo al nodo originante il fatto che sta trasmettendo troppo in fretta. Questa segnalazione può arrivare fondamentalmente in due modi:

  • alcuni pacchetti sono stati scartati da un router perché li riceve troppo in fretta rispetto a quanto li possa ritrasmettere; quindi il nodo destinazione segnala al mittente che ha ricevuto il pacchetto "n+1" ma non il pacchetto "n".
  • un router segnala direttamente al mittente, prima che sia costretto a scartare i suoi pacchetti, che sta trasmettendo troppo in fretta.

Supponiamo che una versione aggiornata del protocollo TCP (o un altro protocollo del livello di trasporto) sia in grado di indicare al nodo mittente anche il punto in cui il collo di bottiglia si sta verificando.

Con questa informazione, se il nodo ha memoria di altri percorsi per raggiungere la destinazione d e di questi percorsi conosce i vari passaggi intermedi, il nodo n è in grado di scegliere con maggior efficienza quale percorso usare per i prossimi pacchetti.

Anche in questo caso è evidente che sia meglio per il nodo n non solo conoscere diversi percorsi, ma che siano tra loro più disgiunti possibile.

Considerazioni sulla mappa gerarchica

Abbiamo mostrato sopra che se due percorsi p1 e p2 hanno in comune un passaggio (ad esempio ... → bc → ...) questo li rende poco disgiunti.

Questo è vero fintanto che si considera un percorso come sequenza di nodi, ma può non essere vero quando si passa a considerare un percorso come sequenza di gruppi di nodi. 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 il percorso p1 da n verso d viene rimosso a causa della caduta di un collegamento tra due nodi interni a g, il percorso p2 potrebbe rimanere valido.

Quali informazioni ha il nodo n relativamente ad un percorso p verso d 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.

Abbiamo già detto quale formula applichiamo al numero stimato di nodi presenti in g per stimare il numero di nodi interni a g che saranno toccati da un percorso p che "tocca" g.

Consideriamo i due percorsi p e q verso d, con p il percorso meno costoso. Supponiamo che entrambi contengano il passaggio in g. Sia numpath ( g ) il numero di nodi ottenuto con la suddetta formula come stima dei nodi toccati all'interno di g.

Quando si calcola il rapporto di hops comuni tra p e q, nel computo del numero di singoli nodi in p vi sommiamo numpath ( g ). Invece nel computo del numero di singoli nodi comuni nei due percorsi procediamo in maniera diversa a seconda di questi casi:

  • Se in entrambi i percorsi p e q si entra in g attraverso l'arco a e se ne esce attraverso l'arco b, allora vi sommiamo numpath ( g ).

  • Se in entrambi i percorsi p e q si entra in g attraverso l'arco a, ma se ne esce attraverso due archi distinti b1 e b2, allora vi sommiamo ceil (numpath ( g ) / 2).

  • Se nei percorsi p e q si entra in g attraverso due archi distinti a1 e a2, ma se ne esce attraverso lo stesso arco b, allora vi sommiamo ceil (numpath ( g ) / 2).

  • Se nei percorsi p e q si entra in g attraverso due archi distinti a1 e a2 e se ne esce attraverso due archi distinti b1 e b2, allora vi sommiamo 0.

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

          • num_path_g2 = floor ( 1.5 * sqrt ( num ( g2 ) ) ).

          • total_hops += num_path_g2.

          • Se g2 ∈ p1:
            • Se nel percorso p1 l'arco di ingresso in g2 è a_ing2:

              • Se nel percorso p1 l'arco di uscita da g2 è a_outg2:

                • common_hops += num_path_g2.

              • Altrimenti:
                • common_hops += ceil (num_path_g2 / 2).

            • Altrimenti:
              • Se nel percorso p1 l'arco di uscita da g2 è a_outg2:

                • common_hops += ceil (num_path_g2 / 2).

              • Altrimenti:
                • common_hops += 0.

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