A Study on Multiobjective Dynamic Alternative Routing

Tese de Doutoramento em Engenharia Electrotécnica e de Computadores, Ramo de Especialização em Telecomunicações, apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra.The Internet has become a true business platform whose traffic has to be efficiently managed. The imminent arrival of 5G networks increases the potential of using mobile phones and laptops for everyday tasks or collaborative work demanding tight Quality of Service (QoS) requirements. With increasing traffic, in volume and dynamism, and the stagnation of operators' revenues, overprovisioning is no longer a reasonable option and it is imperative that more sophisticated mechanisms be used to simultaneously guarantee efficient management of resources and the satisfaction of the Service Level Agreements (SLAs). Internet operators can take advantage of traffic management and QoS guarantee mechanisms through the adoption of Multiprotocol Label Switching (MPLS) on their networks. To maximize the profitability on installed resources without degrading the blocking for the different traffic flows, this dissertation begins by proposing a state-dependent dynamic alternative routing method for multiservice MPLS networks, Simplified MultiObjective Dynamic Routing (SMODR). This routing method seeks to maximize the carried traffic and to minimize the maximum point-to-point blocking probability for each service while maximizing the total carried traffic keeping the maximal service mean blocking probability as lower as possible. The problem is solved by a heuristic that periodically calculates the set of alternative paths (one path per source-destination pair) that best fits the offered traffic conditions and leads to good compromise solutions for the underlying multiobjective model. SMODR is validated using a simulation platform where its performance is compared to that of a reference dynamic routing method. It has also been found that in situations of traffic imbalance single alternative paths per source-destination pair (as in the case of SMODR) may not have the resources to carry all the overflow traffic. To solve this problem a new routing method called Dynamic Multicriteria Alternative Routing (DMAR) is proposed, which associates an event-dependent strategy (based on the blocking or acceptance of a connection request) with the periodic update of multiple alternative paths per source-destination pair and for a given network state. The performance of the method is compared to that of reference methods using a simulation platform that allowed to simulate dynamic (or non-stationary) traffic. The results show that DMAR makes efficient use of the available network resources taking into account the various traffic flows in a single service network, as well as the different services in multiservice environments, leading to a better overall network performance. MPLS networks must also be resilient. In the event of a link failure in a network with a dynamic alternative routing method, incoming connection requests may attempt alternative paths but the traffic in progress on the failed link at the time of the failure is lost. To address this problem, a strategy has been proposed that combines a dynamic alternative routing method with a local protection mechanism without bandwidth reservation, Dynamic Alternative Routing with local Multiple paths Protection (DARMP), highlighting the importance of designing a protection mechanism in line with the routing method to improve the network performance while minimizing the resources usage also in the event of a failure. DARMP is validated by simulation by comparing its performance against two fixed routing methods with local protection. The routing methods proposed in this work are centralized and state-dependent, being adequate for the emerging Software-Defined Networks (SDN). RESUMO: A Internet tornou-se numa verdadeira plataforma de negócios cujo tráfego tem que ser gerido com e ciência. A chegada iminente das redes 5G aumenta o potencial do uso dos telemóveis e computadores portáteis para tarefas do quotidiano ou de trabalho colaborativo que exigem a satisfação de requisitos apertados de Qualidade de Serviço (QoS). Com o aumento do tráfego, em volume e dinamismo, e a estagna ção da receita dos operadores, o sobredimensionamento deixou de ser uma opção viável e e imperativo que sejam utilizados mecanismos sofisticados para garantir simultaneamente uma gestão e ciente dos recursos e a satisfação dos Acordos de Nível de Serviço. Os operadores de Internet podem tirar partido de mecanismos de gestão de tráfego e de garantia de QoS através da adoção de Multiprotocol Label Switching (MPLS) nas suas redes. De modo a maximizar a rentabilização dos recursos instalados sem deixar degradar o bloqueio para os diferentes fluxos de tráfego, esta dissertação começa por propor um método de encaminhamento alternativo dinâmico dependente do estado com formulação multiobjectivo para redes MPLS multi-serviço, o Simplied MultiObjective Dynamic Routing (SMODR). Este método de encaminhamento procura maximizar o tráfego transportado e minimizar o máximo bloqueio ponto- -a-ponto para cada servi co e simultaneamente maximizar o tráfego transportado total mantendo o máximo dos bloqueios médios para cada serviço o menor possível. O problema e resolvido através de uma heurística que calcula periodicamente o conjunto de caminhos alternativos (um caminho por par origem-destino) que melhor se adaptam as condições de tráfego oferecido e que conduzem a obtenção de boas soluções de compromisso para o modelo multiobjectivo subjacente. O SMODR e validado recorrendo a uma plataforma de simulação onde o seu desempenho e comparado com o de um método de referência de encaminhamento dinâmico. Verificou-se ainda que, em situações de desequilíbrio de tráfego, caminhos alternativos únicos por par origem-destino (como no caso do SMODR) podem n~ao ter os recursos necessários para transportar todo o tráfego de transbordo. Para resolver este problema e proposto um novo método de encaminhamento designado por Dynamic Multicriteria Alternative Routing (DMAR), que associa uma estratégia dependente do evento (baseada no bloqueio ou no sucesso no estabelecimento de uma ligação) a atualização periódica de múltiplos caminhos alternativos por par origem-destino e para um dado estado da rede. O desempenho do método e comparado com o de métodos de referência recorrendo a uma plataforma de simulação que permitiu simular tráfego dinâmico (ou não estacionário). Os resultados mostram que o DMAR faz uma utilização e ciente dos recursos disponíveis na rede tendo em conta os vários fluxos de tráfego numa rede mono-serviço, e tamb em os diferentes servi cos em ambientes multi-serviço, conduzindo a um melhor desempenho global da rede. As redes MPLS devem ainda ser resilientes. No caso de uma falha num link de uma rede com encaminhamento alternativo dinâmico, futuros pedidos de ligação podem tentar caminhos alternativos, mas o tráfego em curso no link falhado no instante da falha e perdido. Para resolver este problema foi proposta uma estratégia que associa um método de encaminhamento alternativo dinâmico com um mecanismo de proteção local sem reserva de largura de banda, Dynamic Alternative Routing with local Multiple paths Protection (DARMP), realçando a importância de se projetar um mecanismo de proteção alinhado com o método de encaminhamento no sentido de se melhorar o desempenho da rede minimizando os recursos envolvidos também em caso de falha. O DARMP e validado por simulação através da comparação do seu desempenho com o de dois métodos de encaminhamento fixo com proteção local. Os métodos de encaminhamento propostos neste trabalho são centralizados e dependentes do estado, sendo por isso adequados as emergentes redes definidas por software, ou Software-De ned Networks (SDN)