Alocação de recursos com máxima conectividade em redes com topologia arbitrária

Abstract

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 da p-mediana em que é minimizada a soma das distâncias entre os clientes e seus recursos. Resultados experimentais usando redes de The Internet Topology Zoo avaliam o ganho de conectividade e o aumento da soma das distâncias quando a solução proposta é aplicada. Palavras-chave: Alocamento de Recursos, vértice-conectividade, localização de origens, pmediana.

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 this work 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 its feasibility for several arbitrary topology networks. This work presents a comparison between the connectivity based resource location problem with the classical p-median problem in which the sum of the distances between clients and their resources is minimized. Experimental results using networks from The Internet Topology Zoo show both the connectivity gains and the impact on the sum of the distances when the proposed solution is applied to real Internet-based networks. Keywords: Resource Allocation, vertex-connectivity, source location, p-median.