Aspectos de dimensionamento de redes MPLS: optimização de nós e ligações

Abstract

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.

The present work addresses the problem of dimensioning MPLS based telecommunications networks. The problem considers the operator point of view that aims to determine the least cost physical network capable of routing a given traffic matrix. Both link and node dimensioning are considered. The overall solution is obtained by sequentially solving the two problems, which are modelled as Integer Linear Programming problems. The link dimensioning problem is, for realistic instances, too complex to be exactly solved. For this reason, heuristic techniques are being proposed in the literature to solve this problem in realistic computing times The use of heuristics raises the problem of assessing the quality of the obtained solutions: the quality of a solution is given by the percentual difference between the cost of the solution and a theoretical lower bound. Using a known link dimensioning heuristic, this work proposes and studies some methods to compute better lower bounds than the ones previously known to the solutions of the heuristic. The second addressed problem is the dimensioning of the telecommunications network’s nodes. This dimensioning is based on information obtained from the link dimensioning step (how many interfaces of which type to install on each link), on available network equipment (routers and network cards), purchasable or already installed. The solution to this problem indicates which routers and network cards must be purchased for each node, which must be transferred between nodes, which must be stored for future use and which – previously kept in storage – must be reused. It is proposed an Integer Linear Programming Model that describes this problem and achieves optimal solutions of realistic instances in short computing times. Finally, an MPLS network dimensioning tool integrating both link and node dimensioning is presented.