Os objetivos desta monografia foram analisar as propriedades de topologias de redes complexas, analisar as potencialidades e comparar desempenho de softwares gratuitos de geração de topologias e simular roteamento de tráfego em redes de telecomunicações. As principais topologias analisadas foram a regular, aleatória e livre de escala. As propriedades topológicas incluem o grau nodal, a distribuição de grau, o coeficiente de agrupamento, o comprimento médio do caminho, além do efeito mundo pequeno. Foram avaliadas as potencialidades de três ferramentas gratuitas de geração e análise de redes, o B-A, Pajek e NetLogo. Como exemplos de aplicação em redes de telecomunicações, com destaque para redes ópticas utilizando técnica de multiplexação por divisão de comprimento de onda, foram implementados os seguintes algoritmos de roteamento de tráfego: roteamento fixo com alocação de comprimento de onda sequencial fixa e roteamento adaptativo com alocação de comprimento de onda menos usado, mais usado, aleatória e busca exaustiva. O desempenho dos algoritmos de roteamento e alocação de comprimentos de onda de modo nas topologias analisadas foram comparados. / The purposes of this master\'s thesis are to analyze the properties of complex network topologies, analyze and compare the performance of free software for generating topologies and simulate traffic routing in telecommunication networks. The main topologies analyzed were the regular, random and scale-free. The topological properties include the nodal degree, the distribution degree, clustering coefficient, average path length and small-world effect. The performance of the free softwares B-A, Pajek and Netlogo were evaluated. As examples of application in telecommunication networks, especially for optical networks using wavelength division multiplexing technique, the following routing traffic algorithms were implemented: Fixed routing with first-fit wavelength assignment and adaptive routing with least used wavelength assignment, most used, random and exhaustive search. The performance of algorithms for routing and wavelength allocation employed in the analyzed topologies was compared.

Este trabalho investiga a influência dos efeitos da mistura de quatro ondas (FWM -. Four- Wave Mixing) durante o estabelecimento de caminhos ópticos em uma rede GMPLS/DWDM (Generalized MultiProtocol Label Switching/Dense Wavelength Division Multiplexing). Para minimizar seus impactos e assim reduzir o bloqueio total da rede, são propostas estratégias por meio de extensões ao RSVP-TE (Resource Reservation Protocol-Traffic Engineering). A partir de uma plataforma de simulação que emula e integra a camada óptica e o Plano de Controle da arquitetura GMPLS, a solução proposta é validada. Os vários métodos de alocação de comprimentos de onda são avaliados e as contribuições na redução dos sinais interferentes quantificadas. Para minimizar o bloqueio na rede, uma nova classe de métodos de alocação, classificados como híbridos, é definida e seu desempenho é avaliado. O bloqueio da rede em função da variação de parâmetros que reforçam a eficiência da FWM, tais como a quantidade e espaçamento entre canais, é observado, confirmando a necessidade de métodos de alocação especialistas para gerenciamento do QoS (Quality of Service) óptico em cada caminho a ser estabelecido. Os resultados obtidos comprovam a eficiência da solução proposta e evidenciam a necessidade de um Plano de Controle GMPLS com acurada visibilidade das restrições da camada física, tanto os efeitos estáticos quanto às degradações associadas ao comportamento dinâmico da rede. / This work investigates the effects of the Four-Wave Mixing (FWM) during the lightpaths establishment in a GMPLS/DWDM (Generalized Multiprotocol Label Switching / Dense Wavelength Division Multiplexing) network. In order to minimize their impacts and thus reduce network blocking, strategies based on RSVP-TE (Resource Reservation Protocol- Traffic Engineering) extensions are proposed. The proposed solution is validated using a simulation platform that integrates and emulates the optical layer and the GMPLS Control Plane. The various wavelength allocation methods are evaluated and their contributions on the reduction of interfering signals are quantified. In order to minimize the network blocking, a new class of allocation methods (classified as hybrids) is defined and its performance is evaluated. The network blocking caused by the parameters that enhance the FWM efficiency, such as the number and spacing between channels, is also observed, confirming the need of specialized wavelength allocation methods for managing the optical QoS for each lightpath. The results obtained ascertain that the proposed solution is efficient and demonstrate the need for a GMPLS Control Plane endowed with an accurate visibility of the restrictions in the physical layer, concerning both static and dynamic effects.

