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 incluso il singolo nodo 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 ) ) ).

Abbiamo detto che bisogna escludere dal computo il singolo nodo destinazione. Ma se la destinazione di un percorso p è un g-nodo g che contiene più di un singolo nodo, allora dobbiamo considerare che la vera destinazione del percorso p sarà un singolo nodo al suo interno. Possiamo stimare come numero di nodi che effettivamente quel percorso prevede all'interno di g la metà della formula precedente, cioè floor ( 0.75 * sqrt ( num ( g ) ) ). Da questo valore, se maggiore di 0, togliamo 1, cioè il singolo nodo destinazione.

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:

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:

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:

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:

Operazioni di scelta dei percorsi

Nell'algoritmo occorre tenere in considerazione i requisiti che si prefigge il modulo a riguardo delle conoscenze che il nodo n deve mantenere indipendentemente dal valore di max_paths e dalle regole di disgiunzione:

Ogni volta che il nodo n finisce di rielaborare i percorsi di uno o più messaggi ETP, si trova con un set di percorsi per alcune destinazioni. A questi, che possono essere nuovi o no, il nodo aggiunge quelli che già conosceva per le stesse destinazioni. Indichiamo con O il set di percorsi così ottenuto. Vediamo come il nodo n decida quali percorsi mantenere nella propria mappa e quali scartare.

Per prima cosa il nodo n fa queste operazioni:

Poi il nodo n esamina ogni singola destinazione d di questo set O. Sia Od la lista dei percorsi noti al nodo n per raggiungere la destinazione d. Sia Vn la lista dei vicini di n.

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:

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:

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

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

Il valore max_common_hops_ratio, però, non deve raggiungere lo 0 assoluto, anche se il numero di nodi in g è molto grande. Infatti, se il numero di nodi in g è elevato, e di conseguenza lo è probabilmente anche il numero di archi da h a g, allora il computo del numero di singoli nodi toccati all'interno di g prima di giungere al singolo nodo destinazione (di cui si tiene conto nell'algoritmo sopra delineato) aiuterà a tenere basso il rapporto di hop comuni tra due percorsi p e q, ma non lo potrà azzerare del tutto se prima di arrivare a g entrambi i percorsi hanno qualche singolo nodo in comune. Ad esempio, se il nodo di partenza ha un solo vicino e un solo arco, anche se il g-nodo destinazione fosse molto grande, non avrà mai due percorsi con rapporto di hop comuni uguale a zero.

Quest'ultima riflessione fa pensare che il valore max_common_hops_ratio vada stabilito anche in base al numero di diretti vicini che il nodo n ha. Si noti che abbiamo volutamente usato l'espressione diretto vicino e non arco. Se il numero di vicini è basso (1 o 2) conviene che il max_common_hops_ratio non sia troppo basso. Meglio ancora, andrebbe considerato il numero di diretti vicini tramite i quali n ha almeno un percorso verso d.