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.

Esempio 1

Sia il nostro nodo A e la destinazione G. Siano note le rotte:

Prima ordino le rotte (come già fatto sopra) in base al costo.

La prima rotta è presa per diritto.

La seconda rotta, per decidere se è sufficientemente disgiunta, la devo confrontare solo con la prima. Il confronto si fa con il "rapporto di hops comuni". Esso è il rapporto tra il numero di nodi in comune nelle due rotte e il numero totale di nodi nella rotta più veloce.

In questo caso è 1/2.

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.

Nel nostro caso la seconda rotta è presa.

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:

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:

Analogamente C sa che:

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.

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.