Protocolli e architetture di routing/A1

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è A1. Inoltro e instradamento.

Protocolli e architetture di routing (A. Algoritmi di instradamento)	A2. Algoritmi di instradamento

7-9 L'instradamento è il processo che determina il percorso "migliore" per un pacchetto e lo invia in uscita verso la destinazione:

• algoritmo di instradamento: è responsabile di decidere i percorsi da prendere per i pacchetti in arrivo:
  1. determina le destinazioni raggiungibili da ogni nodo;
  2. calcola i percorsi migliori (secondo certi criteri) in maniera cooperativa con gli altri nodi;
  3. memorizza delle informazioni locali in ogni nodo;
• algoritmo di inoltro: è responsabile di prendere il percorso deciso per ogni pacchetto in arrivo:
  1. effettua una ricerca nelle informazioni locali calcolate e memorizzate dall'algoritmo di instradamento;
  2. invia il pacchetto in uscita lungo il percorso migliore.

177 I protocolli di instradamento si differenziano in due classi:

• Interior Gateway Protocol (IGP): comprende i protocolli utilizzati nell'instradamento intra-dominio (ad es. RIP, IGRP, OSPF) per propagare le informazioni di instradamento all'interno di un Autonomous System;
• Exterior Gateway Protocol (EGP): comprende i protocolli utilizzati nell'instradamento inter-dominio (ad es. BGP) per propagare le informazioni di instradamento fra Autonomous System.

10 Secondo il modello OSI, l'instradamento è una funzionalità propria del livello rete, ma può essere implementato a livelli diversi:

• l'instradamento è implementato interamente a livello rete da protocolli come IP, X.25 e OSI/Decnet;
• alcuni degli algoritmi di instradamento sono implementati a livello data-link da protocolli come Frame Relay e ATM e dai bridge nelle LAN commutate.

11 I router moderni implementano due tabelle:

• Routing Information Base (RIB): è la classica tabella di instradamento che elenca tutte le destinazioni raggiungibili nella rete;
• Forwarding Information Base (FIB): è una tabella di instradamento ottimizzata per velocizzare l'inoltro dei pacchetti:
  • hardware dedicato: le TCAM sono in grado di memorizzare bit i cui valori possibili sono 0, 1 e "don't care" → la netmask è integrata nell'indirizzo di rete stesso: ogni bit nella parte aggregata ha valore "don't care";
  • cache: la FIB include solo gli ultimi indirizzi di destinazione utilizzati;
  • informazioni aggiuntive: porta di uscita, indirizzo MAC di destinazione.

13 Algoritmi di inoltro

14 Instradamento per indirizzo di rete

• Ogni nodo è identificato da un indirizzo di rete.
• Ogni pacchetto contiene l'indirizzo del nodo di destinazione.
• Ogni nodo contiene la lista degli indirizzi delle destinazioni raggiungibili con i relativi next hop.

Quando arriva un pacchetto, il nodo utilizza l'indirizzo di destinazione in esso contenuto come "chiave" nella tabella di inoltro per trovare il next hop.

Vantaggio

È un algoritmo semplice ed efficiente perché è stateless: l'inoltro di un pacchetto avviene indipendentemente dall'inoltro degli altri pacchetti, cioè il nodo una volta inoltrato un pacchetto se ne dimentica.

Svantaggio

Non è possibile la selezione di rotte diverse per la stessa destinazione in base al tipo di traffico per la qualità del servizio.

Adozione

