Architetture di commutazione ed elaborazione dati a pacchetto

Gregorio Procissi      Tel. 050 2217622

Il corso presenta le principali architetture di commutazione, con particolare riferimento alla commutazione di pacchetto. Dopo una breve introduzione al concetto di commutazione (di circuito e pacchetto), il corso si focalizzerà sulle architetture di packet switching, presentandone gli schemi principali con relativa analisi delle prestazioni e problematiche. Di seguito verrà affrontato il tema dell’elaborazione dei pacchetti, presentando i più noti algoritmi di lookup e di classificazione attualmente in uso. Infine verrà trattato il tema del riconoscimento di pattern di dati, attraverso l’uso di tecniche probabilistiche (mediante l’uso di strutture dati evolute quali Bloom Filter) e deterministiche (mediante l’uso di automi a stati finiti deterministici).

1) Generalità sui sistemi di commutazione a. Commutazione di circuito b. Commutazione di pacchetto 2) Architetture di commutazione di pacchetto a. Output Queued Switches (OQ) i. Ritardo medio e massimo throughput ii. Output link scheduling b. Input Queued Switches (IQ) i. Switching fabrics, crossbar. ii. Head Of the Line blocking (HOL) iii. Scheduling (MWM, MSM, etc.) c. Combined Input-Output queueing (CIOQ) i. Emulazione di OQ 3) Packet Processing a. Exact/Prefix match lookup i. Unibit e Multibit Trie ii. Lulea-Compressed Tries iii. Tree bitmap b. Classificazione i. Schemi mono/multi dimensionali c. Pattern Matching i. Tecniche stocastiche ii. Tecniche deterministiche