Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-9QSG6B
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Thiago Ferreira de Noronha | pt_BR |
dc.contributor.referee1 | Andrea Cynthia Santos | pt_BR |
dc.contributor.referee2 | Mauricio Cardoso de Souza | pt_BR |
dc.contributor.referee3 | Sebastián Alberto Urrutia | pt_BR |
dc.creator | Daniel Brasil Magnani | pt_BR |
dc.date.accessioned | 2019-08-13T21:32:54Z | - |
dc.date.available | 2019-08-13T21:32:54Z | - |
dc.date.issued | 2014-06-18 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/ESBF-9QSG6B | - |
dc.description.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. | pt_BR |
dc.description.resumo | 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. | pt_BR |
dc.language | Inglês | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Ciência da Computação | pt_BR |
dc.subject.other | Pesquisa operacional | pt_BR |
dc.subject.other | Computação | pt_BR |
dc.subject.other | Heurística | pt_BR |
dc.title | Robust optimization for OSPF routing | pt_BR |
dc.type | Dissertação de Mestrado | pt_BR |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
danielbrasil.pdf | 1.22 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.