Laboratorio di Calcolo Avanzato del Dipartimento di Fisica

I Bridge

Le reti locali viste fino ad ora devono rispettare dei vincoli riguardo alle distanze massime ammesse, al numero di elaboratori collegabili, al mezzo trasmissivo da utilizzare e così via. Se si vogliono interconnettere due LAN, cioè se si vogliono oltrepassare i limiti imposti, bisogna utilizzare dei repeater, bridge o router.

Facendo riferimento alla pila OSI, come mostrato nella figura precedente, un repeater collega esclusivamente il livello 1 Phisycal, cioè interconnette singoli segmenti di reti, al fine di formare una rete estesa più grande. La sua funzione è quella di ricevere un messaggio e di ritrasmetterlo, rigenerando l'intensità originale del segnale.

Un bridge opera al livello 2 della pila OSI.

E' quindi in grado di connettere reti fisicamente distinte, poiché contiene due MAC, mentre LLC delle reti da interconnettere deve essere lo stesso.

Un router, invece, è in grado di interconnettere anche LAN con architetture di rete e sistemi operativi differenti, quali per esempio TCP/IP e DECnet fase V, in quanto opera al livello 3 della pila OSI.

I bridge ritrasmettono solamente i pacchetti che devono effettivamente transitare da una LAN ad un'altra, mantenendo separati i traffici locali delle singole LAN che interconnettono. Questa funzionalità, detta di "filtering" permette di ottenere un traffico globale sulla BLAN (in questo modo viene detta una rete locale estesa interconnessa tramite bridge) superiore a quello massimo ammesso per ogni singola LAN.
Tale ritrasmissione avviene in modalità store and forward in quanto il pacchetto viene ricevuto dal bridge che effettua i suoi controlli e poi viene eventualmente ritrasmesso.

Un bridge può quindi mettere in comunicazione reti con architettura MAC uguale oppure può collegare una Token Ring con Ethernet 802.3, una FDDI con Ethernet 802.3 o con Ethernet v2.0. In questi casi dovrà effettuare una conversione dei formati delle trame a livello MAC. Tuttavia, la rete Ethernet v2.0 non utilizza LLC 802.2, quindi il bridge dovrà convertire la LLC-PDU in una LLC snap-PDU, (pacchetto contenente PDU di livello 3 di protocolli proprietari), inserendo, accanto al campo Type (tipo di protocollo che ha generato il pacchetto) anche il campo OUI che è l'identificativo dell'organizzazione che ha proposto tale protocollo.

I bridge hanno algoritmi di instradamento molto semplici: ogni bridge calcola autonomamente le sue tabelle di intradamento senza interagire con gli altri presenti sulla rete con un algoritmo di routing isolato.
I bridge possono essere di due tipi che differiscono dal modo di memorizzare le tabelle di instradamento:

Transparent Bridge: hanno le tabelle di instradamento a bordo e sono trasparenti, cioè i sistemi interconnessi alla LAN ignorano la loro esistenza. Lo standard è 802.1D
Source Routing Bridge: non hanno tabelle di instradamento a bordo, in quanto il pacchetto contiene già il percorso che dovrà effettuare per giungere a destinazione; infatti sono i sistemi interconnessi alla LAN che contengono le tabelle e che specificano i sistemi da attraversare; il bridge avrà quindi un proprio indirizzo.

Le tabelle di instradamento, se la topologia delle reti interconnesse è ad albero, si possono creare facilmente tramite un processo di apprendimento proprio dei bridge. Se invece la topologia è a maglia, si deve utilizzare un algoritmo, detto Spanning Tree, per convertire la topologia magliata in un albero, escludendo alcune porte di alcuni bridge.

I bridge che operano tra LAN eterogenee hanno il problema aggiuntivo della diversa lunghezza massimo del campo dati (INFO) del pacchetto MAC. Questa lunghezza, la cosiddetta MTU, varia a seconda degli standard: di va da 1500 byte per 802.3 a 4478 byte per FDDI fino a 17749 per 802.5 (Token Ring). Poichè non è possibile violare tali dimensioni massime, quando un bridge deve ritrasmettere un pacchetto di dimensione superiore a quella massima ammessa ha due possibilità: scartare il pacchetto oppure frammentarlo.
L'operazione della frammentazione è tipica del livello 3 e non può essere fatta da un bridge in modo generalizzato per tutti i protocolli.

