Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

Least-cost Disjoint Paths with Dependent Cost Structure in Wavelength Continuous Optical WDM Networks

One of the important issues in establishing a fault tolerant connection in a wavelength division multiplexing optical network is computing a pair of disjoint working and protection paths and a free wavelength along the paths. While most of the earlier research focused only on computing disjoint paths, in this work we consider computing both disjoint paths and a free wavelength along the paths. The concept of dependent cost structure (DCS) of protection paths to enhance their resource sharing ability was proposed in our earlier work. In this work we extend the concept of DCS of protection paths to wavelength continuous networks. We formalize the problem of computing disjoint paths with DCS in wavelength continuous networks and prove that it is NP-complete. We present an iterative heuristic that uses a layered graph model to compute disjoint paths with DCS and identify a free wavelength.

Survivable Traffic Grooming with Path Protection at the Connection Level in WDM Mesh Networks

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength division multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated protection and shared protection schemes are considered. Given the network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures such as fiber cut and duct cut, we consider the general shared risk link group (SRLG) diverse routing constraints. We first resort to the integer linear programming (ILP) approach to obtain optimal solutions. To address its high computational complexity, we then propose three efficient heuristics, namely separated survivable grooming algorithm (SSGA), integrated survivable grooming algorithm (ISGA) and tabu search survivable grooming algorithm (TSGA). While SSGA and ISGA correspond to an overlay network model and a peer network model respectively, TSGA further improves the grooming results from SSGA and ISGA by incorporating the effective tabu search method. Numerical results show that the heuristics achieve comparable solutions to the ILP approach, which uses significantly longer running times than the heuristics.

Dynamic traffic grooming algorithms for reconfigurable SONET over WDM networks

The emergence of Wavelength Division Multiplexing (WDM) technology provides the capability for increasing the bandwidth of Synchronous Optical Network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add-drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom in the traffic and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently.

Optimization of Amplifier Placements in Switch-Based Optical Networks

Wavelength division multiplexing (WDM) offers a solution to the problem of exploiting the large bandwidth on optical links; it is the current favorite multiplexing technology for optical communication networks. Due to the high cost of an optical amplifier, it is desirable to strategically place the amplifiers throughout the network in a way that guarantees that all the signals are adequately amplified while minimizing the total number amplifiers being used. Previous studies all consider a star-based network. This paper demonstrates an original approach for solving the problem in switch-based WDM optical network assuming the traffic matrix is always the permutation of the nodes. First we formulate the problem by choosing typical permutations which can maximize traffic load on individual links; then a GA (Genetic Algorithm) is used to search for feasible amplifier placements. Finally, by setting up all the lightpaths without violating the power constaints we confirm the feasibility of the solution.

Design of a Comb Generator for High Capacity Coherent-WDM Systems

This paper presents a theoretical model developed for estimating the power, the optical signal to noise ratio and the number of generated carriers in a comb generator, having as a reference the minimum optical signal do noise ratio at the receiver input, for a given fiber link. Based on the recirculating frequency shifting technique, the generator relies on the use of coherent and orthogonal multi-carriers (Coherent-WDM) that makes use of a single laser source (seed) for feeding high capacity (above 100 Gb/s) systems. The theoretical model has been validated by an experimental demonstration, where 23 comb lines with an optical signal to noise ratio ranging from 25 to 33 dB, in a spectral window of similar to 3.5 nm, are obtained.

Progettazione e analisi di soluzioni per la QOS e il controllo di flusso in Networks-on-chip

Nel documento vengono principalmente trattati i principali meccanismi per il controllo di flusso per le NoC. Vengono trattati vari schemi di switching, gli stessi schemi associati all'introduzione dei Virtual Channel, alcuni low-level flow control, e due soluzioni per gli end-to-end flow control: Credit Based e CTC (STMicroelectronics). Nel corso della trattazione vengono presentate alcune possibili modifiche a CTC per incrementarne le prestazioni mantenendo la scalabilità che lo contraddistingue: queste sono le "back-to-back request" e "multiple incoming connections". Infine vengono introdotti alcune soluzioni per l'implementazione della qualità di servizio per le reti su chip. Proprio per il supporto al QoS viene introdotto CTTC: una versione di CTC con il supporto alla Time Division Multiplexing su rete Spidergon.

Sistemi OFDM: prestazioni di livello fisico

