Dual-Ascent Distribuído para Multicast com Restrição de Saltos

Marcelo SantosLúcia M. A. DrummondEduardo UchoaLuidi Simonetti

The directed Steiner Problem consists in finding a minimum cost tree that reaches a subset of nodes of a graph from a root node r. It is frequently used to model the multicast routing problem. The number of hops between two nodes of a network can be used as an approximation for the communication latency between the nodes. So we have practical interest in the construction of a tree with limited height. In this case, we call the problem "Steiner Problem with Hop Constraint". This paper introduces a distributed heuristic to the Steiner Problem with Hop Constraint based on the algorithm "Dual Ascent" proposed by Wong [Wong 1984] and in the layered graph introduced by Gouveia and Uchoa [Gouveia et al. 2007]. We show experimental results where Dual Ascent gives better results than the best known algorithm for the problem.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: