Encaminhamento dinâmico de túneis garantidos por largura de banda com restauração

Este artigo apresenta novos algoritmos para encaminhamento dinâmico de caminhos garantidos por largura de banda recuperáveis. Uma solução simples para o problema de restauração é encontrar dois caminhos disjuntos. No entanto, isso resulta em um uso excessivo de recursos para caminhos de backup e não satisfaz a exigência implícita do provedor de serviços de otimizar a utilização dos recursos da rede para aumentar o número de demandas futuras potenciais que podem ser roteadas. Apresentamos uma formulação de programação inteira para este problema que é nova. O conhecimento completo do encaminhamento de caminhos é uma suposição razoável para um algoritmo de roteamento centralizado. No entanto, requer a manutenção de informações não agregadas ou por caminho, o que muitas vezes não é desejável, especialmente quando o roteamento distribuído é preferido. Mostramos que um cenário de informação parcial que usa apenas informações agregadas e não por caminho fornece informações suficientes para que um algoritmo desenvolvido adequadamente consiga desempenhar quase tão bem quanto o cenário de informação completa. Nesse cenário de informação parcial, o algoritmo de roteamento só sabe qual fração da largura de banda de cada link está atualmente utilizada por caminhos ativos e atualmente utilizada por caminhos de backup. Obter essa informação é viável usando extensões propostas de engenharia de tráfego para protocolos de roteamento. Formulamos o problema de roteamento de largura de banda recuperável dinâmica nesse cenário de informação parcial e desenvolvemos algoritmos de roteamento eficientes. Comparamos o desempenho de roteamento desse algoritmo com um limite obtido usando informações completas. Nosso algoritmo baseado em informação parcial tem um desempenho muito bom e seu desempenho em termos do número de solicitações rejeitadas é muito próximo do limite de informação completa.