MODELLO

MINISTERO DELL'ISTRUZIONE, DELL'UNIVERSITÀ E DELLA RICERCA
Dipartimento per la Programmazione il Coordinamento e gli Affari Economici
Servizio per lo sviluppo e il Potenziamento delle Attività di ricerca (SSPAR)
PNR 2001-2003 (FIRB art.8) D.M. 199 Ric. del 8 marzo 2001

Anno 2001 - Protocollo: RBNE01T7BC

Parte I "Il Progetto"

MACRO OBIETTIVO	Crescita Competitiva Sostenibile
PROGRAMMA STRATEGICO	Tecnologie abilitanti per la Societa' della conoscenza ICT
Proposta progettuale attinente	Metodi analitici e numerici avanzati

1.1 Titolo del Progetto di Ricerca

Software di Ottimizzazione e Simulazione per Reti

Optimization and Simulation Software for Networks

1.2.a Risultati attesi

nº	Articolazione	Descrizione
1.	Modelli ed algoritmi di simulazione e di ottimizzazione per la progettazione e la gestione di reti	sviluppo di algoritmi per diversi problemi di progettazione di reti di comunicazione, comprensivi di localizzazione e dimensionamento dei nodi, di specifica delle connessioni di rete, di analisi del traffico per domande deterministiche e stocastiche.
2.	Sistemi di code e distribuzioni e traffico autosimili	studio delle caratteristiche del traffico di rete di tipo autosimile e sviluppo di un simulatore del traffico di reti di telecomunicazioni.

1.2.b Costituzione, potenziamento e messa in rete di Centri di alta qualificazione scientifica, pubblici o privati

Alla fine del 1999 è stato costituito in Italia il CRIFOR, Centro di Ricerca e Formazione per l'Ottimizzazione su Reti. Si tratta di una struttura dell'Università di Cagliari, alla quale sono stati invitati ad aderire ricercatori di tutte le università e centri di ricerca italiani interessati.
Gli scopi del CRIFOR sono:
- sviluppare ricerche e coordinare progetti di ricerca, nazionali ed europei, relativi ai fondamenti dell'Ottimizzazione su Reti e alle principali applicazioni, con particolare riferimento alla gestione del territorio, ed alle reti idriche, elettriche, di comunicazione e di trasporto;
- promuovere programmi di formazione post-laurea e post-dottorato sui fondamenti e sulle applicazioni dell'Ottimizzazione su Reti;
- analizzare, produrre e rendere disponibile software di Ottimizzazione su Reti, anche attraverso interfacce grafiche aventi l’obiettivo di favorire un accesso amichevole al software di Ottimizzazione su Reti;
- organizzare e gestire un sito Internet dedicato all'Ottimizzazione su Reti, per la presentazione e la distribuzione del software di base e applicativo, comprensivo dei problemi test e dei risultati sperimentali ottenuti.
Nei primi due anni di attività, hanno aderito al CRIFOR diverse decine di studiosi universitari e degli EPR che operano nell'ambito delle metodologie matematiche per problemi di rete, e che sono interessati allo studio e alla messa a punto di software di ottimizzazione su reti, in particolare al software di base e al software per la risoluzione di problemi di progetto e gestione di reti di comunicazione.
Dall'inizio del 2001, molti degli aderenti al CRIFOR hanno operato per consorziare i loro gruppi di ricerca, presso università italiane e Istituti del CNR, al fine di operare come una vera e propria "rete di ricerca" sia per la realizzazione degli obiettivi di ricerca precedentemente esposti, sia per la realizzazione del sito web per la raccolta e la diffusione del software di Ottimizzazione su Reti. Attualmente si sta istituzionalizzando la "rete di ricerca CRIFOR" attraverso adeguati strumenti di funzionamento scientifico, tecnico e amministrativo.
La rete di ricerca CRIFOR si sta sviluppando gradualmente: è stato creato il supporto tecnico-logistico presso l'Università di Cagliari, e sono stati presentati progetti di ricerca congiunti, aventi il comune obiettivo di produzione, validazione, standardizzazione e diffusione di software di Ottimizzazione e Simulazione su Reti. Uno di questi progetti è stato approvato ed è attualmente in corso di svolgimento, mentre per un secondo progetto si attende il completamento della fase di valutazione. Inoltre, alcuni dei gruppi sono inseriti in un progetto europeo per la gestione di risorse idriche.

Si è deciso di partecipare al FIRB con l’obiettivo di potenziare la rete di ricerca CRIFOR, individuando nel tema delle reti di comunicazione uno degli elementi cardine della "Information and Communication Technology". Il presente progetto è incentrato, in particolare, sullo studio dei nuovi problemi di progetto e gestione di reti di comunicazione che si stanno presentando a seguito dello sviluppo della tecnologia, sia a livello di "progetto e dimensionamento" delle reti, a livello di "localizzazione di nodi e canali delle reti", nella "valutazione della gestione del traffico di rete nella fase progettuale", e a livello delle interrelazioni tra tali componenti. Il software attualmente esistente risulta infatti carente per due aspetti: non rispondenza alle future caratteristiche tecnologiche delle reti, ed inadeguatezza a risolvere problemi di grosse dimensioni.
Lo sforzo di ricerca che ci si prefigge è notevole. Esso si basa su una potente ricerca di base relativa a fondamenti e a metodologie, e richiede l'apporto sinergico di competenze diverse nella definizione di nuovi strumenti di calcolo e nella produzione del relativo software. La ricerca ha l’obiettivo di fornire il patrimonio di software sviluppato alla comunità scientifica nazionale ed internazionale, alle imprese e alle amministrazioni, al fine di ampliare al massimo le conoscenze e di stimolare ai più alti livelli la competizione per lo sviluppo di strumenti software di qualità e di facile utilizzo.
I nodi della rete di ricerca direttamente coinvolti nel presente progetto sono otto. Essi si caratterizzano per un'alta qualificazione scientifica, testimoniata, tra l'altro, da un apprezzamento delle ricerche svolte anche a livello internazionale.
Tre nodi, rispettivamente presso il Politecnico di Milano, l'Università di Modena e Reggio Emilia e l'Università di Roma "La Sapienza", sono stati creati attorno alle migliori competenze presenti in Italia nel campo dello studio e della risoluzione di problemi di progetto e gestione di reti di comunicazione.
Due nodi, rispettivamente presso l'Università di Salerno e l'Università della Calabria, coinvolgono due Centri di Eccellenza finanziati dal MIUR, rispettivamente il "Centro di metodi e sistemi per l'apprendimento e la conoscenza" ed il "Centro di calcolo ad alte prestazioni per elaborazioni parallele e distribuite".
Un nodo, presso l'IAC del CNR, raccoglie significative competenze presenti nelle tre università romane e in altri Istituti del CNR, formando un aggregato di altissima potenzialità di ricerca.
Il nodo dell'Università di Cagliari svolge, tra l'altro, il ruolo di supporto tecnico all'intero sistema di rete, e cura tutta l'attività di standardizzazione, valutazione e diffusione del software.
Infine, il nodo dell'Università di Pisa, riconosciuto internazionalmente come uno dei migliori poli di ricerca sull'ottimizzazione di reti e sul relativo software, svolge il ruolo di coordinamento e stimolo dell'intero sistema di rete e, più in generale, dell'intero CRIFOR.
Altri laboratori di ricerca universitari di altissimo livello partecipano inoltre al progetto come collaboratori nelle UR di cui sopra.

Una ricaduta importante che si intende raggiungere col potenziamento della rete consiste nell’aggregazione di altri centri di ricerca, anche privati, istituzionalmente impegnati sul fronte della Ricerca e Sviluppo, al fine di ridurre il "gap" tra ricerca di base di alta qualità e ricadute del "know-how" in ambito produttivo e sociale.
Si prospetta infatti, al termine del triennio di attività, di poter contare su una rete di ricerca sparsa in oltre 30 sedi, che coinvolga all'incirca 250 studiosi e ricercatori nei settori pubblici e privati, con una forte interazione con il mondo della produzione e dei servizi, e con significativi collegamenti con analoghe realtà presenti in Europa e nel Nord-America.

CRIFOR, Network Optimization Research and Education Center, has been constituted at the end of the year 1999. CRIFOR is a facility of the University of Cagliari, which can be joined by all the interested researchers of other Italian universities and research centers.

The main objectives of CRIFOR are:
- to develop research and to coordinate national and European research projects related to the fundamental principles of network optimization and its applications, especially involving land planning issues and hydraulic, electric, telecommunication and transportation networks;
- to promote training programs for graduate students focused on the foundations and applications of network optimization;
- to analyze, produce and release network optimization software, complemented with graphical interfaces to facilitate its utilization;
- to plan and manage a web site dedicated to network optimization, in order to present and distribute the software of network optimization, including benchmark instances and computational results.

In the first two years of activity, CRIFOR has been joined by several dozens of university and research institution researchers, who operate in the field of mathematical methodologies for network problems and who are interested in the study and development of network optimization software, in particular basic software and software for solving telecommunication network planning and management problems.

Since the beginning of 2001, many CRIFOR supporters have been working to pool their research groups, in Italian universities and National Research Council (CNR) centers, with the objective of acting as a true "research network" aiming to achieve the research targets set out above and realize the web site for network optimization software gathering and distribution. Currently, the "CRIFOR research network" is being institutionalized through adequate tools of scientific, technical and administrative functioning.

The CRIFOR research network is gradually developing: a technical-logistic support has been created in Cagliari, and many joined research projects have been proposed, with the common objective of producing, validating and standardizing the network optimization and simulation software.
One of these projects has been approved and is already in progress; a second one is being processed for evaluation.
Further, some research groups are involved in a European project for water resource management.
It has been decided to join the FIRB with the aim of strengthening the CRIFOR research network, since we identified in the telecommunication networks the core element of the "Information and Communication Technology". The current project is focused, in particular, on the study of new telecommunication network planning and management problems which have been recently arising as a consequence of the technological development in the network "planning and sizing", in the "location of network nodes and channels", in the "evaluation of the network traffic management during the planning phase", and in the interrelationships among those components. The software currently available, in fact, is not satisfactory under two main respects: lack of correspondence with the future technological features of networks, and inadequacy to solve large scale problems.

The required research effort is remarkable. It finds its basis on an effective research concerning fundamental principles and methodologies, and requires the synergistic contribution of different expertise for defining new computational tools and producing the corresponding software. The research aims at supplying national and international scientific communities, companies and authorities with the resulting software packages, in order to widen knowledge as much as possible and stimulate competition for the development of high quality and user friendly software tools.

There are eight nodes of the research network currently involved in the project. They are all characterized by a very high scientific qualification, which is also testified by the international appreciation expressed for the research already performed.
Three nodes, corresponding to research groups at the Politecnico di Milano, the University of Modena and Reggio Emilia, and the University of Rome "La Sapienza" respectively, have been created around the best Italian expertise in the field of the study and solution of communication network planning and management problems.
Two nodes, corresponding to research groups at the University of Salerno and the University of Calabria, involve two "Centers of Excellency" financed by the MIUR: the "Center of methods and systems for learning and knowledge" and the "Center of high performance computations for parallel and distributed processing".
A node, at the IAC of the CNR, gathers remarkable competencies coming from the three universities of Rome and other CNR institutions, thus forming a very powerful research aggregate.
The node at the University of Cagliari covers the important task of being the technical support to the whole network system, and takes care of the software standardization, evaluation and diffusion activities.
Finally, the node at the university of Pisa, internationally acknowledged as one of the best research poles in the field of network optimization and software development, operates as coordinator and incentive for the whole network system and, more generally, for the whole CRIFOR.

A relevant spin-off we aim to achieve by strengthening the network consists in aggregating new research centers, even private ones, which will be institutionally engaged in the R&D domain, so as to reduce the gap between basic high quality research and spin-off of the "know-how" in the productive and social sector.
We expect, in fact, that at the end of the three-year activity, we can rely on a research network spread out over 30 centers, involving around 250 scientists and researchers both in the private and public sector, with a strong interaction with the production and service world, and with significant connections with similar realities in Europe and North America.

1.3 Abstract del Progetto di Ricerca

Nel progetto di ricerca si affrontano alcune tematiche specifiche dei problemi di progetto e gestione di reti di comunicazione, con l'obiettivo di studiare, mettere a punto, validare e diffondere il relativo software di ottimizzazione e/o simulazione.

Lo stato dell'arte attuale risulta in gran parte obsoleto: da una parte il continuo evolversi della tecnologia della comunicazione comporta una ridefinizione delle caratteristiche peculiari delle reti in esame, dall'altra le dimensioni stesse dei problemi da risolvere crescono continuamente, rendendo inapplicabili gli strumenti software predisposti solo alcuni anni fa.

Il progetto è incentrato sulla produzione di software per la soluzione dei problemi che si intendono studiare. Il software prodotto verrà standardizzato, testato e documentato secondo specifiche funzionali predefinite, e diffuso nell'ambito della rete di ricerca CRIFOR come descritto nell'attività 1 del Workpackage 1.

Al progetto partecipano 7 Unità di Ricerca, composte da ricercatori del settore di alto livello scientifico, riconosciuto internazionalmente e certificato dalla vasta letteratura scientifica prodotta. Le istituzioni incaricate di organizzare le Unità di Ricerca sono: il Dipartimento di Informatica dell'Università di Pisa, il Dipartimento di Scienze e Metodi dell'Ingegneria dell'Università di Modena e Reggio Emilia, il Dipartimento di Elettronica, Informatica e Sistemistica dell'Università della Calabria, il Dipartimento di Informatica e Sistemistica dell'Università di Roma "La Sapienza", il Dipartimento di Elettronica e Informazione del Politecnico di Milano, L'Istituto per le Applicazioni del Calcolo del CNR, il Centro di Ricerca in Matematica Pura e Applicata dell'Università di Salerno. L'Unità di Ricerca dell'Università di Pisa svolge il coordinamento dell'intero progetto ed è responsabile del potenziamento della rete di ricerca CRIFOR e del suo nodo centrale presso l'Università di Cagliari.

Al progetto partecipano 85 tra professori, ricercatori, assegnisti e borsisti, appartenenti a 12 istituzioni universitarie, 4 centri di ricerca italiani, e 3 università estere.

Il costo globale del progetto è stimato in quasi 4 miliardi, di cui 838 Milioni sono richiesti per la stipula di 6 contratti triennali per giovani ricercatori. Oltre 930 Milioni sono riservati per il cofinanziamento.

Il progetto è articolato in 4 WorkPackages, per un totale di 13 attività distinte. Quasi tutte le attività prevedono la realizzazione di software di ottimizzazione e simulazione. Tra gli obiettivi fondamentali della ricerca vi è infatti quello di realizzare una libreria di software per il progetto e la gestione di reti, che verrà messa a disposizione sia della comunità scientifica che delle aziende pubbliche e private, tramite la rete CRIFOR.

Il WP1, dal titolo "Strumenti di supporto alle decisioni per il progettista ed il gestore delle reti di telecomunicazione", è dedicato alla raccolta e standardizzazione del software, alla predisposizione di un sistema di supporto alla progettazione di reti, e alla valutazione economica dell'offerta di servizi di rete e delle strategie aziendali.

Il WP2 è dedicato allo studio di diversi problemi di progetto di reti, quali il Multicommodity Network Design, il Network Loading (splittable e unsplittable), il Survivable Network Design, il Reserve Network Dimensioning, la progettazione con valutazione di domande aleatorie. Il software da sviluppare è di vario tipo: dalle tecniche euristiche più sofisticate (metaeuristiche) ai metodi esatti basati su Branch&Cut, allo studio dei rilassamenti lagrangiani, ecc.

Il WP3 è dedicato alla localizzazione e dimensionamento delle apparecchiature presso i nodi della rete. Vengono affrontati, a largo spettro, i problemi di localizzazione e dimensionamento; inoltre, vengono affrontati problemi puntuali quali l'assegnazione di frequenze ai nodi di una rete a celle, l'assegnazione di potenza e frequenze ai nodi di una rete di trasmissione radio-televisiva digitale, il Service Network Design, la localizzazione di interconnessioni tra diversi livelli di reti, la localizzazione e dimensionamento di concentratori in reti LAN. In molti dei problemi elencati si studierà anche il contemporaneo problema del bilanciamento dei carichi, per un utilizzo ottimale delle reti stesse. Il software prodotto consisterà di molti algoritmi euristici e diversi metodi esatti, con particolare riguardo alle tecniche di Branch&Cut&Price e di Column Generation.

Il WP4 affronta problemi legati all'instradamento della domanda nelle reti di comunicazione e alla conseguente valutazione dei flussi di traffico, al fine di migliorare l'utilizzo delle reti, di prevenire i sovraccarichi, di simulare le variazioni di carico delle reti a seguito di domande aleatorie. Più specificatamente, si studieranno problemi di scelta di due o più cammini per instradare il traffico, per ciascuna coppia o/d, problemi di instradamento di pacchetti di dati basati sull'Internet Protocol (IP) secondo le tecniche OSPF e MPLS, problemi di reinstradamento a seguito di modifica delle reti, la simulazione di traffico di tipo autosimile (self-similar). Il software di ottimizzazione che verrà sviluppato nell'ambito di questo WP consiste in euristiche innovative di ricerca locale e nel miglioramento di tecniche esatte, in particolare di Column Generation. Si proporranno anche due diversi simulatori, per MPLS-IP e per i flussi di traffico self-similar.

Comune a tutte le attività è anche la produzione eminentemente scientifica, mediante comunicazioni a convegni, rapporti tecnici, pubblicazioni su riviste a diffusione internazionale, organizzazione di workshop e meeting, ecc.

A completamento della ricerca, si è progettato anche il potenziamento del nodo centrale della rete di ricerca CRIFOR, presso l'Università di Cagliari, affinché l'attività di raccolta, testing, validazione, documentazione e diffusione del software di ottimizzazione e simulazione per reti di comunicazione e telecomunicazione possa essere potenziata e proseguita oltre la scadenza triennale del presente progetto. Per tale potenziamento, cui contribuiscono anche l'Università di Cagliari, la Regione Sardegna e alcune industrie sarde, si richiede un finanziamento ad hoc di 435 Milioni.

The research project considers topics on planning and management of communication networks, with the objective of studying, producing, validating and spreading the corresponding optimization and/or simulation software.

The state of the art is for the major part obsolete: on the one hand the communication technology has been continuously evolving, calling for a new definition of the specific characteristics of the networks under study; on the other hand software tools that were developed few years ago are no longer able to deal with the current increased problem sizes.

The core part of the project consists of producing software for the solution of different problems. The resulting software will be standardized, tested, and documented according to predefined functional specifications and released in the CRIFOR research network as described in Activity 1 of Work Package 1.

Seven units of research, involving high level researchers in the field, internationally known and recognized for their scientific production, are part of the project. The institutions in charge of the organization of the units of research are: the "Dipartimento di Informatica" of the University of Pisa, the "Dipartimento di Scienze e Metodi dell'Ingegneria" of the University of Modena and Reggio Emilia, the "Dipartimento di Elettronica, Informatica e Sistemistica" of the university of Calabria, the "Dipartimento di Informatica e Sistemistica" of the University "La Sapienza" of Rome, the "Dipartimento di Elettronica e Informazione" of the Polythecnic of Milan, the "Istituto per le Applicazioni del Calcolo" of the National Research Council, the "Centro di Ricerca in Matematica Pura e Applicata" of the University of Salerno. The Research Unit of the University of Pisa coordinates the entire project and is responsible for the strengthening of the CRIFOR research network and the central node at the University of Cagliari.

85 among professors, researchers, and teaching assistants belonging to 4 research centers and 12 universities in Italy and 3 foreign universities take part in the project.

The total cost of the project is estimated in about 4 billion liras, including 838 million liras to stipulate 6 triennial contracts for young researchers. More than 930 million liras are set aside for co-financing.

The project consists of 4 Working Packages, for a total of 13 specific activities. Almost all the activities imply the development of optimization and simulation software. One of the key objectives of the project is indeed the implementation of a software library for network planning and management that will be made available - via the CRIFOR network - to the scientific community as well as to private and public companies.

The WP1 goes under the name of "Decision support tools for the telecommunication network planners and managers" and is dedicated to collecting and standardizing the available software, setting up a network planning support system, and evaluating from the economic point of view the market of network services in terms of offers and business strategies.

WP2 deals with the study of network planning problems, such as Multicommodity Network Design, (Splittable and Unsplittable) Network Loading, Survivable Network Design, Reserve Network Dimensioning, Stochastic Demand Planning. Several different programming techniques are envisioned: from the more sophisticated heuristics (metaheuristics) to exact methods based on Branch&Cut, lagrangean relaxation, etc.

WP3 concerns equipment location and dimensioning at the network nodes. Together with the generic problems of location and dimensioning, more specific problems such as frequency assignment to the nodes in a cellular network, power and frequency assignment to the nodes in a digital broadcasting network, the Service Network Design, location of the connections between different network layers, location and dimensioning of LAN network concentrators are studied. Many of the aforementioned problems address the question of load balancing for the optimal exploitation of networks. The resulting software consists of heuristic algorithms and several exact solution techniques, with a particular attention to Branch&Cut&Price and Column Generation methods.

WP4 tackles problems related to the routing of demand in communication networks and the subsequent evaluation of traffic flows, in order to enhance network utilization, to prevent overload, to simulate load variation due to the stochasticity of demand. More specifically, we will study problems related to the choice of one or more paths to route traffic between each origin-destination pair, problems of routing data packages based on the internet protocol (IP) according to the OSPF and MPLS techniques, problems of rerouting after network changes, simulation of self-similar traffic. The optimization software which will be developed within this WP consists of innovative local search heuristics and the enhancement of exact techniques, in particular Column Generation. Two simulators for the MPLS-IP and self-similar traffic flows will be proposed.

Common to all activities is also the scientific production, through conference presentations, technical reports, publication in international journals, workshop and meeting organization, etc.

To complete the project, we also planned to strengthen the central node of the CRIFOR research network, at the University of Cagliari, so that the activities of collecting, testing, validating, documenting and spreading the optimization and simulation software for communication and telecommunication networks can be maintained and improved beyond the three years term of this project. The University of Cagliari, the Sardegna Region and some sardinian companies are already contributing towards this goal, for which a complementary "ad hoc" financing of 435 million liras is required.

1.4 Informazioni generali

1.4.1 Durata del Progetto di Ricerca	36 mesi
1.4.2 Mesi uomo complessivi dedicati al Progetto di Ricerca	716
1.4.3 Costo totale del Progetto (MLit)	3.935 (2032.26 KEuro)
1.4.4 Finanziamento richiesto (MLit)	2.161 (1116.06 KEuro)
1.4.5 Numero di contratti triennali per giovani ricercatori	6
Costo totale (MLit)	838 (432.79 KEuro)
1.4.6 Numero di contratti triennali per ricercatori di chiara fama	0
Costo totale (MLit)	0 (0.00 KEuro)

1.4.7 Numero delle Unità di Ricerca (UR) coinvolte	7
1.4.8 Quota % minima di partecipazione di una singola UR al costo totale della Proposta Progettuale	11

nº	Istituzione	Numero UR	Quota % complessiva di partecipazione delle UR al costo totale della Proposta Progettuale
1.	CENTRO DI RICERCA IN MATEMATICA PURA E APPLICATA	1	16
2.	CONSIGLIO NAZIONALE DELLE RICERCHE (CNR)	1	13
3.	POLITECNICO DI MILANO	1	14
4.	UNIVERSITA' DEGLI STUDI DELLA CALABRIA	1	11
5.	UNIVERSITA' DEGLI STUDI DI MODENA E REGGIO EMILIA	1	16
6.	UNIVERSITA' DEGLI STUDI DI ROMA "LA SAPIENZA"	1	14
7.	UNIVERSITA' DI PISA	1	17
		7

1.4.11 Infrastrutture

Numero di Infrastrutture	7
Costo Totale (MLit)	435 (224.66 KEuro)
Disponibilità a stralciare e rimodulare le previsioni delle Infrastrutture in Presenza di un Progetto di Infrastrutture comuni ad uno o più Grandi Progetti Obiettivo	SI

1.5 Soggetto Istituzionale contraente

Denominazione	Università di Pisa
Natura giuridica	Universita'
Domicilio fiscale	Lungarno Pacinotti 43
CAP	56100	Città	Pisa	Provincia	PISA
Telefono	050-2212111	Fax	050-40834	Email	uo6@adm.unipi.it
Codice fiscale	80003670504	P.IVA	00286820501
Codice anagrafe ricerche

1.5.a Legale rappresentante

Cognome	MODICA	Nome	LUCIANO	Data di Nascita	04/01/1950
Sesso	M	Codice Fiscale	MDCLCN50A04C351O	Luogo di Nascita	CATANIA
		Provincia	CATANIA	Nazione	ITALY

1.6 Parole chiave

1.	Progettazione di Reti
2.	Localizzazione di apparati
3.	Istradamento di comunicazioni
4.	Software
5.	Simulazione
6.	Modelli economici

1.	Network Design
2.	Device Location
3.	Transmission Routing
4.	Software
5.	Simulation
6.	Economic models

1.7 Coordinatore scientifico della ricerca (Principal Investigator)

PALLOTTINO	STEFANO	PLLSFN45P26H501M
(cognome)	(nome)	(CF)
Professore Ordinario	MAT/09	26/09/1945
(qualifica)	(settore)	(data di nascita)
Universita' di PISA	Dip. INFORMATICA
(Istituzione di appartenenza) (art.5, c.1, DM citato)	(Dipartimento/Istituto/Divisione/Settore)	(posizione)
050/2212737	050/2212726	pallo@di.unipi.it
(prefisso e telefono)	(numero fax)	(indirizzo posta elettronica)

Referenze

nº	Cognome	Nome	Email	Istituzione
1.	Ahuja	Ravindra K.	ahuja@ufl.edu	University of Florida (USA)
2.	Sorrentino	Roberto	sorrent@unipg.it	Università di Perugia
3.	Crainic	Teodor Gabriel	theo@crt.umontreal.ca	CRT - Univ. de Montreal (Canada)

1.8 Curriculum scientifico

Laurea in Matematica, novembre 1969, Univ. Roma

Borsista C.N.R., 5/70 - 7/73, (con servizio militare)
Ricercatore C.N.R., I.A.C. "Mauro Picone", 8/73 - 10/87
Professore Associato di Ricerca Operativa, Dip. Informatica, Univ. Pisa, 11/87 - 10/94
Professore Straordinario di Ricerca Operativa, Ist. Elettronica, Univ. Perugia, 11/94 - 10/97
Professore Ordinario di Ricerca Operativa, Dip. Informatica, Univ. Pisa, dall'11/97

Ricerche nel campo dell'ottimizzazione di reti; applicazioni su reti idriche, di trasporto e di comunicazione: studio di modelli, produzione di algoritmi, valutazioni sperimentali.

Visiting Scientist presso Univ. Montréal (Canada), M.I.T. (USA), CSIRO (Australia), Univ. Libre de Bruxelles (Belgium), Univ. Florida (USA), Univ. Cagliari.

Ha insegnato presso le Università di Roma "La Sapienza", Pisa, Siena, Perugia.

E` autore di oltre 70 lavori scientifici, ha curato una monografia e due numeri speciali di riviste a diffusione internazionale.

"Laurea" in Mathematics, Univ. Rome, Nov. 1969

Fellow C.N.R. 5/70 - 7/73 (with military service)
Researcher, C.N.R-I.A.C. "Mauro Picone", 8/73 - 10/87
Associate Professor of Operations Research, Dept. Comp. Sci., Univ. Pisa, 11/87 - 10/94
Professor of Operations Research, Inst. Electronics, Univ. Perugia, 11/94 - 10/97
Professor of Operations Research, Dept. Comp. Sci., Univ. Pisa, from 11/97

His research field is Network Optimization methods and algorithms, with application in water distribution, transport and communication networks: models, algorithms, and experiments evaluation.

Visiting Scientist at Univ. Montréal (Canada), M.I.T. (USA), CSIRO (Australia), Univ. Libre de Bruxelles (Belgium), Univ. Florida (USA), Univ. Cagliari.

He taught at the Universities of Roma "La Sapienza", Pisa, Siena, Perugia.

He is author of more than 70 scientific papers, editor of one book and of two special issues of journals with international circulation.

1.9 Pubblicazioni scientifiche più significative del Coordinatore della Ricerca

nº	Pubblicazione
1.	AHUJA R. K.; ORLIN J. B.; PALLOTTINO S.; SCUTELLÀ M. G. (?). Minimum time and minimum cost path problems in street networks with traffic lights TRANSPORTATION SCIENCE. Univ. Pisa, Dip. Informatica, TR 13/99, revised May 2001.
2.	MALUCELLI F.; NONATO M.; PALLOTTINO S. (1999). Demand Adaptive Systems: some proposals on flexible transit In CIRIANI T.A.; GLIOZZI S.; JOHNSON E. L.; TADEI R. Operational Research in Industry. pp. 157-182 ISBN: 0-333-74548-5 LONDON: McMillan Press Ltd (UNITED KINGDOM)
3.	NGUYEN S.; PALLOTTINO S.; MALUCELLI F. (2001). A modeling framework for the passenger assignment on a transport network with time-tables* TRANSPORTATION SCIENCE. (vol. 35 pp. 238-249)*
4.	PALLOTTINO S.; SCUTELLÀ M. G. (1997). Dual Algorithms for the Shortest Path Tree Problem* NETWORKS. (vol. 29 pp. 125-133)*
5.	PALLOTTINO S.; SCUTELLÀ M. G. (1998). Shortest path algorithms in transportation models: classical and innovative aspects. In MARCOTTE P.; NGUYEN S. Equilibrium and Advanced Transportation Modelling. pp. 245-281 ISBN: 0-7923-8162-9 BOSTON: Kluwer Acad. Publ. (UNITED STATES)

1.9.a Titoli scientifici più significativi del Coordinatore della Ricerca

1) Partecipazione a progetti di ricerca
Ha partecipato ai seguenti progetti nazionali con responsabilità di coordinamento di linee di ricerca:
Progetto Finalizzato CNR "Energetica" - 1976/78
Progetto Finalizzato CNR "Informatica" - 1980/83
Progetto Finalizzato CNR "Trasporti" - 1982/87
Progetto Strategico CNR "Tecnologie dell'Informazione" - 1985/87
Progetto MURST 40% "Metodi di ottimizzazione per le decisioni" - 1987/89
Progetto MURST 40% "Gestione dei flussi nei sistemi flessibili di produzione" - 1990/93
Progetto Finalizzato CNR "Trasporti-2" - 1992/98
Progetto Coordinato CNR "Integrazione logistica di sistemi industriali a rete" - 1995/97
Progetto MURST 40% "AAA - Autocordinamento di agenti autonomi" - 1997/98
Progetto MURST cofinanziato "COSO - Algoritmi per l'ottimizzazione dei sistemi complessi" - 1999/2000

E` stato responsabile italiano nel Progetto di Cooperazione Internazionale Italia-Quebec su "Tecnologie dell'Informazione e della Comunicazione", 1994/2000

