Impairment-aware minimization of the number of regenerators in optical transport networks

Abstract

With the increase in bandwidth consumption of today’s applications, backbone networks are required to carry great amounts of traffic, which is achieved using Wavelength Division Multiplexing (WDM) in transport optical networks.Physical impairments limit the maximum length that a signal can travel without regeneration. The quality of a signal in optical WDM networks must thus be restored with Optical-Electrical-Optical (OEO) regeneration in order to reach its destination. As OEO regenerators are costly devices, their sparse deployment using routing optimization is the key to reduce the network cost. In this thesis, the problem of impairment aware Routing and Wavelength Assignment and Regenerator Placement (RWARP), considering capacity constraints, while focusing on minimizing the number of regenerators, is tackled. This problem is NP-Complete. An extension to an existing Integer Linear Programing (ILP) formulation for the RWARP problem which provides, when feasible, an optimal solution, will be proposed. An efficient heuristic to solve the same problem is put forward, which is then enhanced with a traffic distribution method, to improve its effectiveness. Results show that the improved heuristic provides close to optimal results, for most of the tested cases, in a fraction of the ILP execution time.Four variants of the RWARP ILP formulation will be compared to evaluate the impact on the execution time, of the introduction of certain constraints. The comparison of these variants led to the conclusion that the introduction of wavelength assignment capabilities in regenerators speeds up the execution time of the optimizer running the ILP formulation. A single wavelength can carry a significant amount of information and fibres capable of carrying of several Tbps are being deployed. This makes the resilience of the optical connections an important issue, where recovery should take place in a very short time. Therefore, protection mechanisms, for example, the use of two risk disjoint paths (the active and backup path) for the same connection, are present in transport networks. Since fibre cuts are the most frequent form of failure in Optical Network (ON), fibre disjointedness is usually required between paths.Since dedicated (path) protection requires expensive resource allocation, pre-planned path recovery against single fibre failure, with regenerator sharing between backup paths and between an active path and its corresponding backup path, will be the explored recovery approach. This problem may be called the Survivable Routing and Wavelength Assignment and Regenerator Placement (SRWARP) problem and has been shown to be NP-Hard. Three variants of this problem are defined, differing the shared resources: dedicated-dedicated, if nothing is shared; dedicated-shared, if regenerators from an active path may be re-used for the corresponding backup path; and shared-shared, in which besides regenerator sharing between an active path and its backup, sharing of both bandwidth and regenerators is possible between backup paths whose active paths are fibre disjoint. For the two first variants, an ILP formulation is given, and for all variants, an efficient heuristic is proposed. Results for the ILP formulation of the SRWARP problem showed that it is impractical for real size networks. Nevertheless, the heuristics showed acceptable results in a relatively short amount of time. The shared-shared variant greatly reduces the amount of capacity required by the backup paths, as expected.The results of this work were integrated with a multi-layer grooming heuristic developed in the context of another master thesis. A recovery mechanism at the optical layer was also considered.

Com o aumento do consumo de largura de banda por parte das aplicações atuais, as redes de transporte precisam de suportar grandes volumes de tráfego, o que é conseguido usando Wavelength Division Multiplexing (WDM) em redes de transporte ótico.A degradação da qualidade do sinal, restringe a distância máxima que um sinal pode atravessar sem sofrer regeneração. A qualidade de um sinal em redes óticas que utilizem WDM pode ser recuperado usando regeneração Optical-Electrical-Optical (OEO) para poder chegar ao seu destino. Tendo em conta que os regeneradores OEO são dispositivos caros, a have para reduzir os custos de uma rede é a colocação esparsa destes dispositivos, conjugado com otimização do encaminhamento do tráfego. Nesta dissertação é abordado o problema do Routing and Wavelength Assignment and Regenerator Placement (RWARP) levando em conta a degradação do sinal, considerando as restrições de capacidade, com foco na minimização do número de regeneradores necessários. Este problema é NP-Completo. Será proposta uma extensão de uma formulação existente de Programação Linear Inteira (PLI) para o problema RWARP, a qual obtem, quando exequível, uma solução ótima. É ainda proposta uma heurística eficiente para a resolução do problema anterior, a qual é seguidamente extendida, aplicando um algoritmo de distribuição de tráfego, para melhorar a sua eficiência. A heurística melhorada é capaz de fornecer resultados próximos do ótimo, na grande maioria dos testes considerados, numa fração do tempo de execução da resolução exata obtida com a formulação PLI.Quatro variantes da formulação PLI para o problema RWARP serão comparadas, para avaliar o impacto no tempo de execução da introdução de certas restrições. A comparação destas variantes permite concluir que a introdução das capacidades de conversão do comprimento de onda nos regeneradores reduz o tempo de resolução do otimizador da formulação PLI.Um único comprimento de onda é capaz de transmitir uma quantidade significativa de informação, e, actualmente, estão a ser colocadas fibras capazes de transportar vários Tbps. Isto torna a questão da resiliência das conexões óticas fundamental, onde a recuperação das conexões deve ser feita num espaço de tempo muito curto. Por conseguinte, mecanismos de proteção, por exemplo, a utilização, por conexão, de dois caminhos disjuntos nos riscos de falha (caminho ativo e caminho de recuperação) estão presentes nas redes de transporte. Uma vez que os cortes nas fibras são a forma mais frequente de falha em redes óticas, caminhos disjuntos nas fibras são normalmente utilizados.Uma vez que a proteção dedicada (ao caminho) requer uma dispendiosa alocação de recursos, será utilizada recuperação pré-planeada contra falhas de uma única fibra, com a partilha de regeneradores entre caminhos de recuperação e partilha de regeneradores entre caminhos ativos e os respetivos caminhos de recuperação. Este problema pode ser identificado como o problema Survivable Routing and Wavelength Assignment and Regenerator Placement (SRWARP) o qual tem uma complexidade NP-Hard.Três variantes deste problema são definidos, os quais se distinguem pelos recursos que são (ou não) partilhados: dedicado-dedicado, se não há partilha; dedicado-partilhado, se os regeneradores de um caminho ativo podem ser reutilizados pelo caminho de recuperação correspondente; e partilhado-partilhado, onde para além da partilha do caso anterior há ainda a partilha da largura de banda e dos regeneradores entre os caminhos de recuperação cujos caminhos ativos são disjuntos. Para as primeiras duas variantes, uma formulação PLI é apresentada, e para todas as variantes é proposta uma heurística eficiente. Os resultados para o problema SRWARP mostraram que a formulação PLI não é utilizável (na prática) para redes com tamanho real. Contudo, os resultados obtidos pela heurística desenvolvida são aceitáveis e obtidos num tempo relativamente curto. Como esperado, a variante partilhado-partilhado reduz drasticamente a capacidade necessária para suportar os caminhos de recuperação.Os resultados deste trabalho foram ainda integrados numa heurística para a resolução de um problema de encaminhamento multi-camada, a qual foi desenvolvida no âmbito de uma outra dissertação de mestrado. Nesse contexto foi ainda implementado um um mecanismo de recuperação na camada ótica.