logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-07042003-103440


Tipo di tesi
Tesi di laurea specialistica
Autore
Lazzarini, Riccardo
URN
etd-07042003-103440
Titolo
Algoritmi di routing per reti di interconnessione riconfigurabili
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
relatore Prof. Bonuccelli, Maurizio
Parole chiave
  • Clos networks
  • multirate
  • rearrangeable
Data inizio appello
21/07/2003
Consultabilità
Completa
Riassunto
In un sistema di comunicazione le entità che ne fanno parte comunicano attraverso una struttura che prende il nome di rete d’interconnessione.
Tra le caratteristiche auspicabili per una rete di interconnessione è l’essere non bloccante, cioè connettere più entità indipendentemente dalle condizioni di traffico sulla rete.
Questa tipologia di rete garantisce migliori prestazioni ai sistemi che la utilizzano spesso a fronte di elevati costi di realizzazione. Tra gli obiettivi più importanti della progettazione, c’è quindi quello di contenerne i costi.
La teoria delle reti non bloccanti è nata negli anni 50 con le ricerche di C. Clos per risolvere problematiche inerenti la progettazione di reti telefoniche. Da allora, nel corso degli anni, lo studio di tale teoria è stato ripreso ed ampliato da numerosi autori.
La teoria originale, è stata sviluppata tenendo conto che i sistemi di switch utilizzati nelle reti, erano in grado di far “transitare” su un collegamento (link) una sola conversazione alla volta. In tal modo, per tutta la durata di una chiamata, i link impegnati, non potevano essere utilizzati per soddisfare altre richieste. Questa modalità di funzionamento è chiamata classical switching (CS).
Tra gli anni 60 e 70, lo sviluppo tecnologico, condusse alla realizzazione di switch digitali che, assieme a tecniche di mutiplexing, permisero la condivisione di uno stesso collegamento da parte di più conversazioni.
Dagli anni 80 in poi è cresciuto l’interesse verso quei sistemi di comunicazione capaci di gestire applicazioni con caratteristiche molto diverse. In particolare questi sistemi sono progettati per soddisfare richieste che necessitano di una banda che può variare da pochi bit a centinaia di mega bit per secondo. Il traffico da gestire infatti, non è più solo telefonico, ma sono flussi di dati di varia natura ognuno con diverse esigenze di banda ( fax, video, audio, ecc...). Anche in questi sistemi, ogni collegamento può essere utilizzato da più richieste contemporaneamente, ma, a differenza dei precedenti, ogni connessione può “consumare” una frazione arbitraria della banda messa a disposizione da un link. In queste circostanze si parla di ambiente multirate.
Tra le reti d’interconnessione non bloccanti, una categoria particolarmente importante è costituita dalle reti di Clos. Dalla loro comparsa negli anni cinquanta, esse continuano ad essere oggetto di ricerca, poiché costituiscono l’elemento base da cui partire per costruire altre reti non bloccanti.
Nel presente lavoro di tesi affronteremo uno dei classici problemi inerenti le reti non bloccanti: la riconfigurabilità delle reti di Clos negli ambienti classical switching e multirate. In particolare, faremo un’ampia rassegna sull’argomento e proporremo alcuni nuovi risultati.
File