Cálculo de caminhos disjuntos nos nós e nos SRLG, de custo aditivo mínimo, para utilização num PCE

Abstract

Os operadores de telecomunicações sentem cada vez mais a necessidade de melhorar a fiabilidade e disponibilidade dos serviços oferecidos. A utilização de mecanismos de proteção, entre os quais se inclui a proteção global ao caminho, contribui para atingir esses objetivos. Essa proteção pode ser conseguida determinando pares (ou conjuntos) de caminhos disjuntos. A versatilidade que o Generalized Multiprotocol Label Switching (GMPLS) apresenta ao nível do plano de controlo, permite a implementação de mecanismos automáticos de proteção. A distribuição, pelos protocolos de encaminhamento, de informação relativa aos Shared Risk Link Group (SRLG) – grupo de ligações que partilham um risco de falha – torna possível a determinação de caminhos disjuntos nos SRLG, capazes de resistir a falhas múltiplas (desencadeadas pela falha associada a um dado risco). Os Path Computation Elements (PCE) que calculam caminhos numa rede GMPLS, podem dispor de poucos recursos (velocidade e memória). Foram estudados e implementados algoritmos eficientes de determinação de pares de caminhos disjuntos (e um algoritmo de determinação de um conjunto de K caminhos disjuntos) nos nós, de custo aditivo mínimo. Na implementação realizada procurou-se minimizar a utilização da memória sem comprometer a velocidade de execução, definindo uma representação para a rede baseada na Reverse and Foward Star Form (RFSF), adequada à transformação da rede requerida por estes algoritmos. A determinação de um par de caminhos disjuntos nos SRLG é um problema NPcompleto. Foram descritas e implementadas duas heurísticas, Iterative Modified Suurballe’s Heuristic (IMSH) e Confliting SRLG Exclusion-Min Sum (CoSE-MS), para a determinação de pares de caminhos disjuntos nos nós e nos SRLG, de custo aditivo mínimo; foram ainda apresentadas duas novas variantes do CoSE-MS que são ligeiramente mais eficientes que a versão original. Subjacente a este trabalho, esteve sempre o objetivo de obter uma biblioteca partilhada (.so) adequada para utilização num sistema embebido, em particular na placa UNICOMV5. Os testes realizados demonstraram que as rotinas implementadas para o cálculo de caminhos disjuntos nos nós eram perfeitamente adequadas a este ambiente. As duas novas variantes do algoritmo CoSE-MS mostraram ser um bom compromisso entre eficiência computacional e precisão. A heurística IMSH mostrou ser mais adequada para um ambiente de gestão de rede, dada a sua precisão à custa de um maior tempo de execução.

Telecom operators are increasingly feeling the need to improve the reliability and availability of the offered services. One way to achieve this goal is the use of protection mechanisms, among which is global path protection. Such protection can be achieved by determining pairs (or sets) of disjoint paths. The versatility of the Generalized Multiprotocol Label Switching (GMPLS) control plan, allows the implementation of automated protection. The distribution by routing protocols of information about Shared Risk Link Groups (SRLGs) – a group of links that share a risk of failure – makes it possible to determine SRLG disjoint paths, able to withstand multiple failures (triggered by a failure associated with a given risk). The Path Computation Elements (PCEs) which compute paths in a GMPLS network, may have limited resources (CPU and memory). Efficient algorithms for determining pairs of disjoint paths (and an algorithm for determining a set of disjoint paths K), with minimal additive cost, were studied. The implementation of these algorithms sought to minimize memory usage without compromising execution speed, which required the definition of a network representation based on Forward and Reverse Star Form (RFSF), suitable for the network transformation required by the algorithms. The determination of a pair of SRLG disjoint paths is NP-complete. Two heuristics, Iterative Modified Suurballe’s Heuristic (IMSH) and Confliting SRLG Exclusion-Min Sum (CoSE-MS) for determination of SRLG disjoint path pairs, of minimum cost additive, were described and implemented; two new variants of COSE-MS, which are slightly more efficient than the original version, were also presented. The underlying aim of this work has always been producing a shared library (.so) suitable for using in an embedded system, in particular on the UNICOM-V5 board. The tests showed that the routines implemented for the calculation of disjoint paths were perfectly suited to this environment. The two new variants of CoSE-MS algorithm proved to be a good compromise between computational efficiency and accuracy. The heuristic IMSH was shown to be more appropriate for network management due to its accuracy and higher computacional time.