Algebraic formulation for modeling hop-by-hop multi-constrained routing algorithms.

Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho.This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation