Differences between revisions 16 and 17
Revision 16 as of 2015-09-05 09:36:20
Size: 14235
Editor: lukisi
Comment:
Revision 17 as of 2015-09-18 15:48:18
Size: 17105
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 20: Line 20:
Line 31: Line 32:
Line 47: Line 49:
Line 72: Line 75:
Line 154: Line 158:

== Da esplorare ==
Rendere il numero ''max_common_hops_ratio'', cioè il massimo rapporto di hop comuni nei percorsi disgiunti, dipendente dalla dimensione approssimata del g-nodo destinazione.

Questo dovrebbe aiutare nell'avere a disposizione un valido ventaglio di percorsi. Supponiamo che un nodo ''n'' vuole raggiungere una destinazione ''d''. I percorsi che ''n'' memorizza sono sempre verso un g-nodo visibile nella sua mappa. Quindi ''n'' ha dei percorsi verso il massimo distinto g-nodo di ''d''. Sia tale g-nodo ''g''. Sia ''l'' il livello di tale g-nodo.

Il nodo ''n'' non ha alcuna informazione su dove si trovi il nodo ''d'' all'interno di ''g''. Inoltre sappiamo che tutti i percorsi che ''n'' memorizza verso il g-nodo ''g'' sono completamente interni al loro minimo comune g-nodo, chiamiamolo ''w'', di livello ''l'' + 1. Chiamiamo ''h'' il g-nodo di livello ''l'' a cui appartiene ''n''. Sappiamo che ''h'' != ''g''.

Ci saranno un certo numero di archi che costituiscono l'ultimo possibile passo dei percorsi verso ''g'', che cioè partendo da un g-nodo di livello ''l'' diverso da ''g'' entrano in ''g''. Possiamo dire che più è alto il numero di nodi in ''g'' più è probabilmente alto il numero di possibili archi che entrano in ''g''. C'è da dire che, sebbene il nodo ''n'' sappia quale sia l'arco entrante in ''g'' verso il quale ha il percorso più veloce (o meglio meno costoso), il nodo ''n'' non può sapere quale di questi archi sia quello più prossimo (con il percorso meno costoso) al nodo ''d''.

Per semplicità, supponiamo che la ''gsize(l)'' sia 2. Allora all'interno del g-nodo ''w'' abbiamo un certo numero di archi che collegano direttamente il g-nodo ''h'' al g-nodo ''g''.

Questa immagine può aiutare a visualizzare lo scenario. Qualsiasi punto dentro l'area ''h'' può essere il nodo ''n''. Qualsiasi punto dentro l'area ''g'' può essere il nodo ''d''.

{{attachment:draw3.png|Esempio di scenario}}

Siccome vogliamo che il nodo ''n'' mantenga un numero fisso ''max_paths'' di percorsi verso ''g'', se il numero di archi da ''h'' a ''g'' è piccolo, conviene che il valore di ''max_common_hops_ratio'' sia non troppo basso, altrimenti si rischia di scartarne molti e di avere alla fine poche possibili alternative.

Man mano che il numero di archi da ''h'' a ''g'' diventa (ipoteticamente) grande, conviene che il valore di ''max_common_hops_ratio'' si abbassi tendendo a 0. Infatti diventa più probabile che il nodo ''n'' individui fino ad almeno ''max_paths'' percorsi verso ''g'' con un elevato grado di disgiunzione.

Inoltre tali percorsi molto disgiunti porteranno, con buona probabilità, a fare ingresso in ''g'' da archi fra loro geograficamente lontani, che di conseguenza avranno probabilmente percorsi verso il singolo nodo ''d'' anch'essi con un elevato grado di disgiunzione.

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 questi i percorsi noti a n verso d:

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

L'esplorazione della rete svolta dal modulo QSPN mira a trovare i percorsi migliori rispetto ad una certa metrica. Di norma questa sarà la latenza; ma anche se fosse la larghezza di banda questa verrebbe misurata per ogni singolo arco in determinati momenti. Questo per dire che il percorso che è stato individuato come il migliore, qualsiasi metrica sia stata usata per la sua individuazione, in un certo momento potrebbe non essere quello che offre il miglior throughput.

Soltanto nel momento in cui il nodo n usa un percorso p1 per inviare una grossa quantità di dati a d, allora si può rendere conto dell'efficienza che il percorso ha in quel momento.

Il nodo potrebbe provare anche gli altri percorsi a lui noti, per individuare il migliore in quel momento. 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. Infatti, se il collo di bottiglia di un percorso risulta essere un arco che in quel momento esperimenta un fenomeno di congestione particolarmente elevata, il nodo n non avrà alcun vantaggio se usa un altro percorso che passa per lo stesso arco.

Per finire, una osservazione. Supponiamo che in una versione aggiornata del protocollo TCP (o un altro protocollo del livello di trasporto) il router che satura il suo link di trasmissione sia in grado di indicare al nodo mittente non solo che deve rallentare, ma 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 accuratezza quale percorso provare per le prossime connessioni.

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

Da esplorare

Rendere il numero max_common_hops_ratio, cioè il massimo rapporto di hop comuni nei percorsi disgiunti, dipendente dalla dimensione approssimata del g-nodo destinazione.

Questo dovrebbe aiutare nell'avere a disposizione un valido ventaglio di percorsi. Supponiamo che un nodo n vuole raggiungere una destinazione d. I percorsi che n memorizza sono sempre verso un g-nodo visibile nella sua mappa. Quindi n ha dei percorsi verso il massimo distinto g-nodo di d. Sia tale g-nodo g. Sia l il livello di tale g-nodo.

Il nodo n non ha alcuna informazione su dove si trovi il nodo d all'interno di g. Inoltre sappiamo che tutti i percorsi che n memorizza verso il g-nodo g sono completamente interni al loro minimo comune g-nodo, chiamiamolo w, di livello l + 1. Chiamiamo h il g-nodo di livello l a cui appartiene n. Sappiamo che h != g.

Ci saranno un certo numero di archi che costituiscono l'ultimo possibile passo dei percorsi verso g, che cioè partendo da un g-nodo di livello l diverso da g entrano in g. Possiamo dire che più è alto il numero di nodi in g più è probabilmente alto il numero di possibili archi che entrano in g. C'è da dire che, sebbene il nodo n sappia quale sia l'arco entrante in g verso il quale ha il percorso più veloce (o meglio meno costoso), il nodo n non può sapere quale di questi archi sia quello più prossimo (con il percorso meno costoso) al nodo d.

Per semplicità, supponiamo che la gsize(l) sia 2. Allora all'interno del g-nodo w abbiamo un certo numero di archi che collegano direttamente il g-nodo h al g-nodo g.

Questa immagine può aiutare a visualizzare lo scenario. Qualsiasi punto dentro l'area h può essere il nodo n. Qualsiasi punto dentro l'area g può essere il nodo d.

Siccome vogliamo che il nodo n mantenga un numero fisso max_paths di percorsi verso g, se il numero di archi da h a g è piccolo, conviene che il valore di max_common_hops_ratio sia non troppo basso, altrimenti si rischia di scartarne molti e di avere alla fine poche possibili alternative.

Man mano che il numero di archi da h a g diventa (ipoteticamente) grande, conviene che il valore di max_common_hops_ratio si abbassi tendendo a 0. Infatti diventa più probabile che il nodo n individui fino ad almeno max_paths percorsi verso g con un elevato grado di disgiunzione.

Inoltre tali percorsi molto disgiunti porteranno, con buona probabilità, a fare ingresso in g da archi fra loro geograficamente lontani, che di conseguenza avranno probabilmente percorsi verso il singolo nodo d anch'essi con un elevato grado di disgiunzione.

Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti (last edited 2016-04-08 17:00:59 by lukisi)