Dimensionamento de redes ATM multi-serviço : modelos de programação linear inteira

Abstract

Esta tese aborda o problema do dimensionamento de redes ATM (Asynchronous Transfer Mode) num cenário multi-serviço de suporte a serviços com diferentes características de tráfego: serviços conversacionais, serviços de consulta e serviços ponto-multiponto. O problema estudado considera a perspectiva de um operador de telecomunicações que tem como objectivo a determinação da rede física com o menor custo de operação e manutenção possível e que seja capaz de suportar o tráfego esperado para os diferentes serviços com a qualidade de serviço necessária. Os problemas de dimensionamento abordados consideram serviços comutados em que cada serviço é suportado por uma rede lógica constituída por VPCs (Virtual Path Connections) do tipo DBR (Deterministic Bit Rate) e o encaminhamento é fixo (uni-horário e multi-horário). O primeiro problema endereçado é o dimensionamento de redes ATM em que as redes lógicas de suporte a todos os tipos de serviços são constituídas exclusivamente por VPCs extremo-a-extremo. Esta arquitectura tem como principal vantagem a simplificação dos mecanismos de CAC (Call Admission Control) da rede. São propostos modelos de Programação Inteira para este problema. Os modelos desenvolvidos extendem modelos previamente conhecidos para serviços conversacionais de modo a poder ser considerado tráfego assimétrico (característico dos serviços de consulta e serviços pontomultiponto) e a modelização de VPCs em que um dos extremos não é conhecido à partida (característico dos serviços de consulta quando existem múltiplos servidores na rede). É proposto um algoritmo heurístico baseado na técnica da Relaxação Lagrangeana com Optimização por Sub-Gradiente para a resolução dos modelos desenvolvidos em redes de grande dimensão. No entanto, uma arquitectura baseada em VPCs extremo-a-extremo conduz a uma utilização pouco eficiente dos recursos da rede e, para redes de maiores dimensões, torna-se impraticável pelo elevado número de VPCs que exige. Como alternativa, são propostas duas arquitecturas diferentes. Para serviços conversacionais, é proposta uma arquitectura hierarquizada a 2 níveis para as redes lógicas de suporte. Esta arquitectura permite reduzir significativamente o número total de VPCs que é necessário configurar na rede sem contudo permitir que o número máximo de VPCs atravessados por cada ligação seja maior que três (um factor determinante para serviços comutados em que o tempo de estabelecimento de chamada é um parâmetro de qualidade de serviço a ter em consideração). Para serviços ponto-multiponto, é proposta uma arquitectura em árvore para as redes lógicas de suporte. São propostos modelos de Programação Inteira e Programação Inteira Mista para os problemas de dimensionamento da rede com as redes lógicas segundo as arquitecturas propostas. A resolução dos modelos propostos através de um algoritmo de branch-and-bound permite demonstrar que as arquitecturas alternativas propostas conduzem a ganhos significativos nos custos das redes obtidas quando comparados com os custos que se obtêm com redes lógicas baseadas em VPCs extremo-a-extremo.