I protocolli connectionless (come l'IP) tipicamente utilizzano questo algoritmo di inoltro.

15 Tecnica dei "percorsi colorati"

• Ogni percorso tra due nodi è identificato da un PathID ("colore").
• Ogni pacchetto contiene un'etichetta che corrisponde al PathID del percorso da seguire.
• Ogni nodo contiene la lista dei PathID con le relative porte di uscita.

Quando arriva un pacchetto, il nodo utilizza l'etichetta in esso contenuto come "chiave" nella tabella di inoltro per trovare la porta di uscita.

Vantaggio

Sono possibili molti percorsi verso una stessa destinazione → è possibile scegliere il percorso migliore in base al tipo di traffico per la qualità del servizio.

Svantaggio

Il PathID è globale:

• la "colorazione" dei percorsi deve essere coerente su tutti i nodi nella rete;
• scalabilità: il numero di percorsi possibili tra tutte le coppie di nodi nella rete è molto grande → sono necessari molti bit per codificare ogni PathID, ed è difficile trovare un identificativo che non è ancora stato utilizzato.

Label swapping

Label swapping in una rete MPLS.

18 La tabella di inoltro di ogni nodo contiene la mappatura tra le etichette delle porte in ingresso e le etichette delle porte in uscita, includendo entry di tipo:

<porta in ingresso> <etichetta in ingresso> <porta in uscita> <etichetta in uscita>

Quando arriva un pacchetto, il nodo utilizza l'etichetta in esso contenuto e la porta in ingresso come "chiave" nella tabella di inoltro per trovare la porta di uscita, e rimpiazza l'etichetta corrente del pacchetto con l'etichetta in uscita.

Vantaggi

• 17 scalabilità: il PathID del percorso da seguire non è globale, ma l'etichetta viene decisa localmente nodo per nodo, e deve essere coerente solo tra i nodi alle estremità del link:
  • le etichette sono composte da meno bit perché devono codificare meno percorsi;
  • ogni nodo deve conoscere solo le etichette dei percorsi che passano per esso → la tabella di inoltro è più piccola;
• efficienza: il label swapping è veloce rispetto ad algoritmi di inoltro come il "longest prefix matching" di IP.

19 Adozione

Il label swapping è utilizzato da:

• tecnologie di rete di derivazione telecomunicazionista (ad es. X.25, Frame Relay, ATM): il label swapping permette la qualità del servizio, una funzionalità considerata importante dal mondo degli operatori telefonici;
• 22 MPLS: nel backbone i percorsi sono in numero abbastanza limitato e piuttosto stabili poiché sono creati non end-to-end ma nella nuvola MPLS, dove la topologia della rete cambia meno di frequente e il traffico è più regolare rispetto ai margini.

Instaurazione del percorso

Quando un host vuole generare e inviare il primo pacchetto verso una destinazione, come chiede l'instaurazione di un nuovo percorso e quale etichetta deve utilizzare?

20 Instaurazione manuale

I percorsi e le relative etichette sono impostati manualmente dall'amministratore della rete.

Svantaggi

• rischio elevato di errori umani nella configurazione;
• nessun re-instradamento automatico in caso di guasti;
• non adatto per reti altamente dinamiche dove gli utenti chiedono frequentemente nuovi percorsi.

21 Instaurazione su richiesta

È richiesta una fase di segnalazione per l'instaurazione del percorso, ovvero per la preparazione delle etichette in ogni nodo, al termine della quale l'host apprende l'etichetta da utilizzare e può inviare il primo pacchetto verso la destinazione.

Vantaggi
La qualità del servizio è più semplice:

• è possibile instaurare dei percorsi diversi in base alla sorgente che ne richiede l'instaurazione (ad es. il rettore può disporre di un percorso privilegiato rispetto al ricercatore);
• è possibile includere all'interno del pacchetto di segnalazione un'informazione che specifica quanta larghezza di banda riservare per il percorso.

Svantaggi

• complessità: la segnalazione è ottenuta attraverso un'altra tecnica di inoltro (ad es. l'instradamento per indirizzo di rete) su un circuito dedicato → la complessità aumenta perché la rete deve ora gestire due tecniche di inoltro differenti;
• scalabilità: se il percorso è lungo e il numero di nodi da attraversare è elevato, la fase di segnalazione può durare troppo a lungo, soprattutto se le sessioni di comunicazione sono abbastanza brevi come nel mondo delle reti.

23 Source routing

L'host mittente scrive nel pacchetto stesso l'intero percorso che deve seguire per arrivare fino alla destinazione.

Vantaggio

I router interni alla rete sono estremamente semplici.

Svantaggio

L'host mittente deve conoscere la topologia della rete e deve interagire direttamente con gli altri host per poter calcolare i percorsi → ciò viola il paradigma secondo cui gli utenti finali devono limitarsi ad inviare i pacchetti e alla rete è affidato il compito di inoltrare i pacchetti verso le destinazioni.

Adozione

IPv4 e IPv6 prevedono un'opzione che influenza il percorso dei pacchetti.

24 Confronto

Instradamento per indirizzo di rete

• semplicità: no instaurazione, no stato
• scalabilità (inoltro): no stato "per sessione" (stateless)
• efficienza: intestazione dei pacchetti grande
• scalabilità (instradamento): tabella di instradamento molto grande
• affidabilità: difficile garantire il servizio
• multipath: non supporta più percorsi tra due entità

Label swapping

• scalabilità (instradamento): tabella di instradamento ridotta
• efficienza: intestazione dei pacchetti piccola
• garanzia di servizio: possibilità di garantire il servizio (prenotazione del percorso)
• multipath: più percorsi permessi tra due entità
• scalabilità (instaurazione): elaborazione dei pacchetti per l'instaurazione del percorso (critico con sessioni "brevi")
• scalabilità (inoltro): stato "per sessione" (necessario per la qualità del servizio)
• complessità: instaurazione del percorso (processo di instaurazione del percorso, inoltro ad-hoc dei pacchetti per l'instaurazione del percorso)

Source routing

• efficienza (router): i sistemi intermedi sono estremamente semplici
• efficienza (sorgenti): gli end system devono preoccuparsi di calcolare i percorsi

Note

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è A1. Inoltro e instradamento.

Protocolli e architetture di routing (A. Algoritmi di instradamento)	A2. Algoritmi di instradamento