On finding minimum cost tree for multi-resource manycast in mesh networks

We investigate the problem of multi-resource manycast in mesh networks. The problem of multi-resource manycast extends the traditional manycast problem or kk-Steiner tree problem, which finds a minimum cost tree spanning any kk vertices. For the traditional manycast, all the vertices in the set of candidate destinations will be regarded as identical. However, the computing capability of the resource at each vertex may be not equivalent in the realistic networks. In this paper, we consider the problem of multi-resource manycast, in which the computing capability of the resource at a vertex is decomposed into discrete units. That is, each vertex may have multiple units of computing resources. The objective is to find a minimum cost tree spanning any kk units of computing resources distributed in the networks. We show that multi-resource manycast is NP-Complete. The ILP formulation and approximation analysis are given for this problem. Simple polynomial-time heuristic algorithms are also proposed for the problem of multi-resource manycast. We investigate various approaches to implement multi-resources manycast in mesh networks, and verify the effectiveness of the approaches through simulation.