Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLBS-5RVS3L
Type: | Tese de Doutorado |
Title: | Modelos e algoritmos para problemas de atribuição de capacidade e roteamento em redes de comunicação |
Authors: | Ricardo Poley Martins Ferreira |
First Advisor: | Henrique Pacca Loureiro Luna |
First Referee: | Geraldo Robson Mateus |
Second Referee: | José Augusto Suruagy Monteiro |
Third Referee: | Rodney Rezende Saldanha |
Abstract: | O problema conjunto de determinar rotas e as capacidades de cada arco em uma rede de comunicações é tratado. Uma abordagem alternativa para alguns modelos que foram propostos para o problema de atribuição de capacidades discretas e contínuas e roteamento em redes de computadores é adotada. A topologia da rede e as características de tráfego são considerados como sendo dados conhecidos. O objetivo é obter uma solução viável com o mínimo custo total, onde o custo total inclui tanto os custos de instalação de capacidade quanto os custos de congestionamento. Algoritmos heurísticos com desempenho garantido baseados em limites inferiores e na separabilidade da função objetivo são propostos. Um destes algoritmos é adaptado para considerar problemas com roteamento não-bifurcado. Um algoritmo exato baseado no método de enumeração implícita é proposto para resolver o problema de expansão de capacidade. Experimentos foram realizados para verificar o desempenho e confirmar a eficiência dos algoritmos propostos. |
Abstract: | The joint problem of selecting routing and a capacity for each link in a communication network is considered. We apply an alternative approach for some models that have been addressed for computer networks discrete capacity allocation and routing problems. The network topology and trac characteristics are assumed to be given. The goal is to obtain a feasible solution with minimum total cost, where the total cost include both leasing capacity and congestion costs. Heuristic algorithms withperformance guarantees based on lower bounds and on the separability of the objective function are proposed. A heuristic algorithm is proposed to solve the problem with nonbifurcated routing constraints. An implicit enumeration approach is proposed to solve exactly the capacity expansion problem with two capacity levels for each channel. Experiments were conducted to verify the performance and to conrmthe eciency of the proposed algorithms. |
Subject: | Algoritmos Otimização matemática Pesquisa operacional Redes de comunicação Programação heuristica |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLBS-5RVS3L |
Issue Date: | 27-Mar-2003 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ricardo_poley.pdf | 1.12 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.