Aspectos de dimensionamento de redes MPLS: optimização de nós e ligações - Patrão, Jorge Miguel Barbosa
Esta dissertação estuda o problema do dimensionamento de redes de telecomunicações baseadas na tecnologia MPLS (MultiProtocol Label Switching). O problema estudado considera a perspectiva de um operador de telecomunicações que tem como objectivo a determinação da rede física de menor custo capaz de suportar o tráfego esperado. Neste trabalho considera-se tanto o dimensionamento das ligações entre nós como o dimensionamento dos equipamentos a instalar nos nós. Os dois problemas considerados são resolvidos sequencialmente, sendo cada um modelado como um problema de Programação Linear Inteira. O problema do dimensionamento das ligações é, para instâncias realistas, demasiado complexo para ser resolvido de forma exacta. Por esta razão, têm vindo a ser desenvolvidas heurísticas que produzam resultados satisfatórios em intervalos de tempo aceitáveis. No entanto, a aplicação de heurísticas levanta o problema da avaliação da qualidade das soluções obtidas: a qualidade da solução é medida através da diferença percentual entre o custo da solução obtida e um limite inferior teórico. Tomando como ponto de partida uma heurística conhecida de dimensionamento das ligações de redes de telecomunicações, este trabalho propõe e estuda alguns métodos com vista à determinação de melhores limites inferiores teóricos. Através dos métodos propostos, foi possível encontrar limites inferiores substancialmente melhores do que os anteriormente conhecidos para as soluções dadas pela heurística. O segundo problema abordado é o problema do dimensionamento dos nós da rede. Este dimensionamento é feito com base na informação sobre as ligações a instalar entre cada par de nós (i.e., a solução do problema do dimensionamento das ligações) e nos equipamentos de rede (routers e cartas de rede) existentes. A solução deste problema indica quais os equipamentos a adquirir para cada nó da rede, quais os que devem ser transferidos de um nó para outro e quais os equipamentos a armazenar para possível uso futuro. Neste trabalho é apresentado um modelo de Programação Linear Inteira que descreve o problema e que permite resolver instâncias realistas do mesmo de forma óptima em intervalos de tempo curtos. Finalmente, é apresentada uma ferramenta de dimensionamento de redes MPLS que integra o dimensionamento das ligações e dos nós da rede.