Dissertação
Algoritmos genéticos multiobjetivos aplicados ao roteamento multicast com qualidade de serviço
Registro en:
VITA, Stéfano Schwenck Borges Vale. Algoritmos genéticos multiobjetivos aplicados ao roteamento
multicast com qualidade de serviço. 2009. 123 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2009.
Autor
Vita, Stéfano Schwenck Borges Vale
Institución
Resumen
Multicast Routing is an effective way to communicate between multiple routers into computer
networks. In general, the quality of service (QoS) is required in most of multicast
applications. Several researchers have investigated the application of genetic algorithms in
multicast Routing with QoS restrictions. The evolutionary environments proposed in this
dissertation employ a multi-objective approach embracing the concept of Pareto Optimum to
solve the Routing calculus and to deal with several QoS metrics. Basically, four multiobjective
environments were built to solve the problem of multicast Routing with QoS. The
first was based on NSGA and the second was based on NSGA-II; they adopted the original
concept of Pareto dominance. The third multi-objective environment built is an adaptation of
NSGA-II which incorporates the e-dominance. The fourth environment is also an adaptation
of NSGA-II, but it employs a variation of e-dominance, the e -dominance. Five different pairs
of objective functions were evaluated: the first objective in each pair is related to the total
cost of a multicast route. The second objective accounted for: (i) the total delay of the
multicast tree, (ii) the average of accumulated delay from the source to each destination node,
(iii) the maximum accumulated delay from the source to each destination node and (iv) the
total number of routers in the multicast tree. Our results indicate an assessment of the four
multi-objectives environments. These algorithms were applied find routes in two network
topologies named REDE0 and REDE1. Mestrado em Ciência da Computação Roteamento multicast é uma maneira eficaz de se comunicar entre múltiplos roteadores em
redes de computadores. Geralmente, a Qualidade de Serviço (QoS) é exigida como garantia na
maior parte das aplicações multicast. Vários pesquisadores têm investigado a aplicação dos
Algoritmos Genéticos em roteamento multicast com restrições QoS. Os ambientes evolutivos
de roteamento que são propostos neste trabalho empregam uma abordagem multiobjetivos
adotando o conceito de Ótimo de Pareto para lidar com mais de uma métrica QoS.
Basicamente, foram construídos quatro ambientes com abordagem multiobjetivos para o
problema do roteamento multicast com QoS. O primeiro foi baseado no método NSGA, o
segundo foi baseado no método NSGA-II, sendo que esses ambientes adotam o conceito de
dominância de Pareto. O terceiro e quarto ambientes multiobjetivos construídos são
adaptações do NSGA-II, sendo que um deles incorpora a dominância-e e o outro uma variação
dessa, que denominamos dominância-e . Cinco diferentes pares de objetivos foram avaliados,
sendo que o primeiro objetivo utilizado em cada par está relacionado com o custo total de
uma rota multicast. Como segundo objetivo, são avaliados: (i) atraso total envolvido na árvore
multicast; (ii) a média do atraso acumulado a partir do nó origem a cada nó destino; (iii) o
atraso máximo acumulado desde o nó origem até um nó destino; (iv) o total de roteadores na
rota multicast. Duas topologias de rede extraídas da literatura, chamadas REDE0 e REDE1,
foram utilizadas para efetuar experimentos comparativos entre os ambientes multiobjetivos de
roteamento.