Optimización multiobjetivo para enrutamiento multicast en overlay networks utilizando algoritmos evolutivos

Multiobjective Optimization for Multicast Routing in Overlay Networks using Evolutionary Algorithms

Multicast juega un papel muy importante para soportar una nueva generación de aplicaciones. En la actualidad y por diferentes razones, técnicas y no técnicas, multicast IP no ha sido totalmente adoptado en Internet. Durante los últimos años, un área de investigación activa es la de implementar este tipo de tráfico desde la perspectiva del nivel de aplicación, donde la funcionalidad de multicast no es responsabilidad de los enrutadores sino de los hosts, a lo que se le conoce como Multicast Overlay Network (MON). En este artículo se plantea el enrutamiento en MON como un problema de Optimización Multiobjetivo (MOP) donde se optimizan dos funciones: 1) el retardo total extremo a extremo del árbol multicast, y 2) la máxima utilización de los enlaces. La optimización simultánea de estas dos funciones es un problema NP completo y para resolverlo se propone utilizar Algoritmos Evolutivos Multiobjetivos(MOEA), específicamente NSGAII.

1 INTRODUCCIÓN

Multicast se define como la habilidad de una red de aceptar un mensaje de una aplicación y entregar copias de este a múltiples receptores en diferentes puntos [1]. Aunque multicast, a nivel de red, fue propuesto hace un par de décadas [2], su utilización y despliegue han sido muy pobres. Aspectos técnicos y algunos factores económicos, asociados a la inversión y modificación de equipos por parte de los ISP’s, han impedido una implementación real y global de multicast IP en Internet [3]. Debido al poco despliegue de multicast a nivel de red, la tendencia en los últimos años es implementar esta función en el nivel de aplicación. Algunas propuestas se observan en [4,5, 6]. Para esto, los hosts participantes en una sesión multicast construyen entre sí una Overlay Network (ON), la cual se define como una red virtual superpuesta sobre una red física utilizando unicast. En este modelo, las funcionalidades de multicast IP tales como el envío de datos, membresía y esquema de direccionamiento, entre otras, son recargadas a los hosts destinos. Las principales ventajas que ofrecen las Multicast Overlay Network (MON) es que son de fácil despliegue, ya que no implican cambios estructurales ni adquisición de nuevos equipos en la arquitectura de los ISP’s, as ́ı como la flexibilidad dado que puede adaptarse a diversos requerimientos impuestos por las aplicaciones. Llevar esta funciona nivel de aplicación trae consigo unos retos interesantes en el momento deconstruir MON’s eficientes y se relaciona directamente con los objetivos de diseño. Tradicionalmente el problema de enrutamiento multicast en ON ha sido abordado como un problema mono–objetivo, donde solo se optimiza una función (retardo, latencia, conteo de saltos y ancho de banda, entre otras), ose consideran múltiples funciones y se transforman en una sola denominada costo. Sin embargo, en el mundo real, los problemas de diseño de redes y las diferentes aplicaciones demandan la optimización simultanea de múltiples objetivos de diseño [7].