E` coordinatore nazionale del progetto CNR - Agenzia 2000 "Modelli ed algoritmi per l'ottimizzazione della produzione e trasmissione dell'energia elettrica in un regime di libero mercato"

Nell'ambito del Progetto Strategico MIUR (anno 99) "Società dell'Informazione: Strumenti, ambienti e applicazioni innovative per la società dell'informazione", è coordinatore di Azione nel progetto "SORSA, Simulazione e Ottimizzazione su Reti: Software e Applicazioni", 2001/02

2) Attivita` scientifica per riviste, convegni, progetti di ricerca
E` componente del comitato scientifico delle riviste "American Journal of Mathematical and Management Sciences" e "Ricerca Operativa"
Svolge e ha svolto attività di referee per le seguenti riviste scientifiche a diffusione internazionale:American Journal of Mathematical and Management Sciences, Annals of Operations Research, Bollettino dell'U.M.I., Calcolo, Computational Optimization and Applications, European Journal of Operational Research, INFOR, Informs Journal of Computing, Mathematical Programming, Networks, Operations Research, Operations Research Letters, Optimization Methods and Software, RAIRO-Operations Research, Rivista di Informatica, Ricerca Operativa, Theoretical Computer Sciences, Transportation Research, Transportation Science
Ha svolto attività di referee per i volumi "Transportation Analysis" Springer-Verlag, e "Annotated bibliographies in Combinatorial Optimization" McGraw-Hill, e per diversi Proceeding di convegni.
Ha svolto attività di valutazione di progetti di ricerca per: National Research Council of Canada, National Science Foundation of U.S.A., C.N.R., Presidenza del Consiglio dei Ministri

Ha svolto e svolge attività organizzativa di convegni e simposi scientifici: IFIP "Computational Issues in Combinatorial Optimization", Capri, 3/86; "the Management and Planning of Urban Transport Systems from Theory to Practice", Montréal, 8/86; AIRO'95, Ancona, 9/95; AIRO'96, Perugia, 9/96 (Chairman); AIRO'97, St. Vincent (AO), 9/97; INFORMS Spring '98, Montréal, 4/98; AIRO'98, Treviso, 9/98; "Tristan IV", Isole Azzorre, 6/01; AIRO'01, Villasimius (CA), 9/01; EURO Working Group Transportation Conference, Bari, 6/02.

E` co-editore di un volume della Franco Angeli e di due numeri speciali delle riviste "Annals of Operations Research" e "Ricerca Operativa".

3) Attivita` di valutazione di dottorandi, dottorati e promozioni a posti di docente
E` stato membro di diverse commissioni di ammissione a dottorati in Italia;
E` stato membro di commissioni per il titolo di Ph.D. in Canada e in Belgio, oltre a diverse volte in Italia.
E` stato membro di diverse commissioni di concorso a Ricercatore, Professore Associato e Professore Ordinario, per il settore MAT/09 (ex A04B)

4) Attività presso altre sedi in Italia e all'estero
E` stato invitato a tenere conferenze in diverse Università italiane (oltre 20, tra Bologna, Cagliari, Cosenza, Genova, Milano, Padova, Pisa, Roma, Salerno e Torino)
E` stato invitato a tenere conferenze in diverse Università estere (Montréal, Trois Rivières e St. Jean du Richelieu in Canada; Illinois, Texas, Florida e Massachusetts in U.S.A.; Sydney e Melbourne in Australia; Singapore; Lipsia, Bruxelles e Valenciennes in Europa, Kanpur in India)
Ha effettuato oltre 15 visite a centri di ricerca e dipartimenti universitari all'estero. In particolare, ha effettuato visite, in qualita` di Visiting Scientist presso
- Centre de Recherche sur les Transports, Université de Montréal (Canada) 1978/79, 1981, 1998;
- ORC, Massachusetts Institute of Technology, Cambridge (USA), 1991, 2000;
- Indian Institute of Technology, Kanpur (India), 1995
- Faculty of Business Administration, National University of Singapore, 1999;
- Mathematical & Information Sciences, CSIRO, Melbourne (Australia) 1999;
- SMG, Université Libre de Bruxelles (Belgio), 1999;
- College of Engineering, University of Florida (USA) 2000;

