Modulo QSPN - Percorsi disgiunti

Contents

Modulo QSPN - Percorsi disgiunti
1. Definizione
  1. Perché memorizzare diversi percorsi disgiunti
    1. Rimozione di uno o più percorsi
    2. Congestione di un percorso
  2. Considerazioni sulla mappa gerarchica
2. Operazioni di scelta dei percorsi
  1. Esempio

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

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

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

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.