Posicionamento do Número Mínimo de Recursos que Maximizam Caminhos Vértice-Disjuntos em uma Rede de Topologia Arbitrária
Abstract
Resource placement is a problem that has several variants in computer networks, from server placement in the traditional client-server architecture to the allocation of controllers in SDN networks, or caches in CDN networks, among many others. This work presents the problem of placing the minimum number of resources in order to maximize the number of vertex-disjoint paths between a resource and its clients. One of the contributions of the paper is the proof that the problem of finding the minimum number of resources under these conditions is NP-complete. An exact solution to this problem was implemented and experiments showed it is feasibility when it was run in several arbitrary topology networks. We present results comparing the connectivity based resource location problem with the classic problem in which the sum of the distances between clients and their resources is minimized. Experimental results show both the connectivity gains and the impact on the sum of the distances when the proposed solution is applied.
References
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.
