Tipi di reti -...

1

Vittorio Maniezzo – Università di Bologna 10 – rete - 1/53

Livello rete:WAN, routing

Vittorio ManiezzoUniversità di Bologna


Tipi di retiLocal Area Network (LAN) - singolo edificio Metropolitan Area Network (MAN) - singola cittàWide Area network (WAN) - nazioni, continenti,

pianeta Differenze fra LAN e WANUn bridge satellitare può estendere una LAN su

distanze immense Però una LAN non può accettare un numero

arbitrario di stazioni Una WAN può scalare a lunghe distanze e molti

computer

2


Switch di pacchetti

Per accettare lunghe distanze o molti computer, la rete deve sostituire il mezzo condiviso con gli switch di pacchetti

• Ogni switch / router trasferisce un intero pacchetto da una connessione ad un'altra

• Uno switch / router é un piccolo computer con interfacce di rete, memoria e programmi specifici per le funzioni di packet switching.


Switch di pacchettiGli switch possono essere collegati per formare una WAN Una WAN non vincolata ad avere nessuna topologia regolare.Ogni switch può connettersi a uno o più altri switche a uno o più computer

3


Livello reteAffronta il problema dello spostamento dei pacchetti dalmittente al destinatario attraverso sottoreti intermedie (router).Occorre:

– Conoscere la topologia della rete– Scegliere di volta in volta il cammino migliore (routing)– Gestire il flusso dei dati e le congestioni (controllo di

flusso e congestione)– Gestire le problematiche derivanti dalla presenza di più

reti diverse (internetworking)


RoutingLa funzione principale del livello network è di instradare i pacchetti sulla subnet, facendo fare loro salti (hop) da un router ad un altro. Un algoritmo di routing è la parte del software che decide su quale linea di uscita instradare un pacchetto che è arrivato:

– in una sottorete a datagrammi l'algoritmo viene applicato da ogni router ad ogni pacchetto

– in una sottorete basata su circuiti virtuali l'algoritmo viene applicato solo nella fase di setup del circuito (Session routing)

4


Livello 3: servizi

Orientati alla connessione: gli host stabiliscono una connessione, negoziandone i parametri (qualità, costo), alla quale viene associato un identificatore ID– Questo ID viene inserito in ogni pacchetto che

verrà inviato – Comunicazione bidirezionale, i pacchetti

viaggiano, lungo il cammino assegnato alla connessione

– Il controllo di flusso è fornito attraverso alcuni dei parametri negoziati


Livello 3: servizi

Senza connessione: la sottorete è giudicata inaffidabile, gli host devono provvedere per conto proprio alla correzione degli errori e al controllo di flusso

– Il servizio offerto dal livello rete è di tipo a datagrammi

– I pacchetti viaggiano indipendentemente, contengono tutti un l'indirizzo della destinazione

5


Livello 3: serviziOrientati alla connessione:

• La sottorete stabilisce un circuito virtuale

• Tutti i router lungo tale cammino memorizzano, in una struttura dati, la linea in entrata e quale in uscita assegnate al cammino

• Quando arrivano pacchetti che contengono l'IDdel circuito virtuale, vengono instradati di conseguenza (tutti nello stesso modo)


Livello 3: serviziConnectionless:

• I router instradano ogni pacchetto decidendo ogni volta come proseguire

• I router hanno delle tabelle di instradamento (routing table) che indicano, per ogni possibile destinazione, la linea in uscita da utilizzare

• Se offre un servizio con connessione, fa credere al livello superiore che esista una connessione, ma i pacchetti viaggiano indipendentemente e sono riordinati dal livello 3 solo a destinazione, prima di essere consegnati al livello 4

6


Store and forwardL'invio di dati da un computer a un altro avviene tramite una tecnologia store-and-forward

– Ogni switch memorizza (store) ogni pacchetto in ingresso

– ... e lo inoltra (forward) a un altro switch o computer

Ogni router ha una memoria interna – può mantenere un pacchetto se la

connessione é occupata – può accodare più pacchetti per ogni

connessione


Indirizzi fisici su WANSimili a quelli su LAN

– Dati trasmessi in pacchetti (equivalenti ai frame) – Ogni pacchetto ha un formato specificato da un

header– L'header contiene gli indirizzi sorgente e destinazione

