Multi-objective optimization scheme for static and dynamic multicast flows

Abstract

Muchas de las nuevas aplicaciones emergentes de Internet tales como TV sobre Internet, Radio sobre Internet,Video Streamming multi-punto, entre otras, necesitan los siguientes requerimientos de recursos: ancho de banda consumido, retardo extremo-a-extremo, tasa de paquetes perdidos, etc. Por lo anterior, es necesario formular una propuesta que especifique y provea para este tipo de aplicaciones los recursos necesarios para su buen funcionamiento. En esta tesis, proponemos un esquema de ingeniería de tráfico multi-objetivo a través del uso de diferentes árboles de distribución para muchos flujos multicast. En este caso, estamos usando la aproximación de múltiples caminos para cada nodo egreso y de esta forma obtener la aproximación de múltiples árboles y a través de esta forma crear diferentes árboles multicast. Sin embargo, nuestra propuesta resuelve la fracción de la división del tráfico a través de múltiples árboles. La propuesta puede ser aplicada en redes MPLS estableciendo rutas explícitas en eventos multicast. En primera instancia, el objetivo es combinar los siguientes objetivos ponderados dentro de una métrica agregada: máxima utilización de los enlaces, cantidad de saltos, el ancho de banda total consumido y el retardo total extremo-a-extremo. Nosotros hemos formulado esta función multi-objetivo (modelo MHDB-S) y los resultados obtenidos muestran que varios objetivos ponderados son reducidos y la máxima utilización de los enlaces es minimizada. El problema es NP-duro, por lo tanto, un algoritmo es propuesto para optimizar los diferentes objetivos. El comportamiento que obtuvimos usando este algoritmo es similar al que obtuvimos con el modelo. Normalmente, durante la transmisión multicast los nodos egresos pueden salir o entrar del árbol y por esta razón en esta tesis proponemos un esquema de ingeniería de tráfico multi-objetivo usando diferentes árboles para grupos multicast dinámicos. (en el cual los nodos egresos pueden cambiar durante el tiempo de vida de la conexión). Si un árbol multicast es recomputado desde el principio, esto podría consumir un tiempo considerable de CPU y además todas las comuicaciones que están usando el árbol multicast serán temporalmente interrumpida. Para aliviar estos inconvenientes, proponemos un modelo de optimización (modelo dinámico MHDB-D) que utilice los árboles multicast previamente computados (modelo estático MHDB-S) adicionando nuevos nodos egreso. Usando el método de la suma ponderada para resolver el modelo analítico, no necesariamente es correcto, porque es posible tener un espacio de solución no convexo y por esta razón algunas soluciones pueden no ser encontradas. Adicionalmente, otros tipos de objetivos fueron encontrados en diferentes trabajos de investigación. Por las razones mencionadas anteriormente, un nuevo modelo llamado GMM es propuesto y para dar solución a este problema un nuevo algoritmo usando Algoritmos Evolutivos Multi-Objetivos es propuesto. Este algoritmo esta inspirado por el algoritmo Strength Pareto Evolutionary Algorithm (SPEA). Para dar una solución al caso dinámico con este modelo generalizado, nosotros hemos propuesto un nuevo modelo dinámico y una solución computacional usando Breadth First Search (BFS) probabilístico. Finalmente, para evaluar nuestro esquema de optimización propuesto, ejecutamos diferentes pruebas y simulaciones. Las principales contribuciones de esta tesis son la taxonomía, los modelos de optimización multi-objetivo para los casos estático y dinámico en transmisiones multicast (MHDB-S y MHDB-D), los algoritmos para dar solución computacional a los modelos. Finalmente, los modelos generalizados también para los casos estático y dinámico (GMM y GMM Dinámico) y las propuestas computacionales para dar slución usando MOEA y BFS probabilístico.

Many new multicast applications emerging from the Internet, such as TV over the Internet, Radio over the Internet, Video Streaming multi-point, etc., need the following resource requirements: bandwidth consumption, end-to-end delay, packet loss ratio, etc. It is therefore necessary to formulate a proposal to specify and provide for these kinds of applications the resources necessary for them to function well. In this thesis, we propose a multi-objective traffic engineering scheme using different distribution trees to multicast several flows. In this case, we are using the multipath approach to every egress node to obtain the multitree approach and of this way to create several multicast tree. Moreover, our proposal solves the traffic split ratio for multiple trees. The proposed approach can be applied in Multiprotocol Label Switching (MPLS) networks by allowing explicit routes in multicast events to be established. In the first instance, the aim is to combine the following weighting objectives into a single aggregated metric: the maximum link utilization, the hop count, the total bandwidth consumption, and the total end-to-end delay. We have formulated this multi-objective function (MHDB-S model) and the results obtained using a solver show that several weighting objectives are decreased and the maximum link utilization is minimized. The problem is NP-hard, therefore, an algorithm is proposed for optimizing the different objectives. The behavior we get using this algorithm is similar to what we get with the solver. Normally, during multicast transmission the egress node can leave and enter of the tree and for this reason in this thesis we propose a multi-objective traffic engineering scheme using different distribution trees for dynamic multicast groups (i.e. in which egress nodes can change during the connection's lifetime). If a multicast tree is recomputed from scratch, it may consume a considerable amount of CPU time and all communication using the multicast tree will be temporarily interrupted. To alleviate these drawbacks we propose an optimization model (dynamic model MHDB-D) that uses a previously computed multicast tree (static model MHDB-S) adding new egress nodes. Using the weighted sum method to solve the analytical model is not necessarily correct, because is possible to have a non-convex space solution and some solutions cannot be found. In addition, other kinds of objectives were found in different research works. For the above reasons, a new model called GMM is proposed and to find a solution to this problem a new algorithm using a Multi-Objective Evolutionary Algorithm (MOEA) is proposed too. This algorithm is inspired by the Strength Pareto Evolutionary Algorithm (SPEA). To give a solution to the dynamic case with this generalized model a dynamic GMM model is proposed and a computational solution using Breadth First Search (BFS) probabilistic is also proposed to give a solution to the dynamic case in multicast. Finally, in order to evaluate our proposed optimization scheme, we performed the necessary simulations and tests. The main contributions of this thesis are the taxonomy, the optimization model and the formulation of the multi-objective function in static and dynamic multicast transmission (MHDB-S and MHDB-D), as well as the different algorithms proposed to give computational solutions to this problem. Finally, the generalized model with several functions found in different research works in static and dynamic multicast transmission (GMM and Dynamic GMM), as well as the different algorithms proposed to give computational solutions using MOEA and BFS probabilistic.