I primi studi su Orthogonal Frequency Division Multiplexing (OFDM) sono stati fatti fin dal 1960, ma negli ultimi anni la modulazione OFDM è emersa come una tecnica di modulazione chiave commerciale per i sistemi di comunicazione ad alta velocità. La ragione principale di questo crescente interesse è dovuto alla sua capacità di fornire dati ad alta velocità impiegando sistemi con complessità bassa e contrastando l'interferenza intersimbolo (ISI) e quella intercanale (ICI). Per questo motivo la modulazione OFDM è stata adottata da diversi sistemi digitali wireline e wireless standard, come Digital Audio Broadcasting (DAB), Asymmetric Digital Subscriber Line (ADSL), Wireless Local Area Network (IEEE 802.11 a,g,n) oppure per WiMAX e LTE.

Synchronization and Detection Techniques for Navigation and Communication Systems

Synchronization is a key issue in any communication system, but it becomes fundamental in the navigation systems, which are entirely based on the estimation of the time delay of the signals coming from the satellites. Thus, even if synchronization has been a well known topic for many years, the introduction of new modulations and new physical layer techniques in the modern standards makes the traditional synchronization strategies completely ineffective. For this reason, the design of advanced and innovative techniques for synchronization in modern communication systems, like DVB-SH, DVB-T2, DVB-RCS, WiMAX, LTE, and in the modern navigation system, like Galileo, has been the topic of the activity. Recent years have seen the consolidation of two different trends: the introduction of Orthogonal Frequency Division Multiplexing (OFDM) in the communication systems, and of the Binary Offset Carrier (BOC) modulation in the modern Global Navigation Satellite Systems (GNSS). Thus, a particular attention has been given to the investigation of the synchronization algorithms in these areas.

Modellazione Tridimensionale del Processo di Combustione di un Razzo a Propellente Solido

La regolazione dei sistemi di propulsione a razzo a propellente solido (Solid Rocket Motors) ha da sempre rappresentato una delle principali problematiche legate a questa tipologia di motori. L’assenza di un qualsiasi genere di controllo diretto del processo di combustione del grano solido, fa si che la previsione della balistica interna rappresenti da sempre il principale strumento utilizzato sia per definire in fase di progetto la configurazione ottimale del motore, sia per analizzare le eventuali anomalie riscontrate in ambito sperimentale. Variazioni locali nella struttura del propellente, difettosità interne o eterogeneità nelle condizioni di camera posso dare origine ad alterazioni del rateo locale di combustione del propellente e conseguentemente a profili di pressione e di spinta sperimentali differenti da quelli previsti per via teorica. Molti dei codici attualmente in uso offrono un approccio piuttosto semplificato al problema, facendo per lo più ricorso a fattori correttivi (fattori HUMP) semi-empirici, senza tuttavia andare a ricostruire in maniera più realistica le eterogeneità di prestazione del propellente. Questo lavoro di tesi vuole dunque proporre un nuovo approccio alla previsione numerica delle prestazioni dei sistemi a propellente solido, attraverso la realizzazione di un nuovo codice di simulazione, denominato ROBOOST (ROcket BOOst Simulation Tool). Richiamando concetti e techiche proprie della Computer Grafica, questo nuovo codice è in grado di ricostruire in processo di regressione superficiale del grano in maniera puntuale, attraverso l’utilizzo di una mesh triangolare mobile. Variazioni locali del rateo di combustione posso quindi essere facilmente riprodotte ed il calcolo della balistica interna avviene mediante l’accoppiamento di un modello 0D non-stazionario e di uno 1D quasi-stazionario. L’attività è stata svolta in collaborazione con l’azienda Avio Space Division e il nuovo codice è stato implementato con successo sul motore Zefiro 9.

Supersymmetric Mode Converters

Originally developed in the context of quantum field theory, the concept of supersymmetry can be used to systematically design a new class of optical structures. In this work, we demonstrate how key features arising from optical supersymmetry can be exploited to control the flow of light for mode division multiplexing applications. Superpartner configurations are experimentally realized in coupled optical networks, and the corresponding light dynamics in such systems are directly observed. We show that supersymmetry can be judiciously utilized to remove the fundamental mode of a multimode optical structure, while establishing global phase matching conditions for the remaining set of modes. Along these lines, supersymmetry may serve as a promising platform for versatile optical components with desirable properties and functionalities.

Estudio de limitaciones en sistemas WDM