5) Attivita` di formazione a livello di dottorato e post-dottorato
- Dottorato in Informatica e Sistemistica, Università di Roma "La Sapienza" 1985/86
- membro del Collegio dei Docenti del Dottorato in "Matematica per le Decisioni Economiche" delle Università di Firenze, Pisa e Siena cui si sono aggiunte nel 1999 le Università di Bologna, Sassari e Urbino, dal 1992
- Ph.D. in Management Science, Indian Institute of Technology, Kanpur (India) 1995
- Australian Institute for Operations Research, Melbourne (Australia) 1999
- DEA en "Statistique et Recherche Opérationnelle", Université Libre de Bruxelles (Belgio) 1999

1)Participation in research projetcs
He took part in the following national research projects, acting as coordinator at different levels:
CNR Special Project "Energetics" - 1976/78
CNR Special Project "Computer Science" - 1980/83
CNR Special Project "Transportation" - 1982/87
CNR Strategic Project "Information Technology" - 1985/87
MURST 40% Project "Optimization methods for decision sciences" - 1987/89
MURST 40% Project "Flow management in flexible production systems" - 1990/93
CNR Special Project "Transportation-2" - 1992/98
CNR Coordinated Project "Integrated logistic of network industrial systems" - 1995/97
MURST 40% Project "AAA - Self-coordination of autonomous agents -1997/98
Co-financed MURST Project "COSO - COmplex Systems Optimization" - 1999/2000

He acted as the Italian person in charge for the International Cooperation Project Italy-Quebec "Information and Communication Technology", 1994/2000

He is the principal investigator of CNR - Agenzia 2000 project "Optimization of electric power production and transmission systems in competitive markets: models and algorithms".

In the context of Stategic Project MIUR (1999) "Information Society: Tools, environments and innovative applications for the Information Society" he is one of the three executive coordinators of project "SORSA, Networks simulation and optimization: software and applications" 2001/02

2)Scientific activities concerning journals, conferences and research projects
He is member of the scientific committee of the journals "American Journal of Mathematical and Management Sciences" and "Ricerca Operativa".

He acted and still acts as referee for the following international
scientific journals: American Journal of Mathematical and Management Sciences, Annals of Operations Research, Bollettino dell'U.M.I., Calcolo, Computational Optimization and Applications, European Journal of Operational Research, INFOR, Informs Journal of Computing, Mathematical Programming, Networks, Operations Research, Operations Research Letters, Optimization Methods and Software, RAIRO-Operations Research, Rivista di Informatica, Ricerca Operativa, Theoretical Computer Sciences, Transportation Research, Transportation Science.

He acted as referee for the volumes "Transportation Analysis" Springer-Verlag, and "Annotated bibliographies in Combinatorial Optimization" McGraw-Hill, not to mention the referee activity for several conference proceedings.

He carried out the evaluation of research project for National Research Council of Canada, National Science Foundation of U.S.A., C.N.R., Italian Prime Ministery.

He carried out and still does organizing activities for conferences and
scientific symposia: IFIP "Computational Issues in Combinatorial Optimization", Capri, 3/86; "the Management and Planning of Urban Transport Systems from Theory to Practice", Montréal, 8/86; AIRO'95, Ancona, 9/95; AIRO'96, Perugia, 9/96 (Chairman); AIRO'97, St. Vincent (AO), 9/97; INFORMS Spring '98, Montréal, 4/98; AIRO'98, Treviso, 9/98; "Tristan IV", Isole Azzorre, 6/01; AIRO'01, Villasimius (CA), 9/01; EURO Working Group Transportation Conference, Bari, 6/02.

He is co-editor of a volume by Franco Angeli and two special issues of the journals "Annals of Operations Research" and "Ricerca Operativa".

3) Evaluation activity of PhD students, doctorates researchers and
other teaching positions
He was member of several boards of examiners for the admission to Italian PhD programs.

He was member of committees for the defence of two PhD thesis in Canada and one Belgium as well as many in Italy.

He was member of several committees for teaching assistant, associate
professor and professor positions (subject code MAT/09 - ex A04B)

4)Other activities in Italian universities and abroad
He was invited speaker in several Italian universities (over 20, among
which, but not limited to, Bologna, Cagliari, Cosenza, Genova, Milano, Padova, Pisa, Roma, Salerno and Torino) .

He was invited speaker in several foreign universities (Montréal, Trois Rivières and St. Jean du Richelieu in Canada; Illinois, Texas, Florida and Massachusetts in U.S.A.; Sydney and Melbourne in Australia; Singapore; Lipsia, Bruxelles and Valenciennes in Europa, Kanpur in India).

He was visiting professor at more than 15 foreign research centres
and department. In particular he visited as Visiting Scientist
- Centre de Recherche sur les Transports, Université de Montréal (Canada) 1978/79, 1981, 1998;
- ORC, Massachusetts Institute of Technology, Cambridge (USA), 1991, 2000;
- Indian Institute of Technology, Kanpur (India), 1995
- Faculty of Business Administration, National University of Singapore, 1999;
- Mathematical & Information Sciences, CSIRO, Melbourne (Australia) 1999;
- SMG, Université Libre de Bruxelles (Belgium), 1999;
- College of Engineering, University of Florida (USA) 2000.

5) Teaching activities for PhD and post-doc programs
- PhD in "Computer Science and Systems Theory" at University of Rome
"La Sapienza" 1985/86
- Since 1992 he has been member of the teaching body of PhD program
in "Mathematics applied to economic decisions" which involves the Universities of Pisa, Florence and Siena, besides the Universities of Bologna, Sassari and Urbino which joined the program in 1999
- Ph.D. in Management Science, Indian Institute of Technology, Kanpur (India) 1995.
- Australian Institute for Operations Research, Melbourne (Australia) 1999.
- DEA en "Statistique et Recherche Opérationnelle", Université Libre de Bruxelles (Belgio) 1999.

1.10 Elenco delle Unità di Ricerca (UR)

nº	Responsabile scientifico	Qualifica	Settore sc. disc. di riferimento	Istituzione	Dip/Ist/Div/Sez	Mesi/uomo
1.	PALLOTTINO STEFANO	Professore Ordinario	MAT/09	Universita' di PISA	Dip. INFORMATICA	113
2.	DELL'AMICO MAURO	Professore Ordinario	MAT/09	Universita' degli Studi di MODENA e REGGIO EMILIA	Dip. SCIENZE E METODI DELL'INGEGNERIA	119
3.	GRANDINETTI LUCIO	Professore Ordinario	MAT/09	Universita' degli Studi della CALABRIA	Dip. ELETTRONICA, INFORMATICA E SISTEMISTICA	82
4.	SASSANO ANTONIO	Professore Ordinario	MAT/09	Universita' degli Studi di ROMA "La Sapienza"	Dip. INFORMATICA E SISTEMISTICA	95
5.	TRUBIAN MARCO	Ricercatore Universitario	MAT/09	Politecnico di MILANO	Dip. ELETTRONICA E INFORMAZIONE	96
6.	CARAMIA MASSIMILIANO	Ricercatore	MAT/09	Consiglio nazionale delle ricerche (CNR)	IAC - Istituto per le Applicazioni del Calcolo "Mauro Picone"	85
7.	SALERNO SAVERIO	Direttore	MAT/05	Centro di Ricerca in Matematica Pura e Applicata	c/o DIIMA	126
						716

1.11 Breve descrizione delle Unità di Ricerca

Al progetto partecipano 7 Unità di Ricerca. Esse hanno sede presso: Dipartimento di Informatica, Università di Pisa; Dipartimento di Scienze e Metodi dell'Ingegneria, Università di Modena e Reggio Emilia; Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabria; Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"; Dipartimento di Elettronica e Informazione, Politecnico di Milano; Istituto per le Applicazioni del Calcolo, CNR; Centro di Ricerca in Matematica Pura e Applicata, Università di Salerno.

L'UR dell'Università di Pisa, di cui è responsabile Stefano Pallottino, che è anche coordinatore scientifico del progetto, si compone di 2 professori ordinari, 3 professori associati, 2 ricercatori universitari, 1 assegnista di ricerca, 1 dottorando. È prevista l'assegnazione di un contratto triennale di ricerca. A tale UR partecipa il responsabile del nodo centrale della rete di ricerca CRIFOR, situato presso l'Università di Cagliari.
La qualità scientifica dell'UR è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, con particolare riferimento ad algoritmi per problemi di flusso su rete, anche di tipo multicommodity, e dalla messa a punto di software di ottimizzazione su reti.
Le competenze dell'UR hanno portato alla presentazione di due attività incentrate, rispettivamente, sul progetto di reti di comunicazione con domanda multicommodity, e sulla localizzazione e dimensionamento di nodi in una rete.
Importante è l'impegno dell'UR nel potenziamento della rete di ricerca CRIFOR e del suo nodo centrale (vedi 1.12.1, 3.3 ed Attività 1 del WP 1): tale attività è sviluppata in collaborazione con le altre UR per il raggiungimento dell'obiettivo strategico dell'intero progetto di ricerca.

L'UR dell'Università di Modena e Reggio Emilia, di cui è responsabile Mauro Dell'Amico, è composta anche da ricercatori del Dipartimento di Informatica e Automatica del Politecnico di Torino e del Dipartimento di Informatica dell'Universita' di Milano (sede di Crema).
L'UR si compone di 3 professori ordinari, 1 professore associato, 2 ricercatori universitari, 3 assegnisti di ricerca, 4 dottorandi. È prevista l'assegnazione di un contratto triennale di ricerca e di un contratto di collaborazione.
La qualità scientifica dell'UR è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, quali problemi di ottimizzazione per il progetto di reti ottiche, e dalla significativa presenza in progetti di ricerca nazionale.
Le competenze dell'UR hanno condotto alla proposizione di due attività per il progetto di reti ottiche protette, secondo due diverse tecniche (copertura con cicli e coppie di cammini), ed una terza per il progetto e la realizzazione di un "configuratore" di reti per le operazioni di descrizione e aggiornamento di reti, al fine di facilitare l'analisi di scenari di evoluzione.

All'UR dell'Università della Calabria, responsabile Lucio Grandinetti, partecipano anche ricercatori delle Università di Lecce, Napoli "Federico II" e Salerno.
L'UR si compone di 2 professori ordinari, 2 professori associati, 3 ricercatori universitari. È prevista l'assegnazione di un contratto triennale di ricerca e di una borsa di dottorato.
La qualità scientifica dell'UR è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, in particolare lo sviluppo di modelli e metodi per la soluzione di problemi di progetto di reti di telecomunicazione.
Le attività proposte dall'UR sono incentrate sul dimensionamento di reti di comunicazione; in una si affronta il problema di garantire il funzionamento della rete anche a seguito di guasti in porzioni di essa mentre nell'altra si studia l'effetto di una domanda fortemente aleatoria sulla funzionalità delle reti di comunicazione.

L'UR dell'Università di Roma "La Sapienza", responsabile Antonio Sassano, consulente dell'Autorità Nazionale per la Garanzia nelle Comunicazioni e membro del Comitato Nazionale per l'Introduzione della Tecnologia di Trasmissione Digitale, si compone di 2 professori ordinari, 1 professore associato, 4 dottorandi. È prevista l'assegnazione di un contratto triennale di ricerca.
La qualità scientifica dell'UR è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, dalla significativa presenza in progetti di ricerca nazionale e dalle attività svolte per l'Autorità Nazionale per la Garanzia nelle Comunicazioni.
Le attività proposte dall'UR coprono sia aspetti di ottimizzazione, quali il problema del progetto delle capacità delle reti di comunicazione (Network Loading) e il progetto di reti per la trasmissione radio e televisiva digitale, che aspetti di analisi economica, per valutare i costi delle reti e le conseguenti implicazioni, e di analisi delle strategie aziendali, a seguito del nuovo assetto del mercato nazionale delle comunicazioni.

L'UR del Politecnico di Milano, responsabile Marco Trubian, si compone di 2 professori ordinari, 1 professore associato, 2 ricercatori universitari, 2 assegnisti di ricerca, 1 dottorando. È prevista l'assegnazione di un contratto triennale di ricerca.
La qualità scientifica dell'UR è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, in particolare lo studio di problemi di ottimizzazione per la progettazione e la gestione di reti di comunicazione; significativa è anche la partecipazione a progetti di ricerca nazionale.
Il gran numero di attività proposte dall'UR riguardano il progetto di reti ottiche protette (Survivable Network Design Problem) mediante due approcci alternativi (p-cicli e cammini disgiunti), il progetto di reti LAN, l'instradamento di messaggi su reti basate sull'Internet Protocol, e le tecniche di riconfigurazione di traffico sulle reti a seguito di cambiamenti dell'offerta.

L'UR del CNR, responsabile Massimiliano Caramia, riunisce competenze presenti anche presso un altro istituto del CNR e l'Università di Roma "La Sapienza". L'UR si compone di 2 professori ordinari, 1 professore associato, 2 ricercatori universitari, 1 dirigente tecnologo, 1 tecnologo e 2 ricercatori CNR. È previsto un contratto di collaborazione.
Il particolare intreccio di competenze dell'UR, testimoniate dalla vasta gamma di pubblicazioni scientifiche su problemi di ottimizzazione per il progetto e la gestione di reti di comunicazione, ha permesso di prospettare tre attività sui problemi dell'assegnazione di frequenze alle antenne di sistemi di telefonia mobile, del dimensionamento di nodi per reti di telefonia fissa condivise da più società di servizi, e sul problema della protezione della trasmissione attraverso la sua distribuzione su più cammini e il bilanciamento del loro carico.

L'UR del Centro di Ricerca in Matematica Pura e Applicata, responsabile Saverio Salerno, raggruppa studiosi appartenenti a diversi atenei (Università del Sannio, di Salerno, di Napoli "Federico II" e di Roma "La Sapienza") per formare un'UR particolarmente ricca di competenze diverse e sinergiche. Essa si compone di 2 professori ordinari, 2 professori associati, 5 ricercatori universitari, 1 dirigente di ricerca, 3 ricercatori senior, 2 assegnisti di ricerca, 1 dottorando. È prevista l'assegnazione di 2 contratti triennali di ricerca e la collaborazione di due ricercatori esteri di chiara fama.
La qualità scientifica è testimoniata dalle numerose pubblicazioni scientifiche su tematiche inerenti al progetto, in particolare lo studio di problemi di ottimizzazione per il progetto di reti e la simulazione del loro utilizzo; significativa è anche la presenza in progetti di ricerca nazionale, anche con ruoli di responsabilità di coordinamento.
Alle attività di ottimizzazione nel progetto delle capacità delle reti (Network Loading) e nel dimensionamento dei nodi di una rete LAN, si affianca lo studio di modelli matematici per la simulazione del traffico di reti in presenza di domanda aleatoria.

7 Research Units will participate to this project. They are located at: Dipartimento di Informatica, University of Pisa; Dipartimento di Scienze e Metodi dell'Ingegneria, University of Modena e Reggio Emilia; Dipartimento di Elettronica, Informatica e Sistemistica, University of Calabria; Dipartimento di Informatica e Sistemistica, University of Roma "La Sapienza"; Dipartimento di Elettronica e Informazione, Polytechnic of Milano; Istituto per le Applicazioni del Calcolo, CNR; Centro di Ricerca in Matematica Pura e Applicata, University of Salerno.

The RU of University of Pisa has Stefano Pallottino, who is also the scientific coordinator of the project, as its responsible. The RU is composed of 2 full professors, 3 associate professors, 2 university researchers, 1 Post-Doc fellow, 1 Ph.D. student. A three-years research contract will be made available. The responsible of the central node of the research network CRIFOR, located at the University of Cagliari, is a member of this RU.
The scientific quality of the RU is testified by the numerous scientific publications on subjects related to the project themes, such as algorithms and software for network flow problems, also multicommodity flows.
Two activities have been proposed, which are related to the knowledge and skill of the members of the RU. The first one concerns the design of communication networks with multicommodity demands, the second one concerns location and sizing aspects of network nodes. Also, an important role of this RU will be to enhance the research network CRIFOR and its central node (see 1.12.1, 3.3 and WP 1, Act. 1): this activity will be performed by cooperating with the other RUs, in order to achieve the strategic objective of the entire research project.

The RU of University of Modena e Reggio Emilia, having Mauro Dell'Amico as its responsible, is composed also of researchers of the Dipartimento di Informatica e Automatica of the Polytechnic of Torino and of the University of Milan (Crema site).
The RU is formed by 3 full professors, 1 associate professor, 2 university researchers, 3 Post-Doc fellows, 4 Ph.D. students. A three-years research contract will be made available, together with a cooperation contract.
The scientific quality of the RU is testified by the numerous scientific publications on subjects related to the project themes, such as optimization problems for the design of optical networks, and by the relevant participation to Italian research projects.
Three activities have been proposed, which are related to the expertise of the members of the RU. Two activities concern the design of protected networks, according to two different techniques (covering by cycles or couples of paths), whereas the third activity concerns the design and the development of a decision support tool called "configuratore", devoted to operations like description and updating of networks, with the aim of making it easy the analysis of evolutionary scenarios.

The RU of University of Calabria, having Lucio Grandinetti as its responsible, is also formed by researchers of the Universities of Lecce, Napoli "Federico II" and Salerno.
The RU is composed of 2 full professors, 2 associate professors, 3 university researchers. A three-years research contract will be made available, together with a Ph.D. position.
The scientific quality of the RU is testified by the numerous scientific publications on subjects related to the project themes, such as the development of models and methods for the solution of network design problems in telecommunication.
The proposed activities concern the sizing of communication networks. One activity is devoted to the problem of guaranteeing the network performance also in the case of faults in portions of it. A second activity aims to study the influence of a highly random demand on the communication network performance.

The RU of University of Roma "La Sapienza" is coordinated by Antonio Sassano, who is consultant of "Autorità Nazionale per la Garanzia nelle Comunicazioni", and member of "Comitato Nazionale per l’Introduzione della Tecnologia di Trasmissione Digitale". The RU is formed by 2 full professors, 1 associate professor, 4 Ph.D. students. A three-years research contract will be made available.
The scientific quality of the RU is testified by the numerous scientific publications on subjects related to the project themes, by the significant participation to Italian research projects, and by activities performed on indication of the mentioned "Autorità Nazionale".
The activities proposed by the RU concern both optimization aspects, such as the Network Loading problem in communication networks ( and some design problems for digital radio and video transmission, and also economical analysis aspects, in order to evaluate the network costs and their implications, as well as analysis of the firm strategies, as required by the new establishment of the national communication market.

The RU of Polytechnic of Milano, having Marco Trubian as its responsible, is composed of 2 full professors, 1 associate professor, 2 university researchers, 2 Post-Doc fellows, 1 Ph.D. student. A three-years research contract will be made available.
The scientific quality of the RU is testified by the numerous scientific publications on subjects related to the project themes, in particular the study of optimization problems for the design and management of communication networks; relevant is also the participation to Italian research projects.
The RU has proposed several activities, which concern the Survivable Network Design Problem by means of two alternative approaches (p-cycles and disjoint paths), the design of LAN networks, the routing of messages in networks based on the Internet Protocol, and techniques for traffic re-routing on networks due to modifications of the supplies.

The RU of CNR, having in charge Massimiliano Caramia, includes researchers from another institute of CNR and University of Roma "La Sapienza". The RU is formed by 2 full professors, 1 associate professor, 2 university researchers, 1 technician manager, 1 technician e 2 CNR researchers. A cooperation contract will be made available.
The special mix of expertises of this RU, testified by the large set of scientific publications on optimization problems devoted to the design and management of communication networks, has led to the proposal of three activities, concerning the assignment of frequencies to antennas of mobile communication systems, the sizing of nodes in fixed telephone networks, and the protection of the transmission via its distribution on several paths and via the balancing of their charge.

The RU of Centro di Ricerca in Matematica Pura e Applicata, coordinated by Saverio Salerno, is composed of a group of researchers belonging to different universities (University of Sannio, Salerno, Napoli "Federico II" and Roma "La Sapienza"). Therefore this RU possesses several synergic expertises. It is formed by 2 full professors, 2 associate professors, 5 university researchers, 1 research manager, 3 senior researchers, 2 Post-Doc fellows, 1 Ph.D. student. There will be 2 three-years research contracts and the cooperation with two foreign researchers whose scientific value is highly recognized.
The scientific quality is testified by the numerous scientific publications on subjects related to the project themes, in particular the study of optimization problems for network design, and the analysis of simulation tools for their use; furthermore, the participation of the RU members to national research projects is relevant, also with roles of responsibility and coordination.
In addition to activities concerning optimization aspects in designing capacities of networks (Network Loading) and in sizing problems of nodes of LAN networks, a third activity is proposed, which concerns the study of mathematical models for the simulation of network traffic under a highly random demand.

1.12 Descrizione delle infrastrutture da realizzare

1.12.1 Collegamento funzionale con la Proposta Progettuale

Uno dei risultati attesi del presente progetto è di mettere a disposizione della comunità scientifica nazionale ed estera e delle aziende di produzione e di gestione di servizi il patrimonio di software prodotto nell'arco del triennio della ricerca, assieme al software di base per l'ottimizzazione su reti già prodotto e in via di sviluppo in ambito CRIFOR. Si intende anche aprire tale servizio a tutti i gruppi di ricerca che contribuiranno allo sviluppo di software per la progettazione e gestione di reti nell'ambito del finanziamento FIRB e che condivideranno l'iniziativa della diffusione "open" del software attraverso la rete di ricerca CRIFOR.

Le librerie di software di ottimizzazione e simulazione per i problemi di progettazione e gestione di reti descritti nel programma, quelle del software di base di ottimizzazione su reti, e quelle eventuali fornite da altri gruppi di ricerca impegnati nel FIRB, saranno prodotte secondo schemi di standardizzazione e documentazione del software già predefiniti a livello di rete di ricerca CRIFOR e corredati di problemi test in formati standard opportunamente definiti.

Per rendere disponibile e facilmente utilizzabile il software, si intende attrezzare adeguatamente il nodo centrale della rete di ricerca CRIFOR, situato presso l'Università di Cagliari. Tale scelta di potenziamento rientra nel più vasto obiettivo dei progetti FIRB di promuovere la creazione e il potenziamento di reti di ricerca di alto livello scientifico.

Anche con la collaborazione della Regione Sardegna, dell'Università di Cagliari e di un "pool" di aziende sarde, che attualmente cooperano con il nodo CRIFOR di Cagliari, si intende costituire una struttura tecnico-scientifica attrezzata con propri strumenti di calcolo. Si vuole cioè potenziare il nodo-centrale della rete di ricerca CRIFOR affinché sia possa svolgere i compiti sopra descritti e proseguirli oltre il termine del progetto, anche per prevenire l'obsolescenza del software mantenendone il continuo aggiornamento e per rispondere alle continue e diverse richieste provenienti dal mondo reale.

A livello infrastrutturale ci si propone di costituire una rete locale ad alta velocità (Gigabit ethernet) costituita da: un server multiprocessore per il calcolo scientifico ad alte prestazioni per il test e la sperimentazione del software, anche da parte di utenti remoti; workstations di marca ed architettura diversa per la validazione multipiattaforma del software; personal computers per la gestione del sistema di pagine web, la produzione e documentazione del software; un web server dimensionato per elevati livelli di traffico web. Tale rete sarà collegata con la rete dell'ateneo cagliaritano e con la rete scientifica nazionale mediante un accesso ad altissima velocità, allo scopo di permettere un agevole accesso dei nodi della rete CRIFOR al nodo cagliaritano per l'alimentazione, aggiornamento e utilizzo delle librerie software, oltre all'accesso ai più importanti centri italiani, europei e nord-americani di calcolo scientifico, compresi quelli attrezzati per il calcolo parallelo.

La struttura prevederà anche la possibilità di effettuare test comparativi delle librerie prodotte, tra loro e con i migliori pacchetti commerciali disponibili, da parte di utenti remoti su problemi da essi prodotti, in modo da facilitare la valutazione e la divulgazione del software contenuto nel sito.

Una parte del finanziamento serve per attrezzare i locali a contenere la rete e a potenziare il sistema elettrico secondo gli standard di sicurezza previsti.

Per una migliore comprensione delle tabelle seguenti, nel primo anno si intende realizzare i lavori di adeguamento della sede e l'acquisto e messa in funzione della rete, del web server e del software; il server scientifico e le workstation verranno acquistati nell'arco di due anni secondo una cadenza legata all'acquisizione delle librerie software.

One of the expected results of this project is to supply national and international scientific communities as well as companies providing public services, with the software packages produced during the three-year research activity and the basic software for network optimization already developed by the CRIFOR.
We want to extend this service also to the research groups which will contribute to the software development for network planning and management problems within the FIRB financing program, and which will participate to the CRIFOR initiative of the "open'' software distribution.

The optimization and simulation software libraries for network planning and management problems, which have been described in the program, and the libraries provided by other research groups working in the FIRB context, will be produced according to the software standardization and documentation schemes already defined within the CRIFOR research network, and will be supplied with benchmark instances formatted accordingly to opportunely defined standards.

The central node of the CRIFOR research network, located at the University of Cagliari, will be supplied with the adequate tools to make the software available and user friendly. The choice of enhancing the equipment is also one of the primary goals set up in the FIRB projects, i.e., to promote the creation and development of research networks of high scientific quality.

In cooperation with the Regione Sardegna, the University of Cagliari and a pool of sardinian companies that are already working with the CRIFOR node in Cagliari, we also aim at setting up a technical scientific structure equipped with its own computational tools. The central node of the CRIFOR network will thus be strengthened and will be able to perform the tasks mentioned above even beyond the lifetime of the project. This will also be needed in order to keep all the software up-to-date and meet real world requirements, continuously evolving and greatly diversified.

At the infrastructure level we propose a high speed local network (Gigabit ethernet) with the following components: a high performance multiprocessor server for scientific computations so that both local and remote clients can test the software; workstations of several brands and with different architectures to enable multi-platform software validation; personal computers for the management of web sites and software production and documentation; a web server capable of handling high levels of traffic. A high speed link will connect this network to the one at the University of Cagliari and to the national scientific network, with the objective of providing easy access from the CRIFOR nodes both to the Cagliari node - to update and use the software libraries - and to the most important scientific computational centers in Italy, Europe and North America, including those equipped for parallel computation.

It will also be possible to perform comparative tests, among packages included in the newly developed libraries and with the available commercial packages. This possibility will be given also to external users, so as to facilitate the software validation and distribution.

Part of the financing will be used to equip the network premises and to conform the electric system to the required security standards.

To better understand the following tables, it is worth noting that in the first year we plan to carry out the works related to the equipment of the working place and to acquire and put in operation the network, the web server and the software; the scientific server and the work stations will be bought in a two-year period depending on the acquisition of the software libraries.

1.12.2 Descrizione delle infrastrutture

nº	Descrizione	Ubicazione	Costo A (MLit)	Costo B (MLit)	Costo C (MLit)	Costo D (MLit)	Tempo di realizz. (anni)	Resp. Scientifici delle UR partecipanti
1.	Server scientifico ad alte prestazioni con >= 8 processori.	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	200 (103.29 KEuro)	1	PALLOTTINO STEFANO
2.	Workstations di diversi produttori (IBM, HP, CompaQ, Sun ...), con diverse architetture (Intel, Alpha, R6000, UltraSparc) e diversi sistemi operativi (AIX, Linux, Hp-UX, Solaris ...) per lo sviluppo e testing di codici multipiattaforma	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	120 (61.97 KEuro)	0	PALLOTTINO STEFANO
3.	Rete di connessione Gigabit Ethernet, connessione ad alta velocità con backbone Internet	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	30 (15.49 KEuro)	0	PALLOTTINO STEFANO
4.	Licenze software multiutente di software commerciale di ottimizzazione e simulazione (Cplex, Xpress, ...)	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	20 (10.33 KEuro)	0	PALLOTTINO STEFANO
5.	web server mid-range	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	20 (10.33 KEuro)	0	PALLOTTINO STEFANO
6.	cluster di PC per le attività di amministrazione, sviluppo e documentazione	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	15 (7.75 KEuro)	0	PALLOTTINO STEFANO
7.	Cablaggio ed attrezzatura della sede	Cagliari	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	30 (15.49 KEuro)	1	PALLOTTINO STEFANO

Legenda:

Costo A: Costo della progettazione (MLit)
Costo B: Costo delle aree (MLit)
Costo C: Costo delle opere civili (MLit)
Costo D: Costo dell'allestimento (MLit)

1.12.3 Rapporto con iniziative locali/regionali/nazionali/comunitarie/internazionali

Come già specificato in 1.12.1, l'infrastruttura per il potenziamento del nodo centrale della rete CRIFOR si situa nel contesto di una rete di ricerca già esistente, che si estende sull'intero territorio nazionale.
Alle attività del CRIFOR partecipano infatti ricercatori di oltre 25 università italiane, di tre Istituti del CNR, e di alcuni centri di ricerca a capitale pubblico o misto.

Si intende estendere l'iniziativa, attualmente a livello nazionale, anche a livello dell'Unione Europea, collegandosi con analoghi centri presenti in altri paesi.

A livello regionale, inoltre, si sta operando per la definizione di una apposita convenzione tra l'Università di Cagliari e la Regione Sardegna, per costituire un consorzio di ricerca a cui partecipi il CRIFOR e numerose aziende private e a capitale pubblico presenti nella regione sarda.

Il potenziamento dell'infrastruttura di calcolo e di connessione è un prerequisito fondamentale per il potenziamento delle attività di raccolta e distribuzione del software, e quindi per il trasferimento delle conoscenze verso le attività di produzione e servizio.

As already specified in 1.12.1, the infrastructure aimed at the enhancement of the central node of CRIFOR network concerns an existing research network, involving the whole national land.
Several researchers participate in fact to the CRIFOR activities, coming from more than 25 Italian universities, 3 CNR institutes and some research centers with public or mixed funds.

We plan to spread the initiative, currently at a national level, also at a European level, linking the center to similar centers of other countries.

Moreover, at the regional level, a special convention between University of Cagliari and Sardinia Region will be stipulated, in order to constitute a research consortium involving both CRIFOR and several public and private enterprises operating in Sardinia.

The enhancement of the computing and network equipment is a fundamental requirement in order to enhance the activities devoted to the collection and the diffusion of the software and, therefore, to spread out knowledge toward production and service activities.

1.12.4 Rapporto con Istituzioni pubbliche e private, Centri di ricerca, Parchi scientifici e tecnologici, Poli industriali, etc.

Come già specificato in 1.12.1, il nodo centrale della rete CRIFOR è attualmente un Centro di Ricerca dell'Università di Cagliari. Il gruppo sardo di ricercatori del Centro ha avviato da tempo una serie di progetti in collaborazione con diverse realtà imprenditoriali e centri di ricerca, oltre a mantenere un rapporto strutturale di ricerca con diverse università ed Istituti del CNR, in particolare con alcuni dipartimenti e strutture di ricerca dell'Università di Cagliari, e con alcuni centri di ricerca pubblici e privati.

Il nodo centrale della rete CRIFOR ha intrapreso le seguenti attività:
- collabora con la Regione Autonoma della Sardegna nella fase di studio di fattibilità del RUPAR, Rete Unitaria della Pubblica Amministrazione a livello Regionale;
- ha avviato una convenzione quadro con l'Ente Autonomo del Flumendosa (EAF), collaborando al progetto europeo WARSYP, WAter Resources System Planning, nell'ambito del IV Framework, ed implementandone i risultati, nell'ambito di INTERREG III, con altri paesi del Mediterraneo;
- ha avviato una convenzione quadro con la SOcietà Gestione AERoporti di Cagliari-Elmas (SOGAER) nell'ambito dell'attività di adeguamento dell'Aeroporto mediante cofinanziamento europeo;
- ha avviato una convenzione quadro con la società Tiscali per lo studio del traffico su reti Internet;
- ha avviato una collaborazione in fase di perfezionamento con il Consorzio 21, istituito dalla Regione Autonoma della Sardegna, che gestisce la realizzazione del Parco Scientifico e Tecnologico (PST) della Sardegna. Il CRIFOR aderirà al PST e affiancherà il Consorzio nella promozione dell'innovazione tecnologica e nello sviluppo della Società dell'Informazione a livello regionale;
- ha avviato un rapporto, in fase di perfezionamento, con POLi Avanzati RIcerche Sardegna (POLARIS), nato con finanziamento UE, per la localizzazione di imprese innovative e centri di ricerca e sviluppo in ambito SME (Small Medium Enterprise).

Specifically, the central node of CRIFOR network is performing the following activities:
- it collaborates with "Regione Autonoma della Sardegna" (Sardinia Region) in planning the realization of the Regional Join Network of Public Administration (RUPAR, Rete Unitaria della Pubblica Amministrazione a livello Regionale);
- it has stipulated a join convention with Ente Autonomo del Flumendosa (EAF), by participating to the European project WARSYP, WAter Resources System Planning, within the EU IV Framework, and by applying the obtained results with other Mediterranean countries, within the project INTERREG III;
- it has stipulated a join convention with SOcietà Gestione AERoporti (SOGAER) of the airport of Cagliari-Elmas, in order to improve the airport structure by means of EU funds;
- it has stipulated a join convention with Tiscali for some studies on the Internet traffic;
- it has a collaboration, to be defined in its details, with the Sardinian institution "Consorzio 21", which manages the realization of the Sardinian Scientific and Technological Park (PST, Parco Scientifico e Tecnologico). The center CRIFOR will participate to PST, and it will collaborate with the consortium in order to promote the technological innovation and to develop the information society in Sardinia;
- it has a collaboration, to be defined in its details, with POLi Avanzati Ricerche Sardegna (POLARIS), a structure which has been created thanks to EU funds, for the location of innovative enterprises and of research and development centers concerning Small Medium Enterprises (SME).

1.12.5 Costi e tempi di realizzazione

nº	Descrizione	Costo Totale (MLit)	Tempo di Realizzazione (anni)
1.	Server scientifico ad alte prestazioni con >= 8 processori.	200 (103.29 KEuro)	1
2.	Workstations di diversi produttori (IBM, HP, CompaQ, Sun ...), con diverse architetture (Intel, Alpha, R6000, UltraSparc) e diversi sistemi operativi (AIX, Linux, Hp-UX, Solaris ...) per lo sviluppo e testing di codici multipiattaforma	120 (61.97 KEuro)	0
3.	Rete di connessione Gigabit Ethernet, connessione ad alta velocità con backbone Internet	30 (15.49 KEuro)	0
4.	Licenze software multiutente di software commerciale di ottimizzazione e simulazione (Cplex, Xpress, ...)	20 (10.33 KEuro)	0
5.	web server mid-range	20 (10.33 KEuro)	0
6.	cluster di PC per le attività di amministrazione, sviluppo e documentazione	15 (7.75 KEuro)	0
7.	Cablaggio ed attrezzatura della sede	30 (15.49 KEuro)	1
		435 (224.66 KEuro)	2

Parte III "Le Attività di Ricerca"

3.1 Obiettivi scientifici della proposta Progettuale e risultati attesi

La proposta di ricerca si prefigge diversi obiettivi: raggiungimento di risultati scientifici, divulgazione dei risultati ottenuti, coordinamento e potenziamento delle capacità di ricerca.

L'aspetto preponderante è quello scientifico. La proposta di ricerca è infatti presentata dai gruppi nazionali più prestigiosi nello studio di problemi strutturati a rete e nella individuazione di soluzioni algoritmiche e pacchetti software di particolare efficienza. Ciò è testimoniato dalla partecipazione dei ricercatori proponenti a moltissimi progetti di ricerca, anche con responsabilità di coordinamento scientifico, sia a livello nazionale, europeo ed internazionale. Inoltre, la letteratura scientifica prodotta è di altissimo livello, ed il ruolo della scuola italiana di ottimizzazione su reti si estende anche a livello internazionale.
I gruppi di ricerca intendono studiare, in modo coordinato e sinergico, problemi di progetto e gestione di reti di comunicazione che appaiono rilevanti per la loro difficoltà intrinseca, dovuta anche alle grandi dimensioni, e per le particolarità legate all'introduzione delle nuove tecnologie della comunicazione e dell'informazione.
Una motivazione è che i metodi studiati e proposti nella letteratura scientifica corrente appaiono decisamente inadeguati, sia per le dimensioni dei nuovi problemi da risolvere, sia perché il continuo evolversi della tecnologia della comunicazione richiede uno studio approfondito delle caratteristiche peculiari delle reti oggetto di studio, al fine di comprenderne a fondo le proprietà strutturali e proporre approcci algoritmici concepiti espressamente in funzione dello sfruttamento di tali proprietà.

Il PRIMO OBIETTIVO che ci si prefigge è la definizione di modelli e strumenti algoritmici di risoluzione rispondenti alle nuove caratteristiche dei problemi di progetto e gestione delle reti di telecomunicazione , come descritto nella proposta di ricerca articolata in Work Packages e in attività.

Il risultato atteso, legato al primo obiettivo, è disporre, al termine del triennio, di un ampio e aggiornato insieme di modelli e algoritmi di ottimizzazione e simulazione per i problemi di progetto e gestione di reti descritti nei programmi delle singole Unità di Ricerca, nonché del relativo software di ottimizzazione e simulazione. Tale libreria sarà prodotta secondo schemi di standardizzazione e documentazione del software già predefiniti a livello della rete di ricerca CRIFOR, e corredata da problemi test in formato standard opportunamente predefinito.

Il SECONDO OBIETTIVO della ricerca, che si avvale della libreria precedentemente descritta, è rendere disponibile e facilmente utilizzabile il software prodotto nel triennio della ricerca. Il notevole patrimonio di strumenti di soluzione ottenuti nell'ambito di progetti di ricerca rischia spesso di restare confinato all'interno delle unità che lo hanno prodotto, con il duplice danno di una scarsa diffusione del software e la mancanza di un suo adeguato test, ottenibile solo attraverso l'applicazione del software, da parte di terzi, a svariati problemi reali. A tal fine, il nodo centrale della rete di ricerca CRIFOR opererà in collaborazione con tutte le Unità di Ricerca perché il software prodotto sia documentato, validato e diffuso (vedi Attività 1, WP1). L'obiettivo finale, probabilmente raggiungibile durante il quarto anno di attività e quindi oltre il termine del presente progetto di ricerca, sarà quello di mettere a punto un sistema di test e diffusione via Internet del software, aperto alla comunità scientifica nazionale ed estera e alle aziende ed amministrazioni interessate a tale software.

TERZO OBIETTIVO della ricerca, a cui i proponenti attribuiscono una importanza decisiva, è il potenziamento della rete di ricerca. Come già descritto nel punto 1.2b, una struttura a rete, la rete di ricerca CRIFOR (Centro di Ricerca e Formazione per l'Ottimizzazione su Reti), già esiste e accomuna tutti i centri di ricerca partecipanti al progetto. Seppur nata per iniziativa spontanea di alcuni ricercatori del settore, essa si è già affermata come strumento di proposizione di iniziative collettive di ricerca, e come recettore/gestore dei risultati delle ricerche svolte in comune. Si vuole, con la presente proposta progettuale, dare una strutturazione ufficiale alla rete di ricerca, ampliarla negli obiettivi e nella partecipazione, facilitare l'adesione di centri di ricerca e sviluppo di aziende private e di gestione di servizi, permettere cioè la continuazione del lavoro di produzione di ricerca in modo coordinato, e la diffusione dei risultati della ricerca anche oltre il periodo di vita del progetto.

Il risultato atteso è avere, al termine del triennio, una partecipazione ampia e diversificata alle iniziative del CRIFOR, una strutturazione agile ma ufficializzata, un sistema web di raccolta e diffusione dei risultati scientifici (rapporti e pubblicazioni), del software (comprensivo di documentazione d'uso, problemi test, e risultati sperimentali), piattaforme di utilizzo via Internet del software stesso, e strumenti di divulgazione del software anche verso le aziende.

The research proposal aims at accomplishing different objectives, namely: achieving new scientific results, spreading these results among the scientific communities, coordinating and strengthening the ability of carrying out research work.

The primary challenge concerns the scientific achievements. Indeed, this research proposal has been formulated by the most prestigious national research groups, expert in the study of network problems and in the development of very efficient algorithmic solution techniques and software packages. Evidences of the scientific value of the involved researchers are given by their participation in many research projects, even as scientific coordinators at national, European and international level. Furthermore, they have produced very high quality scientific literature, and have contributed to enhance the role of the Italian network optimization school at international level.
The research groups aim at studying, in a well-coordinated and synergistic way, communication network planning and management problems. Those problems have been recently gaining increasing relevance due to their inherent difficulty, often related to their large size, and to some peculiarities strictly connected to the introduction of new telecommunication and information technologies.
The stated research purposes are motivated by the inadequacy of the existent solution approaches to solve large scale new problems, and by the necessity of exploiting the new structural network properties deriving from recent development in communication technologies, so as to device more specific algorithmic approaches.

The FIRST OBJECTIVE we want to achieve is the definition of new models and algorithmic tools, which can meet the new requirements arising in the telecommunication network planning and management problems, as described in the research proposal articulated into Work Packages and activities.

The expected result, related to the first objective, is to provide, by the end of the three years, a wide and up-to-date set of optimization and simulation models and algorithms, with the related software packages, devised for solving network design and management problems, as described in the programs of the individual research units. The software will be produced according to the standardization and documentation schemes, which have been already defined by the research network CRIFOR. Test problems in a common standard format will be also provided.

The SECOND OBJECTIVE of the research, which relies on the scientific achievements just described, is to make the software developed during the three-year research activity available to the scientific community, and facilitate its utilization. Too often, the wealth of software tools developed in the context of a research project remains confined within the individual group that produced it, with a twofold damage: scarce diffusion and lack of adequate testing, which can only be achieved by its use by third parties to solve real-world applications. To avoid these drawbacks, the central node of the research network CRIFOR will cooperate with all the research groups in order to guarantee that the software will be well documented, tested and distributed (see Activity 1, WP1). The final goal, which is likely to be achieved only during the forth year and therefore beyond the end of the present project, is to provide an Internet based system to test and distribute the software, so that it will be available to national and international scientific communities, companies and local governments which might be interested in its use.

The THIRD OBJECTIVE, which has a crucial importance according to the promoters of the project, is the strengthening of the research network. As already pointed out in 1.2b, a research network called CRIFOR ("Centro di Ricerca e Formazione per l'Ottimizzazione su Reti") already exists, and all the research groups involved in the present project are part of it. Even though CRIFOR was born as the realization of the personal efforts of a few researchers in the field, it has already become an active tool to promote collective research work, as well as an efficient collector and manager of the results of joint research projects.
The present research project aims at giving an official structure to this research network, enlarging its objectives and participation, facilitating the access of research and development centers of private companies and service providers. Summarizing, the CRIFOR network should be able to assure continuity in the production of coordinate research and guarantee the spreading of the obtained results even beyond the lifetime of the project.

The expected result within the three-year activity is to have large and divers participation in CRIFOR initiatives, an official and flexible structure, a web system to collect and divulgate scientific results (reports and publications) and software packages (including documentation, benchmark instances and computational results), web-based software platforms, and tools for software distribution.

3.2 Base di partenza scientifica nazionale o internazionale

1. Introduzione
Il sistema della comunicazione ha avuto negli ultimi anni uno sviluppo notevole in termini di tecnologia di trasmissione e memorizzazione, di quantità di informazione trasmissibile nell'unità di tempo, di integrazione fra le diverse reti (fonia, dati, immagini, ecc.). Lo sviluppo è ancora in atto e gli scenari sui prossimi anni mostrano l'estrema importanza della disponibilità di reti molto potenti, affidabili e istallate e gestite in modo altamente efficiente.

È nei fatti un contesto applicativo naturale per l'utilizzo delle metodologie e degli strumenti della Ricerca Operativa; i metodi di Ottimizzazione e di Simulazione sono già stati molto utilizzati nelle fasi di progettazione e pianificazione di reti di comunicazione e della loro gestione secondo parametri di efficienza ed efficacia.
Lo sforzo di ricerca e sviluppo svolto negli anni scorsi ha mostrato, a livello nazionale e internazionale, come le metodologie di ottimizzazione e simulazione su grafi possano essere efficacemente utilizzate per risolvere problemi applicativi nel settore delle telecomunicazioni.

Nella letteratura internazionale sono presenti numerosi e qualificati contributi riguardanti l'utilizzo di modelli e metodi di Ottimizzazione e Simulazione per la soluzione di problemi di progetto e di gestione di reti di telecomunicazione. L'analisi dei contributi esistenti tuttavia evidenzia che:
i) molti dei modelli proposti nella letteratura mantengono un alto livello di astrazione e riescono a cogliere solo parzialmente la complessità dei fenomeni applicativi;
ii) tutti i modelli proposti nella letteratura risultano inadeguati a rappresentare le caratteristiche messe in risalto dalle nuove tecnologie di codifica, trasmissione e comunicazione;
iii) gli algoritmi proposti in ambito ingegneristico spesso si basano su risultanze sperimentali, senza assicurare idonee basi metodologiche e matematiche; risultano nella pratica dei pacchetti software di massiccia computazione ("number crunching") non basati sullo sfruttamento matematico/algoritmico delle proprietà strutturali dei problemi da risolvere.

La proposta progettuale, per ovviare alle carenze elencate sopra, è basata sul seguente approccio: studiare nuovi modelli per la progettazione e gestione di reti di telecomunicazione - in particolare le reti basate sulle nuove tecnologie, adottate e previste -, di "estrarne" le caratteristiche strutturali, di proporre algoritmi di Ottimizzazione e Simulazione basati su tali caratteristiche, di provare su casi "benchmark" e dati reali il software prodotto al fine di renderlo utilizzabile da terzi, e di renderlo disponibile sia in ambiente di ricerca che in ambiente produttivo.
Tale "filosofia" di approccio è presente in molti progetti di ricerca sui fondamenti e sulle applicazioni, in particolare in Nord America, Europa e Giappone. In particolare, in Italia, riferendosi solo agli ultimi anni, sono stati presentati progetti specifici sulla tematica delle reti di comunicazione e con l'approccio indicato: due progetti MURST cofinanziati, un progetto strategico MURST (anno 1999), alcuni progetti in Agenzia 2000 del CNR.

La presente proposta progettuale parte dalle risultanze ottenute con i progetti, sopra indicati, già terminati e da quelle previste nei progetti in via di completamento. Essa può essere vista come il raccordo e completamento degli sforzi di ricerca anche dei progetti precedenti per ottenere una "risposta" coordinata e organizzata ai bisogni crescenti delle aziende di produzione e di gestione di sistemi di comunicazione di poter accedere velocemente al Know-How.

In particolare, in tale progetto si affrontano le problematiche relative alle reti di fonia fissa e "wireless" comprese le reti UMTS, alle reti ottiche di nuova generazione (WDM), alle reti a larga banda, alle reti radio-televisive digitali, ecc. Si affrontano le problematiche relative al posizionamento (siting) di antenne e nodi di rete, alla distribuzone di risorse (frequenze, capacità, potenze, devices di codifica/decodifica, ecc.), al dimensionamento delle reti secondo politiche diverse di trasmissione, alla loro protezione rispetto a guasti e sovraccarichi, alle problematiche relative alla forte aleatorietà della domanda di comunicazione, alle politiche di instradamento delle informazioni, ecc.

2. Progettazione a più fasi
La complessità della tematica relativa alle reti deriva anche dai numerosi vincoli di natura geografica, tecnologica, organizzativa, di affidabilità, di sicurezza, di manutenzione, ecc., che ne caratterizzano e complicano la fase di progettazione. Di conseguenza, spesso, la progettazione delle reti di telecomunicazione è normalmente affrontata in più fasi successive.
Una prima fase comporta una distinzione in base alla tecnologia/metodologia impiegata. In particolare, si distingue tra:
- livello delle infrastrutture fisiche (ad esempio, fibra ottica, ponti radio, cavi in rame, ecc.);
- livello trasmissivo, cioè la definizione di canali di comunicazione di capacità predefinita tra due punti qualunque della rete, indipendentemente dal mezzo fisico a disposizione (infatti possono coesistere diversi mezzi fisici quali, ad esempio, il doppino in rame seguito da una fibra ottica e quindi un ponte radio), assieme ai meccanismi di protezione, in modo che in caso di guasto di una apparato o di un mezzo fisico sia disponibile un mezzo ed un canale di riserva;
- livello di commutazione, cioè l'impiego dinamico dei canali trasmissivi messi a disposizione dal livello precedente per creare connessioni tra utenti;
- livello dei servizi; ad esempio, per la rete radiomobile si può citare il database per fornire la posizione di ogni cellulare per instradare correttamente le chiamate entranti; per la rete Internet, i server in grado di convertire i nomi in indirizzi (DNS), ecc.

Una seconda fase di progetto distingue in base all'area geografica da coprire: reti internazionali, backbone nazionali, network regionali e distrettuali, aree locali, reti urbane, e così via, sino a giungere al singolo utente.

3. Progettazione, tecnologie, ambito territoriale
Per quanto riguarda la prima fase, in sintesi, le tecnologie attualmente impiegate sono:
a) Livello di infrastrutture fisiche/utenti finali (ultimo miglio):
- fibra ottica, costosa in termini di fornitura, posa e gestione ma di capacità elevatissima;
- doppino in rame, economico, ma soggetto a vincoli stringenti in termini di lunghezza massima utilizzabile in funzione della velocità richiesta;
- cavo coassiale in rame, usabile dove è presente la TV via cavo;
- ponte radio, costoso per singoli utenti, soggetto a limitazioni in termini di visibilità ottica dei punti da collegare.
b) Livello di infrastrutture fisiche/area geografica:
- fibra ottica;
- ponte radio.
c) Livello trasmissivo
- su fibra ottica e ponte radio, SDH/SONET;
- su sola fibra ottica, in ambito ristretto ed in sperimentazione, Gigabit Ethernet o ATM over fiber;
- su rame, in ambito ristretto, l'insieme delle tecnologie xDSL (ADSL, HDSL, SDSL, VDSL, ecc.), i cable modem (solo su coassiale);
d) Livello di commutazione:
- ATM (la più consolidata);
- Internet Protocol (IP);
- Ethernet-Virtual LAN.

Nella creazione di una rete a larga banda l'obiettivo che ci si pone è quello di fornire un servizio di comunicazione sostanzialmente di tipo dati con protocollo IP, ad alta velocità, diretto sia verso la rete Internet, sia verso fornitori di servizi locali, sia verso Internet Data Center in cui vengono accentrati gli elaboratori server di numerosi fornitori di servizi.

Nella seconda fase della progettazione si possono distinguere due principali livelli, importanti per il mercato italiano:
a) le reti nazionali/regionali.
Si deve determinare la topologia di rete che collega tutte le città, paesi, ecc. con connessioni di capacità adeguata, al minimo costo, sfruttando le infrastrutture (ad esempio, fibre ottiche, nodi di commutazione) già esistenti, prevedendo le necessarie vie di riserva, stabilendo ampliamenti di capacità o la posa di nuove infrastrutture se necessari. La topologia della rete è ovviamente dettata dal traffico e dalla tecnologia scelta. A questo livello, normalmente buona parte delle infrastrutture (fibre ottiche) sono già presenti. Non sono risolti i problemi decisionali relativi a quali infrastrutture usare, qual sia la richiesta di capacità e, se del caso, quando, dove e con quali modalità ampliare la capacità trasmissiva.

b) le reti urbane/locali
Il problema è quello di costruire una nuova infrastruttura fisica che copra gli utenti residenziali e business. La tecnica più diffusa è formata da "anelli" in fibra ottica che coprono più o meno la città, con gli utenti collegati con doppino in rame (per connessioni sino ad una certa velocità) o in fibra ottica (per connessioni ad altissima velocità). Le tecnologie più consolidate sono SDH/SONET (su fibra) ed xDSL (su rame) con commutazione ATM. Altre tecniche prevedono di sostituire l'xDSL con ponte radio (wireless local loop). Tecnologie ancora in sperimentazione prevedono la connessione di tutti gli utenti con fibra ottica e Gigabit Ethernet (il costo è maggiore per il mezzo fisico, ma minore per gli apparati di commutazione). In generale bisogna progettare la rete di costo minimo scegliendo le infrastrutture (scavi, ponti radio, apparati, pozzetti, ecc.) tenendo conto della tecnologia di commutazione (ATM, IP, Ethernet) e di trasmissione (SDH, Gigabit Ethernet), della topografia della zona da coprire, della densità degli utenti potenziali, della dislocazione delle centrali e degli armadi di distribuzione per il rame, delle le tubazioni e delle fibra ottiche già presenti, delle lunghezze massime ammesse per le tratte in rame o fibra, dei permessi di scavo ed infine della la posizione dei maggiori produttori di traffico.

Va comunque tenuto presente che la distinzione tra reti urbane/locali e reti nazionali/regionali può essere sfumata.

4. Stato dell'arte per la progettazione di reti
Per i problemi di progettazione delle capacità delle reti (Network Design) esistono in letteratura importanti contributi. Lo studio delle proprietà poliedrali e delle formulazioni per il caso di flussi "splitting" è stato sviluppato, tra gli altri, in Barahona [Ba96], Bienstock et al. [Bi-al98], Gunluk [Gu99], per il caso "non splitting" si veda [BrGuWo96]. Gli algoritmi di Branch&Cut esistenti non riescono ancora a risolvere all'ottimo istanze con pochi nodi ed archi (ad es. i problemi SUN, con 27 nodi e 104 archi). I problemi di Network Design con flussi "non-splitting" sembrano presentare un livello di difficoltà ancora maggiore. Pertanto sembra essere necessario un più approfondito studio delle proprietà poliedrali.
Questi problemi sono difficili anche a causa della grande numero di variabili necessarie alla formulazione: la soluzione dei rilassamenti lineari dei modelli può rivelarsi un compito proibitivo anche per i migliori pacchetti commerciali di programmazione lineare. Diventa così necessario investigare strategie alternative, tra le quali è possibile citare lo sviluppo di codici specializzati per la programmazione lineare strutturata, con particolare riguardo per i problemi di flusso di costo minimo di tipo "multicommodity", [CaFr01a] assieme alle tecniche di rilassamento lagrangiano [FrGa99, CaFr01b].
Un tema centrale della proposta di ricerca riguarda lo studio di problemi di Network Design per reti ottiche WDM che sono state introdotte per utilizzare in modo efficiente le fibre; più segnali possono venire trasmessi su una stessa fibra assegnando loro differenti lunghezze d'onda che vengono processate indipendentemente in ogni nodo della rete.
Un aspetto ritenuto cruciale nelle reti WDM è il posizionamento ottimo dei connettori ottici [KaAy98, Ma98]. Il disegno di reti completamente ottiche è decisamente uno dei problemi più interessanti e promettenti del settore. [WaDe96, RaSi96, Mu96, ChSaMa00] propongono alcuni modelli matematici e euristiche per il disegno considerando solamente i costi relativi ai collegamenti. Tuttavia dato l'attuale costo elevato delle apparecchiature ai nodi è necessario introdurre esplicitamente costi associati ai nodi della rete. Risultati preliminari sono presentati in [MiSa98].
Infine le reti devono essere progettate per poter essere resistenti ai guasti (vedi ad esempio [BaMaMi98, GuPiSo99, GuMaRi00]). Il Survivable Network Design è un altro tema importante affrontato nel progetto.

5. Stato dell'arte per la localizzazione e dimensionamento di nodi di rete
La problematica della localizzazione è molto vasta e non è possibile fornire qui una descrizione esaustiva. Si preferisce annotare le problematiche più innovative e specifiche al tipo di approccio oggetto della presente proposta progettuale.

a) Assegnamento di frequenze (FAP) in reti radiomobili cellulari
Il FAP è una delle applicazioni chiave nei sistemi cellulari: l’area complessiva servita è divisa in tante sottoaree o "celle" ciascuna delle quali è "coperta " da una stazione radiobase di potenza più limitata. Le varie stazioni radiobase sono coordinate tra loro da un sistema di controllo e servono l’utente solamente entro il proprio dominio di copertura; allorché l’utente in movimento esce dal dominio di copertura di una stazione radiobase, automaticamente gli viene assegnato, senza interruzione di servizio, un canale radio libero nel domino di una stazione adiacente (handover). Le frequenze radio che sono complessivamente disponibili vengono ripartite tra le stazioni radiobase in modo da poter riutilizzare periodicamente in celle opportunamente distanziate tra loro canali alla stessa frequenza senza che si manifestino tra loro interferenze. Si deve pertanto assegnare un numero limitato di frequenze ad ogni cella radio, minimizzando l’interferenza elettro-magnetica causata dal riutilizzo delle frequenze di trasmissione.
Il problema dell'assegnazione delle frequenze può quindi essere espresso come segue: data una rete di trasmettitori e un insieme di frequenze disponibili, si tratta di assegnare frequenze a trasmettitori in modo da massimizzare una funzione del rapporto segnale rumore nei punti di verifica raggiunti dal segnale (Frequency Assignment Problem, FAP). FAP può essere ridefinito come il problema di assegnare colori (frequenze) ai nodi (trasmettitori) di un grafo non orientato in modo da minimizzare una funzione degli archi e dei colori assegnati ai loro estremi. Una prima sistemazione dell'approccio "graph"-teoretico è presentata in [Ha80], dove FAP viene rappresentato come generalizzazione del noto problema di colorazione di grafi.
Sono state proposte diverse euristiche per la ricerca di soluzioni ammissibili di "buona" qualità [Ku91], [Co93], [CaHuSt96], [HuSmTh98]. Lower bounds basati su diversi tipi di rilassamento sono presentati in [Ga86].
In letteratura esistono due principali varianti del problema:
- Minimum Span FAP (MS-FAP): A ciascun arco del grafo d'interferenza è associato un intero non negativo che rappresenta la minima distanza (in modulo) che le frequenze assegnate agli estremi dell'arco devono soddisfare affinché i due trasmettitori corrispondenti siano non interferenti.
- Minimum Interference FAP (MI-FAP): A ciascun arco del grafo d'interferenza è associato un vettore reale non negativo la cui componente i-esima rappresenta il costo di violazione quando le frequenze assegnate ai suoi estremi hanno distanza esattamente i.
Per la prima versione, un certo numero di algoritmi per il calcolo di lower bound fa uso di una riduzione di FAP al problema di commesso viaggiatore (TSP) sul grafo dei trasmettitori [Ra85], [HuSmTh98], [AvMaSa01].
Per la seconda versione del problema un modello standard consiste nel definire un nuovo grafo, detto "dei conflitti" o split-graph, ottenuto dal grafo dei trasmettitori sostituendo l'i-esimo nodo con un "clique" di dimensione pari al numero di frequenze disponibili nella banda [Aa-al98].
Per questo modello sono presenti in letteratura alcuni algoritmi esatti basati su tecniche poliedrali. Il problema di FAP viene formulato come problema di Vertex Packing con vincoli aggiuntivi in [Aa-al98], [Fi-al96]. Un algoritmo di enumerazione implicita è studiato in [MaSa99]. Inoltre, la maggior parte delle euristiche sono implicitamente basate sul grafo dei conflitti.
Recentemente un approccio basato sulla rappresentazione di MI-FAP come problema di max k-cut è stato proposto in [EiGrKo00]. Questo modello è risolto con tecniche di programmazione semidefinita per calcolare lower bound per l'interferenza di reti cellulari di grandi dimensioni.

b) Problema di siting per reti di trasmissioni radiotelevisive digitali (DAB/DVB)
La progettazione di reti di trasmissione DAB e DVB comporta la scelta dei siti geografici ove localizzare le antenne trasmittenti, e il contemporaneo assegnamento delle potenze di emissione e delle frequenze di trasmissione con l’obiettivo di massimizzare la copertura del territorio. Nella letteratura scientifica e nella pianificazione pratica il problema di "siting" (scelta dei siti + assegnamento di potenze) e il problema di assegnamento di frequenze vengono risolti separatamente. A causa della sua importanza applicativa e teorica, il problema di assegnamento di frequenze è stato ampiamente studiato in letteratura. Per quanto riguarda il problema di siting, esistono in letteratura alcuni modelli di programmazione lineare intera, mentre gli algoritmi di soluzione proposti sono di tipo euristico. Si veda, tra gli altri, [Br93], [Be95], [Li97], [LiZa99], [MaSc00], [RoSaSm01].

c) Localizzazione e dimensionamento di nodi in reti LAN
In una rete di comunicazione locale LAN, formata da una connessione diretta dei vari utenti a concentratori e una connessione ad alta velocità e capacità tra concentratori, un problema specifico è dato dalla localizzazione e dimensionamento dei concentratori, assieme all'assegnamento degli utenti ai concentratori, rispettando vincoli sul numero di utenti per concentratore e bilanciando anche il traffico tra concentratori. Spesso il problema è trattato a più fasi, ad esempio prima si effettua l'assegnazione degli utenti a un numero prefissato di concentratori, quindi la localizzazione e il dimensionamento dei concentratori, infine il bilanciamento mediante riassegnazione degli utenti ai concentratori; per maggiori dettagli, si rinvia a [RoSo77], [Pi87], [Bo89]. Per ottenere reti LAN più affidabili (migliore distribuzione del carico tra concentratori) e più economiche (intervenendo sul numero di concentratori e sulla struttura della rete di connessione tra essi) si stanno studiando problemi sempre più complessi, mischiando opportunamente le fasi sopra descritte. Ne sono scaturiti diversi approcci quali l'Hub Location, il Capacitated Plant Location e lo Spanning Forest Covering. Per i vari aspetti metodologici e algoritmici per affrontare il problema si rinvia, tra gli altri a [DeLaMa96] [DeMa96a], [DeMa96b], [DeMa96c] , [DeMa01].

6. Stato dell'arte per la modellazione e l'istradamento del traffico
L'analisi di scenari di traffico sulle reti di comunicazione è una componente importante nei modelli per la progettazione di reti. Diversi sono i problemi legati allo studio ella modellazione e dell'istradamento del traffico; tra gli altri citiamo:
- l'analisi di traffico altamente aleatorio per il quale un progetto basato sui picchi comporterebbe un sovradimensionamento delle reti mentre, al contrario, una progettazione sui valori medi comporterebbe frequenti eventi di sovraccarico di traffico;
- l'istradamento su percorsi differenziati per mantenere un buon bilanciamento del traffico di rete.

Il primo tipo di problemi può essere affrontato con tecniche di ottimizzazione stocastica [To-al98] o studiato mediante simulazione del processo [Le-al94], [PaFl95].
Modelli di programmazione stocastica definiti in modo da rappresentare l’andamento incerto della domanda sono stati proposti in [FrLu82], [Lo86], [Ga94], [StToVa97], [FaGa97].
Un utile strumento per la loro modellazione del traffico in reti di telecomunicazione è rappresentato dai sistemi a coda (con funzioni di distribuzione di tipo classico e self-similar). Essi, infatti, permettono un’analisi accurata delle prestazioni dei sistemi e forniscono indicazioni utili per la loro sintesi. Sono stati utilizzati modelli di traffico di tipo Markoviano [Lu91], sistemi non tradizionali, detti sistemi con retrials, server searching for customers and vacation [Bo-al00], Da-al00], [Bo-al01a].
I processi "self-similar" sono risultati particolarmente adatti alla modellazione del traffico multimediale, si veda [Le-al94], [PaFl95], [Be-al95].

Il secondo tipo di problemi è affrontato secondo tecniche di ottimizzazione distribuite nei nodi della rete. Ad esempio, nelle reti a commutazione di pacchetti ciascun pacchetto viene smistato dal nodo in cui esso si trova attualmente al meno congestionato tra i nodi adiacenti (istradamento "hop-by-hop" o Open Shortest Path First). L'operatore del servizio può controllare la congestione della rete e bilanciarne il flusso cambiando dinamicamente le "distanze virtuali" tra i nodi. In tal modo la rete risponde adattivamente e localmente alla congestione. Approcci diversi, basati sulla valutazione del carico per cammini piuttosto che per archi, sono studiati e solo in parte applicati: i) strategie di "egualizzazione" il più possibile i flussi lungo i cammini tra coppie di concentratori; ne deriva un problema di flusso multicommodity con funzione obiettivo concava e lineare a tratti da massimizzare; ii) tecniche di "label based forwarding", in cui il protocollo di trasmissione permette, dall'analisi della "label" del pacchetto, l'istradamneto di ogni pacchetto indipendentemente dagli altri secondo considerazioni di qualità e disponibilità di risorse (Multi Protocol Label Switching) [Che98] [Law01], [Gho01].

Bibliografia
[Aa-al98] K. Aardal, A. Hipolito, C.P.M. Van Hoesel, B. Jansen, A branch and bound algorithm for the frequency assignment problem, Tech. Rep., 1998;
[AvMaSa01] A. Avenali, C. Mannino, A. Sassano, Minimizing the Span of d-walks to Compute Optimum Frequency Assignments, to appear in Mathematical Programmino, 2001;
[Ba96] F. Barahona: Network Design Using Cut Inequalities, SIAM J. Optimization 6(3), 823-837, 1996;
[BaMaMi98] Balakrishnan A., Magnanti T.L. and Mirchandani P., Designing hierarchical Survivable networks, Operations-Research. vol.46, 116-36, 1998;
[Be95] R. BEUTLER, Optimization of Digital Single Frequency Networks, Frequenz, 49, 11 - 12, Nov - Dec 1995.
[Be-al 95] J. Beran, R. Sherman, M.S. Taqqu, and W. Willinger, Long-Range Dependence in Variable-Bit-Rate Video Traffic, IEEE Trans. Comm., Vol. 43, No 2/3/4, pp. 1566-1579, 1995;
[Bi-al98] D. Bienstock, S. Chopra, O. Gunluk, C. Tsai: Minimum Cost Capacity Installation for Multicommodity Network Flows, Math. Prog. 81 (1998), 177-199.
[Bo89] Boffey, T.B. (1989). Location problems arising in computer networks. J. Operational Res. Society, 40(4), 347-354.
[Bo-al 00] P.P. Bocharov, C. D’Apice, B. D’Auria, S. Salerno, A queueing system of finite capacity with the server requiring a priority search for customers, Vestnik Rossiyskogo Universiteta Drujbi Nardov, Seria Prikladnaia Mateormatika i Informatika, No 1., 50-61, 2000;
[Bo-al 01a] P.P. Bocharov, C. D’Apice, R. Manzo, N.H. Phong, On a Multiclass arrival retrial MK/GK/1/r Queueing System with Finite Buffer, Proceedings of 16th Belarus Winter Conference in Queueing Theory, Minsk 2001;
[Br93] R. BRUGGER, DAB coverage of interfering single frequency networks, CCETT GT R1/DIG 167, Jun. 1993
[BrGuWo96] B. Brockmuller, O. Gunluk, L. Wolsey: Designing Private Line Networks - Polyhedral Analysis and Computation,Technical Paper Cornell University, 1996;
[CaFr01a] J. Castro, A. Frangioni "A Parallel Implementation of an Interior-Point Algorithm for Multicommodity Network Flows" Lecture Notes in Computer Science vol. 1981, Vector and Parallel Processing - VECPAR 2000, J.M. Palma. J. Dongarra and V. Hernandez eds., Springer-Verlag, p. 301 - 315, 2001
[CaFr01b] J. Castro, A. Frangioni, Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems, INFORMS JOC, to appear, 2001;
[CaHuSt96] D.J. Castelino, S. Hurley, N.M. Stephens, A tabu search algorithm for frequency assignment, Annals of Operations Research, 63:301-319, 1996;
[Che98] Chen S., Nahrstedt K. (1998) An overview of Quality of Service
routing for next-generation high-speed networks: problems and solutions, IEEE Networks Nov-Dec 98, 64-79.
[ChSaMa00] S. Chamberland, B. Sanso', O. Marcotte, Topological design of two level telecommunication networks with modular switches, Operations Research, Vol. 48, no. 5, pp. 745-760, 2000;
[Co93] D. Costa, On the use of some known methods for T-colourings of graphs. Annals of Operations Research, 41:343-358, 1993;
[Da-al00] C. D’Apice, R. Manzo, N.H. Phong, S. Salerno, Retrial queueing system with several input flows and with vacations, Vestnik Rossiyskogo Universiteta Drujbi Nardov, Seria Prikladnaia Mateormatika i Informatika, No 1., 62-73, 2000;
[DeLaMa96] M. Dell'Amico, M. Labbe', F. Maffioli (1996), "Complexity of Spanning Tree Problems with Leaf-Dependant Objectives",Networks 27.
[DeMa96a] M. Dell'Amico, F. Maffioli (1996),"On Some Multiciriteria Arborescence Problems: Complexity and Algorithms", Discr. Appl. Math. 65.
[DeMa96b] M. Dell'Amico, S. Martello (1996), "Open Shop, Satellite Communication and a Theorem by Egervary" Operations Research Letters 18.
[DeMa96c]M. Dell'Amico, S. Martello (1996), "The K-Cardinality Assignment Problem", Discrete Applied Mathematics 76.
[EiGrKo00] A. Eisenblatter, M. Groetchel, A. Koster, Frequency Assignment and Ramifications of Coloring. Konrad-Zuse-Zentrum f"ur Informationstechnik Berlin, ZIB-Report 00-47, 2000;
[FaGa97] Fantauzzi F. and A.A. Gaivoronski, Optimal design of backbone ATM network with dynamic capacity reallocation, International Symposium on Mathematical Programming, Lausanne, 25-29 August 1997.
[Fi-al 96] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur, E. Toto, Frequency Assignment in Mobile Radio Systems using branch-and-cut techniques, to appear, 1996;
[FrGa99] A. Frangioni, G. Gallo, A Bundle Type Dual-Ascent Approach to LinearMulticommodity Min Cost Flow Problems, INFORMS JOC 11(4), p. 370 - 393, 1999;
[FrLu82] Franca P.M. and Luna H.P.L., Solving stochastic transportation-location problems by generealized Benders decomposition, Transportation Science, 1982.
[Ga86] A. Gamst, Some lower bounds for a class of frequency assignment problems. IEEE Transactions on Vehicular Technology, 35:8-14, 1986;
[Ga94] A.A. Gaivoronski, Robust access planning for ATM network in presence of uncertain multiservice demand. In NETWORKS’94 "Planning for a customer-responsive network", September, 1994.
[Gho01] Ghosh D., Sarangan V., Acharya R., (2001) Quality-of-service
routing in IP networks, IEEE Transactions on Multimedia, Volume: 3 Issue: 2, June 2001, 200 -208
[Gu99] O. Gunluk, A Branch-and-Cut Algorithm for Capacitated Network Design Problems, Math. Prog. 86, 17-39, 1999;
[GuMaRi00] Gutierrez M., Marianov V. and Rios M., Survivable capacitated network design problem: new formulation and Lagrangian relaxation, Journal of the Operational Research Society, 51, 574-82, 2000;
[GuPiSo99] Gupta R., Pirkut H. and Soni S., Survivable network design: the state of the art, Information-Systems-Frontiers. vol.1, 303-15, 1999;
[Ha80] K. Hale, Frequency assignment: Theory and applications. Proc. IEEE, 68:1497-1514, 1980;
[HuSmTh98] S. Hurley, D.H. Smith, S.U. Thiel, Improving heuristics for the frequency assignment problem, EJOR 107, 76-86, 1998;
[KaAy98] E. Karasan, E. Ayanoglu, Performance of WDM transport networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp. 1008-1023, 1998;
[Ku91] D. Kunz, Channel assignment for cellular radio using neural networks. IEEE Transactions on Vehicular Technology, 40(1):188-193, 1991;
[Law01] Lawrence J. (2001) Designing multiprotocol label switching
networks, IEEE Communications Magazine , Volume: 39 Issue: 7, July 2001, 134 -142
[Le-al 94] W.E. Leland, M.S. Taqqu, W. Willinger, D.V. Wilson, On the Self-Similar Nature of Ethernet Traffic (extended Version), IEEE Trans. Networking, Vol. 2, No. 1, pp.1-15, Febr. 1994;
[Li97] A. LIGETI, Coverage Optimization in Digital Audio Broadcasting Networks, Licentiate thesis, Dept. of Signals, Sensors and Systems, Royal Institute of Tech., 1997 Siting:
[LiZa99] A. LIGETI, ZANDER J., Minimal Cost Coverage Planning for Single Frequency Network, IEEE Transaction on Broadcasting, 1999
[Lo86] Louveaux F.V., Discrete stochastic location models, Annals of Operations Research, 1986.
[Lu91] D.M. Lucantony, New results on the single-server queue with a batch Markovian arrival process. Communications in Statistics- Stochastic Models., Vol. 7, pp. 1-46, 1991;
[Ma98] M.W. Maeda, Management and control of transparent optical networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp. 1081-1096, 1998;
[MaSa99] C.Mannino, A.Sassano, An enumerative algorithm for the frequency assignment problem, to appear in Discrete Applied Mathematics., 1999;
[MaSc00] R. Mathar, M. Schmeink, Optimal Base Station Positioning and Channel Assignment for 3G Mobile Networks by Integer Programming, 2000;
[MiSa98] Y. Miyao, H. Saito, Optimal Design and Evaluation of Survivable WDM Transport Networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp.1190-1198, 1998;
[Mu96] B. Mukherjee et al., Some principles for designing a wide-area optical network, in Proc. of INFOCOM, vol. 1, pp. 110-119, 1996;
[PaFl95] V. Paxson, S. Floyd, Wide-Area Traffic: The Failure of the Poisson Modeling, IEEE/ACM Trans. Networking, 3(3), pp.226-224, June 1995;
[Pi87] Pirkul, H., (1987). Efficient algorithms for the capacitated concentrator location problem. Computer and Operation Research, 14(3) 197-208.
[Ra85] A.Raychauduri. Intersection assignments, T-colourings and powers of graphs, PhD thesis, Rutgers University, 1985;
[RaSi96] R. Ramaswami, K.N. Sivarajan, Design of logical topologies for wavelength-routed optical networks. IEEE Journal on Selected Areas in Communications /JLT Special Issue on Optical Networks, 1996;
[RoSaSm00] F. Rossi, A. Sassano, S. Smriglio, Models and Algorithms forTerrestrial Digital Broadcasting, Math. of Indust. Syst.,to appear, 2000;
[Roso77] Ross, G.T. and Soland R.M. (1977) Modeling facility location problems as generalized assignement problems. Management Science, 24(3), 345-357.
[StToVa97] L. Stougie, A. Tomasgard and M.H. Van der Vlerk, Some approaches for solving the stochastic service provision problem, Working paper, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7034 Trondheim, Norway, 1997.
[To-al98] A. Tomasgard (HP), J. A. Audestad (HP), S. Dye (HP), L. Stougie (HP), M. H. van der Vlerk (HP) and S. W. Wallace (HP), Modelling aspects of distributed processing in telecommunication networks, Annals of Operations Research, Vol. 82, pp. 161-184, 1998.
[WaDe96] N. Wauters, P. Demeester, Design of the optical-path layer in multiwavelength cross-connected networks, IEEE Journal on Selected Areas in Communications, vol. 14, no. 5 pp. 881-892, 1996;

1. Introduction
In the last years there have been a wide increase in the importance of the communication systems which greatly changed in the transmission and memorisation technology, in the quantity of information transmissible for each time unit and in the integration of different sources of information (voice, data, images, etc.). This transformation is still in progress and the possible future scenarios show the great importance of reliable wide band transmission network, designed and managed with high efficiency.

This is a natural context for using tools and methodologies from Operations Research. Indeed the Optimization and Simulation methods have already been applied in the designing and planning phases of communication networks and in the management of this networks accordingly to efficiency and effectiveness criteria. The research effort of the last years has shown, both at national and international level, that the graph Optimization and Simulation methodologies can be effectively used to solve practical problems in telecommunication.

In the literature there are many and qualified contributions related to the application of Optimisation and Simulation models and methods to the solution of telecommunications network planning and management problems.
The analysis of existing contributions evidences that:
i) in the mathematical literature there are models which often have a high level of abstraction and manage to catch the complexity of real applications and technological evolution just partially;
ii) all the proposed methods poorly represent the characteristic of the new coding and transmitting technologies;
iii) within engineering sectors, proposed algorithm are based on experimental results thus offering a scarce methodological-mathematical content. In practice they are basically number crunching packages that do not use effectively the mathematical structures of the problems.
The present project is aimed at providing a contribution to fill that gap, with the following approach: to study new models for designing and managing communication networks, in particular those based on new technologies (existing or forthcoming); identify the structural characteristic of the new problems and develop Optimisation and Simulation models and algorithms able to solve real life “benchmark”; make available the resulting software to the research and industrial laboratories. The research will be based on the most recent methodologies in Mathematical Programming and Queuing Networks. This approach is common to several research projects in North America, Europe end Japan. In particular in Italy, looking at the last two years, there have been presented national projects tailored on these themes: two projects founded by MURST and one “strategic project” founded by “Agenzia 2000”, CNR.

This proposal starts from the results of the above mentioned projects and can be viewed as a continuation and enhancement of that research. The aim of the project is to obtain an organised answer to the increasing needs of up-to-date “know-how” of the firms producing and managing the communication networks.

In particular the project will address problems in the designing of fixed and wireless networks including UMTS cellular networks, new generation optical networks (WDM) and digital radio-television networks. We will study problems relative to the siting of antennas and equipment, to the distribution of resources (frequency, bandwidth, coding devices, etc..), to the dimensioning of the network accordingly to different transmission policies and to survivability requirements, to the stocasticity of the demand and to routing policies.

In the following a short – and necessarily non exhaustive – description of the scientific background for each of the main sub-themes of the present proposal is presented. In the section "Description of the research programme" the methodological and technical approach we adopt will be described in detail, stressing the most original aspects and the main innovations we expect to add w.r.t the present state of the art.

2. Designing by decomposition
The design of real life communication networks is a complex task and is generally subject to a number of complex constraints of different type, such as, geographical, technological, organizational, etc. The direct consequence of this fact is that the design of telecommunication network is generally tackled in successive phases.
Firstly, it is necessary to make a distinction based on the technology and methodology used. In particular, it is necessary to distinguish between:
- physical infrastructures level (i.e., optic fibres, radio links, copper wires, etc.);
- transmission level. (Design of fixed capacity channels between any two points of the network without taking care of the physical means. The link might use different physical means, for example, copper pair, optic fibre, radio link, etc. Moreover protection measures must be adapted in case of an apparatus or physical mean fault in order to have an available mean and a supply channel);
- commutation level. (It is applied in a dynamic way the transmission channels available from the previous level to create a connection between customers).
- service level. (For the radio car network it is possible to use the database able to provide the position of each mobile-phone to correctly route the incoming calls. For the internet network the server able to convert the names in addresses (DNS), etc. The server dislocation is essential for a good network working).

A second project phase marks related to the geographical area to cover: international network, national backbone, regional and district network, local area, urbane network, and so on, up to the single user.

3. Design, technologies, geographical environment
Speaking about the first phase, briefly, technologies used today are.
a) Physical infrastructures level/final user (last mile):
- optic fibres, expensive equipment, pose and managing but of high capacity;
- copper pair, cheap, but subject to tight constraints in terms of maximum usable length as function of the required speed;
- copper coaxial cable, usable where is present a cable TV;
- radio link, expensive for single user, subject to limitations in terms of optical visibility of points to be connected;
b) Physical infrastructures level/geographic areas;
- optic fibre (the most preferred choice);
- radio link (of limited capacity and used only for the worst getting area).
c) Transmission level:
- on optic fibre and radio link SDH (Synchronous Digital Hierachy)/SONET
- just on optic fibre, in delimited context and in experiment, Gigabit Ethernet over fiber or ATMoverfiber;
- on copper, in delimited context, the set of technology xDSL (ADSL,HDSL, SDSL, VDSL, etc.), and cable modem (only coaxial).
d) Commutation level:
- ATM (Asynchronous Transfer Mode, the most consolidated);
- IP;
- Ethernet-Virtual LAN.

In the design of a wide band telecommunication network the given aim is to provide a high speed commutation service mostly of IP protocol data type (Internet Protocol), addressed to the internet network, the local service supply, the internet data center in which the service supply servers are centralized and also addressed to other service provider.
In the second project phase it is possible to distinguish between two main levels:
a) National/regional networks
The problem is to establish the topological network that links all the cities, towns, etc., with connection of suitable capacity at minimum cost, making the most of the existing infrastructures (for example optical fibres, commutation nodes) foreseeing the necessary reserve ways, establishing if it is necessary capacity incensement or the setting of new infrastructures. The network topology obviously is given by the traffic and the technology chosen. At this level, normally, most of the infrastructures (optical fibres) are already present. What is to decide is, generally, which infrastructures must be used and what is the required capacity and, in case to increase the transmission capacity and to decide which is the way.
b) Urban/local network
The problem is to build a new physical infrastructures covering the residential and business users. A well spread technique foresee the set of optical fibre "rings" which cover, more or less the city, while every user is linked with pair copper (limited speed) or in optical fibre (for high speed connection). The most well established technologies are SDH/SONET (on fibre) and XDSL (on copper) ATM commutation. Other techniques foresee to substitute the XDSL with the radio link (wireless local loop). Still testing technologies forecast the connection of all users with optic fibre and Gigabit Ethernet (the higher cost I due to the physical means, the lower to the commutation apparatus). Generally speaking, given the commutation technology (ATM, IP and
Ethernet), the topography are to cover, the potential user density in different areas, the plant and the copper cabinet distribution location, the pipes and the optical fibre, the maximum feasible length for copper or fibre trade, the permit for available or not available diggings, the preparation times, the position of the major traffic producers, it needs to project the infrastructures network (digging, radio link, apparatus, etc.) of minimum cost.
It must be take into account that the distinction between the urban local network can be vanished. Some operators use national/regional commutation or transmission nodes (which is a network with a transport function) also in order to answer the urban/local network necessity (which is a collecting network). This allowed to provide the high speed connection service to a restricted number of important customers located in places crossed by the transportation network.

4. Network Design: the state of the art
For Network Design problems important contribution exists in the literature. Mathematical formulations and polyhedral properties in the case of “splittable” flows have been proposed, among others, in Barahona [Ba96], Bienstock et al. [Bi-al98], Gunluk [Gu99]. For the “non-splitting” case see e.g. [BrGuWo96]. The existing Branch & Cut algorithms are not yet able to solve exactly instances with a small number of nodes and links (e.g. problems SUN, with 27 nodes and 104 links). The Network Design problems with "non-splitting" flows seems to be harder. Therefore it is necessary to study more deeply the polyhedral characteristics of such problems.
The network design problems are also hard because of the large number of variables needed for the mathematical formulation: the solution of continuous linear relaxation of such models can be a prohibitive task also for the more efficient commercial solvers. It is then necessary to investigate alternative strategies as specialised methods for structured linear programming, and more specifically the models arising in the context of the multicommodity flow (see Castro et. al [CaFr01]) and the Lagrangean relaxation method (see Frangioni et. al [FrGa99, CaFr01b]).
A main theme of our proposal is the study of Network Design problems for optical WDM networks. The WDM networks have been introduced to effectively use the existing optical fibers: different transmission signals can be transmitted on the same fiber by assigning them different wavelength that can be processed separately in each node of the network.
A key issue in an optical WDM network is the placement of the optical cross-connectors [KaAy98, Ma98]. The design of all-optical-networks is certainly one of the most interesting and promising problems in this field. [WaDe96, RaSi96, Mu96, ChSaMa00] propose mathematical models and heuristic algorithms for a design problem considering only the costs on the links. However to take into account the existence of the current high costs of the optical cross-connectors it is necessary to introduce explicitly this costs on the nodes of the network. Some result in this direction is reported in [MiSa98].
Finally a network must be designed so that it can recover a link or node failure (see. e.g. [BaMaMi98, GuPiSo99, GuMaRi00]). The Survivable Network Design Problem is another important issue of this proposal.

5. Location and dimensioning of the nodes of a network: the state of the art.
The telecommunication problems that can be viewed as location and resource dimensioning problems are very numerous. Therefore we prefer to outline only some of the most recent problems with a specific interest in the context of the proposal.

a) Frequency assignment in cellular radio mobile communication
The Frequency Assignment Problem (FAP) is one of the key issues in the application in radio-mobile communication. A given area is partitioned in sub-areas or cells, each of which is served by a radio-base station with a limited power. The radio-base stations are coordinated by a control system and can serve a user only if it is inside their cell. When the user exits from a cell and enters an adjacent cell a free frequency in the domain of the new radio-base station have to be assigned him without any interruption in the communication. The available radio frequencies are assigned to the radio-base stations so that a same frequency can be used more than one time, but limiting the interference due to the use of the same channel. The Frequency Assignment Problem (FAP) can be stated as follows: given a network of transmitters and a set of feasible frequencies, assign frequencies to transmitters so as to maximise a function of the signal/noise ratio in all test points.
FAP can be formulated as the problem of colouring (assigning frequencies) the nodes (transmitters) of an undirected graph so that a function of the edges and of the assigned colours is minimised. A first attempt to formalise FAP as a graph theoretic model is presented in the work by Hale [Ha80], where FAP is formulated as a generalisation of the well-known graph colouring problem.
It is well known [Ha80], that FAP belongs to the class of NP-hard problems. For this reason, several authors concentrated their efforts in developing heuristics to find good feasible solutions. [CaHuSt96, Co93, Ku91, HuSmTh98]. Several relaxations to produce lower bounds have been presented in [Ga86]. The two main variants in the literature are the following:
a) Minimum Span FAP (MS-FAP): With each edge of the interference graph we associate a non-negative integer value representing the minimum distance between the frequencies assigned to the endpoints of the edge, so that the corresponding transmitters do not interfere.
b) Minimum Interference FAP (MI-FAP): With each edge of the interference graph we associate a non-negative real vector, whose i-th component represents a "violation cost" to be paid when the frequencies assigned to the endpoints of the edge differ by exactly i units.
For the first variant (MS-FAP), a number of algorithms to compute lower bounds are based on a reduction of MS-FAP to the travelling salesman problem on the transmitters graph [Ra85, HuSmTh98, AvMaSa01].
For the second variant (MI-FAP) a standard model consists of defining a new symmetric graph (conflict graph), which is obtained from the transmitters graph by substituting the i-th node with a "clique" of size equal to the number of available frequencies (see, [Aa-al98]).
Several exact algorithms, based on polyhedral techniques, make use of the conflict graph. In particular, FAP is formulated as a Vertex Packing problem with side constraints in [Aa-al98, Fi-al96]. An implicit enumeration algorithm has been proposed in [MaSa99]. Moreover, most heuristics are based on the conflict graph.
A recent line of research based on the reduction of MI-FAP to a max k-partitioning problem has been proposed in [EiGrKo00]. The latter problem is solved by semidefinite programming to compute lower bounds for large cellular networks.

b) Digital radio-television network (DAB/DVB): the state of the art.
The planning process of a radio-television network is traditionally decomposed into the "siting" phase and the "frequency assigning" phase.
The "siting problem" can be described as follows: given a set of candidate geographical sites and a finite set of antenna configurations (height, emission diagram, emission power), find a feasible site and an antenna configuration in order to maximise the service quality, w.r.t. number of used frequencies and subject to constraints like budget and safety (electromagnetic pollution).
This problem has been formalised in various papers, see, for instance, [RoSaSm00], [MaSc00]. Various heuristics are proposed, both greedy and local search. The models investigated in [RoSaSm00] are able to certify planned transmitters configuration through the computation of bounds. Integration of the siting and frequency assignment processes appears an extremely complex problem from the optimisation viewpoint. First attempts of study of such an integrated approach are reported in [MaSc00]. The computational results show the computational and theoretical difficulties, but also give some insight about its effectiveness of the integrated approach.

c) Locating and dimensioning of LAN nodes: the state of the art.
In a Local Area Network, made by a direct connection of users to concentrators and of a high speed network connecting the concentrators, a specific problem is to locate and dimension the concentrators while assigning the users to the concentrators and satisfying some requirements on the maximum number of users assigned at a concentrator and on load balancing. Usually this problem is approached through decomposition. For example a first phase is the assignment of users to concentrators, than the concentrators are assigned to the nodes of the network and dimensioned and finally the loads are balanced through reassignment of the users (see. e.g. [RoSo77], [Pi87], [Bo89]). In order to have a better design the network (better distribution of the load, smaller cost) more complex approaches are under consideration which merge some of the phases above. New subproblems have been devised in this study as the Hub Location, the Capacitated Plant Location and the Spanning Forest Covering, see e.g. [DeLaMa96] [DeMa96a], [DeMa96b], [DeMa96c] , [DeMa01].

6. Traffic analysis and routing: the state of the art
The analysis of traffic scenarios in communication networks is an important component in developing adapt models and designing the network. Several problems arise in the study of the modelling and routing of the information:
- analysis of highly aleatory traffic demand where a design based on the maximum traffic will result in a waste of resources, whereas a design based on average values could produce frequent overload of the network capacity;
- routing on adapt paths to balance the load of the network.
The first problem ca be approached with the methods of the Stochastic Optimization [To-al98] or through the simulation of the process [Le-al94], [PaFl95]. Stochastic programming models that can represent the uncertain demand have been propose in [FrLu82], [Lo86], [Ga94], [StToVa97], [FaGa97]. Useful methods for modelling the traffic in telecommunication networks are the queuing systems (with self-similar distributions). These methods allow a careful analysis of the system performances and give useful information for the network synthesis. In particular have been used Markovian models [Lu91], non traditional systems, called systems with retrials, server searching for customers and vacation [Bo-al00], Da-al00], [Bo-al01a]. The "self-similar" process have been shown to be very well tailored for modelling multimedia traffic see e.g. [Le-al94], [PaFl95], [Be-al95].

The second kind of problems is addressed through distributed optimization techniques. For example in the packet switching networks each packet is transmitted from the current node to the less congested node ("hop-by-hop" routing or Open Shortest Path First), The manager of the network can control the congestion and balance the load by dynamically changing the “virtual distance” among the nodes, so that the network adaptively take care of the congestion. Different approaches based on the evaluation of the load by paths rather than by arcs have been proposed, but not yet well implemented: i) methods for the "equalization" of the flows between a pair of concentrators (it results in a multicommodity flow problem with concave objective function) ii) "label based forwarding" methods in which the transmission protocol allow to look at the packet label and to route each pocket separately (Multi Protocol Label Switching) [Che98] [Law01], [Gho01]

Bibliography
[Aa-al98] K. Aardal, A. Hipolito, C.P.M. Van Hoesel, B. Jansen, A branch and bound algorithm for the frequency assignment problem, Tech. Rep., 1998;
[AvMaSa01] A. Avenali, C. Mannino, A. Sassano, Minimizing the Span of d-walks to Compute Optimum Frequency Assignments, to appear in Mathematical Programmino, 2001;
[Ba96] F. Barahona: Network Design Using Cut Inequalities, SIAM J. Optimization 6(3), 823-837, 1996;
[BaMaMi98] Balakrishnan A., Magnanti T.L. and Mirchandani P., Designing hierarchical Survivable networks, Operations-Research. vol.46, 116-36, 1998;
[Be95] R. BEUTLER, Optimization of Digital Single Frequency Networks, Frequenz, 49, 11 - 12, Nov - Dec 1995.
[Be-al 95] J. Beran, R. Sherman, M.S. Taqqu, and W. Willinger, Long-Range Dependence in Variable-Bit-Rate Video Traffic, IEEE Trans. Comm., Vol. 43, No 2/3/4, pp. 1566-1579, 1995;
[Bi-al98] D. Bienstock, S. Chopra, O. Gunluk, C. Tsai: Minimum Cost Capacity Installation for Multicommodity Network Flows, Math. Prog. 81 (1998), 177-199.
[Bo89] Boffey, T.B. (1989). Location problems arising in computer networks. J. Operational Res. Society, 40(4), 347-354.
[Bo-al 00] P.P. Bocharov, C. D’Apice, B. D’Auria, S. Salerno, A queueing system of finite capacity with the server requiring a priority search for customers, Vestnik Rossiyskogo Universiteta Drujbi Nardov, Seria Prikladnaia Mateormatika i Informatika, No 1., 50-61, 2000;
[Bo-al 01a] P.P. Bocharov, C. D’Apice, R. Manzo, N.H. Phong, On a Multiclass arrival retrial MK/GK/1/r Queueing System with Finite Buffer, Proceedings of 16th Belarus Winter Conference in Queueing Theory, Minsk 2001;
[Br93] R. BRUGGER, DAB coverage of interfering single frequency networks, CCETT GT R1/DIG 167, Jun. 1993
[BrGuWo96] B. Brockmuller, O. Gunluk, L. Wolsey: Designing Private Line Networks - Polyhedral Analysis and Computation,Technical Paper Cornell University, 1996;
[CaFr01a] J. Castro, A. Frangioni "A Parallel Implementation of an Interior-Point Algorithm for Multicommodity Network Flows" Lecture Notes in Computer Science vol. 1981, Vector and Parallel Processing - VECPAR 2000, J.M. Palma. J. Dongarra and V. Hernandez eds., Springer-Verlag, p. 301 - 315, 2001
[CaFr01b] J. Castro, A. Frangioni, Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems, INFORMS JOC, to appear, 2001;
[CaHuSt96] D.J. Castelino, S. Hurley, N.M. Stephens, A tabu search algorithm for frequency assignment, Annals of Operations Research, 63:301-319, 1996;
[Che98] Chen S., Nahrstedt K. (1998) An overview of Quality of Service
routing for next-generation high-speed networks: problems and solutions, IEEE Networks Nov-Dec 98, 64-79.
[ChSaMa00] S. Chamberland, B. Sanso', O. Marcotte, Topological design of two level telecommunication networks with modular switches, Operations Research, Vol. 48, no. 5, pp. 745-760, 2000;
[Co93] D. Costa, On the use of some known methods for T-colourings of graphs. Annals of Operations Research, 41:343-358, 1993;
[Da-al00] C. D’Apice, R. Manzo, N.H. Phong, S. Salerno, Retrial queueing system with several input flows and with vacations, Vestnik Rossiyskogo Universiteta Drujbi Nardov, Seria Prikladnaia Mateormatika i Informatika, No 1., 62-73, 2000;
[DeLaMa96] M. Dell'Amico, M. Labbe', F. Maffioli (1996), "Complexity of Spanning Tree Problems with Leaf-Dependant Objectives",Networks 27.
[DeMa96a] M. Dell'Amico, F. Maffioli (1996),"On Some Multiciriteria Arborescence Problems: Complexity and Algorithms", Discr. Appl. Math. 65.
[DeMa96b] M. Dell'Amico, S. Martello (1996), "Open Shop, Satellite Communication and a Theorem by Egervary" Operations Research Letters 18.
[DeMa96c]M. Dell'Amico, S. Martello (1996), "The K-Cardinality Assignment Problem", Discrete Applied Mathematics 76.
[EiGrKo00] A. Eisenblatter, M. Groetchel, A. Koster, Frequency Assignment and Ramifications of Coloring. Konrad-Zuse-Zentrum f"ur Informationstechnik Berlin, ZIB-Report 00-47, 2000;
[FaGa97] Fantauzzi F. and A.A. Gaivoronski, Optimal design of backbone ATM network with dynamic capacity reallocation, International Symposium on Mathematical Programming, Lausanne, 25-29 August 1997.
[Fi-al 96] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur, E. Toto, Frequency Assignment in Mobile Radio Systems using branch-and-cut techniques, to appear, 1996;
[FrGa99] A. Frangioni, G. Gallo, A Bundle Type Dual-Ascent Approach to LinearMulticommodity Min Cost Flow Problems, INFORMS JOC 11(4), p. 370 - 393, 1999;
[FrLu82] Franca P.M. and Luna H.P.L., Solving stochastic transportation-location problems by generealized Benders decomposition, Transportation Science, 1982.
[Ga86] A. Gamst, Some lower bounds for a class of frequency assignment problems. IEEE Transactions on Vehicular Technology, 35:8-14, 1986;
[Ga94] A.A. Gaivoronski, Robust access planning for ATM network in presence of uncertain multiservice demand. In NETWORKS’94 "Planning for a customer-responsive network", September, 1994.
[Gho01] Ghosh D., Sarangan V., Acharya R., (2001) Quality-of-service routing in IP networks, IEEE Transactions on Multimedia, Volume: 3 Issue: 2, June 2001, 200 -208
[Gu99] O. Gunluk, A Branch-and-Cut Algorithm for Capacitated Network Design Problems, Math. Prog. 86, 17-39, 1999;
[GuMaRi00] Gutierrez M., Marianov V. and Rios M., Survivable capacitated network design problem: new formulation and Lagrangian relaxation, Journal of the Operational Research Society, 51, 574-82, 2000;
[GuPiSo99] Gupta R., Pirkut H. and Soni S., Survivable network design: the state of the art, Information-Systems-Frontiers. vol.1, 303-15, 1999;
[Ha80] K. Hale, Frequency assignment: Theory and applications. Proc. IEEE, 68:1497-1514, 1980;
[HuSmTh98] S. Hurley, D.H. Smith, S.U. Thiel, Improving heuristics for the frequency assignment problem, EJOR 107, 76-86, 1998;
[KaAy98] E. Karasan, E. Ayanoglu, Performance of WDM transport networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp. 1008-1023, 1998;
[Ku91] D. Kunz, Channel assignment for cellular radio using neural networks. IEEE Transactions on Vehicular Technology, 40(1):188-193, 1991;
[Law01] Lawrence J. (2001) Designing multiprotocol label switching
networks, IEEE Communications Magazine , Volume: 39 Issue: 7, July 2001, 134 -142
[Le-al 94] W.E. Leland, M.S. Taqqu, W. Willinger, D.V. Wilson, On the Self-Similar Nature of Ethernet Traffic (extended Version), IEEE Trans. Networking, Vol. 2, No. 1, pp.1-15, Febr. 1994;
[Li97] A. LIGETI, Coverage Optimization in Digital Audio Broadcasting Networks, Licentiate thesis, Dept. of Signals, Sensors and Systems, Royal Institute of Tech., 1997 Siting:
[LiZa99] A. LIGETI, ZANDER J., Minimal Cost Coverage Planning for Single Frequency Network, IEEE Transaction on Broadcasting, 1999
[Lo86] Louveaux F.V., Discrete stochastic location models, Annals of Operations Research, 1986.
[Lu91] D.M. Lucantony, New results on the single-server queue with a batch Markovian arrival process. Communications in Statistics- Stochastic Models., Vol. 7, pp. 1-46, 1991;
[Ma98] M.W. Maeda, Management and control of transparent optical networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp. 1081-1096, 1998;
[MaSa99] C.Mannino, A.Sassano, An enumerative algorithm for the frequency assignment problem, to appear in Discrete Applied Mathematics., 1999;
[MaSc00] R. Mathar, M. Schmeink, Optimal Base Station Positioning and Channel Assignment for 3G Mobile Networks by Integer Programming, 2000;
[MiSa98] Y. Miyao, H. Saito, Optimal Design and Evaluation of Survivable WDM Transport Networks, IEEE Journal on Selected Areas in Communications, vol 16 no. 7, pp.1190-1198, 1998;
[Mu96] B. Mukherjee et al., Some principles for designing a wide-area optical network, in Proc. of INFOCOM, vol. 1, pp. 110-119, 1996;
[PaFl95] V. Paxson, S. Floyd, Wide-Area Traffic: The Failure of the Poisson Modeling, IEEE/ACM Trans. Networking, 3(3), pp.226-224, June 1995;
[Pi87] Pirkul, H., (1987). Efficient algorithms for the capacitated concentrator location problem. Computer and Operation Research, 14(3) 197-208.
[Ra85] A.Raychauduri. Intersection assignments, T-colourings and powers of graphs, PhD thesis, Rutgers University, 1985;
[RaSi96] R. Ramaswami, K.N. Sivarajan, Design of logical topologies for wavelength-routed optical networks. IEEE Journal on Selected Areas in Communications /JLT Special Issue on Optical Networks, 1996;
[RoSaSm00] F. Rossi, A. Sassano, S. Smriglio, Models and Algorithms forTerrestrial Digital Broadcasting, Math. of Indust. Syst.,to appear, 2000;
[Roso77] Ross, G.T. and Soland R.M. (1977) Modeling facility location problems as generalized assignement problems. Management Science, 24(3), 345-357.
[StToVa97] L. Stougie, A. Tomasgard and M.H. Van der Vlerk, Some approaches for solving the stochastic service provision problem, Working paper, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7034 Trondheim, Norway, 1997.
[To-al98] A. Tomasgard (HP), J. A. Audestad (HP), S. Dye (HP), L. Stougie (HP), M. H. van der Vlerk (HP) and S. W. Wallace (HP), Modelling aspects of distributed processing in telecommunication networks, Annals of Operations Research, Vol. 82, pp. 161-184, 1998.
[WaDe96] N. Wauters, P. Demeester, Design of the optical-path layer in multiwavelength cross-connected networks, IEEE Journal on Selected Areas in Communications, vol. 14, no. 5 pp. 881-892, 1996;

3.2.a Riferimenti bibliografici

[Aa-al01] K. I . Aardal., C. P. M. v. Hoesel, A. Koster,. C. Mannino, A. Sassano, Models and solution techniques for the frequency assignment problem, Maastricht Univ., 2001
[ArDAGr01] R. Aringhieri, M. Dell'Amico, L. Grasselli. Solution of thw SONET Ring Assignment Problem with Capacity Constraints. Tech,.Rep. 12 DISMI, Univ. Modena e Reggio Emilia, 2001
[Ba-al99] S. Baroni, P. Bayvel, R.J. Gibbens, S. K. Korotky, Analysis and Design of Resilient Multifiber Wavelength-Routed Optical Transport Networks, J. of Lightwave Technology, 17, 1999
[BaMaMi97] A. Balakrishnan, T.L. Magnanti, P. Mirchandani, Network Design, in Annotated Bibliorgaphies in Combinatorial Optimization, Dell'Amico et al. eds., J. Wiley. 1997
[BeKi99] Beckmann, D., Killat, U.. A new strategy for the application of genetic algorithms to the channel-assignment problem. IEEE Trans. on Vehicular Technology, 48, 1261-1269, 1999
[BiGu96] D. Bienstock, O. Gunluk, Capacitated Network Design-Polyhedral Structure, and Computation, INFORMS JOC 8, 243-259, 1996
[BiMu97] D. Bienstock, G. Muratore: Strong Inequalities for Capacitated Survivable Network Design Problems, Math. Prog., to appear 1997.
[Bo-al98], Borndörfer, R., Eisenblätter, A., Grötschel, M., Martin, A.. Frequency assignment in cellular phone networks. Annals of Operations Research, 76, 73-93, 1998
[CaDe01] Caramia, M., Dell'Olmo, P., Solving the Minimum Weighted Coloring Problem, Networks 38, 88-101, 2001
[Co92] Cox, D. Wireless network access for personal communications. IEEE Communication, 96-115, 1992
[Co-al95] S. Cosares, D.N. Deutsch, I. Saniee, O.J. Wasem, SONET Toolkit: A Decision Support System for Designing Robust and Cost-Effective Fiber-Optic Networks, Interfaces 25, 1995
[CoKuOa93] L.A. Cox, W.E. Kuehmer, S.H. Oarrish, Y. Qiu, Optimal Expansion of Fiber-Optic Telecommunication Networks in Metropolitan Areas, Interfaces 23,1993
[CrFrGe98] T.G. Crainic, A. Frangioni, B. Gendron. Multicommodity Capacitated Network Design, in Telecommunications Network Planning, Soriano P., Sanso B. eds, Kluwer, 1-19, 1998.
[CrFrGe01] T.G. Crainic, A. Frangioni, B. Gendron. Bundle-based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems, Discrete Applied Mathematics, 112, 73-99, 2001
[CrHuSt94] W. Crompton, S. Hurley, N.M. Stephens, A parallel genetic algorithm for frequency assignment problems. In Proc. IMACS/IEEE Conf., 81-84, Lille, France, 1994
[CrBe95] M.E. Crovella, A. Bestavros, Explaining World Wide Web Traffic Self-Similarity, TR-95-015, Boston Univ., 1995
[DaSt96] G. Dahl, M. Stoer, A Cutting Plane Algorithm for Multicommodity Survivable Network Design, Tech. Pap., University of Oslo, 1996
[DeLaMa99]M. Dell'Amico, M. Labbé, F. Maffioli, Exact Solution of the SONET Ring Loading Problem, Operations Research Letters, 25, 1999
[DeMaMe01] M. Dell'Amico, F. Maffioli, M. Merani, Static and Dynamic Assignment Policies of OVSF Codes in Wideband CDMA. Tech,.Rep.11 DISMI, Univ. Modena e Reggio Emilia, 2001
[DeMaTr98] M. Dell'Amico, F. Maffioli, M. Trubian, New Bounds for Optimum Traffic Assignment in Satellite Communication, Computers & Operations Research 25, 1998
[Fr00] A. Frangioni. Generalized Bundle Methods, TR 00-18, Dip. Informatica, Univ. Pisa, 2000
[Ga-al 00] M. Galota, C. Glasser, S. Reith, H. Vollmer, A Polynomial-Time Approximation Scheme for Base Station Positioning in UMTS Networks, Manusciprt, Univ. Wuerzburg, 2000
[GaLaSh99] F. Gasmi,J.J. Laffont, W.W. Sharkey: Empirical Evaluation of Regulatory Regimes in Local Telecommunications Markets, Journal of Economics and Management Strategy; 8, 61-93, 1999
[GaTr00] A. Garavaglia, M. Trubian, Planning of protected WDM optical networks, DRCN 2000, Munich, 2000
[Gr99] W.D. Grover, Resource management for fault tolerant path structures in SONET ring networks, Journal of Networks and Systems Management, 7, 1999
[GrBiVe91] Grover, W.D., T.D. Bilodeau, B.D. Venables. Near Optimal Spare Capacity Planning in a Mesh Restorable Network. Proc. of IEEE GLOBECOM’91, 2007-2012, 1991
[GrIrZh98] Grover, W.D., R.R. Irashko, Y. Zheng. Comparative Methods and Issues in Design of Mesh-restorable STM and ATM Networks. in B. Sansò, P. Soriano eds, Telecommunications Network Planning, 169-200. Kluwer, 1998
[GrMoSt95] M. Groetschel, C.L. Monma, M. Stoer, Design of Survivable Networks, in Nework Models, Ball et al. eds, North Holland, 1995
[HaNg90] J.M. Harrison, V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems, 6, 1-32, 1990;
[KaDoGa98] J.K. Hao, R. Dorne, P. Galinier, Tabu search for frequency assignment in mobile radio networks. Journal of Heuristics, 4, 47-62, 1998.
[Ke95] Ketchum, J.W., Routing in cellular mobile radio communication networks. Routing in Communication Networks, M. Steenstrup ed., Prentice-Hall, 1995
[KeGa97] D.M. Kennet, D.J. Gabel: Fully Distributed Cost Pricing, Ramsey Pricing, and Shapley Value Pricing: A Simulated Welfare Analysis for the Telephone Exchange, Review of Industrial Organization, 12, 485-499, 1997
[La-al99] M. Labbé, R. Seguin, P. Soriano, C. Wynants, Network Synthesis with Non-Simultaneous Multicommodity Flow Requirements: Bounds and Heuristics, Tec. Rep. 99/26 SMG/ULB, 1999
[LiSaVi95] Lisser, A., R. Sarkissan, J.P. Vial. Survivability in Transmission Telecommunications Networks. Res. Rep. ORI4491, C.N.E.T., Issy-les-Moulineaux, France, 1995
[Ma-al 00] C. Mannino, F. Rossi, A. Sassano, S. Smriglio, Antenna Siting and Frequency Assignment by Integer Programming, ISMP 2000
[MaNi00] R. Mathar, T. Niessen, Optimum positioning of base station for cellular radio networks, Wireless Networks, 421-428, 2000
[MaVa95] J.K. MacKie-Mason, H. Varian: Pricing the Internet, in B. Kahin, J. Keller, eds. Public access to the internet, MIT Press, 1995, 269-314.
[MoGr99] G.D. Morley, W.D. Grover, Current Approaches in the Design of Ring-Bases Optical Networks, IEEE Canad. Conf., 1999
[MuPaRe99] R.A. Murphey, P.M. Pardalos, M.G.C. Resende, Frequency assignment problems, Handbook of combinatorial optimisation, eds D.-Z. Du, P.M. Pardalos, Kluwer, 1999
[No94] I. Norros, A storage model with self-similar input, Queueing Systems, 16, 387-396, 1994
[Ra96] Rappaport, T. S., Wireless Communications: Principles and Practice. Prentice-Hall, 1996
[SaNiHa90] Sakauchi, H., Y. Nishimura, S. Hasegawa. A self-healing Networks with an Economical Spare-Channel Assignment. Proc. of IEEE GLOBECOM’90, 438-443. 1990
[Sc98] M.G.Scutellà, A strongly polynomial algorithm for the Uniform Balanced Network Flow Problem, Discrete Applied Mathematics 81, 123-131, 1998
[ScMa98] A. Schrader, S. Martin, Vertical market participation, Review of Industrial Organization 13, 321-331, 1998
[SeRe92] M. Sexton, A. Reid, Transmission Networking: SONET and the Synchronous Digital Hierarchy, Artech House, 1992
[ShPeRa96] H. D. SHERALI, C. M. PENDYALA, T.S. RAPPAPORT, Optimal Location for Micro-Cellular Radio Communication System Design, IEEE Journal on selected areas in communications, 1996
[So-al98] Soriano, P., C. Wynants, R. Seguin, M. Labbé, M. Gendreau, B. Fortz Design and Dimensioning of Survivable SDH/SONET Networks, in B. Sansò, P. Soriano eds, Telecommunications Network Planning, 169-200. Kluwer, 1998
[St92] M. Stoer, Design of Survivable Networks, Lecture Notes in Mathematics 1531, Springer-Verlag, 1992
[StDa94] M. Stoer, G. Dahl: A Polyhedral Approach to Multicommodity Survivable Network Design, Num. Math. 68, 149-167, 1994
[SuVaWo98] A. Sutter, F. Vanderbeck, L. Wolsey, Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms, Operations Research 5, 1998
[Wa91] J. Walrand, Communication Networks, Irwin, 1991

3.3 Descrizione della Ricerca

La ricerca che verrà svolta nell'ambito di questa proposta progettuale è tesa a definire modelli ed algoritmi di ottimizzazione e simulazione per problemi di progettazione e gestione di reti di telecomunicazione che utilizzano nuove o future tecnologie o che non sono stati adeguatamente affrontati in precedenza nella letteratura scientifica, causa la loro intrinseca difficoltà o la grande dimensione. La quasi totalità delle attività che compongono i quattro workpackage della ricerca prevedono la realizzazione di software di ottimizzazione e simulazione che implementa gli algoritmi e le metodologie definite. Tra gli obiettivi fondamentali della ricerca vi è infatti quello di realizzare una libreria di software per la progettazione e gestione di reti che verrà messa a disposizione sia della comunità scientifica che delle aziende pubbliche e private, tramite la rete CRIFOR. La libreria si differenzia da analoghe raccolte di progetti di ricerca scientifica in quanto tutto il software verrà testato indipendentemente da terzi e validato su casi reali, standardizzato, fornito di appropriata documentazione e problemi test ed infine reso disponibile tramite internet (vedi l'attività 1 nel workpackage 1 e la sezione infrastrutture).

La ricerca si articola in quattro Workpackage. Il primo è relativo ad azioni generali volte alla raccolta, standardizzazione del software, predisposizione di un sistema di supporto alla progettazione e alla valutazione economica delle reti di trasmissione. I Workpackage WP2-WP4 affrontano ciascuno una specifica area tematica: progettazione delle connessioni (link), localizzazione e dimensionamento delle apparecchiature ai nodi della rete, instradamento e valutazione dei flussi di traffico.

Workpackage 1: "Strumenti di supporto alle decisioni per il progettista ed il gestore delle reti di telecomunicazione".
La prima attività, cui concorrono tutte e sette le UR è relativa alla raccolta, validazione, standardizzazione e diffusione del software prodotto nei vari Workpackage. La parte più rilevante dell’attività è comunque svolta dall’UR di Pisa, cui partecipano anche componenti del nodo centrale cagliaritano della rete CRIFOR. A questa UR è assegnato il compito di organizzare la libreria scientifica di software e renderla disponibile tramite internet. Le altre UR intervengono apportando al software prodotto nelle varie attività di ricerca le modifiche strutturali necessarie a renderlo standardizzato e distribuibile.
La seconda attività riguarda la realizzazione di un "configuratore" di rete. E’ questo uno strumento software che aiuta il progettista di rete fornendogli strumenti di ottimizzazione da applicare in un approccio alla soluzione globale per decomposizione. Il configuratore dovrà essere innanzitutto in grado di rappresentare graficamente un'area geografica e tutte le informazioni rilevanti per la progettazione di una rete di telecomunicazione, quindi metterà a disposizione del progettista una serie di moduli (tools) costituiti dagli algoritmi sviluppati nei WP2-WP4 per fornire valutazioni quantitative e soluzioni di specifiche problematiche.
La terza attività riguarda lo sviluppo di metodologie e analisi economiche che utilizzando strumenti di ottimizzazione per la progettazione di rete (risultato delle altre attività), consentano di valutare il trade-off qualità-capacità-costi e le economie di scala e di gamma nella fornitura dei servizi in diversi problemi di analisi economica e pianificazione aziendale.

Workpackage 2: "Modelli ed algoritmi di ottimizzazione per la progettazione della topologia di rete".
Nella prima attività vengono studiati problemi basilari della progettazione di reti: il problema del Network Loading, ovvero della determinazione della capacità di costo minimo da installare sugli archi della rete che garantiscono l'instradamento simultaneo dei flussi di traffico tra le diverse coppie origine-destinazione, e il più generale problema del MultiCommodity Network Design (MCND). Il problema verrà studiato sia nella versione con flussi "splittable", cioè con flussi di traffico che possono ripartirsi tra più percorsi, sia nella versione con flussi "unsplittable". Si considererà una formulazione di tipo "capacità", ovvero con sole variabili associate agli archi della rete con l'obiettivo di realizzare un algoritmo Branch&Cut. Saranno inoltre studiate nuove tecniche di soluzione per istanze di grande dimensione. Per il problema generale di MCND si realizzeranno approcci risolutivi basati su tecniche di decomposizione, ricerca locale ed algoritmi enumerativi. In particolare saranno sviluppati algoritmi per l'ottimizzazione lagrangiana adatti alle caratteristiche dei problemi MCND (grandi dimensioni, subgradienti sparsi, decomponibilità).
La seconda attività affronta il problema della progettazione di reti protette tramite quattro diverse tecniche: copertura con cicli (SONET ring), copertura con "p-cycle", protezione tramite cammino principale e cammino di backup e allocazione di capacità di riserva. Le prime due tecniche sono tipiche dell’approccio per decomposizione alla progettazione di reti ottiche con tecnologia SONET/SDH, mentre la terza e la quarta sono tecniche generali applicabili a reti magliate. Per tutte queste tecniche l’obiettivo è definire algoritmi euristici in grado di risolvere problemi reali di grande dimensione.
La terza attività affronta invece il caso del Network Design con domande stocastiche. La natura aleatoria della domanda verrà rappresentata tramite la definizione di opportuni modelli di programmazione stocastica. Per la soluzione dei modelli definiti saranno sviluppati metodi innovativi ed efficienti, progettati combinando in maniera opportuna le metodologie classiche della programmazione stocastica e quelle dell'ottimizzazione su reti.

Workpackage 3: "Modelli ed algoritmi di ottimizzazione per la localizzazione e dimensionamento degli apparati di rete".
La prima attività si occupa di tre problemi estremamente rilevanti: (a) la progettazione di reti radiotelevisive digitali (DAB/DVB), ovvero reti di prossima installazione, per cui il problema della localizzazione deve essere risolto contemporaneamente al problema dell’assegnamento di frequenze; (b) il problema di localizzazione di apparati su reti di grandi dimensioni; (c) il problema dell’assegnamento di frequenze e gestione dell’handover nella telefonia cellulare (con l’attuale tecnologia).
La seconda attività realizza strumenti di ottimizzazione per il Service Network Design, ovvero la problematica relativa al dimensionamento delle risorse ai nodi per ottimizzare i differenti servizi offerti, in funzione di una domanda dinamica.
La terza attività si occupa di problemi di dimensionamento e localizzazione dei concentratori nelle reti di accesso locale (LAN). Nelle LAN, i clienti sono collegati a concentratori, che ne accorpano il traffico e lo inoltrano a una rete più veloce ed estesa. Un problema particolarmente rilevante, quello di bilanciare i carichi delle diverse sottoreti, si può formulare come problema di Ottimizzazione Combinatoria e, in particolare, come problema di Localizzazione di Impianti con vincoli di capacità (Capacitated Plant Location).

Workpackage 4: "Modelli ed algoritmi di ottimizzazione e simulazione per l’instradamento e l’analisi del traffico".
La prima attività si occupa del problema di indirizzare il traffico su cammini opportunamente scelti. In particolare si considererà una rete di comunicazione a commutazione di pacchetti e si studieranno criteri di instradamento adatti a ridurre il più possibile la congestione della rete. Verranno considerati due sottoproblemi specifici: (a) la ricerca della coppia di cammini disgiunti di costo minimo rispetto ad una diversa pesatura che tenga conto della diversa importanza dei due: il primo cammino viene utilizzato per la stragrande maggioranza del tempo, il secondo solo in caso di guasto; (b) flusso multicammino con funzione obiettivo concava e lineare a tratti
La seconda attività considera le strategie basate su IP (Internet Protocol). Vi sono due meccanismi di inoltro dei pacchetti: la strategia tradizionale ("datagram forwarding", o protocollo OSPF) e il "label based forwarding" (o protocollo MPLS). Con il metodo tradizionale OSPF, l'operatore del servizio può controllare la congestione della rete e bilanciarne il flusso cambiando dinamicamente le "distanze virtuali" tra i nodi. Questo dà luogo a un problema di ottimizzazione combinatoria inversa per il quale verranno sviluppate euristiche efficienti basate su tecniche di riottimizzazione dei percorsi minimi. Nel protocollo MPLS la scelta dei percorsi può essere fatta indipendentemente per ogni richiesta. Si introducono considerazioni di qualità e la scelta deve tener conto anche delle risorse disponibili lungo il percorso dando quindi luogo a vari problemi di cammini minimi multi-criterio.
La terza attività si occupa di problemi di riconfigurazione di reti multiperiodo. Negli ultimi anni la domanda di traffico sulle reti a fibra ottica SDH sta divenendo sempre più volatile. Questo non riguarda solo l'entità del traffico, ma l'esistenza delle connessioni. A causa del sorgere e dello scadere dei contratti, le connessioni nascono e muoiono con maggiore frequenza. Il conseguente assegnamento frammentario delle domande ai "timeslot" rende inefficiente l'uso della capacità della rete. L'esigenza di un servizio continuo non permette di ottimizzare da capo l'assegnamento e rende la riottimizzazione della rete un compito difficile, benché importante. Ci si propone di produrre algoritmi per riconfigurare dinamicamente l'instradamento e l'uso dei "timeslot" e ridurre la frammentazione.
L’ultima attività considera modelli di simulazione per reti caratterizzate da flussi di traffico autosimili ("self-similar"). Il dimensionamento ottimale di reti di telecomunicazione realizzato con modelli e metodi di ottimizzazione è basato su stime di valori medi della domanda di traffico. I risultati ottenuti pertanto non considerano la dinamicità temporale e la componente stocastica dei flussi di dati. Quindi per validare e raffinare le configurazioni calcolate è necessario integrare le tecniche di programmazione matematica con un’analisi probabilistica della rete. I flussi di dati, visti come processi stocastici, mostrano di avere una struttura speciale della funzione di autocorrelazione. Per questo motivo sono stati introdotti nuovi e più complessi modelli, basati sui processi self-similar, capaci di descrivere questa proprietà e, di conseguenza, predire con maggiore accuratezza i parametri prestazionali dei sistemi oggetto di studio.
L’attività di ricerca sarà centrata sull'estensione ai processi self-similar dei risultati noti per i singoli sistemi a coda. Per la difficoltà della trattazione analitica sarà necessario affiancare agli studi analitici le tecniche di simulazione.

The research work which will be carried out in the context of this project proposal aims at defining optimization and simulation models and algorithms for solving telecommunication network planning and management problems. Such problems, which so far have not been adequately addressed in the scientific literature due to their inherent difficulty or their large size, will be tackled through approaches which make use of innovative technologies. Almost all of the activities, that constitute the four research workpackages, will provide optimization and simulation software to implement the pre-specified algorithms and methodologies.
One of the primary objectives of this research is, indeed, the development of software libraries for network design and management which will be made available through the CRIFOR network to the scientific communities as well as to public and private companies. One feature which differentiates these libraries from the ones developed within other scientific research projects is that the software production will be complemented by testing and validation phases performed by third parties on real world applications, it will be appropriately standardized, documented and supplied with benchmark instances, and finally made accessible through the web (see activity 1 in workpackage 1 and the "infrastructure section").

The research is organized in four Workpackages. The first one deals with generic activities such as software gathering and standardization, set up of an aiding system for transmission network design and economic evaluation. Each of the Workpackage WP2-WP4 treats one of the following specific topics: link design, location and dimensioning of the equipment at the network nodes, routing and estimation of traffic flow.

Workpackage 1: "Decision support tools for the telecommunication network designer and manager"

The first activity, to which all the seven UR take part, concerns the collection, validation, standardization and spreading of the software produced in the other Workpackages. The UR at Pisa will carry out the most relevant portion of this activity, supported by the members of the CRIFOR network node at Cagliari. The Pisa UR has the task of organizing the software scientific library and make it available through the web. The other RUs will bring the proper modifications to the software structure in order to standardize it and make it easy to divulgate.

The second activity focuses on the development of a network "Configuratore". A network "Configuratore" is a software device which aids the network designer by providing him with optimization tools to be employed whenever a problem can be approached through a decomposition method. The first task of the "Configuratore" is to supply graphic representations of geographical areas and relevant information for the telecommunication network design. Then, it will provide the designer with a set of tools, made of the algorithms developed in WP2-WP4, to perform quantitative evaluations and find solutions for specific problems.

The third activity concerns the development of methodologies and economic analysis making use of optimization tools for network planning (which are the results of other activities). Through these tools, the activity aims at evaluating the tradeoff among quality-capacity-costs and the economies of scale and type in the service supply for problems related to economic analysis and business planning.

Workpackage 2 "Optimization models and algorithms for the network topology design"

The first activity is dedicated to the study of basic problems of network design, such as: the Network Loading problem, consisting in determining, at minimum cost, the capacity of the network links in order to guarantee the simultaneous traffic flow routing between each origin-destination pair, and the more general problem of MultiCommodity Network Design (MCND). Two versions of the problem will be considered, dealing respectively with splittable and unsplittable flow. A flow is splittable if it can be routed through different paths. A "capacity" formulation will be treated, where variables are associated only with the network links, and whose structure can be exploited to device a Branch&Cut algorithm. New solution techniques will be also investigated to deal with large scale problems. For the MCND problem, solution approaches based on decomposition, local search and enumerative techniques will be developed. Particular attention will be given to Lagrangean optimization, particularly suitable to handle MCND problem peculiarities (large size, sparse subgradients, decomposability).

The second activity deals with the design of secure networks through four different techniques: cycle covering (SONET ring), p-cycle covering, security through main path and backup path, and allocation of reserve capacity. The first two techniques are largely used in decomposition approaches for optical network design with SONET/SDH technology, while the last two are general techniques applicable to grid networks. The objective of this activity is to define heuristic algorithms for each methodology, so that even very large scale real problems can be solved efficiently.

The third activity tackles the case of Network Design with stochastic demands. Demand randomness will be represented by defining appropriate stochastic programming models. Those problems will then be solved through innovative and efficient techniques, deriving from a convenient combination of classical stochastic programming methodologies and network optimization methodologies.

Workpackage 3 "Optimization models and algorithms for locating and dimensioning network equipment"

The first activity copes with three extremely relevant problems: (a) the design of digital broadcasting networks (DAB/DVB), i.e. networks, which will be shortly set up, where the two problems of location and frequency assignment must be solved simultaneously; (b) the problem of locating machinery on very large size networks; (c) the problem of assigning frequency and managing the handover on wireless telephony (with the current technology).

The second activity aims at producing optimization tools for the Network Design, i.e. for the problem of resource dimensioning at the nodes so as to optimize the service supplied in response to dynamic demands.

The third activity deals with the problems of locating and dimensioning concentrators in local access networks (LAN). In LANs, clients are linked to concentrators whose task is to forward the traffic flow towards faster and broader networks. A particularly relevant problem in this context is the traffic load balancing in different subnetworks. Such a problem can be formulated as a combinatorial optimization problem. More specifically, it can be seen as a facility location problem with capacity constraints.

Workpackage 4 "Optimization and simulation models and algorithms for the traffic routing and analysis"

The first activity treats the problem of routing traffic on opportunely selected paths. In particular, it will consider packet switching networks and study different routing criteria aiming at reducing network congestion as much as possible. Two subproblems will be addressed: (a) the search of pairs of disjoint paths with minimum costs with respect to two different weights, each one corresponding to a different importance degree: the first will be in use most of the time, while the second only when a failure occurs; (b) the multicommodity flow problem with concave and piecewise-linear objective function.

The second activity considers policies based on the IP (Internet Protocol). Two different message delivery policies are currently in use: the most traditional one, known as "datagram forwarding" (or OSPF protocol), and the "label based forwarding" policy (or MPLS protocol). In the OSPF framework, the service agent has direct control on the network congestion and can balance the flow by dynamically changing the "virtual" distances among the nodes. Such a problem can be formulated as an inverse combinatorial optimization problem, for which efficient heuristic techniques, based on shortest path reoptimization methods, will be devised. In the MPLS protocol, the path choice can be made for each request independently. Such a choice must take into account both quality considerations and resource availability along the paths. Those additional issues can be addressed through the study of multi-criteria shortest path problems.

The third activity deals with the "reconfiguration" problem of multi-period networks. In the last few years, the traffic demand on optical fiber networks SDH is becoming more and more volatile, not only with respect to the traffic type, but also as far as the connection existence is concerned. Connections are established and relinquished with a much higher frequency due to contracts stipulation and expiration. The subsequent fragmentary assignment of requests to timeslots prevents an efficient use of the network capacity. The need of providing a continuous service does not allow to optimize the assignment from scratch and increases the difficulty of the important task of reoptimizing the network. One of the objectives is to produce algorithms to dynamically configure the routing and the use of timeslots and decrease the fragmentation.

The last activity considers simulation models for networks with self-similar traffic flows. The optimal telecommunication network dimensioning, obtained through the use of optimization models and methodologies, is based on the estimation of average traffic demands. The results thus achieved do not take into account the dynamic aspects and the stochastic component of data flow. As a consequence, in order to validate and refine the obtained configurations, mathematical programming techniques must be integrated with probabilistic network analysis. The data flows, seen as stochastic processes, show a special structure of the autocorrelation function. For this reason new and more complex models, based on self-similar processes, have been introduced which are able to capture this feature and, therefore, to forecast with a greater accuracy the performance parameters of the systems under examination. The research activity will be focused on the extension of the results obtained for the single queue system to the self-similar processes. To overcome the difficulty of handling those problems analytically, there is a need of integrating analytical studies with simulation techniques.

3.3.1 Tabelle riassuntive dell'articolazione in workpackage (WP)
Tabella sinottica della distribuzione dei mesi/uomo per WP (mesi/uomo)

nº	Responsabile scientifico dell'UR	WP n. 1	WP n. 2	WP n. 3	WP n. 4	TOTALE
1.	PALLOTTINO STEFANO	43	37	33	0	113
2.	DELL'AMICO MAURO	61	58	0	0	119
3.	GRANDINETTI LUCIO	6	76	0	0	82
4.	SASSANO ANTONIO	41	27	27	0	95
5.	TRUBIAN MARCO	6	16	16	58	96
6.	CARAMIA MASSIMILIANO	6	0	64	15	85
7.	SALERNO SAVERIO	6	29	29	62	126
	TOTALE	169	243	169	135	716

Tabella sinottica della distribuzione dei costi complessivi per WP (MLit)

nº	Responsabile scientifico dell'UR	WP n. 1	WP n. 2	WP n. 3	WP n. 4	TOTALE
1.	PALLOTTINO STEFANO	251 (129.63 KEuro)	217 (112.07 KEuro)	193 (99.68 KEuro)	0 (0.00 KEuro)	661 (341.38 KEuro)
2.	DELL'AMICO MAURO	319 (164.75 KEuro)	303 (156.49 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	622 (321.24 KEuro)
3.	GRANDINETTI LUCIO	30 (15.49 KEuro)	386 (199.35 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	416 (214.85 KEuro)
4.	SASSANO ANTONIO	238 (122.92 KEuro)	157 (81.08 KEuro)	157 (81.08 KEuro)	0 (0.00 KEuro)	552 (285.08 KEuro)
5.	TRUBIAN MARCO	34 (17.56 KEuro)	92 (47.51 KEuro)	92 (47.51 KEuro)	333 (171.98 KEuro)	551 (284.57 KEuro)
6.	CARAMIA MASSIMILIANO	35 (18.08 KEuro)	0 (0.00 KEuro)	377 (194.70 KEuro)	88 (45.45 KEuro)	500 (258.23 KEuro)
7.	SALERNO SAVERIO	30 (15.49 KEuro)	146 (75.40 KEuro)	146 (75.40 KEuro)	311 (160.62 KEuro)	633 (326.92 KEuro)
	TOTALE	937 (483.92 KEuro)	1.301 (671.91 KEuro)	965 (498.38 KEuro)	732 (378.05 KEuro)	3.935 (2032.26 KEuro)

3.3.2 Descrizione dettagliata dei WP secondo le attività individuate

Workpackage 1

Referente del Workpackage

Cognome	RINALDI
Nome	GIOVANNI
Qualifica	Dirigente di Ricerca
Ente di appartenenza	Consiglio Nazionale delle Ricerche, I.A.S.I.

Descrizione delle attività

Attività 1

Durata (mesi)	36
Durata (mesi/uomo)	79
Costo totale previsto	446 (230.34 KEuro)

Descrizione

Nel contesto di ampliamento delle attività della rete di ricerca CRIFOR, si intende raccogliere il software sviluppato nell'ambito del progetto da parte delle UR partecipanti ed operare per la sua divulgazione attraverso Internet. L'attività si articola in tre fasi, che si sovrapporranno parzialmente mano mano che le UR procederanno nello sviluppo del software.

Fase 1: verranno definite opportune interfacce e standard per tutti i moduli software da sviluppare, in modo da garantire l'interoperabilità di moduli prodotti da UR diverse per lo stesso problema e facilitare l'uso dei moduli sviluppati anche da parte di UR diverse da quelle originarie. Si realizzerà anche un supporto web per lo scambio e la diffusione dei codici.

Fase 2: il software prodotto verrà raccolto, ne verrà verificata la funzionalità, la robustezza e la corrispondenza agli standard, verrà ampliata ove necessario la documentazione d'uso. Verrà inoltre organizzata e sistematizzata la raccolta di problemi test e di informazioni a loro riguardo (migliore soluzione conosciuta ecc.).

Fase 3: si porranno i presupposti per la prevenzione dell'obsolescenza del software. A tal fine il CRIFOR sottoporrà a continua verifica il materiale prodotto, garantendo l'operatività delle versioni aggiornate del software mano mano che vengono prodotte. Verrà stimolato il continuo aggiornamento del software, che verrà distribuito attraverso le pagine web del CRIFOR. L'uso del software sarà agevolato attraverso la creazione di opportune interfacce grafiche e web.

This activity is part of a larger plan aimed at enhancing CRIFOR's research network activities. By this activity, the software developed within the other activities will be gathered and distributed through the Internet. The activity is divided in three phases, which will partly overlap as the RUs will start developing their software products.

Objective of the first phase is to participate in the process aimed at setting the standards and the interfaces for all the software modules, in order to guarantee compatibility of modules produced by different RUs for a same problem, as well as easy reuse of modules even by RUs different from those of the developers. A web support system for distribution and exchange of the codes will also be produced.

In the second phase, the codes will be gathered and checked for correctness, robustness and compliance to the standards; the documentation will be improved, if necessary. Also, test problems and generators will be systematically gathered and organized, together with information about the instances (best known solution, etc.).

Finally, the third phase is aimed at building the foundations for the prevention of obsolescence of the developed software. CRIFOR will continuously test the modules, in order to guarantee the functionality of the new versions as soon as they are produced. Continuous improvement of the software will therefore be stimulated, and the software will be distributed through CRIFOR's web pages. Also, graphical and web interfaces will be developed in order to make it easier for expert and non-experts to access and use the codes.

Risultati attesi

1) Raccolta di moduli software standardizzati per la risoluzione di problemi di base nella progettazione e gestione delle reti di telecomunicazione.

2) Validazione ed ingegnerizzazione del software di cui in 1.

3) Scrittura di documentazione e preparazione di istanze benchmark per i problemi affrontati dal software prodotto in 1.

4) Realizzazione di un sito web per la distribuzione e diffusione del software prodotto in 1.

1) Collection of standard software tools for solving basic problems arising in the design and management of telecommunication networks and building of a tool’s library.

2) Validation and engineering of the software library

3) Writing of the documentation and definition of benchmark instances for the problems addressed by the tool’s library

4) Design and implementation of a Web site for distributing and spreading the software tools.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	PALLOTTINO STEFANO	43	251 (129.63 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR. Scrittura delle specifiche per la portabilità e standardizzazione del software; raccolta dei moduli prodotti dalle UR; validazione del software; scrittura della documentazione e preparazione benchmark; diffusione del software tramite sito web.
2.	DELL'AMICO MAURO	6	31 (16.01 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
3.	GRANDINETTI LUCIO	6	30 (15.49 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
4.	SASSANO ANTONIO	6	35 (18.08 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
5.	TRUBIAN MARCO	6	34 (17.56 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
6.	CARAMIA MASSIMILIANO	6	35 (18.08 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
7.	SALERNO SAVERIO	6	30 (15.49 KEuro)	Messa a punto del software prodotto nell'ambito delle ricerche descritte in WP2-WP4, secondo le modalità di portabilità e standardizzazione della rete CRIFOR.
		79	446 (230.34 KEuro)

Attività 2

Durata (mesi)	36
Durata (mesi/uomo)	55
Costo totale previsto	288 (148.74 KEuro)

Descrizione

Scopo di questa attività è la realizzazione di uno strumento di supporto alla progettazione delle reti di telecomunicazione, di seguito denominato "configuratore".
Il configuratore viene alimentato innanzitutto con dati geografici che includono:
- densità e tipologia dell'utenza per zone geografiche;
- installazioni presenti (connessioni, concentratori, cross-connector, ecc.);
e con stime parziali sulle richieste di connessioni da parte dei vari utenti.
Utilizzando un opportuno modello, e basandosi sui dati di cui sopra, il configuratore associa ogni utente ed ogni installazione di attrezzature ad un nodo della rete da progettare, quindi determina puntualmente la richieste complessive di connessioni per ogni utente e le richieste di connessioni tra coppie di nodi.
Devono inoltre essere forniti al configuratore i parametri tecnologici del progetto della rete:
- possibilità di potenziamento delle installazioni presenti (es. aumento della capacità trasmissiva su una linea già presente);
- possibilità di installazione di nuove connessioni (posa di fibre, scavi, ecc.);
- possibilità di installazione di attrezzature nei vari nodi;
ed i relativi costi.
Il configuratore mette quindi a disposizione del progettista un insieme di moduli di ottimizzazione realizzati dalle varie UR del progetto e standardizzati come descritto nell'attività 1 di questo workpackage da utilizzarsi per la determinazione della rete "ottimale" tramite risoluzione di sottoproblemi (ad esempio dimensionamento della capacità dei nodi, WP3) e interazione con il progettista.
Più specificatamente il configuratore assiste il progettista nella realizzazione della rete fornendo per ogni fase di progettazione (definizione e dimensionamento delle connessioni, dimensionamento delle installazioni nei nodi, instradamento delle connessioni, ecc.) una serie di opportuni moduli software di ottimizzazione, che si differenziano per tipologia della problematica affrontata (ad esempio domanda deterministica o stocastica) e per tipologia del metodo di ottimizzazione. Quest'ultima scelta è necessaria in quanto metodi di ottimizzazione enumerativi forniscono soluzioni ottime per problemi di limitata dimensione, mentre per dimensioni superiori si devono utilizzare metodi euristici. Il progettista, a seconda della dimensione del sottoproblema che sta affrontando e del tempo che intende dedicare all'elaborazione potrà scegliere tra metodi esatti, ma onerosi come tempo di calcolo, o metodi euristici che forniscono buone soluzioni in tempi contenuti.
Il progettista utilizza quindi il configuratore per risolvere un qualche particolare sottoproblema, sceglie tra le soluzioni proposte, introduce eventuali correzioni e variazioni manuali, quindi passa alla fase successiva che terrà conto delle scelte fatte sino al momento.
Il configuratore sarà dotato di opportune interfacce grafiche per una veloce ed efficace interazione con l'operatore tramite una mappa sensibile della rete in costruzione.

The aim of this activity is the design and the implementation of a decision support tool for the designing of communication networks, called "configuratore".
The "configuratore" must receive as first input data a set of geographical information including:
- density and typology of the users in each zone;
- current equipment (links, hub, cross-connector, etc.);
and partial forecasting on the connection requests of the users.
Using an ad-hoc model the "configuratore" associates each user and equipment to a node of the network to be designed and defines the total connection request of each user and the total traffic between each pair of nodes. Then one has to give as input to the "configuratore" the technological parameters needed for designing the network:
- possible enhancement of the current network (e.g. increase of the capacity of an existing link);
- possible installation of new links (new fiber in an existing tube, new excavation of a line, etc)
- possible enhancement of the equipment at a node, etc.
The optimization algorithms resulting from the work of the research units of this project and collected in a scientific library as described in Activity 1 of this workpackage, are then available to the planner of the network, through the "configuratore". The planner can design the "optimal" network by solving subproblems (e.g. dimensioning of the node capacity, WP3) through the optimization algorithms, evaluating the proposed solution, interactively modifying this solution and then solving other subproblems.
More specifically the "configuratore" support the planner in each phase of the designing (design of the network topology and of the capacities on the links, dimensioning of the node equipment, routing of the transmissions, etc.)
by making available a set of optimization algorithms which differ because of the problem addressed and the optimization method adopted. It is necessary to have different method for the same kind of problem, so that we can use an enumerative method which provides optimal solutions if we want to solve a relatively small subproblem, whereas we have to use an heuristic method when we want to solve a large subproblem.
The "configuratore" will have graphical interfaces for an effective and fast interaction with the planner. In particular the planner will work most of the time through an interactive map representing the network at each designing state.

Risultati attesi

Produzione di un software denominato "configuratore" in grado di assistere il progettista di rete mettendo a disposizione una serie di strumenti di ottimizzazione (prodotti dei WP2-WP4, standardizzati come nell'attività 1 del WP1) che possono guidare le scelte nelle varie fasi della progettazione. Il configuratore interagisce con il progettista tramite una mappa sensibile, ovvero una rete geografica riprodotta a video con possibilità di estrarre informazioni, effettuare modifiche, isolare zone e sottoproblemi con il semplice uso del mouse.

The software tool called "configuratore" which can support the network planner making available at each phase of the planning, through an integrated system, a set of optimization algorithms (workpackages 2-4 and Activity 1 of workpackage 1). The planner interacts with the "configuratore" through an interactive map, representing the network at each designing state, which allows her/him to obtain information on each zone/node/link, select a zone or a subproblem, etc, through the simple use of a mouse.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	DELL'AMICO MAURO	55	288 (148.74 KEuro)	Progettazione e realizzazione del configuratore
		55	288 (148.74 KEuro)

Attività 3

Durata (mesi)	36
Durata (mesi/uomo)	35
Costo totale previsto	203 (104.84 KEuro)

Descrizione

Lo sviluppo di modelli di ottimizzazione per il progetto di rete (vedi WP2-WP4 e Attività 1 di WP1) consente di misurare i trade-off qualità/capacità/costo e le economie di scala e di gamma nella fornitura dei servizi in diversi problemi di analisi economica e pianificazione aziendale.
L'attività si propone quindi di fornire al manager metodi e strumenti per la valutazione dell'efficienza economica delle reti di telecomunicazione. In particolare verranno affrontati i seguenti temi.

A) Analisi dei costi delle reti ed implicazioni sulle politiche pubbliche e la struttura dei mercati

Fase 1
Si propongono, per reti wireless e per reti fisse di trasmissione dati, adattamenti e usi dei modelli di progetto di rete già disponibili o studiati, per effettuare analisi parametriche volte a quantificare le economie di scala e di gamma.

Fase 2
Si usa il modello di dimensionamento della rete per studiare la selezione di prezzi dello spettro socialmente efficienti in reti mobili. Si analizzano, anche per reti di accesso a larga banda, le conseguenze sulle prestazioni del sistema (qualità, prezzi) della scelta della struttura di mercato da parte del regolatore.

Fase 3
L'analisi dell'impatto della qualità del servizio sui costi, per reti mobili e reti integrate nei servizi, è posto alla base della definizione di prezzi coerenti con la disponibilità a pagare di diverse classi di utenti, la prevenzione della congestione e un uso efficiente delle risorse (schemi di yield management e smart market).

B) Analisi del ruolo del progetto di rete nelle strategie delle imprese e nell’organizzazione verticale dei mercati

Gli investimenti in nuove reti avvengono in un contesto dinamico, caratterizzato da incertezza e irreversibilità delle scelte. Si analizzano i problemi di interazione strategica tra operatori derivanti dai vincoli di capacità, dal carattere multiperiodale delle scelte di espansione e da una organizzazione verticale del mercato che prevede operatori di rete e fornitori di servizio, nonché forme di condivisione delle infrastrutture.

Fase 1
Si analizza l’impatto del trade-off costo/flessibilità sulle caratteristiche della rete, evidenziando il ruolo delle scelte di capacità.

Fase 2
Si valuta la possibilità di condividere strati e/o segmenti della rete in diverse strutture verticali dell’offerta ed il relativo impatto su costi e strategie degli operatori. Si analizzano strutture asimmetriche in cui operatori verticalmente integrati competono con fornitori di servizio e strutture simmetriche basate sulla separazione strutturale della proprietà.

Fase 3
Analizzando i costi degli investimenti in capacità e qualità e le strategie di prezzo, si propone una procedura di dimensionamento nel tempo delle reti compatibile con l’evoluzione della domanda in oligopolio. Si determina poi il valore assunto nel tempo dalle opzioni reali di espansione della capacità dei competitori.

The development of suitable optimization models for network planning (WP2-WP4 and Activity 1 of WP1) allows to measure the trade-off between quality, capacity and costs and the economies of scale and scope in service provision, in a variety of problems related to economic analysis and strategic planning.
The aim of this activity is to give the manager methods and tools for evaluating the economical efficiency of a telecommunication network. In particular the activity will address the following themes:

A) Network cost analysis and implications on public policy and market structure

Phase 1
We adapt and apply existing models for network planning to perform parametric analyses aimed at quantifying the economies of scale and scope in wireless networks and fixed networks for data transmission.

Phase 2
We use the network planning model in order to determine socially efficient spectrum prices for mobile networks. We analyse the implications on system performance (quality, final prices) of the regulator’s choice of a given market structure for both wireless and mobile networks.

Phase 3
The analysis of the impact of service quality on costs, both for mobile networks and for service integrated networks, provides the basis for defining pricing strategies that are compatible with the willingness to pay of different classes of users, the prevention of congestion and an efficient use of available resources (yield management schemes, smart markets, etc.).

B). Network planning, firms’ strategies and vertical market structure
Man-months: 15 (4 by University Professors and researchers; 11 by young researchers)

Innovative network investments typically take place in a dynamic context, characterized by uncertainty and choice irreversibility. We analyse strategic interaction among competitors with capacity constraints and multiperiod expansion choices, within a vertical market structure which includes network operators and service providers and allows for network sharing agreements.

Phase 1
Evaluation of the impact of multiperiod coverage choices and of the cost/flexibility trade-off on network characteristics, analysing the role of capacity choices.

Phase 2
Evaluation the possibility of sharing network layers and segments within different vertical structures and the related impact on operators’ costs and strategies. We analyse both asymmetric structures where vertically integrated operators compete with service providers and virtual operators, and symmetric structures based on property separation.

Phase 3
By jointly analysing the costs of capacity investments on the one side, and quality and pricing strategies on the other side, we propose a procedure for selecting the network development pattern over time that is compatible with the evolution of demand in oligopoly. Then, we study the variation of the value of real options related to capacity expansion choices by competing operators.

Risultati attesi

Attività A: "Analisi dei costi delle reti ed implicazioni sulle politiche pubbliche e la struttura dei mercati"

Fase 1: stima di indicatori delle economie dimensionali della rete;
Fase 2: modello di analisi degli effetti dello spectrum pricing sulle scelte progettuali;
Fase 3: modelli strategici di discriminazione dei prezzi.

Attività B: "Analisi del ruolo del progetto di rete nelle strategie delle imprese e nell’organizzazione verticale dei mercati"

Fasi 1 e 2: modelli di interazione oligopolistica basati sulla teoria dei giochi;
Fase 3: modelli di analisi degli investimenti in capacità basati su opzioni reali.

Activity A: Network cost analysis and implications on public policy and market structure

Phase 1: estimation of indicators related to network size economies
Phase 2: model for the analysis of the impact of spectrum pricing policies on network planning strategies
Phase 3: mathematical models of price discrimination strategies

Activity B: Network planning, firms’ strategies and vertical market structure

Phase 1 and 2: game-theoretic models of oligopolistic interaction
Phase 3: mathematical models of capacity investments based on the real options theory

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	SASSANO ANTONIO	35	203 (104.84 KEuro)	Analisi dei costi delle reti ed implicazioni sulle politiche pubbliche e la struttura dei mercati; analisi del ruolo del progetto di rete nelle strategie delle imprese e nell’organizzazione verticale dei mercati
		35	203 (104.84 KEuro)

Workpackage 2

Referente del Workpackage

Cognome	LABBé
Nome	MARTINE
Qualifica	Professeur Ordinaire
Ente di appartenenza	Université Libre de Bruxelles, I.S.R.O.

Descrizione delle attività

Attività 1

Durata (mesi)	36
Durata (mesi/uomo)	93
Costo totale previsto	520 (268.56 KEuro)

Descrizione

In questa attività verranno considerati il problema generale del Multicommodity Network Design (MCND) e più nello specifico il problema del Network Loading.

Dato un grafo orientato ed un insieme di domande di traffico tra coppie di nodi origine-destinazione, il problema di Network Loading consiste nel determinare la capacità di costo minimo da installare sugli archi del grafo che garantiscono l'instradamento simultaneo delle flussi di traffico tra le diverse coppie o/d, detti "multicommodity". Il problema verrà studiato sia nella versione con flussi "splittable", cioè con flussi di traffico che possono ripartirsi tra più percorsi, sia nella versione con flussi "unsplittable", dove il flusso tra ogni coppia origine-destinazione viene instradato su di un unico percorso.

Per la soluzione del problema con flussi "splittable" sono state sinora utilizzate formulazioni "flusso" contenenti sia variabili associate agli archi della rete, che definiscono le capacità, che variabili che definiscono la quantità di flusso su ciascun arco.

Si studierà l'efficacia di una formulazione "capacità", contenente solo variabili associate agli archi. La formulazione "capacità" è descritta da una famiglia di disequazioni denominate Metric Inequalities. Per questa famiglia saranno studiate le proprietà combinatorie per sviluppare più efficaci algoritmi di separazione, con l'obiettivo di realizzare un algoritmo Branch-and-Cut. Saranno inoltre studiate nuove tecniche di soluzione per istanze di grande dimensione.
Per la versione "unsplittable" si studieranno le proprietà poliedrali per definire nuove famiglie di disequazioni valide, investigando la possibilità di definire una formulazione "capacità".

Si procederà quindi alla relizzazione di un algoritmo Branch&Cut per ciascuna delle due versioni (splittable e unsplittable) e di algoritmi approssimanti per la soluzione di istanze di grande dimensione.

Per il problema generale di MCND si realizzeranno approcci risolutivi basati su tecniche di decomposizione, ricerca locale ed algoritmi enumerativi. Innanzitutto saranno sviluppati algoritmi per l'ottimizzazione lagrangiana adatti alle caratteristiche dei problemi MCND (grandi dimensioni, subgradienti sparsi, decomponibilità). Verrà inoltre proposta una piattaforma standardizzata per l'ottimizzazione lagrangiana, che permetta di gestire efficientemente le modifiche corrispondenti all'uso di tali algoritmi in un contesto di ottimizzazione combinatoria (piani di taglio, separazione, ecc.). Sotto questa interfaccia saranno sviluppati e portati diversi solutori efficienti, in modo da poter testare metodi alternativi. Verranno infine proposte ed implementate interfacce standard per risolutori di problemi di tipo multicommodity, in modo da facilitare lo sviluppo, il testing ed il confronto dei diversi approcci implementati nelle fasi successive.

Le tecniche di tipo lagrangiano saranno utilizzate per calcolare valutazioni inferiori accurate e per costruire, mediante euristiche, soluzioni ammissibili. Si utilizzeranno approcci sofisticati di ricerca locale.

Le valutazioni superiori ed inferiori, unitamente a tecniche poliedrali, saranno utilizzate per progettare metodi enumerativi, sequenziali e paralleli; si svilupperanno interfacce che separano la valutazione dei nodi in un albero di Branch&Bound dalla gestione dei nodi candidati, nascondendo così il parallelismo.

La ricerca porterà alla produzione di lavori scientifici e software, secondo gli standard della rete di ricerca CRIFOR.

In this activity we consider the genera Multicommodity Network Design problem (MCND) and more specifically the Network Loading Problem

Given a directed graph and a set of traffic demands between origin-destination pairs, the Network Loading problem consists of determining minimum cost capacities to be assigned to install on the arcs of the graph which guarantee that traffic flows can be simultaneously shipped between origin/destination pairs. We will study both the "splittable" (where flows can split among more paths) and "unsplittable" (where the flow between any origin/destination is assigned to a single path) versions of the problem.

The Network Loading problem with "splittable" flows have been solved by using "flow formulation", containing both variables associated with capacities and variables expressing the amount of flow shipped on the arcs

The research will study "capacity" formulations of Network Loading, containing only variables associated with the capacities to be installed on the arcs of the graph, showing a smaller number of variables. The capacity formulation is described by large family of valid inequalities, known in the literature as Metric Inequalities. We will study combinatorial properties of Metric Inequalities in order to develop new and more effective separation algorithms to be embedded into a Branch-and-Cut algorithm. Moreover will focus on novel techniques for the solution of large-scale instances.

For "unsplittable" Network Loading problems we will study polyhedral properties to investigate the possibility of defining a capacity formulation for this version of the Network Loading problem too.

We will implement Branch-and-Cut algorithms for both the "splittable" and "unsplittable" Network Loading problem.

For the general MCND problem we will define solution methods based on decomposition techniques, local search and enumerative algorithms. In the first phase we will exploit some theoretical results recently obtained in order to develop efficient nondifferentiable optimization algorithms, especially suited for the solution of MCND problems (large-scale, sparse subgradients, decomposability). We will propose a standard platform for Lagrangean optimization, which separates the solution of the Lagrangean problems from the algorithm that solves the dual, but that, at the same time, allows for an efficient handling of the changes required to use these problems within a combinatorial optimization context (cutting plane, separation, etc.). Several efficient solvers will be implemented/ported under this interface, so that alternative algorithms can be easily compared. We will also propose standard interfaces for multicommodity-type problems solvers, in order to facilitate the development, testing and comparison of the alternative approaches developed in the subsequent phases.

The above Lagrangean techniques will be used to compute lower bounds and, through proper heuristics, feasible solutions for MCND. We will exploit the sophisticated local search approaches.

The codes will be developed according to the standards set by CRIFOR's research network.

Risultati attesi

Pubblicazioni scientifiche, algoritmi euristici e metaeuristici, lower bound lagrangiani, algoritmi enumerativi di tipo Branch&Cut.

Technical report, articles on international journals, heuristic and metaheuristic algorithms, Lagrangean lower bounds, enumerative Branch-and-Cut.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	PALLOTTINO STEFANO	37	217 (112.07 KEuro)	Studio di tecniche lagrangiane per il Multicommodity Network Flow e loro utilizzo per lo sviluppo di metaeuristiche e algoritmi enumerativi.
2.	SASSANO ANTONIO	27	157 (81.08 KEuro)	Studio di diseguaglianze valide per il Network Loading, realizzazione di algoritmi di tipo Branch&Cut ed euristiche per problemi di grandi dimensioni.
3.	SALERNO SAVERIO	29	146 (75.40 KEuro)	Studio di diseguaglianze valide per il Network Loading, realizzazione di algoritmi di tipo Branch&Cut ed euristiche per problemi di grandi dimensioni.
		93	520 (268.56 KEuro)

Attività 2

Durata (mesi)	36
Durata (mesi/uomo)	110
Costo totale previsto	578 (298.51 KEuro)

Descrizione

Nella progettazione di reti di telecomunicazione, un importante requisito di qualità è la capacità della rete di far fronte a guasti reinstradando lungo altri percorsi le comunicazioni in atto che utilizzano la connessione o l'apparato guasto. Per poter effettuare questo reinstradamento occorre che la rete sia stata opportunamente progettata. Il problema generale in esame è quindi quello noto come Survivable Network Design. Vi sono differenti tecniche per realizzare reti 'resistenti' ai guasti. Una tecnica è quella di progettare una rete biconnessa, ovvero tale che per ogni coppia origine-destinazione esistano due cammini disgiunti: in caso di guasto su un cammino il traffico viene instradato sul secondo. Il primo problema affrontato nella ricerca è dunque il seguente:

Problema A. Copertura per cicli. Nella progettazione di reti ottiche in tecnologia SONET/SDH un possibile approccio è: (a) progettare una rete biconnessa di costo minimo che collega tutti gli utenti; (b) definire una copertura della rete con cicli, rispettando un insieme di vincoli tecnologici; (c) dimensionare la banda trasmissiva dei link per servire tutto il traffico richiesto. La ricerca partirà da un'analisi dei risultati della letteratura, quindi introdurrà una funzione di valutazione della topologia che tenga conto indirettamente della domanda proponendo nuovi metodi euristici che affrontino contemporaneamente il problema della progettazione della rete e della definizione della capacità delle connessioni.

Problema B. Copertura per "p-cycles". Si estenderà la ricerca relativa al punto precedente valutando l'impatto di usare i "p-cicli" anziché le più classiche sottoreti ad anello allo scopo di minimizzare il costo della capacità e dei dispositivi installati.
Si intendono realizzare modelli di MIP e algoritmi basati su ricerca locale.

Problema C. Progettazione di una rete protetta tramite cammino primario e cammino di backup. Si considererà il problema del dimensionamento a minimo costo di una rete con cammino di protezione per ogni coppia di trasmissioni e con un ulteriore vincolo sul massimo numero di "hop" per ogni cammino.
Si svilupperà un algoritmo di ricerca locale semplice, ma efficiente, quindi lo si estenderà definendo un approccio metaeuristico ed infine verranno studiate metodologie in grado di produrre lower bound stringenti sia per i problemi applicativi sia per il sottoproblema teorico del Minimum Cost Capacity Installation for Multicommodity Network Flows con flussi interi.

Problema D. Reserve Network Dimensioning. Un'altra tecnica per realizzare una rete robusta, è quella di sovradimensionare le capacità rispetto alle condizioni di traffico di progetto, attribuendo agli elementi della rete una "riserva di capacità" che, in caso di guasto, assicuri la possibilità di reindirizzare il traffico minimizzando i costi totali associati alle capacità aggiuntive. Verranno implementati gli algoritmi euristici riportati in letteratura, quindi verranno sviluppati di nuovi modelli e metodi di risoluzione per il problema del reserve network dimensioning su reti STM-ATM nel caso di incrementi di capacità continui e discreti.

Il software realizzato sarà sviluppato secondo standard di portabilità e documentazione definiti in ambito CRIFOR.

In the design of telecommunication networks a key issue for the quality of the service is the ability of the network to recover from an equipment failure by re-routing along other paths the flow using these equipment. In order to make effective this re-routing it is necessary that the network have been designed so that certain topological properties exist. The general problem we address is than the Survivable Network Design. Different techniques have been proposed to design survivable networks. A first technique is to have a biconnected network, that is a network such that for each pair origin/destination two (node/arc) disjoint paths exist: in case of failure on the first path the traffic is re-routed along the second path. The first problem we will consider is than:

Problem A. Covering by cycles. A possible approach to the design of an optical network with SONET/SDH technology is as follows: (a) design a min-cost biconnected network; (b) design a covering by rings of the network, by satisfying a set of technological constraints; (c) define the bandwidth of each link. Our research will start with an analysis of the results from the literature, then we will introduce an objective function indirectly taking into account the traffic demand and we will define new heuristic methods that address at the same time the designing of the network topology and the definition of the bandwidth on the links.

Problem B. Covering by "p-cycles". We will extend the research made for the above problem A evaluating the effectiveness of using "p-cycles" to cover the network, instead of the classic rings. In particular we will concentrate on the possibility of minimizing bandwidth and equipment. We will develop MIP models and we will propose algorithms based on local search.

Problem C. Design of a protected network with primary and backup path. We will address the problem of designing a minimum cost network with backup path for each pair origin-destination and a further constraint on the number of "hops" on each path.
We will develop a simple and fast local search method to solve large instances, than we will extend the approach to a metaheuristic algorithm. Finally we will define strict lower bounds for real life applications.

Problem D. Reserve Network Dimensioning. Another technique to design a robust network is to install a minimum-cost spare capacity over the network so that when a failure occurs it is possible to re-route all the traffic. We will implement software tools for solving the problem using heuristic procedures proposed in literature for specific versions of the problem, than we will develop new models and heuristic techniques to solve the reserve network dimensioning problems for STM-ATM networks with continuous and integer capacity.

The software produced will be implemented accordingly to the CRIFOR specifications and made available through the CRIFOR research network.

Risultati attesi

Articoli scientifici e presentazione a congressi, nonché software di ottimizzazione. In particolare la ricerca fornirà:

Problema A (Copertura per cicli): nuovi algoritmi euristici per problemi di grandi dimensioni.

Problema B (Copertura con "p-cycles"): implementazione con AMPL e CPLEX di modelli MIP; euristiche di ricerca locale.

Problema C (Progettazione di una rete protetta tramite cammino primario e cammino di backup): nuovi algoritmi efficienti di ricerca locale, algoritmi metaeuristici, lower bound.

Problema D (Reserve Network Dimensioning): nuovi modelli e metodi di risoluzione euristici per il problema su reti STM-ATM nel caso di incrementi di capacità continui e discreti.

Technical reports, articles on international journals, optimization software. In particular the deliverable of the research are:

Problem A (covering by cycles) new heuristic algorithms for large scale instances.

Problem B (covering by "p-cycles") AMPL/CPLEX implementation of MIP models; local search algorithms.

Problem C (design of a protected network with primary and backup path) new efficient local search algorithms, metaheuristic algorithms, lower bounds.

Problem D (reserve network dimensioning) new models and heuristic algorithms to solve the reserve network dimensioning problems for STM-ATM networks with continuous and integer capacity.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	DELL'AMICO MAURO	58	303 (156.49 KEuro)	Studio di modelli e sviluppo di algoritmi per i problemi A e C.
2.	GRANDINETTI LUCIO	36	183 (94.51 KEuro)	Studio di modelli e sviluppo di algoritmi per il problema D.
3.	TRUBIAN MARCO	16	92 (47.51 KEuro)	Studio di modelli e sviluppo di algoritmi per il problema B.
		110	578 (298.51 KEuro)

Attività 3

Durata (mesi)	36
Durata (mesi/uomo)	40
Costo totale previsto	203 (104.84 KEuro)

Descrizione

L'attività consiste nello studio di modelli e nella realizzazione di software per la progettazione di reti di telecomunicazione in condizioni di incertezza, ovvero nei casi in cui l'andamento della domanda non sia definito in modo deterministico.

Il problema che si vuole affrontare riguarda la progettazione di una rete di telecomunicazione distinguendo il livello fisico da quello logico. La progettazione della rete fisica consiste nella selezione delle capacità dei collegamenti tra punti di comunicazione (nodi), tenendo in considerazione le diverse possibilità di riconfigurazione. La rete logica si innesta su quella fisica e viene definita mediante un insieme di cammini virtuali che collegano differenti coppie di nodi. Essa può essere riconfigurata, nei limiti imposti dai valori di capacità dei collegamenti fisici, al fine di riflettere i cambiamenti nella domanda. La possibilità di adattare la rete logica alla domanda corrente rappresenta una caratteristica fondamentale che non è presente nelle tradizionali reti di telecomunicazione e che porta ad un miglioramento delle prestazioni del sistema complessivo.
La natura aleatoria della domanda verrà rappresentata tramite la definizione di opportuni modelli di programmazione stocastica. Per la soluzione dei modelli definiti saranno sviluppati metodi innovativi ed efficienti, progettati combinando in maniera opportuna le metodologie classiche della programmazione stocastica e quelle dell'ottimizzazione su reti.

In particolare verranno definiti modelli di ottimizzazione in condizioni di incertezza per la rappresentazione matematica di tipici problemi legati alla progettazione e gestione di reti di telecomunicazione, sviluppati metodi innovativi per tali problemi ed implementati i relativi codici di calcolo. Un'approfondita fase di testing servirà a verificare l’effettiva applicabilità delle metodologie proposte a problemi applicativi.

I codici prodotti saranno corredati di tutti i tools necessari per facilitarne l'uso da parte dell'utente finale e verranno resi disponibili tramite la rete CRIFOR.

This research activity is to design models and methods for solving problems arising in telecommunication networks design, in presence of uncertain demand.

The problem we will address is the design of a telecommunication network, distinguishing between the physical and the logical layer. Design of physical network consists in selection of link capacities between nodes, taking into account reconfiguration capabilities. The logical network is imposed on the top of the physical network and it is defined by means of a set of virtual paths between different nodes. In order to handle changes in demand patterns, the logical network can be reconfigured, within restrictions imposed by capacities of physical links. The possibility to adapt the logical network to actual demand is an important feature which is not considered in traditional telecommunication networks. This aspect can lead to improve network capability.
Stochastic programming models will be developed to represent demand-uncertainty in an efficient way. By combining properly stochastic programming techniques together with network optimization methodologies, innovative and efficient methods will be designed and implemented for the solution of the proposed stochastic programming models.

In particular we will develop stochastic programming models to represent the specific decisional problems arising in telecommunication networks planning under uncertainty, we will develop innovative solution methods for solving the optimization models defined in the first phase and we will implement all the resulting algorithms. Extensive computational experiments will asset the effectiveness of the algorithms on real life instances.

The software produced will be implemented accordingly to the CRIFOR specifications and made available through the CRIFOR network.

Risultati attesi

Modelli di ottimizzazione, pubblicazioni scientifiche, algoritmi di ottimizzazione stocastica su reti.

Optimization methods, articles on international journals, software for stochastic programming on networks.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	GRANDINETTI LUCIO	40	203 (104.84 KEuro)	Sviluppo di modelli matematici e software
		40	203 (104.84 KEuro)

Workpackage 3

Referente del Workpackage

Cognome	SPERANZA
Nome	MARIA GRAZIA
Qualifica	Professore Ordinario
Ente di appartenenza	Università di Brescia, Dip. di Metodi Quantitativi

Descrizione delle attività

Attività 1

Durata (mesi)	36
Durata (mesi/uomo)	97
Costo totale previsto	568 (293.35 KEuro)

Descrizione

Questa attività si occupa di studiare modelli ed algoritmi e realizzare software per problemi di localizzazione e dimensionamento dei nodi delle reti di telecomunicazione, considerando sia la tecnologia esistente che quella in fase di sviluppo.
Gli aspetti di localizzazione nell'ambito delle reti di comunicazione, sebbene estremamente rilevanti, non sono attualmente presentati in letteratura in maniera sistematica: è quindi importante uno studio preliminare che analizzi in modo critico queste problematiche, proponendo una classificazione legata ad aspetti strutturali e proprietà.
Verranno poi affrontati in particolare i seguenti temi.

A) Progettazione di reti di trasmissione radio-televisiva digitale (DAB, DVB).
La progettazione di reti di trasmissione DAB e DVB comporta la scelta dei siti geografici ove localizzare le antenne trasmittenti, e il contemporaneo assegnamento delle potenze di emissione e delle frequenze di trasmissione con l’obiettivo di massimizzare la copertura del territorio. Nella letteratura scientifica e nella pianificazione pratica il problema di “siting” (scelta dei siti + assegnamento di potenze) e il problema di assegnamento di frequenze vengono risolti separatamente; l'attuale scarsità di risorse richiede la definizione di modelli e algoritmi per l'ottimizzazione contemporanea dei siti, delle potenze e delle frequenze.
Un assegnamento di frequenze induce naturalmente una partizione dei trasmettitori. Si intende dunque studiare una rappresentazione del problema di siting + assegnamento come generalizzazione del problema di partizionamento di grafi. La formulazione studiata sarà la base di un algoritmo di tipo Branch&Cut. A causa dell’elevato numero di variabili attese, i rilassamenti verranno risolti col metodo del “simplesso dinamico”. Verranno inoltre studiate e implementate classi di disequazioni valide. Verrà infine identificato un opportuno insieme di problemi test e realizzato un simulatore per la certificazione dei risultati.

B) Dimensionamento di nodi ed archi in reti di grandi dimensioni. Verranno selezionati alcuni problemi LPCN particolarmente significativi e si proporranno algoritmi sofisticati di ricerca locale per la loro risoluzione, basati su una dimensione dell'intorno molto ampia e caratterizzati dall'utilizzo di algoritmi su grafi per la ricerca di buone soluzioni nell'intorno ("Very large neighborhood search algorithms"). Tali algoritmi richiedono un'accurata analisi delle proprietà strutturali dei problemi, ad esempio quelle relative alle particolari caratteristiche delle tecnologie di comunicazione utilizzate, ed un'attenta implementazione. Particolare cura sarà posta al progetto ed implementazione di un package generale, modulare ed efficiente, per lo sviluppo di algoritmi di ricerca locale basati su intorni di dimensione molto ampia, che potrà essere utilizzato anche in altre attività del progetto.

C) Frequency Assignment Problem (FAP). Come noto il problema è una delle applicazioni chiave nell’ingegnerizzazione delle reti radiomobili cellulari. Le frequenze radio che sono complessivamente disponibili vengono ripartite tra le stazioni radiobase limitando le interferenze. Un sistema di controllo gestisce l'assegnazione di frequenza ad un utente e la sua riassegnazione (handover) quando l'utente passa ad una cella vicina.
In questa attività si realizzerà software per la minimizzazione dell’interferenza dato un numero fissato di frequenze, per la minimizzazione delle frequenze necessarie per ottenere un assegnamento senza interferenze, ed infine per la gestione dell'handover.
Poiché tutti questi problemi sono NP-hard, si adotteranno tecniche euristiche basate sui paradigmi della ricerca locale e metaeuristiche, e si utilizzeranno anche approcci legati all'introduzione di un nuovo modo di gestire gli assegnamenti sui nodi della rete tramite priorita'.

Tutto il software prodotto verrà standardizzato e distribuito secondo le modalità della rete CRIFOR.

This activity will study models and algorithms for locating and dimensioning node equipment on telecommunication networks, taking into account both the existing and the incoming technologies.
Despite their importance, location aspects arising in communication networks are not well-studied in the literature; it is therefore important to study and classify these problems according to their structural aspects and properties. We will consider the following arguments.

A) Design of digital broadcasting networks (DAB, DVB) .
The design of digital broadcasting networks involves the selection of the sites where to accommodate antennas and the simultaneous assignment to all antennas of emission power and transmission frequency so as to maximize coverage. In academic production and in practical planning, the antenna siting problem (location + power assignment) and the frequency assignment problem are solved separately; however, the current scarcity of available locations and bandwidth requires the definition of new models and algorithms for the simultaneous solution of the three problems.. A frequency assignment naturally induces a partition of the transmitters set. We intend to study a representation of the problem as graph partitioning problem. This formulation can be used as basis for a branch-and-cut algorithm. Due to the huge number of expected variables, the linear relaxations will be solved by dynamic simplex method. In addition, classes of valid inequalities will be identified and studied. A suitable set of test problems will be identified and a network emulator will be realized.

B) Location and dimensioning of nodes and arcs in large networks. We will select some LPCN which result to be particularly relevant for telecommunication networks and we will develop sophisticated local search methods based on very large neighbourhood local search algorithms, which use graph algorithms to discover improving solutions in the neighbourhood. These algorithms generally require a detailed study and exploitation of the structural properties of the problems, e.g. those relative to the peculiar characteristics of the available communication technologies, and a careful implementation. A general, modular and efficient package for very large neighbourhood local search algorithms will be developed, which will also be available for use in other activities of the project.

C) Frequency assignment problem (FAP). It is well known that this is one of the key issue in the implementation of a radio mobile network. The radio frequencies available have to be partitioned on the radiobase stations, reducing the total interference to a minimum. A control system manage the assignment of the frequencies to the users and the re-assigning of a frequency when the user moves from the domain of a radiobase to a near domain (handover).
In this activity we will implement software for minimizing the interference when the number of available frequencies is fixed, for the minimization of the number of frequencies necessary to have ‘zero’ interference, and finally for managing the handover.
Since all these problems are NP-hard we will adopt heuristic techniques based on the local search and metaheuristic paradigm, and we will use novel approaches related to a new method for managing the assignment on the nodes.

The codes will be developed according to the standards set by CRIFOR's research network.

Risultati attesi

Presentazioni a congressi, articoli scientifici e software di ottimizzazione.

Technical reports, articles on international journals, optimization algorithms.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	PALLOTTINO STEFANO	33	193 (99.68 KEuro)	Studio di problemi di localizzazione su reti di grande dimensione, sviluppo di tecniche metaeuristiche basate sull'utilizzo di "grandi intorni" (problema B)
2.	SASSANO ANTONIO	27	157 (81.08 KEuro)	Studio di modelli e realizzazione di software per la progettazione di reti radiotelevisive digitali (problema A)
3.	CARAMIA MASSIMILIANO	37	218 (112.59 KEuro)	Studio di problemi di allocazione di frequenze e sviluppo di tecniche di soluzione euristiche ed esatte (problema C)
		97	568 (293.35 KEuro)

Attività 2

Durata (mesi)	36
Durata (mesi/uomo)	27
Costo totale previsto	159 (82.12 KEuro)

Descrizione

Questa attività si occupa di strumenti di ottimizzazione per il Service Network Design, ovvero la problematica relativa al dimensionamento delle risorse ai nodi per ottimizzare i differenti servizi offerti, in funzione di una domanda dinamica.

Problema A: Dimensionamento nodi della rete. Al fine di gestire efficientemente la domanda che nasce dai diversi punti della rete in modo dinamico occorre dimensionare opportunamente gli apparati presenti ai nodi. Il problema verrà affrontato con tecniche basate su copertura e colorazione di grafi e gli algoritmi verranno testati usando dati reali.

Problema B: Ottimizzazione dei punti di interconnessione. Con la liberalizzazione del settore delle telecomunicazioni sono entrati sul mercato nuovi operatori ai quali Telecom Italia offre servizi con riferimento al “listino d’interconnessione”. Da ogni punto d’interconnessione prescelto, il nuovo operatore può usufruire di una serie di servizi per i quali è prevista una specifica tariffa a tempo. Si deve quindi ottimizzare la gestione dei punti di interconnessione con relativa attenzione al bilanciamento dei carichi. Gli algoritmi che si intende sviluppare saranno principalmente basati su tecniche di programmazione dinamica e saranno testati con l’ausilio di data reali forniti da Telecom Italia e Cselt.

Il software prodotto verrà reso disponibile nel contesto della rete di ricerca CRIFOR.

In this activity we will develop optimization tools for the Service Network Design, that is the problem of dimensioning the available resources in a node to optimize the quality of the service offered to different users, accordingly to a dynamic demand.

It is known that the telephone network has a structure based on a hierarchy of four levels, denoted as SL, SGU, SGT and CI, respectively. SL stages are line stages which work to pick up user demand; SGU stages are stages of the urban type and have the task of picking up the demand of the users coming from their adjacent SL stages; SGT stages manage the demand from the SGU stages at an inter-district and international level; CI stages manage the international demand. The stages have a proper well defined location. The number of months per person is 30. The task to be developed are:

Problem A. Node dimensioning. We will study the correct sizing of the nodes of the network in order to manage efficiently the dynamic demand arising from the different points of the network, with different characteristic and constraints to be satisfied. We will develop optimization software based on graph covering and graph coloring techniques. The performance of the software produced will be tested on real life instances.
Problem B. Optimization of the interconnection nodes. With the liberalization of the telecommunication sector, new operators are entering in the market, and to the latter Telecom Italia offers services with respect to an "interconnection menu". From each desired interconnection point, the OLO (Other Licensed Operators) can take advantage of a number of services for which there exists a specific payment on a per time base. In this task we will develop optimization software for the management of the interconnection points with related attention to the load balancing. We will test the algorithms we produce with the help of real data and the cooperation of Telecom Italia and Cselt.

The software produced will be implemented accordingly to the CRIFOR specifications and made available through the CRIFOR research network.

Risultati attesi

Presentazioni a congressi, articoli scientifici e software di ottimizzazione e simulazione per entrambi i problemi proposti.

Technical reports, articles on international journals, optimization and simulation software for both problems.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	CARAMIA MASSIMILIANO	27	159 (82.12 KEuro)	Studio di modelli di problemi di Service Network Design e sviluppo di software per il dimensionamento degli apparati.
		27	159 (82.12 KEuro)

Attività 3

Durata (mesi)	36
Durata (mesi/uomo)	45
Costo totale previsto	238 (122.92 KEuro)

Descrizione

L'attività si occupa di problemi di dimensionamento e localizzazione dei concentratori nelle LAN.
Nelle reti di accesso locale, i clienti sono collegati a concentratori, che ne accorpano il traffico e lo inoltrano a una rete più veloce ed estesa. Più specificatamente una rete di telefonia fissa ha una struttura su quattro livelli di gerarchia: lo stadio di linea (SL) con funzioni di raccolta di domanda dell’utenza; lo stadio del gruppo urbano (SGU) che svolge funzioni di raccolta della domanda del traffico proveniente dagli SL ad essi collegati; lo stadio che gestisce il traffico dagli SGU a livello interdistrettuale e infine lo stadio per la gestione del traffico internazionale. Gli stadi hanno un loro precisa localizzazione sul territorio.
Il progetto delle reti che fanno capo ai vari stadi richiede di posizionare i concentratori, sceglierne l'equipaggiamento e assegnare loro i clienti in modo da soddisfare nel modo più efficiente le domande. Particolarmente rilevante è il problema di bilanciare i carichi delle diverse sottoreti per ridurre la probabilità di guasti e i danni conseguenti.

Tali problemi posso essere formulati come problemi di Ottimizzazione Combinatoria e, in particolare, come problemi di Localizzazione di Impianti con vincoli di capacità (Capacitated Plant Location).

Verranno studiati sia approcci euristici che approcci esatti. Gli approcci esatti saranno di due tipi: Branch&Cut&Price e Column Generation. Per definire un efficace algoritmo basato sul primo approccio si studieranno in particolare nuove famiglie di disequazioni valide specifiche per i problemi di telecomunicazione. Il secondo approccio fa riferimento a modelli di set-partitioning e richiede particolare attenzione allo sviluppo del problema di pricing delle colonne.

The activity will consider the location and sizing of concentrator devices in Local Area Networks (LAN). In a LAN, customers are linked to concentrator devices, which pack up their traffic and forward it to a faster large-area network. More specifically a telephone network has a structure based on a hierarchy of four levels: the line stage (SL) which work to pick up user demand; the stage of the urban type (SGU) which has the task of picking up the demand of the users coming from their adjacent SL stages; the stage which manage the demand from the SGU stages at an inter-district and international level. The stages have a proper well defined location on the territory.
The design of these network stages requires to locate concentrators, to choose their equipment and to assign customers to them so as to satisfy the given or estimated demands in the most efficient way. One of the most relevant issue is to balance the load in the subnetworks so that the failure probability and the associate damage is minimized.

These problems have a natural formulation in Combinatorial Optimization leading to the Capacitated Plant Location problems.

We will study both heuristic and exact approaches. We will develop two kind of exact approach: Branch&Cut&Price and Column Generation. The first method requires to study new valid inequalities taking into account the specific structure of the telecommunication networks, The second approach uses a set-partitioning model and requires a careful implementation of the column pricing.

All the software we produce will be implemented accordingly to the CRIFOR specifications and made available through the CRIFOR research network.

Risultati attesi

Articoli scientifici e presentazioni a congressi.

Software di ottimizzazione comprendente:
- algoritmi di tipo metaeuristico
- algoritmo esatto di tipo Branch&Cut&Price
- algoritmo esatto di tipo Column Generation

Technical reports, articles on scientific international journals. Optimization software including:

- metaheuristic algorithms
- exact Branch&Cut&Price algorithm
- exact Column Generation algorithm

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	TRUBIAN MARCO	16	92 (47.51 KEuro)	Sviluppo di algoritmi euristici e di algoritmi esatti basati su Column Generation
2.	SALERNO SAVERIO	29	146 (75.40 KEuro)	Sviluppo di algoritmi euristici e di algoritmi esatti basati su Branch&Cut&Price e su Column Generation
		45	238 (122.92 KEuro)

Workpackage 4

Referente del Workpackage

Cognome	BOCHAROV
Nome	PAVEL
Qualifica	Full Professor
Ente di appartenenza	Peoples' Friendship University of Russia

Descrizione delle attività

Attività 1

Durata (mesi)	36
Durata (mesi/uomo)	28
Costo totale previsto	163 (84.18 KEuro)

Descrizione

Una delle problematiche che sorge nella gestione di una rete di comunicazione esistente è quella di indirizzare il traffico su cammini opportunamente scelti. In una rete di comunicazione a commutazione di pacchetti, per ridurre fenomeni di congestione, a intervalli regolari di tempo ciascun pacchetto viene smistato dal nodo in cui esso si trova attualmente al meno congestionato tra i nodi adiacenti. In tal modo la rete risponde adattivamente e localmente alla congestione. Tuttavia, in un'ottica più strategica e di sistema, è opportuno avere un'idea su come convenga distribuire la domanda tra due concentratori qualunque lungo cammini che collegano tale coppia di concentratori in modo tale da ridurre il più possibile la congestione della rete. A tal fine, si può seguire la strategia di cercare di "egualizzare" il più possibile i flussi lungo tali cammini. Si considereranno i seguenti problemi.

Problema A. Ricerca della coppia di cammini di costo minimo, che siano disgiunti rispetto ai vertici (o agli archi) e colleghino due vertici assegnati su un grafo pesato dato. I costi dei due cammini si calcolano rispetto ad una diversa pesatura che tiene conto della diversa importanza dei due: il primo cammino viene utilizzato per la stragrande maggioranza del tempo, il secondo solo in caso di guasto.

Problema B. Flusso multicammino con funzione obiettivo concava e lineare a tratti (da massimizzare). Per tale problema si svilupperanno innanzitutto algoritmi primali e duali, e relativo software, basati sulla ricerca di cammini su cui modificare i flussi. Verrà quindi sviluppato un algoritmo di Column Generation.

Tutto il software prodotto sarà reso disponibile nel contesto della rete di ricerca CRIFOR.

An important problem in the management of a communication network is the definition of the path that a transmission has to use. To reduce congestion in packet-switching telecommunication networks, the system often uses a "local" adaptive response. This consists in the redistribution of some packets, each being moved from its current node of residence to the less congested of its adjacent nodes. From a more strategic point of view, it is also necessary to determine system-wide strategies that optimally allocate demand between pairs of concentrators among the paths linking the corresponding concentrators to minimize congestion on the network. A promising strategy is to distribute as equally as possible the flows on these paths. We will study the following problems.

Problem A. Finding the minimum cost pair of vertex (or edge) disjoint paths connecting two assigned vertices on a given weighted graph, where the cost of a path is computed using an edge weighting different from that used on the other path. The different weighting take into account the fact that the first path is used the most of the time and the second one only when a failure occurs.

Problem B. Multicommodity flow with a concave objective function (to be maximized). We will develop primal and dual algorithms (and related software) based on path generation and/or many-to-one and one-to-many flow deviations. Next we will propose column generation method.

All the software will be made available in the context of CRIFOR research network.

Risultati attesi

Modelli matematici ed algoritmi, pubblicazione di articoli scientifici. Inoltre produzione di software:

Problema A (coppia di cammini disgiunti di costo minimo con doppia pesatura): algoritmi euristici

Problema B (flusso multicammino con funzione obiettivo concava e lineare a tratti): algoritmi euristici ed esatti di tipo Column Generation.

Mathematical models and optimization algorithms, articles on international journals. In particular we will implement:

Problem A (finding the minimum cost pair of vertex (or edge) disjoint paths with double weighting) heuristic algorithms.

Problem B (multicommodity flow with a concave objective function) heuristic algorithms, exact Column Generation algorithm.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	TRUBIAN MARCO	13	75 (38.73 KEuro)	Sviluppo di modelli ed algoritmi per individuare coppie di cammini disgiunti con doppia pesatura (problema A)
2.	CARAMIA MASSIMILIANO	15	88 (45.45 KEuro)	Sviluppo di modelli ed algoritmi per flussi multicammino con funzioni concave lineari a tratti (problema B)
		28	163 (84.18 KEuro)

Attività 2

Durata (mesi)	36
Durata (mesi/uomo)	25
Costo totale previsto	143 (73.85 KEuro)

Descrizione

Nelle reti basate sull'IP (Internet Protocol), la strategia di instradamento dei pacchetti IP dipende dal meccanismo di inoltro: quello tradizionale ("datagram forwarding") o il "label based forwarding".

Problema A. Protocollo Open Shortest Path First (OPSF). Con lo schema tradizionale OPSF, i pacchetti vengono instradati "hop-by-hop" lungo il percorso minimo fino a destinazione. L'operatore del servizio può controllare la congestione della rete e bilanciarne il flusso cambiando dinamicamente le "distanze virtuali" tra i nodi. Quindi, un importante problema di Ottimizzazione Combinatoria consiste nel determinare le distanze virtuali appropriate per bilanciare il traffico e/o minimizzare la congestione. Per affrontare questo problema di ottimizzazione combinatoria inversa svilupperemo euristiche efficienti basate su tecniche di riottimizzazione dei percorsi minimi capaci di trattare sottoreti reali.

Problema B. Protocollo Multi Protocol Label Switching. Nel protocollo MPLS la scelta dei percorsi può essere fatta indipendentemente per ogni richiesta. Si introducono considerazioni di qualità e la scelta deve tener conto anche delle risorse disponibili lungo il percorso (ad es., l'ampiezza di banda, lo spazio di "buffer"). Investigheremo alcuni di questi problemi di percorso minimo a molti criteri, considerando, ad esempio, l'ampiezza di banda e il ritardo, con particolare enfasi sul caso distribuito e con informazione condivisa ridotta.

In IP (Internet Protocol) based networks, the routing strategy of IP packets depends on the forwarding mechanism: traditional "datagram forwarding" or "label based forwarding".

Problem A. Open Shortest Path First (OSPF) protocol. With the traditional OSPF scheme, packets are routed hop-by-hop along the shortest paths to the destination. The service operator can control the congestion and balance the flow in the network by changing dynamically the "virtual lengths" between the nodes.
Therefore an important combinatorial optimization problem consists in determining the appropriate virtual lengths so as to balance the traffic and/or minimize congestion. To tackle this inverse combinatorial optimization problems we will develop efficient heuristics based on shortest path reoptimization techniques able to deal with real life subnetwork instances.

Problem B. Multi Protocol Label Switching (MPLS). With the MPLS protocol, routing decisions (i.e., path selection) are taken independently for each packet flow entering the network. Quality considerations are introduced and path selection must also take into account the network resources available along the path (e.g., bandwidth, buffer space). We will investigate some of these multicriteria shortest path problems, considering, for example, bandwidth and delay, with a particular emphasis on the distributed setting and on the case of reduced shared information.

Risultati attesi

Pubblicazioni scientifiche e comunicazioni a congressi.

Problema A (OSPF): raccolta di problemi test, prototipo di software di ottimizzazione.

Problema B (MPSL): simulatore del protocollo MPLS.

Technical reports, articles on international journals.

Problem A. Open Shortest Path First protocol: collection of test instances, prototype optimization software.

Problem B. Multi Protocol Label Switching. Network emulator.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	TRUBIAN MARCO	25	143 (73.85 KEuro)	Modelli di instradamento con protocolli OSPF e MPLS, simulatori.
		25	143 (73.85 KEuro)

Attività 3

Durata (mesi)	36
Durata (mesi/uomo)	20
Costo totale previsto	115 (59.39 KEuro)

Descrizione

L'attività si occuperà di problemi di riconfigurazione di reti multiperiodo.

Negli ultimi anni la domanda di traffico sulle reti a fibra ottica SDH sta divenendo sempre più volatile. Questo non riguarda solo l'entità del traffico, ma l'esistenza delle connessioni. A causa del sorgere e dello scadere dei contratti, le connessioni nascono e muoiono con maggiore frequenza. Il conseguente assegnamento frammentario delle domande ai "timeslot" rende inefficiente l'uso della capacità della rete. L'esigenza di un servizio continuo non permette di ottimizzare da capo l'assegnamento e rende la riottimizzazione della rete un compito difficile, benché importante.

Verranno proposti algoritmi per riconfigurare dinamicamente l'instradamento e l'uso dei "timeslot" e ridurre la frammentazione sfruttando la capacità residua, cioè quella non impiegata e quella dedicata ai cammini di protezione. Il sottoproblema di instradare il traffico rispettando requisiti di protezione può essere modellizzato come ricerca di un flusso "multicommodity" di costo minimo. In questo ambito verranno presi in considerazione i modelli ed il software sviluppati, per i casi "splittable" o "unsplittable", anche da altre unità di ricerca.

The activity will address multiperiod network reconfiguration problems.

In recent years, traffic demands across fiber optic SDH networks are increasingly fluctuating. This does not simply concern the entity of the traffic, but the existence of a traffic connection. Due to the issue and the expiry of leasing contracts, connections arise and disappear over time more frequently. The consequent fragmented assignment of demands to timeslots results into an inefficient use of network capacity. The need for a continuous service does not allow optimization of the assignment from scratch and makes the reoptimization of the network a difficult, though important, task.

We will propose algorithms to dynamically reconfigure the routing and the assignment of demands to timeslots, in order to reduce fragmentation, through the use of spare capacity (i.e., both currently unused capacity and existing protection paths). The subproblem of routing traffic while meeting protection criteria can be modelled as minimum cost multicommodity flows. In this context the models and software developed for the bifurcated or non bifurcated cases will be considered.

Risultati attesi

Pubblicazioni scientifiche, modello del problema, euristiche di ricerca locale.

Technical reports, articles on international journals, local search algorithms.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	TRUBIAN MARCO	20	115 (59.39 KEuro)	Studio di modelli e sviluppo di algoritmi prototipali.
		20	115 (59.39 KEuro)

Attività 4

Durata (mesi)	36
Durata (mesi/uomo)	62
Costo totale previsto	311 (160.62 KEuro)

Descrizione

L'attività considererà modelli di simulazione per reti caratterizzate da flussi di traffico "self-similar".

Il dimensionamento ottimale di reti di telecomunicazione realizzato con modelli e metodi di Ottimizzazione è basato su stime di valori medi della domanda di traffico. I risultati ottenuti pertanto non considerano la dinamicità temporale e la componente stocastica dei flussi di dati. Quindi per validare e raffinare le configurazioni calcolate è necessario integrare le tecniche di programmazione matematica con un’analisi probabilistica della rete.
Uno strumento matematico con il quale è possibile effettuare un’analisi stocastica sebbene stazionaria delle reti è la Teoria delle Code. Recenti ricerche hanno tuttavia rivelato che modelli basati sulla Teoria delle Code risultano di scarsa utilità per le reti di dati poiché i flussi di dati, visti come processi stocastici, mostrano di avere una struttura speciale della funzione di autocorrelazione. Per questo motivo sono stati introdotti nuovi e più complessi modelli, basati sui processi self-similar, capaci di descrivere questa proprietà e, di conseguenza, predire con maggiore accuratezza i parametri prestazionali dei sistemi oggetto di studio.
L’attività di ricerca sarà centrata sulla possibile estensione ai processi self-similar dei risultati noti per i singoli sistemi a coda. Per la difficoltà della trattazione analitica sarà necessario affiancare agli studi analitici le tecniche di simulazione.

Verrà effettuato uno studio funzionale alla individuazione dell’insieme dei parametri sufficienti a caratterizzare i flussi di traffico self-similar e i relativi modelli, quindi verranno studiate tecniche innovative per il trattamento delle distribuzioni di tipo long-tailed, che rivestono un ruolo centrale in presenza di processi autosimilari. Verranno quindi studiate di tecniche basate sulla simulazione del flusso aggregato di un elevato numero di sorgenti long-tailed per mezzo di un rumore gaussiano frazionale ed un approccio di tipo distribuito standard quale HLA (High Level Architecture – standard IEEE per la simulazione distribuita) e realizzato un software per la Simulazione del traffico di reti di telecomunicazioni.

We consider analytical and simulation models for networks with self-similar traffic.

The optimal design of the telecommunication network obtained applying optimization models and methods is based on average value estimates of traffic demand. The achieved results do not take into account the temporal dynamism and the stochastic component of the data flows. In order to validate and improve the computed configuration it is therefore necessary to complement the techniques of mathematical programming with a probabilistic analysis of the network.
A mathematical tool that can be used in a stochastic analysis (although a stationary one) is the Queuing Theory. However, recent studies have revealed that these models are of little use if applied to the field of data networks, because data flows, seen as stochastic processes, demonstrate a special structure of the autocorrelation function. For this reason, new and more complex models have been introduced, based on self-similar processes, able to describe this property and then to predict the performance parameters of the studied systems with greater accuracy.
The research activity will focus on how to extend available results for single queuing systems to self-similar processes. Because of the known difficulty in analytic treatment, simulative techniques will also be used.

In order to define the simulation models a study will be carried out to identify the set of relevant parameters sufficient to characterize self-similar flows and their relative models. Existing simulation techniques will then be analyzed, together with the investigation of new innovative ones, especially for the treatment of long-tailed distributions. Alternative techniques will be investigated, based on the simulation of the aggregation of a great number of long-tailed sources by Fractional Gaussian Noise, together with the possibility of using a distributive approach compliant with HLA (High Level Architecture – IEEE standard for the distributed simulation) standard.

The software produced will be implemented accordingly to the CRIFOR specifications and made available through the CRIFOR research network.

Risultati attesi

Articoli scientifici, presentazione a convegni, software per la simulazione del traffico di reti di telecomunicazioni.

Technical reports, articles on international journals, software for the simulation of the self-similar traffic in telecommunication networks.

Unità di ricerca impegnate e relativi compiti

nº	Responsabile scientifico	Mesi/uomo	Costo (ML)	Note
1.	SALERNO SAVERIO	62	311 (160.62 KEuro)	Studio e sviluppo di modelli di traffico self-similar e del relativo simulatore.
		62	311 (160.62 KEuro)

3.4 Elementi per la valutazione globale dell'impatto dei risultati conseguiti nel contesto scientifico nazionale ed internazionale

I risultati ottenuti nell’ambito delle attività descritte nei quattro WPs, sia quelli in itinere che quelli definitivi, saranno pubblicati in appositi Rapporti Tecnici e Rapporti di Ricerca, quali strumenti propedeutici alla produzione di articoli scientifici e comunicazioni a convegni.
Analogamente, il software verrà sviluppato inizialmente come software prototipale, per permetterne una prima diffusione; esso verrà quindi successivamente sviluppato, dopo la fase di validazione, secondo i criteri di standardizzazione previsti in ambito CRIFOR.

Un primo elemento oggettivo di misura del raggiungimento degli obiettivi della ricerca è dunque la raccolta delle pubblicazioni scientifiche relative agli studi effettuati nell’ambito del progetto e la relativa libreria di software standardizzato resa disponibile tramite la rete di ricerca CRIFOR.

La valutazione dei risultati, e del loro impatto nel contesto scientifico nazionale ed internazionale, potrà inoltre essere effettuata agevolmente a più livelli:

- Livello della produzione scientifica
I risultati scientifici conseguiti saranno divulgati, come è tradizione dei gruppi di ricerca partecipanti alle UR, mediante comunicazioni a convegni e pubblicazioni su riviste a diffusione internazionale, per un immediato riscontro della validità delle ricerche intraprese.

- Livello di qualità delle metodologie di ottimizzazione e simulazione
Come usuale, il software prodotto verrà confrontato con il software prodotto da altri gruppi di ricerca e/o con il software disponibile commercialmente, utilizzando problemi "benchmark" per la validazione dell'efficienza dei codici. Inoltre, il software verrà messo a disposizione dei gruppi di ricerca che lo richiedono.

- Livello di qualità del software
La raccolta del software prodotto, in modo coordinato ed organizzato, permetterà di mettere a disposizione del sistema della ricerca, nazionale ed internazionale, e del mondo delle imprese di produzione e gestione ,un complesso insieme di strumenti di facile accesso. Tale obiettivo verrà raggiunto sia grazie agli strumenti di standardizzazione e documentazione adottati, sia grazie al corredo di piattaforme di interfaccia. Inoltre, sarà cruciale la certificazione di funzionalità del software fornita da ricercatori diversi dai produttori del software stesso.

- Livello di controllo della rete di ricerca
Sarà possibile valutare il potenziamento della rete di ricerca CRIFOR in ogni momento durante il triennio di ricerca. La valutazione avverrà anche oltre il termine del triennio: andrà infatti verificato che la rete CRIFOR sia in grado di autoalimentarsi, mediante contratti di ricerca, grazie ad imprese private e a capitale pubblico, e grazie ad istituzioni nazionali e europee di supporto alla ricerca.

A garanzia dell’efficacia dell’intervento e dell’impatto che questo avrà nel contesto nazionale ed internazionale vi è la disponibilità formalmente espressa da aziende e centri di ricerca nelle telecomunicazioni (Alcatel, CSELT, Telecom, Telecom Italia LAB e Tiscali) a eseguire un'analisi critica dei metodi e delle soluzioni proposte, sulla base di casi reali.

Infine, per fornire un ulteriore strumento oggettivo di valutazione dei risultati nel contesto internazionale, è intenzione della rete di ricerca CRIFOR:
i) organizzare un convegno internazionale in Italia a conclusione del triennio di ricerca;
ii) organizzare la stesura di uno "Special Issue" di una delle più importanti riviste nel campo dell'Ottimizzazione e delle sue applicazioni, dedicata al progetto e gestione di reti di comunicazione, che raccolga i risultati scaturiti dalla ricerca e che sia corredata dal relativo software.

The results obtained in the activities which have been described within the 4 WPs, both the ones in development and the final ones, will be published in appropriate Technical Reports and Research Reports, as a first step toward the production of scientific papers and the communication to scientific meetings. Similarly, initially the software will be developed in a prototype form, in order to allow a first dissemination; then, after its validation, it will be developed according to the standards set by CRIFOR.

A first concrete element to evaluate the achievement of the research objectives is therefore the collection of scientific publications concerning the studies performed within the project, and the related library of standard software made it available via the research network CRIFOR.

The evaluation of the results, as well as their impact in the scientific national and international context, will be done at different levels:

Scientific production level
The scientific results gained, as traditionally done by the research groups who join the UR, will be divulgated through conference proceedings and publications in international journals, in order to immediately reveal the validity of the research done.

Optimization and simulation methodologies quality level
As usual, the software developed will be tested against the software realized by other research groups and/or against commercial packages; to this end benchmark problems will be used to validate the efficiency of the codes. Moreover, the software will be made available to all the research groups which ask for it.

Software quality level
The software collection, which will be performed in a coordinate and organized way, will allow to divulgate a complex, easy to access, set of tools in the research community, both national and international, as well as in production and management companies. Such an aim will be pursued both by means of the adopted standardization and documentation tools, and also via the equipment of interface platforms. Furthermore, the certification of the software functionalities, provided by researchers other than those who developed the software itself, will be a crucial element of evaluation.

Research network control level
It will be possible to evaluate the enhancement of the research network CRIFOR at any moment during the three-year research. The evaluation phase will take place also after the end of the three-year research: it will be verified that the CRIFOR network is able to finance itself, through research contracts, through public and private companies, and finally through national and European foundations for the research support.

As a way to guarantee the efficacy of the project actions and of their impact in the national and international context there is the availability, formally stated by companies and research centers operating in telecommunications (Alcatel, CSELT, Telecom, Telecom Italia LAB and Tiscali) to perform a critical analysis of the proposed methods and solutions, using real cases.

Finally, in order to provide a further concrete instrument of evaluation of the results in the international context, the CRIFOR research network intends:

i) to organize an international conference in Italy as a conclusion of the three-year research.;
ii) to organize a "Special Issue" of a major journal in the field of Optimization and its applications, which will be devoted to the design and management of communication networks, and which will collect the results of the research, by enclosing the produced software.

Parte IV "Dati riassuntivi"

4.1 Riassunto Spese delle Unità di Ricerca

nº	Responsabile Scientifico (codice)	Spesa A (MLit)	Spesa B (MLit)	Spesa C (MLit)	Spesa D (MLit)	Spesa E (MLit)	Spesa F (MLit)	Spesa G (MLit)	TOTALE
1.	PALLOTTINO STEFANO	226 (116.72 KEuro)	225 (116.20 KEuro)	150 (77.47 KEuro)	0 (0.00 KEuro)	60 (30.99 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	661 (341.38 KEuro)
2.	DELL'AMICO MAURO	164 (84.70 KEuro)	223 (115.17 KEuro)	210 (108.46 KEuro)	4 (2.07 KEuro)	21 (10.85 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	622 (321.24 KEuro)
3.	GRANDINETTI LUCIO	173 (89.35 KEuro)	156 (80.57 KEuro)	87 (44.93 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	416 (214.85 KEuro)
4.	SASSANO ANTONIO	195 (100.71 KEuro)	207 (106.91 KEuro)	150 (77.47 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	552 (285.08 KEuro)
5.	TRUBIAN MARCO	120 (61.97 KEuro)	162 (83.67 KEuro)	151 (77.98 KEuro)	18 (9.30 KEuro)	90 (46.48 KEuro)	0 (0.00 KEuro)	10 (5.16 KEuro)	551 (284.57 KEuro)
6.	CARAMIA MASSIMILIANO	175 (90.38 KEuro)	105 (54.23 KEuro)	0 (0.00 KEuro)	120 (61.97 KEuro)	60 (30.99 KEuro)	40 (20.66 KEuro)	0 (0.00 KEuro)	500 (258.23 KEuro)
7.	SALERNO SAVERIO	291 (150.29 KEuro)	229 (118.27 KEuro)	90 (46.48 KEuro)	0 (0.00 KEuro)	23 (11.88 KEuro)	0 (0.00 KEuro)	0 (0.00 KEuro)	633 (326.92 KEuro)
		1344 (694.12 KEuro)	1307 (675.01 KEuro)	838 (432.79 KEuro)	142 (73.34 KEuro)	254 (131.18 KEuro)	40 (20.66 KEuro)	10 (5.16 KEuro)	3935 (2032.26 KEuro)

Legenda Voce di spesa (DM. 199 Ric. del 08/03/01; art.6, c.6):

Spesa A: Spese di personale (*)
Spesa B: Spese generali direttamente imputabili all'attività di ricerca nella misura forfettizzata del 60% del costo del personale (compreso quello relativo ai ricercatori)
Spesa C: Spese per giovani ricercatori e ricercatori di chiara fama internazionale
Spesa D: Spese per l'acquisizione di strumentazioni, attrezzature e prodotti software, limitatamente alle quote impiegate per lo svolgimento dell'attività oggetto del progetto
Spesa E: Spese per stages e missioni all'estero di ricercatori coinvolti nel progetto
Spesa F: Costo dei servizi di consulenza e simili utilizzati per l'attività di ricerca
Spesa G: Altri costi di esercizio (ad es. costo dei materiali, delle forniture e dei prodotti analoghi) direttamente imputabili all'attività di ricerca

4.2 Costo complessivo della Proposta Progettuale risorse disponibili

nº	Responsabile Scientifico (codice)	RD+RA (MLit)	Risorse finanziarie richieste al MIUR (MLit)	Giovani ricercatori e ricercatori di chiara fama internazionale	Costo totale della proposta progettuale (MLit)
1.	PALLOTTINO STEFANO	156 (80.57 KEuro)	355 (183.34 KEuro)	150 (77.47 KEuro)	661 (341.38 KEuro)
2.	DELL'AMICO MAURO	124 (64.04 KEuro)	288 (148.74 KEuro)	210 (108.46 KEuro)	622 (321.24 KEuro)
3.	GRANDINETTI LUCIO	101 (52.16 KEuro)	228 (117.75 KEuro)	87 (44.93 KEuro)	416 (214.85 KEuro)
4.	SASSANO ANTONIO	122 (63.01 KEuro)	280 (144.61 KEuro)	150 (77.47 KEuro)	552 (285.08 KEuro)
5.	TRUBIAN MARCO	120 (61.97 KEuro)	280 (144.61 KEuro)	151 (77.98 KEuro)	551 (284.57 KEuro)
6.	CARAMIA MASSIMILIANO	150 (77.47 KEuro)	350 (180.76 KEuro)	0 (0.00 KEuro)	500 (258.23 KEuro)
7.	SALERNO SAVERIO	163 (84.18 KEuro)	380 (196.25 KEuro)	90 (46.48 KEuro)	633 (326.92 KEuro)
		936 (483.40 KEuro)	2161 (1116.06 KEuro)	838 (432.79 KEuro)	3935 (2032.26 KEuro)

	MLit
Costo complessivo della Proposta Progettuale	3935 (2032.26 KEuro)
Risorse complessivamente disponibili all'atto della domanda (RD)	936 (483.40 KEuro)
Risorse complessivamente acquisibili (RA)	0 (0.00 KEuro)
Risorse totali (RD+RA)	936 (483.40 KEuro)
Risorse finanziarie complessive richieste al MIUR	2161 (1116.06 KEuro)
Giovani ricercatori e ricercatori di chiara fama internazionale	838 (432.79 KEuro)

4.3 Costo minimo per garantire la possibilità di verifica dei risultati


(MLit)3.150 (1626.84 KEuro)

Si ricorda che la somma di risorse disponibili (o acquisibili) deve essere non inferiore al 30% del costo totale ammissibile del progetto, detratti i costi dei contratti triennali per giovani ricercatori e per ricercatori di chiara fama, che sono finanziati al 100%.

(per la copia da inviare per raccomandata o da consegnare all'accettazione del MIUR e per l'assenso alla diffusione via Internet delle informazioni riguardanti i progetti finanziati e la loro elaborazione necessaria alle valutazioni; legge del 31.12.96 n°675 sulla "Tutela dei dati personali")

Certifico, sotto la mia personale responsabilità, di aver ottenuto regolare autorizzazione dal rappresentante legale dell'ente di mia appartenenza, nonchè degli enti di tutte le altre Unità di Ricerca.

Firma del Coordinatore .............................

Firma del Rappresentante legale .............................

Data 15/10/2001 16:11