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:

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

• BCDE 65 (AB=15, BC=15, CD=15, DE=15, EH=5)
• BCFE 85 (AB=15, BC=15, CF=25, FE=25, EH=5)
• G 100 (AG=50, GH=50)
• GFE 120 (AG=50, GF=40, FE=25, EH=5)

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:

• AB=15

• BCDEH=50 => ABCDEH=65

• BCFEH=70 => ABCFEH=85

Analogamente C sa che:

• CD=15

• DEH=20 => CDEH=35

• CF=25

• FEH=30 => CFEH=55

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.

• Nota: Oltre alle variazioni nel costo di una rotta, un ETP può trasportare altre informazioni da divulgare, come il cambio del fingerprint del g-nodo o del numero di nodi contenuti.

• Nota: Qui A potrebbe decidere che la variazione è di poca importanza (ad esempio se il costo della rotta cambia poco in percentuale o se il numero di nodi nel g-nodo cambia poco in percentuale) e, per mantenere basso il traffico delle informazioni, non aggiornare questi dati nella sua mappa. Questa decisione però è vietata se ci sono informazioni cruciali come il cambio di fingerprint del g-nodo.

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.