RICERCA ITALIANA     

Programma di ricerca

Algoritmi per Internet e Web di prossima generazione: Metodologie, Progetto ed Esperimenti

Università di riferimento

Università degli Studi di ROMA "Tor Vergata" - INFORMATICA, SISTEMI E PRODUZIONE - ROMA(RM)

Responsabile dell'Unità di ricerca

Giuseppe Francesco ITALIANO

Descrizione

L'obiettivo principale della nostra attività di ricerca è lo sviluppo di tecniche e di metodologie per la progettazione di algoritmi e strutture dati efficienti su grafi, con particolare riguardo alla loro applicazione nel contesto delle reti di prossima generazione. Per affrontare i problemi collegati alla natura estremamente dinamica di queste reti (sulle quali si osserveranno rapide variazioni del traffico e della struttura topologica), accoppiata alla sensibilità delle applicazioni di rete ai guasti, intendiamo: 1. Progettare nuovi algoritmi e nuove metodologie per l'instradamento (routing) mediante tecniche basate sul cammino più breve (Task 2.1); 2. Progettare algoritmi robusti rispetto ai guasti ed agli errori di memoria, per affrontare problemi combinatori fondamentali collegati al progetto di motori di ricerca (Task 1.1) Poichè i problemi di rete, a livello sia di progetto che di esercizio, possono essere affrontati più efficacemente con l'ausilio di una corretta visualizzazione sia delle rete stessa che delle applicazioni, intendiamo anche occuparci di problemi di visualizzazione, e più precisamente: 3. Progettare nuove metodologie di visualizzazione ed implementare strumenti basati sul Web da utilizzare per studiare problemi di rete (Task 1.2 and 3.2). E' nostra intenzione incorporare le tecniche algoritmiche e di visualizzazione che saranno sviluppate in questo progetto in strumenti software efficienti e di facile impiego. La maggior parte dei nostri algoritmi saranno collaudati su piattaforme aperte (come Linux e/o Unix BSD), in maniera da valutarne e misurarne la competitività in scenari concreti. L'attività di ricerca proposta dalla nostra Unità è descritta di seguito più in dettaglio per ogni task a cui partecipa la nostra Unità. Task 1.1 Modelli e Paradigmi Algoritmici Introduzione Come è stato osservato nella descrizione dello stato dell'arte relativa al Task 1.1, i motori di ricerca ed altre applicazioni Web possono trarre notevoli benefici dalla progettazione di algoritmi robusti rispetto ad errori distruttivi nella memoria. Sebbene la replicazione dei dati costituisca un approccio naturale per proteggersi da questo tipo di guasti, essa può risultare molto inefficiente in un contesto dinamico, in cui gli oggetti da gestire sono complessi e di notevoli dimensioni. E' quindi naturale chiedersi se è possibile progettare algoritmi robusti rispetto agli errori che possono verificarsi, e quindi in grado di funzionare correttamente anche in presenza di errori nelle memorie, senza ricorrere ad una replicazione dei dati. Nell'ambito di questo task intendiamo progettare algoritmi di questo tipo per problemi combinatori fondamentali che sorgono nel progetto e nella implementazione di motori di ricerca (per esempio problemi di ricerca e di ordinamento). Fase 1 Esamineremo la progettazione di algoritmi robusti rispetto ad errori distruttivi che possono verificarsi nelle locazioni di memoria. In particolare intendiamo progettare algoritmi capaci di funzionare in presenza di errori altamente dinamici ed impredicibili, che possono verificare in qualunque posizione di memoria e possibilmente in maniera simultanea. Ci concentreremo su algoritmi che non mirano a recuperare i dati corrotti, ma piuttosto a funzionare correttamente sui dati non corrotti, senza utilizzo aggiuntivo di tempo o di spazio. Risultati attesi 1) Progettazione di nuovi algoritmi robusti rispetto agli errori per problemi combinatori fondamentali legati al progetto ed alla implementazione di motori di ricerca Fase 2 Poichè gli errori nelle memorie avvengono soprattutto nelle memorie meno costose, come ad esempio le memorie esterne, intendiamo esaminare se le tecniche ideate durante la Fase 1 possono essere adattate su memoria esterna, in modo da progettare algoritmi per la gestione di grandi quantità di dati in presenza di errori. Risultati attesi 1) Progettazione di modelli ed algoritmi robusti rispetto ad errori su memorie esterne Task 1.2 Metodologie di Visualizzazione Introduzione Partendo dalla nostra precedente esperienza di sviluppo di strumenti di visualizzazione in collaborazione con altre unità di ricerca in questo progetto, intendiamo creare nuovi strumenti basati su Java per la realizzazione di visualizzazioni animate sul Web, da utilizzare per studiare aspetti di rete. Sulla base del convincimento che un programmatore medio non deve spendere troppo tempo nella realizzazione di una animazione del comportamento di un blocco di codice, intendiamo sviluppare strumenti di visualizzazione leggeri e di facile impiego. Inoltre cercheremo di sfruttare le potenzialità offerte dal linguaggio Java per rendere i nostri strumenti quanto più possibile indipendenti da specifici sistemi operativi. Fase 1 Durante la Fase 1 intendiamo sviluppare nuovi approcci per rendere automatica (o quantomeno più semplice) la visualizzazione del software sul Web. In particolare intendiamo sviluppare strumenti basati su Java leggeri e di facile utilizzo per la creazione di visualizzazioni animate mediante l'integrazione di capacità di editing con il tradizionale approccio all'animazione guidata da programma. Risultati attesi 1) Sviluppo di strumenti basati su Java leggeri e di facile impiego per la visualizzazione di software sul Web. Fase 2 Valuteremo l'efficacia dei sistemi di visualizzazione del software sviluppati durante la Fase 1, in stretta cooperazione con altre Unità di ricerca del progetto. Risultati attesi 1) Valutazione e miglioramento degli strumenti di visualizzazione del software sviluppati durante la Fase 1. Task 2.1 Algoritmi per l'Instradamento su Internet Introduzione Insieme ad altre unità di ricerca in questo progetto, intendiamo progettare ed ingegnerizzare nuovi algoritmi per l'instradamento su Internet, basati su tecniche di cammino minimo, da impiegate in strumenti software di rete. Poichè le dinamiche delle reti sono estremamente veloci (a causa della variabilità del traffico e delle variazioni sia nella connettività di rete che nella disponibilità di risorse di commutazione e di trasmissione) il ricalcolo delle tabelle di instradamento deve essere altrettanto veloce. Ricollegandoci ad una tecnica molto recente [DI03], sostanzialmente differente dagli approcci precedenti, intendiamo utilizzare nuove proprietà combinatorie dei grafi, basate sulla ben nota proprietà di sottostruttura ottimale dei cammini minimi come nucleo per la risoluzione di problemi dinamici di cammino minimo a sorgente singola. Intendiamo anche sviluppare metodi per mantenere dinamicamente il "t-spanner" di un grafo, cioè un sottografo in cui le distanze originali sono approssimate a meno di un fattore t. Questo è particolarmente importante per ridurre il numero di collegamenti fisici in una rete di telecomunicazioni, possibilmente molto costosi, senza aumentare eccessivamente le distanze tra i router. Per sviluppare un ambiente di collaudo adeguato per gli algoritmi di instradamento proposti, intendiamo sviluppare degli strumenti per la generazione di strutture di rete tipiche di Internet di prossima generazione. In particolare l'obiettivo della nostra attività di ricerca è di rendere più efficiente il processo di simulazione di strutture di rete seguendo i modelli proposti nella letteratura, con particolare attenzione ai seguenti aspetti: a) il tempo necessario per la generazione; b) la relazione tra i parametri adottati per descrivere tipicamente una struttura di rete e quelli impiegati nei modelli considerati; c) la dinamica della rete simulata. L'obiettivo finale è quello di giungere ad un generatore multi-modello adatto a scopi simulativi, capace di generare un insieme di strutture di rete soggette ad una varietà di requisiti (per esempio, connettività, grado medio dei nodi, distribuzione dei guasti, variazioni della topologia). Fase 1 Esamineremo nuove tecniche algoritmiche per mantenere dinamicamente cammini minimi a sorgente singola. Vogliamo enfatizzare che questo è un obiettivo molto ambizioso. A differenza degli altri problemi su grafi dinamici, come per esempio il mantenimento dinamico di minimi alberi ricoprenti [HDT01], i problemi di cammini minimi dinamici sembrano molto più difficili: in effetti, nonostante l'esistenza di studi precedenti [RR96], trovare una soluzione migliore del ricalcolo dell'albero di cammino minimo da zero costituisce un problema irrisolto da più di quarant'anni. Per ottenere dei miglioramenti intendiamo estendere i risultati più recenti per cammini minimi "all-pairs" presentati in [DI03]. Intendiamo anche studiare metodi per mantenere dinamicamente il t-spanner di un grafo. Infine, intendiamo valutare il tempo di generazione dei modelli proposti in letteratura per la simulazione della struttura di rete e individuare le relazione tra i parametri utilizzati nel processo di generazione e quelli tipicamente usati per descrivere una struttura di rete. Risultati attesi 1) Progettazione di nuovi algoritmi per cammini minimi dinamici a sorgente singola e "t-spanner" dinamici; 2) Confronto di diversi modelli per la simulazione della struttura di rete Fase 2 Oltre a proseguire il nostro studio sui problemi dinamici di cammino minimo a sorgente singola, intendiamo valutare sperimentalmente le tecniche algoritmiche studiate nella Fase 1, sviluppando nuove euristiche per migliorare le prestazioni degli algoritmi proposti in ambienti reali, e collaudandoli su piattaforme aperte. Metteremo inoltre a punto algoritmi di instradamento dinamico esistenti mediante una attività estesa di validazione delle loro prestazioni in un ambiente di collaudo che rispecchi quanto più possibile modelli specifici delle reti Internet di prossima generazione, ed utilizzando l'esperienza acquisita per progettare i nuovi algoritmi. Risultati attesi 1) Ingegnerizzazione degli algoritmi ideati nella Fase 1 per l'instradamento su Internet 2) Caratterizzazione dei fenomeni di guasto e della evoluzione della topologia ai fini del loro impiego nel processo di simulazione della struttura. Si realizzerà inoltre una implementazione del simulatore di struttura. Task 3.2 Esplorazione e Visualizzazione del Web Introduzione Nell'ultimo decennio è stato ideato un notevole numero di tecniche per la rappresentazione grafica di strutture combinatorie riconducibili a grafi. La rappresentazione di siti web e di reti di telecomunicazioni può trarre grandi benefici da queste tecniche. In alcuni casi gli strumenti software per la visualizzazione di mappe Web vengono usati insieme a motori di ricerca e agenti di ricerca in modo da fornire una rappresentazione diretta dei grafi Web (come per esempio Mappuccino e WebSphinx). E' però tipicamente difficile per l'utente interagire con gli strumenti di visualizzazione per ottenere una rappresentazione personalizzata di qualche aspetto di interesse. In questo progetto abbiamo l'obiettivo di studiare nuovi algoritmi di visualizzazione basati sia su tecniche di fuoco più contesto che su modelli di mappa appropriati. In particolare, prevediamo di fornire una descrizione XML di strutture dati corrispondente alla nozione di query maps con applicazione agli algoritmi di ricerca e caching per motori di ricerca su web e applicazioni web-database. Fase 1 Durante la Fase 1 studieremo problemi algoritmici legati ad algoritmi di visualizzazione degli alberi basati su tecniche di fuoco più contesto, in modo da fornire un supporto grafico per il filtraggio di informazioni ridondanti e per la focalizzazione su siti vicini all'argomento di interesse. La maggior parte dei nodi rilevanti dovrebbero essere selezionati come punti focali di partenza, e si dovrebbero applicare tecniche di visualizzazione come la visualizzazione iperbolica in modo da permettere all'utente di percepire quale parte del grafo web riguarda gli argomenti più rilevanti per l'interrogazione effettuata. Risultati attesi 1) Studio di nuovi algoritmi e modelli di dati per grafi web per la visualizzazione di strutture dati di ricerca Fase 2 Realizzeremo gli algoritmi progettati nela Fase 1, sviluppando un prototipo di strumento di visualizzazione e mettendo a punto quelli esistenti usando diversi linguaggi grafici basati su XML (GraphXML, SVG) Risultati attesi 1) Implementazione, messa a punto ed applicazione dei modelli e degli algoritmi progettati durante la Fase 1.