Localização de monitores em redes de telecomunicações

Abstract

Nesta tese estudamos o problema da monitorização de redes que consiste na melhor escolha de nós para a instalação de dispositivos que efetuem a monitorização da rede. Começamos por considerar a versão na qual os caminhos de fluxo da rede são conhecidos. Neste caso o problema pode ser visto como um problema de cobertura no qual temos de cobrir todos os caminhos da rede por nós, que correspondem à localização dos dispositivos de monitorização. São também consideradas duas variantes do problema. Uma variante impõe um limite na capacidade de monitorização de cada dispositivo. Outra variante considera antes uma monitorização da quantidade de fluxo da rede (em vez dos caminhos). Apresentamos uma formulação em programação linear inteira para cada variante e um estudo computacional onde os vários parâmetros do problema variam. Nomeadamente efetuamos a variação do número de caminhos, do número de nós e dos custos de instalação dos monitores. Usando o software Xpress obtemos soluções que nos permitem avaliar a quantidade de dispositivos necessários em função do número de caminhos ou quantidade de fluxo da rede. Apresentamos conclusões tendo em conta o tempo computacional e a qualidade da solução obtida através das relaxações lineares dos modelos apresentados. No final consideramos a versão na qual os caminhos efetuados pelo fluxo na rede não são conhecidos. Apresentamos uma formulação em programação linear inteira para o problema e, usando o software Xpress, obtemos soluções para alguns exemplos.

In this thesis we study the network monitoring problem which is the best selection of nodes for locating monitoring devices on the network. We begin by considering the version in which the flow paths of the network are known. In this case the problem can be seen as a set covering problem in which we cover all the paths of the network with nodes, which correspond to the location of the monitoring devices. Two variants of the problem are also considered. A variant imposes a limit on the capacity of each monitoring device. Another considers the monitoring of the amount of flow of the network (instead of paths). We present a integer linear programming formulation for each variant and a study where various computational parameters of the problem varies. In particular we make the change in the number of paths, the number of nodes and the installation costs of the monitors. Using the software Xpress, the obtained solutions allow us to assess the number of devices needed, the number of routes or amount of network flow. We present conclusions regarding the computational time and the quality of the solution obtained via linear relaxations of the presented models. At the end we consider the version in which the flow paths in the network is not known. We present an integer linear programming formulation for the problem and, using the Xpress software, we obtain solutions to some examples.