Exploring ILP and heuristic formulations for planning multiband optical networks

Abstract

To keep up with the growth in traffic demands in nowadays optical telecommunications networks, solutions such as multiband and flexible grid are needed to improve spectrum efficiency and transmission capacity. This dissertation focuses on planning the routing and wavelength assignment (RWA) in multiband networks using both heuristic and integer linear programming (ILP) solutions to optimize the spectrum allocation. We develop C+L multiband network planning tools to solve the RWA problem in static networks, using flexible and fixed grids, exploring different routing metrics, such as distance and optical signal-to-noise ratio. First, we compare the performance of two RWA tools, a heuristic and an ILP, considering a fixed grid, in terms of the number of wavelengths and computation time, for different network topologies. Then, we extend our RWA heuristic tool to deal with the flexible grid and be aware of the physical layer impairments, to be capable of solving routing, modulation format and spectrum assignment (RMSA) problems. We have concluded that our RWA ILP achieves the optimum number of wavelengths, when it uses more than one candidate path per demand but requires more computing time than the RWA heuristic tool. In RMSA problems, the number of allocated frequency slots (FSs) is dependent on the bit error rate (BER). Networks with shorter links require more FSs as the BER decreases. Networks with longer links require less FSs as the BER decreases, since the blocked demands increase.

Para responder ao crescimento do número de pedidos de tráfego nas atuais redes de telecomunicações óticas, são necessárias soluções como a multibanda e grelha flexível para melhorar a eficiência na utilização do espectro e a capacidade de transmissão. Esta dissertação foca-se no planeamento do encaminhamento e da atribuição de comprimentos de onda (RWA) em redes multibanda utilizando soluções heurísticas e de programação inteira linear (ILP), para otimizar a alocação de espectro. Desenvolveram-se ferramentas de planeamento de redes multibanda C+L para resolver o problema RWA em redes estáticas, utilizando grelhas flexíveis e fixas, explorando diferentes métricas de encaminhamento, como a distância e relação ao sinal-ruido ́ótica. Primeiro, comparou-se o desempenho de ferramentas RWA, uma heurística e outra ILP numa grelha fixa, em relação ao número de comprimentos de onda e tempo de computação, para diferentes topologias de rede. Depois, adaptou-se a ferramenta RWA heurística para suportar a grelha flexível, considerando, as limitações da camada física, para resolver problemas de encaminhamento, atribuição de formato de modulação e espectro (RMSA). Concluiu-se que o RWA ILP atinge o número ótimo de comprimentos de onda, quando um pedido tem vários caminhos candidatos, contudo requer mais tempo de computação que a ferramenta heurística. Nos problemas RMSA, o número de intervalos de frequência (FSs) atribuídos depende da taxa de erro de bit (BER). Em redes com ligações mais curtas, são necessários mais FSs com a diminuição da BER. As redes com ligações mais longas requerem menos FSs com a diminuição da BER, pois os pedidos bloqueados aumentam.