Il corso si propone di fornire gli strumenti di base per l'analisi, il dimensionamento ed il controllo delle moderne reti di telecomunicazioni a pacchetto.

Martedi 14:30-16:30 Aula B4; Mercoledi 16:30-18:30 Aula B1; Giovedi 11:30-13:30 Sala riunioni palazzina 2.

Programma (ogni lezione: 2 ore)

Generalità sulle reti e sulla commutazione
LEZIONE 1: Introduzione panoramica al corso. Cosa è una rete. Reti telefoniche e reti di calcolatori. Sistemi centralizzati e distribuiti. Reti private e pubbliche. I nuovi servizi in rete. Indici di prestazione. Gli Standard.
LEZIONE 2: Il problema fondamentale: la condivisione delle risorse. Il Ritardo. Classificazione della condivisione: commutazione e multiplexing. Commutazione di circuito. Commutazione di pacchetto datagram e circuito virtuale.
LEZIONE 3: Multiplexing: SDM, FDM, TDM, CDM. L'accesso multiplo su portanti condivisi. L'accesso multiplo visto come commutazione periferica. Lo statistical multiplexing.
LEZIONE 4: Il Buffering nelle reti a pacchetto: lo Store & Forward (S&F). Tecniche alternative: Virtal Cut Through, Wormhole Routing. Esempi: Buffer in reti ottiche. Buffering per ritardo di propagazione: hot potato.
LEZIONE 5: S&F: Dimensionamento della taglia del pacchetto. (Gallager p. 93) Fattori di scelta: overhead, elaborazione intestazione, equità nella condivisione, errori sul canale. Pipelining e taglia ottima per traffico non interattivo. Taglia ottima per traffico sincrono (voce pacchettizzata). Il Problema degli echi sui pacchetti voce. Valori tipici della taglia del pacchetto in reti commerciali.
LEZIONE 6: Introduzione alla Teoria della Commutazione (Hinton cap. 3). Classificazione dei commutatori. Esempi: Doppio stadio con perfect shuffle, rete Omega, reti Banyan ed esempi di blocking. Commutatori non-blocking in senso stretto: Switch a matrice. Esempi di realizzazione a commutazione centrale e periferica: WDMA FDMA TDMA. Time slot interchangers. Commutatori Non-blocking in senso lato. Commutatori multistadio. Teorema di Clos. Reti di Clos.
LEZIONE 7: Commutatori TDM tipo TST, STS. Esempi di commutatori riarrangiabili. Teorema di Benes e dimostrazione basata sulla colorazione dei grafi bipartiti (Edge Coloring, Teorema di Konig). Reti di Benes e loro ottimalità asintotica.
LEZIONE 8: Controllo di reti Benes: Looping algorithm Introduzione alla struttura dei commutatori ATM: Reti self-routing. Batcher Sorting. Reti Batcher-Banyan. Batcher's bitonic sorter. Teorema di Batcher.

Analisi di prestazione dei commutatori
LEZIONE 9: Commutatori RNB slottati: Analisi di prestazione in traffico uniforme e senza buffer: throughput, perdite. Uso della Probability Generating Function (PGF).
LEZIONE 10: Commutatori con speed-up spaziale. Analisi di prestazione di rete Banyan senza buffer. Input vs Output Buffering: introduzione (dal paper: M. J. Karol, M. G. Hluchyj, and S. P. Morgan, ``Input versus output queueing on a space-division packet switch,'' IEEE Trans. Commun., vol. COM-35, pp. 1347--1356, Dec. 1987.)
LEZIONE 11: Output buffering: introduzione alla terminologia sulla teoria delle code. La legge di aggiornamento della coda discreta M/D/1. Calcolo PGF stazionaria della coda, e del suo valor medio. Legge di Little. Adattamento ai sistemi slottati e calcolo del ritardo medio nella coda M/D/1 discreta.
LEZIONE 12: Output buffering: struttura fisica. Il Knockout packet switch e sue prestazioni. Input buffering: introduzione. Confronto con output buffering: lo speed-up. Prestazioni: riassunto dei risulti principali. Effetto correlazioni sul vettore di ingresso. Effetto di bloccaggio del capofila.
LEZIONE 13: Analisi con un solo buffer per ingresso: calcolo del throughput. Estensione a infiniti buffer per ingresso: la coda generica di ingresso come una coda tempo discreta Geo/G/1. Coda Geo/G/1: legge di aggiornamento. Analisi dei valori medi .
LEZIONE 14: Geo/G/1: calcolo PGF, della media, e del ritardo medio (formula PK). Input buffering: calcolo del tempo di servizio del capofila con approssimazione geometrica. Reti Banyan con output buffer ad ogni elemento beta: calcolo del ritardo medio in funzione del throughput.

