Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLBS-6GVFBC| Type: | Tese de Doutorado |
| Title: | Um arcabouço para roteamento em redes MPLS |
| Authors: | Adriana de Andrade Oliveira |
| First Advisor: | Geraldo Robson Mateus |
| First Referee: | Celso da Cruz Carneiro Ribeiro |
| Second Referee: | José Augusto Suruagy Monteiro |
| Third Referee: | Antonio Alfredo Ferreira Loureiro |
| metadata.dc.contributor.referee4: | Jose Marcos Silva Nogueira |
| Abstract: | Esse trabalho trata do problema de seleção de rotas físicas para LSPs (Label Switching Paths) em redes MPLS (Multi-Protocol Label Switching). Esse problema consiste na definição de rotas para os LSPs que minimizem o número total de saltos e o número total de rejeições. O problema é tratado através de duas estratégias diferentes: on-line e offline. Inicialmente propomos um modelo linear inteiro para solucionar o problema de maneira exata. Esse modelo tenta balancear a carga na rede enquanto minimiza a taxa de rejeição. O objetivo é otimizar o desempenho global da rede roteando as requisições através de enlaces sub-utilizados melhorando a utilização da infra-estrutura instalada.Há vários problemas relacionados com o tempo necessário para resolver o modelo e por isso desenvolvemos um algoritmo genético, baseado na combinação de políticas de roteamento e movimentos adaptativos de rotas.Para analisar o desempenho do algoritmo genético, foram estudados vários cenários e foram feitas várias simulações. Os resultados mostram que o algoritmo genético executa muito mais rápido que a ferramenta comercial utilizada para resolver o model de forma exata. Os resultados também mostram que o uso do algoritmo genético diminui consideravelmente a quantidade de requisições rejeitadas na rede.Foram executados vários experimentos e resultados satistatórios foram encontrados, mostrando que o algoritmo genético é também apropriado para roteamento on-line. Além do caso clássico de chegada de novas requisições, esse trabalho também trata do problema de ajuste do roteamento em diversos outros casos. Chamamos de Grooming esse processo de ajuste do roteamento da rede e ele ocorre quando um novo elemento de rede é configurado, LSPs são terminados ou elementos de rede se recuperam de falhas. O Grooming da rede é necessário quando decições de roteamento tomadas no passado não são mais eficientes.Um mecanismo de detecção de mudanças é proposto para engatilhar o processo de Grooming. Esse mecanismo é baseado em cartas de controle e é usado para definir o momento em que o Grooming deve acontecer. Resultados de simulação indicam que um melhor desempenho é alcançado através do uso dos mecanismos propostos. |
| Abstract: | This work addresses the problem of physical route selection for Label Switched Paths (LSPs) in Multi-Protocol Label Switching (MPLS) networks. It consists of defining routes for LSPs trying to minimize the total number of hops and the total number of rejections. The LSPs path selection problem is addressed through two different approaches: on-line and offline. We propose an ILP (Integer Linear Programming) model to solve the offline problem in an exact manner. This model tries to balance the network load while minimizing the network rejection rate. The goal is to optimize the overall network performance by routing requests through under-utilized links. Issues concerning the execution time necessary to solve the model are noticed and a genetic algorithm (GA) is developed to address theses issues. The GA is based on the combination of routing policies and adaptive route movements. In order to analyze the genetic algorithm's performance, various simulations are conducted. Results show that the GA executes much faster than the commercial tool used to solve the model in an exact manner. Results also show that the use of the GA considerably decreases the amount of rejected requests in the network. Experiments are conducted and satisfactory results are found showing that the GA is also suitable for on-line routing. This work also addresses the problem of adjusting the network routingin other cases besides the arrival of new requests. The process ofadjusting the network routing is called Grooming and it occurs when a new network element is configured, LSPs are torn down or a network element recovers from failure. It is necessary when routing decisions taken in the past are no longer efficient. A traffic/resource change detection mechanism is proposed to trigger the Grooming process. This mechanism is based on control charts and is used in the context of defining the moment the Grooming should take place. Simulation results indicate that better performance is achieved using the proposed mechanisms. |
| Subject: | Computação Redes de computação Qualidade dos produtos Redes de computação Protocolos Engenharia de tráfego Telecomunicações Tráfego |
| language: | Português |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/SLBS-6GVFBC |
| Issue Date: | 3-Oct-2005 |
| Appears in Collections: | Teses de Doutorado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| adriana_andrade_oliveira.pdf | 882.71 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.