Um algoritmo GRASP para o Problema da Árvore de Steiner em Grafos como Suporte ao Roteamento Multicast (A GRASP for the Steiner Tree Problem in Graphs to Support Multicast Routing)

Calvin Rodrigues Costa (calvin.costa@unifesp.br)1, Valério Rosset (vrosset@unifesp.br)1, Mariá Cristina Vasconcelos Nascimento (mcv.nascimento@unifesp.br)1


1Universidade Federal de São Paulo

This paper appears in: Revista IEEE América Latina

Publication Date: Dec. 2015
Volume: 13,   Issue: 12 
ISSN: 1548-0992


Abstract:
In computer networks, multicast routing is that in which a single message is transmitted to multiple recipients from a subset of devices, called multicast group. To address the multicast routing problem, it is usual to model the computer network as a graph. In line with this, some strategies aim at building a routing tree that minimizes the total costs of transmission between the vertices of the routing tree that contains the multicast group, the Steiner tree. However, in large scale applications, local-based strategies may be a better alternative, since they can also be easily adapted to tackle distributed systems. In the literature, to the extent of our knowledge, to construct approximate Steiner tree using this type of approach remains a challenge. In this paper, we present a neighborhood-based metaheuristic to find an approximate solution for the Steiner tree in graphs. In the computational experiments, we used benchmark instances of small, medium and large scales and compared the results achieved by the proposed strategy with the best found so far. In addition, we analyze a real word instance for which the proposed algorithm has obtained good performance.

Index Terms:
Multicast Routing, Steiner Tree, GRASP   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (426)]