Molte WAN usano un indirizzamento gerarchico – Una parte dell'indirizzo identifica lo switch di

destinazione – L'altra parte identifica una porta dello switch

7


Instradamento next-hopOgni switch deve scegliere una connessione in

uscita per l'inoltro

• se la destinazione é un computer locale, lo switch consegna alla porta del calcolatore

• se la destinazione non é collegata in locale, lo switch inoltra su un'altra connessione (next hop) verso un altro switch

La scelta della connessione é basata sull'indirizzo nel pacchetto


Scelta del passo successivoLo switch non mantiene una informazione completa di tutte le possibili destinazioni, ma solo delle stazioni direttamente connesse

Per ogni pacchetto lo switch scorre una tabella di destinazioni invia su una connessione per il passo successivo.

8


Indipendenza dalla sorgenteIl passo successivo verso la destinazione non dipende dalla sorgente del pacchetto (indipendenza dalla sorgente)

Proprietà alla base di un routing veloce ed efficiente

Gli switch non richiedono informazioni complete, bastano le connessioni dirette

– riduzione dell'informazione totale gestita – aumento della robustezza dinamica: la rete può

continuare a funzionare anche a fronte di modifiche topologiche senza notificarle all'intera rete.


Indirizzamento gerarchico e routingL'instradamento dei pacchetti é detto routingL'informazione rilevante é mantenuta in tabelle di routingMolti cammini possono condividere lo stesso primo passo

Tutte le destinazioni collegate ad uno stesso router hanno lo stesso passo successivo Le tabelle di routing possono essere compresse:

9


Modellizzazione di una WANGrafo della rete: • I nodi corrispondono ai router • Gli archi corrispondono a connessioni dirette fra

router Si ignorano i calcolatori collegati


Calcolo di un cammino nel grafoRappresentabili con tabelle di routing:

Si possono usare algoritmi di teoria dei grafi per identificare i cammini

10


Ridondanza rappresentativa

Ad esempio, viene duplicata informazione al nodo 1:

Il router 1 ha un unica connessione in uscita, tutto il traffico deve passare di lì.


Default routeSi possono collassare tutte le righe di una tabella di routing in una default routeSe una destinazione non ha una specifica riga nella tabella, si usa la default route:

L'uso della default route é opzionale (v. nodo 3)

11


Routing, requisitiRequisiti di un algoritmo di routing:• Correttezza• Semplicità• Robustezza (deve funzionare anche in caso di

cadute di linee e/o router e di riconfigurazionidella topologia)

• Stabilità• Equità• Ottimalità


Algoritmi di routingObiettivi (che possono essere contrastanti):

– Minimizzare i tempi di inoltro dei pacchetti– Massimizzare l'utilizzo delle linee

Scalabilità degli algoritmi– Complessità: non lineare nel numero dei nodi – Stabilità: convergenza problematica con reti

complesse– Equità: non sempre facile garantire uguali condizioni

ai nodiOttimalità: due metriche principali

– Hops: numero di sistemi intermedi attraversati– Costo: sommatoria dei costi delle singole linee

attraversate (inversamente proporzionali a velocità)

12


Algoritmi di routing

Gli algoritmi di routing si dividono in:

• Algoritmi non adattivi (static routing): le decisioni di routing sono prese in anticipo, all'avvio della rete, e sono comunicate ai router che poi si attengono sempre a quelle

• Algoritmi adattivi (dynamic routing): le decisioni di routing sono riformulate molto spesso in base allo stato della rete

– sulla base del traffico

– della topologia della rete

– altre informazioni


Routing, classificazioneGli algoritmi adattivi differiscono fra loro per:• Come ricevono le informazioni

– Localmente– Dai router adiacenti– Da tutti i router

• Quanto spesso rivedono le decisioni– A intervalli di tempo prefissati– Quando il carico cambia– Quando la topologia cambia

• Quale metrica di valutazione adottano– Distanza– Numero di hop– Tempo di transito stimato

13


Routing, classificazioneAlgoritmi (o politiche)• isolate

– routing calcolato con sole informazioni locali, indipendentemente dal resto (stato degli altri nodi e stato della rete)

• distribuite– i nodi cooperano e comunicano frequentemente il

proprio stato e quello della rete• centralizzate

– un centro di controllo conosce lo stato globale e calcola il cammino ottimo per ogni coppia (mittente,destinatario) e dirama le tabelle

• miste– combinazione di politiche isolate e centralizzate


Definizione delle tabelle di routingLe tabelle possono essere costruite:

– Manualmente - file di inizializzazione– Dinamicamente - runtime

Identificazione delle informazioni:

– Routing statico - boot time

– Routing dinamico - permette aggiornamenti automatici via SW

Il routing statico é più semplice, ma non può gestire modifiche della topologia della rete

Il routing dinamico richiede protocolli specifici, può gestire modifiche della rete

14


Tipi di algoritmi di routingNon adattivi (statici, deterministici): i criteri di instradamentorimangono costanti nel tempo

– Fixed Directory Routing– Flooding e Selective Flooding

Adattivi (dinamici, non deterministici): tabelle di instradamento calcolate sulla base della topologia (variabile) della rete, dello stato dei collegamenti e del loro carico

– Routing Centralizzato– Routing Isolato– Routing Distribuito


Fixed directory routingTabelle di instradamento costruite "a mano"

Riconfigurazioni di tabelle gestite "a mano" possibilmente in anticipo rispetto ai guasti

MULTIMEDIA Port_03

MULTIMEDIA Port_003 Port_005

BIOMETRIA Port_15

INFO Port_08

BIOMETRIA Port_015

INFO Port_008 Port_003

15


Routing staticoAlgoritmi che definiscono le regole di instradamento a priori e senza informazione di stato• shortest path routing• flooding• flow-based routing


Routing centralizzato

RCC (Routing Control Center) riceve info sullo stato della rete da ciascun nodo, calcola le tabelle e le distribuisce a tutti i nodoOttimizza prestazioni, ma in caso di guasto si possono generare loop dovuti a info parzialiCarico sulla rete elevato in prossimità di RCC

ROUTING ISOLATO

Ogni nodo instrada senza consultare altri nodi

16


Cammini minimi• Routing statico basato sulla rappresentazione

della rete mediante grafo • Si può utilizzare Dijkstra per calcolare il cammino

minimo da ogni nodo a ogni altro nodo • Si estrae l'informazione del passo successivo dai

cammini calcolati • Si definiscono in accordo le tabelle di routing


Routing su cammini minimiUn host di gestione della rete mantiene un grafo che rappresenta la sottorete:

– I nodi rappresentano i router– Gli archi rappresentano le linee punto-punto

All'avvio della rete (o quando ci sono variazioni della topologia) l'algoritmo:

– Applica al grafo un algoritmo per il calcolo del cammino minimo fra ogni coppia di nodi, ad esempio Dijkstra;

– Invia tali informazioni a tutti i routerMisure da minimizzare:

– Numero di hop, cioè di archi, da attraversare;– Lunghezza dei collegamenti;– Tempo medio di accodamento e trasmissione;– Una combinazione di lunghezza, banda trasmissiva,

traffico medio, o altro

17


Dijkstra (1/2)#define MAX_NODES 1024 /* max num of nodes */#define INF 1OOOOOOOOOint n, dist[MAX_NODES][MAX_NODES];/* dist[i][j] is distance from i to j */ void shortest-path(int s,int t, int path[]){ struct state /* the path being worked on */

{ int predecessor; /* previous node */int length; /* length from source to this node */enum {permanent, tentative} label; /* label state */

} state[MAX_NODES]:int i,k,min,struct state *p;

for (p=&state[0]; p < &state[n]; p++) /* initialize state */{ p->predecessor=-1;

p->length = INF;p->label = tentative;

}state[t].length =0; state[t].label = permanent;k=t, /* k is the initial working node */


Dijkstra (2/2)do /* is there a better path from k? */{ for(i=0;i<n; i++) /* this graph has n nodes */

if (dist[k][i] != O && state[i].label == tentative) if (state[k].length + dist[k][i] < state[i].length) { state[i].predecessor=k;

state[i].length = state[k].lengtlh + dist[k][i];}

/* Find the tentatively labeled node with the smallest label */k = 0; min = INF;for (i=0; i < n; i++)if (state[i].label == tentative && state[i].length< min) { min=state[i].length;

k=i;}state[k).label = permanent,

} while(k!=s),

/* Copy the path into the output array */i=O;k=s;do {path[i++] = k; k=state[k].predecessor;) while (k>=O);

}

