Disaster-resilient network design and resource management of elastic optical networks

Abstract

Disaster-based failures, due to either natural, technological or human causes, became more frequent in time and wider in scope, degrading drastically the communication services supported by telecommunication networks. This is of utmost importance since communication services are an important part of our society critical infrastructure. This issue is even more critical in optical networks where a single optical fiber can carry a very large amount of service demands. It is important not only to quickly recover the failed network elements disrupted by a disaster (post-disaster problem) but also to evaluate and minimize, before the disaster occurs, its impact on services between nodes outside the disaster area (predisaster problem). This thesis focuses on the pre-disaster problem and aims to investigate how Elastic Optical Networks (EONs) can be used in a cost-effective manner so that the impact of disaster-based failures is minimized. This thesis considers the disasters due to malicious humans attacks against some network elements. First, the vulnerability of existing optical networks to these failures is assessed, mainly resorting to variants of the Critical Node Detection (CND) problem, an optimization problem that seeks the set of nodes whose simultaneous failure mostly disrupt the network services. An exact row generation algorithm is proposed for the CND problem in the context of transparent optical networks. Then, we provide telecommunication operators with tools to enhance the robustness of optical network topologies against disaster-based failures. On one hand, we investigate how to upgrade existing optical networks, through link addition, aiming to enhance their robustness to multiple node failures. In a heuristic approach, within a given fiber length budget, a multi-start greedy randomized algorithm and a greedy deterministic algorithm are presented. In an exact approach, methods to compute the Pareto frontier of the bi-objective optimization problem that considers both the robustness maximization and the minimization of the cost of upgrading the network are proposed. On the other hand, a minimum cost gateway nodes selection to third-party networks with maximum disaster resilience against multiple failures is provided. The Gateway Node Selection (GNS) problem is defined, proposing an exact methodology to obtain all Pareto-optimal solutions. Finally, we exploit the advantages of spectrally (provided by elastic optical networking) flexible optical network planning and operations. Considering static and dynamic traffic, with a mix of unicast and anycast service demands, Routing, Modulation and Spectrum Assignment (RMSA) algorithms resilient to multiple node failures are proposed. These RMSA algorithms are based on an introduced metric, called path disaster availability, that measures the probability of a routing path not being disrupted by a multiple node attack.

Falhas provocadas por desastres, devido a causas naturais, tecnológicas ou humanas, tornaram-se mais frequentes e abrangentes, causando uma degradação drástica nos serviços de comunicação providenciados por redes de telecomunicações. Este facto tem uma importância extrema, uma vez que estes serviços de comunicação constituem uma parte com importância crítica na nossa sociedade. Este problema é ainda mais crítico em redes óticas pois uma única fibra ótica pode transportar informação de uma grande quantidade de serviços da rede. É importante não só recuperar rapidamente os elementos da rede afetados por um desastre (problema pós-desastre) mas também avaliar e minimizar, antes do desastre ocorrer, o impacto deste nos serviços entre nós fora da área afetada (problema pré-desastre). Esta tese está centrada no problema pré-desastre e visa investigar como as redes óticas elásticas (EONs) podem ser usadas de forma eficiente, em termos de custo, para que o impacto de falhas provocadas por desastres seja minimizado. Esta tese considera os desastres resultantes de ataques humanos maliciosos a alguns elementos da rede. Primeiramente, avalia-se a vulnerabilidade de rede óticas existentes a essas falhas, recorrendo principalmente a variantes do problema de Deteção de Nós Críticos (CND), um problema de otimização que procura o conjunto de nós cuja falha simultânea interrompe o maior número de serviços da rede. Um algoritmo exato de geração de linhas é proposto para o problema CND no contexto de redes óticas transparentes. Em seguida, fornece-se aos operadores de telecomunicações ferramentas para aumentar a robustez das topologias de redes óticas contra falhas provocadas por desastres. Por um lado, investiga-se como expandir as redes óticas existentes, recorrendo à adição de ligações, com o objetivo de aumentar a robustez a múltiplas falhas de nós. Numa abordagem heurística, dado um limite para o comprimento de fibra adicional, é apresentado um algoritmo greedy aleatório e um algoritmo greedy determinístico. Numa abordagem exata, desenvolvem-se métodos para calcular a fronteira de Pareto do problema de otimização biobjetivo que considera a maximização da robustez e a minimização do custo de expansão da rede. Por outro lado, fornece-se uma seleção de custo mínimo de nós gateway para redes de outros operadores com resiliência máxima contra multiplas falhas. O problema de Seleção de Nós Gateway (GNS) é definido, propondo uma metodologia exata para a obtenção de todos os ótimos de Pareto. Finalmente, explora-se as vantagens do planeamento e da operação de redes óticas com flexibilidade espectral (proporcionada por redes óticas elásticas). Considerando tráfego estático e dinâmico, com uma mistura de pedidos unicast e anycast servidos pela rede, propõem-se algoritmos de Encaminhamento, Modulação e Atribuição de Espectro (RMSA) resilientes a múltiplas falhas de nós. Esses algoritmos RMSA baseiam-se numa métrica introduzida, chamada disponibilidade do caminho em desastres, que mede a probabilidade de um caminho não ser afetado por um ataque a vários nós.