std::string apellidos[] = { "Achával", "Maraschio", "Peyronel" };
for (std::string apellido : apellidos)
std::cout << "Tomás " << apellido << std::endl;
Este lab se basa en analizar e implementar algoritmos de enrutamiento de la capa de red.
Primero analizamos el comportamiento de un protocolo de enrutamiento muy simple. Luego, implementamos nuestro propio algoritmo de enrutamiento y vimos qué cambió con respecto a la solución inicial.
- Los nodos de la red tendrán una tasa de envío de 1 Mbps.
- El tamaño de los paquetes de datos será de 125 000 B (1 Mb).
- Con estos valores, un paquete tarda 1s en transmitirse al medio.
- El intervalo de generación de paquetes estándar será de 1 paquete por segundo, pero analizaremos distintos casos.
| Red de nodos | Cada nodo, internamente |
|---|---|
 |
 |
Esta es la red sobre la que vamos a estar trabajando: es una red anillo donde cada nodo tiene dos interfaces, una para cada vecino.
El algoritmo usado en esta parte es el que venía dado en el proyecto: cuando llega un paquete a un router se fija si está destinado a él, si no lo está lo manda al vecino de la derecha (interfaz 0). Como se ve, este es un algoritmo muy sencillo y funciona solo para redes anillo.
A continuación analizamos dos casos de uso de la red, y la carga que se genera en la misma.
Como se puede ver en el siguiente video, este caso consiste en que los nodos 0 y 2 generan paquetes para enviar con destino al nodo 5.
| Tamaño del buffer de salida del nodo 0 | Delay medido de los paquetes |
|---|---|
 |
 |
| Como ambos nodos generadores eligen la misma ruta, el nodo 0 recibe 2 paquetes por segundo (el que genera su App y el que viene del nodo 2), pero solo puede despachar 1 por segundo, ergo el aumento en su buffer | El tiempo que esperan los paquetes en el buffer de salida del nodo 0 se ve reflejado en la métrica de delay, que mide el tiempo que le toma a los paquetes en llegar de su origen a su destino. |
En este caso, como se puede observar, todos los nodos generan y mandan paquetes hacia el 5, excepto este último que solo recibe. Lo probaremos con distintos intervalos de generación y tomaremos algunas medidas del uso de la red.
| Gráficos para distintos intervalos (aproximados) de generación de paquetes | Explicación |
|---|---|
 |
Un paquete cada 1 segundo: en este caso, todos los nodos generadores excepto el 4 (quien no recibe nada) reciben 2 paquetes por segundo: el que genera su App y el que reciben de su vecino. Y como solo pueden enviar 1 paquete por segundo, sus buffers se comienzan a sobrecargar. |
 |
Un paquete cada 2 segundos: en este caso, el nodo 3 recibe 2 paquetes cada 2 segundos: el que genera su App y el que recibe del 4, pero como su tasa de transmisión le permite despacharlos a ritmo de 1 paquete por segundo, su buffer no se llena. Luego, todos los nodos siguientes al 3 (en sentido horario) reciben 2 paquetes por segundo (el que generan + uno de su vecino), por ello es que se encuentran en la misma situación que el caso anterior, con sobrecarga. El 4 también está en la misma situación que antes, es más, está la mitad del tiempo sin hacer nada. |
 |
Un paquete cada 3 segundos: este caso es igual que la situacion anterior, solo que aquí los nodos 4, 3 y 2 en conjunto producen un paquete por segundo (a este conjunto, que genera un paquete por segundo en promedio y que no se saturan, lo llamaremos grupo productor) y por lo tanto saturan aquellos que tienen por delante en sentido horario. |
 |
Un paquete cada 4 segundos: igual al anterior, con el grupo productor conformado por los nodos 4, 3, 2, y 1, y el resto saturados. |
 |
Un paquete cada 5 segundos: ahora el grupo de los "productores" son los 4, 3, 2, 1 y 0 |
 |
Un paquete cada 6 segundos: se agrega el nodo 7 al grupo de los "productores" |
 |
Un paquete cada 7 segundos: aquí finalmente todos los nodos pueden manejar la carga que reciben, es decir, entre los nodos 4,3,2,1,0,7,6 generarán 1 paquete por segundo en promedio, y todas las partes de la red son capaces de manejarlo. La variación en los tamaños de buffers del gráfico es debida a la pequeña aleatoriedad del tiempo de generación de paquetes. |
Todos los gráficos de arriba se pueden resumir en el siguiente gráfico de delay medido, donde cada curva corresponde a uno de los intervalos de generación de paquetes analizado.
| Gráfico de delay medido | Explicación |
|---|---|
 |