Processi stocastici nelle reti
LEZIONE 15: Processi di rinnovo (Leon Garcia, cap. 5). Medie a lungo termine. Teorema del rinnovo ed estensione con funzioni costo. Esempio: il busy time di un server. La renewal function e relativi teoremi. Teorema di Blackwell. Applicazione: età e tempo residuo di vita.
LEZIONE 16: Catene di Markov tempo-discrete (DTMC) (Leon Garcia, cap. 8). Definizioni. Matrice di transizione e sue proprietà. Esempi di DTMC. Distribuzione iniziale e al passo n-mo. Legge di aggiornamento. Distribuzione stazionaria. Esempio: packet voice. Distribuzione limite.
LEZIONE 17: Proprietà asintotiche delle DTMC. Classificazione degli stati di una DTMC. Irriducibilità. Esempi. Ricorrenza: tipi di classi. DTMC periodiche e aperiodiche. Ergodicità degli stati. Occupazione degli stati a lungo termine.
LEZIONE 18: Ricorrenza positiva e nulla. Proprietà asintotiche DTMC irriducibili. Unicità della distribuzione stazionaria in DTMC irriducibili. Forma canonica della matrice di transizione e significato fisico di DTMC ergodica.
LEZIONE 19: Esempi: la coda Geo/Geo/1 early arrival/late departures (EA/LD). DTMC: calcolo distribuzione stazionaria col bilancio di flusso. Equazioni di bilancio globali e generalizzazioni a macrostati. Interpretazione grafica. Esempi: la coda Geo/Geo/1 ED/LA. Catene di nascita e morte.
LEZIONE 20: Esempi di applicazione di DTMC: Età di un processo di rinnovo discreto. Processo di rinnovo alternato. Calcolo di probabilità di un numero pari di errori su una stringa di n bit con probabilità di errore dipendente dal bit.
LEZIONE 21: Esempi: Calcolo del throughput di un commutatore 2x2 con input buffering. Aggregabilità degli stati. Cenni a DTMC multidimensionali. La Geo/G/1 con buffer finiti. Regole di dimensionamento dei buffer.
LEZIONE 22: Catene assorbenti (AMC). Matrice fondamentale di una AMC e suo significato fisico. Vettore delle visite. Tempo di assorbimento e sua distribuzione. Esempi di applicazione: calcolo numero medio di hop in reti regolari con instradamento a deflessione. Distribuzione del tempo di assorbimento.
LEZIONE 23: Code tempo-continue. Processo di Poisson come limite del processo arrivi discreti di Bernoulli. Proprietà del processo di Poisson. Tempi di interarrivo: la distribuzione esponenziale. Proprietà di assenza di memoria. Somma e random splitting di processi di Poisson.
LEZIONE 24: Catene di Markov tempo-continue (CTMC). Tempo di soggiorno negli stati. Visione costruttiva di una CTMC. Distribuzione al tempo t. Legge di aggiornamento dello stato: equazioni di Chapman-Kolmogorov. Matrice dei generatori infinitesimali. Probabilità stazionarie ed equazioni di bilancio. Cenni ai Processi semi-Markov.
LEZIONE 25: La coda M/M/1. Legge di aggiornamento. Distribuzione a regime. Numero medio in coda e tempo medio d'attesa. FIFO: distribuzione del tempo di attesa. Teorema PASTA. Il processo di partenze dalla M/M/1. Risultati estendibili alla M/G/1.
LEZIONE 26: Catene di nascita e morte. Le code M/M/c, M/M/c/c, M/M/c/c/N e applicazioni ai PABX digitali. La coda M/G/1: formula PK.
LEZIONE 27: Reti di code: Teorema di Burke. Reti aperte di Code. teorema di Jeckson. Approssimazione di Kleinrock. Applicazioni: dimensionamento delle capacita' dati i flussi. Teorema di Jackson per reti chiuse. Mean Value Analysis.

Gli standard
LEZIONE 28: Il modello ISO OSI. Motivazioni: le reti come dilatazione fisica di un commutatore. Problematiche di interfaccciamento di reti e necessità di uno standard. Note sugli organismi di standardizzazione. Evoluzione storica delle trasmissioni a pacchetto e nascita del modello OSI. I sette strati.
LEZIONE 29: I sette livelli OSI: concetti base. Comunicazioni Peer to peer. Il concetto di servizio. PDU, entità e SAP. 1) Il livello fisico: esempi: collegamento diretto con RS232 e remoto tramite modem. L'interfaccia DTE-DCE.
LEZIONE 30: Lo strato fisico e la rete telefonica. I modem in banda fonica e banda base. La topologia della rete telefonica Italiana. Multiplexing TDM plesiocrono e sincrono. Lo standard SDH. La gestione delle linee e degli apparati nell'SDH. La rete ISDN.
LEZIONE 31: 2) livello di linea. Tecniche ARQ: stop and wait, Go back n, Selective repeat. Il controllo di flusso a finestra.
LEZIONE 32: 3) livello di rete. Indirizzamento. Reti a circuito virtuale e datagram. Instradamento: shortest path, multipath, gerarchico, flooding. Cenni agli algoritmi Bellman Ford e Djikstra.
LEZIONE 33: Ridiscesa a livello 2: Introduzione alle reti locali. Panoramica: Aloha, Ethernet, token ring, token bus, slotted ring, polling.
LEZIONE 34: Reti Broadcast: analisi di prestazione (Hammond cap. 5) Controllore ideale (M/D/1).
LEZIONE 35: Slotted Aloha: analisi come DTMC, con 1 buffer per ingresso. Instabilità. Binary exponential backoff.
LEZIONE 36: reti CSMA/CD: Ethernet. Calcolo prestazioni. Lo standard IEEE 802. Token ring (cenni).
LEZIONE 37: Sistemi slottati. Slotted ring. Calcolo throughput e ritardo. Ring Bidirezionale. Estensioni: reti multihop multiring magliate. Il Moore Bound.
LEZIONE 38: Da Little al legame throughput-delay in reti multihop. Confronti asintotici tra reti Shufflenet, Manhattan, e Ring unidirezionale. Connessione coi risultati sui commutatori blocking. Generalizzazioni. Esempio di rete single-hop con commutatore centrale, che diviene gradualmente multihop a causa dell'instradamento a deflessione.
LEZIONE 39: Risalita a livello 3): l' Internetworking. interconnessione di LAN in area privata tramite Bridge. Bridge trasparenti e source routing.
LEZIONE 40: interconnessione di MAN,WAN attraverso router e gateways. Cenni a Internet e TCP/IP. Descrizione funzioni di TCP. Introduzione ad ATM. Gli strati ATM. Internet ed ATM. Le classi di servizio. Il leaky bucket per traffic shaping.

Introduzione alle architetture strutturate:

[1] A. S. Tanenbaum, Computer Networks, 2nd Ed. --- Prentice Hall, 1989.

[2] D. P. Bertsekas, R. Gallager, Data networks, 2nd Ed. --- Prentice Hall, 1992.

[3] S. Gai, P. L. Montessoro, P. Nicoletti, RETI LOCALI Dal cablaggio all'internetworking, 2nd Ed., Scuola Superiore G Reiss Romoli, 1995.

Commutazione:

[4] A. Varma and C. S. Raghavendra Eds, Interconnection networks for multiprocessors and multicomputers: Theory and Practice --- IEEE Computer society press, 1991.

[5] H. S. Hinton ``An introduction to Photonic Switching Fabrics''. Plenum Press. 1993.

Analisi di Prestazione:

[6] D. P. Bertsekas, R. Gallager, Data networks, 2nd Ed. --- Prentice Hall, 1992.

[7] J. L. Hammond, P. J.P. O'Reilly, Performance analysis of Local Computer Networks --- Addison Wesley, 1986.

Processi stocastici:

[8] A. Leon-Garcia, Probability and random processes for electrical engineering, 2nd Ed. --- Addison Wesley, 1994.

[9] J. G. Kemeny et al., Finite mathematical structures --- Prentice Hall, 1959. Ch. 6.4 Absorbing Markov chains.

[10] S. M. Ross, Stochastic Processes, Wiley, 1983.

[11] J. J. Hunter, Mathematical Techniques of Applied Probability. Vol. 2: Discrete time models --- Academic Press, 1983. Ch. 9 Discrete Time Queueing Models.

[12] H. Kobayashi ``Discrete-time queueing systems,'' in G. Louchard, G. Latouche Eds, ``Probability Theory and Computer Science'' -- Academic Press, 1983 -- Part II:

Non esiste un testo specifico per il corso, benche' il riferimento [2] sia il testo che piu' si avvicina ai contenuti del corso. Si consiglia di consultare la bibliografia in biblioteca. Verranno distribuite fotocopie di alcuni articoli spiegati in classe.

Modalità  d'esame

Prova scritta (2 ore): esercizi teorici sulla parte analitica del corso.
Prova orale, subito dopo lo scritto, riguardante i protocolli.