Posicionamento do Número Mínimo de Recursos que Maximizam Caminhos Vértice-Disjuntos em uma Rede de Topologia Arbitrária

  • Henrique Hepp
  • Jaime Cohen
  • Elias P. Duarte Jr.

Resumo


O posicionamento de recursos em redes é um problema que encontra diversas variantes, desde o posicionamento de servidores na arquitetura tradicional cliente-servidor, passando pelo posicionamento de controladores em redes SDN, ou caches em redes CDN, entre vários outros. Este trabalho apresenta o problema de posicionar o número mínimo de recursos de modo a maximizar o número de caminhos vértice-disjuntos entre um recurso e seus clientes. Uma das contribuições do trabalho é a prova de que o problema de encontrar o número mínimo de recursos sob essas condições é NP-completo. Uma solução exata para o problema foi implementada e sua execução se mostrou viável em diversas redes de topologia arbitrária. Apresentamos os resultados comparando-os com o problema clássico em que é minimizada a soma das distâncias entre os clientes e seus recursos. Resultados experimentais avaliam o ganho de conectividade e o aumento da soma das distâncias quando a solução proposta é aplicada.
Publicado
10/05/2018
Como Citar

Selecione um Formato
HEPP, Henrique; COHEN, Jaime; JR., Elias P. Duarte. Posicionamento do Número Mínimo de Recursos que Maximizam Caminhos Vértice-Disjuntos em uma Rede de Topologia Arbitrária. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC) , 2018 Anais do XXXVI Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos. Porto Alegre: Sociedade Brasileira de Computação, may 2018 . ISSN 2177-9384.