Fortunatamente molti protocolli non superano mai il limite di 1500 byte ed il problema non si pone. Invece TCP/IP genera sistematicamente pacchetti più grandi ed il pacchetto va frammentato. Parecchi bridge realizzano perciò la frammentazione anche se limitatamente al protocollo IP.

Importanti sono le prestazioni di un bridge in quanto influenzano le prestazioni di tutta la rete.
I parametri principali sono:

il numero di pacchetti al secondo che un bridge riesce a filtrare (cioè a ricevere e processare)
il numero di pacchetti al secondo che un bridge riesce a ritrasmettere
il tempo medio di latenza, cioè il tempo di attraversamento del bridge da parte di un pacchetto

Un bridge, per minimizzare la perdita di dati, è preferibile che sia full-speed, cioè che i primi due parametri siano uguali al massimo teorico. Tale proprietà va verificata in caso che i pacchetti siano più corti possibili, per massimizzare il carico di lavoro nell'unità di tempo del bridge. Per 802.3, un bridge è full-speed se è in grado di inoltrare 14880 pps da 64 byte. Tale numero va calcolato tenendo presente la lunghezza complessiva di ogni pacchetto, compreso il preambolo, i delimitatori, e l'inter frame spacing.
Il tempo di latenza esprime il tempo che intercorre da quando il pacchetto inizia ad entrare ad entrare nella porta ricevente a quando esso inizia ad uscire dalla porta del trasmittente. Questo tempo e' variabile a seconda della lunghezza del pacchetto e varia da 80 microsecondi fino a 1.2 millisecondi.

Nel progetto OSI i bridge sono stati concepiti per interconnettere LAN su base locale, mentre l'interconnessione su base geografica è demandata ai router. Tuttavia, dato che i bridge sono trasparenti ai protocolli di livello 3 e poichè si sono resi disponibili prima dei router multiprotocollo, sono stati modificati per operare anche su scala geografica e sono nati i cosiddetti bridge remoti. I protocolli più usati sulle linee sono HDLC e PPP. I bridge remoti non si prestano tuttavia a realizzare strutture magliate in quanto l'algoritmo di spannig tree mette in backup (stato di blocking) costose linee pubbliche fino a ridurre la rete ad un albero.

Architettura fisica/logica di un bridge

I bridge sono costituiti, come mostrato nella figura seguente, da una o più CPU, una memoria ROM ed una RAM e due o più interfacce fisiche per le LAN da interconnettere.

La ROM contiene il software per realizzare le funzioni principali gestito dalle CPU. La RAM contiene un buffer di memorizzazione dei dati, le tabelle di instradamento ed un'area di memoria utilizzata dai software per i dati interni. Le interfacce sono costituite dai controller dei differenti standard e dalle connessioni fisiche sui diversi mezzi trasmissivi.

Da un punto di vista logico, un bridge è costituito da seguenti elementi:

le porte
l'entità di trasmissione e filtraggio "MAC Relay Entity"
le entità di livello superiore "Higher Layer Entity"

Ogni porta riceve/trasmette pacchetti da/a una LAN usando il servizio fornito dall'entità MAC associata a tale porta.
La MAC Relay si occupa della trasmissione tra due porte e del filtraggio dei pacchetti.

Le entità di livello superiore (HLE), invece, fanno uso delle procedure proprie dell'LLC che sono:

Bridge Protocol Entity: calcolo e configurazione della topologia della BLAN (Spanning Tree)
Bridge Management: controllo e gestione delle funzioni interne

Indirizzamento

Il bridge, tramite le tabelle di instradamento, decide a quale sistema indirizzare i pacchetti, cioè decide da quale porta trasmettere i dati.

I pacchetti trasmessi da un sistema S1 ad un sistema S2 vengono confinati dai bridge nelle LAN che formano il percorso tra S1 e S2. Questo tipo è il più comune e serve a ridurre il traffico globale e viene effettuato grazie ad algoritmi di apprendimento automatico e grazie all'algoritmo di spannig-tree che effettua il calcolo e la configurazione della BLAN. Qualora esistano diversi percorsi per passare da S1 a S2 i bridge operano un ulteriore filtraggio per prevenire la duplicazione di pacchetti. Esiste anche la possibilità di attivare un filtraggio statico in cui filtrare a priori oppure non filtrare certi pacchetti.

Le porte possono infatti essere attive o passive. Se attive possono essere in uno dei seguenti stati:

