Cálculo de um par de caminhos maximamente disjuntos ou de um par de caminhos disjuntos nas avarias, de custo aditivo mínimo

Abstract

Atualmente, com o crescente volume de tráfego em redes de telecomunicações, é de extrema importância a proteção das ligações ponto a ponto estabelecidas ao longo da rede, com o objetivo de evitar interrupções de serviço. Um SRLG (Shared Risk Link Group) é um conjunto de elementos da rede que têm um risco comum de falha. Os protocolos de encaminhamento podem distribuir informação acerca dos SRLG que podem afetar cada arco da rede, pelo que se torna importante o desenvolvimento de algoritmos eficientes para a determinação de caminhos disjuntos ou maximamente disjuntos nos SRLG. Um par de caminhos disjuntos nas avarias é um par de caminhos totalmente disjuntos ou que podem ter em comum elementos resilientes, ou seja que estão protegidos numa camada inferior. No presente trabalho, desenvolvido no âmbito de um contrato de I&D com a PT Inovação, foram estudados e implementados vários algoritmos: em primeiro lugar um algoritmo de cálculo de um par de caminhos maximamente disjuntos nos nós, de custo aditivo mínimo, que garante que a solução obtida é ótima; em segundo lugar três algoritmos de cálculo de um par de caminhos maximamente disjuntos nos nós e nos SRLG. Cada um desses três algoritmos, propostos no âmbito deste trabalho, são extensões/adaptações de heurísticas para a determinação de pares de caminhos disjuntos nos SRLG; finalmente foi implementada uma heurística, que procura obter um par de caminhos totalmente disjuntos nos nós, exceto em nós extremos de arcos resilientes partilhados por esse par de caminhos. Os algoritmos foram desenvolvidos tendo em vista a sua utilização em PCE (Path Computation Element) integrados em equipamentos de redes GMPLS (Generalized Multiprotocol Label Switching). Dado que os PCE integrados têm tipicamente recursos computacionais (capacidade de processamento e quantidade de memória) limitados, procurouse otimizar os algoritmos implementados. Foram realizados testes de desempenho das rotinas implementadas, tendo-se verificado que o algoritmo de cálculo de um par de caminhos maximamente disjuntos nos nós, de custo aditivo mínimo, é perfeitamente adequado ao PCE utilizado nos testes. As implementações dos algoritmos de cálculo de um par de caminhos maximamente disjuntos nos nós e nos SRLG, mostraram poder ser utilizadas num PCE no plano de controlo desde que o número de iterações permitido fosse limitado. A última heurística desenvolvida poderá ser utilizada num PCE apenas no plano de gestão uma vez que os tempos de execução não são compatíveis com a sua utilização no plano de controlo, para a rede fornecida pela PT Inovação.

Nowadays telecommunication networks face an increasing demand of traffic volume and an increasing need to provide an adequate quality of the service experienced by the users. Therefore the protection of point-to-point connections throughout the network becomes of the utmost importance, in order to avoid service interruptions. A SRLG (Shared Risk Link Group) is a set of network elements with common risk of failure. The routing protocols can consider the information on the SRLG affecting each network link. Therefore, the development of efficient algorithms for the calculation of SRLG-disjoint (or at least maximally disjoint) paths becomes a critical issue in this context. A failure-disjoint path pair is a path pair which is either totally disjoint or only has in common resilient elements (i.e. protected in a lower layer). In this work, which was developed in the context of a R&D contract with PT Inovação, several algorithms were studied and implemented: firstly, an algorithm for the calculation of a maximally node-disjoint path pair of min-sum cost, which guarantees finding an optimal solution; secondly, three algorithms for the calculation of a maximally node and SRLG-disjoint path pair, which are adaptations/extensions of existing heuristics for the calculation of a totally SRLG-disjoint path pair; lastly, a heuristic to calculate a pair of totally node-disjoint paths, except for extreme nodes of resilient links that are shared by that path pair. The algorithms were developed having in mind that they will be used in a PCE (Path Computation Element) in GMPLS (Generalized Multiprotocol Label Switching) networks devices, which are usually very limited in terms of computational resources (processing and memory). Some performance tests for comparison of the implemented algorithms were made. The algorithm for the calculation of maximally node-disjoint path pairs of min-sum cost is suitable for the considered PCE. As for the algorithms for the calculation of maximally node and SRLG-disjoint path pairs, they can be used in a PCE as long as the number of allowed iterations is adequate. The heuristic for the calculation of failure-disjoint path pairs can be used in a PCE but only in a management plane due to its long execution time.