Optical network planning for static applications

Abstract

Traffic demands on optical transport networks continue to grow, both in numbers and in size, at an incredible rate. Consequently, the efficient use of network resources has never been as important as today. A possible solution to this problem is to plan, develop and implement efficient algorithms for static and/or dynamic applications in order to minimize the probability of blocking and/or minimizing the number of wavelengths. Static Routing and Wavelength Assignment (RWA) algorithms use a given set of optical path requests and are intended to provide a long-term plan for future traffic. Static RWA algorithms are important for current and future WDM (Wavelength-Division Multiplexing) networks, especially when there is no wavelength conversion, the network is highly connected or the traffic load is moderate to high. In this dissertation, we propose to develop an optical network planning tool capable of choosing the best optical path and assigning as few wavelengths as possible. This tool is structured in five phases: in the first phase, the network physical topology is defined by the adjacency matrix or by the cost matrix and the logical topology is defined by the traffic matrix; in a second phase, the Dijkstra algorithm is used to find the shortest path for each connection; in the third phase, the traffic routing is accomplished considering one traffic unit between the source and destination nodes; in the fourth phase, the paths are ordered using various ordering strategies, such as Shortest Path First, Longest Path First and Random Path Order; finally, in the fifth phase, the heuristic algorithms for wavelength assignment, such as Graph Coloring, First-Fit and Most-Used are used. This tool is first tested on small networks (e.g. ring and mesh topologies), and then applied to real networks (e.g. COST 239, NSFNET and UBN topologies). We have concluded that the number of wavelengths calculated for each network is almost independent of the Wavelength Assignment (WA) heuristics, as well as the ordering strategy, when a full mesh logical topology is considered.

Os pedidos de tráfego nas redes de transporte ópticas continuam a crescer, tanto em número como em tamanho, a um ritmo incrível. Consequentemente, a utilização eficiente dos recursos das redes nunca foi tão importante como hoje. Uma solução possível para este problema passa por planear, desenvolver e implementar algoritmos eficientes para aplicações estáticas e/ou dinâmicas de modo a minimizar a probabilidade de bloqueio e/ou minimizar o número de comprimentos de onda. Os algoritmos de encaminhamento e de atribuição de comprimentos de onda (RWA) estáticos utilizam um determinado conjunto de pedidos de caminhos ópticos e visam fornecer um plano de longo prazo para tráfego futuro. Os algoritmos RWA estáticos são importantes para as redes em multiplexagem por divisão de comprimento de onda (WDM) atuais e futuras, especialmente quando não há conversão de comprimento de onda, a rede é altamente ligada ou a carga de tráfego é de moderada a alta. Nesta dissertação, propomos desenvolver uma ferramenta de planeamento de redes ópticas capaz de escolher o melhor caminho óptico e atribuir o mínimo de comprimentos ondas possíveis. Esta ferramenta está estruturada em cinco fases: numa primeira fase é definida a topologia física de rede pela matriz das adjacências ou pela matriz de custo e a topologia lógica é definida pela matriz de tráfego; numa segunda fase é utilizado o algoritmo Dijkstra para encontrar o caminho mais curto para cada ligação; na terceira fase o encaminhamento de tráfego é realizado considerando uma unidade de tráfego entre os nós de origem e destino; na quarta fase os caminhos são ordenados tendo em conta as várias estratégias de ordenação, tais como Shortest Path First, Longest Path First e Random Path Order; finalmente, na quinta fase, os algoritmos heurísticos são utilizados para atribuição de comprimentos de onda, como Graph Coloring, First-Fit e Most-Used. Esta ferramenta é primeiramente testada em redes pequenas (por exemplo, topologias em anel e em malha), e depois é aplicada a redes reais (por exemplo, redes COST 239, NSFNET e UBN). Concluímos que o número de comprimentos de onda calculados para cada rede é quase independente da heurística para atribuição dos cumprimentos de onda, bem como da estratégia de ordenação dos caminhos, quando uma topologia lógica em malha completa é considerada.