Este trabalho investiga a influência dos efeitos da mistura de quatro ondas (FWM -. Four- Wave Mixing) durante o estabelecimento de caminhos ópticos em uma rede GMPLS/DWDM (Generalized MultiProtocol Label Switching/Dense Wavelength Division Multiplexing). Para minimizar seus impactos e assim reduzir o bloqueio total da rede, são propostas estratégias por meio de extensões ao RSVP-TE (Resource Reservation Protocol-Traffic Engineering). A partir de uma plataforma de simulação que emula e integra a camada óptica e o Plano de Controle da arquitetura GMPLS, a solução proposta é validada. Os vários métodos de alocação de comprimentos de onda são avaliados e as contribuições na redução dos sinais interferentes quantificadas. Para minimizar o bloqueio na rede, uma nova classe de métodos de alocação, classificados como híbridos, é definida e seu desempenho é avaliado. O bloqueio da rede em função da variação de parâmetros que reforçam a eficiência da FWM, tais como a quantidade e espaçamento entre canais, é observado, confirmando a necessidade de métodos de alocação especialistas para gerenciamento do QoS (Quality of Service) óptico em cada caminho a ser estabelecido. Os resultados obtidos comprovam a eficiência da solução proposta e evidenciam a necessidade de um Plano de Controle GMPLS com acurada visibilidade das restrições da camada física, tanto os efeitos estáticos quanto às degradações associadas ao comportamento dinâmico da rede. / This work investigates the effects of the Four-Wave Mixing (FWM) during the lightpaths establishment in a GMPLS/DWDM (Generalized Multiprotocol Label Switching / Dense Wavelength Division Multiplexing) network. In order to minimize their impacts and thus reduce network blocking, strategies based on RSVP-TE (Resource Reservation Protocol- Traffic Engineering) extensions are proposed. The proposed solution is validated using a simulation platform that integrates and emulates the optical layer and the GMPLS Control Plane. The various wavelength allocation methods are evaluated and their contributions on the reduction of interfering signals are quantified. In order to minimize the network blocking, a new class of allocation methods (classified as hybrids) is defined and its performance is evaluated. The network blocking caused by the parameters that enhance the FWM efficiency, such as the number and spacing between channels, is also observed, confirming the need of specialized wavelength allocation methods for managing the optical QoS for each lightpath. The results obtained ascertain that the proposed solution is efficient and demonstrate the need for a GMPLS Control Plane endowed with an accurate visibility of the restrictions in the physical layer, concerning both static and dynamic effects.