18


FloodingPacchetti ritrasmessi su tutte le porte tranne quella di provenienza

– Carichi bassi: strategia accettabile (o addirittura buona)

– Miglioramenti: time-to-live, packet drop al secondo passaggio (i nodi devono tenere un log del traffico)

Tecniche per limitare il traffico generato:

Inserire in ogni pacchetto un contatore che viene decrementato ad ogni hop. Se il contatore arriva a zero, il pacchetto viene scartato

Inserire la coppia (source router ID, sequence number) in ogni pacchetto. Ogni router esamina tali informazioni e ne tiene traccia, e se le vede per la seconda volta scarta il pacchetto


Selective flooding

Pacchetti ritrasmessi su linee selezionate– Random Walk: viene scelta una porta a caso– Hot Potato: viene scelta la porta con la coda

più corta – Selective flooding: i pacchetti vengono

duplicati solo sulle linee che vanno all'incirca nella giusta direzione (tabelle)

19


Routing basato sul flussoE' basato sull'idea di calcolare in anticipo il traffico atteso su ogni lineaDa questi calcoli derivare una stima del ritardo medio atteso per ciascuna lineaLe informazioni necessarie per poterlo applicare sano:

– La topologia della rete– La matrice delle quantità di traffico T(i,j) stimate Ira ogni coppia

(i,j) di router– Le capacita (in bps) delle linee point to point

Vengono fatte Ie assunzioni– II traffico e stabile nel tempo e nota in anticipo– Il ritardo è proporzionale al traffico: iI ritardo su ciascuna linea

aumenta all'aumentare del traffico sulla linea e diminuisce all'aumentare della velocità della linea secondo Ie leggi della teoria delle code

Ritardo medio della rete: somma pesata dei ritardi delle singole lineePeso della linea prop. al trafficopeso della linea = traffico sulla linea / traffico totale sulla rete.


Routing basato sul flussoAlgoritmo di routing basato sui flusso• Si sceglie un algoritmo di routing• Sulla base di tale algoritmo si determinano i percorsi che

verranno seguiti per il collegamento fra ogni coppia di router

• Si calcola il traffico che incide su ogni linea (uguale alla somma di tutti i T(i,j) instradati su quella linea)

• Si calcola il ritardo di ogni linea• Si calcola il ritardo medio della rete• Si ripete il procedimento con vari algoritmi di routing,

scegliendo alla fine quello che minimizza il ritardo medio dell'intera rete

20


Routing distribuitoTabelle calcolate da ogni router dialogando con gli altri router e con le stazioni

Algoritmi Vector - Distance

– Quando un nodo modifica le proprie tabelle (distance vector), ne invia una copia aggiornata ai nodi adiacenti, che la fondono conquelle provenienti dagli altri nodi, etc.

– Convergenza: O(Cn), ma O(n2) e O(n3) nel caso tipico

Algoritmi Link State

– Ogni router esprora il proprio intorno e informa gli altri, che si costruiscono una mappa completa della rete con l'algoritmo di Dijkstra (Shortest Path First)

– Complessità: E∗log N (E=numero link, N=numero nodi)

– Esegue in 150 ms su CPU a 1 MIPS con 600 nodi e 300 link

– Base del protocollo OSPF, abbastanza usato per TCP/IP


Definizione dinamica dei cammini

La topologia della rete può cambiare dinamicamente

– nuovi router aggiunti – connessioni che saltano – i costi delle connessioni possono cambiare

I router devono poter aggiornare le tabelle di routing considerando le variazioni topologiche

21


Calcolo distribuito dei cammini• Si scambia fra nodi l'informazione sulla

topologia della rete

• Si aggiorna periodicamente l'informazione

• Ogni nodo ricalcola il cammino minimo e i passi successivi

• Si modificano in accordo le tabelle di routing


Algoritmo vector-distanceL'informazione locale é la tabella di routing e la distanza da ogni router

I router inviano periodicamente in broadcastl'informazione sulla topologia locale

Gli altri router aggiornano la tabella di routing sulla base delle informazioni ricevute

22


Algoritmo vector-distanceIn ogni router mantiene una tabella (vector) con, per ogni router:

– La distanza (numero di hop, ritardo, ecc.) che lo separa dal router in oggetto