Listening La porta si prepara a partecipare alla ritrasmissione dei pacchetti. Il processo di forwarding scarta tutti i pacchetti ricevuti. Il processo di learning non aggiunge nuove informazioni alla tabella di instradamento. La porta abbandona questo stato allo scadere del forward delay time per passare allo stato di learning.
Learning La porta si prepara a partecipare alla ritrasmissione dei pacchetti. Il processo di forwarding scarta tutti i pacchetti ricevuti ma il processo di learning aggiunge le informazioni ricevute alla tabella di instradamento. La porta abbandona questo stato allo scadere del forward delay time per passare allo stato di forwarding.
Forwarding La porta partecipa alla ritrasmissione dei pacchetti. Il processo di forwarding può inoltrare i pacchetti ricevuti ed il processo di learning aggiunge le informazioni ricevute alla tabella di instradamento.
Blocking La porta non partecipa alla ritrasmissione dei pacchetti. Il processo di forwarding scarta tutti i pacchetti ricevuti. Una porta entra in questo stato qundo riceve l'informazione che un'altra porta è la designated port per la LAN a cui è connessa (vedi precesso di spannig tree).

Nelle tabelle di instradamento sono quindi contenute queste informazioni sottoforma di righe (entry). Le entry sono statiche (informazioni di filtraggio configurate tramite operazioni di management) o dinamiche (registrate automaticamente dal processo di apprendimento).
Le entry dinamiche non vengono create se ne esiste già una statica relativa allo stesso indirizzo MAC, mentre la creazione di un'entry statica determina la cancellazione di quella dinamica, se già esistente. Inoltre, le entry dinamiche vengono rimosse se non sono aggiornate prima dello scadere di un tempo di timeout.

Ricezione e trasmissione dei pacchetti

Durante la ricezione, il bridge riceve ed esamina tutti i pacchetti che circolano sulla LAN e trattiene quelli da inoltrare sull'altra LAN. Innanzitutto esegue l'analisi dell'FCS e i pacchetti corrotti vengono scartati. I pacchetti possono essere indirizzati ad un'entità superiore del bridge stesso: verranno quindi inoltrati al livello LLC associato alla porta di ricezione. In questo caso il MAC DSAP sarà l'indirizzo del bridge stesso. Se invece il MAC DSAP è diverso, i pacchetti verranno processati per l'inoltro.
Il processo di inoltro deciderà, quindi, su quale porta accodare i dati, utilizzando le informazioni contenute nelle tabelle di instradamento ed in base allo stato delle porte.
Condizione neccessaria affichè ci sia accodamento su una porta è che la porta stessa sia in stato di forwarding.
L'accodamento rispetta l'ordine di arrivo, operando in modalità FIFO.
Un pacchetto viene rimosso dalla coda di una porta dopo la ritrasmissione o se viene oltrepassato il tempo massimo di transito (tempo di latenza).
Un pacchetto può essere accodato su diverse porte se l'indirizzo è broadcast o multicast. Solo se le due LAN sono differenti, il pacchetto verrà convertito e sarà effettuato il ricalcolo del FCS.

Il processo di apprendimento

Al momento della ricezione di un pacchetto, il bridge osserva l'indirizzo del mittente, il MAC SSAP, e la porta da cui è arrivato. Il bridge andrà poi a creare o modificare un'entry dinamica nella tabella di instradamento nella quale specificherà che il tale indirizzo è raggiungibile tramite la tale porta.

Si tratta quindi di informazioni che il bridge potrà utilizzare solo in futuro, quando riceverà un pacchetto con il MAC DSSAP uguale al MAC SSAP precedente. Tale metodologia di apprendimento è detta routing isolato - backward learning.
Il bridge, comunque, creerà la nuova entry dinamica se e solo se non ne esista già una statica che faccia riferimento allo stesso indirizzo o se le porte in questione siano attive e in stato di learning o forwarding.

Bridge management

Ogni bridge deve avere un indirizzo MAC, il classico di 48 bit. Inoltre, anche ogni porta del bridge deve essere identificata da un indirizzo MAC. Le porte sono poi numerate sequenzialmente per l'uso interno e l'indirizzo del bridge corrisponde alla porta 1.

Le entità di protocollo dei bridge effettuano la modifica delle informazioni di stato delle porte e la modifica delle tabelle di instradamento suggerite dall'algoritmo di spanning tree. Esse operano tramite delle speciali PDU, le cosiddette BPDU (Bridge PDU), trasmesse in modalità multicast ad un indirizzo MAC speciale denominato Bridge Group Access (il cui valore è 01-80-C2-00-00-00).

