Classificazione degli algoritmi di Routing
In base all’attributo “posto”:
• Source Routing - La sorgente specifica per ogni messaggio tutte le decisioni di routing intermedie ( i nodi intermedi non necessitano di tabelle di routing).
• Incremental Routing - La sorgente specifica solo la destinazione e lascia ai nodi intermedi la scelta del percorso (anche chiamato Hop-by-Hop routing).
• Hybrid Routing - La sorgente specifica solo alcuni punti intermedi critici e lascia ai nodi le altre scelte.
• Fixed Routing - le tabelle di routing sono calcolate una sola volta (anche chiamato Deterministic Routing).
• Dynamic Routing - le tabelle di routing sono aggiornate spesso riflettendo anche variazioni a breve dell’ambiente (anche chiamato Adaptive Routing:
-Isolated Routing -Centralized Routing -Distribuited Routing In base all’attributo “tempo”:
Shortest Path routing
• Ogni nodo del grafo è etichettato con il costo del percorso dal nodo sorgente, lungo il migliore percorso noto.
• Il costopuò essere rappresentato da uno o più parametri (distanza, larghezza di banda, traffico medio, lunghezza media delle code, ecc.)
• Le etichette sono inizialmente temporaneee vengono modificate man mano che si trovano percorsi migliori.
• Quando l’etichetta rappresenta il percorso più breve dalla sorgente alla destinazione, diventa permanente.
FLOODING
Ogni pacchetto in arrivo è spedito su tutte le linee d’uscita, eccetto quella d’arrivo.
Problema: creazione di copie multiple del pacchetto.
La crescita può essere limitata:
- associando ad ogni pacchetto un contatore di salti effettuati.
- tenendo traccia dei pacchetti già inoltrati
- inviando i pacchetti solo sulle linee che vanno verso la direzione giusta(flooding selettivo).
Il Flooding è robusto e garantisce la consegna del pacchetto se esiste almeno un percorso valido.
Il Flooding può essere usato per:
•applicazioni militari(robustezza)
•aggiornamento concorrente di database distribuiti(broadcast)
•come riferimento rispetto ad altre tecniche(velocità)
FLOW - BASED ROUTING
Può essere applicato quando il traffico medio fra 2 nodi è relativamente costante e noto in anticipo.
Occorre conoscere: -la topologia della rete -la matrice del traffico
-la matrice della larghezza di banda
Capacità delle linee (Kbps)
9 4 1 7 4
AB ABC ABFD AE AEF
9 8 3 2 4
BA BC BFD BFE BF
4 8 3 3 2
CBA CB CD CE CEF
1 3 3 3 4
DFBA DFB DC DCE DF
7 2 3 3 5
EA EFB EC ECD EF
4 4 2 4 5
FEA FB FEC FD FE
A B C D E F
Source
A B C D E F Destination
Matrice di routing, con il traffico nei singoli percorsi, calcolata con l’algoritmo di routing da testare
C, (kbps )
C, (pkts/sec)
1 AB 14 20 25 91
2 BC 12 20 25 77
3 CD 6 10 12,5 154
4 AE 11 20 25 71
5 EF 13 50 62,5 20
6 FD 8 10 12,5 222
7 BF 10 20 25 67
8 EC 8 20 25 59
i Line (pkts/sec ) T,
(ms)
µ
FLOW - BASED ROUTING
Analisi della rete con pacchetti mediamente di 800 bits
Con la teoria delle code è possibile calcolare il ritardo medio sulle singole linee e quindi il ritardo medio di tutti i pacchetti.
Si provano vari algoritmi di Routing fino a determinare quello che offre il ritardo medio più breve
T= ---1
µC− λ I ritardi dei singoli salti permettono di calcolare i ritardi in ogni percorso.
Il ritardo medio per l’intera rete è la somma pesata dei ritardi dei singoli tratti(il peso è la frazione del traffico totale nella linea).
Distance vector routing
• Algoritmo di tipo dinamico. Ogni IMP scambia periodicamente informazioni di routing con ciascuno dei nodi adiacenti.
• Ogni IMP conosce la propria “distanza” dagli IMP adiacenti.
• Ogni IMP calcola la propria “distanza” con tutti gli altri IMP sfruttando l’informazione attenuta dagli IMP adiacenti.
• La “distanza” più breve seleziona l’IMP adiacente a cui inviare un certo pacchetto.
A A I H K
A 0 24 20 21 8 A
B 12 36 31 28 20 A
C 25 18 19 36 28 I
D 40 27 8 24 20 H
E 14 7 30 22 17 I
F G H I J K
L 29 33 9 9 15 K
Tabelle spedite da IMP adiacenti a J
Nuovo valore di ritardo da IMP J attraverso L’uscita
Ritardi verso i nodi adiacenti
A B C D
E F G H
I J K L
Distance vector routing
•L’algoritmo converge velocemente verso la soluzione migliore ma reagisce molto lentamente a situazioni negative,come ad esempio la caduta di un router.
•Reagire lentamente vuol dire che l’algoritmo necessita di molti scambi, i quali avvengono periodicamente, prima di realizzare delle tabelle di routing corrette per ogni nodo (problema del conteggio all’infinito).
Le soluzioni trovate a questo problema sono parzialmente soddisfacent1, es. Algoritmo Split Horizon
Convergenza verso la soluzione ottima
Reazione in conseguenza di un guasto nel router A: il costo del percorso verso A
cresce lentamente
RIP: Routing Information Protocol
• Protocollo distribuito basato sull’algoritmo Distance Vector Routing (Bellman-Ford Shortest Path)
• Inizialmente usato per IP
• Le macchine presenti in rete sono divise in:
– attive:calcolano e diffondono i percorsi di routing (Routers)
– passive:aggiornano le proprie tabelle in base ai dati ricevuti (H osts)
• Utilizza una metrica basata sul numero di salti. Per evitare
oscillazioni fra percorsi equivalenti un percorso può essere sostituito solo da uno con costo strettamente minore.
• Ogni percorso deve essere convalidato entro un time-out (180 Sec).
Problemi:
• non scopre eventuali loop di routing.
• per evitare instabilità limita la max distanza ammissibile(di solito 16)
• conteggio all’infinito.
MULTIPATH ROUTING (Bifurcated Routing)
• Costituisce una generalizzazione di altre tecniche di routing.
• Può essere applicato sia su reti Datagramche a Circuito Virtuale.
• Ogni IMP possiede una tabella di Routing in cui per ogni destinazione sono previsti diversi percorsi (più o meno ottimali).
• La scelta è fatta generando un numero casuale.
• E’ possibile spedire traffico di tipo diverso (con stessa destinazione ) lungo percorsi diversi.
• Aumenta l’affidabilità. A A 0,63 I 0,21 H 0,16
B A 0,46 H 0,31 I 0,23 C A 0,34 I 0,33 H 0,33 D H 0,5 A 0,25 I 0,25
E A 0,4 I 0,4 H 0,2
F A 0,34 H 0,33 I 0,33 G H 0,46 A 0,31 K 0,23 H H 0,63 K 0,21 A 0,16 I I 0,65 A 0,22 H 0,13 - -
K K 0,67 H 0,22 A 0,11 L K 0,42 H 0,42 A 0,16
I
F
G E
B C D
A
H
K L
J Tabella di routing per il nodo J
Link State Routing
• Ha sostituito il distance vector routing che non teneva conto della diversa larghezza di banda delle linee e convergeva lentamente.
• Ogni router deve:
– scoprire i propri vicini ed i loro indirizzi di rete.
– Misurare il ritardo ( o il costo) per ognuno dei suoi vicini(pacchetti ECHO) – costruire un pacchetto contenente tutte le informazioni acquisite
– spedire questo pacchetto a tutti i router(selective flooding, numeri di sequenza a 32 bit, età del pacchetto)
– calcolare il cammino minimo per ogni altro router(algoritmo di Dijkstra).
OSPF: Open Shortest Path First
• Internet è divisa in un insieme di sistemi autonomi (AS), ognuno dei quali usa un protocollo di routing, Interior Gateway Protocol, (IGP) per la comunicazione tra i router.
• OSPF è il nuovo IGPche ha sostituito RIP, nelle grandi reti.
• OSPF è più stabile di RIPpoiché i routers reagiscono tutti contemporaneamente ai cambiamenti della rete.
• Ogni router OSPF mantiene un identico data baseche descrive la topologia del sistema.
• E’ uno standard aperto, le cui specifiche sono di pubblico dominio.
• Possono essere specificati diversi tipi di servizi, con percorsi diversi.
• Gestisce il bilanciamento del caricofra percorsi equivalenti.
• Prevede la partizione in aree delle reti di grandi dimensione, per una più facile gestione.
Tutti gli scambi devono essere autenticati per sicurezza
.OSPF
• OSPF gestisce tre tipi di connessione:
-connessioni punto-punto tra due router.
-reti multiaccesso con broadcasting -reti multiaccesso senza broadcasting.
I messaggi possono essere di cinque tipi 1)Hello
2)Aggiornamento(Link state update) 3)Link state ack
4)Descrizione Database 5)Richiesta(Link state request
)
• L’algoritmo usato per il calcolo delle tabelle è quello di Dijkstra.
CENTRALIZED ROUTING
Vantaggio: visione completa della rete==> Scelta perfetta Svantaggi: -Lunghi tempi di calcolo
-Vulnerabilità dell’RCC( Routing Control Center)
-Le tabelle di routing sono consegnate con ritardi diversi ai vari IMP
-Concentrazione del traffico vicino l’RCC Adatto a reti dalle caratteristiche quasi statiche
RCC
ISOLATED ROUTING (Hot potato)
In ogni IMP il pacchetto è inserito sulla coda più corta.
Può essere usato insieme ad un routing statico.
Carico leggero ==> Routing statico
Linea scelta staticamente sovraccarica => Hot potato
H I K
A
?
BACKWARD LEARNING
• Ogni pacchetto contiene la sorgente ed il numero di IMP attraversati.
• Non può registrare gli eventi negativi verificati nella rete
==> Reset periodico delle tabelle di Routing
ISOLATED ROUTING (Delta Routing - 1976)
• Ogni IMP spedisce periodicamente pacchetti all’RCC.
• L’RCC spedisce ad ogni IMP la tabella di routing con l’elenco dei path equivalenti (a meno di un delta).
• Ogni IMP può scegliere fra i vari path equivalenti.
Approccio ibrido centralizzato - isolato
•Delta --> 0 ==> Routing centralizzato
•Delta --> ==> Routing isolato
FLOODING
Ogni pacchetto in arrivo è spedito in tutte le direzioni (creazione di duplicati).
La crescita è limitata associando al pacchetto un contatore di IMP attraversati
• applicazioni militari
• aggiornamento concorrente di database distribuiti
• usabile come riferimento rispetto ad altre tecniche
BROADCAST ROUTING
Utile per : scheduling
distribuzione di tabelle di routing
• L’IMP sorgente spedisce un pacchetto ad ogni destinazione.
• Flooding
• Multidestination routing: ogni pacchetto contiene gli indirizzi di tutte le destinazioni.
Ad ogni IMP il pacchetto viene duplicato in tutte le uscite utili (suddivisione degli indirizzi)
• Spanning Tree: ogni IMP copia il pacchetto in arrivo su tutti i rami dello Spanning tree eccetto quello da cui è arrivato
REVERSE PATH FORWARDING
Se il pacchetto arriva ad un IMP da una linea che corrisponde a un percorso ottimo verso il nodo sorgente, duplica il pacchetto su tutte le altre linee; altrimenti lo scarta.
•Efficiente
•Non ha bisogno di conoscere lo Spanning tree
•Non introduce richiede l’overhead della lista di destinazione
•Non richiede meccanismi di blocco( come nel Flooding)
B A
C D
G E
H L
O I
J F
K N
A
M
B C
D
G E
H L
O I
J F
K
N
M
I
F H J N
A D
C B
E K
L
G O M
E G A M D N K
O
HIERARCHICAL ROUTING
Utile in reti con elevato numero di IMP.
Gli IMP sono raggruppati in Regioni.
Ogni IMP conosce i dettagli solo della propria Regione.
Il numero ottimale di livelli per N IMP è : Ln N (Kleinrock 1979)
--- ---
1B 1
1C 1
1B 2
1B 3
1B 3
1B 4
1C 3
1C 2
1C 3
1C 4
1C 4
1C 4
1C 5
1B 5
1C 6
1A 1B 1C 2A 2B 2C 2D 3A 3B 4A 4B 4C 5A 5B 5C 5D
Dest. Line Hops Full table for 1A
--- ---
1B 1
1C 1
1B 2
1C 2
1C 3
1C 4
1A 1B 1C 2 3 4 5
Dest. Line Hops Hierarchical table for 1A
5C 2D
4B 4C 4A 3B
5E 5A
5D 5B 3A
1B 1A 1C
2C 2B 2A Regione 1 Regione 2
Regione 3 Regione 5
Algoritmi di controllo della congestione
• Congestione: situazione in cui l’eccessivo numero di pacchetti nella rete porta ad un degrado delle prestazioni.
Possibili cause
• Se il traffico cresce troppo, i routers cominciano a perdere pacchetti.
• Se più flussi in ingresso, richiedono la stessa uscita, verranno accodati.
La memoria può essere un problema.
• Processori lentipossono peggiorare la situazione.
• Le linee lentepossono essere causa di congestione.
• Il problema principale è un cattivo assortimento delle varie partidi un sistema (sbilanciamento)
•
La congestione si autoalimenta e tende a peggiorare.
• Differenza fra controllo della congestionee controllo di flusso.
Principi Generali della Congestione
• Le soluzioni al problema della congestione possono essere a ciclo aperto ed a ciclo chiuso.
• Soluzioni a ciclo aperto: evitano il problema con una buona progettazione prendendo decisioni indipendentemente dallo stato della rete (algoritmi che agiscono dal lato della sorgente / dal lato della destinazione).
• Le soluzioni a ciclo chiusoutilizzano il concetto di Feedback (implicito/esplicito). Occorre:
- Monitorare il sistema per rilevare la congestione(percentuale di pacchetti scartati, lunghezza media nelle code, ritardo medio, pacchetti che vanno in timeout, ecc.)
- Trasferire le informazioni sullo stato della reteai sistemi che risolvono le congestione (pacchetti ad hoc, un campo congestione in ogni pacchetto trasferito, uso di pacchetti sonda, ecc.).
- Modificare il funzionamento del sistema per correggere il problema.
La scala temporale deve essere regolata attentamente(oscillazioni/
CONTROLLO ISORITMICO
•Mantiene costante il numero di pacchetti nella rete .
•Un router puo' immettere un nuovo pacchetto nella rete dopo aver acquisito un apposito token (Permit). Quando il pacchetto arriva a destinazione libera il token.
•Il numero di pacchetti nella rete e' non superiore a quello dei token.
•Non garantisce dalla congestione nel singolo IMP .I token dovrebbero essere distribuiti uniformemente nella rete.
•Se un token viene distrutto non e' facile rigenerarlo poiche' non e' possibile conoscerne il numero complessivo.
Leacky Bucket Algorithm
• E’ un algoritmo di normalizzazione del traffico.
• Trasforma un flusso disuguale in ingresso, in un flusso costante in uscita.
• Se un pacchetto arriva quando il secchio (la coda) è pieno, viene scartato.
• E’ un sistema a coda per singolo server con tempo di servizio costante.
• E’ un sistema rigido: la velocità di trasmissione è indipendente dai picchi di traffico.
L’acqua fuoriesce a ritmo costante Sorgente
Acqua Secchio
bucato
Token Bucket Algorithm
• Offre una maggiore flessibilità del Leaky bucket, permettendo di aumentare il Throughput nei picchi di traffico in ingresso.
• Il secchio bucato contiene gettoni che vengono generati ogni ∆T sec
• Per ogni pacchetto trasmesso viene eliminato un token.
• I token possono essere risparmiati in condizioni di basso carico dell’host, e usati quando servono.
• L’algoritmo elimina i token in eccesso quando il secchio è pieno ma non scarta mai i pacchetti.
Viene aggiunto un token ogni ∆T
II secchio contiene i token
Host Host
RETE RETE
Va usato con prudenza con i router, nei quali, imporre di limitare il traffico trasmesso, può essere molto pericoloso
Controllo della congestione nei circuiti virtuali
• Controllare le ammissioni:non vengono creati nuovi circuiti virtuali finchè la congestione non è risolta.
• Consentire nuovi circuiti virtuali, ma instradarli evitando le aree congestionate.
• Negoziare un accordo fra gli Host e la rete all’atto della creazione di un circuito. La rete riserverà delle risorse (Buffers) lungo il percorso al momento di stabilire il circuito. Tende a sprecare risorse.
congestione
congestione
Circuito virtuale
Chocke Packets
• I meccanismi basati sul controllo di flusso non forniscono buoni risultati poiche' sono tarati su valori medi del traffico e non tengono conto dei picchi.
• Ad ogni uscita dell'IMP e' associata una variabile u di utilizzazione della banda.
• Se u>Soglia_prefissata, viene inviato alla sorgente un Chocke Packet.
• Alla ricezione del Chocke packet, la sorgente riduce il proprio traffico per un certo tempo T
• Se dopo T la sorgente riceve altri Chocke packets, riduce ulteriormente il flusso, altrimenti lo aumenta.
• E’ un approccio adatto sia ai circuiti virtuali, che alle reti datagram.
Caduta di carico (load shedding)
• E’ un approccio basato sulla eliminazione dei pacchetti.
• L’insieme dei pacchetti da scartare dipende dall’applicazione in esecuzione.
• Per un file transfer conviene mantenere i pacchetti più vecchi (wine policy).
• Per dati multimediali conviene scartare i pacchetti più vecchi (milk policy)mantenendo i più recenti.
In assenza di Buffer disponibili in un router, nel caso di:
• Datagram - il pacchetto e' eliminato
• Circuito virtuale - il pacchetto e' eliminato ma ne resta una copia nell'IMP precedente.
• E’ utile allocare almeno un Buffer per ogni linea d'ingresso in modo da verificare se il pacchetto in ingresso contiene un ack. Cio' permette di liberare un Buffer d'uscita.
Eliminare i pacchetti comporta uno spreco di banda che
in alcuni casi puo’ peggiorare la congestione.
INTERNETWORKING
• Internet: Struttura formata dall’unione di più reti, in gran parte differenti.
Problema:
• Molte reti esistevano già prima della messa a punto del modello OSI.
• Le reti locali spesso non sono OSI.
• L’evoluzione tecnologica porta allo sviluppo di nuovi protocolli non OSI.
Sono possibili varie tipologie di interconnessione:
• LAN - LAN
• LAN - WAN
• WAN - WAN
• LAN - WAN - LAN
Dispositivi di interconnessione fra reti
• Il nome dei dispositivi di interconnessione fra reti dipende dal livello al quale opera:
• Livello 1: Repeaters - amplificano e rigenerano segnali deboli. Sono utilizzati nei cablaggi lunghi.
• Livello 2: Bridges - sono dispositivi di tipo store and forward. Verificano la struttura della frame ed in alcuni casi la modificano.
• Livello 3: Routers multiprotocollo- interconnettono reti, spesso con protocolli diversi, e dopo aver esaminato alcuni campi del pacchetto lo inoltrano sull’uscita più adatta.
• Livello 4: Gateway di trasporto- realizzano una connessione fra due reti nel livello di trasporto.
• Oltre il livello 4: Gateway di applicazione- connettono due parti di un’applicazione nel livello application. E’ richiesto se le due applicazioni sono realizzate con protocolli diversi (es. collegamento fra una
macchina che usa la posta elettronica ISO MOTISed una che usa la posta elettronica di internet.
Gateways
Uno dei problemi principali dei Gateways è che essi sono chiamati a supportare il routing fra sottoreti gestite da organizzazioni diverse o che appartengono a paesi diversi
L’approccio utilizzato dal CCITT è quello di separare il Gatewayin due half-gatewaysche comunicano attraverso un opportuno protocollo (viene utilizzato il protocollo X75)
Gateway
Net 1 to internet
Internet to net 1
Net 2 to internet
Internet to net 2 B
u f f e r
Subnet 1
Subnet 2
Net 1 to internet
Internet to net 1
Subnet 1
Subnet 2
Net 2 to internet
Internet to net 2
Macchina gestita insieme dalle due organizzazioni
Macchina gestita dalla sottorete 1
Macchina gestita dalla sottorete 2 Communication line
Connection-oriented Gateways
• La connessione fra “Source” e “Destination” viene costruita come una sequenza di circuiti virtuali attraverso le varie reti.
•Ogni gateway memorizza il circuito virtuale passante per esso e lo prosegue nel gateway successivo finchè la destinazione viene raggiunta.
•La singola sottorete al suo interno potrebbe usare un approccio di tipo datagram, ma il gateway di entrata e quello di uscita debbono restare fissi per una singola connessione, anche se il percorso interno può essere variabile.
G A
G
G G
G G
G G
G G
G G
G B G
G G Source
host Destination
host
VC 1
VC 2 VC 3
VC 4
VC 5
Gateway
Connectionless gateways
L’unico servizio supportato consente il trasferimento di un pacchetto senza alcuna possibile conferma. Non è richiesto che tutti i pacchetti seguano la stessa sequenza di Gateways.
Durante il viaggio da un gateways all’altro, i vari datagram devono essere incapsulati nei formati di Data link tipici di ogni rete attraversata.
G A
G
G G
G G
G G
G G
G G
G B G
G G Source
host Destination
host
Layer
4 TH TH
3 IP TH IP IP IP TH
2
1 Host A
TH
Frame 1 Frame 1
Gateway 1 Gateway 2
Host B
Frame 3 Frame 2
TH
Frame 2 Frame 3
Network 1
Network 2
Network 3
Frammentazione - Riassemblaggio dei pacchetti
Ciascuna rete impone una max dimensione nei messaggi, a causa di requisiti Hardware (es. dimensione di uno slot TDM), Sistema operativo (buffers di 512 bytes), Protocolli adottati, uso di particolari standard, desiderio di ridurre gli errori, per evitare che un pacchetto occupi la rete troppo a lungo.
Due approcci sono possibili:
•Frammentazione trasparente da parte del gateway
•Frammentazione permanente(la ricostruzione del pacchetto avviene solo nell’Host finale).
G1 G2 G3 G4
Network 1 Network 2
Packet
G1Fragments a large packet
G2reassembles the fragments
G3fragments again
G4reassembles again
G1 G2
G1Fragments a large packet
G3 G4
Packet
The fragments are not reassembled until the final