– La linea in uscita da usare per arrivarciPer i suoi vicini immediati il router stima direttamente la distanza dei collegamenti corrispondenti, mandando speciali pacchetti ECHO e misurando quanto tempo ci mette la risposta a tornareA intervalli regolari ogni router manda la sua tabella a tutti i vicini, e riceve quelle dei vicini


Algoritmo vector-distanceAlgoritmo: Aspetta il prossimo messaggio di

aggiornamentoPer ogni elemento del messaggio ripeti

se l'elemento ha un cammino più corto verso la destinazione

inserisci la sorgente come passo successivo verso la destinazioneMemorizza la distanza dal nodo successivo alla destinazione più la distanza dal router al nodo successivo

23


Algoritmo vector-distanceQuando un router riceve nuove informazioni, calcola una nuova tabella scegliendo, tra tutte, la concatenazione migliore tra

– distanza tra il router stesso ad un suo vicino immediato (viene dalla misurazione diretta)

– distanza tra quel vicino immediato ad il router remoto di destinazione (viene dalla tabella ricevuta dal vicino immediato)

Algoritmo buono ma molto lento nell'adattamento (topologia non nota) Algoritmo di routing di ARPANETUsato anche in Internet col nome di RIP (Routing Internet Protocol)


Link-state routingOgni nodo mantiene informazioni sullo stato dei collegamenti con i vicini immediati (misurando il ritardo di ogni linea) e distribuisce tali informazioni a tuttiSulla base di tali informazioni, ogni nodo ricostruisce la topologia completa della rete e calcola il cammino minimo fra se e tutti gli altriI passi da seguire sano:

– Scoprire i vicini e identificarli– Misurare il costo (ritardo o altro) delle relative linee– Costruire un pacchetto con tali informazioni e mandarlo a tutti gli

altri router– A seguito della ricezione degli analoghi pacchetti dagli altri router,

ricostruire la topologia dell'intera rete– Calcolare il cammino più breve a tutti gli altri router

24


Link-state routingSi costruisce un pacchetto con:

– Identità del mittente

– Numero di sequenza del pacchetto

– Età del pacchetto

– Lista dei vicini con i relativi ritardi

La costruzione e l'invio dei pacchetti si verifica a intervalli regolari o quando accade un evento significativo

Il link state routing è molto usato in Internet: OSPF (Open Shortest Path First) è basato su questo principio ed èl'algoritmo più utilizzato


Routing gerarchicoLa rete viene divisa in zone (regioni):All'interno di una regione ogni router (detti router interni) applica un algoritmo di routing verso tutti gli altri router della regione Quando un router interno deve spedire un pacchetto a un router di un'altra regione lo invia ad un particolare router della propria regione, detto router di confine.Il router di confine conosce gli altri router di confine e conosce a quale inviare il pacchetto perché arrivi alla regione di destinazione Due livelli di routing:

– un primo livello di routing all'interno di ogni regione– un secondo livello di routing fra tutti i router di confine

25


Routing gerarchicoI router interni mantengono delle loro tabelle di routing

– Una riga per ogni altro router interno (linea) – Una riga per ogni altra regione (router di

confine)I router di confine mantengono una riga per ogni altra regione, con l'indicazione del prossimo router di confine da contattare e della linea da usare per raggiungerlo


Routing gerarchico

26


CongestioniSe l'input a un qualche collegamento della rete eccede la sua capacità, i pacchetti verranno accodati sulla connessione di quel link

Prima o poi i pacchetti verranno scartati e quindi ritrasmessi, peggiorando la situazioneLa rete si avvia ad un collassoIl problema é simile (non uguale) al data overrun


Controllo della congestioneLa congestione in un router pub derivare da diversi fattori• Buffer a capacita limitata nel router• Processore troppo lento nel router• Linea di trasmissione troppo lenta, che causa

congestione della coda nel router di partenza

27


Controllo della congestioneIl controllo della congestione è un problema globale di tutta la rete, edè diverso dal problema del controllo di flussoDue approcci al problema della congestione

– Open loop (senza retroazione): cerca di prevenire la congestione, ma se si verifica non effettua azioni correttive

– Closed loop (con retroazione): cerca di evitare la congestione, controllando lo stato della rete e intraprendendo le azioni opportune quando necessario

Tipi di reti -...

Documents

Transcript of Tipi di reti -...