Le entità di management, invece, comunicano usando il servizio fornito dai LLC associati alle porte, tramite l'indirizzo All LANs Bridge Management Group Access (01-80-C2-00-00-10).

Qualità del servizio

I bridge realizzano un servizio non connesso e non confermato.
A causa di questo tipo di servizio il recapito dei pacchetti non è garantito. La presenza di un bridge può aumentare leggermente la probabilità di perdita del pacchetto se:

non è in grado di trasmettere entro il tempo massimo definito e deve scartare il pacchetto
non è in grado di memorizzare altri pacchetti in quanto il buffer interno è saturo a causa della maggiore velocità di arrivo dei pacchetti rispetto alla velocià di inoltro
la dimensione del pacchetto eccede quella massima della LAN
durante il cambiamento della topologia deve scartare i pacchetti per un certo periodo di tempo per garantire altri aspetti della qualità del servizio

L'utilizzo dei bridge garantisce comunque l'esatto ordine di sequenza dei pacchetti arrivati.
Viene inserito un ritardo di transito addizionale a causa delle operazioni che deve effettuare per l'inoltro di un pacchetto che sono: aspettare di aver ricevuto il pacchetto, verificare la validità del FCS e controllare la tabella di instradamento per decidere se e dove inoltrare il pacchetto.
Nel seguente diagramma a blocchi vengono mostrate le principali operazioni del bridge.

L'algoritmo di Spanning Tree

Lo Spanning Tree riconfigura una topologia di BLAN a maglia in una topologia ad albero, per evitare la presenza di percorsi alternativi e la conseguente duplicazione dei pacchetti e per evitare percorsi chiusi, i loop.
Deve essere in grado di farlo nel più breve tempo possibile, deve utilizzare una banda limitata per le BPDU che i bridge si devono scambiare ed inoltre deve essere flessibile, cioè deve poter ammettere che un bridge venga aggiunto successivamente a rete configurata senza che sia indispensabile riconfigurare tutta la rete. Per gestire ed assolvere questo compito, si assegna ai bridge a livello di management un valore di priorità di 2 byte, che, aggiunto all'indirizzo MAC di 6 byte, compone un identificativo univoco (bridge ID) di 8 byte per il bridge stesso. La configurazione di una topologia ad albero partendo da una topologia a maglia avviene ponendo alcune porte in stato di blocking; le porte in questo stato non partecipano alla topologia attiva ma sono in attesa ed entrano in funzione in caso di guasto in qualche componente della BLAN.
Anche le porte hanno un valore di priorità di 1 byte ed il valore prioritario è quello minore.

L'algoritmo opera nei seguenti passi:

elezione del root-bridge: il bridge con ID minore è la root dell'albero
selezione della root-port: per ogni bridge si seleziona la porta più conveniente per interconnetterlo al root
selezione del designated-bridge: per ogni LAN si sceglie quale bridge è designato ad interconnetterla con il root; la porta utilizzata è la designated-port

Ogni LAN ha quindi un solo designated bridge che e' quello più "vicino" al root bridge
Al termine di queste azioni, lo spanning procede alla messa in stato di blocking per tutte le porte che non sono root o designated.

Come mostrato nella figura precedente si può notare il funzionamento dell'algoritmo che permette di trasformare una LAN con struttura logica a maglia in una ad albero mettendo in stato di blocking una porta dei bridge 3 e 5. In questo esempio il bridge 1 è stato eletto come root bridge ed è quindi il designated bridge per la LAN 1 e la LAN 2; il bridge 2 è il designated bridge per la LAN 3 e la LAN 4 ed il bridge 4 è il designated bridge per la LAN 5.

Il fattore che determina la configurazione è il path cost: ad ogni porta viene assegnato un path cost che può essere configurato da management e che indica il costo di attraversamento di quella porta. Per ogni bridge e per ogni porta del bridge viene anche definito il root path cost come il costo totale di percorso per raggiungere il root bridge. Con questo ultimo parametro si sceglie all'interno di un bridge quale sia la root port (quella con root path cost minore) e tra le non root port dei bridge che si collegano su una LAN la designated port (quella con root path cost minore).

Il gestore della BLAN può controllare la formazione delle topologie attive intervenendo sui parametri Bridge ID, port priority e path cost.

Risulta, perciò, evidente che, per poter implementare lo spanning tree, i bridge devono scambiarsi delle informazioni. Lo fanno tramite le cosiddette BPDU, Bridge Protocol Data Unit.

BRIDGE PDU

Le BPDU sono pacchetti aventi come DSAP l'indirizzo di Bridge Group Access (indirizzo multicast per tutti i bridge presenti sulla LAN).La trama contiene l'SSAP e una parte è riservata per il Configuration Message, composto come nella figura seguente:

I campi presenti nella Configuration BPDU sono:

Root Identifier: identificatore del root bridge; è composto da 2 byte, che sono la priorità, più altri 6, che sono l'indirizzo MAC.
Root Path Cost: costo totale di percorso per raggiungere il root; questo campo viene aggiornato dopo ogni passaggio da un bridge.
Bridge Identifier: è l'identificatore del bridge che ha ritrasmesso la BPDU; è composto da 2 byte, che sono la priorità, più altri 6, che sono l'indirizzo MAC del bridge.
Port Identifier: l'identificatore della porta da cui è stata trasmessa la BPDU è composto da due ottetti: il primo indica la priorità, mentre il secondo è l'identificativo della porta.
Message Age: è il tempo trascorso dalla generazione della BPDU (in multipli di 4 millisecondi).
Max Age: se Message Age supera questo tempo limite, la BPDU viene scartata (in multipli di 4 millisecondi).
Hello Time: tempo che intercorre fra la generazione di due BPDU.
Forward Delay: indica il tempo di permanenza nello stato di listening prima di passare nello stato di learning e nello stato di learning prima di passare nello stato di forwarding.
Topology Change (TC): è un flag che viene impostato dal root bridge in tutte le BPDU generate in seguito alla ricezione di un Topology Change Notification BPDU o in seguito ad un cambiamento di topologia.
Topology Change Acknowledgment (TCA): è un flag che viene messo ad uno dal designated bridge della LAN in seguito alla ricezione di una TCN BPDU.

Vediamo come procede l'algoritmo di Spanning Tree.

Tutti i bridge, al momento dell'accensione, si credono i root ed incominciano a trasmettere le Configuration PDU. Quando ne ricevono una, confrontano il bridge ID con il proprio e, nel caso che quest'ultimo sia maggiore, smettono di trasmettere. Si elegge così rapidamente il Root Bridge, quello con l'identificativo minore, l'unico che trasmette le Configuration BPDU.
Un bridge, in questo stadio, riceve i pacchetti di configurazione del root bridge da tutte le porte ed eleggerà la sua Root Port confrontando i valori di Root Path Cost.
Le rimanenti porte sono ancora in stato di listening. Quando da una porta riceve una BPDU maggiore, cioè con parametri quali i root path cost, il bridge identifier e il port identifier maggiori rispetto ad una BPDU ricevuta precedentemente da un'altra porta, il bridge metterà in stato di blocking tale porta. Infine, le porte prescelte sono messe in stato di forwarding.
La configurazione ad albero è stata così realizzata.

Un bridge, durante la sua normale attività, può accorgersi che la topologia è stata modificata, senza che questo possa essere avvertito dagli altri bridge. Questo può causare la presenza di loop nella topologia ad albero, con una conseguente proliferazione di pacchetti e possibile duplicazione di essi.
In questo caso il bridge trasmette sulla root port una Topology Change Notification BPDU per avvertire il root bridge. Il root risponderà con una BPDU in cui il flag TC è messo ad 1. La TCN viene ritrasmessa fino a che il designated bridge della LAN non pone ad 1 il flag TCA (Acknowledgment) nella Configuration BPDU.

I bridge source routing sono stati sviluppati per operare tra reti token ring. Essi sono esplicitamente indirizzati dalle stazioni che necessitano di inviare un messaggio sulla BLAN.
I bridge source routing basano l'instradamento del pacchetto sulle informazioni contenute nel pacchetto stesso nel campo RI (routing information). Se un pacchetto non ha il campo RI (ossia se è destinato alla stessa LAN) viene ignorato dal bridge. I sistemi devono perciò mantenere una tabella di instradamento contenente le destinazioni con cui sono interessati a comunicare e che richiedono l'attraversamento di un bridge. Le entry di tali tabelle vengono calcolate automaticamente tramite un processo chiamato route discovery.