Os objetivos desta monografia foram analisar as propriedades de topologias de redes complexas, analisar as potencialidades e comparar desempenho de softwares gratuitos de geração de topologias e simular roteamento de tráfego em redes de telecomunicações. As principais topologias analisadas foram a regular, aleatória e livre de escala. As propriedades topológicas incluem o grau nodal, a distribuição de grau, o coeficiente de agrupamento, o comprimento médio do caminho, além do efeito mundo pequeno. Foram avaliadas as potencialidades de três ferramentas gratuitas de geração e análise de redes, o B-A, Pajek e NetLogo. Como exemplos de aplicação em redes de telecomunicações, com destaque para redes ópticas utilizando técnica de multiplexação por divisão de comprimento de onda, foram implementados os seguintes algoritmos de roteamento de tráfego: roteamento fixo com alocação de comprimento de onda sequencial fixa e roteamento adaptativo com alocação de comprimento de onda menos usado, mais usado, aleatória e busca exaustiva. O desempenho dos algoritmos de roteamento e alocação de comprimentos de onda de modo nas topologias analisadas foram comparados. / The purposes of this master\'s thesis are to analyze the properties of complex network topologies, analyze and compare the performance of free software for generating topologies and simulate traffic routing in telecommunication networks. The main topologies analyzed were the regular, random and scale-free. The topological properties include the nodal degree, the distribution degree, clustering coefficient, average path length and small-world effect. The performance of the free softwares B-A, Pajek and Netlogo were evaluated. As examples of application in telecommunication networks, especially for optical networks using wavelength division multiplexing technique, the following routing traffic algorithms were implemented: Fixed routing with first-fit wavelength assignment and adaptive routing with least used wavelength assignment, most used, random and exhaustive search. The performance of algorithms for routing and wavelength allocation employed in the analyzed topologies was compared.

Notre travail porte sur l'étude du Problème de Routage et d'Allocation de Longueur d'Onde (Routing and Wavelength Allocation - RWA) dans des réseaux optiques WDM, indépendamment de la topologie physique sous-jacente. Le problème a été idntifié comme étant NP-difficile et plusieurs approches, tant exactes qu'approchées, existent. Nous fournissons d'abord une revue de littérature dans laquelle nous présentons quelques formulations mathématiques pour le problème ainsi que plusieurs manières d'obtenir des bornes inférieures et des heuristiques. Nous considérons le problème min-RWA dans lequel on doit satisfaire un certain nombre de requêtes avec le moins de longueurs d'onde possible. Nous présentons une méthodologie reposant sur une recherche locale de type Descente à Voisinage Variable (Variable Neighborhood Descent - VND) que l'on appelle VND-BFD. Son objectif principal est de supprimer des longueurs d'onde. Nous présentons également une méthode hybride VND-BT. Ensuite, nous proposons une nouvelle approche, elle-aussi reposant sur la VND. Elle consiste à ré-arranger les requêtes entre les longueurs d'onde disponibles. Lorsqu'elle atteint un optimum local, une procédure de perturbation est appliquée et le schéma est similaire à la Recherche Locale Itérée (Iterated Local Search - ILS). Quatre variantes sont définies selon les stratégies appliquées dans VND et ILS : VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p et VNDe-ILS5p. Les résultats expérimentaux montrent que cette nouvelle approche est plus performante, en particulier la version VNDe-ILS5p. La méthode est compétitive avec les meilleures méthodes de la littérature puisque VNDe-ILS5p a permis d'améliorer une grande partie des meilleures solutions connues sur les instances standard du min-RWA. Enfin, nous considérons aussi le problème max-RWA dans lequel on doit maximiser le nombre de requêtes traitées avec un nombre donné de longueurs d'onde. Nous proposons des modèles compacts ainsi que des améliorations destinées à accélérer la résolution par des solveurs en nombre entiers. Après avoir décrit des modèles existants utilisant la génération de colonnes, nous proposons un nouveau modèle, PG-MAX-IS-IRC, utilisant lui-aussi la génération de colonnes. Il permet d'obtenir des bornes supérieures de même qualité en un temps très fortement réduit. / This work deals with the routing and Wavelength assignment (RWA) in optical WDM networks independently on the underlying physical topology. We begin with a review of the literature presented some mathematical models formulated to solve theproblem, are also reviewed methods for setting lower bounds and heuristic methods. This problem has been shown to be NP-hard and several heuristic algorithms have been developed to solve it. We present in this work a methodology based on metaheuristic Variable Neighborhood Descent (VND), which we call VND-BFD, primarily with the focus on the elimination of wavelengths and a hybrid method VND-BT to solve the problem. Then we introduce a new approach also based on VND, but this time with the focus on the rearrangement of the requests, when this new version of the VND fails the procedure activates a disturbance, as the metaheuristic Iterated Local Search. We define four variants to this method, which we call VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p and VNDe-ILS5p. The computational experiments show that the approach with the focus on requestsproved more efficient, especially the version VNDe-ILS5p. The proposed method is competitive with respect to the best methods in the literature. Finally, we present compact models aimed at maximizing the number of requests accepted and some simplifications are proposed in order to speed up the resolution of problems. Although we present some models of literature based on column generation and a new methodology is proposed. The new methodology, which we call PG-MAX-IS-IRC, was able to solve all instances faster than the method of the literature and always found the same upper bound.

