Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/38205
Type: | Dissertação |
Title: | Um algoritmo para projeto de redes hierárquicas |
Other Titles: | An algorithm for hierarchical network design |
Authors: | Frederico Rodrigues Borges da Cruz |
First Advisor: | Henrique Pacca Loureiro Luna |
First Referee: | Luiz Aurélio Raggi |
Second Referee: | Roberto Diéguez Galvão |
Third Referee: | Márcio Luiz Bunte de Carvalho |
Abstract: | A rede de alimentação de uma central telefônica é modelada como uma rede hierárquica. Nesse tipo de rede, um nó central (central telefônica) distribui fluxos a nós terminais com demanda (armários de distribuição), através de um conjunto de concentradores de demanda (estágios de linha remotos). É apresentado um algoritmo em três fases para o projeto da rede hierárquica. A primeira fase consiste em localizar os concentradores, através do problema das p-medianas com custos fixos. A cada concentrador corresponde uma rede, para a qual uma boa topologia é determinada na segunda fase, por meio de um problema de programação inteira mista, resolvido através de um procedimento de adição e substituição de arcos. Na terceira fase, usando-se um modelo similar, é feita a conexão dos concentradores ao nó central. Um sistema é implementado, para testes do algoritmo proposto. É apresentada a documentação do sistema, por meio de diagramas de fluxos de dados, dicionário de dados e diagramas hierárquicos dos módulos. Os resultados obtidos com o algoritmo proposto indicam que boas soluções para a rede hierárquica são determinadas, embora nem sempre as melhores. Redes de porte considerável são resolvidas (200 nós) e os resultados indicam que o tempo de processamento cresce rapidamente com o tamanho do problema. |
Abstract: | The primary network of a telephone switching center is presented as a hierarchical network. In such a network, a root node (switching center) distributes flows to terminal nodes (distribution boxes) via a set of demand concentrators. A 3-phase hierarchical network design algorithm is presented. First, the fixed-charge p-median problem formulation is used to locate the concentrators. For each concentrator's network, a good topology is obtained by solving a mixed integer programming problem through addition and interchange of arcs. The third phase uses a similar model to connect the concentrators to the root node. The proposed algorithm is implemented. Also presented are the data flow diagrams, data dictionary, and the module hierarchical diagrams of the implemented system. The 3-phase algorithm results show that good solutions can be obtained for the hierarchical network, in spite of not being the best. Large networks are solved (200 nodes) and the solutions show that the CPU time grows quickly with the problem size. |
Subject: | Computação Localização Otimização combinatória Planejamento Redes de computadores |
language: | por |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ |
URI: | http://hdl.handle.net/1843/38205 |
Issue Date: | 6-Aug-1991 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
MScFRBCruz.pdf | Dissertação de mestrado do discente F. R. B. Cruz | 7.72 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License