Los avances tecnológicos de los últimos años han modificado el panorama de las comunicaciones ópticas. Los amplificadores EDFA (Erbium-Doped Fiber Amplifier) han alterado dos aspectos fundamentales de los sistemas WDM (Wavelength Division Multiplexing): el aumento considerable de las distancias de regeneración y además, la tecnología WDM es un medio más económico de incrementar la capacidad de los sistemas que la tecnología TDM (Time Division Multiplexing). Sin embargo, la implementación de sistemas WDM con grandes tramos sin regeneración de señal óptica trae consigo la aparición de nuevos problemas, entre los que se encuentran las no-linealidades en fibra óptica. Estas no-linealidades en fibras de sílice se pueden clasificar en dos categorías: dispersión estimulada (de Raman y de Brillouin) y efectos debidos al índice no lineal de refracción (automodulación y modulación cruzada de fase y mezcla de cuatro ondas). Este Proyecto Fin de Carrera pretende ser un estudio teórico que refleje el actual Estado del Arte de los principales efectos no-lineales que se producen en los sistemas WDM: dispersión estimulada de Raman (SRS, Stimulated Raman Scattering), dispersión estimulada de Brillouin (SBS,Stimulated Brilfouin Scattering), automodulación de fase (SPM, Self-Phase Modulation), modulación cruzada de fase (XPM, Cross-Phase Modulation) y mezcla de cuatro ondas (FWM, Four-Wave Mixing).

Modulation-Mode Assignment in SVD-Aided Downlink Multiuser MIMO-OFDM Systems

Multicarrier transmission such as OFDM (orthogonal frequency division multiplexing) is an established technique for radio transmission systems and it can be considered as a promising approach for next generation wireless systems. However, in order to comply with the demand on increasing available data rates in particular in wireless technologies, systems with multiple transmit and receive antennas, also called MIMO (multiple-input multiple-output) systems, have become indispensable for future generations of wireless systems. Due to the strongly increasing demand in high-data rate transmission systems, frequency non-selective MIMO links have reached a state of maturity and frequency selective MIMO links are in the focus of interest. In this field, the combination of MIMO transmission and OFDM can be considered as an essential part of fulfilling the requirements of future generations of wireless systems. However, single-user scenarios have reached a state of maturity. By contrast multiple users' scenarios require substantial further research, where in comparison to ZF (zero-forcing) multiuser transmission techniques, the individual user's channel characteristics are taken into consideration in this contribution. The performed joint optimization of the number of activated MIMO layers and the number of transmitted bits per subcarrier shows that not necessarily all user-specific MIMO layers per subcarrier have to be activated in order to minimize the overall BER under the constraint of a given fixed data throughput.

Modulation-mode assignment in SVD-assisted multiuser MIMO-OFDM systems

In order to comply with the demand on increasing available data rates in particular in wireless technologies, systems with multiple transmit and receive antennas, also called MIMO (multiple-input multiple-output) systems, have become indispensable for future generations of wireless systems. Due to the strongly increasing demand in high-data rate transmission systems, frequency non-selective MIMO links have reached a state of maturity and frequency selective MIMO links are in the focus of interest. In this field, the combination of MIMO transmission and OFDM (orthogonal frequency division multiplexing) can be considered as an essential part of fulfilling the requirements of future generations of wireless systems. However, single-user scenarios have reached a state of maturity. By contrast multiple users’ scenarios require substantial further research, where in comparison to ZF (zero-forcing) multiuser transmission techniques, the individual user’s channel characteristics are taken into consideration in this contribution. The performed joint optimization of the number of activated MIMO layers and the number of transmitted bits per subcarrier along with the appropriate allocation of the transmit power shows that not necessarily all user-specific MIMO layers per subcarrier have to be activated in order to minimize the overall BER under the constraint of a given fixed data throughput.

Influence of Current Pulse Shape on Directly Modulated Systems Performance in Metro Area Optical Networks

Due to the fact that a metro network market is very cost sensitive, direct modulated schemes appear attractive. In this paper a CWDM (Coarse Wavelength Division Multiplexing) system is studied in detail by means of an Optical Communication System Design Software; a detailed study of the modulated current shape (exponential, sine and gaussian) for 2.5 Gb/s CWDM Metropolitan Area Networks is performed to evaluate its tolerance to linear impairments such as signal-to-noise-ratio degradation and dispersion. Point-to-point links are investigated and optimum design parameters are obtained. Through extensive sets of simulation results, it is shown that some of these shape pulses are more tolerant to dispersion when compared with conventional gaussian shape pulses. In order to achieve a low Bit Error Rate (BER), different types of optical transmitters are considered including strongly adiabatic and transient chirp dominated Directly Modulated Lasers (DMLs). We have used fibers with different dispersion characteristics, showing that the system performance depends, strongly, on the chosen DML?fiber couple.