polimd/Piattaforme Software per la Rete/MOD1/lesson_08.md

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.