Ottobre 1996
Architetture
degli switch ATM
Silvano GAI
[email protected]
http://www.polito.it/~silvano
ATM_SWI - 1
Copyright: si veda nota a pag. 2
Ottobre 1996
Nota di Copyright
Questo insieme di trasparenze (detto nel seguito slides) è protetto dalle leggi
sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i
copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine,
fotografia, animazione, video, audio, musica e testo) sono di proprietà degli
autori indicati a pag. 1.
Le slides possono essere riprodotte ed utilizzate liberamente dagli istituti di
ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione
e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi
istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna
autorizzazione.
Ogni altra utilizzazione o riproduzione (ivi incluse, ma non limitatamente, le
riproduzioni su supporti magnetici, su reti di calcolatori e stampate) in toto o in
parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte
degli autori.
L’informazione contenuta in queste slides è ritenuta essere accurata alla data
della pubblicazione. Essa è fornita per scopi meramente didattici e non per
essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è
soggetta a cambiamenti senza preavviso. Gli autori non assumono alcuna
responsabilità per il contenuto di queste slides (ivi incluse, ma non
limitatamente, la correttezza, completezza, applicabilità, aggiornamento
dell’informazione).
In ogni caso non può essere dichiarata conformità all’informazione contenuta
in queste slides.
In ogni caso questa nota di copyright non deve mai essere rimossa e deve
essere riportata anche in utilizzi parziali.
ATM_SWI - 2
Copyright: si veda nota a pag. 2
Ottobre 1996
Sommario
Architetture di commutazione ATM
Switch con buffer in ingresso
Switch con buffer in uscita
Switch con buffer condiviso
Trattamento del multicast/broadcast
Un rigraziamento particolare a Davide Bergamasco
che ha contribuito alla relizzazione di questa
presentazione.
ATM_SWI - 3
Copyright: si veda nota a pag. 2
Ottobre 1996
Architetture di Commutazione ATM
Un nodo di commutazione ATM è un dispositivo che
svolge fondamentalmente tre funzioni:
Multiplex switching (M): spostamento fisico delle celle ATM da
un link di ingresso ad un link di uscita;
Label switching (L): sostituzione VC Id. (VPI/VCI) valido sul link
di ingresso con quello valido sul link di uscita;
Replication (R): generazione di copie multiple di una cella per le
connessioni multicast.
Look-up
Table
Delay
M-Function
ATM_SWI - 4
L-Function
Copyright: si veda nota a pag. 2
R-Function
Ottobre 1996
Architetture di Commutazione ATM
Putting all togeter ...
Look-up
Table
Buffered
Switching Fabric
Delay
Look-up
Table
Delay
Look-up
Table
Delay
ATM_SWI - 5
Copyright: si veda nota a pag. 2
Ottobre 1996
Architetture di Commutazione ATM
Di solito la struttura di commutazione svolge le funzioni
M e R sulla base di una routing tag, un campo anteposto
ad ogni cella dalla funzione L che indica verso quale o
quali porte questa deve essere instradata.
I modelli architetturali adottati per la struttura di commutazione si differenziano in base alla posizione dei buffer:
buffer in ingresso;
buffer in uscita;
buffer condiviso.
ATM_SWI - 6
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
I cell switch con buffer in ingresso presentano tipicamente una
architettura
modulare,
realizzata
interconnettendo
opportunamente elementi di commutazione 2 x 2 (Switching
Element, SE).
I buffer FIFO agli ingressi degli SE servono a memorizzare i pacchetti che non posso essere inviati alla porta di uscita desiderata
a causa di una contesa con l’altra porta di ingresso.
FIFO Packet
Buffers
1
2x2
Switching
Element
(SE)
0
1
Outputs
Inputs
0
0
1
ATM_SWI - 7
Pass
State
1
0
0
0
1
0
0
1
Switching
Command
0
Cross
State
0
1
1
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
La rete di interconnessione tra SE, di solito una rete multistadio
della famiglia banyan, è organizzata in modo che esista un unico
cammino tra ogni coppia (ingresso, uscita). Ciò garantisce la
consegna ordinata delle celle.
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
ATM_SWI - 8
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
L’esistenza di un cammino unico tra ingressi ed uscite, rende inoltre le reti banyan auto-instradanti: ciascun SE è in grado di effettuare il routing delle celle autonomamente, basandosi unicamente
sull’indirizzo della porta di uscita.
OUT
110
0
0
0
000
1
1
001
1
2
0
0
0
010
3
1
1
1
011
0
0
100
1
1
101
0
110
1
111
0
5
1
0
11
1
6
0
0
7
1
1
ATM_SWI - 9
11
0
Copyright: si veda nota a pag. 2
Dicembre 1996
Switch con buffer in ingresso
Siccome sia il tempo di arrivo delle celle allo switch sia il tempo di
stazionamento nei buffer sono casuali, sussiste la possibilità di
overflow, con una conseguente perdita di celle.
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
ATM_SWI - 10
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
L’overflow dei buffer può essere evitato grazie al meccanismo di
Back Pressure, che consente agli SE di segnalare una situazione
di congestionamento agli stadi precedenti.
Back Pressure
0
3
2
0
3
1
0
1
2
2
3
3
4
4
2
5
5
1
6
6
7
7
ATM_SWI - 11
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
Negli switch con buffer in ingresso ha luogo un secondo
fenomeno negativo, il cosiddetto Head Of Line (HOL) blocking.
Queues blocked by HOL
0
0
13
1
1
3
2
2
3
3
Back-Press.
4
64
4
5
5
6
6
7
7
ATM_SWI - 12
Copyright: si veda nota a pag. 2
Ottobre 1996
Switch con buffer in ingresso
Lo HOL blocking può essere evitato in due modi:
Meccanismo di Cut-Through;
Mutamento architetturale: buffer in uscita oppure buffer condiviso.
Cut-Through: salta buffer vuoto
Cut-Through: salta HOL
0
1
3
6
3
0
1
1
2
2
3
3
Back-Press.
4
4
4
5
5
6
6
7
7
ATM_SWI - 13
Copyright: si veda nota a pag. 2
Dicembre 1996
Switch con buffer in uscita
INPUTS
Gli switch con buffer in uscita consentono la trasmissione
simultanea di più celle verso la stessa uscita senza alcuna
possibilità di contese o blocchi.
Il rischio di overflow dei buffer, tuttavia, sussiste ugualmente.
0
3
1
2
2
2
3
2
Packet
Filter
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
Buffer
Concentrator
0
ATM_SWI - 14
Concentrator
1
Concentrator
OUTPUTS
2
Copyright: si veda nota a pag. 2
Concentrator
3
PF
Ottobre 1996
Switch con buffer condiviso
Gli switch con buffer condiviso impiegano una memoria ad alta
velocità partizionata in tante code logiche quante sono le uscite.
Ad ogni ciclo il controller:
legge tutte le celle presenti sugli ingressi e li pone nelle code di
destinazione;
preleva le celle dalla testa di ciascuna coda e li invia all’uscita
corrispondente.
L’overflow si verifica solo quando l’intera memoria è satura.
0
Controller
INPUTS
2
3
2
FAST
3
DUAL-PORTED
4
MEMORY
5
6
7
ATM_SWI - 15
1
4
5
OUTPUT
MEMORY
MAP
Copyright: si veda nota a pag. 2
6
7
OUTPUTS
1
0
Dicembre 1996
Multicasting
Le reti banyan multistadio supportano l’invio di celle in multi-cast con
un elevato costo in termini di complessità. Occorre:
attribuire alle celle multicast una routing tag particolare, il Broadcast
Channel Number (BCN), ed un campo che indica il numero di copie
da effettuare;
replicare le celle mediante una rete di Copia;
attribuire alle celle replicate una nuova routing tag per l’inoltro verso
la porta di destinazione effettiva;
instradare infine le celle mediante una normale rete banyan.
n
ATM_SWI - 16
Copy
Network
1
OUTPUTS
Banyan
Singlecast Routing
Tagger
INPUTS
1
0
Multicast Routing
Tagger
0
Banyan
Routing
Network
Copyright: si veda nota a pag. 2
n
Ottobre 1996
Multicasting
0
3
34
32
31
30
1
Multicast
Routing
Tagger
2
3
30
31
30
BCN Copies
3
6
30
4
7
0
30
1
2
30
2
Singlecast
Routing
Tagger
7
ATM_SWI - 17
0
2
4
6
3
3
3
3
2
7
1
4
30
30
In BCN Out
0
2
4
6
1
7
2
7
3
3
3
3
2
7
1
4
1
4
1
2
2
4
5
4
6
7
Copyright: si veda nota a pag. 2
4
6
7
1
4
1
5
3
5
6
In BCN Out
0
3
4
Singlecast
Routing
Tagger
0
3
4
5
2
7
Ottobre 1996
Multicasting
Negli switch con buffer in uscita, il multicasting è gestito in
modo estremamente naturale: è sufficiente programmare i PF
delle porte interessate in modo da consentire il passaggio delle
celle recanti una routing tag corrispondente al BCN.
INPUTS
BCN
0
1
2
10
3
Packet
Filter
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
PF
Buffer
MUX
0
ATM_SWI - 18
MUX
1
MUX
OUTPUTS
2
Copyright: si veda nota a pag. 2
MUX
3
PF
Ottobre 1996
Multicasting
Anche negli switch con buffer condiviso il multicasting risulta
estremamente semplice da realizzare; è sufficiente:
creare nel buffer una coda per ogni destinazione multicast;
programmare il controller in modo che esegua la copia di una cella
appartenente ad una coda multicast sulle uscite ad essa corrispondenti.
0
Controller
1
INPUTS
2
2
Queue
M1
3
3
4
4
5
5
6
7
ATM_SWI - 19
Queue
M1
Out
2, 5, 7
Copyright: si veda nota a pag. 2
6
7
OUTPUTS
1
0
Ottobre 1996
Architetture di Commutazione ATM
Confronto tra le varie soluzioni
Architettura
Buffer in Ingresso
Buffer in Uscita
Buffer condiviso
ATM_SWI - 20
Vantaggi
Svantaggi
• Autoinstradamento;
• HOL blocking (eliminabile);
• Semplicita’ realizzativa; • Elevato tempo di attraversamento
(proporzionale al numero di stadi);
• Ottima Scalabilita’.
• Elevata complessita’ per supportare il multicasting.
• Assenza di HOL block.
• Supporto nativo per il
multicasting;
• Basso tempo di attraversamento;
• Assenza di HOL bloc.;
• Supporto nativo per il
multicasting;
• Basso tempo di attraversamento;
• Complessita’ elevata;
• Scarsa scalabilita’ in funzione del
numero di porte;
• Complessita’ elevata;
• Scarsa scalabilita’ in funzione del
numero di porte;
• Richiede memorie ad elevate
prestazioni.
Copyright: si veda nota a pag. 2