Projecto topológico de redes de comunicações: estudo e programação de algoritmos

Abstract

Com a evolução das redes de comunicações e das tecnologias a elas associadas torna-se cada vez mais importante proceder a um planeamento adequado das mesmas no sentido de garantir uma utilização eficiente dos recursos disponíveis. Com este objectivo têm vindo a ser desenvolvidas ferramentas de software que visam a optimização topológica de redes de comunicações. Estas ferramentas têm como base um conjunto de algoritmos, cujos objectivos de optimização são distintos. Nesta dissertação é feito um estudo e são programados os seguintes algoritmos: algoritmos para determinação de árvores abrangentes de comprimento mínimo sem restrições (Prim e Kruskal), árvores abrangentes de comprimento mínimo com restrições (Esau-Williams e Sharma), algoritmos para a determinação de percursos mínimos (Bellman-Ford e Dijkstra), localização de concentradores (algoritmo do centro de massa ADD e da decomposição), atribuição de terminais a concentradores (método óptimo), algoritmos para encaminhamento óptimo (desvio de fluxos e Bertesckas-Gallager) e atribuição de capacidades às ligações (método contínuo para atribuição de capacidades e método discreto - Serial Merge). É ainda estudado o algoritmo MENTOR para o projecto e optimização de redes em malha. Os algoritmos são integrados num pacote de software que se designou por ProNet. O ProNet tem uma interface amigável permitindo ilustrar de uma forma educativa o modo como os algoritmos funcionam. Isto é conseguido graças à possibilidade de o utilizador poder executar alguns dos algoritmos passo-a-passo e alterar os parâmetros das redes verificando a sua influência nos resultados finais. Este estudo é complementado no final com a aplicação destas ferramentas a um caso real de uma rede de comunicações. Foi seleccionado o caso de uma grande empresa bancária que pretende interligar todas as suas agências regionais usando uma rede privada de dados. Este problema de planeamento foi resolvido usando o ProNet e um pacote de software desenvolvido por outro autor.

The evolution of the network together with the associated technologies brings the need to create proper network planning techniques in order to ensure an efficient use of the available resources. In spite of this some network topology optimization software tools are currently under development. These tools are based in a set of algorithms that have different optimization objectives. Several algorithms were studied in this dissertation and among them we refer the no constrained minimum spanning tree (Prim and Kruskal algorithms), constrained minimum spanning tree (Esau-Williams and Sharma) concentrator location (center of mass, ADD and decomposition algorithms), shortest paths algorithms (Bellman-Ford and Dijkstra), terminal assignment (optimal algorithm), optimal routing (flow deviation and Bertsekas-Gallager algorithms) and capacity assignment (we have study continuous assignment and discrete assignment - Serial Merge). In addition the MENTOR algorithm was also studied, witch is a reasonable algorithm to optimize a mesh topology network. These algorithms were implemented and integrated in a software package named Pro el. The ProNet has a user friendly interface witch gives the possibility to run the algorithms in a step-by-step mode and analyze the intermediate results by changing same parameters and also their influence on the final results. This study is complemented with application of these tools to a real situation. A bank company that intends to interconnect all of the regional agencies through a private network was chosen. The planning of the network was performed with the ProNet and another package developed by other researcher.