RETI DI CALCOLATORI
Parte Quarta
BRIDGE, SWITCH,
ROUTER
Gianfranco Prini
DICO - Università di Milano
[email protected]
NOTA DI COPYRIGHT
•
•
•
•
•
•
Queste trasparenze (slide) sono protette dalle leggi sul copyright e dalle disposizioni dei
trattati internazionali. Il titolo e il copyright delle slide (ivi inclusi, ma non limitatamente,
ogni immagine, fotografia, animazione, video, audio, musica, testo, tabella, disegno) sono
di proprietà dell'autore.
Le slide possono essere riprodotte e utilizzate liberamente dagli istituti di ricerca, scolastici
e universitari italiani afferenti al Ministero dell’Istruzione, dell’Università e della Ricerca per
scopi istituzionali e comunque non a fini di lucro. In tal caso non è richiesta alcuna
autorizzazione.
Ogni altro utilizzo o riproduzione, completa o parziale (ivi incluse, ma non limitatamente, le
riproduzioni su supporti ottici e magnetici, su reti di calcolatori e a stampa), sono vietati se
non preventivamente autorizzati per iscritto dall'autore.
L'informazione contenuta in queste slide è ritenuta essere accurata alla data riportata nel
frontespizio. Essa è fornita per scopi meramente didattici e non per essere utilizzata in
progetti di impianti, prodotti, reti, etc. In ogni caso essa è soggetta a cambiamenti senza
preavviso. L'autore non assume alcuna responsabilità per il contenuto delle slide (ivi
incluse, ma non limitatamente, la correttezza, la completezza, l'applicabilità, l'adeguatezza
per uno scopo specifico e l'aggiornamento dell'informazione).
In nessun caso possono essere rilasciate dichiarazioni di conformità all'informazione
contenuta in queste slide.
In ogni caso questa nota di copyright non deve mai essere rimossa e deve essere riportata
fedelmente e integralmente anche per utilizzi parziali.
ARGOMENTI
•
•
•
•
•
•
•
Limiti delle LAN e loro superamento
Bridge: caratteristiche e tipologia
Transparent e source routing bridge
Switch e "nuove" LAN commutate
Router e differenze rispetto ai bridge
Principali algoritmi di routing
Switching di livello 3 e superiori
"LIMITI DEI LIMITI" DELLE LAN
• Distanze massime tra stazioni
– Limitano la portata geografica delle LAN
• Numero massimo di stazioni
– Limita la portata organizzanizzativa delle LAN
• Massimo carico della rete
– Limita il throughput a valori inadeguati
• Soluzione: interconnettere più LAN tra di loro
a un livello ISO/OSI soprastante quello fisico
BRIDGE (E SWITCH)
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Network
Network
LLC
Relay
LLC
MAC
MAC
MAC
MAC
Physical
Physical
Physical
Physical
OPPORTUNITA' OFFERTE
BRIDGE (E SWITCH)
DA
• Interconnessione di LAN con diverso MAC
(e.g. Ethernet e Token Ring)
– Basta ricopiare le LLC PDU da una trama MAC all'altra
• Interconnessione di LAN con diversa velocità
di trasmissione (e.g. Ethernet e Fast Ethernet)
– La trama MAC rimane (sostanzialmente) immutata
• Incremento della banda complessiva
– Segmentando una LAN in N reti distinte la banda
aggregata aumenta di un fattore compreso tra 1 e N
• Aumento della portata geografica
– Raccordando N reti le distanze massime superabili con la
LAN risultante crescono di un fattore compreso tra 1 e N
CARATTERISTICHE DEI
BRIDGE (E DEGLI SWITCH)
• Operano al sottolivello MAC del Data Link
– La loro presenza è del tutto invisibile al sottolivello LLC
– Consentono talora di filtrare il traffico (inclusivamente o
esclusivamente) su base DSAP, SSAP o Protocol Type
• Possono operare in ambito locale o remoto
– I livelli MAC da raccordare tramite la funzione di relay
possono coesistere all'interno dello stesso apparato
(situazione più frequente - bridge locale) oppure possono
operare separatamente in apparati distinti connessi tra di
loro (caso infrequente - bridge remoti)
• Utilizzano algoritmi di instradamento semplici
– Calcolano le abelle di instradamento con algoritmi di
routing isolato (si limitano a esaminare gli indirizzi MAC
dei pacchetti in transito, senza interagire con altri bridge)
TIPI DI BRIDGE (E DI SWITCH)
• Transparent bridge (standard IEEE 802.1D)
– Derivano architetturalmente dai primi bridge Ethernet
– Gestiscono direttamente le tabelle di instradamento, che
risiedono in una memoria locale al bridge
– Sono del tutto invisibili alle stazioni appartenenti alle LAN
interconnesse dai bridge, le quali non necessitano quindi
di alcuna riconfigurazione quando la rete "cambia"
• Source routing bridge
– Devono comunque essere conformi anche a IEEE 802.1D
– Derivano architetturalmente dai bridge Token RIng
– Non gestiscono tabelle di instradamento (esse risiedono
a bordo delle stazioni, le quali devono esplicitare l'intero
percorso prescelto in ciascuna MAC PDU da inoltrare)
– Le stazioni vanno riconfigurate quando la rete "cambia"
TRANSPARENT BRIDGE:
FORWARDING & LEARNING
while pacchetto ricevuto senza errori sulla porta P
do comment FORWARDING (fase di instradamento)
if DSAP presente in tabella di instradamento
then if tabella richiede instradamento su porta P
then ignorare il pacchetto
else instradare come da tabella
else instradare il pacchetto su tutte le porte del
bridge ad eccezione della porta P
comment LEARNING (fase di apprendimento)
if SSAP non presente in tabella di instratamento
then aggiungere SSAP a tabella di instradamento
associandolo alla porta P (e al timer corrente)
else aggiornare tabella di instradamento (e timer)
SPANNING TREE
• L'algoritmo di apprendimento funziona solo
su reti con topologia ad albero
– Le topologie magliate vanno ricondotte a topologie ad
albero disabilitando alcune porte
• L'algoritmo di spanning tree costruisce un
albero, coerente con la maglia, che raccorda
tutti i bridge presenti nella rete
– Viene eseguito perdiodicamente (ogni minuto secondo)
– Decide quali porte abilitare (stato di forwarding) e quali
disabilitare (stato di blocking)
• Tutti i bridge di una rete devono gestire uno
spanning tree conforme allo standard 802.1D
– Possono implementare schemi di bridging aggiuntivi
SOURCE ROUTING BRIDGE
• RII (Routing Info Indicator): primo bit di SSAP
– Valore RII=1 (trama broadcast/multicast) non significativo
per il SSAP (che è necessariamente un indirizzo unicast)
– Valore RII=1 indica la presenza del campo Route Control
– Route control indica quanti sono i Segment (max 8)
– Segment Number: campo di 16 bit coi due sottocampi
Ring Number (12 bit) e Bridge Number (4 bit)
– Ring Number assegnato dall'amministratore della rete
– Bridge Number discrimina tra bridge paralleli
max 8
DSAP
(6 byte)
SSAP
Route
Segment
Segment
1 (6 byte) Control Number 1 ... Number N
RII
LLC PDU
FCS
(4 byte)
SWITCH
• Bridge multiporta, spesso con molte porte
• Obbiettivo: switching a wire speed su tutte le
porte, quindi algoritmo implementato in H/W
– Pacchetti Ethernet di lunghezza minima 14480 pps
– Pacchetti Ethernet di lunghezza massima: 812 pps
– Algoritmo di forwarding/learning realizzato in hardware
• Talora implementano tecniche cut-through
invece di store-and-forward
– Ritrasmissione del pacchetto inizia subito dopo aver
ricevuto DSAP (e SSAP per completare algoritmo)
– Non filtra i pacchetti corrotti (e i frammenti di collisione)
perché inizia a ritrasmettere ben prima di ricevere FCS
LAN TOTALMENTE COMMUTATE:
VERSO LE "NUOVE" RETI
• Realizzate con switch multiporta a ciascuna
delle quali si connette una sola stazione
• Canali dedicati per ciascuna stazione
– Massimo throughput: banda non più condivisa con altre
porte, ma dedicata per ciascuna porta
– Minima latenza nelle applicazioni interattive se gli switch
lavorano a wire speed e utilizzano cut-through
– Massima sicurezza: nessun rischio di "sniffing" sul
canale, possibilità di filtrare il traffico sulla base degli
indirizzi MAC delle stazioni, oppure degli indirizzi di
livello Network, oppure del protocollo dichiarato nelle
trame LLC, del servizio di rete richiesto dalla stazione,
dell'utente (che viene richiesto di "fare login sulla rete"
prima di poterla usare), etc.
ROUTER
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Relay
Network
Network
Network
Network
LLC
LLC
LLC
LLC
MAC
MAC
MAC
MAC
Physical
Physical
Physical
Physical
ROUTER: CARATTERISTICHE
• Operano a livello Network
• Implementano poche famiglie di protocolli
– Sempre più di frequente implementano solo IP
• Compatibili con topologie magliate
– Nessun problema di spanning tree, utilizzo pieno di tutte
le porte disponibili, nessuna delle quali viene disabilitata
• Non propagano trame broadcast e multicast
del sottolivello MAC
• Permettono routing gerarchico ripartendo la
rete in aree
ROUTER: DIFFERENZE
RISPETTO A BRIDGE
• Router esplicitamente indirizzati dalle stazioni
– Presenza di transparent bridge ignorata (addirittura non
rilevabile) dalle stazioni
• Tabelle di instradamento calcolate sulla base
di informazioni provenienti da altri router
– I bridge si basano su informazione locale
• Frammentazione e riassemblaggio delle trame
possibile con i router
– I bridge non manipolano mai le PDU di livello superiore
• Priorità delle trame gestibile con i router
– I bridge non implementano alcuna nozione di priorità
ALGORITMI DI ROUTING
• Obbiettivi che possono essere contrastanti
– Minimizzare i tempi di inoltro dei pacchetti
– Massimizzare l'utilizzo delle linee a lunga distanza
• Scalabilità degli algoritmi
– Complessità: non lineare nel numero dei nodi
– Stabilità: convergenza problematica con reti complesse
– Equità: non sempre facile garantire par condicio ai nodi
• Ottimalità: due metriche principali
– Hops: numero di sistemi intermedi attraversati
– Costo: sommatoria dei costi delle singole linee
attraversate (inversamente proporzionali a velocità)
TIPI DI ALGORITMI DI ROUTING
• Non adattivi (statici, deterministici): i criteri di
instradamento rimangono 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
• Slogan: dinamici al centro, statici ai bordi
FIXED DIRECTORY ROUTING
• Tabelle di instradamento costruite "a mano"
SOMEDIA
Port_03
SOMALIA
Port_15
SOMAGLIA
Port_08
• Riconfigurazioni di tabelle gestite "a mano"
possibilmente in anticipo rispetto ai guasti
SOMEDIA
Port_003
SOMALIA
Port_015
SOMAGLIA
Port_008
Port_005
Port_003
FLOODING
• Pacchetti ritrasmessi su tutte le porte tranne
quella di provenienza
– Carichi bassi: strategia accettabile (o addirittura buona)
– Miglioramenti: time-to-live, packed drop al secondo
passaggio (i nodi devono tenere un log del traffico)
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
ROUTING CENTRALIZZATO
• RCC (Routing Control Center) riceve info sullo
stato della rete da ciascun nodo, calcola le
tabelle e le distribuisce a tutti i nodo
• Ottimizza prestazioni, ma in caso di guasto si
possono generare loop dovuti a info parziali
• Carico sulla rete elevato in prossimità di RCC
ROUTING ISOLATO
• Ogni nodo instrada senza consultare altri nodi
– Simile all'algoritmo dello standard IEEE 802.1D
ROUTING DISTRIBUITO
• Tabelle calcolate da ogni router dialogando
con gli altri router e con le stazioni
• Algoritmi Distance Vector (Bellman-Ford)
– Quando un nodo modifica le proprie tabelle, ne invia una
copia "massaggiata" (distance vector) ai nodi adiacenti,
che la fondono con quelle provenienti dagli altri nodi, etc.
– Convergenza: O(Cn), ma O(n2) e O(n3) nel caso tipico
• Algoritmi Link State
– Ogni router eslprora 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
SWITCHING DI LIVELLO 3 E 4
• Se uno switch può commutare pacchetti sulla
base dell'indirizzo MAC, perché non può fare
lo stesso per l'indirizzo Network?
• Protocollo IP switching definito da Ypsilon
Networks (RCF-1577), ma altri approcci sono
possibili
• Gli switch diventano sempre più sofisticati, e
implementano funzionalità tipiche del livello
Network (layer 3 switching)
– Non è una novità: molti bridge sono in realtà brouter
• Tendenza a portare lo switching a livello 4
(protocollo definito da Yago Systems)