La croissance continue du trafic Internet implique une augmentation de la consommation d'énergie en raison des nombreuses conversions optique à électronique(OEO) requises par les routeurs et les commutateurs. L'utilisation de réseaux transparents pourraient freiner cette croissance incontrôlée, mais le maintien des données dans le domaine optique a deux conséquences néfastes: une accumulation du bruit et des non-linéarités de l'amplification qui dégrade fortement les performances au niveau de la couche physique. et la contrainte de continuité de longueur d'onde (WCC) reflétant la conservation de la longueur d'onde du signal optique dans les réseaux optiques multiplexés en longueur d'onde (WDM) qui dégradent les performances du réseau, notamment sa probabilité de blocage. Les convertisseurs de longueur d'onde (WC) peuvent pallier la contrainte WCC, mais les seuls dispositifs suffisamment matures disponibles dans le commerce sont les WC basés sur OEO (OEO-WC). Cependant, leur coût augmente avec les débits binaires. D'autre part, des convertisseurs de longueur d'onde tout optique (AO-WC) ont été démontrés dans des laboratoires de recherche, avec toutefois une plage de conversion limitée et une dégradation du signal converti.Dans cette thèse, nous concevons la couche de transmission en utilisant deux ensembles de formats de modulation différents avec des plages de débits différentes; et par conséquent différents modèles d'estimation de performance. Au niveau du réseau, nos analyses montrent que la contribution des WC dépend des demandes de trafic servant à l’ordre dans un scénario de planification du réseau; qu'en utilisant des algorithmes fixed-alternate-routing (FAR) ou least-loaded-routing (LLR) et un algorithme d'affectation de longueur d'onde first-fit (FF), les AO-WCs offrent les mêmes améliorations de performances que les OEO-WC. De plus, nous identifions une plage de conversion et une cascadabilité optimale d’AO-WC qui montre que le LLR nécessite un nombre de conversions par canal inférieur au FAR. / The continuous growth of Internet traffic implies an increased power consumption due to the many optical-to-electronic (OEO) conversions required by routers and switches. Transparent networks could curb this uncontrolled growth, but keeping the data in the optical domain has two adverse consequences: physical layer impairments accumulation which strongly degrades the performance due to amplication noise and non-linearities; and the wavelength continuity constraint (WCC) to keep the opticalsignal's wavelength unchanged in wavelength-division-multiplexed (WDM) optical networks which degrades network blocking performance. Wavelength converters (WCs) can alleviate the WCC constraint, but the only commercially available devices are the OEO-based WCs (OEO-WCs), however, their cost increases with bit-rates. On the other hand, all-optical wavelength converters (AO-WCs) have been demonstrated in research laboratories albeit with a limited conversion range and a performance that degrades converted signal's quality.In this thesis, we design the transmission layer using two different modulation formats sets with different bit-rates ranges; and consequently different performance estimation models. At the network level, our analyses show that WCs' contribution depends on traffic demands serving ordering in the online traffic assumption; that using xed-alternate routing (FAR) or least-loaded routing (LLR) algorithms and first-fit (FF) wavelength assignment algorithm, AO-WCs give the same performance enhancement as OEO-WCs. Moreover, we identify an optimum AO-WC conversion range and cascadability which shows that LLR requires lower number of conversions per channel compared to FAR.