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

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

DOI: https://doi.org/10.5753/sbrc.2018.2465

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.

Referências

Bae, M. M. (1997). Resource placement in torus-based networks. IEEE Transactions on Computers, 46(10):1083–1092.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.

Heller, B., Sherwood, R., and McKeown, N. (2012). The Controller Placement Problem. ACM SIGCOMM Computer Communication Review, 42(4):473.

Ito, H., Ito, M., Itatsu, Y., Nakai, K., Uehara, H., and Yokoyama, M. (2002). Source Location Problems Considering Vertex-Connectivity and Edge-Connectivity Simultaneously. Networks, 40(2):63–70.

Li, B., Golin, M. J., Italiano, G. F., Deng, X., and Sohraby, K. (1999). On the optimal placement of web proxies in the internet. In INFOCOM 1999, volume 3, pages 1282–1290. IEEE.

Makino, K. (2012). Source Location Problems with Flow Requirements. 2012 Third International Conference on Networking and Computing, pages 404–406.

Muller, L. F., Oliveira, R. R., Luizelli, M. C., Gaspary, L. P., and Barcellos, M. P. (2014). Survivor: An Enhanced Controller Placement Strategy for Improving SDN Survivability. In 2014 IEEE Global Communications Conference, GLOBECOM 2014, pages 1909–1915.

Pires, K., Cohen, J., and Duarte Jr., E. P. (2011). Medidas de conectividade baseadas em cortes de vertices para redes complexas. In 12 Workshop de Testes e Tolerância a Falhas (WTF’2011), Anais do SBRC’2011.

Qiu, L., Padmanabhan, V. N., and Voelker, G. M. (2001). On the placement of web server replicas. In INFOCOM 2001, volume 3, pages 1587–1596. IEEE.

Rao, W., Chen, L., Fu, A. W.-C., and Wang, G. (2010). Optimal resource placement in structured peer-to-peer networks. IEEE Transactions on Parallel and Distributed Systems, 21(7):1011–1026.

Reese, J. (2006). Solution methods for the p-median problem: An annotated bibliography. Networks, 48(3):125–142.

Rochman, Y., Levy, H., and Brosh, E. (2013). Resource placement and assignment in distributed network topologies. In INFOCOM 2013, pages 1914–1922. IEEE.

Rodolakis, G., Siachalou, S., and Georgiadis, L. (2006). Replicated server placement with qos constraints. IEEE Transactions on Parallel and Distributed Systems, 17(10):1151–1162.

Sahoo, J., Salahuddin, M., Glitho, R., Elbiaze, H., and Ajib, W. (2017). A Survey on Replica Server Placement Algorithms for Content Delivery Networks. IEEE Communications Surveys & Tutorials, 19(2):1002–1026.

Younis, M. and Akkaya, K. (2008). Strategies and techniques for node placement in wireless sensor networks: A survey. Ad Hoc Networks, 6(4):621–655.