Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/ESBF-9QSG6B
Type: Dissertação de Mestrado
Title: Robust optimization for OSPF routing
Authors: Daniel Brasil Magnani
First Advisor: Thiago Ferreira de Noronha
First Referee: Andrea Cynthia Santos
Second Referee: Mauricio Cardoso de Souza
Third Referee: Sebastián Alberto Urrutia
Abstract: No protocolo OSPF, dado um conjunto de pesos para cada link, os dados são roteados através do menor caminho entre o remetente e o destinatário. O problema da atribuição de pesos OSPF consiste em definir os pesos dos links de uma rede de computadores, de tal forma que o roteamento resulte na rede menos congestionada possível. A maioria dos trabalhos da literatura assumem que uma única matriz de demanda estática está disponível. Entretanto, o tráfego em redes de computadores pode variar significativamente em diferentes momentos de tempo, e não é prático para o administrador da rede mudar manualmente os pesos dos links toda vez que uma variação significativa ocorrer. Estes fatores motivaram o desenvolvimento de modelos de otimização para o problema que lidam com incerteza no tráfego. Ao invés de minimizar o congestionamento médio em relação aos vários cenários, como é o caso dos trabalhos da literatura, nós propomos um novo modelo de otimização, baseado em Otimização Robusta, onde o congestionamento em cada cenário é considerado individualmente. Nós argumentamos que o usuário enxerga cada cenário individualmente. Portanto, uma solução que é boa na média pode resultar numa qualidade de serviço ruim na perspectiva do usuário. Experimentos computacionais, realizados em redes realísticas e artificiais, mostram que, comparado à abordagem que minimiza o caso médio, nossa abordagem consegue reduzir o arrependimento em 25%, enquanto aimenta o congestionamento médio em apenas 0,72%, indicando que nossa abordagem pode ser uma alternativa melhor para a atribuição de pesos OSPF.
Abstract: On OSPF protocol, given a et of weights for each link, the data are routed through the shortest paths between the sender and the receiver. The OSPF weight setting problem consists in defining the assignment of link weights such that the respective shortest path routing results in the least congested network. Most of the works in the literature assume that a single static demand matrix is available. However, the traffic on computer networks may significantly vary in different periods of time, and it is not practical for the network operator to manually change the weights of the links each time significant variation in traffic occurs. These factors motivated the development of optimization models for OSPF weight setting that deal with traffic uncertainties. Instead of minimizing the average congestion over all scenarios as is the case of the works in the literature, we propose a new optimization models, based on Robust Optimization, where the congestion in each scenario is considered individually. We argue that the user experiences each scenario individually. Therefore, a solution that is good on average may sometimes result in a bad quality-of-service from the user point of view. Computational experiments, performed on realistic and artificial instances, show that, compared to the approach that minimizes the average case, our approach is able to reduce the congestion regret by 25%, while increasing the average congestion by only 0,72%, indicating that our approach may be a better alternative for weight setting in OSPF networks.
Subject: Pesquisa operacional
Computação
Heurística
language: Inglês
Publisher: Universidade Federal de Minas Gerais
Publisher Initials: UFMG
Rights: Acesso Aberto
URI: http://hdl.handle.net/1843/ESBF-9QSG6B
Issue Date: 18-Jun-2014
Appears in Collections:Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
danielbrasil.pdf1.22 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.