Como se puede ver, el hecho de que cada vez se sumen más paquetes al "grupo productor" significa que hay menos buffers que se sobrecargan y por lo tanto los paquetes sufren cada vez menos tiempo de demora para llegar a su destino. Esto ocurre hasta alcanzar la establidad del delay (la función graficada deja de ser creciente) en los intervalos de generación de un paquete cada 7 o más segundos (rosa y gris). |
Algunos conceptos:
- Matriz de costos: es una matriz almacenada en cada nodo que mapea una dirección al costo de llegar a ella a través de sus diferentes vecinos.
- Mejores salidas: es un vector, tambien almacenado en cada nodo, que mapea una dirección destino a la dirección del vecino por el que pasa el camino de menor costo. Estos son elegidos a partir de mínimos por fila en la matriz de costos.
- Vector de distancia: lo creamos a partir de las mejores salidas y la matriz de costos. Tiene pares < destino, costo al destino >.
Explicación del algoritmo implementado: Nosotros hicimos una implementación similar al algoritmo de enrutamiento de vector de distancia⁽¹⁾ que vimos en el teórico, donde cada router recibe los vectores de distancia de sus vecinos, y a partir de estos arma su vector de distancia propio. Para representar los costos de las rutas nosotros decidimos usar como distancia la cantidad de saltos entre nodos. Cada nodo usa como dirección su índice en la red (números del 0 al 7), esto lo hicimos porque necesitamos que cada nodo tenga una dirección única. Notar que no asumimos nada con respecto a la posición de un nodo en base a su dirección, son simplemente identificadores. Cuando empieza la simulación, cada nodo envía paquetes Hello a sus vecinos. En estos paquetes cada nodo pone su dirección. A su vez, cuando recibe un paquete Hello, guarda la interfaz desde dónde llegó y la dirección del vecino que lo envió; también agrega a su vector de distancia que puede llegar a ese vecino con costo 1. Cuando un nodo recibe un vector de distancia de un vecino, actualiza su matriz de costos y se fija si hay cambios en su vector de mejores salidas. En caso de haberlos, manda su vector de distancia actualizado a sus vecinos.
Mismo caso que la parte 1, nodos 2 y 0 generan y envían paquetes a nodo 5.
Como se puede ver en el video, esta vez con nuestro algoritmo en acción, se seleccionan los caminos más cortos y por lo tanto todos los paquetes enviados son recibidos sin demoras extra por esperas en bufers (salvo mínimas por aleatoriedad). No hay mucho para analizar aquí pues ninguna parte de la red se satura (el intervalo de generación aqui es de 1 paquete por segundo).
Volvemos a analizar la carga en buffers para distintos intervalos de generación, esta vez con nuestro algoritmo en acción.
A diferencia de la parte 1, donde todos los paquetes compartían un mismo camino, aquí se forman dos caminos (más cortos) por los cuales pasarán los paquetes. Es por ello que en los gráficos que se encuentran a continuación se puede ver que la estabilidad de la red se logra a partir del intervalo de generación de 1 paquete cada 4 segundos, pues el camino más largo hasta el destino tiene 4 nodos y por lo tanto nunca habrá un "grupo productor" que genere más de 4 paquetes por segundo.
| Gráficos para distintos intervalos (aproximados) de generación de paquetes | Explicación |
|---|---|
 |
Un paquete cada 1 segundo |
 |
Un paquete cada 2 segundos |
 |
Un paquete cada 3 segundos |
 |
Un paquete cada 4 segundos |
 |
Un paquete cada 5 segundos |
No ponemos los gráficos para más de 5 paquetes por segundo pues son todos de la misma forma debido a que ya se alcanzó la estabilidad.
| Gráfico de delay medido | Explicación |
|---|---|
 |
Como se puede ver, ocurre lo mismo que en la parte 1, donde el delay medido depende de la cantidad de nodos saturados. Como deja de haber nodos saturados a partir del intervalo de generación de 1 paquete cada 4 segundos, el delay se estabiliza. |
Algunas observaciones notables de la implementaciones:
- El algoritmo implementado en el kickstart depende de la topología de la red (el hecho de mandar siempre por la interfaz 0 podría generar que nunca se llegue a destino en una red no-anillo). Por otro lado, nuestro algoritmo tiene mecanismos para aprender sobre la topología de la red y los caminos más cortos hacia el resto de los nodos.
- Nuestro algoritmo podría mejorarse para manejar las situaciones en las que algún nodo se cae o se incorpora un nuevo nodo. También estaría bueno que el algortimo decida la mejor ruta teniendo en cuenta la congestión de la red (es decir, que el costo no sea solamente la cantidad de saltos).
Para finalizar, en este video se puede ver nuestro algoritmo funcionando en una red con una topología más compleja.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent