Intradomain routing optimization based on evolutionary computation

Abstract

The growing number of Internet-connected devices and the escalation of new Internet services, such as cloud services and video streaming, are some examples of factors that increase the volume and mutability of traffic in communication networks. The need to channel increasingly large volumes of traffic in network infrastructures with limited capacity, highlights the importance of Traffic Engineering mechanisms that aim to deliver an efficient use of network resources. Routing decisions play a key role as they de ne how traffic is distributed on the available paths and hence how networks resources are explored. Traditional routing protocols, such as Open Shortest Path First and Intermediate System to Intermediate System, have constraints which prevent an optimal network resources utilization. Some of these constraints are, for example, their inability to perform uneven splitting of traffic across multiple paths and their lack of a centralized control. These constraints impose additional difficulties when changes in network operating conditions need to be considered, such as significant variations intra c necessities and link failures. When facing such changes, routing configurations need to adapt to the new conditions and ensure that the network continues to operate efficiently. Communication technologies are constantly evolving. Recently, alternative routing solutions have emerged that enable new Traffic Engineering approaches. Network management problems and, in particular, the optimization of network resources utilization can be addressed using such alternative solutions. Software-De ned Networking and Segment Routing paradigms provide greater exibility in the selection of routing paths, and although they can overcome many of the constraints of traditional routing protocols, it is necessary to find configurations, both scalable and manageable in real contexts, that optimize the distribution of available resources. In this context, this research work intends to respond to the stated problems by proposing efficient mechanisms for optimizing the use of resources in networks configured with traditional Link State routing protocols, as well as in networks that implement the latest paradigms of Software De ned Networking and Segment Routing. In addition to enabling efficient resource utilization, the proposed optimization mechanisms are responsive to relevant changes in the network environment that may result from variations in traffic requirements or topology changes such as link failures. The nature of the problems, which besides not being solvable in polynomial time include more than one optimization objective in their formulation, are addressed using algorithms fostered in the field of Evolutionary Computation. Distinct traffic requirements and different network states frequently require clashing configurations. Evolutionary Algorithms possess several characteristics that are desirable to solve problems with multiple conflicting goals and make them preferable to classical optimization methods. They provide a set of compromise solutions to problems for which there is no single optimal solution. The research work winded up in an autonomous optimization framework that integrates all the proposed Traffic Engineering methods, which is made publicly available to be freely used by researchers and network administrators.

O surgimento e a prolifera cão de novos serviços de Internet, como os servi cos de cloud e a transmissão de vídeo, bem como o aumento do número de dispositivos que se ligam diariamente a Internet, são alguns fatores que contribuem para um avolumar e uma mudança nos padrões do trafego em redes de comunica cão. A necessidade de canalizar grandes volumes de trafego em infraestruturas de rede com capacidade limitada, enfatiza a importância da Engenharia de Trafego que tem por objetivo proporcionar um uso e ciente dos recursos de rede. As decisões de encaminhamento desempenham um papel essencial neste contexto, pois de nem como o trafego e distribuído pelos caminhos disponíveis e, consequentemente, como os recursos de rede são utilizados. Os protocolos de encaminhamento tradicionais, como o Open Shortest Path First e o Intermediate System to Intermediate System, possuem restrições operacionais que impedem uma utilização ótima dos recursos. Algumas dessas restrições são, por exemplo, as opções limitadas de balanceamento de carga e a falta de uma gestão centralizada. Essas restrições impõem dificuldades acrescidas quando alterações nas condições de funcionamento da rede têm de ser contempladas como, por exemplo, variações significativas do volume e trafego e falhas de ligações f sicas. As configurações de encaminhamento precisam adaptar-se as novas condições operacionais e garantir que a rede continue a operar de forma e ciente. As tecnologias de comunicação evoluem. Recentemente foram propostas soluções alternativas de encaminhamento de trafego que permitem novas abordagens de Engenharia de Trafego. Os problemas de gestão de redes e, em particular, a otimização da utilização de recursos podem ser abordados com recurso a essas novas soluções. Os paradigmas de Software Defined Networking e Segment Routing proporcionam uma maior exibilidade na seleção de caminhos de trafego, e embora sejam capazes de superar muitas das restrições dos protocolos de encaminhamento tradicionais, e necessário encontrar configurações, escaláveis e geríveis em contexto real, que otimizem a distribuição de trafego nos recursos disponíveis. Neste contexto, este trabalho de investigação procura responder aos problemas enunciados, propondo mecanismos e cientes para a otimização da utilização de recursos de redes configuradas com protocolos de encaminhamento Link State tradicionais, bem como em redes que implementam os mais recentes paradigmas de Software Defined Networking e Segment Routing. Para al em de possibilitarem uma utilização e ciente dos recursos, os mecanismos de otimização propostos são responsivos a altera coes relevantes no ambiente de rede que podem resultar de variações nos requisitos de trafego ou alterações de topologia. A natureza dos problemas, que para alem de não serem resolúveis em tempo polinomial incluem na sua formulação mais do que um objetivo de otimização, são abordados recorrendo a algoritmos da área da Computação Evolucionaria. Distintos requisitos de trafego e diferentes estados de rede exigem frequentemente configurações conflituantes. Os Algoritmos Evolucionários possuem varias características que são desejáveis para resolver problemas com múltiplos objetivos e que os torna preferíveis a métodos clássicos de otimização. Eles fornecem um conjunto de soluções de compromisso em problemas para os quais não existe uma solução ótima única. O trabalho de investigação concluiu numa ferramenta de otimização que integra todos os métodos de engenharia de trafego propostos, e que e disponibilizada para ser usada livremente por investigadores e administradores de rede.