Determinación de las Formas de Salida de Paquetes en una Sesión Multicast utilizando Network Coding con Flujo R

Abstract

El inicio de Network Coding (NC) se le atribuye frecuentemente a Ahlswede, Cai, Li y Yeung en el año 2000. Ellos definieron a Network Coding como “se refiere a codificar en un nodo de una red”. Una característica de una red de computadores que va muy ligado a la calidad del servicio es el throughput, pues entre mayor sea, tomará menos tiempo el envío de información. De las ventajas más conocidas de NC es la de mejorar el throughput. Dado que con en el envío de paquetes en forma multicast, desde un nodo fuente hacia un grupo de sumideros, no siempre se logra la entrega del máximo flujo de paquetes, es importante el uso del paradigma de NC. Orientados a esta problemática, se propone solucionar lo siguiente: Dado un DAG G=(V,E), el cual representa una red de computadores para transmisión multicast uni-sesión, con un nodo s fuente, un conjunto de sumideros T⊂V\\{s}; encontrar todas las posibles formas de salida de r paquetes desde s, donde r representa el máximo flujo asociado a G, de manera que todos lleguen a los sumideros T utilizando NC. Entonces, el objetivo principal del proyecto fue diseñar e implementar un algoritmo que solucionara el problema antes mencionado. Para conseguir dicho objetivo, se llevaron a cabo una serie de pasos: Primero se idearon dos soluciones distintas, se analizó la complejidad de cada solución y se seleccionó la de menor complejidad algorítmica. Luego, se realizó un diseño del algoritmo (figura 1) y posteriormente se implementó. A la implementación se le realizaron pruebas unitarias, es decir, de 2 a 3 pruebas por cada módulo de la implementación, luego se realizaron pruebas de integración, para verificar la funcionalidad completa. Se utilizaron más de 20 grafos con diferentes topologías, cantidad de nodos y máximo flujo, mostrando resultados positivos.

The beginning of Network Coding (NC) is often attributed to Ahlswede, Cai, Li and Yeung in 2000. They define Network Coding as "refers to coding in a node of a network". A characteristic of a computer network that is closely related to the quality of the service is the throughput, because the larger it is, it will take less time to send information. Of the best known advantages of NC is to improve throughput. Given that in the multicast sending of packages, from a source node to a group of targets, the maximum packet flow delivery is not always achieved, the use of the NC paradigm is important. Oriented to this problem, it is proposed to solve the following: Given to DAG G = (V, E), which represents a network of computers for multicast transmission uni-session, with a source node s, a set of targets T⊂V \ \ {s}; find all the possible ways out of r packages from, where r represents the maximum flow associated with G, so that they all reach the targets T using NC. So, the main objective of the project was to design and implement an algorithm that solves the aforementioned problem. To achieve this goal, a series of steps were carried out: First, two different solutions were devised, the complexity of each solution was analyzed and the one with the lowest algorithmic complexity was selected. Then, an algorithm design was made (figure 1) and later it was implemented. The implementation was carried out unit tests, that is, 2 to 3 tests for each module of the implementation, then integration tests were performed, to verify the full functionality. We used more than 20 graphs with different topologies, number of nodes and maximum flow, showing positive results.