# Piattaforme e Software per la rete - lezione 8
#### Giacomo Verticale
###### 8 April 2016
## Switching

Gli switch pososno essere realizzati con tecniche diverse:
- Architettura a BUS
- Matrice di crossbar:
Una matrice con un bus per ogni coppia ingresso uscita
L'architettura __crossbar__ ha il difetto di essere costosa
Ci sono architetture a più stadi che permettono di ottenere lo stesso
livello di connettività con metto punti di incrocio necessari.
Lo __scheduling della crossbar__ consiste nel decidere in ogni istante di tempo
quali ingressi devono parlare con quali uscite.

Il nostro obiettivo è:
##### Massimizzare il numero di connessioni ingressi/uscita contemporanei.

I problemi sono:
- In ogni istante di tempo ogni ingresso/uscita deve trasmettere un pacchetto.
- Può esserci una contesa su una porta in usita.

### Algoritmi per crossbar scheduling
#### Take a ticket
Lavora in modo asincrono.
Ogni *line card* (uscita) mantiene una coda distribuita per i pacchetti destinati ad essa.
Per gestire i ticket non è necessaria una crossbar alternativa, ma basta un bus a contesa.
Le fasi di una ipotesi sincrona sono:
- Gli ingressi chiedono un ticket per il pacchetto più vecchio in base alla destinazione
- L'ordine con cui vengono servite le interfacce dipende dall'algoritmo utilizzato, es: round robin
Questo algoritmo è affetto da __head-of-line-blocking__ in quanto i pacchetti successivi al primo
non vengono processati prima del primo anche se le loro uscite sono disponibili.
- In un round successivo viene servita la porta successiva, che trasmette se la porta necessaria
non è già occupata in una trasmissione.

In condizioni di traffico uniforme il rendimento di questo algoritmo è del 63%
Dato che l'efficienza non è del 100%, se tutte le interfacce sono attive, si formerà una coda.

Strategie per rimediare all'head-of-line blocking.
- Aumentare la velocità del bus interno rispetto alla velocità degli ingressi.
Nei sistemi reali uno speedup di 4X risolve i problemi di efficienza.
- __Virtual Output Queues__ alternativo all'Input Queuing, in cui le code
non sono all'uscita ma all'entrata: ogni ingresso ha una coda per ogni uscita.

#### Parallel Iterative Matching
Diverso dal take a ticket per:
- Virtual Output Queuing invece di Input Queuing
- Richiede pacchetti di dimensione fissa e tempo in slot.

PIM è intrinsecamente randomizzato, feature che non serviva in TaT per l'asyncronicità
Fasi dell'algoritmo:
- Richiesta: tutte le porte di ingresso spediscono informazioni sullo stato tramite una bitmap.
(stringa di bit lunga come #code, se è vuota bit=0 se ci sono pacchetti bit=1)
- Grant: Ciascuna uscita sceglie una porta di ingresso da servire,
se un uscita riceve richieste da più porte di ingresso, ne sceglie una a caso.
- Accept: Ogni ingresso sceglie un uscita, se ce ne sono multiple viene scelta a caso.